lib/Analysis/AliasAnalysisEvaluator.cpp

   1 //===- AliasAnalysisEvaluator.cpp - Alias Analysis Accuracy Evaluator -----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/AliasAnalysisEvaluator.h"
  11 #include "llvm/ADT/SetVector.h"
  12 #include "llvm/Analysis/AliasAnalysis.h"
  13 #include "llvm/IR/Constants.h"
  14 #include "llvm/IR/DataLayout.h"
  15 #include "llvm/IR/DerivedTypes.h"
  16 #include "llvm/IR/Function.h"
  17 #include "llvm/IR/InstIterator.h"
  18 #include "llvm/IR/Instructions.h"
  19 #include "llvm/IR/Module.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->getCalledValue();
 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   }
 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::unknown();
 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(); }