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

vm/flow_graph_builder.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_builder.h"
 
 #include "vm/ast_printer.h"
 #include "vm/bit_vector.h"
 #include "vm/code_descriptors.h"
 #include "vm/dart_entry.h"
@@ skipping 33 matching lines @@
 }
 
 
 void EffectGraphVisitor::Append(const EffectGraphVisitor& other_fragment) {
   ASSERT(is_open());
   if (other_fragment.is_empty()) return;
   if (is_empty()) {
     entry_ = other_fragment.entry();
     exit_ = other_fragment.exit();
   } else {
-    exit()->SetSuccessor(other_fragment.entry());
+    exit()->set_successor(other_fragment.entry());
     exit_ = other_fragment.exit();
   }
   temp_index_ = other_fragment.temp_index();
 }
 
 
 void EffectGraphVisitor::AddInstruction(Instruction* instruction) {
   ASSERT(is_open());
   DeallocateTempIndex(instruction->InputCount());
   if (instruction->IsDefinition()) {
     instruction->AsDefinition()->set_temp_index(AllocateTempIndex());
   }
   if (is_empty()) {
     entry_ = exit_ = instruction;
   } else {
-    exit()->SetSuccessor(instruction);
+    exit()->set_successor(instruction);
     exit_ = instruction;
   }
 }
 
 
+// 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->set_successor(fragment.entry());
+  return fragment.exit();
+}
+
+
 void EffectGraphVisitor::Join(const TestGraphVisitor& test_fragment,
                               const EffectGraphVisitor& true_fragment,
                               const EffectGraphVisitor& false_fragment) {
   // We have: a test graph fragment with zero, one, or two available exits;
   // and a pair of effect graph fragments with zero or one available exits.
   // We want to append the branch and (if necessary) a join node to this
   // graph fragment.
   ASSERT(is_open());
 
   // 1. Connect the test to this graph.
   Append(test_fragment);
 
   // 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) {
     exit_ = false_exit;  // May be NULL.
     if (false_exit != NULL) temp_index_ = false_fragment.temp_index();
   } else if (false_exit == NULL) {
     exit_ = true_exit;
     temp_index_ = true_fragment.temp_index();
   } else {
     exit_ = new JoinEntryInstr();
-    true_exit->SetSuccessor(exit_);
-    false_exit->SetSuccessor(exit_);
+    true_exit->set_successor(exit_);
+    false_exit->set_successor(exit_);
     ASSERT(true_fragment.temp_index() == false_fragment.temp_index());
     temp_index_ = true_fragment.temp_index();
   }
 }
 
 
 void EffectGraphVisitor::TieLoop(const TestGraphVisitor& test_fragment,
                                  const EffectGraphVisitor& body_fragment) {
   // We have: a test graph fragment with zero, one, or two available exits;
   // and an effect graph fragment with zero or one available exits.  We want
   // to append the 'while loop' consisting of the test graph fragment as
   // condition and the effect graph fragment as body.
   ASSERT(is_open());
 
   // 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.
   if (body_exit == NULL) {
     Append(test_fragment);
   } else {
     JoinEntryInstr* join = new JoinEntryInstr();
     AddInstruction(join);
-    join->SetSuccessor(test_fragment.entry());
-    body_exit->SetSuccessor(join);
+    join->set_successor(test_fragment.entry());
+    body_exit->set_successor(join);
   }
 
   // 3. Set the exit to the graph to be the false successor of the test, a
   // fresh target node
   exit_ = *test_fragment.false_successor_address() = new TargetEntryInstr();
 }
 
 
 Computation* EffectGraphVisitor::BuildStoreLocal(
     const LocalVariable& local, Value* value) {
@@ skipping 897 matching lines @@
 
   // Once a test fragment has been added, this fragment is closed.
   ASSERT(!is_open());
 
   // Connect all test cases except the last one.
   for (intptr_t i = 0; i < (len - 1); i++) {
     ASSERT(needs_join_at_statement_entry);
     *case_false_addresses[i] = case_entries[i + 1];
     TargetEntryInstr* true_target = new TargetEntryInstr();
     *case_true_addresses[i] = true_target;
-    true_target->SetSuccessor(statement_start);
+    true_target->set_successor(statement_start);
   }
 
   BlockEntryInstr* exit_instruction = NULL;
   // Handle last (or only) case: false goes to exit or to statement if this
   // node contains default.
   if (len > 0) {
     if (statement_start->IsTargetEntry()) {
       *case_true_addresses[len - 1] = statement_start->AsTargetEntry();
     } else {
       TargetEntryInstr* true_target = new TargetEntryInstr();
       *case_true_addresses[len - 1] = true_target;
-      true_target->SetSuccessor(statement_start);
+      true_target->set_successor(statement_start);
     }
     TargetEntryInstr* false_target = new TargetEntryInstr();
     *case_false_addresses[len - 1] = false_target;
     if (node->contains_default()) {
       // True and false go to statement start.
-      false_target->SetSuccessor(statement_start);
+      false_target->set_successor(statement_start);
       if (for_case_statements.is_open()) {
         exit_instruction = new TargetEntryInstr();
-        for_case_statements.exit()->SetSuccessor(exit_instruction);
+        for_case_statements.exit()->set_successor(exit_instruction);
       }
     } else {
       if (for_case_statements.is_open()) {
         exit_instruction = new JoinEntryInstr();
-        for_case_statements.exit()->SetSuccessor(exit_instruction);
+        for_case_statements.exit()->set_successor(exit_instruction);
       } else {
         exit_instruction = new TargetEntryInstr();
       }
-      false_target->SetSuccessor(exit_instruction);
+      false_target->set_successor(exit_instruction);
     }
   } else {
     // A CaseNode without case expressions must contain default.
     ASSERT(node->contains_default());
     AddInstruction(statement_start);
   }
 
   ASSERT(!is_open());
   exit_ = exit_instruction;
 }
@@ skipping 54 matching lines @@
 
   TestGraphVisitor for_test(owner(),
                             temp_index(),
                             node->condition()->token_pos());
   node->condition()->Visit(&for_test);
   ASSERT(is_open());
 
   // 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;
     if (node->label()->join_for_continue() == NULL) {
       test_entry = new TargetEntryInstr();
     } else {
       test_entry = node->label()->join_for_continue();
     }
-    test_entry->SetSuccessor(for_test.entry());
+    test_entry->set_successor(for_test.entry());
     if (body_exit != NULL) {
-      body_exit->SetSuccessor(test_entry);
+      body_exit->set_successor(test_entry);
     }
   }
 
   TargetEntryInstr* back_target_entry = new TargetEntryInstr();
   *for_test.true_successor_address() = back_target_entry;
-  back_target_entry->SetSuccessor(body_entry_join);
+  back_target_entry->set_successor(body_entry_join);
   TargetEntryInstr* loop_exit_target = new TargetEntryInstr();
   *for_test.false_successor_address() = loop_exit_target;
   if (node->label()->join_for_break() == NULL) {
     exit_ = loop_exit_target;
   } else {
-    loop_exit_target->SetSuccessor(node->label()->join_for_break());
+    loop_exit_target->set_successor(node->label()->join_for_break());
     exit_ = node->label()->join_for_break();
   }
 }
 
 
 // A ForNode can contain break and continue jumps. 'break' joins to
 // ForNode exit, 'continue' joins at increment entry. The fragment is composed
 // as follows:
 // a) [ initializer ]
 // b) loop-join
@@ skipping 26 matching lines @@
   if ((node->label()->join_for_continue() == NULL) && for_body.is_open()) {
     // Do not insert an extra basic block.
     node->increment()->Visit(&for_increment);
     for_body.Append(for_increment);
     loop_increment_end = for_body.exit();
     // 'for_body' contains at least the TargetInstruction 'body_entry'.
     ASSERT(loop_increment_end != NULL);
   } else if (node->label()->join_for_continue() != NULL) {
     // Insert join between body and increment.
     if (for_body.is_open()) {
-      for_body.exit()->SetSuccessor(node->label()->join_for_continue());
+      for_body.exit()->set_successor(node->label()->join_for_continue());
     }
     for_increment.AddInstruction(node->label()->join_for_continue());
     node->increment()->Visit(&for_increment);
     loop_increment_end = for_increment.exit();
     ASSERT(loop_increment_end != NULL);
   } else {
     loop_increment_end = NULL;
     ASSERT(!for_body.is_open() && node->label()->join_for_continue() == NULL);
   }
 
   // 'loop_increment_end' is NULL only if there is no join for continue and the
   // body is not open, i.e., no backward branch exists.
   if (loop_increment_end != NULL) {
     JoinEntryInstr* loop_start = new JoinEntryInstr();
     AddInstruction(loop_start);
-    loop_increment_end->SetSuccessor(loop_start);
+    loop_increment_end->set_successor(loop_start);
   }
 
   if (node->condition() == NULL) {
     // Endless loop, no test.
     Append(for_body);
     if (node->label()->join_for_break() == NULL) {
       CloseFragment();
     } else {
       // Control flow of ForLoop continues into join_for_break.
       exit_ = node->label()->join_for_break();
     }
   } else {
     TargetEntryInstr* loop_exit = new TargetEntryInstr();
     TestGraphVisitor for_test(owner(),
                               temp_index(),
                               node->condition()->token_pos());
     node->condition()->Visit(&for_test);
     Append(for_test);
     *for_test.true_successor_address() = body_entry;
     *for_test.false_successor_address() = loop_exit;
     if (node->label()->join_for_break() == NULL) {
       exit_ = loop_exit;
     } else {
-      loop_exit->SetSuccessor(node->label()->join_for_break());
+      loop_exit->set_successor(node->label()->join_for_break());
       exit_ = node->label()->join_for_break();
     }
   }
 }
 
 
 void EffectGraphVisitor::VisitJumpNode(JumpNode* node) {
   for (intptr_t i = 0; i < node->inlined_finally_list_length(); i++) {
     EffectGraphVisitor for_effect(owner(), temp_index());
     node->InlinedFinallyNodeAt(i)->Visit(&for_effect);
@@ skipping 1092 matching lines @@
                                &postorder_block_entries_,
                                &parent,
                                &assigned_vars,
                                variable_count);
   // Number blocks in reverse postorder.
   intptr_t block_count = postorder_block_entries_.length();
   for (intptr_t i = 0; i < block_count; ++i) {
     postorder_block_entries_[i]->set_block_id(block_count - i - 1);
   }
   if (for_optimized && use_ssa) {
+    // Link instructions backwards for optimized compilation.
+    for (intptr_t i = 0; i < block_count; ++i) {
+      Instruction* prev = postorder_block_entries_[i];
+      Instruction* current = prev->successor();
+      while (current != NULL && !current->IsBlockEntry()) {
+        current->set_previous(prev);
+        prev = current;
+        current = current->successor();
+      }
+    }
     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();
@@ skipping 247 matching lines @@
         PhiInstr* phi = (*join->phis())[i];
         if (phi != NULL) {
           (*env)[i] = new UseVal(phi);
           phi->set_ssa_temp_index(current_ssa_temp_index_++);  // New SSA temp.
         }
       }
     }
   }
 
   // 2. Process normal instructions.
-  Instruction* current = block_entry->StraightLineSuccessor();
-  Instruction* prev = block_entry;
+  Instruction* current = block_entry->successor();
   while ((current != NULL) && !current->IsBlockEntry()) {
     // 2a. Handle uses of LoadLocal / StoreLocal
     // For each use of a LoadLocal or StoreLocal: Replace it with the value
     // from the environment.
     for (intptr_t i = 0; i < current->InputCount(); ++i) {
       Value* v = current->InputAt(i);
       if (v->IsUse() &&
           v->AsUse()->definition()->IsBind() &&
           v->AsUse()->definition()->AsBind()->computation()->IsLoadLocal()) {
         Computation* comp = v->AsUse()->definition()->AsBind()->computation();
@@ skipping 35 matching lines @@
     if (current->IsDo() &&
         current->AsDo()->computation()->IsStoreLocal()) {
       store = current->AsDo()->computation()->AsStoreLocal();
     } else if (current->IsBind() &&
                current->AsBind()->computation()->IsStoreLocal()) {
       store = current->AsBind()->computation()->AsStoreLocal();
     }
 
     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();
+    current = current->successor();
   }
 
   // 3. Process dominated blocks.
   for (intptr_t i = 0; i < block_entry->dominated_blocks().length(); ++i) {
     BlockEntryInstr* block = block_entry->dominated_blocks()[i];
     ZoneGrowableArray<Value*>* new_env =
         new ZoneGrowableArray<Value*>(var_count);
     new_env->AddArray(*env);
     RenameRecursive(block, new_env, var_count);
   }
@@ skipping 28 matching lines @@
   char* chars = reinterpret_cast<char*>(
       Isolate::Current()->current_zone()->Allocate(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);
 }
 
 
 }  // namespace dart