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