LLVM  9.0.0svn
ValueTracking.cpp
Go to the documentation of this file.
1 //===- ValueTracking.cpp - Walk computations to compute properties --------===//
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 contains routines that help analyze properties that chains of
10 // computations have.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/APFloat.h"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/None.h"
19 #include "llvm/ADT/Optional.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/StringRef.h"
30 #include "llvm/Analysis/Loads.h"
31 #include "llvm/Analysis/LoopInfo.h"
34 #include "llvm/IR/Argument.h"
35 #include "llvm/IR/Attributes.h"
36 #include "llvm/IR/BasicBlock.h"
37 #include "llvm/IR/CallSite.h"
38 #include "llvm/IR/Constant.h"
39 #include "llvm/IR/ConstantRange.h"
40 #include "llvm/IR/Constants.h"
41 #include "llvm/IR/DataLayout.h"
42 #include "llvm/IR/DerivedTypes.h"
43 #include "llvm/IR/DiagnosticInfo.h"
44 #include "llvm/IR/Dominators.h"
45 #include "llvm/IR/Function.h"
47 #include "llvm/IR/GlobalAlias.h"
48 #include "llvm/IR/GlobalValue.h"
49 #include "llvm/IR/GlobalVariable.h"
50 #include "llvm/IR/InstrTypes.h"
51 #include "llvm/IR/Instruction.h"
52 #include "llvm/IR/Instructions.h"
53 #include "llvm/IR/IntrinsicInst.h"
54 #include "llvm/IR/Intrinsics.h"
55 #include "llvm/IR/LLVMContext.h"
56 #include "llvm/IR/Metadata.h"
57 #include "llvm/IR/Module.h"
58 #include "llvm/IR/Operator.h"
59 #include "llvm/IR/PatternMatch.h"
60 #include "llvm/IR/Type.h"
61 #include "llvm/IR/User.h"
62 #include "llvm/IR/Value.h"
63 #include "llvm/Support/Casting.h"
65 #include "llvm/Support/Compiler.h"
67 #include "llvm/Support/KnownBits.h"
69 #include <algorithm>
70 #include <array>
71 #include <cassert>
72 #include <cstdint>
73 #include <iterator>
74 #include <utility>
75 
76 using namespace llvm;
77 using namespace llvm::PatternMatch;
78 
79 const unsigned MaxDepth = 6;
80 
81 // Controls the number of uses of the value searched for possible
82 // dominating comparisons.
83 static cl::opt<unsigned> DomConditionsMaxUses("dom-conditions-max-uses",
84  cl::Hidden, cl::init(20));
85 
86 /// Returns the bitwidth of the given scalar or pointer type. For vector types,
87 /// returns the element type's bitwidth.
88 static unsigned getBitWidth(Type *Ty, const DataLayout &DL) {
89  if (unsigned BitWidth = Ty->getScalarSizeInBits())
90  return BitWidth;
91 
92  return DL.getIndexTypeSizeInBits(Ty);
93 }
94 
95 namespace {
96 
97 // Simplifying using an assume can only be done in a particular control-flow
98 // context (the context instruction provides that context). If an assume and
99 // the context instruction are not in the same block then the DT helps in
100 // figuring out if we can use it.
101 struct Query {
102  const DataLayout &DL;
103  AssumptionCache *AC;
104  const Instruction *CxtI;
105  const DominatorTree *DT;
106 
107  // Unlike the other analyses, this may be a nullptr because not all clients
108  // provide it currently.
110 
111  /// Set of assumptions that should be excluded from further queries.
112  /// This is because of the potential for mutual recursion to cause
113  /// computeKnownBits to repeatedly visit the same assume intrinsic. The
114  /// classic case of this is assume(x = y), which will attempt to determine
115  /// bits in x from bits in y, which will attempt to determine bits in y from
116  /// bits in x, etc. Regarding the mutual recursion, computeKnownBits can call
117  /// isKnownNonZero, which calls computeKnownBits and isKnownToBeAPowerOfTwo
118  /// (all of which can call computeKnownBits), and so on.
119  std::array<const Value *, MaxDepth> Excluded;
120 
121  /// If true, it is safe to use metadata during simplification.
122  InstrInfoQuery IIQ;
123 
124  unsigned NumExcluded = 0;
125 
126  Query(const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI,
127  const DominatorTree *DT, bool UseInstrInfo,
128  OptimizationRemarkEmitter *ORE = nullptr)
129  : DL(DL), AC(AC), CxtI(CxtI), DT(DT), ORE(ORE), IIQ(UseInstrInfo) {}
130 
131  Query(const Query &Q, const Value *NewExcl)
132  : DL(Q.DL), AC(Q.AC), CxtI(Q.CxtI), DT(Q.DT), ORE(Q.ORE), IIQ(Q.IIQ),
133  NumExcluded(Q.NumExcluded) {
134  Excluded = Q.Excluded;
135  Excluded[NumExcluded++] = NewExcl;
136  assert(NumExcluded <= Excluded.size());
137  }
138 
139  bool isExcluded(const Value *Value) const {
140  if (NumExcluded == 0)
141  return false;
142  auto End = Excluded.begin() + NumExcluded;
143  return std::find(Excluded.begin(), End, Value) != End;
144  }
145 };
146 
147 } // end anonymous namespace
148 
149 // Given the provided Value and, potentially, a context instruction, return
150 // the preferred context instruction (if any).
151 static const Instruction *safeCxtI(const Value *V, const Instruction *CxtI) {
152  // If we've been provided with a context instruction, then use that (provided
153  // it has been inserted).
154  if (CxtI && CxtI->getParent())
155  return CxtI;
156 
157  // If the value is really an already-inserted instruction, then use that.
158  CxtI = dyn_cast<Instruction>(V);
159  if (CxtI && CxtI->getParent())
160  return CxtI;
161 
162  return nullptr;
163 }
164 
165 static void computeKnownBits(const Value *V, KnownBits &Known,
166  unsigned Depth, const Query &Q);
167 
168 void llvm::computeKnownBits(const Value *V, KnownBits &Known,
169  const DataLayout &DL, unsigned Depth,
170  AssumptionCache *AC, const Instruction *CxtI,
171  const DominatorTree *DT,
172  OptimizationRemarkEmitter *ORE, bool UseInstrInfo) {
173  ::computeKnownBits(V, Known, Depth,
174  Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo, ORE));
175 }
176 
177 static KnownBits computeKnownBits(const Value *V, unsigned Depth,
178  const Query &Q);
179 
181  unsigned Depth, AssumptionCache *AC,
182  const Instruction *CxtI,
183  const DominatorTree *DT,
185  bool UseInstrInfo) {
187  V, Depth, Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo, ORE));
188 }
189 
190 bool llvm::haveNoCommonBitsSet(const Value *LHS, const Value *RHS,
191  const DataLayout &DL, AssumptionCache *AC,
192  const Instruction *CxtI, const DominatorTree *DT,
193  bool UseInstrInfo) {
194  assert(LHS->getType() == RHS->getType() &&
195  "LHS and RHS should have the same type");
196  assert(LHS->getType()->isIntOrIntVectorTy() &&
197  "LHS and RHS should be integers");
198  // Look for an inverted mask: (X & ~M) op (Y & M).
199  Value *M;
200  if (match(LHS, m_c_And(m_Not(m_Value(M)), m_Value())) &&
201  match(RHS, m_c_And(m_Specific(M), m_Value())))
202  return true;
203  if (match(RHS, m_c_And(m_Not(m_Value(M)), m_Value())) &&
204  match(LHS, m_c_And(m_Specific(M), m_Value())))
205  return true;
206  IntegerType *IT = cast<IntegerType>(LHS->getType()->getScalarType());
207  KnownBits LHSKnown(IT->getBitWidth());
208  KnownBits RHSKnown(IT->getBitWidth());
209  computeKnownBits(LHS, LHSKnown, DL, 0, AC, CxtI, DT, nullptr, UseInstrInfo);
210  computeKnownBits(RHS, RHSKnown, DL, 0, AC, CxtI, DT, nullptr, UseInstrInfo);
211  return (LHSKnown.Zero | RHSKnown.Zero).isAllOnesValue();
212 }
213 
215  for (const User *U : CxtI->users()) {
216  if (const ICmpInst *IC = dyn_cast<ICmpInst>(U))
217  if (IC->isEquality())
218  if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
219  if (C->isNullValue())
220  continue;
221  return false;
222  }
223  return true;
224 }
225 
226 static bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth,
227  const Query &Q);
228 
230  bool OrZero, unsigned Depth,
231  AssumptionCache *AC, const Instruction *CxtI,
232  const DominatorTree *DT, bool UseInstrInfo) {
234  V, OrZero, Depth, Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo));
235 }
236 
237 static bool isKnownNonZero(const Value *V, unsigned Depth, const Query &Q);
238 
239 bool llvm::isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth,
240  AssumptionCache *AC, const Instruction *CxtI,
241  const DominatorTree *DT, bool UseInstrInfo) {
242  return ::isKnownNonZero(V, Depth,
243  Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo));
244 }
245 
246 bool llvm::isKnownNonNegative(const Value *V, const DataLayout &DL,
247  unsigned Depth, AssumptionCache *AC,
248  const Instruction *CxtI, const DominatorTree *DT,
249  bool UseInstrInfo) {
250  KnownBits Known =
251  computeKnownBits(V, DL, Depth, AC, CxtI, DT, nullptr, UseInstrInfo);
252  return Known.isNonNegative();
253 }
254 
255 bool llvm::isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth,
256  AssumptionCache *AC, const Instruction *CxtI,
257  const DominatorTree *DT, bool UseInstrInfo) {
258  if (auto *CI = dyn_cast<ConstantInt>(V))
259  return CI->getValue().isStrictlyPositive();
260 
261  // TODO: We'd doing two recursive queries here. We should factor this such
262  // that only a single query is needed.
263  return isKnownNonNegative(V, DL, Depth, AC, CxtI, DT, UseInstrInfo) &&
264  isKnownNonZero(V, DL, Depth, AC, CxtI, DT, UseInstrInfo);
265 }
266 
267 bool llvm::isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth,
268  AssumptionCache *AC, const Instruction *CxtI,
269  const DominatorTree *DT, bool UseInstrInfo) {
270  KnownBits Known =
271  computeKnownBits(V, DL, Depth, AC, CxtI, DT, nullptr, UseInstrInfo);
272  return Known.isNegative();
273 }
274 
275 static bool isKnownNonEqual(const Value *V1, const Value *V2, const Query &Q);
276 
277 bool llvm::isKnownNonEqual(const Value *V1, const Value *V2,
278  const DataLayout &DL, AssumptionCache *AC,
279  const Instruction *CxtI, const DominatorTree *DT,
280  bool UseInstrInfo) {
282  Query(DL, AC, safeCxtI(V1, safeCxtI(V2, CxtI)), DT,
283  UseInstrInfo, /*ORE=*/nullptr));
284 }
285 
286 static bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth,
287  const Query &Q);
288 
289 bool llvm::MaskedValueIsZero(const Value *V, const APInt &Mask,
290  const DataLayout &DL, unsigned Depth,
291  AssumptionCache *AC, const Instruction *CxtI,
292  const DominatorTree *DT, bool UseInstrInfo) {
294  V, Mask, Depth, Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo));
295 }
296 
297 static unsigned ComputeNumSignBits(const Value *V, unsigned Depth,
298  const Query &Q);
299 
300 unsigned llvm::ComputeNumSignBits(const Value *V, const DataLayout &DL,
301  unsigned Depth, AssumptionCache *AC,
302  const Instruction *CxtI,
303  const DominatorTree *DT, bool UseInstrInfo) {
305  V, Depth, Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo));
306 }
307 
308 static void computeKnownBitsAddSub(bool Add, const Value *Op0, const Value *Op1,
309  bool NSW,
310  KnownBits &KnownOut, KnownBits &Known2,
311  unsigned Depth, const Query &Q) {
312  unsigned BitWidth = KnownOut.getBitWidth();
313 
314  // If an initial sequence of bits in the result is not needed, the
315  // corresponding bits in the operands are not needed.
316  KnownBits LHSKnown(BitWidth);
317  computeKnownBits(Op0, LHSKnown, Depth + 1, Q);
318  computeKnownBits(Op1, Known2, Depth + 1, Q);
319 
320  KnownOut = KnownBits::computeForAddSub(Add, NSW, LHSKnown, Known2);
321 }
322 
323 static void computeKnownBitsMul(const Value *Op0, const Value *Op1, bool NSW,
324  KnownBits &Known, KnownBits &Known2,
325  unsigned Depth, const Query &Q) {
326  unsigned BitWidth = Known.getBitWidth();
327  computeKnownBits(Op1, Known, Depth + 1, Q);
328  computeKnownBits(Op0, Known2, Depth + 1, Q);
329 
330  bool isKnownNegative = false;
331  bool isKnownNonNegative = false;
332  // If the multiplication is known not to overflow, compute the sign bit.
333  if (NSW) {
334  if (Op0 == Op1) {
335  // The product of a number with itself is non-negative.
336  isKnownNonNegative = true;
337  } else {
338  bool isKnownNonNegativeOp1 = Known.isNonNegative();
339  bool isKnownNonNegativeOp0 = Known2.isNonNegative();
340  bool isKnownNegativeOp1 = Known.isNegative();
341  bool isKnownNegativeOp0 = Known2.isNegative();
342  // The product of two numbers with the same sign is non-negative.
343  isKnownNonNegative = (isKnownNegativeOp1 && isKnownNegativeOp0) ||
344  (isKnownNonNegativeOp1 && isKnownNonNegativeOp0);
345  // The product of a negative number and a non-negative number is either
346  // negative or zero.
347  if (!isKnownNonNegative)
348  isKnownNegative = (isKnownNegativeOp1 && isKnownNonNegativeOp0 &&
349  isKnownNonZero(Op0, Depth, Q)) ||
350  (isKnownNegativeOp0 && isKnownNonNegativeOp1 &&
351  isKnownNonZero(Op1, Depth, Q));
352  }
353  }
354 
355  assert(!Known.hasConflict() && !Known2.hasConflict());
356  // Compute a conservative estimate for high known-0 bits.
357  unsigned LeadZ = std::max(Known.countMinLeadingZeros() +
358  Known2.countMinLeadingZeros(),
359  BitWidth) - BitWidth;
360  LeadZ = std::min(LeadZ, BitWidth);
361 
362  // The result of the bottom bits of an integer multiply can be
363  // inferred by looking at the bottom bits of both operands and
364  // multiplying them together.
365  // We can infer at least the minimum number of known trailing bits
366  // of both operands. Depending on number of trailing zeros, we can
367  // infer more bits, because (a*b) <=> ((a/m) * (b/n)) * (m*n) assuming
368  // a and b are divisible by m and n respectively.
369  // We then calculate how many of those bits are inferrable and set
370  // the output. For example, the i8 mul:
371  // a = XXXX1100 (12)
372  // b = XXXX1110 (14)
373  // We know the bottom 3 bits are zero since the first can be divided by
374  // 4 and the second by 2, thus having ((12/4) * (14/2)) * (2*4).
375  // Applying the multiplication to the trimmed arguments gets:
376  // XX11 (3)
377  // X111 (7)
378  // -------
379  // XX11
380  // XX11
381  // XX11
382  // XX11
383  // -------
384  // XXXXX01
385  // Which allows us to infer the 2 LSBs. Since we're multiplying the result
386  // by 8, the bottom 3 bits will be 0, so we can infer a total of 5 bits.
387  // The proof for this can be described as:
388  // Pre: (C1 >= 0) && (C1 < (1 << C5)) && (C2 >= 0) && (C2 < (1 << C6)) &&
389  // (C7 == (1 << (umin(countTrailingZeros(C1), C5) +
390  // umin(countTrailingZeros(C2), C6) +
391  // umin(C5 - umin(countTrailingZeros(C1), C5),
392  // C6 - umin(countTrailingZeros(C2), C6)))) - 1)
393  // %aa = shl i8 %a, C5
394  // %bb = shl i8 %b, C6
395  // %aaa = or i8 %aa, C1
396  // %bbb = or i8 %bb, C2
397  // %mul = mul i8 %aaa, %bbb
398  // %mask = and i8 %mul, C7
399  // =>
400  // %mask = i8 ((C1*C2)&C7)
401  // Where C5, C6 describe the known bits of %a, %b
402  // C1, C2 describe the known bottom bits of %a, %b.
403  // C7 describes the mask of the known bits of the result.
404  APInt Bottom0 = Known.One;
405  APInt Bottom1 = Known2.One;
406 
407  // How many times we'd be able to divide each argument by 2 (shr by 1).
408  // This gives us the number of trailing zeros on the multiplication result.
409  unsigned TrailBitsKnown0 = (Known.Zero | Known.One).countTrailingOnes();
410  unsigned TrailBitsKnown1 = (Known2.Zero | Known2.One).countTrailingOnes();
411  unsigned TrailZero0 = Known.countMinTrailingZeros();
412  unsigned TrailZero1 = Known2.countMinTrailingZeros();
413  unsigned TrailZ = TrailZero0 + TrailZero1;
414 
415  // Figure out the fewest known-bits operand.
416  unsigned SmallestOperand = std::min(TrailBitsKnown0 - TrailZero0,
417  TrailBitsKnown1 - TrailZero1);
418  unsigned ResultBitsKnown = std::min(SmallestOperand + TrailZ, BitWidth);
419 
420  APInt BottomKnown = Bottom0.getLoBits(TrailBitsKnown0) *
421  Bottom1.getLoBits(TrailBitsKnown1);
422 
423  Known.resetAll();
424  Known.Zero.setHighBits(LeadZ);
425  Known.Zero |= (~BottomKnown).getLoBits(ResultBitsKnown);
426  Known.One |= BottomKnown.getLoBits(ResultBitsKnown);
427 
428  // Only make use of no-wrap flags if we failed to compute the sign bit
429  // directly. This matters if the multiplication always overflows, in
430  // which case we prefer to follow the result of the direct computation,
431  // though as the program is invoking undefined behaviour we can choose
432  // whatever we like here.
433  if (isKnownNonNegative && !Known.isNegative())
434  Known.makeNonNegative();
435  else if (isKnownNegative && !Known.isNonNegative())
436  Known.makeNegative();
437 }
438 
440  KnownBits &Known) {
441  unsigned BitWidth = Known.getBitWidth();
442  unsigned NumRanges = Ranges.getNumOperands() / 2;
443  assert(NumRanges >= 1);
444 
445  Known.Zero.setAllBits();
446  Known.One.setAllBits();
447 
448  for (unsigned i = 0; i < NumRanges; ++i) {
449  ConstantInt *Lower =
450  mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
451  ConstantInt *Upper =
452  mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
453  ConstantRange Range(Lower->getValue(), Upper->getValue());
454 
455  // The first CommonPrefixBits of all values in Range are equal.
456  unsigned CommonPrefixBits =
457  (Range.getUnsignedMax() ^ Range.getUnsignedMin()).countLeadingZeros();
458 
459  APInt Mask = APInt::getHighBitsSet(BitWidth, CommonPrefixBits);
460  Known.One &= Range.getUnsignedMax() & Mask;
461  Known.Zero &= ~Range.getUnsignedMax() & Mask;
462  }
463 }
464 
465 static bool isEphemeralValueOf(const Instruction *I, const Value *E) {
466  SmallVector<const Value *, 16> WorkSet(1, I);
469 
470  // The instruction defining an assumption's condition itself is always
471  // considered ephemeral to that assumption (even if it has other
472  // non-ephemeral users). See r246696's test case for an example.
473  if (is_contained(I->operands(), E))
474  return true;
475 
476  while (!WorkSet.empty()) {
477  const Value *V = WorkSet.pop_back_val();
478  if (!Visited.insert(V).second)
479  continue;
480 
481  // If all uses of this value are ephemeral, then so is this value.
482  if (llvm::all_of(V->users(), [&](const User *U) {
483  return EphValues.count(U);
484  })) {
485  if (V == E)
486  return true;
487 
488  if (V == I || isSafeToSpeculativelyExecute(V)) {
489  EphValues.insert(V);
490  if (const User *U = dyn_cast<User>(V))
491  for (User::const_op_iterator J = U->op_begin(), JE = U->op_end();
492  J != JE; ++J)
493  WorkSet.push_back(*J);
494  }
495  }
496  }
497 
498  return false;
499 }
500 
501 // Is this an intrinsic that cannot be speculated but also cannot trap?
503  if (const CallInst *CI = dyn_cast<CallInst>(I))
504  if (Function *F = CI->getCalledFunction())
505  switch (F->getIntrinsicID()) {
506  default: break;
507  // FIXME: This list is repeated from NoTTI::getIntrinsicCost.
508  case Intrinsic::assume:
509  case Intrinsic::sideeffect:
510  case Intrinsic::dbg_declare:
511  case Intrinsic::dbg_value:
512  case Intrinsic::dbg_label:
513  case Intrinsic::invariant_start:
514  case Intrinsic::invariant_end:
515  case Intrinsic::lifetime_start:
516  case Intrinsic::lifetime_end:
517  case Intrinsic::objectsize:
518  case Intrinsic::ptr_annotation:
519  case Intrinsic::var_annotation:
520  return true;
521  }
522 
523  return false;
524 }
525 
527  const Instruction *CxtI,
528  const DominatorTree *DT) {
529  // There are two restrictions on the use of an assume:
530  // 1. The assume must dominate the context (or the control flow must
531  // reach the assume whenever it reaches the context).
532  // 2. The context must not be in the assume's set of ephemeral values
533  // (otherwise we will use the assume to prove that the condition
534  // feeding the assume is trivially true, thus causing the removal of
535  // the assume).
536 
537  if (DT) {
538  if (DT->dominates(Inv, CxtI))
539  return true;
540  } else if (Inv->getParent() == CxtI->getParent()->getSinglePredecessor()) {
541  // We don't have a DT, but this trivially dominates.
542  return true;
543  }
544 
545  // With or without a DT, the only remaining case we will check is if the
546  // instructions are in the same BB. Give up if that is not the case.
547  if (Inv->getParent() != CxtI->getParent())
548  return false;
549 
550  // If we have a dom tree, then we now know that the assume doesn't dominate
551  // the other instruction. If we don't have a dom tree then we can check if
552  // the assume is first in the BB.
553  if (!DT) {
554  // Search forward from the assume until we reach the context (or the end
555  // of the block); the common case is that the assume will come first.
556  for (auto I = std::next(BasicBlock::const_iterator(Inv)),
557  IE = Inv->getParent()->end(); I != IE; ++I)
558  if (&*I == CxtI)
559  return true;
560  }
561 
562  // The context comes first, but they're both in the same block. Make sure
563  // there is nothing in between that might interrupt the control flow.
565  std::next(BasicBlock::const_iterator(CxtI)), IE(Inv);
566  I != IE; ++I)
568  return false;
569 
570  return !isEphemeralValueOf(Inv, CxtI);
571 }
572 
573 static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known,
574  unsigned Depth, const Query &Q) {
575  // Use of assumptions is context-sensitive. If we don't have a context, we
576  // cannot use them!
577  if (!Q.AC || !Q.CxtI)
578  return;
579 
580  unsigned BitWidth = Known.getBitWidth();
581 
582  // Note that the patterns below need to be kept in sync with the code
583  // in AssumptionCache::updateAffectedValues.
584 
585  for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
586  if (!AssumeVH)
587  continue;
588  CallInst *I = cast<CallInst>(AssumeVH);
589  assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() &&
590  "Got assumption for the wrong function!");
591  if (Q.isExcluded(I))
592  continue;
593 
594  // Warning: This loop can end up being somewhat performance sensitive.
595  // We're running this loop for once for each value queried resulting in a
596  // runtime of ~O(#assumes * #values).
597 
598  assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
599  "must be an assume intrinsic");
600 
601  Value *Arg = I->getArgOperand(0);
602 
603  if (Arg == V && isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
604  assert(BitWidth == 1 && "assume operand is not i1?");
605  Known.setAllOnes();
606  return;
607  }
608  if (match(Arg, m_Not(m_Specific(V))) &&
609  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
610  assert(BitWidth == 1 && "assume operand is not i1?");
611  Known.setAllZero();
612  return;
613  }
614 
615  // The remaining tests are all recursive, so bail out if we hit the limit.
616  if (Depth == MaxDepth)
617  continue;
618 
619  Value *A, *B;
620  auto m_V = m_CombineOr(m_Specific(V), m_PtrToInt(m_Specific(V)));
621 
622  CmpInst::Predicate Pred;
623  uint64_t C;
624  // assume(v = a)
625  if (match(Arg, m_c_ICmp(Pred, m_V, m_Value(A))) &&
626  Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
627  KnownBits RHSKnown(BitWidth);
628  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
629  Known.Zero |= RHSKnown.Zero;
630  Known.One |= RHSKnown.One;
631  // assume(v & b = a)
632  } else if (match(Arg,
633  m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), m_Value(A))) &&
634  Pred == ICmpInst::ICMP_EQ &&
635  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
636  KnownBits RHSKnown(BitWidth);
637  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
638  KnownBits MaskKnown(BitWidth);
639  computeKnownBits(B, MaskKnown, Depth+1, Query(Q, I));
640 
641  // For those bits in the mask that are known to be one, we can propagate
642  // known bits from the RHS to V.
643  Known.Zero |= RHSKnown.Zero & MaskKnown.One;
644  Known.One |= RHSKnown.One & MaskKnown.One;
645  // assume(~(v & b) = a)
646  } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_And(m_V, m_Value(B))),
647  m_Value(A))) &&
648  Pred == ICmpInst::ICMP_EQ &&
649  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
650  KnownBits RHSKnown(BitWidth);
651  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
652  KnownBits MaskKnown(BitWidth);
653  computeKnownBits(B, MaskKnown, Depth+1, Query(Q, I));
654 
655  // For those bits in the mask that are known to be one, we can propagate
656  // inverted known bits from the RHS to V.
657  Known.Zero |= RHSKnown.One & MaskKnown.One;
658  Known.One |= RHSKnown.Zero & MaskKnown.One;
659  // assume(v | b = a)
660  } else if (match(Arg,
661  m_c_ICmp(Pred, m_c_Or(m_V, m_Value(B)), m_Value(A))) &&
662  Pred == ICmpInst::ICMP_EQ &&
663  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
664  KnownBits RHSKnown(BitWidth);
665  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
666  KnownBits BKnown(BitWidth);
667  computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
668 
669  // For those bits in B that are known to be zero, we can propagate known
670  // bits from the RHS to V.
671  Known.Zero |= RHSKnown.Zero & BKnown.Zero;
672  Known.One |= RHSKnown.One & BKnown.Zero;
673  // assume(~(v | b) = a)
674  } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_Or(m_V, m_Value(B))),
675  m_Value(A))) &&
676  Pred == ICmpInst::ICMP_EQ &&
677  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
678  KnownBits RHSKnown(BitWidth);
679  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
680  KnownBits BKnown(BitWidth);
681  computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
682 
683  // For those bits in B that are known to be zero, we can propagate
684  // inverted known bits from the RHS to V.
685  Known.Zero |= RHSKnown.One & BKnown.Zero;
686  Known.One |= RHSKnown.Zero & BKnown.Zero;
687  // assume(v ^ b = a)
688  } else if (match(Arg,
689  m_c_ICmp(Pred, m_c_Xor(m_V, m_Value(B)), m_Value(A))) &&
690  Pred == ICmpInst::ICMP_EQ &&
691  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
692  KnownBits RHSKnown(BitWidth);
693  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
694  KnownBits BKnown(BitWidth);
695  computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
696 
697  // For those bits in B that are known to be zero, we can propagate known
698  // bits from the RHS to V. For those bits in B that are known to be one,
699  // we can propagate inverted known bits from the RHS to V.
700  Known.Zero |= RHSKnown.Zero & BKnown.Zero;
701  Known.One |= RHSKnown.One & BKnown.Zero;
702  Known.Zero |= RHSKnown.One & BKnown.One;
703  Known.One |= RHSKnown.Zero & BKnown.One;
704  // assume(~(v ^ b) = a)
705  } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_Xor(m_V, m_Value(B))),
706  m_Value(A))) &&
707  Pred == ICmpInst::ICMP_EQ &&
708  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
709  KnownBits RHSKnown(BitWidth);
710  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
711  KnownBits BKnown(BitWidth);
712  computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
713 
714  // For those bits in B that are known to be zero, we can propagate
715  // inverted known bits from the RHS to V. For those bits in B that are
716  // known to be one, we can propagate known bits from the RHS to V.
717  Known.Zero |= RHSKnown.One & BKnown.Zero;
718  Known.One |= RHSKnown.Zero & BKnown.Zero;
719  Known.Zero |= RHSKnown.Zero & BKnown.One;
720  Known.One |= RHSKnown.One & BKnown.One;
721  // assume(v << c = a)
722  } else if (match(Arg, m_c_ICmp(Pred, m_Shl(m_V, m_ConstantInt(C)),
723  m_Value(A))) &&
724  Pred == ICmpInst::ICMP_EQ &&
725  isValidAssumeForContext(I, Q.CxtI, Q.DT) &&
726  C < BitWidth) {
727  KnownBits RHSKnown(BitWidth);
728  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
729  // For those bits in RHS that are known, we can propagate them to known
730  // bits in V shifted to the right by C.
731  RHSKnown.Zero.lshrInPlace(C);
732  Known.Zero |= RHSKnown.Zero;
733  RHSKnown.One.lshrInPlace(C);
734  Known.One |= RHSKnown.One;
735  // assume(~(v << c) = a)
736  } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_Shl(m_V, m_ConstantInt(C))),
737  m_Value(A))) &&
738  Pred == ICmpInst::ICMP_EQ &&
739  isValidAssumeForContext(I, Q.CxtI, Q.DT) &&
740  C < BitWidth) {
741  KnownBits RHSKnown(BitWidth);
742  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
743  // For those bits in RHS that are known, we can propagate them inverted
744  // to known bits in V shifted to the right by C.
745  RHSKnown.One.lshrInPlace(C);
746  Known.Zero |= RHSKnown.One;
747  RHSKnown.Zero.lshrInPlace(C);
748  Known.One |= RHSKnown.Zero;
749  // assume(v >> c = a)
750  } else if (match(Arg,
751  m_c_ICmp(Pred, m_Shr(m_V, m_ConstantInt(C)),
752  m_Value(A))) &&
753  Pred == ICmpInst::ICMP_EQ &&
754  isValidAssumeForContext(I, Q.CxtI, Q.DT) &&
755  C < BitWidth) {
756  KnownBits RHSKnown(BitWidth);
757  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
758  // For those bits in RHS that are known, we can propagate them to known
759  // bits in V shifted to the right by C.
760  Known.Zero |= RHSKnown.Zero << C;
761  Known.One |= RHSKnown.One << C;
762  // assume(~(v >> c) = a)
763  } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_Shr(m_V, m_ConstantInt(C))),
764  m_Value(A))) &&
765  Pred == ICmpInst::ICMP_EQ &&
766  isValidAssumeForContext(I, Q.CxtI, Q.DT) &&
767  C < BitWidth) {
768  KnownBits RHSKnown(BitWidth);
769  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
770  // For those bits in RHS that are known, we can propagate them inverted
771  // to known bits in V shifted to the right by C.
772  Known.Zero |= RHSKnown.One << C;
773  Known.One |= RHSKnown.Zero << C;
774  // assume(v >=_s c) where c is non-negative
775  } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
776  Pred == ICmpInst::ICMP_SGE &&
777  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
778  KnownBits RHSKnown(BitWidth);
779  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
780 
781  if (RHSKnown.isNonNegative()) {
782  // We know that the sign bit is zero.
783  Known.makeNonNegative();
784  }
785  // assume(v >_s c) where c is at least -1.
786  } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
787  Pred == ICmpInst::ICMP_SGT &&
788  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
789  KnownBits RHSKnown(BitWidth);
790  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
791 
792  if (RHSKnown.isAllOnes() || RHSKnown.isNonNegative()) {
793  // We know that the sign bit is zero.
794  Known.makeNonNegative();
795  }
796  // assume(v <=_s c) where c is negative
797  } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
798  Pred == ICmpInst::ICMP_SLE &&
799  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
800  KnownBits RHSKnown(BitWidth);
801  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
802 
803  if (RHSKnown.isNegative()) {
804  // We know that the sign bit is one.
805  Known.makeNegative();
806  }
807  // assume(v <_s c) where c is non-positive
808  } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
809  Pred == ICmpInst::ICMP_SLT &&
810  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
811  KnownBits RHSKnown(BitWidth);
812  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
813 
814  if (RHSKnown.isZero() || RHSKnown.isNegative()) {
815  // We know that the sign bit is one.
816  Known.makeNegative();
817  }
818  // assume(v <=_u c)
819  } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
820  Pred == ICmpInst::ICMP_ULE &&
821  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
822  KnownBits RHSKnown(BitWidth);
823  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
824 
825  // Whatever high bits in c are zero are known to be zero.
826  Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros());
827  // assume(v <_u c)
828  } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
829  Pred == ICmpInst::ICMP_ULT &&
830  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
831  KnownBits RHSKnown(BitWidth);
832  computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
833 
834  // If the RHS is known zero, then this assumption must be wrong (nothing
835  // is unsigned less than zero). Signal a conflict and get out of here.
836  if (RHSKnown.isZero()) {
837  Known.Zero.setAllBits();
838  Known.One.setAllBits();
839  break;
840  }
841 
842  // Whatever high bits in c are zero are known to be zero (if c is a power
843  // of 2, then one more).
844  if (isKnownToBeAPowerOfTwo(A, false, Depth + 1, Query(Q, I)))
845  Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros() + 1);
846  else
847  Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros());
848  }
849  }
850 
851  // If assumptions conflict with each other or previous known bits, then we
852  // have a logical fallacy. It's possible that the assumption is not reachable,
853  // so this isn't a real bug. On the other hand, the program may have undefined
854  // behavior, or we might have a bug in the compiler. We can't assert/crash, so
855  // clear out the known bits, try to warn the user, and hope for the best.
856  if (Known.Zero.intersects(Known.One)) {
857  Known.resetAll();
858 
859  if (Q.ORE)
860  Q.ORE->emit([&]() {
861  auto *CxtI = const_cast<Instruction *>(Q.CxtI);
862  return OptimizationRemarkAnalysis("value-tracking", "BadAssumption",
863  CxtI)
864  << "Detected conflicting code assumptions. Program may "
865  "have undefined behavior, or compiler may have "
866  "internal error.";
867  });
868  }
869 }
870 
871 /// Compute known bits from a shift operator, including those with a
872 /// non-constant shift amount. Known is the output of this function. Known2 is a
873 /// pre-allocated temporary with the same bit width as Known. KZF and KOF are
874 /// operator-specific functions that, given the known-zero or known-one bits
875 /// respectively, and a shift amount, compute the implied known-zero or
876 /// known-one bits of the shift operator's result respectively for that shift
877 /// amount. The results from calling KZF and KOF are conservatively combined for
878 /// all permitted shift amounts.
880  const Operator *I, KnownBits &Known, KnownBits &Known2,
881  unsigned Depth, const Query &Q,
882  function_ref<APInt(const APInt &, unsigned)> KZF,
883  function_ref<APInt(const APInt &, unsigned)> KOF) {
884  unsigned BitWidth = Known.getBitWidth();
885 
886  if (auto *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
887  unsigned ShiftAmt = SA->getLimitedValue(BitWidth-1);
888 
889  computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
890  Known.Zero = KZF(Known.Zero, ShiftAmt);
891  Known.One = KOF(Known.One, ShiftAmt);
892  // If the known bits conflict, this must be an overflowing left shift, so
893  // the shift result is poison. We can return anything we want. Choose 0 for
894  // the best folding opportunity.
895  if (Known.hasConflict())
896  Known.setAllZero();
897 
898  return;
899  }
900 
901  computeKnownBits(I->getOperand(1), Known, Depth + 1, Q);
902 
903  // If the shift amount could be greater than or equal to the bit-width of the
904  // LHS, the value could be poison, but bail out because the check below is
905  // expensive. TODO: Should we just carry on?
906  if ((~Known.Zero).uge(BitWidth)) {
907  Known.resetAll();
908  return;
909  }
910 
911  // Note: We cannot use Known.Zero.getLimitedValue() here, because if
912  // BitWidth > 64 and any upper bits are known, we'll end up returning the
913  // limit value (which implies all bits are known).
914  uint64_t ShiftAmtKZ = Known.Zero.zextOrTrunc(64).getZExtValue();
915  uint64_t ShiftAmtKO = Known.One.zextOrTrunc(64).getZExtValue();
916 
917  // It would be more-clearly correct to use the two temporaries for this
918  // calculation. Reusing the APInts here to prevent unnecessary allocations.
919  Known.resetAll();
920 
921  // If we know the shifter operand is nonzero, we can sometimes infer more
922  // known bits. However this is expensive to compute, so be lazy about it and
923  // only compute it when absolutely necessary.
924  Optional<bool> ShifterOperandIsNonZero;
925 
926  // Early exit if we can't constrain any well-defined shift amount.
927  if (!(ShiftAmtKZ & (PowerOf2Ceil(BitWidth) - 1)) &&
928  !(ShiftAmtKO & (PowerOf2Ceil(BitWidth) - 1))) {
929  ShifterOperandIsNonZero = isKnownNonZero(I->getOperand(1), Depth + 1, Q);
930  if (!*ShifterOperandIsNonZero)
931  return;
932  }
933 
934  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
935 
936  Known.Zero.setAllBits();
937  Known.One.setAllBits();
938  for (unsigned ShiftAmt = 0; ShiftAmt < BitWidth; ++ShiftAmt) {
939  // Combine the shifted known input bits only for those shift amounts
940  // compatible with its known constraints.
941  if ((ShiftAmt & ~ShiftAmtKZ) != ShiftAmt)
942  continue;
943  if ((ShiftAmt | ShiftAmtKO) != ShiftAmt)
944  continue;
945  // If we know the shifter is nonzero, we may be able to infer more known
946  // bits. This check is sunk down as far as possible to avoid the expensive
947  // call to isKnownNonZero if the cheaper checks above fail.
948  if (ShiftAmt == 0) {
949  if (!ShifterOperandIsNonZero.hasValue())
950  ShifterOperandIsNonZero =
951  isKnownNonZero(I->getOperand(1), Depth + 1, Q);
952  if (*ShifterOperandIsNonZero)
953  continue;
954  }
955 
956  Known.Zero &= KZF(Known2.Zero, ShiftAmt);
957  Known.One &= KOF(Known2.One, ShiftAmt);
958  }
959 
960  // If the known bits conflict, the result is poison. Return a 0 and hope the
961  // caller can further optimize that.
962  if (Known.hasConflict())
963  Known.setAllZero();
964 }
965 
966 static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known,
967  unsigned Depth, const Query &Q) {
968  unsigned BitWidth = Known.getBitWidth();
969 
970  KnownBits Known2(Known);
971  switch (I->getOpcode()) {
972  default: break;
973  case Instruction::Load:
974  if (MDNode *MD =
975  Q.IIQ.getMetadata(cast<LoadInst>(I), LLVMContext::MD_range))
977  break;
978  case Instruction::And: {
979  // If either the LHS or the RHS are Zero, the result is zero.
980  computeKnownBits(I->getOperand(1), Known, Depth + 1, Q);
981  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
982 
983  // Output known-1 bits are only known if set in both the LHS & RHS.
984  Known.One &= Known2.One;
985  // Output known-0 are known to be clear if zero in either the LHS | RHS.
986  Known.Zero |= Known2.Zero;
987 
988  // and(x, add (x, -1)) is a common idiom that always clears the low bit;
989  // here we handle the more general case of adding any odd number by
990  // matching the form add(x, add(x, y)) where y is odd.
991  // TODO: This could be generalized to clearing any bit set in y where the
992  // following bit is known to be unset in y.
993  Value *X = nullptr, *Y = nullptr;
994  if (!Known.Zero[0] && !Known.One[0] &&
995  match(I, m_c_BinOp(m_Value(X), m_Add(m_Deferred(X), m_Value(Y))))) {
996  Known2.resetAll();
997  computeKnownBits(Y, Known2, Depth + 1, Q);
998  if (Known2.countMinTrailingOnes() > 0)
999  Known.Zero.setBit(0);
1000  }
1001  break;
1002  }
1003  case Instruction::Or:
1004  computeKnownBits(I->getOperand(1), Known, Depth + 1, Q);
1005  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
1006 
1007  // Output known-0 bits are only known if clear in both the LHS & RHS.
1008  Known.Zero &= Known2.Zero;
1009  // Output known-1 are known to be set if set in either the LHS | RHS.
1010  Known.One |= Known2.One;
1011  break;
1012  case Instruction::Xor: {
1013  computeKnownBits(I->getOperand(1), Known, Depth + 1, Q);
1014  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
1015 
1016  // Output known-0 bits are known if clear or set in both the LHS & RHS.
1017  APInt KnownZeroOut = (Known.Zero & Known2.Zero) | (Known.One & Known2.One);
1018  // Output known-1 are known to be set if set in only one of the LHS, RHS.
1019  Known.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero);
1020  Known.Zero = std::move(KnownZeroOut);
1021  break;
1022  }
1023  case Instruction::Mul: {
1024  bool NSW = Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(I));
1025  computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW, Known,
1026  Known2, Depth, Q);
1027  break;
1028  }
1029  case Instruction::UDiv: {
1030  // For the purposes of computing leading zeros we can conservatively
1031  // treat a udiv as a logical right shift by the power of 2 known to
1032  // be less than the denominator.
1033  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
1034  unsigned LeadZ = Known2.countMinLeadingZeros();
1035 
1036  Known2.resetAll();
1037  computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q);
1038  unsigned RHSMaxLeadingZeros = Known2.countMaxLeadingZeros();
1039  if (RHSMaxLeadingZeros != BitWidth)
1040  LeadZ = std::min(BitWidth, LeadZ + BitWidth - RHSMaxLeadingZeros - 1);
1041 
1042  Known.Zero.setHighBits(LeadZ);
1043  break;
1044  }
1045  case Instruction::Select: {
1046  const Value *LHS, *RHS;
1047  SelectPatternFlavor SPF = matchSelectPattern(I, LHS, RHS).Flavor;
1049  computeKnownBits(RHS, Known, Depth + 1, Q);
1050  computeKnownBits(LHS, Known2, Depth + 1, Q);
1051  } else {
1052  computeKnownBits(I->getOperand(2), Known, Depth + 1, Q);
1053  computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q);
1054  }
1055 
1056  unsigned MaxHighOnes = 0;
1057  unsigned MaxHighZeros = 0;
1058  if (SPF == SPF_SMAX) {
1059  // If both sides are negative, the result is negative.
1060  if (Known.isNegative() && Known2.isNegative())
1061  // We can derive a lower bound on the result by taking the max of the
1062  // leading one bits.
1063  MaxHighOnes =
1065  // If either side is non-negative, the result is non-negative.
1066  else if (Known.isNonNegative() || Known2.isNonNegative())
1067  MaxHighZeros = 1;
1068  } else if (SPF == SPF_SMIN) {
1069  // If both sides are non-negative, the result is non-negative.
1070  if (Known.isNonNegative() && Known2.isNonNegative())
1071  // We can derive an upper bound on the result by taking the max of the
1072  // leading zero bits.
1073  MaxHighZeros = std::max(Known.countMinLeadingZeros(),
1074  Known2.countMinLeadingZeros());
1075  // If either side is negative, the result is negative.
1076  else if (Known.isNegative() || Known2.isNegative())
1077  MaxHighOnes = 1;
1078  } else if (SPF == SPF_UMAX) {
1079  // We can derive a lower bound on the result by taking the max of the
1080  // leading one bits.
1081  MaxHighOnes =
1083  } else if (SPF == SPF_UMIN) {
1084  // We can derive an upper bound on the result by taking the max of the
1085  // leading zero bits.
1086  MaxHighZeros =
1088  } else if (SPF == SPF_ABS) {
1089  // RHS from matchSelectPattern returns the negation part of abs pattern.
1090  // If the negate has an NSW flag we can assume the sign bit of the result
1091  // will be 0 because that makes abs(INT_MIN) undefined.
1092  if (Q.IIQ.hasNoSignedWrap(cast<Instruction>(RHS)))
1093  MaxHighZeros = 1;
1094  }
1095 
1096  // Only known if known in both the LHS and RHS.
1097  Known.One &= Known2.One;
1098  Known.Zero &= Known2.Zero;
1099  if (MaxHighOnes > 0)
1100  Known.One.setHighBits(MaxHighOnes);
1101  if (MaxHighZeros > 0)
1102  Known.Zero.setHighBits(MaxHighZeros);
1103  break;
1104  }
1105  case Instruction::FPTrunc:
1106  case Instruction::FPExt:
1107  case Instruction::FPToUI:
1108  case Instruction::FPToSI:
1109  case Instruction::SIToFP:
1110  case Instruction::UIToFP:
1111  break; // Can't work with floating point.
1112  case Instruction::PtrToInt:
1113  case Instruction::IntToPtr:
1114  // Fall through and handle them the same as zext/trunc.
1116  case Instruction::ZExt:
1117  case Instruction::Trunc: {
1118  Type *SrcTy = I->getOperand(0)->getType();
1119 
1120  unsigned SrcBitWidth;
1121  // Note that we handle pointer operands here because of inttoptr/ptrtoint
1122  // which fall through here.
1123  Type *ScalarTy = SrcTy->getScalarType();
1124  SrcBitWidth = ScalarTy->isPointerTy() ?
1125  Q.DL.getIndexTypeSizeInBits(ScalarTy) :
1126  Q.DL.getTypeSizeInBits(ScalarTy);
1127 
1128  assert(SrcBitWidth && "SrcBitWidth can't be zero");
1129  Known = Known.zextOrTrunc(SrcBitWidth, false);
1130  computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
1131  Known = Known.zextOrTrunc(BitWidth, true /* ExtendedBitsAreKnownZero */);
1132  break;
1133  }
1134  case Instruction::BitCast: {
1135  Type *SrcTy = I->getOperand(0)->getType();
1136  if (SrcTy->isIntOrPtrTy() &&
1137  // TODO: For now, not handling conversions like:
1138  // (bitcast i64 %x to <2 x i32>)
1139  !I->getType()->isVectorTy()) {
1140  computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
1141  break;
1142  }
1143  break;
1144  }
1145  case Instruction::SExt: {
1146  // Compute the bits in the result that are not present in the input.
1147  unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
1148 
1149  Known = Known.trunc(SrcBitWidth);
1150  computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
1151  // If the sign bit of the input is known set or clear, then we know the
1152  // top bits of the result.
1153  Known = Known.sext(BitWidth);
1154  break;
1155  }
1156  case Instruction::Shl: {
1157  // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1158  bool NSW = Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(I));
1159  auto KZF = [NSW](const APInt &KnownZero, unsigned ShiftAmt) {
1160  APInt KZResult = KnownZero << ShiftAmt;
1161  KZResult.setLowBits(ShiftAmt); // Low bits known 0.
1162  // If this shift has "nsw" keyword, then the result is either a poison
1163  // value or has the same sign bit as the first operand.
1164  if (NSW && KnownZero.isSignBitSet())
1165  KZResult.setSignBit();
1166  return KZResult;
1167  };
1168 
1169  auto KOF = [NSW](const APInt &KnownOne, unsigned ShiftAmt) {
1170  APInt KOResult = KnownOne << ShiftAmt;
1171  if (NSW && KnownOne.isSignBitSet())
1172  KOResult.setSignBit();
1173  return KOResult;
1174  };
1175 
1176  computeKnownBitsFromShiftOperator(I, Known, Known2, Depth, Q, KZF, KOF);
1177  break;
1178  }
1179  case Instruction::LShr: {
1180  // (lshr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1181  auto KZF = [](const APInt &KnownZero, unsigned ShiftAmt) {
1182  APInt KZResult = KnownZero.lshr(ShiftAmt);
1183  // High bits known zero.
1184  KZResult.setHighBits(ShiftAmt);
1185  return KZResult;
1186  };
1187 
1188  auto KOF = [](const APInt &KnownOne, unsigned ShiftAmt) {
1189  return KnownOne.lshr(ShiftAmt);
1190  };
1191 
1192  computeKnownBitsFromShiftOperator(I, Known, Known2, Depth, Q, KZF, KOF);
1193  break;
1194  }
1195  case Instruction::AShr: {
1196  // (ashr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1197  auto KZF = [](const APInt &KnownZero, unsigned ShiftAmt) {
1198  return KnownZero.ashr(ShiftAmt);
1199  };
1200 
1201  auto KOF = [](const APInt &KnownOne, unsigned ShiftAmt) {
1202  return KnownOne.ashr(ShiftAmt);
1203  };
1204 
1205  computeKnownBitsFromShiftOperator(I, Known, Known2, Depth, Q, KZF, KOF);
1206  break;
1207  }
1208  case Instruction::Sub: {
1209  bool NSW = Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(I));
1210  computeKnownBitsAddSub(false, I->getOperand(0), I->getOperand(1), NSW,
1211  Known, Known2, Depth, Q);
1212  break;
1213  }
1214  case Instruction::Add: {
1215  bool NSW = Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(I));
1216  computeKnownBitsAddSub(true, I->getOperand(0), I->getOperand(1), NSW,
1217  Known, Known2, Depth, Q);
1218  break;
1219  }
1220  case Instruction::SRem:
1221  if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
1222  APInt RA = Rem->getValue().abs();
1223  if (RA.isPowerOf2()) {
1224  APInt LowBits = RA - 1;
1225  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
1226 
1227  // The low bits of the first operand are unchanged by the srem.
1228  Known.Zero = Known2.Zero & LowBits;
1229  Known.One = Known2.One & LowBits;
1230 
1231  // If the first operand is non-negative or has all low bits zero, then
1232  // the upper bits are all zero.
1233  if (Known2.isNonNegative() || LowBits.isSubsetOf(Known2.Zero))
1234  Known.Zero |= ~LowBits;
1235 
1236  // If the first operand is negative and not all low bits are zero, then
1237  // the upper bits are all one.
1238  if (Known2.isNegative() && LowBits.intersects(Known2.One))
1239  Known.One |= ~LowBits;
1240 
1241  assert((Known.Zero & Known.One) == 0 && "Bits known to be one AND zero?");
1242  break;
1243  }
1244  }
1245 
1246  // The sign bit is the LHS's sign bit, except when the result of the
1247  // remainder is zero.
1248  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
1249  // If it's known zero, our sign bit is also zero.
1250  if (Known2.isNonNegative())
1251  Known.makeNonNegative();
1252 
1253  break;
1254  case Instruction::URem: {
1255  if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
1256  const APInt &RA = Rem->getValue();
1257  if (RA.isPowerOf2()) {
1258  APInt LowBits = (RA - 1);
1259  computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
1260  Known.Zero |= ~LowBits;
1261  Known.One &= LowBits;
1262  break;
1263  }
1264  }
1265 
1266  // Since the result is less than or equal to either operand, any leading
1267  // zero bits in either operand must also exist in the result.
1268  computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
1269  computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q);
1270 
1271  unsigned Leaders =
1273  Known.resetAll();
1274  Known.Zero.setHighBits(Leaders);
1275  break;
1276  }
1277 
1278  case Instruction::Alloca: {
1279  const AllocaInst *AI = cast<AllocaInst>(I);
1280  unsigned Align = AI->getAlignment();
1281  if (Align == 0)
1282  Align = Q.DL.getABITypeAlignment(AI->getAllocatedType());
1283 
1284  if (Align > 0)
1285  Known.Zero.setLowBits(countTrailingZeros(Align));
1286  break;
1287  }
1288  case Instruction::GetElementPtr: {
1289  // Analyze all of the subscripts of this getelementptr instruction
1290  // to determine if we can prove known low zero bits.
1291  KnownBits LocalKnown(BitWidth);
1292  computeKnownBits(I->getOperand(0), LocalKnown, Depth + 1, Q);
1293  unsigned TrailZ = LocalKnown.countMinTrailingZeros();
1294 
1296  for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) {
1297  Value *Index = I->getOperand(i);
1298  if (StructType *STy = GTI.getStructTypeOrNull()) {
1299  // Handle struct member offset arithmetic.
1300 
1301  // Handle case when index is vector zeroinitializer
1302  Constant *CIndex = cast<Constant>(Index);
1303  if (CIndex->isZeroValue())
1304  continue;
1305 
1306  if (CIndex->getType()->isVectorTy())
1307  Index = CIndex->getSplatValue();
1308 
1309  unsigned Idx = cast<ConstantInt>(Index)->getZExtValue();
1310  const StructLayout *SL = Q.DL.getStructLayout(STy);
1311  uint64_t Offset = SL->getElementOffset(Idx);
1312  TrailZ = std::min<unsigned>(TrailZ,
1313  countTrailingZeros(Offset));
1314  } else {
1315  // Handle array index arithmetic.
1316  Type *IndexedTy = GTI.getIndexedType();
1317  if (!IndexedTy->isSized()) {
1318  TrailZ = 0;
1319  break;
1320  }
1321  unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits();
1322  uint64_t TypeSize = Q.DL.getTypeAllocSize(IndexedTy);
1323  LocalKnown.Zero = LocalKnown.One = APInt(GEPOpiBits, 0);
1324  computeKnownBits(Index, LocalKnown, Depth + 1, Q);
1325  TrailZ = std::min(TrailZ,
1326  unsigned(countTrailingZeros(TypeSize) +
1327  LocalKnown.countMinTrailingZeros()));
1328  }
1329  }
1330 
1331  Known.Zero.setLowBits(TrailZ);
1332  break;
1333  }
1334  case Instruction::PHI: {
1335  const PHINode *P = cast<PHINode>(I);
1336  // Handle the case of a simple two-predecessor recurrence PHI.
1337  // There's a lot more that could theoretically be done here, but
1338  // this is sufficient to catch some interesting cases.
1339  if (P->getNumIncomingValues() == 2) {
1340  for (unsigned i = 0; i != 2; ++i) {
1341  Value *L = P->getIncomingValue(i);
1342  Value *R = P->getIncomingValue(!i);
1343  Operator *LU = dyn_cast<Operator>(L);
1344  if (!LU)
1345  continue;
1346  unsigned Opcode = LU->getOpcode();
1347  // Check for operations that have the property that if
1348  // both their operands have low zero bits, the result
1349  // will have low zero bits.
1350  if (Opcode == Instruction::Add ||
1351  Opcode == Instruction::Sub ||
1352  Opcode == Instruction::And ||
1353  Opcode == Instruction::Or ||
1354  Opcode == Instruction::Mul) {
1355  Value *LL = LU->getOperand(0);
1356  Value *LR = LU->getOperand(1);
1357  // Find a recurrence.
1358  if (LL == I)
1359  L = LR;
1360  else if (LR == I)
1361  L = LL;
1362  else
1363  break;
1364  // Ok, we have a PHI of the form L op= R. Check for low
1365  // zero bits.
1366  computeKnownBits(R, Known2, Depth + 1, Q);
1367 
1368  // We need to take the minimum number of known bits
1369  KnownBits Known3(Known);
1370  computeKnownBits(L, Known3, Depth + 1, Q);
1371 
1372  Known.Zero.setLowBits(std::min(Known2.countMinTrailingZeros(),
1373  Known3.countMinTrailingZeros()));
1374 
1375  auto *OverflowOp = dyn_cast<OverflowingBinaryOperator>(LU);
1376  if (OverflowOp && Q.IIQ.hasNoSignedWrap(OverflowOp)) {
1377  // If initial value of recurrence is nonnegative, and we are adding
1378  // a nonnegative number with nsw, the result can only be nonnegative
1379  // or poison value regardless of the number of times we execute the
1380  // add in phi recurrence. If initial value is negative and we are
1381  // adding a negative number with nsw, the result can only be
1382  // negative or poison value. Similar arguments apply to sub and mul.
1383  //
1384  // (add non-negative, non-negative) --> non-negative
1385  // (add negative, negative) --> negative
1386  if (Opcode == Instruction::Add) {
1387  if (Known2.isNonNegative() && Known3.isNonNegative())
1388  Known.makeNonNegative();
1389  else if (Known2.isNegative() && Known3.isNegative())
1390  Known.makeNegative();
1391  }
1392 
1393  // (sub nsw non-negative, negative) --> non-negative
1394  // (sub nsw negative, non-negative) --> negative
1395  else if (Opcode == Instruction::Sub && LL == I) {
1396  if (Known2.isNonNegative() && Known3.isNegative())
1397  Known.makeNonNegative();
1398  else if (Known2.isNegative() && Known3.isNonNegative())
1399  Known.makeNegative();
1400  }
1401 
1402  // (mul nsw non-negative, non-negative) --> non-negative
1403  else if (Opcode == Instruction::Mul && Known2.isNonNegative() &&
1404  Known3.isNonNegative())
1405  Known.makeNonNegative();
1406  }
1407 
1408  break;
1409  }
1410  }
1411  }
1412 
1413  // Unreachable blocks may have zero-operand PHI nodes.
1414  if (P->getNumIncomingValues() == 0)
1415  break;
1416 
1417  // Otherwise take the unions of the known bit sets of the operands,
1418  // taking conservative care to avoid excessive recursion.
1419  if (Depth < MaxDepth - 1 && !Known.Zero && !Known.One) {
1420  // Skip if every incoming value references to ourself.
1421  if (dyn_cast_or_null<UndefValue>(P->hasConstantValue()))
1422  break;
1423 
1424  Known.Zero.setAllBits();
1425  Known.One.setAllBits();
1426  for (Value *IncValue : P->incoming_values()) {
1427  // Skip direct self references.
1428  if (IncValue == P) continue;
1429 
1430  Known2 = KnownBits(BitWidth);
1431  // Recurse, but cap the recursion to one level, because we don't
1432  // want to waste time spinning around in loops.
1433  computeKnownBits(IncValue, Known2, MaxDepth - 1, Q);
1434  Known.Zero &= Known2.Zero;
1435  Known.One &= Known2.One;
1436  // If all bits have been ruled out, there's no need to check
1437  // more operands.
1438  if (!Known.Zero && !Known.One)
1439  break;
1440  }
1441  }
1442  break;
1443  }
1444  case Instruction::Call:
1445  case Instruction::Invoke:
1446  // If range metadata is attached to this call, set known bits from that,
1447  // and then intersect with known bits based on other properties of the
1448  // function.
1449  if (MDNode *MD =
1450  Q.IIQ.getMetadata(cast<Instruction>(I), LLVMContext::MD_range))
1452  if (const Value *RV = ImmutableCallSite(I).getReturnedArgOperand()) {
1453  computeKnownBits(RV, Known2, Depth + 1, Q);
1454  Known.Zero |= Known2.Zero;
1455  Known.One |= Known2.One;
1456  }
1457  if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
1458  switch (II->getIntrinsicID()) {
1459  default: break;
1460  case Intrinsic::bitreverse:
1461  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
1462  Known.Zero |= Known2.Zero.reverseBits();
1463  Known.One |= Known2.One.reverseBits();
1464  break;
1465  case Intrinsic::bswap:
1466  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
1467  Known.Zero |= Known2.Zero.byteSwap();
1468  Known.One |= Known2.One.byteSwap();
1469  break;
1470  case Intrinsic::ctlz: {
1471  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
1472  // If we have a known 1, its position is our upper bound.
1473  unsigned PossibleLZ = Known2.One.countLeadingZeros();
1474  // If this call is undefined for 0, the result will be less than 2^n.
1475  if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext()))
1476  PossibleLZ = std::min(PossibleLZ, BitWidth - 1);
1477  unsigned LowBits = Log2_32(PossibleLZ)+1;
1478  Known.Zero.setBitsFrom(LowBits);
1479  break;
1480  }
1481  case Intrinsic::cttz: {
1482  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
1483  // If we have a known 1, its position is our upper bound.
1484  unsigned PossibleTZ = Known2.One.countTrailingZeros();
1485  // If this call is undefined for 0, the result will be less than 2^n.
1486  if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext()))
1487  PossibleTZ = std::min(PossibleTZ, BitWidth - 1);
1488  unsigned LowBits = Log2_32(PossibleTZ)+1;
1489  Known.Zero.setBitsFrom(LowBits);
1490  break;
1491  }
1492  case Intrinsic::ctpop: {
1493  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
1494  // We can bound the space the count needs. Also, bits known to be zero
1495  // can't contribute to the population.
1496  unsigned BitsPossiblySet = Known2.countMaxPopulation();
1497  unsigned LowBits = Log2_32(BitsPossiblySet)+1;
1498  Known.Zero.setBitsFrom(LowBits);
1499  // TODO: we could bound KnownOne using the lower bound on the number
1500  // of bits which might be set provided by popcnt KnownOne2.
1501  break;
1502  }
1503  case Intrinsic::fshr:
1504  case Intrinsic::fshl: {
1505  const APInt *SA;
1506  if (!match(I->getOperand(2), m_APInt(SA)))
1507  break;
1508 
1509  // Normalize to funnel shift left.
1510  uint64_t ShiftAmt = SA->urem(BitWidth);
1511  if (II->getIntrinsicID() == Intrinsic::fshr)
1512  ShiftAmt = BitWidth - ShiftAmt;
1513 
1514  KnownBits Known3(Known);
1515  computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
1516  computeKnownBits(I->getOperand(1), Known3, Depth + 1, Q);
1517 
1518  Known.Zero =
1519  Known2.Zero.shl(ShiftAmt) | Known3.Zero.lshr(BitWidth - ShiftAmt);
1520  Known.One =
1521  Known2.One.shl(ShiftAmt) | Known3.One.lshr(BitWidth - ShiftAmt);
1522  break;
1523  }
1524  case Intrinsic::uadd_sat:
1525  case Intrinsic::usub_sat: {
1526  bool IsAdd = II->getIntrinsicID() == Intrinsic::uadd_sat;
1527  computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
1528  computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q);
1529 
1530  // Add: Leading ones of either operand are preserved.
1531  // Sub: Leading zeros of LHS and leading ones of RHS are preserved
1532  // as leading zeros in the result.
1533  unsigned LeadingKnown;
1534  if (IsAdd)
1535  LeadingKnown = std::max(Known.countMinLeadingOnes(),
1536  Known2.countMinLeadingOnes());
1537  else
1538  LeadingKnown = std::max(Known.countMinLeadingZeros(),
1539  Known2.countMinLeadingOnes());
1540 
1542  IsAdd, /* NSW */ false, Known, Known2);
1543 
1544  // We select between the operation result and all-ones/zero
1545  // respectively, so we can preserve known ones/zeros.
1546  if (IsAdd) {
1547  Known.One.setHighBits(LeadingKnown);
1548  Known.Zero.clearAllBits();
1549  } else {
1550  Known.Zero.setHighBits(LeadingKnown);
1551  Known.One.clearAllBits();
1552  }
1553  break;
1554  }
1555  case Intrinsic::x86_sse42_crc32_64_64:
1556  Known.Zero.setBitsFrom(32);
1557  break;
1558  }
1559  }
1560  break;
1561  case Instruction::ExtractElement:
1562  // Look through extract element. At the moment we keep this simple and skip
1563  // tracking the specific element. But at least we might find information
1564  // valid for all elements of the vector (for example if vector is sign
1565  // extended, shifted, etc).
1566  computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
1567  break;
1568  case Instruction::ExtractValue:
1569  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) {
1570  const ExtractValueInst *EVI = cast<ExtractValueInst>(I);
1571  if (EVI->getNumIndices() != 1) break;
1572  if (EVI->getIndices()[0] == 0) {
1573  switch (II->getIntrinsicID()) {
1574  default: break;
1575  case Intrinsic::uadd_with_overflow:
1576  case Intrinsic::sadd_with_overflow:
1577  computeKnownBitsAddSub(true, II->getArgOperand(0),
1578  II->getArgOperand(1), false, Known, Known2,
1579  Depth, Q);
1580  break;
1581  case Intrinsic::usub_with_overflow:
1582  case Intrinsic::ssub_with_overflow:
1583  computeKnownBitsAddSub(false, II->getArgOperand(0),
1584  II->getArgOperand(1), false, Known, Known2,
1585  Depth, Q);
1586  break;
1587  case Intrinsic::umul_with_overflow:
1588  case Intrinsic::smul_with_overflow:
1589  computeKnownBitsMul(II->getArgOperand(0), II->getArgOperand(1), false,
1590  Known, Known2, Depth, Q);
1591  break;
1592  }
1593  }
1594  }
1595  }
1596 }
1597 
1598 /// Determine which bits of V are known to be either zero or one and return
1599 /// them.
1600 KnownBits computeKnownBits(const Value *V, unsigned Depth, const Query &Q) {
1601  KnownBits Known(getBitWidth(V->getType(), Q.DL));
1602  computeKnownBits(V, Known, Depth, Q);
1603  return Known;
1604 }
1605 
1606 /// Determine which bits of V are known to be either zero or one and return
1607 /// them in the Known bit set.
1608 ///
1609 /// NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that
1610 /// we cannot optimize based on the assumption that it is zero without changing
1611 /// it to be an explicit zero. If we don't change it to zero, other code could
1612 /// optimized based on the contradictory assumption that it is non-zero.
1613 /// Because instcombine aggressively folds operations with undef args anyway,
1614 /// this won't lose us code quality.
1615 ///
1616 /// This function is defined on values with integer type, values with pointer
1617 /// type, and vectors of integers. In the case
1618 /// where V is a vector, known zero, and known one values are the
1619 /// same width as the vector element, and the bit is set only if it is true
1620 /// for all of the elements in the vector.
1621 void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth,
1622  const Query &Q) {
1623  assert(V && "No Value?");
1624  assert(Depth <= MaxDepth && "Limit Search Depth");
1625  unsigned BitWidth = Known.getBitWidth();
1626 
1627  assert((V->getType()->isIntOrIntVectorTy(BitWidth) ||
1628  V->getType()->isPtrOrPtrVectorTy()) &&
1629  "Not integer or pointer type!");
1630 
1631  Type *ScalarTy = V->getType()->getScalarType();
1632  unsigned ExpectedWidth = ScalarTy->isPointerTy() ?
1633  Q.DL.getIndexTypeSizeInBits(ScalarTy) : Q.DL.getTypeSizeInBits(ScalarTy);
1634  assert(ExpectedWidth == BitWidth && "V and Known should have same BitWidth");
1635  (void)BitWidth;
1636  (void)ExpectedWidth;
1637 
1638  const APInt *C;
1639  if (match(V, m_APInt(C))) {
1640  // We know all of the bits for a scalar constant or a splat vector constant!
1641  Known.One = *C;
1642  Known.Zero = ~Known.One;
1643  return;
1644  }
1645  // Null and aggregate-zero are all-zeros.
1646  if (isa<ConstantPointerNull>(V) || isa<ConstantAggregateZero>(V)) {
1647  Known.setAllZero();
1648  return;
1649  }
1650  // Handle a constant vector by taking the intersection of the known bits of
1651  // each element.
1652  if (const ConstantDataSequential *CDS = dyn_cast<ConstantDataSequential>(V)) {
1653  // We know that CDS must be a vector of integers. Take the intersection of
1654  // each element.
1655  Known.Zero.setAllBits(); Known.One.setAllBits();
1656  for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
1657  APInt Elt = CDS->getElementAsAPInt(i);
1658  Known.Zero &= ~Elt;
1659  Known.One &= Elt;
1660  }
1661  return;
1662  }
1663 
1664  if (const auto *CV = dyn_cast<ConstantVector>(V)) {
1665  // We know that CV must be a vector of integers. Take the intersection of
1666  // each element.
1667  Known.Zero.setAllBits(); Known.One.setAllBits();
1668  for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
1669  Constant *Element = CV->getAggregateElement(i);
1670  auto *ElementCI = dyn_cast_or_null<ConstantInt>(Element);
1671  if (!ElementCI) {
1672  Known.resetAll();
1673  return;
1674  }
1675  const APInt &Elt = ElementCI->getValue();
1676  Known.Zero &= ~Elt;
1677  Known.One &= Elt;
1678  }
1679  return;
1680  }
1681 
1682  // Start out not knowing anything.
1683  Known.resetAll();
1684 
1685  // We can't imply anything about undefs.
1686  if (isa<UndefValue>(V))
1687  return;
1688 
1689  // There's no point in looking through other users of ConstantData for
1690  // assumptions. Confirm that we've handled them all.
1691  assert(!isa<ConstantData>(V) && "Unhandled constant data!");
1692 
1693  // Limit search depth.
1694  // All recursive calls that increase depth must come after this.
1695  if (Depth == MaxDepth)
1696  return;
1697 
1698  // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has
1699  // the bits of its aliasee.
1700  if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
1701  if (!GA->isInterposable())
1702  computeKnownBits(GA->getAliasee(), Known, Depth + 1, Q);
1703  return;
1704  }
1705 
1706  if (const Operator *I = dyn_cast<Operator>(V))
1707  computeKnownBitsFromOperator(I, Known, Depth, Q);
1708 
1709  // Aligned pointers have trailing zeros - refine Known.Zero set
1710  if (V->getType()->isPointerTy()) {
1711  unsigned Align = V->getPointerAlignment(Q.DL);
1712  if (Align)
1713  Known.Zero.setLowBits(countTrailingZeros(Align));
1714  }
1715 
1716  // computeKnownBitsFromAssume strictly refines Known.
1717  // Therefore, we run them after computeKnownBitsFromOperator.
1718 
1719  // Check whether a nearby assume intrinsic can determine some known bits.
1720  computeKnownBitsFromAssume(V, Known, Depth, Q);
1721 
1722  assert((Known.Zero & Known.One) == 0 && "Bits known to be one AND zero?");
1723 }
1724 
1725 /// Return true if the given value is known to have exactly one
1726 /// bit set when defined. For vectors return true if every element is known to
1727 /// be a power of two when defined. Supports values with integer or pointer
1728 /// types and vectors of integers.
1729 bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth,
1730  const Query &Q) {
1731  assert(Depth <= MaxDepth && "Limit Search Depth");
1732 
1733  // Attempt to match against constants.
1734  if (OrZero && match(V, m_Power2OrZero()))
1735  return true;
1736  if (match(V, m_Power2()))
1737  return true;
1738 
1739  // 1 << X is clearly a power of two if the one is not shifted off the end. If
1740  // it is shifted off the end then the result is undefined.
1741  if (match(V, m_Shl(m_One(), m_Value())))
1742  return true;
1743 
1744  // (signmask) >>l X is clearly a power of two if the one is not shifted off
1745  // the bottom. If it is shifted off the bottom then the result is undefined.
1746  if (match(V, m_LShr(m_SignMask(), m_Value())))
1747  return true;
1748 
1749  // The remaining tests are all recursive, so bail out if we hit the limit.
1750  if (Depth++ == MaxDepth)
1751  return false;
1752 
1753  Value *X = nullptr, *Y = nullptr;
1754  // A shift left or a logical shift right of a power of two is a power of two
1755  // or zero.
1756  if (OrZero && (match(V, m_Shl(m_Value(X), m_Value())) ||
1757  match(V, m_LShr(m_Value(X), m_Value()))))
1758  return isKnownToBeAPowerOfTwo(X, /*OrZero*/ true, Depth, Q);
1759 
1760  if (const ZExtInst *ZI = dyn_cast<ZExtInst>(V))
1761  return isKnownToBeAPowerOfTwo(ZI->getOperand(0), OrZero, Depth, Q);
1762 
1763  if (const SelectInst *SI = dyn_cast<SelectInst>(V))
1764  return isKnownToBeAPowerOfTwo(SI->getTrueValue(), OrZero, Depth, Q) &&
1765  isKnownToBeAPowerOfTwo(SI->getFalseValue(), OrZero, Depth, Q);
1766 
1767  if (OrZero && match(V, m_And(m_Value(X), m_Value(Y)))) {
1768  // A power of two and'd with anything is a power of two or zero.
1769  if (isKnownToBeAPowerOfTwo(X, /*OrZero*/ true, Depth, Q) ||
1770  isKnownToBeAPowerOfTwo(Y, /*OrZero*/ true, Depth, Q))
1771  return true;
1772  // X & (-X) is always a power of two or zero.
1773  if (match(X, m_Neg(m_Specific(Y))) || match(Y, m_Neg(m_Specific(X))))
1774  return true;
1775  return false;
1776  }
1777 
1778  // Adding a power-of-two or zero to the same power-of-two or zero yields
1779  // either the original power-of-two, a larger power-of-two or zero.
1780  if (match(V, m_Add(m_Value(X), m_Value(Y)))) {
1781  const OverflowingBinaryOperator *VOBO = cast<OverflowingBinaryOperator>(V);
1782  if (OrZero || Q.IIQ.hasNoUnsignedWrap(VOBO) ||
1783  Q.IIQ.hasNoSignedWrap(VOBO)) {
1784  if (match(X, m_And(m_Specific(Y), m_Value())) ||
1785  match(X, m_And(m_Value(), m_Specific(Y))))
1786  if (isKnownToBeAPowerOfTwo(Y, OrZero, Depth, Q))
1787  return true;
1788  if (match(Y, m_And(m_Specific(X), m_Value())) ||
1789  match(Y, m_And(m_Value(), m_Specific(X))))
1790  if (isKnownToBeAPowerOfTwo(X, OrZero, Depth, Q))
1791  return true;
1792 
1793  unsigned BitWidth = V->getType()->getScalarSizeInBits();
1794  KnownBits LHSBits(BitWidth);
1795  computeKnownBits(X, LHSBits, Depth, Q);
1796 
1797  KnownBits RHSBits(BitWidth);
1798  computeKnownBits(Y, RHSBits, Depth, Q);
1799  // If i8 V is a power of two or zero:
1800  // ZeroBits: 1 1 1 0 1 1 1 1
1801  // ~ZeroBits: 0 0 0 1 0 0 0 0
1802  if ((~(LHSBits.Zero & RHSBits.Zero)).isPowerOf2())
1803  // If OrZero isn't set, we cannot give back a zero result.
1804  // Make sure either the LHS or RHS has a bit set.
1805  if (OrZero || RHSBits.One.getBoolValue() || LHSBits.One.getBoolValue())
1806  return true;
1807  }
1808  }
1809 
1810  // An exact divide or right shift can only shift off zero bits, so the result
1811  // is a power of two only if the first operand is a power of two and not
1812  // copying a sign bit (sdiv int_min, 2).
1813  if (match(V, m_Exact(m_LShr(m_Value(), m_Value()))) ||
1814  match(V, m_Exact(m_UDiv(m_Value(), m_Value())))) {
1815  return isKnownToBeAPowerOfTwo(cast<Operator>(V)->getOperand(0), OrZero,
1816  Depth, Q);
1817  }
1818 
1819  return false;
1820 }
1821 
1822 /// Test whether a GEP's result is known to be non-null.
1823 ///
1824 /// Uses properties inherent in a GEP to try to determine whether it is known
1825 /// to be non-null.
1826 ///
1827 /// Currently this routine does not support vector GEPs.
1828 static bool isGEPKnownNonNull(const GEPOperator *GEP, unsigned Depth,
1829  const Query &Q) {
1830  const Function *F = nullptr;
1831  if (const Instruction *I = dyn_cast<Instruction>(GEP))
1832  F = I->getFunction();
1833 
1834  if (!GEP->isInBounds() ||
1836  return false;
1837 
1838  // FIXME: Support vector-GEPs.
1839  assert(GEP->getType()->isPointerTy() && "We only support plain pointer GEP");
1840 
1841  // If the base pointer is non-null, we cannot walk to a null address with an
1842  // inbounds GEP in address space zero.
1843  if (isKnownNonZero(GEP->getPointerOperand(), Depth, Q))
1844  return true;
1845 
1846  // Walk the GEP operands and see if any operand introduces a non-zero offset.
1847  // If so, then the GEP cannot produce a null pointer, as doing so would
1848  // inherently violate the inbounds contract within address space zero.
1849  for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
1850  GTI != GTE; ++GTI) {
1851  // Struct types are easy -- they must always be indexed by a constant.
1852  if (StructType *STy = GTI.getStructTypeOrNull()) {
1853  ConstantInt *OpC = cast<ConstantInt>(GTI.getOperand());
1854  unsigned ElementIdx = OpC->getZExtValue();
1855  const StructLayout *SL = Q.DL.getStructLayout(STy);
1856  uint64_t ElementOffset = SL->getElementOffset(ElementIdx);
1857  if (ElementOffset > 0)
1858  return true;
1859  continue;
1860  }
1861 
1862  // If we have a zero-sized type, the index doesn't matter. Keep looping.
1863  if (Q.DL.getTypeAllocSize(GTI.getIndexedType()) == 0)
1864  continue;
1865 
1866  // Fast path the constant operand case both for efficiency and so we don't
1867  // increment Depth when just zipping down an all-constant GEP.
1868  if (ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand())) {
1869  if (!OpC->isZero())
1870  return true;
1871  continue;
1872  }
1873 
1874  // We post-increment Depth here because while isKnownNonZero increments it
1875  // as well, when we pop back up that increment won't persist. We don't want
1876  // to recurse 10k times just because we have 10k GEP operands. We don't
1877  // bail completely out because we want to handle constant GEPs regardless
1878  // of depth.
1879  if (Depth++ >= MaxDepth)
1880  continue;
1881 
1882  if (isKnownNonZero(GTI.getOperand(), Depth, Q))
1883  return true;
1884  }
1885 
1886  return false;
1887 }
1888 
1890  const Instruction *CtxI,
1891  const DominatorTree *DT) {
1892  assert(V->getType()->isPointerTy() && "V must be pointer type");
1893  assert(!isa<ConstantData>(V) && "Did not expect ConstantPointerNull");
1894 
1895  if (!CtxI || !DT)
1896  return false;
1897 
1898  unsigned NumUsesExplored = 0;
1899  for (auto *U : V->users()) {
1900  // Avoid massive lists
1901  if (NumUsesExplored >= DomConditionsMaxUses)
1902  break;
1903  NumUsesExplored++;
1904 
1905  // If the value is used as an argument to a call or invoke, then argument
1906  // attributes may provide an answer about null-ness.
1907  if (auto CS = ImmutableCallSite(U))
1908  if (auto *CalledFunc = CS.getCalledFunction())
1909  for (const Argument &Arg : CalledFunc->args())
1910  if (CS.getArgOperand(Arg.getArgNo()) == V &&
1911  Arg.hasNonNullAttr() && DT->dominates(CS.getInstruction(), CtxI))
1912  return true;
1913 
1914  // Consider only compare instructions uniquely controlling a branch
1915  CmpInst::Predicate Pred;
1916  if (!match(const_cast<User *>(U),
1917  m_c_ICmp(Pred, m_Specific(V), m_Zero())) ||
1918  (Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE))
1919  continue;
1920 
1923  for (auto *CmpU : U->users()) {
1924  assert(WorkList.empty() && "Should be!");
1925  if (Visited.insert(CmpU).second)
1926  WorkList.push_back(CmpU);
1927 
1928  while (!WorkList.empty()) {
1929  auto *Curr = WorkList.pop_back_val();
1930 
1931  // If a user is an AND, add all its users to the work list. We only
1932  // propagate "pred != null" condition through AND because it is only
1933  // correct to assume that all conditions of AND are met in true branch.
1934  // TODO: Support similar logic of OR and EQ predicate?
1935  if (Pred == ICmpInst::ICMP_NE)
1936  if (auto *BO = dyn_cast<BinaryOperator>(Curr))
1937  if (BO->getOpcode() == Instruction::And) {
1938  for (auto *BOU : BO->users())
1939  if (Visited.insert(BOU).second)
1940  WorkList.push_back(BOU);
1941  continue;
1942  }
1943 
1944  if (const BranchInst *BI = dyn_cast<BranchInst>(Curr)) {
1945  assert(BI->isConditional() && "uses a comparison!");
1946 
1947  BasicBlock *NonNullSuccessor =
1948  BI->getSuccessor(Pred == ICmpInst::ICMP_EQ ? 1 : 0);
1949  BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
1950  if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
1951  return true;
1952  } else if (Pred == ICmpInst::ICMP_NE && isGuard(Curr) &&
1953  DT->dominates(cast<Instruction>(Curr), CtxI)) {
1954  return true;
1955  }
1956  }
1957  }
1958  }
1959 
1960  return false;
1961 }
1962 
1963 /// Does the 'Range' metadata (which must be a valid MD_range operand list)
1964 /// ensure that the value it's attached to is never Value? 'RangeType' is
1965 /// is the type of the value described by the range.
1966 static bool rangeMetadataExcludesValue(const MDNode* Ranges, const APInt& Value) {
1967  const unsigned NumRanges = Ranges->getNumOperands() / 2;
1968  assert(NumRanges >= 1);
1969  for (unsigned i = 0; i < NumRanges; ++i) {
1970  ConstantInt *Lower =
1971  mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 0));
1972  ConstantInt *Upper =
1973  mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 1));
1974  ConstantRange Range(Lower->getValue(), Upper->getValue());
1975  if (Range.contains(Value))
1976  return false;
1977  }
1978  return true;
1979 }
1980 
1981 /// Return true if the given value is known to be non-zero when defined. For
1982 /// vectors, return true if every element is known to be non-zero when
1983 /// defined. For pointers, if the context instruction and dominator tree are
1984 /// specified, perform context-sensitive analysis and return true if the
1985 /// pointer couldn't possibly be null at the specified instruction.
1986 /// Supports values with integer or pointer type and vectors of integers.
1987 bool isKnownNonZero(const Value *V, unsigned Depth, const Query &Q) {
1988  if (auto *C = dyn_cast<Constant>(V)) {
1989  if (C->isNullValue())
1990  return false;
1991  if (isa<ConstantInt>(C))
1992  // Must be non-zero due to null test above.
1993  return true;
1994 
1995  // For constant vectors, check that all elements are undefined or known
1996  // non-zero to determine that the whole vector is known non-zero.
1997  if (auto *VecTy = dyn_cast<VectorType>(C->getType())) {
1998  for (unsigned i = 0, e = VecTy->getNumElements(); i != e; ++i) {
1999  Constant *Elt = C->getAggregateElement(i);
2000  if (!Elt || Elt->isNullValue())
2001  return false;
2002  if (!isa<UndefValue>(Elt) && !isa<ConstantInt>(Elt))
2003  return false;
2004  }
2005  return true;
2006  }
2007 
2008  // A global variable in address space 0 is non null unless extern weak
2009  // or an absolute symbol reference. Other address spaces may have null as a
2010  // valid address for a global, so we can't assume anything.
2011  if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
2012  if (!GV->isAbsoluteSymbolRef() && !GV->hasExternalWeakLinkage() &&
2013  GV->getType()->getAddressSpace() == 0)
2014  return true;
2015  } else
2016  return false;
2017  }
2018 
2019  if (auto *I = dyn_cast<Instruction>(V)) {
2020  if (MDNode *Ranges = Q.IIQ.getMetadata(I, LLVMContext::MD_range)) {
2021  // If the possible ranges don't contain zero, then the value is
2022  // definitely non-zero.
2023  if (auto *Ty = dyn_cast<IntegerType>(V->getType())) {
2024  const APInt ZeroValue(Ty->getBitWidth(), 0);
2025  if (rangeMetadataExcludesValue(Ranges, ZeroValue))
2026  return true;
2027  }
2028  }
2029  }
2030 
2031  // Some of the tests below are recursive, so bail out if we hit the limit.
2032  if (Depth++ >= MaxDepth)
2033  return false;
2034 
2035  // Check for pointer simplifications.
2036  if (V->getType()->isPointerTy()) {
2037  // Alloca never returns null, malloc might.
2038  if (isa<AllocaInst>(V) && Q.DL.getAllocaAddrSpace() == 0)
2039  return true;
2040 
2041  // A byval, inalloca, or nonnull argument is never null.
2042  if (const Argument *A = dyn_cast<Argument>(V))
2043  if (A->hasByValOrInAllocaAttr() || A->hasNonNullAttr())
2044  return true;
2045 
2046  // A Load tagged with nonnull metadata is never null.
2047  if (const LoadInst *LI = dyn_cast<LoadInst>(V))
2048  if (Q.IIQ.getMetadata(LI, LLVMContext::MD_nonnull))
2049  return true;
2050 
2051  if (const auto *Call = dyn_cast<CallBase>(V)) {
2052  if (Call->isReturnNonNull())
2053  return true;
2054  if (const auto *RP = getArgumentAliasingToReturnedPointer(Call))
2055  return isKnownNonZero(RP, Depth, Q);
2056  }
2057  }
2058 
2059 
2060  // Check for recursive pointer simplifications.
2061  if (V->getType()->isPointerTy()) {
2062  if (isKnownNonNullFromDominatingCondition(V, Q.CxtI, Q.DT))
2063  return true;
2064 
2065  // Look through bitcast operations, GEPs, and int2ptr instructions as they
2066  // do not alter the value, or at least not the nullness property of the
2067  // value, e.g., int2ptr is allowed to zero/sign extend the value.
2068  //
2069  // Note that we have to take special care to avoid looking through
2070  // truncating casts, e.g., int2ptr/ptr2int with appropriate sizes, as well
2071  // as casts that can alter the value, e.g., AddrSpaceCasts.
2072  if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V))
2073  if (isGEPKnownNonNull(GEP, Depth, Q))
2074  return true;
2075 
2076  if (auto *BCO = dyn_cast<BitCastOperator>(V))
2077  return isKnownNonZero(BCO->getOperand(0), Depth, Q);
2078 
2079  if (auto *I2P = dyn_cast<IntToPtrInst>(V))
2080  if (Q.DL.getTypeSizeInBits(I2P->getSrcTy()) <=
2081  Q.DL.getTypeSizeInBits(I2P->getDestTy()))
2082  return isKnownNonZero(I2P->getOperand(0), Depth, Q);
2083  }
2084 
2085  // Similar to int2ptr above, we can look through ptr2int here if the cast
2086  // is a no-op or an extend and not a truncate.
2087  if (auto *P2I = dyn_cast<PtrToIntInst>(V))
2088  if (Q.DL.getTypeSizeInBits(P2I->getSrcTy()) <=
2089  Q.DL.getTypeSizeInBits(P2I->getDestTy()))
2090  return isKnownNonZero(P2I->getOperand(0), Depth, Q);
2091 
2092  unsigned BitWidth = getBitWidth(V->getType()->getScalarType(), Q.DL);
2093 
2094  // X | Y != 0 if X != 0 or Y != 0.
2095  Value *X = nullptr, *Y = nullptr;
2096  if (match(V, m_Or(m_Value(X), m_Value(Y))))
2097  return isKnownNonZero(X, Depth, Q) || isKnownNonZero(Y, Depth, Q);
2098 
2099  // ext X != 0 if X != 0.
2100  if (isa<SExtInst>(V) || isa<ZExtInst>(V))
2101  return isKnownNonZero(cast<Instruction>(V)->getOperand(0), Depth, Q);
2102 
2103  // shl X, Y != 0 if X is odd. Note that the value of the shift is undefined
2104  // if the lowest bit is shifted off the end.
2105  if (match(V, m_Shl(m_Value(X), m_Value(Y)))) {
2106  // shl nuw can't remove any non-zero bits.
2107  const OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V);
2108  if (Q.IIQ.hasNoUnsignedWrap(BO))
2109  return isKnownNonZero(X, Depth, Q);
2110 
2111  KnownBits Known(BitWidth);
2112  computeKnownBits(X, Known, Depth, Q);
2113  if (Known.One[0])
2114  return true;
2115  }
2116  // shr X, Y != 0 if X is negative. Note that the value of the shift is not
2117  // defined if the sign bit is shifted off the end.
2118  else if (match(V, m_Shr(m_Value(X), m_Value(Y)))) {
2119  // shr exact can only shift out zero bits.
2120  const PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V);
2121  if (BO->isExact())
2122  return isKnownNonZero(X, Depth, Q);
2123 
2124  KnownBits Known = computeKnownBits(X, Depth, Q);
2125  if (Known.isNegative())
2126  return true;
2127 
2128  // If the shifter operand is a constant, and all of the bits shifted
2129  // out are known to be zero, and X is known non-zero then at least one
2130  // non-zero bit must remain.
2131  if (ConstantInt *Shift = dyn_cast<ConstantInt>(Y)) {
2132  auto ShiftVal = Shift->getLimitedValue(BitWidth - 1);
2133  // Is there a known one in the portion not shifted out?
2134  if (Known.countMaxLeadingZeros() < BitWidth - ShiftVal)
2135  return true;
2136  // Are all the bits to be shifted out known zero?
2137  if (Known.countMinTrailingZeros() >= ShiftVal)
2138  return isKnownNonZero(X, Depth, Q);
2139  }
2140  }
2141  // div exact can only produce a zero if the dividend is zero.
2142  else if (match(V, m_Exact(m_IDiv(m_Value(X), m_Value())))) {
2143  return isKnownNonZero(X, Depth, Q);
2144  }
2145  // X + Y.
2146  else if (match(V, m_Add(m_Value(X), m_Value(Y)))) {
2147  KnownBits XKnown = computeKnownBits(X, Depth, Q);
2148  KnownBits YKnown = computeKnownBits(Y, Depth, Q);
2149 
2150  // If X and Y are both non-negative (as signed values) then their sum is not
2151  // zero unless both X and Y are zero.
2152  if (XKnown.isNonNegative() && YKnown.isNonNegative())
2153  if (isKnownNonZero(X, Depth, Q) || isKnownNonZero(Y, Depth, Q))
2154  return true;
2155 
2156  // If X and Y are both negative (as signed values) then their sum is not
2157  // zero unless both X and Y equal INT_MIN.
2158  if (XKnown.isNegative() && YKnown.isNegative()) {
2159  APInt Mask = APInt::getSignedMaxValue(BitWidth);
2160  // The sign bit of X is set. If some other bit is set then X is not equal
2161  // to INT_MIN.
2162  if (XKnown.One.intersects(Mask))
2163  return true;
2164  // The sign bit of Y is set. If some other bit is set then Y is not equal
2165  // to INT_MIN.
2166  if (YKnown.One.intersects(Mask))
2167  return true;
2168  }
2169 
2170  // The sum of a non-negative number and a power of two is not zero.
2171  if (XKnown.isNonNegative() &&
2172  isKnownToBeAPowerOfTwo(Y, /*OrZero*/ false, Depth, Q))
2173  return true;
2174  if (YKnown.isNonNegative() &&
2175  isKnownToBeAPowerOfTwo(X, /*OrZero*/ false, Depth, Q))
2176  return true;
2177  }
2178  // X * Y.
2179  else if (match(V, m_Mul(m_Value(X), m_Value(Y)))) {
2180  const OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V);
2181  // If X and Y are non-zero then so is X * Y as long as the multiplication
2182  // does not overflow.
2183  if ((Q.IIQ.hasNoSignedWrap(BO) || Q.IIQ.hasNoUnsignedWrap(BO)) &&
2184  isKnownNonZero(X, Depth, Q) && isKnownNonZero(Y, Depth, Q))
2185  return true;
2186  }
2187  // (C ? X : Y) != 0 if X != 0 and Y != 0.
2188  else if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
2189  if (isKnownNonZero(SI->getTrueValue(), Depth, Q) &&
2190  isKnownNonZero(SI->getFalseValue(), Depth, Q))
2191  return true;
2192  }
2193  // PHI
2194  else if (const PHINode *PN = dyn_cast<PHINode>(V)) {
2195  // Try and detect a recurrence that monotonically increases from a
2196  // starting value, as these are common as induction variables.
2197  if (PN->getNumIncomingValues() == 2) {
2198  Value *Start = PN->getIncomingValue(0);
2199  Value *Induction = PN->getIncomingValue(1);
2200  if (isa<ConstantInt>(Induction) && !isa<ConstantInt>(Start))
2201  std::swap(Start, Induction);
2202  if (ConstantInt *C = dyn_cast<ConstantInt>(Start)) {
2203  if (!C->isZero() && !C->isNegative()) {
2204  ConstantInt *X;
2205  if (Q.IIQ.UseInstrInfo &&
2206  (match(Induction, m_NSWAdd(m_Specific(PN), m_ConstantInt(X))) ||
2207  match(Induction, m_NUWAdd(m_Specific(PN), m_ConstantInt(X)))) &&
2208  !X->isNegative())
2209  return true;
2210  }
2211  }
2212  }
2213  // Check if all incoming values are non-zero constant.
2214  bool AllNonZeroConstants = llvm::all_of(PN->operands(), [](Value *V) {
2215  return isa<ConstantInt>(V) && !cast<ConstantInt>(V)->isZero();
2216  });
2217  if (AllNonZeroConstants)
2218  return true;
2219  }
2220 
2221  KnownBits Known(BitWidth);
2222  computeKnownBits(V, Known, Depth, Q);
2223  return Known.One != 0;
2224 }
2225 
2226 /// Return true if V2 == V1 + X, where X is known non-zero.
2227 static bool isAddOfNonZero(const Value *V1, const Value *V2, const Query &Q) {
2228  const BinaryOperator *BO = dyn_cast<BinaryOperator>(V1);
2229  if (!BO || BO->getOpcode() != Instruction::Add)
2230  return false;
2231  Value *Op = nullptr;
2232  if (V2 == BO->getOperand(0))
2233  Op = BO->getOperand(1);
2234  else if (V2 == BO->getOperand(1))
2235  Op = BO->getOperand(0);
2236  else
2237  return false;
2238  return isKnownNonZero(Op, 0, Q);
2239 }
2240 
2241 /// Return true if it is known that V1 != V2.
2242 static bool isKnownNonEqual(const Value *V1, const Value *V2, const Query &Q) {
2243  if (V1 == V2)
2244  return false;
2245  if (V1->getType() != V2->getType())
2246  // We can't look through casts yet.
2247  return false;
2248  if (isAddOfNonZero(V1, V2, Q) || isAddOfNonZero(V2, V1, Q))
2249  return true;
2250 
2251  if (V1->getType()->isIntOrIntVectorTy()) {
2252  // Are any known bits in V1 contradictory to known bits in V2? If V1
2253  // has a known zero where V2 has a known one, they must not be equal.
2254  KnownBits Known1 = computeKnownBits(V1, 0, Q);
2255  KnownBits Known2 = computeKnownBits(V2, 0, Q);
2256 
2257  if (Known1.Zero.intersects(Known2.One) ||
2258  Known2.Zero.intersects(Known1.One))
2259  return true;
2260  }
2261  return false;
2262 }
2263 
2264 /// Return true if 'V & Mask' is known to be zero. We use this predicate to
2265 /// simplify operations downstream. Mask is known to be zero for bits that V
2266 /// cannot have.
2267 ///
2268 /// This function is defined on values with integer type, values with pointer
2269 /// type, and vectors of integers. In the case
2270 /// where V is a vector, the mask, known zero, and known one values are the
2271 /// same width as the vector element, and the bit is set only if it is true
2272 /// for all of the elements in the vector.
2273 bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth,
2274  const Query &Q) {
2275  KnownBits Known(Mask.getBitWidth());
2276  computeKnownBits(V, Known, Depth, Q);
2277  return Mask.isSubsetOf(Known.Zero);
2278 }
2279 
2280 // Match a signed min+max clamp pattern like smax(smin(In, CHigh), CLow).
2281 // Returns the input and lower/upper bounds.
2282 static bool isSignedMinMaxClamp(const Value *Select, const Value *&In,
2283  const APInt *&CLow, const APInt *&CHigh) {
2284  assert(isa<Operator>(Select) &&
2285  cast<Operator>(Select)->getOpcode() == Instruction::Select &&
2286  "Input should be a Select!");
2287 
2288  const Value *LHS, *RHS, *LHS2, *RHS2;
2289  SelectPatternFlavor SPF = matchSelectPattern(Select, LHS, RHS).Flavor;
2290  if (SPF != SPF_SMAX && SPF != SPF_SMIN)
2291  return false;
2292 
2293  if (!match(RHS, m_APInt(CLow)))
2294  return false;
2295 
2296  SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor;
2297  if (getInverseMinMaxFlavor(SPF) != SPF2)
2298  return false;
2299 
2300  if (!match(RHS2, m_APInt(CHigh)))
2301  return false;
2302 
2303  if (SPF == SPF_SMIN)
2304  std::swap(CLow, CHigh);
2305 
2306  In = LHS2;
2307  return CLow->sle(*CHigh);
2308 }
2309 
2310 /// For vector constants, loop over the elements and find the constant with the
2311 /// minimum number of sign bits. Return 0 if the value is not a vector constant
2312 /// or if any element was not analyzed; otherwise, return the count for the
2313 /// element with the minimum number of sign bits.
2314 static unsigned computeNumSignBitsVectorConstant(const Value *V,
2315  unsigned TyBits) {
2316  const auto *CV = dyn_cast<Constant>(V);
2317  if (!CV || !CV->getType()->isVectorTy())
2318  return 0;
2319 
2320  unsigned MinSignBits = TyBits;
2321  unsigned NumElts = CV->getType()->getVectorNumElements();
2322  for (unsigned i = 0; i != NumElts; ++i) {
2323  // If we find a non-ConstantInt, bail out.
2324  auto *Elt = dyn_cast_or_null<ConstantInt>(CV->getAggregateElement(i));
2325  if (!Elt)
2326  return 0;
2327 
2328  MinSignBits = std::min(MinSignBits, Elt->getValue().getNumSignBits());
2329  }
2330 
2331  return MinSignBits;
2332 }
2333 
2334 static unsigned ComputeNumSignBitsImpl(const Value *V, unsigned Depth,
2335  const Query &Q);
2336 
2337 static unsigned ComputeNumSignBits(const Value *V, unsigned Depth,
2338  const Query &Q) {
2339  unsigned Result = ComputeNumSignBitsImpl(V, Depth, Q);
2340  assert(Result > 0 && "At least one sign bit needs to be present!");
2341  return Result;
2342 }
2343 
2344 /// Return the number of times the sign bit of the register is replicated into
2345 /// the other bits. We know that at least 1 bit is always equal to the sign bit
2346 /// (itself), but other cases can give us information. For example, immediately
2347 /// after an "ashr X, 2", we know that the top 3 bits are all equal to each
2348 /// other, so we return 3. For vectors, return the number of sign bits for the
2349 /// vector element with the minimum number of known sign bits.
2350 static unsigned ComputeNumSignBitsImpl(const Value *V, unsigned Depth,
2351  const Query &Q) {
2352  assert(Depth <= MaxDepth && "Limit Search Depth");
2353 
2354  // We return the minimum number of sign bits that are guaranteed to be present
2355  // in V, so for undef we have to conservatively return 1. We don't have the
2356  // same behavior for poison though -- that's a FIXME today.
2357 
2358  Type *ScalarTy = V->getType()->getScalarType();
2359  unsigned TyBits = ScalarTy->isPointerTy() ?
2360  Q.DL.getIndexTypeSizeInBits(ScalarTy) :
2361  Q.DL.getTypeSizeInBits(ScalarTy);
2362 
2363  unsigned Tmp, Tmp2;
2364  unsigned FirstAnswer = 1;
2365 
2366  // Note that ConstantInt is handled by the general computeKnownBits case
2367  // below.
2368 
2369  if (Depth == MaxDepth)
2370  return 1; // Limit search depth.
2371 
2372  const Operator *U = dyn_cast<Operator>(V);
2373  switch (Operator::getOpcode(V)) {
2374  default: break;
2375  case Instruction::SExt:
2376  Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits();
2377  return ComputeNumSignBits(U->getOperand(0), Depth + 1, Q) + Tmp;
2378 
2379  case Instruction::SDiv: {
2380  const APInt *Denominator;
2381  // sdiv X, C -> adds log(C) sign bits.
2382  if (match(U->getOperand(1), m_APInt(Denominator))) {
2383 
2384  // Ignore non-positive denominator.
2385  if (!Denominator->isStrictlyPositive())
2386  break;
2387 
2388  // Calculate the incoming numerator bits.
2389  unsigned NumBits = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
2390 
2391  // Add floor(log(C)) bits to the numerator bits.
2392  return std::min(TyBits, NumBits + Denominator->logBase2());
2393  }
2394  break;
2395  }
2396 
2397  case Instruction::SRem: {
2398  const APInt *Denominator;
2399  // srem X, C -> we know that the result is within [-C+1,C) when C is a
2400  // positive constant. This let us put a lower bound on the number of sign
2401  // bits.
2402  if (match(U->getOperand(1), m_APInt(Denominator))) {
2403 
2404  // Ignore non-positive denominator.
2405  if (!Denominator->isStrictlyPositive())
2406  break;
2407 
2408  // Calculate the incoming numerator bits. SRem by a positive constant
2409  // can't lower the number of sign bits.
2410  unsigned NumrBits =
2411  ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
2412 
2413  // Calculate the leading sign bit constraints by examining the
2414  // denominator. Given that the denominator is positive, there are two
2415  // cases:
2416  //
2417  // 1. the numerator is positive. The result range is [0,C) and [0,C) u<
2418  // (1 << ceilLogBase2(C)).
2419  //
2420  // 2. the numerator is negative. Then the result range is (-C,0] and
2421  // integers in (-C,0] are either 0 or >u (-1 << ceilLogBase2(C)).
2422  //
2423  // Thus a lower bound on the number of sign bits is `TyBits -
2424  // ceilLogBase2(C)`.
2425 
2426  unsigned ResBits = TyBits - Denominator->ceilLogBase2();
2427  return std::max(NumrBits, ResBits);
2428  }
2429  break;
2430  }
2431 
2432  case Instruction::AShr: {
2433  Tmp = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
2434  // ashr X, C -> adds C sign bits. Vectors too.
2435  const APInt *ShAmt;
2436  if (match(U->getOperand(1), m_APInt(ShAmt))) {
2437  if (ShAmt->uge(TyBits))
2438  break; // Bad shift.
2439  unsigned ShAmtLimited = ShAmt->getZExtValue();
2440  Tmp += ShAmtLimited;
2441  if (Tmp > TyBits) Tmp = TyBits;
2442  }
2443  return Tmp;
2444  }
2445  case Instruction::Shl: {
2446  const APInt *ShAmt;
2447  if (match(U->getOperand(1), m_APInt(ShAmt))) {
2448  // shl destroys sign bits.
2449  Tmp = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
2450  if (ShAmt->uge(TyBits) || // Bad shift.
2451  ShAmt->uge(Tmp)) break; // Shifted all sign bits out.
2452  Tmp2 = ShAmt->getZExtValue();
2453  return Tmp - Tmp2;
2454  }
2455  break;
2456  }
2457  case Instruction::And:
2458  case Instruction::Or:
2459  case Instruction::Xor: // NOT is handled here.
2460  // Logical binary ops preserve the number of sign bits at the worst.
2461  Tmp = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
2462  if (Tmp != 1) {
2463  Tmp2 = ComputeNumSignBits(U->getOperand(1), Depth + 1, Q);
2464  FirstAnswer = std::min(Tmp, Tmp2);
2465  // We computed what we know about the sign bits as our first
2466  // answer. Now proceed to the generic code that uses
2467  // computeKnownBits, and pick whichever answer is better.
2468  }
2469  break;
2470 
2471  case Instruction::Select: {
2472  // If we have a clamp pattern, we know that the number of sign bits will be
2473  // the minimum of the clamp min/max range.
2474  const Value *X;
2475  const APInt *CLow, *CHigh;
2476  if (isSignedMinMaxClamp(U, X, CLow, CHigh))
2477  return std::min(CLow->getNumSignBits(), CHigh->getNumSignBits());
2478 
2479  Tmp = ComputeNumSignBits(U->getOperand(1), Depth + 1, Q);
2480  if (Tmp == 1) break;
2481  Tmp2 = ComputeNumSignBits(U->getOperand(2), Depth + 1, Q);
2482  return std::min(Tmp, Tmp2);
2483  }
2484 
2485  case Instruction::Add:
2486  // Add can have at most one carry bit. Thus we know that the output
2487  // is, at worst, one more bit than the inputs.
2488  Tmp = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
2489  if (Tmp == 1) break;
2490 
2491  // Special case decrementing a value (ADD X, -1):
2492  if (const auto *CRHS = dyn_cast<Constant>(U->getOperand(1)))
2493  if (CRHS->isAllOnesValue()) {
2494  KnownBits Known(TyBits);
2495  computeKnownBits(U->getOperand(0), Known, Depth + 1, Q);
2496 
2497  // If the input is known to be 0 or 1, the output is 0/-1, which is all
2498  // sign bits set.
2499  if ((Known.Zero | 1).isAllOnesValue())
2500  return TyBits;
2501 
2502  // If we are subtracting one from a positive number, there is no carry
2503  // out of the result.
2504  if (Known.isNonNegative())
2505  return Tmp;
2506  }
2507 
2508  Tmp2 = ComputeNumSignBits(U->getOperand(1), Depth + 1, Q);
2509  if (Tmp2 == 1) break;
2510  return std::min(Tmp, Tmp2)-1;
2511 
2512  case Instruction::Sub:
2513  Tmp2 = ComputeNumSignBits(U->getOperand(1), Depth + 1, Q);
2514  if (Tmp2 == 1) break;
2515 
2516  // Handle NEG.
2517  if (const auto *CLHS = dyn_cast<Constant>(U->getOperand(0)))
2518  if (CLHS->isNullValue()) {
2519  KnownBits Known(TyBits);
2520  computeKnownBits(U->getOperand(1), Known, Depth + 1, Q);
2521  // If the input is known to be 0 or 1, the output is 0/-1, which is all
2522  // sign bits set.
2523  if ((Known.Zero | 1).isAllOnesValue())
2524  return TyBits;
2525 
2526  // If the input is known to be positive (the sign bit is known clear),
2527  // the output of the NEG has the same number of sign bits as the input.
2528  if (Known.isNonNegative())
2529  return Tmp2;
2530 
2531  // Otherwise, we treat this like a SUB.
2532  }
2533 
2534  // Sub can have at most one carry bit. Thus we know that the output
2535  // is, at worst, one more bit than the inputs.
2536  Tmp = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
2537  if (Tmp == 1) break;
2538  return std::min(Tmp, Tmp2)-1;
2539 
2540  case Instruction::Mul: {
2541  // The output of the Mul can be at most twice the valid bits in the inputs.
2542  unsigned SignBitsOp0 = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
2543  if (SignBitsOp0 == 1) break;
2544  unsigned SignBitsOp1 = ComputeNumSignBits(U->getOperand(1), Depth + 1, Q);
2545  if (SignBitsOp1 == 1) break;
2546  unsigned OutValidBits =
2547  (TyBits - SignBitsOp0 + 1) + (TyBits - SignBitsOp1 + 1);
2548  return OutValidBits > TyBits ? 1 : TyBits - OutValidBits + 1;
2549  }
2550 
2551  case Instruction::PHI: {
2552  const PHINode *PN = cast<PHINode>(U);
2553  unsigned NumIncomingValues = PN->getNumIncomingValues();
2554  // Don't analyze large in-degree PHIs.
2555  if (NumIncomingValues > 4) break;
2556  // Unreachable blocks may have zero-operand PHI nodes.
2557  if (NumIncomingValues == 0) break;
2558 
2559  // Take the minimum of all incoming values. This can't infinitely loop
2560  // because of our depth threshold.
2561  Tmp = ComputeNumSignBits(PN->getIncomingValue(0), Depth + 1, Q);
2562  for (unsigned i = 1, e = NumIncomingValues; i != e; ++i) {
2563  if (Tmp == 1) return Tmp;
2564  Tmp = std::min(
2565  Tmp, ComputeNumSignBits(PN->getIncomingValue(i), Depth + 1, Q));
2566  }
2567  return Tmp;
2568  }
2569 
2570  case Instruction::Trunc:
2571  // FIXME: it's tricky to do anything useful for this, but it is an important
2572  // case for targets like X86.
2573  break;
2574 
2575  case Instruction::ExtractElement:
2576  // Look through extract element. At the moment we keep this simple and skip
2577  // tracking the specific element. But at least we might find information
2578  // valid for all elements of the vector (for example if vector is sign
2579  // extended, shifted, etc).
2580  return ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
2581 
2582  case Instruction::ShuffleVector: {
2583  // TODO: This is copied almost directly from the SelectionDAG version of
2584  // ComputeNumSignBits. It would be better if we could share common
2585  // code. If not, make sure that changes are translated to the DAG.
2586 
2587  // Collect the minimum number of sign bits that are shared by every vector
2588  // element referenced by the shuffle.
2589  auto *Shuf = cast<ShuffleVectorInst>(U);
2590  int NumElts = Shuf->getOperand(0)->getType()->getVectorNumElements();
2591  int NumMaskElts = Shuf->getMask()->getType()->getVectorNumElements();
2592  APInt DemandedLHS(NumElts, 0), DemandedRHS(NumElts, 0);
2593  for (int i = 0; i != NumMaskElts; ++i) {
2594  int M = Shuf->getMaskValue(i);
2595  assert(M < NumElts * 2 && "Invalid shuffle mask constant");
2596  // For undef elements, we don't know anything about the common state of
2597  // the shuffle result.
2598  if (M == -1)
2599  return 1;
2600  if (M < NumElts)
2601  DemandedLHS.setBit(M % NumElts);
2602  else
2603  DemandedRHS.setBit(M % NumElts);
2604  }
2606  if (!!DemandedLHS)
2607  Tmp = ComputeNumSignBits(Shuf->getOperand(0), Depth + 1, Q);
2608  if (!!DemandedRHS) {
2609  Tmp2 = ComputeNumSignBits(Shuf->getOperand(1), Depth + 1, Q);
2610  Tmp = std::min(Tmp, Tmp2);
2611  }
2612  // If we don't know anything, early out and try computeKnownBits fall-back.
2613  if (Tmp == 1)
2614  break;
2615  assert(Tmp <= V->getType()->getScalarSizeInBits() &&
2616  "Failed to determine minimum sign bits");
2617  return Tmp;
2618  }
2619  }
2620 
2621  // Finally, if we can prove that the top bits of the result are 0's or 1's,
2622  // use this information.
2623 
2624  // If we can examine all elements of a vector constant successfully, we're
2625  // done (we can't do any better than that). If not, keep trying.
2626  if (unsigned VecSignBits = computeNumSignBitsVectorConstant(V, TyBits))
2627  return VecSignBits;
2628 
2629  KnownBits Known(TyBits);
2630  computeKnownBits(V, Known, Depth, Q);
2631 
2632  // If we know that the sign bit is either zero or one, determine the number of
2633  // identical bits in the top of the input value.
2634  return std::max(FirstAnswer, Known.countMinSignBits());
2635 }
2636 
2637 /// This function computes the integer multiple of Base that equals V.
2638 /// If successful, it returns true and returns the multiple in
2639 /// Multiple. If unsuccessful, it returns false. It looks
2640 /// through SExt instructions only if LookThroughSExt is true.
2641 bool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple,
2642  bool LookThroughSExt, unsigned Depth) {
2643  const unsigned MaxDepth = 6;
2644 
2645  assert(V && "No Value?");
2646  assert(Depth <= MaxDepth && "Limit Search Depth");
2647  assert(V->getType()->isIntegerTy() && "Not integer or pointer type!");
2648 
2649  Type *T = V->getType();
2650 
2651  ConstantInt *CI = dyn_cast<ConstantInt>(V);
2652 
2653  if (Base == 0)
2654  return false;
2655 
2656  if (Base == 1) {
2657  Multiple = V;
2658  return true;
2659  }
2660 
2662  Constant *BaseVal = ConstantInt::get(T, Base);
2663  if (CO && CO == BaseVal) {
2664  // Multiple is 1.
2665  Multiple = ConstantInt::get(T, 1);
2666  return true;
2667  }
2668 
2669  if (CI && CI->getZExtValue() % Base == 0) {
2670  Multiple = ConstantInt::get(T, CI->getZExtValue() / Base);
2671  return true;
2672  }
2673 
2674  if (Depth == MaxDepth) return false; // Limit search depth.
2675 
2676  Operator *I = dyn_cast<Operator>(V);
2677  if (!I) return false;
2678 
2679  switch (I->getOpcode()) {
2680  default: break;
2681  case Instruction::SExt:
2682  if (!LookThroughSExt) return false;
2683  // otherwise fall through to ZExt
2685  case Instruction::ZExt:
2686  return ComputeMultiple(I->getOperand(0), Base, Multiple,
2687  LookThroughSExt, Depth+1);
2688  case Instruction::Shl:
2689  case Instruction::Mul: {
2690  Value *Op0 = I->getOperand(0);
2691  Value *Op1 = I->getOperand(1);
2692 
2693  if (I->getOpcode() == Instruction::Shl) {
2694  ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1);
2695  if (!Op1CI) return false;
2696  // Turn Op0 << Op1 into Op0 * 2^Op1
2697  APInt Op1Int = Op1CI->getValue();
2698  uint64_t BitToSet = Op1Int.getLimitedValue(Op1Int.getBitWidth() - 1);
2699  APInt API(Op1Int.getBitWidth(), 0);
2700  API.setBit(BitToSet);
2701  Op1 = ConstantInt::get(V->getContext(), API);
2702  }
2703 
2704  Value *Mul0 = nullptr;
2705  if (ComputeMultiple(Op0, Base, Mul0, LookThroughSExt, Depth+1)) {
2706  if (Constant *Op1C = dyn_cast<Constant>(Op1))
2707  if (Constant *MulC = dyn_cast<Constant>(Mul0)) {
2708  if (Op1C->getType()->getPrimitiveSizeInBits() <
2709  MulC->getType()->getPrimitiveSizeInBits())
2710  Op1C = ConstantExpr::getZExt(Op1C, MulC->getType());
2711  if (Op1C->getType()->getPrimitiveSizeInBits() >
2712  MulC->getType()->getPrimitiveSizeInBits())
2713  MulC = ConstantExpr::getZExt(MulC, Op1C->getType());
2714 
2715  // V == Base * (Mul0 * Op1), so return (Mul0 * Op1)
2716  Multiple = ConstantExpr::getMul(MulC, Op1C);
2717  return true;
2718  }
2719 
2720  if (ConstantInt *Mul0CI = dyn_cast<ConstantInt>(Mul0))
2721  if (Mul0CI->getValue() == 1) {
2722  // V == Base * Op1, so return Op1
2723  Multiple = Op1;
2724  return true;
2725  }
2726  }
2727 
2728  Value *Mul1 = nullptr;
2729  if (ComputeMultiple(Op1, Base, Mul1, LookThroughSExt, Depth+1)) {
2730  if (Constant *Op0C = dyn_cast<Constant>(Op0))
2731  if (Constant *MulC = dyn_cast<Constant>(Mul1)) {
2732  if (Op0C->getType()->getPrimitiveSizeInBits() <
2733  MulC->getType()->getPrimitiveSizeInBits())
2734  Op0C = ConstantExpr::getZExt(Op0C, MulC->getType());
2735  if (Op0C->getType()->getPrimitiveSizeInBits() >
2736  MulC->getType()->getPrimitiveSizeInBits())
2737  MulC = ConstantExpr::getZExt(MulC, Op0C->getType());
2738 
2739  // V == Base * (Mul1 * Op0), so return (Mul1 * Op0)
2740  Multiple = ConstantExpr::getMul(MulC, Op0C);
2741  return true;
2742  }
2743 
2744  if (ConstantInt *Mul1CI = dyn_cast<ConstantInt>(Mul1))
2745  if (Mul1CI->getValue() == 1) {
2746  // V == Base * Op0, so return Op0
2747  Multiple = Op0;
2748  return true;
2749  }
2750  }
2751  }
2752  }
2753 
2754  // We could not determine if V is a multiple of Base.
2755  return false;
2756 }
2757 
2759  const TargetLibraryInfo *TLI) {
2760  const Function *F = ICS.getCalledFunction();
2761  if (!F)
2762  return Intrinsic::not_intrinsic;
2763 
2764  if (F->isIntrinsic())
2765  return F->getIntrinsicID();
2766 
2767  if (!TLI)
2768  return Intrinsic::not_intrinsic;
2769 
2770  LibFunc Func;
2771  // We're going to make assumptions on the semantics of the functions, check
2772  // that the target knows that it's available in this environment and it does
2773  // not have local linkage.
2774  if (!F || F->hasLocalLinkage() || !TLI->getLibFunc(*F, Func))
2775  return Intrinsic::not_intrinsic;
2776 
2777  if (!ICS.onlyReadsMemory())
2778  return Intrinsic::not_intrinsic;
2779 
2780  // Otherwise check if we have a call to a function that can be turned into a
2781  // vector intrinsic.
2782  switch (Func) {
2783  default:
2784  break;
2785  case LibFunc_sin:
2786  case LibFunc_sinf:
2787  case LibFunc_sinl:
2788  return Intrinsic::sin;
2789  case LibFunc_cos:
2790  case LibFunc_cosf:
2791  case LibFunc_cosl:
2792  return Intrinsic::cos;
2793  case LibFunc_exp:
2794  case LibFunc_expf:
2795  case LibFunc_expl:
2796  return Intrinsic::exp;
2797  case LibFunc_exp2:
2798  case LibFunc_exp2f:
2799  case LibFunc_exp2l:
2800  return Intrinsic::exp2;
2801  case LibFunc_log:
2802  case LibFunc_logf:
2803  case LibFunc_logl:
2804  return Intrinsic::log;
2805  case LibFunc_log10:
2806  case LibFunc_log10f:
2807  case LibFunc_log10l:
2808  return Intrinsic::log10;
2809  case LibFunc_log2:
2810  case LibFunc_log2f:
2811  case LibFunc_log2l:
2812  return Intrinsic::log2;
2813  case LibFunc_fabs:
2814  case LibFunc_fabsf:
2815  case LibFunc_fabsl:
2816  return Intrinsic::fabs;
2817  case LibFunc_fmin:
2818  case LibFunc_fminf:
2819  case LibFunc_fminl:
2820  return Intrinsic::minnum;
2821  case LibFunc_fmax:
2822  case LibFunc_fmaxf:
2823  case LibFunc_fmaxl:
2824  return Intrinsic::maxnum;
2825  case LibFunc_copysign:
2826  case LibFunc_copysignf:
2827  case LibFunc_copysignl:
2828  return Intrinsic::copysign;
2829  case LibFunc_floor:
2830  case LibFunc_floorf:
2831  case LibFunc_floorl:
2832  return Intrinsic::floor;
2833  case LibFunc_ceil:
2834  case LibFunc_ceilf:
2835  case LibFunc_ceill:
2836  return Intrinsic::ceil;
2837  case LibFunc_trunc:
2838  case LibFunc_truncf:
2839  case LibFunc_truncl:
2840  return Intrinsic::trunc;
2841  case LibFunc_rint:
2842  case LibFunc_rintf:
2843  case LibFunc_rintl:
2844  return Intrinsic::rint;
2845  case LibFunc_nearbyint:
2846  case LibFunc_nearbyintf:
2847  case LibFunc_nearbyintl:
2848  return Intrinsic::nearbyint;
2849  case LibFunc_round:
2850  case LibFunc_roundf:
2851  case LibFunc_roundl:
2852  return Intrinsic::round;
2853  case LibFunc_pow:
2854  case LibFunc_powf:
2855  case LibFunc_powl:
2856  return Intrinsic::pow;
2857  case LibFunc_sqrt:
2858  case LibFunc_sqrtf:
2859  case LibFunc_sqrtl:
2860  return Intrinsic::sqrt;
2861  }
2862 
2863  return Intrinsic::not_intrinsic;
2864 }
2865 
2866 /// Return true if we can prove that the specified FP value is never equal to
2867 /// -0.0.
2868 ///
2869 /// NOTE: this function will need to be revisited when we support non-default
2870 /// rounding modes!
2872  unsigned Depth) {
2873  if (auto *CFP = dyn_cast<ConstantFP>(V))
2874  return !CFP->getValueAPF().isNegZero();
2875 
2876  // Limit search depth.
2877  if (Depth == MaxDepth)
2878  return false;
2879 
2880  auto *Op = dyn_cast<Operator>(V);
2881  if (!Op)
2882  return false;
2883 
2884  // Check if the nsz fast-math flag is set.
2885  if (auto *FPO = dyn_cast<FPMathOperator>(Op))
2886  if (FPO->hasNoSignedZeros())
2887  return true;
2888 
2889  // (fadd x, 0.0) is guaranteed to return +0.0, not -0.0.
2890  if (match(Op, m_FAdd(m_Value(), m_PosZeroFP())))
2891  return true;
2892 
2893  // sitofp and uitofp turn into +0.0 for zero.
2894  if (isa<SIToFPInst>(Op) || isa<UIToFPInst>(Op))
2895  return true;
2896 
2897  if (auto *Call = dyn_cast<CallInst>(Op)) {
2898  Intrinsic::ID IID = getIntrinsicForCallSite(Call, TLI);
2899  switch (IID) {
2900  default:
2901  break;
2902  // sqrt(-0.0) = -0.0, no other negative results are possible.
2903  case Intrinsic::sqrt:
2904  case Intrinsic::canonicalize:
2905  return CannotBeNegativeZero(Call->getArgOperand(0), TLI, Depth + 1);
2906  // fabs(x) != -0.0
2907  case Intrinsic::fabs:
2908  return true;
2909  }
2910  }
2911 
2912  return false;
2913 }
2914 
2915 /// If \p SignBitOnly is true, test for a known 0 sign bit rather than a
2916 /// standard ordered compare. e.g. make -0.0 olt 0.0 be true because of the sign
2917 /// bit despite comparing equal.
2919  const TargetLibraryInfo *TLI,
2920  bool SignBitOnly,
2921  unsigned Depth) {
2922  // TODO: This function does not do the right thing when SignBitOnly is true
2923  // and we're lowering to a hypothetical IEEE 754-compliant-but-evil platform
2924  // which flips the sign bits of NaNs. See
2925  // https://llvm.org/bugs/show_bug.cgi?id=31702.
2926 
2927  if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) {
2928  return !CFP->getValueAPF().isNegative() ||
2929  (!SignBitOnly && CFP->getValueAPF().isZero());
2930  }
2931 
2932  // Handle vector of constants.
2933  if (auto *CV = dyn_cast<Constant>(V)) {
2934  if (CV->getType()->isVectorTy()) {
2935  unsigned NumElts = CV->getType()->getVectorNumElements();
2936  for (unsigned i = 0; i != NumElts; ++i) {
2937  auto *CFP = dyn_cast_or_null<ConstantFP>(CV->getAggregateElement(i));
2938  if (!CFP)
2939  return false;
2940  if (CFP->getValueAPF().isNegative() &&
2941  (SignBitOnly || !CFP->getValueAPF().isZero()))
2942  return false;
2943  }
2944 
2945  // All non-negative ConstantFPs.
2946  return true;
2947  }
2948  }
2949 
2950  if (Depth == MaxDepth)
2951  return false; // Limit search depth.
2952 
2953  const Operator *I = dyn_cast<Operator>(V);
2954  if (!I)
2955  return false;
2956 
2957  switch (I->getOpcode()) {
2958  default:
2959  break;
2960  // Unsigned integers are always nonnegative.
2961  case Instruction::UIToFP:
2962  return true;
2963  case Instruction::FMul:
2964  // x*x is always non-negative or a NaN.
2965  if (I->getOperand(0) == I->getOperand(1) &&
2966  (!SignBitOnly || cast<FPMathOperator>(I)->hasNoNaNs()))
2967  return true;
2968 
2970  case Instruction::FAdd:
2971  case Instruction::FDiv:
2972  case Instruction::FRem:
2973  return cannotBeOrderedLessThanZeroImpl(I->getOperand(0), TLI, SignBitOnly,
2974  Depth + 1) &&
2975  cannotBeOrderedLessThanZeroImpl(I->getOperand(1), TLI, SignBitOnly,
2976  Depth + 1);
2977  case Instruction::Select:
2978  return cannotBeOrderedLessThanZeroImpl(I->getOperand(1), TLI, SignBitOnly,
2979  Depth + 1) &&
2980  cannotBeOrderedLessThanZeroImpl(I->getOperand(2), TLI, SignBitOnly,
2981  Depth + 1);
2982  case Instruction::FPExt:
2983  case Instruction::FPTrunc:
2984  // Widening/narrowing never change sign.
2985  return cannotBeOrderedLessThanZeroImpl(I->getOperand(0), TLI, SignBitOnly,
2986  Depth + 1);
2987  case Instruction::ExtractElement:
2988  // Look through extract element. At the moment we keep this simple and skip
2989  // tracking the specific element. But at least we might find information
2990  // valid for all elements of the vector.
2991  return cannotBeOrderedLessThanZeroImpl(I->getOperand(0), TLI, SignBitOnly,
2992  Depth + 1);
2993  case Instruction::Call:
2994  const auto *CI = cast<CallInst>(I);
2995  Intrinsic::ID IID = getIntrinsicForCallSite(CI, TLI);
2996  switch (IID) {
2997  default:
2998  break;
2999  case Intrinsic::maxnum:
3000  return (isKnownNeverNaN(I->getOperand(0), TLI) &&
3002  SignBitOnly, Depth + 1)) ||
3003  (isKnownNeverNaN(I->getOperand(1), TLI) &&
3005  SignBitOnly, Depth + 1));
3006 
3007  case Intrinsic::maximum:
3008  return cannotBeOrderedLessThanZeroImpl(I->getOperand(0), TLI, SignBitOnly,
3009  Depth + 1) ||
3010  cannotBeOrderedLessThanZeroImpl(I->getOperand(1), TLI, SignBitOnly,
3011  Depth + 1);
3012  case Intrinsic::minnum:
3013  case Intrinsic::minimum:
3014  return cannotBeOrderedLessThanZeroImpl(I->getOperand(0), TLI, SignBitOnly,
3015  Depth + 1) &&
3016  cannotBeOrderedLessThanZeroImpl(I->getOperand(1), TLI, SignBitOnly,
3017  Depth + 1);
3018  case Intrinsic::exp:
3019  case Intrinsic::exp2:
3020  case Intrinsic::fabs:
3021  return true;
3022 
3023  case Intrinsic::sqrt:
3024  // sqrt(x) is always >= -0 or NaN. Moreover, sqrt(x) == -0 iff x == -0.
3025  if (!SignBitOnly)
3026  return true;
3027  return CI->hasNoNaNs() && (CI->hasNoSignedZeros() ||
3028  CannotBeNegativeZero(CI->getOperand(0), TLI));
3029 
3030  case Intrinsic::powi:
3031  if (ConstantInt *Exponent = dyn_cast<ConstantInt>(I->getOperand(1))) {
3032  // powi(x,n) is non-negative if n is even.
3033  if (Exponent->getBitWidth() <= 64 && Exponent->getSExtValue() % 2u == 0)
3034  return true;
3035  }
3036  // TODO: This is not correct. Given that exp is an integer, here are the
3037  // ways that pow can return a negative value:
3038  //
3039  // pow(x, exp) --> negative if exp is odd and x is negative.
3040  // pow(-0, exp) --> -inf if exp is negative odd.
3041  // pow(-0, exp) --> -0 if exp is positive odd.
3042  // pow(-inf, exp) --> -0 if exp is negative odd.
3043  // pow(-inf, exp) --> -inf if exp is positive odd.
3044  //
3045  // Therefore, if !SignBitOnly, we can return true if x >= +0 or x is NaN,
3046  // but we must return false if x == -0. Unfortunately we do not currently
3047  // have a way of expressing this constraint. See details in
3048  // https://llvm.org/bugs/show_bug.cgi?id=31702.
3049  return cannotBeOrderedLessThanZeroImpl(I->getOperand(0), TLI, SignBitOnly,
3050  Depth + 1);
3051 
3052  case Intrinsic::fma:
3053  case Intrinsic::fmuladd:
3054  // x*x+y is non-negative if y is non-negative.
3055  return I->getOperand(0) == I->getOperand(1) &&
3056  (!SignBitOnly || cast<FPMathOperator>(I)->hasNoNaNs()) &&
3057  cannotBeOrderedLessThanZeroImpl(I->getOperand(2), TLI, SignBitOnly,
3058  Depth + 1);
3059  }
3060  break;
3061  }
3062  return false;
3063 }
3064 
3066  const TargetLibraryInfo *TLI) {
3067  return cannotBeOrderedLessThanZeroImpl(V, TLI, false, 0);
3068 }
3069 
3071  return cannotBeOrderedLessThanZeroImpl(V, TLI, true, 0);
3072 }
3073 
3075  unsigned Depth) {
3076  assert(V->getType()->isFPOrFPVectorTy() && "Querying for NaN on non-FP type");
3077 
3078  // If we're told that NaNs won't happen, assume they won't.
3079  if (auto *FPMathOp = dyn_cast<FPMathOperator>(V))
3080  if (FPMathOp->hasNoNaNs())
3081  return true;
3082 
3083  // Handle scalar constants.
3084  if (auto *CFP = dyn_cast<ConstantFP>(V))
3085  return !CFP->isNaN();
3086 
3087  if (Depth == MaxDepth)
3088  return false;
3089 
3090  if (auto *Inst = dyn_cast<Instruction>(V)) {
3091  switch (Inst->getOpcode()) {
3092  case Instruction::FAdd:
3093  case Instruction::FMul:
3094  case Instruction::FSub:
3095  case Instruction::FDiv:
3096  case Instruction::FRem: {
3097  // TODO: Need isKnownNeverInfinity
3098  return false;
3099  }
3100  case Instruction::Select: {
3101  return isKnownNeverNaN(Inst->getOperand(1), TLI, Depth + 1) &&
3102  isKnownNeverNaN(Inst->getOperand(2), TLI, Depth + 1);
3103  }
3104  case Instruction::SIToFP:
3105  case Instruction::UIToFP:
3106  return true;
3107  case Instruction::FPTrunc:
3108  case Instruction::FPExt:
3109  return isKnownNeverNaN(Inst->getOperand(0), TLI, Depth + 1);
3110  default:
3111  break;
3112  }
3113  }
3114 
3115  if (const auto *II = dyn_cast<IntrinsicInst>(V)) {
3116  switch (II->getIntrinsicID()) {
3117  case Intrinsic::canonicalize:
3118  case Intrinsic::fabs:
3119  case Intrinsic::copysign:
3120  case Intrinsic::exp:
3121  case Intrinsic::exp2:
3122  case Intrinsic::floor:
3123  case Intrinsic::ceil:
3124  case Intrinsic::trunc:
3125  case Intrinsic::rint:
3126  case Intrinsic::nearbyint:
3127  case Intrinsic::round:
3128  return isKnownNeverNaN(II->getArgOperand(0), TLI, Depth + 1);
3129  case Intrinsic::sqrt:
3130  return isKnownNeverNaN(II->getArgOperand(0), TLI, Depth + 1) &&
3131  CannotBeOrderedLessThanZero(II->getArgOperand(0), TLI);
3132  default:
3133  return false;
3134  }
3135  }
3136 
3137  // Bail out for constant expressions, but try to handle vector constants.
3138  if (!V->getType()->isVectorTy() || !isa<Constant>(V))
3139  return false;
3140 
3141  // For vectors, verify that each element is not NaN.
3142  unsigned NumElts = V->getType()->getVectorNumElements();
3143  for (unsigned i = 0; i != NumElts; ++i) {
3144  Constant *Elt = cast<Constant>(V)->getAggregateElement(i);
3145  if (!Elt)
3146  return false;
3147  if (isa<UndefValue>(Elt))
3148  continue;
3149  auto *CElt = dyn_cast<ConstantFP>(Elt);
3150  if (!CElt || CElt->isNaN())
3151  return false;
3152  }
3153  // All elements were confirmed not-NaN or undefined.
3154  return true;
3155 }
3156 
3158 
3159  // All byte-wide stores are splatable, even of arbitrary variables.
3160  if (V->getType()->isIntegerTy(8))
3161  return V;
3162 
3163  LLVMContext &Ctx = V->getContext();
3164 
3165  // Undef don't care.
3166  auto *UndefInt8 = UndefValue::get(Type::getInt8Ty(Ctx));
3167  if (isa<UndefValue>(V))
3168  return UndefInt8;
3169 
3170  Constant *C = dyn_cast<Constant>(V);
3171  if (!C) {
3172  // Conceptually, we could handle things like:
3173  // %a = zext i8 %X to i16
3174  // %b = shl i16 %a, 8
3175  // %c = or i16 %a, %b
3176  // but until there is an example that actually needs this, it doesn't seem
3177  // worth worrying about.
3178  return nullptr;
3179  }
3180 
3181  // Handle 'null' ConstantArrayZero etc.
3182  if (C->isNullValue())
3184 
3185  // Constant floating-point values can be handled as integer values if the
3186  // corresponding integer value is "byteable". An important case is 0.0.
3187  if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
3188  Type *Ty = nullptr;
3189  if (CFP->getType()->isHalfTy())
3190  Ty = Type::getInt16Ty(Ctx);
3191  else if (CFP->getType()->isFloatTy())
3192  Ty = Type::getInt32Ty(Ctx);
3193  else if (CFP->getType()->isDoubleTy())
3194  Ty = Type::getInt64Ty(Ctx);
3195  // Don't handle long double formats, which have strange constraints.
3196  return Ty ? isBytewiseValue(ConstantExpr::getBitCast(CFP, Ty)) : nullptr;
3197  }
3198 
3199  // We can handle constant integers that are multiple of 8 bits.
3200  if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) {
3201  if (CI->getBitWidth() % 8 == 0) {
3202  assert(CI->getBitWidth() > 8 && "8 bits should be handled above!");
3203  if (!CI->getValue().isSplat(8))
3204  return nullptr;
3205  return ConstantInt::get(Ctx, CI->getValue().trunc(8));
3206  }
3207  }
3208 
3209  auto Merge = [&](Value *LHS, Value *RHS) -> Value * {
3210  if (LHS == RHS)
3211  return LHS;
3212  if (!LHS || !RHS)
3213  return nullptr;
3214  if (LHS == UndefInt8)
3215  return RHS;
3216  if (RHS == UndefInt8)
3217  return LHS;
3218  return nullptr;
3219  };
3220 
3221  if (ConstantDataSequential *CA = dyn_cast<ConstantDataSequential>(C)) {
3222  Value *Val = UndefInt8;
3223  for (unsigned I = 0, E = CA->getNumElements(); I != E; ++I)
3224  if (!(Val = Merge(Val, isBytewiseValue(CA->getElementAsConstant(I)))))
3225  return nullptr;
3226  return Val;
3227  }
3228 
3229  if (isa<ConstantVector>(C)) {
3230  Constant *Splat = cast<ConstantVector>(C)->getSplatValue();
3231  return Splat ? isBytewiseValue(Splat) : nullptr;
3232  }
3233 
3234  if (isa<ConstantArray>(C) || isa<ConstantStruct>(C)) {
3235  Value *Val = UndefInt8;
3236  for (unsigned I = 0, E = C->getNumOperands(); I != E; ++I)
3237  if (!(Val = Merge(Val, isBytewiseValue(C->getOperand(I)))))
3238  return nullptr;
3239  return Val;
3240  }
3241 
3242  // Don't try to handle the handful of other constants.
3243  return nullptr;
3244 }
3245 
3246 // This is the recursive version of BuildSubAggregate. It takes a few different
3247 // arguments. Idxs is the index within the nested struct From that we are
3248 // looking at now (which is of type IndexedType). IdxSkip is the number of
3249 // indices from Idxs that should be left out when inserting into the resulting
3250 // struct. To is the result struct built so far, new insertvalue instructions
3251 // build on that.
3252 static Value *BuildSubAggregate(Value *From, Value* To, Type *IndexedType,
3254  unsigned IdxSkip,
3255  Instruction *InsertBefore) {
3256  StructType *STy = dyn_cast<StructType>(IndexedType);
3257  if (STy) {
3258  // Save the original To argument so we can modify it
3259  Value *OrigTo = To;
3260  // General case, the type indexed by Idxs is a struct
3261  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
3262  // Process each struct element recursively
3263  Idxs.push_back(i);
3264  Value *PrevTo = To;
3265  To = BuildSubAggregate(From, To, STy->getElementType(i), Idxs, IdxSkip,
3266  InsertBefore);
3267  Idxs.pop_back();
3268  if (!To) {
3269  // Couldn't find any inserted value for this index? Cleanup
3270  while (PrevTo != OrigTo) {
3271  InsertValueInst* Del = cast<InsertValueInst>(PrevTo);
3272  PrevTo = Del->getAggregateOperand();
3273  Del->eraseFromParent();
3274  }
3275  // Stop processing elements
3276  break;
3277  }
3278  }
3279  // If we successfully found a value for each of our subaggregates
3280  if (To)
3281  return To;
3282  }
3283  // Base case, the type indexed by SourceIdxs is not a struct, or not all of
3284  // the struct's elements had a value that was inserted directly. In the latter
3285  // case, perhaps we can't determine each of the subelements individually, but
3286  // we might be able to find the complete struct somewhere.
3287 
3288  // Find the value that is at that particular spot
3289  Value *V = FindInsertedValue(From, Idxs);
3290 
3291  if (!V)
3292  return nullptr;
3293 
3294  // Insert the value in the new (sub) aggregate
3295  return InsertValueInst::Create(To, V, makeArrayRef(Idxs).slice(IdxSkip),
3296  "tmp", InsertBefore);
3297 }
3298 
3299 // This helper takes a nested struct and extracts a part of it (which is again a
3300 // struct) into a new value. For example, given the struct:
3301 // { a, { b, { c, d }, e } }
3302 // and the indices "1, 1" this returns
3303 // { c, d }.
3304 //
3305 // It does this by inserting an insertvalue for each element in the resulting
3306 // struct, as opposed to just inserting a single struct. This will only work if
3307 // each of the elements of the substruct are known (ie, inserted into From by an
3308 // insertvalue instruction somewhere).
3309 //
3310 // All inserted insertvalue instructions are inserted before InsertBefore
3312  Instruction *InsertBefore) {
3313  assert(InsertBefore && "Must have someplace to insert!");
3314  Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(),
3315  idx_range);
3316  Value *To = UndefValue::get(IndexedType);
3317  SmallVector<unsigned, 10> Idxs(idx_range.begin(), idx_range.end());
3318  unsigned IdxSkip = Idxs.size();
3319 
3320  return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore);
3321 }
3322 
3323 /// Given an aggregate and a sequence of indices, see if the scalar value
3324 /// indexed is already around as a register, for example if it was inserted
3325 /// directly into the aggregate.
3326 ///
3327 /// If InsertBefore is not null, this function will duplicate (modified)
3328 /// insertvalues when a part of a nested struct is extracted.
3330  Instruction *InsertBefore) {
3331  // Nothing to index? Just return V then (this is useful at the end of our
3332  // recursion).
3333  if (idx_range.empty())
3334  return V;
3335  // We have indices, so V should have an indexable type.
3336  assert((V->getType()->isStructTy() || V->getType()->isArrayTy()) &&
3337  "Not looking at a struct or array?");
3338  assert(ExtractValueInst::getIndexedType(V->getType(), idx_range) &&
3339  "Invalid indices for type?");
3340 
3341  if (Constant *C = dyn_cast<Constant>(V)) {
3342  C = C->getAggregateElement(idx_range[0]);
3343  if (!C) return nullptr;
3344  return FindInsertedValue(C, idx_range.slice(1), InsertBefore);
3345  }
3346 
3347  if (InsertValueInst *I = dyn_cast<InsertValueInst>(V)) {
3348  // Loop the indices for the insertvalue instruction in parallel with the
3349  // requested indices
3350  const unsigned *req_idx = idx_range.begin();
3351  for (const unsigned *i = I->idx_begin(), *e = I->idx_end();
3352  i != e; ++i, ++req_idx) {
3353  if (req_idx == idx_range.end()) {
3354  // We can't handle this without inserting insertvalues
3355  if (!InsertBefore)
3356  return nullptr;
3357 
3358  // The requested index identifies a part of a nested aggregate. Handle
3359  // this specially. For example,
3360  // %A = insertvalue { i32, {i32, i32 } } undef, i32 10, 1, 0
3361  // %B = insertvalue { i32, {i32, i32 } } %A, i32 11, 1, 1
3362  // %C = extractvalue {i32, { i32, i32 } } %B, 1
3363  // This can be changed into
3364  // %A = insertvalue {i32, i32 } undef, i32 10, 0
3365  // %C = insertvalue {i32, i32 } %A, i32 11, 1
3366  // which allows the unused 0,0 element from the nested struct to be
3367  // removed.
3368  return BuildSubAggregate(V, makeArrayRef(idx_range.begin(), req_idx),
3369  InsertBefore);
3370  }
3371 
3372  // This insert value inserts something else than what we are looking for.
3373  // See if the (aggregate) value inserted into has the value we are
3374  // looking for, then.
3375  if (*req_idx != *i)
3376  return FindInsertedValue(I->getAggregateOperand(), idx_range,
3377  InsertBefore);
3378  }
3379  // If we end up here, the indices of the insertvalue match with those
3380  // requested (though possibly only partially). Now we recursively look at
3381  // the inserted value, passing any remaining indices.
3382  return FindInsertedValue(I->getInsertedValueOperand(),
3383  makeArrayRef(req_idx, idx_range.end()),
3384  InsertBefore);
3385  }
3386 
3387  if (ExtractValueInst *I = dyn_cast<ExtractValueInst>(V)) {
3388  // If we're extracting a value from an aggregate that was extracted from
3389  // something else, we can extract from that something else directly instead.
3390  // However, we will need to chain I's indices with the requested indices.
3391 
3392  // Calculate the number of indices required
3393  unsigned size = I->getNumIndices() + idx_range.size();
3394  // Allocate some space to put the new indices in
3396  Idxs.reserve(size);
3397  // Add indices from the extract value instruction
3398  Idxs.append(I->idx_begin(), I->idx_end());
3399 
3400  // Add requested indices
3401  Idxs.append(idx_range.begin(), idx_range.end());
3402 
3403  assert(Idxs.size() == size
3404  && "Number of indices added not correct?");
3405 
3406  return FindInsertedValue(I->getAggregateOperand(), Idxs, InsertBefore);
3407  }
3408  // Otherwise, we don't know (such as, extracting from a function return value
3409  // or load instruction)
3410  return nullptr;
3411 }
3412 
3413 /// Analyze the specified pointer to see if it can be expressed as a base
3414 /// pointer plus a constant offset. Return the base and offset to the caller.
3416  const DataLayout &DL) {
3417  unsigned BitWidth = DL.getIndexTypeSizeInBits(Ptr->getType());
3418  APInt ByteOffset(BitWidth, 0);
3419 
3420  // We walk up the defs but use a visited set to handle unreachable code. In
3421  // that case, we stop after accumulating the cycle once (not that it
3422  // matters).
3423  SmallPtrSet<Value *, 16> Visited;
3424  while (Visited.insert(Ptr).second) {
3425  if (Ptr->getType()->isVectorTy())
3426  break;
3427 
3428  if (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) {
3429  // If one of the values we have visited is an addrspacecast, then
3430  // the pointer type of this GEP may be different from the type
3431  // of the Ptr parameter which was passed to this function. This
3432  // means when we construct GEPOffset, we need to use the size
3433  // of GEP's pointer type rather than the size of the original
3434  // pointer type.
3435  APInt GEPOffset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
3436  if (!GEP->accumulateConstantOffset(DL, GEPOffset))
3437  break;
3438 
3439  APInt OrigByteOffset(ByteOffset);
3440  ByteOffset += GEPOffset.sextOrTrunc(ByteOffset.getBitWidth());
3441  if (ByteOffset.getMinSignedBits() > 64) {
3442  // Stop traversal if the pointer offset wouldn't fit into int64_t
3443  // (this should be removed if Offset is updated to an APInt)
3444  ByteOffset = OrigByteOffset;
3445  break;
3446  }
3447 
3448  Ptr = GEP->getPointerOperand();
3449  } else if (Operator::getOpcode(Ptr) == Instruction::BitCast ||
3450  Operator::getOpcode(Ptr) == Instruction::AddrSpaceCast) {
3451  Ptr = cast<Operator>(Ptr)->getOperand(0);
3452  } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Ptr)) {
3453  if (GA->isInterposable())
3454  break;
3455  Ptr = GA->getAliasee();
3456  } else {
3457  break;
3458  }
3459  }
3460  Offset = ByteOffset.getSExtValue();
3461  return Ptr;
3462 }
3463 
3465  unsigned CharSize) {
3466  // Make sure the GEP has exactly three arguments.
3467  if (GEP->getNumOperands() != 3)
3468  return false;
3469 
3470  // Make sure the index-ee is a pointer to array of \p CharSize integers.
3471  // CharSize.
3473  if (!AT || !AT->getElementType()->isIntegerTy(CharSize))
3474  return false;
3475 
3476  // Check to make sure that the first operand of the GEP is an integer and
3477  // has value 0 so that we are sure we're indexing into the initializer.
3478  const ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1));
3479  if (!FirstIdx || !FirstIdx->isZero())
3480  return false;
3481 
3482  return true;
3483 }
3484 
3486  ConstantDataArraySlice &Slice,
3487  unsigned ElementSize, uint64_t Offset) {
3488  assert(V);
3489 
3490  // Look through bitcast instructions and geps.
3491  V = V->stripPointerCasts();
3492 
3493  // If the value is a GEP instruction or constant expression, treat it as an
3494  // offset.
3495  if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
3496  // The GEP operator should be based on a pointer to string constant, and is
3497  // indexing into the string constant.
3498  if (!isGEPBasedOnPointerToString(GEP, ElementSize))
3499  return false;
3500 
3501  // If the second index isn't a ConstantInt, then this is a variable index
3502  // into the array. If this occurs, we can't say anything meaningful about
3503  // the string.
3504  uint64_t StartIdx = 0;
3505  if (const ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
3506  StartIdx = CI->getZExtValue();
3507  else
3508  return false;
3509  return getConstantDataArrayInfo(GEP->getOperand(0), Slice, ElementSize,
3510  StartIdx + Offset);
3511  }
3512 
3513  // The GEP instruction, constant or instruction, must reference a global
3514  // variable that is a constant and is initialized. The referenced constant
3515  // initializer is the array that we'll use for optimization.
3516  const GlobalVariable *GV = dyn_cast<GlobalVariable>(V);
3517  if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())
3518  return false;
3519 
3520  const ConstantDataArray *Array;
3521  ArrayType *ArrayTy;
3522  if (GV->getInitializer()->isNullValue()) {
3523  Type *GVTy = GV->getValueType();
3524  if ( (ArrayTy = dyn_cast<ArrayType>(GVTy)) ) {
3525  // A zeroinitializer for the array; there is no ConstantDataArray.
3526  Array = nullptr;
3527  } else {
3528  const DataLayout &DL = GV->getParent()->getDataLayout();
3529  uint64_t SizeInBytes = DL.getTypeStoreSize(GVTy);
3530  uint64_t Length = SizeInBytes / (ElementSize / 8);
3531  if (Length <= Offset)
3532  return false;
3533 
3534  Slice.Array = nullptr;
3535  Slice.Offset = 0;
3536  Slice.Length = Length - Offset;
3537  return true;
3538  }
3539  } else {
3540  // This must be a ConstantDataArray.
3541  Array = dyn_cast<ConstantDataArray>(GV->getInitializer());
3542  if (!Array)
3543  return false;
3544  ArrayTy = Array->getType();
3545  }
3546  if (!ArrayTy->getElementType()->isIntegerTy(ElementSize))
3547  return false;
3548 
3549  uint64_t NumElts = ArrayTy->getArrayNumElements();
3550  if (Offset > NumElts)
3551  return false;
3552 
3553  Slice.Array = Array;
3554  Slice.Offset = Offset;
3555  Slice.Length = NumElts - Offset;
3556  return true;
3557 }
3558 
3559 /// This function computes the length of a null-terminated C string pointed to
3560 /// by V. If successful, it returns true and returns the string in Str.
3561 /// If unsuccessful, it returns false.
3563  uint64_t Offset, bool TrimAtNul) {
3564  ConstantDataArraySlice Slice;
3565  if (!getConstantDataArrayInfo(V, Slice, 8, Offset))
3566  return false;
3567 
3568  if (Slice.Array == nullptr) {
3569  if (TrimAtNul) {
3570  Str = StringRef();
3571  return true;
3572  }
3573  if (Slice.Length == 1) {
3574  Str = StringRef("", 1);
3575  return true;
3576  }
3577  // We cannot instantiate a StringRef as we do not have an appropriate string
3578  // of 0s at hand.
3579  return false;
3580  }
3581 
3582  // Start out with the entire array in the StringRef.
3583  Str = Slice.Array->getAsString();
3584  // Skip over 'offset' bytes.
3585  Str = Str.substr(Slice.Offset);
3586 
3587  if (TrimAtNul) {
3588  // Trim off the \0 and anything after it. If the array is not nul
3589  // terminated, we just return the whole end of string. The client may know
3590  // some other way that the string is length-bound.
3591  Str = Str.substr(0, Str.find('\0'));
3592  }
3593  return true;
3594 }
3595 
3596 // These next two are very similar to the above, but also look through PHI
3597 // nodes.
3598 // TODO: See if we can integrate these two together.
3599 
3600 /// If we can compute the length of the string pointed to by
3601 /// the specified pointer, return 'len+1'. If we can't, return 0.
3602 static uint64_t GetStringLengthH(const Value *V,
3604  unsigned CharSize) {
3605  // Look through noop bitcast instructions.
3606  V = V->stripPointerCasts();
3607 
3608  // If this is a PHI node, there are two cases: either we have already seen it
3609  // or we haven't.
3610  if (const PHINode *PN = dyn_cast<PHINode>(V)) {
3611  if (!PHIs.insert(PN).second)
3612  return ~0ULL; // already in the set.
3613 
3614  // If it was new, see if all the input strings are the same length.
3615  uint64_t LenSoFar = ~0ULL;
3616  for (Value *IncValue : PN->incoming_values()) {
3617  uint64_t Len = GetStringLengthH(IncValue, PHIs, CharSize);
3618  if (Len == 0) return 0; // Unknown length -> unknown.
3619 
3620  if (Len == ~0ULL) continue;
3621 
3622  if (Len != LenSoFar && LenSoFar != ~0ULL)
3623  return 0; // Disagree -> unknown.
3624  LenSoFar = Len;
3625  }
3626 
3627  // Success, all agree.
3628  return LenSoFar;
3629  }
3630 
3631  // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y)
3632  if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
3633  uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs, CharSize);
3634  if (Len1 == 0) return 0;
3635  uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs, CharSize);
3636  if (Len2 == 0) return 0;
3637  if (Len1 == ~0ULL) return Len2;
3638  if (Len2 == ~0ULL) return Len1;
3639  if (Len1 != Len2) return 0;
3640  return Len1;
3641  }
3642 
3643  // Otherwise, see if we can read the string.
3644  ConstantDataArraySlice Slice;
3645  if (!getConstantDataArrayInfo(V, Slice, CharSize))
3646  return 0;
3647 
3648  if (Slice.Array == nullptr)
3649  return 1;
3650 
3651  // Search for nul characters
3652  unsigned NullIndex = 0;
3653  for (unsigned E = Slice.Length; NullIndex < E; ++NullIndex) {
3654  if (Slice.Array->getElementAsInteger(Slice.Offset + NullIndex) == 0)
3655  break;
3656  }
3657 
3658  return NullIndex + 1;
3659 }
3660 
3661 /// If we can compute the length of the string pointed to by
3662 /// the specified pointer, return 'len+1'. If we can't, return 0.
3663 uint64_t llvm::GetStringLength(const Value *V, unsigned CharSize) {
3664  if (!V->getType()->isPointerTy())
3665  return 0;
3666 
3668  uint64_t Len = GetStringLengthH(V, PHIs, CharSize);
3669  // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return
3670  // an empty string as a length.
3671  return Len == ~0ULL ? 1 : Len;
3672 }
3673 
3675  assert(Call &&
3676  "getArgumentAliasingToReturnedPointer only works on nonnull calls");
3677  if (const Value *RV = Call->getReturnedArgOperand())
3678  return RV;
3679  // This can be used only as a aliasing property.
3681  return Call->getArgOperand(0);
3682  return nullptr;
3683 }
3684 
3686  const CallBase *Call) {
3687  return Call->getIntrinsicID() == Intrinsic::launder_invariant_group ||
3688  Call->getIntrinsicID() == Intrinsic::strip_invariant_group;
3689 }
3690 
3691 /// \p PN defines a loop-variant pointer to an object. Check if the
3692 /// previous iteration of the loop was referring to the same object as \p PN.
3694  const LoopInfo *LI) {
3695  // Find the loop-defined value.
3696  Loop *L = LI->getLoopFor(PN->getParent());
3697  if (PN->getNumIncomingValues() != 2)
3698  return true;
3699 
3700  // Find the value from previous iteration.
3701  auto *PrevValue = dyn_cast<Instruction>(PN->getIncomingValue(0));
3702  if (!PrevValue || LI->getLoopFor(PrevValue->getParent()) != L)
3703  PrevValue = dyn_cast<Instruction>(PN->getIncomingValue(1));
3704  if (!PrevValue || LI->getLoopFor(PrevValue->getParent()) != L)
3705  return true;
3706 
3707  // If a new pointer is loaded in the loop, the pointer references a different
3708  // object in every iteration. E.g.:
3709  // for (i)
3710  // int *p = a[i];
3711  // ...
3712  if (auto *Load = dyn_cast<LoadInst>(PrevValue))
3713  if (!L->isLoopInvariant(Load->getPointerOperand()))
3714  return false;
3715  return true;
3716 }
3717 
3719  unsigned MaxLookup) {
3720  if (!V->getType()->isPointerTy())
3721  return V;
3722  for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
3723  if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
3724  V = GEP->getPointerOperand();
3725  } else if (Operator::getOpcode(V) == Instruction::BitCast ||
3726  Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
3727  V = cast<Operator>(V)->getOperand(0);
3728  } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
3729  if (GA->isInterposable())
3730  return V;
3731  V = GA->getAliasee();
3732  } else if (isa<AllocaInst>(V)) {
3733  // An alloca can't be further simplified.
3734  return V;
3735  } else {
3736  if (auto *Call = dyn_cast<CallBase>(V)) {
3737  // CaptureTracking can know about special capturing properties of some
3738  // intrinsics like launder.invariant.group, that can't be expressed with
3739  // the attributes, but have properties like returning aliasing pointer.
3740  // Because some analysis may assume that nocaptured pointer is not
3741  // returned from some special intrinsic (because function would have to
3742  // be marked with returns attribute), it is crucial to use this function
3743  // because it should be in sync with CaptureTracking. Not using it may
3744  // cause weird miscompilations where 2 aliasing pointers are assumed to
3745  // noalias.
3746  if (auto *RP = getArgumentAliasingToReturnedPointer(Call)) {
3747  V = RP;
3748  continue;
3749  }
3750  }
3751 
3752  // See if InstructionSimplify knows any relevant tricks.
3753  if (Instruction *I = dyn_cast<Instruction>(V))
3754  // TODO: Acquire a DominatorTree and AssumptionCache and use them.
3755  if (Value *Simplified = SimplifyInstruction(I, {DL, I})) {
3756  V = Simplified;
3757  continue;
3758  }
3759 
3760  return V;
3761  }
3762  assert(V->getType()->isPointerTy() && "Unexpected operand type!");
3763  }
3764  return V;
3765 }
3766 
3768  const DataLayout &DL, LoopInfo *LI,
3769  unsigned MaxLookup) {
3770  SmallPtrSet<Value *, 4> Visited;
3771  SmallVector<Value *, 4> Worklist;
3772  Worklist.push_back(V);
3773  do {
3774  Value *P = Worklist.pop_back_val();
3775  P = GetUnderlyingObject(P, DL, MaxLookup);
3776 
3777  if (!Visited.insert(P).second)
3778  continue;
3779 
3780  if (SelectInst *SI = dyn_cast<SelectInst>(P)) {
3781  Worklist.push_back(SI->getTrueValue());
3782  Worklist.push_back(SI->getFalseValue());
3783  continue;
3784  }
3785 
3786  if (PHINode *PN = dyn_cast<PHINode>(P)) {
3787  // If this PHI changes the underlying object in every iteration of the
3788  // loop, don't look through it. Consider:
3789  // int **A;
3790  // for (i) {
3791  // Prev = Curr; // Prev = PHI (Prev_0, Curr)
3792  // Curr = A[i];
3793  // *Prev, *Curr;
3794  //
3795  // Prev is tracking Curr one iteration behind so they refer to different
3796  // underlying objects.
3797  if (!LI || !LI->isLoopHeader(PN->getParent()) ||
3799  for (Value *IncValue : PN->incoming_values())
3800  Worklist.push_back(IncValue);
3801  continue;
3802  }
3803 
3804  Objects.push_back(P);
3805  } while (!Worklist.empty());
3806 }
3807 
3808 /// This is the function that does the work of looking through basic
3809 /// ptrtoint+arithmetic+inttoptr sequences.
3810 static const Value *getUnderlyingObjectFromInt(const Value *V) {
3811  do {
3812  if (const Operator *U = dyn_cast<Operator>(V)) {
3813  // If we find a ptrtoint, we can transfer control back to the
3814  // regular getUnderlyingObjectFromInt.
3815  if (U->getOpcode() == Instruction::PtrToInt)
3816  return U->getOperand(0);
3817  // If we find an add of a constant, a multiplied value, or a phi, it's
3818  // likely that the other operand will lead us to the base
3819  // object. We don't have to worry about the case where the
3820  // object address is somehow being computed by the multiply,
3821  // because our callers only care when the result is an
3822  // identifiable object.
3823  if (U->getOpcode() != Instruction::Add ||
3824  (!isa<ConstantInt>(U->getOperand(1)) &&
3825  Operator::getOpcode(U->getOperand(1)) != Instruction::Mul &&
3826  !isa<PHINode>(U->getOperand(1))))
3827  return V;
3828  V = U->getOperand(0);
3829  } else {
3830  return V;
3831  }
3832  assert(V->getType()->isIntegerTy() && "Unexpected operand type!");
3833  } while (true);
3834 }
3835 
3836 /// This is a wrapper around GetUnderlyingObjects and adds support for basic
3837 /// ptrtoint+arithmetic+inttoptr sequences.
3838 /// It returns false if unidentified object is found in GetUnderlyingObjects.
3840  SmallVectorImpl<Value *> &Objects,
3841  const DataLayout &DL) {
3843  SmallVector<const Value *, 4> Working(1, V);
3844  do {
3845  V = Working.pop_back_val();
3846 
3848  GetUnderlyingObjects(const_cast<Value *>(V), Objs, DL);
3849 
3850  for (Value *V : Objs) {
3851  if (!Visited.insert(V).second)
3852  continue;
3853  if (Operator::getOpcode(V) == Instruction::IntToPtr) {
3854  const Value *O =
3855  getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0));
3856  if (O->getType()->isPointerTy()) {
3857  Working.push_back(O);
3858  continue;
3859  }
3860  }
3861  // If GetUnderlyingObjects fails to find an identifiable object,
3862  // getUnderlyingObjectsForCodeGen also fails for safety.
3863  if (!isIdentifiedObject(V)) {
3864  Objects.clear();
3865  return false;
3866  }
3867  Objects.push_back(const_cast<Value *>(V));
3868  }
3869  } while (!Working.empty());
3870  return true;
3871 }
3872 
3873 /// Return true if the only users of this pointer are lifetime markers.
3875  for (const User *U : V->users()) {
3876  const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U);
3877  if (!II) return false;
3878 
3879  if (!II->isLifetimeStartOrEnd())
3880  return false;
3881  }
3882  return true;
3883 }
3884 
3886  const Instruction *CtxI,
3887  const DominatorTree *DT) {
3888  const Operator *Inst = dyn_cast<Operator>(V);
3889  if (!Inst)
3890  return false;
3891 
3892  for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
3893  if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i)))
3894  if (C->canTrap())
3895  return false;
3896 
3897  switch (Inst->getOpcode()) {
3898  default:
3899  return true;
3900  case Instruction::UDiv:
3901  case Instruction::URem: {
3902  // x / y is undefined if y == 0.
3903  const APInt *V;
3904  if (match(Inst->getOperand(1), m_APInt(V)))
3905  return *V != 0;
3906  return false;
3907  }
3908  case Instruction::SDiv:
3909  case Instruction::SRem: {
3910  // x / y is undefined if y == 0 or x == INT_MIN and y == -1
3911  const APInt *Numerator, *Denominator;
3912  if (!match(Inst->getOperand(1), m_APInt(Denominator)))
3913  return false;
3914  // We cannot hoist this division if the denominator is 0.
3915  if (*Denominator == 0)
3916  return false;
3917  // It's safe to hoist if the denominator is not 0 or -1.
3918  if (*Denominator != -1)
3919  return true;
3920  // At this point we know that the denominator is -1. It is safe to hoist as
3921  // long we know that the numerator is not INT_MIN.
3922  if (match(Inst->getOperand(0), m_APInt(Numerator)))
3923  return !Numerator->isMinSignedValue();
3924  // The numerator *might* be MinSignedValue.
3925  return false;
3926  }
3927  case Instruction::Load: {
3928  const LoadInst *LI = cast<LoadInst>(Inst);
3929  if (!LI->isUnordered() ||
3930  // Speculative load may create a race that did not exist in the source.
3931  LI->getFunction()->hasFnAttribute(Attribute::SanitizeThread) ||
3932  // Speculative load may load data from dirty regions.
3933  LI->getFunction()->hasFnAttribute(Attribute::SanitizeAddress) ||
3934  LI->getFunction()->hasFnAttribute(Attribute::SanitizeHWAddress))
3935  return false;
3936  const DataLayout &DL = LI->getModule()->getDataLayout();
3938  LI->getAlignment(), DL, CtxI, DT);
3939  }
3940  case Instruction::Call: {
3941  auto *CI = cast<const CallInst>(Inst);
3942  const Function *Callee = CI->getCalledFunction();
3943 
3944  // The called function could have undefined behavior or side-effects, even
3945  // if marked readnone nounwind.
3946  return Callee && Callee->isSpeculatable();
3947  }
3948  case Instruction::VAArg:
3949  case Instruction::Alloca:
3950  case Instruction::Invoke:
3951  case Instruction::CallBr:
3952  case Instruction::PHI:
3953  case Instruction::Store:
3954  case Instruction::Ret:
3955  case Instruction::Br:
3956  case Instruction::IndirectBr:
3957  case Instruction::Switch:
3958  case Instruction::Unreachable:
3959  case Instruction::Fence:
3960  case Instruction::AtomicRMW:
3961  case Instruction::AtomicCmpXchg:
3962  case Instruction::LandingPad:
3963  case Instruction::Resume:
3964  case Instruction::CatchSwitch:
3965  case Instruction::CatchPad:
3966  case Instruction::CatchRet:
3967  case Instruction::CleanupPad:
3968  case Instruction::CleanupRet:
3969  return false; // Misc instructions which have effects
3970  }
3971 }
3972 
3975 }
3976 
3978  const Value *LHS, const Value *RHS, const DataLayout &DL,
3979  AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT,
3980  bool UseInstrInfo) {
3981  // Multiplying n * m significant bits yields a result of n + m significant
3982  // bits. If the total number of significant bits does not exceed the
3983  // result bit width (minus 1), there is no overflow.
3984  // This means if we have enough leading zero bits in the operands
3985  // we can guarantee that the result does not overflow.
3986  // Ref: "Hacker's Delight" by Henry Warren
3987  unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
3988  KnownBits LHSKnown(BitWidth);
3989  KnownBits RHSKnown(BitWidth);
3990  computeKnownBits(LHS, LHSKnown, DL, /*Depth=*/0, AC, CxtI, DT, nullptr,
3991  UseInstrInfo);
3992  computeKnownBits(RHS, RHSKnown, DL, /*Depth=*/0, AC, CxtI, DT, nullptr,
3993  UseInstrInfo);
3994  // Note that underestimating the number of zero bits gives a more
3995  // conservative answer.
3996  unsigned ZeroBits = LHSKnown.countMinLeadingZeros() +
3997  RHSKnown.countMinLeadingZeros();
3998  // First handle the easy case: if we have enough zero bits there's
3999  // definitely no overflow.
4000  if (ZeroBits >= BitWidth)
4002 
4003  // Get the largest possible values for each operand.
4004  APInt LHSMax = ~LHSKnown.Zero;
4005  APInt RHSMax = ~RHSKnown.Zero;
4006 
4007  // We know the multiply operation doesn't overflow if the maximum values for
4008  // each operand will not overflow after we multiply them together.
4009  bool MaxOverflow;
4010  (void)LHSMax.umul_ov(RHSMax, MaxOverflow);
4011  if (!MaxOverflow)
4013 
4014  // We know it always overflows if multiplying the smallest possible values for
4015  // the operands also results in overflow.
4016  bool MinOverflow;
4017  (void)LHSKnown.One.umul_ov(RHSKnown.One, MinOverflow);
4018  if (MinOverflow)
4020 
4022 }
4023 
4026  const DataLayout &DL, AssumptionCache *AC,
4027  const Instruction *CxtI,
4028  const DominatorTree *DT, bool UseInstrInfo) {
4029  // Multiplying n * m significant bits yields a result of n + m significant
4030  // bits. If the total number of significant bits does not exceed the
4031  // result bit width (minus 1), there is no overflow.
4032  // This means if we have enough leading sign bits in the operands
4033  // we can guarantee that the result does not overflow.
4034  // Ref: "Hacker's Delight" by Henry Warren
4035  unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
4036 
4037  // Note that underestimating the number of sign bits gives a more
4038  // conservative answer.
4039  unsigned SignBits = ComputeNumSignBits(LHS, DL, 0, AC, CxtI, DT) +
4040  ComputeNumSignBits(RHS, DL, 0, AC, CxtI, DT);
4041 
4042  // First handle the easy case: if we have enough sign bits there's
4043  // definitely no overflow.
4044  if (SignBits > BitWidth + 1)
4046 
4047  // There are two ambiguous cases where there can be no overflow:
4048  // SignBits == BitWidth + 1 and
4049  // SignBits == BitWidth
4050  // The second case is difficult to check, therefore we only handle the
4051  // first case.
4052  if (SignBits == BitWidth + 1) {
4053  // It overflows only when both arguments are negative and the true
4054  // product is exactly the minimum negative number.
4055  // E.g. mul i16 with 17 sign bits: 0xff00 * 0xff80 = 0x8000
4056  // For simplicity we just check if at least one side is not negative.
4057  KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT,
4058  nullptr, UseInstrInfo);
4059  KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT,
4060  nullptr, UseInstrInfo);
4061  if (LHSKnown.isNonNegative() || RHSKnown.isNonNegative())
4063  }
4065 }
4066 
4067 /// Convert ConstantRange OverflowResult into ValueTracking OverflowResult.
4069  switch (OR) {
4076  }
4077  llvm_unreachable("Unknown OverflowResult");
4078 }
4079 
4081  const Value *LHS, const Value *RHS, const DataLayout &DL,
4082  AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT,
4083  bool UseInstrInfo) {
4084  KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT,
4085  nullptr, UseInstrInfo);
4086  KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT,
4087  nullptr, UseInstrInfo);
4088  ConstantRange LHSRange =
4089  ConstantRange::fromKnownBits(LHSKnown, /*signed*/ false);
4090  ConstantRange RHSRange =
4091  ConstantRange::fromKnownBits(RHSKnown, /*signed*/ false);
4092  return mapOverflowResult(LHSRange.unsignedAddMayOverflow(RHSRange));
4093 }
4094 
4096  const Value *RHS,
4097  const AddOperator *Add,
4098  const DataLayout &DL,
4099  AssumptionCache *AC,
4100  const Instruction *CxtI,
4101  const DominatorTree *DT) {
4102  if (Add && Add->hasNoSignedWrap()) {
4104  }
4105 
4106  // If LHS and RHS each have at least two sign bits, the addition will look
4107  // like
4108  //
4109  // XX..... +
4110  // YY.....
4111  //
4112  // If the carry into the most significant position is 0, X and Y can't both
4113  // be 1 and therefore the carry out of the addition is also 0.
4114  //
4115  // If the carry into the most significant position is 1, X and Y can't both
4116  // be 0 and therefore the carry out of the addition is also 1.
4117  //
4118  // Since the carry into the most significant position is always equal to
4119  // the carry out of the addition, there is no signed overflow.
4120  if (ComputeNumSignBits(LHS, DL, 0, AC, CxtI, DT) > 1 &&
4121  ComputeNumSignBits(RHS, DL, 0, AC, CxtI, DT) > 1)
4123 
4124  KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT);
4125  KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT);
4126  ConstantRange LHSRange =
4127  ConstantRange::fromKnownBits(LHSKnown, /*signed*/ true);
4128  ConstantRange RHSRange =
4129  ConstantRange::fromKnownBits(RHSKnown, /*signed*/ true);
4130  OverflowResult OR =
4131  mapOverflowResult(LHSRange.signedAddMayOverflow(RHSRange));
4132  if (OR != OverflowResult::MayOverflow)
4133  return OR;
4134 
4135  // The remaining code needs Add to be available. Early returns if not so.
4136  if (!Add)
4138 
4139  // If the sign of Add is the same as at least one of the operands, this add
4140  // CANNOT overflow. This is particularly useful when the sum is
4141  // @llvm.assume'ed non-negative rather than proved so from analyzing its
4142  // operands.
4143  bool LHSOrRHSKnownNonNegative =
4144  (LHSKnown.isNonNegative() || RHSKnown.isNonNegative());
4145  bool LHSOrRHSKnownNegative =
4146  (LHSKnown.isNegative() || RHSKnown.isNegative());
4147  if (LHSOrRHSKnownNonNegative || LHSOrRHSKnownNegative) {
4148  KnownBits AddKnown = computeKnownBits(Add, DL, /*Depth=*/0, AC, CxtI, DT);
4149  if ((AddKnown.isNonNegative() && LHSOrRHSKnownNonNegative) ||
4150  (AddKnown.isNegative() && LHSOrRHSKnownNegative)) {
4152  }
4153  }
4154 
4156 }
4157 
4159  const Value *RHS,
4160  const DataLayout &DL,
4161  AssumptionCache *AC,
4162  const Instruction *CxtI,
4163  const DominatorTree *DT) {
4164  KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT);
4165  KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT);
4166  ConstantRange LHSRange =
4167  ConstantRange::fromKnownBits(LHSKnown, /*signed*/ false);
4168  ConstantRange RHSRange =
4169  ConstantRange::fromKnownBits(RHSKnown, /*signed*/ false);
4170  return mapOverflowResult(LHSRange.unsignedSubMayOverflow(RHSRange));
4171 }
4172 
4174  const Value *RHS,
4175  const DataLayout &DL,
4176  AssumptionCache *AC,
4177  const Instruction *CxtI,
4178  const DominatorTree *DT) {
4179  // If LHS and RHS each have at least two sign bits, the subtraction
4180  // cannot overflow.
4181  if (ComputeNumSignBits(LHS, DL, 0, AC, CxtI, DT) > 1 &&
4182  ComputeNumSignBits(RHS, DL, 0, AC, CxtI, DT) > 1)
4184 
4185  KnownBits LHSKnown = computeKnownBits(LHS, DL, 0, AC, CxtI, DT);
4186 
4187  KnownBits RHSKnown = computeKnownBits(RHS, DL, 0, AC, CxtI, DT);
4188 
4189  // Subtraction of two 2's complement numbers having identical signs will
4190  // never overflow.
4191  if ((LHSKnown.isNegative() && RHSKnown.isNegative()) ||
4192  (LHSKnown.isNonNegative() && RHSKnown.isNonNegative()))
4194 
4195  // TODO: implement logic similar to checkRippleForAdd
4197 }
4198 
4200  const DominatorTree &DT) {
4201 #ifndef NDEBUG
4202  auto IID = II->getIntrinsicID();
4203  assert((IID == Intrinsic::sadd_with_overflow ||
4204  IID == Intrinsic::uadd_with_overflow ||
4205  IID == Intrinsic::ssub_with_overflow ||
4206  IID == Intrinsic::usub_with_overflow ||
4207  IID == Intrinsic::smul_with_overflow ||
4208  IID == Intrinsic::umul_with_overflow) &&
4209  "Not an overflow intrinsic!");
4210 #endif
4211 
4212  SmallVector<const BranchInst *, 2> GuardingBranches;
4214 
4215  for (const User *U : II->users()) {
4216  if (const auto *EVI = dyn_cast<ExtractValueInst>(U)) {
4217  assert(EVI->getNumIndices() == 1 && "Obvious from CI's type");
4218 
4219  if (EVI->getIndices()[0] == 0)
4220  Results.push_back(EVI);
4221  else {
4222  assert(EVI->getIndices()[0] == 1 && "Obvious from CI's type");
4223 
4224  for (const auto *U : EVI->users())
4225  if (const auto *B = dyn_cast<BranchInst>(U)) {
4226  assert(B->isConditional() && "How else is it using an i1?");
4227  GuardingBranches.push_back(B);
4228  }
4229  }
4230  } else {
4231  // We are using the aggregate directly in a way we don't want to analyze
4232  // here (storing it to a global, say).
4233  return false;
4234  }
4235  }
4236 
4237  auto AllUsesGuardedByBranch = [&](const BranchInst *BI) {
4238  BasicBlockEdge NoWrapEdge(BI->getParent(), BI->getSuccessor(1));
4239  if (!NoWrapEdge.isSingleEdge())
4240  return false;
4241 
4242  // Check if all users of the add are provably no-wrap.
4243  for (const auto *Result : Results) {
4244  // If the extractvalue itself is not executed on overflow, the we don't
4245  // need to check each use separately, since domination is transitive.
4246  if (DT.dominates(NoWrapEdge, Result->getParent()))
4247  continue;
4248 
4249  for (auto &RU : Result->uses())
4250  if (!DT.dominates(NoWrapEdge, RU))
4251  return false;
4252  }
4253 
4254  return true;
4255  };
4256 
4257  return llvm::any_of(GuardingBranches, AllUsesGuardedByBranch);
4258 }
4259 
4260 
4262  const DataLayout &DL,
4263  AssumptionCache *AC,
4264  const Instruction *CxtI,
4265  const DominatorTree *DT) {
4267  Add, DL, AC, CxtI, DT);
4268 }
4269 
4271  const Value *RHS,
4272  const DataLayout &DL,
4273  AssumptionCache *AC,
4274  const Instruction *CxtI,
4275  const DominatorTree *DT) {
4276  return ::computeOverflowForSignedAdd(LHS, RHS, nullptr, DL, AC, CxtI, DT);
4277 }
4278 
4280  // A memory operation returns normally if it isn't volatile. A volatile
4281  // operation is allowed to trap.
4282  //
4283  // An atomic operation isn't guaranteed to return in a reasonable amount of
4284  // time because it's possible for another thread to interfere with it for an
4285  // arbitrary length of time, but programs aren't allowed to rely on that.
4286  if (const LoadInst *LI = dyn_cast<LoadInst>(I))
4287  return !LI->isVolatile();
4288  if (const StoreInst *SI = dyn_cast<StoreInst>(I))
4289  return !SI->isVolatile();
4290  if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(I))
4291  return !CXI->isVolatile();
4292  if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I))
4293  return !RMWI->isVolatile();
4294  if (const MemIntrinsic *MII = dyn_cast<MemIntrinsic>(I))
4295  return !MII->isVolatile();
4296 
4297  // If there is no successor, then execution can't transfer to it.
4298  if (const auto *CRI = dyn_cast<CleanupReturnInst>(I))
4299  return !CRI->unwindsToCaller();
4300  if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(I))
4301  return !CatchSwitch->unwindsToCaller();
4302  if (isa<ResumeInst>(I))
4303  return false;
4304  if (isa<ReturnInst>(I))
4305  return false;
4306  if (isa<UnreachableInst>(I))
4307  return false;
4308 
4309  // Calls can throw, or contain an infinite loop, or kill the process.
4310  if (auto CS = ImmutableCallSite(I)) {
4311  // Call sites that throw have implicit non-local control flow.
4312  if (!CS.doesNotThrow())
4313  return false;
4314 
4315  // Non-throwing call sites can loop infinitely, call exit/pthread_exit
4316  // etc. and thus not return. However, LLVM already assumes that
4317  //
4318  // - Thread exiting actions are modeled as writes to memory invisible to
4319  // the program.
4320  //
4321  // - Loops that don't have side effects (side effects are volatile/atomic
4322  // stores and IO) always terminate (see http://llvm.org/PR965).
4323  // Furthermore IO itself is also modeled as writes to memory invisible to
4324  // the program.
4325  //
4326  // We rely on those assumptions here, and use the memory effects of the call
4327  // target as a proxy for checking that it always returns.
4328 
4329  // FIXME: This isn't aggressive enough; a call which only writes to a global
4330  // is guaranteed to return.
4331  return CS.onlyReadsMemory() || CS.onlyAccessesArgMemory() ||
4332  match(I, m_Intrinsic<Intrinsic::assume>()) ||
4333  match(I, m_Intrinsic<Intrinsic::sideeffect>()) ||
4334  match(I, m_Intrinsic<Intrinsic::experimental_widenable_condition>());
4335  }
4336 
4337  // Other instructions return normally.
4338  return true;
4339 }
4340 
4342  // TODO: This is slightly conservative for invoke instruction since exiting
4343  // via an exception *is* normal control for them.
4344  for (auto I = BB->begin(), E = BB->end(); I != E; ++I)
4346  return false;
4347  return true;
4348 }
4349 
4351  const Loop *L) {
4352  // The loop header is guaranteed to be executed for every iteration.
4353  //
4354  // FIXME: Relax this constraint to cover all basic blocks that are
4355  // guaranteed to be executed at every iteration.
4356  if (I->getParent() != L->getHeader()) return false;
4357 
4358  for (const Instruction &LI : *L->getHeader()) {
4359  if (&LI == I) return true;
4360  if (!isGuaranteedToTransferExecutionToSuccessor(&LI)) return false;
4361  }
4362  llvm_unreachable("Instruction not contained in its own parent basic block.");
4363 }
4364 
4366  switch (I->getOpcode()) {
4367  case Instruction::Add:
4368  case Instruction::Sub:
4369  case Instruction::Xor:
4370  case Instruction::Trunc:
4371  case Instruction::BitCast:
4372  case Instruction::AddrSpaceCast:
4373  case Instruction::Mul:
4374  case Instruction::Shl:
4375  case Instruction::GetElementPtr:
4376  // These operations all propagate poison unconditionally. Note that poison
4377  // is not any particular value, so xor or subtraction of poison with
4378  // itself still yields poison, not zero.
4379  return true;
4380 
4381  case Instruction::AShr:
4382  case Instruction::SExt:
4383  // For these operations, one bit of the input is replicated across
4384  // multiple output bits. A replicated poison bit is still poison.
4385  return true;
4386 
4387  case Instruction::ICmp:
4388  // Comparing poison with any value yields poison. This is why, for
4389  // instance, x s< (x +nsw 1) can be folded to true.
4390  return true;
4391 
4392  default:
4393  return false;
4394  }
4395 }
4396 
4398  switch (I->getOpcode()) {
4399  case Instruction::Store:
4400  return cast<StoreInst>(I)->getPointerOperand();
4401 
4402  case Instruction::Load:
4403  return cast<LoadInst>(I)->getPointerOperand();
4404 
4405  case Instruction::AtomicCmpXchg:
4406  return cast<AtomicCmpXchgInst>(I)->getPointerOperand();
4407 
4408  case Instruction::AtomicRMW:
4409  return cast<AtomicRMWInst>(I)->getPointerOperand();
4410 
4411  case Instruction::UDiv:
4412  case Instruction::SDiv:
4413  case Instruction::URem:
4414  case Instruction::SRem:
4415  return I->getOperand(1);
4416 
4417  default:
4418  return nullptr;
4419  }
4420 }
4421 
4423  // We currently only look for uses of poison values within the same basic
4424  // block, as that makes it easier to guarantee that the uses will be
4425  // executed given that PoisonI is executed.
4426  //
4427  // FIXME: Expand this to consider uses beyond the same basic block. To do
4428  // this, look out for the distinction between post-dominance and strong
4429  // post-dominance.
4430  const BasicBlock *BB = PoisonI->getParent();
4431 
4432  // Set of instructions that we have proved will yield poison if PoisonI
4433  // does.
4434  SmallSet<const Value *, 16> YieldsPoison;
4436  YieldsPoison.insert(PoisonI);
4437  Visited.insert(PoisonI->getParent());
4438 
4439  BasicBlock::const_iterator Begin = PoisonI->getIterator(), End = BB->end();
4440 
4441  unsigned Iter = 0;
4442  while (Iter++ < MaxDepth) {
4443  for (auto &I : make_range(Begin, End)) {
4444  if (&I != PoisonI) {
4445  const Value *NotPoison = getGuaranteedNonFullPoisonOp(&I);
4446  if (NotPoison != nullptr && YieldsPoison.count(NotPoison))
4447  return true;
4449  return false;
4450  }
4451 
4452  // Mark poison that propagates from I through uses of I.
4453  if (YieldsPoison.count(&I)) {
4454  for (const User *User : I.users()) {
4455  const Instruction *UserI = cast<Instruction>(User);
4456  if (propagatesFullPoison(UserI))
4457  YieldsPoison.insert(User);
4458  }
4459  }
4460  }
4461 
4462  if (auto *NextBB = BB->getSingleSuccessor()) {
4463  if (Visited.insert(NextBB).second) {
4464  BB = NextBB;
4465  Begin = BB->getFirstNonPHI()->getIterator();
4466  End = BB->end();
4467  continue;
4468  }
4469  }
4470 
4471  break;
4472  }
4473  return false;
4474 }
4475 
4476 static bool isKnownNonNaN(const Value *V, FastMathFlags FMF) {
4477  if (FMF.noNaNs())
4478  return true;
4479 
4480  if (auto *C = dyn_cast<ConstantFP>(V))
4481  return !C->isNaN();
4482 
4483  if (auto *C = dyn_cast<ConstantDataVector>(V)) {
4484  if (!C->getElementType()->isFloatingPointTy())
4485  return false;
4486  for (unsigned I = 0, E = C->getNumElements(); I < E; ++I) {
4487  if (C->getElementAsAPFloat(I).isNaN())
4488  return false;
4489  }
4490  return true;
4491  }
4492 
4493  return false;
4494 }
4495 
4496 static bool isKnownNonZero(const Value *V) {
4497  if (auto *C = dyn_cast<ConstantFP>(V))
4498  return !C->isZero();
4499 
4500  if (auto *C = dyn_cast<ConstantDataVector>(V)) {
4501  if (!C->getElementType()->isFloatingPointTy())
4502  return false;
4503  for (unsigned I = 0, E = C->getNumElements(); I < E; ++I) {
4504  if (C->getElementAsAPFloat(I).isZero())
4505  return false;
4506  }
4507  return true;
4508  }
4509 
4510  return false;
4511 }
4512 
4513 /// Match clamp pattern for float types without care about NaNs or signed zeros.
4514 /// Given non-min/max outer cmp/select from the clamp pattern this
4515 /// function recognizes if it can be substitued by a "canonical" min/max
4516 /// pattern.
4518  Value *CmpLHS, Value *CmpRHS,
4519  Value *TrueVal, Value *FalseVal,
4520  Value *&LHS, Value *&RHS) {
4521  // Try to match
4522  // X < C1 ? C1 : Min(X, C2) --> Max(C1, Min(X, C2))
4523  // X > C1 ? C1 : Max(X, C2) --> Min(C1, Max(X, C2))
4524  // and return description of the outer Max/Min.
4525 
4526  // First, check if select has inverse order:
4527  if (CmpRHS == FalseVal) {
4528  std::swap(TrueVal, FalseVal);
4529  Pred = CmpInst::getInversePredicate(Pred);
4530  }
4531 
4532  // Assume success now. If there's no match, callers should not use these anyway.
4533  LHS = TrueVal;
4534  RHS = FalseVal;
4535 
4536  const APFloat *FC1;
4537  if (CmpRHS != TrueVal || !match(CmpRHS, m_APFloat(FC1)) || !FC1->isFinite())
4538  return {SPF_UNKNOWN, SPNB_NA, false};
4539 
4540  const APFloat *FC2;
4541  switch (Pred) {
4542  case CmpInst::FCMP_OLT:
4543  case CmpInst::FCMP_OLE:
4544  case CmpInst::FCMP_ULT:
4545  case CmpInst::FCMP_ULE:
4546  if (match(FalseVal,
4547  m_CombineOr(m_OrdFMin(m_Specific(CmpLHS), m_APFloat(FC2)),
4548  m_UnordFMin(m_Specific(CmpLHS), m_APFloat(FC2)))) &&
4549  FC1->compare(*FC2) == APFloat::cmpResult::cmpLessThan)
4550  return {SPF_FMAXNUM, SPNB_RETURNS_ANY, false};
4551  break;
4552  case CmpInst::FCMP_OGT:
4553  case CmpInst::FCMP_OGE:
4554  case CmpInst::FCMP_UGT:
4555  case CmpInst::FCMP_UGE:
4556  if (match(FalseVal,
4557  m_CombineOr(m_OrdFMax(m_Specific(CmpLHS), m_APFloat(FC2)),
4558  m_UnordFMax(m_Specific(CmpLHS), m_APFloat(FC2)))) &&
4559  FC1->compare(*FC2) == APFloat::cmpResult::cmpGreaterThan)
4560  return {SPF_FMINNUM, SPNB_RETURNS_ANY, false};
4561  break;
4562  default:
4563  break;
4564  }
4565 
4566  return {SPF_UNKNOWN, SPNB_NA, false};
4567 }
4568 
4569 /// Recognize variations of:
4570 /// CLAMP(v,l,h) ==> ((v) < (l) ? (l) : ((v) > (h) ? (h) : (v)))
4572  Value *CmpLHS, Value *CmpRHS,
4573  Value *TrueVal, Value *FalseVal) {
4574  // Swap the select operands and predicate to match the patterns below.
4575  if (CmpRHS != TrueVal) {
4576  Pred = ICmpInst::getSwappedPredicate(Pred);
4577  std::swap(TrueVal, FalseVal);
4578  }
4579  const APInt *C1;
4580  if (CmpRHS == TrueVal && match(CmpRHS, m_APInt(C1))) {
4581  const APInt *C2;
4582  // (X <s C1) ? C1 : SMIN(X, C2) ==> SMAX(SMIN(X, C2), C1)
4583  if (match(FalseVal, m_SMin(m_Specific(CmpLHS), m_APInt(C2))) &&
4584  C1->slt(*C2) && Pred == CmpInst::ICMP_SLT)
4585  return {SPF_SMAX, SPNB_NA, false};
4586 
4587  // (X >s C1) ? C1 : SMAX(X, C2) ==> SMIN(SMAX(X, C2), C1)
4588  if (match(FalseVal, m_SMax(m_Specific(CmpLHS), m_APInt(C2))) &&
4589  C1->sgt(*C2) && Pred == CmpInst::ICMP_SGT)
4590  return {SPF_SMIN, SPNB_NA, false};
4591 
4592  // (X <u C1) ? C1 : UMIN(X, C2) ==> UMAX(UMIN(X, C2), C1)
4593  if (match(FalseVal, m_UMin(m_Specific(CmpLHS), m_APInt(C2))) &&
4594  C1->ult(*C2) && Pred == CmpInst::ICMP_ULT)
4595  return {SPF_UMAX, SPNB_NA, false};
4596 
4597  // (X >u C1) ? C1 : UMAX(X, C2) ==> UMIN(UMAX(X, C2), C1)
4598  if (match(FalseVal, m_UMax(m_Specific(CmpLHS), m_APInt(C2))) &&
4599  C1->ugt(*C2) && Pred == CmpInst::ICMP_UGT)
4600  return {SPF_UMIN, SPNB_NA, false};
4601  }
4602  return {SPF_UNKNOWN, SPNB_NA, false};
4603 }
4604 
4605 /// Recognize variations of:
4606 /// a < c ? min(a,b) : min(b,c) ==> min(min(a,b),min(b,c))
4608  Value *CmpLHS, Value *CmpRHS,
4609  Value *TVal, Value *FVal,
4610  unsigned Depth) {
4611  // TODO: Allow FP min/max with nnan/nsz.
4612  assert(CmpInst::isIntPredicate(Pred) && "Expected integer comparison");
4613 
4614  Value *A, *B;
4615  SelectPatternResult L = matchSelectPattern(TVal, A, B, nullptr, Depth + 1);
4617  return {SPF_UNKNOWN, SPNB_NA, false};
4618 
4619  Value *C, *D;
4620  SelectPatternResult R = matchSelectPattern(FVal, C, D, nullptr, Depth + 1);
4621  if (L.Flavor != R.Flavor)
4622  return {SPF_UNKNOWN, SPNB_NA, false};
4623 
4624  // We have something like: x Pred y ? min(a, b) : min(c, d).
4625  // Try to match the compare to the min/max operations of the select operands.
4626  // First, make sure we have the right compare predicate.
4627  switch (L.Flavor) {
4628  case SPF_SMIN:
4629  if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE) {
4630  Pred = ICmpInst::getSwappedPredicate(Pred);
4631  std::swap(CmpLHS, CmpRHS);
4632  }
4633  if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE)
4634  break;
4635  return {SPF_UNKNOWN, SPNB_NA, false};
4636  case SPF_SMAX:
4637  if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) {
4638  Pred = ICmpInst::getSwappedPredicate(Pred);
4639  std::swap(CmpLHS, CmpRHS);
4640  }
4641  if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE)
4642  break;
4643  return {SPF_UNKNOWN, SPNB_NA, false};
4644  case SPF_UMIN:
4645  if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) {
4646  Pred = ICmpInst::getSwappedPredicate(Pred);
4647  std::swap(CmpLHS, CmpRHS);
4648  }
4649  if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE)
4650  break;
4651  return {SPF_UNKNOWN, SPNB_NA, false};
4652  case SPF_UMAX:
4653  if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE) {
4654  Pred = ICmpInst::getSwappedPredicate(Pred);
4655  std::swap(CmpLHS, CmpRHS);
4656  }
4657  if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE)
4658  break;
4659  return {SPF_UNKNOWN, SPNB_NA, false};
4660  default:
4661  return {SPF_UNKNOWN, SPNB_NA, false};
4662  }
4663 
4664  // If there is a common operand in the already matched min/max and the other
4665  // min/max operands match the compare operands (either directly or inverted),
4666  // then this is min/max of the same flavor.
4667 
4668  // a pred c ? m(a, b) : m(c, b) --> m(m(a, b), m(c, b))
4669  // ~c pred ~a ? m(a, b) : m(c, b) --> m(m(a, b), m(c, b))
4670  if (D == B) {
4671  if ((CmpLHS == A && CmpRHS == C) || (match(C, m_Not(m_Specific(CmpLHS))) &&
4672  match(A, m_Not(m_Specific(CmpRHS)))))
4673  return {L.Flavor, SPNB_NA, false};
4674  }
4675  // a pred d ? m(a, b) : m(b, d) --> m(m(a, b), m(b, d))
4676  // ~d pred ~a ? m(a, b) : m(b, d) --> m(m(a, b), m(b, d))
4677  if (C == B) {
4678  if ((CmpLHS == A && CmpRHS == D) || (match(D, m_Not(m_Specific(CmpLHS))) &&
4679  match(A, m_Not(m_Specific(CmpRHS)))))
4680  return {L.Flavor, SPNB_NA, false};
4681  }
4682  // b pred c ? m(a, b) : m(c, a) --> m(m(a, b), m(c, a))
4683  // ~c pred ~b ? m(a, b) : m(c, a) --> m(m(a, b), m(c, a))
4684  if (D == A) {
4685  if ((CmpLHS == B && CmpRHS == C) || (match(C, m_Not(m_Specific(CmpLHS))) &&
4686  match(B, m_Not(m_Specific(CmpRHS)))))
4687  return {L.Flavor, SPNB_NA, false};
4688  }
4689  // b pred d ? m(a, b) : m(a, d) --> m(m(a, b), m(a, d))
4690  // ~d pred ~b ? m(a, b) : m(a, d) --> m(m(a, b), m(a, d))
4691  if (C == A) {
4692  if ((CmpLHS == B && CmpRHS == D) || (match(D, m_Not(m_Specific(CmpLHS))) &&
4693  match(B, m_Not(m_Specific(CmpRHS)))))
4694  return {L.Flavor, SPNB_NA, false};
4695  }
4696 
4697  return {SPF_UNKNOWN, SPNB_NA, false};
4698 }
4699 
4700 /// Match non-obvious integer minimum and maximum sequences.
4702  Value *CmpLHS, Value *CmpRHS,
4703  Value *TrueVal, Value *FalseVal,
4704  Value *&LHS, Value *&RHS,
4705  unsigned Depth) {
4706  // Assume success. If there's no match, callers should not use these anyway.
4707  LHS = TrueVal;
4708  RHS = FalseVal;
4709 
4710  SelectPatternResult SPR = matchClamp(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal);
4712  return SPR;
4713 
4714  SPR = matchMinMaxOfMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, Depth);
4716  return SPR;
4717 
4718  if (Pred != CmpInst::ICMP_SGT && Pred != CmpInst::ICMP_SLT)
4719  return {SPF_UNKNOWN, SPNB_NA, false};
4720 
4721  // Z = X -nsw Y
4722  // (X >s Y) ? 0 : Z ==> (Z >s 0) ? 0 : Z ==> SMIN(Z, 0)
4723  // (X <s Y) ? 0 : Z ==> (Z <s 0) ? 0 : Z ==> SMAX(Z, 0)
4724  if (match(TrueVal, m_Zero()) &&
4725  match(FalseVal, m_NSWSub(m_Specific(CmpLHS), m_Specific(CmpRHS))))
4726  return {Pred == CmpInst::ICMP_SGT ? SPF_SMIN : SPF_SMAX, SPNB_NA, false};
4727 
4728  // Z = X -nsw Y
4729  // (X >s Y) ? Z : 0 ==> (Z >s 0) ? Z : 0 ==> SMAX(Z, 0)
4730  // (X <s Y) ? Z : 0 ==> (Z <s 0) ? Z : 0 ==> SMIN(Z, 0)
4731  if (match(FalseVal, m_Zero()) &&
4732  match(TrueVal, m_NSWSub(m_Specific(CmpLHS), m_Specific(CmpRHS))))
4733  return {Pred == CmpInst::ICMP_SGT ? SPF_SMAX : SPF_SMIN, SPNB_NA, false};
4734 
4735  const APInt *C1;
4736  if (!match(CmpRHS, m_APInt(C1)))
4737  return {SPF_UNKNOWN, SPNB_NA, false};
4738 
4739  // An unsigned min/max can be written with a signed compare.
4740  const APInt *C2;
4741  if ((CmpLHS == TrueVal && match(FalseVal, m_APInt(C2))) ||
4742  (CmpLHS == FalseVal && match(TrueVal, m_APInt(C2)))) {
4743  // Is the sign bit set?
4744  // (X <s 0) ? X : MAXVAL ==> (X >u MAXVAL) ? X : MAXVAL ==> UMAX
4745  // (X <s 0) ? MAXVAL : X ==> (X >u MAXVAL) ? MAXVAL : X ==> UMIN
4746  if (Pred == CmpInst::ICMP_SLT && C1->isNullValue() &&
4747  C2->isMaxSignedValue())
4748  return {CmpLHS == TrueVal ? SPF_UMAX : SPF_UMIN, SPNB_NA, false};
4749 
4750  // Is the sign bit clear?
4751  // (X >s -1) ? MINVAL : X ==> (X <u MINVAL) ? MINVAL : X ==> UMAX
4752  // (X >s -1) ? X : MINVAL ==> (X <u MINVAL) ? X : MINVAL ==> UMIN
4753  if (Pred == CmpInst::ICMP_SGT && C1->isAllOnesValue() &&
4754  C2->isMinSignedValue())
4755  return {CmpLHS == FalseVal ? SPF_UMAX : SPF_UMIN, SPNB_NA, false};
4756  }
4757 
4758  // Look through 'not' ops to find disguised signed min/max.
4759  // (X >s C) ? ~X : ~C ==> (~X <s ~C) ? ~X : ~C ==> SMIN(~X, ~C)
4760  // (X <s C) ? ~X : ~C ==> (~X >s ~C) ? ~X : ~C ==> SMAX(~X, ~C)
4761  if (match(TrueVal, m_Not(m_Specific(CmpLHS))) &&
4762  match(FalseVal, m_APInt(C2)) && ~(*C1) == *C2)
4763  return {Pred == CmpInst::ICMP_SGT ? SPF_SMIN : SPF_SMAX, SPNB_NA, false};
4764 
4765  // (X >s C) ? ~C : ~X ==> (~X <s ~C) ? ~C : ~X ==> SMAX(~C, ~X)
4766  // (X <s C) ? ~C : ~X ==> (~X >s ~C) ? ~C : ~X ==> SMIN(~C, ~X)
4767  if (match(FalseVal, m_Not(m_Specific(CmpLHS))) &&
4768  match(TrueVal, m_APInt(C2)) && ~(*C1) == *C2)
4769  return {Pred == CmpInst::ICMP_SGT ? SPF_SMAX : SPF_SMIN, SPNB_NA, false};
4770 
4771  return {SPF_UNKNOWN, SPNB_NA, false};
4772 }
4773 
4774 bool llvm::isKnownNegation(const Value *X, const Value *Y, bool NeedNSW) {
4775  assert(X && Y && "Invalid operand");
4776 
4777  // X = sub (0, Y) || X = sub nsw (0, Y)
4778  if ((!NeedNSW && match(X, m_Sub(m_ZeroInt(), m_Specific(Y)))) ||
4779  (NeedNSW && match(X, m_NSWSub(m_ZeroInt(), m_Specific(Y)))))
4780  return true;
4781 
4782  // Y = sub (0, X) || Y = sub nsw (0, X)
4783  if ((!NeedNSW && match(Y, m_Sub(m_ZeroInt(), m_Specific(X)))) ||
4784  (NeedNSW && match(Y, m_NSWSub(m_ZeroInt(), m_Specific(X)))))
4785  return true;
4786 
4787  // X = sub (A, B), Y = sub (B, A) || X = sub nsw (A, B), Y = sub nsw (B, A)
4788  Value *A, *B;
4789  return (!NeedNSW && (match(X, m_Sub(m_Value(A), m_Value(B))) &&
4790  match(Y, m_Sub(m_Specific(B), m_Specific(A))))) ||
4791  (NeedNSW && (match(X, m_NSWSub(m_Value(A), m_Value(B))) &&
4792  match(Y, m_NSWSub(m_Specific(B), m_Specific(A)))));
4793 }
4794 
4796  FastMathFlags FMF,
4797  Value *CmpLHS, Value *CmpRHS,
4798  Value *TrueVal, Value *FalseVal,
4799  Value *&LHS, Value *&RHS,
4800  unsigned Depth) {
4801  if (CmpInst::isFPPredicate(Pred)) {
4802  // IEEE-754 ignores the sign of 0.0 in comparisons. So if the select has one
4803  // 0.0 operand, set the compare's 0.0 operands to that same value for the
4804  // purpose of identifying min/max. Disregard vector constants with undefined
4805  // elements because those can not be back-propagated for analysis.
4806  Value *OutputZeroVal = nullptr;
4807  if (match(TrueVal, m_AnyZeroFP()) && !match(FalseVal, m_AnyZeroFP()) &&
4808  !cast<Constant>(TrueVal)->containsUndefElement())
4809  OutputZeroVal = TrueVal;
4810  else if (match(FalseVal, m_AnyZeroFP()) && !match(TrueVal, m_AnyZeroFP()) &&
4811  !cast<Constant>(FalseVal)->containsUndefElement())
4812  OutputZeroVal = FalseVal;
4813 
4814  if (OutputZeroVal) {
4815  if (match(CmpLHS, m_AnyZeroFP()))
4816  CmpLHS = OutputZeroVal;
4817  if (match(CmpRHS, m_AnyZeroFP()))
4818  CmpRHS = OutputZeroVal;
4819  }
4820  }
4821 
4822  LHS = CmpLHS;
4823  RHS = CmpRHS;
4824 
4825  // Signed zero may return inconsistent results between implementations.
4826  // (0.0 <= -0.0) ? 0.0 : -0.0 // Returns 0.0
4827  // minNum(0.0, -0.0) // May return -0.0 or 0.0 (IEEE 754-2008 5.3.1)
4828  // Therefore, we behave conservatively and only proceed if at least one of the
4829  // operands is known to not be zero or if we don't care about signed zero.
4830  switch (Pred) {
4831  default: break;
4832  // FIXME: Include OGT/OLT/UGT/ULT.
4835  if (!FMF.noSignedZeros() && !isKnownNonZero(CmpLHS) &&
4836  !isKnownNonZero(CmpRHS))
4837  return {SPF_UNKNOWN, SPNB_NA, false};
4838  }
4839 
4840  SelectPatternNaNBehavior NaNBehavior = SPNB_NA;
4841  bool Ordered = false;
4842 
4843  // When given one NaN and one non-NaN input:
4844  // - maxnum/minnum (C99 fmaxf()/fminf()) return the non-NaN input.
4845  // - A simple C99 (a < b ? a : b) construction will return 'b' (as the
4846  // ordered comparison fails), which could be NaN or non-NaN.
4847  // so here we discover exactly what NaN behavior is required/accepted.
4848  if (CmpInst::isFPPredicate(Pred)) {
4849  bool LHSSafe = isKnownNonNaN(CmpLHS, FMF);
4850  bool RHSSafe = isKnownNonNaN(CmpRHS, FMF);
4851 
4852  if (LHSSafe && RHSSafe) {
4853  // Both operands are known non-NaN.
4854  NaNBehavior = SPNB_RETURNS_ANY;
4855  } else if (CmpInst::isOrdered(Pred)) {
4856  // An ordered comparison will return false when given a NaN, so it
4857  // returns the RHS.
4858  Ordered = true;
4859  if (LHSSafe)
4860  // LHS is non-NaN, so if RHS is NaN then NaN will be returned.
4861  NaNBehavior = SPNB_RETURNS_NAN;
4862  else if (RHSSafe)
4863  NaNBehavior = SPNB_RETURNS_OTHER;
4864  else
4865  // Completely unsafe.
4866  return {SPF_UNKNOWN, SPNB_NA, false};
4867  } else {
4868  Ordered = false;
4869  // An unordered comparison will return true when given a NaN, so it
4870  // returns the LHS.
4871  if (LHSSafe)
4872  // LHS is non-NaN, so if RHS is NaN then non-NaN will be returned.
4873  NaNBehavior = SPNB_RETURNS_OTHER;
4874  else if (RHSSafe)
4875  NaNBehavior = SPNB_RETURNS_NAN;
4876  else
4877  // Completely unsafe.
4878  return {SPF_UNKNOWN, SPNB_NA, false};
4879  }
4880  }
4881 
4882  if (TrueVal == CmpRHS && FalseVal == CmpLHS) {
4883  std::swap(CmpLHS, CmpRHS);
4884  Pred = CmpInst::getSwappedPredicate(Pred);
4885  if (NaNBehavior == SPNB_RETURNS_NAN)
4886  NaNBehavior = SPNB_RETURNS_OTHER;
4887  else if (NaNBehavior == SPNB_RETURNS_OTHER)
4888  NaNBehavior = SPNB_RETURNS_NAN;
4889  Ordered = !Ordered;
4890  }
4891 
4892  // ([if]cmp X, Y) ? X : Y
4893  if (TrueVal == CmpLHS && FalseVal == CmpRHS) {
4894  switch (Pred) {
4895  default: return {SPF_UNKNOWN, SPNB_NA, false}; // Equality.
4896  case ICmpInst::ICMP_UGT:
4897  case ICmpInst::ICMP_UGE: return {SPF_UMAX, SPNB_NA, false};
4898  case ICmpInst::ICMP_SGT:
4899  case ICmpInst::ICMP_SGE: return {SPF_SMAX, SPNB_NA, false};
4900  case ICmpInst::ICMP_ULT:
4901  case ICmpInst::ICMP_ULE: return {SPF_UMIN, SPNB_NA, false};
4902  case ICmpInst::ICMP_SLT:
4903  case ICmpInst::ICMP_SLE: return {SPF_SMIN, SPNB_NA, false};
4904  case FCmpInst::FCMP_UGT:
4905  case FCmpInst::FCMP_UGE:
4906  case FCmpInst::FCMP_OGT:
4907  case FCmpInst::FCMP_OGE: return {SPF_FMAXNUM, NaNBehavior, Ordered};
4908  case FCmpInst::FCMP_ULT:
4909  case FCmpInst::FCMP_ULE:
4910  case FCmpInst::FCMP_OLT:
4911  case FCmpInst::FCMP_OLE: return {SPF_FMINNUM, NaNBehavior, Ordered};
4912  }
4913  }
4914 
4915  if (isKnownNegation(TrueVal, FalseVal)) {
4916  // Sign-extending LHS does not change its sign, so TrueVal/FalseVal can
4917  // match against either LHS or sext(LHS).
4918  auto MaybeSExtCmpLHS =
4919  m_CombineOr(m_Specific(CmpLHS), m_SExt(m_Specific(CmpLHS)));
4920  auto ZeroOrAllOnes = m_CombineOr(m_ZeroInt(), m_AllOnes());
4921  auto ZeroOrOne = m_CombineOr(m_ZeroInt(), m_One());
4922  if (match(TrueVal, MaybeSExtCmpLHS)) {
4923  // Set the return values. If the compare uses the negated value (-X >s 0),
4924  // swap the return values because the negated value is always 'RHS'.
4925  LHS = TrueVal;
4926  RHS = FalseVal;
4927  if (match(CmpLHS, m_Neg(m_Specific(FalseVal))))
4928  std::swap(LHS, RHS);
4929 
4930  // (X >s 0) ? X : -X or (X >s -1) ? X : -X --> ABS(X)
4931  // (-X >s 0) ? -X : X or (-X >s -1) ? -X : X --> ABS(X)
4932  if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, ZeroOrAllOnes))
4933  return {SPF_ABS, SPNB_NA, false};
4934 
4935  // (X <s 0) ? X : -X or (X <s 1) ? X : -X --> NABS(X)
4936  // (-X <s 0) ? -X : X or (-X <s 1) ? -X : X --> NABS(X)
4937  if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, ZeroOrOne))
4938  return {SPF_NABS, SPNB_NA, false};
4939  }
4940  else if (match(FalseVal, MaybeSExtCmpLHS)) {
4941  // Set the return values. If the compare uses the negated value (-X >s 0),
4942  // swap the return values because the negated value is always 'RHS'.
4943  LHS = FalseVal;
4944  RHS = TrueVal;
4945  if (match(CmpLHS, m_Neg(m_Specific(TrueVal))))
4946  std::swap(LHS, RHS);
4947 
4948  // (X >s 0) ? -X : X or (X >s -1) ? -X : X --> NABS(X)
4949  // (-X >s 0) ? X : -X or (-X >s -1) ? X : -X --> NABS(X)
4950  if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, ZeroOrAllOnes))
4951  return {SPF_NABS, SPNB_NA, false};
4952 
4953  // (X <s 0) ? -X : X or (X <s 1) ? -X : X --> ABS(X)
4954  // (-X <s 0) ? X : -X or (-X <s 1) ? X : -X --> ABS(X)
4955  if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, ZeroOrOne))
4956  return {SPF_ABS, SPNB_NA, false};
4957  }
4958  }
4959 
4960  if (CmpInst::isIntPredicate(Pred))
4961  return matchMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, LHS, RHS, Depth);
4962 
4963  // According to (IEEE 754-2008 5.3.1), minNum(0.0, -0.0) and similar
4964  // may return either -0.0 or 0.0, so fcmp/select pair has stricter
4965  // semantics than minNum. Be conservative in such case.
4966  if (NaNBehavior != SPNB_RETURNS_ANY ||
4967  (!FMF.noSignedZeros() && !isKnownNonZero(CmpLHS) &&
4968  !isKnownNonZero(CmpRHS)))
4969  return {SPF_UNKNOWN, SPNB_NA, false};
4970 
4971  return matchFastFloatClamp(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, LHS, RHS);
4972 }
4973 
4974 /// Helps to match a select pattern in case of a type mismatch.
4975 ///
4976 /// The function processes the case when type of true and false values of a
4977 /// select instruction differs from type of the cmp instruction operands because
4978 /// of a cast instruction. The function checks if it is legal to move the cast
4979 /// operation after "select". If yes, it returns the new second value of
4980 /// "select" (with the assumption that cast is moved):
4981 /// 1. As operand of cast instruction when both values of "select" are same cast
4982 /// instructions.
4983 /// 2. As restored constant (by applying reverse cast operation) when the first
4984 /// value of the "select" is a cast operation and the second value is a
4985 /// constant.
4986 /// NOTE: We return only the new second value because the first value could be
4987 /// accessed as operand of cast instruction.
4988 static Value *lookThroughCast(CmpInst *CmpI, Value *V1, Value *V2,
4989  Instruction::CastOps *CastOp) {
4990  auto *Cast1 = dyn_cast<CastInst>(V1);
4991  if (!Cast1)
4992  return nullptr;
4993 
4994  *CastOp = Cast1->getOpcode();
4995  Type *SrcTy = Cast1->getSrcTy();
4996  if (auto *Cast2 = dyn_cast<CastInst>(V2)) {
4997  // If V1 and V2 are both the same cast from the same type, look through V1.
4998  if (*CastOp == Cast2->getOpcode() && SrcTy == Cast2->getSrcTy())
4999  return Cast2->getOperand(0);
5000  return nullptr;
5001  }
5002 
5003  auto *C = dyn_cast<Constant>(V2);
5004  if (!C)
5005  return nullptr;
5006 
5007  Constant *CastedTo = nullptr;
5008  switch (*CastOp) {
5009  case Instruction::ZExt:
5010  if (CmpI->isUnsigned())
5011  CastedTo = ConstantExpr::getTrunc(C, SrcTy);
5012  break;
5013  case Instruction::SExt:
5014  if (CmpI->isSigned())
5015  CastedTo = ConstantExpr::getTrunc(C, SrcTy, true);
5016  break;
5017  case Instruction::Trunc:
5018  Constant *CmpConst;
5019  if (match(CmpI->getOperand(1), m_Constant(CmpConst)) &&
5020  CmpConst->getType() == SrcTy) {
5021  // Here we have the following case:
5022  //
5023  // %cond = cmp iN %x, CmpConst
5024  // %tr = trunc iN %x to iK
5025  // %narrowsel = select i1 %cond, iK %t, iK C
5026  //
5027  // We can always move trunc after select operation:
5028  //
5029  // %cond = cmp iN %x, CmpConst
5030  // %widesel = select i1 %cond, iN %x, iN CmpConst
5031  // %tr = trunc iN %widesel to iK
5032  //
5033  // Note that C could be extended in any way because we don't care about
5034  // upper bits after truncation. It can't be abs pattern, because it would
5035  // look like:
5036  //
5037  // select i1 %cond, x, -x.
5038  //
5039  // So only min/max pattern could be matched. Such match requires widened C
5040  // == CmpConst. That is why set widened C = CmpConst, condition trunc
5041  // CmpConst == C is checked below.
5042  CastedTo = CmpConst;
5043  } else {
5044  CastedTo = ConstantExpr::getIntegerCast(C, SrcTy, CmpI->isSigned());
5045  }
5046  break;
5047  case Instruction::FPTrunc:
5048  CastedTo = ConstantExpr::getFPExtend(C, SrcTy, true);
5049  break;
5050  case Instruction::FPExt:
5051  CastedTo = ConstantExpr::getFPTrunc(C, SrcTy, true);
5052  break;
5053  case Instruction::FPToUI:
5054  CastedTo = ConstantExpr::getUIToFP(C, SrcTy, true);
5055  break;
5056  case Instruction::FPToSI:
5057  CastedTo = ConstantExpr::getSIToFP(C, SrcTy, true);
5058  break;
5059  case Instruction::UIToFP:
5060  CastedTo = ConstantExpr::getFPToUI(C, SrcTy, true);
5061  break;
5062  case Instruction::SIToFP:
5063  CastedTo = ConstantExpr::getFPToSI(C, SrcTy, true);
5064  break;
5065  default:
5066  break;
5067  }
5068 
5069  if (!CastedTo)
5070  return nullptr;
5071 
5072  // Make sure the cast doesn't lose any information.
5073  Constant *CastedBack =
5074  ConstantExpr::getCast(*CastOp, CastedTo, C->getType(), true);
5075  if (CastedBack != C)
5076  return nullptr;
5077 
5078  return CastedTo;
5079 }
5080 
5082  Instruction::CastOps *CastOp,
5083  unsigned Depth) {
5084  if (Depth >= MaxDepth)
5085  return {SPF_UNKNOWN, SPNB_NA, false};
5086 
5088  if (!SI) return {SPF_UNKNOWN, SPNB_NA, false};
5089 
5090  CmpInst *CmpI = dyn_cast<CmpInst>(SI->getCondition());
5091  if (!CmpI) return {SPF_UNKNOWN, SPNB_NA, false};
5092 
5093  CmpInst::Predicate Pred = CmpI->getPredicate();
5094  Value *CmpLHS = CmpI->getOperand(0);
5095  Value *CmpRHS = CmpI->getOperand(1);
5096  Value *TrueVal = SI->getTrueValue();
5097  Value *FalseVal = SI->getFalseValue();
5098  FastMathFlags FMF;
5099  if (isa<FPMathOperator>(CmpI))
5100  FMF = CmpI->getFastMathFlags();
5101 
5102  // Bail out early.
5103  if (CmpI->isEquality())
5104  return {SPF_UNKNOWN, SPNB_NA, false};
5105 
5106  // Deal with type mismatches.
5107  if (CastOp && CmpLHS->getType() != TrueVal->getType()) {
5108  if (Value *C = lookThroughCast(CmpI, TrueVal, FalseVal, CastOp)) {
5109  // If this is a potential fmin/fmax with a cast to integer, then ignore
5110  // -0.0 because there is no corresponding integer value.
5111  if (*CastOp == Instruction::FPToSI || *CastOp == Instruction::FPToUI)
5112  FMF.setNoSignedZeros();
5113  return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS,
5114  cast<CastInst>(TrueVal)->getOperand(0), C,
5115  LHS, RHS, Depth);
5116  }
5117  if (Value *C = lookThroughCast(CmpI, FalseVal, TrueVal, CastOp)) {
5118  // If this is a potential fmin/fmax with a cast to integer, then ignore
5119  // -0.0 because there is no corresponding integer value.
5120  if (*CastOp == Instruction::FPToSI || *CastOp == Instruction::FPToUI)
5121  FMF.setNoSignedZeros();
5122  return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS,
5123  C, cast<CastInst>(FalseVal)->getOperand(0),
5124  LHS, RHS, Depth);
5125  }
5126  }
5127  return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS, TrueVal, FalseVal,
5128  LHS, RHS, Depth);
5129 }
5130 
5132  if (SPF == SPF_SMIN) return ICmpInst::ICMP_SLT;
5133  if (SPF == SPF_UMIN) return ICmpInst::ICMP_ULT;
5134  if (SPF == SPF_SMAX) return ICmpInst::ICMP_SGT;
5135  if (SPF == SPF_UMAX) return ICmpInst::ICMP_UGT;
5136  if (SPF == SPF_FMINNUM)
5137  return Ordered ? FCmpInst::FCMP_OLT : FCmpInst::FCMP_ULT;
5138  if (SPF == SPF_FMAXNUM)
5139  return Ordered ? FCmpInst::FCMP_OGT : FCmpInst::FCMP_UGT;
5140  llvm_unreachable("unhandled!");
5141 }
5142 
5144  if (SPF == SPF_SMIN) return SPF_SMAX;
5145  if (SPF == SPF_UMIN) return SPF_UMAX;
5146  if (SPF == SPF_SMAX) return SPF_SMIN;
5147  if (SPF == SPF_UMAX) return SPF_UMIN;
5148  llvm_unreachable("unhandled!");
5149 }
5150 
5153 }
5154 
5155 /// Return true if "icmp Pred LHS RHS" is always true.
5156 static bool isTruePredicate(CmpInst::Predicate Pred, const Value *LHS,
5157  const Value *RHS, const DataLayout &DL,
5158  unsigned Depth) {
5159  assert(!LHS->getType()->isVectorTy() && "TODO: extend to handle vectors!");
5160  if (ICmpInst::isTrueWhenEqual(Pred) && LHS == RHS)
5161  return true;
5162 
5163  switch (Pred) {
5164  default:
5165  return false;
5166 
5167  case CmpInst::ICMP_SLE: {
5168  const APInt *C;
5169 
5170  // LHS s<= LHS +_{nsw} C if C >= 0
5171  if (match(RHS, m_NSWAdd(m_Specific(LHS),