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