]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/Analysis/AliasAnalysisEvaluator.cpp
1 //===- AliasAnalysisEvaluator.cpp - Alias Analysis Accuracy Evaluator -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a simple N^2 alias analysis accuracy evaluator.
11 // Basically, for each function in the program, it simply queries to see how the
12 // alias analysis implementation answers alias queries between each pair of
13 // pointers in the function.
15 // This is inspired and adapted from code by: Naveen Neelakantam, Francesco
16 // Spadini, and Wojciech Stryjewski.
18 //===----------------------------------------------------------------------===//
20 #include "llvm/Analysis/Passes.h"
21 #include "llvm/ADT/SetVector.h"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/IR/Constants.h"
24 #include "llvm/IR/DerivedTypes.h"
25 #include "llvm/IR/Function.h"
26 #include "llvm/IR/InstIterator.h"
27 #include "llvm/IR/Instructions.h"
28 #include "llvm/Pass.h"
29 #include "llvm/Support/CommandLine.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/raw_ostream.h"
34 static cl::opt
<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden
);
36 static cl::opt
<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden
);
37 static cl::opt
<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden
);
38 static cl::opt
<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden
);
39 static cl::opt
<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden
);
41 static cl::opt
<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden
);
42 static cl::opt
<bool> PrintMod("print-mod", cl::ReallyHidden
);
43 static cl::opt
<bool> PrintRef("print-ref", cl::ReallyHidden
);
44 static cl::opt
<bool> PrintModRef("print-modref", cl::ReallyHidden
);
46 static cl::opt
<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden
);
49 class AAEval
: public FunctionPass
{
50 unsigned NoAlias
, MayAlias
, PartialAlias
, MustAlias
;
51 unsigned NoModRef
, Mod
, Ref
, ModRef
;
54 static char ID
; // Pass identification, replacement for typeid
55 AAEval() : FunctionPass(ID
) {
56 initializeAAEvalPass(*PassRegistry::getPassRegistry());
59 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
60 AU
.addRequired
<AliasAnalysis
>();
64 bool doInitialization(Module
&M
) override
{
65 NoAlias
= MayAlias
= PartialAlias
= MustAlias
= 0;
66 NoModRef
= Mod
= Ref
= ModRef
= 0;
69 PrintNoAlias
= PrintMayAlias
= true;
70 PrintPartialAlias
= PrintMustAlias
= true;
71 PrintNoModRef
= PrintMod
= PrintRef
= PrintModRef
= true;
76 bool runOnFunction(Function
&F
) override
;
77 bool doFinalization(Module
&M
) override
;
82 INITIALIZE_PASS_BEGIN(AAEval
, "aa-eval",
83 "Exhaustive Alias Analysis Precision Evaluator", false, true)
84 INITIALIZE_AG_DEPENDENCY(AliasAnalysis
)
85 INITIALIZE_PASS_END(AAEval
, "aa-eval",
86 "Exhaustive Alias Analysis Precision Evaluator", false, true)
88 FunctionPass
*llvm::createAAEvalPass() { return new AAEval(); }
90 static void PrintResults(const char *Msg
, bool P
, const Value
*V1
,
91 const Value
*V2
, const Module
*M
) {
95 raw_string_ostream
os1(o1
), os2(o2
);
96 V1
->printAsOperand(os1
, true, M
);
97 V2
->printAsOperand(os2
, true, M
);
102 errs() << " " << Msg
<< ":\t"
109 PrintModRefResults(const char *Msg
, bool P
, Instruction
*I
, Value
*Ptr
,
112 errs() << " " << Msg
<< ": Ptr: ";
113 Ptr
->printAsOperand(errs(), true, M
);
114 errs() << "\t<->" << *I
<< '\n';
119 PrintModRefResults(const char *Msg
, bool P
, CallSite CSA
, CallSite CSB
,
122 errs() << " " << Msg
<< ": " << *CSA
.getInstruction()
123 << " <-> " << *CSB
.getInstruction() << '\n';
128 PrintLoadStoreResults(const char *Msg
, bool P
, const Value
*V1
,
129 const Value
*V2
, const Module
*M
) {
131 errs() << " " << Msg
<< ": " << *V1
132 << " <-> " << *V2
<< '\n';
136 static inline bool isInterestingPointer(Value
*V
) {
137 return V
->getType()->isPointerTy()
138 && !isa
<ConstantPointerNull
>(V
);
141 bool AAEval::runOnFunction(Function
&F
) {
142 AliasAnalysis
&AA
= getAnalysis
<AliasAnalysis
>();
144 SetVector
<Value
*> Pointers
;
145 SetVector
<CallSite
> CallSites
;
146 SetVector
<Value
*> Loads
;
147 SetVector
<Value
*> Stores
;
149 for (Function::arg_iterator I
= F
.arg_begin(), E
= F
.arg_end(); I
!= E
; ++I
)
150 if (I
->getType()->isPointerTy()) // Add all pointer arguments.
153 for (inst_iterator I
= inst_begin(F
), E
= inst_end(F
); I
!= E
; ++I
) {
154 if (I
->getType()->isPointerTy()) // Add all pointer instructions.
155 Pointers
.insert(&*I
);
156 if (EvalAAMD
&& isa
<LoadInst
>(&*I
))
158 if (EvalAAMD
&& isa
<StoreInst
>(&*I
))
160 Instruction
&Inst
= *I
;
161 if (CallSite CS
= cast
<Value
>(&Inst
)) {
162 Value
*Callee
= CS
.getCalledValue();
163 // Skip actual functions for direct function calls.
164 if (!isa
<Function
>(Callee
) && isInterestingPointer(Callee
))
165 Pointers
.insert(Callee
);
167 for (CallSite::arg_iterator AI
= CS
.arg_begin(), AE
= CS
.arg_end();
169 if (isInterestingPointer(*AI
))
170 Pointers
.insert(*AI
);
171 CallSites
.insert(CS
);
173 // Consider all operands.
174 for (Instruction::op_iterator OI
= Inst
.op_begin(), OE
= Inst
.op_end();
176 if (isInterestingPointer(*OI
))
177 Pointers
.insert(*OI
);
181 if (PrintNoAlias
|| PrintMayAlias
|| PrintPartialAlias
|| PrintMustAlias
||
182 PrintNoModRef
|| PrintMod
|| PrintRef
|| PrintModRef
)
183 errs() << "Function: " << F
.getName() << ": " << Pointers
.size()
184 << " pointers, " << CallSites
.size() << " call sites\n";
186 // iterate over the worklist, and run the full (n^2)/2 disambiguations
187 for (SetVector
<Value
*>::iterator I1
= Pointers
.begin(), E
= Pointers
.end();
189 uint64_t I1Size
= AliasAnalysis::UnknownSize
;
190 Type
*I1ElTy
= cast
<PointerType
>((*I1
)->getType())->getElementType();
191 if (I1ElTy
->isSized()) I1Size
= AA
.getTypeStoreSize(I1ElTy
);
193 for (SetVector
<Value
*>::iterator I2
= Pointers
.begin(); I2
!= I1
; ++I2
) {
194 uint64_t I2Size
= AliasAnalysis::UnknownSize
;
195 Type
*I2ElTy
=cast
<PointerType
>((*I2
)->getType())->getElementType();
196 if (I2ElTy
->isSized()) I2Size
= AA
.getTypeStoreSize(I2ElTy
);
198 switch (AA
.alias(*I1
, I1Size
, *I2
, I2Size
)) {
199 case AliasAnalysis::NoAlias
:
200 PrintResults("NoAlias", PrintNoAlias
, *I1
, *I2
, F
.getParent());
202 case AliasAnalysis::MayAlias
:
203 PrintResults("MayAlias", PrintMayAlias
, *I1
, *I2
, F
.getParent());
205 case AliasAnalysis::PartialAlias
:
206 PrintResults("PartialAlias", PrintPartialAlias
, *I1
, *I2
,
208 ++PartialAlias
; break;
209 case AliasAnalysis::MustAlias
:
210 PrintResults("MustAlias", PrintMustAlias
, *I1
, *I2
, F
.getParent());
217 // iterate over all pairs of load, store
218 for (SetVector
<Value
*>::iterator I1
= Loads
.begin(), E
= Loads
.end();
220 for (SetVector
<Value
*>::iterator I2
= Stores
.begin(), E2
= Stores
.end();
222 switch (AA
.alias(AA
.getLocation(cast
<LoadInst
>(*I1
)),
223 AA
.getLocation(cast
<StoreInst
>(*I2
)))) {
224 case AliasAnalysis::NoAlias
:
225 PrintLoadStoreResults("NoAlias", PrintNoAlias
, *I1
, *I2
,
228 case AliasAnalysis::MayAlias
:
229 PrintLoadStoreResults("MayAlias", PrintMayAlias
, *I1
, *I2
,
232 case AliasAnalysis::PartialAlias
:
233 PrintLoadStoreResults("PartialAlias", PrintPartialAlias
, *I1
, *I2
,
235 ++PartialAlias
; break;
236 case AliasAnalysis::MustAlias
:
237 PrintLoadStoreResults("MustAlias", PrintMustAlias
, *I1
, *I2
,
244 // iterate over all pairs of store, store
245 for (SetVector
<Value
*>::iterator I1
= Stores
.begin(), E
= Stores
.end();
247 for (SetVector
<Value
*>::iterator I2
= Stores
.begin(); I2
!= I1
; ++I2
) {
248 switch (AA
.alias(AA
.getLocation(cast
<StoreInst
>(*I1
)),
249 AA
.getLocation(cast
<StoreInst
>(*I2
)))) {
250 case AliasAnalysis::NoAlias
:
251 PrintLoadStoreResults("NoAlias", PrintNoAlias
, *I1
, *I2
,
254 case AliasAnalysis::MayAlias
:
255 PrintLoadStoreResults("MayAlias", PrintMayAlias
, *I1
, *I2
,
258 case AliasAnalysis::PartialAlias
:
259 PrintLoadStoreResults("PartialAlias", PrintPartialAlias
, *I1
, *I2
,
261 ++PartialAlias
; break;
262 case AliasAnalysis::MustAlias
:
263 PrintLoadStoreResults("MustAlias", PrintMustAlias
, *I1
, *I2
,
271 // Mod/ref alias analysis: compare all pairs of calls and values
272 for (SetVector
<CallSite
>::iterator C
= CallSites
.begin(),
273 Ce
= CallSites
.end(); C
!= Ce
; ++C
) {
274 Instruction
*I
= C
->getInstruction();
276 for (SetVector
<Value
*>::iterator V
= Pointers
.begin(), Ve
= Pointers
.end();
278 uint64_t Size
= AliasAnalysis::UnknownSize
;
279 Type
*ElTy
= cast
<PointerType
>((*V
)->getType())->getElementType();
280 if (ElTy
->isSized()) Size
= AA
.getTypeStoreSize(ElTy
);
282 switch (AA
.getModRefInfo(*C
, *V
, Size
)) {
283 case AliasAnalysis::NoModRef
:
284 PrintModRefResults("NoModRef", PrintNoModRef
, I
, *V
, F
.getParent());
286 case AliasAnalysis::Mod
:
287 PrintModRefResults("Just Mod", PrintMod
, I
, *V
, F
.getParent());
289 case AliasAnalysis::Ref
:
290 PrintModRefResults("Just Ref", PrintRef
, I
, *V
, F
.getParent());
292 case AliasAnalysis::ModRef
:
293 PrintModRefResults("Both ModRef", PrintModRef
, I
, *V
, F
.getParent());
299 // Mod/ref alias analysis: compare all pairs of calls
300 for (SetVector
<CallSite
>::iterator C
= CallSites
.begin(),
301 Ce
= CallSites
.end(); C
!= Ce
; ++C
) {
302 for (SetVector
<CallSite
>::iterator D
= CallSites
.begin(); D
!= Ce
; ++D
) {
305 switch (AA
.getModRefInfo(*C
, *D
)) {
306 case AliasAnalysis::NoModRef
:
307 PrintModRefResults("NoModRef", PrintNoModRef
, *C
, *D
, F
.getParent());
309 case AliasAnalysis::Mod
:
310 PrintModRefResults("Just Mod", PrintMod
, *C
, *D
, F
.getParent());
312 case AliasAnalysis::Ref
:
313 PrintModRefResults("Just Ref", PrintRef
, *C
, *D
, F
.getParent());
315 case AliasAnalysis::ModRef
:
316 PrintModRefResults("Both ModRef", PrintModRef
, *C
, *D
, F
.getParent());
325 static void PrintPercent(unsigned Num
, unsigned Sum
) {
326 errs() << "(" << Num
*100ULL/Sum
<< "."
327 << ((Num
*1000ULL/Sum
) % 10) << "%)\n";
330 bool AAEval::doFinalization(Module
&M
) {
331 unsigned AliasSum
= NoAlias
+ MayAlias
+ PartialAlias
+ MustAlias
;
332 errs() << "===== Alias Analysis Evaluator Report =====\n";
334 errs() << " Alias Analysis Evaluator Summary: No pointers!\n";
336 errs() << " " << AliasSum
<< " Total Alias Queries Performed\n";
337 errs() << " " << NoAlias
<< " no alias responses ";
338 PrintPercent(NoAlias
, AliasSum
);
339 errs() << " " << MayAlias
<< " may alias responses ";
340 PrintPercent(MayAlias
, AliasSum
);
341 errs() << " " << PartialAlias
<< " partial alias responses ";
342 PrintPercent(PartialAlias
, AliasSum
);
343 errs() << " " << MustAlias
<< " must alias responses ";
344 PrintPercent(MustAlias
, AliasSum
);
345 errs() << " Alias Analysis Evaluator Pointer Alias Summary: "
346 << NoAlias
*100/AliasSum
<< "%/" << MayAlias
*100/AliasSum
<< "%/"
347 << PartialAlias
*100/AliasSum
<< "%/"
348 << MustAlias
*100/AliasSum
<< "%\n";
351 // Display the summary for mod/ref analysis
352 unsigned ModRefSum
= NoModRef
+ Mod
+ Ref
+ ModRef
;
353 if (ModRefSum
== 0) {
354 errs() << " Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!\n";
356 errs() << " " << ModRefSum
<< " Total ModRef Queries Performed\n";
357 errs() << " " << NoModRef
<< " no mod/ref responses ";
358 PrintPercent(NoModRef
, ModRefSum
);
359 errs() << " " << Mod
<< " mod responses ";
360 PrintPercent(Mod
, ModRefSum
);
361 errs() << " " << Ref
<< " ref responses ";
362 PrintPercent(Ref
, ModRefSum
);
363 errs() << " " << ModRef
<< " mod & ref responses ";
364 PrintPercent(ModRef
, ModRefSum
);
365 errs() << " Alias Analysis Evaluator Mod/Ref Summary: "
366 << NoModRef
*100/ModRefSum
<< "%/" << Mod
*100/ModRefSum
<< "%/"
367 << Ref
*100/ModRefSum
<< "%/" << ModRef
*100/ModRefSum
<< "%\n";