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