Go to the documentation of this file.
46 #define DEBUG_TYPE "stack-slot-coloring"
51 cl::desc(
"Suppress slot sharing during stack coloring"));
55 STATISTIC(NumEliminated,
"Number of stack slots eliminated due to coloring");
56 STATISTIC(NumDead,
"Number of trivially dead stack accesses eliminated");
67 std::vector<LiveInterval*> SSIntervals;
117 void InitializeSlots();
119 bool OverlapWithAssignments(
LiveInterval *li,
int Color)
const;
134 "Stack Slot Coloring",
false,
false)
147 return LHS->weight() >
RHS->weight();
164 int FI = MO.getIndex();
167 if (!
LS->hasInterval(FI))
170 if (!
MI.isDebugInstr())
175 EE =
MI.memoperands_end();
176 MMOI != EE; ++MMOI) {
179 dyn_cast_or_null<FixedStackPseudoSourceValue>(
181 int FI = FSV->getFrameIndex();
183 SSRefs[FI].push_back(MMO);
192 void StackSlotColoring::InitializeSlots() {
199 OrigAlignments.
resize(LastFI);
201 AllColors[0].
resize(LastFI);
202 UsedColors[0].
resize(LastFI);
203 Assignments.
resize(LastFI);
205 using Pair = std::iterator_traits<LiveStacks::iterator>::value_type;
209 Intervals.
reserve(
LS->getNumIntervals());
211 Intervals.push_back(&
I);
213 [](Pair *
LHS, Pair *
RHS) {
return LHS->first <
RHS->first; });
217 for (
auto *
I : Intervals) {
224 SSIntervals.push_back(&li);
230 AllColors.
resize(StackID + 1);
231 UsedColors.
resize(StackID + 1);
232 AllColors[StackID].
resize(LastFI);
233 UsedColors[StackID].
resize(LastFI);
236 AllColors[StackID].set(FI);
243 NextColors.
resize(AllColors.size());
246 for (
unsigned I = 0,
E = AllColors.size();
I !=
E; ++
I)
247 NextColors[
I] = AllColors[
I].find_first();
253 StackSlotColoring::OverlapWithAssignments(
LiveInterval *li,
int Color)
const {
255 for (
unsigned i = 0,
e = OtherLIs.size();
i !=
e; ++
i) {
273 Color = UsedColors[StackID].find_first();
274 while (Color != -1) {
275 if (!OverlapWithAssignments(li, Color)) {
280 Color = UsedColors[StackID].find_next(Color);
285 LLVM_DEBUG(
dbgs() <<
"cannot share FIs with different stack IDs\n");
292 assert(NextColors[StackID] != -1 &&
"No more spill slots?");
293 Color = NextColors[StackID];
294 UsedColors[StackID].set(Color);
295 NextColors[StackID] = AllColors[StackID].find_next(NextColors[StackID]);
301 Assignments[Color].push_back(li);
302 LLVM_DEBUG(
dbgs() <<
"Assigning fi#" << FI <<
" to fi#" << Color <<
"\n");
310 int64_t
Size = OrigSizes[FI];
326 bool Changed =
false;
329 int NewSS = ColorSlot(li);
330 assert(NewSS >= 0 &&
"Stack coloring failed?");
332 RevMap[NewSS].push_back(
SS);
333 SlotWeights[NewSS] += li->
weight();
334 UsedColors.set(NewSS);
335 Changed |= (
SS != NewSS);
356 for (
unsigned SS = 0, SE = SSRefs.size();
SS != SE; ++
SS) {
358 if (NewFI == -1 || (NewFI == (
int)
SS))
363 for (
unsigned i = 0,
e = RefMMOs.size();
i !=
e; ++
i)
364 RefMMOs[
i]->setValue(NewSV);
371 RemoveDeadStores(&
MBB);
375 for (
int StackID = 0,
E = AllColors.size(); StackID !=
E; ++StackID) {
376 int NextColor = NextColors[StackID];
377 while (NextColor != -1) {
378 LLVM_DEBUG(
dbgs() <<
"Removing unused stack object fi#" << NextColor <<
"\n");
380 NextColor = AllColors[StackID].find_next(NextColor);
396 int OldFI = MO.getIndex();
400 if (NewFI == -1 || NewFI == OldFI)
418 bool changed =
false;
426 int FirstSS, SecondSS;
427 if (
TII->isStackSlotCopy(*
I, FirstSS, SecondSS) && FirstSS == SecondSS &&
431 toErase.push_back(&*
I);
438 unsigned LoadReg = 0;
439 unsigned StoreReg = 0;
440 unsigned LoadSize = 0;
441 unsigned StoreSize = 0;
445 while ((NextMI !=
E) && NextMI->isDebugInstr()) {
449 if (NextMI ==
E)
continue;
452 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1 ||
453 LoadSize != StoreSize)
459 if (NextMI->findRegisterUseOperandIdx(LoadReg,
true,
nullptr) != -1) {
461 toErase.push_back(&*ProbableLoadMI);
464 toErase.push_back(&*NextMI);
469 MI->eraseFromParent();
476 dbgs() <<
"********** Stack Slot Coloring **********\n"
477 <<
"********** Function: " << MF.
getName() <<
'\n';
485 LS = &getAnalysis<LiveStacks>();
486 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
488 bool Changed =
false;
490 unsigned NumSlots =
LS->getNumIntervals();
503 ScanForSpillSlotRefs(MF);
505 Changed = ColorSlots(MF);
507 for (
int &Next : NextColors)
511 for (
unsigned i = 0,
e = SSRefs.size();
i !=
e; ++
i)
514 OrigAlignments.
clear();
518 for (
unsigned i = 0,
e = Assignments.size();
i !=
e; ++
i)
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...
This is an optimization pass for GlobalISel generic memory operations.
static cl::opt< bool > DisableSharing("no-stack-slot-sharing", cl::init(false), cl::Hidden, cl::desc("Suppress slot sharing during stack coloring"))
virtual const TargetInstrInfo * getInstrInfo() const
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
bool exposesReturnsTwice() const
exposesReturnsTwice - Returns true if the function calls setjmp or any other similar functions with a...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
static int stackSlot2Index(Register Reg)
Compute the frame index from a register value representing a stack slot.
A description of a memory reference used in the backend.
PseudoSourceValueManager & getPSVManager() const
void setObjectSize(int ObjectIdx, int64_t Size)
Change the size of the specified stack 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.
char & StackSlotColoringID
StackSlotColoring - This pass performs stack slot coloring.
void setObjectAlignment(int ObjectIdx, Align Alignment)
setObjectAlignment - Change the alignment of the specified stack object.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
TargetInstrInfo - Interface to description of machine instruction set.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
bool operator()(LiveInterval *LHS, LiveInterval *RHS) const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Represent the analysis usage information of a pass.
const HexagonInstrInfo * TII
MachineOperand class - Representation of each machine instruction operand.
STATISTIC(NumFunctions, "Total number of functions")
uint8_t getStackID(int ObjectIdx) const
Special value supplied for machine level alias analysis.
LiveInterval - This class represents the liveness of a register, or stack slot.
This struct is a compact representation of a valid (non-zero power of two) alignment.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
bool isDeadObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a dead object.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
This struct contains the mappings from the slot numbers to unnamed metadata nodes,...
Representation of each machine instruction.
int64_t getObjectSize(int ObjectIdx) const
Return the size of the specified object.
void incrementWeight(float Inc)
INITIALIZE_PASS_BEGIN(StackSlotColoring, DEBUG_TYPE, "Stack Slot Coloring", false, false) INITIALIZE_PASS_END(StackSlotColoring
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
Align getObjectAlign(int ObjectIdx) const
Return the alignment of the specified stack object.
initializer< Ty > init(const Ty &Val)
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
ArrayRef< MachineMemOperand * >::iterator mmo_iterator
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
unsigned isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const override
TargetInstrInfo overrides.
void setWeight(float Value)
void stable_sort(R &&Range)
Function & getFunction()
Return the LLVM function that this machine code represents.
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI)
Calculate the spill weight to assign to a single instruction.
const PseudoSourceValue * getFixedStack(int FI)
Return a pseudo source value referencing a fixed stack frame entry, e.g., a spill slot.
void initializeStackSlotColoringPass(PassRegistry &)
A specialized PseudoSourceValue for holding FixedStack values, which must include a frame index.
void sort(IteratorTy Start, IteratorTy End)
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
AnalysisUsage & addRequired()
void reserve(size_type N)
static cl::opt< int > DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden)
const PseudoSourceValue * getPseudoValue() const