1 //===-- MachineSink.cpp - Sinking for machine instructions ----------------===// 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 pass moves instructions into successor blocks when possible, so that 11 // they aren't executed on paths where their results aren't needed. 12 // 13 // This pass is not intended to be a replacement or a complete alternative 14 // for an LLVM-IR-level sinking pass. It is only designed to sink simple 15 // constructs that are not exposed before lowering and instruction selection. 16 // 17 //===----------------------------------------------------------------------===// 18 19 #include "llvm/CodeGen/Passes.h" 20 #include "llvm/ADT/SetVector.h" 21 #include "llvm/ADT/SmallSet.h" 22 #include "llvm/ADT/Statistic.h" 23 #include "llvm/Analysis/AliasAnalysis.h" 24 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 25 #include "llvm/CodeGen/MachineDominators.h" 26 #include "llvm/CodeGen/MachineLoopInfo.h" 27 #include "llvm/CodeGen/MachinePostDominators.h" 28 #include "llvm/CodeGen/MachineRegisterInfo.h" 29 #include "llvm/Support/CommandLine.h" 30 #include "llvm/Support/Debug.h" 31 #include "llvm/Support/raw_ostream.h" 32 #include "llvm/Target/TargetInstrInfo.h" 33 #include "llvm/Target/TargetRegisterInfo.h" 34 #include "llvm/Target/TargetSubtargetInfo.h" 35 using namespace llvm; 36 37 #define DEBUG_TYPE "machine-sink" 38 39 static cl::opt<bool> 40 SplitEdges("machine-sink-split", 41 cl::desc("Split critical edges during machine sinking"), 42 cl::init(true), cl::Hidden); 43 44 static cl::opt<bool> 45 UseBlockFreqInfo("machine-sink-bfi", 46 cl::desc("Use block frequency info to find successors to sink"), 47 cl::init(true), cl::Hidden); 48 49 50 STATISTIC(NumSunk, "Number of machine instructions sunk"); 51 STATISTIC(NumSplit, "Number of critical edges split"); 52 STATISTIC(NumCoalesces, "Number of copies coalesced"); 53 54 namespace { 55 class MachineSinking : public MachineFunctionPass { 56 const TargetInstrInfo *TII; 57 const TargetRegisterInfo *TRI; 58 MachineRegisterInfo *MRI; // Machine register information 59 MachineDominatorTree *DT; // Machine dominator tree 60 MachinePostDominatorTree *PDT; // Machine post dominator tree 61 MachineLoopInfo *LI; 62 const MachineBlockFrequencyInfo *MBFI; 63 AliasAnalysis *AA; 64 65 // Remember which edges have been considered for breaking. 66 SmallSet<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 8> 67 CEBCandidates; 68 // Remember which edges we are about to split. 69 // This is different from CEBCandidates since those edges 70 // will be split. 71 SetVector<std::pair<MachineBasicBlock*,MachineBasicBlock*> > ToSplit; 72 73 public: 74 static char ID; // Pass identification 75 MachineSinking() : MachineFunctionPass(ID) { 76 initializeMachineSinkingPass(*PassRegistry::getPassRegistry()); 77 } 78 79 bool runOnMachineFunction(MachineFunction &MF) override; 80 81 void getAnalysisUsage(AnalysisUsage &AU) const override { 82 AU.setPreservesCFG(); 83 MachineFunctionPass::getAnalysisUsage(AU); 84 AU.addRequired<AliasAnalysis>(); 85 AU.addRequired<MachineDominatorTree>(); 86 AU.addRequired<MachinePostDominatorTree>(); 87 AU.addRequired<MachineLoopInfo>(); 88 AU.addPreserved<MachineDominatorTree>(); 89 AU.addPreserved<MachinePostDominatorTree>(); 90 AU.addPreserved<MachineLoopInfo>(); 91 if (UseBlockFreqInfo) 92 AU.addRequired<MachineBlockFrequencyInfo>(); 93 } 94 95 void releaseMemory() override { 96 CEBCandidates.clear(); 97 } 98 99 private: 100 bool ProcessBlock(MachineBasicBlock &MBB); 101 bool isWorthBreakingCriticalEdge(MachineInstr *MI, 102 MachineBasicBlock *From, 103 MachineBasicBlock *To); 104 /// \brief Postpone the splitting of the given critical 105 /// edge (\p From, \p To). 106 /// 107 /// We do not split the edges on the fly. Indeed, this invalidates 108 /// the dominance information and thus triggers a lot of updates 109 /// of that information underneath. 110 /// Instead, we postpone all the splits after each iteration of 111 /// the main loop. That way, the information is at least valid 112 /// for the lifetime of an iteration. 113 /// 114 /// \return True if the edge is marked as toSplit, false otherwise. 115 /// False can be returned if, for instance, this is not profitable. 116 bool PostponeSplitCriticalEdge(MachineInstr *MI, 117 MachineBasicBlock *From, 118 MachineBasicBlock *To, 119 bool BreakPHIEdge); 120 bool SinkInstruction(MachineInstr *MI, bool &SawStore); 121 bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, 122 MachineBasicBlock *DefMBB, 123 bool &BreakPHIEdge, bool &LocalUse) const; 124 MachineBasicBlock *FindSuccToSinkTo(MachineInstr *MI, MachineBasicBlock *MBB, 125 bool &BreakPHIEdge); 126 bool isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, 127 MachineBasicBlock *MBB, 128 MachineBasicBlock *SuccToSinkTo); 129 130 bool PerformTrivialForwardCoalescing(MachineInstr *MI, 131 MachineBasicBlock *MBB); 132 }; 133 } // end anonymous namespace 134 135 char MachineSinking::ID = 0; 136 char &llvm::MachineSinkingID = MachineSinking::ID; 137 INITIALIZE_PASS_BEGIN(MachineSinking, "machine-sink", 138 "Machine code sinking", false, false) 139 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 140 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 141 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 142 INITIALIZE_PASS_END(MachineSinking, "machine-sink", 143 "Machine code sinking", false, false) 144 145 bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI, 146 MachineBasicBlock *MBB) { 147 if (!MI->isCopy()) 148 return false; 149 150 unsigned SrcReg = MI->getOperand(1).getReg(); 151 unsigned DstReg = MI->getOperand(0).getReg(); 152 if (!TargetRegisterInfo::isVirtualRegister(SrcReg) || 153 !TargetRegisterInfo::isVirtualRegister(DstReg) || 154 !MRI->hasOneNonDBGUse(SrcReg)) 155 return false; 156 157 const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg); 158 const TargetRegisterClass *DRC = MRI->getRegClass(DstReg); 159 if (SRC != DRC) 160 return false; 161 162 MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 163 if (DefMI->isCopyLike()) 164 return false; 165 DEBUG(dbgs() << "Coalescing: " << *DefMI); 166 DEBUG(dbgs() << "*** to: " << *MI); 167 MRI->replaceRegWith(DstReg, SrcReg); 168 MI->eraseFromParent(); 169 170 // Conservatively, clear any kill flags, since it's possible that they are no 171 // longer correct. 172 MRI->clearKillFlags(SrcReg); 173 174 ++NumCoalesces; 175 return true; 176 } 177 178 /// AllUsesDominatedByBlock - Return true if all uses of the specified register 179 /// occur in blocks dominated by the specified block. If any use is in the 180 /// definition block, then return false since it is never legal to move def 181 /// after uses. 182 bool 183 MachineSinking::AllUsesDominatedByBlock(unsigned Reg, 184 MachineBasicBlock *MBB, 185 MachineBasicBlock *DefMBB, 186 bool &BreakPHIEdge, 187 bool &LocalUse) const { 188 assert(TargetRegisterInfo::isVirtualRegister(Reg) && 189 "Only makes sense for vregs"); 190 191 // Ignore debug uses because debug info doesn't affect the code. 192 if (MRI->use_nodbg_empty(Reg)) 193 return true; 194 195 // BreakPHIEdge is true if all the uses are in the successor MBB being sunken 196 // into and they are all PHI nodes. In this case, machine-sink must break 197 // the critical edge first. e.g. 198 // 199 // BB#1: derived from LLVM BB %bb4.preheader 200 // Predecessors according to CFG: BB#0 201 // ... 202 // %reg16385<def> = DEC64_32r %reg16437, %EFLAGS<imp-def,dead> 203 // ... 204 // JE_4 <BB#37>, %EFLAGS<imp-use> 205 // Successors according to CFG: BB#37 BB#2 206 // 207 // BB#2: derived from LLVM BB %bb.nph 208 // Predecessors according to CFG: BB#0 BB#1 209 // %reg16386<def> = PHI %reg16434, <BB#0>, %reg16385, <BB#1> 210 BreakPHIEdge = true; 211 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { 212 MachineInstr *UseInst = MO.getParent(); 213 unsigned OpNo = &MO - &UseInst->getOperand(0); 214 MachineBasicBlock *UseBlock = UseInst->getParent(); 215 if (!(UseBlock == MBB && UseInst->isPHI() && 216 UseInst->getOperand(OpNo+1).getMBB() == DefMBB)) { 217 BreakPHIEdge = false; 218 break; 219 } 220 } 221 if (BreakPHIEdge) 222 return true; 223 224 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { 225 // Determine the block of the use. 226 MachineInstr *UseInst = MO.getParent(); 227 unsigned OpNo = &MO - &UseInst->getOperand(0); 228 MachineBasicBlock *UseBlock = UseInst->getParent(); 229 if (UseInst->isPHI()) { 230 // PHI nodes use the operand in the predecessor block, not the block with 231 // the PHI. 232 UseBlock = UseInst->getOperand(OpNo+1).getMBB(); 233 } else if (UseBlock == DefMBB) { 234 LocalUse = true; 235 return false; 236 } 237 238 // Check that it dominates. 239 if (!DT->dominates(MBB, UseBlock)) 240 return false; 241 } 242 243 return true; 244 } 245 246 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { 247 if (skipOptnoneFunction(*MF.getFunction())) 248 return false; 249 250 DEBUG(dbgs() << "******** Machine Sinking ********\n"); 251 252 TII = MF.getSubtarget().getInstrInfo(); 253 TRI = MF.getSubtarget().getRegisterInfo(); 254 MRI = &MF.getRegInfo(); 255 DT = &getAnalysis<MachineDominatorTree>(); 256 PDT = &getAnalysis<MachinePostDominatorTree>(); 257 LI = &getAnalysis<MachineLoopInfo>(); 258 MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr; 259 AA = &getAnalysis<AliasAnalysis>(); 260 261 bool EverMadeChange = false; 262 263 while (1) { 264 bool MadeChange = false; 265 266 // Process all basic blocks. 267 CEBCandidates.clear(); 268 ToSplit.clear(); 269 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); 270 I != E; ++I) 271 MadeChange |= ProcessBlock(*I); 272 273 // If we have anything we marked as toSplit, split it now. 274 for (auto &Pair : ToSplit) { 275 auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, this); 276 if (NewSucc != nullptr) { 277 DEBUG(dbgs() << " *** Splitting critical edge:" 278 " BB#" << Pair.first->getNumber() 279 << " -- BB#" << NewSucc->getNumber() 280 << " -- BB#" << Pair.second->getNumber() << '\n'); 281 MadeChange = true; 282 ++NumSplit; 283 } else 284 DEBUG(dbgs() << " *** Not legal to break critical edge\n"); 285 } 286 // If this iteration over the code changed anything, keep iterating. 287 if (!MadeChange) break; 288 EverMadeChange = true; 289 } 290 return EverMadeChange; 291 } 292 293 bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { 294 // Can't sink anything out of a block that has less than two successors. 295 if (MBB.succ_size() <= 1 || MBB.empty()) return false; 296 297 // Don't bother sinking code out of unreachable blocks. In addition to being 298 // unprofitable, it can also lead to infinite looping, because in an 299 // unreachable loop there may be nowhere to stop. 300 if (!DT->isReachableFromEntry(&MBB)) return false; 301 302 bool MadeChange = false; 303 304 // Walk the basic block bottom-up. Remember if we saw a store. 305 MachineBasicBlock::iterator I = MBB.end(); 306 --I; 307 bool ProcessedBegin, SawStore = false; 308 do { 309 MachineInstr *MI = I; // The instruction to sink. 310 311 // Predecrement I (if it's not begin) so that it isn't invalidated by 312 // sinking. 313 ProcessedBegin = I == MBB.begin(); 314 if (!ProcessedBegin) 315 --I; 316 317 if (MI->isDebugValue()) 318 continue; 319 320 bool Joined = PerformTrivialForwardCoalescing(MI, &MBB); 321 if (Joined) { 322 MadeChange = true; 323 continue; 324 } 325 326 if (SinkInstruction(MI, SawStore)) 327 ++NumSunk, MadeChange = true; 328 329 // If we just processed the first instruction in the block, we're done. 330 } while (!ProcessedBegin); 331 332 return MadeChange; 333 } 334 335 bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, 336 MachineBasicBlock *From, 337 MachineBasicBlock *To) { 338 // FIXME: Need much better heuristics. 339 340 // If the pass has already considered breaking this edge (during this pass 341 // through the function), then let's go ahead and break it. This means 342 // sinking multiple "cheap" instructions into the same block. 343 if (!CEBCandidates.insert(std::make_pair(From, To)).second) 344 return true; 345 346 if (!MI->isCopy() && !TII->isAsCheapAsAMove(MI)) 347 return true; 348 349 // MI is cheap, we probably don't want to break the critical edge for it. 350 // However, if this would allow some definitions of its source operands 351 // to be sunk then it's probably worth it. 352 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 353 const MachineOperand &MO = MI->getOperand(i); 354 if (!MO.isReg() || !MO.isUse()) 355 continue; 356 unsigned Reg = MO.getReg(); 357 if (Reg == 0) 358 continue; 359 360 // We don't move live definitions of physical registers, 361 // so sinking their uses won't enable any opportunities. 362 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 363 continue; 364 365 // If this instruction is the only user of a virtual register, 366 // check if breaking the edge will enable sinking 367 // both this instruction and the defining instruction. 368 if (MRI->hasOneNonDBGUse(Reg)) { 369 // If the definition resides in same MBB, 370 // claim it's likely we can sink these together. 371 // If definition resides elsewhere, we aren't 372 // blocking it from being sunk so don't break the edge. 373 MachineInstr *DefMI = MRI->getVRegDef(Reg); 374 if (DefMI->getParent() == MI->getParent()) 375 return true; 376 } 377 } 378 379 return false; 380 } 381 382 bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr *MI, 383 MachineBasicBlock *FromBB, 384 MachineBasicBlock *ToBB, 385 bool BreakPHIEdge) { 386 if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB)) 387 return false; 388 389 // Avoid breaking back edge. From == To means backedge for single BB loop. 390 if (!SplitEdges || FromBB == ToBB) 391 return false; 392 393 // Check for backedges of more "complex" loops. 394 if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) && 395 LI->isLoopHeader(ToBB)) 396 return false; 397 398 // It's not always legal to break critical edges and sink the computation 399 // to the edge. 400 // 401 // BB#1: 402 // v1024 403 // Beq BB#3 404 // <fallthrough> 405 // BB#2: 406 // ... no uses of v1024 407 // <fallthrough> 408 // BB#3: 409 // ... 410 // = v1024 411 // 412 // If BB#1 -> BB#3 edge is broken and computation of v1024 is inserted: 413 // 414 // BB#1: 415 // ... 416 // Bne BB#2 417 // BB#4: 418 // v1024 = 419 // B BB#3 420 // BB#2: 421 // ... no uses of v1024 422 // <fallthrough> 423 // BB#3: 424 // ... 425 // = v1024 426 // 427 // This is incorrect since v1024 is not computed along the BB#1->BB#2->BB#3 428 // flow. We need to ensure the new basic block where the computation is 429 // sunk to dominates all the uses. 430 // It's only legal to break critical edge and sink the computation to the 431 // new block if all the predecessors of "To", except for "From", are 432 // not dominated by "From". Given SSA property, this means these 433 // predecessors are dominated by "To". 434 // 435 // There is no need to do this check if all the uses are PHI nodes. PHI 436 // sources are only defined on the specific predecessor edges. 437 if (!BreakPHIEdge) { 438 for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(), 439 E = ToBB->pred_end(); PI != E; ++PI) { 440 if (*PI == FromBB) 441 continue; 442 if (!DT->dominates(ToBB, *PI)) 443 return false; 444 } 445 } 446 447 ToSplit.insert(std::make_pair(FromBB, ToBB)); 448 449 return true; 450 } 451 452 static bool AvoidsSinking(MachineInstr *MI, MachineRegisterInfo *MRI) { 453 return MI->isInsertSubreg() || MI->isSubregToReg() || MI->isRegSequence(); 454 } 455 456 /// collectDebgValues - Scan instructions following MI and collect any 457 /// matching DBG_VALUEs. 458 static void collectDebugValues(MachineInstr *MI, 459 SmallVectorImpl<MachineInstr *> &DbgValues) { 460 DbgValues.clear(); 461 if (!MI->getOperand(0).isReg()) 462 return; 463 464 MachineBasicBlock::iterator DI = MI; ++DI; 465 for (MachineBasicBlock::iterator DE = MI->getParent()->end(); 466 DI != DE; ++DI) { 467 if (!DI->isDebugValue()) 468 return; 469 if (DI->getOperand(0).isReg() && 470 DI->getOperand(0).getReg() == MI->getOperand(0).getReg()) 471 DbgValues.push_back(DI); 472 } 473 } 474 475 /// isProfitableToSinkTo - Return true if it is profitable to sink MI. 476 bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, 477 MachineBasicBlock *MBB, 478 MachineBasicBlock *SuccToSinkTo) { 479 assert (MI && "Invalid MachineInstr!"); 480 assert (SuccToSinkTo && "Invalid SinkTo Candidate BB"); 481 482 if (MBB == SuccToSinkTo) 483 return false; 484 485 // It is profitable if SuccToSinkTo does not post dominate current block. 486 if (!PDT->dominates(SuccToSinkTo, MBB)) 487 return true; 488 489 // It is profitable to sink an instruction from a deeper loop to a shallower 490 // loop, even if the latter post-dominates the former (PR21115). 491 if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo)) 492 return true; 493 494 // Check if only use in post dominated block is PHI instruction. 495 bool NonPHIUse = false; 496 for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) { 497 MachineBasicBlock *UseBlock = UseInst.getParent(); 498 if (UseBlock == SuccToSinkTo && !UseInst.isPHI()) 499 NonPHIUse = true; 500 } 501 if (!NonPHIUse) 502 return true; 503 504 // If SuccToSinkTo post dominates then also it may be profitable if MI 505 // can further profitably sinked into another block in next round. 506 bool BreakPHIEdge = false; 507 // FIXME - If finding successor is compile time expensive then cache results. 508 if (MachineBasicBlock *MBB2 = FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge)) 509 return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2); 510 511 // If SuccToSinkTo is final destination and it is a post dominator of current 512 // block then it is not profitable to sink MI into SuccToSinkTo block. 513 return false; 514 } 515 516 /// FindSuccToSinkTo - Find a successor to sink this instruction to. 517 MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, 518 MachineBasicBlock *MBB, 519 bool &BreakPHIEdge) { 520 521 assert (MI && "Invalid MachineInstr!"); 522 assert (MBB && "Invalid MachineBasicBlock!"); 523 524 // Loop over all the operands of the specified instruction. If there is 525 // anything we can't handle, bail out. 526 527 // SuccToSinkTo - This is the successor to sink this instruction to, once we 528 // decide. 529 MachineBasicBlock *SuccToSinkTo = nullptr; 530 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 531 const MachineOperand &MO = MI->getOperand(i); 532 if (!MO.isReg()) continue; // Ignore non-register operands. 533 534 unsigned Reg = MO.getReg(); 535 if (Reg == 0) continue; 536 537 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 538 if (MO.isUse()) { 539 // If the physreg has no defs anywhere, it's just an ambient register 540 // and we can freely move its uses. Alternatively, if it's allocatable, 541 // it could get allocated to something with a def during allocation. 542 if (!MRI->isConstantPhysReg(Reg, *MBB->getParent())) 543 return nullptr; 544 } else if (!MO.isDead()) { 545 // A def that isn't dead. We can't move it. 546 return nullptr; 547 } 548 } else { 549 // Virtual register uses are always safe to sink. 550 if (MO.isUse()) continue; 551 552 // If it's not safe to move defs of the register class, then abort. 553 if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) 554 return nullptr; 555 556 // Virtual register defs can only be sunk if all their uses are in blocks 557 // dominated by one of the successors. 558 if (SuccToSinkTo) { 559 // If a previous operand picked a block to sink to, then this operand 560 // must be sinkable to the same block. 561 bool LocalUse = false; 562 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, 563 BreakPHIEdge, LocalUse)) 564 return nullptr; 565 566 continue; 567 } 568 569 // Otherwise, we should look at all the successors and decide which one 570 // we should sink to. If we have reliable block frequency information 571 // (frequency != 0) available, give successors with smaller frequencies 572 // higher priority, otherwise prioritize smaller loop depths. 573 SmallVector<MachineBasicBlock*, 4> Succs(MBB->succ_begin(), 574 MBB->succ_end()); 575 576 // Handle cases where sinking can happen but where the sink point isn't a 577 // successor. For example: 578 // 579 // x = computation 580 // if () {} else {} 581 // use x 582 // 583 const std::vector<MachineDomTreeNode *> &Children = 584 DT->getNode(MBB)->getChildren(); 585 for (const auto &DTChild : Children) 586 // DomTree children of MBB that have MBB as immediate dominator are added. 587 if (DTChild->getIDom()->getBlock() == MI->getParent() && 588 // Skip MBBs already added to the Succs vector above. 589 !MBB->isSuccessor(DTChild->getBlock())) 590 Succs.push_back(DTChild->getBlock()); 591 592 // Sort Successors according to their loop depth or block frequency info. 593 std::stable_sort( 594 Succs.begin(), Succs.end(), 595 [this](const MachineBasicBlock *L, const MachineBasicBlock *R) { 596 uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0; 597 uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0; 598 bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0; 599 return HasBlockFreq ? LHSFreq < RHSFreq 600 : LI->getLoopDepth(L) < LI->getLoopDepth(R); 601 }); 602 for (SmallVectorImpl<MachineBasicBlock *>::iterator SI = Succs.begin(), 603 E = Succs.end(); SI != E; ++SI) { 604 MachineBasicBlock *SuccBlock = *SI; 605 bool LocalUse = false; 606 if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB, 607 BreakPHIEdge, LocalUse)) { 608 SuccToSinkTo = SuccBlock; 609 break; 610 } 611 if (LocalUse) 612 // Def is used locally, it's never safe to move this def. 613 return nullptr; 614 } 615 616 // If we couldn't find a block to sink to, ignore this instruction. 617 if (!SuccToSinkTo) 618 return nullptr; 619 if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo)) 620 return nullptr; 621 } 622 } 623 624 // It is not possible to sink an instruction into its own block. This can 625 // happen with loops. 626 if (MBB == SuccToSinkTo) 627 return nullptr; 628 629 // It's not safe to sink instructions to EH landing pad. Control flow into 630 // landing pad is implicitly defined. 631 if (SuccToSinkTo && SuccToSinkTo->isLandingPad()) 632 return nullptr; 633 634 return SuccToSinkTo; 635 } 636 637 /// SinkInstruction - Determine whether it is safe to sink the specified machine 638 /// instruction out of its current block into a successor. 639 bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { 640 // Don't sink insert_subreg, subreg_to_reg, reg_sequence. These are meant to 641 // be close to the source to make it easier to coalesce. 642 if (AvoidsSinking(MI, MRI)) 643 return false; 644 645 // Check if it's safe to move the instruction. 646 if (!MI->isSafeToMove(TII, AA, SawStore)) 647 return false; 648 649 // FIXME: This should include support for sinking instructions within the 650 // block they are currently in to shorten the live ranges. We often get 651 // instructions sunk into the top of a large block, but it would be better to 652 // also sink them down before their first use in the block. This xform has to 653 // be careful not to *increase* register pressure though, e.g. sinking 654 // "x = y + z" down if it kills y and z would increase the live ranges of y 655 // and z and only shrink the live range of x. 656 657 bool BreakPHIEdge = false; 658 MachineBasicBlock *ParentBlock = MI->getParent(); 659 MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge); 660 661 // If there are no outputs, it must have side-effects. 662 if (!SuccToSinkTo) 663 return false; 664 665 666 // If the instruction to move defines a dead physical register which is live 667 // when leaving the basic block, don't move it because it could turn into a 668 // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>) 669 for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) { 670 const MachineOperand &MO = MI->getOperand(I); 671 if (!MO.isReg()) continue; 672 unsigned Reg = MO.getReg(); 673 if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 674 if (SuccToSinkTo->isLiveIn(Reg)) 675 return false; 676 } 677 678 DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo); 679 680 // If the block has multiple predecessors, this is a critical edge. 681 // Decide if we can sink along it or need to break the edge. 682 if (SuccToSinkTo->pred_size() > 1) { 683 // We cannot sink a load across a critical edge - there may be stores in 684 // other code paths. 685 bool TryBreak = false; 686 bool store = true; 687 if (!MI->isSafeToMove(TII, AA, store)) { 688 DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n"); 689 TryBreak = true; 690 } 691 692 // We don't want to sink across a critical edge if we don't dominate the 693 // successor. We could be introducing calculations to new code paths. 694 if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) { 695 DEBUG(dbgs() << " *** NOTE: Critical edge found\n"); 696 TryBreak = true; 697 } 698 699 // Don't sink instructions into a loop. 700 if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) { 701 DEBUG(dbgs() << " *** NOTE: Loop header found\n"); 702 TryBreak = true; 703 } 704 705 // Otherwise we are OK with sinking along a critical edge. 706 if (!TryBreak) 707 DEBUG(dbgs() << "Sinking along critical edge.\n"); 708 else { 709 // Mark this edge as to be split. 710 // If the edge can actually be split, the next iteration of the main loop 711 // will sink MI in the newly created block. 712 bool Status = 713 PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge); 714 if (!Status) 715 DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 716 "break critical edge\n"); 717 // The instruction will not be sunk this time. 718 return false; 719 } 720 } 721 722 if (BreakPHIEdge) { 723 // BreakPHIEdge is true if all the uses are in the successor MBB being 724 // sunken into and they are all PHI nodes. In this case, machine-sink must 725 // break the critical edge first. 726 bool Status = PostponeSplitCriticalEdge(MI, ParentBlock, 727 SuccToSinkTo, BreakPHIEdge); 728 if (!Status) 729 DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 730 "break critical edge\n"); 731 // The instruction will not be sunk this time. 732 return false; 733 } 734 735 // Determine where to insert into. Skip phi nodes. 736 MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin(); 737 while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI()) 738 ++InsertPos; 739 740 // collect matching debug values. 741 SmallVector<MachineInstr *, 2> DbgValuesToSink; 742 collectDebugValues(MI, DbgValuesToSink); 743 744 // Move the instruction. 745 SuccToSinkTo->splice(InsertPos, ParentBlock, MI, 746 ++MachineBasicBlock::iterator(MI)); 747 748 // Move debug values. 749 for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(), 750 DBE = DbgValuesToSink.end(); DBI != DBE; ++DBI) { 751 MachineInstr *DbgMI = *DBI; 752 SuccToSinkTo->splice(InsertPos, ParentBlock, DbgMI, 753 ++MachineBasicBlock::iterator(DbgMI)); 754 } 755 756 // Conservatively, clear any kill flags, since it's possible that they are no 757 // longer correct. 758 MI->clearKillInfo(); 759 760 return true; 761 } 762