Subzero: Improve the memory-related performance of the register allocator.

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 67 matching lines @@
 } // end of anonymous namespace
 
 // Prepare for full register allocation of all variables.  We depend
 // on liveness analysis to have calculated live ranges.
 void LinearScan::initForGlobal() {
   TimerMarker T(TimerStack::TT_initUnhandled, Func);
   FindPreference = true;
   FindOverlap = true;
   const VarList &Vars = Func->getVariables();
   Unhandled.reserve(Vars.size());
+  UnhandledPrecolored.reserve(Vars.size());
   // Gather the live ranges of all variables and add them to the
   // Unhandled set.
   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())
@@ skipping 79 matching lines @@
         for (SizeT J = 0; J < NumVars; ++J) {
           const Variable *Var = Src->getVar(J);
           if (Var->hasReg() || Var->getWeight() == RegWeight::Inf)
             LREnd[Var->getIndex()] = Inst->getNumber();
         }
       }
     }
   }
 
   Unhandled.reserve(NumVars);
+  UnhandledPrecolored.reserve(NumVars);
   for (SizeT i = 0; i < Vars.size(); ++i) {
     Variable *Var = Vars[i];
     if (LRBegin[i] != Inst::NumberSentinel) {
       assert(LREnd[i] != Inst::NumberSentinel);
       Unhandled.push_back(Var);
       Var->resetLiveRange();
       const uint32_t WeightDelta = 1;
       Var->addLiveRange(LRBegin[i], LREnd[i], WeightDelta);
       Var->untrimLiveRange();
       if (Var->hasReg()) {
@@ skipping 12 matching lines @@
   // infinite-weight Variable has a live range spanning a call.
   Kills.clear();
 }
 
 void LinearScan::init(RegAllocKind Kind) {
   Unhandled.clear();
   UnhandledPrecolored.clear();
   Handled.clear();
   Inactive.clear();
   Active.clear();
+  Handled.reserve(Unhandled.size());
+  Inactive.reserve(Unhandled.size());

[jvoung (off chromium), 2014/12/04 02:46:44]

Should this be after initForGlobal/initForInfOnly?

Otherwise, Unhandled.size() is still 0?

[Jim Stichnoth, 2014/12/04 04:25:17]

Done, thanks!

+  Active.reserve(Unhandled.size());
 
   switch (Kind) {
   case RAK_Global:
     initForGlobal();
     break;
   case RAK_InfOnly:
     initForInfOnly();
     break;
   }
 
@@ skipping 40 matching lines @@
 
   // RegUses[I] is the number of live ranges (variables) that register
   // I is currently assigned to.  It can be greater than 1 as a result
   // of AllowOverlap inference below.
   std::vector<int> RegUses(RegMaskFull.size());
   // Unhandled is already set to all ranges in increasing order of
   // start points.
   assert(Active.empty());
   assert(Inactive.empty());
   assert(Handled.empty());
-  UnorderedRanges::iterator Next;
   const TargetLowering::RegSetMask RegsInclude =
       TargetLowering::RegSet_CallerSave;
   const TargetLowering::RegSetMask RegsExclude = TargetLowering::RegSet_None;
   const llvm::SmallBitVector KillsMask =
       Func->getTarget()->getRegisterSet(RegsInclude, RegsExclude);
 
   while (!Unhandled.empty()) {
     Variable *Cur = Unhandled.back();
     Unhandled.pop_back();
     if (Verbose) {
@@ skipping 22 matching lines @@
       Active.push_back(Cur);
       assert(RegUses[RegNum] >= 0);
       ++RegUses[RegNum];
       assert(!UnhandledPrecolored.empty());
       assert(UnhandledPrecolored.back() == Cur);
       UnhandledPrecolored.pop_back();
       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;
-      Variable *Item = *I;
+    for (SizeT I = Active.size(); I > 0; --I) {
+      Variable *Item = Active[I - 1];

[jvoung (off chromium), 2014/12/04 02:46:44]

Maybe initialize I to Active.size() - 1, and go up to I >= 0, then the indexing
doesn't have to be I-1?

[Jim Stichnoth, 2014/12/04 04:25:17]

SizeT is unsigned (uint32_t), so I>=0 is always true...  That's why I used the
clumsy I-1 pattern.

After some thought, changed it to use "const SizeT Index = I - 1;".

       Item->trimLiveRange(Cur->getLiveRange().getStart());
       bool Moved = false;
       if (Item->rangeEndsBefore(Cur)) {
         // Move Item from Active to Handled list.
         if (Verbose) {
           Str << "Expiring     ";
           dumpLiveRange(Item, Func);
           Str << "\n";
         }
-        Handled.splice(Handled.end(), Active, I);
+        moveItem(Active, I - 1, Handled);
         Moved = true;
       } else if (!Item->rangeOverlapsStart(Cur)) {
         // Move Item from Active to Inactive list.
         if (Verbose) {
           Str << "Inactivating ";
           dumpLiveRange(Item, Func);
           Str << "\n";
         }
-        Inactive.splice(Inactive.end(), Active, I);
+        moveItem(Active, I - 1, Inactive);
         Moved = true;
       }
       if (Moved) {
         // Decrement Item from RegUses[].
         assert(Item->hasRegTmp());
         int32_t RegNum = Item->getRegNumTmp();
         --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;
-      Variable *Item = *I;
+    for (SizeT I = Inactive.size(); I > 0; --I) {
+      Variable *Item = Inactive[I - 1];
       Item->trimLiveRange(Cur->getLiveRange().getStart());
       if (Item->rangeEndsBefore(Cur)) {
         // Move Item from Inactive to Handled list.
         if (Verbose) {
           Str << "Expiring     ";
           dumpLiveRange(Item, Func);
           Str << "\n";
         }
-        Handled.splice(Handled.end(), Inactive, I);
+        moveItem(Inactive, I - 1, Handled);
       } else if (Item->rangeOverlapsStart(Cur)) {
         // Move Item from Inactive to Active list.
         if (Verbose) {
           Str << "Reactivating ";
           dumpLiveRange(Item, Func);
           Str << "\n";
         }
-        Active.splice(Active.end(), Inactive, I);
+        moveItem(Inactive, I - 1, Active);
         // Increment Item in RegUses[].
         assert(Item->hasRegTmp());
         int32_t RegNum = Item->getRegNumTmp();
         assert(RegUses[RegNum] >= 0);
         ++RegUses[RegNum];
       }
     }
 
     // Calculate available registers into Free[].
     llvm::SmallBitVector Free = RegMask;
@@ skipping 203 matching lines @@
         // don't allocate any register to it, and move it to the
         // Handled state.
         Handled.push_back(Cur);
         if (Cur->getLiveRange().getWeight().isInf()) {
           Func->setError("Unable to find a physical register for an "
                          "infinite-weight live range");
         }
       } else {
         // Evict all live ranges in Active that register number
         // MinWeightIndex is assigned to.
-        for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) {
-          Next = I;
-          ++Next;
-          Variable *Item = *I;
+        for (SizeT I = Active.size(); I > 0; --I) {
+          Variable *Item = Active[I - 1];
           if (Item->getRegNumTmp() == MinWeightIndex) {
             if (Verbose) {
               Str << "Evicting     ";
               dumpLiveRange(Item, Func);
               Str << "\n";
             }
             --RegUses[MinWeightIndex];
             assert(RegUses[MinWeightIndex] >= 0);
             Item->setRegNumTmp(Variable::NoRegister);
-            Handled.splice(Handled.end(), Active, I);
+            moveItem(Active, I - 1, Handled);
           }
         }
         // Do the same for Inactive.
-        for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) {
-          Next = I;
-          ++Next;
-          Variable *Item = *I;
+        for (SizeT I = Inactive.size(); I > 0; --I) {
+          Variable *Item = Inactive[I - 1];
           // Note: The Item->rangeOverlaps(Cur) clause is not part of the
           // description of AssignMemLoc() in the original paper.  But
           // there doesn't seem to be any need to evict an inactive
           // live range that doesn't overlap with the live range
           // currently being considered.  It's especially bad if we
           // would end up evicting an infinite-weight but
           // currently-inactive live range.  The most common situation
           // for this would be a scratch register kill set for call
           // instructions.
           if (Item->getRegNumTmp() == MinWeightIndex &&
               Item->rangeOverlaps(Cur)) {
             if (Verbose) {
               Str << "Evicting     ";
               dumpLiveRange(Item, Func);
               Str << "\n";
             }
             Item->setRegNumTmp(Variable::NoRegister);
-            Handled.splice(Handled.end(), Inactive, I);
+            moveItem(Inactive, I - 1, Handled);
           }
         }
         // Assign the register to Cur.
         Cur->setRegNumTmp(MinWeightIndex);
         assert(RegUses[MinWeightIndex] >= 0);
         ++RegUses[MinWeightIndex];
         Active.push_back(Cur);
         if (Verbose) {
           Str << "Allocating   ";
           dumpLiveRange(Cur, Func);
@@ skipping 69 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice