contrib/llvm/lib/CodeGen/TailDuplicator.cpp

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