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 are sinking div/rem after a select, we may need to freeze the
433 // condition because div/rem may induce immediate UB with a poison operand.
434 // For example, the following transform is not safe if Cond can ever be poison
435 // because we can replace poison with zero and then we have div-by-zero that
436 // didn't exist in the original code:
437 // Cond ? x/y : x/z --> x / (Cond ? y : z)
438 auto *BO = dyn_cast<BinaryOperator>(TI);
439 if (BO && BO->isIntDivRem() && !isGuaranteedNotToBePoison(Cond)) {
440 // A udiv/urem with a common divisor is safe because UB can only occur with
441 // div-by-zero, and that would be present in the original code.
442 if (BO->getOpcode() == Instruction::SDiv ||
443 BO->getOpcode() == Instruction::SRem || MatchIsOpZero)
445 }
446
447 // If we reach here, they do have operations in common.
448 Value *NewSI = Builder.CreateSelect(Cond, OtherOpT, OtherOpF,
449 SI.getName() + ".v", &SI);
450 Value *Op0 = MatchIsOpZero ? MatchOp : NewSI;
451 Value *Op1 = MatchIsOpZero ? NewSI : MatchOp;
452 if (auto *BO = dyn_cast<BinaryOperator>(TI)) {
453 BinaryOperator *NewBO = BinaryOperator::Create(BO->getOpcode(), Op0, Op1);
454 NewBO->copyIRFlags(TI);
455 NewBO->andIRFlags(FI);
456 return NewBO;
457 }
458 if (auto *TGEP = dyn_cast<GetElementPtrInst>(TI)) {
459 auto *FGEP = cast<GetElementPtrInst>(FI);
460 Type *ElementType = TGEP->getResultElementType();
461 return TGEP->isInBounds() && FGEP->isInBounds()
462 ? GetElementPtrInst::CreateInBounds(ElementType, Op0, {Op1})
463 : GetElementPtrInst::Create(ElementType, Op0, {Op1});
464 }
465 llvm_unreachable("Expected BinaryOperator or GEP");
466 return nullptr;
467}
468
469static bool isSelect01(const APInt &C1I, const APInt &C2I) {
470 if (!C1I.isZero() && !C2I.isZero()) // One side must be zero.
471 return false;
472 return C1I.isOne() || C1I.isAllOnes() || C2I.isOne() || C2I.isAllOnes();
473}
474
475/// Try to fold the select into one of the operands to allow further
476/// optimization.
478 Value *FalseVal) {
479 // See the comment above GetSelectFoldableOperands for a description of the
480 // transformation we are doing here.
481 auto TryFoldSelectIntoOp = [&](SelectInst &SI, Value *TrueVal,
482 Value *FalseVal,
483 bool Swapped) -> Instruction * {
484 auto *TVI = dyn_cast<BinaryOperator>(TrueVal);
485 if (!TVI || !TVI->hasOneUse() || isa<Constant>(FalseVal))
486 return nullptr;
487
488 unsigned SFO = getSelectFoldableOperands(TVI);
489 unsigned OpToFold = 0;
490 if ((SFO & 1) && FalseVal == TVI->getOperand(0))
491 OpToFold = 1;
492 else if ((SFO & 2) && FalseVal == TVI->getOperand(1))
493 OpToFold = 2;
494
495 if (!OpToFold)
496 return nullptr;
497
498 // TODO: We probably ought to revisit cases where the select and FP
499 // instructions have different flags and add tests to ensure the
500 // behaviour is correct.
501 FastMathFlags FMF;
502 if (isa<FPMathOperator>(&SI))
503 FMF = SI.getFastMathFlags();
505 TVI->getOpcode(), TVI->getType(), true, FMF.noSignedZeros());
506 Value *OOp = TVI->getOperand(2 - OpToFold);
507 // Avoid creating select between 2 constants unless it's selecting
508 // between 0, 1 and -1.
509 const APInt *OOpC;
510 bool OOpIsAPInt = match(OOp, m_APInt(OOpC));
511 if (!isa<Constant>(OOp) ||
512 (OOpIsAPInt && isSelect01(C->getUniqueInteger(), *OOpC))) {
513 Value *NewSel = Builder.CreateSelect(SI.getCondition(), Swapped ? C : OOp,
514 Swapped ? OOp : C);
515 if (isa<FPMathOperator>(&SI))
516 cast<Instruction>(NewSel)->setFastMathFlags(FMF);
517 NewSel->takeName(TVI);
518 BinaryOperator *BO =
519 BinaryOperator::Create(TVI->getOpcode(), FalseVal, NewSel);
520 BO->copyIRFlags(TVI);
521 return BO;
522 }
523 return nullptr;
524 };
525
526 if (Instruction *R = TryFoldSelectIntoOp(SI, TrueVal, FalseVal, false))
527 return R;
528
529 if (Instruction *R = TryFoldSelectIntoOp(SI, FalseVal, TrueVal, true))
530 return R;
531
532 return nullptr;
533}
534
535/// We want to turn:
536/// (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1)
537/// into:
538/// zext (icmp ne i32 (and X, (or Y, (shl 1, Z))), 0)
539/// Note:
540/// Z may be 0 if lshr is missing.
541/// Worst-case scenario is that we will replace 5 instructions with 5 different
542/// instructions, but we got rid of select.
543static Instruction *foldSelectICmpAndAnd(Type *SelType, const ICmpInst *Cmp,
544 Value *TVal, Value *FVal,
545 InstCombiner::BuilderTy &Builder) {
546 if (!(Cmp->hasOneUse() && Cmp->getOperand(0)->hasOneUse() &&
547 Cmp->getPredicate() == ICmpInst::ICMP_EQ &&
548 match(Cmp->getOperand(1), m_Zero()) && match(FVal, m_One())))
549 return nullptr;
550
551 // The TrueVal has general form of: and %B, 1
552 Value *B;
553 if (!match(TVal, m_OneUse(m_And(m_Value(B), m_One()))))
554 return nullptr;
555
556 // Where %B may be optionally shifted: lshr %X, %Z.
557 Value *X, *Z;
558 const bool HasShift = match(B, m_OneUse(m_LShr(m_Value(X), m_Value(Z))));
559
560 // The shift must be valid.
561 // TODO: This restricts the fold to constant shift amounts. Is there a way to
562 // handle variable shifts safely? PR47012
563 if (HasShift &&
565 APInt(SelType->getScalarSizeInBits(),
566 SelType->getScalarSizeInBits()))))
567 return nullptr;
568
569 if (!HasShift)
570 X = B;
571
572 Value *Y;
573 if (!match(Cmp->getOperand(0), m_c_And(m_Specific(X), m_Value(Y))))
574 return nullptr;
575
576 // ((X & Y) == 0) ? ((X >> Z) & 1) : 1 --> (X & (Y | (1 << Z))) != 0
577 // ((X & Y) == 0) ? (X & 1) : 1 --> (X & (Y | 1)) != 0
578 Constant *One = ConstantInt::get(SelType, 1);
579 Value *MaskB = HasShift ? Builder.CreateShl(One, Z) : One;
580 Value *FullMask = Builder.CreateOr(Y, MaskB);
581 Value *MaskedX = Builder.CreateAnd(X, FullMask);
582 Value *ICmpNeZero = Builder.CreateIsNotNull(MaskedX);
583 return new ZExtInst(ICmpNeZero, SelType);
584}
585
586/// We want to turn:
587/// (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1
588/// (select (icmp slt x, C), ashr (X, Y), lshr (X, Y)); iff C s>= 0
589/// into:
590/// ashr (X, Y)
591static Value *foldSelectICmpLshrAshr(const ICmpInst *IC, Value *TrueVal,
592 Value *FalseVal,
593 InstCombiner::BuilderTy &Builder) {
595 Value *CmpLHS = IC->getOperand(0);
596 Value *CmpRHS = IC->getOperand(1);
597 if (!CmpRHS->getType()->isIntOrIntVectorTy())
598 return nullptr;
599
600 Value *X, *Y;
601 unsigned Bitwidth = CmpRHS->getType()->getScalarSizeInBits();
602 if ((Pred != ICmpInst::ICMP_SGT ||
603 !match(CmpRHS,
604 m_SpecificInt_ICMP(ICmpInst::ICMP_SGE, APInt(Bitwidth, -1)))) &&
605 (Pred != ICmpInst::ICMP_SLT ||
606 !match(CmpRHS,
608 return nullptr;
609
610 // Canonicalize so that ashr is in FalseVal.
611 if (Pred == ICmpInst::ICMP_SLT)
612 std::swap(TrueVal, FalseVal);
613
614 if (match(TrueVal, m_LShr(m_Value(X), m_Value(Y))) &&
615 match(FalseVal, m_AShr(m_Specific(X), m_Specific(Y))) &&
616 match(CmpLHS, m_Specific(X))) {
617 const auto *Ashr = cast<Instruction>(FalseVal);
618 // if lshr is not exact and ashr is, this new ashr must not be exact.
619 bool IsExact = Ashr->isExact() && cast<Instruction>(TrueVal)->isExact();
620 return Builder.CreateAShr(X, Y, IC->getName(), IsExact);
621 }
622
623 return nullptr;
624}
625
626/// We want to turn:
627/// (select (icmp eq (and X, C1), 0), Y, (or Y, C2))
628/// into:
629/// (or (shl (and X, C1), C3), Y)
630/// iff:
631/// C1 and C2 are both powers of 2
632/// where:
633/// C3 = Log(C2) - Log(C1)
634///
635/// This transform handles cases where:
636/// 1. The icmp predicate is inverted
637/// 2. The select operands are reversed
638/// 3. The magnitude of C2 and C1 are flipped
639static Value *foldSelectICmpAndOr(const ICmpInst *IC, Value *TrueVal,
640 Value *FalseVal,
641 InstCombiner::BuilderTy &Builder) {
642 // Only handle integer compares. Also, if this is a vector select, we need a
643 // vector compare.
644 if (!TrueVal->getType()->isIntOrIntVectorTy() ||
645 TrueVal->getType()->isVectorTy() != IC->getType()->isVectorTy())
646 return nullptr;
647
648 Value *CmpLHS = IC->getOperand(0);
649 Value *CmpRHS = IC->getOperand(1);
650
651 Value *V;
652 unsigned C1Log;
653 bool IsEqualZero;
654 bool NeedAnd = false;
655 if (IC->isEquality()) {
656 if (!match(CmpRHS, m_Zero()))
657 return nullptr;
658
659 const APInt *C1;
660 if (!match(CmpLHS, m_And(m_Value(), m_Power2(C1))))
661 return nullptr;
662
663 V = CmpLHS;
664 C1Log = C1->logBase2();
665 IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_EQ;
666 } else if (IC->getPredicate() == ICmpInst::ICMP_SLT ||
668 // We also need to recognize (icmp slt (trunc (X)), 0) and
669 // (icmp sgt (trunc (X)), -1).
670 IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_SGT;
671 if ((IsEqualZero && !match(CmpRHS, m_AllOnes())) ||
672 (!IsEqualZero && !match(CmpRHS, m_Zero())))
673 return nullptr;
674
675 if (!match(CmpLHS, m_OneUse(m_Trunc(m_Value(V)))))
676 return nullptr;
677
678 C1Log = CmpLHS->getType()->getScalarSizeInBits() - 1;
679 NeedAnd = true;
680 } else {
681 return nullptr;
682 }
683
684 const APInt *C2;
685 bool OrOnTrueVal = false;
686 bool OrOnFalseVal = match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2)));
687 if (!OrOnFalseVal)
688 OrOnTrueVal = match(TrueVal, m_Or(m_Specific(FalseVal), m_Power2(C2)));
689
690 if (!OrOnFalseVal && !OrOnTrueVal)
691 return nullptr;
692
693 Value *Y = OrOnFalseVal ? TrueVal : FalseVal;
694
695 unsigned C2Log = C2->logBase2();
696
697 bool NeedXor = (!IsEqualZero && OrOnFalseVal) || (IsEqualZero && OrOnTrueVal);
698 bool NeedShift = C1Log != C2Log;
699 bool NeedZExtTrunc = Y->getType()->getScalarSizeInBits() !=
700 V->getType()->getScalarSizeInBits();
701
702 // Make sure we don't create more instructions than we save.
703 Value *Or = OrOnFalseVal ? FalseVal : TrueVal;
704 if ((NeedShift + NeedXor + NeedZExtTrunc) >
705 (IC->hasOneUse() + Or->hasOneUse()))
706 return nullptr;
707
708 if (NeedAnd) {
709 // Insert the AND instruction on the input to the truncate.
710 APInt C1 = APInt::getOneBitSet(V->getType()->getScalarSizeInBits(), C1Log);
711 V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), C1));
712 }
713
714 if (C2Log > C1Log) {
715 V = Builder.CreateZExtOrTrunc(V, Y->getType());
716 V = Builder.CreateShl(V, C2Log - C1Log);
717 } else if (C1Log > C2Log) {
718 V = Builder.CreateLShr(V, C1Log - C2Log);
719 V = Builder.CreateZExtOrTrunc(V, Y->getType());
720 } else
721 V = Builder.CreateZExtOrTrunc(V, Y->getType());
722
723 if (NeedXor)
724 V = Builder.CreateXor(V, *C2);
725
726 return Builder.CreateOr(V, Y);
727}
728
729/// Canonicalize a set or clear of a masked set of constant bits to
730/// select-of-constants form.
732 InstCombiner::BuilderTy &Builder) {
733 Value *Cond = Sel.getCondition();
734 Value *T = Sel.getTrueValue();
735 Value *F = Sel.getFalseValue();
736 Type *Ty = Sel.getType();
737 Value *X;
738 const APInt *NotC, *C;
739
740 // Cond ? (X & ~C) : (X | C) --> (X & ~C) | (Cond ? 0 : C)
741 if (match(T, m_And(m_Value(X), m_APInt(NotC))) &&
742 match(F, m_OneUse(m_Or(m_Specific(X), m_APInt(C)))) && *NotC == ~(*C)) {
744 Constant *OrC = ConstantInt::get(Ty, *C);
745 Value *NewSel = Builder.CreateSelect(Cond, Zero, OrC, "masksel", &Sel);
746 return BinaryOperator::CreateOr(T, NewSel);
747 }
748
749 // Cond ? (X | C) : (X & ~C) --> (X & ~C) | (Cond ? C : 0)
750 if (match(F, m_And(m_Value(X), m_APInt(NotC))) &&
751 match(T, m_OneUse(m_Or(m_Specific(X), m_APInt(C)))) && *NotC == ~(*C)) {
753 Constant *OrC = ConstantInt::get(Ty, *C);
754 Value *NewSel = Builder.CreateSelect(Cond, OrC, Zero, "masksel", &Sel);
755 return BinaryOperator::CreateOr(F, NewSel);
756 }
757
758 return nullptr;
759}
760
761// select (x == 0), 0, x * y --> freeze(y) * x
762// select (y == 0), 0, x * y --> freeze(x) * y
763// select (x == 0), undef, x * y --> freeze(y) * x
764// select (x == undef), 0, x * y --> freeze(y) * x
765// Usage of mul instead of 0 will make the result more poisonous,
766// so the operand that was not checked in the condition should be frozen.
767// The latter folding is applied only when a constant compared with x is
768// is a vector consisting of 0 and undefs. If a constant compared with x
769// is a scalar undefined value or undefined vector then an expression
770// should be already folded into a constant.
772 auto *CondVal = SI.getCondition();
773 auto *TrueVal = SI.getTrueValue();
774 auto *FalseVal = SI.getFalseValue();
775 Value *X, *Y;
776 ICmpInst::Predicate Predicate;
777
778 // Assuming that constant compared with zero is not undef (but it may be
779 // a vector with some undef elements). Otherwise (when a constant is undef)
780 // the select expression should be already simplified.
781 if (!match(CondVal, m_ICmp(Predicate, m_Value(X), m_Zero())) ||
782 !ICmpInst::isEquality(Predicate))
783 return nullptr;
784
785 if (Predicate == ICmpInst::ICMP_NE)
786 std::swap(TrueVal, FalseVal);
787
788 // Check that TrueVal is a constant instead of matching it with m_Zero()
789 // to handle the case when it is a scalar undef value or a vector containing
790 // non-zero elements that are masked by undef elements in the compare
791 // constant.
792 auto *TrueValC = dyn_cast<Constant>(TrueVal);
793 if (TrueValC == nullptr ||
794 !match(FalseVal, m_c_Mul(m_Specific(X), m_Value(Y))) ||
795 !isa<Instruction>(FalseVal))
796 return nullptr;
797
798 auto *ZeroC = cast<Constant>(cast<Instruction>(CondVal)->getOperand(1));
799 auto *MergedC = Constant::mergeUndefsWith(TrueValC, ZeroC);
800 // If X is compared with 0 then TrueVal could be either zero or undef.
801 // m_Zero match vectors containing some undef elements, but for scalars
802 // m_Undef should be used explicitly.
803 if (!match(MergedC, m_Zero()) && !match(MergedC, m_Undef()))
804 return nullptr;
805
806 auto *FalseValI = cast<Instruction>(FalseVal);
807 auto *FrY = IC.InsertNewInstBefore(new FreezeInst(Y, Y->getName() + ".fr"),
808 *FalseValI);
809 IC.replaceOperand(*FalseValI, FalseValI->getOperand(0) == Y ? 0 : 1, FrY);
810 return IC.replaceInstUsesWith(SI, FalseValI);
811}
812
813/// Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b).
814/// There are 8 commuted/swapped variants of this pattern.
815/// TODO: Also support a - UMIN(a,b) patterns.
817 const Value *TrueVal,
818 const Value *FalseVal,
819 InstCombiner::BuilderTy &Builder) {
820 ICmpInst::Predicate Pred = ICI->getPredicate();
821 Value *A = ICI->getOperand(0);
822 Value *B = ICI->getOperand(1);
823
824 // (b > a) ? 0 : a - b -> (b <= a) ? a - b : 0
825 // (a == 0) ? 0 : a - 1 -> (a != 0) ? a - 1 : 0
826 if (match(TrueVal, m_Zero())) {
828 std::swap(TrueVal, FalseVal);
829 }
830
831 if (!match(FalseVal, m_Zero()))
832 return nullptr;
833
834 // ugt 0 is canonicalized to ne 0 and requires special handling
835 // (a != 0) ? a + -1 : 0 -> usub.sat(a, 1)
836 if (Pred == ICmpInst::ICMP_NE) {
837 if (match(B, m_Zero()) && match(TrueVal, m_Add(m_Specific(A), m_AllOnes())))
838 return Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, A,
839 ConstantInt::get(A->getType(), 1));
840 return nullptr;
841 }
842
843 if (!ICmpInst::isUnsigned(Pred))
844 return nullptr;
845
846 if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_ULT) {
847 // (b < a) ? a - b : 0 -> (a > b) ? a - b : 0
848 std::swap(A, B);
850 }
851
852 assert((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_UGT) &&
853 "Unexpected isUnsigned predicate!");
854
855 // Ensure the sub is of the form:
856 // (a > b) ? a - b : 0 -> usub.sat(a, b)
857 // (a > b) ? b - a : 0 -> -usub.sat(a, b)
858 // Checking for both a-b and a+(-b) as a constant.
859 bool IsNegative = false;
860 const APInt *C;
861 if (match(TrueVal, m_Sub(m_Specific(B), m_Specific(A))) ||
862 (match(A, m_APInt(C)) &&
863 match(TrueVal, m_Add(m_Specific(B), m_SpecificInt(-*C)))))
864 IsNegative = true;
865 else if (!match(TrueVal, m_Sub(m_Specific(A), m_Specific(B))) &&
866 !(match(B, m_APInt(C)) &&
867 match(TrueVal, m_Add(m_Specific(A), m_SpecificInt(-*C)))))
868 return nullptr;
869
870 // If we are adding a negate and the sub and icmp are used anywhere else, we
871 // would end up with more instructions.
872 if (IsNegative && !TrueVal->hasOneUse() && !ICI->hasOneUse())
873 return nullptr;
874
875 // (a > b) ? a - b : 0 -> usub.sat(a, b)
876 // (a > b) ? b - a : 0 -> -usub.sat(a, b)
877 Value *Result = Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, A, B);
878 if (IsNegative)
879 Result = Builder.CreateNeg(Result);
880 return Result;
881}
882
884 InstCombiner::BuilderTy &Builder) {
885 if (!Cmp->hasOneUse())
886 return nullptr;
887
888 // Match unsigned saturated add with constant.
889 Value *Cmp0 = Cmp->getOperand(0);
890 Value *Cmp1 = Cmp->getOperand(1);
891 ICmpInst::Predicate Pred = Cmp->getPredicate();
892 Value *X;
893 const APInt *C, *CmpC;
894 if (Pred == ICmpInst::ICMP_ULT &&
895 match(TVal, m_Add(m_Value(X), m_APInt(C))) && X == Cmp0 &&
896 match(FVal, m_AllOnes()) && match(Cmp1, m_APInt(CmpC)) && *CmpC == ~*C) {
897 // (X u< ~C) ? (X + C) : -1 --> uadd.sat(X, C)
898 return Builder.CreateBinaryIntrinsic(
899 Intrinsic::uadd_sat, X, ConstantInt::get(X->getType(), *C));
900 }
901
902 // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
903 // There are 8 commuted variants.
904 // Canonicalize -1 (saturated result) to true value of the select.
905 if (match(FVal, m_AllOnes())) {
906 std::swap(TVal, FVal);
907 Pred = CmpInst::getInversePredicate(Pred);
908 }
909 if (!match(TVal, m_AllOnes()))
910 return nullptr;
911
912 // Canonicalize predicate to less-than or less-or-equal-than.
913 if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) {
914 std::swap(Cmp0, Cmp1);
915 Pred = CmpInst::getSwappedPredicate(Pred);
916 }
917 if (Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_ULE)
918 return nullptr;
919
920 // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
921 // Strictness of the comparison is irrelevant.
922 Value *Y;
923 if (match(Cmp0, m_Not(m_Value(X))) &&
924 match(FVal, m_c_Add(m_Specific(X), m_Value(Y))) && Y == Cmp1) {
925 // (~X u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
926 // (~X u< Y) ? -1 : (Y + X) --> uadd.sat(X, Y)
927 return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, X, Y);
928 }
929 // The 'not' op may be included in the sum but not the compare.
930 // Strictness of the comparison is irrelevant.
931 X = Cmp0;
932 Y = Cmp1;
933 if (match(FVal, m_c_Add(m_Not(m_Specific(X)), m_Specific(Y)))) {
934 // (X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y)
935 // (X u< Y) ? -1 : (Y + ~X) --> uadd.sat(Y, ~X)
936 BinaryOperator *BO = cast<BinaryOperator>(FVal);
937 return Builder.CreateBinaryIntrinsic(
938 Intrinsic::uadd_sat, BO->getOperand(0), BO->getOperand(1));
939 }
940 // The overflow may be detected via the add wrapping round.
941 // This is only valid for strict comparison!
942 if (Pred == ICmpInst::ICMP_ULT &&
943 match(Cmp0, m_c_Add(m_Specific(Cmp1), m_Value(Y))) &&
944 match(FVal, m_c_Add(m_Specific(Cmp1), m_Specific(Y)))) {
945 // ((X + Y) u< X) ? -1 : (X + Y) --> uadd.sat(X, Y)
946 // ((X + Y) u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
947 return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, Cmp1, Y);
948 }
949
950 return nullptr;
951}
952
953/// Try to match patterns with select and subtract as absolute difference.
954static Value *foldAbsDiff(ICmpInst *Cmp, Value *TVal, Value *FVal,
955 InstCombiner::BuilderTy &Builder) {
956 auto *TI = dyn_cast<Instruction>(TVal);
957 auto *FI = dyn_cast<Instruction>(FVal);
958 if (!TI || !FI)
959 return nullptr;
960
961 // Normalize predicate to gt/lt rather than ge/le.
962 ICmpInst::Predicate Pred = Cmp->getStrictPredicate();
963 Value *A = Cmp->getOperand(0);
964 Value *B = Cmp->getOperand(1);
965
966 // Normalize "A - B" as the true value of the select.
967 if (match(FI, m_Sub(m_Specific(A), m_Specific(B)))) {
968 std::swap(FI, TI);
970 }
971
972 // With any pair of no-wrap subtracts:
973 // (A > B) ? (A - B) : (B - A) --> abs(A - B)
974 if (Pred == CmpInst::ICMP_SGT &&
975 match(TI, m_Sub(m_Specific(A), m_Specific(B))) &&
976 match(FI, m_Sub(m_Specific(B), m_Specific(A))) &&
977 (TI->hasNoSignedWrap() || TI->hasNoUnsignedWrap()) &&
978 (FI->hasNoSignedWrap() || FI->hasNoUnsignedWrap())) {
979 // The remaining subtract is not "nuw" any more.
980 // If there's one use of the subtract (no other use than the use we are
981 // about to replace), then we know that the sub is "nsw" in this context
982 // even if it was only "nuw" before. If there's another use, then we can't
983 // add "nsw" to the existing instruction because it may not be safe in the
984 // other user's context.
985 TI->setHasNoUnsignedWrap(false);
986 if (!TI->hasNoSignedWrap())
987 TI->setHasNoSignedWrap(TI->hasOneUse());
988 return Builder.CreateBinaryIntrinsic(Intrinsic::abs, TI, Builder.getTrue());
989 }
990
991 return nullptr;
992}
993
994/// Fold the following code sequence:
995/// \code
996/// int a = ctlz(x & -x);
997// x ? 31 - a : a;
998/// \code
999///
1000/// into:
1001/// cttz(x)
1002static Instruction *foldSelectCtlzToCttz(ICmpInst *ICI, Value *TrueVal,
1003 Value *FalseVal,
1004 InstCombiner::BuilderTy &Builder) {
1005 unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits();
1006 if (!ICI->isEquality() || !match(ICI->getOperand(1), m_Zero()))
1007 return nullptr;
1008
1009 if (ICI->getPredicate() == ICmpInst::ICMP_NE)
1010 std::swap(TrueVal, FalseVal);
1011
1012 if (!match(FalseVal,
1013 m_Xor(m_Deferred(TrueVal), m_SpecificInt(BitWidth - 1))))
1014 return nullptr;
1015
1016 if (!match(TrueVal, m_Intrinsic<Intrinsic::ctlz>()))
1017 return nullptr;
1018
1019 Value *X = ICI->getOperand(0);
1020 auto *II = cast<IntrinsicInst>(TrueVal);
1021 if (!match(II->getOperand(0), m_c_And(m_Specific(X), m_Neg(m_Specific(X)))))
1022 return nullptr;
1023
1024 Function *F = Intrinsic::getDeclaration(II->getModule(), Intrinsic::cttz,
1025 II->getType());
1026 return CallInst::Create(F, {X, II->getArgOperand(1)});
1027}
1028
1029/// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single
1030/// call to cttz/ctlz with flag 'is_zero_poison' cleared.
1031///
1032/// For example, we can fold the following code sequence:
1033/// \code
1034/// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
1035/// %1 = icmp ne i32 %x, 0
1036/// %2 = select i1 %1, i32 %0, i32 32
1037/// \code
1038///
1039/// into:
1040/// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
1041static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal,
1042 InstCombiner::BuilderTy &Builder) {
1043 ICmpInst::Predicate Pred = ICI->getPredicate();
1044 Value *CmpLHS = ICI->getOperand(0);
1045 Value *CmpRHS = ICI->getOperand(1);
1046
1047 // Check if the select condition compares a value for equality.
1048 if (!ICI->isEquality())
1049 return nullptr;
1050
1051 Value *SelectArg = FalseVal;
1052 Value *ValueOnZero = TrueVal;
1053 if (Pred == ICmpInst::ICMP_NE)
1054 std::swap(SelectArg, ValueOnZero);
1055
1056 // Skip zero extend/truncate.
1057 Value *Count = nullptr;
1058 if (!match(SelectArg, m_ZExt(m_Value(Count))) &&
1059 !match(SelectArg, m_Trunc(m_Value(Count))))
1060 Count = SelectArg;
1061
1062 // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the
1063 // input to the cttz/ctlz is used as LHS for the compare instruction.
1064 Value *X;
1065 if (!match(Count, m_Intrinsic<Intrinsic::cttz>(m_Value(X))) &&
1066 !match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Value(X))))
1067 return nullptr;
1068
1069 // (X == 0) ? BitWidth : ctz(X)
1070 // (X == -1) ? BitWidth : ctz(~X)
1071 if ((X != CmpLHS || !match(CmpRHS, m_Zero())) &&
1072 (!match(X, m_Not(m_Specific(CmpLHS))) || !match(CmpRHS, m_AllOnes())))
1073 return nullptr;
1074
1075 IntrinsicInst *II = cast<IntrinsicInst>(Count);
1076
1077 // Check if the value propagated on zero is a constant number equal to the
1078 // sizeof in bits of 'Count'.
1079 unsigned SizeOfInBits = Count->getType()->getScalarSizeInBits();
1080 if (match(ValueOnZero, m_SpecificInt(SizeOfInBits))) {
1081 // Explicitly clear the 'is_zero_poison' flag. It's always valid to go from
1082 // true to false on this flag, so we can replace it for all users.
1084 return SelectArg;
1085 }
1086
1087 // The ValueOnZero is not the bitwidth. But if the cttz/ctlz (and optional
1088 // zext/trunc) have one use (ending at the select), the cttz/ctlz result will
1089 // not be used if the input is zero. Relax to 'zero is poison' for that case.
1090 if (II->hasOneUse() && SelectArg->hasOneUse() &&
1091 !match(II->getArgOperand(1), m_One()))
1093
1094 return nullptr;
1095}
1096
1097static Instruction *canonicalizeSPF(SelectInst &Sel, ICmpInst &Cmp,
1098 InstCombinerImpl &IC) {
1099 Value *LHS, *RHS;
1100 // TODO: What to do with pointer min/max patterns?
1101 if (!Sel.getType()->isIntOrIntVectorTy())
1102 return nullptr;
1103
1104 SelectPatternFlavor SPF = matchSelectPattern(&Sel, LHS, RHS).Flavor;
1105 if (SPF == SelectPatternFlavor::SPF_ABS ||
1107 if (!Cmp.hasOneUse() && !RHS->hasOneUse())
1108 return nullptr; // TODO: Relax this restriction.
1109
1110 // Note that NSW flag can only be propagated for normal, non-negated abs!
1111 bool IntMinIsPoison = SPF == SelectPatternFlavor::SPF_ABS &&
1112 match(RHS, m_NSWNeg(m_Specific(LHS)));
1113 Constant *IntMinIsPoisonC =
1114 ConstantInt::get(Type::getInt1Ty(Sel.getContext()), IntMinIsPoison);
1115 Instruction *Abs =
1116 IC.Builder.CreateBinaryIntrinsic(Intrinsic::abs, LHS, IntMinIsPoisonC);
1117
1119 return BinaryOperator::CreateNeg(Abs); // Always without NSW flag!
1120 return IC.replaceInstUsesWith(Sel, Abs);
1121 }
1122
1124 Intrinsic::ID IntrinsicID;
1125 switch (SPF) {
1127 IntrinsicID = Intrinsic::umin;
1128 break;
1130 IntrinsicID = Intrinsic::umax;
1131 break;
1133 IntrinsicID = Intrinsic::smin;
1134 break;
1136 IntrinsicID = Intrinsic::smax;
1137 break;
1138 default:
1139 llvm_unreachable("Unexpected SPF");
1140 }
1141 return IC.replaceInstUsesWith(
1142 Sel, IC.Builder.CreateBinaryIntrinsic(IntrinsicID, LHS, RHS));
1143 }
1144
1145 return nullptr;
1146}
1147
1149 unsigned Depth) {
1150 // Conservatively limit replacement to two instructions upwards.
1151 if (Depth == 2)
1152 return false;
1153
1154 auto *I = dyn_cast<Instruction>(V);
1155 if (!I || !I->hasOneUse() || !isSafeToSpeculativelyExecute(I))
1156 return false;
1157
1158 bool Changed = false;
1159 for (Use &U : I->operands()) {
1160 if (U == Old) {
1161 replaceUse(U, New);
1162 Worklist.add(I);
1163 Changed = true;
1164 } else {
1165 Changed |= replaceInInstruction(U, Old, New, Depth + 1);
1166 }
1167 }
1168 return Changed;
1169}
1170
1171/// If we have a select with an equality comparison, then we know the value in
1172/// one of the arms of the select. See if substituting this value into an arm
1173/// and simplifying the result yields the same value as the other arm.
1174///
1175/// To make this transform safe, we must drop poison-generating flags
1176/// (nsw, etc) if we simplified to a binop because the select may be guarding
1177/// that poison from propagating. If the existing binop already had no
1178/// poison-generating flags, then this transform can be done by instsimplify.
1179///
1180/// Consider:
1181/// %cmp = icmp eq i32 %x, 2147483647
1182/// %add = add nsw i32 %x, 1
1183/// %sel = select i1 %cmp, i32 -2147483648, i32 %add
1184///
1185/// We can't replace %sel with %add unless we strip away the flags.
1186/// TODO: Wrapping flags could be preserved in some cases with better analysis.
1188 ICmpInst &Cmp) {
1189 if (!Cmp.isEquality())
1190 return nullptr;
1191
1192 // Canonicalize the pattern to ICMP_EQ by swapping the select operands.
1193 Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
1194 bool Swapped = false;
1195 if (Cmp.getPredicate() == ICmpInst::ICMP_NE) {
1196 std::swap(TrueVal, FalseVal);
1197 Swapped = true;
1198 }
1199
1200 // In X == Y ? f(X) : Z, try to evaluate f(Y) and replace the operand.
1201 // Make sure Y cannot be undef though, as we might pick different values for
1202 // undef in the icmp and in f(Y). Additionally, take care to avoid replacing
1203 // X == Y ? X : Z with X == Y ? Y : Z, as that would lead to an infinite
1204 // replacement cycle.
1205 Value *CmpLHS = Cmp.getOperand(0), *CmpRHS = Cmp.getOperand(1);
1206 if (TrueVal != CmpLHS &&
1207 isGuaranteedNotToBeUndefOrPoison(CmpRHS, SQ.AC, &Sel, &DT)) {
1208 if (Value *V = simplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, SQ,
1209 /* AllowRefinement */ true))
1210 return replaceOperand(Sel, Swapped ? 2 : 1, V);
1211
1212 // Even if TrueVal does not simplify, we can directly replace a use of
1213 // CmpLHS with CmpRHS, as long as the instruction is not used anywhere
1214 // else and is safe to speculatively execute (we may end up executing it
1215 // with different operands, which should not cause side-effects or trigger
1216 // undefined behavior). Only do this if CmpRHS is a constant, as
1217 // profitability is not clear for other cases.
1218 // FIXME: Support vectors.
1219 if (match(CmpRHS, m_ImmConstant()) && !match(CmpLHS, m_ImmConstant()) &&
1220 !Cmp.getType()->isVectorTy())
1221 if (replaceInInstruction(TrueVal, CmpLHS, CmpRHS))
1222 return &Sel;
1223 }
1224 if (TrueVal != CmpRHS &&
1225 isGuaranteedNotToBeUndefOrPoison(CmpLHS, SQ.AC, &Sel, &DT))
1226 if (Value *V = simplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, SQ,
1227 /* AllowRefinement */ true))
1228 return replaceOperand(Sel, Swapped ? 2 : 1, V);
1229
1230 auto *FalseInst = dyn_cast<Instruction>(FalseVal);
1231 if (!FalseInst)
1232 return nullptr;
1233
1234 // InstSimplify already performed this fold if it was possible subject to
1235 // current poison-generating flags. Try the transform again with
1236 // poison-generating flags temporarily dropped.
1237 bool WasNUW = false, WasNSW = false, WasExact = false, WasInBounds = false;
1238 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(FalseVal)) {
1239 WasNUW = OBO->hasNoUnsignedWrap();
1240 WasNSW = OBO->hasNoSignedWrap();
1241 FalseInst->setHasNoUnsignedWrap(false);
1242 FalseInst->setHasNoSignedWrap(false);
1243 }
1244 if (auto *PEO = dyn_cast<PossiblyExactOperator>(FalseVal)) {
1245 WasExact = PEO->isExact();
1246 FalseInst->setIsExact(false);
1247 }
1248 if (auto *GEP = dyn_cast<GetElementPtrInst>(FalseVal)) {
1249 WasInBounds = GEP->isInBounds();
1250 GEP->setIsInBounds(false);
1251 }
1252
1253 // Try each equivalence substitution possibility.
1254 // We have an 'EQ' comparison, so the select's false value will propagate.
1255 // Example:
1256 // (X == 42) ? 43 : (X + 1) --> (X == 42) ? (X + 1) : (X + 1) --> X + 1
1257 if (simplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, SQ,
1258 /* AllowRefinement */ false) == TrueVal ||
1259 simplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, SQ,
1260 /* AllowRefinement */ false) == TrueVal) {
1261 return replaceInstUsesWith(Sel, FalseVal);
1262 }
1263
1264 // Restore poison-generating flags if the transform did not apply.
1265 if (WasNUW)
1266 FalseInst->setHasNoUnsignedWrap();
1267 if (WasNSW)
1268 FalseInst->setHasNoSignedWrap();
1269 if (WasExact)
1270 FalseInst->setIsExact();
1271 if (WasInBounds)
1272 cast<GetElementPtrInst>(FalseInst)->setIsInBounds();
1273
1274 return nullptr;
1275}
1276
1277// See if this is a pattern like:
1278// %old_cmp1 = icmp slt i32 %x, C2
1279// %old_replacement = select i1 %old_cmp1, i32 %target_low, i32 %target_high
1280// %old_x_offseted = add i32 %x, C1
1281// %old_cmp0 = icmp ult i32 %old_x_offseted, C0
1282// %r = select i1 %old_cmp0, i32 %x, i32 %old_replacement
1283// This can be rewritten as more canonical pattern:
1284// %new_cmp1 = icmp slt i32 %x, -C1
1285// %new_cmp2 = icmp sge i32 %x, C0-C1
1286// %new_clamped_low = select i1 %new_cmp1, i32 %target_low, i32 %x
1287// %r = select i1 %new_cmp2, i32 %target_high, i32 %new_clamped_low
1288// Iff -C1 s<= C2 s<= C0-C1
1289// Also ULT predicate can also be UGT iff C0 != -1 (+invert result)
1290// SLT predicate can also be SGT iff C2 != INT_MAX (+invert res.)
1291static Value *canonicalizeClampLike(SelectInst &Sel0, ICmpInst &Cmp0,
1292 InstCombiner::BuilderTy &Builder) {
1293 Value *X = Sel0.getTrueValue();
1294 Value *Sel1 = Sel0.getFalseValue();
1295
1296 // First match the condition of the outermost select.
1297 // Said condition must be one-use.
1298 if (!Cmp0.hasOneUse())
1299 return nullptr;
1300 ICmpInst::Predicate Pred0 = Cmp0.getPredicate();
1301 Value *Cmp00 = Cmp0.getOperand(0);
1302 Constant *C0;
1303 if (!match(Cmp0.getOperand(1),
1305 return nullptr;
1306
1307 if (!isa<SelectInst>(Sel1)) {
1308 Pred0 = ICmpInst::getInversePredicate(Pred0);
1309 std::swap(X, Sel1);
1310 }
1311
1312 // Canonicalize Cmp0 into ult or uge.
1313 // FIXME: we shouldn't care about lanes that are 'undef' in the end?
1314 switch (Pred0) {
1317 // Although icmp ult %x, 0 is an unusual thing to try and should generally
1318 // have been simplified, it does not verify with undef inputs so ensure we
1319 // are not in a strange state.
1320 if (!match(C0, m_SpecificInt_ICMP(
1323 return nullptr;
1324 break; // Great!
1327 // We want to canonicalize it to 'ult' or 'uge', so we'll need to increment
1328 // C0, which again means it must not have any all-ones elements.
1329 if (!match(C0,
1333 return nullptr; // Can't do, have all-ones element[s].
1335 C0 = InstCombiner::AddOne(C0);
1336 break;
1337 default:
1338 return nullptr; // Unknown predicate.
1339 }
1340
1341 // Now that we've canonicalized the ICmp, we know the X we expect;
1342 // the select in other hand should be one-use.
1343 if (!Sel1->hasOneUse())
1344 return nullptr;
1345
1346 // If the types do not match, look through any truncs to the underlying
1347 // instruction.
1348 if (Cmp00->getType() != X->getType() && X->hasOneUse())
1350
1351 // We now can finish matching the condition of the outermost select:
1352 // it should either be the X itself, or an addition of some constant to X.
1353 Constant *C1;
1354 if (Cmp00 == X)
1355 C1 = ConstantInt::getNullValue(X->getType());
1356 else if (!match(Cmp00,
1359 return nullptr;
1360
1361 Value *Cmp1;
1362 ICmpInst::Predicate Pred1;
1363 Constant *C2;
1364 Value *ReplacementLow, *ReplacementHigh;
1365 if (!match(Sel1, m_Select(m_Value(Cmp1), m_Value(ReplacementLow),
1366 m_Value(ReplacementHigh))) ||
1367 !match(Cmp1,
1368 m_ICmp(Pred1, m_Specific(X),
1370 return nullptr;
1371
1372 if (!Cmp1->hasOneUse() && (Cmp00 == X || !Cmp00->hasOneUse()))
1373 return nullptr; // Not enough one-use instructions for the fold.
1374 // FIXME: this restriction could be relaxed if Cmp1 can be reused as one of
1375 // two comparisons we'll need to build.
1376
1377 // Canonicalize Cmp1 into the form we expect.
1378 // FIXME: we shouldn't care about lanes that are 'undef' in the end?
1379 switch (Pred1) {
1381 break;
1383 // We'd have to increment C2 by one, and for that it must not have signed
1384 // max element, but then it would have been canonicalized to 'slt' before
1385 // we get here. So we can't do anything useful with 'sle'.
1386 return nullptr;
1388 // We want to canonicalize it to 'slt', so we'll need to increment C2,
1389 // which again means it must not have any signed max elements.
1390 if (!match(C2,
1393 C2->getType()->getScalarSizeInBits()))))
1394 return nullptr; // Can't do, have signed max element[s].
1395 C2 = InstCombiner::AddOne(C2);
1396 [[fallthrough]];
1398 // Also non-canonical, but here we don't need to change C2,
1399 // so we don't have any restrictions on C2, so we can just handle it.
1401 std::swap(ReplacementLow, ReplacementHigh);
1402 break;
1403 default:
1404 return nullptr; // Unknown predicate.
1405 }
1407 "Unexpected predicate type.");
1408
1409 // The thresholds of this clamp-like pattern.
1410 auto *ThresholdLowIncl = ConstantExpr::getNeg(C1);
1411 auto *ThresholdHighExcl = ConstantExpr::getSub(C0, C1);
1412
1415 "Unexpected predicate type.");
1416 if (Pred0 == ICmpInst::Predicate::ICMP_UGE)
1417 std::swap(ThresholdLowIncl, ThresholdHighExcl);
1418
1419 // The fold has a precondition 1: C2 s>= ThresholdLow
1421 ThresholdLowIncl);
1422 if (!match(Precond1, m_One()))
1423 return nullptr;
1424 // The fold has a precondition 2: C2 s<= ThresholdHigh
1426 ThresholdHighExcl);
1427 if (!match(Precond2, m_One()))
1428 return nullptr;
1429
1430 // If we are matching from a truncated input, we need to sext the
1431 // ReplacementLow and ReplacementHigh values. Only do the transform if they
1432 // are free to extend due to being constants.
1433 if (X->getType() != Sel0.getType()) {
1434 Constant *LowC, *HighC;
1435 if (!match(ReplacementLow, m_ImmConstant(LowC)) ||
1436 !match(ReplacementHigh, m_ImmConstant(HighC)))
1437 return nullptr;
1438 ReplacementLow = ConstantExpr::getSExt(LowC, X->getType());
1439 ReplacementHigh = ConstantExpr::getSExt(HighC, X->getType());
1440 }
1441
1442 // All good, finally emit the new pattern.
1443 Value *ShouldReplaceLow = Builder.CreateICmpSLT(X, ThresholdLowIncl);
1444 Value *ShouldReplaceHigh = Builder.CreateICmpSGE(X, ThresholdHighExcl);
1445 Value *MaybeReplacedLow =
1446 Builder.CreateSelect(ShouldReplaceLow, ReplacementLow, X);
1447
1448 // Create the final select. If we looked through a truncate above, we will
1449 // need to retruncate the result.
1450 Value *MaybeReplacedHigh = Builder.CreateSelect(
1451 ShouldReplaceHigh, ReplacementHigh, MaybeReplacedLow);
1452 return Builder.CreateTrunc(MaybeReplacedHigh, Sel0.getType());
1453}
1454
1455// If we have
1456// %cmp = icmp [canonical predicate] i32 %x, C0
1457// %r = select i1 %cmp, i32 %y, i32 C1
1458// Where C0 != C1 and %x may be different from %y, see if the constant that we
1459// will have if we flip the strictness of the predicate (i.e. without changing
1460// the result) is identical to the C1 in select. If it matches we can change
1461// original comparison to one with swapped predicate, reuse the constant,
1462// and swap the hands of select.
1463static Instruction *
1464tryToReuseConstantFromSelectInComparison(SelectInst &Sel, ICmpInst &Cmp,
1465 InstCombinerImpl &IC) {
1467 Value *X;
1468 Constant *C0;
1469 if (!match(&Cmp, m_OneUse(m_ICmp(
1470 Pred, m_Value(X),
1472 return nullptr;
1473
1474 // If comparison predicate is non-relational, we won't be able to do anything.
1475 if (ICmpInst::isEquality(Pred))
1476 return nullptr;
1477
1478 // If comparison predicate is non-canonical, then we certainly won't be able
1479 // to make it canonical; canonicalizeCmpWithConstant() already tried.
1481 return nullptr;
1482
1483 // If the [input] type of comparison and select type are different, lets abort
1484 // for now. We could try to compare constants with trunc/[zs]ext though.
1485 if (C0->getType() != Sel.getType())
1486 return nullptr;
1487
1488 // ULT with 'add' of a constant is canonical. See foldICmpAddConstant().
1489 // FIXME: Are there more magic icmp predicate+constant pairs we must avoid?
1490 // Or should we just abandon this transform entirely?
1491 if (Pred == CmpInst::ICMP_ULT && match(X, m_Add(m_Value(), m_Constant())))
1492 return nullptr;
1493
1494
1495 Value *SelVal0, *SelVal1; // We do not care which one is from where.
1496 match(&Sel, m_Select(m_Value(), m_Value(SelVal0), m_Value(SelVal1)));
1497 // At least one of these values we are selecting between must be a constant
1498 // else we'll never succeed.
1499 if (!match(SelVal0, m_AnyIntegralConstant()) &&
1500 !match(SelVal1, m_AnyIntegralConstant()))
1501 return nullptr;
1502
1503 // Does this constant C match any of the `select` values?
1504 auto MatchesSelectValue = [SelVal0, SelVal1](Constant *C) {
1505 return C->isElementWiseEqual(SelVal0) || C->isElementWiseEqual(SelVal1);
1506 };
1507
1508 // If C0 *already* matches true/false value of select, we are done.
1509 if (MatchesSelectValue(C0))
1510 return nullptr;
1511
1512 // Check the constant we'd have with flipped-strictness predicate.
1513 auto FlippedStrictness =
1515 if (!FlippedStrictness)
1516 return nullptr;
1517
1518 // If said constant doesn't match either, then there is no hope,
1519 if (!MatchesSelectValue(FlippedStrictness->second))
1520 return nullptr;
1521
1522 // It matched! Lets insert the new comparison just before select.
1524 IC.Builder.SetInsertPoint(&Sel);
1525
1526 Pred = ICmpInst::getSwappedPredicate(Pred); // Yes, swapped.
1527 Value *NewCmp = IC.Builder.CreateICmp(Pred, X, FlippedStrictness->second,
1528 Cmp.getName() + ".inv");
1529 IC.replaceOperand(Sel, 0, NewCmp);
1530 Sel.swapValues();
1531 Sel.swapProfMetadata();
1532
1533 return &Sel;
1534}
1535
1536static Instruction *foldSelectZeroOrOnes(ICmpInst *Cmp, Value *TVal,
1537 Value *FVal,
1538 InstCombiner::BuilderTy &Builder) {
1539 if (!Cmp->hasOneUse())
1540 return nullptr;
1541
1542 const APInt *CmpC;
1543 if (!match(Cmp->getOperand(1), m_APIntAllowUndef(CmpC)))
1544 return nullptr;
1545
1546 // (X u< 2) ? -X : -1 --> sext (X != 0)
1547 Value *X = Cmp->getOperand(0);
1548 if (Cmp->getPredicate() == ICmpInst::ICMP_ULT && *CmpC == 2 &&
1549 match(TVal, m_Neg(m_Specific(X))) && match(FVal, m_AllOnes()))
1550 return new SExtInst(Builder.CreateIsNotNull(X), TVal->getType());
1551
1552 // (X u> 1) ? -1 : -X --> sext (X != 0)
1553 if (Cmp->getPredicate() == ICmpInst::ICMP_UGT && *CmpC == 1 &&
1554 match(FVal, m_Neg(m_Specific(X))) && match(TVal, m_AllOnes()))
1555 return new SExtInst(Builder.CreateIsNotNull(X), TVal->getType());
1556
1557 return nullptr;
1558}
1559
1560static Value *foldSelectInstWithICmpConst(SelectInst &SI, ICmpInst *ICI,
1561 InstCombiner::BuilderTy &Builder) {
1562 const APInt *CmpC;
1563 Value *V;
1564 CmpInst::Predicate Pred;
1565 if (!match(ICI, m_ICmp(Pred, m_Value(V), m_APInt(CmpC))))
1566 return nullptr;
1567
1568 // Match clamp away from min/max value as a max/min operation.
1569 Value *TVal = SI.getTrueValue();
1570 Value *FVal = SI.getFalseValue();
1571 if (Pred == ICmpInst::ICMP_EQ && V == FVal) {
1572 // (V == UMIN) ? UMIN+1 : V --> umax(V, UMIN+1)
1573 if (CmpC->isMinValue() && match(TVal, m_SpecificInt(*CmpC + 1)))
1574 return Builder.CreateBinaryIntrinsic(Intrinsic::umax, V, TVal);
1575 // (V == UMAX) ? UMAX-1 : V --> umin(V, UMAX-1)
1576 if (CmpC->isMaxValue() && match(TVal, m_SpecificInt(*CmpC - 1)))
1577 return Builder.CreateBinaryIntrinsic(Intrinsic::umin, V, TVal);
1578 // (V == SMIN) ? SMIN+1 : V --> smax(V, SMIN+1)
1579 if (CmpC->isMinSignedValue() && match(TVal, m_SpecificInt(*CmpC + 1)))
1580 return Builder.CreateBinaryIntrinsic(Intrinsic::smax, V, TVal);
1581 // (V == SMAX) ? SMAX-1 : V --> smin(V, SMAX-1)
1582 if (CmpC->isMaxSignedValue() && match(TVal, m_SpecificInt(*CmpC - 1)))
1583 return Builder.CreateBinaryIntrinsic(Intrinsic::smin, V, TVal);
1584 }
1585
1586 BinaryOperator *BO;
1587 const APInt *C;
1588 CmpInst::Predicate CPred;
1589 if (match(&SI, m_Select(m_Specific(ICI), m_APInt(C), m_BinOp(BO))))
1590 CPred = ICI->getPredicate();
1591 else if (match(&SI, m_Select(m_Specific(ICI), m_BinOp(BO), m_APInt(C))))
1592 CPred = ICI->getInversePredicate();
1593 else
1594 return nullptr;
1595
1596 const APInt *BinOpC;
1597 if (!match(BO, m_BinOp(m_Specific(V), m_APInt(BinOpC))))
1598 return nullptr;
1599
1601 .binaryOp(BO->getOpcode(), *BinOpC);
1602 if (R == *C) {
1604 return BO;
1605 }
1606 return nullptr;
1607}
1608
1609/// Visit a SelectInst that has an ICmpInst as its first operand.
1611 ICmpInst *ICI) {
1612 if (Instruction *NewSel = foldSelectValueEquivalence(SI, *ICI))
1613 return NewSel;
1614
1615 if (Instruction *NewSPF = canonicalizeSPF(SI, *ICI, *this))
1616 return NewSPF;
1617
1618 if (Value *V = foldSelectInstWithICmpConst(SI, ICI, Builder))
1619 return replaceInstUsesWith(SI, V);
1620
1621 if (Value *V = canonicalizeClampLike(SI, *ICI, Builder))
1622 return replaceInstUsesWith(SI, V);
1623
1624 if (Instruction *NewSel =
1625 tryToReuseConstantFromSelectInComparison(SI, *ICI, *this))
1626 return NewSel;
1627
1628 if (Value *V = foldSelectICmpAnd(SI, ICI, Builder))
1629 return replaceInstUsesWith(SI, V);
1630
1631 // NOTE: if we wanted to, this is where to detect integer MIN/MAX
1632 bool Changed = false;
1633 Value *TrueVal = SI.getTrueValue();
1634 Value *FalseVal = SI.getFalseValue();
1635 ICmpInst::Predicate Pred = ICI->getPredicate();
1636 Value *CmpLHS = ICI->getOperand(0);
1637 Value *CmpRHS = ICI->getOperand(1);
1638 if (CmpRHS != CmpLHS && isa<Constant>(CmpRHS) && !isa<Constant>(CmpLHS)) {
1639 if (CmpLHS == TrueVal && Pred == ICmpInst::ICMP_EQ) {
1640 // Transform (X == C) ? X : Y -> (X == C) ? C : Y
1641 SI.setOperand(1, CmpRHS);
1642 Changed = true;
1643 } else if (CmpLHS == FalseVal && Pred == ICmpInst::ICMP_NE) {
1644 // Transform (X != C) ? Y : X -> (X != C) ? Y : C
1645 SI.setOperand(2, CmpRHS);
1646 Changed = true;
1647 }
1648 }
1649
1650 // Canonicalize a signbit condition to use zero constant by swapping:
1651 // (CmpLHS > -1) ? TV : FV --> (CmpLHS < 0) ? FV : TV
1652 // To avoid conflicts (infinite loops) with other canonicalizations, this is
1653 // not applied with any constant select arm.
1654 if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes()) &&
1655 !match(TrueVal, m_Constant()) && !match(FalseVal, m_Constant()) &&
1656 ICI->hasOneUse()) {
1659 Value *IsNeg = Builder.CreateIsNeg(CmpLHS, ICI->getName());
1660 replaceOperand(SI, 0, IsNeg);
1661 SI.swapValues();
1662 SI.swapProfMetadata();
1663 return &SI;
1664 }
1665
1666 // FIXME: This code is nearly duplicated in InstSimplify. Using/refactoring
1667 // decomposeBitTestICmp() might help.
1668 if (TrueVal->getType()->isIntOrIntVectorTy()) {
1669 unsigned BitWidth =
1670 DL.getTypeSizeInBits(TrueVal->getType()->getScalarType());
1671 APInt MinSignedValue = APInt::getSignedMinValue(BitWidth);
1672 Value *X;
1673 const APInt *Y, *C;
1674 bool TrueWhenUnset;
1675 bool IsBitTest = false;
1676 if (ICmpInst::isEquality(Pred) &&
1677 match(CmpLHS, m_And(m_Value(X), m_Power2(Y))) &&
1678 match(CmpRHS, m_Zero())) {
1679 IsBitTest = true;
1680 TrueWhenUnset = Pred == ICmpInst::ICMP_EQ;
1681 } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) {
1682 X = CmpLHS;
1683 Y = &MinSignedValue;
1684 IsBitTest = true;
1685 TrueWhenUnset = false;
1686 } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) {
1687 X = CmpLHS;
1688 Y = &MinSignedValue;
1689 IsBitTest = true;
1690 TrueWhenUnset = true;
1691 }
1692 if (IsBitTest) {
1693 Value *V = nullptr;
1694 // (X & Y) == 0 ? X : X ^ Y --> X & ~Y
1695 if (TrueWhenUnset && TrueVal == X &&
1696 match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1697 V = Builder.CreateAnd(X, ~(*Y));
1698 // (X & Y) != 0 ? X ^ Y : X --> X & ~Y
1699 else if (!TrueWhenUnset && FalseVal == X &&
1700 match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1701 V = Builder.CreateAnd(X, ~(*Y));
1702 // (X & Y) == 0 ? X ^ Y : X --> X | Y
1703 else if (TrueWhenUnset && FalseVal == X &&
1704 match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1705 V = Builder.CreateOr(X, *Y);
1706 // (X & Y) != 0 ? X : X ^ Y --> X | Y
1707 else if (!TrueWhenUnset && TrueVal == X &&
1708 match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1709 V = Builder.CreateOr(X, *Y);
1710
1711 if (V)
1712 return replaceInstUsesWith(SI, V);
1713 }
1714 }
1715
1716 if (Instruction *V =
1717 foldSelectICmpAndAnd(SI.getType(), ICI, TrueVal, FalseVal, Builder))
1718 return V;
1719
1720 if (Instruction *V = foldSelectCtlzToCttz(ICI, TrueVal, FalseVal, Builder))
1721 return V;
1722
1723 if (Instruction *V = foldSelectZeroOrOnes(ICI, TrueVal, FalseVal, Builder))
1724 return V;
1725
1726 if (Value *V = foldSelectICmpAndOr(ICI, TrueVal, FalseVal, Builder))
1727 return replaceInstUsesWith(SI, V);
1728
1729 if (Value *V = foldSelectICmpLshrAshr(ICI, TrueVal, FalseVal, Builder))
1730 return replaceInstUsesWith(SI, V);
1731
1732 if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
1733 return replaceInstUsesWith(SI, V);
1734
1735 if (Value *V = canonicalizeSaturatedSubtract(ICI, TrueVal, FalseVal, Builder))
1736 return replaceInstUsesWith(SI, V);
1737
1738 if (Value *V = canonicalizeSaturatedAdd(ICI, TrueVal, FalseVal, Builder))
1739 return replaceInstUsesWith(SI, V);
1740
1741 if (Value *V = foldAbsDiff(ICI, TrueVal, FalseVal, Builder))
1742 return replaceInstUsesWith(SI, V);
1743
1744 return Changed ? &SI : nullptr;
1745}
1746
1747/// SI is a select whose condition is a PHI node (but the two may be in
1748/// different blocks). See if the true/false values (V) are live in all of the
1749/// predecessor blocks of the PHI. For example, cases like this can't be mapped:
1750///
1751/// X = phi [ C1, BB1], [C2, BB2]
1752/// Y = add
1753/// Z = select X, Y, 0
1754///
1755/// because Y is not live in BB1/BB2.
1756static bool canSelectOperandBeMappingIntoPredBlock(const Value *V,
1757 const SelectInst &SI) {
1758 // If the value is a non-instruction value like a constant or argument, it
1759 // can always be mapped.
1760 const Instruction *I = dyn_cast<Instruction>(V);
1761 if (!I) return true;
1762
1763 // If V is a PHI node defined in the same block as the condition PHI, we can
1764 // map the arguments.
1765 const PHINode *CondPHI = cast<PHINode>(SI.getCondition());
1766
1767 if (const PHINode *VP = dyn_cast<PHINode>(I))
1768 if (VP->getParent() == CondPHI->getParent())
1769 return true;
1770
1771 // Otherwise, if the PHI and select are defined in the same block and if V is
1772 // defined in a different block, then we can transform it.
1773 if (SI.getParent() == CondPHI->getParent() &&
1774 I->getParent() != CondPHI->getParent())
1775 return true;
1776
1777 // Otherwise we have a 'hard' case and we can't tell without doing more
1778 // detailed dominator based analysis, punt.
1779 return false;
1780}
1781
1782/// We have an SPF (e.g. a min or max) of an SPF of the form:
1783/// SPF2(SPF1(A, B), C)
1786 Value *B, Instruction &Outer,
1788 Value *C) {
1789 if (Outer.getType() != Inner->getType())
1790 return nullptr;
1791
1792 if (C == A || C == B) {
1793 // MAX(MAX(A, B), B) -> MAX(A, B)
1794 // MIN(MIN(a, b), a) -> MIN(a, b)
1795 // TODO: This could be done in instsimplify.
1796 if (SPF1 == SPF2 && SelectPatternResult::isMinOrMax(SPF1))
1797 return replaceInstUsesWith(Outer, Inner);
1798 }
1799
1800 return nullptr;
1801}
1802
1803/// Turn select C, (X + Y), (X - Y) --> (X + (select C, Y, (-Y))).
1804/// This is even legal for FP.
1805static Instruction *foldAddSubSelect(SelectInst &SI,
1806 InstCombiner::BuilderTy &Builder) {
1807 Value *CondVal = SI.getCondition();
1808 Value *TrueVal = SI.getTrueValue();
1809 Value *FalseVal = SI.getFalseValue();
1810 auto *TI = dyn_cast<Instruction>(TrueVal);
1811 auto *FI = dyn_cast<Instruction>(FalseVal);
1812 if (!TI || !FI || !TI->hasOneUse() || !FI->hasOneUse())
1813 return nullptr;
1814
1815 Instruction *AddOp = nullptr, *SubOp = nullptr;
1816 if ((TI->getOpcode() == Instruction::Sub &&
1817 FI->getOpcode() == Instruction::Add) ||
1818 (TI->getOpcode() == Instruction::FSub &&
1819 FI->getOpcode() == Instruction::FAdd)) {
1820 AddOp = FI;
1821 SubOp = TI;
1822 } else if ((FI->getOpcode() == Instruction::Sub &&
1823 TI->getOpcode() == Instruction::Add) ||
1824 (FI->getOpcode() == Instruction::FSub &&
1825 TI->getOpcode() == Instruction::FAdd)) {
1826 AddOp = TI;
1827 SubOp = FI;
1828 }
1829
1830 if (AddOp) {
1831 Value *OtherAddOp = nullptr;
1832 if (SubOp->getOperand(0) == AddOp->getOperand(0)) {
1833 OtherAddOp = AddOp->getOperand(1);
1834 } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) {
1835 OtherAddOp = AddOp->getOperand(0);
1836 }
1837
1838 if (OtherAddOp) {
1839 // So at this point we know we have (Y -> OtherAddOp):
1840 // select C, (add X, Y), (sub X, Z)
1841 Value *NegVal; // Compute -Z
1842 if (SI.getType()->isFPOrFPVectorTy()) {
1843 NegVal = Builder.CreateFNeg(SubOp->getOperand(1));
1844 if (Instruction *NegInst = dyn_cast<Instruction>(NegVal)) {
1846 Flags &= SubOp->getFastMathFlags();
1847 NegInst->setFastMathFlags(Flags);
1848 }
1849 } else {
1850 NegVal = Builder.CreateNeg(SubOp->getOperand(1));
1851 }
1852
1853 Value *NewTrueOp = OtherAddOp;
1854 Value *NewFalseOp = NegVal;
1855 if (AddOp != TI)
1856 std::swap(NewTrueOp, NewFalseOp);
1857 Value *NewSel = Builder.CreateSelect(CondVal, NewTrueOp, NewFalseOp,
1858 SI.getName() + ".p", &SI);
1859
1860 if (SI.getType()->isFPOrFPVectorTy()) {
1861 Instruction *RI =
1862 BinaryOperator::CreateFAdd(SubOp->getOperand(0), NewSel);
1863
1865 Flags &= SubOp->getFastMathFlags();
1866 RI->setFastMathFlags(Flags);
1867 return RI;
1868 } else
1869 return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel);
1870 }
1871 }
1872 return nullptr;
1873}
1874
1875/// Turn X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
1876/// And X - Y overflows ? 0 : X - Y -> usub_sat X, Y
1877/// Along with a number of patterns similar to:
1878/// X + Y overflows ? (X < 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1879/// X - Y overflows ? (X > 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1880static Instruction *
1881foldOverflowingAddSubSelect(SelectInst &SI, InstCombiner::BuilderTy &Builder) {
1882 Value *CondVal = SI.getCondition();
1883 Value *TrueVal = SI.getTrueValue();
1884 Value *FalseVal = SI.getFalseValue();
1885
1886 WithOverflowInst *II;
1887 if (!match(CondVal, m_ExtractValue<1>(m_WithOverflowInst(II))) ||
1888 !match(FalseVal, m_ExtractValue<0>(m_Specific(II))))
1889 return nullptr;
1890
1891 Value *X = II->getLHS();
1892 Value *Y = II->getRHS();
1893
1894 auto IsSignedSaturateLimit = [&](Value *Limit, bool IsAdd) {
1895 Type *Ty = Limit->getType();
1896
1898 Value *TrueVal, *FalseVal, *Op;
1899 const APInt *C;
1900 if (!match(Limit, m_Select(m_ICmp(Pred, m_Value(Op), m_APInt(C)),
1901 m_Value(TrueVal), m_Value(FalseVal))))
1902 return false;
1903
1904 auto IsZeroOrOne = [](const APInt &C) { return C.isZero() || C.isOne(); };
1905 auto IsMinMax = [&](Value *Min, Value *Max) {
1908 return match(Min, m_SpecificInt(MinVal)) &&
1909 match(Max, m_SpecificInt(MaxVal));
1910 };
1911
1912 if (Op != X && Op != Y)
1913 return false;
1914
1915 if (IsAdd) {
1916 // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1917 // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1918 // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1919 // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1920 if (Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
1921 IsMinMax(TrueVal, FalseVal))
1922 return true;
1923 // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1924 // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1925 // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1926 // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1927 if (Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
1928 IsMinMax(FalseVal, TrueVal))
1929 return true;
1930 } else {
1931 // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1932 // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1933 if (Op == X && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C + 1) &&
1934 IsMinMax(TrueVal, FalseVal))
1935 return true;
1936 // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1937 // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1938 if (Op == X && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 2) &&
1939 IsMinMax(FalseVal, TrueVal))
1940 return true;
1941 // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1942 // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1943 if (Op == Y && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
1944 IsMinMax(FalseVal, TrueVal))
1945 return true;
1946 // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1947 // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1948 if (Op == Y && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
1949 IsMinMax(TrueVal, FalseVal))
1950 return true;
1951 }
1952
1953 return false;
1954 };
1955
1956 Intrinsic::ID NewIntrinsicID;
1957 if (II->getIntrinsicID() == Intrinsic::uadd_with_overflow &&
1958 match(TrueVal, m_AllOnes()))
1959 // X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
1960 NewIntrinsicID = Intrinsic::uadd_sat;
1961 else if (II->getIntrinsicID() == Intrinsic::usub_with_overflow &&
1962 match(TrueVal, m_Zero()))
1963 // X - Y overflows ? 0 : X - Y -> usub_sat X, Y
1964 NewIntrinsicID = Intrinsic::usub_sat;
1965 else if (II->getIntrinsicID() == Intrinsic::sadd_with_overflow &&
1966 IsSignedSaturateLimit(TrueVal, /*IsAdd=*/true))
1967 // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1968 // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1969 // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1970 // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1971 // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1972 // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1973 // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1974 // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1975 NewIntrinsicID = Intrinsic::sadd_sat;
1976 else if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow &&
1977 IsSignedSaturateLimit(TrueVal, /*IsAdd=*/false))
1978 // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1979 // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1980 // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1981 // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1982 // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1983 // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1984 // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1985 // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1986 NewIntrinsicID = Intrinsic::ssub_sat;
1987 else
1988 return nullptr;
1989
1990 Function *F =
1991 Intrinsic::getDeclaration(SI.getModule(), NewIntrinsicID, SI.getType());
1992 return CallInst::Create(F, {X, Y});
1993}
1994
1996 Constant *C;
1997 if (!match(Sel.getTrueValue(), m_Constant(C)) &&
1998 !match(Sel.getFalseValue(), m_Constant(C)))
1999 return nullptr;
2000
2001 Instruction *ExtInst;
2002 if (!match(Sel.getTrueValue(), m_Instruction(ExtInst)) &&
2003 !match(Sel.getFalseValue(), m_Instruction(ExtInst)))
2004 return nullptr;
2005
2006 auto ExtOpcode = ExtInst->getOpcode();
2007 if (ExtOpcode != Instruction::ZExt && ExtOpcode != Instruction::SExt)
2008 return nullptr;
2009
2010 // If we are extending from a boolean type or if we can create a select that
2011 // has the same size operands as its condition, try to narrow the select.
2012 Value *X = ExtInst->getOperand(0);
2013 Type *SmallType = X->getType();
2014 Value *Cond = Sel.getCondition();
2015 auto *Cmp = dyn_cast<CmpInst>(Cond);
2016 if (!SmallType->isIntOrIntVectorTy(1) &&
2017 (!Cmp || Cmp->getOperand(0)->getType() != SmallType))
2018 return nullptr;
2019
2020 // If the constant is the same after truncation to the smaller type and
2021 // extension to the original type, we can narrow the select.
2022 Type *SelType = Sel.getType();
2023 Constant *TruncC = ConstantExpr::getTrunc(C, SmallType);
2024 Constant *ExtC = ConstantExpr::getCast(ExtOpcode, TruncC, SelType);
2025 if (ExtC == C && ExtInst->hasOneUse()) {
2026 Value *TruncCVal = cast<Value>(TruncC);
2027 if (ExtInst == Sel.getFalseValue())
2028 std::swap(X, TruncCVal);
2029
2030 // select Cond, (ext X), C --> ext(select Cond, X, C')
2031 // select Cond, C, (ext X) --> ext(select Cond, C', X)
2032 Value *NewSel = Builder.CreateSelect(Cond, X, TruncCVal, "narrow", &Sel);
2033 return CastInst::Create(Instruction::CastOps(ExtOpcode), NewSel, SelType);
2034 }
2035
2036 // If one arm of the select is the extend of the condition, replace that arm
2037 // with the extension of the appropriate known bool value.
2038 if (Cond == X) {
2039 if (ExtInst == Sel.getTrueValue()) {
2040 // select X, (sext X), C --> select X, -1, C
2041 // select X, (zext X), C --> select X, 1, C
2042 Constant *One = ConstantInt::getTrue(SmallType);
2043 Constant *AllOnesOrOne = ConstantExpr::getCast(ExtOpcode, One, SelType);
2044 return SelectInst::Create(Cond, AllOnesOrOne, C, "", nullptr, &Sel);
2045 } else {
2046 // select X, C, (sext X) --> select X, C, 0
2047 // select X, C, (zext X) --> select X, C, 0
2049 return SelectInst::Create(Cond, C, Zero, "", nullptr, &Sel);
2050 }
2051 }
2052
2053 return nullptr;
2054}
2055
2056/// Try to transform a vector select with a constant condition vector into a
2057/// shuffle for easier combining with other shuffles and insert/extract.
2058static Instruction *canonicalizeSelectToShuffle(SelectInst &SI) {
2059 Value *CondVal = SI.getCondition();
2060 Constant *CondC;
2061 auto *CondValTy = dyn_cast<FixedVectorType>(CondVal->getType());
2062 if (!CondValTy || !match(CondVal, m_Constant(CondC)))
2063 return nullptr;
2064
2065 unsigned NumElts = CondValTy->getNumElements();
2067 Mask.reserve(NumElts);
2068 for (unsigned i = 0; i != NumElts; ++i) {
2069 Constant *Elt = CondC->getAggregateElement(i);
2070 if (!Elt)
2071 return nullptr;
2072
2073 if (Elt->isOneValue()) {
2074 // If the select condition element is true, choose from the 1st vector.
2075 Mask.push_back(i);
2076 } else if (Elt->isNullValue()) {
2077 // If the select condition element is false, choose from the 2nd vector.
2078 Mask.push_back(i + NumElts);
2079 } else if (isa<UndefValue>(Elt)) {
2080 // Undef in a select condition (choose one of the operands) does not mean
2081 // the same thing as undef in a shuffle mask (any value is acceptable), so
2082 // give up.
2083 return nullptr;
2084 } else {
2085 // Bail out on a constant expression.
2086 return nullptr;
2087 }
2088 }
2089
2090 return new ShuffleVectorInst(SI.getTrueValue(), SI.getFalseValue(), Mask);
2091}
2092
2093/// If we have a select of vectors with a scalar condition, try to convert that
2094/// to a vector select by splatting the condition. A splat may get folded with
2095/// other operations in IR and having all operands of a select be vector types
2096/// is likely better for vector codegen.
2097static Instruction *canonicalizeScalarSelectOfVecs(SelectInst &Sel,
2098 InstCombinerImpl &IC) {
2099 auto *Ty = dyn_cast<VectorType>(Sel.getType());
2100 if (!Ty)
2101 return nullptr;
2102
2103 // We can replace a single-use extract with constant index.
2104 Value *Cond = Sel.getCondition();
2106 return nullptr;
2107
2108 // select (extelt V, Index), T, F --> select (splat V, Index), T, F
2109 // Splatting the extracted condition reduces code (we could directly create a
2110 // splat shuffle of the source vector to eliminate the intermediate step).
2111 return IC.replaceOperand(
2112 Sel, 0, IC.Builder.CreateVectorSplat(Ty->getElementCount(), Cond));
2113}
2114
2115/// Reuse bitcasted operands between a compare and select:
2116/// select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2117/// bitcast (select (cmp (bitcast C), (bitcast D)), (bitcast C), (bitcast D))
2118static Instruction *foldSelectCmpBitcasts(SelectInst &Sel,
2119 InstCombiner::BuilderTy &Builder) {
2120 Value *Cond = Sel.getCondition();
2121 Value *TVal = Sel.getTrueValue();
2122 Value *FVal = Sel.getFalseValue();
2123
2124 CmpInst::Predicate Pred;
2125 Value *A, *B;
2126 if (!match(Cond, m_Cmp(Pred, m_Value(A), m_Value(B))))
2127 return nullptr;
2128
2129 // The select condition is a compare instruction. If the select's true/false
2130 // values are already the same as the compare operands, there's nothing to do.
2131 if (TVal == A || TVal == B || FVal == A || FVal == B)
2132 return nullptr;
2133
2134 Value *C, *D;
2135 if (!match(A, m_BitCast(m_Value(C))) || !match(B, m_BitCast(m_Value(D))))
2136 return nullptr;
2137
2138 // select (cmp (bitcast C), (bitcast D)), (bitcast TSrc), (bitcast FSrc)
2139 Value *TSrc, *FSrc;
2140 if (!match(TVal, m_BitCast(m_Value(TSrc))) ||
2141 !match(FVal, m_BitCast(m_Value(FSrc))))
2142 return nullptr;
2143
2144 // If the select true/false values are *different bitcasts* of the same source
2145 // operands, make the select operands the same as the compare operands and
2146 // cast the result. This is the canonical select form for min/max.
2147 Value *NewSel;
2148 if (TSrc == C && FSrc == D) {
2149 // select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2150 // bitcast (select (cmp A, B), A, B)
2151 NewSel = Builder.CreateSelect(Cond, A, B, "", &Sel);
2152 } else if (TSrc == D && FSrc == C) {
2153 // select (cmp (bitcast C), (bitcast D)), (bitcast' D), (bitcast' C) -->
2154 // bitcast (select (cmp A, B), B, A)
2155 NewSel = Builder.CreateSelect(Cond, B, A, "", &Sel);
2156 } else {
2157 return nullptr;
2158 }
2159 return CastInst::CreateBitOrPointerCast(NewSel, Sel.getType());
2160}
2161
2162/// Try to eliminate select instructions that test the returned flag of cmpxchg
2163/// instructions.
2164///
2165/// If a select instruction tests the returned flag of a cmpxchg instruction and
2166/// selects between the returned value of the cmpxchg instruction its compare
2167/// operand, the result of the select will always be equal to its false value.
2168/// For example:
2169///
2170/// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2171/// %1 = extractvalue { i64, i1 } %0, 1
2172/// %2 = extractvalue { i64, i1 } %0, 0
2173/// %3 = select i1 %1, i64 %compare, i64 %2
2174/// ret i64 %3
2175///
2176/// The returned value of the cmpxchg instruction (%2) is the original value
2177/// located at %ptr prior to any update. If the cmpxchg operation succeeds, %2
2178/// must have been equal to %compare. Thus, the result of the select is always
2179/// equal to %2, and the code can be simplified to:
2180///
2181/// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2182/// %1 = extractvalue { i64, i1 } %0, 0
2183/// ret i64 %1
2184///
2185static Value *foldSelectCmpXchg(SelectInst &SI) {
2186 // A helper that determines if V is an extractvalue instruction whose
2187 // aggregate operand is a cmpxchg instruction and whose single index is equal
2188 // to I. If such conditions are true, the helper returns the cmpxchg
2189 // instruction; otherwise, a nullptr is returned.
2190 auto isExtractFromCmpXchg = [](Value *V, unsigned I) -> AtomicCmpXchgInst * {
2191 auto *Extract = dyn_cast<ExtractValueInst>(V);
2192 if (!Extract)
2193 return nullptr;
2194 if (Extract->getIndices()[0] != I)
2195 return nullptr;
2196 return dyn_cast<AtomicCmpXchgInst>(Extract->getAggregateOperand());
2197 };
2198
2199 // If the select has a single user, and this user is a select instruction that
2200 // we can simplify, skip the cmpxchg simplification for now.
2201 if (SI.hasOneUse())
2202 if (auto *Select = dyn_cast<SelectInst>(SI.user_back()))
2203 if (Select->getCondition() == SI.getCondition())
2204 if (Select->getFalseValue() == SI.getTrueValue() ||
2205 Select->getTrueValue() == SI.getFalseValue())
2206 return nullptr;
2207
2208 // Ensure the select condition is the returned flag of a cmpxchg instruction.
2209 auto *CmpXchg = isExtractFromCmpXchg(SI.getCondition(), 1);
2210 if (!CmpXchg)
2211 return nullptr;
2212
2213 // Check the true value case: The true value of the select is the returned
2214 // value of the same cmpxchg used by the condition, and the false value is the
2215 // cmpxchg instruction's compare operand.
2216 if (auto *X = isExtractFromCmpXchg(SI.getTrueValue(), 0))
2217 if (X == CmpXchg && X->getCompareOperand() == SI.getFalseValue())
2218 return SI.getFalseValue();
2219
2220 // Check the false value case: The false value of the select is the returned
2221 // value of the same cmpxchg used by the condition, and the true value is the
2222 // cmpxchg instruction's compare operand.
2223 if (auto *X = isExtractFromCmpXchg(SI.getFalseValue(), 0))
2224 if (X == CmpXchg && X->getCompareOperand() == SI.getTrueValue())
2225 return SI.getFalseValue();
2226
2227 return nullptr;
2228}
2229
2230/// Try to reduce a funnel/rotate pattern that includes a compare and select
2231/// into a funnel shift intrinsic. Example:
2232/// rotl32(a, b) --> (b == 0 ? a : ((a >> (32 - b)) | (a << b)))
2233/// --> call llvm.fshl.i32(a, a, b)
2234/// fshl32(a, b, c) --> (c == 0 ? a : ((b >> (32 - c)) | (a << c)))
2235/// --> call llvm.fshl.i32(a, b, c)
2236/// fshr32(a, b, c) --> (c == 0 ? b : ((a >> (32 - c)) | (b << c)))
2237/// --> call llvm.fshr.i32(a, b, c)
2238static Instruction *foldSelectFunnelShift(SelectInst &Sel,
2239 InstCombiner::BuilderTy &Builder) {
2240 // This must be a power-of-2 type for a bitmasking transform to be valid.
2241 unsigned Width = Sel.getType()->getScalarSizeInBits();
2242 if (!isPowerOf2_32(Width))
2243 return nullptr;
2244
2245 BinaryOperator *Or0, *Or1;
2246 if (!match(Sel.getFalseValue(), m_OneUse(m_Or(m_BinOp(Or0), m_BinOp(Or1)))))
2247 return nullptr;
2248
2249 Value *SV0, *SV1, *SA0, *SA1;
2250 if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(SV0),
2251 m_ZExtOrSelf(m_Value(SA0))))) ||
2253 m_ZExtOrSelf(m_Value(SA1))))) ||
2254 Or0->getOpcode() == Or1->getOpcode())
2255 return nullptr;
2256
2257 // Canonicalize to or(shl(SV0, SA0), lshr(SV1, SA1)).
2258 if (Or0->getOpcode() == BinaryOperator::LShr) {
2259 std::swap(Or0, Or1);
2260 std::swap(SV0, SV1);
2261 std::swap(SA0, SA1);
2262 }
2263 assert(Or0->getOpcode() == BinaryOperator::Shl &&
2264 Or1->getOpcode() == BinaryOperator::LShr &&
2265 "Illegal or(shift,shift) pair");
2266
2267 // Check the shift amounts to see if they are an opposite pair.
2268 Value *ShAmt;
2269 if (match(SA1, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA0)))))
2270 ShAmt = SA0;
2271 else if (match(SA0, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA1)))))
2272 ShAmt = SA1;
2273 else
2274 return nullptr;
2275
2276 // We should now have this pattern:
2277 // select ?, TVal, (or (shl SV0, SA0), (lshr SV1, SA1))
2278 // The false value of the select must be a funnel-shift of the true value:
2279 // IsFShl -> TVal must be SV0 else TVal must be SV1.
2280 bool IsFshl = (ShAmt == SA0);
2281 Value *TVal = Sel.getTrueValue();
2282 if ((IsFshl && TVal != SV0) || (!IsFshl && TVal != SV1))
2283 return nullptr;
2284
2285 // Finally, see if the select is filtering out a shift-by-zero.
2286 Value *Cond = Sel.getCondition();
2288 if (!match(Cond, m_OneUse(m_ICmp(Pred, m_Specific(ShAmt), m_ZeroInt()))) ||
2289 Pred != ICmpInst::ICMP_EQ)
2290 return nullptr;
2291
2292 // If this is not a rotate then the select was blocking poison from the
2293 // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.
2294 if (SV0 != SV1) {
2295 if (IsFshl && !llvm::isGuaranteedNotToBePoison(SV1))
2296 SV1 = Builder.CreateFreeze(SV1);
2297 else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(SV0))
2298 SV0 = Builder.CreateFreeze(SV0);
2299 }
2300
2301 // This is a funnel/rotate that avoids shift-by-bitwidth UB in a suboptimal way.
2302 // Convert to funnel shift intrinsic.
2303 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2305 ShAmt = Builder.CreateZExt(ShAmt, Sel.getType());
2306 return CallInst::Create(F, { SV0, SV1, ShAmt });
2307}
2308
2309static Instruction *foldSelectToCopysign(SelectInst &Sel,
2310 InstCombiner::BuilderTy &Builder) {
2311 Value *Cond = Sel.getCondition();
2312 Value *TVal = Sel.getTrueValue();
2313 Value *FVal = Sel.getFalseValue();
2314 Type *SelType = Sel.getType();
2315
2316 // Match select ?, TC, FC where the constants are equal but negated.
2317 // TODO: Generalize to handle a negated variable operand?
2318 const APFloat *TC, *FC;
2319 if (!match(TVal, m_APFloatAllowUndef(TC)) ||
2320 !match(FVal, m_APFloatAllowUndef(FC)) ||
2321 !abs(*TC).bitwiseIsEqual(abs(*FC)))
2322 return nullptr;
2323
2324 assert(TC != FC && "Expected equal select arms to simplify");
2325
2326 Value *X;
2327 const APInt *C;
2328 bool IsTrueIfSignSet;
2330 if (!match(Cond, m_OneUse(m_ICmp(Pred, m_BitCast(m_Value(X)), m_APInt(C)))) ||
2331 !InstCombiner::isSignBitCheck(Pred, *C, IsTrueIfSignSet) ||
2332 X->getType() != SelType)
2333 return nullptr;
2334
2335 // If needed, negate the value that will be the sign argument of the copysign:
2336 // (bitcast X) < 0 ? -TC : TC --> copysign(TC, X)
2337 // (bitcast X) < 0 ? TC : -TC --> copysign(TC, -X)
2338 // (bitcast X) >= 0 ? -TC : TC --> copysign(TC, -X)
2339 // (bitcast X) >= 0 ? TC : -TC --> copysign(TC, X)
2340 // Note: FMF from the select can not be propagated to the new instructions.
2341 if (IsTrueIfSignSet ^ TC->isNegative())
2342 X = Builder.CreateFNeg(X);
2343
2344 // Canonicalize the magnitude argument as the positive constant since we do
2345 // not care about its sign.
2346 Value *MagArg = ConstantFP::get(SelType, abs(*TC));
2347 Function *F = Intrinsic::getDeclaration(Sel.getModule(), Intrinsic::copysign,
2348 Sel.getType());
2349 return CallInst::Create(F, { MagArg, X });
2350}
2351
2353 if (!isa<VectorType>(Sel.getType()))
2354 return nullptr;
2355
2356 Value *Cond = Sel.getCondition();
2357 Value *TVal = Sel.getTrueValue();
2358 Value *FVal = Sel.getFalseValue();
2359 Value *C, *X, *Y;
2360
2361 if (match(Cond, m_VecReverse(m_Value(C)))) {
2362 auto createSelReverse = [&](Value *C, Value *X, Value *Y) {
2363 Value *V = Builder.CreateSelect(C, X, Y, Sel.getName(), &Sel);
2364 if (auto *I = dyn_cast<Instruction>(V))
2365 I->copyIRFlags(&Sel);
2366 Module *M = Sel.getModule();
2368 M, Intrinsic::experimental_vector_reverse, V->getType());
2369 return CallInst::Create(F, V);
2370 };
2371
2372 if (match(TVal, m_VecReverse(m_Value(X)))) {
2373 // select rev(C), rev(X), rev(Y) --> rev(select C, X, Y)
2374 if (match(FVal, m_VecReverse(m_Value(Y))) &&
2375 (Cond->hasOneUse() || TVal->hasOneUse() || FVal->hasOneUse()))
2376 return createSelReverse(C, X, Y);
2377
2378 // select rev(C), rev(X), FValSplat --> rev(select C, X, FValSplat)
2379 if ((Cond->hasOneUse() || TVal->hasOneUse()) && isSplatValue(FVal))
2380 return createSelReverse(C, X, FVal);
2381 }
2382 // select rev(C), TValSplat, rev(Y) --> rev(select C, TValSplat, Y)
2383 else if (isSplatValue(TVal) && match(FVal, m_VecReverse(m_Value(Y))) &&
2384 (Cond->hasOneUse() || FVal->hasOneUse()))
2385 return createSelReverse(C, TVal, Y);
2386 }
2387
2388 auto *VecTy = dyn_cast<FixedVectorType>(Sel.getType());
2389 if (!VecTy)
2390 return nullptr;
2391
2392 unsigned NumElts = VecTy->getNumElements();
2393 APInt UndefElts(NumElts, 0);
2394 APInt AllOnesEltMask(APInt::getAllOnes(NumElts));
2395 if (Value *V = SimplifyDemandedVectorElts(&Sel, AllOnesEltMask, UndefElts)) {
2396 if (V != &Sel)
2397 return replaceInstUsesWith(Sel, V);
2398 return &Sel;
2399 }
2400
2401 // A select of a "select shuffle" with a common operand can be rearranged
2402 // to select followed by "select shuffle". Because of poison, this only works
2403 // in the case of a shuffle with no undefined mask elements.
2405 if (match(TVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
2406 !is_contained(Mask, PoisonMaskElem) &&
2407 cast<ShuffleVectorInst>(TVal)->isSelect()) {
2408 if (X == FVal) {
2409 // select Cond, (shuf_sel X, Y), X --> shuf_sel X, (select Cond, Y, X)
2410 Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
2411 return new ShuffleVectorInst(X, NewSel, Mask);
2412 }
2413 if (Y == FVal) {
2414 // select Cond, (shuf_sel X, Y), Y --> shuf_sel (select Cond, X, Y), Y
2415 Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
2416 return new ShuffleVectorInst(NewSel, Y, Mask);
2417 }
2418 }
2419 if (match(FVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
2420 !is_contained(Mask, PoisonMaskElem) &&
2421 cast<ShuffleVectorInst>(FVal)->isSelect()) {
2422 if (X == TVal) {
2423 // select Cond, X, (shuf_sel X, Y) --> shuf_sel X, (select Cond, X, Y)
2424 Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
2425 return new ShuffleVectorInst(X, NewSel, Mask);
2426 }
2427 if (Y == TVal) {
2428 // select Cond, Y, (shuf_sel X, Y) --> shuf_sel (select Cond, Y, X), Y
2429 Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
2430 return new ShuffleVectorInst(NewSel, Y, Mask);
2431 }
2432 }
2433
2434 return nullptr;
2435}
2436
2437static Instruction *foldSelectToPhiImpl(SelectInst &Sel, BasicBlock *BB,
2438 const DominatorTree &DT,
2439 InstCombiner::BuilderTy &Builder) {
2440 // Find the block's immediate dominator that ends with a conditional branch
2441 // that matches select's condition (maybe inverted).
2442 auto *IDomNode = DT[BB]->getIDom();
2443 if (!IDomNode)
2444 return nullptr;
2445 BasicBlock *IDom = IDomNode->getBlock();
2446
2447 Value *Cond = Sel.getCondition();
2448 Value *IfTrue, *IfFalse;
2449 BasicBlock *TrueSucc, *FalseSucc;
2450 if (match(IDom->getTerminator(),
2451 m_Br(m_Specific(Cond), m_BasicBlock(TrueSucc),
2452 m_BasicBlock(FalseSucc)))) {
2453 IfTrue = Sel.getTrueValue();
2454 IfFalse = Sel.getFalseValue();
2455 } else if (match(IDom->getTerminator(),
2456 m_Br(m_Not(m_Specific(Cond)), m_BasicBlock(TrueSucc),
2457 m_BasicBlock(FalseSucc)))) {
2458 IfTrue = Sel.getFalseValue();
2459 IfFalse = Sel.getTrueValue();
2460 } else
2461 return nullptr;
2462
2463 // Make sure the branches are actually different.
2464 if (TrueSucc == FalseSucc)
2465 return nullptr;
2466
2467 // We want to replace select %cond, %a, %b with a phi that takes value %a
2468 // for all incoming edges that are dominated by condition `%cond == true`,
2469 // and value %b for edges dominated by condition `%cond == false`. If %a
2470 // or %b are also phis from the same basic block, we can go further and take
2471 // their incoming values from the corresponding blocks.
2472 BasicBlockEdge TrueEdge(IDom, TrueSucc);
2473 BasicBlockEdge FalseEdge(IDom, FalseSucc);
2475 for (auto *Pred : predecessors(BB)) {
2476 // Check implication.
2477 BasicBlockEdge Incoming(Pred, BB);
2478 if (DT.dominates(TrueEdge, Incoming))
2479 Inputs[Pred] = IfTrue->DoPHITranslation(BB, Pred);
2480 else if (DT.dominates(FalseEdge, Incoming))
2481 Inputs[Pred] = IfFalse->DoPHITranslation(BB, Pred);
2482 else
2483 return nullptr;
2484 // Check availability.
2485 if (auto *Insn = dyn_cast<Instruction>(Inputs[Pred]))
2486 if (!DT.dominates(Insn, Pred->getTerminator()))
2487 return nullptr;
2488 }
2489
2490 Builder.SetInsertPoint(&*BB->begin());
2491 auto *PN = Builder.CreatePHI(Sel.getType(), Inputs.size());
2492 for (auto *Pred : predecessors(BB))
2493 PN->addIncoming(Inputs[Pred], Pred);
2494 PN->takeName(&Sel);
2495 return PN;
2496}
2497
2498static Instruction *foldSelectToPhi(SelectInst &Sel, const DominatorTree &DT,
2499 InstCombiner::BuilderTy &Builder) {
2500 // Try to replace this select with Phi in one of these blocks.
2501 SmallSetVector<BasicBlock *, 4> CandidateBlocks;
2502 CandidateBlocks.insert(Sel.getParent());
2503 for (Value *V : Sel.operands())
2504 if (auto *I = dyn_cast<Instruction>(V))
2505 CandidateBlocks.insert(I->getParent());
2506
2507 for (BasicBlock *BB : CandidateBlocks)
2508 if (auto *PN = foldSelectToPhiImpl(Sel, BB, DT, Builder))
2509 return PN;
2510 return nullptr;
2511}
2512
2513static Value *foldSelectWithFrozenICmp(SelectInst &Sel, InstCombiner::BuilderTy &Builder) {
2514 FreezeInst *FI = dyn_cast<FreezeInst>(Sel.getCondition());
2515 if (!FI)
2516 return nullptr;
2517
2518 Value *Cond = FI->getOperand(0);
2519 Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
2520
2521 // select (freeze(x == y)), x, y --> y
2522 // select (freeze(x != y)), x, y --> x
2523 // The freeze should be only used by this select. Otherwise, remaining uses of
2524 // the freeze can observe a contradictory value.
2525 // c = freeze(x == y) ; Let's assume that y = poison & x = 42; c is 0 or 1
2526 // a = select c, x, y ;
2527 // f(a, c) ; f(poison, 1) cannot happen, but if a is folded
2528 // ; to y, this can happen.
2529 CmpInst::Predicate Pred;
2530 if (FI->hasOneUse() &&
2531 match(Cond, m_c_ICmp(Pred, m_Specific(TrueVal), m_Specific(FalseVal))) &&
2532 (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)) {
2533 return Pred == ICmpInst::ICMP_EQ ? FalseVal : TrueVal;
2534 }
2535
2536 return nullptr;
2537}
2538
2539Instruction *InstCombinerImpl::foldAndOrOfSelectUsingImpliedCond(Value *Op,
2540 SelectInst &SI,
2541 bool IsAnd) {
2542 Value *CondVal = SI.getCondition();
2543 Value *A = SI.getTrueValue();
2544 Value *B = SI.getFalseValue();
2545
2546 assert(Op->getType()->isIntOrIntVectorTy(1) &&
2547 "Op must be either i1 or vector of i1.");
2548
2549 std::optional<bool> Res = isImpliedCondition(Op, CondVal, DL, IsAnd);
2550 if (!Res)
2551 return nullptr;
2552
2553 Value *Zero = Constant::getNullValue(A->getType());
2554 Value *One = Constant::getAllOnesValue(A->getType());
2555
2556 if (*Res == true) {
2557 if (IsAnd)
2558 // select op, (select cond, A, B), false => select op, A, false
2559 // and op, (select cond, A, B) => select op, A, false
2560 // if op = true implies condval = true.
2561 return SelectInst::Create(Op, A, Zero);
2562 else
2563 // select op, true, (select cond, A, B) => select op, true, A
2564 // or op, (select cond, A, B) => select op, true, A
2565 // if op = false implies condval = true.
2566 return SelectInst::Create(Op, One, A);
2567 } else {
2568 if (IsAnd)
2569 // select op, (select cond, A, B), false => select op, B, false
2570 // and op, (select cond, A, B) => select op, B, false
2571 // if op = true implies condval = false.
2572 return SelectInst::Create(Op, B, Zero);
2573 else
2574 // select op, true, (select cond, A, B) => select op, true, B
2575 // or op, (select cond, A, B) => select op, true, B
2576 // if op = false implies condval = false.
2577 return SelectInst::Create(Op, One, B);
2578 }
2579}
2580
2581// Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need
2582// fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work.
2583static Instruction *foldSelectWithFCmpToFabs(SelectInst &SI,
2584 InstCombinerImpl &IC) {
2585 Value *CondVal = SI.getCondition();
2586
2587 bool ChangedFMF = false;
2588 for (bool Swap : {false, true}) {
2589 Value *TrueVal = SI.getTrueValue();
2590 Value *X = SI.getFalseValue();
2591 CmpInst::Predicate Pred;
2592
2593 if (Swap)
2594 std::swap(TrueVal, X);
2595
2596 if (!match(CondVal, m_FCmp(Pred, m_Specific(X), m_AnyZeroFP())))
2597 continue;
2598
2599 // fold (X <= +/-0.0) ? (0.0 - X) : X to fabs(X), when 'Swap' is false
2600 // fold (X > +/-0.0) ? X : (0.0 - X) to fabs(X), when 'Swap' is true
2601 if (match(TrueVal, m_FSub(m_PosZeroFP(), m_Specific(X)))) {
2602 if (!Swap && (Pred == FCmpInst::FCMP_OLE || Pred == FCmpInst::FCMP_ULE)) {
2603 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2604 return IC.replaceInstUsesWith(SI, Fabs);
2605 }
2606 if (Swap && (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_UGT)) {
2607 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2608 return IC.replaceInstUsesWith(SI, Fabs);
2609 }
2610 }
2611
2612 if (!match(TrueVal, m_FNeg(m_Specific(X))))
2613 return nullptr;
2614
2615 // Forward-propagate nnan and ninf from the fneg to the select.
2616 // If all inputs are not those values, then the select is not either.
2617 // Note: nsz is defined differently, so it may not be correct to propagate.
2618 FastMathFlags FMF = cast<FPMathOperator>(TrueVal)->getFastMathFlags();
2619 if (FMF.noNaNs() && !SI.hasNoNaNs()) {
2620 SI.setHasNoNaNs(true);
2621 ChangedFMF = true;
2622 }
2623 if (FMF.noInfs() && !SI.hasNoInfs()) {
2624 SI.setHasNoInfs(true);
2625 ChangedFMF = true;
2626 }
2627
2628 // With nsz, when 'Swap' is false:
2629 // fold (X < +/-0.0) ? -X : X or (X <= +/-0.0) ? -X : X to fabs(X)
2630 // fold (X > +/-0.0) ? -X : X or (X >= +/-0.0) ? -X : X to -fabs(x)
2631 // when 'Swap' is true:
2632 // fold (X > +/-0.0) ? X : -X or (X >= +/-0.0) ? X : -X to fabs(X)
2633 // fold (X < +/-0.0) ? X : -X or (X <= +/-0.0) ? X : -X to -fabs(X)
2634 //
2635 // Note: We require "nnan" for this fold because fcmp ignores the signbit
2636 // of NAN, but IEEE-754 specifies the signbit of NAN values with
2637 // fneg/fabs operations.
2638 if (!SI.hasNoSignedZeros() || !SI.hasNoNaNs())
2639 return nullptr;
2640
2641 if (Swap)
2642 Pred = FCmpInst::getSwappedPredicate(Pred);
2643
2644 bool IsLTOrLE = Pred == FCmpInst::FCMP_OLT || Pred == FCmpInst::FCMP_OLE ||
2645 Pred == FCmpInst::FCMP_ULT || Pred == FCmpInst::FCMP_ULE;
2646 bool IsGTOrGE = Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_OGE ||
2647 Pred == FCmpInst::FCMP_UGT || Pred == FCmpInst::FCMP_UGE;
2648
2649 if (IsLTOrLE) {
2650 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2651 return IC.replaceInstUsesWith(SI, Fabs);
2652 }
2653 if (IsGTOrGE) {
2654 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2655 Instruction *NewFNeg = UnaryOperator::CreateFNeg(Fabs);
2656 NewFNeg->setFastMathFlags(SI.getFastMathFlags());
2657 return NewFNeg;
2658 }
2659 }
2660
2661 return ChangedFMF ? &SI : nullptr;
2662}
2663
2664// Match the following IR pattern:
2665// %x.lowbits = and i8 %x, %lowbitmask
2666// %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 0
2667// %x.biased = add i8 %x, %bias
2668// %x.biased.highbits = and i8 %x.biased, %highbitmask
2669// %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
2670// Define:
2671// %alignment = add i8 %lowbitmask, 1
2672// Iff 1. an %alignment is a power-of-two (aka, %lowbitmask is a low bit mask)
2673// and 2. %bias is equal to either %lowbitmask or %alignment,
2674// and 3. %highbitmask is equal to ~%lowbitmask (aka, to -%alignment)
2675// then this pattern can be transformed into:
2676// %x.offset = add i8 %x, %lowbitmask
2677// %x.roundedup = and i8 %x.offset, %highbitmask
2678static Value *
2679foldRoundUpIntegerWithPow2Alignment(SelectInst &SI,
2680 InstCombiner::BuilderTy &Builder) {
2681 Value *Cond = SI.getCondition();
2682 Value *X = SI.getTrueValue();
2683 Value *XBiasedHighBits = SI.getFalseValue();
2684
2686 Value *XLowBits;
2687 if (!match(Cond, m_ICmp(Pred, m_Value(XLowBits), m_ZeroInt())) ||
2688 !ICmpInst::isEquality(Pred))
2689 return nullptr;
2690
2691 if (Pred == ICmpInst::Predicate::ICMP_NE)
2692 std::swap(X, XBiasedHighBits);
2693
2694 // FIXME: we could support non non-splats here.
2695
2696 const APInt *LowBitMaskCst;
2697 if (!match(XLowBits, m_And(m_Specific(X), m_APIntAllowUndef(LowBitMaskCst))))
2698 return nullptr;
2699
2700 // Match even if the AND and ADD are swapped.
2701 const APInt *BiasCst, *HighBitMaskCst;
2702 if (!match(XBiasedHighBits,
2704 m_APIntAllowUndef(HighBitMaskCst))) &&
2705 !match(XBiasedHighBits,
2706 m_Add(m_And(m_Specific(X), m_APIntAllowUndef(HighBitMaskCst)),
2707 m_APIntAllowUndef(BiasCst))))
2708 return nullptr;
2709
2710 if (!LowBitMaskCst->isMask())
2711 return nullptr;
2712
2713 APInt InvertedLowBitMaskCst = ~*LowBitMaskCst;
2714 if (InvertedLowBitMaskCst != *HighBitMaskCst)
2715 return nullptr;
2716
2717 APInt AlignmentCst = *LowBitMaskCst + 1;
2718
2719 if (*BiasCst != AlignmentCst && *BiasCst != *LowBitMaskCst)
2720 return nullptr;
2721
2722 if (!XBiasedHighBits->hasOneUse()) {
2723 if (*BiasCst == *LowBitMaskCst)
2724 return XBiasedHighBits;
2725 return nullptr;
2726 }
2727
2728 // FIXME: could we preserve undef's here?
2729 Type *Ty = X->getType();
2730 Value *XOffset = Builder.CreateAdd(X, ConstantInt::get(Ty, *LowBitMaskCst),
2731 X->getName() + ".biased");
2732 Value *R = Builder.CreateAnd(XOffset, ConstantInt::get(Ty, *HighBitMaskCst));
2733 R->takeName(&SI);
2734 return R;
2735}
2736
2737namespace {
2738struct DecomposedSelect {
2739 Value *Cond = nullptr;
2740 Value *TrueVal = nullptr;
2741 Value *FalseVal = nullptr;
2742};
2743} // namespace
2744
2745/// Look for patterns like
2746/// %outer.cond = select i1 %inner.cond, i1 %alt.cond, i1 false
2747/// %inner.sel = select i1 %inner.cond, i8 %inner.sel.t, i8 %inner.sel.f
2748/// %outer.sel = select i1 %outer.cond, i8 %outer.sel.t, i8 %inner.sel
2749/// and rewrite it as
2750/// %inner.sel = select i1 %cond.alternative, i8 %sel.outer.t, i8 %sel.inner.t
2751/// %sel.outer = select i1 %cond.inner, i8 %inner.sel, i8 %sel.inner.f
2752static Instruction *foldNestedSelects(SelectInst &OuterSelVal,
2753 InstCombiner::BuilderTy &Builder) {
2754 // We must start with a `select`.
2755 DecomposedSelect OuterSel;
2756 match(&OuterSelVal,
2757 m_Select(m_Value(OuterSel.Cond), m_Value(OuterSel.TrueVal),
2758 m_Value(OuterSel.FalseVal)));
2759
2760 // Canonicalize inversion of the outermost `select`'s condition.
2761 if (match(OuterSel.Cond, m_Not(m_Value(OuterSel.Cond))))
2762 std::swap(OuterSel.TrueVal, OuterSel.FalseVal);
2763
2764 // The condition of the outermost select must be an `and`/`or`.
2765 if (!match(OuterSel.Cond, m_c_LogicalOp(m_Value(), m_Value())))
2766 return nullptr;
2767
2768 // Depending on the logical op, inner select might be in different hand.
2769 bool IsAndVariant = match(OuterSel.Cond, m_LogicalAnd());
2770 Value *InnerSelVal = IsAndVariant ? OuterSel.FalseVal : OuterSel.TrueVal;
2771
2772 // Profitability check - avoid increasing instruction count.
2773 if (none_of(ArrayRef<Value *>({OuterSelVal.getCondition(), InnerSelVal}),
2774 [](Value *V) { return V->hasOneUse(); }))
2775 return nullptr;
2776
2777 // The appropriate hand of the outermost `select` must be a select itself.
2778 DecomposedSelect InnerSel;
2779 if (!match(InnerSelVal,
2780 m_Select(m_Value(InnerSel.Cond), m_Value(InnerSel.TrueVal),
2781 m_Value(InnerSel.FalseVal))))
2782 return nullptr;
2783
2784 // Canonicalize inversion of the innermost `select`'s condition.
2785 if (match(InnerSel.Cond, m_Not(m_Value(InnerSel.Cond))))
2786 std::swap(InnerSel.TrueVal, InnerSel.FalseVal);
2787
2788 Value *AltCond = nullptr;
2789 auto matchOuterCond = [OuterSel, &AltCond](auto m_InnerCond) {
2790 return match(OuterSel.Cond, m_c_LogicalOp(m_InnerCond, m_Value(AltCond)));
2791 };
2792
2793 // Finally, match the condition that was driving the outermost `select`,
2794 // it should be a logical operation between the condition that was driving
2795 // the innermost `select` (after accounting for the possible inversions
2796 // of the condition), and some other condition.
2797 if (matchOuterCond(m_Specific(InnerSel.Cond))) {
2798 // Done!
2799 } else if (Value * NotInnerCond; matchOuterCond(m_CombineAnd(
2800 m_Not(m_Specific(InnerSel.Cond)), m_Value(NotInnerCond)))) {
2801 // Done!
2802 std::swap(InnerSel.TrueVal, InnerSel.FalseVal);
2803 InnerSel.Cond = NotInnerCond;
2804 } else // Not the pattern we were looking for.
2805 return nullptr;
2806
2807 Value *SelInner = Builder.CreateSelect(
2808 AltCond, IsAndVariant ? OuterSel.TrueVal : InnerSel.FalseVal,
2809 IsAndVariant ? InnerSel.TrueVal : OuterSel.FalseVal);
2810 SelInner->takeName(InnerSelVal);
2811 return SelectInst::Create(InnerSel.Cond,
2812 IsAndVariant ? SelInner : InnerSel.TrueVal,
2813 !IsAndVariant ? SelInner : InnerSel.FalseVal);
2814}
2815
2817 Value *CondVal = SI.getCondition();
2818 Value *TrueVal = SI.getTrueValue();
2819 Value *FalseVal = SI.getFalseValue();
2820 Type *SelType = SI.getType();
2821
2822 // Avoid potential infinite loops by checking for non-constant condition.
2823 // TODO: Can we assert instead by improving canonicalizeSelectToShuffle()?
2824 // Scalar select must have simplified?
2825 if (!SelType->isIntOrIntVectorTy(1) || isa<Constant>(CondVal) ||
2826 TrueVal->getType() != CondVal->getType())
2827 return nullptr;
2828
2829 auto *One = ConstantInt::getTrue(SelType);
2830 auto *Zero = ConstantInt::getFalse(SelType);
2831 Value *A, *B, *C, *D;
2832
2833 // Folding select to and/or i1 isn't poison safe in general. impliesPoison
2834 // checks whether folding it does not convert a well-defined value into
2835 // poison.
2836 if (match(TrueVal, m_One())) {
2837 if (impliesPoison(FalseVal, CondVal)) {
2838 // Change: A = select B, true, C --> A = or B, C
2839 return BinaryOperator::CreateOr(CondVal, FalseVal);
2840 }
2841
2842 if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
2843 if (auto *RHS = dyn_cast<FCmpInst>(FalseVal))
2844 if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ false,
2845 /*IsSelectLogical*/ true))
2846 return replaceInstUsesWith(SI, V);
2847
2848 // (A && B) || (C && B) --> (A || C) && B
2849 if (match(CondVal, m_LogicalAnd(m_Value(A), m_Value(B))) &&
2850 match(FalseVal, m_LogicalAnd(m_Value(C), m_Value(D))) &&
2851 (CondVal->hasOneUse() || FalseVal->hasOneUse())) {
2852 bool CondLogicAnd = isa<SelectInst>(CondVal);
2853 bool FalseLogicAnd = isa<SelectInst>(FalseVal);
2854 auto AndFactorization = [&](Value *Common, Value *InnerCond,
2855 Value *InnerVal,
2856 bool SelFirst = false) -> Instruction * {
2857 Value *InnerSel = Builder.CreateSelect(InnerCond, One, InnerVal);
2858 if (SelFirst)
2859 std::swap(Common, InnerSel);
2860 if (FalseLogicAnd || (CondLogicAnd && Common == A))
2861 return SelectInst::Create(Common, InnerSel, Zero);
2862 else
2863 return BinaryOperator::CreateAnd(Common, InnerSel);
2864 };
2865
2866 if (A == C)
2867 return AndFactorization(A, B, D);
2868 if (A == D)
2869 return AndFactorization(A, B, C);
2870 if (B == C)
2871 return AndFactorization(B, A, D);
2872 if (B == D)
2873 return AndFactorization(B, A, C, CondLogicAnd && FalseLogicAnd);
2874 }
2875 }
2876
2877 if (match(FalseVal, m_Zero())) {
2878 if (impliesPoison(TrueVal, CondVal)) {
2879 // Change: A = select B, C, false --> A = and B, C
2880 return BinaryOperator::CreateAnd(CondVal, TrueVal);
2881 }
2882
2883 if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
2884 if (auto *RHS = dyn_cast<FCmpInst>(TrueVal))
2885 if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ true,
2886 /*IsSelectLogical*/ true))
2887 return replaceInstUsesWith(SI, V);
2888
2889 // (A || B) && (C || B) --> (A && C) || B
2890 if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
2891 match(TrueVal, m_LogicalOr(m_Value(C), m_Value(D))) &&
2892 (CondVal->hasOneUse() || TrueVal->hasOneUse())) {
2893 bool CondLogicOr = isa<SelectInst>(CondVal);
2894 bool TrueLogicOr = isa<SelectInst>(TrueVal);
2895 auto OrFactorization = [&](Value *Common, Value *InnerCond,
2896 Value *InnerVal,
2897 bool SelFirst = false) -> Instruction * {
2898 Value *InnerSel = Builder.CreateSelect(InnerCond, InnerVal, Zero);
2899 if (SelFirst)
2900 std::swap(Common, InnerSel);
2901 if (TrueLogicOr || (CondLogicOr && Common == A))
2902 return SelectInst::Create(Common, One, InnerSel);
2903 else
2904 return BinaryOperator::CreateOr(Common, InnerSel);
2905 };
2906
2907 if (A == C)
2908 return OrFactorization(A, B, D);
2909 if (A == D)
2910 return OrFactorization(A, B, C);
2911 if (B == C)
2912 return OrFactorization(B, A, D);
2913 if (B == D)
2914 return OrFactorization(B, A, C, CondLogicOr && TrueLogicOr);
2915 }
2916 }
2917
2918 // We match the "full" 0 or 1 constant here to avoid a potential infinite
2919 // loop with vectors that may have undefined/poison elements.
2920 // select a, false, b -> select !a, b, false
2921 if (match(TrueVal, m_Specific(Zero))) {
2922 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2923 return SelectInst::Create(NotCond, FalseVal, Zero);
2924 }
2925 // select a, b, true -> select !a, true, b
2926 if (match(FalseVal, m_Specific(One))) {
2927 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2928 return SelectInst::Create(NotCond, One, TrueVal);
2929 }
2930
2931 // DeMorgan in select form: !a && !b --> !(a || b)
2932 // select !a, !b, false --> not (select a, true, b)
2933 if (match(&SI, m_LogicalAnd(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
2934 (CondVal->hasOneUse() || TrueVal->hasOneUse()) &&
2937
2938 // DeMorgan in select form: !a || !b --> !(a && b)
2939 // select !a, true, !b --> not (select a, b, false)
2940 if (match(&SI, m_LogicalOr(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
2941 (CondVal->hasOneUse() || FalseVal->hasOneUse()) &&
2944
2945 // select (select a, true, b), true, b -> select a, true, b
2946 if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
2947 match(TrueVal, m_One()) && match(FalseVal, m_Specific(B)))
2948 return replaceOperand(SI, 0, A);
2949 // select (select a, b, false), b, false -> select a, b, false
2950 if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
2951 match(TrueVal, m_Specific(B)) && match(FalseVal, m_Zero()))
2952 return replaceOperand(SI, 0, A);
2953 // select a, (select ~a, true, b), false -> select a, b, false
2954 if (match(TrueVal, m_c_LogicalOr(m_Not(m_Specific(CondVal)), m_Value(B))) &&
2955 match(FalseVal, m_Zero()))
2956 return replaceOperand(SI, 1, B);
2957 // select a, true, (select ~a, b, false) -> select a, true, b
2958 if (match(FalseVal, m_c_LogicalAnd(m_Not(m_Specific(CondVal)), m_Value(B))) &&
2959 match(TrueVal, m_One()))
2960 return replaceOperand(SI, 2, B);
2961
2962 // ~(A & B) & (A | B) --> A ^ B
2965 return BinaryOperator::CreateXor(A, B);
2966
2967 // select (~a | c), a, b -> and a, (or c, freeze(b))
2968 if (match(CondVal, m_c_Or(m_Not(m_Specific(TrueVal)), m_Value(C))) &&
2969 CondVal->hasOneUse()) {
2970 FalseVal = Builder.CreateFreeze(FalseVal);
2971 return BinaryOperator::CreateAnd(TrueVal, Builder.CreateOr(C, FalseVal));
2972 }
2973 // select (~c & b), a, b -> and b, (or freeze(a), c)
2974 if (match(CondVal, m_c_And(m_Not(m_Value(C)), m_Specific(FalseVal))) &&
2975 CondVal->hasOneUse()) {
2976 TrueVal = Builder.CreateFreeze(TrueVal);
2977 return BinaryOperator::CreateAnd(FalseVal, Builder.CreateOr(C, TrueVal));
2978 }
2979
2980 if (match(FalseVal, m_Zero()) || match(TrueVal, m_One())) {
2981 Use *Y = nullptr;
2982 bool IsAnd = match(FalseVal, m_Zero()) ? true : false;
2983 Value *Op1 = IsAnd ? TrueVal : FalseVal;
2984 if (isCheckForZeroAndMulWithOverflow(CondVal, Op1, IsAnd, Y)) {
2985 auto *FI = new FreezeInst(*Y, (*Y)->getName() + ".fr");
2986 InsertNewInstBefore(FI, *cast<Instruction>(Y->getUser()));
2987 replaceUse(*Y, FI);
2988 return replaceInstUsesWith(SI, Op1);
2989 }
2990
2991 if (auto *Op1SI = dyn_cast<SelectInst>(Op1))
2992 if (auto *I = foldAndOrOfSelectUsingImpliedCond(CondVal, *Op1SI,
2993 /* IsAnd */ IsAnd))
2994 return I;
2995
2996 if (auto *ICmp0 = dyn_cast<ICmpInst>(CondVal))
2997 if (auto *ICmp1 = dyn_cast<ICmpInst>(Op1))
2998 if (auto *V = foldAndOrOfICmps(ICmp0, ICmp1, SI, IsAnd,
2999 /* IsLogical */ true))
3000 return replaceInstUsesWith(SI, V);
3001 }
3002
3003 // select (a || b), c, false -> select a, c, false
3004 // select c, (a || b), false -> select c, a, false
3005 // if c implies that b is false.
3006 if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
3007 match(FalseVal, m_Zero())) {
3008 std::optional<bool> Res = isImpliedCondition(TrueVal, B, DL);
3009 if (Res && *Res == false)
3010 return replaceOperand(SI, 0, A);
3011 }
3012 if (match(TrueVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
3013 match(FalseVal, m_Zero())) {
3014 std::optional<bool> Res = isImpliedCondition(CondVal, B, DL);
3015 if (Res && *Res == false)
3016 return replaceOperand(SI, 1, A);
3017 }
3018 // select c, true, (a && b) -> select c, true, a
3019 // select (a && b), true, c -> select a, true, c
3020 // if c = false implies that b = true
3021 if (match(TrueVal, m_One()) &&
3022 match(FalseVal, m_LogicalAnd(m_Value(A), m_Value(B)))) {
3023 std::optional<bool> Res = isImpliedCondition(CondVal, B, DL, false);
3024 if (Res && *Res == true)
3025 return replaceOperand(SI, 2, A);
3026 }
3027 if (match(CondVal, m_LogicalAnd(m_Value(A), m_Value(B))) &&
3028 match(TrueVal, m_One())) {
3029 std::optional<bool> Res = isImpliedCondition(FalseVal, B, DL, false);
3030 if (Res && *Res == true)
3031 return replaceOperand(SI, 0, A);
3032 }
3033
3034 if (match(TrueVal, m_One())) {
3035 Value *C;
3036
3037 // (C && A) || (!C && B) --> sel C, A, B
3038 // (A && C) || (!C && B) --> sel C, A, B
3039 // (C && A) || (B && !C) --> sel C, A, B
3040 // (A && C) || (B && !C) --> sel C, A, B (may require freeze)
3041 if (match(FalseVal, m_c_LogicalAnd(m_Not(m_Value(C)), m_Value(B))) &&
3042 match(CondVal, m_c_LogicalAnd(m_Specific(C), m_Value(A)))) {
3043 auto *SelCond = dyn_cast<SelectInst>(CondVal);
3044 auto *SelFVal = dyn_cast<SelectInst>(FalseVal);
3045 bool MayNeedFreeze = SelCond && SelFVal &&
3046 match(SelFVal->getTrueValue(),
3047 m_Not(m_Specific(SelCond->getTrueValue())));
3048 if (MayNeedFreeze)
3050 return SelectInst::Create(C, A, B);
3051 }
3052
3053 // (!C && A) || (C && B) --> sel C, B, A
3054 // (A && !C) || (C && B) --> sel C, B, A
3055 // (!C && A) || (B && C) --> sel C, B, A
3056 // (A && !C) || (B && C) --> sel C, B, A (may require freeze)
3057 if (match(CondVal, m_c_LogicalAnd(m_Not(m_Value(C)), m_Value(A))) &&
3058 match(FalseVal, m_c_LogicalAnd(m_Specific(C), m_Value(B)))) {
3059 auto *SelCond = dyn_cast<SelectInst>(CondVal);
3060 auto *SelFVal = dyn_cast<SelectInst>(FalseVal);
3061 bool MayNeedFreeze = SelCond && SelFVal &&
3062 match(SelCond->getTrueValue(),
3063 m_Not(m_Specific(SelFVal->getTrueValue())));
3064 if (MayNeedFreeze)
3066 return SelectInst::Create(C, B, A);
3067 }
3068 }
3069
3070 return nullptr;
3071}
3072
3073// Return true if we can safely remove the select instruction for std::bit_ceil
3074// pattern.
3075static bool isSafeToRemoveBitCeilSelect(ICmpInst::Predicate Pred, Value *Cond0,
3076 const APInt *Cond1, Value *CtlzOp,
3077 unsigned BitWidth) {
3078 // The challenge in recognizing std::bit_ceil(X) is that the operand is used
3079 // for the CTLZ proper and select condition, each possibly with some
3080 // operation like add and sub.
3081 //
3082 // Our aim is to make sure that -ctlz & (BitWidth - 1) == 0 even when the
3083 // select instruction would select 1, which allows us to get rid of the select
3084 // instruction.
3085 //
3086 // To see if we can do so, we do some symbolic execution with ConstantRange.
3087 // Specifically, we compute the range of values that Cond0 could take when
3088 // Cond == false. Then we successively transform the range until we obtain
3089 // the range of values that CtlzOp could take.
3090 //
3091 // Conceptually, we follow the def-use chain backward from Cond0 while
3092 // transforming the range for Cond0 until we meet the common ancestor of Cond0
3093 // and CtlzOp. Then we follow the def-use chain forward until we obtain the
3094 // range for CtlzOp. That said, we only follow at most one ancestor from
3095 // Cond0. Likewise, we only follow at most one ancestor from CtrlOp.
3096
3098 CmpInst::getInversePredicate(Pred), *Cond1);
3099
3100 // Match the operation that's used to compute CtlzOp from CommonAncestor. If
3101 // CtlzOp == CommonAncestor, return true as no operation is needed. If a
3102 // match is found, execute the operation on CR, update CR, and return true.
3103 // Otherwise, return false.
3104 auto MatchForward = [&](Value *CommonAncestor) {
3105 const APInt *C = nullptr;
3106 if (CtlzOp == CommonAncestor)
3107 return true;
3108 if (match(CtlzOp, m_Add(m_Specific(CommonAncestor), m_APInt(C)))) {
3109 CR = CR.add(*C);
3110 return true;
3111 }
3112 if (match(CtlzOp, m_Sub(m_APInt(C), m_Specific(CommonAncestor)))) {
3113 CR = ConstantRange(*C).sub(CR);
3114 return true;
3115 }
3116 if (match(CtlzOp, m_Not(m_Specific(CommonAncestor)))) {
3117 CR = CR.binaryNot();
3118 return true;
3119 }
3120 return false;
3121 };
3122
3123 const APInt *C = nullptr;
3124 Value *CommonAncestor;
3125 if (MatchForward(Cond0)) {
3126 // Cond0 is either CtlzOp or CtlzOp's parent. CR has been updated.
3127 } else if (match(Cond0, m_Add(m_Value(CommonAncestor), m_APInt(C)))) {
3128 CR = CR.sub(*C);
3129 if (!MatchForward(CommonAncestor))
3130 return false;
3131 // Cond0's parent is either CtlzOp or CtlzOp's parent. CR has been updated.
3132 } else {
3133 return false;
3134 }
3135
3136 // Return true if all the values in the range are either 0 or negative (if
3137 // treated as signed). We do so by evaluating:
3138 //
3139 // CR - 1 u>= (1 << BitWidth) - 1.
3140 APInt IntMax = APInt::getSignMask(BitWidth) - 1;
3141 CR = CR.sub(APInt(BitWidth, 1));
3142 return CR.icmp(ICmpInst::ICMP_UGE, IntMax);
3143}
3144
3145// Transform the std::bit_ceil(X) pattern like:
3146//
3147// %dec = add i32 %x, -1
3148// %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)
3149// %sub = sub i32 32, %ctlz
3150// %shl = shl i32 1, %sub
3151// %ugt = icmp ugt i32 %x, 1
3152// %sel = select i1 %ugt, i32 %shl, i32 1
3153//
3154// into:
3155//
3156// %dec = add i32 %x, -1
3157// %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)
3158// %neg = sub i32 0, %ctlz
3159// %masked = and i32 %ctlz, 31
3160// %shl = shl i32 1, %sub
3161//
3162// Note that the select is optimized away while the shift count is masked with
3163// 31. We handle some variations of the input operand like std::bit_ceil(X +
3164// 1).
3165static Instruction *foldBitCeil(SelectInst &SI, IRBuilderBase &Builder) {
3166 Type *SelType = SI.getType();
3167 unsigned BitWidth = SelType->getScalarSizeInBits();
3168
3169 Value *FalseVal = SI.getFalseValue();
3170 Value *TrueVal = SI.getTrueValue();
3172 const APInt *Cond1;
3173 Value *Cond0, *Ctlz, *CtlzOp;
3174 if (!match(SI.getCondition(), m_ICmp(Pred, m_Value(Cond0), m_APInt(Cond1))))
3175 return nullptr;
3176
3177 if (match(TrueVal, m_One())) {
3178 std::swap(FalseVal, TrueVal);
3179 Pred = CmpInst::getInversePredicate(Pred);
3180 }
3181
3182 if (!match(FalseVal, m_One()) ||
3183 !match(TrueVal,
3185 m_Value(Ctlz)))))) ||
3186 !match(Ctlz, m_Intrinsic<Intrinsic::ctlz>(m_Value(CtlzOp), m_Zero())) ||
3187 !isSafeToRemoveBitCeilSelect(Pred, Cond0, Cond1, CtlzOp, BitWidth))
3188 return nullptr;
3189
3190 // Build 1 << (-CTLZ & (BitWidth-1)). The negation likely corresponds to a
3191 // single hardware instruction as opposed to BitWidth - CTLZ, where BitWidth
3192 // is an integer constant. Masking with BitWidth-1 comes free on some
3193 // hardware as part of the shift instruction.
3194 Value *Neg = Builder.CreateNeg(Ctlz);
3195 Value *Masked =
3196 Builder.CreateAnd(Neg, ConstantInt::get(SelType, BitWidth - 1));
3197 return BinaryOperator::Create(Instruction::Shl, ConstantInt::get(SelType, 1),
3198 Masked);
3199}
3200
3202 Value *CondVal = SI.getCondition();
3203 Value *TrueVal = SI.getTrueValue();
3204 Value *FalseVal = SI.getFalseValue();
3205 Type *SelType = SI.getType();
3206
3207 if (Value *V = simplifySelectInst(CondVal, TrueVal, FalseVal,
3208 SQ.getWithInstruction(&SI)))
3209 return replaceInstUsesWith(SI, V);
3210
3211 if (Instruction *I = canonicalizeSelectToShuffle(SI))
3212 return I;
3213
3214 if (Instruction *I = canonicalizeScalarSelectOfVecs(SI, *this))
3215 return I;
3216
3217 // If the type of select is not an integer type or if the condition and
3218 // the selection type are not both scalar nor both vector types, there is no
3219 // point in attempting to match these patterns.
3220 Type *CondType = CondVal->getType();
3221 if (!isa<Constant>(CondVal) && SelType->isIntOrIntVectorTy() &&
3222 CondType->isVectorTy() == SelType->isVectorTy()) {
3223 if (Value *S = simplifyWithOpReplaced(TrueVal, CondVal,
3224 ConstantInt::getTrue(CondType), SQ,
3225 /* AllowRefinement */ true))
3226 return replaceOperand(SI, 1, S);
3227
3228 if (Value *S = simplifyWithOpReplaced(FalseVal, CondVal,
3229 ConstantInt::getFalse(CondType), SQ,
3230 /* AllowRefinement */ true))
3231 return replaceOperand(SI, 2, S);
3232
3233 // Handle patterns involving sext/zext + not explicitly,
3234 // as simplifyWithOpReplaced() only looks past one instruction.
3235 Value *NotCond;
3236
3237 // select a, sext(!a), b -> select !a, b, 0
3238 // select a, zext(!a), b -> select !a, b, 0
3239 if (match(TrueVal, m_ZExtOrSExt(m_CombineAnd(m_Value(NotCond),
3240 m_Not(m_Specific(CondVal))))))
3241 return SelectInst::Create(NotCond, FalseVal,
3242 Constant::getNullValue(SelType));
3243
3244 // select a, b, zext(!a) -> select !a, 1, b
3245 if (match(FalseVal, m_ZExt(m_CombineAnd(m_Value(NotCond),
3246 m_Not(m_Specific(CondVal))))))
3247 return SelectInst::Create(NotCond, ConstantInt::get(SelType, 1), TrueVal);
3248
3249 // select a, b, sext(!a) -> select !a, -1, b
3250 if (match(FalseVal, m_SExt(m_CombineAnd(m_Value(NotCond),
3251 m_Not(m_Specific(CondVal))))))
3252 return SelectInst::Create(NotCond, Constant::getAllOnesValue(SelType),
3253 TrueVal);
3254 }
3255
3256 if (Instruction *R = foldSelectOfBools(SI))
3257 return R;
3258
3259 // Selecting between two integer or vector splat integer constants?
3260 //
3261 // Note that we don't handle a scalar select of vectors:
3262 // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>
3263 // because that may need 3 instructions to splat the condition value:
3264 // extend, insertelement, shufflevector.
3265 //
3266 // Do not handle i1 TrueVal and FalseVal otherwise would result in
3267 // zext/sext i1 to i1.
3268 if (SelType->isIntOrIntVectorTy() && !SelType->isIntOrIntVectorTy(1) &&
3269 CondVal->getType()->isVectorTy() == SelType->isVectorTy()) {
3270 // select C, 1, 0 -> zext C to int
3271 if (match(TrueVal, m_One()) && match(FalseVal, m_Zero()))
3272 return new ZExtInst(CondVal, SelType);
3273
3274 // select C, -1, 0 -> sext C to int
3275 if (match(TrueVal, m_AllOnes()) && match(FalseVal, m_Zero()))
3276 return new SExtInst(CondVal, SelType);
3277
3278 // select C, 0, 1 -> zext !C to int
3279 if (match(TrueVal, m_Zero()) && match(FalseVal, m_One())) {
3280 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
3281 return new ZExtInst(NotCond, SelType);
3282 }
3283
3284 // select C, 0, -1 -> sext !C to int
3285 if (match(TrueVal, m_Zero()) && match(FalseVal, m_AllOnes())) {
3286 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
3287 return new SExtInst(NotCond, SelType);
3288 }
3289 }
3290
3291 if (auto *FCmp = dyn_cast<FCmpInst>(CondVal)) {
3292 Value *Cmp0 = FCmp->getOperand(0), *Cmp1 = FCmp->getOperand(1);
3293 // Are we selecting a value based on a comparison of the two values?
3294 if ((Cmp0 == TrueVal && Cmp1 == FalseVal) ||
3295 (Cmp0 == FalseVal && Cmp1 == TrueVal)) {
3296 // Canonicalize to use ordered comparisons by swapping the select
3297 // operands.
3298 //
3299 // e.g.
3300 // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X
3301 if (FCmp->hasOneUse() && FCmpInst::isUnordered(FCmp->getPredicate())) {
3302 FCmpInst::Predicate InvPred = FCmp->getInversePredicate();
3304 // FIXME: The FMF should propagate from the select, not the fcmp.
3305 Builder.setFastMathFlags(FCmp->getFastMathFlags());
3306 Value *NewCond = Builder.CreateFCmp(InvPred, Cmp0, Cmp1,
3307 FCmp->getName() + ".inv");
3308 Value *NewSel = Builder.CreateSelect(NewCond, FalseVal, TrueVal);
3309 return replaceInstUsesWith(SI, NewSel);
3310 }
3311 }
3312 }
3313
3314 if (isa<FPMathOperator>(SI)) {
3315 // TODO: Try to forward-propagate FMF from select arms to the select.
3316
3317 // Canonicalize select of FP values where NaN and -0.0 are not valid as
3318 // minnum/maxnum intrinsics.
3319 if (SI.hasNoNaNs() && SI.hasNoSignedZeros()) {
3320 Value *X, *Y;
3321 if (match(&SI, m_OrdFMax(m_Value(X), m_Value(Y))))
3322 return replaceInstUsesWith(
3323 SI, Builder.CreateBinaryIntrinsic(Intrinsic::maxnum, X, Y, &SI));
3324
3325 if (match(&SI, m_OrdFMin(m_Value(X), m_Value(Y))))
3326 return replaceInstUsesWith(
3327 SI, Builder.CreateBinaryIntrinsic(Intrinsic::minnum, X, Y, &SI));
3328 }
3329 }
3330
3331 // Fold selecting to fabs.
3332 if (Instruction *Fabs = foldSelectWithFCmpToFabs(SI, *this))
3333 return Fabs;
3334
3335 // See if we are selecting two values based on a comparison of the two values.
3336 if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal))
3337 if (Instruction *Result = foldSelectInstWithICmp(SI, ICI))
3338 return Result;
3339
3340 if (Instruction *Add = foldAddSubSelect(SI, Builder))
3341 return Add;
3342 if (Instruction *Add = foldOverflowingAddSubSelect(SI, Builder))
3343 return Add;
3345 return Or;
3346 if (Instruction *Mul = foldSelectZeroOrMul(SI, *this))
3347 return Mul;
3348
3349 // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
3350 auto *TI = dyn_cast<Instruction>(TrueVal);
3351 auto *FI = dyn_cast<Instruction>(FalseVal);
3352 if (TI && FI && TI->getOpcode() == FI->getOpcode())
3353 if (Instruction *IV = foldSelectOpOp(SI, TI, FI))
3354 return IV;
3355
3356 if (Instruction *I = foldSelectExtConst(SI))
3357 return I;
3358
3359 // Fold (select C, (gep Ptr, Idx), Ptr) -> (gep Ptr, (select C, Idx, 0))
3360 // Fold (select C, Ptr, (gep Ptr, Idx)) -> (gep Ptr, (select C, 0, Idx))
3361 auto SelectGepWithBase = [&](GetElementPtrInst *Gep, Value *Base,
3362 bool Swap) -> GetElementPtrInst * {
3363 Value *Ptr = Gep->getPointerOperand();
3364 if (Gep->getNumOperands() != 2 || Gep->getPointerOperand() != Base ||
3365 !Gep->hasOneUse())
3366 return nullptr;
3367 Value *Idx = Gep->getOperand(1);
3368 if (isa<VectorType>(CondVal->getType()) && !isa<VectorType>(Idx->getType()))
3369 return nullptr;
3370 Type *ElementType = Gep->getResultElementType();
3371 Value *NewT = Idx;
3372 Value *NewF = Constant::getNullValue(Idx->getType());
3373 if (Swap)
3374 std::swap(NewT, NewF);
3375 Value *NewSI =
3376 Builder.CreateSelect(CondVal, NewT, NewF, SI.getName() + ".idx", &SI);
3377 return GetElementPtrInst::Create(ElementType, Ptr, {NewSI});
3378 };
3379 if (auto *TrueGep = dyn_cast<GetElementPtrInst>(TrueVal))
3380 if (auto *NewGep = SelectGepWithBase(TrueGep, FalseVal, false))
3381 return NewGep;
3382 if (auto *FalseGep = dyn_cast<GetElementPtrInst>(FalseVal))
3383 if (auto *NewGep = SelectGepWithBase(FalseGep, TrueVal, true))
3384 return NewGep;
3385
3386 // See if we can fold the select into one of our operands.
3387 if (SelType->isIntOrIntVectorTy() || SelType->isFPOrFPVectorTy()) {
3388 if (Instruction *FoldI = foldSelectIntoOp(SI, TrueVal, FalseVal))
3389 return FoldI;
3390
3391 Value *LHS, *RHS;
3392 Instruction::CastOps CastOp;
3393 SelectPatternResult SPR = matchSelectPattern(&SI, LHS, RHS, &CastOp);
3394 auto SPF = SPR.Flavor;
3395 if (SPF) {
3396 Value *LHS2, *RHS2;
3397 if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor)
3398 if (Instruction *R = foldSPFofSPF(cast<Instruction>(LHS), SPF2, LHS2,
3399 RHS2, SI, SPF, RHS))
3400 return R;
3401 if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor)
3402 if (Instruction *R = foldSPFofSPF(cast<Instruction>(RHS), SPF2, LHS2,
3403 RHS2, SI, SPF, LHS))
3404 return R;
3405 }
3406
3408 // Canonicalize so that
3409 // - type casts are outside select patterns.
3410 // - float clamp is transformed to min/max pattern
3411
3412 bool IsCastNeeded = LHS->getType() != SelType;
3413 Value *CmpLHS = cast<CmpInst>(CondVal)->getOperand(0);
3414 Value *CmpRHS = cast<CmpInst>(CondVal)->getOperand(1);
3415 if (IsCastNeeded ||
3416 (LHS->getType()->isFPOrFPVectorTy() &&
3417 ((CmpLHS != LHS && CmpLHS != RHS) ||
3418 (CmpRHS != LHS && CmpRHS != RHS)))) {
3419 CmpInst::Predicate MinMaxPred = getMinMaxPred(SPF, SPR.Ordered);
3420
3421 Value *Cmp;
3422 if (CmpInst::isIntPredicate(MinMaxPred)) {
3423 Cmp = Builder.CreateICmp(MinMaxPred, LHS, RHS);
3424 } else {
3426 auto FMF =
3427 cast<FPMathOperator>(SI.getCondition())->getFastMathFlags();
3429 Cmp = Builder.CreateFCmp(MinMaxPred, LHS, RHS);
3430 }
3431
3432 Value *NewSI = Builder.CreateSelect(Cmp, LHS, RHS, SI.getName(), &SI);
3433 if (!IsCastNeeded)
3434 return replaceInstUsesWith(SI, NewSI);
3435
3436 Value *NewCast = Builder.CreateCast(CastOp, NewSI, SelType);
3437 return replaceInstUsesWith(SI, NewCast);
3438 }
3439 }
3440 }
3441
3442 // See if we can fold the select into a phi node if the condition is a select.
3443 if (auto *PN = dyn_cast<PHINode>(SI.getCondition()))
3444 // The true/false values have to be live in the PHI predecessor's blocks.
3445 if (canSelectOperandBeMappingIntoPredBlock(TrueVal, SI) &&
3446 canSelectOperandBeMappingIntoPredBlock(FalseVal, SI))
3447 if (Instruction *NV = foldOpIntoPhi(SI, PN))
3448 return NV;
3449
3450 if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) {
3451 if (TrueSI->getCondition()->getType() == CondVal->getType()) {
3452 // select(C, select(C, a, b), c) -> select(C, a, c)
3453 if (TrueSI->getCondition() == CondVal) {
3454 if (SI.getTrueValue() == TrueSI->getTrueValue())
3455 return nullptr;
3456 return replaceOperand(SI, 1, TrueSI->getTrueValue());
3457 }
3458 // select(C0, select(C1, a, b), b) -> select(C0&C1, a, b)
3459 // We choose this as normal form to enable folding on the And and
3460 // shortening paths for the values (this helps getUnderlyingObjects() for
3461 // example).
3462 if (TrueSI->getFalseValue() == FalseVal && TrueSI->hasOneUse()) {
3463 Value *And = Builder.CreateLogicalAnd(CondVal, TrueSI->getCondition());
3464 replaceOperand(SI, 0, And);
3465 replaceOperand(SI, 1, TrueSI->getTrueValue());
3466 return &SI;
3467 }
3468 }
3469 }
3470 if (SelectInst *FalseSI = dyn_cast<SelectInst>(FalseVal)) {
3471 if (FalseSI->getCondition()->getType() == CondVal->getType()) {
3472 // select(C, a, select(C, b, c)) -> select(C, a, c)
3473 if (FalseSI->getCondition() == CondVal) {
3474 if (SI.getFalseValue() == FalseSI->getFalseValue())
3475 return nullptr;
3476 return replaceOperand(SI, 2, FalseSI->getFalseValue());
3477 }
3478 // select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b)
3479 if (FalseSI->getTrueValue() == TrueVal && FalseSI->hasOneUse()) {
3480 Value *Or = Builder.CreateLogicalOr(CondVal, FalseSI->getCondition());
3481 replaceOperand(SI, 0, Or);
3482 replaceOperand(SI, 2, FalseSI->getFalseValue());
3483 return &SI;
3484 }
3485 }
3486 }
3487
3488 // Try to simplify a binop sandwiched between 2 selects with the same
3489 // condition. This is not valid for div/rem because the select might be
3490 // preventing a division-by-zero.
3491 // TODO: A div/rem restriction is conservative; use something like
3492 // isSafeToSpeculativelyExecute().
3493 // select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z)
3494 BinaryOperator *TrueBO;
3495 if (match(TrueVal, m_OneUse(m_BinOp(TrueBO))) && !TrueBO->isIntDivRem()) {
3496 if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(0))) {
3497 if (TrueBOSI->getCondition() == CondVal) {
3498 replaceOperand(*TrueBO, 0, TrueBOSI->getTrueValue());
3499 Worklist.push(TrueBO);
3500 return &SI;
3501 }
3502 }
3503 if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(1))) {
3504 if (TrueBOSI->getCondition() == CondVal) {
3505 replaceOperand(*TrueBO, 1, TrueBOSI->getTrueValue());
3506 Worklist.push(TrueBO);
3507 return &SI;
3508 }
3509 }
3510 }
3511
3512 // select(C, Z, binop(select(C, X, Y), W)) -> select(C, Z, binop(Y, W))
3513 BinaryOperator *FalseBO;
3514 if (match(FalseVal, m_OneUse(m_BinOp(FalseBO))) && !FalseBO->isIntDivRem()) {
3515 if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(0))) {
3516 if (FalseBOSI->getCondition() == CondVal) {
3517 replaceOperand(*FalseBO, 0, FalseBOSI->getFalseValue());
3518 Worklist.push(FalseBO);
3519 return &SI;
3520 }
3521 }
3522 if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(1))) {
3523 if (FalseBOSI->getCondition() == CondVal) {
3524 replaceOperand(*FalseBO, 1, FalseBOSI->getFalseValue());
3525 Worklist.push(FalseBO);
3526 return &SI;
3527 }
3528 }
3529 }
3530
3531 Value *NotCond;
3532 if (match(CondVal, m_Not(m_Value(NotCond))) &&
3534 replaceOperand(SI, 0, NotCond);
3535 SI.swapValues();
3536 SI.swapProfMetadata();
3537 return &SI;
3538 }
3539
3540 if (Instruction *I = foldVectorSelect(SI))
3541 return I;
3542
3543 // If we can compute the condition, there's no need for a select.
3544 // Like the above fold, we are attempting to reduce compile-time cost by
3545 // putting this fold here with limitations rather than in InstSimplify.
3546 // The motivation for this call into value tracking is to take advantage of
3547 // the assumption cache, so make sure that is populated.
3548 if (!CondVal->getType()->isVectorTy() && !AC.assumptions().empty()) {
3549 KnownBits Known(1);
3550 computeKnownBits(CondVal, Known, 0, &SI);
3551 if (Known.One.isOne())
3552 return replaceInstUsesWith(SI, TrueVal);
3553 if (Known.Zero.isOne())
3554 return replaceInstUsesWith(SI, FalseVal);
3555 }
3556
3557 if (Instruction *BitCastSel = foldSelectCmpBitcasts(SI, Builder))
3558 return BitCastSel;
3559
3560 // Simplify selects that test the returned flag of cmpxchg instructions.
3561 if (Value *V = foldSelectCmpXchg(SI))
3562 return replaceInstUsesWith(SI, V);
3563
3564 if (Instruction *Select = foldSelectBinOpIdentity(SI, TLI, *this))
3565 return Select;
3566
3567 if (Instruction *Funnel = foldSelectFunnelShift(SI, Builder))
3568 return Funnel;
3569
3570 if (Instruction *Copysign = foldSelectToCopysign(SI, Builder))
3571 return Copysign;
3572
3573 if (Instruction *PN = foldSelectToPhi(SI, DT, Builder))
3574 return replaceInstUsesWith(SI, PN);
3575
3576 if (Value *Fr = foldSelectWithFrozenICmp(SI, Builder))
3577 return replaceInstUsesWith(SI, Fr);
3578
3579 if (Value *V = foldRoundUpIntegerWithPow2Alignment(SI, Builder))
3580 return replaceInstUsesWith(SI, V);
3581
3582 // select(mask, mload(,,mask,0), 0) -> mload(,,mask,0)
3583 // Load inst is intentionally not checked for hasOneUse()
3584 if (match(FalseVal, m_Zero()) &&
3585 (match(TrueVal, m_MaskedLoad(m_Value(), m_Value(), m_Specific(CondVal),
3586 m_CombineOr(m_Undef(), m_Zero()))) ||
3587 match(TrueVal, m_MaskedGather(m_Value(), m_Value(), m_Specific(CondVal),
3588 m_CombineOr(m_Undef(), m_Zero()))))) {
3589 auto *MaskedInst = cast<IntrinsicInst>(TrueVal);
3590 if (isa<UndefValue>(MaskedInst->getArgOperand(3)))
3591 MaskedInst->setArgOperand(3, FalseVal /* Zero */);
3592 return replaceInstUsesWith(SI, MaskedInst);
3593 }
3594
3595 Value *Mask;
3596 if (match(TrueVal, m_Zero()) &&
3597 (match(FalseVal, m_MaskedLoad(m_Value(), m_Value(), m_Value(Mask),
3598 m_CombineOr(m_Undef(), m_Zero()))) ||
3599 match(FalseVal, m_MaskedGather(m_Value(), m_Value(), m_Value(Mask),
3600 m_CombineOr(m_Undef(), m_Zero())))) &&
3601 (CondVal->getType() == Mask->getType())) {
3602 // We can remove the select by ensuring the load zeros all lanes the
3603 // select would have. We determine this by proving there is no overlap
3604 // between the load and select masks.
3605 // (i.e (load_mask & select_mask) == 0 == no overlap)
3606 bool CanMergeSelectIntoLoad = false;
3607 if (Value *V = simplifyAndInst(CondVal, Mask, SQ.getWithInstruction(&SI)))
3608 CanMergeSelectIntoLoad = match(V, m_Zero());
3609
3610 if (CanMergeSelectIntoLoad) {
3611 auto *MaskedInst = cast<IntrinsicInst>(FalseVal);
3612 if (isa<UndefValue>(MaskedInst->getArgOperand(3)))
3613 MaskedInst->setArgOperand(3, TrueVal /* Zero */);
3614 return replaceInstUsesWith(SI, MaskedInst);
3615 }
3616 }
3617
3618 if (Instruction *I = foldNestedSelects(SI, Builder))
3619 return I;
3620
3621 // Match logical variants of the pattern,
3622 // and transform them iff that gets rid of inversions.
3623 // (~x) | y --> ~(x & (~y))
3624 // (~x) & y --> ~(x | (~y))
3626 return &SI;
3627
3628 if (Instruction *I = foldBitCeil(SI, Builder))
3629 return I;
3630
3631 return nullptr;
3632}
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 Value * foldAbsDiff(ICmpInst *Cmp, Value *TVal, Value *FVal, InstCombiner::BuilderTy &Builder)
Try to match patterns with select and subtract as absolute difference.
static Instruction * foldSelectBinOpIdentity(SelectInst &Sel, const TargetLibraryInfo &TLI, InstCombinerImpl &IC)
Replace a select operand based on an equality comparison with the identity constant of a binop.
static Value * 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.
@ Flags
Definition: TextStubV5.cpp:93
Value * RHS
Value * LHS
static const uint32_t IV[8]
Definition: blake3_impl.h:77
bool bitwiseIsEqual(const APFloat &RHS) const
Definition: APFloat.h:1234
bool isNegative() const
Definition: APFloat.h:1269
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
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:209
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:415
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:1164
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:1443
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:409
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:1712
bool isMask(unsigned numBits) const
Definition: APInt.h:476
bool isMaxSignedValue() const
Determine if this is the largest signed value.
Definition: APInt.h:397
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
bool isMaxValue() const
Determine if this is the largest unsigned value.
Definition: APInt.h:391
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:323
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:1357
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1362
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:711
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:740
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:741
@ FCMP_OLT
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:717
@ FCMP_ULE
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:726
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:715
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:716
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:735
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:734
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:738
@ FCMP_ULT
1 1 0 0 True if unordered or less than
Definition: InstrTypes.h:725
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:736
@ FCMP_UGT
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:723
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:718
@ ICMP_EQ
equal
Definition: InstrTypes.h:732
@ ICMP_NE
not equal
Definition: InstrTypes.h:733
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:739
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:737
@ FCMP_UGE
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:724
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:863
bool isFPPredicate() const
Definition: InstrTypes.h:818
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:825
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:801
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:929
bool isIntPredicate() const
Definition: InstrTypes.h:819
bool isUnsigned() const
Definition: InstrTypes.h:967
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
Definition: Constants.cpp:1957
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2600
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:2460
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2089
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2672
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2075
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2581
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:927
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
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:888
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:840
This class represents a range of values.
Definition: ConstantRange.h:47
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other? NOTE: false does not mean that inverse pr...
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange binaryNot() const
Return a new range representing the possible values resulting from a binary-xor of a value in this ra...
ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
This is an important base class in LLVM.
Definition: Constant.h: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:777
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:673
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:20
bool noSignedZeros() const
Definition: FMF.h:68
bool noInfs() const
Definition: FMF.h:67
bool noNaNs() const
Definition: FMF.h:66
This class represents a freeze function that returns random concrete value if an operand is either a ...
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h: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.
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:94
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:956
Value * CreateFCmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2256
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Definition: IRBuilder.cpp:1257
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1134
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2430
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:1678
Value * CreateIsNeg(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg < 0.
Definition: IRBuilder.h:2449
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:964
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1404
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1426
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
Definition: IRBuilder.h:1605
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2059
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:2246
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Definition: IRBuilder.h:1611
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.
bool replaceInInstruction(Value *V, Value *Old, Value *New, unsigned Depth=0)
Instruction * foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI)
bool sinkNotIntoOtherHandOfLogicalOp(Instruction &I)
Instruction * foldSelectIntoOp(SelectInst &SI, Value *, Value *)
Try to fold the select into one of the operands to allow further optimization.
Instruction * visitSelectInst(SelectInst &SI)
Instruction * foldSelectOfBools(SelectInst &SI)
Instruction * foldSelectExtConst(SelectInst &Sel)
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
Definition: InstCombiner.h:146
TargetLibraryInfo & TLI
Definition: InstCombiner.h:72
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombiner.h:419
static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
Definition: InstCombiner.h:219
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:450
const SimplifyQuery SQ
Definition: InstCombiner.h:75
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
Definition: InstCombiner.h:63
const DataLayout & DL
Definition: InstCombiner.h:74
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
Definition: InstCombiner.h:398
AssumptionCache & AC
Definition: InstCombiner.h:71
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
Definition: InstCombiner.h:443
DominatorTree & DT
Definition: InstCombiner.h:73
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:166
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:462
BuilderTy & Builder
Definition: InstCombiner.h:59
static Constant * AddOne(Constant *C)
Add one to a Constant.
Definition: InstCombiner.h:203
void add(Instruction *I)
Add instruction to the worklist.
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.
bool isIntDivRem() const
Definition: Instruction.h:174
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:152
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:312
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:265
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:235
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:217
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:242
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:1061
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:1069
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:384
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:119
@ 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:1465
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.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
m_Intrinsic_Ty< Opnd0 >::Ty m_VecReverse(const Opnd0 &Op0)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
MaxMin_match< FCmpInst, LHS, RHS, ofmin_pred_ty > m_OrdFMin(const LHS &L, const RHS &R)
Match an 'ordered' floating point minimum function.
Definition: