1 //===- InstCombineSelect.cpp ----------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements the visitSelect function.
11 //===----------------------------------------------------------------------===//
13 #include "InstCombineInternal.h"
14 #include "llvm/ADT/APInt.h"
15 #include "llvm/ADT/Optional.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/Analysis/AssumptionCache.h"
19 #include "llvm/Analysis/CmpInstAnalysis.h"
20 #include "llvm/Analysis/InstructionSimplify.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/Constant.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DerivedTypes.h"
26 #include "llvm/IR/IRBuilder.h"
27 #include "llvm/IR/InstrTypes.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/IntrinsicInst.h"
31 #include "llvm/IR/Intrinsics.h"
32 #include "llvm/IR/Operator.h"
33 #include "llvm/IR/PatternMatch.h"
34 #include "llvm/IR/Type.h"
35 #include "llvm/IR/User.h"
36 #include "llvm/IR/Value.h"
37 #include "llvm/Support/Casting.h"
38 #include "llvm/Support/ErrorHandling.h"
39 #include "llvm/Support/KnownBits.h"
40 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
45 using namespace PatternMatch
;
47 #define DEBUG_TYPE "instcombine"
49 static Value
*createMinMax(InstCombiner::BuilderTy
&Builder
,
50 SelectPatternFlavor SPF
, Value
*A
, Value
*B
) {
51 CmpInst::Predicate Pred
= getMinMaxPred(SPF
);
52 assert(CmpInst::isIntPredicate(Pred
) && "Expected integer predicate");
53 return Builder
.CreateSelect(Builder
.CreateICmp(Pred
, A
, B
), A
, B
);
56 /// Replace a select operand based on an equality comparison with the identity
57 /// constant of a binop.
58 static Instruction
*foldSelectBinOpIdentity(SelectInst
&Sel
,
59 const TargetLibraryInfo
&TLI
) {
60 // The select condition must be an equality compare with a constant operand.
63 CmpInst::Predicate Pred
;
64 if (!match(Sel
.getCondition(), m_Cmp(Pred
, m_Value(X
), m_Constant(C
))))
68 if (ICmpInst::isEquality(Pred
))
69 IsEq
= Pred
== ICmpInst::ICMP_EQ
;
70 else if (Pred
== FCmpInst::FCMP_OEQ
)
72 else if (Pred
== FCmpInst::FCMP_UNE
)
77 // A select operand must be a binop.
79 if (!match(Sel
.getOperand(IsEq
? 1 : 2), m_BinOp(BO
)))
82 // The compare constant must be the identity constant for that binop.
83 // If this a floating-point compare with 0.0, any zero constant will do.
84 Type
*Ty
= BO
->getType();
85 Constant
*IdC
= ConstantExpr::getBinOpIdentity(BO
->getOpcode(), Ty
, true);
87 if (!IdC
|| !CmpInst::isFPPredicate(Pred
))
89 if (!match(IdC
, m_AnyZeroFP()) || !match(C
, m_AnyZeroFP()))
93 // Last, match the compare variable operand with a binop operand.
95 if (!BO
->isCommutative() && !match(BO
, m_BinOp(m_Value(Y
), m_Specific(X
))))
97 if (!match(BO
, m_c_BinOp(m_Value(Y
), m_Specific(X
))))
100 // +0.0 compares equal to -0.0, and so it does not behave as required for this
101 // transform. Bail out if we can not exclude that possibility.
102 if (isa
<FPMathOperator
>(BO
))
103 if (!BO
->hasNoSignedZeros() && !CannotBeNegativeZero(Y
, &TLI
))
107 // S = { select (cmp eq X, C), BO, ? } or { select (cmp ne X, C), ?, BO }
109 // S = { select (cmp eq X, C), Y, ? } or { select (cmp ne X, C), ?, Y }
110 Sel
.setOperand(IsEq
? 1 : 2, Y
);
115 /// select (icmp eq (and X, C1)), TC, FC
116 /// iff C1 is a power 2 and the difference between TC and FC is a power-of-2.
117 /// To something like:
118 /// (shr (and (X, C1)), (log2(C1) - log2(TC-FC))) + FC
120 /// (shl (and (X, C1)), (log2(TC-FC) - log2(C1))) + FC
121 /// With some variations depending if FC is larger than TC, or the shift
122 /// isn't needed, or the bit widths don't match.
123 static Value
*foldSelectICmpAnd(SelectInst
&Sel
, ICmpInst
*Cmp
,
124 InstCombiner::BuilderTy
&Builder
) {
125 const APInt
*SelTC
, *SelFC
;
126 if (!match(Sel
.getTrueValue(), m_APInt(SelTC
)) ||
127 !match(Sel
.getFalseValue(), m_APInt(SelFC
)))
130 // If this is a vector select, we need a vector compare.
131 Type
*SelType
= Sel
.getType();
132 if (SelType
->isVectorTy() != Cmp
->getType()->isVectorTy())
137 bool CreateAnd
= false;
138 ICmpInst::Predicate Pred
= Cmp
->getPredicate();
139 if (ICmpInst::isEquality(Pred
)) {
140 if (!match(Cmp
->getOperand(1), m_Zero()))
143 V
= Cmp
->getOperand(0);
145 if (!match(V
, m_And(m_Value(), m_Power2(AndRHS
))))
149 } else if (decomposeBitTestICmp(Cmp
->getOperand(0), Cmp
->getOperand(1),
151 assert(ICmpInst::isEquality(Pred
) && "Not equality test?");
152 if (!AndMask
.isPowerOf2())
160 // In general, when both constants are non-zero, we would need an offset to
161 // replace the select. This would require more instructions than we started
162 // with. But there's one special-case that we handle here because it can
163 // simplify/reduce the instructions.
166 if (!TC
.isNullValue() && !FC
.isNullValue()) {
167 // If the select constants differ by exactly one bit and that's the same
168 // bit that is masked and checked by the select condition, the select can
169 // be replaced by bitwise logic to set/clear one bit of the constant result.
170 if (TC
.getBitWidth() != AndMask
.getBitWidth() || (TC
^ FC
) != AndMask
)
173 // If we have to create an 'and', then we must kill the cmp to not
174 // increase the instruction count.
175 if (!Cmp
->hasOneUse())
177 V
= Builder
.CreateAnd(V
, ConstantInt::get(SelType
, AndMask
));
179 bool ExtraBitInTC
= TC
.ugt(FC
);
180 if (Pred
== ICmpInst::ICMP_EQ
) {
181 // If the masked bit in V is clear, clear or set the bit in the result:
182 // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) ^ TC
183 // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) | TC
184 Constant
*C
= ConstantInt::get(SelType
, TC
);
185 return ExtraBitInTC
? Builder
.CreateXor(V
, C
) : Builder
.CreateOr(V
, C
);
187 if (Pred
== ICmpInst::ICMP_NE
) {
188 // If the masked bit in V is set, set or clear the bit in the result:
189 // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) | FC
190 // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) ^ FC
191 Constant
*C
= ConstantInt::get(SelType
, FC
);
192 return ExtraBitInTC
? Builder
.CreateOr(V
, C
) : Builder
.CreateXor(V
, C
);
194 llvm_unreachable("Only expecting equality predicates");
197 // Make sure one of the select arms is a power-of-2.
198 if (!TC
.isPowerOf2() && !FC
.isPowerOf2())
201 // Determine which shift is needed to transform result of the 'and' into the
203 const APInt
&ValC
= !TC
.isNullValue() ? TC
: FC
;
204 unsigned ValZeros
= ValC
.logBase2();
205 unsigned AndZeros
= AndMask
.logBase2();
207 // Insert the 'and' instruction on the input to the truncate.
209 V
= Builder
.CreateAnd(V
, ConstantInt::get(V
->getType(), AndMask
));
211 // If types don't match, we can still convert the select by introducing a zext
212 // or a trunc of the 'and'.
213 if (ValZeros
> AndZeros
) {
214 V
= Builder
.CreateZExtOrTrunc(V
, SelType
);
215 V
= Builder
.CreateShl(V
, ValZeros
- AndZeros
);
216 } else if (ValZeros
< AndZeros
) {
217 V
= Builder
.CreateLShr(V
, AndZeros
- ValZeros
);
218 V
= Builder
.CreateZExtOrTrunc(V
, SelType
);
220 V
= Builder
.CreateZExtOrTrunc(V
, SelType
);
223 // Okay, now we know that everything is set up, we just don't know whether we
224 // have a icmp_ne or icmp_eq and whether the true or false val is the zero.
225 bool ShouldNotVal
= !TC
.isNullValue();
226 ShouldNotVal
^= Pred
== ICmpInst::ICMP_NE
;
228 V
= Builder
.CreateXor(V
, ValC
);
233 /// We want to turn code that looks like this:
235 /// %D = select %cond, %C, %A
237 /// %C = select %cond, %B, 0
240 /// Assuming that the specified instruction is an operand to the select, return
241 /// a bitmask indicating which operands of this instruction are foldable if they
242 /// equal the other incoming value of the select.
243 static unsigned getSelectFoldableOperands(BinaryOperator
*I
) {
244 switch (I
->getOpcode()) {
245 case Instruction::Add
:
246 case Instruction::Mul
:
247 case Instruction::And
:
248 case Instruction::Or
:
249 case Instruction::Xor
:
250 return 3; // Can fold through either operand.
251 case Instruction::Sub
: // Can only fold on the amount subtracted.
252 case Instruction::Shl
: // Can only fold on the shift amount.
253 case Instruction::LShr
:
254 case Instruction::AShr
:
257 return 0; // Cannot fold
261 /// For the same transformation as the previous function, return the identity
262 /// constant that goes into the select.
263 static APInt
getSelectFoldableConstant(BinaryOperator
*I
) {
264 switch (I
->getOpcode()) {
265 default: llvm_unreachable("This cannot happen!");
266 case Instruction::Add
:
267 case Instruction::Sub
:
268 case Instruction::Or
:
269 case Instruction::Xor
:
270 case Instruction::Shl
:
271 case Instruction::LShr
:
272 case Instruction::AShr
:
273 return APInt::getNullValue(I
->getType()->getScalarSizeInBits());
274 case Instruction::And
:
275 return APInt::getAllOnesValue(I
->getType()->getScalarSizeInBits());
276 case Instruction::Mul
:
277 return APInt(I
->getType()->getScalarSizeInBits(), 1);
281 /// We have (select c, TI, FI), and we know that TI and FI have the same opcode.
282 Instruction
*InstCombiner::foldSelectOpOp(SelectInst
&SI
, Instruction
*TI
,
284 // Don't break up min/max patterns. The hasOneUse checks below prevent that
285 // for most cases, but vector min/max with bitcasts can be transformed. If the
286 // one-use restrictions are eased for other patterns, we still don't want to
287 // obfuscate min/max.
288 if ((match(&SI
, m_SMin(m_Value(), m_Value())) ||
289 match(&SI
, m_SMax(m_Value(), m_Value())) ||
290 match(&SI
, m_UMin(m_Value(), m_Value())) ||
291 match(&SI
, m_UMax(m_Value(), m_Value()))))
294 // If this is a cast from the same type, merge.
295 Value
*Cond
= SI
.getCondition();
296 Type
*CondTy
= Cond
->getType();
297 if (TI
->getNumOperands() == 1 && TI
->isCast()) {
298 Type
*FIOpndTy
= FI
->getOperand(0)->getType();
299 if (TI
->getOperand(0)->getType() != FIOpndTy
)
302 // The select condition may be a vector. We may only change the operand
303 // type if the vector width remains the same (and matches the condition).
304 if (CondTy
->isVectorTy()) {
305 if (!FIOpndTy
->isVectorTy())
307 if (CondTy
->getVectorNumElements() != FIOpndTy
->getVectorNumElements())
310 // TODO: If the backend knew how to deal with casts better, we could
311 // remove this limitation. For now, there's too much potential to create
312 // worse codegen by promoting the select ahead of size-altering casts
315 // Note that ValueTracking's matchSelectPattern() looks through casts
316 // without checking 'hasOneUse' when it matches min/max patterns, so this
317 // transform may end up happening anyway.
318 if (TI
->getOpcode() != Instruction::BitCast
&&
319 (!TI
->hasOneUse() || !FI
->hasOneUse()))
321 } else if (!TI
->hasOneUse() || !FI
->hasOneUse()) {
322 // TODO: The one-use restrictions for a scalar select could be eased if
323 // the fold of a select in visitLoadInst() was enhanced to match a pattern
324 // that includes a cast.
328 // Fold this by inserting a select from the input values.
330 Builder
.CreateSelect(Cond
, TI
->getOperand(0), FI
->getOperand(0),
331 SI
.getName() + ".v", &SI
);
332 return CastInst::Create(Instruction::CastOps(TI
->getOpcode()), NewSI
,
336 // Cond ? -X : -Y --> -(Cond ? X : Y)
338 if (match(TI
, m_FNeg(m_Value(X
))) && match(FI
, m_FNeg(m_Value(Y
))) &&
339 (TI
->hasOneUse() || FI
->hasOneUse())) {
340 Value
*NewSel
= Builder
.CreateSelect(Cond
, X
, Y
, SI
.getName() + ".v", &SI
);
341 // TODO: Remove the hack for the binop form when the unary op is optimized
342 // properly with all IR passes.
343 if (TI
->getOpcode() != Instruction::FNeg
)
344 return BinaryOperator::CreateFNegFMF(NewSel
, cast
<BinaryOperator
>(TI
));
345 return UnaryOperator::CreateFNeg(NewSel
);
348 // Only handle binary operators (including two-operand getelementptr) with
349 // one-use here. As with the cast case above, it may be possible to relax the
350 // one-use constraint, but that needs be examined carefully since it may not
351 // reduce the total number of instructions.
352 if (TI
->getNumOperands() != 2 || FI
->getNumOperands() != 2 ||
353 (!isa
<BinaryOperator
>(TI
) && !isa
<GetElementPtrInst
>(TI
)) ||
354 !TI
->hasOneUse() || !FI
->hasOneUse())
357 // Figure out if the operations have any operands in common.
358 Value
*MatchOp
, *OtherOpT
, *OtherOpF
;
360 if (TI
->getOperand(0) == FI
->getOperand(0)) {
361 MatchOp
= TI
->getOperand(0);
362 OtherOpT
= TI
->getOperand(1);
363 OtherOpF
= FI
->getOperand(1);
364 MatchIsOpZero
= true;
365 } else if (TI
->getOperand(1) == FI
->getOperand(1)) {
366 MatchOp
= TI
->getOperand(1);
367 OtherOpT
= TI
->getOperand(0);
368 OtherOpF
= FI
->getOperand(0);
369 MatchIsOpZero
= false;
370 } else if (!TI
->isCommutative()) {
372 } else if (TI
->getOperand(0) == FI
->getOperand(1)) {
373 MatchOp
= TI
->getOperand(0);
374 OtherOpT
= TI
->getOperand(1);
375 OtherOpF
= FI
->getOperand(0);
376 MatchIsOpZero
= true;
377 } else if (TI
->getOperand(1) == FI
->getOperand(0)) {
378 MatchOp
= TI
->getOperand(1);
379 OtherOpT
= TI
->getOperand(0);
380 OtherOpF
= FI
->getOperand(1);
381 MatchIsOpZero
= true;
386 // If the select condition is a vector, the operands of the original select's
387 // operands also must be vectors. This may not be the case for getelementptr
389 if (CondTy
->isVectorTy() && (!OtherOpT
->getType()->isVectorTy() ||
390 !OtherOpF
->getType()->isVectorTy()))
393 // If we reach here, they do have operations in common.
394 Value
*NewSI
= Builder
.CreateSelect(Cond
, OtherOpT
, OtherOpF
,
395 SI
.getName() + ".v", &SI
);
396 Value
*Op0
= MatchIsOpZero
? MatchOp
: NewSI
;
397 Value
*Op1
= MatchIsOpZero
? NewSI
: MatchOp
;
398 if (auto *BO
= dyn_cast
<BinaryOperator
>(TI
)) {
399 BinaryOperator
*NewBO
= BinaryOperator::Create(BO
->getOpcode(), Op0
, Op1
);
400 NewBO
->copyIRFlags(TI
);
401 NewBO
->andIRFlags(FI
);
404 if (auto *TGEP
= dyn_cast
<GetElementPtrInst
>(TI
)) {
405 auto *FGEP
= cast
<GetElementPtrInst
>(FI
);
406 Type
*ElementType
= TGEP
->getResultElementType();
407 return TGEP
->isInBounds() && FGEP
->isInBounds()
408 ? GetElementPtrInst::CreateInBounds(ElementType
, Op0
, {Op1
})
409 : GetElementPtrInst::Create(ElementType
, Op0
, {Op1
});
411 llvm_unreachable("Expected BinaryOperator or GEP");
415 static bool isSelect01(const APInt
&C1I
, const APInt
&C2I
) {
416 if (!C1I
.isNullValue() && !C2I
.isNullValue()) // One side must be zero.
418 return C1I
.isOneValue() || C1I
.isAllOnesValue() ||
419 C2I
.isOneValue() || C2I
.isAllOnesValue();
422 /// Try to fold the select into one of the operands to allow further
424 Instruction
*InstCombiner::foldSelectIntoOp(SelectInst
&SI
, Value
*TrueVal
,
426 // See the comment above GetSelectFoldableOperands for a description of the
427 // transformation we are doing here.
428 if (auto *TVI
= dyn_cast
<BinaryOperator
>(TrueVal
)) {
429 if (TVI
->hasOneUse() && !isa
<Constant
>(FalseVal
)) {
430 if (unsigned SFO
= getSelectFoldableOperands(TVI
)) {
431 unsigned OpToFold
= 0;
432 if ((SFO
& 1) && FalseVal
== TVI
->getOperand(0)) {
434 } else if ((SFO
& 2) && FalseVal
== TVI
->getOperand(1)) {
439 APInt CI
= getSelectFoldableConstant(TVI
);
440 Value
*OOp
= TVI
->getOperand(2-OpToFold
);
441 // Avoid creating select between 2 constants unless it's selecting
442 // between 0, 1 and -1.
444 bool OOpIsAPInt
= match(OOp
, m_APInt(OOpC
));
445 if (!isa
<Constant
>(OOp
) || (OOpIsAPInt
&& isSelect01(CI
, *OOpC
))) {
446 Value
*C
= ConstantInt::get(OOp
->getType(), CI
);
447 Value
*NewSel
= Builder
.CreateSelect(SI
.getCondition(), OOp
, C
);
448 NewSel
->takeName(TVI
);
449 BinaryOperator
*BO
= BinaryOperator::Create(TVI
->getOpcode(),
451 BO
->copyIRFlags(TVI
);
459 if (auto *FVI
= dyn_cast
<BinaryOperator
>(FalseVal
)) {
460 if (FVI
->hasOneUse() && !isa
<Constant
>(TrueVal
)) {
461 if (unsigned SFO
= getSelectFoldableOperands(FVI
)) {
462 unsigned OpToFold
= 0;
463 if ((SFO
& 1) && TrueVal
== FVI
->getOperand(0)) {
465 } else if ((SFO
& 2) && TrueVal
== FVI
->getOperand(1)) {
470 APInt CI
= getSelectFoldableConstant(FVI
);
471 Value
*OOp
= FVI
->getOperand(2-OpToFold
);
472 // Avoid creating select between 2 constants unless it's selecting
473 // between 0, 1 and -1.
475 bool OOpIsAPInt
= match(OOp
, m_APInt(OOpC
));
476 if (!isa
<Constant
>(OOp
) || (OOpIsAPInt
&& isSelect01(CI
, *OOpC
))) {
477 Value
*C
= ConstantInt::get(OOp
->getType(), CI
);
478 Value
*NewSel
= Builder
.CreateSelect(SI
.getCondition(), C
, OOp
);
479 NewSel
->takeName(FVI
);
480 BinaryOperator
*BO
= BinaryOperator::Create(FVI
->getOpcode(),
482 BO
->copyIRFlags(FVI
);
494 /// (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1)
496 /// zext (icmp ne i32 (and X, (or Y, (shl 1, Z))), 0)
498 /// Z may be 0 if lshr is missing.
499 /// Worst-case scenario is that we will replace 5 instructions with 5 different
500 /// instructions, but we got rid of select.
501 static Instruction
*foldSelectICmpAndAnd(Type
*SelType
, const ICmpInst
*Cmp
,
502 Value
*TVal
, Value
*FVal
,
503 InstCombiner::BuilderTy
&Builder
) {
504 if (!(Cmp
->hasOneUse() && Cmp
->getOperand(0)->hasOneUse() &&
505 Cmp
->getPredicate() == ICmpInst::ICMP_EQ
&&
506 match(Cmp
->getOperand(1), m_Zero()) && match(FVal
, m_One())))
509 // The TrueVal has general form of: and %B, 1
511 if (!match(TVal
, m_OneUse(m_And(m_Value(B
), m_One()))))
514 // Where %B may be optionally shifted: lshr %X, %Z.
516 const bool HasShift
= match(B
, m_OneUse(m_LShr(m_Value(X
), m_Value(Z
))));
521 if (!match(Cmp
->getOperand(0), m_c_And(m_Specific(X
), m_Value(Y
))))
524 // ((X & Y) == 0) ? ((X >> Z) & 1) : 1 --> (X & (Y | (1 << Z))) != 0
525 // ((X & Y) == 0) ? (X & 1) : 1 --> (X & (Y | 1)) != 0
526 Constant
*One
= ConstantInt::get(SelType
, 1);
527 Value
*MaskB
= HasShift
? Builder
.CreateShl(One
, Z
) : One
;
528 Value
*FullMask
= Builder
.CreateOr(Y
, MaskB
);
529 Value
*MaskedX
= Builder
.CreateAnd(X
, FullMask
);
530 Value
*ICmpNeZero
= Builder
.CreateIsNotNull(MaskedX
);
531 return new ZExtInst(ICmpNeZero
, SelType
);
535 /// (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1
536 /// (select (icmp slt x, C), ashr (X, Y), lshr (X, Y)); iff C s>= 0
539 static Value
*foldSelectICmpLshrAshr(const ICmpInst
*IC
, Value
*TrueVal
,
541 InstCombiner::BuilderTy
&Builder
) {
542 ICmpInst::Predicate Pred
= IC
->getPredicate();
543 Value
*CmpLHS
= IC
->getOperand(0);
544 Value
*CmpRHS
= IC
->getOperand(1);
545 if (!CmpRHS
->getType()->isIntOrIntVectorTy())
549 unsigned Bitwidth
= CmpRHS
->getType()->getScalarSizeInBits();
550 if ((Pred
!= ICmpInst::ICMP_SGT
||
552 m_SpecificInt_ICMP(ICmpInst::ICMP_SGE
, APInt(Bitwidth
, -1)))) &&
553 (Pred
!= ICmpInst::ICMP_SLT
||
555 m_SpecificInt_ICMP(ICmpInst::ICMP_SGE
, APInt(Bitwidth
, 0)))))
558 // Canonicalize so that ashr is in FalseVal.
559 if (Pred
== ICmpInst::ICMP_SLT
)
560 std::swap(TrueVal
, FalseVal
);
562 if (match(TrueVal
, m_LShr(m_Value(X
), m_Value(Y
))) &&
563 match(FalseVal
, m_AShr(m_Specific(X
), m_Specific(Y
))) &&
564 match(CmpLHS
, m_Specific(X
))) {
565 const auto *Ashr
= cast
<Instruction
>(FalseVal
);
566 // if lshr is not exact and ashr is, this new ashr must not be exact.
567 bool IsExact
= Ashr
->isExact() && cast
<Instruction
>(TrueVal
)->isExact();
568 return Builder
.CreateAShr(X
, Y
, IC
->getName(), IsExact
);
575 /// (select (icmp eq (and X, C1), 0), Y, (or Y, C2))
577 /// (or (shl (and X, C1), C3), Y)
579 /// C1 and C2 are both powers of 2
581 /// C3 = Log(C2) - Log(C1)
583 /// This transform handles cases where:
584 /// 1. The icmp predicate is inverted
585 /// 2. The select operands are reversed
586 /// 3. The magnitude of C2 and C1 are flipped
587 static Value
*foldSelectICmpAndOr(const ICmpInst
*IC
, Value
*TrueVal
,
589 InstCombiner::BuilderTy
&Builder
) {
590 // Only handle integer compares. Also, if this is a vector select, we need a
592 if (!TrueVal
->getType()->isIntOrIntVectorTy() ||
593 TrueVal
->getType()->isVectorTy() != IC
->getType()->isVectorTy())
596 Value
*CmpLHS
= IC
->getOperand(0);
597 Value
*CmpRHS
= IC
->getOperand(1);
602 bool NeedAnd
= false;
603 if (IC
->isEquality()) {
604 if (!match(CmpRHS
, m_Zero()))
608 if (!match(CmpLHS
, m_And(m_Value(), m_Power2(C1
))))
612 C1Log
= C1
->logBase2();
613 IsEqualZero
= IC
->getPredicate() == ICmpInst::ICMP_EQ
;
614 } else if (IC
->getPredicate() == ICmpInst::ICMP_SLT
||
615 IC
->getPredicate() == ICmpInst::ICMP_SGT
) {
616 // We also need to recognize (icmp slt (trunc (X)), 0) and
617 // (icmp sgt (trunc (X)), -1).
618 IsEqualZero
= IC
->getPredicate() == ICmpInst::ICMP_SGT
;
619 if ((IsEqualZero
&& !match(CmpRHS
, m_AllOnes())) ||
620 (!IsEqualZero
&& !match(CmpRHS
, m_Zero())))
623 if (!match(CmpLHS
, m_OneUse(m_Trunc(m_Value(V
)))))
626 C1Log
= CmpLHS
->getType()->getScalarSizeInBits() - 1;
633 bool OrOnTrueVal
= false;
634 bool OrOnFalseVal
= match(FalseVal
, m_Or(m_Specific(TrueVal
), m_Power2(C2
)));
636 OrOnTrueVal
= match(TrueVal
, m_Or(m_Specific(FalseVal
), m_Power2(C2
)));
638 if (!OrOnFalseVal
&& !OrOnTrueVal
)
641 Value
*Y
= OrOnFalseVal
? TrueVal
: FalseVal
;
643 unsigned C2Log
= C2
->logBase2();
645 bool NeedXor
= (!IsEqualZero
&& OrOnFalseVal
) || (IsEqualZero
&& OrOnTrueVal
);
646 bool NeedShift
= C1Log
!= C2Log
;
647 bool NeedZExtTrunc
= Y
->getType()->getScalarSizeInBits() !=
648 V
->getType()->getScalarSizeInBits();
650 // Make sure we don't create more instructions than we save.
651 Value
*Or
= OrOnFalseVal
? FalseVal
: TrueVal
;
652 if ((NeedShift
+ NeedXor
+ NeedZExtTrunc
) >
653 (IC
->hasOneUse() + Or
->hasOneUse()))
657 // Insert the AND instruction on the input to the truncate.
658 APInt C1
= APInt::getOneBitSet(V
->getType()->getScalarSizeInBits(), C1Log
);
659 V
= Builder
.CreateAnd(V
, ConstantInt::get(V
->getType(), C1
));
663 V
= Builder
.CreateZExtOrTrunc(V
, Y
->getType());
664 V
= Builder
.CreateShl(V
, C2Log
- C1Log
);
665 } else if (C1Log
> C2Log
) {
666 V
= Builder
.CreateLShr(V
, C1Log
- C2Log
);
667 V
= Builder
.CreateZExtOrTrunc(V
, Y
->getType());
669 V
= Builder
.CreateZExtOrTrunc(V
, Y
->getType());
672 V
= Builder
.CreateXor(V
, *C2
);
674 return Builder
.CreateOr(V
, Y
);
677 /// Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b).
678 /// There are 8 commuted/swapped variants of this pattern.
679 /// TODO: Also support a - UMIN(a,b) patterns.
680 static Value
*canonicalizeSaturatedSubtract(const ICmpInst
*ICI
,
681 const Value
*TrueVal
,
682 const Value
*FalseVal
,
683 InstCombiner::BuilderTy
&Builder
) {
684 ICmpInst::Predicate Pred
= ICI
->getPredicate();
685 if (!ICmpInst::isUnsigned(Pred
))
688 // (b > a) ? 0 : a - b -> (b <= a) ? a - b : 0
689 if (match(TrueVal
, m_Zero())) {
690 Pred
= ICmpInst::getInversePredicate(Pred
);
691 std::swap(TrueVal
, FalseVal
);
693 if (!match(FalseVal
, m_Zero()))
696 Value
*A
= ICI
->getOperand(0);
697 Value
*B
= ICI
->getOperand(1);
698 if (Pred
== ICmpInst::ICMP_ULE
|| Pred
== ICmpInst::ICMP_ULT
) {
699 // (b < a) ? a - b : 0 -> (a > b) ? a - b : 0
701 Pred
= ICmpInst::getSwappedPredicate(Pred
);
704 assert((Pred
== ICmpInst::ICMP_UGE
|| Pred
== ICmpInst::ICMP_UGT
) &&
705 "Unexpected isUnsigned predicate!");
707 // Account for swapped form of subtraction: ((a > b) ? b - a : 0).
708 bool IsNegative
= false;
709 if (match(TrueVal
, m_Sub(m_Specific(B
), m_Specific(A
))))
711 else if (!match(TrueVal
, m_Sub(m_Specific(A
), m_Specific(B
))))
714 // If sub is used anywhere else, we wouldn't be able to eliminate it
716 if (!TrueVal
->hasOneUse())
719 // (a > b) ? a - b : 0 -> usub.sat(a, b)
720 // (a > b) ? b - a : 0 -> -usub.sat(a, b)
721 Value
*Result
= Builder
.CreateBinaryIntrinsic(Intrinsic::usub_sat
, A
, B
);
723 Result
= Builder
.CreateNeg(Result
);
727 static Value
*canonicalizeSaturatedAdd(ICmpInst
*Cmp
, Value
*TVal
, Value
*FVal
,
728 InstCombiner::BuilderTy
&Builder
) {
729 if (!Cmp
->hasOneUse())
732 // Match unsigned saturated add with constant.
733 Value
*Cmp0
= Cmp
->getOperand(0);
734 Value
*Cmp1
= Cmp
->getOperand(1);
735 ICmpInst::Predicate Pred
= Cmp
->getPredicate();
737 const APInt
*C
, *CmpC
;
738 if (Pred
== ICmpInst::ICMP_ULT
&&
739 match(TVal
, m_Add(m_Value(X
), m_APInt(C
))) && X
== Cmp0
&&
740 match(FVal
, m_AllOnes()) && match(Cmp1
, m_APInt(CmpC
)) && *CmpC
== ~*C
) {
741 // (X u< ~C) ? (X + C) : -1 --> uadd.sat(X, C)
742 return Builder
.CreateBinaryIntrinsic(
743 Intrinsic::uadd_sat
, X
, ConstantInt::get(X
->getType(), *C
));
746 // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
747 // There are 8 commuted variants.
748 // Canonicalize -1 (saturated result) to true value of the select. Just
749 // swapping the compare operands is legal, because the selected value is the
750 // same in case of equality, so we can interchange u< and u<=.
751 if (match(FVal
, m_AllOnes())) {
752 std::swap(TVal
, FVal
);
753 std::swap(Cmp0
, Cmp1
);
755 if (!match(TVal
, m_AllOnes()))
758 // Canonicalize predicate to 'ULT'.
759 if (Pred
== ICmpInst::ICMP_UGT
) {
760 Pred
= ICmpInst::ICMP_ULT
;
761 std::swap(Cmp0
, Cmp1
);
763 if (Pred
!= ICmpInst::ICMP_ULT
)
766 // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
768 if (match(Cmp0
, m_Not(m_Value(X
))) &&
769 match(FVal
, m_c_Add(m_Specific(X
), m_Value(Y
))) && Y
== Cmp1
) {
770 // (~X u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
771 // (~X u< Y) ? -1 : (Y + X) --> uadd.sat(X, Y)
772 return Builder
.CreateBinaryIntrinsic(Intrinsic::uadd_sat
, X
, Y
);
774 // The 'not' op may be included in the sum but not the compare.
777 if (match(FVal
, m_c_Add(m_Not(m_Specific(X
)), m_Specific(Y
)))) {
778 // (X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y)
779 // (X u< Y) ? -1 : (Y + ~X) --> uadd.sat(Y, ~X)
780 BinaryOperator
*BO
= cast
<BinaryOperator
>(FVal
);
781 return Builder
.CreateBinaryIntrinsic(
782 Intrinsic::uadd_sat
, BO
->getOperand(0), BO
->getOperand(1));
788 /// Fold the following code sequence:
790 /// int a = ctlz(x & -x);
796 static Instruction
*foldSelectCtlzToCttz(ICmpInst
*ICI
, Value
*TrueVal
,
798 InstCombiner::BuilderTy
&Builder
) {
799 unsigned BitWidth
= TrueVal
->getType()->getScalarSizeInBits();
800 if (!ICI
->isEquality() || !match(ICI
->getOperand(1), m_Zero()))
803 if (ICI
->getPredicate() == ICmpInst::ICMP_NE
)
804 std::swap(TrueVal
, FalseVal
);
807 m_Xor(m_Deferred(TrueVal
), m_SpecificInt(BitWidth
- 1))))
810 if (!match(TrueVal
, m_Intrinsic
<Intrinsic::ctlz
>()))
813 Value
*X
= ICI
->getOperand(0);
814 auto *II
= cast
<IntrinsicInst
>(TrueVal
);
815 if (!match(II
->getOperand(0), m_c_And(m_Specific(X
), m_Neg(m_Specific(X
)))))
818 Function
*F
= Intrinsic::getDeclaration(II
->getModule(), Intrinsic::cttz
,
820 return CallInst::Create(F
, {X
, II
->getArgOperand(1)});
823 /// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single
824 /// call to cttz/ctlz with flag 'is_zero_undef' cleared.
826 /// For example, we can fold the following code sequence:
828 /// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
829 /// %1 = icmp ne i32 %x, 0
830 /// %2 = select i1 %1, i32 %0, i32 32
834 /// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
835 static Value
*foldSelectCttzCtlz(ICmpInst
*ICI
, Value
*TrueVal
, Value
*FalseVal
,
836 InstCombiner::BuilderTy
&Builder
) {
837 ICmpInst::Predicate Pred
= ICI
->getPredicate();
838 Value
*CmpLHS
= ICI
->getOperand(0);
839 Value
*CmpRHS
= ICI
->getOperand(1);
841 // Check if the condition value compares a value for equality against zero.
842 if (!ICI
->isEquality() || !match(CmpRHS
, m_Zero()))
845 Value
*Count
= FalseVal
;
846 Value
*ValueOnZero
= TrueVal
;
847 if (Pred
== ICmpInst::ICMP_NE
)
848 std::swap(Count
, ValueOnZero
);
850 // Skip zero extend/truncate.
852 if (match(Count
, m_ZExt(m_Value(V
))) ||
853 match(Count
, m_Trunc(m_Value(V
))))
856 // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the
857 // input to the cttz/ctlz is used as LHS for the compare instruction.
858 if (!match(Count
, m_Intrinsic
<Intrinsic::cttz
>(m_Specific(CmpLHS
))) &&
859 !match(Count
, m_Intrinsic
<Intrinsic::ctlz
>(m_Specific(CmpLHS
))))
862 IntrinsicInst
*II
= cast
<IntrinsicInst
>(Count
);
864 // Check if the value propagated on zero is a constant number equal to the
865 // sizeof in bits of 'Count'.
866 unsigned SizeOfInBits
= Count
->getType()->getScalarSizeInBits();
867 if (match(ValueOnZero
, m_SpecificInt(SizeOfInBits
))) {
868 // Explicitly clear the 'undef_on_zero' flag.
869 IntrinsicInst
*NewI
= cast
<IntrinsicInst
>(II
->clone());
870 NewI
->setArgOperand(1, ConstantInt::getFalse(NewI
->getContext()));
871 Builder
.Insert(NewI
);
872 return Builder
.CreateZExtOrTrunc(NewI
, ValueOnZero
->getType());
875 // If the ValueOnZero is not the bitwidth, we can at least make use of the
876 // fact that the cttz/ctlz result will not be used if the input is zero, so
877 // it's okay to relax it to undef for that case.
878 if (II
->hasOneUse() && !match(II
->getArgOperand(1), m_One()))
879 II
->setArgOperand(1, ConstantInt::getTrue(II
->getContext()));
884 /// Return true if we find and adjust an icmp+select pattern where the compare
885 /// is with a constant that can be incremented or decremented to match the
886 /// minimum or maximum idiom.
887 static bool adjustMinMax(SelectInst
&Sel
, ICmpInst
&Cmp
) {
888 ICmpInst::Predicate Pred
= Cmp
.getPredicate();
889 Value
*CmpLHS
= Cmp
.getOperand(0);
890 Value
*CmpRHS
= Cmp
.getOperand(1);
891 Value
*TrueVal
= Sel
.getTrueValue();
892 Value
*FalseVal
= Sel
.getFalseValue();
894 // We may move or edit the compare, so make sure the select is the only user.
896 if (!Cmp
.hasOneUse() || !match(CmpRHS
, m_APInt(CmpC
)))
899 // These transforms only work for selects of integers or vector selects of
901 Type
*SelTy
= Sel
.getType();
902 auto *SelEltTy
= dyn_cast
<IntegerType
>(SelTy
->getScalarType());
903 if (!SelEltTy
|| SelTy
->isVectorTy() != Cmp
.getType()->isVectorTy())
906 Constant
*AdjustedRHS
;
907 if (Pred
== ICmpInst::ICMP_UGT
|| Pred
== ICmpInst::ICMP_SGT
)
908 AdjustedRHS
= ConstantInt::get(CmpRHS
->getType(), *CmpC
+ 1);
909 else if (Pred
== ICmpInst::ICMP_ULT
|| Pred
== ICmpInst::ICMP_SLT
)
910 AdjustedRHS
= ConstantInt::get(CmpRHS
->getType(), *CmpC
- 1);
914 // X > C ? X : C+1 --> X < C+1 ? C+1 : X
915 // X < C ? X : C-1 --> X > C-1 ? C-1 : X
916 if ((CmpLHS
== TrueVal
&& AdjustedRHS
== FalseVal
) ||
917 (CmpLHS
== FalseVal
&& AdjustedRHS
== TrueVal
)) {
918 ; // Nothing to do here. Values match without any sign/zero extension.
920 // Types do not match. Instead of calculating this with mixed types, promote
921 // all to the larger type. This enables scalar evolution to analyze this
923 else if (CmpRHS
->getType()->getScalarSizeInBits() < SelEltTy
->getBitWidth()) {
924 Constant
*SextRHS
= ConstantExpr::getSExt(AdjustedRHS
, SelTy
);
926 // X = sext x; x >s c ? X : C+1 --> X = sext x; X <s C+1 ? C+1 : X
927 // X = sext x; x <s c ? X : C-1 --> X = sext x; X >s C-1 ? C-1 : X
928 // X = sext x; x >u c ? X : C+1 --> X = sext x; X <u C+1 ? C+1 : X
929 // X = sext x; x <u c ? X : C-1 --> X = sext x; X >u C-1 ? C-1 : X
930 if (match(TrueVal
, m_SExt(m_Specific(CmpLHS
))) && SextRHS
== FalseVal
) {
932 AdjustedRHS
= SextRHS
;
933 } else if (match(FalseVal
, m_SExt(m_Specific(CmpLHS
))) &&
934 SextRHS
== TrueVal
) {
936 AdjustedRHS
= SextRHS
;
937 } else if (Cmp
.isUnsigned()) {
938 Constant
*ZextRHS
= ConstantExpr::getZExt(AdjustedRHS
, SelTy
);
939 // X = zext x; x >u c ? X : C+1 --> X = zext x; X <u C+1 ? C+1 : X
940 // X = zext x; x <u c ? X : C-1 --> X = zext x; X >u C-1 ? C-1 : X
941 // zext + signed compare cannot be changed:
942 // 0xff <s 0x00, but 0x00ff >s 0x0000
943 if (match(TrueVal
, m_ZExt(m_Specific(CmpLHS
))) && ZextRHS
== FalseVal
) {
945 AdjustedRHS
= ZextRHS
;
946 } else if (match(FalseVal
, m_ZExt(m_Specific(CmpLHS
))) &&
947 ZextRHS
== TrueVal
) {
949 AdjustedRHS
= ZextRHS
;
960 Pred
= ICmpInst::getSwappedPredicate(Pred
);
961 CmpRHS
= AdjustedRHS
;
962 std::swap(FalseVal
, TrueVal
);
963 Cmp
.setPredicate(Pred
);
964 Cmp
.setOperand(0, CmpLHS
);
965 Cmp
.setOperand(1, CmpRHS
);
966 Sel
.setOperand(1, TrueVal
);
967 Sel
.setOperand(2, FalseVal
);
968 Sel
.swapProfMetadata();
970 // Move the compare instruction right before the select instruction. Otherwise
971 // the sext/zext value may be defined after the compare instruction uses it.
972 Cmp
.moveBefore(&Sel
);
977 /// If this is an integer min/max (icmp + select) with a constant operand,
978 /// create the canonical icmp for the min/max operation and canonicalize the
979 /// constant to the 'false' operand of the select:
980 /// select (icmp Pred X, C1), C2, X --> select (icmp Pred' X, C2), X, C2
981 /// Note: if C1 != C2, this will change the icmp constant to the existing
982 /// constant operand of the select.
984 canonicalizeMinMaxWithConstant(SelectInst
&Sel
, ICmpInst
&Cmp
,
985 InstCombiner::BuilderTy
&Builder
) {
986 if (!Cmp
.hasOneUse() || !isa
<Constant
>(Cmp
.getOperand(1)))
989 // Canonicalize the compare predicate based on whether we have min or max.
991 SelectPatternResult SPR
= matchSelectPattern(&Sel
, LHS
, RHS
);
992 if (!SelectPatternResult::isMinOrMax(SPR
.Flavor
))
995 // Is this already canonical?
996 ICmpInst::Predicate CanonicalPred
= getMinMaxPred(SPR
.Flavor
);
997 if (Cmp
.getOperand(0) == LHS
&& Cmp
.getOperand(1) == RHS
&&
998 Cmp
.getPredicate() == CanonicalPred
)
1001 // Create the canonical compare and plug it into the select.
1002 Sel
.setCondition(Builder
.CreateICmp(CanonicalPred
, LHS
, RHS
));
1004 // If the select operands did not change, we're done.
1005 if (Sel
.getTrueValue() == LHS
&& Sel
.getFalseValue() == RHS
)
1008 // If we are swapping the select operands, swap the metadata too.
1009 assert(Sel
.getTrueValue() == RHS
&& Sel
.getFalseValue() == LHS
&&
1010 "Unexpected results from matchSelectPattern");
1012 Sel
.swapProfMetadata();
1016 /// There are many select variants for each of ABS/NABS.
1017 /// In matchSelectPattern(), there are different compare constants, compare
1018 /// predicates/operands and select operands.
1019 /// In isKnownNegation(), there are different formats of negated operands.
1020 /// Canonicalize all these variants to 1 pattern.
1021 /// This makes CSE more likely.
1022 static Instruction
*canonicalizeAbsNabs(SelectInst
&Sel
, ICmpInst
&Cmp
,
1023 InstCombiner::BuilderTy
&Builder
) {
1024 if (!Cmp
.hasOneUse() || !isa
<Constant
>(Cmp
.getOperand(1)))
1027 // Choose a sign-bit check for the compare (likely simpler for codegen).
1028 // ABS: (X <s 0) ? -X : X
1029 // NABS: (X <s 0) ? X : -X
1031 SelectPatternFlavor SPF
= matchSelectPattern(&Sel
, LHS
, RHS
).Flavor
;
1032 if (SPF
!= SelectPatternFlavor::SPF_ABS
&&
1033 SPF
!= SelectPatternFlavor::SPF_NABS
)
1036 Value
*TVal
= Sel
.getTrueValue();
1037 Value
*FVal
= Sel
.getFalseValue();
1038 assert(isKnownNegation(TVal
, FVal
) &&
1039 "Unexpected result from matchSelectPattern");
1041 // The compare may use the negated abs()/nabs() operand, or it may use
1042 // negation in non-canonical form such as: sub A, B.
1043 bool CmpUsesNegatedOp
= match(Cmp
.getOperand(0), m_Neg(m_Specific(TVal
))) ||
1044 match(Cmp
.getOperand(0), m_Neg(m_Specific(FVal
)));
1046 bool CmpCanonicalized
= !CmpUsesNegatedOp
&&
1047 match(Cmp
.getOperand(1), m_ZeroInt()) &&
1048 Cmp
.getPredicate() == ICmpInst::ICMP_SLT
;
1049 bool RHSCanonicalized
= match(RHS
, m_Neg(m_Specific(LHS
)));
1051 // Is this already canonical?
1052 if (CmpCanonicalized
&& RHSCanonicalized
)
1055 // If RHS is used by other instructions except compare and select, don't
1056 // canonicalize it to not increase the instruction count.
1057 if (!(RHS
->hasOneUse() || (RHS
->hasNUses(2) && CmpUsesNegatedOp
)))
1060 // Create the canonical compare: icmp slt LHS 0.
1061 if (!CmpCanonicalized
) {
1062 Cmp
.setPredicate(ICmpInst::ICMP_SLT
);
1063 Cmp
.setOperand(1, ConstantInt::getNullValue(Cmp
.getOperand(0)->getType()));
1064 if (CmpUsesNegatedOp
)
1065 Cmp
.setOperand(0, LHS
);
1068 // Create the canonical RHS: RHS = sub (0, LHS).
1069 if (!RHSCanonicalized
) {
1070 assert(RHS
->hasOneUse() && "RHS use number is not right");
1071 RHS
= Builder
.CreateNeg(LHS
);
1073 Sel
.setFalseValue(RHS
);
1076 Sel
.setTrueValue(RHS
);
1081 // If the select operands do not change, we're done.
1082 if (SPF
== SelectPatternFlavor::SPF_NABS
) {
1085 assert(FVal
== LHS
&& "Unexpected results from matchSelectPattern");
1089 assert(TVal
== LHS
&& "Unexpected results from matchSelectPattern");
1092 // We are swapping the select operands, so swap the metadata too.
1094 Sel
.swapProfMetadata();
1098 static Value
*simplifyWithOpReplaced(Value
*V
, Value
*Op
, Value
*ReplaceOp
,
1099 const SimplifyQuery
&Q
) {
1100 // If this is a binary operator, try to simplify it with the replaced op
1101 // because we know Op and ReplaceOp are equivalant.
1102 // For example: V = X + 1, Op = X, ReplaceOp = 42
1103 // Simplifies as: add(42, 1) --> 43
1104 if (auto *BO
= dyn_cast
<BinaryOperator
>(V
)) {
1105 if (BO
->getOperand(0) == Op
)
1106 return SimplifyBinOp(BO
->getOpcode(), ReplaceOp
, BO
->getOperand(1), Q
);
1107 if (BO
->getOperand(1) == Op
)
1108 return SimplifyBinOp(BO
->getOpcode(), BO
->getOperand(0), ReplaceOp
, Q
);
1114 /// If we have a select with an equality comparison, then we know the value in
1115 /// one of the arms of the select. See if substituting this value into an arm
1116 /// and simplifying the result yields the same value as the other arm.
1118 /// To make this transform safe, we must drop poison-generating flags
1119 /// (nsw, etc) if we simplified to a binop because the select may be guarding
1120 /// that poison from propagating. If the existing binop already had no
1121 /// poison-generating flags, then this transform can be done by instsimplify.
1124 /// %cmp = icmp eq i32 %x, 2147483647
1125 /// %add = add nsw i32 %x, 1
1126 /// %sel = select i1 %cmp, i32 -2147483648, i32 %add
1128 /// We can't replace %sel with %add unless we strip away the flags.
1129 /// TODO: Wrapping flags could be preserved in some cases with better analysis.
1130 static Value
*foldSelectValueEquivalence(SelectInst
&Sel
, ICmpInst
&Cmp
,
1131 const SimplifyQuery
&Q
) {
1132 if (!Cmp
.isEquality())
1135 // Canonicalize the pattern to ICMP_EQ by swapping the select operands.
1136 Value
*TrueVal
= Sel
.getTrueValue(), *FalseVal
= Sel
.getFalseValue();
1137 if (Cmp
.getPredicate() == ICmpInst::ICMP_NE
)
1138 std::swap(TrueVal
, FalseVal
);
1140 // Try each equivalence substitution possibility.
1141 // We have an 'EQ' comparison, so the select's false value will propagate.
1143 // (X == 42) ? 43 : (X + 1) --> (X == 42) ? (X + 1) : (X + 1) --> X + 1
1144 // (X == 42) ? (X + 1) : 43 --> (X == 42) ? (42 + 1) : 43 --> 43
1145 Value
*CmpLHS
= Cmp
.getOperand(0), *CmpRHS
= Cmp
.getOperand(1);
1146 if (simplifyWithOpReplaced(FalseVal
, CmpLHS
, CmpRHS
, Q
) == TrueVal
||
1147 simplifyWithOpReplaced(FalseVal
, CmpRHS
, CmpLHS
, Q
) == TrueVal
||
1148 simplifyWithOpReplaced(TrueVal
, CmpLHS
, CmpRHS
, Q
) == FalseVal
||
1149 simplifyWithOpReplaced(TrueVal
, CmpRHS
, CmpLHS
, Q
) == FalseVal
) {
1150 if (auto *FalseInst
= dyn_cast
<Instruction
>(FalseVal
))
1151 FalseInst
->dropPoisonGeneratingFlags();
1157 // See if this is a pattern like:
1158 // %old_cmp1 = icmp slt i32 %x, C2
1159 // %old_replacement = select i1 %old_cmp1, i32 %target_low, i32 %target_high
1160 // %old_x_offseted = add i32 %x, C1
1161 // %old_cmp0 = icmp ult i32 %old_x_offseted, C0
1162 // %r = select i1 %old_cmp0, i32 %x, i32 %old_replacement
1163 // This can be rewritten as more canonical pattern:
1164 // %new_cmp1 = icmp slt i32 %x, -C1
1165 // %new_cmp2 = icmp sge i32 %x, C0-C1
1166 // %new_clamped_low = select i1 %new_cmp1, i32 %target_low, i32 %x
1167 // %r = select i1 %new_cmp2, i32 %target_high, i32 %new_clamped_low
1168 // Iff -C1 s<= C2 s<= C0-C1
1169 // Also ULT predicate can also be UGT iff C0 != -1 (+invert result)
1170 // SLT predicate can also be SGT iff C2 != INT_MAX (+invert res.)
1171 static Instruction
*canonicalizeClampLike(SelectInst
&Sel0
, ICmpInst
&Cmp0
,
1172 InstCombiner::BuilderTy
&Builder
) {
1173 Value
*X
= Sel0
.getTrueValue();
1174 Value
*Sel1
= Sel0
.getFalseValue();
1176 // First match the condition of the outermost select.
1177 // Said condition must be one-use.
1178 if (!Cmp0
.hasOneUse())
1180 Value
*Cmp00
= Cmp0
.getOperand(0);
1182 if (!match(Cmp0
.getOperand(1),
1183 m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C0
))))
1185 // Canonicalize Cmp0 into the form we expect.
1186 // FIXME: we shouldn't care about lanes that are 'undef' in the end?
1187 switch (Cmp0
.getPredicate()) {
1188 case ICmpInst::Predicate::ICMP_ULT
:
1190 case ICmpInst::Predicate::ICMP_ULE
:
1191 // We'd have to increment C0 by one, and for that it must not have all-ones
1192 // element, but then it would have been canonicalized to 'ult' before
1193 // we get here. So we can't do anything useful with 'ule'.
1195 case ICmpInst::Predicate::ICMP_UGT
:
1196 // We want to canonicalize it to 'ult', so we'll need to increment C0,
1197 // which again means it must not have any all-ones elements.
1199 m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE
,
1200 APInt::getAllOnesValue(
1201 C0
->getType()->getScalarSizeInBits()))))
1202 return nullptr; // Can't do, have all-ones element[s].
1206 case ICmpInst::Predicate::ICMP_UGE
:
1207 // The only way we'd get this predicate if this `icmp` has extra uses,
1208 // but then we won't be able to do this fold.
1211 return nullptr; // Unknown predicate.
1214 // Now that we've canonicalized the ICmp, we know the X we expect;
1215 // the select in other hand should be one-use.
1216 if (!Sel1
->hasOneUse())
1219 // We now can finish matching the condition of the outermost select:
1220 // it should either be the X itself, or an addition of some constant to X.
1223 C1
= ConstantInt::getNullValue(Sel0
.getType());
1224 else if (!match(Cmp00
,
1225 m_Add(m_Specific(X
),
1226 m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C1
)))))
1230 ICmpInst::Predicate Pred1
;
1232 Value
*ReplacementLow
, *ReplacementHigh
;
1233 if (!match(Sel1
, m_Select(m_Value(Cmp1
), m_Value(ReplacementLow
),
1234 m_Value(ReplacementHigh
))) ||
1236 m_ICmp(Pred1
, m_Specific(X
),
1237 m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C2
)))))
1240 if (!Cmp1
->hasOneUse() && (Cmp00
== X
|| !Cmp00
->hasOneUse()))
1241 return nullptr; // Not enough one-use instructions for the fold.
1242 // FIXME: this restriction could be relaxed if Cmp1 can be reused as one of
1243 // two comparisons we'll need to build.
1245 // Canonicalize Cmp1 into the form we expect.
1246 // FIXME: we shouldn't care about lanes that are 'undef' in the end?
1248 case ICmpInst::Predicate::ICMP_SLT
:
1250 case ICmpInst::Predicate::ICMP_SLE
:
1251 // We'd have to increment C2 by one, and for that it must not have signed
1252 // max element, but then it would have been canonicalized to 'slt' before
1253 // we get here. So we can't do anything useful with 'sle'.
1255 case ICmpInst::Predicate::ICMP_SGT
:
1256 // We want to canonicalize it to 'slt', so we'll need to increment C2,
1257 // which again means it must not have any signed max elements.
1259 m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE
,
1260 APInt::getSignedMaxValue(
1261 C2
->getType()->getScalarSizeInBits()))))
1262 return nullptr; // Can't do, have signed max element[s].
1265 case ICmpInst::Predicate::ICMP_SGE
:
1266 // Also non-canonical, but here we don't need to change C2,
1267 // so we don't have any restrictions on C2, so we can just handle it.
1268 std::swap(ReplacementLow
, ReplacementHigh
);
1271 return nullptr; // Unknown predicate.
1274 // The thresholds of this clamp-like pattern.
1275 auto *ThresholdLowIncl
= ConstantExpr::getNeg(C1
);
1276 auto *ThresholdHighExcl
= ConstantExpr::getSub(C0
, C1
);
1278 // The fold has a precondition 1: C2 s>= ThresholdLow
1279 auto *Precond1
= ConstantExpr::getICmp(ICmpInst::Predicate::ICMP_SGE
, C2
,
1281 if (!match(Precond1
, m_One()))
1283 // The fold has a precondition 2: C2 s<= ThresholdHigh
1284 auto *Precond2
= ConstantExpr::getICmp(ICmpInst::Predicate::ICMP_SLE
, C2
,
1286 if (!match(Precond2
, m_One()))
1289 // All good, finally emit the new pattern.
1290 Value
*ShouldReplaceLow
= Builder
.CreateICmpSLT(X
, ThresholdLowIncl
);
1291 Value
*ShouldReplaceHigh
= Builder
.CreateICmpSGE(X
, ThresholdHighExcl
);
1292 Value
*MaybeReplacedLow
=
1293 Builder
.CreateSelect(ShouldReplaceLow
, ReplacementLow
, X
);
1294 Instruction
*MaybeReplacedHigh
=
1295 SelectInst::Create(ShouldReplaceHigh
, ReplacementHigh
, MaybeReplacedLow
);
1297 return MaybeReplacedHigh
;
1301 // %cmp = icmp [canonical predicate] i32 %x, C0
1302 // %r = select i1 %cmp, i32 %y, i32 C1
1303 // Where C0 != C1 and %x may be different from %y, see if the constant that we
1304 // will have if we flip the strictness of the predicate (i.e. without changing
1305 // the result) is identical to the C1 in select. If it matches we can change
1306 // original comparison to one with swapped predicate, reuse the constant,
1307 // and swap the hands of select.
1308 static Instruction
*
1309 tryToReuseConstantFromSelectInComparison(SelectInst
&Sel
, ICmpInst
&Cmp
,
1310 InstCombiner::BuilderTy
&Builder
) {
1311 ICmpInst::Predicate Pred
;
1314 if (!match(&Cmp
, m_OneUse(m_ICmp(
1316 m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C0
))))))
1319 // If comparison predicate is non-relational, we won't be able to do anything.
1320 if (ICmpInst::isEquality(Pred
))
1323 // If comparison predicate is non-canonical, then we certainly won't be able
1324 // to make it canonical; canonicalizeCmpWithConstant() already tried.
1325 if (!isCanonicalPredicate(Pred
))
1328 // If the [input] type of comparison and select type are different, lets abort
1329 // for now. We could try to compare constants with trunc/[zs]ext though.
1330 if (C0
->getType() != Sel
.getType())
1333 // FIXME: are there any magic icmp predicate+constant pairs we must not touch?
1335 Value
*SelVal0
, *SelVal1
; // We do not care which one is from where.
1336 match(&Sel
, m_Select(m_Value(), m_Value(SelVal0
), m_Value(SelVal1
)));
1337 // At least one of these values we are selecting between must be a constant
1338 // else we'll never succeed.
1339 if (!match(SelVal0
, m_AnyIntegralConstant()) &&
1340 !match(SelVal1
, m_AnyIntegralConstant()))
1343 // Does this constant C match any of the `select` values?
1344 auto MatchesSelectValue
= [SelVal0
, SelVal1
](Constant
*C
) {
1345 return C
->isElementWiseEqual(SelVal0
) || C
->isElementWiseEqual(SelVal1
);
1348 // If C0 *already* matches true/false value of select, we are done.
1349 if (MatchesSelectValue(C0
))
1352 // Check the constant we'd have with flipped-strictness predicate.
1353 auto FlippedStrictness
= getFlippedStrictnessPredicateAndConstant(Pred
, C0
);
1354 if (!FlippedStrictness
)
1357 // If said constant doesn't match either, then there is no hope,
1358 if (!MatchesSelectValue(FlippedStrictness
->second
))
1361 // It matched! Lets insert the new comparison just before select.
1362 InstCombiner::BuilderTy::InsertPointGuard
Guard(Builder
);
1363 Builder
.SetInsertPoint(&Sel
);
1365 Pred
= ICmpInst::getSwappedPredicate(Pred
); // Yes, swapped.
1366 Value
*NewCmp
= Builder
.CreateICmp(Pred
, X
, FlippedStrictness
->second
,
1367 Cmp
.getName() + ".inv");
1368 Sel
.setCondition(NewCmp
);
1370 Sel
.swapProfMetadata();
1375 /// Visit a SelectInst that has an ICmpInst as its first operand.
1376 Instruction
*InstCombiner::foldSelectInstWithICmp(SelectInst
&SI
,
1378 if (Value
*V
= foldSelectValueEquivalence(SI
, *ICI
, SQ
))
1379 return replaceInstUsesWith(SI
, V
);
1381 if (Instruction
*NewSel
= canonicalizeMinMaxWithConstant(SI
, *ICI
, Builder
))
1384 if (Instruction
*NewAbs
= canonicalizeAbsNabs(SI
, *ICI
, Builder
))
1387 if (Instruction
*NewAbs
= canonicalizeClampLike(SI
, *ICI
, Builder
))
1390 if (Instruction
*NewSel
=
1391 tryToReuseConstantFromSelectInComparison(SI
, *ICI
, Builder
))
1394 bool Changed
= adjustMinMax(SI
, *ICI
);
1396 if (Value
*V
= foldSelectICmpAnd(SI
, ICI
, Builder
))
1397 return replaceInstUsesWith(SI
, V
);
1399 // NOTE: if we wanted to, this is where to detect integer MIN/MAX
1400 Value
*TrueVal
= SI
.getTrueValue();
1401 Value
*FalseVal
= SI
.getFalseValue();
1402 ICmpInst::Predicate Pred
= ICI
->getPredicate();
1403 Value
*CmpLHS
= ICI
->getOperand(0);
1404 Value
*CmpRHS
= ICI
->getOperand(1);
1405 if (CmpRHS
!= CmpLHS
&& isa
<Constant
>(CmpRHS
)) {
1406 if (CmpLHS
== TrueVal
&& Pred
== ICmpInst::ICMP_EQ
) {
1407 // Transform (X == C) ? X : Y -> (X == C) ? C : Y
1408 SI
.setOperand(1, CmpRHS
);
1410 } else if (CmpLHS
== FalseVal
&& Pred
== ICmpInst::ICMP_NE
) {
1411 // Transform (X != C) ? Y : X -> (X != C) ? Y : C
1412 SI
.setOperand(2, CmpRHS
);
1417 // FIXME: This code is nearly duplicated in InstSimplify. Using/refactoring
1418 // decomposeBitTestICmp() might help.
1421 DL
.getTypeSizeInBits(TrueVal
->getType()->getScalarType());
1422 APInt MinSignedValue
= APInt::getSignedMinValue(BitWidth
);
1426 bool IsBitTest
= false;
1427 if (ICmpInst::isEquality(Pred
) &&
1428 match(CmpLHS
, m_And(m_Value(X
), m_Power2(Y
))) &&
1429 match(CmpRHS
, m_Zero())) {
1431 TrueWhenUnset
= Pred
== ICmpInst::ICMP_EQ
;
1432 } else if (Pred
== ICmpInst::ICMP_SLT
&& match(CmpRHS
, m_Zero())) {
1434 Y
= &MinSignedValue
;
1436 TrueWhenUnset
= false;
1437 } else if (Pred
== ICmpInst::ICMP_SGT
&& match(CmpRHS
, m_AllOnes())) {
1439 Y
= &MinSignedValue
;
1441 TrueWhenUnset
= true;
1445 // (X & Y) == 0 ? X : X ^ Y --> X & ~Y
1446 if (TrueWhenUnset
&& TrueVal
== X
&&
1447 match(FalseVal
, m_Xor(m_Specific(X
), m_APInt(C
))) && *Y
== *C
)
1448 V
= Builder
.CreateAnd(X
, ~(*Y
));
1449 // (X & Y) != 0 ? X ^ Y : X --> X & ~Y
1450 else if (!TrueWhenUnset
&& FalseVal
== X
&&
1451 match(TrueVal
, m_Xor(m_Specific(X
), m_APInt(C
))) && *Y
== *C
)
1452 V
= Builder
.CreateAnd(X
, ~(*Y
));
1453 // (X & Y) == 0 ? X ^ Y : X --> X | Y
1454 else if (TrueWhenUnset
&& FalseVal
== X
&&
1455 match(TrueVal
, m_Xor(m_Specific(X
), m_APInt(C
))) && *Y
== *C
)
1456 V
= Builder
.CreateOr(X
, *Y
);
1457 // (X & Y) != 0 ? X : X ^ Y --> X | Y
1458 else if (!TrueWhenUnset
&& TrueVal
== X
&&
1459 match(FalseVal
, m_Xor(m_Specific(X
), m_APInt(C
))) && *Y
== *C
)
1460 V
= Builder
.CreateOr(X
, *Y
);
1463 return replaceInstUsesWith(SI
, V
);
1467 if (Instruction
*V
=
1468 foldSelectICmpAndAnd(SI
.getType(), ICI
, TrueVal
, FalseVal
, Builder
))
1471 if (Instruction
*V
= foldSelectCtlzToCttz(ICI
, TrueVal
, FalseVal
, Builder
))
1474 if (Value
*V
= foldSelectICmpAndOr(ICI
, TrueVal
, FalseVal
, Builder
))
1475 return replaceInstUsesWith(SI
, V
);
1477 if (Value
*V
= foldSelectICmpLshrAshr(ICI
, TrueVal
, FalseVal
, Builder
))
1478 return replaceInstUsesWith(SI
, V
);
1480 if (Value
*V
= foldSelectCttzCtlz(ICI
, TrueVal
, FalseVal
, Builder
))
1481 return replaceInstUsesWith(SI
, V
);
1483 if (Value
*V
= canonicalizeSaturatedSubtract(ICI
, TrueVal
, FalseVal
, Builder
))
1484 return replaceInstUsesWith(SI
, V
);
1486 if (Value
*V
= canonicalizeSaturatedAdd(ICI
, TrueVal
, FalseVal
, Builder
))
1487 return replaceInstUsesWith(SI
, V
);
1489 return Changed
? &SI
: nullptr;
1492 /// SI is a select whose condition is a PHI node (but the two may be in
1493 /// different blocks). See if the true/false values (V) are live in all of the
1494 /// predecessor blocks of the PHI. For example, cases like this can't be mapped:
1496 /// X = phi [ C1, BB1], [C2, BB2]
1498 /// Z = select X, Y, 0
1500 /// because Y is not live in BB1/BB2.
1501 static bool canSelectOperandBeMappingIntoPredBlock(const Value
*V
,
1502 const SelectInst
&SI
) {
1503 // If the value is a non-instruction value like a constant or argument, it
1504 // can always be mapped.
1505 const Instruction
*I
= dyn_cast
<Instruction
>(V
);
1506 if (!I
) return true;
1508 // If V is a PHI node defined in the same block as the condition PHI, we can
1509 // map the arguments.
1510 const PHINode
*CondPHI
= cast
<PHINode
>(SI
.getCondition());
1512 if (const PHINode
*VP
= dyn_cast
<PHINode
>(I
))
1513 if (VP
->getParent() == CondPHI
->getParent())
1516 // Otherwise, if the PHI and select are defined in the same block and if V is
1517 // defined in a different block, then we can transform it.
1518 if (SI
.getParent() == CondPHI
->getParent() &&
1519 I
->getParent() != CondPHI
->getParent())
1522 // Otherwise we have a 'hard' case and we can't tell without doing more
1523 // detailed dominator based analysis, punt.
1527 /// We have an SPF (e.g. a min or max) of an SPF of the form:
1528 /// SPF2(SPF1(A, B), C)
1529 Instruction
*InstCombiner::foldSPFofSPF(Instruction
*Inner
,
1530 SelectPatternFlavor SPF1
,
1533 SelectPatternFlavor SPF2
, Value
*C
) {
1534 if (Outer
.getType() != Inner
->getType())
1537 if (C
== A
|| C
== B
) {
1538 // MAX(MAX(A, B), B) -> MAX(A, B)
1539 // MIN(MIN(a, b), a) -> MIN(a, b)
1540 // TODO: This could be done in instsimplify.
1541 if (SPF1
== SPF2
&& SelectPatternResult::isMinOrMax(SPF1
))
1542 return replaceInstUsesWith(Outer
, Inner
);
1544 // MAX(MIN(a, b), a) -> a
1545 // MIN(MAX(a, b), a) -> a
1546 // TODO: This could be done in instsimplify.
1547 if ((SPF1
== SPF_SMIN
&& SPF2
== SPF_SMAX
) ||
1548 (SPF1
== SPF_SMAX
&& SPF2
== SPF_SMIN
) ||
1549 (SPF1
== SPF_UMIN
&& SPF2
== SPF_UMAX
) ||
1550 (SPF1
== SPF_UMAX
&& SPF2
== SPF_UMIN
))
1551 return replaceInstUsesWith(Outer
, C
);
1555 const APInt
*CB
, *CC
;
1556 if (match(B
, m_APInt(CB
)) && match(C
, m_APInt(CC
))) {
1557 // MIN(MIN(A, 23), 97) -> MIN(A, 23)
1558 // MAX(MAX(A, 97), 23) -> MAX(A, 97)
1559 // TODO: This could be done in instsimplify.
1560 if ((SPF1
== SPF_UMIN
&& CB
->ule(*CC
)) ||
1561 (SPF1
== SPF_SMIN
&& CB
->sle(*CC
)) ||
1562 (SPF1
== SPF_UMAX
&& CB
->uge(*CC
)) ||
1563 (SPF1
== SPF_SMAX
&& CB
->sge(*CC
)))
1564 return replaceInstUsesWith(Outer
, Inner
);
1566 // MIN(MIN(A, 97), 23) -> MIN(A, 23)
1567 // MAX(MAX(A, 23), 97) -> MAX(A, 97)
1568 if ((SPF1
== SPF_UMIN
&& CB
->ugt(*CC
)) ||
1569 (SPF1
== SPF_SMIN
&& CB
->sgt(*CC
)) ||
1570 (SPF1
== SPF_UMAX
&& CB
->ult(*CC
)) ||
1571 (SPF1
== SPF_SMAX
&& CB
->slt(*CC
))) {
1572 Outer
.replaceUsesOfWith(Inner
, A
);
1578 // max(max(A, B), min(A, B)) --> max(A, B)
1579 // min(min(A, B), max(A, B)) --> min(A, B)
1580 // TODO: This could be done in instsimplify.
1582 ((SPF1
== SPF_UMIN
&& match(C
, m_c_UMax(m_Specific(A
), m_Specific(B
)))) ||
1583 (SPF1
== SPF_SMIN
&& match(C
, m_c_SMax(m_Specific(A
), m_Specific(B
)))) ||
1584 (SPF1
== SPF_UMAX
&& match(C
, m_c_UMin(m_Specific(A
), m_Specific(B
)))) ||
1585 (SPF1
== SPF_SMAX
&& match(C
, m_c_SMin(m_Specific(A
), m_Specific(B
))))))
1586 return replaceInstUsesWith(Outer
, Inner
);
1588 // ABS(ABS(X)) -> ABS(X)
1589 // NABS(NABS(X)) -> NABS(X)
1590 // TODO: This could be done in instsimplify.
1591 if (SPF1
== SPF2
&& (SPF1
== SPF_ABS
|| SPF1
== SPF_NABS
)) {
1592 return replaceInstUsesWith(Outer
, Inner
);
1595 // ABS(NABS(X)) -> ABS(X)
1596 // NABS(ABS(X)) -> NABS(X)
1597 if ((SPF1
== SPF_ABS
&& SPF2
== SPF_NABS
) ||
1598 (SPF1
== SPF_NABS
&& SPF2
== SPF_ABS
)) {
1599 SelectInst
*SI
= cast
<SelectInst
>(Inner
);
1601 Builder
.CreateSelect(SI
->getCondition(), SI
->getFalseValue(),
1602 SI
->getTrueValue(), SI
->getName(), SI
);
1603 return replaceInstUsesWith(Outer
, NewSI
);
1606 auto IsFreeOrProfitableToInvert
=
1607 [&](Value
*V
, Value
*&NotV
, bool &ElidesXor
) {
1608 if (match(V
, m_Not(m_Value(NotV
)))) {
1609 // If V has at most 2 uses then we can get rid of the xor operation
1611 ElidesXor
|= !V
->hasNUsesOrMore(3);
1615 if (isFreeToInvert(V
, !V
->hasNUsesOrMore(3))) {
1623 Value
*NotA
, *NotB
, *NotC
;
1624 bool ElidesXor
= false;
1626 // MIN(MIN(~A, ~B), ~C) == ~MAX(MAX(A, B), C)
1627 // MIN(MAX(~A, ~B), ~C) == ~MAX(MIN(A, B), C)
1628 // MAX(MIN(~A, ~B), ~C) == ~MIN(MAX(A, B), C)
1629 // MAX(MAX(~A, ~B), ~C) == ~MIN(MIN(A, B), C)
1631 // This transform is performance neutral if we can elide at least one xor from
1632 // the set of three operands, since we'll be tacking on an xor at the very
1634 if (SelectPatternResult::isMinOrMax(SPF1
) &&
1635 SelectPatternResult::isMinOrMax(SPF2
) &&
1636 IsFreeOrProfitableToInvert(A
, NotA
, ElidesXor
) &&
1637 IsFreeOrProfitableToInvert(B
, NotB
, ElidesXor
) &&
1638 IsFreeOrProfitableToInvert(C
, NotC
, ElidesXor
) && ElidesXor
) {
1640 NotA
= Builder
.CreateNot(A
);
1642 NotB
= Builder
.CreateNot(B
);
1644 NotC
= Builder
.CreateNot(C
);
1646 Value
*NewInner
= createMinMax(Builder
, getInverseMinMaxFlavor(SPF1
), NotA
,
1648 Value
*NewOuter
= Builder
.CreateNot(
1649 createMinMax(Builder
, getInverseMinMaxFlavor(SPF2
), NewInner
, NotC
));
1650 return replaceInstUsesWith(Outer
, NewOuter
);
1656 /// Turn select C, (X + Y), (X - Y) --> (X + (select C, Y, (-Y))).
1657 /// This is even legal for FP.
1658 static Instruction
*foldAddSubSelect(SelectInst
&SI
,
1659 InstCombiner::BuilderTy
&Builder
) {
1660 Value
*CondVal
= SI
.getCondition();
1661 Value
*TrueVal
= SI
.getTrueValue();
1662 Value
*FalseVal
= SI
.getFalseValue();
1663 auto *TI
= dyn_cast
<Instruction
>(TrueVal
);
1664 auto *FI
= dyn_cast
<Instruction
>(FalseVal
);
1665 if (!TI
|| !FI
|| !TI
->hasOneUse() || !FI
->hasOneUse())
1668 Instruction
*AddOp
= nullptr, *SubOp
= nullptr;
1669 if ((TI
->getOpcode() == Instruction::Sub
&&
1670 FI
->getOpcode() == Instruction::Add
) ||
1671 (TI
->getOpcode() == Instruction::FSub
&&
1672 FI
->getOpcode() == Instruction::FAdd
)) {
1675 } else if ((FI
->getOpcode() == Instruction::Sub
&&
1676 TI
->getOpcode() == Instruction::Add
) ||
1677 (FI
->getOpcode() == Instruction::FSub
&&
1678 TI
->getOpcode() == Instruction::FAdd
)) {
1684 Value
*OtherAddOp
= nullptr;
1685 if (SubOp
->getOperand(0) == AddOp
->getOperand(0)) {
1686 OtherAddOp
= AddOp
->getOperand(1);
1687 } else if (SubOp
->getOperand(0) == AddOp
->getOperand(1)) {
1688 OtherAddOp
= AddOp
->getOperand(0);
1692 // So at this point we know we have (Y -> OtherAddOp):
1693 // select C, (add X, Y), (sub X, Z)
1694 Value
*NegVal
; // Compute -Z
1695 if (SI
.getType()->isFPOrFPVectorTy()) {
1696 NegVal
= Builder
.CreateFNeg(SubOp
->getOperand(1));
1697 if (Instruction
*NegInst
= dyn_cast
<Instruction
>(NegVal
)) {
1698 FastMathFlags Flags
= AddOp
->getFastMathFlags();
1699 Flags
&= SubOp
->getFastMathFlags();
1700 NegInst
->setFastMathFlags(Flags
);
1703 NegVal
= Builder
.CreateNeg(SubOp
->getOperand(1));
1706 Value
*NewTrueOp
= OtherAddOp
;
1707 Value
*NewFalseOp
= NegVal
;
1709 std::swap(NewTrueOp
, NewFalseOp
);
1710 Value
*NewSel
= Builder
.CreateSelect(CondVal
, NewTrueOp
, NewFalseOp
,
1711 SI
.getName() + ".p", &SI
);
1713 if (SI
.getType()->isFPOrFPVectorTy()) {
1715 BinaryOperator::CreateFAdd(SubOp
->getOperand(0), NewSel
);
1717 FastMathFlags Flags
= AddOp
->getFastMathFlags();
1718 Flags
&= SubOp
->getFastMathFlags();
1719 RI
->setFastMathFlags(Flags
);
1722 return BinaryOperator::CreateAdd(SubOp
->getOperand(0), NewSel
);
1728 Instruction
*InstCombiner::foldSelectExtConst(SelectInst
&Sel
) {
1730 if (!match(Sel
.getTrueValue(), m_Constant(C
)) &&
1731 !match(Sel
.getFalseValue(), m_Constant(C
)))
1734 Instruction
*ExtInst
;
1735 if (!match(Sel
.getTrueValue(), m_Instruction(ExtInst
)) &&
1736 !match(Sel
.getFalseValue(), m_Instruction(ExtInst
)))
1739 auto ExtOpcode
= ExtInst
->getOpcode();
1740 if (ExtOpcode
!= Instruction::ZExt
&& ExtOpcode
!= Instruction::SExt
)
1743 // If we are extending from a boolean type or if we can create a select that
1744 // has the same size operands as its condition, try to narrow the select.
1745 Value
*X
= ExtInst
->getOperand(0);
1746 Type
*SmallType
= X
->getType();
1747 Value
*Cond
= Sel
.getCondition();
1748 auto *Cmp
= dyn_cast
<CmpInst
>(Cond
);
1749 if (!SmallType
->isIntOrIntVectorTy(1) &&
1750 (!Cmp
|| Cmp
->getOperand(0)->getType() != SmallType
))
1753 // If the constant is the same after truncation to the smaller type and
1754 // extension to the original type, we can narrow the select.
1755 Type
*SelType
= Sel
.getType();
1756 Constant
*TruncC
= ConstantExpr::getTrunc(C
, SmallType
);
1757 Constant
*ExtC
= ConstantExpr::getCast(ExtOpcode
, TruncC
, SelType
);
1759 Value
*TruncCVal
= cast
<Value
>(TruncC
);
1760 if (ExtInst
== Sel
.getFalseValue())
1761 std::swap(X
, TruncCVal
);
1763 // select Cond, (ext X), C --> ext(select Cond, X, C')
1764 // select Cond, C, (ext X) --> ext(select Cond, C', X)
1765 Value
*NewSel
= Builder
.CreateSelect(Cond
, X
, TruncCVal
, "narrow", &Sel
);
1766 return CastInst::Create(Instruction::CastOps(ExtOpcode
), NewSel
, SelType
);
1769 // If one arm of the select is the extend of the condition, replace that arm
1770 // with the extension of the appropriate known bool value.
1772 if (ExtInst
== Sel
.getTrueValue()) {
1773 // select X, (sext X), C --> select X, -1, C
1774 // select X, (zext X), C --> select X, 1, C
1775 Constant
*One
= ConstantInt::getTrue(SmallType
);
1776 Constant
*AllOnesOrOne
= ConstantExpr::getCast(ExtOpcode
, One
, SelType
);
1777 return SelectInst::Create(Cond
, AllOnesOrOne
, C
, "", nullptr, &Sel
);
1779 // select X, C, (sext X) --> select X, C, 0
1780 // select X, C, (zext X) --> select X, C, 0
1781 Constant
*Zero
= ConstantInt::getNullValue(SelType
);
1782 return SelectInst::Create(Cond
, C
, Zero
, "", nullptr, &Sel
);
1789 /// Try to transform a vector select with a constant condition vector into a
1790 /// shuffle for easier combining with other shuffles and insert/extract.
1791 static Instruction
*canonicalizeSelectToShuffle(SelectInst
&SI
) {
1792 Value
*CondVal
= SI
.getCondition();
1794 if (!CondVal
->getType()->isVectorTy() || !match(CondVal
, m_Constant(CondC
)))
1797 unsigned NumElts
= CondVal
->getType()->getVectorNumElements();
1798 SmallVector
<Constant
*, 16> Mask
;
1799 Mask
.reserve(NumElts
);
1800 Type
*Int32Ty
= Type::getInt32Ty(CondVal
->getContext());
1801 for (unsigned i
= 0; i
!= NumElts
; ++i
) {
1802 Constant
*Elt
= CondC
->getAggregateElement(i
);
1806 if (Elt
->isOneValue()) {
1807 // If the select condition element is true, choose from the 1st vector.
1808 Mask
.push_back(ConstantInt::get(Int32Ty
, i
));
1809 } else if (Elt
->isNullValue()) {
1810 // If the select condition element is false, choose from the 2nd vector.
1811 Mask
.push_back(ConstantInt::get(Int32Ty
, i
+ NumElts
));
1812 } else if (isa
<UndefValue
>(Elt
)) {
1813 // Undef in a select condition (choose one of the operands) does not mean
1814 // the same thing as undef in a shuffle mask (any value is acceptable), so
1818 // Bail out on a constant expression.
1823 return new ShuffleVectorInst(SI
.getTrueValue(), SI
.getFalseValue(),
1824 ConstantVector::get(Mask
));
1827 /// If we have a select of vectors with a scalar condition, try to convert that
1828 /// to a vector select by splatting the condition. A splat may get folded with
1829 /// other operations in IR and having all operands of a select be vector types
1830 /// is likely better for vector codegen.
1831 static Instruction
*canonicalizeScalarSelectOfVecs(
1832 SelectInst
&Sel
, InstCombiner::BuilderTy
&Builder
) {
1833 Type
*Ty
= Sel
.getType();
1834 if (!Ty
->isVectorTy())
1837 // We can replace a single-use extract with constant index.
1838 Value
*Cond
= Sel
.getCondition();
1839 if (!match(Cond
, m_OneUse(m_ExtractElement(m_Value(), m_ConstantInt()))))
1842 // select (extelt V, Index), T, F --> select (splat V, Index), T, F
1843 // Splatting the extracted condition reduces code (we could directly create a
1844 // splat shuffle of the source vector to eliminate the intermediate step).
1845 unsigned NumElts
= Ty
->getVectorNumElements();
1846 Value
*SplatCond
= Builder
.CreateVectorSplat(NumElts
, Cond
);
1847 Sel
.setCondition(SplatCond
);
1851 /// Reuse bitcasted operands between a compare and select:
1852 /// select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
1853 /// bitcast (select (cmp (bitcast C), (bitcast D)), (bitcast C), (bitcast D))
1854 static Instruction
*foldSelectCmpBitcasts(SelectInst
&Sel
,
1855 InstCombiner::BuilderTy
&Builder
) {
1856 Value
*Cond
= Sel
.getCondition();
1857 Value
*TVal
= Sel
.getTrueValue();
1858 Value
*FVal
= Sel
.getFalseValue();
1860 CmpInst::Predicate Pred
;
1862 if (!match(Cond
, m_Cmp(Pred
, m_Value(A
), m_Value(B
))))
1865 // The select condition is a compare instruction. If the select's true/false
1866 // values are already the same as the compare operands, there's nothing to do.
1867 if (TVal
== A
|| TVal
== B
|| FVal
== A
|| FVal
== B
)
1871 if (!match(A
, m_BitCast(m_Value(C
))) || !match(B
, m_BitCast(m_Value(D
))))
1874 // select (cmp (bitcast C), (bitcast D)), (bitcast TSrc), (bitcast FSrc)
1876 if (!match(TVal
, m_BitCast(m_Value(TSrc
))) ||
1877 !match(FVal
, m_BitCast(m_Value(FSrc
))))
1880 // If the select true/false values are *different bitcasts* of the same source
1881 // operands, make the select operands the same as the compare operands and
1882 // cast the result. This is the canonical select form for min/max.
1884 if (TSrc
== C
&& FSrc
== D
) {
1885 // select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
1886 // bitcast (select (cmp A, B), A, B)
1887 NewSel
= Builder
.CreateSelect(Cond
, A
, B
, "", &Sel
);
1888 } else if (TSrc
== D
&& FSrc
== C
) {
1889 // select (cmp (bitcast C), (bitcast D)), (bitcast' D), (bitcast' C) -->
1890 // bitcast (select (cmp A, B), B, A)
1891 NewSel
= Builder
.CreateSelect(Cond
, B
, A
, "", &Sel
);
1895 return CastInst::CreateBitOrPointerCast(NewSel
, Sel
.getType());
1898 /// Try to eliminate select instructions that test the returned flag of cmpxchg
1901 /// If a select instruction tests the returned flag of a cmpxchg instruction and
1902 /// selects between the returned value of the cmpxchg instruction its compare
1903 /// operand, the result of the select will always be equal to its false value.
1906 /// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
1907 /// %1 = extractvalue { i64, i1 } %0, 1
1908 /// %2 = extractvalue { i64, i1 } %0, 0
1909 /// %3 = select i1 %1, i64 %compare, i64 %2
1912 /// The returned value of the cmpxchg instruction (%2) is the original value
1913 /// located at %ptr prior to any update. If the cmpxchg operation succeeds, %2
1914 /// must have been equal to %compare. Thus, the result of the select is always
1915 /// equal to %2, and the code can be simplified to:
1917 /// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
1918 /// %1 = extractvalue { i64, i1 } %0, 0
1921 static Instruction
*foldSelectCmpXchg(SelectInst
&SI
) {
1922 // A helper that determines if V is an extractvalue instruction whose
1923 // aggregate operand is a cmpxchg instruction and whose single index is equal
1924 // to I. If such conditions are true, the helper returns the cmpxchg
1925 // instruction; otherwise, a nullptr is returned.
1926 auto isExtractFromCmpXchg
= [](Value
*V
, unsigned I
) -> AtomicCmpXchgInst
* {
1927 auto *Extract
= dyn_cast
<ExtractValueInst
>(V
);
1930 if (Extract
->getIndices()[0] != I
)
1932 return dyn_cast
<AtomicCmpXchgInst
>(Extract
->getAggregateOperand());
1935 // If the select has a single user, and this user is a select instruction that
1936 // we can simplify, skip the cmpxchg simplification for now.
1938 if (auto *Select
= dyn_cast
<SelectInst
>(SI
.user_back()))
1939 if (Select
->getCondition() == SI
.getCondition())
1940 if (Select
->getFalseValue() == SI
.getTrueValue() ||
1941 Select
->getTrueValue() == SI
.getFalseValue())
1944 // Ensure the select condition is the returned flag of a cmpxchg instruction.
1945 auto *CmpXchg
= isExtractFromCmpXchg(SI
.getCondition(), 1);
1949 // Check the true value case: The true value of the select is the returned
1950 // value of the same cmpxchg used by the condition, and the false value is the
1951 // cmpxchg instruction's compare operand.
1952 if (auto *X
= isExtractFromCmpXchg(SI
.getTrueValue(), 0))
1953 if (X
== CmpXchg
&& X
->getCompareOperand() == SI
.getFalseValue()) {
1954 SI
.setTrueValue(SI
.getFalseValue());
1958 // Check the false value case: The false value of the select is the returned
1959 // value of the same cmpxchg used by the condition, and the true value is the
1960 // cmpxchg instruction's compare operand.
1961 if (auto *X
= isExtractFromCmpXchg(SI
.getFalseValue(), 0))
1962 if (X
== CmpXchg
&& X
->getCompareOperand() == SI
.getTrueValue()) {
1963 SI
.setTrueValue(SI
.getFalseValue());
1970 static Instruction
*moveAddAfterMinMax(SelectPatternFlavor SPF
, Value
*X
,
1972 InstCombiner::BuilderTy
&Builder
) {
1973 assert(SelectPatternResult::isMinOrMax(SPF
) && "Expected min/max pattern");
1974 bool IsUnsigned
= SPF
== SelectPatternFlavor::SPF_UMIN
||
1975 SPF
== SelectPatternFlavor::SPF_UMAX
;
1976 // TODO: If InstSimplify could fold all cases where C2 <= C1, we could change
1977 // the constant value check to an assert.
1979 const APInt
*C1
, *C2
;
1980 if (IsUnsigned
&& match(X
, m_NUWAdd(m_Value(A
), m_APInt(C1
))) &&
1981 match(Y
, m_APInt(C2
)) && C2
->uge(*C1
) && X
->hasNUses(2)) {
1982 // umin (add nuw A, C1), C2 --> add nuw (umin A, C2 - C1), C1
1983 // umax (add nuw A, C1), C2 --> add nuw (umax A, C2 - C1), C1
1984 Value
*NewMinMax
= createMinMax(Builder
, SPF
, A
,
1985 ConstantInt::get(X
->getType(), *C2
- *C1
));
1986 return BinaryOperator::CreateNUW(BinaryOperator::Add
, NewMinMax
,
1987 ConstantInt::get(X
->getType(), *C1
));
1990 if (!IsUnsigned
&& match(X
, m_NSWAdd(m_Value(A
), m_APInt(C1
))) &&
1991 match(Y
, m_APInt(C2
)) && X
->hasNUses(2)) {
1993 APInt Diff
= C2
->ssub_ov(*C1
, Overflow
);
1995 // smin (add nsw A, C1), C2 --> add nsw (smin A, C2 - C1), C1
1996 // smax (add nsw A, C1), C2 --> add nsw (smax A, C2 - C1), C1
1997 Value
*NewMinMax
= createMinMax(Builder
, SPF
, A
,
1998 ConstantInt::get(X
->getType(), Diff
));
1999 return BinaryOperator::CreateNSW(BinaryOperator::Add
, NewMinMax
,
2000 ConstantInt::get(X
->getType(), *C1
));
2007 /// Reduce a sequence of min/max with a common operand.
2008 static Instruction
*factorizeMinMaxTree(SelectPatternFlavor SPF
, Value
*LHS
,
2010 InstCombiner::BuilderTy
&Builder
) {
2011 assert(SelectPatternResult::isMinOrMax(SPF
) && "Expected a min/max");
2012 // TODO: Allow FP min/max with nnan/nsz.
2013 if (!LHS
->getType()->isIntOrIntVectorTy())
2016 // Match 3 of the same min/max ops. Example: umin(umin(), umin()).
2017 Value
*A
, *B
, *C
, *D
;
2018 SelectPatternResult L
= matchSelectPattern(LHS
, A
, B
);
2019 SelectPatternResult R
= matchSelectPattern(RHS
, C
, D
);
2020 if (SPF
!= L
.Flavor
|| L
.Flavor
!= R
.Flavor
)
2023 // Look for a common operand. The use checks are different than usual because
2024 // a min/max pattern typically has 2 uses of each op: 1 by the cmp and 1 by
2026 Value
*MinMaxOp
= nullptr;
2027 Value
*ThirdOp
= nullptr;
2028 if (!LHS
->hasNUsesOrMore(3) && RHS
->hasNUsesOrMore(3)) {
2029 // If the LHS is only used in this chain and the RHS is used outside of it,
2030 // reuse the RHS min/max because that will eliminate the LHS.
2031 if (D
== A
|| C
== A
) {
2032 // min(min(a, b), min(c, a)) --> min(min(c, a), b)
2033 // min(min(a, b), min(a, d)) --> min(min(a, d), b)
2036 } else if (D
== B
|| C
== B
) {
2037 // min(min(a, b), min(c, b)) --> min(min(c, b), a)
2038 // min(min(a, b), min(b, d)) --> min(min(b, d), a)
2042 } else if (!RHS
->hasNUsesOrMore(3)) {
2043 // Reuse the LHS. This will eliminate the RHS.
2044 if (D
== A
|| D
== B
) {
2045 // min(min(a, b), min(c, a)) --> min(min(a, b), c)
2046 // min(min(a, b), min(c, b)) --> min(min(a, b), c)
2049 } else if (C
== A
|| C
== B
) {
2050 // min(min(a, b), min(b, d)) --> min(min(a, b), d)
2051 // min(min(a, b), min(c, b)) --> min(min(a, b), d)
2056 if (!MinMaxOp
|| !ThirdOp
)
2059 CmpInst::Predicate P
= getMinMaxPred(SPF
);
2060 Value
*CmpABC
= Builder
.CreateICmp(P
, MinMaxOp
, ThirdOp
);
2061 return SelectInst::Create(CmpABC
, MinMaxOp
, ThirdOp
);
2064 /// Try to reduce a rotate pattern that includes a compare and select into a
2065 /// funnel shift intrinsic. Example:
2066 /// rotl32(a, b) --> (b == 0 ? a : ((a >> (32 - b)) | (a << b)))
2067 /// --> call llvm.fshl.i32(a, a, b)
2068 static Instruction
*foldSelectRotate(SelectInst
&Sel
) {
2069 // The false value of the select must be a rotate of the true value.
2071 if (!match(Sel
.getFalseValue(), m_OneUse(m_Or(m_Value(Or0
), m_Value(Or1
)))))
2074 Value
*TVal
= Sel
.getTrueValue();
2076 if (!match(Or0
, m_OneUse(m_LogicalShift(m_Specific(TVal
), m_Value(SA0
)))) ||
2077 !match(Or1
, m_OneUse(m_LogicalShift(m_Specific(TVal
), m_Value(SA1
)))))
2080 auto ShiftOpcode0
= cast
<BinaryOperator
>(Or0
)->getOpcode();
2081 auto ShiftOpcode1
= cast
<BinaryOperator
>(Or1
)->getOpcode();
2082 if (ShiftOpcode0
== ShiftOpcode1
)
2085 // We have one of these patterns so far:
2086 // select ?, TVal, (or (lshr TVal, SA0), (shl TVal, SA1))
2087 // select ?, TVal, (or (shl TVal, SA0), (lshr TVal, SA1))
2088 // This must be a power-of-2 rotate for a bitmasking transform to be valid.
2089 unsigned Width
= Sel
.getType()->getScalarSizeInBits();
2090 if (!isPowerOf2_32(Width
))
2093 // Check the shift amounts to see if they are an opposite pair.
2095 if (match(SA1
, m_OneUse(m_Sub(m_SpecificInt(Width
), m_Specific(SA0
)))))
2097 else if (match(SA0
, m_OneUse(m_Sub(m_SpecificInt(Width
), m_Specific(SA1
)))))
2102 // Finally, see if the select is filtering out a shift-by-zero.
2103 Value
*Cond
= Sel
.getCondition();
2104 ICmpInst::Predicate Pred
;
2105 if (!match(Cond
, m_OneUse(m_ICmp(Pred
, m_Specific(ShAmt
), m_ZeroInt()))) ||
2106 Pred
!= ICmpInst::ICMP_EQ
)
2109 // This is a rotate that avoids shift-by-bitwidth UB in a suboptimal way.
2110 // Convert to funnel shift intrinsic.
2111 bool IsFshl
= (ShAmt
== SA0
&& ShiftOpcode0
== BinaryOperator::Shl
) ||
2112 (ShAmt
== SA1
&& ShiftOpcode1
== BinaryOperator::Shl
);
2113 Intrinsic::ID IID
= IsFshl
? Intrinsic::fshl
: Intrinsic::fshr
;
2114 Function
*F
= Intrinsic::getDeclaration(Sel
.getModule(), IID
, Sel
.getType());
2115 return IntrinsicInst::Create(F
, { TVal
, TVal
, ShAmt
});
2118 Instruction
*InstCombiner::visitSelectInst(SelectInst
&SI
) {
2119 Value
*CondVal
= SI
.getCondition();
2120 Value
*TrueVal
= SI
.getTrueValue();
2121 Value
*FalseVal
= SI
.getFalseValue();
2122 Type
*SelType
= SI
.getType();
2124 // FIXME: Remove this workaround when freeze related patches are done.
2125 // For select with undef operand which feeds into an equality comparison,
2126 // don't simplify it so loop unswitch can know the equality comparison
2127 // may have an undef operand. This is a workaround for PR31652 caused by
2128 // descrepancy about branch on undef between LoopUnswitch and GVN.
2129 if (isa
<UndefValue
>(TrueVal
) || isa
<UndefValue
>(FalseVal
)) {
2130 if (llvm::any_of(SI
.users(), [&](User
*U
) {
2131 ICmpInst
*CI
= dyn_cast
<ICmpInst
>(U
);
2132 if (CI
&& CI
->isEquality())
2140 if (Value
*V
= SimplifySelectInst(CondVal
, TrueVal
, FalseVal
,
2141 SQ
.getWithInstruction(&SI
)))
2142 return replaceInstUsesWith(SI
, V
);
2144 if (Instruction
*I
= canonicalizeSelectToShuffle(SI
))
2147 if (Instruction
*I
= canonicalizeScalarSelectOfVecs(SI
, Builder
))
2150 // Canonicalize a one-use integer compare with a non-canonical predicate by
2151 // inverting the predicate and swapping the select operands. This matches a
2152 // compare canonicalization for conditional branches.
2153 // TODO: Should we do the same for FP compares?
2154 CmpInst::Predicate Pred
;
2155 if (match(CondVal
, m_OneUse(m_ICmp(Pred
, m_Value(), m_Value()))) &&
2156 !isCanonicalPredicate(Pred
)) {
2157 // Swap true/false values and condition.
2158 CmpInst
*Cond
= cast
<CmpInst
>(CondVal
);
2159 Cond
->setPredicate(CmpInst::getInversePredicate(Pred
));
2160 SI
.setOperand(1, FalseVal
);
2161 SI
.setOperand(2, TrueVal
);
2162 SI
.swapProfMetadata();
2167 if (SelType
->isIntOrIntVectorTy(1) &&
2168 TrueVal
->getType() == CondVal
->getType()) {
2169 if (match(TrueVal
, m_One())) {
2170 // Change: A = select B, true, C --> A = or B, C
2171 return BinaryOperator::CreateOr(CondVal
, FalseVal
);
2173 if (match(TrueVal
, m_Zero())) {
2174 // Change: A = select B, false, C --> A = and !B, C
2175 Value
*NotCond
= Builder
.CreateNot(CondVal
, "not." + CondVal
->getName());
2176 return BinaryOperator::CreateAnd(NotCond
, FalseVal
);
2178 if (match(FalseVal
, m_Zero())) {
2179 // Change: A = select B, C, false --> A = and B, C
2180 return BinaryOperator::CreateAnd(CondVal
, TrueVal
);
2182 if (match(FalseVal
, m_One())) {
2183 // Change: A = select B, C, true --> A = or !B, C
2184 Value
*NotCond
= Builder
.CreateNot(CondVal
, "not." + CondVal
->getName());
2185 return BinaryOperator::CreateOr(NotCond
, TrueVal
);
2188 // select a, a, b -> a | b
2189 // select a, b, a -> a & b
2190 if (CondVal
== TrueVal
)
2191 return BinaryOperator::CreateOr(CondVal
, FalseVal
);
2192 if (CondVal
== FalseVal
)
2193 return BinaryOperator::CreateAnd(CondVal
, TrueVal
);
2195 // select a, ~a, b -> (~a) & b
2196 // select a, b, ~a -> (~a) | b
2197 if (match(TrueVal
, m_Not(m_Specific(CondVal
))))
2198 return BinaryOperator::CreateAnd(TrueVal
, FalseVal
);
2199 if (match(FalseVal
, m_Not(m_Specific(CondVal
))))
2200 return BinaryOperator::CreateOr(TrueVal
, FalseVal
);
2203 // Selecting between two integer or vector splat integer constants?
2205 // Note that we don't handle a scalar select of vectors:
2206 // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>
2207 // because that may need 3 instructions to splat the condition value:
2208 // extend, insertelement, shufflevector.
2209 if (SelType
->isIntOrIntVectorTy() &&
2210 CondVal
->getType()->isVectorTy() == SelType
->isVectorTy()) {
2211 // select C, 1, 0 -> zext C to int
2212 if (match(TrueVal
, m_One()) && match(FalseVal
, m_Zero()))
2213 return new ZExtInst(CondVal
, SelType
);
2215 // select C, -1, 0 -> sext C to int
2216 if (match(TrueVal
, m_AllOnes()) && match(FalseVal
, m_Zero()))
2217 return new SExtInst(CondVal
, SelType
);
2219 // select C, 0, 1 -> zext !C to int
2220 if (match(TrueVal
, m_Zero()) && match(FalseVal
, m_One())) {
2221 Value
*NotCond
= Builder
.CreateNot(CondVal
, "not." + CondVal
->getName());
2222 return new ZExtInst(NotCond
, SelType
);
2225 // select C, 0, -1 -> sext !C to int
2226 if (match(TrueVal
, m_Zero()) && match(FalseVal
, m_AllOnes())) {
2227 Value
*NotCond
= Builder
.CreateNot(CondVal
, "not." + CondVal
->getName());
2228 return new SExtInst(NotCond
, SelType
);
2232 // See if we are selecting two values based on a comparison of the two values.
2233 if (FCmpInst
*FCI
= dyn_cast
<FCmpInst
>(CondVal
)) {
2234 if (FCI
->getOperand(0) == TrueVal
&& FCI
->getOperand(1) == FalseVal
) {
2235 // Canonicalize to use ordered comparisons by swapping the select
2239 // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X
2240 if (FCI
->hasOneUse() && FCmpInst::isUnordered(FCI
->getPredicate())) {
2241 FCmpInst::Predicate InvPred
= FCI
->getInversePredicate();
2242 IRBuilder
<>::FastMathFlagGuard
FMFG(Builder
);
2243 Builder
.setFastMathFlags(FCI
->getFastMathFlags());
2244 Value
*NewCond
= Builder
.CreateFCmp(InvPred
, TrueVal
, FalseVal
,
2245 FCI
->getName() + ".inv");
2247 return SelectInst::Create(NewCond
, FalseVal
, TrueVal
,
2248 SI
.getName() + ".p");
2251 // NOTE: if we wanted to, this is where to detect MIN/MAX
2252 } else if (FCI
->getOperand(0) == FalseVal
&& FCI
->getOperand(1) == TrueVal
){
2253 // Canonicalize to use ordered comparisons by swapping the select
2257 // (X ugt Y) ? X : Y -> (X ole Y) ? X : Y
2258 if (FCI
->hasOneUse() && FCmpInst::isUnordered(FCI
->getPredicate())) {
2259 FCmpInst::Predicate InvPred
= FCI
->getInversePredicate();
2260 IRBuilder
<>::FastMathFlagGuard
FMFG(Builder
);
2261 Builder
.setFastMathFlags(FCI
->getFastMathFlags());
2262 Value
*NewCond
= Builder
.CreateFCmp(InvPred
, FalseVal
, TrueVal
,
2263 FCI
->getName() + ".inv");
2265 return SelectInst::Create(NewCond
, FalseVal
, TrueVal
,
2266 SI
.getName() + ".p");
2269 // NOTE: if we wanted to, this is where to detect MIN/MAX
2273 // Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need
2274 // fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work. We
2275 // also require nnan because we do not want to unintentionally change the
2276 // sign of a NaN value.
2277 // FIXME: These folds should test/propagate FMF from the select, not the
2279 // (X <= +/-0.0) ? (0.0 - X) : X --> fabs(X)
2281 if (match(CondVal
, m_FCmp(Pred
, m_Specific(FalseVal
), m_AnyZeroFP())) &&
2282 match(TrueVal
, m_FSub(m_PosZeroFP(), m_Specific(FalseVal
))) &&
2283 match(TrueVal
, m_Instruction(FSub
)) && FSub
->hasNoNaNs() &&
2284 (Pred
== FCmpInst::FCMP_OLE
|| Pred
== FCmpInst::FCMP_ULE
)) {
2285 Value
*Fabs
= Builder
.CreateUnaryIntrinsic(Intrinsic::fabs
, FalseVal
, FSub
);
2286 return replaceInstUsesWith(SI
, Fabs
);
2288 // (X > +/-0.0) ? X : (0.0 - X) --> fabs(X)
2289 if (match(CondVal
, m_FCmp(Pred
, m_Specific(TrueVal
), m_AnyZeroFP())) &&
2290 match(FalseVal
, m_FSub(m_PosZeroFP(), m_Specific(TrueVal
))) &&
2291 match(FalseVal
, m_Instruction(FSub
)) && FSub
->hasNoNaNs() &&
2292 (Pred
== FCmpInst::FCMP_OGT
|| Pred
== FCmpInst::FCMP_UGT
)) {
2293 Value
*Fabs
= Builder
.CreateUnaryIntrinsic(Intrinsic::fabs
, TrueVal
, FSub
);
2294 return replaceInstUsesWith(SI
, Fabs
);
2296 // With nnan and nsz:
2297 // (X < +/-0.0) ? -X : X --> fabs(X)
2298 // (X <= +/-0.0) ? -X : X --> fabs(X)
2300 if (match(CondVal
, m_FCmp(Pred
, m_Specific(FalseVal
), m_AnyZeroFP())) &&
2301 match(TrueVal
, m_FNeg(m_Specific(FalseVal
))) &&
2302 match(TrueVal
, m_Instruction(FNeg
)) &&
2303 FNeg
->hasNoNaNs() && FNeg
->hasNoSignedZeros() &&
2304 (Pred
== FCmpInst::FCMP_OLT
|| Pred
== FCmpInst::FCMP_OLE
||
2305 Pred
== FCmpInst::FCMP_ULT
|| Pred
== FCmpInst::FCMP_ULE
)) {
2306 Value
*Fabs
= Builder
.CreateUnaryIntrinsic(Intrinsic::fabs
, FalseVal
, FNeg
);
2307 return replaceInstUsesWith(SI
, Fabs
);
2309 // With nnan and nsz:
2310 // (X > +/-0.0) ? X : -X --> fabs(X)
2311 // (X >= +/-0.0) ? X : -X --> fabs(X)
2312 if (match(CondVal
, m_FCmp(Pred
, m_Specific(TrueVal
), m_AnyZeroFP())) &&
2313 match(FalseVal
, m_FNeg(m_Specific(TrueVal
))) &&
2314 match(FalseVal
, m_Instruction(FNeg
)) &&
2315 FNeg
->hasNoNaNs() && FNeg
->hasNoSignedZeros() &&
2316 (Pred
== FCmpInst::FCMP_OGT
|| Pred
== FCmpInst::FCMP_OGE
||
2317 Pred
== FCmpInst::FCMP_UGT
|| Pred
== FCmpInst::FCMP_UGE
)) {
2318 Value
*Fabs
= Builder
.CreateUnaryIntrinsic(Intrinsic::fabs
, TrueVal
, FNeg
);
2319 return replaceInstUsesWith(SI
, Fabs
);
2322 // See if we are selecting two values based on a comparison of the two values.
2323 if (ICmpInst
*ICI
= dyn_cast
<ICmpInst
>(CondVal
))
2324 if (Instruction
*Result
= foldSelectInstWithICmp(SI
, ICI
))
2327 if (Instruction
*Add
= foldAddSubSelect(SI
, Builder
))
2330 // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
2331 auto *TI
= dyn_cast
<Instruction
>(TrueVal
);
2332 auto *FI
= dyn_cast
<Instruction
>(FalseVal
);
2333 if (TI
&& FI
&& TI
->getOpcode() == FI
->getOpcode())
2334 if (Instruction
*IV
= foldSelectOpOp(SI
, TI
, FI
))
2337 if (Instruction
*I
= foldSelectExtConst(SI
))
2340 // See if we can fold the select into one of our operands.
2341 if (SelType
->isIntOrIntVectorTy() || SelType
->isFPOrFPVectorTy()) {
2342 if (Instruction
*FoldI
= foldSelectIntoOp(SI
, TrueVal
, FalseVal
))
2346 Instruction::CastOps CastOp
;
2347 SelectPatternResult SPR
= matchSelectPattern(&SI
, LHS
, RHS
, &CastOp
);
2348 auto SPF
= SPR
.Flavor
;
2351 if (SelectPatternFlavor SPF2
= matchSelectPattern(LHS
, LHS2
, RHS2
).Flavor
)
2352 if (Instruction
*R
= foldSPFofSPF(cast
<Instruction
>(LHS
), SPF2
, LHS2
,
2353 RHS2
, SI
, SPF
, RHS
))
2355 if (SelectPatternFlavor SPF2
= matchSelectPattern(RHS
, LHS2
, RHS2
).Flavor
)
2356 if (Instruction
*R
= foldSPFofSPF(cast
<Instruction
>(RHS
), SPF2
, LHS2
,
2357 RHS2
, SI
, SPF
, LHS
))
2360 // ABS(-X) -> ABS(X)
2363 if (SelectPatternResult::isMinOrMax(SPF
)) {
2364 // Canonicalize so that
2365 // - type casts are outside select patterns.
2366 // - float clamp is transformed to min/max pattern
2368 bool IsCastNeeded
= LHS
->getType() != SelType
;
2369 Value
*CmpLHS
= cast
<CmpInst
>(CondVal
)->getOperand(0);
2370 Value
*CmpRHS
= cast
<CmpInst
>(CondVal
)->getOperand(1);
2372 (LHS
->getType()->isFPOrFPVectorTy() &&
2373 ((CmpLHS
!= LHS
&& CmpLHS
!= RHS
) ||
2374 (CmpRHS
!= LHS
&& CmpRHS
!= RHS
)))) {
2375 CmpInst::Predicate MinMaxPred
= getMinMaxPred(SPF
, SPR
.Ordered
);
2378 if (CmpInst::isIntPredicate(MinMaxPred
)) {
2379 Cmp
= Builder
.CreateICmp(MinMaxPred
, LHS
, RHS
);
2381 IRBuilder
<>::FastMathFlagGuard
FMFG(Builder
);
2383 cast
<FPMathOperator
>(SI
.getCondition())->getFastMathFlags();
2384 Builder
.setFastMathFlags(FMF
);
2385 Cmp
= Builder
.CreateFCmp(MinMaxPred
, LHS
, RHS
);
2388 Value
*NewSI
= Builder
.CreateSelect(Cmp
, LHS
, RHS
, SI
.getName(), &SI
);
2390 return replaceInstUsesWith(SI
, NewSI
);
2392 Value
*NewCast
= Builder
.CreateCast(CastOp
, NewSI
, SelType
);
2393 return replaceInstUsesWith(SI
, NewCast
);
2396 // MAX(~a, ~b) -> ~MIN(a, b)
2397 // MAX(~a, C) -> ~MIN(a, ~C)
2398 // MIN(~a, ~b) -> ~MAX(a, b)
2399 // MIN(~a, C) -> ~MAX(a, ~C)
2400 auto moveNotAfterMinMax
= [&](Value
*X
, Value
*Y
) -> Instruction
* {
2402 if (match(X
, m_Not(m_Value(A
))) && !X
->hasNUsesOrMore(3) &&
2403 !isFreeToInvert(A
, A
->hasOneUse()) &&
2404 // Passing false to only consider m_Not and constants.
2405 isFreeToInvert(Y
, false)) {
2406 Value
*B
= Builder
.CreateNot(Y
);
2407 Value
*NewMinMax
= createMinMax(Builder
, getInverseMinMaxFlavor(SPF
),
2409 // Copy the profile metadata.
2410 if (MDNode
*MD
= SI
.getMetadata(LLVMContext::MD_prof
)) {
2411 cast
<SelectInst
>(NewMinMax
)->setMetadata(LLVMContext::MD_prof
, MD
);
2412 // Swap the metadata if the operands are swapped.
2413 if (X
== SI
.getFalseValue() && Y
== SI
.getTrueValue())
2414 cast
<SelectInst
>(NewMinMax
)->swapProfMetadata();
2417 return BinaryOperator::CreateNot(NewMinMax
);
2423 if (Instruction
*I
= moveNotAfterMinMax(LHS
, RHS
))
2425 if (Instruction
*I
= moveNotAfterMinMax(RHS
, LHS
))
2428 if (Instruction
*I
= moveAddAfterMinMax(SPF
, LHS
, RHS
, Builder
))
2431 if (Instruction
*I
= factorizeMinMaxTree(SPF
, LHS
, RHS
, Builder
))
2436 // Canonicalize select of FP values where NaN and -0.0 are not valid as
2437 // minnum/maxnum intrinsics.
2438 if (isa
<FPMathOperator
>(SI
) && SI
.hasNoNaNs() && SI
.hasNoSignedZeros()) {
2440 if (match(&SI
, m_OrdFMax(m_Value(X
), m_Value(Y
))))
2441 return replaceInstUsesWith(
2442 SI
, Builder
.CreateBinaryIntrinsic(Intrinsic::maxnum
, X
, Y
, &SI
));
2444 if (match(&SI
, m_OrdFMin(m_Value(X
), m_Value(Y
))))
2445 return replaceInstUsesWith(
2446 SI
, Builder
.CreateBinaryIntrinsic(Intrinsic::minnum
, X
, Y
, &SI
));
2449 // See if we can fold the select into a phi node if the condition is a select.
2450 if (auto *PN
= dyn_cast
<PHINode
>(SI
.getCondition()))
2451 // The true/false values have to be live in the PHI predecessor's blocks.
2452 if (canSelectOperandBeMappingIntoPredBlock(TrueVal
, SI
) &&
2453 canSelectOperandBeMappingIntoPredBlock(FalseVal
, SI
))
2454 if (Instruction
*NV
= foldOpIntoPhi(SI
, PN
))
2457 if (SelectInst
*TrueSI
= dyn_cast
<SelectInst
>(TrueVal
)) {
2458 if (TrueSI
->getCondition()->getType() == CondVal
->getType()) {
2459 // select(C, select(C, a, b), c) -> select(C, a, c)
2460 if (TrueSI
->getCondition() == CondVal
) {
2461 if (SI
.getTrueValue() == TrueSI
->getTrueValue())
2463 SI
.setOperand(1, TrueSI
->getTrueValue());
2466 // select(C0, select(C1, a, b), b) -> select(C0&C1, a, b)
2467 // We choose this as normal form to enable folding on the And and shortening
2468 // paths for the values (this helps GetUnderlyingObjects() for example).
2469 if (TrueSI
->getFalseValue() == FalseVal
&& TrueSI
->hasOneUse()) {
2470 Value
*And
= Builder
.CreateAnd(CondVal
, TrueSI
->getCondition());
2471 SI
.setOperand(0, And
);
2472 SI
.setOperand(1, TrueSI
->getTrueValue());
2477 if (SelectInst
*FalseSI
= dyn_cast
<SelectInst
>(FalseVal
)) {
2478 if (FalseSI
->getCondition()->getType() == CondVal
->getType()) {
2479 // select(C, a, select(C, b, c)) -> select(C, a, c)
2480 if (FalseSI
->getCondition() == CondVal
) {
2481 if (SI
.getFalseValue() == FalseSI
->getFalseValue())
2483 SI
.setOperand(2, FalseSI
->getFalseValue());
2486 // select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b)
2487 if (FalseSI
->getTrueValue() == TrueVal
&& FalseSI
->hasOneUse()) {
2488 Value
*Or
= Builder
.CreateOr(CondVal
, FalseSI
->getCondition());
2489 SI
.setOperand(0, Or
);
2490 SI
.setOperand(2, FalseSI
->getFalseValue());
2496 auto canMergeSelectThroughBinop
= [](BinaryOperator
*BO
) {
2497 // The select might be preventing a division by 0.
2498 switch (BO
->getOpcode()) {
2501 case Instruction::SRem
:
2502 case Instruction::URem
:
2503 case Instruction::SDiv
:
2504 case Instruction::UDiv
:
2509 // Try to simplify a binop sandwiched between 2 selects with the same
2511 // select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z)
2512 BinaryOperator
*TrueBO
;
2513 if (match(TrueVal
, m_OneUse(m_BinOp(TrueBO
))) &&
2514 canMergeSelectThroughBinop(TrueBO
)) {
2515 if (auto *TrueBOSI
= dyn_cast
<SelectInst
>(TrueBO
->getOperand(0))) {
2516 if (TrueBOSI
->getCondition() == CondVal
) {
2517 TrueBO
->setOperand(0, TrueBOSI
->getTrueValue());
2518 Worklist
.Add(TrueBO
);
2522 if (auto *TrueBOSI
= dyn_cast
<SelectInst
>(TrueBO
->getOperand(1))) {
2523 if (TrueBOSI
->getCondition() == CondVal
) {
2524 TrueBO
->setOperand(1, TrueBOSI
->getTrueValue());
2525 Worklist
.Add(TrueBO
);
2531 // select(C, Z, binop(select(C, X, Y), W)) -> select(C, Z, binop(Y, W))
2532 BinaryOperator
*FalseBO
;
2533 if (match(FalseVal
, m_OneUse(m_BinOp(FalseBO
))) &&
2534 canMergeSelectThroughBinop(FalseBO
)) {
2535 if (auto *FalseBOSI
= dyn_cast
<SelectInst
>(FalseBO
->getOperand(0))) {
2536 if (FalseBOSI
->getCondition() == CondVal
) {
2537 FalseBO
->setOperand(0, FalseBOSI
->getFalseValue());
2538 Worklist
.Add(FalseBO
);
2542 if (auto *FalseBOSI
= dyn_cast
<SelectInst
>(FalseBO
->getOperand(1))) {
2543 if (FalseBOSI
->getCondition() == CondVal
) {
2544 FalseBO
->setOperand(1, FalseBOSI
->getFalseValue());
2545 Worklist
.Add(FalseBO
);
2552 if (match(CondVal
, m_Not(m_Value(NotCond
)))) {
2553 SI
.setOperand(0, NotCond
);
2554 SI
.setOperand(1, FalseVal
);
2555 SI
.setOperand(2, TrueVal
);
2556 SI
.swapProfMetadata();
2560 if (VectorType
*VecTy
= dyn_cast
<VectorType
>(SelType
)) {
2561 unsigned VWidth
= VecTy
->getNumElements();
2562 APInt
UndefElts(VWidth
, 0);
2563 APInt
AllOnesEltMask(APInt::getAllOnesValue(VWidth
));
2564 if (Value
*V
= SimplifyDemandedVectorElts(&SI
, AllOnesEltMask
, UndefElts
)) {
2566 return replaceInstUsesWith(SI
, V
);
2571 // If we can compute the condition, there's no need for a select.
2572 // Like the above fold, we are attempting to reduce compile-time cost by
2573 // putting this fold here with limitations rather than in InstSimplify.
2574 // The motivation for this call into value tracking is to take advantage of
2575 // the assumption cache, so make sure that is populated.
2576 if (!CondVal
->getType()->isVectorTy() && !AC
.assumptions().empty()) {
2578 computeKnownBits(CondVal
, Known
, 0, &SI
);
2579 if (Known
.One
.isOneValue())
2580 return replaceInstUsesWith(SI
, TrueVal
);
2581 if (Known
.Zero
.isOneValue())
2582 return replaceInstUsesWith(SI
, FalseVal
);
2585 if (Instruction
*BitCastSel
= foldSelectCmpBitcasts(SI
, Builder
))
2588 // Simplify selects that test the returned flag of cmpxchg instructions.
2589 if (Instruction
*Select
= foldSelectCmpXchg(SI
))
2592 if (Instruction
*Select
= foldSelectBinOpIdentity(SI
, TLI
))
2595 if (Instruction
*Rot
= foldSelectRotate(SI
))