contrib/llvm/lib/CodeGen/TailDuplicator.cpp

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