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