include/llvm/CodeGen/RegAllocPBQP.h

   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
  26 namespace llvm {
  27
  28   class LiveInterval;
  29   class MachineFunction;
  30
  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).
  35
  36   class PBQPRAProblem {
  37   public:
  38
  39     typedef SmallVector<unsigned, 16> AllowedSet;
  40
  41     PBQP::Graph& getGraph() { return graph; }
  42
  43     const PBQP::Graph& getGraph() const { return graph; }
  44
  45     /// Record the mapping between the given virtual register and PBQP node,
  46     /// and the set of allowed pregs for the vreg.
  47     ///
  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.");
  57
  58       node2VReg[node] = vreg;
  59       vreg2Node[vreg] = node;
  60       std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg]));
  61     }
  62
  63     /// Get the virtual register corresponding to the given PBQP node.
  64     unsigned getVRegForNode(PBQP::Graph::ConstNodeItr node) const;
  65
  66     /// Get the PBQP node corresponding to the given virtual register.
  67     PBQP::Graph::NodeItr getNodeForVReg(unsigned vreg) const;
  68
  69     /// Returns true if the given PBQP option represents a physical register,
  70     /// false otherwise.
  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);
  75     }
  76
  77     /// Returns true if the given PBQP option represents spilling, false
  78     /// otherwise.
  79     bool isSpillOption(unsigned vreg, unsigned option) const {
  80       // We hardcode option zero as the spill option.
  81       return option == 0;
  82     }
  83
  84     /// Returns the allowed set for the given virtual register.
  85     const AllowedSet& getAllowedSet(unsigned vreg) const;
  86
  87     /// Get PReg for option.
  88     unsigned getPRegForOption(unsigned vreg, unsigned option) const;
  89
  90   private:
  91
  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;
  96
  97     PBQP::Graph graph;
  98     Node2VReg node2VReg;
  99     VReg2Node vreg2Node;
 100
 101     AllowedSetMap allowedSets;
 102
 103   };
 104
 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.
 108   class PBQPBuilder {
 109   private:
 110     PBQPBuilder(const PBQPBuilder&) {}
 111     void operator=(const PBQPBuilder&) {}
 112   public:
 113
 114     typedef std::set<unsigned> RegSet;
 115
 116
 117     /// Default constructor.
 118     PBQPBuilder() {}
 119
 120     /// Clean up a PBQPBuilder.
 121     virtual ~PBQPBuilder() {}
 122
 123     /// Build a PBQP instance to represent the register allocation problem for
 124     /// the given MachineFunction.
 125     virtual std::auto_ptr<PBQPRAProblem> build(
 126                                               MachineFunction *mf,
 127                                               const LiveIntervals *lis,
 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   ///
 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 {
 144   public:
 145
 146     static char ID;
 147
 148     /// Construct a PBQP register allocator.
 149     RegAllocPBQP(std::auto_ptr<PBQPBuilder> b) : MachineFunctionPass(ID), builder(b) {}
 150
 151     /// Return the pass name.
 152     virtual const char* getPassName() const {
 153       return "PBQP Register Allocator";
 154     }
 155
 156     /// PBQP analysis usage.
 157     virtual void getAnalysisUsage(AnalysisUsage &au) const;
 158
 159     /// Perform register allocation
 160     virtual bool runOnMachineFunction(MachineFunction &MF);
 161
 162   private:
 163
 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;
 172
 173
 174     std::auto_ptr<PBQPBuilder> builder;
 175
 176     MachineFunction *mf;
 177     const TargetMachine *tm;
 178     const TargetRegisterInfo *tri;
 179     const TargetInstrInfo *tii;
 180     const MachineLoopInfo *loopInfo;
 181     MachineRegisterInfo *mri;
 182     RenderMachineFunction *rmf;
 183
 184     LiveIntervals *lis;
 185     LiveStacks *lss;
 186     VirtRegMap *vrm;
 187
 188     LI2NodeMap li2Node;
 189     Node2LIMap node2LI;
 190     AllowedSetMap allowedSets;
 191     RegSet vregsToAlloc, emptyIntervalVRegs;
 192     NodeVector problemNodes;
 193
 194
 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;
 201
 202     /// \brief Builds a PBQP interference matrix.
 203     ///
 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.
 206     ///
 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;
 213
 214     ///
 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;
 223
 224     /// \brief Finds coalescing opportunities and returns them as a map.
 225     ///
 226     /// Any entries in the map are guaranteed coalescable, even if their
 227     /// corresponding live intervals overlap.
 228     CoalesceMap findCoalesces();
 229
 230     /// \brief Finds the initial set of vreg intervals to allocate.
 231     void findVRegIntervalsToAlloc();
 232
 233     /// \brief Constructs a PBQP problem representation of the register
 234     /// allocation problem for this function.
 235     ///
 236     /// @return a PBQP solver object for the register allocation problem.
 237     PBQP::Graph constructPBQPProblem();
 238
 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);
 242
 243     /// \brief Given a solved PBQP problem maps this solution back to a register
 244     /// assignment.
 245     bool mapPBQPToRegAlloc(const PBQP::Solution &solution);
 246
 247     /// \brief Given a solved PBQP problem maps this solution back to a register
 248     /// assignment.
 249     bool mapPBQPToRegAlloc2(const PBQPRAProblem &problem,
 250                             const PBQP::Solution &solution);
 251
 252     /// \brief Postprocessing before final spilling. Sets basic block "live in"
 253     /// variables.
 254     void finalizeAlloc() const;
 255
 256   };
 257
 258 }
 259
 260 #endif /* LLVM_CODEGEN_REGALLOCPBQP_H */