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