LLVM  14.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 <algorithm>
22 #include <cstdint>
23 #include <memory>
24 #include <utility>
25 
26 namespace llvm {
27 
28 struct AAMDNodes;
29 class AssumptionCache;
30 class BasicBlock;
31 class DataLayout;
32 class DominatorTree;
33 class Function;
34 class GEPOperator;
35 class PHINode;
36 class SelectInst;
37 class TargetLibraryInfo;
38 class PhiValues;
39 class Value;
40 
41 /// This is the AA result object for the basic, local, and stateless alias
42 /// analysis. It implements the AA query interface in an entirely stateless
43 /// manner. As one consequence, it is never invalidated due to IR changes.
44 /// While it does retain some storage, that is used as an optimization and not
45 /// to preserve information from query to query. However it does retain handles
46 /// to various other analyses and must be recomputed when those analyses are.
47 class BasicAAResult : public AAResultBase<BasicAAResult> {
49 
50  const DataLayout &DL;
51  const Function &F;
52  const TargetLibraryInfo &TLI;
53  AssumptionCache &AC;
54  DominatorTree *DT;
55  PhiValues *PV;
56 
57 public:
58  BasicAAResult(const DataLayout &DL, const Function &F,
59  const TargetLibraryInfo &TLI, AssumptionCache &AC,
60  DominatorTree *DT = nullptr, PhiValues *PV = nullptr)
61  : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), PV(PV) {}
62 
64  : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
65  DT(Arg.DT), PV(Arg.PV) {}
67  : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI),
68  AC(Arg.AC), DT(Arg.DT), PV(Arg.PV) {}
69 
70  /// Handle invalidation events in the new pass manager.
71  bool invalidate(Function &Fn, const PreservedAnalyses &PA,
73 
74  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
75  AAQueryInfo &AAQI);
76 
77  ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
78  AAQueryInfo &AAQI);
79 
80  ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
81  AAQueryInfo &AAQI);
82 
83  /// Chases pointers until we find a (constant global) or not.
84  bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
85  bool OrLocal);
86 
87  /// Get the location associated with a pointer argument of a callsite.
88  ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
89 
90  /// Returns the behavior when calling the given call site.
92 
93  /// Returns the behavior when calling the given function. For use when the
94  /// call site is not known.
96 
97 private:
98  struct DecomposedGEP;
99 
100  /// Tracks phi nodes we have visited.
101  ///
102  /// When interpret "Value" pointer equality as value equality we need to make
103  /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
104  /// come from different "iterations" of a cycle and see different values for
105  /// the same "Value" pointer.
106  ///
107  /// The following example shows the problem:
108  /// %p = phi(%alloca1, %addr2)
109  /// %l = load %ptr
110  /// %addr1 = gep, %alloca2, 0, %l
111  /// %addr2 = gep %alloca2, 0, (%l + 1)
112  /// alias(%p, %addr1) -> MayAlias !
113  /// store %l, ...
115 
116  /// Tracks instructions visited by pointsToConstantMemory.
118 
119  static DecomposedGEP
120  DecomposeGEPExpression(const Value *V, const DataLayout &DL,
121  AssumptionCache *AC, DominatorTree *DT);
122 
123  /// A Heuristic for aliasGEP that searches for a constant offset
124  /// between the variables.
125  ///
126  /// GetLinearExpression has some limitations, as generally zext(%x + 1)
127  /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
128  /// will therefore conservatively refuse to decompose these expressions.
129  /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
130  /// the addition overflows.
131  bool
132  constantOffsetHeuristic(const DecomposedGEP &GEP, LocationSize V1Size,
133  LocationSize V2Size, AssumptionCache *AC,
134  DominatorTree *DT);
135 
136  bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
137 
138  void subtractDecomposedGEPs(DecomposedGEP &DestGEP,
139  const DecomposedGEP &SrcGEP);
140 
141  AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
142  const Value *V2, LocationSize V2Size,
143  const Value *UnderlyingV1, const Value *UnderlyingV2,
144  AAQueryInfo &AAQI);
145 
146  AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
147  const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
148 
149  AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
150  const Value *V2, LocationSize V2Size,
151  AAQueryInfo &AAQI);
152 
153  AliasResult aliasCheck(const Value *V1, LocationSize V1Size,
154  const Value *V2, LocationSize V2Size,
155  AAQueryInfo &AAQI);
156 
157  AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
158  const Value *V2, LocationSize V2Size,
159  AAQueryInfo &AAQI, const Value *O1,
160  const Value *O2);
161 };
162 
163 /// Analysis pass providing a never-invalidated alias analysis result.
164 class BasicAA : public AnalysisInfoMixin<BasicAA> {
166 
167  static AnalysisKey Key;
168 
169 public:
171 
173 };
174 
175 /// Legacy wrapper pass to provide the BasicAAResult object.
177  std::unique_ptr<BasicAAResult> Result;
178 
179  virtual void anchor();
180 
181 public:
182  static char ID;
183 
185 
186  BasicAAResult &getResult() { return *Result; }
187  const BasicAAResult &getResult() const { return *Result; }
188 
189  bool runOnFunction(Function &F) override;
190  void getAnalysisUsage(AnalysisUsage &AU) const override;
191 };
192 
193 FunctionPass *createBasicAAWrapperPass();
194 
195 /// A helper for the legacy pass manager to create a \c BasicAAResult object
196 /// populated to the best of our ability for a particular function when inside
197 /// of a \c ModulePass or a \c CallGraphSCCPass.
198 BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F);
199 
200 /// This class is a functor to be used in legacy module or SCC passes for
201 /// computing AA results for a function. We store the results in fields so that
202 /// they live long enough to be queried, but we re-use them each time.
204  Pass &P;
207 
208 public:
212  AAR.emplace(createLegacyPMAAResults(P, F, *BAR));
213  return *AAR;
214  }
215 };
216 
217 } // end namespace llvm
218 
219 #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H
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:164
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
Pass
print lazy value Lazy Value Info Printer Pass
Definition: LazyValueInfo.cpp:1965
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:1904
llvm::Function
Definition: Function.h:62
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:63
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:1933
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::Optional
Definition: APInt.h:33
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:82
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:1947
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::LegacyAARGetter::LegacyAARGetter
LegacyAARGetter(Pass &P)
Definition: BasicAliasAnalysis.h:209
AliasAnalysis.h
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:459
llvm::BasicAAWrapperPass::ID
static char ID
Definition: BasicAliasAnalysis.h:182
llvm::AAResults
Definition: AliasAnalysis.h:508
llvm::LocationSize
Definition: MemoryLocation.h:65
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: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:931
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:727
llvm::BasicAAResult::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: BasicAliasAnalysis.cpp:912
llvm::BasicAAResult::invalidate
bool invalidate(Function &Fn, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
Definition: BasicAliasAnalysis.cpp:89
llvm::BasicAAResult::BasicAAResult
BasicAAResult(BasicAAResult &&Arg)
Definition: BasicAliasAnalysis.h:66
llvm::BasicAAWrapperPass
Legacy wrapper pass to provide the BasicAAResult object.
Definition: BasicAliasAnalysis.h:176
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:58
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: AliasAnalysis.h:149
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:1609
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::LegacyAARGetter::operator()
AAResults & operator()(Function &F)
Definition: BasicAliasAnalysis.h:210
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:397
llvm::GEPOperator
Definition: Operator.h:458
llvm::ReplayInlineScope::Function
@ Function
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:926
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:187
llvm::BasicAAResult::getArgModRefInfo
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the location associated with a pointer argument of a callsite.
Definition: BasicAliasAnalysis.cpp:874
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:263
llvm::BasicAAResult
This is the AA result object for the basic, local, and stateless alias analysis.
Definition: BasicAliasAnalysis.h:47
llvm::BasicAAWrapperPass::BasicAAWrapperPass
BasicAAWrapperPass()
Definition: BasicAliasAnalysis.cpp:1912
llvm::createBasicAAWrapperPass
FunctionPass * createBasicAAWrapperPass()
Definition: BasicAliasAnalysis.cpp:1929
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:221
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:1955
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
P
#define P(N)
llvm::PHINode
Definition: Instructions.h:2633
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
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::BasicAAWrapperPass::getResult
BasicAAResult & getResult()
Definition: BasicAliasAnalysis.h:186
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:203
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:791
llvm::AAResultBase
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept.
Definition: AliasAnalysis.h:1131
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:209