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