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