32 #define DEBUG_TYPE "regalloc"
72 cl::desc(
"Attempt coalescing during PBQP register allocation."),
78 cl::desc(
"Dump graphs for each function/round in the compilation unit."),
103 virtual const char* getPassName()
const {
104 return "PBQP Register Allocator";
115 typedef std::map<const LiveInterval*, unsigned> LI2NodeMap;
116 typedef std::vector<const LiveInterval*> Node2LIMap;
117 typedef std::vector<unsigned> AllowedSet;
118 typedef std::vector<AllowedSet> AllowedSetMap;
119 typedef std::pair<unsigned, unsigned> RegPair;
120 typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
121 typedef std::set<unsigned> RegSet;
140 RegSet vregsToAlloc, emptyIntervalVRegs;
143 void findVRegIntervalsToAlloc();
152 void finalizeAlloc()
const;
161 Node2VReg::const_iterator vregItr = node2VReg.find(node);
162 assert(vregItr != node2VReg.end() &&
"No vreg for node.");
163 return vregItr->second;
168 assert(nodeItr != vreg2Node.
end() &&
"No node for vreg.");
169 return nodeItr->second;
176 assert(allowedSetItr != allowedSets.
end() &&
"No pregs for vreg.");
177 const AllowedSet &allowedSet = allowedSetItr->second;
182 assert(
isPRegOption(vreg, option) &&
"Not a preg option.");
185 assert(option <= allowedSet.
size() &&
"Option outside allowed set.");
186 return allowedSet[option - 1];
210 for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end();
211 vregItr != vregEnd; ++vregItr) {
212 unsigned vreg = *vregItr;
221 typedef std::vector<unsigned> VRAllowed;
224 for (
unsigned i = 0; i != rawOrder.
size(); ++i) {
225 unsigned preg = rawOrder[i];
230 if (!regMaskOverlaps.
empty() && !regMaskOverlaps.
test(preg))
234 bool Interference =
false;
245 vrAllowed.push_back(preg);
253 p->
recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end());
256 vregLI->
weight : std::numeric_limits<PBQP::PBQPNum>::min();
261 for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end();
262 vr1Itr != vrEnd; ++vr1Itr) {
263 unsigned vr1 = *vr1Itr;
267 for (RegSet::const_iterator vr2Itr =
llvm::next(vr1Itr);
268 vr2Itr != vrEnd; ++vr2Itr) {
269 unsigned vr2 = *vr2Itr;
273 assert(!l2.
empty() &&
"Empty interval in vreg set?");
279 addInterferenceCosts(g.
getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri);
289 costVec[0] = spillCost;
292 void PBQPBuilder::addInterferenceCosts(
297 assert(costMat.
getRows() == vr1Allowed.
size() + 1 &&
"Matrix height mismatch.");
298 assert(costMat.
getCols() == vr2Allowed.
size() + 1 &&
"Matrix width mismatch.");
300 for (
unsigned i = 0; i != vr1Allowed.
size(); ++i) {
301 unsigned preg1 = vr1Allowed[i];
303 for (
unsigned j = 0; j != vr2Allowed.
size(); ++j) {
304 unsigned preg2 = vr2Allowed[j];
307 costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
328 mbbItr != mbbEnd; ++mbbItr) {
333 miItr != miEnd; ++miItr) {
336 if (!cp.setRegisters(mi)) {
340 if (cp.getSrcReg() == cp.getDstReg()) {
344 unsigned dst = cp.getDstReg(),
345 src = cp.getSrcReg();
347 const float copyFactor = 0.5;
360 unsigned pregOpt = 0;
361 while (pregOpt < allowed.
size() && allowed[pregOpt] != dst) {
364 if (pregOpt < allowed.
size()) {
367 addPhysRegCoalesce(g.
getNodeCosts(node), pregOpt, cBenefit);
377 allowed2->
size() + 1,
386 addVirtRegCoalesce(g.
getEdgeCosts(edge), *allowed1, *allowed2,
395 void PBQPBuilderWithCoalescing::addPhysRegCoalesce(
PBQP::Vector &costVec,
398 costVec[pregOption] += -benefit;
401 void PBQPBuilderWithCoalescing::addVirtRegCoalesce(
407 assert(costMat.
getRows() == vr1Allowed.
size() + 1 &&
"Size mismatch.");
408 assert(costMat.
getCols() == vr2Allowed.
size() + 1 &&
"Size mismatch.");
410 for (
unsigned i = 0; i != vr1Allowed.
size(); ++i) {
411 unsigned preg1 = vr1Allowed[i];
412 for (
unsigned j = 0; j != vr2Allowed.
size(); ++j) {
413 unsigned preg2 = vr2Allowed[j];
415 if (preg1 == preg2) {
416 costMat[i + 1][j + 1] += -benefit;
423 void RegAllocPBQP::getAnalysisUsage(
AnalysisUsage &au)
const {
447 void RegAllocPBQP::findVRegIntervalsToAlloc() {
450 for (
unsigned i = 0, e = mri->getNumVirtRegs(); i != e; ++i) {
452 if (mri->reg_nodbg_empty(Reg))
460 vregsToAlloc.insert(li->
reg);
462 emptyIntervalVRegs.insert(li->
reg);
467 bool RegAllocPBQP::mapPBQPToRegAlloc(
const PBQPRAProblem &problem,
470 bool anotherRoundNeeded =
false;
480 nodeItr != nodeEnd; ++nodeItr) {
487 << tri->
getName(preg) <<
"\n");
488 assert(preg != 0 &&
"Invalid preg selected.");
489 vrm->assignVirt2Phys(vreg, preg);
491 vregsToAlloc.erase(vreg);
493 LiveRangeEdit LRE(&lis->getInterval(vreg), newSpills, *mf, *lis, vrm);
497 << LRE.getParent().weight <<
", New vregs: ");
504 assert(!li.
empty() &&
"Empty spill range.");
506 vregsToAlloc.insert(li.
reg);
512 anotherRoundNeeded |= !LRE.empty();
518 return !anotherRoundNeeded;
522 void RegAllocPBQP::finalizeAlloc()
const {
524 for (RegSet::const_iterator
525 itr = emptyIntervalVRegs.begin(),
end = emptyIntervalVRegs.
end();
529 unsigned physReg = mri->getSimpleHint(li->
reg);
536 vrm->assignVirt2Phys(li->
reg, physReg);
544 tri = tm->getRegisterInfo();
545 tii = tm->getInstrInfo();
546 mri = &mf->getRegInfo();
548 lis = &getAnalysis<LiveIntervals>();
549 lss = &getAnalysis<LiveStacks>();
550 mbfi = &getAnalysis<MachineBlockFrequencyInfo>();
555 vrm = &getAnalysis<VirtRegMap>();
558 mri->freezeReservedRegs(MF);
560 DEBUG(
dbgs() <<
"PBQP Register Allocating for " << mf->getName() <<
"\n");
572 findVRegIntervalsToAlloc();
575 const Function* func = mf->getFunction();
582 if (!vregsToAlloc.empty()) {
584 bool pbqpAllocComplete =
false;
587 while (!pbqpAllocComplete) {
588 DEBUG(
dbgs() <<
" PBQP Regalloc round " << round <<
":\n");
591 builder->build(mf, lis, mbfi, vregsToAlloc));
595 std::ostringstream rs;
597 std::string graphFileName(fqn +
"." + rs.str() +
".pbqpgraph");
600 DEBUG(
dbgs() <<
"Dumping graph for round " << round <<
" to \""
601 << graphFileName <<
"\"\n");
610 pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution);
618 vregsToAlloc.clear();
619 emptyIntervalVRegs.clear();
621 DEBUG(
dbgs() <<
"Post alloc VirtRegMap:\n" << *vrm <<
"\n");
628 char *customPassID) {
629 return new RegAllocPBQP(builder, customPassID);
static float getSpillWeight(bool isDef, bool isUse, BlockFrequency freq)
unsigned getPRegForOption(unsigned vreg, unsigned option) const
Get PReg for option.
const_iterator end(StringRef path)
Get end iterator over path.
void setPhysRegUsed(unsigned Reg)
EdgeId invalidEdgeId() const
AnalysisUsage & addPreserved()
static PassRegistry * getPassRegistry()
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Vector & getNodeCosts(NodeId nId)
Get a node's cost vector.
static unsigned index2VirtReg(unsigned Index)
const T & front() const
front - Get the first element.
void recordVReg(unsigned vreg, PBQP::Graph::NodeId nodeId, AllowedRegsItr arBegin, AllowedRegsItr arEnd)
NodeItr nodesEnd() const
End iterator for node set.
NodeId getEdgeNode1(EdgeId eId)
Get the first node connected to this edge.
std::string str() const
str - Get the contents as an std::string.
virtual PBQPRAProblem * build(MachineFunction *mf, const LiveIntervals *lis, const MachineBlockFrequencyInfo *mbfi, const RegSet &vregs)
Extended builder which adds coalescing constraints to a problem.
void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF, const MachineLoopInfo &MLI, const MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo::NormalizingFn norm=normalizeSpillWeight)
Compute spill weights and allocation hints for all virtual register live intervals.
bool checkRegMaskInterference(LiveInterval &LI, BitVector &UsableRegs)
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
StringRef getName() const
AnalysisUsage & addRequired()
NodeId addNode(const Vector &costs)
Add a node with the given costs.
#define llvm_unreachable(msg)
ArrayRef< MCPhysReg > getRawAllocationOrder(const MachineFunction &MF) const
const TargetRegisterClass * getRegClass(unsigned Reg) const
SmallVectorImpl< unsigned >::const_iterator iterator
Iterator for accessing the new registers added by this edit.
ID
LLVM Calling Convention Representation.
const std::string & getModuleIdentifier() const
unsigned getRows() const
Return the number of rows in this matrix.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
std::set< unsigned > RegSet
unsigned getSelection(Graph::NodeId nodeId) const
Get a node's selection.
EdgeId findEdge(NodeId n1Id, NodeId n2Id)
Get the edge connecting two nodes.
static cl::opt< bool > pbqpCoalescing("pbqp-coalescing", cl::desc("Attempt coalescing during PBQP register allocation."), cl::init(false), cl::Hidden)
size_t size() const
size - Get the array size.
initializer< Ty > init(const Ty &Val)
friend const_iterator end(StringRef path)
Get end iterator over path.
static Solution solve(Graph &g)
void initializeSlotIndexesPass(PassRegistry &)
bool regsOverlap(unsigned regA, unsigned regB) const
FunctionPass * createPBQPRegisterAllocator(OwningPtr< PBQPBuilder > &builder, char *customPassID=0)
void initializeLiveStacksPass(PassRegistry &)
bool isReserved(unsigned PhysReg) const
const AllowedSet & getAllowedSet(unsigned vreg) const
Returns the allowed set for the given virtual register.
bool empty() const
empty - Tests whether there are no bits in this bitvector.
static RegisterRegAlloc registerPBQPRepAlloc("pbqp","PBQP register allocator", createDefaultPBQPRegisterAllocator)
bool overlaps(const LiveRange &other) const
ItTy next(ItTy it, Dist n)
void initializeLiveIntervalsPass(PassRegistry &)
FunctionPass * createDefaultPBQPRegisterAllocator()
bool isPRegOption(unsigned vreg, unsigned option) const
virtual PBQPRAProblem * build(MachineFunction *mf, const LiveIntervals *lis, const MachineBlockFrequencyInfo *mbfi, const RegSet &vregs)
unsigned getVRegForNode(PBQP::Graph::NodeId nodeId) const
Get the virtual register corresponding to the given PBQP node.
bool isSpillOption(unsigned vreg, unsigned option) const
PBQP::Graph::NodeId getNodeForVReg(unsigned vreg) const
Get the PBQP node corresponding to the given virtual register.
AnalysisUsage & addRequiredID(const void *ID)
bool test(unsigned Idx) const
bool isAllocatable(unsigned PhysReg) const
Matrix & getEdgeCosts(EdgeId eId)
Get an edge's cost matrix.
LiveInterval & getInterval(unsigned Reg)
raw_ostream & dbgs()
dbgs - Return a circular-buffered debug stream.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
void dump(OStream &os)
Dump a graph to an output stream.
void initializeVirtRegMapPass(PassRegistry &)
Spiller * createInlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm)
Represents a solution to a PBQP problem.
bundle_iterator< const MachineInstr, const_instr_iterator > const_iterator
MachineRegisterInfo & getRegInfo()
virtual void getAnalysisUsage(AnalysisUsage &AU) const
const TargetMachine & getTarget() const
virtual const TargetRegisterInfo * getRegisterInfo() const
EdgeId addEdge(NodeId n1Id, NodeId n2Id, const Matrix &costs)
Add an edge between the given nodes with the given costs.
bool def_empty(unsigned RegNo) const
static cl::opt< bool > pbqpDumpGraphs("pbqp-dump-graphs", cl::desc("Dump graphs for each function/round in the compilation unit."), cl::init(false), cl::Hidden)
NodeItr nodesBegin() const
Begin iterator for node set.
const char * getName(unsigned RegNo) const
Return the human-readable symbolic target-specific name for the specified physical register...
iterator find(const KeyT &Val)
unsigned getCols() const
Return the number of cols in this matrix.
LiveRange & getRegUnit(unsigned Unit)