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

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.h"
@@ skipping 478 matching lines @@
 #endif
 
   for (intptr_t i = 0; i < live_ranges_.length(); i++) {
     if (live_ranges_[i] != NULL) {
       live_ranges_[i]->Print();
     }
   }
 }
 
 
+// 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());
   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 whole 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());
     }
 
     // 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();
     }
 
+
+    // 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);
   }
 
   // Process incoming parameters and constants.  Do this after all other
   // instructions so that safepoints for all calls have already been found.
   GraphEntryInstr* graph_entry = flow_graph_.graph_entry();
   for (intptr_t i = 0; i < graph_entry->initial_definitions()->length(); i++) {
     Definition* defn = (*graph_entry->initial_definitions())[i];
     LiveRange* range = GetLiveRange(defn->ssa_temp_index());
     range->AddUseInterval(graph_entry->start_pos(), graph_entry->end_pos());
@@ skipping 148 matching lines @@
 void FlowGraphAllocator::ConnectIncomingPhiMoves(BlockEntryInstr* block) {
   // 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 = 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;
     for (intptr_t phi_idx = 0; phi_idx < phis->length(); phi_idx++) {
       PhiInstr* phi = (*phis)[phi_idx];
       if (phi == NULL) continue;
 
       const intptr_t vreg = phi->ssa_temp_index();
       ASSERT(vreg != -1);
 
       // Expected shape of live range:
       //
       //                 B
       //      phi        [--------
       //
       LiveRange* range = GetLiveRange(vreg);
       range->DefineAt(pos);  // Shorten live range.
 
+      if (is_loop_header) range->mark_loop_phi();
+
       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();
         ASSERT((goto_instr != NULL) && (goto_instr->HasParallelMove()));
         MoveOperands* move =
             goto_instr->parallel_move()->MoveOperandsAt(move_idx);
         move->set_dest(Location::PrefersRegister());
         range->AddUse(pos, move->dest_slot());
       }
 
@@ skipping 290 matching lines @@
     ASSERT(locs->in(0).Equals(Location::RequiresRegister()) ||
            locs->in(0).Equals(Location::RequiresXmmRegister()));
 
     // Create move that will copy value between input and output.
     locs->set_out(Location::RequiresRegister());
     MoveOperands* move = AddMoveAt(pos,
                                    Location::RequiresRegister(),
                                    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());
 
     // 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));
   } else {
@@ skipping 106 matching lines @@
 
 // Discover structural (reducible) loops nesting structure.
 void FlowGraphAllocator::DiscoverLoops() {
   // This algorithm relies on the assumption that we emit blocks in reverse
   // postorder, so postorder number can be used to identify loop nesting.
   //
   // TODO(vegorov): consider using a generic algorithm to correctly discover
   // 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];
     GotoInstr* goto_instr = block->last_instruction()->AsGoto();
     if (goto_instr != NULL) {
       JoinEntryInstr* successor = goto_instr->successor();
       if (successor->postorder_number() > i) {
         // This is back-edge.
         BlockInfo* successor_info = BlockInfoAt(successor->lifetime_position());
         ASSERT(successor_info->entry() == successor);
         if (!successor_info->is_loop_header() &&
             ((current_loop == NULL) ||
              (current_loop->entry()->postorder_number() >
                   successor_info->entry()->postorder_number()))) {
           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;
         }
       }
     }
 
     if (current_loop != NULL) {
       BlockInfo* current_info = BlockInfoAt(block->lifetime_position());
       if (current_info == current_loop) {
@@ skipping 286 matching lines @@
   } else {
     // No intersection between tail and [from, to).
     AddToUnallocated(tail);
   }
 }
 
 
 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);
 }
 
 
 void FlowGraphAllocator::AllocateSpillSlotFor(LiveRange* range) {
   ASSERT(range->spill_slot().IsInvalid());
 
   intptr_t idx = 0;
   for (; idx < spill_slots_.length(); idx++) {
@@ skipping 132 matching lines @@
   }
 
   registers_[candidate].Add(unallocated);
   unallocated->set_assigned_location(
       MakeRegisterLocation(candidate, unallocated->representation()));
 
   return true;
 }
 
 
+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;
   }
 
   intptr_t candidate = kNoRegister;
   intptr_t free_until = 0;
   intptr_t blocked_at = kMaxPosition;
 
   for (int reg = 0; reg < NumberOfRegisters(); ++reg) {
     if (blocked_registers_[reg]) continue;
     if (UpdateFreeUntil(reg, unallocated, &free_until, &blocked_at)) {
       candidate = reg;
     }
   }
 
-  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;
   }
 
   TRACE_ALLOC(OS::Print("assigning blocked register "));
   TRACE_ALLOC(MakeRegisterLocation(candidate, Location::kDouble).Print());
   TRACE_ALLOC(OS::Print(" to live range %"Pd" until %"Pd"\n",
                         unallocated->vreg(), blocked_at));
 
   if (blocked_at < unallocated->End()) {
@@ skipping 577 matching lines @@
     OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(flow_graph_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart