xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/IfConversion.cpp (revision 7ef62cebc2f965b0f640263e179276928885e33d)
1 //===- IfConversion.cpp - Machine code if conversion pass -----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the machine instruction level if-conversion pass, which
10 // tries to convert conditional branches into predicated instructions.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "BranchFolding.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/ScopeExit.h"
17 #include "llvm/ADT/SmallSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/SparseSet.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/ADT/iterator_range.h"
22 #include "llvm/Analysis/ProfileSummaryInfo.h"
23 #include "llvm/CodeGen/LivePhysRegs.h"
24 #include "llvm/CodeGen/MBFIWrapper.h"
25 #include "llvm/CodeGen/MachineBasicBlock.h"
26 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
27 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
28 #include "llvm/CodeGen/MachineFunction.h"
29 #include "llvm/CodeGen/MachineFunctionPass.h"
30 #include "llvm/CodeGen/MachineInstr.h"
31 #include "llvm/CodeGen/MachineInstrBuilder.h"
32 #include "llvm/CodeGen/MachineOperand.h"
33 #include "llvm/CodeGen/MachineRegisterInfo.h"
34 #include "llvm/CodeGen/TargetInstrInfo.h"
35 #include "llvm/CodeGen/TargetLowering.h"
36 #include "llvm/CodeGen/TargetRegisterInfo.h"
37 #include "llvm/CodeGen/TargetSchedule.h"
38 #include "llvm/CodeGen/TargetSubtargetInfo.h"
39 #include "llvm/IR/DebugLoc.h"
40 #include "llvm/InitializePasses.h"
41 #include "llvm/MC/MCRegisterInfo.h"
42 #include "llvm/Pass.h"
43 #include "llvm/Support/BranchProbability.h"
44 #include "llvm/Support/CommandLine.h"
45 #include "llvm/Support/Debug.h"
46 #include "llvm/Support/ErrorHandling.h"
47 #include "llvm/Support/raw_ostream.h"
48 #include <algorithm>
49 #include <cassert>
50 #include <functional>
51 #include <iterator>
52 #include <memory>
53 #include <utility>
54 #include <vector>
55 
56 using namespace llvm;
57 
58 #define DEBUG_TYPE "if-converter"
59 
60 // Hidden options for help debugging.
61 static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);
62 static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);
63 static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden);
64 static cl::opt<bool> DisableSimple("disable-ifcvt-simple",
65                                    cl::init(false), cl::Hidden);
66 static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false",
67                                     cl::init(false), cl::Hidden);
68 static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle",
69                                      cl::init(false), cl::Hidden);
70 static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev",
71                                       cl::init(false), cl::Hidden);
72 static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false",
73                                       cl::init(false), cl::Hidden);
74 static cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev",
75                                        cl::init(false), cl::Hidden);
76 static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond",
77                                     cl::init(false), cl::Hidden);
78 static cl::opt<bool> DisableForkedDiamond("disable-ifcvt-forked-diamond",
79                                         cl::init(false), cl::Hidden);
80 static cl::opt<bool> IfCvtBranchFold("ifcvt-branch-fold",
81                                      cl::init(true), cl::Hidden);
82 
83 STATISTIC(NumSimple,       "Number of simple if-conversions performed");
84 STATISTIC(NumSimpleFalse,  "Number of simple (F) if-conversions performed");
85 STATISTIC(NumTriangle,     "Number of triangle if-conversions performed");
86 STATISTIC(NumTriangleRev,  "Number of triangle (R) if-conversions performed");
87 STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed");
88 STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed");
89 STATISTIC(NumDiamonds,     "Number of diamond if-conversions performed");
90 STATISTIC(NumForkedDiamonds, "Number of forked-diamond if-conversions performed");
91 STATISTIC(NumIfConvBBs,    "Number of if-converted blocks");
92 STATISTIC(NumDupBBs,       "Number of duplicated blocks");
93 STATISTIC(NumUnpred,       "Number of true blocks of diamonds unpredicated");
94 
95 namespace {
96 
97   class IfConverter : public MachineFunctionPass {
98     enum IfcvtKind {
99       ICNotClassfied,  // BB data valid, but not classified.
100       ICSimpleFalse,   // Same as ICSimple, but on the false path.
101       ICSimple,        // BB is entry of an one split, no rejoin sub-CFG.
102       ICTriangleFRev,  // Same as ICTriangleFalse, but false path rev condition.
103       ICTriangleRev,   // Same as ICTriangle, but true path rev condition.
104       ICTriangleFalse, // Same as ICTriangle, but on the false path.
105       ICTriangle,      // BB is entry of a triangle sub-CFG.
106       ICDiamond,       // BB is entry of a diamond sub-CFG.
107       ICForkedDiamond  // BB is entry of an almost diamond sub-CFG, with a
108                        // common tail that can be shared.
109     };
110 
111     /// One per MachineBasicBlock, this is used to cache the result
112     /// if-conversion feasibility analysis. This includes results from
113     /// TargetInstrInfo::analyzeBranch() (i.e. TBB, FBB, and Cond), and its
114     /// classification, and common tail block of its successors (if it's a
115     /// diamond shape), its size, whether it's predicable, and whether any
116     /// instruction can clobber the 'would-be' predicate.
117     ///
118     /// IsDone          - True if BB is not to be considered for ifcvt.
119     /// IsBeingAnalyzed - True if BB is currently being analyzed.
120     /// IsAnalyzed      - True if BB has been analyzed (info is still valid).
121     /// IsEnqueued      - True if BB has been enqueued to be ifcvt'ed.
122     /// IsBrAnalyzable  - True if analyzeBranch() returns false.
123     /// HasFallThrough  - True if BB may fallthrough to the following BB.
124     /// IsUnpredicable  - True if BB is known to be unpredicable.
125     /// ClobbersPred    - True if BB could modify predicates (e.g. has
126     ///                   cmp, call, etc.)
127     /// NonPredSize     - Number of non-predicated instructions.
128     /// ExtraCost       - Extra cost for multi-cycle instructions.
129     /// ExtraCost2      - Some instructions are slower when predicated
130     /// BB              - Corresponding MachineBasicBlock.
131     /// TrueBB / FalseBB- See analyzeBranch().
132     /// BrCond          - Conditions for end of block conditional branches.
133     /// Predicate       - Predicate used in the BB.
134     struct BBInfo {
135       bool IsDone          : 1;
136       bool IsBeingAnalyzed : 1;
137       bool IsAnalyzed      : 1;
138       bool IsEnqueued      : 1;
139       bool IsBrAnalyzable  : 1;
140       bool IsBrReversible  : 1;
141       bool HasFallThrough  : 1;
142       bool IsUnpredicable  : 1;
143       bool CannotBeCopied  : 1;
144       bool ClobbersPred    : 1;
145       unsigned NonPredSize = 0;
146       unsigned ExtraCost = 0;
147       unsigned ExtraCost2 = 0;
148       MachineBasicBlock *BB = nullptr;
149       MachineBasicBlock *TrueBB = nullptr;
150       MachineBasicBlock *FalseBB = nullptr;
151       SmallVector<MachineOperand, 4> BrCond;
152       SmallVector<MachineOperand, 4> Predicate;
153 
154       BBInfo() : IsDone(false), IsBeingAnalyzed(false),
155                  IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false),
156                  IsBrReversible(false), HasFallThrough(false),
157                  IsUnpredicable(false), CannotBeCopied(false),
158                  ClobbersPred(false) {}
159     };
160 
161     /// Record information about pending if-conversions to attempt:
162     /// BBI             - Corresponding BBInfo.
163     /// Kind            - Type of block. See IfcvtKind.
164     /// NeedSubsumption - True if the to-be-predicated BB has already been
165     ///                   predicated.
166     /// NumDups      - Number of instructions that would be duplicated due
167     ///                   to this if-conversion. (For diamonds, the number of
168     ///                   identical instructions at the beginnings of both
169     ///                   paths).
170     /// NumDups2     - For diamonds, the number of identical instructions
171     ///                   at the ends of both paths.
172     struct IfcvtToken {
173       BBInfo &BBI;
174       IfcvtKind Kind;
175       unsigned NumDups;
176       unsigned NumDups2;
177       bool NeedSubsumption : 1;
178       bool TClobbersPred : 1;
179       bool FClobbersPred : 1;
180 
181       IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0,
182                  bool tc = false, bool fc = false)
183         : BBI(b), Kind(k), NumDups(d), NumDups2(d2), NeedSubsumption(s),
184           TClobbersPred(tc), FClobbersPred(fc) {}
185     };
186 
187     /// Results of if-conversion feasibility analysis indexed by basic block
188     /// number.
189     std::vector<BBInfo> BBAnalysis;
190     TargetSchedModel SchedModel;
191 
192     const TargetLoweringBase *TLI;
193     const TargetInstrInfo *TII;
194     const TargetRegisterInfo *TRI;
195     const MachineBranchProbabilityInfo *MBPI;
196     MachineRegisterInfo *MRI;
197 
198     LivePhysRegs Redefs;
199 
200     bool PreRegAlloc;
201     bool MadeChange;
202     int FnNum = -1;
203     std::function<bool(const MachineFunction &)> PredicateFtor;
204 
205   public:
206     static char ID;
207 
208     IfConverter(std::function<bool(const MachineFunction &)> Ftor = nullptr)
209         : MachineFunctionPass(ID), PredicateFtor(std::move(Ftor)) {
210       initializeIfConverterPass(*PassRegistry::getPassRegistry());
211     }
212 
213     void getAnalysisUsage(AnalysisUsage &AU) const override {
214       AU.addRequired<MachineBlockFrequencyInfo>();
215       AU.addRequired<MachineBranchProbabilityInfo>();
216       AU.addRequired<ProfileSummaryInfoWrapperPass>();
217       MachineFunctionPass::getAnalysisUsage(AU);
218     }
219 
220     bool runOnMachineFunction(MachineFunction &MF) override;
221 
222     MachineFunctionProperties getRequiredProperties() const override {
223       return MachineFunctionProperties().set(
224           MachineFunctionProperties::Property::NoVRegs);
225     }
226 
227   private:
228     bool reverseBranchCondition(BBInfo &BBI) const;
229     bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups,
230                      BranchProbability Prediction) const;
231     bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
232                        bool FalseBranch, unsigned &Dups,
233                        BranchProbability Prediction) const;
234     bool CountDuplicatedInstructions(
235         MachineBasicBlock::iterator &TIB, MachineBasicBlock::iterator &FIB,
236         MachineBasicBlock::iterator &TIE, MachineBasicBlock::iterator &FIE,
237         unsigned &Dups1, unsigned &Dups2,
238         MachineBasicBlock &TBB, MachineBasicBlock &FBB,
239         bool SkipUnconditionalBranches) const;
240     bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
241                       unsigned &Dups1, unsigned &Dups2,
242                       BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const;
243     bool ValidForkedDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
244                             unsigned &Dups1, unsigned &Dups2,
245                             BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const;
246     void AnalyzeBranches(BBInfo &BBI);
247     void ScanInstructions(BBInfo &BBI,
248                           MachineBasicBlock::iterator &Begin,
249                           MachineBasicBlock::iterator &End,
250                           bool BranchUnpredicable = false) const;
251     bool RescanInstructions(
252         MachineBasicBlock::iterator &TIB, MachineBasicBlock::iterator &FIB,
253         MachineBasicBlock::iterator &TIE, MachineBasicBlock::iterator &FIE,
254         BBInfo &TrueBBI, BBInfo &FalseBBI) const;
255     void AnalyzeBlock(MachineBasicBlock &MBB,
256                       std::vector<std::unique_ptr<IfcvtToken>> &Tokens);
257     bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Pred,
258                              bool isTriangle = false, bool RevBranch = false,
259                              bool hasCommonTail = false);
260     void AnalyzeBlocks(MachineFunction &MF,
261                        std::vector<std::unique_ptr<IfcvtToken>> &Tokens);
262     void InvalidatePreds(MachineBasicBlock &MBB);
263     bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);
264     bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind);
265     bool IfConvertDiamondCommon(BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,
266                                 unsigned NumDups1, unsigned NumDups2,
267                                 bool TClobbersPred, bool FClobbersPred,
268                                 bool RemoveBranch, bool MergeAddEdges);
269     bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
270                           unsigned NumDups1, unsigned NumDups2,
271                           bool TClobbers, bool FClobbers);
272     bool IfConvertForkedDiamond(BBInfo &BBI, IfcvtKind Kind,
273                               unsigned NumDups1, unsigned NumDups2,
274                               bool TClobbers, bool FClobbers);
275     void PredicateBlock(BBInfo &BBI,
276                         MachineBasicBlock::iterator E,
277                         SmallVectorImpl<MachineOperand> &Cond,
278                         SmallSet<MCPhysReg, 4> *LaterRedefs = nullptr);
279     void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
280                                SmallVectorImpl<MachineOperand> &Cond,
281                                bool IgnoreBr = false);
282     void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges = true);
283 
284     bool MeetIfcvtSizeLimit(MachineBasicBlock &BB,
285                             unsigned Cycle, unsigned Extra,
286                             BranchProbability Prediction) const {
287       return Cycle > 0 && TII->isProfitableToIfCvt(BB, Cycle, Extra,
288                                                    Prediction);
289     }
290 
291     bool MeetIfcvtSizeLimit(BBInfo &TBBInfo, BBInfo &FBBInfo,
292                             MachineBasicBlock &CommBB, unsigned Dups,
293                             BranchProbability Prediction, bool Forked) const {
294       const MachineFunction &MF = *TBBInfo.BB->getParent();
295       if (MF.getFunction().hasMinSize()) {
296         MachineBasicBlock::iterator TIB = TBBInfo.BB->begin();
297         MachineBasicBlock::iterator FIB = FBBInfo.BB->begin();
298         MachineBasicBlock::iterator TIE = TBBInfo.BB->end();
299         MachineBasicBlock::iterator FIE = FBBInfo.BB->end();
300 
301         unsigned Dups1 = 0, Dups2 = 0;
302         if (!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
303                                          *TBBInfo.BB, *FBBInfo.BB,
304                                          /*SkipUnconditionalBranches*/ true))
305           llvm_unreachable("should already have been checked by ValidDiamond");
306 
307         unsigned BranchBytes = 0;
308         unsigned CommonBytes = 0;
309 
310         // Count common instructions at the start of the true and false blocks.
311         for (auto &I : make_range(TBBInfo.BB->begin(), TIB)) {
312           LLVM_DEBUG(dbgs() << "Common inst: " << I);
313           CommonBytes += TII->getInstSizeInBytes(I);
314         }
315         for (auto &I : make_range(FBBInfo.BB->begin(), FIB)) {
316           LLVM_DEBUG(dbgs() << "Common inst: " << I);
317           CommonBytes += TII->getInstSizeInBytes(I);
318         }
319 
320         // Count instructions at the end of the true and false blocks, after
321         // the ones we plan to predicate. Analyzable branches will be removed
322         // (unless this is a forked diamond), and all other instructions are
323         // common between the two blocks.
324         for (auto &I : make_range(TIE, TBBInfo.BB->end())) {
325           if (I.isBranch() && TBBInfo.IsBrAnalyzable && !Forked) {
326             LLVM_DEBUG(dbgs() << "Saving branch: " << I);
327             BranchBytes += TII->predictBranchSizeForIfCvt(I);
328           } else {
329             LLVM_DEBUG(dbgs() << "Common inst: " << I);
330             CommonBytes += TII->getInstSizeInBytes(I);
331           }
332         }
333         for (auto &I : make_range(FIE, FBBInfo.BB->end())) {
334           if (I.isBranch() && FBBInfo.IsBrAnalyzable && !Forked) {
335             LLVM_DEBUG(dbgs() << "Saving branch: " << I);
336             BranchBytes += TII->predictBranchSizeForIfCvt(I);
337           } else {
338             LLVM_DEBUG(dbgs() << "Common inst: " << I);
339             CommonBytes += TII->getInstSizeInBytes(I);
340           }
341         }
342         for (auto &I : CommBB.terminators()) {
343           if (I.isBranch()) {
344             LLVM_DEBUG(dbgs() << "Saving branch: " << I);
345             BranchBytes += TII->predictBranchSizeForIfCvt(I);
346           }
347         }
348 
349         // The common instructions in one branch will be eliminated, halving
350         // their code size.
351         CommonBytes /= 2;
352 
353         // Count the instructions which we need to predicate.
354         unsigned NumPredicatedInstructions = 0;
355         for (auto &I : make_range(TIB, TIE)) {
356           if (!I.isDebugInstr()) {
357             LLVM_DEBUG(dbgs() << "Predicating: " << I);
358             NumPredicatedInstructions++;
359           }
360         }
361         for (auto &I : make_range(FIB, FIE)) {
362           if (!I.isDebugInstr()) {
363             LLVM_DEBUG(dbgs() << "Predicating: " << I);
364             NumPredicatedInstructions++;
365           }
366         }
367 
368         // Even though we're optimising for size at the expense of performance,
369         // avoid creating really long predicated blocks.
370         if (NumPredicatedInstructions > 15)
371           return false;
372 
373         // Some targets (e.g. Thumb2) need to insert extra instructions to
374         // start predicated blocks.
375         unsigned ExtraPredicateBytes = TII->extraSizeToPredicateInstructions(
376             MF, NumPredicatedInstructions);
377 
378         LLVM_DEBUG(dbgs() << "MeetIfcvtSizeLimit(BranchBytes=" << BranchBytes
379                           << ", CommonBytes=" << CommonBytes
380                           << ", NumPredicatedInstructions="
381                           << NumPredicatedInstructions
382                           << ", ExtraPredicateBytes=" << ExtraPredicateBytes
383                           << ")\n");
384         return (BranchBytes + CommonBytes) > ExtraPredicateBytes;
385       } else {
386         unsigned TCycle = TBBInfo.NonPredSize + TBBInfo.ExtraCost - Dups;
387         unsigned FCycle = FBBInfo.NonPredSize + FBBInfo.ExtraCost - Dups;
388         bool Res = TCycle > 0 && FCycle > 0 &&
389                    TII->isProfitableToIfCvt(
390                        *TBBInfo.BB, TCycle, TBBInfo.ExtraCost2, *FBBInfo.BB,
391                        FCycle, FBBInfo.ExtraCost2, Prediction);
392         LLVM_DEBUG(dbgs() << "MeetIfcvtSizeLimit(TCycle=" << TCycle
393                           << ", FCycle=" << FCycle
394                           << ", TExtra=" << TBBInfo.ExtraCost2 << ", FExtra="
395                           << FBBInfo.ExtraCost2 << ") = " << Res << "\n");
396         return Res;
397       }
398     }
399 
400     /// Returns true if Block ends without a terminator.
401     bool blockAlwaysFallThrough(BBInfo &BBI) const {
402       return BBI.IsBrAnalyzable && BBI.TrueBB == nullptr;
403     }
404 
405     /// Used to sort if-conversion candidates.
406     static bool IfcvtTokenCmp(const std::unique_ptr<IfcvtToken> &C1,
407                               const std::unique_ptr<IfcvtToken> &C2) {
408       int Incr1 = (C1->Kind == ICDiamond)
409         ? -(int)(C1->NumDups + C1->NumDups2) : (int)C1->NumDups;
410       int Incr2 = (C2->Kind == ICDiamond)
411         ? -(int)(C2->NumDups + C2->NumDups2) : (int)C2->NumDups;
412       if (Incr1 > Incr2)
413         return true;
414       else if (Incr1 == Incr2) {
415         // Favors subsumption.
416         if (!C1->NeedSubsumption && C2->NeedSubsumption)
417           return true;
418         else if (C1->NeedSubsumption == C2->NeedSubsumption) {
419           // Favors diamond over triangle, etc.
420           if ((unsigned)C1->Kind < (unsigned)C2->Kind)
421             return true;
422           else if (C1->Kind == C2->Kind)
423             return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber();
424         }
425       }
426       return false;
427     }
428   };
429 
430 } // end anonymous namespace
431 
432 char IfConverter::ID = 0;
433 
434 char &llvm::IfConverterID = IfConverter::ID;
435 
436 INITIALIZE_PASS_BEGIN(IfConverter, DEBUG_TYPE, "If Converter", false, false)
437 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
438 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
439 INITIALIZE_PASS_END(IfConverter, DEBUG_TYPE, "If Converter", false, false)
440 
441 bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
442   if (skipFunction(MF.getFunction()) || (PredicateFtor && !PredicateFtor(MF)))
443     return false;
444 
445   const TargetSubtargetInfo &ST = MF.getSubtarget();
446   TLI = ST.getTargetLowering();
447   TII = ST.getInstrInfo();
448   TRI = ST.getRegisterInfo();
449   MBFIWrapper MBFI(getAnalysis<MachineBlockFrequencyInfo>());
450   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
451   ProfileSummaryInfo *PSI =
452       &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
453   MRI = &MF.getRegInfo();
454   SchedModel.init(&ST);
455 
456   if (!TII) return false;
457 
458   PreRegAlloc = MRI->isSSA();
459 
460   bool BFChange = false;
461   if (!PreRegAlloc) {
462     // Tail merge tend to expose more if-conversion opportunities.
463     BranchFolder BF(true, false, MBFI, *MBPI, PSI);
464     BFChange = BF.OptimizeFunction(MF, TII, ST.getRegisterInfo());
465   }
466 
467   LLVM_DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum << ") \'"
468                     << MF.getName() << "\'");
469 
470   if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) {
471     LLVM_DEBUG(dbgs() << " skipped\n");
472     return false;
473   }
474   LLVM_DEBUG(dbgs() << "\n");
475 
476   MF.RenumberBlocks();
477   BBAnalysis.resize(MF.getNumBlockIDs());
478 
479   std::vector<std::unique_ptr<IfcvtToken>> Tokens;
480   MadeChange = false;
481   unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +
482     NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;
483   while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) {
484     // Do an initial analysis for each basic block and find all the potential
485     // candidates to perform if-conversion.
486     bool Change = false;
487     AnalyzeBlocks(MF, Tokens);
488     while (!Tokens.empty()) {
489       std::unique_ptr<IfcvtToken> Token = std::move(Tokens.back());
490       Tokens.pop_back();
491       BBInfo &BBI = Token->BBI;
492       IfcvtKind Kind = Token->Kind;
493       unsigned NumDups = Token->NumDups;
494       unsigned NumDups2 = Token->NumDups2;
495 
496       // If the block has been evicted out of the queue or it has already been
497       // marked dead (due to it being predicated), then skip it.
498       if (BBI.IsDone)
499         BBI.IsEnqueued = false;
500       if (!BBI.IsEnqueued)
501         continue;
502 
503       BBI.IsEnqueued = false;
504 
505       bool RetVal = false;
506       switch (Kind) {
507       default: llvm_unreachable("Unexpected!");
508       case ICSimple:
509       case ICSimpleFalse: {
510         bool isFalse = Kind == ICSimpleFalse;
511         if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break;
512         LLVM_DEBUG(dbgs() << "Ifcvt (Simple"
513                           << (Kind == ICSimpleFalse ? " false" : "")
514                           << "): " << printMBBReference(*BBI.BB) << " ("
515                           << ((Kind == ICSimpleFalse) ? BBI.FalseBB->getNumber()
516                                                       : BBI.TrueBB->getNumber())
517                           << ") ");
518         RetVal = IfConvertSimple(BBI, Kind);
519         LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
520         if (RetVal) {
521           if (isFalse) ++NumSimpleFalse;
522           else         ++NumSimple;
523         }
524        break;
525       }
526       case ICTriangle:
527       case ICTriangleRev:
528       case ICTriangleFalse:
529       case ICTriangleFRev: {
530         bool isFalse = Kind == ICTriangleFalse;
531         bool isRev   = (Kind == ICTriangleRev || Kind == ICTriangleFRev);
532         if (DisableTriangle && !isFalse && !isRev) break;
533         if (DisableTriangleR && !isFalse && isRev) break;
534         if (DisableTriangleF && isFalse && !isRev) break;
535         if (DisableTriangleFR && isFalse && isRev) break;
536         LLVM_DEBUG(dbgs() << "Ifcvt (Triangle");
537         if (isFalse)
538           LLVM_DEBUG(dbgs() << " false");
539         if (isRev)
540           LLVM_DEBUG(dbgs() << " rev");
541         LLVM_DEBUG(dbgs() << "): " << printMBBReference(*BBI.BB)
542                           << " (T:" << BBI.TrueBB->getNumber()
543                           << ",F:" << BBI.FalseBB->getNumber() << ") ");
544         RetVal = IfConvertTriangle(BBI, Kind);
545         LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
546         if (RetVal) {
547           if (isFalse) {
548             if (isRev) ++NumTriangleFRev;
549             else       ++NumTriangleFalse;
550           } else {
551             if (isRev) ++NumTriangleRev;
552             else       ++NumTriangle;
553           }
554         }
555         break;
556       }
557       case ICDiamond:
558         if (DisableDiamond) break;
559         LLVM_DEBUG(dbgs() << "Ifcvt (Diamond): " << printMBBReference(*BBI.BB)
560                           << " (T:" << BBI.TrueBB->getNumber()
561                           << ",F:" << BBI.FalseBB->getNumber() << ") ");
562         RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2,
563                                   Token->TClobbersPred,
564                                   Token->FClobbersPred);
565         LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
566         if (RetVal) ++NumDiamonds;
567         break;
568       case ICForkedDiamond:
569         if (DisableForkedDiamond) break;
570         LLVM_DEBUG(dbgs() << "Ifcvt (Forked Diamond): "
571                           << printMBBReference(*BBI.BB)
572                           << " (T:" << BBI.TrueBB->getNumber()
573                           << ",F:" << BBI.FalseBB->getNumber() << ") ");
574         RetVal = IfConvertForkedDiamond(BBI, Kind, NumDups, NumDups2,
575                                       Token->TClobbersPred,
576                                       Token->FClobbersPred);
577         LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
578         if (RetVal) ++NumForkedDiamonds;
579         break;
580       }
581 
582       if (RetVal && MRI->tracksLiveness())
583         recomputeLivenessFlags(*BBI.BB);
584 
585       Change |= RetVal;
586 
587       NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +
588         NumTriangleFalse + NumTriangleFRev + NumDiamonds;
589       if (IfCvtLimit != -1 && (int)NumIfCvts >= IfCvtLimit)
590         break;
591     }
592 
593     if (!Change)
594       break;
595     MadeChange |= Change;
596   }
597 
598   Tokens.clear();
599   BBAnalysis.clear();
600 
601   if (MadeChange && IfCvtBranchFold) {
602     BranchFolder BF(false, false, MBFI, *MBPI, PSI);
603     BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo());
604   }
605 
606   MadeChange |= BFChange;
607   return MadeChange;
608 }
609 
610 /// BB has a fallthrough. Find its 'false' successor given its 'true' successor.
611 static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
612                                          MachineBasicBlock *TrueBB) {
613   for (MachineBasicBlock *SuccBB : BB->successors()) {
614     if (SuccBB != TrueBB)
615       return SuccBB;
616   }
617   return nullptr;
618 }
619 
620 /// Reverse the condition of the end of the block branch. Swap block's 'true'
621 /// and 'false' successors.
622 bool IfConverter::reverseBranchCondition(BBInfo &BBI) const {
623   DebugLoc dl;  // FIXME: this is nowhere
624   if (!TII->reverseBranchCondition(BBI.BrCond)) {
625     TII->removeBranch(*BBI.BB);
626     TII->insertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond, dl);
627     std::swap(BBI.TrueBB, BBI.FalseBB);
628     return true;
629   }
630   return false;
631 }
632 
633 /// Returns the next block in the function blocks ordering. If it is the end,
634 /// returns NULL.
635 static inline MachineBasicBlock *getNextBlock(MachineBasicBlock &MBB) {
636   MachineFunction::iterator I = MBB.getIterator();
637   MachineFunction::iterator E = MBB.getParent()->end();
638   if (++I == E)
639     return nullptr;
640   return &*I;
641 }
642 
643 /// Returns true if the 'true' block (along with its predecessor) forms a valid
644 /// simple shape for ifcvt. It also returns the number of instructions that the
645 /// ifcvt would need to duplicate if performed in Dups.
646 bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups,
647                               BranchProbability Prediction) const {
648   Dups = 0;
649   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
650     return false;
651 
652   if (TrueBBI.IsBrAnalyzable)
653     return false;
654 
655   if (TrueBBI.BB->pred_size() > 1) {
656     if (TrueBBI.CannotBeCopied ||
657         !TII->isProfitableToDupForIfCvt(*TrueBBI.BB, TrueBBI.NonPredSize,
658                                         Prediction))
659       return false;
660     Dups = TrueBBI.NonPredSize;
661   }
662 
663   return true;
664 }
665 
666 /// Returns true if the 'true' and 'false' blocks (along with their common
667 /// predecessor) forms a valid triangle shape for ifcvt. If 'FalseBranch' is
668 /// true, it checks if 'true' block's false branch branches to the 'false' block
669 /// rather than the other way around. It also returns the number of instructions
670 /// that the ifcvt would need to duplicate if performed in 'Dups'.
671 bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
672                                 bool FalseBranch, unsigned &Dups,
673                                 BranchProbability Prediction) const {
674   Dups = 0;
675   if (TrueBBI.BB == FalseBBI.BB)
676     return false;
677 
678   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
679     return false;
680 
681   if (TrueBBI.BB->pred_size() > 1) {
682     if (TrueBBI.CannotBeCopied)
683       return false;
684 
685     unsigned Size = TrueBBI.NonPredSize;
686     if (TrueBBI.IsBrAnalyzable) {
687       if (TrueBBI.TrueBB && TrueBBI.BrCond.empty())
688         // Ends with an unconditional branch. It will be removed.
689         --Size;
690       else {
691         MachineBasicBlock *FExit = FalseBranch
692           ? TrueBBI.TrueBB : TrueBBI.FalseBB;
693         if (FExit)
694           // Require a conditional branch
695           ++Size;
696       }
697     }
698     if (!TII->isProfitableToDupForIfCvt(*TrueBBI.BB, Size, Prediction))
699       return false;
700     Dups = Size;
701   }
702 
703   MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB;
704   if (!TExit && blockAlwaysFallThrough(TrueBBI)) {
705     MachineFunction::iterator I = TrueBBI.BB->getIterator();
706     if (++I == TrueBBI.BB->getParent()->end())
707       return false;
708     TExit = &*I;
709   }
710   return TExit && TExit == FalseBBI.BB;
711 }
712 
713 /// Count duplicated instructions and move the iterators to show where they
714 /// are.
715 /// @param TIB True Iterator Begin
716 /// @param FIB False Iterator Begin
717 /// These two iterators initially point to the first instruction of the two
718 /// blocks, and finally point to the first non-shared instruction.
719 /// @param TIE True Iterator End
720 /// @param FIE False Iterator End
721 /// These two iterators initially point to End() for the two blocks() and
722 /// finally point to the first shared instruction in the tail.
723 /// Upon return [TIB, TIE), and [FIB, FIE) mark the un-duplicated portions of
724 /// two blocks.
725 /// @param Dups1 count of duplicated instructions at the beginning of the 2
726 /// blocks.
727 /// @param Dups2 count of duplicated instructions at the end of the 2 blocks.
728 /// @param SkipUnconditionalBranches if true, Don't make sure that
729 /// unconditional branches at the end of the blocks are the same. True is
730 /// passed when the blocks are analyzable to allow for fallthrough to be
731 /// handled.
732 /// @return false if the shared portion prevents if conversion.
733 bool IfConverter::CountDuplicatedInstructions(
734     MachineBasicBlock::iterator &TIB,
735     MachineBasicBlock::iterator &FIB,
736     MachineBasicBlock::iterator &TIE,
737     MachineBasicBlock::iterator &FIE,
738     unsigned &Dups1, unsigned &Dups2,
739     MachineBasicBlock &TBB, MachineBasicBlock &FBB,
740     bool SkipUnconditionalBranches) const {
741   while (TIB != TIE && FIB != FIE) {
742     // Skip dbg_value instructions. These do not count.
743     TIB = skipDebugInstructionsForward(TIB, TIE, false);
744     FIB = skipDebugInstructionsForward(FIB, FIE, false);
745     if (TIB == TIE || FIB == FIE)
746       break;
747     if (!TIB->isIdenticalTo(*FIB))
748       break;
749     // A pred-clobbering instruction in the shared portion prevents
750     // if-conversion.
751     std::vector<MachineOperand> PredDefs;
752     if (TII->ClobbersPredicate(*TIB, PredDefs, false))
753       return false;
754     // If we get all the way to the branch instructions, don't count them.
755     if (!TIB->isBranch())
756       ++Dups1;
757     ++TIB;
758     ++FIB;
759   }
760 
761   // Check for already containing all of the block.
762   if (TIB == TIE || FIB == FIE)
763     return true;
764   // Now, in preparation for counting duplicate instructions at the ends of the
765   // blocks, switch to reverse_iterators. Note that getReverse() returns an
766   // iterator that points to the same instruction, unlike std::reverse_iterator.
767   // We have to do our own shifting so that we get the same range.
768   MachineBasicBlock::reverse_iterator RTIE = std::next(TIE.getReverse());
769   MachineBasicBlock::reverse_iterator RFIE = std::next(FIE.getReverse());
770   const MachineBasicBlock::reverse_iterator RTIB = std::next(TIB.getReverse());
771   const MachineBasicBlock::reverse_iterator RFIB = std::next(FIB.getReverse());
772 
773   if (!TBB.succ_empty() || !FBB.succ_empty()) {
774     if (SkipUnconditionalBranches) {
775       while (RTIE != RTIB && RTIE->isUnconditionalBranch())
776         ++RTIE;
777       while (RFIE != RFIB && RFIE->isUnconditionalBranch())
778         ++RFIE;
779     }
780   }
781 
782   // Count duplicate instructions at the ends of the blocks.
783   while (RTIE != RTIB && RFIE != RFIB) {
784     // Skip dbg_value instructions. These do not count.
785     // Note that these are reverse iterators going forward.
786     RTIE = skipDebugInstructionsForward(RTIE, RTIB, false);
787     RFIE = skipDebugInstructionsForward(RFIE, RFIB, false);
788     if (RTIE == RTIB || RFIE == RFIB)
789       break;
790     if (!RTIE->isIdenticalTo(*RFIE))
791       break;
792     // We have to verify that any branch instructions are the same, and then we
793     // don't count them toward the # of duplicate instructions.
794     if (!RTIE->isBranch())
795       ++Dups2;
796     ++RTIE;
797     ++RFIE;
798   }
799   TIE = std::next(RTIE.getReverse());
800   FIE = std::next(RFIE.getReverse());
801   return true;
802 }
803 
804 /// RescanInstructions - Run ScanInstructions on a pair of blocks.
805 /// @param TIB - True Iterator Begin, points to first non-shared instruction
806 /// @param FIB - False Iterator Begin, points to first non-shared instruction
807 /// @param TIE - True Iterator End, points past last non-shared instruction
808 /// @param FIE - False Iterator End, points past last non-shared instruction
809 /// @param TrueBBI  - BBInfo to update for the true block.
810 /// @param FalseBBI - BBInfo to update for the false block.
811 /// @returns - false if either block cannot be predicated or if both blocks end
812 ///   with a predicate-clobbering instruction.
813 bool IfConverter::RescanInstructions(
814     MachineBasicBlock::iterator &TIB, MachineBasicBlock::iterator &FIB,
815     MachineBasicBlock::iterator &TIE, MachineBasicBlock::iterator &FIE,
816     BBInfo &TrueBBI, BBInfo &FalseBBI) const {
817   bool BranchUnpredicable = true;
818   TrueBBI.IsUnpredicable = FalseBBI.IsUnpredicable = false;
819   ScanInstructions(TrueBBI, TIB, TIE, BranchUnpredicable);
820   if (TrueBBI.IsUnpredicable)
821     return false;
822   ScanInstructions(FalseBBI, FIB, FIE, BranchUnpredicable);
823   if (FalseBBI.IsUnpredicable)
824     return false;
825   if (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)
826     return false;
827   return true;
828 }
829 
830 #ifndef NDEBUG
831 static void verifySameBranchInstructions(
832     MachineBasicBlock *MBB1,
833     MachineBasicBlock *MBB2) {
834   const MachineBasicBlock::reverse_iterator B1 = MBB1->rend();
835   const MachineBasicBlock::reverse_iterator B2 = MBB2->rend();
836   MachineBasicBlock::reverse_iterator E1 = MBB1->rbegin();
837   MachineBasicBlock::reverse_iterator E2 = MBB2->rbegin();
838   while (E1 != B1 && E2 != B2) {
839     skipDebugInstructionsForward(E1, B1, false);
840     skipDebugInstructionsForward(E2, B2, false);
841     if (E1 == B1 && E2 == B2)
842       break;
843 
844     if (E1 == B1) {
845       assert(!E2->isBranch() && "Branch mis-match, one block is empty.");
846       break;
847     }
848     if (E2 == B2) {
849       assert(!E1->isBranch() && "Branch mis-match, one block is empty.");
850       break;
851     }
852 
853     if (E1->isBranch() || E2->isBranch())
854       assert(E1->isIdenticalTo(*E2) &&
855              "Branch mis-match, branch instructions don't match.");
856     else
857       break;
858     ++E1;
859     ++E2;
860   }
861 }
862 #endif
863 
864 /// ValidForkedDiamond - Returns true if the 'true' and 'false' blocks (along
865 /// with their common predecessor) form a diamond if a common tail block is
866 /// extracted.
867 /// While not strictly a diamond, this pattern would form a diamond if
868 /// tail-merging had merged the shared tails.
869 ///           EBB
870 ///         _/   \_
871 ///         |     |
872 ///        TBB   FBB
873 ///        /  \ /   \
874 ///  FalseBB TrueBB FalseBB
875 /// Currently only handles analyzable branches.
876 /// Specifically excludes actual diamonds to avoid overlap.
877 bool IfConverter::ValidForkedDiamond(
878     BBInfo &TrueBBI, BBInfo &FalseBBI,
879     unsigned &Dups1, unsigned &Dups2,
880     BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const {
881   Dups1 = Dups2 = 0;
882   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
883       FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
884     return false;
885 
886   if (!TrueBBI.IsBrAnalyzable || !FalseBBI.IsBrAnalyzable)
887     return false;
888   // Don't IfConvert blocks that can't be folded into their predecessor.
889   if  (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
890     return false;
891 
892   // This function is specifically looking for conditional tails, as
893   // unconditional tails are already handled by the standard diamond case.
894   if (TrueBBI.BrCond.size() == 0 ||
895       FalseBBI.BrCond.size() == 0)
896     return false;
897 
898   MachineBasicBlock *TT = TrueBBI.TrueBB;
899   MachineBasicBlock *TF = TrueBBI.FalseBB;
900   MachineBasicBlock *FT = FalseBBI.TrueBB;
901   MachineBasicBlock *FF = FalseBBI.FalseBB;
902 
903   if (!TT)
904     TT = getNextBlock(*TrueBBI.BB);
905   if (!TF)
906     TF = getNextBlock(*TrueBBI.BB);
907   if (!FT)
908     FT = getNextBlock(*FalseBBI.BB);
909   if (!FF)
910     FF = getNextBlock(*FalseBBI.BB);
911 
912   if (!TT || !TF)
913     return false;
914 
915   // Check successors. If they don't match, bail.
916   if (!((TT == FT && TF == FF) || (TF == FT && TT == FF)))
917     return false;
918 
919   bool FalseReversed = false;
920   if (TF == FT && TT == FF) {
921     // If the branches are opposing, but we can't reverse, don't do it.
922     if (!FalseBBI.IsBrReversible)
923       return false;
924     FalseReversed = true;
925     reverseBranchCondition(FalseBBI);
926   }
927   auto UnReverseOnExit = make_scope_exit([&]() {
928     if (FalseReversed)
929       reverseBranchCondition(FalseBBI);
930   });
931 
932   // Count duplicate instructions at the beginning of the true and false blocks.
933   MachineBasicBlock::iterator TIB = TrueBBI.BB->begin();
934   MachineBasicBlock::iterator FIB = FalseBBI.BB->begin();
935   MachineBasicBlock::iterator TIE = TrueBBI.BB->end();
936   MachineBasicBlock::iterator FIE = FalseBBI.BB->end();
937   if(!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
938                                   *TrueBBI.BB, *FalseBBI.BB,
939                                   /* SkipUnconditionalBranches */ true))
940     return false;
941 
942   TrueBBICalc.BB = TrueBBI.BB;
943   FalseBBICalc.BB = FalseBBI.BB;
944   TrueBBICalc.IsBrAnalyzable = TrueBBI.IsBrAnalyzable;
945   FalseBBICalc.IsBrAnalyzable = FalseBBI.IsBrAnalyzable;
946   if (!RescanInstructions(TIB, FIB, TIE, FIE, TrueBBICalc, FalseBBICalc))
947     return false;
948 
949   // The size is used to decide whether to if-convert, and the shared portions
950   // are subtracted off. Because of the subtraction, we just use the size that
951   // was calculated by the original ScanInstructions, as it is correct.
952   TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;
953   FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;
954   return true;
955 }
956 
957 /// ValidDiamond - Returns true if the 'true' and 'false' blocks (along
958 /// with their common predecessor) forms a valid diamond shape for ifcvt.
959 bool IfConverter::ValidDiamond(
960     BBInfo &TrueBBI, BBInfo &FalseBBI,
961     unsigned &Dups1, unsigned &Dups2,
962     BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const {
963   Dups1 = Dups2 = 0;
964   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
965       FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
966     return false;
967 
968   // If the True and False BBs are equal we're dealing with a degenerate case
969   // that we don't treat as a diamond.
970   if (TrueBBI.BB == FalseBBI.BB)
971     return false;
972 
973   MachineBasicBlock *TT = TrueBBI.TrueBB;
974   MachineBasicBlock *FT = FalseBBI.TrueBB;
975 
976   if (!TT && blockAlwaysFallThrough(TrueBBI))
977     TT = getNextBlock(*TrueBBI.BB);
978   if (!FT && blockAlwaysFallThrough(FalseBBI))
979     FT = getNextBlock(*FalseBBI.BB);
980   if (TT != FT)
981     return false;
982   if (!TT && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
983     return false;
984   if  (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
985     return false;
986 
987   // FIXME: Allow true block to have an early exit?
988   if (TrueBBI.FalseBB || FalseBBI.FalseBB)
989     return false;
990 
991   // Count duplicate instructions at the beginning and end of the true and
992   // false blocks.
993   // Skip unconditional branches only if we are considering an analyzable
994   // diamond. Otherwise the branches must be the same.
995   bool SkipUnconditionalBranches =
996       TrueBBI.IsBrAnalyzable && FalseBBI.IsBrAnalyzable;
997   MachineBasicBlock::iterator TIB = TrueBBI.BB->begin();
998   MachineBasicBlock::iterator FIB = FalseBBI.BB->begin();
999   MachineBasicBlock::iterator TIE = TrueBBI.BB->end();
1000   MachineBasicBlock::iterator FIE = FalseBBI.BB->end();
1001   if(!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
1002                                   *TrueBBI.BB, *FalseBBI.BB,
1003                                   SkipUnconditionalBranches))
1004     return false;
1005 
1006   TrueBBICalc.BB = TrueBBI.BB;
1007   FalseBBICalc.BB = FalseBBI.BB;
1008   TrueBBICalc.IsBrAnalyzable = TrueBBI.IsBrAnalyzable;
1009   FalseBBICalc.IsBrAnalyzable = FalseBBI.IsBrAnalyzable;
1010   if (!RescanInstructions(TIB, FIB, TIE, FIE, TrueBBICalc, FalseBBICalc))
1011     return false;
1012   // The size is used to decide whether to if-convert, and the shared portions
1013   // are subtracted off. Because of the subtraction, we just use the size that
1014   // was calculated by the original ScanInstructions, as it is correct.
1015   TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;
1016   FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;
1017   return true;
1018 }
1019 
1020 /// AnalyzeBranches - Look at the branches at the end of a block to determine if
1021 /// the block is predicable.
1022 void IfConverter::AnalyzeBranches(BBInfo &BBI) {
1023   if (BBI.IsDone)
1024     return;
1025 
1026   BBI.TrueBB = BBI.FalseBB = nullptr;
1027   BBI.BrCond.clear();
1028   BBI.IsBrAnalyzable =
1029       !TII->analyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
1030   if (!BBI.IsBrAnalyzable) {
1031     BBI.TrueBB = nullptr;
1032     BBI.FalseBB = nullptr;
1033     BBI.BrCond.clear();
1034   }
1035 
1036   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1037   BBI.IsBrReversible = (RevCond.size() == 0) ||
1038       !TII->reverseBranchCondition(RevCond);
1039   BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == nullptr;
1040 
1041   if (BBI.BrCond.size()) {
1042     // No false branch. This BB must end with a conditional branch and a
1043     // fallthrough.
1044     if (!BBI.FalseBB)
1045       BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB);
1046     if (!BBI.FalseBB) {
1047       // Malformed bcc? True and false blocks are the same?
1048       BBI.IsUnpredicable = true;
1049     }
1050   }
1051 }
1052 
1053 /// ScanInstructions - Scan all the instructions in the block to determine if
1054 /// the block is predicable. In most cases, that means all the instructions
1055 /// in the block are isPredicable(). Also checks if the block contains any
1056 /// instruction which can clobber a predicate (e.g. condition code register).
1057 /// If so, the block is not predicable unless it's the last instruction.
1058 void IfConverter::ScanInstructions(BBInfo &BBI,
1059                                    MachineBasicBlock::iterator &Begin,
1060                                    MachineBasicBlock::iterator &End,
1061                                    bool BranchUnpredicable) const {
1062   if (BBI.IsDone || BBI.IsUnpredicable)
1063     return;
1064 
1065   bool AlreadyPredicated = !BBI.Predicate.empty();
1066 
1067   BBI.NonPredSize = 0;
1068   BBI.ExtraCost = 0;
1069   BBI.ExtraCost2 = 0;
1070   BBI.ClobbersPred = false;
1071   for (MachineInstr &MI : make_range(Begin, End)) {
1072     if (MI.isDebugInstr())
1073       continue;
1074 
1075     // It's unsafe to duplicate convergent instructions in this context, so set
1076     // BBI.CannotBeCopied to true if MI is convergent.  To see why, consider the
1077     // following CFG, which is subject to our "simple" transformation.
1078     //
1079     //    BB0     // if (c1) goto BB1; else goto BB2;
1080     //   /   \
1081     //  BB1   |
1082     //   |   BB2  // if (c2) goto TBB; else goto FBB;
1083     //   |   / |
1084     //   |  /  |
1085     //   TBB   |
1086     //    |    |
1087     //    |   FBB
1088     //    |
1089     //    exit
1090     //
1091     // Suppose we want to move TBB's contents up into BB1 and BB2 (in BB1 they'd
1092     // be unconditional, and in BB2, they'd be predicated upon c2), and suppose
1093     // TBB contains a convergent instruction.  This is safe iff doing so does
1094     // not add a control-flow dependency to the convergent instruction -- i.e.,
1095     // it's safe iff the set of control flows that leads us to the convergent
1096     // instruction does not get smaller after the transformation.
1097     //
1098     // Originally we executed TBB if c1 || c2.  After the transformation, there
1099     // are two copies of TBB's instructions.  We get to the first if c1, and we
1100     // get to the second if !c1 && c2.
1101     //
1102     // There are clearly fewer ways to satisfy the condition "c1" than
1103     // "c1 || c2".  Since we've shrunk the set of control flows which lead to
1104     // our convergent instruction, the transformation is unsafe.
1105     if (MI.isNotDuplicable() || MI.isConvergent())
1106       BBI.CannotBeCopied = true;
1107 
1108     bool isPredicated = TII->isPredicated(MI);
1109     bool isCondBr = BBI.IsBrAnalyzable && MI.isConditionalBranch();
1110 
1111     if (BranchUnpredicable && MI.isBranch()) {
1112       BBI.IsUnpredicable = true;
1113       return;
1114     }
1115 
1116     // A conditional branch is not predicable, but it may be eliminated.
1117     if (isCondBr)
1118       continue;
1119 
1120     if (!isPredicated) {
1121       BBI.NonPredSize++;
1122       unsigned ExtraPredCost = TII->getPredicationCost(MI);
1123       unsigned NumCycles = SchedModel.computeInstrLatency(&MI, false);
1124       if (NumCycles > 1)
1125         BBI.ExtraCost += NumCycles-1;
1126       BBI.ExtraCost2 += ExtraPredCost;
1127     } else if (!AlreadyPredicated) {
1128       // FIXME: This instruction is already predicated before the
1129       // if-conversion pass. It's probably something like a conditional move.
1130       // Mark this block unpredicable for now.
1131       BBI.IsUnpredicable = true;
1132       return;
1133     }
1134 
1135     if (BBI.ClobbersPred && !isPredicated) {
1136       // Predicate modification instruction should end the block (except for
1137       // already predicated instructions and end of block branches).
1138       // Predicate may have been modified, the subsequent (currently)
1139       // unpredicated instructions cannot be correctly predicated.
1140       BBI.IsUnpredicable = true;
1141       return;
1142     }
1143 
1144     // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are
1145     // still potentially predicable.
1146     std::vector<MachineOperand> PredDefs;
1147     if (TII->ClobbersPredicate(MI, PredDefs, true))
1148       BBI.ClobbersPred = true;
1149 
1150     if (!TII->isPredicable(MI)) {
1151       BBI.IsUnpredicable = true;
1152       return;
1153     }
1154   }
1155 }
1156 
1157 /// Determine if the block is a suitable candidate to be predicated by the
1158 /// specified predicate.
1159 /// @param BBI BBInfo for the block to check
1160 /// @param Pred Predicate array for the branch that leads to BBI
1161 /// @param isTriangle true if the Analysis is for a triangle
1162 /// @param RevBranch true if Reverse(Pred) leads to BBI (e.g. BBI is the false
1163 ///        case
1164 /// @param hasCommonTail true if BBI shares a tail with a sibling block that
1165 ///        contains any instruction that would make the block unpredicable.
1166 bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,
1167                                       SmallVectorImpl<MachineOperand> &Pred,
1168                                       bool isTriangle, bool RevBranch,
1169                                       bool hasCommonTail) {
1170   // If the block is dead or unpredicable, then it cannot be predicated.
1171   // Two blocks may share a common unpredicable tail, but this doesn't prevent
1172   // them from being if-converted. The non-shared portion is assumed to have
1173   // been checked
1174   if (BBI.IsDone || (BBI.IsUnpredicable && !hasCommonTail))
1175     return false;
1176 
1177   // If it is already predicated but we couldn't analyze its terminator, the
1178   // latter might fallthrough, but we can't determine where to.
1179   // Conservatively avoid if-converting again.
1180   if (BBI.Predicate.size() && !BBI.IsBrAnalyzable)
1181     return false;
1182 
1183   // If it is already predicated, check if the new predicate subsumes
1184   // its predicate.
1185   if (BBI.Predicate.size() && !TII->SubsumesPredicate(Pred, BBI.Predicate))
1186     return false;
1187 
1188   if (!hasCommonTail && BBI.BrCond.size()) {
1189     if (!isTriangle)
1190       return false;
1191 
1192     // Test predicate subsumption.
1193     SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end());
1194     SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
1195     if (RevBranch) {
1196       if (TII->reverseBranchCondition(Cond))
1197         return false;
1198     }
1199     if (TII->reverseBranchCondition(RevPred) ||
1200         !TII->SubsumesPredicate(Cond, RevPred))
1201       return false;
1202   }
1203 
1204   return true;
1205 }
1206 
1207 /// Analyze the structure of the sub-CFG starting from the specified block.
1208 /// Record its successors and whether it looks like an if-conversion candidate.
1209 void IfConverter::AnalyzeBlock(
1210     MachineBasicBlock &MBB, std::vector<std::unique_ptr<IfcvtToken>> &Tokens) {
1211   struct BBState {
1212     BBState(MachineBasicBlock &MBB) : MBB(&MBB) {}
1213     MachineBasicBlock *MBB;
1214 
1215     /// This flag is true if MBB's successors have been analyzed.
1216     bool SuccsAnalyzed = false;
1217   };
1218 
1219   // Push MBB to the stack.
1220   SmallVector<BBState, 16> BBStack(1, MBB);
1221 
1222   while (!BBStack.empty()) {
1223     BBState &State = BBStack.back();
1224     MachineBasicBlock *BB = State.MBB;
1225     BBInfo &BBI = BBAnalysis[BB->getNumber()];
1226 
1227     if (!State.SuccsAnalyzed) {
1228       if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed) {
1229         BBStack.pop_back();
1230         continue;
1231       }
1232 
1233       BBI.BB = BB;
1234       BBI.IsBeingAnalyzed = true;
1235 
1236       AnalyzeBranches(BBI);
1237       MachineBasicBlock::iterator Begin = BBI.BB->begin();
1238       MachineBasicBlock::iterator End = BBI.BB->end();
1239       ScanInstructions(BBI, Begin, End);
1240 
1241       // Unanalyzable or ends with fallthrough or unconditional branch, or if is
1242       // not considered for ifcvt anymore.
1243       if (!BBI.IsBrAnalyzable || BBI.BrCond.empty() || BBI.IsDone) {
1244         BBI.IsBeingAnalyzed = false;
1245         BBI.IsAnalyzed = true;
1246         BBStack.pop_back();
1247         continue;
1248       }
1249 
1250       // Do not ifcvt if either path is a back edge to the entry block.
1251       if (BBI.TrueBB == BB || BBI.FalseBB == BB) {
1252         BBI.IsBeingAnalyzed = false;
1253         BBI.IsAnalyzed = true;
1254         BBStack.pop_back();
1255         continue;
1256       }
1257 
1258       // Do not ifcvt if true and false fallthrough blocks are the same.
1259       if (!BBI.FalseBB) {
1260         BBI.IsBeingAnalyzed = false;
1261         BBI.IsAnalyzed = true;
1262         BBStack.pop_back();
1263         continue;
1264       }
1265 
1266       // Push the False and True blocks to the stack.
1267       State.SuccsAnalyzed = true;
1268       BBStack.push_back(*BBI.FalseBB);
1269       BBStack.push_back(*BBI.TrueBB);
1270       continue;
1271     }
1272 
1273     BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
1274     BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1275 
1276     if (TrueBBI.IsDone && FalseBBI.IsDone) {
1277       BBI.IsBeingAnalyzed = false;
1278       BBI.IsAnalyzed = true;
1279       BBStack.pop_back();
1280       continue;
1281     }
1282 
1283     SmallVector<MachineOperand, 4>
1284         RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1285     bool CanRevCond = !TII->reverseBranchCondition(RevCond);
1286 
1287     unsigned Dups = 0;
1288     unsigned Dups2 = 0;
1289     bool TNeedSub = !TrueBBI.Predicate.empty();
1290     bool FNeedSub = !FalseBBI.Predicate.empty();
1291     bool Enqueued = false;
1292 
1293     BranchProbability Prediction = MBPI->getEdgeProbability(BB, TrueBBI.BB);
1294 
1295     if (CanRevCond) {
1296       BBInfo TrueBBICalc, FalseBBICalc;
1297       auto feasibleDiamond = [&](bool Forked) {
1298         bool MeetsSize = MeetIfcvtSizeLimit(TrueBBICalc, FalseBBICalc, *BB,
1299                                             Dups + Dups2, Prediction, Forked);
1300         bool TrueFeasible = FeasibilityAnalysis(TrueBBI, BBI.BrCond,
1301                                                 /* IsTriangle */ false, /* RevCond */ false,
1302                                                 /* hasCommonTail */ true);
1303         bool FalseFeasible = FeasibilityAnalysis(FalseBBI, RevCond,
1304                                                  /* IsTriangle */ false, /* RevCond */ false,
1305                                                  /* hasCommonTail */ true);
1306         return MeetsSize && TrueFeasible && FalseFeasible;
1307       };
1308 
1309       if (ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2,
1310                        TrueBBICalc, FalseBBICalc)) {
1311         if (feasibleDiamond(false)) {
1312           // Diamond:
1313           //   EBB
1314           //   / \_
1315           //  |   |
1316           // TBB FBB
1317           //   \ /
1318           //  TailBB
1319           // Note TailBB can be empty.
1320           Tokens.push_back(std::make_unique<IfcvtToken>(
1321               BBI, ICDiamond, TNeedSub | FNeedSub, Dups, Dups2,
1322               (bool) TrueBBICalc.ClobbersPred, (bool) FalseBBICalc.ClobbersPred));
1323           Enqueued = true;
1324         }
1325       } else if (ValidForkedDiamond(TrueBBI, FalseBBI, Dups, Dups2,
1326                                     TrueBBICalc, FalseBBICalc)) {
1327         if (feasibleDiamond(true)) {
1328           // ForkedDiamond:
1329           // if TBB and FBB have a common tail that includes their conditional
1330           // branch instructions, then we can If Convert this pattern.
1331           //          EBB
1332           //         _/ \_
1333           //         |   |
1334           //        TBB  FBB
1335           //        / \ /   \
1336           //  FalseBB TrueBB FalseBB
1337           //
1338           Tokens.push_back(std::make_unique<IfcvtToken>(
1339               BBI, ICForkedDiamond, TNeedSub | FNeedSub, Dups, Dups2,
1340               (bool) TrueBBICalc.ClobbersPred, (bool) FalseBBICalc.ClobbersPred));
1341           Enqueued = true;
1342         }
1343       }
1344     }
1345 
1346     if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction) &&
1347         MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
1348                            TrueBBI.ExtraCost2, Prediction) &&
1349         FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
1350       // Triangle:
1351       //   EBB
1352       //   | \_
1353       //   |  |
1354       //   | TBB
1355       //   |  /
1356       //   FBB
1357       Tokens.push_back(
1358           std::make_unique<IfcvtToken>(BBI, ICTriangle, TNeedSub, Dups));
1359       Enqueued = true;
1360     }
1361 
1362     if (ValidTriangle(TrueBBI, FalseBBI, true, Dups, Prediction) &&
1363         MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
1364                            TrueBBI.ExtraCost2, Prediction) &&
1365         FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {
1366       Tokens.push_back(
1367           std::make_unique<IfcvtToken>(BBI, ICTriangleRev, TNeedSub, Dups));
1368       Enqueued = true;
1369     }
1370 
1371     if (ValidSimple(TrueBBI, Dups, Prediction) &&
1372         MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
1373                            TrueBBI.ExtraCost2, Prediction) &&
1374         FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
1375       // Simple (split, no rejoin):
1376       //   EBB
1377       //   | \_
1378       //   |  |
1379       //   | TBB---> exit
1380       //   |
1381       //   FBB
1382       Tokens.push_back(
1383           std::make_unique<IfcvtToken>(BBI, ICSimple, TNeedSub, Dups));
1384       Enqueued = true;
1385     }
1386 
1387     if (CanRevCond) {
1388       // Try the other path...
1389       if (ValidTriangle(FalseBBI, TrueBBI, false, Dups,
1390                         Prediction.getCompl()) &&
1391           MeetIfcvtSizeLimit(*FalseBBI.BB,
1392                              FalseBBI.NonPredSize + FalseBBI.ExtraCost,
1393                              FalseBBI.ExtraCost2, Prediction.getCompl()) &&
1394           FeasibilityAnalysis(FalseBBI, RevCond, true)) {
1395         Tokens.push_back(std::make_unique<IfcvtToken>(BBI, ICTriangleFalse,
1396                                                        FNeedSub, Dups));
1397         Enqueued = true;
1398       }
1399 
1400       if (ValidTriangle(FalseBBI, TrueBBI, true, Dups,
1401                         Prediction.getCompl()) &&
1402           MeetIfcvtSizeLimit(*FalseBBI.BB,
1403                              FalseBBI.NonPredSize + FalseBBI.ExtraCost,
1404                            FalseBBI.ExtraCost2, Prediction.getCompl()) &&
1405         FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {
1406         Tokens.push_back(
1407             std::make_unique<IfcvtToken>(BBI, ICTriangleFRev, FNeedSub, Dups));
1408         Enqueued = true;
1409       }
1410 
1411       if (ValidSimple(FalseBBI, Dups, Prediction.getCompl()) &&
1412           MeetIfcvtSizeLimit(*FalseBBI.BB,
1413                              FalseBBI.NonPredSize + FalseBBI.ExtraCost,
1414                              FalseBBI.ExtraCost2, Prediction.getCompl()) &&
1415           FeasibilityAnalysis(FalseBBI, RevCond)) {
1416         Tokens.push_back(
1417             std::make_unique<IfcvtToken>(BBI, ICSimpleFalse, FNeedSub, Dups));
1418         Enqueued = true;
1419       }
1420     }
1421 
1422     BBI.IsEnqueued = Enqueued;
1423     BBI.IsBeingAnalyzed = false;
1424     BBI.IsAnalyzed = true;
1425     BBStack.pop_back();
1426   }
1427 }
1428 
1429 /// Analyze all blocks and find entries for all if-conversion candidates.
1430 void IfConverter::AnalyzeBlocks(
1431     MachineFunction &MF, std::vector<std::unique_ptr<IfcvtToken>> &Tokens) {
1432   for (MachineBasicBlock &MBB : MF)
1433     AnalyzeBlock(MBB, Tokens);
1434 
1435   // Sort to favor more complex ifcvt scheme.
1436   llvm::stable_sort(Tokens, IfcvtTokenCmp);
1437 }
1438 
1439 /// Returns true either if ToMBB is the next block after MBB or that all the
1440 /// intervening blocks are empty (given MBB can fall through to its next block).
1441 static bool canFallThroughTo(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB) {
1442   MachineFunction::iterator PI = MBB.getIterator();
1443   MachineFunction::iterator I = std::next(PI);
1444   MachineFunction::iterator TI = ToMBB.getIterator();
1445   MachineFunction::iterator E = MBB.getParent()->end();
1446   while (I != TI) {
1447     // Check isSuccessor to avoid case where the next block is empty, but
1448     // it's not a successor.
1449     if (I == E || !I->empty() || !PI->isSuccessor(&*I))
1450       return false;
1451     PI = I++;
1452   }
1453   // Finally see if the last I is indeed a successor to PI.
1454   return PI->isSuccessor(&*I);
1455 }
1456 
1457 /// Invalidate predecessor BB info so it would be re-analyzed to determine if it
1458 /// can be if-converted. If predecessor is already enqueued, dequeue it!
1459 void IfConverter::InvalidatePreds(MachineBasicBlock &MBB) {
1460   for (const MachineBasicBlock *Predecessor : MBB.predecessors()) {
1461     BBInfo &PBBI = BBAnalysis[Predecessor->getNumber()];
1462     if (PBBI.IsDone || PBBI.BB == &MBB)
1463       continue;
1464     PBBI.IsAnalyzed = false;
1465     PBBI.IsEnqueued = false;
1466   }
1467 }
1468 
1469 /// Inserts an unconditional branch from \p MBB to \p ToMBB.
1470 static void InsertUncondBranch(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB,
1471                                const TargetInstrInfo *TII) {
1472   DebugLoc dl;  // FIXME: this is nowhere
1473   SmallVector<MachineOperand, 0> NoCond;
1474   TII->insertBranch(MBB, &ToMBB, nullptr, NoCond, dl);
1475 }
1476 
1477 /// Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all
1478 /// values defined in MI which are also live/used by MI.
1479 static void UpdatePredRedefs(MachineInstr &MI, LivePhysRegs &Redefs) {
1480   const TargetRegisterInfo *TRI = MI.getMF()->getSubtarget().getRegisterInfo();
1481 
1482   // Before stepping forward past MI, remember which regs were live
1483   // before MI. This is needed to set the Undef flag only when reg is
1484   // dead.
1485   SparseSet<MCPhysReg, identity<MCPhysReg>> LiveBeforeMI;
1486   LiveBeforeMI.setUniverse(TRI->getNumRegs());
1487   for (unsigned Reg : Redefs)
1488     LiveBeforeMI.insert(Reg);
1489 
1490   SmallVector<std::pair<MCPhysReg, const MachineOperand*>, 4> Clobbers;
1491   Redefs.stepForward(MI, Clobbers);
1492 
1493   // Now add the implicit uses for each of the clobbered values.
1494   for (auto Clobber : Clobbers) {
1495     // FIXME: Const cast here is nasty, but better than making StepForward
1496     // take a mutable instruction instead of const.
1497     unsigned Reg = Clobber.first;
1498     MachineOperand &Op = const_cast<MachineOperand&>(*Clobber.second);
1499     MachineInstr *OpMI = Op.getParent();
1500     MachineInstrBuilder MIB(*OpMI->getMF(), OpMI);
1501     if (Op.isRegMask()) {
1502       // First handle regmasks.  They clobber any entries in the mask which
1503       // means that we need a def for those registers.
1504       if (LiveBeforeMI.count(Reg))
1505         MIB.addReg(Reg, RegState::Implicit);
1506 
1507       // We also need to add an implicit def of this register for the later
1508       // use to read from.
1509       // For the register allocator to have allocated a register clobbered
1510       // by the call which is used later, it must be the case that
1511       // the call doesn't return.
1512       MIB.addReg(Reg, RegState::Implicit | RegState::Define);
1513       continue;
1514     }
1515     if (LiveBeforeMI.count(Reg))
1516       MIB.addReg(Reg, RegState::Implicit);
1517     else {
1518       bool HasLiveSubReg = false;
1519       for (MCSubRegIterator S(Reg, TRI); S.isValid(); ++S) {
1520         if (!LiveBeforeMI.count(*S))
1521           continue;
1522         HasLiveSubReg = true;
1523         break;
1524       }
1525       if (HasLiveSubReg)
1526         MIB.addReg(Reg, RegState::Implicit);
1527     }
1528   }
1529 }
1530 
1531 /// If convert a simple (split, no rejoin) sub-CFG.
1532 bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
1533   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
1534   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1535   BBInfo *CvtBBI = &TrueBBI;
1536   BBInfo *NextBBI = &FalseBBI;
1537 
1538   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
1539   if (Kind == ICSimpleFalse)
1540     std::swap(CvtBBI, NextBBI);
1541 
1542   MachineBasicBlock &CvtMBB = *CvtBBI->BB;
1543   MachineBasicBlock &NextMBB = *NextBBI->BB;
1544   if (CvtBBI->IsDone ||
1545       (CvtBBI->CannotBeCopied && CvtMBB.pred_size() > 1)) {
1546     // Something has changed. It's no longer safe to predicate this block.
1547     BBI.IsAnalyzed = false;
1548     CvtBBI->IsAnalyzed = false;
1549     return false;
1550   }
1551 
1552   if (CvtMBB.hasAddressTaken())
1553     // Conservatively abort if-conversion if BB's address is taken.
1554     return false;
1555 
1556   if (Kind == ICSimpleFalse)
1557     if (TII->reverseBranchCondition(Cond))
1558       llvm_unreachable("Unable to reverse branch condition!");
1559 
1560   Redefs.init(*TRI);
1561 
1562   if (MRI->tracksLiveness()) {
1563     // Initialize liveins to the first BB. These are potentially redefined by
1564     // predicated instructions.
1565     Redefs.addLiveInsNoPristines(CvtMBB);
1566     Redefs.addLiveInsNoPristines(NextMBB);
1567   }
1568 
1569   // Remove the branches from the entry so we can add the contents of the true
1570   // block to it.
1571   BBI.NonPredSize -= TII->removeBranch(*BBI.BB);
1572 
1573   if (CvtMBB.pred_size() > 1) {
1574     // Copy instructions in the true block, predicate them, and add them to
1575     // the entry block.
1576     CopyAndPredicateBlock(BBI, *CvtBBI, Cond);
1577 
1578     // Keep the CFG updated.
1579     BBI.BB->removeSuccessor(&CvtMBB, true);
1580   } else {
1581     // Predicate the instructions in the true block.
1582     PredicateBlock(*CvtBBI, CvtMBB.end(), Cond);
1583 
1584     // Merge converted block into entry block. The BB to Cvt edge is removed
1585     // by MergeBlocks.
1586     MergeBlocks(BBI, *CvtBBI);
1587   }
1588 
1589   bool IterIfcvt = true;
1590   if (!canFallThroughTo(*BBI.BB, NextMBB)) {
1591     InsertUncondBranch(*BBI.BB, NextMBB, TII);
1592     BBI.HasFallThrough = false;
1593     // Now ifcvt'd block will look like this:
1594     // BB:
1595     // ...
1596     // t, f = cmp
1597     // if t op
1598     // b BBf
1599     //
1600     // We cannot further ifcvt this block because the unconditional branch
1601     // will have to be predicated on the new condition, that will not be
1602     // available if cmp executes.
1603     IterIfcvt = false;
1604   }
1605 
1606   // Update block info. BB can be iteratively if-converted.
1607   if (!IterIfcvt)
1608     BBI.IsDone = true;
1609   InvalidatePreds(*BBI.BB);
1610   CvtBBI->IsDone = true;
1611 
1612   // FIXME: Must maintain LiveIns.
1613   return true;
1614 }
1615 
1616 /// If convert a triangle sub-CFG.
1617 bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
1618   BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
1619   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1620   BBInfo *CvtBBI = &TrueBBI;
1621   BBInfo *NextBBI = &FalseBBI;
1622   DebugLoc dl;  // FIXME: this is nowhere
1623 
1624   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
1625   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1626     std::swap(CvtBBI, NextBBI);
1627 
1628   MachineBasicBlock &CvtMBB = *CvtBBI->BB;
1629   MachineBasicBlock &NextMBB = *NextBBI->BB;
1630   if (CvtBBI->IsDone ||
1631       (CvtBBI->CannotBeCopied && CvtMBB.pred_size() > 1)) {
1632     // Something has changed. It's no longer safe to predicate this block.
1633     BBI.IsAnalyzed = false;
1634     CvtBBI->IsAnalyzed = false;
1635     return false;
1636   }
1637 
1638   if (CvtMBB.hasAddressTaken())
1639     // Conservatively abort if-conversion if BB's address is taken.
1640     return false;
1641 
1642   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1643     if (TII->reverseBranchCondition(Cond))
1644       llvm_unreachable("Unable to reverse branch condition!");
1645 
1646   if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {
1647     if (reverseBranchCondition(*CvtBBI)) {
1648       // BB has been changed, modify its predecessors (except for this
1649       // one) so they don't get ifcvt'ed based on bad intel.
1650       for (MachineBasicBlock *PBB : CvtMBB.predecessors()) {
1651         if (PBB == BBI.BB)
1652           continue;
1653         BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
1654         if (PBBI.IsEnqueued) {
1655           PBBI.IsAnalyzed = false;
1656           PBBI.IsEnqueued = false;
1657         }
1658       }
1659     }
1660   }
1661 
1662   // Initialize liveins to the first BB. These are potentially redefined by
1663   // predicated instructions.
1664   Redefs.init(*TRI);
1665   if (MRI->tracksLiveness()) {
1666     Redefs.addLiveInsNoPristines(CvtMBB);
1667     Redefs.addLiveInsNoPristines(NextMBB);
1668   }
1669 
1670   bool HasEarlyExit = CvtBBI->FalseBB != nullptr;
1671   BranchProbability CvtNext, CvtFalse, BBNext, BBCvt;
1672 
1673   if (HasEarlyExit) {
1674     // Get probabilities before modifying CvtMBB and BBI.BB.
1675     CvtNext = MBPI->getEdgeProbability(&CvtMBB, &NextMBB);
1676     CvtFalse = MBPI->getEdgeProbability(&CvtMBB, CvtBBI->FalseBB);
1677     BBNext = MBPI->getEdgeProbability(BBI.BB, &NextMBB);
1678     BBCvt = MBPI->getEdgeProbability(BBI.BB, &CvtMBB);
1679   }
1680 
1681   // Remove the branches from the entry so we can add the contents of the true
1682   // block to it.
1683   BBI.NonPredSize -= TII->removeBranch(*BBI.BB);
1684 
1685   if (CvtMBB.pred_size() > 1) {
1686     // Copy instructions in the true block, predicate them, and add them to
1687     // the entry block.
1688     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true);
1689   } else {
1690     // Predicate the 'true' block after removing its branch.
1691     CvtBBI->NonPredSize -= TII->removeBranch(CvtMBB);
1692     PredicateBlock(*CvtBBI, CvtMBB.end(), Cond);
1693 
1694     // Now merge the entry of the triangle with the true block.
1695     MergeBlocks(BBI, *CvtBBI, false);
1696   }
1697 
1698   // Keep the CFG updated.
1699   BBI.BB->removeSuccessor(&CvtMBB, true);
1700 
1701   // If 'true' block has a 'false' successor, add an exit branch to it.
1702   if (HasEarlyExit) {
1703     SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
1704                                            CvtBBI->BrCond.end());
1705     if (TII->reverseBranchCondition(RevCond))
1706       llvm_unreachable("Unable to reverse branch condition!");
1707 
1708     // Update the edge probability for both CvtBBI->FalseBB and NextBBI.
1709     // NewNext = New_Prob(BBI.BB, NextMBB) =
1710     //   Prob(BBI.BB, NextMBB) +
1711     //   Prob(BBI.BB, CvtMBB) * Prob(CvtMBB, NextMBB)
1712     // NewFalse = New_Prob(BBI.BB, CvtBBI->FalseBB) =
1713     //   Prob(BBI.BB, CvtMBB) * Prob(CvtMBB, CvtBBI->FalseBB)
1714     auto NewTrueBB = getNextBlock(*BBI.BB);
1715     auto NewNext = BBNext + BBCvt * CvtNext;
1716     auto NewTrueBBIter = find(BBI.BB->successors(), NewTrueBB);
1717     if (NewTrueBBIter != BBI.BB->succ_end())
1718       BBI.BB->setSuccProbability(NewTrueBBIter, NewNext);
1719 
1720     auto NewFalse = BBCvt * CvtFalse;
1721     TII->insertBranch(*BBI.BB, CvtBBI->FalseBB, nullptr, RevCond, dl);
1722     BBI.BB->addSuccessor(CvtBBI->FalseBB, NewFalse);
1723   }
1724 
1725   // Merge in the 'false' block if the 'false' block has no other
1726   // predecessors. Otherwise, add an unconditional branch to 'false'.
1727   bool FalseBBDead = false;
1728   bool IterIfcvt = true;
1729   bool isFallThrough = canFallThroughTo(*BBI.BB, NextMBB);
1730   if (!isFallThrough) {
1731     // Only merge them if the true block does not fallthrough to the false
1732     // block. By not merging them, we make it possible to iteratively
1733     // ifcvt the blocks.
1734     if (!HasEarlyExit &&
1735         NextMBB.pred_size() == 1 && !NextBBI->HasFallThrough &&
1736         !NextMBB.hasAddressTaken()) {
1737       MergeBlocks(BBI, *NextBBI);
1738       FalseBBDead = true;
1739     } else {
1740       InsertUncondBranch(*BBI.BB, NextMBB, TII);
1741       BBI.HasFallThrough = false;
1742     }
1743     // Mixed predicated and unpredicated code. This cannot be iteratively
1744     // predicated.
1745     IterIfcvt = false;
1746   }
1747 
1748   // Update block info. BB can be iteratively if-converted.
1749   if (!IterIfcvt)
1750     BBI.IsDone = true;
1751   InvalidatePreds(*BBI.BB);
1752   CvtBBI->IsDone = true;
1753   if (FalseBBDead)
1754     NextBBI->IsDone = true;
1755 
1756   // FIXME: Must maintain LiveIns.
1757   return true;
1758 }
1759 
1760 /// Common code shared between diamond conversions.
1761 /// \p BBI, \p TrueBBI, and \p FalseBBI form the diamond shape.
1762 /// \p NumDups1 - number of shared instructions at the beginning of \p TrueBBI
1763 ///               and FalseBBI
1764 /// \p NumDups2 - number of shared instructions at the end of \p TrueBBI
1765 ///               and \p FalseBBI
1766 /// \p RemoveBranch - Remove the common branch of the two blocks before
1767 ///                   predicating. Only false for unanalyzable fallthrough
1768 ///                   cases. The caller will replace the branch if necessary.
1769 /// \p MergeAddEdges - Add successor edges when merging blocks. Only false for
1770 ///                    unanalyzable fallthrough
1771 bool IfConverter::IfConvertDiamondCommon(
1772     BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,
1773     unsigned NumDups1, unsigned NumDups2,
1774     bool TClobbersPred, bool FClobbersPred,
1775     bool RemoveBranch, bool MergeAddEdges) {
1776 
1777   if (TrueBBI.IsDone || FalseBBI.IsDone ||
1778       TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1) {
1779     // Something has changed. It's no longer safe to predicate these blocks.
1780     BBI.IsAnalyzed = false;
1781     TrueBBI.IsAnalyzed = false;
1782     FalseBBI.IsAnalyzed = false;
1783     return false;
1784   }
1785 
1786   if (TrueBBI.BB->hasAddressTaken() || FalseBBI.BB->hasAddressTaken())
1787     // Conservatively abort if-conversion if either BB has its address taken.
1788     return false;
1789 
1790   // Put the predicated instructions from the 'true' block before the
1791   // instructions from the 'false' block, unless the true block would clobber
1792   // the predicate, in which case, do the opposite.
1793   BBInfo *BBI1 = &TrueBBI;
1794   BBInfo *BBI2 = &FalseBBI;
1795   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1796   if (TII->reverseBranchCondition(RevCond))
1797     llvm_unreachable("Unable to reverse branch condition!");
1798   SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;
1799   SmallVector<MachineOperand, 4> *Cond2 = &RevCond;
1800 
1801   // Figure out the more profitable ordering.
1802   bool DoSwap = false;
1803   if (TClobbersPred && !FClobbersPred)
1804     DoSwap = true;
1805   else if (!TClobbersPred && !FClobbersPred) {
1806     if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
1807       DoSwap = true;
1808   } else if (TClobbersPred && FClobbersPred)
1809     llvm_unreachable("Predicate info cannot be clobbered by both sides.");
1810   if (DoSwap) {
1811     std::swap(BBI1, BBI2);
1812     std::swap(Cond1, Cond2);
1813   }
1814 
1815   // Remove the conditional branch from entry to the blocks.
1816   BBI.NonPredSize -= TII->removeBranch(*BBI.BB);
1817 
1818   MachineBasicBlock &MBB1 = *BBI1->BB;
1819   MachineBasicBlock &MBB2 = *BBI2->BB;
1820 
1821   // Initialize the Redefs:
1822   // - BB2 live-in regs need implicit uses before being redefined by BB1
1823   //   instructions.
1824   // - BB1 live-out regs need implicit uses before being redefined by BB2
1825   //   instructions. We start with BB1 live-ins so we have the live-out regs
1826   //   after tracking the BB1 instructions.
1827   Redefs.init(*TRI);
1828   if (MRI->tracksLiveness()) {
1829     Redefs.addLiveInsNoPristines(MBB1);
1830     Redefs.addLiveInsNoPristines(MBB2);
1831   }
1832 
1833   // Remove the duplicated instructions at the beginnings of both paths.
1834   // Skip dbg_value instructions.
1835   MachineBasicBlock::iterator DI1 = MBB1.getFirstNonDebugInstr(false);
1836   MachineBasicBlock::iterator DI2 = MBB2.getFirstNonDebugInstr(false);
1837   BBI1->NonPredSize -= NumDups1;
1838   BBI2->NonPredSize -= NumDups1;
1839 
1840   // Skip past the dups on each side separately since there may be
1841   // differing dbg_value entries. NumDups1 can include a "return"
1842   // instruction, if it's not marked as "branch".
1843   for (unsigned i = 0; i < NumDups1; ++DI1) {
1844     if (DI1 == MBB1.end())
1845       break;
1846     if (!DI1->isDebugInstr())
1847       ++i;
1848   }
1849   while (NumDups1 != 0) {
1850     // Since this instruction is going to be deleted, update call
1851     // site info state if the instruction is call instruction.
1852     if (DI2->shouldUpdateCallSiteInfo())
1853       MBB2.getParent()->eraseCallSiteInfo(&*DI2);
1854 
1855     ++DI2;
1856     if (DI2 == MBB2.end())
1857       break;
1858     if (!DI2->isDebugInstr())
1859       --NumDups1;
1860   }
1861 
1862   if (MRI->tracksLiveness()) {
1863     for (const MachineInstr &MI : make_range(MBB1.begin(), DI1)) {
1864       SmallVector<std::pair<MCPhysReg, const MachineOperand*>, 4> Dummy;
1865       Redefs.stepForward(MI, Dummy);
1866     }
1867   }
1868 
1869   BBI.BB->splice(BBI.BB->end(), &MBB1, MBB1.begin(), DI1);
1870   MBB2.erase(MBB2.begin(), DI2);
1871 
1872   // The branches have been checked to match, so it is safe to remove the
1873   // branch in BB1 and rely on the copy in BB2. The complication is that
1874   // the blocks may end with a return instruction, which may or may not
1875   // be marked as "branch". If it's not, then it could be included in
1876   // "dups1", leaving the blocks potentially empty after moving the common
1877   // duplicates.
1878 #ifndef NDEBUG
1879   // Unanalyzable branches must match exactly. Check that now.
1880   if (!BBI1->IsBrAnalyzable)
1881     verifySameBranchInstructions(&MBB1, &MBB2);
1882 #endif
1883   // Remove duplicated instructions from the tail of MBB1: any branch
1884   // instructions, and the common instructions counted by NumDups2.
1885   DI1 = MBB1.end();
1886   while (DI1 != MBB1.begin()) {
1887     MachineBasicBlock::iterator Prev = std::prev(DI1);
1888     if (!Prev->isBranch() && !Prev->isDebugInstr())
1889       break;
1890     DI1 = Prev;
1891   }
1892   for (unsigned i = 0; i != NumDups2; ) {
1893     // NumDups2 only counted non-dbg_value instructions, so this won't
1894     // run off the head of the list.
1895     assert(DI1 != MBB1.begin());
1896 
1897     --DI1;
1898 
1899     // Since this instruction is going to be deleted, update call
1900     // site info state if the instruction is call instruction.
1901     if (DI1->shouldUpdateCallSiteInfo())
1902       MBB1.getParent()->eraseCallSiteInfo(&*DI1);
1903 
1904     // skip dbg_value instructions
1905     if (!DI1->isDebugInstr())
1906       ++i;
1907   }
1908   MBB1.erase(DI1, MBB1.end());
1909 
1910   DI2 = BBI2->BB->end();
1911   // The branches have been checked to match. Skip over the branch in the false
1912   // block so that we don't try to predicate it.
1913   if (RemoveBranch)
1914     BBI2->NonPredSize -= TII->removeBranch(*BBI2->BB);
1915   else {
1916     // Make DI2 point to the end of the range where the common "tail"
1917     // instructions could be found.
1918     while (DI2 != MBB2.begin()) {
1919       MachineBasicBlock::iterator Prev = std::prev(DI2);
1920       if (!Prev->isBranch() && !Prev->isDebugInstr())
1921         break;
1922       DI2 = Prev;
1923     }
1924   }
1925   while (NumDups2 != 0) {
1926     // NumDups2 only counted non-dbg_value instructions, so this won't
1927     // run off the head of the list.
1928     assert(DI2 != MBB2.begin());
1929     --DI2;
1930     // skip dbg_value instructions
1931     if (!DI2->isDebugInstr())
1932       --NumDups2;
1933   }
1934 
1935   // Remember which registers would later be defined by the false block.
1936   // This allows us not to predicate instructions in the true block that would
1937   // later be re-defined. That is, rather than
1938   //   subeq  r0, r1, #1
1939   //   addne  r0, r1, #1
1940   // generate:
1941   //   sub    r0, r1, #1
1942   //   addne  r0, r1, #1
1943   SmallSet<MCPhysReg, 4> RedefsByFalse;
1944   SmallSet<MCPhysReg, 4> ExtUses;
1945   if (TII->isProfitableToUnpredicate(MBB1, MBB2)) {
1946     for (const MachineInstr &FI : make_range(MBB2.begin(), DI2)) {
1947       if (FI.isDebugInstr())
1948         continue;
1949       SmallVector<MCPhysReg, 4> Defs;
1950       for (const MachineOperand &MO : FI.operands()) {
1951         if (!MO.isReg())
1952           continue;
1953         Register Reg = MO.getReg();
1954         if (!Reg)
1955           continue;
1956         if (MO.isDef()) {
1957           Defs.push_back(Reg);
1958         } else if (!RedefsByFalse.count(Reg)) {
1959           // These are defined before ctrl flow reach the 'false' instructions.
1960           // They cannot be modified by the 'true' instructions.
1961           for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
1962                SubRegs.isValid(); ++SubRegs)
1963             ExtUses.insert(*SubRegs);
1964         }
1965       }
1966 
1967       for (MCPhysReg Reg : Defs) {
1968         if (!ExtUses.count(Reg)) {
1969           for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
1970                SubRegs.isValid(); ++SubRegs)
1971             RedefsByFalse.insert(*SubRegs);
1972         }
1973       }
1974     }
1975   }
1976 
1977   // Predicate the 'true' block.
1978   PredicateBlock(*BBI1, MBB1.end(), *Cond1, &RedefsByFalse);
1979 
1980   // After predicating BBI1, if there is a predicated terminator in BBI1 and
1981   // a non-predicated in BBI2, then we don't want to predicate the one from
1982   // BBI2. The reason is that if we merged these blocks, we would end up with
1983   // two predicated terminators in the same block.
1984   // Also, if the branches in MBB1 and MBB2 were non-analyzable, then don't
1985   // predicate them either. They were checked to be identical, and so the
1986   // same branch would happen regardless of which path was taken.
1987   if (!MBB2.empty() && (DI2 == MBB2.end())) {
1988     MachineBasicBlock::iterator BBI1T = MBB1.getFirstTerminator();
1989     MachineBasicBlock::iterator BBI2T = MBB2.getFirstTerminator();
1990     bool BB1Predicated = BBI1T != MBB1.end() && TII->isPredicated(*BBI1T);
1991     bool BB2NonPredicated = BBI2T != MBB2.end() && !TII->isPredicated(*BBI2T);
1992     if (BB2NonPredicated && (BB1Predicated || !BBI2->IsBrAnalyzable))
1993       --DI2;
1994   }
1995 
1996   // Predicate the 'false' block.
1997   PredicateBlock(*BBI2, DI2, *Cond2);
1998 
1999   // Merge the true block into the entry of the diamond.
2000   MergeBlocks(BBI, *BBI1, MergeAddEdges);
2001   MergeBlocks(BBI, *BBI2, MergeAddEdges);
2002   return true;
2003 }
2004 
2005 /// If convert an almost-diamond sub-CFG where the true
2006 /// and false blocks share a common tail.
2007 bool IfConverter::IfConvertForkedDiamond(
2008     BBInfo &BBI, IfcvtKind Kind,
2009     unsigned NumDups1, unsigned NumDups2,
2010     bool TClobbersPred, bool FClobbersPred) {
2011   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
2012   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
2013 
2014   // Save the debug location for later.
2015   DebugLoc dl;
2016   MachineBasicBlock::iterator TIE = TrueBBI.BB->getFirstTerminator();
2017   if (TIE != TrueBBI.BB->end())
2018     dl = TIE->getDebugLoc();
2019   // Removing branches from both blocks is safe, because we have already
2020   // determined that both blocks have the same branch instructions. The branch
2021   // will be added back at the end, unpredicated.
2022   if (!IfConvertDiamondCommon(
2023       BBI, TrueBBI, FalseBBI,
2024       NumDups1, NumDups2,
2025       TClobbersPred, FClobbersPred,
2026       /* RemoveBranch */ true, /* MergeAddEdges */ true))
2027     return false;
2028 
2029   // Add back the branch.
2030   // Debug location saved above when removing the branch from BBI2
2031   TII->insertBranch(*BBI.BB, TrueBBI.TrueBB, TrueBBI.FalseBB,
2032                     TrueBBI.BrCond, dl);
2033 
2034   // Update block info.
2035   BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
2036   InvalidatePreds(*BBI.BB);
2037 
2038   // FIXME: Must maintain LiveIns.
2039   return true;
2040 }
2041 
2042 /// If convert a diamond sub-CFG.
2043 bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
2044                                    unsigned NumDups1, unsigned NumDups2,
2045                                    bool TClobbersPred, bool FClobbersPred) {
2046   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
2047   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
2048   MachineBasicBlock *TailBB = TrueBBI.TrueBB;
2049 
2050   // True block must fall through or end with an unanalyzable terminator.
2051   if (!TailBB) {
2052     if (blockAlwaysFallThrough(TrueBBI))
2053       TailBB = FalseBBI.TrueBB;
2054     assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");
2055   }
2056 
2057   if (!IfConvertDiamondCommon(
2058       BBI, TrueBBI, FalseBBI,
2059       NumDups1, NumDups2,
2060       TClobbersPred, FClobbersPred,
2061       /* RemoveBranch */ TrueBBI.IsBrAnalyzable,
2062       /* MergeAddEdges */ TailBB == nullptr))
2063     return false;
2064 
2065   // If the if-converted block falls through or unconditionally branches into
2066   // the tail block, and the tail block does not have other predecessors, then
2067   // fold the tail block in as well. Otherwise, unless it falls through to the
2068   // tail, add a unconditional branch to it.
2069   if (TailBB) {
2070     // We need to remove the edges to the true and false blocks manually since
2071     // we didn't let IfConvertDiamondCommon update the CFG.
2072     BBI.BB->removeSuccessor(TrueBBI.BB);
2073     BBI.BB->removeSuccessor(FalseBBI.BB, true);
2074 
2075     BBInfo &TailBBI = BBAnalysis[TailBB->getNumber()];
2076     bool CanMergeTail = !TailBBI.HasFallThrough &&
2077       !TailBBI.BB->hasAddressTaken();
2078     // The if-converted block can still have a predicated terminator
2079     // (e.g. a predicated return). If that is the case, we cannot merge
2080     // it with the tail block.
2081     MachineBasicBlock::const_iterator TI = BBI.BB->getFirstTerminator();
2082     if (TI != BBI.BB->end() && TII->isPredicated(*TI))
2083       CanMergeTail = false;
2084     // There may still be a fall-through edge from BBI1 or BBI2 to TailBB;
2085     // check if there are any other predecessors besides those.
2086     unsigned NumPreds = TailBB->pred_size();
2087     if (NumPreds > 1)
2088       CanMergeTail = false;
2089     else if (NumPreds == 1 && CanMergeTail) {
2090       MachineBasicBlock::pred_iterator PI = TailBB->pred_begin();
2091       if (*PI != TrueBBI.BB && *PI != FalseBBI.BB)
2092         CanMergeTail = false;
2093     }
2094     if (CanMergeTail) {
2095       MergeBlocks(BBI, TailBBI);
2096       TailBBI.IsDone = true;
2097     } else {
2098       BBI.BB->addSuccessor(TailBB, BranchProbability::getOne());
2099       InsertUncondBranch(*BBI.BB, *TailBB, TII);
2100       BBI.HasFallThrough = false;
2101     }
2102   }
2103 
2104   // Update block info.
2105   BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
2106   InvalidatePreds(*BBI.BB);
2107 
2108   // FIXME: Must maintain LiveIns.
2109   return true;
2110 }
2111 
2112 static bool MaySpeculate(const MachineInstr &MI,
2113                          SmallSet<MCPhysReg, 4> &LaterRedefs) {
2114   bool SawStore = true;
2115   if (!MI.isSafeToMove(nullptr, SawStore))
2116     return false;
2117 
2118   for (const MachineOperand &MO : MI.operands()) {
2119     if (!MO.isReg())
2120       continue;
2121     Register Reg = MO.getReg();
2122     if (!Reg)
2123       continue;
2124     if (MO.isDef() && !LaterRedefs.count(Reg))
2125       return false;
2126   }
2127 
2128   return true;
2129 }
2130 
2131 /// Predicate instructions from the start of the block to the specified end with
2132 /// the specified condition.
2133 void IfConverter::PredicateBlock(BBInfo &BBI,
2134                                  MachineBasicBlock::iterator E,
2135                                  SmallVectorImpl<MachineOperand> &Cond,
2136                                  SmallSet<MCPhysReg, 4> *LaterRedefs) {
2137   bool AnyUnpred = false;
2138   bool MaySpec = LaterRedefs != nullptr;
2139   for (MachineInstr &I : make_range(BBI.BB->begin(), E)) {
2140     if (I.isDebugInstr() || TII->isPredicated(I))
2141       continue;
2142     // It may be possible not to predicate an instruction if it's the 'true'
2143     // side of a diamond and the 'false' side may re-define the instruction's
2144     // defs.
2145     if (MaySpec && MaySpeculate(I, *LaterRedefs)) {
2146       AnyUnpred = true;
2147       continue;
2148     }
2149     // If any instruction is predicated, then every instruction after it must
2150     // be predicated.
2151     MaySpec = false;
2152     if (!TII->PredicateInstruction(I, Cond)) {
2153 #ifndef NDEBUG
2154       dbgs() << "Unable to predicate " << I << "!\n";
2155 #endif
2156       llvm_unreachable(nullptr);
2157     }
2158 
2159     // If the predicated instruction now redefines a register as the result of
2160     // if-conversion, add an implicit kill.
2161     UpdatePredRedefs(I, Redefs);
2162   }
2163 
2164   BBI.Predicate.append(Cond.begin(), Cond.end());
2165 
2166   BBI.IsAnalyzed = false;
2167   BBI.NonPredSize = 0;
2168 
2169   ++NumIfConvBBs;
2170   if (AnyUnpred)
2171     ++NumUnpred;
2172 }
2173 
2174 /// Copy and predicate instructions from source BB to the destination block.
2175 /// Skip end of block branches if IgnoreBr is true.
2176 void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
2177                                         SmallVectorImpl<MachineOperand> &Cond,
2178                                         bool IgnoreBr) {
2179   MachineFunction &MF = *ToBBI.BB->getParent();
2180 
2181   MachineBasicBlock &FromMBB = *FromBBI.BB;
2182   for (MachineInstr &I : FromMBB) {
2183     // Do not copy the end of the block branches.
2184     if (IgnoreBr && I.isBranch())
2185       break;
2186 
2187     MachineInstr *MI = MF.CloneMachineInstr(&I);
2188     // Make a copy of the call site info.
2189     if (I.isCandidateForCallSiteEntry())
2190       MF.copyCallSiteInfo(&I, MI);
2191 
2192     ToBBI.BB->insert(ToBBI.BB->end(), MI);
2193     ToBBI.NonPredSize++;
2194     unsigned ExtraPredCost = TII->getPredicationCost(I);
2195     unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
2196     if (NumCycles > 1)
2197       ToBBI.ExtraCost += NumCycles-1;
2198     ToBBI.ExtraCost2 += ExtraPredCost;
2199 
2200     if (!TII->isPredicated(I) && !MI->isDebugInstr()) {
2201       if (!TII->PredicateInstruction(*MI, Cond)) {
2202 #ifndef NDEBUG
2203         dbgs() << "Unable to predicate " << I << "!\n";
2204 #endif
2205         llvm_unreachable(nullptr);
2206       }
2207     }
2208 
2209     // If the predicated instruction now redefines a register as the result of
2210     // if-conversion, add an implicit kill.
2211     UpdatePredRedefs(*MI, Redefs);
2212   }
2213 
2214   if (!IgnoreBr) {
2215     std::vector<MachineBasicBlock *> Succs(FromMBB.succ_begin(),
2216                                            FromMBB.succ_end());
2217     MachineBasicBlock *NBB = getNextBlock(FromMBB);
2218     MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;
2219 
2220     for (MachineBasicBlock *Succ : Succs) {
2221       // Fallthrough edge can't be transferred.
2222       if (Succ == FallThrough)
2223         continue;
2224       ToBBI.BB->addSuccessor(Succ);
2225     }
2226   }
2227 
2228   ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
2229   ToBBI.Predicate.append(Cond.begin(), Cond.end());
2230 
2231   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
2232   ToBBI.IsAnalyzed = false;
2233 
2234   ++NumDupBBs;
2235 }
2236 
2237 /// Move all instructions from FromBB to the end of ToBB.  This will leave
2238 /// FromBB as an empty block, so remove all of its successor edges and move it
2239 /// to the end of the function.  If AddEdges is true, i.e., when FromBBI's
2240 /// branch is being moved, add those successor edges to ToBBI and remove the old
2241 /// edge from ToBBI to FromBBI.
2242 void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
2243   MachineBasicBlock &FromMBB = *FromBBI.BB;
2244   assert(!FromMBB.hasAddressTaken() &&
2245          "Removing a BB whose address is taken!");
2246 
2247   // If we're about to splice an INLINEASM_BR from FromBBI, we need to update
2248   // ToBBI's successor list accordingly.
2249   if (FromMBB.mayHaveInlineAsmBr())
2250     for (MachineInstr &MI : FromMBB)
2251       if (MI.getOpcode() == TargetOpcode::INLINEASM_BR)
2252         for (MachineOperand &MO : MI.operands())
2253           if (MO.isMBB() && !ToBBI.BB->isSuccessor(MO.getMBB()))
2254             ToBBI.BB->addSuccessor(MO.getMBB(), BranchProbability::getZero());
2255 
2256   // In case FromMBB contains terminators (e.g. return instruction),
2257   // first move the non-terminator instructions, then the terminators.
2258   MachineBasicBlock::iterator FromTI = FromMBB.getFirstTerminator();
2259   MachineBasicBlock::iterator ToTI = ToBBI.BB->getFirstTerminator();
2260   ToBBI.BB->splice(ToTI, &FromMBB, FromMBB.begin(), FromTI);
2261 
2262   // If FromBB has non-predicated terminator we should copy it at the end.
2263   if (FromTI != FromMBB.end() && !TII->isPredicated(*FromTI))
2264     ToTI = ToBBI.BB->end();
2265   ToBBI.BB->splice(ToTI, &FromMBB, FromTI, FromMBB.end());
2266 
2267   // Force normalizing the successors' probabilities of ToBBI.BB to convert all
2268   // unknown probabilities into known ones.
2269   // FIXME: This usage is too tricky and in the future we would like to
2270   // eliminate all unknown probabilities in MBB.
2271   if (ToBBI.IsBrAnalyzable)
2272     ToBBI.BB->normalizeSuccProbs();
2273 
2274   SmallVector<MachineBasicBlock *, 4> FromSuccs(FromMBB.successors());
2275   MachineBasicBlock *NBB = getNextBlock(FromMBB);
2276   MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;
2277   // The edge probability from ToBBI.BB to FromMBB, which is only needed when
2278   // AddEdges is true and FromMBB is a successor of ToBBI.BB.
2279   auto To2FromProb = BranchProbability::getZero();
2280   if (AddEdges && ToBBI.BB->isSuccessor(&FromMBB)) {
2281     // Remove the old edge but remember the edge probability so we can calculate
2282     // the correct weights on the new edges being added further down.
2283     To2FromProb = MBPI->getEdgeProbability(ToBBI.BB, &FromMBB);
2284     ToBBI.BB->removeSuccessor(&FromMBB);
2285   }
2286 
2287   for (MachineBasicBlock *Succ : FromSuccs) {
2288     // Fallthrough edge can't be transferred.
2289     if (Succ == FallThrough) {
2290       FromMBB.removeSuccessor(Succ);
2291       continue;
2292     }
2293 
2294     auto NewProb = BranchProbability::getZero();
2295     if (AddEdges) {
2296       // Calculate the edge probability for the edge from ToBBI.BB to Succ,
2297       // which is a portion of the edge probability from FromMBB to Succ. The
2298       // portion ratio is the edge probability from ToBBI.BB to FromMBB (if
2299       // FromBBI is a successor of ToBBI.BB. See comment below for exception).
2300       NewProb = MBPI->getEdgeProbability(&FromMBB, Succ);
2301 
2302       // To2FromProb is 0 when FromMBB is not a successor of ToBBI.BB. This
2303       // only happens when if-converting a diamond CFG and FromMBB is the
2304       // tail BB.  In this case FromMBB post-dominates ToBBI.BB and hence we
2305       // could just use the probabilities on FromMBB's out-edges when adding
2306       // new successors.
2307       if (!To2FromProb.isZero())
2308         NewProb *= To2FromProb;
2309     }
2310 
2311     FromMBB.removeSuccessor(Succ);
2312 
2313     if (AddEdges) {
2314       // If the edge from ToBBI.BB to Succ already exists, update the
2315       // probability of this edge by adding NewProb to it. An example is shown
2316       // below, in which A is ToBBI.BB and B is FromMBB. In this case we
2317       // don't have to set C as A's successor as it already is. We only need to
2318       // update the edge probability on A->C. Note that B will not be
2319       // immediately removed from A's successors. It is possible that B->D is
2320       // not removed either if D is a fallthrough of B. Later the edge A->D
2321       // (generated here) and B->D will be combined into one edge. To maintain
2322       // correct edge probability of this combined edge, we need to set the edge
2323       // probability of A->B to zero, which is already done above. The edge
2324       // probability on A->D is calculated by scaling the original probability
2325       // on A->B by the probability of B->D.
2326       //
2327       // Before ifcvt:      After ifcvt (assume B->D is kept):
2328       //
2329       //       A                A
2330       //      /|               /|\
2331       //     / B              / B|
2332       //    | /|             |  ||
2333       //    |/ |             |  |/
2334       //    C  D             C  D
2335       //
2336       if (ToBBI.BB->isSuccessor(Succ))
2337         ToBBI.BB->setSuccProbability(
2338             find(ToBBI.BB->successors(), Succ),
2339             MBPI->getEdgeProbability(ToBBI.BB, Succ) + NewProb);
2340       else
2341         ToBBI.BB->addSuccessor(Succ, NewProb);
2342     }
2343   }
2344 
2345   // Move the now empty FromMBB out of the way to the end of the function so
2346   // it doesn't interfere with fallthrough checks done by canFallThroughTo().
2347   MachineBasicBlock *Last = &*FromMBB.getParent()->rbegin();
2348   if (Last != &FromMBB)
2349     FromMBB.moveAfter(Last);
2350 
2351   // Normalize the probabilities of ToBBI.BB's successors with all adjustment
2352   // we've done above.
2353   if (ToBBI.IsBrAnalyzable && FromBBI.IsBrAnalyzable)
2354     ToBBI.BB->normalizeSuccProbs();
2355 
2356   ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
2357   FromBBI.Predicate.clear();
2358 
2359   ToBBI.NonPredSize += FromBBI.NonPredSize;
2360   ToBBI.ExtraCost += FromBBI.ExtraCost;
2361   ToBBI.ExtraCost2 += FromBBI.ExtraCost2;
2362   FromBBI.NonPredSize = 0;
2363   FromBBI.ExtraCost = 0;
2364   FromBBI.ExtraCost2 = 0;
2365 
2366   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
2367   ToBBI.HasFallThrough = FromBBI.HasFallThrough;
2368   ToBBI.IsAnalyzed = false;
2369   FromBBI.IsAnalyzed = false;
2370 }
2371 
2372 FunctionPass *
2373 llvm::createIfConverter(std::function<bool(const MachineFunction &)> Ftor) {
2374   return new IfConverter(std::move(Ftor));
2375 }
2376