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