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