LLVM 17.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
18#include "llvm/IR/PassManager.h"
19#include "llvm/Pass.h"
20#include <memory>
21#include <optional>
22#include <utility>
23
24namespace llvm {
25
26class AssumptionCache;
27class DataLayout;
28class DominatorTree;
29class Function;
30class GEPOperator;
31class PHINode;
32class SelectInst;
33class TargetLibraryInfo;
34class PhiValues;
35class Value;
36
37/// This is the AA result object for the basic, local, and stateless alias
38/// analysis. It implements the AA query interface in an entirely stateless
39/// manner. As one consequence, it is never invalidated due to IR changes.
40/// While it does retain some storage, that is used as an optimization and not
41/// to preserve information from query to query. However it does retain handles
42/// to various other analyses and must be recomputed when those analyses are.
44 const DataLayout &DL;
45 const Function &F;
46 const TargetLibraryInfo &TLI;
48 DominatorTree *DT;
49
50public:
51 BasicAAResult(const DataLayout &DL, const Function &F,
52 const TargetLibraryInfo &TLI, AssumptionCache &AC,
53 DominatorTree *DT = nullptr)
54 : DL(DL), F(F), TLI(TLI), AC(AC), DT(DT) {}
55
57 : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
58 DT(Arg.DT) {}
60 : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI),
61 AC(Arg.AC), DT(Arg.DT) {}
62
63 /// Handle invalidation events in the new pass manager.
64 bool invalidate(Function &Fn, const PreservedAnalyses &PA,
66
67 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
68 AAQueryInfo &AAQI, const Instruction *CtxI);
69
70 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
71 AAQueryInfo &AAQI);
72
73 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
74 AAQueryInfo &AAQI);
75
76 /// Returns a bitmask that should be unconditionally applied to the ModRef
77 /// info of a memory location. This allows us to eliminate Mod and/or Ref
78 /// from the ModRef info based on the knowledge that the memory location
79 /// points to constant and/or locally-invariant memory.
80 ///
81 /// If IgnoreLocals is true, then this method returns NoModRef for memory
82 /// that points to a local alloca.
84 bool IgnoreLocals = false);
85
86 /// Get the location associated with a pointer argument of a callsite.
87 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
88
89 /// Returns the behavior when calling the given call site.
91
92 /// Returns the behavior when calling the given function. For use when the
93 /// call site is not known.
95
96private:
97 struct DecomposedGEP;
98
99 /// Tracks instructions visited by pointsToConstantMemory.
101
102 static DecomposedGEP
103 DecomposeGEPExpression(const Value *V, const DataLayout &DL,
105
106 /// A Heuristic for aliasGEP that searches for a constant offset
107 /// between the variables.
108 ///
109 /// GetLinearExpression has some limitations, as generally zext(%x + 1)
110 /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
111 /// will therefore conservatively refuse to decompose these expressions.
112 /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
113 /// the addition overflows.
114 bool constantOffsetHeuristic(const DecomposedGEP &GEP, LocationSize V1Size,
115 LocationSize V2Size, AssumptionCache *AC,
116 DominatorTree *DT, const AAQueryInfo &AAQI);
117
118 bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2,
119 const AAQueryInfo &AAQI);
120
121 void subtractDecomposedGEPs(DecomposedGEP &DestGEP,
122 const DecomposedGEP &SrcGEP,
123 const AAQueryInfo &AAQI);
124
125 AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
126 const Value *V2, LocationSize V2Size,
127 const Value *UnderlyingV1, const Value *UnderlyingV2,
128 AAQueryInfo &AAQI);
129
130 AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
131 const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
132
133 AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
134 const Value *V2, LocationSize V2Size,
135 AAQueryInfo &AAQI);
136
137 AliasResult aliasCheck(const Value *V1, LocationSize V1Size, const Value *V2,
138 LocationSize V2Size, AAQueryInfo &AAQI,
139 const Instruction *CtxI);
140
141 AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
142 const Value *V2, LocationSize V2Size,
143 AAQueryInfo &AAQI, const Value *O1,
144 const Value *O2);
145};
146
147/// Analysis pass providing a never-invalidated alias analysis result.
148class BasicAA : public AnalysisInfoMixin<BasicAA> {
150
151 static AnalysisKey Key;
152
153public:
155
157};
158
159/// Legacy wrapper pass to provide the BasicAAResult object.
161 std::unique_ptr<BasicAAResult> Result;
162
163 virtual void anchor();
164
165public:
166 static char ID;
167
169
170 BasicAAResult &getResult() { return *Result; }
171 const BasicAAResult &getResult() const { return *Result; }
172
173 bool runOnFunction(Function &F) override;
174 void getAnalysisUsage(AnalysisUsage &AU) const override;
175};
176
177FunctionPass *createBasicAAWrapperPass();
178
179/// A helper for the legacy pass manager to create a \c BasicAAResult object
180/// populated to the best of our ability for a particular function when inside
181/// of a \c ModulePass or a \c CallGraphSCCPass.
182BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F);
183
184/// This class is a functor to be used in legacy module or SCC passes for
185/// computing AA results for a function. We store the results in fields so that
186/// they live long enough to be queried, but we re-use them each time.
188 Pass &P;
189 std::optional<BasicAAResult> BAR;
190 std::optional<AAResults> AAR;
191
192public:
195 BAR.emplace(createLegacyPMBasicAAResult(P, F));
196 AAR.emplace(createLegacyPMAAResults(P, F, *BAR));
197 return *AAR;
198 }
199};
200
201} // end namespace llvm
202
203#endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Hexagon Common GEP
#define F(x, y, z)
Definition: MD5.cpp:55
#define P(N)
This header defines various interfaces for pass management in LLVM.
@ SI
This file defines the SmallPtrSet class.
This class stores info we want to provide to or retain within an alias query.
A base class to help implement the function alias analysis results concept.
The possible results of an alias query.
Definition: AliasAnalysis.h:83
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
Represent the analysis usage information of a pass.
A cache of @llvm.assume calls within a function.
This is the AA result object for the basic, local, and stateless alias analysis.
BasicAAResult(const DataLayout &DL, const Function &F, const TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree *DT=nullptr)
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Checks to see if the specified callsite can clobber the specified memory object.
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the location associated with a pointer argument of a callsite.
BasicAAResult(BasicAAResult &&Arg)
MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI)
Returns the behavior when calling the given call site.
BasicAAResult(const BasicAAResult &Arg)
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.
bool invalidate(Function &Fn, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI, const Instruction *CtxI)
Legacy wrapper pass to provide the BasicAAResult object.
const BasicAAResult & getResult() const
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Analysis pass providing a never-invalidated alias analysis result.
BasicAAResult run(Function &F, FunctionAnalysisManager &AM)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1186
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
This class is a functor to be used in legacy module or SCC passes for computing AA results for a func...
AAResults & operator()(Function &F)
Summary of how a function affects memory in the program.
Definition: ModRef.h:63
Representation for a specific memory location.
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
This class represents the LLVM 'select' instruction.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
Provides information about what library functions are available for the current target.
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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...
FunctionPass * createBasicAAWrapperPass()
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: ModRef.h:27
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:1946
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: BitVector.h:858
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69