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