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