Introduce Goto instructions to the flow graph.

runtime/vm/flow_graph_allocator.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_allocator.h"
 
 #include "vm/bit_vector.h"
 #include "vm/intermediate_language.h"
 #include "vm/il_printer.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 367 matching lines @@
     BlockEntryInstr* block = postorder_[i];
 
     // For every SSA value that is live out of this block create an interval
     // that covers the hole block.  It will be shortened if we encounter a
     // definition of this value in this block.
     for (BitVector::Iterator it(live_out_[i]); !it.Done(); it.Advance()) {
       LiveRange* range = GetLiveRange(it.Current());
       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);
+      if (parallel_move != NULL) {
+        JoinEntryInstr* join = goto_instr->successor();
+        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;
+        // 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);
+        ASSERT(pred_idx < join->PredecessorCount());
 
-      // 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;
+        // 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;
 
-        Value* val = phi->InputAt(pred_idx);
-
-        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();
 
       const bool output_same_as_first_input =
         locs->out().IsUnallocated() &&
         locs->out().policy() == Location::kSameAsFirstInput;
 
       // TODO(vegorov): number of inputs should match number of input locations.
       // TODO(vegorov): generic support for writable registers?
       for (intptr_t j = 0; j < current->InputCount(); j++) {
@@ skipping 61 matching lines @@
       }
 
       Definition* def = current->AsDefinition();
       if ((def != NULL) && (def->ssa_temp_index() >= 0)) {
         Define(output_same_as_first_input ? current : NULL,
                pos,
                def->ssa_temp_index(),
                locs->out_slot());
       }
 
+      pos -= 2;
       current = current->previous();
-      pos -= 2;
     }
 
     // If this block is a join we need to add destinations of phi
     // resolution moves to phi's live range so that register allocator will
     // fill them with moves.
     if (block->IsJoinEntry() && block->AsJoinEntry()->phis() != NULL) {
       ZoneGrowableArray<PhiInstr*>* phis = block->AsJoinEntry()->phis();
 
       intptr_t move_idx = 0;
       for (intptr_t j = 0; j < phis->length(); j++) {
@@ skipping 46 matching lines @@
       current = current->next();
       pos += 2;
     }
     block->set_end_pos(pos);
 
     // For join entry predecessors create phi resolution moves if
     // necessary. They will be populated by the register allocator.
     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);
       }
     }
   }
 }
 
 
 intptr_t UseInterval::Intersect(UseInterval* other) {
   if (this->start() <= other->start()) {
     if (other->start() < this->end()) return other->start();
   } else if (this->start() < other->end()) {
@@ skipping 313 matching lines @@
 
   if (FLAG_trace_ssa_allocator) {
     OS::Print("-- ir after allocation -------------------------\n");
     FlowGraphPrinter printer(Function::Handle(), block_order_, true);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart