Bug Summary

File:llvm/include/llvm/IR/Instructions.h
Warning:line 2630, column 17
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name ValueTracking.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/build-llvm -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Analysis -I /build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/llvm/lib/Analysis -I include -I /build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-01-16-232930-107970-1 -x c++ /build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/llvm/lib/Analysis/ValueTracking.cpp

/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/llvm/lib/Analysis/ValueTracking.cpp

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