LCOV - code coverage report
Current view: top level - lib/CodeGen - TailDuplicator.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 329 388 84.8 %
Date: 2018-06-17 00:07:59 Functions: 20 21 95.2 %
Legend: Lines: hit not hit

          Line data    Source code
       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      101169 : static cl::opt<unsigned> TailDuplicateSize(
      61             :     "tail-dup-size",
      62      202338 :     cl::desc("Maximum instructions to consider tail duplicating"), cl::init(2),
      63      303507 :     cl::Hidden);
      64             : 
      65      101169 : static cl::opt<unsigned> TailDupIndirectBranchSize(
      66             :     "tail-dup-indirect-size",
      67      101169 :     cl::desc("Maximum instructions to consider tail duplicating blocks that "
      68      202338 :              "end with indirect branches."), cl::init(20),
      69      303507 :     cl::Hidden);
      70             : 
      71             : static cl::opt<bool>
      72      101169 :     TailDupVerify("tail-dup-verify",
      73      101169 :                   cl::desc("Verify sanity of PHI instructions during taildup"),
      74      303507 :                   cl::init(false), cl::Hidden);
      75             : 
      76      303507 : static cl::opt<unsigned> TailDupLimit("tail-dup-limit", cl::init(~0U),
      77      303507 :                                       cl::Hidden);
      78             : 
      79      374208 : void TailDuplicator::initMF(MachineFunction &MFin, bool PreRegAlloc,
      80             :                             const MachineBranchProbabilityInfo *MBPIin,
      81             :                             bool LayoutModeIn, unsigned TailDupSizeIn) {
      82      374208 :   MF = &MFin;
      83      374208 :   TII = MF->getSubtarget().getInstrInfo();
      84      374208 :   TRI = MF->getSubtarget().getRegisterInfo();
      85      374208 :   MRI = &MF->getRegInfo();
      86      374208 :   MMI = &MF->getMMI();
      87      374208 :   MBPI = MBPIin;
      88      374208 :   TailDupSize = TailDupSizeIn;
      89             : 
      90             :   assert(MBPI != nullptr && "Machine Branch Probability Info required");
      91             : 
      92      374208 :   LayoutMode = LayoutModeIn;
      93      374208 :   this->PreRegAlloc = PreRegAlloc;
      94      374208 : }
      95             : 
      96           0 : static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) {
      97           0 :   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           0 :                                                  MBB->pred_end());
     101           0 :     MachineBasicBlock::iterator MI = MBB->begin();
     102           0 :     while (MI != MBB->end()) {
     103             :       if (!MI->isPHI())
     104             :         break;
     105           0 :       for (MachineBasicBlock *PredBB : Preds) {
     106             :         bool Found = false;
     107           0 :         for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
     108           0 :           MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB();
     109           0 :           if (PHIBB == PredBB) {
     110             :             Found = true;
     111             :             break;
     112             :           }
     113             :         }
     114           0 :         if (!Found) {
     115           0 :           dbgs() << "Malformed PHI in " << printMBBReference(*MBB) << ": "
     116           0 :                  << *MI;
     117           0 :           dbgs() << "  missing input from predecessor "
     118           0 :                  << printMBBReference(*PredBB) << '\n';
     119           0 :           llvm_unreachable(nullptr);
     120             :         }
     121             :       }
     122             : 
     123           0 :       for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
     124           0 :         MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB();
     125           0 :         if (CheckExtra && !Preds.count(PHIBB)) {
     126           0 :           dbgs() << "Warning: malformed PHI in " << printMBBReference(*MBB)
     127           0 :                  << ": " << *MI;
     128           0 :           dbgs() << "  extra input from predecessor "
     129           0 :                  << printMBBReference(*PHIBB) << '\n';
     130           0 :           llvm_unreachable(nullptr);
     131             :         }
     132           0 :         if (PHIBB->getNumber() < 0) {
     133           0 :           dbgs() << "Malformed PHI in " << printMBBReference(*MBB) << ": "
     134           0 :                  << *MI;
     135           0 :           dbgs() << "  non-existing " << printMBBReference(*PHIBB) << '\n';
     136           0 :           llvm_unreachable(nullptr);
     137             :         }
     138             :       }
     139             :       ++MI;
     140             :     }
     141             :   }
     142           0 : }
     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       27252 : 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       27252 :                                                MBB->succ_end());
     160             : 
     161             :   SmallVector<MachineBasicBlock *, 8> TDBBs;
     162             :   SmallVector<MachineInstr *, 16> Copies;
     163       27252 :   if (!tailDuplicate(IsSimple, MBB, ForcedLayoutPred, TDBBs, Copies))
     164             :     return false;
     165             : 
     166             :   ++NumTails;
     167             : 
     168             :   SmallVector<MachineInstr *, 8> NewPHIs;
     169        7050 :   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        3525 :   bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken();
     175        3525 :   if (PreRegAlloc)
     176        1650 :     updateSuccessorsPHIs(MBB, isDead, TDBBs, Succs);
     177             : 
     178             :   // If it is dead, remove it.
     179        3525 :   if (isDead) {
     180             :     NumTailDupRemoved += MBB->size();
     181        2837 :     removeDeadBlock(MBB, RemovalCallback);
     182             :     ++NumDeadBlocks;
     183             :   }
     184             : 
     185             :   // Update SSA form.
     186        3525 :   if (!SSAUpdateVRs.empty()) {
     187        1948 :     for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) {
     188        2494 :       unsigned VReg = SSAUpdateVRs[i];
     189        1247 :       SSAUpdate.Initialize(VReg);
     190             : 
     191             :       // If the original definition is still around, add it as an available
     192             :       // value.
     193        1247 :       MachineInstr *DefMI = MRI->getVRegDef(VReg);
     194             :       MachineBasicBlock *DefBB = nullptr;
     195        1247 :       if (DefMI) {
     196           2 :         DefBB = DefMI->getParent();
     197           2 :         SSAUpdate.AddAvailableValue(DefBB, VReg);
     198             :       }
     199             : 
     200             :       // Add the new vregs as available values.
     201             :       DenseMap<unsigned, AvailableValsTy>::iterator LI =
     202        1247 :           SSAUpdateVals.find(VReg);
     203        5397 :       for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {
     204        5806 :         MachineBasicBlock *SrcBB = LI->second[j].first;
     205        2903 :         unsigned SrcReg = LI->second[j].second;
     206        2903 :         SSAUpdate.AddAvailableValue(SrcBB, SrcReg);
     207             :       }
     208             : 
     209             :       // Rewrite uses that are outside of the original def's block.
     210        1247 :       MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg);
     211        1311 :       while (UI != MRI->use_end()) {
     212             :         MachineOperand &UseMO = *UI;
     213          64 :         MachineInstr *UseMI = UseMO.getParent();
     214             :         ++UI;
     215          64 :         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           0 :           UseMI->eraseFromParent();
     221           0 :           continue;
     222             :         }
     223          64 :         if (UseMI->getParent() == DefBB && !UseMI->isPHI())
     224           0 :           continue;
     225          64 :         SSAUpdate.RewriteUse(UseMO);
     226             :       }
     227             :     }
     228             : 
     229             :     SSAUpdateVRs.clear();
     230         701 :     SSAUpdateVals.clear();
     231             :   }
     232             : 
     233             :   // Eliminate some of the copies inserted by tail duplication to maintain
     234             :   // SSA form.
     235        6778 :   for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
     236        6506 :     MachineInstr *Copy = Copies[i];
     237        3253 :     if (!Copy->isCopy())
     238           0 :       continue;
     239        3253 :     unsigned Dst = Copy->getOperand(0).getReg();
     240        3253 :     unsigned Src = Copy->getOperand(1).getReg();
     241        6433 :     if (MRI->hasOneNonDBGUse(Src) &&
     242        6360 :         MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) {
     243             :       // Copy is the only use. Do trivial copy propagation here.
     244        3180 :       MRI->replaceRegWith(Dst, Src);
     245        3180 :       Copy->eraseFromParent();
     246             :     }
     247             :   }
     248             : 
     249             :   if (NewPHIs.size())
     250             :     NumAddedPHIs += NewPHIs.size();
     251             : 
     252        3525 :   if (DuplicatedPreds)
     253         864 :     *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      360638 : bool TailDuplicator::tailDuplicateBlocks() {
     262             :   bool MadeChange = false;
     263             : 
     264      542438 :   if (PreRegAlloc && TailDupVerify) {
     265             :     LLVM_DEBUG(dbgs() << "\n*** Before tail-duplicating\n");
     266           0 :     VerifyPHIs(*MF, true);
     267             :   }
     268             : 
     269     1120453 :   for (MachineFunction::iterator I = ++MF->begin(), E = MF->end(); I != E;) {
     270             :     MachineBasicBlock *MBB = &*I++;
     271             : 
     272      399177 :     if (NumTails == TailDupLimit)
     273             :       break;
     274             : 
     275      399177 :     bool IsSimple = isSimpleBB(MBB);
     276             : 
     277      399177 :     if (!shouldTailDuplicate(IsSimple, *MBB))
     278      381072 :       continue;
     279             : 
     280       18105 :     MadeChange |= tailDuplicateAndUpdate(IsSimple, MBB, nullptr);
     281             :   }
     282             : 
     283      542438 :   if (PreRegAlloc && TailDupVerify)
     284           0 :     VerifyPHIs(*MF, false);
     285             : 
     286      360638 :   return MadeChange;
     287             : }
     288             : 
     289        3383 : static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB,
     290             :                          const MachineRegisterInfo *MRI) {
     291        7124 :   for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {
     292        3077 :     if (UseMI.isDebugValue())
     293           0 :       continue;
     294        3077 :     if (UseMI.getParent() != BB)
     295        2898 :       return true;
     296             :   }
     297         485 :   return false;
     298             : }
     299             : 
     300             : static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) {
     301       12655 :   for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2)
     302       25310 :     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       27252 : static void getRegsUsedByPHIs(const MachineBasicBlock &BB,
     311             :                               DenseSet<unsigned> *UsedByPhi) {
     312       55916 :   for (const auto &MI : BB) {
     313             :     if (!MI.isPHI())
     314             :       break;
     315        4689 :     for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
     316        6554 :       unsigned SrcReg = MI.getOperand(i).getReg();
     317             :       UsedByPhi->insert(SrcReg);
     318             :     }
     319             :   }
     320       27252 : }
     321             : 
     322             : /// Add a definition and source virtual registers pair for SSA update.
     323        2903 : void TailDuplicator::addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
     324             :                                        MachineBasicBlock *BB) {
     325             :   DenseMap<unsigned, AvailableValsTy>::iterator LI =
     326        2903 :       SSAUpdateVals.find(OrigReg);
     327        2903 :   if (LI != SSAUpdateVals.end())
     328        3312 :     LI->second.push_back(std::make_pair(BB, NewReg));
     329             :   else {
     330             :     AvailableValsTy Vals;
     331        2494 :     Vals.push_back(std::make_pair(BB, NewReg));
     332        3741 :     SSAUpdateVals.insert(std::make_pair(OrigReg, Vals));
     333        1247 :     SSAUpdateVRs.push_back(OrigReg);
     334             :   }
     335        2903 : }
     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        3253 : 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        3253 :   unsigned DefReg = MI->getOperand(0).getReg();
     345             :   unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB);
     346             :   assert(SrcOpIdx && "Unable to find matching PHI source?");
     347        3253 :   unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg();
     348             :   unsigned SrcSubReg = MI->getOperand(SrcOpIdx).getSubReg();
     349        3253 :   const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
     350        6506 :   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        6506 :   unsigned NewDef = MRI->createVirtualRegister(RC);
     355        3253 :   Copies.push_back(std::make_pair(NewDef, RegSubRegPair(SrcReg, SrcSubReg)));
     356        3253 :   if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg))
     357        2880 :     addSSAUpdateEntry(DefReg, NewDef, PredBB);
     358             : 
     359        3253 :   if (!Remove)
     360           0 :     return;
     361             : 
     362             :   // Remove PredBB from the PHI node.
     363        3253 :   MI->RemoveOperand(SrcOpIdx + 1);
     364        3253 :   MI->RemoveOperand(SrcOpIdx);
     365        3253 :   if (MI->getNumOperands() == 1)
     366        1387 :     MI->eraseFromParent();
     367             : }
     368             : 
     369             : /// Duplicate a TailBB instruction to PredBB and update
     370             : /// the source operands due to earlier PHI translation.
     371        9154 : 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        9154 :   if (MI->isCFIInstruction()) {
     377         609 :     BuildMI(*PredBB, PredBB->end(), PredBB->findDebugLoc(PredBB->begin()),
     378         203 :       TII->get(TargetOpcode::CFI_INSTRUCTION)).addCFIIndex(
     379         203 :       MI->getOperand(0).getCFIIndex());
     380         203 :     return;
     381             :   }
     382       17902 :   MachineInstr &NewMI = TII->duplicate(*PredBB, PredBB->end(), *MI);
     383        8951 :   if (PreRegAlloc) {
     384       20045 :     for (unsigned i = 0, e = NewMI.getNumOperands(); i != e; ++i) {
     385       15082 :       MachineOperand &MO = NewMI.getOperand(i);
     386       15082 :       if (!MO.isReg())
     387       22961 :         continue;
     388        6888 :       unsigned Reg = MO.getReg();
     389        6888 :       if (!TargetRegisterInfo::isVirtualRegister(Reg))
     390        6573 :         continue;
     391         315 :       if (MO.isDef()) {
     392         130 :         const TargetRegisterClass *RC = MRI->getRegClass(Reg);
     393         130 :         unsigned NewReg = MRI->createVirtualRegister(RC);
     394         130 :         MO.setReg(NewReg);
     395         260 :         LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
     396         130 :         if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg))
     397          23 :           addSSAUpdateEntry(Reg, NewReg, PredBB);
     398             :       } else {
     399         185 :         auto VI = LocalVRMap.find(Reg);
     400         185 :         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         159 :           auto *OrigRC = MRI->getRegClass(Reg);
     405         159 :           auto *MappedRC = MRI->getRegClass(VI->second.Reg);
     406             :           const TargetRegisterClass *ConstrRC;
     407         159 :           if (VI->second.SubReg != 0) {
     408           0 :             ConstrRC = TRI->getMatchingSuperRegClass(MappedRC, OrigRC,
     409           0 :                                                      VI->second.SubReg);
     410           0 :             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           0 :               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         159 :             ConstrRC = MRI->constrainRegClass(VI->second.Reg, OrigRC);
     420             :           }
     421             : 
     422         159 :           if (ConstrRC) {
     423             :             // If the class constraining succeeded, we can simply replace
     424             :             // the old register with the mapped one.
     425         159 :             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         159 :             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           0 :             auto *NewRC = MI->getRegClassConstraint(i, TII, TRI);
     435           0 :             if (NewRC == nullptr)
     436             :               NewRC = OrigRC;
     437           0 :             unsigned NewReg = MRI->createVirtualRegister(NewRC);
     438           0 :             BuildMI(*PredBB, MI, MI->getDebugLoc(),
     439           0 :                     TII->get(TargetOpcode::COPY), NewReg)
     440           0 :                 .addReg(VI->second.Reg, 0, VI->second.SubReg);
     441             :             LocalVRMap.erase(VI);
     442           0 :             LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
     443           0 :             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        1650 : void TailDuplicator::updateSuccessorsPHIs(
     462             :     MachineBasicBlock *FromBB, bool isDead,
     463             :     SmallVectorImpl<MachineBasicBlock *> &TDBBs,
     464             :     SmallSetVector<MachineBasicBlock *, 8> &Succs) {
     465        5086 :   for (MachineBasicBlock *SuccBB : Succs) {
     466        4879 :     for (MachineInstr &MI : *SuccBB) {
     467             :       if (!MI.isPHI())
     468             :         break;
     469        1443 :       MachineInstrBuilder MIB(*FromBB->getParent(), MI);
     470             :       unsigned Idx = 0;
     471        4328 :       for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
     472        4328 :         MachineOperand &MO = MI.getOperand(i + 1);
     473        4328 :         if (MO.getMBB() == FromBB) {
     474             :           Idx = i;
     475             :           break;
     476             :         }
     477             :       }
     478             : 
     479             :       assert(Idx != 0);
     480        1443 :       MachineOperand &MO0 = MI.getOperand(Idx);
     481        1443 :       unsigned Reg = MO0.getReg();
     482        1443 :       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        8462 :         for (unsigned i = MI.getNumOperands() - 2; i != Idx; i -= 2) {
     487        7025 :           MachineOperand &MO = MI.getOperand(i + 1);
     488        7025 :           if (MO.getMBB() == FromBB) {
     489           0 :             MI.RemoveOperand(i + 1);
     490           0 :             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        1443 :           SSAUpdateVals.find(Reg);
     501        1443 :       if (LI != SSAUpdateVals.end()) {
     502             :         // This register is defined in the tail block.
     503        5363 :         for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {
     504        5762 :           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        2881 :           if (!SrcBB->isSuccessor(SuccBB))
     510           0 :             continue;
     511             : 
     512        5762 :           unsigned SrcReg = LI->second[j].second;
     513        2881 :           if (Idx != 0) {
     514        2482 :             MI.getOperand(Idx).setReg(SrcReg);
     515        1241 :             MI.getOperand(Idx + 1).setMBB(SrcBB);
     516             :             Idx = 0;
     517             :           } else {
     518        1640 :             MIB.addReg(SrcReg).addMBB(SrcBB);
     519             :           }
     520             :         }
     521             :       } else {
     522             :         // Live in tail block, must also be live in predecessors.
     523         418 :         for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) {
     524         432 :           MachineBasicBlock *SrcBB = TDBBs[j];
     525         216 :           if (Idx != 0) {
     526         392 :             MI.getOperand(Idx).setReg(Reg);
     527         196 :             MI.getOperand(Idx + 1).setMBB(SrcBB);
     528             :             Idx = 0;
     529             :           } else {
     530          20 :             MIB.addReg(Reg).addMBB(SrcBB);
     531             :           }
     532             :         }
     533             :       }
     534        1443 :       if (Idx != 0) {
     535           0 :         MI.RemoveOperand(Idx + 1);
     536           0 :         MI.RemoveOperand(Idx);
     537             :       }
     538             :     }
     539             :   }
     540        1650 : }
     541             : 
     542             : /// Determine if it is profitable to duplicate this block.
     543      558292 : 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      558292 :   if (!LayoutMode && TailBB.canFallThrough())
     549             :     return false;
     550             : 
     551             :   // Don't try to tail-duplicate single-block loops.
     552      320676 :   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      472546 :   if (TailDupSize == 0 &&
     560      472526 :       TailDuplicateSize.getNumOccurrences() == 0 &&
     561      160325 :       MF->getFunction().optForSize())
     562             :     MaxDuplicateCount = 1;
     563      311148 :   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      312201 :   MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
     573             :   SmallVector<MachineOperand, 4> PredCond;
     574      383604 :   if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond) &&
     575       71403 :       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      312160 :   if (!TailBB.empty())
     586             :     HasIndirectbr = TailBB.back().isIndirectBranch();
     587             : 
     588      309163 :   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     1158640 :   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      798974 :     if (MI.isNotDuplicable() &&
     601      156541 :         (TailBB.getParent()->getTarget().getTargetTriple().isOSDarwin() ||
     602             :         !MI.isCFIInstruction()))
     603      264654 :       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      734181 :     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      938055 :     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      914131 :     if (PreRegAlloc && MI.isCall())
     620             :       return false;
     621             : 
     622             :     if (!MI.isPHI() && !MI.isMetaInstruction())
     623      656677 :       InstrCount += 1;
     624             : 
     625      719735 :     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       75604 :   for (auto SB : TailBB.successors()) {
     639       59602 :     for (auto &I : *SB) {
     640             :       if (!I.isPHI())
     641             :         break;
     642             :       unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB);
     643             :       assert(Idx != 0);
     644        3406 :       MachineOperand &PU = I.getOperand(Idx);
     645        3406 :       if (PU.getSubReg() != 0)
     646           0 :         return false;
     647             :     }
     648             :   }
     649             : 
     650       47506 :   if (HasIndirectbr && PreRegAlloc)
     651             :     return true;
     652             : 
     653       47266 :   if (IsSimple)
     654             :     return true;
     655             : 
     656       46229 :   if (!PreRegAlloc)
     657             :     return true;
     658             : 
     659        3871 :   return canCompletelyDuplicateBB(TailBB);
     660             : }
     661             : 
     662             : /// True if this BB has only one unconditional jump.
     663      649827 : bool TailDuplicator::isSimpleBB(MachineBasicBlock *TailBB) {
     664      649827 :   if (TailBB->succ_size() != 1)
     665             :     return false;
     666      250488 :   if (TailBB->pred_empty())
     667             :     return false;
     668      250485 :   MachineBasicBlock::iterator I = TailBB->getFirstNonDebugInstr();
     669      250485 :   if (I == TailBB->end())
     670             :     return true;
     671      247390 :   return I->isUnconditionalBranch();
     672             : }
     673             : 
     674        1073 : static bool bothUsedInPHI(const MachineBasicBlock &A,
     675             :                           const SmallPtrSet<MachineBasicBlock *, 8> &SuccsB) {
     676        3485 :   for (MachineBasicBlock *BB : A.successors())
     677        2651 :     if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI())
     678             :       return true;
     679             : 
     680             :   return false;
     681             : }
     682             : 
     683        3871 : bool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) {
     684        5674 :   for (MachineBasicBlock *PredBB : BB.predecessors()) {
     685        4805 :     if (PredBB->succ_size() > 1)
     686        3002 :       return false;
     687             : 
     688        1824 :     MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
     689             :     SmallVector<MachineOperand, 4> PredCond;
     690        1824 :     if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
     691             :       return false;
     692             : 
     693        1804 :     if (!PredCond.empty())
     694             :       return false;
     695             :   }
     696             :   return true;
     697             : }
     698             : 
     699        1037 : 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        1037 :                                             TailBB->succ_end());
     705             :   SmallVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(),
     706             :                                             TailBB->pred_end());
     707             :   bool Changed = false;
     708        3205 :   for (MachineBasicBlock *PredBB : Preds) {
     709        1084 :     if (PredBB->hasEHPadSuccessor())
     710         181 :       continue;
     711             : 
     712        1073 :     if (bothUsedInPHI(*PredBB, Succs))
     713          86 :       continue;
     714             : 
     715         987 :     MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
     716             :     SmallVector<MachineOperand, 4> PredCond;
     717         987 :     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         914 :     MachineBasicBlock *NewTarget = *TailBB->succ_begin();
     725         914 :     MachineBasicBlock *NextBB = PredBB->getNextNode();
     726             : 
     727             :     // Make PredFBB explicit.
     728         914 :     if (PredCond.empty())
     729          19 :       PredFBB = PredTBB;
     730             : 
     731             :     // Make fall through explicit.
     732         914 :     if (!PredTBB)
     733          11 :       PredTBB = NextBB;
     734         914 :     if (!PredFBB)
     735          21 :       PredFBB = NextBB;
     736             : 
     737             :     // Redirect
     738         914 :     if (PredFBB == TailBB)
     739         840 :       PredFBB = NewTarget;
     740         914 :     if (PredTBB == TailBB)
     741          93 :       PredTBB = NewTarget;
     742             : 
     743             :     // Make the branch unconditional if possible
     744         914 :     if (PredTBB == PredFBB) {
     745             :       PredCond.clear();
     746          66 :       PredFBB = nullptr;
     747             :     }
     748             : 
     749             :     // Avoid adding fall through branches.
     750         914 :     if (PredFBB == NextBB)
     751          45 :       PredFBB = nullptr;
     752         914 :     if (PredTBB == NextBB && PredFBB == nullptr)
     753          12 :       PredTBB = nullptr;
     754             : 
     755         914 :     auto DL = PredBB->findBranchDebugLoc();
     756         914 :     TII->removeBranch(*PredBB);
     757             : 
     758         914 :     if (!PredBB->isSuccessor(NewTarget))
     759         867 :       PredBB->replaceSuccessor(TailBB, NewTarget);
     760             :     else {
     761          47 :       PredBB->removeSuccessor(TailBB, true);
     762             :       assert(PredBB->succ_size() <= 1);
     763             :     }
     764             : 
     765         914 :     if (PredTBB)
     766        1804 :       TII->insertBranch(*PredBB, PredTBB, PredFBB, PredCond, DL);
     767             : 
     768         914 :     TDBBs.push_back(PredBB);
     769             :   }
     770        1037 :   return Changed;
     771             : }
     772             : 
     773       41725 : bool TailDuplicator::canTailDuplicate(MachineBasicBlock *TailBB,
     774             :                                       MachineBasicBlock *PredBB) {
     775             :   // EH edges are ignored by analyzeBranch.
     776       41725 :   if (PredBB->succ_size() > 1)
     777             :     return false;
     778             : 
     779       13200 :   MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
     780             :   SmallVector<MachineOperand, 4> PredCond;
     781       13200 :   if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
     782             :     return false;
     783       12991 :   if (!PredCond.empty())
     784             :     return false;
     785       12967 :   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       27252 : 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       27252 :   getRegsUsedByPHIs(*TailBB, &UsedByPhi);
     807             : 
     808       27252 :   if (IsSimple)
     809        1037 :     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       26215 :                                                TailBB->pred_end());
     817       99969 :   for (MachineBasicBlock *PredBB : Preds) {
     818             :     assert(TailBB != PredBB &&
     819             :            "Single-block loop should have been rejected earlier!");
     820             : 
     821       36877 :     if (!canTailDuplicate(TailBB, PredBB))
     822       60645 :       continue;
     823             : 
     824             :     // Don't duplicate into a fall-through predecessor (at least for now).
     825             :     bool IsLayoutSuccessor = false;
     826        9550 :     if (ForcedLayoutPred)
     827        3082 :       IsLayoutSuccessor = (ForcedLayoutPred == PredBB);
     828        6468 :     else if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough())
     829             :       IsLayoutSuccessor = true;
     830        9073 :     if (IsLayoutSuccessor)
     831        5991 :       continue;
     832             : 
     833             :     LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
     834             :                       << "From Succ: " << *TailBB);
     835             : 
     836        3559 :     TDBBs.push_back(PredBB);
     837             : 
     838             :     // Remove PredBB's unconditional branch.
     839        3559 :     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        3559 :     for (MachineBasicBlock::iterator I = TailBB->begin(), E = TailBB->end();
     845       14603 :          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        2732 :         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        8312 :         duplicateInstruction(MI, TailBB, PredBB, LocalVRMap, UsedByPhi);
     856             :       }
     857             :     }
     858        3559 :     appendCopies(PredBB, CopyInfos, Copies);
     859             : 
     860             :     // Simplify
     861        3559 :     MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
     862             :     SmallVector<MachineOperand, 4> PredCond;
     863        3559 :     TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond);
     864             : 
     865             :     NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch
     866             : 
     867             :     // Update the CFG.
     868        7118 :     PredBB->removeSuccessor(PredBB->succ_begin());
     869             :     assert(PredBB->succ_empty() &&
     870             :            "TailDuplicate called on block with multiple successors!");
     871        6913 :     for (MachineBasicBlock *Succ : TailBB->successors())
     872        3354 :       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       26215 :   MachineBasicBlock *PrevBB = ForcedLayoutPred;
     882       26215 :   if (!PrevBB)
     883       34136 :     PrevBB = &*std::prev(TailBB->getIterator());
     884       26215 :   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       33189 :   if (PrevBB->succ_size() == 1 &&
     889             :       // Layout preds are not always CFG preds. Check.
     890       13166 :       *PrevBB->succ_begin() == TailBB &&
     891       12203 :       !TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond) &&
     892       12002 :       PriorCond.empty() &&
     893       12189 :       (!PriorTBB || PriorTBB == TailBB) &&
     894       27783 :       TailBB->pred_size() == 1 &&
     895        1568 :       !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        1518 :     TII->removeBranch(*PrevBB);
     902        1518 :     if (PreRegAlloc) {
     903             :       DenseMap<unsigned, RegSubRegPair> LocalVRMap;
     904             :       SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos;
     905         316 :       MachineBasicBlock::iterator I = TailBB->begin();
     906             :       // Process PHI instructions first.
     907        1358 :       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         521 :         processPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true);
     912             :       }
     913             : 
     914             :       // Now copy the non-PHI instructions.
     915        2000 :       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         842 :         duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi);
     921         842 :         MI->eraseFromParent();
     922             :       }
     923         316 :       appendCopies(PrevBB, CopyInfos, Copies);
     924             :     } else {
     925        1202 :       TII->removeBranch(*PrevBB);
     926             :       // No PHIs to worry about, just splice the instructions over.
     927        1202 :       PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());
     928             :     }
     929        3036 :     PrevBB->removeSuccessor(PrevBB->succ_begin());
     930             :     assert(PrevBB->succ_empty());
     931        1518 :     PrevBB->transferSuccessors(TailBB);
     932        1518 :     TDBBs.push_back(PrevBB);
     933             :     Changed = true;
     934             :   }
     935             : 
     936             :   // If this is after register allocation, there are no phis to fix.
     937       26215 :   if (!PreRegAlloc)
     938             :     return Changed;
     939             : 
     940             :   // If we made no changes so far, we are safe.
     941        1109 :   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        4321 :   for (MachineBasicBlock *PredBB : Preds) {
     959        1773 :     if (is_contained(TDBBs, PredBB))
     960        3536 :       continue;
     961             : 
     962             :     // EH edges
     963          10 :     if (PredBB->succ_size() != 1)
     964          10 :       continue;
     965             : 
     966             :     DenseMap<unsigned, RegSubRegPair> LocalVRMap;
     967             :     SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos;
     968           0 :     MachineBasicBlock::iterator I = TailBB->begin();
     969             :     // Process PHI instructions first.
     970           0 :     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           0 :       processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false);
     975             :     }
     976           0 :     appendCopies(PredBB, CopyInfos, Copies);
     977             :   }
     978             : 
     979         775 :   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        3875 : void TailDuplicator::appendCopies(MachineBasicBlock *MBB,
     985             :       SmallVectorImpl<std::pair<unsigned,RegSubRegPair>> &CopyInfos,
     986             :       SmallVectorImpl<MachineInstr*> &Copies) {
     987        3875 :   MachineBasicBlock::iterator Loc = MBB->getFirstTerminator();
     988        3875 :   const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY);
     989       10381 :   for (auto &CI : CopyInfos) {
     990        9759 :     auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first)
     991        3253 :                 .addReg(CI.second.Reg, 0, CI.second.SubReg);
     992        3253 :     Copies.push_back(C);
     993             :   }
     994        3875 : }
     995             : 
     996             : /// Remove the specified dead machine basic block from the function, updating
     997             : /// the CFG.
     998        2837 : 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        2837 :   if (RemovalCallback)
    1005             :     (*RemovalCallback)(MBB);
    1006             : 
    1007             :   // Remove all successors.
    1008        5475 :   while (!MBB->succ_empty())
    1009        1319 :     MBB->removeSuccessor(MBB->succ_end() - 1);
    1010             : 
    1011             :   // Remove the block.
    1012        2837 :   MBB->eraseFromParent();
    1013      306344 : }

Generated by: LCOV version 1.13