1 | //===- BasicAliasAnalysis.h - Stateless, local Alias Analysis ---*- C++ -*-===// |
2 | // |
3 | // The LLVM Compiler Infrastructure |
4 | // |
5 | // This file is distributed under the University of Illinois Open Source |
6 | // License. See LICENSE.TXT for details. |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | /// \file |
10 | /// This is the interface for LLVM's primary stateless and local alias analysis. |
11 | /// |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_ANALYSIS_BASICALIASANALYSIS_H |
15 | #define LLVM_ANALYSIS_BASICALIASANALYSIS_H |
16 | |
17 | #include "llvm/ADT/DenseMap.h" |
18 | #include "llvm/ADT/Optional.h" |
19 | #include "llvm/ADT/SmallPtrSet.h" |
20 | #include "llvm/ADT/SmallVector.h" |
21 | #include "llvm/Analysis/AliasAnalysis.h" |
22 | #include "llvm/Analysis/AssumptionCache.h" |
23 | #include "llvm/Analysis/MemoryLocation.h" |
24 | #include "llvm/IR/InstrTypes.h" |
25 | #include "llvm/IR/PassManager.h" |
26 | #include "llvm/Pass.h" |
27 | #include <algorithm> |
28 | #include <cstdint> |
29 | #include <memory> |
30 | #include <utility> |
31 | |
32 | namespace llvm { |
33 | |
34 | struct AAMDNodes; |
35 | class APInt; |
36 | class AssumptionCache; |
37 | class BasicBlock; |
38 | class DataLayout; |
39 | class DominatorTree; |
40 | class Function; |
41 | class GEPOperator; |
42 | class LoopInfo; |
43 | class PHINode; |
44 | class SelectInst; |
45 | class TargetLibraryInfo; |
46 | class PhiValues; |
47 | class Value; |
48 | |
49 | /// This is the AA result object for the basic, local, and stateless alias |
50 | /// analysis. It implements the AA query interface in an entirely stateless |
51 | /// manner. As one consequence, it is never invalidated due to IR changes. |
52 | /// While it does retain some storage, that is used as an optimization and not |
53 | /// to preserve information from query to query. However it does retain handles |
54 | /// to various other analyses and must be recomputed when those analyses are. |
55 | class BasicAAResult : public AAResultBase<BasicAAResult> { |
56 | friend AAResultBase<BasicAAResult>; |
57 | |
58 | const DataLayout &DL; |
59 | const Function &F; |
60 | const TargetLibraryInfo &TLI; |
61 | AssumptionCache &AC; |
62 | DominatorTree *DT; |
63 | LoopInfo *LI; |
64 | PhiValues *PV; |
65 | |
66 | public: |
67 | BasicAAResult(const DataLayout &DL, const Function &F, |
68 | const TargetLibraryInfo &TLI, AssumptionCache &AC, |
69 | DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, |
70 | PhiValues *PV = nullptr) |
71 | : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), PV(PV) |
72 | {} |
73 | |
74 | BasicAAResult(const BasicAAResult &Arg) |
75 | : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC), |
76 | DT(Arg.DT), LI(Arg.LI), PV(Arg.PV) {} |
77 | BasicAAResult(BasicAAResult &&Arg) |
78 | : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), |
79 | AC(Arg.AC), DT(Arg.DT), LI(Arg.LI), PV(Arg.PV) {} |
80 | |
81 | /// Handle invalidation events in the new pass manager. |
82 | bool invalidate(Function &Fn, const PreservedAnalyses &PA, |
83 | FunctionAnalysisManager::Invalidator &Inv); |
84 | |
85 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB); |
86 | |
87 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc); |
88 | |
89 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2); |
90 | |
91 | /// Chases pointers until we find a (constant global) or not. |
92 | bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal); |
93 | |
94 | /// Get the location associated with a pointer argument of a callsite. |
95 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx); |
96 | |
97 | /// Returns the behavior when calling the given call site. |
98 | FunctionModRefBehavior getModRefBehavior(const CallBase *Call); |
99 | |
100 | /// Returns the behavior when calling the given function. For use when the |
101 | /// call site is not known. |
102 | FunctionModRefBehavior getModRefBehavior(const Function *Fn); |
103 | |
104 | private: |
105 | // A linear transformation of a Value; this class represents ZExt(SExt(V, |
106 | // SExtBits), ZExtBits) * Scale + Offset. |
107 | struct VariableGEPIndex { |
108 | // An opaque Value - we can't decompose this further. |
109 | const Value *V; |
110 | |
111 | // We need to track what extensions we've done as we consider the same Value |
112 | // with different extensions as different variables in a GEP's linear |
113 | // expression; |
114 | // e.g.: if V == -1, then sext(x) != zext(x). |
115 | unsigned ZExtBits; |
116 | unsigned SExtBits; |
117 | |
118 | APInt Scale; |
119 | |
120 | bool operator==(const VariableGEPIndex &Other) const { |
121 | return V == Other.V && ZExtBits == Other.ZExtBits && |
122 | SExtBits == Other.SExtBits && Scale == Other.Scale; |
123 | } |
124 | |
125 | bool operator!=(const VariableGEPIndex &Other) const { |
126 | return !operator==(Other); |
127 | } |
128 | }; |
129 | |
130 | // Represents the internal structure of a GEP, decomposed into a base pointer, |
131 | // constant offsets, and variable scaled indices. |
132 | struct DecomposedGEP { |
133 | // Base pointer of the GEP |
134 | const Value *Base; |
135 | // Total constant offset w.r.t the base from indexing into structs |
136 | APInt StructOffset; |
137 | // Total constant offset w.r.t the base from indexing through |
138 | // pointers/arrays/vectors |
139 | APInt OtherOffset; |
140 | // Scaled variable (non-constant) indices. |
141 | SmallVector<VariableGEPIndex, 4> VarIndices; |
142 | }; |
143 | |
144 | /// Track alias queries to guard against recursion. |
145 | using LocPair = std::pair<MemoryLocation, MemoryLocation>; |
146 | using AliasCacheTy = SmallDenseMap<LocPair, AliasResult, 8>; |
147 | AliasCacheTy AliasCache; |
148 | |
149 | /// Tracks phi nodes we have visited. |
150 | /// |
151 | /// When interpret "Value" pointer equality as value equality we need to make |
152 | /// sure that the "Value" is not part of a cycle. Otherwise, two uses could |
153 | /// come from different "iterations" of a cycle and see different values for |
154 | /// the same "Value" pointer. |
155 | /// |
156 | /// The following example shows the problem: |
157 | /// %p = phi(%alloca1, %addr2) |
158 | /// %l = load %ptr |
159 | /// %addr1 = gep, %alloca2, 0, %l |
160 | /// %addr2 = gep %alloca2, 0, (%l + 1) |
161 | /// alias(%p, %addr1) -> MayAlias ! |
162 | /// store %l, ... |
163 | SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs; |
164 | |
165 | /// Tracks instructions visited by pointsToConstantMemory. |
166 | SmallPtrSet<const Value *, 16> Visited; |
167 | |
168 | static const Value * |
169 | GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset, |
170 | unsigned &ZExtBits, unsigned &SExtBits, |
171 | const DataLayout &DL, unsigned Depth, AssumptionCache *AC, |
172 | DominatorTree *DT, bool &NSW, bool &NUW); |
173 | |
174 | static bool DecomposeGEPExpression(const Value *V, DecomposedGEP &Decomposed, |
175 | const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT); |
176 | |
177 | static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp, |
178 | const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject, |
179 | LocationSize ObjectAccessSize); |
180 | |
181 | /// A Heuristic for aliasGEP that searches for a constant offset |
182 | /// between the variables. |
183 | /// |
184 | /// GetLinearExpression has some limitations, as generally zext(%x + 1) |
185 | /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression |
186 | /// will therefore conservatively refuse to decompose these expressions. |
187 | /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if |
188 | /// the addition overflows. |
189 | bool |
190 | constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices, |
191 | LocationSize V1Size, LocationSize V2Size, |
192 | APInt BaseOffset, AssumptionCache *AC, |
193 | DominatorTree *DT); |
194 | |
195 | bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2); |
196 | |
197 | void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, |
198 | const SmallVectorImpl<VariableGEPIndex> &Src); |
199 | |
200 | AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size, |
201 | const AAMDNodes &V1AAInfo, const Value *V2, |
202 | LocationSize V2Size, const AAMDNodes &V2AAInfo, |
203 | const Value *UnderlyingV1, const Value *UnderlyingV2); |
204 | |
205 | AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize, |
206 | const AAMDNodes &PNAAInfo, const Value *V2, |
207 | LocationSize V2Size, const AAMDNodes &V2AAInfo, |
208 | const Value *UnderV2); |
209 | |
210 | AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize, |
211 | const AAMDNodes &SIAAInfo, const Value *V2, |
212 | LocationSize V2Size, const AAMDNodes &V2AAInfo, |
213 | const Value *UnderV2); |
214 | |
215 | AliasResult aliasCheck(const Value *V1, LocationSize V1Size, |
216 | AAMDNodes V1AATag, const Value *V2, |
217 | LocationSize V2Size, AAMDNodes V2AATag, |
218 | const Value *O1 = nullptr, 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 | BasicAAResult &getResult() { return *Result; } |
245 | 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 | LegacyAARGetter(Pass &P) : P(P) {} |
268 | AAResults &operator()(Function &F) { |
269 | BAR.emplace(createLegacyPMBasicAAResult(P, F)); |
270 | AAR.emplace(createLegacyPMAAResults(P, F, *BAR)); |
271 | return *AAR; |
272 | } |
273 | }; |
274 | |
275 | } // end namespace llvm |
276 | |
277 | #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H |
278 | |