StackSlotColoring.cpp revision 4669f7d6ee8f83e171df13736a54eca7a5f0776f 
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 "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"
31#include <vector>
32using namespace llvm;
33
34static cl::opt<bool>
35DisableSharing("no-stack-slot-sharing",
36             cl::init(false), cl::Hidden,
37             cl::desc("Suppress slot sharing during stack coloring"));
38
39static cl::opt<bool>
40ColorWithRegs("color-ss-with-regs",
41             cl::init(false), cl::Hidden,
42             cl::desc("Color stack slots with free registers"));
43
44
45static cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden);
46
47STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring");
48STATISTIC(NumRegRepl,    "Number of stack slot refs replaced with reg refs");
49STATISTIC(NumLoadElim,   "Number of load eliminated");
50STATISTIC(NumStoreElim,  "Number of stores eliminated");
51STATISTIC(NumDead,       "Number of trivially dead stack accesses eliminated");
52
53namespace {
54  class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass {
55    LiveStacks* LS;
56    VirtRegMap* VRM;
57    MachineFrameInfo *MFI;
58    MachineRegisterInfo *MRI;
59    const TargetInstrInfo  *TII;
60    const TargetRegisterInfo *TRI;
61    const MachineLoopInfo *loopInfo;
62
63    // SSIntervals - Spill slot intervals.
64    std::vector<LiveInterval*> SSIntervals;
65
66    // SSRefs - Keep a list of frame index references for each spill slot.
67    SmallVector<SmallVector<MachineInstr*, 8>, 16> SSRefs;
68
69    // OrigAlignments - Alignments of stack objects before coloring.
70    SmallVector<unsigned, 16> OrigAlignments;
71
72    // OrigSizes - Sizess of stack objects before coloring.
73    SmallVector<unsigned, 16> OrigSizes;
74
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.
79    BitVector AllColors;
80
81    // NextColor - Next "color" that's not yet used.
82    int NextColor;
83
84    // UsedColors - "Colors" that have been assigned.
85    BitVector UsedColors;
86
87    // Assignments - Color to intervals mapping.
88    SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments;
89
90  public:
91    static char ID; // Pass identification
92    StackSlotColoring() : MachineFunctionPass(&ID), NextColor(-1) {}
93
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);
102    }
103
104    virtual bool runOnMachineFunction(MachineFunction &MF);
105    virtual const char* getPassName() const {
106      return "Stack Slot Coloring";
107    }
108
109  private:
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);
131  };
132} // end anonymous namespace
133
134char StackSlotColoring::ID = 0;
135
136static RegisterPass<StackSlotColoring>
137X("stack-slot-coloring", "Stack Slot Coloring");
138
139FunctionPass *llvm::createStackSlotColoringPass() {
140  return new StackSlotColoring();
141}
142
143namespace {
144  // IntervalSorter - Comparison predicate that sort live intervals by
145  // their weight.
146  struct IntervalSorter {
147    bool operator()(LiveInterval* LHS, LiveInterval* RHS) const {
148      return LHS->weight > RHS->weight;
149    }
150  };
151}
152
153/// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot
154/// references and update spill slot weights.
155void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) {
156  SSRefs.resize(MFI->getObjectIndexEnd());
157
158  // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands.
159  for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
160       MBBI != E; ++MBBI) {
161    MachineBasicBlock *MBB = &*MBBI;
162    unsigned loopDepth = loopInfo->getLoopDepth(MBB);
163    for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end();
164         MII != EE; ++MII) {
165      MachineInstr *MI = &*MII;
166      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
167        MachineOperand &MO = MI->getOperand(i);
168        if (!MO.isFI())
169          continue;
170        int FI = MO.getIndex();
171        if (FI < 0)
172          continue;
173        if (!LS->hasInterval(FI))
174          continue;
175        LiveInterval &li = LS->getInterval(FI);
176        li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth);
177        SSRefs[FI].push_back(MI);
178      }
179    }
180  }
181}
182
183/// InitializeSlots - Process all spill stack slot liveintervals and add them
184/// to a sorted (by weight) list.
185void 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);
192
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;
197    DEBUG(li.dump());
198    int FI = li.getStackSlotIndex();
199    if (MFI->isDeadObjectIndex(FI))
200      continue;
201    SSIntervals.push_back(&li);
202    OrigAlignments[FI] = MFI->getObjectAlignment(FI);
203    OrigSizes[FI]      = MFI->getObjectSize(FI);
204    AllColors.set(FI);
205  }
206  DOUT << '\n';
207
208  // Sort them by weight.
209  std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
210
211  // Get first "color".
212  NextColor = AllColors.find_first();
213}
214
215/// OverlapWithAssignments - Return true if LiveInterval overlaps with any
216/// LiveIntervals that have already been assigned to the specified color.
217bool
218StackSlotColoring::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))
223      return true;
224  }
225  return false;
226}
227
228/// ColorSlotsWithFreeRegs - If there are any free registers available, try
229/// replacing spill slots references with registers instead.
230bool
231StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping,
232                                   SmallVector<SmallVector<int, 4>, 16> &RevMap,
233                                   BitVector &SlotIsReg) {
234  if (!ColorWithRegs || !VRM->HasUnusedRegisters())
235    return false;
236
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();
242    if (!UsedColors[SS])
243      continue;
244
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.
253      if (!RC) {
254        AllColored = false;
255        continue;
256      }
257      unsigned Reg = VRM->getFirstUnusedRegister(RC);
258      if (!Reg) {
259        AllColored = false;
260        continue;
261      }
262      if (!AllMemRefsCanBeUnfolded(RSS)) {
263        AllColored = false;
264        continue;
265      } else {
266        DOUT << "Assigning fi#" << RSS << " to " << TRI->getName(Reg) << '\n';
267        ColoredRegs.push_back(Reg);
268        SlotMapping[RSS] = Reg;
269        SlotIsReg.set(RSS);
270        Changed = true;
271      }
272    }
273
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
280      // the prologue.
281      MRI->setPhysRegUsed(Reg);
282      for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
283        VRM->setRegisterUsed(*AS);
284        MRI->setPhysRegUsed(*AS);
285      }
286    }
287    // This spill slot is dead after the rewrites
288    if (AllColored) {
289      MFI->RemoveStackObject(SS);
290      ++NumEliminated;
291    }
292  }
293  DOUT << '\n';
294
295  return Changed;
296}
297
298/// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.
299///
300int StackSlotColoring::ColorSlot(LiveInterval *li) {
301  int Color = -1;
302  bool Share = false;
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)) {
308        Share = true;
309        ++NumEliminated;
310        break;
311      }
312      Color = UsedColors.find_next(Color);
313    }
314  }
315
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.
318  if (!Share) {
319    assert(NextColor != -1 && "No more spill slots?");
320    Color = NextColor;
321    UsedColors.set(Color);
322    NextColor = AllColors.find_next(NextColor);
323  }
324
325  // Record the assignment.
326  Assignments[Color].push_back(li);
327  int FI = li->getStackSlotIndex();
328  DOUT << "Assigning fi#" << FI << " to fi#" << Color << "\n";
329
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);
339  return Color;
340}
341
342/// Colorslots - Color all spill stack slots and rewrite all frameindex machine
343/// operands in the function.
344bool 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);
351
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);
364  }
365
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];
371  }
372  // Sort them by new weight.
373  std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
374
375#ifndef NDEBUG
376  for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i)
377    DEBUG(SSIntervals[i]->dump());
378  DOUT << '\n';
379#endif
380
381  // Can we "color" a stack slot with a unused register?
382  Changed |= ColorSlotsWithFreeRegs(SlotMapping, RevMap, SlotIsReg);
383
384  if (!Changed)
385    return false;
386
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))
392      continue;
393
394    SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS];
395    for (unsigned i = 0, e = RefMIs.size(); i != e; ++i)
396      if (!isReg)
397        RewriteInstruction(RefMIs[i], SS, NewFI, MF);
398      else {
399        // Rewrite to use a register instead.
400        const TargetRegisterClass *RC = LS->getIntervalRegClass(SS);
401        UnfoldAndRewriteInstruction(RefMIs[i], SS, NewFI, RC, MF);
402      }
403  }
404
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);
410  }
411
412  return true;
413}
414
415/// AllMemRefsCanBeUnfolded - Return true if all references of the specified
416/// spill slot index can be unfolded.
417bool 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.
424      return true;
425    if (!TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), false, false))
426      return 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.
431        return false;
432    }
433  }
434  return true;
435}
436
437/// RewriteInstruction - Rewrite specified instruction by replacing references
438/// to old frame index with new one.
439void 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);
443    if (!MO.isFI())
444      continue;
445    int FI = MO.getIndex();
446    if (FI != OldFI)
447      continue;
448    MO.setIndex(NewFI);
449  }
450
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]);
460    else {
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);
465    }
466  }
467}
468
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.
472bool 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);
483      if (!MO.isReg())
484        continue;
485      unsigned Reg = MO.getReg();
486      if (Reg == 0)
487        continue;
488      if (Reg == OldReg) {
489        const TargetRegisterClass *RC = getInstrOperandRegClass(TRI, TID, i);
490        if (RC && !RC->contains(NewReg))
491          return false;
492
493        if (MO.isUse()) {
494          FoundUse = true;
495          if (MO.isKill())
496            FoundKill = true;
497          Refs.push_back(&MO);
498        } else {
499          Refs.push_back(&MO);
500          if (!MII->isRegTiedToUseOperand(i))
501            FoundDef = true;
502        }
503      } else if (TRI->regsOverlap(Reg, NewReg)) {
504        return false;
505      } else if (TRI->regsOverlap(Reg, OldReg)) {
506        if (!MO.isUse() || !MO.isKill())
507          return false;
508      }
509    }
510    if (FoundDef) {
511      for (unsigned i = 0, e = Refs.size(); i != e; ++i)
512        Refs[i]->setReg(NewReg);
513      return true;
514    }
515  }
516  return false;
517}
518
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
521/// return true.
522bool 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);
532      if (!MO.isReg())
533        continue;
534      unsigned Reg = MO.getReg();
535      if (Reg == 0)
536        continue;
537      if (Reg == OldReg) {
538        if (MO.isDef())
539          return false;
540
541        const TargetRegisterClass *RC = getInstrOperandRegClass(TRI, TID, i);
542        if (RC && !RC->contains(NewReg))
543          return false;
544        FoundUse = true;
545        if (MO.isKill())
546          FoundKill = true;
547        Uses.push_back(&MO);
548      } else if (TRI->regsOverlap(Reg, NewReg) ||
549                 TRI->regsOverlap(Reg, OldReg))
550        return false;
551    }
552    if (FoundKill) {
553      for (unsigned i = 0, e = Uses.size(); i != e; ++i)
554        Uses[i]->setReg(NewReg);
555      return true;
556    }
557  }
558  return false;
559}
560
561/// UnfoldAndRewriteInstruction - Rewrite specified instruction by unfolding
562/// folded memory references and replacing those references with register
563/// references instead.
564void StackSlotColoring::UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI,
565                                                  unsigned Reg,
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: ";
572      DEBUG(MI->dump());
573      ++NumLoadElim;
574    } else {
575      TII->copyRegToReg(*MBB, MI, DstReg, Reg, RC, RC);
576      ++NumRegRepl;
577    }
578  } else if (unsigned SrcReg = TII->isStoreToStackSlot(MI, OldFI)) {
579    if (MI->killsRegister(SrcReg) && PropagateBackward(MI, MBB, SrcReg, Reg)) {
580      DOUT << "Eliminated store: ";
581      DEBUG(MI->dump());
582      ++NumStoreElim;
583    } else {
584      TII->copyRegToReg(*MBB, MI, Reg, SrcReg, RC, RC);
585      ++NumRegRepl;
586    }
587  } else {
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]);
592    ++NumRegRepl;
593  }
594  MBB->erase(MI);
595}
596
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.
602bool 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;
606
607  SmallVector<MachineInstr*, 4> toErase;
608
609  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
610       I != E; ++I) {
611    if (DCELimit != -1 && (int)NumDead >= DCELimit)
612      break;
613
614    MachineBasicBlock::iterator NextMI = next(I);
615    if (NextMI == MBB->end()) continue;
616
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;
623
624    ++NumDead;
625    changed = true;
626
627    if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) {
628      ++NumDead;
629      toErase.push_back(I);
630    }
631
632    toErase.push_back(NextMI);
633    ++I;
634  }
635
636  for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(),
637       E = toErase.end(); I != E; ++I)
638    (*I)->eraseFromParent();
639
640  return changed;
641}
642
643
644bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
645  DOUT << "********** Stack Slot Coloring **********\n";
646
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>();
654
655  bool Changed = false;
656
657  unsigned NumSlots = LS->getNumIntervals();
658  if (NumSlots < 2) {
659    if (NumSlots == 0 || !VRM->HasUnusedRegisters())
660      // Nothing to do!
661      return false;
662  }
663
664  // Gather spill slot references
665  ScanForSpillSlotRefs(MF);
666  InitializeSlots();
667  Changed = ColorSlots(MF);
668
669  NextColor = -1;
670  SSIntervals.clear();
671  for (unsigned i = 0, e = SSRefs.size(); i != e; ++i)
672    SSRefs[i].clear();
673  SSRefs.clear();
674  OrigAlignments.clear();
675  OrigSizes.clear();
676  AllColors.clear();
677  UsedColors.clear();
678  for (unsigned i = 0, e = Assignments.size(); i != e; ++i)
679    Assignments[i].clear();
680  Assignments.clear();
681
682  if (Changed) {
683    for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
684      Changed |= RemoveDeadStores(I);
685  }
686
687  return Changed;
688}
689