Bug Summary

File:src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Analysis/ValueTracking.cpp
Warning:line 1335, column 13
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -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 -mrelocation-model static -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Analysis -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ASMParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/BinaryFormat -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitstream -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /include/llvm/CodeGen -I /include/llvm/CodeGen/PBQP -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Coroutines -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData/Coverage -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/CodeView -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/DWARF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/MSF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/PDB -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Demangle -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/JITLink -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/Orc -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenACC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenMP -I /include/llvm/CodeGen/GlobalISel -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IRReader -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/LTO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Linker -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC/MCParser -I /include/llvm/CodeGen/MIRParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Object -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Option -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Passes -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Scalar -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/Symbolize -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Target -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Vectorize -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/IPO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVM/../include -I /usr/src/gnu/usr.bin/clang/libLLVM/obj -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -stack-protector 2 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Analysis/ValueTracking.cpp

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