Implement loop invariant code motion for check instructions.

runtime/vm/flow_graph.cc

Index: runtime/vm/flow_graph.cc
===================================================================
--- runtime/vm/flow_graph.cc	(revision 11934)
+++ runtime/vm/flow_graph.cc	(working copy)
@@ -12,6 +12,8 @@
 
 namespace dart {
 
+DECLARE_FLAG(bool, trace_optimization);
+
 FlowGraph::FlowGraph(const FlowGraphBuilder& builder,
                      GraphEntryInstr* graph_entry)
   : parent_(),
@@ -497,7 +499,7 @@
   // Initialize start environment.
   GrowableArray<Definition*> start_env(variable_count());
   for (intptr_t i = 0; i < parameter_count(); ++i) {
-    ParameterInstr* param = new ParameterInstr(i);
+    ParameterInstr* param = new ParameterInstr(i, graph_entry_);
     param->set_ssa_temp_index(alloc_ssa_temp_index());  // New SSA temp.
     start_env.Add(param);
   }
@@ -664,6 +666,61 @@
 }
 
 
+// Find the natural loop for the back edge m->n and attach loop information
+// to block n (loop header). The algorithm is described in "Advanced Compiler
+// Design & Implementation" (Muchnick) p192.
+static void FindLoop(BlockEntryInstr* m, BlockEntryInstr* n) {

[srdjan, 2012/09/06 13:44:26]

There is also FlowGraphAllocator::DiscoverLoops, how do they differ, are they
both necessary?

[Florian Schneider, 2012/09/06 13:49:30]

Good point. I didn't remember that we have such a thing. Mine is more generic,
so I'll replace the old one.

+  GrowableArray<BlockEntryInstr*> stack;
+  ZoneGrowableArray<BlockEntryInstr*>* loop =

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

Consider a bit vector indexed by preorder block number to make Contains constant
time.

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

Done.

+      new ZoneGrowableArray<BlockEntryInstr*>(2);
+
+  loop->Add(n);
+  if (n != m) {
+    loop->Add(m);
+    stack.Add(m);
+  }
+
+  while (!stack.is_empty()) {
+    BlockEntryInstr* p = stack.Last();
+    stack.RemoveLast();
+    for (intptr_t i = 0; i < p->PredecessorCount(); ++i) {
+      BlockEntryInstr* q = p->PredecessorAt(i);
+      if (!loop->Contains(q)) {
+        loop->Add(q);
+        stack.Add(q);
+      }
+    }
+  }
+  n->set_loop_info(loop);
+  if (FLAG_trace_optimization) {
+    for (intptr_t i = 0; i < loop->length(); i++) {
+      OS::Print("  B%"Pd"\n", (*loop)[i]->block_id());
+    }
+  }
+}
+
+
+void FlowGraph::ComputeLoops(GrowableArray<BlockEntryInstr*>* loop_headers) {
+  ASSERT(loop_headers->is_empty());
+  for (BlockIterator it = postorder_iterator();
+       !it.Done();
+       it.Advance()) {
+    BlockEntryInstr* block = it.Current();
+    for (intptr_t i = 0; i < block->PredecessorCount(); ++i) {
+      BlockEntryInstr* pred = block->PredecessorAt(i);
+      if (block->Dominates(pred)) {
+        if (FLAG_trace_optimization) {
+          OS::Print("Back edge B%"Pd" -> B%"Pd"\n", pred->block_id(),
+                    block->block_id());
+        }
+        FindLoop(pred, block);
+        loop_headers->Add(block);
+      }
+    }
+  }
+}
+
+
 void FlowGraph::Bailout(const char* reason) const {
   const char* kFormat = "FlowGraph Bailout: %s %s";
   const char* function_name = parsed_function_.function().ToCString();