RegAllocPBQP.h revision 263508 
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
26namespace 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::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(PBQP::Graph::NodeId nodeId) const;
68
69    /// Get the PBQP node corresponding to the given virtual register.
70    PBQP::Graph::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<PBQP::Graph::NodeId, unsigned>  Node2VReg;
96    typedef DenseMap<unsigned, PBQP::Graph::NodeId> 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 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    virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis,
146                                 const MachineBlockFrequencyInfo *mbfi,
147                                 const RegSet &vregs);
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* createPBQPRegisterAllocator(OwningPtr<PBQPBuilder> &builder,
161                                            char *customPassID=0);
162}
163
164#endif /* LLVM_CODEGEN_REGALLOCPBQP_H */
165