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

src/IceRegAlloc.cpp

Index: src/IceRegAlloc.cpp
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index 2a300346018749ce5561b65b4df5101facbcd250..b30b6016f14ecae2b9869f17243352c22617ef14 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -85,6 +85,7 @@ void LinearScan::initForGlobal() {
   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) {
@@ -184,6 +185,7 @@ void LinearScan::initForInfOnly() {
   }
 
   Unhandled.reserve(NumVars);
+  UnhandledPrecolored.reserve(NumVars);
   for (SizeT i = 0; i < Vars.size(); ++i) {
     Variable *Var = Vars[i];
     if (LRBegin[i] != Inst::NumberSentinel) {
@@ -216,6 +218,9 @@ void LinearScan::init(RegAllocKind Kind) {
   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:
@@ -276,7 +281,6 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
   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;
@@ -319,10 +323,8 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
     }
 
     // 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)) {
@@ -332,7 +334,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
           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.
@@ -341,7 +343,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
           dumpLiveRange(Item, Func);
           Str << "\n";
         }
-        Inactive.splice(Inactive.end(), Active, I);
+        moveItem(Active, I - 1, Inactive);
         Moved = true;
       }
       if (Moved) {
@@ -354,10 +356,8 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
     }
 
     // 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.
@@ -366,7 +366,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
           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) {
@@ -374,7 +374,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
           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();
@@ -598,10 +598,8 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
       } 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     ";
@@ -611,14 +609,12 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
             --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
@@ -636,7 +632,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
               Str << "\n";
             }
             Item->setRegNumTmp(Variable::NoRegister);
-            Handled.splice(Handled.end(), Inactive, I);
+            moveItem(Inactive, I - 1, Handled);
           }
         }
         // Assign the register to Cur.