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 #include <map>
  24 #include <set>
  25
  26 namespace llvm {
  27
  28   class LiveIntervals;
  29   class MachineFunction;
  30   class MachineLoopInfo;
  31   class TargetRegisterInfo;
  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&) 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 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 */