LLVM  15.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/Optional.h"
17 #include "llvm/ADT/SmallPtrSet.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> {
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 
61  : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
62  DT(Arg.DT), PV(Arg.PV) {}
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,
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.
89 
90  /// Returns the behavior when calling the given function. For use when the
91  /// call site is not known.
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, ...
112 
113  /// Tracks instructions visited by pointsToConstantMemory.
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> {
163 
164  static AnalysisKey Key;
165 
166 public:
168 
170 };
171 
172 /// Legacy wrapper pass to provide the BasicAAResult object.
174  std::unique_ptr<BasicAAResult> Result;
175 
176  virtual void anchor();
177 
178 public:
179  static char ID;
180 
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.
201  Pass &P;
204 
205 public:
209  AAR.emplace(createLegacyPMAAResults(P, F, *BAR));
210  return *AAR;
211  }
212 };
213 
214 } // end namespace llvm
215 
216 #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::BasicAA
Analysis pass providing a never-invalidated alias analysis result.
Definition: BasicAliasAnalysis.h:161
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
Pass
print lazy value Lazy Value Info Printer Pass
Definition: LazyValueInfo.cpp:1978
Optional.h
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::BasicAA::run
BasicAAResult run(Function &F, FunctionAnalysisManager &AM)
Definition: BasicAliasAnalysis.cpp:1886
llvm::Function
Definition: Function.h:60
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:60
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:1915
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::Optional
Definition: APInt.h:33
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
llvm::SmallPtrSet< const BasicBlock *, 8 >
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:1929
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::LegacyAARGetter::LegacyAARGetter
LegacyAARGetter(Pass &P)
Definition: BasicAliasAnalysis.h:206
AliasAnalysis.h
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:462
llvm::BasicAAWrapperPass::ID
static char ID
Definition: BasicAliasAnalysis.h:179
llvm::AAResults
Definition: AliasAnalysis.h:511
llvm::LocationSize
Definition: MemoryLocation.h:66
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
SmallPtrSet.h
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:667
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:932
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:705
llvm::BasicAAResult::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: BasicAliasAnalysis.cpp:890
llvm::BasicAAResult::invalidate
bool invalidate(Function &Fn, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
Definition: BasicAliasAnalysis.cpp:87
llvm::BasicAAResult::BasicAAResult
BasicAAResult(BasicAAResult &&Arg)
Definition: BasicAliasAnalysis.h:63
llvm::BasicAAWrapperPass
Legacy wrapper pass to provide the BasicAAResult object.
Definition: BasicAliasAnalysis.h:173
llvm::Optional::emplace
void emplace(ArgTypes &&... Args)
Create a new object by constructing it in place with the given arguments.
Definition: Optional.h:261
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::BasicAAResult::BasicAAResult
BasicAAResult(const DataLayout &DL, const Function &F, const TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree *DT=nullptr, PhiValues *PV=nullptr)
Definition: BasicAliasAnalysis.h:55
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:1665
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1737
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::LegacyAARGetter::operator()
AAResults & operator()(Function &F)
Definition: BasicAliasAnalysis.h:207
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::GEPOperator
Definition: Operator.h:375
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:904
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::BasicAAWrapperPass::getResult
const BasicAAResult & getResult() const
Definition: BasicAliasAnalysis.h:184
llvm::BasicAAResult::getArgModRefInfo
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the location associated with a pointer argument of a callsite.
Definition: BasicAliasAnalysis.cpp:852
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:44
llvm::BasicAAWrapperPass::BasicAAWrapperPass
BasicAAWrapperPass()
Definition: BasicAliasAnalysis.cpp:1894
llvm::createBasicAAWrapperPass
FunctionPass * createBasicAAWrapperPass()
Definition: BasicAliasAnalysis.cpp:1911
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
std
Definition: BitVector.h:851
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:222
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:1937
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:40
P
#define P(N)
llvm::PHINode
Definition: Instructions.h:2664
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::BasicAAWrapperPass::getResult
BasicAAResult & getResult()
Definition: BasicAliasAnalysis.h:183
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:200
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::BasicAAResult::getModRefBehavior
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Returns the behavior when calling the given call site.
Definition: BasicAliasAnalysis.cpp:769
llvm::AAResultBase
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept.
Definition: AliasAnalysis.h:1134
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
llvm::codeview::PublicSymFlags::Function
@ Function