#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"
#include "llvm/CodeGen/PBQP/Graph.h"
#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
-#include "llvm/CodeGen/RegisterCoalescer.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.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 {
///
static char ID;
/// Construct a PBQP register allocator.
- RegAllocPBQP(std::auto_ptr<PBQPBuilder> b) : MachineFunctionPass(ID), builder(b) {}
+ RegAllocPBQP(std::auto_ptr<PBQPBuilder> b, char *cPassID=0)
+ : MachineFunctionPass(ID), builder(b), customPassID(cPassID) {
+ initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
+ initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
+ initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
+ initializeLiveStacksPass(*PassRegistry::getPassRegistry());
+ initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
+ initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
+ initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
+ }
/// Return the pass name.
virtual const char* getPassName() const {
std::auto_ptr<PBQPBuilder> builder;
+ char *customPassID;
+
MachineFunction *mf;
const TargetMachine *tm;
const TargetRegisterInfo *tri;
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,
VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg);
assert(nodeItr != vreg2Node.end() && "No node for vreg.");
return nodeItr->second;
-
+
}
const PBQPRAProblem::AllowedSet&
typedef std::vector<const LiveInterval*> LIVector;
MachineRegisterInfo *mri = &mf->getRegInfo();
- const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo();
+ const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo();
std::auto_ptr<PBQPRAProblem> p(new PBQPRAProblem());
PBQP::Graph &g = p->getGraph();
BitVector reservedRegs = tri->getReservedRegs(*mf);
- // Iterate over vregs.
+ // Iterate over vregs.
for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end();
vregItr != vregEnd; ++vregItr) {
unsigned vreg = *vregItr;
// Compute an initial allowed set for the current vreg.
typedef std::vector<unsigned> VRAllowed;
VRAllowed vrAllowed;
- for (TargetRegisterClass::iterator aoItr = trc->allocation_order_begin(*mf),
- aoEnd = trc->allocation_order_end(*mf);
- aoItr != aoEnd; ++aoItr) {
- unsigned preg = *aoItr;
+ ArrayRef<unsigned> rawOrder = trc->getRawAllocationOrder(*mf);
+ for (unsigned i = 0; i != rawOrder.size(); ++i) {
+ unsigned preg = rawOrder[i];
if (!reservedRegs.test(preg)) {
vrAllowed.push_back(preg);
}
unsigned preg = *pregItr;
const LiveInterval *pregLI = &lis->getInterval(preg);
- if (pregLI->empty())
+ if (pregLI->empty()) {
continue;
+ }
- if (!vregLI->overlaps(*pregLI))
+ if (!vregLI->overlaps(*pregLI)) {
continue;
+ }
// Remove the register from the allowed set.
VRAllowed::iterator eraseItr =
}
// Construct the node.
- PBQP::Graph::NodeItr node =
+ PBQP::Graph::NodeItr node =
g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0));
// Record the mapping and allowed set in the problem.
assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch.");
assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch.");
- for (unsigned i = 0; i < vr1Allowed.size(); ++i) {
+ for (unsigned i = 0; i != vr1Allowed.size(); ++i) {
unsigned preg1 = vr1Allowed[i];
- for (unsigned j = 0; j < vr2Allowed.size(); ++j) {
+ for (unsigned j = 0; j != vr2Allowed.size(); ++j) {
unsigned preg2 = vr2Allowed[j];
if (tri->regsOverlap(preg1, preg2)) {
miItr != miEnd; ++miItr) {
const MachineInstr *mi = &*miItr;
- if (!cp.setRegisters(mi))
+ if (!cp.setRegisters(mi)) {
continue; // Not coalescable.
+ }
- if (cp.getSrcReg() == cp.getDstReg())
+ if (cp.getSrcReg() == cp.getDstReg()) {
continue; // Already coalesced.
+ }
unsigned dst = cp.getDstReg(),
src = cp.getSrcReg();
const float copyFactor = 0.5; // Cost of copy relative to load. Current
// value plucked randomly out of the air.
-
+
PBQP::PBQPNum cBenefit =
copyFactor * LiveIntervals::getSpillWeight(false, true,
loopInfo->getLoopDepth(mbb));
if (cp.isPhys()) {
- if (!lis->isAllocatable(dst))
+ if (!lis->isAllocatable(dst)) {
continue;
+ }
const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src);
- unsigned pregOpt = 0;
- while (pregOpt < allowed.size() && allowed[pregOpt] != dst)
+ unsigned pregOpt = 0;
+ while (pregOpt < allowed.size() && allowed[pregOpt] != dst) {
++pregOpt;
+ }
if (pregOpt < allowed.size()) {
++pregOpt; // +1 to account for spill option.
PBQP::Graph::NodeItr node = p->getNodeForVReg(src);
std::swap(allowed1, allowed2);
}
}
-
+
addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2,
cBenefit);
}
assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch.");
assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch.");
- for (unsigned i = 0; i < vr1Allowed.size(); ++i) {
+ for (unsigned i = 0; i != vr1Allowed.size(); ++i) {
unsigned preg1 = vr1Allowed[i];
- for (unsigned j = 0; j < vr2Allowed.size(); ++j) {
+ for (unsigned j = 0; j != vr2Allowed.size(); ++j) {
unsigned preg2 = vr2Allowed[j];
if (preg1 == preg2) {
costMat[i + 1][j + 1] += -benefit;
- }
+ }
}
}
}
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>();
+ 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);
// finalizeAlloc.
if (!li->empty()) {
vregsToAlloc.insert(li->reg);
- }
- else {
+ } else {
emptyIntervalVRegs.insert(li->reg);
}
}
}
-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
unsigned alloc = solution.getSelection(node);
if (problem.isPRegOption(vreg, alloc)) {
- unsigned preg = problem.getPRegForOption(vreg, alloc);
+ unsigned preg = problem.getPRegForOption(vreg, alloc);
DEBUG(dbgs() << "VREG " << vreg << " -> " << tri->getName(preg) << "\n");
assert(preg != 0 && "Invalid preg selected.");
- vrm->assignVirt2Phys(vreg, preg);
+ vrm->assignVirt2Phys(vreg, preg);
} else if (problem.isSpillOption(vreg, alloc)) {
vregsToAlloc.erase(vreg);
- const LiveInterval* spillInterval = &lis->getInterval(vreg);
- double oldWeight = spillInterval->weight;
- SmallVector<LiveInterval*, 8> spillIs;
- rmf->rememberUseDefs(spillInterval);
- std::vector<LiveInterval*> newSpills =
- lis->addIntervalsForSpills(*spillInterval, spillIs, 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.");
+ llvm_unreachable("Unknown allocation option.");
}
}
if (physReg == 0) {
const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
- physReg = *liRC->allocation_order_begin(*mf);
+ physReg = liRC->getRawAllocationOrder(*mf).front();
}
vrm->assignVirt2Phys(li->reg, physReg);
// Get the physical register for this interval
if (TargetRegisterInfo::isPhysicalRegister(li->reg)) {
reg = li->reg;
- }
- else if (vrm->isAssignedReg(li->reg)) {
+ } else if (vrm->isAssignedReg(li->reg)) {
reg = vrm->getPhys(li->reg);
- }
- else {
+ } else {
// Ranges which are assigned a stack slot only are ignored.
continue;
}
// Find the set of basic blocks which this range is live into...
if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) {
// And add the physreg for this interval to their live-in sets.
- for (unsigned i = 0; i < liveInMBBs.size(); ++i) {
+ for (unsigned i = 0; i != liveInMBBs.size(); ++i) {
if (liveInMBBs[i] != entryMBB) {
if (!liveInMBBs[i]->isLiveIn(reg)) {
liveInMBBs[i]->addLiveIn(reg);
tm = &mf->getTarget();
tri = tm->getRegisterInfo();
tii = tm->getInstrInfo();
- mri = &mf->getRegInfo();
+ mri = &mf->getRegInfo();
lis = &getAnalysis<LiveIntervals>();
lss = &getAnalysis<LiveStacks>();
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;
}
FunctionPass* llvm::createPBQPRegisterAllocator(
- std::auto_ptr<PBQPBuilder> builder) {
- return new RegAllocPBQP(builder);
+ std::auto_ptr<PBQPBuilder> builder,
+ char *customPassID) {
+ return new RegAllocPBQP(builder, customPassID);
}
FunctionPass* llvm::createDefaultPBQPRegisterAllocator() {
projects / oota-llvm.git / blobdiff