1 //===- StackSlotColoring.cpp - Stack slot coloring pass. ------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the stack slot coloring pass.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/ADT/BitVector.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/CodeGen/LiveInterval.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/TargetRegisterInfo.h"
33 #include "llvm/CodeGen/TargetSubtargetInfo.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;
63     MachineFrameInfo *MFI;
64     const TargetInstrInfo  *TII;
65     const MachineBlockFrequencyInfo *MBFI;
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<unsigned, 16> OrigAlignments;
78 
79     // OrigSizes - Sizess 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.
86     BitVector AllColors;
87 
88     // NextColor - Next "color" that's not yet used.
89     int NextColor = -1;
90 
91     // UsedColors - "Colors" that have been assigned.
92     BitVector UsedColors;
93 
94     // Assignments - Color to intervals mapping.
95     SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments;
96 
97   public:
98     static char ID; // Pass identification
99 
100     StackSlotColoring() : MachineFunctionPass(ID) {
101       initializeStackSlotColoringPass(*PassRegistry::getPassRegistry());
102     }
103 
104     void getAnalysisUsage(AnalysisUsage &AU) const override {
105       AU.setPreservesCFG();
106       AU.addRequired<SlotIndexes>();
107       AU.addPreserved<SlotIndexes>();
108       AU.addRequired<LiveStacks>();
109       AU.addRequired<MachineBlockFrequencyInfo>();
110       AU.addPreserved<MachineBlockFrequencyInfo>();
111       AU.addPreservedID(MachineDominatorsID);
112       MachineFunctionPass::getAnalysisUsage(AU);
113     }
114 
115     bool runOnMachineFunction(MachineFunction &MF) override;
116 
117   private:
118     void InitializeSlots();
119     void ScanForSpillSlotRefs(MachineFunction &MF);
120     bool OverlapWithAssignments(LiveInterval *li, int Color) const;
121     int ColorSlot(LiveInterval *li);
122     bool ColorSlots(MachineFunction &MF);
123     void RewriteInstruction(MachineInstr &MI, SmallVectorImpl<int> &SlotMapping,
124                             MachineFunction &MF);
125     bool RemoveDeadStores(MachineBasicBlock* MBB);
126   };
127 
128 } // end anonymous namespace
129 
130 char StackSlotColoring::ID = 0;
131 
132 char &llvm::StackSlotColoringID = StackSlotColoring::ID;
133 
134 INITIALIZE_PASS_BEGIN(StackSlotColoring, DEBUG_TYPE,
135                 "Stack Slot Coloring", false, false)
136 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
137 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
138 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
139 INITIALIZE_PASS_END(StackSlotColoring, DEBUG_TYPE,
140                 "Stack Slot Coloring", false, false)
141 
142 namespace {
143 
144 // IntervalSorter - Comparison predicate that sort live intervals by
145 // their weight.
146 struct IntervalSorter {
147   bool operator()(LiveInterval* LHS, LiveInterval* RHS) const {
148     return LHS->weight > RHS->weight;
149   }
150 };
151 
152 } // end anonymous namespace
153 
154 /// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot
155 /// references and update spill slot weights.
156 void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) {
157   SSRefs.resize(MFI->getObjectIndexEnd());
158 
159   // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands.
160   for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
161        MBBI != E; ++MBBI) {
162     MachineBasicBlock *MBB = &*MBBI;
163     for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end();
164          MII != EE; ++MII) {
165       MachineInstr &MI = *MII;
166       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
167         MachineOperand &MO = MI.getOperand(i);
168         if (!MO.isFI())
169           continue;
170         int FI = MO.getIndex();
171         if (FI < 0)
172           continue;
173         if (!LS->hasInterval(FI))
174           continue;
175         LiveInterval &li = LS->getInterval(FI);
176         if (!MI.isDebugValue())
177           li.weight += LiveIntervals::getSpillWeight(false, true, MBFI, MI);
178       }
179       for (MachineInstr::mmo_iterator MMOI = MI.memoperands_begin(),
180                                       EE = MI.memoperands_end();
181            MMOI != EE; ++MMOI) {
182         MachineMemOperand *MMO = *MMOI;
183         if (const FixedStackPseudoSourceValue *FSV =
184             dyn_cast_or_null<FixedStackPseudoSourceValue>(
185                 MMO->getPseudoValue())) {
186           int FI = FSV->getFrameIndex();
187           if (FI >= 0)
188             SSRefs[FI].push_back(MMO);
189         }
190       }
191     }
192   }
193 }
194 
195 /// InitializeSlots - Process all spill stack slot liveintervals and add them
196 /// to a sorted (by weight) list.
197 void StackSlotColoring::InitializeSlots() {
198   int LastFI = MFI->getObjectIndexEnd();
199   OrigAlignments.resize(LastFI);
200   OrigSizes.resize(LastFI);
201   AllColors.resize(LastFI);
202   UsedColors.resize(LastFI);
203   Assignments.resize(LastFI);
204 
205   using Pair = std::iterator_traits<LiveStacks::iterator>::value_type;
206 
207   SmallVector<Pair *, 16> Intervals;
208 
209   Intervals.reserve(LS->getNumIntervals());
210   for (auto &I : *LS)
211     Intervals.push_back(&I);
212   std::sort(Intervals.begin(), Intervals.end(),
213             [](Pair *LHS, Pair *RHS) { return LHS->first < RHS->first; });
214 
215   // Gather all spill slots into a list.
216   DEBUG(dbgs() << "Spill slot intervals:\n");
217   for (auto *I : Intervals) {
218     LiveInterval &li = I->second;
219     DEBUG(li.dump());
220     int FI = TargetRegisterInfo::stackSlot2Index(li.reg);
221     if (MFI->isDeadObjectIndex(FI))
222       continue;
223     SSIntervals.push_back(&li);
224     OrigAlignments[FI] = MFI->getObjectAlignment(FI);
225     OrigSizes[FI]      = MFI->getObjectSize(FI);
226     AllColors.set(FI);
227   }
228   DEBUG(dbgs() << '\n');
229 
230   // Sort them by weight.
231   std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
232 
233   // Get first "color".
234   NextColor = AllColors.find_first();
235 }
236 
237 /// OverlapWithAssignments - Return true if LiveInterval overlaps with any
238 /// LiveIntervals that have already been assigned to the specified color.
239 bool
240 StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const {
241   const SmallVectorImpl<LiveInterval *> &OtherLIs = Assignments[Color];
242   for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) {
243     LiveInterval *OtherLI = OtherLIs[i];
244     if (OtherLI->overlaps(*li))
245       return true;
246   }
247   return false;
248 }
249 
250 /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.
251 int StackSlotColoring::ColorSlot(LiveInterval *li) {
252   int Color = -1;
253   bool Share = false;
254   int FI = TargetRegisterInfo::stackSlot2Index(li->reg);
255 
256   if (!DisableSharing) {
257     // Check if it's possible to reuse any of the used colors.
258     Color = UsedColors.find_first();
259     while (Color != -1) {
260       if (!OverlapWithAssignments(li, Color)) {
261         Share = true;
262         ++NumEliminated;
263         break;
264       }
265       Color = UsedColors.find_next(Color);
266     }
267   }
268 
269   if (Color != -1 && MFI->getStackID(Color) != MFI->getStackID(FI)) {
270     DEBUG(dbgs() << "cannot share FIs with different stack IDs\n");
271     Share = false;
272   }
273 
274   // Assign it to the first available color (assumed to be the best) if it's
275   // not possible to share a used color with other objects.
276   if (!Share) {
277     assert(NextColor != -1 && "No more spill slots?");
278     Color = NextColor;
279     UsedColors.set(Color);
280     NextColor = AllColors.find_next(NextColor);
281   }
282 
283   // Record the assignment.
284   Assignments[Color].push_back(li);
285   DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n");
286 
287   // Change size and alignment of the allocated slot. If there are multiple
288   // objects sharing the same slot, then make sure the size and alignment
289   // are large enough for all.
290   unsigned Align = OrigAlignments[FI];
291   if (!Share || Align > MFI->getObjectAlignment(Color))
292     MFI->setObjectAlignment(Color, Align);
293   int64_t Size = OrigSizes[FI];
294   if (!Share || Size > MFI->getObjectSize(Color))
295     MFI->setObjectSize(Color, Size);
296   return Color;
297 }
298 
299 /// Colorslots - Color all spill stack slots and rewrite all frameindex machine
300 /// operands in the function.
301 bool StackSlotColoring::ColorSlots(MachineFunction &MF) {
302   unsigned NumObjs = MFI->getObjectIndexEnd();
303   SmallVector<int, 16> SlotMapping(NumObjs, -1);
304   SmallVector<float, 16> SlotWeights(NumObjs, 0.0);
305   SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs);
306   BitVector UsedColors(NumObjs);
307 
308   DEBUG(dbgs() << "Color spill slot intervals:\n");
309   bool Changed = false;
310   for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
311     LiveInterval *li = SSIntervals[i];
312     int SS = TargetRegisterInfo::stackSlot2Index(li->reg);
313     int NewSS = ColorSlot(li);
314     assert(NewSS >= 0 && "Stack coloring failed?");
315     SlotMapping[SS] = NewSS;
316     RevMap[NewSS].push_back(SS);
317     SlotWeights[NewSS] += li->weight;
318     UsedColors.set(NewSS);
319     Changed |= (SS != NewSS);
320   }
321 
322   DEBUG(dbgs() << "\nSpill slots after coloring:\n");
323   for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
324     LiveInterval *li = SSIntervals[i];
325     int SS = TargetRegisterInfo::stackSlot2Index(li->reg);
326     li->weight = SlotWeights[SS];
327   }
328   // Sort them by new weight.
329   std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
330 
331 #ifndef NDEBUG
332   for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i)
333     DEBUG(SSIntervals[i]->dump());
334   DEBUG(dbgs() << '\n');
335 #endif
336 
337   if (!Changed)
338     return false;
339 
340   // Rewrite all MachineMemOperands.
341   for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) {
342     int NewFI = SlotMapping[SS];
343     if (NewFI == -1 || (NewFI == (int)SS))
344       continue;
345 
346     const PseudoSourceValue *NewSV = MF.getPSVManager().getFixedStack(NewFI);
347     SmallVectorImpl<MachineMemOperand *> &RefMMOs = SSRefs[SS];
348     for (unsigned i = 0, e = RefMMOs.size(); i != e; ++i)
349       RefMMOs[i]->setValue(NewSV);
350   }
351 
352   // Rewrite all MO_FrameIndex operands.  Look for dead stores.
353   for (MachineBasicBlock &MBB : MF) {
354     for (MachineInstr &MI : MBB)
355       RewriteInstruction(MI, SlotMapping, MF);
356     RemoveDeadStores(&MBB);
357   }
358 
359   // Delete unused stack slots.
360   while (NextColor != -1) {
361     DEBUG(dbgs() << "Removing unused stack object fi#" << NextColor << "\n");
362     MFI->RemoveStackObject(NextColor);
363     NextColor = AllColors.find_next(NextColor);
364   }
365 
366   return true;
367 }
368 
369 /// RewriteInstruction - Rewrite specified instruction by replacing references
370 /// to old frame index with new one.
371 void StackSlotColoring::RewriteInstruction(MachineInstr &MI,
372                                            SmallVectorImpl<int> &SlotMapping,
373                                            MachineFunction &MF) {
374   // Update the operands.
375   for (unsigned i = 0, ee = MI.getNumOperands(); i != ee; ++i) {
376     MachineOperand &MO = MI.getOperand(i);
377     if (!MO.isFI())
378       continue;
379     int OldFI = MO.getIndex();
380     if (OldFI < 0)
381       continue;
382     int NewFI = SlotMapping[OldFI];
383     if (NewFI == -1 || NewFI == OldFI)
384       continue;
385     MO.setIndex(NewFI);
386   }
387 
388   // The MachineMemOperands have already been updated.
389 }
390 
391 /// RemoveDeadStores - Scan through a basic block and look for loads followed
392 /// by stores.  If they're both using the same stack slot, then the store is
393 /// definitely dead.  This could obviously be much more aggressive (consider
394 /// pairs with instructions between them), but such extensions might have a
395 /// considerable compile time impact.
396 bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) {
397   // FIXME: This could be much more aggressive, but we need to investigate
398   // the compile time impact of doing so.
399   bool changed = false;
400 
401   SmallVector<MachineInstr*, 4> toErase;
402 
403   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
404        I != E; ++I) {
405     if (DCELimit != -1 && (int)NumDead >= DCELimit)
406       break;
407     int FirstSS, SecondSS;
408     if (TII->isStackSlotCopy(*I, FirstSS, SecondSS) && FirstSS == SecondSS &&
409         FirstSS != -1) {
410       ++NumDead;
411       changed = true;
412       toErase.push_back(&*I);
413       continue;
414     }
415 
416     MachineBasicBlock::iterator NextMI = std::next(I);
417     MachineBasicBlock::iterator ProbableLoadMI = I;
418 
419     unsigned LoadReg = 0;
420     unsigned StoreReg = 0;
421     if (!(LoadReg = TII->isLoadFromStackSlot(*I, FirstSS)))
422       continue;
423     // Skip the ...pseudo debugging... instructions between a load and store.
424     while ((NextMI != E) && NextMI->isDebugValue()) {
425       ++NextMI;
426       ++I;
427     }
428     if (NextMI == E) continue;
429     if (!(StoreReg = TII->isStoreToStackSlot(*NextMI, SecondSS)))
430       continue;
431     if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue;
432 
433     ++NumDead;
434     changed = true;
435 
436     if (NextMI->findRegisterUseOperandIdx(LoadReg, true, nullptr) != -1) {
437       ++NumDead;
438       toErase.push_back(&*ProbableLoadMI);
439     }
440 
441     toErase.push_back(&*NextMI);
442     ++I;
443   }
444 
445   for (SmallVectorImpl<MachineInstr *>::iterator I = toErase.begin(),
446        E = toErase.end(); I != E; ++I)
447     (*I)->eraseFromParent();
448 
449   return changed;
450 }
451 
452 bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
453   DEBUG({
454       dbgs() << "********** Stack Slot Coloring **********\n"
455              << "********** Function: " << MF.getName() << '\n';
456     });
457 
458   MFI = &MF.getFrameInfo();
459   TII = MF.getSubtarget().getInstrInfo();
460   LS = &getAnalysis<LiveStacks>();
461   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
462 
463   bool Changed = false;
464 
465   unsigned NumSlots = LS->getNumIntervals();
466   if (NumSlots == 0)
467     // Nothing to do!
468     return false;
469 
470   // If there are calls to setjmp or sigsetjmp, don't perform stack slot
471   // coloring. The stack could be modified before the longjmp is executed,
472   // resulting in the wrong value being used afterwards. (See
473   // <rdar://problem/8007500>.)
474   if (MF.exposesReturnsTwice())
475     return false;
476 
477   // Gather spill slot references
478   ScanForSpillSlotRefs(MF);
479   InitializeSlots();
480   Changed = ColorSlots(MF);
481 
482   NextColor = -1;
483   SSIntervals.clear();
484   for (unsigned i = 0, e = SSRefs.size(); i != e; ++i)
485     SSRefs[i].clear();
486   SSRefs.clear();
487   OrigAlignments.clear();
488   OrigSizes.clear();
489   AllColors.clear();
490   UsedColors.clear();
491   for (unsigned i = 0, e = Assignments.size(); i != e; ++i)
492     Assignments[i].clear();
493   Assignments.clear();
494 
495   return Changed;
496 }
497