1 //===-- RegAllocPBQP.h ------------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the PBQPBuilder interface, for classes which build PBQP
11 // instances to represent register allocation problems, and the RegAllocPBQP
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_CODEGEN_REGALLOCPBQP_H
17 #define LLVM_CODEGEN_REGALLOCPBQP_H
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/CodeGen/PBQP/RegAllocSolver.h"
29 class MachineBlockFrequencyInfo;
30 class MachineFunction;
31 class TargetRegisterInfo;
32 template<class T> class OwningPtr;
34 typedef PBQP::RegAlloc::Graph PBQPRAGraph;
36 /// This class wraps up a PBQP instance representing a register allocation
37 /// problem, plus the structures necessary to map back from the PBQP solution
38 /// to a register allocation solution. (i.e. The PBQP-node <--> vreg map,
39 /// and the PBQP option <--> storage location map).
43 typedef SmallVector<unsigned, 16> AllowedSet;
45 PBQPRAGraph& getGraph() { return graph; }
47 const PBQPRAGraph& getGraph() const { return graph; }
49 /// Record the mapping between the given virtual register and PBQP node,
50 /// and the set of allowed pregs for the vreg.
52 /// If you are extending
53 /// PBQPBuilder you are unlikely to need this: Nodes and options for all
54 /// vregs will already have been set up for you by the base class.
55 template <typename AllowedRegsItr>
56 void recordVReg(unsigned vreg, PBQPRAGraph::NodeId nodeId,
57 AllowedRegsItr arBegin, AllowedRegsItr arEnd) {
58 assert(node2VReg.find(nodeId) == node2VReg.end() && "Re-mapping node.");
59 assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg.");
60 assert(allowedSets[vreg].empty() && "vreg already has pregs.");
62 node2VReg[nodeId] = vreg;
63 vreg2Node[vreg] = nodeId;
64 std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg]));
67 /// Get the virtual register corresponding to the given PBQP node.
68 unsigned getVRegForNode(PBQPRAGraph::NodeId nodeId) const;
70 /// Get the PBQP node corresponding to the given virtual register.
71 PBQPRAGraph::NodeId getNodeForVReg(unsigned vreg) const;
73 /// Returns true if the given PBQP option represents a physical register,
75 bool isPRegOption(unsigned vreg, unsigned option) const {
76 // At present we only have spills or pregs, so anything that's not a
77 // spill is a preg. (This might be extended one day to support remat).
78 return !isSpillOption(vreg, option);
81 /// Returns true if the given PBQP option represents spilling, false
83 bool isSpillOption(unsigned vreg, unsigned option) const {
84 // We hardcode option zero as the spill option.
88 /// Returns the allowed set for the given virtual register.
89 const AllowedSet& getAllowedSet(unsigned vreg) const;
91 /// Get PReg for option.
92 unsigned getPRegForOption(unsigned vreg, unsigned option) const;
96 typedef std::map<PBQPRAGraph::NodeId, unsigned> Node2VReg;
97 typedef DenseMap<unsigned, PBQPRAGraph::NodeId> VReg2Node;
98 typedef DenseMap<unsigned, AllowedSet> AllowedSetMap;
104 AllowedSetMap allowedSets;
108 /// Builds PBQP instances to represent register allocation problems. Includes
109 /// spill, interference and coalescing costs by default. You can extend this
110 /// class to support additional constraints for your architecture.
113 PBQPBuilder(const PBQPBuilder&) LLVM_DELETED_FUNCTION;
114 void operator=(const PBQPBuilder&) LLVM_DELETED_FUNCTION;
117 typedef std::set<unsigned> RegSet;
119 /// Default constructor.
122 /// Clean up a PBQPBuilder.
123 virtual ~PBQPBuilder() {}
125 /// Build a PBQP instance to represent the register allocation problem for
126 /// the given MachineFunction.
127 virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis,
128 const MachineBlockFrequencyInfo *mbfi,
129 const RegSet &vregs);
132 void addSpillCosts(PBQP::Vector &costVec, PBQP::PBQPNum spillCost);
134 void addInterferenceCosts(PBQP::Matrix &costMat,
135 const PBQPRAProblem::AllowedSet &vr1Allowed,
136 const PBQPRAProblem::AllowedSet &vr2Allowed,
137 const TargetRegisterInfo *tri);
140 /// Extended builder which adds coalescing constraints to a problem.
141 class PBQPBuilderWithCoalescing : public PBQPBuilder {
144 /// Build a PBQP instance to represent the register allocation problem for
145 /// the given MachineFunction.
146 virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis,
147 const MachineBlockFrequencyInfo *mbfi,
148 const RegSet &vregs);
152 void addPhysRegCoalesce(PBQP::Vector &costVec, unsigned pregOption,
153 PBQP::PBQPNum benefit);
155 void addVirtRegCoalesce(PBQP::Matrix &costMat,
156 const PBQPRAProblem::AllowedSet &vr1Allowed,
157 const PBQPRAProblem::AllowedSet &vr2Allowed,
158 PBQP::PBQPNum benefit);
161 FunctionPass* createPBQPRegisterAllocator(OwningPtr<PBQPBuilder> &builder,
162 char *customPassID=0);
165 #endif /* LLVM_CODEGEN_REGALLOCPBQP_H */