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