diff options
Diffstat (limited to 'contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp')
| -rw-r--r-- | contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp | 173 |
1 files changed, 103 insertions, 70 deletions
diff --git a/contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp b/contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp index 0d2cf2d..a284614 100644 --- a/contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp +++ b/contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp @@ -32,14 +32,17 @@ #define DEBUG_TYPE "regalloc" #include "RenderMachineFunction.h" -#include "Splitter.h" +#include "Spiller.h" #include "VirtRegMap.h" -#include "VirtRegRewriter.h" #include "RegisterCoalescer.h" +#include "llvm/Module.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/LiveRangeEdit.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" @@ -54,6 +57,7 @@ #include <limits> #include <memory> #include <set> +#include <sstream> #include <vector> using namespace llvm; @@ -67,10 +71,12 @@ pbqpCoalescing("pbqp-coalescing", cl::desc("Attempt coalescing during PBQP register allocation."), cl::init(false), cl::Hidden); +#ifndef NDEBUG static cl::opt<bool> -pbqpPreSplitting("pbqp-pre-splitting", - cl::desc("Pre-split before PBQP register allocation."), - cl::init(false), cl::Hidden); +pbqpDumpGraphs("pbqp-dump-graphs", + cl::desc("Dump graphs for each function/round in the compilation unit."), + cl::init(false), cl::Hidden); +#endif namespace { @@ -88,11 +94,9 @@ public: : MachineFunctionPass(ID), builder(b), customPassID(cPassID) { initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); - initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); initializeLiveStacksPass(*PassRegistry::getPassRegistry()); initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); - initializeLoopSplitterPass(*PassRegistry::getPassRegistry()); initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry()); } @@ -132,6 +136,7 @@ private: MachineRegisterInfo *mri; RenderMachineFunction *rmf; + std::auto_ptr<Spiller> spiller; LiveIntervals *lis; LiveStacks *lss; VirtRegMap *vrm; @@ -141,10 +146,6 @@ private: /// \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, @@ -170,7 +171,7 @@ PBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const { VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg); assert(nodeItr != vreg2Node.end() && "No node for vreg."); return nodeItr->second; - + } const PBQPRAProblem::AllowedSet& @@ -195,9 +196,9 @@ std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf, const RegSet &vregs) { typedef std::vector<const LiveInterval*> LIVector; - + ArrayRef<SlotIndex> regMaskSlots = lis->getRegMaskSlots(); 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(); @@ -214,7 +215,7 @@ std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf, 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; @@ -224,7 +225,7 @@ std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf, // Compute an initial allowed set for the current vreg. typedef std::vector<unsigned> VRAllowed; VRAllowed vrAllowed; - ArrayRef<unsigned> rawOrder = trc->getRawAllocationOrder(*mf); + ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(*mf); for (unsigned i = 0; i != rawOrder.size(); ++i) { unsigned preg = rawOrder[i]; if (!reservedRegs.test(preg)) { @@ -232,7 +233,9 @@ std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf, } } - // Remove any physical registers which overlap. + RegSet overlappingPRegs; + + // Record physical registers whose ranges overlap. for (RegSet::const_iterator pregItr = pregs.begin(), pregEnd = pregs.end(); pregItr != pregEnd; ++pregItr) { @@ -243,9 +246,41 @@ std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf, continue; } - if (!vregLI->overlaps(*pregLI)) { - continue; + if (vregLI->overlaps(*pregLI)) + overlappingPRegs.insert(preg); + } + + // Record any overlaps with regmask operands. + BitVector regMaskOverlaps(tri->getNumRegs()); + for (ArrayRef<SlotIndex>::iterator rmItr = regMaskSlots.begin(), + rmEnd = regMaskSlots.end(); + rmItr != rmEnd; ++rmItr) { + SlotIndex rmIdx = *rmItr; + if (vregLI->liveAt(rmIdx)) { + MachineInstr *rmMI = lis->getInstructionFromIndex(rmIdx); + const uint32_t* regMask = 0; + for (MachineInstr::mop_iterator mopItr = rmMI->operands_begin(), + mopEnd = rmMI->operands_end(); + mopItr != mopEnd; ++mopItr) { + if (mopItr->isRegMask()) { + regMask = mopItr->getRegMask(); + break; + } + } + assert(regMask != 0 && "Couldn't find register mask."); + regMaskOverlaps.setBitsNotInMask(regMask); } + } + + for (unsigned preg = 0; preg < tri->getNumRegs(); ++preg) { + if (regMaskOverlaps.test(preg)) + overlappingPRegs.insert(preg); + } + + for (RegSet::const_iterator pregItr = overlappingPRegs.begin(), + pregEnd = overlappingPRegs.end(); + pregItr != pregEnd; ++pregItr) { + unsigned preg = *pregItr; // Remove the register from the allowed set. VRAllowed::iterator eraseItr = @@ -256,7 +291,7 @@ std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf, } // Also remove any aliases. - const unsigned *aliasItr = tri->getAliasSet(preg); + const uint16_t *aliasItr = tri->getAliasSet(preg); if (aliasItr != 0) { for (; *aliasItr != 0; ++aliasItr) { VRAllowed::iterator eraseItr = @@ -270,7 +305,7 @@ std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf, } // 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. @@ -371,7 +406,7 @@ std::auto_ptr<PBQPRAProblem> PBQPBuilderWithCoalescing::build( 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)); @@ -382,7 +417,7 @@ std::auto_ptr<PBQPRAProblem> PBQPBuilderWithCoalescing::build( } const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src); - unsigned pregOpt = 0; + unsigned pregOpt = 0; while (pregOpt < allowed.size() && allowed[pregOpt] != dst) { ++pregOpt; } @@ -407,7 +442,7 @@ std::auto_ptr<PBQPRAProblem> PBQPBuilderWithCoalescing::build( std::swap(allowed1, allowed2); } } - + addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2, cBenefit); } @@ -439,27 +474,29 @@ void PBQPBuilderWithCoalescing::addVirtRegCoalesce( 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.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); @@ -488,29 +525,6 @@ void RegAllocPBQP::findVRegIntervalsToAlloc() { } } -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 @@ -529,28 +543,22 @@ bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem, 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; - 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, *mf, *lis, vrm); + 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 << " "); @@ -560,9 +568,9 @@ bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem, 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."); } } @@ -642,7 +650,7 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { tm = &mf->getTarget(); tri = tm->getRegisterInfo(); tii = tm->getInstrInfo(); - mri = &mf->getRegInfo(); + mri = &mf->getRegInfo(); lis = &getAnalysis<LiveIntervals>(); lss = &getAnalysis<LiveStacks>(); @@ -650,7 +658,9 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { 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"); @@ -666,6 +676,12 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { // Find the vreg intervals in need of allocation. findVRegIntervalsToAlloc(); + const Function* func = mf->getFunction(); + std::string fqn = + func->getParent()->getModuleIdentifier() + "." + + func->getName().str(); + (void)fqn; + // If there are non-empty intervals allocate them using pbqp. if (!vregsToAlloc.empty()) { @@ -677,6 +693,20 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { std::auto_ptr<PBQPRAProblem> problem = builder->build(mf, lis, loopInfo, vregsToAlloc); + +#ifndef NDEBUG + if (pbqpDumpGraphs) { + std::ostringstream rs; + rs << round; + std::string graphFileName(fqn + "." + rs.str() + ".pbqpgraph"); + std::string tmp; + raw_fd_ostream os(graphFileName.c_str(), tmp); + DEBUG(dbgs() << "Dumping graph for round " << round << " to \"" + << graphFileName << "\"\n"); + problem->getGraph().dump(os); + } +#endif + PBQP::Solution solution = PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve( problem->getGraph()); @@ -698,9 +728,12 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); // Run rewriter - std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter()); + vrm->rewrite(lis->getSlotIndexes()); - rewriter->runOnMachineFunction(*mf, *vrm, lis); + // All machine operands and other references to virtual registers have been + // replaced. Remove the virtual registers. + vrm->clearAllVirt(); + mri->clearVirtRegs(); return true; } |
