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