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 "VirtRegMap.h"
  16 #include "llvm/Function.h"
  17 #include "llvm/Module.h"
  18 #include "llvm/CodeGen/Passes.h"
  19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  20 #include "llvm/CodeGen/LiveStackAnalysis.h"
  21 #include "llvm/CodeGen/MachineFrameInfo.h"
  22 #include "llvm/CodeGen/MachineInstrBuilder.h"
  23 #include "llvm/CodeGen/MachineLoopInfo.h"
  24 #include "llvm/CodeGen/MachineMemOperand.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/PseudoSourceValue.h"
  27 #include "llvm/Support/CommandLine.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Target/TargetInstrInfo.h"
  30 #include "llvm/Target/TargetMachine.h"
  31 #include "llvm/ADT/BitVector.h"
  32 #include "llvm/ADT/SmallSet.h"
  33 #include "llvm/ADT/SmallVector.h"
  34 #include "llvm/ADT/Statistic.h"
  35 #include <vector>
  36 using namespace llvm;
  37
  38 static cl::opt<bool>
  39 DisableSharing("no-stack-slot-sharing",
  40              cl::init(false), cl::Hidden,
  41              cl::desc("Suppress slot sharing during stack coloring"));
  42
  43 static cl::opt<bool>
  44 ColorWithRegsOpt("color-ss-with-regs",
  45                  cl::init(false), cl::Hidden,
  46                  cl::desc("Color stack slots with free registers"));
  47
  48
  49 static cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden);
  50
  51 STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring");
  52 STATISTIC(NumRegRepl,    "Number of stack slot refs replaced with reg refs");
  53 STATISTIC(NumLoadElim,   "Number of loads eliminated");
  54 STATISTIC(NumStoreElim,  "Number of stores eliminated");
  55 STATISTIC(NumDead,       "Number of trivially dead stack accesses eliminated");
  56
  57 namespace {
  58   class StackSlotColoring : public MachineFunctionPass {
  59     bool ColorWithRegs;
  60     LiveStacks* LS;
  61     VirtRegMap* VRM;
  62     MachineFrameInfo *MFI;
  63     MachineRegisterInfo *MRI;
  64     const TargetInstrInfo  *TII;
  65     const TargetRegisterInfo *TRI;
  66     const MachineLoopInfo *loopInfo;
  67
  68     // SSIntervals - Spill slot intervals.
  69     std::vector<LiveInterval*> SSIntervals;
  70
  71     // SSRefs - Keep a list of frame index references for each spill slot.
  72     SmallVector<SmallVector<MachineInstr*, 8>, 16> SSRefs;
  73
  74     // OrigAlignments - Alignments of stack objects before coloring.
  75     SmallVector<unsigned, 16> OrigAlignments;
  76
  77     // OrigSizes - Sizess of stack objects before coloring.
  78     SmallVector<unsigned, 16> OrigSizes;
  79
  80     // AllColors - If index is set, it's a spill slot, i.e. color.
  81     // FIXME: This assumes PEI locate spill slot with smaller indices
  82     // closest to stack pointer / frame pointer. Therefore, smaller
  83     // index == better color.
  84     BitVector AllColors;
  85
  86     // NextColor - Next "color" that's not yet used.
  87     int NextColor;
  88
  89     // UsedColors - "Colors" that have been assigned.
  90     BitVector UsedColors;
  91
  92     // Assignments - Color to intervals mapping.
  93     SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments;
  94
  95   public:
  96     static char ID; // Pass identification
  97     StackSlotColoring() :
  98       MachineFunctionPass(ID), ColorWithRegs(false), NextColor(-1) {}
  99     StackSlotColoring(bool RegColor) :
 100       MachineFunctionPass(ID), ColorWithRegs(RegColor), NextColor(-1) {}
 101
 102     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 103       AU.setPreservesCFG();
 104       AU.addRequired<SlotIndexes>();
 105       AU.addPreserved<SlotIndexes>();
 106       AU.addRequired<LiveStacks>();
 107       AU.addRequired<VirtRegMap>();
 108       AU.addPreserved<VirtRegMap>();
 109       AU.addRequired<MachineLoopInfo>();
 110       AU.addPreserved<MachineLoopInfo>();
 111       AU.addPreservedID(MachineDominatorsID);
 112       MachineFunctionPass::getAnalysisUsage(AU);
 113     }
 114
 115     virtual bool runOnMachineFunction(MachineFunction &MF);
 116     virtual const char* getPassName() const {
 117       return "Stack Slot Coloring";
 118     }
 119
 120   private:
 121     void InitializeSlots();
 122     void ScanForSpillSlotRefs(MachineFunction &MF);
 123     bool OverlapWithAssignments(LiveInterval *li, int Color) const;
 124     int ColorSlot(LiveInterval *li);
 125     bool ColorSlots(MachineFunction &MF);
 126     bool ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping,
 127                                 SmallVector<SmallVector<int, 4>, 16> &RevMap,
 128                                 BitVector &SlotIsReg);
 129     void RewriteInstruction(MachineInstr *MI, int OldFI, int NewFI,
 130                             MachineFunction &MF);
 131     bool PropagateBackward(MachineBasicBlock::iterator MII,
 132                            MachineBasicBlock *MBB,
 133                            unsigned OldReg, unsigned NewReg);
 134     bool PropagateForward(MachineBasicBlock::iterator MII,
 135                           MachineBasicBlock *MBB,
 136                           unsigned OldReg, unsigned NewReg);
 137     void UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI,
 138                                     unsigned Reg, const TargetRegisterClass *RC,
 139                                     SmallSet<unsigned, 4> &Defs,
 140                                     MachineFunction &MF);
 141     bool AllMemRefsCanBeUnfolded(int SS);
 142     bool RemoveDeadStores(MachineBasicBlock* MBB);
 143   };
 144 } // end anonymous namespace
 145
 146 char StackSlotColoring::ID = 0;
 147
 148 INITIALIZE_PASS_BEGIN(StackSlotColoring, "stack-slot-coloring",
 149                 "Stack Slot Coloring", false, false)
 150 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
 151 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
 152 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
 153 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 154 INITIALIZE_PASS_END(StackSlotColoring, "stack-slot-coloring",
 155                 "Stack Slot Coloring", false, false)
 156
 157 FunctionPass *llvm::createStackSlotColoringPass(bool RegColor) {
 158   return new StackSlotColoring(RegColor);
 159 }
 160
 161 namespace {
 162   // IntervalSorter - Comparison predicate that sort live intervals by
 163   // their weight.
 164   struct IntervalSorter {
 165     bool operator()(LiveInterval* LHS, LiveInterval* RHS) const {
 166       return LHS->weight > RHS->weight;
 167     }
 168   };
 169 }
 170
 171 /// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot
 172 /// references and update spill slot weights.
 173 void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) {
 174   SSRefs.resize(MFI->getObjectIndexEnd());
 175
 176   // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands.
 177   for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
 178        MBBI != E; ++MBBI) {
 179     MachineBasicBlock *MBB = &*MBBI;
 180     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
 181     for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end();
 182          MII != EE; ++MII) {
 183       MachineInstr *MI = &*MII;
 184       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 185         MachineOperand &MO = MI->getOperand(i);
 186         if (!MO.isFI())
 187           continue;
 188         int FI = MO.getIndex();
 189         if (FI < 0)
 190           continue;
 191         if (!LS->hasInterval(FI))
 192           continue;
 193         LiveInterval &li = LS->getInterval(FI);
 194         if (!MI->isDebugValue())
 195           li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth);
 196         SSRefs[FI].push_back(MI);
 197       }
 198     }
 199   }
 200 }
 201
 202 /// InitializeSlots - Process all spill stack slot liveintervals and add them
 203 /// to a sorted (by weight) list.
 204 void StackSlotColoring::InitializeSlots() {
 205   int LastFI = MFI->getObjectIndexEnd();
 206   OrigAlignments.resize(LastFI);
 207   OrigSizes.resize(LastFI);
 208   AllColors.resize(LastFI);
 209   UsedColors.resize(LastFI);
 210   Assignments.resize(LastFI);
 211
 212   // Gather all spill slots into a list.
 213   DEBUG(dbgs() << "Spill slot intervals:\n");
 214   for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) {
 215     LiveInterval &li = i->second;
 216     DEBUG(li.dump());
 217     int FI = li.getStackSlotIndex();
 218     if (MFI->isDeadObjectIndex(FI))
 219       continue;
 220     SSIntervals.push_back(&li);
 221     OrigAlignments[FI] = MFI->getObjectAlignment(FI);
 222     OrigSizes[FI]      = MFI->getObjectSize(FI);
 223     AllColors.set(FI);
 224   }
 225   DEBUG(dbgs() << '\n');
 226
 227   // Sort them by weight.
 228   std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
 229
 230   // Get first "color".
 231   NextColor = AllColors.find_first();
 232 }
 233
 234 /// OverlapWithAssignments - Return true if LiveInterval overlaps with any
 235 /// LiveIntervals that have already been assigned to the specified color.
 236 bool
 237 StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const {
 238   const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color];
 239   for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) {
 240     LiveInterval *OtherLI = OtherLIs[i];
 241     if (OtherLI->overlaps(*li))
 242       return true;
 243   }
 244   return false;
 245 }
 246
 247 /// ColorSlotsWithFreeRegs - If there are any free registers available, try
 248 /// replacing spill slots references with registers instead.
 249 bool
 250 StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping,
 251                                    SmallVector<SmallVector<int, 4>, 16> &RevMap,
 252                                    BitVector &SlotIsReg) {
 253   if (!(ColorWithRegs || ColorWithRegsOpt) || !VRM->HasUnusedRegisters())
 254     return false;
 255
 256   bool Changed = false;
 257   DEBUG(dbgs() << "Assigning unused registers to spill slots:\n");
 258   for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
 259     LiveInterval *li = SSIntervals[i];
 260     int SS = li->getStackSlotIndex();
 261     if (!UsedColors[SS] || li->weight < 20)
 262       // If the weight is < 20, i.e. two references in a loop with depth 1,
 263       // don't bother with it.
 264       continue;
 265
 266     // These slots allow to share the same registers.
 267     bool AllColored = true;
 268     SmallVector<unsigned, 4> ColoredRegs;
 269     for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) {
 270       int RSS = RevMap[SS][j];
 271       const TargetRegisterClass *RC = LS->getIntervalRegClass(RSS);
 272       // If it's not colored to another stack slot, try coloring it
 273       // to a "free" register.
 274       if (!RC) {
 275         AllColored = false;
 276         continue;
 277       }
 278       unsigned Reg = VRM->getFirstUnusedRegister(RC);
 279       if (!Reg) {
 280         AllColored = false;
 281         continue;
 282       }
 283       if (!AllMemRefsCanBeUnfolded(RSS)) {
 284         AllColored = false;
 285         continue;
 286       } else {
 287         DEBUG(dbgs() << "Assigning fi#" << RSS << " to "
 288                      << TRI->getName(Reg) << '\n');
 289         ColoredRegs.push_back(Reg);
 290         SlotMapping[RSS] = Reg;
 291         SlotIsReg.set(RSS);
 292         Changed = true;
 293       }
 294     }
 295
 296     // Register and its sub-registers are no longer free.
 297     while (!ColoredRegs.empty()) {
 298       unsigned Reg = ColoredRegs.back();
 299       ColoredRegs.pop_back();
 300       VRM->setRegisterUsed(Reg);
 301       // If reg is a callee-saved register, it will have to be spilled in
 302       // the prologue.
 303       MRI->setPhysRegUsed(Reg);
 304       for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
 305         VRM->setRegisterUsed(*AS);
 306         MRI->setPhysRegUsed(*AS);
 307       }
 308     }
 309     // This spill slot is dead after the rewrites
 310     if (AllColored) {
 311       MFI->RemoveStackObject(SS);
 312       ++NumEliminated;
 313     }
 314   }
 315   DEBUG(dbgs() << '\n');
 316
 317   return Changed;
 318 }
 319
 320 /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.
 321 ///
 322 int StackSlotColoring::ColorSlot(LiveInterval *li) {
 323   int Color = -1;
 324   bool Share = false;
 325   if (!DisableSharing) {
 326     // Check if it's possible to reuse any of the used colors.
 327     Color = UsedColors.find_first();
 328     while (Color != -1) {
 329       if (!OverlapWithAssignments(li, Color)) {
 330         Share = true;
 331         ++NumEliminated;
 332         break;
 333       }
 334       Color = UsedColors.find_next(Color);
 335     }
 336   }
 337
 338   // Assign it to the first available color (assumed to be the best) if it's
 339   // not possible to share a used color with other objects.
 340   if (!Share) {
 341     assert(NextColor != -1 && "No more spill slots?");
 342     Color = NextColor;
 343     UsedColors.set(Color);
 344     NextColor = AllColors.find_next(NextColor);
 345   }
 346
 347   // Record the assignment.
 348   Assignments[Color].push_back(li);
 349   int FI = li->getStackSlotIndex();
 350   DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n");
 351
 352   // Change size and alignment of the allocated slot. If there are multiple
 353   // objects sharing the same slot, then make sure the size and alignment
 354   // are large enough for all.
 355   unsigned Align = OrigAlignments[FI];
 356   if (!Share || Align > MFI->getObjectAlignment(Color))
 357     MFI->setObjectAlignment(Color, Align);
 358   int64_t Size = OrigSizes[FI];
 359   if (!Share || Size > MFI->getObjectSize(Color))
 360     MFI->setObjectSize(Color, Size);
 361   return Color;
 362 }
 363
 364 /// Colorslots - Color all spill stack slots and rewrite all frameindex machine
 365 /// operands in the function.
 366 bool StackSlotColoring::ColorSlots(MachineFunction &MF) {
 367   unsigned NumObjs = MFI->getObjectIndexEnd();
 368   SmallVector<int, 16> SlotMapping(NumObjs, -1);
 369   SmallVector<float, 16> SlotWeights(NumObjs, 0.0);
 370   SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs);
 371   BitVector SlotIsReg(NumObjs);
 372   BitVector UsedColors(NumObjs);
 373
 374   DEBUG(dbgs() << "Color spill slot intervals:\n");
 375   bool Changed = false;
 376   for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
 377     LiveInterval *li = SSIntervals[i];
 378     int SS = li->getStackSlotIndex();
 379     int NewSS = ColorSlot(li);
 380     assert(NewSS >= 0 && "Stack coloring failed?");
 381     SlotMapping[SS] = NewSS;
 382     RevMap[NewSS].push_back(SS);
 383     SlotWeights[NewSS] += li->weight;
 384     UsedColors.set(NewSS);
 385     Changed |= (SS != NewSS);
 386   }
 387
 388   DEBUG(dbgs() << "\nSpill slots after coloring:\n");
 389   for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
 390     LiveInterval *li = SSIntervals[i];
 391     int SS = li->getStackSlotIndex();
 392     li->weight = SlotWeights[SS];
 393   }
 394   // Sort them by new weight.
 395   std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
 396
 397 #ifndef NDEBUG
 398   for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i)
 399     DEBUG(SSIntervals[i]->dump());
 400   DEBUG(dbgs() << '\n');
 401 #endif
 402
 403   // Can we "color" a stack slot with a unused register?
 404   Changed |= ColorSlotsWithFreeRegs(SlotMapping, RevMap, SlotIsReg);
 405
 406   if (!Changed)
 407     return false;
 408
 409   // Rewrite all MO_FrameIndex operands.
 410   SmallVector<SmallSet<unsigned, 4>, 4> NewDefs(MF.getNumBlockIDs());
 411   for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) {
 412     bool isReg = SlotIsReg[SS];
 413     int NewFI = SlotMapping[SS];
 414     if (NewFI == -1 || (NewFI == (int)SS && !isReg))
 415       continue;
 416
 417     const TargetRegisterClass *RC = LS->getIntervalRegClass(SS);
 418     SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS];
 419     for (unsigned i = 0, e = RefMIs.size(); i != e; ++i)
 420       if (!isReg)
 421         RewriteInstruction(RefMIs[i], SS, NewFI, MF);
 422       else {
 423         // Rewrite to use a register instead.
 424         unsigned MBBId = RefMIs[i]->getParent()->getNumber();
 425         SmallSet<unsigned, 4> &Defs = NewDefs[MBBId];
 426         UnfoldAndRewriteInstruction(RefMIs[i], SS, NewFI, RC, Defs, MF);
 427       }
 428   }
 429
 430   // Delete unused stack slots.
 431   while (NextColor != -1) {
 432     DEBUG(dbgs() << "Removing unused stack object fi#" << NextColor << "\n");
 433     MFI->RemoveStackObject(NextColor);
 434     NextColor = AllColors.find_next(NextColor);
 435   }
 436
 437   return true;
 438 }
 439
 440 /// AllMemRefsCanBeUnfolded - Return true if all references of the specified
 441 /// spill slot index can be unfolded.
 442 bool StackSlotColoring::AllMemRefsCanBeUnfolded(int SS) {
 443   SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS];
 444   for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) {
 445     MachineInstr *MI = RefMIs[i];
 446     if (TII->isLoadFromStackSlot(MI, SS) ||
 447         TII->isStoreToStackSlot(MI, SS))
 448       // Restore and spill will become copies.
 449       return true;
 450     if (!TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), false, false))
 451       return false;
 452     for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
 453       MachineOperand &MO = MI->getOperand(j);
 454       if (MO.isFI() && MO.getIndex() != SS)
 455         // If it uses another frameindex, we can, currently* unfold it.
 456         return false;
 457     }
 458   }
 459   return true;
 460 }
 461
 462 /// RewriteInstruction - Rewrite specified instruction by replacing references
 463 /// to old frame index with new one.
 464 void StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI,
 465                                            int NewFI, MachineFunction &MF) {
 466   // Update the operands.
 467   for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) {
 468     MachineOperand &MO = MI->getOperand(i);
 469     if (!MO.isFI())
 470       continue;
 471     int FI = MO.getIndex();
 472     if (FI != OldFI)
 473       continue;
 474     MO.setIndex(NewFI);
 475   }
 476
 477   // Update the memory references. This changes the MachineMemOperands
 478   // directly. They may be in use by multiple instructions, however all
 479   // instructions using OldFI are being rewritten to use NewFI.
 480   const Value *OldSV = PseudoSourceValue::getFixedStack(OldFI);
 481   const Value *NewSV = PseudoSourceValue::getFixedStack(NewFI);
 482   for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
 483        E = MI->memoperands_end(); I != E; ++I)
 484     if ((*I)->getValue() == OldSV)
 485       (*I)->setValue(NewSV);
 486 }
 487
 488 /// PropagateBackward - Traverse backward and look for the definition of
 489 /// OldReg. If it can successfully update all of the references with NewReg,
 490 /// do so and return true.
 491 bool StackSlotColoring::PropagateBackward(MachineBasicBlock::iterator MII,
 492                                           MachineBasicBlock *MBB,
 493                                           unsigned OldReg, unsigned NewReg) {
 494   if (MII == MBB->begin())
 495     return false;
 496
 497   SmallVector<MachineOperand*, 4> Uses;
 498   SmallVector<MachineOperand*, 4> Refs;
 499   while (--MII != MBB->begin()) {
 500     bool FoundDef = false;  // Not counting 2address def.
 501
 502     Uses.clear();
 503     const TargetInstrDesc &TID = MII->getDesc();
 504     for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
 505       MachineOperand &MO = MII->getOperand(i);
 506       if (!MO.isReg())
 507         continue;
 508       unsigned Reg = MO.getReg();
 509       if (Reg == 0)
 510         continue;
 511       if (Reg == OldReg) {
 512         if (MO.isImplicit())
 513           return false;
 514
 515         // Abort the use is actually a sub-register def. We don't have enough
 516         // information to figure out if it is really legal.
 517         if (MO.getSubReg() || MII->isSubregToReg())
 518           return false;
 519
 520         const TargetRegisterClass *RC = TID.OpInfo[i].getRegClass(TRI);
 521         if (RC && !RC->contains(NewReg))
 522           return false;
 523
 524         if (MO.isUse()) {
 525           Uses.push_back(&MO);
 526         } else {
 527           Refs.push_back(&MO);
 528           if (!MII->isRegTiedToUseOperand(i))
 529             FoundDef = true;
 530         }
 531       } else if (TRI->regsOverlap(Reg, NewReg)) {
 532         return false;
 533       } else if (TRI->regsOverlap(Reg, OldReg)) {
 534         if (!MO.isUse() || !MO.isKill())
 535           return false;
 536       }
 537     }
 538
 539     if (FoundDef) {
 540       // Found non-two-address def. Stop here.
 541       for (unsigned i = 0, e = Refs.size(); i != e; ++i)
 542         Refs[i]->setReg(NewReg);
 543       return true;
 544     }
 545
 546     // Two-address uses must be updated as well.
 547     for (unsigned i = 0, e = Uses.size(); i != e; ++i)
 548       Refs.push_back(Uses[i]);
 549   }
 550   return false;
 551 }
 552
 553 /// PropagateForward - Traverse forward and look for the kill of OldReg. If
 554 /// it can successfully update all of the uses with NewReg, do so and
 555 /// return true.
 556 bool StackSlotColoring::PropagateForward(MachineBasicBlock::iterator MII,
 557                                          MachineBasicBlock *MBB,
 558                                          unsigned OldReg, unsigned NewReg) {
 559   if (MII == MBB->end())
 560     return false;
 561
 562   SmallVector<MachineOperand*, 4> Uses;
 563   while (++MII != MBB->end()) {
 564     bool FoundKill = false;
 565     const TargetInstrDesc &TID = MII->getDesc();
 566     for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
 567       MachineOperand &MO = MII->getOperand(i);
 568       if (!MO.isReg())
 569         continue;
 570       unsigned Reg = MO.getReg();
 571       if (Reg == 0)
 572         continue;
 573       if (Reg == OldReg) {
 574         if (MO.isDef() || MO.isImplicit())
 575           return false;
 576
 577         // Abort the use is actually a sub-register use. We don't have enough
 578         // information to figure out if it is really legal.
 579         if (MO.getSubReg())
 580           return false;
 581
 582         const TargetRegisterClass *RC = TID.OpInfo[i].getRegClass(TRI);
 583         if (RC && !RC->contains(NewReg))
 584           return false;
 585         if (MO.isKill())
 586           FoundKill = true;
 587
 588         Uses.push_back(&MO);
 589       } else if (TRI->regsOverlap(Reg, NewReg) ||
 590                  TRI->regsOverlap(Reg, OldReg))
 591         return false;
 592     }
 593     if (FoundKill) {
 594       for (unsigned i = 0, e = Uses.size(); i != e; ++i)
 595         Uses[i]->setReg(NewReg);
 596       return true;
 597     }
 598   }
 599   return false;
 600 }
 601
 602 /// UnfoldAndRewriteInstruction - Rewrite specified instruction by unfolding
 603 /// folded memory references and replacing those references with register
 604 /// references instead.
 605 void
 606 StackSlotColoring::UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI,
 607                                                unsigned Reg,
 608                                                const TargetRegisterClass *RC,
 609                                                SmallSet<unsigned, 4> &Defs,
 610                                                MachineFunction &MF) {
 611   MachineBasicBlock *MBB = MI->getParent();
 612   if (unsigned DstReg = TII->isLoadFromStackSlot(MI, OldFI)) {
 613     if (PropagateForward(MI, MBB, DstReg, Reg)) {
 614       DEBUG(dbgs() << "Eliminated load: ");
 615       DEBUG(MI->dump());
 616       ++NumLoadElim;
 617     } else {
 618       BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(TargetOpcode::COPY),
 619               DstReg).addReg(Reg);
 620       ++NumRegRepl;
 621     }
 622
 623     if (!Defs.count(Reg)) {
 624       // If this is the first use of Reg in this MBB and it wasn't previously
 625       // defined in MBB, add it to livein.
 626       MBB->addLiveIn(Reg);
 627       Defs.insert(Reg);
 628     }
 629   } else if (unsigned SrcReg = TII->isStoreToStackSlot(MI, OldFI)) {
 630     if (MI->killsRegister(SrcReg) && PropagateBackward(MI, MBB, SrcReg, Reg)) {
 631       DEBUG(dbgs() << "Eliminated store: ");
 632       DEBUG(MI->dump());
 633       ++NumStoreElim;
 634     } else {
 635       BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(TargetOpcode::COPY), Reg)
 636         .addReg(SrcReg);
 637       ++NumRegRepl;
 638     }
 639
 640     // Remember reg has been defined in MBB.
 641     Defs.insert(Reg);
 642   } else {
 643     SmallVector<MachineInstr*, 4> NewMIs;
 644     bool Success = TII->unfoldMemoryOperand(MF, MI, Reg, false, false, NewMIs);
 645     Success = Success; // Silence compiler warning.
 646     assert(Success && "Failed to unfold!");
 647     MachineInstr *NewMI = NewMIs[0];
 648     MBB->insert(MI, NewMI);
 649     ++NumRegRepl;
 650
 651     if (NewMI->readsRegister(Reg)) {
 652       if (!Defs.count(Reg))
 653         // If this is the first use of Reg in this MBB and it wasn't previously
 654         // defined in MBB, add it to livein.
 655         MBB->addLiveIn(Reg);
 656       Defs.insert(Reg);
 657     }
 658   }
 659   MBB->erase(MI);
 660 }
 661
 662 /// RemoveDeadStores - Scan through a basic block and look for loads followed
 663 /// by stores.  If they're both using the same stack slot, then the store is
 664 /// definitely dead.  This could obviously be much more aggressive (consider
 665 /// pairs with instructions between them), but such extensions might have a
 666 /// considerable compile time impact.
 667 bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) {
 668   // FIXME: This could be much more aggressive, but we need to investigate
 669   // the compile time impact of doing so.
 670   bool changed = false;
 671
 672   SmallVector<MachineInstr*, 4> toErase;
 673
 674   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
 675        I != E; ++I) {
 676     if (DCELimit != -1 && (int)NumDead >= DCELimit)
 677       break;
 678
 679     MachineBasicBlock::iterator NextMI = llvm::next(I);
 680     if (NextMI == MBB->end()) continue;
 681
 682     int FirstSS, SecondSS;
 683     unsigned LoadReg = 0;
 684     unsigned StoreReg = 0;
 685     if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue;
 686     if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue;
 687     if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue;
 688
 689     ++NumDead;
 690     changed = true;
 691
 692     if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) {
 693       ++NumDead;
 694       toErase.push_back(I);
 695     }
 696
 697     toErase.push_back(NextMI);
 698     ++I;
 699   }
 700
 701   for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(),
 702        E = toErase.end(); I != E; ++I)
 703     (*I)->eraseFromParent();
 704
 705   return changed;
 706 }
 707
 708
 709 bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
 710   DEBUG({
 711       dbgs() << "********** Stack Slot Coloring **********\n"
 712              << "********** Function: "
 713              << MF.getFunction()->getName() << '\n';
 714     });
 715
 716   MFI = MF.getFrameInfo();
 717   MRI = &MF.getRegInfo();
 718   TII = MF.getTarget().getInstrInfo();
 719   TRI = MF.getTarget().getRegisterInfo();
 720   LS = &getAnalysis<LiveStacks>();
 721   VRM = &getAnalysis<VirtRegMap>();
 722   loopInfo = &getAnalysis<MachineLoopInfo>();
 723
 724   bool Changed = false;
 725
 726   unsigned NumSlots = LS->getNumIntervals();
 727   if (NumSlots < 2) {
 728     if (NumSlots == 0 || !VRM->HasUnusedRegisters())
 729       // Nothing to do!
 730       return false;
 731   }
 732
 733   // If there are calls to setjmp or sigsetjmp, don't perform stack slot
 734   // coloring. The stack could be modified before the longjmp is executed,
 735   // resulting in the wrong value being used afterwards. (See
 736   // <rdar://problem/8007500>.)
 737   if (MF.callsSetJmp())
 738     return false;
 739
 740   // Gather spill slot references
 741   ScanForSpillSlotRefs(MF);
 742   InitializeSlots();
 743   Changed = ColorSlots(MF);
 744
 745   NextColor = -1;
 746   SSIntervals.clear();
 747   for (unsigned i = 0, e = SSRefs.size(); i != e; ++i)
 748     SSRefs[i].clear();
 749   SSRefs.clear();
 750   OrigAlignments.clear();
 751   OrigSizes.clear();
 752   AllColors.clear();
 753   UsedColors.clear();
 754   for (unsigned i = 0, e = Assignments.size(); i != e; ++i)
 755     Assignments[i].clear();
 756   Assignments.clear();
 757
 758   if (Changed) {
 759     for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
 760       Changed |= RemoveDeadStores(I);
 761   }
 762
 763   return Changed;
 764 }