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

src/IceOperand.cpp

 //===- subzero/src/IceOperand.cpp - High-level operand implementation -----===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Operand class and its target-independent
@@ skipping 87 matching lines @@
 bool LiveRange::endsBefore(const LiveRange &Other) const {
   // Neither range should be empty, but let's be graceful.
   if (Range.empty() || Other.Range.empty())
     return true;
   InstNumberT MyEnd = (*Range.rbegin()).second;
   InstNumberT OtherStart = (*Other.Range.begin()).first;
   return MyEnd <= OtherStart;
 }
 
 // Returns true if there is any overlap between the two live ranges.
-bool LiveRange::overlaps(const LiveRange &Other) const {
+bool LiveRange::overlaps(const LiveRange &Other, bool UseTrimmed) const {
   // Do a two-finger walk through the two sorted lists of segments.
-  RangeType::const_iterator I1 = Range.begin(), I2 = Other.Range.begin();
-  RangeType::const_iterator E1 = Range.end(), E2 = Other.Range.end();
+  auto I1 = (UseTrimmed ? TrimmedBegin : Range.begin()),
+       I2 = (UseTrimmed ? Other.TrimmedBegin : Other.Range.begin());
+  auto E1 = Range.end(), E2 = Other.Range.end();
   while (I1 != E1 && I2 != E2) {
     if (I1->second <= I2->first) {
       ++I1;
       continue;
     }
     if (I2->second <= I1->first) {
       ++I2;
       continue;
     }
     return true;
   }
   return false;
 }
 
-bool LiveRange::overlaps(InstNumberT OtherBegin) const {
+bool LiveRange::overlapsInst(InstNumberT OtherBegin, bool UseTrimmed) const {
   if (!IsNonpoints)
     return false;
   bool Result = false;
-  for (const RangeElementType &I : Range) {
-    if (OtherBegin < I.first) {
+  for (auto I = (UseTrimmed ? TrimmedBegin : Range.begin()), E = Range.end();
+       I != E; ++I) {
+    if (OtherBegin < I->first) {
       Result = false;
       break;
     }
-    if (OtherBegin < I.second) {
+    if (OtherBegin < I->second) {
       Result = true;
       break;
     }
   }
 #if 0
   // An equivalent but less inefficient implementation:
   LiveRange Temp;
   Temp.addSegment(OtherBegin, OtherBegin + 1);
   bool Validation = overlaps(Temp);
   assert(Result == Validation);
 #endif
   return Result;
 }
 
 // Returns true if the live range contains the given instruction
 // number.  This is only used for validating the live range
 // calculation.
 bool LiveRange::containsValue(InstNumberT Value) const {
   for (const RangeElementType &I : Range) {
     if (I.first <= Value && Value <= I.second)
       return true;
   }
   return false;
 }
 
+void LiveRange::trim(InstNumberT Lower) {
+  while (TrimmedBegin != Range.end() && TrimmedBegin->second <= Lower)
+    ++TrimmedBegin;
+}
+
 IceString Variable::getName() const {
   if (!Name.empty())
     return Name;
   char buf[30];
   snprintf(buf, llvm::array_lengthof(buf), "__%u", getIndex());
   return buf;
 }
 
 Variable Variable::asType(Type Ty) {
   // Note: This returns a Variable, even if the "this" object is a
@@ skipping 43 matching lines @@
     SingleUseNode = NULL;
   }
 }
 
 void VariableTracking::markDef(const Inst *Instr, const CfgNode *Node) {
   // TODO(stichnot): If the definition occurs in the last instruction
   // of the block, consider not marking this as a separate use.  But
   // be careful not to omit all uses of the variable if markDef() and
   // markUse() both use this optimization.
   assert(Node);
+  // Verify that instructions are added in increasing order.
+  assert(Definitions.empty() ||
+         Instr->getNumber() >= Definitions.back()->getNumber());
   Definitions.push_back(Instr);
   const bool IsFromDef = true;
   const bool IsImplicit = false;
   markUse(Instr, Node, IsFromDef, IsImplicit);
   switch (MultiDef) {
   case MDS_Unknown:
     assert(SingleDefNode == NULL);
     MultiDef = MDS_SingleDef;
     SingleDefNode = Node;
     break;
@@ skipping 218 matching lines @@
 
 Ostream &operator<<(Ostream &Str, const RegWeight &W) {
   if (W.getWeight() == RegWeight::Inf)
     Str << "Inf";
   else
     Str << W.getWeight();
   return Str;
 }
 
 } // end of namespace Ice