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