MemoryDependenceAnalysis.h revision 6b278fc7860c1e0e5cf72340e43f78a87159be4c
178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson//===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps --*- C++ -*-===// 278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// The LLVM Compiler Infrastructure 478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// This file was developed by the Owen Anderson and is distributed under 678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// the University of Illinois Open Source License. See LICENSE.TXT for details. 778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson//===----------------------------------------------------------------------===// 978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 1078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// This file defines an analysis that determines, for a given memory operation, 1178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// what preceding memory operations it depends on. It builds on alias analysis 1278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// information, and tries to provide a lazy, caching interface to a common kind 1378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// of alias information query. 1478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 1578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson//===----------------------------------------------------------------------===// 1678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 1778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H 1878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H 1978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 2078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#include "llvm/Pass.h" 2178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#include "llvm/ADT/DenseMap.h" 2278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#include "llvm/Support/Compiler.h" 2378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#include <map> 2478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 2578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Andersonnamespace llvm { 2678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 2778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Andersonclass Function; 2878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Andersonclass FunctionPass; 2978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Andersonclass Instruction; 3078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 316b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Andersonclass MemoryDependenceAnalysis : public FunctionPass { 3278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson private: 3378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 3478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson DenseMap<Instruction*, std::pair<Instruction*, bool> > depGraphLocal; 3578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson std::multimap<Instruction*, Instruction*> reverseDep; 3678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 3778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson public: 3878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 3978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson static Instruction* NonLocal; 4078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson static Instruction* None; 4178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 4278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson static char ID; // Class identification, replacement for typeinfo 4378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson MemoryDependenceAnalysis() : FunctionPass((intptr_t)&ID) {} 4478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 4578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// Pass Implementation stuff. This doesn't do any analysis. 4678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// 476b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Anderson bool runOnFunction(Function &) {return false; } 486b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Anderson 496b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Anderson /// Clean up memory in between runs 506b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Anderson void releaseMemory() { 5178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson depGraphLocal.clear(); 5278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson reverseDep.clear(); 5378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson } 5478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 5578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// getAnalysisUsage - Does not modify anything. It uses Value Numbering 5678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// and Alias Analysis. 5778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// 5878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const; 5978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 6078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// getDependency - Return the instruction on which a memory operation 6178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// depends. 6278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson Instruction* getDependency(Instruction* query, bool local = true); 6378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 6478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// removeInstruction - Remove an instruction from the dependence analysis, 6578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// updating the dependence of instructions that previously depended on it. 6678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson void removeInstruction(Instruction* rem); 6778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson }; 6878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 6978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson} // End llvm namespace 7078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 7178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#endif 72