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