llvm/lib/Analysis/AliasAnalysisEvaluator.cpp

   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/DataLayout.h"
  13 #include "llvm/IR/Function.h"
  14 #include "llvm/IR/InstIterator.h"
  15 #include "llvm/IR/Instructions.h"
  16 #include "llvm/IR/Module.h"
  17 #include "llvm/InitializePasses.h"
  18 #include "llvm/Pass.h"
  19 #include "llvm/Support/CommandLine.h"
  20 #include "llvm/Support/raw_ostream.h"
  21 using namespace llvm;
  22
  23 static cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden);
  24
  25 static cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden);
  26 static cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden);
  27 static cl::opt<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden);
  28 static cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden);
  29
  30 static cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden);
  31 static cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden);
  32 static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden);
  33 static cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden);
  34
  35 static cl::opt<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden);
  36
  37 static void PrintResults(AliasResult AR, bool P,
  38                          std::pair<const Value *, Type *> Loc1,
  39                          std::pair<const Value *, Type *> Loc2,
  40                          const Module *M) {
  41   if (PrintAll || P) {
  42     Type *Ty1 = Loc1.second, *Ty2 = Loc2.second;
  43     unsigned AS1 = Loc1.first->getType()->getPointerAddressSpace();
  44     unsigned AS2 = Loc2.first->getType()->getPointerAddressSpace();
  45     std::string o1, o2;
  46     {
  47       raw_string_ostream os1(o1), os2(o2);
  48       Loc1.first->printAsOperand(os1, false, M);
  49       Loc2.first->printAsOperand(os2, false, M);
  50     }
  51
  52     if (o2 < o1) {
  53       std::swap(o1, o2);
  54       std::swap(Ty1, Ty2);
  55       std::swap(AS1, AS2);
  56       // Change offset sign for the local AR, for printing only.
  57       AR.swap();
  58     }
  59     errs() << "  " << AR << ":\t";
  60     Ty1->print(errs(), false, /* NoDetails */ true);
  61     if (AS1 != 0)
  62       errs() << " addrspace(" << AS1 << ")";
  63     errs() << "* " << o1 << ", ";
  64     Ty2->print(errs(), false, /* NoDetails */ true);
  65     if (AS2 != 0)
  66       errs() << " addrspace(" << AS2 << ")";
  67     errs() << "* " << o2 << "\n";
  68   }
  69 }
  70
  71 static inline void PrintModRefResults(
  72     const char *Msg, bool P, Instruction *I,
  73     std::pair<const Value *, Type *> Loc, Module *M) {
  74   if (PrintAll || P) {
  75     errs() << "  " << Msg << ":  Ptr: ";
  76     Loc.second->print(errs(), false, /* NoDetails */ true);
  77     errs() << "* ";
  78     Loc.first->printAsOperand(errs(), false, M);
  79     errs() << "\t<->" << *I << '\n';
  80   }
  81 }
  82
  83 static inline void PrintModRefResults(const char *Msg, bool P, CallBase *CallA,
  84                                       CallBase *CallB, Module *M) {
  85   if (PrintAll || P) {
  86     errs() << "  " << Msg << ": " << *CallA << " <-> " << *CallB << '\n';
  87   }
  88 }
  89
  90 static inline void PrintLoadStoreResults(AliasResult AR, bool P,
  91                                          const Value *V1, const Value *V2,
  92                                          const Module *M) {
  93   if (PrintAll || P) {
  94     errs() << "  " << AR << ": " << *V1 << " <-> " << *V2 << '\n';
  95   }
  96 }
  97
  98 PreservedAnalyses AAEvaluator::run(Function &F, FunctionAnalysisManager &AM) {
  99   runInternal(F, AM.getResult<AAManager>(F));
 100   return PreservedAnalyses::all();
 101 }
 102
 103 void AAEvaluator::runInternal(Function &F, AAResults &AA) {
 104   const DataLayout &DL = F.getParent()->getDataLayout();
 105
 106   ++FunctionCount;
 107
 108   SetVector<std::pair<const Value *, Type *>> Pointers;
 109   SmallSetVector<CallBase *, 16> Calls;
 110   SetVector<Value *> Loads;
 111   SetVector<Value *> Stores;
 112
 113   for (Instruction &Inst : instructions(F)) {
 114     if (auto *LI = dyn_cast<LoadInst>(&Inst)) {
 115       Pointers.insert({LI->getPointerOperand(), LI->getType()});
 116       Loads.insert(LI);
 117     } else if (auto *SI = dyn_cast<StoreInst>(&Inst)) {
 118       Pointers.insert({SI->getPointerOperand(),
 119                        SI->getValueOperand()->getType()});
 120       Stores.insert(SI);
 121     } else if (auto *CB = dyn_cast<CallBase>(&Inst))
 122       Calls.insert(CB);
 123   }
 124
 125   if (PrintAll || PrintNoAlias || PrintMayAlias || PrintPartialAlias ||
 126       PrintMustAlias || PrintNoModRef || PrintMod || PrintRef || PrintModRef)
 127     errs() << "Function: " << F.getName() << ": " << Pointers.size()
 128            << " pointers, " << Calls.size() << " call sites\n";
 129
 130   // iterate over the worklist, and run the full (n^2)/2 disambiguations
 131   for (auto I1 = Pointers.begin(), E = Pointers.end(); I1 != E; ++I1) {
 132     LocationSize Size1 = LocationSize::precise(DL.getTypeStoreSize(I1->second));
 133     for (auto I2 = Pointers.begin(); I2 != I1; ++I2) {
 134       LocationSize Size2 =
 135           LocationSize::precise(DL.getTypeStoreSize(I2->second));
 136       AliasResult AR = AA.alias(I1->first, Size1, I2->first, Size2);
 137       switch (AR) {
 138       case AliasResult::NoAlias:
 139         PrintResults(AR, PrintNoAlias, *I1, *I2, F.getParent());
 140         ++NoAliasCount;
 141         break;
 142       case AliasResult::MayAlias:
 143         PrintResults(AR, PrintMayAlias, *I1, *I2, F.getParent());
 144         ++MayAliasCount;
 145         break;
 146       case AliasResult::PartialAlias:
 147         PrintResults(AR, PrintPartialAlias, *I1, *I2, F.getParent());
 148         ++PartialAliasCount;
 149         break;
 150       case AliasResult::MustAlias:
 151         PrintResults(AR, PrintMustAlias, *I1, *I2, F.getParent());
 152         ++MustAliasCount;
 153         break;
 154       }
 155     }
 156   }
 157
 158   if (EvalAAMD) {
 159     // iterate over all pairs of load, store
 160     for (Value *Load : Loads) {
 161       for (Value *Store : Stores) {
 162         AliasResult AR = AA.alias(MemoryLocation::get(cast<LoadInst>(Load)),
 163                                   MemoryLocation::get(cast<StoreInst>(Store)));
 164         switch (AR) {
 165         case AliasResult::NoAlias:
 166           PrintLoadStoreResults(AR, PrintNoAlias, Load, Store, F.getParent());
 167           ++NoAliasCount;
 168           break;
 169         case AliasResult::MayAlias:
 170           PrintLoadStoreResults(AR, PrintMayAlias, Load, Store, F.getParent());
 171           ++MayAliasCount;
 172           break;
 173         case AliasResult::PartialAlias:
 174           PrintLoadStoreResults(AR, PrintPartialAlias, Load, Store, F.getParent());
 175           ++PartialAliasCount;
 176           break;
 177         case AliasResult::MustAlias:
 178           PrintLoadStoreResults(AR, PrintMustAlias, Load, Store, F.getParent());
 179           ++MustAliasCount;
 180           break;
 181         }
 182       }
 183     }
 184
 185     // iterate over all pairs of store, store
 186     for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end();
 187          I1 != E; ++I1) {
 188       for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) {
 189         AliasResult AR = AA.alias(MemoryLocation::get(cast<StoreInst>(*I1)),
 190                                   MemoryLocation::get(cast<StoreInst>(*I2)));
 191         switch (AR) {
 192         case AliasResult::NoAlias:
 193           PrintLoadStoreResults(AR, PrintNoAlias, *I1, *I2, F.getParent());
 194           ++NoAliasCount;
 195           break;
 196         case AliasResult::MayAlias:
 197           PrintLoadStoreResults(AR, PrintMayAlias, *I1, *I2, F.getParent());
 198           ++MayAliasCount;
 199           break;
 200         case AliasResult::PartialAlias:
 201           PrintLoadStoreResults(AR, PrintPartialAlias, *I1, *I2, F.getParent());
 202           ++PartialAliasCount;
 203           break;
 204         case AliasResult::MustAlias:
 205           PrintLoadStoreResults(AR, PrintMustAlias, *I1, *I2, F.getParent());
 206           ++MustAliasCount;
 207           break;
 208         }
 209       }
 210     }
 211   }
 212
 213   // Mod/ref alias analysis: compare all pairs of calls and values
 214   for (CallBase *Call : Calls) {
 215     for (const auto &Pointer : Pointers) {
 216       LocationSize Size =
 217           LocationSize::precise(DL.getTypeStoreSize(Pointer.second));
 218       switch (AA.getModRefInfo(Call, Pointer.first, Size)) {
 219       case ModRefInfo::NoModRef:
 220         PrintModRefResults("NoModRef", PrintNoModRef, Call, Pointer,
 221                            F.getParent());
 222         ++NoModRefCount;
 223         break;
 224       case ModRefInfo::Mod:
 225         PrintModRefResults("Just Mod", PrintMod, Call, Pointer, F.getParent());
 226         ++ModCount;
 227         break;
 228       case ModRefInfo::Ref:
 229         PrintModRefResults("Just Ref", PrintRef, Call, Pointer, F.getParent());
 230         ++RefCount;
 231         break;
 232       case ModRefInfo::ModRef:
 233         PrintModRefResults("Both ModRef", PrintModRef, Call, Pointer,
 234                            F.getParent());
 235         ++ModRefCount;
 236         break;
 237       }
 238     }
 239   }
 240
 241   // Mod/ref alias analysis: compare all pairs of calls
 242   for (CallBase *CallA : Calls) {
 243     for (CallBase *CallB : Calls) {
 244       if (CallA == CallB)
 245         continue;
 246       switch (AA.getModRefInfo(CallA, CallB)) {
 247       case ModRefInfo::NoModRef:
 248         PrintModRefResults("NoModRef", PrintNoModRef, CallA, CallB,
 249                            F.getParent());
 250         ++NoModRefCount;
 251         break;
 252       case ModRefInfo::Mod:
 253         PrintModRefResults("Just Mod", PrintMod, CallA, CallB, F.getParent());
 254         ++ModCount;
 255         break;
 256       case ModRefInfo::Ref:
 257         PrintModRefResults("Just Ref", PrintRef, CallA, CallB, F.getParent());
 258         ++RefCount;
 259         break;
 260       case ModRefInfo::ModRef:
 261         PrintModRefResults("Both ModRef", PrintModRef, CallA, CallB,
 262                            F.getParent());
 263         ++ModRefCount;
 264         break;
 265       }
 266     }
 267   }
 268 }
 269
 270 static void PrintPercent(int64_t Num, int64_t Sum) {
 271   errs() << "(" << Num * 100LL / Sum << "." << ((Num * 1000LL / Sum) % 10)
 272          << "%)\n";
 273 }
 274
 275 AAEvaluator::~AAEvaluator() {
 276   if (FunctionCount == 0)
 277     return;
 278
 279   int64_t AliasSum =
 280       NoAliasCount + MayAliasCount + PartialAliasCount + MustAliasCount;
 281   errs() << "===== Alias Analysis Evaluator Report =====\n";
 282   if (AliasSum == 0) {
 283     errs() << "  Alias Analysis Evaluator Summary: No pointers!\n";
 284   } else {
 285     errs() << "  " << AliasSum << " Total Alias Queries Performed\n";
 286     errs() << "  " << NoAliasCount << " no alias responses ";
 287     PrintPercent(NoAliasCount, AliasSum);
 288     errs() << "  " << MayAliasCount << " may alias responses ";
 289     PrintPercent(MayAliasCount, AliasSum);
 290     errs() << "  " << PartialAliasCount << " partial alias responses ";
 291     PrintPercent(PartialAliasCount, AliasSum);
 292     errs() << "  " << MustAliasCount << " must alias responses ";
 293     PrintPercent(MustAliasCount, AliasSum);
 294     errs() << "  Alias Analysis Evaluator Pointer Alias Summary: "
 295            << NoAliasCount * 100 / AliasSum << "%/"
 296            << MayAliasCount * 100 / AliasSum << "%/"
 297            << PartialAliasCount * 100 / AliasSum << "%/"
 298            << MustAliasCount * 100 / AliasSum << "%\n";
 299   }
 300
 301   // Display the summary for mod/ref analysis
 302   int64_t ModRefSum = NoModRefCount + RefCount + ModCount + ModRefCount;
 303   if (ModRefSum == 0) {
 304     errs() << "  Alias Analysis Mod/Ref Evaluator Summary: no "
 305               "mod/ref!\n";
 306   } else {
 307     errs() << "  " << ModRefSum << " Total ModRef Queries Performed\n";
 308     errs() << "  " << NoModRefCount << " no mod/ref responses ";
 309     PrintPercent(NoModRefCount, ModRefSum);
 310     errs() << "  " << ModCount << " mod responses ";
 311     PrintPercent(ModCount, ModRefSum);
 312     errs() << "  " << RefCount << " ref responses ";
 313     PrintPercent(RefCount, ModRefSum);
 314     errs() << "  " << ModRefCount << " mod & ref responses ";
 315     PrintPercent(ModRefCount, ModRefSum);
 316     errs() << "  Alias Analysis Evaluator Mod/Ref Summary: "
 317            << NoModRefCount * 100 / ModRefSum << "%/"
 318            << ModCount * 100 / ModRefSum << "%/" << RefCount * 100 / ModRefSum
 319            << "%/" << ModRefCount * 100 / ModRefSum << "%\n";
 320   }
 321 }
 322
 323 namespace llvm {
 324 class AAEvalLegacyPass : public FunctionPass {
 325   std::unique_ptr<AAEvaluator> P;
 326
 327 public:
 328   static char ID; // Pass identification, replacement for typeid
 329   AAEvalLegacyPass() : FunctionPass(ID) {
 330     initializeAAEvalLegacyPassPass(*PassRegistry::getPassRegistry());
 331   }
 332
 333   void getAnalysisUsage(AnalysisUsage &AU) const override {
 334     AU.addRequired<AAResultsWrapperPass>();
 335     AU.setPreservesAll();
 336   }
 337
 338   bool doInitialization(Module &M) override {
 339     P.reset(new AAEvaluator());
 340     return false;
 341   }
 342
 343   bool runOnFunction(Function &F) override {
 344     P->runInternal(F, getAnalysis<AAResultsWrapperPass>().getAAResults());
 345     return false;
 346   }
 347   bool doFinalization(Module &M) override {
 348     P.reset();
 349     return false;
 350   }
 351 };
 352 }
 353
 354 char AAEvalLegacyPass::ID = 0;
 355 INITIALIZE_PASS_BEGIN(AAEvalLegacyPass, "aa-eval",
 356                       "Exhaustive Alias Analysis Precision Evaluator", false,
 357                       true)
 358 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 359 INITIALIZE_PASS_END(AAEvalLegacyPass, "aa-eval",
 360                     "Exhaustive Alias Analysis Precision Evaluator", false,
 361                     true)
 362
 363 FunctionPass *llvm::createAAEvalPass() { return new AAEvalLegacyPass(); }