AliasDebugger.cpp revision ce665bd2e2b581ab0858d1afe359192bac96b868
1472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth//===- AliasDebugger.cpp - Simple Alias Analysis Use Checker --------------===// 2472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth// 3472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth// The LLVM Compiler Infrastructure 4472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth// 8472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth//===----------------------------------------------------------------------===// 9472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth// 10472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth// This simple pass checks alias analysis users to ensure that if they 11472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth// create a new value, they do not query AA without informing it of the value. 12472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth// It acts as a shim over any other AA pass you want. 13472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth// 14472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth// Yes keeping track of every value in the program is expensive, but this is 15472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth// a debugging pass. 16472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth// 17472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth//===----------------------------------------------------------------------===// 18472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 19472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth#include "llvm/Analysis/Passes.h" 20472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth#include "llvm/Module.h" 21472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth#include "llvm/Pass.h" 22472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth#include "llvm/Instructions.h" 23472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth#include "llvm/Constants.h" 24472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth#include "llvm/DerivedTypes.h" 25472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth#include "llvm/Analysis/AliasAnalysis.h" 26472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth#include <set> 27472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharthusing namespace llvm; 28472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 29472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharthnamespace { 30472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 316726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class AliasDebugger : public ModulePass, public AliasAnalysis { 32472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 33472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth //What we do is simple. Keep track of every value the AA could 34472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth //know about, and verify that queries are one of those. 35472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth //A query to a value that didn't exist when the AA was created 36472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth //means someone forgot to update the AA when creating new values 37472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 38472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth std::set<const Value*> Vals; 39472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 40472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth public: 411997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Class identification, replacement for typeinfo 4290c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson AliasDebugger() : ModulePass(ID) {} 431cee94f04111cfd7114979d6dfddce2669c9380dDevang Patel 44472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth bool runOnModule(Module &M) { 45472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth InitializeAliasAnalysis(this); // set up super class 46472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 47472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth for(Module::global_iterator I = M.global_begin(), 48dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman E = M.global_end(); I != E; ++I) { 49472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth Vals.insert(&*I); 50dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman for (User::const_op_iterator OI = I->op_begin(), 51dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman OE = I->op_end(); OI != OE; ++OI) 52dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman Vals.insert(*OI); 53dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman } 54472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 55472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth for(Module::iterator I = M.begin(), 56472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth E = M.end(); I != E; ++I){ 57472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth Vals.insert(&*I); 585cbf985dcbc89fba3208e7baf8b6f488b06d3ec9Reid Spencer if(!I->isDeclaration()) { 59472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth for (Function::arg_iterator AI = I->arg_begin(), AE = I->arg_end(); 60472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth AI != AE; ++AI) 61472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth Vals.insert(&*AI); 62472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth for (Function::const_iterator FI = I->begin(), FE = I->end(); 63472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth FI != FE; ++FI) 64472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth for (BasicBlock::const_iterator BI = FI->begin(), BE = FI->end(); 65dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman BI != BE; ++BI) { 66472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth Vals.insert(&*BI); 67dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman for (User::const_op_iterator OI = BI->op_begin(), 68dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman OE = BI->op_end(); OI != OE; ++OI) 69dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman Vals.insert(*OI); 70dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman } 71472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 72472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 73472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 74472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth return false; 75472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 76472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 77472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth virtual void getAnalysisUsage(AnalysisUsage &AU) const { 78472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth AliasAnalysis::getAnalysisUsage(AU); 79472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth AU.setPreservesAll(); // Does not transform code 80472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 81472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 821bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// getAdjustedAnalysisPointer - This method is used when a pass implements 831bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// an analysis interface through multiple inheritance. If needed, it 841bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// should override this to adjust the this pointer as needed for the 851bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// specified pass info. 8690c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { 8790c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (PI == &AliasAnalysis::ID) 881bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner return (AliasAnalysis*)this; 891bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner return this; 901bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner } 911bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner 92472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth //------------------------------------------------ 93472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth // Implement the AliasAnalysis API 94472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth // 95b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman AliasResult alias(const Location &LocA, const Location &LocB) { 96b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman assert(Vals.find(LocA.Ptr) != Vals.end() && 97b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman "Never seen value in AA before"); 98b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman assert(Vals.find(LocB.Ptr) != Vals.end() && 99b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman "Never seen value in AA before"); 100b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return AliasAnalysis::alias(LocA, LocB); 101472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 102472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 10379fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman ModRefResult getModRefInfo(ImmutableCallSite CS, 104b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 105b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman assert(Vals.find(Loc.Ptr) != Vals.end() && "Never seen value in AA before"); 106b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return AliasAnalysis::getModRefInfo(CS, Loc); 107472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 108472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 10979fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman ModRefResult getModRefInfo(ImmutableCallSite CS1, 11079fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman ImmutableCallSite CS2) { 111472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth return AliasAnalysis::getModRefInfo(CS1,CS2); 112472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 113472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 114b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman bool pointsToConstantMemory(const Location &Loc) { 115b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman assert(Vals.find(Loc.Ptr) != Vals.end() && "Never seen value in AA before"); 116b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return AliasAnalysis::pointsToConstantMemory(Loc); 117472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 118472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 119472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth virtual void deleteValue(Value *V) { 120472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth assert(Vals.find(V) != Vals.end() && "Never seen value in AA before"); 121472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth AliasAnalysis::deleteValue(V); 122472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 123472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth virtual void copyValue(Value *From, Value *To) { 124472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth Vals.insert(To); 125472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth AliasAnalysis::copyValue(From, To); 126472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 127472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 128472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth }; 129472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth} 130472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 131844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar AliasDebugger::ID = 0; 132d8cc7be0262092882d848a1c7d8a4cb6752cce6fOwen AndersonINITIALIZE_AG_PASS(AliasDebugger, AliasAnalysis, "debug-aa", 133ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "AA use debugger", false, true, false) 134844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 135472c7918b0bc155e002db6f682c899e21bff852cAndrew LenharthPass *llvm::createAliasDebugger() { return new AliasDebugger(); } 136472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 137