Try allocating loop phi into a register even if phi has only unconstrained uses but there are cheap…

runtime/vm/flow_graph_allocator.cc

Index: runtime/vm/flow_graph_allocator.cc
diff --git a/runtime/vm/flow_graph_allocator.cc b/runtime/vm/flow_graph_allocator.cc
index 0097c7283dcebd8960e124bbe81a437f1ae2cc97..f1de3a80e10df1f1b26e52da74ab26798cdcf7ff 100644
--- a/runtime/vm/flow_graph_allocator.cc
+++ b/runtime/vm/flow_graph_allocator.cc
@@ -496,6 +496,24 @@ void FlowGraphAllocator::PrintLiveRanges() {
 }
 
 
+// Returns true if all uses of the given range inside the given loop
+// have Any allocation policy.
+static bool HasOnlyUnconstrainedUsesInLoop(LiveRange* range,
+                                           BlockInfo* loop_header) {
+  const intptr_t boundary = loop_header->last_block()->end_pos();
+
+  UsePosition* use = range->first_use();
+  while ((use != NULL) && (use->pos() < boundary)) {
+    if (!use->location_slot()->Equals(Location::Any())) {
+      return false;
+    }
+    use = use->next();
+  }
+
+  return true;
+}
+
+
 void FlowGraphAllocator::BuildLiveRanges() {
   const intptr_t block_count = postorder_.length();
   ASSERT(postorder_.Last()->IsGraphEntry());
@@ -523,6 +541,18 @@ void FlowGraphAllocator::BuildLiveRanges() {
       current = current->previous();
     }
 
+
+    // Check if any values live into the loop can be spilled for free.
+    BlockInfo* block_info = BlockInfoAt(block->start_pos());
+    if (block_info->is_loop_header()) {
+      for (BitVector::Iterator it(live_in_[i]); !it.Done(); it.Advance()) {
+        LiveRange* range = GetLiveRange(it.Current());
+        if (HasOnlyUnconstrainedUsesInLoop(range, block_info)) {
+          range->MarkHasOnlyUnconstrainedUsesInLoop(block_info->loop_id());
+        }
+      }
+    }
+
     ConnectIncomingPhiMoves(block);
   }
 
@@ -691,6 +721,8 @@ void FlowGraphAllocator::ConnectIncomingPhiMoves(BlockEntryInstr* block) {
   // All uses are recorded at the start position in the block.
   const intptr_t pos = join->start_pos();
 
+  const intptr_t is_loop_header = join->loop_info() != NULL;

[Florian Schneider, 2012/11/08 02:05:36]

Move this down to the use.

[Vyacheslav Egorov (Google), 2012/11/08 02:13:43]

Done.

+
   ZoneGrowableArray<PhiInstr*>* phis = join->phis();
   if (phis != NULL) {
     intptr_t move_idx = 0;
@@ -709,6 +741,8 @@ void FlowGraphAllocator::ConnectIncomingPhiMoves(BlockEntryInstr* block) {
       LiveRange* range = GetLiveRange(vreg);
       range->DefineAt(pos);  // Shorten live range.
 
+      if (is_loop_header) range->mark_loop_phi();
+
       for (intptr_t pred_idx = 0; pred_idx < phi->InputCount(); pred_idx++) {
         BlockEntryInstr* pred = block->PredecessorAt(pred_idx);
         GotoInstr* goto_instr = pred->last_instruction()->AsGoto();
@@ -1019,9 +1053,9 @@ void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block,
                                    Location::Any());
 
     // Add uses to the live range of the input.
-    Value* input = current->InputAt(0);
+    Definition* input = current->InputAt(0)->definition();
     LiveRange* input_range =
-        GetLiveRange(input->definition()->ssa_temp_index());
+        GetLiveRange(input->ssa_temp_index());
     input_range->AddUseInterval(block->start_pos(), pos);
     input_range->AddUse(pos, move->src_slot());
 
@@ -1148,6 +1182,8 @@ void FlowGraphAllocator::DiscoverLoops() {
   // both headers of reducible and irreducible loops.
   BlockInfo* current_loop = NULL;
 
+  intptr_t loop_id = 0;  // All loop headers have a unique id.
+
   const intptr_t block_count = postorder_.length();
   for (intptr_t i = 0; i < block_count; i++) {
     BlockEntryInstr* block = postorder_[i];
@@ -1165,6 +1201,8 @@ void FlowGraphAllocator::DiscoverLoops() {
           ASSERT(successor_info != current_loop);
 
           successor_info->mark_loop_header();
+          successor_info->set_loop_id(loop_id++);
+          successor_info->set_last_block(block);
           // For loop header loop information points to the outer loop.
           successor_info->set_loop(current_loop);
           current_loop = successor_info;
@@ -1471,6 +1509,23 @@ void FlowGraphAllocator::SpillBetween(LiveRange* range,
 void FlowGraphAllocator::SpillAfter(LiveRange* range, intptr_t from) {
   TRACE_ALLOC(OS::Print("spill %"Pd" [%"Pd", %"Pd") after %"Pd"\n",
                         range->vreg(), range->Start(), range->End(), from));
+
+  // When spilling the value inside the loop check if this spill can
+  // be moved outside.
+  BlockInfo* block_info = BlockInfoAt(from);
+  if (block_info->is_loop_header() || (block_info->loop() != NULL)) {
+    BlockInfo* loop_header =
+        block_info->is_loop_header() ? block_info : block_info->loop();
+
+    if ((range->Start() <= loop_header->entry()->start_pos()) &&
+        RangeHasOnlyUnconstrainedUsesInLoop(range, loop_header->loop_id())) {
+      ASSERT(loop_header->entry()->start_pos() <= from);
+      from = loop_header->entry()->start_pos();
+      TRACE_ALLOC(OS::Print("  moved spill position to loop header %"Pd"\n",
+                            from));

[Florian Schneider, 2012/11/08 02:05:36]

Please make sure that this code is covered in our tests.

[Vyacheslav Egorov (Google), 2012/11/08 02:13:43]

Done.

+    }
+  }
+
   LiveRange* tail = range->SplitAt(from);
   Spill(tail);
 }
@@ -1623,10 +1678,67 @@ bool FlowGraphAllocator::AllocateFreeRegister(LiveRange* unallocated) {
 }
 
 
+bool FlowGraphAllocator::RangeHasOnlyUnconstrainedUsesInLoop(LiveRange* range,
+                                                             intptr_t loop_id) {
+  if (range->vreg() >= 0) {
+    return GetLiveRange(range->vreg())->HasOnlyUnconstrainedUsesInLoop(loop_id);
+  }
+  return false;
+}
+
+
+bool FlowGraphAllocator::IsCheapToEvictRegisterInLoop(BlockInfo* loop,
+                                                      int reg) {
+  const intptr_t loop_start = loop->entry()->start_pos();
+  const intptr_t loop_end = loop->last_block()->end_pos();
+
+  for (intptr_t i = 0; i < registers_[reg].length(); i++) {
+    LiveRange* allocated = registers_[reg][i];
+
+    UseInterval* interval = allocated->finger()->first_pending_use_interval();
+    if (interval->Contains(loop_start)) {
+      if (!RangeHasOnlyUnconstrainedUsesInLoop(allocated, loop->loop_id())) {
+        return false;
+      }
+    } else {

[Florian Schneider, 2012/11/08 02:05:36]

} else if (interval->start() < loop_end) {

[Vyacheslav Egorov (Google), 2012/11/08 02:13:43]

Done.

+      if (interval->start() < loop_end) {
+        return false;
+      }
+    }
+  }
+
+  return true;
+}
+
+
+bool FlowGraphAllocator::HasCheapEvictionCandidate(LiveRange* phi_range) {
+  ASSERT(phi_range->is_loop_phi());
+
+  BlockInfo* loop_header = BlockInfoAt(phi_range->Start());
+  ASSERT(loop_header->is_loop_header());
+  ASSERT(phi_range->Start() == loop_header->entry()->start_pos());
+
+  for (int reg = 0; reg < NumberOfRegisters(); ++reg) {

[Florian Schneider, 2012/11/08 02:05:36]

intptr_t?

[Vyacheslav Egorov (Google), 2012/11/08 02:13:43]

Done.

+    if (blocked_registers_[reg]) continue;
+    if (IsCheapToEvictRegisterInLoop(loop_header, reg)) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
+
 void FlowGraphAllocator::AllocateAnyRegister(LiveRange* unallocated) {
+  // If a loop phi has no register uses we might still want to allocate it

[Florian Schneider, 2012/11/08 02:05:36]

Please split this 4-line sentence into simpler phrases.

[Vyacheslav Egorov (Google), 2012/11/08 02:13:43]

Done.

+  // to the register to minimize amount of memory moves on the back edge
+  // especially if there is a register blocked by a range that can be
+  // cheaply evicated i.e. it has no register beneficial uses inside the

[Florian Schneider, 2012/11/08 02:05:36]

s/evicated/evicted/g

[Vyacheslav Egorov (Google), 2012/11/08 02:13:43]

Done.

+  // loop.
   UsePosition* register_use =
       unallocated->finger()->FirstRegisterUse(unallocated->Start());
-  if (register_use == NULL) {
+  if ((register_use == NULL) &&
+      !(unallocated->is_loop_phi() && HasCheapEvictionCandidate(unallocated))) {

[Florian Schneider, 2012/11/08 02:05:36]

Please make sure that this part is hit in our tests.

[Vyacheslav Egorov (Google), 2012/11/08 02:13:43]

Done.

     Spill(unallocated);
     return;
   }
@@ -1642,9 +1754,12 @@ void FlowGraphAllocator::AllocateAnyRegister(LiveRange* unallocated) {
     }
   }
 
-  if (free_until < register_use->pos()) {
+  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()));
+    ASSERT(unallocated->Start() < ToInstructionStart(register_use_pos));
     SpillBetween(unallocated, unallocated->Start(), register_use->pos());
     return;
   }