Subzero: Optimize live range overlaps() computation through trimming.

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.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file declares the Operand class and its target-independent
@@ skipping 285 matching lines @@
 // coalesced into a single interval.  LiveRange also includes a
 // weight, in case e.g. we want a live range to have higher weight
 // inside a loop.
 class LiveRange {
 public:
   LiveRange() : Weight(0), IsNonpoints(false) {}
 
   void reset() {
     Range.clear();
     Weight.setWeight(0);
+    untrim();
     IsNonpoints = false;
   }
   void addSegment(InstNumberT Start, InstNumberT End);
 
   bool endsBefore(const LiveRange &Other) const;
-  bool overlaps(const LiveRange &Other) const;
-  bool overlaps(InstNumberT OtherBegin) const;
+  bool overlaps(const LiveRange &Other, bool UseTrimmed = false) const;
+  bool overlapsInst(InstNumberT OtherBegin, bool UseTrimmed = false) const;
   bool containsValue(InstNumberT Value) const;
   bool isEmpty() const { return Range.empty(); }
+  bool isNonpoints() const { return IsNonpoints; }
   InstNumberT getStart() const {
     return Range.empty() ? -1 : Range.begin()->first;
   }
 
+  void untrim() { TrimmedBegin = Range.begin(); }
+  void trim(InstNumberT Lower);
+
   RegWeight getWeight() const { return Weight; }
   void setWeight(const RegWeight &NewWeight) { Weight = NewWeight; }
   void addWeight(uint32_t Delta) { Weight.addWeight(Delta); }
   void dump(Ostream &Str) const;
 
   // Defining USE_SET uses std::set to hold the segments instead of
   // std::list.  Using std::list will be slightly faster, but is more
   // restrictive because new segments cannot be added in the middle.
 
   //#define USE_SET
 
 private:
   typedef std::pair<InstNumberT, InstNumberT> RangeElementType;
 #ifdef USE_SET
   typedef std::set<RangeElementType> RangeType;
 #else
   typedef std::list<RangeElementType> RangeType;
 #endif
   RangeType Range;
   RegWeight Weight;
+  // 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;
   // IsNonpoints keeps track of whether the live range contains at
   // least one interval where Start!=End.  If it is empty or has the
   // form [x,x),[y,y),...,[z,z), then overlaps(InstNumberT) is
   // trivially false.
   bool IsNonpoints;
 };
 
 Ostream &operator<<(Ostream &Str, const LiveRange &L);
 
 // Variable represents an operand that is register-allocated or
@@ skipping 48 matching lines @@
   void resetLiveRange() { Live.reset(); }
   void addLiveRange(InstNumberT Start, InstNumberT End, uint32_t WeightDelta) {
     assert(WeightDelta != RegWeight::Inf);
     Live.addSegment(Start, End);
     if (Weight.isInf())
       Live.setWeight(RegWeight::Inf);
     else
       Live.addWeight(WeightDelta * Weight.getWeight());
   }
   void setLiveRangeInfiniteWeight() { Live.setWeight(RegWeight::Inf); }
+  void trimLiveRange(InstNumberT Start) { Live.trim(Start); }
+  void untrimLiveRange() { Live.untrim(); }
 
   Variable *getLo() const { return LoVar; }
   Variable *getHi() const { return HiVar; }
   void setLoHi(Variable *Lo, Variable *Hi) {
     assert(LoVar == NULL);
     assert(HiVar == NULL);
     LoVar = Lo;
     HiVar = Hi;
   }
   // Creates a temporary copy of the variable with a different type.
@@ skipping 85 matching lines @@
   void markUse(const Inst *Instr, const CfgNode *Node, bool IsFromDef,
                bool IsImplicit);
   void markDef(const Inst *Instr, const CfgNode *Node);
 
 private:
   VariableTracking &operator=(const VariableTracking &) = delete;
   MultiDefState MultiDef;
   MultiBlockState MultiBlock;
   const CfgNode *SingleUseNode;
   const CfgNode *SingleDefNode;
-  // All definitions of the variable are collected here, in the order
-  // encountered.  Definitions in the same basic block are in
-  // instruction order, but there's no guarantee for the basic block
-  // order.
+  // All definitions of the variable are collected here, in increasing
+  // order of instruction number.
   InstDefList Definitions;
 };
 
 // VariablesMetadata analyzes and summarizes the metadata for the
 // complete set of Variables.
 class VariablesMetadata {
 public:
   VariablesMetadata(const Cfg *Func) : Func(Func) {}
   // Initialize the state by traversing all instructions/variables in
   // the CFG.
@@ skipping 39 matching lines @@
   const Cfg *Func;
   std::vector<VariableTracking> Metadata;
   const static InstDefList NoDefinitions;
   VariablesMetadata(const VariablesMetadata &) = delete;
   VariablesMetadata &operator=(const VariablesMetadata &) = delete;
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEOPERAND_H