Subzero: Implement "second-chance bin-packing" for register allocation.

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.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 259 matching lines @@
   }
   // This isn't actually a fatal condition, but it would be nice to know if we
   // somehow pre-calculated Unhandled's size wrong.
   assert(NumVars == 0);
 
   // Don't build up the list of Kills because we know that no infinite-weight
   // Variable has a live range spanning a call.
   Kills.clear();
 }
 
+void LinearScan::initForSecondChance() {
+  TimerMarker T(TimerStack::TT_initUnhandled, Func);
+  FindPreference = true;
+  FindOverlap = true;
+  const VarList &Vars = Func->getVariables();
+  Unhandled.reserve(Vars.size());
+  UnhandledPrecolored.reserve(Vars.size());
+  for (Variable *Var : Vars) {
+    if (Var->hasReg()) {
+      Var->untrimLiveRange();
+      Var->setRegNumTmp(Var->getRegNum());
+      Var->setMustHaveReg();
+      UnhandledPrecolored.push_back(Var);
+      Unhandled.push_back(Var);
+    }
+  }
+  for (Variable *Var : Evicted) {
+    Var->untrimLiveRange();
+    Unhandled.push_back(Var);
+  }
+}
+
 void LinearScan::init(RegAllocKind Kind) {
   this->Kind = Kind;
   Unhandled.clear();
   UnhandledPrecolored.clear();
   Handled.clear();
   Inactive.clear();
   Active.clear();
 
   SizeT NumRegs = Target->getNumRegisters();
   RegAliases.resize(NumRegs);
   for (SizeT Reg = 0; Reg < NumRegs; ++Reg) {
     RegAliases[Reg] = &Target->getAliasesForRegister(Reg);
   }
 
   switch (Kind) {
   case RAK_Unknown:
     llvm::report_fatal_error("Invalid RAK_Unknown");
     break;
   case RAK_Global:
   case RAK_Phi:
     initForGlobal();
     break;
   case RAK_InfOnly:
     initForInfOnly();
     break;
+  case RAK_SecondChance:
+    initForSecondChance();
+    break;
   }
 
+  Evicted.clear();
+
   auto CompareRanges = [](const Variable *L, const Variable *R) {
     InstNumberT Lstart = L->getLiveRange().getStart();
     InstNumberT Rstart = R->getLiveRange().getStart();
     if (Lstart == Rstart)
       return L->getIndex() < R->getIndex();
     return Lstart < Rstart;
   };
   // Do a reverse sort so that erasing elements (from the end) is fast.
   std::sort(Unhandled.rbegin(), Unhandled.rend(), CompareRanges);
   std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(),
             CompareRanges);
 
   Handled.reserve(Unhandled.size());
   Inactive.reserve(Unhandled.size());
   Active.reserve(Unhandled.size());
+  Evicted.reserve(Unhandled.size());
 }
 
 // This is called when Cur must be allocated a register but no registers are
 // available across Cur's live range. To handle this, we find a register that
 // is not explicitly used during Cur's live range, spill that register to a
 // stack location right before Cur's live range begins, and fill (reload) the
 // register from the stack location right after Cur's live range ends.
 void LinearScan::addSpillFill(IterationState &Iter) {
   // Identify the actual instructions that begin and end Iter.Cur's live range.
   // Iterate through Iter.Cur's node's instruction list until we find the actual
@@ skipping 324 matching lines @@
     for (SizeT I = Active.size(); I > 0; --I) {
       const SizeT Index = I - 1;
       Variable *Item = Active[Index];
       int32_t RegNum = Item->getRegNumTmp();
       if (Aliases[RegNum]) {
         dumpLiveRangeTrace("Evicting A   ", Item);
         --RegUses[RegNum];
         assert(RegUses[RegNum] >= 0);
         Item->setRegNumTmp(Variable::NoRegister);
         moveItem(Active, Index, Handled);
+        Evicted.push_back(Item);
       }
     }
     // Do the same for Inactive.
     for (SizeT I = Inactive.size(); I > 0; --I) {
       const SizeT Index = I - 1;
       Variable *Item = Inactive[Index];
       // 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 (Aliases[Item->getRegNumTmp()] && Item->rangeOverlaps(Iter.Cur)) {
         dumpLiveRangeTrace("Evicting I   ", Item);
         Item->setRegNumTmp(Variable::NoRegister);
         moveItem(Inactive, Index, Handled);
+        Evicted.push_back(Item);
       }
     }
     // Assign the register to Cur.
     Iter.Cur->setRegNumTmp(MinWeightIndex);
     for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
          RegAlias = Aliases.find_next(RegAlias)) {
       assert(RegUses[RegAlias] >= 0);
       ++RegUses[RegAlias];
     }
     Active.push_back(Iter.Cur);
@@ skipping 247 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice