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