New linear scan allocator.

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 10 matching lines @@
 #define TRACE_ALLOC(m) do {                     \
     if (FLAG_trace_ssa_allocator) OS::Print m ; \
   } while (0)
 #else
 #define TRACE_ALLOC(m)
 #endif
 
 
 static const intptr_t kNoVirtualRegister = -1;
 static const intptr_t kTempVirtualRegister = -2;
-static UseInterval* const kPermanentlyBlocked =
-  reinterpret_cast<UseInterval*>(-1);
 static const intptr_t kIllegalPosition = -1;
 static const intptr_t kMaxPosition = 0x7FFFFFFF;
 
 
+static intptr_t MinPosition(intptr_t a, intptr_t b) {
+  return (a < b) ? a : b;
+}
+
+
+static bool IsParallelMovePosition(intptr_t pos) {
+  return (pos & 1) == 0;
+}
+
+
+static bool IsInstructionPosition(intptr_t pos) {
+  return (pos & 1) == 1;
+}
+
+
+static intptr_t ToParallelMove(intptr_t pos) {
+  return (pos & ~1);
+}
+
 FlowGraphAllocator::FlowGraphAllocator(
   const GrowableArray<BlockEntryInstr*>& block_order,
   FlowGraphBuilder* builder)
   : builder_(builder),
     block_order_(block_order),
     postorder_(builder->postorder_block_entries()),
     live_out_(block_order.length()),
     kill_(block_order.length()),
     live_in_(block_order.length()),
     vreg_count_(builder->current_ssa_temp_index()),
     live_ranges_(builder->current_ssa_temp_index()) {
   for (intptr_t i = 0; i < vreg_count_; i++) live_ranges_.Add(NULL);
 
   for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
-    cpu_regs_[reg] = NULL;
+    blocked_cpu_regs_[reg] = false;
   }
 
-  cpu_regs_[CTX] = kPermanentlyBlocked;
+  blocked_cpu_regs_[CTX] = true;
   if (TMP != kNoRegister) {
-    cpu_regs_[TMP] = kPermanentlyBlocked;
+    blocked_cpu_regs_[TMP] = true;
   }
-  cpu_regs_[SPREG] = kPermanentlyBlocked;
-  cpu_regs_[FPREG] = kPermanentlyBlocked;
+  blocked_cpu_regs_[SPREG] = true;
+  blocked_cpu_regs_[FPREG] = true;
 }
 
 
 void FlowGraphAllocator::ComputeInitialSets() {
   const intptr_t block_count = postorder_.length();
   for (intptr_t i = 0; i < block_count; i++) {
     BlockEntryInstr* block = postorder_[i];
 
     BitVector* kill = kill_[i];
     BitVector* live_in = live_in_[i];
@@ skipping 136 matching lines @@
     }
     OS::Print("\n");
 
     PrintBitVector("  live out", live_out_[i]);
     PrintBitVector("  kill", kill_[i]);
     PrintBitVector("  live in", live_in_[i]);
   }
 }
 
 
-void UseInterval::Print() {
-  OS::Print("  [%d, %d) uses {", start_, end_);
-  for (UsePosition* use_pos = uses_;
-       use_pos != NULL && use_pos->pos() <= end();
-       use_pos = use_pos->next()) {
-    if (use_pos != uses_) OS::Print(", ");
-    OS::Print("%d", use_pos->pos());
-  }
-  OS::Print("}\n");
-}
-
-
-void UseInterval::AddUse(Instruction* instr,
-                         intptr_t pos,
-                         Location* location_slot) {
-  ASSERT((start_ <= pos) && (pos <= end_));
-  ASSERT((instr == NULL) || (instr->lifetime_position() == pos));
+void LiveRange::AddUse(intptr_t pos,
+                       Location* location_slot) {

[srdjan, 2012/07/22 23:27:33]

Args should fit into one line.

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+  ASSERT((first_use_interval_->start_ <= pos) &&
+         (pos <= first_use_interval_->end_));
   if ((uses_ != NULL) && (uses_->pos() == pos)) {
     if ((location_slot == NULL) || (uses_->location_slot() == location_slot)) {
       return;
-    } else if ((uses_->location_slot() == NULL) && (instr == NULL)) {
+    } else if (uses_->location_slot() == NULL) {
       uses_->set_location_slot(location_slot);
       return;
     }
   }
-  uses_ = new UsePosition(instr, pos, uses_, location_slot);
+  uses_ = new UsePosition(pos, uses_, location_slot);
 }
 
 
-void LiveRange::Print() {
-  OS::Print("vreg %d live intervals:\n", vreg_);
-  for (UseInterval* interval = head_;
-       interval != NULL;
-       interval = interval->next_) {
-    interval->Print();
+void LiveRange::AddUseInterval(intptr_t start, intptr_t end) {
+  if (first_use_interval_ != NULL) {

[srdjan, 2012/07/22 23:27:33]

Add comment: do not add if the first_use_interval_ covers the new interval. What
about other use_intervals (linked via next_). Why add an interval when it is
already covered by an existing one? Should you traverse all intervals to figure
it out?

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Added comment.

+    if (first_use_interval_->start_ == start) {
+      ASSERT(end <= first_use_interval_->end_);
+      return;
+    } else if (first_use_interval_->start_ == end) {
+      first_use_interval_->start_ = start;

[srdjan, 2012/07/22 23:27:33]

Do you want to do that even if start < first_use_interval_->start, i.e., do you
allow shrinking of UseInterval?

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

This is not shrinking this is expansion. UseIntervals are being built in a
monotonically decreasing order.

+      return;
+    }
+  }
+
+  first_use_interval_ = new UseInterval(start, end, first_use_interval_);
+  if (last_use_interval_ == NULL) last_use_interval_ = first_use_interval_;

[srdjan, 2012/07/22 23:27:33]

ASSERT(last_use_interval_->next() == NULL) thus making sure that nobody else
wrote into first_use_interval_ before.

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+}
+
+
+void LiveRange::DefineAt(intptr_t pos) {
+  if (first_use_interval_ != NULL) {

[srdjan, 2012/07/22 23:27:33]

I would revert, test for positive first, makes it more readable IMHO.

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+    ASSERT(first_use_interval_->start_ <= pos);
+    first_use_interval_->start_ = pos;
+  } else {
+    // Definition without a use.
+    first_use_interval_ = new UseInterval(pos, pos + 1, NULL);
+    last_use_interval_ = first_use_interval_;
   }
 }
 
 
-void LiveRange::AddUseInterval(intptr_t start, intptr_t end) {
-  if ((head_ != NULL) && (head_->start_ == end)) {
-    head_->start_ = start;
-    return;
-  }
-
-  head_ = new UseInterval(vreg_, start, end, head_);
-}
-
-
-void LiveRange::DefineAt(Instruction* instr, intptr_t pos, Location* loc) {
-  if (head_ != NULL) {
-    ASSERT(head_->start_ <= pos);
-    head_->start_ = pos;
-  } else {
-    // Definition without a use.
-    head_ = new UseInterval(vreg_, pos, pos + 1, NULL);
-  }
-  head_->AddUse(instr, pos, loc);
-}
-
-
-// TODO(vegorov): encode use_at_start vs. use_at_end in the location itself?
-void LiveRange::UseAt(Instruction* instr,
-                      intptr_t def, intptr_t use,
-                      bool use_at_end,
-                      Location* loc) {
-  if (head_ == NULL || head_->start_ != def) {
-    AddUseInterval(def, use + (use_at_end ? 1 : 0));
-  }
-  head_->AddUse(instr, use, loc);
-}
-
-
 LiveRange* FlowGraphAllocator::GetLiveRange(intptr_t vreg) {
   if (live_ranges_[vreg] == NULL) {
     live_ranges_[vreg] = new LiveRange(vreg);
   }
   return live_ranges_[vreg];
 }
 
 
-void FlowGraphAllocator::BlockLocation(Location loc, intptr_t pos) {
+void FlowGraphAllocator::BlockLocation(Location loc,
+                                       intptr_t from,
+                                       intptr_t to) {
   ASSERT(loc.IsRegister());
   const Register reg = loc.reg();
-  UseInterval* last = cpu_regs_[reg];
-  if (last == kPermanentlyBlocked) return;
-  if ((last != NULL) && (last->start() == pos)) return;
-  cpu_regs_[reg] = new UseInterval(kNoVirtualRegister, pos, pos + 1, last);
-}
-
-
-void FlowGraphAllocator::Define(Instruction* instr,
-                                intptr_t pos,
-                                intptr_t vreg,
-                                Location* loc) {
-  LiveRange* range = GetLiveRange(vreg);
-  ASSERT(loc != NULL);
-  if (loc->IsRegister()) {
-    BlockLocation(*loc, pos);
-    range->DefineAt(instr, pos + 1, loc);
-  } else if (loc->IsUnallocated()) {
-    range->DefineAt(instr, pos, loc);
-  } else {
-    UNREACHABLE();
-  }
-
-  AddToUnallocated(range->head());
-}
-
-
-void FlowGraphAllocator::UseValue(Instruction* instr,
-                                  intptr_t def_pos,
-                                  intptr_t use_pos,
-                                  intptr_t vreg,
-                                  Location* loc,
-                                  bool use_at_end) {
-  LiveRange* range = GetLiveRange(vreg);
-  if (loc == NULL) {
-    range->UseAt(NULL, def_pos, use_pos, true, loc);
-  } else if (loc->IsRegister()) {
-    // We have a fixed use.
-    BlockLocation(*loc, use_pos);
-    range->UseAt(instr, def_pos, use_pos, false, loc);
-  } else if (loc->IsUnallocated()) {
-    ASSERT(loc->policy() == Location::kRequiresRegister);
-    range->UseAt(use_at_end ? NULL : instr, def_pos, use_pos, use_at_end, loc);
-  }
-}
-
-
-static void PrintChain(UseInterval* chain) {
-  if (chain == kPermanentlyBlocked) {
-    OS::Print("  not for allocation\n");
-    return;
-  }
-
-  while (chain != NULL) {
-    chain->Print();
-    chain = chain->next();
+  if (blocked_cpu_regs_[reg]) return;

[srdjan, 2012/07/22 23:27:33]

 == NULL

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

blocked_cpu_regs_[reg] is a bool value.

+  if (cpu_regs_[reg].length() == 0) {
+    cpu_regs_[reg].Add(new LiveRange(kNoVirtualRegister));
+  }
+  cpu_regs_[reg][0]->AddUseInterval(from, to);
+}
+
+
+void LiveRange::Print() {
+  OS::Print("  live range v%d [%d, %d)\n", vreg(), Start(), End());
+  UsePosition* use_pos = uses_;
+  for (UseInterval* interval = first_use_interval_;
+       interval != NULL;
+       interval = interval->next()) {
+    OS::Print("    use interval [%d, %d)\n",
+              interval->start(),
+              interval->end());
+    while ((use_pos != NULL) && (use_pos->pos() <= interval->end())) {
+      OS::Print("      use at %d as %s\n",
+                use_pos->pos(),
+                (use_pos->location_slot() == NULL)
+                ? "-" : use_pos->location_slot()->Name());
+      use_pos = use_pos->next();
+    }
+  }
+
+  if (next_sibling() != NULL) {
+    next_sibling()->Print();
   }
 }
 
 
 void FlowGraphAllocator::PrintLiveRanges() {
   for (intptr_t i = 0; i < unallocated_.length(); i++) {
-    OS::Print("unallocated chain for vr%d\n", unallocated_[i]->vreg());
-    PrintChain(unallocated_[i]);
+    unallocated_[i]->Print();
   }
 
   for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
-    OS::Print("blocking chain for %s\n",
+    if (blocked_cpu_regs_[reg]) continue;
+    if (cpu_regs_[reg].length() == 0) continue;
+
+    ASSERT(cpu_regs_[reg].length() == 1);
+    OS::Print("blocking live range for %s\n",
               Location::RegisterLocation(static_cast<Register>(reg)).Name());
-    PrintChain(cpu_regs_[reg]);
-  }
+    cpu_regs_[reg][0]->Print();
+  }
+}
+
+
+Instruction* FlowGraphAllocator::ConnectOutgoingPhiMoves(
+  BlockEntryInstr* block) {

[srdjan, 2012/07/22 15:09:24]

indent 4 spaces

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+  Instruction* last = block->last_instruction();
+
+  GotoInstr* goto_instr = last->AsGoto();
+  if (goto_instr == NULL) return last;

[srdjan, 2012/07/22 23:27:33]

What about branches?

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Branches cannot have outgoing phi moves this violates edge split form.

+
+  // If we have a parallel move here then the successor block must be a
+  // join with phis.  The phi inputs contribute uses to each predecessor
+  // block (and the phi outputs contribute definitions in the successor
+  // block).
+  ParallelMoveInstr* parallel_move = goto_instr->previous()->AsParallelMove();
+  if (parallel_move == NULL) return last->previous();

[srdjan, 2012/07/22 23:27:33]

Since last can survive here only as goto_instr, return goto_instr->previous() ?

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+
+  // All uses are recorded at the position of parallel move preceding goto.
+  const intptr_t pos = goto_instr->lifetime_position() - 1;
+  ASSERT((pos >= 0) && IsParallelMovePosition(pos));
+
+  JoinEntryInstr* join = goto_instr->successor();
+  ASSERT(join != NULL);
+
+  // 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 < join->PredecessorCount());

[srdjan, 2012/07/22 23:27:33]

class JoinInstr has a method that does the above:
intptr_t pred_idx = join->IndexOfPredecessor(block);

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

I guess this code predates the method. Thanks.

+
+  // Record the corresponding phi input use for each phi.
+  ZoneGrowableArray<PhiInstr*>* phis = join->phis();
+  intptr_t move_idx = 0;
+  for (intptr_t phi_idx = 0; phi_idx < phis->length(); phi_idx++) {
+    PhiInstr* phi = (*phis)[phi_idx];
+    if (phi == NULL) continue;
+
+    Value* val = phi->InputAt(pred_idx);
+    MoveOperands* move = parallel_move->MoveOperandsAt(move_idx);
+    if (val->IsUse()) {
+      // Expected shape of live ranges (m is parallel move, g is goto
+      // instruction):
+      //
+      //                 m  g
+      //      value    --*
+      //

[srdjan, 2012/07/22 15:09:24]

I do not understand the comment above. I see you are using the format below as
well. Please explain what *, - etc means.

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+
+      LiveRange* range = GetLiveRange(
+        val->AsUse()->definition()->ssa_temp_index());

[srdjan, 2012/07/22 15:09:24]

4 spaces indent. 2 spaces is used only when starting a new nested block.

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+
+      Location* slot = move->src_slot();
+      *slot = Location::PrefersRegister();
+
+      range->AddUseInterval(block->start_pos(), pos);
+      range->AddUse(pos, slot);

[srdjan, 2012/07/22 23:27:33]

Rewrite: 
move->set_src(Location::Prefersregister());
range->AddUseInterval(block->start_pos(), pos);
range->AddUse(pos, move->src_slot());

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+    } else {
+      ASSERT(val->IsConstant());
+      move->set_src(Location::Constant(val->AsConstant()->value()));
+    }
+    move_idx++;
+  }
+
+  // Begin backward iteration with the instruction before the parallel
+  // move.
+  return parallel_move->previous();
+}
+
+
+void FlowGraphAllocator::ConnectIncommingPhiMoves(BlockEntryInstr* block) {

[srdjan, 2012/07/22 23:27:33]

s/Incomming/Incoming/

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+  // 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.
+  JoinEntryInstr* join = block->AsJoinEntry();
+  if (join == NULL) return;
+
+  // All uses are recorded at the start position in the block.
+  const intptr_t pos = block->start_pos();
+

[srdjan, 2012/07/22 23:27:33]

s/block/join/

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+  ZoneGrowableArray<PhiInstr*>* phis = join->phis();
+  if (phis != NULL) {
+    intptr_t move_idx = 0;
+    for (intptr_t j = 0; j < phis->length(); j++) {
+      PhiInstr* phi = (*phis)[j];
+      if (phi == NULL) continue;
+
+      const intptr_t vreg = phi->ssa_temp_index();
+      ASSERT(vreg != -1);
+
+      // Expected shape of live range (B is the block start):
+      //
+      //                 B
+      //      phi        [--------
+      //

[srdjan, 2012/07/22 15:09:24]

ditto

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+
+      LiveRange* range = GetLiveRange(vreg);
+      range->DefineAt(pos);  // Shorten live range.
+
+      for (intptr_t k = 0; k < phi->InputCount(); k++) {
+        BlockEntryInstr* pred = block->PredecessorAt(k);
+        ASSERT(pred->last_instruction()->IsGoto());
+        Instruction* move_instr = pred->last_instruction()->previous();
+        ASSERT(move_instr->IsParallelMove());
+
+        MoveOperands* move =
+          move_instr->AsParallelMove()->MoveOperandsAt(move_idx);

[srdjan, 2012/07/22 23:27:33]

indent 4

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+        move->set_dest(Location::PrefersRegister());
+        range->AddUse(pos, move->dest_slot());
+      }
+
+      // All phi resolution moves are connected. Phi's live range is
+      // complete.
+      AddToUnallocated(range);
+
+      move_idx++;
+    }
+  }
+}
+
+
+void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block,
+                                               Instruction* current) {

[srdjan, 2012/07/22 23:27:33]

ProcessOneInstruction is not self explanatory, pelase add brief comment or
rename.

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+  const intptr_t pos = current->lifetime_position();
+  ASSERT(IsInstructionPosition(pos));
+
+  LocationSummary* locs = current->locs();
+
+  // TODO(vegorov): number of inputs must match number of input locations.
+  if (locs->input_count() != current->InputCount()) {
+    builder_->Bailout("ssa allocator: number of input locations mismatch");
+  }
+
+  const bool output_same_as_first_input =
+    locs->out().IsUnallocated() &&
+    (locs->out().policy() == Location::kSameAsFirstInput);

[srdjan, 2012/07/22 23:27:33]

Indent 4

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+
+  // Add uses from the deoptimization environment.
+  if (current->env() != NULL) {
+    // Any value mentioned in the deoptimization environment should survive
+    // until the end of instruction but it does not need to be in the register.
+    // Expected shape of live range:
+    //
+    //                 m  i  m
+    //      value    -----*--)
+    //
+
+    const GrowableArray<Value*>& values = current->env()->values();
+    GrowableArray<Location>* locations = current->env()->locations();
+
+    for (intptr_t j = 0; j < values.length(); j++) {
+      Value* val = values[j];
+      if (val->IsUse()) {
+        locations->Add(Location::Any());
+        const intptr_t vreg = val->AsUse()->definition()->ssa_temp_index();
+
+        LiveRange* range = GetLiveRange(vreg);
+        range->AddUseInterval(block->start_pos(), pos + 1);
+        range->AddUse(pos, &(*locations)[j]);
+      } else {
+        ASSERT(val->IsConstant());
+        locations->Add(Location::NoLocation());
+      }
+    }
+  }
+
+  // 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);
+    ASSERT(input->IsUse());  // Can not be a constant currently.
+
+    const intptr_t vreg = input->AsUse()->definition()->ssa_temp_index();
+    LiveRange* range = GetLiveRange(vreg);
+
+    Location* in_ref = locs->in_slot(j);
+
+    if (in_ref->IsRegister()) {
+      // Input is expected in a fixed register. Expected shape of
+      // live ranges:
+      //
+      //                 m  i  m
+      //      value    --*
+      //      register   [-----)
+      //
+      MoveOperands* move =
+        AddMoveAt(pos - 1, *in_ref, Location::PrefersRegister());

[srdjan, 2012/07/22 23:27:33]

4 spaces

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+      BlockLocation(*in_ref, pos - 1, pos + 1);
+      range->AddUseInterval(block->start_pos(), pos - 1);
+      range->AddUse(pos - 1, move->src_slot());
+    } else {
+      // Normal unallocated input. Expected shape of
+      // live ranges:
+      //
+      //                 m  i  m
+      //      value    -----*--)
+      //
+      ASSERT(in_ref->IsUnallocated());
+      range->AddUseInterval(block->start_pos(), pos + 1);
+      range->AddUse(pos, in_ref);
+    }
+  }
+
+  // Process temps.
+  for (intptr_t j = 0; j < locs->temp_count(); j++) {
+    // Expected shape of live range:
+    //
+    //           m  i  m
+    //              [--)
+    //
+
+    Location temp = locs->temp(j);
+    if (temp.IsRegister()) {
+      BlockLocation(temp, pos, pos + 1);
+    } else if (temp.IsUnallocated()) {
+      LiveRange* range = new LiveRange(kTempVirtualRegister);
+      range->AddUseInterval(pos, pos + 1);
+      range->AddUse(pos, locs->temp_slot(j));
+      AddToUnallocated(range);
+    } else {
+      UNREACHABLE();
+    }
+  }
+
+  // Block all allocatable registers for calls.
+  if (locs->is_call()) {
+    // Expected shape of live range:
+    //
+    //           m  i  m
+    //              [--)
+    //
+
+    for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
+      BlockLocation(Location::RegisterLocation(static_cast<Register>(reg)),
+                    pos,
+                    pos + 1);
+    }
+
+#ifdef 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).IsUnallocated());
+    }
+
+    for (intptr_t j = 0; j < locs->input_count(); j++) {
+      ASSERT(!locs->in(j).IsUnallocated());
+    }
+
+    ASSERT(!locs->out().IsUnallocated());
+#endif
+  }
+
+  Definition* def = current->AsDefinition();
+  if ((def == NULL) || (def->ssa_temp_index() < 0)) {
+    ASSERT(locs->out().IsInvalid());
+    return;
+  }
+
+  LiveRange* range = GetLiveRange(def->ssa_temp_index());
+  Location* out = locs->out_slot();
+
+  // Process output and finalize its liverange.
+  if (out->IsRegister()) {
+    // Fixed output location. Expected shape of live range:
+    //
+    //                 m  i  m
+    //    register        [--)
+    //    output             [-------
+    //
+    BlockLocation(*out, pos, pos + 1);
+    // We need to emit move connecting out to some other place.
+    // Interesting case is: fixed output + fixed input last use:
+
+    UsePosition* use = range->first_use();
+    if (use->pos() == (pos + 1)) {
+      // We have a use position on the parallel move.
+      ASSERT(use->location_slot()->IsUnallocated());
+      *(use->location_slot()) = *out;
+    }
+
+    // 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::PrefersRegister(), *out);
+    range->AddUse(pos - 1, move->dest_slot());
+  } 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:
+    //
+    //                 m  i  m
+    //    input #0   --*
+    //    output       [--*----
+    //
+    ASSERT(locs->in_slot(0)->Equals(Location::RequiresRegister()));
+
+    // Create move that will copy value between input and output.
+    locs->set_out(Location::RequiresRegister());
+    MoveOperands* move = AddMoveAt(pos - 1,
+                                   Location::RequiresRegister(),
+                                   Location::PrefersRegister());
+
+    // Add uses to the live range of the input.
+    Value* input = current->InputAt(0);
+    ASSERT(input->IsUse());  // Can not be a constant currently.
+    LiveRange* input_range = GetLiveRange(
+      input->AsUse()->definition()->ssa_temp_index());
+    input_range->AddUseInterval(block->start_pos(), pos - 1);
+    input_range->AddUse(pos - 1, 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 - 1);
+    range->AddUse(pos - 1, out);
+    range->AddUse(pos - 1, move->dest_slot());
+    range->AddUse(pos, locs->in_slot(0));
+  } else {
+    // Normal unallocated location that requires a register. Expected shape of
+    // live range:
+    //
+    //                 m  i  m
+    //    output          [-------
+    //
+    ASSERT(out->IsUnallocated() &&
+           (out->policy() == Location::kRequiresRegister));
+
+    // Shorten live range to the point of definition and add use to be filled by
+    // allocator.
+    range->DefineAt(pos);
+    range->AddUse(pos, out);
+  }
+
+  AddToUnallocated(range);
 }
 
 
 void FlowGraphAllocator::BuildLiveRanges() {
   NumberInstructions();
 
   const intptr_t block_count = postorder_.length();
-  for (intptr_t i = 0; i < block_count; i++) {
+  ASSERT(postorder_[block_count - 1]->IsGraphEntry());
+  for (intptr_t i = 0; i < (block_count - 1); i++) {
     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 beginning of the last instruction in the
-    // block.
-    intptr_t pos = block->end_pos() - 1;
-    Instruction* current = block->last_instruction();
-
-    // Goto instructions do not contribute liveness information.
-    GotoInstr* goto_instr = current->AsGoto();
-    if (goto_instr != NULL) {
+    // Connect outgoing phi-moves that were created in NumberInstructions
+    // and find last instruction that contributes to liveness.
+    Instruction* current = ConnectOutgoingPhiMoves(block);
+
+    // Now process all instructions in reverse order.
+    while (current != block) {
+      // Skip parallel moves that we insert while processing instructions.
+      if (!current->IsParallelMove()) {
+        ProcessOneInstruction(block, current);
+      }
       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 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();
-      if (parallel_move != NULL) {
-        JoinEntryInstr* join = goto_instr->successor();
-        ASSERT(join != NULL);
-
-        // 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 < join->PredecessorCount());
-
-        // Record the corresponding phi input use for each phi.
-        ZoneGrowableArray<PhiInstr*>* phis = join->phis();
-        intptr_t move_idx = 0;
-        for (intptr_t phi_idx = 0; phi_idx < phis->length(); phi_idx++) {
-          PhiInstr* phi = (*phis)[phi_idx];
-          if (phi == NULL) continue;
-
-          Value* val = phi->InputAt(pred_idx);
-          MoveOperands* move = parallel_move->MoveOperandsAt(move_idx);
-          if (val->IsUse()) {
-            const intptr_t virtual_register =
-                val->AsUse()->definition()->ssa_temp_index();
-            move->set_src(Location::RequiresRegister());
-            GetLiveRange(
-                virtual_register)->head()->AddUse(NULL, pos, move->src_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();
-      }
-    }
-
-    // Now process all instructions in reverse order.
-    --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++) {
-        Value* input = current->InputAt(j);
-        if (input->IsUse()) {
-          const intptr_t use = input->AsUse()->definition()->ssa_temp_index();
-
-          Location* in_ref = (j < locs->input_count()) ?
-            locs->in_slot(j) : NULL;
-          const bool use_at_end = (j > 0) || (in_ref == NULL) ||
-            !output_same_as_first_input;
-          UseValue(current, block->start_pos(), pos, use, in_ref, use_at_end);
-        }
-      }
-
-      // Add uses from the deoptimization environment.
-      // TODO(vegorov): these uses should _not_ require register but for now
-      // they do because we don't support spilling at all.
-      if (current->env() != NULL) {
-        const GrowableArray<Value*>& values = current->env()->values();
-        GrowableArray<Location>* locations = current->env()->locations();
-
-        for (intptr_t j = 0; j < values.length(); j++) {
-          Value* val = values[j];
-          if (val->IsUse()) {
-            locations->Add(Location::RequiresRegister());
-            const intptr_t use = val->AsUse()->definition()->ssa_temp_index();
-            UseValue(current,
-                     block->start_pos(),
-                     pos,
-                     use,
-                     &(*locations)[j],
-                     true);
-          } else {
-            locations->Add(Location::NoLocation());
-          }
-        }
-      }
-
-      // Process temps.
-      for (intptr_t j = 0; j < locs->temp_count(); j++) {
-        Location temp = locs->temp(j);
-        if (temp.IsRegister()) {
-          BlockLocation(temp, pos);
-        } else if (temp.IsUnallocated()) {
-          UseInterval* temp_interval = new UseInterval(
-            kTempVirtualRegister, pos, pos + 1, NULL);
-          temp_interval->AddUse(NULL, pos, locs->temp_slot(j));
-          AddToUnallocated(temp_interval);
-        } else {
-          UNREACHABLE();
-        }
-      }
-
-      // Block all allocatable registers for calls.
-      if (locs->is_call()) {
-        for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
-          BlockLocation(Location::RegisterLocation(static_cast<Register>(reg)),
-                        pos);
-        }
-      }
-
-      if (locs->out().IsRegister()) {
-        builder_->Bailout("ssa allocator: fixed outputs are not supported");
-      }
-
-      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());
-      }
-
-      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.
-    JoinEntryInstr* join = block->AsJoinEntry();
-    if (join != NULL) {
-      ZoneGrowableArray<PhiInstr*>* phis = join->phis();
-      if (phis != NULL) {
-        intptr_t move_idx = 0;
-        for (intptr_t j = 0; j < phis->length(); j++) {
-          PhiInstr* phi = (*phis)[j];
-          if (phi == NULL) continue;
-
-          const intptr_t virtual_register = phi->ssa_temp_index();
-          ASSERT(virtual_register != -1);
-
-          LiveRange* range = GetLiveRange(virtual_register);
-          range->DefineAt(NULL, pos, NULL);
-          UseInterval* interval = GetLiveRange(virtual_register)->head();
-
-          for (intptr_t k = 0; k < phi->InputCount(); k++) {
-            BlockEntryInstr* pred = block->PredecessorAt(k);
-            ASSERT(pred->last_instruction()->IsGoto());
-            Instruction* move_instr = pred->last_instruction()->previous();
-            ParallelMoveInstr* pmove = move_instr->AsParallelMove();
-            ASSERT(pmove != NULL);
-
-            MoveOperands* move_operands = pmove->MoveOperandsAt(move_idx);
-            move_operands->set_dest(Location::RequiresRegister());
-            interval->AddUse(NULL, pos, move_operands->dest_slot());
-          }
-
-          // All phi resolution moves are connected. Phi's live range is
-          // complete.
-          AddToUnallocated(interval);
-
-          move_idx++;
-        }
-      }
-    }
-  }
-}
-
-
+    }
+
+    ConnectIncommingPhiMoves(block);
+  }
+}
+
+
+static ParallelMoveInstr* CreateParallelMoveBefore(Instruction* instr,
+                                                   intptr_t pos) {
+  Instruction* prev = instr->previous();
+  ParallelMoveInstr* move = prev->AsParallelMove();
+  if ((move == NULL) || (move->lifetime_position() != pos)) {
+    move = new ParallelMoveInstr();
+    move->set_next(prev->next());
+    prev->set_next(move);
+    move->next()->set_previous(move);
+    move->set_previous(prev);
+    move->set_lifetime_position(pos);
+  }
+  return move;
+}
+
+
+static ParallelMoveInstr* CreateParallelMoveAfter(Instruction* instr,
+                                                  intptr_t pos) {
+  Instruction* next = instr->next();
+  if (next->IsParallelMove() && (next->lifetime_position() == pos)) {
+    return next->AsParallelMove();
+  }
+  return CreateParallelMoveBefore(next, pos);
+}
+
+
 // 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.
 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];
+
+    instructions_.Add(block);
     block->set_start_pos(pos);
-    block->set_lifetime_position(pos);
+    block->set_lifetime_position(pos + 1);
     pos += 2;
+
     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);
+      // Do not assign numbers to parallel move instructions.
+      if (!current->IsParallelMove()) {
+        instructions_.Add(current);
+        current->set_lifetime_position(pos + 1);
         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.
     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++) {
-        ParallelMoveInstr* move = new ParallelMoveInstr();
+        // 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();
+        ParallelMoveInstr* move =
+          CreateParallelMoveBefore(last, last->lifetime_position() - 1);
+
         // 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);
       }
     }
   }
 }
 
 
+Instruction* FlowGraphAllocator::InstructionAt(intptr_t pos) {
+  return instructions_[pos >> 1];

[srdjan, 2012/07/22 23:27:33]

pos / 2 is clearer, IMHO.

[Vyacheslav Egorov (Google), 2012/07/24 12:26:42]

Done.

+}
+
+
+bool FlowGraphAllocator::IsBlockEntry(intptr_t pos) {
+  return InstructionAt(pos)->IsBlockEntry();
+}
+
+
+static UsePosition* FirstUseAfter(UsePosition* use, intptr_t after) {
+  while ((use != NULL) && (use->pos() < after)) {
+    use = use->next();
+  }
+  return use;
+}
+
+
+Location AllocationFinger::FirstHint() {
+  UsePosition* use = first_hinted_use_;
+
+  while (use != NULL) {
+    if (use->HasHint()) return use->hint();
+    use = use->next();
+  }
+
+  return Location::NoLocation();
+}
+
+
+UsePosition* AllocationFinger::FirstRegisterUse(intptr_t after) {
+  for (UsePosition* use = FirstUseAfter(first_register_use_, after);
+       use != NULL;
+       use = use->next()) {
+    Location* loc = use->location_slot();
+    if ((loc != NULL) &&
+        loc->IsUnallocated() &&
+        (loc->policy() == Location::kRequiresRegister)) {
+      first_register_use_ = use;
+      return use;
+    }
+  }
+  return NULL;
+}
+
+
+UsePosition* AllocationFinger::FirstRegisterBeneficialUse(intptr_t after) {
+  for (UsePosition* use = FirstUseAfter(first_register_beneficial_use_, after);
+       use != NULL;
+       use = use->next()) {
+    Location* loc = use->location_slot();
+    if ((loc != NULL) &&
+        (loc->IsRegister() ||
+         (loc->IsUnallocated() && loc->IsRegisterBeneficial()))) {
+      first_register_beneficial_use_ = use;
+      return use;
+    }
+  }
+  return NULL;
+}
+
+
 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()) {
     return this->start();
   }
   return kIllegalPosition;
 }
 
 
 static intptr_t FirstIntersection(UseInterval* a, UseInterval* u) {
   while (a != NULL && u != NULL) {
     const intptr_t pos = a->Intersect(u);
     if (pos != kIllegalPosition) return pos;
 
     if (a->start() < u->start()) {
-      a = a->next_allocated();
+      a = a->next();
     } else {
       u = u->next();
     }
   }
 
   return kMaxPosition;
 }
 
 
-static Location LookAheadForHint(UseInterval* interval) {
-  UsePosition* use = interval->first_use();
-
-  while (use != NULL) {
-    if (use->HasHint()) return use->hint();
-    use = use->next();
-  }
-
-  return Location::NoLocation();
+LiveRange* LiveRange::MakeTemp(intptr_t pos, Location* location_slot) {
+  UNREACHABLE();
+  return NULL;
 }
 
 
-bool FlowGraphAllocator::AllocateFreeRegister(UseInterval* unallocated) {
+LiveRange* LiveRange::SplitAt(intptr_t split_pos) {
+  if (Start() == split_pos) return this;
+
+  // Ranges can only be connected by parallel moves.
+  split_pos = ToParallelMove(split_pos);
+
+  UseInterval* interval = finger_.first_pending_use_interval();
+  ASSERT(interval->start() < split_pos);
+
+  // Corner case. We need to start over to find previous interval.
+  if (interval->start() == split_pos) interval = first_use_interval_;
+
+  UseInterval* last_before_split = NULL;
+  while (interval->end() <= split_pos) {
+    last_before_split = interval;
+    interval = interval->next();
+  }
+
+  const bool split_at_start = (interval->start() == split_pos);
+
+  UseInterval* first_after_split = interval;
+  if (!split_at_start && interval->Contains(split_pos)) {
+    first_after_split = new UseInterval(split_pos,
+                                        interval->end(),
+                                        interval->next());
+    interval->end_ = split_pos;
+    interval->next_ = first_after_split;
+    last_before_split = interval;
+  }
+
+  ASSERT(last_before_split->next() == first_after_split);
+  ASSERT(last_before_split->end() <= split_pos);
+  ASSERT(split_pos <= first_after_split->start());
+
+  UsePosition* last_use_before_split = NULL;
+  UsePosition* use = uses_;
+  if (split_at_start) {
+    while ((use != NULL) && (use->pos() < split_pos)) {
+      last_use_before_split = use;
+      use = use->next();
+    }
+  } else {
+    while ((use != NULL) && (use->pos() <= split_pos)) {
+      last_use_before_split = use;
+      use = use->next();
+    }
+  }
+  UsePosition* first_use_after_split = use;
+
+  if (last_use_before_split == NULL) {
+    uses_ = NULL;
+  } else {
+    last_use_before_split->set_next(NULL);
+  }
+
+  UseInterval* last_use_interval = (last_before_split == last_use_interval_) ?
+    first_after_split : last_use_interval_;
+  next_sibling_ = new LiveRange(vreg(),
+                                first_use_after_split,
+                                first_after_split,
+                                last_use_interval,
+                                next_sibling_);
+
+  TRACE_ALLOC(("  split sibling [%d, %d)\n",
+               next_sibling_->Start(), next_sibling_->End()));
+
+  // Split sibling can only start at a parallel move.
+  ASSERT(IsParallelMovePosition(next_sibling_->Start()));
+
+  last_use_interval_ = last_before_split;
+  last_use_interval_->next_ = NULL;
+  return next_sibling_;
+}
+
+
+LiveRange* FlowGraphAllocator::SplitBetween(LiveRange* range,
+                                            intptr_t from,
+                                            intptr_t to) {
+  // TODO(vegorov): select optimal split position based on loop structure.
+  TRACE_ALLOC(("split %d [%d, %d) between [%d, %d)\n",
+               range->vreg(), range->Start(), range->End(), from, to));
+  return range->SplitAt(to);
+}
+
+
+void FlowGraphAllocator::SpillBetween(LiveRange* range,
+                                      intptr_t from,
+                                      intptr_t to) {
+  ASSERT(from < to);
+  TRACE_ALLOC(("spill %d [%d, %d) between [%d, %d)\n",
+               range->vreg(), range->Start(), range->End(), from, to));
+  LiveRange* tail = range->SplitAt(from);
+
+  if (tail->Start() < to) {
+    // There is an intersection of tail and [from, to).
+    LiveRange* tail_tail = SplitBetween(tail, tail->Start(), to);
+    Spill(tail);
+    AddToUnallocated(tail_tail);
+  } else {
+    // No intersection between tail and [from, to).
+    AddToUnallocated(tail);
+  }
+}
+
+
+void FlowGraphAllocator::SpillAfter(LiveRange* range, intptr_t from) {
+  TRACE_ALLOC(("spill %d [%d, %d) after %d\n",
+               range->vreg(), range->Start(), range->End(), from));
+  LiveRange* tail = range->SplitAt(from);
+  Spill(tail);
+}
+
+
+intptr_t FlowGraphAllocator::AllocateSpillSlotFor(LiveRange* range) {
+  for (intptr_t i = 0; i < spill_slots_.length(); i++) {
+    if (spill_slots_[i] <= range->Start()) {
+      return i;
+    }
+  }
+  spill_slots_.Add(0);
+  return spill_slots_.length() - 1;
+}
+
+
+void FlowGraphAllocator::Spill(LiveRange* range) {
+  const intptr_t spill_index = AllocateSpillSlotFor(range);
+  ASSERT(spill_slots_[spill_index] < range->Start());
+  spill_slots_[spill_index] = range->End();
+  range->set_assigned_location(Location::SpillSlot(spill_index));
+  ConvertAllUses(range);
+}
+
+
+intptr_t FlowGraphAllocator::FirstIntersectionWithAllocated(
+  Register reg, LiveRange* unallocated) {
+  intptr_t intersection = kMaxPosition;
+  for (intptr_t i = 0; i < cpu_regs_[reg].length(); i++) {
+    LiveRange* allocated = cpu_regs_[reg][i];
+    if (allocated == NULL) continue;
+
+    UseInterval* allocated_head =
+      allocated->finger()->first_pending_use_interval();
+    if (allocated_head->start() >= intersection) continue;
+
+    const intptr_t pos = FirstIntersection(
+      unallocated->finger()->first_pending_use_interval(),
+      allocated_head);
+    if (pos < intersection) intersection = pos;
+  }
+  return intersection;
+}
+
+
+
+bool FlowGraphAllocator::AllocateFreeRegister(LiveRange* unallocated) {
   Register candidate = kNoRegister;
   intptr_t free_until = 0;
 
   // If hint is available try hint first.
-  // TODO(vegorov): ensure that phis are hinted on the backedge.
-  Location hint = LookAheadForHint(unallocated);
+  // TODO(vegorov): ensure that phis are hinted on the back edge.
+  Location hint = unallocated->finger()->FirstHint();
   if (!hint.IsInvalid()) {
     ASSERT(hint.IsRegister());
 
-    if (cpu_regs_[hint.reg()] != kPermanentlyBlocked) {
-      free_until = FirstIntersection(cpu_regs_[hint.reg()], unallocated);
+    if (!blocked_cpu_regs_[hint.reg()]) {
+      free_until = FirstIntersectionWithAllocated(hint.reg(), unallocated);
       candidate = hint.reg();
     }
 
     TRACE_ALLOC(("found hint %s for %d: free until %d\n",
                  hint.Name(), unallocated->vreg(), free_until));
   }
 
   if (free_until != kMaxPosition) {
-    for (int reg = 0; reg < kNumberOfCpuRegisters; ++reg) {
-      if (cpu_regs_[reg] == NULL) {
+    for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; ++reg) {
+      if (!blocked_cpu_regs_[reg] && cpu_regs_[reg].length() == 0) {
         candidate = static_cast<Register>(reg);
         free_until = kMaxPosition;
         break;
       }
     }
   }
 
   ASSERT(0 <= kMaxPosition);
   if (free_until != kMaxPosition) {
-    for (int reg = 0; reg < kNumberOfCpuRegisters; ++reg) {
-      if (cpu_regs_[reg] == kPermanentlyBlocked) continue;
-      if (reg == candidate) continue;
-
-      const intptr_t pos = FirstIntersection(cpu_regs_[reg], unallocated);
-
-      if (pos > free_until) {
+    for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; ++reg) {
+      if (blocked_cpu_regs_[reg] || (reg == candidate)) continue;
+
+      const intptr_t intersection =
+        FirstIntersectionWithAllocated(static_cast<Register>(reg), unallocated);
+
+      if (intersection > free_until) {
         candidate = static_cast<Register>(reg);
-        free_until = pos;
+        free_until = intersection;
         if (free_until == kMaxPosition) break;
       }
     }
   }
 
+  if (free_until != kMaxPosition) free_until = ToParallelMove(free_until);
+
   // All registers are blocked by active ranges.
-  if (free_until <= unallocated->start()) return false;
-
-  AssignFreeRegister(unallocated, candidate);
+  if (free_until <= unallocated->Start()) return false;
+
+  TRACE_ALLOC(("assigning free register %s to %d\n",
+               Location::RegisterLocation(candidate).Name(),
+               unallocated->vreg()));
+
+  if (free_until != kMaxPosition) {
+    // There was an intersection. Split unallocated.
+    TRACE_ALLOC(("  splitting at %d\n", free_until));
+    LiveRange* tail = unallocated->SplitAt(free_until);
+    AddToUnallocated(tail);
+  }
+
+  cpu_regs_[candidate].Add(unallocated);
+  unallocated->set_assigned_location(Location::RegisterLocation(candidate));
+
   return true;
 }
 
 
-UseInterval* UseInterval::Split(intptr_t pos) {
-  if (pos == start()) return this;
-  ASSERT(Contains(pos));
-  UseInterval* tail = new UseInterval(vreg(), pos, end(), next());
-
-  UsePosition* use = uses_;
-  while (use != NULL && use->pos() <= pos) {
-    use = use->next();
-  }
-
-  tail->uses_ = use;
-
-  end_ = pos;
-
-  return tail;
-}
-
-
-void FlowGraphAllocator::AssignFreeRegister(UseInterval* unallocated,
-                                            Register reg) {
-  TRACE_ALLOC(("assigning free register %s to %d\n",
+void FlowGraphAllocator::AllocateAnyRegister(LiveRange* unallocated) {
+  UsePosition* register_use =
+    unallocated->finger()->FirstRegisterUse(unallocated->Start());
+  if (register_use == NULL) {
+    Spill(unallocated);
+    return;
+  }
+
+  Register candidate = kNoRegister;
+  intptr_t free_until = 0;
+  intptr_t blocked_at = kMaxPosition;
+
+  for (int reg = 0; reg < kNumberOfCpuRegisters; ++reg) {
+    if (blocked_cpu_regs_[reg]) continue;
+    if (UpdateFreeUntil(static_cast<Register>(reg),
+                        unallocated,
+                        &free_until,
+                        &blocked_at)) {
+      candidate = static_cast<Register>(reg);
+    }
+  }
+
+  if (free_until < register_use->pos()) {
+    // Can't acquire free register. Spill until we really need one.
+    ASSERT(unallocated->Start() < ToParallelMove(register_use->pos()));
+    SpillBetween(unallocated, unallocated->Start(), register_use->pos());
+    return;
+  }
+
+  if (blocked_at < unallocated->End()) {
+    LiveRange* tail = SplitBetween(unallocated,
+                                   unallocated->Start(),
+                                   blocked_at);
+    AddToUnallocated(tail);
+  }
+
+  AssignBlockedRegister(unallocated, candidate);
+}
+
+
+bool FlowGraphAllocator::UpdateFreeUntil(Register reg,
+                                         LiveRange* unallocated,
+                                         intptr_t* cur_free_until,
+                                         intptr_t* cur_blocked_at) {
+  intptr_t free_until = kMaxPosition;
+  intptr_t blocked_at = kMaxPosition;
+  const intptr_t start = unallocated->Start();
+
+  for (intptr_t i = 0; i < cpu_regs_[reg].length(); i++) {
+    LiveRange* allocated = cpu_regs_[reg][i];
+
+    UseInterval* first_pending_use_interval =
+      allocated->finger()->first_pending_use_interval();
+    if (first_pending_use_interval->Contains(start)) {
+      // This is an active interval.
+      if (allocated->vreg() <= 0) {
+        // This register blocked by an interval that
+        // can't be spilled.
+        return false;
+      }
+
+      const UsePosition* use =
+        allocated->finger()->FirstRegisterBeneficialUse(unallocated->Start());
+
+      if ((use != NULL) && ((use->pos() - start) <= 1)) {
+        // This register is blocked by interval that is used
+        // as register in the current instruction and can't
+        // be spilled.
+        return false;
+      }
+
+      const intptr_t use_pos = (use != NULL) ? use->pos()
+                                             : allocated->End();
+
+      if (use_pos < free_until) free_until = use_pos;
+    } else {
+      // This is inactive interval.
+      const intptr_t intersection = FirstIntersection(
+        first_pending_use_interval, unallocated->first_use_interval());
+      if (intersection != kMaxPosition) {
+        if (intersection < free_until) free_until = intersection;
+        if (allocated->vreg() == kNoVirtualRegister) blocked_at = intersection;
+      }
+    }
+
+    if (free_until <= *cur_free_until) {
+      return false;
+    }
+  }
+
+  ASSERT(free_until > *cur_free_until);
+  *cur_free_until = free_until;
+  *cur_blocked_at = blocked_at;
+  return true;
+}
+
+
+void FlowGraphAllocator::RemoveEvicted(Register reg, intptr_t first_evicted) {
+  intptr_t to = first_evicted;
+  intptr_t from = first_evicted + 1;
+  while (from < cpu_regs_[reg].length()) {
+    LiveRange* allocated = cpu_regs_[reg][from++];
+    if (allocated != NULL) cpu_regs_[reg][to++] = allocated;
+  }
+  cpu_regs_[reg].TruncateTo(to);
+}
+
+
+void FlowGraphAllocator::AssignBlockedRegister(LiveRange* unallocated,
+                                               Register reg) {
+  TRACE_ALLOC(("assigning blocked register %s to live range %d\n",
                Location::RegisterLocation(reg).Name(),
                unallocated->vreg()));
 
-  UseInterval* a = cpu_regs_[reg];
-  if (a == NULL) {
-    // Register is completely free.
-    cpu_regs_[reg] = unallocated;
+  intptr_t first_evicted = -1;
+  for (intptr_t i = cpu_regs_[reg].length() - 1; i >= 0; i--) {
+    LiveRange* allocated = cpu_regs_[reg][i];
+    if (allocated->vreg() < 0) continue;  // Can't be evicted.
+    if (EvictIntersection(allocated,
+                          unallocated)) {
+      cpu_regs_[reg][i] = NULL;
+      first_evicted = i;
+    }
+  }
+
+  // Remove evicted ranges from the array.
+  if (first_evicted != -1) RemoveEvicted(reg, first_evicted);
+
+  cpu_regs_[reg].Add(unallocated);
+  unallocated->set_assigned_location(Location::RegisterLocation(reg));
+}
+
+
+bool FlowGraphAllocator::EvictIntersection(LiveRange* allocated,
+                                           LiveRange* unallocated) {
+  UseInterval* first_unallocated =
+    unallocated->finger()->first_pending_use_interval();
+  const intptr_t intersection = FirstIntersection(
+    allocated->finger()->first_pending_use_interval(),
+    first_unallocated);
+  if (intersection == kMaxPosition) return false;
+
+  const intptr_t spill_position = first_unallocated->start();
+  UsePosition* use = allocated->finger()->FirstRegisterUse(spill_position);
+  if (use == NULL) {
+    // No register uses after this point.
+    SpillAfter(allocated, spill_position);
+  } else {
+    const intptr_t restore_position =
+      (spill_position < intersection) ? MinPosition(intersection, use->pos())
+                                      : use->pos();
+
+    SpillBetween(allocated, spill_position, restore_position);
+  }
+
+  return true;
+}
+
+
+MoveOperands* FlowGraphAllocator::AddMoveAt(intptr_t pos,
+                                            Location to,
+                                            Location from) {
+  ASSERT(IsParallelMovePosition(pos));
+  Instruction* instr = InstructionAt(pos);
+  ASSERT(!instr->IsBlockEntry());
+  return CreateParallelMoveBefore(instr, pos)->AddMove(to, from);
+}
+
+
+void FlowGraphAllocator::ConvertUseTo(UsePosition* use, Location loc) {
+  ASSERT(use->location_slot() != NULL);
+  Location* slot = use->location_slot();
+  ASSERT(slot->IsUnallocated());
+  ASSERT((slot->policy() == Location::kRequiresRegister) ||
+         (slot->policy() == Location::kPrefersRegister) ||
+         (slot->policy() == Location::kAny));
+  TRACE_ALLOC(("  use at %d converted to %s\n", use->pos(), loc.Name()));
+  *slot = loc;
+}
+
+
+void FlowGraphAllocator::ConvertAllUses(LiveRange* range) {
+  if (range->vreg() == kNoVirtualRegister) return;
+  TRACE_ALLOC(("range [%d, %d) for v%d has been allocated to %s:\n",
+               range->Start(),
+               range->End(),
+               range->vreg(),
+               range->assigned_location().Name()));
+  ASSERT(!range->assigned_location().IsInvalid());
+  const Location loc = range->assigned_location();
+  for (UsePosition* use = range->first_use(); use != NULL; use = use->next()) {
+    ConvertUseTo(use, loc);
+  }
+}
+
+
+bool AllocationFinger::Advance(const intptr_t start) {
+  UseInterval* a = first_pending_use_interval_;
+  while (a != NULL && a->end() <= start) a = a->next();
+  first_pending_use_interval_ = a;
+  if (first_pending_use_interval_ == NULL) {
+    return true;
+  }
+  return false;
+}
+
+
+void FlowGraphAllocator::AdvanceActiveIntervals(const intptr_t start) {
+  for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
+    if (cpu_regs_[reg].length() == 0) continue;
+
+    intptr_t first_evicted = -1;
+    for (intptr_t i = cpu_regs_[reg].length() - 1; i >= 0; i--) {
+      LiveRange* range = cpu_regs_[reg][i];
+      if (range->finger()->Advance(start)) {
+        ConvertAllUses(range);
+        cpu_regs_[reg][i] = NULL;
+        first_evicted = i;
+      }
+    }
+
+    if (first_evicted != -1) {
+      RemoveEvicted(static_cast<Register>(reg), first_evicted);
+    }
+  }
+}
+
+
+void AllocationFinger::Initialize(LiveRange* range) {
+  first_pending_use_interval_ = range->first_use_interval();
+  first_register_use_ = range->first_use();
+  first_register_beneficial_use_ = range->first_use();
+  first_hinted_use_ = range->first_use();
+}
+
+
+static inline bool ShouldBeAllocatedBefore(LiveRange* a, LiveRange* b) {
+  return a->Start() <= b->Start();
+}
+
+
+void FlowGraphAllocator::AddToUnallocated(LiveRange* range) {
+  range->finger()->Initialize(range);
+
+  if (unallocated_.is_empty()) {
+    unallocated_.Add(range);
     return;
   }
 
-  UseInterval* u = unallocated;
-  ASSERT(u->start() < a->start());  // Register is free.
-  cpu_regs_[reg] = u;
-  if (u->next() == NULL || u->next()->start() >= a->start()) {
-    u->set_next_allocated(a);
-  }
-
-  while (a != NULL && u != NULL) {
-    const intptr_t pos = a->Intersect(u);
-    if (pos != kIllegalPosition) {
-      // TODO(vegorov): split live ranges might require control flow resolution
-      // which is not implemented yet.
-      builder_->Bailout("ssa allocator: control flow resolution required");
-
-      TRACE_ALLOC(("  splitting at %d\n", pos));
-      // Reached intersection
-      UseInterval* tail = u->Split(pos);
-      AddToUnallocated(tail);
-      ASSERT(tail == u || u->next_allocated() == a);
+  for (intptr_t i = unallocated_.length() - 1; i >= 0; i--) {
+    if (ShouldBeAllocatedBefore(range, unallocated_[i])) {
+      unallocated_.InsertAt(i + 1, range);
       return;
     }
-
-    if (a->start() < u->start()) {
-      if (a->next_allocated() == NULL) {
-        a->set_next_allocated(u);
-        break;
-      }
-
-      UseInterval* next = a->next_allocated();
-      if (next->start() > u->start()) {
-        a->set_next_allocated(u);
-        u->set_next_allocated(next);
-      }
-
-      a = next;
-    } else {
-      UseInterval* next = u->next();
-
-      if (next == NULL || next->start() >= a->start()) {
-        u->set_next_allocated(a);
-      }
-      u = next;
-    }
-  }
-}
-
-
-static void InsertMoveBefore(Instruction* instr, Location to, Location from) {
-  Instruction* prev = instr->previous();
-  ParallelMoveInstr* move = prev->AsParallelMove();
-  if (move == NULL) {
-    move = new ParallelMoveInstr();
-    move->set_next(prev->next());
-    prev->set_next(move);
-    move->next()->set_previous(move);
-    move->set_previous(prev);
-  }
-  move->AddMove(to, from);
-}
-
-
-void UsePosition::AssignLocation(Location loc) {
-  if (location_slot_ == NULL) return;
-
-  if (location_slot_->IsUnallocated()) {
-    if (location_slot_->policy() == Location::kSameAsFirstInput) {
-      Instruction* instr = this->instr();
-      LocationSummary* locs = instr->locs();
-      if (!locs->in(0).IsUnallocated()) {
-        InsertMoveBefore(instr, loc, locs->in(0));
-      }
-      locs->set_in(0, loc);
-    }
-    TRACE_ALLOC(("  use at %d converted to %s\n", pos(), loc.Name()));
-    *location_slot_ = loc;
-  } else if (location_slot_->IsRegister()) {
-    InsertMoveBefore(this->instr(), *location_slot_, loc);
-  }
-}
-
-
-void FlowGraphAllocator::FinalizeInterval(UseInterval* interval, Location loc) {
-  if (interval->vreg() == kNoVirtualRegister) return;
-
-  TRACE_ALLOC(("assigning location %s to interval [%d, %d)\n", loc.Name(),
-               interval->start(), interval->end()));
-
-  for (UsePosition* use = interval->first_use();
-       use != NULL && use->pos() <= interval->end();
-       use = use->next()) {
-    use->AssignLocation(loc);
-  }
-}
-
-
-void FlowGraphAllocator::AdvanceActiveIntervals(const intptr_t start) {
-  for (int reg = 0; reg < kNumberOfCpuRegisters; reg++) {
-    if (cpu_regs_[reg] == NULL) continue;
-    if (cpu_regs_[reg] == kPermanentlyBlocked) continue;
-
-    UseInterval* a = cpu_regs_[reg];
-    while (a != NULL && a->end() <= start) {
-      FinalizeInterval(a,
-                       Location::RegisterLocation(static_cast<Register>(reg)));
-      a = a->next_allocated();
-    }
-
-    cpu_regs_[reg] = a;
-  }
-}
-
-
-static inline bool ShouldBeAllocatedBefore(UseInterval* a, UseInterval* b) {
-  return a->start() <= b->start();
-}
-
-
-void FlowGraphAllocator::AddToUnallocated(UseInterval* chain) {
-  if (unallocated_.is_empty()) {
-    unallocated_.Add(chain);
-    return;
-  }
-
-  for (intptr_t i = unallocated_.length() - 1; i >= 0; i--) {
-    if (ShouldBeAllocatedBefore(chain, unallocated_[i])) {
-      unallocated_.InsertAt(i + 1, chain);
-      return;
-    }
-  }
-  unallocated_.InsertAt(0, chain);
+  }
+  unallocated_.InsertAt(0, range);
 }
 
 
 bool FlowGraphAllocator::UnallocatedIsSorted() {
   for (intptr_t i = unallocated_.length() - 1; i >= 1; i--) {
-    UseInterval* a = unallocated_[i];
-    UseInterval* b = unallocated_[i - 1];
+    LiveRange* a = unallocated_[i];
+    LiveRange* b = unallocated_[i - 1];
     if (!ShouldBeAllocatedBefore(a, b)) return false;
   }
   return true;
 }
 
 
 void FlowGraphAllocator::AllocateCPURegisters() {
   ASSERT(UnallocatedIsSorted());
 
+  for (intptr_t i = 0; i < kNumberOfCpuRegisters; i++) {
+    if (cpu_regs_[i].length() == 1) {
+      LiveRange* range = cpu_regs_[i][0];
+      range->finger()->Initialize(range);
+    }
+  }
+
   while (!unallocated_.is_empty()) {
-    UseInterval* range = unallocated_.Last();
+    LiveRange* range = unallocated_.Last();
     unallocated_.RemoveLast();
-    const intptr_t start = range->start();
-    TRACE_ALLOC(("Processing interval chain for vreg %d starting at %d\n",
+    const intptr_t start = range->Start();
+    TRACE_ALLOC(("Processing live range for vreg %d starting at %d\n",
                  range->vreg(),
                  start));
 
     // TODO(vegorov): eagerly spill liveranges without register uses.
     AdvanceActiveIntervals(start);
 
     if (!AllocateFreeRegister(range)) {
-      builder_->Bailout("ssa allocator: spilling required");
-      return;
+      AllocateAnyRegister(range);
     }
   }
 
   // All allocation decisions were done.
   ASSERT(unallocated_.is_empty());
 
   // Finish allocation.
   AdvanceActiveIntervals(kMaxPosition);
   TRACE_ALLOC(("Allocation completed\n"));
 }
 
 
+void FlowGraphAllocator::ConnectSplitSiblings(LiveRange* range,
+                                              BlockEntryInstr* source_block,
+                                              BlockEntryInstr* target_block) {
+  if (range->next_sibling() == NULL) {
+    // Nothing to connect. The whole range was allocated to the same location.
+    TRACE_ALLOC(("range %d has no siblings\n", range->vreg()));
+    return;
+  }
+
+  const intptr_t source_pos = source_block->end_pos() - 1;
+  ASSERT(IsInstructionPosition(source_pos));
+
+  const intptr_t target_pos = target_block->start_pos();
+
+  Location target;
+  Location source;
+
+#ifdef DEBUG
+  LiveRange* source_cover = NULL;
+  LiveRange* target_cover = NULL;
+#endif
+
+  while ((range != NULL) && (source.IsInvalid() || target.IsInvalid())) {
+    if (range->CanCover(source_pos)) {
+      ASSERT(source.IsInvalid());
+      source = range->assigned_location();
+#ifdef DEBUG
+      source_cover = range;
+#endif
+    }
+    if (range->CanCover(target_pos)) {
+      ASSERT(target.IsInvalid());
+      target = range->assigned_location();
+#ifdef DEBUG
+      target_cover = range;
+#endif
+    }
+
+    range = range->next_sibling();
+  }
+
+  TRACE_ALLOC(("connecting [%d, %d) [%s] to [%d, %d) [%s]\n",
+               source_cover->Start(), source_cover->End(), source.Name(),
+               target_cover->Start(), target_cover->End(), target.Name()));
+
+  // Siblings were allocated to the same register.
+  if (source.Equals(target)) return;
+
+  Instruction* last = source_block->last_instruction();
+  if (last->SuccessorCount() == 1) {
+    CreateParallelMoveBefore(last, last->lifetime_position() - 1)->
+      AddMove(target, source);
+  } else {
+    CreateParallelMoveAfter(target_block, target_block->start_pos())->
+      AddMove(target, source);
+  }
+}
+
+
+void FlowGraphAllocator::ResolveControlFlow() {
+  // Resolve linear control flow between touching split siblings
+  // inside basic blocks.
+  for (intptr_t vreg = 0; vreg < live_ranges_.length(); vreg++) {
+    LiveRange* range = live_ranges_[vreg];
+    if (range == NULL) continue;
+
+    while (range->next_sibling() != NULL) {
+      LiveRange* sibling = range->next_sibling();
+      if ((range->End() == sibling->Start()) &&
+          !range->assigned_location().Equals(sibling->assigned_location()) &&
+          !IsBlockEntry(range->End())) {
+        AddMoveAt(sibling->Start(),
+                  sibling->assigned_location(),
+                  range->assigned_location());
+      }
+      range = sibling;
+    }
+  }
+
+  // Resolve non-linear control flow across branches.
+  for (intptr_t i = 1; i < block_order_.length(); i++) {
+    BlockEntryInstr* block = block_order_[i];
+    BitVector* live = live_in_[block->postorder_number()];
+    for (BitVector::Iterator it(live); !it.Done(); it.Advance()) {
+      LiveRange* range = GetLiveRange(it.Current());
+      for (intptr_t j = 0; j < block->PredecessorCount(); j++) {
+        ConnectSplitSiblings(range, block->PredecessorAt(j), block);
+      }
+    }
+  }
+}
+
+
 void FlowGraphAllocator::AllocateRegisters() {
   GraphEntryInstr* entry = block_order_[0]->AsGraphEntry();
   ASSERT(entry != NULL);
 
   for (intptr_t i = 0; i < entry->start_env()->values().length(); i++) {
     if (entry->start_env()->values()[i]->IsUse()) {
       builder_->Bailout("ssa allocator: unsupported start environment");
     }
   }
 
   AnalyzeLiveness();
 
   BuildLiveRanges();
 
   if (FLAG_print_ssa_liveness) {
     DumpLiveness();
   }
 
   if (FLAG_trace_ssa_allocator) {
     PrintLiveRanges();
   }
 
   AllocateCPURegisters();
 
+  ResolveControlFlow();
+
   if (FLAG_trace_ssa_allocator) {
     OS::Print("-- ir after allocation -------------------------\n");
     FlowGraphPrinter printer(Function::Handle(), block_order_, true);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart