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 #include <map> 24 #include <set> 25 26 namespace llvm { 27 28 class LiveIntervals; 29 class MachineBlockFrequencyInfo; 30 class MachineFunction; 31 class TargetRegisterInfo; 32 template<class T> class OwningPtr; 33 34 /// This class wraps up a PBQP instance representing a register allocation 35 /// problem, plus the structures necessary to map back from the PBQP solution 36 /// to a register allocation solution. (i.e. The PBQP-node <--> vreg map, 37 /// and the PBQP option <--> storage location map). 38 39 class PBQPRAProblem { 40 public: 41 42 typedef SmallVector<unsigned, 16> AllowedSet; 43 44 PBQP::Graph& getGraph() { return graph; } 45 46 const PBQP::Graph& getGraph() const { return graph; } 47 48 /// Record the mapping between the given virtual register and PBQP node, 49 /// and the set of allowed pregs for the vreg. 50 /// 51 /// If you are extending 52 /// PBQPBuilder you are unlikely to need this: Nodes and options for all 53 /// vregs will already have been set up for you by the base class. 54 template <typename AllowedRegsItr> 55 void recordVReg(unsigned vreg, PBQP::Graph::NodeItr node, 56 AllowedRegsItr arBegin, AllowedRegsItr arEnd) { 57 assert(node2VReg.find(node) == node2VReg.end() && "Re-mapping node."); 58 assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg."); 59 assert(allowedSets[vreg].empty() && "vreg already has pregs."); 60 61 node2VReg[node] = vreg; 62 vreg2Node[vreg] = node; 63 std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg])); 64 } 65 66 /// Get the virtual register corresponding to the given PBQP node. 67 unsigned getVRegForNode(PBQP::Graph::ConstNodeItr node) const; 68 69 /// Get the PBQP node corresponding to the given virtual register. 70 PBQP::Graph::NodeItr getNodeForVReg(unsigned vreg) const; 71 72 /// Returns true if the given PBQP option represents a physical register, 73 /// false otherwise. 74 bool isPRegOption(unsigned vreg, unsigned option) const { 75 // At present we only have spills or pregs, so anything that's not a 76 // spill is a preg. (This might be extended one day to support remat). 77 return !isSpillOption(vreg, option); 78 } 79 80 /// Returns true if the given PBQP option represents spilling, false 81 /// otherwise. 82 bool isSpillOption(unsigned vreg, unsigned option) const { 83 // We hardcode option zero as the spill option. 84 return option == 0; 85 } 86 87 /// Returns the allowed set for the given virtual register. 88 const AllowedSet& getAllowedSet(unsigned vreg) const; 89 90 /// Get PReg for option. 91 unsigned getPRegForOption(unsigned vreg, unsigned option) const; 92 93 private: 94 95 typedef std::map<PBQP::Graph::ConstNodeItr, unsigned, 96 PBQP::NodeItrComparator> Node2VReg; 97 typedef DenseMap<unsigned, PBQP::Graph::NodeItr> VReg2Node; 98 typedef DenseMap<unsigned, AllowedSet> AllowedSetMap; 99 100 PBQP::Graph graph; 101 Node2VReg node2VReg; 102 VReg2Node vreg2Node; 103 104 AllowedSetMap allowedSets; 105 106 }; 107 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. 111 class PBQPBuilder { 112 private: 113 PBQPBuilder(const PBQPBuilder&) LLVM_DELETED_FUNCTION; 114 void operator=(const PBQPBuilder&) LLVM_DELETED_FUNCTION; 115 public: 116 117 typedef std::set<unsigned> RegSet; 118 119 /// Default constructor. 120 PBQPBuilder() {} 121 122 /// Clean up a PBQPBuilder. 123 virtual ~PBQPBuilder() {} 124 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); 130 private: 131 132 void addSpillCosts(PBQP::Vector &costVec, PBQP::PBQPNum spillCost); 133 134 void addInterferenceCosts(PBQP::Matrix &costMat, 135 const PBQPRAProblem::AllowedSet &vr1Allowed, 136 const PBQPRAProblem::AllowedSet &vr2Allowed, 137 const TargetRegisterInfo *tri); 138 }; 139 140 /// Extended builder which adds coalescing constraints to a problem. 141 class PBQPBuilderWithCoalescing : public PBQPBuilder { 142 public: 143 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); 149 150 private: 151 152 void addPhysRegCoalesce(PBQP::Vector &costVec, unsigned pregOption, 153 PBQP::PBQPNum benefit); 154 155 void addVirtRegCoalesce(PBQP::Matrix &costMat, 156 const PBQPRAProblem::AllowedSet &vr1Allowed, 157 const PBQPRAProblem::AllowedSet &vr2Allowed, 158 PBQP::PBQPNum benefit); 159 }; 160 161 FunctionPass* createPBQPRegisterAllocator(OwningPtr<PBQPBuilder> &builder, 162 char *customPassID=0); 163 } 164 165 #endif /* LLVM_CODEGEN_REGALLOCPBQP_H */ 166
