LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

DependenceGraph.cpp

Go to the documentation of this file.
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