1 //===- TailDuplicator.cpp - Duplicate blocks into predecessors' tails -----===// 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 utility class duplicates basic blocks ending in unconditional branches 10 // into the tails of their predecessors. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/TailDuplicator.h" 15 #include "llvm/ADT/DenseMap.h" 16 #include "llvm/ADT/DenseSet.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/ADT/SetVector.h" 19 #include "llvm/ADT/SmallPtrSet.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/ADT/Statistic.h" 22 #include "llvm/Analysis/ProfileSummaryInfo.h" 23 #include "llvm/CodeGen/MachineBasicBlock.h" 24 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 25 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 26 #include "llvm/CodeGen/MachineFunction.h" 27 #include "llvm/CodeGen/MachineInstr.h" 28 #include "llvm/CodeGen/MachineInstrBuilder.h" 29 #include "llvm/CodeGen/MachineOperand.h" 30 #include "llvm/CodeGen/MachineRegisterInfo.h" 31 #include "llvm/CodeGen/MachineSizeOpts.h" 32 #include "llvm/CodeGen/MachineSSAUpdater.h" 33 #include "llvm/CodeGen/TargetInstrInfo.h" 34 #include "llvm/CodeGen/TargetRegisterInfo.h" 35 #include "llvm/CodeGen/TargetSubtargetInfo.h" 36 #include "llvm/IR/DebugLoc.h" 37 #include "llvm/IR/Function.h" 38 #include "llvm/Support/CommandLine.h" 39 #include "llvm/Support/Debug.h" 40 #include "llvm/Support/ErrorHandling.h" 41 #include "llvm/Support/raw_ostream.h" 42 #include "llvm/Target/TargetMachine.h" 43 #include <algorithm> 44 #include <cassert> 45 #include <iterator> 46 #include <utility> 47 48 using namespace llvm; 49 50 #define DEBUG_TYPE "tailduplication" 51 52 STATISTIC(NumTails, "Number of tails duplicated"); 53 STATISTIC(NumTailDups, "Number of tail duplicated blocks"); 54 STATISTIC(NumTailDupAdded, 55 "Number of instructions added due to tail duplication"); 56 STATISTIC(NumTailDupRemoved, 57 "Number of instructions removed due to tail duplication"); 58 STATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 59 STATISTIC(NumAddedPHIs, "Number of phis added"); 60 61 // Heuristic for tail duplication. 62 static cl::opt<unsigned> TailDuplicateSize( 63 "tail-dup-size", 64 cl::desc("Maximum instructions to consider tail duplicating"), cl::init(2), 65 cl::Hidden); 66 67 static cl::opt<unsigned> TailDupIndirectBranchSize( 68 "tail-dup-indirect-size", 69 cl::desc("Maximum instructions to consider tail duplicating blocks that " 70 "end with indirect branches."), cl::init(20), 71 cl::Hidden); 72 73 static cl::opt<bool> 74 TailDupVerify("tail-dup-verify", 75 cl::desc("Verify sanity of PHI instructions during taildup"), 76 cl::init(false), cl::Hidden); 77 78 static cl::opt<unsigned> TailDupLimit("tail-dup-limit", cl::init(~0U), 79 cl::Hidden); 80 81 void TailDuplicator::initMF(MachineFunction &MFin, bool PreRegAlloc, 82 const MachineBranchProbabilityInfo *MBPIin, 83 MBFIWrapper *MBFIin, 84 ProfileSummaryInfo *PSIin, 85 bool LayoutModeIn, unsigned TailDupSizeIn) { 86 MF = &MFin; 87 TII = MF->getSubtarget().getInstrInfo(); 88 TRI = MF->getSubtarget().getRegisterInfo(); 89 MRI = &MF->getRegInfo(); 90 MMI = &MF->getMMI(); 91 MBPI = MBPIin; 92 MBFI = MBFIin; 93 PSI = PSIin; 94 TailDupSize = TailDupSizeIn; 95 96 assert(MBPI != nullptr && "Machine Branch Probability Info required"); 97 98 LayoutMode = LayoutModeIn; 99 this->PreRegAlloc = PreRegAlloc; 100 } 101 102 static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 103 for (MachineBasicBlock &MBB : llvm::drop_begin(MF)) { 104 SmallSetVector<MachineBasicBlock *, 8> Preds(MBB.pred_begin(), 105 MBB.pred_end()); 106 MachineBasicBlock::iterator MI = MBB.begin(); 107 while (MI != MBB.end()) { 108 if (!MI->isPHI()) 109 break; 110 for (MachineBasicBlock *PredBB : Preds) { 111 bool Found = false; 112 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 113 MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB(); 114 if (PHIBB == PredBB) { 115 Found = true; 116 break; 117 } 118 } 119 if (!Found) { 120 dbgs() << "Malformed PHI in " << printMBBReference(MBB) << ": " 121 << *MI; 122 dbgs() << " missing input from predecessor " 123 << printMBBReference(*PredBB) << '\n'; 124 llvm_unreachable(nullptr); 125 } 126 } 127 128 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 129 MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB(); 130 if (CheckExtra && !Preds.count(PHIBB)) { 131 dbgs() << "Warning: malformed PHI in " << printMBBReference(MBB) 132 << ": " << *MI; 133 dbgs() << " extra input from predecessor " 134 << printMBBReference(*PHIBB) << '\n'; 135 llvm_unreachable(nullptr); 136 } 137 if (PHIBB->getNumber() < 0) { 138 dbgs() << "Malformed PHI in " << printMBBReference(MBB) << ": " 139 << *MI; 140 dbgs() << " non-existing " << printMBBReference(*PHIBB) << '\n'; 141 llvm_unreachable(nullptr); 142 } 143 } 144 ++MI; 145 } 146 } 147 } 148 149 /// Tail duplicate the block and cleanup. 150 /// \p IsSimple - return value of isSimpleBB 151 /// \p MBB - block to be duplicated 152 /// \p ForcedLayoutPred - If non-null, treat this block as the layout 153 /// predecessor, instead of using the ordering in MF 154 /// \p DuplicatedPreds - if non-null, \p DuplicatedPreds will contain a list of 155 /// all Preds that received a copy of \p MBB. 156 /// \p RemovalCallback - if non-null, called just before MBB is deleted. 157 bool TailDuplicator::tailDuplicateAndUpdate( 158 bool IsSimple, MachineBasicBlock *MBB, 159 MachineBasicBlock *ForcedLayoutPred, 160 SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds, 161 function_ref<void(MachineBasicBlock *)> *RemovalCallback, 162 SmallVectorImpl<MachineBasicBlock *> *CandidatePtr) { 163 // Save the successors list. 164 SmallSetVector<MachineBasicBlock *, 8> Succs(MBB->succ_begin(), 165 MBB->succ_end()); 166 167 SmallVector<MachineBasicBlock *, 8> TDBBs; 168 SmallVector<MachineInstr *, 16> Copies; 169 if (!tailDuplicate(IsSimple, MBB, ForcedLayoutPred, 170 TDBBs, Copies, CandidatePtr)) 171 return false; 172 173 ++NumTails; 174 175 SmallVector<MachineInstr *, 8> NewPHIs; 176 MachineSSAUpdater SSAUpdate(*MF, &NewPHIs); 177 178 // TailBB's immediate successors are now successors of those predecessors 179 // which duplicated TailBB. Add the predecessors as sources to the PHI 180 // instructions. 181 bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); 182 if (PreRegAlloc) 183 updateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 184 185 // If it is dead, remove it. 186 if (isDead) { 187 NumTailDupRemoved += MBB->size(); 188 removeDeadBlock(MBB, RemovalCallback); 189 ++NumDeadBlocks; 190 } 191 192 // Update SSA form. 193 if (!SSAUpdateVRs.empty()) { 194 for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 195 unsigned VReg = SSAUpdateVRs[i]; 196 SSAUpdate.Initialize(VReg); 197 198 // If the original definition is still around, add it as an available 199 // value. 200 MachineInstr *DefMI = MRI->getVRegDef(VReg); 201 MachineBasicBlock *DefBB = nullptr; 202 if (DefMI) { 203 DefBB = DefMI->getParent(); 204 SSAUpdate.AddAvailableValue(DefBB, VReg); 205 } 206 207 // Add the new vregs as available values. 208 DenseMap<Register, AvailableValsTy>::iterator LI = 209 SSAUpdateVals.find(VReg); 210 for (std::pair<MachineBasicBlock *, Register> &J : LI->second) { 211 MachineBasicBlock *SrcBB = J.first; 212 Register SrcReg = J.second; 213 SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 214 } 215 216 SmallVector<MachineOperand *> DebugUses; 217 // Rewrite uses that are outside of the original def's block. 218 for (MachineOperand &UseMO : 219 llvm::make_early_inc_range(MRI->use_operands(VReg))) { 220 MachineInstr *UseMI = UseMO.getParent(); 221 // Rewrite debug uses last so that they can take advantage of any 222 // register mappings introduced by other users in its BB, since we 223 // cannot create new register definitions specifically for the debug 224 // instruction (as debug instructions should not affect CodeGen). 225 if (UseMI->isDebugValue()) { 226 DebugUses.push_back(&UseMO); 227 continue; 228 } 229 if (UseMI->getParent() == DefBB && !UseMI->isPHI()) 230 continue; 231 SSAUpdate.RewriteUse(UseMO); 232 } 233 for (auto *UseMO : DebugUses) { 234 MachineInstr *UseMI = UseMO->getParent(); 235 UseMO->setReg( 236 SSAUpdate.GetValueInMiddleOfBlock(UseMI->getParent(), true)); 237 } 238 } 239 240 SSAUpdateVRs.clear(); 241 SSAUpdateVals.clear(); 242 } 243 244 // Eliminate some of the copies inserted by tail duplication to maintain 245 // SSA form. 246 for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 247 MachineInstr *Copy = Copies[i]; 248 if (!Copy->isCopy()) 249 continue; 250 Register Dst = Copy->getOperand(0).getReg(); 251 Register Src = Copy->getOperand(1).getReg(); 252 if (MRI->hasOneNonDBGUse(Src) && 253 MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) { 254 // Copy is the only use. Do trivial copy propagation here. 255 MRI->replaceRegWith(Dst, Src); 256 Copy->eraseFromParent(); 257 } 258 } 259 260 if (NewPHIs.size()) 261 NumAddedPHIs += NewPHIs.size(); 262 263 if (DuplicatedPreds) 264 *DuplicatedPreds = std::move(TDBBs); 265 266 return true; 267 } 268 269 /// Look for small blocks that are unconditionally branched to and do not fall 270 /// through. Tail-duplicate their instructions into their predecessors to 271 /// eliminate (dynamic) branches. 272 bool TailDuplicator::tailDuplicateBlocks() { 273 bool MadeChange = false; 274 275 if (PreRegAlloc && TailDupVerify) { 276 LLVM_DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 277 VerifyPHIs(*MF, true); 278 } 279 280 for (MachineBasicBlock &MBB : 281 llvm::make_early_inc_range(llvm::drop_begin(*MF))) { 282 if (NumTails == TailDupLimit) 283 break; 284 285 bool IsSimple = isSimpleBB(&MBB); 286 287 if (!shouldTailDuplicate(IsSimple, MBB)) 288 continue; 289 290 MadeChange |= tailDuplicateAndUpdate(IsSimple, &MBB, nullptr); 291 } 292 293 if (PreRegAlloc && TailDupVerify) 294 VerifyPHIs(*MF, false); 295 296 return MadeChange; 297 } 298 299 static bool isDefLiveOut(Register Reg, MachineBasicBlock *BB, 300 const MachineRegisterInfo *MRI) { 301 for (MachineInstr &UseMI : MRI->use_instructions(Reg)) { 302 if (UseMI.isDebugValue()) 303 continue; 304 if (UseMI.getParent() != BB) 305 return true; 306 } 307 return false; 308 } 309 310 static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 311 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 312 if (MI->getOperand(i + 1).getMBB() == SrcBB) 313 return i; 314 return 0; 315 } 316 317 // Remember which registers are used by phis in this block. This is 318 // used to determine which registers are liveout while modifying the 319 // block (which is why we need to copy the information). 320 static void getRegsUsedByPHIs(const MachineBasicBlock &BB, 321 DenseSet<Register> *UsedByPhi) { 322 for (const auto &MI : BB) { 323 if (!MI.isPHI()) 324 break; 325 for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { 326 Register SrcReg = MI.getOperand(i).getReg(); 327 UsedByPhi->insert(SrcReg); 328 } 329 } 330 } 331 332 /// Add a definition and source virtual registers pair for SSA update. 333 void TailDuplicator::addSSAUpdateEntry(Register OrigReg, Register NewReg, 334 MachineBasicBlock *BB) { 335 DenseMap<Register, AvailableValsTy>::iterator LI = 336 SSAUpdateVals.find(OrigReg); 337 if (LI != SSAUpdateVals.end()) 338 LI->second.push_back(std::make_pair(BB, NewReg)); 339 else { 340 AvailableValsTy Vals; 341 Vals.push_back(std::make_pair(BB, NewReg)); 342 SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 343 SSAUpdateVRs.push_back(OrigReg); 344 } 345 } 346 347 /// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the 348 /// source register that's contributed by PredBB and update SSA update map. 349 void TailDuplicator::processPHI( 350 MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB, 351 DenseMap<Register, RegSubRegPair> &LocalVRMap, 352 SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies, 353 const DenseSet<Register> &RegsUsedByPhi, bool Remove) { 354 Register DefReg = MI->getOperand(0).getReg(); 355 unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 356 assert(SrcOpIdx && "Unable to find matching PHI source?"); 357 Register SrcReg = MI->getOperand(SrcOpIdx).getReg(); 358 unsigned SrcSubReg = MI->getOperand(SrcOpIdx).getSubReg(); 359 const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 360 LocalVRMap.insert(std::make_pair(DefReg, RegSubRegPair(SrcReg, SrcSubReg))); 361 362 // Insert a copy from source to the end of the block. The def register is the 363 // available value liveout of the block. 364 Register NewDef = MRI->createVirtualRegister(RC); 365 Copies.push_back(std::make_pair(NewDef, RegSubRegPair(SrcReg, SrcSubReg))); 366 if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg)) 367 addSSAUpdateEntry(DefReg, NewDef, PredBB); 368 369 if (!Remove) 370 return; 371 372 // Remove PredBB from the PHI node. 373 MI->RemoveOperand(SrcOpIdx + 1); 374 MI->RemoveOperand(SrcOpIdx); 375 if (MI->getNumOperands() == 1) 376 MI->eraseFromParent(); 377 } 378 379 /// Duplicate a TailBB instruction to PredBB and update 380 /// the source operands due to earlier PHI translation. 381 void TailDuplicator::duplicateInstruction( 382 MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB, 383 DenseMap<Register, RegSubRegPair> &LocalVRMap, 384 const DenseSet<Register> &UsedByPhi) { 385 // Allow duplication of CFI instructions. 386 if (MI->isCFIInstruction()) { 387 BuildMI(*PredBB, PredBB->end(), PredBB->findDebugLoc(PredBB->begin()), 388 TII->get(TargetOpcode::CFI_INSTRUCTION)).addCFIIndex( 389 MI->getOperand(0).getCFIIndex()); 390 return; 391 } 392 MachineInstr &NewMI = TII->duplicate(*PredBB, PredBB->end(), *MI); 393 if (PreRegAlloc) { 394 for (unsigned i = 0, e = NewMI.getNumOperands(); i != e; ++i) { 395 MachineOperand &MO = NewMI.getOperand(i); 396 if (!MO.isReg()) 397 continue; 398 Register Reg = MO.getReg(); 399 if (!Register::isVirtualRegister(Reg)) 400 continue; 401 if (MO.isDef()) { 402 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 403 Register NewReg = MRI->createVirtualRegister(RC); 404 MO.setReg(NewReg); 405 LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0))); 406 if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg)) 407 addSSAUpdateEntry(Reg, NewReg, PredBB); 408 } else { 409 auto VI = LocalVRMap.find(Reg); 410 if (VI != LocalVRMap.end()) { 411 // Need to make sure that the register class of the mapped register 412 // will satisfy the constraints of the class of the register being 413 // replaced. 414 auto *OrigRC = MRI->getRegClass(Reg); 415 auto *MappedRC = MRI->getRegClass(VI->second.Reg); 416 const TargetRegisterClass *ConstrRC; 417 if (VI->second.SubReg != 0) { 418 ConstrRC = TRI->getMatchingSuperRegClass(MappedRC, OrigRC, 419 VI->second.SubReg); 420 if (ConstrRC) { 421 // The actual constraining (as in "find appropriate new class") 422 // is done by getMatchingSuperRegClass, so now we only need to 423 // change the class of the mapped register. 424 MRI->setRegClass(VI->second.Reg, ConstrRC); 425 } 426 } else { 427 // For mapped registers that do not have sub-registers, simply 428 // restrict their class to match the original one. 429 ConstrRC = MRI->constrainRegClass(VI->second.Reg, OrigRC); 430 } 431 432 if (ConstrRC) { 433 // If the class constraining succeeded, we can simply replace 434 // the old register with the mapped one. 435 MO.setReg(VI->second.Reg); 436 // We have Reg -> VI.Reg:VI.SubReg, so if Reg is used with a 437 // sub-register, we need to compose the sub-register indices. 438 MO.setSubReg(TRI->composeSubRegIndices(MO.getSubReg(), 439 VI->second.SubReg)); 440 } else { 441 // The direct replacement is not possible, due to failing register 442 // class constraints. An explicit COPY is necessary. Create one 443 // that can be reused 444 auto *NewRC = MI->getRegClassConstraint(i, TII, TRI); 445 if (NewRC == nullptr) 446 NewRC = OrigRC; 447 Register NewReg = MRI->createVirtualRegister(NewRC); 448 BuildMI(*PredBB, NewMI, NewMI.getDebugLoc(), 449 TII->get(TargetOpcode::COPY), NewReg) 450 .addReg(VI->second.Reg, 0, VI->second.SubReg); 451 LocalVRMap.erase(VI); 452 LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0))); 453 MO.setReg(NewReg); 454 // The composed VI.Reg:VI.SubReg is replaced with NewReg, which 455 // is equivalent to the whole register Reg. Hence, Reg:subreg 456 // is same as NewReg:subreg, so keep the sub-register index 457 // unchanged. 458 } 459 // Clear any kill flags from this operand. The new register could 460 // have uses after this one, so kills are not valid here. 461 MO.setIsKill(false); 462 } 463 } 464 } 465 } 466 } 467 468 /// After FromBB is tail duplicated into its predecessor blocks, the successors 469 /// have gained new predecessors. Update the PHI instructions in them 470 /// accordingly. 471 void TailDuplicator::updateSuccessorsPHIs( 472 MachineBasicBlock *FromBB, bool isDead, 473 SmallVectorImpl<MachineBasicBlock *> &TDBBs, 474 SmallSetVector<MachineBasicBlock *, 8> &Succs) { 475 for (MachineBasicBlock *SuccBB : Succs) { 476 for (MachineInstr &MI : *SuccBB) { 477 if (!MI.isPHI()) 478 break; 479 MachineInstrBuilder MIB(*FromBB->getParent(), MI); 480 unsigned Idx = 0; 481 for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { 482 MachineOperand &MO = MI.getOperand(i + 1); 483 if (MO.getMBB() == FromBB) { 484 Idx = i; 485 break; 486 } 487 } 488 489 assert(Idx != 0); 490 MachineOperand &MO0 = MI.getOperand(Idx); 491 Register Reg = MO0.getReg(); 492 if (isDead) { 493 // Folded into the previous BB. 494 // There could be duplicate phi source entries. FIXME: Should sdisel 495 // or earlier pass fixed this? 496 for (unsigned i = MI.getNumOperands() - 2; i != Idx; i -= 2) { 497 MachineOperand &MO = MI.getOperand(i + 1); 498 if (MO.getMBB() == FromBB) { 499 MI.RemoveOperand(i + 1); 500 MI.RemoveOperand(i); 501 } 502 } 503 } else 504 Idx = 0; 505 506 // If Idx is set, the operands at Idx and Idx+1 must be removed. 507 // We reuse the location to avoid expensive RemoveOperand calls. 508 509 DenseMap<Register, AvailableValsTy>::iterator LI = 510 SSAUpdateVals.find(Reg); 511 if (LI != SSAUpdateVals.end()) { 512 // This register is defined in the tail block. 513 for (const std::pair<MachineBasicBlock *, Register> &J : LI->second) { 514 MachineBasicBlock *SrcBB = J.first; 515 // If we didn't duplicate a bb into a particular predecessor, we 516 // might still have added an entry to SSAUpdateVals to correcly 517 // recompute SSA. If that case, avoid adding a dummy extra argument 518 // this PHI. 519 if (!SrcBB->isSuccessor(SuccBB)) 520 continue; 521 522 Register SrcReg = J.second; 523 if (Idx != 0) { 524 MI.getOperand(Idx).setReg(SrcReg); 525 MI.getOperand(Idx + 1).setMBB(SrcBB); 526 Idx = 0; 527 } else { 528 MIB.addReg(SrcReg).addMBB(SrcBB); 529 } 530 } 531 } else { 532 // Live in tail block, must also be live in predecessors. 533 for (MachineBasicBlock *SrcBB : TDBBs) { 534 if (Idx != 0) { 535 MI.getOperand(Idx).setReg(Reg); 536 MI.getOperand(Idx + 1).setMBB(SrcBB); 537 Idx = 0; 538 } else { 539 MIB.addReg(Reg).addMBB(SrcBB); 540 } 541 } 542 } 543 if (Idx != 0) { 544 MI.RemoveOperand(Idx + 1); 545 MI.RemoveOperand(Idx); 546 } 547 } 548 } 549 } 550 551 /// Determine if it is profitable to duplicate this block. 552 bool TailDuplicator::shouldTailDuplicate(bool IsSimple, 553 MachineBasicBlock &TailBB) { 554 // When doing tail-duplication during layout, the block ordering is in flux, 555 // so canFallThrough returns a result based on incorrect information and 556 // should just be ignored. 557 if (!LayoutMode && TailBB.canFallThrough()) 558 return false; 559 560 // Don't try to tail-duplicate single-block loops. 561 if (TailBB.isSuccessor(&TailBB)) 562 return false; 563 564 // Set the limit on the cost to duplicate. When optimizing for size, 565 // duplicate only one, because one branch instruction can be eliminated to 566 // compensate for the duplication. 567 unsigned MaxDuplicateCount; 568 bool OptForSize = MF->getFunction().hasOptSize() || 569 llvm::shouldOptimizeForSize(&TailBB, PSI, MBFI); 570 if (TailDupSize == 0) 571 MaxDuplicateCount = TailDuplicateSize; 572 else 573 MaxDuplicateCount = TailDupSize; 574 if (OptForSize) 575 MaxDuplicateCount = 1; 576 577 // If the block to be duplicated ends in an unanalyzable fallthrough, don't 578 // duplicate it. 579 // A similar check is necessary in MachineBlockPlacement to make sure pairs of 580 // blocks with unanalyzable fallthrough get layed out contiguously. 581 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 582 SmallVector<MachineOperand, 4> PredCond; 583 if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond) && 584 TailBB.canFallThrough()) 585 return false; 586 587 // If the target has hardware branch prediction that can handle indirect 588 // branches, duplicating them can often make them predictable when there 589 // are common paths through the code. The limit needs to be high enough 590 // to allow undoing the effects of tail merging and other optimizations 591 // that rearrange the predecessors of the indirect branch. 592 593 bool HasIndirectbr = false; 594 if (!TailBB.empty()) 595 HasIndirectbr = TailBB.back().isIndirectBranch(); 596 597 if (HasIndirectbr && PreRegAlloc) 598 MaxDuplicateCount = TailDupIndirectBranchSize; 599 600 // Check the instructions in the block to determine whether tail-duplication 601 // is invalid or unlikely to be profitable. 602 unsigned InstrCount = 0; 603 for (MachineInstr &MI : TailBB) { 604 // Non-duplicable things shouldn't be tail-duplicated. 605 // CFI instructions are marked as non-duplicable, because Darwin compact 606 // unwind info emission can't handle multiple prologue setups. In case of 607 // DWARF, allow them be duplicated, so that their existence doesn't prevent 608 // tail duplication of some basic blocks, that would be duplicated otherwise. 609 if (MI.isNotDuplicable() && 610 (TailBB.getParent()->getTarget().getTargetTriple().isOSDarwin() || 611 !MI.isCFIInstruction())) 612 return false; 613 614 // Convergent instructions can be duplicated only if doing so doesn't add 615 // new control dependencies, which is what we're going to do here. 616 if (MI.isConvergent()) 617 return false; 618 619 // Do not duplicate 'return' instructions if this is a pre-regalloc run. 620 // A return may expand into a lot more instructions (e.g. reload of callee 621 // saved registers) after PEI. 622 if (PreRegAlloc && MI.isReturn()) 623 return false; 624 625 // Avoid duplicating calls before register allocation. Calls presents a 626 // barrier to register allocation so duplicating them may end up increasing 627 // spills. 628 if (PreRegAlloc && MI.isCall()) 629 return false; 630 631 // TailDuplicator::appendCopies will erroneously place COPYs after 632 // INLINEASM_BR instructions after 4b0aa5724fea, which demonstrates the same 633 // bug that was fixed in f7a53d82c090. 634 // FIXME: Use findPHICopyInsertPoint() to find the correct insertion point 635 // for the COPY when replacing PHIs. 636 if (MI.getOpcode() == TargetOpcode::INLINEASM_BR) 637 return false; 638 639 if (MI.isBundle()) 640 InstrCount += MI.getBundleSize(); 641 else if (!MI.isPHI() && !MI.isMetaInstruction()) 642 InstrCount += 1; 643 644 if (InstrCount > MaxDuplicateCount) 645 return false; 646 } 647 648 // Check if any of the successors of TailBB has a PHI node in which the 649 // value corresponding to TailBB uses a subregister. 650 // If a phi node uses a register paired with a subregister, the actual 651 // "value type" of the phi may differ from the type of the register without 652 // any subregisters. Due to a bug, tail duplication may add a new operand 653 // without a necessary subregister, producing an invalid code. This is 654 // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll. 655 // Disable tail duplication for this case for now, until the problem is 656 // fixed. 657 for (auto SB : TailBB.successors()) { 658 for (auto &I : *SB) { 659 if (!I.isPHI()) 660 break; 661 unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB); 662 assert(Idx != 0); 663 MachineOperand &PU = I.getOperand(Idx); 664 if (PU.getSubReg() != 0) 665 return false; 666 } 667 } 668 669 if (HasIndirectbr && PreRegAlloc) 670 return true; 671 672 if (IsSimple) 673 return true; 674 675 if (!PreRegAlloc) 676 return true; 677 678 return canCompletelyDuplicateBB(TailBB); 679 } 680 681 /// True if this BB has only one unconditional jump. 682 bool TailDuplicator::isSimpleBB(MachineBasicBlock *TailBB) { 683 if (TailBB->succ_size() != 1) 684 return false; 685 if (TailBB->pred_empty()) 686 return false; 687 MachineBasicBlock::iterator I = TailBB->getFirstNonDebugInstr(true); 688 if (I == TailBB->end()) 689 return true; 690 return I->isUnconditionalBranch(); 691 } 692 693 static bool bothUsedInPHI(const MachineBasicBlock &A, 694 const SmallPtrSet<MachineBasicBlock *, 8> &SuccsB) { 695 for (MachineBasicBlock *BB : A.successors()) 696 if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI()) 697 return true; 698 699 return false; 700 } 701 702 bool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) { 703 for (MachineBasicBlock *PredBB : BB.predecessors()) { 704 if (PredBB->succ_size() > 1) 705 return false; 706 707 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 708 SmallVector<MachineOperand, 4> PredCond; 709 if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond)) 710 return false; 711 712 if (!PredCond.empty()) 713 return false; 714 } 715 return true; 716 } 717 718 bool TailDuplicator::duplicateSimpleBB( 719 MachineBasicBlock *TailBB, SmallVectorImpl<MachineBasicBlock *> &TDBBs, 720 const DenseSet<Register> &UsedByPhi, 721 SmallVectorImpl<MachineInstr *> &Copies) { 722 SmallPtrSet<MachineBasicBlock *, 8> Succs(TailBB->succ_begin(), 723 TailBB->succ_end()); 724 SmallVector<MachineBasicBlock *, 8> Preds(TailBB->predecessors()); 725 bool Changed = false; 726 for (MachineBasicBlock *PredBB : Preds) { 727 if (PredBB->hasEHPadSuccessor() || PredBB->mayHaveInlineAsmBr()) 728 continue; 729 730 if (bothUsedInPHI(*PredBB, Succs)) 731 continue; 732 733 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 734 SmallVector<MachineOperand, 4> PredCond; 735 if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond)) 736 continue; 737 738 Changed = true; 739 LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 740 << "From simple Succ: " << *TailBB); 741 742 MachineBasicBlock *NewTarget = *TailBB->succ_begin(); 743 MachineBasicBlock *NextBB = PredBB->getNextNode(); 744 745 // Make PredFBB explicit. 746 if (PredCond.empty()) 747 PredFBB = PredTBB; 748 749 // Make fall through explicit. 750 if (!PredTBB) 751 PredTBB = NextBB; 752 if (!PredFBB) 753 PredFBB = NextBB; 754 755 // Redirect 756 if (PredFBB == TailBB) 757 PredFBB = NewTarget; 758 if (PredTBB == TailBB) 759 PredTBB = NewTarget; 760 761 // Make the branch unconditional if possible 762 if (PredTBB == PredFBB) { 763 PredCond.clear(); 764 PredFBB = nullptr; 765 } 766 767 // Avoid adding fall through branches. 768 if (PredFBB == NextBB) 769 PredFBB = nullptr; 770 if (PredTBB == NextBB && PredFBB == nullptr) 771 PredTBB = nullptr; 772 773 auto DL = PredBB->findBranchDebugLoc(); 774 TII->removeBranch(*PredBB); 775 776 if (!PredBB->isSuccessor(NewTarget)) 777 PredBB->replaceSuccessor(TailBB, NewTarget); 778 else { 779 PredBB->removeSuccessor(TailBB, true); 780 assert(PredBB->succ_size() <= 1); 781 } 782 783 if (PredTBB) 784 TII->insertBranch(*PredBB, PredTBB, PredFBB, PredCond, DL); 785 786 TDBBs.push_back(PredBB); 787 } 788 return Changed; 789 } 790 791 bool TailDuplicator::canTailDuplicate(MachineBasicBlock *TailBB, 792 MachineBasicBlock *PredBB) { 793 // EH edges are ignored by analyzeBranch. 794 if (PredBB->succ_size() > 1) 795 return false; 796 797 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 798 SmallVector<MachineOperand, 4> PredCond; 799 if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond)) 800 return false; 801 if (!PredCond.empty()) 802 return false; 803 return true; 804 } 805 806 /// If it is profitable, duplicate TailBB's contents in each 807 /// of its predecessors. 808 /// \p IsSimple result of isSimpleBB 809 /// \p TailBB Block to be duplicated. 810 /// \p ForcedLayoutPred When non-null, use this block as the layout predecessor 811 /// instead of the previous block in MF's order. 812 /// \p TDBBs A vector to keep track of all blocks tail-duplicated 813 /// into. 814 /// \p Copies A vector of copy instructions inserted. Used later to 815 /// walk all the inserted copies and remove redundant ones. 816 bool TailDuplicator::tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB, 817 MachineBasicBlock *ForcedLayoutPred, 818 SmallVectorImpl<MachineBasicBlock *> &TDBBs, 819 SmallVectorImpl<MachineInstr *> &Copies, 820 SmallVectorImpl<MachineBasicBlock *> *CandidatePtr) { 821 LLVM_DEBUG(dbgs() << "\n*** Tail-duplicating " << printMBBReference(*TailBB) 822 << '\n'); 823 824 bool ShouldUpdateTerminators = TailBB->canFallThrough(); 825 826 DenseSet<Register> UsedByPhi; 827 getRegsUsedByPHIs(*TailBB, &UsedByPhi); 828 829 if (IsSimple) 830 return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies); 831 832 // Iterate through all the unique predecessors and tail-duplicate this 833 // block into them, if possible. Copying the list ahead of time also 834 // avoids trouble with the predecessor list reallocating. 835 bool Changed = false; 836 SmallSetVector<MachineBasicBlock *, 8> Preds; 837 if (CandidatePtr) 838 Preds.insert(CandidatePtr->begin(), CandidatePtr->end()); 839 else 840 Preds.insert(TailBB->pred_begin(), TailBB->pred_end()); 841 842 for (MachineBasicBlock *PredBB : Preds) { 843 assert(TailBB != PredBB && 844 "Single-block loop should have been rejected earlier!"); 845 846 if (!canTailDuplicate(TailBB, PredBB)) 847 continue; 848 849 // Don't duplicate into a fall-through predecessor (at least for now). 850 // If profile is available, findDuplicateCandidates can choose better 851 // fall-through predecessor. 852 if (!(MF->getFunction().hasProfileData() && LayoutMode)) { 853 bool IsLayoutSuccessor = false; 854 if (ForcedLayoutPred) 855 IsLayoutSuccessor = (ForcedLayoutPred == PredBB); 856 else if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 857 IsLayoutSuccessor = true; 858 if (IsLayoutSuccessor) 859 continue; 860 } 861 862 LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 863 << "From Succ: " << *TailBB); 864 865 TDBBs.push_back(PredBB); 866 867 // Remove PredBB's unconditional branch. 868 TII->removeBranch(*PredBB); 869 870 // Clone the contents of TailBB into PredBB. 871 DenseMap<Register, RegSubRegPair> LocalVRMap; 872 SmallVector<std::pair<Register, RegSubRegPair>, 4> CopyInfos; 873 for (MachineInstr &MI : llvm::make_early_inc_range(*TailBB)) { 874 if (MI.isPHI()) { 875 // Replace the uses of the def of the PHI with the register coming 876 // from PredBB. 877 processPHI(&MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); 878 } else { 879 // Replace def of virtual registers with new registers, and update 880 // uses with PHI source register or the new registers. 881 duplicateInstruction(&MI, TailBB, PredBB, LocalVRMap, UsedByPhi); 882 } 883 } 884 appendCopies(PredBB, CopyInfos, Copies); 885 886 NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch 887 888 // Update the CFG. 889 PredBB->removeSuccessor(PredBB->succ_begin()); 890 assert(PredBB->succ_empty() && 891 "TailDuplicate called on block with multiple successors!"); 892 for (MachineBasicBlock *Succ : TailBB->successors()) 893 PredBB->addSuccessor(Succ, MBPI->getEdgeProbability(TailBB, Succ)); 894 895 // Update branches in pred to jump to tail's layout successor if needed. 896 if (ShouldUpdateTerminators) 897 PredBB->updateTerminator(TailBB->getNextNode()); 898 899 Changed = true; 900 ++NumTailDups; 901 } 902 903 // If TailBB was duplicated into all its predecessors except for the prior 904 // block, which falls through unconditionally, move the contents of this 905 // block into the prior block. 906 MachineBasicBlock *PrevBB = ForcedLayoutPred; 907 if (!PrevBB) 908 PrevBB = &*std::prev(TailBB->getIterator()); 909 MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr; 910 SmallVector<MachineOperand, 4> PriorCond; 911 // This has to check PrevBB->succ_size() because EH edges are ignored by 912 // analyzeBranch. 913 if (PrevBB->succ_size() == 1 && 914 // Layout preds are not always CFG preds. Check. 915 *PrevBB->succ_begin() == TailBB && 916 !TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond) && 917 PriorCond.empty() && 918 (!PriorTBB || PriorTBB == TailBB) && 919 TailBB->pred_size() == 1 && 920 !TailBB->hasAddressTaken()) { 921 LLVM_DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 922 << "From MBB: " << *TailBB); 923 // There may be a branch to the layout successor. This is unlikely but it 924 // happens. The correct thing to do is to remove the branch before 925 // duplicating the instructions in all cases. 926 bool RemovedBranches = TII->removeBranch(*PrevBB) != 0; 927 928 // If there are still tail instructions, abort the merge 929 if (PrevBB->getFirstTerminator() == PrevBB->end()) { 930 if (PreRegAlloc) { 931 DenseMap<Register, RegSubRegPair> LocalVRMap; 932 SmallVector<std::pair<Register, RegSubRegPair>, 4> CopyInfos; 933 MachineBasicBlock::iterator I = TailBB->begin(); 934 // Process PHI instructions first. 935 while (I != TailBB->end() && I->isPHI()) { 936 // Replace the uses of the def of the PHI with the register coming 937 // from PredBB. 938 MachineInstr *MI = &*I++; 939 processPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, 940 true); 941 } 942 943 // Now copy the non-PHI instructions. 944 while (I != TailBB->end()) { 945 // Replace def of virtual registers with new registers, and update 946 // uses with PHI source register or the new registers. 947 MachineInstr *MI = &*I++; 948 assert(!MI->isBundle() && "Not expecting bundles before regalloc!"); 949 duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi); 950 MI->eraseFromParent(); 951 } 952 appendCopies(PrevBB, CopyInfos, Copies); 953 } else { 954 TII->removeBranch(*PrevBB); 955 // No PHIs to worry about, just splice the instructions over. 956 PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 957 } 958 PrevBB->removeSuccessor(PrevBB->succ_begin()); 959 assert(PrevBB->succ_empty()); 960 PrevBB->transferSuccessors(TailBB); 961 962 // Update branches in PrevBB based on Tail's layout successor. 963 if (ShouldUpdateTerminators) 964 PrevBB->updateTerminator(TailBB->getNextNode()); 965 966 TDBBs.push_back(PrevBB); 967 Changed = true; 968 } else { 969 LLVM_DEBUG(dbgs() << "Abort merging blocks, the predecessor still " 970 "contains terminator instructions"); 971 // Return early if no changes were made 972 if (!Changed) 973 return RemovedBranches; 974 } 975 Changed |= RemovedBranches; 976 } 977 978 // If this is after register allocation, there are no phis to fix. 979 if (!PreRegAlloc) 980 return Changed; 981 982 // If we made no changes so far, we are safe. 983 if (!Changed) 984 return Changed; 985 986 // Handle the nasty case in that we duplicated a block that is part of a loop 987 // into some but not all of its predecessors. For example: 988 // 1 -> 2 <-> 3 | 989 // \ | 990 // \---> rest | 991 // if we duplicate 2 into 1 but not into 3, we end up with 992 // 12 -> 3 <-> 2 -> rest | 993 // \ / | 994 // \----->-----/ | 995 // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced 996 // with a phi in 3 (which now dominates 2). 997 // What we do here is introduce a copy in 3 of the register defined by the 998 // phi, just like when we are duplicating 2 into 3, but we don't copy any 999 // real instructions or remove the 3 -> 2 edge from the phi in 2. 1000 for (MachineBasicBlock *PredBB : Preds) { 1001 if (is_contained(TDBBs, PredBB)) 1002 continue; 1003 1004 // EH edges 1005 if (PredBB->succ_size() != 1) 1006 continue; 1007 1008 DenseMap<Register, RegSubRegPair> LocalVRMap; 1009 SmallVector<std::pair<Register, RegSubRegPair>, 4> CopyInfos; 1010 MachineBasicBlock::iterator I = TailBB->begin(); 1011 // Process PHI instructions first. 1012 while (I != TailBB->end() && I->isPHI()) { 1013 // Replace the uses of the def of the PHI with the register coming 1014 // from PredBB. 1015 MachineInstr *MI = &*I++; 1016 processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); 1017 } 1018 appendCopies(PredBB, CopyInfos, Copies); 1019 } 1020 1021 return Changed; 1022 } 1023 1024 /// At the end of the block \p MBB generate COPY instructions between registers 1025 /// described by \p CopyInfos. Append resulting instructions to \p Copies. 1026 void TailDuplicator::appendCopies(MachineBasicBlock *MBB, 1027 SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos, 1028 SmallVectorImpl<MachineInstr*> &Copies) { 1029 MachineBasicBlock::iterator Loc = MBB->getFirstTerminator(); 1030 const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY); 1031 for (auto &CI : CopyInfos) { 1032 auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first) 1033 .addReg(CI.second.Reg, 0, CI.second.SubReg); 1034 Copies.push_back(C); 1035 } 1036 } 1037 1038 /// Remove the specified dead machine basic block from the function, updating 1039 /// the CFG. 1040 void TailDuplicator::removeDeadBlock( 1041 MachineBasicBlock *MBB, 1042 function_ref<void(MachineBasicBlock *)> *RemovalCallback) { 1043 assert(MBB->pred_empty() && "MBB must be dead!"); 1044 LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 1045 1046 MachineFunction *MF = MBB->getParent(); 1047 // Update the call site info. 1048 for (const MachineInstr &MI : *MBB) 1049 if (MI.shouldUpdateCallSiteInfo()) 1050 MF->eraseCallSiteInfo(&MI); 1051 1052 if (RemovalCallback) 1053 (*RemovalCallback)(MBB); 1054 1055 // Remove all successors. 1056 while (!MBB->succ_empty()) 1057 MBB->removeSuccessor(MBB->succ_end() - 1); 1058 1059 // Remove the block. 1060 MBB->eraseFromParent(); 1061 } 1062