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