VM: Support phis with pair representations.

runtime/vm/flow_graph_allocator.cc

 // Copyright (c) 2013, 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.h"
@@ skipping 204 matching lines @@
             }
           }
         }
       }
     }
 
     // Handle phis.
     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.
         for (intptr_t k = 0; k < phi->InputCount(); k++) {
           Value* val = phi->InputAt(k);
           if (val->BindsToConstant()) continue;
 
           BlockEntryInstr* pred = block->PredecessorAt(k);
           const intptr_t use = val->definition()->ssa_temp_index();
           if (!kill_[pred->postorder_number()]->Contains(use)) {
@@ skipping 527 matching lines @@
   ParallelMoveInstr* parallel_move = goto_instr->parallel_move();
 
   // All uses are recorded at the position of parallel move preceding goto.
   const intptr_t pos = goto_instr->lifetime_position();
 
   JoinEntryInstr* join = goto_instr->successor();
   ASSERT(join != NULL);
 
   // 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;
     }
 
     // Expected shape of live ranges:
     //
     //                 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);
 
     range->AddUseInterval(block->start_pos(), pos);
     range->AddHintedUse(
         pos,
         move->src_slot(),
         GetLiveRange(phi->ssa_temp_index())->assigned_location_slot());
+    move->set_src(Location::PrefersRegister());
 
-    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
   // move.
   return goto_instr->previous();
 }
 
 
 void FlowGraphAllocator::ConnectIncomingPhiMoves(JoinEntryInstr* join) {
   // For join blocks we need to add destinations of phi resolution moves
   // to phi's live range so that register allocator will fill them with moves.
 
   // All uses are recorded at the start position in the block.
   const intptr_t pos = join->start_pos();
   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:
     //
     //                 B
     //      phi        [--------
     //
     LiveRange* range = GetLiveRange(vreg);
     range->DefineAt(pos);  // Shorten live range.
+    if (is_loop_header) range->mark_loop_phi();
 
-    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();
       ASSERT((goto_instr != NULL) && (goto_instr->HasParallelMove()));
       MoveOperands* move =
           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));
+    }
 
-    CompleteRange(range, RegisterKindForResult(phi));
-
-    move_idx++;
+    move_idx += is_pair_phi ? 2 : 1;
   }
 }
 
 
 void FlowGraphAllocator::ProcessEnvironmentUses(BlockEntryInstr* block,
                                                 Instruction* current) {
   ASSERT(current->env() != NULL);
   Environment* env = current->env();
   while (env != NULL) {
     // Any value mentioned in the deoptimization environment should survive
@@ skipping 620 matching lines @@
   }
 
   // Create parallel moves in join predecessors.  This must be done after
   // all instructions are numbered.
   for (intptr_t i = block_count - 1; i >= 0; i--) {
     BlockEntryInstr* block = postorder_[i];
 
     // 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:
         // the block entry and goto instructions.)
         Instruction* last = block->PredecessorAt(i)->last_instruction();
         ASSERT(last->IsGoto());
 
         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());
         }
       }
     }
   }
 }
 
 
 // Discover structural (reducible) loops nesting structure.
 void FlowGraphAllocator::DiscoverLoops() {
@@ skipping 489 matching lines @@
     const intptr_t pos = FirstIntersection(
         unallocated->finger()->first_pending_use_interval(),
         allocated_head);
     if (pos < intersection) intersection = pos;
   }
   return intersection;
 }
 
 
 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(
         zone, flow_graph_.max_virtual_register_number()));
 
     // Compute initial set reaching defs set.
     bool depends_on_phi = false;
     for (intptr_t i = 0; i < phi->InputCount(); i++) {
       Definition* input = phi->InputAt(i)->definition();
       if (input->IsPhi()) {
         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.
     if (depends_on_phi) phis_.Add(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.
     for (intptr_t i = 0; i < phi->InputCount(); i++) {
       PhiInstr* input_phi = phi->InputAt(i)->definition()->AsPhi();
       if (input_phi != NULL) {
         AddPhi(input_phi);
       }
     }
   }
@@ skipping 84 matching lines @@
       (free_until >= loop_header->last_block()->end_pos()) &&
       loop_header->backedge_interference()->Contains(unallocated->vreg())) {
     GrowableArray<bool> used_on_backedge(number_of_registers_);
     for (intptr_t i = 0; i < number_of_registers_; i++) {
       used_on_backedge.Add(false);
     }
 
     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]) {
       TRACE_ALLOC(THR_Print(
           "considering %s for v%" Pd ": has interference on the back edge"
           " {loop [%" Pd ", %" Pd ")}\n",
           MakeRegisterLocation(candidate).Name(),
           unallocated->vreg(),
           loop_header->entry()->start_pos(),
           loop_header->last_block()->end_pos()));
@@ skipping 692 matching lines @@
         Definition* def = (*catch_entry->initial_definitions())[i];
         ASSERT(!def->HasPairRepresentation());
         value_representations_[def->ssa_temp_index()] =
             RepresentationForRange(def->representation());
       }
     }
     // Phis.
     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());
         }
       }
     }
     // Normal instructions.
     for (ForwardInstructionIterator instr_it(block);
          !instr_it.Done();
          instr_it.Advance()) {
       Definition* def = instr_it.Current()->AsDefinition();
       if ((def != NULL) && (def->ssa_temp_index() >= 0)) {
@@ skipping 76 matching lines @@
     THR_Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(flow_graph_, true);
     printer.PrintBlocks();
     THR_Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart