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