Subzero: Use a proper RegNumT type instead of int32_t/SizeT.

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 52 matching lines @@
     Str << "," << Defs[i]->getNumber();
   }
   Str << "\n";
 }
 
 void dumpLiveRange(const Variable *Var, const Cfg *Func) {
   if (!BuildDefs::dump())
     return;
   Ostream &Str = Func->getContext()->getStrDump();
   char buf[30];
-  snprintf(buf, llvm::array_lengthof(buf), "%2d", Var->getRegNumTmp());
+  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 llvm::SmallVector<RegWeight, LinearScan::REGS_SIZE> &Weights) {
-  int32_t MinWeightIndex = RegMask.find_first();
+  int MinWeightIndex = RegMask.find_first();
   assert(MinWeightIndex >= 0);
-  for (int32_t i = RegMask.find_next(MinWeightIndex); i != -1;
+  for (int i = RegMask.find_next(MinWeightIndex); i != -1;
        i = RegMask.find_next(i)) {
     if (Weights[i] < Weights[MinWeightIndex])
       MinWeightIndex = i;
   }
   return MinWeightIndex;
 }
 
 } // end of anonymous namespace
 
 LinearScan::LinearScan(Cfg *Func)
@@ skipping 312 matching lines @@
     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()];
-        for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+        for (int RegAlias = Aliases.find_first(); RegAlias >= 0;
              RegAlias = Aliases.find_next(RegAlias)) {
           Iter.RegMask[RegAlias] = false;
         }
       }
     }
   }
   assert(SpillPoint != Insts.end());
   assert(FillPoint != Insts.end());
   ++FillPoint;
   // TODO(stichnot): Randomize instead of find_first().
-  int32_t RegNum = Iter.RegMask.find_first();
+  int RegNum = Iter.RegMask.find_first();
   assert(RegNum != -1);
   Iter.Cur->setRegNumTmp(RegNum);
   Variable *Preg = Target->getPhysicalRegister(RegNum, Iter.Cur->getType());
   // TODO(stichnot): Add SpillLoc to VariablesMetadata tracking so that SpillLoc
   // is correctly identified as !isMultiBlock(), reducing stack frame size.
   Variable *SpillLoc = Func->makeVariable(Iter.Cur->getType());
   // Add "reg=FakeDef;spill=reg" before SpillPoint
   Target->lowerInst(Node, SpillPoint, InstFakeDef::create(Func, Preg));
   Target->lowerInst(Node, SpillPoint, InstAssign::create(Func, SpillLoc, Preg));
   // add "reg=spill;FakeUse(reg)" before FillPoint
@@ skipping 15 matching lines @@
     } 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()];
-      for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+      for (int RegAlias = Aliases.find_first(); RegAlias >= 0;
            RegAlias = Aliases.find_next(RegAlias)) {
         --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()];
-      for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+      for (int RegAlias = Aliases.find_first(); RegAlias >= 0;
            RegAlias = Aliases.find_next(RegAlias)) {
         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
 // some source Variable of the defining instruction that either is assigned a
 // register that is currently free, or that is assigned a register that is not
 // free but overlap is allowed. Overlap is allowed when the Variable under
 // consideration is single-definition, and its definition is a simple assignment
 // - i.e., the register gets copied/aliased but is never modified.  Furthermore,
 // overlap is only allowed when preferred Variable definition instructions do
 // not appear within the current Variable's live range.
 void LinearScan::findRegisterPreference(IterationState &Iter) {
   Iter.Prefer = nullptr;
-  Iter.PreferReg = Variable::NoRegister;
+  Iter.PreferReg = RegNumT::NoRegister;
   Iter.AllowOverlap = false;
 
   if (!FindPreference)
     return;
 
   VariablesMetadata *VMetadata = Func->getVMetadata();
   const Inst *DefInst = VMetadata->getFirstDefinitionSingleBlock(Iter.Cur);
   if (DefInst == nullptr)
     return;
 
   assert(DefInst->getDest() == Iter.Cur);
   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 int32_t SrcReg = (Iter.RegMask & Aliases).find_first();
+    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]) {
       Iter.Prefer = SrcVar;
@@ skipping 17 matching lines @@
 }
 
 // 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()];
     // TODO(stichnot): Do this with bitvector ops, not a loop, for efficiency.
-    for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+    for (int RegAlias = Aliases.find_first(); RegAlias >= 0;
          RegAlias = Aliases.find_next(RegAlias)) {
       // Don't assert(Iter.Free[RegNum]) 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)) {
+          RegNumT(RegAlias) == Iter.PreferReg &&
+          overlapsDefs(Func, Iter.Cur, Item)) {
         Iter.AllowOverlap = false;
         dumpDisableOverlap(Func, Item, "Inactive");
       }
     }
   }
 }
 
 // Remove registers from the Iter.Free[] list where an Unhandled pre-colored
 // range overlaps with the current range, and set those registers to infinite
 // weight so that they aren't candidates for eviction.
 // Cur->rangeEndsBefore(Item) is an early exit check that turns a guaranteed
 // 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 =
         *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp()
-    for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+    for (int RegAlias = Aliases.find_first(); RegAlias >= 0;
          RegAlias = Aliases.find_next(RegAlias)) {
       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) {
+      if (Iter.AllowOverlap && RegNumT(RegAlias) == Iter.PreferReg) {
         Iter.AllowOverlap = false;
         dumpDisableOverlap(Func, Item, "PrecoloredUnhandled");
       }
     }
   }
 }
 
 void LinearScan::allocatePrecoloredRegister(Variable *Cur) {
-  int32_t RegNum = Cur->getRegNum();
+  RegNumT 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];
-  for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+  for (int RegAlias = Aliases.find_first(); RegAlias >= 0;
        RegAlias = Aliases.find_next(RegAlias)) {
     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];
-  for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+  for (int RegAlias = Aliases.find_first(); RegAlias >= 0;
        RegAlias = Aliases.find_next(RegAlias)) {
     assert(RegUses[RegAlias] >= 0);
     ++RegUses[RegAlias];
   }
   Active.push_back(Iter.Cur);
 }
 
 void LinearScan::allocateFreeRegister(IterationState &Iter, bool Filtered) {
-  const int32_t RegNum =
+  const RegNumT RegNum =
       Filtered ? Iter.Free.find_first() : Iter.FreeUnfiltered.find_first();
   Iter.Cur->setRegNumTmp(RegNum);
   if (Filtered)
     dumpLiveRangeTrace("Allocating   ", Iter.Cur);
   else
     dumpLiveRangeTrace("Allocating X ", Iter.Cur);
   const llvm::SmallBitVector &Aliases = *RegAliases[RegNum];
-  for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+  for (int RegAlias = Aliases.find_first(); RegAlias >= 0;
        RegAlias = Aliases.find_next(RegAlias)) {
     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()];
     // 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 (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+    for (int RegAlias = Aliases.find_first(); RegAlias >= 0;
          RegAlias = Aliases.find_next(RegAlias)) {
       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()];
     RegWeight W = Item->getWeight(Func);
-    for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+    for (int RegAlias = Aliases.find_first(); RegAlias >= 0;
          RegAlias = Aliases.find_next(RegAlias)) {
       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]) {
     if (!Iter.Cur->mustHaveReg()) {
@@ skipping 36 matching lines @@
     // 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];
   for (SizeT I = Active.size(); I > 0; --I) {
     const SizeT Index = I - 1;
     Variable *Item = Active[Index];
-    int32_t RegNum = Item->getRegNumTmp();
+    RegNumT RegNum = Item->getRegNumTmp();
     if (Aliases[RegNum]) {
       dumpLiveRangeTrace("Evicting A   ", Item);
       const llvm::SmallBitVector &Aliases = *RegAliases[RegNum];
-      for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+      for (int RegAlias = Aliases.find_first(); RegAlias >= 0;
            RegAlias = Aliases.find_next(RegAlias)) {
         --RegUses[RegAlias];
         assert(RegUses[RegAlias] >= 0);
       }
-      Item->setRegNumTmp(Variable::NoRegister);
+      Item->setRegNumTmp(RegNumT::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);
+      Item->setRegNumTmp(RegNumT::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;
+  for (int RegAlias = Aliases.find_first(); RegAlias >= 0;
        RegAlias = Aliases.find_next(RegAlias)) {
     assert(RegUses[RegAlias] >= 0);
     ++RegUses[RegAlias];
   }
   Active.push_back(Iter.Cur);
   dumpLiveRangeTrace("Allocating   ", Iter.Cur);
 }
 
 void LinearScan::assignFinalRegisters(
     const llvm::SmallBitVector &RegMaskFull,
     const llvm::SmallBitVector &PreDefinedRegisters, bool Randomized) {
   const size_t NumRegisters = RegMaskFull.size();
-  llvm::SmallVector<int32_t, REGS_SIZE> Permutation(NumRegisters);
+  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);
     Target->makeRandomRegisterPermutation(
         Permutation, PreDefinedRegisters | ~RegMaskFull, Salt);
   }
 
   // Finish up by setting RegNum = RegNumTmp (or a random permutation thereof)
   // for each Variable.
   for (Variable *Item : Handled) {
-    int32_t RegNum = Item->getRegNumTmp();
-    int32_t AssignedRegNum = RegNum;
+    RegNumT RegNum = Item->getRegNumTmp();
+    RegNumT AssignedRegNum = RegNum;
 
     if (Randomized && Item->hasRegTmp() && !Item->hasReg()) {
       AssignedRegNum = Permutation[RegNum];
     }
     if (BuildDefs::dump() && Verbose) {
       Ostream &Str = Ctx->getStrDump();
       if (!Item->hasRegTmp()) {
         Str << "Not assigning ";
         Item->dump(Func);
         Str << "\n";
@@ skipping 90 matching lines @@
     }
 
     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];
       for (const Variable *Item : Active) {
-        int32_t RegNum = Item->getRegNumTmp();
+        RegNumT RegNum = Item->getRegNumTmp();
         if (Item != Iter.Prefer && Aliases[RegNum] &&
             overlapsDefs(Func, Iter.Cur, Item)) {
           Iter.AllowOverlap = false;
           dumpDisableOverlap(Func, Item, "Active");
         }
       }
     }
 
     Iter.Weights.resize(Iter.RegMask.size());
     std::fill(Iter.Weights.begin(), Iter.Weights.end(), RegWeight());
 
     Iter.PrecoloredUnhandledMask.resize(Iter.RegMask.size());
     Iter.PrecoloredUnhandledMask.reset();
 
     filterFreeWithPrecoloredRanges(Iter);
 
     // Remove scratch registers from the Iter.Free[] list, and mark their
     // Iter.Weights[] as infinite, if KillsRange overlaps Cur's live range.
     constexpr bool UseTrimmed = true;
     if (Iter.Cur->getLiveRange().overlaps(KillsRange, UseTrimmed)) {
       Iter.Free.reset(KillsMask);
       Iter.FreeUnfiltered.reset(KillsMask);
       for (int i = KillsMask.find_first(); i != -1;
            i = KillsMask.find_next(i)) {
         Iter.Weights[i].setWeight(RegWeight::Inf);
-        if (Iter.PreferReg == i)
+        if (Iter.PreferReg == RegNumT(i))
           Iter.AllowOverlap = false;
       }
     }
 
     // Print info about physical register availability.
     if (BuildDefs::dump() && Verbose) {
       Ostream &Str = Ctx->getStrDump();
-      for (SizeT i = 0; i < Iter.RegMask.size(); ++i) {
-        if (Iter.RegMaskUnfiltered[i]) {
-          Str << Target->getRegName(i, Iter.Cur->getType())
-              << "(U=" << RegUses[i] << ",F=" << Iter.Free[i]
-              << ",P=" << Iter.PrecoloredUnhandledMask[i] << ") ";
-        }
+      for (int i = Iter.RegMaskUnfiltered.find_first(); i != -1;
+           i = Iter.RegMaskUnfiltered.find_next(i)) {

[Eric Holk, 2016/02/08 19:37:09]

A lot of the changes in this file seem kind of independent of the change to
RegNumT. Am I missing the connection, or would it be better to consider
splitting into two CLs?

[Jim Stichnoth, 2016/02/09 19:33:39]

True - while tracking down all the changes, I also took the opportunity to do
proper iteration over bitvector entries, including fixing int32_t==>int to match
the llvm::BitVector API.

I can revert that if you like, but TBH I'd rather just roll it in here. :)

[Eric Holk, 2016/02/10 01:11:30]

Yeah, that's fine with me. It's a pain to split up CLs!

+        Str << Target->getRegName(i, Iter.Cur->getType()) << "(U=" << RegUses[i]
+            << ",F=" << Iter.Free[i] << ",P=" << Iter.PrecoloredUnhandledMask[i]
+            << ") ";
       }
       Str << "\n";
     }
 
     if (Iter.Prefer && (Iter.AllowOverlap || Iter.Free[Iter.PreferReg])) {
       // First choice: a preferred register that is either free or is allowed to
       // overlap with its linked variable.
       allocatePreferredRegister(Iter);
     } else if (Iter.Free.any()) {
       // Second choice: any free register.
@@ skipping 58 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice