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

src/IceRegAlloc.cpp

 //===- subzero/src/IceRegAlloc.cpp - Linear-scan 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 LinearScan class, which performs the
@@ skipping 80 matching lines @@
     TimerMarker T(IDinitUnhandled, Func->getContext());
     for (Variable *Var : Vars) {
       // Explicitly don't consider zero-weight variables, which are
       // meant to be spill slots.
       if (Var->getWeight() == RegWeight::Zero)
         continue;
       // Don't bother if the variable has a null live range, which means
       // it was never referenced.
       if (Var->getLiveRange().isEmpty())
         continue;
+      Var->untrimLiveRange();
       LiveRangeWrapper R(Var);
       Unhandled.insert(R);
       if (Var->hasReg()) {
         Var->setRegNumTmp(Var->getRegNum());
         Var->setLiveRangeInfiniteWeight();
         UnhandledPrecolored.insert(R);
       }
     }
   }
 
@@ skipping 41 matching lines @@
       assert(UnhandledPrecolored.begin()->Var == Cur.Var);
       UnhandledPrecolored.erase(UnhandledPrecolored.begin());
       continue;
     }
 
     // Check for active ranges that have expired or become inactive.
     for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) {
       Next = I;
       ++Next;
       LiveRangeWrapper Item = *I;
+      Item.Var->trimLiveRange(Cur.range().getStart());
       bool Moved = false;
       if (Item.endsBefore(Cur)) {
         // Move Item from Active to Handled list.
         if (Verbose) {
           Str << "Expiring     ";
           Item.dump(Func);
           Str << "\n";
         }
         Active.erase(I);
         Handled.push_back(Item);
@@ skipping 16 matching lines @@
         --RegUses[RegNum];
         assert(RegUses[RegNum] >= 0);
       }
     }
 
     // Check for inactive ranges that have expired or reactivated.
     for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) {
       Next = I;
       ++Next;
       LiveRangeWrapper Item = *I;
+      Item.Var->trimLiveRange(Cur.range().getStart());
+      // As an optimization, don't bother checking pure point-valued
+      // Inactive ranges, because the overlapsStart() test will never
+      // succeed, and the endsBefore() test will generally only
+      // succeed after the last call instruction, which statistically
+      // happens near the end.  TODO(stichnot): Consider suppressing
+      // this check every N iterations in case calls are only at the
+      // beginning of the function.
+      if (!Item.range().isNonpoints())
+        continue;
       if (Item.endsBefore(Cur)) {
         // Move Item from Inactive to Handled list.
         if (Verbose) {
           Str << "Expiring     ";
           Item.dump(Func);
           Str << "\n";
         }
         Inactive.erase(I);
         Handled.push_back(Item);
       } else if (Item.overlapsStart(Cur)) {
@@ skipping 108 matching lines @@
 
     // Remove registers from the Free[] list where an Unhandled
     // precolored range overlaps with the current range, and set those
     // registers to infinite weight so that they aren't candidates for
     // eviction.  Cur.endsBefore(Item) is an early exit check that
     // turns a guaranteed O(N^2) algorithm into expected linear
     // complexity.
     llvm::SmallBitVector PrecoloredUnhandledMask(RegMask.size());
     // Note: PrecoloredUnhandledMask is only used for dumping.
     for (const LiveRangeWrapper &Item : UnhandledPrecolored) {
       assert(Item.Var->hasReg());

[jvoung (off chromium), 2014/10/05 20:34:14]

Is there any benefit to trimming the UnhandledPrecolored?

[Jim Stichnoth, 2014/10/06 13:38:01]

It shouldn't have any benefit.  By definition, the Unhandled live ranges begin
at or after the start of Cur's live range, so trim() should not actually do
anything.

       if (Cur.endsBefore(Item))
         break;
       if (Item.overlaps(Cur)) {
         int32_t ItemReg = Item.Var->getRegNum(); // Note: not getRegNumTmp()
         Weights[ItemReg].setWeight(RegWeight::Inf);
         Free[ItemReg] = false;
         PrecoloredUnhandledMask[ItemReg] = true;
         // Disable AllowOverlap if the preferred register is one of
         // these precolored unhandled overlapping ranges.
         if (AllowOverlap && ItemReg == PreferReg) {
@@ skipping 213 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const LiveRangeWrapper &Item : Inactive) {
     Item.dump(Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice