#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/PBQP/Graph.h"
#include "llvm/CodeGen/PBQP/Solution.h"
-
#include <map>
+#include <set>
namespace llvm {
- class LiveInterval;
+ class LiveIntervals;
+ class MachineBlockFrequencyInfo;
class MachineFunction;
+ class TargetRegisterInfo;
+ template<class T> class OwningPtr;
/// This class wraps up a PBQP instance representing a register allocation
/// problem, plus the structures necessary to map back from the PBQP solution
/// 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 <typename AllowedRegsItr>
- void recordVReg(unsigned vreg, PBQP::Graph::NodeItr node,
+ void recordVReg(unsigned vreg, PBQP::Graph::NodeId nodeId,
AllowedRegsItr arBegin, AllowedRegsItr arEnd) {
- assert(node2VReg.find(node) == node2VReg.end() && "Re-mapping node.");
+ assert(node2VReg.find(nodeId) == 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;
+ node2VReg[nodeId] = vreg;
+ vreg2Node[vreg] = nodeId;
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;
+ unsigned getVRegForNode(PBQP::Graph::NodeId nodeId) const;
/// Get the PBQP node corresponding to the given virtual register.
- PBQP::Graph::NodeItr getNodeForVReg(unsigned vreg) const;
+ PBQP::Graph::NodeId getNodeForVReg(unsigned vreg) const;
/// Returns true if the given PBQP option represents a physical register,
/// false otherwise.
private:
- typedef std::map<PBQP::Graph::ConstNodeItr, unsigned,
- PBQP::NodeItrComparator> Node2VReg;
- typedef DenseMap<unsigned, PBQP::Graph::NodeItr> VReg2Node;
- typedef std::map<unsigned, AllowedSet> AllowedSetMap;
+ typedef std::map<PBQP::Graph::NodeId, unsigned> Node2VReg;
+ typedef DenseMap<unsigned, PBQP::Graph::NodeId> VReg2Node;
+ typedef DenseMap<unsigned, AllowedSet> AllowedSetMap;
PBQP::Graph graph;
Node2VReg node2VReg;
/// class to support additional constraints for your architecture.
class PBQPBuilder {
private:
- PBQPBuilder(const PBQPBuilder&) {}
- void operator=(const PBQPBuilder&) {}
+ PBQPBuilder(const PBQPBuilder&) LLVM_DELETED_FUNCTION;
+ void operator=(const PBQPBuilder&) LLVM_DELETED_FUNCTION;
public:
typedef std::set<unsigned> RegSet;
-
/// Default constructor.
PBQPBuilder() {}
/// Build a PBQP instance to represent the register allocation problem for
/// the given MachineFunction.
- virtual std::auto_ptr<PBQPRAProblem> build(
- MachineFunction *mf,
- const LiveIntervals *lis,
- const RegSet &vregs);
+ virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis,
+ const MachineBlockFrequencyInfo *mbfi,
+ const RegSet &vregs);
private:
void addSpillCosts(PBQP::Vector &costVec, PBQP::PBQPNum spillCost);
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 {
+ /// Extended builder which adds coalescing constraints to a problem.
+ class PBQPBuilderWithCoalescing : public PBQPBuilder {
public:
-
- static char ID;
-
- /// Construct a PBQP register allocator.
- RegAllocPBQP(std::auto_ptr<PBQPBuilder> 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);
+
+ /// Build a PBQP instance to represent the register allocation problem for
+ /// the given MachineFunction.
+ virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis,
+ const MachineBlockFrequencyInfo *mbfi,
+ const RegSet &vregs);
private:
- typedef std::map<const LiveInterval*, unsigned> LI2NodeMap;
- typedef std::vector<const LiveInterval*> Node2LIMap;
- typedef std::vector<unsigned> AllowedSet;
- typedef std::vector<AllowedSet> AllowedSetMap;
- typedef std::pair<unsigned, unsigned> RegPair;
- typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
- typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
- typedef std::set<unsigned> RegSet;
-
-
- std::auto_ptr<PBQPBuilder> 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 <typename RegContainer>
- 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 <typename RegContainer>
- 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 <typename RegContainer>
- 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;
+ void addPhysRegCoalesce(PBQP::Vector &costVec, unsigned pregOption,
+ PBQP::PBQPNum benefit);
+ void addVirtRegCoalesce(PBQP::Matrix &costMat,
+ const PBQPRAProblem::AllowedSet &vr1Allowed,
+ const PBQPRAProblem::AllowedSet &vr2Allowed,
+ PBQP::PBQPNum benefit);
};
+ FunctionPass* createPBQPRegisterAllocator(OwningPtr<PBQPBuilder> &builder,
+ char *customPassID=0);
}
#endif /* LLVM_CODEGEN_REGALLOCPBQP_H */
projects / oota-llvm.git / blobdiff