LLVM  13.0.0git
BasicAliasAnalysis.h
Go to the documentation of this file.
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"
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> {
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)
64  : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), PV(PV) {}
65 
67  : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
68  DT(Arg.DT), PV(Arg.PV) {}
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,
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.
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  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 
122  void dump() const {
123  print(dbgs());
124  dbgs() << "\n";
125  }
126  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 
149  void dump() const {
150  print(dbgs());
151  dbgs() << "\n";
152  }
153  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> {
238 
239  static AnalysisKey Key;
240 
241 public:
243 
245 };
246 
247 /// Legacy wrapper pass to provide the BasicAAResult object.
249  std::unique_ptr<BasicAAResult> Result;
250 
251  virtual void anchor();
252 
253 public:
254  static char ID;
255 
257 
258  BasicAAResult &getResult() { return *Result; }
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.
276  Pass &P;
279 
280 public:
284  AAR.emplace(createLegacyPMAAResults(P, F, *BAR));
285  return *AAR;
286  }
287 };
288 
289 } // end namespace llvm
290 
291 #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::BasicAA
Analysis pass providing a never-invalidated alias analysis result.
Definition: BasicAliasAnalysis.h:236
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
Pass
print lazy value Lazy Value Info Printer Pass
Definition: LazyValueInfo.cpp:1966
Optional.h
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::BasicAA::run
BasicAAResult run(Function &F, FunctionAnalysisManager &AM)
Definition: BasicAliasAnalysis.cpp:1792
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
llvm::Function
Definition: Function.h:61
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::BasicAAResult::BasicAAResult
BasicAAResult(const BasicAAResult &Arg)
Definition: BasicAliasAnalysis.h:66
llvm::BasicAAWrapperPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: BasicAliasAnalysis.cpp:1821
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
DenseMap.h
llvm::Optional
Definition: APInt.h:33
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
llvm::BasicAAWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: BasicAliasAnalysis.cpp:1835
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::LegacyAARGetter::LegacyAARGetter
LegacyAARGetter(Pass &P)
Definition: BasicAliasAnalysis.h:281
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:414
llvm::BasicAAWrapperPass::ID
static char ID
Definition: BasicAliasAnalysis.h:254
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::Instruction
Definition: Instruction.h:45
SmallPtrSet.h
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:656
llvm::createLegacyPMAAResults
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...
Definition: AliasAnalysis.cpp:937
llvm::BasicAAResult::pointsToConstantMemory
bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal)
Chases pointers until we find a (constant global) or not.
Definition: BasicAliasAnalysis.cpp:613
llvm::BasicAAResult::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: BasicAliasAnalysis.cpp:798
llvm::BasicAAResult::invalidate
bool invalidate(Function &Fn, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
Definition: BasicAliasAnalysis.cpp:98
llvm::BasicAAResult::BasicAAResult
BasicAAResult(BasicAAResult &&Arg)
Definition: BasicAliasAnalysis.h:69
llvm::BasicAAWrapperPass
Legacy wrapper pass to provide the BasicAAResult object.
Definition: BasicAliasAnalysis.h:248
llvm::Optional::emplace
void emplace(ArgTypes &&... Args)
Create a new object by constructing it in place with the given arguments.
Definition: Optional.h:264
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::BasicAAResult::BasicAAResult
BasicAAResult(const DataLayout &DL, const Function &F, const TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree *DT=nullptr, PhiValues *PV=nullptr)
Definition: BasicAliasAnalysis.h:61
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: AliasAnalysis.h:148
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1592
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::LegacyAARGetter::operator()
AAResults & operator()(Function &F)
Definition: BasicAliasAnalysis.h:282
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:391
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::BasicAAResult::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Checks to see if the specified callsite can clobber the specified memory object.
Definition: BasicAliasAnalysis.cpp:812
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::BasicAAWrapperPass::getResult
const BasicAAResult & getResult() const
Definition: BasicAliasAnalysis.h:259
llvm::BasicAAResult::getArgModRefInfo
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the location associated with a pointer argument of a callsite.
Definition: BasicAliasAnalysis.cpp:760
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::FunctionModRefBehavior
FunctionModRefBehavior
Summary of how a function affects memory in the program.
Definition: AliasAnalysis.h:262
llvm::BasicAAResult
This is the AA result object for the basic, local, and stateless alias analysis.
Definition: BasicAliasAnalysis.h:50
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:297
llvm::BasicAAWrapperPass::BasicAAWrapperPass
BasicAAWrapperPass()
Definition: BasicAliasAnalysis.cpp:1800
llvm::createBasicAAWrapperPass
FunctionPass * createBasicAAWrapperPass()
Definition: BasicAliasAnalysis.cpp:1817
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
std
Definition: BitVector.h:838
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
PassManager.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
llvm::createLegacyPMBasicAAResult
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...
Definition: BasicAliasAnalysis.cpp:1843
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
llvm::PhiValues
Class for calculating and caching the underlying values of phis in a function.
Definition: PhiValues.h:41
SmallVector.h
P
#define P(N)
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::BasicAAWrapperPass::getResult
BasicAAResult & getResult()
Definition: BasicAliasAnalysis.h:258
llvm::LegacyAARGetter
This class is a functor to be used in legacy module or SCC passes for computing AA results for a func...
Definition: BasicAliasAnalysis.h:275
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::BasicAAResult::getModRefBehavior
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Returns the behavior when calling the given call site.
Definition: BasicAliasAnalysis.cpp:677
llvm::AAResultBase
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept.
Definition: AliasAnalysis.h:1076
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:209
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58