170e332d34b795f1645953c35747e345f88b8688bChris Lattner//===- AliasAnalysisCounter.cpp - Alias Analysis Query Counter ------------===// 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//===----------------------------------------------------------------------===// 970e332d34b795f1645953c35747e345f88b8688bChris Lattner// 1070e332d34b795f1645953c35747e345f88b8688bChris Lattner// This file implements a pass which can be used to count how many alias queries 1170e332d34b795f1645953c35747e345f88b8688bChris Lattner// are being made and how the alias analysis implementation being used responds. 1270e332d34b795f1645953c35747e345f88b8688bChris Lattner// 1370e332d34b795f1645953c35747e345f88b8688bChris Lattner//===----------------------------------------------------------------------===// 1470e332d34b795f1645953c35747e345f88b8688bChris Lattner 15534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen#include "llvm/Analysis/Passes.h" 16cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner#include "llvm/Analysis/AliasAnalysis.h" 17cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner#include "llvm/Assembly/Writer.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 19cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner#include "llvm/Support/CommandLine.h" 2020638dc948b0d81d6c9bf70dde0137d7d43b02ddDavid Greene#include "llvm/Support/Debug.h" 21c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 22bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/raw_ostream.h" 23381bf79ae17a77fedb902b87aea7e55be9b793aaChris Lattnerusing namespace llvm; 24d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 25844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> 260819cfb1e6333cc8554e567ae0c885c11821eec6Chris LattnerPrintAll("count-aa-print-all-queries", cl::ReallyHidden, cl::init(true)); 27844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> 28844731a7f1909f55935e3514c9e713a62d67662eDan GohmanPrintAllFailures("count-aa-print-all-failed-queries", cl::ReallyHidden); 29cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner 30844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 316726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class AliasAnalysisCounter : public ModulePass, public AliasAnalysis { 3291d747569a87ed412622857521f0952d778f67fcDan Gohman unsigned No, May, Partial, Must; 33d80651df46b397fba19a89bf9e074dffaacbfa8bChris Lattner unsigned NoMR, JustRef, JustMod, MR; 34cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner Module *M; 35a89feb55e04fd4f25d7c09fb0c119fc9250b5b5aChris Lattner public: 361997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Class identification, replacement for typeinfo 3790c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson AliasAnalysisCounter() : ModulePass(ID) { 38081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeAliasAnalysisCounterPass(*PassRegistry::getPassRegistry()); 3991d747569a87ed412622857521f0952d778f67fcDan Gohman No = May = Partial = Must = 0; 40d80651df46b397fba19a89bf9e074dffaacbfa8bChris Lattner NoMR = JustRef = JustMod = MR = 0; 41d80651df46b397fba19a89bf9e074dffaacbfa8bChris Lattner } 42d80651df46b397fba19a89bf9e074dffaacbfa8bChris Lattner 43d80651df46b397fba19a89bf9e074dffaacbfa8bChris Lattner void printLine(const char *Desc, unsigned Val, unsigned Sum) { 444850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << Val << " " << Desc << " responses (" 45791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner << Val*100/Sum << "%)\n"; 46d80651df46b397fba19a89bf9e074dffaacbfa8bChris Lattner } 47a89feb55e04fd4f25d7c09fb0c119fc9250b5b5aChris Lattner ~AliasAnalysisCounter() { 4891d747569a87ed412622857521f0952d778f67fcDan Gohman unsigned AASum = No+May+Partial+Must; 49d80651df46b397fba19a89bf9e074dffaacbfa8bChris Lattner unsigned MRSum = NoMR+JustRef+JustMod+MR; 50d80651df46b397fba19a89bf9e074dffaacbfa8bChris Lattner if (AASum + MRSum) { // Print a report if any counted queries occurred... 514850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << "\n===== Alias Analysis Counter Report =====\n" 52c5e5b3c830db331974ddae3d8fb98e678b3a7152Chris Lattner << " Analysis counted:\n" 53791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner << " " << AASum << " Total Alias Queries Performed\n"; 54efa095e41830bdbbc4eb0c4ff423fe483f2de0e2Chris Lattner if (AASum) { 55efa095e41830bdbbc4eb0c4ff423fe483f2de0e2Chris Lattner printLine("no alias", No, AASum); 56efa095e41830bdbbc4eb0c4ff423fe483f2de0e2Chris Lattner printLine("may alias", May, AASum); 5791d747569a87ed412622857521f0952d778f67fcDan Gohman printLine("partial alias", Partial, AASum); 58efa095e41830bdbbc4eb0c4ff423fe483f2de0e2Chris Lattner printLine("must alias", Must, AASum); 594850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " Alias Analysis Counter Summary: " << No*100/AASum << "%/" 6091d747569a87ed412622857521f0952d778f67fcDan Gohman << May*100/AASum << "%/" 6191d747569a87ed412622857521f0952d778f67fcDan Gohman << Partial*100/AASum << "%/" 6291d747569a87ed412622857521f0952d778f67fcDan Gohman << Must*100/AASum<<"%\n\n"; 63efa095e41830bdbbc4eb0c4ff423fe483f2de0e2Chris Lattner } 64d80651df46b397fba19a89bf9e074dffaacbfa8bChris Lattner 654850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " " << MRSum << " Total Mod/Ref Queries Performed\n"; 66efa095e41830bdbbc4eb0c4ff423fe483f2de0e2Chris Lattner if (MRSum) { 67efa095e41830bdbbc4eb0c4ff423fe483f2de0e2Chris Lattner printLine("no mod/ref", NoMR, MRSum); 68efa095e41830bdbbc4eb0c4ff423fe483f2de0e2Chris Lattner printLine("ref", JustRef, MRSum); 69efa095e41830bdbbc4eb0c4ff423fe483f2de0e2Chris Lattner printLine("mod", JustMod, MRSum); 70efa095e41830bdbbc4eb0c4ff423fe483f2de0e2Chris Lattner printLine("mod/ref", MR, MRSum); 714850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << " Mod/Ref Analysis Counter Summary: " <<NoMR*100/MRSum 72791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner << "%/" << JustRef*100/MRSum << "%/" << JustMod*100/MRSum 73791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner << "%/" << MR*100/MRSum <<"%\n\n"; 74efa095e41830bdbbc4eb0c4ff423fe483f2de0e2Chris Lattner } 75a89feb55e04fd4f25d7c09fb0c119fc9250b5b5aChris Lattner } 76a89feb55e04fd4f25d7c09fb0c119fc9250b5b5aChris Lattner } 77a89feb55e04fd4f25d7c09fb0c119fc9250b5b5aChris Lattner 78b12914bfc0f76a7a48357162d5f4c39a1343e69bChris Lattner bool runOnModule(Module &M) { 79cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner this->M = &M; 80d80651df46b397fba19a89bf9e074dffaacbfa8bChris Lattner InitializeAliasAnalysis(this); 81a89feb55e04fd4f25d7c09fb0c119fc9250b5b5aChris Lattner return false; 82a89feb55e04fd4f25d7c09fb0c119fc9250b5b5aChris Lattner } 8370e332d34b795f1645953c35747e345f88b8688bChris Lattner 8470e332d34b795f1645953c35747e345f88b8688bChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 85d80651df46b397fba19a89bf9e074dffaacbfa8bChris Lattner AliasAnalysis::getAnalysisUsage(AU); 8670e332d34b795f1645953c35747e345f88b8688bChris Lattner AU.addRequired<AliasAnalysis>(); 8770e332d34b795f1645953c35747e345f88b8688bChris Lattner AU.setPreservesAll(); 8870e332d34b795f1645953c35747e345f88b8688bChris Lattner } 8970e332d34b795f1645953c35747e345f88b8688bChris Lattner 901bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// getAdjustedAnalysisPointer - This method is used when a pass implements 911bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// an analysis interface through multiple inheritance. If needed, it 921bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// should override this to adjust the this pointer as needed for the 931bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// specified pass info. 9490c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { 9590c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (PI == &AliasAnalysis::ID) 961bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner return (AliasAnalysis*)this; 971bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner return this; 981bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner } 991bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner 100b79d79297d7115e89776155c92eeb5e7ba518a01Chris Lattner // FIXME: We could count these too... 101a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman bool pointsToConstantMemory(const Location &Loc, bool OrLocal) { 102a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return getAnalysis<AliasAnalysis>().pointsToConstantMemory(Loc, OrLocal); 103b79d79297d7115e89776155c92eeb5e7ba518a01Chris Lattner } 1042b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 10570e332d34b795f1645953c35747e345f88b8688bChris Lattner // Forwarding functions: just delegate to a real AA implementation, counting 10670e332d34b795f1645953c35747e345f88b8688bChris Lattner // the number of responses... 107b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman AliasResult alias(const Location &LocA, const Location &LocB); 108cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner 10979fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman ModRefResult getModRefInfo(ImmutableCallSite CS, 110b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc); 11179fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman ModRefResult getModRefInfo(ImmutableCallSite CS1, 11279fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman ImmutableCallSite CS2) { 1134a7ebfa4111305ea22fc753d4f029eed88149662Reid Spencer return AliasAnalysis::getModRefInfo(CS1,CS2); 1144a7ebfa4111305ea22fc753d4f029eed88149662Reid Spencer } 11570e332d34b795f1645953c35747e345f88b8688bChris Lattner }; 11670e332d34b795f1645953c35747e345f88b8688bChris Lattner} 117534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen 118844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar AliasAnalysisCounter::ID = 0; 119d8cc7be0262092882d848a1c7d8a4cb6752cce6fOwen AndersonINITIALIZE_AG_PASS(AliasAnalysisCounter, AliasAnalysis, "count-aa", 120ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Count Alias Analysis Query Responses", false, true, false) 121844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 122534927d82de6d1be0f6e939263eeb309ad135661Jeff CohenModulePass *llvm::createAliasAnalysisCounterPass() { 123534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen return new AliasAnalysisCounter(); 124534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen} 125cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner 1262b37d7cf28b1382420b5e4007042feeb66d21ac8Misha BrukmanAliasAnalysis::AliasResult 127b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysisCounter::alias(const Location &LocA, const Location &LocB) { 128b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman AliasResult R = getAnalysis<AliasAnalysis>().alias(LocA, LocB); 1292b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 1305b8a1db7ea6510a2589f710d50754599da742de9Duncan Sands const char *AliasString = 0; 131cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner switch (R) { 132cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner case NoAlias: No++; AliasString = "No alias"; break; 133cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner case MayAlias: May++; AliasString = "May alias"; break; 13491d747569a87ed412622857521f0952d778f67fcDan Gohman case PartialAlias: Partial++; AliasString = "Partial alias"; break; 135cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner case MustAlias: Must++; AliasString = "Must alias"; break; 136cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner } 137cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner 138cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner if (PrintAll || (PrintAllFailures && R == MayAlias)) { 1394850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << AliasString << ":\t"; 140b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman errs() << "[" << LocA.Size << "B] "; 141b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman WriteAsOperand(errs(), LocA.Ptr, true, M); 1424850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << ", "; 143b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman errs() << "[" << LocB.Size << "B] "; 144b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman WriteAsOperand(errs(), LocB.Ptr, true, M); 1454850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << "\n"; 146cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner } 147cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner 148cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner return R; 149cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner} 150cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner 1512b37d7cf28b1382420b5e4007042feeb66d21ac8Misha BrukmanAliasAnalysis::ModRefResult 15279fca6fea87be7221843031870bbf2c9ae1fc555Dan GohmanAliasAnalysisCounter::getModRefInfo(ImmutableCallSite CS, 153b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 154b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman ModRefResult R = getAnalysis<AliasAnalysis>().getModRefInfo(CS, Loc); 155cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner 1565b8a1db7ea6510a2589f710d50754599da742de9Duncan Sands const char *MRString = 0; 157cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner switch (R) { 158cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner case NoModRef: NoMR++; MRString = "NoModRef"; break; 159cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner case Ref: JustRef++; MRString = "JustRef"; break; 160cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner case Mod: JustMod++; MRString = "JustMod"; break; 161cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner case ModRef: MR++; MRString = "ModRef"; break; 162cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner } 163cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner 164cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner if (PrintAll || (PrintAllFailures && R == ModRef)) { 1654850a89b77e7dc677c2b73508f2a4c10386c844fDavid Greene errs() << MRString << ": Ptr: "; 166b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman errs() << "[" << Loc.Size << "B] "; 167b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman WriteAsOperand(errs(), Loc.Ptr, true, M); 16852fd7da29594af15650f99de2bb7e2f2872d1619Dan Gohman errs() << "\t<->" << *CS.getInstruction() << '\n'; 169cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner } 170cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner return R; 171cf9f20189f55d4036df598c88371e13512b075b2Chris Lattner} 172