When selecting an optimal position for SplitBetween(from, to) ensure:

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 399 matching lines @@
 
   for (intptr_t i = 0; i < live_ranges_.length(); i++) {
     if (live_ranges_[i] != NULL) {
       live_ranges_[i]->Print();
     }
   }
 }
 
 
 void FlowGraphAllocator::BuildLiveRanges() {
-  NumberInstructions();
-
   const intptr_t block_count = postorder_.length();
   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 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());
@@ skipping 461 matching lines @@
 // 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];
+    BlockInfo* info = new BlockInfo(block);
 
     instructions_.Add(block);
+    block_info_.Add(info);
     block->set_start_pos(pos);
     block->set_lifetime_position(pos);
     pos += 2;
 
     for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
       Instruction* current = it.Current();
       // Do not assign numbers to parallel move instructions.
       if (!current->IsParallelMove()) {
         instructions_.Add(current);
+        block_info_.Add(info);
         current->set_lifetime_position(pos);
         pos += 2;
       }
     }
     block->set_end_pos(pos);
   }
 
   // Create parallel moves in join predecessors.  This must be done after
   // all instructions are numbered.
   for (intptr_t i = block_count - 1; i >= 0; i--) {
@@ skipping 16 matching lines @@
         // Populate the ParallelMove with empty moves.
         for (intptr_t j = 0; j < phi_count; j++) {
           move->AddMove(Location::NoLocation(), Location::NoLocation());
         }
       }
     }
   }
 }
 
 
+static bool IsNestedLoop(BlockInfo* outer, BlockInfo* inner) {

[srdjan, 2012/08/02 20:04:37]

Can you make checks a little bit more robust since the method is outside the
context where it is currently used. E.g.:
ASSERT(outer == NULL || outer->is_loop_info())

Shouldn't it say false if there is no outer loop (outer == NULL) or should the
function be called IsLoop?

Do you want to check the postorder_number (as you do for detecting back-edges)
or block_id?

[Vyacheslav Egorov (Google), 2012/08/03 06:29:00]

Inlined function back into DiscoverLoops to avoid confusion.

It was just checking that a new backedge does not exit the current loop to
filter out cases where loops are improperly nested.

+  return (outer == NULL) ||
+      (outer->entry()->block_id() < inner->entry()->block_id());
+}
+
+
+// Discover structural (reducible) loops nesting structure.

[srdjan, 2012/08/02 20:04:37]

Aren't all Dart generated loops reducible?

[Vyacheslav Egorov (Google), 2012/08/03 06:29:00]

AFAIK you can generate an irreducible control flow with 

switch (a) {
  case 1: break 2;
  case 2: break 1;
}

if it still compiles.

[srdjan, 2012/08/03 21:40:49]

You cannot do this. The break goes only  to outer enclosing structure (loop,
switch, etc).

+void FlowGraphAllocator::DiscoverLoops() {
+  // TODO(vegorov): consider using a generic algorithm to correctly discover
+  // both headers of reducible and irreducible loops.
+  BlockInfo* current_loop = NULL;
+
+  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() &&
+            IsNestedLoop(current_loop, successor_info)) {
+          ASSERT(successor_info != current_loop);
+
+          successor_info->mark_loop_header();
+          // 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) {
+        ASSERT(current_loop->is_loop_header());
+        current_loop = current_info->loop();
+      } else {
+        current_info->set_loop(current_loop);
+      }
+    }
+  }
+}
+
+
 Instruction* FlowGraphAllocator::InstructionAt(intptr_t pos) const {
   return instructions_[pos / 2];
 }
 
 
+BlockInfo* FlowGraphAllocator::BlockInfoAt(intptr_t pos) const {
+  return block_info_[pos / 2];
+}
+
+
 bool FlowGraphAllocator::IsBlockEntry(intptr_t pos) const {
   return IsInstructionStartPosition(pos) && InstructionAt(pos)->IsBlockEntry();
 }
 
 
 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();
@@ skipping 166 matching lines @@
 
   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));
 
-  // Prefer spliting at instruction starts if possible.
-  if (from < ToInstructionStart(to)) {
-    to = ToInstructionStart(to);
+  intptr_t split_pos = kIllegalPosition;
+
+  BlockInfo* split_block = BlockInfoAt(to);
+  if (from < split_block->entry()->lifetime_position()) {
+    // Interval [from, to) spans multiple blocks.
+
+    // If it covers any last block is inside a loop prefer splitting at
+    // loops header if possible.

[srdjan, 2012/08/02 20:04:37]

Please make comment easier to read.

[Vyacheslav Egorov (Google), 2012/08/03 06:29:00]

Done.

+    BlockInfo* loop_header = split_block->loop();
+    while ((loop_header != NULL) &&
+           (from < loop_header->entry()->lifetime_position())) {
+      split_block = loop_header;
+      loop_header = loop_header->loop();
+    }
+
+    // Split at block's start.
+    split_pos = split_block->entry()->lifetime_position();
+  } else {
+    // Interval [from, to) is contained inside a single block.
+
+    // Split at position corresponding to the end of the previous
+    // instruction.
+    split_pos = ToInstructionStart(to) - 1;
   }
 
-  // Splitting at the end is not allowed as it produces an empty
-  // live range.
-  if (to == range->End()) to -= 1;
-  ASSERT(from <= to);
+  ASSERT((split_pos != kIllegalPosition) && (from < split_pos));
 
-  return range->SplitAt(to);
+  return range->SplitAt(split_pos);
 }
 
 
 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);
@@ skipping 160 matching lines @@
     }
   }
 
   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;
   }
 
+  TRACE_ALLOC(("assigning blocked register %s to live range %d until %d\n",
+               Location::RegisterLocation(candidate).Name(),
+               unallocated->vreg(),
+               blocked_at));
+
   if (blocked_at < unallocated->End()) {
     LiveRange* tail = SplitBetween(unallocated,
                                    unallocated->Start(),
                                    blocked_at);
     AddToUnallocated(tail);
   }
 
   AssignNonFreeRegister(unallocated, candidate);
 }
 
@@ skipping 61 matching lines @@
   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::AssignNonFreeRegister(LiveRange* unallocated,
                                                Register reg) {
-  TRACE_ALLOC(("assigning blocked register %s to live range %d\n",
-               Location::RegisterLocation(reg).Name(),
-               unallocated->vreg()));
-
   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)) {
-      ASSERT(allocated->End() <= unallocated->Start());
-      ConvertAllUses(allocated);
+      // If allocated was not spilled convert all pending uses.
+      if (allocated->assigned_location().IsRegister()) {
+        ASSERT(allocated->End() <= unallocated->Start());
+        ConvertAllUses(allocated);
+      }
       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));
@@ skipping 216 matching lines @@
   // Siblings were allocated to the same register.
   if (source.Equals(target)) return;
 
   // Values are eagerly spilled. Spill slot already contains appropriate value.
   if (target.IsStackSlot()) {
     ASSERT(parent->spill_slot().Equals(target));
     return;
   }
 
   Instruction* last = source_block->last_instruction();
-  if (last->SuccessorCount() == 1) {
+  if ((last->SuccessorCount() == 1) && !source_block->IsGraphEntry()) {
     ASSERT(last->IsGoto());
     last->AsGoto()->GetParallelMove()->AddMove(target, source);
   } else {
     target_block->GetParallelMove()->AddMove(target, source);
   }
 }
 
 
 void FlowGraphAllocator::ResolveControlFlow() {
   // Resolve linear control flow between touching split siblings
@@ skipping 47 matching lines @@
     }
   }
 }
 
 
 void FlowGraphAllocator::AllocateRegisters() {
   EliminateEnvironmentUses();
 
   AnalyzeLiveness();
 
+  NumberInstructions();
+
+  DiscoverLoops();
+
   BuildLiveRanges();
 
   if (FLAG_print_ssa_liveness) {
     DumpLiveness();
   }
 
   AllocateCPURegisters();
 
   ResolveControlFlow();
 
@@ skipping 12 matching lines @@
     OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(Function::Handle(), block_order_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart