X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FAliasAnalysisEvaluator.cpp;h=fe4bd4cc21099c0280824115be33a927c92d30ea;hb=798ace2e58a4bbe607d907a9efc7388e221dc431;hp=f42fde899737bdf4b076cc7d8e77b2b376de824b;hpb=2b37d7cf28b1382420b5e4007042feeb66d21ac8;p=oota-llvm.git diff --git a/lib/Analysis/AliasAnalysisEvaluator.cpp b/lib/Analysis/AliasAnalysisEvaluator.cpp index f42fde89973..fe4bd4cc210 100644 --- a/lib/Analysis/AliasAnalysisEvaluator.cpp +++ b/lib/Analysis/AliasAnalysisEvaluator.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -17,71 +17,91 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" -#include "llvm/Pass.h" #include "llvm/Analysis/Passes.h" +#include "llvm/ADT/SetVector.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Assembly/Writer.h" -#include "llvm/Target/TargetData.h" -#include "llvm/Support/InstIterator.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Instructions.h" +#include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" -#include -#include - +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; -namespace { - cl::opt PrintAll("print-all-alias-modref-info", cl::ReallyHidden); +static cl::opt PrintAll("print-all-alias-modref-info", cl::ReallyHidden); + +static cl::opt PrintNoAlias("print-no-aliases", cl::ReallyHidden); +static cl::opt PrintMayAlias("print-may-aliases", cl::ReallyHidden); +static cl::opt PrintPartialAlias("print-partial-aliases", cl::ReallyHidden); +static cl::opt PrintMustAlias("print-must-aliases", cl::ReallyHidden); - cl::opt PrintNoAlias("print-no-aliases", cl::ReallyHidden); - cl::opt PrintMayAlias("print-may-aliases", cl::ReallyHidden); - cl::opt PrintMustAlias("print-must-aliases", cl::ReallyHidden); +static cl::opt PrintNoModRef("print-no-modref", cl::ReallyHidden); +static cl::opt PrintMod("print-mod", cl::ReallyHidden); +static cl::opt PrintRef("print-ref", cl::ReallyHidden); +static cl::opt PrintModRef("print-modref", cl::ReallyHidden); - cl::opt PrintNoModRef("print-no-modref", cl::ReallyHidden); - cl::opt PrintMod("print-mod", cl::ReallyHidden); - cl::opt PrintRef("print-ref", cl::ReallyHidden); - cl::opt PrintModRef("print-modref", cl::ReallyHidden); +static cl::opt EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden); +namespace { class AAEval : public FunctionPass { - unsigned NoAlias, MayAlias, MustAlias; + unsigned NoAlias, MayAlias, PartialAlias, MustAlias; unsigned NoModRef, Mod, Ref, ModRef; public: - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + static char ID; // Pass identification, replacement for typeid + AAEval() : FunctionPass(ID) { + initializeAAEvalPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); AU.setPreservesAll(); } - bool doInitialization(Module &M) { - NoAlias = MayAlias = MustAlias = 0; + bool doInitialization(Module &M) override { + NoAlias = MayAlias = PartialAlias = MustAlias = 0; NoModRef = Mod = Ref = ModRef = 0; if (PrintAll) { - PrintNoAlias = PrintMayAlias = PrintMustAlias = true; + PrintNoAlias = PrintMayAlias = true; + PrintPartialAlias = PrintMustAlias = true; PrintNoModRef = PrintMod = PrintRef = PrintModRef = true; } return false; } - bool runOnFunction(Function &F); - bool doFinalization(Module &M); + bool runOnFunction(Function &F) override; + bool doFinalization(Module &M) override; }; - - RegisterOpt - X("aa-eval", "Exhaustive Alias Analysis Precision Evaluator"); } +char AAEval::ID = 0; +INITIALIZE_PASS_BEGIN(AAEval, "aa-eval", + "Exhaustive Alias Analysis Precision Evaluator", false, true) +INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_END(AAEval, "aa-eval", + "Exhaustive Alias Analysis Precision Evaluator", false, true) + FunctionPass *llvm::createAAEvalPass() { return new AAEval(); } -static inline void PrintResults(const char *Msg, bool P, Value *V1, Value *V2, - Module *M) { +static void PrintResults(const char *Msg, bool P, const Value *V1, + const Value *V2, const Module *M) { if (P) { - std::cerr << " " << Msg << ":\t"; - WriteAsOperand(std::cerr, V1, true, true, M) << ", "; - WriteAsOperand(std::cerr, V2, true, true, M) << "\n"; + std::string o1, o2; + { + raw_string_ostream os1(o1), os2(o2); + V1->printAsOperand(os1, true, M); + V2->printAsOperand(os2, true, M); + } + + if (o2 < o1) + std::swap(o1, o2); + errs() << " " << Msg << ":\t" + << o1 << ", " + << o2 << "\n"; } } @@ -89,56 +109,91 @@ static inline void PrintModRefResults(const char *Msg, bool P, Instruction *I, Value *Ptr, Module *M) { if (P) { - std::cerr << " " << Msg << ": Ptr: "; - WriteAsOperand(std::cerr, Ptr, true, true, M); - std::cerr << "\t<->" << *I; + errs() << " " << Msg << ": Ptr: "; + Ptr->printAsOperand(errs(), true, M); + errs() << "\t<->" << *I << '\n'; } } +static inline void +PrintModRefResults(const char *Msg, bool P, CallSite CSA, CallSite CSB, + Module *M) { + if (P) { + errs() << " " << Msg << ": " << *CSA.getInstruction() + << " <-> " << *CSB.getInstruction() << '\n'; + } +} + +static inline void +PrintLoadStoreResults(const char *Msg, bool P, const Value *V1, + const Value *V2, const Module *M) { + if (P) { + errs() << " " << Msg << ": " << *V1 + << " <-> " << *V2 << '\n'; + } +} + +static inline bool isInterestingPointer(Value *V) { + return V->getType()->isPointerTy() + && !isa(V); +} + bool AAEval::runOnFunction(Function &F) { AliasAnalysis &AA = getAnalysis(); - const TargetData &TD = AA.getTargetData(); - - std::set Pointers; - std::set CallSites; + SetVector Pointers; + SetVector CallSites; + SetVector Loads; + SetVector Stores; for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) - if (isa(I->getType())) // Add all pointer arguments + if (I->getType()->isPointerTy()) // Add all pointer arguments. Pointers.insert(I); for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { - if (isa(I->getType())) // Add all pointer instructions + if (I->getType()->isPointerTy()) // Add all pointer instructions. Pointers.insert(&*I); + if (EvalAAMD && isa(&*I)) + Loads.insert(&*I); + if (EvalAAMD && isa(&*I)) + Stores.insert(&*I); Instruction &Inst = *I; - User::op_iterator OI = Inst.op_begin(); - if ((isa(Inst) || isa(Inst)) && - isa(Inst.getOperand(0))) - ++OI; // Skip actual functions for direct function calls. - for (; OI != Inst.op_end(); ++OI) - if (isa((*OI)->getType()) && !isa(*OI)) - Pointers.insert(*OI); - - CallSite CS = CallSite::get(&*I); - if (CS.getInstruction()) CallSites.insert(CS); + if (CallSite CS = cast(&Inst)) { + Value *Callee = CS.getCalledValue(); + // Skip actual functions for direct function calls. + if (!isa(Callee) && isInterestingPointer(Callee)) + Pointers.insert(Callee); + // Consider formals. + for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); + AI != AE; ++AI) + if (isInterestingPointer(*AI)) + Pointers.insert(*AI); + CallSites.insert(CS); + } else { + // Consider all operands. + for (Instruction::op_iterator OI = Inst.op_begin(), OE = Inst.op_end(); + OI != OE; ++OI) + if (isInterestingPointer(*OI)) + Pointers.insert(*OI); + } } - if (PrintNoAlias || PrintMayAlias || PrintMustAlias || + if (PrintNoAlias || PrintMayAlias || PrintPartialAlias || PrintMustAlias || PrintNoModRef || PrintMod || PrintRef || PrintModRef) - std::cerr << "Function: " << F.getName() << ": " << Pointers.size() - << " pointers, " << CallSites.size() << " call sites\n"; + errs() << "Function: " << F.getName() << ": " << Pointers.size() + << " pointers, " << CallSites.size() << " call sites\n"; // iterate over the worklist, and run the full (n^2)/2 disambiguations - for (std::set::iterator I1 = Pointers.begin(), E = Pointers.end(); + for (SetVector::iterator I1 = Pointers.begin(), E = Pointers.end(); I1 != E; ++I1) { - unsigned I1Size = 0; - const Type *I1ElTy = cast((*I1)->getType())->getElementType(); - if (I1ElTy->isSized()) I1Size = TD.getTypeSize(I1ElTy); + uint64_t I1Size = AliasAnalysis::UnknownSize; + Type *I1ElTy = cast((*I1)->getType())->getElementType(); + if (I1ElTy->isSized()) I1Size = AA.getTypeStoreSize(I1ElTy); - for (std::set::iterator I2 = Pointers.begin(); I2 != I1; ++I2) { - unsigned I2Size = 0; - const Type *I2ElTy =cast((*I2)->getType())->getElementType(); - if (I2ElTy->isSized()) I2Size = TD.getTypeSize(I2ElTy); + for (SetVector::iterator I2 = Pointers.begin(); I2 != I1; ++I2) { + uint64_t I2Size = AliasAnalysis::UnknownSize; + Type *I2ElTy =cast((*I2)->getType())->getElementType(); + if (I2ElTy->isSized()) I2Size = AA.getTypeStoreSize(I2ElTy); switch (AA.alias(*I1, I1Size, *I2, I2Size)) { case AliasAnalysis::NoAlias: @@ -147,41 +202,119 @@ bool AAEval::runOnFunction(Function &F) { case AliasAnalysis::MayAlias: PrintResults("MayAlias", PrintMayAlias, *I1, *I2, F.getParent()); ++MayAlias; break; + case AliasAnalysis::PartialAlias: + PrintResults("PartialAlias", PrintPartialAlias, *I1, *I2, + F.getParent()); + ++PartialAlias; break; case AliasAnalysis::MustAlias: PrintResults("MustAlias", PrintMustAlias, *I1, *I2, F.getParent()); ++MustAlias; break; - default: - std::cerr << "Unknown alias query result!\n"; + } + } + } + + if (EvalAAMD) { + // iterate over all pairs of load, store + for (SetVector::iterator I1 = Loads.begin(), E = Loads.end(); + I1 != E; ++I1) { + for (SetVector::iterator I2 = Stores.begin(), E2 = Stores.end(); + I2 != E2; ++I2) { + switch (AA.alias(AA.getLocation(cast(*I1)), + AA.getLocation(cast(*I2)))) { + case AliasAnalysis::NoAlias: + PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2, + F.getParent()); + ++NoAlias; break; + case AliasAnalysis::MayAlias: + PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2, + F.getParent()); + ++MayAlias; break; + case AliasAnalysis::PartialAlias: + PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2, + F.getParent()); + ++PartialAlias; break; + case AliasAnalysis::MustAlias: + PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2, + F.getParent()); + ++MustAlias; break; + } + } + } + + // iterate over all pairs of store, store + for (SetVector::iterator I1 = Stores.begin(), E = Stores.end(); + I1 != E; ++I1) { + for (SetVector::iterator I2 = Stores.begin(); I2 != I1; ++I2) { + switch (AA.alias(AA.getLocation(cast(*I1)), + AA.getLocation(cast(*I2)))) { + case AliasAnalysis::NoAlias: + PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2, + F.getParent()); + ++NoAlias; break; + case AliasAnalysis::MayAlias: + PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2, + F.getParent()); + ++MayAlias; break; + case AliasAnalysis::PartialAlias: + PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2, + F.getParent()); + ++PartialAlias; break; + case AliasAnalysis::MustAlias: + PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2, + F.getParent()); + ++MustAlias; break; + } } } } // Mod/ref alias analysis: compare all pairs of calls and values - for (std::set::iterator C = CallSites.begin(), + for (SetVector::iterator C = CallSites.begin(), Ce = CallSites.end(); C != Ce; ++C) { Instruction *I = C->getInstruction(); - for (std::set::iterator V = Pointers.begin(), Ve = Pointers.end(); + for (SetVector::iterator V = Pointers.begin(), Ve = Pointers.end(); V != Ve; ++V) { - unsigned Size = 0; - const Type *ElTy = cast((*V)->getType())->getElementType(); - if (ElTy->isSized()) Size = TD.getTypeSize(ElTy); + uint64_t Size = AliasAnalysis::UnknownSize; + Type *ElTy = cast((*V)->getType())->getElementType(); + if (ElTy->isSized()) Size = AA.getTypeStoreSize(ElTy); switch (AA.getModRefInfo(*C, *V, Size)) { case AliasAnalysis::NoModRef: PrintModRefResults("NoModRef", PrintNoModRef, I, *V, F.getParent()); ++NoModRef; break; case AliasAnalysis::Mod: - PrintModRefResults(" Mod", PrintMod, I, *V, F.getParent()); + PrintModRefResults("Just Mod", PrintMod, I, *V, F.getParent()); + ++Mod; break; + case AliasAnalysis::Ref: + PrintModRefResults("Just Ref", PrintRef, I, *V, F.getParent()); + ++Ref; break; + case AliasAnalysis::ModRef: + PrintModRefResults("Both ModRef", PrintModRef, I, *V, F.getParent()); + ++ModRef; break; + } + } + } + + // Mod/ref alias analysis: compare all pairs of calls + for (SetVector::iterator C = CallSites.begin(), + Ce = CallSites.end(); C != Ce; ++C) { + for (SetVector::iterator D = CallSites.begin(); D != Ce; ++D) { + if (D == C) + continue; + switch (AA.getModRefInfo(*C, *D)) { + case AliasAnalysis::NoModRef: + PrintModRefResults("NoModRef", PrintNoModRef, *C, *D, F.getParent()); + ++NoModRef; break; + case AliasAnalysis::Mod: + PrintModRefResults("Just Mod", PrintMod, *C, *D, F.getParent()); ++Mod; break; case AliasAnalysis::Ref: - PrintModRefResults(" Ref", PrintRef, I, *V, F.getParent()); + PrintModRefResults("Just Ref", PrintRef, *C, *D, F.getParent()); ++Ref; break; case AliasAnalysis::ModRef: - PrintModRefResults(" ModRef", PrintModRef, I, *V, F.getParent()); + PrintModRefResults("Both ModRef", PrintModRef, *C, *D, F.getParent()); ++ModRef; break; - default: - std::cerr << "Unknown alias query result!\n"; } } } @@ -190,45 +323,48 @@ bool AAEval::runOnFunction(Function &F) { } static void PrintPercent(unsigned Num, unsigned Sum) { - std::cerr << "(" << Num*100ULL/Sum << "." - << ((Num*1000ULL/Sum) % 10) << "%)\n"; + errs() << "(" << Num*100ULL/Sum << "." + << ((Num*1000ULL/Sum) % 10) << "%)\n"; } bool AAEval::doFinalization(Module &M) { - unsigned AliasSum = NoAlias + MayAlias + MustAlias; - std::cerr << "===== Alias Analysis Evaluator Report =====\n"; + unsigned AliasSum = NoAlias + MayAlias + PartialAlias + MustAlias; + errs() << "===== Alias Analysis Evaluator Report =====\n"; if (AliasSum == 0) { - std::cerr << " Alias Analysis Evaluator Summary: No pointers!\n"; + errs() << " Alias Analysis Evaluator Summary: No pointers!\n"; } else { - std::cerr << " " << AliasSum << " Total Alias Queries Performed\n"; - std::cerr << " " << NoAlias << " no alias responses "; + errs() << " " << AliasSum << " Total Alias Queries Performed\n"; + errs() << " " << NoAlias << " no alias responses "; PrintPercent(NoAlias, AliasSum); - std::cerr << " " << MayAlias << " may alias responses "; + errs() << " " << MayAlias << " may alias responses "; PrintPercent(MayAlias, AliasSum); - std::cerr << " " << MustAlias << " must alias responses "; + errs() << " " << PartialAlias << " partial alias responses "; + PrintPercent(PartialAlias, AliasSum); + errs() << " " << MustAlias << " must alias responses "; PrintPercent(MustAlias, AliasSum); - std::cerr << " Alias Analysis Evaluator Pointer Alias Summary: " - << NoAlias*100/AliasSum << "%/" << MayAlias*100/AliasSum << "%/" - << MustAlias*100/AliasSum << "%\n"; + errs() << " Alias Analysis Evaluator Pointer Alias Summary: " + << NoAlias*100/AliasSum << "%/" << MayAlias*100/AliasSum << "%/" + << PartialAlias*100/AliasSum << "%/" + << MustAlias*100/AliasSum << "%\n"; } // Display the summary for mod/ref analysis unsigned ModRefSum = NoModRef + Mod + Ref + ModRef; if (ModRefSum == 0) { - std::cerr << " Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!\n"; + errs() << " Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!\n"; } else { - std::cerr << " " << ModRefSum << " Total ModRef Queries Performed\n"; - std::cerr << " " << NoModRef << " no mod/ref responses "; + errs() << " " << ModRefSum << " Total ModRef Queries Performed\n"; + errs() << " " << NoModRef << " no mod/ref responses "; PrintPercent(NoModRef, ModRefSum); - std::cerr << " " << Mod << " mod responses "; + errs() << " " << Mod << " mod responses "; PrintPercent(Mod, ModRefSum); - std::cerr << " " << Ref << " ref responses "; + errs() << " " << Ref << " ref responses "; PrintPercent(Ref, ModRefSum); - std::cerr << " " << ModRef << " mod & ref responses "; + errs() << " " << ModRef << " mod & ref responses "; PrintPercent(ModRef, ModRefSum); - std::cerr << " Alias Analysis Evaluator Mod/Ref Summary: " - << NoModRef*100/ModRefSum << "%/" << Mod*100/ModRefSum << "%/" - << Ref*100/ModRefSum << "%/" << ModRef*100/ModRefSum << "%\n"; + errs() << " Alias Analysis Evaluator Mod/Ref Summary: " + << NoModRef*100/ModRefSum << "%/" << Mod*100/ModRefSum << "%/" + << Ref*100/ModRefSum << "%/" << ModRef*100/ModRefSum << "%\n"; } return false;