LLVM API Documentation
00001 //===- DependenceGraph.cpp - Dependence graph for a function ----*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements an explicit representation for the dependence graph 00011 // of a function, with one node per instruction and one edge per dependence. 00012 // Dependences include both data and control dependences. 00013 // 00014 // Each dep. graph node (class DepGraphNode) keeps lists of incoming and 00015 // outgoing dependence edges. 00016 // 00017 // Each dep. graph edge (class Dependence) keeps a pointer to one end-point 00018 // of the dependence. This saves space and is important because dep. graphs 00019 // can grow quickly. It works just fine because the standard idiom is to 00020 // start with a known node and enumerate the dependences to or from that node. 00021 //===----------------------------------------------------------------------===// 00022 00023 00024 #include "DependenceGraph.h" 00025 #include "llvm/Function.h" 00026 00027 namespace llvm { 00028 00029 //---------------------------------------------------------------------------- 00030 // class Dependence: 00031 // 00032 // A representation of a simple (non-loop-related) dependence 00033 //---------------------------------------------------------------------------- 00034 00035 void Dependence::print(std::ostream &O) const 00036 { 00037 assert(depType != NoDependence && "This dependence should never be created!"); 00038 switch (depType) { 00039 case TrueDependence: O << "TRUE dependence"; break; 00040 case AntiDependence: O << "ANTI dependence"; break; 00041 case OutputDependence: O << "OUTPUT dependence"; break; 00042 case ControlDependence: O << "CONTROL dependence"; break; 00043 default: assert(0 && "Invalid dependence type"); break; 00044 } 00045 } 00046 00047 00048 //---------------------------------------------------------------------------- 00049 // class DepGraphNode 00050 //---------------------------------------------------------------------------- 00051 00052 void DepGraphNode::print(std::ostream &O) const 00053 { 00054 const_iterator DI = outDepBegin(), DE = outDepEnd(); 00055 00056 O << "\nDeps. from instr:" << getInstr(); 00057 00058 for ( ; DI != DE; ++DI) 00059 { 00060 O << "\t"; 00061 DI->print(O); 00062 O << " to instruction:"; 00063 O << DI->getSink()->getInstr(); 00064 } 00065 } 00066 00067 //---------------------------------------------------------------------------- 00068 // class DependenceGraph 00069 //---------------------------------------------------------------------------- 00070 00071 DependenceGraph::~DependenceGraph() 00072 { 00073 // Free all DepGraphNode objects created for this graph 00074 for (map_iterator I = depNodeMap.begin(), E = depNodeMap.end(); I != E; ++I) 00075 delete I->second; 00076 } 00077 00078 void DependenceGraph::print(const Function& func, std::ostream &O) const 00079 { 00080 O << "DEPENDENCE GRAPH FOR FUNCTION " << func.getName() << ":\n"; 00081 for (Function::const_iterator BB=func.begin(), FE=func.end(); BB != FE; ++BB) 00082 for (BasicBlock::const_iterator II=BB->begin(), IE=BB->end(); II !=IE; ++II) 00083 if (const DepGraphNode* dgNode = this->getNode(*II)) 00084 dgNode->print(O); 00085 } 00086 00087 } // End llvm namespace