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