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

runtime/vm/flow_graph_allocator.h

 // 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.
 
 #ifndef VM_FLOW_GRAPH_ALLOCATOR_H_
 #define VM_FLOW_GRAPH_ALLOCATOR_H_
 
 #include "vm/growable_array.h"
 #include "vm/intermediate_language.h"
 
 namespace dart {
 
 class AllocationFinger;
+class BlockInfo;
 class FlowGraphBuilder;
 class LiveRange;
 class UseInterval;
 class UsePosition;
 
 class FlowGraphAllocator : public ValueObject {
  public:
   FlowGraphAllocator(const GrowableArray<BlockEntryInstr*>& block_order,
                      FlowGraphBuilder* builder);
 
@@ skipping 42 matching lines @@
   // need value in the register until the end of instruction's body.
   // Register allocator can perform splitting of live ranges at any position.
   // An implicit ParallelMove will be inserted by ConnectSplitSiblings where
   // required to resolve data flow between split siblings when allocation
   // is finished.
   // For specific examples see comments inside ProcessOneInstruction.
   // Additionally creates parallel moves at the joins' predecessors
   // that will be used for phi resolution.
   void NumberInstructions();
   Instruction* InstructionAt(intptr_t pos) const;
+  BlockInfo* BlockInfoAt(intptr_t pos) const;
   bool IsBlockEntry(intptr_t pos) const;
 
+  // Discover structural (reducible) loops nesting structure.
+  // It will be used later in SplitBetween heuristic that selects an
+  // optimal splitting position.
+  void DiscoverLoops();
+
   LiveRange* GetLiveRange(intptr_t vreg);
   LiveRange* MakeLiveRangeForTemporary();
 
   // Visit instructions in the postorder and build live ranges for
   // all SSA values.
   void BuildLiveRanges();
   Instruction* ConnectOutgoingPhiMoves(BlockEntryInstr* block);
   void ProcessOneInstruction(BlockEntryInstr* block, Instruction* instr);
   void ConnectIncomingPhiMoves(BlockEntryInstr* block);
   void BlockLocation(Location loc, intptr_t pos);
@@ skipping 55 matching lines @@
   // Find a spill slot that can be used by the given live range.
   void AllocateSpillSlotFor(LiveRange* range);
 
   // Allocate the given live range to a spill slot.
   void Spill(LiveRange* range);
 
   // Spill the given live range from the given position onwards.
   void SpillAfter(LiveRange* range, intptr_t from);
 
   // Spill the given live range from the given position until some
-  // position preceeding the to position.
+  // position preceding the to position.
   void SpillBetween(LiveRange* range, intptr_t from, intptr_t to);
 
   MoveOperands* AddMoveAt(intptr_t pos, Location to, Location from);
 
   void PrintLiveRanges();
 
   // TODO(vegorov): this field is used only to call Bailout. Remove when
   // all bailouts are gone.
   FlowGraphBuilder* builder_;
 
   const GrowableArray<BlockEntryInstr*>& block_order_;
   const GrowableArray<BlockEntryInstr*>& postorder_;
 
+  // Mapping between lifetime positions and instructions.
   GrowableArray<Instruction*> instructions_;
 
+  // Mapping between lifetime positions and blocks containing them.
+  GrowableArray<BlockInfo*> block_info_;
+
   // Live-out sets for each block.  They contain indices of SSA values
   // that are live out from this block: that is values that were either
   // defined in this block or live into it and that are used in some
   // successor block.
   GrowableArray<BitVector*> live_out_;
 
   // Kill sets for each block.  They contain indices of SSA values that
   // are defined by this block.
   GrowableArray<BitVector*> kill_;
 
@@ skipping 27 matching lines @@
   // List of used spill slots. Contain positions after which spill slots
   // become free and can be reused for allocation.
   GrowableArray<intptr_t> spill_slots_;
 
   bool blocked_cpu_regs_[kNumberOfCpuRegisters];
 
   DISALLOW_COPY_AND_ASSIGN(FlowGraphAllocator);
 };
 
 
+// Additional information about a block that is not contained in a
+// block entry.
+class BlockInfo : public ZoneAllocated {
+ public:
+  explicit BlockInfo(BlockEntryInstr* entry)
+    : entry_(entry), loop_(NULL), is_loop_header_(false) {
+  }
+
+  BlockEntryInstr* entry() const { return entry_; }
+
+  // Returns true is this node is a header of a structural loop.
+  bool is_loop_header() const { return is_loop_header_; }
+
+  // Innermost reducible loop containing this node. Loop headers point to
+  // outer loop not to themselves.
+  BlockInfo* loop() const { return loop_; }
+
+  void mark_loop_header() { is_loop_header_ = true; }
+  void set_loop(BlockInfo* loop) {
+    ASSERT(loop_ == NULL);
+    ASSERT((loop == NULL) || loop->is_loop_header());
+    loop_ = loop;
+  }
+
+ private:
+  BlockEntryInstr* entry_;
+  BlockInfo* loop_;
+  bool is_loop_header_;
+
+  DISALLOW_COPY_AND_ASSIGN(BlockInfo);
+};
+
+
 // UsePosition represents a single use of an SSA value by some instruction.
 // It points to a location slot which either tells register allocator
 // where instruction expects the value (if slot contains a fixed location) or
 // asks register allocator to allocate storage (register or spill slot) for
 // this use with certain properties (if slot contains an unallocated location).
 class UsePosition : public ZoneAllocated {
  public:
   UsePosition(intptr_t pos, UsePosition* next, Location* location_slot)
       : pos_(pos), location_slot_(location_slot), next_(next) { }
 
@@ skipping 178 matching lines @@
 
   AllocationFinger finger_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_ALLOCATOR_H_