Skeleton of a linear scan register 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 7848d2b11822e7b5d6a25d69c61d9430cd34ba02..abef00c28554ab67543feb48ae96161e83fad5f1 100644
--- a/runtime/vm/flow_graph_allocator.h
+++ b/runtime/vm/flow_graph_allocator.h
@@ -10,12 +10,16 @@
 
 namespace dart {
 
+class FlowGraphBuilder;
+class LiveRange;
+class UseInterval;
+
 class FlowGraphAllocator : public ValueObject {
  public:
-  FlowGraphAllocator(const GrowableArray<BlockEntryInstr*>& postorder,
-                     intptr_t max_ssa_temp_index);
+  FlowGraphAllocator(const GrowableArray<BlockEntryInstr*>& block_order,
+                     FlowGraphBuilder* builder);
 
-  void ResolveConstraints();
+  void AllocateRegisters();
 
   // Build live-in and live-out sets for each block.
   void AnalyzeLiveness();
@@ -30,7 +34,7 @@ class FlowGraphAllocator : public ValueObject {
   bool UpdateLiveOut(BlockEntryInstr* instr);
 
   // Update live-in set for the given block: live-in should contain
-  // all values taht are live-out from the block and are not defined
+  // all values that are live-out from the block and are not defined
   // by this block.
   // Returns true if live-in set was changed.
   bool UpdateLiveIn(BlockEntryInstr* instr);
@@ -42,6 +46,55 @@ class FlowGraphAllocator : public ValueObject {
   // Print results of liveness analysis.
   void DumpLiveness();
 
+  // Visit blocks in the code generation order (reverse post order) and
+  // linearly assign consequent lifetime positions to every instruction.
+  // Each instruction gets two positions:
+  //
+  //    2 * n     - even one corresponding to instruction's start
+  //
+  //    2 * n + 1 - odd one corresponding to instruction's end
+  //
+  // Having two positions allows us to capture non-trivial register
+  // constraints in use intervals: for example we can declare that
+  // an input value is only used at the start of the instruction and
+  // this might allow register allocator to allocate both this input
+  // and output (or temp) to the same register if this is the last
+  // use of the value.
+  // Additionally creates parallel moves at the joins' predecessors
+  // that will be used for phi resolution.
+  void NumberInstructions();
+
+  LiveRange* GetLiveRange(intptr_t vreg);
+  void BuildLiveRanges();
+  void PrintLiveRanges();
+
+  void UseValue(Instruction* instr,
+                intptr_t def,
+                intptr_t use,

[srdjan, 2012/07/11 17:22:32]

Please describe what are def and use. intptr_t sometime represents a virtual
register sometimes a position. Maybe we should use value types for those in
order to eliminate confusion (later CL)?

+                intptr_t vreg,
+                Location* loc,
+                bool use_at_end);
+  void Define(Instruction* instr, intptr_t def, intptr_t vreg, Location* loc);
+
+  void AddToUnallocated(UseInterval* chain);
+  void BlockLocation(Location loc, intptr_t pos);
+
+  bool AllocateFreeRegister(UseInterval* unallocated);
+  void AssignFreeRegister(UseInterval* unallocated, Register reg);
+
+  void FinalizeInterval(UseInterval* interval, Location loc);
+  void AdvanceActiveIntervals(const intptr_t start);
+
+  bool UnallocatedIsSorted();
+  void AllocateCPURegisters();
+
+  // TODO(vegorov): this field is used only to call Bailout. remove when

[srdjan, 2012/07/11 17:22:32]

s/remove/Remove/

+  // all bailouts are gone.
+  FlowGraphBuilder* builder_;
+
+  const GrowableArray<BlockEntryInstr*>& block_order_;
+  const GrowableArray<BlockEntryInstr*>& postorder_;
+
   // 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
@@ -56,15 +109,193 @@ class FlowGraphAllocator : public ValueObject {
   // that are used by this block or its successors.
   GrowableArray<BitVector*> live_in_;
 
-  const GrowableArray<BlockEntryInstr*>& postorder_;
-
   // Number of virtual registers.  Currently equal to the number of
   // SSA values.
   const intptr_t vreg_count_;
 
+  // LiveRanges corresponding to SSA values.
+  GrowableArray<LiveRange*> live_ranges_;
+
+  // Worklist for register allocator. Always maintained sorted according
+  // to ShouldBeAllocatedBefore predicate.
+  GrowableArray<UseInterval*> unallocated_;
+
+  // 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];
+
   DISALLOW_COPY_AND_ASSIGN(FlowGraphAllocator);
 };
 
+
+// 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 contain an unallocated location).
+class UsePosition : public ZoneAllocated {
+ public:
+  static const intptr_t kFixedUse = 0x1;
+  static const intptr_t kSameAsFirstUse = 0x2;
+  static const intptr_t kInstructionTagMask = 0x3;
+  static const intptr_t kPositionShift = 2;
+
+  static intptr_t FlagForUse(const Location& loc) {
+    if (loc.IsRegister()) return kFixedUse;
+    if (loc.IsUnallocated() && (loc.policy() == Location::kSameAsFirstInput)) {
+      return kSameAsFirstUse;
+    }
+    return kInstructionTagMask;
+  }
+
+  // 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* next,
+              Location* location_slot)
+      : pos_(pos << kPositionShift),
+        location_slot_(location_slot),
+        next_(next) {
+    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;
+  }
+
+  void set_next(UsePosition* next) { next_ = next; }
+  UsePosition* next() const { return next_; }
+
+  intptr_t pos() const {
+    if ((pos_ & kInstructionTagMask) != 0) {
+      return instr()->lifetime_position();
+    }
+    return pos_ >> kPositionShift;
+  }
+
+  Instruction* instr() const {
+    ASSERT((pos_ & kInstructionTagMask) != 0);
+    return reinterpret_cast<Instruction*>(pos_ & ~kInstructionTagMask);
+  }
+
+  bool HasHint() const {
+    return (pos_ & kInstructionTagMask) == kFixedUse;
+  }
+
+  Location hint() const {
+    ASSERT(HasHint());
+    ASSERT(location_slot()->IsRegister());
+    return *location_slot_;
+  }
+
+ private:
+  intptr_t pos_;
+  Location* location_slot_;
+  UsePosition* next_;
+};
+
+
+// UseInterval represents a holeless half open interval of liveness for a given
+// SSA value: [start, end) in terms of lifetime positions that
+// 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),
+        end_(end),
+        uses_((next == NULL) ? NULL : next->uses_),
+        next_(next),
+        next_allocated_(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 {
+    return (start() <= pos) && (pos < end());
+  }
+
+  // Return the smallest position that is covered by both UseIntervals or
+  // 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_; }
+
+ private:
+  friend class LiveRange;
+  const intptr_t vreg_;
+
+  intptr_t start_;
+  intptr_t end_;
+
+  UsePosition* uses_;
+
+  UseInterval* next_;
+  UseInterval* next_allocated_;
+};
+
+
+// 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) { }
+
+  void DefineAt(Instruction* instr, intptr_t pos, Location* loc);
+
+  void UseAt(Instruction* instr,
+             intptr_t def_pos,
+             intptr_t use_pos,
+             bool use_at_end,
+             Location* loc);
+
+  void AddUseInterval(intptr_t start, intptr_t end);
+
+  void Print();
+
+  UseInterval* head() const { return head_; }
+
+ private:
+  const intptr_t vreg_;
+  UseInterval* head_;
+};
+
+
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_ALLOCATOR_H_