LLVM 18.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 Value;
35
36/// This is the AA result object for the basic, local, and stateless alias
37/// analysis. It implements the AA query interface in an entirely stateless
38/// manner. As one consequence, it is never invalidated due to IR changes.
39/// While it does retain some storage, that is used as an optimization and not
40/// to preserve information from query to query. However it does retain handles
41/// to various other analyses and must be recomputed when those analyses are.
43 const DataLayout &DL;
44 const Function &F;
45 const TargetLibraryInfo &TLI;
47 DominatorTree *DT;
48
49public:
50 BasicAAResult(const DataLayout &DL, const Function &F,
51 const TargetLibraryInfo &TLI, AssumptionCache &AC,
52 DominatorTree *DT = nullptr)
53 : DL(DL), F(F), TLI(TLI), AC(AC), DT(DT) {}
54
56 : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
57 DT(Arg.DT) {}
59 : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI),
60 AC(Arg.AC), DT(Arg.DT) {}
61
62 /// Handle invalidation events in the new pass manager.
63 bool invalidate(Function &Fn, const PreservedAnalyses &PA,
65
66 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
67 AAQueryInfo &AAQI, const Instruction *CtxI);
68
69 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
70 AAQueryInfo &AAQI);
71
72 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
73 AAQueryInfo &AAQI);
74
75 /// Returns a bitmask that should be unconditionally applied to the ModRef
76 /// info of a memory location. This allows us to eliminate Mod and/or Ref
77 /// from the ModRef info based on the knowledge that the memory location
78 /// points to constant and/or locally-invariant memory.
79 ///
80 /// If IgnoreLocals is true, then this method returns NoModRef for memory
81 /// that points to a local alloca.
83 bool IgnoreLocals = false);
84
85 /// Get the location associated with a pointer argument of a callsite.
86 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
87
88 /// Returns the behavior when calling the given call site.
90
91 /// Returns the behavior when calling the given function. For use when the
92 /// call site is not known.
94
95private:
96 struct DecomposedGEP;
97
98 /// Tracks instructions visited by pointsToConstantMemory.
100
101 static DecomposedGEP
102 DecomposeGEPExpression(const Value *V, const DataLayout &DL,
104
105 /// A Heuristic for aliasGEP that searches for a constant offset
106 /// between the variables.
107 ///
108 /// GetLinearExpression has some limitations, as generally zext(%x + 1)
109 /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
110 /// will therefore conservatively refuse to decompose these expressions.
111 /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
112 /// the addition overflows.
113 bool constantOffsetHeuristic(const DecomposedGEP &GEP, LocationSize V1Size,
114 LocationSize V2Size, AssumptionCache *AC,
115 DominatorTree *DT, const AAQueryInfo &AAQI);
116
117 bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2,
118 const AAQueryInfo &AAQI);
119
120 void subtractDecomposedGEPs(DecomposedGEP &DestGEP,
121 const DecomposedGEP &SrcGEP,
122 const AAQueryInfo &AAQI);
123
124 AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
125 const Value *V2, LocationSize V2Size,
126 const Value *UnderlyingV1, const Value *UnderlyingV2,
127 AAQueryInfo &AAQI);
128
129 AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
130 const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
131
132 AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
133 const Value *V2, LocationSize V2Size,
134 AAQueryInfo &AAQI);
135
136 AliasResult aliasCheck(const Value *V1, LocationSize V1Size, const Value *V2,
137 LocationSize V2Size, AAQueryInfo &AAQI,
138 const Instruction *CtxI);
139
140 AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
141 const Value *V2, LocationSize V2Size,
142 AAQueryInfo &AAQI, const Value *O1,
143 const Value *O2);
144};
145
146/// Analysis pass providing a never-invalidated alias analysis result.
147class BasicAA : public AnalysisInfoMixin<BasicAA> {
149
150 static AnalysisKey Key;
151
152public:
154
156};
157
158/// Legacy wrapper pass to provide the BasicAAResult object.
160 std::unique_ptr<BasicAAResult> Result;
161
162 virtual void anchor();
163
164public:
165 static char ID;
166
168
169 BasicAAResult &getResult() { return *Result; }
170 const BasicAAResult &getResult() const { return *Result; }
171
172 bool runOnFunction(Function &F) override;
173 void getAnalysisUsage(AnalysisUsage &AU) const override;
174};
175
176FunctionPass *createBasicAAWrapperPass();
177
178} // end namespace llvm
179
180#endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Hexagon Common GEP
#define F(x, y, z)
Definition: MD5.cpp:55
StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)
This header defines various interfaces for pass management in LLVM.
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:82
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:1190
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:311
Representation for a specific memory location.
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:451
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
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:1854
Implement std::hash so that hash_code can be used in STL containers.
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