LLVM  7.0.0svn
BasicAliasAnalysis.h
Go to the documentation of this file.
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"
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> {
56 
57  const DataLayout &DL;
58  const Function &F;
59  const TargetLibraryInfo &TLI;
60  AssumptionCache &AC;
61  DominatorTree *DT;
62  LoopInfo *LI;
63 
64 public:
65  BasicAAResult(const DataLayout &DL, const Function &F,
66  const TargetLibraryInfo &TLI, AssumptionCache &AC,
67  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr)
68  : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), LI(LI) {}
69 
71  : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
72  DT(Arg.DT), LI(Arg.LI) {}
74  : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI),
75  AC(Arg.AC), DT(Arg.DT), LI(Arg.LI) {}
76 
77  /// Handle invalidation events in the new pass manager.
78  bool invalidate(Function &Fn, const PreservedAnalyses &PA,
80 
81  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
82 
84 
86 
87  /// Chases pointers until we find a (constant global) or not.
88  bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal);
89 
90  /// Get the location associated with a pointer argument of a callsite.
91  ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
92 
93  /// Returns the behavior when calling the given call site.
95 
96  /// Returns the behavior when calling the given function. For use when the
97  /// call site is not known.
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  int64_t Scale;
115 
116  bool operator==(const VariableGEPIndex &Other) const {
117  return V == Other.V && ZExtBits == Other.ZExtBits &&
118  SExtBits == Other.SExtBits && Scale == Other.Scale;
119  }
120 
121  bool operator!=(const VariableGEPIndex &Other) const {
122  return !operator==(Other);
123  }
124  };
125 
126  // Represents the internal structure of a GEP, decomposed into a base pointer,
127  // constant offsets, and variable scaled indices.
128  struct DecomposedGEP {
129  // Base pointer of the GEP
130  const Value *Base;
131  // Total constant offset w.r.t the base from indexing into structs
132  int64_t StructOffset;
133  // Total constant offset w.r.t the base from indexing through
134  // pointers/arrays/vectors
135  int64_t OtherOffset;
136  // Scaled variable (non-constant) indices.
138  };
139 
140  /// Track alias queries to guard against recursion.
141  using LocPair = std::pair<MemoryLocation, MemoryLocation>;
143  AliasCacheTy AliasCache;
144 
145  /// Tracks phi nodes we have visited.
146  ///
147  /// When interpret "Value" pointer equality as value equality we need to make
148  /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
149  /// come from different "iterations" of a cycle and see different values for
150  /// the same "Value" pointer.
151  ///
152  /// The following example shows the problem:
153  /// %p = phi(%alloca1, %addr2)
154  /// %l = load %ptr
155  /// %addr1 = gep, %alloca2, 0, %l
156  /// %addr2 = gep %alloca2, 0, (%l + 1)
157  /// alias(%p, %addr1) -> MayAlias !
158  /// store %l, ...
160 
161  /// Tracks instructions visited by pointsToConstantMemory.
163 
164  static const Value *
165  GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset,
166  unsigned &ZExtBits, unsigned &SExtBits,
167  const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
168  DominatorTree *DT, bool &NSW, bool &NUW);
169 
170  static bool DecomposeGEPExpression(const Value *V, DecomposedGEP &Decomposed,
171  const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT);
172 
173  static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
174  const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
175  LocationSize ObjectAccessSize);
176 
177  /// A Heuristic for aliasGEP that searches for a constant offset
178  /// between the variables.
179  ///
180  /// GetLinearExpression has some limitations, as generally zext(%x + 1)
181  /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
182  /// will therefore conservatively refuse to decompose these expressions.
183  /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
184  /// the addition overflows.
185  bool
186  constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
187  LocationSize V1Size, LocationSize V2Size,
188  int64_t BaseOffset, AssumptionCache *AC,
189  DominatorTree *DT);
190 
191  bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
192 
193  void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
195 
196  AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
197  const AAMDNodes &V1AAInfo, const Value *V2,
198  LocationSize V2Size, const AAMDNodes &V2AAInfo,
199  const Value *UnderlyingV1, const Value *UnderlyingV2);
200 
201  AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
202  const AAMDNodes &PNAAInfo, const Value *V2,
203  LocationSize V2Size, const AAMDNodes &V2AAInfo,
204  const Value *UnderV2);
205 
206  AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
207  const AAMDNodes &SIAAInfo, const Value *V2,
208  LocationSize V2Size, const AAMDNodes &V2AAInfo,
209  const Value *UnderV2);
210 
211  AliasResult aliasCheck(const Value *V1, LocationSize V1Size,
212  AAMDNodes V1AATag, const Value *V2,
213  LocationSize V2Size, AAMDNodes V2AATag,
214  const Value *O1 = nullptr, const Value *O2 = nullptr);
215 };
216 
217 /// Analysis pass providing a never-invalidated alias analysis result.
218 class BasicAA : public AnalysisInfoMixin<BasicAA> {
220 
221  static AnalysisKey Key;
222 
223 public:
225 
227 };
228 
229 /// Legacy wrapper pass to provide the BasicAAResult object.
231  std::unique_ptr<BasicAAResult> Result;
232 
233  virtual void anchor();
234 
235 public:
236  static char ID;
237 
239 
240  BasicAAResult &getResult() { return *Result; }
241  const BasicAAResult &getResult() const { return *Result; }
242 
243  bool runOnFunction(Function &F) override;
244  void getAnalysisUsage(AnalysisUsage &AU) const override;
245 };
246 
248 
249 /// A helper for the legacy pass manager to create a \c BasicAAResult object
250 /// populated to the best of our ability for a particular function when inside
251 /// of a \c ModulePass or a \c CallGraphSCCPass.
253 
254 /// This class is a functor to be used in legacy module or SCC passes for
255 /// computing AA results for a function. We store the results in fields so that
256 /// they live long enough to be queried, but we re-use them each time.
258  Pass &P;
261 
262 public:
263  LegacyAARGetter(Pass &P) : P(P) {}
266  AAR.emplace(createLegacyPMAAResults(P, F, *BAR));
267  return *AAR;
268  }
269 };
270 
271 } // end namespace llvm
272 
273 #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
uint64_t LocationSize
const BasicAAResult & getResult() const
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Various leaf nodes.
Definition: ISDOpcodes.h:60
BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F)
A helper for the legacy pass manager to create a BasicAAResult object populated to the best of our ab...
BasicAAResult(const DataLayout &DL, const Function &F, const TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
void emplace(ArgTypes &&... Args)
Create a new object by constructing it in place with the given arguments.
Definition: Optional.h:153
A cache of @llvm.assume calls within a function.
This is the AA result object for the basic, local, and stateless alias analysis.
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal)
Chases pointers until we find a (constant global) or not.
Definition: BitVector.h:921
This class represents the LLVM &#39;select&#39; instruction.
This class is a functor to be used in legacy module or SCC passes for computing AA results for a func...
AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR)
A helper for the legacy pass manager to create a AAResults object populated to the best of our abilit...
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:773
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept...
Key
PAL metadata keys.
#define F(x, y, z)
Definition: MD5.cpp:55
FunctionModRefBehavior
Summary of how a function affects memory in the program.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:79
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
AAResults & operator()(Function &F)
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:382
FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS)
Returns the behavior when calling the given call site.
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
Checks to see if the specified callsite can clobber the specified memory object.
bool invalidate(Function &Fn, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
Representation for a specific memory location.
Provides information about what library functions are available for the current target.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:642
Class for arbitrary precision integers.
Definition: APInt.h:69
FunctionPass * createBasicAAWrapperPass()
amdgpu Simplify well known AMD library false Value Value * Arg
Analysis pass providing a never-invalidated alias analysis result.
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1962
BasicAAResult(BasicAAResult &&Arg)
BasicAAResult(const BasicAAResult &Arg)
This file provides utility analysis objects describing memory locations.
Establish a view to a call site for examination.
Definition: CallSite.h:714
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
LLVM Value Representation.
Definition: Value.h:73
ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx)
Get the location associated with a pointer argument of a callsite.
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
A container for analyses that lazily runs them and caches their results.
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1960
This header defines various interfaces for pass management in LLVM.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
Legacy wrapper pass to provide the BasicAAResult object.