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  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.
233 class BasicAA : public AnalysisInfoMixin<BasicAA> {
235 
236  static AnalysisKey Key;
237 
238 public:
240 
242 };
243 
244 /// Legacy wrapper pass to provide the BasicAAResult object.
246  std::unique_ptr<BasicAAResult> Result;
247 
248  virtual void anchor();
249 
250 public:
251  static char ID;
252 
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 
262 FunctionPass *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.
267 BasicAAResult 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.
273  Pass &P;
276 
277 public:
281  AAR.emplace(createLegacyPMAAResults(P, F, *BAR));
282  return *AAR;
283  }
284 };
285 
286 } // end namespace llvm
287 
288 #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:233
llvm
Definition: AllocatorList.h:23
Pass
print lazy value Lazy Value Info Printer Pass
Definition: LazyValueInfo.cpp:1947
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:1774
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:1803
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:1817
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::LegacyAARGetter::LegacyAARGetter
LegacyAARGetter(Pass &P)
Definition: BasicAliasAnalysis.h:278
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:205
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:251
llvm::AAResults
Definition: AliasAnalysis.h:456
SI
@ SI
Definition: SIInstrInfo.cpp:7463
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:670
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:935
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:604
llvm::BasicAAResult::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: BasicAliasAnalysis.cpp:789
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:245
llvm::Optional::emplace
void emplace(ArgTypes &&... Args)
Create a new object by constructing it in place with the given arguments.
Definition: Optional.h:262
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:1540
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:64
llvm::LegacyAARGetter::operator()
AAResults & operator()(Function &F)
Definition: BasicAliasAnalysis.h:279
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:803
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:256
llvm::BasicAAResult::getArgModRefInfo
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the location associated with a pointer argument of a callsite.
Definition: BasicAliasAnalysis.cpp:751
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:299
llvm::BasicAAWrapperPass::BasicAAWrapperPass
BasicAAWrapperPass()
Definition: BasicAliasAnalysis.cpp:1782
llvm::createBasicAAWrapperPass
FunctionPass * createBasicAAWrapperPass()
Definition: BasicAliasAnalysis.cpp:1799
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:207
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:1825
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:1164
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:255
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:272
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:668
llvm::AAResultBase
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept.
Definition: AliasAnalysis.h:1064
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:209
llvm::codeview::PublicSymFlags::Function
@ Function