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 
28 namespace llvm {
29 
30 struct AAMDNodes;
31 class APInt;
32 class AssumptionCache;
33 class BasicBlock;
34 class DataLayout;
35 class DominatorTree;
36 class Function;
37 class GEPOperator;
38 class PHINode;
39 class SelectInst;
40 class TargetLibraryInfo;
41 class PhiValues;
42 class 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.
50 class 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 
60 public:
61   BasicAAResult(const DataLayout &DL, const Function &F,
62                 const TargetLibraryInfo &TLI, AssumptionCache &AC,
63                 DominatorTree *DT = nullptr, PhiValues *PV = nullptr)
AAResultBase()64       : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), PV(PV) {}
65 
BasicAAResult(const BasicAAResult & Arg)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) {}
BasicAAResult(BasicAAResult && Arg)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 
100 private:
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     /// True if all operations in this expression are NSW.
120     bool IsNSW;
121 
dumpVariableGEPIndex122     void dump() const {
123       print(dbgs());
124       dbgs() << "\n";
125     }
printVariableGEPIndex126     void print(raw_ostream &OS) const {
127       OS << "(V=" << V->getName()
128 	 << ", zextbits=" << ZExtBits
129 	 << ", sextbits=" << SExtBits
130 	 << ", scale=" << Scale << ")";
131     }
132   };
133 
134   // Represents the internal structure of a GEP, decomposed into a base pointer,
135   // constant offsets, and variable scaled indices.
136   struct DecomposedGEP {
137     // Base pointer of the GEP
138     const Value *Base;
139     // Total constant offset from base.
140     APInt Offset;
141     // Scaled variable (non-constant) indices.
142     SmallVector<VariableGEPIndex, 4> VarIndices;
143     // Is GEP index scale compile-time constant.
144     bool HasCompileTimeConstantScale;
145     // Are all operations inbounds GEPs or non-indexing operations?
146     // (None iff expression doesn't involve any geps)
147     Optional<bool> InBounds;
148 
dumpDecomposedGEP149     void dump() const {
150       print(dbgs());
151       dbgs() << "\n";
152     }
printDecomposedGEP153     void print(raw_ostream &OS) const {
154       OS << "(DecomposedGEP Base=" << Base->getName()
155          << ", Offset=" << Offset
156          << ", VarIndices=[";
157       for (size_t i = 0; i < VarIndices.size(); i++) {
158         if (i != 0)
159           OS << ", ";
160         VarIndices[i].print(OS);
161       }
162       OS << "], HasCompileTimeConstantScale=" << HasCompileTimeConstantScale
163          << ")";
164     }
165   };
166 
167   /// Tracks phi nodes we have visited.
168   ///
169   /// When interpret "Value" pointer equality as value equality we need to make
170   /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
171   /// come from different "iterations" of a cycle and see different values for
172   /// the same "Value" pointer.
173   ///
174   /// The following example shows the problem:
175   ///   %p = phi(%alloca1, %addr2)
176   ///   %l = load %ptr
177   ///   %addr1 = gep, %alloca2, 0, %l
178   ///   %addr2 = gep  %alloca2, 0, (%l + 1)
179   ///      alias(%p, %addr1) -> MayAlias !
180   ///   store %l, ...
181   SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
182 
183   /// Tracks instructions visited by pointsToConstantMemory.
184   SmallPtrSet<const Value *, 16> Visited;
185 
186   static DecomposedGEP
187   DecomposeGEPExpression(const Value *V, const DataLayout &DL,
188                          AssumptionCache *AC, DominatorTree *DT);
189 
190   static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
191       const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
192       LocationSize ObjectAccessSize);
193 
194   /// A Heuristic for aliasGEP that searches for a constant offset
195   /// between the variables.
196   ///
197   /// GetLinearExpression has some limitations, as generally zext(%x + 1)
198   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
199   /// will therefore conservatively refuse to decompose these expressions.
200   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
201   /// the addition overflows.
202   bool
203   constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
204                           LocationSize V1Size, LocationSize V2Size,
205                           const APInt &BaseOffset, AssumptionCache *AC,
206                           DominatorTree *DT);
207 
208   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
209 
210   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
211                           const SmallVectorImpl<VariableGEPIndex> &Src);
212 
213   AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
214                        const Value *V2, LocationSize V2Size,
215                        const Value *UnderlyingV1, const Value *UnderlyingV2,
216                        AAQueryInfo &AAQI);
217 
218   AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
219                        const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
220 
221   AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
222                           const Value *V2, LocationSize V2Size,
223                           AAQueryInfo &AAQI);
224 
225   AliasResult aliasCheck(const Value *V1, LocationSize V1Size,
226                          const Value *V2, LocationSize V2Size,
227                          AAQueryInfo &AAQI);
228 
229   AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
230                                   const Value *V2, LocationSize V2Size,
231                                   AAQueryInfo &AAQI, const Value *O1,
232                                   const Value *O2);
233 };
234 
235 /// Analysis pass providing a never-invalidated alias analysis result.
236 class BasicAA : public AnalysisInfoMixin<BasicAA> {
237   friend AnalysisInfoMixin<BasicAA>;
238 
239   static AnalysisKey Key;
240 
241 public:
242   using Result = BasicAAResult;
243 
244   BasicAAResult run(Function &F, FunctionAnalysisManager &AM);
245 };
246 
247 /// Legacy wrapper pass to provide the BasicAAResult object.
248 class BasicAAWrapperPass : public FunctionPass {
249   std::unique_ptr<BasicAAResult> Result;
250 
251   virtual void anchor();
252 
253 public:
254   static char ID;
255 
256   BasicAAWrapperPass();
257 
getResult()258   BasicAAResult &getResult() { return *Result; }
getResult()259   const BasicAAResult &getResult() const { return *Result; }
260 
261   bool runOnFunction(Function &F) override;
262   void getAnalysisUsage(AnalysisUsage &AU) const override;
263 };
264 
265 FunctionPass *createBasicAAWrapperPass();
266 
267 /// A helper for the legacy pass manager to create a \c BasicAAResult object
268 /// populated to the best of our ability for a particular function when inside
269 /// of a \c ModulePass or a \c CallGraphSCCPass.
270 BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F);
271 
272 /// This class is a functor to be used in legacy module or SCC passes for
273 /// computing AA results for a function. We store the results in fields so that
274 /// they live long enough to be queried, but we re-use them each time.
275 class LegacyAARGetter {
276   Pass &P;
277   Optional<BasicAAResult> BAR;
278   Optional<AAResults> AAR;
279 
280 public:
LegacyAARGetter(Pass & P)281   LegacyAARGetter(Pass &P) : P(P) {}
operator()282   AAResults &operator()(Function &F) {
283     BAR.emplace(createLegacyPMBasicAAResult(P, F));
284     AAR.emplace(createLegacyPMAAResults(P, F, *BAR));
285     return *AAR;
286   }
287 };
288 
289 } // end namespace llvm
290 
291 #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H
292