VM: Support phis with pair representations.

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 93d964ab067b2c6f308936cd0e09b5e4cad57c55..17b7cc2f2a48c1506f2091d167562cc2bb81193d 100644
--- a/runtime/vm/flow_graph_allocator.cc
+++ b/runtime/vm/flow_graph_allocator.cc
@@ -222,11 +222,14 @@ void SSALivenessAnalysis::ComputeInitialSets() {
     if (block->IsJoinEntry()) {
       JoinEntryInstr* join = block->AsJoinEntry();
       for (PhiIterator it(join); !it.Done(); it.Advance()) {
-        // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation.
         PhiInstr* phi = it.Current();
         ASSERT(phi != NULL);
         kill->Add(phi->ssa_temp_index());
         live_in->Remove(phi->ssa_temp_index());
+        if (phi->HasPairRepresentation()) {
+          kill->Add(ToSecondPairVreg(phi->ssa_temp_index()));
+          live_in->Remove(ToSecondPairVreg(phi->ssa_temp_index()));
+        }
 
         // If a phi input is not defined by the corresponding predecessor it
         // must be marked live-in for that predecessor.
@@ -774,20 +777,18 @@ Instruction* FlowGraphAllocator::ConnectOutgoingPhiMoves(
 
   // Search for the index of the current block in the predecessors of
   // the join.
-  const intptr_t pred_idx = join->IndexOfPredecessor(block);
+  const intptr_t pred_index = join->IndexOfPredecessor(block);
 
   // Record the corresponding phi input use for each phi.
-  intptr_t move_idx = 0;
+  intptr_t move_index = 0;
   for (PhiIterator it(join); !it.Done(); it.Advance()) {
-    // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation.
     PhiInstr* phi = it.Current();
-    Value* val = phi->InputAt(pred_idx);
-    MoveOperands* move = parallel_move->MoveOperandsAt(move_idx);
+    Value* val = phi->InputAt(pred_index);
+    MoveOperands* move = parallel_move->MoveOperandsAt(move_index++);
 
     ConstantInstr* constant = val->definition()->AsConstant();
     if (constant != NULL) {
       move->set_src(Location::Constant(constant));
-      move_idx++;
       continue;
     }
 
@@ -796,8 +797,7 @@ Instruction* FlowGraphAllocator::ConnectOutgoingPhiMoves(
     //                 g  g'
     //      value    --*
     //
-
-    const intptr_t vreg = val->definition()->ssa_temp_index();
+    intptr_t vreg = val->definition()->ssa_temp_index();
     LiveRange* range = GetLiveRange(vreg);
     if (interfere_at_backedge != NULL) interfere_at_backedge->Add(vreg);
 
@@ -806,9 +806,23 @@ Instruction* FlowGraphAllocator::ConnectOutgoingPhiMoves(
         pos,
         move->src_slot(),
         GetLiveRange(phi->ssa_temp_index())->assigned_location_slot());
-
     move->set_src(Location::PrefersRegister());
-    move_idx++;
+
+    if (val->definition()->HasPairRepresentation()) {
+      move = parallel_move->MoveOperandsAt(move_index++);
+      vreg = ToSecondPairVreg(vreg);
+      range = GetLiveRange(vreg);

[Cutch, 2015/10/01 17:27:41]

This code is the same as the first vreg code. Could this be factored into a
helper that takes the vreg?

[Florian Schneider, 2015/10/01 18:27:38]

It would need to take vreg, block, interfere_at_backedge, pos, move, phi as
parameters...

I'm not sure it's worth a helper yet.

+      if (interfere_at_backedge != NULL) {
+        interfere_at_backedge->Add(vreg);
+      }
+      range->AddUseInterval(block->start_pos(), pos);
+      range->AddHintedUse(
+          pos,
+          move->src_slot(),
+          GetLiveRange(ToSecondPairVreg(
+              phi->ssa_temp_index()))->assigned_location_slot());
+      move->set_src(Location::PrefersRegister());
+    }
   }
 
   // Begin backward iteration with the instruction before the parallel
@@ -826,11 +840,11 @@ void FlowGraphAllocator::ConnectIncomingPhiMoves(JoinEntryInstr* join) {
   const bool is_loop_header = BlockInfoAt(join->start_pos())->is_loop_header();
   intptr_t move_idx = 0;
   for (PhiIterator it(join); !it.Done(); it.Advance()) {
-    // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation.
     PhiInstr* phi = it.Current();
     ASSERT(phi != NULL);
     const intptr_t vreg = phi->ssa_temp_index();
     ASSERT(vreg >= 0);
+    bool is_pair_phi = phi->HasPairRepresentation();

[Cutch, 2015/10/01 17:27:41]

const bool....

[Florian Schneider, 2015/10/01 18:27:39]

Done.

 
     // Expected shape of live range:
     //
@@ -839,9 +853,14 @@ void FlowGraphAllocator::ConnectIncomingPhiMoves(JoinEntryInstr* join) {
     //
     LiveRange* range = GetLiveRange(vreg);
     range->DefineAt(pos);  // Shorten live range.
-
     if (is_loop_header) range->mark_loop_phi();
 
+    if (is_pair_phi) {
+      LiveRange* range = GetLiveRange(ToSecondPairVreg(vreg));

[Cutch, 2015/10/01 17:27:41]

Could you rename range here, it is confusing that you introduce a new "range" in
an inner scope that shadows the outer scope.

[Florian Schneider, 2015/10/01 18:27:38]

Otoh, it prevents from accidentally using the outer range here where is would be
wrong.

I can rename it.

+      range->DefineAt(pos);  // Shorten live range.
+      if (is_loop_header) range->mark_loop_phi();
+    }
+
     for (intptr_t pred_idx = 0; pred_idx < phi->InputCount(); pred_idx++) {
       BlockEntryInstr* pred = join->PredecessorAt(pred_idx);
       GotoInstr* goto_instr = pred->last_instruction()->AsGoto();
@@ -850,15 +869,26 @@ void FlowGraphAllocator::ConnectIncomingPhiMoves(JoinEntryInstr* join) {
           goto_instr->parallel_move()->MoveOperandsAt(move_idx);
       move->set_dest(Location::PrefersRegister());
       range->AddUse(pos, move->dest_slot());
+      if (is_pair_phi) {
+        LiveRange* range = GetLiveRange(ToSecondPairVreg(vreg));
+        MoveOperands* move =
+            goto_instr->parallel_move()->MoveOperandsAt(move_idx + 1);

[Cutch, 2015/10/01 17:27:41]

More duplicate code- how difficult would be to factor this into a helper and
call with both vregs?

[Florian Schneider, 2015/10/01 18:27:38]

Same as above... I think 2 common lines don't seem to be enough yet.

+        move->set_dest(Location::PrefersRegister());
+        range->AddUse(pos, move->dest_slot());
+      }
     }
 
     // All phi resolution moves are connected. Phi's live range is
     // complete.
     AssignSafepoints(phi, range);
-
     CompleteRange(range, RegisterKindForResult(phi));
+    if (is_pair_phi) {
+      LiveRange* range = GetLiveRange(ToSecondPairVreg(vreg));

[Cutch, 2015/10/01 17:27:41]

This shadow of range confused me.

[Florian Schneider, 2015/10/01 18:27:38]

I can rename it.

+      AssignSafepoints(phi, range);
+      CompleteRange(range, RegisterKindForResult(phi));
+    }
 
-    move_idx++;
+    move_idx += is_pair_phi ? 2 : 1;
   }
 }
 
@@ -1499,10 +1529,11 @@ void FlowGraphAllocator::NumberInstructions() {
     // For join entry predecessors create phi resolution moves if
     // necessary. They will be populated by the register allocator.
     JoinEntryInstr* join = block->AsJoinEntry();
-    if ((join != NULL) &&
-        (join->phis() != NULL) &&
-        !join->phis()->is_empty()) {
-      const intptr_t phi_count = join->phis()->length();
+    if (join != NULL) {
+      intptr_t move_count = 0;
+      for (PhiIterator it(join); !it.Done(); it.Advance()) {
+        move_count += it.Current()->HasPairRepresentation() ? 2 : 1;
+      }
       for (intptr_t i = 0; i < block->PredecessorCount(); i++) {
         // Insert the move between the last two instructions of the
         // predecessor block (all such blocks have at least two instructions:
@@ -1513,7 +1544,7 @@ void FlowGraphAllocator::NumberInstructions() {
         ParallelMoveInstr* move = last->AsGoto()->GetParallelMove();
 
         // Populate the ParallelMove with empty moves.
-        for (intptr_t j = 0; j < phi_count; j++) {
+        for (intptr_t j = 0; j < move_count; j++) {
           move->AddMove(Location::NoLocation(), Location::NoLocation());
         }
       }
@@ -2023,7 +2054,6 @@ intptr_t FlowGraphAllocator::FirstIntersectionWithAllocated(
 
 
 void ReachingDefs::AddPhi(PhiInstr* phi) {
-  // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation.
   if (phi->reaching_defs() == NULL) {
     Zone* zone = flow_graph_.zone();
     phi->set_reaching_defs(new(zone) BitVector(
@@ -2037,6 +2067,9 @@ void ReachingDefs::AddPhi(PhiInstr* phi) {
         depends_on_phi = true;
       }
       phi->reaching_defs()->Add(input->ssa_temp_index());
+      if (phi->HasPairRepresentation()) {
+        phi->reaching_defs()->Add(ToSecondPairVreg(input->ssa_temp_index()));
+      }
     }
 
     // If this phi depends on another phi then we need fix point iteration.
@@ -2048,7 +2081,6 @@ void ReachingDefs::AddPhi(PhiInstr* phi) {
 void ReachingDefs::Compute() {
   // Transitively collect all phis that are used by the given phi.
   for (intptr_t i = 0; i < phis_.length(); i++) {
-    // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation.
     PhiInstr* phi = phis_[i];
 
     // Add all phis that affect this phi to the list.
@@ -2153,18 +2185,26 @@ bool FlowGraphAllocator::AllocateFreeRegister(LiveRange* unallocated) {
     for (PhiIterator it(loop_header->entry()->AsJoinEntry());
          !it.Done();
          it.Advance()) {
-      // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation.
       PhiInstr* phi = it.Current();
       ASSERT(phi->is_alive());
-      const intptr_t phi_vreg = phi->ssa_temp_index();
+      intptr_t phi_vreg = phi->ssa_temp_index();
       LiveRange* range = GetLiveRange(phi_vreg);
       if (range->assigned_location().kind() == register_kind_) {
         const intptr_t reg = range->assigned_location().register_code();
-
         if (!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) {
           used_on_backedge[reg] = true;
         }
       }
+      if (phi->HasPairRepresentation()) {
+        phi_vreg = ToSecondPairVreg(phi_vreg);
+        range = GetLiveRange(phi_vreg);
+        if (range->assigned_location().kind() == register_kind_) {
+          const intptr_t reg = range->assigned_location().register_code();
+          if (!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) {

[Cutch, 2015/10/01 17:27:41]

Factor into another helper routine?

[Florian Schneider, 2015/10/01 18:27:38]

Renamed locals like above.

+            used_on_backedge[reg] = true;
+          }
+        }
+      }
     }
 
     if (used_on_backedge[candidate]) {
@@ -2877,11 +2917,12 @@ void FlowGraphAllocator::CollectRepresentations() {
     if (block->IsJoinEntry()) {
       JoinEntryInstr* join = block->AsJoinEntry();
       for (PhiIterator it(join); !it.Done(); it.Advance()) {
-        // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation.
         PhiInstr* phi = it.Current();
-        if ((phi != NULL) && (phi->ssa_temp_index() >= 0)) {
-          ASSERT(!phi->HasPairRepresentation());
-          value_representations_[phi->ssa_temp_index()] =
+        ASSERT(phi != NULL && phi->ssa_temp_index() >= 0);
+        value_representations_[phi->ssa_temp_index()] =
+            RepresentationForRange(phi->representation());
+        if (phi->HasPairRepresentation()) {
+          value_representations_[ToSecondPairVreg(phi->ssa_temp_index())] =
               RepresentationForRange(phi->representation());
         }
       }