1	//===- InstCombineSelect.cpp ----------------------------------------------===//
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 visitSelect function.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "InstCombineInternal.h"
14	#include "llvm/ADT/APInt.h"
15	#include "llvm/ADT/STLExtras.h"
16	#include "llvm/ADT/SmallVector.h"
17	#include "llvm/Analysis/AssumptionCache.h"
18	#include "llvm/Analysis/CmpInstAnalysis.h"
19	#include "llvm/Analysis/InstructionSimplify.h"
20	#include "llvm/Analysis/OverflowInstAnalysis.h"
21	#include "llvm/Analysis/ValueTracking.h"
22	#include "llvm/Analysis/VectorUtils.h"
23	#include "llvm/IR/BasicBlock.h"
24	#include "llvm/IR/Constant.h"
25	#include "llvm/IR/ConstantRange.h"
26	#include "llvm/IR/Constants.h"
27	#include "llvm/IR/DerivedTypes.h"
28	#include "llvm/IR/IRBuilder.h"
29	#include "llvm/IR/InstrTypes.h"
30	#include "llvm/IR/Instruction.h"
31	#include "llvm/IR/Instructions.h"
32	#include "llvm/IR/IntrinsicInst.h"
33	#include "llvm/IR/Intrinsics.h"
34	#include "llvm/IR/Operator.h"
35	#include "llvm/IR/PatternMatch.h"
36	#include "llvm/IR/Type.h"
37	#include "llvm/IR/User.h"
38	#include "llvm/IR/Value.h"
39	#include "llvm/Support/Casting.h"
40	#include "llvm/Support/ErrorHandling.h"
41	#include "llvm/Support/KnownBits.h"
42	#include "llvm/Transforms/InstCombine/InstCombiner.h"
43	#include <cassert>
44	#include <utility>
45
46	#define DEBUG_TYPE "instcombine"
47	#include "llvm/Transforms/Utils/InstructionWorklist.h"
48
49	using namespace llvm;
50	using namespace PatternMatch;
51
52
53	/// Replace a select operand based on an equality comparison with the identity
54	/// constant of a binop.
55	static Instruction *foldSelectBinOpIdentity(SelectInst &Sel,
56	const TargetLibraryInfo &TLI,
57	InstCombinerImpl &IC) {
58	// The select condition must be an equality compare with a constant operand.
59	Value *X;
60	Constant *C;
61	CmpInst::Predicate Pred;
62	if (!match(V: Sel.getCondition(), P: m_Cmp(Pred, L: m_Value(V&: X), R: m_Constant(C))))
63	return nullptr;
64
65	bool IsEq;
66	if (ICmpInst::isEquality(P: Pred))
67	IsEq = Pred == ICmpInst::ICMP_EQ;
68	else if (Pred == FCmpInst::FCMP_OEQ)
69	IsEq = true;
70	else if (Pred == FCmpInst::FCMP_UNE)
71	IsEq = false;
72	else
73	return nullptr;
74
75	// A select operand must be a binop.
76	BinaryOperator *BO;
77	if (!match(V: Sel.getOperand(i_nocapture: IsEq ? 1 : 2), P: m_BinOp(I&: BO)))
78	return nullptr;
79
80	// The compare constant must be the identity constant for that binop.
81	// If this a floating-point compare with 0.0, any zero constant will do.
82	Type *Ty = BO->getType();
83	Constant *IdC = ConstantExpr::getBinOpIdentity(Opcode: BO->getOpcode(), Ty, AllowRHSConstant: true);
84	if (IdC != C) {
85	if (!IdC || !CmpInst::isFPPredicate(P: Pred))
86	return nullptr;
87	if (!match(V: IdC, P: m_AnyZeroFP()) || !match(V: C, P: m_AnyZeroFP()))
88	return nullptr;
89	}
90
91	// Last, match the compare variable operand with a binop operand.
92	Value *Y;
93	if (!BO->isCommutative() && !match(V: BO, P: m_BinOp(L: m_Value(V&: Y), R: m_Specific(V: X))))
94	return nullptr;
95	if (!match(V: BO, P: m_c_BinOp(L: m_Value(V&: Y), R: m_Specific(V: X))))
96	return nullptr;
97
98	// +0.0 compares equal to -0.0, and so it does not behave as required for this
99	// transform. Bail out if we can not exclude that possibility.
100	if (isa<FPMathOperator>(Val: BO))
101	if (!BO->hasNoSignedZeros() &&
102	!cannotBeNegativeZero(V: Y, Depth: 0,
103	SQ: IC.getSimplifyQuery().getWithInstruction(I: &Sel)))
104	return nullptr;
105
106	// BO = binop Y, X
107	// S = { select (cmp eq X, C), BO, ? } or { select (cmp ne X, C), ?, BO }
108	// =>
109	// S = { select (cmp eq X, C), Y, ? } or { select (cmp ne X, C), ?, Y }
110	return IC.replaceOperand(I&: Sel, OpNum: IsEq ? 1 : 2, V: Y);
111	}
112
113	/// This folds:
114	/// select (icmp eq (and X, C1)), TC, FC
115	/// iff C1 is a power 2 and the difference between TC and FC is a power-of-2.
116	/// To something like:
117	/// (shr (and (X, C1)), (log2(C1) - log2(TC-FC))) + FC
118	/// Or:
119	/// (shl (and (X, C1)), (log2(TC-FC) - log2(C1))) + FC
120	/// With some variations depending if FC is larger than TC, or the shift
121	/// isn't needed, or the bit widths don't match.
122	static Value *foldSelectICmpAnd(SelectInst &Sel, ICmpInst *Cmp,
123	InstCombiner::BuilderTy &Builder) {
124	const APInt *SelTC, *SelFC;
125	if (!match(V: Sel.getTrueValue(), P: m_APInt(Res&: SelTC)) ||
126	!match(V: Sel.getFalseValue(), P: m_APInt(Res&: SelFC)))
127	return nullptr;
128
129	// If this is a vector select, we need a vector compare.
130	Type *SelType = Sel.getType();
131	if (SelType->isVectorTy() != Cmp->getType()->isVectorTy())
132	return nullptr;
133
134	Value *V;
135	APInt AndMask;
136	bool CreateAnd = false;
137	ICmpInst::Predicate Pred = Cmp->getPredicate();
138	if (ICmpInst::isEquality(P: Pred)) {
139	if (!match(V: Cmp->getOperand(i_nocapture: 1), P: m_Zero()))
140	return nullptr;
141
142	V = Cmp->getOperand(i_nocapture: 0);
143	const APInt *AndRHS;
144	if (!match(V, P: m_And(L: m_Value(), R: m_Power2(V&: AndRHS))))
145	return nullptr;
146
147	AndMask = *AndRHS;
148	} else if (decomposeBitTestICmp(LHS: Cmp->getOperand(i_nocapture: 0), RHS: Cmp->getOperand(i_nocapture: 1),
149	Pred, X&: V, Mask&: AndMask)) {
150	assert(ICmpInst::isEquality(Pred) && "Not equality test?");
151	if (!AndMask.isPowerOf2())
152	return nullptr;
153
154	CreateAnd = true;
155	} else {
156	return nullptr;
157	}
158
159	// In general, when both constants are non-zero, we would need an offset to
160	// replace the select. This would require more instructions than we started
161	// with. But there's one special-case that we handle here because it can
162	// simplify/reduce the instructions.
163	APInt TC = *SelTC;
164	APInt FC = *SelFC;
165	if (!TC.isZero() && !FC.isZero()) {
166	// If the select constants differ by exactly one bit and that's the same
167	// bit that is masked and checked by the select condition, the select can
168	// be replaced by bitwise logic to set/clear one bit of the constant result.
169	if (TC.getBitWidth() != AndMask.getBitWidth() || (TC ^ FC) != AndMask)
170	return nullptr;
171	if (CreateAnd) {
172	// If we have to create an 'and', then we must kill the cmp to not
173	// increase the instruction count.
174	if (!Cmp->hasOneUse())
175	return nullptr;
176	V = Builder.CreateAnd(LHS: V, RHS: ConstantInt::get(Ty: SelType, V: AndMask));
177	}
178	bool ExtraBitInTC = TC.ugt(RHS: FC);
179	if (Pred == ICmpInst::ICMP_EQ) {
180	// If the masked bit in V is clear, clear or set the bit in the result:
181	// (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) ^ TC
182	// (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) | TC
183	Constant *C = ConstantInt::get(Ty: SelType, V: TC);
184	return ExtraBitInTC ? Builder.CreateXor(LHS: V, RHS: C) : Builder.CreateOr(LHS: V, RHS: C);
185	}
186	if (Pred == ICmpInst::ICMP_NE) {
187	// If the masked bit in V is set, set or clear the bit in the result:
188	// (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) | FC
189	// (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) ^ FC
190	Constant *C = ConstantInt::get(Ty: SelType, V: FC);
191	return ExtraBitInTC ? Builder.CreateOr(LHS: V, RHS: C) : Builder.CreateXor(LHS: V, RHS: C);
192	}
193	llvm_unreachable("Only expecting equality predicates");
194	}
195
196	// Make sure one of the select arms is a power-of-2.
197	if (!TC.isPowerOf2() && !FC.isPowerOf2())
198	return nullptr;
199
200	// Determine which shift is needed to transform result of the 'and' into the
201	// desired result.
202	const APInt &ValC = !TC.isZero() ? TC : FC;
203	unsigned ValZeros = ValC.logBase2();
204	unsigned AndZeros = AndMask.logBase2();
205
206	// Insert the 'and' instruction on the input to the truncate.
207	if (CreateAnd)
208	V = Builder.CreateAnd(LHS: V, RHS: ConstantInt::get(Ty: V->getType(), V: AndMask));
209
210	// If types don't match, we can still convert the select by introducing a zext
211	// or a trunc of the 'and'.
212	if (ValZeros > AndZeros) {
213	V = Builder.CreateZExtOrTrunc(V, DestTy: SelType);
214	V = Builder.CreateShl(LHS: V, RHS: ValZeros - AndZeros);
215	} else if (ValZeros < AndZeros) {
216	V = Builder.CreateLShr(LHS: V, RHS: AndZeros - ValZeros);
217	V = Builder.CreateZExtOrTrunc(V, DestTy: SelType);
218	} else {
219	V = Builder.CreateZExtOrTrunc(V, DestTy: SelType);
220	}
221
222	// Okay, now we know that everything is set up, we just don't know whether we
223	// have a icmp_ne or icmp_eq and whether the true or false val is the zero.
224	bool ShouldNotVal = !TC.isZero();
225	ShouldNotVal ^= Pred == ICmpInst::ICMP_NE;
226	if (ShouldNotVal)
227	V = Builder.CreateXor(LHS: V, RHS: ValC);
228
229	return V;
230	}
231
232	/// We want to turn code that looks like this:
233	/// %C = or %A, %B
234	/// %D = select %cond, %C, %A
235	/// into:
236	/// %C = select %cond, %B, 0
237	/// %D = or %A, %C
238	///
239	/// Assuming that the specified instruction is an operand to the select, return
240	/// a bitmask indicating which operands of this instruction are foldable if they
241	/// equal the other incoming value of the select.
242	static unsigned getSelectFoldableOperands(BinaryOperator *I) {
243	switch (I->getOpcode()) {
244	case Instruction::Add:
245	case Instruction::FAdd:
246	case Instruction::Mul:
247	case Instruction::FMul:
248	case Instruction::And:
249	case Instruction::Or:
250	case Instruction::Xor:
251	return 3; // Can fold through either operand.
252	case Instruction::Sub: // Can only fold on the amount subtracted.
253	case Instruction::FSub:
254	case Instruction::FDiv: // Can only fold on the divisor amount.
255	case Instruction::Shl: // Can only fold on the shift amount.
256	case Instruction::LShr:
257	case Instruction::AShr:
258	return 1;
259	default:
260	return 0; // Cannot fold
261	}
262	}
263
264	/// We have (select c, TI, FI), and we know that TI and FI have the same opcode.
265	Instruction *InstCombinerImpl::foldSelectOpOp(SelectInst &SI, Instruction *TI,
266	Instruction *FI) {
267	// Don't break up min/max patterns. The hasOneUse checks below prevent that
268	// for most cases, but vector min/max with bitcasts can be transformed. If the
269	// one-use restrictions are eased for other patterns, we still don't want to
270	// obfuscate min/max.
271	if ((match(V: &SI, P: m_SMin(L: m_Value(), R: m_Value())) ||
272	match(V: &SI, P: m_SMax(L: m_Value(), R: m_Value())) ||
273	match(V: &SI, P: m_UMin(L: m_Value(), R: m_Value())) ||
274	match(V: &SI, P: m_UMax(L: m_Value(), R: m_Value()))))
275	return nullptr;
276
277	// If this is a cast from the same type, merge.
278	Value *Cond = SI.getCondition();
279	Type *CondTy = Cond->getType();
280	if (TI->getNumOperands() == 1 && TI->isCast()) {
281	Type *FIOpndTy = FI->getOperand(i: 0)->getType();
282	if (TI->getOperand(i: 0)->getType() != FIOpndTy)
283	return nullptr;
284
285	// The select condition may be a vector. We may only change the operand
286	// type if the vector width remains the same (and matches the condition).
287	if (auto *CondVTy = dyn_cast<VectorType>(Val: CondTy)) {
288	if (!FIOpndTy->isVectorTy() ||
289	CondVTy->getElementCount() !=
290	cast<VectorType>(Val: FIOpndTy)->getElementCount())
291	return nullptr;
292
293	// TODO: If the backend knew how to deal with casts better, we could
294	// remove this limitation. For now, there's too much potential to create
295	// worse codegen by promoting the select ahead of size-altering casts
296	// (PR28160).
297	//
298	// Note that ValueTracking's matchSelectPattern() looks through casts
299	// without checking 'hasOneUse' when it matches min/max patterns, so this
300	// transform may end up happening anyway.
301	if (TI->getOpcode() != Instruction::BitCast &&
302	(!TI->hasOneUse() || !FI->hasOneUse()))
303	return nullptr;
304	} else if (!TI->hasOneUse() || !FI->hasOneUse()) {
305	// TODO: The one-use restrictions for a scalar select could be eased if
306	// the fold of a select in visitLoadInst() was enhanced to match a pattern
307	// that includes a cast.
308	return nullptr;
309	}
310
311	// Fold this by inserting a select from the input values.
312	Value *NewSI =
313	Builder.CreateSelect(C: Cond, True: TI->getOperand(i: 0), False: FI->getOperand(i: 0),
314	Name: SI.getName() + ".v", MDFrom: &SI);
315	return CastInst::Create(Instruction::CastOps(TI->getOpcode()), S: NewSI,
316	Ty: TI->getType());
317	}
318
319	Value *OtherOpT, *OtherOpF;
320	bool MatchIsOpZero;
321	auto getCommonOp = [&](Instruction *TI, Instruction *FI, bool Commute,
322	bool Swapped = false) -> Value * {
323	assert(!(Commute && Swapped) &&
324	"Commute and Swapped can't set at the same time");
325	if (!Swapped) {
326	if (TI->getOperand(i: 0) == FI->getOperand(i: 0)) {
327	OtherOpT = TI->getOperand(i: 1);
328	OtherOpF = FI->getOperand(i: 1);
329	MatchIsOpZero = true;
330	return TI->getOperand(i: 0);
331	} else if (TI->getOperand(i: 1) == FI->getOperand(i: 1)) {
332	OtherOpT = TI->getOperand(i: 0);
333	OtherOpF = FI->getOperand(i: 0);
334	MatchIsOpZero = false;
335	return TI->getOperand(i: 1);
336	}
337	}
338
339	if (!Commute && !Swapped)
340	return nullptr;
341
342	// If we are allowing commute or swap of operands, then
343	// allow a cross-operand match. In that case, MatchIsOpZero
344	// means that TI's operand 0 (FI's operand 1) is the common op.
345	if (TI->getOperand(i: 0) == FI->getOperand(i: 1)) {
346	OtherOpT = TI->getOperand(i: 1);
347	OtherOpF = FI->getOperand(i: 0);
348	MatchIsOpZero = true;
349	return TI->getOperand(i: 0);
350	} else if (TI->getOperand(i: 1) == FI->getOperand(i: 0)) {
351	OtherOpT = TI->getOperand(i: 0);
352	OtherOpF = FI->getOperand(i: 1);
353	MatchIsOpZero = false;
354	return TI->getOperand(i: 1);
355	}
356	return nullptr;
357	};
358
359	if (TI->hasOneUse() || FI->hasOneUse()) {
360	// Cond ? -X : -Y --> -(Cond ? X : Y)
361	Value *X, *Y;
362	if (match(V: TI, P: m_FNeg(X: m_Value(V&: X))) && match(V: FI, P: m_FNeg(X: m_Value(V&: Y)))) {
363	// Intersect FMF from the fneg instructions and union those with the
364	// select.
365	FastMathFlags FMF = TI->getFastMathFlags();
366	FMF &= FI->getFastMathFlags();
367	FMF |= SI.getFastMathFlags();
368	Value *NewSel =
369	Builder.CreateSelect(C: Cond, True: X, False: Y, Name: SI.getName() + ".v", MDFrom: &SI);
370	if (auto *NewSelI = dyn_cast<Instruction>(Val: NewSel))
371	NewSelI->setFastMathFlags(FMF);
372	Instruction *NewFNeg = UnaryOperator::CreateFNeg(V: NewSel);
373	NewFNeg->setFastMathFlags(FMF);
374	return NewFNeg;
375	}
376
377	// Min/max intrinsic with a common operand can have the common operand
378	// pulled after the select. This is the same transform as below for binops,
379	// but specialized for intrinsic matching and without the restrictive uses
380	// clause.
381	auto *TII = dyn_cast<IntrinsicInst>(Val: TI);
382	auto *FII = dyn_cast<IntrinsicInst>(Val: FI);
383	if (TII && FII && TII->getIntrinsicID() == FII->getIntrinsicID()) {
384	if (match(V: TII, P: m_MaxOrMin(L: m_Value(), R: m_Value()))) {
385	if (Value *MatchOp = getCommonOp(TI, FI, true)) {
386	Value *NewSel =
387	Builder.CreateSelect(C: Cond, True: OtherOpT, False: OtherOpF, Name: "minmaxop", MDFrom: &SI);
388	return CallInst::Create(Func: TII->getCalledFunction(), Args: {NewSel, MatchOp});
389	}
390	}
391
392	// select c, (ldexp v, e0), (ldexp v, e1) -> ldexp v, (select c, e0, e1)
393	// select c, (ldexp v0, e), (ldexp v1, e) -> ldexp (select c, v0, v1), e
394	//
395	// select c, (ldexp v0, e0), (ldexp v1, e1) ->
396	// ldexp (select c, v0, v1), (select c, e0, e1)
397	if (TII->getIntrinsicID() == Intrinsic::ldexp) {
398	Value *LdexpVal0 = TII->getArgOperand(i: 0);
399	Value *LdexpExp0 = TII->getArgOperand(i: 1);
400	Value *LdexpVal1 = FII->getArgOperand(i: 0);
401	Value *LdexpExp1 = FII->getArgOperand(i: 1);
402	if (LdexpExp0->getType() == LdexpExp1->getType()) {
403	FPMathOperator *SelectFPOp = cast<FPMathOperator>(Val: &SI);
404	FastMathFlags FMF = cast<FPMathOperator>(Val: TII)->getFastMathFlags();
405	FMF &= cast<FPMathOperator>(Val: FII)->getFastMathFlags();
406	FMF |= SelectFPOp->getFastMathFlags();
407
408	Value *SelectVal = Builder.CreateSelect(C: Cond, True: LdexpVal0, False: LdexpVal1);
409	Value *SelectExp = Builder.CreateSelect(C: Cond, True: LdexpExp0, False: LdexpExp1);
410
411	CallInst *NewLdexp = Builder.CreateIntrinsic(
412	TII->getType(), Intrinsic::ldexp, {SelectVal, SelectExp});
413	NewLdexp->setFastMathFlags(FMF);
414	return replaceInstUsesWith(I&: SI, V: NewLdexp);
415	}
416	}
417	}
418
419	// icmp with a common operand also can have the common operand
420	// pulled after the select.
421	ICmpInst::Predicate TPred, FPred;
422	if (match(V: TI, P: m_ICmp(Pred&: TPred, L: m_Value(), R: m_Value())) &&
423	match(V: FI, P: m_ICmp(Pred&: FPred, L: m_Value(), R: m_Value()))) {
424	if (TPred == FPred || TPred == CmpInst::getSwappedPredicate(pred: FPred)) {
425	bool Swapped = TPred != FPred;
426	if (Value *MatchOp =
427	getCommonOp(TI, FI, ICmpInst::isEquality(P: TPred), Swapped)) {
428	Value *NewSel = Builder.CreateSelect(C: Cond, True: OtherOpT, False: OtherOpF,
429	Name: SI.getName() + ".v", MDFrom: &SI);
430	return new ICmpInst(
431	MatchIsOpZero ? TPred : CmpInst::getSwappedPredicate(pred: TPred),
432	MatchOp, NewSel);
433	}
434	}
435	}
436	}
437
438	// Only handle binary operators (including two-operand getelementptr) with
439	// one-use here. As with the cast case above, it may be possible to relax the
440	// one-use constraint, but that needs be examined carefully since it may not
441	// reduce the total number of instructions.
442	if (TI->getNumOperands() != 2 || FI->getNumOperands() != 2 ||
443	!TI->isSameOperationAs(I: FI) ||
444	(!isa<BinaryOperator>(Val: TI) && !isa<GetElementPtrInst>(Val: TI)) ||
445	!TI->hasOneUse() || !FI->hasOneUse())
446	return nullptr;
447
448	// Figure out if the operations have any operands in common.
449	Value *MatchOp = getCommonOp(TI, FI, TI->isCommutative());
450	if (!MatchOp)
451	return nullptr;
452
453	// If the select condition is a vector, the operands of the original select's
454	// operands also must be vectors. This may not be the case for getelementptr
455	// for example.
456	if (CondTy->isVectorTy() && (!OtherOpT->getType()->isVectorTy() ||
457	!OtherOpF->getType()->isVectorTy()))
458	return nullptr;
459
460	// If we are sinking div/rem after a select, we may need to freeze the
461	// condition because div/rem may induce immediate UB with a poison operand.
462	// For example, the following transform is not safe if Cond can ever be poison
463	// because we can replace poison with zero and then we have div-by-zero that
464	// didn't exist in the original code:
465	// Cond ? x/y : x/z --> x / (Cond ? y : z)
466	auto *BO = dyn_cast<BinaryOperator>(Val: TI);
467	if (BO && BO->isIntDivRem() && !isGuaranteedNotToBePoison(V: Cond)) {
468	// A udiv/urem with a common divisor is safe because UB can only occur with
469	// div-by-zero, and that would be present in the original code.
470	if (BO->getOpcode() == Instruction::SDiv ||
471	BO->getOpcode() == Instruction::SRem || MatchIsOpZero)
472	Cond = Builder.CreateFreeze(V: Cond);
473	}
474
475	// If we reach here, they do have operations in common.
476	Value *NewSI = Builder.CreateSelect(C: Cond, True: OtherOpT, False: OtherOpF,
477	Name: SI.getName() + ".v", MDFrom: &SI);
478	Value *Op0 = MatchIsOpZero ? MatchOp : NewSI;
479	Value *Op1 = MatchIsOpZero ? NewSI : MatchOp;
480	if (auto *BO = dyn_cast<BinaryOperator>(Val: TI)) {
481	BinaryOperator *NewBO = BinaryOperator::Create(Op: BO->getOpcode(), S1: Op0, S2: Op1);
482	NewBO->copyIRFlags(V: TI);
483	NewBO->andIRFlags(V: FI);
484	return NewBO;
485	}
486	if (auto *TGEP = dyn_cast<GetElementPtrInst>(Val: TI)) {
487	auto *FGEP = cast<GetElementPtrInst>(Val: FI);
488	Type *ElementType = TGEP->getResultElementType();
489	return TGEP->isInBounds() && FGEP->isInBounds()
490	? GetElementPtrInst::CreateInBounds(PointeeType: ElementType, Ptr: Op0, IdxList: {Op1})
491	: GetElementPtrInst::Create(PointeeType: ElementType, Ptr: Op0, IdxList: {Op1});
492	}
493	llvm_unreachable("Expected BinaryOperator or GEP");
494	return nullptr;
495	}
496
497	static bool isSelect01(const APInt &C1I, const APInt &C2I) {
498	if (!C1I.isZero() && !C2I.isZero()) // One side must be zero.
499	return false;
500	return C1I.isOne() || C1I.isAllOnes() || C2I.isOne() || C2I.isAllOnes();
501	}
502
503	/// Try to fold the select into one of the operands to allow further
504	/// optimization.
505	Instruction *InstCombinerImpl::foldSelectIntoOp(SelectInst &SI, Value *TrueVal,
506	Value *FalseVal) {
507	// See the comment above getSelectFoldableOperands for a description of the
508	// transformation we are doing here.
509	auto TryFoldSelectIntoOp = [&](SelectInst &SI, Value *TrueVal,
510	Value *FalseVal,
511	bool Swapped) -> Instruction * {
512	auto *TVI = dyn_cast<BinaryOperator>(Val: TrueVal);
513	if (!TVI || !TVI->hasOneUse() || isa<Constant>(Val: FalseVal))
514	return nullptr;
515
516	unsigned SFO = getSelectFoldableOperands(I: TVI);
517	unsigned OpToFold = 0;
518	if ((SFO & 1) && FalseVal == TVI->getOperand(i_nocapture: 0))
519	OpToFold = 1;
520	else if ((SFO & 2) && FalseVal == TVI->getOperand(i_nocapture: 1))
521	OpToFold = 2;
522
523	if (!OpToFold)
524	return nullptr;
525
526	// TODO: We probably ought to revisit cases where the select and FP
527	// instructions have different flags and add tests to ensure the
528	// behaviour is correct.
529	FastMathFlags FMF;
530	if (isa<FPMathOperator>(Val: &SI))
531	FMF = SI.getFastMathFlags();
532	Constant *C = ConstantExpr::getBinOpIdentity(
533	Opcode: TVI->getOpcode(), Ty: TVI->getType(), AllowRHSConstant: true, NSZ: FMF.noSignedZeros());
534	Value *OOp = TVI->getOperand(i_nocapture: 2 - OpToFold);
535	// Avoid creating select between 2 constants unless it's selecting
536	// between 0, 1 and -1.
537	const APInt *OOpC;
538	bool OOpIsAPInt = match(V: OOp, P: m_APInt(Res&: OOpC));
539	if (isa<Constant>(Val: OOp) &&
540	(!OOpIsAPInt || !isSelect01(C1I: C->getUniqueInteger(), C2I: *OOpC)))
541	return nullptr;
542
543	// If the false value is a NaN then we have that the floating point math
544	// operation in the transformed code may not preserve the exact NaN
545	// bit-pattern -- e.g. `fadd sNaN, 0.0 -> qNaN`.
546	// This makes the transformation incorrect since the original program would
547	// have preserved the exact NaN bit-pattern.
548	// Avoid the folding if the false value might be a NaN.
549	if (isa<FPMathOperator>(Val: &SI) &&
550	!computeKnownFPClass(Val: FalseVal, FMF, Interested: fcNan, CtxI: &SI).isKnownNeverNaN())
551	return nullptr;
552
553	Value *NewSel = Builder.CreateSelect(C: SI.getCondition(), True: Swapped ? C : OOp,
554	False: Swapped ? OOp : C, Name: "", MDFrom: &SI);
555	if (isa<FPMathOperator>(Val: &SI))
556	cast<Instruction>(Val: NewSel)->setFastMathFlags(FMF);
557	NewSel->takeName(V: TVI);
558	BinaryOperator *BO =
559	BinaryOperator::Create(Op: TVI->getOpcode(), S1: FalseVal, S2: NewSel);
560	BO->copyIRFlags(V: TVI);
561	return BO;
562	};
563
564	if (Instruction *R = TryFoldSelectIntoOp(SI, TrueVal, FalseVal, false))
565	return R;
566
567	if (Instruction *R = TryFoldSelectIntoOp(SI, FalseVal, TrueVal, true))
568	return R;
569
570	return nullptr;
571	}
572
573	/// We want to turn:
574	/// (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1)
575	/// into:
576	/// zext (icmp ne i32 (and X, (or Y, (shl 1, Z))), 0)
577	/// Note:
578	/// Z may be 0 if lshr is missing.
579	/// Worst-case scenario is that we will replace 5 instructions with 5 different
580	/// instructions, but we got rid of select.
581	static Instruction *foldSelectICmpAndAnd(Type *SelType, const ICmpInst *Cmp,
582	Value *TVal, Value *FVal,
583	InstCombiner::BuilderTy &Builder) {
584	if (!(Cmp->hasOneUse() && Cmp->getOperand(i_nocapture: 0)->hasOneUse() &&
585	Cmp->getPredicate() == ICmpInst::ICMP_EQ &&
586	match(V: Cmp->getOperand(i_nocapture: 1), P: m_Zero()) && match(V: FVal, P: m_One())))
587	return nullptr;
588
589	// The TrueVal has general form of: and %B, 1
590	Value *B;
591	if (!match(V: TVal, P: m_OneUse(SubPattern: m_And(L: m_Value(V&: B), R: m_One()))))
592	return nullptr;
593
594	// Where %B may be optionally shifted: lshr %X, %Z.
595	Value *X, *Z;
596	const bool HasShift = match(V: B, P: m_OneUse(SubPattern: m_LShr(L: m_Value(V&: X), R: m_Value(V&: Z))));
597
598	// The shift must be valid.
599	// TODO: This restricts the fold to constant shift amounts. Is there a way to
600	// handle variable shifts safely? PR47012
601	if (HasShift &&
602	!match(V: Z, P: m_SpecificInt_ICMP(Predicate: CmpInst::ICMP_ULT,
603	Threshold: APInt(SelType->getScalarSizeInBits(),
604	SelType->getScalarSizeInBits()))))
605	return nullptr;
606
607	if (!HasShift)
608	X = B;
609
610	Value *Y;
611	if (!match(V: Cmp->getOperand(i_nocapture: 0), P: m_c_And(L: m_Specific(V: X), R: m_Value(V&: Y))))
612	return nullptr;
613
614	// ((X & Y) == 0) ? ((X >> Z) & 1) : 1 --> (X & (Y | (1 << Z))) != 0
615	// ((X & Y) == 0) ? (X & 1) : 1 --> (X & (Y | 1)) != 0
616	Constant *One = ConstantInt::get(Ty: SelType, V: 1);
617	Value *MaskB = HasShift ? Builder.CreateShl(LHS: One, RHS: Z) : One;
618	Value *FullMask = Builder.CreateOr(LHS: Y, RHS: MaskB);
619	Value *MaskedX = Builder.CreateAnd(LHS: X, RHS: FullMask);
620	Value *ICmpNeZero = Builder.CreateIsNotNull(Arg: MaskedX);
621	return new ZExtInst(ICmpNeZero, SelType);
622	}
623
624	/// We want to turn:
625	/// (select (icmp eq (and X, C1), 0), 0, (shl [nsw/nuw] X, C2));
626	/// iff C1 is a mask and the number of its leading zeros is equal to C2
627	/// into:
628	/// shl X, C2
629	static Value *foldSelectICmpAndZeroShl(const ICmpInst *Cmp, Value *TVal,
630	Value *FVal,
631	InstCombiner::BuilderTy &Builder) {
632	ICmpInst::Predicate Pred;
633	Value *AndVal;
634	if (!match(V: Cmp, P: m_ICmp(Pred, L: m_Value(V&: AndVal), R: m_Zero())))
635	return nullptr;
636
637	if (Pred == ICmpInst::ICMP_NE) {
638	Pred = ICmpInst::ICMP_EQ;
639	std::swap(a&: TVal, b&: FVal);
640	}
641
642	Value *X;
643	const APInt *C2, *C1;
644	if (Pred != ICmpInst::ICMP_EQ ||
645	!match(V: AndVal, P: m_And(L: m_Value(V&: X), R: m_APInt(Res&: C1))) ||
646	!match(V: TVal, P: m_Zero()) || !match(V: FVal, P: m_Shl(L: m_Specific(V: X), R: m_APInt(Res&: C2))))
647	return nullptr;
648
649	if (!C1->isMask() ||
650	C1->countLeadingZeros() != static_cast<unsigned>(C2->getZExtValue()))
651	return nullptr;
652
653	auto *FI = dyn_cast<Instruction>(Val: FVal);
654	if (!FI)
655	return nullptr;
656
657	FI->setHasNoSignedWrap(false);
658	FI->setHasNoUnsignedWrap(false);
659	return FVal;
660	}
661
662	/// We want to turn:
663	/// (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1
664	/// (select (icmp slt x, C), ashr (X, Y), lshr (X, Y)); iff C s>= 0
665	/// into:
666	/// ashr (X, Y)
667	static Value *foldSelectICmpLshrAshr(const ICmpInst *IC, Value *TrueVal,
668	Value *FalseVal,
669	InstCombiner::BuilderTy &Builder) {
670	ICmpInst::Predicate Pred = IC->getPredicate();
671	Value *CmpLHS = IC->getOperand(i_nocapture: 0);
672	Value *CmpRHS = IC->getOperand(i_nocapture: 1);
673	if (!CmpRHS->getType()->isIntOrIntVectorTy())
674	return nullptr;
675
676	Value *X, *Y;
677	unsigned Bitwidth = CmpRHS->getType()->getScalarSizeInBits();
678	if ((Pred != ICmpInst::ICMP_SGT ||
679	!match(V: CmpRHS,
680	P: m_SpecificInt_ICMP(Predicate: ICmpInst::ICMP_SGE, Threshold: APInt(Bitwidth, -1)))) &&
681	(Pred != ICmpInst::ICMP_SLT ||
682	!match(V: CmpRHS,
683	P: m_SpecificInt_ICMP(Predicate: ICmpInst::ICMP_SGE, Threshold: APInt(Bitwidth, 0)))))
684	return nullptr;
685
686	// Canonicalize so that ashr is in FalseVal.
687	if (Pred == ICmpInst::ICMP_SLT)
688	std::swap(a&: TrueVal, b&: FalseVal);
689
690	if (match(V: TrueVal, P: m_LShr(L: m_Value(V&: X), R: m_Value(V&: Y))) &&
691	match(V: FalseVal, P: m_AShr(L: m_Specific(V: X), R: m_Specific(V: Y))) &&
692	match(V: CmpLHS, P: m_Specific(V: X))) {
693	const auto *Ashr = cast<Instruction>(Val: FalseVal);
694	// if lshr is not exact and ashr is, this new ashr must not be exact.
695	bool IsExact = Ashr->isExact() && cast<Instruction>(Val: TrueVal)->isExact();
696	return Builder.CreateAShr(LHS: X, RHS: Y, Name: IC->getName(), isExact: IsExact);
697	}
698
699	return nullptr;
700	}
701
702	/// We want to turn:
703	/// (select (icmp eq (and X, C1), 0), Y, (BinOp Y, C2))
704	/// into:
705	/// IF C2 u>= C1
706	/// (BinOp Y, (shl (and X, C1), C3))
707	/// ELSE
708	/// (BinOp Y, (lshr (and X, C1), C3))
709	/// iff:
710	/// 0 on the RHS is the identity value (i.e add, xor, shl, etc...)
711	/// C1 and C2 are both powers of 2
712	/// where:
713	/// IF C2 u>= C1
714	/// C3 = Log(C2) - Log(C1)
715	/// ELSE
716	/// C3 = Log(C1) - Log(C2)
717	///
718	/// This transform handles cases where:
719	/// 1. The icmp predicate is inverted
720	/// 2. The select operands are reversed
721	/// 3. The magnitude of C2 and C1 are flipped
722	static Value *foldSelectICmpAndBinOp(const ICmpInst *IC, Value *TrueVal,
723	Value *FalseVal,
724	InstCombiner::BuilderTy &Builder) {
725	// Only handle integer compares. Also, if this is a vector select, we need a
726	// vector compare.
727	if (!TrueVal->getType()->isIntOrIntVectorTy() ||
728	TrueVal->getType()->isVectorTy() != IC->getType()->isVectorTy())
729	return nullptr;
730
731	Value *CmpLHS = IC->getOperand(i_nocapture: 0);
732	Value *CmpRHS = IC->getOperand(i_nocapture: 1);
733
734	unsigned C1Log;
735	bool NeedAnd = false;
736	CmpInst::Predicate Pred = IC->getPredicate();
737	if (IC->isEquality()) {
738	if (!match(V: CmpRHS, P: m_Zero()))
739	return nullptr;
740
741	const APInt *C1;
742	if (!match(V: CmpLHS, P: m_And(L: m_Value(), R: m_Power2(V&: C1))))
743	return nullptr;
744
745	C1Log = C1->logBase2();
746	} else {
747	APInt C1;
748	if (!decomposeBitTestICmp(LHS: CmpLHS, RHS: CmpRHS, Pred, X&: CmpLHS, Mask&: C1) ||
749	!C1.isPowerOf2())
750	return nullptr;
751
752	C1Log = C1.logBase2();
753	NeedAnd = true;
754	}
755
756	Value *Y, *V = CmpLHS;
757	BinaryOperator *BinOp;
758	const APInt *C2;
759	bool NeedXor;
760	if (match(V: FalseVal, P: m_BinOp(L: m_Specific(V: TrueVal), R: m_Power2(V&: C2)))) {
761	Y = TrueVal;
762	BinOp = cast<BinaryOperator>(Val: FalseVal);
763	NeedXor = Pred == ICmpInst::ICMP_NE;
764	} else if (match(V: TrueVal, P: m_BinOp(L: m_Specific(V: FalseVal), R: m_Power2(V&: C2)))) {
765	Y = FalseVal;
766	BinOp = cast<BinaryOperator>(Val: TrueVal);
767	NeedXor = Pred == ICmpInst::ICMP_EQ;
768	} else {
769	return nullptr;
770	}
771
772	// Check that 0 on RHS is identity value for this binop.
773	auto *IdentityC =
774	ConstantExpr::getBinOpIdentity(Opcode: BinOp->getOpcode(), Ty: BinOp->getType(),
775	/*AllowRHSConstant*/ true);
776	if (IdentityC == nullptr || !IdentityC->isNullValue())
777	return nullptr;
778
779	unsigned C2Log = C2->logBase2();
780
781	bool NeedShift = C1Log != C2Log;
782	bool NeedZExtTrunc = Y->getType()->getScalarSizeInBits() !=
783	V->getType()->getScalarSizeInBits();
784
785	// Make sure we don't create more instructions than we save.
786	if ((NeedShift + NeedXor + NeedZExtTrunc + NeedAnd) >
787	(IC->hasOneUse() + BinOp->hasOneUse()))
788	return nullptr;
789
790	if (NeedAnd) {
791	// Insert the AND instruction on the input to the truncate.
792	APInt C1 = APInt::getOneBitSet(numBits: V->getType()->getScalarSizeInBits(), BitNo: C1Log);
793	V = Builder.CreateAnd(LHS: V, RHS: ConstantInt::get(Ty: V->getType(), V: C1));
794	}
795
796	if (C2Log > C1Log) {
797	V = Builder.CreateZExtOrTrunc(V, DestTy: Y->getType());
798	V = Builder.CreateShl(LHS: V, RHS: C2Log - C1Log);
799	} else if (C1Log > C2Log) {
800	V = Builder.CreateLShr(LHS: V, RHS: C1Log - C2Log);
801	V = Builder.CreateZExtOrTrunc(V, DestTy: Y->getType());
802	} else
803	V = Builder.CreateZExtOrTrunc(V, DestTy: Y->getType());
804
805	if (NeedXor)
806	V = Builder.CreateXor(LHS: V, RHS: *C2);
807
808	return Builder.CreateBinOp(Opc: BinOp->getOpcode(), LHS: Y, RHS: V);
809	}
810
811	/// Canonicalize a set or clear of a masked set of constant bits to
812	/// select-of-constants form.
813	static Instruction *foldSetClearBits(SelectInst &Sel,
814	InstCombiner::BuilderTy &Builder) {
815	Value *Cond = Sel.getCondition();
816	Value *T = Sel.getTrueValue();
817	Value *F = Sel.getFalseValue();
818	Type *Ty = Sel.getType();
819	Value *X;
820	const APInt *NotC, *C;
821
822	// Cond ? (X & ~C) : (X | C) --> (X & ~C) | (Cond ? 0 : C)
823	if (match(V: T, P: m_And(L: m_Value(V&: X), R: m_APInt(Res&: NotC))) &&
824	match(V: F, P: m_OneUse(SubPattern: m_Or(L: m_Specific(V: X), R: m_APInt(Res&: C)))) && *NotC == ~(*C)) {
825	Constant *Zero = ConstantInt::getNullValue(Ty);
826	Constant *OrC = ConstantInt::get(Ty, V: *C);
827	Value *NewSel = Builder.CreateSelect(C: Cond, True: Zero, False: OrC, Name: "masksel", MDFrom: &Sel);
828	return BinaryOperator::CreateOr(V1: T, V2: NewSel);
829	}
830
831	// Cond ? (X | C) : (X & ~C) --> (X & ~C) | (Cond ? C : 0)
832	if (match(V: F, P: m_And(L: m_Value(V&: X), R: m_APInt(Res&: NotC))) &&
833	match(V: T, P: m_OneUse(SubPattern: m_Or(L: m_Specific(V: X), R: m_APInt(Res&: C)))) && *NotC == ~(*C)) {
834	Constant *Zero = ConstantInt::getNullValue(Ty);
835	Constant *OrC = ConstantInt::get(Ty, V: *C);
836	Value *NewSel = Builder.CreateSelect(C: Cond, True: OrC, False: Zero, Name: "masksel", MDFrom: &Sel);
837	return BinaryOperator::CreateOr(V1: F, V2: NewSel);
838	}
839
840	return nullptr;
841	}
842
843	// select (x == 0), 0, x * y --> freeze(y) * x
844	// select (y == 0), 0, x * y --> freeze(x) * y
845	// select (x == 0), undef, x * y --> freeze(y) * x
846	// select (x == undef), 0, x * y --> freeze(y) * x
847	// Usage of mul instead of 0 will make the result more poisonous,
848	// so the operand that was not checked in the condition should be frozen.
849	// The latter folding is applied only when a constant compared with x is
850	// is a vector consisting of 0 and undefs. If a constant compared with x
851	// is a scalar undefined value or undefined vector then an expression
852	// should be already folded into a constant.
853	static Instruction *foldSelectZeroOrMul(SelectInst &SI, InstCombinerImpl &IC) {
854	auto *CondVal = SI.getCondition();
855	auto *TrueVal = SI.getTrueValue();
856	auto *FalseVal = SI.getFalseValue();
857	Value *X, *Y;
858	ICmpInst::Predicate Predicate;
859
860	// Assuming that constant compared with zero is not undef (but it may be
861	// a vector with some undef elements). Otherwise (when a constant is undef)
862	// the select expression should be already simplified.
863	if (!match(V: CondVal, P: m_ICmp(Pred&: Predicate, L: m_Value(V&: X), R: m_Zero())) ||
864	!ICmpInst::isEquality(P: Predicate))
865	return nullptr;
866
867	if (Predicate == ICmpInst::ICMP_NE)
868	std::swap(a&: TrueVal, b&: FalseVal);
869
870	// Check that TrueVal is a constant instead of matching it with m_Zero()
871	// to handle the case when it is a scalar undef value or a vector containing
872	// non-zero elements that are masked by undef elements in the compare
873	// constant.
874	auto *TrueValC = dyn_cast<Constant>(Val: TrueVal);
875	if (TrueValC == nullptr ||
876	!match(V: FalseVal, P: m_c_Mul(L: m_Specific(V: X), R: m_Value(V&: Y))) ||
877	!isa<Instruction>(Val: FalseVal))
878	return nullptr;
879
880	auto *ZeroC = cast<Constant>(Val: cast<Instruction>(Val: CondVal)->getOperand(i: 1));
881	auto *MergedC = Constant::mergeUndefsWith(C: TrueValC, Other: ZeroC);
882	// If X is compared with 0 then TrueVal could be either zero or undef.
883	// m_Zero match vectors containing some undef elements, but for scalars
884	// m_Undef should be used explicitly.
885	if (!match(V: MergedC, P: m_Zero()) && !match(V: MergedC, P: m_Undef()))
886	return nullptr;
887
888	auto *FalseValI = cast<Instruction>(Val: FalseVal);
889	auto *FrY = IC.InsertNewInstBefore(New: new FreezeInst(Y, Y->getName() + ".fr"),
890	Old: FalseValI->getIterator());
891	IC.replaceOperand(I&: *FalseValI, OpNum: FalseValI->getOperand(i: 0) == Y ? 0 : 1, V: FrY);
892	return IC.replaceInstUsesWith(I&: SI, V: FalseValI);
893	}
894
895	/// Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b).
896	/// There are 8 commuted/swapped variants of this pattern.
897	/// TODO: Also support a - UMIN(a,b) patterns.
898	static Value *canonicalizeSaturatedSubtract(const ICmpInst *ICI,
899	const Value *TrueVal,
900	const Value *FalseVal,
901	InstCombiner::BuilderTy &Builder) {
902	ICmpInst::Predicate Pred = ICI->getPredicate();
903	Value *A = ICI->getOperand(i_nocapture: 0);
904	Value *B = ICI->getOperand(i_nocapture: 1);
905
906	// (b > a) ? 0 : a - b -> (b <= a) ? a - b : 0
907	// (a == 0) ? 0 : a - 1 -> (a != 0) ? a - 1 : 0
908	if (match(V: TrueVal, P: m_Zero())) {
909	Pred = ICmpInst::getInversePredicate(pred: Pred);
910	std::swap(a&: TrueVal, b&: FalseVal);
911	}
912
913	if (!match(V: FalseVal, P: m_Zero()))
914	return nullptr;
915
916	// ugt 0 is canonicalized to ne 0 and requires special handling
917	// (a != 0) ? a + -1 : 0 -> usub.sat(a, 1)
918	if (Pred == ICmpInst::ICMP_NE) {
919	if (match(V: B, P: m_Zero()) && match(V: TrueVal, P: m_Add(L: m_Specific(V: A), R: m_AllOnes())))
920	return Builder.CreateBinaryIntrinsic(Intrinsic::ID: usub_sat, LHS: A,
921	RHS: ConstantInt::get(Ty: A->getType(), V: 1));
922	return nullptr;
923	}
924
925	if (!ICmpInst::isUnsigned(predicate: Pred))
926	return nullptr;
927
928	if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_ULT) {
929	// (b < a) ? a - b : 0 -> (a > b) ? a - b : 0
930	std::swap(a&: A, b&: B);
931	Pred = ICmpInst::getSwappedPredicate(pred: Pred);
932	}
933
934	assert((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_UGT) &&
935	"Unexpected isUnsigned predicate!");
936
937	// Ensure the sub is of the form:
938	// (a > b) ? a - b : 0 -> usub.sat(a, b)
939	// (a > b) ? b - a : 0 -> -usub.sat(a, b)
940	// Checking for both a-b and a+(-b) as a constant.
941	bool IsNegative = false;
942	const APInt *C;
943	if (match(V: TrueVal, P: m_Sub(L: m_Specific(V: B), R: m_Specific(V: A))) ||
944	(match(V: A, P: m_APInt(Res&: C)) &&
945	match(V: TrueVal, P: m_Add(L: m_Specific(V: B), R: m_SpecificInt(V: -*C)))))
946	IsNegative = true;
947	else if (!match(V: TrueVal, P: m_Sub(L: m_Specific(V: A), R: m_Specific(V: B))) &&
948	!(match(V: B, P: m_APInt(Res&: C)) &&
949	match(V: TrueVal, P: m_Add(L: m_Specific(V: A), R: m_SpecificInt(V: -*C)))))
950	return nullptr;
951
952	// If we are adding a negate and the sub and icmp are used anywhere else, we
953	// would end up with more instructions.
954	if (IsNegative && !TrueVal->hasOneUse() && !ICI->hasOneUse())
955	return nullptr;
956
957	// (a > b) ? a - b : 0 -> usub.sat(a, b)
958	// (a > b) ? b - a : 0 -> -usub.sat(a, b)
959	Value *Result = Builder.CreateBinaryIntrinsic(Intrinsic::ID: usub_sat, LHS: A, RHS: B);
960	if (IsNegative)
961	Result = Builder.CreateNeg(V: Result);
962	return Result;
963	}
964
965	static Value *canonicalizeSaturatedAdd(ICmpInst *Cmp, Value *TVal, Value *FVal,
966	InstCombiner::BuilderTy &Builder) {
967	if (!Cmp->hasOneUse())
968	return nullptr;
969
970	// Match unsigned saturated add with constant.
971	Value *Cmp0 = Cmp->getOperand(i_nocapture: 0);
972	Value *Cmp1 = Cmp->getOperand(i_nocapture: 1);
973	ICmpInst::Predicate Pred = Cmp->getPredicate();
974	Value *X;
975	const APInt *C, *CmpC;
976	if (Pred == ICmpInst::ICMP_ULT &&
977	match(V: TVal, P: m_Add(L: m_Value(V&: X), R: m_APInt(Res&: C))) && X == Cmp0 &&
978	match(V: FVal, P: m_AllOnes()) && match(V: Cmp1, P: m_APInt(Res&: CmpC)) && *CmpC == ~*C) {
979	// (X u< ~C) ? (X + C) : -1 --> uadd.sat(X, C)
980	return Builder.CreateBinaryIntrinsic(
981	Intrinsic::ID: uadd_sat, LHS: X, RHS: ConstantInt::get(Ty: X->getType(), V: *C));
982	}
983
984	// Match unsigned saturated add of 2 variables with an unnecessary 'not'.
985	// There are 8 commuted variants.
986	// Canonicalize -1 (saturated result) to true value of the select.
987	if (match(V: FVal, P: m_AllOnes())) {
988	std::swap(a&: TVal, b&: FVal);
989	Pred = CmpInst::getInversePredicate(pred: Pred);
990	}
991	if (!match(V: TVal, P: m_AllOnes()))
992	return nullptr;
993
994	// Canonicalize predicate to less-than or less-or-equal-than.
995	if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) {
996	std::swap(a&: Cmp0, b&: Cmp1);
997	Pred = CmpInst::getSwappedPredicate(pred: Pred);
998	}
999	if (Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_ULE)
1000	return nullptr;
1001
1002	// Match unsigned saturated add of 2 variables with an unnecessary 'not'.
1003	// Strictness of the comparison is irrelevant.
1004	Value *Y;
1005	if (match(V: Cmp0, P: m_Not(V: m_Value(V&: X))) &&
1006	match(V: FVal, P: m_c_Add(L: m_Specific(V: X), R: m_Value(V&: Y))) && Y == Cmp1) {
1007	// (~X u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
1008	// (~X u< Y) ? -1 : (Y + X) --> uadd.sat(X, Y)
1009	return Builder.CreateBinaryIntrinsic(Intrinsic::ID: uadd_sat, LHS: X, RHS: Y);
1010	}
1011	// The 'not' op may be included in the sum but not the compare.
1012	// Strictness of the comparison is irrelevant.
1013	X = Cmp0;
1014	Y = Cmp1;
1015	if (match(V: FVal, P: m_c_Add(L: m_Not(V: m_Specific(V: X)), R: m_Specific(V: Y)))) {
1016	// (X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y)
1017	// (X u< Y) ? -1 : (Y + ~X) --> uadd.sat(Y, ~X)
1018	BinaryOperator *BO = cast<BinaryOperator>(Val: FVal);
1019	return Builder.CreateBinaryIntrinsic(
1020	Intrinsic::ID: uadd_sat, LHS: BO->getOperand(i_nocapture: 0), RHS: BO->getOperand(i_nocapture: 1));
1021	}
1022	// The overflow may be detected via the add wrapping round.
1023	// This is only valid for strict comparison!
1024	if (Pred == ICmpInst::ICMP_ULT &&
1025	match(V: Cmp0, P: m_c_Add(L: m_Specific(V: Cmp1), R: m_Value(V&: Y))) &&
1026	match(V: FVal, P: m_c_Add(L: m_Specific(V: Cmp1), R: m_Specific(V: Y)))) {
1027	// ((X + Y) u< X) ? -1 : (X + Y) --> uadd.sat(X, Y)
1028	// ((X + Y) u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
1029	return Builder.CreateBinaryIntrinsic(Intrinsic::ID: uadd_sat, LHS: Cmp1, RHS: Y);
1030	}
1031
1032	return nullptr;
1033	}
1034
1035	/// Try to match patterns with select and subtract as absolute difference.
1036	static Value *foldAbsDiff(ICmpInst *Cmp, Value *TVal, Value *FVal,
1037	InstCombiner::BuilderTy &Builder) {
1038	auto *TI = dyn_cast<Instruction>(Val: TVal);
1039	auto *FI = dyn_cast<Instruction>(Val: FVal);
1040	if (!TI || !FI)
1041	return nullptr;
1042
1043	// Normalize predicate to gt/lt rather than ge/le.
1044	ICmpInst::Predicate Pred = Cmp->getStrictPredicate();
1045	Value *A = Cmp->getOperand(i_nocapture: 0);
1046	Value *B = Cmp->getOperand(i_nocapture: 1);
1047
1048	// Normalize "A - B" as the true value of the select.
1049	if (match(V: FI, P: m_Sub(L: m_Specific(V: A), R: m_Specific(V: B)))) {
1050	std::swap(a&: FI, b&: TI);
1051	Pred = ICmpInst::getSwappedPredicate(pred: Pred);
1052	}
1053
1054	// With any pair of no-wrap subtracts:
1055	// (A > B) ? (A - B) : (B - A) --> abs(A - B)
1056	if (Pred == CmpInst::ICMP_SGT &&
1057	match(V: TI, P: m_Sub(L: m_Specific(V: A), R: m_Specific(V: B))) &&
1058	match(V: FI, P: m_Sub(L: m_Specific(V: B), R: m_Specific(V: A))) &&
1059	(TI->hasNoSignedWrap() || TI->hasNoUnsignedWrap()) &&
1060	(FI->hasNoSignedWrap() || FI->hasNoUnsignedWrap())) {
1061	// The remaining subtract is not "nuw" any more.
1062	// If there's one use of the subtract (no other use than the use we are
1063	// about to replace), then we know that the sub is "nsw" in this context
1064	// even if it was only "nuw" before. If there's another use, then we can't
1065	// add "nsw" to the existing instruction because it may not be safe in the
1066	// other user's context.
1067	TI->setHasNoUnsignedWrap(false);
1068	if (!TI->hasNoSignedWrap())
1069	TI->setHasNoSignedWrap(TI->hasOneUse());
1070	return Builder.CreateBinaryIntrinsic(Intrinsic::ID: abs, LHS: TI, RHS: Builder.getTrue());
1071	}
1072
1073	return nullptr;
1074	}
1075
1076	/// Fold the following code sequence:
1077	/// \code
1078	/// int a = ctlz(x & -x);
1079	// x ? 31 - a : a;
1080	// // or
1081	// x ? 31 - a : 32;
1082	/// \code
1083	///
1084	/// into:
1085	/// cttz(x)
1086	static Instruction *foldSelectCtlzToCttz(ICmpInst *ICI, Value *TrueVal,
1087	Value *FalseVal,
1088	InstCombiner::BuilderTy &Builder) {
1089	unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits();
1090	if (!ICI->isEquality() || !match(V: ICI->getOperand(i_nocapture: 1), P: m_Zero()))
1091	return nullptr;
1092
1093	if (ICI->getPredicate() == ICmpInst::ICMP_NE)
1094	std::swap(a&: TrueVal, b&: FalseVal);
1095
1096	Value *Ctlz;
1097	if (!match(V: FalseVal,
1098	P: m_Xor(L: m_Value(V&: Ctlz), R: m_SpecificInt(V: BitWidth - 1))))
1099	return nullptr;
1100
1101	if (!match(Ctlz, m_Intrinsic<Intrinsic::ctlz>()))
1102	return nullptr;
1103
1104	if (TrueVal != Ctlz && !match(V: TrueVal, P: m_SpecificInt(V: BitWidth)))
1105	return nullptr;
1106
1107	Value *X = ICI->getOperand(i_nocapture: 0);
1108	auto *II = cast<IntrinsicInst>(Val: Ctlz);
1109	if (!match(V: II->getOperand(i_nocapture: 0), P: m_c_And(L: m_Specific(V: X), R: m_Neg(V: m_Specific(V: X)))))
1110	return nullptr;
1111
1112	Function *F = Intrinsic::getDeclaration(M: II->getModule(), Intrinsic::id: cttz,
1113	Tys: II->getType());
1114	return CallInst::Create(Func: F, Args: {X, II->getArgOperand(i: 1)});
1115	}
1116
1117	/// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single
1118	/// call to cttz/ctlz with flag 'is_zero_poison' cleared.
1119	///
1120	/// For example, we can fold the following code sequence:
1121	/// \code
1122	/// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
1123	/// %1 = icmp ne i32 %x, 0
1124	/// %2 = select i1 %1, i32 %0, i32 32
1125	/// \code
1126	///
1127	/// into:
1128	/// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
1129	static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal,
1130	InstCombiner::BuilderTy &Builder) {
1131	ICmpInst::Predicate Pred = ICI->getPredicate();
1132	Value *CmpLHS = ICI->getOperand(i_nocapture: 0);
1133	Value *CmpRHS = ICI->getOperand(i_nocapture: 1);
1134
1135	// Check if the select condition compares a value for equality.
1136	if (!ICI->isEquality())
1137	return nullptr;
1138
1139	Value *SelectArg = FalseVal;
1140	Value *ValueOnZero = TrueVal;
1141	if (Pred == ICmpInst::ICMP_NE)
1142	std::swap(a&: SelectArg, b&: ValueOnZero);
1143
1144	// Skip zero extend/truncate.
1145	Value *Count = nullptr;
1146	if (!match(V: SelectArg, P: m_ZExt(Op: m_Value(V&: Count))) &&
1147	!match(V: SelectArg, P: m_Trunc(Op: m_Value(V&: Count))))
1148	Count = SelectArg;
1149
1150	// Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the
1151	// input to the cttz/ctlz is used as LHS for the compare instruction.
1152	Value *X;
1153	if (!match(Count, m_Intrinsic<Intrinsic::cttz>(m_Value(X))) &&
1154	!match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Value(X))))
1155	return nullptr;
1156
1157	// (X == 0) ? BitWidth : ctz(X)
1158	// (X == -1) ? BitWidth : ctz(~X)
1159	if ((X != CmpLHS || !match(V: CmpRHS, P: m_Zero())) &&
1160	(!match(V: X, P: m_Not(V: m_Specific(V: CmpLHS))) || !match(V: CmpRHS, P: m_AllOnes())))
1161	return nullptr;
1162
1163	IntrinsicInst *II = cast<IntrinsicInst>(Val: Count);
1164
1165	// Check if the value propagated on zero is a constant number equal to the
1166	// sizeof in bits of 'Count'.
1167	unsigned SizeOfInBits = Count->getType()->getScalarSizeInBits();
1168	if (match(V: ValueOnZero, P: m_SpecificInt(V: SizeOfInBits))) {
1169	// Explicitly clear the 'is_zero_poison' flag. It's always valid to go from
1170	// true to false on this flag, so we can replace it for all users.
1171	II->setArgOperand(i: 1, v: ConstantInt::getFalse(Context&: II->getContext()));
1172	return SelectArg;
1173	}
1174
1175	// The ValueOnZero is not the bitwidth. But if the cttz/ctlz (and optional
1176	// zext/trunc) have one use (ending at the select), the cttz/ctlz result will
1177	// not be used if the input is zero. Relax to 'zero is poison' for that case.
1178	if (II->hasOneUse() && SelectArg->hasOneUse() &&
1179	!match(V: II->getArgOperand(i: 1), P: m_One()))
1180	II->setArgOperand(i: 1, v: ConstantInt::getTrue(Context&: II->getContext()));
1181
1182	return nullptr;
1183	}
1184
1185	static Value *canonicalizeSPF(ICmpInst &Cmp, Value *TrueVal, Value *FalseVal,
1186	InstCombinerImpl &IC) {
1187	Value *LHS, *RHS;
1188	// TODO: What to do with pointer min/max patterns?
1189	if (!TrueVal->getType()->isIntOrIntVectorTy())
1190	return nullptr;
1191
1192	SelectPatternFlavor SPF =
1193	matchDecomposedSelectPattern(CmpI: &Cmp, TrueVal, FalseVal, LHS, RHS).Flavor;
1194	if (SPF == SelectPatternFlavor::SPF_ABS ||
1195	SPF == SelectPatternFlavor::SPF_NABS) {
1196	if (!Cmp.hasOneUse() && !RHS->hasOneUse())
1197	return nullptr; // TODO: Relax this restriction.
1198
1199	// Note that NSW flag can only be propagated for normal, non-negated abs!
1200	bool IntMinIsPoison = SPF == SelectPatternFlavor::SPF_ABS &&
1201	match(V: RHS, P: m_NSWNeg(V: m_Specific(V: LHS)));
1202	Constant *IntMinIsPoisonC =
1203	ConstantInt::get(Ty: Type::getInt1Ty(C&: Cmp.getContext()), V: IntMinIsPoison);
1204	Value *Abs =
1205	IC.Builder.CreateBinaryIntrinsic(Intrinsic::ID: abs, LHS, RHS: IntMinIsPoisonC);
1206
1207	if (SPF == SelectPatternFlavor::SPF_NABS)
1208	return IC.Builder.CreateNeg(V: Abs); // Always without NSW flag!
1209	return Abs;
1210	}
1211
1212	if (SelectPatternResult::isMinOrMax(SPF)) {
1213	Intrinsic::ID IntrinsicID;
1214	switch (SPF) {
1215	case SelectPatternFlavor::SPF_UMIN:
1216	IntrinsicID = Intrinsic::umin;
1217	break;
1218	case SelectPatternFlavor::SPF_UMAX:
1219	IntrinsicID = Intrinsic::umax;
1220	break;
1221	case SelectPatternFlavor::SPF_SMIN:
1222	IntrinsicID = Intrinsic::smin;
1223	break;
1224	case SelectPatternFlavor::SPF_SMAX:
1225	IntrinsicID = Intrinsic::smax;
1226	break;
1227	default:
1228	llvm_unreachable("Unexpected SPF");
1229	}
1230	return IC.Builder.CreateBinaryIntrinsic(ID: IntrinsicID, LHS, RHS);
1231	}
1232
1233	return nullptr;
1234	}
1235
1236	bool InstCombinerImpl::replaceInInstruction(Value *V, Value *Old, Value *New,
1237	unsigned Depth) {
1238	// Conservatively limit replacement to two instructions upwards.
1239	if (Depth == 2)
1240	return false;
1241
1242	auto *I = dyn_cast<Instruction>(Val: V);
1243	if (!I || !I->hasOneUse() || !isSafeToSpeculativelyExecute(I))
1244	return false;
1245
1246	bool Changed = false;
1247	for (Use &U : I->operands()) {
1248	if (U == Old) {
1249	replaceUse(U, NewValue: New);
1250	Worklist.add(I);
1251	Changed = true;
1252	} else {
1253	Changed |= replaceInInstruction(V: U, Old, New, Depth: Depth + 1);
1254	}
1255	}
1256	return Changed;
1257	}
1258
1259	/// If we have a select with an equality comparison, then we know the value in
1260	/// one of the arms of the select. See if substituting this value into an arm
1261	/// and simplifying the result yields the same value as the other arm.
1262	///
1263	/// To make this transform safe, we must drop poison-generating flags
1264	/// (nsw, etc) if we simplified to a binop because the select may be guarding
1265	/// that poison from propagating. If the existing binop already had no
1266	/// poison-generating flags, then this transform can be done by instsimplify.
1267	///
1268	/// Consider:
1269	/// %cmp = icmp eq i32 %x, 2147483647
1270	/// %add = add nsw i32 %x, 1
1271	/// %sel = select i1 %cmp, i32 -2147483648, i32 %add
1272	///
1273	/// We can't replace %sel with %add unless we strip away the flags.
1274	/// TODO: Wrapping flags could be preserved in some cases with better analysis.
1275	Instruction *InstCombinerImpl::foldSelectValueEquivalence(SelectInst &Sel,
1276	ICmpInst &Cmp) {
1277	if (!Cmp.isEquality())
1278	return nullptr;
1279
1280	// Canonicalize the pattern to ICMP_EQ by swapping the select operands.
1281	Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
1282	bool Swapped = false;
1283	if (Cmp.getPredicate() == ICmpInst::ICMP_NE) {
1284	std::swap(a&: TrueVal, b&: FalseVal);
1285	Swapped = true;
1286	}
1287
1288	// In X == Y ? f(X) : Z, try to evaluate f(Y) and replace the operand.
1289	// Make sure Y cannot be undef though, as we might pick different values for
1290	// undef in the icmp and in f(Y). Additionally, take care to avoid replacing
1291	// X == Y ? X : Z with X == Y ? Y : Z, as that would lead to an infinite
1292	// replacement cycle.
1293	Value *CmpLHS = Cmp.getOperand(i_nocapture: 0), *CmpRHS = Cmp.getOperand(i_nocapture: 1);
1294	if (TrueVal != CmpLHS &&
1295	isGuaranteedNotToBeUndefOrPoison(V: CmpRHS, AC: SQ.AC, CtxI: &Sel, DT: &DT)) {
1296	if (Value *V = simplifyWithOpReplaced(V: TrueVal, Op: CmpLHS, RepOp: CmpRHS, Q: SQ,
1297	/* AllowRefinement */ true))
1298	// Require either the replacement or the simplification result to be a
1299	// constant to avoid infinite loops.
1300	// FIXME: Make this check more precise.
1301	if (isa<Constant>(Val: CmpRHS) || isa<Constant>(Val: V))
1302	return replaceOperand(I&: Sel, OpNum: Swapped ? 2 : 1, V);
1303
1304	// Even if TrueVal does not simplify, we can directly replace a use of
1305	// CmpLHS with CmpRHS, as long as the instruction is not used anywhere
1306	// else and is safe to speculatively execute (we may end up executing it
1307	// with different operands, which should not cause side-effects or trigger
1308	// undefined behavior). Only do this if CmpRHS is a constant, as
1309	// profitability is not clear for other cases.
1310	// FIXME: Support vectors.
1311	if (match(V: CmpRHS, P: m_ImmConstant()) && !match(V: CmpLHS, P: m_ImmConstant()) &&
1312	!Cmp.getType()->isVectorTy())
1313	if (replaceInInstruction(V: TrueVal, Old: CmpLHS, New: CmpRHS))
1314	return &Sel;
1315	}
1316	if (TrueVal != CmpRHS &&
1317	isGuaranteedNotToBeUndefOrPoison(V: CmpLHS, AC: SQ.AC, CtxI: &Sel, DT: &DT))
1318	if (Value *V = simplifyWithOpReplaced(V: TrueVal, Op: CmpRHS, RepOp: CmpLHS, Q: SQ,
1319	/* AllowRefinement */ true))
1320	if (isa<Constant>(Val: CmpLHS) || isa<Constant>(Val: V))
1321	return replaceOperand(I&: Sel, OpNum: Swapped ? 2 : 1, V);
1322
1323	auto *FalseInst = dyn_cast<Instruction>(Val: FalseVal);
1324	if (!FalseInst)
1325	return nullptr;
1326
1327	// InstSimplify already performed this fold if it was possible subject to
1328	// current poison-generating flags. Check whether dropping poison-generating
1329	// flags enables the transform.
1330
1331	// Try each equivalence substitution possibility.
1332	// We have an 'EQ' comparison, so the select's false value will propagate.
1333	// Example:
1334	// (X == 42) ? 43 : (X + 1) --> (X == 42) ? (X + 1) : (X + 1) --> X + 1
1335	SmallVector<Instruction *> DropFlags;
1336	if (simplifyWithOpReplaced(V: FalseVal, Op: CmpLHS, RepOp: CmpRHS, Q: SQ,
1337	/* AllowRefinement */ false,
1338	DropFlags: &DropFlags) == TrueVal ||
1339	simplifyWithOpReplaced(V: FalseVal, Op: CmpRHS, RepOp: CmpLHS, Q: SQ,
1340	/* AllowRefinement */ false,
1341	DropFlags: &DropFlags) == TrueVal) {
1342	for (Instruction *I : DropFlags) {
1343	I->dropPoisonGeneratingAnnotations();
1344	Worklist.add(I);
1345	}
1346
1347	return replaceInstUsesWith(I&: Sel, V: FalseVal);
1348	}
1349
1350	return nullptr;
1351	}
1352
1353	// See if this is a pattern like:
1354	// %old_cmp1 = icmp slt i32 %x, C2
1355	// %old_replacement = select i1 %old_cmp1, i32 %target_low, i32 %target_high
1356	// %old_x_offseted = add i32 %x, C1
1357	// %old_cmp0 = icmp ult i32 %old_x_offseted, C0
1358	// %r = select i1 %old_cmp0, i32 %x, i32 %old_replacement
1359	// This can be rewritten as more canonical pattern:
1360	// %new_cmp1 = icmp slt i32 %x, -C1
1361	// %new_cmp2 = icmp sge i32 %x, C0-C1
1362	// %new_clamped_low = select i1 %new_cmp1, i32 %target_low, i32 %x
1363	// %r = select i1 %new_cmp2, i32 %target_high, i32 %new_clamped_low
1364	// Iff -C1 s<= C2 s<= C0-C1
1365	// Also ULT predicate can also be UGT iff C0 != -1 (+invert result)
1366	// SLT predicate can also be SGT iff C2 != INT_MAX (+invert res.)
1367	static Value *canonicalizeClampLike(SelectInst &Sel0, ICmpInst &Cmp0,
1368	InstCombiner::BuilderTy &Builder) {
1369	Value *X = Sel0.getTrueValue();
1370	Value *Sel1 = Sel0.getFalseValue();
1371
1372	// First match the condition of the outermost select.
1373	// Said condition must be one-use.
1374	if (!Cmp0.hasOneUse())
1375	return nullptr;
1376	ICmpInst::Predicate Pred0 = Cmp0.getPredicate();
1377	Value *Cmp00 = Cmp0.getOperand(i_nocapture: 0);
1378	Constant *C0;
1379	if (!match(V: Cmp0.getOperand(i_nocapture: 1),
1380	P: m_CombineAnd(L: m_AnyIntegralConstant(), R: m_Constant(C&: C0))))
1381	return nullptr;
1382
1383	if (!isa<SelectInst>(Val: Sel1)) {
1384	Pred0 = ICmpInst::getInversePredicate(pred: Pred0);
1385	std::swap(a&: X, b&: Sel1);
1386	}
1387
1388	// Canonicalize Cmp0 into ult or uge.
1389	// FIXME: we shouldn't care about lanes that are 'undef' in the end?
1390	switch (Pred0) {
1391	case ICmpInst::Predicate::ICMP_ULT:
1392	case ICmpInst::Predicate::ICMP_UGE:
1393	// Although icmp ult %x, 0 is an unusual thing to try and should generally
1394	// have been simplified, it does not verify with undef inputs so ensure we
1395	// are not in a strange state.
1396	if (!match(V: C0, P: m_SpecificInt_ICMP(
1397	Predicate: ICmpInst::Predicate::ICMP_NE,
1398	Threshold: APInt::getZero(numBits: C0->getType()->getScalarSizeInBits()))))
1399	return nullptr;
1400	break; // Great!
1401	case ICmpInst::Predicate::ICMP_ULE:
1402	case ICmpInst::Predicate::ICMP_UGT:
1403	// We want to canonicalize it to 'ult' or 'uge', so we'll need to increment
1404	// C0, which again means it must not have any all-ones elements.
1405	if (!match(V: C0,
1406	P: m_SpecificInt_ICMP(
1407	Predicate: ICmpInst::Predicate::ICMP_NE,
1408	Threshold: APInt::getAllOnes(numBits: C0->getType()->getScalarSizeInBits()))))
1409	return nullptr; // Can't do, have all-ones element[s].
1410	Pred0 = ICmpInst::getFlippedStrictnessPredicate(pred: Pred0);
1411	C0 = InstCombiner::AddOne(C: C0);
1412	break;
1413	default:
1414	return nullptr; // Unknown predicate.
1415	}
1416
1417	// Now that we've canonicalized the ICmp, we know the X we expect;
1418	// the select in other hand should be one-use.
1419	if (!Sel1->hasOneUse())
1420	return nullptr;
1421
1422	// If the types do not match, look through any truncs to the underlying
1423	// instruction.
1424	if (Cmp00->getType() != X->getType() && X->hasOneUse())
1425	match(V: X, P: m_TruncOrSelf(Op: m_Value(V&: X)));
1426
1427	// We now can finish matching the condition of the outermost select:
1428	// it should either be the X itself, or an addition of some constant to X.
1429	Constant *C1;
1430	if (Cmp00 == X)
1431	C1 = ConstantInt::getNullValue(Ty: X->getType());
1432	else if (!match(V: Cmp00,
1433	P: m_Add(L: m_Specific(V: X),
1434	R: m_CombineAnd(L: m_AnyIntegralConstant(), R: m_Constant(C&: C1)))))
1435	return nullptr;
1436
1437	Value *Cmp1;
1438	ICmpInst::Predicate Pred1;
1439	Constant *C2;
1440	Value *ReplacementLow, *ReplacementHigh;
1441	if (!match(V: Sel1, P: m_Select(C: m_Value(V&: Cmp1), L: m_Value(V&: ReplacementLow),
1442	R: m_Value(V&: ReplacementHigh))) ||
1443	!match(V: Cmp1,
1444	P: m_ICmp(Pred&: Pred1, L: m_Specific(V: X),
1445	R: m_CombineAnd(L: m_AnyIntegralConstant(), R: m_Constant(C&: C2)))))
1446	return nullptr;
1447
1448	if (!Cmp1->hasOneUse() && (Cmp00 == X || !Cmp00->hasOneUse()))
1449	return nullptr; // Not enough one-use instructions for the fold.
1450	// FIXME: this restriction could be relaxed if Cmp1 can be reused as one of
1451	// two comparisons we'll need to build.
1452
1453	// Canonicalize Cmp1 into the form we expect.
1454	// FIXME: we shouldn't care about lanes that are 'undef' in the end?
1455	switch (Pred1) {
1456	case ICmpInst::Predicate::ICMP_SLT:
1457	break;
1458	case ICmpInst::Predicate::ICMP_SLE:
1459	// We'd have to increment C2 by one, and for that it must not have signed
1460	// max element, but then it would have been canonicalized to 'slt' before
1461	// we get here. So we can't do anything useful with 'sle'.
1462	return nullptr;
1463	case ICmpInst::Predicate::ICMP_SGT:
1464	// We want to canonicalize it to 'slt', so we'll need to increment C2,
1465	// which again means it must not have any signed max elements.
1466	if (!match(V: C2,
1467	P: m_SpecificInt_ICMP(Predicate: ICmpInst::Predicate::ICMP_NE,
1468	Threshold: APInt::getSignedMaxValue(
1469	numBits: C2->getType()->getScalarSizeInBits()))))
1470	return nullptr; // Can't do, have signed max element[s].
1471	C2 = InstCombiner::AddOne(C: C2);
1472	[[fallthrough]];
1473	case ICmpInst::Predicate::ICMP_SGE:
1474	// Also non-canonical, but here we don't need to change C2,
1475	// so we don't have any restrictions on C2, so we can just handle it.
1476	Pred1 = ICmpInst::Predicate::ICMP_SLT;
1477	std::swap(a&: ReplacementLow, b&: ReplacementHigh);
1478	break;
1479	default:
1480	return nullptr; // Unknown predicate.
1481	}
1482	assert(Pred1 == ICmpInst::Predicate::ICMP_SLT &&
1483	"Unexpected predicate type.");
1484
1485	// The thresholds of this clamp-like pattern.
1486	auto *ThresholdLowIncl = ConstantExpr::getNeg(C: C1);
1487	auto *ThresholdHighExcl = ConstantExpr::getSub(C1: C0, C2: C1);
1488
1489	assert((Pred0 == ICmpInst::Predicate::ICMP_ULT ||
1490	Pred0 == ICmpInst::Predicate::ICMP_UGE) &&
1491	"Unexpected predicate type.");
1492	if (Pred0 == ICmpInst::Predicate::ICMP_UGE)
1493	std::swap(a&: ThresholdLowIncl, b&: ThresholdHighExcl);
1494
1495	// The fold has a precondition 1: C2 s>= ThresholdLow
1496	auto *Precond1 = ConstantExpr::getICmp(pred: ICmpInst::Predicate::ICMP_SGE, LHS: C2,
1497	RHS: ThresholdLowIncl);
1498	if (!match(V: Precond1, P: m_One()))
1499	return nullptr;
1500	// The fold has a precondition 2: C2 s<= ThresholdHigh
1501	auto *Precond2 = ConstantExpr::getICmp(pred: ICmpInst::Predicate::ICMP_SLE, LHS: C2,
1502	RHS: ThresholdHighExcl);
1503	if (!match(V: Precond2, P: m_One()))
1504	return nullptr;
1505
1506	// If we are matching from a truncated input, we need to sext the
1507	// ReplacementLow and ReplacementHigh values. Only do the transform if they
1508	// are free to extend due to being constants.
1509	if (X->getType() != Sel0.getType()) {
1510	Constant *LowC, *HighC;
1511	if (!match(V: ReplacementLow, P: m_ImmConstant(C&: LowC)) ||
1512	!match(V: ReplacementHigh, P: m_ImmConstant(C&: HighC)))
1513	return nullptr;
1514	const DataLayout &DL = Sel0.getModule()->getDataLayout();
1515	ReplacementLow =
1516	ConstantFoldCastOperand(Opcode: Instruction::SExt, C: LowC, DestTy: X->getType(), DL);
1517	ReplacementHigh =
1518	ConstantFoldCastOperand(Opcode: Instruction::SExt, C: HighC, DestTy: X->getType(), DL);
1519	assert(ReplacementLow && ReplacementHigh &&
1520	"Constant folding of ImmConstant cannot fail");
1521	}
1522
1523	// All good, finally emit the new pattern.
1524	Value *ShouldReplaceLow = Builder.CreateICmpSLT(LHS: X, RHS: ThresholdLowIncl);
1525	Value *ShouldReplaceHigh = Builder.CreateICmpSGE(LHS: X, RHS: ThresholdHighExcl);
1526	Value *MaybeReplacedLow =
1527	Builder.CreateSelect(C: ShouldReplaceLow, True: ReplacementLow, False: X);
1528
1529	// Create the final select. If we looked through a truncate above, we will
1530	// need to retruncate the result.
1531	Value *MaybeReplacedHigh = Builder.CreateSelect(
1532	C: ShouldReplaceHigh, True: ReplacementHigh, False: MaybeReplacedLow);
1533	return Builder.CreateTrunc(V: MaybeReplacedHigh, DestTy: Sel0.getType());
1534	}
1535
1536	// If we have
1537	// %cmp = icmp [canonical predicate] i32 %x, C0
1538	// %r = select i1 %cmp, i32 %y, i32 C1
1539	// Where C0 != C1 and %x may be different from %y, see if the constant that we
1540	// will have if we flip the strictness of the predicate (i.e. without changing
1541	// the result) is identical to the C1 in select. If it matches we can change
1542	// original comparison to one with swapped predicate, reuse the constant,
1543	// and swap the hands of select.
1544	static Instruction *
1545	tryToReuseConstantFromSelectInComparison(SelectInst &Sel, ICmpInst &Cmp,
1546	InstCombinerImpl &IC) {
1547	ICmpInst::Predicate Pred;
1548	Value *X;
1549	Constant *C0;
1550	if (!match(V: &Cmp, P: m_OneUse(SubPattern: m_ICmp(
1551	Pred, L: m_Value(V&: X),
1552	R: m_CombineAnd(L: m_AnyIntegralConstant(), R: m_Constant(C&: C0))))))
1553	return nullptr;
1554
1555	// If comparison predicate is non-relational, we won't be able to do anything.
1556	if (ICmpInst::isEquality(P: Pred))
1557	return nullptr;
1558
1559	// If comparison predicate is non-canonical, then we certainly won't be able
1560	// to make it canonical; canonicalizeCmpWithConstant() already tried.
1561	if (!InstCombiner::isCanonicalPredicate(Pred))
1562	return nullptr;
1563
1564	// If the [input] type of comparison and select type are different, lets abort
1565	// for now. We could try to compare constants with trunc/[zs]ext though.
1566	if (C0->getType() != Sel.getType())
1567	return nullptr;
1568
1569	// ULT with 'add' of a constant is canonical. See foldICmpAddConstant().
1570	// FIXME: Are there more magic icmp predicate+constant pairs we must avoid?
1571	// Or should we just abandon this transform entirely?
1572	if (Pred == CmpInst::ICMP_ULT && match(V: X, P: m_Add(L: m_Value(), R: m_Constant())))
1573	return nullptr;
1574
1575
1576	Value *SelVal0, *SelVal1; // We do not care which one is from where.
1577	match(V: &Sel, P: m_Select(C: m_Value(), L: m_Value(V&: SelVal0), R: m_Value(V&: SelVal1)));
1578	// At least one of these values we are selecting between must be a constant
1579	// else we'll never succeed.
1580	if (!match(V: SelVal0, P: m_AnyIntegralConstant()) &&
1581	!match(V: SelVal1, P: m_AnyIntegralConstant()))
1582	return nullptr;
1583
1584	// Does this constant C match any of the `select` values?
1585	auto MatchesSelectValue = [SelVal0, SelVal1](Constant *C) {
1586	return C->isElementWiseEqual(Y: SelVal0) || C->isElementWiseEqual(Y: SelVal1);
1587	};
1588
1589	// If C0 *already* matches true/false value of select, we are done.
1590	if (MatchesSelectValue(C0))
1591	return nullptr;
1592
1593	// Check the constant we'd have with flipped-strictness predicate.
1594	auto FlippedStrictness =
1595	InstCombiner::getFlippedStrictnessPredicateAndConstant(Pred, C: C0);
1596	if (!FlippedStrictness)
1597	return nullptr;
1598
1599	// If said constant doesn't match either, then there is no hope,
1600	if (!MatchesSelectValue(FlippedStrictness->second))
1601	return nullptr;
1602
1603	// It matched! Lets insert the new comparison just before select.
1604	InstCombiner::BuilderTy::InsertPointGuard Guard(IC.Builder);
1605	IC.Builder.SetInsertPoint(&Sel);
1606
1607	Pred = ICmpInst::getSwappedPredicate(pred: Pred); // Yes, swapped.
1608	Value *NewCmp = IC.Builder.CreateICmp(P: Pred, LHS: X, RHS: FlippedStrictness->second,
1609	Name: Cmp.getName() + ".inv");
1610	IC.replaceOperand(I&: Sel, OpNum: 0, V: NewCmp);
1611	Sel.swapValues();
1612	Sel.swapProfMetadata();
1613
1614	return &Sel;
1615	}
1616
1617	static Instruction *foldSelectZeroOrOnes(ICmpInst *Cmp, Value *TVal,
1618	Value *FVal,
1619	InstCombiner::BuilderTy &Builder) {
1620	if (!Cmp->hasOneUse())
1621	return nullptr;
1622
1623	const APInt *CmpC;
1624	if (!match(V: Cmp->getOperand(i_nocapture: 1), P: m_APIntAllowPoison(Res&: CmpC)))
1625	return nullptr;
1626
1627	// (X u< 2) ? -X : -1 --> sext (X != 0)
1628	Value *X = Cmp->getOperand(i_nocapture: 0);
1629	if (Cmp->getPredicate() == ICmpInst::ICMP_ULT && *CmpC == 2 &&
1630	match(V: TVal, P: m_Neg(V: m_Specific(V: X))) && match(V: FVal, P: m_AllOnes()))
1631	return new SExtInst(Builder.CreateIsNotNull(Arg: X), TVal->getType());
1632
1633	// (X u> 1) ? -1 : -X --> sext (X != 0)
1634	if (Cmp->getPredicate() == ICmpInst::ICMP_UGT && *CmpC == 1 &&
1635	match(V: FVal, P: m_Neg(V: m_Specific(V: X))) && match(V: TVal, P: m_AllOnes()))
1636	return new SExtInst(Builder.CreateIsNotNull(Arg: X), TVal->getType());
1637
1638	return nullptr;
1639	}
1640
1641	static Value *foldSelectInstWithICmpConst(SelectInst &SI, ICmpInst *ICI,
1642	InstCombiner::BuilderTy &Builder) {
1643	const APInt *CmpC;
1644	Value *V;
1645	CmpInst::Predicate Pred;
1646	if (!match(V: ICI, P: m_ICmp(Pred, L: m_Value(V), R: m_APInt(Res&: CmpC))))
1647	return nullptr;
1648
1649	// Match clamp away from min/max value as a max/min operation.
1650	Value *TVal = SI.getTrueValue();
1651	Value *FVal = SI.getFalseValue();
1652	if (Pred == ICmpInst::ICMP_EQ && V == FVal) {
1653	// (V == UMIN) ? UMIN+1 : V --> umax(V, UMIN+1)
1654	if (CmpC->isMinValue() && match(V: TVal, P: m_SpecificInt(V: *CmpC + 1)))
1655	return Builder.CreateBinaryIntrinsic(Intrinsic::ID: umax, LHS: V, RHS: TVal);
1656	// (V == UMAX) ? UMAX-1 : V --> umin(V, UMAX-1)
1657	if (CmpC->isMaxValue() && match(V: TVal, P: m_SpecificInt(V: *CmpC - 1)))
1658	return Builder.CreateBinaryIntrinsic(Intrinsic::ID: umin, LHS: V, RHS: TVal);
1659	// (V == SMIN) ? SMIN+1 : V --> smax(V, SMIN+1)
1660	if (CmpC->isMinSignedValue() && match(V: TVal, P: m_SpecificInt(V: *CmpC + 1)))
1661	return Builder.CreateBinaryIntrinsic(Intrinsic::ID: smax, LHS: V, RHS: TVal);
1662	// (V == SMAX) ? SMAX-1 : V --> smin(V, SMAX-1)
1663	if (CmpC->isMaxSignedValue() && match(V: TVal, P: m_SpecificInt(V: *CmpC - 1)))
1664	return Builder.CreateBinaryIntrinsic(Intrinsic::ID: smin, LHS: V, RHS: TVal);
1665	}
1666
1667	BinaryOperator *BO;
1668	const APInt *C;
1669	CmpInst::Predicate CPred;
1670	if (match(V: &SI, P: m_Select(C: m_Specific(V: ICI), L: m_APInt(Res&: C), R: m_BinOp(I&: BO))))
1671	CPred = ICI->getPredicate();
1672	else if (match(V: &SI, P: m_Select(C: m_Specific(V: ICI), L: m_BinOp(I&: BO), R: m_APInt(Res&: C))))
1673	CPred = ICI->getInversePredicate();
1674	else
1675	return nullptr;
1676
1677	const APInt *BinOpC;
1678	if (!match(V: BO, P: m_BinOp(L: m_Specific(V), R: m_APInt(Res&: BinOpC))))
1679	return nullptr;
1680
1681	ConstantRange R = ConstantRange::makeExactICmpRegion(Pred: CPred, Other: *CmpC)
1682	.binaryOp(BinOp: BO->getOpcode(), Other: *BinOpC);
1683	if (R == *C) {
1684	BO->dropPoisonGeneratingFlags();
1685	return BO;
1686	}
1687	return nullptr;
1688	}
1689
1690	static Instruction *foldSelectICmpEq(SelectInst &SI, ICmpInst *ICI,
1691	InstCombinerImpl &IC) {
1692	ICmpInst::Predicate Pred = ICI->getPredicate();
1693	if (!ICmpInst::isEquality(P: Pred))
1694	return nullptr;
1695
1696	Value *TrueVal = SI.getTrueValue();
1697	Value *FalseVal = SI.getFalseValue();
1698	Value *CmpLHS = ICI->getOperand(i_nocapture: 0);
1699	Value *CmpRHS = ICI->getOperand(i_nocapture: 1);
1700
1701	if (Pred == ICmpInst::ICMP_NE)
1702	std::swap(a&: TrueVal, b&: FalseVal);
1703
1704	// Transform (X == C) ? X : Y -> (X == C) ? C : Y
1705	// specific handling for Bitwise operation.
1706	// x&y -> (x|y) ^ (x^y) or (x|y) & ~(x^y)
1707	// x|y -> (x&y) | (x^y) or (x&y) ^ (x^y)
1708	// x^y -> (x|y) ^ (x&y) or (x|y) & ~(x&y)
1709	Value *X, *Y;
1710	if (!match(V: CmpLHS, P: m_BitwiseLogic(L: m_Value(V&: X), R: m_Value(V&: Y))) ||
1711	!match(V: TrueVal, P: m_c_BitwiseLogic(L: m_Specific(V: X), R: m_Specific(V: Y))))
1712	return nullptr;
1713
1714	const unsigned AndOps = Instruction::And, OrOps = Instruction::Or,
1715	XorOps = Instruction::Xor, NoOps = 0;
1716	enum NotMask { None = 0, NotInner, NotRHS };
1717
1718	auto matchFalseVal = [&](unsigned OuterOpc, unsigned InnerOpc,
1719	unsigned NotMask) {
1720	auto matchInner = m_c_BinOp(Opcode: InnerOpc, L: m_Specific(V: X), R: m_Specific(V: Y));
1721	if (OuterOpc == NoOps)
1722	return match(V: CmpRHS, P: m_Zero()) && match(V: FalseVal, P: matchInner);
1723
1724	if (NotMask == NotInner) {
1725	return match(V: FalseVal, P: m_c_BinOp(Opcode: OuterOpc, L: m_NotForbidPoison(V: matchInner),
1726	R: m_Specific(V: CmpRHS)));
1727	} else if (NotMask == NotRHS) {
1728	return match(V: FalseVal, P: m_c_BinOp(Opcode: OuterOpc, L: matchInner,
1729	R: m_NotForbidPoison(V: m_Specific(V: CmpRHS))));
1730	} else {
1731	return match(V: FalseVal,
1732	P: m_c_BinOp(Opcode: OuterOpc, L: matchInner, R: m_Specific(V: CmpRHS)));
1733	}
1734	};
1735
1736	// (X&Y)==C ? X|Y : X^Y -> (X^Y)|C : X^Y or (X^Y)^ C : X^Y
1737	// (X&Y)==C ? X^Y : X|Y -> (X|Y)^C : X|Y or (X|Y)&~C : X|Y
1738	if (match(V: CmpLHS, P: m_And(L: m_Value(V&: X), R: m_Value(V&: Y)))) {
1739	if (match(V: TrueVal, P: m_c_Or(L: m_Specific(V: X), R: m_Specific(V: Y)))) {
1740	// (X&Y)==C ? X|Y : (X^Y)|C -> (X^Y)|C : (X^Y)|C -> (X^Y)|C
1741	// (X&Y)==C ? X|Y : (X^Y)^C -> (X^Y)^C : (X^Y)^C -> (X^Y)^C
1742	if (matchFalseVal(OrOps, XorOps, None) ||
1743	matchFalseVal(XorOps, XorOps, None))
1744	return IC.replaceInstUsesWith(I&: SI, V: FalseVal);
1745	} else if (match(V: TrueVal, P: m_c_Xor(L: m_Specific(V: X), R: m_Specific(V: Y)))) {
1746	// (X&Y)==C ? X^Y : (X|Y)^ C -> (X|Y)^ C : (X|Y)^ C -> (X|Y)^ C
1747	// (X&Y)==C ? X^Y : (X|Y)&~C -> (X|Y)&~C : (X|Y)&~C -> (X|Y)&~C
1748	if (matchFalseVal(XorOps, OrOps, None) ||
1749	matchFalseVal(AndOps, OrOps, NotRHS))
1750	return IC.replaceInstUsesWith(I&: SI, V: FalseVal);
1751	}
1752	}
1753
1754	// (X|Y)==C ? X&Y : X^Y -> (X^Y)^C : X^Y or ~(X^Y)&C : X^Y
1755	// (X|Y)==C ? X^Y : X&Y -> (X&Y)^C : X&Y or ~(X&Y)&C : X&Y
1756	if (match(V: CmpLHS, P: m_Or(L: m_Value(V&: X), R: m_Value(V&: Y)))) {
1757	if (match(V: TrueVal, P: m_c_And(L: m_Specific(V: X), R: m_Specific(V: Y)))) {
1758	// (X|Y)==C ? X&Y: (X^Y)^C -> (X^Y)^C: (X^Y)^C -> (X^Y)^C
1759	// (X|Y)==C ? X&Y:~(X^Y)&C ->~(X^Y)&C:~(X^Y)&C -> ~(X^Y)&C
1760	if (matchFalseVal(XorOps, XorOps, None) ||
1761	matchFalseVal(AndOps, XorOps, NotInner))
1762	return IC.replaceInstUsesWith(I&: SI, V: FalseVal);
1763	} else if (match(V: TrueVal, P: m_c_Xor(L: m_Specific(V: X), R: m_Specific(V: Y)))) {
1764	// (X|Y)==C ? X^Y : (X&Y)^C -> (X&Y)^C : (X&Y)^C -> (X&Y)^C
1765	// (X|Y)==C ? X^Y :~(X&Y)&C -> ~(X&Y)&C :~(X&Y)&C -> ~(X&Y)&C
1766	if (matchFalseVal(XorOps, AndOps, None) ||
1767	matchFalseVal(AndOps, AndOps, NotInner))
1768	return IC.replaceInstUsesWith(I&: SI, V: FalseVal);
1769	}
1770	}
1771
1772	// (X^Y)==C ? X&Y : X|Y -> (X|Y)^C : X|Y or (X|Y)&~C : X|Y
1773	// (X^Y)==C ? X|Y : X&Y -> (X&Y)|C : X&Y or (X&Y)^ C : X&Y
1774	if (match(V: CmpLHS, P: m_Xor(L: m_Value(V&: X), R: m_Value(V&: Y)))) {
1775	if ((match(V: TrueVal, P: m_c_And(L: m_Specific(V: X), R: m_Specific(V: Y))))) {
1776	// (X^Y)==C ? X&Y : (X|Y)^C -> (X|Y)^C
1777	// (X^Y)==C ? X&Y : (X|Y)&~C -> (X|Y)&~C
1778	if (matchFalseVal(XorOps, OrOps, None) ||
1779	matchFalseVal(AndOps, OrOps, NotRHS))
1780	return IC.replaceInstUsesWith(I&: SI, V: FalseVal);
1781	} else if (match(V: TrueVal, P: m_c_Or(L: m_Specific(V: X), R: m_Specific(V: Y)))) {
1782	// (X^Y)==C ? (X|Y) : (X&Y)|C -> (X&Y)|C
1783	// (X^Y)==C ? (X|Y) : (X&Y)^C -> (X&Y)^C
1784	if (matchFalseVal(OrOps, AndOps, None) ||
1785	matchFalseVal(XorOps, AndOps, None))
1786	return IC.replaceInstUsesWith(I&: SI, V: FalseVal);
1787	}
1788	}
1789
1790	return nullptr;
1791	}
1792
1793	/// Visit a SelectInst that has an ICmpInst as its first operand.
1794	Instruction *InstCombinerImpl::foldSelectInstWithICmp(SelectInst &SI,
1795	ICmpInst *ICI) {
1796	if (Instruction *NewSel = foldSelectValueEquivalence(Sel&: SI, Cmp&: *ICI))
1797	return NewSel;
1798
1799	if (Value *V =
1800	canonicalizeSPF(Cmp&: *ICI, TrueVal: SI.getTrueValue(), FalseVal: SI.getFalseValue(), IC&: *this))
1801	return replaceInstUsesWith(I&: SI, V);
1802
1803	if (Value *V = foldSelectInstWithICmpConst(SI, ICI, Builder))
1804	return replaceInstUsesWith(I&: SI, V);
1805
1806	if (Value *V = canonicalizeClampLike(Sel0&: SI, Cmp0&: *ICI, Builder))
1807	return replaceInstUsesWith(I&: SI, V);
1808
1809	if (Instruction *NewSel =
1810	tryToReuseConstantFromSelectInComparison(Sel&: SI, Cmp&: *ICI, IC&: *this))
1811	return NewSel;
1812
1813	if (Value *V = foldSelectICmpAnd(Sel&: SI, Cmp: ICI, Builder))
1814	return replaceInstUsesWith(I&: SI, V);
1815
1816	// NOTE: if we wanted to, this is where to detect integer MIN/MAX
1817	bool Changed = false;
1818	Value *TrueVal = SI.getTrueValue();
1819	Value *FalseVal = SI.getFalseValue();
1820	ICmpInst::Predicate Pred = ICI->getPredicate();
1821	Value *CmpLHS = ICI->getOperand(i_nocapture: 0);
1822	Value *CmpRHS = ICI->getOperand(i_nocapture: 1);
1823	if (CmpRHS != CmpLHS && isa<Constant>(Val: CmpRHS) && !isa<Constant>(Val: CmpLHS)) {
1824	if (CmpLHS == TrueVal && Pred == ICmpInst::ICMP_EQ) {
1825	// Transform (X == C) ? X : Y -> (X == C) ? C : Y
1826	replaceOperand(I&: SI, OpNum: 1, V: CmpRHS);
1827	Changed = true;
1828	} else if (CmpLHS == FalseVal && Pred == ICmpInst::ICMP_NE) {
1829	// Transform (X != C) ? Y : X -> (X != C) ? Y : C
1830	replaceOperand(I&: SI, OpNum: 2, V: CmpRHS);
1831	Changed = true;
1832	}
1833	}
1834
1835	if (Instruction *NewSel = foldSelectICmpEq(SI, ICI, IC&: *this))
1836	return NewSel;
1837
1838	// Canonicalize a signbit condition to use zero constant by swapping:
1839	// (CmpLHS > -1) ? TV : FV --> (CmpLHS < 0) ? FV : TV
1840	// To avoid conflicts (infinite loops) with other canonicalizations, this is
1841	// not applied with any constant select arm.
1842	if (Pred == ICmpInst::ICMP_SGT && match(V: CmpRHS, P: m_AllOnes()) &&
1843	!match(V: TrueVal, P: m_Constant()) && !match(V: FalseVal, P: m_Constant()) &&
1844	ICI->hasOneUse()) {
1845	InstCombiner::BuilderTy::InsertPointGuard Guard(Builder);
1846	Builder.SetInsertPoint(&SI);
1847	Value *IsNeg = Builder.CreateIsNeg(Arg: CmpLHS, Name: ICI->getName());
1848	replaceOperand(I&: SI, OpNum: 0, V: IsNeg);
1849	SI.swapValues();
1850	SI.swapProfMetadata();
1851	return &SI;
1852	}
1853
1854	// FIXME: This code is nearly duplicated in InstSimplify. Using/refactoring
1855	// decomposeBitTestICmp() might help.
1856	if (TrueVal->getType()->isIntOrIntVectorTy()) {
1857	unsigned BitWidth =
1858	DL.getTypeSizeInBits(Ty: TrueVal->getType()->getScalarType());
1859	APInt MinSignedValue = APInt::getSignedMinValue(numBits: BitWidth);
1860	Value *X;
1861	const APInt *Y, *C;
1862	bool TrueWhenUnset;
1863	bool IsBitTest = false;
1864	if (ICmpInst::isEquality(P: Pred) &&
1865	match(V: CmpLHS, P: m_And(L: m_Value(V&: X), R: m_Power2(V&: Y))) &&
1866	match(V: CmpRHS, P: m_Zero())) {
1867	IsBitTest = true;
1868	TrueWhenUnset = Pred == ICmpInst::ICMP_EQ;
1869	} else if (Pred == ICmpInst::ICMP_SLT && match(V: CmpRHS, P: m_Zero())) {
1870	X = CmpLHS;
1871	Y = &MinSignedValue;
1872	IsBitTest = true;
1873	TrueWhenUnset = false;
1874	} else if (Pred == ICmpInst::ICMP_SGT && match(V: CmpRHS, P: m_AllOnes())) {
1875	X = CmpLHS;
1876	Y = &MinSignedValue;
1877	IsBitTest = true;
1878	TrueWhenUnset = true;
1879	}
1880	if (IsBitTest) {
1881	Value *V = nullptr;
1882	// (X & Y) == 0 ? X : X ^ Y --> X & ~Y
1883	if (TrueWhenUnset && TrueVal == X &&
1884	match(V: FalseVal, P: m_Xor(L: m_Specific(V: X), R: m_APInt(Res&: C))) && *Y == *C)
1885	V = Builder.CreateAnd(LHS: X, RHS: ~(*Y));
1886	// (X & Y) != 0 ? X ^ Y : X --> X & ~Y
1887	else if (!TrueWhenUnset && FalseVal == X &&
1888	match(V: TrueVal, P: m_Xor(L: m_Specific(V: X), R: m_APInt(Res&: C))) && *Y == *C)
1889	V = Builder.CreateAnd(LHS: X, RHS: ~(*Y));
1890	// (X & Y) == 0 ? X ^ Y : X --> X | Y
1891	else if (TrueWhenUnset && FalseVal == X &&
1892	match(V: TrueVal, P: m_Xor(L: m_Specific(V: X), R: m_APInt(Res&: C))) && *Y == *C)
1893	V = Builder.CreateOr(LHS: X, RHS: *Y);
1894	// (X & Y) != 0 ? X : X ^ Y --> X | Y
1895	else if (!TrueWhenUnset && TrueVal == X &&
1896	match(V: FalseVal, P: m_Xor(L: m_Specific(V: X), R: m_APInt(Res&: C))) && *Y == *C)
1897	V = Builder.CreateOr(LHS: X, RHS: *Y);
1898
1899	if (V)
1900	return replaceInstUsesWith(I&: SI, V);
1901	}
1902	}
1903
1904	if (Instruction *V =
1905	foldSelectICmpAndAnd(SelType: SI.getType(), Cmp: ICI, TVal: TrueVal, FVal: FalseVal, Builder))
1906	return V;
1907
1908	if (Value *V = foldSelectICmpAndZeroShl(Cmp: ICI, TVal: TrueVal, FVal: FalseVal, Builder))
1909	return replaceInstUsesWith(I&: SI, V);
1910
1911	if (Instruction *V = foldSelectCtlzToCttz(ICI, TrueVal, FalseVal, Builder))
1912	return V;
1913
1914	if (Instruction *V = foldSelectZeroOrOnes(Cmp: ICI, TVal: TrueVal, FVal: FalseVal, Builder))
1915	return V;
1916
1917	if (Value *V = foldSelectICmpAndBinOp(IC: ICI, TrueVal, FalseVal, Builder))
1918	return replaceInstUsesWith(I&: SI, V);
1919
1920	if (Value *V = foldSelectICmpLshrAshr(IC: ICI, TrueVal, FalseVal, Builder))
1921	return replaceInstUsesWith(I&: SI, V);
1922
1923	if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
1924	return replaceInstUsesWith(I&: SI, V);
1925
1926	if (Value *V = canonicalizeSaturatedSubtract(ICI, TrueVal, FalseVal, Builder))
1927	return replaceInstUsesWith(I&: SI, V);
1928
1929	if (Value *V = canonicalizeSaturatedAdd(Cmp: ICI, TVal: TrueVal, FVal: FalseVal, Builder))
1930	return replaceInstUsesWith(I&: SI, V);
1931
1932	if (Value *V = foldAbsDiff(Cmp: ICI, TVal: TrueVal, FVal: FalseVal, Builder))
1933	return replaceInstUsesWith(I&: SI, V);
1934
1935	return Changed ? &SI : nullptr;
1936	}
1937
1938	/// SI is a select whose condition is a PHI node (but the two may be in
1939	/// different blocks). See if the true/false values (V) are live in all of the
1940	/// predecessor blocks of the PHI. For example, cases like this can't be mapped:
1941	///
1942	/// X = phi [ C1, BB1], [C2, BB2]
1943	/// Y = add
1944	/// Z = select X, Y, 0
1945	///
1946	/// because Y is not live in BB1/BB2.
1947	static bool canSelectOperandBeMappingIntoPredBlock(const Value *V,
1948	const SelectInst &SI) {
1949	// If the value is a non-instruction value like a constant or argument, it
1950	// can always be mapped.
1951	const Instruction *I = dyn_cast<Instruction>(Val: V);
1952	if (!I) return true;
1953
1954	// If V is a PHI node defined in the same block as the condition PHI, we can
1955	// map the arguments.
1956	const PHINode *CondPHI = cast<PHINode>(Val: SI.getCondition());
1957
1958	if (const PHINode *VP = dyn_cast<PHINode>(Val: I))
1959	if (VP->getParent() == CondPHI->getParent())
1960	return true;
1961
1962	// Otherwise, if the PHI and select are defined in the same block and if V is
1963	// defined in a different block, then we can transform it.
1964	if (SI.getParent() == CondPHI->getParent() &&
1965	I->getParent() != CondPHI->getParent())
1966	return true;
1967
1968	// Otherwise we have a 'hard' case and we can't tell without doing more
1969	// detailed dominator based analysis, punt.
1970	return false;
1971	}
1972
1973	/// We have an SPF (e.g. a min or max) of an SPF of the form:
1974	/// SPF2(SPF1(A, B), C)
1975	Instruction *InstCombinerImpl::foldSPFofSPF(Instruction *Inner,
1976	SelectPatternFlavor SPF1, Value *A,
1977	Value *B, Instruction &Outer,
1978	SelectPatternFlavor SPF2,
1979	Value *C) {
1980	if (Outer.getType() != Inner->getType())
1981	return nullptr;
1982
1983	if (C == A || C == B) {
1984	// MAX(MAX(A, B), B) -> MAX(A, B)
1985	// MIN(MIN(a, b), a) -> MIN(a, b)
1986	// TODO: This could be done in instsimplify.
1987	if (SPF1 == SPF2 && SelectPatternResult::isMinOrMax(SPF: SPF1))
1988	return replaceInstUsesWith(I&: Outer, V: Inner);
1989	}
1990
1991	return nullptr;
1992	}
1993
1994	/// Turn select C, (X + Y), (X - Y) --> (X + (select C, Y, (-Y))).
1995	/// This is even legal for FP.
1996	static Instruction *foldAddSubSelect(SelectInst &SI,
1997	InstCombiner::BuilderTy &Builder) {
1998	Value *CondVal = SI.getCondition();
1999	Value *TrueVal = SI.getTrueValue();
2000	Value *FalseVal = SI.getFalseValue();
2001	auto *TI = dyn_cast<Instruction>(Val: TrueVal);
2002	auto *FI = dyn_cast<Instruction>(Val: FalseVal);
2003	if (!TI || !FI || !TI->hasOneUse() || !FI->hasOneUse())
2004	return nullptr;
2005
2006	Instruction *AddOp = nullptr, *SubOp = nullptr;
2007	if ((TI->getOpcode() == Instruction::Sub &&
2008	FI->getOpcode() == Instruction::Add) ||
2009	(TI->getOpcode() == Instruction::FSub &&
2010	FI->getOpcode() == Instruction::FAdd)) {
2011	AddOp = FI;
2012	SubOp = TI;
2013	} else if ((FI->getOpcode() == Instruction::Sub &&
2014	TI->getOpcode() == Instruction::Add) ||
2015	(FI->getOpcode() == Instruction::FSub &&
2016	TI->getOpcode() == Instruction::FAdd)) {
2017	AddOp = TI;
2018	SubOp = FI;
2019	}
2020
2021	if (AddOp) {
2022	Value *OtherAddOp = nullptr;
2023	if (SubOp->getOperand(i: 0) == AddOp->getOperand(i: 0)) {
2024	OtherAddOp = AddOp->getOperand(i: 1);
2025	} else if (SubOp->getOperand(i: 0) == AddOp->getOperand(i: 1)) {
2026	OtherAddOp = AddOp->getOperand(i: 0);
2027	}
2028
2029	if (OtherAddOp) {
2030	// So at this point we know we have (Y -> OtherAddOp):
2031	// select C, (add X, Y), (sub X, Z)
2032	Value *NegVal; // Compute -Z
2033	if (SI.getType()->isFPOrFPVectorTy()) {
2034	NegVal = Builder.CreateFNeg(V: SubOp->getOperand(i: 1));
2035	if (Instruction *NegInst = dyn_cast<Instruction>(Val: NegVal)) {
2036	FastMathFlags Flags = AddOp->getFastMathFlags();
2037	Flags &= SubOp->getFastMathFlags();
2038	NegInst->setFastMathFlags(Flags);
2039	}
2040	} else {
2041	NegVal = Builder.CreateNeg(V: SubOp->getOperand(i: 1));
2042	}
2043
2044	Value *NewTrueOp = OtherAddOp;
2045	Value *NewFalseOp = NegVal;
2046	if (AddOp != TI)
2047	std::swap(a&: NewTrueOp, b&: NewFalseOp);
2048	Value *NewSel = Builder.CreateSelect(C: CondVal, True: NewTrueOp, False: NewFalseOp,
2049	Name: SI.getName() + ".p", MDFrom: &SI);
2050
2051	if (SI.getType()->isFPOrFPVectorTy()) {
2052	Instruction *RI =
2053	BinaryOperator::CreateFAdd(V1: SubOp->getOperand(i: 0), V2: NewSel);
2054
2055	FastMathFlags Flags = AddOp->getFastMathFlags();
2056	Flags &= SubOp->getFastMathFlags();
2057	RI->setFastMathFlags(Flags);
2058	return RI;
2059	} else
2060	return BinaryOperator::CreateAdd(V1: SubOp->getOperand(i: 0), V2: NewSel);
2061	}
2062	}
2063	return nullptr;
2064	}
2065
2066	/// Turn X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
2067	/// And X - Y overflows ? 0 : X - Y -> usub_sat X, Y
2068	/// Along with a number of patterns similar to:
2069	/// X + Y overflows ? (X < 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2070	/// X - Y overflows ? (X > 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2071	static Instruction *
2072	foldOverflowingAddSubSelect(SelectInst &SI, InstCombiner::BuilderTy &Builder) {
2073	Value *CondVal = SI.getCondition();
2074	Value *TrueVal = SI.getTrueValue();
2075	Value *FalseVal = SI.getFalseValue();
2076
2077	WithOverflowInst *II;
2078	if (!match(V: CondVal, P: m_ExtractValue<1>(V: m_WithOverflowInst(I&: II))) ||
2079	!match(V: FalseVal, P: m_ExtractValue<0>(V: m_Specific(V: II))))
2080	return nullptr;
2081
2082	Value *X = II->getLHS();
2083	Value *Y = II->getRHS();
2084
2085	auto IsSignedSaturateLimit = [&](Value *Limit, bool IsAdd) {
2086	Type *Ty = Limit->getType();
2087
2088	ICmpInst::Predicate Pred;
2089	Value *TrueVal, *FalseVal, *Op;
2090	const APInt *C;
2091	if (!match(V: Limit, P: m_Select(C: m_ICmp(Pred, L: m_Value(V&: Op), R: m_APInt(Res&: C)),
2092	L: m_Value(V&: TrueVal), R: m_Value(V&: FalseVal))))
2093	return false;
2094
2095	auto IsZeroOrOne = [](const APInt &C) { return C.isZero() || C.isOne(); };
2096	auto IsMinMax = [&](Value *Min, Value *Max) {
2097	APInt MinVal = APInt::getSignedMinValue(numBits: Ty->getScalarSizeInBits());
2098	APInt MaxVal = APInt::getSignedMaxValue(numBits: Ty->getScalarSizeInBits());
2099	return match(V: Min, P: m_SpecificInt(V: MinVal)) &&
2100	match(V: Max, P: m_SpecificInt(V: MaxVal));
2101	};
2102
2103	if (Op != X && Op != Y)
2104	return false;
2105
2106	if (IsAdd) {
2107	// X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2108	// X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2109	// X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2110	// X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2111	if (Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
2112	IsMinMax(TrueVal, FalseVal))
2113	return true;
2114	// X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
2115	// X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
2116	// X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
2117	// X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
2118	if (Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
2119	IsMinMax(FalseVal, TrueVal))
2120	return true;
2121	} else {
2122	// X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2123	// X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2124	if (Op == X && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C + 1) &&
2125	IsMinMax(TrueVal, FalseVal))
2126	return true;
2127	// X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2128	// X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2129	if (Op == X && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 2) &&
2130	IsMinMax(FalseVal, TrueVal))
2131	return true;
2132	// X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2133	// X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2134	if (Op == Y && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
2135	IsMinMax(FalseVal, TrueVal))
2136	return true;
2137	// X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2138	// X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2139	if (Op == Y && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
2140	IsMinMax(TrueVal, FalseVal))
2141	return true;
2142	}
2143
2144	return false;
2145	};
2146
2147	Intrinsic::ID NewIntrinsicID;
2148	if (II->getIntrinsicID() == Intrinsic::uadd_with_overflow &&
2149	match(V: TrueVal, P: m_AllOnes()))
2150	// X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
2151	NewIntrinsicID = Intrinsic::uadd_sat;
2152	else if (II->getIntrinsicID() == Intrinsic::usub_with_overflow &&
2153	match(V: TrueVal, P: m_Zero()))
2154	// X - Y overflows ? 0 : X - Y -> usub_sat X, Y
2155	NewIntrinsicID = Intrinsic::usub_sat;
2156	else if (II->getIntrinsicID() == Intrinsic::sadd_with_overflow &&
2157	IsSignedSaturateLimit(TrueVal, /*IsAdd=*/true))
2158	// X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2159	// X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2160	// X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
2161	// X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
2162	// X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2163	// X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2164	// X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
2165	// X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
2166	NewIntrinsicID = Intrinsic::sadd_sat;
2167	else if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow &&
2168	IsSignedSaturateLimit(TrueVal, /*IsAdd=*/false))
2169	// X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2170	// X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2171	// X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2172	// X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2173	// X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2174	// X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2175	// X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2176	// X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2177	NewIntrinsicID = Intrinsic::ssub_sat;
2178	else
2179	return nullptr;
2180
2181	Function *F =
2182	Intrinsic::getDeclaration(M: SI.getModule(), id: NewIntrinsicID, Tys: SI.getType());
2183	return CallInst::Create(Func: F, Args: {X, Y});
2184	}
2185
2186	Instruction *InstCombinerImpl::foldSelectExtConst(SelectInst &Sel) {
2187	Constant *C;
2188	if (!match(V: Sel.getTrueValue(), P: m_Constant(C)) &&
2189	!match(V: Sel.getFalseValue(), P: m_Constant(C)))
2190	return nullptr;
2191
2192	Instruction *ExtInst;
2193	if (!match(V: Sel.getTrueValue(), P: m_Instruction(I&: ExtInst)) &&
2194	!match(V: Sel.getFalseValue(), P: m_Instruction(I&: ExtInst)))
2195	return nullptr;
2196
2197	auto ExtOpcode = ExtInst->getOpcode();
2198	if (ExtOpcode != Instruction::ZExt && ExtOpcode != Instruction::SExt)
2199	return nullptr;
2200
2201	// If we are extending from a boolean type or if we can create a select that
2202	// has the same size operands as its condition, try to narrow the select.
2203	Value *X = ExtInst->getOperand(i: 0);
2204	Type *SmallType = X->getType();
2205	Value *Cond = Sel.getCondition();
2206	auto *Cmp = dyn_cast<CmpInst>(Val: Cond);
2207	if (!SmallType->isIntOrIntVectorTy(BitWidth: 1) &&
2208	(!Cmp || Cmp->getOperand(i_nocapture: 0)->getType() != SmallType))
2209	return nullptr;
2210
2211	// If the constant is the same after truncation to the smaller type and
2212	// extension to the original type, we can narrow the select.
2213	Type *SelType = Sel.getType();
2214	Constant *TruncC = getLosslessTrunc(C, TruncTy: SmallType, ExtOp: ExtOpcode);
2215	if (TruncC && ExtInst->hasOneUse()) {
2216	Value *TruncCVal = cast<Value>(Val: TruncC);
2217	if (ExtInst == Sel.getFalseValue())
2218	std::swap(a&: X, b&: TruncCVal);
2219
2220	// select Cond, (ext X), C --> ext(select Cond, X, C')
2221	// select Cond, C, (ext X) --> ext(select Cond, C', X)
2222	Value *NewSel = Builder.CreateSelect(C: Cond, True: X, False: TruncCVal, Name: "narrow", MDFrom: &Sel);
2223	return CastInst::Create(Instruction::CastOps(ExtOpcode), S: NewSel, Ty: SelType);
2224	}
2225
2226	return nullptr;
2227	}
2228
2229	/// Try to transform a vector select with a constant condition vector into a
2230	/// shuffle for easier combining with other shuffles and insert/extract.
2231	static Instruction *canonicalizeSelectToShuffle(SelectInst &SI) {
2232	Value *CondVal = SI.getCondition();
2233	Constant *CondC;
2234	auto *CondValTy = dyn_cast<FixedVectorType>(Val: CondVal->getType());
2235	if (!CondValTy || !match(V: CondVal, P: m_Constant(C&: CondC)))
2236	return nullptr;
2237
2238	unsigned NumElts = CondValTy->getNumElements();
2239	SmallVector<int, 16> Mask;
2240	Mask.reserve(N: NumElts);
2241	for (unsigned i = 0; i != NumElts; ++i) {
2242	Constant *Elt = CondC->getAggregateElement(Elt: i);
2243	if (!Elt)
2244	return nullptr;
2245
2246	if (Elt->isOneValue()) {
2247	// If the select condition element is true, choose from the 1st vector.
2248	Mask.push_back(Elt: i);
2249	} else if (Elt->isNullValue()) {
2250	// If the select condition element is false, choose from the 2nd vector.
2251	Mask.push_back(Elt: i + NumElts);
2252	} else if (isa<UndefValue>(Val: Elt)) {
2253	// Undef in a select condition (choose one of the operands) does not mean
2254	// the same thing as undef in a shuffle mask (any value is acceptable), so
2255	// give up.
2256	return nullptr;
2257	} else {
2258	// Bail out on a constant expression.
2259	return nullptr;
2260	}
2261	}
2262
2263	return new ShuffleVectorInst(SI.getTrueValue(), SI.getFalseValue(), Mask);
2264	}
2265
2266	/// If we have a select of vectors with a scalar condition, try to convert that
2267	/// to a vector select by splatting the condition. A splat may get folded with
2268	/// other operations in IR and having all operands of a select be vector types
2269	/// is likely better for vector codegen.
2270	static Instruction *canonicalizeScalarSelectOfVecs(SelectInst &Sel,
2271	InstCombinerImpl &IC) {
2272	auto *Ty = dyn_cast<VectorType>(Val: Sel.getType());
2273	if (!Ty)
2274	return nullptr;
2275
2276	// We can replace a single-use extract with constant index.
2277	Value *Cond = Sel.getCondition();
2278	if (!match(V: Cond, P: m_OneUse(SubPattern: m_ExtractElt(Val: m_Value(), Idx: m_ConstantInt()))))
2279	return nullptr;
2280
2281	// select (extelt V, Index), T, F --> select (splat V, Index), T, F
2282	// Splatting the extracted condition reduces code (we could directly create a
2283	// splat shuffle of the source vector to eliminate the intermediate step).
2284	return IC.replaceOperand(
2285	I&: Sel, OpNum: 0, V: IC.Builder.CreateVectorSplat(EC: Ty->getElementCount(), V: Cond));
2286	}
2287
2288	/// Reuse bitcasted operands between a compare and select:
2289	/// select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2290	/// bitcast (select (cmp (bitcast C), (bitcast D)), (bitcast C), (bitcast D))
2291	static Instruction *foldSelectCmpBitcasts(SelectInst &Sel,
2292	InstCombiner::BuilderTy &Builder) {
2293	Value *Cond = Sel.getCondition();
2294	Value *TVal = Sel.getTrueValue();
2295	Value *FVal = Sel.getFalseValue();
2296
2297	CmpInst::Predicate Pred;
2298	Value *A, *B;
2299	if (!match(V: Cond, P: m_Cmp(Pred, L: m_Value(V&: A), R: m_Value(V&: B))))
2300	return nullptr;
2301
2302	// The select condition is a compare instruction. If the select's true/false
2303	// values are already the same as the compare operands, there's nothing to do.
2304	if (TVal == A || TVal == B || FVal == A || FVal == B)
2305	return nullptr;
2306
2307	Value *C, *D;
2308	if (!match(V: A, P: m_BitCast(Op: m_Value(V&: C))) || !match(V: B, P: m_BitCast(Op: m_Value(V&: D))))
2309	return nullptr;
2310
2311	// select (cmp (bitcast C), (bitcast D)), (bitcast TSrc), (bitcast FSrc)
2312	Value *TSrc, *FSrc;
2313	if (!match(V: TVal, P: m_BitCast(Op: m_Value(V&: TSrc))) ||
2314	!match(V: FVal, P: m_BitCast(Op: m_Value(V&: FSrc))))
2315	return nullptr;
2316
2317	// If the select true/false values are *different bitcasts* of the same source
2318	// operands, make the select operands the same as the compare operands and
2319	// cast the result. This is the canonical select form for min/max.
2320	Value *NewSel;
2321	if (TSrc == C && FSrc == D) {
2322	// select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2323	// bitcast (select (cmp A, B), A, B)
2324	NewSel = Builder.CreateSelect(C: Cond, True: A, False: B, Name: "", MDFrom: &Sel);
2325	} else if (TSrc == D && FSrc == C) {
2326	// select (cmp (bitcast C), (bitcast D)), (bitcast' D), (bitcast' C) -->
2327	// bitcast (select (cmp A, B), B, A)
2328	NewSel = Builder.CreateSelect(C: Cond, True: B, False: A, Name: "", MDFrom: &Sel);
2329	} else {
2330	return nullptr;
2331	}
2332	return CastInst::CreateBitOrPointerCast(S: NewSel, Ty: Sel.getType());
2333	}
2334
2335	/// Try to eliminate select instructions that test the returned flag of cmpxchg
2336	/// instructions.
2337	///
2338	/// If a select instruction tests the returned flag of a cmpxchg instruction and
2339	/// selects between the returned value of the cmpxchg instruction its compare
2340	/// operand, the result of the select will always be equal to its false value.
2341	/// For example:
2342	///
2343	/// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2344	/// %1 = extractvalue { i64, i1 } %0, 1
2345	/// %2 = extractvalue { i64, i1 } %0, 0
2346	/// %3 = select i1 %1, i64 %compare, i64 %2
2347	/// ret i64 %3
2348	///
2349	/// The returned value of the cmpxchg instruction (%2) is the original value
2350	/// located at %ptr prior to any update. If the cmpxchg operation succeeds, %2
2351	/// must have been equal to %compare. Thus, the result of the select is always
2352	/// equal to %2, and the code can be simplified to:
2353	///
2354	/// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2355	/// %1 = extractvalue { i64, i1 } %0, 0
2356	/// ret i64 %1
2357	///
2358	static Value *foldSelectCmpXchg(SelectInst &SI) {
2359	// A helper that determines if V is an extractvalue instruction whose
2360	// aggregate operand is a cmpxchg instruction and whose single index is equal
2361	// to I. If such conditions are true, the helper returns the cmpxchg
2362	// instruction; otherwise, a nullptr is returned.
2363	auto isExtractFromCmpXchg = [](Value *V, unsigned I) -> AtomicCmpXchgInst * {
2364	auto *Extract = dyn_cast<ExtractValueInst>(Val: V);
2365	if (!Extract)
2366	return nullptr;
2367	if (Extract->getIndices()[0] != I)
2368	return nullptr;
2369	return dyn_cast<AtomicCmpXchgInst>(Val: Extract->getAggregateOperand());
2370	};
2371
2372	// If the select has a single user, and this user is a select instruction that
2373	// we can simplify, skip the cmpxchg simplification for now.
2374	if (SI.hasOneUse())
2375	if (auto *Select = dyn_cast<SelectInst>(Val: SI.user_back()))
2376	if (Select->getCondition() == SI.getCondition())
2377	if (Select->getFalseValue() == SI.getTrueValue() ||
2378	Select->getTrueValue() == SI.getFalseValue())
2379	return nullptr;
2380
2381	// Ensure the select condition is the returned flag of a cmpxchg instruction.
2382	auto *CmpXchg = isExtractFromCmpXchg(SI.getCondition(), 1);
2383	if (!CmpXchg)
2384	return nullptr;
2385
2386	// Check the true value case: The true value of the select is the returned
2387	// value of the same cmpxchg used by the condition, and the false value is the
2388	// cmpxchg instruction's compare operand.
2389	if (auto *X = isExtractFromCmpXchg(SI.getTrueValue(), 0))
2390	if (X == CmpXchg && X->getCompareOperand() == SI.getFalseValue())
2391	return SI.getFalseValue();
2392
2393	// Check the false value case: The false value of the select is the returned
2394	// value of the same cmpxchg used by the condition, and the true value is the
2395	// cmpxchg instruction's compare operand.
2396	if (auto *X = isExtractFromCmpXchg(SI.getFalseValue(), 0))
2397	if (X == CmpXchg && X->getCompareOperand() == SI.getTrueValue())
2398	return SI.getFalseValue();
2399
2400	return nullptr;
2401	}
2402
2403	/// Try to reduce a funnel/rotate pattern that includes a compare and select
2404	/// into a funnel shift intrinsic. Example:
2405	/// rotl32(a, b) --> (b == 0 ? a : ((a >> (32 - b)) | (a << b)))
2406	/// --> call llvm.fshl.i32(a, a, b)
2407	/// fshl32(a, b, c) --> (c == 0 ? a : ((b >> (32 - c)) | (a << c)))
2408	/// --> call llvm.fshl.i32(a, b, c)
2409	/// fshr32(a, b, c) --> (c == 0 ? b : ((a >> (32 - c)) | (b << c)))
2410	/// --> call llvm.fshr.i32(a, b, c)
2411	static Instruction *foldSelectFunnelShift(SelectInst &Sel,
2412	InstCombiner::BuilderTy &Builder) {
2413	// This must be a power-of-2 type for a bitmasking transform to be valid.
2414	unsigned Width = Sel.getType()->getScalarSizeInBits();
2415	if (!isPowerOf2_32(Value: Width))
2416	return nullptr;
2417
2418	BinaryOperator *Or0, *Or1;
2419	if (!match(V: Sel.getFalseValue(), P: m_OneUse(SubPattern: m_Or(L: m_BinOp(I&: Or0), R: m_BinOp(I&: Or1)))))
2420	return nullptr;
2421
2422	Value *SV0, *SV1, *SA0, *SA1;
2423	if (!match(V: Or0, P: m_OneUse(SubPattern: m_LogicalShift(L: m_Value(V&: SV0),
2424	R: m_ZExtOrSelf(Op: m_Value(V&: SA0))))) ||
2425	!match(V: Or1, P: m_OneUse(SubPattern: m_LogicalShift(L: m_Value(V&: SV1),
2426	R: m_ZExtOrSelf(Op: m_Value(V&: SA1))))) ||
2427	Or0->getOpcode() == Or1->getOpcode())
2428	return nullptr;
2429
2430	// Canonicalize to or(shl(SV0, SA0), lshr(SV1, SA1)).
2431	if (Or0->getOpcode() == BinaryOperator::LShr) {
2432	std::swap(a&: Or0, b&: Or1);
2433	std::swap(a&: SV0, b&: SV1);
2434	std::swap(a&: SA0, b&: SA1);
2435	}
2436	assert(Or0->getOpcode() == BinaryOperator::Shl &&
2437	Or1->getOpcode() == BinaryOperator::LShr &&
2438	"Illegal or(shift,shift) pair");
2439
2440	// Check the shift amounts to see if they are an opposite pair.
2441	Value *ShAmt;
2442	if (match(V: SA1, P: m_OneUse(SubPattern: m_Sub(L: m_SpecificInt(V: Width), R: m_Specific(V: SA0)))))
2443	ShAmt = SA0;
2444	else if (match(V: SA0, P: m_OneUse(SubPattern: m_Sub(L: m_SpecificInt(V: Width), R: m_Specific(V: SA1)))))
2445	ShAmt = SA1;
2446	else
2447	return nullptr;
2448
2449	// We should now have this pattern:
2450	// select ?, TVal, (or (shl SV0, SA0), (lshr SV1, SA1))
2451	// The false value of the select must be a funnel-shift of the true value:
2452	// IsFShl -> TVal must be SV0 else TVal must be SV1.
2453	bool IsFshl = (ShAmt == SA0);
2454	Value *TVal = Sel.getTrueValue();
2455	if ((IsFshl && TVal != SV0) || (!IsFshl && TVal != SV1))
2456	return nullptr;
2457
2458	// Finally, see if the select is filtering out a shift-by-zero.
2459	Value *Cond = Sel.getCondition();
2460	ICmpInst::Predicate Pred;
2461	if (!match(V: Cond, P: m_OneUse(SubPattern: m_ICmp(Pred, L: m_Specific(V: ShAmt), R: m_ZeroInt()))) ||
2462	Pred != ICmpInst::ICMP_EQ)
2463	return nullptr;
2464
2465	// If this is not a rotate then the select was blocking poison from the
2466	// 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.
2467	if (SV0 != SV1) {
2468	if (IsFshl && !llvm::isGuaranteedNotToBePoison(V: SV1))
2469	SV1 = Builder.CreateFreeze(V: SV1);
2470	else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(V: SV0))
2471	SV0 = Builder.CreateFreeze(V: SV0);
2472	}
2473
2474	// This is a funnel/rotate that avoids shift-by-bitwidth UB in a suboptimal way.
2475	// Convert to funnel shift intrinsic.
2476	Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2477	Function *F = Intrinsic::getDeclaration(M: Sel.getModule(), id: IID, Tys: Sel.getType());
2478	ShAmt = Builder.CreateZExt(V: ShAmt, DestTy: Sel.getType());
2479	return CallInst::Create(Func: F, Args: { SV0, SV1, ShAmt });
2480	}
2481
2482	static Instruction *foldSelectToCopysign(SelectInst &Sel,
2483	InstCombiner::BuilderTy &Builder) {
2484	Value *Cond = Sel.getCondition();
2485	Value *TVal = Sel.getTrueValue();
2486	Value *FVal = Sel.getFalseValue();
2487	Type *SelType = Sel.getType();
2488
2489	// Match select ?, TC, FC where the constants are equal but negated.
2490	// TODO: Generalize to handle a negated variable operand?
2491	const APFloat *TC, *FC;
2492	if (!match(V: TVal, P: m_APFloatAllowPoison(Res&: TC)) ||
2493	!match(V: FVal, P: m_APFloatAllowPoison(Res&: FC)) ||
2494	!abs(X: *TC).bitwiseIsEqual(RHS: abs(X: *FC)))
2495	return nullptr;
2496
2497	assert(TC != FC && "Expected equal select arms to simplify");
2498
2499	Value *X;
2500	const APInt *C;
2501	bool IsTrueIfSignSet;
2502	ICmpInst::Predicate Pred;
2503	if (!match(V: Cond, P: m_OneUse(SubPattern: m_ICmp(Pred, L: m_ElementWiseBitCast(Op: m_Value(V&: X)),
2504	R: m_APInt(Res&: C)))) ||
2505	!isSignBitCheck(Pred, RHS: *C, TrueIfSigned&: IsTrueIfSignSet) || X->getType() != SelType)
2506	return nullptr;
2507
2508	// If needed, negate the value that will be the sign argument of the copysign:
2509	// (bitcast X) < 0 ? -TC : TC --> copysign(TC, X)
2510	// (bitcast X) < 0 ? TC : -TC --> copysign(TC, -X)
2511	// (bitcast X) >= 0 ? -TC : TC --> copysign(TC, -X)
2512	// (bitcast X) >= 0 ? TC : -TC --> copysign(TC, X)
2513	// Note: FMF from the select can not be propagated to the new instructions.
2514	if (IsTrueIfSignSet ^ TC->isNegative())
2515	X = Builder.CreateFNeg(V: X);
2516
2517	// Canonicalize the magnitude argument as the positive constant since we do
2518	// not care about its sign.
2519	Value *MagArg = ConstantFP::get(Ty: SelType, V: abs(X: *TC));
2520	Function *F = Intrinsic::getDeclaration(M: Sel.getModule(), Intrinsic::id: copysign,
2521	Tys: Sel.getType());
2522	return CallInst::Create(Func: F, Args: { MagArg, X });
2523	}
2524
2525	Instruction *InstCombinerImpl::foldVectorSelect(SelectInst &Sel) {
2526	if (!isa<VectorType>(Val: Sel.getType()))
2527	return nullptr;
2528
2529	Value *Cond = Sel.getCondition();
2530	Value *TVal = Sel.getTrueValue();
2531	Value *FVal = Sel.getFalseValue();
2532	Value *C, *X, *Y;
2533
2534	if (match(V: Cond, P: m_VecReverse(Op0: m_Value(V&: C)))) {
2535	auto createSelReverse = [&](Value *C, Value *X, Value *Y) {
2536	Value *V = Builder.CreateSelect(C, True: X, False: Y, Name: Sel.getName(), MDFrom: &Sel);
2537	if (auto *I = dyn_cast<Instruction>(Val: V))
2538	I->copyIRFlags(V: &Sel);
2539	Module *M = Sel.getModule();
2540	Function *F = Intrinsic::getDeclaration(
2541	M, Intrinsic::id: experimental_vector_reverse, Tys: V->getType());
2542	return CallInst::Create(F, V);
2543	};
2544
2545	if (match(V: TVal, P: m_VecReverse(Op0: m_Value(V&: X)))) {
2546	// select rev(C), rev(X), rev(Y) --> rev(select C, X, Y)
2547	if (match(V: FVal, P: m_VecReverse(Op0: m_Value(V&: Y))) &&
2548	(Cond->hasOneUse() || TVal->hasOneUse() || FVal->hasOneUse()))
2549	return createSelReverse(C, X, Y);
2550
2551	// select rev(C), rev(X), FValSplat --> rev(select C, X, FValSplat)
2552	if ((Cond->hasOneUse() || TVal->hasOneUse()) && isSplatValue(V: FVal))
2553	return createSelReverse(C, X, FVal);
2554	}
2555	// select rev(C), TValSplat, rev(Y) --> rev(select C, TValSplat, Y)
2556	else if (isSplatValue(V: TVal) && match(V: FVal, P: m_VecReverse(Op0: m_Value(V&: Y))) &&
2557	(Cond->hasOneUse() || FVal->hasOneUse()))
2558	return createSelReverse(C, TVal, Y);
2559	}
2560
2561	auto *VecTy = dyn_cast<FixedVectorType>(Val: Sel.getType());
2562	if (!VecTy)
2563	return nullptr;
2564
2565	unsigned NumElts = VecTy->getNumElements();
2566	APInt PoisonElts(NumElts, 0);
2567	APInt AllOnesEltMask(APInt::getAllOnes(numBits: NumElts));
2568	if (Value *V = SimplifyDemandedVectorElts(V: &Sel, DemandedElts: AllOnesEltMask, PoisonElts)) {
2569	if (V != &Sel)
2570	return replaceInstUsesWith(I&: Sel, V);
2571	return &Sel;
2572	}
2573
2574	// A select of a "select shuffle" with a common operand can be rearranged
2575	// to select followed by "select shuffle". Because of poison, this only works
2576	// in the case of a shuffle with no undefined mask elements.
2577	ArrayRef<int> Mask;
2578	if (match(V: TVal, P: m_OneUse(SubPattern: m_Shuffle(v1: m_Value(V&: X), v2: m_Value(V&: Y), mask: m_Mask(Mask)))) &&
2579	!is_contained(Range&: Mask, Element: PoisonMaskElem) &&
2580	cast<ShuffleVectorInst>(Val: TVal)->isSelect()) {
2581	if (X == FVal) {
2582	// select Cond, (shuf_sel X, Y), X --> shuf_sel X, (select Cond, Y, X)
2583	Value *NewSel = Builder.CreateSelect(C: Cond, True: Y, False: X, Name: "sel", MDFrom: &Sel);
2584	return new ShuffleVectorInst(X, NewSel, Mask);
2585	}
2586	if (Y == FVal) {
2587	// select Cond, (shuf_sel X, Y), Y --> shuf_sel (select Cond, X, Y), Y
2588	Value *NewSel = Builder.CreateSelect(C: Cond, True: X, False: Y, Name: "sel", MDFrom: &Sel);
2589	return new ShuffleVectorInst(NewSel, Y, Mask);
2590	}
2591	}
2592	if (match(V: FVal, P: m_OneUse(SubPattern: m_Shuffle(v1: m_Value(V&: X), v2: m_Value(V&: Y), mask: m_Mask(Mask)))) &&
2593	!is_contained(Range&: Mask, Element: PoisonMaskElem) &&
2594	cast<ShuffleVectorInst>(Val: FVal)->isSelect()) {
2595	if (X == TVal) {
2596	// select Cond, X, (shuf_sel X, Y) --> shuf_sel X, (select Cond, X, Y)
2597	Value *NewSel = Builder.CreateSelect(C: Cond, True: X, False: Y, Name: "sel", MDFrom: &Sel);
2598	return new ShuffleVectorInst(X, NewSel, Mask);
2599	}
2600	if (Y == TVal) {
2601	// select Cond, Y, (shuf_sel X, Y) --> shuf_sel (select Cond, Y, X), Y
2602	Value *NewSel = Builder.CreateSelect(C: Cond, True: Y, False: X, Name: "sel", MDFrom: &Sel);
2603	return new ShuffleVectorInst(NewSel, Y, Mask);
2604	}
2605	}
2606
2607	return nullptr;
2608	}
2609
2610	static Instruction *foldSelectToPhiImpl(SelectInst &Sel, BasicBlock *BB,
2611	const DominatorTree &DT,
2612	InstCombiner::BuilderTy &Builder) {
2613	// Find the block's immediate dominator that ends with a conditional branch
2614	// that matches select's condition (maybe inverted).
2615	auto *IDomNode = DT[BB]->getIDom();
2616	if (!IDomNode)
2617	return nullptr;
2618	BasicBlock *IDom = IDomNode->getBlock();
2619
2620	Value *Cond = Sel.getCondition();
2621	Value *IfTrue, *IfFalse;
2622	BasicBlock *TrueSucc, *FalseSucc;
2623	if (match(V: IDom->getTerminator(),
2624	P: m_Br(C: m_Specific(V: Cond), T: m_BasicBlock(V&: TrueSucc),
2625	F: m_BasicBlock(V&: FalseSucc)))) {
2626	IfTrue = Sel.getTrueValue();
2627	IfFalse = Sel.getFalseValue();
2628	} else if (match(V: IDom->getTerminator(),
2629	P: m_Br(C: m_Not(V: m_Specific(V: Cond)), T: m_BasicBlock(V&: TrueSucc),
2630	F: m_BasicBlock(V&: FalseSucc)))) {
2631	IfTrue = Sel.getFalseValue();
2632	IfFalse = Sel.getTrueValue();
2633	} else
2634	return nullptr;
2635
2636	// Make sure the branches are actually different.
2637	if (TrueSucc == FalseSucc)
2638	return nullptr;
2639
2640	// We want to replace select %cond, %a, %b with a phi that takes value %a
2641	// for all incoming edges that are dominated by condition `%cond == true`,
2642	// and value %b for edges dominated by condition `%cond == false`. If %a
2643	// or %b are also phis from the same basic block, we can go further and take
2644	// their incoming values from the corresponding blocks.
2645	BasicBlockEdge TrueEdge(IDom, TrueSucc);
2646	BasicBlockEdge FalseEdge(IDom, FalseSucc);
2647	DenseMap<BasicBlock *, Value *> Inputs;
2648	for (auto *Pred : predecessors(BB)) {
2649	// Check implication.
2650	BasicBlockEdge Incoming(Pred, BB);
2651	if (DT.dominates(BBE1: TrueEdge, BBE2: Incoming))
2652	Inputs[Pred] = IfTrue->DoPHITranslation(CurBB: BB, PredBB: Pred);
2653	else if (DT.dominates(BBE1: FalseEdge, BBE2: Incoming))
2654	Inputs[Pred] = IfFalse->DoPHITranslation(CurBB: BB, PredBB: Pred);
2655	else
2656	return nullptr;
2657	// Check availability.
2658	if (auto *Insn = dyn_cast<Instruction>(Val: Inputs[Pred]))
2659	if (!DT.dominates(Def: Insn, User: Pred->getTerminator()))
2660	return nullptr;
2661	}
2662
2663	Builder.SetInsertPoint(TheBB: BB, IP: BB->begin());
2664	auto *PN = Builder.CreatePHI(Ty: Sel.getType(), NumReservedValues: Inputs.size());
2665	for (auto *Pred : predecessors(BB))
2666	PN->addIncoming(V: Inputs[Pred], BB: Pred);
2667	PN->takeName(V: &Sel);
2668	return PN;
2669	}
2670
2671	static Instruction *foldSelectToPhi(SelectInst &Sel, const DominatorTree &DT,
2672	InstCombiner::BuilderTy &Builder) {
2673	// Try to replace this select with Phi in one of these blocks.
2674	SmallSetVector<BasicBlock *, 4> CandidateBlocks;
2675	CandidateBlocks.insert(X: Sel.getParent());
2676	for (Value *V : Sel.operands())
2677	if (auto *I = dyn_cast<Instruction>(Val: V))
2678	CandidateBlocks.insert(X: I->getParent());
2679
2680	for (BasicBlock *BB : CandidateBlocks)
2681	if (auto *PN = foldSelectToPhiImpl(Sel, BB, DT, Builder))
2682	return PN;
2683	return nullptr;
2684	}
2685
2686	/// Tries to reduce a pattern that arises when calculating the remainder of the
2687	/// Euclidean division. When the divisor is a power of two and is guaranteed not
2688	/// to be negative, a signed remainder can be folded with a bitwise and.
2689	///
2690	/// (x % n) < 0 ? (x % n) + n : (x % n)
2691	/// -> x & (n - 1)
2692	static Instruction *foldSelectWithSRem(SelectInst &SI, InstCombinerImpl &IC,
2693	IRBuilderBase &Builder) {
2694	Value *CondVal = SI.getCondition();
2695	Value *TrueVal = SI.getTrueValue();
2696	Value *FalseVal = SI.getFalseValue();
2697
2698	ICmpInst::Predicate Pred;
2699	Value *Op, *RemRes, *Remainder;
2700	const APInt *C;
2701	bool TrueIfSigned = false;
2702
2703	if (!(match(V: CondVal, P: m_ICmp(Pred, L: m_Value(V&: RemRes), R: m_APInt(Res&: C))) &&
2704	isSignBitCheck(Pred, RHS: *C, TrueIfSigned)))
2705	return nullptr;
2706
2707	// If the sign bit is not set, we have a SGE/SGT comparison, and the operands
2708	// of the select are inverted.
2709	if (!TrueIfSigned)
2710	std::swap(a&: TrueVal, b&: FalseVal);
2711
2712	auto FoldToBitwiseAnd = [&](Value *Remainder) -> Instruction * {
2713	Value *Add = Builder.CreateAdd(
2714	LHS: Remainder, RHS: Constant::getAllOnesValue(Ty: RemRes->getType()));
2715	return BinaryOperator::CreateAnd(V1: Op, V2: Add);
2716	};
2717
2718	// Match the general case:
2719	// %rem = srem i32 %x, %n
2720	// %cnd = icmp slt i32 %rem, 0
2721	// %add = add i32 %rem, %n
2722	// %sel = select i1 %cnd, i32 %add, i32 %rem
2723	if (match(V: TrueVal, P: m_Add(L: m_Specific(V: RemRes), R: m_Value(V&: Remainder))) &&
2724	match(V: RemRes, P: m_SRem(L: m_Value(V&: Op), R: m_Specific(V: Remainder))) &&
2725	IC.isKnownToBeAPowerOfTwo(V: Remainder, /*OrZero*/ true) &&
2726	FalseVal == RemRes)
2727	return FoldToBitwiseAnd(Remainder);
2728
2729	// Match the case where the one arm has been replaced by constant 1:
2730	// %rem = srem i32 %n, 2
2731	// %cnd = icmp slt i32 %rem, 0
2732	// %sel = select i1 %cnd, i32 1, i32 %rem
2733	if (match(V: TrueVal, P: m_One()) &&
2734	match(V: RemRes, P: m_SRem(L: m_Value(V&: Op), R: m_SpecificInt(V: 2))) &&
2735	FalseVal == RemRes)
2736	return FoldToBitwiseAnd(ConstantInt::get(Ty: RemRes->getType(), V: 2));
2737
2738	return nullptr;
2739	}
2740
2741	static Value *foldSelectWithFrozenICmp(SelectInst &Sel, InstCombiner::BuilderTy &Builder) {
2742	FreezeInst *FI = dyn_cast<FreezeInst>(Val: Sel.getCondition());
2743	if (!FI)
2744	return nullptr;
2745
2746	Value *Cond = FI->getOperand(i_nocapture: 0);
2747	Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
2748
2749	// select (freeze(x == y)), x, y --> y
2750	// select (freeze(x != y)), x, y --> x
2751	// The freeze should be only used by this select. Otherwise, remaining uses of
2752	// the freeze can observe a contradictory value.
2753	// c = freeze(x == y) ; Let's assume that y = poison & x = 42; c is 0 or 1
2754	// a = select c, x, y ;
2755	// f(a, c) ; f(poison, 1) cannot happen, but if a is folded
2756	// ; to y, this can happen.
2757	CmpInst::Predicate Pred;
2758	if (FI->hasOneUse() &&
2759	match(V: Cond, P: m_c_ICmp(Pred, L: m_Specific(V: TrueVal), R: m_Specific(V: FalseVal))) &&
2760	(Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)) {
2761	return Pred == ICmpInst::ICMP_EQ ? FalseVal : TrueVal;
2762	}
2763
2764	return nullptr;
2765	}
2766
2767	/// Given that \p CondVal is known to be \p CondIsTrue, try to simplify \p SI.
2768	static Value *simplifyNestedSelectsUsingImpliedCond(SelectInst &SI,
2769	Value *CondVal,
2770	bool CondIsTrue,
2771	const DataLayout &DL) {
2772	Value *InnerCondVal = SI.getCondition();
2773	Value *InnerTrueVal = SI.getTrueValue();
2774	Value *InnerFalseVal = SI.getFalseValue();
2775	assert(CondVal->getType() == InnerCondVal->getType() &&
2776	"The type of inner condition must match with the outer.");
2777	if (auto Implied = isImpliedCondition(LHS: CondVal, RHS: InnerCondVal, DL, LHSIsTrue: CondIsTrue))
2778	return *Implied ? InnerTrueVal : InnerFalseVal;
2779	return nullptr;
2780	}
2781
2782	Instruction *InstCombinerImpl::foldAndOrOfSelectUsingImpliedCond(Value *Op,
2783	SelectInst &SI,
2784	bool IsAnd) {
2785	assert(Op->getType()->isIntOrIntVectorTy(1) &&
2786	"Op must be either i1 or vector of i1.");
2787	if (SI.getCondition()->getType() != Op->getType())
2788	return nullptr;
2789	if (Value *V = simplifyNestedSelectsUsingImpliedCond(SI, CondVal: Op, CondIsTrue: IsAnd, DL))
2790	return SelectInst::Create(C: Op,
2791	S1: IsAnd ? V : ConstantInt::getTrue(Ty: Op->getType()),
2792	S2: IsAnd ? ConstantInt::getFalse(Ty: Op->getType()) : V);
2793	return nullptr;
2794	}
2795
2796	// Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need
2797	// fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work.
2798	static Instruction *foldSelectWithFCmpToFabs(SelectInst &SI,
2799	InstCombinerImpl &IC) {
2800	Value *CondVal = SI.getCondition();
2801
2802	bool ChangedFMF = false;
2803	for (bool Swap : {false, true}) {
2804	Value *TrueVal = SI.getTrueValue();
2805	Value *X = SI.getFalseValue();
2806	CmpInst::Predicate Pred;
2807
2808	if (Swap)
2809	std::swap(a&: TrueVal, b&: X);
2810
2811	if (!match(V: CondVal, P: m_FCmp(Pred, L: m_Specific(V: X), R: m_AnyZeroFP())))
2812	continue;
2813
2814	// fold (X <= +/-0.0) ? (0.0 - X) : X to fabs(X), when 'Swap' is false
2815	// fold (X > +/-0.0) ? X : (0.0 - X) to fabs(X), when 'Swap' is true
2816	if (match(V: TrueVal, P: m_FSub(L: m_PosZeroFP(), R: m_Specific(V: X)))) {
2817	if (!Swap && (Pred == FCmpInst::FCMP_OLE || Pred == FCmpInst::FCMP_ULE)) {
2818	Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::ID: fabs, V: X, FMFSource: &SI);
2819	return IC.replaceInstUsesWith(I&: SI, V: Fabs);
2820	}
2821	if (Swap && (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_UGT)) {
2822	Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::ID: fabs, V: X, FMFSource: &SI);
2823	return IC.replaceInstUsesWith(I&: SI, V: Fabs);
2824	}
2825	}
2826
2827	if (!match(V: TrueVal, P: m_FNeg(X: m_Specific(V: X))))
2828	return nullptr;
2829
2830	// Forward-propagate nnan and ninf from the fneg to the select.
2831	// If all inputs are not those values, then the select is not either.
2832	// Note: nsz is defined differently, so it may not be correct to propagate.
2833	FastMathFlags FMF = cast<FPMathOperator>(Val: TrueVal)->getFastMathFlags();
2834	if (FMF.noNaNs() && !SI.hasNoNaNs()) {
2835	SI.setHasNoNaNs(true);
2836	ChangedFMF = true;
2837	}
2838	if (FMF.noInfs() && !SI.hasNoInfs()) {
2839	SI.setHasNoInfs(true);
2840	ChangedFMF = true;
2841	}
2842
2843	// With nsz, when 'Swap' is false:
2844	// fold (X < +/-0.0) ? -X : X or (X <= +/-0.0) ? -X : X to fabs(X)
2845	// fold (X > +/-0.0) ? -X : X or (X >= +/-0.0) ? -X : X to -fabs(x)
2846	// when 'Swap' is true:
2847	// fold (X > +/-0.0) ? X : -X or (X >= +/-0.0) ? X : -X to fabs(X)
2848	// fold (X < +/-0.0) ? X : -X or (X <= +/-0.0) ? X : -X to -fabs(X)
2849	//
2850	// Note: We require "nnan" for this fold because fcmp ignores the signbit
2851	// of NAN, but IEEE-754 specifies the signbit of NAN values with
2852	// fneg/fabs operations.
2853	if (!SI.hasNoSignedZeros() || !SI.hasNoNaNs())
2854	return nullptr;
2855
2856	if (Swap)
2857	Pred = FCmpInst::getSwappedPredicate(pred: Pred);
2858
2859	bool IsLTOrLE = Pred == FCmpInst::FCMP_OLT || Pred == FCmpInst::FCMP_OLE ||
2860	Pred == FCmpInst::FCMP_ULT || Pred == FCmpInst::FCMP_ULE;
2861	bool IsGTOrGE = Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_OGE ||
2862	Pred == FCmpInst::FCMP_UGT || Pred == FCmpInst::FCMP_UGE;
2863
2864	if (IsLTOrLE) {
2865	Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::ID: fabs, V: X, FMFSource: &SI);
2866	return IC.replaceInstUsesWith(I&: SI, V: Fabs);
2867	}
2868	if (IsGTOrGE) {
2869	Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::ID: fabs, V: X, FMFSource: &SI);
2870	Instruction *NewFNeg = UnaryOperator::CreateFNeg(V: Fabs);
2871	NewFNeg->setFastMathFlags(SI.getFastMathFlags());
2872	return NewFNeg;
2873	}
2874	}
2875
2876	// Match select with (icmp slt (bitcast X to int), 0)
2877	// or (icmp sgt (bitcast X to int), -1)
2878
2879	for (bool Swap : {false, true}) {
2880	Value *TrueVal = SI.getTrueValue();
2881	Value *X = SI.getFalseValue();
2882
2883	if (Swap)
2884	std::swap(a&: TrueVal, b&: X);
2885
2886	CmpInst::Predicate Pred;
2887	const APInt *C;
2888	bool TrueIfSigned;
2889	if (!match(V: CondVal,
2890	P: m_ICmp(Pred, L: m_ElementWiseBitCast(Op: m_Specific(V: X)), R: m_APInt(Res&: C))) ||
2891	!isSignBitCheck(Pred, RHS: *C, TrueIfSigned))
2892	continue;
2893	if (!match(V: TrueVal, P: m_FNeg(X: m_Specific(V: X))))
2894	return nullptr;
2895	if (Swap == TrueIfSigned && !CondVal->hasOneUse() && !TrueVal->hasOneUse())
2896	return nullptr;
2897
2898	// Fold (IsNeg ? -X : X) or (!IsNeg ? X : -X) to fabs(X)
2899	// Fold (IsNeg ? X : -X) or (!IsNeg ? -X : X) to -fabs(X)
2900	Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::ID: fabs, V: X, FMFSource: &SI);
2901	if (Swap != TrueIfSigned)
2902	return IC.replaceInstUsesWith(I&: SI, V: Fabs);
2903	return UnaryOperator::CreateFNegFMF(Op: Fabs, FMFSource: &SI);
2904	}
2905
2906	return ChangedFMF ? &SI : nullptr;
2907	}
2908
2909	// Match the following IR pattern:
2910	// %x.lowbits = and i8 %x, %lowbitmask
2911	// %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 0
2912	// %x.biased = add i8 %x, %bias
2913	// %x.biased.highbits = and i8 %x.biased, %highbitmask
2914	// %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
2915	// Define:
2916	// %alignment = add i8 %lowbitmask, 1
2917	// Iff 1. an %alignment is a power-of-two (aka, %lowbitmask is a low bit mask)
2918	// and 2. %bias is equal to either %lowbitmask or %alignment,
2919	// and 3. %highbitmask is equal to ~%lowbitmask (aka, to -%alignment)
2920	// then this pattern can be transformed into:
2921	// %x.offset = add i8 %x, %lowbitmask
2922	// %x.roundedup = and i8 %x.offset, %highbitmask
2923	static Value *
2924	foldRoundUpIntegerWithPow2Alignment(SelectInst &SI,
2925	InstCombiner::BuilderTy &Builder) {
2926	Value *Cond = SI.getCondition();
2927	Value *X = SI.getTrueValue();
2928	Value *XBiasedHighBits = SI.getFalseValue();
2929
2930	ICmpInst::Predicate Pred;
2931	Value *XLowBits;
2932	if (!match(V: Cond, P: m_ICmp(Pred, L: m_Value(V&: XLowBits), R: m_ZeroInt())) ||
2933	!ICmpInst::isEquality(P: Pred))
2934	return nullptr;
2935
2936	if (Pred == ICmpInst::Predicate::ICMP_NE)
2937	std::swap(a&: X, b&: XBiasedHighBits);
2938
2939	// FIXME: we could support non non-splats here.
2940
2941	const APInt *LowBitMaskCst;
2942	if (!match(V: XLowBits, P: m_And(L: m_Specific(V: X), R: m_APIntAllowPoison(Res&: LowBitMaskCst))))
2943	return nullptr;
2944
2945	// Match even if the AND and ADD are swapped.
2946	const APInt *BiasCst, *HighBitMaskCst;
2947	if (!match(V: XBiasedHighBits,
2948	P: m_And(L: m_Add(L: m_Specific(V: X), R: m_APIntAllowPoison(Res&: BiasCst)),
2949	R: m_APIntAllowPoison(Res&: HighBitMaskCst))) &&
2950	!match(V: XBiasedHighBits,
2951	P: m_Add(L: m_And(L: m_Specific(V: X), R: m_APIntAllowPoison(Res&: HighBitMaskCst)),
2952	R: m_APIntAllowPoison(Res&: BiasCst))))
2953	return nullptr;
2954
2955	if (!LowBitMaskCst->isMask())
2956	return nullptr;
2957
2958	APInt InvertedLowBitMaskCst = ~*LowBitMaskCst;
2959	if (InvertedLowBitMaskCst != *HighBitMaskCst)
2960	return nullptr;
2961
2962	APInt AlignmentCst = *LowBitMaskCst + 1;
2963
2964	if (*BiasCst != AlignmentCst && *BiasCst != *LowBitMaskCst)
2965	return nullptr;
2966
2967	if (!XBiasedHighBits->hasOneUse()) {
2968	// We can't directly return XBiasedHighBits if it is more poisonous.
2969	if (*BiasCst == *LowBitMaskCst && impliesPoison(ValAssumedPoison: XBiasedHighBits, V: X))
2970	return XBiasedHighBits;
2971	return nullptr;
2972	}
2973
2974	// FIXME: could we preserve undef's here?
2975	Type *Ty = X->getType();
2976	Value *XOffset = Builder.CreateAdd(LHS: X, RHS: ConstantInt::get(Ty, V: *LowBitMaskCst),
2977	Name: X->getName() + ".biased");
2978	Value *R = Builder.CreateAnd(LHS: XOffset, RHS: ConstantInt::get(Ty, V: *HighBitMaskCst));
2979	R->takeName(V: &SI);
2980	return R;
2981	}
2982
2983	namespace {
2984	struct DecomposedSelect {
2985	Value *Cond = nullptr;
2986	Value *TrueVal = nullptr;
2987	Value *FalseVal = nullptr;
2988	};
2989	} // namespace
2990
2991	/// Look for patterns like
2992	/// %outer.cond = select i1 %inner.cond, i1 %alt.cond, i1 false
2993	/// %inner.sel = select i1 %inner.cond, i8 %inner.sel.t, i8 %inner.sel.f
2994	/// %outer.sel = select i1 %outer.cond, i8 %outer.sel.t, i8 %inner.sel
2995	/// and rewrite it as
2996	/// %inner.sel = select i1 %cond.alternative, i8 %sel.outer.t, i8 %sel.inner.t
2997	/// %sel.outer = select i1 %cond.inner, i8 %inner.sel, i8 %sel.inner.f
2998	static Instruction *foldNestedSelects(SelectInst &OuterSelVal,
2999	InstCombiner::BuilderTy &Builder) {
3000	// We must start with a `select`.
3001	DecomposedSelect OuterSel;
3002	match(V: &OuterSelVal,
3003	P: m_Select(C: m_Value(V&: OuterSel.Cond), L: m_Value(V&: OuterSel.TrueVal),
3004	R: m_Value(V&: OuterSel.FalseVal)));
3005
3006	// Canonicalize inversion of the outermost `select`'s condition.
3007	if (match(V: OuterSel.Cond, P: m_Not(V: m_Value(V&: OuterSel.Cond))))
3008	std::swap(a&: OuterSel.TrueVal, b&: OuterSel.FalseVal);
3009
3010	// The condition of the outermost select must be an `and`/`or`.
3011	if (!match(V: OuterSel.Cond, P: m_c_LogicalOp(L: m_Value(), R: m_Value())))
3012	return nullptr;
3013
3014	// Depending on the logical op, inner select might be in different hand.
3015	bool IsAndVariant = match(V: OuterSel.Cond, P: m_LogicalAnd());
3016	Value *InnerSelVal = IsAndVariant ? OuterSel.FalseVal : OuterSel.TrueVal;
3017
3018	// Profitability check - avoid increasing instruction count.
3019	if (none_of(Range: ArrayRef<Value *>({OuterSelVal.getCondition(), InnerSelVal}),
3020	P: [](Value *V) { return V->hasOneUse(); }))
3021	return nullptr;
3022
3023	// The appropriate hand of the outermost `select` must be a select itself.
3024	DecomposedSelect InnerSel;
3025	if (!match(V: InnerSelVal,
3026	P: m_Select(C: m_Value(V&: InnerSel.Cond), L: m_Value(V&: InnerSel.TrueVal),
3027	R: m_Value(V&: InnerSel.FalseVal))))
3028	return nullptr;
3029
3030	// Canonicalize inversion of the innermost `select`'s condition.
3031	if (match(V: InnerSel.Cond, P: m_Not(V: m_Value(V&: InnerSel.Cond))))
3032	std::swap(a&: InnerSel.TrueVal, b&: InnerSel.FalseVal);
3033
3034	Value *AltCond = nullptr;
3035	auto matchOuterCond = [OuterSel, IsAndVariant, &AltCond](auto m_InnerCond) {
3036	// An unsimplified select condition can match both LogicalAnd and LogicalOr
3037	// (select true, true, false). Since below we assume that LogicalAnd implies
3038	// InnerSel match the FVal and vice versa for LogicalOr, we can't match the
3039	// alternative pattern here.
3040	return IsAndVariant ? match(OuterSel.Cond,
3041	m_c_LogicalAnd(m_InnerCond, m_Value(V&: AltCond)))
3042	: match(OuterSel.Cond,
3043	m_c_LogicalOr(m_InnerCond, m_Value(V&: AltCond)));
3044	};
3045
3046	// Finally, match the condition that was driving the outermost `select`,
3047	// it should be a logical operation between the condition that was driving
3048	// the innermost `select` (after accounting for the possible inversions
3049	// of the condition), and some other condition.
3050	if (matchOuterCond(m_Specific(V: InnerSel.Cond))) {
3051	// Done!
3052	} else if (Value * NotInnerCond; matchOuterCond(m_CombineAnd(
3053	L: m_Not(V: m_Specific(V: InnerSel.Cond)), R: m_Value(V&: NotInnerCond)))) {
3054	// Done!
3055	std::swap(a&: InnerSel.TrueVal, b&: InnerSel.FalseVal);
3056	InnerSel.Cond = NotInnerCond;
3057	} else // Not the pattern we were looking for.
3058	return nullptr;
3059
3060	Value *SelInner = Builder.CreateSelect(
3061	C: AltCond, True: IsAndVariant ? OuterSel.TrueVal : InnerSel.FalseVal,
3062	False: IsAndVariant ? InnerSel.TrueVal : OuterSel.FalseVal);
3063	SelInner->takeName(V: InnerSelVal);
3064	return SelectInst::Create(C: InnerSel.Cond,
3065	S1: IsAndVariant ? SelInner : InnerSel.TrueVal,
3066	S2: !IsAndVariant ? SelInner : InnerSel.FalseVal);
3067	}
3068
3069	Instruction *InstCombinerImpl::foldSelectOfBools(SelectInst &SI) {
3070	Value *CondVal = SI.getCondition();
3071	Value *TrueVal = SI.getTrueValue();
3072	Value *FalseVal = SI.getFalseValue();
3073	Type *SelType = SI.getType();
3074
3075	// Avoid potential infinite loops by checking for non-constant condition.
3076	// TODO: Can we assert instead by improving canonicalizeSelectToShuffle()?
3077	// Scalar select must have simplified?
3078	if (!SelType->isIntOrIntVectorTy(BitWidth: 1) || isa<Constant>(Val: CondVal) ||
3079	TrueVal->getType() != CondVal->getType())
3080	return nullptr;
3081
3082	auto *One = ConstantInt::getTrue(Ty: SelType);
3083	auto *Zero = ConstantInt::getFalse(Ty: SelType);
3084	Value *A, *B, *C, *D;
3085
3086	// Folding select to and/or i1 isn't poison safe in general. impliesPoison
3087	// checks whether folding it does not convert a well-defined value into
3088	// poison.
3089	if (match(V: TrueVal, P: m_One())) {
3090	if (impliesPoison(ValAssumedPoison: FalseVal, V: CondVal)) {
3091	// Change: A = select B, true, C --> A = or B, C
3092	return BinaryOperator::CreateOr(V1: CondVal, V2: FalseVal);
3093	}
3094
3095	if (match(V: CondVal, P: m_OneUse(SubPattern: m_Select(C: m_Value(V&: A), L: m_One(), R: m_Value(V&: B)))) &&
3096	impliesPoison(ValAssumedPoison: FalseVal, V: B)) {
3097	// (A || B) || C --> A || (B | C)
3098	return replaceInstUsesWith(
3099	I&: SI, V: Builder.CreateLogicalOr(Cond1: A, Cond2: Builder.CreateOr(LHS: B, RHS: FalseVal)));
3100	}
3101
3102	if (auto *LHS = dyn_cast<FCmpInst>(Val: CondVal))
3103	if (auto *RHS = dyn_cast<FCmpInst>(Val: FalseVal))
3104	if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ false,
3105	/*IsSelectLogical*/ IsLogicalSelect: true))
3106	return replaceInstUsesWith(I&: SI, V);
3107
3108	// (A && B) || (C && B) --> (A || C) && B
3109	if (match(V: CondVal, P: m_LogicalAnd(L: m_Value(V&: A), R: m_Value(V&: B))) &&
3110	match(V: FalseVal, P: m_LogicalAnd(L: m_Value(V&: C), R: m_Value(V&: D))) &&
3111	(CondVal->hasOneUse() || FalseVal->hasOneUse())) {
3112	bool CondLogicAnd = isa<SelectInst>(Val: CondVal);
3113	bool FalseLogicAnd = isa<SelectInst>(Val: FalseVal);
3114	auto AndFactorization = [&](Value *Common, Value *InnerCond,
3115	Value *InnerVal,
3116	bool SelFirst = false) -> Instruction * {
3117	Value *InnerSel = Builder.CreateSelect(C: InnerCond, True: One, False: InnerVal);
3118	if (SelFirst)
3119	std::swap(a&: Common, b&: InnerSel);
3120	if (FalseLogicAnd || (CondLogicAnd && Common == A))
3121	return SelectInst::Create(C: Common, S1: InnerSel, S2: Zero);
3122	else
3123	return BinaryOperator::CreateAnd(V1: Common, V2: InnerSel);
3124	};
3125
3126	if (A == C)
3127	return AndFactorization(A, B, D);
3128	if (A == D)
3129	return AndFactorization(A, B, C);
3130	if (B == C)
3131	return AndFactorization(B, A, D);
3132	if (B == D)
3133	return AndFactorization(B, A, C, CondLogicAnd && FalseLogicAnd);
3134	}
3135	}
3136
3137	if (match(V: FalseVal, P: m_Zero())) {
3138	if (impliesPoison(ValAssumedPoison: TrueVal, V: CondVal)) {
3139	// Change: A = select B, C, false --> A = and B, C
3140	return BinaryOperator::CreateAnd(V1: CondVal, V2: TrueVal);
3141	}
3142
3143	if (match(V: CondVal, P: m_OneUse(SubPattern: m_Select(C: m_Value(V&: A), L: m_Value(V&: B), R: m_Zero()))) &&
3144	impliesPoison(ValAssumedPoison: TrueVal, V: B)) {
3145	// (A && B) && C --> A && (B & C)
3146	return replaceInstUsesWith(
3147	I&: SI, V: Builder.CreateLogicalAnd(Cond1: A, Cond2: Builder.CreateAnd(LHS: B, RHS: TrueVal)));
3148	}
3149
3150	if (auto *LHS = dyn_cast<FCmpInst>(Val: CondVal))
3151	if (auto *RHS = dyn_cast<FCmpInst>(Val: TrueVal))
3152	if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ true,
3153	/*IsSelectLogical*/ IsLogicalSelect: true))
3154	return replaceInstUsesWith(I&: SI, V);
3155
3156	// (A || B) && (C || B) --> (A && C) || B
3157	if (match(V: CondVal, P: m_LogicalOr(L: m_Value(V&: A), R: m_Value(V&: B))) &&
3158	match(V: TrueVal, P: m_LogicalOr(L: m_Value(V&: C), R: m_Value(V&: D))) &&
3159	(CondVal->hasOneUse() || TrueVal->hasOneUse())) {
3160	bool CondLogicOr = isa<SelectInst>(Val: CondVal);
3161	bool TrueLogicOr = isa<SelectInst>(Val: TrueVal);
3162	auto OrFactorization = [&](Value *Common, Value *InnerCond,
3163	Value *InnerVal,
3164	bool SelFirst = false) -> Instruction * {
3165	Value *InnerSel = Builder.CreateSelect(C: InnerCond, True: InnerVal, False: Zero);
3166	if (SelFirst)
3167	std::swap(a&: Common, b&: InnerSel);
3168	if (TrueLogicOr || (CondLogicOr && Common == A))
3169	return SelectInst::Create(C: Common, S1: One, S2: InnerSel);
3170	else
3171	return BinaryOperator::CreateOr(V1: Common, V2: InnerSel);
3172	};
3173
3174	if (A == C)
3175	return OrFactorization(A, B, D);
3176	if (A == D)
3177	return OrFactorization(A, B, C);
3178	if (B == C)
3179	return OrFactorization(B, A, D);
3180	if (B == D)
3181	return OrFactorization(B, A, C, CondLogicOr && TrueLogicOr);
3182	}
3183	}
3184
3185	// We match the "full" 0 or 1 constant here to avoid a potential infinite
3186	// loop with vectors that may have undefined/poison elements.
3187	// select a, false, b -> select !a, b, false
3188	if (match(V: TrueVal, P: m_Specific(V: Zero))) {
3189	Value *NotCond = Builder.CreateNot(V: CondVal, Name: "not." + CondVal->getName());
3190	return SelectInst::Create(C: NotCond, S1: FalseVal, S2: Zero);
3191	}
3192	// select a, b, true -> select !a, true, b
3193	if (match(V: FalseVal, P: m_Specific(V: One))) {
3194	Value *NotCond = Builder.CreateNot(V: CondVal, Name: "not." + CondVal->getName());
3195	return SelectInst::Create(C: NotCond, S1: One, S2: TrueVal);
3196	}
3197
3198	// DeMorgan in select form: !a && !b --> !(a || b)
3199	// select !a, !b, false --> not (select a, true, b)
3200	if (match(V: &SI, P: m_LogicalAnd(L: m_Not(V: m_Value(V&: A)), R: m_Not(V: m_Value(V&: B)))) &&
3201	(CondVal->hasOneUse() || TrueVal->hasOneUse()) &&
3202	!match(V: A, P: m_ConstantExpr()) && !match(V: B, P: m_ConstantExpr()))
3203	return BinaryOperator::CreateNot(Op: Builder.CreateSelect(C: A, True: One, False: B));
3204
3205	// DeMorgan in select form: !a || !b --> !(a && b)
3206	// select !a, true, !b --> not (select a, b, false)
3207	if (match(V: &SI, P: m_LogicalOr(L: m_Not(V: m_Value(V&: A)), R: m_Not(V: m_Value(V&: B)))) &&
3208	(CondVal->hasOneUse() || FalseVal->hasOneUse()) &&
3209	!match(V: A, P: m_ConstantExpr()) && !match(V: B, P: m_ConstantExpr()))
3210	return BinaryOperator::CreateNot(Op: Builder.CreateSelect(C: A, True: B, False: Zero));
3211
3212	// select (select a, true, b), true, b -> select a, true, b
3213	if (match(V: CondVal, P: m_Select(C: m_Value(V&: A), L: m_One(), R: m_Value(V&: B))) &&
3214	match(V: TrueVal, P: m_One()) && match(V: FalseVal, P: m_Specific(V: B)))
3215	return replaceOperand(I&: SI, OpNum: 0, V: A);
3216	// select (select a, b, false), b, false -> select a, b, false
3217	if (match(V: CondVal, P: m_Select(C: m_Value(V&: A), L: m_Value(V&: B), R: m_Zero())) &&
3218	match(V: TrueVal, P: m_Specific(V: B)) && match(V: FalseVal, P: m_Zero()))
3219	return replaceOperand(I&: SI, OpNum: 0, V: A);
3220
3221	// ~(A & B) & (A | B) --> A ^ B
3222	if (match(V: &SI, P: m_c_LogicalAnd(L: m_Not(V: m_LogicalAnd(L: m_Value(V&: A), R: m_Value(V&: B))),
3223	R: m_c_LogicalOr(L: m_Deferred(V: A), R: m_Deferred(V: B)))))
3224	return BinaryOperator::CreateXor(V1: A, V2: B);
3225
3226	// select (~a | c), a, b -> select a, (select c, true, b), false
3227	if (match(V: CondVal,
3228	P: m_OneUse(SubPattern: m_c_Or(L: m_Not(V: m_Specific(V: TrueVal)), R: m_Value(V&: C))))) {
3229	Value *OrV = Builder.CreateSelect(C, True: One, False: FalseVal);
3230	return SelectInst::Create(C: TrueVal, S1: OrV, S2: Zero);
3231	}
3232	// select (c & b), a, b -> select b, (select ~c, true, a), false
3233	if (match(V: CondVal, P: m_OneUse(SubPattern: m_c_And(L: m_Value(V&: C), R: m_Specific(V: FalseVal))))) {
3234	if (Value *NotC = getFreelyInverted(V: C, WillInvertAllUses: C->hasOneUse(), Builder: &Builder)) {
3235	Value *OrV = Builder.CreateSelect(C: NotC, True: One, False: TrueVal);
3236	return SelectInst::Create(C: FalseVal, S1: OrV, S2: Zero);
3237	}
3238	}
3239	// select (a | c), a, b -> select a, true, (select ~c, b, false)
3240	if (match(V: CondVal, P: m_OneUse(SubPattern: m_c_Or(L: m_Specific(V: TrueVal), R: m_Value(V&: C))))) {
3241	if (Value *NotC = getFreelyInverted(V: C, WillInvertAllUses: C->hasOneUse(), Builder: &Builder)) {
3242	Value *AndV = Builder.CreateSelect(C: NotC, True: FalseVal, False: Zero);
3243	return SelectInst::Create(C: TrueVal, S1: One, S2: AndV);
3244	}
3245	}
3246	// select (c & ~b), a, b -> select b, true, (select c, a, false)
3247	if (match(V: CondVal,
3248	P: m_OneUse(SubPattern: m_c_And(L: m_Value(V&: C), R: m_Not(V: m_Specific(V: FalseVal)))))) {
3249	Value *AndV = Builder.CreateSelect(C, True: TrueVal, False: Zero);
3250	return SelectInst::Create(C: FalseVal, S1: One, S2: AndV);
3251	}
3252
3253	if (match(V: FalseVal, P: m_Zero()) || match(V: TrueVal, P: m_One())) {
3254	Use *Y = nullptr;
3255	bool IsAnd = match(V: FalseVal, P: m_Zero()) ? true : false;
3256	Value *Op1 = IsAnd ? TrueVal : FalseVal;
3257	if (isCheckForZeroAndMulWithOverflow(Op0: CondVal, Op1, IsAnd, Y)) {
3258	auto *FI = new FreezeInst(*Y, (*Y)->getName() + ".fr");
3259	InsertNewInstBefore(New: FI, Old: cast<Instruction>(Val: Y->getUser())->getIterator());
3260	replaceUse(U&: *Y, NewValue: FI);
3261	return replaceInstUsesWith(I&: SI, V: Op1);
3262	}
3263
3264	if (auto *ICmp0 = dyn_cast<ICmpInst>(Val: CondVal))
3265	if (auto *ICmp1 = dyn_cast<ICmpInst>(Val: Op1))
3266	if (auto *V = foldAndOrOfICmps(LHS: ICmp0, RHS: ICmp1, I&: SI, IsAnd,
3267	/* IsLogical */ true))
3268	return replaceInstUsesWith(I&: SI, V);
3269	}
3270
3271	// select (a || b), c, false -> select a, c, false
3272	// select c, (a || b), false -> select c, a, false
3273	// if c implies that b is false.
3274	if (match(V: CondVal, P: m_LogicalOr(L: m_Value(V&: A), R: m_Value(V&: B))) &&
3275	match(V: FalseVal, P: m_Zero())) {
3276	std::optional<bool> Res = isImpliedCondition(LHS: TrueVal, RHS: B, DL);
3277	if (Res && *Res == false)
3278	return replaceOperand(I&: SI, OpNum: 0, V: A);
3279	}
3280	if (match(V: TrueVal, P: m_LogicalOr(L: m_Value(V&: A), R: m_Value(V&: B))) &&
3281	match(V: FalseVal, P: m_Zero())) {
3282	std::optional<bool> Res = isImpliedCondition(LHS: CondVal, RHS: B, DL);
3283	if (Res && *Res == false)
3284	return replaceOperand(I&: SI, OpNum: 1, V: A);
3285	}
3286	// select c, true, (a && b) -> select c, true, a
3287	// select (a && b), true, c -> select a, true, c
3288	// if c = false implies that b = true
3289	if (match(V: TrueVal, P: m_One()) &&
3290	match(V: FalseVal, P: m_LogicalAnd(L: m_Value(V&: A), R: m_Value(V&: B)))) {
3291	std::optional<bool> Res = isImpliedCondition(LHS: CondVal, RHS: B, DL, LHSIsTrue: false);
3292	if (Res && *Res == true)
3293	return replaceOperand(I&: SI, OpNum: 2, V: A);
3294	}
3295	if (match(V: CondVal, P: m_LogicalAnd(L: m_Value(V&: A), R: m_Value(V&: B))) &&
3296	match(V: TrueVal, P: m_One())) {
3297	std::optional<bool> Res = isImpliedCondition(LHS: FalseVal, RHS: B, DL, LHSIsTrue: false);
3298	if (Res && *Res == true)
3299	return replaceOperand(I&: SI, OpNum: 0, V: A);
3300	}
3301
3302	if (match(V: TrueVal, P: m_One())) {
3303	Value *C;
3304
3305	// (C && A) || (!C && B) --> sel C, A, B
3306	// (A && C) || (!C && B) --> sel C, A, B
3307	// (C && A) || (B && !C) --> sel C, A, B
3308	// (A && C) || (B && !C) --> sel C, A, B (may require freeze)
3309	if (match(V: FalseVal, P: m_c_LogicalAnd(L: m_Not(V: m_Value(V&: C)), R: m_Value(V&: B))) &&
3310	match(V: CondVal, P: m_c_LogicalAnd(L: m_Specific(V: C), R: m_Value(V&: A)))) {
3311	auto *SelCond = dyn_cast<SelectInst>(Val: CondVal);
3312	auto *SelFVal = dyn_cast<SelectInst>(Val: FalseVal);
3313	bool MayNeedFreeze = SelCond && SelFVal &&
3314	match(V: SelFVal->getTrueValue(),
3315	P: m_Not(V: m_Specific(V: SelCond->getTrueValue())));
3316	if (MayNeedFreeze)
3317	C = Builder.CreateFreeze(V: C);
3318	return SelectInst::Create(C, S1: A, S2: B);
3319	}
3320
3321	// (!C && A) || (C && B) --> sel C, B, A
3322	// (A && !C) || (C && B) --> sel C, B, A
3323	// (!C && A) || (B && C) --> sel C, B, A
3324	// (A && !C) || (B && C) --> sel C, B, A (may require freeze)
3325	if (match(V: CondVal, P: m_c_LogicalAnd(L: m_Not(V: m_Value(V&: C)), R: m_Value(V&: A))) &&
3326	match(V: FalseVal, P: m_c_LogicalAnd(L: m_Specific(V: C), R: m_Value(V&: B)))) {
3327	auto *SelCond = dyn_cast<SelectInst>(Val: CondVal);
3328	auto *SelFVal = dyn_cast<SelectInst>(Val: FalseVal);
3329	bool MayNeedFreeze = SelCond && SelFVal &&
3330	match(V: SelCond->getTrueValue(),
3331	P: m_Not(V: m_Specific(V: SelFVal->getTrueValue())));
3332	if (MayNeedFreeze)
3333	C = Builder.CreateFreeze(V: C);
3334	return SelectInst::Create(C, S1: B, S2: A);
3335	}
3336	}
3337
3338	return nullptr;
3339	}
3340
3341	// Return true if we can safely remove the select instruction for std::bit_ceil
3342	// pattern.
3343	static bool isSafeToRemoveBitCeilSelect(ICmpInst::Predicate Pred, Value *Cond0,
3344	const APInt *Cond1, Value *CtlzOp,
3345	unsigned BitWidth) {
3346	// The challenge in recognizing std::bit_ceil(X) is that the operand is used
3347	// for the CTLZ proper and select condition, each possibly with some
3348	// operation like add and sub.
3349	//
3350	// Our aim is to make sure that -ctlz & (BitWidth - 1) == 0 even when the
3351	// select instruction would select 1, which allows us to get rid of the select
3352	// instruction.
3353	//
3354	// To see if we can do so, we do some symbolic execution with ConstantRange.
3355	// Specifically, we compute the range of values that Cond0 could take when
3356	// Cond == false. Then we successively transform the range until we obtain
3357	// the range of values that CtlzOp could take.
3358	//
3359	// Conceptually, we follow the def-use chain backward from Cond0 while
3360	// transforming the range for Cond0 until we meet the common ancestor of Cond0
3361	// and CtlzOp. Then we follow the def-use chain forward until we obtain the
3362	// range for CtlzOp. That said, we only follow at most one ancestor from
3363	// Cond0. Likewise, we only follow at most one ancestor from CtrlOp.
3364
3365	ConstantRange CR = ConstantRange::makeExactICmpRegion(
3366	Pred: CmpInst::getInversePredicate(pred: Pred), Other: *Cond1);
3367
3368	// Match the operation that's used to compute CtlzOp from CommonAncestor. If
3369	// CtlzOp == CommonAncestor, return true as no operation is needed. If a
3370	// match is found, execute the operation on CR, update CR, and return true.
3371	// Otherwise, return false.
3372	auto MatchForward = [&](Value *CommonAncestor) {
3373	const APInt *C = nullptr;
3374	if (CtlzOp == CommonAncestor)
3375	return true;
3376	if (match(V: CtlzOp, P: m_Add(L: m_Specific(V: CommonAncestor), R: m_APInt(Res&: C)))) {
3377	CR = CR.add(Other: *C);
3378	return true;
3379	}
3380	if (match(V: CtlzOp, P: m_Sub(L: m_APInt(Res&: C), R: m_Specific(V: CommonAncestor)))) {
3381	CR = ConstantRange(*C).sub(Other: CR);
3382	return true;
3383	}
3384	if (match(V: CtlzOp, P: m_Not(V: m_Specific(V: CommonAncestor)))) {
3385	CR = CR.binaryNot();
3386	return true;
3387	}
3388	return false;
3389	};
3390
3391	const APInt *C = nullptr;
3392	Value *CommonAncestor;
3393	if (MatchForward(Cond0)) {
3394	// Cond0 is either CtlzOp or CtlzOp's parent. CR has been updated.
3395	} else if (match(V: Cond0, P: m_Add(L: m_Value(V&: CommonAncestor), R: m_APInt(Res&: C)))) {
3396	CR = CR.sub(Other: *C);
3397	if (!MatchForward(CommonAncestor))
3398	return false;
3399	// Cond0's parent is either CtlzOp or CtlzOp's parent. CR has been updated.
3400	} else {
3401	return false;
3402	}
3403
3404	// Return true if all the values in the range are either 0 or negative (if
3405	// treated as signed). We do so by evaluating:
3406	//
3407	// CR - 1 u>= (1 << BitWidth) - 1.
3408	APInt IntMax = APInt::getSignMask(BitWidth) - 1;
3409	CR = CR.sub(Other: APInt(BitWidth, 1));
3410	return CR.icmp(Pred: ICmpInst::ICMP_UGE, Other: IntMax);
3411	}
3412
3413	// Transform the std::bit_ceil(X) pattern like:
3414	//
3415	// %dec = add i32 %x, -1
3416	// %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)
3417	// %sub = sub i32 32, %ctlz
3418	// %shl = shl i32 1, %sub
3419	// %ugt = icmp ugt i32 %x, 1
3420	// %sel = select i1 %ugt, i32 %shl, i32 1
3421	//
3422	// into:
3423	//
3424	// %dec = add i32 %x, -1
3425	// %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)
3426	// %neg = sub i32 0, %ctlz
3427	// %masked = and i32 %ctlz, 31
3428	// %shl = shl i32 1, %sub
3429	//
3430	// Note that the select is optimized away while the shift count is masked with
3431	// 31. We handle some variations of the input operand like std::bit_ceil(X +
3432	// 1).
3433	static Instruction *foldBitCeil(SelectInst &SI, IRBuilderBase &Builder) {
3434	Type *SelType = SI.getType();
3435	unsigned BitWidth = SelType->getScalarSizeInBits();
3436
3437	Value *FalseVal = SI.getFalseValue();
3438	Value *TrueVal = SI.getTrueValue();
3439	ICmpInst::Predicate Pred;
3440	const APInt *Cond1;
3441	Value *Cond0, *Ctlz, *CtlzOp;
3442	if (!match(V: SI.getCondition(), P: m_ICmp(Pred, L: m_Value(V&: Cond0), R: m_APInt(Res&: Cond1))))
3443	return nullptr;
3444
3445	if (match(V: TrueVal, P: m_One())) {
3446	std::swap(a&: FalseVal, b&: TrueVal);
3447	Pred = CmpInst::getInversePredicate(pred: Pred);
3448	}
3449
3450	if (!match(V: FalseVal, P: m_One()) ||
3451	!match(V: TrueVal,
3452	P: m_OneUse(SubPattern: m_Shl(L: m_One(), R: m_OneUse(SubPattern: m_Sub(L: m_SpecificInt(V: BitWidth),
3453	R: m_Value(V&: Ctlz)))))) ||
3454	!match(Ctlz, m_Intrinsic<Intrinsic::ctlz>(m_Value(V&: CtlzOp), m_Zero())) ||
3455	!isSafeToRemoveBitCeilSelect(Pred, Cond0, Cond1, CtlzOp, BitWidth))
3456	return nullptr;
3457
3458	// Build 1 << (-CTLZ & (BitWidth-1)). The negation likely corresponds to a
3459	// single hardware instruction as opposed to BitWidth - CTLZ, where BitWidth
3460	// is an integer constant. Masking with BitWidth-1 comes free on some
3461	// hardware as part of the shift instruction.
3462	Value *Neg = Builder.CreateNeg(V: Ctlz);
3463	Value *Masked =
3464	Builder.CreateAnd(LHS: Neg, RHS: ConstantInt::get(Ty: SelType, V: BitWidth - 1));
3465	return BinaryOperator::Create(Op: Instruction::Shl, S1: ConstantInt::get(Ty: SelType, V: 1),
3466	S2: Masked);
3467	}
3468
3469	bool InstCombinerImpl::fmulByZeroIsZero(Value *MulVal, FastMathFlags FMF,
3470	const Instruction *CtxI) const {
3471	KnownFPClass Known = computeKnownFPClass(Val: MulVal, FMF, Interested: fcNegative, CtxI);
3472
3473	return Known.isKnownNeverNaN() && Known.isKnownNeverInfinity() &&
3474	(FMF.noSignedZeros() || Known.signBitIsZeroOrNaN());
3475	}
3476
3477	static bool matchFMulByZeroIfResultEqZero(InstCombinerImpl &IC, Value *Cmp0,
3478	Value *Cmp1, Value *TrueVal,
3479	Value *FalseVal, Instruction &CtxI,
3480	bool SelectIsNSZ) {
3481	Value *MulRHS;
3482	if (match(V: Cmp1, P: m_PosZeroFP()) &&
3483	match(V: TrueVal, P: m_c_FMul(L: m_Specific(V: Cmp0), R: m_Value(V&: MulRHS)))) {
3484	FastMathFlags FMF = cast<FPMathOperator>(Val: TrueVal)->getFastMathFlags();
3485	// nsz must be on the select, it must be ignored on the multiply. We
3486	// need nnan and ninf on the multiply for the other value.
3487	FMF.setNoSignedZeros(SelectIsNSZ);
3488	return IC.fmulByZeroIsZero(MulVal: MulRHS, FMF, CtxI: &CtxI);
3489	}
3490
3491	return false;
3492	}
3493
3494	Instruction *InstCombinerImpl::visitSelectInst(SelectInst &SI) {
3495	Value *CondVal = SI.getCondition();
3496	Value *TrueVal = SI.getTrueValue();
3497	Value *FalseVal = SI.getFalseValue();
3498	Type *SelType = SI.getType();
3499
3500	if (Value *V = simplifySelectInst(Cond: CondVal, TrueVal, FalseVal,
3501	Q: SQ.getWithInstruction(I: &SI)))
3502	return replaceInstUsesWith(I&: SI, V);
3503
3504	if (Instruction *I = canonicalizeSelectToShuffle(SI))
3505	return I;
3506
3507	if (Instruction *I = canonicalizeScalarSelectOfVecs(Sel&: SI, IC&: *this))
3508	return I;
3509
3510	// If the type of select is not an integer type or if the condition and
3511	// the selection type are not both scalar nor both vector types, there is no
3512	// point in attempting to match these patterns.
3513	Type *CondType = CondVal->getType();
3514	if (!isa<Constant>(Val: CondVal) && SelType->isIntOrIntVectorTy() &&
3515	CondType->isVectorTy() == SelType->isVectorTy()) {
3516	if (Value *S = simplifyWithOpReplaced(V: TrueVal, Op: CondVal,
3517	RepOp: ConstantInt::getTrue(Ty: CondType), Q: SQ,
3518	/* AllowRefinement */ true))
3519	return replaceOperand(I&: SI, OpNum: 1, V: S);
3520
3521	if (Value *S = simplifyWithOpReplaced(V: FalseVal, Op: CondVal,
3522	RepOp: ConstantInt::getFalse(Ty: CondType), Q: SQ,
3523	/* AllowRefinement */ true))
3524	return replaceOperand(I&: SI, OpNum: 2, V: S);
3525	}
3526
3527	if (Instruction *R = foldSelectOfBools(SI))
3528	return R;
3529
3530	// Selecting between two integer or vector splat integer constants?
3531	//
3532	// Note that we don't handle a scalar select of vectors:
3533	// select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>
3534	// because that may need 3 instructions to splat the condition value:
3535	// extend, insertelement, shufflevector.
3536	//
3537	// Do not handle i1 TrueVal and FalseVal otherwise would result in
3538	// zext/sext i1 to i1.
3539	if (SelType->isIntOrIntVectorTy() && !SelType->isIntOrIntVectorTy(BitWidth: 1) &&
3540	CondVal->getType()->isVectorTy() == SelType->isVectorTy()) {
3541	// select C, 1, 0 -> zext C to int
3542	if (match(V: TrueVal, P: m_One()) && match(V: FalseVal, P: m_Zero()))
3543	return new ZExtInst(CondVal, SelType);
3544
3545	// select C, -1, 0 -> sext C to int
3546	if (match(V: TrueVal, P: m_AllOnes()) && match(V: FalseVal, P: m_Zero()))
3547	return new SExtInst(CondVal, SelType);
3548
3549	// select C, 0, 1 -> zext !C to int
3550	if (match(V: TrueVal, P: m_Zero()) && match(V: FalseVal, P: m_One())) {
3551	Value *NotCond = Builder.CreateNot(V: CondVal, Name: "not." + CondVal->getName());
3552	return new ZExtInst(NotCond, SelType);
3553	}
3554
3555	// select C, 0, -1 -> sext !C to int
3556	if (match(V: TrueVal, P: m_Zero()) && match(V: FalseVal, P: m_AllOnes())) {
3557	Value *NotCond = Builder.CreateNot(V: CondVal, Name: "not." + CondVal->getName());
3558	return new SExtInst(NotCond, SelType);
3559	}
3560	}
3561
3562	auto *SIFPOp = dyn_cast<FPMathOperator>(Val: &SI);
3563
3564	if (auto *FCmp = dyn_cast<FCmpInst>(Val: CondVal)) {
3565	FCmpInst::Predicate Pred = FCmp->getPredicate();
3566	Value *Cmp0 = FCmp->getOperand(i_nocapture: 0), *Cmp1 = FCmp->getOperand(i_nocapture: 1);
3567	// Are we selecting a value based on a comparison of the two values?
3568	if ((Cmp0 == TrueVal && Cmp1 == FalseVal) ||
3569	(Cmp0 == FalseVal && Cmp1 == TrueVal)) {
3570	// Canonicalize to use ordered comparisons by swapping the select
3571	// operands.
3572	//
3573	// e.g.
3574	// (X ugt Y) ? X : Y -> (X ole Y) ? Y : X
3575	if (FCmp->hasOneUse() && FCmpInst::isUnordered(predicate: Pred)) {
3576	FCmpInst::Predicate InvPred = FCmp->getInversePredicate();
3577	IRBuilder<>::FastMathFlagGuard FMFG(Builder);
3578	// FIXME: The FMF should propagate from the select, not the fcmp.
3579	Builder.setFastMathFlags(FCmp->getFastMathFlags());
3580	Value *NewCond = Builder.CreateFCmp(P: InvPred, LHS: Cmp0, RHS: Cmp1,
3581	Name: FCmp->getName() + ".inv");
3582	Value *NewSel = Builder.CreateSelect(C: NewCond, True: FalseVal, False: TrueVal);
3583	return replaceInstUsesWith(I&: SI, V: NewSel);
3584	}
3585	}
3586
3587	if (SIFPOp) {
3588	// Fold out scale-if-equals-zero pattern.
3589	//
3590	// This pattern appears in code with denormal range checks after it's
3591	// assumed denormals are treated as zero. This drops a canonicalization.
3592
3593	// TODO: Could relax the signed zero logic. We just need to know the sign
3594	// of the result matches (fmul x, y has the same sign as x).
3595	//
3596	// TODO: Handle always-canonicalizing variant that selects some value or 1
3597	// scaling factor in the fmul visitor.
3598
3599	// TODO: Handle ldexp too
3600
3601	Value *MatchCmp0 = nullptr;
3602	Value *MatchCmp1 = nullptr;
3603
3604	// (select (fcmp [ou]eq x, 0.0), (fmul x, K), x => x
3605	// (select (fcmp [ou]ne x, 0.0), x, (fmul x, K) => x
3606	if (Pred == CmpInst::FCMP_OEQ || Pred == CmpInst::FCMP_UEQ) {
3607	MatchCmp0 = FalseVal;
3608	MatchCmp1 = TrueVal;
3609	} else if (Pred == CmpInst::FCMP_ONE || Pred == CmpInst::FCMP_UNE) {
3610	MatchCmp0 = TrueVal;
3611	MatchCmp1 = FalseVal;
3612	}
3613
3614	if (Cmp0 == MatchCmp0 &&
3615	matchFMulByZeroIfResultEqZero(IC&: *this, Cmp0, Cmp1, TrueVal: MatchCmp1, FalseVal: MatchCmp0,
3616	CtxI&: SI, SelectIsNSZ: SIFPOp->hasNoSignedZeros()))
3617	return replaceInstUsesWith(I&: SI, V: Cmp0);
3618	}
3619	}
3620
3621	if (SIFPOp) {
3622	// TODO: Try to forward-propagate FMF from select arms to the select.
3623
3624	// Canonicalize select of FP values where NaN and -0.0 are not valid as
3625	// minnum/maxnum intrinsics.
3626	if (SIFPOp->hasNoNaNs() && SIFPOp->hasNoSignedZeros()) {
3627	Value *X, *Y;
3628	if (match(V: &SI, P: m_OrdFMax(L: m_Value(V&: X), R: m_Value(V&: Y))))
3629	return replaceInstUsesWith(
3630	I&: SI, V: Builder.CreateBinaryIntrinsic(Intrinsic::ID: maxnum, LHS: X, RHS: Y, FMFSource: &SI));
3631
3632	if (match(V: &SI, P: m_OrdFMin(L: m_Value(V&: X), R: m_Value(V&: Y))))
3633	return replaceInstUsesWith(
3634	I&: SI, V: Builder.CreateBinaryIntrinsic(Intrinsic::ID: minnum, LHS: X, RHS: Y, FMFSource: &SI));
3635	}
3636	}
3637
3638	// Fold selecting to fabs.
3639	if (Instruction *Fabs = foldSelectWithFCmpToFabs(SI, IC&: *this))
3640	return Fabs;
3641
3642	// See if we are selecting two values based on a comparison of the two values.
3643	if (ICmpInst *ICI = dyn_cast<ICmpInst>(Val: CondVal))
3644	if (Instruction *Result = foldSelectInstWithICmp(SI, ICI))
3645	return Result;
3646
3647	if (Instruction *Add = foldAddSubSelect(SI, Builder))
3648	return Add;
3649	if (Instruction *Add = foldOverflowingAddSubSelect(SI, Builder))
3650	return Add;
3651	if (Instruction *Or = foldSetClearBits(Sel&: SI, Builder))
3652	return Or;
3653	if (Instruction *Mul = foldSelectZeroOrMul(SI, IC&: *this))
3654	return Mul;
3655
3656	// Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
3657	auto *TI = dyn_cast<Instruction>(Val: TrueVal);
3658	auto *FI = dyn_cast<Instruction>(Val: FalseVal);
3659	if (TI && FI && TI->getOpcode() == FI->getOpcode())
3660	if (Instruction *IV = foldSelectOpOp(SI, TI, FI))
3661	return IV;
3662
3663	if (Instruction *I = foldSelectExtConst(Sel&: SI))
3664	return I;
3665
3666	if (Instruction *I = foldSelectWithSRem(SI, IC&: *this, Builder))
3667	return I;
3668
3669	// Fold (select C, (gep Ptr, Idx), Ptr) -> (gep Ptr, (select C, Idx, 0))
3670	// Fold (select C, Ptr, (gep Ptr, Idx)) -> (gep Ptr, (select C, 0, Idx))
3671	auto SelectGepWithBase = [&](GetElementPtrInst *Gep, Value *Base,
3672	bool Swap) -> GetElementPtrInst * {
3673	Value *Ptr = Gep->getPointerOperand();
3674	if (Gep->getNumOperands() != 2 || Gep->getPointerOperand() != Base ||
3675	!Gep->hasOneUse())
3676	return nullptr;
3677	Value *Idx = Gep->getOperand(i_nocapture: 1);
3678	if (isa<VectorType>(Val: CondVal->getType()) && !isa<VectorType>(Val: Idx->getType()))
3679	return nullptr;
3680	Type *ElementType = Gep->getResultElementType();
3681	Value *NewT = Idx;
3682	Value *NewF = Constant::getNullValue(Ty: Idx->getType());
3683	if (Swap)
3684	std::swap(a&: NewT, b&: NewF);
3685	Value *NewSI =
3686	Builder.CreateSelect(C: CondVal, True: NewT, False: NewF, Name: SI.getName() + ".idx", MDFrom: &SI);
3687	if (Gep->isInBounds())
3688	return GetElementPtrInst::CreateInBounds(PointeeType: ElementType, Ptr, IdxList: {NewSI});
3689	return GetElementPtrInst::Create(PointeeType: ElementType, Ptr, IdxList: {NewSI});
3690	};
3691	if (auto *TrueGep = dyn_cast<GetElementPtrInst>(Val: TrueVal))
3692	if (auto *NewGep = SelectGepWithBase(TrueGep, FalseVal, false))
3693	return NewGep;
3694	if (auto *FalseGep = dyn_cast<GetElementPtrInst>(Val: FalseVal))
3695	if (auto *NewGep = SelectGepWithBase(FalseGep, TrueVal, true))
3696	return NewGep;
3697
3698	// See if we can fold the select into one of our operands.
3699	if (SelType->isIntOrIntVectorTy() || SelType->isFPOrFPVectorTy()) {
3700	if (Instruction *FoldI = foldSelectIntoOp(SI, TrueVal, FalseVal))
3701	return FoldI;
3702
3703	Value *LHS, *RHS;
3704	Instruction::CastOps CastOp;
3705	SelectPatternResult SPR = matchSelectPattern(V: &SI, LHS, RHS, CastOp: &CastOp);
3706	auto SPF = SPR.Flavor;
3707	if (SPF) {
3708	Value *LHS2, *RHS2;
3709	if (SelectPatternFlavor SPF2 = matchSelectPattern(V: LHS, LHS&: LHS2, RHS&: RHS2).Flavor)
3710	if (Instruction *R = foldSPFofSPF(Inner: cast<Instruction>(Val: LHS), SPF1: SPF2, A: LHS2,
3711	B: RHS2, Outer&: SI, SPF2: SPF, C: RHS))
3712	return R;
3713	if (SelectPatternFlavor SPF2 = matchSelectPattern(V: RHS, LHS&: LHS2, RHS&: RHS2).Flavor)
3714	if (Instruction *R = foldSPFofSPF(Inner: cast<Instruction>(Val: RHS), SPF1: SPF2, A: LHS2,
3715	B: RHS2, Outer&: SI, SPF2: SPF, C: LHS))
3716	return R;
3717	}
3718
3719	if (SelectPatternResult::isMinOrMax(SPF)) {
3720	// Canonicalize so that
3721	// - type casts are outside select patterns.
3722	// - float clamp is transformed to min/max pattern
3723
3724	bool IsCastNeeded = LHS->getType() != SelType;
3725	Value *CmpLHS = cast<CmpInst>(Val: CondVal)->getOperand(i_nocapture: 0);
3726	Value *CmpRHS = cast<CmpInst>(Val: CondVal)->getOperand(i_nocapture: 1);
3727	if (IsCastNeeded ||
3728	(LHS->getType()->isFPOrFPVectorTy() &&
3729	((CmpLHS != LHS && CmpLHS != RHS) ||
3730	(CmpRHS != LHS && CmpRHS != RHS)))) {
3731	CmpInst::Predicate MinMaxPred = getMinMaxPred(SPF, Ordered: SPR.Ordered);
3732
3733	Value *Cmp;
3734	if (CmpInst::isIntPredicate(P: MinMaxPred)) {
3735	Cmp = Builder.CreateICmp(P: MinMaxPred, LHS, RHS);
3736	} else {
3737	IRBuilder<>::FastMathFlagGuard FMFG(Builder);
3738	auto FMF =
3739	cast<FPMathOperator>(Val: SI.getCondition())->getFastMathFlags();
3740	Builder.setFastMathFlags(FMF);
3741	Cmp = Builder.CreateFCmp(P: MinMaxPred, LHS, RHS);
3742	}
3743
3744	Value *NewSI = Builder.CreateSelect(C: Cmp, True: LHS, False: RHS, Name: SI.getName(), MDFrom: &SI);
3745	if (!IsCastNeeded)
3746	return replaceInstUsesWith(I&: SI, V: NewSI);
3747
3748	Value *NewCast = Builder.CreateCast(Op: CastOp, V: NewSI, DestTy: SelType);
3749	return replaceInstUsesWith(I&: SI, V: NewCast);
3750	}
3751	}
3752	}
3753
3754	// See if we can fold the select into a phi node if the condition is a select.
3755	if (auto *PN = dyn_cast<PHINode>(Val: SI.getCondition()))
3756	// The true/false values have to be live in the PHI predecessor's blocks.
3757	if (canSelectOperandBeMappingIntoPredBlock(V: TrueVal, SI) &&
3758	canSelectOperandBeMappingIntoPredBlock(V: FalseVal, SI))
3759	if (Instruction *NV = foldOpIntoPhi(I&: SI, PN))
3760	return NV;
3761
3762	if (SelectInst *TrueSI = dyn_cast<SelectInst>(Val: TrueVal)) {
3763	if (TrueSI->getCondition()->getType() == CondVal->getType()) {
3764	// Fold nested selects if the inner condition can be implied by the outer
3765	// condition.
3766	if (Value *V = simplifyNestedSelectsUsingImpliedCond(
3767	SI&: *TrueSI, CondVal, /*CondIsTrue=*/true, DL))
3768	return replaceOperand(I&: SI, OpNum: 1, V);
3769
3770	// select(C0, select(C1, a, b), b) -> select(C0&C1, a, b)
3771	// We choose this as normal form to enable folding on the And and
3772	// shortening paths for the values (this helps getUnderlyingObjects() for
3773	// example).
3774	if (TrueSI->getFalseValue() == FalseVal && TrueSI->hasOneUse()) {
3775	Value *And = Builder.CreateLogicalAnd(Cond1: CondVal, Cond2: TrueSI->getCondition());
3776	replaceOperand(I&: SI, OpNum: 0, V: And);
3777	replaceOperand(I&: SI, OpNum: 1, V: TrueSI->getTrueValue());
3778	return &SI;
3779	}
3780	}
3781	}
3782	if (SelectInst *FalseSI = dyn_cast<SelectInst>(Val: FalseVal)) {
3783	if (FalseSI->getCondition()->getType() == CondVal->getType()) {
3784	// Fold nested selects if the inner condition can be implied by the outer
3785	// condition.
3786	if (Value *V = simplifyNestedSelectsUsingImpliedCond(
3787	SI&: *FalseSI, CondVal, /*CondIsTrue=*/false, DL))
3788	return replaceOperand(I&: SI, OpNum: 2, V);
3789
3790	// select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b)
3791	if (FalseSI->getTrueValue() == TrueVal && FalseSI->hasOneUse()) {
3792	Value *Or = Builder.CreateLogicalOr(Cond1: CondVal, Cond2: FalseSI->getCondition());
3793	replaceOperand(I&: SI, OpNum: 0, V: Or);
3794	replaceOperand(I&: SI, OpNum: 2, V: FalseSI->getFalseValue());
3795	return &SI;
3796	}
3797	}
3798	}
3799
3800	// Try to simplify a binop sandwiched between 2 selects with the same
3801	// condition. This is not valid for div/rem because the select might be
3802	// preventing a division-by-zero.
3803	// TODO: A div/rem restriction is conservative; use something like
3804	// isSafeToSpeculativelyExecute().
3805	// select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z)
3806	BinaryOperator *TrueBO;
3807	if (match(V: TrueVal, P: m_OneUse(SubPattern: m_BinOp(I&: TrueBO))) && !TrueBO->isIntDivRem()) {
3808	if (auto *TrueBOSI = dyn_cast<SelectInst>(Val: TrueBO->getOperand(i_nocapture: 0))) {
3809	if (TrueBOSI->getCondition() == CondVal) {
3810	replaceOperand(I&: *TrueBO, OpNum: 0, V: TrueBOSI->getTrueValue());
3811	Worklist.push(I: TrueBO);
3812	return &SI;
3813	}
3814	}
3815	if (auto *TrueBOSI = dyn_cast<SelectInst>(Val: TrueBO->getOperand(i_nocapture: 1))) {
3816	if (TrueBOSI->getCondition() == CondVal) {
3817	replaceOperand(I&: *TrueBO, OpNum: 1, V: TrueBOSI->getTrueValue());
3818	Worklist.push(I: TrueBO);
3819	return &SI;
3820	}
3821	}
3822	}
3823
3824	// select(C, Z, binop(select(C, X, Y), W)) -> select(C, Z, binop(Y, W))
3825	BinaryOperator *FalseBO;
3826	if (match(V: FalseVal, P: m_OneUse(SubPattern: m_BinOp(I&: FalseBO))) && !FalseBO->isIntDivRem()) {
3827	if (auto *FalseBOSI = dyn_cast<SelectInst>(Val: FalseBO->getOperand(i_nocapture: 0))) {
3828	if (FalseBOSI->getCondition() == CondVal) {
3829	replaceOperand(I&: *FalseBO, OpNum: 0, V: FalseBOSI->getFalseValue());
3830	Worklist.push(I: FalseBO);
3831	return &SI;
3832	}
3833	}
3834	if (auto *FalseBOSI = dyn_cast<SelectInst>(Val: FalseBO->getOperand(i_nocapture: 1))) {
3835	if (FalseBOSI->getCondition() == CondVal) {
3836	replaceOperand(I&: *FalseBO, OpNum: 1, V: FalseBOSI->getFalseValue());
3837	Worklist.push(I: FalseBO);
3838	return &SI;
3839	}
3840	}
3841	}
3842
3843	Value *NotCond;
3844	if (match(V: CondVal, P: m_Not(V: m_Value(V&: NotCond))) &&
3845	!InstCombiner::shouldAvoidAbsorbingNotIntoSelect(SI)) {
3846	replaceOperand(I&: SI, OpNum: 0, V: NotCond);
3847	SI.swapValues();
3848	SI.swapProfMetadata();
3849	return &SI;
3850	}
3851
3852	if (Instruction *I = foldVectorSelect(Sel&: SI))
3853	return I;
3854
3855	// If we can compute the condition, there's no need for a select.
3856	// Like the above fold, we are attempting to reduce compile-time cost by
3857	// putting this fold here with limitations rather than in InstSimplify.
3858	// The motivation for this call into value tracking is to take advantage of
3859	// the assumption cache, so make sure that is populated.
3860	if (!CondVal->getType()->isVectorTy() && !AC.assumptions().empty()) {
3861	KnownBits Known(1);
3862	computeKnownBits(V: CondVal, Known, Depth: 0, CxtI: &SI);
3863	if (Known.One.isOne())
3864	return replaceInstUsesWith(I&: SI, V: TrueVal);
3865	if (Known.Zero.isOne())
3866	return replaceInstUsesWith(I&: SI, V: FalseVal);
3867	}
3868
3869	if (Instruction *BitCastSel = foldSelectCmpBitcasts(Sel&: SI, Builder))
3870	return BitCastSel;
3871
3872	// Simplify selects that test the returned flag of cmpxchg instructions.
3873	if (Value *V = foldSelectCmpXchg(SI))
3874	return replaceInstUsesWith(I&: SI, V);
3875
3876	if (Instruction *Select = foldSelectBinOpIdentity(Sel&: SI, TLI, IC&: *this))
3877	return Select;
3878
3879	if (Instruction *Funnel = foldSelectFunnelShift(Sel&: SI, Builder))
3880	return Funnel;
3881
3882	if (Instruction *Copysign = foldSelectToCopysign(Sel&: SI, Builder))
3883	return Copysign;
3884
3885	if (Instruction *PN = foldSelectToPhi(Sel&: SI, DT, Builder))
3886	return replaceInstUsesWith(I&: SI, V: PN);
3887
3888	if (Value *Fr = foldSelectWithFrozenICmp(Sel&: SI, Builder))
3889	return replaceInstUsesWith(I&: SI, V: Fr);
3890
3891	if (Value *V = foldRoundUpIntegerWithPow2Alignment(SI, Builder))
3892	return replaceInstUsesWith(I&: SI, V);
3893
3894	// select(mask, mload(,,mask,0), 0) -> mload(,,mask,0)
3895	// Load inst is intentionally not checked for hasOneUse()
3896	if (match(V: FalseVal, P: m_Zero()) &&
3897	(match(V: TrueVal, P: m_MaskedLoad(Op0: m_Value(), Op1: m_Value(), Op2: m_Specific(V: CondVal),
3898	Op3: m_CombineOr(L: m_Undef(), R: m_Zero()))) ||
3899	match(V: TrueVal, P: m_MaskedGather(Op0: m_Value(), Op1: m_Value(), Op2: m_Specific(V: CondVal),
3900	Op3: m_CombineOr(L: m_Undef(), R: m_Zero()))))) {
3901	auto *MaskedInst = cast<IntrinsicInst>(Val: TrueVal);
3902	if (isa<UndefValue>(Val: MaskedInst->getArgOperand(i: 3)))
3903	MaskedInst->setArgOperand(i: 3, v: FalseVal /* Zero */);
3904	return replaceInstUsesWith(I&: SI, V: MaskedInst);
3905	}
3906
3907	Value *Mask;
3908	if (match(V: TrueVal, P: m_Zero()) &&
3909	(match(V: FalseVal, P: m_MaskedLoad(Op0: m_Value(), Op1: m_Value(), Op2: m_Value(V&: Mask),
3910	Op3: m_CombineOr(L: m_Undef(), R: m_Zero()))) ||
3911	match(V: FalseVal, P: m_MaskedGather(Op0: m_Value(), Op1: m_Value(), Op2: m_Value(V&: Mask),
3912	Op3: m_CombineOr(L: m_Undef(), R: m_Zero())))) &&
3913	(CondVal->getType() == Mask->getType())) {
3914	// We can remove the select by ensuring the load zeros all lanes the
3915	// select would have. We determine this by proving there is no overlap
3916	// between the load and select masks.
3917	// (i.e (load_mask & select_mask) == 0 == no overlap)
3918	bool CanMergeSelectIntoLoad = false;
3919	if (Value *V = simplifyAndInst(LHS: CondVal, RHS: Mask, Q: SQ.getWithInstruction(I: &SI)))
3920	CanMergeSelectIntoLoad = match(V, P: m_Zero());
3921
3922	if (CanMergeSelectIntoLoad) {
3923	auto *MaskedInst = cast<IntrinsicInst>(Val: FalseVal);
3924	if (isa<UndefValue>(Val: MaskedInst->getArgOperand(i: 3)))
3925	MaskedInst->setArgOperand(i: 3, v: TrueVal /* Zero */);
3926	return replaceInstUsesWith(I&: SI, V: MaskedInst);
3927	}
3928	}
3929
3930	if (Instruction *I = foldNestedSelects(OuterSelVal&: SI, Builder))
3931	return I;
3932
3933	// Match logical variants of the pattern,
3934	// and transform them iff that gets rid of inversions.
3935	// (~x) | y --> ~(x & (~y))
3936	// (~x) & y --> ~(x | (~y))
3937	if (sinkNotIntoOtherHandOfLogicalOp(I&: SI))
3938	return &SI;
3939
3940	if (Instruction *I = foldBitCeil(SI, Builder))
3941	return I;
3942
3943	// Fold:
3944	// (select A && B, T, F) -> (select A, (select B, T, F), F)
3945	// (select A || B, T, F) -> (select A, T, (select B, T, F))
3946	// if (select B, T, F) is foldable.
3947	// TODO: preserve FMF flags
3948	auto FoldSelectWithAndOrCond = [&](bool IsAnd, Value *A,
3949	Value *B) -> Instruction * {
3950	if (Value *V = simplifySelectInst(Cond: B, TrueVal, FalseVal,
3951	Q: SQ.getWithInstruction(I: &SI)))
3952	return SelectInst::Create(C: A, S1: IsAnd ? V : TrueVal, S2: IsAnd ? FalseVal : V);
3953
3954	// Is (select B, T, F) a SPF?
3955	if (CondVal->hasOneUse() && SelType->isIntOrIntVectorTy()) {
3956	if (ICmpInst *Cmp = dyn_cast<ICmpInst>(Val: B))
3957	if (Value *V = canonicalizeSPF(Cmp&: *Cmp, TrueVal, FalseVal, IC&: *this))
3958	return SelectInst::Create(C: A, S1: IsAnd ? V : TrueVal,
3959	S2: IsAnd ? FalseVal : V);
3960	}
3961
3962	return nullptr;
3963	};
3964
3965	Value *LHS, *RHS;
3966	if (match(V: CondVal, P: m_And(L: m_Value(V&: LHS), R: m_Value(V&: RHS)))) {
3967	if (Instruction *I = FoldSelectWithAndOrCond(/*IsAnd*/ true, LHS, RHS))
3968	return I;
3969	if (Instruction *I = FoldSelectWithAndOrCond(/*IsAnd*/ true, RHS, LHS))
3970	return I;
3971	} else if (match(V: CondVal, P: m_Or(L: m_Value(V&: LHS), R: m_Value(V&: RHS)))) {
3972	if (Instruction *I = FoldSelectWithAndOrCond(/*IsAnd*/ false, LHS, RHS))
3973	return I;
3974	if (Instruction *I = FoldSelectWithAndOrCond(/*IsAnd*/ false, RHS, LHS))
3975	return I;
3976	} else {
3977	// We cannot swap the operands of logical and/or.
3978	// TODO: Can we swap the operands by inserting a freeze?
3979	if (match(V: CondVal, P: m_LogicalAnd(L: m_Value(V&: LHS), R: m_Value(V&: RHS)))) {
3980	if (Instruction *I = FoldSelectWithAndOrCond(/*IsAnd*/ true, LHS, RHS))
3981	return I;
3982	} else if (match(V: CondVal, P: m_LogicalOr(L: m_Value(V&: LHS), R: m_Value(V&: RHS)))) {
3983	if (Instruction *I = FoldSelectWithAndOrCond(/*IsAnd*/ false, LHS, RHS))
3984	return I;
3985	}
3986	}
3987
3988	return nullptr;
3989	}
3990