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