LLVM 19.0.0git
Go to the documentation of this file.
1//===- BasicAliasAnalysis.h - Stateless, local Alias Analysis ---*- C++ -*-===//
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
8/// \file
9/// This is the interface for LLVM's primary stateless and local alias analysis.
18#include "llvm/IR/PassManager.h"
19#include "llvm/Pass.h"
20#include <memory>
21#include <utility>
23namespace llvm {
25class AssumptionCache;
26class DataLayout;
27class DominatorTree;
28class Function;
29class GEPOperator;
30class PHINode;
31class SelectInst;
32class TargetLibraryInfo;
33class Value;
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_;
50 DominatorTree *getDT(const AAQueryInfo &AAQI) const {
51 return AAQI.UseDominatorTree ? DT_ : nullptr;
52 }
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) {}
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_) {}
67 /// Handle invalidation events in the new pass manager.
68 bool invalidate(Function &Fn, const PreservedAnalyses &PA,
71 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
72 AAQueryInfo &AAQI, const Instruction *CtxI);
74 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
75 AAQueryInfo &AAQI);
77 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
78 AAQueryInfo &AAQI);
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);
90 /// Get the location associated with a pointer argument of a callsite.
91 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
93 /// Returns the behavior when calling the given call site.
96 /// Returns the behavior when calling the given function. For use when the
97 /// call site is not known.
101 struct DecomposedGEP;
103 /// Tracks instructions visited by pointsToConstantMemory.
106 static DecomposedGEP
107 DecomposeGEPExpression(const Value *V, const DataLayout &DL,
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);
122 bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2,
123 const AAQueryInfo &AAQI);
125 void subtractDecomposedGEPs(DecomposedGEP &DestGEP,
126 const DecomposedGEP &SrcGEP,
127 const AAQueryInfo &AAQI);
129 AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
130 const Value *V2, LocationSize V2Size,
131 const Value *UnderlyingV1, const Value *UnderlyingV2,
132 AAQueryInfo &AAQI);
134 AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
135 const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
137 AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
138 const Value *V2, LocationSize V2Size,
139 AAQueryInfo &AAQI);
141 AliasResult aliasCheck(const Value *V1, LocationSize V1Size, const Value *V2,
142 LocationSize V2Size, AAQueryInfo &AAQI,
143 const Instruction *CtxI);
145 AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
146 const Value *V2, LocationSize V2Size,
147 AAQueryInfo &AAQI, const Value *O1,
148 const Value *O2);
151/// Analysis pass providing a never-invalidated alias analysis result.
152class BasicAA : public AnalysisInfoMixin<BasicAA> {
155 static AnalysisKey Key;
163/// Legacy wrapper pass to provide the BasicAAResult object.
165 std::unique_ptr<BasicAAResult> Result;
167 virtual void anchor();
170 static char ID;
174 BasicAAResult &getResult() { return *Result; }
175 const BasicAAResult &getResult() const { return *Result; }
177 bool runOnFunction(Function &F) override;
178 void getAnalysisUsage(AnalysisUsage &AU) const override;
181FunctionPass *createBasicAAWrapperPass();
183} // end namespace llvm
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:82
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:292
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
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:1236
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:111
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:479
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()
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:1849
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:92
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:28