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/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   template<class T> class OwningPtr;
  33
  34   typedef PBQP::RegAlloc::Graph PBQPRAGraph;
  35
  36   /// This class wraps up a PBQP instance representing a register allocation
  37   /// problem, plus the structures necessary to map back from the PBQP solution
  38   /// to a register allocation solution. (i.e. The PBQP-node <--> vreg map,
  39   /// and the PBQP option <--> storage location map).
  40   class PBQPRAProblem {
  41   public:
  42
  43     typedef SmallVector<unsigned, 16> AllowedSet;
  44
  45     PBQPRAGraph& getGraph() { return graph; }
  46
  47     const PBQPRAGraph& getGraph() const { return graph; }
  48
  49     /// Record the mapping between the given virtual register and PBQP node,
  50     /// and the set of allowed pregs for the vreg.
  51     ///
  52     /// If you are extending
  53     /// PBQPBuilder you are unlikely to need this: Nodes and options for all
  54     /// vregs will already have been set up for you by the base class.
  55     template <typename AllowedRegsItr>
  56     void recordVReg(unsigned vreg, PBQPRAGraph::NodeId nodeId,
  57                     AllowedRegsItr arBegin, AllowedRegsItr arEnd) {
  58       assert(node2VReg.find(nodeId) == node2VReg.end() && "Re-mapping node.");
  59       assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg.");
  60       assert(allowedSets[vreg].empty() && "vreg already has pregs.");
  61
  62       node2VReg[nodeId] = vreg;
  63       vreg2Node[vreg] = nodeId;
  64       std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg]));
  65     }
  66
  67     /// Get the virtual register corresponding to the given PBQP node.
  68     unsigned getVRegForNode(PBQPRAGraph::NodeId nodeId) const;
  69
  70     /// Get the PBQP node corresponding to the given virtual register.
  71     PBQPRAGraph::NodeId getNodeForVReg(unsigned vreg) const;
  72
  73     /// Returns true if the given PBQP option represents a physical register,
  74     /// false otherwise.
  75     bool isPRegOption(unsigned vreg, unsigned option) const {
  76       // At present we only have spills or pregs, so anything that's not a
  77       // spill is a preg. (This might be extended one day to support remat).
  78       return !isSpillOption(vreg, option);
  79     }
  80
  81     /// Returns true if the given PBQP option represents spilling, false
  82     /// otherwise.
  83     bool isSpillOption(unsigned vreg, unsigned option) const {
  84       // We hardcode option zero as the spill option.
  85       return option == 0;
  86     }
  87
  88     /// Returns the allowed set for the given virtual register.
  89     const AllowedSet& getAllowedSet(unsigned vreg) const;
  90
  91     /// Get PReg for option.
  92     unsigned getPRegForOption(unsigned vreg, unsigned option) const;
  93
  94   private:
  95
  96     typedef std::map<PBQPRAGraph::NodeId, unsigned>  Node2VReg;
  97     typedef DenseMap<unsigned, PBQPRAGraph::NodeId> VReg2Node;
  98     typedef DenseMap<unsigned, AllowedSet> AllowedSetMap;
  99
 100     PBQPRAGraph 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 */