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