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 61 matching lines @@
   char buf[30];
   snprintf(buf, llvm::array_lengthof(buf), "%2d", Var->getRegNumTmp());
   Str << "R=" << buf << "  V=";
   Var->dump(Func);
   Str << "  Range=" << Var->getLiveRange();
 }
 
 } // end of anonymous namespace
 
 LinearScan::LinearScan(Cfg *Func)
-    : Func(Func), Ctx(Func->getContext()),
+    : Func(Func), Ctx(Func->getContext()), Target(Func->getTarget()),
       Verbose(BuildDefs::dump() && Func->isVerbose(IceV_LinearScan)) {}
 
 // Prepare for full register allocation of all variables.  We depend on
 // liveness analysis to have calculated live ranges.
 void LinearScan::initForGlobal() {
   TimerMarker T(TimerStack::TT_initUnhandled, Func);
   FindPreference = true;
   // For full register allocation, normally we want to enable FindOverlap
   // (meaning we look for opportunities for two overlapping live ranges to
   // safely share the same register).  However, we disable it for phi-lowering
@@ skipping 125 matching lines @@
 }
 
 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();
@@ skipping 50 matching lines @@
        I != E && (SpillPoint == E || FillPoint == E); ++I) {
     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;
+        if (!Var->hasRegTmp())
+          continue;
+        const llvm::SmallBitVector &Aliases = *RegAliases[Var->getRegNumTmp()];
+        for (int32_t 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();
   assert(RegNum != -1);
   Iter.Cur->setRegNumTmp(RegNum);
-  TargetLowering *Target = Func->getTarget();
   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
   Target->lowerInst(Node, FillPoint, InstAssign::create(Func, Preg, SpillLoc));
   Target->lowerInst(Node, FillPoint, InstFakeUse::create(Func, Preg));
@@ skipping 12 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;
+           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 45 matching lines @@
             << " Overlap=" << Iter.AllowOverlap << "\n";
       }
     }
   }
 }
 
 // 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();
+    if (!Item->rangeOverlaps(Iter.Cur))
+      continue;
+    const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+    for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+         RegAlias = Aliases.find_next(RegAlias)) {
       // 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;
+      Iter.Free[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 &&
-          RegNum == Iter.PreferReg && overlapsDefs(Func, Iter.Cur, Item)) {
+          RegAlias == 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(
+    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;
 
     if (Randomized && Item->hasRegTmp() && !Item->hasReg()) {
       AssignedRegNum = Permutation[RegNum];
     }
     if (Verbose) {
       Ostream &Str = Ctx->getStrDump();
       if (!Item->hasRegTmp()) {
         Str << "Not assigning ";
         Item->dump(Func);
         Str << "\n";
       } else {
         Str << (AssignedRegNum == Item->getRegNum() ? "Reassigning "
                                                     : "Assigning ")
-            << Func->getTarget()->getRegName(AssignedRegNum, IceType_i32)
-            << "(r" << AssignedRegNum << ") to ";
+            << Target->getRegName(AssignedRegNum, IceType_i32) << "(r"
+            << AssignedRegNum << ") to ";
         Item->dump(Func);
         Str << "\n";
       }
     }
     Item->setRegNum(AssignedRegNum);
   }
 }
 
 // Implements the linear-scan algorithm. Based on "Linear Scan Register
 // Allocation in the Context of SSA Form and Register Constraints" by Hanspeter
@@ skipping 29 matching lines @@
 
   // 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 =
-      Func->getTarget()->getRegisterSet(RegsInclude, RegsExclude);
+      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();
     dumpLiveRangeTrace("\nConsidering  ", Iter.Cur);
     Iter.RegMask =
-        RegMaskFull &
-        Func->getTarget()->getRegisterSetForType(Iter.Cur->getType());
+        RegMaskFull & Target->getRegisterSetForType(Iter.Cur->getType());
     KillsRange.trim(Iter.Cur->getLiveRange().getStart());
 
     // Check for pre-colored ranges. If Cur is pre-colored, it definitely gets
     // that register. Previously processed live ranges would have avoided that
     // register due to it being pre-colored. Future processed live ranges won't
     // evict that register because the live range has infinite weight.
     if (Iter.Cur->hasReg()) {
       allocatePrecoloredRegister(Iter.Cur);
       continue;
     }
@@ skipping 43 matching lines @@
         if (Iter.PreferReg == i)
           Iter.AllowOverlap = false;
       }
     }
 
     // Print info about physical register availability.
     if (Verbose) {
       Ostream &Str = Ctx->getStrDump();
       for (SizeT i = 0; i < Iter.RegMask.size(); ++i) {
         if (Iter.RegMask[i]) {
-          Str << Func->getTarget()->getRegName(i, IceType_i32)
-              << "(U=" << RegUses[i] << ",F=" << Iter.Free[i]
+          Str << Target->getRegName(i, IceType_i32) << "(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);
@@ skipping 69 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice