StackSlotColoring.cpp revision 04fa35ab13afbbc5b2f12437a256db84a27485d2
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(NumDead, "Number of trivially dead stack accesses eliminated"); 49STATISTIC(NumRegRepl, "Number of stack slot refs replaced with reg refs"); 50 51namespace { 52 class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass { 53 LiveStacks* LS; 54 VirtRegMap* VRM; 55 MachineFrameInfo *MFI; 56 MachineRegisterInfo *MRI; 57 const TargetInstrInfo *TII; 58 const TargetRegisterInfo *TRI; 59 const MachineLoopInfo *loopInfo; 60 61 // SSIntervals - Spill slot intervals. 62 std::vector<LiveInterval*> SSIntervals; 63 64 // SSRefs - Keep a list of frame index references for each spill slot. 65 SmallVector<SmallVector<MachineInstr*, 8>, 16> SSRefs; 66 67 // OrigAlignments - Alignments of stack objects before coloring. 68 SmallVector<unsigned, 16> OrigAlignments; 69 70 // OrigSizes - Sizess of stack objects before coloring. 71 SmallVector<unsigned, 16> OrigSizes; 72 73 // AllColors - If index is set, it's a spill slot, i.e. color. 74 // FIXME: This assumes PEI locate spill slot with smaller indices 75 // closest to stack pointer / frame pointer. Therefore, smaller 76 // index == better color. 77 BitVector AllColors; 78 79 // NextColor - Next "color" that's not yet used. 80 int NextColor; 81 82 // UsedColors - "Colors" that have been assigned. 83 BitVector UsedColors; 84 85 // Assignments - Color to intervals mapping. 86 SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments; 87 88 public: 89 static char ID; // Pass identification 90 StackSlotColoring() : MachineFunctionPass(&ID), NextColor(-1) {} 91 92 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 93 AU.addRequired<LiveStacks>(); 94 AU.addRequired<VirtRegMap>(); 95 AU.addPreserved<VirtRegMap>(); 96 AU.addRequired<MachineLoopInfo>(); 97 AU.addPreserved<MachineLoopInfo>(); 98 AU.addPreservedID(MachineDominatorsID); 99 MachineFunctionPass::getAnalysisUsage(AU); 100 } 101 102 virtual bool runOnMachineFunction(MachineFunction &MF); 103 virtual const char* getPassName() const { 104 return "Stack Slot Coloring"; 105 } 106 107 private: 108 void InitializeSlots(); 109 void ScanForSpillSlotRefs(MachineFunction &MF); 110 bool OverlapWithAssignments(LiveInterval *li, int Color) const; 111 int ColorSlot(LiveInterval *li); 112 bool ColorSlots(MachineFunction &MF); 113 bool ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping, 114 SmallVector<SmallVector<int, 4>, 16> &RevMap, 115 BitVector &SlotIsReg); 116 void RewriteInstruction(MachineInstr *MI, int OldFI, int NewFI, 117 MachineFunction &MF); 118 void UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI, 119 unsigned Reg, MachineFunction &MF); 120 bool AllMemRefsCanBeUnfolded(int SS); 121 bool RemoveDeadStores(MachineBasicBlock* MBB); 122 }; 123} // end anonymous namespace 124 125char StackSlotColoring::ID = 0; 126 127static RegisterPass<StackSlotColoring> 128X("stack-slot-coloring", "Stack Slot Coloring"); 129 130FunctionPass *llvm::createStackSlotColoringPass() { 131 return new StackSlotColoring(); 132} 133 134namespace { 135 // IntervalSorter - Comparison predicate that sort live intervals by 136 // their weight. 137 struct IntervalSorter { 138 bool operator()(LiveInterval* LHS, LiveInterval* RHS) const { 139 return LHS->weight > RHS->weight; 140 } 141 }; 142} 143 144/// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot 145/// references and update spill slot weights. 146void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) { 147 SSRefs.resize(MFI->getObjectIndexEnd()); 148 149 // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. 150 for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 151 MBBI != E; ++MBBI) { 152 MachineBasicBlock *MBB = &*MBBI; 153 unsigned loopDepth = loopInfo->getLoopDepth(MBB); 154 for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); 155 MII != EE; ++MII) { 156 MachineInstr *MI = &*MII; 157 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 158 MachineOperand &MO = MI->getOperand(i); 159 if (!MO.isFI()) 160 continue; 161 int FI = MO.getIndex(); 162 if (FI < 0) 163 continue; 164 if (!LS->hasInterval(FI)) 165 continue; 166 LiveInterval &li = LS->getInterval(FI); 167 li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth); 168 SSRefs[FI].push_back(MI); 169 } 170 } 171 } 172} 173 174/// InitializeSlots - Process all spill stack slot liveintervals and add them 175/// to a sorted (by weight) list. 176void StackSlotColoring::InitializeSlots() { 177 int LastFI = MFI->getObjectIndexEnd(); 178 OrigAlignments.resize(LastFI); 179 OrigSizes.resize(LastFI); 180 AllColors.resize(LastFI); 181 UsedColors.resize(LastFI); 182 Assignments.resize(LastFI); 183 184 // Gather all spill slots into a list. 185 DOUT << "Spill slot intervals:\n"; 186 for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { 187 LiveInterval &li = i->second; 188 DEBUG(li.dump()); 189 int FI = li.getStackSlotIndex(); 190 if (MFI->isDeadObjectIndex(FI)) 191 continue; 192 SSIntervals.push_back(&li); 193 OrigAlignments[FI] = MFI->getObjectAlignment(FI); 194 OrigSizes[FI] = MFI->getObjectSize(FI); 195 AllColors.set(FI); 196 } 197 DOUT << '\n'; 198 199 // Sort them by weight. 200 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 201 202 // Get first "color". 203 NextColor = AllColors.find_first(); 204} 205 206/// OverlapWithAssignments - Return true if LiveInterval overlaps with any 207/// LiveIntervals that have already been assigned to the specified color. 208bool 209StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { 210 const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color]; 211 for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) { 212 LiveInterval *OtherLI = OtherLIs[i]; 213 if (OtherLI->overlaps(*li)) 214 return true; 215 } 216 return false; 217} 218 219/// ColorSlotsWithFreeRegs - If there are any free registers available, try 220/// replacing spill slots references with registers instead. 221bool 222StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping, 223 SmallVector<SmallVector<int, 4>, 16> &RevMap, 224 BitVector &SlotIsReg) { 225 if (!ColorWithRegs || !VRM->HasUnusedRegisters()) 226 return false; 227 228 bool Changed = false; 229 DOUT << "Assigning unused registers to spill slots:\n"; 230 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 231 LiveInterval *li = SSIntervals[i]; 232 int SS = li->getStackSlotIndex(); 233 if (!UsedColors[SS]) 234 continue; 235 // Get the largest common sub- register class of all the stack slots that 236 // are colored to this stack slot. 237 const TargetRegisterClass *RC = 0; 238 for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) { 239 int RSS = RevMap[SS][j]; 240 const TargetRegisterClass *RRC = LS->getIntervalRegClass(RSS); 241 if (!RC) 242 RC = RRC; 243 else 244 RC = getCommonSubClass(RC, RRC); 245 } 246 247 // If it's not colored to another stack slot, try coloring it 248 // to a "free" register. 249 if (!RC) 250 continue; 251 unsigned Reg = VRM->getFirstUnusedRegister(RC); 252 if (!Reg) 253 continue; 254 bool IsSafe = true; 255 for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) { 256 int RSS = RevMap[SS][j]; 257 if (!AllMemRefsCanBeUnfolded(RSS)) { 258 IsSafe = false; 259 break; 260 } 261 } 262 if (!IsSafe) 263 // Try color the next spill slot. 264 continue; 265 266 DOUT << "Assigning fi#" << SS << " to " << TRI->getName(Reg) 267 << ", which in turn means...\n"; 268 // Register and its sub-registers are no longer free. 269 VRM->setRegisterUsed(Reg); 270 // If reg is a callee-saved register, it will have to be spilled in 271 // the prologue. 272 MRI->setPhysRegUsed(Reg); 273 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 274 VRM->setRegisterUsed(*AS); 275 MRI->setPhysRegUsed(*AS); 276 } 277 // This spill slot is dead after the rewrites 278 MFI->RemoveStackObject(SS); 279 280 // Remember all these FI references will have to be unfolded. 281 for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) { 282 int RSS = RevMap[SS][j]; 283 DOUT << " Assigning fi#" << RSS << " to " << TRI->getName(Reg) << '\n'; 284 SlotMapping[RSS] = Reg; 285 SlotIsReg.set(RSS); 286 } 287 288 ++NumEliminated; 289 Changed = true; 290 } 291 DOUT << '\n'; 292 293 return Changed; 294} 295 296/// ColorSlot - Assign a "color" (stack slot) to the specified stack slot. 297/// 298int StackSlotColoring::ColorSlot(LiveInterval *li) { 299 int Color = -1; 300 bool Share = false; 301 if (!DisableSharing) { 302 // Check if it's possible to reuse any of the used colors. 303 Color = UsedColors.find_first(); 304 while (Color != -1) { 305 if (!OverlapWithAssignments(li, Color)) { 306 Share = true; 307 ++NumEliminated; 308 break; 309 } 310 Color = UsedColors.find_next(Color); 311 } 312 } 313 314 // Assign it to the first available color (assumed to be the best) if it's 315 // not possible to share a used color with other objects. 316 if (!Share) { 317 assert(NextColor != -1 && "No more spill slots?"); 318 Color = NextColor; 319 UsedColors.set(Color); 320 NextColor = AllColors.find_next(NextColor); 321 } 322 323 // Record the assignment. 324 Assignments[Color].push_back(li); 325 int FI = li->getStackSlotIndex(); 326 DOUT << "Assigning fi#" << FI << " to fi#" << Color << "\n"; 327 328 // Change size and alignment of the allocated slot. If there are multiple 329 // objects sharing the same slot, then make sure the size and alignment 330 // are large enough for all. 331 unsigned Align = OrigAlignments[FI]; 332 if (!Share || Align > MFI->getObjectAlignment(Color)) 333 MFI->setObjectAlignment(Color, Align); 334 int64_t Size = OrigSizes[FI]; 335 if (!Share || Size > MFI->getObjectSize(Color)) 336 MFI->setObjectSize(Color, Size); 337 return Color; 338} 339 340/// Colorslots - Color all spill stack slots and rewrite all frameindex machine 341/// operands in the function. 342bool StackSlotColoring::ColorSlots(MachineFunction &MF) { 343 unsigned NumObjs = MFI->getObjectIndexEnd(); 344 SmallVector<int, 16> SlotMapping(NumObjs, -1); 345 SmallVector<float, 16> SlotWeights(NumObjs, 0.0); 346 SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs); 347 BitVector SlotIsReg(NumObjs); 348 BitVector UsedColors(NumObjs); 349 350 DOUT << "Color spill slot intervals:\n"; 351 bool Changed = false; 352 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 353 LiveInterval *li = SSIntervals[i]; 354 int SS = li->getStackSlotIndex(); 355 int NewSS = ColorSlot(li); 356 assert(NewSS >= 0 && "Stack coloring failed?"); 357 SlotMapping[SS] = NewSS; 358 RevMap[NewSS].push_back(SS); 359 SlotWeights[NewSS] += li->weight; 360 UsedColors.set(NewSS); 361 Changed |= (SS != NewSS); 362 } 363 364 DOUT << "\nSpill slots after coloring:\n"; 365 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 366 LiveInterval *li = SSIntervals[i]; 367 int SS = li->getStackSlotIndex(); 368 li->weight = SlotWeights[SS]; 369 } 370 // Sort them by new weight. 371 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 372 373#ifndef NDEBUG 374 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) 375 DEBUG(SSIntervals[i]->dump()); 376 DOUT << '\n'; 377#endif 378 379 // Can we "color" a stack slot with a unused register? 380 Changed |= ColorSlotsWithFreeRegs(SlotMapping, RevMap, SlotIsReg); 381 382 if (!Changed) 383 return false; 384 385 // Rewrite all MO_FrameIndex operands. 386 for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) { 387 bool isReg = SlotIsReg[SS]; 388 int NewFI = SlotMapping[SS]; 389 if (NewFI == -1 || (NewFI == (int)SS && !isReg)) 390 continue; 391 392 SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS]; 393 for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) 394 if (isReg) 395 // Rewrite to use a register instead. 396 UnfoldAndRewriteInstruction(RefMIs[i], SS, NewFI, MF); 397 else 398 RewriteInstruction(RefMIs[i], SS, NewFI, MF); 399 } 400 401 // Delete unused stack slots. 402 while (NextColor != -1) { 403 DOUT << "Removing unused stack object fi#" << NextColor << "\n"; 404 MFI->RemoveStackObject(NextColor); 405 NextColor = AllColors.find_next(NextColor); 406 } 407 408 return true; 409} 410 411/// AllMemRefsCanBeUnfolded - Return true if all references of the specified 412/// spill slot index can be unfolded. 413bool StackSlotColoring::AllMemRefsCanBeUnfolded(int SS) { 414 SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS]; 415 for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) { 416 MachineInstr *MI = RefMIs[i]; 417 if (!TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), false, false)) 418 return false; 419 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 420 MachineOperand &MO = MI->getOperand(j); 421 if (MO.isFI() && MO.getIndex() != SS) 422 // If it uses another frameindex, we can, currently* unfold it. 423 return false; 424 } 425 } 426 return true; 427} 428 429/// RewriteInstruction - Rewrite specified instruction by replacing references 430/// to old frame index with new one. 431void StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI, 432 int NewFI, MachineFunction &MF) { 433 for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) { 434 MachineOperand &MO = MI->getOperand(i); 435 if (!MO.isFI()) 436 continue; 437 int FI = MO.getIndex(); 438 if (FI != OldFI) 439 continue; 440 MO.setIndex(NewFI); 441 } 442 443 // Update the MachineMemOperand for the new memory location. 444 // FIXME: We need a better method of managing these too. 445 SmallVector<MachineMemOperand, 2> MMOs(MI->memoperands_begin(), 446 MI->memoperands_end()); 447 MI->clearMemOperands(MF); 448 const Value *OldSV = PseudoSourceValue::getFixedStack(OldFI); 449 for (unsigned i = 0, ee = MMOs.size(); i != ee; ++i) { 450 if (MMOs[i].getValue() != OldSV) 451 MI->addMemOperand(MF, MMOs[i]); 452 else { 453 MachineMemOperand MMO(PseudoSourceValue::getFixedStack(NewFI), 454 MMOs[i].getFlags(), MMOs[i].getOffset(), 455 MMOs[i].getSize(), MMOs[i].getAlignment()); 456 MI->addMemOperand(MF, MMO); 457 } 458 } 459} 460 461/// UnfoldAndRewriteInstruction - Rewrite specified instruction by unfolding 462/// folded memory references and replacing those references with register 463/// references instead. 464void StackSlotColoring::UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI, 465 unsigned Reg, 466 MachineFunction &MF) { 467 MachineBasicBlock *MBB = MI->getParent(); 468 SmallVector<MachineInstr*, 4> NewMIs; 469 bool Success = TII->unfoldMemoryOperand(MF, MI, Reg, false, false, NewMIs); 470 assert(Success && "Failed to unfold!"); 471 MBB->insert(MI, NewMIs[0]); 472 MBB->erase(MI); 473 ++NumRegRepl; 474} 475 476/// RemoveDeadStores - Scan through a basic block and look for loads followed 477/// by stores. If they're both using the same stack slot, then the store is 478/// definitely dead. This could obviously be much more aggressive (consider 479/// pairs with instructions between them), but such extensions might have a 480/// considerable compile time impact. 481bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) { 482 // FIXME: This could be much more aggressive, but we need to investigate 483 // the compile time impact of doing so. 484 bool changed = false; 485 486 SmallVector<MachineInstr*, 4> toErase; 487 488 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 489 I != E; ++I) { 490 if (DCELimit != -1 && (int)NumDead >= DCELimit) 491 break; 492 493 MachineBasicBlock::iterator NextMI = next(I); 494 if (NextMI == MBB->end()) continue; 495 496 int FirstSS, SecondSS; 497 unsigned LoadReg = 0; 498 unsigned StoreReg = 0; 499 if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue; 500 if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue; 501 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue; 502 503 ++NumDead; 504 changed = true; 505 506 if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) { 507 ++NumDead; 508 toErase.push_back(I); 509 } 510 511 toErase.push_back(NextMI); 512 ++I; 513 } 514 515 for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(), 516 E = toErase.end(); I != E; ++I) 517 (*I)->eraseFromParent(); 518 519 return changed; 520} 521 522 523bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { 524 DOUT << "********** Stack Slot Coloring **********\n"; 525 526 MFI = MF.getFrameInfo(); 527 MRI = &MF.getRegInfo(); 528 TII = MF.getTarget().getInstrInfo(); 529 TRI = MF.getTarget().getRegisterInfo(); 530 LS = &getAnalysis<LiveStacks>(); 531 VRM = &getAnalysis<VirtRegMap>(); 532 loopInfo = &getAnalysis<MachineLoopInfo>(); 533 534 bool Changed = false; 535 536 unsigned NumSlots = LS->getNumIntervals(); 537 if (NumSlots < 2) { 538 if (NumSlots == 0 || !VRM->HasUnusedRegisters()) 539 // Nothing to do! 540 return false; 541 } 542 543 // Gather spill slot references 544 ScanForSpillSlotRefs(MF); 545 InitializeSlots(); 546 Changed = ColorSlots(MF); 547 548 NextColor = -1; 549 SSIntervals.clear(); 550 for (unsigned i = 0, e = SSRefs.size(); i != e; ++i) 551 SSRefs[i].clear(); 552 SSRefs.clear(); 553 OrigAlignments.clear(); 554 OrigSizes.clear(); 555 AllColors.clear(); 556 UsedColors.clear(); 557 for (unsigned i = 0, e = Assignments.size(); i != e; ++i) 558 Assignments[i].clear(); 559 Assignments.clear(); 560 561 if (Changed) { 562 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 563 Changed |= RemoveDeadStores(I); 564 } 565 566 return Changed; 567} 568