Implement loop invariant code motion for check instructions.

runtime/vm/flow_graph.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.h"
 
 #include "vm/bit_vector.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/intermediate_language.h"
 #include "vm/longjump.h"
 #include "vm/growable_array.h"
 
 namespace dart {
 
+DECLARE_FLAG(bool, trace_optimization);
+
 FlowGraph::FlowGraph(const FlowGraphBuilder& builder,
                      GraphEntryInstr* graph_entry)
   : parent_(),
     assigned_vars_(),
     current_ssa_temp_index_(0),
     parsed_function_(builder.parsed_function()),
     copied_parameter_count_(builder.copied_parameter_count()),
     non_copied_parameter_count_(builder.non_copied_parameter_count()),
     stack_local_count_(builder.stack_local_count()),
     graph_entry_(graph_entry),
@@ skipping 465 matching lines @@
   if (graph_entry_->SuccessorCount() > 1) {
     Bailout("Catch-entry support in SSA.");
   }
 
   // Name global constants.
   graph_entry_->constant_null()->set_ssa_temp_index(alloc_ssa_temp_index());
 
   // 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);
   }
 
   // All locals are initialized with #null.  Use the global definition, uses
   // will be created in the Environment constructor.
   while (start_env.length() < variable_count()) {
     start_env.Add(graph_entry_->constant_null());
   }
   graph_entry_->set_start_env(
@@ skipping 146 matching lines @@
       PhiInstr* used_phi = val->definition()->AsPhi();
       if ((used_phi != NULL) && !used_phi->is_alive()) {
         used_phi->mark_alive();
         live_phis->Add(used_phi);
       }
     }
   }
 }
 
 
+// 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();
   intptr_t len = OS::SNPrint(NULL, 0, kFormat, function_name, reason) + 1;
   char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
   OS::SNPrint(chars, len, kFormat, function_name, reason);
   const Error& error = Error::Handle(
       LanguageError::New(String::Handle(String::New(chars))));
   Isolate::Current()->long_jump_base()->Jump(1, error);
 }
@@ skipping 57 matching lines @@
   // Remove original arguments to the call.
   for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {
     PushArgumentInstr* push = call->ArgumentAt(i);
     push->ReplaceUsesWith(push->value()->definition());
     push->RemoveFromGraph();
   }
 }
 
 
 }  // namespace dart