graph node

    SgGraphNode* graphNode = new SgGraphNode(functionName);
    graphNode->set_SgNode(currentFunction.functionDeclaration);

   // maintain an extra hash table between AST function and SgGraphNode
   graphNodes[currentFunction.functionDeclaration] = graphNode;

   // add a node into a graph
   returnGraph->addNode(graphNode);

graph edge

SgGraphNode *startingNode, *endNode; 
...
if (returnGraph->checkIfDirectedGraphEdgeExists(startingNode, endNode) == false)
 {
       ROSE_ASSERT(startingNode != NULL && endNode != NULL);
       returnGraph->addDirectedEdge(startingNode, endNode);
 }

function nodes

first nondefining declaration has precedence compared to defining declaration.

+++ b/src/midend/programAnalysis/CallGraphAnalysis/CallGraph.h
@@ -192,6 +192,7 @@ CallGraphBuilder::buildCallGraph(Predicate pred)
         else
         {
             // we need to have only one declaration for regular functions as well
+            // first nondefining declaration has precedence compared to defining declaration
             SgFunctionDeclaration *nonDefDecl = isSgFunctionDeclaration(functionDeclaration->get_firstNondefiningDeclaration());
             assert(!isSgTemplateFunctionDeclaration(nonDefDecl));
             if (nonDefDecl)

create a call graph

You can pass a predicate to filter out some functioins

// A Function object used as a predicate that determines which functions are 
// to be represented in the call graph.
struct keepFunction : public unary_function<bool,SgFunctionDeclaration*>{
  public:
    bool operator()(SgFunctionDeclaration* funcDecl){
      bool returnValue = true;
      ROSE_ASSERT(funcDecl != NULL);
      string filename = funcDecl->get_file_info()->get_filename();

      //Filter out functions from the ROSE preinclude header file
      if(filename.find("rose_edg_required_macros_and_functions")!=string::npos)
        returnValue = false;

      //Filter out compiler generated functions
      if(funcDecl->get_file_info()->isCompilerGenerated()==true)
        returnValue=false;
      //Filter out prototypes when defining function declarations exist at the same time
      // This is now necessary since we always generate the first nondefining declaration in ROSE using EDG 4.4.
      //Liao 1/23/2013
      if (funcDecl->get_definingDeclaration () != NULL)
        if (funcDecl->get_firstNondefiningDeclaration() == funcDecl)
          returnValue = false;

      return returnValue;
    }
};


 CallGraphBuilder builder(project);
 builder.buildCallGraph(keepFunction());

No predicate is fine also:

CallGraphBuilder CGBuilder( project );
CGBuilder.buildCallGraph();

CGBuilder.classifyCallGraph(); //? Classify subgraphs within call graph

//generate dot graph !!
GenerateDotGraph(CGBuilder.getGraph(),"callgraph.dot");

• src/3rdPartyLibraries/MSTL/DOTGraphInterface.h

(gdb) p *i $5 = (CallGraphNode &) @0x9abc060: {<GraphNode> = {<GraphElem> = {_vptr.GraphElem = 0x65d1d00, gc = 0x0, count = 1}, <No data fields>}, label = {static npos = 4294967295, _M_dataplus = {<std::allocator<char>> = {<__gnu_cxx::new_allocator<char>> = {<No data fields>}, <No data fields>}, _M_p = 0x9abbecc "__builtin_copysign"}}, functionDeclaration = 0xb7e60008, hasDefinition = false}

AST to Call Graph

class CallGraphBuilder
{
public:
   //We map each function to the corresponding graph node , a hash table
    boost::unordered_map<SgFunctionDeclaration*, SgGraphNode*>& getGraphNodesMapping(){ return graphNodes; }
};

traverse the graph

see SgGraph

class hierarchy

#SgGraph
    * SgIncidenceDirectedGraph  // directional
          o SgBidirectionalGraph  // bidirectional, in/out edges
                + SgIntKeyedBidirectionalGraph
                + SgStringKeyedBidirectionalGraph 
    * SgIncidenceUndirectedGraph  // undirected graph

# SgGraphNode:  an index as a unique id for each node

# SgGraphEdge: 
    * SgDirectedGraphEdge
    * SgUndirectedGraphEdge 

# SgGraphEdgeList

# SgGraphNodeList 

obtain nodes

A function can have multiple call graph nodes: why?

// initializes the cgNodes set
void CGFunction::initCGNodes()
{

    // get all the nodes
        set<SgGraphNode *> nodes = graph->computeNodeSet();

   // iterate through the nodes

        for(set<SgGraphNode*>::iterator itn = nodes.begin(); itn != nodes.end(); itn++) {
                SgNode* n = (*itn)->get_SgNode();
                ROSE_ASSERT(isSgFunctionDeclaration(n));
                
                SgFunctionDeclaration* cfgDecl = getCanonicalDecl(isSgFunctionDeclaration(n));

                // if the given SgGraphNode refers to this function
                if(cfgDecl == decl)
                        cgNodes.insert(*itn);
        }
}

obtain edges

  std::set<SgGraphNode*>::iterator itn;
  ...

  if(dir == fw) edges = func->graph->computeEdgeSetOut(*itn);  // get out edges
  else          edges = func->graph->computeEdgeSetIn(*itn);   // get in edges


  std::set<SgDirectedGraphEdge*>::iterator ite; // The current edge in edges

  // get destination or source of an edge
  SgGraphNode* target = (dir == fw ? (*ite)->get_to() : (*ite)->get_from());

dot graph generation

./tutorial/buildCallGraph.C

#include "rose.h"
#include <CallGraph.h>
#include <iostream>
using namespace std;

// A Function object used as a predicate that determines which functions are 
// to be represented in the call graph.
struct keepFunction : public unary_function<bool,SgFunctionDeclaration*>{
  public:
    bool operator()(SgFunctionDeclaration* funcDecl){
      bool returnValue = true;
      ROSE_ASSERT(funcDecl != NULL);
      string filename = funcDecl->get_file_info()->get_filename();

      //Filter out functions from the ROSE preinclude header file
      if(filename.find("rose_edg_required_macros_and_functions")!=string::npos)
        returnValue = false;

      //Filter out compiler generated functions
      if(funcDecl->get_file_info()->isCompilerGenerated()==true)
        returnValue=false;

      return returnValue;
    }
};

int main( int argc, char * argv[] )
{
  SgProject* project = new SgProject(argc, argv);
  ROSE_ASSERT (project != NULL);

  if (project->get_fileList().size() >=1)
  {
    //Construct a call Graph
    CallGraphBuilder CGBuilder( project);
    CGBuilder.buildCallGraph(keepFunction());

    // Output to a dot file
    AstDOTGeneration dotgen;
    SgFilePtrList file_list = project->get_fileList();
    std::string firstFileName = StringUtility::stripPathFromFileName(file_list[0]->getFileName());
    dotgen.writeIncidenceGraphToDOTFile( CGBuilder.getGraph(), firstFileName+"_callGraph.dot");
  }

  return 0; // backend(project);
}