aboutsummaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/RegAllocLinearScan.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/RegAllocLinearScan.cpp')
-rw-r--r--lib/CodeGen/RegAllocLinearScan.cpp151
1 files changed, 85 insertions, 66 deletions
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 6a303f6..81b9070 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -15,10 +15,10 @@
#include "VirtRegMap.h"
#include "VirtRegRewriter.h"
#include "Spiller.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Function.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
-#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
@@ -87,10 +87,22 @@ namespace {
"to skip."),
cl::init(0),
cl::Hidden);
-
+
struct RALinScan : public MachineFunctionPass {
static char ID;
RALinScan() : MachineFunctionPass(ID) {
+ initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
+ initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
+ initializeRegisterCoalescerAnalysisGroup(
+ *PassRegistry::getPassRegistry());
+ initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
+ initializePreAllocSplittingPass(*PassRegistry::getPassRegistry());
+ initializeLiveStacksPass(*PassRegistry::getPassRegistry());
+ initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
+ initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
+ initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
+ initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
+
// Initialize the queue to record recently-used registers.
if (NumRecentlyUsedRegs > 0)
RecentRegs.resize(NumRecentlyUsedRegs, 0);
@@ -125,8 +137,8 @@ namespace {
const TargetRegisterInfo* tri_;
const TargetInstrInfo* tii_;
BitVector allocatableRegs_;
+ BitVector reservedRegs_;
LiveIntervals* li_;
- LiveStacks* ls_;
MachineLoopInfo *loopInfo;
/// handled_ - Intervals are added to the handled_ set in the order of their
@@ -182,6 +194,8 @@ namespace {
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
+ AU.addRequired<AliasAnalysis>();
+ AU.addPreserved<AliasAnalysis>();
AU.addRequired<LiveIntervals>();
AU.addPreserved<SlotIndexes>();
if (StrongPHIElim)
@@ -192,12 +206,13 @@ namespace {
AU.addRequired<CalculateSpillWeights>();
if (PreSplitIntervals)
AU.addRequiredID(PreAllocSplittingID);
- AU.addRequired<LiveStacks>();
- AU.addPreserved<LiveStacks>();
+ AU.addRequiredID(LiveStacksID);
+ AU.addPreservedID(LiveStacksID);
AU.addRequired<MachineLoopInfo>();
AU.addPreserved<MachineLoopInfo>();
AU.addRequired<VirtRegMap>();
AU.addPreserved<VirtRegMap>();
+ AU.addRequiredID(MachineDominatorsID);
AU.addPreservedID(MachineDominatorsID);
MachineFunctionPass::getAnalysisUsage(AU);
}
@@ -335,6 +350,17 @@ namespace {
SmallVector<unsigned, 256> &inactiveCounts,
bool SkipDGRegs);
+ /// getFirstNonReservedPhysReg - return the first non-reserved physical
+ /// register in the register class.
+ unsigned getFirstNonReservedPhysReg(const TargetRegisterClass *RC) {
+ TargetRegisterClass::iterator aoe = RC->allocation_order_end(*mf_);
+ TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_);
+ while (i != aoe && reservedRegs_.test(*i))
+ ++i;
+ assert(i != aoe && "All registers reserved?!");
+ return *i;
+ }
+
void ComputeRelatedRegClasses();
template <typename ItTy>
@@ -358,8 +384,19 @@ namespace {
char RALinScan::ID = 0;
}
-INITIALIZE_PASS(RALinScan, "linearscan-regalloc",
- "Linear Scan Register Allocator", false, false);
+INITIALIZE_PASS_BEGIN(RALinScan, "linearscan-regalloc",
+ "Linear Scan Register Allocator", false, false)
+INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
+INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination)
+INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights)
+INITIALIZE_PASS_DEPENDENCY(PreAllocSplitting)
+INITIALIZE_PASS_DEPENDENCY(LiveStacks)
+INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
+INITIALIZE_AG_DEPENDENCY(RegisterCoalescer)
+INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_END(RALinScan, "linearscan-regalloc",
+ "Linear Scan Register Allocator", false, false)
void RALinScan::ComputeRelatedRegClasses() {
// First pass, add all reg classes to the union, and determine at least one
@@ -371,7 +408,7 @@ void RALinScan::ComputeRelatedRegClasses() {
for (TargetRegisterClass::iterator I = (*RCI)->begin(), E = (*RCI)->end();
I != E; ++I) {
HasAliases = HasAliases || *tri_->getAliasSet(*I) != 0;
-
+
const TargetRegisterClass *&PRC = OneClassForEachPhysReg[*I];
if (PRC) {
// Already processed this register. Just make sure we know that
@@ -382,7 +419,7 @@ void RALinScan::ComputeRelatedRegClasses() {
}
}
}
-
+
// Second pass, now that we know conservatively what register classes each reg
// belongs to, add info about aliases. We don't need to do this for targets
// without register aliases.
@@ -419,8 +456,7 @@ unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) {
unsigned CandReg;
{
MachineInstr *CopyMI;
- if (vni->def != SlotIndex() && vni->isDefAccurate() &&
- (CopyMI = li_->getInstructionFromIndex(vni->def)) && CopyMI->isCopy())
+ if ((CopyMI = li_->getInstructionFromIndex(vni->def)) && CopyMI->isCopy())
// Defined by a copy, try to extend SrcReg forward
CandReg = CopyMI->getOperand(1).getReg();
else if (TrivCoalesceEnds &&
@@ -464,8 +500,8 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
tri_ = tm_->getRegisterInfo();
tii_ = tm_->getInstrInfo();
allocatableRegs_ = tri_->getAllocatableSet(fn);
+ reservedRegs_ = tri_->getReservedRegs(fn);
li_ = &getAnalysis<LiveIntervals>();
- ls_ = &getAnalysis<LiveStacks>();
loopInfo = &getAnalysis<MachineLoopInfo>();
// We don't run the coalescer here because we have no reason to
@@ -482,9 +518,9 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
vrm_ = &getAnalysis<VirtRegMap>();
if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter());
-
+
spiller_.reset(createSpiller(*this, *mf_, *vrm_));
-
+
initIntervalSets();
linearScan();
@@ -538,7 +574,7 @@ void RALinScan::linearScan() {
// linear scan algorithm
DEBUG({
dbgs() << "********** LINEAR SCAN **********\n"
- << "********** Function: "
+ << "********** Function: "
<< mf_->getFunction()->getName() << '\n';
printIntervals("fixed", fixed_.begin(), fixed_.end());
});
@@ -625,8 +661,6 @@ void RALinScan::linearScan() {
// Look for physical registers that end up not being allocated even though
// register allocator had to spill other registers in its register class.
- if (ls_->getNumIntervals() == 0)
- return;
if (!vrm_->FindUnusedRegisters(li_))
return;
}
@@ -760,7 +794,8 @@ FindIntervalInVector(RALinScan::IntervalPtrs &IP, LiveInterval *LI) {
return IP.end();
}
-static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, SlotIndex Point){
+static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V,
+ SlotIndex Point){
for (unsigned i = 0, e = V.size(); i != e; ++i) {
RALinScan::IntervalPtr &IP = V[i];
LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
@@ -770,30 +805,6 @@ static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, SlotIndex Point)
}
}
-/// addStackInterval - Create a LiveInterval for stack if the specified live
-/// interval has been spilled.
-static void addStackInterval(LiveInterval *cur, LiveStacks *ls_,
- LiveIntervals *li_,
- MachineRegisterInfo* mri_, VirtRegMap &vrm_) {
- int SS = vrm_.getStackSlot(cur->reg);
- if (SS == VirtRegMap::NO_STACK_SLOT)
- return;
-
- const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
- LiveInterval &SI = ls_->getOrCreateInterval(SS, RC);
-
- VNInfo *VNI;
- if (SI.hasAtLeastOneValue())
- VNI = SI.getValNumInfo(0);
- else
- VNI = SI.getNextValue(SlotIndex(), 0, false,
- ls_->getVNInfoAllocator());
-
- LiveInterval &RI = li_->getInterval(cur->reg);
- // FIXME: This may be overly conservative.
- SI.MergeRangesInAsValue(RI, VNI);
-}
-
/// getConflictWeight - Return the number of conflicts between cur
/// live interval and defs and uses of Reg weighted by loop depthes.
static
@@ -832,7 +843,7 @@ void RALinScan::findIntervalsToSpill(LiveInterval *cur,
dbgs() << tri_->getName(Candidates[i].first) << " ";
dbgs() << "\n";
});
-
+
// Calculate the number of conflicts of each candidate.
for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
unsigned Reg = i->first->reg;
@@ -950,7 +961,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
if (cur->empty()) {
unsigned physReg = vrm_->getRegAllocPref(cur->reg);
if (!physReg)
- physReg = *RC->allocation_order_begin(*mf_);
+ physReg = getFirstNonReservedPhysReg(RC);
DEBUG(dbgs() << tri_->getName(physReg) << '\n');
// Note the register is not really in use.
vrm_->assignVirt2Phys(cur->reg, physReg);
@@ -970,8 +981,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
// one, e.g. X86::mov32to32_. These move instructions are not coalescable.
if (!vrm_->getRegAllocPref(cur->reg) && cur->hasAtLeastOneValue()) {
VNInfo *vni = cur->begin()->valno;
- if ((vni->def != SlotIndex()) && !vni->isUnused() &&
- vni->isDefAccurate()) {
+ if (!vni->isUnused()) {
MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
if (CopyMI && CopyMI->isCopy()) {
unsigned DstSubReg = CopyMI->getOperand(0).getSubReg();
@@ -1002,7 +1012,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
"Can only allocate virtual registers!");
const TargetRegisterClass *RegRC = mri_->getRegClass(Reg);
- // If this is not in a related reg class to the register we're allocating,
+ // If this is not in a related reg class to the register we're allocating,
// don't check it.
if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
cur->overlapsFrom(*i->first, i->second-1)) {
@@ -1011,7 +1021,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight));
}
}
-
+
// Speculatively check to see if we can get a register right now. If not,
// we know we won't be able to by adding more constraints. If so, we can
// check to see if it is valid. Doing an exhaustive search of the fixed_ list
@@ -1026,7 +1036,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
SmallSet<unsigned, 8> RegAliases;
for (const unsigned *AS = tri_->getAliasSet(physReg); *AS; ++AS)
RegAliases.insert(*AS);
-
+
bool ConflictsWithFixed = false;
for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
IntervalPtr &IP = fixed_[i];
@@ -1046,7 +1056,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
}
}
}
-
+
// Okay, the register picked by our speculative getFreePhysReg call turned
// out to be in use. Actually add all of the conflicting fixed registers to
// regUse_ so we can do an accurate query.
@@ -1058,7 +1068,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
LiveInterval *I = IP.first;
const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg];
- if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
+ if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
I->endIndex() > StartPosition) {
LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
IP.second = II;
@@ -1077,11 +1087,11 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
physReg = getFreePhysReg(cur);
}
}
-
+
// Restore the physical register tracker, removing information about the
// future.
restoreRegUses();
-
+
// If we find a free register, we are done: assign this virtual to
// the free physical register and add this interval to the active
// list.
@@ -1096,7 +1106,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
UpgradeRegister(physReg);
if (LiveInterval *NextReloadLI = hasNextReloadInterval(cur)) {
// "Downgrade" physReg to try to keep physReg from being allocated until
- // the next reload from the same SS is allocated.
+ // the next reload from the same SS is allocated.
mri_->setRegAllocationHint(NextReloadLI->reg, 0, physReg);
DowngradeRegister(cur, physReg);
}
@@ -1109,7 +1119,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
for (std::vector<std::pair<unsigned, float> >::iterator
I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I)
updateSpillWeights(SpillWeights, I->first, I->second, RC);
-
+
// for each interval in active, update spill weights.
for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
i != e; ++i) {
@@ -1119,7 +1129,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
reg = vrm_->getPhys(reg);
updateSpillWeights(SpillWeights, reg, i->first->weight, RC);
}
-
+
DEBUG(dbgs() << "\tassigning stack slot at interval "<< *cur << ":\n");
// Find a register to spill.
@@ -1133,17 +1143,22 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
e = RC->allocation_order_end(*mf_); i != e; ++i) {
unsigned reg = *i;
float regWeight = SpillWeights[reg];
- // Skip recently allocated registers.
+ // Don't even consider reserved regs.
+ if (reservedRegs_.test(reg))
+ continue;
+ // Skip recently allocated registers and reserved registers.
if (minWeight > regWeight && !isRecentlyUsed(reg))
Found = true;
RegsWeights.push_back(std::make_pair(reg, regWeight));
}
-
+
// If we didn't find a register that is spillable, try aliases?
if (!Found) {
for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
e = RC->allocation_order_end(*mf_); i != e; ++i) {
unsigned reg = *i;
+ if (reservedRegs_.test(reg))
+ continue;
// No need to worry about if the alias register size < regsize of RC.
// We are going to spill all registers that alias it anyway.
for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as)
@@ -1157,7 +1172,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
minWeight = RegsWeights[0].second;
if (minWeight == HUGE_VALF) {
// All registers must have inf weight. Just grab one!
- minReg = BestPhysReg ? BestPhysReg : *RC->allocation_order_begin(*mf_);
+ minReg = BestPhysReg ? BestPhysReg : getFirstNonReservedPhysReg(RC);
if (cur->weight == HUGE_VALF ||
li_->getApproximateInstructionCount(*cur) == 0) {
// Spill a physical register around defs and uses.
@@ -1206,7 +1221,6 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
spiller_->spill(cur, added, spillIs);
std::sort(added.begin(), added.end(), LISorter());
- addStackInterval(cur, ls_, li_, mri_, *vrm_);
if (added.empty())
return; // Early exit if all spills were folded.
@@ -1265,7 +1279,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
// The earliest start of a Spilled interval indicates up to where
// in handled we need to roll back
- assert(!spillIs.empty() && "No spill intervals?");
+ assert(!spillIs.empty() && "No spill intervals?");
SlotIndex earliestStart = spillIs[0]->beginIndex();
// Spill live intervals of virtual regs mapped to the physical register we
@@ -1281,7 +1295,6 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
if (sli->beginIndex() < earliestStart)
earliestStart = sli->beginIndex();
spiller_->spill(sli, added, spillIs);
- addStackInterval(sli, ls_, li_, mri_, *vrm_);
spilled.insert(sli->reg);
}
@@ -1414,6 +1427,9 @@ unsigned RALinScan::getFreePhysReg(LiveInterval* cur,
// Ignore "downgraded" registers.
if (SkipDGRegs && DowngradedRegs.count(Reg))
continue;
+ // Skip reserved registers.
+ if (reservedRegs_.test(Reg))
+ continue;
// Skip recently allocated registers.
if (isRegAvail(Reg) && !isRecentlyUsed(Reg)) {
FreeReg = Reg;
@@ -1442,6 +1458,9 @@ unsigned RALinScan::getFreePhysReg(LiveInterval* cur,
// Ignore "downgraded" registers.
if (SkipDGRegs && DowngradedRegs.count(Reg))
continue;
+ // Skip reserved registers.
+ if (reservedRegs_.test(Reg))
+ continue;
if (isRegAvail(Reg) && Reg < inactiveCounts.size() &&
FreeRegInactiveCount < inactiveCounts[Reg] && !isRecentlyUsed(Reg)) {
FreeReg = Reg;
@@ -1462,17 +1481,17 @@ unsigned RALinScan::getFreePhysReg(LiveInterval* cur,
unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
SmallVector<unsigned, 256> inactiveCounts;
unsigned MaxInactiveCount = 0;
-
+
const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
-
+
for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
i != e; ++i) {
unsigned reg = i->first->reg;
assert(TargetRegisterInfo::isVirtualRegister(reg) &&
"Can only allocate virtual registers!");
- // If this is not in a related reg class to the register we're allocating,
+ // If this is not in a related reg class to the register we're allocating,
// don't check it.
const TargetRegisterClass *RegRC = mri_->getRegClass(reg);
if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
@@ -1489,7 +1508,7 @@ unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
unsigned Preference = vrm_->getRegAllocPref(cur->reg);
if (Preference) {
DEBUG(dbgs() << "(preferred: " << tri_->getName(Preference) << ") ");
- if (isRegAvail(Preference) &&
+ if (isRegAvail(Preference) &&
RC->contains(Preference))
return Preference;
}
generated by cgit v1.1 at 2025-08-25 08:02:18 +0000