48#define DEBUG_TYPE "stack-slot-coloring"
53 cl::desc(
"Suppress slot sharing during stack coloring"));
57STATISTIC(NumEliminated,
"Number of stack slots eliminated due to coloring");
58STATISTIC(NumDead,
"Number of trivially dead stack accesses eliminated");
69 std::vector<LiveInterval*> SSIntervals;
97 class ColorAssignmentInfo {
107 ~ColorAssignmentInfo() {
109 LIU->~LiveIntervalUnion();
117 return SingleLI ? SingleLI->
overlaps(*LI) :
false;
124 LIU->
unify(*LI, *LI);
125 }
else if (SingleLI) {
127 LIU->
unify(*SingleLI, *SingleLI);
128 LIU->
unify(*LI, *LI);
161 void InitializeSlots();
172char StackSlotColoring::ID = 0;
177 "Stack Slot Coloring",
false,
false)
190 return LHS->weight() >
RHS->weight();
207 int FI = MO.getIndex();
210 if (!
LS->hasInterval(FI))
213 if (!
MI.isDebugInstr())
218 EE =
MI.memoperands_end();
219 MMOI != EE; ++MMOI) {
222 dyn_cast_or_null<FixedStackPseudoSourceValue>(
224 int FI = FSV->getFrameIndex();
235void StackSlotColoring::InitializeSlots() {
242 OrigAlignments.
resize(LastFI);
244 AllColors[0].
resize(LastFI);
245 UsedColors[0].
resize(LastFI);
246 Assignments.
resize(LastFI);
248 using Pair = std::iterator_traits<LiveStacks::iterator>::value_type;
252 Intervals.
reserve(
LS->getNumIntervals());
256 [](Pair *LHS, Pair *RHS) {
return LHS->first <
RHS->first; });
260 for (
auto *
I : Intervals) {
267 SSIntervals.push_back(&li);
273 AllColors.
resize(StackID + 1);
274 UsedColors.
resize(StackID + 1);
275 AllColors[StackID].
resize(LastFI);
276 UsedColors[StackID].
resize(LastFI);
279 AllColors[StackID].set(FI);
289 for (
unsigned I = 0,
E = AllColors.
size();
I !=
E; ++
I)
290 NextColors[
I] = AllColors[
I].find_first();
303 Color = UsedColors[StackID].find_first();
304 while (Color != -1) {
305 if (!Assignments[Color].overlaps(li)) {
310 Color = UsedColors[StackID].find_next(Color);
315 LLVM_DEBUG(
dbgs() <<
"cannot share FIs with different stack IDs\n");
322 assert(NextColors[StackID] != -1 &&
"No more spill slots?");
323 Color = NextColors[StackID];
324 UsedColors[StackID].set(Color);
325 NextColors[StackID] = AllColors[StackID].find_next(NextColors[StackID]);
331 Assignments[Color].add(li, LIUAlloc);
332 LLVM_DEBUG(
dbgs() <<
"Assigning fi#" << FI <<
" to fi#" << Color <<
"\n");
337 Align Alignment = OrigAlignments[FI];
340 int64_t
Size = OrigSizes[FI];
356 bool Changed =
false;
359 int NewSS = ColorSlot(li);
360 assert(NewSS >= 0 &&
"Stack coloring failed?");
362 RevMap[NewSS].push_back(SS);
363 SlotWeights[NewSS] += li->
weight();
364 UsedColors.set(NewSS);
365 Changed |= (
SS != NewSS);
386 for (
unsigned SS = 0, SE = SSRefs.
size(); SS != SE; ++SS) {
388 if (NewFI == -1 || (NewFI == (
int)SS))
393 for (
unsigned i = 0, e = RefMMOs.
size(); i != e; ++i)
394 RefMMOs[i]->setValue(NewSV);
401 RemoveDeadStores(&
MBB);
405 for (
int StackID = 0,
E = AllColors.
size(); StackID !=
E; ++StackID) {
406 int NextColor = NextColors[StackID];
407 while (NextColor != -1) {
408 LLVM_DEBUG(
dbgs() <<
"Removing unused stack object fi#" << NextColor <<
"\n");
410 NextColor = AllColors[StackID].find_next(NextColor);
426 int OldFI = MO.getIndex();
430 if (NewFI == -1 || NewFI == OldFI)
448 bool changed =
false;
456 int FirstSS, SecondSS;
457 if (
TII->isStackSlotCopy(*
I, FirstSS, SecondSS) && FirstSS == SecondSS &&
468 unsigned LoadReg = 0;
469 unsigned StoreReg = 0;
470 unsigned LoadSize = 0;
471 unsigned StoreSize = 0;
475 while ((NextMI !=
E) && NextMI->isDebugInstr()) {
479 if (NextMI ==
E)
continue;
482 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1 ||
489 if (NextMI->findRegisterUseOperandIdx(LoadReg,
true,
nullptr) != -1) {
499 MI->eraseFromParent();
506 dbgs() <<
"********** Stack Slot Coloring **********\n"
507 <<
"********** Function: " << MF.
getName() <<
'\n';
515 LS = &getAnalysis<LiveStacks>();
516 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
518 bool Changed =
false;
520 unsigned NumSlots =
LS->getNumIntervals();
532 ScanForSpillSlotRefs(MF);
534 Changed = ColorSlots(MF);
536 for (
int &Next : NextColors)
540 for (
unsigned i = 0, e = SSRefs.
size(); i != e; ++i)
543 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.
Register isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const override
TargetInstrInfo overrides.
Register 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...
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.
bool isSpillSlotObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a spill slot.
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,...