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/SmallPtrSet.h" |
17 | #include "llvm/Analysis/AliasAnalysis.h" |
18 | #include "llvm/IR/PassManager.h" |
19 | #include "llvm/Pass.h" |
20 | #include <memory> |
21 | #include <utility> |
22 | |
23 | namespace llvm { |
24 | |
25 | class AssumptionCache; |
26 | class DataLayout; |
27 | class DominatorTree; |
28 | class Function; |
29 | class GEPOperator; |
30 | class PHINode; |
31 | class SelectInst; |
32 | class TargetLibraryInfo; |
33 | class Value; |
34 | |
35 | /// This is the AA result object for the basic, local, and stateless alias |
36 | /// analysis. It implements the AA query interface in an entirely stateless |
37 | /// manner. As one consequence, it is never invalidated due to IR changes. |
38 | /// While it does retain some storage, that is used as an optimization and not |
39 | /// to preserve information from query to query. However it does retain handles |
40 | /// to various other analyses and must be recomputed when those analyses are. |
41 | class BasicAAResult : public AAResultBase { |
42 | const DataLayout &DL; |
43 | const Function &F; |
44 | const TargetLibraryInfo &TLI; |
45 | AssumptionCache &AC; |
46 | /// Use getDT() instead of accessing this member directly, in order to |
47 | /// respect the AAQI.UseDominatorTree option. |
48 | DominatorTree *DT_; |
49 | |
50 | DominatorTree *getDT(const AAQueryInfo &AAQI) const { |
51 | return AAQI.UseDominatorTree ? DT_ : nullptr; |
52 | } |
53 | |
54 | public: |
55 | BasicAAResult(const DataLayout &DL, const Function &F, |
56 | const TargetLibraryInfo &TLI, AssumptionCache &AC, |
57 | DominatorTree *DT = nullptr) |
58 | : DL(DL), F(F), TLI(TLI), AC(AC), DT_(DT) {} |
59 | |
60 | BasicAAResult(const BasicAAResult &Arg) |
61 | : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC), |
62 | DT_(Arg.DT_) {} |
63 | BasicAAResult(BasicAAResult &&Arg) |
64 | : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), |
65 | AC(Arg.AC), DT_(Arg.DT_) {} |
66 | |
67 | /// Handle invalidation events in the new pass manager. |
68 | bool invalidate(Function &Fn, const PreservedAnalyses &PA, |
69 | FunctionAnalysisManager::Invalidator &Inv); |
70 | |
71 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
72 | AAQueryInfo &AAQI, const Instruction *CtxI); |
73 | |
74 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
75 | AAQueryInfo &AAQI); |
76 | |
77 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
78 | AAQueryInfo &AAQI); |
79 | |
80 | /// Returns a bitmask that should be unconditionally applied to the ModRef |
81 | /// info of a memory location. This allows us to eliminate Mod and/or Ref |
82 | /// from the ModRef info based on the knowledge that the memory location |
83 | /// points to constant and/or locally-invariant memory. |
84 | /// |
85 | /// If IgnoreLocals is true, then this method returns NoModRef for memory |
86 | /// that points to a local alloca. |
87 | ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
88 | bool IgnoreLocals = false); |
89 | |
90 | /// Get the location associated with a pointer argument of a callsite. |
91 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx); |
92 | |
93 | /// Returns the behavior when calling the given call site. |
94 | MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI); |
95 | |
96 | /// Returns the behavior when calling the given function. For use when the |
97 | /// call site is not known. |
98 | MemoryEffects getMemoryEffects(const Function *Fn); |
99 | |
100 | private: |
101 | struct DecomposedGEP; |
102 | |
103 | /// Tracks instructions visited by pointsToConstantMemory. |
104 | SmallPtrSet<const Value *, 16> Visited; |
105 | |
106 | static DecomposedGEP |
107 | DecomposeGEPExpression(const Value *V, const DataLayout &DL, |
108 | AssumptionCache *AC, DominatorTree *DT); |
109 | |
110 | /// A Heuristic for aliasGEP that searches for a constant offset |
111 | /// between the variables. |
112 | /// |
113 | /// GetLinearExpression has some limitations, as generally zext(%x + 1) |
114 | /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression |
115 | /// will therefore conservatively refuse to decompose these expressions. |
116 | /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if |
117 | /// the addition overflows. |
118 | bool constantOffsetHeuristic(const DecomposedGEP &GEP, LocationSize V1Size, |
119 | LocationSize V2Size, AssumptionCache *AC, |
120 | DominatorTree *DT, const AAQueryInfo &AAQI); |
121 | |
122 | bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2, |
123 | const AAQueryInfo &AAQI); |
124 | |
125 | void subtractDecomposedGEPs(DecomposedGEP &DestGEP, |
126 | const DecomposedGEP &SrcGEP, |
127 | const AAQueryInfo &AAQI); |
128 | |
129 | AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size, |
130 | const Value *V2, LocationSize V2Size, |
131 | const Value *UnderlyingV1, const Value *UnderlyingV2, |
132 | AAQueryInfo &AAQI); |
133 | |
134 | AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize, |
135 | const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI); |
136 | |
137 | AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize, |
138 | const Value *V2, LocationSize V2Size, |
139 | AAQueryInfo &AAQI); |
140 | |
141 | AliasResult aliasCheck(const Value *V1, LocationSize V1Size, const Value *V2, |
142 | LocationSize V2Size, AAQueryInfo &AAQI, |
143 | const Instruction *CtxI); |
144 | |
145 | AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size, |
146 | const Value *V2, LocationSize V2Size, |
147 | AAQueryInfo &AAQI, const Value *O1, |
148 | const Value *O2); |
149 | }; |
150 | |
151 | /// Analysis pass providing a never-invalidated alias analysis result. |
152 | class BasicAA : public AnalysisInfoMixin<BasicAA> { |
153 | friend AnalysisInfoMixin<BasicAA>; |
154 | |
155 | static AnalysisKey Key; |
156 | |
157 | public: |
158 | using Result = BasicAAResult; |
159 | |
160 | BasicAAResult run(Function &F, FunctionAnalysisManager &AM); |
161 | }; |
162 | |
163 | /// Legacy wrapper pass to provide the BasicAAResult object. |
164 | class BasicAAWrapperPass : public FunctionPass { |
165 | std::unique_ptr<BasicAAResult> Result; |
166 | |
167 | virtual void anchor(); |
168 | |
169 | public: |
170 | static char ID; |
171 | |
172 | BasicAAWrapperPass(); |
173 | |
174 | BasicAAResult &getResult() { return *Result; } |
175 | const BasicAAResult &getResult() const { return *Result; } |
176 | |
177 | bool runOnFunction(Function &F) override; |
178 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
179 | }; |
180 | |
181 | FunctionPass *createBasicAAWrapperPass(); |
182 | |
183 | } // end namespace llvm |
184 | |
185 | #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H |
186 | |