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