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