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/ADT/SmallVector.h" 21 #include "llvm/CodeGen/MachineFunctionPass.h" 22 #include "llvm/CodeGen/PBQP/RegAllocSolver.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 33 typedef PBQP::RegAlloc::Graph PBQPRAGraph; 34 35 /// This class wraps up a PBQP instance representing a register allocation 36 /// problem, plus the structures necessary to map back from the PBQP solution 37 /// to a register allocation solution. (i.e. The PBQP-node <--> vreg map, 38 /// and the PBQP option <--> storage location map). 39 class PBQPRAProblem { 40 public: 41 42 typedef SmallVector<unsigned, 16> AllowedSet; 43 44 PBQPRAGraph& getGraph() { return graph; } 45 46 const PBQPRAGraph& 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, PBQPRAGraph::NodeId nodeId, 56 AllowedRegsItr arBegin, AllowedRegsItr arEnd) { 57 assert(node2VReg.find(nodeId) == 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[nodeId] = vreg; 62 vreg2Node[vreg] = nodeId; 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(PBQPRAGraph::NodeId nodeId) const; 68 69 /// Get the PBQP node corresponding to the given virtual register. 70 PBQPRAGraph::NodeId 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<PBQPRAGraph::NodeId, unsigned> Node2VReg; 96 typedef DenseMap<unsigned, PBQPRAGraph::NodeId> VReg2Node; 97 typedef DenseMap<unsigned, AllowedSet> AllowedSetMap; 98 99 PBQPRAGraph 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&) LLVM_DELETED_FUNCTION; 113 void operator=(const PBQPBuilder&) LLVM_DELETED_FUNCTION; 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 PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis, 127 const MachineBlockFrequencyInfo *mbfi, 128 const RegSet &vregs); 129 private: 130 131 void addSpillCosts(PBQP::Vector &costVec, PBQP::PBQPNum spillCost); 132 133 void addInterferenceCosts(PBQP::Matrix &costMat, 134 const PBQPRAProblem::AllowedSet &vr1Allowed, 135 const PBQPRAProblem::AllowedSet &vr2Allowed, 136 const TargetRegisterInfo *tri); 137 }; 138 139 /// Extended builder which adds coalescing constraints to a problem. 140 class PBQPBuilderWithCoalescing : public PBQPBuilder { 141 public: 142 143 /// Build a PBQP instance to represent the register allocation problem for 144 /// the given MachineFunction. 145 PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis, 146 const MachineBlockFrequencyInfo *mbfi, 147 const RegSet &vregs) override; 148 149 private: 150 151 void addPhysRegCoalesce(PBQP::Vector &costVec, unsigned pregOption, 152 PBQP::PBQPNum benefit); 153 154 void addVirtRegCoalesce(PBQP::Matrix &costMat, 155 const PBQPRAProblem::AllowedSet &vr1Allowed, 156 const PBQPRAProblem::AllowedSet &vr2Allowed, 157 PBQP::PBQPNum benefit); 158 }; 159 160 FunctionPass * 161 createPBQPRegisterAllocator(std::unique_ptr<PBQPBuilder> &builder, 162 char *customPassID = nullptr); 163 } 164 165 #endif /* LLVM_CODEGEN_REGALLOCPBQP_H */ 166
