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