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" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/AliasAnalysis.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DerivedTypes.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 25d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.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 42081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson AliasDebugger() : ModulePass(ID) { 43081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeAliasDebuggerPass(*PassRegistry::getPassRegistry()); 44081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 451cee94f04111cfd7114979d6dfddce2669c9380dDevang Patel 46472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth bool runOnModule(Module &M) { 47472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth InitializeAliasAnalysis(this); // set up super class 48472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 49472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth for(Module::global_iterator I = M.global_begin(), 50dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman E = M.global_end(); I != E; ++I) { 51472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth Vals.insert(&*I); 52dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman for (User::const_op_iterator OI = I->op_begin(), 53dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman OE = I->op_end(); OI != OE; ++OI) 54dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman Vals.insert(*OI); 55dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman } 56472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 57472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth for(Module::iterator I = M.begin(), 58472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth E = M.end(); I != E; ++I){ 59472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth Vals.insert(&*I); 605cbf985dcbc89fba3208e7baf8b6f488b06d3ec9Reid Spencer if(!I->isDeclaration()) { 61472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth for (Function::arg_iterator AI = I->arg_begin(), AE = I->arg_end(); 62472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth AI != AE; ++AI) 63472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth Vals.insert(&*AI); 64472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth for (Function::const_iterator FI = I->begin(), FE = I->end(); 65472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth FI != FE; ++FI) 66472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth for (BasicBlock::const_iterator BI = FI->begin(), BE = FI->end(); 67dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman BI != BE; ++BI) { 68472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth Vals.insert(&*BI); 69dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman for (User::const_op_iterator OI = BI->op_begin(), 70dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman OE = BI->op_end(); OI != OE; ++OI) 71dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman Vals.insert(*OI); 72dd05466ef493d34b68ad0c67b7c05d9fa1123484Dan Gohman } 73472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 74472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 75472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 76472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth return false; 77472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 78472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 79472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth virtual void getAnalysisUsage(AnalysisUsage &AU) const { 80472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth AliasAnalysis::getAnalysisUsage(AU); 81472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth AU.setPreservesAll(); // Does not transform code 82472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 83472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 841bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// getAdjustedAnalysisPointer - This method is used when a pass implements 851bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// an analysis interface through multiple inheritance. If needed, it 861bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// should override this to adjust the this pointer as needed for the 871bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// specified pass info. 8890c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { 8990c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (PI == &AliasAnalysis::ID) 901bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner return (AliasAnalysis*)this; 911bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner return this; 921bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner } 931bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner 94472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth //------------------------------------------------ 95472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth // Implement the AliasAnalysis API 96472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth // 97b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman AliasResult alias(const Location &LocA, const Location &LocB) { 98b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman assert(Vals.find(LocA.Ptr) != Vals.end() && 99b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman "Never seen value in AA before"); 100b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman assert(Vals.find(LocB.Ptr) != Vals.end() && 101b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman "Never seen value in AA before"); 102b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return AliasAnalysis::alias(LocA, LocB); 103472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 104472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 10579fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman ModRefResult getModRefInfo(ImmutableCallSite CS, 106b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 107b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman assert(Vals.find(Loc.Ptr) != Vals.end() && "Never seen value in AA before"); 108b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return AliasAnalysis::getModRefInfo(CS, Loc); 109472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 110472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 11179fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman ModRefResult getModRefInfo(ImmutableCallSite CS1, 11279fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman ImmutableCallSite CS2) { 113472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth return AliasAnalysis::getModRefInfo(CS1,CS2); 114472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 115472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 116a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman bool pointsToConstantMemory(const Location &Loc, bool OrLocal) { 117b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman assert(Vals.find(Loc.Ptr) != Vals.end() && "Never seen value in AA before"); 118a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 119472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 120472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 121472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth virtual void deleteValue(Value *V) { 122472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth assert(Vals.find(V) != Vals.end() && "Never seen value in AA before"); 123472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth AliasAnalysis::deleteValue(V); 124472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 125472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth virtual void copyValue(Value *From, Value *To) { 126472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth Vals.insert(To); 127472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth AliasAnalysis::copyValue(From, To); 128472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth } 129472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 130472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth }; 131472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth} 132472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 133844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar AliasDebugger::ID = 0; 134d8cc7be0262092882d848a1c7d8a4cb6752cce6fOwen AndersonINITIALIZE_AG_PASS(AliasDebugger, AliasAnalysis, "debug-aa", 135ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "AA use debugger", false, true, false) 136844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 137472c7918b0bc155e002db6f682c899e21bff852cAndrew LenharthPass *llvm::createAliasDebugger() { return new AliasDebugger(); } 138472c7918b0bc155e002db6f682c899e21bff852cAndrew Lenharth 139