LLVM  6.0.0svn
AliasAnalysisEvaluator.cpp
Go to the documentation of this file.
1 //===- AliasAnalysisEvaluator.cpp - Alias Analysis Accuracy Evaluator -----===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
11 #include "llvm/ADT/SetVector.h"
13 #include "llvm/IR/Constants.h"
14 #include "llvm/IR/DataLayout.h"
15 #include "llvm/IR/DerivedTypes.h"
16 #include "llvm/IR/Function.h"
17 #include "llvm/IR/InstIterator.h"
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/IR/Module.h"
20 #include "llvm/Pass.h"
22 #include "llvm/Support/Debug.h"
24 using namespace llvm;
25 
26 static cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden);
27 
28 static cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden);
29 static cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden);
30 static cl::opt<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden);
31 static cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden);
32 
33 static cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden);
34 static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden);
35 static cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden);
36 static cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden);
37 
38 static cl::opt<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden);
39 
40 static void PrintResults(const char *Msg, bool P, const Value *V1,
41  const Value *V2, const Module *M) {
42  if (PrintAll || P) {
43  std::string o1, o2;
44  {
45  raw_string_ostream os1(o1), os2(o2);
46  V1->printAsOperand(os1, true, M);
47  V2->printAsOperand(os2, true, M);
48  }
49 
50  if (o2 < o1)
51  std::swap(o1, o2);
52  errs() << " " << Msg << ":\t"
53  << o1 << ", "
54  << o2 << "\n";
55  }
56 }
57 
58 static inline void
59 PrintModRefResults(const char *Msg, bool P, Instruction *I, Value *Ptr,
60  Module *M) {
61  if (PrintAll || P) {
62  errs() << " " << Msg << ": Ptr: ";
63  Ptr->printAsOperand(errs(), true, M);
64  errs() << "\t<->" << *I << '\n';
65  }
66 }
67 
68 static inline void
69 PrintModRefResults(const char *Msg, bool P, CallSite CSA, CallSite CSB,
70  Module *M) {
71  if (PrintAll || P) {
72  errs() << " " << Msg << ": " << *CSA.getInstruction()
73  << " <-> " << *CSB.getInstruction() << '\n';
74  }
75 }
76 
77 static inline void
78 PrintLoadStoreResults(const char *Msg, bool P, const Value *V1,
79  const Value *V2, const Module *M) {
80  if (PrintAll || P) {
81  errs() << " " << Msg << ": " << *V1
82  << " <-> " << *V2 << '\n';
83  }
84 }
85 
86 static inline bool isInterestingPointer(Value *V) {
87  return V->getType()->isPointerTy()
88  && !isa<ConstantPointerNull>(V);
89 }
90 
92  runInternal(F, AM.getResult<AAManager>(F));
93  return PreservedAnalyses::all();
94 }
95 
96 void AAEvaluator::runInternal(Function &F, AAResults &AA) {
97  const DataLayout &DL = F.getParent()->getDataLayout();
98 
99  ++FunctionCount;
100 
101  SetVector<Value *> Pointers;
103  SetVector<Value *> Loads;
104  SetVector<Value *> Stores;
105 
106  for (auto &I : F.args())
107  if (I.getType()->isPointerTy()) // Add all pointer arguments.
108  Pointers.insert(&I);
109 
110  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
111  if (I->getType()->isPointerTy()) // Add all pointer instructions.
112  Pointers.insert(&*I);
113  if (EvalAAMD && isa<LoadInst>(&*I))
114  Loads.insert(&*I);
115  if (EvalAAMD && isa<StoreInst>(&*I))
116  Stores.insert(&*I);
117  Instruction &Inst = *I;
118  if (auto CS = CallSite(&Inst)) {
119  Value *Callee = CS.getCalledValue();
120  // Skip actual functions for direct function calls.
121  if (!isa<Function>(Callee) && isInterestingPointer(Callee))
122  Pointers.insert(Callee);
123  // Consider formals.
124  for (Use &DataOp : CS.data_ops())
125  if (isInterestingPointer(DataOp))
126  Pointers.insert(DataOp);
127  CallSites.insert(CS);
128  } else {
129  // Consider all operands.
130  for (Instruction::op_iterator OI = Inst.op_begin(), OE = Inst.op_end();
131  OI != OE; ++OI)
132  if (isInterestingPointer(*OI))
133  Pointers.insert(*OI);
134  }
135  }
136 
139  errs() << "Function: " << F.getName() << ": " << Pointers.size()
140  << " pointers, " << CallSites.size() << " call sites\n";
141 
142  // iterate over the worklist, and run the full (n^2)/2 disambiguations
143  for (SetVector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end();
144  I1 != E; ++I1) {
145  uint64_t I1Size = MemoryLocation::UnknownSize;
146  Type *I1ElTy = cast<PointerType>((*I1)->getType())->getElementType();
147  if (I1ElTy->isSized()) I1Size = DL.getTypeStoreSize(I1ElTy);
148 
149  for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) {
150  uint64_t I2Size = MemoryLocation::UnknownSize;
151  Type *I2ElTy =cast<PointerType>((*I2)->getType())->getElementType();
152  if (I2ElTy->isSized()) I2Size = DL.getTypeStoreSize(I2ElTy);
153 
154  switch (AA.alias(*I1, I1Size, *I2, I2Size)) {
155  case NoAlias:
156  PrintResults("NoAlias", PrintNoAlias, *I1, *I2, F.getParent());
157  ++NoAliasCount;
158  break;
159  case MayAlias:
160  PrintResults("MayAlias", PrintMayAlias, *I1, *I2, F.getParent());
161  ++MayAliasCount;
162  break;
163  case PartialAlias:
164  PrintResults("PartialAlias", PrintPartialAlias, *I1, *I2,
165  F.getParent());
166  ++PartialAliasCount;
167  break;
168  case MustAlias:
169  PrintResults("MustAlias", PrintMustAlias, *I1, *I2, F.getParent());
170  ++MustAliasCount;
171  break;
172  }
173  }
174  }
175 
176  if (EvalAAMD) {
177  // iterate over all pairs of load, store
178  for (Value *Load : Loads) {
179  for (Value *Store : Stores) {
180  switch (AA.alias(MemoryLocation::get(cast<LoadInst>(Load)),
181  MemoryLocation::get(cast<StoreInst>(Store)))) {
182  case NoAlias:
184  F.getParent());
185  ++NoAliasCount;
186  break;
187  case MayAlias:
189  F.getParent());
190  ++MayAliasCount;
191  break;
192  case PartialAlias:
194  F.getParent());
195  ++PartialAliasCount;
196  break;
197  case MustAlias:
199  F.getParent());
200  ++MustAliasCount;
201  break;
202  }
203  }
204  }
205 
206  // iterate over all pairs of store, store
207  for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end();
208  I1 != E; ++I1) {
209  for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) {
210  switch (AA.alias(MemoryLocation::get(cast<StoreInst>(*I1)),
211  MemoryLocation::get(cast<StoreInst>(*I2)))) {
212  case NoAlias:
213  PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2,
214  F.getParent());
215  ++NoAliasCount;
216  break;
217  case MayAlias:
218  PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2,
219  F.getParent());
220  ++MayAliasCount;
221  break;
222  case PartialAlias:
223  PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2,
224  F.getParent());
225  ++PartialAliasCount;
226  break;
227  case MustAlias:
228  PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2,
229  F.getParent());
230  ++MustAliasCount;
231  break;
232  }
233  }
234  }
235  }
236 
237  // Mod/ref alias analysis: compare all pairs of calls and values
238  for (CallSite C : CallSites) {
239  Instruction *I = C.getInstruction();
240 
241  for (auto Pointer : Pointers) {
243  Type *ElTy = cast<PointerType>(Pointer->getType())->getElementType();
244  if (ElTy->isSized()) Size = DL.getTypeStoreSize(ElTy);
245 
246  switch (AA.getModRefInfo(C, Pointer, Size)) {
247  case MRI_NoModRef:
248  PrintModRefResults("NoModRef", PrintNoModRef, I, Pointer,
249  F.getParent());
250  ++NoModRefCount;
251  break;
252  case MRI_Mod:
253  PrintModRefResults("Just Mod", PrintMod, I, Pointer, F.getParent());
254  ++ModCount;
255  break;
256  case MRI_Ref:
257  PrintModRefResults("Just Ref", PrintRef, I, Pointer, F.getParent());
258  ++RefCount;
259  break;
260  case MRI_ModRef:
261  PrintModRefResults("Both ModRef", PrintModRef, I, Pointer,
262  F.getParent());
263  ++ModRefCount;
264  break;
265  }
266  }
267  }
268 
269  // Mod/ref alias analysis: compare all pairs of calls
270  for (auto C = CallSites.begin(), Ce = CallSites.end(); C != Ce; ++C) {
271  for (auto D = CallSites.begin(); D != Ce; ++D) {
272  if (D == C)
273  continue;
274  switch (AA.getModRefInfo(*C, *D)) {
275  case MRI_NoModRef:
276  PrintModRefResults("NoModRef", PrintNoModRef, *C, *D, F.getParent());
277  ++NoModRefCount;
278  break;
279  case MRI_Mod:
280  PrintModRefResults("Just Mod", PrintMod, *C, *D, F.getParent());
281  ++ModCount;
282  break;
283  case MRI_Ref:
284  PrintModRefResults("Just Ref", PrintRef, *C, *D, F.getParent());
285  ++RefCount;
286  break;
287  case MRI_ModRef:
288  PrintModRefResults("Both ModRef", PrintModRef, *C, *D, F.getParent());
289  ++ModRefCount;
290  break;
291  }
292  }
293  }
294 }
295 
296 static void PrintPercent(int64_t Num, int64_t Sum) {
297  errs() << "(" << Num * 100LL / Sum << "." << ((Num * 1000LL / Sum) % 10)
298  << "%)\n";
299 }
300 
302  if (FunctionCount == 0)
303  return;
304 
305  int64_t AliasSum =
306  NoAliasCount + MayAliasCount + PartialAliasCount + MustAliasCount;
307  errs() << "===== Alias Analysis Evaluator Report =====\n";
308  if (AliasSum == 0) {
309  errs() << " Alias Analysis Evaluator Summary: No pointers!\n";
310  } else {
311  errs() << " " << AliasSum << " Total Alias Queries Performed\n";
312  errs() << " " << NoAliasCount << " no alias responses ";
313  PrintPercent(NoAliasCount, AliasSum);
314  errs() << " " << MayAliasCount << " may alias responses ";
315  PrintPercent(MayAliasCount, AliasSum);
316  errs() << " " << PartialAliasCount << " partial alias responses ";
317  PrintPercent(PartialAliasCount, AliasSum);
318  errs() << " " << MustAliasCount << " must alias responses ";
319  PrintPercent(MustAliasCount, AliasSum);
320  errs() << " Alias Analysis Evaluator Pointer Alias Summary: "
321  << NoAliasCount * 100 / AliasSum << "%/"
322  << MayAliasCount * 100 / AliasSum << "%/"
323  << PartialAliasCount * 100 / AliasSum << "%/"
324  << MustAliasCount * 100 / AliasSum << "%\n";
325  }
326 
327  // Display the summary for mod/ref analysis
328  int64_t ModRefSum = NoModRefCount + ModCount + RefCount + ModRefCount;
329  if (ModRefSum == 0) {
330  errs() << " Alias Analysis Mod/Ref Evaluator Summary: no "
331  "mod/ref!\n";
332  } else {
333  errs() << " " << ModRefSum << " Total ModRef Queries Performed\n";
334  errs() << " " << NoModRefCount << " no mod/ref responses ";
335  PrintPercent(NoModRefCount, ModRefSum);
336  errs() << " " << ModCount << " mod responses ";
337  PrintPercent(ModCount, ModRefSum);
338  errs() << " " << RefCount << " ref responses ";
339  PrintPercent(RefCount, ModRefSum);
340  errs() << " " << ModRefCount << " mod & ref responses ";
341  PrintPercent(ModRefCount, ModRefSum);
342  errs() << " Alias Analysis Evaluator Mod/Ref Summary: "
343  << NoModRefCount * 100 / ModRefSum << "%/"
344  << ModCount * 100 / ModRefSum << "%/" << RefCount * 100 / ModRefSum
345  << "%/" << ModRefCount * 100 / ModRefSum << "%\n";
346  }
347 }
348 
349 namespace llvm {
351  std::unique_ptr<AAEvaluator> P;
352 
353 public:
354  static char ID; // Pass identification, replacement for typeid
357  }
358 
359  void getAnalysisUsage(AnalysisUsage &AU) const override {
361  AU.setPreservesAll();
362  }
363 
364  bool doInitialization(Module &M) override {
365  P.reset(new AAEvaluator());
366  return false;
367  }
368 
369  bool runOnFunction(Function &F) override {
370  P->runInternal(F, getAnalysis<AAResultsWrapperPass>().getAAResults());
371  return false;
372  }
373  bool doFinalization(Module &M) override {
374  P.reset();
375  return false;
376  }
377 };
378 }
379 
380 char AAEvalLegacyPass::ID = 0;
382  "Exhaustive Alias Analysis Precision Evaluator", false,
383  true)
386  "Exhaustive Alias Analysis Precision Evaluator", false,
387  true)
388 
The two locations precisely alias each other.
Definition: AliasAnalysis.h:85
static cl::opt< bool > PrintPartialAlias("print-partial-aliases", cl::ReallyHidden)
uint64_t CallInst * C
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:78
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:262
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:83
void initializeAAEvalLegacyPassPass(PassRegistry &)
This file implements a simple N^2 alias analysis accuracy evaluator.
static void PrintModRefResults(const char *Msg, bool P, Instruction *I, Value *Ptr, Module *M)
static cl::opt< bool > PrintMod("print-mod", cl::ReallyHidden)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
static cl::opt< bool > PrintModRef("print-modref", cl::ReallyHidden)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
The two locations do not alias at all.
Definition: AliasAnalysis.h:79
FunctionPass * createAAEvalPass()
Create a wrapper of the above for the legacy pass manager.
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:93
The access modifies the value stored in memory.
op_iterator op_begin()
Definition: User.h:214
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:81
static cl::opt< bool > PrintMustAlias("print-must-aliases", cl::ReallyHidden)
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:132
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
InstrTy * getInstruction() const
Definition: CallSite.h:89
The access references the value stored in memory.
Definition: AliasAnalysis.h:98
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
#define F(x, y, z)
Definition: MD5.cpp:55
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:83
INITIALIZE_PASS_BEGIN(AAEvalLegacyPass, "aa-eval", "Exhaustive Alias Analysis Precision Evaluator", false, true) INITIALIZE_PASS_END(AAEvalLegacyPass
static void PrintResults(const char *Msg, bool P, const Value *V1, const Value *V2, const Module *M)
static void PrintLoadStoreResults(const char *Msg, bool P, const Value *V1, const Value *V2, const Module *M)
static bool isInterestingPointer(Value *V)
static cl::opt< bool > PrintRef("print-ref", cl::ReallyHidden)
The access neither references nor modifies the value stored in memory.
Definition: AliasAnalysis.h:96
#define P(N)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
static cl::opt< bool > PrintMayAlias("print-may-aliases", cl::ReallyHidden)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:221
A manager for alias analyses.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
Represent the analysis usage information of a pass.
op_iterator op_end()
Definition: User.h:216
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:3538
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This class evaluates LLVM IR, producing the Constant representing each SSA instruction.
Definition: Evaluator.h:37
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
#define E
Definition: LargeTest.cpp:27
Module.h This file contains the declarations for the Module class.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
void setPreservesAll()
Set by analyses that do not transform their input at all.
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
static void PrintPercent(int64_t Num, int64_t Sum)
Basic Alias true
block Block Frequency Analysis
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
static cl::opt< bool > EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden)
The access both references and modifies the value stored in memory.
#define I(x, y, z)
Definition: MD5.cpp:58
static cl::opt< bool > PrintNoModRef("print-no-modref", cl::ReallyHidden)
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:463
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:545
LLVM Value Representation.
Definition: Value.h:73
uint64_t getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type...
Definition: DataLayout.h:388
inst_iterator inst_end(Function *F)
Definition: InstIterator.h:133
A container for analyses that lazily runs them and caches their results.
int * Ptr
static cl::opt< bool > PrintAll("print-all-alias-modref-info", cl::ReallyHidden)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
static cl::opt< bool > PrintNoAlias("print-no-aliases", cl::ReallyHidden)
#define D
Definition: LargeTest.cpp:26
iterator_range< arg_iterator > args()
Definition: Function.h:613
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...