50#define DEBUG_TYPE "stack-slot-coloring"
52STATISTIC(NumEliminated,
"Number of stack slots eliminated due to coloring");
53STATISTIC(NumDead,
"Number of trivially dead stack accesses eliminated");
57class StackSlotColoring {
58 const CodeGenOptions &Opts;
66 std::vector<LiveInterval *> SSIntervals;
94 class ColorAssignmentInfo {
96 LiveInterval *SingleLI =
nullptr;
98 LiveIntervalUnion *LIU =
nullptr;
101 uint8_t LIUPad[
sizeof(LiveIntervalUnion)];
104 ~ColorAssignmentInfo() {
106 LIU->~LiveIntervalUnion();
111 bool overlaps(LiveInterval *LI)
const {
113 return LiveIntervalUnion::Query(*LI, *LIU).checkInterference();
114 return SingleLI ? SingleLI->overlaps(*LI) :
false;
121 LIU->unify(*LI, *LI);
122 }
else if (SingleLI) {
123 LIU =
new (LIUPad) LiveIntervalUnion(
Alloc);
124 LIU->unify(*SingleLI, *SingleLI);
125 LIU->unify(*LI, *LI);
139 MachineBlockFrequencyInfo *MBFI, SlotIndexes *Indexes)
141 TII(MF.getSubtarget().getInstrInfo()), LS(LS), MBFI(MBFI),
146 void InitializeSlots();
148 int ColorSlot(LiveInterval *li);
150 void RewriteInstruction(MachineInstr &
MI, SmallVectorImpl<int> &SlotMapping,
152 bool RemoveDeadStores(MachineBasicBlock *
MBB);
159 StackSlotColoringLegacy() : MachineFunctionPass(ID) {}
161 void getAnalysisUsage(AnalysisUsage &AU)
const override {
166 AU.
addRequired<MachineBlockFrequencyInfoWrapperPass>();
183char StackSlotColoringLegacy::ID = 0;
188 "Stack Slot Coloring",
false,
false)
201 return LHS->weight() > RHS->weight();
213 for (MachineBasicBlock &
MBB : MF) {
214 for (MachineInstr &
MI :
MBB) {
215 for (
const MachineOperand &MO :
MI.operands()) {
218 int FI = MO.getIndex();
221 if (!
LS->hasInterval(FI))
223 LiveInterval &li =
LS->getInterval(FI);
224 if (!
MI.isDebugInstr())
228 for (MachineMemOperand *MMO :
MI.memoperands()) {
229 if (
const FixedStackPseudoSourceValue *FSV =
231 MMO->getPseudoValue())) {
232 int FI = FSV->getFrameIndex();
243void StackSlotColoring::InitializeSlots() {
250 OrigAlignments.
resize(LastFI);
252 AllColors[0].
resize(LastFI);
253 UsedColors[0].
resize(LastFI);
254 Assignments.resize(LastFI);
256 using Pair = std::iterator_traits<LiveStacks::iterator>::value_type;
260 Intervals.
reserve(
LS->getNumIntervals());
264 [](Pair *
LHS, Pair *
RHS) {
return LHS->first <
RHS->first; });
268 for (
auto *
I : Intervals) {
269 LiveInterval &li =
I->second;
275 SSIntervals.push_back(&li);
281 if (StackID >= AllColors.
size()) {
282 AllColors.
resize(StackID + 1);
283 UsedColors.
resize(StackID + 1);
285 AllColors[StackID].
resize(LastFI);
286 UsedColors[StackID].
resize(LastFI);
289 AllColors[StackID].set(FI);
299 for (
unsigned I = 0,
E = AllColors.
size();
I !=
E; ++
I)
300 NextColors[
I] = AllColors[
I].find_first();
304int StackSlotColoring::ColorSlot(LiveInterval *li) {
310 if (Opts.stack_slot_sharing) {
313 Color = UsedColors[StackID].find_first();
314 while (Color != -1) {
315 if (!Assignments[Color].overlaps(li)) {
320 Color = UsedColors[StackID].find_next(Color);
325 LLVM_DEBUG(
dbgs() <<
"cannot share FIs with different stack IDs\n");
332 assert(NextColors[StackID] != -1 &&
"No more spill slots?");
333 Color = NextColors[StackID];
334 UsedColors[StackID].set(Color);
335 NextColors[StackID] = AllColors[StackID].find_next(NextColors[StackID]);
341 Assignments[Color].add(li, LIUAlloc);
342 LLVM_DEBUG(
dbgs() <<
"Assigning fi#" << FI <<
" to fi#" << Color <<
"\n");
350 int64_t
Size = OrigSizes[FI];
360 SmallVector<int, 16> SlotMapping(NumObjs, -1);
363 BitVector UsedColors(NumObjs);
367 for (LiveInterval *li : SSIntervals) {
369 int NewSS = ColorSlot(li);
370 assert(NewSS >= 0 &&
"Stack coloring failed?");
371 SlotMapping[
SS] = NewSS;
372 RevMap[NewSS].push_back(SS);
373 SlotWeights[NewSS] += li->
weight();
374 UsedColors.set(NewSS);
379 for (LiveInterval *li : SSIntervals) {
387 for (LiveInterval *li : SSIntervals)
396 for (
unsigned SS = 0, SE = SSRefs.
size(); SS != SE; ++SS) {
397 int NewFI = SlotMapping[
SS];
398 if (NewFI == -1 || (NewFI == (
int)SS))
402 SmallVectorImpl<MachineMemOperand *> &RefMMOs = SSRefs[
SS];
403 for (MachineMemOperand *MMO : RefMMOs)
404 MMO->setValue(NewSV);
408 for (MachineBasicBlock &
MBB : MF) {
409 for (MachineInstr &
MI :
MBB)
410 RewriteInstruction(
MI, SlotMapping, MF);
411 RemoveDeadStores(&
MBB);
415 for (
int StackID = 0,
E = AllColors.
size(); StackID !=
E; ++StackID) {
416 int NextColor = NextColors[StackID];
417 while (NextColor != -1) {
418 LLVM_DEBUG(
dbgs() <<
"Removing unused stack object fi#" << NextColor <<
"\n");
420 NextColor = AllColors[StackID].find_next(NextColor);
429void StackSlotColoring::RewriteInstruction(MachineInstr &
MI,
430 SmallVectorImpl<int> &SlotMapping,
433 for (MachineOperand &MO :
MI.operands()) {
436 int OldFI = MO.getIndex();
439 int NewFI = SlotMapping[OldFI];
440 if (NewFI == -1 || NewFI == OldFI)
455bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock*
MBB) {
458 bool changed =
false;
460 SmallVector<MachineInstr*, 4> toErase;
464 if (Opts.ssc_dce_limit != -1 && (
int)NumDead >= Opts.ssc_dce_limit)
466 int FirstSS, SecondSS;
467 if (
TII->isStackSlotCopy(*
I, FirstSS, SecondSS) && FirstSS == SecondSS &&
485 while ((NextMI !=
E) && NextMI->isDebugInstr()) {
489 if (NextMI ==
E)
continue;
493 if (!LoadSize || !StoreSize)
495 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1 ||
502 if (NextMI->findRegisterUseOperandIdx(LoadReg,
nullptr,
true) !=
512 for (MachineInstr *
MI : toErase) {
515 MI->eraseFromParent();
523 dbgs() <<
"********** Stack Slot Coloring **********\n"
524 <<
"********** Function: " << MF.
getName() <<
'\n';
529 unsigned NumSlots =
LS->getNumIntervals();
541 ScanForSpillSlotRefs(MF);
545 for (
int &
Next : NextColors)
549 for (
auto &RefMMOs : SSRefs)
552 OrigAlignments.
clear();
561bool StackSlotColoringLegacy::runOnMachineFunction(
MachineFunction &MF) {
565 LiveStacks *
LS = &getAnalysis<LiveStacksWrapperLegacy>().getLS();
566 MachineBlockFrequencyInfo *MBFI =
567 &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
568 SlotIndexes *Indexes = &getAnalysis<SlotIndexesWrapperPass>().getSI();
569 StackSlotColoring Impl(MF, LS, MBFI, Indexes);
580 StackSlotColoring Impl(MF, LS, MBFI, Indexes);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
const AArch64InstrInfo & TII
This file implements the BitVector class.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Promote Memory to Register
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Register isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const override
Register isStoreToStackSlot(const MachineInstr &MI, int &FrameIndex) const override
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM_ABI void setPreservesCFG()
This function should be called by the pass, iff they do not:
Represents analyses that only rely on functions' control flow.
LiveSegments::Allocator Allocator
LiveInterval - This class represents the liveness of a register, or stack slot.
LLVM_ABI void dump() const
void incrementWeight(float Inc)
void setWeight(float Value)
static LLVM_ABI float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI, ProfileSummaryInfo *PSI=nullptr)
Calculate the spill weight to assign to a single instruction.
MachineInstrBundleIterator< MachineInstr > iterator
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.
PseudoSourceValueManager & getPSVManager() const
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...
Function & getFunction()
Return the LLVM function that this machine code represents.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
LLVM_ABI const PseudoSourceValue * getFixedStack(int FI)
Return a pseudo source value referencing a fixed stack frame entry, e.g., a spill slot.
int stackSlotIndex() const
Compute the frame index from a register value representing a stack slot.
LLVM_ABI void removeMachineInstrFromMaps(MachineInstr &MI, bool AllowBundled=false)
Removes machine instruction (bundle) MI from the mapping.
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.
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
TargetInstrInfo - Interface to description of machine instruction set.
static constexpr TypeSize getZero()
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
void stable_sort(R &&Range)
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
auto dyn_cast_or_null(const Y &Val)
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI char & StackSlotColoringID
StackSlotColoring - This pass performs stack slot coloring.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Next
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
bool operator()(LiveInterval *LHS, LiveInterval *RHS) const