Introduce Goto instructions to the flow graph.

runtime/vm/flow_graph_allocator.cc

Index: runtime/vm/flow_graph_allocator.cc
diff --git a/runtime/vm/flow_graph_allocator.cc b/runtime/vm/flow_graph_allocator.cc
index 9230dac1452c6c69b3a3881f2052462221db101c..c81420e1e25ccb2416641b748a3fa42b31e52966 100644
--- a/runtime/vm/flow_graph_allocator.cc
+++ b/runtime/vm/flow_graph_allocator.cc
@@ -385,60 +385,60 @@ void FlowGraphAllocator::BuildLiveRanges() {
       range->AddUseInterval(block->start_pos(), block->end_pos());
     }
 
-    // Position corresponding to the end of the last instruction in the block.
-    intptr_t pos = block->end_pos() - 1;
-
+    // Position corresponding to the beginning of the last instruction in the
+    // block.
+    intptr_t pos = block->end_pos() - 2;
     Instruction* current = block->last_instruction();
 
-    // If last instruction is a parallel move we need to perform phi resolution.
-    if (current->IsParallelMove()) {
+    // Goto instructions do not contribute liveness information.
+    GotoInstr* goto_instr = current->AsGoto();

[Vyacheslav Egorov (Google), 2012/07/16 12:42:55]

I suggest you just don't give goto a position in NumberInstructions.

+    if (goto_instr != NULL) {
+      --pos;  // The end of the previous instruction.
+      current = current->previous();
+      // If we have a parallel move here then the successor block must be a
+      // join with phis.  The phi inputs contribute uses to the predecessor
+      // blocks (and the phi outputs are definitions in the successor block).
       ParallelMoveInstr* parallel_move = current->AsParallelMove();
-      JoinEntryInstr* join = current->next()->AsJoinEntry();
-      ASSERT(join != NULL);
-
-      // Find index of the current block in predecessors of join.
-      intptr_t pred_idx = -1;
-      for (intptr_t j = 0; j < join->PredecessorCount(); j++) {
-        BlockEntryInstr* pred = join->PredecessorAt(j);
-        if (pred == block) {
-          pred_idx = j;
-          break;
+      if (parallel_move != NULL) {
+        JoinEntryInstr* join = goto_instr->successor();
+        ASSERT(join != NULL);
+
+        // Search for the index of the current block in the predecessors of
+        // the join.  TODO(kmillikin): record the predecessor index in the
+        // goto when building the predecessor list to avoid this search.
+        intptr_t pred_idx = 0;
+        for (; pred_idx < join->PredecessorCount(); pred_idx++) {
+          if (join->PredecessorAt(pred_idx) == block) break;
         }
-      }
-      ASSERT(pred_idx != -1);
-
-      // For every phi we have a reserved phi resolution move and we need
-      // to either initialize its source with constant or to register a use, so
-      // that register allocator will populate source slot with location of
-      // the appropriate SSA value.
-      ZoneGrowableArray<PhiInstr*>* phis = join->phis();
-      intptr_t move_idx = 0;
-      for (intptr_t j = 0; j < phis->length(); j++) {
-        PhiInstr* phi = (*phis)[j];
-        if (phi == NULL) continue;
+        ASSERT(pred_idx < join->PredecessorCount());
 
-        Value* val = phi->InputAt(pred_idx);
+        // Record the corresponding phi input use for each phi.
+        ZoneGrowableArray<PhiInstr*>* phis = join->phis();
+        for (intptr_t move_idx = 0; move_idx < phis->length(); move_idx++) {
+          PhiInstr* phi = (*phis)[move_idx];
+          if (phi == NULL) continue;
 
-        MoveOperands move = parallel_move->moves()[move_idx];
-        if (val->IsUse()) {
-          const intptr_t use = val->AsUse()->definition()->ssa_temp_index();
-          Location* slot = move.src_slot();
-          *slot = Location::RequiresRegister();
-          GetLiveRange(use)->head()->AddUse(NULL, pos, slot);
-        } else {
-          ASSERT(val->IsConstant());
-          move.set_src(Location::Constant(val->AsConstant()->value()));
+          Value* val = phi->InputAt(pred_idx);
+          MoveOperands move = parallel_move->moves()[move_idx];
+          if (val->IsUse()) {
+            const intptr_t virtual_register =
+                val->AsUse()->definition()->ssa_temp_index();
+            Location* slot = move.src_slot();
+            *slot = Location::RequiresRegister();
+            GetLiveRange(virtual_register)->head()->AddUse(NULL, pos, slot);
+          } else {
+            ASSERT(val->IsConstant());
+            move.set_src(Location::Constant(val->AsConstant()->value()));
+          }
         }
 
-        move_idx++;
+        // Skip to the instruction before the parallel move.
+        pos -= 3;  // The beginning of the previous instruction.

[Vyacheslav Egorov (Google), 2012/07/16 12:42:55]

I don't get where -3 comes from. we now have -6 in total here. which is 3
instructions in total, but it's only goto an last instruction, so it should be
-4 tops. (ParallelMove should have no position, and I suggest goto should have
none as well, then pos should be just -2).

[Kevin Millikin (Google), 2012/07/16 13:47:48]

I was counting both the goto and the parallel move.

I missed the way that NumberInstructions assigned numbers to some but not all
instructions.  Obviously this this code that recreates the instruction numbers
needs to account for that.

I'll change it to not number those two classes of instructions, but I think that
makes the situation worse, not better.  I would say we should either (1) just
read the number off the instruction and not try to recompute the same number
here or (2) make the numbering completely uniform for all instructions even if
it leaks integers.

+        current = current->previous();
       }
-
-      current = current->previous();
     }
 
     // Now process all instructions in reverse order.
-    // Advance position to the start of the last instruction in the block.
-    pos -= 1;
     while (current != block) {
       LocationSummary* locs = current->locs();
 
@@ -520,8 +520,8 @@ void FlowGraphAllocator::BuildLiveRanges() {
                locs->out_slot());
       }
 
-      current = current->previous();
       pos -= 2;
+      current = current->previous();
     }
 
     // If this block is a join we need to add destinations of phi
@@ -588,19 +588,24 @@ void FlowGraphAllocator::NumberInstructions() {
     if (block->IsJoinEntry() && (block->AsJoinEntry()->phi_count() > 0)) {
       const intptr_t phi_count = block->AsJoinEntry()->phi_count();
       for (intptr_t i = 0; i < block->PredecessorCount(); i++) {
-        BlockEntryInstr* pred = block->PredecessorAt(i);
-        ASSERT(!pred->last_instruction()->IsParallelMove());
-
         ParallelMoveInstr* move = new ParallelMoveInstr();
-        move->set_next(block);
-        move->set_previous(pred->last_instruction());
-        pred->last_instruction()->set_next(move);
-        pred->set_last_instruction(move);
-
-        // Populate ParallelMove with empty moves.
+        // Populate the ParallelMove with empty moves.
         for (intptr_t j = 0; j < phi_count; j++) {
           move->AddMove(Location::NoLocation(), Location::NoLocation());
         }
+
+        // Insert the move between the last two instructions of the
+        // predecessor block (all such blocks have at least two instructions:
+        // the block entry and goto instructions.)
+        BlockEntryInstr* pred = block->PredecessorAt(i);
+        Instruction* next = pred->last_instruction();
+        Instruction* previous = next->previous();
+        ASSERT(next->IsGoto());
+        ASSERT(!previous->IsParallelMove());  // Why??

[Vyacheslav Egorov (Google), 2012/07/16 12:42:55]

ParallelMove should be created only once. (verification of an edge split form:
join can't have a predecessor with multiple-successors).

[Kevin Millikin (Google), 2012/07/16 13:47:48]

It seems like an indirect way to assert that.  It would probably be nicer to
just make it impossible (i.e., have a dedicated parallel move for phi resolution
that lies outside the instruction stream and so always at the end of the block).

It's already impossible to have the violation, because the only instructions
with multiple successors are GraphEntry and Branch, and those successors have
type TargetEntryInstr*.

+        previous->set_next(move);
+        move->set_previous(previous);
+        move->set_next(next);
+        next->set_previous(move);
       }
     }
   }