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