Implement loop invariant code motion for check instructions.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph_optimizer.h"
 
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/hash_map.h"
 #include "vm/il_printer.h"
@@ skipping 1127 matching lines @@
       LocationSummary* locs = it.Current()->locs();
       if ((locs != NULL) && locs->can_call()) {
         is_leaf_ = false;
         return;
       }
     }
   }
 }
 
 
+static BlockEntryInstr* FindPreHeader(BlockEntryInstr* header) {
+  for (intptr_t j = 0; j < header->PredecessorCount(); ++j) {
+    BlockEntryInstr*  candidate = header->PredecessorAt(j);

[Kevin Millikin (Google), 2012/09/06 12:42:42]

Extra space!

[Florian Schneider, 2012/09/06 13:05:53]

Done.

+    if (header->dominator() == candidate) {
+      return candidate;
+    }
+  }
+  return NULL;
+}
+
+
+void LICM::Optimize(FlowGraph* flow_graph) {
+  GrowableArray<BlockEntryInstr*> loop_headers;
+  flow_graph->ComputeLoops(&loop_headers);
+
+  for (intptr_t i = 0; i < loop_headers.length(); ++i) {
+    BlockEntryInstr* header = loop_headers[i];
+    // Skip loop that don't have a pre-header block.
+    BlockEntryInstr* pre_header = FindPreHeader(header);
+    if (pre_header == NULL) continue;
+
+    for (intptr_t j = 0; j < header->loop_info()->length(); ++j) {
+      BlockEntryInstr* block = (*header->loop_info())[j];
+      for (ForwardInstructionIterator it(block);
+           !it.Done();
+           it.Advance()) {
+        Definition* current = it.Current()->AsDefinition();
+        if (current != NULL &&
+            !current->IsPushArgument() &&
+            !current->HasSideEffect()) {
+          bool inputs_loop_invariant = true;
+          for (int i = 0; i < current->InputCount(); ++i) {
+            Definition* input_def = current->InputAt(i)->definition();
+            if (!input_def->GetBlock()->Dominates(pre_header)) {
+              inputs_loop_invariant = false;
+              break;
+            }
+          }
+          if (inputs_loop_invariant) {
+            // TODO(fschneider): Avoid repeated deoptimization when
+            // speculatively hoisting checks.
+            if (FLAG_trace_optimization) {
+              OS::Print("Hoisting instruction %s:%"Pd" from B%"Pd" to B%"Pd"\n",
+                        current->DebugName(),
+                        current->deopt_id(),
+                        current->GetBlock()->block_id(),
+                        pre_header->block_id());
+            }
+            // Move the instruction out of the loop.
+            it.RemoveCurrentFromGraph();
+            GotoInstr* last = pre_header->last_instruction()->AsGoto();
+            current->InsertBefore(last);
+            // Attach the environment of the Goto instruction to the hoisted
+            // instruction.
+            ASSERT(last->env() != NULL);
+            last->env()->CopyTo(current);
+            current->deopt_id_ = last->GetDeoptId();
+          }
+        }
+      }
+    }
+  }
+}
+
+
 void DominatorBasedCSE::Optimize(BlockEntryInstr* graph_entry) {
   ASSERT(graph_entry->IsGraphEntry());
   DirectChainedHashMap<Definition*> map;
   OptimizeRecursive(graph_entry, &map);
 }
 
 
 void DominatorBasedCSE::OptimizeRecursive(
     BlockEntryInstr* block,
     DirectChainedHashMap<Definition*>* map) {
@@ skipping 23 matching lines @@
       DirectChainedHashMap<Definition*> child_map(*map);  // Copy map.
       OptimizeRecursive(child, &child_map);
     } else {
       OptimizeRecursive(child, map);  // Reuse map for the last child.
     }
   }
 }
 
 
 }  // namespace dart