From eb6c8f53b4df1488f3d07c11af8f754cc4620f3a Mon Sep 17 00:00:00 2001 From: Lang Hames Date: Sat, 18 Sep 2010 09:07:10 +0000 Subject: [PATCH] Added a separate class (PBQPBuilder) for PBQP Problem construction. This class can be extended to support custom constraints. For now the allocator still uses the old (internal) construction mechanism by default. This will be phased out soon assuming no issues with the builder system come up. To invoke the new construction mechanism just pass '-regalloc=pbqp -pbqp-builder' to llc. To provide custom constraints a Target just needs to extend PBQPBuilder and pass an instance of their derived builder to the RegAllocPBQP constructor. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114272 91177308-0d34-0410-b5e6-96231b3b80d8 --- {lib => include/llvm}/CodeGen/PBQP/Graph.h | 0 .../llvm}/CodeGen/PBQP/HeuristicBase.h | 0 .../llvm}/CodeGen/PBQP/HeuristicSolver.h | 0 .../llvm}/CodeGen/PBQP/Heuristics/Briggs.h | 0 {lib => include/llvm}/CodeGen/PBQP/Math.h | 0 {lib => include/llvm}/CodeGen/PBQP/Solution.h | 5 +- include/llvm/CodeGen/RegAllocPBQP.h | 260 ++++++++++ lib/CodeGen/RegAllocPBQP.cpp | 481 +++++++++++------- 8 files changed, 572 insertions(+), 174 deletions(-) rename {lib => include/llvm}/CodeGen/PBQP/Graph.h (100%) rename {lib => include/llvm}/CodeGen/PBQP/HeuristicBase.h (100%) rename {lib => include/llvm}/CodeGen/PBQP/HeuristicSolver.h (100%) rename {lib => include/llvm}/CodeGen/PBQP/Heuristics/Briggs.h (100%) rename {lib => include/llvm}/CodeGen/PBQP/Math.h (100%) rename {lib => include/llvm}/CodeGen/PBQP/Solution.h (94%) create mode 100644 include/llvm/CodeGen/RegAllocPBQP.h diff --git a/lib/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h similarity index 100% rename from lib/CodeGen/PBQP/Graph.h rename to include/llvm/CodeGen/PBQP/Graph.h diff --git a/lib/CodeGen/PBQP/HeuristicBase.h b/include/llvm/CodeGen/PBQP/HeuristicBase.h similarity index 100% rename from lib/CodeGen/PBQP/HeuristicBase.h rename to include/llvm/CodeGen/PBQP/HeuristicBase.h diff --git a/lib/CodeGen/PBQP/HeuristicSolver.h b/include/llvm/CodeGen/PBQP/HeuristicSolver.h similarity index 100% rename from lib/CodeGen/PBQP/HeuristicSolver.h rename to include/llvm/CodeGen/PBQP/HeuristicSolver.h diff --git a/lib/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h similarity index 100% rename from lib/CodeGen/PBQP/Heuristics/Briggs.h rename to include/llvm/CodeGen/PBQP/Heuristics/Briggs.h diff --git a/lib/CodeGen/PBQP/Math.h b/include/llvm/CodeGen/PBQP/Math.h similarity index 100% rename from lib/CodeGen/PBQP/Math.h rename to include/llvm/CodeGen/PBQP/Math.h diff --git a/lib/CodeGen/PBQP/Solution.h b/include/llvm/CodeGen/PBQP/Solution.h similarity index 94% rename from lib/CodeGen/PBQP/Solution.h rename to include/llvm/CodeGen/PBQP/Solution.h index 9c40ed7070a..57d9b95fc3b 100644 --- a/lib/CodeGen/PBQP/Solution.h +++ b/include/llvm/CodeGen/PBQP/Solution.h @@ -27,7 +27,8 @@ namespace PBQP { class Solution { private: - typedef std::map SelectionsMap; + typedef std::map SelectionsMap; SelectionsMap selections; unsigned r0Reductions, r1Reductions, r2Reductions, rNReductions; @@ -80,7 +81,7 @@ namespace PBQP { /// \brief Get a node's selection. /// @param nItr Node iterator. /// @return The selection for nItr; - unsigned getSelection(Graph::NodeItr nItr) const { + unsigned getSelection(Graph::ConstNodeItr nItr) const { SelectionsMap::const_iterator sItr = selections.find(nItr); assert(sItr != selections.end() && "No selection for node."); return sItr->second; diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h new file mode 100644 index 00000000000..ee3baf36a92 --- /dev/null +++ b/include/llvm/CodeGen/RegAllocPBQP.h @@ -0,0 +1,260 @@ +//===-- RegAllocPBQP.h ------------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the PBQPBuilder interface, for classes which build PBQP +// instances to represent register allocation problems, and the RegAllocPBQP +// interface. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_REGALLOCPBQP_H +#define LLVM_CODEGEN_REGALLOCPBQP_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/PBQP/Graph.h" +#include "llvm/CodeGen/PBQP/Solution.h" + +#include + +namespace llvm { + + class LiveInterval; + class MachineFunction; + + /// This class wraps up a PBQP instance representing a register allocation + /// problem, plus the structures necessary to map back from the PBQP solution + /// to a register allocation solution. (i.e. The PBQP-node <--> vreg map, + /// and the PBQP option <--> storage location map). + + class PBQPRAProblem { + public: + + typedef SmallVector AllowedSet; + + PBQP::Graph& getGraph() { return graph; } + + const PBQP::Graph& getGraph() const { return graph; } + + /// Record the mapping between the given virtual register and PBQP node, + /// and the set of allowed pregs for the vreg. + /// + /// If you are extending + /// PBQPBuilder you are unlikely to need this: Nodes and options for all + /// vregs will already have been set up for you by the base class. + template + void recordVReg(unsigned vreg, PBQP::Graph::NodeItr node, + AllowedRegsItr arBegin, AllowedRegsItr arEnd) { + assert(node2VReg.find(node) == node2VReg.end() && "Re-mapping node."); + assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg."); + assert(allowedSets[vreg].empty() && "vreg already has pregs."); + + node2VReg[node] = vreg; + vreg2Node[vreg] = node; + std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg])); + } + + /// Get the virtual register corresponding to the given PBQP node. + unsigned getVRegForNode(PBQP::Graph::ConstNodeItr node) const; + + /// Get the PBQP node corresponding to the given virtual register. + PBQP::Graph::NodeItr getNodeForVReg(unsigned vreg) const; + + /// Returns true if the given PBQP option represents a physical register, + /// false otherwise. + bool isPRegOption(unsigned vreg, unsigned option) const { + // At present we only have spills or pregs, so anything that's not a + // spill is a preg. (This might be extended one day to support remat). + return !isSpillOption(vreg, option); + } + + /// Returns true if the given PBQP option represents spilling, false + /// otherwise. + bool isSpillOption(unsigned vreg, unsigned option) const { + // We hardcode option zero as the spill option. + return option == 0; + } + + /// Returns the allowed set for the given virtual register. + const AllowedSet& getAllowedSet(unsigned vreg) const; + + /// Get PReg for option. + unsigned getPRegForOption(unsigned vreg, unsigned option) const; + + private: + + typedef std::map Node2VReg; + typedef DenseMap VReg2Node; + typedef std::map AllowedSetMap; + + PBQP::Graph graph; + Node2VReg node2VReg; + VReg2Node vreg2Node; + + AllowedSetMap allowedSets; + + }; + + /// Builds PBQP instances to represent register allocation problems. Includes + /// spill, interference and coalescing costs by default. You can extend this + /// class to support additional constraints for your architecture. + class PBQPBuilder { + private: + PBQPBuilder(const PBQPBuilder&) {} + void operator=(const PBQPBuilder&) {} + public: + + typedef std::set RegSet; + + + /// Default constructor. + PBQPBuilder() {} + + /// Clean up a PBQPBuilder. + virtual ~PBQPBuilder() {} + + /// Build a PBQP instance to represent the register allocation problem for + /// the given MachineFunction. + virtual std::auto_ptr build( + MachineFunction *mf, + const LiveIntervals *lis, + const RegSet &vregs); + private: + + void addSpillCosts(PBQP::Vector &costVec, PBQP::PBQPNum spillCost); + + void addInterferenceCosts(PBQP::Matrix &costMat, + const PBQPRAProblem::AllowedSet &vr1Allowed, + const PBQPRAProblem::AllowedSet &vr2Allowed, + const TargetRegisterInfo *tri); + }; + + /// + /// PBQP based allocators solve the register allocation problem by mapping + /// register allocation problems to Partitioned Boolean Quadratic + /// Programming problems. + class RegAllocPBQP : public MachineFunctionPass { + public: + + static char ID; + + /// Construct a PBQP register allocator. + RegAllocPBQP(std::auto_ptr b) : MachineFunctionPass(ID), builder(b) {} + + /// Return the pass name. + virtual const char* getPassName() const { + return "PBQP Register Allocator"; + } + + /// PBQP analysis usage. + virtual void getAnalysisUsage(AnalysisUsage &au) const; + + /// Perform register allocation + virtual bool runOnMachineFunction(MachineFunction &MF); + + private: + + typedef std::map LI2NodeMap; + typedef std::vector Node2LIMap; + typedef std::vector AllowedSet; + typedef std::vector AllowedSetMap; + typedef std::pair RegPair; + typedef std::map CoalesceMap; + typedef std::vector NodeVector; + typedef std::set RegSet; + + + std::auto_ptr builder; + + MachineFunction *mf; + const TargetMachine *tm; + const TargetRegisterInfo *tri; + const TargetInstrInfo *tii; + const MachineLoopInfo *loopInfo; + MachineRegisterInfo *mri; + RenderMachineFunction *rmf; + + LiveIntervals *lis; + LiveStacks *lss; + VirtRegMap *vrm; + + LI2NodeMap li2Node; + Node2LIMap node2LI; + AllowedSetMap allowedSets; + RegSet vregsToAlloc, emptyIntervalVRegs; + NodeVector problemNodes; + + + /// Builds a PBQP cost vector. + template + PBQP::Vector buildCostVector(unsigned vReg, + const RegContainer &allowed, + const CoalesceMap &cealesces, + PBQP::PBQPNum spillCost) const; + + /// \brief Builds a PBQP interference matrix. + /// + /// @return Either a pointer to a non-zero PBQP matrix representing the + /// allocation option costs, or a null pointer for a zero matrix. + /// + /// Expects allowed sets for two interfering LiveIntervals. These allowed + /// sets should contain only allocable registers from the LiveInterval's + /// register class, with any interfering pre-colored registers removed. + template + PBQP::Matrix* buildInterferenceMatrix(const RegContainer &allowed1, + const RegContainer &allowed2) const; + + /// + /// Expects allowed sets for two potentially coalescable LiveIntervals, + /// and an estimated benefit due to coalescing. The allowed sets should + /// contain only allocable registers from the LiveInterval's register + /// classes, with any interfering pre-colored registers removed. + template + PBQP::Matrix* buildCoalescingMatrix(const RegContainer &allowed1, + const RegContainer &allowed2, + PBQP::PBQPNum cBenefit) const; + + /// \brief Finds coalescing opportunities and returns them as a map. + /// + /// Any entries in the map are guaranteed coalescable, even if their + /// corresponding live intervals overlap. + CoalesceMap findCoalesces(); + + /// \brief Finds the initial set of vreg intervals to allocate. + void findVRegIntervalsToAlloc(); + + /// \brief Constructs a PBQP problem representation of the register + /// allocation problem for this function. + /// + /// @return a PBQP solver object for the register allocation problem. + PBQP::Graph constructPBQPProblem(); + + /// \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 PBQP::Solution &solution); + + /// \brief Given a solved PBQP problem maps this solution back to a register + /// assignment. + bool mapPBQPToRegAlloc2(const PBQPRAProblem &problem, + const PBQP::Solution &solution); + + /// \brief Postprocessing before final spilling. Sets basic block "live in" + /// variables. + void finalizeAlloc() const; + + }; + +} + +#endif /* LLVM_CODEGEN_REGALLOCPBQP_H */ diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index 61f337bab49..6b2e5c04807 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -31,9 +31,6 @@ #define DEBUG_TYPE "regalloc" -#include "PBQP/HeuristicSolver.h" -#include "PBQP/Graph.h" -#include "PBQP/Heuristics/Briggs.h" #include "RenderMachineFunction.h" #include "Splitter.h" #include "VirtRegMap.h" @@ -41,9 +38,13 @@ #include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" +#include "llvm/CodeGen/RegAllocPBQP.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/PBQP/HeuristicSolver.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" @@ -51,12 +52,14 @@ #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include -#include #include #include #include -using namespace llvm; +namespace llvm { + +using namespace PBQP; + using namespace PBQP::Heuristics; static RegisterRegAlloc registerPBQPRepAlloc("pbqp", "PBQP register allocator", @@ -67,157 +70,213 @@ pbqpCoalescing("pbqp-coalescing", cl::desc("Attempt coalescing during PBQP register allocation."), cl::init(false), cl::Hidden); +static cl::opt +pbqpBuilder("pbqp-builder", + cl::desc("Use new builder system."), + cl::init(false), cl::Hidden); + + static cl::opt pbqpPreSplitting("pbqp-pre-splitting", cl::desc("Pre-splite before PBQP register allocation."), cl::init(false), cl::Hidden); -namespace { +char RegAllocPBQP::ID = 0; + +unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const { + Node2VReg::const_iterator vregItr = node2VReg.find(node); + assert(vregItr != node2VReg.end() && "No vreg for node."); + return vregItr->second; +} + +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& + PBQPRAProblem::getAllowedSet(unsigned vreg) const { + AllowedSetMap::const_iterator allowedSetItr = allowedSets.find(vreg); + assert(allowedSetItr != allowedSets.end() && "No pregs for vreg."); + const AllowedSet &allowedSet = allowedSetItr->second; + return allowedSet; +} + +unsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const { + assert(isPRegOption(vreg, option) && "Not a preg option."); + + const AllowedSet& allowedSet = getAllowedSet(vreg); + assert(option <= allowedSet.size() && "Option outside allowed set."); + return allowedSet[option - 1]; +} + +std::auto_ptr PBQPBuilder::build( + MachineFunction *mf, + const LiveIntervals *lis, + const RegSet &vregs) { + + typedef std::vector LIVector; + + MachineRegisterInfo *mri = &mf->getRegInfo(); + const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo(); + + std::auto_ptr p(new PBQPRAProblem()); + PBQP::Graph &g = p->getGraph(); + RegSet pregs; + + // Collect the set of preg intervals, record that they're used in the MF. + for (LiveIntervals::const_iterator itr = lis->begin(), end = lis->end(); + itr != end; ++itr) { + if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { + pregs.insert(itr->first); + mri->setPhysRegUsed(itr->first); + } + } + + BitVector reservedRegs = tri->getReservedRegs(*mf); + + // Iterate over vregs. + for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end(); + vregItr != vregEnd; ++vregItr) { + unsigned vreg = *vregItr; + const TargetRegisterClass *trc = mri->getRegClass(vreg); + const LiveInterval *vregLI = &lis->getInterval(vreg); + + // Compute an initial allowed set for the current vreg. + typedef std::vector VRAllowed; + VRAllowed vrAllowed; + for (TargetRegisterClass::iterator aoItr = trc->allocation_order_begin(*mf), + aoEnd = trc->allocation_order_end(*mf); + aoItr != aoEnd; ++aoItr) { + unsigned preg = *aoItr; + if (!reservedRegs.test(preg)) { + vrAllowed.push_back(preg); + } + } + + // Remove any physical registers which overlap. + for (RegSet::const_iterator pregItr = pregs.begin(), + pregEnd = pregs.end(); + pregItr != pregEnd; ++pregItr) { + unsigned preg = *pregItr; + const LiveInterval *pregLI = &lis->getInterval(preg); + + if (pregLI->empty()) + continue; + + if (!vregLI->overlaps(*pregLI)) + continue; - /// - /// PBQP based allocators solve the register allocation problem by mapping - /// register allocation problems to Partitioned Boolean Quadratic - /// Programming problems. - class PBQPRegAlloc : public MachineFunctionPass { - public: + // Remove the register from the allowed set. + VRAllowed::iterator eraseItr = + std::find(vrAllowed.begin(), vrAllowed.end(), preg); - static char ID; + if (eraseItr != vrAllowed.end()) { + vrAllowed.erase(eraseItr); + } - /// Construct a PBQP register allocator. - PBQPRegAlloc() : MachineFunctionPass(ID) {} + // Also remove any aliases. + const unsigned *aliasItr = tri->getAliasSet(preg); + if (aliasItr != 0) { + for (; *aliasItr != 0; ++aliasItr) { + VRAllowed::iterator eraseItr = + std::find(vrAllowed.begin(), vrAllowed.end(), *aliasItr); - /// Return the pass name. - virtual const char* getPassName() const { - return "PBQP Register Allocator"; + if (eraseItr != vrAllowed.end()) { + vrAllowed.erase(eraseItr); + } + } + } } - /// PBQP analysis usage. - virtual void getAnalysisUsage(AnalysisUsage &au) const { - au.addRequired(); - au.addPreserved(); - au.addRequired(); - //au.addRequiredID(SplitCriticalEdgesID); - au.addRequired(); - au.addRequired(); - au.addRequired(); - au.addPreserved(); - au.addRequired(); - au.addPreserved(); - if (pbqpPreSplitting) - au.addRequired(); - au.addRequired(); - au.addRequired(); - MachineFunctionPass::getAnalysisUsage(au); + // Construct the node. + PBQP::Graph::NodeItr node = + g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0)); + + // Record the mapping and allowed set in the problem. + p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end()); + + PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ? + vregLI->weight : std::numeric_limits::min(); + + addSpillCosts(g.getNodeCosts(node), spillCost); + } + + for (RegSet::iterator vr1Itr = vregs.begin(), vrEnd = vregs.end(); + vr1Itr != vrEnd; ++vr1Itr) { + unsigned vr1 = *vr1Itr; + const LiveInterval &l1 = lis->getInterval(vr1); + const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1); + + for (RegSet::iterator vr2Itr = llvm::next(vr1Itr); + vr2Itr != vrEnd; ++vr2Itr) { + unsigned vr2 = *vr2Itr; + const LiveInterval &l2 = lis->getInterval(vr2); + const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2); + + assert(!l2.empty() && "Empty interval in vreg set?"); + if (l1.overlaps(l2)) { + PBQP::Graph::EdgeItr edge = + g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2), + PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0)); + + addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri); + } } + } + + return p; +} + +void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec, + PBQP::PBQPNum spillCost) { + costVec[0] = spillCost; +} + +void PBQPBuilder::addInterferenceCosts(PBQP::Matrix &costMat, + const PBQPRAProblem::AllowedSet &vr1Allowed, + const PBQPRAProblem::AllowedSet &vr2Allowed, + const TargetRegisterInfo *tri) { + assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch."); + assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch."); - /// Perform register allocation - virtual bool runOnMachineFunction(MachineFunction &MF); + for (unsigned i = 0; i < vr1Allowed.size(); ++i) { + unsigned preg1 = vr1Allowed[i]; - private: + for (unsigned j = 0; j < vr2Allowed.size(); ++j) { + unsigned preg2 = vr2Allowed[j]; - class LIOrdering { - public: - bool operator()(const LiveInterval *li1, const LiveInterval *li2) const { - return li1->reg < li2->reg; + if (tri->regsOverlap(preg1, preg2)) { + costMat[i + 1][j + 1] = std::numeric_limits::infinity(); } - }; - - typedef std::map LI2NodeMap; - typedef std::vector Node2LIMap; - typedef std::vector AllowedSet; - typedef std::vector AllowedSetMap; - typedef std::set RegSet; - typedef std::pair RegPair; - typedef std::map CoalesceMap; - - typedef std::set LiveIntervalSet; - - typedef std::vector NodeVector; - - MachineFunction *mf; - const TargetMachine *tm; - const TargetRegisterInfo *tri; - const TargetInstrInfo *tii; - const MachineLoopInfo *loopInfo; - MachineRegisterInfo *mri; - RenderMachineFunction *rmf; - - LiveIntervals *lis; - LiveStacks *lss; - VirtRegMap *vrm; - - LI2NodeMap li2Node; - Node2LIMap node2LI; - AllowedSetMap allowedSets; - LiveIntervalSet vregIntervalsToAlloc, - emptyVRegIntervals; - NodeVector problemNodes; - - - /// Builds a PBQP cost vector. - template - PBQP::Vector buildCostVector(unsigned vReg, - const RegContainer &allowed, - const CoalesceMap &cealesces, - PBQP::PBQPNum spillCost) const; - - /// \brief Builds a PBQP interference matrix. - /// - /// @return Either a pointer to a non-zero PBQP matrix representing the - /// allocation option costs, or a null pointer for a zero matrix. - /// - /// Expects allowed sets for two interfering LiveIntervals. These allowed - /// sets should contain only allocable registers from the LiveInterval's - /// register class, with any interfering pre-colored registers removed. - template - PBQP::Matrix* buildInterferenceMatrix(const RegContainer &allowed1, - const RegContainer &allowed2) const; - - /// - /// Expects allowed sets for two potentially coalescable LiveIntervals, - /// and an estimated benefit due to coalescing. The allowed sets should - /// contain only allocable registers from the LiveInterval's register - /// classes, with any interfering pre-colored registers removed. - template - PBQP::Matrix* buildCoalescingMatrix(const RegContainer &allowed1, - const RegContainer &allowed2, - PBQP::PBQPNum cBenefit) const; - - /// \brief Finds coalescing opportunities and returns them as a map. - /// - /// Any entries in the map are guaranteed coalescable, even if their - /// corresponding live intervals overlap. - CoalesceMap findCoalesces(); - - /// \brief Finds the initial set of vreg intervals to allocate. - void findVRegIntervalsToAlloc(); - - /// \brief Constructs a PBQP problem representation of the register - /// allocation problem for this function. - /// - /// @return a PBQP solver object for the register allocation problem. - PBQP::Graph constructPBQPProblem(); - - /// \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 PBQP::Solution &solution); - - /// \brief Postprocessing before final spilling. Sets basic block "live in" - /// variables. - void finalizeAlloc() const; - - }; - - char PBQPRegAlloc::ID = 0; + } + } } + +void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { + au.addRequired(); + au.addPreserved(); + au.addRequired(); + //au.addRequiredID(SplitCriticalEdgesID); + au.addRequired(); + au.addRequired(); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + if (pbqpPreSplitting) + au.addRequired(); + au.addRequired(); + au.addRequired(); + MachineFunctionPass::getAnalysisUsage(au); +} + template -PBQP::Vector PBQPRegAlloc::buildCostVector(unsigned vReg, +PBQP::Vector RegAllocPBQP::buildCostVector(unsigned vReg, const RegContainer &allowed, const CoalesceMap &coalesces, PBQP::PBQPNum spillCost) const { @@ -252,7 +311,7 @@ PBQP::Vector PBQPRegAlloc::buildCostVector(unsigned vReg, } template -PBQP::Matrix* PBQPRegAlloc::buildInterferenceMatrix( +PBQP::Matrix* RegAllocPBQP::buildInterferenceMatrix( const RegContainer &allowed1, const RegContainer &allowed2) const { typedef typename RegContainer::const_iterator RegContainerIterator; @@ -318,7 +377,7 @@ PBQP::Matrix* PBQPRegAlloc::buildInterferenceMatrix( } template -PBQP::Matrix* PBQPRegAlloc::buildCoalescingMatrix( +PBQP::Matrix* RegAllocPBQP::buildCoalescingMatrix( const RegContainer &allowed1, const RegContainer &allowed2, PBQP::PBQPNum cBenefit) const { @@ -379,7 +438,7 @@ PBQP::Matrix* PBQPRegAlloc::buildCoalescingMatrix( return m; } -PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { +RegAllocPBQP::CoalesceMap RegAllocPBQP::findCoalesces() { typedef MachineFunction::const_iterator MFIterator; typedef MachineBasicBlock::const_iterator MBBIterator; @@ -516,7 +575,7 @@ PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { return coalescesFound; } -void PBQPRegAlloc::findVRegIntervalsToAlloc() { +void RegAllocPBQP::findVRegIntervalsToAlloc() { // Iterate over all live ranges. for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); @@ -532,15 +591,15 @@ void PBQPRegAlloc::findVRegIntervalsToAlloc() { // Empty intervals we allocate in a simple post-processing stage in // finalizeAlloc. if (!li->empty()) { - vregIntervalsToAlloc.insert(li); + vregsToAlloc.insert(li->reg); } else { - emptyVRegIntervals.insert(li); + emptyIntervalVRegs.insert(li->reg); } } } -PBQP::Graph PBQPRegAlloc::constructPBQPProblem() { +PBQP::Graph RegAllocPBQP::constructPBQPProblem() { typedef std::vector LIVector; typedef std::vector RegVector; @@ -565,10 +624,10 @@ PBQP::Graph PBQPRegAlloc::constructPBQPProblem() { // Iterate over vreg intervals, construct live interval <-> node number // mappings. - for (LiveIntervalSet::const_iterator - itr = vregIntervalsToAlloc.begin(), end = vregIntervalsToAlloc.end(); + for (RegSet::const_iterator itr = vregsToAlloc.begin(), + end = vregsToAlloc.end(); itr != end; ++itr) { - const LiveInterval *li = *itr; + const LiveInterval *li = &lis->getInterval(*itr); li2Node[li] = node2LI.size(); node2LI.push_back(li); @@ -583,10 +642,10 @@ PBQP::Graph PBQPRegAlloc::constructPBQPProblem() { // Construct a PBQP solver for this problem PBQP::Graph problem; - problemNodes.resize(vregIntervalsToAlloc.size()); + problemNodes.resize(vregsToAlloc.size()); // Resize allowedSets container appropriately. - allowedSets.resize(vregIntervalsToAlloc.size()); + allowedSets.resize(vregsToAlloc.size()); BitVector ReservedRegs = tri->getReservedRegs(*mf); @@ -617,8 +676,10 @@ PBQP::Graph PBQPRegAlloc::constructPBQPProblem() { // If we get here then the live intervals overlap, but we're still ok // if they're coalescable. - if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end()) + if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end()) { + DEBUG(dbgs() << "CoalescingOverride: (" << li->reg << ", " << pReg << ")\n"); continue; + } // If we get here then we have a genuine exclusion. @@ -703,7 +764,7 @@ PBQP::Graph PBQPRegAlloc::constructPBQPProblem() { return problem; } -void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, +void RegAllocPBQP::addStackInterval(const LiveInterval *spilled, MachineRegisterInfo* mri) { int stackSlot = vrm->getStackSlot(spilled->reg); @@ -724,7 +785,7 @@ void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, stackInterval.MergeRangesInAsValue(rhsInterval, vni); } -bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { +bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQP::Solution &solution) { // Set to true if we have any spills bool anotherRoundNeeded = false; @@ -744,7 +805,7 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { unsigned physReg = allowedSets[node][allocSelection - 1]; DEBUG(dbgs() << "VREG " << virtReg << " -> " - << tri->getName(physReg) << "\n"); + << tri->getName(physReg) << " (Option: " << allocSelection << ")\n"); assert(physReg != 0); @@ -756,7 +817,7 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { // Make sure we ignore this virtual reg on the next round // of allocation - vregIntervalsToAlloc.erase(&lis->getInterval(virtReg)); + vregsToAlloc.erase(virtReg); // Insert spill ranges for this live range const LiveInterval *spillInterval = node2LI[node]; @@ -769,7 +830,7 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { rmf->rememberSpills(spillInterval, newSpills); (void) oldSpillWeight; - DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Cost: " + DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Option: 0, Cost: " << oldSpillWeight << ", New vregs: "); // Copy any newly inserted live intervals into the list of regs to @@ -782,28 +843,88 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { DEBUG(dbgs() << (*itr)->reg << " "); - vregIntervalsToAlloc.insert(*itr); + vregsToAlloc.insert((*itr)->reg); + } + + DEBUG(dbgs() << ")\n"); + + // We need another round if spill intervals were added. + anotherRoundNeeded |= !newSpills.empty(); + } + } + + return !anotherRoundNeeded; +} + +bool RegAllocPBQP::mapPBQPToRegAlloc2(const PBQPRAProblem &problem, + const PBQP::Solution &solution) { + // Set to true if we have any spills + bool anotherRoundNeeded = false; + + // Clear the existing allocation. + vrm->clearAllVirt(); + + const PBQP::Graph &g = problem.getGraph(); + // Iterate over the nodes mapping the PBQP solution to a register + // assignment. + for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(), + nodeEnd = g.nodesEnd(); + node != nodeEnd; ++node) { + unsigned vreg = problem.getVRegForNode(node); + unsigned alloc = solution.getSelection(node); + + if (problem.isPRegOption(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); + } else if (problem.isSpillOption(vreg, alloc)) { + vregsToAlloc.erase(vreg); + const LiveInterval* spillInterval = &lis->getInterval(vreg); + double oldWeight = spillInterval->weight; + SmallVector spillIs; + rmf->rememberUseDefs(spillInterval); + std::vector newSpills = + lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm); + addStackInterval(spillInterval, mri); + rmf->rememberSpills(spillInterval, newSpills); + + (void) oldWeight; + DEBUG(dbgs() << "VREG " << vreg << " -> SPILLED (Cost: " + << oldWeight << ", New vregs: "); + + // Copy any newly inserted live intervals into the list of regs to + // allocate. + for (std::vector::const_iterator + itr = newSpills.begin(), end = newSpills.end(); + itr != end; ++itr) { + assert(!(*itr)->empty() && "Empty spill range."); + DEBUG(dbgs() << (*itr)->reg << " "); + vregsToAlloc.insert((*itr)->reg); } DEBUG(dbgs() << ")\n"); // We need another round if spill intervals were added. anotherRoundNeeded |= !newSpills.empty(); + } else { + assert(false && "Unknown allocation option."); } } return !anotherRoundNeeded; } -void PBQPRegAlloc::finalizeAlloc() const { + +void RegAllocPBQP::finalizeAlloc() const { typedef LiveIntervals::iterator LIIterator; typedef LiveInterval::Ranges::const_iterator LRIterator; // First allocate registers for the empty intervals. - for (LiveIntervalSet::const_iterator - itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end(); + for (RegSet::const_iterator + itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end(); itr != end; ++itr) { - LiveInterval *li = *itr; + LiveInterval *li = &lis->getInterval(*itr); unsigned physReg = vrm->getRegAllocPref(li->reg); @@ -863,7 +984,7 @@ void PBQPRegAlloc::finalizeAlloc() const { } -bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { +bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { mf = &MF; tm = &mf->getTarget(); @@ -894,21 +1015,36 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { findVRegIntervalsToAlloc(); // If there are non-empty intervals allocate them using pbqp. - if (!vregIntervalsToAlloc.empty()) { + if (!vregsToAlloc.empty()) { bool pbqpAllocComplete = false; unsigned round = 0; - while (!pbqpAllocComplete) { - DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); + if (!pbqpBuilder) { + while (!pbqpAllocComplete) { + DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); - PBQP::Graph problem = constructPBQPProblem(); - PBQP::Solution solution = - PBQP::HeuristicSolver::solve(problem); + PBQP::Graph problem = constructPBQPProblem(); + PBQP::Solution solution = + PBQP::HeuristicSolver::solve(problem); - pbqpAllocComplete = mapPBQPToRegAlloc(solution); + pbqpAllocComplete = mapPBQPToRegAlloc(solution); - ++round; + ++round; + } + } else { + while (!pbqpAllocComplete) { + DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); + + std::auto_ptr problem = + builder->build(mf, lis, vregsToAlloc); + PBQP::Solution solution = + HeuristicSolver::solve(problem->getGraph()); + + pbqpAllocComplete = mapPBQPToRegAlloc2(*problem, solution); + + ++round; + } } } @@ -917,8 +1053,8 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { rmf->renderMachineFunction("After PBQP register allocation.", vrm); - vregIntervalsToAlloc.clear(); - emptyVRegIntervals.clear(); + vregsToAlloc.clear(); + emptyIntervalVRegs.clear(); li2Node.clear(); node2LI.clear(); allowedSets.clear(); @@ -934,9 +1070,10 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { return true; } -FunctionPass* llvm::createPBQPRegisterAllocator() { - return new PBQPRegAlloc(); +FunctionPass* createPBQPRegisterAllocator() { + return new RegAllocPBQP(std::auto_ptr(new PBQPBuilder())); } +} #undef DEBUG_TYPE -- 2.34.1