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