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