lib/CodeGen/TailDuplication.cpp

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