1 //===-- StackSlotColoring.cpp - Stack slot coloring pass. -----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the stack slot coloring pass.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "stackcoloring"
15 #include "VirtRegMap.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/MachineLoopInfo.h"
21 #include "llvm/CodeGen/MachineRegisterInfo.h"
22 #include "llvm/CodeGen/PseudoSourceValue.h"
23 #include "llvm/Support/CommandLine.h"
24 #include "llvm/Support/Compiler.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Target/TargetInstrInfo.h"
27 #include "llvm/Target/TargetMachine.h"
28 #include "llvm/ADT/BitVector.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/Statistic.h"
35 DisableSharing("no-stack-slot-sharing",
36 cl::init(false), cl::Hidden,
37 cl::desc("Suppress slot sharing during stack coloring"));
40 ColorWithRegs("color-ss-with-regs",
41 cl::init(false), cl::Hidden,
42 cl::desc("Color stack slots with free registers"));
45 static cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden);
47 STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring");
48 STATISTIC(NumRegRepl, "Number of stack slot refs replaced with reg refs");
49 STATISTIC(NumLoadElim, "Number of load eliminated");
50 STATISTIC(NumStoreElim, "Number of stores eliminated");
51 STATISTIC(NumDead, "Number of trivially dead stack accesses eliminated");
54 class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass {
57 MachineFrameInfo *MFI;
58 MachineRegisterInfo *MRI;
59 const TargetInstrInfo *TII;
60 const TargetRegisterInfo *TRI;
61 const MachineLoopInfo *loopInfo;
63 // SSIntervals - Spill slot intervals.
64 std::vector<LiveInterval*> SSIntervals;
66 // SSRefs - Keep a list of frame index references for each spill slot.
67 SmallVector<SmallVector<MachineInstr*, 8>, 16> SSRefs;
69 // OrigAlignments - Alignments of stack objects before coloring.
70 SmallVector<unsigned, 16> OrigAlignments;
72 // OrigSizes - Sizess of stack objects before coloring.
73 SmallVector<unsigned, 16> OrigSizes;
75 // AllColors - If index is set, it's a spill slot, i.e. color.
76 // FIXME: This assumes PEI locate spill slot with smaller indices
77 // closest to stack pointer / frame pointer. Therefore, smaller
78 // index == better color.
81 // NextColor - Next "color" that's not yet used.
84 // UsedColors - "Colors" that have been assigned.
87 // Assignments - Color to intervals mapping.
88 SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments;
91 static char ID; // Pass identification
92 StackSlotColoring() : MachineFunctionPass(&ID), NextColor(-1) {}
94 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
95 AU.addRequired<LiveStacks>();
96 AU.addRequired<VirtRegMap>();
97 AU.addPreserved<VirtRegMap>();
98 AU.addRequired<MachineLoopInfo>();
99 AU.addPreserved<MachineLoopInfo>();
100 AU.addPreservedID(MachineDominatorsID);
101 MachineFunctionPass::getAnalysisUsage(AU);
104 virtual bool runOnMachineFunction(MachineFunction &MF);
105 virtual const char* getPassName() const {
106 return "Stack Slot Coloring";
110 void InitializeSlots();
111 void ScanForSpillSlotRefs(MachineFunction &MF);
112 bool OverlapWithAssignments(LiveInterval *li, int Color) const;
113 int ColorSlot(LiveInterval *li);
114 bool ColorSlots(MachineFunction &MF);
115 bool ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping,
116 SmallVector<SmallVector<int, 4>, 16> &RevMap,
117 BitVector &SlotIsReg);
118 void RewriteInstruction(MachineInstr *MI, int OldFI, int NewFI,
119 MachineFunction &MF);
120 bool PropagateBackward(MachineBasicBlock::iterator MII,
121 MachineBasicBlock *MBB,
122 unsigned OldReg, unsigned NewReg);
123 bool PropagateForward(MachineBasicBlock::iterator MII,
124 MachineBasicBlock *MBB,
125 unsigned OldReg, unsigned NewReg);
126 void UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI,
127 unsigned Reg, const TargetRegisterClass *RC,
128 MachineFunction &MF);
129 bool AllMemRefsCanBeUnfolded(int SS);
130 bool RemoveDeadStores(MachineBasicBlock* MBB);
132 } // end anonymous namespace
134 char StackSlotColoring::ID = 0;
136 static RegisterPass<StackSlotColoring>
137 X("stack-slot-coloring", "Stack Slot Coloring");
139 FunctionPass *llvm::createStackSlotColoringPass() {
140 return new StackSlotColoring();
144 // IntervalSorter - Comparison predicate that sort live intervals by
146 struct IntervalSorter {
147 bool operator()(LiveInterval* LHS, LiveInterval* RHS) const {
148 return LHS->weight > RHS->weight;
153 /// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot
154 /// references and update spill slot weights.
155 void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) {
156 SSRefs.resize(MFI->getObjectIndexEnd());
158 // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands.
159 for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
161 MachineBasicBlock *MBB = &*MBBI;
162 unsigned loopDepth = loopInfo->getLoopDepth(MBB);
163 for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end();
165 MachineInstr *MI = &*MII;
166 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
167 MachineOperand &MO = MI->getOperand(i);
170 int FI = MO.getIndex();
173 if (!LS->hasInterval(FI))
175 LiveInterval &li = LS->getInterval(FI);
176 li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth);
177 SSRefs[FI].push_back(MI);
183 /// InitializeSlots - Process all spill stack slot liveintervals and add them
184 /// to a sorted (by weight) list.
185 void StackSlotColoring::InitializeSlots() {
186 int LastFI = MFI->getObjectIndexEnd();
187 OrigAlignments.resize(LastFI);
188 OrigSizes.resize(LastFI);
189 AllColors.resize(LastFI);
190 UsedColors.resize(LastFI);
191 Assignments.resize(LastFI);
193 // Gather all spill slots into a list.
194 DOUT << "Spill slot intervals:\n";
195 for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) {
196 LiveInterval &li = i->second;
198 int FI = li.getStackSlotIndex();
199 if (MFI->isDeadObjectIndex(FI))
201 SSIntervals.push_back(&li);
202 OrigAlignments[FI] = MFI->getObjectAlignment(FI);
203 OrigSizes[FI] = MFI->getObjectSize(FI);
208 // Sort them by weight.
209 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
211 // Get first "color".
212 NextColor = AllColors.find_first();
215 /// OverlapWithAssignments - Return true if LiveInterval overlaps with any
216 /// LiveIntervals that have already been assigned to the specified color.
218 StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const {
219 const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color];
220 for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) {
221 LiveInterval *OtherLI = OtherLIs[i];
222 if (OtherLI->overlaps(*li))
228 /// ColorSlotsWithFreeRegs - If there are any free registers available, try
229 /// replacing spill slots references with registers instead.
231 StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping,
232 SmallVector<SmallVector<int, 4>, 16> &RevMap,
233 BitVector &SlotIsReg) {
234 if (!ColorWithRegs || !VRM->HasUnusedRegisters())
237 bool Changed = false;
238 DOUT << "Assigning unused registers to spill slots:\n";
239 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
240 LiveInterval *li = SSIntervals[i];
241 int SS = li->getStackSlotIndex();
245 // These slots allow to share the same registers.
246 bool AllColored = true;
247 SmallVector<unsigned, 4> ColoredRegs;
248 for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) {
249 int RSS = RevMap[SS][j];
250 const TargetRegisterClass *RC = LS->getIntervalRegClass(RSS);
251 // If it's not colored to another stack slot, try coloring it
252 // to a "free" register.
257 unsigned Reg = VRM->getFirstUnusedRegister(RC);
262 if (!AllMemRefsCanBeUnfolded(RSS)) {
266 DOUT << "Assigning fi#" << RSS << " to " << TRI->getName(Reg) << '\n';
267 ColoredRegs.push_back(Reg);
268 SlotMapping[RSS] = Reg;
274 // Register and its sub-registers are no longer free.
275 while (!ColoredRegs.empty()) {
276 unsigned Reg = ColoredRegs.back();
277 ColoredRegs.pop_back();
278 VRM->setRegisterUsed(Reg);
279 // If reg is a callee-saved register, it will have to be spilled in
281 MRI->setPhysRegUsed(Reg);
282 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
283 VRM->setRegisterUsed(*AS);
284 MRI->setPhysRegUsed(*AS);
287 // This spill slot is dead after the rewrites
289 MFI->RemoveStackObject(SS);
298 /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.
300 int StackSlotColoring::ColorSlot(LiveInterval *li) {
303 if (!DisableSharing) {
304 // Check if it's possible to reuse any of the used colors.
305 Color = UsedColors.find_first();
306 while (Color != -1) {
307 if (!OverlapWithAssignments(li, Color)) {
312 Color = UsedColors.find_next(Color);
316 // Assign it to the first available color (assumed to be the best) if it's
317 // not possible to share a used color with other objects.
319 assert(NextColor != -1 && "No more spill slots?");
321 UsedColors.set(Color);
322 NextColor = AllColors.find_next(NextColor);
325 // Record the assignment.
326 Assignments[Color].push_back(li);
327 int FI = li->getStackSlotIndex();
328 DOUT << "Assigning fi#" << FI << " to fi#" << Color << "\n";
330 // Change size and alignment of the allocated slot. If there are multiple
331 // objects sharing the same slot, then make sure the size and alignment
332 // are large enough for all.
333 unsigned Align = OrigAlignments[FI];
334 if (!Share || Align > MFI->getObjectAlignment(Color))
335 MFI->setObjectAlignment(Color, Align);
336 int64_t Size = OrigSizes[FI];
337 if (!Share || Size > MFI->getObjectSize(Color))
338 MFI->setObjectSize(Color, Size);
342 /// Colorslots - Color all spill stack slots and rewrite all frameindex machine
343 /// operands in the function.
344 bool StackSlotColoring::ColorSlots(MachineFunction &MF) {
345 unsigned NumObjs = MFI->getObjectIndexEnd();
346 SmallVector<int, 16> SlotMapping(NumObjs, -1);
347 SmallVector<float, 16> SlotWeights(NumObjs, 0.0);
348 SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs);
349 BitVector SlotIsReg(NumObjs);
350 BitVector UsedColors(NumObjs);
352 DOUT << "Color spill slot intervals:\n";
353 bool Changed = false;
354 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
355 LiveInterval *li = SSIntervals[i];
356 int SS = li->getStackSlotIndex();
357 int NewSS = ColorSlot(li);
358 assert(NewSS >= 0 && "Stack coloring failed?");
359 SlotMapping[SS] = NewSS;
360 RevMap[NewSS].push_back(SS);
361 SlotWeights[NewSS] += li->weight;
362 UsedColors.set(NewSS);
363 Changed |= (SS != NewSS);
366 DOUT << "\nSpill slots after coloring:\n";
367 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
368 LiveInterval *li = SSIntervals[i];
369 int SS = li->getStackSlotIndex();
370 li->weight = SlotWeights[SS];
372 // Sort them by new weight.
373 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
376 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i)
377 DEBUG(SSIntervals[i]->dump());
381 // Can we "color" a stack slot with a unused register?
382 Changed |= ColorSlotsWithFreeRegs(SlotMapping, RevMap, SlotIsReg);
387 // Rewrite all MO_FrameIndex operands.
388 for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) {
389 bool isReg = SlotIsReg[SS];
390 int NewFI = SlotMapping[SS];
391 if (NewFI == -1 || (NewFI == (int)SS && !isReg))
394 SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS];
395 for (unsigned i = 0, e = RefMIs.size(); i != e; ++i)
397 RewriteInstruction(RefMIs[i], SS, NewFI, MF);
399 // Rewrite to use a register instead.
400 const TargetRegisterClass *RC = LS->getIntervalRegClass(SS);
401 UnfoldAndRewriteInstruction(RefMIs[i], SS, NewFI, RC, MF);
405 // Delete unused stack slots.
406 while (NextColor != -1) {
407 DOUT << "Removing unused stack object fi#" << NextColor << "\n";
408 MFI->RemoveStackObject(NextColor);
409 NextColor = AllColors.find_next(NextColor);
415 /// AllMemRefsCanBeUnfolded - Return true if all references of the specified
416 /// spill slot index can be unfolded.
417 bool StackSlotColoring::AllMemRefsCanBeUnfolded(int SS) {
418 SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS];
419 for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) {
420 MachineInstr *MI = RefMIs[i];
421 if (TII->isLoadFromStackSlot(MI, SS) ||
422 TII->isStoreToStackSlot(MI, SS))
423 // Restore and spill will become copies.
425 if (!TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), false, false))
427 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
428 MachineOperand &MO = MI->getOperand(j);
429 if (MO.isFI() && MO.getIndex() != SS)
430 // If it uses another frameindex, we can, currently* unfold it.
437 /// RewriteInstruction - Rewrite specified instruction by replacing references
438 /// to old frame index with new one.
439 void StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI,
440 int NewFI, MachineFunction &MF) {
441 for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) {
442 MachineOperand &MO = MI->getOperand(i);
445 int FI = MO.getIndex();
451 // Update the MachineMemOperand for the new memory location.
452 // FIXME: We need a better method of managing these too.
453 SmallVector<MachineMemOperand, 2> MMOs(MI->memoperands_begin(),
454 MI->memoperands_end());
455 MI->clearMemOperands(MF);
456 const Value *OldSV = PseudoSourceValue::getFixedStack(OldFI);
457 for (unsigned i = 0, ee = MMOs.size(); i != ee; ++i) {
458 if (MMOs[i].getValue() != OldSV)
459 MI->addMemOperand(MF, MMOs[i]);
461 MachineMemOperand MMO(PseudoSourceValue::getFixedStack(NewFI),
462 MMOs[i].getFlags(), MMOs[i].getOffset(),
463 MMOs[i].getSize(), MMOs[i].getAlignment());
464 MI->addMemOperand(MF, MMO);
469 /// PropagateBackward - Traverse backward and look for the definition of
470 /// OldReg. If it can successfully update all of the references with NewReg,
471 /// do so and return true.
472 bool StackSlotColoring::PropagateBackward(MachineBasicBlock::iterator MII,
473 MachineBasicBlock *MBB,
474 unsigned OldReg, unsigned NewReg) {
475 SmallVector<MachineOperand*, 4> Refs;
476 while (--MII != MBB->begin()) {
477 bool FoundDef = false; // Not counting 2address def.
478 bool FoundUse = false;
479 bool FoundKill = false;
480 const TargetInstrDesc &TID = MII->getDesc();
481 for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
482 MachineOperand &MO = MII->getOperand(i);
485 unsigned Reg = MO.getReg();
489 const TargetRegisterClass *RC = getInstrOperandRegClass(TRI, TID, i);
490 if (RC && !RC->contains(NewReg))
500 if (!MII->isRegTiedToUseOperand(i))
503 } else if (TRI->regsOverlap(Reg, NewReg)) {
505 } else if (TRI->regsOverlap(Reg, OldReg)) {
506 if (!MO.isUse() || !MO.isKill())
511 for (unsigned i = 0, e = Refs.size(); i != e; ++i)
512 Refs[i]->setReg(NewReg);
519 /// PropagateForward - Traverse forward and look for the kill of OldReg. If
520 /// it can successfully update all of the uses with NewReg, do so and
522 bool StackSlotColoring::PropagateForward(MachineBasicBlock::iterator MII,
523 MachineBasicBlock *MBB,
524 unsigned OldReg, unsigned NewReg) {
525 SmallVector<MachineOperand*, 4> Uses;
526 while (++MII != MBB->end()) {
527 bool FoundUse = false;
528 bool FoundKill = false;
529 const TargetInstrDesc &TID = MII->getDesc();
530 for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
531 MachineOperand &MO = MII->getOperand(i);
534 unsigned Reg = MO.getReg();
541 const TargetRegisterClass *RC = getInstrOperandRegClass(TRI, TID, i);
542 if (RC && !RC->contains(NewReg))
548 } else if (TRI->regsOverlap(Reg, NewReg) ||
549 TRI->regsOverlap(Reg, OldReg))
553 for (unsigned i = 0, e = Uses.size(); i != e; ++i)
554 Uses[i]->setReg(NewReg);
561 /// UnfoldAndRewriteInstruction - Rewrite specified instruction by unfolding
562 /// folded memory references and replacing those references with register
563 /// references instead.
564 void StackSlotColoring::UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI,
566 const TargetRegisterClass *RC,
567 MachineFunction &MF) {
568 MachineBasicBlock *MBB = MI->getParent();
569 if (unsigned DstReg = TII->isLoadFromStackSlot(MI, OldFI)) {
570 if (PropagateForward(MI, MBB, DstReg, Reg)) {
571 DOUT << "Eliminated load: ";
575 TII->copyRegToReg(*MBB, MI, DstReg, Reg, RC, RC);
578 } else if (unsigned SrcReg = TII->isStoreToStackSlot(MI, OldFI)) {
579 if (MI->killsRegister(SrcReg) && PropagateBackward(MI, MBB, SrcReg, Reg)) {
580 DOUT << "Eliminated store: ";
584 TII->copyRegToReg(*MBB, MI, Reg, SrcReg, RC, RC);
588 SmallVector<MachineInstr*, 4> NewMIs;
589 bool Success = TII->unfoldMemoryOperand(MF, MI, Reg, false, false, NewMIs);
590 assert(Success && "Failed to unfold!");
591 MBB->insert(MI, NewMIs[0]);
597 /// RemoveDeadStores - Scan through a basic block and look for loads followed
598 /// by stores. If they're both using the same stack slot, then the store is
599 /// definitely dead. This could obviously be much more aggressive (consider
600 /// pairs with instructions between them), but such extensions might have a
601 /// considerable compile time impact.
602 bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) {
603 // FIXME: This could be much more aggressive, but we need to investigate
604 // the compile time impact of doing so.
605 bool changed = false;
607 SmallVector<MachineInstr*, 4> toErase;
609 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
611 if (DCELimit != -1 && (int)NumDead >= DCELimit)
614 MachineBasicBlock::iterator NextMI = next(I);
615 if (NextMI == MBB->end()) continue;
617 int FirstSS, SecondSS;
618 unsigned LoadReg = 0;
619 unsigned StoreReg = 0;
620 if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue;
621 if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue;
622 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue;
627 if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) {
629 toErase.push_back(I);
632 toErase.push_back(NextMI);
636 for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(),
637 E = toErase.end(); I != E; ++I)
638 (*I)->eraseFromParent();
644 bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
645 DOUT << "********** Stack Slot Coloring **********\n";
647 MFI = MF.getFrameInfo();
648 MRI = &MF.getRegInfo();
649 TII = MF.getTarget().getInstrInfo();
650 TRI = MF.getTarget().getRegisterInfo();
651 LS = &getAnalysis<LiveStacks>();
652 VRM = &getAnalysis<VirtRegMap>();
653 loopInfo = &getAnalysis<MachineLoopInfo>();
655 bool Changed = false;
657 unsigned NumSlots = LS->getNumIntervals();
659 if (NumSlots == 0 || !VRM->HasUnusedRegisters())
664 // Gather spill slot references
665 ScanForSpillSlotRefs(MF);
667 Changed = ColorSlots(MF);
671 for (unsigned i = 0, e = SSRefs.size(); i != e; ++i)
674 OrigAlignments.clear();
678 for (unsigned i = 0, e = Assignments.size(); i != e; ++i)
679 Assignments[i].clear();
683 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
684 Changed |= RemoveDeadStores(I);