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