19798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner//===- AliasAnalysisEvaluator.cpp - Alias Analysis Accuracy Evaluator -----===// 22b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 72b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 99798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner// 109798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner// This file implements a simple N^2 alias analysis accuracy evaluator. 119798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner// Basically, for each function in the program, it simply queries to see how the 129798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner// alias analysis implementation answers alias queries between each pair of 139798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner// pointers in the function. 149798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner// 159798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner// This is inspired and adapted from code by: Naveen Neelakantam, Francesco 169798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner// Spadini, and Wojciech Stryjewski. 179798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner// 189798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner//===----------------------------------------------------------------------===// 199798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Passes.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SetVector.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/AliasAnalysis.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DerivedTypes.h" 250b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/InstIterator.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 28bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman#include "llvm/Pass.h" 29d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/CommandLine.h" 3044d98a76dc5c41cd6e57b4a5cce73075120ce80aDavid Greene#include "llvm/Support/Debug.h" 31ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 329a4f8ef78757882ceb2edbf90f37439deb112c88Chris Lattnerusing namespace llvm; 33d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 34844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden); 350e872cb4707cbfc260279132e290ed595e47d2cdChris Lattner 36844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden); 37844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden); 383d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohmanstatic cl::opt<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden); 39844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden); 40bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman 41844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden); 42844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden); 43844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden); 44844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden); 45638b381713e32a0a9fb2a83c43b600683116df52Chris Lattner 4637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstatic cl::opt<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden); 47a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren 48844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 499e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman class AAEval : public FunctionPass { 503d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman unsigned NoAlias, MayAlias, PartialAlias, MustAlias; 51bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman unsigned NoModRef, Mod, Ref, ModRef; 529798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner 539e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman public: 549e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman static char ID; // Pass identification, replacement for typeid 55081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson AAEval() : FunctionPass(ID) { 56081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeAAEvalPass(*PassRegistry::getPassRegistry()); 57081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 58794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 609798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner AU.addRequired<AliasAnalysis>(); 619798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner AU.setPreservesAll(); 629798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner } 632b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool doInitialization(Module &M) override { 653d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman NoAlias = MayAlias = PartialAlias = MustAlias = 0; 66bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman NoModRef = Mod = Ref = ModRef = 0; 670e872cb4707cbfc260279132e290ed595e47d2cdChris Lattner 680e872cb4707cbfc260279132e290ed595e47d2cdChris Lattner if (PrintAll) { 693d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman PrintNoAlias = PrintMayAlias = true; 703d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman PrintPartialAlias = PrintMustAlias = true; 710e872cb4707cbfc260279132e290ed595e47d2cdChris Lattner PrintNoModRef = PrintMod = PrintRef = PrintModRef = true; 720e872cb4707cbfc260279132e290ed595e47d2cdChris Lattner } 732b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman return false; 74bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman } 75bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman 7636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 7736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool doFinalization(Module &M) override; 789798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner }; 799798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner} 809798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner 819e86f4364b912ae743490ba01d6989acfd12c046Dan Gohmanchar AAEval::ID = 0; 822ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(AAEval, "aa-eval", 832ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Exhaustive Alias Analysis Precision Evaluator", false, true) 842ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 852ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(AAEval, "aa-eval", 86ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Exhaustive Alias Analysis Precision Evaluator", false, true) 87844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 889e86f4364b912ae743490ba01d6989acfd12c046Dan GohmanFunctionPass *llvm::createAAEvalPass() { return new AAEval(); } 89534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen 90791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattnerstatic void PrintResults(const char *Msg, bool P, const Value *V1, 91791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner const Value *V2, const Module *M) { 92638b381713e32a0a9fb2a83c43b600683116df52Chris Lattner if (P) { 93791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner std::string o1, o2; 94791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner { 95791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner raw_string_ostream os1(o1), os2(o2); 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines V1->printAsOperand(os1, true, M); 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines V2->printAsOperand(os2, true, M); 98791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner } 99791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner 100c0734e3c994b55d054916921ef2d5eb9bc04f28dGabor Greif if (o2 < o1) 101ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar std::swap(o1, o2); 1024850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << Msg << ":\t" 103ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << o1 << ", " 104ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << o2 << "\n"; 105638b381713e32a0a9fb2a83c43b600683116df52Chris Lattner } 106638b381713e32a0a9fb2a83c43b600683116df52Chris Lattner} 107638b381713e32a0a9fb2a83c43b600683116df52Chris Lattner 1082b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukmanstatic inline void 109ad48cc71dcd218216e5e7df6d05c481946a65879Chris LattnerPrintModRefResults(const char *Msg, bool P, Instruction *I, Value *Ptr, 110ad48cc71dcd218216e5e7df6d05c481946a65879Chris Lattner Module *M) { 111ad48cc71dcd218216e5e7df6d05c481946a65879Chris Lattner if (P) { 1124850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << Msg << ": Ptr: "; 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Ptr->printAsOperand(errs(), true, M); 1144850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << "\t<->" << *I << '\n'; 115ad48cc71dcd218216e5e7df6d05c481946a65879Chris Lattner } 116ad48cc71dcd218216e5e7df6d05c481946a65879Chris Lattner} 117ad48cc71dcd218216e5e7df6d05c481946a65879Chris Lattner 1183dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohmanstatic inline void 1193dcc91ee8c48f210d302937ecbbf0d277f8b656eDan GohmanPrintModRefResults(const char *Msg, bool P, CallSite CSA, CallSite CSB, 1203dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman Module *M) { 1213dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman if (P) { 1223dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman errs() << " " << Msg << ": " << *CSA.getInstruction() 1233dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman << " <-> " << *CSB.getInstruction() << '\n'; 1243dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman } 1253dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman} 1263dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman 127a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Renstatic inline void 128a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman RenPrintLoadStoreResults(const char *Msg, bool P, const Value *V1, 129a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren const Value *V2, const Module *M) { 130a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren if (P) { 131a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren errs() << " " << Msg << ": " << *V1 132a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren << " <-> " << *V2 << '\n'; 133a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren } 134a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren} 135a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren 136fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greifstatic inline bool isInterestingPointer(Value *V) { 137fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif return V->getType()->isPointerTy() 138fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif && !isa<ConstantPointerNull>(V); 139fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif} 140fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif 1419e86f4364b912ae743490ba01d6989acfd12c046Dan Gohmanbool AAEval::runOnFunction(Function &F) { 1429e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 1439e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman 1449e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman SetVector<Value *> Pointers; 1459e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman SetVector<CallSite> CallSites; 146a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren SetVector<Value *> Loads; 147a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren SetVector<Value *> Stores; 1489e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman 149e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 150fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif if (I->getType()->isPointerTy()) // Add all pointer arguments. 1511842a90e0bf7b9137fb595828c6e07c5b629b2adChris Lattner Pointers.insert(I); 1529798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner 1531842a90e0bf7b9137fb595828c6e07c5b629b2adChris Lattner for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 154fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif if (I->getType()->isPointerTy()) // Add all pointer instructions. 1556ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner Pointers.insert(&*I); 15637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (EvalAAMD && isa<LoadInst>(&*I)) 157a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren Loads.insert(&*I); 15837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (EvalAAMD && isa<StoreInst>(&*I)) 159a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren Stores.insert(&*I); 160ddc77c458abaa920bb68564cba9e8b04d7b96172Chris Lattner Instruction &Inst = *I; 1612c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar if (auto CS = CallSite(&Inst)) { 162fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif Value *Callee = CS.getCalledValue(); 163fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif // Skip actual functions for direct function calls. 164fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif if (!isa<Function>(Callee) && isInterestingPointer(Callee)) 165fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif Pointers.insert(Callee); 166fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif // Consider formals. 167fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 168fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif AI != AE; ++AI) 169fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif if (isInterestingPointer(*AI)) 170fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif Pointers.insert(*AI); 1715d4b32ef96ef91026517ea1769faa7066467d0a9Gabor Greif CallSites.insert(CS); 172fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif } else { 173fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif // Consider all operands. 174fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif for (Instruction::op_iterator OI = Inst.op_begin(), OE = Inst.op_end(); 175fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif OI != OE; ++OI) 176fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif if (isInterestingPointer(*OI)) 177fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif Pointers.insert(*OI); 178fcf0f082f485e45f591c0d1cbaa9a2ad8691e2c3Gabor Greif } 179bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman } 180bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman 1813d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman if (PrintNoAlias || PrintMayAlias || PrintPartialAlias || PrintMustAlias || 1829e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman PrintNoModRef || PrintMod || PrintRef || PrintModRef) 1839e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman errs() << "Function: " << F.getName() << ": " << Pointers.size() 1849e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman << " pointers, " << CallSites.size() << " call sites\n"; 185638b381713e32a0a9fb2a83c43b600683116df52Chris Lattner 1869798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner // iterate over the worklist, and run the full (n^2)/2 disambiguations 187a8c711cb235bf2705a4dbfbe34b23e6c57451c58Dan Gohman for (SetVector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end(); 1881ed80b66b192ce695431b14eecc5121ef057251bChris Lattner I1 != E; ++I1) { 1893da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman uint64_t I1Size = AliasAnalysis::UnknownSize; 190db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *I1ElTy = cast<PointerType>((*I1)->getType())->getElementType(); 1919e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (I1ElTy->isSized()) I1Size = AA.getTypeStoreSize(I1ElTy); 1921ed80b66b192ce695431b14eecc5121ef057251bChris Lattner 193a8c711cb235bf2705a4dbfbe34b23e6c57451c58Dan Gohman for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) { 1943da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman uint64_t I2Size = AliasAnalysis::UnknownSize; 195db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *I2ElTy =cast<PointerType>((*I2)->getType())->getElementType(); 1969e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (I2ElTy->isSized()) I2Size = AA.getTypeStoreSize(I2ElTy); 1971ed80b66b192ce695431b14eecc5121ef057251bChris Lattner 1989e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman switch (AA.alias(*I1, I1Size, *I2, I2Size)) { 199638b381713e32a0a9fb2a83c43b600683116df52Chris Lattner case AliasAnalysis::NoAlias: 2009e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman PrintResults("NoAlias", PrintNoAlias, *I1, *I2, F.getParent()); 201bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman ++NoAlias; break; 202638b381713e32a0a9fb2a83c43b600683116df52Chris Lattner case AliasAnalysis::MayAlias: 2039e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman PrintResults("MayAlias", PrintMayAlias, *I1, *I2, F.getParent()); 204bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman ++MayAlias; break; 2053d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman case AliasAnalysis::PartialAlias: 2063d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman PrintResults("PartialAlias", PrintPartialAlias, *I1, *I2, 2073d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman F.getParent()); 2083d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman ++PartialAlias; break; 209638b381713e32a0a9fb2a83c43b600683116df52Chris Lattner case AliasAnalysis::MustAlias: 2109e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman PrintResults("MustAlias", PrintMustAlias, *I1, *I2, F.getParent()); 211bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman ++MustAlias; break; 2129798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner } 2131ed80b66b192ce695431b14eecc5121ef057251bChris Lattner } 2141ed80b66b192ce695431b14eecc5121ef057251bChris Lattner } 2159798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner 21637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (EvalAAMD) { 217a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren // iterate over all pairs of load, store 218a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren for (SetVector<Value *>::iterator I1 = Loads.begin(), E = Loads.end(); 219a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren I1 != E; ++I1) { 220a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren for (SetVector<Value *>::iterator I2 = Stores.begin(), E2 = Stores.end(); 221a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren I2 != E2; ++I2) { 222a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren switch (AA.alias(AA.getLocation(cast<LoadInst>(*I1)), 223a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren AA.getLocation(cast<StoreInst>(*I2)))) { 224a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren case AliasAnalysis::NoAlias: 225a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2, 226a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren F.getParent()); 227a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren ++NoAlias; break; 228a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren case AliasAnalysis::MayAlias: 229a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2, 230a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren F.getParent()); 231a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren ++MayAlias; break; 232a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren case AliasAnalysis::PartialAlias: 233a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2, 234a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren F.getParent()); 235a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren ++PartialAlias; break; 236a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren case AliasAnalysis::MustAlias: 237a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2, 238a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren F.getParent()); 239a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren ++MustAlias; break; 240a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren } 241a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren } 242a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren } 243a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren 244a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren // iterate over all pairs of store, store 245a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end(); 246a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren I1 != E; ++I1) { 247a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) { 248a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren switch (AA.alias(AA.getLocation(cast<StoreInst>(*I1)), 249a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren AA.getLocation(cast<StoreInst>(*I2)))) { 250a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren case AliasAnalysis::NoAlias: 251a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2, 252a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren F.getParent()); 253a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren ++NoAlias; break; 254a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren case AliasAnalysis::MayAlias: 255a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2, 256a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren F.getParent()); 257a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren ++MayAlias; break; 258a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren case AliasAnalysis::PartialAlias: 259a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2, 260a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren F.getParent()); 261a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren ++PartialAlias; break; 262a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren case AliasAnalysis::MustAlias: 263a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2, 264a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren F.getParent()); 265a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren ++MustAlias; break; 266a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren } 267a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren } 268a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren } 269a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren } 270a2e3834d1644889484ef3a8a94189b7369e3eaf9Manman Ren 271bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman // Mod/ref alias analysis: compare all pairs of calls and values 272a8c711cb235bf2705a4dbfbe34b23e6c57451c58Dan Gohman for (SetVector<CallSite>::iterator C = CallSites.begin(), 2730772e78789124ca8b747bdc6f9756a5e944bc8f3Chris Lattner Ce = CallSites.end(); C != Ce; ++C) { 2740772e78789124ca8b747bdc6f9756a5e944bc8f3Chris Lattner Instruction *I = C->getInstruction(); 2752b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 276a8c711cb235bf2705a4dbfbe34b23e6c57451c58Dan Gohman for (SetVector<Value *>::iterator V = Pointers.begin(), Ve = Pointers.end(); 2770772e78789124ca8b747bdc6f9756a5e944bc8f3Chris Lattner V != Ve; ++V) { 2783da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman uint64_t Size = AliasAnalysis::UnknownSize; 279db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *ElTy = cast<PointerType>((*V)->getType())->getElementType(); 2809e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (ElTy->isSized()) Size = AA.getTypeStoreSize(ElTy); 2812b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 2829e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman switch (AA.getModRefInfo(*C, *V, Size)) { 2831ed80b66b192ce695431b14eecc5121ef057251bChris Lattner case AliasAnalysis::NoModRef: 2849e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman PrintModRefResults("NoModRef", PrintNoModRef, I, *V, F.getParent()); 2851ed80b66b192ce695431b14eecc5121ef057251bChris Lattner ++NoModRef; break; 2861ed80b66b192ce695431b14eecc5121ef057251bChris Lattner case AliasAnalysis::Mod: 287907857d74630430be024cbb67da960147fa7a1d9Dan Gohman PrintModRefResults("Just Mod", PrintMod, I, *V, F.getParent()); 2881ed80b66b192ce695431b14eecc5121ef057251bChris Lattner ++Mod; break; 2891ed80b66b192ce695431b14eecc5121ef057251bChris Lattner case AliasAnalysis::Ref: 290907857d74630430be024cbb67da960147fa7a1d9Dan Gohman PrintModRefResults("Just Ref", PrintRef, I, *V, F.getParent()); 2911ed80b66b192ce695431b14eecc5121ef057251bChris Lattner ++Ref; break; 2921ed80b66b192ce695431b14eecc5121ef057251bChris Lattner case AliasAnalysis::ModRef: 293907857d74630430be024cbb67da960147fa7a1d9Dan Gohman PrintModRefResults("Both ModRef", PrintModRef, I, *V, F.getParent()); 2941ed80b66b192ce695431b14eecc5121ef057251bChris Lattner ++ModRef; break; 295bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman } 2961ed80b66b192ce695431b14eecc5121ef057251bChris Lattner } 297cb19d679076724a86b62a1821e422ad69ab3d9c5Chris Lattner } 2982b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 2993dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman // Mod/ref alias analysis: compare all pairs of calls 3003dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman for (SetVector<CallSite>::iterator C = CallSites.begin(), 3013dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman Ce = CallSites.end(); C != Ce; ++C) { 3023dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman for (SetVector<CallSite>::iterator D = CallSites.begin(); D != Ce; ++D) { 3033dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman if (D == C) 3043dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman continue; 3053dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman switch (AA.getModRefInfo(*C, *D)) { 3063dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman case AliasAnalysis::NoModRef: 3073dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman PrintModRefResults("NoModRef", PrintNoModRef, *C, *D, F.getParent()); 3083dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman ++NoModRef; break; 3093dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman case AliasAnalysis::Mod: 310907857d74630430be024cbb67da960147fa7a1d9Dan Gohman PrintModRefResults("Just Mod", PrintMod, *C, *D, F.getParent()); 3113dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman ++Mod; break; 3123dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman case AliasAnalysis::Ref: 313907857d74630430be024cbb67da960147fa7a1d9Dan Gohman PrintModRefResults("Just Ref", PrintRef, *C, *D, F.getParent()); 3143dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman ++Ref; break; 3153dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman case AliasAnalysis::ModRef: 316907857d74630430be024cbb67da960147fa7a1d9Dan Gohman PrintModRefResults("Both ModRef", PrintModRef, *C, *D, F.getParent()); 3173dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman ++ModRef; break; 3183dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman } 3193dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman } 3203dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman } 3213dcc91ee8c48f210d302937ecbbf0d277f8b656eDan Gohman 3229e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman return false; 3239798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner} 3249798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner 325e70492d0e298487f9cb8dd37cfcf9c4a060cc21cChris Lattnerstatic void PrintPercent(unsigned Num, unsigned Sum) { 3264850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << "(" << Num*100ULL/Sum << "." 327ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << ((Num*1000ULL/Sum) % 10) << "%)\n"; 328e70492d0e298487f9cb8dd37cfcf9c4a060cc21cChris Lattner} 329e70492d0e298487f9cb8dd37cfcf9c4a060cc21cChris Lattner 3309e86f4364b912ae743490ba01d6989acfd12c046Dan Gohmanbool AAEval::doFinalization(Module &M) { 3313d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman unsigned AliasSum = NoAlias + MayAlias + PartialAlias + MustAlias; 3324850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << "===== Alias Analysis Evaluator Report =====\n"; 333bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman if (AliasSum == 0) { 3344850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " Alias Analysis Evaluator Summary: No pointers!\n"; 3352b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman } else { 3364850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << AliasSum << " Total Alias Queries Performed\n"; 3374850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << NoAlias << " no alias responses "; 338e70492d0e298487f9cb8dd37cfcf9c4a060cc21cChris Lattner PrintPercent(NoAlias, AliasSum); 3394850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << MayAlias << " may alias responses "; 340e70492d0e298487f9cb8dd37cfcf9c4a060cc21cChris Lattner PrintPercent(MayAlias, AliasSum); 3413d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman errs() << " " << PartialAlias << " partial alias responses "; 3423d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman PrintPercent(PartialAlias, AliasSum); 3434850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << MustAlias << " must alias responses "; 344e70492d0e298487f9cb8dd37cfcf9c4a060cc21cChris Lattner PrintPercent(MustAlias, AliasSum); 3454850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " Alias Analysis Evaluator Pointer Alias Summary: " 346ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << NoAlias*100/AliasSum << "%/" << MayAlias*100/AliasSum << "%/" 3473d9f1ca5afd909bfcea243fb27c96013a9134484Dan Gohman << PartialAlias*100/AliasSum << "%/" 348ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << MustAlias*100/AliasSum << "%\n"; 349bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman } 350bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman 351bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman // Display the summary for mod/ref analysis 352bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman unsigned ModRefSum = NoModRef + Mod + Ref + ModRef; 353bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman if (ModRefSum == 0) { 3544850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!\n"; 355bc1dbe95b87a1931f9187597da26a1810250a40aMisha Brukman } else { 3564850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << ModRefSum << " Total ModRef Queries Performed\n"; 3574850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << NoModRef << " no mod/ref responses "; 358e70492d0e298487f9cb8dd37cfcf9c4a060cc21cChris Lattner PrintPercent(NoModRef, ModRefSum); 3594850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << Mod << " mod responses "; 360e70492d0e298487f9cb8dd37cfcf9c4a060cc21cChris Lattner PrintPercent(Mod, ModRefSum); 3614850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << Ref << " ref responses "; 362e70492d0e298487f9cb8dd37cfcf9c4a060cc21cChris Lattner PrintPercent(Ref, ModRefSum); 3634850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << ModRef << " mod & ref responses "; 364e70492d0e298487f9cb8dd37cfcf9c4a060cc21cChris Lattner PrintPercent(ModRef, ModRefSum); 3654850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " Alias Analysis Evaluator Mod/Ref Summary: " 366ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << NoModRef*100/ModRefSum << "%/" << Mod*100/ModRefSum << "%/" 367ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << Ref*100/ModRefSum << "%/" << ModRef*100/ModRefSum << "%\n"; 3682c1d7cf13b3c049c40627416315841ccbe6b123fChris Lattner } 3699e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman 3709e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman return false; 3719798ca55e1c5e07b175dbb7bbae3b50dbffeec94Chris Lattner} 372