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