Subzero : Live Range Splitting after initial Register Allocation

src/IceOperand.h

 //===- subzero/src/IceOperand.h - High-level operands -----------*- C++ -*-===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 585 matching lines @@
 bool operator<(const RegWeight &A, const RegWeight &B);
 bool operator<=(const RegWeight &A, const RegWeight &B);
 bool operator==(const RegWeight &A, const RegWeight &B);
 
 /// LiveRange is a set of instruction number intervals representing a variable's
 /// live range. Generally there is one interval per basic block where the
 /// variable is live, but adjacent intervals get coalesced into a single
 /// interval.
 class LiveRange {
 public:
+  using RangeElementType = std::pair<InstNumberT, InstNumberT>;
+  /// RangeType is arena-allocated from the Cfg's allocator.
+  using RangeType = CfgVector<RangeElementType>;
   LiveRange() = default;
   /// Special constructor for building a kill set. The advantage is that we can
   /// reserve the right amount of space in advance.
   explicit LiveRange(const CfgVector<InstNumberT> &Kills) {
     Range.reserve(Kills.size());
     for (InstNumberT I : Kills)
       addSegment(I, I);
   }
   LiveRange(const LiveRange &) = default;
   LiveRange &operator=(const LiveRange &) = default;
 
   void reset() {
     Range.clear();
     untrim();
   }
-  void addSegment(InstNumberT Start, InstNumberT End);
+  void addSegment(InstNumberT Start, InstNumberT End, CfgNode *Node = nullptr);
+  void addSegment(RangeElementType Segment) {

[Jim Stichnoth, 2016/07/29 17:04:07]

How about:

void addSegment(RangeElementType Segment, CfgNode *Node = nullptr) {
  addSegment(Segment.first, Segment.second, Node);
}

[manasijm, 2016/08/01 22:20:04]

Done.

+    addSegment(Segment.first, Segment.second);
+  }
 
   bool endsBefore(const LiveRange &Other) const;
   bool overlaps(const LiveRange &Other, bool UseTrimmed = false) const;
   bool overlapsInst(InstNumberT OtherBegin, bool UseTrimmed = false) const;
   bool containsValue(InstNumberT Value, bool IsDest) const;
   bool isEmpty() const { return Range.empty(); }
   InstNumberT getStart() const {
     return Range.empty() ? -1 : Range.begin()->first;
   }
   InstNumberT getEnd() const {
     return Range.empty() ? -1 : Range.rbegin()->second;
   }
 
   void untrim() { TrimmedBegin = Range.begin(); }
   void trim(InstNumberT Lower);
 
   void dump(Ostream &Str) const;
 
+  SizeT getNumSegments() { return Range.size(); }

[Jim Stichnoth, 2016/07/29 17:04:07]

SizeT getNumSegments() const ...

[manasijm, 2016/08/01 22:20:03]

Done.

+
+  const RangeType &getSegments() { return Range; }

[Jim Stichnoth, 2016/07/29 17:04:07]

can this be const?

[manasijm, 2016/08/01 22:20:03]

Done.

+  CfgNode *getNodeForSegment(InstNumberT Begin) { return NodeMap[Begin]; }

[Jim Stichnoth, 2016/07/29 17:04:07]

const?

[manasijm, 2016/08/01 22:20:04]

Probably not.

+
 private:
-  using RangeElementType = std::pair<InstNumberT, InstNumberT>;
-  /// RangeType is arena-allocated from the Cfg's allocator.
-  using RangeType = CfgVector<RangeElementType>;
   RangeType Range;
+  CfgUnorderedMap<InstNumberT, CfgNode *> NodeMap;
   /// TrimmedBegin is an optimization for the overlaps() computation. Since the
   /// linear-scan algorithm always calls it as overlaps(Cur) and Cur advances
   /// monotonically according to live range start, we can optimize overlaps() by
   /// ignoring all segments that end before the start of Cur's range. The
   /// linear-scan code enables this by calling trim() on the ranges of interest
   /// as Cur advances. Note that linear-scan also has to initialize TrimmedBegin
   /// at the beginning by calling untrim().
   RangeType::const_iterator TrimmedBegin;
 };
 
@@ skipping 13 matching lines @@
     RR_MustNotHaveRegister,
   };
 
 public:
   static Variable *create(Cfg *Func, Type Ty, SizeT Index) {
     return new (Func->allocate<Variable>())
         Variable(Func, kVariable, Ty, Index);
   }
 
   SizeT getIndex() const { return Number; }
+  void setIndex(SizeT NewIndex) { Number = NewIndex; }
   std::string getName() const {
     if (Name.hasStdString())
       return Name.toString();
     return "__" + std::to_string(getIndex());
   }
   virtual void setName(const Cfg *Func, const std::string &NewName) {
     if (NewName.empty())
       return;
     Name = VariableString::createWithString(Func, NewName);
   }
@@ skipping 49 matching lines @@
   }
   bool isRematerializable() const { return IsRematerializable; }
 
   void setRegClass(uint8_t RC) { RegisterClass = static_cast<RegClass>(RC); }
   RegClass getRegClass() const { return RegisterClass; }
 
   LiveRange &getLiveRange() { return Live; }
   const LiveRange &getLiveRange() const { return Live; }
   void setLiveRange(const LiveRange &Range) { Live = Range; }
   void resetLiveRange() { Live.reset(); }
-  void addLiveRange(InstNumberT Start, InstNumberT End) {
+  void addLiveRange(InstNumberT Start, InstNumberT End,
+                    CfgNode *Node = nullptr) {
     assert(!getIgnoreLiveness());
-    Live.addSegment(Start, End);
+    Live.addSegment(Start, End, Node);
   }
   void trimLiveRange(InstNumberT Start) { Live.trim(Start); }
   void untrimLiveRange() { Live.untrim(); }
   bool rangeEndsBefore(const Variable *Other) const {
     return Live.endsBefore(Other->Live);
   }
   bool rangeOverlaps(const Variable *Other) const {
     constexpr bool UseTrimmed = true;
     return Live.overlaps(Other->Live, UseTrimmed);
   }
@@ skipping 41 matching lines @@
   Variable(const Cfg *Func, OperandKind K, Type Ty, SizeT Index)
       : Operand(K, Ty), Number(Index),
         Name(VariableString::createWithoutString(Func)),
         RegisterClass(static_cast<RegClass>(Ty)) {
     Vars = VarsReal;
     Vars[0] = this;
     NumVars = 1;
   }
   /// Number is unique across all variables, and is used as a (bit)vector index
   /// for liveness analysis.
-  const SizeT Number;
+  SizeT Number;
   VariableString Name;
   bool IsArgument = false;
   bool IsImplicitArgument = false;
   /// IgnoreLiveness means that the variable should be ignored when constructing
   /// and validating live ranges. This is usually reserved for the stack
   /// pointer and other physical registers specifically referenced by name.
   bool IgnoreLiveness = false;
   // If IsRematerializable, RegNum keeps track of which register (stack or frame
   // pointer), and StackOffset is the known offset from that register.
   bool IsRematerializable = false;
@@ skipping 222 matching lines @@
     return Operand->getKind() == kVariableBoolean;
   }
 
 private:
   Variable *BoolSource = nullptr;
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEOPERAND_H