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