#define DEBUG_TYPE "regalloc"
+#include "LiveRangeEdit.h"
#include "RenderMachineFunction.h"
-#include "Splitter.h"
+#include "Spiller.h"
#include "VirtRegMap.h"
-#include "VirtRegRewriter.h"
#include "RegisterCoalescer.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/RegAllocPBQP.h"
+#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
cl::desc("Attempt coalescing during PBQP register allocation."),
cl::init(false), cl::Hidden);
-static cl::opt<bool>
-pbqpPreSplitting("pbqp-pre-splitting",
- cl::desc("Pre-split before PBQP register allocation."),
- cl::init(false), cl::Hidden);
-
namespace {
///
initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
initializeLiveStacksPass(*PassRegistry::getPassRegistry());
initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
- initializeLoopSplitterPass(*PassRegistry::getPassRegistry());
initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
}
MachineRegisterInfo *mri;
RenderMachineFunction *rmf;
+ std::auto_ptr<Spiller> spiller;
LiveIntervals *lis;
LiveStacks *lss;
VirtRegMap *vrm;
/// \brief Finds the initial set of vreg intervals to allocate.
void findVRegIntervalsToAlloc();
- /// \brief Adds a stack interval if the given live interval has been
- /// spilled. Used to support stack slot coloring.
- void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri);
-
/// \brief Given a solved PBQP problem maps this solution back to a register
/// assignment.
bool mapPBQPToRegAlloc(const PBQPRAProblem &problem,
void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const {
+ au.setPreservesCFG();
+ au.addRequired<AliasAnalysis>();
+ au.addPreserved<AliasAnalysis>();
au.addRequired<SlotIndexes>();
au.addPreserved<SlotIndexes>();
au.addRequired<LiveIntervals>();
//au.addRequiredID(SplitCriticalEdgesID);
- au.addRequired<RegisterCoalescer>();
+ au.addRequiredID(RegisterCoalescerPassID);
if (customPassID)
au.addRequiredID(*customPassID);
au.addRequired<CalculateSpillWeights>();
au.addRequired<LiveStacks>();
au.addPreserved<LiveStacks>();
+ au.addRequired<MachineDominatorTree>();
+ au.addPreserved<MachineDominatorTree>();
au.addRequired<MachineLoopInfo>();
au.addPreserved<MachineLoopInfo>();
- if (pbqpPreSplitting)
- au.addRequired<LoopSplitter>();
au.addRequired<VirtRegMap>();
au.addRequired<RenderMachineFunction>();
MachineFunctionPass::getAnalysisUsage(au);
}
}
-void RegAllocPBQP::addStackInterval(const LiveInterval *spilled,
- MachineRegisterInfo* mri) {
- int stackSlot = vrm->getStackSlot(spilled->reg);
-
- if (stackSlot == VirtRegMap::NO_STACK_SLOT) {
- return;
- }
-
- const TargetRegisterClass *RC = mri->getRegClass(spilled->reg);
- LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC);
-
- VNInfo *vni;
- if (stackInterval.getNumValNums() != 0) {
- vni = stackInterval.getValNumInfo(0);
- } else {
- vni = stackInterval.getNextValue(
- SlotIndex(), 0, lss->getVNInfoAllocator());
- }
-
- LiveInterval &rhsInterval = lis->getInterval(spilled->reg);
- stackInterval.MergeRangesInAsValue(rhsInterval, vni);
-}
-
bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem,
const PBQP::Solution &solution) {
// Set to true if we have any spills
vrm->assignVirt2Phys(vreg, preg);
} else if (problem.isSpillOption(vreg, alloc)) {
vregsToAlloc.erase(vreg);
- const LiveInterval* spillInterval = &lis->getInterval(vreg);
- double oldWeight = spillInterval->weight;
- rmf->rememberUseDefs(spillInterval);
- std::vector<LiveInterval*> newSpills =
- lis->addIntervalsForSpills(*spillInterval, 0, loopInfo, *vrm);
- addStackInterval(spillInterval, mri);
- rmf->rememberSpills(spillInterval, newSpills);
-
- (void) oldWeight;
+ SmallVector<LiveInterval*, 8> newSpills;
+ LiveRangeEdit LRE(lis->getInterval(vreg), newSpills);
+ spiller->spill(LRE);
+
DEBUG(dbgs() << "VREG " << vreg << " -> SPILLED (Cost: "
- << oldWeight << ", New vregs: ");
+ << LRE.getParent().weight << ", New vregs: ");
// Copy any newly inserted live intervals into the list of regs to
// allocate.
- for (std::vector<LiveInterval*>::const_iterator
- itr = newSpills.begin(), end = newSpills.end();
+ for (LiveRangeEdit::iterator itr = LRE.begin(), end = LRE.end();
itr != end; ++itr) {
assert(!(*itr)->empty() && "Empty spill range.");
DEBUG(dbgs() << (*itr)->reg << " ");
DEBUG(dbgs() << ")\n");
// We need another round if spill intervals were added.
- anotherRoundNeeded |= !newSpills.empty();
+ anotherRoundNeeded |= !LRE.empty();
} else {
assert(false && "Unknown allocation option.");
}
rmf = &getAnalysis<RenderMachineFunction>();
vrm = &getAnalysis<VirtRegMap>();
+ spiller.reset(createInlineSpiller(*this, MF, *vrm));
+ mri->freezeReservedRegs(MF);
DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n");
DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
// Run rewriter
- std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
-
- rewriter->runOnMachineFunction(*mf, *vrm, lis);
+ vrm->rewrite(lis->getSlotIndexes());
return true;
}