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