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"
30 class MachineFunction;
31 class MachineLoopInfo;
33 /// This class wraps up a PBQP instance representing a register allocation
34 /// problem, plus the structures necessary to map back from the PBQP solution
35 /// to a register allocation solution. (i.e. The PBQP-node <--> vreg map,
36 /// and the PBQP option <--> storage location map).
41 typedef SmallVector<unsigned, 16> AllowedSet;
43 PBQP::Graph& getGraph() { return graph; }
45 const PBQP::Graph& getGraph() const { return graph; }
47 /// Record the mapping between the given virtual register and PBQP node,
48 /// and the set of allowed pregs for the vreg.
50 /// If you are extending
51 /// PBQPBuilder you are unlikely to need this: Nodes and options for all
52 /// vregs will already have been set up for you by the base class.
53 template <typename AllowedRegsItr>
54 void recordVReg(unsigned vreg, PBQP::Graph::NodeItr node,
55 AllowedRegsItr arBegin, AllowedRegsItr arEnd) {
56 assert(node2VReg.find(node) == node2VReg.end() && "Re-mapping node.");
57 assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg.");
58 assert(allowedSets[vreg].empty() && "vreg already has pregs.");
60 node2VReg[node] = vreg;
61 vreg2Node[vreg] = node;
62 std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg]));
65 /// Get the virtual register corresponding to the given PBQP node.
66 unsigned getVRegForNode(PBQP::Graph::ConstNodeItr node) const;
68 /// Get the PBQP node corresponding to the given virtual register.
69 PBQP::Graph::NodeItr getNodeForVReg(unsigned vreg) const;
71 /// Returns true if the given PBQP option represents a physical register,
73 bool isPRegOption(unsigned vreg, unsigned option) const {
74 // At present we only have spills or pregs, so anything that's not a
75 // spill is a preg. (This might be extended one day to support remat).
76 return !isSpillOption(vreg, option);
79 /// Returns true if the given PBQP option represents spilling, false
81 bool isSpillOption(unsigned vreg, unsigned option) const {
82 // We hardcode option zero as the spill option.
86 /// Returns the allowed set for the given virtual register.
87 const AllowedSet& getAllowedSet(unsigned vreg) const;
89 /// Get PReg for option.
90 unsigned getPRegForOption(unsigned vreg, unsigned option) const;
94 typedef std::map<PBQP::Graph::ConstNodeItr, unsigned,
95 PBQP::NodeItrComparator> Node2VReg;
96 typedef DenseMap<unsigned, PBQP::Graph::NodeItr> VReg2Node;
97 typedef DenseMap<unsigned, AllowedSet> AllowedSetMap;
103 AllowedSetMap allowedSets;
107 /// Builds PBQP instances to represent register allocation problems. Includes
108 /// spill, interference and coalescing costs by default. You can extend this
109 /// class to support additional constraints for your architecture.
112 PBQPBuilder(const PBQPBuilder&) {}
113 void operator=(const PBQPBuilder&) {}
116 typedef std::set<unsigned> RegSet;
118 /// Default constructor.
121 /// Clean up a PBQPBuilder.
122 virtual ~PBQPBuilder() {}
124 /// Build a PBQP instance to represent the register allocation problem for
125 /// the given MachineFunction.
126 virtual std::auto_ptr<PBQPRAProblem> build(
128 const LiveIntervals *lis,
129 const MachineLoopInfo *loopInfo,
130 const RegSet &vregs);
133 void addSpillCosts(PBQP::Vector &costVec, PBQP::PBQPNum spillCost);
135 void addInterferenceCosts(PBQP::Matrix &costMat,
136 const PBQPRAProblem::AllowedSet &vr1Allowed,
137 const PBQPRAProblem::AllowedSet &vr2Allowed,
138 const TargetRegisterInfo *tri);
141 /// Extended builder which adds coalescing constraints to a problem.
142 class PBQPBuilderWithCoalescing : public PBQPBuilder {
145 /// Build a PBQP instance to represent the register allocation problem for
146 /// the given MachineFunction.
147 virtual std::auto_ptr<PBQPRAProblem> build(
149 const LiveIntervals *lis,
150 const MachineLoopInfo *loopInfo,
151 const RegSet &vregs);
155 void addPhysRegCoalesce(PBQP::Vector &costVec, unsigned pregOption,
156 PBQP::PBQPNum benefit);
158 void addVirtRegCoalesce(PBQP::Matrix &costMat,
159 const PBQPRAProblem::AllowedSet &vr1Allowed,
160 const PBQPRAProblem::AllowedSet &vr2Allowed,
161 PBQP::PBQPNum benefit);
164 FunctionPass* createPBQPRegisterAllocator(std::auto_ptr<PBQPBuilder> builder,
165 char *customPassID=0);
168 #endif /* LLVM_CODEGEN_REGALLOCPBQP_H */