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