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/Optional.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/Analysis/AliasAnalysis.h"
19 #include "llvm/IR/PassManager.h"
20 #include "llvm/Pass.h"
21 #include <memory>
22 #include <utility>
23 
24 namespace llvm {
25 
26 class AssumptionCache;
27 class BasicBlock;
28 class DataLayout;
29 class DominatorTree;
30 class Function;
31 class GEPOperator;
32 class PHINode;
33 class SelectInst;
34 class TargetLibraryInfo;
35 class PhiValues;
36 class Value;
37 
38 /// This is the AA result object for the basic, local, and stateless alias
39 /// analysis. It implements the AA query interface in an entirely stateless
40 /// manner. As one consequence, it is never invalidated due to IR changes.
41 /// While it does retain some storage, that is used as an optimization and not
42 /// to preserve information from query to query. However it does retain handles
43 /// to various other analyses and must be recomputed when those analyses are.
44 class BasicAAResult : public AAResultBase<BasicAAResult> {
45   friend AAResultBase<BasicAAResult>;
46 
47   const DataLayout &DL;
48   const Function &F;
49   const TargetLibraryInfo &TLI;
50   AssumptionCache &AC;
51   DominatorTree *DT;
52   PhiValues *PV;
53 
54 public:
55   BasicAAResult(const DataLayout &DL, const Function &F,
56                 const TargetLibraryInfo &TLI, AssumptionCache &AC,
57                 DominatorTree *DT = nullptr, PhiValues *PV = nullptr)
58       : DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), PV(PV) {}
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), PV(Arg.PV) {}
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), PV(Arg.PV) {}
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);
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   /// Chases pointers until we find a (constant global) or not.
81   bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
82                               bool OrLocal);
83 
84   /// Get the location associated with a pointer argument of a callsite.
85   ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
86 
87   /// Returns the behavior when calling the given call site.
88   FunctionModRefBehavior getModRefBehavior(const CallBase *Call);
89 
90   /// Returns the behavior when calling the given function. For use when the
91   /// call site is not known.
92   FunctionModRefBehavior getModRefBehavior(const Function *Fn);
93 
94 private:
95   struct DecomposedGEP;
96 
97   /// Tracks phi nodes we have visited.
98   ///
99   /// When interpret "Value" pointer equality as value equality we need to make
100   /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
101   /// come from different "iterations" of a cycle and see different values for
102   /// the same "Value" pointer.
103   ///
104   /// The following example shows the problem:
105   ///   %p = phi(%alloca1, %addr2)
106   ///   %l = load %ptr
107   ///   %addr1 = gep, %alloca2, 0, %l
108   ///   %addr2 = gep  %alloca2, 0, (%l + 1)
109   ///      alias(%p, %addr1) -> MayAlias !
110   ///   store %l, ...
111   SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
112 
113   /// Tracks instructions visited by pointsToConstantMemory.
114   SmallPtrSet<const Value *, 16> Visited;
115 
116   static DecomposedGEP
117   DecomposeGEPExpression(const Value *V, const DataLayout &DL,
118                          AssumptionCache *AC, DominatorTree *DT);
119 
120   /// A Heuristic for aliasGEP that searches for a constant offset
121   /// between the variables.
122   ///
123   /// GetLinearExpression has some limitations, as generally zext(%x + 1)
124   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
125   /// will therefore conservatively refuse to decompose these expressions.
126   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
127   /// the addition overflows.
128   bool
129   constantOffsetHeuristic(const DecomposedGEP &GEP, LocationSize V1Size,
130                           LocationSize V2Size, AssumptionCache *AC,
131                           DominatorTree *DT);
132 
133   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
134 
135   void subtractDecomposedGEPs(DecomposedGEP &DestGEP,
136                               const DecomposedGEP &SrcGEP);
137 
138   AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
139                        const Value *V2, LocationSize V2Size,
140                        const Value *UnderlyingV1, const Value *UnderlyingV2,
141                        AAQueryInfo &AAQI);
142 
143   AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
144                        const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
145 
146   AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
147                           const Value *V2, LocationSize V2Size,
148                           AAQueryInfo &AAQI);
149 
150   AliasResult aliasCheck(const Value *V1, LocationSize V1Size,
151                          const Value *V2, LocationSize V2Size,
152                          AAQueryInfo &AAQI);
153 
154   AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
155                                   const Value *V2, LocationSize V2Size,
156                                   AAQueryInfo &AAQI, const Value *O1,
157                                   const Value *O2);
158 };
159 
160 /// Analysis pass providing a never-invalidated alias analysis result.
161 class BasicAA : public AnalysisInfoMixin<BasicAA> {
162   friend AnalysisInfoMixin<BasicAA>;
163 
164   static AnalysisKey Key;
165 
166 public:
167   using Result = BasicAAResult;
168 
169   BasicAAResult run(Function &F, FunctionAnalysisManager &AM);
170 };
171 
172 /// Legacy wrapper pass to provide the BasicAAResult object.
173 class BasicAAWrapperPass : public FunctionPass {
174   std::unique_ptr<BasicAAResult> Result;
175 
176   virtual void anchor();
177 
178 public:
179   static char ID;
180 
181   BasicAAWrapperPass();
182 
183   BasicAAResult &getResult() { return *Result; }
184   const BasicAAResult &getResult() const { return *Result; }
185 
186   bool runOnFunction(Function &F) override;
187   void getAnalysisUsage(AnalysisUsage &AU) const override;
188 };
189 
190 FunctionPass *createBasicAAWrapperPass();
191 
192 /// A helper for the legacy pass manager to create a \c BasicAAResult object
193 /// populated to the best of our ability for a particular function when inside
194 /// of a \c ModulePass or a \c CallGraphSCCPass.
195 BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F);
196 
197 /// This class is a functor to be used in legacy module or SCC passes for
198 /// computing AA results for a function. We store the results in fields so that
199 /// they live long enough to be queried, but we re-use them each time.
200 class LegacyAARGetter {
201   Pass &P;
202   Optional<BasicAAResult> BAR;
203   Optional<AAResults> AAR;
204 
205 public:
206   LegacyAARGetter(Pass &P) : P(P) {}
207   AAResults &operator()(Function &F) {
208     BAR.emplace(createLegacyPMBasicAAResult(P, F));
209     AAR.emplace(createLegacyPMAAResults(P, F, *BAR));
210     return *AAR;
211   }
212 };
213 
214 } // end namespace llvm
215 
216 #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H
217