New linear scan allocator.

runtime/vm/flow_graph_allocator.h

Index: runtime/vm/flow_graph_allocator.h
diff --git a/runtime/vm/flow_graph_allocator.h b/runtime/vm/flow_graph_allocator.h
index 9622ed674c03c9a2b738b7a953156ac42aeac91b..4a0f26bd1b7521788b0fffc35de36d91051b9d20 100644
--- a/runtime/vm/flow_graph_allocator.h
+++ b/runtime/vm/flow_graph_allocator.h
@@ -10,9 +10,11 @@
 
 namespace dart {
 
+class AllocationFinger;
 class FlowGraphBuilder;
 class LiveRange;
 class UseInterval;
+class UsePosition;
 
 class FlowGraphAllocator : public ValueObject {
  public:
@@ -63,6 +65,8 @@ class FlowGraphAllocator : public ValueObject {
   // Additionally creates parallel moves at the joins' predecessors
   // that will be used for phi resolution.
   void NumberInstructions();
+  Instruction* InstructionAt(intptr_t pos);
+  bool IsBlockEntry(intptr_t pos);
 
   LiveRange* GetLiveRange(intptr_t vreg);
   void BuildLiveRanges();
@@ -71,8 +75,7 @@ class FlowGraphAllocator : public ValueObject {
   // Register use of the given virtual register at lifetime position use_pos.
   // If definition position is unknown then start of the block contaning
   // use_pos will be passed.
-  void UseValue(Instruction* instr,
-                intptr_t def_pos,  // Lifetime position for the definition.
+  void UseValue(intptr_t def_pos,  // Lifetime position for the definition.
                 intptr_t use_pos,  // Lifetime position for the use.
                 intptr_t vreg,
                 Location* loc,
@@ -80,23 +83,56 @@ class FlowGraphAllocator : public ValueObject {
 
   // Register definition of the given virtual register at lifetime position
   // def_pos.  Existing use interval will be shortened to start at def_pos.
-  void Define(Instruction* instr,
-              intptr_t def_pos,
+  void Define(intptr_t def_pos,
               intptr_t vreg,
               Location* loc);
 
-  void AddToUnallocated(UseInterval* chain);
+  void AddToUnallocated(LiveRange* range);
   void BlockLocation(Location loc, intptr_t pos);
 
-  bool AllocateFreeRegister(UseInterval* unallocated);
-  void AssignFreeRegister(UseInterval* unallocated, Register reg);
+  bool AllocateFreeRegister(LiveRange* unallocated);
+
+  void AllocateAnyRegister(LiveRange* unallocated);
+  bool UpdateFreeUntil(Register reg,
+                       LiveRange* unallocated,
+                       intptr_t* cur_free_until,
+                       intptr_t* cur_blocked_at);
+
+  void AssignBlockedRegister(LiveRange* unallocated, Register reg);
+
+  intptr_t FirstIntersectionWithAllocated(Register reg,
+                                          LiveRange* unallocated);
+  bool EvictIntersection(LiveRange* allocated, LiveRange* unallocated);
+
+  void RemoveEvicted(Register reg, intptr_t first_evicted);
 
-  void FinalizeInterval(UseInterval* interval, Location loc);
   void AdvanceActiveIntervals(const intptr_t start);
 
+  LiveRange* SplitBetween(LiveRange* range, intptr_t from, intptr_t to);
+
+  intptr_t AllocateSpillSlotFor(LiveRange* range);
+  void Spill(LiveRange* range);
+  void SpillAfter(LiveRange* range, intptr_t from);
+  void SpillBetween(LiveRange* range, intptr_t from, intptr_t to);
+
   bool UnallocatedIsSorted();
   void AllocateCPURegisters();
 
+  // Tell the use that it should load the value from the given location.
+  // If location slot for the use is flexible (unallocated) it will be updated
+  // with the given location. Otherwise a move will be scheduled from the given
+  // location to the location already stored in the slot.
+  void ConvertUseTo(UsePosition* use, Location loc);
+  void ConvertAllUses(LiveRange* range);
+
+
+  // Connect split siblings over non-linear control flow edges.
+  void ResolveControlFlow();
+  void ConnectSplitSiblings(LiveRange* range,
+                            BlockEntryInstr* source_block,
+                            BlockEntryInstr* target_block);
+
+
   // TODO(vegorov): this field is used only to call Bailout. Remove when
   // all bailouts are gone.
   FlowGraphBuilder* builder_;
@@ -104,6 +140,8 @@ class FlowGraphAllocator : public ValueObject {
   const GrowableArray<BlockEntryInstr*>& block_order_;
   const GrowableArray<BlockEntryInstr*>& postorder_;
 
+  GrowableArray<Instruction*> instructions_;
+
   // 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
@@ -127,14 +165,17 @@ class FlowGraphAllocator : public ValueObject {
 
   // Worklist for register allocator. Always maintained sorted according
   // to ShouldBeAllocatedBefore predicate.
-  GrowableArray<UseInterval*> unallocated_;
+  GrowableArray<LiveRange*> unallocated_;
+
+  // Per register lists of allocated UseIntervals.  Contains only those
+  // intervals that can be affected by future allocation decisions.
+  // Those intervals that end before the start of the current UseInterval are
+  // removed from this list and will not be affected.
+  GrowableArray<LiveRange*> cpu_regs_[kNumberOfCpuRegisters];
 
-  // Per register lists of allocated UseIntervals, linked through
-  // next_allocated field.  Contains only those intervals that
-  // can be affected by future allocation decisions.  Those intervals
-  // that end before the start of the current UseInterval are removed
-  // from this list and will not be affected.
-  UseInterval* cpu_regs_[kNumberOfCpuRegisters];
+  GrowableArray<intptr_t> spill_slots_;
+
+  bool blocked_cpu_regs_[kNumberOfCpuRegisters];
 
   DISALLOW_COPY_AND_ASSIGN(FlowGraphAllocator);
 };
@@ -147,49 +188,14 @@ class FlowGraphAllocator : public ValueObject {
 // this use with certain properties (if slot contain an unallocated location).
 class UsePosition : public ZoneAllocated {
  public:
-  enum UseFlag {
-    kNoFlag = 0,
-    kFixedUse = 1,
-    kSameAsFirstUse = 2,
-    kOther = 3
-  };
-
-  static const intptr_t kUseFlagMask = 0x3;
-  static const intptr_t kPositionShift = 2;
-
-  static UseFlag FlagForUse(const Location& loc) {
-    if (loc.IsRegister()) return kFixedUse;
-    if (loc.IsUnallocated() && (loc.policy() == Location::kSameAsFirstInput)) {
-      return kSameAsFirstUse;
-    }
-    return kOther;
-  }
-
-  // TODO(vegorov): we encode either position or instruction pointer
-  // into the pos_ field to generate moves when needed to resolve
-  // fixed or same-as-first constraints, but this looks ugly.
-  UsePosition(Instruction* instr,
-              intptr_t pos,
+  UsePosition(intptr_t pos,
               UsePosition* next,
               Location* location_slot)
-      : pos_(pos << kPositionShift),
+      : pos_(pos),
         location_slot_(location_slot),
         next_(next) {
-    // Non-NULL instr is considered unlikely so we preinitialize pos_ field
-    // with an encoded position even if instr is not NULL.
-    if (instr != NULL) {
-      ASSERT(location_slot_ != NULL);
-      pos_ = reinterpret_cast<intptr_t>(instr) | FlagForUse(*location_slot_);
-    }
-    ASSERT(this->pos() == pos);
   }
 
-  // Tell the use that it should load the value from the given location.
-  // If location slot for the use is flexible (unallocated) it will be updated
-  // with the given location. Otherwise a move will be scheduled from the given
-  // location to the location already stored in the slot.
-  void AssignLocation(Location loc);
-
   Location* location_slot() const { return location_slot_; }
   void set_location_slot(Location* location_slot) {
     location_slot_ = location_slot;
@@ -198,26 +204,15 @@ class UsePosition : public ZoneAllocated {
   void set_next(UsePosition* next) { next_ = next; }
   UsePosition* next() const { return next_; }
 
-  intptr_t pos() const {
-    if ((pos_ & kUseFlagMask) != kNoFlag) {
-      return instr()->lifetime_position();
-    }
-    return pos_ >> kPositionShift;
-  }
-
-  Instruction* instr() const {
-    ASSERT((pos_ & kUseFlagMask) != kNoFlag);
-    return reinterpret_cast<Instruction*>(pos_ & ~kUseFlagMask);
-  }
+  intptr_t pos() const { return pos_; }
 
   bool HasHint() const {
-    return (pos_ & kUseFlagMask) == kFixedUse;
+    return (location_slot() != NULL) && (location_slot()->IsRegister());
   }
 
   Location hint() const {
     ASSERT(HasHint());
-    ASSERT(location_slot()->IsRegister());
-    return *location_slot_;
+    return *location_slot();
   }
 
  private:
@@ -232,29 +227,19 @@ class UsePosition : public ZoneAllocated {
 // NumberInstructions assigns to instructions.  Register allocator has to keep
 // a value live in the register or in a spill slot from start position and until
 // the end position.  The interval can cover zero or more uses.
-// During the register allocation UseIntervals from different live ranges
-// allocated to the same register will be chained together through
-// next_allocated_ field.
 // Note: currently all uses of the same SSA value are linked together into a
 // single list (and not split between UseIntervals).
 class UseInterval : public ZoneAllocated {
  public:
-  UseInterval(intptr_t vreg, intptr_t start, intptr_t end, UseInterval* next)
-      : vreg_(vreg),
-        start_(start),
+  UseInterval(intptr_t start, intptr_t end, UseInterval* next)
+      : start_(start),
         end_(end),
-        uses_((next == NULL) ? NULL : next->uses_),
-        next_(next),
-        next_allocated_(next) { }
-
+        next_(next) { }
 
-  void AddUse(Instruction* instr, intptr_t pos, Location* loc);
   void Print();
 
-  intptr_t vreg() const { return vreg_; }
   intptr_t start() const { return start_; }
   intptr_t end() const { return end_; }
-  UsePosition* first_use() const { return uses_; }
   UseInterval* next() const { return next_; }
 
   bool Contains(intptr_t pos) const {
@@ -265,50 +250,117 @@ class UseInterval : public ZoneAllocated {
   // kIllegalPosition if intervals do not intersect.
   intptr_t Intersect(UseInterval* other);
 
-  UseInterval* Split(intptr_t pos);
-
-  void set_next_allocated(UseInterval* next_allocated) {
-    next_allocated_ = next_allocated;
-  }
-  UseInterval* next_allocated() const { return next_allocated_; }
+  // UseInterval* Split(intptr_t pos);

[srdjan, 2012/07/19 22:54:39]

Delete dead code.

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

Done.

 
  private:
   friend class LiveRange;
-  const intptr_t vreg_;
 
   intptr_t start_;
   intptr_t end_;
+  UseInterval* next_;
+};
 
-  UsePosition* uses_;
 
-  UseInterval* next_;
-  UseInterval* next_allocated_;
+class AllocationFinger : public ValueObject {
+ public:
+  AllocationFinger()
+    : first_pending_use_interval_(NULL),
+      first_register_use_(NULL),
+      first_register_beneficial_use_(NULL),
+      first_hinted_use_(NULL) {
+  }
+
+  void Initialize(LiveRange* range);
+  bool Advance(intptr_t start);
+
+  UseInterval* first_pending_use_interval() const {
+    return first_pending_use_interval_;
+  }
+
+  Location FirstHint();
+  UsePosition* FirstRegisterUse(intptr_t after_pos);
+  UsePosition* FirstRegisterBeneficialUse(intptr_t after_pos);
+
+ private:
+  UseInterval* first_pending_use_interval_;
+  UsePosition* first_register_use_;
+  UsePosition* first_register_beneficial_use_;
+  UsePosition* first_hinted_use_;
 };
 
 
 // LiveRange represents a sequence of UseIntervals for a given SSA value.
-// TODO(vegorov): this class is actually redundant currently.
 class LiveRange : public ZoneAllocated {
  public:
-  explicit LiveRange(intptr_t vreg) : vreg_(vreg), head_(NULL) { }
+  explicit LiveRange(intptr_t vreg)
+    : vreg_(vreg),
+      uses_(NULL),
+      first_use_interval_(NULL),
+      last_use_interval_(NULL),
+      next_sibling_(NULL) {

[srdjan, 2012/07/19 22:54:39]

, finger_() {

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

Done.

+  }
 
-  void DefineAt(Instruction* instr, intptr_t pos, Location* loc);
+  static LiveRange* MakeTemp(intptr_t pos, Location* location_slot);
 
-  void UseAt(Instruction* instr,
-             intptr_t def_pos,
+  intptr_t vreg() const { return vreg_; }
+  LiveRange* next_sibling() const { return next_sibling_; }
+  UsePosition* first_use() const { return uses_; }
+  UseInterval* first_use_interval() const { return first_use_interval_; }
+  UseInterval* last_use_interval() const { return last_use_interval_; }
+  Location assigned_location() const { return assigned_location_; }
+  intptr_t Start() const { return first_use_interval()->start(); }
+  intptr_t End() const { return first_use_interval()->end(); }
+
+  AllocationFinger* finger() { return &finger_; }
+
+  void set_assigned_location(Location location) {
+    assigned_location_ = location;
+  }
+
+
+  void DefineAt(intptr_t pos, Location* loc);
+
+  void UseAt(intptr_t def_pos,
              intptr_t use_pos,
              bool use_at_end,
              Location* loc);
 
+  void AddUse(intptr_t pos, Location* location_slot);
   void AddUseInterval(intptr_t start, intptr_t end);
 
   void Print();
 
-  UseInterval* head() const { return head_; }
+  void AssignLocation(UseInterval* use, Location loc);
+
+  LiveRange* SplitAt(intptr_t pos);
+
+  bool CanCover(intptr_t pos) const {
+    return (Start() <= pos) && (pos < End());
+  }
 
  private:
+  LiveRange(intptr_t vreg,
+            UsePosition* uses,
+            UseInterval* first_use_interval,
+            UseInterval* last_use_interval,
+            LiveRange* next_sibling)
+    : vreg_(vreg),
+      uses_(uses),
+      first_use_interval_(first_use_interval),
+      last_use_interval_(last_use_interval),
+      next_sibling_(next_sibling) {

[srdjan, 2012/07/19 22:54:39]

, finger_() {

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

Done.

+  }
+
   const intptr_t vreg_;
-  UseInterval* head_;
+  Location assigned_location_;
+
+  UsePosition* uses_;
+  UseInterval* first_use_interval_;
+  UseInterval* last_use_interval_;
+
+  LiveRange* next_sibling_;
+
+  AllocationFinger finger_;
 };