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