LLVM  16.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 <optional>
23 #include <utility>
24 
25 namespace llvm {
26 
27 class AssumptionCache;
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 {
45  const DataLayout &DL;
46  const Function &F;
47  const TargetLibraryInfo &TLI;
48  AssumptionCache &AC;
49  DominatorTree *DT;
50  PhiValues *PV;
51 
52 public:
53  BasicAAResult(const DataLayout &DL, const Function &F,
54  const TargetLibraryInfo &TLI, AssumptionCache &AC,
55  DominatorTree *DT = nullptr, PhiValues *PV = nullptr)
56  : DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), PV(PV) {}
57 
59  : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
60  DT(Arg.DT), PV(Arg.PV) {}
62  : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI),
63  AC(Arg.AC), DT(Arg.DT), PV(Arg.PV) {}
64 
65  /// Handle invalidation events in the new pass manager.
66  bool invalidate(Function &Fn, const PreservedAnalyses &PA,
68 
69  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
70  AAQueryInfo &AAQI);
71 
72  ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
73  AAQueryInfo &AAQI);
74 
75  ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
76  AAQueryInfo &AAQI);
77 
78  /// Returns a bitmask that should be unconditionally applied to the ModRef
79  /// info of a memory location. This allows us to eliminate Mod and/or Ref
80  /// from the ModRef info based on the knowledge that the memory location
81  /// points to constant and/or locally-invariant memory.
82  ///
83  /// If IgnoreLocals is true, then this method returns NoModRef for memory
84  /// that points to a local alloca.
86  bool IgnoreLocals = false);
87 
88  /// Get the location associated with a pointer argument of a callsite.
89  ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
90 
91  /// Returns the behavior when calling the given call site.
93 
94  /// Returns the behavior when calling the given function. For use when the
95  /// call site is not known.
97 
98 private:
99  struct DecomposedGEP;
100 
101  /// Tracks instructions visited by pointsToConstantMemory.
103 
104  static DecomposedGEP
105  DecomposeGEPExpression(const Value *V, const DataLayout &DL,
106  AssumptionCache *AC, DominatorTree *DT);
107 
108  /// A Heuristic for aliasGEP that searches for a constant offset
109  /// between the variables.
110  ///
111  /// GetLinearExpression has some limitations, as generally zext(%x + 1)
112  /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
113  /// will therefore conservatively refuse to decompose these expressions.
114  /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
115  /// the addition overflows.
116  bool constantOffsetHeuristic(const DecomposedGEP &GEP, LocationSize V1Size,
117  LocationSize V2Size, AssumptionCache *AC,
118  DominatorTree *DT, const AAQueryInfo &AAQI);
119 
120  bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2,
121  const AAQueryInfo &AAQI);
122 
123  void subtractDecomposedGEPs(DecomposedGEP &DestGEP,
124  const DecomposedGEP &SrcGEP,
125  const AAQueryInfo &AAQI);
126 
127  AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
128  const Value *V2, LocationSize V2Size,
129  const Value *UnderlyingV1, const Value *UnderlyingV2,
130  AAQueryInfo &AAQI);
131 
132  AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
133  const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
134 
135  AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
136  const Value *V2, LocationSize V2Size,
137  AAQueryInfo &AAQI);
138 
139  AliasResult aliasCheck(const Value *V1, LocationSize V1Size,
140  const Value *V2, LocationSize V2Size,
141  AAQueryInfo &AAQI);
142 
143  AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
144  const Value *V2, LocationSize V2Size,
145  AAQueryInfo &AAQI, const Value *O1,
146  const Value *O2);
147 };
148 
149 /// Analysis pass providing a never-invalidated alias analysis result.
150 class BasicAA : public AnalysisInfoMixin<BasicAA> {
152 
153  static AnalysisKey Key;
154 
155 public:
157 
159 };
160 
161 /// Legacy wrapper pass to provide the BasicAAResult object.
163  std::unique_ptr<BasicAAResult> Result;
164 
165  virtual void anchor();
166 
167 public:
168  static char ID;
169 
171 
172  BasicAAResult &getResult() { return *Result; }
173  const BasicAAResult &getResult() const { return *Result; }
174 
175  bool runOnFunction(Function &F) override;
176  void getAnalysisUsage(AnalysisUsage &AU) const override;
177 };
178 
179 FunctionPass *createBasicAAWrapperPass();
180 
181 /// A helper for the legacy pass manager to create a \c BasicAAResult object
182 /// populated to the best of our ability for a particular function when inside
183 /// of a \c ModulePass or a \c CallGraphSCCPass.
184 BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F);
185 
186 /// This class is a functor to be used in legacy module or SCC passes for
187 /// computing AA results for a function. We store the results in fields so that
188 /// they live long enough to be queried, but we re-use them each time.
190  Pass &P;
191  std::optional<BasicAAResult> BAR;
192  std::optional<AAResults> AAR;
193 
194 public:
197  BAR.emplace(createLegacyPMBasicAAResult(P, F));
198  AAR.emplace(createLegacyPMAAResults(P, F, *BAR));
199  return *AAR;
200  }
201 };
202 
203 } // end namespace llvm
204 
205 #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:150
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Pass
print lazy value Lazy Value Info Printer Pass
Definition: LazyValueInfo.cpp:1999
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:1770
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:58
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:1799
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:83
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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:1813
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::LegacyAARGetter::LegacyAARGetter
LegacyAARGetter(Pass &P)
Definition: BasicAliasAnalysis.h:195
AliasAnalysis.h
llvm::MemoryEffects
Summary of how a function affects memory in the program.
Definition: ModRef.h:63
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:233
llvm::BasicAAResult::getMemoryEffects
MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI)
Returns the behavior when calling the given call site.
Definition: BasicAliasAnalysis.cpp:757
llvm::BasicAAWrapperPass::ID
static char ID
Definition: BasicAliasAnalysis.h:168
llvm::AAResults
Definition: AliasAnalysis.h:294
llvm::LocationSize
Definition: MemoryLocation.h:67
SI
@ SI
Definition: SIInstrInfo.cpp:7966
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::BasicAAResult::getModRefInfoMask
ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool IgnoreLocals=false)
Returns a bitmask that should be unconditionally applied to the ModRef info of a memory location.
Definition: BasicAliasAnalysis.cpp:680
SmallPtrSet.h
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
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:852
llvm::BasicAAResult::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: BasicAliasAnalysis.cpp:827
llvm::BasicAAResult::invalidate
bool invalidate(Function &Fn, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
Definition: BasicAliasAnalysis.cpp:83
llvm::BasicAAResult::BasicAAResult
BasicAAResult(BasicAAResult &&Arg)
Definition: BasicAliasAnalysis.h:61
llvm::BasicAAWrapperPass
Legacy wrapper pass to provide the BasicAAResult object.
Definition: BasicAliasAnalysis.h:162
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:53
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: ModRef.h:27
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:1861
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1735
llvm::LegacyAARGetter::operator()
AAResults & operator()(Function &F)
Definition: BasicAliasAnalysis.h:196
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:841
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:173
llvm::BasicAAResult::getArgModRefInfo
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the location associated with a pointer argument of a callsite.
Definition: BasicAliasAnalysis.cpp:790
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
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:1778
llvm::createBasicAAWrapperPass
FunctionPass * createBasicAAWrapperPass()
Definition: BasicAliasAnalysis.cpp:1795
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:226
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:1821
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:2697
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1175
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:171
llvm::BasicAAWrapperPass::getResult
BasicAAResult & getResult()
Definition: BasicAliasAnalysis.h:172
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:189
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::AAResultBase
A base class to help implement the function alias analysis results concept.
Definition: AliasAnalysis.h:785
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:211
llvm::codeview::PublicSymFlags::Function
@ Function