//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "regalloc"
-
-#include "Spiller.h"
-#include "VirtRegMap.h"
+#include "llvm/CodeGen/RegAllocPBQP.h"
#include "RegisterCoalescer.h"
-#include "llvm/Module.h"
+#include "Spiller.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
-#include "llvm/CodeGen/RegAllocPBQP.h"
+#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/PBQP/HeuristicSolver.h"
-#include "llvm/CodeGen/PBQP/Graph.h"
-#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
+#include "llvm/CodeGen/VirtRegMap.h"
+#include "llvm/IR/Module.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/FileSystem.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
#include <limits>
#include <memory>
#include <set>
using namespace llvm;
+#define DEBUG_TYPE "regalloc"
+
static RegisterRegAlloc
registerPBQPRepAlloc("pbqp", "PBQP register allocator",
createDefaultPBQPRegisterAllocator);
static char ID;
/// Construct a PBQP register allocator.
- RegAllocPBQP(std::auto_ptr<PBQPBuilder> b, char *cPassID=0)
- : MachineFunctionPass(ID), builder(b), customPassID(cPassID) {
+ RegAllocPBQP(std::unique_ptr<PBQPBuilder> b, char *cPassID = nullptr)
+ : MachineFunctionPass(ID), builder(std::move(b)), customPassID(cPassID) {
initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
- initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
initializeLiveStacksPass(*PassRegistry::getPassRegistry());
- initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
}
/// Return the pass name.
- virtual const char* getPassName() const {
+ const char* getPassName() const override {
return "PBQP Register Allocator";
}
/// PBQP analysis usage.
- virtual void getAnalysisUsage(AnalysisUsage &au) const;
+ void getAnalysisUsage(AnalysisUsage &au) const override;
/// Perform register allocation
- virtual bool runOnMachineFunction(MachineFunction &MF);
+ bool runOnMachineFunction(MachineFunction &MF) override;
private:
typedef std::vector<AllowedSet> AllowedSetMap;
typedef std::pair<unsigned, unsigned> RegPair;
typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
- typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
typedef std::set<unsigned> RegSet;
-
- std::auto_ptr<PBQPBuilder> builder;
+ std::unique_ptr<PBQPBuilder> builder;
char *customPassID;
const TargetMachine *tm;
const TargetRegisterInfo *tri;
const TargetInstrInfo *tii;
- const MachineLoopInfo *loopInfo;
MachineRegisterInfo *mri;
+ const MachineBlockFrequencyInfo *mbfi;
- std::auto_ptr<Spiller> spiller;
+ std::unique_ptr<Spiller> spiller;
LiveIntervals *lis;
LiveStacks *lss;
VirtRegMap *vrm;
} // End anonymous namespace.
-unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const {
+unsigned PBQPRAProblem::getVRegForNode(PBQPRAGraph::NodeId node) const {
Node2VReg::const_iterator vregItr = node2VReg.find(node);
assert(vregItr != node2VReg.end() && "No vreg for node.");
return vregItr->second;
}
-PBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const {
+PBQPRAGraph::NodeId PBQPRAProblem::getNodeForVReg(unsigned vreg) const {
VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg);
assert(nodeItr != vreg2Node.end() && "No node for vreg.");
return nodeItr->second;
return allowedSet[option - 1];
}
-std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf,
- const LiveIntervals *lis,
- const MachineLoopInfo *loopInfo,
- const RegSet &vregs) {
+PBQPRAProblem *PBQPBuilder::build(MachineFunction *mf, const LiveIntervals *lis,
+ const MachineBlockFrequencyInfo *mbfi,
+ const RegSet &vregs) {
LiveIntervals *LIS = const_cast<LiveIntervals*>(lis);
MachineRegisterInfo *mri = &mf->getRegInfo();
- const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo();
+ const TargetRegisterInfo *tri =
+ mf->getTarget().getSubtargetImpl()->getRegisterInfo();
- std::
auto_ptr<PBQPRAProblem> p(new PBQPRAProblem());
- PBQP::Graph &g = p->getGraph();
+ std::
unique_ptr<PBQPRAProblem> p(new PBQPRAProblem());
+ PBQPRAGraph &g = p->getGraph();
RegSet pregs;
// Collect the set of preg intervals, record that they're used in the MF.
mri->setPhysRegUsed(Reg);
}
- BitVector reservedRegs = tri->getReservedRegs(*mf);
-
// Iterate over vregs.
for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end();
vregItr != vregEnd; ++vregItr) {
LiveInterval *vregLI = &LIS->getInterval(vreg);
// Record any overlaps with regmask operands.
- BitVector regMaskOverlaps(tri->getNumRegs());
+ BitVector regMaskOverlaps;
LIS->checkRegMaskInterference(*vregLI, regMaskOverlaps);
// Compute an initial allowed set for the current vreg.
typedef std::vector<unsigned> VRAllowed;
VRAllowed vrAllowed;
- ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(*mf);
+ ArrayRef<MCPhysReg> rawOrder = trc->getRawAllocationOrder(*mf);
for (unsigned i = 0; i != rawOrder.size(); ++i) {
unsigned preg = rawOrder[i];
- if (reservedRegs.test(preg))
+ if (mri->isReserved(preg))
continue;
// vregLI crosses a regmask operand that clobbers preg.
- if (!regMaskOverlaps.empty() && regMaskOverlaps.test(preg))
+ if (!regMaskOverlaps.empty() && !regMaskOverlaps.test(preg))
continue;
// vregLI overlaps fixed regunit interference.
vrAllowed.push_back(preg);
}
- // Construct the node.
- PBQP::Graph::NodeItr node =
- g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0));
-
- // Record the mapping and allowed set in the problem.
- p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end());
+ PBQP::Vector nodeCosts(vrAllowed.size() + 1, 0);
PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ?
vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min();
- addSpillCosts(g.getNodeCosts(node), spillCost);
+ addSpillCosts(nodeCosts, spillCost);
+
+ // Construct the node.
+ PBQPRAGraph::NodeId nId = g.addNode(std::move(nodeCosts));
+
+ // Record the mapping and allowed set in the problem.
+ p->recordVReg(vreg, nId, vrAllowed.begin(), vrAllowed.end());
+
}
for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end();
const LiveInterval &l1 = lis->getInterval(vr1);
const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1);
- for (RegSet::const_iterator vr2Itr = llvm::next(vr1Itr);
- vr2Itr != vrEnd; ++vr2Itr) {
+ for (RegSet::const_iterator vr2Itr = std::next(vr1Itr); vr2Itr != vrEnd;
+ ++vr2Itr) {
unsigned vr2 = *vr2Itr;
const LiveInterval &l2 = lis->getInterval(vr2);
const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2);
assert(!l2.empty() && "Empty interval in vreg set?");
if (l1.overlaps(l2)) {
- PBQP::Graph::EdgeItr edge =
- g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2),
- PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0));
+ PBQP::Matrix edgeCosts(vr1Allowed.size()+1, vr2Allowed.size()+1, 0);
+ addInterferenceCosts(edgeCosts, vr1Allowed, vr2Allowed, tri);
- addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri);
+ g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2),
+ std::move(edgeCosts));
}
}
}
- return p;
+ return p.release();
}
void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec,
}
}
-std::auto_ptr<PBQPRAProblem> PBQPBuilderWithCoalescing::build(
- MachineFunction *mf,
+PBQPRAProblem *PBQPBuilderWithCoalescing::build(MachineFunction *mf,
const LiveIntervals *lis,
- const MachineLoopInfo *loopInfo,
+ const MachineBlockFrequencyInfo *mbfi,
const RegSet &vregs) {
- std::auto_ptr<PBQPRAProblem> p = PBQPBuilder::build(mf, lis, loopInfo, vregs);
- PBQP::Graph &g = p->getGraph();
+ std::unique_ptr<PBQPRAProblem> p(PBQPBuilder::build(mf, lis, mbfi, vregs));
+ PBQPRAGraph &g = p->getGraph();
const TargetMachine &tm = mf->getTarget();
- CoalescerPair cp(*tm.getRegisterInfo());
+ CoalescerPair cp(*tm.getSubtargetImpl()->getRegisterInfo());
// Scan the machine function and add a coalescing cost whenever CoalescerPair
// gives the Ok.
- for (MachineFunction::const_iterator mbbItr = mf->begin(),
- mbbEnd = mf->end();
- mbbItr != mbbEnd; ++mbbItr) {
- const MachineBasicBlock *mbb = &*mbbItr;
-
- for (MachineBasicBlock::const_iterator miItr = mbb->begin(),
- miEnd = mbb->end();
- miItr != miEnd; ++miItr) {
- const MachineInstr *mi = &*miItr;
-
- if (!cp.setRegisters(mi)) {
+ for (const auto &mbb : *mf) {
+ for (const auto &mi : mbb) {
+ if (!cp.setRegisters(&mi)) {
continue; // Not coalescable.
}
// value plucked randomly out of the air.
PBQP::PBQPNum cBenefit =
- copyFactor * LiveIntervals::getSpillWeight(false, true,
- loopInfo->getLoopDepth(mbb));
+ copyFactor * LiveIntervals::getSpillWeight(false, true, mbfi, &mi);
if (cp.isPhys()) {
- if (!lis->isAllocatable(dst)) {
+ if (!mf->getRegInfo().isAllocatable(dst)) {
continue;
}
}
if (pregOpt < allowed.size()) {
++pregOpt; // +1 to account for spill option.
- PBQP::Graph::NodeItr node = p->getNodeForVReg(src);
- addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit);
+ PBQPRAGraph::NodeId node = p->getNodeForVReg(src);
+ llvm::dbgs() << "Reading node costs for node " << node << "\n";
+ llvm::dbgs() << "Source node: " << &g.getNodeCosts(node) << "\n";
+ PBQP::Vector newCosts(g.getNodeCosts(node));
+ addPhysRegCoalesce(newCosts, pregOpt, cBenefit);
+ g.setNodeCosts(node, newCosts);
}
} else {
const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst);
const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src);
- PBQP::Graph::NodeItr node1 = p->getNodeForVReg(dst);
- PBQP::Graph::NodeItr node2 = p->getNodeForVReg(src);
- PBQP::Graph::EdgeItr edge = g.findEdge(node1, node2);
- if (edge == g.edgesEnd()) {
- edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1,
- allowed2->size() + 1,
- 0));
+ PBQPRAGraph::NodeId node1 = p->getNodeForVReg(dst);
+ PBQPRAGraph::NodeId node2 = p->getNodeForVReg(src);
+ PBQPRAGraph::EdgeId edge = g.findEdge(node1, node2);
+ if (edge == g.invalidEdgeId()) {
+ PBQP::Matrix costs(allowed1->size() + 1, allowed2->size() + 1, 0);
+ addVirtRegCoalesce(costs, *allowed1, *allowed2, cBenefit);
+ g.addEdge(node1, node2, costs);
} else {
- if (g.getEdgeNode1(edge) == node2) {
+ if (g.getEdgeNode1Id(edge) == node2) {
std::swap(node1, node2);
std::swap(allowed1, allowed2);
}
+ PBQP::Matrix costs(g.getEdgeCosts(edge));
+ addVirtRegCoalesce(costs, *allowed1, *allowed2, cBenefit);
+ g.setEdgeCosts(edge, costs);
}
-
- addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2,
- cBenefit);
}
}
}
- return p;
+ return p.release();
}
void PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec,
//au.addRequiredID(SplitCriticalEdgesID);
if (customPassID)
au.addRequiredID(*customPassID);
- au.addRequired<CalculateSpillWeights>();
au.addRequired<LiveStacks>();
au.addPreserved<LiveStacks>();
- au.addRequired<MachineDominatorTree>();
- au.addPreserved<MachineDominatorTree>();
+ au.addRequired<MachineBlockFrequencyInfo>();
+ au.addPreserved<MachineBlockFrequencyInfo>();
au.addRequired<MachineLoopInfo>();
au.addPreserved<MachineLoopInfo>();
+ au.addRequired<MachineDominatorTree>();
+ au.addPreserved<MachineDominatorTree>();
au.addRequired<VirtRegMap>();
au.addPreserved<VirtRegMap>();
MachineFunctionPass::getAnalysisUsage(au);
// Clear the existing allocation.
vrm->clearAllVirt();
- const PBQP::Graph &g = problem.getGraph();
+ const PBQPRAGraph &g = problem.getGraph();
// Iterate over the nodes mapping the PBQP solution to a register
// assignment.
- for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(),
- nodeEnd = g.nodesEnd();
- node != nodeEnd; ++node) {
- unsigned vreg = problem.getVRegForNode(node);
- unsigned alloc = solution.getSelection(node);
+ for (auto NId : g.nodeIds()) {
+ unsigned vreg = problem.getVRegForNode(NId);
+ unsigned alloc = solution.getSelection(NId);
if (problem.isPRegOption(vreg, alloc)) {
unsigned preg = problem.getPRegForOption(vreg, alloc);
vrm->assignVirt2Phys(vreg, preg);
} else if (problem.isSpillOption(vreg, alloc)) {
vregsToAlloc.erase(vreg);
- SmallVector<LiveInterval*, 8> newSpills;
+ SmallVector<unsigned, 8> newSpills;
LiveRangeEdit LRE(&lis->getInterval(vreg), newSpills, *mf, *lis, vrm);
spiller->spill(LRE);
// allocate.
for (LiveRangeEdit::iterator itr = LRE.begin(), end = LRE.end();
itr != end; ++itr) {
- assert(!(*itr)->empty() && "Empty spill range.");
- DEBUG(dbgs() << PrintReg((*itr)->reg, tri) << " ");
- vregsToAlloc.insert((*itr)->reg);
+ LiveInterval &li = lis->getInterval(*itr);
+ assert(!li.empty() && "Empty spill range.");
+ DEBUG(dbgs() << PrintReg(li.reg, tri) << " ");
+ vregsToAlloc.insert(li.reg);
}
DEBUG(dbgs() << ")\n");
itr != end; ++itr) {
LiveInterval *li = &lis->getInterval(*itr);
- unsigned physReg = vrm->getRegAllocPref(li->reg);
+ unsigned physReg = mri->getSimpleHint(li->reg);
if (physReg == 0) {
const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
mf = &MF;
tm = &mf->getTarget();
- tri = tm->getRegisterInfo();
- tii = tm->getInstrInfo();
+ tri = tm->getSubtargetImpl()->getRegisterInfo();
+ tii = tm->getSubtargetImpl()->getInstrInfo();
mri = &mf->getRegInfo();
lis = &getAnalysis<LiveIntervals>();
lss = &getAnalysis<LiveStacks>();
- loopInfo = &getAnalysis<MachineLoopInfo>();
+ mbfi = &getAnalysis<MachineBlockFrequencyInfo>();
+
+ calculateSpillWeightsAndHints(*lis, MF, getAnalysis<MachineLoopInfo>(),
+ *mbfi);
vrm = &getAnalysis<VirtRegMap>();
spiller.reset(createInlineSpiller(*this, MF, *vrm));
while (!pbqpAllocComplete) {
DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n");
- std::auto_ptr<PBQPRAProblem> problem =
- builder->build(mf, lis, loopInfo, vregsToAlloc);
+ std::unique_ptr<PBQPRAProblem> problem(
+ builder->build(mf, lis, mbfi, vregsToAlloc));
#ifndef NDEBUG
if (pbqpDumpGraphs) {
rs << round;
std::string graphFileName(fqn + "." + rs.str() + ".pbqpgraph");
std::string tmp;
- raw_fd_ostream os(graphFileName.c_str(), tmp);
+ raw_fd_ostream os(graphFileName.c_str(), tmp, sys::fs::F_Text);
DEBUG(dbgs() << "Dumping graph for round " << round << " to \""
<< graphFileName << "\"\n");
problem->getGraph().dump(os);
#endif
PBQP::Solution solution =
- PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(
- problem->getGraph());
+ PBQP::RegAlloc::solve(problem->getGraph());
pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution);
return true;
}
-FunctionPass* llvm::createPBQPRegisterAllocator(
-
std::auto_ptr<PBQPBuilder> builder,
- char *customPassID) {
- return new RegAllocPBQP(builder, customPassID);
+FunctionPass *
+
llvm::createPBQPRegisterAllocator(std::unique_ptr<PBQPBuilder> builder,
+ char *customPassID) {
+ return new RegAllocPBQP(std::move(builder), customPassID);
}
FunctionPass* llvm::createDefaultPBQPRegisterAllocator() {
- if (pbqpCoalescing) {
- return createPBQPRegisterAllocator(
- std::auto_ptr<PBQPBuilder>(new PBQPBuilderWithCoalescing()));
- } // else
- return createPBQPRegisterAllocator(
- std::auto_ptr<PBQPBuilder>(new PBQPBuilder()));
+ std::unique_ptr<PBQPBuilder> Builder;
+ if (pbqpCoalescing)
+ Builder = llvm::make_unique<PBQPBuilderWithCoalescing>();
+ else
+ Builder = llvm::make_unique<PBQPBuilder>();
+ return createPBQPRegisterAllocator(std::move(Builder));
}
#undef DEBUG_TYPE
projects / oota-llvm.git / blobdiff