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