/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/BasicAliasAnalysis.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- BasicAliasAnalysis.h - Stateless, local Alias Analysis ---*- C++ -*-===// |
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 | | /// \file |
9 | | /// This is the interface for LLVM's primary stateless and local alias analysis. |
10 | | /// |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #ifndef LLVM_ANALYSIS_BASICALIASANALYSIS_H |
14 | | #define LLVM_ANALYSIS_BASICALIASANALYSIS_H |
15 | | |
16 | | #include "llvm/ADT/DenseMap.h" |
17 | | #include "llvm/ADT/Optional.h" |
18 | | #include "llvm/ADT/SmallPtrSet.h" |
19 | | #include "llvm/ADT/SmallVector.h" |
20 | | #include "llvm/Analysis/AliasAnalysis.h" |
21 | | #include "llvm/Analysis/AssumptionCache.h" |
22 | | #include "llvm/Analysis/MemoryLocation.h" |
23 | | #include "llvm/IR/InstrTypes.h" |
24 | | #include "llvm/IR/PassManager.h" |
25 | | #include "llvm/Pass.h" |
26 | | #include <algorithm> |
27 | | #include <cstdint> |
28 | | #include <memory> |
29 | | #include <utility> |
30 | | |
31 | | namespace llvm { |
32 | | |
33 | | struct AAMDNodes; |
34 | | class APInt; |
35 | | class AssumptionCache; |
36 | | class BasicBlock; |
37 | | class DataLayout; |
38 | | class DominatorTree; |
39 | | class Function; |
40 | | class GEPOperator; |
41 | | class LoopInfo; |
42 | | class PHINode; |
43 | | class SelectInst; |
44 | | class TargetLibraryInfo; |
45 | | class PhiValues; |
46 | | class Value; |
47 | | |
48 | | /// This is the AA result object for the basic, local, and stateless alias |
49 | | /// analysis. It implements the AA query interface in an entirely stateless |
50 | | /// manner. As one consequence, it is never invalidated due to IR changes. |
51 | | /// While it does retain some storage, that is used as an optimization and not |
52 | | /// to preserve information from query to query. However it does retain handles |
53 | | /// to various other analyses and must be recomputed when those analyses are. |
54 | | class BasicAAResult : public AAResultBase<BasicAAResult> { |
55 | | friend AAResultBase<BasicAAResult>; |
56 | | |
57 | | const DataLayout &DL; |
58 | | const Function &F; |
59 | | const TargetLibraryInfo &TLI; |
60 | | AssumptionCache &AC; |
61 | | DominatorTree *DT; |
62 | | LoopInfo *LI; |
63 | | PhiValues *PV; |
64 | | |
65 | | public: |
66 | | BasicAAResult(const DataLayout &DL, const Function &F, |
67 | | const TargetLibraryInfo &TLI, AssumptionCache &AC, |
68 | | DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, |
69 | | PhiValues *PV = nullptr) |
70 | | : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), PV(PV) |
71 | 10.7M | {} |
72 | | |
73 | | BasicAAResult(const BasicAAResult &Arg) |
74 | | : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC), |
75 | 0 | DT(Arg.DT), LI(Arg.LI), PV(Arg.PV) {} |
76 | | BasicAAResult(BasicAAResult &&Arg) |
77 | | : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), |
78 | 1.18M | AC(Arg.AC), DT(Arg.DT), LI(Arg.LI), PV(Arg.PV) {} |
79 | | |
80 | | /// Handle invalidation events in the new pass manager. |
81 | | bool invalidate(Function &Fn, const PreservedAnalyses &PA, |
82 | | FunctionAnalysisManager::Invalidator &Inv); |
83 | | |
84 | | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
85 | | AAQueryInfo &AAQI); |
86 | | |
87 | | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
88 | | AAQueryInfo &AAQI); |
89 | | |
90 | | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
91 | | AAQueryInfo &AAQI); |
92 | | |
93 | | /// Chases pointers until we find a (constant global) or not. |
94 | | bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
95 | | bool OrLocal); |
96 | | |
97 | | /// Get the location associated with a pointer argument of a callsite. |
98 | | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx); |
99 | | |
100 | | /// Returns the behavior when calling the given call site. |
101 | | FunctionModRefBehavior getModRefBehavior(const CallBase *Call); |
102 | | |
103 | | /// Returns the behavior when calling the given function. For use when the |
104 | | /// call site is not known. |
105 | | FunctionModRefBehavior getModRefBehavior(const Function *Fn); |
106 | | |
107 | | private: |
108 | | // A linear transformation of a Value; this class represents ZExt(SExt(V, |
109 | | // SExtBits), ZExtBits) * Scale + Offset. |
110 | | struct VariableGEPIndex { |
111 | | // An opaque Value - we can't decompose this further. |
112 | | const Value *V; |
113 | | |
114 | | // We need to track what extensions we've done as we consider the same Value |
115 | | // with different extensions as different variables in a GEP's linear |
116 | | // expression; |
117 | | // e.g.: if V == -1, then sext(x) != zext(x). |
118 | | unsigned ZExtBits; |
119 | | unsigned SExtBits; |
120 | | |
121 | | APInt Scale; |
122 | | |
123 | 156k | bool operator==(const VariableGEPIndex &Other) const { |
124 | 156k | return V == Other.V && ZExtBits == Other.ZExtBits49.4k && |
125 | 156k | SExtBits == Other.SExtBits49.4k && Scale == Other.Scale49.4k ; |
126 | 156k | } |
127 | | |
128 | 0 | bool operator!=(const VariableGEPIndex &Other) const { |
129 | 0 | return !operator==(Other); |
130 | 0 | } |
131 | | }; |
132 | | |
133 | | // Represents the internal structure of a GEP, decomposed into a base pointer, |
134 | | // constant offsets, and variable scaled indices. |
135 | | struct DecomposedGEP { |
136 | | // Base pointer of the GEP |
137 | | const Value *Base; |
138 | | // Total constant offset w.r.t the base from indexing into structs |
139 | | APInt StructOffset; |
140 | | // Total constant offset w.r.t the base from indexing through |
141 | | // pointers/arrays/vectors |
142 | | APInt OtherOffset; |
143 | | // Scaled variable (non-constant) indices. |
144 | | SmallVector<VariableGEPIndex, 4> VarIndices; |
145 | | }; |
146 | | |
147 | | /// Tracks phi nodes we have visited. |
148 | | /// |
149 | | /// When interpret "Value" pointer equality as value equality we need to make |
150 | | /// sure that the "Value" is not part of a cycle. Otherwise, two uses could |
151 | | /// come from different "iterations" of a cycle and see different values for |
152 | | /// the same "Value" pointer. |
153 | | /// |
154 | | /// The following example shows the problem: |
155 | | /// %p = phi(%alloca1, %addr2) |
156 | | /// %l = load %ptr |
157 | | /// %addr1 = gep, %alloca2, 0, %l |
158 | | /// %addr2 = gep %alloca2, 0, (%l + 1) |
159 | | /// alias(%p, %addr1) -> MayAlias ! |
160 | | /// store %l, ... |
161 | | SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs; |
162 | | |
163 | | /// Tracks instructions visited by pointsToConstantMemory. |
164 | | SmallPtrSet<const Value *, 16> Visited; |
165 | | |
166 | | static const Value * |
167 | | GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset, |
168 | | unsigned &ZExtBits, unsigned &SExtBits, |
169 | | const DataLayout &DL, unsigned Depth, AssumptionCache *AC, |
170 | | DominatorTree *DT, bool &NSW, bool &NUW); |
171 | | |
172 | | static bool DecomposeGEPExpression(const Value *V, DecomposedGEP &Decomposed, |
173 | | const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT); |
174 | | |
175 | | static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp, |
176 | | const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject, |
177 | | LocationSize ObjectAccessSize); |
178 | | |
179 | | /// A Heuristic for aliasGEP that searches for a constant offset |
180 | | /// between the variables. |
181 | | /// |
182 | | /// GetLinearExpression has some limitations, as generally zext(%x + 1) |
183 | | /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression |
184 | | /// will therefore conservatively refuse to decompose these expressions. |
185 | | /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if |
186 | | /// the addition overflows. |
187 | | bool |
188 | | constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices, |
189 | | LocationSize V1Size, LocationSize V2Size, |
190 | | APInt BaseOffset, AssumptionCache *AC, |
191 | | DominatorTree *DT); |
192 | | |
193 | | bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2); |
194 | | |
195 | | void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, |
196 | | const SmallVectorImpl<VariableGEPIndex> &Src); |
197 | | |
198 | | AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size, |
199 | | const AAMDNodes &V1AAInfo, const Value *V2, |
200 | | LocationSize V2Size, const AAMDNodes &V2AAInfo, |
201 | | const Value *UnderlyingV1, const Value *UnderlyingV2, |
202 | | AAQueryInfo &AAQI); |
203 | | |
204 | | AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize, |
205 | | const AAMDNodes &PNAAInfo, const Value *V2, |
206 | | LocationSize V2Size, const AAMDNodes &V2AAInfo, |
207 | | const Value *UnderV2, AAQueryInfo &AAQI); |
208 | | |
209 | | AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize, |
210 | | const AAMDNodes &SIAAInfo, const Value *V2, |
211 | | LocationSize V2Size, const AAMDNodes &V2AAInfo, |
212 | | const Value *UnderV2, AAQueryInfo &AAQI); |
213 | | |
214 | | AliasResult aliasCheck(const Value *V1, LocationSize V1Size, |
215 | | AAMDNodes V1AATag, const Value *V2, |
216 | | LocationSize V2Size, AAMDNodes V2AATag, |
217 | | AAQueryInfo &AAQI, const Value *O1 = nullptr, |
218 | | const Value *O2 = nullptr); |
219 | | }; |
220 | | |
221 | | /// Analysis pass providing a never-invalidated alias analysis result. |
222 | | class BasicAA : public AnalysisInfoMixin<BasicAA> { |
223 | | friend AnalysisInfoMixin<BasicAA>; |
224 | | |
225 | | static AnalysisKey Key; |
226 | | |
227 | | public: |
228 | | using Result = BasicAAResult; |
229 | | |
230 | | BasicAAResult run(Function &F, FunctionAnalysisManager &AM); |
231 | | }; |
232 | | |
233 | | /// Legacy wrapper pass to provide the BasicAAResult object. |
234 | | class BasicAAWrapperPass : public FunctionPass { |
235 | | std::unique_ptr<BasicAAResult> Result; |
236 | | |
237 | | virtual void anchor(); |
238 | | |
239 | | public: |
240 | | static char ID; |
241 | | |
242 | | BasicAAWrapperPass(); |
243 | | |
244 | 9.40M | BasicAAResult &getResult() { return *Result; } |
245 | 0 | const BasicAAResult &getResult() const { return *Result; } |
246 | | |
247 | | bool runOnFunction(Function &F) override; |
248 | | void getAnalysisUsage(AnalysisUsage &AU) const override; |
249 | | }; |
250 | | |
251 | | FunctionPass *createBasicAAWrapperPass(); |
252 | | |
253 | | /// A helper for the legacy pass manager to create a \c BasicAAResult object |
254 | | /// populated to the best of our ability for a particular function when inside |
255 | | /// of a \c ModulePass or a \c CallGraphSCCPass. |
256 | | BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F); |
257 | | |
258 | | /// This class is a functor to be used in legacy module or SCC passes for |
259 | | /// computing AA results for a function. We store the results in fields so that |
260 | | /// they live long enough to be queried, but we re-use them each time. |
261 | | class LegacyAARGetter { |
262 | | Pass &P; |
263 | | Optional<BasicAAResult> BAR; |
264 | | Optional<AAResults> AAR; |
265 | | |
266 | | public: |
267 | 2.12M | LegacyAARGetter(Pass &P) : P(P) {} |
268 | 1.17M | AAResults &operator()(Function &F) { |
269 | 1.17M | BAR.emplace(createLegacyPMBasicAAResult(P, F)); |
270 | 1.17M | AAR.emplace(createLegacyPMAAResults(P, F, *BAR)); |
271 | 1.17M | return *AAR; |
272 | 1.17M | } |
273 | | }; |
274 | | |
275 | | } // end namespace llvm |
276 | | |
277 | | #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H |