Subzero. Changes the Register Allocator so that it is aware of register

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 207 matching lines @@
 }
 
 void LinearScan::init(RegAllocKind Kind) {
   this->Kind = Kind;
   Unhandled.clear();
   UnhandledPrecolored.clear();
   Handled.clear();
   Inactive.clear();
   Active.clear();
 
+  Target = Func->getTarget();

[Jim Stichnoth, 2015/09/04 16:53:10]

Actually, Target is probably better initialized in the ctor, similar to Ctx.

[John, 2015/09/04 17:32:25]

Done.

+  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();
@@ skipping 51 matching lines @@
     if (I->getNumber() == Start)
       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())
           Iter.RegMask[Var->getRegNumTmp()] = false;

[jvoung (off chromium), 2015/09/04 16:14:46]

Do you need to go over the aliases here too?

[Jim Stichnoth, 2015/09/04 16:38:51]

Good catch, I think the aliases do need to be removed here.

[John, 2015/09/04 17:32:25]

Done.

       }
     }
   }
   assert(SpillPoint != Insts.end());
   assert(FillPoint != Insts.end());
   ++FillPoint;
   // TODO(stichnot): Randomize instead of find_first().
   int32_t RegNum = Iter.RegMask.find_first();
   assert(RegNum != -1);
   Iter.Cur->setRegNumTmp(RegNum);
@@ skipping 23 matching lines @@
       Moved = true;
     } else if (!Item->rangeOverlapsStart(Cur)) {
       // Move Item from Active to Inactive list.
       dumpLiveRangeTrace("Inactivating ", Cur);
       moveItem(Active, Index, Inactive);
       Moved = true;
     }
     if (Moved) {
       // Decrement Item from RegUses[].
       assert(Item->hasRegTmp());
-      int32_t RegNum = Item->getRegNumTmp();
-      --RegUses[RegNum];
-      assert(RegUses[RegNum] >= 0);
+      const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+      for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;

[Jim Stichnoth, 2015/09/04 00:10:20]

So I greatly prefer using int32_t rather than int.  Unfortunately,
SmallBitVector.h chooses to use int for the return value of find_first() and
find_next().  I wonder if it's reasonable to typedef something to int and use it
for these SmallBitVector accesses, so that the type actually matches yet we
minimize our explicit use of int.

[John, 2015/09/04 17:32:25]

This is an excellent case where using auto is superior to **anything** (ok,
maybe using decltype() magic would also work, but... yikes.)

+           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     ", Cur);
       moveItem(Inactive, Index, Handled);
     } else if (Item->rangeOverlapsStart(Cur)) {
       // Move Item from Inactive to Active list.
       dumpLiveRangeTrace("Reactivating ", Cur);
       moveItem(Inactive, Index, Active);
       // Increment Item in RegUses[].
       assert(Item->hasRegTmp());
-      int32_t RegNum = Item->getRegNumTmp();
-      assert(RegUses[RegNum] >= 0);
-      ++RegUses[RegNum];
+      const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+      for (int32_t 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
@@ skipping 46 matching lines @@
       }
     }
   }
 }
 
 // Remove registers from the 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)) {
       int32_t RegNum = Item->getRegNumTmp();

[jvoung (off chromium), 2015/09/04 16:14:46]

Do you need to go over the aliases here too?

[Jim Stichnoth, 2015/09/04 16:38:51]

Yeah, I think so...

[John, 2015/09/04 17:32:25]

Done.

       // Don't assert(Free[RegNum]) because in theory (though probably never in
       // practice) there could be two inactive variables that were marked with
       // AllowOverlap.
       Iter.Free[RegNum] = 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 &&
           RegNum == Iter.PreferReg && overlapsDefs(Func, Iter.Cur, Item)) {
         Iter.AllowOverlap = false;
         dumpDisableOverlap(Func, Item, "Inactive");
       }
     }
   }
 }
 
 // Remove registers from the 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) {
   for (Variable *Item : reverse_range(UnhandledPrecolored)) {
     assert(Item->hasReg());
     if (Iter.Cur->rangeEndsBefore(Item))
       break;
     if (Item->rangeOverlaps(Iter.Cur)) {
-      int32_t ItemReg = Item->getRegNum(); // Note: not getRegNumTmp()
-      Iter.Weights[ItemReg].setWeight(RegWeight::Inf);
-      Iter.Free[ItemReg] = false;
-      Iter.PrecoloredUnhandledMask[ItemReg] = true;
-      // Disable Iter.AllowOverlap if the preferred register is one of these
-      // pre-colored unhandled overlapping ranges.
-      if (Iter.AllowOverlap && ItemReg == Iter.PreferReg) {
-        Iter.AllowOverlap = false;
-        dumpDisableOverlap(Func, Item, "PrecoloredUnhandled");
+      const llvm::SmallBitVector &Aliases =
+          *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp()
+      for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+           RegAlias = Aliases.find_next(RegAlias)) {
+        Iter.Weights[RegAlias].setWeight(RegWeight::Inf);
+        Iter.Free[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) {
   int32_t RegNum = Cur->getRegNum();
   // RegNumTmp should have already been set above.
   assert(Cur->getRegNumTmp() == RegNum);
   dumpLiveRangeTrace("Precoloring  ", Cur);
   Active.push_back(Cur);
-  assert(RegUses[RegNum] >= 0);
-  ++RegUses[RegNum];
+  const llvm::SmallBitVector &Aliases = *RegAliases[RegNum];
+  for (int32_t 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);
-  assert(RegUses[Iter.PreferReg] >= 0);
-  ++RegUses[Iter.PreferReg];
+  const llvm::SmallBitVector &Aliases = *RegAliases[Iter.PreferReg];
+  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);
 }
 
 void LinearScan::allocateFreeRegister(IterationState &Iter) {
   int32_t RegNum = Iter.Free.find_first();
   Iter.Cur->setRegNumTmp(RegNum);
   dumpLiveRangeTrace("Allocating   ", Iter.Cur);
-  assert(RegUses[RegNum] >= 0);
-  ++RegUses[RegNum];
+  const llvm::SmallBitVector &Aliases = *RegAliases[RegNum];
+  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);
 }
 
 void LinearScan::handleNoFreeRegisters(IterationState &Iter) {
   // Check Active ranges.
   for (const Variable *Item : Active) {
     assert(Item->rangeOverlaps(Iter.Cur));
-    int32_t RegNum = Item->getRegNumTmp();
     assert(Item->hasRegTmp());
-    Iter.Weights[RegNum].addWeight(Item->getWeight(Func));
+    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;
+         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) {
-    int32_t RegNum = Item->getRegNumTmp();
+    if (!Item->rangeOverlaps(Iter.Cur))
+      continue;
     assert(Item->hasRegTmp());
-    if (Item->rangeOverlaps(Iter.Cur))
-      Iter.Weights[RegNum].addWeight(Item->getWeight(Func));
+    const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+    RegWeight W = Item->getWeight(Func);
+    for (int32_t 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 = Iter.RegMask.find_first();
   // MinWeightIndex must be valid because of the initial RegMask.any() test.
   assert(MinWeightIndex >= 0);
   for (SizeT i = MinWeightIndex + 1; i < Iter.Weights.size(); ++i) {
     if (Iter.RegMask[i] && Iter.Weights[i] < Iter.Weights[MinWeightIndex])
       MinWeightIndex = i;
@@ skipping 11 matching lines @@
                        "infinite-weight live range");
     }
   } else {
     // Evict all live ranges in Active that register number MinWeightIndex is
     // assigned to.
     for (SizeT I = Active.size(); I > 0; --I) {
       const SizeT Index = I - 1;
       Variable *Item = Active[Index];
       if (Item->getRegNumTmp() == MinWeightIndex) {
         dumpLiveRangeTrace("Evicting     ", Item);
-        --RegUses[MinWeightIndex];
-        assert(RegUses[MinWeightIndex] >= 0);
+        const llvm::SmallBitVector &Aliases = *RegAliases[MinWeightIndex];
+        for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+             RegAlias = Aliases.find_next(RegAlias)) {
+          --RegUses[RegAlias];
+          assert(RegUses[RegAlias] >= 0);
+        }
         Item->setRegNumTmp(Variable::NoRegister);
         moveItem(Active, Index, Handled);
       }
     }
     // 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 (Item->getRegNumTmp() == MinWeightIndex &&
           Item->rangeOverlaps(Iter.Cur)) {
         dumpLiveRangeTrace("Evicting     ", Item);
         Item->setRegNumTmp(Variable::NoRegister);
         moveItem(Inactive, Index, Handled);
       }
     }
     // Assign the register to Cur.
     Iter.Cur->setRegNumTmp(MinWeightIndex);
-    assert(RegUses[MinWeightIndex] >= 0);
-    ++RegUses[MinWeightIndex];
+    const llvm::SmallBitVector &Aliases = *RegAliases[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);
     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);
   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);
     Func->getTarget()->makeRandomRegisterPermutation(

[Jim Stichnoth, 2015/09/04 16:50:17]

Can you change this and basically all Func->getTarget() instances to just
Target?

[John, 2015/09/04 17:32:25]

Done.

         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;
 
     if (Randomized && Item->hasRegTmp() && !Item->hasReg()) {
@@ skipping 220 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice