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