1//===- StackSlotColoring.cpp - Stack slot coloring pass. ------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the stack slot coloring pass.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/ADT/BitVector.h"
14#include "llvm/ADT/SmallVector.h"
15#include "llvm/ADT/Statistic.h"
16#include "llvm/CodeGen/LiveInterval.h"
17#include "llvm/CodeGen/LiveIntervalUnion.h"
18#include "llvm/CodeGen/LiveIntervals.h"
19#include "llvm/CodeGen/LiveStacks.h"
20#include "llvm/CodeGen/MachineBasicBlock.h"
21#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
22#include "llvm/CodeGen/MachineFrameInfo.h"
23#include "llvm/CodeGen/MachineFunction.h"
24#include "llvm/CodeGen/MachineFunctionPass.h"
25#include "llvm/CodeGen/MachineInstr.h"
26#include "llvm/CodeGen/MachineMemOperand.h"
27#include "llvm/CodeGen/MachineOperand.h"
28#include "llvm/CodeGen/Passes.h"
29#include "llvm/CodeGen/PseudoSourceValue.h"
30#include "llvm/CodeGen/PseudoSourceValueManager.h"
31#include "llvm/CodeGen/SlotIndexes.h"
32#include "llvm/CodeGen/TargetInstrInfo.h"
33#include "llvm/CodeGen/TargetSubtargetInfo.h"
34#include "llvm/InitializePasses.h"
35#include "llvm/Pass.h"
36#include "llvm/Support/Casting.h"
37#include "llvm/Support/CommandLine.h"
38#include "llvm/Support/Debug.h"
39#include "llvm/Support/raw_ostream.h"
40#include <algorithm>
41#include <cassert>
42#include <cstdint>
43#include <iterator>
44#include <vector>
45
46using namespace llvm;
47
48#define DEBUG_TYPE "stack-slot-coloring"
49
50static cl::opt<bool>
51DisableSharing("no-stack-slot-sharing",
52 cl::init(Val: false), cl::Hidden,
53 cl::desc("Suppress slot sharing during stack coloring"));
54
55static cl::opt<int> DCELimit("ssc-dce-limit", cl::init(Val: -1), cl::Hidden);
56
57STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring");
58STATISTIC(NumDead, "Number of trivially dead stack accesses eliminated");
59
60namespace {
61
62 class StackSlotColoring : public MachineFunctionPass {
63 LiveStacks *LS = nullptr;
64 MachineFrameInfo *MFI = nullptr;
65 const TargetInstrInfo *TII = nullptr;
66 const MachineBlockFrequencyInfo *MBFI = nullptr;
67
68 // SSIntervals - Spill slot intervals.
69 std::vector<LiveInterval*> SSIntervals;
70
71 // SSRefs - Keep a list of MachineMemOperands for each spill slot.
72 // MachineMemOperands can be shared between instructions, so we need
73 // to be careful that renames like [FI0, FI1] -> [FI1, FI2] do not
74 // become FI0 -> FI1 -> FI2.
75 SmallVector<SmallVector<MachineMemOperand *, 8>, 16> SSRefs;
76
77 // OrigAlignments - Alignments of stack objects before coloring.
78 SmallVector<Align, 16> OrigAlignments;
79
80 // OrigSizes - Sizes of stack objects before coloring.
81 SmallVector<unsigned, 16> OrigSizes;
82
83 // AllColors - If index is set, it's a spill slot, i.e. color.
84 // FIXME: This assumes PEI locate spill slot with smaller indices
85 // closest to stack pointer / frame pointer. Therefore, smaller
86 // index == better color. This is per stack ID.
87 SmallVector<BitVector, 2> AllColors;
88
89 // NextColor - Next "color" that's not yet used. This is per stack ID.
90 SmallVector<int, 2> NextColors = { -1 };
91
92 // UsedColors - "Colors" that have been assigned. This is per stack ID
93 SmallVector<BitVector, 2> UsedColors;
94
95 // Join all intervals sharing one color into a single LiveIntervalUnion to
96 // speedup range overlap test.
97 class ColorAssignmentInfo {
98 // Single liverange (used to avoid creation of LiveIntervalUnion).
99 LiveInterval *SingleLI = nullptr;
100 // LiveIntervalUnion to perform overlap test.
101 LiveIntervalUnion *LIU = nullptr;
102 // LiveIntervalUnion has a parameter in its constructor so doing this
103 // dirty magic.
104 uint8_t LIUPad[sizeof(LiveIntervalUnion)];
105
106 public:
107 ~ColorAssignmentInfo() {
108 if (LIU)
109 LIU->~LiveIntervalUnion(); // Dirty magic again.
110 }
111
112 // Return true if LiveInterval overlaps with any
113 // intervals that have already been assigned to this color.
114 bool overlaps(LiveInterval *LI) const {
115 if (LIU)
116 return LiveIntervalUnion::Query(*LI, *LIU).checkInterference();
117 return SingleLI ? SingleLI->overlaps(other: *LI) : false;
118 }
119
120 // Add new LiveInterval to this color.
121 void add(LiveInterval *LI, LiveIntervalUnion::Allocator &Alloc) {
122 assert(!overlaps(LI));
123 if (LIU) {
124 LIU->unify(VirtReg: *LI, Range: *LI);
125 } else if (SingleLI) {
126 LIU = new (LIUPad) LiveIntervalUnion(Alloc);
127 LIU->unify(VirtReg: *SingleLI, Range: *SingleLI);
128 LIU->unify(VirtReg: *LI, Range: *LI);
129 SingleLI = nullptr;
130 } else
131 SingleLI = LI;
132 }
133 };
134
135 LiveIntervalUnion::Allocator LIUAlloc;
136
137 // Assignments - Color to intervals mapping.
138 SmallVector<ColorAssignmentInfo, 16> Assignments;
139
140 public:
141 static char ID; // Pass identification
142
143 StackSlotColoring() : MachineFunctionPass(ID) {
144 initializeStackSlotColoringPass(*PassRegistry::getPassRegistry());
145 }
146
147 void getAnalysisUsage(AnalysisUsage &AU) const override {
148 AU.setPreservesCFG();
149 AU.addRequired<SlotIndexes>();
150 AU.addPreserved<SlotIndexes>();
151 AU.addRequired<LiveStacks>();
152 AU.addRequired<MachineBlockFrequencyInfo>();
153 AU.addPreserved<MachineBlockFrequencyInfo>();
154 AU.addPreservedID(ID&: MachineDominatorsID);
155 MachineFunctionPass::getAnalysisUsage(AU);
156 }
157
158 bool runOnMachineFunction(MachineFunction &MF) override;
159
160 private:
161 void InitializeSlots();
162 void ScanForSpillSlotRefs(MachineFunction &MF);
163 int ColorSlot(LiveInterval *li);
164 bool ColorSlots(MachineFunction &MF);
165 void RewriteInstruction(MachineInstr &MI, SmallVectorImpl<int> &SlotMapping,
166 MachineFunction &MF);
167 bool RemoveDeadStores(MachineBasicBlock* MBB);
168 };
169
170} // end anonymous namespace
171
172char StackSlotColoring::ID = 0;
173
174char &llvm::StackSlotColoringID = StackSlotColoring::ID;
175
176INITIALIZE_PASS_BEGIN(StackSlotColoring, DEBUG_TYPE,
177 "Stack Slot Coloring", false, false)
178INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
179INITIALIZE_PASS_DEPENDENCY(LiveStacks)
180INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
181INITIALIZE_PASS_END(StackSlotColoring, DEBUG_TYPE,
182 "Stack Slot Coloring", false, false)
183
184namespace {
185
186// IntervalSorter - Comparison predicate that sort live intervals by
187// their weight.
188struct IntervalSorter {
189 bool operator()(LiveInterval* LHS, LiveInterval* RHS) const {
190 return LHS->weight() > RHS->weight();
191 }
192};
193
194} // end anonymous namespace
195
196/// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot
197/// references and update spill slot weights.
198void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) {
199 SSRefs.resize(N: MFI->getObjectIndexEnd());
200
201 // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands.
202 for (MachineBasicBlock &MBB : MF) {
203 for (MachineInstr &MI : MBB) {
204 for (const MachineOperand &MO : MI.operands()) {
205 if (!MO.isFI())
206 continue;
207 int FI = MO.getIndex();
208 if (FI < 0)
209 continue;
210 if (!LS->hasInterval(Slot: FI))
211 continue;
212 LiveInterval &li = LS->getInterval(Slot: FI);
213 if (!MI.isDebugInstr())
214 li.incrementWeight(
215 Inc: LiveIntervals::getSpillWeight(isDef: false, isUse: true, MBFI, MI));
216 }
217 for (MachineInstr::mmo_iterator MMOI = MI.memoperands_begin(),
218 EE = MI.memoperands_end();
219 MMOI != EE; ++MMOI) {
220 MachineMemOperand *MMO = *MMOI;
221 if (const FixedStackPseudoSourceValue *FSV =
222 dyn_cast_or_null<FixedStackPseudoSourceValue>(
223 Val: MMO->getPseudoValue())) {
224 int FI = FSV->getFrameIndex();
225 if (FI >= 0)
226 SSRefs[FI].push_back(Elt: MMO);
227 }
228 }
229 }
230 }
231}
232
233/// InitializeSlots - Process all spill stack slot liveintervals and add them
234/// to a sorted (by weight) list.
235void StackSlotColoring::InitializeSlots() {
236 int LastFI = MFI->getObjectIndexEnd();
237
238 // There is always at least one stack ID.
239 AllColors.resize(N: 1);
240 UsedColors.resize(N: 1);
241
242 OrigAlignments.resize(N: LastFI);
243 OrigSizes.resize(N: LastFI);
244 AllColors[0].resize(N: LastFI);
245 UsedColors[0].resize(N: LastFI);
246 Assignments.resize(N: LastFI);
247
248 using Pair = std::iterator_traits<LiveStacks::iterator>::value_type;
249
250 SmallVector<Pair *, 16> Intervals;
251
252 Intervals.reserve(N: LS->getNumIntervals());
253 for (auto &I : *LS)
254 Intervals.push_back(Elt: &I);
255 llvm::sort(C&: Intervals,
256 Comp: [](Pair *LHS, Pair *RHS) { return LHS->first < RHS->first; });
257
258 // Gather all spill slots into a list.
259 LLVM_DEBUG(dbgs() << "Spill slot intervals:\n");
260 for (auto *I : Intervals) {
261 LiveInterval &li = I->second;
262 LLVM_DEBUG(li.dump());
263 int FI = Register::stackSlot2Index(Reg: li.reg());
264 if (MFI->isDeadObjectIndex(ObjectIdx: FI))
265 continue;
266
267 SSIntervals.push_back(x: &li);
268 OrigAlignments[FI] = MFI->getObjectAlign(ObjectIdx: FI);
269 OrigSizes[FI] = MFI->getObjectSize(ObjectIdx: FI);
270
271 auto StackID = MFI->getStackID(ObjectIdx: FI);
272 if (StackID != 0) {
273 AllColors.resize(N: StackID + 1);
274 UsedColors.resize(N: StackID + 1);
275 AllColors[StackID].resize(N: LastFI);
276 UsedColors[StackID].resize(N: LastFI);
277 }
278
279 AllColors[StackID].set(FI);
280 }
281 LLVM_DEBUG(dbgs() << '\n');
282
283 // Sort them by weight.
284 llvm::stable_sort(Range&: SSIntervals, C: IntervalSorter());
285
286 NextColors.resize(N: AllColors.size());
287
288 // Get first "color".
289 for (unsigned I = 0, E = AllColors.size(); I != E; ++I)
290 NextColors[I] = AllColors[I].find_first();
291}
292
293/// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.
294int StackSlotColoring::ColorSlot(LiveInterval *li) {
295 int Color = -1;
296 bool Share = false;
297 int FI = Register::stackSlot2Index(Reg: li->reg());
298 uint8_t StackID = MFI->getStackID(ObjectIdx: FI);
299
300 if (!DisableSharing) {
301
302 // Check if it's possible to reuse any of the used colors.
303 Color = UsedColors[StackID].find_first();
304 while (Color != -1) {
305 if (!Assignments[Color].overlaps(LI: li)) {
306 Share = true;
307 ++NumEliminated;
308 break;
309 }
310 Color = UsedColors[StackID].find_next(Prev: Color);
311 }
312 }
313
314 if (Color != -1 && MFI->getStackID(ObjectIdx: Color) != MFI->getStackID(ObjectIdx: FI)) {
315 LLVM_DEBUG(dbgs() << "cannot share FIs with different stack IDs\n");
316 Share = false;
317 }
318
319 // Assign it to the first available color (assumed to be the best) if it's
320 // not possible to share a used color with other objects.
321 if (!Share) {
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(Prev: NextColors[StackID]);
326 }
327
328 assert(MFI->getStackID(Color) == MFI->getStackID(FI));
329
330 // Record the assignment.
331 Assignments[Color].add(LI: li, Alloc&: LIUAlloc);
332 LLVM_DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n");
333
334 // Change size and alignment of the allocated slot. If there are multiple
335 // objects sharing the same slot, then make sure the size and alignment
336 // are large enough for all.
337 Align Alignment = OrigAlignments[FI];
338 if (!Share || Alignment > MFI->getObjectAlign(ObjectIdx: Color))
339 MFI->setObjectAlignment(ObjectIdx: Color, Alignment);
340 int64_t Size = OrigSizes[FI];
341 if (!Share || Size > MFI->getObjectSize(ObjectIdx: Color))
342 MFI->setObjectSize(ObjectIdx: Color, Size);
343 return Color;
344}
345
346/// Colorslots - Color all spill stack slots and rewrite all frameindex machine
347/// operands in the function.
348bool StackSlotColoring::ColorSlots(MachineFunction &MF) {
349 unsigned NumObjs = MFI->getObjectIndexEnd();
350 SmallVector<int, 16> SlotMapping(NumObjs, -1);
351 SmallVector<float, 16> SlotWeights(NumObjs, 0.0);
352 SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs);
353 BitVector UsedColors(NumObjs);
354
355 LLVM_DEBUG(dbgs() << "Color spill slot intervals:\n");
356 bool Changed = false;
357 for (LiveInterval *li : SSIntervals) {
358 int SS = Register::stackSlot2Index(Reg: li->reg());
359 int NewSS = ColorSlot(li);
360 assert(NewSS >= 0 && "Stack coloring failed?");
361 SlotMapping[SS] = NewSS;
362 RevMap[NewSS].push_back(Elt: SS);
363 SlotWeights[NewSS] += li->weight();
364 UsedColors.set(NewSS);
365 Changed |= (SS != NewSS);
366 }
367
368 LLVM_DEBUG(dbgs() << "\nSpill slots after coloring:\n");
369 for (LiveInterval *li : SSIntervals) {
370 int SS = Register::stackSlot2Index(Reg: li->reg());
371 li->setWeight(SlotWeights[SS]);
372 }
373 // Sort them by new weight.
374 llvm::stable_sort(Range&: SSIntervals, C: IntervalSorter());
375
376#ifndef NDEBUG
377 for (LiveInterval *li : SSIntervals)
378 LLVM_DEBUG(li->dump());
379 LLVM_DEBUG(dbgs() << '\n');
380#endif
381
382 if (!Changed)
383 return false;
384
385 // Rewrite all MachineMemOperands.
386 for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) {
387 int NewFI = SlotMapping[SS];
388 if (NewFI == -1 || (NewFI == (int)SS))
389 continue;
390
391 const PseudoSourceValue *NewSV = MF.getPSVManager().getFixedStack(FI: NewFI);
392 SmallVectorImpl<MachineMemOperand *> &RefMMOs = SSRefs[SS];
393 for (unsigned i = 0, e = RefMMOs.size(); i != e; ++i)
394 RefMMOs[i]->setValue(NewSV);
395 }
396
397 // Rewrite all MO_FrameIndex operands. Look for dead stores.
398 for (MachineBasicBlock &MBB : MF) {
399 for (MachineInstr &MI : MBB)
400 RewriteInstruction(MI, SlotMapping, MF);
401 RemoveDeadStores(MBB: &MBB);
402 }
403
404 // Delete unused stack slots.
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");
409 MFI->RemoveStackObject(ObjectIdx: NextColor);
410 NextColor = AllColors[StackID].find_next(Prev: NextColor);
411 }
412 }
413
414 return true;
415}
416
417/// RewriteInstruction - Rewrite specified instruction by replacing references
418/// to old frame index with new one.
419void StackSlotColoring::RewriteInstruction(MachineInstr &MI,
420 SmallVectorImpl<int> &SlotMapping,
421 MachineFunction &MF) {
422 // Update the operands.
423 for (MachineOperand &MO : MI.operands()) {
424 if (!MO.isFI())
425 continue;
426 int OldFI = MO.getIndex();
427 if (OldFI < 0)
428 continue;
429 int NewFI = SlotMapping[OldFI];
430 if (NewFI == -1 || NewFI == OldFI)
431 continue;
432
433 assert(MFI->getStackID(OldFI) == MFI->getStackID(NewFI));
434 MO.setIndex(NewFI);
435 }
436
437 // The MachineMemOperands have already been updated.
438}
439
440/// RemoveDeadStores - Scan through a basic block and look for loads followed
441/// by stores. If they're both using the same stack slot, then the store is
442/// definitely dead. This could obviously be much more aggressive (consider
443/// pairs with instructions between them), but such extensions might have a
444/// considerable compile time impact.
445bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) {
446 // FIXME: This could be much more aggressive, but we need to investigate
447 // the compile time impact of doing so.
448 bool changed = false;
449
450 SmallVector<MachineInstr*, 4> toErase;
451
452 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
453 I != E; ++I) {
454 if (DCELimit != -1 && (int)NumDead >= DCELimit)
455 break;
456 int FirstSS, SecondSS;
457 if (TII->isStackSlotCopy(MI: *I, DestFrameIndex&: FirstSS, SrcFrameIndex&: SecondSS) && FirstSS == SecondSS &&
458 FirstSS != -1) {
459 ++NumDead;
460 changed = true;
461 toErase.push_back(Elt: &*I);
462 continue;
463 }
464
465 MachineBasicBlock::iterator NextMI = std::next(x: I);
466 MachineBasicBlock::iterator ProbableLoadMI = I;
467
468 unsigned LoadReg = 0;
469 unsigned StoreReg = 0;
470 unsigned LoadSize = 0;
471 unsigned StoreSize = 0;
472 if (!(LoadReg = TII->isLoadFromStackSlot(MI: *I, FrameIndex&: FirstSS, MemBytes&: LoadSize)))
473 continue;
474 // Skip the ...pseudo debugging... instructions between a load and store.
475 while ((NextMI != E) && NextMI->isDebugInstr()) {
476 ++NextMI;
477 ++I;
478 }
479 if (NextMI == E) continue;
480 if (!(StoreReg = TII->isStoreToStackSlot(MI: *NextMI, FrameIndex&: SecondSS, MemBytes&: StoreSize)))
481 continue;
482 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1 ||
483 LoadSize != StoreSize || !MFI->isSpillSlotObjectIndex(ObjectIdx: FirstSS))
484 continue;
485
486 ++NumDead;
487 changed = true;
488
489 if (NextMI->findRegisterUseOperandIdx(Reg: LoadReg, /*TRI=*/nullptr, isKill: true) !=
490 -1) {
491 ++NumDead;
492 toErase.push_back(Elt: &*ProbableLoadMI);
493 }
494
495 toErase.push_back(Elt: &*NextMI);
496 ++I;
497 }
498
499 for (MachineInstr *MI : toErase)
500 MI->eraseFromParent();
501
502 return changed;
503}
504
505bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
506 LLVM_DEBUG({
507 dbgs() << "********** Stack Slot Coloring **********\n"
508 << "********** Function: " << MF.getName() << '\n';
509 });
510
511 if (skipFunction(F: MF.getFunction()))
512 return false;
513
514 MFI = &MF.getFrameInfo();
515 TII = MF.getSubtarget().getInstrInfo();
516 LS = &getAnalysis<LiveStacks>();
517 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
518
519 bool Changed = false;
520
521 unsigned NumSlots = LS->getNumIntervals();
522 if (NumSlots == 0)
523 // Nothing to do!
524 return false;
525
526 // If there are calls to setjmp or sigsetjmp, don't perform stack slot
527 // coloring. The stack could be modified before the longjmp is executed,
528 // resulting in the wrong value being used afterwards.
529 if (MF.exposesReturnsTwice())
530 return false;
531
532 // Gather spill slot references
533 ScanForSpillSlotRefs(MF);
534 InitializeSlots();
535 Changed = ColorSlots(MF);
536
537 for (int &Next : NextColors)
538 Next = -1;
539
540 SSIntervals.clear();
541 for (unsigned i = 0, e = SSRefs.size(); i != e; ++i)
542 SSRefs[i].clear();
543 SSRefs.clear();
544 OrigAlignments.clear();
545 OrigSizes.clear();
546 AllColors.clear();
547 UsedColors.clear();
548 Assignments.clear();
549
550 return Changed;
551}
552

source code of llvm/lib/CodeGen/StackSlotColoring.cpp