1 //===-- RegAllocPBQP.h ------------------------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the PBQPBuilder interface, for classes which build PBQP 11 // instances to represent register allocation problems, and the RegAllocPBQP 12 // interface. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_CODEGEN_REGALLOCPBQP_H 17 #define LLVM_CODEGEN_REGALLOCPBQP_H 18 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" 23 24 #include <map> 25 #include <set> 26 27 namespace llvm { 28 29 class LiveIntervals; 30 class MachineFunction; 31 class MachineLoopInfo; 32 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). 37 38 class PBQPRAProblem { 39 public: 40 41 typedef SmallVector<unsigned, 16> AllowedSet; 42 43 PBQP::Graph& getGraph() { return graph; } 44 45 const PBQP::Graph& getGraph() const { return graph; } 46 47 /// Record the mapping between the given virtual register and PBQP node, 48 /// and the set of allowed pregs for the vreg. 49 /// 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."); 59 60 node2VReg[node] = vreg; 61 vreg2Node[vreg] = node; 62 std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg])); 63 } 64 65 /// Get the virtual register corresponding to the given PBQP node. 66 unsigned getVRegForNode(PBQP::Graph::ConstNodeItr node) const; 67 68 /// Get the PBQP node corresponding to the given virtual register. 69 PBQP::Graph::NodeItr getNodeForVReg(unsigned vreg) const; 70 71 /// Returns true if the given PBQP option represents a physical register, 72 /// false otherwise. 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); 77 } 78 79 /// Returns true if the given PBQP option represents spilling, false 80 /// otherwise. 81 bool isSpillOption(unsigned vreg, unsigned option) const { 82 // We hardcode option zero as the spill option. 83 return option == 0; 84 } 85 86 /// Returns the allowed set for the given virtual register. 87 const AllowedSet& getAllowedSet(unsigned vreg) const; 88 89 /// Get PReg for option. 90 unsigned getPRegForOption(unsigned vreg, unsigned option) const; 91 92 private: 93 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; 98 99 PBQP::Graph graph; 100 Node2VReg node2VReg; 101 VReg2Node vreg2Node; 102 103 AllowedSetMap allowedSets; 104 105 }; 106 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. 110 class PBQPBuilder { 111 private: 112 PBQPBuilder(const PBQPBuilder&) {} 113 void operator=(const PBQPBuilder&) {} 114 public: 115 116 typedef std::set<unsigned> RegSet; 117 118 /// Default constructor. 119 PBQPBuilder() {} 120 121 /// Clean up a PBQPBuilder. 122 virtual ~PBQPBuilder() {} 123 124 /// Build a PBQP instance to represent the register allocation problem for 125 /// the given MachineFunction. 126 virtual std::auto_ptr<PBQPRAProblem> build( 127 MachineFunction *mf, 128 const LiveIntervals *lis, 129 const MachineLoopInfo *loopInfo, 130 const RegSet &vregs); 131 private: 132 133 void addSpillCosts(PBQP::Vector &costVec, PBQP::PBQPNum spillCost); 134 135 void addInterferenceCosts(PBQP::Matrix &costMat, 136 const PBQPRAProblem::AllowedSet &vr1Allowed, 137 const PBQPRAProblem::AllowedSet &vr2Allowed, 138 const TargetRegisterInfo *tri); 139 }; 140 141 /// Extended builder which adds coalescing constraints to a problem. 142 class PBQPBuilderWithCoalescing : public PBQPBuilder { 143 public: 144 145 /// Build a PBQP instance to represent the register allocation problem for 146 /// the given MachineFunction. 147 virtual std::auto_ptr<PBQPRAProblem> build( 148 MachineFunction *mf, 149 const LiveIntervals *lis, 150 const MachineLoopInfo *loopInfo, 151 const RegSet &vregs); 152 153 private: 154 155 void addPhysRegCoalesce(PBQP::Vector &costVec, unsigned pregOption, 156 PBQP::PBQPNum benefit); 157 158 void addVirtRegCoalesce(PBQP::Matrix &costMat, 159 const PBQPRAProblem::AllowedSet &vr1Allowed, 160 const PBQPRAProblem::AllowedSet &vr2Allowed, 161 PBQP::PBQPNum benefit); 162 }; 163 164 FunctionPass* createPBQPRegisterAllocator(std::auto_ptr<PBQPBuilder> builder, 165 char *customPassID=0); 166 } 167 168 #endif /* LLVM_CODEGEN_REGALLOCPBQP_H */ 169
