Implement loop invariant code motion for check instructions.

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
===================================================================
--- runtime/vm/flow_graph_optimizer.cc	(revision 11934)
+++ runtime/vm/flow_graph_optimizer.cc	(working copy)
@@ -1145,6 +1145,71 @@
 }
 
 
+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;