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