Subzero. Performance tweaks.

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
 /// \brief Implements the LinearScan class, which performs the linear-scan
 /// register allocation after liveness analysis has been performed.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "IceRegAlloc.h"
 
+#include "IceBitVector.h"
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 #include "IceInst.h"
 #include "IceInstVarIter.h"
 #include "IceOperand.h"
 #include "IceTargetLowering.h"
 
 namespace Ice {
 
 namespace {
@@ skipping 43 matching lines @@
   Ostream &Str = Func->getContext()->getStrDump();
   char buf[30];
   snprintf(buf, llvm::array_lengthof(buf), "%2u",
            unsigned(Var->getRegNumTmp()));
   Str << "R=" << buf << "  V=";
   Var->dump(Func);
   Str << "  Range=" << Var->getLiveRange();
 }
 
 int32_t findMinWeightIndex(
-    const llvm::SmallBitVector &RegMask,
+    const SmallBitVector &RegMask,
     const llvm::SmallVector<RegWeight, LinearScan::REGS_SIZE> &Weights) {
   int MinWeightIndex = -1;
   for (RegNumT i : RegNumBVIter(RegMask)) {
     if (MinWeightIndex < 0 || Weights[i] < Weights[MinWeightIndex])
       MinWeightIndex = i;
   }
   assert(MinWeightIndex >= 0);
   return MinWeightIndex;
 }
 
@@ skipping 314 matching lines @@
       SpillPoint = I;
     if (I->getNumber() == End)
       FillPoint = I;
     if (SpillPoint != E) {
       // Remove from RegMask any physical registers referenced during Cur's live
       // range. Start looking after SpillPoint gets set, i.e. once Cur's live
       // range begins.
       FOREACH_VAR_IN_INST(Var, *I) {
         if (!Var->hasRegTmp())
           continue;
-        const llvm::SmallBitVector &Aliases = *RegAliases[Var->getRegNumTmp()];
+        const auto &Aliases = *RegAliases[Var->getRegNumTmp()];
         for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
           Iter.RegMask[RegAlias] = false;
         }
       }
     }
   }
   assert(SpillPoint != Insts.end());
   assert(FillPoint != Insts.end());
   ++FillPoint;
   // TODO(stichnot): Randomize instead of *.begin() which maps to find_first().
@@ skipping 24 matching lines @@
       Moved = true;
     } else if (!Item->rangeOverlapsStart(Cur)) {
       // Move Item from Active to Inactive list.
       dumpLiveRangeTrace("Inactivating ", Item);
       moveItem(Active, Index, Inactive);
       Moved = true;
     }
     if (Moved) {
       // Decrement Item from RegUses[].
       assert(Item->hasRegTmp());
-      const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+      const auto &Aliases = *RegAliases[Item->getRegNumTmp()];
       for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
         --RegUses[RegAlias];
         assert(RegUses[RegAlias] >= 0);
       }
     }
   }
 }
 
 void LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) {
   for (SizeT I = Inactive.size(); I > 0; --I) {
     const SizeT Index = I - 1;
     Variable *Item = Inactive[Index];
     Item->trimLiveRange(Cur->getLiveRange().getStart());
     if (Item->rangeEndsBefore(Cur)) {
       // Move Item from Inactive to Handled list.
       dumpLiveRangeTrace("Expiring     ", Item);
       moveItem(Inactive, Index, Handled);
     } else if (Item->rangeOverlapsStart(Cur)) {
       // Move Item from Inactive to Active list.
       dumpLiveRangeTrace("Reactivating ", Item);
       moveItem(Inactive, Index, Active);
       // Increment Item in RegUses[].
       assert(Item->hasRegTmp());
-      const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+      const auto &Aliases = *RegAliases[Item->getRegNumTmp()];
       for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
         assert(RegUses[RegAlias] >= 0);
         ++RegUses[RegAlias];
       }
     }
   }
 }
 
 // Infer register preference and allowable overlap. Only form a preference when
 // the current Variable has an unambiguous "first" definition. The preference is
@@ skipping 21 matching lines @@
   const bool IsSingleDefAssign =
       DefInst->isVarAssign() && !VMetadata->isMultiDef(Iter.Cur);
   FOREACH_VAR_IN_INST(SrcVar, *DefInst) {
     // Only consider source variables that have (so far) been assigned a
     // register.
     if (!SrcVar->hasRegTmp())
       continue;
 
     // That register must be one in the RegMask set, e.g. don't try to prefer
     // the stack pointer as a result of the stacksave intrinsic.
-    const llvm::SmallBitVector &Aliases = *RegAliases[SrcVar->getRegNumTmp()];
+    const auto &Aliases = *RegAliases[SrcVar->getRegNumTmp()];
     const int SrcReg = (Iter.RegMask & Aliases).find_first();
     if (SrcReg == -1)
       continue;
 
     if (FindOverlap && IsSingleDefAssign && !Iter.Free[SrcReg]) {
       // Don't bother trying to enable AllowOverlap if the register is already
       // free (hence the test on Iter.Free[SrcReg]).
       Iter.AllowOverlap = !overlapsDefs(Func, Iter.Cur, SrcVar);
     }
     if (Iter.AllowOverlap || Iter.Free[SrcReg]) {
@@ skipping 16 matching lines @@
         << " Overlap=" << Iter.AllowOverlap << "\n";
   }
 }
 
 // Remove registers from the Iter.Free[] list where an Inactive range overlaps
 // with the current range.
 void LinearScan::filterFreeWithInactiveRanges(IterationState &Iter) {
   for (const Variable *Item : Inactive) {
     if (!Item->rangeOverlaps(Iter.Cur))
       continue;
-    const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+    const auto &Aliases = *RegAliases[Item->getRegNumTmp()];
     for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
       // Don't assert(Iter.Free[RegAlias]) because in theory (though probably
       // never in practice) there could be two inactive variables that were
       // marked with AllowOverlap.
       Iter.Free[RegAlias] = false;
       Iter.FreeUnfiltered[RegAlias] = false;
       // Disable AllowOverlap if an Inactive variable, which is not Prefer,
       // shares Prefer's register, and has a definition within Cur's live range.
       if (Iter.AllowOverlap && Item != Iter.Prefer &&
           RegAlias == Iter.PreferReg && overlapsDefs(Func, Iter.Cur, Item)) {
@@ skipping 11 matching lines @@
 // O(N^2) algorithm into expected linear complexity.
 void LinearScan::filterFreeWithPrecoloredRanges(IterationState &Iter) {
   // TODO(stichnot): Partition UnhandledPrecolored according to register class,
   // to restrict the number of overlap comparisons needed.
   for (Variable *Item : reverse_range(UnhandledPrecolored)) {
     assert(Item->hasReg());
     if (Iter.Cur->rangeEndsBefore(Item))
       break;
     if (!Item->rangeOverlaps(Iter.Cur))
       continue;
-    const llvm::SmallBitVector &Aliases =
+    const auto &Aliases =
         *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp()
     for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
       Iter.Weights[RegAlias].setWeight(RegWeight::Inf);
       Iter.Free[RegAlias] = false;
       Iter.FreeUnfiltered[RegAlias] = false;
       Iter.PrecoloredUnhandledMask[RegAlias] = true;
       // Disable Iter.AllowOverlap if the preferred register is one of these
       // pre-colored unhandled overlapping ranges.
       if (Iter.AllowOverlap && RegAlias == Iter.PreferReg) {
         Iter.AllowOverlap = false;
         dumpDisableOverlap(Func, Item, "PrecoloredUnhandled");
       }
     }
   }
 }
 
 void LinearScan::allocatePrecoloredRegister(Variable *Cur) {
   const auto RegNum = Cur->getRegNum();
   // RegNumTmp should have already been set above.
   assert(Cur->getRegNumTmp() == RegNum);
   dumpLiveRangeTrace("Precoloring  ", Cur);
   Active.push_back(Cur);
-  const llvm::SmallBitVector &Aliases = *RegAliases[RegNum];
+  const auto &Aliases = *RegAliases[RegNum];
   for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
     assert(RegUses[RegAlias] >= 0);
     ++RegUses[RegAlias];
   }
   assert(!UnhandledPrecolored.empty());
   assert(UnhandledPrecolored.back() == Cur);
   UnhandledPrecolored.pop_back();
 }
 
 void LinearScan::allocatePreferredRegister(IterationState &Iter) {
   Iter.Cur->setRegNumTmp(Iter.PreferReg);
   dumpLiveRangeTrace("Preferring   ", Iter.Cur);
-  const llvm::SmallBitVector &Aliases = *RegAliases[Iter.PreferReg];
+  const auto &Aliases = *RegAliases[Iter.PreferReg];
   for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
     assert(RegUses[RegAlias] >= 0);
     ++RegUses[RegAlias];
   }
   Active.push_back(Iter.Cur);
 }
 
 void LinearScan::allocateFreeRegister(IterationState &Iter, bool Filtered) {
   const RegNumT RegNum =
       *RegNumBVIter(Filtered ? Iter.Free : Iter.FreeUnfiltered).begin();
   Iter.Cur->setRegNumTmp(RegNum);
   if (Filtered)
     dumpLiveRangeTrace("Allocating Y ", Iter.Cur);
   else
     dumpLiveRangeTrace("Allocating X ", Iter.Cur);
-  const llvm::SmallBitVector &Aliases = *RegAliases[RegNum];
+  const auto &Aliases = *RegAliases[RegNum];
   for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
     assert(RegUses[RegAlias] >= 0);
     ++RegUses[RegAlias];
   }
   Active.push_back(Iter.Cur);
 }
 
 void LinearScan::handleNoFreeRegisters(IterationState &Iter) {
   // Check Active ranges.
   for (const Variable *Item : Active) {
     assert(Item->rangeOverlaps(Iter.Cur));
     assert(Item->hasRegTmp());
-    const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+    const auto &Aliases = *RegAliases[Item->getRegNumTmp()];
     // We add the Item's weight to each alias/subregister to represent that,
     // should we decide to pick any of them, then we would incur that many
     // memory accesses.
     RegWeight W = Item->getWeight(Func);
     for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
       Iter.Weights[RegAlias].addWeight(W);
     }
   }
   // Same as above, but check Inactive ranges instead of Active.
   for (const Variable *Item : Inactive) {
     if (!Item->rangeOverlaps(Iter.Cur))
       continue;
     assert(Item->hasRegTmp());
-    const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+    const auto &Aliases = *RegAliases[Item->getRegNumTmp()];
     RegWeight W = Item->getWeight(Func);
     for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
       Iter.Weights[RegAlias].addWeight(W);
     }
   }
 
   // All the weights are now calculated. Find the register with smallest weight.
   int32_t MinWeightIndex = findMinWeightIndex(Iter.RegMask, Iter.Weights);
 
   if (Iter.Cur->getWeight(Func) <= Iter.Weights[MinWeightIndex]) {
@@ skipping 33 matching lines @@
                      Iter.Cur->getName(Func));
       Handled.push_back(Iter.Cur);
       return;
     }
     // At this point, MinWeightIndex points to a valid reserve register to
     // reallocate to Iter.Cur, so drop into the eviction code.
   }
 
   // Evict all live ranges in Active that register number MinWeightIndex is
   // assigned to.
-  const llvm::SmallBitVector &Aliases = *RegAliases[MinWeightIndex];
+  const auto &Aliases = *RegAliases[MinWeightIndex];
   for (SizeT I = Active.size(); I > 0; --I) {
     const SizeT Index = I - 1;
     Variable *Item = Active[Index];
     const auto RegNum = Item->getRegNumTmp();
     if (Aliases[RegNum]) {
       dumpLiveRangeTrace("Evicting A   ", Item);
-      const llvm::SmallBitVector &Aliases = *RegAliases[RegNum];
+      const auto &Aliases = *RegAliases[RegNum];
       for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
         --RegUses[RegAlias];
         assert(RegUses[RegAlias] >= 0);
       }
       Item->setRegNumTmp(RegNumT());
       moveItem(Active, Index, Handled);
       Evicted.push_back(Item);
     }
   }
   // Do the same for Inactive.
@@ skipping 17 matching lines @@
   // Assign the register to Cur.
   Iter.Cur->setRegNumTmp(RegNumT::fromInt(MinWeightIndex));
   for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
     assert(RegUses[RegAlias] >= 0);
     ++RegUses[RegAlias];
   }
   Active.push_back(Iter.Cur);
   dumpLiveRangeTrace("Allocating Z ", Iter.Cur);
 }
 
-void LinearScan::assignFinalRegisters(
-    const llvm::SmallBitVector &RegMaskFull,
-    const llvm::SmallBitVector &PreDefinedRegisters, bool Randomized) {
+void LinearScan::assignFinalRegisters(const SmallBitVector &RegMaskFull,
+                                      const SmallBitVector &PreDefinedRegisters,
+                                      bool Randomized) {
   const size_t NumRegisters = RegMaskFull.size();
   llvm::SmallVector<RegNumT, REGS_SIZE> Permutation(NumRegisters);
   if (Randomized) {
     // Create a random number generator for regalloc randomization. Merge
     // function's sequence and Kind value as the Salt. Because regAlloc() is
     // called twice under O2, the second time with RAK_Phi, we check Kind ==
     // RAK_Phi to determine the lowest-order bit to make sure the Salt is
     // different.
     uint64_t Salt =
         (Func->getSequenceNumber() << 1) ^ (Kind == RAK_Phi ? 0u : 1u);
@@ skipping 31 matching lines @@
 
 // Implements the linear-scan algorithm. Based on "Linear Scan Register
 // Allocation in the Context of SSA Form and Register Constraints" by Hanspeter
 // Mössenböck and Michael Pfeiffer,
 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF. This implementation is
 // modified to take affinity into account and allow two interfering variables to
 // share the same register in certain cases.
 //
 // Requires running Cfg::liveness(Liveness_Intervals) in preparation. Results
 // are assigned to Variable::RegNum for each Variable.
-void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull,
-                      bool Randomized) {
+void LinearScan::scan(const SmallBitVector &RegMaskFull, bool Randomized) {
   TimerMarker T(TimerStack::TT_linearScan, Func);
   assert(RegMaskFull.any()); // Sanity check
   if (Verbose)
     Ctx->lockStr();
   Func->resetCurrentNode();
   const size_t NumRegisters = RegMaskFull.size();
-  llvm::SmallBitVector PreDefinedRegisters(NumRegisters);
+  SmallBitVector PreDefinedRegisters(NumRegisters);
   if (Randomized) {
     for (Variable *Var : UnhandledPrecolored) {
       PreDefinedRegisters[Var->getRegNum()] = true;
     }
   }
 
   // Build a LiveRange representing the Kills list.
   LiveRange KillsRange(Kills);
   KillsRange.untrim();
 
   // Reset the register use count.
   RegUses.resize(NumRegisters);
   std::fill(RegUses.begin(), RegUses.end(), 0);
 
   // Unhandled is already set to all ranges in increasing order of start points.
   assert(Active.empty());
   assert(Inactive.empty());
   assert(Handled.empty());
   const TargetLowering::RegSetMask RegsInclude =
       TargetLowering::RegSet_CallerSave;
   const TargetLowering::RegSetMask RegsExclude = TargetLowering::RegSet_None;
-  const llvm::SmallBitVector KillsMask =
+  const SmallBitVector KillsMask =
       Target->getRegisterSet(RegsInclude, RegsExclude);
 
   // Allocate memory once outside the loop.
   IterationState Iter;
   Iter.Weights.reserve(NumRegisters);
   Iter.PrecoloredUnhandledMask.reserve(NumRegisters);
 
   while (!Unhandled.empty()) {
     Iter.Cur = Unhandled.back();
     Unhandled.pop_back();
@@ skipping 25 matching lines @@
         Iter.FreeUnfiltered[i] = false;
       }
     }
 
     findRegisterPreference(Iter);
     filterFreeWithInactiveRanges(Iter);
 
     // Disable AllowOverlap if an Active variable, which is not Prefer, shares
     // Prefer's register, and has a definition within Cur's live range.
     if (Iter.AllowOverlap) {
-      const llvm::SmallBitVector &Aliases = *RegAliases[Iter.PreferReg];
+      const auto &Aliases = *RegAliases[Iter.PreferReg];
       for (const Variable *Item : Active) {
         const RegNumT RegNum = Item->getRegNumTmp();
         if (Item != Iter.Prefer && Aliases[RegNum] &&
             overlapsDefs(Func, Iter.Cur, Item)) {
           Iter.AllowOverlap = false;
           dumpDisableOverlap(Func, Item, "Active");
         }
       }
     }
 
@@ skipping 96 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice