MemoryDependenceAnalysis.h revision 956033a4f5de491fcc07bc3ef0700ad22fd836a0
178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson//===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps --*- C++ -*-===// 278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// The LLVM Compiler Infrastructure 478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson//===----------------------------------------------------------------------===// 978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 10e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner// This file defines the MemoryDependenceAnalysis analysis pass. 1178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 1278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson//===----------------------------------------------------------------------===// 1378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 1478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H 1578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H 1678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 1778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#include "llvm/Pass.h" 1878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#include "llvm/ADT/DenseMap.h" 194beedbd0063a8ba6f97db02c3c94707d8ab45b50Owen Anderson#include "llvm/ADT/SmallPtrSet.h" 2078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 2178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Andersonnamespace llvm { 22e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner class Function; 23e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner class FunctionPass; 24e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner class Instruction; 25b390b1728e6c36f1f28d75d6f8f27cb91f8a8c56Chris Lattner class CallSite; 2678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 27e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner /// MemoryDependenceAnalysis - This is an analysis that determines, for a 28e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner /// given memory operation, what preceding memory operations it depends on. 29e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner /// It builds on alias analysis information, and tries to provide a lazy, 30e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner /// caching interface to a common kind of alias information query. 31e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner class MemoryDependenceAnalysis : public FunctionPass { 3278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson private: 33179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson // A map from instructions to their dependency, with a boolean 34956033a4f5de491fcc07bc3ef0700ad22fd836a0Chris Lattner // flags for whether this mapping is confirmed or not. 35b390b1728e6c36f1f28d75d6f8f27cb91f8a8c56Chris Lattner typedef DenseMap<Instruction*, std::pair<Instruction*, bool> > depMapType; 36df464195fe049d5ea921e2e37f4f833c2ea4e3ecDavid Greene depMapType depGraphLocal; 37df464195fe049d5ea921e2e37f4f833c2ea4e3ecDavid Greene 384d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson // A map from instructions to their non-local dependencies. 39956033a4f5de491fcc07bc3ef0700ad22fd836a0Chris Lattner typedef DenseMap<Instruction*, 40956033a4f5de491fcc07bc3ef0700ad22fd836a0Chris Lattner DenseMap<BasicBlock*, Value*> > nonLocalDepMapType; 414d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson nonLocalDepMapType depGraphNonLocal; 424d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson 43956033a4f5de491fcc07bc3ef0700ad22fd836a0Chris Lattner // A reverse mapping from dependencies to the dependees. This is 44179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson // used when removing instructions to keep the cache coherent. 45b390b1728e6c36f1f28d75d6f8f27cb91f8a8c56Chris Lattner typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > reverseDepMapType; 46df464195fe049d5ea921e2e37f4f833c2ea4e3ecDavid Greene reverseDepMapType reverseDep; 4778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 484d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson // A reverse mapping form dependencies to the non-local dependees. 494d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson reverseDepMapType reverseDepNonLocal; 504d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson 51179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson public: 52179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson // Special marker indicating that the query has no dependency 53179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson // in the specified block. 549528f11481e6840a10442733f1dc45c04b79d596Owen Anderson static Instruction* const NonLocal; 55179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson 56179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson // Special marker indicating that the query has no dependency at all 579528f11481e6840a10442733f1dc45c04b79d596Owen Anderson static Instruction* const None; 5878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 59742f9b66822cb03af0cf7b94436e9d0288565591Owen Anderson // Special marker indicating a dirty cache entry 60742f9b66822cb03af0cf7b94436e9d0288565591Owen Anderson static Instruction* const Dirty; 61742f9b66822cb03af0cf7b94436e9d0288565591Owen Anderson 6278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson static char ID; // Class identification, replacement for typeinfo 63ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman MemoryDependenceAnalysis() : FunctionPass(&ID) {} 641cee94f04111cfd7114979d6dfddce2669c9380dDevang Patel 6578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// Pass Implementation stuff. This doesn't do any analysis. 6678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// 676b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Anderson bool runOnFunction(Function &) {return false; } 686b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Anderson 696b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Anderson /// Clean up memory in between runs 706b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Anderson void releaseMemory() { 7178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson depGraphLocal.clear(); 724d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson depGraphNonLocal.clear(); 7378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson reverseDep.clear(); 744d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson reverseDepNonLocal.clear(); 7578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson } 7678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 7778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// getAnalysisUsage - Does not modify anything. It uses Value Numbering 7878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// and Alias Analysis. 7978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// 8078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const; 8178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 8278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// getDependency - Return the instruction on which a memory operation 83faac518ce0ae88a19f26b9aa9d34f6bf86ecb8c4Owen Anderson /// depends, starting with start. 849528f11481e6840a10442733f1dc45c04b79d596Owen Anderson Instruction* getDependency(Instruction* query, Instruction* start = 0, 854beedbd0063a8ba6f97db02c3c94707d8ab45b50Owen Anderson BasicBlock* block = 0); 864beedbd0063a8ba6f97db02c3c94707d8ab45b50Owen Anderson 8749609a5ddfe8a318eb155a9ccaf0464cd54aa3c7Owen Anderson /// getNonLocalDependency - Fills the passed-in map with the non-local 8849609a5ddfe8a318eb155a9ccaf0464cd54aa3c7Owen Anderson /// dependencies of the queries. The map will contain NonLocal for 8949609a5ddfe8a318eb155a9ccaf0464cd54aa3c7Owen Anderson /// blocks between the query and its dependencies. 909066020993695a690c1f979f9cac4e14d325e237Owen Anderson void getNonLocalDependency(Instruction* query, 910cd320362e91852c8f7f2c8c4841498aab7f92faOwen Anderson DenseMap<BasicBlock*, Value*>& resp); 9278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 9378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// removeInstruction - Remove an instruction from the dependence analysis, 9478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// updating the dependence of instructions that previously depended on it. 9578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson void removeInstruction(Instruction* rem); 96179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson 9730b4bd4d1099764db4f1e1a955b7f7cc9dafdd97Owen Anderson /// dropInstruction - Remove an instruction from the analysis, making 9830b4bd4d1099764db4f1e1a955b7f7cc9dafdd97Owen Anderson /// absolutely conservative assumptions when updating the cache. This is 9930b4bd4d1099764db4f1e1a955b7f7cc9dafdd97Owen Anderson /// useful, for example when an instruction is changed rather than removed. 10030b4bd4d1099764db4f1e1a955b7f7cc9dafdd97Owen Anderson void dropInstruction(Instruction* drop); 10130b4bd4d1099764db4f1e1a955b7f7cc9dafdd97Owen Anderson 102179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson private: 1038b589fa135d873e683b29ed0918638a79272f5d2Chris Lattner /// verifyRemoved - Verify that the specified instruction does not occur 1048b589fa135d873e683b29ed0918638a79272f5d2Chris Lattner /// in our internal data structures. 1058b589fa135d873e683b29ed0918638a79272f5d2Chris Lattner void verifyRemoved(Instruction *Inst) const; 1068b589fa135d873e683b29ed0918638a79272f5d2Chris Lattner 1079528f11481e6840a10442733f1dc45c04b79d596Owen Anderson Instruction* getCallSiteDependency(CallSite C, Instruction* start, 108179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson BasicBlock* block); 109179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson void nonLocalHelper(Instruction* query, BasicBlock* block, 110179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson DenseMap<BasicBlock*, Value*>& resp); 11178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson }; 11278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 11378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson} // End llvm namespace 11478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 11578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#endif 116