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/MachineRegisterInfo.h"
  21 #include "llvm/CodeGen/MachineSSAUpdater.h"
  22 #include "llvm/Target/TargetInstrInfo.h"
  23 #include "llvm/Support/CommandLine.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include "llvm/ADT/SmallSet.h"
  27 #include "llvm/ADT/SetVector.h"
  28 #include "llvm/ADT/Statistic.h"
  29 using namespace llvm;
  30
  31 STATISTIC(NumTailDups  , "Number of tail duplicated blocks");
  32 STATISTIC(NumInstrDups , "Additional instructions due to tail duplication");
  33 STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
  34
  35 // Heuristic for tail duplication.
  36 static cl::opt<unsigned>
  37 TailDuplicateSize("tail-dup-size",
  38                   cl::desc("Maximum instructions to consider tail duplicating"),
  39                   cl::init(2), cl::Hidden);
  40
  41 typedef std::vector<unsigned> AvailableValsTy;
  42
  43 namespace {
  44   /// TailDuplicatePass - Perform tail duplication.
  45   class TailDuplicatePass : public MachineFunctionPass {
  46     const TargetInstrInfo *TII;
  47     MachineModuleInfo *MMI;
  48     MachineRegisterInfo *MRI;
  49
  50     // SSAUpdateVRs - A list of virtual registers for which to update SSA form.
  51     SmallVector<unsigned, 16> SSAUpdateVRs;
  52
  53     // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of
  54     // source virtual registers.
  55     DenseMap<unsigned, AvailableValsTy> SSAUpdateVals;
  56
  57   public:
  58     static char ID;
  59     explicit TailDuplicatePass() : MachineFunctionPass(&ID) {}
  60
  61     virtual bool runOnMachineFunction(MachineFunction &MF);
  62     virtual const char *getPassName() const { return "Tail Duplication"; }
  63
  64   private:
  65     void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg);
  66     bool TailDuplicateBlocks(MachineFunction &MF);
  67     bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF);
  68     void RemoveDeadBlock(MachineBasicBlock *MBB);
  69   };
  70
  71   char TailDuplicatePass::ID = 0;
  72 }
  73
  74 FunctionPass *llvm::createTailDuplicatePass() {
  75   return new TailDuplicatePass();
  76 }
  77
  78 bool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) {
  79   TII = MF.getTarget().getInstrInfo();
  80   MRI = &MF.getRegInfo();
  81   MMI = getAnalysisIfAvailable<MachineModuleInfo>();
  82
  83   bool MadeChange = false;
  84   bool MadeChangeThisIteration = true;
  85   while (MadeChangeThisIteration) {
  86     MadeChangeThisIteration = false;
  87     MadeChangeThisIteration |= TailDuplicateBlocks(MF);
  88     MadeChange |= MadeChangeThisIteration;
  89   }
  90
  91   return MadeChange;
  92 }
  93
  94 /// TailDuplicateBlocks - Look for small blocks that are unconditionally
  95 /// branched to and do not fall through. Tail-duplicate their instructions
  96 /// into their predecessors to eliminate (dynamic) branches.
  97 bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) {
  98   bool MadeChange = false;
  99
 100   SSAUpdateVRs.clear();
 101   SSAUpdateVals.clear();
 102
 103   for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
 104     MachineBasicBlock *MBB = I++;
 105
 106     // Only duplicate blocks that end with unconditional branches.
 107     if (MBB->canFallThrough())
 108       continue;
 109
 110     MadeChange |= TailDuplicate(MBB, MF);
 111
 112     // If it is dead, remove it.
 113     if (MBB->pred_empty()) {
 114       NumInstrDups -= MBB->size();
 115       RemoveDeadBlock(MBB);
 116       MadeChange = true;
 117       ++NumDeadBlocks;
 118     }
 119   }
 120
 121   if (!SSAUpdateVRs.empty()) {
 122     // Update SSA form.
 123     MachineSSAUpdater SSAUpdate(MF);
 124
 125     for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) {
 126       unsigned VReg = SSAUpdateVRs[i];
 127       SSAUpdate.Initialize(VReg);
 128
 129       // If the original definition is still around, add it as an available
 130       // value.
 131       MachineInstr *DefMI = MRI->getVRegDef(VReg);
 132       MachineBasicBlock *DefBB = 0;
 133       if (DefMI) {
 134         DefBB = DefMI->getParent();
 135         SSAUpdate.AddAvailableValue(DefBB, VReg);
 136       }
 137
 138       // Add the new vregs as available values.
 139       DenseMap<unsigned, AvailableValsTy>::iterator LI =
 140         SSAUpdateVals.find(VReg);
 141       for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {
 142         unsigned NewReg = LI->second[j];
 143         MachineInstr *DefMI = MRI->getVRegDef(NewReg);
 144         SSAUpdate.AddAvailableValue(DefMI->getParent(), NewReg);
 145       }
 146
 147       // Rewrite uses that are outside of the original def's block.
 148       for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg),
 149              UE = MRI->use_end(); UI != UE; ++UI) {
 150         MachineInstr *UseMI = &*UI;
 151         if (UseMI->getParent() != DefBB)
 152           SSAUpdate.RewriteUse(UI.getOperand());
 153       }
 154     }
 155   }
 156
 157   return MadeChange;
 158 }
 159
 160 static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB,
 161                          const MachineRegisterInfo *MRI) {
 162   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
 163          UE = MRI->use_end(); UI != UE; ++UI) {
 164     MachineInstr *UseMI = &*UI;
 165     if (UseMI->getParent() != BB)
 166       return true;
 167   }
 168   return false;
 169 }
 170
 171 static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) {
 172   for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2)
 173     if (MI->getOperand(i+1).getMBB() == SrcBB)
 174       return i;
 175   return 0;
 176 }
 177
 178 /// AddSSAUpdateEntry - Add a definition and source virtual registers pair for
 179 /// SSA update.
 180 void TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg) {
 181   DenseMap<unsigned, AvailableValsTy>::iterator LI =
 182     SSAUpdateVals.find(OrigReg);
 183   if (LI != SSAUpdateVals.end())
 184     LI->second.push_back(NewReg);
 185   else {
 186     AvailableValsTy Vals;
 187     Vals.push_back(NewReg);
 188     SSAUpdateVals.insert(std::make_pair(OrigReg, Vals));
 189     SSAUpdateVRs.push_back(OrigReg);
 190   }
 191 }
 192
 193 /// TailDuplicate - If it is profitable, duplicate TailBB's contents in each
 194 /// of its predecessors.
 195 bool TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB,
 196                                       MachineFunction &MF) {
 197   // Don't try to tail-duplicate single-block loops.
 198   if (TailBB->isSuccessor(TailBB))
 199     return false;
 200
 201   // Set the limit on the number of instructions to duplicate, with a default
 202   // of one less than the tail-merge threshold. When optimizing for size,
 203   // duplicate only one, because one branch instruction can be eliminated to
 204   // compensate for the duplication.
 205   unsigned MaxDuplicateCount;
 206   if (!TailBB->empty() && TailBB->back().getDesc().isIndirectBranch())
 207     // If the target has hardware branch prediction that can handle indirect
 208     // branches, duplicating them can often make them predictable when there
 209     // are common paths through the code.  The limit needs to be high enough
 210     // to allow undoing the effects of tail merging.
 211     MaxDuplicateCount = 20;
 212   else if (MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize))
 213     MaxDuplicateCount = 1;
 214   else
 215     MaxDuplicateCount = TailDuplicateSize;
 216
 217   // Check the instructions in the block to determine whether tail-duplication
 218   // is invalid or unlikely to be profitable.
 219   unsigned InstrCount = 0;
 220   bool HasCall = false;
 221   for (MachineBasicBlock::iterator I = TailBB->begin();
 222        I != TailBB->end(); ++I) {
 223     // Non-duplicable things shouldn't be tail-duplicated.
 224     if (I->getDesc().isNotDuplicable()) return false;
 225     // Don't duplicate more than the threshold.
 226     if (InstrCount == MaxDuplicateCount) return false;
 227     // Remember if we saw a call.
 228     if (I->getDesc().isCall()) HasCall = true;
 229     if (I->getOpcode() != TargetInstrInfo::PHI)
 230       InstrCount += 1;
 231   }
 232   // Heuristically, don't tail-duplicate calls if it would expand code size,
 233   // as it's less likely to be worth the extra cost.
 234   if (InstrCount > 1 && HasCall)
 235     return false;
 236
 237   // Iterate through all the unique predecessors and tail-duplicate this
 238   // block into them, if possible. Copying the list ahead of time also
 239   // avoids trouble with the predecessor list reallocating.
 240   bool Changed = false;
 241   SmallSetVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(),
 242                                                TailBB->pred_end());
 243   for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(),
 244        PE = Preds.end(); PI != PE; ++PI) {
 245     MachineBasicBlock *PredBB = *PI;
 246
 247     assert(TailBB != PredBB &&
 248            "Single-block loop should have been rejected earlier!");
 249     if (PredBB->succ_size() > 1) continue;
 250
 251     MachineBasicBlock *PredTBB, *PredFBB;
 252     SmallVector<MachineOperand, 4> PredCond;
 253     if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true))
 254       continue;
 255     if (!PredCond.empty())
 256       continue;
 257     // EH edges are ignored by AnalyzeBranch.
 258     if (PredBB->succ_size() != 1)
 259       continue;
 260     // Don't duplicate into a fall-through predecessor (at least for now).
 261     if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough())
 262       continue;
 263
 264     DEBUG(errs() << "\nTail-duplicating into PredBB: " << *PredBB
 265                  << "From Succ: " << *TailBB);
 266
 267     // Remove PredBB's unconditional branch.
 268     TII->RemoveBranch(*PredBB);
 269
 270     // Clone the contents of TailBB into PredBB.
 271     DenseMap<unsigned, unsigned> LocalVRMap;
 272     MachineBasicBlock::iterator I = TailBB->begin();
 273     MachineBasicBlock::iterator NI;
 274     for (MachineBasicBlock::iterator E = TailBB->end(); I != E; I = NI) {
 275       NI = next(I);
 276       if (I->getOpcode() == TargetInstrInfo::PHI) {
 277         // Replace the uses of the def of the PHI with the register coming
 278         // from PredBB.
 279         unsigned DefReg = I->getOperand(0).getReg();
 280         unsigned SrcOpIdx = getPHISrcRegOpIdx(I, PredBB);
 281         unsigned SrcReg = I->getOperand(SrcOpIdx).getReg();
 282         LocalVRMap.insert(std::make_pair(DefReg, SrcReg));
 283         if (isDefLiveOut(DefReg, TailBB, MRI))
 284           AddSSAUpdateEntry(DefReg, SrcReg);
 285
 286         // Remove PredBB from the PHI node.
 287         I->RemoveOperand(SrcOpIdx+1);
 288         I->RemoveOperand(SrcOpIdx);
 289         if (I->getNumOperands() == 1)
 290           I->eraseFromParent();
 291         continue;
 292       }
 293
 294       // Replace def of virtual registers with new registers, and update uses
 295       // with PHI source register or the new registers.
 296       MachineInstr *NewMI = MF.CloneMachineInstr(I);
 297       for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) {
 298         MachineOperand &MO = NewMI->getOperand(i);
 299         if (!MO.isReg())
 300           continue;
 301         unsigned Reg = MO.getReg();
 302         if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg))
 303           continue;
 304         if (MO.isDef()) {
 305           const TargetRegisterClass *RC = MRI->getRegClass(Reg);
 306           unsigned NewReg = MRI->createVirtualRegister(RC);
 307           MO.setReg(NewReg);
 308           LocalVRMap.insert(std::make_pair(Reg, NewReg));
 309           if (isDefLiveOut(Reg, TailBB, MRI))
 310             AddSSAUpdateEntry(Reg, NewReg);
 311         } else {
 312           DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg);
 313           if (VI != LocalVRMap.end())
 314             MO.setReg(VI->second);
 315         }
 316       }
 317       PredBB->insert(PredBB->end(), NewMI);
 318     }
 319     NumInstrDups += TailBB->size() - 1; // subtract one for removed branch
 320
 321     // Update the CFG.
 322     PredBB->removeSuccessor(PredBB->succ_begin());
 323     assert(PredBB->succ_empty() &&
 324            "TailDuplicate called on block with multiple successors!");
 325     for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(),
 326          E = TailBB->succ_end(); I != E; ++I)
 327        PredBB->addSuccessor(*I);
 328
 329     Changed = true;
 330     ++NumTailDups;
 331   }
 332
 333   // If TailBB was duplicated into all its predecessors except for the prior
 334   // block, which falls through unconditionally, move the contents of this
 335   // block into the prior block.
 336   MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(TailBB));
 337   MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
 338   SmallVector<MachineOperand, 4> PriorCond;
 339   bool PriorUnAnalyzable =
 340     TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
 341   // This has to check PrevBB->succ_size() because EH edges are ignored by
 342   // AnalyzeBranch.
 343   if (!PriorUnAnalyzable && PriorCond.empty() && !PriorTBB &&
 344       TailBB->pred_size() == 1 && PrevBB.succ_size() == 1 &&
 345       !TailBB->hasAddressTaken()) {
 346     DEBUG(errs() << "\nMerging into block: " << PrevBB
 347           << "From MBB: " << *TailBB);
 348     PrevBB.splice(PrevBB.end(), TailBB, TailBB->begin(), TailBB->end());
 349     PrevBB.removeSuccessor(PrevBB.succ_begin());;
 350     assert(PrevBB.succ_empty());
 351     PrevBB.transferSuccessors(TailBB);
 352     Changed = true;
 353   }
 354
 355   return Changed;
 356 }
 357
 358 /// RemoveDeadBlock - Remove the specified dead machine basic block from the
 359 /// function, updating the CFG.
 360 void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) {
 361   assert(MBB->pred_empty() && "MBB must be dead!");
 362   DEBUG(errs() << "\nRemoving MBB: " << *MBB);
 363
 364   // Remove all successors.
 365   while (!MBB->succ_empty())
 366     MBB->removeSuccessor(MBB->succ_end()-1);
 367
 368   // If there are any labels in the basic block, unregister them from
 369   // MachineModuleInfo.
 370   if (MMI && !MBB->empty()) {
 371     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
 372          I != E; ++I) {
 373       if (I->isLabel())
 374         // The label ID # is always operand #0, an immediate.
 375         MMI->InvalidateLabel(I->getOperand(0).getImm());
 376     }
 377   }
 378
 379   // Remove the block.
 380   MBB->eraseFromParent();
 381 }
 382