1 //===- MachineSink.cpp - Sinking for machine instructions -----------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This pass moves instructions into successor blocks when possible, so that 10 // they aren't executed on paths where their results aren't needed. 11 // 12 // This pass is not intended to be a replacement or a complete alternative 13 // for an LLVM-IR-level sinking pass. It is only designed to sink simple 14 // constructs that are not exposed before lowering and instruction selection. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #include "llvm/ADT/DenseSet.h" 19 #include "llvm/ADT/PointerIntPair.h" 20 #include "llvm/ADT/SetVector.h" 21 #include "llvm/ADT/SmallSet.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/ADT/SparseBitVector.h" 24 #include "llvm/ADT/Statistic.h" 25 #include "llvm/Analysis/AliasAnalysis.h" 26 #include "llvm/CodeGen/MachineBasicBlock.h" 27 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 28 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 29 #include "llvm/CodeGen/MachineDominators.h" 30 #include "llvm/CodeGen/MachineFunction.h" 31 #include "llvm/CodeGen/MachineFunctionPass.h" 32 #include "llvm/CodeGen/MachineInstr.h" 33 #include "llvm/CodeGen/MachineLoopInfo.h" 34 #include "llvm/CodeGen/MachineOperand.h" 35 #include "llvm/CodeGen/MachinePostDominators.h" 36 #include "llvm/CodeGen/MachineRegisterInfo.h" 37 #include "llvm/CodeGen/TargetInstrInfo.h" 38 #include "llvm/CodeGen/TargetRegisterInfo.h" 39 #include "llvm/CodeGen/TargetSubtargetInfo.h" 40 #include "llvm/IR/BasicBlock.h" 41 #include "llvm/IR/DebugInfoMetadata.h" 42 #include "llvm/IR/LLVMContext.h" 43 #include "llvm/InitializePasses.h" 44 #include "llvm/MC/MCRegisterInfo.h" 45 #include "llvm/Pass.h" 46 #include "llvm/Support/BranchProbability.h" 47 #include "llvm/Support/CommandLine.h" 48 #include "llvm/Support/Debug.h" 49 #include "llvm/Support/raw_ostream.h" 50 #include <algorithm> 51 #include <cassert> 52 #include <cstdint> 53 #include <map> 54 #include <utility> 55 #include <vector> 56 57 using namespace llvm; 58 59 #define DEBUG_TYPE "machine-sink" 60 61 static cl::opt<bool> 62 SplitEdges("machine-sink-split", 63 cl::desc("Split critical edges during machine sinking"), 64 cl::init(true), cl::Hidden); 65 66 static cl::opt<bool> 67 UseBlockFreqInfo("machine-sink-bfi", 68 cl::desc("Use block frequency info to find successors to sink"), 69 cl::init(true), cl::Hidden); 70 71 static cl::opt<unsigned> SplitEdgeProbabilityThreshold( 72 "machine-sink-split-probability-threshold", 73 cl::desc( 74 "Percentage threshold for splitting single-instruction critical edge. " 75 "If the branch threshold is higher than this threshold, we allow " 76 "speculative execution of up to 1 instruction to avoid branching to " 77 "splitted critical edge"), 78 cl::init(40), cl::Hidden); 79 80 STATISTIC(NumSunk, "Number of machine instructions sunk"); 81 STATISTIC(NumSplit, "Number of critical edges split"); 82 STATISTIC(NumCoalesces, "Number of copies coalesced"); 83 STATISTIC(NumPostRACopySink, "Number of copies sunk after RA"); 84 85 namespace { 86 87 class MachineSinking : public MachineFunctionPass { 88 const TargetInstrInfo *TII; 89 const TargetRegisterInfo *TRI; 90 MachineRegisterInfo *MRI; // Machine register information 91 MachineDominatorTree *DT; // Machine dominator tree 92 MachinePostDominatorTree *PDT; // Machine post dominator tree 93 MachineLoopInfo *LI; 94 MachineBlockFrequencyInfo *MBFI; 95 const MachineBranchProbabilityInfo *MBPI; 96 AliasAnalysis *AA; 97 98 // Remember which edges have been considered for breaking. 99 SmallSet<std::pair<MachineBasicBlock*, MachineBasicBlock*>, 8> 100 CEBCandidates; 101 // Remember which edges we are about to split. 102 // This is different from CEBCandidates since those edges 103 // will be split. 104 SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit; 105 106 SparseBitVector<> RegsToClearKillFlags; 107 108 using AllSuccsCache = 109 std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>; 110 111 /// DBG_VALUE pointer and flag. The flag is true if this DBG_VALUE is 112 /// post-dominated by another DBG_VALUE of the same variable location. 113 /// This is necessary to detect sequences such as: 114 /// %0 = someinst 115 /// DBG_VALUE %0, !123, !DIExpression() 116 /// %1 = anotherinst 117 /// DBG_VALUE %1, !123, !DIExpression() 118 /// Where if %0 were to sink, the DBG_VAUE should not sink with it, as that 119 /// would re-order assignments. 120 using SeenDbgUser = PointerIntPair<MachineInstr *, 1>; 121 122 /// Record of DBG_VALUE uses of vregs in a block, so that we can identify 123 /// debug instructions to sink. 124 SmallDenseMap<unsigned, TinyPtrVector<SeenDbgUser>> SeenDbgUsers; 125 126 /// Record of debug variables that have had their locations set in the 127 /// current block. 128 DenseSet<DebugVariable> SeenDbgVars; 129 130 public: 131 static char ID; // Pass identification 132 133 MachineSinking() : MachineFunctionPass(ID) { 134 initializeMachineSinkingPass(*PassRegistry::getPassRegistry()); 135 } 136 137 bool runOnMachineFunction(MachineFunction &MF) override; 138 139 void getAnalysisUsage(AnalysisUsage &AU) const override { 140 MachineFunctionPass::getAnalysisUsage(AU); 141 AU.addRequired<AAResultsWrapperPass>(); 142 AU.addRequired<MachineDominatorTree>(); 143 AU.addRequired<MachinePostDominatorTree>(); 144 AU.addRequired<MachineLoopInfo>(); 145 AU.addRequired<MachineBranchProbabilityInfo>(); 146 AU.addPreserved<MachineLoopInfo>(); 147 if (UseBlockFreqInfo) 148 AU.addRequired<MachineBlockFrequencyInfo>(); 149 } 150 151 void releaseMemory() override { 152 CEBCandidates.clear(); 153 } 154 155 private: 156 bool ProcessBlock(MachineBasicBlock &MBB); 157 void ProcessDbgInst(MachineInstr &MI); 158 bool isWorthBreakingCriticalEdge(MachineInstr &MI, 159 MachineBasicBlock *From, 160 MachineBasicBlock *To); 161 162 /// Postpone the splitting of the given critical 163 /// edge (\p From, \p To). 164 /// 165 /// We do not split the edges on the fly. Indeed, this invalidates 166 /// the dominance information and thus triggers a lot of updates 167 /// of that information underneath. 168 /// Instead, we postpone all the splits after each iteration of 169 /// the main loop. That way, the information is at least valid 170 /// for the lifetime of an iteration. 171 /// 172 /// \return True if the edge is marked as toSplit, false otherwise. 173 /// False can be returned if, for instance, this is not profitable. 174 bool PostponeSplitCriticalEdge(MachineInstr &MI, 175 MachineBasicBlock *From, 176 MachineBasicBlock *To, 177 bool BreakPHIEdge); 178 bool SinkInstruction(MachineInstr &MI, bool &SawStore, 179 AllSuccsCache &AllSuccessors); 180 181 /// If we sink a COPY inst, some debug users of it's destination may no 182 /// longer be dominated by the COPY, and will eventually be dropped. 183 /// This is easily rectified by forwarding the non-dominated debug uses 184 /// to the copy source. 185 void SalvageUnsunkDebugUsersOfCopy(MachineInstr &, 186 MachineBasicBlock *TargetBlock); 187 bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, 188 MachineBasicBlock *DefMBB, 189 bool &BreakPHIEdge, bool &LocalUse) const; 190 MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB, 191 bool &BreakPHIEdge, AllSuccsCache &AllSuccessors); 192 bool isProfitableToSinkTo(unsigned Reg, MachineInstr &MI, 193 MachineBasicBlock *MBB, 194 MachineBasicBlock *SuccToSinkTo, 195 AllSuccsCache &AllSuccessors); 196 197 bool PerformTrivialForwardCoalescing(MachineInstr &MI, 198 MachineBasicBlock *MBB); 199 200 SmallVector<MachineBasicBlock *, 4> & 201 GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB, 202 AllSuccsCache &AllSuccessors) const; 203 }; 204 205 } // end anonymous namespace 206 207 char MachineSinking::ID = 0; 208 209 char &llvm::MachineSinkingID = MachineSinking::ID; 210 211 INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE, 212 "Machine code sinking", false, false) 213 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 214 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 215 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 216 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 217 INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE, 218 "Machine code sinking", false, false) 219 220 bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI, 221 MachineBasicBlock *MBB) { 222 if (!MI.isCopy()) 223 return false; 224 225 Register SrcReg = MI.getOperand(1).getReg(); 226 Register DstReg = MI.getOperand(0).getReg(); 227 if (!Register::isVirtualRegister(SrcReg) || 228 !Register::isVirtualRegister(DstReg) || !MRI->hasOneNonDBGUse(SrcReg)) 229 return false; 230 231 const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg); 232 const TargetRegisterClass *DRC = MRI->getRegClass(DstReg); 233 if (SRC != DRC) 234 return false; 235 236 MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 237 if (DefMI->isCopyLike()) 238 return false; 239 LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI); 240 LLVM_DEBUG(dbgs() << "*** to: " << MI); 241 MRI->replaceRegWith(DstReg, SrcReg); 242 MI.eraseFromParent(); 243 244 // Conservatively, clear any kill flags, since it's possible that they are no 245 // longer correct. 246 MRI->clearKillFlags(SrcReg); 247 248 ++NumCoalesces; 249 return true; 250 } 251 252 /// AllUsesDominatedByBlock - Return true if all uses of the specified register 253 /// occur in blocks dominated by the specified block. If any use is in the 254 /// definition block, then return false since it is never legal to move def 255 /// after uses. 256 bool 257 MachineSinking::AllUsesDominatedByBlock(unsigned Reg, 258 MachineBasicBlock *MBB, 259 MachineBasicBlock *DefMBB, 260 bool &BreakPHIEdge, 261 bool &LocalUse) const { 262 assert(Register::isVirtualRegister(Reg) && "Only makes sense for vregs"); 263 264 // Ignore debug uses because debug info doesn't affect the code. 265 if (MRI->use_nodbg_empty(Reg)) 266 return true; 267 268 // BreakPHIEdge is true if all the uses are in the successor MBB being sunken 269 // into and they are all PHI nodes. In this case, machine-sink must break 270 // the critical edge first. e.g. 271 // 272 // %bb.1: 273 // Predecessors according to CFG: %bb.0 274 // ... 275 // %def = DEC64_32r %x, implicit-def dead %eflags 276 // ... 277 // JE_4 <%bb.37>, implicit %eflags 278 // Successors according to CFG: %bb.37 %bb.2 279 // 280 // %bb.2: 281 // %p = PHI %y, %bb.0, %def, %bb.1 282 if (all_of(MRI->use_nodbg_operands(Reg), [&](MachineOperand &MO) { 283 MachineInstr *UseInst = MO.getParent(); 284 unsigned OpNo = UseInst->getOperandNo(&MO); 285 MachineBasicBlock *UseBlock = UseInst->getParent(); 286 return UseBlock == MBB && UseInst->isPHI() && 287 UseInst->getOperand(OpNo + 1).getMBB() == DefMBB; 288 })) { 289 BreakPHIEdge = true; 290 return true; 291 } 292 293 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { 294 // Determine the block of the use. 295 MachineInstr *UseInst = MO.getParent(); 296 unsigned OpNo = &MO - &UseInst->getOperand(0); 297 MachineBasicBlock *UseBlock = UseInst->getParent(); 298 if (UseInst->isPHI()) { 299 // PHI nodes use the operand in the predecessor block, not the block with 300 // the PHI. 301 UseBlock = UseInst->getOperand(OpNo+1).getMBB(); 302 } else if (UseBlock == DefMBB) { 303 LocalUse = true; 304 return false; 305 } 306 307 // Check that it dominates. 308 if (!DT->dominates(MBB, UseBlock)) 309 return false; 310 } 311 312 return true; 313 } 314 315 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { 316 if (skipFunction(MF.getFunction())) 317 return false; 318 319 LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n"); 320 321 TII = MF.getSubtarget().getInstrInfo(); 322 TRI = MF.getSubtarget().getRegisterInfo(); 323 MRI = &MF.getRegInfo(); 324 DT = &getAnalysis<MachineDominatorTree>(); 325 PDT = &getAnalysis<MachinePostDominatorTree>(); 326 LI = &getAnalysis<MachineLoopInfo>(); 327 MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr; 328 MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 329 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 330 331 bool EverMadeChange = false; 332 333 while (true) { 334 bool MadeChange = false; 335 336 // Process all basic blocks. 337 CEBCandidates.clear(); 338 ToSplit.clear(); 339 for (auto &MBB: MF) 340 MadeChange |= ProcessBlock(MBB); 341 342 // If we have anything we marked as toSplit, split it now. 343 for (auto &Pair : ToSplit) { 344 auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this); 345 if (NewSucc != nullptr) { 346 LLVM_DEBUG(dbgs() << " *** Splitting critical edge: " 347 << printMBBReference(*Pair.first) << " -- " 348 << printMBBReference(*NewSucc) << " -- " 349 << printMBBReference(*Pair.second) << '\n'); 350 if (MBFI) { 351 auto NewSuccFreq = MBFI->getBlockFreq(Pair.first) * 352 MBPI->getEdgeProbability(Pair.first, NewSucc); 353 MBFI->setBlockFreq(NewSucc, NewSuccFreq.getFrequency()); 354 } 355 MadeChange = true; 356 ++NumSplit; 357 } else 358 LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n"); 359 } 360 // If this iteration over the code changed anything, keep iterating. 361 if (!MadeChange) break; 362 EverMadeChange = true; 363 } 364 365 // Now clear any kill flags for recorded registers. 366 for (auto I : RegsToClearKillFlags) 367 MRI->clearKillFlags(I); 368 RegsToClearKillFlags.clear(); 369 370 return EverMadeChange; 371 } 372 373 bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { 374 // Can't sink anything out of a block that has less than two successors. 375 if (MBB.succ_size() <= 1 || MBB.empty()) return false; 376 377 // Don't bother sinking code out of unreachable blocks. In addition to being 378 // unprofitable, it can also lead to infinite looping, because in an 379 // unreachable loop there may be nowhere to stop. 380 if (!DT->isReachableFromEntry(&MBB)) return false; 381 382 bool MadeChange = false; 383 384 // Cache all successors, sorted by frequency info and loop depth. 385 AllSuccsCache AllSuccessors; 386 387 // Walk the basic block bottom-up. Remember if we saw a store. 388 MachineBasicBlock::iterator I = MBB.end(); 389 --I; 390 bool ProcessedBegin, SawStore = false; 391 do { 392 MachineInstr &MI = *I; // The instruction to sink. 393 394 // Predecrement I (if it's not begin) so that it isn't invalidated by 395 // sinking. 396 ProcessedBegin = I == MBB.begin(); 397 if (!ProcessedBegin) 398 --I; 399 400 if (MI.isDebugInstr()) { 401 if (MI.isDebugValue()) 402 ProcessDbgInst(MI); 403 continue; 404 } 405 406 bool Joined = PerformTrivialForwardCoalescing(MI, &MBB); 407 if (Joined) { 408 MadeChange = true; 409 continue; 410 } 411 412 if (SinkInstruction(MI, SawStore, AllSuccessors)) { 413 ++NumSunk; 414 MadeChange = true; 415 } 416 417 // If we just processed the first instruction in the block, we're done. 418 } while (!ProcessedBegin); 419 420 SeenDbgUsers.clear(); 421 SeenDbgVars.clear(); 422 423 return MadeChange; 424 } 425 426 void MachineSinking::ProcessDbgInst(MachineInstr &MI) { 427 // When we see DBG_VALUEs for registers, record any vreg it reads, so that 428 // we know what to sink if the vreg def sinks. 429 assert(MI.isDebugValue() && "Expected DBG_VALUE for processing"); 430 431 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(), 432 MI.getDebugLoc()->getInlinedAt()); 433 bool SeenBefore = SeenDbgVars.count(Var) != 0; 434 435 MachineOperand &MO = MI.getDebugOperand(0); 436 if (MO.isReg() && MO.getReg().isVirtual()) 437 SeenDbgUsers[MO.getReg()].push_back(SeenDbgUser(&MI, SeenBefore)); 438 439 // Record the variable for any DBG_VALUE, to avoid re-ordering any of them. 440 SeenDbgVars.insert(Var); 441 } 442 443 bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI, 444 MachineBasicBlock *From, 445 MachineBasicBlock *To) { 446 // FIXME: Need much better heuristics. 447 448 // If the pass has already considered breaking this edge (during this pass 449 // through the function), then let's go ahead and break it. This means 450 // sinking multiple "cheap" instructions into the same block. 451 if (!CEBCandidates.insert(std::make_pair(From, To)).second) 452 return true; 453 454 if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI)) 455 return true; 456 457 if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <= 458 BranchProbability(SplitEdgeProbabilityThreshold, 100)) 459 return true; 460 461 // MI is cheap, we probably don't want to break the critical edge for it. 462 // However, if this would allow some definitions of its source operands 463 // to be sunk then it's probably worth it. 464 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 465 const MachineOperand &MO = MI.getOperand(i); 466 if (!MO.isReg() || !MO.isUse()) 467 continue; 468 Register Reg = MO.getReg(); 469 if (Reg == 0) 470 continue; 471 472 // We don't move live definitions of physical registers, 473 // so sinking their uses won't enable any opportunities. 474 if (Register::isPhysicalRegister(Reg)) 475 continue; 476 477 // If this instruction is the only user of a virtual register, 478 // check if breaking the edge will enable sinking 479 // both this instruction and the defining instruction. 480 if (MRI->hasOneNonDBGUse(Reg)) { 481 // If the definition resides in same MBB, 482 // claim it's likely we can sink these together. 483 // If definition resides elsewhere, we aren't 484 // blocking it from being sunk so don't break the edge. 485 MachineInstr *DefMI = MRI->getVRegDef(Reg); 486 if (DefMI->getParent() == MI.getParent()) 487 return true; 488 } 489 } 490 491 return false; 492 } 493 494 bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI, 495 MachineBasicBlock *FromBB, 496 MachineBasicBlock *ToBB, 497 bool BreakPHIEdge) { 498 if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB)) 499 return false; 500 501 // Avoid breaking back edge. From == To means backedge for single BB loop. 502 if (!SplitEdges || FromBB == ToBB) 503 return false; 504 505 // Check for backedges of more "complex" loops. 506 if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) && 507 LI->isLoopHeader(ToBB)) 508 return false; 509 510 // It's not always legal to break critical edges and sink the computation 511 // to the edge. 512 // 513 // %bb.1: 514 // v1024 515 // Beq %bb.3 516 // <fallthrough> 517 // %bb.2: 518 // ... no uses of v1024 519 // <fallthrough> 520 // %bb.3: 521 // ... 522 // = v1024 523 // 524 // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted: 525 // 526 // %bb.1: 527 // ... 528 // Bne %bb.2 529 // %bb.4: 530 // v1024 = 531 // B %bb.3 532 // %bb.2: 533 // ... no uses of v1024 534 // <fallthrough> 535 // %bb.3: 536 // ... 537 // = v1024 538 // 539 // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3 540 // flow. We need to ensure the new basic block where the computation is 541 // sunk to dominates all the uses. 542 // It's only legal to break critical edge and sink the computation to the 543 // new block if all the predecessors of "To", except for "From", are 544 // not dominated by "From". Given SSA property, this means these 545 // predecessors are dominated by "To". 546 // 547 // There is no need to do this check if all the uses are PHI nodes. PHI 548 // sources are only defined on the specific predecessor edges. 549 if (!BreakPHIEdge) { 550 for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(), 551 E = ToBB->pred_end(); PI != E; ++PI) { 552 if (*PI == FromBB) 553 continue; 554 if (!DT->dominates(ToBB, *PI)) 555 return false; 556 } 557 } 558 559 ToSplit.insert(std::make_pair(FromBB, ToBB)); 560 561 return true; 562 } 563 564 /// isProfitableToSinkTo - Return true if it is profitable to sink MI. 565 bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr &MI, 566 MachineBasicBlock *MBB, 567 MachineBasicBlock *SuccToSinkTo, 568 AllSuccsCache &AllSuccessors) { 569 assert (SuccToSinkTo && "Invalid SinkTo Candidate BB"); 570 571 if (MBB == SuccToSinkTo) 572 return false; 573 574 // It is profitable if SuccToSinkTo does not post dominate current block. 575 if (!PDT->dominates(SuccToSinkTo, MBB)) 576 return true; 577 578 // It is profitable to sink an instruction from a deeper loop to a shallower 579 // loop, even if the latter post-dominates the former (PR21115). 580 if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo)) 581 return true; 582 583 // Check if only use in post dominated block is PHI instruction. 584 bool NonPHIUse = false; 585 for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) { 586 MachineBasicBlock *UseBlock = UseInst.getParent(); 587 if (UseBlock == SuccToSinkTo && !UseInst.isPHI()) 588 NonPHIUse = true; 589 } 590 if (!NonPHIUse) 591 return true; 592 593 // If SuccToSinkTo post dominates then also it may be profitable if MI 594 // can further profitably sinked into another block in next round. 595 bool BreakPHIEdge = false; 596 // FIXME - If finding successor is compile time expensive then cache results. 597 if (MachineBasicBlock *MBB2 = 598 FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors)) 599 return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors); 600 601 // If SuccToSinkTo is final destination and it is a post dominator of current 602 // block then it is not profitable to sink MI into SuccToSinkTo block. 603 return false; 604 } 605 606 /// Get the sorted sequence of successors for this MachineBasicBlock, possibly 607 /// computing it if it was not already cached. 608 SmallVector<MachineBasicBlock *, 4> & 609 MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB, 610 AllSuccsCache &AllSuccessors) const { 611 // Do we have the sorted successors in cache ? 612 auto Succs = AllSuccessors.find(MBB); 613 if (Succs != AllSuccessors.end()) 614 return Succs->second; 615 616 SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->succ_begin(), 617 MBB->succ_end()); 618 619 // Handle cases where sinking can happen but where the sink point isn't a 620 // successor. For example: 621 // 622 // x = computation 623 // if () {} else {} 624 // use x 625 // 626 for (MachineDomTreeNode *DTChild : DT->getNode(MBB)->children()) { 627 // DomTree children of MBB that have MBB as immediate dominator are added. 628 if (DTChild->getIDom()->getBlock() == MI.getParent() && 629 // Skip MBBs already added to the AllSuccs vector above. 630 !MBB->isSuccessor(DTChild->getBlock())) 631 AllSuccs.push_back(DTChild->getBlock()); 632 } 633 634 // Sort Successors according to their loop depth or block frequency info. 635 llvm::stable_sort( 636 AllSuccs, [this](const MachineBasicBlock *L, const MachineBasicBlock *R) { 637 uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0; 638 uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0; 639 bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0; 640 return HasBlockFreq ? LHSFreq < RHSFreq 641 : LI->getLoopDepth(L) < LI->getLoopDepth(R); 642 }); 643 644 auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs)); 645 646 return it.first->second; 647 } 648 649 /// FindSuccToSinkTo - Find a successor to sink this instruction to. 650 MachineBasicBlock * 651 MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB, 652 bool &BreakPHIEdge, 653 AllSuccsCache &AllSuccessors) { 654 assert (MBB && "Invalid MachineBasicBlock!"); 655 656 // Loop over all the operands of the specified instruction. If there is 657 // anything we can't handle, bail out. 658 659 // SuccToSinkTo - This is the successor to sink this instruction to, once we 660 // decide. 661 MachineBasicBlock *SuccToSinkTo = nullptr; 662 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 663 const MachineOperand &MO = MI.getOperand(i); 664 if (!MO.isReg()) continue; // Ignore non-register operands. 665 666 Register Reg = MO.getReg(); 667 if (Reg == 0) continue; 668 669 if (Register::isPhysicalRegister(Reg)) { 670 if (MO.isUse()) { 671 // If the physreg has no defs anywhere, it's just an ambient register 672 // and we can freely move its uses. Alternatively, if it's allocatable, 673 // it could get allocated to something with a def during allocation. 674 if (!MRI->isConstantPhysReg(Reg)) 675 return nullptr; 676 } else if (!MO.isDead()) { 677 // A def that isn't dead. We can't move it. 678 return nullptr; 679 } 680 } else { 681 // Virtual register uses are always safe to sink. 682 if (MO.isUse()) continue; 683 684 // If it's not safe to move defs of the register class, then abort. 685 if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) 686 return nullptr; 687 688 // Virtual register defs can only be sunk if all their uses are in blocks 689 // dominated by one of the successors. 690 if (SuccToSinkTo) { 691 // If a previous operand picked a block to sink to, then this operand 692 // must be sinkable to the same block. 693 bool LocalUse = false; 694 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, 695 BreakPHIEdge, LocalUse)) 696 return nullptr; 697 698 continue; 699 } 700 701 // Otherwise, we should look at all the successors and decide which one 702 // we should sink to. If we have reliable block frequency information 703 // (frequency != 0) available, give successors with smaller frequencies 704 // higher priority, otherwise prioritize smaller loop depths. 705 for (MachineBasicBlock *SuccBlock : 706 GetAllSortedSuccessors(MI, MBB, AllSuccessors)) { 707 bool LocalUse = false; 708 if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB, 709 BreakPHIEdge, LocalUse)) { 710 SuccToSinkTo = SuccBlock; 711 break; 712 } 713 if (LocalUse) 714 // Def is used locally, it's never safe to move this def. 715 return nullptr; 716 } 717 718 // If we couldn't find a block to sink to, ignore this instruction. 719 if (!SuccToSinkTo) 720 return nullptr; 721 if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors)) 722 return nullptr; 723 } 724 } 725 726 // It is not possible to sink an instruction into its own block. This can 727 // happen with loops. 728 if (MBB == SuccToSinkTo) 729 return nullptr; 730 731 // It's not safe to sink instructions to EH landing pad. Control flow into 732 // landing pad is implicitly defined. 733 if (SuccToSinkTo && SuccToSinkTo->isEHPad()) 734 return nullptr; 735 736 // It ought to be okay to sink instructions into an INLINEASM_BR target, but 737 // only if we make sure that MI occurs _before_ an INLINEASM_BR instruction in 738 // the source block (which this code does not yet do). So for now, forbid 739 // doing so. 740 if (SuccToSinkTo && SuccToSinkTo->isInlineAsmBrIndirectTarget()) 741 return nullptr; 742 743 return SuccToSinkTo; 744 } 745 746 /// Return true if MI is likely to be usable as a memory operation by the 747 /// implicit null check optimization. 748 /// 749 /// This is a "best effort" heuristic, and should not be relied upon for 750 /// correctness. This returning true does not guarantee that the implicit null 751 /// check optimization is legal over MI, and this returning false does not 752 /// guarantee MI cannot possibly be used to do a null check. 753 static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI, 754 const TargetInstrInfo *TII, 755 const TargetRegisterInfo *TRI) { 756 using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate; 757 758 auto *MBB = MI.getParent(); 759 if (MBB->pred_size() != 1) 760 return false; 761 762 auto *PredMBB = *MBB->pred_begin(); 763 auto *PredBB = PredMBB->getBasicBlock(); 764 765 // Frontends that don't use implicit null checks have no reason to emit 766 // branches with make.implicit metadata, and this function should always 767 // return false for them. 768 if (!PredBB || 769 !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit)) 770 return false; 771 772 const MachineOperand *BaseOp; 773 int64_t Offset; 774 bool OffsetIsScalable; 775 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI)) 776 return false; 777 778 if (!BaseOp->isReg()) 779 return false; 780 781 if (!(MI.mayLoad() && !MI.isPredicable())) 782 return false; 783 784 MachineBranchPredicate MBP; 785 if (TII->analyzeBranchPredicate(*PredMBB, MBP, false)) 786 return false; 787 788 return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 && 789 (MBP.Predicate == MachineBranchPredicate::PRED_NE || 790 MBP.Predicate == MachineBranchPredicate::PRED_EQ) && 791 MBP.LHS.getReg() == BaseOp->getReg(); 792 } 793 794 /// If the sunk instruction is a copy, try to forward the copy instead of 795 /// leaving an 'undef' DBG_VALUE in the original location. Don't do this if 796 /// there's any subregister weirdness involved. Returns true if copy 797 /// propagation occurred. 798 static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI) { 799 const MachineRegisterInfo &MRI = SinkInst.getMF()->getRegInfo(); 800 const TargetInstrInfo &TII = *SinkInst.getMF()->getSubtarget().getInstrInfo(); 801 802 // Copy DBG_VALUE operand and set the original to undef. We then check to 803 // see whether this is something that can be copy-forwarded. If it isn't, 804 // continue around the loop. 805 MachineOperand &DbgMO = DbgMI.getDebugOperand(0); 806 807 const MachineOperand *SrcMO = nullptr, *DstMO = nullptr; 808 auto CopyOperands = TII.isCopyInstr(SinkInst); 809 if (!CopyOperands) 810 return false; 811 SrcMO = CopyOperands->Source; 812 DstMO = CopyOperands->Destination; 813 814 // Check validity of forwarding this copy. 815 bool PostRA = MRI.getNumVirtRegs() == 0; 816 817 // Trying to forward between physical and virtual registers is too hard. 818 if (DbgMO.getReg().isVirtual() != SrcMO->getReg().isVirtual()) 819 return false; 820 821 // Only try virtual register copy-forwarding before regalloc, and physical 822 // register copy-forwarding after regalloc. 823 bool arePhysRegs = !DbgMO.getReg().isVirtual(); 824 if (arePhysRegs != PostRA) 825 return false; 826 827 // Pre-regalloc, only forward if all subregisters agree (or there are no 828 // subregs at all). More analysis might recover some forwardable copies. 829 if (!PostRA && (DbgMO.getSubReg() != SrcMO->getSubReg() || 830 DbgMO.getSubReg() != DstMO->getSubReg())) 831 return false; 832 833 // Post-regalloc, we may be sinking a DBG_VALUE of a sub or super-register 834 // of this copy. Only forward the copy if the DBG_VALUE operand exactly 835 // matches the copy destination. 836 if (PostRA && DbgMO.getReg() != DstMO->getReg()) 837 return false; 838 839 DbgMO.setReg(SrcMO->getReg()); 840 DbgMO.setSubReg(SrcMO->getSubReg()); 841 return true; 842 } 843 844 /// Sink an instruction and its associated debug instructions. 845 static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo, 846 MachineBasicBlock::iterator InsertPos, 847 SmallVectorImpl<MachineInstr *> &DbgValuesToSink) { 848 849 // If we cannot find a location to use (merge with), then we erase the debug 850 // location to prevent debug-info driven tools from potentially reporting 851 // wrong location information. 852 if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end()) 853 MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(), 854 InsertPos->getDebugLoc())); 855 else 856 MI.setDebugLoc(DebugLoc()); 857 858 // Move the instruction. 859 MachineBasicBlock *ParentBlock = MI.getParent(); 860 SuccToSinkTo.splice(InsertPos, ParentBlock, MI, 861 ++MachineBasicBlock::iterator(MI)); 862 863 // Sink a copy of debug users to the insert position. Mark the original 864 // DBG_VALUE location as 'undef', indicating that any earlier variable 865 // location should be terminated as we've optimised away the value at this 866 // point. 867 for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(), 868 DBE = DbgValuesToSink.end(); 869 DBI != DBE; ++DBI) { 870 MachineInstr *DbgMI = *DBI; 871 MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(*DBI); 872 SuccToSinkTo.insert(InsertPos, NewDbgMI); 873 874 if (!attemptDebugCopyProp(MI, *DbgMI)) 875 DbgMI->setDebugValueUndef(); 876 } 877 } 878 879 /// SinkInstruction - Determine whether it is safe to sink the specified machine 880 /// instruction out of its current block into a successor. 881 bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore, 882 AllSuccsCache &AllSuccessors) { 883 // Don't sink instructions that the target prefers not to sink. 884 if (!TII->shouldSink(MI)) 885 return false; 886 887 // Check if it's safe to move the instruction. 888 if (!MI.isSafeToMove(AA, SawStore)) 889 return false; 890 891 // Convergent operations may not be made control-dependent on additional 892 // values. 893 if (MI.isConvergent()) 894 return false; 895 896 // Don't break implicit null checks. This is a performance heuristic, and not 897 // required for correctness. 898 if (SinkingPreventsImplicitNullCheck(MI, TII, TRI)) 899 return false; 900 901 // FIXME: This should include support for sinking instructions within the 902 // block they are currently in to shorten the live ranges. We often get 903 // instructions sunk into the top of a large block, but it would be better to 904 // also sink them down before their first use in the block. This xform has to 905 // be careful not to *increase* register pressure though, e.g. sinking 906 // "x = y + z" down if it kills y and z would increase the live ranges of y 907 // and z and only shrink the live range of x. 908 909 bool BreakPHIEdge = false; 910 MachineBasicBlock *ParentBlock = MI.getParent(); 911 MachineBasicBlock *SuccToSinkTo = 912 FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors); 913 914 // If there are no outputs, it must have side-effects. 915 if (!SuccToSinkTo) 916 return false; 917 918 // If the instruction to move defines a dead physical register which is live 919 // when leaving the basic block, don't move it because it could turn into a 920 // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>) 921 for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) { 922 const MachineOperand &MO = MI.getOperand(I); 923 if (!MO.isReg()) continue; 924 Register Reg = MO.getReg(); 925 if (Reg == 0 || !Register::isPhysicalRegister(Reg)) 926 continue; 927 if (SuccToSinkTo->isLiveIn(Reg)) 928 return false; 929 } 930 931 LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo); 932 933 // If the block has multiple predecessors, this is a critical edge. 934 // Decide if we can sink along it or need to break the edge. 935 if (SuccToSinkTo->pred_size() > 1) { 936 // We cannot sink a load across a critical edge - there may be stores in 937 // other code paths. 938 bool TryBreak = false; 939 bool store = true; 940 if (!MI.isSafeToMove(AA, store)) { 941 LLVM_DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n"); 942 TryBreak = true; 943 } 944 945 // We don't want to sink across a critical edge if we don't dominate the 946 // successor. We could be introducing calculations to new code paths. 947 if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) { 948 LLVM_DEBUG(dbgs() << " *** NOTE: Critical edge found\n"); 949 TryBreak = true; 950 } 951 952 // Don't sink instructions into a loop. 953 if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) { 954 LLVM_DEBUG(dbgs() << " *** NOTE: Loop header found\n"); 955 TryBreak = true; 956 } 957 958 // Otherwise we are OK with sinking along a critical edge. 959 if (!TryBreak) 960 LLVM_DEBUG(dbgs() << "Sinking along critical edge.\n"); 961 else { 962 // Mark this edge as to be split. 963 // If the edge can actually be split, the next iteration of the main loop 964 // will sink MI in the newly created block. 965 bool Status = 966 PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge); 967 if (!Status) 968 LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 969 "break critical edge\n"); 970 // The instruction will not be sunk this time. 971 return false; 972 } 973 } 974 975 if (BreakPHIEdge) { 976 // BreakPHIEdge is true if all the uses are in the successor MBB being 977 // sunken into and they are all PHI nodes. In this case, machine-sink must 978 // break the critical edge first. 979 bool Status = PostponeSplitCriticalEdge(MI, ParentBlock, 980 SuccToSinkTo, BreakPHIEdge); 981 if (!Status) 982 LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 983 "break critical edge\n"); 984 // The instruction will not be sunk this time. 985 return false; 986 } 987 988 // Determine where to insert into. Skip phi nodes. 989 MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin(); 990 while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI()) 991 ++InsertPos; 992 993 // Collect debug users of any vreg that this inst defines. 994 SmallVector<MachineInstr *, 4> DbgUsersToSink; 995 for (auto &MO : MI.operands()) { 996 if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual()) 997 continue; 998 if (!SeenDbgUsers.count(MO.getReg())) 999 continue; 1000 1001 // Sink any users that don't pass any other DBG_VALUEs for this variable. 1002 auto &Users = SeenDbgUsers[MO.getReg()]; 1003 for (auto &User : Users) { 1004 MachineInstr *DbgMI = User.getPointer(); 1005 if (User.getInt()) { 1006 // This DBG_VALUE would re-order assignments. If we can't copy-propagate 1007 // it, it can't be recovered. Set it undef. 1008 if (!attemptDebugCopyProp(MI, *DbgMI)) 1009 DbgMI->setDebugValueUndef(); 1010 } else { 1011 DbgUsersToSink.push_back(DbgMI); 1012 } 1013 } 1014 } 1015 1016 // After sinking, some debug users may not be dominated any more. If possible, 1017 // copy-propagate their operands. As it's expensive, don't do this if there's 1018 // no debuginfo in the program. 1019 if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy()) 1020 SalvageUnsunkDebugUsersOfCopy(MI, SuccToSinkTo); 1021 1022 performSink(MI, *SuccToSinkTo, InsertPos, DbgUsersToSink); 1023 1024 // Conservatively, clear any kill flags, since it's possible that they are no 1025 // longer correct. 1026 // Note that we have to clear the kill flags for any register this instruction 1027 // uses as we may sink over another instruction which currently kills the 1028 // used registers. 1029 for (MachineOperand &MO : MI.operands()) { 1030 if (MO.isReg() && MO.isUse()) 1031 RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags. 1032 } 1033 1034 return true; 1035 } 1036 1037 void MachineSinking::SalvageUnsunkDebugUsersOfCopy( 1038 MachineInstr &MI, MachineBasicBlock *TargetBlock) { 1039 assert(MI.isCopy()); 1040 assert(MI.getOperand(1).isReg()); 1041 1042 // Enumerate all users of vreg operands that are def'd. Skip those that will 1043 // be sunk. For the rest, if they are not dominated by the block we will sink 1044 // MI into, propagate the copy source to them. 1045 SmallVector<MachineInstr *, 4> DbgDefUsers; 1046 const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo(); 1047 for (auto &MO : MI.operands()) { 1048 if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual()) 1049 continue; 1050 for (auto &User : MRI.use_instructions(MO.getReg())) { 1051 if (!User.isDebugValue() || DT->dominates(TargetBlock, User.getParent())) 1052 continue; 1053 1054 // If is in same block, will either sink or be use-before-def. 1055 if (User.getParent() == MI.getParent()) 1056 continue; 1057 1058 assert(User.getDebugOperand(0).isReg() && 1059 "DBG_VALUE user of vreg, but non reg operand?"); 1060 DbgDefUsers.push_back(&User); 1061 } 1062 } 1063 1064 // Point the users of this copy that are no longer dominated, at the source 1065 // of the copy. 1066 for (auto *User : DbgDefUsers) { 1067 User->getDebugOperand(0).setReg(MI.getOperand(1).getReg()); 1068 User->getDebugOperand(0).setSubReg(MI.getOperand(1).getSubReg()); 1069 } 1070 } 1071 1072 //===----------------------------------------------------------------------===// 1073 // This pass is not intended to be a replacement or a complete alternative 1074 // for the pre-ra machine sink pass. It is only designed to sink COPY 1075 // instructions which should be handled after RA. 1076 // 1077 // This pass sinks COPY instructions into a successor block, if the COPY is not 1078 // used in the current block and the COPY is live-in to a single successor 1079 // (i.e., doesn't require the COPY to be duplicated). This avoids executing the 1080 // copy on paths where their results aren't needed. This also exposes 1081 // additional opportunites for dead copy elimination and shrink wrapping. 1082 // 1083 // These copies were either not handled by or are inserted after the MachineSink 1084 // pass. As an example of the former case, the MachineSink pass cannot sink 1085 // COPY instructions with allocatable source registers; for AArch64 these type 1086 // of copy instructions are frequently used to move function parameters (PhyReg) 1087 // into virtual registers in the entry block. 1088 // 1089 // For the machine IR below, this pass will sink %w19 in the entry into its 1090 // successor (%bb.1) because %w19 is only live-in in %bb.1. 1091 // %bb.0: 1092 // %wzr = SUBSWri %w1, 1 1093 // %w19 = COPY %w0 1094 // Bcc 11, %bb.2 1095 // %bb.1: 1096 // Live Ins: %w19 1097 // BL @fun 1098 // %w0 = ADDWrr %w0, %w19 1099 // RET %w0 1100 // %bb.2: 1101 // %w0 = COPY %wzr 1102 // RET %w0 1103 // As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be 1104 // able to see %bb.0 as a candidate. 1105 //===----------------------------------------------------------------------===// 1106 namespace { 1107 1108 class PostRAMachineSinking : public MachineFunctionPass { 1109 public: 1110 bool runOnMachineFunction(MachineFunction &MF) override; 1111 1112 static char ID; 1113 PostRAMachineSinking() : MachineFunctionPass(ID) {} 1114 StringRef getPassName() const override { return "PostRA Machine Sink"; } 1115 1116 void getAnalysisUsage(AnalysisUsage &AU) const override { 1117 AU.setPreservesCFG(); 1118 MachineFunctionPass::getAnalysisUsage(AU); 1119 } 1120 1121 MachineFunctionProperties getRequiredProperties() const override { 1122 return MachineFunctionProperties().set( 1123 MachineFunctionProperties::Property::NoVRegs); 1124 } 1125 1126 private: 1127 /// Track which register units have been modified and used. 1128 LiveRegUnits ModifiedRegUnits, UsedRegUnits; 1129 1130 /// Track DBG_VALUEs of (unmodified) register units. Each DBG_VALUE has an 1131 /// entry in this map for each unit it touches. 1132 DenseMap<unsigned, TinyPtrVector<MachineInstr *>> SeenDbgInstrs; 1133 1134 /// Sink Copy instructions unused in the same block close to their uses in 1135 /// successors. 1136 bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF, 1137 const TargetRegisterInfo *TRI, const TargetInstrInfo *TII); 1138 }; 1139 } // namespace 1140 1141 char PostRAMachineSinking::ID = 0; 1142 char &llvm::PostRAMachineSinkingID = PostRAMachineSinking::ID; 1143 1144 INITIALIZE_PASS(PostRAMachineSinking, "postra-machine-sink", 1145 "PostRA Machine Sink", false, false) 1146 1147 static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, unsigned Reg, 1148 const TargetRegisterInfo *TRI) { 1149 LiveRegUnits LiveInRegUnits(*TRI); 1150 LiveInRegUnits.addLiveIns(MBB); 1151 return !LiveInRegUnits.available(Reg); 1152 } 1153 1154 static MachineBasicBlock * 1155 getSingleLiveInSuccBB(MachineBasicBlock &CurBB, 1156 const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs, 1157 unsigned Reg, const TargetRegisterInfo *TRI) { 1158 // Try to find a single sinkable successor in which Reg is live-in. 1159 MachineBasicBlock *BB = nullptr; 1160 for (auto *SI : SinkableBBs) { 1161 if (aliasWithRegsInLiveIn(*SI, Reg, TRI)) { 1162 // If BB is set here, Reg is live-in to at least two sinkable successors, 1163 // so quit. 1164 if (BB) 1165 return nullptr; 1166 BB = SI; 1167 } 1168 } 1169 // Reg is not live-in to any sinkable successors. 1170 if (!BB) 1171 return nullptr; 1172 1173 // Check if any register aliased with Reg is live-in in other successors. 1174 for (auto *SI : CurBB.successors()) { 1175 if (!SinkableBBs.count(SI) && aliasWithRegsInLiveIn(*SI, Reg, TRI)) 1176 return nullptr; 1177 } 1178 return BB; 1179 } 1180 1181 static MachineBasicBlock * 1182 getSingleLiveInSuccBB(MachineBasicBlock &CurBB, 1183 const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs, 1184 ArrayRef<unsigned> DefedRegsInCopy, 1185 const TargetRegisterInfo *TRI) { 1186 MachineBasicBlock *SingleBB = nullptr; 1187 for (auto DefReg : DefedRegsInCopy) { 1188 MachineBasicBlock *BB = 1189 getSingleLiveInSuccBB(CurBB, SinkableBBs, DefReg, TRI); 1190 if (!BB || (SingleBB && SingleBB != BB)) 1191 return nullptr; 1192 SingleBB = BB; 1193 } 1194 return SingleBB; 1195 } 1196 1197 static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB, 1198 SmallVectorImpl<unsigned> &UsedOpsInCopy, 1199 LiveRegUnits &UsedRegUnits, 1200 const TargetRegisterInfo *TRI) { 1201 for (auto U : UsedOpsInCopy) { 1202 MachineOperand &MO = MI->getOperand(U); 1203 Register SrcReg = MO.getReg(); 1204 if (!UsedRegUnits.available(SrcReg)) { 1205 MachineBasicBlock::iterator NI = std::next(MI->getIterator()); 1206 for (MachineInstr &UI : make_range(NI, CurBB.end())) { 1207 if (UI.killsRegister(SrcReg, TRI)) { 1208 UI.clearRegisterKills(SrcReg, TRI); 1209 MO.setIsKill(true); 1210 break; 1211 } 1212 } 1213 } 1214 } 1215 } 1216 1217 static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB, 1218 SmallVectorImpl<unsigned> &UsedOpsInCopy, 1219 SmallVectorImpl<unsigned> &DefedRegsInCopy) { 1220 MachineFunction &MF = *SuccBB->getParent(); 1221 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); 1222 for (unsigned DefReg : DefedRegsInCopy) 1223 for (MCSubRegIterator S(DefReg, TRI, true); S.isValid(); ++S) 1224 SuccBB->removeLiveIn(*S); 1225 for (auto U : UsedOpsInCopy) { 1226 Register SrcReg = MI->getOperand(U).getReg(); 1227 LaneBitmask Mask; 1228 for (MCRegUnitMaskIterator S(SrcReg, TRI); S.isValid(); ++S) { 1229 Mask |= (*S).second; 1230 } 1231 SuccBB->addLiveIn(SrcReg, Mask.any() ? Mask : LaneBitmask::getAll()); 1232 } 1233 SuccBB->sortUniqueLiveIns(); 1234 } 1235 1236 static bool hasRegisterDependency(MachineInstr *MI, 1237 SmallVectorImpl<unsigned> &UsedOpsInCopy, 1238 SmallVectorImpl<unsigned> &DefedRegsInCopy, 1239 LiveRegUnits &ModifiedRegUnits, 1240 LiveRegUnits &UsedRegUnits) { 1241 bool HasRegDependency = false; 1242 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1243 MachineOperand &MO = MI->getOperand(i); 1244 if (!MO.isReg()) 1245 continue; 1246 Register Reg = MO.getReg(); 1247 if (!Reg) 1248 continue; 1249 if (MO.isDef()) { 1250 if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) { 1251 HasRegDependency = true; 1252 break; 1253 } 1254 DefedRegsInCopy.push_back(Reg); 1255 1256 // FIXME: instead of isUse(), readsReg() would be a better fix here, 1257 // For example, we can ignore modifications in reg with undef. However, 1258 // it's not perfectly clear if skipping the internal read is safe in all 1259 // other targets. 1260 } else if (MO.isUse()) { 1261 if (!ModifiedRegUnits.available(Reg)) { 1262 HasRegDependency = true; 1263 break; 1264 } 1265 UsedOpsInCopy.push_back(i); 1266 } 1267 } 1268 return HasRegDependency; 1269 } 1270 1271 static SmallSet<unsigned, 4> getRegUnits(unsigned Reg, 1272 const TargetRegisterInfo *TRI) { 1273 SmallSet<unsigned, 4> RegUnits; 1274 for (auto RI = MCRegUnitIterator(Reg, TRI); RI.isValid(); ++RI) 1275 RegUnits.insert(*RI); 1276 return RegUnits; 1277 } 1278 1279 bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB, 1280 MachineFunction &MF, 1281 const TargetRegisterInfo *TRI, 1282 const TargetInstrInfo *TII) { 1283 SmallPtrSet<MachineBasicBlock *, 2> SinkableBBs; 1284 // FIXME: For now, we sink only to a successor which has a single predecessor 1285 // so that we can directly sink COPY instructions to the successor without 1286 // adding any new block or branch instruction. 1287 for (MachineBasicBlock *SI : CurBB.successors()) 1288 if (!SI->livein_empty() && SI->pred_size() == 1) 1289 SinkableBBs.insert(SI); 1290 1291 if (SinkableBBs.empty()) 1292 return false; 1293 1294 bool Changed = false; 1295 1296 // Track which registers have been modified and used between the end of the 1297 // block and the current instruction. 1298 ModifiedRegUnits.clear(); 1299 UsedRegUnits.clear(); 1300 SeenDbgInstrs.clear(); 1301 1302 for (auto I = CurBB.rbegin(), E = CurBB.rend(); I != E;) { 1303 MachineInstr *MI = &*I; 1304 ++I; 1305 1306 // Track the operand index for use in Copy. 1307 SmallVector<unsigned, 2> UsedOpsInCopy; 1308 // Track the register number defed in Copy. 1309 SmallVector<unsigned, 2> DefedRegsInCopy; 1310 1311 // We must sink this DBG_VALUE if its operand is sunk. To avoid searching 1312 // for DBG_VALUEs later, record them when they're encountered. 1313 if (MI->isDebugValue()) { 1314 auto &MO = MI->getDebugOperand(0); 1315 if (MO.isReg() && Register::isPhysicalRegister(MO.getReg())) { 1316 // Bail if we can already tell the sink would be rejected, rather 1317 // than needlessly accumulating lots of DBG_VALUEs. 1318 if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy, 1319 ModifiedRegUnits, UsedRegUnits)) 1320 continue; 1321 1322 // Record debug use of each reg unit. 1323 SmallSet<unsigned, 4> Units = getRegUnits(MO.getReg(), TRI); 1324 for (unsigned Reg : Units) 1325 SeenDbgInstrs[Reg].push_back(MI); 1326 } 1327 continue; 1328 } 1329 1330 if (MI->isDebugInstr()) 1331 continue; 1332 1333 // Do not move any instruction across function call. 1334 if (MI->isCall()) 1335 return false; 1336 1337 if (!MI->isCopy() || !MI->getOperand(0).isRenamable()) { 1338 LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits, 1339 TRI); 1340 continue; 1341 } 1342 1343 // Don't sink the COPY if it would violate a register dependency. 1344 if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy, 1345 ModifiedRegUnits, UsedRegUnits)) { 1346 LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits, 1347 TRI); 1348 continue; 1349 } 1350 assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) && 1351 "Unexpect SrcReg or DefReg"); 1352 MachineBasicBlock *SuccBB = 1353 getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI); 1354 // Don't sink if we cannot find a single sinkable successor in which Reg 1355 // is live-in. 1356 if (!SuccBB) { 1357 LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits, 1358 TRI); 1359 continue; 1360 } 1361 assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) && 1362 "Unexpected predecessor"); 1363 1364 // Collect DBG_VALUEs that must sink with this copy. We've previously 1365 // recorded which reg units that DBG_VALUEs read, if this instruction 1366 // writes any of those units then the corresponding DBG_VALUEs must sink. 1367 SetVector<MachineInstr *> DbgValsToSinkSet; 1368 SmallVector<MachineInstr *, 4> DbgValsToSink; 1369 for (auto &MO : MI->operands()) { 1370 if (!MO.isReg() || !MO.isDef()) 1371 continue; 1372 1373 SmallSet<unsigned, 4> Units = getRegUnits(MO.getReg(), TRI); 1374 for (unsigned Reg : Units) 1375 for (auto *MI : SeenDbgInstrs.lookup(Reg)) 1376 DbgValsToSinkSet.insert(MI); 1377 } 1378 DbgValsToSink.insert(DbgValsToSink.begin(), DbgValsToSinkSet.begin(), 1379 DbgValsToSinkSet.end()); 1380 1381 // Clear the kill flag if SrcReg is killed between MI and the end of the 1382 // block. 1383 clearKillFlags(MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI); 1384 MachineBasicBlock::iterator InsertPos = SuccBB->getFirstNonPHI(); 1385 performSink(*MI, *SuccBB, InsertPos, DbgValsToSink); 1386 updateLiveIn(MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy); 1387 1388 Changed = true; 1389 ++NumPostRACopySink; 1390 } 1391 return Changed; 1392 } 1393 1394 bool PostRAMachineSinking::runOnMachineFunction(MachineFunction &MF) { 1395 if (skipFunction(MF.getFunction())) 1396 return false; 1397 1398 bool Changed = false; 1399 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); 1400 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo(); 1401 1402 ModifiedRegUnits.init(*TRI); 1403 UsedRegUnits.init(*TRI); 1404 for (auto &BB : MF) 1405 Changed |= tryToSinkCopy(BB, MF, TRI, TII); 1406 1407 return Changed; 1408 } 1409