LLVM 19.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 /// Use getDT() instead of accessing this member directly, in order to
47 /// respect the AAQI.UseDominatorTree option.
48 DominatorTree *DT_;
49
50 DominatorTree *getDT(const AAQueryInfo &AAQI) const {
51 return AAQI.UseDominatorTree ? DT_ : nullptr;
52 }
53
54public:
55 BasicAAResult(const DataLayout &DL, const Function &F,
56 const TargetLibraryInfo &TLI, AssumptionCache &AC,
57 DominatorTree *DT = nullptr)
58 : DL(DL), F(F), TLI(TLI), AC(AC), DT_(DT) {}
59
61 : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
62 DT_(Arg.DT_) {}
64 : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI),
65 AC(Arg.AC), DT_(Arg.DT_) {}
66
67 /// Handle invalidation events in the new pass manager.
68 bool invalidate(Function &Fn, const PreservedAnalyses &PA,
70
71 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
72 AAQueryInfo &AAQI, const Instruction *CtxI);
73
74 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
75 AAQueryInfo &AAQI);
76
77 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
78 AAQueryInfo &AAQI);
79
80 /// Returns a bitmask that should be unconditionally applied to the ModRef
81 /// info of a memory location. This allows us to eliminate Mod and/or Ref
82 /// from the ModRef info based on the knowledge that the memory location
83 /// points to constant and/or locally-invariant memory.
84 ///
85 /// If IgnoreLocals is true, then this method returns NoModRef for memory
86 /// that points to a local alloca.
88 bool IgnoreLocals = false);
89
90 /// Get the location associated with a pointer argument of a callsite.
91 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
92
93 /// Returns the behavior when calling the given call site.
95
96 /// Returns the behavior when calling the given function. For use when the
97 /// call site is not known.
99
100private:
101 struct DecomposedGEP;
102
103 /// Tracks instructions visited by pointsToConstantMemory.
105
106 static DecomposedGEP
107 DecomposeGEPExpression(const Value *V, const DataLayout &DL,
109
110 /// A Heuristic for aliasGEP that searches for a constant offset
111 /// between the variables.
112 ///
113 /// GetLinearExpression has some limitations, as generally zext(%x + 1)
114 /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
115 /// will therefore conservatively refuse to decompose these expressions.
116 /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
117 /// the addition overflows.
118 bool constantOffsetHeuristic(const DecomposedGEP &GEP, LocationSize V1Size,
119 LocationSize V2Size, AssumptionCache *AC,
120 DominatorTree *DT, const AAQueryInfo &AAQI);
121
122 bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2,
123 const AAQueryInfo &AAQI);
124
125 void subtractDecomposedGEPs(DecomposedGEP &DestGEP,
126 const DecomposedGEP &SrcGEP,
127 const AAQueryInfo &AAQI);
128
129 AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
130 const Value *V2, LocationSize V2Size,
131 const Value *UnderlyingV1, const Value *UnderlyingV2,
132 AAQueryInfo &AAQI);
133
134 AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
135 const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
136
137 AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
138 const Value *V2, LocationSize V2Size,
139 AAQueryInfo &AAQI);
140
141 AliasResult aliasCheck(const Value *V1, LocationSize V1Size, const Value *V2,
142 LocationSize V2Size, AAQueryInfo &AAQI,
143 const Instruction *CtxI);
144
145 AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
146 const Value *V2, LocationSize V2Size,
147 AAQueryInfo &AAQI, const Value *O1,
148 const Value *O2);
149};
150
151/// Analysis pass providing a never-invalidated alias analysis result.
152class BasicAA : public AnalysisInfoMixin<BasicAA> {
154
155 static AnalysisKey Key;
156
157public:
159
161};
162
163/// Legacy wrapper pass to provide the BasicAAResult object.
165 std::unique_ptr<BasicAAResult> Result;
166
167 virtual void anchor();
168
169public:
170 static char ID;
171
173
174 BasicAAResult &getResult() { return *Result; }
175 const BasicAAResult &getResult() const { return *Result; }
176
177 bool runOnFunction(Function &F) override;
178 void getAnalysisUsage(AnalysisUsage &AU) const override;
179};
180
181FunctionPass *createBasicAAWrapperPass();
182
183} // end namespace llvm
184
185#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.
bool UseDominatorTree
Whether alias analysis is allowed to use the dominator tree, for use by passes that lazily update the...
A base class to help implement the function alias analysis results concept.
The possible results of an alias query.
Definition: AliasAnalysis.h:81
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:387
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
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:1259
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:162
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: Analysis.h:109
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:427
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:1858
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:114
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26