Support for multiple register values

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 16 matching lines @@
   } while (0)
 #else
 #define TRACE_ALLOC(statement)
 #endif
 
 
 static const intptr_t kNoVirtualRegister = -1;
 static const intptr_t kTempVirtualRegister = -2;
 static const intptr_t kIllegalPosition = -1;
 static const intptr_t kMaxPosition = 0x7FFFFFFF;
+static const intptr_t kPairVirtualRegisterOffset = 1;
+
+// Definitions which have pair representations
+// (kPairOfTagged or kPairOfUnboxedDouble) use two virtual register names.
+// At SSA index allocation time each definition reserves two SSA indexes,
+// the second index is only used for pairs. This function maps from the first
+// SSA index to the second.
+static intptr_t ToSecondPairVreg(intptr_t vreg) {
+  // Map vreg to its pair vreg.
+  return vreg + kPairVirtualRegisterOffset;
+}
+
 
 static intptr_t MinPosition(intptr_t a, intptr_t b) {
   return (a < b) ? a : b;
 }
 
 
 static bool IsInstructionStartPosition(intptr_t pos) {
   return (pos & 1) == 0;
 }
 
@@ skipping 20 matching lines @@
     block_order_(flow_graph.reverse_postorder()),
     postorder_(flow_graph.postorder()),
     liveness_(flow_graph),
     vreg_count_(flow_graph.max_virtual_register_number()),
     live_ranges_(flow_graph.max_virtual_register_number()),
     cpu_regs_(),
     fpu_regs_(),
     blocked_cpu_registers_(),
     blocked_fpu_registers_(),
     cpu_spill_slot_count_(0) {
-  for (intptr_t i = 0; i < vreg_count_; i++) live_ranges_.Add(NULL);
+  for (intptr_t i = 0; i < vreg_count_; i++) {
+    live_ranges_.Add(NULL);
+  }
   for (intptr_t i = 0; i < vreg_count_; i++) {
     value_representations_.Add(kNoRepresentation);
   }
 
   // All registers are marked as "not blocked" (array initialized to false).
   // Mark the unavailable ones as "blocked" (true).
   for (intptr_t i = 0; i < kFirstFreeCpuRegister; i++) {
     blocked_cpu_registers_[i] = true;
   }
   for (intptr_t i = kLastFreeCpuRegister + 1; i < kNumberOfCpuRegisters; i++) {
@@ skipping 19 matching lines @@
   for (intptr_t i = 0; i < block_count; i++) {
     BlockEntryInstr* block = postorder_[i];
 
     BitVector* kill = kill_[i];
     BitVector* live_in = live_in_[i];
 
     // Iterate backwards starting at the last instruction.
     for (BackwardInstructionIterator it(block); !it.Done(); it.Advance()) {
       Instruction* current = it.Current();
 
+      // Initialize location summary for instruction.
+      current->InitializeLocationSummary(true);  // Optimizing.
+      LocationSummary* locs = current->locs();
+
       // Handle definitions.
       Definition* current_def = current->AsDefinition();
       if ((current_def != NULL) && current_def->HasSSATemp()) {
         kill->Add(current_def->ssa_temp_index());
         live_in->Remove(current_def->ssa_temp_index());
+        if (current_def->HasPairRepresentation()) {
+          kill->Add(ToSecondPairVreg(current_def->ssa_temp_index()));
+          live_in->Remove(ToSecondPairVreg(current_def->ssa_temp_index()));
+        }
       }
 
       // Handle uses.
-      current->InitializeLocationSummary(true);  // Optimizing.
-      LocationSummary* locs = current->locs();
       ASSERT(locs->input_count() == current->InputCount());
       for (intptr_t j = 0; j < current->InputCount(); j++) {
         Value* input = current->InputAt(j);
-        const intptr_t use = input->definition()->ssa_temp_index();
 
         ASSERT(!locs->in(j).IsConstant() || input->BindsToConstant());
         if (locs->in(j).IsConstant()) continue;
 
-        live_in->Add(use);
+        live_in->Add(input->definition()->ssa_temp_index());
+        if (input->definition()->HasPairRepresentation()) {
+          live_in->Add(ToSecondPairVreg(input->definition()->ssa_temp_index()));
+        }
       }
 
       // Add non-argument uses from the deoptimization environment (pushed
       // arguments are not allocated by the register allocator).
       if (current->env() != NULL) {
         for (Environment::DeepIterator env_it(current->env());
              !env_it.Done();
              env_it.Advance()) {
           Definition* defn = env_it.CurrentValue()->definition();
           if (defn->IsMaterializeObject()) {
             // MaterializeObject instruction is not in the graph.
             // Treat its inputs as part of the environment.
             for (intptr_t i = 0; i < defn->InputCount(); i++) {
               if (!defn->InputAt(i)->BindsToConstant()) {
-                live_in->Add(defn->InputAt(i)->definition()->ssa_temp_index());
+                intptr_t idx = defn->InputAt(i)->definition()->ssa_temp_index();
+                live_in->Add(idx);
               }
             }
           } else if (!defn->IsPushArgument() && !defn->IsConstant()) {
             live_in->Add(defn->ssa_temp_index());
+            if (defn->HasPairRepresentation()) {
+              live_in->Add(ToSecondPairVreg(defn->ssa_temp_index()));
+            }
           }
         }
       }
     }
 
     // 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 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)) {
             live_in_[pred->postorder_number()]->Add(use);
           }
         }
       }
     } else if (block->IsCatchBlockEntry()) {
       // Process initial definitions.
       CatchBlockEntryInstr* catch_entry = block->AsCatchBlockEntry();
       for (intptr_t i = 0;
            i < catch_entry->initial_definitions()->length();
            i++) {
-        intptr_t vreg =
-            (*catch_entry->initial_definitions())[i]->ssa_temp_index();
+        Definition* def = (*catch_entry->initial_definitions())[i];
+        const intptr_t vreg = def->ssa_temp_index();
         kill_[catch_entry->postorder_number()]->Add(vreg);
         live_in_[catch_entry->postorder_number()]->Remove(vreg);
       }
     }
   }
 
   // Process initial definitions, ie, constants and incoming parameters.
   for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); i++) {
-    intptr_t vreg = (*graph_entry_->initial_definitions())[i]->ssa_temp_index();
+    Definition* def = (*graph_entry_->initial_definitions())[i];
+    const intptr_t vreg = def->ssa_temp_index();
     kill_[graph_entry_->postorder_number()]->Add(vreg);
     live_in_[graph_entry_->postorder_number()]->Remove(vreg);
   }
 
   // Update initial live_in sets to match live_out sets. Has to be
   // done in a separate path because of backwards branches.
   for (intptr_t i = 0; i < block_count; i++) {
     UpdateLiveIn(*postorder_[i]);
   }
 }
@@ skipping 391 matching lines @@
     return Location::kRegister;
   }
 }
 
 
 static Location::Kind RegisterKindForResult(Instruction* instr) {
   if ((instr->representation() == kUnboxedDouble) ||
       (instr->representation() == kUnboxedMint) ||
       (instr->representation() == kUnboxedFloat32x4) ||
       (instr->representation() == kUnboxedInt32x4) ||
-      (instr->representation() == kUnboxedFloat64x2)) {
+      (instr->representation() == kUnboxedFloat64x2) ||
+      (instr->representation() == kPairOfUnboxedDouble)) {
     return Location::kFpuRegister;
   } else {
     return Location::kRegister;
   }
 }
 
 
 //
 // When describing shape of live ranges in comments below we are going to use
 // the following notation:
@@ skipping 38 matching lines @@
   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);
 
   // Record the corresponding phi input use for each phi.
   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();
     Value* val = phi->InputAt(pred_idx);
     MoveOperands* move = parallel_move->MoveOperandsAt(move_idx);
 
     ConstantInstr* constant = val->definition()->AsConstant();
     if (constant != NULL) {
       move->set_src(Location::Constant(constant->value()));
       move_idx++;
       continue;
     }
@@ skipping 23 matching lines @@
 
 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);
 
     // Expected shape of live range:
     //
     //                 B
     //      phi        [--------
     //
@@ skipping 67 matching lines @@
       MaterializeObjectInstr* mat = def->AsMaterializeObject();
       if (mat != NULL) {
         // MaterializeObject itself produces no value. But its uses
         // are treated as part of the environment: allocated locations
         // will be used when building deoptimization data.
         locations[i] = Location::NoLocation();
         ProcessMaterializationUses(block, block_start_pos, use_pos, mat);
         continue;
       }
 
-      const intptr_t vreg = def->ssa_temp_index();
-      LiveRange* range = GetLiveRange(vreg);
+      LiveRange* range = GetLiveRange(def->ssa_temp_index());
       range->AddUseInterval(block_start_pos, use_pos);
       range->AddUse(use_pos, &locations[i]);
+
+      if (def->HasPairRepresentation()) {
+        LiveRange* range =
+            GetLiveRange(ToSecondPairVreg(def->ssa_temp_index()));
+        range->AddUseInterval(block_start_pos, use_pos);
+        range->AddUse(use_pos, &locations[i]);
+      }
     }
 
     env->set_locations(locations);
     env = env->outer();
   }
 }
 
 
 void FlowGraphAllocator::ProcessMaterializationUses(
     BlockEntryInstr* block,
@@ skipping 14 matching lines @@
     Definition* def = mat->InputAt(i)->definition();
 
     ConstantInstr* constant = def->AsConstant();
     if (constant != NULL) {
       locations[i] = Location::Constant(constant->value());
       continue;
     }
 
     locations[i] = Location::Any();
 
-    const intptr_t vreg = def->ssa_temp_index();
-    LiveRange* range = GetLiveRange(vreg);
+    LiveRange* range = GetLiveRange(def->ssa_temp_index());
     range->AddUseInterval(block_start_pos, use_pos);
     range->AddUse(use_pos, &locations[i]);
+    if (def->HasPairRepresentation()) {
+      LiveRange* range = GetLiveRange(ToSecondPairVreg(def->ssa_temp_index()));
+      range->AddUseInterval(block_start_pos, use_pos);
+      range->AddUse(use_pos, &locations[i]);
+    }
   }
 
   mat->set_locations(locations);
 }
 
 
+void FlowGraphAllocator::ProcessOneInput(BlockEntryInstr* block,
+                                         intptr_t pos,
+                                         Location* in_ref,
+                                         Value* input,
+                                         intptr_t vreg) {
+  ASSERT(in_ref != NULL);
+  ASSERT(!in_ref->IsPairLocation());
+  ASSERT(input != NULL);
+  ASSERT(block != NULL);
+  LiveRange* range = GetLiveRange(vreg);
+  if (in_ref->IsMachineRegister()) {
+    // Input is expected in a fixed register. Expected shape of
+    // live ranges:
+    //
+    //                 j' i  i'
+    //      value    --*
+    //      register   [-----)
+    //
+    MoveOperands* move =
+        AddMoveAt(pos - 1, *in_ref, Location::Any());
+    BlockLocation(*in_ref, pos - 1, pos + 1);
+    range->AddUseInterval(block->start_pos(), pos - 1);
+    range->AddHintedUse(pos - 1, move->src_slot(), in_ref);
+  } else if (in_ref->IsUnallocated()) {
+    if (in_ref->policy() == Location::kWritableRegister) {
+      // Writable unallocated input. Expected shape of
+      // live ranges:
+      //
+      //                 j' i  i'
+      //      value    --*
+      //      temp       [------)
+      MoveOperands* move = AddMoveAt(pos - 1,
+                                     Location::RequiresRegister(),
+                                     Location::PrefersRegister());
+
+      // Add uses to the live range of the input.
+      range->AddUseInterval(block->start_pos(), pos - 1);
+      range->AddUse(pos - 1, move->src_slot());
+
+      // Create live range for the temporary.
+      LiveRange* temp = MakeLiveRangeForTemporary();
+      temp->AddUseInterval(pos - 1, pos + 1);
+      temp->AddHintedUse(pos - 1, in_ref, move->src_slot());
+      temp->AddUse(pos + 1, move->dest_slot());
+      *in_ref = Location::RequiresRegister();
+      CompleteRange(temp, RegisterKindFromPolicy(*in_ref));
+    } else {
+      // Normal unallocated input. Expected shape of
+      // live ranges:
+      //
+      //                 i  i'
+      //      value    -----*
+      //
+      range->AddUseInterval(block->start_pos(), pos + 1);
+      range->AddUse(pos + 1, in_ref);
+    }
+  } else {
+    ASSERT(in_ref->IsConstant());
+  }
+}
+
+
+void FlowGraphAllocator::ProcessOneOutput(BlockEntryInstr* block,
+                                          Instruction* current,
+                                          intptr_t pos,
+                                          Location* out,
+                                          Definition* def,
+                                          intptr_t vreg,
+                                          bool output_same_as_first_input,
+                                          Location* in_ref,
+                                          Definition* input,
+                                          intptr_t input_vreg,
+                                          BitVector* interference_set) {
+  ASSERT(out != NULL);
+  ASSERT(!out->IsPairLocation());
+  ASSERT(def != NULL);
+  ASSERT(block != NULL);
+
+  LiveRange* range = vreg >= 0 ?
+      GetLiveRange(vreg) : MakeLiveRangeForTemporary();
+
+  // Process output and finalize its liverange.
+  if (out->IsMachineRegister()) {
+    // Fixed output location. Expected shape of live range:
+    //
+    //                    i  i' j  j'
+    //    register        [--)
+    //    output             [-------
+    //
+    BlockLocation(*out, pos, pos + 1);
+
+    if (range->vreg() == kTempVirtualRegister) return;
+
+    // We need to emit move connecting fixed register with another location
+    // that will be allocated for this output's live range.
+    // Special case: fixed output followed by a fixed input last use.
+    UsePosition* use = range->first_use();
+
+    // If the value has no uses we don't need to allocate it.
+    if (use == NULL) return;
+
+    if (use->pos() == (pos + 1)) {
+      ASSERT(use->location_slot()->IsUnallocated());
+      *(use->location_slot()) = *out;
+
+      // Remove first use. It was allocated.
+      range->set_first_use(range->first_use()->next());
+    }
+
+    // Shorten live range to the point of definition, this might make the range
+    // empty (if the only use immediately follows). If range is not empty add
+    // move from a fixed register to an unallocated location.
+    range->DefineAt(pos + 1);
+    if (range->Start() == range->End()) return;
+
+    MoveOperands* move = AddMoveAt(pos + 1, Location::Any(), *out);
+    range->AddHintedUse(pos + 1, move->dest_slot(), out);
+  } else if (output_same_as_first_input) {
+    ASSERT(in_ref != NULL);
+    ASSERT(input != NULL);
+    // Output register will contain a value of the first input at instruction's
+    // start. Expected shape of live ranges:
+    //
+    //                 i  i'
+    //    input #0   --*
+    //    output       [----
+    //
+    ASSERT(in_ref->Equals(Location::RequiresRegister()) ||
+           in_ref->Equals(Location::RequiresFpuRegister()));
+
+    // TODO(johnmccutchan): Without this I get allocated a register instead
+    // of an FPU register. Figure out why.
+
+    *out = *in_ref;
+    // Create move that will copy value between input and output.
+    MoveOperands* move = AddMoveAt(pos,
+                                   Location::RequiresRegister(),
+                                   Location::Any());
+
+    // Add uses to the live range of the input.
+    LiveRange* input_range = GetLiveRange(input_vreg);
+    input_range->AddUseInterval(block->start_pos(), pos);
+    input_range->AddUse(pos, move->src_slot());
+
+    // Shorten output live range to the point of definition and add both input
+    // and output uses slots to be filled by allocator.
+    range->DefineAt(pos);
+    range->AddHintedUse(pos, out, move->src_slot());
+    range->AddUse(pos, move->dest_slot());
+    range->AddUse(pos, in_ref);
+
+    if ((interference_set != NULL) &&
+        (range->vreg() >= 0) &&
+        interference_set->Contains(range->vreg())) {
+      interference_set->Add(input->ssa_temp_index());
+    }
+  } else {
+    // Normal unallocated location that requires a register. Expected shape of
+    // live range:
+    //
+    //                    i  i'
+    //    output          [-------
+    //
+    ASSERT(out->Equals(Location::RequiresRegister()) ||
+           out->Equals(Location::RequiresFpuRegister()));
+
+    // Shorten live range to the point of definition and add use to be filled by
+    // allocator.
+    range->DefineAt(pos);
+    range->AddUse(pos, out);
+  }
+
+  AssignSafepoints(range);
+  CompleteRange(range, RegisterKindForResult(current));
+}
+
+
 // Create and update live ranges corresponding to instruction's inputs,
 // temporaries and output.
 void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block,
                                                Instruction* current,
                                                BitVector* interference_set) {
   LocationSummary* locs = current->locs();
 
   Definition* def = current->AsDefinition();
   if ((def != NULL) && (def->AsConstant() != NULL)) {
+    ASSERT(!def->HasPairRepresentation());
     LiveRange* range = (def->ssa_temp_index() != -1) ?
         GetLiveRange(def->ssa_temp_index()) : NULL;
 
     // Drop definitions of constants that have no uses.
     if ((range == NULL) || (range->first_use() == NULL)) {
       locs->set_out(0, Location::NoLocation());
       return;
     }
 
     // If this constant has only unconstrained uses convert them all
     // to use the constant directly and drop this definition.
     // TODO(vegorov): improve allocation when we have enough registers to keep
     // constants used in the loop in them.
     if (HasOnlyUnconstrainedUses(range)) {
       const Object& value = def->AsConstant()->value();
       range->set_assigned_location(Location::Constant(value));
       range->set_spill_slot(Location::Constant(value));
       range->finger()->Initialize(range);
       ConvertAllUses(range);
 
       locs->set_out(0, Location::NoLocation());
       return;
     }
   }
 
   const intptr_t pos = current->lifetime_position();
   ASSERT(IsInstructionStartPosition(pos));
 
-  // Number of input locations and number of input operands have to agree.
   ASSERT(locs->input_count() == current->InputCount());
 
   // Normalize same-as-first-input output if input is specified as
   // fixed register.
   if (locs->out(0).IsUnallocated() &&
       (locs->out(0).policy() == Location::kSameAsFirstInput) &&
       (locs->in(0).IsMachineRegister())) {
     locs->set_out(0, locs->in(0));
   }
 
   const bool output_same_as_first_input =
       locs->out(0).IsUnallocated() &&
       (locs->out(0).policy() == Location::kSameAsFirstInput);
 
   // Add uses from the deoptimization environment.
   if (current->env() != NULL) ProcessEnvironmentUses(block, current);
 
   // Process inputs.
   // Skip the first input if output is specified with kSameAsFirstInput policy,
   // they will be processed together at the very end.
-  for (intptr_t j = output_same_as_first_input ? 1 : 0;
-       j < current->InputCount();
-       j++) {
-    Value* input = current->InputAt(j);
-    const intptr_t vreg = input->definition()->ssa_temp_index();
-    LiveRange* range = GetLiveRange(vreg);
-
-    Location* in_ref = locs->in_slot(j);
-
-    if (in_ref->IsMachineRegister()) {
-      // Input is expected in a fixed register. Expected shape of
-      // live ranges:
-      //
-      //                 j' i  i'
-      //      value    --*
-      //      register   [-----)
-      //
-      MoveOperands* move =
-          AddMoveAt(pos - 1, *in_ref, Location::Any());
-      BlockLocation(*in_ref, pos - 1, pos + 1);
-      range->AddUseInterval(block->start_pos(), pos - 1);
-      range->AddHintedUse(pos - 1, move->src_slot(), in_ref);
-    } else if (in_ref->IsUnallocated()) {
-      if (in_ref->policy() == Location::kWritableRegister) {
-        // Writable unallocated input. Expected shape of
-        // live ranges:
-        //
-        //                 i  i'
-        //      value    --*
-        //      temp       [--)
-        MoveOperands* move = AddMoveAt(pos,
-                                       Location::RequiresRegister(),
-                                       Location::PrefersRegister());
-
-        // Add uses to the live range of the input.
-        range->AddUseInterval(block->start_pos(), pos);
-        range->AddUse(pos, move->src_slot());
-
-        // Create live range for the temporary.
-        LiveRange* temp = MakeLiveRangeForTemporary();
-        temp->AddUseInterval(pos, pos + 1);
-        temp->AddHintedUse(pos, in_ref, move->src_slot());
-        temp->AddUse(pos, move->dest_slot());
-        *in_ref = Location::RequiresRegister();
-        CompleteRange(temp, RegisterKindFromPolicy(*in_ref));
+  {
+    for (intptr_t j = output_same_as_first_input ? 1 : 0;
+         j < locs->input_count();
+         j++) {
+      // Determine if we are dealing with a value pair, and if so, whether
+      // the location is the first register or second register.
+      Value* input = current->InputAt(j);
+      Location* in_ref = locs->in_slot(j);
+      if (in_ref->IsPairLocation()) {
+        ASSERT(input->definition()->HasPairRepresentation());
+        PairLocation* pair = in_ref->AsPairLocation();
+        const intptr_t vreg = input->definition()->ssa_temp_index();
+        // Each element of the pair is assigned it's own virtual register number
+        // and is allocated its own LiveRange.
+        ProcessOneInput(block, pos, pair->SlotAt(0),
+                        input, vreg);
+        ProcessOneInput(block, pos, pair->SlotAt(1), input,
+                        ToSecondPairVreg(vreg));
       } else {
-        // Normal unallocated input. Expected shape of
-        // live ranges:
-        //
-        //                 i  i'
-        //      value    -----*
-        //
-        range->AddUseInterval(block->start_pos(), pos + 1);
-        range->AddUse(pos + 1, in_ref);
+        ProcessOneInput(block, pos, in_ref, input,
+                        input->definition()->ssa_temp_index());
       }
-    } else {
-      ASSERT(in_ref->IsConstant());
     }
   }
 
   // Process temps.
   for (intptr_t j = 0; j < locs->temp_count(); j++) {
     // Expected shape of live range:
     //
     //              i  i'
     //              [--)
     //
 
     Location temp = locs->temp(j);
+    // We do not support pair locations for temporaries.
+    ASSERT(!temp.IsPairLocation());
     if (temp.IsMachineRegister()) {
       BlockLocation(temp, pos, pos + 1);
     } else if (temp.IsUnallocated()) {
       LiveRange* range = MakeLiveRangeForTemporary();
       range->AddUseInterval(pos, pos + 1);
       range->AddUse(pos, locs->temp_slot(j));
       CompleteRange(range, RegisterKindFromPolicy(temp));
     } else {
       UNREACHABLE();
     }
@@ skipping 19 matching lines @@
           pos,
           pos + 1);
     }
 
 
 #if defined(DEBUG)
     // Verify that temps, inputs and output were specified as fixed
     // locations.  Every register is blocked now so attempt to
     // allocate will not succeed.
     for (intptr_t j = 0; j < locs->temp_count(); j++) {
+      ASSERT(!locs->temp(j).IsPairLocation());
       ASSERT(!locs->temp(j).IsUnallocated());
     }
 
     for (intptr_t j = 0; j < locs->input_count(); j++) {
-      ASSERT(!locs->in(j).IsUnallocated());
+      if (locs->in(j).IsPairLocation()) {
+        PairLocation* pair = locs->in_slot(j)->AsPairLocation();
+        ASSERT(!pair->At(0).IsUnallocated());
+        ASSERT(!pair->At(1).IsUnallocated());
+      } else {
+        ASSERT(!locs->in(j).IsUnallocated());
+      }
     }
 
-    ASSERT(!locs->out(0).IsUnallocated());
+    if (locs->out(0).IsPairLocation()) {
+      PairLocation* pair = locs->out_slot(0)->AsPairLocation();
+      ASSERT(!pair->At(0).IsUnallocated());
+      ASSERT(!pair->At(1).IsUnallocated());
+    } else {
+      ASSERT(!locs->out(0).IsUnallocated());
+    }
 #endif
   }
 
   if (locs->can_call()) {
     safepoints_.Add(current);
   }
 
   if (def == NULL) {
     ASSERT(locs->out(0).IsInvalid());
     return;
   }
 
   if (locs->out(0).IsInvalid()) {
     ASSERT(def->ssa_temp_index() < 0);
     return;
   }
 
-  // We might have a definition without use.  We do not assign SSA index to
-  // such definitions.
-  LiveRange* range = (def->ssa_temp_index() >= 0) ?
-      GetLiveRange(def->ssa_temp_index()) :
-      MakeLiveRangeForTemporary();
+  ASSERT(locs->output_count() == 1);
   Location* out = locs->out_slot(0);
-
-  // Process output and finalize its liverange.
-  if (out->IsMachineRegister()) {
-    // Fixed output location. Expected shape of live range:
-    //
-    //                    i  i' j  j'
-    //    register        [--)
-    //    output             [-------
-    //
-    BlockLocation(*out, pos, pos + 1);
-
-    if (range->vreg() == kTempVirtualRegister) return;
-
-    // We need to emit move connecting fixed register with another location
-    // that will be allocated for this output's live range.
-    // Special case: fixed output followed by a fixed input last use.
-    UsePosition* use = range->first_use();
-
-    // If the value has no uses we don't need to allocate it.
-    if (use == NULL) return;
-
-    if (use->pos() == (pos + 1)) {
-      ASSERT(use->location_slot()->IsUnallocated());
-      *(use->location_slot()) = *out;
-
-      // Remove first use. It was allocated.
-      range->set_first_use(range->first_use()->next());
-    }
-
-    // Shorten live range to the point of definition, this might make the range
-    // empty (if the only use immediately follows). If range is not empty add
-    // move from a fixed register to an unallocated location.
-    range->DefineAt(pos + 1);
-    if (range->Start() == range->End()) return;
-
-    MoveOperands* move = AddMoveAt(pos + 1, Location::Any(), *out);
-    range->AddHintedUse(pos + 1, move->dest_slot(), out);
-  } else if (output_same_as_first_input) {
-    // Output register will contain a value of the first input at instruction's
-    // start. Expected shape of live ranges:
-    //
-    //                 i  i'
-    //    input #0   --*
-    //    output       [----
-    //
-    ASSERT(locs->in(0).Equals(Location::RequiresRegister()) ||
-           locs->in(0).Equals(Location::RequiresFpuRegister()));
-
-    // Create move that will copy value between input and output.
-    locs->set_out(0, Location::RequiresRegister());
-    MoveOperands* move = AddMoveAt(pos,
-                                   Location::RequiresRegister(),
-                                   Location::Any());
-
-    // Add uses to the live range of the input.
-    Definition* input = current->InputAt(0)->definition();
-    LiveRange* input_range =
-        GetLiveRange(input->ssa_temp_index());
-    input_range->AddUseInterval(block->start_pos(), pos);
-    input_range->AddUse(pos, move->src_slot());
-
-    // Shorten output live range to the point of definition and add both input
-    // and output uses slots to be filled by allocator.
-    range->DefineAt(pos);
-    range->AddHintedUse(pos, out, move->src_slot());
-    range->AddUse(pos, move->dest_slot());
-    range->AddUse(pos, locs->in_slot(0));
-
-    if ((interference_set != NULL) &&
-        (range->vreg() >= 0) &&
-        interference_set->Contains(range->vreg())) {
-      interference_set->Add(input->ssa_temp_index());
+  if (out->IsPairLocation()) {
+    ASSERT(def->HasPairRepresentation());
+    PairLocation* pair = out->AsPairLocation();
+    if (output_same_as_first_input) {
+      ASSERT(locs->in_slot(0)->IsPairLocation());
+      PairLocation* in_pair = locs->in_slot(0)->AsPairLocation();
+      Definition* input = current->InputAt(0)->definition();
+      ASSERT(input->HasPairRepresentation());
+      // Each element of the pair is assigned it's own virtual register number
+      // and is allocated its own LiveRange.
+      ProcessOneOutput(block, current, pos,  // BlockEntry, Instruction, seq.
+                       pair->SlotAt(0), def,  // (output) Location, Definition.
+                       def->ssa_temp_index(),  // (output) virtual register.
+                       true,  // output mapped to first input.
+                       in_pair->SlotAt(0), input,  // (input) Location, Def.
+                       input->ssa_temp_index(),  // (input) virtual register.
+                       interference_set);
+      ProcessOneOutput(block, current, pos,
+                       pair->SlotAt(1), def,
+                       ToSecondPairVreg(def->ssa_temp_index()),
+                       true,
+                       in_pair->SlotAt(1), input,
+                       ToSecondPairVreg(input->ssa_temp_index()),
+                       interference_set);
+    } else {
+      // Each element of the pair is assigned it's own virtual register number
+      // and is allocated its own LiveRange.
+      ProcessOneOutput(block, current, pos,
+                       pair->SlotAt(0), def,
+                       def->ssa_temp_index(),
+                       false,            // output is not mapped to first input.
+                       NULL, NULL, -1,   // First input not needed.
+                       interference_set);
+      ProcessOneOutput(block, current, pos,
+                       pair->SlotAt(1), def,
+                       ToSecondPairVreg(def->ssa_temp_index()),
+                       false,
+                       NULL, NULL, -1,
+                       interference_set);
     }
   } else {
-    // Normal unallocated location that requires a register. Expected shape of
-    // live range:
-    //
-    //                    i  i'
-    //    output          [-------
-    //
-    ASSERT(locs->out(0).Equals(Location::RequiresRegister()) ||
-           locs->out(0).Equals(Location::RequiresFpuRegister()));
-
-    // Shorten live range to the point of definition and add use to be filled by
-    // allocator.
-    range->DefineAt(pos);
-    range->AddUse(pos, out);
+    if (output_same_as_first_input) {
+      Location* in_ref = locs->in_slot(0);
+      Definition* input = current->InputAt(0)->definition();
+      ASSERT(!in_ref->IsPairLocation());
+      ProcessOneOutput(block, current, pos,  // BlockEntry, Instruction, seq.
+                       out, def,  // (output) Location, Definition.
+                       def->ssa_temp_index(),  // (output) virtual register.
+                       true,  // output mapped to first input.
+                       in_ref, input,  // (input) Location, Def.
+                       input->ssa_temp_index(),  // (input) virtual register.
+                       interference_set);
+    } else {
+      ProcessOneOutput(block, current, pos,
+                       out, def,
+                       def->ssa_temp_index(),
+                       false,            // output is not mapped to first input.
+                       NULL, NULL, -1,   // First input not needed.
+                       interference_set);
+    }
   }
-
-  AssignSafepoints(range);
-  CompleteRange(range, RegisterKindForResult(current));
 }
 
 
 static ParallelMoveInstr* CreateParallelMoveBefore(Instruction* instr,
                                                    intptr_t pos) {
   ASSERT(pos > 0);
   Instruction* prev = instr->previous();
   ParallelMoveInstr* move = prev->AsParallelMove();
   if ((move == NULL) || (move->lifetime_position() != pos)) {
     move = new ParallelMoveInstr();
@@ skipping 566 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) {
     phi->set_reaching_defs(
         new BitVector(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 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 83 matching lines @@
       (loop_header != NULL) &&
       (free_until >= loop_header->last_block()->end_pos()) &&
       loop_header->backedge_interference()->Contains(unallocated->vreg())) {
     ASSERT(static_cast<intptr_t>(kNumberOfFpuRegisters) <=
            kNumberOfCpuRegisters);
     bool used_on_backedge[kNumberOfCpuRegisters] = { 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();
       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;
         }
@@ skipping 44 matching lines @@
   registers_[candidate].Add(unallocated);
   unallocated->set_assigned_location(MakeRegisterLocation(candidate));
 
   return true;
 }
 
 
 bool FlowGraphAllocator::RangeHasOnlyUnconstrainedUsesInLoop(LiveRange* range,
                                                              intptr_t loop_id) {
   if (range->vreg() >= 0) {
-    return GetLiveRange(range->vreg())->HasOnlyUnconstrainedUsesInLoop(loop_id);
+    LiveRange* parent = GetLiveRange(range->vreg());
+    return parent->HasOnlyUnconstrainedUsesInLoop(loop_id);
   }
   return false;
 }
 
 
 bool FlowGraphAllocator::IsCheapToEvictRegisterInLoop(BlockInfo* loop,
                                                       intptr_t reg) {
   const intptr_t loop_start = loop->entry()->start_pos();
   const intptr_t loop_end = loop->last_block()->end_pos();
 
@@ skipping 60 matching lines @@
   const intptr_t register_use_pos =
       (register_use != NULL) ? register_use->pos()
                              : unallocated->Start();
   if (free_until < register_use_pos) {
     // Can't acquire free register. Spill until we really need one.
     ASSERT(unallocated->Start() < ToInstructionStart(register_use_pos));
     SpillBetween(unallocated, unallocated->Start(), register_use->pos());
     return;
   }
 
+  ASSERT(candidate != kNoRegister);
+
   TRACE_ALLOC(OS::Print("assigning blocked register "));
   TRACE_ALLOC(MakeRegisterLocation(candidate).Print());
   TRACE_ALLOC(OS::Print(" to live range v%" Pd " until %" Pd "\n",
                         unallocated->vreg(), blocked_at));
 
   if (blocked_at < unallocated->End()) {
     // Register is blocked before the end of the live range.  Split the range
     // at latest at blocked_at position.
     LiveRange* tail = SplitBetween(unallocated,
                                    unallocated->Start(),
@@ skipping 490 matching lines @@
   }
 }
 
 
 void FlowGraphAllocator::CollectRepresentations() {
   // Parameters.
   GraphEntryInstr* graph_entry = flow_graph_.graph_entry();
   for (intptr_t i = 0; i < graph_entry->initial_definitions()->length(); ++i) {
     Definition* def = (*graph_entry->initial_definitions())[i];
     value_representations_[def->ssa_temp_index()] = def->representation();
+    ASSERT(!def->HasPairRepresentation());
   }
 
   for (BlockIterator it = flow_graph_.reverse_postorder_iterator();
        !it.Done();
        it.Advance()) {
     BlockEntryInstr* block = it.Current();
 
     // Catch entry.
     if (block->IsCatchBlockEntry()) {
       CatchBlockEntryInstr* catch_entry = block->AsCatchBlockEntry();
       for (intptr_t i = 0;
            i < catch_entry->initial_definitions()->length();
            ++i) {
         Definition* def = (*catch_entry->initial_definitions())[i];
         value_representations_[def->ssa_temp_index()] = 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)) {
           value_representations_[phi->ssa_temp_index()] = 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)) {
-        value_representations_[def->ssa_temp_index()] = def->representation();
+        const intptr_t vreg = def->ssa_temp_index();
+        value_representations_[vreg] = def->representation();
+        if (def->HasPairRepresentation()) {
+         value_representations_[ToSecondPairVreg(vreg)] = def->representation();
+        }
       }
     }
   }
 }
 
 
 void FlowGraphAllocator::AllocateRegisters() {
   CollectRepresentations();
 
   liveness_.Analyze();
@@ skipping 59 matching lines @@
     OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(flow_graph_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart