64#include "llvm/Config/llvm-config.h"
85#include <system_error>
92#define DEBUG_TYPE "regalloc"
100 cl::desc(
"Attempt coalescing during PBQP register allocation."),
106 cl::desc(
"Dump graphs for each function/round in the compilation unit."),
121 RegAllocPBQP(
char *cPassID =
nullptr)
140 MachineFunctionProperties::Property::NoPHIs);
145 MachineFunctionProperties::Property::IsSSA);
149 using RegSet = std::set<Register>;
153 RegSet VRegsToAlloc, EmptyIntervalVRegs;
187char RegAllocPBQP::ID = 0;
199 for (
auto NId :
G.nodeIds()) {
202 if (SpillCost == 0.0)
203 SpillCost = std::numeric_limits<PBQP::PBQPNum>::min();
205 SpillCost += MinSpillCost;
208 G.setNodeCosts(NId, std::move(NodeCosts));
217 using IKey = std::pair<AllowedRegVecPtr, AllowedRegVecPtr>;
220 using IEdgeKey = std::pair<PBQP::GraphBase::NodeId, PBQP::GraphBase::NodeId>;
225 const DisjointAllowedRegsCache &
D)
const {
226 const auto *NRegs = &
G.getNodeMetadata(NId).getAllowedRegs();
227 const auto *MRegs = &
G.getNodeMetadata(MId).getAllowedRegs();
233 return D.contains(IKey(NRegs, MRegs));
235 return D.contains(IKey(MRegs, NRegs));
240 DisjointAllowedRegsCache &
D) {
241 const auto *NRegs = &
G.getNodeMetadata(NId).getAllowedRegs();
242 const auto *MRegs = &
G.getNodeMetadata(MId).getAllowedRegs();
244 assert(NRegs != MRegs &&
"AllowedRegs can not be disjoint with itself");
247 D.insert(IKey(NRegs, MRegs));
249 D.insert(IKey(MRegs, NRegs));
257 std::tuple<LiveInterval*, size_t, PBQP::GraphBase::NodeId>;
259 static SlotIndex getStartPoint(
const IntervalInfo &
I) {
260 return std::get<0>(
I)->segments[std::get<1>(
I)].start;
263 static SlotIndex getEndPoint(
const IntervalInfo &
I) {
264 return std::get<0>(
I)->segments[std::get<1>(
I)].end;
268 return std::get<2>(
I);
271 static bool lowestStartPoint(
const IntervalInfo &I1,
272 const IntervalInfo &I2) {
275 return getStartPoint(I1) > getStartPoint(I2);
278 static bool lowestEndPoint(
const IntervalInfo &I1,
279 const IntervalInfo &I2) {
292 return std::get<0>(I1)->reg() < std::get<0>(I2)->reg();
295 static bool isAtLastSegment(
const IntervalInfo &
I) {
296 return std::get<1>(
I) == std::get<0>(
I)->size() - 1;
299 static IntervalInfo nextSegment(
const IntervalInfo &
I) {
300 return std::make_tuple(std::get<0>(
I), std::get<1>(
I) + 1, std::get<2>(
I));
322 DisjointAllowedRegsCache
D;
324 using IntervalSet = std::set<IntervalInfo,
decltype(&lowestEndPoint)>;
325 using IntervalQueue =
326 std::priority_queue<IntervalInfo, std::vector<IntervalInfo>,
327 decltype(&lowestStartPoint)>;
328 IntervalSet Active(lowestEndPoint);
329 IntervalQueue Inactive(lowestStartPoint);
332 for (
auto NId :
G.nodeIds()) {
333 Register VReg =
G.getNodeMetadata(NId).getVReg();
335 assert(!LI.
empty() &&
"PBQP graph contains node for empty interval");
336 Inactive.push(std::make_tuple(&LI, 0, NId));
339 while (!Inactive.empty()) {
342 IntervalInfo Cur = Inactive.top();
345 IntervalSet::iterator RetireItr = Active.begin();
346 while (RetireItr != Active.end() &&
347 (getEndPoint(*RetireItr) <= getStartPoint(Cur))) {
350 if (!isAtLastSegment(*RetireItr))
351 Inactive.push(nextSegment(*RetireItr));
355 Active.erase(Active.begin(), RetireItr);
359 Cur = Inactive.top();
365 for (
const auto &
A : Active) {
370 if (haveDisjointAllowedRegs(
G, NId, MId,
D))
374 IEdgeKey EK(std::min(NId, MId), std::max(NId, MId));
379 if (!createInterferenceEdge(
G, NId, MId,
C))
380 setDisjointAllowedRegs(
G, NId, MId,
D);
400 *
G.getMetadata().MF.getSubtarget().getRegisterInfo();
401 const auto &NRegs =
G.getNodeMetadata(NId).getAllowedRegs();
402 const auto &MRegs =
G.getNodeMetadata(MId).getAllowedRegs();
405 IKey
K(&NRegs, &MRegs);
408 G.addEdgeBypassingCostAllocator(NId, MId,
I->second);
413 bool NodesInterfere =
false;
414 for (
unsigned I = 0;
I != NRegs.size(); ++
I) {
416 for (
unsigned J = 0; J != MRegs.size(); ++J) {
418 if (
TRI.regsOverlap(PRegN, PRegM)) {
419 M[
I + 1][J + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
420 NodesInterfere =
true;
429 C[
K] =
G.getEdgeCostsPtr(EId);
444 for (
const auto &
MBB : MF) {
445 for (
const auto &
MI :
MBB) {
447 if (!
CP.setRegisters(&
MI) ||
CP.getSrcReg() ==
CP.getDstReg())
456 if (!MF.getRegInfo().isAllocatable(DstReg))
461 const PBQPRAGraph::NodeMetadata::AllowedRegVector &
Allowed =
462 G.getNodeMetadata(NId).getAllowedRegs();
464 unsigned PRegOpt = 0;
465 while (PRegOpt <
Allowed.size() && Allowed[PRegOpt].id() != DstReg)
468 if (PRegOpt <
Allowed.size()) {
470 NewCosts[PRegOpt + 1] -= CBenefit;
471 G.setNodeCosts(NId, std::move(NewCosts));
476 const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed1 =
477 &
G.getNodeMetadata(N1Id).getAllowedRegs();
478 const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed2 =
479 &
G.getNodeMetadata(N2Id).getAllowedRegs();
482 if (EId ==
G.invalidEdgeId()) {
484 Allowed2->size() + 1, 0);
485 addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
486 G.addEdge(N1Id, N2Id, std::move(Costs));
488 if (
G.getEdgeNode1Id(EId) == N2Id) {
493 addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
494 G.updateEdgeCosts(EId, std::move(Costs));
502 void addVirtRegCoalesce(
504 const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed1,
505 const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed2,
507 assert(CostMat.getRows() == Allowed1.size() + 1 &&
"Size mismatch.");
508 assert(CostMat.getCols() == Allowed2.size() + 1 &&
"Size mismatch.");
509 for (
unsigned I = 0;
I != Allowed1.size(); ++
I) {
511 for (
unsigned J = 0; J != Allowed2.size(); ++J) {
514 CostMat[
I + 1][J + 1] -= Benefit;
522 float normalize(
float UseDefFreq,
unsigned Size,
unsigned NumInstr)
override {
539void PBQPRAConstraint::anchor() {}
541void PBQPRAConstraintList::anchor() {}
543void RegAllocPBQP::getAnalysisUsage(
AnalysisUsage &au)
const {
572 for (
unsigned I = 0, E =
MRI.getNumVirtRegs();
I != E; ++
I) {
574 if (
MRI.reg_nodbg_empty(Reg))
576 VRegsToAlloc.insert(Reg);
584 for (
unsigned i = 0; CSR[i] != 0; ++i)
585 if (
TRI.regsOverlap(Reg, CSR[i]))
597 *
G.getMetadata().MF.getSubtarget().getRegisterInfo();
599 std::vector<Register> Worklist(VRegsToAlloc.begin(), VRegsToAlloc.end());
601 std::map<Register, std::vector<MCRegister>> VRegAllowedMap;
603 while (!Worklist.empty()) {
611 if (VRegLI.
empty()) {
612 EmptyIntervalVRegs.insert(VRegLI.
reg());
613 VRegsToAlloc.erase(VRegLI.
reg());
624 std::vector<MCRegister> VRegAllowed;
628 if (
MRI.isReserved(PReg))
632 if (!RegMaskOverlaps.
empty() && !RegMaskOverlaps.
test(PReg))
636 bool Interference =
false;
647 VRegAllowed.push_back(PReg);
652 if (VRegAllowed.empty()) {
654 spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
659 VRegAllowedMap[VReg.
id()] = std::move(VRegAllowed);
662 for (
auto &KV : VRegAllowedMap) {
663 auto VReg = KV.first;
667 EmptyIntervalVRegs.insert(VReg);
668 VRegsToAlloc.erase(VReg);
672 auto &VRegAllowed = KV.second;
678 for (
unsigned i = 0; i != VRegAllowed.size(); ++i)
680 NodeCosts[1 + i] += 1.0;
683 G.getNodeMetadata(NId).setVReg(VReg);
684 G.getNodeMetadata(NId).setAllowedRegs(
685 G.getMetadata().getAllowedRegs(std::move(VRegAllowed)));
686 G.getMetadata().setNodeIdForVReg(VReg, NId);
690void RegAllocPBQP::spillVReg(
Register VReg,
694 VRegsToAlloc.erase(VReg);
696 nullptr, &DeadRemats);
697 VRegSpiller.
spill(LRE);
702 << LRE.getParent().weight() <<
", New vregs: ");
710 VRegsToAlloc.insert(LI.
reg());
716bool RegAllocPBQP::mapPBQPToRegAlloc(
const PBQPRAGraph &
G,
726 bool AnotherRoundNeeded =
false;
733 for (
auto NId :
G.nodeIds()) {
734 Register VReg =
G.getNodeMetadata(NId).getVReg();
738 MCRegister PReg =
G.getNodeMetadata(NId).getAllowedRegs()[AllocOpt - 1];
740 <<
TRI.getName(PReg) <<
"\n");
741 assert(PReg != 0 &&
"Invalid preg selected.");
747 spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
748 AnotherRoundNeeded |= !NewVRegs.
empty();
752 return !AnotherRoundNeeded;
761 for (
const Register &R : EmptyIntervalVRegs) {
769 for (
MCRegister CandidateReg : RawPRegOrder) {
776 "No un-reserved physical registers in this register class");
786 for (
auto *DeadInst : DeadRemats) {
788 DeadInst->eraseFromParent();
794 LiveIntervals &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
796 getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
800 PBQPVirtRegAuxInfo VRAI(
801 MF, LIS, VRM, getAnalysis<MachineLoopInfoWrapperPass>().getLI(), MBFI);
802 VRAI.calculateSpillWeightsAndHints();
809 MF, LIS, VRM, getAnalysis<MachineLoopInfoWrapperPass>().getLI(), MBFI);
810 std::unique_ptr<Spiller> VRegSpiller(
827 findVRegIntervalsToAlloc(MF, LIS);
831 std::string FullyQualifiedName =
832 F.getParent()->getModuleIdentifier() +
"." +
F.getName().str();
836 if (!VRegsToAlloc.empty()) {
838 std::unique_ptr<PBQPRAConstraintList> ConstraintsRoot =
839 std::make_unique<PBQPRAConstraintList>();
840 ConstraintsRoot->addConstraint(std::make_unique<SpillCosts>());
841 ConstraintsRoot->addConstraint(std::make_unique<Interference>());
843 ConstraintsRoot->addConstraint(std::make_unique<Coalescing>());
846 bool PBQPAllocComplete =
false;
849 while (!PBQPAllocComplete) {
854 initializeGraph(
G, VRM, *VRegSpiller);
855 ConstraintsRoot->apply(
G);
859 std::ostringstream RS;
861 std::string GraphFileName = FullyQualifiedName +
"." + RS.str() +
865 LLVM_DEBUG(
dbgs() <<
"Dumping graph for round " << Round <<
" to \""
866 << GraphFileName <<
"\"\n");
872 PBQPAllocComplete = mapPBQPToRegAlloc(
G, Solution, VRM, *VRegSpiller);
878 finalizeAlloc(MF, LIS, VRM);
879 postOptimization(*VRegSpiller, LIS);
880 VRegsToAlloc.clear();
881 EmptyIntervalVRegs.clear();
894 Register VReg =
G.getNodeMetadata(NId).getVReg();
895 const char *RegClassName =
TRI->getRegClassName(
MRI.getRegClass(VReg));
896 OS << NId <<
" (" << RegClassName <<
':' <<
printReg(VReg,
TRI) <<
')';
900#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
904 assert(Costs.getLength() != 0 &&
"Empty vector in graph.");
912 assert(N1Id != N2Id &&
"PBQP graphs should not have self-edges.");
914 assert(M.getRows() != 0 &&
"No rows in matrix.");
915 assert(M.getCols() != 0 &&
"No cols in matrix.");
929 for (
auto NId : nodeIds()) {
930 OS <<
" node" << NId <<
" [ label=\""
932 << getNodeCosts(NId) <<
"\" ]\n";
935 OS <<
" edge [ len=" << nodeIds().size() <<
" ]\n";
936 for (
auto EId : edgeIds()) {
937 OS <<
" node" << getEdgeNode1Id(EId)
938 <<
" -- node" << getEdgeNode2Id(EId)
940 const Matrix &EdgeCosts = getEdgeCosts(EId);
941 for (
unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
942 OS << EdgeCosts.getRowAsVector(i) <<
"\\n";
950 return new RegAllocPBQP(customPassID);
unsigned const MachineRegisterInfo * MRI
This file implements the BitVector class.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
unsigned const TargetRegisterInfo * TRI
Module.h This file contains the declarations for the Module class.
static Printable PrintNodeInfo(PBQP::RegAlloc::PBQPRAGraph::NodeId NId, const PBQP::RegAlloc::PBQPRAGraph &G)
Create Printable object for node and register info.
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)
static cl::opt< bool > PBQPCoalescing("pbqp-coalescing", cl::desc("Attempt coalescing during PBQP register allocation."), cl::init(false), cl::Hidden)
static bool isACalleeSavedRegister(MCRegister Reg, const TargetRegisterInfo &TRI, const MachineFunction &MF)
static RegisterRegAlloc RegisterPBQPRepAlloc("pbqp", "PBQP register allocator", createDefaultPBQPRegisterAllocator)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequiredID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool test(unsigned Idx) const
bool empty() const
empty - Tests whether there are no bits in this bitvector.
A helper class for register coalescers.
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
Implements a dense probed hash-table based set.
FunctionPass class - This class is used to implement most global optimizations.
LiveInterval - This class represents the liveness of a register, or stack slot.
bool checkRegMaskInterference(const LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
void RemoveMachineInstrFromMaps(MachineInstr &MI)
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
LiveInterval & getInterval(Register Reg)
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
Wrapper class representing physical registers. Should be passed by value.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
double getBlockFreqRelativeToEntryBlock(const MachineBasicBlock *MBB) const
Compute the frequency of the block, relative to the entry block.
Analysis pass which computes a MachineDominatorTree.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual MachineFunctionProperties getClearedProperties() const
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
void freezeReservedRegs()
freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
const MCPhysReg * getCalleeSavedRegs() const
Returns list of callee saved registers.
Abstract base for classes implementing PBQP register allocation constraints (e.g.
virtual ~PBQPRAConstraint()=0
virtual void apply(PBQPRAGraph &G)=0
typename SolverT::GraphMetadata GraphMetadata
typename SolverT::Matrix Matrix
NodeId getEdgeNode2Id(EdgeId EId) const
Get the second node connected to this edge.
NodeId getEdgeNode1Id(EdgeId EId) const
Get the first node connected to this edge.
const Matrix & getEdgeCosts(EdgeId EId) const
Get an edge's cost matrix.
typename SolverT::Vector Vector
NodeIdSet nodeIds() const
typename SolverT::RawMatrix RawMatrix
typename SolverT::RawVector RawVector
const Vector & getNodeCosts(NodeId NId) const
Get a node's cost vector.
EdgeIdSet edgeIds() const
Holds a vector of the allowed physical regs for a vreg.
void printDot(raw_ostream &OS) const
Print a representation of this graph in DOT format.
void dump() const
Dump this graph to dbgs().
Represents a solution to a PBQP problem.
unsigned getSelection(GraphBase::NodeId nodeId) const
Get a node's selection.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Simple wrapper around std::function<void(raw_ostream&)>.
Wrapper class representing virtual and physical registers.
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
constexpr unsigned id() const
SlotIndex - An opaque wrapper around machine indexes.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
virtual void spill(LiveRangeEdit &LRE)=0
spill - Spill the LRE.getParent() live interval.
virtual void postOptimization()
StringRef - Represent a constant reference to a string, i.e.
ArrayRef< MCPhysReg > getRawAllocationOrder(const MachineFunction &MF) const
Returns the preferred order for allocating registers from this register class in MF.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual std::unique_ptr< PBQPRAConstraint > getCustomPBQPConstraints() const
Return PBQPConstraint(s) for the target.
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.
virtual float normalize(float UseDefFreq, unsigned Size, unsigned NumInstr)
Weight normalization function.
void clearAllVirt()
clears all virtual to physical register mappings
MachineRegisterInfo & getRegInfo() const
void assignVirt2Phys(Register virtReg, MCPhysReg physReg)
creates a mapping for the specified virtual register to the specified physical register
A raw_ostream that writes to a file descriptor.
This class implements an extremely fast bulk output stream that can only output to a stream.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
Solution solve(PBQPRAGraph &G)
unsigned getSpillOptionIdx()
Spill option index.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
@ OF_TextWithCRLF
The file should be opened in text mode and use a carriage linefeed '\r '.
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
void initializeVirtRegMapPass(PassRegistry &)
Spiller * createInlineSpiller(MachineFunctionPass &Pass, MachineFunction &MF, VirtRegMap &VRM, VirtRegAuxInfo &VRAI)
Create and return a spiller that will insert spill code directly instead of deferring though VirtRegM...
void initializeLiveStacksPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
FunctionPass * createDefaultPBQPRegisterAllocator()
PBQPRegisterAllocation Pass - This pass implements the Partitioned Boolean Quadratic Prograaming (PBQ...
void initializeLiveIntervalsWrapperPassPass(PassRegistry &)
FunctionPass * createPBQPRegisterAllocator(char *customPassID=nullptr)
Create a PBQP register allocator instance.
void initializeSlotIndexesWrapperPassPass(PassRegistry &)
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.