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(NumDead, "Number of trivially dead stack accesses eliminated");
49 STATISTIC(NumRegRepl, "Number of stack slot refs replaced with reg refs");
52 class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass {
55 MachineFrameInfo *MFI;
56 MachineRegisterInfo *MRI;
57 const TargetInstrInfo *TII;
58 const TargetRegisterInfo *TRI;
59 const MachineLoopInfo *loopInfo;
61 // SSIntervals - Spill slot intervals.
62 std::vector<LiveInterval*> SSIntervals;
64 // SSRefs - Keep a list of frame index references for each spill slot.
65 SmallVector<SmallVector<MachineInstr*, 8>, 16> SSRefs;
67 // OrigAlignments - Alignments of stack objects before coloring.
68 SmallVector<unsigned, 16> OrigAlignments;
70 // OrigSizes - Sizess of stack objects before coloring.
71 SmallVector<unsigned, 16> OrigSizes;
73 // AllColors - If index is set, it's a spill slot, i.e. color.
74 // FIXME: This assumes PEI locate spill slot with smaller indices
75 // closest to stack pointer / frame pointer. Therefore, smaller
76 // index == better color.
79 // NextColor - Next "color" that's not yet used.
82 // UsedColors - "Colors" that have been assigned.
85 // Assignments - Color to intervals mapping.
86 SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments;
89 static char ID; // Pass identification
90 StackSlotColoring() : MachineFunctionPass(&ID), NextColor(-1) {}
92 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
93 AU.addRequired<LiveStacks>();
94 AU.addRequired<VirtRegMap>();
95 AU.addPreserved<VirtRegMap>();
96 AU.addRequired<MachineLoopInfo>();
97 AU.addPreserved<MachineLoopInfo>();
98 AU.addPreservedID(MachineDominatorsID);
99 MachineFunctionPass::getAnalysisUsage(AU);
102 virtual bool runOnMachineFunction(MachineFunction &MF);
103 virtual const char* getPassName() const {
104 return "Stack Slot Coloring";
108 void InitializeSlots();
109 void ScanForSpillSlotRefs(MachineFunction &MF);
110 bool OverlapWithAssignments(LiveInterval *li, int Color) const;
111 int ColorSlot(LiveInterval *li);
112 bool ColorSlots(MachineFunction &MF);
113 bool ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping,
114 SmallVector<SmallVector<int, 4>, 16> &RevMap,
115 BitVector &SlotIsReg);
116 void RewriteInstruction(MachineInstr *MI, int OldFI, int NewFI,
117 MachineFunction &MF);
118 void UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI,
119 unsigned Reg, MachineFunction &MF);
120 bool AllMemRefsCanBeUnfolded(int SS);
121 bool RemoveDeadStores(MachineBasicBlock* MBB);
123 } // end anonymous namespace
125 char StackSlotColoring::ID = 0;
127 static RegisterPass<StackSlotColoring>
128 X("stack-slot-coloring", "Stack Slot Coloring");
130 FunctionPass *llvm::createStackSlotColoringPass() {
131 return new StackSlotColoring();
135 // IntervalSorter - Comparison predicate that sort live intervals by
137 struct IntervalSorter {
138 bool operator()(LiveInterval* LHS, LiveInterval* RHS) const {
139 return LHS->weight > RHS->weight;
144 /// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot
145 /// references and update spill slot weights.
146 void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) {
147 SSRefs.resize(MFI->getObjectIndexEnd());
149 // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands.
150 for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
152 MachineBasicBlock *MBB = &*MBBI;
153 unsigned loopDepth = loopInfo->getLoopDepth(MBB);
154 for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end();
156 MachineInstr *MI = &*MII;
157 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
158 MachineOperand &MO = MI->getOperand(i);
161 int FI = MO.getIndex();
164 if (!LS->hasInterval(FI))
166 LiveInterval &li = LS->getInterval(FI);
167 li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth);
168 SSRefs[FI].push_back(MI);
174 /// InitializeSlots - Process all spill stack slot liveintervals and add them
175 /// to a sorted (by weight) list.
176 void StackSlotColoring::InitializeSlots() {
177 int LastFI = MFI->getObjectIndexEnd();
178 OrigAlignments.resize(LastFI);
179 OrigSizes.resize(LastFI);
180 AllColors.resize(LastFI);
181 UsedColors.resize(LastFI);
182 Assignments.resize(LastFI);
184 // Gather all spill slots into a list.
185 DOUT << "Spill slot intervals:\n";
186 for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) {
187 LiveInterval &li = i->second;
189 int FI = li.getStackSlotIndex();
190 if (MFI->isDeadObjectIndex(FI))
192 SSIntervals.push_back(&li);
193 OrigAlignments[FI] = MFI->getObjectAlignment(FI);
194 OrigSizes[FI] = MFI->getObjectSize(FI);
199 // Sort them by weight.
200 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
202 // Get first "color".
203 NextColor = AllColors.find_first();
206 /// OverlapWithAssignments - Return true if LiveInterval overlaps with any
207 /// LiveIntervals that have already been assigned to the specified color.
209 StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const {
210 const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color];
211 for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) {
212 LiveInterval *OtherLI = OtherLIs[i];
213 if (OtherLI->overlaps(*li))
219 /// ColorSlotsWithFreeRegs - If there are any free registers available, try
220 /// replacing spill slots references with registers instead.
222 StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping,
223 SmallVector<SmallVector<int, 4>, 16> &RevMap,
224 BitVector &SlotIsReg) {
225 if (!ColorWithRegs || !VRM->HasUnusedRegisters())
228 bool Changed = false;
229 DOUT << "Assigning unused registers to spill slots:\n";
230 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
231 LiveInterval *li = SSIntervals[i];
232 int SS = li->getStackSlotIndex();
236 // These slots allow to share the same registers.
237 bool AllColored = true;
238 SmallVector<unsigned, 4> ColoredRegs;
239 for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) {
240 int RSS = RevMap[SS][j];
241 const TargetRegisterClass *RC = LS->getIntervalRegClass(RSS);
242 // If it's not colored to another stack slot, try coloring it
243 // to a "free" register.
248 unsigned Reg = VRM->getFirstUnusedRegister(RC);
253 if (!AllMemRefsCanBeUnfolded(RSS)) {
257 DOUT << "Assigning fi#" << RSS << " to " << TRI->getName(Reg) << '\n';
258 ColoredRegs.push_back(Reg);
259 SlotMapping[RSS] = Reg;
265 // Register and its sub-registers are no longer free.
266 while (!ColoredRegs.empty()) {
267 unsigned Reg = ColoredRegs.back();
268 ColoredRegs.pop_back();
269 VRM->setRegisterUsed(Reg);
270 // If reg is a callee-saved register, it will have to be spilled in
272 MRI->setPhysRegUsed(Reg);
273 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
274 VRM->setRegisterUsed(*AS);
275 MRI->setPhysRegUsed(*AS);
278 // This spill slot is dead after the rewrites
280 MFI->RemoveStackObject(SS);
289 /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.
291 int StackSlotColoring::ColorSlot(LiveInterval *li) {
294 if (!DisableSharing) {
295 // Check if it's possible to reuse any of the used colors.
296 Color = UsedColors.find_first();
297 while (Color != -1) {
298 if (!OverlapWithAssignments(li, Color)) {
303 Color = UsedColors.find_next(Color);
307 // Assign it to the first available color (assumed to be the best) if it's
308 // not possible to share a used color with other objects.
310 assert(NextColor != -1 && "No more spill slots?");
312 UsedColors.set(Color);
313 NextColor = AllColors.find_next(NextColor);
316 // Record the assignment.
317 Assignments[Color].push_back(li);
318 int FI = li->getStackSlotIndex();
319 DOUT << "Assigning fi#" << FI << " to fi#" << Color << "\n";
321 // Change size and alignment of the allocated slot. If there are multiple
322 // objects sharing the same slot, then make sure the size and alignment
323 // are large enough for all.
324 unsigned Align = OrigAlignments[FI];
325 if (!Share || Align > MFI->getObjectAlignment(Color))
326 MFI->setObjectAlignment(Color, Align);
327 int64_t Size = OrigSizes[FI];
328 if (!Share || Size > MFI->getObjectSize(Color))
329 MFI->setObjectSize(Color, Size);
333 /// Colorslots - Color all spill stack slots and rewrite all frameindex machine
334 /// operands in the function.
335 bool StackSlotColoring::ColorSlots(MachineFunction &MF) {
336 unsigned NumObjs = MFI->getObjectIndexEnd();
337 SmallVector<int, 16> SlotMapping(NumObjs, -1);
338 SmallVector<float, 16> SlotWeights(NumObjs, 0.0);
339 SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs);
340 BitVector SlotIsReg(NumObjs);
341 BitVector UsedColors(NumObjs);
343 DOUT << "Color spill slot intervals:\n";
344 bool Changed = false;
345 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
346 LiveInterval *li = SSIntervals[i];
347 int SS = li->getStackSlotIndex();
348 int NewSS = ColorSlot(li);
349 assert(NewSS >= 0 && "Stack coloring failed?");
350 SlotMapping[SS] = NewSS;
351 RevMap[NewSS].push_back(SS);
352 SlotWeights[NewSS] += li->weight;
353 UsedColors.set(NewSS);
354 Changed |= (SS != NewSS);
357 DOUT << "\nSpill slots after coloring:\n";
358 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
359 LiveInterval *li = SSIntervals[i];
360 int SS = li->getStackSlotIndex();
361 li->weight = SlotWeights[SS];
363 // Sort them by new weight.
364 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
367 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i)
368 DEBUG(SSIntervals[i]->dump());
372 // Can we "color" a stack slot with a unused register?
373 Changed |= ColorSlotsWithFreeRegs(SlotMapping, RevMap, SlotIsReg);
378 // Rewrite all MO_FrameIndex operands.
379 for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) {
380 bool isReg = SlotIsReg[SS];
381 int NewFI = SlotMapping[SS];
382 if (NewFI == -1 || (NewFI == (int)SS && !isReg))
385 SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS];
386 for (unsigned i = 0, e = RefMIs.size(); i != e; ++i)
388 // Rewrite to use a register instead.
389 UnfoldAndRewriteInstruction(RefMIs[i], SS, NewFI, MF);
391 RewriteInstruction(RefMIs[i], SS, NewFI, MF);
394 // Delete unused stack slots.
395 while (NextColor != -1) {
396 DOUT << "Removing unused stack object fi#" << NextColor << "\n";
397 MFI->RemoveStackObject(NextColor);
398 NextColor = AllColors.find_next(NextColor);
404 /// AllMemRefsCanBeUnfolded - Return true if all references of the specified
405 /// spill slot index can be unfolded.
406 bool StackSlotColoring::AllMemRefsCanBeUnfolded(int SS) {
407 SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS];
408 for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) {
409 MachineInstr *MI = RefMIs[i];
410 if (!TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), false, false))
412 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
413 MachineOperand &MO = MI->getOperand(j);
414 if (MO.isFI() && MO.getIndex() != SS)
415 // If it uses another frameindex, we can, currently* unfold it.
422 /// RewriteInstruction - Rewrite specified instruction by replacing references
423 /// to old frame index with new one.
424 void StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI,
425 int NewFI, MachineFunction &MF) {
426 for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) {
427 MachineOperand &MO = MI->getOperand(i);
430 int FI = MO.getIndex();
436 // Update the MachineMemOperand for the new memory location.
437 // FIXME: We need a better method of managing these too.
438 SmallVector<MachineMemOperand, 2> MMOs(MI->memoperands_begin(),
439 MI->memoperands_end());
440 MI->clearMemOperands(MF);
441 const Value *OldSV = PseudoSourceValue::getFixedStack(OldFI);
442 for (unsigned i = 0, ee = MMOs.size(); i != ee; ++i) {
443 if (MMOs[i].getValue() != OldSV)
444 MI->addMemOperand(MF, MMOs[i]);
446 MachineMemOperand MMO(PseudoSourceValue::getFixedStack(NewFI),
447 MMOs[i].getFlags(), MMOs[i].getOffset(),
448 MMOs[i].getSize(), MMOs[i].getAlignment());
449 MI->addMemOperand(MF, MMO);
454 /// UnfoldAndRewriteInstruction - Rewrite specified instruction by unfolding
455 /// folded memory references and replacing those references with register
456 /// references instead.
457 void StackSlotColoring::UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI,
459 MachineFunction &MF) {
460 MachineBasicBlock *MBB = MI->getParent();
461 SmallVector<MachineInstr*, 4> NewMIs;
462 bool Success = TII->unfoldMemoryOperand(MF, MI, Reg, false, false, NewMIs);
463 assert(Success && "Failed to unfold!");
464 MBB->insert(MI, NewMIs[0]);
469 /// RemoveDeadStores - Scan through a basic block and look for loads followed
470 /// by stores. If they're both using the same stack slot, then the store is
471 /// definitely dead. This could obviously be much more aggressive (consider
472 /// pairs with instructions between them), but such extensions might have a
473 /// considerable compile time impact.
474 bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) {
475 // FIXME: This could be much more aggressive, but we need to investigate
476 // the compile time impact of doing so.
477 bool changed = false;
479 SmallVector<MachineInstr*, 4> toErase;
481 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
483 if (DCELimit != -1 && (int)NumDead >= DCELimit)
486 MachineBasicBlock::iterator NextMI = next(I);
487 if (NextMI == MBB->end()) continue;
489 int FirstSS, SecondSS;
490 unsigned LoadReg = 0;
491 unsigned StoreReg = 0;
492 if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue;
493 if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue;
494 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue;
499 if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) {
501 toErase.push_back(I);
504 toErase.push_back(NextMI);
508 for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(),
509 E = toErase.end(); I != E; ++I)
510 (*I)->eraseFromParent();
516 bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
517 DOUT << "********** Stack Slot Coloring **********\n";
519 MFI = MF.getFrameInfo();
520 MRI = &MF.getRegInfo();
521 TII = MF.getTarget().getInstrInfo();
522 TRI = MF.getTarget().getRegisterInfo();
523 LS = &getAnalysis<LiveStacks>();
524 VRM = &getAnalysis<VirtRegMap>();
525 loopInfo = &getAnalysis<MachineLoopInfo>();
527 bool Changed = false;
529 unsigned NumSlots = LS->getNumIntervals();
531 if (NumSlots == 0 || !VRM->HasUnusedRegisters())
536 // Gather spill slot references
537 ScanForSpillSlotRefs(MF);
539 Changed = ColorSlots(MF);
543 for (unsigned i = 0, e = SSRefs.size(); i != e; ++i)
546 OrigAlignments.clear();
550 for (unsigned i = 0, e = Assignments.size(); i != e; ++i)
551 Assignments[i].clear();
555 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
556 Changed |= RemoveDeadStores(I);