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 const DataLayout &DL = Sel0.getModule()->getDataLayout();
1499 ReplacementLow =
1500 ConstantFoldCastOperand(Instruction::SExt, LowC, X->getType(), DL);
1501 ReplacementHigh =
1502 ConstantFoldCastOperand(Instruction::SExt, HighC, X->getType(), DL);
1503 assert(ReplacementLow && ReplacementHigh &&
1504 "Constant folding of ImmConstant cannot fail");
1505 }
1506
1507 // All good, finally emit the new pattern.
1508 Value *ShouldReplaceLow = Builder.CreateICmpSLT(X, ThresholdLowIncl);
1509 Value *ShouldReplaceHigh = Builder.CreateICmpSGE(X, ThresholdHighExcl);
1510 Value *MaybeReplacedLow =
1511 Builder.CreateSelect(ShouldReplaceLow, ReplacementLow, X);
1512
1513 // Create the final select. If we looked through a truncate above, we will
1514 // need to retruncate the result.
1515 Value *MaybeReplacedHigh = Builder.CreateSelect(
1516 ShouldReplaceHigh, ReplacementHigh, MaybeReplacedLow);
1517 return Builder.CreateTrunc(MaybeReplacedHigh, Sel0.getType());
1518}
1519
1520// If we have
1521// %cmp = icmp [canonical predicate] i32 %x, C0
1522// %r = select i1 %cmp, i32 %y, i32 C1
1523// Where C0 != C1 and %x may be different from %y, see if the constant that we
1524// will have if we flip the strictness of the predicate (i.e. without changing
1525// the result) is identical to the C1 in select. If it matches we can change
1526// original comparison to one with swapped predicate, reuse the constant,
1527// and swap the hands of select.
1528static Instruction *
1529tryToReuseConstantFromSelectInComparison(SelectInst &Sel, ICmpInst &Cmp,
1530 InstCombinerImpl &IC) {
1532 Value *X;
1533 Constant *C0;
1534 if (!match(&Cmp, m_OneUse(m_ICmp(
1535 Pred, m_Value(X),
1537 return nullptr;
1538
1539 // If comparison predicate is non-relational, we won't be able to do anything.
1540 if (ICmpInst::isEquality(Pred))
1541 return nullptr;
1542
1543 // If comparison predicate is non-canonical, then we certainly won't be able
1544 // to make it canonical; canonicalizeCmpWithConstant() already tried.
1546 return nullptr;
1547
1548 // If the [input] type of comparison and select type are different, lets abort
1549 // for now. We could try to compare constants with trunc/[zs]ext though.
1550 if (C0->getType() != Sel.getType())
1551 return nullptr;
1552
1553 // ULT with 'add' of a constant is canonical. See foldICmpAddConstant().
1554 // FIXME: Are there more magic icmp predicate+constant pairs we must avoid?
1555 // Or should we just abandon this transform entirely?
1556 if (Pred == CmpInst::ICMP_ULT && match(X, m_Add(m_Value(), m_Constant())))
1557 return nullptr;
1558
1559
1560 Value *SelVal0, *SelVal1; // We do not care which one is from where.
1561 match(&Sel, m_Select(m_Value(), m_Value(SelVal0), m_Value(SelVal1)));
1562 // At least one of these values we are selecting between must be a constant
1563 // else we'll never succeed.
1564 if (!match(SelVal0, m_AnyIntegralConstant()) &&
1565 !match(SelVal1, m_AnyIntegralConstant()))
1566 return nullptr;
1567
1568 // Does this constant C match any of the `select` values?
1569 auto MatchesSelectValue = [SelVal0, SelVal1](Constant *C) {
1570 return C->isElementWiseEqual(SelVal0) || C->isElementWiseEqual(SelVal1);
1571 };
1572
1573 // If C0 *already* matches true/false value of select, we are done.
1574 if (MatchesSelectValue(C0))
1575 return nullptr;
1576
1577 // Check the constant we'd have with flipped-strictness predicate.
1578 auto FlippedStrictness =
1580 if (!FlippedStrictness)
1581 return nullptr;
1582
1583 // If said constant doesn't match either, then there is no hope,
1584 if (!MatchesSelectValue(FlippedStrictness->second))
1585 return nullptr;
1586
1587 // It matched! Lets insert the new comparison just before select.
1589 IC.Builder.SetInsertPoint(&Sel);
1590
1591 Pred = ICmpInst::getSwappedPredicate(Pred); // Yes, swapped.
1592 Value *NewCmp = IC.Builder.CreateICmp(Pred, X, FlippedStrictness->second,
1593 Cmp.getName() + ".inv");
1594 IC.replaceOperand(Sel, 0, NewCmp);
1595 Sel.swapValues();
1596 Sel.swapProfMetadata();
1597
1598 return &Sel;
1599}
1600
1601static Instruction *foldSelectZeroOrOnes(ICmpInst *Cmp, Value *TVal,
1602 Value *FVal,
1603 InstCombiner::BuilderTy &Builder) {
1604 if (!Cmp->hasOneUse())
1605 return nullptr;
1606
1607 const APInt *CmpC;
1608 if (!match(Cmp->getOperand(1), m_APIntAllowUndef(CmpC)))
1609 return nullptr;
1610
1611 // (X u< 2) ? -X : -1 --> sext (X != 0)
1612 Value *X = Cmp->getOperand(0);
1613 if (Cmp->getPredicate() == ICmpInst::ICMP_ULT && *CmpC == 2 &&
1614 match(TVal, m_Neg(m_Specific(X))) && match(FVal, m_AllOnes()))
1615 return new SExtInst(Builder.CreateIsNotNull(X), TVal->getType());
1616
1617 // (X u> 1) ? -1 : -X --> sext (X != 0)
1618 if (Cmp->getPredicate() == ICmpInst::ICMP_UGT && *CmpC == 1 &&
1619 match(FVal, m_Neg(m_Specific(X))) && match(TVal, m_AllOnes()))
1620 return new SExtInst(Builder.CreateIsNotNull(X), TVal->getType());
1621
1622 return nullptr;
1623}
1624
1625static Value *foldSelectInstWithICmpConst(SelectInst &SI, ICmpInst *ICI,
1626 InstCombiner::BuilderTy &Builder) {
1627 const APInt *CmpC;
1628 Value *V;
1629 CmpInst::Predicate Pred;
1630 if (!match(ICI, m_ICmp(Pred, m_Value(V), m_APInt(CmpC))))
1631 return nullptr;
1632
1633 // Match clamp away from min/max value as a max/min operation.
1634 Value *TVal = SI.getTrueValue();
1635 Value *FVal = SI.getFalseValue();
1636 if (Pred == ICmpInst::ICMP_EQ && V == FVal) {
1637 // (V == UMIN) ? UMIN+1 : V --> umax(V, UMIN+1)
1638 if (CmpC->isMinValue() && match(TVal, m_SpecificInt(*CmpC + 1)))
1639 return Builder.CreateBinaryIntrinsic(Intrinsic::umax, V, TVal);
1640 // (V == UMAX) ? UMAX-1 : V --> umin(V, UMAX-1)
1641 if (CmpC->isMaxValue() && match(TVal, m_SpecificInt(*CmpC - 1)))
1642 return Builder.CreateBinaryIntrinsic(Intrinsic::umin, V, TVal);
1643 // (V == SMIN) ? SMIN+1 : V --> smax(V, SMIN+1)
1644 if (CmpC->isMinSignedValue() && match(TVal, m_SpecificInt(*CmpC + 1)))
1645 return Builder.CreateBinaryIntrinsic(Intrinsic::smax, V, TVal);
1646 // (V == SMAX) ? SMAX-1 : V --> smin(V, SMAX-1)
1647 if (CmpC->isMaxSignedValue() && match(TVal, m_SpecificInt(*CmpC - 1)))
1648 return Builder.CreateBinaryIntrinsic(Intrinsic::smin, V, TVal);
1649 }
1650
1651 BinaryOperator *BO;
1652 const APInt *C;
1653 CmpInst::Predicate CPred;
1654 if (match(&SI, m_Select(m_Specific(ICI), m_APInt(C), m_BinOp(BO))))
1655 CPred = ICI->getPredicate();
1656 else if (match(&SI, m_Select(m_Specific(ICI), m_BinOp(BO), m_APInt(C))))
1657 CPred = ICI->getInversePredicate();
1658 else
1659 return nullptr;
1660
1661 const APInt *BinOpC;
1662 if (!match(BO, m_BinOp(m_Specific(V), m_APInt(BinOpC))))
1663 return nullptr;
1664
1666 .binaryOp(BO->getOpcode(), *BinOpC);
1667 if (R == *C) {
1669 return BO;
1670 }
1671 return nullptr;
1672}
1673
1674/// Visit a SelectInst that has an ICmpInst as its first operand.
1676 ICmpInst *ICI) {
1677 if (Instruction *NewSel = foldSelectValueEquivalence(SI, *ICI))
1678 return NewSel;
1679
1680 if (Instruction *NewSPF = canonicalizeSPF(SI, *ICI, *this))
1681 return NewSPF;
1682
1683 if (Value *V = foldSelectInstWithICmpConst(SI, ICI, Builder))
1684 return replaceInstUsesWith(SI, V);
1685
1686 if (Value *V = canonicalizeClampLike(SI, *ICI, Builder))
1687 return replaceInstUsesWith(SI, V);
1688
1689 if (Instruction *NewSel =
1690 tryToReuseConstantFromSelectInComparison(SI, *ICI, *this))
1691 return NewSel;
1692
1693 if (Value *V = foldSelectICmpAnd(SI, ICI, Builder))
1694 return replaceInstUsesWith(SI, V);
1695
1696 // NOTE: if we wanted to, this is where to detect integer MIN/MAX
1697 bool Changed = false;
1698 Value *TrueVal = SI.getTrueValue();
1699 Value *FalseVal = SI.getFalseValue();
1700 ICmpInst::Predicate Pred = ICI->getPredicate();
1701 Value *CmpLHS = ICI->getOperand(0);
1702 Value *CmpRHS = ICI->getOperand(1);
1703 if (CmpRHS != CmpLHS && isa<Constant>(CmpRHS) && !isa<Constant>(CmpLHS)) {
1704 if (CmpLHS == TrueVal && Pred == ICmpInst::ICMP_EQ) {
1705 // Transform (X == C) ? X : Y -> (X == C) ? C : Y
1706 SI.setOperand(1, CmpRHS);
1707 Changed = true;
1708 } else if (CmpLHS == FalseVal && Pred == ICmpInst::ICMP_NE) {
1709 // Transform (X != C) ? Y : X -> (X != C) ? Y : C
1710 SI.setOperand(2, CmpRHS);
1711 Changed = true;
1712 }
1713 }
1714
1715 // Canonicalize a signbit condition to use zero constant by swapping:
1716 // (CmpLHS > -1) ? TV : FV --> (CmpLHS < 0) ? FV : TV
1717 // To avoid conflicts (infinite loops) with other canonicalizations, this is
1718 // not applied with any constant select arm.
1719 if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes()) &&
1720 !match(TrueVal, m_Constant()) && !match(FalseVal, m_Constant()) &&
1721 ICI->hasOneUse()) {
1724 Value *IsNeg = Builder.CreateIsNeg(CmpLHS, ICI->getName());
1725 replaceOperand(SI, 0, IsNeg);
1726 SI.swapValues();
1727 SI.swapProfMetadata();
1728 return &SI;
1729 }
1730
1731 // FIXME: This code is nearly duplicated in InstSimplify. Using/refactoring
1732 // decomposeBitTestICmp() might help.
1733 if (TrueVal->getType()->isIntOrIntVectorTy()) {
1734 unsigned BitWidth =
1735 DL.getTypeSizeInBits(TrueVal->getType()->getScalarType());
1736 APInt MinSignedValue = APInt::getSignedMinValue(BitWidth);
1737 Value *X;
1738 const APInt *Y, *C;
1739 bool TrueWhenUnset;
1740 bool IsBitTest = false;
1741 if (ICmpInst::isEquality(Pred) &&
1742 match(CmpLHS, m_And(m_Value(X), m_Power2(Y))) &&
1743 match(CmpRHS, m_Zero())) {
1744 IsBitTest = true;
1745 TrueWhenUnset = Pred == ICmpInst::ICMP_EQ;
1746 } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) {
1747 X = CmpLHS;
1748 Y = &MinSignedValue;
1749 IsBitTest = true;
1750 TrueWhenUnset = false;
1751 } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) {
1752 X = CmpLHS;
1753 Y = &MinSignedValue;
1754 IsBitTest = true;
1755 TrueWhenUnset = true;
1756 }
1757 if (IsBitTest) {
1758 Value *V = nullptr;
1759 // (X & Y) == 0 ? X : X ^ Y --> X & ~Y
1760 if (TrueWhenUnset && TrueVal == X &&
1761 match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1762 V = Builder.CreateAnd(X, ~(*Y));
1763 // (X & Y) != 0 ? X ^ Y : X --> X & ~Y
1764 else if (!TrueWhenUnset && FalseVal == X &&
1765 match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1766 V = Builder.CreateAnd(X, ~(*Y));
1767 // (X & Y) == 0 ? X ^ Y : X --> X | Y
1768 else if (TrueWhenUnset && FalseVal == X &&
1769 match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1770 V = Builder.CreateOr(X, *Y);
1771 // (X & Y) != 0 ? X : X ^ Y --> X | Y
1772 else if (!TrueWhenUnset && TrueVal == X &&
1773 match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1774 V = Builder.CreateOr(X, *Y);
1775
1776 if (V)
1777 return replaceInstUsesWith(SI, V);
1778 }
1779 }
1780
1781 if (Instruction *V =
1782 foldSelectICmpAndAnd(SI.getType(), ICI, TrueVal, FalseVal, Builder))
1783 return V;
1784
1785 if (Value *V = foldSelectICmpAndZeroShl(ICI, TrueVal, FalseVal, Builder))
1786 return replaceInstUsesWith(SI, V);
1787
1788 if (Instruction *V = foldSelectCtlzToCttz(ICI, TrueVal, FalseVal, Builder))
1789 return V;
1790
1791 if (Instruction *V = foldSelectZeroOrOnes(ICI, TrueVal, FalseVal, Builder))
1792 return V;
1793
1794 if (Value *V = foldSelectICmpAndBinOp(ICI, TrueVal, FalseVal, Builder))
1795 return replaceInstUsesWith(SI, V);
1796
1797 if (Value *V = foldSelectICmpLshrAshr(ICI, TrueVal, FalseVal, Builder))
1798 return replaceInstUsesWith(SI, V);
1799
1800 if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
1801 return replaceInstUsesWith(SI, V);
1802
1803 if (Value *V = canonicalizeSaturatedSubtract(ICI, TrueVal, FalseVal, Builder))
1804 return replaceInstUsesWith(SI, V);
1805
1806 if (Value *V = canonicalizeSaturatedAdd(ICI, TrueVal, FalseVal, Builder))
1807 return replaceInstUsesWith(SI, V);
1808
1809 if (Value *V = foldAbsDiff(ICI, TrueVal, FalseVal, Builder))
1810 return replaceInstUsesWith(SI, V);
1811
1812 return Changed ? &SI : nullptr;
1813}
1814
1815/// SI is a select whose condition is a PHI node (but the two may be in
1816/// different blocks). See if the true/false values (V) are live in all of the
1817/// predecessor blocks of the PHI. For example, cases like this can't be mapped:
1818///
1819/// X = phi [ C1, BB1], [C2, BB2]
1820/// Y = add
1821/// Z = select X, Y, 0
1822///
1823/// because Y is not live in BB1/BB2.
1824static bool canSelectOperandBeMappingIntoPredBlock(const Value *V,
1825 const SelectInst &SI) {
1826 // If the value is a non-instruction value like a constant or argument, it
1827 // can always be mapped.
1828 const Instruction *I = dyn_cast<Instruction>(V);
1829 if (!I) return true;
1830
1831 // If V is a PHI node defined in the same block as the condition PHI, we can
1832 // map the arguments.
1833 const PHINode *CondPHI = cast<PHINode>(SI.getCondition());
1834
1835 if (const PHINode *VP = dyn_cast<PHINode>(I))
1836 if (VP->getParent() == CondPHI->getParent())
1837 return true;
1838
1839 // Otherwise, if the PHI and select are defined in the same block and if V is
1840 // defined in a different block, then we can transform it.
1841 if (SI.getParent() == CondPHI->getParent() &&
1842 I->getParent() != CondPHI->getParent())
1843 return true;
1844
1845 // Otherwise we have a 'hard' case and we can't tell without doing more
1846 // detailed dominator based analysis, punt.
1847 return false;
1848}
1849
1850/// We have an SPF (e.g. a min or max) of an SPF of the form:
1851/// SPF2(SPF1(A, B), C)
1854 Value *B, Instruction &Outer,
1856 Value *C) {
1857 if (Outer.getType() != Inner->getType())
1858 return nullptr;
1859
1860 if (C == A || C == B) {
1861 // MAX(MAX(A, B), B) -> MAX(A, B)
1862 // MIN(MIN(a, b), a) -> MIN(a, b)
1863 // TODO: This could be done in instsimplify.
1864 if (SPF1 == SPF2 && SelectPatternResult::isMinOrMax(SPF1))
1865 return replaceInstUsesWith(Outer, Inner);
1866 }
1867
1868 return nullptr;
1869}
1870
1871/// Turn select C, (X + Y), (X - Y) --> (X + (select C, Y, (-Y))).
1872/// This is even legal for FP.
1873static Instruction *foldAddSubSelect(SelectInst &SI,
1874 InstCombiner::BuilderTy &Builder) {
1875 Value *CondVal = SI.getCondition();
1876 Value *TrueVal = SI.getTrueValue();
1877 Value *FalseVal = SI.getFalseValue();
1878 auto *TI = dyn_cast<Instruction>(TrueVal);
1879 auto *FI = dyn_cast<Instruction>(FalseVal);
1880 if (!TI || !FI || !TI->hasOneUse() || !FI->hasOneUse())
1881 return nullptr;
1882
1883 Instruction *AddOp = nullptr, *SubOp = nullptr;
1884 if ((TI->getOpcode() == Instruction::Sub &&
1885 FI->getOpcode() == Instruction::Add) ||
1886 (TI->getOpcode() == Instruction::FSub &&
1887 FI->getOpcode() == Instruction::FAdd)) {
1888 AddOp = FI;
1889 SubOp = TI;
1890 } else if ((FI->getOpcode() == Instruction::Sub &&
1891 TI->getOpcode() == Instruction::Add) ||
1892 (FI->getOpcode() == Instruction::FSub &&
1893 TI->getOpcode() == Instruction::FAdd)) {
1894 AddOp = TI;
1895 SubOp = FI;
1896 }
1897
1898 if (AddOp) {
1899 Value *OtherAddOp = nullptr;
1900 if (SubOp->getOperand(0) == AddOp->getOperand(0)) {
1901 OtherAddOp = AddOp->getOperand(1);
1902 } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) {
1903 OtherAddOp = AddOp->getOperand(0);
1904 }
1905
1906 if (OtherAddOp) {
1907 // So at this point we know we have (Y -> OtherAddOp):
1908 // select C, (add X, Y), (sub X, Z)
1909 Value *NegVal; // Compute -Z
1910 if (SI.getType()->isFPOrFPVectorTy()) {
1911 NegVal = Builder.CreateFNeg(SubOp->getOperand(1));
1912 if (Instruction *NegInst = dyn_cast<Instruction>(NegVal)) {
1914 Flags &= SubOp->getFastMathFlags();
1915 NegInst->setFastMathFlags(Flags);
1916 }
1917 } else {
1918 NegVal = Builder.CreateNeg(SubOp->getOperand(1));
1919 }
1920
1921 Value *NewTrueOp = OtherAddOp;
1922 Value *NewFalseOp = NegVal;
1923 if (AddOp != TI)
1924 std::swap(NewTrueOp, NewFalseOp);
1925 Value *NewSel = Builder.CreateSelect(CondVal, NewTrueOp, NewFalseOp,
1926 SI.getName() + ".p", &SI);
1927
1928 if (SI.getType()->isFPOrFPVectorTy()) {
1929 Instruction *RI =
1930 BinaryOperator::CreateFAdd(SubOp->getOperand(0), NewSel);
1931
1933 Flags &= SubOp->getFastMathFlags();
1934 RI->setFastMathFlags(Flags);
1935 return RI;
1936 } else
1937 return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel);
1938 }
1939 }
1940 return nullptr;
1941}
1942
1943/// Turn X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
1944/// And X - Y overflows ? 0 : X - Y -> usub_sat X, Y
1945/// Along with a number of patterns similar to:
1946/// X + Y overflows ? (X < 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1947/// X - Y overflows ? (X > 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1948static Instruction *
1949foldOverflowingAddSubSelect(SelectInst &SI, InstCombiner::BuilderTy &Builder) {
1950 Value *CondVal = SI.getCondition();
1951 Value *TrueVal = SI.getTrueValue();
1952 Value *FalseVal = SI.getFalseValue();
1953
1954 WithOverflowInst *II;
1955 if (!match(CondVal, m_ExtractValue<1>(m_WithOverflowInst(II))) ||
1956 !match(FalseVal, m_ExtractValue<0>(m_Specific(II))))
1957 return nullptr;
1958
1959 Value *X = II->getLHS();
1960 Value *Y = II->getRHS();
1961
1962 auto IsSignedSaturateLimit = [&](Value *Limit, bool IsAdd) {
1963 Type *Ty = Limit->getType();
1964
1966 Value *TrueVal, *FalseVal, *Op;
1967 const APInt *C;
1968 if (!match(Limit, m_Select(m_ICmp(Pred, m_Value(Op), m_APInt(C)),
1969 m_Value(TrueVal), m_Value(FalseVal))))
1970 return false;
1971
1972 auto IsZeroOrOne = [](const APInt &C) { return C.isZero() || C.isOne(); };
1973 auto IsMinMax = [&](Value *Min, Value *Max) {
1976 return match(Min, m_SpecificInt(MinVal)) &&
1977 match(Max, m_SpecificInt(MaxVal));
1978 };
1979
1980 if (Op != X && Op != Y)
1981 return false;
1982
1983 if (IsAdd) {
1984 // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1985 // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1986 // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1987 // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1988 if (Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
1989 IsMinMax(TrueVal, FalseVal))
1990 return true;
1991 // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1992 // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1993 // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1994 // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1995 if (Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
1996 IsMinMax(FalseVal, TrueVal))
1997 return true;
1998 } else {
1999 // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2000 // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2001 if (Op == X && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C + 1) &&
2002 IsMinMax(TrueVal, FalseVal))
2003 return true;
2004 // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2005 // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2006 if (Op == X && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 2) &&
2007 IsMinMax(FalseVal, TrueVal))
2008 return true;
2009 // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2010 // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2011 if (Op == Y && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
2012 IsMinMax(FalseVal, TrueVal))
2013 return true;
2014 // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2015 // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2016 if (Op == Y && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
2017 IsMinMax(TrueVal, FalseVal))
2018 return true;
2019 }
2020
2021 return false;
2022 };
2023
2024 Intrinsic::ID NewIntrinsicID;
2025 if (II->getIntrinsicID() == Intrinsic::uadd_with_overflow &&
2026 match(TrueVal, m_AllOnes()))
2027 // X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
2028 NewIntrinsicID = Intrinsic::uadd_sat;
2029 else if (II->getIntrinsicID() == Intrinsic::usub_with_overflow &&
2030 match(TrueVal, m_Zero()))
2031 // X - Y overflows ? 0 : X - Y -> usub_sat X, Y
2032 NewIntrinsicID = Intrinsic::usub_sat;
2033 else if (II->getIntrinsicID() == Intrinsic::sadd_with_overflow &&
2034 IsSignedSaturateLimit(TrueVal, /*IsAdd=*/true))
2035 // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2036 // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2037 // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
2038 // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
2039 // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2040 // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
2041 // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
2042 // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
2043 NewIntrinsicID = Intrinsic::sadd_sat;
2044 else if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow &&
2045 IsSignedSaturateLimit(TrueVal, /*IsAdd=*/false))
2046 // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2047 // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2048 // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2049 // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2050 // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2051 // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
2052 // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2053 // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
2054 NewIntrinsicID = Intrinsic::ssub_sat;
2055 else
2056 return nullptr;
2057
2058 Function *F =
2059 Intrinsic::getDeclaration(SI.getModule(), NewIntrinsicID, SI.getType());
2060 return CallInst::Create(F, {X, Y});
2061}
2062
2064 Constant *C;
2065 if (!match(Sel.getTrueValue(), m_Constant(C)) &&
2066 !match(Sel.getFalseValue(), m_Constant(C)))
2067 return nullptr;
2068
2069 Instruction *ExtInst;
2070 if (!match(Sel.getTrueValue(), m_Instruction(ExtInst)) &&
2071 !match(Sel.getFalseValue(), m_Instruction(ExtInst)))
2072 return nullptr;
2073
2074 auto ExtOpcode = ExtInst->getOpcode();
2075 if (ExtOpcode != Instruction::ZExt && ExtOpcode != Instruction::SExt)
2076 return nullptr;
2077
2078 // If we are extending from a boolean type or if we can create a select that
2079 // has the same size operands as its condition, try to narrow the select.
2080 Value *X = ExtInst->getOperand(0);
2081 Type *SmallType = X->getType();
2082 Value *Cond = Sel.getCondition();
2083 auto *Cmp = dyn_cast<CmpInst>(Cond);
2084 if (!SmallType->isIntOrIntVectorTy(1) &&
2085 (!Cmp || Cmp->getOperand(0)->getType() != SmallType))
2086 return nullptr;
2087
2088 // If the constant is the same after truncation to the smaller type and
2089 // extension to the original type, we can narrow the select.
2090 Type *SelType = Sel.getType();
2091 Constant *TruncC = getLosslessTrunc(C, SmallType, ExtOpcode);
2092 if (TruncC && ExtInst->hasOneUse()) {
2093 Value *TruncCVal = cast<Value>(TruncC);
2094 if (ExtInst == Sel.getFalseValue())
2095 std::swap(X, TruncCVal);
2096
2097 // select Cond, (ext X), C --> ext(select Cond, X, C')
2098 // select Cond, C, (ext X) --> ext(select Cond, C', X)
2099 Value *NewSel = Builder.CreateSelect(Cond, X, TruncCVal, "narrow", &Sel);
2100 return CastInst::Create(Instruction::CastOps(ExtOpcode), NewSel, SelType);
2101 }
2102
2103 return nullptr;
2104}
2105
2106/// Try to transform a vector select with a constant condition vector into a
2107/// shuffle for easier combining with other shuffles and insert/extract.
2108static Instruction *canonicalizeSelectToShuffle(SelectInst &SI) {
2109 Value *CondVal = SI.getCondition();
2110 Constant *CondC;
2111 auto *CondValTy = dyn_cast<FixedVectorType>(CondVal->getType());
2112 if (!CondValTy || !match(CondVal, m_Constant(CondC)))
2113 return nullptr;
2114
2115 unsigned NumElts = CondValTy->getNumElements();
2117 Mask.reserve(NumElts);
2118 for (unsigned i = 0; i != NumElts; ++i) {
2119 Constant *Elt = CondC->getAggregateElement(i);
2120 if (!Elt)
2121 return nullptr;
2122
2123 if (Elt->isOneValue()) {
2124 // If the select condition element is true, choose from the 1st vector.
2125 Mask.push_back(i);
2126 } else if (Elt->isNullValue()) {
2127 // If the select condition element is false, choose from the 2nd vector.
2128 Mask.push_back(i + NumElts);
2129 } else if (isa<UndefValue>(Elt)) {
2130 // Undef in a select condition (choose one of the operands) does not mean
2131 // the same thing as undef in a shuffle mask (any value is acceptable), so
2132 // give up.
2133 return nullptr;
2134 } else {
2135 // Bail out on a constant expression.
2136 return nullptr;
2137 }
2138 }
2139
2140 return new ShuffleVectorInst(SI.getTrueValue(), SI.getFalseValue(), Mask);
2141}
2142
2143/// If we have a select of vectors with a scalar condition, try to convert that
2144/// to a vector select by splatting the condition. A splat may get folded with
2145/// other operations in IR and having all operands of a select be vector types
2146/// is likely better for vector codegen.
2147static Instruction *canonicalizeScalarSelectOfVecs(SelectInst &Sel,
2148 InstCombinerImpl &IC) {
2149 auto *Ty = dyn_cast<VectorType>(Sel.getType());
2150 if (!Ty)
2151 return nullptr;
2152
2153 // We can replace a single-use extract with constant index.
2154 Value *Cond = Sel.getCondition();
2156 return nullptr;
2157
2158 // select (extelt V, Index), T, F --> select (splat V, Index), T, F
2159 // Splatting the extracted condition reduces code (we could directly create a
2160 // splat shuffle of the source vector to eliminate the intermediate step).
2161 return IC.replaceOperand(
2162 Sel, 0, IC.Builder.CreateVectorSplat(Ty->getElementCount(), Cond));
2163}
2164
2165/// Reuse bitcasted operands between a compare and select:
2166/// select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2167/// bitcast (select (cmp (bitcast C), (bitcast D)), (bitcast C), (bitcast D))
2168static Instruction *foldSelectCmpBitcasts(SelectInst &Sel,
2169 InstCombiner::BuilderTy &Builder) {
2170 Value *Cond = Sel.getCondition();
2171 Value *TVal = Sel.getTrueValue();
2172 Value *FVal = Sel.getFalseValue();
2173
2174 CmpInst::Predicate Pred;
2175 Value *A, *B;
2176 if (!match(Cond, m_Cmp(Pred, m_Value(A), m_Value(B))))
2177 return nullptr;
2178
2179 // The select condition is a compare instruction. If the select's true/false
2180 // values are already the same as the compare operands, there's nothing to do.
2181 if (TVal == A || TVal == B || FVal == A || FVal == B)
2182 return nullptr;
2183
2184 Value *C, *D;
2185 if (!match(A, m_BitCast(m_Value(C))) || !match(B, m_BitCast(m_Value(D))))
2186 return nullptr;
2187
2188 // select (cmp (bitcast C), (bitcast D)), (bitcast TSrc), (bitcast FSrc)
2189 Value *TSrc, *FSrc;
2190 if (!match(TVal, m_BitCast(m_Value(TSrc))) ||
2191 !match(FVal, m_BitCast(m_Value(FSrc))))
2192 return nullptr;
2193
2194 // If the select true/false values are *different bitcasts* of the same source
2195 // operands, make the select operands the same as the compare operands and
2196 // cast the result. This is the canonical select form for min/max.
2197 Value *NewSel;
2198 if (TSrc == C && FSrc == D) {
2199 // select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2200 // bitcast (select (cmp A, B), A, B)
2201 NewSel = Builder.CreateSelect(Cond, A, B, "", &Sel);
2202 } else if (TSrc == D && FSrc == C) {
2203 // select (cmp (bitcast C), (bitcast D)), (bitcast' D), (bitcast' C) -->
2204 // bitcast (select (cmp A, B), B, A)
2205 NewSel = Builder.CreateSelect(Cond, B, A, "", &Sel);
2206 } else {
2207 return nullptr;
2208 }
2209 return CastInst::CreateBitOrPointerCast(NewSel, Sel.getType());
2210}
2211
2212/// Try to eliminate select instructions that test the returned flag of cmpxchg
2213/// instructions.
2214///
2215/// If a select instruction tests the returned flag of a cmpxchg instruction and
2216/// selects between the returned value of the cmpxchg instruction its compare
2217/// operand, the result of the select will always be equal to its false value.
2218/// For example:
2219///
2220/// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2221/// %1 = extractvalue { i64, i1 } %0, 1
2222/// %2 = extractvalue { i64, i1 } %0, 0
2223/// %3 = select i1 %1, i64 %compare, i64 %2
2224/// ret i64 %3
2225///
2226/// The returned value of the cmpxchg instruction (%2) is the original value
2227/// located at %ptr prior to any update. If the cmpxchg operation succeeds, %2
2228/// must have been equal to %compare. Thus, the result of the select is always
2229/// equal to %2, and the code can be simplified to:
2230///
2231/// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2232/// %1 = extractvalue { i64, i1 } %0, 0
2233/// ret i64 %1
2234///
2235static Value *foldSelectCmpXchg(SelectInst &SI) {
2236 // A helper that determines if V is an extractvalue instruction whose
2237 // aggregate operand is a cmpxchg instruction and whose single index is equal
2238 // to I. If such conditions are true, the helper returns the cmpxchg
2239 // instruction; otherwise, a nullptr is returned.
2240 auto isExtractFromCmpXchg = [](Value *V, unsigned I) -> AtomicCmpXchgInst * {
2241 auto *Extract = dyn_cast<ExtractValueInst>(V);
2242 if (!Extract)
2243 return nullptr;
2244 if (Extract->getIndices()[0] != I)
2245 return nullptr;
2246 return dyn_cast<AtomicCmpXchgInst>(Extract->getAggregateOperand());
2247 };
2248
2249 // If the select has a single user, and this user is a select instruction that
2250 // we can simplify, skip the cmpxchg simplification for now.
2251 if (SI.hasOneUse())
2252 if (auto *Select = dyn_cast<SelectInst>(SI.user_back()))
2253 if (Select->getCondition() == SI.getCondition())
2254 if (Select->getFalseValue() == SI.getTrueValue() ||
2255 Select->getTrueValue() == SI.getFalseValue())
2256 return nullptr;
2257
2258 // Ensure the select condition is the returned flag of a cmpxchg instruction.
2259 auto *CmpXchg = isExtractFromCmpXchg(SI.getCondition(), 1);
2260 if (!CmpXchg)
2261 return nullptr;
2262
2263 // Check the true value case: The true value of the select is the returned
2264 // value of the same cmpxchg used by the condition, and the false value is the
2265 // cmpxchg instruction's compare operand.
2266 if (auto *X = isExtractFromCmpXchg(SI.getTrueValue(), 0))
2267 if (X == CmpXchg && X->getCompareOperand() == SI.getFalseValue())
2268 return SI.getFalseValue();
2269
2270 // Check the false value case: The false value of the select is the returned
2271 // value of the same cmpxchg used by the condition, and the true value is the
2272 // cmpxchg instruction's compare operand.
2273 if (auto *X = isExtractFromCmpXchg(SI.getFalseValue(), 0))
2274 if (X == CmpXchg && X->getCompareOperand() == SI.getTrueValue())
2275 return SI.getFalseValue();
2276
2277 return nullptr;
2278}
2279
2280/// Try to reduce a funnel/rotate pattern that includes a compare and select
2281/// into a funnel shift intrinsic. Example:
2282/// rotl32(a, b) --> (b == 0 ? a : ((a >> (32 - b)) | (a << b)))
2283/// --> call llvm.fshl.i32(a, a, b)
2284/// fshl32(a, b, c) --> (c == 0 ? a : ((b >> (32 - c)) | (a << c)))
2285/// --> call llvm.fshl.i32(a, b, c)
2286/// fshr32(a, b, c) --> (c == 0 ? b : ((a >> (32 - c)) | (b << c)))
2287/// --> call llvm.fshr.i32(a, b, c)
2288static Instruction *foldSelectFunnelShift(SelectInst &Sel,
2289 InstCombiner::BuilderTy &Builder) {
2290 // This must be a power-of-2 type for a bitmasking transform to be valid.
2291 unsigned Width = Sel.getType()->getScalarSizeInBits();
2292 if (!isPowerOf2_32(Width))
2293 return nullptr;
2294
2295 BinaryOperator *Or0, *Or1;
2296 if (!match(Sel.getFalseValue(), m_OneUse(m_Or(m_BinOp(Or0), m_BinOp(Or1)))))
2297 return nullptr;
2298
2299 Value *SV0, *SV1, *SA0, *SA1;
2300 if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(SV0),
2301 m_ZExtOrSelf(m_Value(SA0))))) ||
2303 m_ZExtOrSelf(m_Value(SA1))))) ||
2304 Or0->getOpcode() == Or1->getOpcode())
2305 return nullptr;
2306
2307 // Canonicalize to or(shl(SV0, SA0), lshr(SV1, SA1)).
2308 if (Or0->getOpcode() == BinaryOperator::LShr) {
2309 std::swap(Or0, Or1);
2310 std::swap(SV0, SV1);
2311 std::swap(SA0, SA1);
2312 }
2313 assert(Or0->getOpcode() == BinaryOperator::Shl &&
2314 Or1->getOpcode() == BinaryOperator::LShr &&
2315 "Illegal or(shift,shift) pair");
2316
2317 // Check the shift amounts to see if they are an opposite pair.
2318 Value *ShAmt;
2319 if (match(SA1, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA0)))))
2320 ShAmt = SA0;
2321 else if (match(SA0, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA1)))))
2322 ShAmt = SA1;
2323 else
2324 return nullptr;
2325
2326 // We should now have this pattern:
2327 // select ?, TVal, (or (shl SV0, SA0), (lshr SV1, SA1))
2328 // The false value of the select must be a funnel-shift of the true value:
2329 // IsFShl -> TVal must be SV0 else TVal must be SV1.
2330 bool IsFshl = (ShAmt == SA0);
2331 Value *TVal = Sel.getTrueValue();
2332 if ((IsFshl && TVal != SV0) || (!IsFshl && TVal != SV1))
2333 return nullptr;
2334
2335 // Finally, see if the select is filtering out a shift-by-zero.
2336 Value *Cond = Sel.getCondition();
2338 if (!match(Cond, m_OneUse(m_ICmp(Pred, m_Specific(ShAmt), m_ZeroInt()))) ||
2339 Pred != ICmpInst::ICMP_EQ)
2340 return nullptr;
2341
2342 // If this is not a rotate then the select was blocking poison from the
2343 // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.
2344 if (SV0 != SV1) {
2345 if (IsFshl && !llvm::isGuaranteedNotToBePoison(SV1))
2346 SV1 = Builder.CreateFreeze(SV1);
2347 else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(SV0))
2348 SV0 = Builder.CreateFreeze(SV0);
2349 }
2350
2351 // This is a funnel/rotate that avoids shift-by-bitwidth UB in a suboptimal way.
2352 // Convert to funnel shift intrinsic.
2353 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2355 ShAmt = Builder.CreateZExt(ShAmt, Sel.getType());
2356 return CallInst::Create(F, { SV0, SV1, ShAmt });
2357}
2358
2359static Instruction *foldSelectToCopysign(SelectInst &Sel,
2360 InstCombiner::BuilderTy &Builder) {
2361 Value *Cond = Sel.getCondition();
2362 Value *TVal = Sel.getTrueValue();
2363 Value *FVal = Sel.getFalseValue();
2364 Type *SelType = Sel.getType();
2365
2366 // Match select ?, TC, FC where the constants are equal but negated.
2367 // TODO: Generalize to handle a negated variable operand?
2368 const APFloat *TC, *FC;
2369 if (!match(TVal, m_APFloatAllowUndef(TC)) ||
2370 !match(FVal, m_APFloatAllowUndef(FC)) ||
2371 !abs(*TC).bitwiseIsEqual(abs(*FC)))
2372 return nullptr;
2373
2374 assert(TC != FC && "Expected equal select arms to simplify");
2375
2376 Value *X;
2377 const APInt *C;
2378 bool IsTrueIfSignSet;
2380 if (!match(Cond, m_OneUse(m_ICmp(Pred, m_BitCast(m_Value(X)), m_APInt(C)))) ||
2381 !InstCombiner::isSignBitCheck(Pred, *C, IsTrueIfSignSet) ||
2382 X->getType() != SelType)
2383 return nullptr;
2384
2385 // If needed, negate the value that will be the sign argument of the copysign:
2386 // (bitcast X) < 0 ? -TC : TC --> copysign(TC, X)
2387 // (bitcast X) < 0 ? TC : -TC --> copysign(TC, -X)
2388 // (bitcast X) >= 0 ? -TC : TC --> copysign(TC, -X)
2389 // (bitcast X) >= 0 ? TC : -TC --> copysign(TC, X)
2390 // Note: FMF from the select can not be propagated to the new instructions.
2391 if (IsTrueIfSignSet ^ TC->isNegative())
2392 X = Builder.CreateFNeg(X);
2393
2394 // Canonicalize the magnitude argument as the positive constant since we do
2395 // not care about its sign.
2396 Value *MagArg = ConstantFP::get(SelType, abs(*TC));
2397 Function *F = Intrinsic::getDeclaration(Sel.getModule(), Intrinsic::copysign,
2398 Sel.getType());
2399 return CallInst::Create(F, { MagArg, X });
2400}
2401
2403 if (!isa<VectorType>(Sel.getType()))
2404 return nullptr;
2405
2406 Value *Cond = Sel.getCondition();
2407 Value *TVal = Sel.getTrueValue();
2408 Value *FVal = Sel.getFalseValue();
2409 Value *C, *X, *Y;
2410
2411 if (match(Cond, m_VecReverse(m_Value(C)))) {
2412 auto createSelReverse = [&](Value *C, Value *X, Value *Y) {
2413 Value *V = Builder.CreateSelect(C, X, Y, Sel.getName(), &Sel);
2414 if (auto *I = dyn_cast<Instruction>(V))
2415 I->copyIRFlags(&Sel);
2416 Module *M = Sel.getModule();
2418 M, Intrinsic::experimental_vector_reverse, V->getType());
2419 return CallInst::Create(F, V);
2420 };
2421
2422 if (match(TVal, m_VecReverse(m_Value(X)))) {
2423 // select rev(C), rev(X), rev(Y) --> rev(select C, X, Y)
2424 if (match(FVal, m_VecReverse(m_Value(Y))) &&
2425 (Cond->hasOneUse() || TVal->hasOneUse() || FVal->hasOneUse()))
2426 return createSelReverse(C, X, Y);
2427
2428 // select rev(C), rev(X), FValSplat --> rev(select C, X, FValSplat)
2429 if ((Cond->hasOneUse() || TVal->hasOneUse()) && isSplatValue(FVal))
2430 return createSelReverse(C, X, FVal);
2431 }
2432 // select rev(C), TValSplat, rev(Y) --> rev(select C, TValSplat, Y)
2433 else if (isSplatValue(TVal) && match(FVal, m_VecReverse(m_Value(Y))) &&
2434 (Cond->hasOneUse() || FVal->hasOneUse()))
2435 return createSelReverse(C, TVal, Y);
2436 }
2437
2438 auto *VecTy = dyn_cast<FixedVectorType>(Sel.getType());
2439 if (!VecTy)
2440 return nullptr;
2441
2442 unsigned NumElts = VecTy->getNumElements();
2443 APInt UndefElts(NumElts, 0);
2444 APInt AllOnesEltMask(APInt::getAllOnes(NumElts));
2445 if (Value *V = SimplifyDemandedVectorElts(&Sel, AllOnesEltMask, UndefElts)) {
2446 if (V != &Sel)
2447 return replaceInstUsesWith(Sel, V);
2448 return &Sel;
2449 }
2450
2451 // A select of a "select shuffle" with a common operand can be rearranged
2452 // to select followed by "select shuffle". Because of poison, this only works
2453 // in the case of a shuffle with no undefined mask elements.
2455 if (match(TVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
2456 !is_contained(Mask, PoisonMaskElem) &&
2457 cast<ShuffleVectorInst>(TVal)->isSelect()) {
2458 if (X == FVal) {
2459 // select Cond, (shuf_sel X, Y), X --> shuf_sel X, (select Cond, Y, X)
2460 Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
2461 return new ShuffleVectorInst(X, NewSel, Mask);
2462 }
2463 if (Y == FVal) {
2464 // select Cond, (shuf_sel X, Y), Y --> shuf_sel (select Cond, X, Y), Y
2465 Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
2466 return new ShuffleVectorInst(NewSel, Y, Mask);
2467 }
2468 }
2469 if (match(FVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
2470 !is_contained(Mask, PoisonMaskElem) &&
2471 cast<ShuffleVectorInst>(FVal)->isSelect()) {
2472 if (X == TVal) {
2473 // select Cond, X, (shuf_sel X, Y) --> shuf_sel X, (select Cond, X, Y)
2474 Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
2475 return new ShuffleVectorInst(X, NewSel, Mask);
2476 }
2477 if (Y == TVal) {
2478 // select Cond, Y, (shuf_sel X, Y) --> shuf_sel (select Cond, Y, X), Y
2479 Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
2480 return new ShuffleVectorInst(NewSel, Y, Mask);
2481 }
2482 }
2483
2484 return nullptr;
2485}
2486
2487static Instruction *foldSelectToPhiImpl(SelectInst &Sel, BasicBlock *BB,
2488 const DominatorTree &DT,
2489 InstCombiner::BuilderTy &Builder) {
2490 // Find the block's immediate dominator that ends with a conditional branch
2491 // that matches select's condition (maybe inverted).
2492 auto *IDomNode = DT[BB]->getIDom();
2493 if (!IDomNode)
2494 return nullptr;
2495 BasicBlock *IDom = IDomNode->getBlock();
2496
2497 Value *Cond = Sel.getCondition();
2498 Value *IfTrue, *IfFalse;
2499 BasicBlock *TrueSucc, *FalseSucc;
2500 if (match(IDom->getTerminator(),
2501 m_Br(m_Specific(Cond), m_BasicBlock(TrueSucc),
2502 m_BasicBlock(FalseSucc)))) {
2503 IfTrue = Sel.getTrueValue();
2504 IfFalse = Sel.getFalseValue();
2505 } else if (match(IDom->getTerminator(),
2506 m_Br(m_Not(m_Specific(Cond)), m_BasicBlock(TrueSucc),
2507 m_BasicBlock(FalseSucc)))) {
2508 IfTrue = Sel.getFalseValue();
2509 IfFalse = Sel.getTrueValue();
2510 } else
2511 return nullptr;
2512
2513 // Make sure the branches are actually different.
2514 if (TrueSucc == FalseSucc)
2515 return nullptr;
2516
2517 // We want to replace select %cond, %a, %b with a phi that takes value %a
2518 // for all incoming edges that are dominated by condition `%cond == true`,
2519 // and value %b for edges dominated by condition `%cond == false`. If %a
2520 // or %b are also phis from the same basic block, we can go further and take
2521 // their incoming values from the corresponding blocks.
2522 BasicBlockEdge TrueEdge(IDom, TrueSucc);
2523 BasicBlockEdge FalseEdge(IDom, FalseSucc);
2525 for (auto *Pred : predecessors(BB)) {
2526 // Check implication.
2527 BasicBlockEdge Incoming(Pred, BB);
2528 if (DT.dominates(TrueEdge, Incoming))
2529 Inputs[Pred] = IfTrue->DoPHITranslation(BB, Pred);
2530 else if (DT.dominates(FalseEdge, Incoming))
2531 Inputs[Pred] = IfFalse->DoPHITranslation(BB, Pred);
2532 else
2533 return nullptr;
2534 // Check availability.
2535 if (auto *Insn = dyn_cast<Instruction>(Inputs[Pred]))
2536 if (!DT.dominates(Insn, Pred->getTerminator()))
2537 return nullptr;
2538 }
2539
2540 Builder.SetInsertPoint(BB, BB->begin());
2541 auto *PN = Builder.CreatePHI(Sel.getType(), Inputs.size());
2542 for (auto *Pred : predecessors(BB))
2543 PN->addIncoming(Inputs[Pred], Pred);
2544 PN->takeName(&Sel);
2545 return PN;
2546}
2547
2548static Instruction *foldSelectToPhi(SelectInst &Sel, const DominatorTree &DT,
2549 InstCombiner::BuilderTy &Builder) {
2550 // Try to replace this select with Phi in one of these blocks.
2551 SmallSetVector<BasicBlock *, 4> CandidateBlocks;
2552 CandidateBlocks.insert(Sel.getParent());
2553 for (Value *V : Sel.operands())
2554 if (auto *I = dyn_cast<Instruction>(V))
2555 CandidateBlocks.insert(I->getParent());
2556
2557 for (BasicBlock *BB : CandidateBlocks)
2558 if (auto *PN = foldSelectToPhiImpl(Sel, BB, DT, Builder))
2559 return PN;
2560 return nullptr;
2561}
2562
2563/// Tries to reduce a pattern that arises when calculating the remainder of the
2564/// Euclidean division. When the divisor is a power of two and is guaranteed not
2565/// to be negative, a signed remainder can be folded with a bitwise and.
2566///
2567/// (x % n) < 0 ? (x % n) + n : (x % n)
2568/// -> x & (n - 1)
2569static Instruction *foldSelectWithSRem(SelectInst &SI, InstCombinerImpl &IC,
2570 IRBuilderBase &Builder) {
2571 Value *CondVal = SI.getCondition();
2572 Value *TrueVal = SI.getTrueValue();
2573 Value *FalseVal = SI.getFalseValue();
2574
2576 Value *Op, *RemRes, *Remainder;
2577 const APInt *C;
2578 bool TrueIfSigned = false;
2579
2580 if (!(match(CondVal, m_ICmp(Pred, m_Value(RemRes), m_APInt(C))) &&
2581 IC.isSignBitCheck(Pred, *C, TrueIfSigned)))
2582 return nullptr;
2583
2584 // If the sign bit is not set, we have a SGE/SGT comparison, and the operands
2585 // of the select are inverted.
2586 if (!TrueIfSigned)
2587 std::swap(TrueVal, FalseVal);
2588
2589 auto FoldToBitwiseAnd = [&](Value *Remainder) -> Instruction * {
2590 Value *Add = Builder.CreateAdd(
2591 Remainder, Constant::getAllOnesValue(RemRes->getType()));
2592 return BinaryOperator::CreateAnd(Op, Add);
2593 };
2594
2595 // Match the general case:
2596 // %rem = srem i32 %x, %n
2597 // %cnd = icmp slt i32 %rem, 0
2598 // %add = add i32 %rem, %n
2599 // %sel = select i1 %cnd, i32 %add, i32 %rem
2600 if (match(TrueVal, m_Add(m_Value(RemRes), m_Value(Remainder))) &&
2601 match(RemRes, m_SRem(m_Value(Op), m_Specific(Remainder))) &&
2602 IC.isKnownToBeAPowerOfTwo(Remainder, /*OrZero*/ true) &&
2603 FalseVal == RemRes)
2604 return FoldToBitwiseAnd(Remainder);
2605
2606 // Match the case where the one arm has been replaced by constant 1:
2607 // %rem = srem i32 %n, 2
2608 // %cnd = icmp slt i32 %rem, 0
2609 // %sel = select i1 %cnd, i32 1, i32 %rem
2610 if (match(TrueVal, m_One()) &&
2611 match(RemRes, m_SRem(m_Value(Op), m_SpecificInt(2))) &&
2612 FalseVal == RemRes)
2613 return FoldToBitwiseAnd(ConstantInt::get(RemRes->getType(), 2));
2614
2615 return nullptr;
2616}
2617
2618static Value *foldSelectWithFrozenICmp(SelectInst &Sel, InstCombiner::BuilderTy &Builder) {
2619 FreezeInst *FI = dyn_cast<FreezeInst>(Sel.getCondition());
2620 if (!FI)
2621 return nullptr;
2622
2623 Value *Cond = FI->getOperand(0);
2624 Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
2625
2626 // select (freeze(x == y)), x, y --> y
2627 // select (freeze(x != y)), x, y --> x
2628 // The freeze should be only used by this select. Otherwise, remaining uses of
2629 // the freeze can observe a contradictory value.
2630 // c = freeze(x == y) ; Let's assume that y = poison & x = 42; c is 0 or 1
2631 // a = select c, x, y ;
2632 // f(a, c) ; f(poison, 1) cannot happen, but if a is folded
2633 // ; to y, this can happen.
2634 CmpInst::Predicate Pred;
2635 if (FI->hasOneUse() &&
2636 match(Cond, m_c_ICmp(Pred, m_Specific(TrueVal), m_Specific(FalseVal))) &&
2637 (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)) {
2638 return Pred == ICmpInst::ICMP_EQ ? FalseVal : TrueVal;
2639 }
2640
2641 return nullptr;
2642}
2643
2644Instruction *InstCombinerImpl::foldAndOrOfSelectUsingImpliedCond(Value *Op,
2645 SelectInst &SI,
2646 bool IsAnd) {
2647 Value *CondVal = SI.getCondition();
2648 Value *A = SI.getTrueValue();
2649 Value *B = SI.getFalseValue();
2650
2651 assert(Op->getType()->isIntOrIntVectorTy(1) &&
2652 "Op must be either i1 or vector of i1.");
2653
2654 std::optional<bool> Res = isImpliedCondition(Op, CondVal, DL, IsAnd);
2655 if (!Res)
2656 return nullptr;
2657
2658 Value *Zero = Constant::getNullValue(A->getType());
2659 Value *One = Constant::getAllOnesValue(A->getType());
2660
2661 if (*Res == true) {
2662 if (IsAnd)
2663 // select op, (select cond, A, B), false => select op, A, false
2664 // and op, (select cond, A, B) => select op, A, false
2665 // if op = true implies condval = true.
2666 return SelectInst::Create(Op, A, Zero);
2667 else
2668 // select op, true, (select cond, A, B) => select op, true, A
2669 // or op, (select cond, A, B) => select op, true, A
2670 // if op = false implies condval = true.
2671 return SelectInst::Create(Op, One, A);
2672 } else {
2673 if (IsAnd)
2674 // select op, (select cond, A, B), false => select op, B, false
2675 // and op, (select cond, A, B) => select op, B, false
2676 // if op = true implies condval = false.
2677 return SelectInst::Create(Op, B, Zero);
2678 else
2679 // select op, true, (select cond, A, B) => select op, true, B
2680 // or op, (select cond, A, B) => select op, true, B
2681 // if op = false implies condval = false.
2682 return SelectInst::Create(Op, One, B);
2683 }
2684}
2685
2686// Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need
2687// fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work.
2688static Instruction *foldSelectWithFCmpToFabs(SelectInst &SI,
2689 InstCombinerImpl &IC) {
2690 Value *CondVal = SI.getCondition();
2691
2692 bool ChangedFMF = false;
2693 for (bool Swap : {false, true}) {
2694 Value *TrueVal = SI.getTrueValue();
2695 Value *X = SI.getFalseValue();
2696 CmpInst::Predicate Pred;
2697
2698 if (Swap)
2699 std::swap(TrueVal, X);
2700
2701 if (!match(CondVal, m_FCmp(Pred, m_Specific(X), m_AnyZeroFP())))
2702 continue;
2703
2704 // fold (X <= +/-0.0) ? (0.0 - X) : X to fabs(X), when 'Swap' is false
2705 // fold (X > +/-0.0) ? X : (0.0 - X) to fabs(X), when 'Swap' is true
2706 if (match(TrueVal, m_FSub(m_PosZeroFP(), m_Specific(X)))) {
2707 if (!Swap && (Pred == FCmpInst::FCMP_OLE || Pred == FCmpInst::FCMP_ULE)) {
2708 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2709 return IC.replaceInstUsesWith(SI, Fabs);
2710 }
2711 if (Swap && (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_UGT)) {
2712 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2713 return IC.replaceInstUsesWith(SI, Fabs);
2714 }
2715 }
2716
2717 if (!match(TrueVal, m_FNeg(m_Specific(X))))
2718 return nullptr;
2719
2720 // Forward-propagate nnan and ninf from the fneg to the select.
2721 // If all inputs are not those values, then the select is not either.
2722 // Note: nsz is defined differently, so it may not be correct to propagate.
2723 FastMathFlags FMF = cast<FPMathOperator>(TrueVal)->getFastMathFlags();
2724 if (FMF.noNaNs() && !SI.hasNoNaNs()) {
2725 SI.setHasNoNaNs(true);
2726 ChangedFMF = true;
2727 }
2728 if (FMF.noInfs() && !SI.hasNoInfs()) {
2729 SI.setHasNoInfs(true);
2730 ChangedFMF = true;
2731 }
2732
2733 // With nsz, when 'Swap' is false:
2734 // fold (X < +/-0.0) ? -X : X or (X <= +/-0.0) ? -X : X to fabs(X)
2735 // fold (X > +/-0.0) ? -X : X or (X >= +/-0.0) ? -X : X to -fabs(x)
2736 // when 'Swap' is true:
2737 // fold (X > +/-0.0) ? X : -X or (X >= +/-0.0) ? X : -X to fabs(X)
2738 // fold (X < +/-0.0) ? X : -X or (X <= +/-0.0) ? X : -X to -fabs(X)
2739 //
2740 // Note: We require "nnan" for this fold because fcmp ignores the signbit
2741 // of NAN, but IEEE-754 specifies the signbit of NAN values with
2742 // fneg/fabs operations.
2743 if (!SI.hasNoSignedZeros() || !SI.hasNoNaNs())
2744 return nullptr;
2745
2746 if (Swap)
2747 Pred = FCmpInst::getSwappedPredicate(Pred);
2748
2749 bool IsLTOrLE = Pred == FCmpInst::FCMP_OLT || Pred == FCmpInst::FCMP_OLE ||
2750 Pred == FCmpInst::FCMP_ULT || Pred == FCmpInst::FCMP_ULE;
2751 bool IsGTOrGE = Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_OGE ||
2752 Pred == FCmpInst::FCMP_UGT || Pred == FCmpInst::FCMP_UGE;
2753
2754 if (IsLTOrLE) {
2755 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2756 return IC.replaceInstUsesWith(SI, Fabs);
2757 }
2758 if (IsGTOrGE) {
2759 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2760 Instruction *NewFNeg = UnaryOperator::CreateFNeg(Fabs);
2761 NewFNeg->setFastMathFlags(SI.getFastMathFlags());
2762 return NewFNeg;
2763 }
2764 }
2765
2766 return ChangedFMF ? &SI : nullptr;
2767}
2768
2769// Match the following IR pattern:
2770// %x.lowbits = and i8 %x, %lowbitmask
2771// %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 0
2772// %x.biased = add i8 %x, %bias
2773// %x.biased.highbits = and i8 %x.biased, %highbitmask
2774// %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
2775// Define:
2776// %alignment = add i8 %lowbitmask, 1
2777// Iff 1. an %alignment is a power-of-two (aka, %lowbitmask is a low bit mask)
2778// and 2. %bias is equal to either %lowbitmask or %alignment,
2779// and 3. %highbitmask is equal to ~%lowbitmask (aka, to -%alignment)
2780// then this pattern can be transformed into:
2781// %x.offset = add i8 %x, %lowbitmask
2782// %x.roundedup = and i8 %x.offset, %highbitmask
2783static Value *
2784foldRoundUpIntegerWithPow2Alignment(SelectInst &SI,
2785 InstCombiner::BuilderTy &Builder) {
2786 Value *Cond = SI.getCondition();
2787 Value *X = SI.getTrueValue();
2788 Value *XBiasedHighBits = SI.getFalseValue();
2789
2791 Value *XLowBits;
2792 if (!match(Cond, m_ICmp(Pred, m_Value(XLowBits), m_ZeroInt())) ||
2793 !ICmpInst::isEquality(Pred))
2794 return nullptr;
2795
2796 if (Pred == ICmpInst::Predicate::ICMP_NE)
2797 std::swap(X, XBiasedHighBits);
2798
2799 // FIXME: we could support non non-splats here.
2800
2801 const APInt *LowBitMaskCst;
2802 if (!match(XLowBits, m_And(m_Specific(X), m_APIntAllowUndef(LowBitMaskCst))))
2803 return nullptr;
2804
2805 // Match even if the AND and ADD are swapped.
2806 const APInt *BiasCst, *HighBitMaskCst;
2807 if (!match(XBiasedHighBits,
2809 m_APIntAllowUndef(HighBitMaskCst))) &&
2810 !match(XBiasedHighBits,
2811 m_Add(m_And(m_Specific(X), m_APIntAllowUndef(HighBitMaskCst)),
2812 m_APIntAllowUndef(BiasCst))))
2813 return nullptr;
2814
2815 if (!LowBitMaskCst->isMask())
2816 return nullptr;
2817
2818 APInt InvertedLowBitMaskCst = ~*LowBitMaskCst;
2819 if (InvertedLowBitMaskCst != *HighBitMaskCst)
2820 return nullptr;
2821
2822 APInt AlignmentCst = *LowBitMaskCst + 1;
2823
2824 if (*BiasCst != AlignmentCst && *BiasCst != *LowBitMaskCst)
2825 return nullptr;
2826
2827 if (!XBiasedHighBits->hasOneUse()) {
2828 if (*BiasCst == *LowBitMaskCst)
2829 return XBiasedHighBits;
2830 return nullptr;
2831 }
2832
2833 // FIXME: could we preserve undef's here?
2834 Type *Ty = X->getType();
2835 Value *XOffset = Builder.CreateAdd(X, ConstantInt::get(Ty, *LowBitMaskCst),
2836 X->getName() + ".biased");
2837 Value *R = Builder.CreateAnd(XOffset, ConstantInt::get(Ty, *HighBitMaskCst));
2838 R->takeName(&SI);
2839 return R;
2840}
2841
2842namespace {
2843struct DecomposedSelect {
2844 Value *Cond = nullptr;
2845 Value *TrueVal = nullptr;
2846 Value *FalseVal = nullptr;
2847};
2848} // namespace
2849
2850/// Look for patterns like
2851/// %outer.cond = select i1 %inner.cond, i1 %alt.cond, i1 false
2852/// %inner.sel = select i1 %inner.cond, i8 %inner.sel.t, i8 %inner.sel.f
2853/// %outer.sel = select i1 %outer.cond, i8 %outer.sel.t, i8 %inner.sel
2854/// and rewrite it as
2855/// %inner.sel = select i1 %cond.alternative, i8 %sel.outer.t, i8 %sel.inner.t
2856/// %sel.outer = select i1 %cond.inner, i8 %inner.sel, i8 %sel.inner.f
2857static Instruction *foldNestedSelects(SelectInst &OuterSelVal,
2858 InstCombiner::BuilderTy &Builder) {
2859 // We must start with a `select`.
2860 DecomposedSelect OuterSel;
2861 match(&OuterSelVal,
2862 m_Select(m_Value(OuterSel.Cond), m_Value(OuterSel.TrueVal),
2863 m_Value(OuterSel.FalseVal)));
2864
2865 // Canonicalize inversion of the outermost `select`'s condition.
2866 if (match(OuterSel.Cond, m_Not(m_Value(OuterSel.Cond))))
2867 std::swap(OuterSel.TrueVal, OuterSel.FalseVal);
2868
2869 // The condition of the outermost select must be an `and`/`or`.
2870 if (!match(OuterSel.Cond, m_c_LogicalOp(m_Value(), m_Value())))
2871 return nullptr;
2872
2873 // Depending on the logical op, inner select might be in different hand.
2874 bool IsAndVariant = match(OuterSel.Cond, m_LogicalAnd());
2875 Value *InnerSelVal = IsAndVariant ? OuterSel.FalseVal : OuterSel.TrueVal;
2876
2877 // Profitability check - avoid increasing instruction count.
2878 if (none_of(ArrayRef<Value *>({OuterSelVal.getCondition(), InnerSelVal}),
2879 [](Value *V) { return V->hasOneUse(); }))
2880 return nullptr;
2881
2882 // The appropriate hand of the outermost `select` must be a select itself.
2883 DecomposedSelect InnerSel;
2884 if (!match(InnerSelVal,
2885 m_Select(m_Value(InnerSel.Cond), m_Value(InnerSel.TrueVal),
2886 m_Value(InnerSel.FalseVal))))
2887 return nullptr;
2888
2889 // Canonicalize inversion of the innermost `select`'s condition.
2890 if (match(InnerSel.Cond, m_Not(m_Value(InnerSel.Cond))))
2891 std::swap(InnerSel.TrueVal, InnerSel.FalseVal);
2892
2893 Value *AltCond = nullptr;
2894 auto matchOuterCond = [OuterSel, IsAndVariant, &AltCond](auto m_InnerCond) {
2895 // An unsimplified select condition can match both LogicalAnd and LogicalOr
2896 // (select true, true, false). Since below we assume that LogicalAnd implies
2897 // InnerSel match the FVal and vice versa for LogicalOr, we can't match the
2898 // alternative pattern here.
2899 return IsAndVariant ? match(OuterSel.Cond,
2900 m_c_LogicalAnd(m_InnerCond, m_Value(AltCond)))
2901 : match(OuterSel.Cond,
2902 m_c_LogicalOr(m_InnerCond, m_Value(AltCond)));
2903 };
2904
2905 // Finally, match the condition that was driving the outermost `select`,
2906 // it should be a logical operation between the condition that was driving
2907 // the innermost `select` (after accounting for the possible inversions
2908 // of the condition), and some other condition.
2909 if (matchOuterCond(m_Specific(InnerSel.Cond))) {
2910 // Done!
2911 } else if (Value * NotInnerCond; matchOuterCond(m_CombineAnd(
2912 m_Not(m_Specific(InnerSel.Cond)), m_Value(NotInnerCond)))) {
2913 // Done!
2914 std::swap(InnerSel.TrueVal, InnerSel.FalseVal);
2915 InnerSel.Cond = NotInnerCond;
2916 } else // Not the pattern we were looking for.
2917 return nullptr;
2918
2919 Value *SelInner = Builder.CreateSelect(
2920 AltCond, IsAndVariant ? OuterSel.TrueVal : InnerSel.FalseVal,
2921 IsAndVariant ? InnerSel.TrueVal : OuterSel.FalseVal);
2922 SelInner->takeName(InnerSelVal);
2923 return SelectInst::Create(InnerSel.Cond,
2924 IsAndVariant ? SelInner : InnerSel.TrueVal,
2925 !IsAndVariant ? SelInner : InnerSel.FalseVal);
2926}
2927
2929 Value *CondVal = SI.getCondition();
2930 Value *TrueVal = SI.getTrueValue();
2931 Value *FalseVal = SI.getFalseValue();
2932 Type *SelType = SI.getType();
2933
2934 // Avoid potential infinite loops by checking for non-constant condition.
2935 // TODO: Can we assert instead by improving canonicalizeSelectToShuffle()?
2936 // Scalar select must have simplified?
2937 if (!SelType->isIntOrIntVectorTy(1) || isa<Constant>(CondVal) ||
2938 TrueVal->getType() != CondVal->getType())
2939 return nullptr;
2940
2941 auto *One = ConstantInt::getTrue(SelType);
2942 auto *Zero = ConstantInt::getFalse(SelType);
2943 Value *A, *B, *C, *D;
2944
2945 // Folding select to and/or i1 isn't poison safe in general. impliesPoison
2946 // checks whether folding it does not convert a well-defined value into
2947 // poison.
2948 if (match(TrueVal, m_One())) {
2949 if (impliesPoison(FalseVal, CondVal)) {
2950 // Change: A = select B, true, C --> A = or B, C
2951 return BinaryOperator::CreateOr(CondVal, FalseVal);
2952 }
2953
2954 if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
2955 if (auto *RHS = dyn_cast<FCmpInst>(FalseVal))
2956 if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ false,
2957 /*IsSelectLogical*/ true))
2958 return replaceInstUsesWith(SI, V);
2959
2960 // (A && B) || (C && B) --> (A || C) && B
2961 if (match(CondVal, m_LogicalAnd(m_Value(A), m_Value(B))) &&
2962 match(FalseVal, m_LogicalAnd(m_Value(C), m_Value(D))) &&
2963 (CondVal->hasOneUse() || FalseVal->hasOneUse())) {
2964 bool CondLogicAnd = isa<SelectInst>(CondVal);
2965 bool FalseLogicAnd = isa<SelectInst>(FalseVal);
2966 auto AndFactorization = [&](Value *Common, Value *InnerCond,
2967 Value *InnerVal,
2968 bool SelFirst = false) -> Instruction * {
2969 Value *InnerSel = Builder.CreateSelect(InnerCond, One, InnerVal);
2970 if (SelFirst)
2971 std::swap(Common, InnerSel);
2972 if (FalseLogicAnd || (CondLogicAnd && Common == A))
2973 return SelectInst::Create(Common, InnerSel, Zero);
2974 else
2975 return BinaryOperator::CreateAnd(Common, InnerSel);
2976 };
2977
2978 if (A == C)
2979 return AndFactorization(A, B, D);
2980 if (A == D)
2981 return AndFactorization(A, B, C);
2982 if (B == C)
2983 return AndFactorization(B, A, D);
2984 if (B == D)
2985 return AndFactorization(B, A, C, CondLogicAnd && FalseLogicAnd);
2986 }
2987 }
2988
2989 if (match(FalseVal, m_Zero())) {
2990 if (impliesPoison(TrueVal, CondVal)) {
2991 // Change: A = select B, C, false --> A = and B, C
2992 return BinaryOperator::CreateAnd(CondVal, TrueVal);
2993 }
2994
2995 if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
2996 if (auto *RHS = dyn_cast<FCmpInst>(TrueVal))
2997 if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ true,
2998 /*IsSelectLogical*/ true))
2999 return replaceInstUsesWith(SI, V);
3000
3001 // (A || B) && (C || B) --> (A && C) || B
3002 if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
3003 match(TrueVal, m_LogicalOr(m_Value(C), m_Value(D))) &&
3004 (CondVal->hasOneUse() || TrueVal->hasOneUse())) {
3005 bool CondLogicOr = isa<SelectInst>(CondVal);
3006 bool TrueLogicOr = isa<SelectInst>(TrueVal);
3007 auto OrFactorization = [&](Value *Common, Value *InnerCond,
3008 Value *InnerVal,
3009 bool SelFirst = false) -> Instruction * {
3010 Value *InnerSel = Builder.CreateSelect(InnerCond, InnerVal, Zero);
3011 if (SelFirst)
3012 std::swap(Common, InnerSel);
3013 if (TrueLogicOr || (CondLogicOr && Common == A))
3014 return SelectInst::Create(Common, One, InnerSel);
3015 else
3016 return BinaryOperator::CreateOr(Common, InnerSel);
3017 };
3018
3019 if (A == C)
3020 return OrFactorization(A, B, D);
3021 if (A == D)
3022 return OrFactorization(A, B, C);
3023 if (B == C)
3024 return OrFactorization(B, A, D);
3025 if (B == D)
3026 return OrFactorization(B, A, C, CondLogicOr && TrueLogicOr);
3027 }
3028 }
3029
3030 // We match the "full" 0 or 1 constant here to avoid a potential infinite
3031 // loop with vectors that may have undefined/poison elements.
3032 // select a, false, b -> select !a, b, false
3033 if (match(TrueVal, m_Specific(Zero))) {
3034 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
3035 return SelectInst::Create(NotCond, FalseVal, Zero);
3036 }
3037 // select a, b, true -> select !a, true, b
3038 if (match(FalseVal, m_Specific(One))) {
3039 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
3040 return SelectInst::Create(NotCond, One, TrueVal);
3041 }
3042
3043 // DeMorgan in select form: !a && !b --> !(a || b)
3044 // select !a, !b, false --> not (select a, true, b)
3045 if (match(&SI, m_LogicalAnd(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
3046 (CondVal->hasOneUse() || TrueVal->hasOneUse()) &&
3049
3050 // DeMorgan in select form: !a || !b --> !(a && b)
3051 // select !a, true, !b --> not (select a, b, false)
3052 if (match(&SI, m_LogicalOr(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
3053 (CondVal->hasOneUse() || FalseVal->hasOneUse()) &&
3056
3057 // select (select a, true, b), true, b -> select a, true, b
3058 if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
3059 match(TrueVal, m_One()) && match(FalseVal, m_Specific(B)))
3060 return replaceOperand(SI, 0, A);
3061 // select (select a, b, false), b, false -> select a, b, false
3062 if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
3063 match(TrueVal, m_Specific(B)) && match(FalseVal, m_Zero()))
3064 return replaceOperand(SI, 0, A);
3065
3066 // ~(A & B) & (A | B) --> A ^ B
3069 return BinaryOperator::CreateXor(A, B);
3070
3071 // select (~a | c), a, b -> select a, (select c, true, b), false
3072 if (match(CondVal,
3073 m_OneUse(m_c_Or(m_Not(m_Specific(TrueVal)), m_Value(C))))) {
3074 Value *OrV = Builder.CreateSelect(C, One, FalseVal);
3075 return SelectInst::Create(TrueVal, OrV, Zero);
3076 }
3077 // select (c & b), a, b -> select b, (select ~c, true, a), false
3078 if (match(CondVal, m_OneUse(m_c_And(m_Value(C), m_Specific(FalseVal))))) {
3079 if (Value *NotC = getFreelyInverted(C, C->hasOneUse(), &Builder)) {
3080 Value *OrV = Builder.CreateSelect(NotC, One, TrueVal);
3081 return SelectInst::Create(FalseVal, OrV, Zero);
3082 }
3083 }
3084 // select (a | c), a, b -> select a, true, (select ~c, b, false)
3085 if (match(CondVal, m_OneUse(m_c_Or(m_Specific(TrueVal), m_Value(C))))) {
3086 if (Value *NotC = getFreelyInverted(C, C->hasOneUse(), &Builder)) {
3087 Value *AndV = Builder.CreateSelect(NotC, FalseVal, Zero);
3088 return SelectInst::Create(TrueVal, One, AndV);
3089 }
3090 }
3091 // select (c & ~b), a, b -> select b, true, (select c, a, false)
3092 if (match(CondVal,
3093 m_OneUse(m_c_And(m_Value(C), m_Not(m_Specific(FalseVal)))))) {
3094 Value *AndV = Builder.CreateSelect(C, TrueVal, Zero);
3095 return SelectInst::Create(FalseVal, One, AndV);
3096 }
3097
3098 if (match(FalseVal, m_Zero()) || match(TrueVal, m_One())) {
3099 Use *Y = nullptr;
3100 bool IsAnd = match(FalseVal, m_Zero()) ? true : false;
3101 Value *Op1 = IsAnd ? TrueVal : FalseVal;
3102 if (isCheckForZeroAndMulWithOverflow(CondVal, Op1, IsAnd, Y)) {
3103 auto *FI = new FreezeInst(*Y, (*Y)->getName() + ".fr");
3104 InsertNewInstBefore(FI, cast<Instruction>(Y->getUser())->getIterator());
3105 replaceUse(*Y, FI);
3106 return replaceInstUsesWith(SI, Op1);
3107 }
3108
3109 if (auto *Op1SI = dyn_cast<SelectInst>(Op1))
3110 if (auto *I = foldAndOrOfSelectUsingImpliedCond(CondVal, *Op1SI,
3111 /* IsAnd */ IsAnd))
3112 return I;
3113
3114 if (auto *ICmp0 = dyn_cast<ICmpInst>(CondVal))
3115 if (auto *ICmp1 = dyn_cast<ICmpInst>(Op1))
3116 if (auto *V = foldAndOrOfICmps(ICmp0, ICmp1, SI, IsAnd,
3117 /* IsLogical */ true))
3118 return replaceInstUsesWith(SI, V);
3119 }
3120
3121 // select (a || b), c, false -> select a, c, false
3122 // select c, (a || b), false -> select c, a, false
3123 // if c implies that b is false.
3124 if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
3125 match(FalseVal, m_Zero())) {
3126 std::optional<bool> Res = isImpliedCondition(TrueVal, B, DL);
3127 if (Res && *Res == false)
3128 return replaceOperand(SI, 0, A);
3129 }
3130 if (match(TrueVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
3131 match(FalseVal, m_Zero())) {
3132 std::optional<bool> Res = isImpliedCondition(CondVal, B, DL);
3133 if (Res && *Res == false)
3134 return replaceOperand(SI, 1, A);
3135 }
3136 // select c, true, (a && b) -> select c, true, a
3137 // select (a && b), true, c -> select a, true, c
3138 // if c = false implies that b = true
3139 if (match(TrueVal, m_One()) &&
3140 match(FalseVal, m_LogicalAnd(m_Value(A), m_Value(B)))) {
3141 std::optional<bool> Res = isImpliedCondition(CondVal, B, DL, false);
3142 if (Res && *Res == true)
3143 return replaceOperand(SI, 2, A);
3144 }
3145 if (match(CondVal, m_LogicalAnd(m_Value(A), m_Value(B))) &&
3146 match(TrueVal, m_One())) {
3147 std::optional<bool> Res = isImpliedCondition(FalseVal, B, DL, false);
3148 if (Res && *Res == true)
3149 return replaceOperand(SI, 0, A);
3150 }
3151
3152 if (match(TrueVal, m_One())) {
3153 Value *C;
3154
3155 // (C && A) || (!C && B) --> sel C, A, B
3156 // (A && C) || (!C && B) --> sel C, A, B
3157 // (C && A) || (B && !C) --> sel C, A, B
3158 // (A && C) || (B && !C) --> sel C, A, B (may require freeze)
3159 if (match(FalseVal, m_c_LogicalAnd(m_Not(m_Value(C)), m_Value(B))) &&
3160 match(CondVal, m_c_LogicalAnd(m_Specific(C), m_Value(A)))) {
3161 auto *SelCond = dyn_cast<SelectInst>(CondVal);
3162 auto *SelFVal = dyn_cast<SelectInst>(FalseVal);
3163 bool MayNeedFreeze = SelCond && SelFVal &&
3164 match(SelFVal->getTrueValue(),
3165 m_Not(m_Specific(SelCond->getTrueValue())));
3166 if (MayNeedFreeze)
3168 return SelectInst::Create(C, A, B);
3169 }
3170
3171 // (!C && A) || (C && B) --> sel C, B, A
3172 // (A && !C) || (C && B) --> sel C, B, A
3173 // (!C && A) || (B && C) --> sel C, B, A
3174 // (A && !C) || (B && C) --> sel C, B, A (may require freeze)
3175 if (match(CondVal, m_c_LogicalAnd(m_Not(m_Value(C)), m_Value(A))) &&
3176 match(FalseVal, m_c_LogicalAnd(m_Specific(C), m_Value(B)))) {
3177 auto *SelCond = dyn_cast<SelectInst>(CondVal);
3178 auto *SelFVal = dyn_cast<SelectInst>(FalseVal);
3179 bool MayNeedFreeze = SelCond && SelFVal &&
3180 match(SelCond->getTrueValue(),
3181 m_Not(m_Specific(SelFVal->getTrueValue())));
3182 if (MayNeedFreeze)
3184 return SelectInst::Create(C, B, A);
3185 }
3186 }
3187
3188 return nullptr;
3189}
3190
3191// Return true if we can safely remove the select instruction for std::bit_ceil
3192// pattern.
3193static bool isSafeToRemoveBitCeilSelect(ICmpInst::Predicate Pred, Value *Cond0,
3194 const APInt *Cond1, Value *CtlzOp,
3195 unsigned BitWidth) {
3196 // The challenge in recognizing std::bit_ceil(X) is that the operand is used
3197 // for the CTLZ proper and select condition, each possibly with some
3198 // operation like add and sub.
3199 //
3200 // Our aim is to make sure that -ctlz & (BitWidth - 1) == 0 even when the
3201 // select instruction would select 1, which allows us to get rid of the select
3202 // instruction.
3203 //
3204 // To see if we can do so, we do some symbolic execution with ConstantRange.
3205 // Specifically, we compute the range of values that Cond0 could take when
3206 // Cond == false. Then we successively transform the range until we obtain
3207 // the range of values that CtlzOp could take.
3208 //
3209 // Conceptually, we follow the def-use chain backward from Cond0 while
3210 // transforming the range for Cond0 until we meet the common ancestor of Cond0
3211 // and CtlzOp. Then we follow the def-use chain forward until we obtain the
3212 // range for CtlzOp. That said, we only follow at most one ancestor from
3213 // Cond0. Likewise, we only follow at most one ancestor from CtrlOp.
3214
3216 CmpInst::getInversePredicate(Pred), *Cond1);
3217
3218 // Match the operation that's used to compute CtlzOp from CommonAncestor. If
3219 // CtlzOp == CommonAncestor, return true as no operation is needed. If a
3220 // match is found, execute the operation on CR, update CR, and return true.
3221 // Otherwise, return false.
3222 auto MatchForward = [&](Value *CommonAncestor) {
3223 const APInt *C = nullptr;
3224 if (CtlzOp == CommonAncestor)
3225 return true;
3226 if (match(CtlzOp, m_Add(m_Specific(CommonAncestor), m_APInt(C)))) {
3227 CR = CR.add(*C);
3228 return true;
3229 }
3230 if (match(CtlzOp, m_Sub(m_APInt(C), m_Specific(CommonAncestor)))) {
3231 CR = ConstantRange(*C).sub(CR);
3232 return true;
3233 }
3234 if (match(CtlzOp, m_Not(m_Specific(CommonAncestor)))) {
3235 CR = CR.binaryNot();
3236 return true;
3237 }
3238 return false;
3239 };
3240
3241 const APInt *C = nullptr;
3242 Value *CommonAncestor;
3243 if (MatchForward(Cond0)) {
3244 // Cond0 is either CtlzOp or CtlzOp's parent. CR has been updated.
3245 } else if (match(Cond0, m_Add(m_Value(CommonAncestor), m_APInt(C)))) {
3246 CR = CR.sub(*C);
3247 if (!MatchForward(CommonAncestor))
3248 return false;
3249 // Cond0's parent is either CtlzOp or CtlzOp's parent. CR has been updated.
3250 } else {
3251 return false;
3252 }
3253
3254 // Return true if all the values in the range are either 0 or negative (if
3255 // treated as signed). We do so by evaluating:
3256 //
3257 // CR - 1 u>= (1 << BitWidth) - 1.
3258 APInt IntMax = APInt::getSignMask(BitWidth) - 1;
3259 CR = CR.sub(APInt(BitWidth, 1));
3260 return CR.icmp(ICmpInst::ICMP_UGE, IntMax);
3261}
3262
3263// Transform the std::bit_ceil(X) pattern like:
3264//
3265// %dec = add i32 %x, -1
3266// %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)
3267// %sub = sub i32 32, %ctlz
3268// %shl = shl i32 1, %sub
3269// %ugt = icmp ugt i32 %x, 1
3270// %sel = select i1 %ugt, i32 %shl, i32 1
3271//
3272// into:
3273//
3274// %dec = add i32 %x, -1
3275// %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)
3276// %neg = sub i32 0, %ctlz
3277// %masked = and i32 %ctlz, 31
3278// %shl = shl i32 1, %sub
3279//
3280// Note that the select is optimized away while the shift count is masked with
3281// 31. We handle some variations of the input operand like std::bit_ceil(X +
3282// 1).
3283static Instruction *foldBitCeil(SelectInst &SI, IRBuilderBase &Builder) {
3284 Type *SelType = SI.getType();
3285 unsigned BitWidth = SelType->getScalarSizeInBits();
3286
3287 Value *FalseVal = SI.getFalseValue();
3288 Value *TrueVal = SI.getTrueValue();
3290 const APInt *Cond1;
3291 Value *Cond0, *Ctlz, *CtlzOp;
3292 if (!match(SI.getCondition(), m_ICmp(Pred, m_Value(Cond0), m_APInt(Cond1))))
3293 return nullptr;
3294
3295 if (match(TrueVal, m_One())) {
3296 std::swap(FalseVal, TrueVal);
3297 Pred = CmpInst::getInversePredicate(Pred);
3298 }
3299
3300 if (!match(FalseVal, m_One()) ||
3301 !match(TrueVal,
3303 m_Value(Ctlz)))))) ||
3304 !match(Ctlz, m_Intrinsic<Intrinsic::ctlz>(m_Value(CtlzOp), m_Zero())) ||
3305 !isSafeToRemoveBitCeilSelect(Pred, Cond0, Cond1, CtlzOp, BitWidth))
3306 return nullptr;
3307
3308 // Build 1 << (-CTLZ & (BitWidth-1)). The negation likely corresponds to a
3309 // single hardware instruction as opposed to BitWidth - CTLZ, where BitWidth
3310 // is an integer constant. Masking with BitWidth-1 comes free on some
3311 // hardware as part of the shift instruction.
3312 Value *Neg = Builder.CreateNeg(Ctlz);
3313 Value *Masked =
3314 Builder.CreateAnd(Neg, ConstantInt::get(SelType, BitWidth - 1));
3315 return BinaryOperator::Create(Instruction::Shl, ConstantInt::get(SelType, 1),
3316 Masked);
3317}
3318
3320 const Instruction *CtxI) const {
3321 KnownFPClass Known = computeKnownFPClass(MulVal, FMF, fcNegative, CtxI);
3322
3323 return Known.isKnownNeverNaN() && Known.isKnownNeverInfinity() &&
3324 (FMF.noSignedZeros() || Known.signBitIsZeroOrNaN());
3325}
3326
3327static bool matchFMulByZeroIfResultEqZero(InstCombinerImpl &IC, Value *Cmp0,
3328 Value *Cmp1, Value *TrueVal,
3329 Value *FalseVal, Instruction &CtxI,
3330 bool SelectIsNSZ) {
3331 Value *MulRHS;
3332 if (match(Cmp1, m_PosZeroFP()) &&
3333 match(TrueVal, m_c_FMul(m_Specific(Cmp0), m_Value(MulRHS)))) {
3334 FastMathFlags FMF = cast<FPMathOperator>(TrueVal)->getFastMathFlags();
3335 // nsz must be on the select, it must be ignored on the multiply. We
3336 // need nnan and ninf on the multiply for the other value.
3337 FMF.setNoSignedZeros(SelectIsNSZ);
3338 return IC.fmulByZeroIsZero(MulRHS, FMF, &CtxI);
3339 }
3340
3341 return false;
3342}
3343
3345 Value *CondVal = SI.getCondition();
3346 Value *TrueVal = SI.getTrueValue();
3347 Value *FalseVal = SI.getFalseValue();
3348 Type *SelType = SI.getType();
3349
3350 if (Value *V = simplifySelectInst(CondVal, TrueVal, FalseVal,
3351 SQ.getWithInstruction(&SI)))
3352 return replaceInstUsesWith(SI, V);
3353
3354 if (Instruction *I = canonicalizeSelectToShuffle(SI))
3355 return I;
3356
3357 if (Instruction *I = canonicalizeScalarSelectOfVecs(SI, *this))
3358 return I;
3359
3360 // If the type of select is not an integer type or if the condition and
3361 // the selection type are not both scalar nor both vector types, there is no
3362 // point in attempting to match these patterns.
3363 Type *CondType = CondVal->getType();
3364 if (!isa<Constant>(CondVal) && SelType->isIntOrIntVectorTy() &&
3365 CondType->isVectorTy() == SelType->isVectorTy()) {
3366 if (Value *S = simplifyWithOpReplaced(TrueVal, CondVal,
3367 ConstantInt::getTrue(CondType), SQ,
3368 /* AllowRefinement */ true))
3369 return replaceOperand(SI, 1, S);
3370
3371 if (Value *S = simplifyWithOpReplaced(FalseVal, CondVal,
3372 ConstantInt::getFalse(CondType), SQ,
3373 /* AllowRefinement */ true))
3374 return replaceOperand(SI, 2, S);
3375 }
3376
3377 if (Instruction *R = foldSelectOfBools(SI))
3378 return R;
3379
3380 // Selecting between two integer or vector splat integer constants?
3381 //
3382 // Note that we don't handle a scalar select of vectors:
3383 // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>
3384 // because that may need 3 instructions to splat the condition value:
3385 // extend, insertelement, shufflevector.
3386 //
3387 // Do not handle i1 TrueVal and FalseVal otherwise would result in
3388 // zext/sext i1 to i1.
3389 if (SelType->isIntOrIntVectorTy() && !SelType->isIntOrIntVectorTy(1) &&
3390 CondVal->getType()->isVectorTy() == SelType->isVectorTy()) {
3391 // select C, 1, 0 -> zext C to int
3392 if (match(TrueVal, m_One()) && match(FalseVal, m_Zero()))
3393 return new ZExtInst(CondVal, SelType);
3394
3395 // select C, -1, 0 -> sext C to int
3396 if (match(TrueVal, m_AllOnes()) && match(FalseVal, m_Zero()))
3397 return new SExtInst(CondVal, SelType);
3398
3399 // select C, 0, 1 -> zext !C to int
3400 if (match(TrueVal, m_Zero()) && match(FalseVal, m_One())) {
3401 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
3402 return new ZExtInst(NotCond, SelType);
3403 }
3404
3405 // select C, 0, -1 -> sext !C to int
3406 if (match(TrueVal, m_Zero()) && match(FalseVal, m_AllOnes())) {
3407 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
3408 return new SExtInst(NotCond, SelType);
3409 }
3410 }
3411
3412 auto *SIFPOp = dyn_cast<FPMathOperator>(&SI);
3413
3414 if (auto *FCmp = dyn_cast<FCmpInst>(CondVal)) {
3415 FCmpInst::Predicate Pred = FCmp->getPredicate();
3416 Value *Cmp0 = FCmp->getOperand(0), *Cmp1 = FCmp->getOperand(1);
3417 // Are we selecting a value based on a comparison of the two values?
3418 if ((Cmp0 == TrueVal && Cmp1 == FalseVal) ||
3419 (Cmp0 == FalseVal && Cmp1 == TrueVal)) {
3420 // Canonicalize to use ordered comparisons by swapping the select
3421 // operands.
3422 //
3423 // e.g.
3424 // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X
3425 if (FCmp->hasOneUse() && FCmpInst::isUnordered(Pred)) {
3426 FCmpInst::Predicate InvPred = FCmp->getInversePredicate();
3428 // FIXME: The FMF should propagate from the select, not the fcmp.
3429 Builder.setFastMathFlags(FCmp->getFastMathFlags());
3430 Value *NewCond = Builder.CreateFCmp(InvPred, Cmp0, Cmp1,
3431 FCmp->getName() + ".inv");
3432 Value *NewSel = Builder.CreateSelect(NewCond, FalseVal, TrueVal);
3433 return replaceInstUsesWith(SI, NewSel);
3434 }
3435 }
3436
3437 if (SIFPOp) {
3438 // Fold out scale-if-equals-zero pattern.
3439 //
3440 // This pattern appears in code with denormal range checks after it's
3441 // assumed denormals are treated as zero. This drops a canonicalization.
3442
3443 // TODO: Could relax the signed zero logic. We just need to know the sign
3444 // of the result matches (fmul x, y has the same sign as x).
3445 //
3446 // TODO: Handle always-canonicalizing variant that selects some value or 1
3447 // scaling factor in the fmul visitor.
3448
3449 // TODO: Handle ldexp too
3450
3451 Value *MatchCmp0 = nullptr;
3452 Value *MatchCmp1 = nullptr;
3453
3454 // (select (fcmp [ou]eq x, 0.0), (fmul x, K), x => x
3455 // (select (fcmp [ou]ne x, 0.0), x, (fmul x, K) => x
3456 if (Pred == CmpInst::FCMP_OEQ || Pred == CmpInst::FCMP_UEQ) {
3457 MatchCmp0 = FalseVal;
3458 MatchCmp1 = TrueVal;
3459 } else if (Pred == CmpInst::FCMP_ONE || Pred == CmpInst::FCMP_UNE) {
3460 MatchCmp0 = TrueVal;
3461 MatchCmp1 = FalseVal;
3462 }
3463
3464 if (Cmp0 == MatchCmp0 &&
3465 matchFMulByZeroIfResultEqZero(*this, Cmp0, Cmp1, MatchCmp1, MatchCmp0,
3466 SI, SIFPOp->hasNoSignedZeros()))
3467 return replaceInstUsesWith(SI, Cmp0);
3468 }
3469 }
3470
3471 if (SIFPOp) {
3472 // TODO: Try to forward-propagate FMF from select arms to the select.
3473
3474 // Canonicalize select of FP values where NaN and -0.0 are not valid as
3475 // minnum/maxnum intrinsics.
3476 if (SIFPOp->hasNoNaNs() && SIFPOp->hasNoSignedZeros()) {
3477 Value *X, *Y;
3478 if (match(&SI, m_OrdFMax(m_Value(X), m_Value(Y))))
3479 return replaceInstUsesWith(
3480 SI, Builder.CreateBinaryIntrinsic(Intrinsic::maxnum, X, Y, &SI));
3481
3482 if (match(&SI, m_OrdFMin(m_Value(X), m_Value(Y))))
3483 return replaceInstUsesWith(
3484 SI, Builder.CreateBinaryIntrinsic(Intrinsic::minnum, X, Y, &SI));
3485 }
3486 }
3487
3488 // Fold selecting to fabs.
3489 if (Instruction *Fabs = foldSelectWithFCmpToFabs(SI, *this))
3490 return Fabs;
3491
3492 // See if we are selecting two values based on a comparison of the two values.
3493 if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal))
3494 if (Instruction *Result = foldSelectInstWithICmp(SI, ICI))
3495 return Result;
3496
3497 if (Instruction *Add = foldAddSubSelect(SI, Builder))
3498 return Add;
3499 if (Instruction *Add = foldOverflowingAddSubSelect(SI, Builder))
3500 return Add;
3502 return Or;
3503 if (Instruction *Mul = foldSelectZeroOrMul(SI, *this))
3504 return Mul;
3505
3506 // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
3507 auto *TI = dyn_cast<Instruction>(TrueVal);
3508 auto *FI = dyn_cast<Instruction>(FalseVal);
3509 if (TI && FI && TI->getOpcode() == FI->getOpcode())
3510 if (Instruction *IV = foldSelectOpOp(SI, TI, FI))
3511 return IV;
3512
3513 if (Instruction *I = foldSelectExtConst(SI))
3514 return I;
3515
3516 if (Instruction *I = foldSelectWithSRem(SI, *this, Builder))
3517 return I;
3518
3519 // Fold (select C, (gep Ptr, Idx), Ptr) -> (gep Ptr, (select C, Idx, 0))
3520 // Fold (select C, Ptr, (gep Ptr, Idx)) -> (gep Ptr, (select C, 0, Idx))
3521 auto SelectGepWithBase = [&](GetElementPtrInst *Gep, Value *Base,
3522 bool Swap) -> GetElementPtrInst * {
3523 Value *Ptr = Gep->getPointerOperand();
3524 if (Gep->getNumOperands() != 2 || Gep->getPointerOperand() != Base ||
3525 !Gep->hasOneUse())
3526 return nullptr;
3527 Value *Idx = Gep->getOperand(1);
3528 if (isa<VectorType>(CondVal->getType()) && !isa<VectorType>(Idx->getType()))
3529 return nullptr;
3530 Type *ElementType = Gep->getResultElementType();
3531 Value *NewT = Idx;
3532 Value *NewF = Constant::getNullValue(Idx->getType());
3533 if (Swap)
3534 std::swap(NewT, NewF);
3535 Value *NewSI =
3536 Builder.CreateSelect(CondVal, NewT, NewF, SI.getName() + ".idx", &SI);
3537 if (Gep->isInBounds())
3538 return GetElementPtrInst::CreateInBounds(ElementType, Ptr, {NewSI});
3539 return GetElementPtrInst::Create(ElementType, Ptr, {NewSI});
3540 };
3541 if (auto *TrueGep = dyn_cast<GetElementPtrInst>(TrueVal))
3542 if (auto *NewGep = SelectGepWithBase(TrueGep, FalseVal, false))
3543 return NewGep;
3544 if (auto *FalseGep = dyn_cast<GetElementPtrInst>(FalseVal))
3545 if (auto *NewGep = SelectGepWithBase(FalseGep, TrueVal, true))
3546 return NewGep;
3547
3548 // See if we can fold the select into one of our operands.
3549 if (SelType->isIntOrIntVectorTy() || SelType->isFPOrFPVectorTy()) {
3550 if (Instruction *FoldI = foldSelectIntoOp(SI, TrueVal, FalseVal))
3551 return FoldI;
3552
3553 Value *LHS, *RHS;
3554 Instruction::CastOps CastOp;
3555 SelectPatternResult SPR = matchSelectPattern(&SI, LHS, RHS, &CastOp);
3556 auto SPF = SPR.Flavor;
3557 if (SPF) {
3558 Value *LHS2, *RHS2;
3559 if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor)
3560 if (Instruction *R = foldSPFofSPF(cast<Instruction>(LHS), SPF2, LHS2,
3561 RHS2, SI, SPF, RHS))
3562 return R;
3563 if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor)
3564 if (Instruction *R = foldSPFofSPF(cast<Instruction>(RHS), SPF2, LHS2,
3565 RHS2, SI, SPF, LHS))
3566 return R;
3567 }
3568
3570 // Canonicalize so that
3571 // - type casts are outside select patterns.
3572 // - float clamp is transformed to min/max pattern
3573
3574 bool IsCastNeeded = LHS->getType() != SelType;
3575 Value *CmpLHS = cast<CmpInst>(CondVal)->getOperand(0);
3576 Value *CmpRHS = cast<CmpInst>(CondVal)->getOperand(1);
3577 if (IsCastNeeded ||
3578 (LHS->getType()->isFPOrFPVectorTy() &&
3579 ((CmpLHS != LHS && CmpLHS != RHS) ||
3580 (CmpRHS != LHS && CmpRHS != RHS)))) {
3581 CmpInst::Predicate MinMaxPred = getMinMaxPred(SPF, SPR.Ordered);
3582
3583 Value *Cmp;
3584 if (CmpInst::isIntPredicate(MinMaxPred)) {
3585 Cmp = Builder.CreateICmp(MinMaxPred, LHS, RHS);
3586 } else {
3588 auto FMF =
3589 cast<FPMathOperator>(SI.getCondition())->getFastMathFlags();
3591 Cmp = Builder.CreateFCmp(MinMaxPred, LHS, RHS);
3592 }
3593
3594 Value *NewSI = Builder.CreateSelect(Cmp, LHS, RHS, SI.getName(), &SI);
3595 if (!IsCastNeeded)
3596 return replaceInstUsesWith(SI, NewSI);
3597
3598 Value *NewCast = Builder.CreateCast(CastOp, NewSI, SelType);
3599 return replaceInstUsesWith(SI, NewCast);
3600 }
3601 }
3602 }
3603
3604 // See if we can fold the select into a phi node if the condition is a select.
3605 if (auto *PN = dyn_cast<PHINode>(SI.getCondition()))
3606 // The true/false values have to be live in the PHI predecessor's blocks.
3607 if (canSelectOperandBeMappingIntoPredBlock(TrueVal, SI) &&
3608 canSelectOperandBeMappingIntoPredBlock(FalseVal, SI))
3609 if (Instruction *NV = foldOpIntoPhi(SI, PN))
3610 return NV;
3611
3612 if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) {
3613 if (TrueSI->getCondition()->getType() == CondVal->getType()) {
3614 // select(C, select(C, a, b), c) -> select(C, a, c)
3615 if (TrueSI->getCondition() == CondVal) {
3616 if (SI.getTrueValue() == TrueSI->getTrueValue())
3617 return nullptr;
3618 return replaceOperand(SI, 1, TrueSI->getTrueValue());
3619 }
3620 // select(C0, select(C1, a, b), b) -> select(C0&C1, a, b)
3621 // We choose this as normal form to enable folding on the And and
3622 // shortening paths for the values (this helps getUnderlyingObjects() for
3623 // example).
3624 if (TrueSI->getFalseValue() == FalseVal && TrueSI->hasOneUse()) {
3625 Value *And = Builder.CreateLogicalAnd(CondVal, TrueSI->getCondition());
3626 replaceOperand(SI, 0, And);
3627 replaceOperand(SI, 1, TrueSI->getTrueValue());
3628 return &SI;
3629 }
3630 }
3631 }
3632 if (SelectInst *FalseSI = dyn_cast<SelectInst>(FalseVal)) {
3633 if (FalseSI->getCondition()->getType() == CondVal->getType()) {
3634 // select(C, a, select(C, b, c)) -> select(C, a, c)
3635 if (FalseSI->getCondition() == CondVal) {
3636 if (SI.getFalseValue() == FalseSI->getFalseValue())
3637 return nullptr;
3638 return replaceOperand(SI, 2, FalseSI->getFalseValue());
3639 }
3640 // select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b)
3641 if (FalseSI->getTrueValue() == TrueVal && FalseSI->hasOneUse()) {
3642 Value *Or = Builder.CreateLogicalOr(CondVal, FalseSI->getCondition());
3643 replaceOperand(SI, 0, Or);
3644 replaceOperand(SI, 2, FalseSI->getFalseValue());
3645 return &SI;
3646 }
3647 }
3648 }
3649
3650 // Try to simplify a binop sandwiched between 2 selects with the same
3651 // condition. This is not valid for div/rem because the select might be
3652 // preventing a division-by-zero.
3653 // TODO: A div/rem restriction is conservative; use something like
3654 // isSafeToSpeculativelyExecute().
3655 // select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z)
3656 BinaryOperator *TrueBO;
3657 if (match(TrueVal, m_OneUse(m_BinOp(TrueBO))) && !TrueBO->isIntDivRem()) {
3658 if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(0))) {
3659 if (TrueBOSI->getCondition() == CondVal) {
3660 replaceOperand(*TrueBO, 0, TrueBOSI->getTrueValue());
3661 Worklist.push(TrueBO);
3662 return &SI;
3663 }
3664 }
3665 if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(1))) {
3666 if (TrueBOSI->getCondition() == CondVal) {
3667 replaceOperand(*TrueBO, 1, TrueBOSI->getTrueValue());
3668 Worklist.push(TrueBO);
3669 return &SI;
3670 }
3671 }
3672 }
3673
3674 // select(C, Z, binop(select(C, X, Y), W)) -> select(C, Z, binop(Y, W))
3675 BinaryOperator *FalseBO;
3676 if (match(FalseVal, m_OneUse(m_BinOp(FalseBO))) && !FalseBO->isIntDivRem()) {
3677 if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(0))) {
3678 if (FalseBOSI->getCondition() == CondVal) {
3679 replaceOperand(*FalseBO, 0, FalseBOSI->getFalseValue());
3680 Worklist.push(FalseBO);
3681 return &SI;
3682 }
3683 }
3684 if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(1))) {
3685 if (FalseBOSI->getCondition() == CondVal) {
3686 replaceOperand(*FalseBO, 1, FalseBOSI->getFalseValue());
3687 Worklist.push(FalseBO);
3688 return &SI;
3689 }
3690 }
3691 }
3692
3693 Value *NotCond;
3694 if (match(CondVal, m_Not(m_Value(NotCond))) &&
3696 replaceOperand(SI, 0, NotCond);
3697 SI.swapValues();
3698 SI.swapProfMetadata();
3699 return &SI;
3700 }
3701
3702 if (Instruction *I = foldVectorSelect(SI))
3703 return I;
3704
3705 // If we can compute the condition, there's no need for a select.
3706 // Like the above fold, we are attempting to reduce compile-time cost by
3707 // putting this fold here with limitations rather than in InstSimplify.
3708 // The motivation for this call into value tracking is to take advantage of
3709 // the assumption cache, so make sure that is populated.
3710 if (!CondVal->getType()->isVectorTy() && !AC.assumptions().empty()) {
3711 KnownBits Known(1);
3712 computeKnownBits(CondVal, Known, 0, &SI);
3713 if (Known.One.isOne())
3714 return replaceInstUsesWith(SI, TrueVal);
3715 if (Known.Zero.isOne())
3716 return replaceInstUsesWith(SI, FalseVal);
3717 }
3718
3719 if (Instruction *BitCastSel = foldSelectCmpBitcasts(SI, Builder))
3720 return BitCastSel;
3721
3722 // Simplify selects that test the returned flag of cmpxchg instructions.
3723 if (Value *V = foldSelectCmpXchg(SI))
3724 return replaceInstUsesWith(SI, V);
3725
3726 if (Instruction *Select = foldSelectBinOpIdentity(SI, TLI, *this))
3727 return Select;
3728
3729 if (Instruction *Funnel = foldSelectFunnelShift(SI, Builder))
3730 return Funnel;
3731
3732 if (Instruction *Copysign = foldSelectToCopysign(SI, Builder))
3733 return Copysign;
3734
3735 if (Instruction *PN = foldSelectToPhi(SI, DT, Builder))
3736 return replaceInstUsesWith(SI, PN);
3737
3738 if (Value *Fr = foldSelectWithFrozenICmp(SI, Builder))
3739 return replaceInstUsesWith(SI, Fr);
3740
3741 if (Value *V = foldRoundUpIntegerWithPow2Alignment(SI, Builder))
3742 return replaceInstUsesWith(SI, V);
3743
3744 // select(mask, mload(,,mask,0), 0) -> mload(,,mask,0)
3745 // Load inst is intentionally not checked for hasOneUse()
3746 if (match(FalseVal, m_Zero()) &&
3747 (match(TrueVal, m_MaskedLoad(m_Value(), m_Value(), m_Specific(CondVal),
3748 m_CombineOr(m_Undef(), m_Zero()))) ||
3749 match(TrueVal, m_MaskedGather(m_Value(), m_Value(), m_Specific(CondVal),
3750 m_CombineOr(m_Undef(), m_Zero()))))) {
3751 auto *MaskedInst = cast<IntrinsicInst>(TrueVal);
3752 if (isa<UndefValue>(MaskedInst->getArgOperand(3)))
3753 MaskedInst->setArgOperand(3, FalseVal /* Zero */);
3754 return replaceInstUsesWith(SI, MaskedInst);
3755 }
3756
3757 Value *Mask;
3758 if (match(TrueVal, m_Zero()) &&
3759 (match(FalseVal, m_MaskedLoad(m_Value(), m_Value(), m_Value(Mask),
3760 m_CombineOr(m_Undef(), m_Zero()))) ||
3761 match(FalseVal, m_MaskedGather(m_Value(), m_Value(), m_Value(Mask),
3762 m_CombineOr(m_Undef(), m_Zero())))) &&
3763 (CondVal->getType() == Mask->getType())) {
3764 // We can remove the select by ensuring the load zeros all lanes the
3765 // select would have. We determine this by proving there is no overlap
3766 // between the load and select masks.
3767 // (i.e (load_mask & select_mask) == 0 == no overlap)
3768 bool CanMergeSelectIntoLoad = false;
3769 if (Value *V = simplifyAndInst(CondVal, Mask, SQ.getWithInstruction(&SI)))
3770 CanMergeSelectIntoLoad = match(V, m_Zero());
3771
3772 if (CanMergeSelectIntoLoad) {
3773 auto *MaskedInst = cast<IntrinsicInst>(FalseVal);
3774 if (isa<UndefValue>(MaskedInst->getArgOperand(3)))
3775 MaskedInst->setArgOperand(3, TrueVal /* Zero */);
3776 return replaceInstUsesWith(SI, MaskedInst);
3777 }
3778 }
3779
3780 if (Instruction *I = foldNestedSelects(SI, Builder))
3781 return I;
3782
3783 // Match logical variants of the pattern,
3784 // and transform them iff that gets rid of inversions.
3785 // (~x) | y --> ~(x & (~y))
3786 // (~x) & y --> ~(x | (~y))
3788 return &SI;
3789
3790 if (Instruction *I = foldBitCeil(SI, Builder))
3791 return I;
3792
3793 return nullptr;
3794}
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
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:1260
bool isNegative() const
Definition: APFloat.h:1295
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:521
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:437
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:228
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:1394
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1399
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:748
@ FCMP_OEQ
0 0 0 1 True if ordered and equal
Definition: InstrTypes.h:751
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:777
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:778
@ FCMP_OLT
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:754
@ FCMP_ULE
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:763
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:752
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:753
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:772
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:771
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:775
@ FCMP_ULT
1 1 0 0 True if unordered or less than
Definition: InstrTypes.h:762
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:756
@ FCMP_UEQ
1 0 0 1 True if unordered or equal
Definition: InstrTypes.h:759
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:773
@ FCMP_UGT
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:760
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:755
@ ICMP_EQ
equal
Definition: InstrTypes.h:769
@ ICMP_NE
not equal
Definition: InstrTypes.h:770
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:776
@ FCMP_UNE
1 1 1 0 True if unordered or not equal
Definition: InstrTypes.h:764
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:774
@ FCMP_UGE
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:761
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:900
bool isFPPredicate() const
Definition: InstrTypes.h:855
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:862
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:838
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:966
bool isIntPredicate() const
Definition: InstrTypes.h:856
bool isUnsigned() const
Definition: InstrTypes.h:1004
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2460
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:2320
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2514
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2441
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.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
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:165
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:123
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:948
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:997
Type * getResultElementType() const
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:974
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:913
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1996
Value * CreateNeg(Value *V, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1715
Value * CreateFCmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2334
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
Definition: IRBuilder.h:2018
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Definition: IRBuilder.cpp:1212
ConstantInt * getTrue()
Get the constant value for i1 true.
Definition: IRBuilder.h:460
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:930
Value * CreateICmpSGE(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2242
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1108
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2508
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1431
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
Definition: IRBuilder.h:305
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Definition: IRBuilder.h:2370
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1748
Value * CreateIsNeg(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg < 0.
Definition: IRBuilder.h:2527
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1410
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:921
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Definition: IRBuilder.h:2000
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1469
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1321
Value * CreateIsNotNull(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg != 0.
Definition: IRBuilder.h:2522
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1491
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1660
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
Definition: IRBuilder.h:1670
Value * CreateICmpSLT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2246
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2134
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
Value * CreateAShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1450
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1513
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2324
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Definition: IRBuilder.h:1676
Value * CreateFNeg(Value *V, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1729
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)
Constant * getLosslessTrunc(Constant *C, Type *TruncTy, unsigned ExtOp)
Instruction * foldSelectIntoOp(SelectInst &SI, Value *, Value *)
Try to fold the select into one of the operands to allow further optimization.
Instruction * visitSelectInst(SelectInst &SI)
Instruction * foldSelectOfBools(SelectInst &SI)
Instruction * foldSelectExtConst(SelectInst &Sel)
const DataLayout & getDataLayout() const
Definition: InstCombiner.h:375
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
Definition: InstCombiner.h:152
TargetLibraryInfo & TLI
Definition: InstCombiner.h:72
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
Definition: InstCombiner.h:475
Instruction * InsertNewInstBefore(Instruction *New, BasicBlock::iterator Old)
Inserts an instruction New before instruction Old.
Definition: InstCombiner.h:400
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombiner.h:420
static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
Definition: InstCombiner.h:225
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:452
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:444
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:172
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:465
BuilderTy & Builder
Definition: InstCombiner.h:59
Value * getFreelyInverted(Value *V, bool WillInvertAllUses, BuilderTy *Builder, bool &DoesConsume)
Definition: InstCombiner.h:247
static Constant * AddOne(Constant *C)
Add one to a Constant.
Definition: InstCombiner.h:209
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:247
bool hasNoSignedZeros() const LLVM_READONLY
Determine whether the no-signed-zeros flag is set.
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:71
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
void setFastMathFlags(FastMathFlags FMF)
Convenience function for setting multiple fast-math flags on this instruction, which must be an opera...
const BasicBlock * getParent() const
Definition: Instruction.h:139
void swapProfMetadata()
If the instruction has "branch_weights" MD_prof metadata and the MDNode has three operands (including...
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.