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