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