lib/Analysis/IPA/DependenceGraph.cpp

   1 //===- DependenceGraph.cpp - Dependence graph for a function ----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements an explicit representation for the dependence graph
  11 // of a function, with one node per instruction and one edge per dependence.
  12 // Dependences include both data and control dependences.
  13 //
  14 // Each dep. graph node (class DepGraphNode) keeps lists of incoming and
  15 // outgoing dependence edges.
  16 //
  17 // Each dep. graph edge (class Dependence) keeps a pointer to one end-point
  18 // of the dependence.  This saves space and is important because dep. graphs
  19 // can grow quickly.  It works just fine because the standard idiom is to
  20 // start with a known node and enumerate the dependences to or from that node.
  21 //===----------------------------------------------------------------------===//
  22
  23
  24 #include "llvm/Analysis/DependenceGraph.h"
  25 #include "llvm/Function.h"
  26
  27 namespace llvm {
  28
  29 //----------------------------------------------------------------------------
  30 // class Dependence:
  31 //
  32 // A representation of a simple (non-loop-related) dependence
  33 //----------------------------------------------------------------------------
  34
  35 void Dependence::print(std::ostream &O) const
  36 {
  37   assert(depType != NoDependence && "This dependence should never be created!");
  38   switch (depType) {
  39   case TrueDependence:    O << "TRUE dependence"; break;
  40   case AntiDependence:    O << "ANTI dependence"; break;
  41   case OutputDependence:  O << "OUTPUT dependence"; break;
  42   case ControlDependence: O << "CONTROL dependence"; break;
  43   default: assert(0 && "Invalid dependence type"); break;
  44   }
  45 }
  46
  47
  48 //----------------------------------------------------------------------------
  49 // class DepGraphNode
  50 //----------------------------------------------------------------------------
  51
  52 void DepGraphNode::print(std::ostream &O) const
  53 {
  54   const_iterator DI = outDepBegin(), DE = outDepEnd();
  55
  56   O << "\nDeps. from instr:" << getInstr();
  57
  58   for ( ; DI != DE; ++DI)
  59     {
  60       O << "\t";
  61       DI->print(O);
  62       O << " to instruction:";
  63       O << DI->getSink()->getInstr();
  64     }
  65 }
  66
  67 //----------------------------------------------------------------------------
  68 // class DependenceGraph
  69 //----------------------------------------------------------------------------
  70
  71 DependenceGraph::~DependenceGraph()
  72 {
  73   // Free all DepGraphNode objects created for this graph
  74   for (map_iterator I = depNodeMap.begin(), E = depNodeMap.end(); I != E; ++I)
  75     delete I->second;
  76 }
  77
  78 void DependenceGraph::print(const Function& func, std::ostream &O) const
  79 {
  80   O << "DEPENDENCE GRAPH FOR FUNCTION " << func.getName() << ":\n";
  81   for (Function::const_iterator BB=func.begin(), FE=func.end(); BB != FE; ++BB)
  82     for (BasicBlock::const_iterator II=BB->begin(), IE=BB->end(); II !=IE; ++II)
  83       if (const DepGraphNode* dgNode = this->getNode(*II))
  84         dgNode->print(O);
  85 }
  86
  87 } // End llvm namespace