1193323Sed//===-- StackSlotColoring.cpp - Stack slot coloring pass. -----------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the stack slot coloring pass. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14245431Sdim#define DEBUG_TYPE "stackslotcoloring" 15193323Sed#include "llvm/CodeGen/Passes.h" 16252723Sdim#include "llvm/ADT/BitVector.h" 17252723Sdim#include "llvm/ADT/SmallVector.h" 18252723Sdim#include "llvm/ADT/Statistic.h" 19193323Sed#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20193323Sed#include "llvm/CodeGen/LiveStackAnalysis.h" 21263509Sdim#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 22193323Sed#include "llvm/CodeGen/MachineFrameInfo.h" 23210299Sed#include "llvm/CodeGen/MachineInstrBuilder.h" 24198090Srdivacky#include "llvm/CodeGen/MachineMemOperand.h" 25193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 26193323Sed#include "llvm/CodeGen/PseudoSourceValue.h" 27252723Sdim#include "llvm/IR/Module.h" 28193323Sed#include "llvm/Support/CommandLine.h" 29193323Sed#include "llvm/Support/Debug.h" 30263509Sdim#include "llvm/Support/raw_ostream.h" 31193323Sed#include "llvm/Target/TargetInstrInfo.h" 32193323Sed#include "llvm/Target/TargetMachine.h" 33193323Sed#include <vector> 34193323Sedusing namespace llvm; 35193323Sed 36193323Sedstatic cl::opt<bool> 37193323SedDisableSharing("no-stack-slot-sharing", 38193323Sed cl::init(false), cl::Hidden, 39193323Sed cl::desc("Suppress slot sharing during stack coloring")); 40193323Sed 41193323Sedstatic cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden); 42193323Sed 43193323SedSTATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); 44193323SedSTATISTIC(NumDead, "Number of trivially dead stack accesses eliminated"); 45193323Sed 46193323Sednamespace { 47198892Srdivacky class StackSlotColoring : public MachineFunctionPass { 48193323Sed LiveStacks* LS; 49193323Sed MachineFrameInfo *MFI; 50193323Sed const TargetInstrInfo *TII; 51263509Sdim const MachineBlockFrequencyInfo *MBFI; 52193323Sed 53193323Sed // SSIntervals - Spill slot intervals. 54193323Sed std::vector<LiveInterval*> SSIntervals; 55193323Sed 56263509Sdim // SSRefs - Keep a list of MachineMemOperands for each spill slot. 57263509Sdim // MachineMemOperands can be shared between instructions, so we need 58263509Sdim // to be careful that renames like [FI0, FI1] -> [FI1, FI2] do not 59263509Sdim // become FI0 -> FI1 -> FI2. 60263509Sdim SmallVector<SmallVector<MachineMemOperand *, 8>, 16> SSRefs; 61193323Sed 62193323Sed // OrigAlignments - Alignments of stack objects before coloring. 63193323Sed SmallVector<unsigned, 16> OrigAlignments; 64193323Sed 65193323Sed // OrigSizes - Sizess of stack objects before coloring. 66193323Sed SmallVector<unsigned, 16> OrigSizes; 67193323Sed 68193323Sed // AllColors - If index is set, it's a spill slot, i.e. color. 69193323Sed // FIXME: This assumes PEI locate spill slot with smaller indices 70193323Sed // closest to stack pointer / frame pointer. Therefore, smaller 71193323Sed // index == better color. 72193323Sed BitVector AllColors; 73193323Sed 74193323Sed // NextColor - Next "color" that's not yet used. 75193323Sed int NextColor; 76193323Sed 77193323Sed // UsedColors - "Colors" that have been assigned. 78193323Sed BitVector UsedColors; 79193323Sed 80193323Sed // Assignments - Color to intervals mapping. 81193323Sed SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments; 82193323Sed 83193323Sed public: 84193323Sed static char ID; // Pass identification 85193323Sed StackSlotColoring() : 86245431Sdim MachineFunctionPass(ID), NextColor(-1) { 87218893Sdim initializeStackSlotColoringPass(*PassRegistry::getPassRegistry()); 88218893Sdim } 89235633Sdim 90193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 91198090Srdivacky AU.setPreservesCFG(); 92198892Srdivacky AU.addRequired<SlotIndexes>(); 93198892Srdivacky AU.addPreserved<SlotIndexes>(); 94193323Sed AU.addRequired<LiveStacks>(); 95263509Sdim AU.addRequired<MachineBlockFrequencyInfo>(); 96263509Sdim AU.addPreserved<MachineBlockFrequencyInfo>(); 97193323Sed AU.addPreservedID(MachineDominatorsID); 98193323Sed MachineFunctionPass::getAnalysisUsage(AU); 99193323Sed } 100193323Sed 101193323Sed virtual bool runOnMachineFunction(MachineFunction &MF); 102193323Sed 103193323Sed private: 104193323Sed void InitializeSlots(); 105193323Sed void ScanForSpillSlotRefs(MachineFunction &MF); 106193323Sed bool OverlapWithAssignments(LiveInterval *li, int Color) const; 107193323Sed int ColorSlot(LiveInterval *li); 108193323Sed bool ColorSlots(MachineFunction &MF); 109263509Sdim void RewriteInstruction(MachineInstr *MI, SmallVectorImpl<int> &SlotMapping, 110193323Sed MachineFunction &MF); 111193323Sed bool RemoveDeadStores(MachineBasicBlock* MBB); 112193323Sed }; 113193323Sed} // end anonymous namespace 114193323Sed 115193323Sedchar StackSlotColoring::ID = 0; 116235633Sdimchar &llvm::StackSlotColoringID = StackSlotColoring::ID; 117193323Sed 118218893SdimINITIALIZE_PASS_BEGIN(StackSlotColoring, "stack-slot-coloring", 119218893Sdim "Stack Slot Coloring", false, false) 120218893SdimINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 121218893SdimINITIALIZE_PASS_DEPENDENCY(LiveStacks) 122218893SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 123218893SdimINITIALIZE_PASS_END(StackSlotColoring, "stack-slot-coloring", 124218893Sdim "Stack Slot Coloring", false, false) 125193323Sed 126193323Sednamespace { 127193323Sed // IntervalSorter - Comparison predicate that sort live intervals by 128193323Sed // their weight. 129193323Sed struct IntervalSorter { 130193323Sed bool operator()(LiveInterval* LHS, LiveInterval* RHS) const { 131193323Sed return LHS->weight > RHS->weight; 132193323Sed } 133193323Sed }; 134193323Sed} 135193323Sed 136193323Sed/// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot 137193323Sed/// references and update spill slot weights. 138193323Sedvoid StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) { 139193323Sed SSRefs.resize(MFI->getObjectIndexEnd()); 140193323Sed 141193323Sed // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. 142193323Sed for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 143193323Sed MBBI != E; ++MBBI) { 144193323Sed MachineBasicBlock *MBB = &*MBBI; 145263509Sdim BlockFrequency Freq = MBFI->getBlockFreq(MBB); 146193323Sed for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); 147193323Sed MII != EE; ++MII) { 148193323Sed MachineInstr *MI = &*MII; 149193323Sed for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 150193323Sed MachineOperand &MO = MI->getOperand(i); 151193323Sed if (!MO.isFI()) 152193323Sed continue; 153193323Sed int FI = MO.getIndex(); 154193323Sed if (FI < 0) 155193323Sed continue; 156193323Sed if (!LS->hasInterval(FI)) 157193323Sed continue; 158193323Sed LiveInterval &li = LS->getInterval(FI); 159207618Srdivacky if (!MI->isDebugValue()) 160263509Sdim li.weight += LiveIntervals::getSpillWeight(false, true, Freq); 161193323Sed } 162263509Sdim for (MachineInstr::mmo_iterator MMOI = MI->memoperands_begin(), 163263509Sdim EE = MI->memoperands_end(); MMOI != EE; ++MMOI) { 164263509Sdim MachineMemOperand *MMO = *MMOI; 165263509Sdim if (const Value *V = MMO->getValue()) { 166263509Sdim if (const FixedStackPseudoSourceValue *FSV = 167263509Sdim dyn_cast<FixedStackPseudoSourceValue>(V)) { 168263509Sdim int FI = FSV->getFrameIndex(); 169263509Sdim if (FI >= 0) 170263509Sdim SSRefs[FI].push_back(MMO); 171263509Sdim } 172263509Sdim } 173263509Sdim } 174193323Sed } 175193323Sed } 176193323Sed} 177193323Sed 178193323Sed/// InitializeSlots - Process all spill stack slot liveintervals and add them 179193323Sed/// to a sorted (by weight) list. 180193323Sedvoid StackSlotColoring::InitializeSlots() { 181193323Sed int LastFI = MFI->getObjectIndexEnd(); 182193323Sed OrigAlignments.resize(LastFI); 183193323Sed OrigSizes.resize(LastFI); 184193323Sed AllColors.resize(LastFI); 185193323Sed UsedColors.resize(LastFI); 186193323Sed Assignments.resize(LastFI); 187193323Sed 188193323Sed // Gather all spill slots into a list. 189202375Srdivacky DEBUG(dbgs() << "Spill slot intervals:\n"); 190193323Sed for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { 191193323Sed LiveInterval &li = i->second; 192193323Sed DEBUG(li.dump()); 193218893Sdim int FI = TargetRegisterInfo::stackSlot2Index(li.reg); 194193323Sed if (MFI->isDeadObjectIndex(FI)) 195193323Sed continue; 196193323Sed SSIntervals.push_back(&li); 197193323Sed OrigAlignments[FI] = MFI->getObjectAlignment(FI); 198193323Sed OrigSizes[FI] = MFI->getObjectSize(FI); 199193323Sed AllColors.set(FI); 200193323Sed } 201202375Srdivacky DEBUG(dbgs() << '\n'); 202193323Sed 203193323Sed // Sort them by weight. 204193323Sed std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 205193323Sed 206193323Sed // Get first "color". 207193323Sed NextColor = AllColors.find_first(); 208193323Sed} 209193323Sed 210193323Sed/// OverlapWithAssignments - Return true if LiveInterval overlaps with any 211193323Sed/// LiveIntervals that have already been assigned to the specified color. 212193323Sedbool 213193323SedStackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { 214263509Sdim const SmallVectorImpl<LiveInterval *> &OtherLIs = Assignments[Color]; 215193323Sed for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) { 216193323Sed LiveInterval *OtherLI = OtherLIs[i]; 217193323Sed if (OtherLI->overlaps(*li)) 218193323Sed return true; 219193323Sed } 220193323Sed return false; 221193323Sed} 222193323Sed 223193323Sed/// ColorSlot - Assign a "color" (stack slot) to the specified stack slot. 224193323Sed/// 225193323Sedint StackSlotColoring::ColorSlot(LiveInterval *li) { 226193323Sed int Color = -1; 227193323Sed bool Share = false; 228193323Sed if (!DisableSharing) { 229193323Sed // Check if it's possible to reuse any of the used colors. 230193323Sed Color = UsedColors.find_first(); 231193323Sed while (Color != -1) { 232193323Sed if (!OverlapWithAssignments(li, Color)) { 233193323Sed Share = true; 234193323Sed ++NumEliminated; 235193323Sed break; 236193323Sed } 237193323Sed Color = UsedColors.find_next(Color); 238193323Sed } 239193323Sed } 240193323Sed 241193323Sed // Assign it to the first available color (assumed to be the best) if it's 242193323Sed // not possible to share a used color with other objects. 243193323Sed if (!Share) { 244193323Sed assert(NextColor != -1 && "No more spill slots?"); 245193323Sed Color = NextColor; 246193323Sed UsedColors.set(Color); 247193323Sed NextColor = AllColors.find_next(NextColor); 248193323Sed } 249193323Sed 250193323Sed // Record the assignment. 251193323Sed Assignments[Color].push_back(li); 252218893Sdim int FI = TargetRegisterInfo::stackSlot2Index(li->reg); 253202375Srdivacky DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n"); 254193323Sed 255193323Sed // Change size and alignment of the allocated slot. If there are multiple 256193323Sed // objects sharing the same slot, then make sure the size and alignment 257193323Sed // are large enough for all. 258193323Sed unsigned Align = OrigAlignments[FI]; 259193323Sed if (!Share || Align > MFI->getObjectAlignment(Color)) 260193323Sed MFI->setObjectAlignment(Color, Align); 261193323Sed int64_t Size = OrigSizes[FI]; 262193323Sed if (!Share || Size > MFI->getObjectSize(Color)) 263193323Sed MFI->setObjectSize(Color, Size); 264193323Sed return Color; 265193323Sed} 266193323Sed 267193323Sed/// Colorslots - Color all spill stack slots and rewrite all frameindex machine 268193323Sed/// operands in the function. 269193323Sedbool StackSlotColoring::ColorSlots(MachineFunction &MF) { 270193323Sed unsigned NumObjs = MFI->getObjectIndexEnd(); 271193323Sed SmallVector<int, 16> SlotMapping(NumObjs, -1); 272193323Sed SmallVector<float, 16> SlotWeights(NumObjs, 0.0); 273193323Sed SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs); 274193323Sed BitVector UsedColors(NumObjs); 275193323Sed 276202375Srdivacky DEBUG(dbgs() << "Color spill slot intervals:\n"); 277193323Sed bool Changed = false; 278193323Sed for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 279193323Sed LiveInterval *li = SSIntervals[i]; 280218893Sdim int SS = TargetRegisterInfo::stackSlot2Index(li->reg); 281193323Sed int NewSS = ColorSlot(li); 282193323Sed assert(NewSS >= 0 && "Stack coloring failed?"); 283193323Sed SlotMapping[SS] = NewSS; 284193323Sed RevMap[NewSS].push_back(SS); 285193323Sed SlotWeights[NewSS] += li->weight; 286193323Sed UsedColors.set(NewSS); 287193323Sed Changed |= (SS != NewSS); 288193323Sed } 289193323Sed 290202375Srdivacky DEBUG(dbgs() << "\nSpill slots after coloring:\n"); 291193323Sed for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 292193323Sed LiveInterval *li = SSIntervals[i]; 293218893Sdim int SS = TargetRegisterInfo::stackSlot2Index(li->reg); 294193323Sed li->weight = SlotWeights[SS]; 295193323Sed } 296193323Sed // Sort them by new weight. 297193323Sed std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 298193323Sed 299193323Sed#ifndef NDEBUG 300193323Sed for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) 301193323Sed DEBUG(SSIntervals[i]->dump()); 302202375Srdivacky DEBUG(dbgs() << '\n'); 303193323Sed#endif 304193323Sed 305193323Sed if (!Changed) 306193323Sed return false; 307193323Sed 308263509Sdim // Rewrite all MachineMemOperands. 309193323Sed for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) { 310193323Sed int NewFI = SlotMapping[SS]; 311235633Sdim if (NewFI == -1 || (NewFI == (int)SS)) 312193323Sed continue; 313193323Sed 314263509Sdim const Value *NewSV = PseudoSourceValue::getFixedStack(NewFI); 315263509Sdim SmallVectorImpl<MachineMemOperand *> &RefMMOs = SSRefs[SS]; 316263509Sdim for (unsigned i = 0, e = RefMMOs.size(); i != e; ++i) 317263509Sdim RefMMOs[i]->setValue(NewSV); 318193323Sed } 319193323Sed 320263509Sdim // Rewrite all MO_FrameIndex operands. Look for dead stores. 321263509Sdim for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 322263509Sdim MBBI != E; ++MBBI) { 323263509Sdim MachineBasicBlock *MBB = &*MBBI; 324263509Sdim for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); 325263509Sdim MII != EE; ++MII) 326263509Sdim RewriteInstruction(MII, SlotMapping, MF); 327263509Sdim RemoveDeadStores(MBB); 328263509Sdim } 329263509Sdim 330193323Sed // Delete unused stack slots. 331193323Sed while (NextColor != -1) { 332202375Srdivacky DEBUG(dbgs() << "Removing unused stack object fi#" << NextColor << "\n"); 333193323Sed MFI->RemoveStackObject(NextColor); 334193323Sed NextColor = AllColors.find_next(NextColor); 335193323Sed } 336193323Sed 337193323Sed return true; 338193323Sed} 339193323Sed 340193323Sed/// RewriteInstruction - Rewrite specified instruction by replacing references 341193323Sed/// to old frame index with new one. 342263509Sdimvoid StackSlotColoring::RewriteInstruction(MachineInstr *MI, 343263509Sdim SmallVectorImpl<int> &SlotMapping, 344263509Sdim MachineFunction &MF) { 345198090Srdivacky // Update the operands. 346193323Sed for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) { 347193323Sed MachineOperand &MO = MI->getOperand(i); 348193323Sed if (!MO.isFI()) 349193323Sed continue; 350263509Sdim int OldFI = MO.getIndex(); 351263509Sdim if (OldFI < 0) 352193323Sed continue; 353263509Sdim int NewFI = SlotMapping[OldFI]; 354263509Sdim if (NewFI == -1 || NewFI == OldFI) 355263509Sdim continue; 356193323Sed MO.setIndex(NewFI); 357193323Sed } 358193323Sed 359263509Sdim // The MachineMemOperands have already been updated. 360193323Sed} 361193323Sed 362193323Sed 363193323Sed/// RemoveDeadStores - Scan through a basic block and look for loads followed 364193323Sed/// by stores. If they're both using the same stack slot, then the store is 365193323Sed/// definitely dead. This could obviously be much more aggressive (consider 366193323Sed/// pairs with instructions between them), but such extensions might have a 367193323Sed/// considerable compile time impact. 368193323Sedbool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) { 369193323Sed // FIXME: This could be much more aggressive, but we need to investigate 370193323Sed // the compile time impact of doing so. 371193323Sed bool changed = false; 372193323Sed 373193323Sed SmallVector<MachineInstr*, 4> toErase; 374193323Sed 375193323Sed for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 376193323Sed I != E; ++I) { 377193323Sed if (DCELimit != -1 && (int)NumDead >= DCELimit) 378193323Sed break; 379235633Sdim 380263509Sdim int FirstSS, SecondSS; 381263509Sdim if (TII->isStackSlotCopy(I, FirstSS, SecondSS) && 382263509Sdim FirstSS == SecondSS && 383263509Sdim FirstSS != -1) { 384263509Sdim ++NumDead; 385263509Sdim changed = true; 386263509Sdim toErase.push_back(I); 387263509Sdim continue; 388263509Sdim } 389263509Sdim 390200581Srdivacky MachineBasicBlock::iterator NextMI = llvm::next(I); 391193323Sed if (NextMI == MBB->end()) continue; 392235633Sdim 393193323Sed unsigned LoadReg = 0; 394193323Sed unsigned StoreReg = 0; 395193323Sed if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue; 396193323Sed if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue; 397193323Sed if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue; 398235633Sdim 399193323Sed ++NumDead; 400193323Sed changed = true; 401235633Sdim 402193323Sed if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) { 403193323Sed ++NumDead; 404193323Sed toErase.push_back(I); 405193323Sed } 406235633Sdim 407193323Sed toErase.push_back(NextMI); 408193323Sed ++I; 409193323Sed } 410235633Sdim 411263509Sdim for (SmallVectorImpl<MachineInstr *>::iterator I = toErase.begin(), 412193323Sed E = toErase.end(); I != E; ++I) 413193323Sed (*I)->eraseFromParent(); 414235633Sdim 415193323Sed return changed; 416193323Sed} 417193323Sed 418193323Sed 419193323Sedbool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { 420208599Srdivacky DEBUG({ 421208599Srdivacky dbgs() << "********** Stack Slot Coloring **********\n" 422245431Sdim << "********** Function: " << MF.getName() << '\n'; 423208599Srdivacky }); 424193323Sed 425193323Sed MFI = MF.getFrameInfo(); 426193323Sed TII = MF.getTarget().getInstrInfo(); 427193323Sed LS = &getAnalysis<LiveStacks>(); 428263509Sdim MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 429193323Sed 430193323Sed bool Changed = false; 431193323Sed 432193323Sed unsigned NumSlots = LS->getNumIntervals(); 433235633Sdim if (NumSlots == 0) 434235633Sdim // Nothing to do! 435235633Sdim return false; 436193323Sed 437208599Srdivacky // If there are calls to setjmp or sigsetjmp, don't perform stack slot 438208599Srdivacky // coloring. The stack could be modified before the longjmp is executed, 439208599Srdivacky // resulting in the wrong value being used afterwards. (See 440208599Srdivacky // <rdar://problem/8007500>.) 441235633Sdim if (MF.exposesReturnsTwice()) 442208599Srdivacky return false; 443208599Srdivacky 444193323Sed // Gather spill slot references 445193323Sed ScanForSpillSlotRefs(MF); 446193323Sed InitializeSlots(); 447193323Sed Changed = ColorSlots(MF); 448193323Sed 449193323Sed NextColor = -1; 450193323Sed SSIntervals.clear(); 451193323Sed for (unsigned i = 0, e = SSRefs.size(); i != e; ++i) 452193323Sed SSRefs[i].clear(); 453193323Sed SSRefs.clear(); 454193323Sed OrigAlignments.clear(); 455193323Sed OrigSizes.clear(); 456193323Sed AllColors.clear(); 457193323Sed UsedColors.clear(); 458193323Sed for (unsigned i = 0, e = Assignments.size(); i != e; ++i) 459193323Sed Assignments[i].clear(); 460193323Sed Assignments.clear(); 461193323Sed 462193323Sed return Changed; 463193323Sed} 464