LLVM  16.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/Optional.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/IR/BasicBlock.h"
24 #include "llvm/IR/Constant.h"
25 #include "llvm/IR/ConstantRange.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/IRBuilder.h"
29 #include "llvm/IR/InstrTypes.h"
30 #include "llvm/IR/Instruction.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/IR/Intrinsics.h"
34 #include "llvm/IR/Operator.h"
35 #include "llvm/IR/PatternMatch.h"
36 #include "llvm/IR/Type.h"
37 #include "llvm/IR/User.h"
38 #include "llvm/IR/Value.h"
39 #include "llvm/Support/Casting.h"
41 #include "llvm/Support/KnownBits.h"
43 #include <cassert>
44 #include <utility>
45 
46 #define DEBUG_TYPE "instcombine"
48 
49 using namespace llvm;
50 using 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;
61  CmpInst::Predicate Pred;
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.
76  BinaryOperator *BO;
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();
83  Constant *IdC = ConstantExpr::getBinOpIdentity(BO->getOpcode(), Ty, true);
84  if (IdC != C) {
85  if (!IdC || !CmpInst::isFPPredicate(Pred))
86  return nullptr;
87  if (!match(IdC, m_AnyZeroFP()) || !match(C, m_AnyZeroFP()))
88  return nullptr;
89  }
90 
91  // Last, match the compare variable operand with a binop operand.
92  Value *Y;
93  if (!BO->isCommutative() && !match(BO, m_BinOp(m_Value(Y), m_Specific(X))))
94  return nullptr;
95  if (!match(BO, m_c_BinOp(m_Value(Y), m_Specific(X))))
96  return nullptr;
97 
98  // +0.0 compares equal to -0.0, and so it does not behave as required for this
99  // transform. Bail out if we can not exclude that possibility.
100  if (isa<FPMathOperator>(BO))
101  if (!BO->hasNoSignedZeros() && !CannotBeNegativeZero(Y, &TLI))
102  return nullptr;
103 
104  // BO = binop Y, X
105  // S = { select (cmp eq X, C), BO, ? } or { select (cmp ne X, C), ?, BO }
106  // =>
107  // S = { select (cmp eq X, C), Y, ? } or { select (cmp ne X, C), ?, Y }
108  return IC.replaceOperand(Sel, IsEq ? 1 : 2, Y);
109 }
110 
111 /// This folds:
112 /// select (icmp eq (and X, C1)), TC, FC
113 /// iff C1 is a power 2 and the difference between TC and FC is a power-of-2.
114 /// To something like:
115 /// (shr (and (X, C1)), (log2(C1) - log2(TC-FC))) + FC
116 /// Or:
117 /// (shl (and (X, C1)), (log2(TC-FC) - log2(C1))) + FC
118 /// With some variations depending if FC is larger than TC, or the shift
119 /// isn't needed, or the bit widths don't match.
122  const APInt *SelTC, *SelFC;
123  if (!match(Sel.getTrueValue(), m_APInt(SelTC)) ||
124  !match(Sel.getFalseValue(), m_APInt(SelFC)))
125  return nullptr;
126 
127  // If this is a vector select, we need a vector compare.
128  Type *SelType = Sel.getType();
129  if (SelType->isVectorTy() != Cmp->getType()->isVectorTy())
130  return nullptr;
131 
132  Value *V;
133  APInt AndMask;
134  bool CreateAnd = false;
135  ICmpInst::Predicate Pred = Cmp->getPredicate();
136  if (ICmpInst::isEquality(Pred)) {
137  if (!match(Cmp->getOperand(1), m_Zero()))
138  return nullptr;
139 
140  V = Cmp->getOperand(0);
141  const APInt *AndRHS;
142  if (!match(V, m_And(m_Value(), m_Power2(AndRHS))))
143  return nullptr;
144 
145  AndMask = *AndRHS;
146  } else if (decomposeBitTestICmp(Cmp->getOperand(0), Cmp->getOperand(1),
147  Pred, V, AndMask)) {
148  assert(ICmpInst::isEquality(Pred) && "Not equality test?");
149  if (!AndMask.isPowerOf2())
150  return nullptr;
151 
152  CreateAnd = true;
153  } else {
154  return nullptr;
155  }
156 
157  // In general, when both constants are non-zero, we would need an offset to
158  // replace the select. This would require more instructions than we started
159  // with. But there's one special-case that we handle here because it can
160  // simplify/reduce the instructions.
161  APInt TC = *SelTC;
162  APInt FC = *SelFC;
163  if (!TC.isZero() && !FC.isZero()) {
164  // If the select constants differ by exactly one bit and that's the same
165  // bit that is masked and checked by the select condition, the select can
166  // be replaced by bitwise logic to set/clear one bit of the constant result.
167  if (TC.getBitWidth() != AndMask.getBitWidth() || (TC ^ FC) != AndMask)
168  return nullptr;
169  if (CreateAnd) {
170  // If we have to create an 'and', then we must kill the cmp to not
171  // increase the instruction count.
172  if (!Cmp->hasOneUse())
173  return nullptr;
174  V = Builder.CreateAnd(V, ConstantInt::get(SelType, AndMask));
175  }
176  bool ExtraBitInTC = TC.ugt(FC);
177  if (Pred == ICmpInst::ICMP_EQ) {
178  // If the masked bit in V is clear, clear or set the bit in the result:
179  // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) ^ TC
180  // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) | TC
181  Constant *C = ConstantInt::get(SelType, TC);
182  return ExtraBitInTC ? Builder.CreateXor(V, C) : Builder.CreateOr(V, C);
183  }
184  if (Pred == ICmpInst::ICMP_NE) {
185  // If the masked bit in V is set, set or clear the bit in the result:
186  // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) | FC
187  // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) ^ FC
188  Constant *C = ConstantInt::get(SelType, FC);
189  return ExtraBitInTC ? Builder.CreateOr(V, C) : Builder.CreateXor(V, C);
190  }
191  llvm_unreachable("Only expecting equality predicates");
192  }
193 
194  // Make sure one of the select arms is a power-of-2.
195  if (!TC.isPowerOf2() && !FC.isPowerOf2())
196  return nullptr;
197 
198  // Determine which shift is needed to transform result of the 'and' into the
199  // desired result.
200  const APInt &ValC = !TC.isZero() ? TC : FC;
201  unsigned ValZeros = ValC.logBase2();
202  unsigned AndZeros = AndMask.logBase2();
203 
204  // Insert the 'and' instruction on the input to the truncate.
205  if (CreateAnd)
206  V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), AndMask));
207 
208  // If types don't match, we can still convert the select by introducing a zext
209  // or a trunc of the 'and'.
210  if (ValZeros > AndZeros) {
211  V = Builder.CreateZExtOrTrunc(V, SelType);
212  V = Builder.CreateShl(V, ValZeros - AndZeros);
213  } else if (ValZeros < AndZeros) {
214  V = Builder.CreateLShr(V, AndZeros - ValZeros);
215  V = Builder.CreateZExtOrTrunc(V, SelType);
216  } else {
217  V = Builder.CreateZExtOrTrunc(V, SelType);
218  }
219 
220  // Okay, now we know that everything is set up, we just don't know whether we
221  // have a icmp_ne or icmp_eq and whether the true or false val is the zero.
222  bool ShouldNotVal = !TC.isZero();
223  ShouldNotVal ^= Pred == ICmpInst::ICMP_NE;
224  if (ShouldNotVal)
225  V = Builder.CreateXor(V, ValC);
226 
227  return V;
228 }
229 
230 /// We want to turn code that looks like this:
231 /// %C = or %A, %B
232 /// %D = select %cond, %C, %A
233 /// into:
234 /// %C = select %cond, %B, 0
235 /// %D = or %A, %C
236 ///
237 /// Assuming that the specified instruction is an operand to the select, return
238 /// a bitmask indicating which operands of this instruction are foldable if they
239 /// equal the other incoming value of the select.
241  switch (I->getOpcode()) {
242  case Instruction::Add:
243  case Instruction::FAdd:
244  case Instruction::Mul:
245  case Instruction::FMul:
246  case Instruction::And:
247  case Instruction::Or:
248  case Instruction::Xor:
249  return 3; // Can fold through either operand.
250  case Instruction::Sub: // Can only fold on the amount subtracted.
251  case Instruction::FSub:
252  case Instruction::FDiv: // Can only fold on the divisor amount.
253  case Instruction::Shl: // Can only fold on the shift amount.
254  case Instruction::LShr:
255  case Instruction::AShr:
256  return 1;
257  default:
258  return 0; // Cannot fold
259  }
260 }
261 
262 /// We have (select c, TI, FI), and we know that TI and FI have the same opcode.
264  Instruction *FI) {
265  // Don't break up min/max patterns. The hasOneUse checks below prevent that
266  // for most cases, but vector min/max with bitcasts can be transformed. If the
267  // one-use restrictions are eased for other patterns, we still don't want to
268  // obfuscate min/max.
269  if ((match(&SI, m_SMin(m_Value(), m_Value())) ||
270  match(&SI, m_SMax(m_Value(), m_Value())) ||
271  match(&SI, m_UMin(m_Value(), m_Value())) ||
272  match(&SI, m_UMax(m_Value(), m_Value()))))
273  return nullptr;
274 
275  // If this is a cast from the same type, merge.
276  Value *Cond = SI.getCondition();
277  Type *CondTy = Cond->getType();
278  if (TI->getNumOperands() == 1 && TI->isCast()) {
279  Type *FIOpndTy = FI->getOperand(0)->getType();
280  if (TI->getOperand(0)->getType() != FIOpndTy)
281  return nullptr;
282 
283  // The select condition may be a vector. We may only change the operand
284  // type if the vector width remains the same (and matches the condition).
285  if (auto *CondVTy = dyn_cast<VectorType>(CondTy)) {
286  if (!FIOpndTy->isVectorTy() ||
287  CondVTy->getElementCount() !=
288  cast<VectorType>(FIOpndTy)->getElementCount())
289  return nullptr;
290 
291  // TODO: If the backend knew how to deal with casts better, we could
292  // remove this limitation. For now, there's too much potential to create
293  // worse codegen by promoting the select ahead of size-altering casts
294  // (PR28160).
295  //
296  // Note that ValueTracking's matchSelectPattern() looks through casts
297  // without checking 'hasOneUse' when it matches min/max patterns, so this
298  // transform may end up happening anyway.
299  if (TI->getOpcode() != Instruction::BitCast &&
300  (!TI->hasOneUse() || !FI->hasOneUse()))
301  return nullptr;
302  } else if (!TI->hasOneUse() || !FI->hasOneUse()) {
303  // TODO: The one-use restrictions for a scalar select could be eased if
304  // the fold of a select in visitLoadInst() was enhanced to match a pattern
305  // that includes a cast.
306  return nullptr;
307  }
308 
309  // Fold this by inserting a select from the input values.
310  Value *NewSI =
311  Builder.CreateSelect(Cond, TI->getOperand(0), FI->getOperand(0),
312  SI.getName() + ".v", &SI);
313  return CastInst::Create(Instruction::CastOps(TI->getOpcode()), NewSI,
314  TI->getType());
315  }
316 
317  // Cond ? -X : -Y --> -(Cond ? X : Y)
318  Value *X, *Y;
319  if (match(TI, m_FNeg(m_Value(X))) && match(FI, m_FNeg(m_Value(Y))) &&
320  (TI->hasOneUse() || FI->hasOneUse())) {
321  // Intersect FMF from the fneg instructions and union those with the select.
322  FastMathFlags FMF = TI->getFastMathFlags();
323  FMF &= FI->getFastMathFlags();
324  FMF |= SI.getFastMathFlags();
325  Value *NewSel = Builder.CreateSelect(Cond, X, Y, SI.getName() + ".v", &SI);
326  if (auto *NewSelI = dyn_cast<Instruction>(NewSel))
327  NewSelI->setFastMathFlags(FMF);
328  Instruction *NewFNeg = UnaryOperator::CreateFNeg(NewSel);
329  NewFNeg->setFastMathFlags(FMF);
330  return NewFNeg;
331  }
332 
333  // Min/max intrinsic with a common operand can have the common operand pulled
334  // after the select. This is the same transform as below for binops, but
335  // specialized for intrinsic matching and without the restrictive uses clause.
336  auto *TII = dyn_cast<IntrinsicInst>(TI);
337  auto *FII = dyn_cast<IntrinsicInst>(FI);
338  if (TII && FII && TII->getIntrinsicID() == FII->getIntrinsicID() &&
339  (TII->hasOneUse() || FII->hasOneUse())) {
340  Value *T0, *T1, *F0, *F1;
341  if (match(TII, m_MaxOrMin(m_Value(T0), m_Value(T1))) &&
342  match(FII, m_MaxOrMin(m_Value(F0), m_Value(F1)))) {
343  if (T0 == F0) {
344  Value *NewSel = Builder.CreateSelect(Cond, T1, F1, "minmaxop", &SI);
345  return CallInst::Create(TII->getCalledFunction(), {NewSel, T0});
346  }
347  if (T0 == F1) {
348  Value *NewSel = Builder.CreateSelect(Cond, T1, F0, "minmaxop", &SI);
349  return CallInst::Create(TII->getCalledFunction(), {NewSel, T0});
350  }
351  if (T1 == F0) {
352  Value *NewSel = Builder.CreateSelect(Cond, T0, F1, "minmaxop", &SI);
353  return CallInst::Create(TII->getCalledFunction(), {NewSel, T1});
354  }
355  if (T1 == F1) {
356  Value *NewSel = Builder.CreateSelect(Cond, T0, F0, "minmaxop", &SI);
357  return CallInst::Create(TII->getCalledFunction(), {NewSel, T1});
358  }
359  }
360  }
361 
362  // Only handle binary operators (including two-operand getelementptr) with
363  // one-use here. As with the cast case above, it may be possible to relax the
364  // one-use constraint, but that needs be examined carefully since it may not
365  // reduce the total number of instructions.
366  if (TI->getNumOperands() != 2 || FI->getNumOperands() != 2 ||
367  !TI->isSameOperationAs(FI) ||
368  (!isa<BinaryOperator>(TI) && !isa<GetElementPtrInst>(TI)) ||
369  !TI->hasOneUse() || !FI->hasOneUse())
370  return nullptr;
371 
372  // Figure out if the operations have any operands in common.
373  Value *MatchOp, *OtherOpT, *OtherOpF;
374  bool MatchIsOpZero;
375  if (TI->getOperand(0) == FI->getOperand(0)) {
376  MatchOp = TI->getOperand(0);
377  OtherOpT = TI->getOperand(1);
378  OtherOpF = FI->getOperand(1);
379  MatchIsOpZero = true;
380  } else if (TI->getOperand(1) == FI->getOperand(1)) {
381  MatchOp = TI->getOperand(1);
382  OtherOpT = TI->getOperand(0);
383  OtherOpF = FI->getOperand(0);
384  MatchIsOpZero = false;
385  } else if (!TI->isCommutative()) {
386  return nullptr;
387  } else if (TI->getOperand(0) == FI->getOperand(1)) {
388  MatchOp = TI->getOperand(0);
389  OtherOpT = TI->getOperand(1);
390  OtherOpF = FI->getOperand(0);
391  MatchIsOpZero = true;
392  } else if (TI->getOperand(1) == FI->getOperand(0)) {
393  MatchOp = TI->getOperand(1);
394  OtherOpT = TI->getOperand(0);
395  OtherOpF = FI->getOperand(1);
396  MatchIsOpZero = true;
397  } else {
398  return nullptr;
399  }
400 
401  // If the select condition is a vector, the operands of the original select's
402  // operands also must be vectors. This may not be the case for getelementptr
403  // for example.
404  if (CondTy->isVectorTy() && (!OtherOpT->getType()->isVectorTy() ||
405  !OtherOpF->getType()->isVectorTy()))
406  return nullptr;
407 
408  // If we reach here, they do have operations in common.
409  Value *NewSI = Builder.CreateSelect(Cond, OtherOpT, OtherOpF,
410  SI.getName() + ".v", &SI);
411  Value *Op0 = MatchIsOpZero ? MatchOp : NewSI;
412  Value *Op1 = MatchIsOpZero ? NewSI : MatchOp;
413  if (auto *BO = dyn_cast<BinaryOperator>(TI)) {
414  BinaryOperator *NewBO = BinaryOperator::Create(BO->getOpcode(), Op0, Op1);
415  NewBO->copyIRFlags(TI);
416  NewBO->andIRFlags(FI);
417  return NewBO;
418  }
419  if (auto *TGEP = dyn_cast<GetElementPtrInst>(TI)) {
420  auto *FGEP = cast<GetElementPtrInst>(FI);
421  Type *ElementType = TGEP->getResultElementType();
422  return TGEP->isInBounds() && FGEP->isInBounds()
423  ? GetElementPtrInst::CreateInBounds(ElementType, Op0, {Op1})
424  : GetElementPtrInst::Create(ElementType, Op0, {Op1});
425  }
426  llvm_unreachable("Expected BinaryOperator or GEP");
427  return nullptr;
428 }
429 
430 static bool isSelect01(const APInt &C1I, const APInt &C2I) {
431  if (!C1I.isZero() && !C2I.isZero()) // One side must be zero.
432  return false;
433  return C1I.isOne() || C1I.isAllOnes() || C2I.isOne() || C2I.isAllOnes();
434 }
435 
436 /// Try to fold the select into one of the operands to allow further
437 /// optimization.
439  Value *FalseVal) {
440  // See the comment above GetSelectFoldableOperands for a description of the
441  // transformation we are doing here.
442  auto TryFoldSelectIntoOp = [&](SelectInst &SI, Value *TrueVal,
443  Value *FalseVal,
444  bool Swapped) -> Instruction * {
445  if (auto *TVI = dyn_cast<BinaryOperator>(TrueVal)) {
446  if (TVI->hasOneUse() && !isa<Constant>(FalseVal)) {
447  if (unsigned SFO = getSelectFoldableOperands(TVI)) {
448  unsigned OpToFold = 0;
449  if ((SFO & 1) && FalseVal == TVI->getOperand(0))
450  OpToFold = 1;
451  else if ((SFO & 2) && FalseVal == TVI->getOperand(1))
452  OpToFold = 2;
453 
454  if (OpToFold) {
455  FastMathFlags FMF;
456  // TODO: We probably ought to revisit cases where the select and FP
457  // instructions have different flags and add tests to ensure the
458  // behaviour is correct.
459  if (isa<FPMathOperator>(&SI))
460  FMF = SI.getFastMathFlags();
462  TVI->getOpcode(), TVI->getType(), true, FMF.noSignedZeros());
463  Value *OOp = TVI->getOperand(2 - OpToFold);
464  // Avoid creating select between 2 constants unless it's selecting
465  // between 0, 1 and -1.
466  const APInt *OOpC;
467  bool OOpIsAPInt = match(OOp, m_APInt(OOpC));
468  if (!isa<Constant>(OOp) ||
469  (OOpIsAPInt && isSelect01(C->getUniqueInteger(), *OOpC))) {
470  Value *NewSel = Builder.CreateSelect(
471  SI.getCondition(), Swapped ? C : OOp, Swapped ? OOp : C);
472  if (isa<FPMathOperator>(&SI))
473  cast<Instruction>(NewSel)->setFastMathFlags(FMF);
474  NewSel->takeName(TVI);
475  BinaryOperator *BO =
476  BinaryOperator::Create(TVI->getOpcode(), FalseVal, NewSel);
477  BO->copyIRFlags(TVI);
478  return BO;
479  }
480  }
481  }
482  }
483  }
484  return nullptr;
485  };
486 
487  if (Instruction *R = TryFoldSelectIntoOp(SI, TrueVal, FalseVal, false))
488  return R;
489 
490  if (Instruction *R = TryFoldSelectIntoOp(SI, FalseVal, TrueVal, true))
491  return R;
492 
493  return nullptr;
494 }
495 
496 /// We want to turn:
497 /// (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1)
498 /// into:
499 /// zext (icmp ne i32 (and X, (or Y, (shl 1, Z))), 0)
500 /// Note:
501 /// Z may be 0 if lshr is missing.
502 /// Worst-case scenario is that we will replace 5 instructions with 5 different
503 /// instructions, but we got rid of select.
504 static Instruction *foldSelectICmpAndAnd(Type *SelType, const ICmpInst *Cmp,
505  Value *TVal, Value *FVal,
507  if (!(Cmp->hasOneUse() && Cmp->getOperand(0)->hasOneUse() &&
508  Cmp->getPredicate() == ICmpInst::ICMP_EQ &&
509  match(Cmp->getOperand(1), m_Zero()) && match(FVal, m_One())))
510  return nullptr;
511 
512  // The TrueVal has general form of: and %B, 1
513  Value *B;
514  if (!match(TVal, m_OneUse(m_And(m_Value(B), m_One()))))
515  return nullptr;
516 
517  // Where %B may be optionally shifted: lshr %X, %Z.
518  Value *X, *Z;
519  const bool HasShift = match(B, m_OneUse(m_LShr(m_Value(X), m_Value(Z))));
520 
521  // The shift must be valid.
522  // TODO: This restricts the fold to constant shift amounts. Is there a way to
523  // handle variable shifts safely? PR47012
524  if (HasShift &&
526  APInt(SelType->getScalarSizeInBits(),
527  SelType->getScalarSizeInBits()))))
528  return nullptr;
529 
530  if (!HasShift)
531  X = B;
532 
533  Value *Y;
534  if (!match(Cmp->getOperand(0), m_c_And(m_Specific(X), m_Value(Y))))
535  return nullptr;
536 
537  // ((X & Y) == 0) ? ((X >> Z) & 1) : 1 --> (X & (Y | (1 << Z))) != 0
538  // ((X & Y) == 0) ? (X & 1) : 1 --> (X & (Y | 1)) != 0
539  Constant *One = ConstantInt::get(SelType, 1);
540  Value *MaskB = HasShift ? Builder.CreateShl(One, Z) : One;
541  Value *FullMask = Builder.CreateOr(Y, MaskB);
542  Value *MaskedX = Builder.CreateAnd(X, FullMask);
543  Value *ICmpNeZero = Builder.CreateIsNotNull(MaskedX);
544  return new ZExtInst(ICmpNeZero, SelType);
545 }
546 
547 /// We want to turn:
548 /// (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1
549 /// (select (icmp slt x, C), ashr (X, Y), lshr (X, Y)); iff C s>= 0
550 /// into:
551 /// ashr (X, Y)
553  Value *FalseVal,
555  ICmpInst::Predicate Pred = IC->getPredicate();
556  Value *CmpLHS = IC->getOperand(0);
557  Value *CmpRHS = IC->getOperand(1);
558  if (!CmpRHS->getType()->isIntOrIntVectorTy())
559  return nullptr;
560 
561  Value *X, *Y;
562  unsigned Bitwidth = CmpRHS->getType()->getScalarSizeInBits();
563  if ((Pred != ICmpInst::ICMP_SGT ||
564  !match(CmpRHS,
565  m_SpecificInt_ICMP(ICmpInst::ICMP_SGE, APInt(Bitwidth, -1)))) &&
566  (Pred != ICmpInst::ICMP_SLT ||
567  !match(CmpRHS,
569  return nullptr;
570 
571  // Canonicalize so that ashr is in FalseVal.
572  if (Pred == ICmpInst::ICMP_SLT)
574 
575  if (match(TrueVal, m_LShr(m_Value(X), m_Value(Y))) &&
577  match(CmpLHS, m_Specific(X))) {
578  const auto *Ashr = cast<Instruction>(FalseVal);
579  // if lshr is not exact and ashr is, this new ashr must not be exact.
580  bool IsExact = Ashr->isExact() && cast<Instruction>(TrueVal)->isExact();
581  return Builder.CreateAShr(X, Y, IC->getName(), IsExact);
582  }
583 
584  return nullptr;
585 }
586 
587 /// We want to turn:
588 /// (select (icmp eq (and X, C1), 0), Y, (or Y, C2))
589 /// into:
590 /// (or (shl (and X, C1), C3), Y)
591 /// iff:
592 /// C1 and C2 are both powers of 2
593 /// where:
594 /// C3 = Log(C2) - Log(C1)
595 ///
596 /// This transform handles cases where:
597 /// 1. The icmp predicate is inverted
598 /// 2. The select operands are reversed
599 /// 3. The magnitude of C2 and C1 are flipped
601  Value *FalseVal,
603  // Only handle integer compares. Also, if this is a vector select, we need a
604  // vector compare.
605  if (!TrueVal->getType()->isIntOrIntVectorTy() ||
606  TrueVal->getType()->isVectorTy() != IC->getType()->isVectorTy())
607  return nullptr;
608 
609  Value *CmpLHS = IC->getOperand(0);
610  Value *CmpRHS = IC->getOperand(1);
611 
612  Value *V;
613  unsigned C1Log;
614  bool IsEqualZero;
615  bool NeedAnd = false;
616  if (IC->isEquality()) {
617  if (!match(CmpRHS, m_Zero()))
618  return nullptr;
619 
620  const APInt *C1;
621  if (!match(CmpLHS, m_And(m_Value(), m_Power2(C1))))
622  return nullptr;
623 
624  V = CmpLHS;
625  C1Log = C1->logBase2();
626  IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_EQ;
627  } else if (IC->getPredicate() == ICmpInst::ICMP_SLT ||
628  IC->getPredicate() == ICmpInst::ICMP_SGT) {
629  // We also need to recognize (icmp slt (trunc (X)), 0) and
630  // (icmp sgt (trunc (X)), -1).
631  IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_SGT;
632  if ((IsEqualZero && !match(CmpRHS, m_AllOnes())) ||
633  (!IsEqualZero && !match(CmpRHS, m_Zero())))
634  return nullptr;
635 
636  if (!match(CmpLHS, m_OneUse(m_Trunc(m_Value(V)))))
637  return nullptr;
638 
639  C1Log = CmpLHS->getType()->getScalarSizeInBits() - 1;
640  NeedAnd = true;
641  } else {
642  return nullptr;
643  }
644 
645  const APInt *C2;
646  bool OrOnTrueVal = false;
647  bool OrOnFalseVal = match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2)));
648  if (!OrOnFalseVal)
649  OrOnTrueVal = match(TrueVal, m_Or(m_Specific(FalseVal), m_Power2(C2)));
650 
651  if (!OrOnFalseVal && !OrOnTrueVal)
652  return nullptr;
653 
654  Value *Y = OrOnFalseVal ? TrueVal : FalseVal;
655 
656  unsigned C2Log = C2->logBase2();
657 
658  bool NeedXor = (!IsEqualZero && OrOnFalseVal) || (IsEqualZero && OrOnTrueVal);
659  bool NeedShift = C1Log != C2Log;
660  bool NeedZExtTrunc = Y->getType()->getScalarSizeInBits() !=
662 
663  // Make sure we don't create more instructions than we save.
664  Value *Or = OrOnFalseVal ? FalseVal : TrueVal;
665  if ((NeedShift + NeedXor + NeedZExtTrunc) >
666  (IC->hasOneUse() + Or->hasOneUse()))
667  return nullptr;
668 
669  if (NeedAnd) {
670  // Insert the AND instruction on the input to the truncate.
672  V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), C1));
673  }
674 
675  if (C2Log > C1Log) {
676  V = Builder.CreateZExtOrTrunc(V, Y->getType());
677  V = Builder.CreateShl(V, C2Log - C1Log);
678  } else if (C1Log > C2Log) {
679  V = Builder.CreateLShr(V, C1Log - C2Log);
680  V = Builder.CreateZExtOrTrunc(V, Y->getType());
681  } else
682  V = Builder.CreateZExtOrTrunc(V, Y->getType());
683 
684  if (NeedXor)
685  V = Builder.CreateXor(V, *C2);
686 
687  return Builder.CreateOr(V, Y);
688 }
689 
690 /// Canonicalize a set or clear of a masked set of constant bits to
691 /// select-of-constants form.
694  Value *Cond = Sel.getCondition();
695  Value *T = Sel.getTrueValue();
696  Value *F = Sel.getFalseValue();
697  Type *Ty = Sel.getType();
698  Value *X;
699  const APInt *NotC, *C;
700 
701  // Cond ? (X & ~C) : (X | C) --> (X & ~C) | (Cond ? 0 : C)
702  if (match(T, m_And(m_Value(X), m_APInt(NotC))) &&
703  match(F, m_OneUse(m_Or(m_Specific(X), m_APInt(C)))) && *NotC == ~(*C)) {
705  Constant *OrC = ConstantInt::get(Ty, *C);
706  Value *NewSel = Builder.CreateSelect(Cond, Zero, OrC, "masksel", &Sel);
707  return BinaryOperator::CreateOr(T, NewSel);
708  }
709 
710  // Cond ? (X | C) : (X & ~C) --> (X & ~C) | (Cond ? C : 0)
711  if (match(F, m_And(m_Value(X), m_APInt(NotC))) &&
712  match(T, m_OneUse(m_Or(m_Specific(X), m_APInt(C)))) && *NotC == ~(*C)) {
714  Constant *OrC = ConstantInt::get(Ty, *C);
715  Value *NewSel = Builder.CreateSelect(Cond, OrC, Zero, "masksel", &Sel);
716  return BinaryOperator::CreateOr(F, NewSel);
717  }
718 
719  return nullptr;
720 }
721 
722 // select (x == 0), 0, x * y --> freeze(y) * x
723 // select (y == 0), 0, x * y --> freeze(x) * y
724 // select (x == 0), undef, x * y --> freeze(y) * x
725 // select (x == undef), 0, x * y --> freeze(y) * x
726 // Usage of mul instead of 0 will make the result more poisonous,
727 // so the operand that was not checked in the condition should be frozen.
728 // The latter folding is applied only when a constant compared with x is
729 // is a vector consisting of 0 and undefs. If a constant compared with x
730 // is a scalar undefined value or undefined vector then an expression
731 // should be already folded into a constant.
733  auto *CondVal = SI.getCondition();
734  auto *TrueVal = SI.getTrueValue();
735  auto *FalseVal = SI.getFalseValue();
736  Value *X, *Y;
738 
739  // Assuming that constant compared with zero is not undef (but it may be
740  // a vector with some undef elements). Otherwise (when a constant is undef)
741  // the select expression should be already simplified.
742  if (!match(CondVal, m_ICmp(Predicate, m_Value(X), m_Zero())) ||
744  return nullptr;
745 
748 
749  // Check that TrueVal is a constant instead of matching it with m_Zero()
750  // to handle the case when it is a scalar undef value or a vector containing
751  // non-zero elements that are masked by undef elements in the compare
752  // constant.
753  auto *TrueValC = dyn_cast<Constant>(TrueVal);
754  if (TrueValC == nullptr ||
756  !isa<Instruction>(FalseVal))
757  return nullptr;
758 
759  auto *ZeroC = cast<Constant>(cast<Instruction>(CondVal)->getOperand(1));
760  auto *MergedC = Constant::mergeUndefsWith(TrueValC, ZeroC);
761  // If X is compared with 0 then TrueVal could be either zero or undef.
762  // m_Zero match vectors containing some undef elements, but for scalars
763  // m_Undef should be used explicitly.
764  if (!match(MergedC, m_Zero()) && !match(MergedC, m_Undef()))
765  return nullptr;
766 
767  auto *FalseValI = cast<Instruction>(FalseVal);
768  auto *FrY = IC.InsertNewInstBefore(new FreezeInst(Y, Y->getName() + ".fr"),
769  *FalseValI);
770  IC.replaceOperand(*FalseValI, FalseValI->getOperand(0) == Y ? 0 : 1, FrY);
771  return IC.replaceInstUsesWith(SI, FalseValI);
772 }
773 
774 /// Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b).
775 /// There are 8 commuted/swapped variants of this pattern.
776 /// TODO: Also support a - UMIN(a,b) patterns.
778  const Value *TrueVal,
779  const Value *FalseVal,
781  ICmpInst::Predicate Pred = ICI->getPredicate();
782  if (!ICmpInst::isUnsigned(Pred))
783  return nullptr;
784 
785  // (b > a) ? 0 : a - b -> (b <= a) ? a - b : 0
786  if (match(TrueVal, m_Zero())) {
787  Pred = ICmpInst::getInversePredicate(Pred);
789  }
790  if (!match(FalseVal, m_Zero()))
791  return nullptr;
792 
793  Value *A = ICI->getOperand(0);
794  Value *B = ICI->getOperand(1);
795  if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_ULT) {
796  // (b < a) ? a - b : 0 -> (a > b) ? a - b : 0
797  std::swap(A, B);
798  Pred = ICmpInst::getSwappedPredicate(Pred);
799  }
800 
801  assert((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_UGT) &&
802  "Unexpected isUnsigned predicate!");
803 
804  // Ensure the sub is of the form:
805  // (a > b) ? a - b : 0 -> usub.sat(a, b)
806  // (a > b) ? b - a : 0 -> -usub.sat(a, b)
807  // Checking for both a-b and a+(-b) as a constant.
808  bool IsNegative = false;
809  const APInt *C;
810  if (match(TrueVal, m_Sub(m_Specific(B), m_Specific(A))) ||
811  (match(A, m_APInt(C)) &&
813  IsNegative = true;
814  else if (!match(TrueVal, m_Sub(m_Specific(A), m_Specific(B))) &&
815  !(match(B, m_APInt(C)) &&
817  return nullptr;
818 
819  // If we are adding a negate and the sub and icmp are used anywhere else, we
820  // would end up with more instructions.
821  if (IsNegative && !TrueVal->hasOneUse() && !ICI->hasOneUse())
822  return nullptr;
823 
824  // (a > b) ? a - b : 0 -> usub.sat(a, b)
825  // (a > b) ? b - a : 0 -> -usub.sat(a, b)
826  Value *Result = Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, A, B);
827  if (IsNegative)
828  Result = Builder.CreateNeg(Result);
829  return Result;
830 }
831 
832 static Value *canonicalizeSaturatedAdd(ICmpInst *Cmp, Value *TVal, Value *FVal,
834  if (!Cmp->hasOneUse())
835  return nullptr;
836 
837  // Match unsigned saturated add with constant.
838  Value *Cmp0 = Cmp->getOperand(0);
839  Value *Cmp1 = Cmp->getOperand(1);
840  ICmpInst::Predicate Pred = Cmp->getPredicate();
841  Value *X;
842  const APInt *C, *CmpC;
843  if (Pred == ICmpInst::ICMP_ULT &&
844  match(TVal, m_Add(m_Value(X), m_APInt(C))) && X == Cmp0 &&
845  match(FVal, m_AllOnes()) && match(Cmp1, m_APInt(CmpC)) && *CmpC == ~*C) {
846  // (X u< ~C) ? (X + C) : -1 --> uadd.sat(X, C)
847  return Builder.CreateBinaryIntrinsic(
848  Intrinsic::uadd_sat, X, ConstantInt::get(X->getType(), *C));
849  }
850 
851  // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
852  // There are 8 commuted variants.
853  // Canonicalize -1 (saturated result) to true value of the select.
854  if (match(FVal, m_AllOnes())) {
855  std::swap(TVal, FVal);
856  Pred = CmpInst::getInversePredicate(Pred);
857  }
858  if (!match(TVal, m_AllOnes()))
859  return nullptr;
860 
861  // Canonicalize predicate to less-than or less-or-equal-than.
862  if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) {
863  std::swap(Cmp0, Cmp1);
864  Pred = CmpInst::getSwappedPredicate(Pred);
865  }
866  if (Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_ULE)
867  return nullptr;
868 
869  // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
870  // Strictness of the comparison is irrelevant.
871  Value *Y;
872  if (match(Cmp0, m_Not(m_Value(X))) &&
873  match(FVal, m_c_Add(m_Specific(X), m_Value(Y))) && Y == Cmp1) {
874  // (~X u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
875  // (~X u< Y) ? -1 : (Y + X) --> uadd.sat(X, Y)
876  return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, X, Y);
877  }
878  // The 'not' op may be included in the sum but not the compare.
879  // Strictness of the comparison is irrelevant.
880  X = Cmp0;
881  Y = Cmp1;
882  if (match(FVal, m_c_Add(m_Not(m_Specific(X)), m_Specific(Y)))) {
883  // (X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y)
884  // (X u< Y) ? -1 : (Y + ~X) --> uadd.sat(Y, ~X)
885  BinaryOperator *BO = cast<BinaryOperator>(FVal);
886  return Builder.CreateBinaryIntrinsic(
887  Intrinsic::uadd_sat, BO->getOperand(0), BO->getOperand(1));
888  }
889  // The overflow may be detected via the add wrapping round.
890  // This is only valid for strict comparison!
891  if (Pred == ICmpInst::ICMP_ULT &&
892  match(Cmp0, m_c_Add(m_Specific(Cmp1), m_Value(Y))) &&
893  match(FVal, m_c_Add(m_Specific(Cmp1), m_Specific(Y)))) {
894  // ((X + Y) u< X) ? -1 : (X + Y) --> uadd.sat(X, Y)
895  // ((X + Y) u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
896  return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, Cmp1, Y);
897  }
898 
899  return nullptr;
900 }
901 
902 /// Fold the following code sequence:
903 /// \code
904 /// int a = ctlz(x & -x);
905 // x ? 31 - a : a;
906 /// \code
907 ///
908 /// into:
909 /// cttz(x)
910 static Instruction *foldSelectCtlzToCttz(ICmpInst *ICI, Value *TrueVal,
911  Value *FalseVal,
913  unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits();
914  if (!ICI->isEquality() || !match(ICI->getOperand(1), m_Zero()))
915  return nullptr;
916 
917  if (ICI->getPredicate() == ICmpInst::ICMP_NE)
919 
920  if (!match(FalseVal,
922  return nullptr;
923 
924  if (!match(TrueVal, m_Intrinsic<Intrinsic::ctlz>()))
925  return nullptr;
926 
927  Value *X = ICI->getOperand(0);
928  auto *II = cast<IntrinsicInst>(TrueVal);
929  if (!match(II->getOperand(0), m_c_And(m_Specific(X), m_Neg(m_Specific(X)))))
930  return nullptr;
931 
932  Function *F = Intrinsic::getDeclaration(II->getModule(), Intrinsic::cttz,
933  II->getType());
934  return CallInst::Create(F, {X, II->getArgOperand(1)});
935 }
936 
937 /// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single
938 /// call to cttz/ctlz with flag 'is_zero_poison' cleared.
939 ///
940 /// For example, we can fold the following code sequence:
941 /// \code
942 /// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
943 /// %1 = icmp ne i32 %x, 0
944 /// %2 = select i1 %1, i32 %0, i32 32
945 /// \code
946 ///
947 /// into:
948 /// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
949 static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal,
951  ICmpInst::Predicate Pred = ICI->getPredicate();
952  Value *CmpLHS = ICI->getOperand(0);
953  Value *CmpRHS = ICI->getOperand(1);
954 
955  // Check if the select condition compares a value for equality.
956  if (!ICI->isEquality())
957  return nullptr;
958 
959  Value *SelectArg = FalseVal;
960  Value *ValueOnZero = TrueVal;
961  if (Pred == ICmpInst::ICMP_NE)
962  std::swap(SelectArg, ValueOnZero);
963 
964  // Skip zero extend/truncate.
965  Value *Count = nullptr;
966  if (!match(SelectArg, m_ZExt(m_Value(Count))) &&
967  !match(SelectArg, m_Trunc(m_Value(Count))))
968  Count = SelectArg;
969 
970  // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the
971  // input to the cttz/ctlz is used as LHS for the compare instruction.
972  Value *X;
973  if (!match(Count, m_Intrinsic<Intrinsic::cttz>(m_Value(X))) &&
974  !match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Value(X))))
975  return nullptr;
976 
977  // (X == 0) ? BitWidth : ctz(X)
978  // (X == -1) ? BitWidth : ctz(~X)
979  if ((X != CmpLHS || !match(CmpRHS, m_Zero())) &&
980  (!match(X, m_Not(m_Specific(CmpLHS))) || !match(CmpRHS, m_AllOnes())))
981  return nullptr;
982 
983  IntrinsicInst *II = cast<IntrinsicInst>(Count);
984 
985  // Check if the value propagated on zero is a constant number equal to the
986  // sizeof in bits of 'Count'.
987  unsigned SizeOfInBits = Count->getType()->getScalarSizeInBits();
988  if (match(ValueOnZero, m_SpecificInt(SizeOfInBits))) {
989  // Explicitly clear the 'is_zero_poison' flag. It's always valid to go from
990  // true to false on this flag, so we can replace it for all users.
992  return SelectArg;
993  }
994 
995  // The ValueOnZero is not the bitwidth. But if the cttz/ctlz (and optional
996  // zext/trunc) have one use (ending at the select), the cttz/ctlz result will
997  // not be used if the input is zero. Relax to 'zero is poison' for that case.
998  if (II->hasOneUse() && SelectArg->hasOneUse() &&
999  !match(II->getArgOperand(1), m_One()))
1001 
1002  return nullptr;
1003 }
1004 
1005 /// Return true if we find and adjust an icmp+select pattern where the compare
1006 /// is with a constant that can be incremented or decremented to match the
1007 /// minimum or maximum idiom.
1008 static bool adjustMinMax(SelectInst &Sel, ICmpInst &Cmp) {
1009  ICmpInst::Predicate Pred = Cmp.getPredicate();
1010  Value *CmpLHS = Cmp.getOperand(0);
1011  Value *CmpRHS = Cmp.getOperand(1);
1012  Value *TrueVal = Sel.getTrueValue();
1013  Value *FalseVal = Sel.getFalseValue();
1014 
1015  // We may move or edit the compare, so make sure the select is the only user.
1016  const APInt *CmpC;
1017  if (!Cmp.hasOneUse() || !match(CmpRHS, m_APInt(CmpC)))
1018  return false;
1019 
1020  // These transforms only work for selects of integers or vector selects of
1021  // integer vectors.
1022  Type *SelTy = Sel.getType();
1023  auto *SelEltTy = dyn_cast<IntegerType>(SelTy->getScalarType());
1024  if (!SelEltTy || SelTy->isVectorTy() != Cmp.getType()->isVectorTy())
1025  return false;
1026 
1027  Constant *AdjustedRHS;
1028  if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_SGT)
1029  AdjustedRHS = ConstantInt::get(CmpRHS->getType(), *CmpC + 1);
1030  else if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_SLT)
1031  AdjustedRHS = ConstantInt::get(CmpRHS->getType(), *CmpC - 1);
1032  else
1033  return false;
1034 
1035  // X > C ? X : C+1 --> X < C+1 ? C+1 : X
1036  // X < C ? X : C-1 --> X > C-1 ? C-1 : X
1037  if ((CmpLHS == TrueVal && AdjustedRHS == FalseVal) ||
1038  (CmpLHS == FalseVal && AdjustedRHS == TrueVal)) {
1039  ; // Nothing to do here. Values match without any sign/zero extension.
1040  }
1041  // Types do not match. Instead of calculating this with mixed types, promote
1042  // all to the larger type. This enables scalar evolution to analyze this
1043  // expression.
1044  else if (CmpRHS->getType()->getScalarSizeInBits() < SelEltTy->getBitWidth()) {
1045  Constant *SextRHS = ConstantExpr::getSExt(AdjustedRHS, SelTy);
1046 
1047  // X = sext x; x >s c ? X : C+1 --> X = sext x; X <s C+1 ? C+1 : X
1048  // X = sext x; x <s c ? X : C-1 --> X = sext x; X >s C-1 ? C-1 : X
1049  // X = sext x; x >u c ? X : C+1 --> X = sext x; X <u C+1 ? C+1 : X
1050  // X = sext x; x <u c ? X : C-1 --> X = sext x; X >u C-1 ? C-1 : X
1051  if (match(TrueVal, m_SExt(m_Specific(CmpLHS))) && SextRHS == FalseVal) {
1052  CmpLHS = TrueVal;
1053  AdjustedRHS = SextRHS;
1054  } else if (match(FalseVal, m_SExt(m_Specific(CmpLHS))) &&
1055  SextRHS == TrueVal) {
1056  CmpLHS = FalseVal;
1057  AdjustedRHS = SextRHS;
1058  } else if (Cmp.isUnsigned()) {
1059  Constant *ZextRHS = ConstantExpr::getZExt(AdjustedRHS, SelTy);
1060  // X = zext x; x >u c ? X : C+1 --> X = zext x; X <u C+1 ? C+1 : X
1061  // X = zext x; x <u c ? X : C-1 --> X = zext x; X >u C-1 ? C-1 : X
1062  // zext + signed compare cannot be changed:
1063  // 0xff <s 0x00, but 0x00ff >s 0x0000
1064  if (match(TrueVal, m_ZExt(m_Specific(CmpLHS))) && ZextRHS == FalseVal) {
1065  CmpLHS = TrueVal;
1066  AdjustedRHS = ZextRHS;
1067  } else if (match(FalseVal, m_ZExt(m_Specific(CmpLHS))) &&
1068  ZextRHS == TrueVal) {
1069  CmpLHS = FalseVal;
1070  AdjustedRHS = ZextRHS;
1071  } else {
1072  return false;
1073  }
1074  } else {
1075  return false;
1076  }
1077  } else {
1078  return false;
1079  }
1080 
1081  Pred = ICmpInst::getSwappedPredicate(Pred);
1082  CmpRHS = AdjustedRHS;
1084  Cmp.setPredicate(Pred);
1085  Cmp.setOperand(0, CmpLHS);
1086  Cmp.setOperand(1, CmpRHS);
1087  Sel.setOperand(1, TrueVal);
1088  Sel.setOperand(2, FalseVal);
1089  Sel.swapProfMetadata();
1090 
1091  // Move the compare instruction right before the select instruction. Otherwise
1092  // the sext/zext value may be defined after the compare instruction uses it.
1093  Cmp.moveBefore(&Sel);
1094 
1095  return true;
1096 }
1097 
1098 static Instruction *canonicalizeSPF(SelectInst &Sel, ICmpInst &Cmp,
1099  InstCombinerImpl &IC) {
1100  Value *LHS, *RHS;
1101  // TODO: What to do with pointer min/max patterns?
1102  if (!Sel.getType()->isIntOrIntVectorTy())
1103  return nullptr;
1104 
1106  if (SPF == SelectPatternFlavor::SPF_ABS ||
1108  if (!Cmp.hasOneUse() && !RHS->hasOneUse())
1109  return nullptr; // TODO: Relax this restriction.
1110 
1111  // Note that NSW flag can only be propagated for normal, non-negated abs!
1112  bool IntMinIsPoison = SPF == SelectPatternFlavor::SPF_ABS &&
1114  Constant *IntMinIsPoisonC =
1115  ConstantInt::get(Type::getInt1Ty(Sel.getContext()), IntMinIsPoison);
1116  Instruction *Abs =
1117  IC.Builder.CreateBinaryIntrinsic(Intrinsic::abs, LHS, IntMinIsPoisonC);
1118 
1119  if (SPF == SelectPatternFlavor::SPF_NABS)
1120  return BinaryOperator::CreateNeg(Abs); // Always without NSW flag!
1121  return IC.replaceInstUsesWith(Sel, Abs);
1122  }
1123 
1125  Intrinsic::ID IntrinsicID;
1126  switch (SPF) {
1128  IntrinsicID = Intrinsic::umin;
1129  break;
1131  IntrinsicID = Intrinsic::umax;
1132  break;
1134  IntrinsicID = Intrinsic::smin;
1135  break;
1137  IntrinsicID = Intrinsic::smax;
1138  break;
1139  default:
1140  llvm_unreachable("Unexpected SPF");
1141  }
1142  return IC.replaceInstUsesWith(
1143  Sel, IC.Builder.CreateBinaryIntrinsic(IntrinsicID, LHS, RHS));
1144  }
1145 
1146  return nullptr;
1147 }
1148 
1149 /// If we have a select with an equality comparison, then we know the value in
1150 /// one of the arms of the select. See if substituting this value into an arm
1151 /// and simplifying the result yields the same value as the other arm.
1152 ///
1153 /// To make this transform safe, we must drop poison-generating flags
1154 /// (nsw, etc) if we simplified to a binop because the select may be guarding
1155 /// that poison from propagating. If the existing binop already had no
1156 /// poison-generating flags, then this transform can be done by instsimplify.
1157 ///
1158 /// Consider:
1159 /// %cmp = icmp eq i32 %x, 2147483647
1160 /// %add = add nsw i32 %x, 1
1161 /// %sel = select i1 %cmp, i32 -2147483648, i32 %add
1162 ///
1163 /// We can't replace %sel with %add unless we strip away the flags.
1164 /// TODO: Wrapping flags could be preserved in some cases with better analysis.
1166  ICmpInst &Cmp) {
1167  if (!Cmp.isEquality())
1168  return nullptr;
1169 
1170  // Canonicalize the pattern to ICMP_EQ by swapping the select operands.
1171  Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
1172  bool Swapped = false;
1173  if (Cmp.getPredicate() == ICmpInst::ICMP_NE) {
1175  Swapped = true;
1176  }
1177 
1178  // In X == Y ? f(X) : Z, try to evaluate f(Y) and replace the operand.
1179  // Make sure Y cannot be undef though, as we might pick different values for
1180  // undef in the icmp and in f(Y). Additionally, take care to avoid replacing
1181  // X == Y ? X : Z with X == Y ? Y : Z, as that would lead to an infinite
1182  // replacement cycle.
1183  Value *CmpLHS = Cmp.getOperand(0), *CmpRHS = Cmp.getOperand(1);
1184  if (TrueVal != CmpLHS &&
1185  isGuaranteedNotToBeUndefOrPoison(CmpRHS, SQ.AC, &Sel, &DT)) {
1186  if (Value *V = simplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, SQ,
1187  /* AllowRefinement */ true))
1188  return replaceOperand(Sel, Swapped ? 2 : 1, V);
1189 
1190  // Even if TrueVal does not simplify, we can directly replace a use of
1191  // CmpLHS with CmpRHS, as long as the instruction is not used anywhere
1192  // else and is safe to speculatively execute (we may end up executing it
1193  // with different operands, which should not cause side-effects or trigger
1194  // undefined behavior). Only do this if CmpRHS is a constant, as
1195  // profitability is not clear for other cases.
1196  // FIXME: The replacement could be performed recursively.
1197  // FIXME: Support vectors.
1198  if (match(CmpRHS, m_ImmConstant()) && !match(CmpLHS, m_ImmConstant()) &&
1199  !Cmp.getType()->isVectorTy())
1200  if (auto *I = dyn_cast<Instruction>(TrueVal))
1201  if (I->hasOneUse() && isSafeToSpeculativelyExecute(I))
1202  for (Use &U : I->operands())
1203  if (U == CmpLHS) {
1204  replaceUse(U, CmpRHS);
1205  return &Sel;
1206  }
1207  }
1208  if (TrueVal != CmpRHS &&
1209  isGuaranteedNotToBeUndefOrPoison(CmpLHS, SQ.AC, &Sel, &DT))
1210  if (Value *V = simplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, SQ,
1211  /* AllowRefinement */ true))
1212  return replaceOperand(Sel, Swapped ? 2 : 1, V);
1213 
1214  auto *FalseInst = dyn_cast<Instruction>(FalseVal);
1215  if (!FalseInst)
1216  return nullptr;
1217 
1218  // InstSimplify already performed this fold if it was possible subject to
1219  // current poison-generating flags. Try the transform again with
1220  // poison-generating flags temporarily dropped.
1221  bool WasNUW = false, WasNSW = false, WasExact = false, WasInBounds = false;
1222  if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(FalseVal)) {
1223  WasNUW = OBO->hasNoUnsignedWrap();
1224  WasNSW = OBO->hasNoSignedWrap();
1225  FalseInst->setHasNoUnsignedWrap(false);
1226  FalseInst->setHasNoSignedWrap(false);
1227  }
1228  if (auto *PEO = dyn_cast<PossiblyExactOperator>(FalseVal)) {
1229  WasExact = PEO->isExact();
1230  FalseInst->setIsExact(false);
1231  }
1232  if (auto *GEP = dyn_cast<GetElementPtrInst>(FalseVal)) {
1233  WasInBounds = GEP->isInBounds();
1234  GEP->setIsInBounds(false);
1235  }
1236 
1237  // Try each equivalence substitution possibility.
1238  // We have an 'EQ' comparison, so the select's false value will propagate.
1239  // Example:
1240  // (X == 42) ? 43 : (X + 1) --> (X == 42) ? (X + 1) : (X + 1) --> X + 1
1241  if (simplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, SQ,
1242  /* AllowRefinement */ false) == TrueVal ||
1243  simplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, SQ,
1244  /* AllowRefinement */ false) == TrueVal) {
1245  return replaceInstUsesWith(Sel, FalseVal);
1246  }
1247 
1248  // Restore poison-generating flags if the transform did not apply.
1249  if (WasNUW)
1250  FalseInst->setHasNoUnsignedWrap();
1251  if (WasNSW)
1252  FalseInst->setHasNoSignedWrap();
1253  if (WasExact)
1254  FalseInst->setIsExact();
1255  if (WasInBounds)
1256  cast<GetElementPtrInst>(FalseInst)->setIsInBounds();
1257 
1258  return nullptr;
1259 }
1260 
1261 // See if this is a pattern like:
1262 // %old_cmp1 = icmp slt i32 %x, C2
1263 // %old_replacement = select i1 %old_cmp1, i32 %target_low, i32 %target_high
1264 // %old_x_offseted = add i32 %x, C1
1265 // %old_cmp0 = icmp ult i32 %old_x_offseted, C0
1266 // %r = select i1 %old_cmp0, i32 %x, i32 %old_replacement
1267 // This can be rewritten as more canonical pattern:
1268 // %new_cmp1 = icmp slt i32 %x, -C1
1269 // %new_cmp2 = icmp sge i32 %x, C0-C1
1270 // %new_clamped_low = select i1 %new_cmp1, i32 %target_low, i32 %x
1271 // %r = select i1 %new_cmp2, i32 %target_high, i32 %new_clamped_low
1272 // Iff -C1 s<= C2 s<= C0-C1
1273 // Also ULT predicate can also be UGT iff C0 != -1 (+invert result)
1274 // SLT predicate can also be SGT iff C2 != INT_MAX (+invert res.)
1275 static Value *canonicalizeClampLike(SelectInst &Sel0, ICmpInst &Cmp0,
1277  Value *X = Sel0.getTrueValue();
1278  Value *Sel1 = Sel0.getFalseValue();
1279 
1280  // First match the condition of the outermost select.
1281  // Said condition must be one-use.
1282  if (!Cmp0.hasOneUse())
1283  return nullptr;
1284  ICmpInst::Predicate Pred0 = Cmp0.getPredicate();
1285  Value *Cmp00 = Cmp0.getOperand(0);
1286  Constant *C0;
1287  if (!match(Cmp0.getOperand(1),
1289  return nullptr;
1290 
1291  if (!isa<SelectInst>(Sel1)) {
1292  Pred0 = ICmpInst::getInversePredicate(Pred0);
1293  std::swap(X, Sel1);
1294  }
1295 
1296  // Canonicalize Cmp0 into ult or uge.
1297  // FIXME: we shouldn't care about lanes that are 'undef' in the end?
1298  switch (Pred0) {
1299  case ICmpInst::Predicate::ICMP_ULT:
1300  case ICmpInst::Predicate::ICMP_UGE:
1301  // Although icmp ult %x, 0 is an unusual thing to try and should generally
1302  // have been simplified, it does not verify with undef inputs so ensure we
1303  // are not in a strange state.
1304  if (!match(C0, m_SpecificInt_ICMP(
1305  ICmpInst::Predicate::ICMP_NE,
1307  return nullptr;
1308  break; // Great!
1309  case ICmpInst::Predicate::ICMP_ULE:
1310  case ICmpInst::Predicate::ICMP_UGT:
1311  // We want to canonicalize it to 'ult' or 'uge', so we'll need to increment
1312  // C0, which again means it must not have any all-ones elements.
1313  if (!match(C0,
1315  ICmpInst::Predicate::ICMP_NE,
1317  return nullptr; // Can't do, have all-ones element[s].
1319  C0 = InstCombiner::AddOne(C0);
1320  break;
1321  default:
1322  return nullptr; // Unknown predicate.
1323  }
1324 
1325  // Now that we've canonicalized the ICmp, we know the X we expect;
1326  // the select in other hand should be one-use.
1327  if (!Sel1->hasOneUse())
1328  return nullptr;
1329 
1330  // If the types do not match, look through any truncs to the underlying
1331  // instruction.
1332  if (Cmp00->getType() != X->getType() && X->hasOneUse())
1334 
1335  // We now can finish matching the condition of the outermost select:
1336  // it should either be the X itself, or an addition of some constant to X.
1337  Constant *C1;
1338  if (Cmp00 == X)
1339  C1 = ConstantInt::getNullValue(X->getType());
1340  else if (!match(Cmp00,
1341  m_Add(m_Specific(X),
1343  return nullptr;
1344 
1345  Value *Cmp1;
1346  ICmpInst::Predicate Pred1;
1347  Constant *C2;
1348  Value *ReplacementLow, *ReplacementHigh;
1349  if (!match(Sel1, m_Select(m_Value(Cmp1), m_Value(ReplacementLow),
1350  m_Value(ReplacementHigh))) ||
1351  !match(Cmp1,
1352  m_ICmp(Pred1, m_Specific(X),
1354  return nullptr;
1355 
1356  if (!Cmp1->hasOneUse() && (Cmp00 == X || !Cmp00->hasOneUse()))
1357  return nullptr; // Not enough one-use instructions for the fold.
1358  // FIXME: this restriction could be relaxed if Cmp1 can be reused as one of
1359  // two comparisons we'll need to build.
1360 
1361  // Canonicalize Cmp1 into the form we expect.
1362  // FIXME: we shouldn't care about lanes that are 'undef' in the end?
1363  switch (Pred1) {
1364  case ICmpInst::Predicate::ICMP_SLT:
1365  break;
1366  case ICmpInst::Predicate::ICMP_SLE:
1367  // We'd have to increment C2 by one, and for that it must not have signed
1368  // max element, but then it would have been canonicalized to 'slt' before
1369  // we get here. So we can't do anything useful with 'sle'.
1370  return nullptr;
1371  case ICmpInst::Predicate::ICMP_SGT:
1372  // We want to canonicalize it to 'slt', so we'll need to increment C2,
1373  // which again means it must not have any signed max elements.
1374  if (!match(C2,
1375  m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE,
1377  C2->getType()->getScalarSizeInBits()))))
1378  return nullptr; // Can't do, have signed max element[s].
1379  C2 = InstCombiner::AddOne(C2);
1380  [[fallthrough]];
1381  case ICmpInst::Predicate::ICMP_SGE:
1382  // Also non-canonical, but here we don't need to change C2,
1383  // so we don't have any restrictions on C2, so we can just handle it.
1384  Pred1 = ICmpInst::Predicate::ICMP_SLT;
1385  std::swap(ReplacementLow, ReplacementHigh);
1386  break;
1387  default:
1388  return nullptr; // Unknown predicate.
1389  }
1390  assert(Pred1 == ICmpInst::Predicate::ICMP_SLT &&
1391  "Unexpected predicate type.");
1392 
1393  // The thresholds of this clamp-like pattern.
1394  auto *ThresholdLowIncl = ConstantExpr::getNeg(C1);
1395  auto *ThresholdHighExcl = ConstantExpr::getSub(C0, C1);
1396 
1397  assert((Pred0 == ICmpInst::Predicate::ICMP_ULT ||
1398  Pred0 == ICmpInst::Predicate::ICMP_UGE) &&
1399  "Unexpected predicate type.");
1400  if (Pred0 == ICmpInst::Predicate::ICMP_UGE)
1401  std::swap(ThresholdLowIncl, ThresholdHighExcl);
1402 
1403  // The fold has a precondition 1: C2 s>= ThresholdLow
1404  auto *Precond1 = ConstantExpr::getICmp(ICmpInst::Predicate::ICMP_SGE, C2,
1405  ThresholdLowIncl);
1406  if (!match(Precond1, m_One()))
1407  return nullptr;
1408  // The fold has a precondition 2: C2 s<= ThresholdHigh
1409  auto *Precond2 = ConstantExpr::getICmp(ICmpInst::Predicate::ICMP_SLE, C2,
1410  ThresholdHighExcl);
1411  if (!match(Precond2, m_One()))
1412  return nullptr;
1413 
1414  // If we are matching from a truncated input, we need to sext the
1415  // ReplacementLow and ReplacementHigh values. Only do the transform if they
1416  // are free to extend due to being constants.
1417  if (X->getType() != Sel0.getType()) {
1418  Constant *LowC, *HighC;
1419  if (!match(ReplacementLow, m_ImmConstant(LowC)) ||
1420  !match(ReplacementHigh, m_ImmConstant(HighC)))
1421  return nullptr;
1422  ReplacementLow = ConstantExpr::getSExt(LowC, X->getType());
1423  ReplacementHigh = ConstantExpr::getSExt(HighC, X->getType());
1424  }
1425 
1426  // All good, finally emit the new pattern.
1427  Value *ShouldReplaceLow = Builder.CreateICmpSLT(X, ThresholdLowIncl);
1428  Value *ShouldReplaceHigh = Builder.CreateICmpSGE(X, ThresholdHighExcl);
1429  Value *MaybeReplacedLow =
1430  Builder.CreateSelect(ShouldReplaceLow, ReplacementLow, X);
1431 
1432  // Create the final select. If we looked through a truncate above, we will
1433  // need to retruncate the result.
1434  Value *MaybeReplacedHigh = Builder.CreateSelect(
1435  ShouldReplaceHigh, ReplacementHigh, MaybeReplacedLow);
1436  return Builder.CreateTrunc(MaybeReplacedHigh, Sel0.getType());
1437 }
1438 
1439 // If we have
1440 // %cmp = icmp [canonical predicate] i32 %x, C0
1441 // %r = select i1 %cmp, i32 %y, i32 C1
1442 // Where C0 != C1 and %x may be different from %y, see if the constant that we
1443 // will have if we flip the strictness of the predicate (i.e. without changing
1444 // the result) is identical to the C1 in select. If it matches we can change
1445 // original comparison to one with swapped predicate, reuse the constant,
1446 // and swap the hands of select.
1447 static Instruction *
1448 tryToReuseConstantFromSelectInComparison(SelectInst &Sel, ICmpInst &Cmp,
1449  InstCombinerImpl &IC) {
1450  ICmpInst::Predicate Pred;
1451  Value *X;
1452  Constant *C0;
1453  if (!match(&Cmp, m_OneUse(m_ICmp(
1454  Pred, m_Value(X),
1456  return nullptr;
1457 
1458  // If comparison predicate is non-relational, we won't be able to do anything.
1459  if (ICmpInst::isEquality(Pred))
1460  return nullptr;
1461 
1462  // If comparison predicate is non-canonical, then we certainly won't be able
1463  // to make it canonical; canonicalizeCmpWithConstant() already tried.
1465  return nullptr;
1466 
1467  // If the [input] type of comparison and select type are different, lets abort
1468  // for now. We could try to compare constants with trunc/[zs]ext though.
1469  if (C0->getType() != Sel.getType())
1470  return nullptr;
1471 
1472  // ULT with 'add' of a constant is canonical. See foldICmpAddConstant().
1473  // FIXME: Are there more magic icmp predicate+constant pairs we must avoid?
1474  // Or should we just abandon this transform entirely?
1475  if (Pred == CmpInst::ICMP_ULT && match(X, m_Add(m_Value(), m_Constant())))
1476  return nullptr;
1477 
1478 
1479  Value *SelVal0, *SelVal1; // We do not care which one is from where.
1480  match(&Sel, m_Select(m_Value(), m_Value(SelVal0), m_Value(SelVal1)));
1481  // At least one of these values we are selecting between must be a constant
1482  // else we'll never succeed.
1483  if (!match(SelVal0, m_AnyIntegralConstant()) &&
1484  !match(SelVal1, m_AnyIntegralConstant()))
1485  return nullptr;
1486 
1487  // Does this constant C match any of the `select` values?
1488  auto MatchesSelectValue = [SelVal0, SelVal1](Constant *C) {
1489  return C->isElementWiseEqual(SelVal0) || C->isElementWiseEqual(SelVal1);
1490  };
1491 
1492  // If C0 *already* matches true/false value of select, we are done.
1493  if (MatchesSelectValue(C0))
1494  return nullptr;
1495 
1496  // Check the constant we'd have with flipped-strictness predicate.
1497  auto FlippedStrictness =
1499  if (!FlippedStrictness)
1500  return nullptr;
1501 
1502  // If said constant doesn't match either, then there is no hope,
1503  if (!MatchesSelectValue(FlippedStrictness->second))
1504  return nullptr;
1505 
1506  // It matched! Lets insert the new comparison just before select.
1507  InstCombiner::BuilderTy::InsertPointGuard Guard(IC.Builder);
1508  IC.Builder.SetInsertPoint(&Sel);
1509 
1510  Pred = ICmpInst::getSwappedPredicate(Pred); // Yes, swapped.
1511  Value *NewCmp = IC.Builder.CreateICmp(Pred, X, FlippedStrictness->second,
1512  Cmp.getName() + ".inv");
1513  IC.replaceOperand(Sel, 0, NewCmp);
1514  Sel.swapValues();
1515  Sel.swapProfMetadata();
1516 
1517  return &Sel;
1518 }
1519 
1520 static Instruction *foldSelectZeroOrOnes(ICmpInst *Cmp, Value *TVal,
1521  Value *FVal,
1523  if (!Cmp->hasOneUse())
1524  return nullptr;
1525 
1526  const APInt *CmpC;
1527  if (!match(Cmp->getOperand(1), m_APIntAllowUndef(CmpC)))
1528  return nullptr;
1529 
1530  // (X u< 2) ? -X : -1 --> sext (X != 0)
1531  Value *X = Cmp->getOperand(0);
1532  if (Cmp->getPredicate() == ICmpInst::ICMP_ULT && *CmpC == 2 &&
1533  match(TVal, m_Neg(m_Specific(X))) && match(FVal, m_AllOnes()))
1534  return new SExtInst(Builder.CreateIsNotNull(X), TVal->getType());
1535 
1536  // (X u> 1) ? -1 : -X --> sext (X != 0)
1537  if (Cmp->getPredicate() == ICmpInst::ICMP_UGT && *CmpC == 1 &&
1538  match(FVal, m_Neg(m_Specific(X))) && match(TVal, m_AllOnes()))
1539  return new SExtInst(Builder.CreateIsNotNull(X), TVal->getType());
1540 
1541  return nullptr;
1542 }
1543 
1544 static Value *foldSelectInstWithICmpConst(SelectInst &SI, ICmpInst *ICI) {
1545  const APInt *CmpC;
1546  Value *V;
1547  CmpInst::Predicate Pred;
1548  if (!match(ICI, m_ICmp(Pred, m_Value(V), m_APInt(CmpC))))
1549  return nullptr;
1550 
1551  BinaryOperator *BO;
1552  const APInt *C;
1553  CmpInst::Predicate CPred;
1554  if (match(&SI, m_Select(m_Specific(ICI), m_APInt(C), m_BinOp(BO))))
1555  CPred = ICI->getPredicate();
1556  else if (match(&SI, m_Select(m_Specific(ICI), m_BinOp(BO), m_APInt(C))))
1557  CPred = ICI->getInversePredicate();
1558  else
1559  return nullptr;
1560 
1561  const APInt *BinOpC;
1562  if (!match(BO, m_BinOp(m_Specific(V), m_APInt(BinOpC))))
1563  return nullptr;
1564 
1566  .binaryOp(BO->getOpcode(), *BinOpC);
1567  if (R == *C) {
1569  return BO;
1570  }
1571  return nullptr;
1572 }
1573 
1574 /// Visit a SelectInst that has an ICmpInst as its first operand.
1576  ICmpInst *ICI) {
1577  if (Instruction *NewSel = foldSelectValueEquivalence(SI, *ICI))
1578  return NewSel;
1579 
1580  if (Instruction *NewSPF = canonicalizeSPF(SI, *ICI, *this))
1581  return NewSPF;
1582 
1583  if (Value *V = foldSelectInstWithICmpConst(SI, ICI))
1584  return replaceInstUsesWith(SI, V);
1585 
1586  if (Value *V = canonicalizeClampLike(SI, *ICI, Builder))
1587  return replaceInstUsesWith(SI, V);
1588 
1589  if (Instruction *NewSel =
1590  tryToReuseConstantFromSelectInComparison(SI, *ICI, *this))
1591  return NewSel;
1592 
1593  bool Changed = adjustMinMax(SI, *ICI);
1594 
1595  if (Value *V = foldSelectICmpAnd(SI, ICI, Builder))
1596  return replaceInstUsesWith(SI, V);
1597 
1598  // NOTE: if we wanted to, this is where to detect integer MIN/MAX
1599  Value *TrueVal = SI.getTrueValue();
1600  Value *FalseVal = SI.getFalseValue();
1601  ICmpInst::Predicate Pred = ICI->getPredicate();
1602  Value *CmpLHS = ICI->getOperand(0);
1603  Value *CmpRHS = ICI->getOperand(1);
1604  if (CmpRHS != CmpLHS && isa<Constant>(CmpRHS)) {
1605  if (CmpLHS == TrueVal && Pred == ICmpInst::ICMP_EQ) {
1606  // Transform (X == C) ? X : Y -> (X == C) ? C : Y
1607  SI.setOperand(1, CmpRHS);
1608  Changed = true;
1609  } else if (CmpLHS == FalseVal && Pred == ICmpInst::ICMP_NE) {
1610  // Transform (X != C) ? Y : X -> (X != C) ? Y : C
1611  SI.setOperand(2, CmpRHS);
1612  Changed = true;
1613  }
1614  }
1615 
1616  // Canonicalize a signbit condition to use zero constant by swapping:
1617  // (CmpLHS > -1) ? TV : FV --> (CmpLHS < 0) ? FV : TV
1618  // To avoid conflicts (infinite loops) with other canonicalizations, this is
1619  // not applied with any constant select arm.
1620  if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes()) &&
1622  ICI->hasOneUse()) {
1623  InstCombiner::BuilderTy::InsertPointGuard Guard(Builder);
1624  Builder.SetInsertPoint(&SI);
1625  Value *IsNeg = Builder.CreateIsNeg(CmpLHS, ICI->getName());
1626  replaceOperand(SI, 0, IsNeg);
1627  SI.swapValues();
1628  SI.swapProfMetadata();
1629  return &SI;
1630  }
1631 
1632  // FIXME: This code is nearly duplicated in InstSimplify. Using/refactoring
1633  // decomposeBitTestICmp() might help.
1634  {
1635  unsigned BitWidth =
1636  DL.getTypeSizeInBits(TrueVal->getType()->getScalarType());
1637  APInt MinSignedValue = APInt::getSignedMinValue(BitWidth);
1638  Value *X;
1639  const APInt *Y, *C;
1640  bool TrueWhenUnset;
1641  bool IsBitTest = false;
1642  if (ICmpInst::isEquality(Pred) &&
1643  match(CmpLHS, m_And(m_Value(X), m_Power2(Y))) &&
1644  match(CmpRHS, m_Zero())) {
1645  IsBitTest = true;
1646  TrueWhenUnset = Pred == ICmpInst::ICMP_EQ;
1647  } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) {
1648  X = CmpLHS;
1649  Y = &MinSignedValue;
1650  IsBitTest = true;
1651  TrueWhenUnset = false;
1652  } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) {
1653  X = CmpLHS;
1654  Y = &MinSignedValue;
1655  IsBitTest = true;
1656  TrueWhenUnset = true;
1657  }
1658  if (IsBitTest) {
1659  Value *V = nullptr;
1660  // (X & Y) == 0 ? X : X ^ Y --> X & ~Y
1661  if (TrueWhenUnset && TrueVal == X &&
1662  match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1663  V = Builder.CreateAnd(X, ~(*Y));
1664  // (X & Y) != 0 ? X ^ Y : X --> X & ~Y
1665  else if (!TrueWhenUnset && FalseVal == X &&
1666  match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1667  V = Builder.CreateAnd(X, ~(*Y));
1668  // (X & Y) == 0 ? X ^ Y : X --> X | Y
1669  else if (TrueWhenUnset && FalseVal == X &&
1670  match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1671  V = Builder.CreateOr(X, *Y);
1672  // (X & Y) != 0 ? X : X ^ Y --> X | Y
1673  else if (!TrueWhenUnset && TrueVal == X &&
1674  match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1675  V = Builder.CreateOr(X, *Y);
1676 
1677  if (V)
1678  return replaceInstUsesWith(SI, V);
1679  }
1680  }
1681 
1682  if (Instruction *V =
1683  foldSelectICmpAndAnd(SI.getType(), ICI, TrueVal, FalseVal, Builder))
1684  return V;
1685 
1686  if (Instruction *V = foldSelectCtlzToCttz(ICI, TrueVal, FalseVal, Builder))
1687  return V;
1688 
1689  if (Instruction *V = foldSelectZeroOrOnes(ICI, TrueVal, FalseVal, Builder))
1690  return V;
1691 
1693  return replaceInstUsesWith(SI, V);
1694 
1696  return replaceInstUsesWith(SI, V);
1697 
1698  if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
1699  return replaceInstUsesWith(SI, V);
1700 
1702  return replaceInstUsesWith(SI, V);
1703 
1705  return replaceInstUsesWith(SI, V);
1706 
1707  return Changed ? &SI : nullptr;
1708 }
1709 
1710 /// SI is a select whose condition is a PHI node (but the two may be in
1711 /// different blocks). See if the true/false values (V) are live in all of the
1712 /// predecessor blocks of the PHI. For example, cases like this can't be mapped:
1713 ///
1714 /// X = phi [ C1, BB1], [C2, BB2]
1715 /// Y = add
1716 /// Z = select X, Y, 0
1717 ///
1718 /// because Y is not live in BB1/BB2.
1719 static bool canSelectOperandBeMappingIntoPredBlock(const Value *V,
1720  const SelectInst &SI) {
1721  // If the value is a non-instruction value like a constant or argument, it
1722  // can always be mapped.
1723  const Instruction *I = dyn_cast<Instruction>(V);
1724  if (!I) return true;
1725 
1726  // If V is a PHI node defined in the same block as the condition PHI, we can
1727  // map the arguments.
1728  const PHINode *CondPHI = cast<PHINode>(SI.getCondition());
1729 
1730  if (const PHINode *VP = dyn_cast<PHINode>(I))
1731  if (VP->getParent() == CondPHI->getParent())
1732  return true;
1733 
1734  // Otherwise, if the PHI and select are defined in the same block and if V is
1735  // defined in a different block, then we can transform it.
1736  if (SI.getParent() == CondPHI->getParent() &&
1737  I->getParent() != CondPHI->getParent())
1738  return true;
1739 
1740  // Otherwise we have a 'hard' case and we can't tell without doing more
1741  // detailed dominator based analysis, punt.
1742  return false;
1743 }
1744 
1745 /// We have an SPF (e.g. a min or max) of an SPF of the form:
1746 /// SPF2(SPF1(A, B), C)
1748  SelectPatternFlavor SPF1, Value *A,
1749  Value *B, Instruction &Outer,
1750  SelectPatternFlavor SPF2,
1751  Value *C) {
1752  if (Outer.getType() != Inner->getType())
1753  return nullptr;
1754 
1755  if (C == A || C == B) {
1756  // MAX(MAX(A, B), B) -> MAX(A, B)
1757  // MIN(MIN(a, b), a) -> MIN(a, b)
1758  // TODO: This could be done in instsimplify.
1759  if (SPF1 == SPF2 && SelectPatternResult::isMinOrMax(SPF1))
1760  return replaceInstUsesWith(Outer, Inner);
1761  }
1762 
1763  return nullptr;
1764 }
1765 
1766 /// Turn select C, (X + Y), (X - Y) --> (X + (select C, Y, (-Y))).
1767 /// This is even legal for FP.
1768 static Instruction *foldAddSubSelect(SelectInst &SI,
1770  Value *CondVal = SI.getCondition();
1771  Value *TrueVal = SI.getTrueValue();
1772  Value *FalseVal = SI.getFalseValue();
1773  auto *TI = dyn_cast<Instruction>(TrueVal);
1774  auto *FI = dyn_cast<Instruction>(FalseVal);
1775  if (!TI || !FI || !TI->hasOneUse() || !FI->hasOneUse())
1776  return nullptr;
1777 
1778  Instruction *AddOp = nullptr, *SubOp = nullptr;
1779  if ((TI->getOpcode() == Instruction::Sub &&
1780  FI->getOpcode() == Instruction::Add) ||
1781  (TI->getOpcode() == Instruction::FSub &&
1782  FI->getOpcode() == Instruction::FAdd)) {
1783  AddOp = FI;
1784  SubOp = TI;
1785  } else if ((FI->getOpcode() == Instruction::Sub &&
1786  TI->getOpcode() == Instruction::Add) ||
1787  (FI->getOpcode() == Instruction::FSub &&
1788  TI->getOpcode() == Instruction::FAdd)) {
1789  AddOp = TI;
1790  SubOp = FI;
1791  }
1792 
1793  if (AddOp) {
1794  Value *OtherAddOp = nullptr;
1795  if (SubOp->getOperand(0) == AddOp->getOperand(0)) {
1796  OtherAddOp = AddOp->getOperand(1);
1797  } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) {
1798  OtherAddOp = AddOp->getOperand(0);
1799  }
1800 
1801  if (OtherAddOp) {
1802  // So at this point we know we have (Y -> OtherAddOp):
1803  // select C, (add X, Y), (sub X, Z)
1804  Value *NegVal; // Compute -Z
1805  if (SI.getType()->isFPOrFPVectorTy()) {
1806  NegVal = Builder.CreateFNeg(SubOp->getOperand(1));
1807  if (Instruction *NegInst = dyn_cast<Instruction>(NegVal)) {
1809  Flags &= SubOp->getFastMathFlags();
1810  NegInst->setFastMathFlags(Flags);
1811  }
1812  } else {
1813  NegVal = Builder.CreateNeg(SubOp->getOperand(1));
1814  }
1815 
1816  Value *NewTrueOp = OtherAddOp;
1817  Value *NewFalseOp = NegVal;
1818  if (AddOp != TI)
1819  std::swap(NewTrueOp, NewFalseOp);
1820  Value *NewSel = Builder.CreateSelect(CondVal, NewTrueOp, NewFalseOp,
1821  SI.getName() + ".p", &SI);
1822 
1823  if (SI.getType()->isFPOrFPVectorTy()) {
1824  Instruction *RI =
1825  BinaryOperator::CreateFAdd(SubOp->getOperand(0), NewSel);
1826 
1828  Flags &= SubOp->getFastMathFlags();
1829  RI->setFastMathFlags(Flags);
1830  return RI;
1831  } else
1832  return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel);
1833  }
1834  }
1835  return nullptr;
1836 }
1837 
1838 /// Turn X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
1839 /// And X - Y overflows ? 0 : X - Y -> usub_sat X, Y
1840 /// Along with a number of patterns similar to:
1841 /// X + Y overflows ? (X < 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1842 /// X - Y overflows ? (X > 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1843 static Instruction *
1844 foldOverflowingAddSubSelect(SelectInst &SI, InstCombiner::BuilderTy &Builder) {
1845  Value *CondVal = SI.getCondition();
1846  Value *TrueVal = SI.getTrueValue();
1847  Value *FalseVal = SI.getFalseValue();
1848 
1849  WithOverflowInst *II;
1850  if (!match(CondVal, m_ExtractValue<1>(m_WithOverflowInst(II))) ||
1851  !match(FalseVal, m_ExtractValue<0>(m_Specific(II))))
1852  return nullptr;
1853 
1854  Value *X = II->getLHS();
1855  Value *Y = II->getRHS();
1856 
1857  auto IsSignedSaturateLimit = [&](Value *Limit, bool IsAdd) {
1858  Type *Ty = Limit->getType();
1859 
1860  ICmpInst::Predicate Pred;
1861  Value *TrueVal, *FalseVal, *Op;
1862  const APInt *C;
1863  if (!match(Limit, m_Select(m_ICmp(Pred, m_Value(Op), m_APInt(C)),
1865  return false;
1866 
1867  auto IsZeroOrOne = [](const APInt &C) { return C.isZero() || C.isOne(); };
1868  auto IsMinMax = [&](Value *Min, Value *Max) {
1871  return match(Min, m_SpecificInt(MinVal)) &&
1872  match(Max, m_SpecificInt(MaxVal));
1873  };
1874 
1875  if (Op != X && Op != Y)
1876  return false;
1877 
1878  if (IsAdd) {
1879  // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1880  // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1881  // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1882  // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1883  if (Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
1884  IsMinMax(TrueVal, FalseVal))
1885  return true;
1886  // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1887  // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1888  // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1889  // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1890  if (Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
1891  IsMinMax(FalseVal, TrueVal))
1892  return true;
1893  } else {
1894  // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1895  // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1896  if (Op == X && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C + 1) &&
1897  IsMinMax(TrueVal, FalseVal))
1898  return true;
1899  // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1900  // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1901  if (Op == X && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 2) &&
1902  IsMinMax(FalseVal, TrueVal))
1903  return true;
1904  // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1905  // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1906  if (Op == Y && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
1907  IsMinMax(FalseVal, TrueVal))
1908  return true;
1909  // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1910  // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1911  if (Op == Y && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
1912  IsMinMax(TrueVal, FalseVal))
1913  return true;
1914  }
1915 
1916  return false;
1917  };
1918 
1919  Intrinsic::ID NewIntrinsicID;
1920  if (II->getIntrinsicID() == Intrinsic::uadd_with_overflow &&
1921  match(TrueVal, m_AllOnes()))
1922  // X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
1923  NewIntrinsicID = Intrinsic::uadd_sat;
1924  else if (II->getIntrinsicID() == Intrinsic::usub_with_overflow &&
1925  match(TrueVal, m_Zero()))
1926  // X - Y overflows ? 0 : X - Y -> usub_sat X, Y
1927  NewIntrinsicID = Intrinsic::usub_sat;
1928  else if (II->getIntrinsicID() == Intrinsic::sadd_with_overflow &&
1929  IsSignedSaturateLimit(TrueVal, /*IsAdd=*/true))
1930  // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1931  // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1932  // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1933  // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1934  // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1935  // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1936  // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1937  // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1938  NewIntrinsicID = Intrinsic::sadd_sat;
1939  else if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow &&
1940  IsSignedSaturateLimit(TrueVal, /*IsAdd=*/false))
1941  // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1942  // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1943  // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1944  // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1945  // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1946  // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1947  // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1948  // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1949  NewIntrinsicID = Intrinsic::ssub_sat;
1950  else
1951  return nullptr;
1952 
1953  Function *F =
1954  Intrinsic::getDeclaration(SI.getModule(), NewIntrinsicID, SI.getType());
1955  return CallInst::Create(F, {X, Y});
1956 }
1957 
1959  Constant *C;
1960  if (!match(Sel.getTrueValue(), m_Constant(C)) &&
1961  !match(Sel.getFalseValue(), m_Constant(C)))
1962  return nullptr;
1963 
1964  Instruction *ExtInst;
1965  if (!match(Sel.getTrueValue(), m_Instruction(ExtInst)) &&
1966  !match(Sel.getFalseValue(), m_Instruction(ExtInst)))
1967  return nullptr;
1968 
1969  auto ExtOpcode = ExtInst->getOpcode();
1970  if (ExtOpcode != Instruction::ZExt && ExtOpcode != Instruction::SExt)
1971  return nullptr;
1972 
1973  // If we are extending from a boolean type or if we can create a select that
1974  // has the same size operands as its condition, try to narrow the select.
1975  Value *X = ExtInst->getOperand(0);
1976  Type *SmallType = X->getType();
1977  Value *Cond = Sel.getCondition();
1978  auto *Cmp = dyn_cast<CmpInst>(Cond);
1979  if (!SmallType->isIntOrIntVectorTy(1) &&
1980  (!Cmp || Cmp->getOperand(0)->getType() != SmallType))
1981  return nullptr;
1982 
1983  // If the constant is the same after truncation to the smaller type and
1984  // extension to the original type, we can narrow the select.
1985  Type *SelType = Sel.getType();
1986  Constant *TruncC = ConstantExpr::getTrunc(C, SmallType);
1987  Constant *ExtC = ConstantExpr::getCast(ExtOpcode, TruncC, SelType);
1988  if (ExtC == C && ExtInst->hasOneUse()) {
1989  Value *TruncCVal = cast<Value>(TruncC);
1990  if (ExtInst == Sel.getFalseValue())
1991  std::swap(X, TruncCVal);
1992 
1993  // select Cond, (ext X), C --> ext(select Cond, X, C')
1994  // select Cond, C, (ext X) --> ext(select Cond, C', X)
1995  Value *NewSel = Builder.CreateSelect(Cond, X, TruncCVal, "narrow", &Sel);
1996  return CastInst::Create(Instruction::CastOps(ExtOpcode), NewSel, SelType);
1997  }
1998 
1999  // If one arm of the select is the extend of the condition, replace that arm
2000  // with the extension of the appropriate known bool value.
2001  if (Cond == X) {
2002  if (ExtInst == Sel.getTrueValue()) {
2003  // select X, (sext X), C --> select X, -1, C
2004  // select X, (zext X), C --> select X, 1, C
2005  Constant *One = ConstantInt::getTrue(SmallType);
2006  Constant *AllOnesOrOne = ConstantExpr::getCast(ExtOpcode, One, SelType);
2007  return SelectInst::Create(Cond, AllOnesOrOne, C, "", nullptr, &Sel);
2008  } else {
2009  // select X, C, (sext X) --> select X, C, 0
2010  // select X, C, (zext X) --> select X, C, 0
2012  return SelectInst::Create(Cond, C, Zero, "", nullptr, &Sel);
2013  }
2014  }
2015 
2016  return nullptr;
2017 }
2018 
2019 /// Try to transform a vector select with a constant condition vector into a
2020 /// shuffle for easier combining with other shuffles and insert/extract.
2021 static Instruction *canonicalizeSelectToShuffle(SelectInst &SI) {
2022  Value *CondVal = SI.getCondition();
2023  Constant *CondC;
2024  auto *CondValTy = dyn_cast<FixedVectorType>(CondVal->getType());
2025  if (!CondValTy || !match(CondVal, m_Constant(CondC)))
2026  return nullptr;
2027 
2028  unsigned NumElts = CondValTy->getNumElements();
2030  Mask.reserve(NumElts);
2031  for (unsigned i = 0; i != NumElts; ++i) {
2032  Constant *Elt = CondC->getAggregateElement(i);
2033  if (!Elt)
2034  return nullptr;
2035 
2036  if (Elt->isOneValue()) {
2037  // If the select condition element is true, choose from the 1st vector.
2038  Mask.push_back(i);
2039  } else if (Elt->isNullValue()) {
2040  // If the select condition element is false, choose from the 2nd vector.
2041  Mask.push_back(i + NumElts);
2042  } else if (isa<UndefValue>(Elt)) {
2043  // Undef in a select condition (choose one of the operands) does not mean
2044  // the same thing as undef in a shuffle mask (any value is acceptable), so
2045  // give up.
2046  return nullptr;
2047  } else {
2048  // Bail out on a constant expression.
2049  return nullptr;
2050  }
2051  }
2052 
2053  return new ShuffleVectorInst(SI.getTrueValue(), SI.getFalseValue(), Mask);
2054 }
2055 
2056 /// If we have a select of vectors with a scalar condition, try to convert that
2057 /// to a vector select by splatting the condition. A splat may get folded with
2058 /// other operations in IR and having all operands of a select be vector types
2059 /// is likely better for vector codegen.
2060 static Instruction *canonicalizeScalarSelectOfVecs(SelectInst &Sel,
2061  InstCombinerImpl &IC) {
2062  auto *Ty = dyn_cast<VectorType>(Sel.getType());
2063  if (!Ty)
2064  return nullptr;
2065 
2066  // We can replace a single-use extract with constant index.
2067  Value *Cond = Sel.getCondition();
2069  return nullptr;
2070 
2071  // select (extelt V, Index), T, F --> select (splat V, Index), T, F
2072  // Splatting the extracted condition reduces code (we could directly create a
2073  // splat shuffle of the source vector to eliminate the intermediate step).
2074  return IC.replaceOperand(
2075  Sel, 0, IC.Builder.CreateVectorSplat(Ty->getElementCount(), Cond));
2076 }
2077 
2078 /// Reuse bitcasted operands between a compare and select:
2079 /// select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2080 /// bitcast (select (cmp (bitcast C), (bitcast D)), (bitcast C), (bitcast D))
2081 static Instruction *foldSelectCmpBitcasts(SelectInst &Sel,
2083  Value *Cond = Sel.getCondition();
2084  Value *TVal = Sel.getTrueValue();
2085  Value *FVal = Sel.getFalseValue();
2086 
2087  CmpInst::Predicate Pred;
2088  Value *A, *B;
2089  if (!match(Cond, m_Cmp(Pred, m_Value(A), m_Value(B))))
2090  return nullptr;
2091 
2092  // The select condition is a compare instruction. If the select's true/false
2093  // values are already the same as the compare operands, there's nothing to do.
2094  if (TVal == A || TVal == B || FVal == A || FVal == B)
2095  return nullptr;
2096 
2097  Value *C, *D;
2098  if (!match(A, m_BitCast(m_Value(C))) || !match(B, m_BitCast(m_Value(D))))
2099  return nullptr;
2100 
2101  // select (cmp (bitcast C), (bitcast D)), (bitcast TSrc), (bitcast FSrc)
2102  Value *TSrc, *FSrc;
2103  if (!match(TVal, m_BitCast(m_Value(TSrc))) ||
2104  !match(FVal, m_BitCast(m_Value(FSrc))))
2105  return nullptr;
2106 
2107  // If the select true/false values are *different bitcasts* of the same source
2108  // operands, make the select operands the same as the compare operands and
2109  // cast the result. This is the canonical select form for min/max.
2110  Value *NewSel;
2111  if (TSrc == C && FSrc == D) {
2112  // select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2113  // bitcast (select (cmp A, B), A, B)
2114  NewSel = Builder.CreateSelect(Cond, A, B, "", &Sel);
2115  } else if (TSrc == D && FSrc == C) {
2116  // select (cmp (bitcast C), (bitcast D)), (bitcast' D), (bitcast' C) -->
2117  // bitcast (select (cmp A, B), B, A)
2118  NewSel = Builder.CreateSelect(Cond, B, A, "", &Sel);
2119  } else {
2120  return nullptr;
2121  }
2122  return CastInst::CreateBitOrPointerCast(NewSel, Sel.getType());
2123 }
2124 
2125 /// Try to eliminate select instructions that test the returned flag of cmpxchg
2126 /// instructions.
2127 ///
2128 /// If a select instruction tests the returned flag of a cmpxchg instruction and
2129 /// selects between the returned value of the cmpxchg instruction its compare
2130 /// operand, the result of the select will always be equal to its false value.
2131 /// For example:
2132 ///
2133 /// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2134 /// %1 = extractvalue { i64, i1 } %0, 1
2135 /// %2 = extractvalue { i64, i1 } %0, 0
2136 /// %3 = select i1 %1, i64 %compare, i64 %2
2137 /// ret i64 %3
2138 ///
2139 /// The returned value of the cmpxchg instruction (%2) is the original value
2140 /// located at %ptr prior to any update. If the cmpxchg operation succeeds, %2
2141 /// must have been equal to %compare. Thus, the result of the select is always
2142 /// equal to %2, and the code can be simplified to:
2143 ///
2144 /// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2145 /// %1 = extractvalue { i64, i1 } %0, 0
2146 /// ret i64 %1
2147 ///
2148 static Value *foldSelectCmpXchg(SelectInst &SI) {
2149  // A helper that determines if V is an extractvalue instruction whose
2150  // aggregate operand is a cmpxchg instruction and whose single index is equal
2151  // to I. If such conditions are true, the helper returns the cmpxchg
2152  // instruction; otherwise, a nullptr is returned.
2153  auto isExtractFromCmpXchg = [](Value *V, unsigned I) -> AtomicCmpXchgInst * {
2154  auto *Extract = dyn_cast<ExtractValueInst>(V);
2155  if (!Extract)
2156  return nullptr;
2157  if (Extract->getIndices()[0] != I)
2158  return nullptr;
2159  return dyn_cast<AtomicCmpXchgInst>(Extract->getAggregateOperand());
2160  };
2161 
2162  // If the select has a single user, and this user is a select instruction that
2163  // we can simplify, skip the cmpxchg simplification for now.
2164  if (SI.hasOneUse())
2165  if (auto *Select = dyn_cast<SelectInst>(SI.user_back()))
2166  if (Select->getCondition() == SI.getCondition())
2167  if (Select->getFalseValue() == SI.getTrueValue() ||
2168  Select->getTrueValue() == SI.getFalseValue())
2169  return nullptr;
2170 
2171  // Ensure the select condition is the returned flag of a cmpxchg instruction.
2172  auto *CmpXchg = isExtractFromCmpXchg(SI.getCondition(), 1);
2173  if (!CmpXchg)
2174  return nullptr;
2175 
2176  // Check the true value case: The true value of the select is the returned
2177  // value of the same cmpxchg used by the condition, and the false value is the
2178  // cmpxchg instruction's compare operand.
2179  if (auto *X = isExtractFromCmpXchg(SI.getTrueValue(), 0))
2180  if (X == CmpXchg && X->getCompareOperand() == SI.getFalseValue())
2181  return SI.getFalseValue();
2182 
2183  // Check the false value case: The false value of the select is the returned
2184  // value of the same cmpxchg used by the condition, and the true value is the
2185  // cmpxchg instruction's compare operand.
2186  if (auto *X = isExtractFromCmpXchg(SI.getFalseValue(), 0))
2187  if (X == CmpXchg && X->getCompareOperand() == SI.getTrueValue())
2188  return SI.getFalseValue();
2189 
2190  return nullptr;
2191 }
2192 
2193 /// Try to reduce a funnel/rotate pattern that includes a compare and select
2194 /// into a funnel shift intrinsic. Example:
2195 /// rotl32(a, b) --> (b == 0 ? a : ((a >> (32 - b)) | (a << b)))
2196 /// --> call llvm.fshl.i32(a, a, b)
2197 /// fshl32(a, b, c) --> (c == 0 ? a : ((b >> (32 - c)) | (a << c)))
2198 /// --> call llvm.fshl.i32(a, b, c)
2199 /// fshr32(a, b, c) --> (c == 0 ? b : ((a >> (32 - c)) | (b << c)))
2200 /// --> call llvm.fshr.i32(a, b, c)
2201 static Instruction *foldSelectFunnelShift(SelectInst &Sel,
2203  // This must be a power-of-2 type for a bitmasking transform to be valid.
2204  unsigned Width = Sel.getType()->getScalarSizeInBits();
2205  if (!isPowerOf2_32(Width))
2206  return nullptr;
2207 
2208  BinaryOperator *Or0, *Or1;
2209  if (!match(Sel.getFalseValue(), m_OneUse(m_Or(m_BinOp(Or0), m_BinOp(Or1)))))
2210  return nullptr;
2211 
2212  Value *SV0, *SV1, *SA0, *SA1;
2213  if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(SV0),
2214  m_ZExtOrSelf(m_Value(SA0))))) ||
2215  !match(Or1, m_OneUse(m_LogicalShift(m_Value(SV1),
2216  m_ZExtOrSelf(m_Value(SA1))))) ||
2217  Or0->getOpcode() == Or1->getOpcode())
2218  return nullptr;
2219 
2220  // Canonicalize to or(shl(SV0, SA0), lshr(SV1, SA1)).
2221  if (Or0->getOpcode() == BinaryOperator::LShr) {
2222  std::swap(Or0, Or1);
2223  std::swap(SV0, SV1);
2224  std::swap(SA0, SA1);
2225  }
2226  assert(Or0->getOpcode() == BinaryOperator::Shl &&
2227  Or1->getOpcode() == BinaryOperator::LShr &&
2228  "Illegal or(shift,shift) pair");
2229 
2230  // Check the shift amounts to see if they are an opposite pair.
2231  Value *ShAmt;
2232  if (match(SA1, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA0)))))
2233  ShAmt = SA0;
2234  else if (match(SA0, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA1)))))
2235  ShAmt = SA1;
2236  else
2237  return nullptr;
2238 
2239  // We should now have this pattern:
2240  // select ?, TVal, (or (shl SV0, SA0), (lshr SV1, SA1))
2241  // The false value of the select must be a funnel-shift of the true value:
2242  // IsFShl -> TVal must be SV0 else TVal must be SV1.
2243  bool IsFshl = (ShAmt == SA0);
2244  Value *TVal = Sel.getTrueValue();
2245  if ((IsFshl && TVal != SV0) || (!IsFshl && TVal != SV1))
2246  return nullptr;
2247 
2248  // Finally, see if the select is filtering out a shift-by-zero.
2249  Value *Cond = Sel.getCondition();
2250  ICmpInst::Predicate Pred;
2251  if (!match(Cond, m_OneUse(m_ICmp(Pred, m_Specific(ShAmt), m_ZeroInt()))) ||
2252  Pred != ICmpInst::ICMP_EQ)
2253  return nullptr;
2254 
2255  // If this is not a rotate then the select was blocking poison from the
2256  // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.
2257  if (SV0 != SV1) {
2258  if (IsFshl && !llvm::isGuaranteedNotToBePoison(SV1))
2259  SV1 = Builder.CreateFreeze(SV1);
2260  else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(SV0))
2261  SV0 = Builder.CreateFreeze(SV0);
2262  }
2263 
2264  // This is a funnel/rotate that avoids shift-by-bitwidth UB in a suboptimal way.
2265  // Convert to funnel shift intrinsic.
2266  Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2267  Function *F = Intrinsic::getDeclaration(Sel.getModule(), IID, Sel.getType());
2268  ShAmt = Builder.CreateZExt(ShAmt, Sel.getType());
2269  return CallInst::Create(F, { SV0, SV1, ShAmt });
2270 }
2271 
2272 static Instruction *foldSelectToCopysign(SelectInst &Sel,
2274  Value *Cond = Sel.getCondition();
2275  Value *TVal = Sel.getTrueValue();
2276  Value *FVal = Sel.getFalseValue();
2277  Type *SelType = Sel.getType();
2278 
2279  // Match select ?, TC, FC where the constants are equal but negated.
2280  // TODO: Generalize to handle a negated variable operand?
2281  const APFloat *TC, *FC;
2282  if (!match(TVal, m_APFloatAllowUndef(TC)) ||
2283  !match(FVal, m_APFloatAllowUndef(FC)) ||
2284  !abs(*TC).bitwiseIsEqual(abs(*FC)))
2285  return nullptr;
2286 
2287  assert(TC != FC && "Expected equal select arms to simplify");
2288 
2289  Value *X;
2290  const APInt *C;
2291  bool IsTrueIfSignSet;
2292  ICmpInst::Predicate Pred;
2293  if (!match(Cond, m_OneUse(m_ICmp(Pred, m_BitCast(m_Value(X)), m_APInt(C)))) ||
2294  !InstCombiner::isSignBitCheck(Pred, *C, IsTrueIfSignSet) ||
2295  X->getType() != SelType)
2296  return nullptr;
2297 
2298  // If needed, negate the value that will be the sign argument of the copysign:
2299  // (bitcast X) < 0 ? -TC : TC --> copysign(TC, X)
2300  // (bitcast X) < 0 ? TC : -TC --> copysign(TC, -X)
2301  // (bitcast X) >= 0 ? -TC : TC --> copysign(TC, -X)
2302  // (bitcast X) >= 0 ? TC : -TC --> copysign(TC, X)
2303  // Note: FMF from the select can not be propagated to the new instructions.
2304  if (IsTrueIfSignSet ^ TC->isNegative())
2305  X = Builder.CreateFNeg(X);
2306 
2307  // Canonicalize the magnitude argument as the positive constant since we do
2308  // not care about its sign.
2309  Value *MagArg = ConstantFP::get(SelType, abs(*TC));
2310  Function *F = Intrinsic::getDeclaration(Sel.getModule(), Intrinsic::copysign,
2311  Sel.getType());
2312  return CallInst::Create(F, { MagArg, X });
2313 }
2314 
2316  auto *VecTy = dyn_cast<FixedVectorType>(Sel.getType());
2317  if (!VecTy)
2318  return nullptr;
2319 
2320  unsigned NumElts = VecTy->getNumElements();
2321  APInt UndefElts(NumElts, 0);
2322  APInt AllOnesEltMask(APInt::getAllOnes(NumElts));
2323  if (Value *V = SimplifyDemandedVectorElts(&Sel, AllOnesEltMask, UndefElts)) {
2324  if (V != &Sel)
2325  return replaceInstUsesWith(Sel, V);
2326  return &Sel;
2327  }
2328 
2329  // A select of a "select shuffle" with a common operand can be rearranged
2330  // to select followed by "select shuffle". Because of poison, this only works
2331  // in the case of a shuffle with no undefined mask elements.
2332  Value *Cond = Sel.getCondition();
2333  Value *TVal = Sel.getTrueValue();
2334  Value *FVal = Sel.getFalseValue();
2335  Value *X, *Y;
2337  if (match(TVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
2339  cast<ShuffleVectorInst>(TVal)->isSelect()) {
2340  if (X == FVal) {
2341  // select Cond, (shuf_sel X, Y), X --> shuf_sel X, (select Cond, Y, X)
2342  Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
2343  return new ShuffleVectorInst(X, NewSel, Mask);
2344  }
2345  if (Y == FVal) {
2346  // select Cond, (shuf_sel X, Y), Y --> shuf_sel (select Cond, X, Y), Y
2347  Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
2348  return new ShuffleVectorInst(NewSel, Y, Mask);
2349  }
2350  }
2351  if (match(FVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
2353  cast<ShuffleVectorInst>(FVal)->isSelect()) {
2354  if (X == TVal) {
2355  // select Cond, X, (shuf_sel X, Y) --> shuf_sel X, (select Cond, X, Y)
2356  Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
2357  return new ShuffleVectorInst(X, NewSel, Mask);
2358  }
2359  if (Y == TVal) {
2360  // select Cond, Y, (shuf_sel X, Y) --> shuf_sel (select Cond, Y, X), Y
2361  Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
2362  return new ShuffleVectorInst(NewSel, Y, Mask);
2363  }
2364  }
2365 
2366  return nullptr;
2367 }
2368 
2369 static Instruction *foldSelectToPhiImpl(SelectInst &Sel, BasicBlock *BB,
2370  const DominatorTree &DT,
2372  // Find the block's immediate dominator that ends with a conditional branch
2373  // that matches select's condition (maybe inverted).
2374  auto *IDomNode = DT[BB]->getIDom();
2375  if (!IDomNode)
2376  return nullptr;
2377  BasicBlock *IDom = IDomNode->getBlock();
2378 
2379  Value *Cond = Sel.getCondition();
2380  Value *IfTrue, *IfFalse;
2381  BasicBlock *TrueSucc, *FalseSucc;
2382  if (match(IDom->getTerminator(),
2383  m_Br(m_Specific(Cond), m_BasicBlock(TrueSucc),
2384  m_BasicBlock(FalseSucc)))) {
2385  IfTrue = Sel.getTrueValue();
2386  IfFalse = Sel.getFalseValue();
2387  } else if (match(IDom->getTerminator(),
2388  m_Br(m_Not(m_Specific(Cond)), m_BasicBlock(TrueSucc),
2389  m_BasicBlock(FalseSucc)))) {
2390  IfTrue = Sel.getFalseValue();
2391  IfFalse = Sel.getTrueValue();
2392  } else
2393  return nullptr;
2394 
2395  // Make sure the branches are actually different.
2396  if (TrueSucc == FalseSucc)
2397  return nullptr;
2398 
2399  // We want to replace select %cond, %a, %b with a phi that takes value %a
2400  // for all incoming edges that are dominated by condition `%cond == true`,
2401  // and value %b for edges dominated by condition `%cond == false`. If %a
2402  // or %b are also phis from the same basic block, we can go further and take
2403  // their incoming values from the corresponding blocks.
2404  BasicBlockEdge TrueEdge(IDom, TrueSucc);
2405  BasicBlockEdge FalseEdge(IDom, FalseSucc);
2407  for (auto *Pred : predecessors(BB)) {
2408  // Check implication.
2409  BasicBlockEdge Incoming(Pred, BB);
2410  if (DT.dominates(TrueEdge, Incoming))
2411  Inputs[Pred] = IfTrue->DoPHITranslation(BB, Pred);
2412  else if (DT.dominates(FalseEdge, Incoming))
2413  Inputs[Pred] = IfFalse->DoPHITranslation(BB, Pred);
2414  else
2415  return nullptr;
2416  // Check availability.
2417  if (auto *Insn = dyn_cast<Instruction>(Inputs[Pred]))
2418  if (!DT.dominates(Insn, Pred->getTerminator()))
2419  return nullptr;
2420  }
2421 
2422  Builder.SetInsertPoint(&*BB->begin());
2423  auto *PN = Builder.CreatePHI(Sel.getType(), Inputs.size());
2424  for (auto *Pred : predecessors(BB))
2425  PN->addIncoming(Inputs[Pred], Pred);
2426  PN->takeName(&Sel);
2427  return PN;
2428 }
2429 
2430 static Instruction *foldSelectToPhi(SelectInst &Sel, const DominatorTree &DT,
2432  // Try to replace this select with Phi in one of these blocks.
2433  SmallSetVector<BasicBlock *, 4> CandidateBlocks;
2434  CandidateBlocks.insert(Sel.getParent());
2435  for (Value *V : Sel.operands())
2436  if (auto *I = dyn_cast<Instruction>(V))
2437  CandidateBlocks.insert(I->getParent());
2438 
2439  for (BasicBlock *BB : CandidateBlocks)
2440  if (auto *PN = foldSelectToPhiImpl(Sel, BB, DT, Builder))
2441  return PN;
2442  return nullptr;
2443 }
2444 
2445 static Value *foldSelectWithFrozenICmp(SelectInst &Sel, InstCombiner::BuilderTy &Builder) {
2446  FreezeInst *FI = dyn_cast<FreezeInst>(Sel.getCondition());
2447  if (!FI)
2448  return nullptr;
2449 
2450  Value *Cond = FI->getOperand(0);
2451  Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
2452 
2453  // select (freeze(x == y)), x, y --> y
2454  // select (freeze(x != y)), x, y --> x
2455  // The freeze should be only used by this select. Otherwise, remaining uses of
2456  // the freeze can observe a contradictory value.
2457  // c = freeze(x == y) ; Let's assume that y = poison & x = 42; c is 0 or 1
2458  // a = select c, x, y ;
2459  // f(a, c) ; f(poison, 1) cannot happen, but if a is folded
2460  // ; to y, this can happen.
2461  CmpInst::Predicate Pred;
2462  if (FI->hasOneUse() &&
2464  (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)) {
2465  return Pred == ICmpInst::ICMP_EQ ? FalseVal : TrueVal;
2466  }
2467 
2468  return nullptr;
2469 }
2470 
2471 Instruction *InstCombinerImpl::foldAndOrOfSelectUsingImpliedCond(Value *Op,
2472  SelectInst &SI,
2473  bool IsAnd) {
2474  Value *CondVal = SI.getCondition();
2475  Value *A = SI.getTrueValue();
2476  Value *B = SI.getFalseValue();
2477 
2478  assert(Op->getType()->isIntOrIntVectorTy(1) &&
2479  "Op must be either i1 or vector of i1.");
2480 
2481  Optional<bool> Res = isImpliedCondition(Op, CondVal, DL, IsAnd);
2482  if (!Res)
2483  return nullptr;
2484 
2485  Value *Zero = Constant::getNullValue(A->getType());
2486  Value *One = Constant::getAllOnesValue(A->getType());
2487 
2488  if (*Res == true) {
2489  if (IsAnd)
2490  // select op, (select cond, A, B), false => select op, A, false
2491  // and op, (select cond, A, B) => select op, A, false
2492  // if op = true implies condval = true.
2493  return SelectInst::Create(Op, A, Zero);
2494  else
2495  // select op, true, (select cond, A, B) => select op, true, A
2496  // or op, (select cond, A, B) => select op, true, A
2497  // if op = false implies condval = true.
2498  return SelectInst::Create(Op, One, A);
2499  } else {
2500  if (IsAnd)
2501  // select op, (select cond, A, B), false => select op, B, false
2502  // and op, (select cond, A, B) => select op, B, false
2503  // if op = true implies condval = false.
2504  return SelectInst::Create(Op, B, Zero);
2505  else
2506  // select op, true, (select cond, A, B) => select op, true, B
2507  // or op, (select cond, A, B) => select op, true, B
2508  // if op = false implies condval = false.
2509  return SelectInst::Create(Op, One, B);
2510  }
2511 }
2512 
2513 // Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need
2514 // fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work.
2515 static Instruction *foldSelectWithFCmpToFabs(SelectInst &SI,
2516  InstCombinerImpl &IC) {
2517  Value *CondVal = SI.getCondition();
2518 
2519  for (bool Swap : {false, true}) {
2520  Value *TrueVal = SI.getTrueValue();
2521  Value *X = SI.getFalseValue();
2522  CmpInst::Predicate Pred;
2523 
2524  if (Swap)
2525  std::swap(TrueVal, X);
2526 
2527  if (!match(CondVal, m_FCmp(Pred, m_Specific(X), m_AnyZeroFP())))
2528  continue;
2529 
2530  // fold (X <= +/-0.0) ? (0.0 - X) : X to fabs(X), when 'Swap' is false
2531  // fold (X > +/-0.0) ? X : (0.0 - X) to fabs(X), when 'Swap' is true
2532  if (match(TrueVal, m_FSub(m_PosZeroFP(), m_Specific(X)))) {
2533  if (!Swap && (Pred == FCmpInst::FCMP_OLE || Pred == FCmpInst::FCMP_ULE)) {
2534  Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2535  return IC.replaceInstUsesWith(SI, Fabs);
2536  }
2537  if (Swap && (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_UGT)) {
2538  Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2539  return IC.replaceInstUsesWith(SI, Fabs);
2540  }
2541  }
2542 
2543  // With nsz, when 'Swap' is false:
2544  // fold (X < +/-0.0) ? -X : X or (X <= +/-0.0) ? -X : X to fabs(X)
2545  // fold (X > +/-0.0) ? -X : X or (X >= +/-0.0) ? -X : X to -fabs(x)
2546  // when 'Swap' is true:
2547  // fold (X > +/-0.0) ? X : -X or (X >= +/-0.0) ? X : -X to fabs(X)
2548  // fold (X < +/-0.0) ? X : -X or (X <= +/-0.0) ? X : -X to -fabs(X)
2549  if (!match(TrueVal, m_FNeg(m_Specific(X))) || !SI.hasNoSignedZeros())
2550  return nullptr;
2551 
2552  if (Swap)
2553  Pred = FCmpInst::getSwappedPredicate(Pred);
2554 
2555  bool IsLTOrLE = Pred == FCmpInst::FCMP_OLT || Pred == FCmpInst::FCMP_OLE ||
2556  Pred == FCmpInst::FCMP_ULT || Pred == FCmpInst::FCMP_ULE;
2557  bool IsGTOrGE = Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_OGE ||
2558  Pred == FCmpInst::FCMP_UGT || Pred == FCmpInst::FCMP_UGE;
2559 
2560  if (IsLTOrLE) {
2561  Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2562  return IC.replaceInstUsesWith(SI, Fabs);
2563  }
2564  if (IsGTOrGE) {
2565  Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2566  Instruction *NewFNeg = UnaryOperator::CreateFNeg(Fabs);
2567  NewFNeg->setFastMathFlags(SI.getFastMathFlags());
2568  return NewFNeg;
2569  }
2570  }
2571 
2572  return nullptr;
2573 }
2574 
2575 // Match the following IR pattern:
2576 // %x.lowbits = and i8 %x, %lowbitmask
2577 // %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 0
2578 // %x.biased = add i8 %x, %bias
2579 // %x.biased.highbits = and i8 %x.biased, %highbitmask
2580 // %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
2581 // Define:
2582 // %alignment = add i8 %lowbitmask, 1
2583 // Iff 1. an %alignment is a power-of-two (aka, %lowbitmask is a low bit mask)
2584 // and 2. %bias is equal to either %lowbitmask or %alignment,
2585 // and 3. %highbitmask is equal to ~%lowbitmask (aka, to -%alignment)
2586 // then this pattern can be transformed into:
2587 // %x.offset = add i8 %x, %lowbitmask
2588 // %x.roundedup = and i8 %x.offset, %highbitmask
2589 static Value *
2590 foldRoundUpIntegerWithPow2Alignment(SelectInst &SI,
2592  Value *Cond = SI.getCondition();
2593  Value *X = SI.getTrueValue();
2594  Value *XBiasedHighBits = SI.getFalseValue();
2595 
2596  ICmpInst::Predicate Pred;
2597  Value *XLowBits;
2598  if (!match(Cond, m_ICmp(Pred, m_Value(XLowBits), m_ZeroInt())) ||
2599  !ICmpInst::isEquality(Pred))
2600  return nullptr;
2601 
2602  if (Pred == ICmpInst::Predicate::ICMP_NE)
2603  std::swap(X, XBiasedHighBits);
2604 
2605  // FIXME: we could support non non-splats here.
2606 
2607  const APInt *LowBitMaskCst;
2608  if (!match(XLowBits, m_And(m_Specific(X), m_APIntAllowUndef(LowBitMaskCst))))
2609  return nullptr;
2610 
2611  // Match even if the AND and ADD are swapped.
2612  const APInt *BiasCst, *HighBitMaskCst;
2613  if (!match(XBiasedHighBits,
2615  m_APIntAllowUndef(HighBitMaskCst))) &&
2616  !match(XBiasedHighBits,
2617  m_Add(m_And(m_Specific(X), m_APIntAllowUndef(HighBitMaskCst)),
2618  m_APIntAllowUndef(BiasCst))))
2619  return nullptr;
2620 
2621  if (!LowBitMaskCst->isMask())
2622  return nullptr;
2623 
2624  APInt InvertedLowBitMaskCst = ~*LowBitMaskCst;
2625  if (InvertedLowBitMaskCst != *HighBitMaskCst)
2626  return nullptr;
2627 
2628  APInt AlignmentCst = *LowBitMaskCst + 1;
2629 
2630  if (*BiasCst != AlignmentCst && *BiasCst != *LowBitMaskCst)
2631  return nullptr;
2632 
2633  if (!XBiasedHighBits->hasOneUse()) {
2634  if (*BiasCst == *LowBitMaskCst)
2635  return XBiasedHighBits;
2636  return nullptr;
2637  }
2638 
2639  // FIXME: could we preserve undef's here?
2640  Type *Ty = X->getType();
2641  Value *XOffset = Builder.CreateAdd(X, ConstantInt::get(Ty, *LowBitMaskCst),
2642  X->getName() + ".biased");
2643  Value *R = Builder.CreateAnd(XOffset, ConstantInt::get(Ty, *HighBitMaskCst));
2644  R->takeName(&SI);
2645  return R;
2646 }
2647 
2649  Value *CondVal = SI.getCondition();
2650  Value *TrueVal = SI.getTrueValue();
2651  Value *FalseVal = SI.getFalseValue();
2652  Type *SelType = SI.getType();
2653 
2654  // Avoid potential infinite loops by checking for non-constant condition.
2655  // TODO: Can we assert instead by improving canonicalizeSelectToShuffle()?
2656  // Scalar select must have simplified?
2657  if (!SelType->isIntOrIntVectorTy(1) || isa<Constant>(CondVal) ||
2658  TrueVal->getType() != CondVal->getType())
2659  return nullptr;
2660 
2661  // Folding select to and/or i1 isn't poison safe in general. impliesPoison
2662  // checks whether folding it does not convert a well-defined value into
2663  // poison.
2664  if (match(TrueVal, m_One())) {
2665  if (impliesPoison(FalseVal, CondVal)) {
2666  // Change: A = select B, true, C --> A = or B, C
2667  return BinaryOperator::CreateOr(CondVal, FalseVal);
2668  }
2669 
2670  if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
2671  if (auto *RHS = dyn_cast<FCmpInst>(FalseVal))
2672  if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ false,
2673  /*IsSelectLogical*/ true))
2674  return replaceInstUsesWith(SI, V);
2675  }
2676  if (match(FalseVal, m_Zero())) {
2677  if (impliesPoison(TrueVal, CondVal)) {
2678  // Change: A = select B, C, false --> A = and B, C
2679  return BinaryOperator::CreateAnd(CondVal, TrueVal);
2680  }
2681 
2682  if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
2683  if (auto *RHS = dyn_cast<FCmpInst>(TrueVal))
2684  if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ true,
2685  /*IsSelectLogical*/ true))
2686  return replaceInstUsesWith(SI, V);
2687  }
2688 
2689  auto *One = ConstantInt::getTrue(SelType);
2690  auto *Zero = ConstantInt::getFalse(SelType);
2691 
2692  // We match the "full" 0 or 1 constant here to avoid a potential infinite
2693  // loop with vectors that may have undefined/poison elements.
2694  // select a, false, b -> select !a, b, false
2695  if (match(TrueVal, m_Specific(Zero))) {
2696  Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2697  return SelectInst::Create(NotCond, FalseVal, Zero);
2698  }
2699  // select a, b, true -> select !a, true, b
2700  if (match(FalseVal, m_Specific(One))) {
2701  Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2702  return SelectInst::Create(NotCond, One, TrueVal);
2703  }
2704 
2705  Value *A, *B;
2706 
2707  // DeMorgan in select form: !a && !b --> !(a || b)
2708  // select !a, !b, false --> not (select a, true, b)
2709  if (match(&SI, m_LogicalAnd(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
2710  (CondVal->hasOneUse() || TrueVal->hasOneUse()) &&
2711  !match(A, m_ConstantExpr()) && !match(B, m_ConstantExpr()))
2712  return BinaryOperator::CreateNot(Builder.CreateSelect(A, One, B));
2713 
2714  // DeMorgan in select form: !a || !b --> !(a && b)
2715  // select !a, true, !b --> not (select a, b, false)
2716  if (match(&SI, m_LogicalOr(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
2717  (CondVal->hasOneUse() || FalseVal->hasOneUse()) &&
2718  !match(A, m_ConstantExpr()) && !match(B, m_ConstantExpr()))
2719  return BinaryOperator::CreateNot(Builder.CreateSelect(A, B, Zero));
2720 
2721  // select (select a, true, b), true, b -> select a, true, b
2722  if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
2724  return replaceOperand(SI, 0, A);
2725  // select (select a, b, false), b, false -> select a, b, false
2726  if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
2728  return replaceOperand(SI, 0, A);
2729 
2730  // ~(A & B) & (A | B) --> A ^ B
2733  return BinaryOperator::CreateXor(A, B);
2734 
2735  Value *C;
2736  // select (~a | c), a, b -> and a, (or c, freeze(b))
2737  if (match(CondVal, m_c_Or(m_Not(m_Specific(TrueVal)), m_Value(C))) &&
2738  CondVal->hasOneUse()) {
2739  FalseVal = Builder.CreateFreeze(FalseVal);
2740  return BinaryOperator::CreateAnd(TrueVal, Builder.CreateOr(C, FalseVal));
2741  }
2742  // select (~c & b), a, b -> and b, (or freeze(a), c)
2743  if (match(CondVal, m_c_And(m_Not(m_Value(C)), m_Specific(FalseVal))) &&
2744  CondVal->hasOneUse()) {
2745  TrueVal = Builder.CreateFreeze(TrueVal);
2746  return BinaryOperator::CreateAnd(FalseVal, Builder.CreateOr(C, TrueVal));
2747  }
2748 
2749  if (match(FalseVal, m_Zero()) || match(TrueVal, m_One())) {
2750  Use *Y = nullptr;
2751  bool IsAnd = match(FalseVal, m_Zero()) ? true : false;
2752  Value *Op1 = IsAnd ? TrueVal : FalseVal;
2753  if (isCheckForZeroAndMulWithOverflow(CondVal, Op1, IsAnd, Y)) {
2754  auto *FI = new FreezeInst(*Y, (*Y)->getName() + ".fr");
2755  InsertNewInstBefore(FI, *cast<Instruction>(Y->getUser()));
2756  replaceUse(*Y, FI);
2757  return replaceInstUsesWith(SI, Op1);
2758  }
2759 
2760  if (auto *Op1SI = dyn_cast<SelectInst>(Op1))
2761  if (auto *I = foldAndOrOfSelectUsingImpliedCond(CondVal, *Op1SI,
2762  /* IsAnd */ IsAnd))
2763  return I;
2764 
2765  if (auto *ICmp0 = dyn_cast<ICmpInst>(CondVal))
2766  if (auto *ICmp1 = dyn_cast<ICmpInst>(Op1))
2767  if (auto *V = foldAndOrOfICmps(ICmp0, ICmp1, SI, IsAnd,
2768  /* IsLogical */ true))
2769  return replaceInstUsesWith(SI, V);
2770  }
2771 
2772  // select (a || b), c, false -> select a, c, false
2773  // select c, (a || b), false -> select c, a, false
2774  // if c implies that b is false.
2775  if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
2776  match(FalseVal, m_Zero())) {
2778  if (Res && *Res == false)
2779  return replaceOperand(SI, 0, A);
2780  }
2781  if (match(TrueVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
2782  match(FalseVal, m_Zero())) {
2783  Optional<bool> Res = isImpliedCondition(CondVal, B, DL);
2784  if (Res && *Res == false)
2785  return replaceOperand(SI, 1, A);
2786  }
2787  // select c, true, (a && b) -> select c, true, a
2788  // select (a && b), true, c -> select a, true, c
2789  // if c = false implies that b = true
2790  if (match(TrueVal, m_One()) &&
2792  Optional<bool> Res = isImpliedCondition(CondVal, B, DL, false);
2793  if (Res && *Res == true)
2794  return replaceOperand(SI, 2, A);
2795  }
2796  if (match(CondVal, m_LogicalAnd(m_Value(A), m_Value(B))) &&
2797  match(TrueVal, m_One())) {
2798  Optional<bool> Res = isImpliedCondition(FalseVal, B, DL, false);
2799  if (Res && *Res == true)
2800  return replaceOperand(SI, 0, A);
2801  }
2802 
2803  if (match(TrueVal, m_One())) {
2804  Value *C;
2805 
2806  // (C && A) || (!C && B) --> sel C, A, B
2807  // (A && C) || (!C && B) --> sel C, A, B
2808  // (C && A) || (B && !C) --> sel C, A, B
2809  // (A && C) || (B && !C) --> sel C, A, B (may require freeze)
2811  match(CondVal, m_c_LogicalAnd(m_Specific(C), m_Value(A)))) {
2812  auto *SelCond = dyn_cast<SelectInst>(CondVal);
2813  auto *SelFVal = dyn_cast<SelectInst>(FalseVal);
2814  bool MayNeedFreeze = SelCond && SelFVal &&
2815  match(SelFVal->getTrueValue(),
2816  m_Not(m_Specific(SelCond->getTrueValue())));
2817  if (MayNeedFreeze)
2818  C = Builder.CreateFreeze(C);
2819  return SelectInst::Create(C, A, B);
2820  }
2821 
2822  // (!C && A) || (C && B) --> sel C, B, A
2823  // (A && !C) || (C && B) --> sel C, B, A
2824  // (!C && A) || (B && C) --> sel C, B, A
2825  // (A && !C) || (B && C) --> sel C, B, A (may require freeze)
2826  if (match(CondVal, m_c_LogicalAnd(m_Not(m_Value(C)), m_Value(A))) &&
2828  auto *SelCond = dyn_cast<SelectInst>(CondVal);
2829  auto *SelFVal = dyn_cast<SelectInst>(FalseVal);
2830  bool MayNeedFreeze = SelCond && SelFVal &&
2831  match(SelCond->getTrueValue(),
2832  m_Not(m_Specific(SelFVal->getTrueValue())));
2833  if (MayNeedFreeze)
2834  C = Builder.CreateFreeze(C);
2835  return SelectInst::Create(C, B, A);
2836  }
2837  }
2838 
2839  return nullptr;
2840 }
2841 
2843  Value *CondVal = SI.getCondition();
2844  Value *TrueVal = SI.getTrueValue();
2845  Value *FalseVal = SI.getFalseValue();
2846  Type *SelType = SI.getType();
2847 
2848  if (Value *V = simplifySelectInst(CondVal, TrueVal, FalseVal,
2849  SQ.getWithInstruction(&SI)))
2850  return replaceInstUsesWith(SI, V);
2851 
2852  if (Instruction *I = canonicalizeSelectToShuffle(SI))
2853  return I;
2854 
2855  if (Instruction *I = canonicalizeScalarSelectOfVecs(SI, *this))
2856  return I;
2857 
2858  // If the type of select is not an integer type or if the condition and
2859  // the selection type are not both scalar nor both vector types, there is no
2860  // point in attempting to match these patterns.
2861  Type *CondType = CondVal->getType();
2862  if (!isa<Constant>(CondVal) && SelType->isIntOrIntVectorTy() &&
2863  CondType->isVectorTy() == SelType->isVectorTy()) {
2864  if (Value *S = simplifyWithOpReplaced(TrueVal, CondVal,
2865  ConstantInt::getTrue(CondType), SQ,
2866  /* AllowRefinement */ true))
2867  return replaceOperand(SI, 1, S);
2868 
2869  if (Value *S = simplifyWithOpReplaced(FalseVal, CondVal,
2870  ConstantInt::getFalse(CondType), SQ,
2871  /* AllowRefinement */ true))
2872  return replaceOperand(SI, 2, S);
2873 
2874  // Handle patterns involving sext/zext + not explicitly,
2875  // as simplifyWithOpReplaced() only looks past one instruction.
2876  Value *NotCond;
2877 
2878  // select a, sext(!a), b -> select !a, b, 0
2879  // select a, zext(!a), b -> select !a, b, 0
2881  m_Not(m_Specific(CondVal))))))
2882  return SelectInst::Create(NotCond, FalseVal,
2883  Constant::getNullValue(SelType));
2884 
2885  // select a, b, zext(!a) -> select !a, 1, b
2886  if (match(FalseVal, m_ZExt(m_CombineAnd(m_Value(NotCond),
2887  m_Not(m_Specific(CondVal))))))
2888  return SelectInst::Create(NotCond, ConstantInt::get(SelType, 1), TrueVal);
2889 
2890  // select a, b, sext(!a) -> select !a, -1, b
2891  if (match(FalseVal, m_SExt(m_CombineAnd(m_Value(NotCond),
2892  m_Not(m_Specific(CondVal))))))
2893  return SelectInst::Create(NotCond, Constant::getAllOnesValue(SelType),
2894  TrueVal);
2895  }
2896 
2897  if (Instruction *R = foldSelectOfBools(SI))
2898  return R;
2899 
2900  // Selecting between two integer or vector splat integer constants?
2901  //
2902  // Note that we don't handle a scalar select of vectors:
2903  // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>
2904  // because that may need 3 instructions to splat the condition value:
2905  // extend, insertelement, shufflevector.
2906  //
2907  // Do not handle i1 TrueVal and FalseVal otherwise would result in
2908  // zext/sext i1 to i1.
2909  if (SelType->isIntOrIntVectorTy() && !SelType->isIntOrIntVectorTy(1) &&
2910  CondVal->getType()->isVectorTy() == SelType->isVectorTy()) {
2911  // select C, 1, 0 -> zext C to int
2912  if (match(TrueVal, m_One()) && match(FalseVal, m_Zero()))
2913  return new ZExtInst(CondVal, SelType);
2914 
2915  // select C, -1, 0 -> sext C to int
2916  if (match(TrueVal, m_AllOnes()) && match(FalseVal, m_Zero()))
2917  return new SExtInst(CondVal, SelType);
2918 
2919  // select C, 0, 1 -> zext !C to int
2920  if (match(TrueVal, m_Zero()) && match(FalseVal, m_One())) {
2921  Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2922  return new ZExtInst(NotCond, SelType);
2923  }
2924 
2925  // select C, 0, -1 -> sext !C to int
2926  if (match(TrueVal, m_Zero()) && match(FalseVal, m_AllOnes())) {
2927  Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2928  return new SExtInst(NotCond, SelType);
2929  }
2930  }
2931 
2932  if (auto *FCmp = dyn_cast<FCmpInst>(CondVal)) {
2933  Value *Cmp0 = FCmp->getOperand(0), *Cmp1 = FCmp->getOperand(1);
2934  // Are we selecting a value based on a comparison of the two values?
2935  if ((Cmp0 == TrueVal && Cmp1 == FalseVal) ||
2936  (Cmp0 == FalseVal && Cmp1 == TrueVal)) {
2937  // Canonicalize to use ordered comparisons by swapping the select
2938  // operands.
2939  //
2940  // e.g.
2941  // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X
2942  if (FCmp->hasOneUse() && FCmpInst::isUnordered(FCmp->getPredicate())) {
2943  FCmpInst::Predicate InvPred = FCmp->getInversePredicate();
2945  // FIXME: The FMF should propagate from the select, not the fcmp.
2946  Builder.setFastMathFlags(FCmp->getFastMathFlags());
2947  Value *NewCond = Builder.CreateFCmp(InvPred, Cmp0, Cmp1,
2948  FCmp->getName() + ".inv");
2949  Value *NewSel = Builder.CreateSelect(NewCond, FalseVal, TrueVal);
2950  return replaceInstUsesWith(SI, NewSel);
2951  }
2952 
2953  // NOTE: if we wanted to, this is where to detect MIN/MAX
2954  }
2955  }
2956 
2957  // Fold selecting to fabs.
2958  if (Instruction *Fabs = foldSelectWithFCmpToFabs(SI, *this))
2959  return Fabs;
2960 
2961  // See if we are selecting two values based on a comparison of the two values.
2962  if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal))
2963  if (Instruction *Result = foldSelectInstWithICmp(SI, ICI))
2964  return Result;
2965 
2966  if (Instruction *Add = foldAddSubSelect(SI, Builder))
2967  return Add;
2968  if (Instruction *Add = foldOverflowingAddSubSelect(SI, Builder))
2969  return Add;
2970  if (Instruction *Or = foldSetClearBits(SI, Builder))
2971  return Or;
2972  if (Instruction *Mul = foldSelectZeroOrMul(SI, *this))
2973  return Mul;
2974 
2975  // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
2976  auto *TI = dyn_cast<Instruction>(TrueVal);
2977  auto *FI = dyn_cast<Instruction>(FalseVal);
2978  if (TI && FI && TI->getOpcode() == FI->getOpcode())
2979  if (Instruction *IV = foldSelectOpOp(SI, TI, FI))
2980  return IV;
2981 
2982  if (Instruction *I = foldSelectExtConst(SI))
2983  return I;
2984 
2985  // Fold (select C, (gep Ptr, Idx), Ptr) -> (gep Ptr, (select C, Idx, 0))
2986  // Fold (select C, Ptr, (gep Ptr, Idx)) -> (gep Ptr, (select C, 0, Idx))
2987  auto SelectGepWithBase = [&](GetElementPtrInst *Gep, Value *Base,
2988  bool Swap) -> GetElementPtrInst * {
2989  Value *Ptr = Gep->getPointerOperand();
2990  if (Gep->getNumOperands() != 2 || Gep->getPointerOperand() != Base ||
2991  !Gep->hasOneUse())
2992  return nullptr;
2993  Value *Idx = Gep->getOperand(1);
2994  if (isa<VectorType>(CondVal->getType()) && !isa<VectorType>(Idx->getType()))
2995  return nullptr;
2996  Type *ElementType = Gep->getResultElementType();
2997  Value *NewT = Idx;
2998  Value *NewF = Constant::getNullValue(Idx->getType());
2999  if (Swap)
3000  std::swap(NewT, NewF);
3001  Value *NewSI =
3002  Builder.CreateSelect(CondVal, NewT, NewF, SI.getName() + ".idx", &SI);
3003  return GetElementPtrInst::Create(ElementType, Ptr, {NewSI});
3004  };
3005  if (auto *TrueGep = dyn_cast<GetElementPtrInst>(TrueVal))
3006  if (auto *NewGep = SelectGepWithBase(TrueGep, FalseVal, false))
3007  return NewGep;
3008  if (auto *FalseGep = dyn_cast<GetElementPtrInst>(FalseVal))
3009  if (auto *NewGep = SelectGepWithBase(FalseGep, TrueVal, true))
3010  return NewGep;
3011 
3012  // See if we can fold the select into one of our operands.
3013  if (SelType->isIntOrIntVectorTy() || SelType->isFPOrFPVectorTy()) {
3014  if (Instruction *FoldI = foldSelectIntoOp(SI, TrueVal, FalseVal))
3015  return FoldI;
3016 
3017  Value *LHS, *RHS;
3018  Instruction::CastOps CastOp;
3019  SelectPatternResult SPR = matchSelectPattern(&SI, LHS, RHS, &CastOp);
3020  auto SPF = SPR.Flavor;
3021  if (SPF) {
3022  Value *LHS2, *RHS2;
3023  if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor)
3024  if (Instruction *R = foldSPFofSPF(cast<Instruction>(LHS), SPF2, LHS2,
3025  RHS2, SI, SPF, RHS))
3026  return R;
3027  if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor)
3028  if (Instruction *R = foldSPFofSPF(cast<Instruction>(RHS), SPF2, LHS2,
3029  RHS2, SI, SPF, LHS))
3030  return R;
3031  }
3032 
3034  // Canonicalize so that
3035  // - type casts are outside select patterns.
3036  // - float clamp is transformed to min/max pattern
3037 
3038  bool IsCastNeeded = LHS->getType() != SelType;
3039  Value *CmpLHS = cast<CmpInst>(CondVal)->getOperand(0);
3040  Value *CmpRHS = cast<CmpInst>(CondVal)->getOperand(1);
3041  if (IsCastNeeded ||
3042  (LHS->getType()->isFPOrFPVectorTy() &&
3043  ((CmpLHS != LHS && CmpLHS != RHS) ||
3044  (CmpRHS != LHS && CmpRHS != RHS)))) {
3045  CmpInst::Predicate MinMaxPred = getMinMaxPred(SPF, SPR.Ordered);
3046 
3047  Value *Cmp;
3048  if (CmpInst::isIntPredicate(MinMaxPred)) {
3049  Cmp = Builder.CreateICmp(MinMaxPred, LHS, RHS);
3050  } else {
3052  auto FMF =
3053  cast<FPMathOperator>(SI.getCondition())->getFastMathFlags();
3054  Builder.setFastMathFlags(FMF);
3055  Cmp = Builder.CreateFCmp(MinMaxPred, LHS, RHS);
3056  }
3057 
3058  Value *NewSI = Builder.CreateSelect(Cmp, LHS, RHS, SI.getName(), &SI);
3059  if (!IsCastNeeded)
3060  return replaceInstUsesWith(SI, NewSI);
3061 
3062  Value *NewCast = Builder.CreateCast(CastOp, NewSI, SelType);
3063  return replaceInstUsesWith(SI, NewCast);
3064  }
3065  }
3066  }
3067 
3068  // Canonicalize select of FP values where NaN and -0.0 are not valid as
3069  // minnum/maxnum intrinsics.
3070  if (isa<FPMathOperator>(SI) && SI.hasNoNaNs() && SI.hasNoSignedZeros()) {
3071  Value *X, *Y;
3072  if (match(&SI, m_OrdFMax(m_Value(X), m_Value(Y))))
3073  return replaceInstUsesWith(
3074  SI, Builder.CreateBinaryIntrinsic(Intrinsic::maxnum, X, Y, &SI));
3075 
3076  if (match(&SI, m_OrdFMin(m_Value(X), m_Value(Y))))
3077  return replaceInstUsesWith(
3078  SI, Builder.CreateBinaryIntrinsic(Intrinsic::minnum, X, Y, &SI));
3079  }
3080 
3081  // See if we can fold the select into a phi node if the condition is a select.
3082  if (auto *PN = dyn_cast<PHINode>(SI.getCondition()))
3083  // The true/false values have to be live in the PHI predecessor's blocks.
3084  if (canSelectOperandBeMappingIntoPredBlock(TrueVal, SI) &&
3085  canSelectOperandBeMappingIntoPredBlock(FalseVal, SI))
3086  if (Instruction *NV = foldOpIntoPhi(SI, PN))
3087  return NV;
3088 
3089  if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) {
3090  if (TrueSI->getCondition()->getType() == CondVal->getType()) {
3091  // select(C, select(C, a, b), c) -> select(C, a, c)
3092  if (TrueSI->getCondition() == CondVal) {
3093  if (SI.getTrueValue() == TrueSI->getTrueValue())
3094  return nullptr;
3095  return replaceOperand(SI, 1, TrueSI->getTrueValue());
3096  }
3097  // select(C0, select(C1, a, b), b) -> select(C0&C1, a, b)
3098  // We choose this as normal form to enable folding on the And and
3099  // shortening paths for the values (this helps getUnderlyingObjects() for
3100  // example).
3101  if (TrueSI->getFalseValue() == FalseVal && TrueSI->hasOneUse()) {
3102  Value *And = Builder.CreateLogicalAnd(CondVal, TrueSI->getCondition());
3103  replaceOperand(SI, 0, And);
3104  replaceOperand(SI, 1, TrueSI->getTrueValue());
3105  return &SI;
3106  }
3107  }
3108  }
3109  if (SelectInst *FalseSI = dyn_cast<SelectInst>(FalseVal)) {
3110  if (FalseSI->getCondition()->getType() == CondVal->getType()) {
3111  // select(C, a, select(C, b, c)) -> select(C, a, c)
3112  if (FalseSI->getCondition() == CondVal) {
3113  if (SI.getFalseValue() == FalseSI->getFalseValue())
3114  return nullptr;
3115  return replaceOperand(SI, 2, FalseSI->getFalseValue());
3116  }
3117  // select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b)
3118  if (FalseSI->getTrueValue() == TrueVal && FalseSI->hasOneUse()) {
3119  Value *Or = Builder.CreateLogicalOr(CondVal, FalseSI->getCondition());
3120  replaceOperand(SI, 0, Or);
3121  replaceOperand(SI, 2, FalseSI->getFalseValue());
3122  return &SI;
3123  }
3124  }
3125  }
3126 
3127  auto canMergeSelectThroughBinop = [](BinaryOperator *BO) {
3128  // The select might be preventing a division by 0.
3129  switch (BO->getOpcode()) {
3130  default:
3131  return true;
3132  case Instruction::SRem:
3133  case Instruction::URem:
3134  case Instruction::SDiv:
3135  case Instruction::UDiv:
3136  return false;
3137  }
3138  };
3139 
3140  // Try to simplify a binop sandwiched between 2 selects with the same
3141  // condition.
3142  // select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z)
3143  BinaryOperator *TrueBO;
3144  if (match(TrueVal, m_OneUse(m_BinOp(TrueBO))) &&
3145  canMergeSelectThroughBinop(TrueBO)) {
3146  if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(0))) {
3147  if (TrueBOSI->getCondition() == CondVal) {
3148  replaceOperand(*TrueBO, 0, TrueBOSI->getTrueValue());
3149  Worklist.push(TrueBO);
3150  return &SI;
3151  }
3152  }
3153  if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(1))) {
3154  if (TrueBOSI->getCondition() == CondVal) {
3155  replaceOperand(*TrueBO, 1, TrueBOSI->getTrueValue());
3156  Worklist.push(TrueBO);
3157  return &SI;
3158  }
3159  }
3160  }
3161 
3162  // select(C, Z, binop(select(C, X, Y), W)) -> select(C, Z, binop(Y, W))
3163  BinaryOperator *FalseBO;
3164  if (match(FalseVal, m_OneUse(m_BinOp(FalseBO))) &&
3165  canMergeSelectThroughBinop(FalseBO)) {
3166  if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(0))) {
3167  if (FalseBOSI->getCondition() == CondVal) {
3168  replaceOperand(*FalseBO, 0, FalseBOSI->getFalseValue());
3169  Worklist.push(FalseBO);
3170  return &SI;
3171  }
3172  }
3173  if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(1))) {
3174  if (FalseBOSI->getCondition() == CondVal) {
3175  replaceOperand(*FalseBO, 1, FalseBOSI->getFalseValue());
3176  Worklist.push(FalseBO);
3177  return &SI;
3178  }
3179  }
3180  }
3181 
3182  Value *NotCond;
3183  if (match(CondVal, m_Not(m_Value(NotCond))) &&
3185  replaceOperand(SI, 0, NotCond);
3186  SI.swapValues();
3187  SI.swapProfMetadata();
3188  return &SI;
3189  }
3190 
3191  if (Instruction *I = foldVectorSelect(SI))
3192  return I;
3193 
3194  // If we can compute the condition, there's no need for a select.
3195  // Like the above fold, we are attempting to reduce compile-time cost by
3196  // putting this fold here with limitations rather than in InstSimplify.
3197  // The motivation for this call into value tracking is to take advantage of
3198  // the assumption cache, so make sure that is populated.
3199  if (!CondVal->getType()->isVectorTy() && !AC.assumptions().empty()) {
3200  KnownBits Known(1);
3201  computeKnownBits(CondVal, Known, 0, &SI);
3202  if (Known.One.isOne())
3203  return replaceInstUsesWith(SI, TrueVal);
3204  if (Known.Zero.isOne())
3205  return replaceInstUsesWith(SI, FalseVal);
3206  }
3207 
3208  if (Instruction *BitCastSel = foldSelectCmpBitcasts(SI, Builder))
3209  return BitCastSel;
3210 
3211  // Simplify selects that test the returned flag of cmpxchg instructions.
3212  if (Value *V = foldSelectCmpXchg(SI))
3213  return replaceInstUsesWith(SI, V);
3214 
3215  if (Instruction *Select = foldSelectBinOpIdentity(SI, TLI, *this))
3216  return Select;
3217 
3218  if (Instruction *Funnel = foldSelectFunnelShift(SI, Builder))
3219  return Funnel;
3220 
3221  if (Instruction *Copysign = foldSelectToCopysign(SI, Builder))
3222  return Copysign;
3223 
3224  if (Instruction *PN = foldSelectToPhi(SI, DT, Builder))
3225  return replaceInstUsesWith(SI, PN);
3226 
3227  if (Value *Fr = foldSelectWithFrozenICmp(SI, Builder))
3228  return replaceInstUsesWith(SI, Fr);
3229 
3230  if (Value *V = foldRoundUpIntegerWithPow2Alignment(SI, Builder))
3231  return replaceInstUsesWith(SI, V);
3232 
3233  // select(mask, mload(,,mask,0), 0) -> mload(,,mask,0)
3234  // Load inst is intentionally not checked for hasOneUse()
3235  if (match(FalseVal, m_Zero()) &&
3237  m_CombineOr(m_Undef(), m_Zero()))) ||
3239  m_CombineOr(m_Undef(), m_Zero()))))) {
3240  auto *MaskedInst = cast<IntrinsicInst>(TrueVal);
3241  if (isa<UndefValue>(MaskedInst->getArgOperand(3)))
3242  MaskedInst->setArgOperand(3, FalseVal /* Zero */);
3243  return replaceInstUsesWith(SI, MaskedInst);
3244  }
3245 
3246  Value *Mask;
3247  if (match(TrueVal, m_Zero()) &&
3249  m_CombineOr(m_Undef(), m_Zero()))) ||
3251  m_CombineOr(m_Undef(), m_Zero())))) &&
3252  (CondVal->getType() == Mask->getType())) {
3253  // We can remove the select by ensuring the load zeros all lanes the
3254  // select would have. We determine this by proving there is no overlap
3255  // between the load and select masks.
3256  // (i.e (load_mask & select_mask) == 0 == no overlap)
3257  bool CanMergeSelectIntoLoad = false;
3258  if (Value *V = simplifyAndInst(CondVal, Mask, SQ.getWithInstruction(&SI)))
3259  CanMergeSelectIntoLoad = match(V, m_Zero());
3260 
3261  if (CanMergeSelectIntoLoad) {
3262  auto *MaskedInst = cast<IntrinsicInst>(FalseVal);
3263  if (isa<UndefValue>(MaskedInst->getArgOperand(3)))
3264  MaskedInst->setArgOperand(3, TrueVal /* Zero */);
3265  return replaceInstUsesWith(SI, MaskedInst);
3266  }
3267  }
3268 
3269  return nullptr;
3270 }
i
i
Definition: README.txt:29
llvm::CmpInst::FCMP_ULE
@ FCMP_ULE
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:734
AssumptionCache.h
llvm::InstCombiner::shouldAvoidAbsorbingNotIntoSelect
static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
Definition: InstCombiner.h:218
llvm::SPF_SMAX
@ SPF_SMAX
Unsigned minimum.
Definition: ValueTracking.h:691
foldSelectBinOpIdentity
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.
Definition: InstCombineSelect.cpp:55
llvm::PatternMatch::m_MaskedGather
m_Intrinsic_Ty< Opnd0, Opnd1, Opnd2, Opnd3 >::Ty m_MaskedGather(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2, const Opnd3 &Op3)
Matches MaskedGather Intrinsic.
Definition: PatternMatch.h:2112
foldSelectICmpAnd
static Value * foldSelectICmpAnd(SelectInst &Sel, ICmpInst *Cmp, InstCombiner::BuilderTy &Builder)
This folds: select (icmp eq (and X, C1)), TC, FC iff C1 is a power 2 and the difference between TC an...
Definition: InstCombineSelect.cpp:120
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:849
llvm::IRBuilderBase::SetInsertPoint
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:179
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::isCheckForZeroAndMulWithOverflow
bool isCheckForZeroAndMulWithOverflow(Value *Op0, Value *Op1, bool IsAnd, Use *&Y)
Match one of the patterns up to the select/logic op: Op0 = icmp ne i4 X, 0 Agg = call { i4,...
Definition: OverflowInstAnalysis.cpp:21
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:236
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:69
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:740
llvm::PatternMatch::m_TruncOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1617
Optional.h
llvm::RecurKind::Or
@ Or
Bitwise or logical OR of integers.
llvm::PatternMatch::m_Mask
Definition: PatternMatch.h:1514
CmpInstAnalysis.h
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
InstCombiner.h
llvm::Intrinsic::getDeclaration
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1481
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::Instruction::hasNoSignedZeros
bool hasNoSignedZeros() const LLVM_READONLY
Determine whether the no-signed-zeros flag is set.
Definition: Instruction.cpp:299
IntrinsicInst.h
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2092
llvm::APInt::isMask
bool isMask(unsigned numBits) const
Definition: APInt.h:469
llvm::Function
Definition: Function.h:60
llvm::Instruction::isCast
bool isCast() const
Definition: Instruction.h:172
llvm::isImpliedCondition
Optional< bool > isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, bool LHSIsTrue=true, unsigned Depth=0)
Return true if RHS is known to be implied true by LHS.
Definition: ValueTracking.cpp:6830
llvm::BinaryOperator::CreateNot
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: Instructions.cpp:2992
llvm::IntrinsicInst::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:53
llvm::SelectPatternResult::Flavor
SelectPatternFlavor Flavor
Definition: ValueTracking.h:711
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1117
llvm::APInt::isPowerOf2
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:425
isSelect01
static bool isSelect01(const APInt &C1I, const APInt &C2I)
Definition: InstCombineSelect.cpp:430
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
llvm::InstCombiner::getFlippedStrictnessPredicateAndConstant
static llvm::Optional< std::pair< CmpInst::Predicate, Constant * > > getFlippedStrictnessPredicateAndConstant(CmpInst::Predicate Pred, Constant *C)
Definition: InstCombineCompares.cpp:5854
llvm::isGuaranteedNotToBeUndefOrPoison
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
Definition: ValueTracking.cpp:5439
llvm::Type::getScalarType
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:328
llvm::Instruction::isSameOperationAs
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const LLVM_READONLY
This function determines if the specified instruction executes the same operation as the current one.
Definition: Instruction.cpp:564
llvm::BinaryOpIntrinsic::getRHS
Value * getRHS() const
Definition: IntrinsicInst.h:748
llvm::ConstantExpr::getSExt
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2078
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::InstCombiner::Builder
BuilderTy & Builder
Definition: InstCombiner.h:58
llvm::InstCombinerImpl::InsertNewInstBefore
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
Definition: InstCombineInternal.h:387
llvm::ConstantExpr::getICmp
static Constant * getICmp(unsigned short pred, Constant *LHS, Constant *RHS, bool OnlyIfReduced=false)
get* - Return some common constants without having to specify the full Instruction::OPCODE identifier...
Definition: Constants.cpp:2496
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
llvm::BinaryOpIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:747
ErrorHandling.h
llvm::PatternMatch::m_CombineOr
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:218
llvm::IRBuilder< TargetFolder, IRBuilderCallbackInserter >
llvm::CastInst::Create
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
Definition: Instructions.cpp:3340
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:741
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:833
R600_InstFlag::FC
@ FC
Definition: R600Defines.h:32
llvm::APInt::isOne
bool isOne() const
Determine if this is a value of 1.
Definition: APInt.h:371
ValueTracking.h
canonicalizeSaturatedAdd
static Value * canonicalizeSaturatedAdd(ICmpInst *Cmp, Value *TVal, Value *FVal, InstCombiner::BuilderTy &Builder)
Definition: InstCombineSelect.cpp:832
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::IRBuilderBase::CreateUnaryIntrinsic
CallInst * CreateUnaryIntrinsic(Intrinsic::ID ID, Value *V, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with 1 operand which is mangled on its type.
Definition: IRBuilder.cpp:945
llvm::Type::isFPOrFPVectorTy
bool isFPOrFPVectorTy() const
Return true if this is a FP type or a vector of FP.
Definition: Type.h:198
llvm::PatternMatch::m_Br
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
Definition: PatternMatch.h:1731
llvm::CmpInst::getFlippedStrictnessPredicate
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
Definition: InstrTypes.h:915
APInt.h
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:746
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1792
llvm::APInt::getSignedMaxValue
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1431
llvm::ICmpInst::isEquality
bool isEquality() const
Return true if this predicate is either EQ or NE.
Definition: Instructions.h:1280
llvm::BasicBlockEdge
Definition: Dominators.h:98
T1
#define T1
Definition: Mips16ISelLowering.cpp:340
llvm::FastMathFlags::noSignedZeros
bool noSignedZeros() const
Definition: FMF.h:69
llvm::SPF_UMAX
@ SPF_UMAX
Signed maximum.
Definition: ValueTracking.h:692
llvm::APInt::ugt
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1152
llvm::InstCombinerImpl::replaceInstUsesWith
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombineInternal.h:408
llvm::IRBuilderBase::CreateBinaryIntrinsic
CallInst * CreateBinaryIntrinsic(Intrinsic::ID ID, Value *LHS, Value *RHS, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with 2 operands which is mangled on the first type.
Definition: IRBuilder.cpp:953
llvm::Optional< bool >
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::PatternMatch::m_BinOp
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:84
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::PatternMatch::m_AShr
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1123
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:62
llvm::SelectInst::getFalseValue
const Value * getFalseValue() const
Definition: Instructions.h:1785
getSelectFoldableOperands
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,...
Definition: InstCombineSelect.cpp:240
Operator.h
llvm::codeview::VFTableSlotKind::Outer
@ Outer
STLExtras.h
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::isPowerOf2_32
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:458
llvm::matchSelectPattern
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
Definition: ValueTracking.cpp:6396
llvm::PatternMatch::m_c_And
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
Definition: PatternMatch.h:2251
llvm::BinaryOperator::CreateNeg
NUW NUW NUW NUW Exact static Exact BinaryOperator * CreateNeg(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...
Definition: Instructions.cpp:2952
llvm::PatternMatch::m_Not
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
Definition: PatternMatch.h:2289
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:687
llvm::FastMathFlags
Convenience struct for specifying and reasoning about fast-math flags.
Definition: FMF.h:21
llvm::PatternMatch::m_BitCast
CastClass_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
Definition: PatternMatch.h:1593
llvm::Constant::isOneValue
bool isOneValue() const
Returns true if the value is one.
Definition: Constants.cpp:110
llvm::CmpInst::FCMP_OGT
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:723
llvm::APInt::getZero
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition: APInt.h:177
llvm::PatternMatch::m_Deferred
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
Definition: PatternMatch.h:790
llvm::APIntOps::umin
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
Definition: APInt.h:2157
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:265
KnownBits.h
llvm::PatternMatch::m_FSub
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:997
llvm::ConstantRange::binaryOp
ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
Definition: ConstantRange.cpp:878
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::UndefMaskElem
constexpr int UndefMaskElem
Definition: Instructions.h:1995
llvm::PatternMatch::m_c_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate, true > m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
Definition: PatternMatch.h:2223
llvm::PatternMatch::m_OneUse
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
llvm::CmpInst::FCMP_ULT
@ FCMP_ULT
1 1 0 0 True if unordered or less than
Definition: InstrTypes.h:733
llvm::ConstantExpr::getSub
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2637
llvm::InstCombinerImpl::foldSelectInstWithICmp
Instruction * foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI)
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
Instruction.h
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:278
llvm::SPF_NABS
@ SPF_NABS
Absolute value.
Definition: ValueTracking.h:696
llvm::PatternMatch::m_c_BinOp
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
Definition: PatternMatch.h:2215
llvm::ConstantExpr::getBinOpIdentity
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2714
llvm::PatternMatch::m_UMax
MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty > m_UMax(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1865
llvm::PatternMatch::m_OrdFMin
MaxMin_match< FCmpInst, LHS, RHS, ofmin_pred_ty > m_OrdFMin(const LHS &L, const RHS &R)
Match an 'ordered' floating point minimum function.
Definition: PatternMatch.h:1912
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
foldSelectICmpLshrAshr
static Value * foldSelectICmpLshrAshr(const ICmpInst *IC, Value *TrueVal, Value *FalseVal, InstCombiner::BuilderTy &Builder)
We want to turn: (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1 (select (icmp slt x...
Definition: InstCombineSelect.cpp:552
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:164
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1767
llvm::SelectInst::getCondition
const Value * getCondition() const
Definition: Instructions.h:1783
llvm::RecurKind::And
@ And
Bitwise or logical AND of integers.
InstCombineInternal.h
llvm::InstCombinerImpl::foldSelectIntoOp
Instruction * foldSelectIntoOp(SelectInst &SI, Value *, Value *)
Try to fold the select into one of the operands to allow further optimization.
Definition: InstCombineSelect.cpp:438
llvm::PatternMatch::m_Select
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
Definition: PatternMatch.h:1462
llvm::CmpInst::isFPPredicate
bool isFPPredicate() const
Definition: InstrTypes.h:826
llvm::PatternMatch::m_ZExtOrSExt
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, CastClass_match< OpTy, Instruction::SExt > > m_ZExtOrSExt(const OpTy &Op)
Definition: PatternMatch.h:1648
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::Constant::isNullValue
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:76
llvm::APInt::isZero
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:359
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::InstCombinerImpl::foldSelectOfBools
Instruction * foldSelectOfBools(SelectInst &SI)
llvm::CmpInst::ICMP_ULE
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:745
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
InstrTypes.h
llvm::SelectPatternResult::isMinOrMax
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
Definition: ValueTracking.h:719
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::PatternMatch::m_PosZeroFP
cstfp_pred_ty< is_pos_zero_fp > m_PosZeroFP()
Match a floating-point positive zero.
Definition: PatternMatch.h:673
InstructionWorklist.h
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1516
SI
@ SI
Definition: SIInstrInfo.cpp:7882
llvm::CmpInst::FCMP_UGE
@ FCMP_UGE
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:732
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::APInt::getAllOnes
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:246
llvm::PatternMatch::m_Instruction
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:716
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::PatternMatch::m_ZExt
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:1629
llvm::PatternMatch::m_c_Add
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
Definition: PatternMatch.h:2237
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::PatternMatch::m_MaxOrMin
match_combine_or< match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > >, match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > > > m_MaxOrMin(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1882
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:802
llvm::PatternMatch::m_FNeg
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
Definition: PatternMatch.h:1033
llvm::APFloat::isNegative
bool isNegative() const
Definition: APFloat.h:1230
llvm::Constant::getAllOnesValue
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:395
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:392
llvm::PatternMatch::m_ConstantInt
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:147
llvm::Instruction
Definition: Instruction.h:42
llvm::Type::getScalarSizeInBits
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition: Type.cpp:189
llvm::APInt::isAllOnes
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:347
llvm::PatternMatch::m_UMin
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1871
llvm::PatternMatch::m_c_Or
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
Definition: PatternMatch.h:2258
llvm::APFloat::bitwiseIsEqual
bool bitwiseIsEqual(const APFloat &RHS) const
Definition: APFloat.h:1195
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::InstCombinerImpl
Definition: InstCombineInternal.h:61
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:879
llvm::CmpInst::FCMP_OEQ
@ FCMP_OEQ
0 0 0 1 True if ordered and equal
Definition: InstrTypes.h:722
llvm::CmpInst::FCMP_OLT
@ FCMP_OLT
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:725
PatternMatch.h
llvm::impliesPoison
bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
Definition: ValueTracking.cpp:5301
llvm::PatternMatch::m_APIntAllowUndef
apint_match m_APIntAllowUndef(const APInt *&Res)
Match APInt while allowing undefs in splat vector constants.
Definition: PatternMatch.h:284
llvm::SPF_SMIN
@ SPF_SMIN
Definition: ValueTracking.h:689
Type.h
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::PatternMatch::m_One
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:517
llvm::Instruction::isCommutative
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
Definition: Instruction.cpp:800
llvm::maxnum
LLVM_READONLY APFloat maxnum(const APFloat &A, const APFloat &B)
Implements IEEE maxNum semantics.
Definition: APFloat.h:1322
llvm::PatternMatch::m_ExtractElt
TwoOps_match< Val_t, Idx_t, Instruction::ExtractElement > m_ExtractElt(const Val_t &Val, const Idx_t &Idx)
Matches ExtractElementInst.
Definition: PatternMatch.h:1492
llvm::PatternMatch::m_Power2
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:544
llvm::PatternMatch::m_Xor
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1105
llvm::APInt::getOneBitSet
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:222
llvm::SelectPatternResult
Definition: ValueTracking.h:710
llvm::Instruction::andIRFlags
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
Definition: Instruction.cpp:352
llvm::PatternMatch::m_ZExtOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, OpTy > m_ZExtOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1635
llvm::ConstantExpr::getTrunc
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2064
BasicBlock.h
llvm::APFloat
Definition: APFloat.h:716
canonicalizeSaturatedSubtract
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).
Definition: InstCombineSelect.cpp:777
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::PatternMatch::m_Zero
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:537
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::IRBuilderBase::CreateICmp
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2209
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1185
llvm::InstCombiner::AddOne
static Constant * AddOne(Constant *C)
Add one to a Constant.
Definition: InstCombiner.h:202
llvm::simplifySelectInst
Value * simplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, const SimplifyQuery &Q)
Given operands for a SelectInst, fold the result or return null.
Definition: InstructionSimplify.cpp:4587
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::PatternMatch::m_LogicalOr
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
Definition: PatternMatch.h:2561
llvm::InstCombiner::isCanonicalPredicate
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
Definition: InstCombiner.h:145
llvm::APInt::logBase2
unsigned logBase2() const
Definition: APInt.h:1672
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1099
llvm::PatternMatch::m_AllOnes
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:453
llvm::PatternMatch::m_ImmConstant
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:751
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:928
llvm::SelectInst::getTrueValue
const Value * getTrueValue() const
Definition: Instructions.h:1784
llvm::PatternMatch::m_MaskedLoad
m_Intrinsic_Ty< Opnd0, Opnd1, Opnd2, Opnd3 >::Ty m_MaskedLoad(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2, const Opnd3 &Op3)
Matches MaskedLoad Intrinsic.
Definition: PatternMatch.h:2104
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1093
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1843
llvm::GetElementPtrInst::getResultElementType
Type * getResultElementType() const
Definition: Instructions.h:1008
llvm::ICmpInst::isEquality
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Definition: Instructions.h:1274
foldSetClearBits
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.
Definition: InstCombineSelect.cpp:692
llvm::GetElementPtrInst::CreateInBounds
static GetElementPtrInst * CreateInBounds(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Create an "inbounds" getelementptr.
Definition: Instructions.h:981
llvm::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Definition: ValueTracking.cpp:196
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PatternMatch::m_Sub
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:991
llvm::SPF_ABS
@ SPF_ABS
Floating point maxnum.
Definition: ValueTracking.h:695
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::CmpInst::FCMP_OGE
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:724
llvm::ConstantExpr::getCast
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
Definition: Constants.cpp:1946
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:743
llvm::Instruction::getFastMathFlags
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
Definition: Instruction.cpp:319
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1736
llvm::PatternMatch::m_ConstantExpr
constantexpr_match m_ConstantExpr()
Match a constant expression or a constant that contains a constant expression.
Definition: PatternMatch.h:165
llvm::PatternMatch::m_WithOverflowInst
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
Definition: PatternMatch.h:722
llvm::PatternMatch::m_SMin
MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1859
llvm::SelectInst::swapValues
void swapValues()
Swap the true and false values of the select instruction.
Definition: Instructions.h:1796
llvm::PatternMatch::m_Constant
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:144
llvm::simplifyAndInst
Value * simplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an And, fold the result or return null.
Definition: InstructionSimplify.cpp:2197
llvm::InstCombinerImpl::foldSelectExtConst
Instruction * foldSelectExtConst(SelectInst &Sel)
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::ZExtInst
This class represents zero extension of integer types.
Definition: Instructions.h:4849
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:748
llvm::CmpInst::isIntPredicate
bool isIntPredicate() const
Definition: InstrTypes.h:827
llvm::APIntOps::smin
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2147
llvm::GetElementPtrInst::Create
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:954
llvm::PatternMatch::m_SExt
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:1623
foldSelectICmpAndOr
static Value * foldSelectICmpAndOr(const ICmpInst *IC, Value *TrueVal, Value *FalseVal, InstCombiner::BuilderTy &Builder)
We want to turn: (select (icmp eq (and X, C1), 0), Y, (or Y, C2)) into: (or (shl (and X,...
Definition: InstCombineSelect.cpp:600
llvm::PatternMatch::m_SpecificInt
specific_intval< false > m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:854
llvm::PatternMatch::m_CombineAnd
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:224
llvm::ArrayRef< int >
llvm::BinaryOperator
Definition: InstrTypes.h:188
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
llvm::PatternMatch::m_SpecificInt_ICMP
cst_pred_ty< icmp_pred_with_threshold > m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold)
Match an integer or vector with every element comparing 'pred' (eg/ne/...) to Threshold.
Definition: PatternMatch.h:598
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::PatternMatch::m_Undef
auto m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:136
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:744
llvm::logicalview::LVAttributeKind::Zero
@ Zero
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Constant::getAggregateElement
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:410
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::PatternMatch::m_Shuffle
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
Definition: PatternMatch.h:1551
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
ConstantRange.h
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::WithOverflowInst
Represents an op.with.overflow intrinsic.
Definition: IntrinsicInst.h:761
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4888
llvm::PatternMatch::m_SMax
MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1853
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
foldSelectZeroOrMul
static Instruction * foldSelectZeroOrMul(SelectInst &SI, InstCombinerImpl &IC)
Definition: InstCombineSelect.cpp:732
llvm::CallBase::setArgOperand
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1346
llvm::PatternMatch::m_OrdFMax
MaxMin_match< FCmpInst, LHS, RHS, ofmax_pred_ty > m_OrdFMax(const LHS &L, const RHS &R)
Match an 'ordered' floating point maximum function.
Definition: PatternMatch.h:1897
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:834
NeedAnd
static cl::opt< bool > NeedAnd("extract-needand", cl::init(true), cl::Hidden, cl::desc("Require & in extract patterns"))
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
llvm::APIntOps::umax
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
Definition: APInt.h:2162
llvm::Instruction::setFastMathFlags
void setFastMathFlags(FastMathFlags FMF)
Convenience function for setting multiple fast-math flags on this instruction, which must be an opera...
Definition: Instruction.cpp:269
llvm::CmpInst::FCMP_UGT
@ FCMP_UGT
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:731
Constant.h
llvm::minnum
LLVM_READONLY APFloat minnum(const APFloat &A, const APFloat &B)
Implements IEEE minNum semantics.
Definition: APFloat.h:1311
llvm::InstCombinerImpl::foldSelectValueEquivalence
Instruction * foldSelectValueEquivalence(SelectInst &SI, ICmpInst &ICI)
llvm::simplifyWithOpReplaced
Value * simplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp, const SimplifyQuery &Q, bool AllowRefinement)
See if V simplifies when its operand Op is replaced with RepOp.
Definition: InstructionSimplify.cpp:4203
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:827
Insn
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
Definition: AArch64MIPeepholeOpt.cpp:130
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
llvm::KnownBits
Definition: KnownBits.h:23
llvm::decomposeBitTestICmp
bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred, Value *&X, APInt &Mask, bool LookThroughTrunc=true)
Decompose an icmp into the form ((X & Mask) pred 0) if possible.
Definition: CmpInstAnalysis.cpp:76
llvm::ConstantExpr::getNeg
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2617
llvm::SelectPatternResult::Ordered
bool Ordered
Only applicable if Flavor is SPF_FMINNUM or SPF_FMAXNUM.
Definition: ValueTracking.h:714
llvm::CastInst::CreateBitOrPointerCast
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
Definition: Instructions.cpp:3495
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::X86::FirstMacroFusionInstKind::Cmp
@ Cmp
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:216
llvm::CmpInst::isUnsigned
bool isUnsigned() const
Definition: InstrTypes.h:953
llvm::ConstantFP::get
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:926
Casting.h
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::size
unsigned size() const
Definition: DenseMap.h:99
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:225
llvm::ARCCC::Z
@ Z
Definition: ARCInfo.h:41
OverflowInstAnalysis.h
llvm::PatternMatch::m_c_LogicalAnd
LogicalOp_match< LHS, RHS, Instruction::And, true > m_c_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R with LHS and RHS in either order.
Definition: PatternMatch.h:2554
llvm::PatternMatch::m_c_Mul
BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)
Matches a Mul with LHS and RHS in either order.
Definition: PatternMatch.h:2244
llvm::InstCombinerImpl::visitSelectInst
Instruction * visitSelectInst(SelectInst &SI)
llvm::PatternMatch::m_ZeroInt
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
Definition: PatternMatch.h:524
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:747
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::APInt::getSignedMinValue
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
llvm::PatternMatch::m_APFloatAllowUndef
apfloat_match m_APFloatAllowUndef(const APFloat *&Res)
Match APFloat while allowing undefs in splat vector constants.
Definition: PatternMatch.h:301
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:439
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
llvm::InstCombinerImpl::foldSelectOpOp
Instruction * foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI)
We have (select c, TI, FI), and we know that TI and FI have the same opcode.
Definition: InstCombineSelect.cpp:263
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::PatternMatch::m_LogicalShift
BinOpPred_match< LHS, RHS, is_logical_shift_op > m_LogicalShift(const LHS &L, const RHS &R)
Matches logical shift operations.
Definition: PatternMatch.h:1311
llvm::PatternMatch::m_AnyZeroFP
cstfp_pred_ty< is_any_zero_fp > m_AnyZeroFP()
Match a floating-point negative zero or positive zero.
Definition: PatternMatch.h:664
llvm::Constant::mergeUndefsWith
static Constant * mergeUndefsWith(Constant *C, Constant *Other)
Merges undefs of a Constant with another Constant, along with the undefs already present.
Definition: Constants.cpp:771
llvm::InstCombinerImpl::replaceOperand
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
Definition: InstCombineInternal.h:429
llvm::ShuffleVectorInst
This instruction constructs a fixed permutation of two input vectors.
Definition: Instructions.h:2007
llvm::CannotBeNegativeZero
bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI, unsigned Depth=0)
Return true if we can prove that the specified FP value is never equal to -0.0.
Definition: ValueTracking.cpp:3511
Instructions.h
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
llvm::pdb::DbgHeaderType::Max
@ Max
llvm::PatternMatch::m_AnyIntegralConstant
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
Definition: PatternMatch.h:444
SmallVector.h
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:772
User.h
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1394
llvm::Value::DoPHITranslation
const Value * DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) const
Translate PHI node to its predecessor from the given basic block.
Definition: Value.cpp:986
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:742
llvm::CmpInst::FCMP_UNE
@ FCMP_UNE
1 1 1 0 True if unordered or not equal
Definition: InstrTypes.h:735
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1341
llvm::FreezeInst
This class represents a freeze function that returns random concrete value if an operand is either a ...
Definition: Instructions.h:5437
llvm::SPF_UMIN
@ SPF_UMIN
Signed minimum.
Definition: ValueTracking.h:690
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
InstructionSimplify.h
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:809
llvm::getMinMaxPred
CmpInst::Predicate getMinMaxPred(SelectPatternFlavor SPF, bool Ordered=false)
Return the canonical comparison predicate for the specified minimum/maximum flavor.
Definition: ValueTracking.cpp:6454
llvm::InstCombinerImpl::foldVectorSelect
Instruction * foldVectorSelect(SelectInst &Sel)
llvm::PatternMatch::m_NSWNeg
OverflowingBinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWNeg(const ValTy &V)
Matches a 'Neg' as 'sub nsw 0, V'.
Definition: PatternMatch.h:2282
llvm::Instruction::swapProfMetadata
void swapProfMetadata()
If the instruction has "branch_weights" MD_prof metadata and the MDNode has three operands (including...
Definition: Instruction.cpp:854
llvm::PHINode
Definition: Instructions.h:2698
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:119
llvm::Instruction::copyIRFlags
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
Definition: Instruction.cpp:328
IV
static const uint32_t IV[8]
Definition: blake3_impl.h:85
llvm::CmpInst::FCMP_OLE
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:726
llvm::PatternMatch::m_FCmp
CmpClass_match< LHS, RHS, FCmpInst, FCmpInst::Predicate > m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1400
llvm::ConstantRange::makeExactICmpRegion
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
Definition: ConstantRange.cpp:156
llvm::InstCombiner::isSignBitCheck
static bool isSignBitCheck(ICmpInst::Predicate Pred, const APInt &RHS, bool &TrueIfSigned)
Given an exploded icmp instruction, return true if the comparison only checks the sign bit.
Definition: InstCombiner.h:165
llvm::IRBuilderBase::CreateVectorSplat
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Definition: IRBuilder.cpp:1246
DerivedTypes.h
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::CmpInst::isUnordered
static bool isUnordered(Predicate predicate)
Determine if the predicate is an unordered operation.
Definition: Instructions.cpp:4413
llvm::PatternMatch::m_Neg
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
Definition: PatternMatch.h:2273
llvm::isGuaranteedNotToBePoison
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Definition: ValueTracking.cpp:5446
llvm::omp::RTLDependInfoFields::Flags
@ Flags
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
CreateAdd
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:241
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:381
llvm::PatternMatch::m_BasicBlock
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
Definition: PatternMatch.h:168
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::PatternMatch::m_Trunc
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:1611
foldSelectICmpAndAnd
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...
Definition: InstCombineSelect.cpp:504
llvm::BinaryOperator::Create
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
Definition: Instructions.cpp:2936
llvm::tgtok::TrueVal
@ TrueVal
Definition: TGLexer.h:62
Value.h
llvm::abs
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1297
llvm::PatternMatch::m_c_LogicalOr
LogicalOp_match< LHS, RHS, Instruction::Or, true > m_c_LogicalOr(const LHS &L, const RHS &R)
Matches L || R with LHS and RHS in either order.
Definition: PatternMatch.h:2572
llvm::PatternMatch::m_Cmp
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:89
llvm::GetElementPtrInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:1051
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4730
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::AtomicCmpXchgInst
An instruction that atomically checks whether a specified value is in a memory location,...
Definition: Instructions.h:509
llvm::Instruction::dropPoisonGeneratingFlags
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
Definition: Instruction.cpp:177
llvm::APIntOps::smax
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2152
llvm::PatternMatch::m_LogicalAnd
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
Definition: PatternMatch.h:2543
llvm::InstCombinerImpl::foldSPFofSPF
Instruction * foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1, Value *A, Value *B, Instruction &Outer, SelectPatternFlavor SPF2, Value *C)
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38