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