LLVM 17.0.0git
AliasAnalysisEvaluator.cpp
Go to the documentation of this file.
1//===- AliasAnalysisEvaluator.cpp - Alias Analysis Accuracy Evaluator -----===//
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
10#include "llvm/ADT/SetVector.h"
12#include "llvm/IR/DataLayout.h"
13#include "llvm/IR/Function.h"
16#include "llvm/IR/Module.h"
18#include "llvm/Pass.h"
21using namespace llvm;
22
23static cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden);
24
25static cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden);
26static cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden);
27static cl::opt<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden);
28static cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden);
29
30static cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden);
34
35static cl::opt<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden);
36
37static void PrintResults(AliasResult AR, bool P,
38 std::pair<const Value *, Type *> Loc1,
39 std::pair<const Value *, Type *> Loc2,
40 const Module *M) {
41 if (PrintAll || P) {
42 Type *Ty1 = Loc1.second, *Ty2 = Loc2.second;
43 unsigned AS1 = Loc1.first->getType()->getPointerAddressSpace();
44 unsigned AS2 = Loc2.first->getType()->getPointerAddressSpace();
45 std::string o1, o2;
46 {
47 raw_string_ostream os1(o1), os2(o2);
48 Loc1.first->printAsOperand(os1, false, M);
49 Loc2.first->printAsOperand(os2, false, M);
50 }
51
52 if (o2 < o1) {
53 std::swap(o1, o2);
54 std::swap(Ty1, Ty2);
55 std::swap(AS1, AS2);
56 // Change offset sign for the local AR, for printing only.
57 AR.swap();
58 }
59 errs() << " " << AR << ":\t";
60 Ty1->print(errs(), false, /* NoDetails */ true);
61 if (AS1 != 0)
62 errs() << " addrspace(" << AS1 << ")";
63 errs() << "* " << o1 << ", ";
64 Ty2->print(errs(), false, /* NoDetails */ true);
65 if (AS2 != 0)
66 errs() << " addrspace(" << AS2 << ")";
67 errs() << "* " << o2 << "\n";
68 }
69}
70
71static inline void PrintModRefResults(
72 const char *Msg, bool P, Instruction *I,
73 std::pair<const Value *, Type *> Loc, Module *M) {
74 if (PrintAll || P) {
75 errs() << " " << Msg << ": Ptr: ";
76 Loc.second->print(errs(), false, /* NoDetails */ true);
77 errs() << "* ";
78 Loc.first->printAsOperand(errs(), false, M);
79 errs() << "\t<->" << *I << '\n';
80 }
81}
82
83static inline void PrintModRefResults(const char *Msg, bool P, CallBase *CallA,
84 CallBase *CallB, Module *M) {
85 if (PrintAll || P) {
86 errs() << " " << Msg << ": " << *CallA << " <-> " << *CallB << '\n';
87 }
88}
89
90static inline void PrintLoadStoreResults(AliasResult AR, bool P,
91 const Value *V1, const Value *V2,
92 const Module *M) {
93 if (PrintAll || P) {
94 errs() << " " << AR << ": " << *V1 << " <-> " << *V2 << '\n';
95 }
96}
97
99 runInternal(F, AM.getResult<AAManager>(F));
100 return PreservedAnalyses::all();
101}
102
103void AAEvaluator::runInternal(Function &F, AAResults &AA) {
104 const DataLayout &DL = F.getParent()->getDataLayout();
105
106 ++FunctionCount;
107
110 SetVector<Value *> Loads;
111 SetVector<Value *> Stores;
112
113 for (Instruction &Inst : instructions(F)) {
114 if (auto *LI = dyn_cast<LoadInst>(&Inst)) {
115 Pointers.insert({LI->getPointerOperand(), LI->getType()});
116 Loads.insert(LI);
117 } else if (auto *SI = dyn_cast<StoreInst>(&Inst)) {
118 Pointers.insert({SI->getPointerOperand(),
119 SI->getValueOperand()->getType()});
120 Stores.insert(SI);
121 } else if (auto *CB = dyn_cast<CallBase>(&Inst))
122 Calls.insert(CB);
123 }
124
125 if (PrintAll || PrintNoAlias || PrintMayAlias || PrintPartialAlias ||
127 errs() << "Function: " << F.getName() << ": " << Pointers.size()
128 << " pointers, " << Calls.size() << " call sites\n";
129
130 // iterate over the worklist, and run the full (n^2)/2 disambiguations
131 for (auto I1 = Pointers.begin(), E = Pointers.end(); I1 != E; ++I1) {
132 LocationSize Size1 = LocationSize::precise(DL.getTypeStoreSize(I1->second));
133 for (auto I2 = Pointers.begin(); I2 != I1; ++I2) {
134 LocationSize Size2 =
135 LocationSize::precise(DL.getTypeStoreSize(I2->second));
136 AliasResult AR = AA.alias(I1->first, Size1, I2->first, Size2);
137 switch (AR) {
139 PrintResults(AR, PrintNoAlias, *I1, *I2, F.getParent());
140 ++NoAliasCount;
141 break;
143 PrintResults(AR, PrintMayAlias, *I1, *I2, F.getParent());
144 ++MayAliasCount;
145 break;
147 PrintResults(AR, PrintPartialAlias, *I1, *I2, F.getParent());
148 ++PartialAliasCount;
149 break;
151 PrintResults(AR, PrintMustAlias, *I1, *I2, F.getParent());
152 ++MustAliasCount;
153 break;
154 }
155 }
156 }
157
158 if (EvalAAMD) {
159 // iterate over all pairs of load, store
160 for (Value *Load : Loads) {
161 for (Value *Store : Stores) {
162 AliasResult AR = AA.alias(MemoryLocation::get(cast<LoadInst>(Load)),
163 MemoryLocation::get(cast<StoreInst>(Store)));
164 switch (AR) {
166 PrintLoadStoreResults(AR, PrintNoAlias, Load, Store, F.getParent());
167 ++NoAliasCount;
168 break;
170 PrintLoadStoreResults(AR, PrintMayAlias, Load, Store, F.getParent());
171 ++MayAliasCount;
172 break;
174 PrintLoadStoreResults(AR, PrintPartialAlias, Load, Store, F.getParent());
175 ++PartialAliasCount;
176 break;
178 PrintLoadStoreResults(AR, PrintMustAlias, Load, Store, F.getParent());
179 ++MustAliasCount;
180 break;
181 }
182 }
183 }
184
185 // iterate over all pairs of store, store
186 for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end();
187 I1 != E; ++I1) {
188 for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) {
189 AliasResult AR = AA.alias(MemoryLocation::get(cast<StoreInst>(*I1)),
190 MemoryLocation::get(cast<StoreInst>(*I2)));
191 switch (AR) {
193 PrintLoadStoreResults(AR, PrintNoAlias, *I1, *I2, F.getParent());
194 ++NoAliasCount;
195 break;
197 PrintLoadStoreResults(AR, PrintMayAlias, *I1, *I2, F.getParent());
198 ++MayAliasCount;
199 break;
201 PrintLoadStoreResults(AR, PrintPartialAlias, *I1, *I2, F.getParent());
202 ++PartialAliasCount;
203 break;
205 PrintLoadStoreResults(AR, PrintMustAlias, *I1, *I2, F.getParent());
206 ++MustAliasCount;
207 break;
208 }
209 }
210 }
211 }
212
213 // Mod/ref alias analysis: compare all pairs of calls and values
214 for (CallBase *Call : Calls) {
215 for (const auto &Pointer : Pointers) {
217 LocationSize::precise(DL.getTypeStoreSize(Pointer.second));
218 switch (AA.getModRefInfo(Call, Pointer.first, Size)) {
220 PrintModRefResults("NoModRef", PrintNoModRef, Call, Pointer,
221 F.getParent());
222 ++NoModRefCount;
223 break;
224 case ModRefInfo::Mod:
225 PrintModRefResults("Just Mod", PrintMod, Call, Pointer, F.getParent());
226 ++ModCount;
227 break;
228 case ModRefInfo::Ref:
229 PrintModRefResults("Just Ref", PrintRef, Call, Pointer, F.getParent());
230 ++RefCount;
231 break;
233 PrintModRefResults("Both ModRef", PrintModRef, Call, Pointer,
234 F.getParent());
235 ++ModRefCount;
236 break;
237 }
238 }
239 }
240
241 // Mod/ref alias analysis: compare all pairs of calls
242 for (CallBase *CallA : Calls) {
243 for (CallBase *CallB : Calls) {
244 if (CallA == CallB)
245 continue;
246 switch (AA.getModRefInfo(CallA, CallB)) {
248 PrintModRefResults("NoModRef", PrintNoModRef, CallA, CallB,
249 F.getParent());
250 ++NoModRefCount;
251 break;
252 case ModRefInfo::Mod:
253 PrintModRefResults("Just Mod", PrintMod, CallA, CallB, F.getParent());
254 ++ModCount;
255 break;
256 case ModRefInfo::Ref:
257 PrintModRefResults("Just Ref", PrintRef, CallA, CallB, F.getParent());
258 ++RefCount;
259 break;
261 PrintModRefResults("Both ModRef", PrintModRef, CallA, CallB,
262 F.getParent());
263 ++ModRefCount;
264 break;
265 }
266 }
267 }
268}
269
270static void PrintPercent(int64_t Num, int64_t Sum) {
271 errs() << "(" << Num * 100LL / Sum << "." << ((Num * 1000LL / Sum) % 10)
272 << "%)\n";
273}
274
276 if (FunctionCount == 0)
277 return;
278
279 int64_t AliasSum =
280 NoAliasCount + MayAliasCount + PartialAliasCount + MustAliasCount;
281 errs() << "===== Alias Analysis Evaluator Report =====\n";
282 if (AliasSum == 0) {
283 errs() << " Alias Analysis Evaluator Summary: No pointers!\n";
284 } else {
285 errs() << " " << AliasSum << " Total Alias Queries Performed\n";
286 errs() << " " << NoAliasCount << " no alias responses ";
287 PrintPercent(NoAliasCount, AliasSum);
288 errs() << " " << MayAliasCount << " may alias responses ";
289 PrintPercent(MayAliasCount, AliasSum);
290 errs() << " " << PartialAliasCount << " partial alias responses ";
291 PrintPercent(PartialAliasCount, AliasSum);
292 errs() << " " << MustAliasCount << " must alias responses ";
293 PrintPercent(MustAliasCount, AliasSum);
294 errs() << " Alias Analysis Evaluator Pointer Alias Summary: "
295 << NoAliasCount * 100 / AliasSum << "%/"
296 << MayAliasCount * 100 / AliasSum << "%/"
297 << PartialAliasCount * 100 / AliasSum << "%/"
298 << MustAliasCount * 100 / AliasSum << "%\n";
299 }
300
301 // Display the summary for mod/ref analysis
302 int64_t ModRefSum = NoModRefCount + RefCount + ModCount + ModRefCount;
303 if (ModRefSum == 0) {
304 errs() << " Alias Analysis Mod/Ref Evaluator Summary: no "
305 "mod/ref!\n";
306 } else {
307 errs() << " " << ModRefSum << " Total ModRef Queries Performed\n";
308 errs() << " " << NoModRefCount << " no mod/ref responses ";
309 PrintPercent(NoModRefCount, ModRefSum);
310 errs() << " " << ModCount << " mod responses ";
311 PrintPercent(ModCount, ModRefSum);
312 errs() << " " << RefCount << " ref responses ";
313 PrintPercent(RefCount, ModRefSum);
314 errs() << " " << ModRefCount << " mod & ref responses ";
315 PrintPercent(ModRefCount, ModRefSum);
316 errs() << " Alias Analysis Evaluator Mod/Ref Summary: "
317 << NoModRefCount * 100 / ModRefSum << "%/"
318 << ModCount * 100 / ModRefSum << "%/" << RefCount * 100 / ModRefSum
319 << "%/" << ModRefCount * 100 / ModRefSum << "%\n";
320 }
321}
322
323namespace llvm {
325 std::unique_ptr<AAEvaluator> P;
326
327public:
328 static char ID; // Pass identification, replacement for typeid
331 }
332
333 void getAnalysisUsage(AnalysisUsage &AU) const override {
335 AU.setPreservesAll();
336 }
337
338 bool doInitialization(Module &M) override {
339 P.reset(new AAEvaluator());
340 return false;
341 }
342
343 bool runOnFunction(Function &F) override {
344 P->runInternal(F, getAnalysis<AAResultsWrapperPass>().getAAResults());
345 return false;
346 }
347 bool doFinalization(Module &M) override {
348 P.reset();
349 return false;
350 }
351};
352}
353
354char AAEvalLegacyPass::ID = 0;
356 "Exhaustive Alias Analysis Precision Evaluator", false,
357 true)
360 "Exhaustive Alias Analysis Precision Evaluator", false,
361 true)
362
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static void PrintModRefResults(const char *Msg, bool P, Instruction *I, std::pair< const Value *, Type * > Loc, Module *M)
static cl::opt< bool > PrintModRef("print-modref", cl::ReallyHidden)
static void PrintLoadStoreResults(AliasResult AR, bool P, const Value *V1, const Value *V2, const Module *M)
static void PrintPercent(int64_t Num, int64_t Sum)
static cl::opt< bool > EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden)
static cl::opt< bool > PrintRef("print-ref", cl::ReallyHidden)
static cl::opt< bool > PrintNoAlias("print-no-aliases", cl::ReallyHidden)
static cl::opt< bool > PrintMayAlias("print-may-aliases", cl::ReallyHidden)
static cl::opt< bool > PrintMod("print-mod", cl::ReallyHidden)
static cl::opt< bool > PrintMustAlias("print-must-aliases", cl::ReallyHidden)
static cl::opt< bool > PrintAll("print-all-alias-modref-info", cl::ReallyHidden)
static cl::opt< bool > PrintNoModRef("print-no-modref", cl::ReallyHidden)
static cl::opt< bool > PrintPartialAlias("print-partial-aliases", cl::ReallyHidden)
This file implements a simple N^2 alias analysis accuracy evaluator.
static cl::opt< bool > PrintResults("print-debug-ata", cl::init(false), cl::Hidden)
Print the results of the analysis. Respects -filter-print-funcs.
basic Basic Alias true
block Block Frequency Analysis
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
uint64_t Size
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
print must be executed print the must be executed context for all instructions
#define P(N)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
@ SI
This file implements a set that has insertion order iteration characteristics.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
The possible results of an alias query.
Definition: AliasAnalysis.h:83
void swap(bool DoSwap=true)
Helper for processing AliasResult for swapped memory location pairs.
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
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
This class evaluates LLVM IR, producing the Constant representing each SSA instruction.
Definition: Evaluator.h:37
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
static LocationSize precise(uint64_t Value)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
A vector that has set insertion semantics.
Definition: SetVector.h:51
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:88
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:152
typename vector_type::const_iterator iterator
Definition: SetVector.h:59
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:93
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:103
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:312
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
void print(raw_ostream &O, bool IsForDebug=false, bool NoDetails=false) const
Print the current type.
LLVM Value Representation.
Definition: Value.h:74
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:642
@ ReallyHidden
Definition: CommandLine.h:139
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void initializeAAEvalLegacyPassPass(PassRegistry &)
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
@ Ref
The access may reference the value stored in memory.
@ ModRef
The access may reference and may modify the value stored in memory.
@ Mod
The access may modify the value stored in memory.
@ NoModRef
The access neither references nor modifies the value stored in memory.
FunctionPass * createAAEvalPass()
Create a wrapper of the above for the legacy pass manager.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860