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 // 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. 14 // 15 // This is inspired and adapted from code by: Naveen Neelakantam, Francesco 16 // Spadini, and Wojciech Stryjewski. 17 // 18 //===----------------------------------------------------------------------===// 19 20 #include "llvm/Constants.h" 21 #include "llvm/DerivedTypes.h" 22 #include "llvm/Function.h" 23 #include "llvm/Instructions.h" 24 #include "llvm/Pass.h" 25 #include "llvm/Analysis/Passes.h" 26 #include "llvm/Analysis/AliasAnalysis.h" 27 #include "llvm/Assembly/Writer.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/InstIterator.h" 30 #include "llvm/Support/CommandLine.h" 31 #include "llvm/Support/raw_ostream.h" 32 #include "llvm/ADT/SetVector.h" 33 using namespace llvm; 34 35 static cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden); 36 37 static cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden); 38 static cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden); 39 static cl::opt<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden); 40 static cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden); 41 42 static cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden); 43 static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden); 44 static cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden); 45 static cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden); 46 47 namespace { 48 class AAEval : public FunctionPass { 49 unsigned NoAlias, MayAlias, PartialAlias, MustAlias; 50 unsigned NoModRef, Mod, Ref, ModRef; 51 52 public: 53 static char ID; // Pass identification, replacement for typeid 54 AAEval() : FunctionPass(ID) { 55 initializeAAEvalPass(*PassRegistry::getPassRegistry()); 56 } 57 58 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 59 AU.addRequired<AliasAnalysis>(); 60 AU.setPreservesAll(); 61 } 62 63 bool doInitialization(Module &M) { 64 NoAlias = MayAlias = PartialAlias = MustAlias = 0; 65 NoModRef = Mod = Ref = ModRef = 0; 66 67 if (PrintAll) { 68 PrintNoAlias = PrintMayAlias = true; 69 PrintPartialAlias = PrintMustAlias = true; 70 PrintNoModRef = PrintMod = PrintRef = PrintModRef = true; 71 } 72 return false; 73 } 74 75 bool runOnFunction(Function &F); 76 bool doFinalization(Module &M); 77 }; 78 } 79 80 char AAEval::ID = 0; 81 INITIALIZE_PASS_BEGIN(AAEval, "aa-eval", 82 "Exhaustive Alias Analysis Precision Evaluator", false, true) 83 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 84 INITIALIZE_PASS_END(AAEval, "aa-eval", 85 "Exhaustive Alias Analysis Precision Evaluator", false, true) 86 87 FunctionPass *llvm::createAAEvalPass() { return new AAEval(); } 88 89 static void PrintResults(const char *Msg, bool P, const Value *V1, 90 const Value *V2, const Module *M) { 91 if (P) { 92 std::string o1, o2; 93 { 94 raw_string_ostream os1(o1), os2(o2); 95 WriteAsOperand(os1, V1, true, M); 96 WriteAsOperand(os2, V2, true, M); 97 } 98 99 if (o2 < o1) 100 std::swap(o1, o2); 101 errs() << " " << Msg << ":\t" 102 << o1 << ", " 103 << o2 << "\n"; 104 } 105 } 106 107 static inline void 108 PrintModRefResults(const char *Msg, bool P, Instruction *I, Value *Ptr, 109 Module *M) { 110 if (P) { 111 errs() << " " << Msg << ": Ptr: "; 112 WriteAsOperand(errs(), Ptr, true, M); 113 errs() << "\t<->" << *I << '\n'; 114 } 115 } 116 117 static inline void 118 PrintModRefResults(const char *Msg, bool P, CallSite CSA, CallSite CSB, 119 Module *M) { 120 if (P) { 121 errs() << " " << Msg << ": " << *CSA.getInstruction() 122 << " <-> " << *CSB.getInstruction() << '\n'; 123 } 124 } 125 126 static inline bool isInterestingPointer(Value *V) { 127 return V->getType()->isPointerTy() 128 && !isa<ConstantPointerNull>(V); 129 } 130 131 bool AAEval::runOnFunction(Function &F) { 132 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 133 134 SetVector<Value *> Pointers; 135 SetVector<CallSite> CallSites; 136 137 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 138 if (I->getType()->isPointerTy()) // Add all pointer arguments. 139 Pointers.insert(I); 140 141 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 142 if (I->getType()->isPointerTy()) // Add all pointer instructions. 143 Pointers.insert(&*I); 144 Instruction &Inst = *I; 145 if (CallSite CS = cast<Value>(&Inst)) { 146 Value *Callee = CS.getCalledValue(); 147 // Skip actual functions for direct function calls. 148 if (!isa<Function>(Callee) && isInterestingPointer(Callee)) 149 Pointers.insert(Callee); 150 // Consider formals. 151 for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 152 AI != AE; ++AI) 153 if (isInterestingPointer(*AI)) 154 Pointers.insert(*AI); 155 CallSites.insert(CS); 156 } else { 157 // Consider all operands. 158 for (Instruction::op_iterator OI = Inst.op_begin(), OE = Inst.op_end(); 159 OI != OE; ++OI) 160 if (isInterestingPointer(*OI)) 161 Pointers.insert(*OI); 162 } 163 } 164 165 if (PrintNoAlias || PrintMayAlias || PrintPartialAlias || PrintMustAlias || 166 PrintNoModRef || PrintMod || PrintRef || PrintModRef) 167 errs() << "Function: " << F.getName() << ": " << Pointers.size() 168 << " pointers, " << CallSites.size() << " call sites\n"; 169 170 // iterate over the worklist, and run the full (n^2)/2 disambiguations 171 for (SetVector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end(); 172 I1 != E; ++I1) { 173 uint64_t I1Size = AliasAnalysis::UnknownSize; 174 Type *I1ElTy = cast<PointerType>((*I1)->getType())->getElementType(); 175 if (I1ElTy->isSized()) I1Size = AA.getTypeStoreSize(I1ElTy); 176 177 for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) { 178 uint64_t I2Size = AliasAnalysis::UnknownSize; 179 Type *I2ElTy =cast<PointerType>((*I2)->getType())->getElementType(); 180 if (I2ElTy->isSized()) I2Size = AA.getTypeStoreSize(I2ElTy); 181 182 switch (AA.alias(*I1, I1Size, *I2, I2Size)) { 183 case AliasAnalysis::NoAlias: 184 PrintResults("NoAlias", PrintNoAlias, *I1, *I2, F.getParent()); 185 ++NoAlias; break; 186 case AliasAnalysis::MayAlias: 187 PrintResults("MayAlias", PrintMayAlias, *I1, *I2, F.getParent()); 188 ++MayAlias; break; 189 case AliasAnalysis::PartialAlias: 190 PrintResults("PartialAlias", PrintPartialAlias, *I1, *I2, 191 F.getParent()); 192 ++PartialAlias; break; 193 case AliasAnalysis::MustAlias: 194 PrintResults("MustAlias", PrintMustAlias, *I1, *I2, F.getParent()); 195 ++MustAlias; break; 196 default: 197 errs() << "Unknown alias query result!\n"; 198 } 199 } 200 } 201 202 // Mod/ref alias analysis: compare all pairs of calls and values 203 for (SetVector<CallSite>::iterator C = CallSites.begin(), 204 Ce = CallSites.end(); C != Ce; ++C) { 205 Instruction *I = C->getInstruction(); 206 207 for (SetVector<Value *>::iterator V = Pointers.begin(), Ve = Pointers.end(); 208 V != Ve; ++V) { 209 uint64_t Size = AliasAnalysis::UnknownSize; 210 Type *ElTy = cast<PointerType>((*V)->getType())->getElementType(); 211 if (ElTy->isSized()) Size = AA.getTypeStoreSize(ElTy); 212 213 switch (AA.getModRefInfo(*C, *V, Size)) { 214 case AliasAnalysis::NoModRef: 215 PrintModRefResults("NoModRef", PrintNoModRef, I, *V, F.getParent()); 216 ++NoModRef; break; 217 case AliasAnalysis::Mod: 218 PrintModRefResults("Just Mod", PrintMod, I, *V, F.getParent()); 219 ++Mod; break; 220 case AliasAnalysis::Ref: 221 PrintModRefResults("Just Ref", PrintRef, I, *V, F.getParent()); 222 ++Ref; break; 223 case AliasAnalysis::ModRef: 224 PrintModRefResults("Both ModRef", PrintModRef, I, *V, F.getParent()); 225 ++ModRef; break; 226 default: 227 errs() << "Unknown alias query result!\n"; 228 } 229 } 230 } 231 232 // Mod/ref alias analysis: compare all pairs of calls 233 for (SetVector<CallSite>::iterator C = CallSites.begin(), 234 Ce = CallSites.end(); C != Ce; ++C) { 235 for (SetVector<CallSite>::iterator D = CallSites.begin(); D != Ce; ++D) { 236 if (D == C) 237 continue; 238 switch (AA.getModRefInfo(*C, *D)) { 239 case AliasAnalysis::NoModRef: 240 PrintModRefResults("NoModRef", PrintNoModRef, *C, *D, F.getParent()); 241 ++NoModRef; break; 242 case AliasAnalysis::Mod: 243 PrintModRefResults("Just Mod", PrintMod, *C, *D, F.getParent()); 244 ++Mod; break; 245 case AliasAnalysis::Ref: 246 PrintModRefResults("Just Ref", PrintRef, *C, *D, F.getParent()); 247 ++Ref; break; 248 case AliasAnalysis::ModRef: 249 PrintModRefResults("Both ModRef", PrintModRef, *C, *D, F.getParent()); 250 ++ModRef; break; 251 } 252 } 253 } 254 255 return false; 256 } 257 258 static void PrintPercent(unsigned Num, unsigned Sum) { 259 errs() << "(" << Num*100ULL/Sum << "." 260 << ((Num*1000ULL/Sum) % 10) << "%)\n"; 261 } 262 263 bool AAEval::doFinalization(Module &M) { 264 unsigned AliasSum = NoAlias + MayAlias + PartialAlias + MustAlias; 265 errs() << "===== Alias Analysis Evaluator Report =====\n"; 266 if (AliasSum == 0) { 267 errs() << " Alias Analysis Evaluator Summary: No pointers!\n"; 268 } else { 269 errs() << " " << AliasSum << " Total Alias Queries Performed\n"; 270 errs() << " " << NoAlias << " no alias responses "; 271 PrintPercent(NoAlias, AliasSum); 272 errs() << " " << MayAlias << " may alias responses "; 273 PrintPercent(MayAlias, AliasSum); 274 errs() << " " << PartialAlias << " partial alias responses "; 275 PrintPercent(PartialAlias, AliasSum); 276 errs() << " " << MustAlias << " must alias responses "; 277 PrintPercent(MustAlias, AliasSum); 278 errs() << " Alias Analysis Evaluator Pointer Alias Summary: " 279 << NoAlias*100/AliasSum << "%/" << MayAlias*100/AliasSum << "%/" 280 << PartialAlias*100/AliasSum << "%/" 281 << MustAlias*100/AliasSum << "%\n"; 282 } 283 284 // Display the summary for mod/ref analysis 285 unsigned ModRefSum = NoModRef + Mod + Ref + ModRef; 286 if (ModRefSum == 0) { 287 errs() << " Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!\n"; 288 } else { 289 errs() << " " << ModRefSum << " Total ModRef Queries Performed\n"; 290 errs() << " " << NoModRef << " no mod/ref responses "; 291 PrintPercent(NoModRef, ModRefSum); 292 errs() << " " << Mod << " mod responses "; 293 PrintPercent(Mod, ModRefSum); 294 errs() << " " << Ref << " ref responses "; 295 PrintPercent(Ref, ModRefSum); 296 errs() << " " << ModRef << " mod & ref responses "; 297 PrintPercent(ModRef, ModRefSum); 298 errs() << " Alias Analysis Evaluator Mod/Ref Summary: " 299 << NoModRef*100/ModRefSum << "%/" << Mod*100/ModRefSum << "%/" 300 << Ref*100/ModRefSum << "%/" << ModRef*100/ModRefSum << "%\n"; 301 } 302 303 return false; 304 } 305
