Make IL instructions a doubly-linked list within basic blocks.

vm/flow_graph_builder.cc

Index: vm/flow_graph_builder.cc
===================================================================
--- vm/flow_graph_builder.cc	(revision 9056)
+++ vm/flow_graph_builder.cc	(working copy)
@@ -73,6 +73,16 @@
 }
 
 
+// Appends a graph fragment to a block entry instruction and returns the exit
+// of the resulting graph fragment.
+static Instruction* AppendFragment(BlockEntryInstr* entry,
+                                   const EffectGraphVisitor& fragment) {
+  if (fragment.is_empty()) return entry;
+  entry->SetSuccessor(fragment.entry());
+  return fragment.exit();
+}

[srdjan, 2012/06/25 15:57:16]

I like it a lot that we factor out the knowledge of how the IL nodes are
connected.

+
+
 void EffectGraphVisitor::Join(const TestGraphVisitor& test_fragment,
                               const EffectGraphVisitor& true_fragment,
                               const EffectGraphVisitor& false_fragment) {
@@ -87,17 +97,13 @@
 
   // 2. Connect the true and false bodies to the test and record their exits
   // (if any).
-  Instruction* true_exit = NULL;
-  Instruction* false_exit = NULL;
   TargetEntryInstr* true_entry = new TargetEntryInstr();
   *test_fragment.true_successor_address() = true_entry;
-  true_entry->SetSuccessor(true_fragment.entry());
-  true_exit = true_fragment.is_empty() ? true_entry : true_fragment.exit();
+  Instruction* true_exit = AppendFragment(true_entry, true_fragment);
 
   TargetEntryInstr* false_entry = new TargetEntryInstr();
   *test_fragment.false_successor_address() = false_entry;
-  false_entry->SetSuccessor(false_fragment.entry());
-  false_exit = false_fragment.is_empty() ? false_entry : false_fragment.exit();
+  Instruction* false_exit = AppendFragment(false_entry, false_fragment);
 
   // 3. Add a join or select one (or neither) of the arms as exit.
   if (true_exit == NULL) {
@@ -126,11 +132,9 @@
 
   // 1. Connect the body to the test if it is reachable, and if so record
   // its exit (if any).
-  Instruction* body_exit = NULL;
   TargetEntryInstr* body_entry = new TargetEntryInstr();
   *test_fragment.true_successor_address() = body_entry;
-  body_entry->SetSuccessor(body_fragment.entry());
-  body_exit = body_fragment.is_empty() ? body_entry : body_fragment.exit();
+  Instruction* body_exit = AppendFragment(body_entry, body_fragment);
 
   // 2. Connect the test to this graph, including the body if reachable and
   // using a fresh join node if the body is reachable and has an open exit.
@@ -1125,9 +1129,7 @@
   // Tie do-while loop (test is after the body).
   JoinEntryInstr* body_entry_join = new JoinEntryInstr();
   AddInstruction(body_entry_join);
-  body_entry_join->SetSuccessor(for_body.entry());
-  Instruction* body_exit =
-      for_body.is_empty() ? body_entry_join : for_body.exit();
+  Instruction* body_exit = AppendFragment(body_entry_join, for_body);
 
   if (for_body.is_open() || (node->label()->join_for_continue() != NULL)) {
     BlockEntryInstr* test_entry = NULL;
@@ -2349,14 +2351,28 @@
   for (intptr_t i = 0; i < block_count; ++i) {
     postorder_block_entries_[i]->set_block_id(block_count - i - 1);
   }
-  if (for_optimized && FLAG_use_ssa) {
-    GrowableArray<BitVector*> dominance_frontier;
-    ComputeDominators(&preorder_block_entries_, &parent, &dominance_frontier);
-    InsertPhis(preorder_block_entries_,
-               assigned_vars,
-               variable_count,
-               dominance_frontier);
-    Rename(variable_count);
+  if (for_optimized) {
+    // Link instructions backwards for optimized compilation.
+    for (intptr_t i = 0; i < block_count; ++i) {
+      Instruction* prev = postorder_block_entries_[i];
+      Instruction* current = prev->StraightLineSuccessor();
+      while (current != NULL && !current->IsBlockEntry()) {
+        current->SetPrevious(prev);
+        prev = current;
+        current = current->StraightLineSuccessor();
+      }
+    }
+
+    // Construct SSA form.
+    if (FLAG_use_ssa) {
+      GrowableArray<BitVector*> dominance_frontier;
+      ComputeDominators(&preorder_block_entries_, &parent, &dominance_frontier);
+      InsertPhis(preorder_block_entries_,
+                 assigned_vars,
+                 variable_count,
+                 dominance_frontier);
+      Rename(variable_count);
+    }
   }
   if (FLAG_print_flow_graph || (Dart::flow_graph_writer() != NULL)) {
     intptr_t length = postorder_block_entries_.length();
@@ -2618,7 +2634,6 @@
 
   // 2. Process normal instructions.
   Instruction* current = block_entry->StraightLineSuccessor();
-  Instruction* prev = block_entry;
   while ((current != NULL) && !current->IsBlockEntry()) {
     // 2a. Handle uses of LoadLocal / StoreLocal
     // For each use of a LoadLocal or StoreLocal: Replace it with the value
@@ -2674,18 +2689,14 @@
 
     if (load != NULL) {
       // Remove instruction.
-      prev->SetSuccessor(current->StraightLineSuccessor());
+      current->RemoveFromGraph();
     } else if (store != NULL) {
       // Remove instruction and update renaming environment.
-      prev->SetSuccessor(current->StraightLineSuccessor());
+      current->RemoveFromGraph();
       (*env)[store->local().BitIndexIn(var_count)] = store->value();
-    } else {
+    } else if (current->IsBind()) {
       // Assign new SSA temporary.
-      if (current->IsBind()) {
-        current->AsDefinition()->set_ssa_temp_index(current_ssa_temp_index_++);
-      }
-      // Update previous only if no instruction was removed from the graph.
-      prev = current;
+      current->AsDefinition()->set_ssa_temp_index(current_ssa_temp_index_++);
     }
     current = current->StraightLineSuccessor();
   }