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::unknown(); 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::unknown(); 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 // We assume that alias(I1, I2) == alias(I2, I1) and only print one 175 // order. Make sure this assumption actually holds. 176 // TODO: We should probably assert this in AA itself under 177 // EXPENSIVE_CHECKS. This would need some more thorough verification that 178 // all AA queries are symmetric first. 179 assert(AR == AA.alias(*I2, I2Size, *I1, I1Size) && 180 "AA query not symmetric"); 181 } 182 } 183 184 if (EvalAAMD) { 185 // iterate over all pairs of load, store 186 for (Value *Load : Loads) { 187 for (Value *Store : Stores) { 188 AliasResult AR = AA.alias(MemoryLocation::get(cast<LoadInst>(Load)), 189 MemoryLocation::get(cast<StoreInst>(Store))); 190 switch (AR) { 191 case NoAlias: 192 PrintLoadStoreResults(AR, PrintNoAlias, Load, Store, F.getParent()); 193 ++NoAliasCount; 194 break; 195 case MayAlias: 196 PrintLoadStoreResults(AR, PrintMayAlias, Load, Store, F.getParent()); 197 ++MayAliasCount; 198 break; 199 case PartialAlias: 200 PrintLoadStoreResults(AR, PrintPartialAlias, Load, Store, F.getParent()); 201 ++PartialAliasCount; 202 break; 203 case MustAlias: 204 PrintLoadStoreResults(AR, PrintMustAlias, Load, Store, F.getParent()); 205 ++MustAliasCount; 206 break; 207 } 208 } 209 } 210 211 // iterate over all pairs of store, store 212 for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end(); 213 I1 != E; ++I1) { 214 for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) { 215 AliasResult AR = AA.alias(MemoryLocation::get(cast<StoreInst>(*I1)), 216 MemoryLocation::get(cast<StoreInst>(*I2))); 217 switch (AR) { 218 case NoAlias: 219 PrintLoadStoreResults(AR, PrintNoAlias, *I1, *I2, F.getParent()); 220 ++NoAliasCount; 221 break; 222 case MayAlias: 223 PrintLoadStoreResults(AR, PrintMayAlias, *I1, *I2, F.getParent()); 224 ++MayAliasCount; 225 break; 226 case PartialAlias: 227 PrintLoadStoreResults(AR, PrintPartialAlias, *I1, *I2, F.getParent()); 228 ++PartialAliasCount; 229 break; 230 case MustAlias: 231 PrintLoadStoreResults(AR, PrintMustAlias, *I1, *I2, F.getParent()); 232 ++MustAliasCount; 233 break; 234 } 235 } 236 } 237 } 238 239 // Mod/ref alias analysis: compare all pairs of calls and values 240 for (CallBase *Call : Calls) { 241 for (auto Pointer : Pointers) { 242 auto Size = LocationSize::unknown(); 243 Type *ElTy = cast<PointerType>(Pointer->getType())->getElementType(); 244 if (ElTy->isSized()) 245 Size = LocationSize::precise(DL.getTypeStoreSize(ElTy)); 246 247 switch (AA.getModRefInfo(Call, Pointer, Size)) { 248 case ModRefInfo::NoModRef: 249 PrintModRefResults("NoModRef", PrintNoModRef, Call, Pointer, 250 F.getParent()); 251 ++NoModRefCount; 252 break; 253 case ModRefInfo::Mod: 254 PrintModRefResults("Just Mod", PrintMod, Call, Pointer, F.getParent()); 255 ++ModCount; 256 break; 257 case ModRefInfo::Ref: 258 PrintModRefResults("Just Ref", PrintRef, Call, Pointer, F.getParent()); 259 ++RefCount; 260 break; 261 case ModRefInfo::ModRef: 262 PrintModRefResults("Both ModRef", PrintModRef, Call, Pointer, 263 F.getParent()); 264 ++ModRefCount; 265 break; 266 case ModRefInfo::Must: 267 PrintModRefResults("Must", PrintMust, Call, Pointer, F.getParent()); 268 ++MustCount; 269 break; 270 case ModRefInfo::MustMod: 271 PrintModRefResults("Just Mod (MustAlias)", PrintMustMod, Call, Pointer, 272 F.getParent()); 273 ++MustModCount; 274 break; 275 case ModRefInfo::MustRef: 276 PrintModRefResults("Just Ref (MustAlias)", PrintMustRef, Call, Pointer, 277 F.getParent()); 278 ++MustRefCount; 279 break; 280 case ModRefInfo::MustModRef: 281 PrintModRefResults("Both ModRef (MustAlias)", PrintMustModRef, Call, 282 Pointer, F.getParent()); 283 ++MustModRefCount; 284 break; 285 } 286 } 287 } 288 289 // Mod/ref alias analysis: compare all pairs of calls 290 for (CallBase *CallA : Calls) { 291 for (CallBase *CallB : Calls) { 292 if (CallA == CallB) 293 continue; 294 switch (AA.getModRefInfo(CallA, CallB)) { 295 case ModRefInfo::NoModRef: 296 PrintModRefResults("NoModRef", PrintNoModRef, CallA, CallB, 297 F.getParent()); 298 ++NoModRefCount; 299 break; 300 case ModRefInfo::Mod: 301 PrintModRefResults("Just Mod", PrintMod, CallA, CallB, F.getParent()); 302 ++ModCount; 303 break; 304 case ModRefInfo::Ref: 305 PrintModRefResults("Just Ref", PrintRef, CallA, CallB, F.getParent()); 306 ++RefCount; 307 break; 308 case ModRefInfo::ModRef: 309 PrintModRefResults("Both ModRef", PrintModRef, CallA, CallB, 310 F.getParent()); 311 ++ModRefCount; 312 break; 313 case ModRefInfo::Must: 314 PrintModRefResults("Must", PrintMust, CallA, CallB, F.getParent()); 315 ++MustCount; 316 break; 317 case ModRefInfo::MustMod: 318 PrintModRefResults("Just Mod (MustAlias)", PrintMustMod, CallA, CallB, 319 F.getParent()); 320 ++MustModCount; 321 break; 322 case ModRefInfo::MustRef: 323 PrintModRefResults("Just Ref (MustAlias)", PrintMustRef, CallA, CallB, 324 F.getParent()); 325 ++MustRefCount; 326 break; 327 case ModRefInfo::MustModRef: 328 PrintModRefResults("Both ModRef (MustAlias)", PrintMustModRef, CallA, 329 CallB, F.getParent()); 330 ++MustModRefCount; 331 break; 332 } 333 } 334 } 335 } 336 337 static void PrintPercent(int64_t Num, int64_t Sum) { 338 errs() << "(" << Num * 100LL / Sum << "." << ((Num * 1000LL / Sum) % 10) 339 << "%)\n"; 340 } 341 342 AAEvaluator::~AAEvaluator() { 343 if (FunctionCount == 0) 344 return; 345 346 int64_t AliasSum = 347 NoAliasCount + MayAliasCount + PartialAliasCount + MustAliasCount; 348 errs() << "===== Alias Analysis Evaluator Report =====\n"; 349 if (AliasSum == 0) { 350 errs() << " Alias Analysis Evaluator Summary: No pointers!\n"; 351 } else { 352 errs() << " " << AliasSum << " Total Alias Queries Performed\n"; 353 errs() << " " << NoAliasCount << " no alias responses "; 354 PrintPercent(NoAliasCount, AliasSum); 355 errs() << " " << MayAliasCount << " may alias responses "; 356 PrintPercent(MayAliasCount, AliasSum); 357 errs() << " " << PartialAliasCount << " partial alias responses "; 358 PrintPercent(PartialAliasCount, AliasSum); 359 errs() << " " << MustAliasCount << " must alias responses "; 360 PrintPercent(MustAliasCount, AliasSum); 361 errs() << " Alias Analysis Evaluator Pointer Alias Summary: " 362 << NoAliasCount * 100 / AliasSum << "%/" 363 << MayAliasCount * 100 / AliasSum << "%/" 364 << PartialAliasCount * 100 / AliasSum << "%/" 365 << MustAliasCount * 100 / AliasSum << "%\n"; 366 } 367 368 // Display the summary for mod/ref analysis 369 int64_t ModRefSum = NoModRefCount + RefCount + ModCount + ModRefCount + 370 MustCount + MustRefCount + MustModCount + MustModRefCount; 371 if (ModRefSum == 0) { 372 errs() << " Alias Analysis Mod/Ref Evaluator Summary: no " 373 "mod/ref!\n"; 374 } else { 375 errs() << " " << ModRefSum << " Total ModRef Queries Performed\n"; 376 errs() << " " << NoModRefCount << " no mod/ref responses "; 377 PrintPercent(NoModRefCount, ModRefSum); 378 errs() << " " << ModCount << " mod responses "; 379 PrintPercent(ModCount, ModRefSum); 380 errs() << " " << RefCount << " ref responses "; 381 PrintPercent(RefCount, ModRefSum); 382 errs() << " " << ModRefCount << " mod & ref responses "; 383 PrintPercent(ModRefCount, ModRefSum); 384 errs() << " " << MustCount << " must responses "; 385 PrintPercent(MustCount, ModRefSum); 386 errs() << " " << MustModCount << " must mod responses "; 387 PrintPercent(MustModCount, ModRefSum); 388 errs() << " " << MustRefCount << " must ref responses "; 389 PrintPercent(MustRefCount, ModRefSum); 390 errs() << " " << MustModRefCount << " must mod & ref responses "; 391 PrintPercent(MustModRefCount, ModRefSum); 392 errs() << " Alias Analysis Evaluator Mod/Ref Summary: " 393 << NoModRefCount * 100 / ModRefSum << "%/" 394 << ModCount * 100 / ModRefSum << "%/" << RefCount * 100 / ModRefSum 395 << "%/" << ModRefCount * 100 / ModRefSum << "%/" 396 << MustCount * 100 / ModRefSum << "%/" 397 << MustRefCount * 100 / ModRefSum << "%/" 398 << MustModCount * 100 / ModRefSum << "%/" 399 << MustModRefCount * 100 / ModRefSum << "%\n"; 400 } 401 } 402 403 namespace llvm { 404 class AAEvalLegacyPass : public FunctionPass { 405 std::unique_ptr<AAEvaluator> P; 406 407 public: 408 static char ID; // Pass identification, replacement for typeid 409 AAEvalLegacyPass() : FunctionPass(ID) { 410 initializeAAEvalLegacyPassPass(*PassRegistry::getPassRegistry()); 411 } 412 413 void getAnalysisUsage(AnalysisUsage &AU) const override { 414 AU.addRequired<AAResultsWrapperPass>(); 415 AU.setPreservesAll(); 416 } 417 418 bool doInitialization(Module &M) override { 419 P.reset(new AAEvaluator()); 420 return false; 421 } 422 423 bool runOnFunction(Function &F) override { 424 P->runInternal(F, getAnalysis<AAResultsWrapperPass>().getAAResults()); 425 return false; 426 } 427 bool doFinalization(Module &M) override { 428 P.reset(); 429 return false; 430 } 431 }; 432 } 433 434 char AAEvalLegacyPass::ID = 0; 435 INITIALIZE_PASS_BEGIN(AAEvalLegacyPass, "aa-eval", 436 "Exhaustive Alias Analysis Precision Evaluator", false, 437 true) 438 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 439 INITIALIZE_PASS_END(AAEvalLegacyPass, "aa-eval", 440 "Exhaustive Alias Analysis Precision Evaluator", false, 441 true) 442 443 FunctionPass *llvm::createAAEvalPass() { return new AAEvalLegacyPass(); } 444