"Fossies" - the Fresh Open Source Software Archive

Member "clamav-0.102.3/libclamav/c++/llvm/lib/Analysis/AliasAnalysisEvaluator.cpp" (12 May 2020, 10406 Bytes) of package /linux/misc/clamav-0.102.3.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "AliasAnalysisEvaluator.cpp" see the Fossies "Dox" file reference documentation.

    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 // This file implements a simple N^2 alias analysis accuracy evaluator.
   11 // Basically, for each function in the program, it simply queries to see how the
   12 // alias analysis implementation answers alias queries between each pair of
   13 // pointers in the function.
   14 //
   15 // This is inspired and adapted from code by: Naveen Neelakantam, Francesco
   16 // Spadini, and Wojciech Stryjewski.
   17 //
   18 //===----------------------------------------------------------------------===//
   19 
   20 #include "llvm/Constants.h"
   21 #include "llvm/DerivedTypes.h"
   22 #include "llvm/Function.h"
   23 #include "llvm/Instructions.h"
   24 #include "llvm/Pass.h"
   25 #include "llvm/Analysis/Passes.h"
   26 #include "llvm/Analysis/AliasAnalysis.h"
   27 #include "llvm/Assembly/Writer.h"
   28 #include "llvm/Support/Debug.h"
   29 #include "llvm/Support/InstIterator.h"
   30 #include "llvm/Support/CommandLine.h"
   31 #include "llvm/Support/raw_ostream.h"
   32 #include "llvm/ADT/SetVector.h"
   33 using namespace llvm;
   34 
   35 static cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden);
   36 
   37 static cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden);
   38 static cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden);
   39 static cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden);
   40 
   41 static cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden);
   42 static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden);
   43 static cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden);
   44 static cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden);
   45 
   46 namespace {
   47   class AAEval : public FunctionPass {
   48     unsigned NoAlias, MayAlias, MustAlias;
   49     unsigned NoModRef, Mod, Ref, ModRef;
   50 
   51   public:
   52     static char ID; // Pass identification, replacement for typeid
   53     AAEval() : FunctionPass(ID) {}
   54 
   55     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
   56       AU.addRequired<AliasAnalysis>();
   57       AU.setPreservesAll();
   58     }
   59 
   60     bool doInitialization(Module &M) {
   61       NoAlias = MayAlias = MustAlias = 0;
   62       NoModRef = Mod = Ref = ModRef = 0;
   63 
   64       if (PrintAll) {
   65         PrintNoAlias = PrintMayAlias = PrintMustAlias = true;
   66         PrintNoModRef = PrintMod = PrintRef = PrintModRef = true;
   67       }
   68       return false;
   69     }
   70 
   71     bool runOnFunction(Function &F);
   72     bool doFinalization(Module &M);
   73   };
   74 }
   75 
   76 char AAEval::ID = 0;
   77 INITIALIZE_PASS(AAEval, "aa-eval",
   78                 "Exhaustive Alias Analysis Precision Evaluator", false, true);
   79 
   80 FunctionPass *llvm::createAAEvalPass() { return new AAEval(); }
   81 
   82 static void PrintResults(const char *Msg, bool P, const Value *V1,
   83                          const Value *V2, const Module *M) {
   84   if (P) {
   85     std::string o1, o2;
   86     {
   87       raw_string_ostream os1(o1), os2(o2);
   88       WriteAsOperand(os1, V1, true, M);
   89       WriteAsOperand(os2, V2, true, M);
   90     }
   91     
   92     if (o2 < o1)
   93       std::swap(o1, o2);
   94     errs() << "  " << Msg << ":\t"
   95            << o1 << ", "
   96            << o2 << "\n";
   97   }
   98 }
   99 
  100 static inline void
  101 PrintModRefResults(const char *Msg, bool P, Instruction *I, Value *Ptr,
  102                    Module *M) {
  103   if (P) {
  104     errs() << "  " << Msg << ":  Ptr: ";
  105     WriteAsOperand(errs(), Ptr, true, M);
  106     errs() << "\t<->" << *I << '\n';
  107   }
  108 }
  109 
  110 static inline void
  111 PrintModRefResults(const char *Msg, bool P, CallSite CSA, CallSite CSB,
  112                    Module *M) {
  113   if (P) {
  114     errs() << "  " << Msg << ": " << *CSA.getInstruction()
  115            << " <-> " << *CSB.getInstruction() << '\n';
  116   }
  117 }
  118 
  119 static inline bool isInterestingPointer(Value *V) {
  120   return V->getType()->isPointerTy()
  121       && !isa<ConstantPointerNull>(V);
  122 }
  123 
  124 bool AAEval::runOnFunction(Function &F) {
  125   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
  126 
  127   SetVector<Value *> Pointers;
  128   SetVector<CallSite> CallSites;
  129 
  130   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
  131     if (I->getType()->isPointerTy())    // Add all pointer arguments.
  132       Pointers.insert(I);
  133 
  134   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
  135     if (I->getType()->isPointerTy()) // Add all pointer instructions.
  136       Pointers.insert(&*I);
  137     Instruction &Inst = *I;
  138     if (CallSite CS = cast<Value>(&Inst)) {
  139       Value *Callee = CS.getCalledValue();
  140       // Skip actual functions for direct function calls.
  141       if (!isa<Function>(Callee) && isInterestingPointer(Callee))
  142         Pointers.insert(Callee);
  143       // Consider formals.
  144       for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
  145            AI != AE; ++AI)
  146         if (isInterestingPointer(*AI))
  147           Pointers.insert(*AI);
  148       CallSites.insert(CS);
  149     } else {
  150       // Consider all operands.
  151       for (Instruction::op_iterator OI = Inst.op_begin(), OE = Inst.op_end();
  152            OI != OE; ++OI)
  153         if (isInterestingPointer(*OI))
  154           Pointers.insert(*OI);
  155     }
  156   }
  157 
  158   if (PrintNoAlias || PrintMayAlias || PrintMustAlias ||
  159       PrintNoModRef || PrintMod || PrintRef || PrintModRef)
  160     errs() << "Function: " << F.getName() << ": " << Pointers.size()
  161            << " pointers, " << CallSites.size() << " call sites\n";
  162 
  163   // iterate over the worklist, and run the full (n^2)/2 disambiguations
  164   for (SetVector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end();
  165        I1 != E; ++I1) {
  166     unsigned I1Size = ~0u;
  167     const Type *I1ElTy = cast<PointerType>((*I1)->getType())->getElementType();
  168     if (I1ElTy->isSized()) I1Size = AA.getTypeStoreSize(I1ElTy);
  169 
  170     for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) {
  171       unsigned I2Size = ~0u;
  172       const Type *I2ElTy =cast<PointerType>((*I2)->getType())->getElementType();
  173       if (I2ElTy->isSized()) I2Size = AA.getTypeStoreSize(I2ElTy);
  174 
  175       switch (AA.alias(*I1, I1Size, *I2, I2Size)) {
  176       case AliasAnalysis::NoAlias:
  177         PrintResults("NoAlias", PrintNoAlias, *I1, *I2, F.getParent());
  178         ++NoAlias; break;
  179       case AliasAnalysis::MayAlias:
  180         PrintResults("MayAlias", PrintMayAlias, *I1, *I2, F.getParent());
  181         ++MayAlias; break;
  182       case AliasAnalysis::MustAlias:
  183         PrintResults("MustAlias", PrintMustAlias, *I1, *I2, F.getParent());
  184         ++MustAlias; break;
  185       default:
  186         errs() << "Unknown alias query result!\n";
  187       }
  188     }
  189   }
  190 
  191   // Mod/ref alias analysis: compare all pairs of calls and values
  192   for (SetVector<CallSite>::iterator C = CallSites.begin(),
  193          Ce = CallSites.end(); C != Ce; ++C) {
  194     Instruction *I = C->getInstruction();
  195 
  196     for (SetVector<Value *>::iterator V = Pointers.begin(), Ve = Pointers.end();
  197          V != Ve; ++V) {
  198       unsigned Size = ~0u;
  199       const Type *ElTy = cast<PointerType>((*V)->getType())->getElementType();
  200       if (ElTy->isSized()) Size = AA.getTypeStoreSize(ElTy);
  201 
  202       switch (AA.getModRefInfo(*C, *V, Size)) {
  203       case AliasAnalysis::NoModRef:
  204         PrintModRefResults("NoModRef", PrintNoModRef, I, *V, F.getParent());
  205         ++NoModRef; break;
  206       case AliasAnalysis::Mod:
  207         PrintModRefResults("Just Mod", PrintMod, I, *V, F.getParent());
  208         ++Mod; break;
  209       case AliasAnalysis::Ref:
  210         PrintModRefResults("Just Ref", PrintRef, I, *V, F.getParent());
  211         ++Ref; break;
  212       case AliasAnalysis::ModRef:
  213         PrintModRefResults("Both ModRef", PrintModRef, I, *V, F.getParent());
  214         ++ModRef; break;
  215       default:
  216         errs() << "Unknown alias query result!\n";
  217       }
  218     }
  219   }
  220 
  221   // Mod/ref alias analysis: compare all pairs of calls
  222   for (SetVector<CallSite>::iterator C = CallSites.begin(),
  223          Ce = CallSites.end(); C != Ce; ++C) {
  224     for (SetVector<CallSite>::iterator D = CallSites.begin(); D != Ce; ++D) {
  225       if (D == C)
  226         continue;
  227       switch (AA.getModRefInfo(*C, *D)) {
  228       case AliasAnalysis::NoModRef:
  229         PrintModRefResults("NoModRef", PrintNoModRef, *C, *D, F.getParent());
  230         ++NoModRef; break;
  231       case AliasAnalysis::Mod:
  232         PrintModRefResults("Just Mod", PrintMod, *C, *D, F.getParent());
  233         ++Mod; break;
  234       case AliasAnalysis::Ref:
  235         PrintModRefResults("Just Ref", PrintRef, *C, *D, F.getParent());
  236         ++Ref; break;
  237       case AliasAnalysis::ModRef:
  238         PrintModRefResults("Both ModRef", PrintModRef, *C, *D, F.getParent());
  239         ++ModRef; break;
  240       }
  241     }
  242   }
  243 
  244   return false;
  245 }
  246 
  247 static void PrintPercent(unsigned Num, unsigned Sum) {
  248   errs() << "(" << Num*100ULL/Sum << "."
  249          << ((Num*1000ULL/Sum) % 10) << "%)\n";
  250 }
  251 
  252 bool AAEval::doFinalization(Module &M) {
  253   unsigned AliasSum = NoAlias + MayAlias + MustAlias;
  254   errs() << "===== Alias Analysis Evaluator Report =====\n";
  255   if (AliasSum == 0) {
  256     errs() << "  Alias Analysis Evaluator Summary: No pointers!\n";
  257   } else {
  258     errs() << "  " << AliasSum << " Total Alias Queries Performed\n";
  259     errs() << "  " << NoAlias << " no alias responses ";
  260     PrintPercent(NoAlias, AliasSum);
  261     errs() << "  " << MayAlias << " may alias responses ";
  262     PrintPercent(MayAlias, AliasSum);
  263     errs() << "  " << MustAlias << " must alias responses ";
  264     PrintPercent(MustAlias, AliasSum);
  265     errs() << "  Alias Analysis Evaluator Pointer Alias Summary: "
  266            << NoAlias*100/AliasSum  << "%/" << MayAlias*100/AliasSum << "%/"
  267            << MustAlias*100/AliasSum << "%\n";
  268   }
  269 
  270   // Display the summary for mod/ref analysis
  271   unsigned ModRefSum = NoModRef + Mod + Ref + ModRef;
  272   if (ModRefSum == 0) {
  273     errs() << "  Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!\n";
  274   } else {
  275     errs() << "  " << ModRefSum << " Total ModRef Queries Performed\n";
  276     errs() << "  " << NoModRef << " no mod/ref responses ";
  277     PrintPercent(NoModRef, ModRefSum);
  278     errs() << "  " << Mod << " mod responses ";
  279     PrintPercent(Mod, ModRefSum);
  280     errs() << "  " << Ref << " ref responses ";
  281     PrintPercent(Ref, ModRefSum);
  282     errs() << "  " << ModRef << " mod & ref responses ";
  283     PrintPercent(ModRef, ModRefSum);
  284     errs() << "  Alias Analysis Evaluator Mod/Ref Summary: "
  285            << NoModRef*100/ModRefSum  << "%/" << Mod*100/ModRefSum << "%/"
  286            << Ref*100/ModRefSum << "%/" << ModRef*100/ModRefSum << "%\n";
  287   }
  288 
  289   return false;
  290 }