#define DEBUG_TYPE "regalloc"
#include "VirtRegMap.h"
+#include "VirtRegRewriter.h"
#include "Spiller.h"
#include "llvm/Function.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Compiler.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <set>
#include <queue>
#include <memory>
#include <cmath>
+
using namespace llvm;
STATISTIC(NumIters , "Number of iterations performed");
cl::desc("Pre-register allocation live interval splitting"),
cl::init(false), cl::Hidden);
+static cl::opt<bool>
+NewSpillFramework("new-spill-framework",
+ cl::desc("New spilling framework"),
+ cl::init(false), cl::Hidden);
+
static RegisterRegAlloc
linearscanRegAlloc("linearscan", "linear scan register allocator",
createLinearScanRegisterAllocator);
/// vrm_ - Tracks register assignments.
VirtRegMap* vrm_;
+ std::auto_ptr<VirtRegRewriter> rewriter_;
+
std::auto_ptr<Spiller> spiller_;
public:
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesCFG();
AU.addRequired<LiveIntervals>();
if (StrongPHIElim)
AU.addRequiredID(StrongPHIEliminationID);
}
void finalizeRegUses() {
+#ifndef NDEBUG
+ // Verify all the registers are "freed".
+ bool Error = false;
+ for (unsigned i = 0, e = tri_->getNumRegs(); i != e; ++i) {
+ if (regUse_[i] != 0) {
+ cerr << tri_->getName(i) << " is still in use!\n";
+ Error = true;
+ }
+ }
+ if (Error)
+ llvm_unreachable(0);
+#endif
regUse_.clear();
regUseBackUp_.clear();
}
/// getFreePhysReg - return a free physical register for this virtual
/// register interval if we have one, otherwise return 0.
unsigned getFreePhysReg(LiveInterval* cur);
- unsigned getFreePhysReg(const TargetRegisterClass *RC,
+ unsigned getFreePhysReg(LiveInterval* cur,
+ const TargetRegisterClass *RC,
unsigned MaxInactiveCount,
SmallVector<unsigned, 256> &inactiveCounts,
bool SkipDGRegs);
/// different register classes or because the coalescer was overly
/// conservative.
unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) {
- if ((cur.preference && cur.preference == Reg) || !cur.containsOneValue())
+ unsigned Preference = vrm_->getRegAllocPref(cur.reg);
+ if ((Preference && Preference == Reg) || !cur.containsOneValue())
return Reg;
VNInfo *vni = cur.begin()->valno;
- if (!vni->def || vni->def == ~1U || vni->def == ~0U)
+ if (!vni->def || vni->isUnused() || !vni->isDefAccurate())
return Reg;
MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
- unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+ unsigned SrcReg, DstReg, SrcSubReg, DstSubReg, PhysReg;
if (!CopyMI ||
!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg))
return Reg;
+ PhysReg = SrcReg;
if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
if (!vrm_->isAssignedReg(SrcReg))
return Reg;
- else
- SrcReg = vrm_->getPhys(SrcReg);
+ PhysReg = vrm_->getPhys(SrcReg);
}
- if (Reg == SrcReg)
+ if (Reg == PhysReg)
return Reg;
const TargetRegisterClass *RC = mri_->getRegClass(cur.reg);
- if (!RC->contains(SrcReg))
+ if (!RC->contains(PhysReg))
return Reg;
// Try to coalesce.
- if (!li_->conflictsWithPhysRegDef(cur, *vrm_, SrcReg)) {
- DOUT << "Coalescing: " << cur << " -> " << tri_->getName(SrcReg)
+ if (!li_->conflictsWithPhysRegDef(cur, *vrm_, PhysReg)) {
+ DOUT << "Coalescing: " << cur << " -> " << tri_->getName(PhysReg)
<< '\n';
vrm_->clearVirt(cur.reg);
- vrm_->assignVirt2Phys(cur.reg, SrcReg);
+ vrm_->assignVirt2Phys(cur.reg, PhysReg);
+
+ // Remove unnecessary kills since a copy does not clobber the register.
+ if (li_->hasInterval(SrcReg)) {
+ LiveInterval &SrcLI = li_->getInterval(SrcReg);
+ for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(cur.reg),
+ E = mri_->reg_end(); I != E; ++I) {
+ MachineOperand &O = I.getOperand();
+ if (!O.isUse() || !O.isKill())
+ continue;
+ MachineInstr *MI = &*I;
+ if (SrcLI.liveAt(li_->getDefIndex(li_->getInstructionIndex(MI))))
+ O.setIsKill(false);
+ }
+ }
+
++NumCoalesce;
- return SrcReg;
+ return PhysReg;
}
return Reg;
initRegUses();
vrm_ = &getAnalysis<VirtRegMap>();
- if (!spiller_.get()) spiller_.reset(createSpiller());
-
+ if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter());
+
+ if (NewSpillFramework) {
+ spiller_.reset(createSpiller(mf_, li_, ls_, vrm_));
+ }
+
initIntervalSets();
linearScan();
// Rewrite spill code and update the PhysRegsUsed set.
- spiller_->runOnMachineFunction(*mf_, *vrm_, li_);
+ rewriter_->runOnMachineFunction(*mf_, *vrm_, li_);
assert(unhandled_.empty() && "Unhandled live intervals remain!");
NextReloadMap.clear();
DowngradedRegs.clear();
DowngradeMap.clear();
+ spiller_.reset(0);
return true;
}
{
// linear scan algorithm
DOUT << "********** LINEAR SCAN **********\n";
- DOUT << "********** Function: " << mf_->getFunction()->getName() << '\n';
+ DEBUG(errs() << "********** Function: "
+ << mf_->getFunction()->getName() << '\n');
DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
// Ignore splited live intervals.
if (!isPhys && vrm_->getPreSplitReg(cur.reg))
continue;
+
for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end();
I != E; ++I) {
const LiveRange &LR = *I;
if (li_->findLiveInMBBs(LR.start, LR.end, LiveInMBBs)) {
for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i)
- if (LiveInMBBs[i] != EntryMBB)
+ if (LiveInMBBs[i] != EntryMBB) {
+ assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
+ "Adding a virtual register to livein set?");
LiveInMBBs[i]->addLiveIn(Reg);
+ }
LiveInMBBs.clear();
}
}
}
DOUT << *vrm_;
+
+ // 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;
}
/// processActiveIntervals - expire old intervals and move non-overlapping ones
// bl should get the same spill weight otherwise it will be choosen
// as a spill candidate since spilling bh doesn't make ebx available.
for (unsigned i = 0, e = Supers.size(); i != e; ++i) {
- for (const unsigned *sr = tri_->getSubRegisters(Supers[i]); *sr; ++sr)
- if (!Processed.count(*sr))
- Weights[*sr] += weight;
+ for (const unsigned *sr = tri_->getSubRegisters(Supers[i]); *sr; ++sr)
+ if (!Processed.count(*sr))
+ Weights[*sr] += weight;
}
}
/// addStackInterval - Create a LiveInterval for stack if the specified live
/// interval has been spilled.
static void addStackInterval(LiveInterval *cur, LiveStacks *ls_,
- LiveIntervals *li_, float &Weight,
- VirtRegMap &vrm_) {
+ LiveIntervals *li_,
+ MachineRegisterInfo* mri_, VirtRegMap &vrm_) {
int SS = vrm_.getStackSlot(cur->reg);
if (SS == VirtRegMap::NO_STACK_SLOT)
return;
- LiveInterval &SI = ls_->getOrCreateInterval(SS);
- SI.weight += Weight;
+
+ 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(~0U, 0, ls_->getVNInfoAllocator());
+ VNI = SI.getNextValue(0, 0, false, ls_->getVNInfoAllocator());
LiveInterval &RI = li_->getInterval(cur->reg);
// FIXME: This may be overly conservative.
/// getConflictWeight - Return the number of conflicts between cur
/// live interval and defs and uses of Reg weighted by loop depthes.
-static float getConflictWeight(LiveInterval *cur, unsigned Reg,
- LiveIntervals *li_,
- MachineRegisterInfo *mri_,
- const MachineLoopInfo *loopInfo) {
+static
+float getConflictWeight(LiveInterval *cur, unsigned Reg, LiveIntervals *li_,
+ MachineRegisterInfo *mri_,
+ const MachineLoopInfo *loopInfo) {
float Conflicts = 0;
for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg),
E = mri_->reg_end(); I != E; ++I) {
// This is an implicitly defined live interval, just assign any register.
const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
if (cur->empty()) {
- unsigned physReg = cur->preference;
+ unsigned physReg = vrm_->getRegAllocPref(cur->reg);
if (!physReg)
physReg = *RC->allocation_order_begin(*mf_);
DOUT << tri_->getName(physReg) << '\n';
// register class, then we should try to assign it the same register.
// This can happen when the move is from a larger register class to a smaller
// one, e.g. X86::mov32to32_. These move instructions are not coalescable.
- if (!cur->preference && cur->hasAtLeastOneValue()) {
+ if (!vrm_->getRegAllocPref(cur->reg) && cur->hasAtLeastOneValue()) {
VNInfo *vni = cur->begin()->valno;
- if (vni->def && vni->def != ~1U && vni->def != ~0U) {
+ if (vni->def && !vni->isUnused() && vni->isDefAccurate()) {
MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
if (CopyMI &&
if (DstSubReg)
Reg = tri_->getMatchingSuperReg(Reg, DstSubReg, RC);
if (Reg && allocatableRegs_[Reg] && RC->contains(Reg))
- cur->preference = Reg;
+ mri_->setRegAllocationHint(cur->reg, 0, Reg);
}
}
}
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.
- NextReloadLI->preference = physReg;
+ mri_->setRegAllocationHint(NextReloadLI->reg, 0, physReg);
DowngradeRegister(cur, physReg);
}
return;
// Find a register to spill.
float minWeight = HUGE_VALF;
- unsigned minReg = 0; /*cur->preference*/; // Try the pref register first.
+ unsigned minReg = 0;
bool Found = false;
std::vector<std::pair<unsigned,float> > RegsWeights;
DowngradedRegs.clear();
assignRegOrStackSlotAtInterval(cur);
} else {
- cerr << "Ran out of registers during register allocation!\n";
- exit(1);
+ llvm_report_error("Ran out of registers during register allocation!");
}
return;
}
// linearscan.
if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
DOUT << "\t\t\tspilling(c): " << *cur << '\n';
- float SSWeight;
SmallVector<LiveInterval*, 8> spillIs;
- std::vector<LiveInterval*> added =
- li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_, SSWeight);
+ std::vector<LiveInterval*> added;
+
+ if (!NewSpillFramework) {
+ added = li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_);
+ } else {
+ added = spiller_->spill(cur);
+ }
+
std::sort(added.begin(), added.end(), LISorter());
- addStackInterval(cur, ls_, li_, SSWeight, *vrm_);
+ addStackInterval(cur, ls_, li_, mri_, *vrm_);
if (added.empty())
return; // Early exit if all spills were folded.
// The earliest start of a Spilled interval indicates up to where
// in handled we need to roll back
- unsigned earliestStart = cur->beginNumber();
+
+ LiveInterval *earliestStartInterval = cur;
// Spill live intervals of virtual regs mapped to the physical register we
// want to clear (and its aliases). We only spill those that overlap with the
LiveInterval *sli = spillIs.back();
spillIs.pop_back();
DOUT << "\t\t\tspilling(a): " << *sli << '\n';
- earliestStart = std::min(earliestStart, sli->beginNumber());
- float SSWeight;
- std::vector<LiveInterval*> newIs =
- li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_, SSWeight);
- addStackInterval(sli, ls_, li_, SSWeight, *vrm_);
+ earliestStartInterval =
+ (earliestStartInterval->beginNumber() < sli->beginNumber()) ?
+ earliestStartInterval : sli;
+
+ std::vector<LiveInterval*> newIs;
+ if (!NewSpillFramework) {
+ newIs = li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_);
+ } else {
+ newIs = spiller_->spill(sli);
+ }
+ addStackInterval(sli, ls_, li_, mri_, *vrm_);
std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
spilled.insert(sli->reg);
}
+ unsigned earliestStart = earliestStartInterval->beginNumber();
+
DOUT << "\t\trolling back to: " << earliestStart << '\n';
// Scan handled in reverse order up to the earliest start of a
// It interval has a preference, it must be defined by a copy. Clear the
// preference now since the source interval allocation may have been
// undone as well.
- i->preference = 0;
+ mri_->setRegAllocationHint(i->reg, 0, 0);
else {
UpgradeRegister(ii->second);
}
}
}
-unsigned RALinScan::getFreePhysReg(const TargetRegisterClass *RC,
+unsigned RALinScan::getFreePhysReg(LiveInterval* cur,
+ const TargetRegisterClass *RC,
unsigned MaxInactiveCount,
SmallVector<unsigned, 256> &inactiveCounts,
bool SkipDGRegs) {
unsigned FreeReg = 0;
unsigned FreeRegInactiveCount = 0;
- TargetRegisterClass::iterator I = RC->allocation_order_begin(*mf_);
- TargetRegisterClass::iterator E = RC->allocation_order_end(*mf_);
+ std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(cur->reg);
+ // Resolve second part of the hint (if possible) given the current allocation.
+ unsigned physReg = Hint.second;
+ if (physReg &&
+ TargetRegisterInfo::isVirtualRegister(physReg) && vrm_->hasPhys(physReg))
+ physReg = vrm_->getPhys(physReg);
+
+ TargetRegisterClass::iterator I, E;
+ tie(I, E) = tri_->getAllocationOrder(RC, Hint.first, physReg, *mf_);
assert(I != E && "No allocatable register in this register class!");
// Scan for the first available register.
// return this register.
if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount)
return FreeReg;
-
+
// Continue scanning the registers, looking for the one with the highest
// inactive count. Alkis found that this reduced register pressure very
// slightly on X86 (in rev 1.94 of this file), though this should probably be
// If copy coalescer has assigned a "preferred" register, check if it's
// available first.
- if (cur->preference) {
- DOUT << "(preferred: " << tri_->getName(cur->preference) << ") ";
- if (isRegAvail(cur->preference) &&
- RC->contains(cur->preference))
- return cur->preference;
+ unsigned Preference = vrm_->getRegAllocPref(cur->reg);
+ if (Preference) {
+ DOUT << "(preferred: " << tri_->getName(Preference) << ") ";
+ if (isRegAvail(Preference) &&
+ RC->contains(Preference))
+ return Preference;
}
if (!DowngradedRegs.empty()) {
- unsigned FreeReg = getFreePhysReg(RC, MaxInactiveCount, inactiveCounts,
+ unsigned FreeReg = getFreePhysReg(cur, RC, MaxInactiveCount, inactiveCounts,
true);
if (FreeReg)
return FreeReg;
}
- return getFreePhysReg(RC, MaxInactiveCount, inactiveCounts, false);
+ return getFreePhysReg(cur, RC, MaxInactiveCount, inactiveCounts, false);
}
FunctionPass* llvm::createLinearScanRegisterAllocator() {