lib/Analysis/IPA/DependenceGraph.cpp

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