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