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