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