#include "llvm/IR/Module.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Printable.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS);
/// \brief Constructs an initial graph.
- void initializeGraph(PBQPRAGraph &G);
+ void initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, Spiller &VRegSpiller);
+
+ /// \brief Spill the given VReg.
+ void spillVReg(unsigned VReg, SmallVectorImpl<unsigned> &NewIntervals,
+ MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM,
+ Spiller &VRegSpiller);
/// \brief Given a solved PBQP problem maps this solution back to a register
/// assignment.
/// @brief Add interference edges between overlapping vregs.
class Interference : public PBQPRAConstraint {
-private:
-
private:
typedef const PBQP::RegAlloc::AllowedRegVector* AllowedRegVecPtr;
- typedef std::pair<AllowedRegVecPtr, AllowedRegVecPtr> IMatrixKey;
- typedef DenseMap<IMatrixKey, PBQPRAGraph::MatrixPtr> IMatrixCache;
+ typedef std::pair<AllowedRegVecPtr, AllowedRegVecPtr> IKey;
+ typedef DenseMap<IKey, PBQPRAGraph::MatrixPtr> IMatrixCache;
+ typedef DenseSet<IKey> DisjointAllowedRegsCache;
+ typedef std::pair<PBQP::GraphBase::NodeId, PBQP::GraphBase::NodeId> IEdgeKey;
+ typedef DenseSet<IEdgeKey> IEdgeCache;
+
+ bool haveDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
+ PBQPRAGraph::NodeId MId,
+ const DisjointAllowedRegsCache &D) const {
+ const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
+ const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();
+
+ if (NRegs == MRegs)
+ return false;
+
+ if (NRegs < MRegs)
+ return D.count(IKey(NRegs, MRegs)) > 0;
+
+ return D.count(IKey(MRegs, NRegs)) > 0;
+ }
+
+ void setDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
+ PBQPRAGraph::NodeId MId,
+ DisjointAllowedRegsCache &D) {
+ const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
+ const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();
+
+ assert(NRegs != MRegs && "AllowedRegs can not be disjoint with itself");
+
+ if (NRegs < MRegs)
+ D.insert(IKey(NRegs, MRegs));
+ else
+ D.insert(IKey(MRegs, NRegs));
+ }
// Holds (Interval, CurrentSegmentID, and NodeId). The first two are required
// for the fast interference graph construction algorithm. The last is there
// and uniquing them.
IMatrixCache C;
+ // Finding an edge is expensive in the worst case (O(max_clique(G))). So
+ // cache locally edges we have already seen.
+ IEdgeCache EC;
+
+ // Cache known disjoint allowed registers pairs
+ DisjointAllowedRegsCache D;
+
typedef std::set<IntervalInfo, decltype(&lowestEndPoint)> IntervalSet;
typedef std::priority_queue<IntervalInfo, std::vector<IntervalInfo>,
decltype(&lowestStartPoint)> IntervalQueue;
for (const auto &A : Active) {
PBQP::GraphBase::NodeId MId = getNodeId(A);
+ // Do not add an edge when the nodes' allowed registers do not
+ // intersect: there is obviously no interference.
+ if (haveDisjointAllowedRegs(G, NId, MId, D))
+ continue;
+
// Check that we haven't already added this edge
- // FIXME: findEdge is expensive in the worst case (O(max_clique(G))).
- // It might be better to replace this with a local bit-matrix.
- if (G.findEdge(NId, MId) != PBQPRAGraph::invalidEdgeId())
+ IEdgeKey EK(std::min(NId, MId), std::max(NId, MId));
+ if (EC.count(EK))
continue;
// This is a new edge - add it to the graph.
- createInterferenceEdge(G, NId, MId, C);
+ if (!createInterferenceEdge(G, NId, MId, C))
+ setDisjointAllowedRegs(G, NId, MId, D);
+ else
+ EC.insert(EK);
}
// Finally, add Cur to the Active set.
private:
- void createInterferenceEdge(PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
- PBQPRAGraph::NodeId MId, IMatrixCache &C) {
+ // Create an Interference edge and add it to the graph, unless it is
+ // a null matrix, meaning the nodes' allowed registers do not have any
+ // interference. This case occurs frequently between integer and floating
+ // point registers for example.
+ // return true iff both nodes interferes.
+ bool createInterferenceEdge(PBQPRAGraph &G,
+ PBQPRAGraph::NodeId NId, PBQPRAGraph::NodeId MId,
+ IMatrixCache &C) {
const TargetRegisterInfo &TRI =
- *G.getMetadata().MF.getTarget().getSubtargetImpl()->getRegisterInfo();
-
+ *G.getMetadata().MF.getSubtarget().getRegisterInfo();
const auto &NRegs = G.getNodeMetadata(NId).getAllowedRegs();
const auto &MRegs = G.getNodeMetadata(MId).getAllowedRegs();
// Try looking the edge costs up in the IMatrixCache first.
- IMatrixKey K(&NRegs, &MRegs);
+ IKey K(&NRegs, &MRegs);
IMatrixCache::iterator I = C.find(K);
if (I != C.end()) {
G.addEdgeBypassingCostAllocator(NId, MId, I->second);
- return;
+ return true;
}
PBQPRAGraph::RawMatrix M(NRegs.size() + 1, MRegs.size() + 1, 0);
+ bool NodesInterfere = false;
for (unsigned I = 0; I != NRegs.size(); ++I) {
unsigned PRegN = NRegs[I];
for (unsigned J = 0; J != MRegs.size(); ++J) {
unsigned PRegM = MRegs[J];
- if (TRI.regsOverlap(PRegN, PRegM))
+ if (TRI.regsOverlap(PRegN, PRegM)) {
M[I + 1][J + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
+ NodesInterfere = true;
+ }
}
}
+ if (!NodesInterfere)
+ return false;
+
PBQPRAGraph::EdgeId EId = G.addEdge(NId, MId, std::move(M));
C[K] = G.getEdgeCostsPtr(EId);
+
+ return true;
}
};
void apply(PBQPRAGraph &G) override {
MachineFunction &MF = G.getMetadata().MF;
MachineBlockFrequencyInfo &MBFI = G.getMetadata().MBFI;
- CoalescerPair CP(*MF.getTarget().getSubtargetImpl()->getRegisterInfo());
+ CoalescerPair CP(*MF.getSubtarget().getRegisterInfo());
// Scan the machine function and add a coalescing cost whenever CoalescerPair
// gives the Ok.
}
PBQPRAGraph::RawMatrix Costs(G.getEdgeCosts(EId));
addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
- G.setEdgeCosts(EId, std::move(Costs));
+ G.updateEdgeCosts(EId, std::move(Costs));
}
}
}
void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const {
au.setPreservesCFG();
- au.addRequired<AliasAnalysis>();
- au.addPreserved<AliasAnalysis>();
+ au.addRequired<AAResultsWrapperPass>();
+ au.addPreserved<AAResultsWrapperPass>();
au.addRequired<SlotIndexes>();
au.addPreserved<SlotIndexes>();
au.addRequired<LiveIntervals>();
}
}
-void RegAllocPBQP::initializeGraph(PBQPRAGraph &G) {
+static bool isACalleeSavedRegister(unsigned reg, const TargetRegisterInfo &TRI,
+ const MachineFunction &MF) {
+ const MCPhysReg *CSR = TRI.getCalleeSavedRegs(&MF);
+ for (unsigned i = 0; CSR[i] != 0; ++i)
+ if (TRI.regsOverlap(reg, CSR[i]))
+ return true;
+ return false;
+}
+
+void RegAllocPBQP::initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM,
+ Spiller &VRegSpiller) {
MachineFunction &MF = G.getMetadata().MF;
LiveIntervals &LIS = G.getMetadata().LIS;
const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
const TargetRegisterInfo &TRI =
- *G.getMetadata().MF.getTarget().getSubtargetImpl()->getRegisterInfo();
+ *G.getMetadata().MF.getSubtarget().getRegisterInfo();
+
+ std::vector<unsigned> Worklist(VRegsToAlloc.begin(), VRegsToAlloc.end());
+
+ while (!Worklist.empty()) {
+ unsigned VReg = Worklist.back();
+ Worklist.pop_back();
- for (auto VReg : VRegsToAlloc) {
const TargetRegisterClass *TRC = MRI.getRegClass(VReg);
LiveInterval &VRegLI = LIS.getInterval(VReg);
VRegAllowed.push_back(PReg);
}
+ // Check for vregs that have no allowed registers. These should be
+ // pre-spilled and the new vregs added to the worklist.
+ if (VRegAllowed.empty()) {
+ SmallVector<unsigned, 8> NewVRegs;
+ spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
+ Worklist.insert(Worklist.end(), NewVRegs.begin(), NewVRegs.end());
+ continue;
+ }
+
PBQPRAGraph::RawVector NodeCosts(VRegAllowed.size() + 1, 0);
+
+ // Tweak cost of callee saved registers, as using then force spilling and
+ // restoring them. This would only happen in the prologue / epilogue though.
+ for (unsigned i = 0; i != VRegAllowed.size(); ++i)
+ if (isACalleeSavedRegister(VRegAllowed[i], TRI, MF))
+ NodeCosts[1 + i] += 1.0;
+
PBQPRAGraph::NodeId NId = G.addNode(std::move(NodeCosts));
G.getNodeMetadata(NId).setVReg(VReg);
G.getNodeMetadata(NId).setAllowedRegs(
}
}
+void RegAllocPBQP::spillVReg(unsigned VReg,
+ SmallVectorImpl<unsigned> &NewIntervals,
+ MachineFunction &MF, LiveIntervals &LIS,
+ VirtRegMap &VRM, Spiller &VRegSpiller) {
+
+ VRegsToAlloc.erase(VReg);
+ LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM);
+ VRegSpiller.spill(LRE);
+
+ const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
+ (void)TRI;
+ DEBUG(dbgs() << "VREG " << PrintReg(VReg, &TRI) << " -> SPILLED (Cost: "
+ << LRE.getParent().weight << ", New vregs: ");
+
+ // Copy any newly inserted live intervals into the list of regs to
+ // allocate.
+ for (LiveRangeEdit::iterator I = LRE.begin(), E = LRE.end();
+ I != E; ++I) {
+ const LiveInterval &LI = LIS.getInterval(*I);
+ assert(!LI.empty() && "Empty spill range.");
+ DEBUG(dbgs() << PrintReg(LI.reg, &TRI) << " ");
+ VRegsToAlloc.insert(LI.reg);
+ }
+
+ DEBUG(dbgs() << ")\n");
+}
+
bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G,
const PBQP::Solution &Solution,
VirtRegMap &VRM,
Spiller &VRegSpiller) {
MachineFunction &MF = G.getMetadata().MF;
LiveIntervals &LIS = G.getMetadata().LIS;
- const TargetRegisterInfo &TRI =
- *MF.getTarget().getSubtargetImpl()->getRegisterInfo();
+ const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
(void)TRI;
// Set to true if we have any spills
assert(PReg != 0 && "Invalid preg selected.");
VRM.assignVirt2Phys(VReg, PReg);
} else {
- VRegsToAlloc.erase(VReg);
- SmallVector<unsigned, 8> NewSpills;
- LiveRangeEdit LRE(&LIS.getInterval(VReg), NewSpills, MF, LIS, &VRM);
- VRegSpiller.spill(LRE);
-
- DEBUG(dbgs() << "VREG " << PrintReg(VReg, &TRI) << " -> SPILLED (Cost: "
- << LRE.getParent().weight << ", New vregs: ");
-
- // Copy any newly inserted live intervals into the list of regs to
- // allocate.
- for (LiveRangeEdit::iterator I = LRE.begin(), E = LRE.end();
- I != E; ++I) {
- LiveInterval &LI = LIS.getInterval(*I);
- assert(!LI.empty() && "Empty spill range.");
- DEBUG(dbgs() << PrintReg(LI.reg, &TRI) << " ");
- VRegsToAlloc.insert(LI.reg);
- }
-
- DEBUG(dbgs() << ")\n");
-
- // We need another round if spill intervals were added.
- AnotherRoundNeeded |= !LRE.empty();
+ // Spill VReg. If this introduces new intervals we'll need another round
+ // of allocation.
+ SmallVector<unsigned, 8> NewVRegs;
+ spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
+ AnotherRoundNeeded |= !NewVRegs.empty();
}
}
MachineBlockFrequencyInfo &MBFI =
getAnalysis<MachineBlockFrequencyInfo>();
- calculateSpillWeightsAndHints(LIS, MF, getAnalysis<MachineLoopInfo>(), MBFI,
- normalizePBQPSpillWeight);
-
VirtRegMap &VRM = getAnalysis<VirtRegMap>();
+ calculateSpillWeightsAndHints(LIS, MF, &VRM, getAnalysis<MachineLoopInfo>(),
+ MBFI, normalizePBQPSpillWeight);
+
std::unique_ptr<Spiller> VRegSpiller(createInlineSpiller(*this, MF, VRM));
MF.getRegInfo().freezeReservedRegs(MF);
// If there are non-empty intervals allocate them using pbqp.
if (!VRegsToAlloc.empty()) {
- const TargetSubtargetInfo &Subtarget = *MF.getTarget().getSubtargetImpl();
+ const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
std::unique_ptr<PBQPRAConstraintList> ConstraintsRoot =
llvm::make_unique<PBQPRAConstraintList>();
ConstraintsRoot->addConstraint(llvm::make_unique<SpillCosts>());
DEBUG(dbgs() << " PBQP Regalloc round " << Round << ":\n");
PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI));
- initializeGraph(G);
+ initializeGraph(G, VRM, *VRegSpiller);
ConstraintsRoot->apply(G);
#ifndef NDEBUG
raw_fd_ostream OS(GraphFileName, EC, sys::fs::F_Text);
DEBUG(dbgs() << "Dumping graph for round " << Round << " to \""
<< GraphFileName << "\"\n");
- G.dumpToStream(OS);
+ G.dump(OS);
}
#endif
return true;
}
+/// Create Printable object for node and register info.
+static Printable PrintNodeInfo(PBQP::RegAlloc::PBQPRAGraph::NodeId NId,
+ const PBQP::RegAlloc::PBQPRAGraph &G) {
+ return Printable([NId, &G](raw_ostream &OS) {
+ const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
+ const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
+ unsigned VReg = G.getNodeMetadata(NId).getVReg();
+ const char *RegClassName = TRI->getRegClassName(MRI.getRegClass(VReg));
+ OS << NId << " (" << RegClassName << ':' << PrintReg(VReg, TRI) << ')';
+ });
+}
+
+void PBQP::RegAlloc::PBQPRAGraph::dump(raw_ostream &OS) const {
+ for (auto NId : nodeIds()) {
+ const Vector &Costs = getNodeCosts(NId);
+ assert(Costs.getLength() != 0 && "Empty vector in graph.");
+ OS << PrintNodeInfo(NId, *this) << ": " << Costs << '\n';
+ }
+ OS << '\n';
+
+ for (auto EId : edgeIds()) {
+ NodeId N1Id = getEdgeNode1Id(EId);
+ NodeId N2Id = getEdgeNode2Id(EId);
+ assert(N1Id != N2Id && "PBQP graphs should not have self-edges.");
+ const Matrix &M = getEdgeCosts(EId);
+ assert(M.getRows() != 0 && "No rows in matrix.");
+ assert(M.getCols() != 0 && "No cols in matrix.");
+ OS << PrintNodeInfo(N1Id, *this) << ' ' << M.getRows() << " rows / ";
+ OS << PrintNodeInfo(N2Id, *this) << ' ' << M.getCols() << " cols:\n";
+ OS << M << '\n';
+ }
+}
+
+void PBQP::RegAlloc::PBQPRAGraph::dump() const { dump(dbgs()); }
+
+void PBQP::RegAlloc::PBQPRAGraph::printDot(raw_ostream &OS) const {
+ OS << "graph {\n";
+ for (auto NId : nodeIds()) {
+ OS << " node" << NId << " [ label=\""
+ << PrintNodeInfo(NId, *this) << "\\n"
+ << getNodeCosts(NId) << "\" ]\n";
+ }
+
+ OS << " edge [ len=" << nodeIds().size() << " ]\n";
+ for (auto EId : edgeIds()) {
+ OS << " node" << getEdgeNode1Id(EId)
+ << " -- node" << getEdgeNode2Id(EId)
+ << " [ label=\"";
+ const Matrix &EdgeCosts = getEdgeCosts(EId);
+ for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
+ OS << EdgeCosts.getRowAsVector(i) << "\\n";
+ }
+ OS << "\" ]\n";
+ }
+ OS << "}\n";
+}
+
FunctionPass *llvm::createPBQPRegisterAllocator(char *customPassID) {
return new RegAllocPBQP(customPassID);
}
projects / oota-llvm.git / blobdiff