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