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, CfgNode *Node = nullptr) {
+    addSegment(Segment.first, Segment.second, Node);
+  }
 
   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() const { return Range.size(); }
+
+  const RangeType &getSegments() const { return Range; }
+  CfgNode *getNodeForSegment(InstNumberT Begin) { return NodeMap[Begin]; }

[Jim Stichnoth, 2016/08/02 05:57:50]

Should probably assert that NodeMap contains Begin.

[manasijm, 2016/08/02 21:41:58]

Done.

+
 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 82 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 284 matching lines @@
     return Operand->getKind() == kVariableBoolean;
   }
 
 private:
   Variable *BoolSource = nullptr;
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEOPERAND_H