47#define DEBUG_TYPE "stack-slot-coloring"
52 cl::desc(
"Suppress slot sharing during stack coloring"));
56STATISTIC(NumEliminated,
"Number of stack slots eliminated due to coloring");
57STATISTIC(NumDead,
"Number of trivially dead stack accesses eliminated");
68 std::vector<LiveInterval*> SSIntervals;
96 class ColorAssignmentInfo {
106 ~ColorAssignmentInfo() {
108 LIU->~LiveIntervalUnion();
116 return SingleLI ? SingleLI->
overlaps(*LI) :
false;
123 LIU->
unify(*LI, *LI);
124 }
else if (SingleLI) {
126 LIU->
unify(*SingleLI, *SingleLI);
127 LIU->
unify(*LI, *LI);
160 void InitializeSlots();
171char StackSlotColoring::ID = 0;
176 "Stack Slot Coloring",
false,
false)
189 return LHS->weight() >
RHS->weight();
206 int FI = MO.getIndex();
209 if (!
LS->hasInterval(FI))
212 if (!
MI.isDebugInstr())
217 EE =
MI.memoperands_end();
218 MMOI != EE; ++MMOI) {
221 dyn_cast_or_null<FixedStackPseudoSourceValue>(
223 int FI = FSV->getFrameIndex();
234void StackSlotColoring::InitializeSlots() {
241 OrigAlignments.
resize(LastFI);
243 AllColors[0].
resize(LastFI);
244 UsedColors[0].
resize(LastFI);
245 Assignments.
resize(LastFI);
247 using Pair = std::iterator_traits<LiveStacks::iterator>::value_type;
251 Intervals.
reserve(
LS->getNumIntervals());
255 [](Pair *LHS, Pair *RHS) {
return LHS->first <
RHS->first; });
259 for (
auto *
I : Intervals) {
266 SSIntervals.push_back(&li);
272 AllColors.
resize(StackID + 1);
273 UsedColors.
resize(StackID + 1);
274 AllColors[StackID].
resize(LastFI);
275 UsedColors[StackID].
resize(LastFI);
278 AllColors[StackID].set(FI);
288 for (
unsigned I = 0,
E = AllColors.
size();
I !=
E; ++
I)
289 NextColors[
I] = AllColors[
I].find_first();
302 Color = UsedColors[StackID].find_first();
303 while (Color != -1) {
304 if (!Assignments[Color].overlaps(li)) {
309 Color = UsedColors[StackID].find_next(Color);
314 LLVM_DEBUG(
dbgs() <<
"cannot share FIs with different stack IDs\n");
321 assert(NextColors[StackID] != -1 &&
"No more spill slots?");
322 Color = NextColors[StackID];
323 UsedColors[StackID].set(Color);
324 NextColors[StackID] = AllColors[StackID].find_next(NextColors[StackID]);
330 Assignments[Color].add(li, LIUAlloc);
331 LLVM_DEBUG(
dbgs() <<
"Assigning fi#" << FI <<
" to fi#" << Color <<
"\n");
336 Align Alignment = OrigAlignments[FI];
339 int64_t
Size = OrigSizes[FI];
355 bool Changed =
false;
358 int NewSS = ColorSlot(li);
359 assert(NewSS >= 0 &&
"Stack coloring failed?");
361 RevMap[NewSS].push_back(SS);
362 SlotWeights[NewSS] += li->
weight();
363 UsedColors.set(NewSS);
364 Changed |= (
SS != NewSS);
385 for (
unsigned SS = 0, SE = SSRefs.
size(); SS != SE; ++SS) {
387 if (NewFI == -1 || (NewFI == (
int)SS))
392 for (
unsigned i = 0, e = RefMMOs.
size(); i != e; ++i)
393 RefMMOs[i]->setValue(NewSV);
400 RemoveDeadStores(&
MBB);
404 for (
int StackID = 0,
E = AllColors.
size(); StackID !=
E; ++StackID) {
405 int NextColor = NextColors[StackID];
406 while (NextColor != -1) {
407 LLVM_DEBUG(
dbgs() <<
"Removing unused stack object fi#" << NextColor <<
"\n");
409 NextColor = AllColors[StackID].find_next(NextColor);
425 int OldFI = MO.getIndex();
429 if (NewFI == -1 || NewFI == OldFI)
447 bool changed =
false;
455 int FirstSS, SecondSS;
456 if (
TII->isStackSlotCopy(*
I, FirstSS, SecondSS) && FirstSS == SecondSS &&
467 unsigned LoadReg = 0;
468 unsigned StoreReg = 0;
469 unsigned LoadSize = 0;
470 unsigned StoreSize = 0;
474 while ((NextMI !=
E) && NextMI->isDebugInstr()) {
478 if (NextMI ==
E)
continue;
481 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1 ||
482 LoadSize != StoreSize)
488 if (NextMI->findRegisterUseOperandIdx(LoadReg,
true,
nullptr) != -1) {
498 MI->eraseFromParent();
505 dbgs() <<
"********** Stack Slot Coloring **********\n"
506 <<
"********** Function: " << MF.
getName() <<
'\n';
514 LS = &getAnalysis<LiveStacks>();
515 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
517 bool Changed =
false;
519 unsigned NumSlots =
LS->getNumIntervals();
531 ScanForSpillSlotRefs(MF);
533 Changed = ColorSlots(MF);
535 for (
int &Next : NextColors)
539 for (
unsigned i = 0, e = SSRefs.
size(); i != e; ++i)
542 OrigAlignments.
clear();
This file implements the BitVector class.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const HexagonInstrInfo * TII
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
static cl::opt< bool > DisableSharing("no-stack-slot-sharing", cl::init(false), cl::Hidden, cl::desc("Suppress slot sharing during stack coloring"))
static cl::opt< int > DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden)
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Represent the analysis usage information of a pass.
AnalysisUsage & addPreservedID(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:
A specialized PseudoSourceValue for holding FixedStack values, which must include a frame index.
unsigned isStoreToStackSlot(const MachineInstr &MI, int &FrameIndex) const override
If the specified machine instruction is a direct store to a stack slot, return the virtual or physica...
unsigned isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const override
TargetInstrInfo overrides.
Query interferences between a single live virtual register and a live interval union.
Union of live intervals that are strong candidates for coalescing into a single register (either phys...
void unify(const LiveInterval &VirtReg, const LiveRange &Range)
LiveSegments::Allocator Allocator
LiveInterval - This class represents the liveness of a register, or stack slot.
void incrementWeight(float Inc)
void setWeight(float Value)
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI)
Calculate the spill weight to assign to a single instruction.
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
void setObjectSize(int ObjectIdx, int64_t Size)
Change the size of the specified stack object.
Align getObjectAlign(int ObjectIdx) const
Return the alignment of the specified stack object.
int64_t getObjectSize(int ObjectIdx) const
Return the size of the specified object.
void RemoveStackObject(int ObjectIdx)
Remove or mark dead a statically sized stack object.
int getObjectIndexEnd() const
Return one past the maximum frame object index.
uint8_t getStackID(int ObjectIdx) const
void setObjectAlignment(int ObjectIdx, Align Alignment)
setObjectAlignment - Change the alignment of the specified stack object.
bool isDeadObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a dead object.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
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...
PseudoSourceValueManager & getPSVManager() const
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.
bool exposesReturnsTwice() const
exposesReturnsTwice - Returns true if the function calls setjmp or any other similar functions with a...
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
A description of a memory reference used in the backend.
const PseudoSourceValue * getPseudoValue() const
MachineOperand class - Representation of each machine instruction operand.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
const PseudoSourceValue * getFixedStack(int FI)
Return a pseudo source value referencing a fixed stack frame entry, e.g., a spill slot.
Special value supplied for machine level alias analysis.
static int stackSlot2Index(Register Reg)
Compute the frame index from a register value representing a stack slot.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
virtual const TargetInstrInfo * getInstrInfo() const
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
void stable_sort(R &&Range)
void initializeStackSlotColoringPass(PassRegistry &)
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
char & StackSlotColoringID
StackSlotColoring - This pass performs stack slot coloring.
bool operator()(LiveInterval *LHS, LiveInterval *RHS) const
This struct is a compact representation of a valid (non-zero power of two) alignment.
This struct contains the mappings from the slot numbers to unnamed metadata nodes,...