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