LLVM 17.0.0git
InstCombineSelect.cpp
Go to the documentation of this file.
1//===- InstCombineSelect.cpp ----------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the visitSelect function.
10//
11//===----------------------------------------------------------------------===//
12
13#include "InstCombineInternal.h"
14#include "llvm/ADT/APInt.h"
15#include "llvm/ADT/STLExtras.h"
23#include "llvm/IR/BasicBlock.h"
24#include "llvm/IR/Constant.h"
26#include "llvm/IR/Constants.h"
28#include "llvm/IR/IRBuilder.h"
29#include "llvm/IR/InstrTypes.h"
30#include "llvm/IR/Instruction.h"
33#include "llvm/IR/Intrinsics.h"
34#include "llvm/IR/Operator.h"
36#include "llvm/IR/Type.h"
37#include "llvm/IR/User.h"
38#include "llvm/IR/Value.h"
43#include <cassert>
44#include <utility>
45
46#define DEBUG_TYPE "instcombine"
48
49using namespace llvm;
50using namespace PatternMatch;
51
52
53/// Replace a select operand based on an equality comparison with the identity
54/// constant of a binop.
56 const TargetLibraryInfo &TLI,
57 InstCombinerImpl &IC) {
58 // The select condition must be an equality compare with a constant operand.
59 Value *X;
60 Constant *C;
62 if (!match(Sel.getCondition(), m_Cmp(Pred, m_Value(X), m_Constant(C))))
63 return nullptr;
64
65 bool IsEq;
66 if (ICmpInst::isEquality(Pred))
67 IsEq = Pred == ICmpInst::ICMP_EQ;
68 else if (Pred == FCmpInst::FCMP_OEQ)
69 IsEq = true;
70 else if (Pred == FCmpInst::FCMP_UNE)
71 IsEq = false;
72 else
73 return nullptr;
74
75 // A select operand must be a binop.
77 if (!match(Sel.getOperand(IsEq ? 1 : 2), m_BinOp(BO)))
78 return nullptr;
79
80 // The compare constant must be the identity constant for that binop.
81 // If this a floating-point compare with 0.0, any zero constant will do.
82 Type *Ty = BO->getType();
84 if (IdC != C) {
85 if (!IdC || !CmpInst::isFPPredicate(Pred))
86 return nullptr;
87 if (!match(IdC, m_AnyZeroFP()) || !match(C, m_AnyZeroFP()))
88 return nullptr;
89 }
90
91 // Last, match the compare variable operand with a binop operand.
92 Value *Y;
93 if (!BO->isCommutative() && !match(BO, m_BinOp(m_Value(Y), m_Specific(X))))
94 return nullptr;
95 if (!match(BO, m_c_BinOp(m_Value(Y), m_Specific(X))))
96 return nullptr;
97
98 // +0.0 compares equal to -0.0, and so it does not behave as required for this
99 // transform. Bail out if we can not exclude that possibility.
100 if (isa<FPMathOperator>(BO))
101 if (!BO->hasNoSignedZeros() && !CannotBeNegativeZero(Y, &TLI))
102 return nullptr;
103
104 // BO = binop Y, X
105 // S = { select (cmp eq X, C), BO, ? } or { select (cmp ne X, C), ?, BO }
106 // =>
107 // S = { select (cmp eq X, C), Y, ? } or { select (cmp ne X, C), ?, Y }
108 return IC.replaceOperand(Sel, IsEq ? 1 : 2, Y);
109}
110
111/// This folds:
112/// select (icmp eq (and X, C1)), TC, FC
113/// iff C1 is a power 2 and the difference between TC and FC is a power-of-2.
114/// To something like:
115/// (shr (and (X, C1)), (log2(C1) - log2(TC-FC))) + FC
116/// Or:
117/// (shl (and (X, C1)), (log2(TC-FC) - log2(C1))) + FC
118/// With some variations depending if FC is larger than TC, or the shift
119/// isn't needed, or the bit widths don't match.
121 InstCombiner::BuilderTy &Builder) {
122 const APInt *SelTC, *SelFC;
123 if (!match(Sel.getTrueValue(), m_APInt(SelTC)) ||
124 !match(Sel.getFalseValue(), m_APInt(SelFC)))
125 return nullptr;
126
127 // If this is a vector select, we need a vector compare.
128 Type *SelType = Sel.getType();
129 if (SelType->isVectorTy() != Cmp->getType()->isVectorTy())
130 return nullptr;
131
132 Value *V;
133 APInt AndMask;
134 bool CreateAnd = false;
135 ICmpInst::Predicate Pred = Cmp->getPredicate();
136 if (ICmpInst::isEquality(Pred)) {
137 if (!match(Cmp->getOperand(1), m_Zero()))
138 return nullptr;
139
140 V = Cmp->getOperand(0);
141 const APInt *AndRHS;
142 if (!match(V, m_And(m_Value(), m_Power2(AndRHS))))
143 return nullptr;
144
145 AndMask = *AndRHS;
146 } else if (decomposeBitTestICmp(Cmp->getOperand(0), Cmp->getOperand(1),
147 Pred, V, AndMask)) {
148 assert(ICmpInst::isEquality(Pred) && "Not equality test?");
149 if (!AndMask.isPowerOf2())
150 return nullptr;
151
152 CreateAnd = true;
153 } else {
154 return nullptr;
155 }
156
157 // In general, when both constants are non-zero, we would need an offset to
158 // replace the select. This would require more instructions than we started
159 // with. But there's one special-case that we handle here because it can
160 // simplify/reduce the instructions.
161 APInt TC = *SelTC;
162 APInt FC = *SelFC;
163 if (!TC.isZero() && !FC.isZero()) {
164 // If the select constants differ by exactly one bit and that's the same
165 // bit that is masked and checked by the select condition, the select can
166 // be replaced by bitwise logic to set/clear one bit of the constant result.
167 if (TC.getBitWidth() != AndMask.getBitWidth() || (TC ^ FC) != AndMask)
168 return nullptr;
169 if (CreateAnd) {
170 // If we have to create an 'and', then we must kill the cmp to not
171 // increase the instruction count.
172 if (!Cmp->hasOneUse())
173 return nullptr;
174 V = Builder.CreateAnd(V, ConstantInt::get(SelType, AndMask));
175 }
176 bool ExtraBitInTC = TC.ugt(FC);
177 if (Pred == ICmpInst::ICMP_EQ) {
178 // If the masked bit in V is clear, clear or set the bit in the result:
179 // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) ^ TC
180 // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) | TC
181 Constant *C = ConstantInt::get(SelType, TC);
182 return ExtraBitInTC ? Builder.CreateXor(V, C) : Builder.CreateOr(V, C);
183 }
184 if (Pred == ICmpInst::ICMP_NE) {
185 // If the masked bit in V is set, set or clear the bit in the result:
186 // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) | FC
187 // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) ^ FC
188 Constant *C = ConstantInt::get(SelType, FC);
189 return ExtraBitInTC ? Builder.CreateOr(V, C) : Builder.CreateXor(V, C);
190 }
191 llvm_unreachable("Only expecting equality predicates");
192 }
193
194 // Make sure one of the select arms is a power-of-2.
195 if (!TC.isPowerOf2() && !FC.isPowerOf2())
196 return nullptr;
197
198 // Determine which shift is needed to transform result of the 'and' into the
199 // desired result.
200 const APInt &ValC = !TC.isZero() ? TC : FC;
201 unsigned ValZeros = ValC.logBase2();
202 unsigned AndZeros = AndMask.logBase2();
203
204 // Insert the 'and' instruction on the input to the truncate.
205 if (CreateAnd)
206 V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), AndMask));
207
208 // If types don't match, we can still convert the select by introducing a zext
209 // or a trunc of the 'and'.
210 if (ValZeros > AndZeros) {
211 V = Builder.CreateZExtOrTrunc(V, SelType);
212 V = Builder.CreateShl(V, ValZeros - AndZeros);
213 } else if (ValZeros < AndZeros) {
214 V = Builder.CreateLShr(V, AndZeros - ValZeros);
215 V = Builder.CreateZExtOrTrunc(V, SelType);
216 } else {
217 V = Builder.CreateZExtOrTrunc(V, SelType);
218 }
219
220 // Okay, now we know that everything is set up, we just don't know whether we
221 // have a icmp_ne or icmp_eq and whether the true or false val is the zero.
222 bool ShouldNotVal = !TC.isZero();
223 ShouldNotVal ^= Pred == ICmpInst::ICMP_NE;
224 if (ShouldNotVal)
225 V = Builder.CreateXor(V, ValC);
226
227 return V;
228}
229
230/// We want to turn code that looks like this:
231/// %C = or %A, %B
232/// %D = select %cond, %C, %A
233/// into:
234/// %C = select %cond, %B, 0
235/// %D = or %A, %C
236///
237/// Assuming that the specified instruction is an operand to the select, return
238/// a bitmask indicating which operands of this instruction are foldable if they
239/// equal the other incoming value of the select.
241 switch (I->getOpcode()) {
242 case Instruction::Add:
243 case Instruction::FAdd:
244 case Instruction::Mul:
245 case Instruction::FMul:
246 case Instruction::And:
247 case Instruction::Or:
248 case Instruction::Xor:
249 return 3; // Can fold through either operand.
250 case Instruction::Sub: // Can only fold on the amount subtracted.
251 case Instruction::FSub:
252 case Instruction::FDiv: // Can only fold on the divisor amount.
253 case Instruction::Shl: // Can only fold on the shift amount.
254 case Instruction::LShr:
255 case Instruction::AShr:
256 return 1;
257 default:
258 return 0; // Cannot fold
259 }
260}
261
262/// We have (select c, TI, FI), and we know that TI and FI have the same opcode.
264 Instruction *FI) {
265 // Don't break up min/max patterns. The hasOneUse checks below prevent that
266 // for most cases, but vector min/max with bitcasts can be transformed. If the
267 // one-use restrictions are eased for other patterns, we still don't want to
268 // obfuscate min/max.
269 if ((match(&SI, m_SMin(m_Value(), m_Value())) ||
270 match(&SI, m_SMax(m_Value(), m_Value())) ||
271 match(&SI, m_UMin(m_Value(), m_Value())) ||
272 match(&SI, m_UMax(m_Value(), m_Value()))))
273 return nullptr;
274
275 // If this is a cast from the same type, merge.
276 Value *Cond = SI.getCondition();
277 Type *CondTy = Cond->getType();
278 if (TI->getNumOperands() == 1 && TI->isCast()) {
279 Type *FIOpndTy = FI->getOperand(0)->getType();
280 if (TI->getOperand(0)->getType() != FIOpndTy)
281 return nullptr;
282
283 // The select condition may be a vector. We may only change the operand
284 // type if the vector width remains the same (and matches the condition).
285 if (auto *CondVTy = dyn_cast<VectorType>(CondTy)) {
286 if (!FIOpndTy->isVectorTy() ||
287 CondVTy->getElementCount() !=
288 cast<VectorType>(FIOpndTy)->getElementCount())
289 return nullptr;
290
291 // TODO: If the backend knew how to deal with casts better, we could
292 // remove this limitation. For now, there's too much potential to create
293 // worse codegen by promoting the select ahead of size-altering casts
294 // (PR28160).
295 //
296 // Note that ValueTracking's matchSelectPattern() looks through casts
297 // without checking 'hasOneUse' when it matches min/max patterns, so this
298 // transform may end up happening anyway.
299 if (TI->getOpcode() != Instruction::BitCast &&
300 (!TI->hasOneUse() || !FI->hasOneUse()))
301 return nullptr;
302 } else if (!TI->hasOneUse() || !FI->hasOneUse()) {
303 // TODO: The one-use restrictions for a scalar select could be eased if
304 // the fold of a select in visitLoadInst() was enhanced to match a pattern
305 // that includes a cast.
306 return nullptr;
307 }
308
309 // Fold this by inserting a select from the input values.
310 Value *NewSI =
312 SI.getName() + ".v", &SI);
314 TI->getType());
315 }
316
317 Value *OtherOpT, *OtherOpF;
318 bool MatchIsOpZero;
319 auto getCommonOp = [&](Instruction *TI, Instruction *FI, bool Commute,
320 bool Swapped = false) -> Value * {
321 assert(!(Commute && Swapped) &&
322 "Commute and Swapped can't set at the same time");
323 if (!Swapped) {
324 if (TI->getOperand(0) == FI->getOperand(0)) {
325 OtherOpT = TI->getOperand(1);
326 OtherOpF = FI->getOperand(1);
327 MatchIsOpZero = true;
328 return TI->getOperand(0);
329 } else if (TI->getOperand(1) == FI->getOperand(1)) {
330 OtherOpT = TI->getOperand(0);
331 OtherOpF = FI->getOperand(0);
332 MatchIsOpZero = false;
333 return TI->getOperand(1);
334 }
335 }
336
337 if (!Commute && !Swapped)
338 return nullptr;
339
340 // If we are allowing commute or swap of operands, then
341 // allow a cross-operand match. In that case, MatchIsOpZero
342 // means that TI's operand 0 (FI's operand 1) is the common op.
343 if (TI->getOperand(0) == FI->getOperand(1)) {
344 OtherOpT = TI->getOperand(1);
345 OtherOpF = FI->getOperand(0);
346 MatchIsOpZero = true;
347 return TI->getOperand(0);
348 } else if (TI->getOperand(1) == FI->getOperand(0)) {
349 OtherOpT = TI->getOperand(0);
350 OtherOpF = FI->getOperand(1);
351 MatchIsOpZero = false;
352 return TI->getOperand(1);
353 }
354 return nullptr;
355 };
356
357 if (TI->hasOneUse() || FI->hasOneUse()) {
358 // Cond ? -X : -Y --> -(Cond ? X : Y)
359 Value *X, *Y;
360 if (match(TI, m_FNeg(m_Value(X))) && match(FI, m_FNeg(m_Value(Y)))) {
361 // Intersect FMF from the fneg instructions and union those with the
362 // select.
364 FMF &= FI->getFastMathFlags();
365 FMF |= SI.getFastMathFlags();
366 Value *NewSel =
367 Builder.CreateSelect(Cond, X, Y, SI.getName() + ".v", &SI);
368 if (auto *NewSelI = dyn_cast<Instruction>(NewSel))
369 NewSelI->setFastMathFlags(FMF);
370 Instruction *NewFNeg = UnaryOperator::CreateFNeg(NewSel);
371 NewFNeg->setFastMathFlags(FMF);
372 return NewFNeg;
373 }
374
375 // Min/max intrinsic with a common operand can have the common operand
376 // pulled after the select. This is the same transform as below for binops,
377 // but specialized for intrinsic matching and without the restrictive uses
378 // clause.
379 auto *TII = dyn_cast<IntrinsicInst>(TI);
380 auto *FII = dyn_cast<IntrinsicInst>(FI);
381 if (TII && FII && TII->getIntrinsicID() == FII->getIntrinsicID()) {
382 if (match(TII, m_MaxOrMin(m_Value(), m_Value()))) {
383 if (Value *MatchOp = getCommonOp(TI, FI, true)) {
384 Value *NewSel =
385 Builder.CreateSelect(Cond, OtherOpT, OtherOpF, "minmaxop", &SI);
386 return CallInst::Create(TII->getCalledFunction(), {NewSel, MatchOp});
387 }
388 }
389 }
390
391 // icmp with a common operand also can have the common operand
392 // pulled after the select.
393 ICmpInst::Predicate TPred, FPred;
394 if (match(TI, m_ICmp(TPred, m_Value(), m_Value())) &&
395 match(FI, m_ICmp(FPred, m_Value(), m_Value()))) {
396 if (TPred == FPred || TPred == CmpInst::getSwappedPredicate(FPred)) {
397 bool Swapped = TPred != FPred;
398 if (Value *MatchOp =
399 getCommonOp(TI, FI, ICmpInst::isEquality(TPred), Swapped)) {
400 Value *NewSel = Builder.CreateSelect(Cond, OtherOpT, OtherOpF,
401 SI.getName() + ".v", &SI);
402 return new ICmpInst(
403 MatchIsOpZero ? TPred : CmpInst::getSwappedPredicate(TPred),
404 MatchOp, NewSel);
405 }
406 }
407 }
408 }
409
410 // Only handle binary operators (including two-operand getelementptr) with
411 // one-use here. As with the cast case above, it may be possible to relax the
412 // one-use constraint, but that needs be examined carefully since it may not
413 // reduce the total number of instructions.
414 if (TI->getNumOperands() != 2 || FI->getNumOperands() != 2 ||
415 !TI->isSameOperationAs(FI) ||
416 (!isa<BinaryOperator>(TI) && !isa<GetElementPtrInst>(TI)) ||
417 !TI->hasOneUse() || !FI->hasOneUse())
418 return nullptr;
419
420 // Figure out if the operations have any operands in common.
421 Value *MatchOp = getCommonOp(TI, FI, TI->isCommutative());
422 if (!MatchOp)
423 return nullptr;
424
425 // If the select condition is a vector, the operands of the original select's
426 // operands also must be vectors. This may not be the case for getelementptr
427 // for example.
428 if (CondTy->isVectorTy() && (!OtherOpT->getType()->isVectorTy() ||
429 !OtherOpF->getType()->isVectorTy()))
430 return nullptr;
431
432 // If we reach here, they do have operations in common.
433 Value *NewSI = Builder.CreateSelect(Cond, OtherOpT, OtherOpF,
434 SI.getName() + ".v", &SI);
435 Value *Op0 = MatchIsOpZero ? MatchOp : NewSI;
436 Value *Op1 = MatchIsOpZero ? NewSI : MatchOp;
437 if (auto *BO = dyn_cast<BinaryOperator>(TI)) {
438 BinaryOperator *NewBO = BinaryOperator::Create(BO->getOpcode(), Op0, Op1);
439 NewBO->copyIRFlags(TI);
440 NewBO->andIRFlags(FI);
441 return NewBO;
442 }
443 if (auto *TGEP = dyn_cast<GetElementPtrInst>(TI)) {
444 auto *FGEP = cast<GetElementPtrInst>(FI);
445 Type *ElementType = TGEP->getResultElementType();
446 return TGEP->isInBounds() && FGEP->isInBounds()
447 ? GetElementPtrInst::CreateInBounds(ElementType, Op0, {Op1})
448 : GetElementPtrInst::Create(ElementType, Op0, {Op1});
449 }
450 llvm_unreachable("Expected BinaryOperator or GEP");
451 return nullptr;
452}
453
454static bool isSelect01(const APInt &C1I, const APInt &C2I) {
455 if (!C1I.isZero() && !C2I.isZero()) // One side must be zero.
456 return false;
457 return C1I.isOne() || C1I.isAllOnes() || C2I.isOne() || C2I.isAllOnes();
458}
459
460/// Try to fold the select into one of the operands to allow further
461/// optimization.
463 Value *FalseVal) {
464 // See the comment above GetSelectFoldableOperands for a description of the
465 // transformation we are doing here.
466 auto TryFoldSelectIntoOp = [&](SelectInst &SI, Value *TrueVal,
467 Value *FalseVal,
468 bool Swapped) -> Instruction * {
469 auto *TVI = dyn_cast<BinaryOperator>(TrueVal);
470 if (!TVI || !TVI->hasOneUse() || isa<Constant>(FalseVal))
471 return nullptr;
472
473 unsigned SFO = getSelectFoldableOperands(TVI);
474 unsigned OpToFold = 0;
475 if ((SFO & 1) && FalseVal == TVI->getOperand(0))
476 OpToFold = 1;
477 else if ((SFO & 2) && FalseVal == TVI->getOperand(1))
478 OpToFold = 2;
479
480 if (!OpToFold)
481 return nullptr;
482
483 // TODO: We probably ought to revisit cases where the select and FP
484 // instructions have different flags and add tests to ensure the
485 // behaviour is correct.
486 FastMathFlags FMF;
487 if (isa<FPMathOperator>(&SI))
488 FMF = SI.getFastMathFlags();
490 TVI->getOpcode(), TVI->getType(), true, FMF.noSignedZeros());
491 Value *OOp = TVI->getOperand(2 - OpToFold);
492 // Avoid creating select between 2 constants unless it's selecting
493 // between 0, 1 and -1.
494 const APInt *OOpC;
495 bool OOpIsAPInt = match(OOp, m_APInt(OOpC));
496 if (!isa<Constant>(OOp) ||
497 (OOpIsAPInt && isSelect01(C->getUniqueInteger(), *OOpC))) {
498 Value *NewSel = Builder.CreateSelect(SI.getCondition(), Swapped ? C : OOp,
499 Swapped ? OOp : C);
500 if (isa<FPMathOperator>(&SI))
501 cast<Instruction>(NewSel)->setFastMathFlags(FMF);
502 NewSel->takeName(TVI);
503 BinaryOperator *BO =
504 BinaryOperator::Create(TVI->getOpcode(), FalseVal, NewSel);
505 BO->copyIRFlags(TVI);
506 return BO;
507 }
508 return nullptr;
509 };
510
511 if (Instruction *R = TryFoldSelectIntoOp(SI, TrueVal, FalseVal, false))
512 return R;
513
514 if (Instruction *R = TryFoldSelectIntoOp(SI, FalseVal, TrueVal, true))
515 return R;
516
517 return nullptr;
518}
519
520/// We want to turn:
521/// (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1)
522/// into:
523/// zext (icmp ne i32 (and X, (or Y, (shl 1, Z))), 0)
524/// Note:
525/// Z may be 0 if lshr is missing.
526/// Worst-case scenario is that we will replace 5 instructions with 5 different
527/// instructions, but we got rid of select.
528static Instruction *foldSelectICmpAndAnd(Type *SelType, const ICmpInst *Cmp,
529 Value *TVal, Value *FVal,
530 InstCombiner::BuilderTy &Builder) {
531 if (!(Cmp->hasOneUse() && Cmp->getOperand(0)->hasOneUse() &&
532 Cmp->getPredicate() == ICmpInst::ICMP_EQ &&
533 match(Cmp->getOperand(1), m_Zero()) && match(FVal, m_One())))
534 return nullptr;
535
536 // The TrueVal has general form of: and %B, 1
537 Value *B;
538 if (!match(TVal, m_OneUse(m_And(m_Value(B), m_One()))))
539 return nullptr;
540
541 // Where %B may be optionally shifted: lshr %X, %Z.
542 Value *X, *Z;
543 const bool HasShift = match(B, m_OneUse(m_LShr(m_Value(X), m_Value(Z))));
544
545 // The shift must be valid.
546 // TODO: This restricts the fold to constant shift amounts. Is there a way to
547 // handle variable shifts safely? PR47012
548 if (HasShift &&
550 APInt(SelType->getScalarSizeInBits(),
551 SelType->getScalarSizeInBits()))))
552 return nullptr;
553
554 if (!HasShift)
555 X = B;
556
557 Value *Y;
558 if (!match(Cmp->getOperand(0), m_c_And(m_Specific(X), m_Value(Y))))
559 return nullptr;
560
561 // ((X & Y) == 0) ? ((X >> Z) & 1) : 1 --> (X & (Y | (1 << Z))) != 0
562 // ((X & Y) == 0) ? (X & 1) : 1 --> (X & (Y | 1)) != 0
563 Constant *One = ConstantInt::get(SelType, 1);
564 Value *MaskB = HasShift ? Builder.CreateShl(One, Z) : One;
565 Value *FullMask = Builder.CreateOr(Y, MaskB);
566 Value *MaskedX = Builder.CreateAnd(X, FullMask);
567 Value *ICmpNeZero = Builder.CreateIsNotNull(MaskedX);
568 return new ZExtInst(ICmpNeZero, SelType);
569}
570
571/// We want to turn:
572/// (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1
573/// (select (icmp slt x, C), ashr (X, Y), lshr (X, Y)); iff C s>= 0
574/// into:
575/// ashr (X, Y)
576static Value *foldSelectICmpLshrAshr(const ICmpInst *IC, Value *TrueVal,
577 Value *FalseVal,
578 InstCombiner::BuilderTy &Builder) {
580 Value *CmpLHS = IC->getOperand(0);
581 Value *CmpRHS = IC->getOperand(1);
582 if (!CmpRHS->getType()->isIntOrIntVectorTy())
583 return nullptr;
584
585 Value *X, *Y;
586 unsigned Bitwidth = CmpRHS->getType()->getScalarSizeInBits();
587 if ((Pred != ICmpInst::ICMP_SGT ||
588 !match(CmpRHS,
589 m_SpecificInt_ICMP(ICmpInst::ICMP_SGE, APInt(Bitwidth, -1)))) &&
590 (Pred != ICmpInst::ICMP_SLT ||
591 !match(CmpRHS,
593 return nullptr;
594
595 // Canonicalize so that ashr is in FalseVal.
596 if (Pred == ICmpInst::ICMP_SLT)
597 std::swap(TrueVal, FalseVal);
598
599 if (match(TrueVal, m_LShr(m_Value(X), m_Value(Y))) &&
600 match(FalseVal, m_AShr(m_Specific(X), m_Specific(Y))) &&
601 match(CmpLHS, m_Specific(X))) {
602 const auto *Ashr = cast<Instruction>(FalseVal);
603 // if lshr is not exact and ashr is, this new ashr must not be exact.
604 bool IsExact = Ashr->isExact() && cast<Instruction>(TrueVal)->isExact();
605 return Builder.CreateAShr(X, Y, IC->getName(), IsExact);
606 }
607
608 return nullptr;
609}
610
611/// We want to turn:
612/// (select (icmp eq (and X, C1), 0), Y, (or Y, C2))
613/// into:
614/// (or (shl (and X, C1), C3), Y)
615/// iff:
616/// C1 and C2 are both powers of 2
617/// where:
618/// C3 = Log(C2) - Log(C1)
619///
620/// This transform handles cases where:
621/// 1. The icmp predicate is inverted
622/// 2. The select operands are reversed
623/// 3. The magnitude of C2 and C1 are flipped
624static Value *foldSelectICmpAndOr(const ICmpInst *IC, Value *TrueVal,
625 Value *FalseVal,
626 InstCombiner::BuilderTy &Builder) {
627 // Only handle integer compares. Also, if this is a vector select, we need a
628 // vector compare.
629 if (!TrueVal->getType()->isIntOrIntVectorTy() ||
630 TrueVal->getType()->isVectorTy() != IC->getType()->isVectorTy())
631 return nullptr;
632
633 Value *CmpLHS = IC->getOperand(0);
634 Value *CmpRHS = IC->getOperand(1);
635
636 Value *V;
637 unsigned C1Log;
638 bool IsEqualZero;
639 bool NeedAnd = false;
640 if (IC->isEquality()) {
641 if (!match(CmpRHS, m_Zero()))
642 return nullptr;
643
644 const APInt *C1;
645 if (!match(CmpLHS, m_And(m_Value(), m_Power2(C1))))
646 return nullptr;
647
648 V = CmpLHS;
649 C1Log = C1->logBase2();
650 IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_EQ;
651 } else if (IC->getPredicate() == ICmpInst::ICMP_SLT ||
653 // We also need to recognize (icmp slt (trunc (X)), 0) and
654 // (icmp sgt (trunc (X)), -1).
655 IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_SGT;
656 if ((IsEqualZero && !match(CmpRHS, m_AllOnes())) ||
657 (!IsEqualZero && !match(CmpRHS, m_Zero())))
658 return nullptr;
659
660 if (!match(CmpLHS, m_OneUse(m_Trunc(m_Value(V)))))
661 return nullptr;
662
663 C1Log = CmpLHS->getType()->getScalarSizeInBits() - 1;
664 NeedAnd = true;
665 } else {
666 return nullptr;
667 }
668
669 const APInt *C2;
670 bool OrOnTrueVal = false;
671 bool OrOnFalseVal = match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2)));
672 if (!OrOnFalseVal)
673 OrOnTrueVal = match(TrueVal, m_Or(m_Specific(FalseVal), m_Power2(C2)));
674
675 if (!OrOnFalseVal && !OrOnTrueVal)
676 return nullptr;
677
678 Value *Y = OrOnFalseVal ? TrueVal : FalseVal;
679
680 unsigned C2Log = C2->logBase2();
681
682 bool NeedXor = (!IsEqualZero && OrOnFalseVal) || (IsEqualZero && OrOnTrueVal);
683 bool NeedShift = C1Log != C2Log;
684 bool NeedZExtTrunc = Y->getType()->getScalarSizeInBits() !=
686
687 // Make sure we don't create more instructions than we save.
688 Value *Or = OrOnFalseVal ? FalseVal : TrueVal;
689 if ((NeedShift + NeedXor + NeedZExtTrunc) >
690 (IC->hasOneUse() + Or->hasOneUse()))
691 return nullptr;
692
693 if (NeedAnd) {
694 // Insert the AND instruction on the input to the truncate.
696 V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), C1));
697 }
698
699 if (C2Log > C1Log) {
700 V = Builder.CreateZExtOrTrunc(V, Y->getType());
701 V = Builder.CreateShl(V, C2Log - C1Log);
702 } else if (C1Log > C2Log) {
703 V = Builder.CreateLShr(V, C1Log - C2Log);
704 V = Builder.CreateZExtOrTrunc(V, Y->getType());
705 } else
706 V = Builder.CreateZExtOrTrunc(V, Y->getType());
707
708 if (NeedXor)
709 V = Builder.CreateXor(V, *C2);
710
711 return Builder.CreateOr(V, Y);
712}
713
714/// Canonicalize a set or clear of a masked set of constant bits to
715/// select-of-constants form.
717 InstCombiner::BuilderTy &Builder) {
718 Value *Cond = Sel.getCondition();
719 Value *T = Sel.getTrueValue();
720 Value *F = Sel.getFalseValue();
721 Type *Ty = Sel.getType();
722 Value *X;
723 const APInt *NotC, *C;
724
725 // Cond ? (X & ~C) : (X | C) --> (X & ~C) | (Cond ? 0 : C)
726 if (match(T, m_And(m_Value(X), m_APInt(NotC))) &&
727 match(F, m_OneUse(m_Or(m_Specific(X), m_APInt(C)))) && *NotC == ~(*C)) {
729 Constant *OrC = ConstantInt::get(Ty, *C);
730 Value *NewSel = Builder.CreateSelect(Cond, Zero, OrC, "masksel", &Sel);
731 return BinaryOperator::CreateOr(T, NewSel);
732 }
733
734 // Cond ? (X | C) : (X & ~C) --> (X & ~C) | (Cond ? C : 0)
735 if (match(F, m_And(m_Value(X), m_APInt(NotC))) &&
736 match(T, m_OneUse(m_Or(m_Specific(X), m_APInt(C)))) && *NotC == ~(*C)) {
738 Constant *OrC = ConstantInt::get(Ty, *C);
739 Value *NewSel = Builder.CreateSelect(Cond, OrC, Zero, "masksel", &Sel);
740 return BinaryOperator::CreateOr(F, NewSel);
741 }
742
743 return nullptr;
744}
745
746// select (x == 0), 0, x * y --> freeze(y) * x
747// select (y == 0), 0, x * y --> freeze(x) * y
748// select (x == 0), undef, x * y --> freeze(y) * x
749// select (x == undef), 0, x * y --> freeze(y) * x
750// Usage of mul instead of 0 will make the result more poisonous,
751// so the operand that was not checked in the condition should be frozen.
752// The latter folding is applied only when a constant compared with x is
753// is a vector consisting of 0 and undefs. If a constant compared with x
754// is a scalar undefined value or undefined vector then an expression
755// should be already folded into a constant.
757 auto *CondVal = SI.getCondition();
758 auto *TrueVal = SI.getTrueValue();
759 auto *FalseVal = SI.getFalseValue();
760 Value *X, *Y;
761 ICmpInst::Predicate Predicate;
762
763 // Assuming that constant compared with zero is not undef (but it may be
764 // a vector with some undef elements). Otherwise (when a constant is undef)
765 // the select expression should be already simplified.
766 if (!match(CondVal, m_ICmp(Predicate, m_Value(X), m_Zero())) ||
767 !ICmpInst::isEquality(Predicate))
768 return nullptr;
769
770 if (Predicate == ICmpInst::ICMP_NE)
771 std::swap(TrueVal, FalseVal);
772
773 // Check that TrueVal is a constant instead of matching it with m_Zero()
774 // to handle the case when it is a scalar undef value or a vector containing
775 // non-zero elements that are masked by undef elements in the compare
776 // constant.
777 auto *TrueValC = dyn_cast<Constant>(TrueVal);
778 if (TrueValC == nullptr ||
779 !match(FalseVal, m_c_Mul(m_Specific(X), m_Value(Y))) ||
780 !isa<Instruction>(FalseVal))
781 return nullptr;
782
783 auto *ZeroC = cast<Constant>(cast<Instruction>(CondVal)->getOperand(1));
784 auto *MergedC = Constant::mergeUndefsWith(TrueValC, ZeroC);
785 // If X is compared with 0 then TrueVal could be either zero or undef.
786 // m_Zero match vectors containing some undef elements, but for scalars
787 // m_Undef should be used explicitly.
788 if (!match(MergedC, m_Zero()) && !match(MergedC, m_Undef()))
789 return nullptr;
790
791 auto *FalseValI = cast<Instruction>(FalseVal);
792 auto *FrY = IC.InsertNewInstBefore(new FreezeInst(Y, Y->getName() + ".fr"),
793 *FalseValI);
794 IC.replaceOperand(*FalseValI, FalseValI->getOperand(0) == Y ? 0 : 1, FrY);
795 return IC.replaceInstUsesWith(SI, FalseValI);
796}
797
798/// Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b).
799/// There are 8 commuted/swapped variants of this pattern.
800/// TODO: Also support a - UMIN(a,b) patterns.
802 const Value *TrueVal,
803 const Value *FalseVal,
804 InstCombiner::BuilderTy &Builder) {
805 ICmpInst::Predicate Pred = ICI->getPredicate();
806 Value *A = ICI->getOperand(0);
807 Value *B = ICI->getOperand(1);
808
809 // (b > a) ? 0 : a - b -> (b <= a) ? a - b : 0
810 // (a == 0) ? 0 : a - 1 -> (a != 0) ? a - 1 : 0
811 if (match(TrueVal, m_Zero())) {
813 std::swap(TrueVal, FalseVal);
814 }
815
816 if (!match(FalseVal, m_Zero()))
817 return nullptr;
818
819 // ugt 0 is canonicalized to ne 0 and requires special handling
820 // (a != 0) ? a + -1 : 0 -> usub.sat(a, 1)
821 if (Pred == ICmpInst::ICMP_NE) {
822 if (match(B, m_Zero()) && match(TrueVal, m_Add(m_Specific(A), m_AllOnes())))
823 return Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, A,
824 ConstantInt::get(A->getType(), 1));
825 return nullptr;
826 }
827
828 if (!ICmpInst::isUnsigned(Pred))
829 return nullptr;
830
831 if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_ULT) {
832 // (b < a) ? a - b : 0 -> (a > b) ? a - b : 0
833 std::swap(A, B);
835 }
836
837 assert((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_UGT) &&
838 "Unexpected isUnsigned predicate!");
839
840 // Ensure the sub is of the form:
841 // (a > b) ? a - b : 0 -> usub.sat(a, b)
842 // (a > b) ? b - a : 0 -> -usub.sat(a, b)
843 // Checking for both a-b and a+(-b) as a constant.
844 bool IsNegative = false;
845 const APInt *C;
846 if (match(TrueVal, m_Sub(m_Specific(B), m_Specific(A))) ||
847 (match(A, m_APInt(C)) &&
848 match(TrueVal, m_Add(m_Specific(B), m_SpecificInt(-*C)))))
849 IsNegative = true;
850 else if (!match(TrueVal, m_Sub(m_Specific(A), m_Specific(B))) &&
851 !(match(B, m_APInt(C)) &&
852 match(TrueVal, m_Add(m_Specific(A), m_SpecificInt(-*C)))))
853 return nullptr;
854
855 // If we are adding a negate and the sub and icmp are used anywhere else, we
856 // would end up with more instructions.
857 if (IsNegative && !TrueVal->hasOneUse() && !ICI->hasOneUse())
858 return nullptr;
859
860 // (a > b) ? a - b : 0 -> usub.sat(a, b)
861 // (a > b) ? b - a : 0 -> -usub.sat(a, b)
862 Value *Result = Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, A, B);
863 if (IsNegative)
864 Result = Builder.CreateNeg(Result);
865 return Result;
866}
867
869 InstCombiner::BuilderTy &Builder) {
870 if (!Cmp->hasOneUse())
871 return nullptr;
872
873 // Match unsigned saturated add with constant.
874 Value *Cmp0 = Cmp->getOperand(0);
875 Value *Cmp1 = Cmp->getOperand(1);
876 ICmpInst::Predicate Pred = Cmp->getPredicate();
877 Value *X;
878 const APInt *C, *CmpC;
879 if (Pred == ICmpInst::ICMP_ULT &&
880 match(TVal, m_Add(m_Value(X), m_APInt(C))) && X == Cmp0 &&
881 match(FVal, m_AllOnes()) && match(Cmp1, m_APInt(CmpC)) && *CmpC == ~*C) {
882 // (X u< ~C) ? (X + C) : -1 --> uadd.sat(X, C)
883 return Builder.CreateBinaryIntrinsic(
884 Intrinsic::uadd_sat, X, ConstantInt::get(X->getType(), *C));
885 }
886
887 // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
888 // There are 8 commuted variants.
889 // Canonicalize -1 (saturated result) to true value of the select.
890 if (match(FVal, m_AllOnes())) {
891 std::swap(TVal, FVal);
892 Pred = CmpInst::getInversePredicate(Pred);
893 }
894 if (!match(TVal, m_AllOnes()))
895 return nullptr;
896
897 // Canonicalize predicate to less-than or less-or-equal-than.
898 if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) {
899 std::swap(Cmp0, Cmp1);
900 Pred = CmpInst::getSwappedPredicate(Pred);
901 }
902 if (Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_ULE)
903 return nullptr;
904
905 // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
906 // Strictness of the comparison is irrelevant.
907 Value *Y;
908 if (match(Cmp0, m_Not(m_Value(X))) &&
909 match(FVal, m_c_Add(m_Specific(X), m_Value(Y))) && Y == Cmp1) {
910 // (~X u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
911 // (~X u< Y) ? -1 : (Y + X) --> uadd.sat(X, Y)
912 return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, X, Y);
913 }
914 // The 'not' op may be included in the sum but not the compare.
915 // Strictness of the comparison is irrelevant.
916 X = Cmp0;
917 Y = Cmp1;
918 if (match(FVal, m_c_Add(m_Not(m_Specific(X)), m_Specific(Y)))) {
919 // (X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y)
920 // (X u< Y) ? -1 : (Y + ~X) --> uadd.sat(Y, ~X)
921 BinaryOperator *BO = cast<BinaryOperator>(FVal);
922 return Builder.CreateBinaryIntrinsic(
923 Intrinsic::uadd_sat, BO->getOperand(0), BO->getOperand(1));
924 }
925 // The overflow may be detected via the add wrapping round.
926 // This is only valid for strict comparison!
927 if (Pred == ICmpInst::ICMP_ULT &&
928 match(Cmp0, m_c_Add(m_Specific(Cmp1), m_Value(Y))) &&
929 match(FVal, m_c_Add(m_Specific(Cmp1), m_Specific(Y)))) {
930 // ((X + Y) u< X) ? -1 : (X + Y) --> uadd.sat(X, Y)
931 // ((X + Y) u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
932 return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, Cmp1, Y);
933 }
934
935 return nullptr;
936}
937
938/// Fold the following code sequence:
939/// \code
940/// int a = ctlz(x & -x);
941// x ? 31 - a : a;
942/// \code
943///
944/// into:
945/// cttz(x)
946static Instruction *foldSelectCtlzToCttz(ICmpInst *ICI, Value *TrueVal,
947 Value *FalseVal,
948 InstCombiner::BuilderTy &Builder) {
949 unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits();
950 if (!ICI->isEquality() || !match(ICI->getOperand(1), m_Zero()))
951 return nullptr;
952
953 if (ICI->getPredicate() == ICmpInst::ICMP_NE)
954 std::swap(TrueVal, FalseVal);
955
956 if (!match(FalseVal,
957 m_Xor(m_Deferred(TrueVal), m_SpecificInt(BitWidth - 1))))
958 return nullptr;
959
960 if (!match(TrueVal, m_Intrinsic<Intrinsic::ctlz>()))
961 return nullptr;
962
963 Value *X = ICI->getOperand(0);
964 auto *II = cast<IntrinsicInst>(TrueVal);
965 if (!match(II->getOperand(0), m_c_And(m_Specific(X), m_Neg(m_Specific(X)))))
966 return nullptr;
967
968 Function *F = Intrinsic::getDeclaration(II->getModule(), Intrinsic::cttz,
969 II->getType());
970 return CallInst::Create(F, {X, II->getArgOperand(1)});
971}
972
973/// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single
974/// call to cttz/ctlz with flag 'is_zero_poison' cleared.
975///
976/// For example, we can fold the following code sequence:
977/// \code
978/// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
979/// %1 = icmp ne i32 %x, 0
980/// %2 = select i1 %1, i32 %0, i32 32
981/// \code
982///
983/// into:
984/// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
985static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal,
986 InstCombiner::BuilderTy &Builder) {
987 ICmpInst::Predicate Pred = ICI->getPredicate();
988 Value *CmpLHS = ICI->getOperand(0);
989 Value *CmpRHS = ICI->getOperand(1);
990
991 // Check if the select condition compares a value for equality.
992 if (!ICI->isEquality())
993 return nullptr;
994
995 Value *SelectArg = FalseVal;
996 Value *ValueOnZero = TrueVal;
997 if (Pred == ICmpInst::ICMP_NE)
998 std::swap(SelectArg, ValueOnZero);
999
1000 // Skip zero extend/truncate.
1001 Value *Count = nullptr;
1002 if (!match(SelectArg, m_ZExt(m_Value(Count))) &&
1003 !match(SelectArg, m_Trunc(m_Value(Count))))
1004 Count = SelectArg;
1005
1006 // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the
1007 // input to the cttz/ctlz is used as LHS for the compare instruction.
1008 Value *X;
1009 if (!match(Count, m_Intrinsic<Intrinsic::cttz>(m_Value(X))) &&
1010 !match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Value(X))))
1011 return nullptr;
1012
1013 // (X == 0) ? BitWidth : ctz(X)
1014 // (X == -1) ? BitWidth : ctz(~X)
1015 if ((X != CmpLHS || !match(CmpRHS, m_Zero())) &&
1016 (!match(X, m_Not(m_Specific(CmpLHS))) || !match(CmpRHS, m_AllOnes())))
1017 return nullptr;
1018
1019 IntrinsicInst *II = cast<IntrinsicInst>(Count);
1020
1021 // Check if the value propagated on zero is a constant number equal to the
1022 // sizeof in bits of 'Count'.
1023 unsigned SizeOfInBits = Count->getType()->getScalarSizeInBits();
1024 if (match(ValueOnZero, m_SpecificInt(SizeOfInBits))) {
1025 // Explicitly clear the 'is_zero_poison' flag. It's always valid to go from
1026 // true to false on this flag, so we can replace it for all users.
1028 return SelectArg;
1029 }
1030
1031 // The ValueOnZero is not the bitwidth. But if the cttz/ctlz (and optional
1032 // zext/trunc) have one use (ending at the select), the cttz/ctlz result will
1033 // not be used if the input is zero. Relax to 'zero is poison' for that case.
1034 if (II->hasOneUse() && SelectArg->hasOneUse() &&
1035 !match(II->getArgOperand(1), m_One()))
1037
1038 return nullptr;
1039}
1040
1041/// Return true if we find and adjust an icmp+select pattern where the compare
1042/// is with a constant that can be incremented or decremented to match the
1043/// minimum or maximum idiom.
1044static bool adjustMinMax(SelectInst &Sel, ICmpInst &Cmp) {
1045 ICmpInst::Predicate Pred = Cmp.getPredicate();
1046 Value *CmpLHS = Cmp.getOperand(0);
1047 Value *CmpRHS = Cmp.getOperand(1);
1048 Value *TrueVal = Sel.getTrueValue();
1049 Value *FalseVal = Sel.getFalseValue();
1050
1051 // We may move or edit the compare, so make sure the select is the only user.
1052 const APInt *CmpC;
1053 if (!Cmp.hasOneUse() || !match(CmpRHS, m_APInt(CmpC)))
1054 return false;
1055
1056 // These transforms only work for selects of integers or vector selects of
1057 // integer vectors.
1058 Type *SelTy = Sel.getType();
1059 auto *SelEltTy = dyn_cast<IntegerType>(SelTy->getScalarType());
1060 if (!SelEltTy || SelTy->isVectorTy() != Cmp.getType()->isVectorTy())
1061 return false;
1062
1063 Constant *AdjustedRHS;
1064 if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_SGT)
1065 AdjustedRHS = ConstantInt::get(CmpRHS->getType(), *CmpC + 1);
1066 else if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_SLT)
1067 AdjustedRHS = ConstantInt::get(CmpRHS->getType(), *CmpC - 1);
1068 else
1069 return false;
1070
1071 // X > C ? X : C+1 --> X < C+1 ? C+1 : X
1072 // X < C ? X : C-1 --> X > C-1 ? C-1 : X
1073 if ((CmpLHS == TrueVal && AdjustedRHS == FalseVal) ||
1074 (CmpLHS == FalseVal && AdjustedRHS == TrueVal)) {
1075 ; // Nothing to do here. Values match without any sign/zero extension.
1076 }
1077 // Types do not match. Instead of calculating this with mixed types, promote
1078 // all to the larger type. This enables scalar evolution to analyze this
1079 // expression.
1080 else if (CmpRHS->getType()->getScalarSizeInBits() < SelEltTy->getBitWidth()) {
1081 Constant *SextRHS = ConstantExpr::getSExt(AdjustedRHS, SelTy);
1082
1083 // X = sext x; x >s c ? X : C+1 --> X = sext x; X <s C+1 ? C+1 : X
1084 // X = sext x; x <s c ? X : C-1 --> X = sext x; X >s C-1 ? C-1 : X
1085 // X = sext x; x >u c ? X : C+1 --> X = sext x; X <u C+1 ? C+1 : X
1086 // X = sext x; x <u c ? X : C-1 --> X = sext x; X >u C-1 ? C-1 : X
1087 if (match(TrueVal, m_SExt(m_Specific(CmpLHS))) && SextRHS == FalseVal) {
1088 CmpLHS = TrueVal;
1089 AdjustedRHS = SextRHS;
1090 } else if (match(FalseVal, m_SExt(m_Specific(CmpLHS))) &&
1091 SextRHS == TrueVal) {
1092 CmpLHS = FalseVal;
1093 AdjustedRHS = SextRHS;
1094 } else if (Cmp.isUnsigned()) {
1095 Constant *ZextRHS = ConstantExpr::getZExt(AdjustedRHS, SelTy);
1096 // X = zext x; x >u c ? X : C+1 --> X = zext x; X <u C+1 ? C+1 : X
1097 // X = zext x; x <u c ? X : C-1 --> X = zext x; X >u C-1 ? C-1 : X
1098 // zext + signed compare cannot be changed:
1099 // 0xff <s 0x00, but 0x00ff >s 0x0000
1100 if (match(TrueVal, m_ZExt(m_Specific(CmpLHS))) && ZextRHS == FalseVal) {
1101 CmpLHS = TrueVal;
1102 AdjustedRHS = ZextRHS;
1103 } else if (match(FalseVal, m_ZExt(m_Specific(CmpLHS))) &&
1104 ZextRHS == TrueVal) {
1105 CmpLHS = FalseVal;
1106 AdjustedRHS = ZextRHS;
1107 } else {
1108 return false;
1109 }
1110 } else {
1111 return false;
1112 }
1113 } else {
1114 return false;
1115 }
1116
1117 Pred = ICmpInst::getSwappedPredicate(Pred);
1118 CmpRHS = AdjustedRHS;
1119 std::swap(FalseVal, TrueVal);
1120 Cmp.setPredicate(Pred);
1121 Cmp.setOperand(0, CmpLHS);
1122 Cmp.setOperand(1, CmpRHS);
1123 Sel.setOperand(1, TrueVal);
1124 Sel.setOperand(2, FalseVal);
1125 Sel.swapProfMetadata();
1126
1127 // Move the compare instruction right before the select instruction. Otherwise
1128 // the sext/zext value may be defined after the compare instruction uses it.
1129 Cmp.moveBefore(&Sel);
1130
1131 return true;
1132}
1133
1134static Instruction *canonicalizeSPF(SelectInst &Sel, ICmpInst &Cmp,
1135 InstCombinerImpl &IC) {
1136 Value *LHS, *RHS;
1137 // TODO: What to do with pointer min/max patterns?
1138 if (!Sel.getType()->isIntOrIntVectorTy())
1139 return nullptr;
1140
1141 SelectPatternFlavor SPF = matchSelectPattern(&Sel, LHS, RHS).Flavor;
1142 if (SPF == SelectPatternFlavor::SPF_ABS ||
1144 if (!Cmp.hasOneUse() && !RHS->hasOneUse())
1145 return nullptr; // TODO: Relax this restriction.
1146
1147 // Note that NSW flag can only be propagated for normal, non-negated abs!
1148 bool IntMinIsPoison = SPF == SelectPatternFlavor::SPF_ABS &&
1149 match(RHS, m_NSWNeg(m_Specific(LHS)));
1150 Constant *IntMinIsPoisonC =
1151 ConstantInt::get(Type::getInt1Ty(Sel.getContext()), IntMinIsPoison);
1152 Instruction *Abs =
1153 IC.Builder.CreateBinaryIntrinsic(Intrinsic::abs, LHS, IntMinIsPoisonC);
1154
1156 return BinaryOperator::CreateNeg(Abs); // Always without NSW flag!
1157 return IC.replaceInstUsesWith(Sel, Abs);
1158 }
1159
1161 Intrinsic::ID IntrinsicID;
1162 switch (SPF) {
1164 IntrinsicID = Intrinsic::umin;
1165 break;
1167 IntrinsicID = Intrinsic::umax;
1168 break;
1170 IntrinsicID = Intrinsic::smin;
1171 break;
1173 IntrinsicID = Intrinsic::smax;
1174 break;
1175 default:
1176 llvm_unreachable("Unexpected SPF");
1177 }
1178 return IC.replaceInstUsesWith(
1179 Sel, IC.Builder.CreateBinaryIntrinsic(IntrinsicID, LHS, RHS));
1180 }
1181
1182 return nullptr;
1183}
1184
1185static bool replaceInInstruction(Value *V, Value *Old, Value *New,
1186 InstCombiner &IC, unsigned Depth = 0) {
1187 // Conservatively limit replacement to two instructions upwards.
1188 if (Depth == 2)
1189 return false;
1190
1191 auto *I = dyn_cast<Instruction>(V);
1192 if (!I || !I->hasOneUse() || !isSafeToSpeculativelyExecute(I))
1193 return false;
1194
1195 bool Changed = false;
1196 for (Use &U : I->operands()) {
1197 if (U == Old) {
1198 IC.replaceUse(U, New);
1199 Changed = true;
1200 } else {
1201 Changed |= replaceInInstruction(U, Old, New, IC, Depth + 1);
1202 }
1203 }
1204 return Changed;
1205}
1206
1207/// If we have a select with an equality comparison, then we know the value in
1208/// one of the arms of the select. See if substituting this value into an arm
1209/// and simplifying the result yields the same value as the other arm.
1210///
1211/// To make this transform safe, we must drop poison-generating flags
1212/// (nsw, etc) if we simplified to a binop because the select may be guarding
1213/// that poison from propagating. If the existing binop already had no
1214/// poison-generating flags, then this transform can be done by instsimplify.
1215///
1216/// Consider:
1217/// %cmp = icmp eq i32 %x, 2147483647
1218/// %add = add nsw i32 %x, 1
1219/// %sel = select i1 %cmp, i32 -2147483648, i32 %add
1220///
1221/// We can't replace %sel with %add unless we strip away the flags.
1222/// TODO: Wrapping flags could be preserved in some cases with better analysis.
1224 ICmpInst &Cmp) {
1225 if (!Cmp.isEquality())
1226 return nullptr;
1227
1228 // Canonicalize the pattern to ICMP_EQ by swapping the select operands.
1229 Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
1230 bool Swapped = false;
1231 if (Cmp.getPredicate() == ICmpInst::ICMP_NE) {
1232 std::swap(TrueVal, FalseVal);
1233 Swapped = true;
1234 }
1235
1236 // In X == Y ? f(X) : Z, try to evaluate f(Y) and replace the operand.
1237 // Make sure Y cannot be undef though, as we might pick different values for
1238 // undef in the icmp and in f(Y). Additionally, take care to avoid replacing
1239 // X == Y ? X : Z with X == Y ? Y : Z, as that would lead to an infinite
1240 // replacement cycle.
1241 Value *CmpLHS = Cmp.getOperand(0), *CmpRHS = Cmp.getOperand(1);
1242 if (TrueVal != CmpLHS &&
1243 isGuaranteedNotToBeUndefOrPoison(CmpRHS, SQ.AC, &Sel, &DT)) {
1244 if (Value *V = simplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, SQ,
1245 /* AllowRefinement */ true))
1246 return replaceOperand(Sel, Swapped ? 2 : 1, V);
1247
1248 // Even if TrueVal does not simplify, we can directly replace a use of
1249 // CmpLHS with CmpRHS, as long as the instruction is not used anywhere
1250 // else and is safe to speculatively execute (we may end up executing it
1251 // with different operands, which should not cause side-effects or trigger
1252 // undefined behavior). Only do this if CmpRHS is a constant, as
1253 // profitability is not clear for other cases.
1254 // FIXME: Support vectors.
1255 if (match(CmpRHS, m_ImmConstant()) && !match(CmpLHS, m_ImmConstant()) &&
1256 !Cmp.getType()->isVectorTy())
1257 if (replaceInInstruction(TrueVal, CmpLHS, CmpRHS, *this))
1258 return &Sel;
1259 }
1260 if (TrueVal != CmpRHS &&
1261 isGuaranteedNotToBeUndefOrPoison(CmpLHS, SQ.AC, &Sel, &DT))
1262 if (Value *V = simplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, SQ,
1263 /* AllowRefinement */ true))
1264 return replaceOperand(Sel, Swapped ? 2 : 1, V);
1265
1266 auto *FalseInst = dyn_cast<Instruction>(FalseVal);
1267 if (!FalseInst)
1268 return nullptr;
1269
1270 // InstSimplify already performed this fold if it was possible subject to
1271 // current poison-generating flags. Try the transform again with
1272 // poison-generating flags temporarily dropped.
1273 bool WasNUW = false, WasNSW = false, WasExact = false, WasInBounds = false;
1274 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(FalseVal)) {
1275 WasNUW = OBO->hasNoUnsignedWrap();
1276 WasNSW = OBO->hasNoSignedWrap();
1277 FalseInst->setHasNoUnsignedWrap(false);
1278 FalseInst->setHasNoSignedWrap(false);
1279 }
1280 if (auto *PEO = dyn_cast<PossiblyExactOperator>(FalseVal)) {
1281 WasExact = PEO->isExact();
1282 FalseInst->setIsExact(false);
1283 }
1284 if (auto *GEP = dyn_cast<GetElementPtrInst>(FalseVal)) {
1285 WasInBounds = GEP->isInBounds();
1286 GEP->setIsInBounds(false);
1287 }
1288
1289 // Try each equivalence substitution possibility.
1290 // We have an 'EQ' comparison, so the select's false value will propagate.
1291 // Example:
1292 // (X == 42) ? 43 : (X + 1) --> (X == 42) ? (X + 1) : (X + 1) --> X + 1
1293 if (simplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, SQ,
1294 /* AllowRefinement */ false) == TrueVal ||
1295 simplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, SQ,
1296 /* AllowRefinement */ false) == TrueVal) {
1297 return replaceInstUsesWith(Sel, FalseVal);
1298 }
1299
1300 // Restore poison-generating flags if the transform did not apply.
1301 if (WasNUW)
1302 FalseInst->setHasNoUnsignedWrap();
1303 if (WasNSW)
1304 FalseInst->setHasNoSignedWrap();
1305 if (WasExact)
1306 FalseInst->setIsExact();
1307 if (WasInBounds)
1308 cast<GetElementPtrInst>(FalseInst)->setIsInBounds();
1309
1310 return nullptr;
1311}
1312
1313// See if this is a pattern like:
1314// %old_cmp1 = icmp slt i32 %x, C2
1315// %old_replacement = select i1 %old_cmp1, i32 %target_low, i32 %target_high
1316// %old_x_offseted = add i32 %x, C1
1317// %old_cmp0 = icmp ult i32 %old_x_offseted, C0
1318// %r = select i1 %old_cmp0, i32 %x, i32 %old_replacement
1319// This can be rewritten as more canonical pattern:
1320// %new_cmp1 = icmp slt i32 %x, -C1
1321// %new_cmp2 = icmp sge i32 %x, C0-C1
1322// %new_clamped_low = select i1 %new_cmp1, i32 %target_low, i32 %x
1323// %r = select i1 %new_cmp2, i32 %target_high, i32 %new_clamped_low
1324// Iff -C1 s<= C2 s<= C0-C1
1325// Also ULT predicate can also be UGT iff C0 != -1 (+invert result)
1326// SLT predicate can also be SGT iff C2 != INT_MAX (+invert res.)
1327static Value *canonicalizeClampLike(SelectInst &Sel0, ICmpInst &Cmp0,
1328 InstCombiner::BuilderTy &Builder) {
1329 Value *X = Sel0.getTrueValue();
1330 Value *Sel1 = Sel0.getFalseValue();
1331
1332 // First match the condition of the outermost select.
1333 // Said condition must be one-use.
1334 if (!Cmp0.hasOneUse())
1335 return nullptr;
1336 ICmpInst::Predicate Pred0 = Cmp0.getPredicate();
1337 Value *Cmp00 = Cmp0.getOperand(0);
1338 Constant *C0;
1339 if (!match(Cmp0.getOperand(1),
1341 return nullptr;
1342
1343 if (!isa<SelectInst>(Sel1)) {
1344 Pred0 = ICmpInst::getInversePredicate(Pred0);
1345 std::swap(X, Sel1);
1346 }
1347
1348 // Canonicalize Cmp0 into ult or uge.
1349 // FIXME: we shouldn't care about lanes that are 'undef' in the end?
1350 switch (Pred0) {
1353 // Although icmp ult %x, 0 is an unusual thing to try and should generally
1354 // have been simplified, it does not verify with undef inputs so ensure we
1355 // are not in a strange state.
1356 if (!match(C0, m_SpecificInt_ICMP(
1359 return nullptr;
1360 break; // Great!
1363 // We want to canonicalize it to 'ult' or 'uge', so we'll need to increment
1364 // C0, which again means it must not have any all-ones elements.
1365 if (!match(C0,
1369 return nullptr; // Can't do, have all-ones element[s].
1371 C0 = InstCombiner::AddOne(C0);
1372 break;
1373 default:
1374 return nullptr; // Unknown predicate.
1375 }
1376
1377 // Now that we've canonicalized the ICmp, we know the X we expect;
1378 // the select in other hand should be one-use.
1379 if (!Sel1->hasOneUse())
1380 return nullptr;
1381
1382 // If the types do not match, look through any truncs to the underlying
1383 // instruction.
1384 if (Cmp00->getType() != X->getType() && X->hasOneUse())
1386
1387 // We now can finish matching the condition of the outermost select:
1388 // it should either be the X itself, or an addition of some constant to X.
1389 Constant *C1;
1390 if (Cmp00 == X)
1391 C1 = ConstantInt::getNullValue(X->getType());
1392 else if (!match(Cmp00,
1395 return nullptr;
1396
1397 Value *Cmp1;
1398 ICmpInst::Predicate Pred1;
1399 Constant *C2;
1400 Value *ReplacementLow, *ReplacementHigh;
1401 if (!match(Sel1, m_Select(m_Value(Cmp1), m_Value(ReplacementLow),
1402 m_Value(ReplacementHigh))) ||
1403 !match(Cmp1,
1404 m_ICmp(Pred1, m_Specific(X),
1406 return nullptr;
1407
1408 if (!Cmp1->hasOneUse() && (Cmp00 == X || !Cmp00->hasOneUse()))
1409 return nullptr; // Not enough one-use instructions for the fold.
1410 // FIXME: this restriction could be relaxed if Cmp1 can be reused as one of
1411 // two comparisons we'll need to build.
1412
1413 // Canonicalize Cmp1 into the form we expect.
1414 // FIXME: we shouldn't care about lanes that are 'undef' in the end?
1415 switch (Pred1) {
1417 break;
1419 // We'd have to increment C2 by one, and for that it must not have signed
1420 // max element, but then it would have been canonicalized to 'slt' before
1421 // we get here. So we can't do anything useful with 'sle'.
1422 return nullptr;
1424 // We want to canonicalize it to 'slt', so we'll need to increment C2,
1425 // which again means it must not have any signed max elements.
1426 if (!match(C2,
1429 C2->getType()->getScalarSizeInBits()))))
1430 return nullptr; // Can't do, have signed max element[s].
1431 C2 = InstCombiner::AddOne(C2);
1432 [[fallthrough]];
1434 // Also non-canonical, but here we don't need to change C2,
1435 // so we don't have any restrictions on C2, so we can just handle it.
1437 std::swap(ReplacementLow, ReplacementHigh);
1438 break;
1439 default:
1440 return nullptr; // Unknown predicate.
1441 }
1443 "Unexpected predicate type.");
1444
1445 // The thresholds of this clamp-like pattern.
1446 auto *ThresholdLowIncl = ConstantExpr::getNeg(C1);
1447 auto *ThresholdHighExcl = ConstantExpr::getSub(C0, C1);
1448
1451 "Unexpected predicate type.");
1452 if (Pred0 == ICmpInst::Predicate::ICMP_UGE)
1453 std::swap(ThresholdLowIncl, ThresholdHighExcl);
1454
1455 // The fold has a precondition 1: C2 s>= ThresholdLow
1457 ThresholdLowIncl);
1458 if (!match(Precond1, m_One()))
1459 return nullptr;
1460 // The fold has a precondition 2: C2 s<= ThresholdHigh
1462 ThresholdHighExcl);
1463 if (!match(Precond2, m_One()))
1464 return nullptr;
1465
1466 // If we are matching from a truncated input, we need to sext the
1467 // ReplacementLow and ReplacementHigh values. Only do the transform if they
1468 // are free to extend due to being constants.
1469 if (X->getType() != Sel0.getType()) {
1470 Constant *LowC, *HighC;
1471 if (!match(ReplacementLow, m_ImmConstant(LowC)) ||
1472 !match(ReplacementHigh, m_ImmConstant(HighC)))
1473 return nullptr;
1474 ReplacementLow = ConstantExpr::getSExt(LowC, X->getType());
1475 ReplacementHigh = ConstantExpr::getSExt(HighC, X->getType());
1476 }
1477
1478 // All good, finally emit the new pattern.
1479 Value *ShouldReplaceLow = Builder.CreateICmpSLT(X, ThresholdLowIncl);
1480 Value *ShouldReplaceHigh = Builder.CreateICmpSGE(X, ThresholdHighExcl);
1481 Value *MaybeReplacedLow =
1482 Builder.CreateSelect(ShouldReplaceLow, ReplacementLow, X);
1483
1484 // Create the final select. If we looked through a truncate above, we will
1485 // need to retruncate the result.
1486 Value *MaybeReplacedHigh = Builder.CreateSelect(
1487 ShouldReplaceHigh, ReplacementHigh, MaybeReplacedLow);
1488 return Builder.CreateTrunc(MaybeReplacedHigh, Sel0.getType());
1489}
1490
1491// If we have
1492// %cmp = icmp [canonical predicate] i32 %x, C0
1493// %r = select i1 %cmp, i32 %y, i32 C1
1494// Where C0 != C1 and %x may be different from %y, see if the constant that we
1495// will have if we flip the strictness of the predicate (i.e. without changing
1496// the result) is identical to the C1 in select. If it matches we can change
1497// original comparison to one with swapped predicate, reuse the constant,
1498// and swap the hands of select.
1499static Instruction *
1500tryToReuseConstantFromSelectInComparison(SelectInst &Sel, ICmpInst &Cmp,
1501 InstCombinerImpl &IC) {
1503 Value *X;
1504 Constant *C0;
1505 if (!match(&Cmp, m_OneUse(m_ICmp(
1506 Pred, m_Value(X),
1508 return nullptr;
1509
1510 // If comparison predicate is non-relational, we won't be able to do anything.
1511 if (ICmpInst::isEquality(Pred))
1512 return nullptr;
1513
1514 // If comparison predicate is non-canonical, then we certainly won't be able
1515 // to make it canonical; canonicalizeCmpWithConstant() already tried.
1517 return nullptr;
1518
1519 // If the [input] type of comparison and select type are different, lets abort
1520 // for now. We could try to compare constants with trunc/[zs]ext though.
1521 if (C0->getType() != Sel.getType())
1522 return nullptr;
1523
1524 // ULT with 'add' of a constant is canonical. See foldICmpAddConstant().
1525 // FIXME: Are there more magic icmp predicate+constant pairs we must avoid?
1526 // Or should we just abandon this transform entirely?
1527 if (Pred == CmpInst::ICMP_ULT && match(X, m_Add(m_Value(), m_Constant())))
1528 return nullptr;
1529
1530
1531 Value *SelVal0, *SelVal1; // We do not care which one is from where.
1532 match(&Sel, m_Select(m_Value(), m_Value(SelVal0), m_Value(SelVal1)));
1533 // At least one of these values we are selecting between must be a constant
1534 // else we'll never succeed.
1535 if (!match(SelVal0, m_AnyIntegralConstant()) &&
1536 !match(SelVal1, m_AnyIntegralConstant()))
1537 return nullptr;
1538
1539 // Does this constant C match any of the `select` values?
1540 auto MatchesSelectValue = [SelVal0, SelVal1](Constant *C) {
1541 return C->isElementWiseEqual(SelVal0) || C->isElementWiseEqual(SelVal1);
1542 };
1543
1544 // If C0 *already* matches true/false value of select, we are done.
1545 if (MatchesSelectValue(C0))
1546 return nullptr;
1547
1548 // Check the constant we'd have with flipped-strictness predicate.
1549 auto FlippedStrictness =
1551 if (!FlippedStrictness)
1552 return nullptr;
1553
1554 // If said constant doesn't match either, then there is no hope,
1555 if (!MatchesSelectValue(FlippedStrictness->second))
1556 return nullptr;
1557
1558 // It matched! Lets insert the new comparison just before select.
1560 IC.Builder.SetInsertPoint(&Sel);
1561
1562 Pred = ICmpInst::getSwappedPredicate(Pred); // Yes, swapped.
1563 Value *NewCmp = IC.Builder.CreateICmp(Pred, X, FlippedStrictness->second,
1564 Cmp.getName() + ".inv");
1565 IC.replaceOperand(Sel, 0, NewCmp);
1566 Sel.swapValues();
1567 Sel.swapProfMetadata();
1568
1569 return &Sel;
1570}
1571
1572static Instruction *foldSelectZeroOrOnes(ICmpInst *Cmp, Value *TVal,
1573 Value *FVal,
1574 InstCombiner::BuilderTy &Builder) {
1575 if (!Cmp->hasOneUse())
1576 return nullptr;
1577
1578 const APInt *CmpC;
1579 if (!match(Cmp->getOperand(1), m_APIntAllowUndef(CmpC)))
1580 return nullptr;
1581
1582 // (X u< 2) ? -X : -1 --> sext (X != 0)
1583 Value *X = Cmp->getOperand(0);
1584 if (Cmp->getPredicate() == ICmpInst::ICMP_ULT && *CmpC == 2 &&
1585 match(TVal, m_Neg(m_Specific(X))) && match(FVal, m_AllOnes()))
1586 return new SExtInst(Builder.CreateIsNotNull(X), TVal->getType());
1587
1588 // (X u> 1) ? -1 : -X --> sext (X != 0)
1589 if (Cmp->getPredicate() == ICmpInst::ICMP_UGT && *CmpC == 1 &&
1590 match(FVal, m_Neg(m_Specific(X))) && match(TVal, m_AllOnes()))
1591 return new SExtInst(Builder.CreateIsNotNull(X), TVal->getType());
1592
1593 return nullptr;
1594}
1595
1596static Value *foldSelectInstWithICmpConst(SelectInst &SI, ICmpInst *ICI) {
1597 const APInt *CmpC;
1598 Value *V;
1599 CmpInst::Predicate Pred;
1600 if (!match(ICI, m_ICmp(Pred, m_Value(V), m_APInt(CmpC))))
1601 return nullptr;
1602
1603 BinaryOperator *BO;
1604 const APInt *C;
1605 CmpInst::Predicate CPred;
1606 if (match(&SI, m_Select(m_Specific(ICI), m_APInt(C), m_BinOp(BO))))
1607 CPred = ICI->getPredicate();
1608 else if (match(&SI, m_Select(m_Specific(ICI), m_BinOp(BO), m_APInt(C))))
1609 CPred = ICI->getInversePredicate();
1610 else
1611 return nullptr;
1612
1613 const APInt *BinOpC;
1614 if (!match(BO, m_BinOp(m_Specific(V), m_APInt(BinOpC))))
1615 return nullptr;
1616
1618 .binaryOp(BO->getOpcode(), *BinOpC);
1619 if (R == *C) {
1621 return BO;
1622 }
1623 return nullptr;
1624}
1625
1626/// Visit a SelectInst that has an ICmpInst as its first operand.
1628 ICmpInst *ICI) {
1629 if (Instruction *NewSel = foldSelectValueEquivalence(SI, *ICI))
1630 return NewSel;
1631
1632 if (Instruction *NewSPF = canonicalizeSPF(SI, *ICI, *this))
1633 return NewSPF;
1634
1635 if (Value *V = foldSelectInstWithICmpConst(SI, ICI))
1636 return replaceInstUsesWith(SI, V);
1637
1638 if (Value *V = canonicalizeClampLike(SI, *ICI, Builder))
1639 return replaceInstUsesWith(SI, V);
1640
1641 if (Instruction *NewSel =
1642 tryToReuseConstantFromSelectInComparison(SI, *ICI, *this))
1643 return NewSel;
1644
1645 bool Changed = adjustMinMax(SI, *ICI);
1646
1647 if (Value *V = foldSelectICmpAnd(SI, ICI, Builder))
1648 return replaceInstUsesWith(SI, V);
1649
1650 // NOTE: if we wanted to, this is where to detect integer MIN/MAX
1651 Value *TrueVal = SI.getTrueValue();
1652 Value *FalseVal = SI.getFalseValue();
1653 ICmpInst::Predicate Pred = ICI->getPredicate();
1654 Value *CmpLHS = ICI->getOperand(0);
1655 Value *CmpRHS = ICI->getOperand(1);
1656 if (CmpRHS != CmpLHS && isa<Constant>(CmpRHS)) {
1657 if (CmpLHS == TrueVal && Pred == ICmpInst::ICMP_EQ) {
1658 // Transform (X == C) ? X : Y -> (X == C) ? C : Y
1659 SI.setOperand(1, CmpRHS);
1660 Changed = true;
1661 } else if (CmpLHS == FalseVal && Pred == ICmpInst::ICMP_NE) {
1662 // Transform (X != C) ? Y : X -> (X != C) ? Y : C
1663 SI.setOperand(2, CmpRHS);
1664 Changed = true;
1665 }
1666 }
1667
1668 // Canonicalize a signbit condition to use zero constant by swapping:
1669 // (CmpLHS > -1) ? TV : FV --> (CmpLHS < 0) ? FV : TV
1670 // To avoid conflicts (infinite loops) with other canonicalizations, this is
1671 // not applied with any constant select arm.
1672 if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes()) &&
1673 !match(TrueVal, m_Constant()) && !match(FalseVal, m_Constant()) &&
1674 ICI->hasOneUse()) {
1677 Value *IsNeg = Builder.CreateIsNeg(CmpLHS, ICI->getName());
1678 replaceOperand(SI, 0, IsNeg);
1679 SI.swapValues();
1680 SI.swapProfMetadata();
1681 return &SI;
1682 }
1683
1684 // FIXME: This code is nearly duplicated in InstSimplify. Using/refactoring
1685 // decomposeBitTestICmp() might help.
1686 {
1687 unsigned BitWidth =
1688 DL.getTypeSizeInBits(TrueVal->getType()->getScalarType());
1689 APInt MinSignedValue = APInt::getSignedMinValue(BitWidth);
1690 Value *X;
1691 const APInt *Y, *C;
1692 bool TrueWhenUnset;
1693 bool IsBitTest = false;
1694 if (ICmpInst::isEquality(Pred) &&
1695 match(CmpLHS, m_And(m_Value(X), m_Power2(Y))) &&
1696 match(CmpRHS, m_Zero())) {
1697 IsBitTest = true;
1698 TrueWhenUnset = Pred == ICmpInst::ICMP_EQ;
1699 } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) {
1700 X = CmpLHS;
1701 Y = &MinSignedValue;
1702 IsBitTest = true;
1703 TrueWhenUnset = false;
1704 } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) {
1705 X = CmpLHS;
1706 Y = &MinSignedValue;
1707 IsBitTest = true;
1708 TrueWhenUnset = true;
1709 }
1710 if (IsBitTest) {
1711 Value *V = nullptr;
1712 // (X & Y) == 0 ? X : X ^ Y --> X & ~Y
1713 if (TrueWhenUnset && TrueVal == X &&
1714 match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1715 V = Builder.CreateAnd(X, ~(*Y));
1716 // (X & Y) != 0 ? X ^ Y : X --> X & ~Y
1717 else if (!TrueWhenUnset && FalseVal == X &&
1718 match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1719 V = Builder.CreateAnd(X, ~(*Y));
1720 // (X & Y) == 0 ? X ^ Y : X --> X | Y
1721 else if (TrueWhenUnset && FalseVal == X &&
1722 match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1723 V = Builder.CreateOr(X, *Y);
1724 // (X & Y) != 0 ? X : X ^ Y --> X | Y
1725 else if (!TrueWhenUnset && TrueVal == X &&
1726 match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1727 V = Builder.CreateOr(X, *Y);
1728
1729 if (V)
1730 return replaceInstUsesWith(SI, V);
1731 }
1732 }
1733
1734 if (Instruction *V =
1735 foldSelectICmpAndAnd(SI.getType(), ICI, TrueVal, FalseVal, Builder))
1736 return V;
1737
1738 if (Instruction *V = foldSelectCtlzToCttz(ICI, TrueVal, FalseVal, Builder))
1739 return V;
1740
1741 if (Instruction *V = foldSelectZeroOrOnes(ICI, TrueVal, FalseVal, Builder))
1742 return V;
1743
1744 if (Value *V = foldSelectICmpAndOr(ICI, TrueVal, FalseVal, Builder))
1745 return replaceInstUsesWith(SI, V);
1746
1747 if (Value *V = foldSelectICmpLshrAshr(ICI, TrueVal, FalseVal, Builder))
1748 return replaceInstUsesWith(SI, V);
1749
1750 if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
1751 return replaceInstUsesWith(SI, V);
1752
1753 if (Value *V = canonicalizeSaturatedSubtract(ICI, TrueVal, FalseVal, Builder))
1754 return replaceInstUsesWith(SI, V);
1755
1756 if (Value *V = canonicalizeSaturatedAdd(ICI, TrueVal, FalseVal, Builder))
1757 return replaceInstUsesWith(SI, V);
1758
1759 return Changed ? &SI : nullptr;
1760}
1761
1762/// SI is a select whose condition is a PHI node (but the two may be in
1763/// different blocks). See if the true/false values (V) are live in all of the
1764/// predecessor blocks of the PHI. For example, cases like this can't be mapped:
1765///
1766/// X = phi [ C1, BB1], [C2, BB2]
1767/// Y = add
1768/// Z = select X, Y, 0
1769///
1770/// because Y is not live in BB1/BB2.
1771static bool canSelectOperandBeMappingIntoPredBlock(const Value *V,
1772 const SelectInst &SI) {
1773 // If the value is a non-instruction value like a constant or argument, it
1774 // can always be mapped.
1775 const Instruction *I = dyn_cast<Instruction>(V);
1776 if (!I) return true;
1777
1778 // If V is a PHI node defined in the same block as the condition PHI, we can
1779 // map the arguments.
1780 const PHINode *CondPHI = cast<PHINode>(SI.getCondition());
1781
1782 if (const PHINode *VP = dyn_cast<PHINode>(I))
1783 if (VP->getParent() == CondPHI->getParent())
1784 return true;
1785
1786 // Otherwise, if the PHI and select are defined in the same block and if V is
1787 // defined in a different block, then we can transform it.
1788 if (SI.getParent() == CondPHI->getParent() &&
1789 I->getParent() != CondPHI->getParent())
1790 return true;
1791
1792 // Otherwise we have a 'hard' case and we can't tell without doing more
1793 // detailed dominator based analysis, punt.
1794 return false;
1795}
1796
1797/// We have an SPF (e.g. a min or max) of an SPF of the form:
1798/// SPF2(SPF1(A, B), C)
1801 Value *B, Instruction &Outer,
1803 Value *C) {
1804 if (Outer.getType() != Inner->getType())
1805 return nullptr;
1806
1807 if (C == A || C == B) {
1808 // MAX(MAX(A, B), B) -> MAX(A, B)
1809 // MIN(MIN(a, b), a) -> MIN(a, b)
1810 // TODO: This could be done in instsimplify.
1811 if (SPF1 == SPF2 && SelectPatternResult::isMinOrMax(SPF1))
1812 return replaceInstUsesWith(Outer, Inner);
1813 }
1814
1815 return nullptr;
1816}
1817
1818/// Turn select C, (X + Y), (X - Y) --> (X + (select C, Y, (-Y))).
1819/// This is even legal for FP.
1820static Instruction *foldAddSubSelect(SelectInst &SI,
1821 InstCombiner::BuilderTy &Builder) {
1822 Value *CondVal = SI.getCondition();
1823 Value *TrueVal = SI.getTrueValue();
1824 Value *FalseVal = SI.getFalseValue();
1825 auto *TI = dyn_cast<Instruction>(TrueVal);
1826 auto *FI = dyn_cast<Instruction>(FalseVal);
1827 if (!TI || !FI || !TI->hasOneUse() || !FI->hasOneUse())
1828 return nullptr;
1829
1830 Instruction *AddOp = nullptr, *SubOp = nullptr;
1831 if ((TI->getOpcode() == Instruction::Sub &&
1832 FI->getOpcode() == Instruction::Add) ||
1833 (TI->getOpcode() == Instruction::FSub &&
1834 FI->getOpcode() == Instruction::FAdd)) {
1835 AddOp = FI;
1836 SubOp = TI;
1837 } else if ((FI->getOpcode() == Instruction::Sub &&
1838 TI->getOpcode() == Instruction::Add) ||
1839 (FI->getOpcode() == Instruction::FSub &&
1840 TI->getOpcode() == Instruction::FAdd)) {
1841 AddOp = TI;
1842 SubOp = FI;
1843 }
1844
1845 if (AddOp) {
1846 Value *OtherAddOp = nullptr;
1847 if (SubOp->getOperand(0) == AddOp->getOperand(0)) {
1848 OtherAddOp = AddOp->getOperand(1);
1849 } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) {
1850 OtherAddOp = AddOp->getOperand(0);
1851 }
1852
1853 if (OtherAddOp) {
1854 // So at this point we know we have (Y -> OtherAddOp):
1855 // select C, (add X, Y), (sub X, Z)
1856 Value *NegVal; // Compute -Z
1857 if (SI.getType()->isFPOrFPVectorTy()) {
1858 NegVal = Builder.CreateFNeg(SubOp->getOperand(1));
1859 if (Instruction *NegInst = dyn_cast<Instruction>(NegVal)) {
1861 Flags &= SubOp->getFastMathFlags();
1862 NegInst->setFastMathFlags(Flags);
1863 }
1864 } else {
1865 NegVal = Builder.CreateNeg(SubOp->getOperand(1));
1866 }
1867
1868 Value *NewTrueOp = OtherAddOp;
1869 Value *NewFalseOp = NegVal;
1870 if (AddOp != TI)
1871 std::swap(NewTrueOp, NewFalseOp);
1872 Value *NewSel = Builder.CreateSelect(CondVal, NewTrueOp, NewFalseOp,
1873 SI.getName() + ".p", &SI);
1874
1875 if (SI.getType()->isFPOrFPVectorTy()) {
1876 Instruction *RI =
1877 BinaryOperator::CreateFAdd(SubOp->getOperand(0), NewSel);
1878
1880 Flags &= SubOp->getFastMathFlags();
1881 RI->setFastMathFlags(Flags);
1882 return RI;
1883 } else
1884 return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel);
1885 }
1886 }
1887 return nullptr;
1888}
1889
1890/// Turn X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
1891/// And X - Y overflows ? 0 : X - Y -> usub_sat X, Y
1892/// Along with a number of patterns similar to:
1893/// X + Y overflows ? (X < 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1894/// X - Y overflows ? (X > 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1895static Instruction *
1896foldOverflowingAddSubSelect(SelectInst &SI, InstCombiner::BuilderTy &Builder) {
1897 Value *CondVal = SI.getCondition();
1898 Value *TrueVal = SI.getTrueValue();
1899 Value *FalseVal = SI.getFalseValue();
1900
1901 WithOverflowInst *II;
1902 if (!match(CondVal, m_ExtractValue<1>(m_WithOverflowInst(II))) ||
1903 !match(FalseVal, m_ExtractValue<0>(m_Specific(II))))
1904 return nullptr;
1905
1906 Value *X = II->getLHS();
1907 Value *Y = II->getRHS();
1908
1909 auto IsSignedSaturateLimit = [&](Value *Limit, bool IsAdd) {
1910 Type *Ty = Limit->getType();
1911
1913 Value *TrueVal, *FalseVal, *Op;
1914 const APInt *C;
1915 if (!match(Limit, m_Select(m_ICmp(Pred, m_Value(Op), m_APInt(C)),
1916 m_Value(TrueVal), m_Value(FalseVal))))
1917 return false;
1918
1919 auto IsZeroOrOne = [](const APInt &C) { return C.isZero() || C.isOne(); };
1920 auto IsMinMax = [&](Value *Min, Value *Max) {
1923 return match(Min, m_SpecificInt(MinVal)) &&
1924 match(Max, m_SpecificInt(MaxVal));
1925 };
1926
1927 if (Op != X && Op != Y)
1928 return false;
1929
1930 if (IsAdd) {
1931 // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1932 // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1933 // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1934 // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1935 if (Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
1936 IsMinMax(TrueVal, FalseVal))
1937 return true;
1938 // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1939 // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1940 // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1941 // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1942 if (Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
1943 IsMinMax(FalseVal, TrueVal))
1944 return true;
1945 } else {
1946 // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1947 // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1948 if (Op == X && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C + 1) &&
1949 IsMinMax(TrueVal, FalseVal))
1950 return true;
1951 // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1952 // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1953 if (Op == X && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 2) &&
1954 IsMinMax(FalseVal, TrueVal))
1955 return true;
1956 // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1957 // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1958 if (Op == Y && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
1959 IsMinMax(FalseVal, TrueVal))
1960 return true;
1961 // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1962 // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1963 if (Op == Y && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
1964 IsMinMax(TrueVal, FalseVal))
1965 return true;
1966 }
1967
1968 return false;
1969 };
1970
1971 Intrinsic::ID NewIntrinsicID;
1972 if (II->getIntrinsicID() == Intrinsic::uadd_with_overflow &&
1973 match(TrueVal, m_AllOnes()))
1974 // X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
1975 NewIntrinsicID = Intrinsic::uadd_sat;
1976 else if (II->getIntrinsicID() == Intrinsic::usub_with_overflow &&
1977 match(TrueVal, m_Zero()))
1978 // X - Y overflows ? 0 : X - Y -> usub_sat X, Y
1979 NewIntrinsicID = Intrinsic::usub_sat;
1980 else if (II->getIntrinsicID() == Intrinsic::sadd_with_overflow &&
1981 IsSignedSaturateLimit(TrueVal, /*IsAdd=*/true))
1982 // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1983 // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1984 // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1985 // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1986 // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1987 // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1988 // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1989 // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1990 NewIntrinsicID = Intrinsic::sadd_sat;
1991 else if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow &&
1992 IsSignedSaturateLimit(TrueVal, /*IsAdd=*/false))
1993 // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1994 // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1995 // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1996 // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1997 // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1998 // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1999 // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2000 // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2001 NewIntrinsicID = Intrinsic::ssub_sat;
2002 else
2003 return nullptr;
2004
2005 Function *F =
2006 Intrinsic::getDeclaration(SI.getModule(), NewIntrinsicID, SI.getType());
2007 return CallInst::Create(F, {X, Y});
2008}
2009
2011 Constant *C;
2012 if (!match(Sel.getTrueValue(), m_Constant(C)) &&
2013 !match(Sel.getFalseValue(), m_Constant(C)))
2014 return nullptr;
2015
2016 Instruction *ExtInst;
2017 if (!match(Sel.getTrueValue(), m_Instruction(ExtInst)) &&
2018 !match(Sel.getFalseValue(), m_Instruction(ExtInst)))
2019 return nullptr;
2020
2021 auto ExtOpcode = ExtInst->getOpcode();
2022 if (ExtOpcode != Instruction::ZExt && ExtOpcode != Instruction::SExt)
2023 return nullptr;
2024
2025 // If we are extending from a boolean type or if we can create a select that
2026 // has the same size operands as its condition, try to narrow the select.
2027 Value *X = ExtInst->getOperand(0);
2028 Type *SmallType = X->getType();
2029 Value *Cond = Sel.getCondition();
2030 auto *Cmp = dyn_cast<CmpInst>(Cond);
2031 if (!SmallType->isIntOrIntVectorTy(1) &&
2032 (!Cmp || Cmp->getOperand(0)->getType() != SmallType))
2033 return nullptr;
2034
2035 // If the constant is the same after truncation to the smaller type and
2036 // extension to the original type, we can narrow the select.
2037 Type *SelType = Sel.getType();
2038 Constant *TruncC = ConstantExpr::getTrunc(C, SmallType);
2039 Constant *ExtC = ConstantExpr::getCast(ExtOpcode, TruncC, SelType);
2040 if (ExtC == C && ExtInst->hasOneUse()) {
2041 Value *TruncCVal = cast<Value>(TruncC);
2042 if (ExtInst == Sel.getFalseValue())
2043 std::swap(X, TruncCVal);
2044
2045 // select Cond, (ext X), C --> ext(select Cond, X, C')
2046 // select Cond, C, (ext X) --> ext(select Cond, C', X)
2047 Value *NewSel = Builder.CreateSelect(Cond, X, TruncCVal, "narrow", &Sel);
2048 return CastInst::Create(Instruction::CastOps(ExtOpcode), NewSel, SelType);
2049 }
2050
2051 // If one arm of the select is the extend of the condition, replace that arm
2052 // with the extension of the appropriate known bool value.
2053 if (Cond == X) {
2054 if (ExtInst == Sel.getTrueValue()) {
2055 // select X, (sext X), C --> select X, -1, C
2056 // select X, (zext X), C --> select X, 1, C
2057 Constant *One = ConstantInt::getTrue(SmallType);
2058 Constant *AllOnesOrOne = ConstantExpr::getCast(ExtOpcode, One, SelType);
2059 return SelectInst::Create(Cond, AllOnesOrOne, C, "", nullptr, &Sel);
2060 } else {
2061 // select X, C, (sext X) --> select X, C, 0
2062 // select X, C, (zext X) --> select X, C, 0
2064 return SelectInst::Create(Cond, C, Zero, "", nullptr, &Sel);
2065 }
2066 }
2067
2068 return nullptr;
2069}
2070
2071/// Try to transform a vector select with a constant condition vector into a
2072/// shuffle for easier combining with other shuffles and insert/extract.
2073static Instruction *canonicalizeSelectToShuffle(SelectInst &SI) {
2074 Value *CondVal = SI.getCondition();
2075 Constant *CondC;
2076 auto *CondValTy = dyn_cast<FixedVectorType>(CondVal->getType());
2077 if (!CondValTy || !match(CondVal, m_Constant(CondC)))
2078 return nullptr;
2079
2080 unsigned NumElts = CondValTy->getNumElements();
2082 Mask.reserve(NumElts);
2083 for (unsigned i = 0; i != NumElts; ++i) {
2084 Constant *Elt = CondC->getAggregateElement(i);
2085 if (!Elt)
2086 return nullptr;
2087
2088 if (Elt->isOneValue()) {
2089 // If the select condition element is true, choose from the 1st vector.
2090 Mask.push_back(i);
2091 } else if (Elt->isNullValue()) {
2092 // If the select condition element is false, choose from the 2nd vector.
2093 Mask.push_back(i + NumElts);
2094 } else if (isa<UndefValue>(Elt)) {
2095 // Undef in a select condition (choose one of the operands) does not mean
2096 // the same thing as undef in a shuffle mask (any value is acceptable), so
2097 // give up.
2098 return nullptr;
2099 } else {
2100 // Bail out on a constant expression.
2101 return nullptr;
2102 }
2103 }
2104
2105 return new ShuffleVectorInst(SI.getTrueValue(), SI.getFalseValue(), Mask);
2106}
2107
2108/// If we have a select of vectors with a scalar condition, try to convert that
2109/// to a vector select by splatting the condition. A splat may get folded with
2110/// other operations in IR and having all operands of a select be vector types
2111/// is likely better for vector codegen.
2112static Instruction *canonicalizeScalarSelectOfVecs(SelectInst &Sel,
2113 InstCombinerImpl &IC) {
2114 auto *Ty = dyn_cast<VectorType>(Sel.getType());
2115 if (!Ty)
2116 return nullptr;
2117
2118 // We can replace a single-use extract with constant index.
2119 Value *Cond = Sel.getCondition();
2121 return nullptr;
2122
2123 // select (extelt V, Index), T, F --> select (splat V, Index), T, F
2124 // Splatting the extracted condition reduces code (we could directly create a
2125 // splat shuffle of the source vector to eliminate the intermediate step).
2126 return IC.replaceOperand(
2127 Sel, 0, IC.Builder.CreateVectorSplat(Ty->getElementCount(), Cond));
2128}
2129
2130/// Reuse bitcasted operands between a compare and select:
2131/// select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2132/// bitcast (select (cmp (bitcast C), (bitcast D)), (bitcast C), (bitcast D))
2133static Instruction *foldSelectCmpBitcasts(SelectInst &Sel,
2134 InstCombiner::BuilderTy &Builder) {
2135 Value *Cond = Sel.getCondition();
2136 Value *TVal = Sel.getTrueValue();
2137 Value *FVal = Sel.getFalseValue();
2138
2139 CmpInst::Predicate Pred;
2140 Value *A, *B;
2141 if (!match(Cond, m_Cmp(Pred, m_Value(A), m_Value(B))))
2142 return nullptr;
2143
2144 // The select condition is a compare instruction. If the select's true/false
2145 // values are already the same as the compare operands, there's nothing to do.
2146 if (TVal == A || TVal == B || FVal == A || FVal == B)
2147 return nullptr;
2148
2149 Value *C, *D;
2150 if (!match(A, m_BitCast(m_Value(C))) || !match(B, m_BitCast(m_Value(D))))
2151 return nullptr;
2152
2153 // select (cmp (bitcast C), (bitcast D)), (bitcast TSrc), (bitcast FSrc)
2154 Value *TSrc, *FSrc;
2155 if (!match(TVal, m_BitCast(m_Value(TSrc))) ||
2156 !match(FVal, m_BitCast(m_Value(FSrc))))
2157 return nullptr;
2158
2159 // If the select true/false values are *different bitcasts* of the same source
2160 // operands, make the select operands the same as the compare operands and
2161 // cast the result. This is the canonical select form for min/max.
2162 Value *NewSel;
2163 if (TSrc == C && FSrc == D) {
2164 // select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2165 // bitcast (select (cmp A, B), A, B)
2166 NewSel = Builder.CreateSelect(Cond, A, B, "", &Sel);
2167 } else if (TSrc == D && FSrc == C) {
2168 // select (cmp (bitcast C), (bitcast D)), (bitcast' D), (bitcast' C) -->
2169 // bitcast (select (cmp A, B), B, A)
2170 NewSel = Builder.CreateSelect(Cond, B, A, "", &Sel);
2171 } else {
2172 return nullptr;
2173 }
2174 return CastInst::CreateBitOrPointerCast(NewSel, Sel.getType());
2175}
2176
2177/// Try to eliminate select instructions that test the returned flag of cmpxchg
2178/// instructions.
2179///
2180/// If a select instruction tests the returned flag of a cmpxchg instruction and
2181/// selects between the returned value of the cmpxchg instruction its compare
2182/// operand, the result of the select will always be equal to its false value.
2183/// For example:
2184///
2185/// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2186/// %1 = extractvalue { i64, i1 } %0, 1
2187/// %2 = extractvalue { i64, i1 } %0, 0
2188/// %3 = select i1 %1, i64 %compare, i64 %2
2189/// ret i64 %3
2190///
2191/// The returned value of the cmpxchg instruction (%2) is the original value
2192/// located at %ptr prior to any update. If the cmpxchg operation succeeds, %2
2193/// must have been equal to %compare. Thus, the result of the select is always
2194/// equal to %2, and the code can be simplified to:
2195///
2196/// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2197/// %1 = extractvalue { i64, i1 } %0, 0
2198/// ret i64 %1
2199///
2200static Value *foldSelectCmpXchg(SelectInst &SI) {
2201 // A helper that determines if V is an extractvalue instruction whose
2202 // aggregate operand is a cmpxchg instruction and whose single index is equal
2203 // to I. If such conditions are true, the helper returns the cmpxchg
2204 // instruction; otherwise, a nullptr is returned.
2205 auto isExtractFromCmpXchg = [](Value *V, unsigned I) -> AtomicCmpXchgInst * {
2206 auto *Extract = dyn_cast<ExtractValueInst>(V);
2207 if (!Extract)
2208 return nullptr;
2209 if (Extract->getIndices()[0] != I)
2210 return nullptr;
2211 return dyn_cast<AtomicCmpXchgInst>(Extract->getAggregateOperand());
2212 };
2213
2214 // If the select has a single user, and this user is a select instruction that
2215 // we can simplify, skip the cmpxchg simplification for now.
2216 if (SI.hasOneUse())
2217 if (auto *Select = dyn_cast<SelectInst>(SI.user_back()))
2218 if (Select->getCondition() == SI.getCondition())
2219 if (Select->getFalseValue() == SI.getTrueValue() ||
2220 Select->getTrueValue() == SI.getFalseValue())
2221 return nullptr;
2222
2223 // Ensure the select condition is the returned flag of a cmpxchg instruction.
2224 auto *CmpXchg = isExtractFromCmpXchg(SI.getCondition(), 1);
2225 if (!CmpXchg)
2226 return nullptr;
2227
2228 // Check the true value case: The true value of the select is the returned
2229 // value of the same cmpxchg used by the condition, and the false value is the
2230 // cmpxchg instruction's compare operand.
2231 if (auto *X = isExtractFromCmpXchg(SI.getTrueValue(), 0))
2232 if (X == CmpXchg && X->getCompareOperand() == SI.getFalseValue())
2233 return SI.getFalseValue();
2234
2235 // Check the false value case: The false value of the select is the returned
2236 // value of the same cmpxchg used by the condition, and the true value is the
2237 // cmpxchg instruction's compare operand.
2238 if (auto *X = isExtractFromCmpXchg(SI.getFalseValue(), 0))
2239 if (X == CmpXchg && X->getCompareOperand() == SI.getTrueValue())
2240 return SI.getFalseValue();
2241
2242 return nullptr;
2243}
2244
2245/// Try to reduce a funnel/rotate pattern that includes a compare and select
2246/// into a funnel shift intrinsic. Example:
2247/// rotl32(a, b) --> (b == 0 ? a : ((a >> (32 - b)) | (a << b)))
2248/// --> call llvm.fshl.i32(a, a, b)
2249/// fshl32(a, b, c) --> (c == 0 ? a : ((b >> (32 - c)) | (a << c)))
2250/// --> call llvm.fshl.i32(a, b, c)
2251/// fshr32(a, b, c) --> (c == 0 ? b : ((a >> (32 - c)) | (b << c)))
2252/// --> call llvm.fshr.i32(a, b, c)
2253static Instruction *foldSelectFunnelShift(SelectInst &Sel,
2254 InstCombiner::BuilderTy &Builder) {
2255 // This must be a power-of-2 type for a bitmasking transform to be valid.
2256 unsigned Width = Sel.getType()->getScalarSizeInBits();
2257 if (!isPowerOf2_32(Width))
2258 return nullptr;
2259
2260 BinaryOperator *Or0, *Or1;
2261 if (!match(Sel.getFalseValue(), m_OneUse(m_Or(m_BinOp(Or0), m_BinOp(Or1)))))
2262 return nullptr;
2263
2264 Value *SV0, *SV1, *SA0, *SA1;
2265 if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(SV0),
2266 m_ZExtOrSelf(m_Value(SA0))))) ||
2268 m_ZExtOrSelf(m_Value(SA1))))) ||
2269 Or0->getOpcode() == Or1->getOpcode())
2270 return nullptr;
2271
2272 // Canonicalize to or(shl(SV0, SA0), lshr(SV1, SA1)).
2273 if (Or0->getOpcode() == BinaryOperator::LShr) {
2274 std::swap(Or0, Or1);
2275 std::swap(SV0, SV1);
2276 std::swap(SA0, SA1);
2277 }
2278 assert(Or0->getOpcode() == BinaryOperator::Shl &&
2279 Or1->getOpcode() == BinaryOperator::LShr &&
2280 "Illegal or(shift,shift) pair");
2281
2282 // Check the shift amounts to see if they are an opposite pair.
2283 Value *ShAmt;
2284 if (match(SA1, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA0)))))
2285 ShAmt = SA0;
2286 else if (match(SA0, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA1)))))
2287 ShAmt = SA1;
2288 else
2289 return nullptr;
2290
2291 // We should now have this pattern:
2292 // select ?, TVal, (or (shl SV0, SA0), (lshr SV1, SA1))
2293 // The false value of the select must be a funnel-shift of the true value:
2294 // IsFShl -> TVal must be SV0 else TVal must be SV1.
2295 bool IsFshl = (ShAmt == SA0);
2296 Value *TVal = Sel.getTrueValue();
2297 if ((IsFshl && TVal != SV0) || (!IsFshl && TVal != SV1))
2298 return nullptr;
2299
2300 // Finally, see if the select is filtering out a shift-by-zero.
2301 Value *Cond = Sel.getCondition();
2303 if (!match(Cond, m_OneUse(m_ICmp(Pred, m_Specific(ShAmt), m_ZeroInt()))) ||
2304 Pred != ICmpInst::ICMP_EQ)
2305 return nullptr;
2306
2307 // If this is not a rotate then the select was blocking poison from the
2308 // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.
2309 if (SV0 != SV1) {
2310 if (IsFshl && !llvm::isGuaranteedNotToBePoison(SV1))
2311 SV1 = Builder.CreateFreeze(SV1);
2312 else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(SV0))
2313 SV0 = Builder.CreateFreeze(SV0);
2314 }
2315
2316 // This is a funnel/rotate that avoids shift-by-bitwidth UB in a suboptimal way.
2317 // Convert to funnel shift intrinsic.
2318 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2320 ShAmt = Builder.CreateZExt(ShAmt, Sel.getType());
2321 return CallInst::Create(F, { SV0, SV1, ShAmt });
2322}
2323
2324static Instruction *foldSelectToCopysign(SelectInst &Sel,
2325 InstCombiner::BuilderTy &Builder) {
2326 Value *Cond = Sel.getCondition();
2327 Value *TVal = Sel.getTrueValue();
2328 Value *FVal = Sel.getFalseValue();
2329 Type *SelType = Sel.getType();
2330
2331 // Match select ?, TC, FC where the constants are equal but negated.
2332 // TODO: Generalize to handle a negated variable operand?
2333 const APFloat *TC, *FC;
2334 if (!match(TVal, m_APFloatAllowUndef(TC)) ||
2335 !match(FVal, m_APFloatAllowUndef(FC)) ||
2336 !abs(*TC).bitwiseIsEqual(abs(*FC)))
2337 return nullptr;
2338
2339 assert(TC != FC && "Expected equal select arms to simplify");
2340
2341 Value *X;
2342 const APInt *C;
2343 bool IsTrueIfSignSet;
2345 if (!match(Cond, m_OneUse(m_ICmp(Pred, m_BitCast(m_Value(X)), m_APInt(C)))) ||
2346 !InstCombiner::isSignBitCheck(Pred, *C, IsTrueIfSignSet) ||
2347 X->getType() != SelType)
2348 return nullptr;
2349
2350 // If needed, negate the value that will be the sign argument of the copysign:
2351 // (bitcast X) < 0 ? -TC : TC --> copysign(TC, X)
2352 // (bitcast X) < 0 ? TC : -TC --> copysign(TC, -X)
2353 // (bitcast X) >= 0 ? -TC : TC --> copysign(TC, -X)
2354 // (bitcast X) >= 0 ? TC : -TC --> copysign(TC, X)
2355 // Note: FMF from the select can not be propagated to the new instructions.
2356 if (IsTrueIfSignSet ^ TC->isNegative())
2357 X = Builder.CreateFNeg(X);
2358
2359 // Canonicalize the magnitude argument as the positive constant since we do
2360 // not care about its sign.
2361 Value *MagArg = ConstantFP::get(SelType, abs(*TC));
2362 Function *F = Intrinsic::getDeclaration(Sel.getModule(), Intrinsic::copysign,
2363 Sel.getType());
2364 return CallInst::Create(F, { MagArg, X });
2365}
2366
2368 if (!isa<VectorType>(Sel.getType()))
2369 return nullptr;
2370
2371 Value *Cond = Sel.getCondition();
2372 Value *TVal = Sel.getTrueValue();
2373 Value *FVal = Sel.getFalseValue();
2374 Value *C, *X, *Y;
2375
2376 if (match(Cond, m_VecReverse(m_Value(C)))) {
2377 auto createSelReverse = [&](Value *C, Value *X, Value *Y) {
2378 Value *V = Builder.CreateSelect(C, X, Y, Sel.getName(), &Sel);
2379 if (auto *I = dyn_cast<Instruction>(V))
2380 I->copyIRFlags(&Sel);
2381 Module *M = Sel.getModule();
2383 M, Intrinsic::experimental_vector_reverse, V->getType());
2384 return CallInst::Create(F, V);
2385 };
2386
2387 if (match(TVal, m_VecReverse(m_Value(X)))) {
2388 // select rev(C), rev(X), rev(Y) --> rev(select C, X, Y)
2389 if (match(FVal, m_VecReverse(m_Value(Y))) &&
2390 (Cond->hasOneUse() || TVal->hasOneUse() || FVal->hasOneUse()))
2391 return createSelReverse(C, X, Y);
2392
2393 // select rev(C), rev(X), FValSplat --> rev(select C, X, FValSplat)
2394 if ((Cond->hasOneUse() || TVal->hasOneUse()) && isSplatValue(FVal))
2395 return createSelReverse(C, X, FVal);
2396 }
2397 // select rev(C), TValSplat, rev(Y) --> rev(select C, TValSplat, Y)
2398 else if (isSplatValue(TVal) && match(FVal, m_VecReverse(m_Value(Y))) &&
2399 (Cond->hasOneUse() || FVal->hasOneUse()))
2400 return createSelReverse(C, TVal, Y);
2401 }
2402
2403 auto *VecTy = dyn_cast<FixedVectorType>(Sel.getType());
2404 if (!VecTy)
2405 return nullptr;
2406
2407 unsigned NumElts = VecTy->getNumElements();
2408 APInt UndefElts(NumElts, 0);
2409 APInt AllOnesEltMask(APInt::getAllOnes(NumElts));
2410 if (Value *V = SimplifyDemandedVectorElts(&Sel, AllOnesEltMask, UndefElts)) {
2411 if (V != &Sel)
2412 return replaceInstUsesWith(Sel, V);
2413 return &Sel;
2414 }
2415
2416 // A select of a "select shuffle" with a common operand can be rearranged
2417 // to select followed by "select shuffle". Because of poison, this only works
2418 // in the case of a shuffle with no undefined mask elements.
2420 if (match(TVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
2421 !is_contained(Mask, UndefMaskElem) &&
2422 cast<ShuffleVectorInst>(TVal)->isSelect()) {
2423 if (X == FVal) {
2424 // select Cond, (shuf_sel X, Y), X --> shuf_sel X, (select Cond, Y, X)
2425 Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
2426 return new ShuffleVectorInst(X, NewSel, Mask);
2427 }
2428 if (Y == FVal) {
2429 // select Cond, (shuf_sel X, Y), Y --> shuf_sel (select Cond, X, Y), Y
2430 Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
2431 return new ShuffleVectorInst(NewSel, Y, Mask);
2432 }
2433 }
2434 if (match(FVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
2435 !is_contained(Mask, UndefMaskElem) &&
2436 cast<ShuffleVectorInst>(FVal)->isSelect()) {
2437 if (X == TVal) {
2438 // select Cond, X, (shuf_sel X, Y) --> shuf_sel X, (select Cond, X, Y)
2439 Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
2440 return new ShuffleVectorInst(X, NewSel, Mask);
2441 }
2442 if (Y == TVal) {
2443 // select Cond, Y, (shuf_sel X, Y) --> shuf_sel (select Cond, Y, X), Y
2444 Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
2445 return new ShuffleVectorInst(NewSel, Y, Mask);
2446 }
2447 }
2448
2449 return nullptr;
2450}
2451
2452static Instruction *foldSelectToPhiImpl(SelectInst &Sel, BasicBlock *BB,
2453 const DominatorTree &DT,
2454 InstCombiner::BuilderTy &Builder) {
2455 // Find the block's immediate dominator that ends with a conditional branch
2456 // that matches select's condition (maybe inverted).
2457 auto *IDomNode = DT[BB]->getIDom();
2458 if (!IDomNode)
2459 return nullptr;
2460 BasicBlock *IDom = IDomNode->getBlock();
2461
2462 Value *Cond = Sel.getCondition();
2463 Value *IfTrue, *IfFalse;
2464 BasicBlock *TrueSucc, *FalseSucc;
2465 if (match(IDom->getTerminator(),
2466 m_Br(m_Specific(Cond), m_BasicBlock(TrueSucc),
2467 m_BasicBlock(FalseSucc)))) {
2468 IfTrue = Sel.getTrueValue();
2469 IfFalse = Sel.getFalseValue();
2470 } else if (match(IDom->getTerminator(),
2471 m_Br(m_Not(m_Specific(Cond)), m_BasicBlock(TrueSucc),
2472 m_BasicBlock(FalseSucc)))) {
2473 IfTrue = Sel.getFalseValue();
2474 IfFalse = Sel.getTrueValue();
2475 } else
2476 return nullptr;
2477
2478 // Make sure the branches are actually different.
2479 if (TrueSucc == FalseSucc)
2480 return nullptr;
2481
2482 // We want to replace select %cond, %a, %b with a phi that takes value %a
2483 // for all incoming edges that are dominated by condition `%cond == true`,
2484 // and value %b for edges dominated by condition `%cond == false`. If %a
2485 // or %b are also phis from the same basic block, we can go further and take
2486 // their incoming values from the corresponding blocks.
2487 BasicBlockEdge TrueEdge(IDom, TrueSucc);
2488 BasicBlockEdge FalseEdge(IDom, FalseSucc);
2490 for (auto *Pred : predecessors(BB)) {
2491 // Check implication.
2492 BasicBlockEdge Incoming(Pred, BB);
2493 if (DT.dominates(TrueEdge, Incoming))
2494 Inputs[Pred] = IfTrue->DoPHITranslation(BB, Pred);
2495 else if (DT.dominates(FalseEdge, Incoming))
2496 Inputs[Pred] = IfFalse->DoPHITranslation(BB, Pred);
2497 else
2498 return nullptr;
2499 // Check availability.
2500 if (auto *Insn = dyn_cast<Instruction>(Inputs[Pred]))
2501 if (!DT.dominates(Insn, Pred->getTerminator()))
2502 return nullptr;
2503 }
2504
2505 Builder.SetInsertPoint(&*BB->begin());
2506 auto *PN = Builder.CreatePHI(Sel.getType(), Inputs.size());
2507 for (auto *Pred : predecessors(BB))
2508 PN->addIncoming(Inputs[Pred], Pred);
2509 PN->takeName(&Sel);
2510 return PN;
2511}
2512
2513static Instruction *foldSelectToPhi(SelectInst &Sel, const DominatorTree &DT,
2514 InstCombiner::BuilderTy &Builder) {
2515 // Try to replace this select with Phi in one of these blocks.
2516 SmallSetVector<BasicBlock *, 4> CandidateBlocks;
2517 CandidateBlocks.insert(Sel.getParent());
2518 for (Value *V : Sel.operands())
2519 if (auto *I = dyn_cast<Instruction>(V))
2520 CandidateBlocks.insert(I->getParent());
2521
2522 for (BasicBlock *BB : CandidateBlocks)
2523 if (auto *PN = foldSelectToPhiImpl(Sel, BB, DT, Builder))
2524 return PN;
2525 return nullptr;
2526}
2527
2528static Value *foldSelectWithFrozenICmp(SelectInst &Sel, InstCombiner::BuilderTy &Builder) {
2529 FreezeInst *FI = dyn_cast<FreezeInst>(Sel.getCondition());
2530 if (!FI)
2531 return nullptr;
2532
2533 Value *Cond = FI->getOperand(0);
2534 Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
2535
2536 // select (freeze(x == y)), x, y --> y
2537 // select (freeze(x != y)), x, y --> x
2538 // The freeze should be only used by this select. Otherwise, remaining uses of
2539 // the freeze can observe a contradictory value.
2540 // c = freeze(x == y) ; Let's assume that y = poison & x = 42; c is 0 or 1
2541 // a = select c, x, y ;
2542 // f(a, c) ; f(poison, 1) cannot happen, but if a is folded
2543 // ; to y, this can happen.
2544 CmpInst::Predicate Pred;
2545 if (FI->hasOneUse() &&
2546 match(Cond, m_c_ICmp(Pred, m_Specific(TrueVal), m_Specific(FalseVal))) &&
2547 (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)) {
2548 return Pred == ICmpInst::ICMP_EQ ? FalseVal : TrueVal;
2549 }
2550
2551 return nullptr;
2552}
2553
2554Instruction *InstCombinerImpl::foldAndOrOfSelectUsingImpliedCond(Value *Op,
2555 SelectInst &SI,
2556 bool IsAnd) {
2557 Value *CondVal = SI.getCondition();
2558 Value *A = SI.getTrueValue();
2559 Value *B = SI.getFalseValue();
2560
2561 assert(Op->getType()->isIntOrIntVectorTy(1) &&
2562 "Op must be either i1 or vector of i1.");
2563
2564 std::optional<bool> Res = isImpliedCondition(Op, CondVal, DL, IsAnd);
2565 if (!Res)
2566 return nullptr;
2567
2568 Value *Zero = Constant::getNullValue(A->getType());
2569 Value *One = Constant::getAllOnesValue(A->getType());
2570
2571 if (*Res == true) {
2572 if (IsAnd)
2573 // select op, (select cond, A, B), false => select op, A, false
2574 // and op, (select cond, A, B) => select op, A, false
2575 // if op = true implies condval = true.
2576 return SelectInst::Create(Op, A, Zero);
2577 else
2578 // select op, true, (select cond, A, B) => select op, true, A
2579 // or op, (select cond, A, B) => select op, true, A
2580 // if op = false implies condval = true.
2581 return SelectInst::Create(Op, One, A);
2582 } else {
2583 if (IsAnd)
2584 // select op, (select cond, A, B), false => select op, B, false
2585 // and op, (select cond, A, B) => select op, B, false
2586 // if op = true implies condval = false.
2587 return SelectInst::Create(Op, B, Zero);
2588 else
2589 // select op, true, (select cond, A, B) => select op, true, B
2590 // or op, (select cond, A, B) => select op, true, B
2591 // if op = false implies condval = false.
2592 return SelectInst::Create(Op, One, B);
2593 }
2594}
2595
2596// Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need
2597// fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work.
2598static Instruction *foldSelectWithFCmpToFabs(SelectInst &SI,
2599 InstCombinerImpl &IC) {
2600 Value *CondVal = SI.getCondition();
2601
2602 bool ChangedFMF = false;
2603 for (bool Swap : {false, true}) {
2604 Value *TrueVal = SI.getTrueValue();
2605 Value *X = SI.getFalseValue();
2606 CmpInst::Predicate Pred;
2607
2608 if (Swap)
2609 std::swap(TrueVal, X);
2610
2611 if (!match(CondVal, m_FCmp(Pred, m_Specific(X), m_AnyZeroFP())))
2612 continue;
2613
2614 // fold (X <= +/-0.0) ? (0.0 - X) : X to fabs(X), when 'Swap' is false
2615 // fold (X > +/-0.0) ? X : (0.0 - X) to fabs(X), when 'Swap' is true
2616 if (match(TrueVal, m_FSub(m_PosZeroFP(), m_Specific(X)))) {
2617 if (!Swap && (Pred == FCmpInst::FCMP_OLE || Pred == FCmpInst::FCMP_ULE)) {
2618 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2619 return IC.replaceInstUsesWith(SI, Fabs);
2620 }
2621 if (Swap && (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_UGT)) {
2622 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2623 return IC.replaceInstUsesWith(SI, Fabs);
2624 }
2625 }
2626
2627 if (!match(TrueVal, m_FNeg(m_Specific(X))))
2628 return nullptr;
2629
2630 // Forward-propagate nnan and ninf from the fneg to the select.
2631 // If all inputs are not those values, then the select is not either.
2632 // Note: nsz is defined differently, so it may not be correct to propagate.
2633 FastMathFlags FMF = cast<FPMathOperator>(TrueVal)->getFastMathFlags();
2634 if (FMF.noNaNs() && !SI.hasNoNaNs()) {
2635 SI.setHasNoNaNs(true);
2636 ChangedFMF = true;
2637 }
2638 if (FMF.noInfs() && !SI.hasNoInfs()) {
2639 SI.setHasNoInfs(true);
2640 ChangedFMF = true;
2641 }
2642
2643 // With nsz, when 'Swap' is false:
2644 // fold (X < +/-0.0) ? -X : X or (X <= +/-0.0) ? -X : X to fabs(X)
2645 // fold (X > +/-0.0) ? -X : X or (X >= +/-0.0) ? -X : X to -fabs(x)
2646 // when 'Swap' is true:
2647 // fold (X > +/-0.0) ? X : -X or (X >= +/-0.0) ? X : -X to fabs(X)
2648 // fold (X < +/-0.0) ? X : -X or (X <= +/-0.0) ? X : -X to -fabs(X)
2649 //
2650 // Note: We require "nnan" for this fold because fcmp ignores the signbit
2651 // of NAN, but IEEE-754 specifies the signbit of NAN values with
2652 // fneg/fabs operations.
2653 if (!SI.hasNoSignedZeros() || !SI.hasNoNaNs())
2654 return nullptr;
2655
2656 if (Swap)
2657 Pred = FCmpInst::getSwappedPredicate(Pred);
2658
2659 bool IsLTOrLE = Pred == FCmpInst::FCMP_OLT || Pred == FCmpInst::FCMP_OLE ||
2660 Pred == FCmpInst::FCMP_ULT || Pred == FCmpInst::FCMP_ULE;
2661 bool IsGTOrGE = Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_OGE ||
2662 Pred == FCmpInst::FCMP_UGT || Pred == FCmpInst::FCMP_UGE;
2663
2664 if (IsLTOrLE) {
2665 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2666 return IC.replaceInstUsesWith(SI, Fabs);
2667 }
2668 if (IsGTOrGE) {
2669 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2670 Instruction *NewFNeg = UnaryOperator::CreateFNeg(Fabs);
2671 NewFNeg->setFastMathFlags(SI.getFastMathFlags());
2672 return NewFNeg;
2673 }
2674 }
2675
2676 return ChangedFMF ? &SI : nullptr;
2677}
2678
2679// Match the following IR pattern:
2680// %x.lowbits = and i8 %x, %lowbitmask
2681// %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 0
2682// %x.biased = add i8 %x, %bias
2683// %x.biased.highbits = and i8 %x.biased, %highbitmask
2684// %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
2685// Define:
2686// %alignment = add i8 %lowbitmask, 1
2687// Iff 1. an %alignment is a power-of-two (aka, %lowbitmask is a low bit mask)
2688// and 2. %bias is equal to either %lowbitmask or %alignment,
2689// and 3. %highbitmask is equal to ~%lowbitmask (aka, to -%alignment)
2690// then this pattern can be transformed into:
2691// %x.offset = add i8 %x, %lowbitmask
2692// %x.roundedup = and i8 %x.offset, %highbitmask
2693static Value *
2694foldRoundUpIntegerWithPow2Alignment(SelectInst &SI,
2695 InstCombiner::BuilderTy &Builder) {
2696 Value *Cond = SI.getCondition();
2697 Value *X = SI.getTrueValue();
2698 Value *XBiasedHighBits = SI.getFalseValue();
2699
2701 Value *XLowBits;
2702 if (!match(Cond, m_ICmp(Pred, m_Value(XLowBits), m_ZeroInt())) ||
2703 !ICmpInst::isEquality(Pred))
2704 return nullptr;
2705
2706 if (Pred == ICmpInst::Predicate::ICMP_NE)
2707 std::swap(X, XBiasedHighBits);
2708
2709 // FIXME: we could support non non-splats here.
2710
2711 const APInt *LowBitMaskCst;
2712 if (!match(XLowBits, m_And(m_Specific(X), m_APIntAllowUndef(LowBitMaskCst))))
2713 return nullptr;
2714
2715 // Match even if the AND and ADD are swapped.
2716 const APInt *BiasCst, *HighBitMaskCst;
2717 if (!match(XBiasedHighBits,
2719 m_APIntAllowUndef(HighBitMaskCst))) &&
2720 !match(XBiasedHighBits,
2721 m_Add(m_And(m_Specific(X), m_APIntAllowUndef(HighBitMaskCst)),
2722 m_APIntAllowUndef(BiasCst))))
2723 return nullptr;
2724
2725 if (!LowBitMaskCst->isMask())
2726 return nullptr;
2727
2728 APInt InvertedLowBitMaskCst = ~*LowBitMaskCst;
2729 if (InvertedLowBitMaskCst != *HighBitMaskCst)
2730 return nullptr;
2731
2732 APInt AlignmentCst = *LowBitMaskCst + 1;
2733
2734 if (*BiasCst != AlignmentCst && *BiasCst != *LowBitMaskCst)
2735 return nullptr;
2736
2737 if (!XBiasedHighBits->hasOneUse()) {
2738 if (*BiasCst == *LowBitMaskCst)
2739 return XBiasedHighBits;
2740 return nullptr;
2741 }
2742
2743 // FIXME: could we preserve undef's here?
2744 Type *Ty = X->getType();
2745 Value *XOffset = Builder.CreateAdd(X, ConstantInt::get(Ty, *LowBitMaskCst),
2746 X->getName() + ".biased");
2747 Value *R = Builder.CreateAnd(XOffset, ConstantInt::get(Ty, *HighBitMaskCst));
2748 R->takeName(&SI);
2749 return R;
2750}
2751
2752namespace {
2753struct DecomposedSelect {
2754 Value *Cond = nullptr;
2755 Value *TrueVal = nullptr;
2756 Value *FalseVal = nullptr;
2757};
2758} // namespace
2759
2760/// Look for patterns like
2761/// %outer.cond = select i1 %inner.cond, i1 %alt.cond, i1 false
2762/// %inner.sel = select i1 %inner.cond, i8 %inner.sel.t, i8 %inner.sel.f
2763/// %outer.sel = select i1 %outer.cond, i8 %outer.sel.t, i8 %inner.sel
2764/// and rewrite it as
2765/// %inner.sel = select i1 %cond.alternative, i8 %sel.outer.t, i8 %sel.inner.t
2766/// %sel.outer = select i1 %cond.inner, i8 %inner.sel, i8 %sel.inner.f
2767static Instruction *foldNestedSelects(SelectInst &OuterSelVal,
2768 InstCombiner::BuilderTy &Builder) {
2769 // We must start with a `select`.
2770 DecomposedSelect OuterSel;
2771 match(&OuterSelVal,
2772 m_Select(m_Value(OuterSel.Cond), m_Value(OuterSel.TrueVal),
2773 m_Value(OuterSel.FalseVal)));
2774
2775 // Canonicalize inversion of the outermost `select`'s condition.
2776 if (match(OuterSel.Cond, m_Not(m_Value(OuterSel.Cond))))
2777 std::swap(OuterSel.TrueVal, OuterSel.FalseVal);
2778
2779 // The condition of the outermost select must be an `and`/`or`.
2780 if (!match(OuterSel.Cond, m_c_LogicalOp(m_Value(), m_Value())))
2781 return nullptr;
2782
2783 // Depending on the logical op, inner select might be in different hand.
2784 bool IsAndVariant = match(OuterSel.Cond, m_LogicalAnd());
2785 Value *InnerSelVal = IsAndVariant ? OuterSel.FalseVal : OuterSel.TrueVal;
2786
2787 // Profitability check - avoid increasing instruction count.
2788 if (none_of(ArrayRef<Value *>({OuterSelVal.getCondition(), InnerSelVal}),
2789 [](Value *V) { return V->hasOneUse(); }))
2790 return nullptr;
2791
2792 // The appropriate hand of the outermost `select` must be a select itself.
2793 DecomposedSelect InnerSel;
2794 if (!match(InnerSelVal,
2795 m_Select(m_Value(InnerSel.Cond), m_Value(InnerSel.TrueVal),
2796 m_Value(InnerSel.FalseVal))))
2797 return nullptr;
2798
2799 // Canonicalize inversion of the innermost `select`'s condition.
2800 if (match(InnerSel.Cond, m_Not(m_Value(InnerSel.Cond))))
2801 std::swap(InnerSel.TrueVal, InnerSel.FalseVal);
2802
2803 Value *AltCond = nullptr;
2804 auto matchOuterCond = [OuterSel, &AltCond](auto m_InnerCond) {
2805 return match(OuterSel.Cond, m_c_LogicalOp(m_InnerCond, m_Value(AltCond)));
2806 };
2807
2808 // Finally, match the condition that was driving the outermost `select`,
2809 // it should be a logical operation between the condition that was driving
2810 // the innermost `select` (after accounting for the possible inversions
2811 // of the condition), and some other condition.
2812 if (matchOuterCond(m_Specific(InnerSel.Cond))) {
2813 // Done!
2814 } else if (Value * NotInnerCond; matchOuterCond(m_CombineAnd(
2815 m_Not(m_Specific(InnerSel.Cond)), m_Value(NotInnerCond)))) {
2816 // Done!
2817 std::swap(InnerSel.TrueVal, InnerSel.FalseVal);
2818 InnerSel.Cond = NotInnerCond;
2819 } else // Not the pattern we were looking for.
2820 return nullptr;
2821
2822 Value *SelInner = Builder.CreateSelect(
2823 AltCond, IsAndVariant ? OuterSel.TrueVal : InnerSel.FalseVal,
2824 IsAndVariant ? InnerSel.TrueVal : OuterSel.FalseVal);
2825 SelInner->takeName(InnerSelVal);
2826 return SelectInst::Create(InnerSel.Cond,
2827 IsAndVariant ? SelInner : InnerSel.TrueVal,
2828 !IsAndVariant ? SelInner : InnerSel.FalseVal);
2829}
2830
2832 Value *CondVal = SI.getCondition();
2833 Value *TrueVal = SI.getTrueValue();
2834 Value *FalseVal = SI.getFalseValue();
2835 Type *SelType = SI.getType();
2836
2837 // Avoid potential infinite loops by checking for non-constant condition.
2838 // TODO: Can we assert instead by improving canonicalizeSelectToShuffle()?
2839 // Scalar select must have simplified?
2840 if (!SelType->isIntOrIntVectorTy(1) || isa<Constant>(CondVal) ||
2841 TrueVal->getType() != CondVal->getType())
2842 return nullptr;
2843
2844 auto *One = ConstantInt::getTrue(SelType);
2845 auto *Zero = ConstantInt::getFalse(SelType);
2846 Value *A, *B, *C, *D;
2847
2848 // Folding select to and/or i1 isn't poison safe in general. impliesPoison
2849 // checks whether folding it does not convert a well-defined value into
2850 // poison.
2851 if (match(TrueVal, m_One())) {
2852 if (impliesPoison(FalseVal, CondVal)) {
2853 // Change: A = select B, true, C --> A = or B, C
2854 return BinaryOperator::CreateOr(CondVal, FalseVal);
2855 }
2856
2857 if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
2858 if (auto *RHS = dyn_cast<FCmpInst>(FalseVal))
2859 if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ false,
2860 /*IsSelectLogical*/ true))
2861 return replaceInstUsesWith(SI, V);
2862
2863 // (A && B) || (C && B) --> (A || C) && B
2864 if (match(CondVal, m_LogicalAnd(m_Value(A), m_Value(B))) &&
2865 match(FalseVal, m_LogicalAnd(m_Value(C), m_Value(D))) &&
2866 (CondVal->hasOneUse() || FalseVal->hasOneUse())) {
2867 bool CondLogicAnd = isa<SelectInst>(CondVal);
2868 bool FalseLogicAnd = isa<SelectInst>(FalseVal);
2869 auto AndFactorization = [&](Value *Common, Value *InnerCond,
2870 Value *InnerVal,
2871 bool SelFirst = false) -> Instruction * {
2872 Value *InnerSel = Builder.CreateSelect(InnerCond, One, InnerVal);
2873 if (SelFirst)
2874 std::swap(Common, InnerSel);
2875 if (FalseLogicAnd || (CondLogicAnd && Common == A))
2876 return SelectInst::Create(Common, InnerSel, Zero);
2877 else
2878 return BinaryOperator::CreateAnd(Common, InnerSel);
2879 };
2880
2881 if (A == C)
2882 return AndFactorization(A, B, D);
2883 if (A == D)
2884 return AndFactorization(A, B, C);
2885 if (B == C)
2886 return AndFactorization(B, A, D);
2887 if (B == D)
2888 return AndFactorization(B, A, C, CondLogicAnd && FalseLogicAnd);
2889 }
2890 }
2891
2892 if (match(FalseVal, m_Zero())) {
2893 if (impliesPoison(TrueVal, CondVal)) {
2894 // Change: A = select B, C, false --> A = and B, C
2895 return BinaryOperator::CreateAnd(CondVal, TrueVal);
2896 }
2897
2898 if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
2899 if (auto *RHS = dyn_cast<FCmpInst>(TrueVal))
2900 if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ true,
2901 /*IsSelectLogical*/ true))
2902 return replaceInstUsesWith(SI, V);
2903
2904 // (A || B) && (C || B) --> (A && C) || B
2905 if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
2906 match(TrueVal, m_LogicalOr(m_Value(C), m_Value(D))) &&
2907 (CondVal->hasOneUse() || TrueVal->hasOneUse())) {
2908 bool CondLogicOr = isa<SelectInst>(CondVal);
2909 bool TrueLogicOr = isa<SelectInst>(TrueVal);
2910 auto OrFactorization = [&](Value *Common, Value *InnerCond,
2911 Value *InnerVal,
2912 bool SelFirst = false) -> Instruction * {
2913 Value *InnerSel = Builder.CreateSelect(InnerCond, InnerVal, Zero);
2914 if (SelFirst)
2915 std::swap(Common, InnerSel);
2916 if (TrueLogicOr || (CondLogicOr && Common == A))
2917 return SelectInst::Create(Common, One, InnerSel);
2918 else
2919 return BinaryOperator::CreateOr(Common, InnerSel);
2920 };
2921
2922 if (A == C)
2923 return OrFactorization(A, B, D);
2924 if (A == D)
2925 return OrFactorization(A, B, C);
2926 if (B == C)
2927 return OrFactorization(B, A, D);
2928 if (B == D)
2929 return OrFactorization(B, A, C, CondLogicOr && TrueLogicOr);
2930 }
2931 }
2932
2933 // We match the "full" 0 or 1 constant here to avoid a potential infinite
2934 // loop with vectors that may have undefined/poison elements.
2935 // select a, false, b -> select !a, b, false
2936 if (match(TrueVal, m_Specific(Zero))) {
2937 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2938 return SelectInst::Create(NotCond, FalseVal, Zero);
2939 }
2940 // select a, b, true -> select !a, true, b
2941 if (match(FalseVal, m_Specific(One))) {
2942 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2943 return SelectInst::Create(NotCond, One, TrueVal);
2944 }
2945
2946 // DeMorgan in select form: !a && !b --> !(a || b)
2947 // select !a, !b, false --> not (select a, true, b)
2948 if (match(&SI, m_LogicalAnd(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
2949 (CondVal->hasOneUse() || TrueVal->hasOneUse()) &&
2952
2953 // DeMorgan in select form: !a || !b --> !(a && b)
2954 // select !a, true, !b --> not (select a, b, false)
2955 if (match(&SI, m_LogicalOr(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
2956 (CondVal->hasOneUse() || FalseVal->hasOneUse()) &&
2959
2960 // select (select a, true, b), true, b -> select a, true, b
2961 if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
2962 match(TrueVal, m_One()) && match(FalseVal, m_Specific(B)))
2963 return replaceOperand(SI, 0, A);
2964 // select (select a, b, false), b, false -> select a, b, false
2965 if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
2966 match(TrueVal, m_Specific(B)) && match(FalseVal, m_Zero()))
2967 return replaceOperand(SI, 0, A);
2968
2969 // ~(A & B) & (A | B) --> A ^ B
2972 return BinaryOperator::CreateXor(A, B);
2973
2974 // select (~a | c), a, b -> and a, (or c, freeze(b))
2975 if (match(CondVal, m_c_Or(m_Not(m_Specific(TrueVal)), m_Value(C))) &&
2976 CondVal->hasOneUse()) {
2977 FalseVal = Builder.CreateFreeze(FalseVal);
2978 return BinaryOperator::CreateAnd(TrueVal, Builder.CreateOr(C, FalseVal));
2979 }
2980 // select (~c & b), a, b -> and b, (or freeze(a), c)
2981 if (match(CondVal, m_c_And(m_Not(m_Value(C)), m_Specific(FalseVal))) &&
2982 CondVal->hasOneUse()) {
2983 TrueVal = Builder.CreateFreeze(TrueVal);
2984 return BinaryOperator::CreateAnd(FalseVal, Builder.CreateOr(C, TrueVal));
2985 }
2986
2987 if (match(FalseVal, m_Zero()) || match(TrueVal, m_One())) {
2988 Use *Y = nullptr;
2989 bool IsAnd = match(FalseVal, m_Zero()) ? true : false;
2990 Value *Op1 = IsAnd ? TrueVal : FalseVal;
2991 if (isCheckForZeroAndMulWithOverflow(CondVal, Op1, IsAnd, Y)) {
2992 auto *FI = new FreezeInst(*Y, (*Y)->getName() + ".fr");
2993 InsertNewInstBefore(FI, *cast<Instruction>(Y->getUser()));
2994 replaceUse(*Y, FI);
2995 return replaceInstUsesWith(SI, Op1);
2996 }
2997
2998 if (auto *Op1SI = dyn_cast<SelectInst>(Op1))
2999 if (auto *I = foldAndOrOfSelectUsingImpliedCond(CondVal, *Op1SI,
3000 /* IsAnd */ IsAnd))
3001 return I;
3002
3003 if (auto *ICmp0 = dyn_cast<ICmpInst>(CondVal))
3004 if (auto *ICmp1 = dyn_cast<ICmpInst>(Op1))
3005 if (auto *V = foldAndOrOfICmps(ICmp0, ICmp1, SI, IsAnd,
3006 /* IsLogical */ true))
3007 return replaceInstUsesWith(SI, V);
3008 }
3009
3010 // select (a || b), c, false -> select a, c, false
3011 // select c, (a || b), false -> select c, a, false
3012 // if c implies that b is false.
3013 if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
3014 match(FalseVal, m_Zero())) {
3015 std::optional<bool> Res = isImpliedCondition(TrueVal, B, DL);
3016 if (Res && *Res == false)
3017 return replaceOperand(SI, 0, A);
3018 }
3019 if (match(TrueVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
3020 match(FalseVal, m_Zero())) {
3021 std::optional<bool> Res = isImpliedCondition(CondVal, B, DL);
3022 if (Res && *Res == false)
3023 return replaceOperand(SI, 1, A);
3024 }
3025 // select c, true, (a && b) -> select c, true, a
3026 // select (a && b), true, c -> select a, true, c
3027 // if c = false implies that b = true
3028 if (match(TrueVal, m_One()) &&
3029 match(FalseVal, m_LogicalAnd(m_Value(A), m_Value(B)))) {
3030 std::optional<bool> Res = isImpliedCondition(CondVal, B, DL, false);
3031 if (Res && *Res == true)
3032 return replaceOperand(SI, 2, A);
3033 }
3034 if (match(CondVal, m_LogicalAnd(m_Value(A), m_Value(B))) &&
3035 match(TrueVal, m_One())) {
3036 std::optional<bool> Res = isImpliedCondition(FalseVal, B, DL, false);
3037 if (Res && *Res == true)
3038 return replaceOperand(SI, 0, A);
3039 }
3040
3041 if (match(TrueVal, m_One())) {
3042 Value *C;
3043
3044 // (C && A) || (!C && B) --> sel C, A, B
3045 // (A && C) || (!C && B) --> sel C, A, B
3046 // (C && A) || (B && !C) --> sel C, A, B
3047 // (A && C) || (B && !C) --> sel C, A, B (may require freeze)
3048 if (match(FalseVal, m_c_LogicalAnd(m_Not(m_Value(C)), m_Value(B))) &&
3049 match(CondVal, m_c_LogicalAnd(m_Specific(C), m_Value(A)))) {
3050 auto *SelCond = dyn_cast<SelectInst>(CondVal);
3051 auto *SelFVal = dyn_cast<SelectInst>(FalseVal);
3052 bool MayNeedFreeze = SelCond && SelFVal &&
3053 match(SelFVal->getTrueValue(),
3054 m_Not(m_Specific(SelCond->getTrueValue())));
3055 if (MayNeedFreeze)
3057 return SelectInst::Create(C, A, B);
3058 }
3059
3060 // (!C && A) || (C && B) --> sel C, B, A
3061 // (A && !C) || (C && B) --> sel C, B, A
3062 // (!C && A) || (B && C) --> sel C, B, A
3063 // (A && !C) || (B && C) --> sel C, B, A (may require freeze)
3064 if (match(CondVal, m_c_LogicalAnd(m_Not(m_Value(C)), m_Value(A))) &&
3065 match(FalseVal, m_c_LogicalAnd(m_Specific(C), m_Value(B)))) {
3066 auto *SelCond = dyn_cast<SelectInst>(CondVal);
3067 auto *SelFVal = dyn_cast<SelectInst>(FalseVal);
3068 bool MayNeedFreeze = SelCond && SelFVal &&
3069 match(SelCond->getTrueValue(),
3070 m_Not(m_Specific(SelFVal->getTrueValue())));
3071 if (MayNeedFreeze)
3073 return SelectInst::Create(C, B, A);
3074 }
3075 }
3076
3077 return nullptr;
3078}
3079
3081 Value *CondVal = SI.getCondition();
3082 Value *TrueVal = SI.getTrueValue();
3083 Value *FalseVal = SI.getFalseValue();
3084 Type *SelType = SI.getType();
3085
3086 if (Value *V = simplifySelectInst(CondVal, TrueVal, FalseVal,
3087 SQ.getWithInstruction(&SI)))
3088 return replaceInstUsesWith(SI, V);
3089
3090 if (Instruction *I = canonicalizeSelectToShuffle(SI))
3091 return I;
3092
3093 if (Instruction *I = canonicalizeScalarSelectOfVecs(SI, *this))
3094 return I;
3095
3096 // If the type of select is not an integer type or if the condition and
3097 // the selection type are not both scalar nor both vector types, there is no
3098 // point in attempting to match these patterns.
3099 Type *CondType = CondVal->getType();
3100 if (!isa<Constant>(CondVal) && SelType->isIntOrIntVectorTy() &&
3101 CondType->isVectorTy() == SelType->isVectorTy()) {
3102 if (Value *S = simplifyWithOpReplaced(TrueVal, CondVal,
3103 ConstantInt::getTrue(CondType), SQ,
3104 /* AllowRefinement */ true))
3105 return replaceOperand(SI, 1, S);
3106
3107 if (Value *S = simplifyWithOpReplaced(FalseVal, CondVal,
3108 ConstantInt::getFalse(CondType), SQ,
3109 /* AllowRefinement */ true))
3110 return replaceOperand(SI, 2, S);
3111
3112 // Handle patterns involving sext/zext + not explicitly,
3113 // as simplifyWithOpReplaced() only looks past one instruction.
3114 Value *NotCond;
3115
3116 // select a, sext(!a), b -> select !a, b, 0
3117 // select a, zext(!a), b -> select !a, b, 0
3118 if (match(TrueVal, m_ZExtOrSExt(m_CombineAnd(m_Value(NotCond),
3119 m_Not(m_Specific(CondVal))))))
3120 return SelectInst::Create(NotCond, FalseVal,
3121 Constant::getNullValue(SelType));
3122
3123 // select a, b, zext(!a) -> select !a, 1, b
3124 if (match(FalseVal, m_ZExt(m_CombineAnd(m_Value(NotCond),
3125 m_Not(m_Specific(CondVal))))))
3126 return SelectInst::Create(NotCond, ConstantInt::get(SelType, 1), TrueVal);
3127
3128 // select a, b, sext(!a) -> select !a, -1, b
3129 if (match(FalseVal, m_SExt(m_CombineAnd(m_Value(NotCond),
3130 m_Not(m_Specific(CondVal))))))
3131 return SelectInst::Create(NotCond, Constant::getAllOnesValue(SelType),
3132 TrueVal);
3133 }
3134
3135 if (Instruction *R = foldSelectOfBools(SI))
3136 return R;
3137
3138 // Selecting between two integer or vector splat integer constants?
3139 //
3140 // Note that we don't handle a scalar select of vectors:
3141 // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>
3142 // because that may need 3 instructions to splat the condition value:
3143 // extend, insertelement, shufflevector.
3144 //
3145 // Do not handle i1 TrueVal and FalseVal otherwise would result in
3146 // zext/sext i1 to i1.
3147 if (SelType->isIntOrIntVectorTy() && !SelType->isIntOrIntVectorTy(1) &&
3148 CondVal->getType()->isVectorTy() == SelType->isVectorTy()) {
3149 // select C, 1, 0 -> zext C to int
3150 if (match(TrueVal, m_One()) && match(FalseVal, m_Zero()))
3151 return new ZExtInst(CondVal, SelType);
3152
3153 // select C, -1, 0 -> sext C to int
3154 if (match(TrueVal, m_AllOnes()) && match(FalseVal, m_Zero()))
3155 return new SExtInst(CondVal, SelType);
3156
3157 // select C, 0, 1 -> zext !C to int
3158 if (match(TrueVal, m_Zero()) && match(FalseVal, m_One())) {
3159 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
3160 return new ZExtInst(NotCond, SelType);
3161 }
3162
3163 // select C, 0, -1 -> sext !C to int
3164 if (match(TrueVal, m_Zero()) && match(FalseVal, m_AllOnes())) {
3165 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
3166 return new SExtInst(NotCond, SelType);
3167 }
3168 }
3169
3170 if (auto *FCmp = dyn_cast<FCmpInst>(CondVal)) {
3171 Value *Cmp0 = FCmp->getOperand(0), *Cmp1 = FCmp->getOperand(1);
3172 // Are we selecting a value based on a comparison of the two values?
3173 if ((Cmp0 == TrueVal && Cmp1 == FalseVal) ||
3174 (Cmp0 == FalseVal && Cmp1 == TrueVal)) {
3175 // Canonicalize to use ordered comparisons by swapping the select
3176 // operands.
3177 //
3178 // e.g.
3179 // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X
3180 if (FCmp->hasOneUse() && FCmpInst::isUnordered(FCmp->getPredicate())) {
3181 FCmpInst::Predicate InvPred = FCmp->getInversePredicate();
3183 // FIXME: The FMF should propagate from the select, not the fcmp.
3184 Builder.setFastMathFlags(FCmp->getFastMathFlags());
3185 Value *NewCond = Builder.CreateFCmp(InvPred, Cmp0, Cmp1,
3186 FCmp->getName() + ".inv");
3187 Value *NewSel = Builder.CreateSelect(NewCond, FalseVal, TrueVal);
3188 return replaceInstUsesWith(SI, NewSel);
3189 }
3190 }
3191 }
3192
3193 if (isa<FPMathOperator>(SI)) {
3194 // TODO: Try to forward-propagate FMF from select arms to the select.
3195
3196 // Canonicalize select of FP values where NaN and -0.0 are not valid as
3197 // minnum/maxnum intrinsics.
3198 if (SI.hasNoNaNs() && SI.hasNoSignedZeros()) {
3199 Value *X, *Y;
3200 if (match(&SI, m_OrdFMax(m_Value(X), m_Value(Y))))
3201 return replaceInstUsesWith(
3202 SI, Builder.CreateBinaryIntrinsic(Intrinsic::maxnum, X, Y, &SI));
3203
3204 if (match(&SI, m_OrdFMin(m_Value(X), m_Value(Y))))
3205 return replaceInstUsesWith(
3206 SI, Builder.CreateBinaryIntrinsic(Intrinsic::minnum, X, Y, &SI));
3207 }
3208 }
3209
3210 // Fold selecting to fabs.
3211 if (Instruction *Fabs = foldSelectWithFCmpToFabs(SI, *this))
3212 return Fabs;
3213
3214 // See if we are selecting two values based on a comparison of the two values.
3215 if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal))
3216 if (Instruction *Result = foldSelectInstWithICmp(SI, ICI))
3217 return Result;
3218
3219 if (Instruction *Add = foldAddSubSelect(SI, Builder))
3220 return Add;
3221 if (Instruction *Add = foldOverflowingAddSubSelect(SI, Builder))
3222 return Add;
3224 return Or;
3225 if (Instruction *Mul = foldSelectZeroOrMul(SI, *this))
3226 return Mul;
3227
3228 // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
3229 auto *TI = dyn_cast<Instruction>(TrueVal);
3230 auto *FI = dyn_cast<Instruction>(FalseVal);
3231 if (TI && FI && TI->getOpcode() == FI->getOpcode())
3232 if (Instruction *IV = foldSelectOpOp(SI, TI, FI))
3233 return IV;
3234
3235 if (Instruction *I = foldSelectExtConst(SI))
3236 return I;
3237
3238 // Fold (select C, (gep Ptr, Idx), Ptr) -> (gep Ptr, (select C, Idx, 0))
3239 // Fold (select C, Ptr, (gep Ptr, Idx)) -> (gep Ptr, (select C, 0, Idx))
3240 auto SelectGepWithBase = [&](GetElementPtrInst *Gep, Value *Base,
3241 bool Swap) -> GetElementPtrInst * {
3242 Value *Ptr = Gep->getPointerOperand();
3243 if (Gep->getNumOperands() != 2 || Gep->getPointerOperand() != Base ||
3244 !Gep->hasOneUse())
3245 return nullptr;
3246 Value *Idx = Gep->getOperand(1);
3247 if (isa<VectorType>(CondVal->getType()) && !isa<VectorType>(Idx->getType()))
3248 return nullptr;
3249 Type *ElementType = Gep->getResultElementType();
3250 Value *NewT = Idx;
3251 Value *NewF = Constant::getNullValue(Idx->getType());
3252 if (Swap)
3253 std::swap(NewT, NewF);
3254 Value *NewSI =
3255 Builder.CreateSelect(CondVal, NewT, NewF, SI.getName() + ".idx", &SI);
3256 return GetElementPtrInst::Create(ElementType, Ptr, {NewSI});
3257 };
3258 if (auto *TrueGep = dyn_cast<GetElementPtrInst>(TrueVal))
3259 if (auto *NewGep = SelectGepWithBase(TrueGep, FalseVal, false))
3260 return NewGep;
3261 if (auto *FalseGep = dyn_cast<GetElementPtrInst>(FalseVal))
3262 if (auto *NewGep = SelectGepWithBase(FalseGep, TrueVal, true))
3263 return NewGep;
3264
3265 // See if we can fold the select into one of our operands.
3266 if (SelType->isIntOrIntVectorTy() || SelType->isFPOrFPVectorTy()) {
3267 if (Instruction *FoldI = foldSelectIntoOp(SI, TrueVal, FalseVal))
3268 return FoldI;
3269
3270 Value *LHS, *RHS;
3271 Instruction::CastOps CastOp;
3272 SelectPatternResult SPR = matchSelectPattern(&SI, LHS, RHS, &CastOp);
3273 auto SPF = SPR.Flavor;
3274 if (SPF) {
3275 Value *LHS2, *RHS2;
3276 if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor)
3277 if (Instruction *R = foldSPFofSPF(cast<Instruction>(LHS), SPF2, LHS2,
3278 RHS2, SI, SPF, RHS))
3279 return R;
3280 if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor)
3281 if (Instruction *R = foldSPFofSPF(cast<Instruction>(RHS), SPF2, LHS2,
3282 RHS2, SI, SPF, LHS))
3283 return R;
3284 }
3285
3287 // Canonicalize so that
3288 // - type casts are outside select patterns.
3289 // - float clamp is transformed to min/max pattern
3290
3291 bool IsCastNeeded = LHS->getType() != SelType;
3292 Value *CmpLHS = cast<CmpInst>(CondVal)->getOperand(0);
3293 Value *CmpRHS = cast<CmpInst>(CondVal)->getOperand(1);
3294 if (IsCastNeeded ||
3295 (LHS->getType()->isFPOrFPVectorTy() &&
3296 ((CmpLHS != LHS && CmpLHS != RHS) ||
3297 (CmpRHS != LHS && CmpRHS != RHS)))) {
3298 CmpInst::Predicate MinMaxPred = getMinMaxPred(SPF, SPR.Ordered);
3299
3300 Value *Cmp;
3301 if (CmpInst::isIntPredicate(MinMaxPred)) {
3302 Cmp = Builder.CreateICmp(MinMaxPred, LHS, RHS);
3303 } else {
3305 auto FMF =
3306 cast<FPMathOperator>(SI.getCondition())->getFastMathFlags();
3308 Cmp = Builder.CreateFCmp(MinMaxPred, LHS, RHS);
3309 }
3310
3311 Value *NewSI = Builder.CreateSelect(Cmp, LHS, RHS, SI.getName(), &SI);
3312 if (!IsCastNeeded)
3313 return replaceInstUsesWith(SI, NewSI);
3314
3315 Value *NewCast = Builder.CreateCast(CastOp, NewSI, SelType);
3316 return replaceInstUsesWith(SI, NewCast);
3317 }
3318 }
3319 }
3320
3321 // See if we can fold the select into a phi node if the condition is a select.
3322 if (auto *PN = dyn_cast<PHINode>(SI.getCondition()))
3323 // The true/false values have to be live in the PHI predecessor's blocks.
3324 if (canSelectOperandBeMappingIntoPredBlock(TrueVal, SI) &&
3325 canSelectOperandBeMappingIntoPredBlock(FalseVal, SI))
3326 if (Instruction *NV = foldOpIntoPhi(SI, PN))
3327 return NV;
3328
3329 if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) {
3330 if (TrueSI->getCondition()->getType() == CondVal->getType()) {
3331 // select(C, select(C, a, b), c) -> select(C, a, c)
3332 if (TrueSI->getCondition() == CondVal) {
3333 if (SI.getTrueValue() == TrueSI->getTrueValue())
3334 return nullptr;
3335 return replaceOperand(SI, 1, TrueSI->getTrueValue());
3336 }
3337 // select(C0, select(C1, a, b), b) -> select(C0&C1, a, b)
3338 // We choose this as normal form to enable folding on the And and
3339 // shortening paths for the values (this helps getUnderlyingObjects() for
3340 // example).
3341 if (TrueSI->getFalseValue() == FalseVal && TrueSI->hasOneUse()) {
3342 Value *And = Builder.CreateLogicalAnd(CondVal, TrueSI->getCondition());
3343 replaceOperand(SI, 0, And);
3344 replaceOperand(SI, 1, TrueSI->getTrueValue());
3345 return &SI;
3346 }
3347 }
3348 }
3349 if (SelectInst *FalseSI = dyn_cast<SelectInst>(FalseVal)) {
3350 if (FalseSI->getCondition()->getType() == CondVal->getType()) {
3351 // select(C, a, select(C, b, c)) -> select(C, a, c)
3352 if (FalseSI->getCondition() == CondVal) {
3353 if (SI.getFalseValue() == FalseSI->getFalseValue())
3354 return nullptr;
3355 return replaceOperand(SI, 2, FalseSI->getFalseValue());
3356 }
3357 // select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b)
3358 if (FalseSI->getTrueValue() == TrueVal && FalseSI->hasOneUse()) {
3359 Value *Or = Builder.CreateLogicalOr(CondVal, FalseSI->getCondition());
3360 replaceOperand(SI, 0, Or);
3361 replaceOperand(SI, 2, FalseSI->getFalseValue());
3362 return &SI;
3363 }
3364 }
3365 }
3366
3367 auto canMergeSelectThroughBinop = [](BinaryOperator *BO) {
3368 // The select might be preventing a division by 0.
3369 switch (BO->getOpcode()) {
3370 default:
3371 return true;
3372 case Instruction::SRem:
3373 case Instruction::URem:
3374 case Instruction::SDiv:
3375 case Instruction::UDiv:
3376 return false;
3377 }
3378 };
3379
3380 // Try to simplify a binop sandwiched between 2 selects with the same
3381 // condition.
3382 // select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z)
3383 BinaryOperator *TrueBO;
3384 if (match(TrueVal, m_OneUse(m_BinOp(TrueBO))) &&
3385 canMergeSelectThroughBinop(TrueBO)) {
3386 if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(0))) {
3387 if (TrueBOSI->getCondition() == CondVal) {
3388 replaceOperand(*TrueBO, 0, TrueBOSI->getTrueValue());
3389 Worklist.push(TrueBO);
3390 return &SI;
3391 }
3392 }
3393 if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(1))) {
3394 if (TrueBOSI->getCondition() == CondVal) {
3395 replaceOperand(*TrueBO, 1, TrueBOSI->getTrueValue());
3396 Worklist.push(TrueBO);
3397 return &SI;
3398 }
3399 }
3400 }
3401
3402 // select(C, Z, binop(select(C, X, Y), W)) -> select(C, Z, binop(Y, W))
3403 BinaryOperator *FalseBO;
3404 if (match(FalseVal, m_OneUse(m_BinOp(FalseBO))) &&
3405 canMergeSelectThroughBinop(FalseBO)) {
3406 if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(0))) {
3407 if (FalseBOSI->getCondition() == CondVal) {
3408 replaceOperand(*FalseBO, 0, FalseBOSI->getFalseValue());
3409 Worklist.push(FalseBO);
3410 return &SI;
3411 }
3412 }
3413 if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(1))) {
3414 if (FalseBOSI->getCondition() == CondVal) {
3415 replaceOperand(*FalseBO, 1, FalseBOSI->getFalseValue());
3416 Worklist.push(FalseBO);
3417 return &SI;
3418 }
3419 }
3420 }
3421
3422 Value *NotCond;
3423 if (match(CondVal, m_Not(m_Value(NotCond))) &&
3425 replaceOperand(SI, 0, NotCond);
3426 SI.swapValues();
3427 SI.swapProfMetadata();
3428 return &SI;
3429 }
3430
3431 if (Instruction *I = foldVectorSelect(SI))
3432 return I;
3433
3434 // If we can compute the condition, there's no need for a select.
3435 // Like the above fold, we are attempting to reduce compile-time cost by
3436 // putting this fold here with limitations rather than in InstSimplify.
3437 // The motivation for this call into value tracking is to take advantage of
3438 // the assumption cache, so make sure that is populated.
3439 if (!CondVal->getType()->isVectorTy() && !AC.assumptions().empty()) {
3440 KnownBits Known(1);
3441 computeKnownBits(CondVal, Known, 0, &SI);
3442 if (Known.One.isOne())
3443 return replaceInstUsesWith(SI, TrueVal);
3444 if (Known.Zero.isOne())
3445 return replaceInstUsesWith(SI, FalseVal);
3446 }
3447
3448 if (Instruction *BitCastSel = foldSelectCmpBitcasts(SI, Builder))
3449 return BitCastSel;
3450
3451 // Simplify selects that test the returned flag of cmpxchg instructions.
3452 if (Value *V = foldSelectCmpXchg(SI))
3453 return replaceInstUsesWith(SI, V);
3454
3455 if (Instruction *Select = foldSelectBinOpIdentity(SI, TLI, *this))
3456 return Select;
3457
3458 if (Instruction *Funnel = foldSelectFunnelShift(SI, Builder))
3459 return Funnel;
3460
3461 if (Instruction *Copysign = foldSelectToCopysign(SI, Builder))
3462 return Copysign;
3463
3464 if (Instruction *PN = foldSelectToPhi(SI, DT, Builder))
3465 return replaceInstUsesWith(SI, PN);
3466
3467 if (Value *Fr = foldSelectWithFrozenICmp(SI, Builder))
3468 return replaceInstUsesWith(SI, Fr);
3469
3470 if (Value *V = foldRoundUpIntegerWithPow2Alignment(SI, Builder))
3471 return replaceInstUsesWith(SI, V);
3472
3473 // select(mask, mload(,,mask,0), 0) -> mload(,,mask,0)
3474 // Load inst is intentionally not checked for hasOneUse()
3475 if (match(FalseVal, m_Zero()) &&
3476 (match(TrueVal, m_MaskedLoad(m_Value(), m_Value(), m_Specific(CondVal),
3477 m_CombineOr(m_Undef(), m_Zero()))) ||
3478 match(TrueVal, m_MaskedGather(m_Value(), m_Value(), m_Specific(CondVal),
3479 m_CombineOr(m_Undef(), m_Zero()))))) {
3480 auto *MaskedInst = cast<IntrinsicInst>(TrueVal);
3481 if (isa<UndefValue>(MaskedInst->getArgOperand(3)))
3482 MaskedInst->setArgOperand(3, FalseVal /* Zero */);
3483 return replaceInstUsesWith(SI, MaskedInst);
3484 }
3485
3486 Value *Mask;
3487 if (match(TrueVal, m_Zero()) &&
3488 (match(FalseVal, m_MaskedLoad(m_Value(), m_Value(), m_Value(Mask),
3489 m_CombineOr(m_Undef(), m_Zero()))) ||
3490 match(FalseVal, m_MaskedGather(m_Value(), m_Value(), m_Value(Mask),
3491 m_CombineOr(m_Undef(), m_Zero())))) &&
3492 (CondVal->getType() == Mask->getType())) {
3493 // We can remove the select by ensuring the load zeros all lanes the
3494 // select would have. We determine this by proving there is no overlap
3495 // between the load and select masks.
3496 // (i.e (load_mask & select_mask) == 0 == no overlap)
3497 bool CanMergeSelectIntoLoad = false;
3498 if (Value *V = simplifyAndInst(CondVal, Mask, SQ.getWithInstruction(&SI)))
3499 CanMergeSelectIntoLoad = match(V, m_Zero());
3500
3501 if (CanMergeSelectIntoLoad) {
3502 auto *MaskedInst = cast<IntrinsicInst>(FalseVal);
3503 if (isa<UndefValue>(MaskedInst->getArgOperand(3)))
3504 MaskedInst->setArgOperand(3, TrueVal /* Zero */);
3505 return replaceInstUsesWith(SI, MaskedInst);
3506 }
3507 }
3508
3509 if (Instruction *I = foldNestedSelects(SI, Builder))
3510 return I;
3511
3512 // Match logical variants of the pattern,
3513 // and transform them iff that gets rid of inversions.
3514 // (~x) | y --> ~(x & (~y))
3515 // (~x) & y --> ~(x | (~y))
3517 return &SI;
3518
3519 return nullptr;
3520}
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
amdgpu AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
assume Assume Builder
basic Basic Alias true
SmallVector< MachineOperand, 4 > Cond
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Hexagon Common GEP
const HexagonInstrInfo * TII
static cl::opt< bool > NeedAnd("extract-needand", cl::init(true), cl::Hidden, cl::desc("Require & in extract patterns"))
This file provides internal interfaces used to implement the InstCombine.
static Value * canonicalizeSaturatedAdd(ICmpInst *Cmp, Value *TVal, Value *FVal, InstCombiner::BuilderTy &Builder)
static Instruction * foldSetClearBits(SelectInst &Sel, InstCombiner::BuilderTy &Builder)
Canonicalize a set or clear of a masked set of constant bits to select-of-constants form.
static Instruction * foldSelectICmpAndAnd(Type *SelType, const ICmpInst *Cmp, Value *TVal, Value *FVal, InstCombiner::BuilderTy &Builder)
We want to turn: (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1) into: zext (icmp ne i32 (a...
static unsigned getSelectFoldableOperands(BinaryOperator *I)
We want to turn code that looks like this: C = or A, B D = select cond, C, A into: C = select cond,...
static Instruction * foldSelectZeroOrMul(SelectInst &SI, InstCombinerImpl &IC)
static Value * canonicalizeSaturatedSubtract(const ICmpInst *ICI, const Value *TrueVal, const Value *FalseVal, InstCombiner::BuilderTy &Builder)
Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b).
static Value * foldSelectICmpAndOr(const ICmpInst *IC, Value *TrueVal, Value *FalseVal, InstCombiner::BuilderTy &Builder)
We want to turn: (select (icmp eq (and X, C1), 0), Y, (or Y, C2)) into: (or (shl (and X,...
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 * foldSelectICmpLshrAshr(const ICmpInst *IC, Value *TrueVal, Value *FalseVal, InstCombiner::BuilderTy &Builder)
We want to turn: (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1 (select (icmp slt x...
static bool isSelect01(const APInt &C1I, const APInt &C2I)
static Value * foldSelectICmpAnd(SelectInst &Sel, ICmpInst *Cmp, InstCombiner::BuilderTy &Builder)
This folds: select (icmp eq (and X, C1)), TC, FC iff C1 is a power 2 and the difference between TC an...
This file provides the interface for the instcombine pass implementation.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallVector class.
Value * RHS
Value * LHS
static const uint32_t IV[8]
Definition: blake3_impl.h:85
bool bitwiseIsEqual(const APFloat &RHS) const
Definition: APFloat.h:1195
bool isNegative() const
Definition: APFloat.h:1230
Class for arbitrary precision integers.
Definition: APInt.h:75
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:354
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1160
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:366
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1439
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
unsigned logBase2() const
Definition: APInt.h:1700
bool isMask(unsigned numBits) const
Definition: APInt.h:476
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:432
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition: APInt.h:177
bool isOne() const
Determine if this is a value of 1.
Definition: APInt.h:378
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:222
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
An instruction that atomically checks whether a specified value is in a memory location,...
Definition: Instructions.h:513
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:314
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:127
Value * getRHS() const
Value * getLHS() const
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
static BinaryOperator * CreateNeg(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...
BinaryOps getOpcode() const
Definition: InstrTypes.h:391
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1351
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1356
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:747
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:748
@ FCMP_OLT
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:724
@ FCMP_ULE
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:733
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:722
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:723
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:742
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:741
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:745
@ FCMP_ULT
1 1 0 0 True if unordered or less than
Definition: InstrTypes.h:732
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:743
@ FCMP_UGT
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:730
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:725
@ ICMP_EQ
equal
Definition: InstrTypes.h:739
@ ICMP_NE
not equal
Definition: InstrTypes.h:740
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:746
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:744
@ FCMP_UGE
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:731
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:859
bool isFPPredicate() const
Definition: InstrTypes.h:825
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:832
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:808
static bool isUnordered(Predicate predicate)
Determine if the predicate is an unordered operation.
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
Definition: InstrTypes.h:925
bool isIntPredicate() const
Definition: InstrTypes.h:826
bool isUnsigned() const
Definition: InstrTypes.h:963
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
Definition: Constants.cpp:1973
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2664
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2119
static Constant * getICmp(unsigned short pred, Constant *LHS, Constant *RHS, bool OnlyIfReduced=false)
get* - Return some common constants without having to specify the full Instruction::OPCODE identifier...
Definition: Constants.cpp:2523
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2105
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2741
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2091
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2644
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:934
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:835
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:887
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:842
This class represents a range of values.
Definition: ConstantRange.h:47
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * mergeUndefsWith(Constant *C, Constant *Other)
Merges undefs of a Constant with another Constant, along with the undefs already present.
Definition: Constants.cpp:779
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:403
bool isOneValue() const
Returns true if the value is one.
Definition: Constants.cpp:110
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:356
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:418
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:76
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:676
unsigned size() const
Definition: DenseMap.h:99
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
Convenience struct for specifying and reasoning about fast-math flags.
Definition: FMF.h:21
bool noSignedZeros() const
Definition: FMF.h:69
bool noInfs() const
Definition: FMF.h:68
bool noNaNs() const
Definition: FMF.h:67
This class represents a freeze function that returns random concrete value if an operand is either a ...
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:940
static GetElementPtrInst * CreateInBounds(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Create an "inbounds" getelementptr.
Definition: Instructions.h:993
Type * getResultElementType() const
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:966
This instruction compares its operands according to the predicate given to the constructor.
bool isEquality() const
Return true if this predicate is either EQ or NE.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
CallInst * CreateUnaryIntrinsic(Intrinsic::ID ID, Value *V, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with 1 operand which is mangled on its type.
Definition: IRBuilder.cpp:948
Value * CreateFCmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2242
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Definition: IRBuilder.cpp:1249
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1126
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2416
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
Definition: IRBuilder.h:297
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1664
Value * CreateIsNeg(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg < 0.
Definition: IRBuilder.h:2435
CallInst * CreateBinaryIntrinsic(Intrinsic::ID ID, Value *LHS, Value *RHS, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with 2 operands which is mangled on the first type.
Definition: IRBuilder.cpp:956
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1390
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1412
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
Definition: IRBuilder.h:1591
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2045
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2232
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Definition: IRBuilder.h:1597
Instruction * foldOpIntoPhi(Instruction &I, PHINode *PN)
Given a binary operator, cast instruction, or select which has a PHI node as operand #0,...
Value * SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts, unsigned Depth=0, bool AllowMultipleUsers=false) override
The specified value produces a vector with any number of elements.
Instruction * foldVectorSelect(SelectInst &Sel)
Instruction * foldSelectValueEquivalence(SelectInst &SI, ICmpInst &ICI)
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.
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.
Instruction * visitSelectInst(SelectInst &SI)
Instruction * foldSelectOfBools(SelectInst &SI)
Instruction * foldSelectExtConst(SelectInst &Sel)
The core instruction combiner logic.
Definition: InstCombiner.h:45
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
Definition: InstCombiner.h:145
TargetLibraryInfo & TLI
Definition: InstCombiner.h:71
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombiner.h:418
static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
Definition: InstCombiner.h:218
static std::optional< std::pair< CmpInst::Predicate, Constant * > > getFlippedStrictnessPredicateAndConstant(CmpInst::Predicate Pred, Constant *C)
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
Definition: InstCombiner.h:449
const SimplifyQuery SQ
Definition: InstCombiner.h:74
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
Definition: InstCombiner.h:62
const DataLayout & DL
Definition: InstCombiner.h:73
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
Definition: InstCombiner.h:397
AssumptionCache & AC
Definition: InstCombiner.h:70
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
Definition: InstCombiner.h:442
DominatorTree & DT
Definition: InstCombiner.h:72
static 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.
Definition: InstCombiner.h:165
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:461
BuilderTy & Builder
Definition: InstCombiner.h:58
static Constant * AddOne(Constant *C)
Add one to a Constant.
Definition: InstCombiner.h:202
void push(Instruction *I)
Push the instruction onto the worklist stack.
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const LLVM_READONLY
This function determines if the specified instruction executes the same operation as the current one.
bool isCast() const
Definition: Instruction.h:176
bool hasNoSignedZeros() const LLVM_READONLY
Determine whether the no-signed-zeros flag is set.
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:70
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
void setFastMathFlags(FastMathFlags FMF)
Convenience function for setting multiple fast-math flags on this instruction, which must be an opera...
const BasicBlock * getParent() const
Definition: Instruction.h:90
void swapProfMetadata()
If the instruction has "branch_weights" MD_prof metadata and the MDNode has three operands (including...
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:168
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:54
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
This class represents a sign extension of integer types.
This class represents the LLVM 'select' instruction.
const Value * getFalseValue() const
void swapValues()
Swap the true and false values of the select instruction.
const Value * getCondition() const
const Value * getTrueValue() const
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
This instruction constructs a fixed permutation of two input vectors.
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:301
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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:258
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:228
static IntegerType * getInt1Ty(LLVMContext &C)
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isFPOrFPVectorTy() const
Return true if this is a FP type or a vector of FP.
Definition: Type.h:210
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:341
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:242
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
Value * getOperand(unsigned i) const
Definition: User.h:169
unsigned getNumOperands() const
Definition: User.h:191
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
const Value * DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) const
Translate PHI node to its predecessor from the given basic block.
Definition: Value.cpp:986
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:381
Represents an op.with.overflow intrinsic.
This class represents zero extension of integer types.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1502
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:453
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
specific_intval< false > m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:854
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, OpTy > m_ZExtOrSelf(const OpTy &Op)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:84
apfloat_match m_APFloatAllowUndef(const APFloat *&Res)
Match APFloat while allowing undefs in splat vector constants.
Definition: PatternMatch.h:301
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
apint_match m_APIntAllowUndef(const APInt *&Res)
Match APInt while allowing undefs in splat vector constants.
Definition: PatternMatch.h:284
CastClass_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:997
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:544
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:144
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.
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:716
cstfp_pred_ty< is_any_zero_fp > m_AnyZeroFP()
Match a floating-point negative zero or positive zero.
Definition: PatternMatch.h:664
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:772
constantexpr_match m_ConstantExpr()
Match a constant expression or a constant that contains a constant expression.
Definition: PatternMatch.h:165
OverflowingBinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWNeg(const ValTy &V)
Matches a 'Neg' as 'sub nsw 0, V'.
TwoOps_match< Val_t, Idx_t, Instruction::ExtractElement > m_ExtractElt(const Val_t &Val, const Idx_t &Idx)
Matches ExtractElementInst.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:147
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:517
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
BinOpPred_match< LHS, RHS, is_logical_shift_op > m_LogicalShift(const LHS &L, const RHS &R)
Matches logical shift operations.
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:224
MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
Definition: PatternMatch.h:444
CmpClass_match< LHS, RHS, FCmpInst, FCmpInst::Predicate > m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R)
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
Definition: PatternMatch.h:722
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
Definition: PatternMatch.h:790
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
Definition: PatternMatch.h:524
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:751
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
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.
match_combine_or< CastClass_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty > m_UMax(const LHS &L, const RHS &R)
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:89
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
auto m_c_LogicalOp(const LHS &L, const RHS &R)
Matches either L && R or L || R with LHS and RHS in either order.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate, true > m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
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< CastClass_match< OpTy, Instruction::ZExt >, CastClass_match< OpTy, Instruction::SExt > > m_ZExtOrSExt(const OpTy &Op)
MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:278
MaxMin_match< FCmpInst, LHS, RHS, ofmax_pred_ty > m_OrdFMax(const LHS &L, const RHS &R)
Match an 'ordered' floating point maximum function.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
cstfp_pred_ty< is_pos_zero_fp > m_PosZeroFP()
Match a floating-point positive zero.
Definition: PatternMatch.h:673
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.
m_Intrinsic_Ty< Opnd0 >::Ty m_VecReverse(const Opnd0 &Op0)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
MaxMin_match< FCmpInst, LHS, RHS, ofmin_pred_ty > m_OrdFMin(const LHS &L, const RHS &R)
Match an 'ordered' floating point minimum function.
match_combine_or< match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > >, match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > > > m_MaxOrMin(const LHS &L, const RHS &R)
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
Definition: PatternMatch.h:168
auto m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:136
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:537
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.
BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)
Matches a Mul with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:991
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
m_Intrinsic_Ty< Opnd0, Opnd1, Opnd2, Opnd3 >::Ty m_MaskedGather(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2, const Opnd3 &Op3)
Matches MaskedGather Intrinsic.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:218
cst_pred_ty< icmp_pred_with_threshold > m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold)
Match an integer or vector with every element comparing 'pred' (eg/ne/...) to Threshold.
Definition: PatternMatch.h:598
DiagnosticInfoOptimizationBase::Argument NV
@ FalseVal
Definition: TGLexer.h:62
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1303
CmpInst::Predicate getMinMaxPred(SelectPatternFlavor SPF, bool Ordered=false)
Return the canonical comparison predicate for the specified minimum/maximum flavor.
constexpr int UndefMaskElem
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...
SelectPatternFlavor
Specific patterns of select instructions we can match.
@ SPF_ABS
Floating point maxnum.
@ SPF_NABS
Absolute value.
@ SPF_UMIN
Signed minimum.
@ SPF_UMAX
Signed maximum.
@ SPF_SMIN
@ SPF_SMAX
Unsigned minimum.
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:288
bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1749
Value * simplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an And, fold the result or return null.
@ Or
Bitwise or logical OR of integers.
@ Mul
Product of integers.
@ And
Bitwise or logical AND of integers.
@ Add
Sum of integers.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1869
bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred, Value *&X, APInt &Mask, bool LookThroughTrunc=true)
Decompose an icmp into the form ((X & Mask) pred 0) if possible.
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI, unsigned Depth=0)
Return true if we can prove that the specified FP value is never equal to -0.0.
bool isCheckForZeroAndMulWithOverflow(Value *Op0, Value *Op1, bool IsAnd, Use *&Y)
Match one of the patterns up to the select/logic op: Op0 = icmp ne i4 X, 0 Agg = call { i4,...
Value * simplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp, const SimplifyQuery &Q, bool AllowRefinement)
See if V simplifies when its operand Op is replaced with RepOp.
Value * simplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, const SimplifyQuery &Q)
Given operands for a SelectInst, fold the result or return null.
std::optional< bool > isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, bool LHSIsTrue=true, unsigned Depth=0)
Return true if RHS is known to be implied true by LHS.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
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?
AssumptionCache * AC
SimplifyQuery getWithInstruction(Instruction *I) const