1 //===- DependenceGraph.cpp - Dependence graph for a function ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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.
14 // Each dep. graph node (class DepGraphNode) keeps lists of incoming and
15 // outgoing dependence edges.
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 //===----------------------------------------------------------------------===//
24 #include "DependenceGraph.h"
25 #include "llvm/Function.h"
29 //----------------------------------------------------------------------------
32 // A representation of a simple (non-loop-related) dependence
33 //----------------------------------------------------------------------------
35 void Dependence::print(std::ostream &O) const
37 assert(depType != NoDependence && "This dependence should never be created!");
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;
48 //----------------------------------------------------------------------------
50 //----------------------------------------------------------------------------
52 void DepGraphNode::print(std::ostream &O) const
54 const_iterator DI = outDepBegin(), DE = outDepEnd();
56 O << "\nDeps. from instr:" << getInstr();
58 for ( ; DI != DE; ++DI)
62 O << " to instruction:";
63 O << DI->getSink()->getInstr();
67 //----------------------------------------------------------------------------
68 // class DependenceGraph
69 //----------------------------------------------------------------------------
71 DependenceGraph::~DependenceGraph()
73 // Free all DepGraphNode objects created for this graph
74 for (map_iterator I = depNodeMap.begin(), E = depNodeMap.end(); I != E; ++I)
78 void DependenceGraph::print(const Function& func, std::ostream &O) const
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))
87 } // End llvm namespace