LLVM  15.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  if (!HasShift)
521  X = B;
522 
523  Value *Y;
524  if (!match(Cmp->getOperand(0), m_c_And(m_Specific(X), m_Value(Y))))
525  return nullptr;
526 
527  // ((X & Y) == 0) ? ((X >> Z) & 1) : 1 --> (X & (Y | (1 << Z))) != 0
528  // ((X & Y) == 0) ? (X & 1) : 1 --> (X & (Y | 1)) != 0
529  Constant *One = ConstantInt::get(SelType, 1);
530  Value *MaskB = HasShift ? Builder.CreateShl(One, Z) : One;
531  Value *FullMask = Builder.CreateOr(Y, MaskB);
532  Value *MaskedX = Builder.CreateAnd(X, FullMask);
533  Value *ICmpNeZero = Builder.CreateIsNotNull(MaskedX);
534  return new ZExtInst(ICmpNeZero, SelType);
535 }
536 
537 /// We want to turn:
538 /// (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1
539 /// (select (icmp slt x, C), ashr (X, Y), lshr (X, Y)); iff C s>= 0
540 /// into:
541 /// ashr (X, Y)
543  Value *FalseVal,
545  ICmpInst::Predicate Pred = IC->getPredicate();
546  Value *CmpLHS = IC->getOperand(0);
547  Value *CmpRHS = IC->getOperand(1);
548  if (!CmpRHS->getType()->isIntOrIntVectorTy())
549  return nullptr;
550 
551  Value *X, *Y;
552  unsigned Bitwidth = CmpRHS->getType()->getScalarSizeInBits();
553  if ((Pred != ICmpInst::ICMP_SGT ||
554  !match(CmpRHS,
555  m_SpecificInt_ICMP(ICmpInst::ICMP_SGE, APInt(Bitwidth, -1)))) &&
556  (Pred != ICmpInst::ICMP_SLT ||
557  !match(CmpRHS,
559  return nullptr;
560 
561  // Canonicalize so that ashr is in FalseVal.
562  if (Pred == ICmpInst::ICMP_SLT)
564 
565  if (match(TrueVal, m_LShr(m_Value(X), m_Value(Y))) &&
567  match(CmpLHS, m_Specific(X))) {
568  const auto *Ashr = cast<Instruction>(FalseVal);
569  // if lshr is not exact and ashr is, this new ashr must not be exact.
570  bool IsExact = Ashr->isExact() && cast<Instruction>(TrueVal)->isExact();
571  return Builder.CreateAShr(X, Y, IC->getName(), IsExact);
572  }
573 
574  return nullptr;
575 }
576 
577 /// We want to turn:
578 /// (select (icmp eq (and X, C1), 0), Y, (or Y, C2))
579 /// into:
580 /// (or (shl (and X, C1), C3), Y)
581 /// iff:
582 /// C1 and C2 are both powers of 2
583 /// where:
584 /// C3 = Log(C2) - Log(C1)
585 ///
586 /// This transform handles cases where:
587 /// 1. The icmp predicate is inverted
588 /// 2. The select operands are reversed
589 /// 3. The magnitude of C2 and C1 are flipped
591  Value *FalseVal,
593  // Only handle integer compares. Also, if this is a vector select, we need a
594  // vector compare.
595  if (!TrueVal->getType()->isIntOrIntVectorTy() ||
596  TrueVal->getType()->isVectorTy() != IC->getType()->isVectorTy())
597  return nullptr;
598 
599  Value *CmpLHS = IC->getOperand(0);
600  Value *CmpRHS = IC->getOperand(1);
601 
602  Value *V;
603  unsigned C1Log;
604  bool IsEqualZero;
605  bool NeedAnd = false;
606  if (IC->isEquality()) {
607  if (!match(CmpRHS, m_Zero()))
608  return nullptr;
609 
610  const APInt *C1;
611  if (!match(CmpLHS, m_And(m_Value(), m_Power2(C1))))
612  return nullptr;
613 
614  V = CmpLHS;
615  C1Log = C1->logBase2();
616  IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_EQ;
617  } else if (IC->getPredicate() == ICmpInst::ICMP_SLT ||
618  IC->getPredicate() == ICmpInst::ICMP_SGT) {
619  // We also need to recognize (icmp slt (trunc (X)), 0) and
620  // (icmp sgt (trunc (X)), -1).
621  IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_SGT;
622  if ((IsEqualZero && !match(CmpRHS, m_AllOnes())) ||
623  (!IsEqualZero && !match(CmpRHS, m_Zero())))
624  return nullptr;
625 
626  if (!match(CmpLHS, m_OneUse(m_Trunc(m_Value(V)))))
627  return nullptr;
628 
629  C1Log = CmpLHS->getType()->getScalarSizeInBits() - 1;
630  NeedAnd = true;
631  } else {
632  return nullptr;
633  }
634 
635  const APInt *C2;
636  bool OrOnTrueVal = false;
637  bool OrOnFalseVal = match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2)));
638  if (!OrOnFalseVal)
639  OrOnTrueVal = match(TrueVal, m_Or(m_Specific(FalseVal), m_Power2(C2)));
640 
641  if (!OrOnFalseVal && !OrOnTrueVal)
642  return nullptr;
643 
644  Value *Y = OrOnFalseVal ? TrueVal : FalseVal;
645 
646  unsigned C2Log = C2->logBase2();
647 
648  bool NeedXor = (!IsEqualZero && OrOnFalseVal) || (IsEqualZero && OrOnTrueVal);
649  bool NeedShift = C1Log != C2Log;
650  bool NeedZExtTrunc = Y->getType()->getScalarSizeInBits() !=
652 
653  // Make sure we don't create more instructions than we save.
654  Value *Or = OrOnFalseVal ? FalseVal : TrueVal;
655  if ((NeedShift + NeedXor + NeedZExtTrunc) >
656  (IC->hasOneUse() + Or->hasOneUse()))
657  return nullptr;
658 
659  if (NeedAnd) {
660  // Insert the AND instruction on the input to the truncate.
662  V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), C1));
663  }
664 
665  if (C2Log > C1Log) {
666  V = Builder.CreateZExtOrTrunc(V, Y->getType());
667  V = Builder.CreateShl(V, C2Log - C1Log);
668  } else if (C1Log > C2Log) {
669  V = Builder.CreateLShr(V, C1Log - C2Log);
670  V = Builder.CreateZExtOrTrunc(V, Y->getType());
671  } else
672  V = Builder.CreateZExtOrTrunc(V, Y->getType());
673 
674  if (NeedXor)
675  V = Builder.CreateXor(V, *C2);
676 
677  return Builder.CreateOr(V, Y);
678 }
679 
680 /// Canonicalize a set or clear of a masked set of constant bits to
681 /// select-of-constants form.
684  Value *Cond = Sel.getCondition();
685  Value *T = Sel.getTrueValue();
686  Value *F = Sel.getFalseValue();
687  Type *Ty = Sel.getType();
688  Value *X;
689  const APInt *NotC, *C;
690 
691  // Cond ? (X & ~C) : (X | C) --> (X & ~C) | (Cond ? 0 : C)
692  if (match(T, m_And(m_Value(X), m_APInt(NotC))) &&
693  match(F, m_OneUse(m_Or(m_Specific(X), m_APInt(C)))) && *NotC == ~(*C)) {
695  Constant *OrC = ConstantInt::get(Ty, *C);
696  Value *NewSel = Builder.CreateSelect(Cond, Zero, OrC, "masksel", &Sel);
697  return BinaryOperator::CreateOr(T, NewSel);
698  }
699 
700  // Cond ? (X | C) : (X & ~C) --> (X & ~C) | (Cond ? C : 0)
701  if (match(F, m_And(m_Value(X), m_APInt(NotC))) &&
702  match(T, m_OneUse(m_Or(m_Specific(X), m_APInt(C)))) && *NotC == ~(*C)) {
704  Constant *OrC = ConstantInt::get(Ty, *C);
705  Value *NewSel = Builder.CreateSelect(Cond, OrC, Zero, "masksel", &Sel);
706  return BinaryOperator::CreateOr(F, NewSel);
707  }
708 
709  return nullptr;
710 }
711 
712 // select (x == 0), 0, x * y --> freeze(y) * x
713 // select (y == 0), 0, x * y --> freeze(x) * y
714 // select (x == 0), undef, x * y --> freeze(y) * x
715 // select (x == undef), 0, x * y --> freeze(y) * x
716 // Usage of mul instead of 0 will make the result more poisonous,
717 // so the operand that was not checked in the condition should be frozen.
718 // The latter folding is applied only when a constant compared with x is
719 // is a vector consisting of 0 and undefs. If a constant compared with x
720 // is a scalar undefined value or undefined vector then an expression
721 // should be already folded into a constant.
723  auto *CondVal = SI.getCondition();
724  auto *TrueVal = SI.getTrueValue();
725  auto *FalseVal = SI.getFalseValue();
726  Value *X, *Y;
728 
729  // Assuming that constant compared with zero is not undef (but it may be
730  // a vector with some undef elements). Otherwise (when a constant is undef)
731  // the select expression should be already simplified.
732  if (!match(CondVal, m_ICmp(Predicate, m_Value(X), m_Zero())) ||
734  return nullptr;
735 
738 
739  // Check that TrueVal is a constant instead of matching it with m_Zero()
740  // to handle the case when it is a scalar undef value or a vector containing
741  // non-zero elements that are masked by undef elements in the compare
742  // constant.
743  auto *TrueValC = dyn_cast<Constant>(TrueVal);
744  if (TrueValC == nullptr ||
746  !isa<Instruction>(FalseVal))
747  return nullptr;
748 
749  auto *ZeroC = cast<Constant>(cast<Instruction>(CondVal)->getOperand(1));
750  auto *MergedC = Constant::mergeUndefsWith(TrueValC, ZeroC);
751  // If X is compared with 0 then TrueVal could be either zero or undef.
752  // m_Zero match vectors containing some undef elements, but for scalars
753  // m_Undef should be used explicitly.
754  if (!match(MergedC, m_Zero()) && !match(MergedC, m_Undef()))
755  return nullptr;
756 
757  auto *FalseValI = cast<Instruction>(FalseVal);
758  auto *FrY = IC.InsertNewInstBefore(new FreezeInst(Y, Y->getName() + ".fr"),
759  *FalseValI);
760  IC.replaceOperand(*FalseValI, FalseValI->getOperand(0) == Y ? 0 : 1, FrY);
761  return IC.replaceInstUsesWith(SI, FalseValI);
762 }
763 
764 /// Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b).
765 /// There are 8 commuted/swapped variants of this pattern.
766 /// TODO: Also support a - UMIN(a,b) patterns.
768  const Value *TrueVal,
769  const Value *FalseVal,
771  ICmpInst::Predicate Pred = ICI->getPredicate();
772  if (!ICmpInst::isUnsigned(Pred))
773  return nullptr;
774 
775  // (b > a) ? 0 : a - b -> (b <= a) ? a - b : 0
776  if (match(TrueVal, m_Zero())) {
777  Pred = ICmpInst::getInversePredicate(Pred);
779  }
780  if (!match(FalseVal, m_Zero()))
781  return nullptr;
782 
783  Value *A = ICI->getOperand(0);
784  Value *B = ICI->getOperand(1);
785  if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_ULT) {
786  // (b < a) ? a - b : 0 -> (a > b) ? a - b : 0
787  std::swap(A, B);
788  Pred = ICmpInst::getSwappedPredicate(Pred);
789  }
790 
791  assert((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_UGT) &&
792  "Unexpected isUnsigned predicate!");
793 
794  // Ensure the sub is of the form:
795  // (a > b) ? a - b : 0 -> usub.sat(a, b)
796  // (a > b) ? b - a : 0 -> -usub.sat(a, b)
797  // Checking for both a-b and a+(-b) as a constant.
798  bool IsNegative = false;
799  const APInt *C;
800  if (match(TrueVal, m_Sub(m_Specific(B), m_Specific(A))) ||
801  (match(A, m_APInt(C)) &&
803  IsNegative = true;
804  else if (!match(TrueVal, m_Sub(m_Specific(A), m_Specific(B))) &&
805  !(match(B, m_APInt(C)) &&
807  return nullptr;
808 
809  // If we are adding a negate and the sub and icmp are used anywhere else, we
810  // would end up with more instructions.
811  if (IsNegative && !TrueVal->hasOneUse() && !ICI->hasOneUse())
812  return nullptr;
813 
814  // (a > b) ? a - b : 0 -> usub.sat(a, b)
815  // (a > b) ? b - a : 0 -> -usub.sat(a, b)
816  Value *Result = Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, A, B);
817  if (IsNegative)
818  Result = Builder.CreateNeg(Result);
819  return Result;
820 }
821 
822 static Value *canonicalizeSaturatedAdd(ICmpInst *Cmp, Value *TVal, Value *FVal,
824  if (!Cmp->hasOneUse())
825  return nullptr;
826 
827  // Match unsigned saturated add with constant.
828  Value *Cmp0 = Cmp->getOperand(0);
829  Value *Cmp1 = Cmp->getOperand(1);
830  ICmpInst::Predicate Pred = Cmp->getPredicate();
831  Value *X;
832  const APInt *C, *CmpC;
833  if (Pred == ICmpInst::ICMP_ULT &&
834  match(TVal, m_Add(m_Value(X), m_APInt(C))) && X == Cmp0 &&
835  match(FVal, m_AllOnes()) && match(Cmp1, m_APInt(CmpC)) && *CmpC == ~*C) {
836  // (X u< ~C) ? (X + C) : -1 --> uadd.sat(X, C)
837  return Builder.CreateBinaryIntrinsic(
838  Intrinsic::uadd_sat, X, ConstantInt::get(X->getType(), *C));
839  }
840 
841  // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
842  // There are 8 commuted variants.
843  // Canonicalize -1 (saturated result) to true value of the select.
844  if (match(FVal, m_AllOnes())) {
845  std::swap(TVal, FVal);
846  Pred = CmpInst::getInversePredicate(Pred);
847  }
848  if (!match(TVal, m_AllOnes()))
849  return nullptr;
850 
851  // Canonicalize predicate to less-than or less-or-equal-than.
852  if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) {
853  std::swap(Cmp0, Cmp1);
854  Pred = CmpInst::getSwappedPredicate(Pred);
855  }
856  if (Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_ULE)
857  return nullptr;
858 
859  // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
860  // Strictness of the comparison is irrelevant.
861  Value *Y;
862  if (match(Cmp0, m_Not(m_Value(X))) &&
863  match(FVal, m_c_Add(m_Specific(X), m_Value(Y))) && Y == Cmp1) {
864  // (~X u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
865  // (~X u< Y) ? -1 : (Y + X) --> uadd.sat(X, Y)
866  return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, X, Y);
867  }
868  // The 'not' op may be included in the sum but not the compare.
869  // Strictness of the comparison is irrelevant.
870  X = Cmp0;
871  Y = Cmp1;
872  if (match(FVal, m_c_Add(m_Not(m_Specific(X)), m_Specific(Y)))) {
873  // (X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y)
874  // (X u< Y) ? -1 : (Y + ~X) --> uadd.sat(Y, ~X)
875  BinaryOperator *BO = cast<BinaryOperator>(FVal);
876  return Builder.CreateBinaryIntrinsic(
877  Intrinsic::uadd_sat, BO->getOperand(0), BO->getOperand(1));
878  }
879  // The overflow may be detected via the add wrapping round.
880  // This is only valid for strict comparison!
881  if (Pred == ICmpInst::ICMP_ULT &&
882  match(Cmp0, m_c_Add(m_Specific(Cmp1), m_Value(Y))) &&
883  match(FVal, m_c_Add(m_Specific(Cmp1), m_Specific(Y)))) {
884  // ((X + Y) u< X) ? -1 : (X + Y) --> uadd.sat(X, Y)
885  // ((X + Y) u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
886  return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, Cmp1, Y);
887  }
888 
889  return nullptr;
890 }
891 
892 /// Fold the following code sequence:
893 /// \code
894 /// int a = ctlz(x & -x);
895 // x ? 31 - a : a;
896 /// \code
897 ///
898 /// into:
899 /// cttz(x)
900 static Instruction *foldSelectCtlzToCttz(ICmpInst *ICI, Value *TrueVal,
901  Value *FalseVal,
903  unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits();
904  if (!ICI->isEquality() || !match(ICI->getOperand(1), m_Zero()))
905  return nullptr;
906 
907  if (ICI->getPredicate() == ICmpInst::ICMP_NE)
909 
910  if (!match(FalseVal,
912  return nullptr;
913 
914  if (!match(TrueVal, m_Intrinsic<Intrinsic::ctlz>()))
915  return nullptr;
916 
917  Value *X = ICI->getOperand(0);
918  auto *II = cast<IntrinsicInst>(TrueVal);
919  if (!match(II->getOperand(0), m_c_And(m_Specific(X), m_Neg(m_Specific(X)))))
920  return nullptr;
921 
922  Function *F = Intrinsic::getDeclaration(II->getModule(), Intrinsic::cttz,
923  II->getType());
924  return CallInst::Create(F, {X, II->getArgOperand(1)});
925 }
926 
927 /// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single
928 /// call to cttz/ctlz with flag 'is_zero_poison' cleared.
929 ///
930 /// For example, we can fold the following code sequence:
931 /// \code
932 /// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
933 /// %1 = icmp ne i32 %x, 0
934 /// %2 = select i1 %1, i32 %0, i32 32
935 /// \code
936 ///
937 /// into:
938 /// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
939 static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal,
941  ICmpInst::Predicate Pred = ICI->getPredicate();
942  Value *CmpLHS = ICI->getOperand(0);
943  Value *CmpRHS = ICI->getOperand(1);
944 
945  // Check if the condition value compares a value for equality against zero.
946  if (!ICI->isEquality() || !match(CmpRHS, m_Zero()))
947  return nullptr;
948 
949  Value *SelectArg = FalseVal;
950  Value *ValueOnZero = TrueVal;
951  if (Pred == ICmpInst::ICMP_NE)
952  std::swap(SelectArg, ValueOnZero);
953 
954  // Skip zero extend/truncate.
955  Value *Count = nullptr;
956  if (!match(SelectArg, m_ZExt(m_Value(Count))) &&
957  !match(SelectArg, m_Trunc(m_Value(Count))))
958  Count = SelectArg;
959 
960  // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the
961  // input to the cttz/ctlz is used as LHS for the compare instruction.
962  if (!match(Count, m_Intrinsic<Intrinsic::cttz>(m_Specific(CmpLHS))) &&
963  !match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Specific(CmpLHS))))
964  return nullptr;
965 
966  IntrinsicInst *II = cast<IntrinsicInst>(Count);
967 
968  // Check if the value propagated on zero is a constant number equal to the
969  // sizeof in bits of 'Count'.
970  unsigned SizeOfInBits = Count->getType()->getScalarSizeInBits();
971  if (match(ValueOnZero, m_SpecificInt(SizeOfInBits))) {
972  // Explicitly clear the 'is_zero_poison' flag. It's always valid to go from
973  // true to false on this flag, so we can replace it for all users.
975  return SelectArg;
976  }
977 
978  // The ValueOnZero is not the bitwidth. But if the cttz/ctlz (and optional
979  // zext/trunc) have one use (ending at the select), the cttz/ctlz result will
980  // not be used if the input is zero. Relax to 'zero is poison' for that case.
981  if (II->hasOneUse() && SelectArg->hasOneUse() &&
982  !match(II->getArgOperand(1), m_One()))
984 
985  return nullptr;
986 }
987 
988 /// Return true if we find and adjust an icmp+select pattern where the compare
989 /// is with a constant that can be incremented or decremented to match the
990 /// minimum or maximum idiom.
991 static bool adjustMinMax(SelectInst &Sel, ICmpInst &Cmp) {
992  ICmpInst::Predicate Pred = Cmp.getPredicate();
993  Value *CmpLHS = Cmp.getOperand(0);
994  Value *CmpRHS = Cmp.getOperand(1);
995  Value *TrueVal = Sel.getTrueValue();
996  Value *FalseVal = Sel.getFalseValue();
997 
998  // We may move or edit the compare, so make sure the select is the only user.
999  const APInt *CmpC;
1000  if (!Cmp.hasOneUse() || !match(CmpRHS, m_APInt(CmpC)))
1001  return false;
1002 
1003  // These transforms only work for selects of integers or vector selects of
1004  // integer vectors.
1005  Type *SelTy = Sel.getType();
1006  auto *SelEltTy = dyn_cast<IntegerType>(SelTy->getScalarType());
1007  if (!SelEltTy || SelTy->isVectorTy() != Cmp.getType()->isVectorTy())
1008  return false;
1009 
1010  Constant *AdjustedRHS;
1011  if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_SGT)
1012  AdjustedRHS = ConstantInt::get(CmpRHS->getType(), *CmpC + 1);
1013  else if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_SLT)
1014  AdjustedRHS = ConstantInt::get(CmpRHS->getType(), *CmpC - 1);
1015  else
1016  return false;
1017 
1018  // X > C ? X : C+1 --> X < C+1 ? C+1 : X
1019  // X < C ? X : C-1 --> X > C-1 ? C-1 : X
1020  if ((CmpLHS == TrueVal && AdjustedRHS == FalseVal) ||
1021  (CmpLHS == FalseVal && AdjustedRHS == TrueVal)) {
1022  ; // Nothing to do here. Values match without any sign/zero extension.
1023  }
1024  // Types do not match. Instead of calculating this with mixed types, promote
1025  // all to the larger type. This enables scalar evolution to analyze this
1026  // expression.
1027  else if (CmpRHS->getType()->getScalarSizeInBits() < SelEltTy->getBitWidth()) {
1028  Constant *SextRHS = ConstantExpr::getSExt(AdjustedRHS, SelTy);
1029 
1030  // X = sext x; x >s c ? X : C+1 --> X = sext x; X <s C+1 ? C+1 : X
1031  // X = sext x; x <s c ? X : C-1 --> X = sext x; X >s C-1 ? C-1 : X
1032  // X = sext x; x >u c ? X : C+1 --> X = sext x; X <u C+1 ? C+1 : X
1033  // X = sext x; x <u c ? X : C-1 --> X = sext x; X >u C-1 ? C-1 : X
1034  if (match(TrueVal, m_SExt(m_Specific(CmpLHS))) && SextRHS == FalseVal) {
1035  CmpLHS = TrueVal;
1036  AdjustedRHS = SextRHS;
1037  } else if (match(FalseVal, m_SExt(m_Specific(CmpLHS))) &&
1038  SextRHS == TrueVal) {
1039  CmpLHS = FalseVal;
1040  AdjustedRHS = SextRHS;
1041  } else if (Cmp.isUnsigned()) {
1042  Constant *ZextRHS = ConstantExpr::getZExt(AdjustedRHS, SelTy);
1043  // X = zext x; x >u c ? X : C+1 --> X = zext x; X <u C+1 ? C+1 : X
1044  // X = zext x; x <u c ? X : C-1 --> X = zext x; X >u C-1 ? C-1 : X
1045  // zext + signed compare cannot be changed:
1046  // 0xff <s 0x00, but 0x00ff >s 0x0000
1047  if (match(TrueVal, m_ZExt(m_Specific(CmpLHS))) && ZextRHS == FalseVal) {
1048  CmpLHS = TrueVal;
1049  AdjustedRHS = ZextRHS;
1050  } else if (match(FalseVal, m_ZExt(m_Specific(CmpLHS))) &&
1051  ZextRHS == TrueVal) {
1052  CmpLHS = FalseVal;
1053  AdjustedRHS = ZextRHS;
1054  } else {
1055  return false;
1056  }
1057  } else {
1058  return false;
1059  }
1060  } else {
1061  return false;
1062  }
1063 
1064  Pred = ICmpInst::getSwappedPredicate(Pred);
1065  CmpRHS = AdjustedRHS;
1067  Cmp.setPredicate(Pred);
1068  Cmp.setOperand(0, CmpLHS);
1069  Cmp.setOperand(1, CmpRHS);
1070  Sel.setOperand(1, TrueVal);
1071  Sel.setOperand(2, FalseVal);
1072  Sel.swapProfMetadata();
1073 
1074  // Move the compare instruction right before the select instruction. Otherwise
1075  // the sext/zext value may be defined after the compare instruction uses it.
1076  Cmp.moveBefore(&Sel);
1077 
1078  return true;
1079 }
1080 
1081 static Instruction *canonicalizeSPF(SelectInst &Sel, ICmpInst &Cmp,
1082  InstCombinerImpl &IC) {
1083  Value *LHS, *RHS;
1084  // TODO: What to do with pointer min/max patterns?
1085  if (!Sel.getType()->isIntOrIntVectorTy())
1086  return nullptr;
1087 
1089  if (SPF == SelectPatternFlavor::SPF_ABS ||
1091  if (!Cmp.hasOneUse() && !RHS->hasOneUse())
1092  return nullptr; // TODO: Relax this restriction.
1093 
1094  // Note that NSW flag can only be propagated for normal, non-negated abs!
1095  bool IntMinIsPoison = SPF == SelectPatternFlavor::SPF_ABS &&
1097  Constant *IntMinIsPoisonC =
1098  ConstantInt::get(Type::getInt1Ty(Sel.getContext()), IntMinIsPoison);
1099  Instruction *Abs =
1100  IC.Builder.CreateBinaryIntrinsic(Intrinsic::abs, LHS, IntMinIsPoisonC);
1101 
1102  if (SPF == SelectPatternFlavor::SPF_NABS)
1103  return BinaryOperator::CreateNeg(Abs); // Always without NSW flag!
1104  return IC.replaceInstUsesWith(Sel, Abs);
1105  }
1106 
1108  Intrinsic::ID IntrinsicID;
1109  switch (SPF) {
1111  IntrinsicID = Intrinsic::umin;
1112  break;
1114  IntrinsicID = Intrinsic::umax;
1115  break;
1117  IntrinsicID = Intrinsic::smin;
1118  break;
1120  IntrinsicID = Intrinsic::smax;
1121  break;
1122  default:
1123  llvm_unreachable("Unexpected SPF");
1124  }
1125  return IC.replaceInstUsesWith(
1126  Sel, IC.Builder.CreateBinaryIntrinsic(IntrinsicID, LHS, RHS));
1127  }
1128 
1129  return nullptr;
1130 }
1131 
1132 /// If we have a select with an equality comparison, then we know the value in
1133 /// one of the arms of the select. See if substituting this value into an arm
1134 /// and simplifying the result yields the same value as the other arm.
1135 ///
1136 /// To make this transform safe, we must drop poison-generating flags
1137 /// (nsw, etc) if we simplified to a binop because the select may be guarding
1138 /// that poison from propagating. If the existing binop already had no
1139 /// poison-generating flags, then this transform can be done by instsimplify.
1140 ///
1141 /// Consider:
1142 /// %cmp = icmp eq i32 %x, 2147483647
1143 /// %add = add nsw i32 %x, 1
1144 /// %sel = select i1 %cmp, i32 -2147483648, i32 %add
1145 ///
1146 /// We can't replace %sel with %add unless we strip away the flags.
1147 /// TODO: Wrapping flags could be preserved in some cases with better analysis.
1149  ICmpInst &Cmp) {
1150  // Value equivalence substitution requires an all-or-nothing replacement.
1151  // It does not make sense for a vector compare where each lane is chosen
1152  // independently.
1153  if (!Cmp.isEquality() || Cmp.getType()->isVectorTy())
1154  return nullptr;
1155 
1156  // Canonicalize the pattern to ICMP_EQ by swapping the select operands.
1157  Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
1158  bool Swapped = false;
1159  if (Cmp.getPredicate() == ICmpInst::ICMP_NE) {
1161  Swapped = true;
1162  }
1163 
1164  // In X == Y ? f(X) : Z, try to evaluate f(Y) and replace the operand.
1165  // Make sure Y cannot be undef though, as we might pick different values for
1166  // undef in the icmp and in f(Y). Additionally, take care to avoid replacing
1167  // X == Y ? X : Z with X == Y ? Y : Z, as that would lead to an infinite
1168  // replacement cycle.
1169  Value *CmpLHS = Cmp.getOperand(0), *CmpRHS = Cmp.getOperand(1);
1170  if (TrueVal != CmpLHS &&
1171  isGuaranteedNotToBeUndefOrPoison(CmpRHS, SQ.AC, &Sel, &DT)) {
1172  if (Value *V = simplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, SQ,
1173  /* AllowRefinement */ true))
1174  return replaceOperand(Sel, Swapped ? 2 : 1, V);
1175 
1176  // Even if TrueVal does not simplify, we can directly replace a use of
1177  // CmpLHS with CmpRHS, as long as the instruction is not used anywhere
1178  // else and is safe to speculatively execute (we may end up executing it
1179  // with different operands, which should not cause side-effects or trigger
1180  // undefined behavior). Only do this if CmpRHS is a constant, as
1181  // profitability is not clear for other cases.
1182  // FIXME: The replacement could be performed recursively.
1183  if (match(CmpRHS, m_ImmConstant()) && !match(CmpLHS, m_ImmConstant()))
1184  if (auto *I = dyn_cast<Instruction>(TrueVal))
1185  if (I->hasOneUse() && isSafeToSpeculativelyExecute(I))
1186  for (Use &U : I->operands())
1187  if (U == CmpLHS) {
1188  replaceUse(U, CmpRHS);
1189  return &Sel;
1190  }
1191  }
1192  if (TrueVal != CmpRHS &&
1193  isGuaranteedNotToBeUndefOrPoison(CmpLHS, SQ.AC, &Sel, &DT))
1194  if (Value *V = simplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, SQ,
1195  /* AllowRefinement */ true))
1196  return replaceOperand(Sel, Swapped ? 2 : 1, V);
1197 
1198  auto *FalseInst = dyn_cast<Instruction>(FalseVal);
1199  if (!FalseInst)
1200  return nullptr;
1201 
1202  // InstSimplify already performed this fold if it was possible subject to
1203  // current poison-generating flags. Try the transform again with
1204  // poison-generating flags temporarily dropped.
1205  bool WasNUW = false, WasNSW = false, WasExact = false, WasInBounds = false;
1206  if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(FalseVal)) {
1207  WasNUW = OBO->hasNoUnsignedWrap();
1208  WasNSW = OBO->hasNoSignedWrap();
1209  FalseInst->setHasNoUnsignedWrap(false);
1210  FalseInst->setHasNoSignedWrap(false);
1211  }
1212  if (auto *PEO = dyn_cast<PossiblyExactOperator>(FalseVal)) {
1213  WasExact = PEO->isExact();
1214  FalseInst->setIsExact(false);
1215  }
1216  if (auto *GEP = dyn_cast<GetElementPtrInst>(FalseVal)) {
1217  WasInBounds = GEP->isInBounds();
1218  GEP->setIsInBounds(false);
1219  }
1220 
1221  // Try each equivalence substitution possibility.
1222  // We have an 'EQ' comparison, so the select's false value will propagate.
1223  // Example:
1224  // (X == 42) ? 43 : (X + 1) --> (X == 42) ? (X + 1) : (X + 1) --> X + 1
1225  if (simplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, SQ,
1226  /* AllowRefinement */ false) == TrueVal ||
1227  simplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, SQ,
1228  /* AllowRefinement */ false) == TrueVal) {
1229  return replaceInstUsesWith(Sel, FalseVal);
1230  }
1231 
1232  // Restore poison-generating flags if the transform did not apply.
1233  if (WasNUW)
1234  FalseInst->setHasNoUnsignedWrap();
1235  if (WasNSW)
1236  FalseInst->setHasNoSignedWrap();
1237  if (WasExact)
1238  FalseInst->setIsExact();
1239  if (WasInBounds)
1240  cast<GetElementPtrInst>(FalseInst)->setIsInBounds();
1241 
1242  return nullptr;
1243 }
1244 
1245 // See if this is a pattern like:
1246 // %old_cmp1 = icmp slt i32 %x, C2
1247 // %old_replacement = select i1 %old_cmp1, i32 %target_low, i32 %target_high
1248 // %old_x_offseted = add i32 %x, C1
1249 // %old_cmp0 = icmp ult i32 %old_x_offseted, C0
1250 // %r = select i1 %old_cmp0, i32 %x, i32 %old_replacement
1251 // This can be rewritten as more canonical pattern:
1252 // %new_cmp1 = icmp slt i32 %x, -C1
1253 // %new_cmp2 = icmp sge i32 %x, C0-C1
1254 // %new_clamped_low = select i1 %new_cmp1, i32 %target_low, i32 %x
1255 // %r = select i1 %new_cmp2, i32 %target_high, i32 %new_clamped_low
1256 // Iff -C1 s<= C2 s<= C0-C1
1257 // Also ULT predicate can also be UGT iff C0 != -1 (+invert result)
1258 // SLT predicate can also be SGT iff C2 != INT_MAX (+invert res.)
1259 static Value *canonicalizeClampLike(SelectInst &Sel0, ICmpInst &Cmp0,
1261  Value *X = Sel0.getTrueValue();
1262  Value *Sel1 = Sel0.getFalseValue();
1263 
1264  // First match the condition of the outermost select.
1265  // Said condition must be one-use.
1266  if (!Cmp0.hasOneUse())
1267  return nullptr;
1268  ICmpInst::Predicate Pred0 = Cmp0.getPredicate();
1269  Value *Cmp00 = Cmp0.getOperand(0);
1270  Constant *C0;
1271  if (!match(Cmp0.getOperand(1),
1273  return nullptr;
1274 
1275  if (!isa<SelectInst>(Sel1)) {
1276  Pred0 = ICmpInst::getInversePredicate(Pred0);
1277  std::swap(X, Sel1);
1278  }
1279 
1280  // Canonicalize Cmp0 into ult or uge.
1281  // FIXME: we shouldn't care about lanes that are 'undef' in the end?
1282  switch (Pred0) {
1283  case ICmpInst::Predicate::ICMP_ULT:
1284  case ICmpInst::Predicate::ICMP_UGE:
1285  // Although icmp ult %x, 0 is an unusual thing to try and should generally
1286  // have been simplified, it does not verify with undef inputs so ensure we
1287  // are not in a strange state.
1288  if (!match(C0, m_SpecificInt_ICMP(
1289  ICmpInst::Predicate::ICMP_NE,
1291  return nullptr;
1292  break; // Great!
1293  case ICmpInst::Predicate::ICMP_ULE:
1294  case ICmpInst::Predicate::ICMP_UGT:
1295  // We want to canonicalize it to 'ult' or 'uge', so we'll need to increment
1296  // C0, which again means it must not have any all-ones elements.
1297  if (!match(C0,
1299  ICmpInst::Predicate::ICMP_NE,
1301  return nullptr; // Can't do, have all-ones element[s].
1303  C0 = InstCombiner::AddOne(C0);
1304  break;
1305  default:
1306  return nullptr; // Unknown predicate.
1307  }
1308 
1309  // Now that we've canonicalized the ICmp, we know the X we expect;
1310  // the select in other hand should be one-use.
1311  if (!Sel1->hasOneUse())
1312  return nullptr;
1313 
1314  // If the types do not match, look through any truncs to the underlying
1315  // instruction.
1316  if (Cmp00->getType() != X->getType() && X->hasOneUse())
1318 
1319  // We now can finish matching the condition of the outermost select:
1320  // it should either be the X itself, or an addition of some constant to X.
1321  Constant *C1;
1322  if (Cmp00 == X)
1323  C1 = ConstantInt::getNullValue(X->getType());
1324  else if (!match(Cmp00,
1325  m_Add(m_Specific(X),
1327  return nullptr;
1328 
1329  Value *Cmp1;
1330  ICmpInst::Predicate Pred1;
1331  Constant *C2;
1332  Value *ReplacementLow, *ReplacementHigh;
1333  if (!match(Sel1, m_Select(m_Value(Cmp1), m_Value(ReplacementLow),
1334  m_Value(ReplacementHigh))) ||
1335  !match(Cmp1,
1336  m_ICmp(Pred1, m_Specific(X),
1338  return nullptr;
1339 
1340  if (!Cmp1->hasOneUse() && (Cmp00 == X || !Cmp00->hasOneUse()))
1341  return nullptr; // Not enough one-use instructions for the fold.
1342  // FIXME: this restriction could be relaxed if Cmp1 can be reused as one of
1343  // two comparisons we'll need to build.
1344 
1345  // Canonicalize Cmp1 into the form we expect.
1346  // FIXME: we shouldn't care about lanes that are 'undef' in the end?
1347  switch (Pred1) {
1348  case ICmpInst::Predicate::ICMP_SLT:
1349  break;
1350  case ICmpInst::Predicate::ICMP_SLE:
1351  // We'd have to increment C2 by one, and for that it must not have signed
1352  // max element, but then it would have been canonicalized to 'slt' before
1353  // we get here. So we can't do anything useful with 'sle'.
1354  return nullptr;
1355  case ICmpInst::Predicate::ICMP_SGT:
1356  // We want to canonicalize it to 'slt', so we'll need to increment C2,
1357  // which again means it must not have any signed max elements.
1358  if (!match(C2,
1359  m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE,
1361  C2->getType()->getScalarSizeInBits()))))
1362  return nullptr; // Can't do, have signed max element[s].
1363  C2 = InstCombiner::AddOne(C2);
1365  case ICmpInst::Predicate::ICMP_SGE:
1366  // Also non-canonical, but here we don't need to change C2,
1367  // so we don't have any restrictions on C2, so we can just handle it.
1368  Pred1 = ICmpInst::Predicate::ICMP_SLT;
1369  std::swap(ReplacementLow, ReplacementHigh);
1370  break;
1371  default:
1372  return nullptr; // Unknown predicate.
1373  }
1374  assert(Pred1 == ICmpInst::Predicate::ICMP_SLT &&
1375  "Unexpected predicate type.");
1376 
1377  // The thresholds of this clamp-like pattern.
1378  auto *ThresholdLowIncl = ConstantExpr::getNeg(C1);
1379  auto *ThresholdHighExcl = ConstantExpr::getSub(C0, C1);
1380 
1381  assert((Pred0 == ICmpInst::Predicate::ICMP_ULT ||
1382  Pred0 == ICmpInst::Predicate::ICMP_UGE) &&
1383  "Unexpected predicate type.");
1384  if (Pred0 == ICmpInst::Predicate::ICMP_UGE)
1385  std::swap(ThresholdLowIncl, ThresholdHighExcl);
1386 
1387  // The fold has a precondition 1: C2 s>= ThresholdLow
1388  auto *Precond1 = ConstantExpr::getICmp(ICmpInst::Predicate::ICMP_SGE, C2,
1389  ThresholdLowIncl);
1390  if (!match(Precond1, m_One()))
1391  return nullptr;
1392  // The fold has a precondition 2: C2 s<= ThresholdHigh
1393  auto *Precond2 = ConstantExpr::getICmp(ICmpInst::Predicate::ICMP_SLE, C2,
1394  ThresholdHighExcl);
1395  if (!match(Precond2, m_One()))
1396  return nullptr;
1397 
1398  // If we are matching from a truncated input, we need to sext the
1399  // ReplacementLow and ReplacementHigh values. Only do the transform if they
1400  // are free to extend due to being constants.
1401  if (X->getType() != Sel0.getType()) {
1402  Constant *LowC, *HighC;
1403  if (!match(ReplacementLow, m_ImmConstant(LowC)) ||
1404  !match(ReplacementHigh, m_ImmConstant(HighC)))
1405  return nullptr;
1406  ReplacementLow = ConstantExpr::getSExt(LowC, X->getType());
1407  ReplacementHigh = ConstantExpr::getSExt(HighC, X->getType());
1408  }
1409 
1410  // All good, finally emit the new pattern.
1411  Value *ShouldReplaceLow = Builder.CreateICmpSLT(X, ThresholdLowIncl);
1412  Value *ShouldReplaceHigh = Builder.CreateICmpSGE(X, ThresholdHighExcl);
1413  Value *MaybeReplacedLow =
1414  Builder.CreateSelect(ShouldReplaceLow, ReplacementLow, X);
1415 
1416  // Create the final select. If we looked through a truncate above, we will
1417  // need to retruncate the result.
1418  Value *MaybeReplacedHigh = Builder.CreateSelect(
1419  ShouldReplaceHigh, ReplacementHigh, MaybeReplacedLow);
1420  return Builder.CreateTrunc(MaybeReplacedHigh, Sel0.getType());
1421 }
1422 
1423 // If we have
1424 // %cmp = icmp [canonical predicate] i32 %x, C0
1425 // %r = select i1 %cmp, i32 %y, i32 C1
1426 // Where C0 != C1 and %x may be different from %y, see if the constant that we
1427 // will have if we flip the strictness of the predicate (i.e. without changing
1428 // the result) is identical to the C1 in select. If it matches we can change
1429 // original comparison to one with swapped predicate, reuse the constant,
1430 // and swap the hands of select.
1431 static Instruction *
1432 tryToReuseConstantFromSelectInComparison(SelectInst &Sel, ICmpInst &Cmp,
1433  InstCombinerImpl &IC) {
1434  ICmpInst::Predicate Pred;
1435  Value *X;
1436  Constant *C0;
1437  if (!match(&Cmp, m_OneUse(m_ICmp(
1438  Pred, m_Value(X),
1440  return nullptr;
1441 
1442  // If comparison predicate is non-relational, we won't be able to do anything.
1443  if (ICmpInst::isEquality(Pred))
1444  return nullptr;
1445 
1446  // If comparison predicate is non-canonical, then we certainly won't be able
1447  // to make it canonical; canonicalizeCmpWithConstant() already tried.
1449  return nullptr;
1450 
1451  // If the [input] type of comparison and select type are different, lets abort
1452  // for now. We could try to compare constants with trunc/[zs]ext though.
1453  if (C0->getType() != Sel.getType())
1454  return nullptr;
1455 
1456  // ULT with 'add' of a constant is canonical. See foldICmpAddConstant().
1457  // FIXME: Are there more magic icmp predicate+constant pairs we must avoid?
1458  // Or should we just abandon this transform entirely?
1459  if (Pred == CmpInst::ICMP_ULT && match(X, m_Add(m_Value(), m_Constant())))
1460  return nullptr;
1461 
1462 
1463  Value *SelVal0, *SelVal1; // We do not care which one is from where.
1464  match(&Sel, m_Select(m_Value(), m_Value(SelVal0), m_Value(SelVal1)));
1465  // At least one of these values we are selecting between must be a constant
1466  // else we'll never succeed.
1467  if (!match(SelVal0, m_AnyIntegralConstant()) &&
1468  !match(SelVal1, m_AnyIntegralConstant()))
1469  return nullptr;
1470 
1471  // Does this constant C match any of the `select` values?
1472  auto MatchesSelectValue = [SelVal0, SelVal1](Constant *C) {
1473  return C->isElementWiseEqual(SelVal0) || C->isElementWiseEqual(SelVal1);
1474  };
1475 
1476  // If C0 *already* matches true/false value of select, we are done.
1477  if (MatchesSelectValue(C0))
1478  return nullptr;
1479 
1480  // Check the constant we'd have with flipped-strictness predicate.
1481  auto FlippedStrictness =
1483  if (!FlippedStrictness)
1484  return nullptr;
1485 
1486  // If said constant doesn't match either, then there is no hope,
1487  if (!MatchesSelectValue(FlippedStrictness->second))
1488  return nullptr;
1489 
1490  // It matched! Lets insert the new comparison just before select.
1491  InstCombiner::BuilderTy::InsertPointGuard Guard(IC.Builder);
1492  IC.Builder.SetInsertPoint(&Sel);
1493 
1494  Pred = ICmpInst::getSwappedPredicate(Pred); // Yes, swapped.
1495  Value *NewCmp = IC.Builder.CreateICmp(Pred, X, FlippedStrictness->second,
1496  Cmp.getName() + ".inv");
1497  IC.replaceOperand(Sel, 0, NewCmp);
1498  Sel.swapValues();
1499  Sel.swapProfMetadata();
1500 
1501  return &Sel;
1502 }
1503 
1504 static Instruction *foldSelectZeroOrOnes(ICmpInst *Cmp, Value *TVal,
1505  Value *FVal,
1507  if (!Cmp->hasOneUse())
1508  return nullptr;
1509 
1510  const APInt *CmpC;
1511  if (!match(Cmp->getOperand(1), m_APIntAllowUndef(CmpC)))
1512  return nullptr;
1513 
1514  // (X u< 2) ? -X : -1 --> sext (X != 0)
1515  Value *X = Cmp->getOperand(0);
1516  if (Cmp->getPredicate() == ICmpInst::ICMP_ULT && *CmpC == 2 &&
1517  match(TVal, m_Neg(m_Specific(X))) && match(FVal, m_AllOnes()))
1518  return new SExtInst(Builder.CreateIsNotNull(X), TVal->getType());
1519 
1520  // (X u> 1) ? -1 : -X --> sext (X != 0)
1521  if (Cmp->getPredicate() == ICmpInst::ICMP_UGT && *CmpC == 1 &&
1522  match(FVal, m_Neg(m_Specific(X))) && match(TVal, m_AllOnes()))
1523  return new SExtInst(Builder.CreateIsNotNull(X), TVal->getType());
1524 
1525  return nullptr;
1526 }
1527 
1528 static Value *foldSelectInstWithICmpConst(SelectInst &SI, ICmpInst *ICI) {
1529  const APInt *CmpC;
1530  Value *V;
1531  CmpInst::Predicate Pred;
1532  if (!match(ICI, m_ICmp(Pred, m_Value(V), m_APInt(CmpC))))
1533  return nullptr;
1534 
1535  BinaryOperator *BO;
1536  const APInt *C;
1537  CmpInst::Predicate CPred;
1538  if (match(&SI, m_Select(m_Specific(ICI), m_APInt(C), m_BinOp(BO))))
1539  CPred = ICI->getPredicate();
1540  else if (match(&SI, m_Select(m_Specific(ICI), m_BinOp(BO), m_APInt(C))))
1541  CPred = ICI->getInversePredicate();
1542  else
1543  return nullptr;
1544 
1545  const APInt *BinOpC;
1546  if (!match(BO, m_BinOp(m_Specific(V), m_APInt(BinOpC))))
1547  return nullptr;
1548 
1550  .binaryOp(BO->getOpcode(), *BinOpC);
1551  if (R == *C) {
1553  return BO;
1554  }
1555  return nullptr;
1556 }
1557 
1558 /// Visit a SelectInst that has an ICmpInst as its first operand.
1560  ICmpInst *ICI) {
1561  if (Instruction *NewSel = foldSelectValueEquivalence(SI, *ICI))
1562  return NewSel;
1563 
1564  if (Instruction *NewSPF = canonicalizeSPF(SI, *ICI, *this))
1565  return NewSPF;
1566 
1567  if (Value *V = foldSelectInstWithICmpConst(SI, ICI))
1568  return replaceInstUsesWith(SI, V);
1569 
1570  if (Value *V = canonicalizeClampLike(SI, *ICI, Builder))
1571  return replaceInstUsesWith(SI, V);
1572 
1573  if (Instruction *NewSel =
1574  tryToReuseConstantFromSelectInComparison(SI, *ICI, *this))
1575  return NewSel;
1576 
1577  bool Changed = adjustMinMax(SI, *ICI);
1578 
1579  if (Value *V = foldSelectICmpAnd(SI, ICI, Builder))
1580  return replaceInstUsesWith(SI, V);
1581 
1582  // NOTE: if we wanted to, this is where to detect integer MIN/MAX
1583  Value *TrueVal = SI.getTrueValue();
1584  Value *FalseVal = SI.getFalseValue();
1585  ICmpInst::Predicate Pred = ICI->getPredicate();
1586  Value *CmpLHS = ICI->getOperand(0);
1587  Value *CmpRHS = ICI->getOperand(1);
1588  if (CmpRHS != CmpLHS && isa<Constant>(CmpRHS)) {
1589  if (CmpLHS == TrueVal && Pred == ICmpInst::ICMP_EQ) {
1590  // Transform (X == C) ? X : Y -> (X == C) ? C : Y
1591  SI.setOperand(1, CmpRHS);
1592  Changed = true;
1593  } else if (CmpLHS == FalseVal && Pred == ICmpInst::ICMP_NE) {
1594  // Transform (X != C) ? Y : X -> (X != C) ? Y : C
1595  SI.setOperand(2, CmpRHS);
1596  Changed = true;
1597  }
1598  }
1599 
1600  // Canonicalize a signbit condition to use zero constant by swapping:
1601  // (CmpLHS > -1) ? TV : FV --> (CmpLHS < 0) ? FV : TV
1602  // To avoid conflicts (infinite loops) with other canonicalizations, this is
1603  // not applied with any constant select arm.
1604  if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes()) &&
1606  ICI->hasOneUse()) {
1607  InstCombiner::BuilderTy::InsertPointGuard Guard(Builder);
1608  Builder.SetInsertPoint(&SI);
1609  Value *IsNeg = Builder.CreateIsNeg(CmpLHS, ICI->getName());
1610  replaceOperand(SI, 0, IsNeg);
1611  SI.swapValues();
1612  SI.swapProfMetadata();
1613  return &SI;
1614  }
1615 
1616  // FIXME: This code is nearly duplicated in InstSimplify. Using/refactoring
1617  // decomposeBitTestICmp() might help.
1618  {
1619  unsigned BitWidth =
1620  DL.getTypeSizeInBits(TrueVal->getType()->getScalarType());
1621  APInt MinSignedValue = APInt::getSignedMinValue(BitWidth);
1622  Value *X;
1623  const APInt *Y, *C;
1624  bool TrueWhenUnset;
1625  bool IsBitTest = false;
1626  if (ICmpInst::isEquality(Pred) &&
1627  match(CmpLHS, m_And(m_Value(X), m_Power2(Y))) &&
1628  match(CmpRHS, m_Zero())) {
1629  IsBitTest = true;
1630  TrueWhenUnset = Pred == ICmpInst::ICMP_EQ;
1631  } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) {
1632  X = CmpLHS;
1633  Y = &MinSignedValue;
1634  IsBitTest = true;
1635  TrueWhenUnset = false;
1636  } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) {
1637  X = CmpLHS;
1638  Y = &MinSignedValue;
1639  IsBitTest = true;
1640  TrueWhenUnset = true;
1641  }
1642  if (IsBitTest) {
1643  Value *V = nullptr;
1644  // (X & Y) == 0 ? X : X ^ Y --> X & ~Y
1645  if (TrueWhenUnset && TrueVal == X &&
1646  match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1647  V = Builder.CreateAnd(X, ~(*Y));
1648  // (X & Y) != 0 ? X ^ Y : X --> X & ~Y
1649  else if (!TrueWhenUnset && FalseVal == X &&
1650  match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1651  V = Builder.CreateAnd(X, ~(*Y));
1652  // (X & Y) == 0 ? X ^ Y : X --> X | Y
1653  else if (TrueWhenUnset && FalseVal == X &&
1654  match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1655  V = Builder.CreateOr(X, *Y);
1656  // (X & Y) != 0 ? X : X ^ Y --> X | Y
1657  else if (!TrueWhenUnset && TrueVal == X &&
1658  match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1659  V = Builder.CreateOr(X, *Y);
1660 
1661  if (V)
1662  return replaceInstUsesWith(SI, V);
1663  }
1664  }
1665 
1666  if (Instruction *V =
1667  foldSelectICmpAndAnd(SI.getType(), ICI, TrueVal, FalseVal, Builder))
1668  return V;
1669 
1670  if (Instruction *V = foldSelectCtlzToCttz(ICI, TrueVal, FalseVal, Builder))
1671  return V;
1672 
1673  if (Instruction *V = foldSelectZeroOrOnes(ICI, TrueVal, FalseVal, Builder))
1674  return V;
1675 
1677  return replaceInstUsesWith(SI, V);
1678 
1680  return replaceInstUsesWith(SI, V);
1681 
1682  if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
1683  return replaceInstUsesWith(SI, V);
1684 
1686  return replaceInstUsesWith(SI, V);
1687 
1689  return replaceInstUsesWith(SI, V);
1690 
1691  return Changed ? &SI : nullptr;
1692 }
1693 
1694 /// SI is a select whose condition is a PHI node (but the two may be in
1695 /// different blocks). See if the true/false values (V) are live in all of the
1696 /// predecessor blocks of the PHI. For example, cases like this can't be mapped:
1697 ///
1698 /// X = phi [ C1, BB1], [C2, BB2]
1699 /// Y = add
1700 /// Z = select X, Y, 0
1701 ///
1702 /// because Y is not live in BB1/BB2.
1703 static bool canSelectOperandBeMappingIntoPredBlock(const Value *V,
1704  const SelectInst &SI) {
1705  // If the value is a non-instruction value like a constant or argument, it
1706  // can always be mapped.
1707  const Instruction *I = dyn_cast<Instruction>(V);
1708  if (!I) return true;
1709 
1710  // If V is a PHI node defined in the same block as the condition PHI, we can
1711  // map the arguments.
1712  const PHINode *CondPHI = cast<PHINode>(SI.getCondition());
1713 
1714  if (const PHINode *VP = dyn_cast<PHINode>(I))
1715  if (VP->getParent() == CondPHI->getParent())
1716  return true;
1717 
1718  // Otherwise, if the PHI and select are defined in the same block and if V is
1719  // defined in a different block, then we can transform it.
1720  if (SI.getParent() == CondPHI->getParent() &&
1721  I->getParent() != CondPHI->getParent())
1722  return true;
1723 
1724  // Otherwise we have a 'hard' case and we can't tell without doing more
1725  // detailed dominator based analysis, punt.
1726  return false;
1727 }
1728 
1729 /// We have an SPF (e.g. a min or max) of an SPF of the form:
1730 /// SPF2(SPF1(A, B), C)
1732  SelectPatternFlavor SPF1, Value *A,
1733  Value *B, Instruction &Outer,
1734  SelectPatternFlavor SPF2,
1735  Value *C) {
1736  if (Outer.getType() != Inner->getType())
1737  return nullptr;
1738 
1739  if (C == A || C == B) {
1740  // MAX(MAX(A, B), B) -> MAX(A, B)
1741  // MIN(MIN(a, b), a) -> MIN(a, b)
1742  // TODO: This could be done in instsimplify.
1743  if (SPF1 == SPF2 && SelectPatternResult::isMinOrMax(SPF1))
1744  return replaceInstUsesWith(Outer, Inner);
1745  }
1746 
1747  return nullptr;
1748 }
1749 
1750 /// Turn select C, (X + Y), (X - Y) --> (X + (select C, Y, (-Y))).
1751 /// This is even legal for FP.
1752 static Instruction *foldAddSubSelect(SelectInst &SI,
1754  Value *CondVal = SI.getCondition();
1755  Value *TrueVal = SI.getTrueValue();
1756  Value *FalseVal = SI.getFalseValue();
1757  auto *TI = dyn_cast<Instruction>(TrueVal);
1758  auto *FI = dyn_cast<Instruction>(FalseVal);
1759  if (!TI || !FI || !TI->hasOneUse() || !FI->hasOneUse())
1760  return nullptr;
1761 
1762  Instruction *AddOp = nullptr, *SubOp = nullptr;
1763  if ((TI->getOpcode() == Instruction::Sub &&
1764  FI->getOpcode() == Instruction::Add) ||
1765  (TI->getOpcode() == Instruction::FSub &&
1766  FI->getOpcode() == Instruction::FAdd)) {
1767  AddOp = FI;
1768  SubOp = TI;
1769  } else if ((FI->getOpcode() == Instruction::Sub &&
1770  TI->getOpcode() == Instruction::Add) ||
1771  (FI->getOpcode() == Instruction::FSub &&
1772  TI->getOpcode() == Instruction::FAdd)) {
1773  AddOp = TI;
1774  SubOp = FI;
1775  }
1776 
1777  if (AddOp) {
1778  Value *OtherAddOp = nullptr;
1779  if (SubOp->getOperand(0) == AddOp->getOperand(0)) {
1780  OtherAddOp = AddOp->getOperand(1);
1781  } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) {
1782  OtherAddOp = AddOp->getOperand(0);
1783  }
1784 
1785  if (OtherAddOp) {
1786  // So at this point we know we have (Y -> OtherAddOp):
1787  // select C, (add X, Y), (sub X, Z)
1788  Value *NegVal; // Compute -Z
1789  if (SI.getType()->isFPOrFPVectorTy()) {
1790  NegVal = Builder.CreateFNeg(SubOp->getOperand(1));
1791  if (Instruction *NegInst = dyn_cast<Instruction>(NegVal)) {
1792  FastMathFlags Flags = AddOp->getFastMathFlags();
1793  Flags &= SubOp->getFastMathFlags();
1794  NegInst->setFastMathFlags(Flags);
1795  }
1796  } else {
1797  NegVal = Builder.CreateNeg(SubOp->getOperand(1));
1798  }
1799 
1800  Value *NewTrueOp = OtherAddOp;
1801  Value *NewFalseOp = NegVal;
1802  if (AddOp != TI)
1803  std::swap(NewTrueOp, NewFalseOp);
1804  Value *NewSel = Builder.CreateSelect(CondVal, NewTrueOp, NewFalseOp,
1805  SI.getName() + ".p", &SI);
1806 
1807  if (SI.getType()->isFPOrFPVectorTy()) {
1808  Instruction *RI =
1809  BinaryOperator::CreateFAdd(SubOp->getOperand(0), NewSel);
1810 
1811  FastMathFlags Flags = AddOp->getFastMathFlags();
1812  Flags &= SubOp->getFastMathFlags();
1813  RI->setFastMathFlags(Flags);
1814  return RI;
1815  } else
1816  return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel);
1817  }
1818  }
1819  return nullptr;
1820 }
1821 
1822 /// Turn X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
1823 /// And X - Y overflows ? 0 : X - Y -> usub_sat X, Y
1824 /// Along with a number of patterns similar to:
1825 /// X + Y overflows ? (X < 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1826 /// X - Y overflows ? (X > 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1827 static Instruction *
1828 foldOverflowingAddSubSelect(SelectInst &SI, InstCombiner::BuilderTy &Builder) {
1829  Value *CondVal = SI.getCondition();
1830  Value *TrueVal = SI.getTrueValue();
1831  Value *FalseVal = SI.getFalseValue();
1832 
1833  WithOverflowInst *II;
1834  if (!match(CondVal, m_ExtractValue<1>(m_WithOverflowInst(II))) ||
1835  !match(FalseVal, m_ExtractValue<0>(m_Specific(II))))
1836  return nullptr;
1837 
1838  Value *X = II->getLHS();
1839  Value *Y = II->getRHS();
1840 
1841  auto IsSignedSaturateLimit = [&](Value *Limit, bool IsAdd) {
1842  Type *Ty = Limit->getType();
1843 
1844  ICmpInst::Predicate Pred;
1845  Value *TrueVal, *FalseVal, *Op;
1846  const APInt *C;
1847  if (!match(Limit, m_Select(m_ICmp(Pred, m_Value(Op), m_APInt(C)),
1849  return false;
1850 
1851  auto IsZeroOrOne = [](const APInt &C) { return C.isZero() || C.isOne(); };
1852  auto IsMinMax = [&](Value *Min, Value *Max) {
1855  return match(Min, m_SpecificInt(MinVal)) &&
1856  match(Max, m_SpecificInt(MaxVal));
1857  };
1858 
1859  if (Op != X && Op != Y)
1860  return false;
1861 
1862  if (IsAdd) {
1863  // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1864  // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1865  // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1866  // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1867  if (Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
1868  IsMinMax(TrueVal, FalseVal))
1869  return true;
1870  // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1871  // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1872  // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1873  // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1874  if (Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
1875  IsMinMax(FalseVal, TrueVal))
1876  return true;
1877  } else {
1878  // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1879  // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1880  if (Op == X && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C + 1) &&
1881  IsMinMax(TrueVal, FalseVal))
1882  return true;
1883  // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1884  // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1885  if (Op == X && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 2) &&
1886  IsMinMax(FalseVal, TrueVal))
1887  return true;
1888  // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1889  // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1890  if (Op == Y && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
1891  IsMinMax(FalseVal, TrueVal))
1892  return true;
1893  // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1894  // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1895  if (Op == Y && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
1896  IsMinMax(TrueVal, FalseVal))
1897  return true;
1898  }
1899 
1900  return false;
1901  };
1902 
1903  Intrinsic::ID NewIntrinsicID;
1904  if (II->getIntrinsicID() == Intrinsic::uadd_with_overflow &&
1905  match(TrueVal, m_AllOnes()))
1906  // X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
1907  NewIntrinsicID = Intrinsic::uadd_sat;
1908  else if (II->getIntrinsicID() == Intrinsic::usub_with_overflow &&
1909  match(TrueVal, m_Zero()))
1910  // X - Y overflows ? 0 : X - Y -> usub_sat X, Y
1911  NewIntrinsicID = Intrinsic::usub_sat;
1912  else if (II->getIntrinsicID() == Intrinsic::sadd_with_overflow &&
1913  IsSignedSaturateLimit(TrueVal, /*IsAdd=*/true))
1914  // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1915  // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1916  // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1917  // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1918  // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1919  // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1920  // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1921  // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1922  NewIntrinsicID = Intrinsic::sadd_sat;
1923  else if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow &&
1924  IsSignedSaturateLimit(TrueVal, /*IsAdd=*/false))
1925  // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1926  // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1927  // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1928  // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1929  // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1930  // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1931  // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1932  // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1933  NewIntrinsicID = Intrinsic::ssub_sat;
1934  else
1935  return nullptr;
1936 
1937  Function *F =
1938  Intrinsic::getDeclaration(SI.getModule(), NewIntrinsicID, SI.getType());
1939  return CallInst::Create(F, {X, Y});
1940 }
1941 
1943  Constant *C;
1944  if (!match(Sel.getTrueValue(), m_Constant(C)) &&
1945  !match(Sel.getFalseValue(), m_Constant(C)))
1946  return nullptr;
1947 
1948  Instruction *ExtInst;
1949  if (!match(Sel.getTrueValue(), m_Instruction(ExtInst)) &&
1950  !match(Sel.getFalseValue(), m_Instruction(ExtInst)))
1951  return nullptr;
1952 
1953  auto ExtOpcode = ExtInst->getOpcode();
1954  if (ExtOpcode != Instruction::ZExt && ExtOpcode != Instruction::SExt)
1955  return nullptr;
1956 
1957  // If we are extending from a boolean type or if we can create a select that
1958  // has the same size operands as its condition, try to narrow the select.
1959  Value *X = ExtInst->getOperand(0);
1960  Type *SmallType = X->getType();
1961  Value *Cond = Sel.getCondition();
1962  auto *Cmp = dyn_cast<CmpInst>(Cond);
1963  if (!SmallType->isIntOrIntVectorTy(1) &&
1964  (!Cmp || Cmp->getOperand(0)->getType() != SmallType))
1965  return nullptr;
1966 
1967  // If the constant is the same after truncation to the smaller type and
1968  // extension to the original type, we can narrow the select.
1969  Type *SelType = Sel.getType();
1970  Constant *TruncC = ConstantExpr::getTrunc(C, SmallType);
1971  Constant *ExtC = ConstantExpr::getCast(ExtOpcode, TruncC, SelType);
1972  if (ExtC == C && ExtInst->hasOneUse()) {
1973  Value *TruncCVal = cast<Value>(TruncC);
1974  if (ExtInst == Sel.getFalseValue())
1975  std::swap(X, TruncCVal);
1976 
1977  // select Cond, (ext X), C --> ext(select Cond, X, C')
1978  // select Cond, C, (ext X) --> ext(select Cond, C', X)
1979  Value *NewSel = Builder.CreateSelect(Cond, X, TruncCVal, "narrow", &Sel);
1980  return CastInst::Create(Instruction::CastOps(ExtOpcode), NewSel, SelType);
1981  }
1982 
1983  // If one arm of the select is the extend of the condition, replace that arm
1984  // with the extension of the appropriate known bool value.
1985  if (Cond == X) {
1986  if (ExtInst == Sel.getTrueValue()) {
1987  // select X, (sext X), C --> select X, -1, C
1988  // select X, (zext X), C --> select X, 1, C
1989  Constant *One = ConstantInt::getTrue(SmallType);
1990  Constant *AllOnesOrOne = ConstantExpr::getCast(ExtOpcode, One, SelType);
1991  return SelectInst::Create(Cond, AllOnesOrOne, C, "", nullptr, &Sel);
1992  } else {
1993  // select X, C, (sext X) --> select X, C, 0
1994  // select X, C, (zext X) --> select X, C, 0
1995  Constant *Zero = ConstantInt::getNullValue(SelType);
1996  return SelectInst::Create(Cond, C, Zero, "", nullptr, &Sel);
1997  }
1998  }
1999 
2000  return nullptr;
2001 }
2002 
2003 /// Try to transform a vector select with a constant condition vector into a
2004 /// shuffle for easier combining with other shuffles and insert/extract.
2005 static Instruction *canonicalizeSelectToShuffle(SelectInst &SI) {
2006  Value *CondVal = SI.getCondition();
2007  Constant *CondC;
2008  auto *CondValTy = dyn_cast<FixedVectorType>(CondVal->getType());
2009  if (!CondValTy || !match(CondVal, m_Constant(CondC)))
2010  return nullptr;
2011 
2012  unsigned NumElts = CondValTy->getNumElements();
2014  Mask.reserve(NumElts);
2015  for (unsigned i = 0; i != NumElts; ++i) {
2016  Constant *Elt = CondC->getAggregateElement(i);
2017  if (!Elt)
2018  return nullptr;
2019 
2020  if (Elt->isOneValue()) {
2021  // If the select condition element is true, choose from the 1st vector.
2022  Mask.push_back(i);
2023  } else if (Elt->isNullValue()) {
2024  // If the select condition element is false, choose from the 2nd vector.
2025  Mask.push_back(i + NumElts);
2026  } else if (isa<UndefValue>(Elt)) {
2027  // Undef in a select condition (choose one of the operands) does not mean
2028  // the same thing as undef in a shuffle mask (any value is acceptable), so
2029  // give up.
2030  return nullptr;
2031  } else {
2032  // Bail out on a constant expression.
2033  return nullptr;
2034  }
2035  }
2036 
2037  return new ShuffleVectorInst(SI.getTrueValue(), SI.getFalseValue(), Mask);
2038 }
2039 
2040 /// If we have a select of vectors with a scalar condition, try to convert that
2041 /// to a vector select by splatting the condition. A splat may get folded with
2042 /// other operations in IR and having all operands of a select be vector types
2043 /// is likely better for vector codegen.
2044 static Instruction *canonicalizeScalarSelectOfVecs(SelectInst &Sel,
2045  InstCombinerImpl &IC) {
2046  auto *Ty = dyn_cast<VectorType>(Sel.getType());
2047  if (!Ty)
2048  return nullptr;
2049 
2050  // We can replace a single-use extract with constant index.
2051  Value *Cond = Sel.getCondition();
2053  return nullptr;
2054 
2055  // select (extelt V, Index), T, F --> select (splat V, Index), T, F
2056  // Splatting the extracted condition reduces code (we could directly create a
2057  // splat shuffle of the source vector to eliminate the intermediate step).
2058  return IC.replaceOperand(
2059  Sel, 0, IC.Builder.CreateVectorSplat(Ty->getElementCount(), Cond));
2060 }
2061 
2062 /// Reuse bitcasted operands between a compare and select:
2063 /// select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2064 /// bitcast (select (cmp (bitcast C), (bitcast D)), (bitcast C), (bitcast D))
2065 static Instruction *foldSelectCmpBitcasts(SelectInst &Sel,
2067  Value *Cond = Sel.getCondition();
2068  Value *TVal = Sel.getTrueValue();
2069  Value *FVal = Sel.getFalseValue();
2070 
2071  CmpInst::Predicate Pred;
2072  Value *A, *B;
2073  if (!match(Cond, m_Cmp(Pred, m_Value(A), m_Value(B))))
2074  return nullptr;
2075 
2076  // The select condition is a compare instruction. If the select's true/false
2077  // values are already the same as the compare operands, there's nothing to do.
2078  if (TVal == A || TVal == B || FVal == A || FVal == B)
2079  return nullptr;
2080 
2081  Value *C, *D;
2082  if (!match(A, m_BitCast(m_Value(C))) || !match(B, m_BitCast(m_Value(D))))
2083  return nullptr;
2084 
2085  // select (cmp (bitcast C), (bitcast D)), (bitcast TSrc), (bitcast FSrc)
2086  Value *TSrc, *FSrc;
2087  if (!match(TVal, m_BitCast(m_Value(TSrc))) ||
2088  !match(FVal, m_BitCast(m_Value(FSrc))))
2089  return nullptr;
2090 
2091  // If the select true/false values are *different bitcasts* of the same source
2092  // operands, make the select operands the same as the compare operands and
2093  // cast the result. This is the canonical select form for min/max.
2094  Value *NewSel;
2095  if (TSrc == C && FSrc == D) {
2096  // select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2097  // bitcast (select (cmp A, B), A, B)
2098  NewSel = Builder.CreateSelect(Cond, A, B, "", &Sel);
2099  } else if (TSrc == D && FSrc == C) {
2100  // select (cmp (bitcast C), (bitcast D)), (bitcast' D), (bitcast' C) -->
2101  // bitcast (select (cmp A, B), B, A)
2102  NewSel = Builder.CreateSelect(Cond, B, A, "", &Sel);
2103  } else {
2104  return nullptr;
2105  }
2106  return CastInst::CreateBitOrPointerCast(NewSel, Sel.getType());
2107 }
2108 
2109 /// Try to eliminate select instructions that test the returned flag of cmpxchg
2110 /// instructions.
2111 ///
2112 /// If a select instruction tests the returned flag of a cmpxchg instruction and
2113 /// selects between the returned value of the cmpxchg instruction its compare
2114 /// operand, the result of the select will always be equal to its false value.
2115 /// For example:
2116 ///
2117 /// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2118 /// %1 = extractvalue { i64, i1 } %0, 1
2119 /// %2 = extractvalue { i64, i1 } %0, 0
2120 /// %3 = select i1 %1, i64 %compare, i64 %2
2121 /// ret i64 %3
2122 ///
2123 /// The returned value of the cmpxchg instruction (%2) is the original value
2124 /// located at %ptr prior to any update. If the cmpxchg operation succeeds, %2
2125 /// must have been equal to %compare. Thus, the result of the select is always
2126 /// equal to %2, and the code can be simplified to:
2127 ///
2128 /// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2129 /// %1 = extractvalue { i64, i1 } %0, 0
2130 /// ret i64 %1
2131 ///
2132 static Value *foldSelectCmpXchg(SelectInst &SI) {
2133  // A helper that determines if V is an extractvalue instruction whose
2134  // aggregate operand is a cmpxchg instruction and whose single index is equal
2135  // to I. If such conditions are true, the helper returns the cmpxchg
2136  // instruction; otherwise, a nullptr is returned.
2137  auto isExtractFromCmpXchg = [](Value *V, unsigned I) -> AtomicCmpXchgInst * {
2138  auto *Extract = dyn_cast<ExtractValueInst>(V);
2139  if (!Extract)
2140  return nullptr;
2141  if (Extract->getIndices()[0] != I)
2142  return nullptr;
2143  return dyn_cast<AtomicCmpXchgInst>(Extract->getAggregateOperand());
2144  };
2145 
2146  // If the select has a single user, and this user is a select instruction that
2147  // we can simplify, skip the cmpxchg simplification for now.
2148  if (SI.hasOneUse())
2149  if (auto *Select = dyn_cast<SelectInst>(SI.user_back()))
2150  if (Select->getCondition() == SI.getCondition())
2151  if (Select->getFalseValue() == SI.getTrueValue() ||
2152  Select->getTrueValue() == SI.getFalseValue())
2153  return nullptr;
2154 
2155  // Ensure the select condition is the returned flag of a cmpxchg instruction.
2156  auto *CmpXchg = isExtractFromCmpXchg(SI.getCondition(), 1);
2157  if (!CmpXchg)
2158  return nullptr;
2159 
2160  // Check the true value case: The true value of the select is the returned
2161  // value of the same cmpxchg used by the condition, and the false value is the
2162  // cmpxchg instruction's compare operand.
2163  if (auto *X = isExtractFromCmpXchg(SI.getTrueValue(), 0))
2164  if (X == CmpXchg && X->getCompareOperand() == SI.getFalseValue())
2165  return SI.getFalseValue();
2166 
2167  // Check the false value case: The false value of the select is the returned
2168  // value of the same cmpxchg used by the condition, and the true value is the
2169  // cmpxchg instruction's compare operand.
2170  if (auto *X = isExtractFromCmpXchg(SI.getFalseValue(), 0))
2171  if (X == CmpXchg && X->getCompareOperand() == SI.getTrueValue())
2172  return SI.getFalseValue();
2173 
2174  return nullptr;
2175 }
2176 
2177 /// Try to reduce a funnel/rotate pattern that includes a compare and select
2178 /// into a funnel shift intrinsic. Example:
2179 /// rotl32(a, b) --> (b == 0 ? a : ((a >> (32 - b)) | (a << b)))
2180 /// --> call llvm.fshl.i32(a, a, b)
2181 /// fshl32(a, b, c) --> (c == 0 ? a : ((b >> (32 - c)) | (a << c)))
2182 /// --> call llvm.fshl.i32(a, b, c)
2183 /// fshr32(a, b, c) --> (c == 0 ? b : ((a >> (32 - c)) | (b << c)))
2184 /// --> call llvm.fshr.i32(a, b, c)
2185 static Instruction *foldSelectFunnelShift(SelectInst &Sel,
2187  // This must be a power-of-2 type for a bitmasking transform to be valid.
2188  unsigned Width = Sel.getType()->getScalarSizeInBits();
2189  if (!isPowerOf2_32(Width))
2190  return nullptr;
2191 
2192  BinaryOperator *Or0, *Or1;
2193  if (!match(Sel.getFalseValue(), m_OneUse(m_Or(m_BinOp(Or0), m_BinOp(Or1)))))
2194  return nullptr;
2195 
2196  Value *SV0, *SV1, *SA0, *SA1;
2197  if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(SV0),
2198  m_ZExtOrSelf(m_Value(SA0))))) ||
2199  !match(Or1, m_OneUse(m_LogicalShift(m_Value(SV1),
2200  m_ZExtOrSelf(m_Value(SA1))))) ||
2201  Or0->getOpcode() == Or1->getOpcode())
2202  return nullptr;
2203 
2204  // Canonicalize to or(shl(SV0, SA0), lshr(SV1, SA1)).
2205  if (Or0->getOpcode() == BinaryOperator::LShr) {
2206  std::swap(Or0, Or1);
2207  std::swap(SV0, SV1);
2208  std::swap(SA0, SA1);
2209  }
2210  assert(Or0->getOpcode() == BinaryOperator::Shl &&
2211  Or1->getOpcode() == BinaryOperator::LShr &&
2212  "Illegal or(shift,shift) pair");
2213 
2214  // Check the shift amounts to see if they are an opposite pair.
2215  Value *ShAmt;
2216  if (match(SA1, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA0)))))
2217  ShAmt = SA0;
2218  else if (match(SA0, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA1)))))
2219  ShAmt = SA1;
2220  else
2221  return nullptr;
2222 
2223  // We should now have this pattern:
2224  // select ?, TVal, (or (shl SV0, SA0), (lshr SV1, SA1))
2225  // The false value of the select must be a funnel-shift of the true value:
2226  // IsFShl -> TVal must be SV0 else TVal must be SV1.
2227  bool IsFshl = (ShAmt == SA0);
2228  Value *TVal = Sel.getTrueValue();
2229  if ((IsFshl && TVal != SV0) || (!IsFshl && TVal != SV1))
2230  return nullptr;
2231 
2232  // Finally, see if the select is filtering out a shift-by-zero.
2233  Value *Cond = Sel.getCondition();
2234  ICmpInst::Predicate Pred;
2235  if (!match(Cond, m_OneUse(m_ICmp(Pred, m_Specific(ShAmt), m_ZeroInt()))) ||
2236  Pred != ICmpInst::ICMP_EQ)
2237  return nullptr;
2238 
2239  // If this is not a rotate then the select was blocking poison from the
2240  // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.
2241  if (SV0 != SV1) {
2242  if (IsFshl && !llvm::isGuaranteedNotToBePoison(SV1))
2243  SV1 = Builder.CreateFreeze(SV1);
2244  else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(SV0))
2245  SV0 = Builder.CreateFreeze(SV0);
2246  }
2247 
2248  // This is a funnel/rotate that avoids shift-by-bitwidth UB in a suboptimal way.
2249  // Convert to funnel shift intrinsic.
2250  Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2251  Function *F = Intrinsic::getDeclaration(Sel.getModule(), IID, Sel.getType());
2252  ShAmt = Builder.CreateZExt(ShAmt, Sel.getType());
2253  return CallInst::Create(F, { SV0, SV1, ShAmt });
2254 }
2255 
2256 static Instruction *foldSelectToCopysign(SelectInst &Sel,
2258  Value *Cond = Sel.getCondition();
2259  Value *TVal = Sel.getTrueValue();
2260  Value *FVal = Sel.getFalseValue();
2261  Type *SelType = Sel.getType();
2262 
2263  // Match select ?, TC, FC where the constants are equal but negated.
2264  // TODO: Generalize to handle a negated variable operand?
2265  const APFloat *TC, *FC;
2266  if (!match(TVal, m_APFloatAllowUndef(TC)) ||
2267  !match(FVal, m_APFloatAllowUndef(FC)) ||
2268  !abs(*TC).bitwiseIsEqual(abs(*FC)))
2269  return nullptr;
2270 
2271  assert(TC != FC && "Expected equal select arms to simplify");
2272 
2273  Value *X;
2274  const APInt *C;
2275  bool IsTrueIfSignSet;
2276  ICmpInst::Predicate Pred;
2277  if (!match(Cond, m_OneUse(m_ICmp(Pred, m_BitCast(m_Value(X)), m_APInt(C)))) ||
2278  !InstCombiner::isSignBitCheck(Pred, *C, IsTrueIfSignSet) ||
2279  X->getType() != SelType)
2280  return nullptr;
2281 
2282  // If needed, negate the value that will be the sign argument of the copysign:
2283  // (bitcast X) < 0 ? -TC : TC --> copysign(TC, X)
2284  // (bitcast X) < 0 ? TC : -TC --> copysign(TC, -X)
2285  // (bitcast X) >= 0 ? -TC : TC --> copysign(TC, -X)
2286  // (bitcast X) >= 0 ? TC : -TC --> copysign(TC, X)
2287  // Note: FMF from the select can not be propagated to the new instructions.
2288  if (IsTrueIfSignSet ^ TC->isNegative())
2289  X = Builder.CreateFNeg(X);
2290 
2291  // Canonicalize the magnitude argument as the positive constant since we do
2292  // not care about its sign.
2293  Value *MagArg = ConstantFP::get(SelType, abs(*TC));
2294  Function *F = Intrinsic::getDeclaration(Sel.getModule(), Intrinsic::copysign,
2295  Sel.getType());
2296  return CallInst::Create(F, { MagArg, X });
2297 }
2298 
2300  auto *VecTy = dyn_cast<FixedVectorType>(Sel.getType());
2301  if (!VecTy)
2302  return nullptr;
2303 
2304  unsigned NumElts = VecTy->getNumElements();
2305  APInt UndefElts(NumElts, 0);
2306  APInt AllOnesEltMask(APInt::getAllOnes(NumElts));
2307  if (Value *V = SimplifyDemandedVectorElts(&Sel, AllOnesEltMask, UndefElts)) {
2308  if (V != &Sel)
2309  return replaceInstUsesWith(Sel, V);
2310  return &Sel;
2311  }
2312 
2313  // A select of a "select shuffle" with a common operand can be rearranged
2314  // to select followed by "select shuffle". Because of poison, this only works
2315  // in the case of a shuffle with no undefined mask elements.
2316  Value *Cond = Sel.getCondition();
2317  Value *TVal = Sel.getTrueValue();
2318  Value *FVal = Sel.getFalseValue();
2319  Value *X, *Y;
2321  if (match(TVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
2323  cast<ShuffleVectorInst>(TVal)->isSelect()) {
2324  if (X == FVal) {
2325  // select Cond, (shuf_sel X, Y), X --> shuf_sel X, (select Cond, Y, X)
2326  Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
2327  return new ShuffleVectorInst(X, NewSel, Mask);
2328  }
2329  if (Y == FVal) {
2330  // select Cond, (shuf_sel X, Y), Y --> shuf_sel (select Cond, X, Y), Y
2331  Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
2332  return new ShuffleVectorInst(NewSel, Y, Mask);
2333  }
2334  }
2335  if (match(FVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
2337  cast<ShuffleVectorInst>(FVal)->isSelect()) {
2338  if (X == TVal) {
2339  // select Cond, X, (shuf_sel X, Y) --> shuf_sel X, (select Cond, X, Y)
2340  Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
2341  return new ShuffleVectorInst(X, NewSel, Mask);
2342  }
2343  if (Y == TVal) {
2344  // select Cond, Y, (shuf_sel X, Y) --> shuf_sel (select Cond, Y, X), Y
2345  Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
2346  return new ShuffleVectorInst(NewSel, Y, Mask);
2347  }
2348  }
2349 
2350  return nullptr;
2351 }
2352 
2353 static Instruction *foldSelectToPhiImpl(SelectInst &Sel, BasicBlock *BB,
2354  const DominatorTree &DT,
2356  // Find the block's immediate dominator that ends with a conditional branch
2357  // that matches select's condition (maybe inverted).
2358  auto *IDomNode = DT[BB]->getIDom();
2359  if (!IDomNode)
2360  return nullptr;
2361  BasicBlock *IDom = IDomNode->getBlock();
2362 
2363  Value *Cond = Sel.getCondition();
2364  Value *IfTrue, *IfFalse;
2365  BasicBlock *TrueSucc, *FalseSucc;
2366  if (match(IDom->getTerminator(),
2367  m_Br(m_Specific(Cond), m_BasicBlock(TrueSucc),
2368  m_BasicBlock(FalseSucc)))) {
2369  IfTrue = Sel.getTrueValue();
2370  IfFalse = Sel.getFalseValue();
2371  } else if (match(IDom->getTerminator(),
2372  m_Br(m_Not(m_Specific(Cond)), m_BasicBlock(TrueSucc),
2373  m_BasicBlock(FalseSucc)))) {
2374  IfTrue = Sel.getFalseValue();
2375  IfFalse = Sel.getTrueValue();
2376  } else
2377  return nullptr;
2378 
2379  // Make sure the branches are actually different.
2380  if (TrueSucc == FalseSucc)
2381  return nullptr;
2382 
2383  // We want to replace select %cond, %a, %b with a phi that takes value %a
2384  // for all incoming edges that are dominated by condition `%cond == true`,
2385  // and value %b for edges dominated by condition `%cond == false`. If %a
2386  // or %b are also phis from the same basic block, we can go further and take
2387  // their incoming values from the corresponding blocks.
2388  BasicBlockEdge TrueEdge(IDom, TrueSucc);
2389  BasicBlockEdge FalseEdge(IDom, FalseSucc);
2391  for (auto *Pred : predecessors(BB)) {
2392  // Check implication.
2393  BasicBlockEdge Incoming(Pred, BB);
2394  if (DT.dominates(TrueEdge, Incoming))
2395  Inputs[Pred] = IfTrue->DoPHITranslation(BB, Pred);
2396  else if (DT.dominates(FalseEdge, Incoming))
2397  Inputs[Pred] = IfFalse->DoPHITranslation(BB, Pred);
2398  else
2399  return nullptr;
2400  // Check availability.
2401  if (auto *Insn = dyn_cast<Instruction>(Inputs[Pred]))
2402  if (!DT.dominates(Insn, Pred->getTerminator()))
2403  return nullptr;
2404  }
2405 
2406  Builder.SetInsertPoint(&*BB->begin());
2407  auto *PN = Builder.CreatePHI(Sel.getType(), Inputs.size());
2408  for (auto *Pred : predecessors(BB))
2409  PN->addIncoming(Inputs[Pred], Pred);
2410  PN->takeName(&Sel);
2411  return PN;
2412 }
2413 
2414 static Instruction *foldSelectToPhi(SelectInst &Sel, const DominatorTree &DT,
2416  // Try to replace this select with Phi in one of these blocks.
2417  SmallSetVector<BasicBlock *, 4> CandidateBlocks;
2418  CandidateBlocks.insert(Sel.getParent());
2419  for (Value *V : Sel.operands())
2420  if (auto *I = dyn_cast<Instruction>(V))
2421  CandidateBlocks.insert(I->getParent());
2422 
2423  for (BasicBlock *BB : CandidateBlocks)
2424  if (auto *PN = foldSelectToPhiImpl(Sel, BB, DT, Builder))
2425  return PN;
2426  return nullptr;
2427 }
2428 
2429 static Value *foldSelectWithFrozenICmp(SelectInst &Sel, InstCombiner::BuilderTy &Builder) {
2430  FreezeInst *FI = dyn_cast<FreezeInst>(Sel.getCondition());
2431  if (!FI)
2432  return nullptr;
2433 
2434  Value *Cond = FI->getOperand(0);
2435  Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
2436 
2437  // select (freeze(x == y)), x, y --> y
2438  // select (freeze(x != y)), x, y --> x
2439  // The freeze should be only used by this select. Otherwise, remaining uses of
2440  // the freeze can observe a contradictory value.
2441  // c = freeze(x == y) ; Let's assume that y = poison & x = 42; c is 0 or 1
2442  // a = select c, x, y ;
2443  // f(a, c) ; f(poison, 1) cannot happen, but if a is folded
2444  // ; to y, this can happen.
2445  CmpInst::Predicate Pred;
2446  if (FI->hasOneUse() &&
2448  (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)) {
2449  return Pred == ICmpInst::ICMP_EQ ? FalseVal : TrueVal;
2450  }
2451 
2452  return nullptr;
2453 }
2454 
2455 Instruction *InstCombinerImpl::foldAndOrOfSelectUsingImpliedCond(Value *Op,
2456  SelectInst &SI,
2457  bool IsAnd) {
2458  Value *CondVal = SI.getCondition();
2459  Value *A = SI.getTrueValue();
2460  Value *B = SI.getFalseValue();
2461 
2462  assert(Op->getType()->isIntOrIntVectorTy(1) &&
2463  "Op must be either i1 or vector of i1.");
2464 
2465  Optional<bool> Res = isImpliedCondition(Op, CondVal, DL, IsAnd);
2466  if (!Res)
2467  return nullptr;
2468 
2469  Value *Zero = Constant::getNullValue(A->getType());
2470  Value *One = Constant::getAllOnesValue(A->getType());
2471 
2472  if (*Res == true) {
2473  if (IsAnd)
2474  // select op, (select cond, A, B), false => select op, A, false
2475  // and op, (select cond, A, B) => select op, A, false
2476  // if op = true implies condval = true.
2477  return SelectInst::Create(Op, A, Zero);
2478  else
2479  // select op, true, (select cond, A, B) => select op, true, A
2480  // or op, (select cond, A, B) => select op, true, A
2481  // if op = false implies condval = true.
2482  return SelectInst::Create(Op, One, A);
2483  } else {
2484  if (IsAnd)
2485  // select op, (select cond, A, B), false => select op, B, false
2486  // and op, (select cond, A, B) => select op, B, false
2487  // if op = true implies condval = false.
2488  return SelectInst::Create(Op, B, Zero);
2489  else
2490  // select op, true, (select cond, A, B) => select op, true, B
2491  // or op, (select cond, A, B) => select op, true, B
2492  // if op = false implies condval = false.
2493  return SelectInst::Create(Op, One, B);
2494  }
2495 }
2496 
2497 // Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need
2498 // fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work.
2499 static Instruction *foldSelectWithFCmpToFabs(SelectInst &SI,
2500  InstCombinerImpl &IC) {
2501  Value *CondVal = SI.getCondition();
2502 
2503  for (bool Swap : {false, true}) {
2504  Value *TrueVal = SI.getTrueValue();
2505  Value *X = SI.getFalseValue();
2506  CmpInst::Predicate Pred;
2507 
2508  if (Swap)
2509  std::swap(TrueVal, X);
2510 
2511  if (!match(CondVal, m_FCmp(Pred, m_Specific(X), m_AnyZeroFP())))
2512  continue;
2513 
2514  // fold (X <= +/-0.0) ? (0.0 - X) : X to fabs(X), when 'Swap' is false
2515  // fold (X > +/-0.0) ? X : (0.0 - X) to fabs(X), when 'Swap' is true
2516  if (match(TrueVal, m_FSub(m_PosZeroFP(), m_Specific(X)))) {
2517  if (!Swap && (Pred == FCmpInst::FCMP_OLE || Pred == FCmpInst::FCMP_ULE)) {
2518  Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2519  return IC.replaceInstUsesWith(SI, Fabs);
2520  }
2521  if (Swap && (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_UGT)) {
2522  Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2523  return IC.replaceInstUsesWith(SI, Fabs);
2524  }
2525  }
2526 
2527  // With nsz, when 'Swap' is false:
2528  // fold (X < +/-0.0) ? -X : X or (X <= +/-0.0) ? -X : X to fabs(X)
2529  // fold (X > +/-0.0) ? -X : X or (X >= +/-0.0) ? -X : X to -fabs(x)
2530  // when 'Swap' is true:
2531  // fold (X > +/-0.0) ? X : -X or (X >= +/-0.0) ? X : -X to fabs(X)
2532  // fold (X < +/-0.0) ? X : -X or (X <= +/-0.0) ? X : -X to -fabs(X)
2533  if (!match(TrueVal, m_FNeg(m_Specific(X))) || !SI.hasNoSignedZeros())
2534  return nullptr;
2535 
2536  if (Swap)
2537  Pred = FCmpInst::getSwappedPredicate(Pred);
2538 
2539  bool IsLTOrLE = Pred == FCmpInst::FCMP_OLT || Pred == FCmpInst::FCMP_OLE ||
2540  Pred == FCmpInst::FCMP_ULT || Pred == FCmpInst::FCMP_ULE;
2541  bool IsGTOrGE = Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_OGE ||
2542  Pred == FCmpInst::FCMP_UGT || Pred == FCmpInst::FCMP_UGE;
2543 
2544  if (IsLTOrLE) {
2545  Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2546  return IC.replaceInstUsesWith(SI, Fabs);
2547  }
2548  if (IsGTOrGE) {
2549  Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);
2550  Instruction *NewFNeg = UnaryOperator::CreateFNeg(Fabs);
2551  NewFNeg->setFastMathFlags(SI.getFastMathFlags());
2552  return NewFNeg;
2553  }
2554  }
2555 
2556  return nullptr;
2557 }
2558 
2559 // Match the following IR pattern:
2560 // %x.lowbits = and i8 %x, %lowbitmask
2561 // %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 0
2562 // %x.biased = add i8 %x, %bias
2563 // %x.biased.highbits = and i8 %x.biased, %highbitmask
2564 // %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
2565 // Define:
2566 // %alignment = add i8 %lowbitmask, 1
2567 // Iff 1. an %alignment is a power-of-two (aka, %lowbitmask is a low bit mask)
2568 // and 2. %bias is equal to either %lowbitmask or %alignment,
2569 // and 3. %highbitmask is equal to ~%lowbitmask (aka, to -%alignment)
2570 // then this pattern can be transformed into:
2571 // %x.offset = add i8 %x, %lowbitmask
2572 // %x.roundedup = and i8 %x.offset, %highbitmask
2573 static Value *
2574 foldRoundUpIntegerWithPow2Alignment(SelectInst &SI,
2576  Value *Cond = SI.getCondition();
2577  Value *X = SI.getTrueValue();
2578  Value *XBiasedHighBits = SI.getFalseValue();
2579 
2580  ICmpInst::Predicate Pred;
2581  Value *XLowBits;
2582  if (!match(Cond, m_ICmp(Pred, m_Value(XLowBits), m_ZeroInt())) ||
2583  !ICmpInst::isEquality(Pred))
2584  return nullptr;
2585 
2586  if (Pred == ICmpInst::Predicate::ICMP_NE)
2587  std::swap(X, XBiasedHighBits);
2588 
2589  // FIXME: we could support non non-splats here.
2590 
2591  const APInt *LowBitMaskCst;
2592  if (!match(XLowBits, m_And(m_Specific(X), m_APIntAllowUndef(LowBitMaskCst))))
2593  return nullptr;
2594 
2595  const APInt *BiasCst, *HighBitMaskCst;
2596  if (!match(XBiasedHighBits,
2598  m_APIntAllowUndef(HighBitMaskCst))))
2599  return nullptr;
2600 
2601  if (!LowBitMaskCst->isMask())
2602  return nullptr;
2603 
2604  APInt InvertedLowBitMaskCst = ~*LowBitMaskCst;
2605  if (InvertedLowBitMaskCst != *HighBitMaskCst)
2606  return nullptr;
2607 
2608  APInt AlignmentCst = *LowBitMaskCst + 1;
2609 
2610  if (*BiasCst != AlignmentCst && *BiasCst != *LowBitMaskCst)
2611  return nullptr;
2612 
2613  if (!XBiasedHighBits->hasOneUse()) {
2614  if (*BiasCst == *LowBitMaskCst)
2615  return XBiasedHighBits;
2616  return nullptr;
2617  }
2618 
2619  // FIXME: could we preserve undef's here?
2620  Type *Ty = X->getType();
2621  Value *XOffset = Builder.CreateAdd(X, ConstantInt::get(Ty, *LowBitMaskCst),
2622  X->getName() + ".biased");
2623  Value *R = Builder.CreateAnd(XOffset, ConstantInt::get(Ty, *HighBitMaskCst));
2624  R->takeName(&SI);
2625  return R;
2626 }
2627 
2629  Value *CondVal = SI.getCondition();
2630  Value *TrueVal = SI.getTrueValue();
2631  Value *FalseVal = SI.getFalseValue();
2632  Type *SelType = SI.getType();
2633 
2634  if (Value *V = simplifySelectInst(CondVal, TrueVal, FalseVal,
2635  SQ.getWithInstruction(&SI)))
2636  return replaceInstUsesWith(SI, V);
2637 
2638  if (Instruction *I = canonicalizeSelectToShuffle(SI))
2639  return I;
2640 
2641  if (Instruction *I = canonicalizeScalarSelectOfVecs(SI, *this))
2642  return I;
2643 
2644  // Avoid potential infinite loops by checking for non-constant condition.
2645  // TODO: Can we assert instead by improving canonicalizeSelectToShuffle()?
2646  // Scalar select must have simplified?
2647  if (SelType->isIntOrIntVectorTy(1) && !isa<Constant>(CondVal) &&
2648  TrueVal->getType() == CondVal->getType()) {
2649  // Folding select to and/or i1 isn't poison safe in general. impliesPoison
2650  // checks whether folding it does not convert a well-defined value into
2651  // poison.
2652  if (match(TrueVal, m_One())) {
2653  if (impliesPoison(FalseVal, CondVal)) {
2654  // Change: A = select B, true, C --> A = or B, C
2655  return BinaryOperator::CreateOr(CondVal, FalseVal);
2656  }
2657 
2658  if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
2659  if (auto *RHS = dyn_cast<FCmpInst>(FalseVal))
2660  if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ false,
2661  /*IsSelectLogical*/ true))
2662  return replaceInstUsesWith(SI, V);
2663  }
2664  if (match(FalseVal, m_Zero())) {
2665  if (impliesPoison(TrueVal, CondVal)) {
2666  // Change: A = select B, C, false --> A = and B, C
2667  return BinaryOperator::CreateAnd(CondVal, TrueVal);
2668  }
2669 
2670  if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
2671  if (auto *RHS = dyn_cast<FCmpInst>(TrueVal))
2672  if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ true,
2673  /*IsSelectLogical*/ true))
2674  return replaceInstUsesWith(SI, V);
2675  }
2676 
2677  auto *One = ConstantInt::getTrue(SelType);
2678  auto *Zero = ConstantInt::getFalse(SelType);
2679 
2680  // We match the "full" 0 or 1 constant here to avoid a potential infinite
2681  // loop with vectors that may have undefined/poison elements.
2682  // select a, false, b -> select !a, b, false
2683  if (match(TrueVal, m_Specific(Zero))) {
2684  Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2685  return SelectInst::Create(NotCond, FalseVal, Zero);
2686  }
2687  // select a, b, true -> select !a, true, b
2688  if (match(FalseVal, m_Specific(One))) {
2689  Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2690  return SelectInst::Create(NotCond, One, TrueVal);
2691  }
2692 
2693  // select a, a, b -> select a, true, b
2694  if (CondVal == TrueVal)
2695  return replaceOperand(SI, 1, One);
2696  // select a, b, a -> select a, b, false
2697  if (CondVal == FalseVal)
2698  return replaceOperand(SI, 2, Zero);
2699 
2700  // select a, !a, b -> select !a, b, false
2701  if (match(TrueVal, m_Not(m_Specific(CondVal))))
2702  return SelectInst::Create(TrueVal, FalseVal, Zero);
2703  // select a, b, !a -> select !a, true, b
2704  if (match(FalseVal, m_Not(m_Specific(CondVal))))
2705  return SelectInst::Create(FalseVal, One, TrueVal);
2706 
2707  Value *A, *B;
2708 
2709  // DeMorgan in select form: !a && !b --> !(a || b)
2710  // select !a, !b, false --> not (select a, true, b)
2711  if (match(&SI, m_LogicalAnd(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
2712  (CondVal->hasOneUse() || TrueVal->hasOneUse()) &&
2713  !match(A, m_ConstantExpr()) && !match(B, m_ConstantExpr()))
2714  return BinaryOperator::CreateNot(Builder.CreateSelect(A, One, B));
2715 
2716  // DeMorgan in select form: !a || !b --> !(a && b)
2717  // select !a, true, !b --> not (select a, b, false)
2718  if (match(&SI, m_LogicalOr(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
2719  (CondVal->hasOneUse() || FalseVal->hasOneUse()) &&
2720  !match(A, m_ConstantExpr()) && !match(B, m_ConstantExpr()))
2721  return BinaryOperator::CreateNot(Builder.CreateSelect(A, B, Zero));
2722 
2723  // select (select a, true, b), true, b -> select a, true, b
2724  if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
2726  return replaceOperand(SI, 0, A);
2727  // select (select a, b, false), b, false -> select a, b, false
2728  if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
2730  return replaceOperand(SI, 0, A);
2731 
2732  Value *C;
2733  // select (~a | c), a, b -> and a, (or c, freeze(b))
2734  if (match(CondVal, m_c_Or(m_Not(m_Specific(TrueVal)), m_Value(C))) &&
2735  CondVal->hasOneUse()) {
2736  FalseVal = Builder.CreateFreeze(FalseVal);
2737  return BinaryOperator::CreateAnd(TrueVal, Builder.CreateOr(C, FalseVal));
2738  }
2739  // select (~c & b), a, b -> and b, (or freeze(a), c)
2740  if (match(CondVal, m_c_And(m_Not(m_Value(C)), m_Specific(FalseVal))) &&
2741  CondVal->hasOneUse()) {
2742  TrueVal = Builder.CreateFreeze(TrueVal);
2743  return BinaryOperator::CreateAnd(FalseVal, Builder.CreateOr(C, TrueVal));
2744  }
2745 
2746  if (!SelType->isVectorTy()) {
2747  if (Value *S = simplifyWithOpReplaced(TrueVal, CondVal, One, SQ,
2748  /* AllowRefinement */ true))
2749  return replaceOperand(SI, 1, S);
2750  if (Value *S = simplifyWithOpReplaced(FalseVal, CondVal, Zero, SQ,
2751  /* AllowRefinement */ true))
2752  return replaceOperand(SI, 2, S);
2753  }
2754 
2755  if (match(FalseVal, m_Zero()) || match(TrueVal, m_One())) {
2756  Use *Y = nullptr;
2757  bool IsAnd = match(FalseVal, m_Zero()) ? true : false;
2758  Value *Op1 = IsAnd ? TrueVal : FalseVal;
2759  if (isCheckForZeroAndMulWithOverflow(CondVal, Op1, IsAnd, Y)) {
2760  auto *FI = new FreezeInst(*Y, (*Y)->getName() + ".fr");
2761  InsertNewInstBefore(FI, *cast<Instruction>(Y->getUser()));
2762  replaceUse(*Y, FI);
2763  return replaceInstUsesWith(SI, Op1);
2764  }
2765 
2766  if (auto *Op1SI = dyn_cast<SelectInst>(Op1))
2767  if (auto *I = foldAndOrOfSelectUsingImpliedCond(CondVal, *Op1SI,
2768  /* IsAnd */ IsAnd))
2769  return I;
2770 
2771  if (auto *ICmp0 = dyn_cast<ICmpInst>(CondVal))
2772  if (auto *ICmp1 = dyn_cast<ICmpInst>(Op1))
2773  if (auto *V = foldAndOrOfICmps(ICmp0, ICmp1, SI, IsAnd,
2774  /* IsLogical */ true))
2775  return replaceInstUsesWith(SI, V);
2776  }
2777 
2778  // select (select a, true, b), c, false -> select a, c, false
2779  // select c, (select a, true, b), false -> select c, a, false
2780  // if c implies that b is false.
2781  if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
2782  match(FalseVal, m_Zero())) {
2784  if (Res && *Res == false)
2785  return replaceOperand(SI, 0, A);
2786  }
2787  if (match(TrueVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
2788  match(FalseVal, m_Zero())) {
2789  Optional<bool> Res = isImpliedCondition(CondVal, B, DL);
2790  if (Res && *Res == false)
2791  return replaceOperand(SI, 1, A);
2792  }
2793  // select c, true, (select a, b, false) -> select c, true, a
2794  // select (select a, b, false), true, c -> select a, true, c
2795  // if c = false implies that b = true
2796  if (match(TrueVal, m_One()) &&
2797  match(FalseVal, m_Select(m_Value(A), m_Value(B), m_Zero()))) {
2798  Optional<bool> Res = isImpliedCondition(CondVal, B, DL, false);
2799  if (Res && *Res == true)
2800  return replaceOperand(SI, 2, A);
2801  }
2802  if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
2803  match(TrueVal, m_One())) {
2804  Optional<bool> Res = isImpliedCondition(FalseVal, B, DL, false);
2805  if (Res && *Res == true)
2806  return replaceOperand(SI, 0, A);
2807  }
2808 
2809  // sel (sel c, a, false), true, (sel !c, b, false) -> sel c, a, b
2810  // sel (sel !c, a, false), true, (sel c, b, false) -> sel c, b, a
2811  Value *C1, *C2;
2812  if (match(CondVal, m_Select(m_Value(C1), m_Value(A), m_Zero())) &&
2813  match(TrueVal, m_One()) &&
2814  match(FalseVal, m_Select(m_Value(C2), m_Value(B), m_Zero()))) {
2815  if (match(C2, m_Not(m_Specific(C1)))) // first case
2816  return SelectInst::Create(C1, A, B);
2817  else if (match(C1, m_Not(m_Specific(C2)))) // second case
2818  return SelectInst::Create(C2, B, A);
2819  }
2820  }
2821 
2822  // Selecting between two integer or vector splat integer constants?
2823  //
2824  // Note that we don't handle a scalar select of vectors:
2825  // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>
2826  // because that may need 3 instructions to splat the condition value:
2827  // extend, insertelement, shufflevector.
2828  //
2829  // Do not handle i1 TrueVal and FalseVal otherwise would result in
2830  // zext/sext i1 to i1.
2831  if (SelType->isIntOrIntVectorTy() && !SelType->isIntOrIntVectorTy(1) &&
2832  CondVal->getType()->isVectorTy() == SelType->isVectorTy()) {
2833  // select C, 1, 0 -> zext C to int
2834  if (match(TrueVal, m_One()) && match(FalseVal, m_Zero()))
2835  return new ZExtInst(CondVal, SelType);
2836 
2837  // select C, -1, 0 -> sext C to int
2838  if (match(TrueVal, m_AllOnes()) && match(FalseVal, m_Zero()))
2839  return new SExtInst(CondVal, SelType);
2840 
2841  // select C, 0, 1 -> zext !C to int
2842  if (match(TrueVal, m_Zero()) && match(FalseVal, m_One())) {
2843  Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2844  return new ZExtInst(NotCond, SelType);
2845  }
2846 
2847  // select C, 0, -1 -> sext !C to int
2848  if (match(TrueVal, m_Zero()) && match(FalseVal, m_AllOnes())) {
2849  Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2850  return new SExtInst(NotCond, SelType);
2851  }
2852  }
2853 
2854  if (auto *FCmp = dyn_cast<FCmpInst>(CondVal)) {
2855  Value *Cmp0 = FCmp->getOperand(0), *Cmp1 = FCmp->getOperand(1);
2856  // Are we selecting a value based on a comparison of the two values?
2857  if ((Cmp0 == TrueVal && Cmp1 == FalseVal) ||
2858  (Cmp0 == FalseVal && Cmp1 == TrueVal)) {
2859  // Canonicalize to use ordered comparisons by swapping the select
2860  // operands.
2861  //
2862  // e.g.
2863  // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X
2864  if (FCmp->hasOneUse() && FCmpInst::isUnordered(FCmp->getPredicate())) {
2865  FCmpInst::Predicate InvPred = FCmp->getInversePredicate();
2867  // FIXME: The FMF should propagate from the select, not the fcmp.
2868  Builder.setFastMathFlags(FCmp->getFastMathFlags());
2869  Value *NewCond = Builder.CreateFCmp(InvPred, Cmp0, Cmp1,
2870  FCmp->getName() + ".inv");
2871  Value *NewSel = Builder.CreateSelect(NewCond, FalseVal, TrueVal);
2872  return replaceInstUsesWith(SI, NewSel);
2873  }
2874 
2875  // NOTE: if we wanted to, this is where to detect MIN/MAX
2876  }
2877  }
2878 
2879  // Fold selecting to fabs.
2880  if (Instruction *Fabs = foldSelectWithFCmpToFabs(SI, *this))
2881  return Fabs;
2882 
2883  // See if we are selecting two values based on a comparison of the two values.
2884  if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal))
2885  if (Instruction *Result = foldSelectInstWithICmp(SI, ICI))
2886  return Result;
2887 
2888  if (Instruction *Add = foldAddSubSelect(SI, Builder))
2889  return Add;
2890  if (Instruction *Add = foldOverflowingAddSubSelect(SI, Builder))
2891  return Add;
2892  if (Instruction *Or = foldSetClearBits(SI, Builder))
2893  return Or;
2894  if (Instruction *Mul = foldSelectZeroOrMul(SI, *this))
2895  return Mul;
2896 
2897  // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
2898  auto *TI = dyn_cast<Instruction>(TrueVal);
2899  auto *FI = dyn_cast<Instruction>(FalseVal);
2900  if (TI && FI && TI->getOpcode() == FI->getOpcode())
2901  if (Instruction *IV = foldSelectOpOp(SI, TI, FI))
2902  return IV;
2903 
2904  if (Instruction *I = foldSelectExtConst(SI))
2905  return I;
2906 
2907  // Fold (select C, (gep Ptr, Idx), Ptr) -> (gep Ptr, (select C, Idx, 0))
2908  // Fold (select C, Ptr, (gep Ptr, Idx)) -> (gep Ptr, (select C, 0, Idx))
2909  auto SelectGepWithBase = [&](GetElementPtrInst *Gep, Value *Base,
2910  bool Swap) -> GetElementPtrInst * {
2911  Value *Ptr = Gep->getPointerOperand();
2912  if (Gep->getNumOperands() != 2 || Gep->getPointerOperand() != Base ||
2913  !Gep->hasOneUse())
2914  return nullptr;
2915  Value *Idx = Gep->getOperand(1);
2916  if (isa<VectorType>(CondVal->getType()) && !isa<VectorType>(Idx->getType()))
2917  return nullptr;
2918  Type *ElementType = Gep->getResultElementType();
2919  Value *NewT = Idx;
2920  Value *NewF = Constant::getNullValue(Idx->getType());
2921  if (Swap)
2922  std::swap(NewT, NewF);
2923  Value *NewSI =
2924  Builder.CreateSelect(CondVal, NewT, NewF, SI.getName() + ".idx", &SI);
2925  return GetElementPtrInst::Create(ElementType, Ptr, {NewSI});
2926  };
2927  if (auto *TrueGep = dyn_cast<GetElementPtrInst>(TrueVal))
2928  if (auto *NewGep = SelectGepWithBase(TrueGep, FalseVal, false))
2929  return NewGep;
2930  if (auto *FalseGep = dyn_cast<GetElementPtrInst>(FalseVal))
2931  if (auto *NewGep = SelectGepWithBase(FalseGep, TrueVal, true))
2932  return NewGep;
2933 
2934  // See if we can fold the select into one of our operands.
2935  if (SelType->isIntOrIntVectorTy() || SelType->isFPOrFPVectorTy()) {
2936  if (Instruction *FoldI = foldSelectIntoOp(SI, TrueVal, FalseVal))
2937  return FoldI;
2938 
2939  Value *LHS, *RHS;
2940  Instruction::CastOps CastOp;
2941  SelectPatternResult SPR = matchSelectPattern(&SI, LHS, RHS, &CastOp);
2942  auto SPF = SPR.Flavor;
2943  if (SPF) {
2944  Value *LHS2, *RHS2;
2945  if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor)
2946  if (Instruction *R = foldSPFofSPF(cast<Instruction>(LHS), SPF2, LHS2,
2947  RHS2, SI, SPF, RHS))
2948  return R;
2949  if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor)
2950  if (Instruction *R = foldSPFofSPF(cast<Instruction>(RHS), SPF2, LHS2,
2951  RHS2, SI, SPF, LHS))
2952  return R;
2953  }
2954 
2956  // Canonicalize so that
2957  // - type casts are outside select patterns.
2958  // - float clamp is transformed to min/max pattern
2959 
2960  bool IsCastNeeded = LHS->getType() != SelType;
2961  Value *CmpLHS = cast<CmpInst>(CondVal)->getOperand(0);
2962  Value *CmpRHS = cast<CmpInst>(CondVal)->getOperand(1);
2963  if (IsCastNeeded ||
2964  (LHS->getType()->isFPOrFPVectorTy() &&
2965  ((CmpLHS != LHS && CmpLHS != RHS) ||
2966  (CmpRHS != LHS && CmpRHS != RHS)))) {
2967  CmpInst::Predicate MinMaxPred = getMinMaxPred(SPF, SPR.Ordered);
2968 
2969  Value *Cmp;
2970  if (CmpInst::isIntPredicate(MinMaxPred)) {
2971  Cmp = Builder.CreateICmp(MinMaxPred, LHS, RHS);
2972  } else {
2974  auto FMF =
2975  cast<FPMathOperator>(SI.getCondition())->getFastMathFlags();
2976  Builder.setFastMathFlags(FMF);
2977  Cmp = Builder.CreateFCmp(MinMaxPred, LHS, RHS);
2978  }
2979 
2980  Value *NewSI = Builder.CreateSelect(Cmp, LHS, RHS, SI.getName(), &SI);
2981  if (!IsCastNeeded)
2982  return replaceInstUsesWith(SI, NewSI);
2983 
2984  Value *NewCast = Builder.CreateCast(CastOp, NewSI, SelType);
2985  return replaceInstUsesWith(SI, NewCast);
2986  }
2987  }
2988  }
2989 
2990  // Canonicalize select of FP values where NaN and -0.0 are not valid as
2991  // minnum/maxnum intrinsics.
2992  if (isa<FPMathOperator>(SI) && SI.hasNoNaNs() && SI.hasNoSignedZeros()) {
2993  Value *X, *Y;
2994  if (match(&SI, m_OrdFMax(m_Value(X), m_Value(Y))))
2995  return replaceInstUsesWith(
2996  SI, Builder.CreateBinaryIntrinsic(Intrinsic::maxnum, X, Y, &SI));
2997 
2998  if (match(&SI, m_OrdFMin(m_Value(X), m_Value(Y))))
2999  return replaceInstUsesWith(
3000  SI, Builder.CreateBinaryIntrinsic(Intrinsic::minnum, X, Y, &SI));
3001  }
3002 
3003  // See if we can fold the select into a phi node if the condition is a select.
3004  if (auto *PN = dyn_cast<PHINode>(SI.getCondition()))
3005  // The true/false values have to be live in the PHI predecessor's blocks.
3006  if (canSelectOperandBeMappingIntoPredBlock(TrueVal, SI) &&
3007  canSelectOperandBeMappingIntoPredBlock(FalseVal, SI))
3008  if (Instruction *NV = foldOpIntoPhi(SI, PN))
3009  return NV;
3010 
3011  if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) {
3012  if (TrueSI->getCondition()->getType() == CondVal->getType()) {
3013  // select(C, select(C, a, b), c) -> select(C, a, c)
3014  if (TrueSI->getCondition() == CondVal) {
3015  if (SI.getTrueValue() == TrueSI->getTrueValue())
3016  return nullptr;
3017  return replaceOperand(SI, 1, TrueSI->getTrueValue());
3018  }
3019  // select(C0, select(C1, a, b), b) -> select(C0&C1, a, b)
3020  // We choose this as normal form to enable folding on the And and
3021  // shortening paths for the values (this helps getUnderlyingObjects() for
3022  // example).
3023  if (TrueSI->getFalseValue() == FalseVal && TrueSI->hasOneUse()) {
3024  Value *And = Builder.CreateLogicalAnd(CondVal, TrueSI->getCondition());
3025  replaceOperand(SI, 0, And);
3026  replaceOperand(SI, 1, TrueSI->getTrueValue());
3027  return &SI;
3028  }
3029  }
3030  }
3031  if (SelectInst *FalseSI = dyn_cast<SelectInst>(FalseVal)) {
3032  if (FalseSI->getCondition()->getType() == CondVal->getType()) {
3033  // select(C, a, select(C, b, c)) -> select(C, a, c)
3034  if (FalseSI->getCondition() == CondVal) {
3035  if (SI.getFalseValue() == FalseSI->getFalseValue())
3036  return nullptr;
3037  return replaceOperand(SI, 2, FalseSI->getFalseValue());
3038  }
3039  // select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b)
3040  if (FalseSI->getTrueValue() == TrueVal && FalseSI->hasOneUse()) {
3041  Value *Or = Builder.CreateLogicalOr(CondVal, FalseSI->getCondition());
3042  replaceOperand(SI, 0, Or);
3043  replaceOperand(SI, 2, FalseSI->getFalseValue());
3044  return &SI;
3045  }
3046  }
3047  }
3048 
3049  auto canMergeSelectThroughBinop = [](BinaryOperator *BO) {
3050  // The select might be preventing a division by 0.
3051  switch (BO->getOpcode()) {
3052  default:
3053  return true;
3054  case Instruction::SRem:
3055  case Instruction::URem:
3056  case Instruction::SDiv:
3057  case Instruction::UDiv:
3058  return false;
3059  }
3060  };
3061 
3062  // Try to simplify a binop sandwiched between 2 selects with the same
3063  // condition.
3064  // select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z)
3065  BinaryOperator *TrueBO;
3066  if (match(TrueVal, m_OneUse(m_BinOp(TrueBO))) &&
3067  canMergeSelectThroughBinop(TrueBO)) {
3068  if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(0))) {
3069  if (TrueBOSI->getCondition() == CondVal) {
3070  replaceOperand(*TrueBO, 0, TrueBOSI->getTrueValue());
3071  Worklist.push(TrueBO);
3072  return &SI;
3073  }
3074  }
3075  if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(1))) {
3076  if (TrueBOSI->getCondition() == CondVal) {
3077  replaceOperand(*TrueBO, 1, TrueBOSI->getTrueValue());
3078  Worklist.push(TrueBO);
3079  return &SI;
3080  }
3081  }
3082  }
3083 
3084  // select(C, Z, binop(select(C, X, Y), W)) -> select(C, Z, binop(Y, W))
3085  BinaryOperator *FalseBO;
3086  if (match(FalseVal, m_OneUse(m_BinOp(FalseBO))) &&
3087  canMergeSelectThroughBinop(FalseBO)) {
3088  if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(0))) {
3089  if (FalseBOSI->getCondition() == CondVal) {
3090  replaceOperand(*FalseBO, 0, FalseBOSI->getFalseValue());
3091  Worklist.push(FalseBO);
3092  return &SI;
3093  }
3094  }
3095  if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(1))) {
3096  if (FalseBOSI->getCondition() == CondVal) {
3097  replaceOperand(*FalseBO, 1, FalseBOSI->getFalseValue());
3098  Worklist.push(FalseBO);
3099  return &SI;
3100  }
3101  }
3102  }
3103 
3104  Value *NotCond;
3105  if (match(CondVal, m_Not(m_Value(NotCond))) &&
3107  replaceOperand(SI, 0, NotCond);
3108  SI.swapValues();
3109  SI.swapProfMetadata();
3110  return &SI;
3111  }
3112 
3113  if (Instruction *I = foldVectorSelect(SI))
3114  return I;
3115 
3116  // If we can compute the condition, there's no need for a select.
3117  // Like the above fold, we are attempting to reduce compile-time cost by
3118  // putting this fold here with limitations rather than in InstSimplify.
3119  // The motivation for this call into value tracking is to take advantage of
3120  // the assumption cache, so make sure that is populated.
3121  if (!CondVal->getType()->isVectorTy() && !AC.assumptions().empty()) {
3122  KnownBits Known(1);
3123  computeKnownBits(CondVal, Known, 0, &SI);
3124  if (Known.One.isOne())
3125  return replaceInstUsesWith(SI, TrueVal);
3126  if (Known.Zero.isOne())
3127  return replaceInstUsesWith(SI, FalseVal);
3128  }
3129 
3130  if (Instruction *BitCastSel = foldSelectCmpBitcasts(SI, Builder))
3131  return BitCastSel;
3132 
3133  // Simplify selects that test the returned flag of cmpxchg instructions.
3134  if (Value *V = foldSelectCmpXchg(SI))
3135  return replaceInstUsesWith(SI, V);
3136 
3137  if (Instruction *Select = foldSelectBinOpIdentity(SI, TLI, *this))
3138  return Select;
3139 
3140  if (Instruction *Funnel = foldSelectFunnelShift(SI, Builder))
3141  return Funnel;
3142 
3143  if (Instruction *Copysign = foldSelectToCopysign(SI, Builder))
3144  return Copysign;
3145 
3146  if (Instruction *PN = foldSelectToPhi(SI, DT, Builder))
3147  return replaceInstUsesWith(SI, PN);
3148 
3149  if (Value *Fr = foldSelectWithFrozenICmp(SI, Builder))
3150  return replaceInstUsesWith(SI, Fr);
3151 
3152  if (Value *V = foldRoundUpIntegerWithPow2Alignment(SI, Builder))
3153  return replaceInstUsesWith(SI, V);
3154 
3155  // select(mask, mload(,,mask,0), 0) -> mload(,,mask,0)
3156  // Load inst is intentionally not checked for hasOneUse()
3157  if (match(FalseVal, m_Zero()) &&
3159  m_CombineOr(m_Undef(), m_Zero()))) ||
3161  m_CombineOr(m_Undef(), m_Zero()))))) {
3162  auto *MaskedInst = cast<IntrinsicInst>(TrueVal);
3163  if (isa<UndefValue>(MaskedInst->getArgOperand(3)))
3164  MaskedInst->setArgOperand(3, FalseVal /* Zero */);
3165  return replaceInstUsesWith(SI, MaskedInst);
3166  }
3167 
3168  Value *Mask;
3169  if (match(TrueVal, m_Zero()) &&
3171  m_CombineOr(m_Undef(), m_Zero()))) ||
3173  m_CombineOr(m_Undef(), m_Zero())))) &&
3174  (CondVal->getType() == Mask->getType())) {
3175  // We can remove the select by ensuring the load zeros all lanes the
3176  // select would have. We determine this by proving there is no overlap
3177  // between the load and select masks.
3178  // (i.e (load_mask & select_mask) == 0 == no overlap)
3179  bool CanMergeSelectIntoLoad = false;
3180  if (Value *V = simplifyAndInst(CondVal, Mask, SQ.getWithInstruction(&SI)))
3181  CanMergeSelectIntoLoad = match(V, m_Zero());
3182 
3183  if (CanMergeSelectIntoLoad) {
3184  auto *MaskedInst = cast<IntrinsicInst>(FalseVal);
3185  if (isa<UndefValue>(MaskedInst->getArgOperand(3)))
3186  MaskedInst->setArgOperand(3, TrueVal /* Zero */);
3187  return replaceInstUsesWith(SI, MaskedInst);
3188  }
3189  }
3190 
3191  return nullptr;
3192 }
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:702
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:2106
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:17
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:1611
Optional.h
llvm::RecurKind::Or
@ Or
Bitwise or logical OR of integers.
llvm::PatternMatch::m_Mask
Definition: PatternMatch.h:1508
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:1418
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
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4688
IntrinsicInst.h
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2156
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:165
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:6807
llvm::BinaryOperator::CreateNot
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: Instructions.cpp:2834
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:722
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1111
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:5681
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:5404
llvm::Type::getScalarType
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:309
llvm::BinaryOpIntrinsic::getRHS
Value * getRHS() const
Definition: IntrinsicInst.h:664
llvm::ConstantExpr::getSExt
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2142
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
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:384
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:2535
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:973
llvm::BinaryOpIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:663
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:212
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:3182
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:822
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:869
llvm::Type::isFPOrFPVectorTy
bool isFPOrFPVectorTy() const
Return true if this is a FP type or a vector of FP.
Definition: Type.h:179
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:1725
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:1886
llvm::APInt::getSignedMaxValue
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1411
llvm::ICmpInst::isEquality
bool isEquality() const
Return true if this predicate is either EQ or NE.
Definition: Instructions.h:1268
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:703
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:405
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:877
llvm::Optional< bool >
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::PatternMatch::m_BinOp
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:84
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::PatternMatch::m_AShr
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1117
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:62
llvm::SelectInst::getFalseValue
const Value * getFalseValue() const
Definition: Instructions.h:1773
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:491
llvm::matchSelectPattern
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
Definition: ValueTracking.cpp:6350
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:2245
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:2794
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:2283
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:698
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:1587
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:784
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:240
KnownBits.h
llvm::PatternMatch::m_FSub
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:991
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:1983
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:2217
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:2734
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:272
llvm::SPF_NABS
@ SPF_NABS
Absolute value.
Definition: ValueTracking.h:707
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:2209
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:2845
llvm::PatternMatch::m_UMax
MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty > m_UMax(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1859
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:1906
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:542
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:157
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1755
llvm::SelectInst::getCondition
const Value * getCondition() const
Definition: Instructions.h:1771
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:1456
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:730
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:667
InstructionWorklist.h
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1504
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:227
llvm::PatternMatch::m_Instruction
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:710
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:1623
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:2231
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:1876
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:800
llvm::PatternMatch::m_FNeg
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
Definition: PatternMatch.h:1027
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:1865
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:2252
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:928
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:5266
llvm::PatternMatch::m_APIntAllowUndef
apint_match m_APIntAllowUndef(const APInt *&Res)
Match APInt while allowing undefs in splat vector constants.
Definition: PatternMatch.h:278
llvm::SPF_SMIN
@ SPF_SMIN
Definition: ValueTracking.h:700
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:511
llvm::Instruction::isCommutative
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
Definition: Instruction.cpp:770
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:1486
llvm::PatternMatch::m_Power2
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:538
llvm::PatternMatch::m_Xor
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1099
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:721
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:322
llvm::PatternMatch::m_ZExtOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, OpTy > m_ZExtOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1629
llvm::ConstantExpr::getTrunc
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2128
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:767
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:531
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:2182
llvm::PatternMatch::m_ImmConstant
match_combine_and< class_match< Constant >, match_unless< class_match< ConstantExpr > > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:745
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1173
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:4534
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:2549
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:1093
llvm::PatternMatch::m_AllOnes
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:447
llvm::DenseMap
Definition: DenseMap.h:716
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:916
llvm::SelectInst::getTrueValue
const Value * getTrueValue() const
Definition: Instructions.h:1772
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:2098
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1087
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:1682
llvm::GetElementPtrInst::getResultElementType
Type * getResultElementType() const
Definition: Instructions.h:996
llvm::ICmpInst::isEquality
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Definition: Instructions.h:1262
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:682
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:969
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:985
llvm::SPF_ABS
@ SPF_ABS
Floating point maxnum.
Definition: ValueTracking.h:706
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:2010
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:743
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1724
llvm::PatternMatch::m_WithOverflowInst
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
Definition: PatternMatch.h:716
llvm::PatternMatch::m_SMin
MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1853
llvm::SelectInst::swapValues
void swapValues()
Swap the true and false values of the select instruction.
Definition: Instructions.h:1784
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:2246
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:4806
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:942
llvm::PatternMatch::m_SExt
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:1617
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:590
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:848
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:218
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:289
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:592
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:1545
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
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:677
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4845
LLVM_FALLTHROUGH
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:280
llvm::PatternMatch::m_SMax
MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1847
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
foldSelectZeroOrMul
static Instruction * foldSelectZeroOrMul(SelectInst &SI, InstCombinerImpl &IC)
Definition: InstCombineSelect.cpp:722
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:1891
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:883
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:239
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:4223
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:876
Insn
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
Definition: AArch64MIPeepholeOpt.cpp:127
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:2704
llvm::SelectPatternResult::Ordered
bool Ordered
Only applicable if Flavor is SPF_FMINNUM or SPF_FMAXNUM.
Definition: ValueTracking.h:725
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:3337
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
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:197
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:975
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:101
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
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:2238
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:518
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:295
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:436
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:1305
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:658
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:820
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:426
llvm::PatternMatch::m_ConstantExpr
class_match< ConstantExpr > m_ConstantExpr()
Match an arbitrary ConstantExpr and ignore it.
Definition: PatternMatch.h:157
llvm::ShuffleVectorInst
This instruction constructs a fixed permutation of two input vectors.
Definition: Instructions.h:1995
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:3498
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:438
SmallVector.h
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:766
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:1388
llvm::Value::DoPHITranslation
const Value * DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) const
Translate PHI node to its predecessor from the given basic block.
Definition: Value.cpp:983
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h: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:5394
llvm::SPF_UMIN
@ SPF_UMIN
Signed minimum.
Definition: ValueTracking.h:701
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:6408
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:2276
llvm::Instruction::swapProfMetadata
void swapProfMetadata()
If the instruction has "branch_weights" MD_prof metadata and the MDNode has three operands (including...
Definition: Instruction.cpp:824
llvm::PHINode
Definition: Instructions.h:2651
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:298
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:1394
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:269
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:1143
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:4255
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:2267
llvm::isGuaranteedNotToBePoison
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Definition: ValueTracking.cpp:5411
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:231
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:378
llvm::PatternMatch::m_BasicBlock
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
Definition: PatternMatch.h:162
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:1605
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:534
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:2778
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:1039
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:509
llvm::Instruction::dropPoisonGeneratingFlags
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
Definition: Instruction.cpp:147
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:2531
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