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 "stackslotcoloring" 15 #include "llvm/CodeGen/Passes.h" 16 #include "llvm/ADT/BitVector.h" 17 #include "llvm/ADT/SmallSet.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 21 #include "llvm/CodeGen/LiveStackAnalysis.h" 22 #include "llvm/CodeGen/MachineFrameInfo.h" 23 #include "llvm/CodeGen/MachineInstrBuilder.h" 24 #include "llvm/CodeGen/MachineLoopInfo.h" 25 #include "llvm/CodeGen/MachineMemOperand.h" 26 #include "llvm/CodeGen/MachineRegisterInfo.h" 27 #include "llvm/CodeGen/PseudoSourceValue.h" 28 #include "llvm/IR/Module.h" 29 #include "llvm/Support/CommandLine.h" 30 #include "llvm/Support/Debug.h" 31 #include "llvm/Target/TargetInstrInfo.h" 32 #include "llvm/Target/TargetMachine.h" 33 #include <vector> 34 using namespace llvm; 35 36 static cl::opt<bool> 37 DisableSharing("no-stack-slot-sharing", 38 cl::init(false), cl::Hidden, 39 cl::desc("Suppress slot sharing during stack coloring")); 40 41 static cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden); 42 43 STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); 44 STATISTIC(NumDead, "Number of trivially dead stack accesses eliminated"); 45 46 namespace { 47 class StackSlotColoring : public MachineFunctionPass { 48 LiveStacks* LS; 49 MachineFrameInfo *MFI; 50 const TargetInstrInfo *TII; 51 const MachineLoopInfo *loopInfo; 52 53 // SSIntervals - Spill slot intervals. 54 std::vector<LiveInterval*> SSIntervals; 55 56 // SSRefs - Keep a list of frame index references for each spill slot. 57 SmallVector<SmallVector<MachineInstr*, 8>, 16> SSRefs; 58 59 // OrigAlignments - Alignments of stack objects before coloring. 60 SmallVector<unsigned, 16> OrigAlignments; 61 62 // OrigSizes - Sizess of stack objects before coloring. 63 SmallVector<unsigned, 16> OrigSizes; 64 65 // AllColors - If index is set, it's a spill slot, i.e. color. 66 // FIXME: This assumes PEI locate spill slot with smaller indices 67 // closest to stack pointer / frame pointer. Therefore, smaller 68 // index == better color. 69 BitVector AllColors; 70 71 // NextColor - Next "color" that's not yet used. 72 int NextColor; 73 74 // UsedColors - "Colors" that have been assigned. 75 BitVector UsedColors; 76 77 // Assignments - Color to intervals mapping. 78 SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments; 79 80 public: 81 static char ID; // Pass identification 82 StackSlotColoring() : 83 MachineFunctionPass(ID), NextColor(-1) { 84 initializeStackSlotColoringPass(*PassRegistry::getPassRegistry()); 85 } 86 87 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 88 AU.setPreservesCFG(); 89 AU.addRequired<SlotIndexes>(); 90 AU.addPreserved<SlotIndexes>(); 91 AU.addRequired<LiveStacks>(); 92 AU.addRequired<MachineLoopInfo>(); 93 AU.addPreserved<MachineLoopInfo>(); 94 AU.addPreservedID(MachineDominatorsID); 95 MachineFunctionPass::getAnalysisUsage(AU); 96 } 97 98 virtual bool runOnMachineFunction(MachineFunction &MF); 99 100 private: 101 void InitializeSlots(); 102 void ScanForSpillSlotRefs(MachineFunction &MF); 103 bool OverlapWithAssignments(LiveInterval *li, int Color) const; 104 int ColorSlot(LiveInterval *li); 105 bool ColorSlots(MachineFunction &MF); 106 void RewriteInstruction(MachineInstr *MI, int OldFI, int NewFI, 107 MachineFunction &MF); 108 bool RemoveDeadStores(MachineBasicBlock* MBB); 109 }; 110 } // end anonymous namespace 111 112 char StackSlotColoring::ID = 0; 113 char &llvm::StackSlotColoringID = StackSlotColoring::ID; 114 115 INITIALIZE_PASS_BEGIN(StackSlotColoring, "stack-slot-coloring", 116 "Stack Slot Coloring", false, false) 117 INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 118 INITIALIZE_PASS_DEPENDENCY(LiveStacks) 119 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 120 INITIALIZE_PASS_END(StackSlotColoring, "stack-slot-coloring", 121 "Stack Slot Coloring", false, false) 122 123 namespace { 124 // IntervalSorter - Comparison predicate that sort live intervals by 125 // their weight. 126 struct IntervalSorter { 127 bool operator()(LiveInterval* LHS, LiveInterval* RHS) const { 128 return LHS->weight > RHS->weight; 129 } 130 }; 131 } 132 133 /// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot 134 /// references and update spill slot weights. 135 void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) { 136 SSRefs.resize(MFI->getObjectIndexEnd()); 137 138 // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. 139 for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 140 MBBI != E; ++MBBI) { 141 MachineBasicBlock *MBB = &*MBBI; 142 unsigned loopDepth = loopInfo->getLoopDepth(MBB); 143 for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); 144 MII != EE; ++MII) { 145 MachineInstr *MI = &*MII; 146 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 147 MachineOperand &MO = MI->getOperand(i); 148 if (!MO.isFI()) 149 continue; 150 int FI = MO.getIndex(); 151 if (FI < 0) 152 continue; 153 if (!LS->hasInterval(FI)) 154 continue; 155 LiveInterval &li = LS->getInterval(FI); 156 if (!MI->isDebugValue()) 157 li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth); 158 SSRefs[FI].push_back(MI); 159 } 160 } 161 } 162 } 163 164 /// InitializeSlots - Process all spill stack slot liveintervals and add them 165 /// to a sorted (by weight) list. 166 void StackSlotColoring::InitializeSlots() { 167 int LastFI = MFI->getObjectIndexEnd(); 168 OrigAlignments.resize(LastFI); 169 OrigSizes.resize(LastFI); 170 AllColors.resize(LastFI); 171 UsedColors.resize(LastFI); 172 Assignments.resize(LastFI); 173 174 // Gather all spill slots into a list. 175 DEBUG(dbgs() << "Spill slot intervals:\n"); 176 for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { 177 LiveInterval &li = i->second; 178 DEBUG(li.dump()); 179 int FI = TargetRegisterInfo::stackSlot2Index(li.reg); 180 if (MFI->isDeadObjectIndex(FI)) 181 continue; 182 SSIntervals.push_back(&li); 183 OrigAlignments[FI] = MFI->getObjectAlignment(FI); 184 OrigSizes[FI] = MFI->getObjectSize(FI); 185 AllColors.set(FI); 186 } 187 DEBUG(dbgs() << '\n'); 188 189 // Sort them by weight. 190 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 191 192 // Get first "color". 193 NextColor = AllColors.find_first(); 194 } 195 196 /// OverlapWithAssignments - Return true if LiveInterval overlaps with any 197 /// LiveIntervals that have already been assigned to the specified color. 198 bool 199 StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { 200 const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color]; 201 for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) { 202 LiveInterval *OtherLI = OtherLIs[i]; 203 if (OtherLI->overlaps(*li)) 204 return true; 205 } 206 return false; 207 } 208 209 /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot. 210 /// 211 int StackSlotColoring::ColorSlot(LiveInterval *li) { 212 int Color = -1; 213 bool Share = false; 214 if (!DisableSharing) { 215 // Check if it's possible to reuse any of the used colors. 216 Color = UsedColors.find_first(); 217 while (Color != -1) { 218 if (!OverlapWithAssignments(li, Color)) { 219 Share = true; 220 ++NumEliminated; 221 break; 222 } 223 Color = UsedColors.find_next(Color); 224 } 225 } 226 227 // Assign it to the first available color (assumed to be the best) if it's 228 // not possible to share a used color with other objects. 229 if (!Share) { 230 assert(NextColor != -1 && "No more spill slots?"); 231 Color = NextColor; 232 UsedColors.set(Color); 233 NextColor = AllColors.find_next(NextColor); 234 } 235 236 // Record the assignment. 237 Assignments[Color].push_back(li); 238 int FI = TargetRegisterInfo::stackSlot2Index(li->reg); 239 DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n"); 240 241 // Change size and alignment of the allocated slot. If there are multiple 242 // objects sharing the same slot, then make sure the size and alignment 243 // are large enough for all. 244 unsigned Align = OrigAlignments[FI]; 245 if (!Share || Align > MFI->getObjectAlignment(Color)) 246 MFI->setObjectAlignment(Color, Align); 247 int64_t Size = OrigSizes[FI]; 248 if (!Share || Size > MFI->getObjectSize(Color)) 249 MFI->setObjectSize(Color, Size); 250 return Color; 251 } 252 253 /// Colorslots - Color all spill stack slots and rewrite all frameindex machine 254 /// operands in the function. 255 bool StackSlotColoring::ColorSlots(MachineFunction &MF) { 256 unsigned NumObjs = MFI->getObjectIndexEnd(); 257 SmallVector<int, 16> SlotMapping(NumObjs, -1); 258 SmallVector<float, 16> SlotWeights(NumObjs, 0.0); 259 SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs); 260 BitVector UsedColors(NumObjs); 261 262 DEBUG(dbgs() << "Color spill slot intervals:\n"); 263 bool Changed = false; 264 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 265 LiveInterval *li = SSIntervals[i]; 266 int SS = TargetRegisterInfo::stackSlot2Index(li->reg); 267 int NewSS = ColorSlot(li); 268 assert(NewSS >= 0 && "Stack coloring failed?"); 269 SlotMapping[SS] = NewSS; 270 RevMap[NewSS].push_back(SS); 271 SlotWeights[NewSS] += li->weight; 272 UsedColors.set(NewSS); 273 Changed |= (SS != NewSS); 274 } 275 276 DEBUG(dbgs() << "\nSpill slots after coloring:\n"); 277 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 278 LiveInterval *li = SSIntervals[i]; 279 int SS = TargetRegisterInfo::stackSlot2Index(li->reg); 280 li->weight = SlotWeights[SS]; 281 } 282 // Sort them by new weight. 283 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 284 285 #ifndef NDEBUG 286 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) 287 DEBUG(SSIntervals[i]->dump()); 288 DEBUG(dbgs() << '\n'); 289 #endif 290 291 if (!Changed) 292 return false; 293 294 // Rewrite all MO_FrameIndex operands. 295 SmallVector<SmallSet<unsigned, 4>, 4> NewDefs(MF.getNumBlockIDs()); 296 for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) { 297 int NewFI = SlotMapping[SS]; 298 if (NewFI == -1 || (NewFI == (int)SS)) 299 continue; 300 301 SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS]; 302 for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) 303 RewriteInstruction(RefMIs[i], SS, NewFI, MF); 304 } 305 306 // Delete unused stack slots. 307 while (NextColor != -1) { 308 DEBUG(dbgs() << "Removing unused stack object fi#" << NextColor << "\n"); 309 MFI->RemoveStackObject(NextColor); 310 NextColor = AllColors.find_next(NextColor); 311 } 312 313 return true; 314 } 315 316 /// RewriteInstruction - Rewrite specified instruction by replacing references 317 /// to old frame index with new one. 318 void StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI, 319 int NewFI, MachineFunction &MF) { 320 // Update the operands. 321 for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) { 322 MachineOperand &MO = MI->getOperand(i); 323 if (!MO.isFI()) 324 continue; 325 int FI = MO.getIndex(); 326 if (FI != OldFI) 327 continue; 328 MO.setIndex(NewFI); 329 } 330 331 // Update the memory references. This changes the MachineMemOperands 332 // directly. They may be in use by multiple instructions, however all 333 // instructions using OldFI are being rewritten to use NewFI. 334 const Value *OldSV = PseudoSourceValue::getFixedStack(OldFI); 335 const Value *NewSV = PseudoSourceValue::getFixedStack(NewFI); 336 for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), 337 E = MI->memoperands_end(); I != E; ++I) 338 if ((*I)->getValue() == OldSV) 339 (*I)->setValue(NewSV); 340 } 341 342 343 /// RemoveDeadStores - Scan through a basic block and look for loads followed 344 /// by stores. If they're both using the same stack slot, then the store is 345 /// definitely dead. This could obviously be much more aggressive (consider 346 /// pairs with instructions between them), but such extensions might have a 347 /// considerable compile time impact. 348 bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) { 349 // FIXME: This could be much more aggressive, but we need to investigate 350 // the compile time impact of doing so. 351 bool changed = false; 352 353 SmallVector<MachineInstr*, 4> toErase; 354 355 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 356 I != E; ++I) { 357 if (DCELimit != -1 && (int)NumDead >= DCELimit) 358 break; 359 360 MachineBasicBlock::iterator NextMI = llvm::next(I); 361 if (NextMI == MBB->end()) continue; 362 363 int FirstSS, SecondSS; 364 unsigned LoadReg = 0; 365 unsigned StoreReg = 0; 366 if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue; 367 if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue; 368 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue; 369 370 ++NumDead; 371 changed = true; 372 373 if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) { 374 ++NumDead; 375 toErase.push_back(I); 376 } 377 378 toErase.push_back(NextMI); 379 ++I; 380 } 381 382 for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(), 383 E = toErase.end(); I != E; ++I) 384 (*I)->eraseFromParent(); 385 386 return changed; 387 } 388 389 390 bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { 391 DEBUG({ 392 dbgs() << "********** Stack Slot Coloring **********\n" 393 << "********** Function: " << MF.getName() << '\n'; 394 }); 395 396 MFI = MF.getFrameInfo(); 397 TII = MF.getTarget().getInstrInfo(); 398 LS = &getAnalysis<LiveStacks>(); 399 loopInfo = &getAnalysis<MachineLoopInfo>(); 400 401 bool Changed = false; 402 403 unsigned NumSlots = LS->getNumIntervals(); 404 if (NumSlots == 0) 405 // Nothing to do! 406 return false; 407 408 // If there are calls to setjmp or sigsetjmp, don't perform stack slot 409 // coloring. The stack could be modified before the longjmp is executed, 410 // resulting in the wrong value being used afterwards. (See 411 // <rdar://problem/8007500>.) 412 if (MF.exposesReturnsTwice()) 413 return false; 414 415 // Gather spill slot references 416 ScanForSpillSlotRefs(MF); 417 InitializeSlots(); 418 Changed = ColorSlots(MF); 419 420 NextColor = -1; 421 SSIntervals.clear(); 422 for (unsigned i = 0, e = SSRefs.size(); i != e; ++i) 423 SSRefs[i].clear(); 424 SSRefs.clear(); 425 OrigAlignments.clear(); 426 OrigSizes.clear(); 427 AllColors.clear(); 428 UsedColors.clear(); 429 for (unsigned i = 0, e = Assignments.size(); i != e; ++i) 430 Assignments[i].clear(); 431 Assignments.clear(); 432 433 if (Changed) { 434 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 435 Changed |= RemoveDeadStores(I); 436 } 437 438 return Changed; 439 } 440