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