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 9 #include "llvm/Analysis/AliasAnalysisEvaluator.h" 10 #include "llvm/ADT/SetVector.h" 11 #include "llvm/Analysis/AliasAnalysis.h" 12 #include "llvm/IR/Constants.h" 13 #include "llvm/IR/DataLayout.h" 14 #include "llvm/IR/DerivedTypes.h" 15 #include "llvm/IR/Function.h" 16 #include "llvm/IR/InstIterator.h" 17 #include "llvm/IR/Instructions.h" 18 #include "llvm/IR/Module.h" 19 #include "llvm/InitializePasses.h" 20 #include "llvm/Pass.h" 21 #include "llvm/Support/CommandLine.h" 22 #include "llvm/Support/Debug.h" 23 #include "llvm/Support/raw_ostream.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> PrintRef("print-ref", cl::ReallyHidden); 35 static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden); 36 static cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden); 37 static cl::opt<bool> PrintMust("print-must", cl::ReallyHidden); 38 static cl::opt<bool> PrintMustRef("print-mustref", cl::ReallyHidden); 39 static cl::opt<bool> PrintMustMod("print-mustmod", cl::ReallyHidden); 40 static cl::opt<bool> PrintMustModRef("print-mustmodref", cl::ReallyHidden); 41 42 static cl::opt<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden); 43 44 static void PrintResults(AliasResult AR, bool P, const Value *V1, 45 const Value *V2, const Module *M) { 46 if (PrintAll || P) { 47 std::string o1, o2; 48 { 49 raw_string_ostream os1(o1), os2(o2); 50 V1->printAsOperand(os1, true, M); 51 V2->printAsOperand(os2, true, M); 52 } 53 54 if (o2 < o1) 55 std::swap(o1, o2); 56 errs() << " " << AR << ":\t" << o1 << ", " << o2 << "\n"; 57 } 58 } 59 60 static inline void PrintModRefResults(const char *Msg, bool P, Instruction *I, 61 Value *Ptr, Module *M) { 62 if (PrintAll || P) { 63 errs() << " " << Msg << ": Ptr: "; 64 Ptr->printAsOperand(errs(), true, M); 65 errs() << "\t<->" << *I << '\n'; 66 } 67 } 68 69 static inline void PrintModRefResults(const char *Msg, bool P, CallBase *CallA, 70 CallBase *CallB, Module *M) { 71 if (PrintAll || P) { 72 errs() << " " << Msg << ": " << *CallA << " <-> " << *CallB << '\n'; 73 } 74 } 75 76 static inline void PrintLoadStoreResults(AliasResult AR, bool P, 77 const Value *V1, const Value *V2, 78 const Module *M) { 79 if (PrintAll || P) { 80 errs() << " " << AR << ": " << *V1 << " <-> " << *V2 << '\n'; 81 } 82 } 83 84 static inline bool isInterestingPointer(Value *V) { 85 return V->getType()->isPointerTy() 86 && !isa<ConstantPointerNull>(V); 87 } 88 89 PreservedAnalyses AAEvaluator::run(Function &F, FunctionAnalysisManager &AM) { 90 runInternal(F, AM.getResult<AAManager>(F)); 91 return PreservedAnalyses::all(); 92 } 93 94 void AAEvaluator::runInternal(Function &F, AAResults &AA) { 95 const DataLayout &DL = F.getParent()->getDataLayout(); 96 97 ++FunctionCount; 98 99 SetVector<Value *> Pointers; 100 SmallSetVector<CallBase *, 16> Calls; 101 SetVector<Value *> Loads; 102 SetVector<Value *> Stores; 103 104 for (auto &I : F.args()) 105 if (I.getType()->isPointerTy()) // Add all pointer arguments. 106 Pointers.insert(&I); 107 108 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 109 if (I->getType()->isPointerTy()) // Add all pointer instructions. 110 Pointers.insert(&*I); 111 if (EvalAAMD && isa<LoadInst>(&*I)) 112 Loads.insert(&*I); 113 if (EvalAAMD && isa<StoreInst>(&*I)) 114 Stores.insert(&*I); 115 Instruction &Inst = *I; 116 if (auto *Call = dyn_cast<CallBase>(&Inst)) { 117 Value *Callee = Call->getCalledOperand(); 118 // Skip actual functions for direct function calls. 119 if (!isa<Function>(Callee) && isInterestingPointer(Callee)) 120 Pointers.insert(Callee); 121 // Consider formals. 122 for (Use &DataOp : Call->data_ops()) 123 if (isInterestingPointer(DataOp)) 124 Pointers.insert(DataOp); 125 Calls.insert(Call); 126 } else { 127 // Consider all operands. 128 for (Instruction::op_iterator OI = Inst.op_begin(), OE = Inst.op_end(); 129 OI != OE; ++OI) 130 if (isInterestingPointer(*OI)) 131 Pointers.insert(*OI); 132 } 133 } 134 135 if (PrintAll || PrintNoAlias || PrintMayAlias || PrintPartialAlias || 136 PrintMustAlias || PrintNoModRef || PrintMod || PrintRef || PrintModRef) 137 errs() << "Function: " << F.getName() << ": " << Pointers.size() 138 << " pointers, " << Calls.size() << " call sites\n"; 139 140 // iterate over the worklist, and run the full (n^2)/2 disambiguations 141 for (SetVector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end(); 142 I1 != E; ++I1) { 143 auto I1Size = LocationSize::afterPointer(); 144 Type *I1ElTy = cast<PointerType>((*I1)->getType())->getElementType(); 145 if (I1ElTy->isSized()) 146 I1Size = LocationSize::precise(DL.getTypeStoreSize(I1ElTy)); 147 148 for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) { 149 auto I2Size = LocationSize::afterPointer(); 150 Type *I2ElTy = cast<PointerType>((*I2)->getType())->getElementType(); 151 if (I2ElTy->isSized()) 152 I2Size = LocationSize::precise(DL.getTypeStoreSize(I2ElTy)); 153 154 AliasResult AR = AA.alias(*I1, I1Size, *I2, I2Size); 155 switch (AR) { 156 case NoAlias: 157 PrintResults(AR, PrintNoAlias, *I1, *I2, F.getParent()); 158 ++NoAliasCount; 159 break; 160 case MayAlias: 161 PrintResults(AR, PrintMayAlias, *I1, *I2, F.getParent()); 162 ++MayAliasCount; 163 break; 164 case PartialAlias: 165 PrintResults(AR, PrintPartialAlias, *I1, *I2, F.getParent()); 166 ++PartialAliasCount; 167 break; 168 case MustAlias: 169 PrintResults(AR, 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 AliasResult AR = AA.alias(MemoryLocation::get(cast<LoadInst>(Load)), 181 MemoryLocation::get(cast<StoreInst>(Store))); 182 switch (AR) { 183 case NoAlias: 184 PrintLoadStoreResults(AR, PrintNoAlias, Load, Store, F.getParent()); 185 ++NoAliasCount; 186 break; 187 case MayAlias: 188 PrintLoadStoreResults(AR, PrintMayAlias, Load, Store, F.getParent()); 189 ++MayAliasCount; 190 break; 191 case PartialAlias: 192 PrintLoadStoreResults(AR, PrintPartialAlias, Load, Store, F.getParent()); 193 ++PartialAliasCount; 194 break; 195 case MustAlias: 196 PrintLoadStoreResults(AR, PrintMustAlias, Load, Store, F.getParent()); 197 ++MustAliasCount; 198 break; 199 } 200 } 201 } 202 203 // iterate over all pairs of store, store 204 for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end(); 205 I1 != E; ++I1) { 206 for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) { 207 AliasResult AR = AA.alias(MemoryLocation::get(cast<StoreInst>(*I1)), 208 MemoryLocation::get(cast<StoreInst>(*I2))); 209 switch (AR) { 210 case NoAlias: 211 PrintLoadStoreResults(AR, PrintNoAlias, *I1, *I2, F.getParent()); 212 ++NoAliasCount; 213 break; 214 case MayAlias: 215 PrintLoadStoreResults(AR, PrintMayAlias, *I1, *I2, F.getParent()); 216 ++MayAliasCount; 217 break; 218 case PartialAlias: 219 PrintLoadStoreResults(AR, PrintPartialAlias, *I1, *I2, F.getParent()); 220 ++PartialAliasCount; 221 break; 222 case MustAlias: 223 PrintLoadStoreResults(AR, PrintMustAlias, *I1, *I2, F.getParent()); 224 ++MustAliasCount; 225 break; 226 } 227 } 228 } 229 } 230 231 // Mod/ref alias analysis: compare all pairs of calls and values 232 for (CallBase *Call : Calls) { 233 for (auto Pointer : Pointers) { 234 auto Size = LocationSize::afterPointer(); 235 Type *ElTy = cast<PointerType>(Pointer->getType())->getElementType(); 236 if (ElTy->isSized()) 237 Size = LocationSize::precise(DL.getTypeStoreSize(ElTy)); 238 239 switch (AA.getModRefInfo(Call, Pointer, Size)) { 240 case ModRefInfo::NoModRef: 241 PrintModRefResults("NoModRef", PrintNoModRef, Call, Pointer, 242 F.getParent()); 243 ++NoModRefCount; 244 break; 245 case ModRefInfo::Mod: 246 PrintModRefResults("Just Mod", PrintMod, Call, Pointer, F.getParent()); 247 ++ModCount; 248 break; 249 case ModRefInfo::Ref: 250 PrintModRefResults("Just Ref", PrintRef, Call, Pointer, F.getParent()); 251 ++RefCount; 252 break; 253 case ModRefInfo::ModRef: 254 PrintModRefResults("Both ModRef", PrintModRef, Call, Pointer, 255 F.getParent()); 256 ++ModRefCount; 257 break; 258 case ModRefInfo::Must: 259 PrintModRefResults("Must", PrintMust, Call, Pointer, F.getParent()); 260 ++MustCount; 261 break; 262 case ModRefInfo::MustMod: 263 PrintModRefResults("Just Mod (MustAlias)", PrintMustMod, Call, Pointer, 264 F.getParent()); 265 ++MustModCount; 266 break; 267 case ModRefInfo::MustRef: 268 PrintModRefResults("Just Ref (MustAlias)", PrintMustRef, Call, Pointer, 269 F.getParent()); 270 ++MustRefCount; 271 break; 272 case ModRefInfo::MustModRef: 273 PrintModRefResults("Both ModRef (MustAlias)", PrintMustModRef, Call, 274 Pointer, F.getParent()); 275 ++MustModRefCount; 276 break; 277 } 278 } 279 } 280 281 // Mod/ref alias analysis: compare all pairs of calls 282 for (CallBase *CallA : Calls) { 283 for (CallBase *CallB : Calls) { 284 if (CallA == CallB) 285 continue; 286 switch (AA.getModRefInfo(CallA, CallB)) { 287 case ModRefInfo::NoModRef: 288 PrintModRefResults("NoModRef", PrintNoModRef, CallA, CallB, 289 F.getParent()); 290 ++NoModRefCount; 291 break; 292 case ModRefInfo::Mod: 293 PrintModRefResults("Just Mod", PrintMod, CallA, CallB, F.getParent()); 294 ++ModCount; 295 break; 296 case ModRefInfo::Ref: 297 PrintModRefResults("Just Ref", PrintRef, CallA, CallB, F.getParent()); 298 ++RefCount; 299 break; 300 case ModRefInfo::ModRef: 301 PrintModRefResults("Both ModRef", PrintModRef, CallA, CallB, 302 F.getParent()); 303 ++ModRefCount; 304 break; 305 case ModRefInfo::Must: 306 PrintModRefResults("Must", PrintMust, CallA, CallB, F.getParent()); 307 ++MustCount; 308 break; 309 case ModRefInfo::MustMod: 310 PrintModRefResults("Just Mod (MustAlias)", PrintMustMod, CallA, CallB, 311 F.getParent()); 312 ++MustModCount; 313 break; 314 case ModRefInfo::MustRef: 315 PrintModRefResults("Just Ref (MustAlias)", PrintMustRef, CallA, CallB, 316 F.getParent()); 317 ++MustRefCount; 318 break; 319 case ModRefInfo::MustModRef: 320 PrintModRefResults("Both ModRef (MustAlias)", PrintMustModRef, CallA, 321 CallB, F.getParent()); 322 ++MustModRefCount; 323 break; 324 } 325 } 326 } 327 } 328 329 static void PrintPercent(int64_t Num, int64_t Sum) { 330 errs() << "(" << Num * 100LL / Sum << "." << ((Num * 1000LL / Sum) % 10) 331 << "%)\n"; 332 } 333 334 AAEvaluator::~AAEvaluator() { 335 if (FunctionCount == 0) 336 return; 337 338 int64_t AliasSum = 339 NoAliasCount + MayAliasCount + PartialAliasCount + MustAliasCount; 340 errs() << "===== Alias Analysis Evaluator Report =====\n"; 341 if (AliasSum == 0) { 342 errs() << " Alias Analysis Evaluator Summary: No pointers!\n"; 343 } else { 344 errs() << " " << AliasSum << " Total Alias Queries Performed\n"; 345 errs() << " " << NoAliasCount << " no alias responses "; 346 PrintPercent(NoAliasCount, AliasSum); 347 errs() << " " << MayAliasCount << " may alias responses "; 348 PrintPercent(MayAliasCount, AliasSum); 349 errs() << " " << PartialAliasCount << " partial alias responses "; 350 PrintPercent(PartialAliasCount, AliasSum); 351 errs() << " " << MustAliasCount << " must alias responses "; 352 PrintPercent(MustAliasCount, AliasSum); 353 errs() << " Alias Analysis Evaluator Pointer Alias Summary: " 354 << NoAliasCount * 100 / AliasSum << "%/" 355 << MayAliasCount * 100 / AliasSum << "%/" 356 << PartialAliasCount * 100 / AliasSum << "%/" 357 << MustAliasCount * 100 / AliasSum << "%\n"; 358 } 359 360 // Display the summary for mod/ref analysis 361 int64_t ModRefSum = NoModRefCount + RefCount + ModCount + ModRefCount + 362 MustCount + MustRefCount + MustModCount + MustModRefCount; 363 if (ModRefSum == 0) { 364 errs() << " Alias Analysis Mod/Ref Evaluator Summary: no " 365 "mod/ref!\n"; 366 } else { 367 errs() << " " << ModRefSum << " Total ModRef Queries Performed\n"; 368 errs() << " " << NoModRefCount << " no mod/ref responses "; 369 PrintPercent(NoModRefCount, ModRefSum); 370 errs() << " " << ModCount << " mod responses "; 371 PrintPercent(ModCount, ModRefSum); 372 errs() << " " << RefCount << " ref responses "; 373 PrintPercent(RefCount, ModRefSum); 374 errs() << " " << ModRefCount << " mod & ref responses "; 375 PrintPercent(ModRefCount, ModRefSum); 376 errs() << " " << MustCount << " must responses "; 377 PrintPercent(MustCount, ModRefSum); 378 errs() << " " << MustModCount << " must mod responses "; 379 PrintPercent(MustModCount, ModRefSum); 380 errs() << " " << MustRefCount << " must ref responses "; 381 PrintPercent(MustRefCount, ModRefSum); 382 errs() << " " << MustModRefCount << " must mod & ref responses "; 383 PrintPercent(MustModRefCount, ModRefSum); 384 errs() << " Alias Analysis Evaluator Mod/Ref Summary: " 385 << NoModRefCount * 100 / ModRefSum << "%/" 386 << ModCount * 100 / ModRefSum << "%/" << RefCount * 100 / ModRefSum 387 << "%/" << ModRefCount * 100 / ModRefSum << "%/" 388 << MustCount * 100 / ModRefSum << "%/" 389 << MustRefCount * 100 / ModRefSum << "%/" 390 << MustModCount * 100 / ModRefSum << "%/" 391 << MustModRefCount * 100 / ModRefSum << "%\n"; 392 } 393 } 394 395 namespace llvm { 396 class AAEvalLegacyPass : public FunctionPass { 397 std::unique_ptr<AAEvaluator> P; 398 399 public: 400 static char ID; // Pass identification, replacement for typeid 401 AAEvalLegacyPass() : FunctionPass(ID) { 402 initializeAAEvalLegacyPassPass(*PassRegistry::getPassRegistry()); 403 } 404 405 void getAnalysisUsage(AnalysisUsage &AU) const override { 406 AU.addRequired<AAResultsWrapperPass>(); 407 AU.setPreservesAll(); 408 } 409 410 bool doInitialization(Module &M) override { 411 P.reset(new AAEvaluator()); 412 return false; 413 } 414 415 bool runOnFunction(Function &F) override { 416 P->runInternal(F, getAnalysis<AAResultsWrapperPass>().getAAResults()); 417 return false; 418 } 419 bool doFinalization(Module &M) override { 420 P.reset(); 421 return false; 422 } 423 }; 424 } 425 426 char AAEvalLegacyPass::ID = 0; 427 INITIALIZE_PASS_BEGIN(AAEvalLegacyPass, "aa-eval", 428 "Exhaustive Alias Analysis Precision Evaluator", false, 429 true) 430 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 431 INITIALIZE_PASS_END(AAEvalLegacyPass, "aa-eval", 432 "Exhaustive Alias Analysis Precision Evaluator", false, 433 true) 434 435 FunctionPass *llvm::createAAEvalPass() { return new AAEvalLegacyPass(); } 436