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 #define DEBUG_TYPE "stackcoloring"
15 #include "VirtRegMap.h"
16 #include "llvm/Function.h"
17 #include "llvm/Module.h"
18 #include "llvm/CodeGen/Passes.h"
19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
20 #include "llvm/CodeGen/LiveStackAnalysis.h"
21 #include "llvm/CodeGen/MachineFrameInfo.h"
22 #include "llvm/CodeGen/MachineInstrBuilder.h"
23 #include "llvm/CodeGen/MachineLoopInfo.h"
24 #include "llvm/CodeGen/MachineMemOperand.h"
25 #include "llvm/CodeGen/MachineRegisterInfo.h"
26 #include "llvm/CodeGen/PseudoSourceValue.h"
27 #include "llvm/Support/CommandLine.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Target/TargetInstrInfo.h"
30 #include "llvm/Target/TargetMachine.h"
31 #include "llvm/ADT/BitVector.h"
32 #include "llvm/ADT/SmallSet.h"
33 #include "llvm/ADT/SmallVector.h"
34 #include "llvm/ADT/Statistic.h"
35 #include <vector>
36 using namespace llvm;
37 
38 static cl::opt<bool>
39 DisableSharing("no-stack-slot-sharing",
40              cl::init(false), cl::Hidden,
41              cl::desc("Suppress slot sharing during stack coloring"));
42 
43 static cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden);
44 
45 STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring");
46 STATISTIC(NumDead,       "Number of trivially dead stack accesses eliminated");
47 
48 namespace {
49   class StackSlotColoring : public MachineFunctionPass {
50     bool ColorWithRegs;
51     LiveStacks* LS;
52     MachineFrameInfo *MFI;
53     const TargetInstrInfo  *TII;
54     const MachineLoopInfo *loopInfo;
55 
56     // SSIntervals - Spill slot intervals.
57     std::vector<LiveInterval*> SSIntervals;
58 
59     // SSRefs - Keep a list of frame index references for each spill slot.
60     SmallVector<SmallVector<MachineInstr*, 8>, 16> SSRefs;
61 
62     // OrigAlignments - Alignments of stack objects before coloring.
63     SmallVector<unsigned, 16> OrigAlignments;
64 
65     // OrigSizes - Sizess of stack objects before coloring.
66     SmallVector<unsigned, 16> OrigSizes;
67 
68     // AllColors - If index is set, it's a spill slot, i.e. color.
69     // FIXME: This assumes PEI locate spill slot with smaller indices
70     // closest to stack pointer / frame pointer. Therefore, smaller
71     // index == better color.
72     BitVector AllColors;
73 
74     // NextColor - Next "color" that's not yet used.
75     int NextColor;
76 
77     // UsedColors - "Colors" that have been assigned.
78     BitVector UsedColors;
79 
80     // Assignments - Color to intervals mapping.
81     SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments;
82 
83   public:
84     static char ID; // Pass identification
85     StackSlotColoring() :
86       MachineFunctionPass(ID), ColorWithRegs(false), NextColor(-1) {
87         initializeStackSlotColoringPass(*PassRegistry::getPassRegistry());
88       }
89     StackSlotColoring(bool RegColor) :
90       MachineFunctionPass(ID), ColorWithRegs(RegColor), NextColor(-1) {
91         initializeStackSlotColoringPass(*PassRegistry::getPassRegistry());
92       }
93 
94     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
95       AU.setPreservesCFG();
96       AU.addRequired<SlotIndexes>();
97       AU.addPreserved<SlotIndexes>();
98       AU.addRequired<LiveStacks>();
99       AU.addRequired<VirtRegMap>();
100       AU.addPreserved<VirtRegMap>();
101       AU.addRequired<MachineLoopInfo>();
102       AU.addPreserved<MachineLoopInfo>();
103       AU.addPreservedID(MachineDominatorsID);
104       MachineFunctionPass::getAnalysisUsage(AU);
105     }
106 
107     virtual bool runOnMachineFunction(MachineFunction &MF);
108     virtual const char* getPassName() const {
109       return "Stack Slot Coloring";
110     }
111 
112   private:
113     void InitializeSlots();
114     void ScanForSpillSlotRefs(MachineFunction &MF);
115     bool OverlapWithAssignments(LiveInterval *li, int Color) const;
116     int ColorSlot(LiveInterval *li);
117     bool ColorSlots(MachineFunction &MF);
118     void RewriteInstruction(MachineInstr *MI, int OldFI, int NewFI,
119                             MachineFunction &MF);
120     bool RemoveDeadStores(MachineBasicBlock* MBB);
121   };
122 } // end anonymous namespace
123 
124 char StackSlotColoring::ID = 0;
125 
126 INITIALIZE_PASS_BEGIN(StackSlotColoring, "stack-slot-coloring",
127                 "Stack Slot Coloring", false, false)
128 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
129 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
130 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
131 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
132 INITIALIZE_PASS_END(StackSlotColoring, "stack-slot-coloring",
133                 "Stack Slot Coloring", false, false)
134 
135 FunctionPass *llvm::createStackSlotColoringPass(bool RegColor) {
136   return new StackSlotColoring(RegColor);
137 }
138 
139 namespace {
140   // IntervalSorter - Comparison predicate that sort live intervals by
141   // their weight.
142   struct IntervalSorter {
143     bool operator()(LiveInterval* LHS, LiveInterval* RHS) const {
144       return LHS->weight > RHS->weight;
145     }
146   };
147 }
148 
149 /// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot
150 /// references and update spill slot weights.
151 void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) {
152   SSRefs.resize(MFI->getObjectIndexEnd());
153 
154   // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands.
155   for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
156        MBBI != E; ++MBBI) {
157     MachineBasicBlock *MBB = &*MBBI;
158     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
159     for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end();
160          MII != EE; ++MII) {
161       MachineInstr *MI = &*MII;
162       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
163         MachineOperand &MO = MI->getOperand(i);
164         if (!MO.isFI())
165           continue;
166         int FI = MO.getIndex();
167         if (FI < 0)
168           continue;
169         if (!LS->hasInterval(FI))
170           continue;
171         LiveInterval &li = LS->getInterval(FI);
172         if (!MI->isDebugValue())
173           li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth);
174         SSRefs[FI].push_back(MI);
175       }
176     }
177   }
178 }
179 
180 /// InitializeSlots - Process all spill stack slot liveintervals and add them
181 /// to a sorted (by weight) list.
182 void StackSlotColoring::InitializeSlots() {
183   int LastFI = MFI->getObjectIndexEnd();
184   OrigAlignments.resize(LastFI);
185   OrigSizes.resize(LastFI);
186   AllColors.resize(LastFI);
187   UsedColors.resize(LastFI);
188   Assignments.resize(LastFI);
189 
190   // Gather all spill slots into a list.
191   DEBUG(dbgs() << "Spill slot intervals:\n");
192   for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) {
193     LiveInterval &li = i->second;
194     DEBUG(li.dump());
195     int FI = TargetRegisterInfo::stackSlot2Index(li.reg);
196     if (MFI->isDeadObjectIndex(FI))
197       continue;
198     SSIntervals.push_back(&li);
199     OrigAlignments[FI] = MFI->getObjectAlignment(FI);
200     OrigSizes[FI]      = MFI->getObjectSize(FI);
201     AllColors.set(FI);
202   }
203   DEBUG(dbgs() << '\n');
204 
205   // Sort them by weight.
206   std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
207 
208   // Get first "color".
209   NextColor = AllColors.find_first();
210 }
211 
212 /// OverlapWithAssignments - Return true if LiveInterval overlaps with any
213 /// LiveIntervals that have already been assigned to the specified color.
214 bool
215 StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const {
216   const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color];
217   for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) {
218     LiveInterval *OtherLI = OtherLIs[i];
219     if (OtherLI->overlaps(*li))
220       return true;
221   }
222   return false;
223 }
224 
225 /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.
226 ///
227 int StackSlotColoring::ColorSlot(LiveInterval *li) {
228   int Color = -1;
229   bool Share = false;
230   if (!DisableSharing) {
231     // Check if it's possible to reuse any of the used colors.
232     Color = UsedColors.find_first();
233     while (Color != -1) {
234       if (!OverlapWithAssignments(li, Color)) {
235         Share = true;
236         ++NumEliminated;
237         break;
238       }
239       Color = UsedColors.find_next(Color);
240     }
241   }
242 
243   // Assign it to the first available color (assumed to be the best) if it's
244   // not possible to share a used color with other objects.
245   if (!Share) {
246     assert(NextColor != -1 && "No more spill slots?");
247     Color = NextColor;
248     UsedColors.set(Color);
249     NextColor = AllColors.find_next(NextColor);
250   }
251 
252   // Record the assignment.
253   Assignments[Color].push_back(li);
254   int FI = TargetRegisterInfo::stackSlot2Index(li->reg);
255   DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n");
256 
257   // Change size and alignment of the allocated slot. If there are multiple
258   // objects sharing the same slot, then make sure the size and alignment
259   // are large enough for all.
260   unsigned Align = OrigAlignments[FI];
261   if (!Share || Align > MFI->getObjectAlignment(Color))
262     MFI->setObjectAlignment(Color, Align);
263   int64_t Size = OrigSizes[FI];
264   if (!Share || Size > MFI->getObjectSize(Color))
265     MFI->setObjectSize(Color, Size);
266   return Color;
267 }
268 
269 /// Colorslots - Color all spill stack slots and rewrite all frameindex machine
270 /// operands in the function.
271 bool StackSlotColoring::ColorSlots(MachineFunction &MF) {
272   unsigned NumObjs = MFI->getObjectIndexEnd();
273   SmallVector<int, 16> SlotMapping(NumObjs, -1);
274   SmallVector<float, 16> SlotWeights(NumObjs, 0.0);
275   SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs);
276   BitVector UsedColors(NumObjs);
277 
278   DEBUG(dbgs() << "Color spill slot intervals:\n");
279   bool Changed = false;
280   for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
281     LiveInterval *li = SSIntervals[i];
282     int SS = TargetRegisterInfo::stackSlot2Index(li->reg);
283     int NewSS = ColorSlot(li);
284     assert(NewSS >= 0 && "Stack coloring failed?");
285     SlotMapping[SS] = NewSS;
286     RevMap[NewSS].push_back(SS);
287     SlotWeights[NewSS] += li->weight;
288     UsedColors.set(NewSS);
289     Changed |= (SS != NewSS);
290   }
291 
292   DEBUG(dbgs() << "\nSpill slots after coloring:\n");
293   for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
294     LiveInterval *li = SSIntervals[i];
295     int SS = TargetRegisterInfo::stackSlot2Index(li->reg);
296     li->weight = SlotWeights[SS];
297   }
298   // Sort them by new weight.
299   std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
300 
301 #ifndef NDEBUG
302   for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i)
303     DEBUG(SSIntervals[i]->dump());
304   DEBUG(dbgs() << '\n');
305 #endif
306 
307   if (!Changed)
308     return false;
309 
310   // Rewrite all MO_FrameIndex operands.
311   SmallVector<SmallSet<unsigned, 4>, 4> NewDefs(MF.getNumBlockIDs());
312   for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) {
313     int NewFI = SlotMapping[SS];
314     if (NewFI == -1 || (NewFI == (int)SS))
315       continue;
316 
317     SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS];
318     for (unsigned i = 0, e = RefMIs.size(); i != e; ++i)
319       RewriteInstruction(RefMIs[i], SS, NewFI, MF);
320   }
321 
322   // Delete unused stack slots.
323   while (NextColor != -1) {
324     DEBUG(dbgs() << "Removing unused stack object fi#" << NextColor << "\n");
325     MFI->RemoveStackObject(NextColor);
326     NextColor = AllColors.find_next(NextColor);
327   }
328 
329   return true;
330 }
331 
332 /// RewriteInstruction - Rewrite specified instruction by replacing references
333 /// to old frame index with new one.
334 void StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI,
335                                            int NewFI, MachineFunction &MF) {
336   // Update the operands.
337   for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) {
338     MachineOperand &MO = MI->getOperand(i);
339     if (!MO.isFI())
340       continue;
341     int FI = MO.getIndex();
342     if (FI != OldFI)
343       continue;
344     MO.setIndex(NewFI);
345   }
346 
347   // Update the memory references. This changes the MachineMemOperands
348   // directly. They may be in use by multiple instructions, however all
349   // instructions using OldFI are being rewritten to use NewFI.
350   const Value *OldSV = PseudoSourceValue::getFixedStack(OldFI);
351   const Value *NewSV = PseudoSourceValue::getFixedStack(NewFI);
352   for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
353        E = MI->memoperands_end(); I != E; ++I)
354     if ((*I)->getValue() == OldSV)
355       (*I)->setValue(NewSV);
356 }
357 
358 
359 /// RemoveDeadStores - Scan through a basic block and look for loads followed
360 /// by stores.  If they're both using the same stack slot, then the store is
361 /// definitely dead.  This could obviously be much more aggressive (consider
362 /// pairs with instructions between them), but such extensions might have a
363 /// considerable compile time impact.
364 bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) {
365   // FIXME: This could be much more aggressive, but we need to investigate
366   // the compile time impact of doing so.
367   bool changed = false;
368 
369   SmallVector<MachineInstr*, 4> toErase;
370 
371   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
372        I != E; ++I) {
373     if (DCELimit != -1 && (int)NumDead >= DCELimit)
374       break;
375 
376     MachineBasicBlock::iterator NextMI = llvm::next(I);
377     if (NextMI == MBB->end()) continue;
378 
379     int FirstSS, SecondSS;
380     unsigned LoadReg = 0;
381     unsigned StoreReg = 0;
382     if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue;
383     if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue;
384     if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue;
385 
386     ++NumDead;
387     changed = true;
388 
389     if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) {
390       ++NumDead;
391       toErase.push_back(I);
392     }
393 
394     toErase.push_back(NextMI);
395     ++I;
396   }
397 
398   for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(),
399        E = toErase.end(); I != E; ++I)
400     (*I)->eraseFromParent();
401 
402   return changed;
403 }
404 
405 
406 bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
407   DEBUG({
408       dbgs() << "********** Stack Slot Coloring **********\n"
409              << "********** Function: "
410              << MF.getFunction()->getName() << '\n';
411     });
412 
413   MFI = MF.getFrameInfo();
414   TII = MF.getTarget().getInstrInfo();
415   LS = &getAnalysis<LiveStacks>();
416   loopInfo = &getAnalysis<MachineLoopInfo>();
417 
418   bool Changed = false;
419 
420   unsigned NumSlots = LS->getNumIntervals();
421   if (NumSlots == 0)
422     // Nothing to do!
423     return false;
424 
425   // If there are calls to setjmp or sigsetjmp, don't perform stack slot
426   // coloring. The stack could be modified before the longjmp is executed,
427   // resulting in the wrong value being used afterwards. (See
428   // <rdar://problem/8007500>.)
429   if (MF.callsSetJmp())
430     return false;
431 
432   // Gather spill slot references
433   ScanForSpillSlotRefs(MF);
434   InitializeSlots();
435   Changed = ColorSlots(MF);
436 
437   NextColor = -1;
438   SSIntervals.clear();
439   for (unsigned i = 0, e = SSRefs.size(); i != e; ++i)
440     SSRefs[i].clear();
441   SSRefs.clear();
442   OrigAlignments.clear();
443   OrigSizes.clear();
444   AllColors.clear();
445   UsedColors.clear();
446   for (unsigned i = 0, e = Assignments.size(); i != e; ++i)
447     Assignments[i].clear();
448   Assignments.clear();
449 
450   if (Changed) {
451     for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
452       Changed |= RemoveDeadStores(I);
453   }
454 
455   return Changed;
456 }
457