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.
+    // Position corresponding to the beginning of the last instruction in the
+    // block.
     intptr_t pos = block->end_pos() - 1;
-
     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();
+    if (goto_instr != NULL) {
+      current = current->previous();
+      // If we have a parallel move here then the successor block must be a

[srdjan, 2012/07/16 16:50:45]

must start with a join with phis

+      // join with phis.  The phi inputs contribute uses to each predecessor
+      // block (and the phi outputs contribute definitions in the successor
+      // block).
+      //
+      // We record those uses at the end of the instruction preceding the
+      // parallel move.  This position is 'pos', because we do not assign
+      // instruction numbers to parallel moves.
       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++;
+        // Begin backward iteration with the instruction before the parallel
+        // move.
+        current = current->previous();

[srdjan, 2012/07/16 16:50:45]

According to the comment this should this be 'current =
parallel_move->previous()'  and inside 'if (parallel_move ! = NULL)', no?

[Kevin Millikin (Google), 2012/07/18 09:47:11]

Yes.  It's hard to see on the codereview tool, but this is inside parallel_move
!= NULL already and in that case parallel_move == current->AsParallelMove().

       }
-
-      current = current->previous();
     }
 
     // Now process all instructions in reverse order.
-    // Advance position to the start of the last instruction in the block.
-    pos -= 1;
+    --pos;  // 'pos' is now the start position for the current instruction.
     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 103 matching lines @@
         // All phi resolution moves are connected. Phi's live range is complete.
         AddToUnallocated(interval);
 
         move_idx++;
       }
     }
   }
 }
 
 
+// Linearize the control flow graph.  The chosen order will be used by the
+// linear-scan register allocator.  Number most instructions with a pair of
+// numbers representing lifetime positions.  Introduce explicit parallel
+// move instructions in the predecessors of join nodes.  The moves are used
+// for phi resolution.

[Vyacheslav Egorov (Google), 2012/07/16 14:16:41]

there is a comment in the header file. you can copy it to here

 void FlowGraphAllocator::NumberInstructions() {
   intptr_t pos = 0;
 
+  // The basic block order is reverse postorder.
   const intptr_t block_count = postorder_.length();
   for (intptr_t i = block_count - 1; i >= 0; i--) {
     BlockEntryInstr* block = postorder_[i];
-
     block->set_start_pos(pos);
+    block->set_lifetime_position(pos);
     pos += 2;
-    Instruction* current = block->next();
-
-    Instruction* last = block->last_instruction();
-    if (!last->IsParallelMove()) last = last->next();
-
-    while (current != last) {
-      current->set_lifetime_position(pos);
-      current = current->next();
-      pos += 2;
+    // We do not assign an instruction number to the block entry.

[Kevin Millikin (Google), 2012/07/16 13:49:18]

Ooops, this comment described the situation before.  I've changed it to be
numbered with the block's start position so I'll scrap the comment.

+    for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+      Instruction* current = it.Current();
+      // Do not assign numbers to parallel moves or goto instructions.
+      if (!current->IsParallelMove() && !current->IsGoto()) {
+        current->set_lifetime_position(pos);
+        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();
+    JoinEntryInstr* join = block->AsJoinEntry();
+    if ((join != NULL) && (join->phi_count() > 0)) {
+      const intptr_t phi_count = join->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());
+        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