//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "regalloc"
+#include "AllocationOrder.h"
#include "LiveIntervalUnion.h"
+#include "LiveRangeEdit.h"
#include "RegAllocBase.h"
#include "Spiller.h"
+#include "SplitKit.h"
#include "VirtRegMap.h"
#include "VirtRegRewriter.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
+#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineLoopRanges.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/Timer.h"
using namespace llvm;
class RAGreedy : public MachineFunctionPass, public RegAllocBase {
// context
MachineFunction *MF;
- const TargetMachine *TM;
- MachineRegisterInfo *MRI;
-
BitVector ReservedRegs;
// analyses
LiveStacks *LS;
+ MachineDominatorTree *DomTree;
+ MachineLoopInfo *Loops;
+ MachineLoopRanges *LoopRanges;
// state
std::auto_ptr<Spiller> SpillerInstance;
+ std::auto_ptr<SplitAnalysis> SA;
public:
RAGreedy();
/// Return the pass name.
virtual const char* getPassName() const {
- return "Basic Register Allocator";
+ return "Greedy Register Allocator";
}
/// RAGreedy analysis usage.
virtual bool runOnMachineFunction(MachineFunction &mf);
static char ID;
+
+private:
+ bool checkUncachedInterference(LiveInterval&, unsigned);
+ LiveInterval *getSingleInterference(LiveInterval&, unsigned);
+ bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg);
+ bool reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg);
+ unsigned findInterferenceFreeReg(MachineLoopRange*,
+ LiveInterval&, AllocationOrder&);
+ float calcInterferenceWeight(LiveInterval&, unsigned);
+
+ unsigned tryReassign(LiveInterval&, AllocationOrder&);
+ unsigned trySplit(LiveInterval&, AllocationOrder&,
+ SmallVectorImpl<LiveInterval*>&);
+ unsigned trySpillInterferences(LiveInterval&, AllocationOrder&,
+ SmallVectorImpl<LiveInterval*>&);
};
} // end anonymous namespace
initializeLiveStacksPass(*PassRegistry::getPassRegistry());
initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
+ initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
}
AU.addRequired<CalculateSpillWeights>();
AU.addRequired<LiveStacks>();
AU.addPreserved<LiveStacks>();
- AU.addRequiredID(MachineDominatorsID);
- AU.addPreservedID(MachineDominatorsID);
+ AU.addRequired<MachineDominatorTree>();
+ AU.addPreserved<MachineDominatorTree>();
AU.addRequired<MachineLoopInfo>();
AU.addPreserved<MachineLoopInfo>();
+ AU.addRequired<MachineLoopRanges>();
+ AU.addPreserved<MachineLoopRanges>();
AU.addRequired<VirtRegMap>();
AU.addPreserved<VirtRegMap>();
MachineFunctionPass::getAnalysisUsage(AU);
return Priority;
}
-unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
- SmallVectorImpl<LiveInterval*> &SplitVRegs) {
- // Populate a list of physical register spill candidates.
- SmallVector<unsigned, 8> PhysRegSpillCands;
-
- // Check for an available register in this class.
- const TargetRegisterClass *TRC = MRI->getRegClass(VirtReg.reg);
- DEBUG(dbgs() << "RegClass: " << TRC->getName() << ' ');
-
- // Preferred physical register computed from hints.
- unsigned Hint = VRM->getRegAllocPref(VirtReg.reg);
-
- // Try a hinted allocation.
- if (Hint && !ReservedRegs.test(Hint) && TRC->contains(Hint) &&
- checkPhysRegInterference(VirtReg, Hint) == 0)
- return Hint;
-
- for (TargetRegisterClass::iterator I = TRC->allocation_order_begin(*MF),
- E = TRC->allocation_order_end(*MF);
- I != E; ++I) {
-
- unsigned PhysReg = *I;
- if (ReservedRegs.test(PhysReg)) continue;
-
- // Check interference and as a side effect, intialize queries for this
- // VirtReg and its aliases.
- unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg);
- if (interfReg == 0) {
- // Found an available register.
+
+//===----------------------------------------------------------------------===//
+// Register Reassignment
+//===----------------------------------------------------------------------===//
+
+// Check interference without using the cache.
+bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg,
+ unsigned PhysReg) {
+ for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
+ LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]);
+ if (subQ.checkInterference())
+ return true;
+ }
+ return false;
+}
+
+/// getSingleInterference - Return the single interfering virtual register
+/// assigned to PhysReg. Return 0 if more than one virtual register is
+/// interfering.
+LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg,
+ unsigned PhysReg) {
+ // Check physreg and aliases.
+ LiveInterval *Interference = 0;
+ for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
+ LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
+ if (Q.checkInterference()) {
+ if (Interference)
+ return 0;
+ Q.collectInterferingVRegs(1);
+ if (!Q.seenAllInterferences())
+ return 0;
+ Interference = Q.interferingVRegs().front();
+ }
+ }
+ return Interference;
+}
+
+// Attempt to reassign this virtual register to a different physical register.
+//
+// FIXME: we are not yet caching these "second-level" interferences discovered
+// in the sub-queries. These interferences can change with each call to
+// selectOrSplit. However, we could implement a "may-interfere" cache that
+// could be conservatively dirtied when we reassign or split.
+//
+// FIXME: This may result in a lot of alias queries. We could summarize alias
+// live intervals in their parent register's live union, but it's messy.
+bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg,
+ unsigned WantedPhysReg) {
+ assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) &&
+ "Can only reassign virtual registers");
+ assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) &&
+ "inconsistent phys reg assigment");
+
+ AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs);
+ while (unsigned PhysReg = Order.next()) {
+ // Don't reassign to a WantedPhysReg alias.
+ if (TRI->regsOverlap(PhysReg, WantedPhysReg))
+ continue;
+
+ if (checkUncachedInterference(InterferingVReg, PhysReg))
+ continue;
+
+ // Reassign the interfering virtual reg to this physical reg.
+ unsigned OldAssign = VRM->getPhys(InterferingVReg.reg);
+ DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " <<
+ TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n');
+ PhysReg2LiveUnion[OldAssign].extract(InterferingVReg);
+ VRM->clearVirt(InterferingVReg.reg);
+ VRM->assignVirt2Phys(InterferingVReg.reg, PhysReg);
+ PhysReg2LiveUnion[PhysReg].unify(InterferingVReg);
+
+ return true;
+ }
+ return false;
+}
+
+/// reassignInterferences - Reassign all interferences to different physical
+/// registers such that Virtreg can be assigned to PhysReg.
+/// Currently this only works with a single interference.
+/// @param VirtReg Currently unassigned virtual register.
+/// @param PhysReg Physical register to be cleared.
+/// @return True on success, false if nothing was changed.
+bool RAGreedy::reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg) {
+ LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg);
+ if (!InterferingVReg)
+ return false;
+ if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg))
+ return false;
+ return reassignVReg(*InterferingVReg, PhysReg);
+}
+
+/// tryReassign - Try to reassign interferences to different physregs.
+/// @param VirtReg Currently unassigned virtual register.
+/// @param Order Physregs to try.
+/// @return Physreg to assign VirtReg, or 0.
+unsigned RAGreedy::tryReassign(LiveInterval &VirtReg, AllocationOrder &Order) {
+ NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled);
+ Order.rewind();
+ while (unsigned PhysReg = Order.next())
+ if (reassignInterferences(VirtReg, PhysReg))
return PhysReg;
+ return 0;
+}
+
+
+//===----------------------------------------------------------------------===//
+// Loop Splitting
+//===----------------------------------------------------------------------===//
+
+/// findInterferenceFreeReg - Find a physical register in Order where Loop has
+/// no interferences with VirtReg.
+unsigned RAGreedy::findInterferenceFreeReg(MachineLoopRange *Loop,
+ LiveInterval &VirtReg,
+ AllocationOrder &Order) {
+ Order.rewind();
+ while (unsigned PhysReg = Order.next()) {
+ bool interference = false;
+ for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
+ if (query(VirtReg, *AI).checkLoopInterference(Loop)) {
+ interference = true;
+ break;
+ }
}
- LiveInterval *interferingVirtReg =
- Queries[interfReg].firstInterference().liveUnionPos().value();
+ if (!interference)
+ return PhysReg;
+ }
+ // No physreg found.
+ return 0;
+}
- // The current VirtReg must either spillable, or one of its interferences
- // must have less spill weight.
- if (interferingVirtReg->weight < VirtReg.weight ) {
- PhysRegSpillCands.push_back(PhysReg);
+/// trySplit - Try to split VirtReg or one of its interferences, making it
+/// assignable.
+/// @return Physreg when VirtReg may be assigned and/or new SplitVRegs.
+unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
+ SmallVectorImpl<LiveInterval*>&SplitVRegs) {
+ NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled);
+ SA->analyze(&VirtReg);
+
+ // Get the set of loops that have VirtReg uses and are splittable.
+ SplitAnalysis::LoopPtrSet SplitLoopSet;
+ SA->getSplitLoops(SplitLoopSet);
+
+ // Order loops by descending area.
+ SmallVector<MachineLoopRange*, 8> SplitLoops;
+ for (SplitAnalysis::LoopPtrSet::const_iterator I = SplitLoopSet.begin(),
+ E = SplitLoopSet.end(); I != E; ++I)
+ SplitLoops.push_back(LoopRanges->getLoopRange(*I));
+ array_pod_sort(SplitLoops.begin(), SplitLoops.end(),
+ MachineLoopRange::byAreaDesc);
+
+ // Find the first loop that is interference-free for some register in the
+ // allocation order.
+ MachineLoopRange *Loop = 0;
+ for (unsigned i = 0, e = SplitLoops.size(); i != e; ++i) {
+ DEBUG(dbgs() << " Checking " << *SplitLoops[i]);
+ if (unsigned PhysReg = findInterferenceFreeReg(SplitLoops[i],
+ VirtReg, Order)) {
+ (void)PhysReg;
+ Loop = SplitLoops[i];
+ DEBUG(dbgs() << ": Use %" << TRI->getName(PhysReg) << '\n');
+ break;
+ } else {
+ DEBUG(dbgs() << ": Interference.\n");
}
}
- // Try to spill another interfering reg with less spill weight.
- //
- // FIXME: RAGreedy will sort this list by spill weight.
- for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
- PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
- if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue;
+ if (!Loop) {
+ DEBUG(dbgs() << " All candidate loops have interference.\n");
+ return 0;
+ }
+
+ // Execute the split around Loop.
+ SmallVector<LiveInterval*, 4> SpillRegs;
+ LiveRangeEdit LREdit(VirtReg, SplitVRegs, SpillRegs);
+ SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit)
+ .splitAroundLoop(Loop->getLoop());
- assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 &&
- "Interference after spill.");
- // Tell the caller to allocate to this newly freed physical register.
- return *PhysRegI;
+ if (VerifyEnabled)
+ MF->verify(this, "After splitting live range around loop");
+
+ // We have new split regs, don't assign anything.
+ return 0;
+}
+
+
+//===----------------------------------------------------------------------===//
+// Spilling
+//===----------------------------------------------------------------------===//
+
+/// calcInterferenceWeight - Calculate the combined spill weight of
+/// interferences when assigning VirtReg to PhysReg.
+float RAGreedy::calcInterferenceWeight(LiveInterval &VirtReg, unsigned PhysReg){
+ float Sum = 0;
+ for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
+ LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
+ Q.collectInterferingVRegs();
+ if (Q.seenUnspillableVReg())
+ return HUGE_VALF;
+ for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i)
+ Sum += Q.interferingVRegs()[i]->weight;
}
- // No other spill candidates were found, so spill the current VirtReg.
- DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
- SmallVector<LiveInterval*, 1> pendingSpills;
+ return Sum;
+}
+
+/// trySpillInterferences - Try to spill interfering registers instead of the
+/// current one. Only do it if the accumulated spill weight is smaller than the
+/// current spill weight.
+unsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg,
+ AllocationOrder &Order,
+ SmallVectorImpl<LiveInterval*> &NewVRegs) {
+ NamedRegionTimer T("Spill Interference", TimerGroupName, TimePassesIsEnabled);
+ unsigned BestPhys = 0;
+ float BestWeight = 0;
+
+ Order.rewind();
+ while (unsigned PhysReg = Order.next()) {
+ float Weight = calcInterferenceWeight(VirtReg, PhysReg);
+ if (Weight == HUGE_VALF || Weight >= VirtReg.weight)
+ continue;
+ if (!BestPhys || Weight < BestWeight)
+ BestPhys = PhysReg, BestWeight = Weight;
+ }
+
+ // No candidates found.
+ if (!BestPhys)
+ return 0;
+
+ // Collect all interfering registers.
+ SmallVector<LiveInterval*, 8> Spills;
+ for (const unsigned *AI = TRI->getOverlaps(BestPhys); *AI; ++AI) {
+ LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
+ Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end());
+ for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
+ LiveInterval *VReg = Q.interferingVRegs()[i];
+ PhysReg2LiveUnion[*AI].extract(*VReg);
+ VRM->clearVirt(VReg->reg);
+ }
+ }
+
+ // Spill them all.
+ DEBUG(dbgs() << "spilling " << Spills.size() << " interferences with weight "
+ << BestWeight << '\n');
+ for (unsigned i = 0, e = Spills.size(); i != e; ++i)
+ spiller().spill(Spills[i], NewVRegs, Spills);
+ return BestPhys;
+}
+
+//===----------------------------------------------------------------------===//
+// Main Entry Point
+//===----------------------------------------------------------------------===//
+
+unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
+ SmallVectorImpl<LiveInterval*> &SplitVRegs) {
+ // First try assigning a free register.
+ AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
+ while (unsigned PhysReg = Order.next()) {
+ if (!checkPhysRegInterference(VirtReg, PhysReg))
+ return PhysReg;
+ }
+
+ // Try to reassign interferences.
+ if (unsigned PhysReg = tryReassign(VirtReg, Order))
+ return PhysReg;
+
+ // Try splitting VirtReg or interferences.
+ unsigned PhysReg = trySplit(VirtReg, Order, SplitVRegs);
+ if (PhysReg || !SplitVRegs.empty())
+ return PhysReg;
+
+ // Try to spill another interfering reg with less spill weight.
+ PhysReg = trySpillInterferences(VirtReg, Order, SplitVRegs);
+ if (PhysReg)
+ return PhysReg;
+
+ // Finally spill VirtReg itself.
+ NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
+ SmallVector<LiveInterval*, 1> pendingSpills;
spiller().spill(&VirtReg, SplitVRegs, pendingSpills);
// The live virtual register requesting allocation was spilled, so tell
<< ((Value*)mf.getFunction())->getName() << '\n');
MF = &mf;
- TM = &mf.getTarget();
- MRI = &mf.getRegInfo();
-
- const TargetRegisterInfo *TRI = TM->getRegisterInfo();
- RegAllocBase::init(*TRI, getAnalysis<VirtRegMap>(),
- getAnalysis<LiveIntervals>());
+ if (VerifyEnabled)
+ MF->verify(this, "Before greedy register allocator");
+ RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
+ DomTree = &getAnalysis<MachineDominatorTree>();
ReservedRegs = TRI->getReservedRegs(*MF);
- SpillerInstance.reset(createSpiller(*this, *MF, *VRM));
+ SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
+ Loops = &getAnalysis<MachineLoopInfo>();
+ LoopRanges = &getAnalysis<MachineLoopRanges>();
+ SA.reset(new SplitAnalysis(*MF, *LIS, *Loops));
+
allocatePhysRegs();
addMBBLiveIns(MF);
// Run rewriter
- std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
- rewriter->runOnMachineFunction(*MF, *VRM, LIS);
+ {
+ NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
+ std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
+ rewriter->runOnMachineFunction(*MF, *VRM, LIS);
+ }
// The pass output is in VirtRegMap. Release all the transient data.
releaseMemory();
return true;
}
-
projects / oota-llvm.git / blobdiff