Line data Source code
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. 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 : // Assignments - Color to intervals mapping.
95 : SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments;
96 :
97 : public:
98 : static char ID; // Pass identification
99 :
100 19896 : StackSlotColoring() : MachineFunctionPass(ID) {
101 19896 : initializeStackSlotColoringPass(*PassRegistry::getPassRegistry());
102 19896 : }
103 :
104 19738 : void getAnalysisUsage(AnalysisUsage &AU) const override {
105 19738 : AU.setPreservesCFG();
106 : AU.addRequired<SlotIndexes>();
107 : AU.addPreserved<SlotIndexes>();
108 : AU.addRequired<LiveStacks>();
109 : AU.addRequired<MachineBlockFrequencyInfo>();
110 : AU.addPreserved<MachineBlockFrequencyInfo>();
111 19738 : AU.addPreservedID(MachineDominatorsID);
112 19738 : MachineFunctionPass::getAnalysisUsage(AU);
113 19738 : }
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 31780 : INITIALIZE_PASS_BEGIN(StackSlotColoring, DEBUG_TYPE,
135 : "Stack Slot Coloring", false, false)
136 31780 : INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
137 31780 : INITIALIZE_PASS_DEPENDENCY(LiveStacks)
138 31780 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
139 105043 : 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 0 : bool operator()(LiveInterval* LHS, LiveInterval* RHS) const {
148 0 : 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 4167 : void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) {
157 8334 : 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 126693 : MBBI != E; ++MBBI) {
162 : MachineBasicBlock *MBB = &*MBBI;
163 : for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end();
164 1258490 : MII != EE; ++MII) {
165 : MachineInstr &MI = *MII;
166 6971274 : for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
167 5835310 : MachineOperand &MO = MI.getOperand(i);
168 5835310 : if (!MO.isFI())
169 : continue;
170 107527 : int FI = MO.getIndex();
171 107527 : if (FI < 0)
172 : continue;
173 102160 : if (!LS->hasInterval(FI))
174 : continue;
175 42271 : LiveInterval &li = LS->getInterval(FI);
176 42271 : if (!MI.isDebugValue())
177 40616 : li.weight += LiveIntervals::getSpillWeight(false, true, MBFI, MI);
178 : }
179 658320 : for (MachineInstr::mmo_iterator MMOI = MI.memoperands_begin(),
180 : EE = MI.memoperands_end();
181 1794284 : MMOI != EE; ++MMOI) {
182 658320 : MachineMemOperand *MMO = *MMOI;
183 606449 : if (const FixedStackPseudoSourceValue *FSV =
184 : dyn_cast_or_null<FixedStackPseudoSourceValue>(
185 : MMO->getPseudoValue())) {
186 50506 : int FI = FSV->getFrameIndex();
187 50506 : if (FI >= 0)
188 90946 : SSRefs[FI].push_back(MMO);
189 : }
190 : }
191 : }
192 : }
193 4167 : }
194 :
195 : /// InitializeSlots - Process all spill stack slot liveintervals and add them
196 : /// to a sorted (by weight) list.
197 4167 : void StackSlotColoring::InitializeSlots() {
198 4167 : int LastFI = MFI->getObjectIndexEnd();
199 :
200 : // There is always at least one stack ID.
201 4167 : AllColors.resize(1);
202 4167 : UsedColors.resize(1);
203 :
204 4167 : OrigAlignments.resize(LastFI);
205 4167 : OrigSizes.resize(LastFI);
206 4167 : AllColors[0].resize(LastFI);
207 4167 : UsedColors[0].resize(LastFI);
208 4167 : Assignments.resize(LastFI);
209 :
210 : using Pair = std::iterator_traits<LiveStacks::iterator>::value_type;
211 :
212 : SmallVector<Pair *, 16> Intervals;
213 :
214 4167 : Intervals.reserve(LS->getNumIntervals());
215 18511 : for (auto &I : *LS)
216 14344 : Intervals.push_back(&I);
217 : llvm::sort(Intervals,
218 0 : [](Pair *LHS, Pair *RHS) { return LHS->first < RHS->first; });
219 :
220 : // Gather all spill slots into a list.
221 : LLVM_DEBUG(dbgs() << "Spill slot intervals:\n");
222 18511 : for (auto *I : Intervals) {
223 14344 : LiveInterval &li = I->second;
224 : LLVM_DEBUG(li.dump());
225 14344 : int FI = TargetRegisterInfo::stackSlot2Index(li.reg);
226 28688 : if (MFI->isDeadObjectIndex(FI))
227 : continue;
228 :
229 14344 : SSIntervals.push_back(&li);
230 14344 : OrigAlignments[FI] = MFI->getObjectAlignment(FI);
231 14344 : OrigSizes[FI] = MFI->getObjectSize(FI);
232 :
233 14344 : auto StackID = MFI->getStackID(FI);
234 14344 : if (StackID != 0) {
235 107 : AllColors.resize(StackID + 1);
236 107 : UsedColors.resize(StackID + 1);
237 214 : AllColors[StackID].resize(LastFI);
238 107 : UsedColors[StackID].resize(LastFI);
239 : }
240 :
241 14344 : AllColors[StackID].set(FI);
242 : }
243 : LLVM_DEBUG(dbgs() << '\n');
244 :
245 : // Sort them by weight.
246 4167 : std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
247 :
248 8334 : NextColors.resize(AllColors.size());
249 :
250 : // Get first "color".
251 8348 : for (unsigned I = 0, E = AllColors.size(); I != E; ++I)
252 8362 : NextColors[I] = AllColors[I].find_first();
253 4167 : }
254 :
255 : /// OverlapWithAssignments - Return true if LiveInterval overlaps with any
256 : /// LiveIntervals that have already been assigned to the specified color.
257 : bool
258 331492 : StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const {
259 331492 : const SmallVectorImpl<LiveInterval *> &OtherLIs = Assignments[Color];
260 358888 : for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) {
261 356920 : LiveInterval *OtherLI = OtherLIs[i];
262 713840 : if (OtherLI->overlaps(*li))
263 : return true;
264 : }
265 : return false;
266 : }
267 :
268 : /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.
269 14344 : int StackSlotColoring::ColorSlot(LiveInterval *li) {
270 : int Color = -1;
271 : bool Share = false;
272 14344 : int FI = TargetRegisterInfo::stackSlot2Index(li->reg);
273 14344 : uint8_t StackID = MFI->getStackID(FI);
274 :
275 14344 : if (!DisableSharing) {
276 :
277 : // Check if it's possible to reuse any of the used colors.
278 14340 : Color = UsedColors[StackID].find_first();
279 343864 : while (Color != -1) {
280 331492 : if (!OverlapWithAssignments(li, Color)) {
281 : Share = true;
282 : ++NumEliminated;
283 : break;
284 : }
285 329524 : Color = UsedColors[StackID].find_next(Color);
286 : }
287 : }
288 :
289 14340 : if (Color != -1 && MFI->getStackID(Color) != MFI->getStackID(FI)) {
290 : LLVM_DEBUG(dbgs() << "cannot share FIs with different stack IDs\n");
291 : Share = false;
292 : }
293 :
294 : // Assign it to the first available color (assumed to be the best) if it's
295 : // not possible to share a used color with other objects.
296 14344 : if (!Share) {
297 : assert(NextColors[StackID] != -1 && "No more spill slots?");
298 24752 : Color = NextColors[StackID];
299 12376 : UsedColors[StackID].set(Color);
300 12376 : NextColors[StackID] = AllColors[StackID].find_next(NextColors[StackID]);
301 : }
302 :
303 : assert(MFI->getStackID(Color) == MFI->getStackID(FI));
304 :
305 : // Record the assignment.
306 28688 : Assignments[Color].push_back(li);
307 : LLVM_DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n");
308 :
309 : // Change size and alignment of the allocated slot. If there are multiple
310 : // objects sharing the same slot, then make sure the size and alignment
311 : // are large enough for all.
312 14344 : unsigned Align = OrigAlignments[FI];
313 14344 : if (!Share || Align > MFI->getObjectAlignment(Color))
314 12419 : MFI->setObjectAlignment(Color, Align);
315 14344 : int64_t Size = OrigSizes[FI];
316 14344 : if (!Share || Size > MFI->getObjectSize(Color))
317 12425 : MFI->setObjectSize(Color, Size);
318 14344 : return Color;
319 : }
320 :
321 : /// Colorslots - Color all spill stack slots and rewrite all frameindex machine
322 : /// operands in the function.
323 4167 : bool StackSlotColoring::ColorSlots(MachineFunction &MF) {
324 4167 : unsigned NumObjs = MFI->getObjectIndexEnd();
325 4167 : SmallVector<int, 16> SlotMapping(NumObjs, -1);
326 4167 : SmallVector<float, 16> SlotWeights(NumObjs, 0.0);
327 4167 : SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs);
328 4167 : BitVector UsedColors(NumObjs);
329 :
330 : LLVM_DEBUG(dbgs() << "Color spill slot intervals:\n");
331 : bool Changed = false;
332 22678 : for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
333 14344 : LiveInterval *li = SSIntervals[i];
334 14344 : int SS = TargetRegisterInfo::stackSlot2Index(li->reg);
335 14344 : int NewSS = ColorSlot(li);
336 : assert(NewSS >= 0 && "Stack coloring failed?");
337 14344 : SlotMapping[SS] = NewSS;
338 28688 : RevMap[NewSS].push_back(SS);
339 14344 : SlotWeights[NewSS] += li->weight;
340 14344 : UsedColors.set(NewSS);
341 14344 : Changed |= (SS != NewSS);
342 : }
343 :
344 : LLVM_DEBUG(dbgs() << "\nSpill slots after coloring:\n");
345 22678 : for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
346 14344 : LiveInterval *li = SSIntervals[i];
347 14344 : int SS = TargetRegisterInfo::stackSlot2Index(li->reg);
348 28688 : li->weight = SlotWeights[SS];
349 : }
350 : // Sort them by new weight.
351 4167 : std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
352 :
353 : #ifndef NDEBUG
354 : for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i)
355 : LLVM_DEBUG(SSIntervals[i]->dump());
356 : LLVM_DEBUG(dbgs() << '\n');
357 : #endif
358 :
359 4167 : if (!Changed)
360 : return false;
361 :
362 : // Rewrite all MachineMemOperands.
363 16200 : for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) {
364 15319 : int NewFI = SlotMapping[SS];
365 15319 : if (NewFI == -1 || (NewFI == (int)SS))
366 : continue;
367 :
368 6361 : const PseudoSourceValue *NewSV = MF.getPSVManager().getFixedStack(NewFI);
369 : SmallVectorImpl<MachineMemOperand *> &RefMMOs = SSRefs[SS];
370 27661 : for (unsigned i = 0, e = RefMMOs.size(); i != e; ++i)
371 42600 : RefMMOs[i]->setValue(NewSV);
372 : }
373 :
374 : // Rewrite all MO_FrameIndex operands. Look for dead stores.
375 78630 : for (MachineBasicBlock &MBB : MF) {
376 799220 : for (MachineInstr &MI : MBB)
377 721471 : RewriteInstruction(MI, SlotMapping, MF);
378 77749 : RemoveDeadStores(&MBB);
379 : }
380 :
381 : // Delete unused stack slots.
382 1766 : for (int StackID = 0, E = AllColors.size(); StackID != E; ++StackID) {
383 1770 : int NextColor = NextColors[StackID];
384 2853 : while (NextColor != -1) {
385 : LLVM_DEBUG(dbgs() << "Removing unused stack object fi#" << NextColor << "\n");
386 1968 : MFI->RemoveStackObject(NextColor);
387 : NextColor = AllColors[StackID].find_next(NextColor);
388 : }
389 : }
390 :
391 : return true;
392 : }
393 :
394 : /// RewriteInstruction - Rewrite specified instruction by replacing references
395 : /// to old frame index with new one.
396 0 : void StackSlotColoring::RewriteInstruction(MachineInstr &MI,
397 : SmallVectorImpl<int> &SlotMapping,
398 : MachineFunction &MF) {
399 : // Update the operands.
400 0 : for (unsigned i = 0, ee = MI.getNumOperands(); i != ee; ++i) {
401 0 : MachineOperand &MO = MI.getOperand(i);
402 0 : if (!MO.isFI())
403 0 : continue;
404 0 : int OldFI = MO.getIndex();
405 0 : if (OldFI < 0)
406 0 : continue;
407 0 : int NewFI = SlotMapping[OldFI];
408 0 : if (NewFI == -1 || NewFI == OldFI)
409 0 : continue;
410 :
411 : assert(MFI->getStackID(OldFI) == MFI->getStackID(NewFI));
412 : MO.setIndex(NewFI);
413 : }
414 :
415 : // The MachineMemOperands have already been updated.
416 0 : }
417 :
418 : /// RemoveDeadStores - Scan through a basic block and look for loads followed
419 : /// by stores. If they're both using the same stack slot, then the store is
420 : /// definitely dead. This could obviously be much more aggressive (consider
421 : /// pairs with instructions between them), but such extensions might have a
422 : /// considerable compile time impact.
423 0 : bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) {
424 : // FIXME: This could be much more aggressive, but we need to investigate
425 : // the compile time impact of doing so.
426 : bool changed = false;
427 :
428 : SmallVector<MachineInstr*, 4> toErase;
429 :
430 : for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
431 0 : I != E; ++I) {
432 0 : if (DCELimit != -1 && (int)NumDead >= DCELimit)
433 : break;
434 : int FirstSS, SecondSS;
435 0 : if (TII->isStackSlotCopy(*I, FirstSS, SecondSS) && FirstSS == SecondSS &&
436 : FirstSS != -1) {
437 : ++NumDead;
438 : changed = true;
439 0 : toErase.push_back(&*I);
440 0 : continue;
441 : }
442 :
443 0 : MachineBasicBlock::iterator NextMI = std::next(I);
444 : MachineBasicBlock::iterator ProbableLoadMI = I;
445 :
446 : unsigned LoadReg = 0;
447 : unsigned StoreReg = 0;
448 0 : unsigned LoadSize = 0;
449 0 : unsigned StoreSize = 0;
450 0 : if (!(LoadReg = TII->isLoadFromStackSlot(*I, FirstSS, LoadSize)))
451 0 : continue;
452 : // Skip the ...pseudo debugging... instructions between a load and store.
453 0 : while ((NextMI != E) && NextMI->isDebugInstr()) {
454 : ++NextMI;
455 : ++I;
456 : }
457 0 : if (NextMI == E) continue;
458 0 : if (!(StoreReg = TII->isStoreToStackSlot(*NextMI, SecondSS, StoreSize)))
459 0 : continue;
460 0 : if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1 ||
461 0 : LoadSize != StoreSize)
462 0 : continue;
463 :
464 : ++NumDead;
465 : changed = true;
466 :
467 0 : if (NextMI->findRegisterUseOperandIdx(LoadReg, true, nullptr) != -1) {
468 : ++NumDead;
469 0 : toErase.push_back(&*ProbableLoadMI);
470 : }
471 :
472 0 : toErase.push_back(&*NextMI);
473 : ++I;
474 : }
475 :
476 0 : for (SmallVectorImpl<MachineInstr *>::iterator I = toErase.begin(),
477 0 : E = toErase.end(); I != E; ++I)
478 0 : (*I)->eraseFromParent();
479 :
480 0 : return changed;
481 : }
482 :
483 194994 : bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
484 : LLVM_DEBUG({
485 : dbgs() << "********** Stack Slot Coloring **********\n"
486 : << "********** Function: " << MF.getName() << '\n';
487 : });
488 :
489 194994 : if (skipFunction(MF.getFunction()))
490 : return false;
491 :
492 194829 : MFI = &MF.getFrameInfo();
493 194829 : TII = MF.getSubtarget().getInstrInfo();
494 194829 : LS = &getAnalysis<LiveStacks>();
495 194829 : MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
496 :
497 : bool Changed = false;
498 :
499 194829 : unsigned NumSlots = LS->getNumIntervals();
500 194829 : if (NumSlots == 0)
501 : // Nothing to do!
502 : return false;
503 :
504 : // If there are calls to setjmp or sigsetjmp, don't perform stack slot
505 : // coloring. The stack could be modified before the longjmp is executed,
506 : // resulting in the wrong value being used afterwards. (See
507 : // <rdar://problem/8007500>.)
508 4173 : if (MF.exposesReturnsTwice())
509 : return false;
510 :
511 : // Gather spill slot references
512 4167 : ScanForSpillSlotRefs(MF);
513 4167 : InitializeSlots();
514 4167 : Changed = ColorSlots(MF);
515 :
516 8348 : for (int &Next : NextColors)
517 4181 : Next = -1;
518 :
519 : SSIntervals.clear();
520 30947 : for (unsigned i = 0, e = SSRefs.size(); i != e; ++i)
521 26780 : SSRefs[i].clear();
522 4167 : SSRefs.clear();
523 : OrigAlignments.clear();
524 : OrigSizes.clear();
525 4167 : AllColors.clear();
526 4167 : UsedColors.clear();
527 30947 : for (unsigned i = 0, e = Assignments.size(); i != e; ++i)
528 26780 : Assignments[i].clear();
529 4167 : Assignments.clear();
530 :
531 4167 : return Changed;
532 : }
|
