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