StackSlotColoring.cpp revision ae3b4c328e882f4a9db6f10af73b106cb14a3290
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/MachineLoopInfo.h" 23#include "llvm/CodeGen/MachineMemOperand.h" 24#include "llvm/CodeGen/MachineRegisterInfo.h" 25#include "llvm/CodeGen/PseudoSourceValue.h" 26#include "llvm/Support/CommandLine.h" 27#include "llvm/Support/Debug.h" 28#include "llvm/Target/TargetInstrInfo.h" 29#include "llvm/Target/TargetMachine.h" 30#include "llvm/ADT/BitVector.h" 31#include "llvm/ADT/SmallSet.h" 32#include "llvm/ADT/SmallVector.h" 33#include "llvm/ADT/Statistic.h" 34#include <vector> 35using namespace llvm; 36 37static cl::opt<bool> 38DisableSharing("no-stack-slot-sharing", 39 cl::init(false), cl::Hidden, 40 cl::desc("Suppress slot sharing during stack coloring")); 41 42static cl::opt<bool> 43ColorWithRegsOpt("color-ss-with-regs", 44 cl::init(false), cl::Hidden, 45 cl::desc("Color stack slots with free registers")); 46 47 48static cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden); 49 50STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); 51STATISTIC(NumRegRepl, "Number of stack slot refs replaced with reg refs"); 52STATISTIC(NumLoadElim, "Number of loads eliminated"); 53STATISTIC(NumStoreElim, "Number of stores eliminated"); 54STATISTIC(NumDead, "Number of trivially dead stack accesses eliminated"); 55 56namespace { 57 class StackSlotColoring : public MachineFunctionPass { 58 bool ColorWithRegs; 59 LiveStacks* LS; 60 VirtRegMap* VRM; 61 MachineFrameInfo *MFI; 62 MachineRegisterInfo *MRI; 63 const TargetInstrInfo *TII; 64 const TargetRegisterInfo *TRI; 65 const MachineLoopInfo *loopInfo; 66 67 // SSIntervals - Spill slot intervals. 68 std::vector<LiveInterval*> SSIntervals; 69 70 // SSRefs - Keep a list of frame index references for each spill slot. 71 SmallVector<SmallVector<MachineInstr*, 8>, 16> SSRefs; 72 73 // OrigAlignments - Alignments of stack objects before coloring. 74 SmallVector<unsigned, 16> OrigAlignments; 75 76 // OrigSizes - Sizess of stack objects before coloring. 77 SmallVector<unsigned, 16> OrigSizes; 78 79 // AllColors - If index is set, it's a spill slot, i.e. color. 80 // FIXME: This assumes PEI locate spill slot with smaller indices 81 // closest to stack pointer / frame pointer. Therefore, smaller 82 // index == better color. 83 BitVector AllColors; 84 85 // NextColor - Next "color" that's not yet used. 86 int NextColor; 87 88 // UsedColors - "Colors" that have been assigned. 89 BitVector UsedColors; 90 91 // Assignments - Color to intervals mapping. 92 SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments; 93 94 public: 95 static char ID; // Pass identification 96 StackSlotColoring() : 97 MachineFunctionPass(&ID), ColorWithRegs(false), NextColor(-1) {} 98 StackSlotColoring(bool RegColor) : 99 MachineFunctionPass(&ID), ColorWithRegs(RegColor), NextColor(-1) {} 100 101 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 102 AU.setPreservesCFG(); 103 AU.addRequired<SlotIndexes>(); 104 AU.addPreserved<SlotIndexes>(); 105 AU.addRequired<LiveStacks>(); 106 AU.addRequired<VirtRegMap>(); 107 AU.addPreserved<VirtRegMap>(); 108 AU.addRequired<MachineLoopInfo>(); 109 AU.addPreserved<MachineLoopInfo>(); 110 AU.addPreservedID(MachineDominatorsID); 111 MachineFunctionPass::getAnalysisUsage(AU); 112 } 113 114 virtual bool runOnMachineFunction(MachineFunction &MF); 115 virtual const char* getPassName() const { 116 return "Stack Slot Coloring"; 117 } 118 119 private: 120 void InitializeSlots(); 121 void ScanForSpillSlotRefs(MachineFunction &MF); 122 bool OverlapWithAssignments(LiveInterval *li, int Color) const; 123 int ColorSlot(LiveInterval *li); 124 bool ColorSlots(MachineFunction &MF); 125 bool ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping, 126 SmallVector<SmallVector<int, 4>, 16> &RevMap, 127 BitVector &SlotIsReg); 128 void RewriteInstruction(MachineInstr *MI, int OldFI, int NewFI, 129 MachineFunction &MF); 130 bool PropagateBackward(MachineBasicBlock::iterator MII, 131 MachineBasicBlock *MBB, 132 unsigned OldReg, unsigned NewReg); 133 bool PropagateForward(MachineBasicBlock::iterator MII, 134 MachineBasicBlock *MBB, 135 unsigned OldReg, unsigned NewReg); 136 void UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI, 137 unsigned Reg, const TargetRegisterClass *RC, 138 SmallSet<unsigned, 4> &Defs, 139 MachineFunction &MF); 140 bool AllMemRefsCanBeUnfolded(int SS); 141 bool RemoveDeadStores(MachineBasicBlock* MBB); 142 }; 143} // end anonymous namespace 144 145char StackSlotColoring::ID = 0; 146 147static RegisterPass<StackSlotColoring> 148X("stack-slot-coloring", "Stack Slot Coloring"); 149 150FunctionPass *llvm::createStackSlotColoringPass(bool RegColor) { 151 return new StackSlotColoring(RegColor); 152} 153 154namespace { 155 // IntervalSorter - Comparison predicate that sort live intervals by 156 // their weight. 157 struct IntervalSorter { 158 bool operator()(LiveInterval* LHS, LiveInterval* RHS) const { 159 return LHS->weight > RHS->weight; 160 } 161 }; 162} 163 164/// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot 165/// references and update spill slot weights. 166void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) { 167 SSRefs.resize(MFI->getObjectIndexEnd()); 168 169 // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. 170 for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 171 MBBI != E; ++MBBI) { 172 MachineBasicBlock *MBB = &*MBBI; 173 unsigned loopDepth = loopInfo->getLoopDepth(MBB); 174 for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); 175 MII != EE; ++MII) { 176 MachineInstr *MI = &*MII; 177 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 178 MachineOperand &MO = MI->getOperand(i); 179 if (!MO.isFI()) 180 continue; 181 int FI = MO.getIndex(); 182 if (FI < 0) 183 continue; 184 if (!LS->hasInterval(FI)) 185 continue; 186 LiveInterval &li = LS->getInterval(FI); 187 if (!MI->isDebugValue()) 188 li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth); 189 SSRefs[FI].push_back(MI); 190 } 191 } 192 } 193} 194 195/// InitializeSlots - Process all spill stack slot liveintervals and add them 196/// to a sorted (by weight) list. 197void StackSlotColoring::InitializeSlots() { 198 int LastFI = MFI->getObjectIndexEnd(); 199 OrigAlignments.resize(LastFI); 200 OrigSizes.resize(LastFI); 201 AllColors.resize(LastFI); 202 UsedColors.resize(LastFI); 203 Assignments.resize(LastFI); 204 205 // Gather all spill slots into a list. 206 DEBUG(dbgs() << "Spill slot intervals:\n"); 207 for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { 208 LiveInterval &li = i->second; 209 DEBUG(li.dump()); 210 int FI = li.getStackSlotIndex(); 211 if (MFI->isDeadObjectIndex(FI)) 212 continue; 213 SSIntervals.push_back(&li); 214 OrigAlignments[FI] = MFI->getObjectAlignment(FI); 215 OrigSizes[FI] = MFI->getObjectSize(FI); 216 AllColors.set(FI); 217 } 218 DEBUG(dbgs() << '\n'); 219 220 // Sort them by weight. 221 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 222 223 // Get first "color". 224 NextColor = AllColors.find_first(); 225} 226 227/// OverlapWithAssignments - Return true if LiveInterval overlaps with any 228/// LiveIntervals that have already been assigned to the specified color. 229bool 230StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { 231 const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color]; 232 for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) { 233 LiveInterval *OtherLI = OtherLIs[i]; 234 if (OtherLI->overlaps(*li)) 235 return true; 236 } 237 return false; 238} 239 240/// ColorSlotsWithFreeRegs - If there are any free registers available, try 241/// replacing spill slots references with registers instead. 242bool 243StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping, 244 SmallVector<SmallVector<int, 4>, 16> &RevMap, 245 BitVector &SlotIsReg) { 246 if (!(ColorWithRegs || ColorWithRegsOpt) || !VRM->HasUnusedRegisters()) 247 return false; 248 249 bool Changed = false; 250 DEBUG(dbgs() << "Assigning unused registers to spill slots:\n"); 251 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 252 LiveInterval *li = SSIntervals[i]; 253 int SS = li->getStackSlotIndex(); 254 if (!UsedColors[SS] || li->weight < 20) 255 // If the weight is < 20, i.e. two references in a loop with depth 1, 256 // don't bother with it. 257 continue; 258 259 // These slots allow to share the same registers. 260 bool AllColored = true; 261 SmallVector<unsigned, 4> ColoredRegs; 262 for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) { 263 int RSS = RevMap[SS][j]; 264 const TargetRegisterClass *RC = LS->getIntervalRegClass(RSS); 265 // If it's not colored to another stack slot, try coloring it 266 // to a "free" register. 267 if (!RC) { 268 AllColored = false; 269 continue; 270 } 271 unsigned Reg = VRM->getFirstUnusedRegister(RC); 272 if (!Reg) { 273 AllColored = false; 274 continue; 275 } 276 if (!AllMemRefsCanBeUnfolded(RSS)) { 277 AllColored = false; 278 continue; 279 } else { 280 DEBUG(dbgs() << "Assigning fi#" << RSS << " to " 281 << TRI->getName(Reg) << '\n'); 282 ColoredRegs.push_back(Reg); 283 SlotMapping[RSS] = Reg; 284 SlotIsReg.set(RSS); 285 Changed = true; 286 } 287 } 288 289 // Register and its sub-registers are no longer free. 290 while (!ColoredRegs.empty()) { 291 unsigned Reg = ColoredRegs.back(); 292 ColoredRegs.pop_back(); 293 VRM->setRegisterUsed(Reg); 294 // If reg is a callee-saved register, it will have to be spilled in 295 // the prologue. 296 MRI->setPhysRegUsed(Reg); 297 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 298 VRM->setRegisterUsed(*AS); 299 MRI->setPhysRegUsed(*AS); 300 } 301 } 302 // This spill slot is dead after the rewrites 303 if (AllColored) { 304 MFI->RemoveStackObject(SS); 305 ++NumEliminated; 306 } 307 } 308 DEBUG(dbgs() << '\n'); 309 310 return Changed; 311} 312 313/// ColorSlot - Assign a "color" (stack slot) to the specified stack slot. 314/// 315int StackSlotColoring::ColorSlot(LiveInterval *li) { 316 int Color = -1; 317 bool Share = false; 318 if (!DisableSharing) { 319 // Check if it's possible to reuse any of the used colors. 320 Color = UsedColors.find_first(); 321 while (Color != -1) { 322 if (!OverlapWithAssignments(li, Color)) { 323 Share = true; 324 ++NumEliminated; 325 break; 326 } 327 Color = UsedColors.find_next(Color); 328 } 329 } 330 331 // Assign it to the first available color (assumed to be the best) if it's 332 // not possible to share a used color with other objects. 333 if (!Share) { 334 assert(NextColor != -1 && "No more spill slots?"); 335 Color = NextColor; 336 UsedColors.set(Color); 337 NextColor = AllColors.find_next(NextColor); 338 } 339 340 // Record the assignment. 341 Assignments[Color].push_back(li); 342 int FI = li->getStackSlotIndex(); 343 DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n"); 344 345 // Change size and alignment of the allocated slot. If there are multiple 346 // objects sharing the same slot, then make sure the size and alignment 347 // are large enough for all. 348 unsigned Align = OrigAlignments[FI]; 349 if (!Share || Align > MFI->getObjectAlignment(Color)) 350 MFI->setObjectAlignment(Color, Align); 351 int64_t Size = OrigSizes[FI]; 352 if (!Share || Size > MFI->getObjectSize(Color)) 353 MFI->setObjectSize(Color, Size); 354 return Color; 355} 356 357/// Colorslots - Color all spill stack slots and rewrite all frameindex machine 358/// operands in the function. 359bool StackSlotColoring::ColorSlots(MachineFunction &MF) { 360 unsigned NumObjs = MFI->getObjectIndexEnd(); 361 SmallVector<int, 16> SlotMapping(NumObjs, -1); 362 SmallVector<float, 16> SlotWeights(NumObjs, 0.0); 363 SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs); 364 BitVector SlotIsReg(NumObjs); 365 BitVector UsedColors(NumObjs); 366 367 DEBUG(dbgs() << "Color spill slot intervals:\n"); 368 bool Changed = false; 369 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 370 LiveInterval *li = SSIntervals[i]; 371 int SS = li->getStackSlotIndex(); 372 int NewSS = ColorSlot(li); 373 assert(NewSS >= 0 && "Stack coloring failed?"); 374 SlotMapping[SS] = NewSS; 375 RevMap[NewSS].push_back(SS); 376 SlotWeights[NewSS] += li->weight; 377 UsedColors.set(NewSS); 378 Changed |= (SS != NewSS); 379 } 380 381 DEBUG(dbgs() << "\nSpill slots after coloring:\n"); 382 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 383 LiveInterval *li = SSIntervals[i]; 384 int SS = li->getStackSlotIndex(); 385 li->weight = SlotWeights[SS]; 386 } 387 // Sort them by new weight. 388 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 389 390#ifndef NDEBUG 391 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) 392 DEBUG(SSIntervals[i]->dump()); 393 DEBUG(dbgs() << '\n'); 394#endif 395 396 // Can we "color" a stack slot with a unused register? 397 Changed |= ColorSlotsWithFreeRegs(SlotMapping, RevMap, SlotIsReg); 398 399 if (!Changed) 400 return false; 401 402 // Rewrite all MO_FrameIndex operands. 403 SmallVector<SmallSet<unsigned, 4>, 4> NewDefs(MF.getNumBlockIDs()); 404 for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) { 405 bool isReg = SlotIsReg[SS]; 406 int NewFI = SlotMapping[SS]; 407 if (NewFI == -1 || (NewFI == (int)SS && !isReg)) 408 continue; 409 410 const TargetRegisterClass *RC = LS->getIntervalRegClass(SS); 411 SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS]; 412 for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) 413 if (!isReg) 414 RewriteInstruction(RefMIs[i], SS, NewFI, MF); 415 else { 416 // Rewrite to use a register instead. 417 unsigned MBBId = RefMIs[i]->getParent()->getNumber(); 418 SmallSet<unsigned, 4> &Defs = NewDefs[MBBId]; 419 UnfoldAndRewriteInstruction(RefMIs[i], SS, NewFI, RC, Defs, MF); 420 } 421 } 422 423 // Delete unused stack slots. 424 while (NextColor != -1) { 425 DEBUG(dbgs() << "Removing unused stack object fi#" << NextColor << "\n"); 426 MFI->RemoveStackObject(NextColor); 427 NextColor = AllColors.find_next(NextColor); 428 } 429 430 return true; 431} 432 433/// AllMemRefsCanBeUnfolded - Return true if all references of the specified 434/// spill slot index can be unfolded. 435bool StackSlotColoring::AllMemRefsCanBeUnfolded(int SS) { 436 SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS]; 437 for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) { 438 MachineInstr *MI = RefMIs[i]; 439 if (TII->isLoadFromStackSlot(MI, SS) || 440 TII->isStoreToStackSlot(MI, SS)) 441 // Restore and spill will become copies. 442 return true; 443 if (!TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), false, false)) 444 return false; 445 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 446 MachineOperand &MO = MI->getOperand(j); 447 if (MO.isFI() && MO.getIndex() != SS) 448 // If it uses another frameindex, we can, currently* unfold it. 449 return false; 450 } 451 } 452 return true; 453} 454 455/// RewriteInstruction - Rewrite specified instruction by replacing references 456/// to old frame index with new one. 457void StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI, 458 int NewFI, MachineFunction &MF) { 459 // Update the operands. 460 for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) { 461 MachineOperand &MO = MI->getOperand(i); 462 if (!MO.isFI()) 463 continue; 464 int FI = MO.getIndex(); 465 if (FI != OldFI) 466 continue; 467 MO.setIndex(NewFI); 468 } 469 470 // Update the memory references. This changes the MachineMemOperands 471 // directly. They may be in use by multiple instructions, however all 472 // instructions using OldFI are being rewritten to use NewFI. 473 const Value *OldSV = PseudoSourceValue::getFixedStack(OldFI); 474 const Value *NewSV = PseudoSourceValue::getFixedStack(NewFI); 475 for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), 476 E = MI->memoperands_end(); I != E; ++I) 477 if ((*I)->getValue() == OldSV) 478 (*I)->setValue(NewSV); 479} 480 481/// PropagateBackward - Traverse backward and look for the definition of 482/// OldReg. If it can successfully update all of the references with NewReg, 483/// do so and return true. 484bool StackSlotColoring::PropagateBackward(MachineBasicBlock::iterator MII, 485 MachineBasicBlock *MBB, 486 unsigned OldReg, unsigned NewReg) { 487 if (MII == MBB->begin()) 488 return false; 489 490 SmallVector<MachineOperand*, 4> Uses; 491 SmallVector<MachineOperand*, 4> Refs; 492 while (--MII != MBB->begin()) { 493 bool FoundDef = false; // Not counting 2address def. 494 495 Uses.clear(); 496 const TargetInstrDesc &TID = MII->getDesc(); 497 for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) { 498 MachineOperand &MO = MII->getOperand(i); 499 if (!MO.isReg()) 500 continue; 501 unsigned Reg = MO.getReg(); 502 if (Reg == 0) 503 continue; 504 if (Reg == OldReg) { 505 if (MO.isImplicit()) 506 return false; 507 508 // Abort the use is actually a sub-register def. We don't have enough 509 // information to figure out if it is really legal. 510 if (MO.getSubReg() || MII->isExtractSubreg() || 511 MII->isInsertSubreg() || 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() || MII->isExtractSubreg()) 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 TII->copyRegToReg(*MBB, MI, DstReg, Reg, RC, RC, 613 MI->getDebugLoc()); 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 TII->copyRegToReg(*MBB, MI, Reg, SrcReg, RC, RC, 630 MI->getDebugLoc()); 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 is a call to a function with the attribute "returns_twice" (like 728 // setjmp or sigsetjmp), don't perform stack slot coloring. The stack could be 729 // modified before the the second return, resulting in the wrong value being 730 // used afterwards. (See <rdar://problem/8007500>.) 731 if (MF.hasReturnsTwiceCall()) 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