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