320 lines · 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-exception6//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"19using namespace llvm;20 21static cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden);22 23static cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden);24static cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden);25static cl::opt<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden);26static cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden);27 28static cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden);29static cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden);30static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden);31static cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden);32 33static cl::opt<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden);34 35static 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 69static 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 81static 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 88static 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 96PreservedAnalyses AAEvaluator::run(Function &F, FunctionAnalysisManager &AM) {97 runInternal(F, AM.getResult<AAManager>(F));98 return PreservedAnalyses::all();99}100 101void AAEvaluator::runInternal(Function &F, AAResults &AA) {102 const DataLayout &DL = F.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 disambiguations129 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, store158 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, store184 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 values212 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 calls240 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 268static void PrintPercent(int64_t Num, int64_t Sum) {269 errs() << "(" << Num * 100LL / Sum << "." << ((Num * 1000LL / Sum) % 10)270 << "%)\n";271}272 273AAEvaluator::~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 analysis300 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 / ModRefSum317 << "%/" << ModRefCount * 100 / ModRefSum << "%\n";318 }319}320