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/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/PBQP/Graph.h"
22 #include "llvm/CodeGen/PBQP/Solution.h"
29 class MachineFunction;
31 /// This class wraps up a PBQP instance representing a register allocation
32 /// problem, plus the structures necessary to map back from the PBQP solution
33 /// to a register allocation solution. (i.e. The PBQP-node <--> vreg map,
34 /// and the PBQP option <--> storage location map).
39 typedef SmallVector<unsigned, 16> AllowedSet;
41 PBQP::Graph& getGraph() { return graph; }
43 const PBQP::Graph& getGraph() const { return graph; }
45 /// Record the mapping between the given virtual register and PBQP node,
46 /// and the set of allowed pregs for the vreg.
48 /// If you are extending
49 /// PBQPBuilder you are unlikely to need this: Nodes and options for all
50 /// vregs will already have been set up for you by the base class.
51 template <typename AllowedRegsItr>
52 void recordVReg(unsigned vreg, PBQP::Graph::NodeItr node,
53 AllowedRegsItr arBegin, AllowedRegsItr arEnd) {
54 assert(node2VReg.find(node) == node2VReg.end() && "Re-mapping node.");
55 assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg.");
56 assert(allowedSets[vreg].empty() && "vreg already has pregs.");
58 node2VReg[node] = vreg;
59 vreg2Node[vreg] = node;
60 std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg]));
63 /// Get the virtual register corresponding to the given PBQP node.
64 unsigned getVRegForNode(PBQP::Graph::ConstNodeItr node) const;
66 /// Get the PBQP node corresponding to the given virtual register.
67 PBQP::Graph::NodeItr getNodeForVReg(unsigned vreg) const;
69 /// Returns true if the given PBQP option represents a physical register,
71 bool isPRegOption(unsigned vreg, unsigned option) const {
72 // At present we only have spills or pregs, so anything that's not a
73 // spill is a preg. (This might be extended one day to support remat).
74 return !isSpillOption(vreg, option);
77 /// Returns true if the given PBQP option represents spilling, false
79 bool isSpillOption(unsigned vreg, unsigned option) const {
80 // We hardcode option zero as the spill option.
84 /// Returns the allowed set for the given virtual register.
85 const AllowedSet& getAllowedSet(unsigned vreg) const;
87 /// Get PReg for option.
88 unsigned getPRegForOption(unsigned vreg, unsigned option) const;
92 typedef std::map<PBQP::Graph::ConstNodeItr, unsigned,
93 PBQP::NodeItrComparator> Node2VReg;
94 typedef DenseMap<unsigned, PBQP::Graph::NodeItr> VReg2Node;
95 typedef std::map<unsigned, AllowedSet> AllowedSetMap;
101 AllowedSetMap allowedSets;
105 /// Builds PBQP instances to represent register allocation problems. Includes
106 /// spill, interference and coalescing costs by default. You can extend this
107 /// class to support additional constraints for your architecture.
110 PBQPBuilder(const PBQPBuilder&) {}
111 void operator=(const PBQPBuilder&) {}
114 typedef std::set<unsigned> RegSet;
117 /// Default constructor.
120 /// Clean up a PBQPBuilder.
121 virtual ~PBQPBuilder() {}
123 /// Build a PBQP instance to represent the register allocation problem for
124 /// the given MachineFunction.
125 virtual std::auto_ptr<PBQPRAProblem> build(
127 const LiveIntervals *lis,
128 const RegSet &vregs);
131 void addSpillCosts(PBQP::Vector &costVec, PBQP::PBQPNum spillCost);
133 void addInterferenceCosts(PBQP::Matrix &costMat,
134 const PBQPRAProblem::AllowedSet &vr1Allowed,
135 const PBQPRAProblem::AllowedSet &vr2Allowed,
136 const TargetRegisterInfo *tri);
140 /// PBQP based allocators solve the register allocation problem by mapping
141 /// register allocation problems to Partitioned Boolean Quadratic
142 /// Programming problems.
143 class RegAllocPBQP : public MachineFunctionPass {
148 /// Construct a PBQP register allocator.
149 RegAllocPBQP(std::auto_ptr<PBQPBuilder> b) : MachineFunctionPass(ID), builder(b) {}
151 /// Return the pass name.
152 virtual const char* getPassName() const {
153 return "PBQP Register Allocator";
156 /// PBQP analysis usage.
157 virtual void getAnalysisUsage(AnalysisUsage &au) const;
159 /// Perform register allocation
160 virtual bool runOnMachineFunction(MachineFunction &MF);
164 typedef std::map<const LiveInterval*, unsigned> LI2NodeMap;
165 typedef std::vector<const LiveInterval*> Node2LIMap;
166 typedef std::vector<unsigned> AllowedSet;
167 typedef std::vector<AllowedSet> AllowedSetMap;
168 typedef std::pair<unsigned, unsigned> RegPair;
169 typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
170 typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
171 typedef std::set<unsigned> RegSet;
174 std::auto_ptr<PBQPBuilder> builder;
177 const TargetMachine *tm;
178 const TargetRegisterInfo *tri;
179 const TargetInstrInfo *tii;
180 const MachineLoopInfo *loopInfo;
181 MachineRegisterInfo *mri;
182 RenderMachineFunction *rmf;
190 AllowedSetMap allowedSets;
191 RegSet vregsToAlloc, emptyIntervalVRegs;
192 NodeVector problemNodes;
195 /// Builds a PBQP cost vector.
196 template <typename RegContainer>
197 PBQP::Vector buildCostVector(unsigned vReg,
198 const RegContainer &allowed,
199 const CoalesceMap &cealesces,
200 PBQP::PBQPNum spillCost) const;
202 /// \brief Builds a PBQP interference matrix.
204 /// @return Either a pointer to a non-zero PBQP matrix representing the
205 /// allocation option costs, or a null pointer for a zero matrix.
207 /// Expects allowed sets for two interfering LiveIntervals. These allowed
208 /// sets should contain only allocable registers from the LiveInterval's
209 /// register class, with any interfering pre-colored registers removed.
210 template <typename RegContainer>
211 PBQP::Matrix* buildInterferenceMatrix(const RegContainer &allowed1,
212 const RegContainer &allowed2) const;
215 /// Expects allowed sets for two potentially coalescable LiveIntervals,
216 /// and an estimated benefit due to coalescing. The allowed sets should
217 /// contain only allocable registers from the LiveInterval's register
218 /// classes, with any interfering pre-colored registers removed.
219 template <typename RegContainer>
220 PBQP::Matrix* buildCoalescingMatrix(const RegContainer &allowed1,
221 const RegContainer &allowed2,
222 PBQP::PBQPNum cBenefit) const;
224 /// \brief Finds coalescing opportunities and returns them as a map.
226 /// Any entries in the map are guaranteed coalescable, even if their
227 /// corresponding live intervals overlap.
228 CoalesceMap findCoalesces();
230 /// \brief Finds the initial set of vreg intervals to allocate.
231 void findVRegIntervalsToAlloc();
233 /// \brief Constructs a PBQP problem representation of the register
234 /// allocation problem for this function.
236 /// @return a PBQP solver object for the register allocation problem.
237 PBQP::Graph constructPBQPProblem();
239 /// \brief Adds a stack interval if the given live interval has been
240 /// spilled. Used to support stack slot coloring.
241 void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri);
243 /// \brief Given a solved PBQP problem maps this solution back to a register
245 bool mapPBQPToRegAlloc(const PBQP::Solution &solution);
247 /// \brief Given a solved PBQP problem maps this solution back to a register
249 bool mapPBQPToRegAlloc2(const PBQPRAProblem &problem,
250 const PBQP::Solution &solution);
252 /// \brief Postprocessing before final spilling. Sets basic block "live in"
254 void finalizeAlloc() const;
260 #endif /* LLVM_CODEGEN_REGALLOCPBQP_H */