contrib/llvm-project/llvm/lib/CodeGen/TailDuplicator.cpp

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