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

Generated by: LCOV version 1.13