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 <utility>
22
23namespace llvm {
24
25class AssumptionCache;
26class DataLayout;
27class DominatorTree;
28class Function;
29class GEPOperator;
30class PHINode;
31class SelectInst;
32class TargetLibraryInfo;
33class Value;
34
35/// This is the AA result object for the basic, local, and stateless alias
36/// analysis. It implements the AA query interface in an entirely stateless
37/// manner. As one consequence, it is never invalidated due to IR changes.
38/// While it does retain some storage, that is used as an optimization and not
39/// to preserve information from query to query. However it does retain handles
40/// to various other analyses and must be recomputed when those analyses are.
42 const DataLayout &DL;
43 const Function &F;
44 const TargetLibraryInfo &TLI;
46 DominatorTree *DT;
47
48public:
49 BasicAAResult(const DataLayout &DL, const Function &F,
50 const TargetLibraryInfo &TLI, AssumptionCache &AC,
51 DominatorTree *DT = nullptr)
52 : DL(DL), F(F), TLI(TLI), AC(AC), DT(DT) {}
53
55 : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
56 DT(Arg.DT) {}
58 : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI),
59 AC(Arg.AC), DT(Arg.DT) {}
60
61 /// Handle invalidation events in the new pass manager.
62 bool invalidate(Function &Fn, const PreservedAnalyses &PA,
64
65 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
66 AAQueryInfo &AAQI, const Instruction *CtxI);
67
68 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
69 AAQueryInfo &AAQI);
70
71 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
72 AAQueryInfo &AAQI);
73
74 /// Returns a bitmask that should be unconditionally applied to the ModRef
75 /// info of a memory location. This allows us to eliminate Mod and/or Ref
76 /// from the ModRef info based on the knowledge that the memory location
77 /// points to constant and/or locally-invariant memory.
78 ///
79 /// If IgnoreLocals is true, then this method returns NoModRef for memory
80 /// that points to a local alloca.
82 bool IgnoreLocals = false);
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
94private:
95 struct DecomposedGEP;
96
97 /// Tracks instructions visited by pointsToConstantMemory.
99
100 static DecomposedGEP
101 DecomposeGEPExpression(const Value *V, const DataLayout &DL,
103
104 /// A Heuristic for aliasGEP that searches for a constant offset
105 /// between the variables.
106 ///
107 /// GetLinearExpression has some limitations, as generally zext(%x + 1)
108 /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
109 /// will therefore conservatively refuse to decompose these expressions.
110 /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
111 /// the addition overflows.
112 bool constantOffsetHeuristic(const DecomposedGEP &GEP, LocationSize V1Size,
113 LocationSize V2Size, AssumptionCache *AC,
114 DominatorTree *DT, const AAQueryInfo &AAQI);
115
116 bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2,
117 const AAQueryInfo &AAQI);
118
119 void subtractDecomposedGEPs(DecomposedGEP &DestGEP,
120 const DecomposedGEP &SrcGEP,
121 const AAQueryInfo &AAQI);
122
123 AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
124 const Value *V2, LocationSize V2Size,
125 const Value *UnderlyingV1, const Value *UnderlyingV2,
126 AAQueryInfo &AAQI);
127
128 AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
129 const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
130
131 AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
132 const Value *V2, LocationSize V2Size,
133 AAQueryInfo &AAQI);
134
135 AliasResult aliasCheck(const Value *V1, LocationSize V1Size, const Value *V2,
136 LocationSize V2Size, AAQueryInfo &AAQI,
137 const Instruction *CtxI);
138
139 AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
140 const Value *V2, LocationSize V2Size,
141 AAQueryInfo &AAQI, const Value *O1,
142 const Value *O2);
143};
144
145/// Analysis pass providing a never-invalidated alias analysis result.
146class BasicAA : public AnalysisInfoMixin<BasicAA> {
148
149 static AnalysisKey Key;
150
151public:
153
155};
156
157/// Legacy wrapper pass to provide the BasicAAResult object.
159 std::unique_ptr<BasicAAResult> Result;
160
161 virtual void anchor();
162
163public:
164 static char ID;
165
167
168 BasicAAResult &getResult() { return *Result; }
169 const BasicAAResult &getResult() const { return *Result; }
170
171 bool runOnFunction(Function &F) override;
172 void getAnalysisUsage(AnalysisUsage &AU) const override;
173};
174
175FunctionPass *createBasicAAWrapperPass();
176
177} // end namespace llvm
178
179#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:690
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:649
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:1227
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:164
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:172
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:1853
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:414
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:89