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