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