lib/CodeGen/StackSlotColoring.cpp

   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 "llvm/CodeGen/Passes.h"
  16 #include "llvm/CodeGen/LiveStackAnalysis.h"
  17 #include "llvm/CodeGen/MachineFrameInfo.h"
  18 #include "llvm/CodeGen/PseudoSourceValue.h"
  19 #include "llvm/Support/CommandLine.h"
  20 #include "llvm/Support/Compiler.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/Target/TargetInstrInfo.h"
  23 #include "llvm/Target/TargetMachine.h"
  24 #include "llvm/ADT/BitVector.h"
  25 #include "llvm/ADT/SmallVector.h"
  26 #include "llvm/ADT/Statistic.h"
  27 #include <vector>
  28 using namespace llvm;
  29
  30 static cl::opt<bool>
  31 DisableSharing("no-stack-slot-sharing",
  32              cl::init(false), cl::Hidden,
  33              cl::desc("Surpress slot sharing during stack coloring"));
  34
  35 static cl::opt<bool>
  36 EnableDCE("enable-ssc-dce",
  37                cl::init(false), cl::Hidden,
  38                cl::desc("Enable slot coloring DCE"));
  39
  40 static cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden);
  41
  42 STATISTIC(NumEliminated,   "Number of stack slots eliminated due to coloring");
  43 STATISTIC(NumDeadAccesses,
  44                           "Number of trivially dead stack accesses eliminated");
  45
  46 namespace {
  47   class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass {
  48     LiveStacks* LS;
  49     MachineFrameInfo *MFI;
  50     const TargetInstrInfo  *TII;
  51
  52     // SSIntervals - Spill slot intervals.
  53     std::vector<LiveInterval*> SSIntervals;
  54
  55     // OrigAlignments - Alignments of stack objects before coloring.
  56     SmallVector<unsigned, 16> OrigAlignments;
  57
  58     // OrigSizes - Sizess of stack objects before coloring.
  59     SmallVector<unsigned, 16> OrigSizes;
  60
  61     // AllColors - If index is set, it's a spill slot, i.e. color.
  62     // FIXME: This assumes PEI locate spill slot with smaller indices
  63     // closest to stack pointer / frame pointer. Therefore, smaller
  64     // index == better color.
  65     BitVector AllColors;
  66
  67     // NextColor - Next "color" that's not yet used.
  68     int NextColor;
  69
  70     // UsedColors - "Colors" that have been assigned.
  71     BitVector UsedColors;
  72
  73     // Assignments - Color to intervals mapping.
  74     SmallVector<SmallVector<LiveInterval*,4>,16> Assignments;
  75
  76   public:
  77     static char ID; // Pass identification
  78     StackSlotColoring() : MachineFunctionPass(&ID), NextColor(-1) {}
  79
  80     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  81       AU.addRequired<LiveStacks>();
  82
  83       AU.addPreservedID(MachineLoopInfoID);
  84       AU.addPreservedID(MachineDominatorsID);
  85       MachineFunctionPass::getAnalysisUsage(AU);
  86     }
  87
  88     virtual bool runOnMachineFunction(MachineFunction &MF);
  89     virtual const char* getPassName() const {
  90       return "Stack Slot Coloring";
  91     }
  92
  93   private:
  94     bool InitializeSlots();
  95     bool OverlapWithAssignments(LiveInterval *li, int Color) const;
  96     int ColorSlot(LiveInterval *li);
  97     bool ColorSlots(MachineFunction &MF);
  98     bool removeDeadStores(MachineBasicBlock* MBB);
  99   };
 100 } // end anonymous namespace
 101
 102 char StackSlotColoring::ID = 0;
 103
 104 static RegisterPass<StackSlotColoring>
 105 X("stack-slot-coloring", "Stack Slot Coloring");
 106
 107 FunctionPass *llvm::createStackSlotColoringPass() {
 108   return new StackSlotColoring();
 109 }
 110
 111 namespace {
 112   // IntervalSorter - Comparison predicate that sort live intervals by
 113   // their weight.
 114   struct IntervalSorter {
 115     bool operator()(LiveInterval* LHS, LiveInterval* RHS) const {
 116       return LHS->weight > RHS->weight;
 117     }
 118   };
 119 }
 120
 121 /// InitializeSlots - Process all spill stack slot liveintervals and add them
 122 /// to a sorted (by weight) list.
 123 bool StackSlotColoring::InitializeSlots() {
 124   if (LS->getNumIntervals() < 2)
 125     return false;
 126
 127   int LastFI = MFI->getObjectIndexEnd();
 128   OrigAlignments.resize(LastFI);
 129   OrigSizes.resize(LastFI);
 130   AllColors.resize(LastFI);
 131   UsedColors.resize(LastFI);
 132   Assignments.resize(LastFI);
 133
 134   // Gather all spill slots into a list.
 135   for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) {
 136     LiveInterval &li = i->second;
 137     int FI = li.getStackSlotIndex();
 138     if (MFI->isDeadObjectIndex(FI))
 139       continue;
 140     SSIntervals.push_back(&li);
 141     OrigAlignments[FI] = MFI->getObjectAlignment(FI);
 142     OrigSizes[FI]      = MFI->getObjectSize(FI);
 143     AllColors.set(FI);
 144   }
 145
 146   // Sort them by weight.
 147   std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
 148
 149   // Get first "color".
 150   NextColor = AllColors.find_first();
 151   return true;
 152 }
 153
 154 /// OverlapWithAssignments - Return true if LiveInterval overlaps with any
 155 /// LiveIntervals that have already been assigned to the specified color.
 156 bool
 157 StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const {
 158   const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color];
 159   for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) {
 160     LiveInterval *OtherLI = OtherLIs[i];
 161     if (OtherLI->overlaps(*li))
 162       return true;
 163   }
 164   return false;
 165 }
 166
 167 /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.
 168 ///
 169 int StackSlotColoring::ColorSlot(LiveInterval *li) {
 170   int Color = -1;
 171   bool Share = false;
 172   if (!DisableSharing) {
 173     // Check if it's possible to reuse any of the used colors.
 174     Color = UsedColors.find_first();
 175     while (Color != -1) {
 176       if (!OverlapWithAssignments(li, Color)) {
 177         Share = true;
 178         ++NumEliminated;
 179         break;
 180       }
 181       Color = UsedColors.find_next(Color);
 182     }
 183   }
 184
 185   // Assign it to the first available color (assumed to be the best) if it's
 186   // not possible to share a used color with other objects.
 187   if (!Share) {
 188     assert(NextColor != -1 && "No more spill slots?");
 189     Color = NextColor;
 190     UsedColors.set(Color);
 191     NextColor = AllColors.find_next(NextColor);
 192   }
 193
 194   // Record the assignment.
 195   Assignments[Color].push_back(li);
 196   int FI = li->getStackSlotIndex();
 197   DOUT << "Assigning fi#" << FI << " to fi#" << Color << "\n";
 198
 199   // Change size and alignment of the allocated slot. If there are multiple
 200   // objects sharing the same slot, then make sure the size and alignment
 201   // are large enough for all.
 202   unsigned Align = OrigAlignments[FI];
 203   if (!Share || Align > MFI->getObjectAlignment(Color))
 204     MFI->setObjectAlignment(Color, Align);
 205   int64_t Size = OrigSizes[FI];
 206   if (!Share || Size > MFI->getObjectSize(Color))
 207     MFI->setObjectSize(Color, Size);
 208   return Color;
 209 }
 210
 211 /// Colorslots - Color all spill stack slots and rewrite all frameindex machine
 212 /// operands in the function.
 213 bool StackSlotColoring::ColorSlots(MachineFunction &MF) {
 214   unsigned NumObjs = MFI->getObjectIndexEnd();
 215   std::vector<int> SlotMapping(NumObjs, -1);
 216
 217   bool Changed = false;
 218   for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
 219     LiveInterval *li = SSIntervals[i];
 220     int SS = li->getStackSlotIndex();
 221     int NewSS = ColorSlot(li);
 222     SlotMapping[SS] = NewSS;
 223     Changed |= (SS != NewSS);
 224   }
 225
 226   if (!Changed)
 227     return false;
 228
 229   // Rewrite all MO_FrameIndex operands.
 230   // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands.
 231   for (MachineFunction::iterator MBB = MF.begin(), E = MF.end();
 232        MBB != E; ++MBB) {
 233     for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end();
 234          MII != EE; ++MII) {
 235       MachineInstr &MI = *MII;
 236       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 237         MachineOperand &MO = MI.getOperand(i);
 238         if (!MO.isFI())
 239           continue;
 240         int FI = MO.getIndex();
 241         if (FI < 0)
 242           continue;
 243         int NewFI = SlotMapping[FI];
 244         if (NewFI == -1)
 245           continue;
 246         MO.setIndex(NewFI);
 247
 248         // Update the MachineMemOperand for the new memory location.
 249         // FIXME: We need a better method of managing these too.
 250         SmallVector<MachineMemOperand, 2> MMOs(MI.memoperands_begin(),
 251                                                MI.memoperands_end());
 252         MI.clearMemOperands(MF);
 253         const Value *OldSV = PseudoSourceValue::getFixedStack(FI);
 254         for (unsigned i = 0, e = MMOs.size(); i != e; ++i) {
 255           if (MMOs[i].getValue() == OldSV) {
 256             MachineMemOperand MMO(PseudoSourceValue::getFixedStack(NewFI),
 257                                   MMOs[i].getFlags(), MMOs[i].getOffset(),
 258                                   MMOs[i].getSize(), MMOs[i].getAlignment());
 259             MI.addMemOperand(MF, MMO);
 260           } else
 261             MI.addMemOperand(MF, MMOs[i]);
 262         }
 263       }
 264     }
 265   }
 266
 267   // Delete unused stack slots.
 268   while (NextColor != -1) {
 269     DOUT << "Removing unused stack object fi#" << NextColor << "\n";
 270     MFI->RemoveStackObject(NextColor);
 271     NextColor = AllColors.find_next(NextColor);
 272   }
 273
 274   return true;
 275 }
 276
 277 /// removeDeadStores - Scan through a basic block and look for loads followed
 278 /// by stores.  If they're both using the same stack slot, then the store is
 279 /// definitely dead.  This could obviously be much more aggressive (consider
 280 /// pairs with instructions between them), but such extensions might have a
 281 /// considerable compile time impact.
 282 bool StackSlotColoring::removeDeadStores(MachineBasicBlock* MBB) {
 283   // FIXME: This could be much more aggressive, but we need to investigate
 284   // the compile time impact of doing so.
 285   bool changed = false;
 286
 287   SmallVector<MachineInstr*, 4> toErase;
 288
 289   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
 290        I != E; ++I) {
 291     if (DCELimit != -1 && (int)NumDeadAccesses >= DCELimit)
 292       break;
 293
 294     MachineBasicBlock::iterator NextMI = next(I);
 295     if (NextMI == MBB->end()) continue;
 296
 297     int FirstSS, SecondSS;
 298     unsigned LoadReg = 0;
 299     unsigned StoreReg = 0;
 300     if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue;
 301     if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue;
 302     if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue;
 303
 304     ++NumDeadAccesses;
 305     changed = true;
 306
 307     if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) {
 308       ++NumDeadAccesses;
 309       toErase.push_back(I);
 310     }
 311
 312     toErase.push_back(NextMI);
 313     ++I;
 314   }
 315
 316   for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(),
 317        E = toErase.end(); I != E; ++I)
 318     (*I)->eraseFromParent();
 319
 320   return changed;
 321 }
 322
 323
 324 bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
 325   DOUT << "********** Stack Slot Coloring **********\n";
 326
 327   MFI = MF.getFrameInfo();
 328   TII = MF.getTarget().getInstrInfo();
 329   LS = &getAnalysis<LiveStacks>();
 330
 331   bool Changed = false;
 332   if (InitializeSlots())
 333     Changed = ColorSlots(MF);
 334
 335   NextColor = -1;
 336   SSIntervals.clear();
 337   OrigAlignments.clear();
 338   OrigSizes.clear();
 339   AllColors.clear();
 340   UsedColors.clear();
 341   for (unsigned i = 0, e = Assignments.size(); i != e; ++i)
 342     Assignments[i].clear();
 343   Assignments.clear();
 344
 345   if (EnableDCE) {
 346     for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
 347       Changed |= removeDeadStores(I);
 348   }
 349
 350   return Changed;
 351 }