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