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