#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"
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,
if (NRegs < MRegs)
return D.count(IKey(NRegs, MRegs)) > 0;
- else
- return D.count(IKey(MRegs, NRegs)) > 0;
+
+ return D.count(IKey(MRegs, NRegs)) > 0;
}
void setDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
// 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;
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.
if (!createInterferenceEdge(G, NId, MId, C))
setDisjointAllowedRegs(G, NId, MId, D);
+ else
+ EC.insert(EK);
}
// Finally, add Cur to the Active set.
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>();
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);
return true;
}
-namespace {
-// A helper class for printing node and register info in a consistent way
-class PrintNodeInfo {
-public:
- typedef PBQP::RegAlloc::PBQPRAGraph Graph;
- typedef PBQP::RegAlloc::PBQPRAGraph::NodeId NodeId;
-
- PrintNodeInfo(NodeId NId, const Graph &G) : G(G), NId(NId) {}
-
- void print(raw_ostream &OS) const {
+/// 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) << ')';
- }
-
-private:
- const Graph &G;
- NodeId NId;
-};
-
-inline raw_ostream &operator<<(raw_ostream &OS, const PrintNodeInfo &PR) {
- PR.print(OS);
- return OS;
+ });
}
-} // anonymous namespace
void PBQP::RegAlloc::PBQPRAGraph::dump(raw_ostream &OS) const {
for (auto NId : nodeIds()) {