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/MachineMemOperand.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/CodeGen/PseudoSourceValue.h"
24 #include "llvm/Support/CommandLine.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/SmallSet.h"
30 #include "llvm/ADT/SmallVector.h"
31 #include "llvm/ADT/Statistic.h"
36 DisableSharing("no-stack-slot-sharing",
37 cl::init(false), cl::Hidden
,
38 cl::desc("Suppress slot sharing during stack coloring"));
41 ColorWithRegsOpt("color-ss-with-regs",
42 cl::init(false), cl::Hidden
,
43 cl::desc("Color stack slots with free registers"));
46 static cl::opt
<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden
);
48 STATISTIC(NumEliminated
, "Number of stack slots eliminated due to coloring");
49 STATISTIC(NumRegRepl
, "Number of stack slot refs replaced with reg refs");
50 STATISTIC(NumLoadElim
, "Number of loads eliminated");
51 STATISTIC(NumStoreElim
, "Number of stores eliminated");
52 STATISTIC(NumDead
, "Number of trivially dead stack accesses eliminated");
55 class StackSlotColoring
: public MachineFunctionPass
{
59 MachineFrameInfo
*MFI
;
60 MachineRegisterInfo
*MRI
;
61 const TargetInstrInfo
*TII
;
62 const TargetRegisterInfo
*TRI
;
63 const MachineLoopInfo
*loopInfo
;
65 // SSIntervals - Spill slot intervals.
66 std::vector
<LiveInterval
*> SSIntervals
;
68 // SSRefs - Keep a list of frame index references for each spill slot.
69 SmallVector
<SmallVector
<MachineInstr
*, 8>, 16> SSRefs
;
71 // OrigAlignments - Alignments of stack objects before coloring.
72 SmallVector
<unsigned, 16> OrigAlignments
;
74 // OrigSizes - Sizess of stack objects before coloring.
75 SmallVector
<unsigned, 16> OrigSizes
;
77 // AllColors - If index is set, it's a spill slot, i.e. color.
78 // FIXME: This assumes PEI locate spill slot with smaller indices
79 // closest to stack pointer / frame pointer. Therefore, smaller
80 // index == better color.
83 // NextColor - Next "color" that's not yet used.
86 // UsedColors - "Colors" that have been assigned.
89 // Assignments - Color to intervals mapping.
90 SmallVector
<SmallVector
<LiveInterval
*,4>, 16> Assignments
;
93 static char ID
; // Pass identification
95 MachineFunctionPass(&ID
), ColorWithRegs(false), NextColor(-1) {}
96 StackSlotColoring(bool RegColor
) :
97 MachineFunctionPass(&ID
), ColorWithRegs(RegColor
), NextColor(-1) {}
99 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
100 AU
.setPreservesCFG();
101 AU
.addRequired
<LiveStacks
>();
102 AU
.addRequired
<VirtRegMap
>();
103 AU
.addPreserved
<VirtRegMap
>();
104 AU
.addRequired
<MachineLoopInfo
>();
105 AU
.addPreserved
<MachineLoopInfo
>();
106 AU
.addPreservedID(MachineDominatorsID
);
107 MachineFunctionPass::getAnalysisUsage(AU
);
110 virtual bool runOnMachineFunction(MachineFunction
&MF
);
111 virtual const char* getPassName() const {
112 return "Stack Slot Coloring";
116 void InitializeSlots();
117 void ScanForSpillSlotRefs(MachineFunction
&MF
);
118 bool OverlapWithAssignments(LiveInterval
*li
, int Color
) const;
119 int ColorSlot(LiveInterval
*li
);
120 bool ColorSlots(MachineFunction
&MF
);
121 bool ColorSlotsWithFreeRegs(SmallVector
<int, 16> &SlotMapping
,
122 SmallVector
<SmallVector
<int, 4>, 16> &RevMap
,
123 BitVector
&SlotIsReg
);
124 void RewriteInstruction(MachineInstr
*MI
, int OldFI
, int NewFI
,
125 MachineFunction
&MF
);
126 bool PropagateBackward(MachineBasicBlock::iterator MII
,
127 MachineBasicBlock
*MBB
,
128 unsigned OldReg
, unsigned NewReg
);
129 bool PropagateForward(MachineBasicBlock::iterator MII
,
130 MachineBasicBlock
*MBB
,
131 unsigned OldReg
, unsigned NewReg
);
132 void UnfoldAndRewriteInstruction(MachineInstr
*MI
, int OldFI
,
133 unsigned Reg
, const TargetRegisterClass
*RC
,
134 SmallSet
<unsigned, 4> &Defs
,
135 MachineFunction
&MF
);
136 bool AllMemRefsCanBeUnfolded(int SS
);
137 bool RemoveDeadStores(MachineBasicBlock
* MBB
);
139 } // end anonymous namespace
141 char StackSlotColoring::ID
= 0;
143 static RegisterPass
<StackSlotColoring
>
144 X("stack-slot-coloring", "Stack Slot Coloring");
146 FunctionPass
*llvm::createStackSlotColoringPass(bool RegColor
) {
147 return new StackSlotColoring(RegColor
);
151 // IntervalSorter - Comparison predicate that sort live intervals by
153 struct IntervalSorter
{
154 bool operator()(LiveInterval
* LHS
, LiveInterval
* RHS
) const {
155 return LHS
->weight
> RHS
->weight
;
160 /// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot
161 /// references and update spill slot weights.
162 void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction
&MF
) {
163 SSRefs
.resize(MFI
->getObjectIndexEnd());
165 // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands.
166 for (MachineFunction::iterator MBBI
= MF
.begin(), E
= MF
.end();
168 MachineBasicBlock
*MBB
= &*MBBI
;
169 unsigned loopDepth
= loopInfo
->getLoopDepth(MBB
);
170 for (MachineBasicBlock::iterator MII
= MBB
->begin(), EE
= MBB
->end();
172 MachineInstr
*MI
= &*MII
;
173 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
174 MachineOperand
&MO
= MI
->getOperand(i
);
177 int FI
= MO
.getIndex();
180 if (!LS
->hasInterval(FI
))
182 LiveInterval
&li
= LS
->getInterval(FI
);
183 li
.weight
+= LiveIntervals::getSpillWeight(false, true, loopDepth
);
184 SSRefs
[FI
].push_back(MI
);
190 /// InitializeSlots - Process all spill stack slot liveintervals and add them
191 /// to a sorted (by weight) list.
192 void StackSlotColoring::InitializeSlots() {
193 int LastFI
= MFI
->getObjectIndexEnd();
194 OrigAlignments
.resize(LastFI
);
195 OrigSizes
.resize(LastFI
);
196 AllColors
.resize(LastFI
);
197 UsedColors
.resize(LastFI
);
198 Assignments
.resize(LastFI
);
200 // Gather all spill slots into a list.
201 DEBUG(errs() << "Spill slot intervals:\n");
202 for (LiveStacks::iterator i
= LS
->begin(), e
= LS
->end(); i
!= e
; ++i
) {
203 LiveInterval
&li
= i
->second
;
205 int FI
= li
.getStackSlotIndex();
206 if (MFI
->isDeadObjectIndex(FI
))
208 SSIntervals
.push_back(&li
);
209 OrigAlignments
[FI
] = MFI
->getObjectAlignment(FI
);
210 OrigSizes
[FI
] = MFI
->getObjectSize(FI
);
213 DEBUG(errs() << '\n');
215 // Sort them by weight.
216 std::stable_sort(SSIntervals
.begin(), SSIntervals
.end(), IntervalSorter());
218 // Get first "color".
219 NextColor
= AllColors
.find_first();
222 /// OverlapWithAssignments - Return true if LiveInterval overlaps with any
223 /// LiveIntervals that have already been assigned to the specified color.
225 StackSlotColoring::OverlapWithAssignments(LiveInterval
*li
, int Color
) const {
226 const SmallVector
<LiveInterval
*,4> &OtherLIs
= Assignments
[Color
];
227 for (unsigned i
= 0, e
= OtherLIs
.size(); i
!= e
; ++i
) {
228 LiveInterval
*OtherLI
= OtherLIs
[i
];
229 if (OtherLI
->overlaps(*li
))
235 /// ColorSlotsWithFreeRegs - If there are any free registers available, try
236 /// replacing spill slots references with registers instead.
238 StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector
<int, 16> &SlotMapping
,
239 SmallVector
<SmallVector
<int, 4>, 16> &RevMap
,
240 BitVector
&SlotIsReg
) {
241 if (!(ColorWithRegs
|| ColorWithRegsOpt
) || !VRM
->HasUnusedRegisters())
244 bool Changed
= false;
245 DEBUG(errs() << "Assigning unused registers to spill slots:\n");
246 for (unsigned i
= 0, e
= SSIntervals
.size(); i
!= e
; ++i
) {
247 LiveInterval
*li
= SSIntervals
[i
];
248 int SS
= li
->getStackSlotIndex();
249 if (!UsedColors
[SS
] || li
->weight
< 20)
250 // If the weight is < 20, i.e. two references in a loop with depth 1,
251 // don't bother with it.
254 // These slots allow to share the same registers.
255 bool AllColored
= true;
256 SmallVector
<unsigned, 4> ColoredRegs
;
257 for (unsigned j
= 0, ee
= RevMap
[SS
].size(); j
!= ee
; ++j
) {
258 int RSS
= RevMap
[SS
][j
];
259 const TargetRegisterClass
*RC
= LS
->getIntervalRegClass(RSS
);
260 // If it's not colored to another stack slot, try coloring it
261 // to a "free" register.
266 unsigned Reg
= VRM
->getFirstUnusedRegister(RC
);
271 if (!AllMemRefsCanBeUnfolded(RSS
)) {
275 DEBUG(errs() << "Assigning fi#" << RSS
<< " to "
276 << TRI
->getName(Reg
) << '\n');
277 ColoredRegs
.push_back(Reg
);
278 SlotMapping
[RSS
] = Reg
;
284 // Register and its sub-registers are no longer free.
285 while (!ColoredRegs
.empty()) {
286 unsigned Reg
= ColoredRegs
.back();
287 ColoredRegs
.pop_back();
288 VRM
->setRegisterUsed(Reg
);
289 // If reg is a callee-saved register, it will have to be spilled in
291 MRI
->setPhysRegUsed(Reg
);
292 for (const unsigned *AS
= TRI
->getAliasSet(Reg
); *AS
; ++AS
) {
293 VRM
->setRegisterUsed(*AS
);
294 MRI
->setPhysRegUsed(*AS
);
297 // This spill slot is dead after the rewrites
299 MFI
->RemoveStackObject(SS
);
303 DEBUG(errs() << '\n');
308 /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.
310 int StackSlotColoring::ColorSlot(LiveInterval
*li
) {
313 if (!DisableSharing
) {
314 // Check if it's possible to reuse any of the used colors.
315 Color
= UsedColors
.find_first();
316 while (Color
!= -1) {
317 if (!OverlapWithAssignments(li
, Color
)) {
322 Color
= UsedColors
.find_next(Color
);
326 // Assign it to the first available color (assumed to be the best) if it's
327 // not possible to share a used color with other objects.
329 assert(NextColor
!= -1 && "No more spill slots?");
331 UsedColors
.set(Color
);
332 NextColor
= AllColors
.find_next(NextColor
);
335 // Record the assignment.
336 Assignments
[Color
].push_back(li
);
337 int FI
= li
->getStackSlotIndex();
338 DEBUG(errs() << "Assigning fi#" << FI
<< " to fi#" << Color
<< "\n");
340 // Change size and alignment of the allocated slot. If there are multiple
341 // objects sharing the same slot, then make sure the size and alignment
342 // are large enough for all.
343 unsigned Align
= OrigAlignments
[FI
];
344 if (!Share
|| Align
> MFI
->getObjectAlignment(Color
))
345 MFI
->setObjectAlignment(Color
, Align
);
346 int64_t Size
= OrigSizes
[FI
];
347 if (!Share
|| Size
> MFI
->getObjectSize(Color
))
348 MFI
->setObjectSize(Color
, Size
);
352 /// Colorslots - Color all spill stack slots and rewrite all frameindex machine
353 /// operands in the function.
354 bool StackSlotColoring::ColorSlots(MachineFunction
&MF
) {
355 unsigned NumObjs
= MFI
->getObjectIndexEnd();
356 SmallVector
<int, 16> SlotMapping(NumObjs
, -1);
357 SmallVector
<float, 16> SlotWeights(NumObjs
, 0.0);
358 SmallVector
<SmallVector
<int, 4>, 16> RevMap(NumObjs
);
359 BitVector
SlotIsReg(NumObjs
);
360 BitVector
UsedColors(NumObjs
);
362 DEBUG(errs() << "Color spill slot intervals:\n");
363 bool Changed
= false;
364 for (unsigned i
= 0, e
= SSIntervals
.size(); i
!= e
; ++i
) {
365 LiveInterval
*li
= SSIntervals
[i
];
366 int SS
= li
->getStackSlotIndex();
367 int NewSS
= ColorSlot(li
);
368 assert(NewSS
>= 0 && "Stack coloring failed?");
369 SlotMapping
[SS
] = NewSS
;
370 RevMap
[NewSS
].push_back(SS
);
371 SlotWeights
[NewSS
] += li
->weight
;
372 UsedColors
.set(NewSS
);
373 Changed
|= (SS
!= NewSS
);
376 DEBUG(errs() << "\nSpill slots after coloring:\n");
377 for (unsigned i
= 0, e
= SSIntervals
.size(); i
!= e
; ++i
) {
378 LiveInterval
*li
= SSIntervals
[i
];
379 int SS
= li
->getStackSlotIndex();
380 li
->weight
= SlotWeights
[SS
];
382 // Sort them by new weight.
383 std::stable_sort(SSIntervals
.begin(), SSIntervals
.end(), IntervalSorter());
386 for (unsigned i
= 0, e
= SSIntervals
.size(); i
!= e
; ++i
)
387 DEBUG(SSIntervals
[i
]->dump());
388 DEBUG(errs() << '\n');
391 // Can we "color" a stack slot with a unused register?
392 Changed
|= ColorSlotsWithFreeRegs(SlotMapping
, RevMap
, SlotIsReg
);
397 // Rewrite all MO_FrameIndex operands.
398 SmallVector
<SmallSet
<unsigned, 4>, 4> NewDefs(MF
.getNumBlockIDs());
399 for (unsigned SS
= 0, SE
= SSRefs
.size(); SS
!= SE
; ++SS
) {
400 bool isReg
= SlotIsReg
[SS
];
401 int NewFI
= SlotMapping
[SS
];
402 if (NewFI
== -1 || (NewFI
== (int)SS
&& !isReg
))
405 const TargetRegisterClass
*RC
= LS
->getIntervalRegClass(SS
);
406 SmallVector
<MachineInstr
*, 8> &RefMIs
= SSRefs
[SS
];
407 for (unsigned i
= 0, e
= RefMIs
.size(); i
!= e
; ++i
)
409 RewriteInstruction(RefMIs
[i
], SS
, NewFI
, MF
);
411 // Rewrite to use a register instead.
412 unsigned MBBId
= RefMIs
[i
]->getParent()->getNumber();
413 SmallSet
<unsigned, 4> &Defs
= NewDefs
[MBBId
];
414 UnfoldAndRewriteInstruction(RefMIs
[i
], SS
, NewFI
, RC
, Defs
, MF
);
418 // Delete unused stack slots.
419 while (NextColor
!= -1) {
420 DEBUG(errs() << "Removing unused stack object fi#" << NextColor
<< "\n");
421 MFI
->RemoveStackObject(NextColor
);
422 NextColor
= AllColors
.find_next(NextColor
);
428 /// AllMemRefsCanBeUnfolded - Return true if all references of the specified
429 /// spill slot index can be unfolded.
430 bool StackSlotColoring::AllMemRefsCanBeUnfolded(int SS
) {
431 SmallVector
<MachineInstr
*, 8> &RefMIs
= SSRefs
[SS
];
432 for (unsigned i
= 0, e
= RefMIs
.size(); i
!= e
; ++i
) {
433 MachineInstr
*MI
= RefMIs
[i
];
434 if (TII
->isLoadFromStackSlot(MI
, SS
) ||
435 TII
->isStoreToStackSlot(MI
, SS
))
436 // Restore and spill will become copies.
438 if (!TII
->getOpcodeAfterMemoryUnfold(MI
->getOpcode(), false, false))
440 for (unsigned j
= 0, ee
= MI
->getNumOperands(); j
!= ee
; ++j
) {
441 MachineOperand
&MO
= MI
->getOperand(j
);
442 if (MO
.isFI() && MO
.getIndex() != SS
)
443 // If it uses another frameindex, we can, currently* unfold it.
450 /// RewriteInstruction - Rewrite specified instruction by replacing references
451 /// to old frame index with new one.
452 void StackSlotColoring::RewriteInstruction(MachineInstr
*MI
, int OldFI
,
453 int NewFI
, MachineFunction
&MF
) {
454 // Update the operands.
455 for (unsigned i
= 0, ee
= MI
->getNumOperands(); i
!= ee
; ++i
) {
456 MachineOperand
&MO
= MI
->getOperand(i
);
459 int FI
= MO
.getIndex();
465 // Update the memory references. This changes the MachineMemOperands
466 // directly. They may be in use by multiple instructions, however all
467 // instructions using OldFI are being rewritten to use NewFI.
468 const Value
*OldSV
= PseudoSourceValue::getFixedStack(OldFI
);
469 const Value
*NewSV
= PseudoSourceValue::getFixedStack(NewFI
);
470 for (MachineInstr::mmo_iterator I
= MI
->memoperands_begin(),
471 E
= MI
->memoperands_end(); I
!= E
; ++I
)
472 if ((*I
)->getValue() == OldSV
)
473 (*I
)->setValue(NewSV
);
476 /// PropagateBackward - Traverse backward and look for the definition of
477 /// OldReg. If it can successfully update all of the references with NewReg,
478 /// do so and return true.
479 bool StackSlotColoring::PropagateBackward(MachineBasicBlock::iterator MII
,
480 MachineBasicBlock
*MBB
,
481 unsigned OldReg
, unsigned NewReg
) {
482 if (MII
== MBB
->begin())
485 SmallVector
<MachineOperand
*, 4> Uses
;
486 SmallVector
<MachineOperand
*, 4> Refs
;
487 while (--MII
!= MBB
->begin()) {
488 bool FoundDef
= false; // Not counting 2address def.
491 const TargetInstrDesc
&TID
= MII
->getDesc();
492 for (unsigned i
= 0, e
= MII
->getNumOperands(); i
!= e
; ++i
) {
493 MachineOperand
&MO
= MII
->getOperand(i
);
496 unsigned Reg
= MO
.getReg();
503 // Abort the use is actually a sub-register def. We don't have enough
504 // information to figure out if it is really legal.
505 if (MO
.getSubReg() ||
506 TID
.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG
||
507 TID
.getOpcode() == TargetInstrInfo::INSERT_SUBREG
||
508 TID
.getOpcode() == TargetInstrInfo::SUBREG_TO_REG
)
511 const TargetRegisterClass
*RC
= TID
.OpInfo
[i
].getRegClass(TRI
);
512 if (RC
&& !RC
->contains(NewReg
))
519 if (!MII
->isRegTiedToUseOperand(i
))
522 } else if (TRI
->regsOverlap(Reg
, NewReg
)) {
524 } else if (TRI
->regsOverlap(Reg
, OldReg
)) {
525 if (!MO
.isUse() || !MO
.isKill())
531 // Found non-two-address def. Stop here.
532 for (unsigned i
= 0, e
= Refs
.size(); i
!= e
; ++i
)
533 Refs
[i
]->setReg(NewReg
);
537 // Two-address uses must be updated as well.
538 for (unsigned i
= 0, e
= Uses
.size(); i
!= e
; ++i
)
539 Refs
.push_back(Uses
[i
]);
544 /// PropagateForward - Traverse forward and look for the kill of OldReg. If
545 /// it can successfully update all of the uses with NewReg, do so and
547 bool StackSlotColoring::PropagateForward(MachineBasicBlock::iterator MII
,
548 MachineBasicBlock
*MBB
,
549 unsigned OldReg
, unsigned NewReg
) {
550 if (MII
== MBB
->end())
553 SmallVector
<MachineOperand
*, 4> Uses
;
554 while (++MII
!= MBB
->end()) {
555 bool FoundKill
= false;
556 const TargetInstrDesc
&TID
= MII
->getDesc();
557 for (unsigned i
= 0, e
= MII
->getNumOperands(); i
!= e
; ++i
) {
558 MachineOperand
&MO
= MII
->getOperand(i
);
561 unsigned Reg
= MO
.getReg();
565 if (MO
.isDef() || MO
.isImplicit())
568 // Abort the use is actually a sub-register use. We don't have enough
569 // information to figure out if it is really legal.
570 if (MO
.getSubReg() ||
571 TID
.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG
)
574 const TargetRegisterClass
*RC
= TID
.OpInfo
[i
].getRegClass(TRI
);
575 if (RC
&& !RC
->contains(NewReg
))
581 } else if (TRI
->regsOverlap(Reg
, NewReg
) ||
582 TRI
->regsOverlap(Reg
, OldReg
))
586 for (unsigned i
= 0, e
= Uses
.size(); i
!= e
; ++i
)
587 Uses
[i
]->setReg(NewReg
);
594 /// UnfoldAndRewriteInstruction - Rewrite specified instruction by unfolding
595 /// folded memory references and replacing those references with register
596 /// references instead.
598 StackSlotColoring::UnfoldAndRewriteInstruction(MachineInstr
*MI
, int OldFI
,
600 const TargetRegisterClass
*RC
,
601 SmallSet
<unsigned, 4> &Defs
,
602 MachineFunction
&MF
) {
603 MachineBasicBlock
*MBB
= MI
->getParent();
604 if (unsigned DstReg
= TII
->isLoadFromStackSlot(MI
, OldFI
)) {
605 if (PropagateForward(MI
, MBB
, DstReg
, Reg
)) {
606 DEBUG(errs() << "Eliminated load: ");
610 TII
->copyRegToReg(*MBB
, MI
, DstReg
, Reg
, RC
, RC
);
614 if (!Defs
.count(Reg
)) {
615 // If this is the first use of Reg in this MBB and it wasn't previously
616 // defined in MBB, add it to livein.
620 } else if (unsigned SrcReg
= TII
->isStoreToStackSlot(MI
, OldFI
)) {
621 if (MI
->killsRegister(SrcReg
) && PropagateBackward(MI
, MBB
, SrcReg
, Reg
)) {
622 DEBUG(errs() << "Eliminated store: ");
626 TII
->copyRegToReg(*MBB
, MI
, Reg
, SrcReg
, RC
, RC
);
630 // Remember reg has been defined in MBB.
633 SmallVector
<MachineInstr
*, 4> NewMIs
;
634 bool Success
= TII
->unfoldMemoryOperand(MF
, MI
, Reg
, false, false, NewMIs
);
635 Success
= Success
; // Silence compiler warning.
636 assert(Success
&& "Failed to unfold!");
637 MachineInstr
*NewMI
= NewMIs
[0];
638 MBB
->insert(MI
, NewMI
);
641 if (NewMI
->readsRegister(Reg
)) {
642 if (!Defs
.count(Reg
))
643 // If this is the first use of Reg in this MBB and it wasn't previously
644 // defined in MBB, add it to livein.
652 /// RemoveDeadStores - Scan through a basic block and look for loads followed
653 /// by stores. If they're both using the same stack slot, then the store is
654 /// definitely dead. This could obviously be much more aggressive (consider
655 /// pairs with instructions between them), but such extensions might have a
656 /// considerable compile time impact.
657 bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock
* MBB
) {
658 // FIXME: This could be much more aggressive, but we need to investigate
659 // the compile time impact of doing so.
660 bool changed
= false;
662 SmallVector
<MachineInstr
*, 4> toErase
;
664 for (MachineBasicBlock::iterator I
= MBB
->begin(), E
= MBB
->end();
666 if (DCELimit
!= -1 && (int)NumDead
>= DCELimit
)
669 MachineBasicBlock::iterator NextMI
= next(I
);
670 if (NextMI
== MBB
->end()) continue;
672 int FirstSS
, SecondSS
;
673 unsigned LoadReg
= 0;
674 unsigned StoreReg
= 0;
675 if (!(LoadReg
= TII
->isLoadFromStackSlot(I
, FirstSS
))) continue;
676 if (!(StoreReg
= TII
->isStoreToStackSlot(NextMI
, SecondSS
))) continue;
677 if (FirstSS
!= SecondSS
|| LoadReg
!= StoreReg
|| FirstSS
== -1) continue;
682 if (NextMI
->findRegisterUseOperandIdx(LoadReg
, true, 0) != -1) {
684 toErase
.push_back(I
);
687 toErase
.push_back(NextMI
);
691 for (SmallVector
<MachineInstr
*, 4>::iterator I
= toErase
.begin(),
692 E
= toErase
.end(); I
!= E
; ++I
)
693 (*I
)->eraseFromParent();
699 bool StackSlotColoring::runOnMachineFunction(MachineFunction
&MF
) {
700 DEBUG(errs() << "********** Stack Slot Coloring **********\n");
702 MFI
= MF
.getFrameInfo();
703 MRI
= &MF
.getRegInfo();
704 TII
= MF
.getTarget().getInstrInfo();
705 TRI
= MF
.getTarget().getRegisterInfo();
706 LS
= &getAnalysis
<LiveStacks
>();
707 VRM
= &getAnalysis
<VirtRegMap
>();
708 loopInfo
= &getAnalysis
<MachineLoopInfo
>();
710 bool Changed
= false;
712 unsigned NumSlots
= LS
->getNumIntervals();
714 if (NumSlots
== 0 || !VRM
->HasUnusedRegisters())
719 // Gather spill slot references
720 ScanForSpillSlotRefs(MF
);
722 Changed
= ColorSlots(MF
);
726 for (unsigned i
= 0, e
= SSRefs
.size(); i
!= e
; ++i
)
729 OrigAlignments
.clear();
733 for (unsigned i
= 0, e
= Assignments
.size(); i
!= e
; ++i
)
734 Assignments
[i
].clear();
738 for (MachineFunction::iterator I
= MF
.begin(), E
= MF
.end(); I
!= E
; ++I
)
739 Changed
|= RemoveDeadStores(I
);