LLVM  16.0.0git
IfConversion.cpp
Go to the documentation of this file.
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"
39 #include "llvm/IR/DebugLoc.h"
40 #include "llvm/InitializePasses.h"
41 #include "llvm/MC/MCRegisterInfo.h"
42 #include "llvm/Pass.h"
45 #include "llvm/Support/Debug.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;
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;
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)) {
211  }
212 
213  void getAnalysisUsage(AnalysisUsage &AU) const override {
218  }
219 
220  bool runOnMachineFunction(MachineFunction &MF) override;
221 
222  MachineFunctionProperties getRequiredProperties() const override {
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(
237  unsigned &Dups1, unsigned &Dups2,
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,
250  bool BranchUnpredicable = false) const;
251  bool RescanInstructions(
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,
278  SmallSet<MCPhysReg, 4> *LaterRedefs = nullptr);
279  void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
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 &&
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 
435 
436 INITIALIZE_PASS_BEGIN(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.
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.
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(
738  unsigned &Dups1, unsigned &Dups2,
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(
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
832  MachineBasicBlock *MBB1,
833  MachineBasicBlock *MBB2) {
834  const MachineBasicBlock::reverse_iterator B1 = MBB1->rend();
835  const MachineBasicBlock::reverse_iterator B2 = MBB2->rend();
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,
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,
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) {
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) {}
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 
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).
1443  MachineFunction::iterator I = std::next(PI);
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.
1471  const TargetInstrInfo *TII) {
1472  DebugLoc dl; // FIXME: this is nowhere
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.
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.
1486  LiveBeforeMI.setUniverse(TRI->getNumRegs());
1487  for (unsigned Reg : Redefs)
1488  LiveBeforeMI.insert(Reg);
1489 
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))
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.
1513  continue;
1514  }
1515  if (LiveBeforeMI.count(Reg))
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)
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)
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)
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.
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)) {
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;
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())) {
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) {
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,
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,
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 
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  // In case FromMBB contains terminators (e.g. return instruction),
2248  // first move the non-terminator instructions, then the terminators.
2250  MachineBasicBlock::iterator ToTI = ToBBI.BB->getFirstTerminator();
2251  ToBBI.BB->splice(ToTI, &FromMBB, FromMBB.begin(), FromTI);
2252 
2253  // If FromBB has non-predicated terminator we should copy it at the end.
2254  if (FromTI != FromMBB.end() && !TII->isPredicated(*FromTI))
2255  ToTI = ToBBI.BB->end();
2256  ToBBI.BB->splice(ToTI, &FromMBB, FromTI, FromMBB.end());
2257 
2258  // Force normalizing the successors' probabilities of ToBBI.BB to convert all
2259  // unknown probabilities into known ones.
2260  // FIXME: This usage is too tricky and in the future we would like to
2261  // eliminate all unknown probabilities in MBB.
2262  if (ToBBI.IsBrAnalyzable)
2263  ToBBI.BB->normalizeSuccProbs();
2264 
2265  SmallVector<MachineBasicBlock *, 4> FromSuccs(FromMBB.successors());
2266  MachineBasicBlock *NBB = getNextBlock(FromMBB);
2267  MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;
2268  // The edge probability from ToBBI.BB to FromMBB, which is only needed when
2269  // AddEdges is true and FromMBB is a successor of ToBBI.BB.
2270  auto To2FromProb = BranchProbability::getZero();
2271  if (AddEdges && ToBBI.BB->isSuccessor(&FromMBB)) {
2272  // Remove the old edge but remember the edge probability so we can calculate
2273  // the correct weights on the new edges being added further down.
2274  To2FromProb = MBPI->getEdgeProbability(ToBBI.BB, &FromMBB);
2275  ToBBI.BB->removeSuccessor(&FromMBB);
2276  }
2277 
2278  for (MachineBasicBlock *Succ : FromSuccs) {
2279  // Fallthrough edge can't be transferred.
2280  if (Succ == FallThrough) {
2281  FromMBB.removeSuccessor(Succ);
2282  continue;
2283  }
2284 
2285  auto NewProb = BranchProbability::getZero();
2286  if (AddEdges) {
2287  // Calculate the edge probability for the edge from ToBBI.BB to Succ,
2288  // which is a portion of the edge probability from FromMBB to Succ. The
2289  // portion ratio is the edge probability from ToBBI.BB to FromMBB (if
2290  // FromBBI is a successor of ToBBI.BB. See comment below for exception).
2291  NewProb = MBPI->getEdgeProbability(&FromMBB, Succ);
2292 
2293  // To2FromProb is 0 when FromMBB is not a successor of ToBBI.BB. This
2294  // only happens when if-converting a diamond CFG and FromMBB is the
2295  // tail BB. In this case FromMBB post-dominates ToBBI.BB and hence we
2296  // could just use the probabilities on FromMBB's out-edges when adding
2297  // new successors.
2298  if (!To2FromProb.isZero())
2299  NewProb *= To2FromProb;
2300  }
2301 
2302  FromMBB.removeSuccessor(Succ);
2303 
2304  if (AddEdges) {
2305  // If the edge from ToBBI.BB to Succ already exists, update the
2306  // probability of this edge by adding NewProb to it. An example is shown
2307  // below, in which A is ToBBI.BB and B is FromMBB. In this case we
2308  // don't have to set C as A's successor as it already is. We only need to
2309  // update the edge probability on A->C. Note that B will not be
2310  // immediately removed from A's successors. It is possible that B->D is
2311  // not removed either if D is a fallthrough of B. Later the edge A->D
2312  // (generated here) and B->D will be combined into one edge. To maintain
2313  // correct edge probability of this combined edge, we need to set the edge
2314  // probability of A->B to zero, which is already done above. The edge
2315  // probability on A->D is calculated by scaling the original probability
2316  // on A->B by the probability of B->D.
2317  //
2318  // Before ifcvt: After ifcvt (assume B->D is kept):
2319  //
2320  // A A
2321  // /| /|\
2322  // / B / B|
2323  // | /| | ||
2324  // |/ | | |/
2325  // C D C D
2326  //
2327  if (ToBBI.BB->isSuccessor(Succ))
2328  ToBBI.BB->setSuccProbability(
2329  find(ToBBI.BB->successors(), Succ),
2330  MBPI->getEdgeProbability(ToBBI.BB, Succ) + NewProb);
2331  else
2332  ToBBI.BB->addSuccessor(Succ, NewProb);
2333  }
2334  }
2335 
2336  // Move the now empty FromMBB out of the way to the end of the function so
2337  // it doesn't interfere with fallthrough checks done by canFallThroughTo().
2338  MachineBasicBlock *Last = &*FromMBB.getParent()->rbegin();
2339  if (Last != &FromMBB)
2340  FromMBB.moveAfter(Last);
2341 
2342  // Normalize the probabilities of ToBBI.BB's successors with all adjustment
2343  // we've done above.
2344  if (ToBBI.IsBrAnalyzable && FromBBI.IsBrAnalyzable)
2345  ToBBI.BB->normalizeSuccProbs();
2346 
2347  ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
2348  FromBBI.Predicate.clear();
2349 
2350  ToBBI.NonPredSize += FromBBI.NonPredSize;
2351  ToBBI.ExtraCost += FromBBI.ExtraCost;
2352  ToBBI.ExtraCost2 += FromBBI.ExtraCost2;
2353  FromBBI.NonPredSize = 0;
2354  FromBBI.ExtraCost = 0;
2355  FromBBI.ExtraCost2 = 0;
2356 
2357  ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
2358  ToBBI.HasFallThrough = FromBBI.HasFallThrough;
2359  ToBBI.IsAnalyzed = false;
2360  FromBBI.IsAnalyzed = false;
2361 }
2362 
2363 FunctionPass *
2365  return new IfConverter(std::move(Ftor));
2366 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
llvm::BranchFolder
Definition: BranchFolding.h:31
i
i
Definition: README.txt:29
IfCvtLimit
static cl::opt< int > IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden)
llvm::MachineBasicBlock::pred_begin
pred_iterator pred_begin()
Definition: MachineBasicBlock.h:357
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::TargetLoweringBase
This base class for TargetLowering contains the SelectionDAG-independent parts that can be used from ...
Definition: TargetLowering.h:191
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::ARM::PredBlockMask::TT
@ TT
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::HexagonInstrInfo::removeBranch
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
Definition: HexagonInstrInfo.cpp:604
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::PseudoProbeReservedId::Last
@ Last
llvm::recomputeLivenessFlags
void recomputeLivenessFlags(MachineBasicBlock &MBB)
Recomputes dead and kill flags in MBB.
Definition: LivePhysRegs.cpp:281
Pass.h
llvm::HexagonInstrInfo::analyzeBranch
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
Definition: HexagonInstrInfo.cpp:434
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:859
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:118
ErrorHandling.h
llvm::MachineFunction::copyCallSiteInfo
void copyCallSiteInfo(const MachineInstr *Old, const MachineInstr *New)
Copy the call site info from Old to \ New.
Definition: MachineFunction.cpp:944
llvm::MCRegisterInfo::getNumRegs
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Definition: MCRegisterInfo.h:491
llvm::LivePhysRegs::addLiveInsNoPristines
void addLiveInsNoPristines(const MachineBasicBlock &MBB)
Adds all live-in registers of basic block MBB but skips pristine registers.
Definition: LivePhysRegs.cpp:244
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::RegState::Define
@ Define
Register definition.
Definition: MachineInstrBuilder.h:44
MachineBasicBlock.h
llvm::LivePhysRegs
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:236
DisableSimple
static cl::opt< bool > DisableSimple("disable-ifcvt-simple", cl::init(false), cl::Hidden)
llvm::BranchProbability::getZero
static BranchProbability getZero()
Definition: BranchProbability.h:49
TargetInstrInfo.h
llvm::HexagonInstrInfo::isPredicated
bool isPredicated(const MachineInstr &MI) const override
Returns true if the instruction is already predicated.
Definition: HexagonInstrInfo.cpp:1660
DisableTriangleF
static cl::opt< bool > DisableTriangleF("disable-ifcvt-triangle-false", cl::init(false), cl::Hidden)
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
MBFIWrapper.h
llvm::MachineInstr::getMF
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
Definition: MachineInstr.cpp:677
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:127
canFallThroughTo
static bool canFallThroughTo(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB)
Returns true either if ToMBB is the next block after MBB or that all the intervening blocks are empty...
Definition: IfConversion.cpp:1441
llvm::HexagonInstrInfo::ClobbersPredicate
bool ClobbersPredicate(MachineInstr &MI, std::vector< MachineOperand > &Pred, bool SkipDead) const override
If the specified instruction defines any predicate or condition code register(s) used for predication...
Definition: HexagonInstrInfo.cpp:1723
STLExtras.h
llvm::MachineBasicBlock::terminators
iterator_range< iterator > terminators()
Definition: MachineBasicBlock.h:329
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DisableTriangleFR
static cl::opt< bool > DisableTriangleFR("disable-ifcvt-triangle-false-rev", cl::init(false), cl::Hidden)
llvm::HexagonInstrInfo::isPredicable
bool isPredicable(const MachineInstr &MI) const override
Return true if the specified instruction can be predicated.
Definition: HexagonInstrInfo.cpp:1750
MachineRegisterInfo.h
llvm::MachineBasicBlock::erase
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
Definition: MachineBasicBlock.cpp:1324
llvm::MachineRegisterInfo::tracksLiveness
bool tracksLiveness() const
tracksLiveness - Returns true when tracking register liveness accurately.
Definition: MachineRegisterInfo.h:195
llvm::TargetSchedModel::init
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
Definition: TargetSchedule.cpp:47
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:369
TargetLowering.h
DisableTriangle
static cl::opt< bool > DisableTriangle("disable-ifcvt-triangle", cl::init(false), cl::Hidden)
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
DisableForkedDiamond
static cl::opt< bool > DisableForkedDiamond("disable-ifcvt-forked-diamond", cl::init(false), cl::Hidden)
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::ARM_MC::isPredicated
bool isPredicated(const MCInst &MI, const MCInstrInfo *MCII)
Definition: ARMMCTargetDesc.cpp:170
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::MachineBranchProbabilityInfo
Definition: MachineBranchProbabilityInfo.h:22
DisableTriangleR
static cl::opt< bool > DisableTriangleR("disable-ifcvt-triangle-rev", cl::init(false), cl::Hidden)
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
DisableDiamond
static cl::opt< bool > DisableDiamond("disable-ifcvt-diamond", cl::init(false), cl::Hidden)
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
TBB
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
Definition: RISCVRedundantCopyElimination.cpp:76
false
Definition: StackSlotColoring.cpp:141
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::MachineFunction::rbegin
reverse_iterator rbegin()
Definition: MachineFunction.h:862
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:196
llvm::GenericCycle
A possibly irreducible generalization of a Loop.
Definition: GenericCycleInfo.h:48
llvm::MachineBasicBlock::rend
reverse_iterator rend()
Definition: MachineBasicBlock.h:319
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::HexagonInstrInfo::insertBranch
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
Definition: HexagonInstrInfo.cpp:627
llvm::tgtok::If
@ If
Definition: TGLexer.h:51
DebugLoc.h
BranchFolding.h
llvm::MBFIWrapper
Definition: MBFIWrapper.h:27
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
BranchProbability.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
findFalseBlock
static MachineBasicBlock * findFalseBlock(MachineBasicBlock *BB, MachineBasicBlock *TrueBB)
BB has a fallthrough. Find its 'false' successor given its 'true' successor.
Definition: IfConversion.cpp:611
IfCvtFnStop
static cl::opt< int > IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden)
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:40
llvm::MachineRegisterInfo::isSSA
bool isSSA() const
Definition: MachineRegisterInfo.h:183
llvm::MachineFunctionProperties::Property::NoVRegs
@ NoVRegs
verifySameBranchInstructions
static void verifySameBranchInstructions(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2)
Definition: IfConversion.cpp:831
llvm::cl::opt
Definition: CommandLine.h:1411
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::SmallSet::count
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:165
TargetSchedule.h
llvm::MachineInstrBundleIterator::getReverse
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
Definition: MachineInstrBundleIterator.h:283
llvm::TargetSchedModel
Provide an instruction scheduling machine model to CodeGen passes.
Definition: TargetSchedule.h:30
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MachineInstrBuilder
Definition: MachineInstrBuilder.h:69
llvm::HexagonInstrInfo::isProfitableToDupForIfCvt
bool isProfitableToDupForIfCvt(MachineBasicBlock &MBB, unsigned NumCycles, BranchProbability Probability) const override
Return true if it's profitable for if-converter to duplicate instructions of specified accumulated in...
Definition: HexagonInstrInfo.cpp:831
ProfileSummaryInfo.h
llvm::MachineBasicBlock::hasAddressTaken
bool hasAddressTaken() const
Test whether this block is used as as something other than the target of a terminator,...
Definition: MachineBasicBlock.h:231
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1754
llvm::MachineFunction::CloneMachineInstr
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
Definition: MachineFunction.cpp:383
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
s
multiplies can be turned into SHL s
Definition: README.txt:370
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
IfCvtBranchFold
static cl::opt< bool > IfCvtBranchFold("ifcvt-branch-fold", cl::init(true), cl::Hidden)
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MCPhysReg
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:21
UpdatePredRedefs
static void UpdatePredRedefs(MachineInstr &MI, LivePhysRegs &Redefs)
Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all values defined in MI whic...
Definition: IfConversion.cpp:1479
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:446
MCRegisterInfo.h
llvm::ProfileSummaryInfoWrapperPass
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:194
MachineFunctionPass.h
llvm::MachineBasicBlock::pred_iterator
std::vector< MachineBasicBlock * >::iterator pred_iterator
Definition: MachineBasicBlock.h:345
llvm::SparseSet::setUniverse
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
Definition: SparseSet.h:155
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1861
MachineBranchProbabilityInfo.h
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
Converter
Early If Converter
Definition: EarlyIfConversion.cpp:790
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:265
iterator_range.h
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
MaySpeculate
static bool MaySpeculate(const MachineInstr &MI, SmallSet< MCPhysReg, 4 > &LaterRedefs)
Definition: IfConversion.cpp:2112
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:390
llvm::MachineBranchProbabilityInfo::getEdgeProbability
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Definition: MachineBranchProbabilityInfo.cpp:56
llvm::BranchFolder::OptimizeFunction
bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii, const TargetRegisterInfo *tri, MachineLoopInfo *mli=nullptr, bool AfterPlacement=false)
Perhaps branch folding, tail merging and other CFG optimizations on the given function.
Definition: BranchFolding.cpp:182
llvm::initializeIfConverterPass
void initializeIfConverterPass(PassRegistry &)
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::BranchProbability::getOne
static BranchProbability getOne()
Definition: BranchProbability.h:50
llvm::MachineBasicBlock::moveAfter
void moveAfter(MachineBasicBlock *NewBefore)
Definition: MachineBasicBlock.cpp:663
llvm::MachineBasicBlock::succ_empty
bool succ_empty() const
Definition: MachineBasicBlock.h:388
llvm::NVPTXISD::Dummy
@ Dummy
Definition: NVPTXISelLowering.h:60
llvm::MachineBasicBlock::getFirstTerminator
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Definition: MachineBasicBlock.cpp:240
llvm::skipDebugInstructionsForward
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
Definition: MachineBasicBlock.h:1288
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1138
DisableSimpleF
static cl::opt< bool > DisableSimpleF("disable-ifcvt-simple-false", cl::init(false), cl::Hidden)
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:396
llvm::MachineBasicBlock::getFirstNonDebugInstr
iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the first non-debug instruction in the basic block, or end().
Definition: MachineBasicBlock.cpp:263
llvm::MachineBasicBlock::rbegin
reverse_iterator rbegin()
Definition: MachineBasicBlock.h:313
llvm::LivePhysRegs::init
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
Definition: LivePhysRegs.h:68
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::RegState::Implicit
@ Implicit
Not emitted register (e.g. carry, or temporary result).
Definition: MachineInstrBuilder.h:46
llvm::BranchProbability
Definition: BranchProbability.h:30
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
TargetSubtargetInfo.h
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::LivePhysRegs::stepForward
void stepForward(const MachineInstr &MI, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand * >> &Clobbers)
Simulates liveness when stepping forward over an instruction(bundle).
Definition: LivePhysRegs.cpp:80
SparseSet.h
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:62
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::make_scope_exit
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
IfCvtFnStart
static cl::opt< int > IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden)
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1947
llvm::SparseSet::insert
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
Definition: SparseSet.h:252
std
Definition: BitVector.h:851
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:626
llvm::MachineBasicBlock::removeSuccessor
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:810
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:351
DEBUG_TYPE
#define DEBUG_TYPE
Definition: IfConversion.cpp:58
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::SparseSet::count
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise.
Definition: SparseSet.h:240
llvm::SmallSet::insert
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:178
llvm::createIfConverter
FunctionPass * createIfConverter(std::function< bool(const MachineFunction &)> Ftor)
Definition: IfConversion.cpp:2364
llvm::BranchProbability::getCompl
BranchProbability getCompl() const
Definition: BranchProbability.h:69
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:597
llvm::HexagonInstrInfo::reverseBranchCondition
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
Definition: HexagonInstrInfo.cpp:1627
INITIALIZE_PASS_BEGIN
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:51
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:309
MachineInstrBuilder.h
llvm::HexagonInstrInfo::SubsumesPredicate
bool SubsumesPredicate(ArrayRef< MachineOperand > Pred1, ArrayRef< MachineOperand > Pred2) const override
Returns true if the first specified predicate subsumes the second, e.g.
Definition: HexagonInstrInfo.cpp:1717
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
llvm::HexagonInstrInfo::isProfitableToIfCvt
bool isProfitableToIfCvt(MachineBasicBlock &MBB, unsigned NumCycles, unsigned ExtraPredCycles, BranchProbability Probability) const override
Return true if it's profitable to predicate instructions with accumulated instruction latency of "Num...
Definition: HexagonInstrInfo.cpp:818
InsertUncondBranch
static void InsertUncondBranch(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB, const TargetInstrInfo *TII)
Inserts an unconditional branch from MBB to ToMBB.
Definition: IfConversion.cpp:1470
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:281
ScopeExit.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
MachineOperand.h
llvm::SparseSet
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
Definition: SparseSet.h:124
llvm::Function::hasMinSize
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:642
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
getNextBlock
static MachineBasicBlock * getNextBlock(MachineBasicBlock &MBB)
Returns the next block in the function blocks ordering.
Definition: IfConversion.cpp:635
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
raw_ostream.h
d
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int int d
Definition: README.txt:418
llvm::IfConverterID
char & IfConverterID
IfConverter - This pass performs machine code if conversion.
Definition: IfConversion.cpp:434
MachineFunction.h
llvm::MachineFunction::eraseCallSiteInfo
void eraseCallSiteInfo(const MachineInstr *MI)
Following functions update call site info.
Definition: MachineFunction.cpp:932
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::HexagonInstrInfo::PredicateInstruction
bool PredicateInstruction(MachineInstr &MI, ArrayRef< MachineOperand > Cond) const override
Convert the instruction into a predicated instruction.
Definition: HexagonInstrInfo.cpp:1665
InitializePasses.h
MachineBlockFrequencyInfo.h
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:311
SmallSet.h
LivePhysRegs.h