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