/usr/include/llvm-3.5/llvm/CodeGen/RegAllocPBQP.h is in llvm-3.5-dev 1:3.5~svn201651-1ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 | //===-- RegAllocPBQP.h ------------------------------------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the PBQPBuilder interface, for classes which build PBQP
// instances to represent register allocation problems, and the RegAllocPBQP
// interface.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_REGALLOCPBQP_H
#define LLVM_CODEGEN_REGALLOCPBQP_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/PBQP/Graph.h"
#include "llvm/CodeGen/PBQP/Solution.h"
#include <map>
#include <set>
namespace llvm {
class LiveIntervals;
class MachineBlockFrequencyInfo;
class MachineFunction;
class TargetRegisterInfo;
template<class T> class OwningPtr;
/// This class wraps up a PBQP instance representing a register allocation
/// problem, plus the structures necessary to map back from the PBQP solution
/// to a register allocation solution. (i.e. The PBQP-node <--> vreg map,
/// and the PBQP option <--> storage location map).
class PBQPRAProblem {
public:
typedef SmallVector<unsigned, 16> AllowedSet;
PBQP::Graph& getGraph() { return graph; }
const PBQP::Graph& getGraph() const { return graph; }
/// Record the mapping between the given virtual register and PBQP node,
/// and the set of allowed pregs for the vreg.
///
/// If you are extending
/// PBQPBuilder you are unlikely to need this: Nodes and options for all
/// vregs will already have been set up for you by the base class.
template <typename AllowedRegsItr>
void recordVReg(unsigned vreg, PBQP::Graph::NodeId nodeId,
AllowedRegsItr arBegin, AllowedRegsItr arEnd) {
assert(node2VReg.find(nodeId) == node2VReg.end() && "Re-mapping node.");
assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg.");
assert(allowedSets[vreg].empty() && "vreg already has pregs.");
node2VReg[nodeId] = vreg;
vreg2Node[vreg] = nodeId;
std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg]));
}
/// Get the virtual register corresponding to the given PBQP node.
unsigned getVRegForNode(PBQP::Graph::NodeId nodeId) const;
/// Get the PBQP node corresponding to the given virtual register.
PBQP::Graph::NodeId getNodeForVReg(unsigned vreg) const;
/// Returns true if the given PBQP option represents a physical register,
/// false otherwise.
bool isPRegOption(unsigned vreg, unsigned option) const {
// At present we only have spills or pregs, so anything that's not a
// spill is a preg. (This might be extended one day to support remat).
return !isSpillOption(vreg, option);
}
/// Returns true if the given PBQP option represents spilling, false
/// otherwise.
bool isSpillOption(unsigned vreg, unsigned option) const {
// We hardcode option zero as the spill option.
return option == 0;
}
/// Returns the allowed set for the given virtual register.
const AllowedSet& getAllowedSet(unsigned vreg) const;
/// Get PReg for option.
unsigned getPRegForOption(unsigned vreg, unsigned option) const;
private:
typedef std::map<PBQP::Graph::NodeId, unsigned> Node2VReg;
typedef DenseMap<unsigned, PBQP::Graph::NodeId> VReg2Node;
typedef DenseMap<unsigned, AllowedSet> AllowedSetMap;
PBQP::Graph graph;
Node2VReg node2VReg;
VReg2Node vreg2Node;
AllowedSetMap allowedSets;
};
/// Builds PBQP instances to represent register allocation problems. Includes
/// spill, interference and coalescing costs by default. You can extend this
/// class to support additional constraints for your architecture.
class PBQPBuilder {
private:
PBQPBuilder(const PBQPBuilder&) LLVM_DELETED_FUNCTION;
void operator=(const PBQPBuilder&) LLVM_DELETED_FUNCTION;
public:
typedef std::set<unsigned> RegSet;
/// Default constructor.
PBQPBuilder() {}
/// Clean up a PBQPBuilder.
virtual ~PBQPBuilder() {}
/// Build a PBQP instance to represent the register allocation problem for
/// the given MachineFunction.
virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis,
const MachineBlockFrequencyInfo *mbfi,
const RegSet &vregs);
private:
void addSpillCosts(PBQP::Vector &costVec, PBQP::PBQPNum spillCost);
void addInterferenceCosts(PBQP::Matrix &costMat,
const PBQPRAProblem::AllowedSet &vr1Allowed,
const PBQPRAProblem::AllowedSet &vr2Allowed,
const TargetRegisterInfo *tri);
};
/// Extended builder which adds coalescing constraints to a problem.
class PBQPBuilderWithCoalescing : public PBQPBuilder {
public:
/// Build a PBQP instance to represent the register allocation problem for
/// the given MachineFunction.
virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis,
const MachineBlockFrequencyInfo *mbfi,
const RegSet &vregs);
private:
void addPhysRegCoalesce(PBQP::Vector &costVec, unsigned pregOption,
PBQP::PBQPNum benefit);
void addVirtRegCoalesce(PBQP::Matrix &costMat,
const PBQPRAProblem::AllowedSet &vr1Allowed,
const PBQPRAProblem::AllowedSet &vr2Allowed,
PBQP::PBQPNum benefit);
};
FunctionPass* createPBQPRegisterAllocator(OwningPtr<PBQPBuilder> &builder,
char *customPassID=0);
}
#endif /* LLVM_CODEGEN_REGALLOCPBQP_H */
|