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