ROSE Compiler Framework/call graph analysis

source files

src/midend/programAnalysis/CallGraphAnalysis/CallGraph.h

rose/tutorial/callGraphAnalysis.C and buildCallGraph.C

class interface 

class CallGraphBuilder
   {
     public:
       CallGraphBuilder( SgProject *proj );
       
       void buildCallGraph();

       template<typename Predicate>
       void buildCallGraph(Predicate pred);

       CallGraphCreate *getGraph(); 
       void classifyCallGraph();
     private:
       SgProject *project;
       CallGraphCreate *graph;
   };

Data structures

SgGraph

  • FunctionData: for a function decl, stores (callee?) function declaration list(functionList)*** , hasDefinition , findPointsToVirtualFunction():
  • FunctionData::FunctionData() find all callees and fill functionList for each node(function)
  • FuntionData * list --> callGraphData
  • CallGraphCreate typedef DAGCreate<CallGraphNode, CallGraphEdge> CallGraphCreate;
    • CallGraphNode * nodeList: label, hasDefinition, functionDeclaration,
    • CallGraphEdge  : label

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);
 }

Driver: CallGraphBuilder

  • CallGraphBuilder::buildCallGraph() CallGraph.C L1553
    • queryMemoryPool for all function declarations, including member function declarations

get the first nondefining declaration only

    • Create FunctionData for each of them
    • add FunctionData into callGraphData list.

FunctionData::FunctionData () //CallGraph.C L1096

  • get defining declaration
  • querySubTree(def, V_SgFunctionCallExp)
  • several cases : how about function pointers passed as parameters?
    • dotStartOp  : CallTargetSet::solveMemberFunctionPointerCall() **
    • .func and ->func: CallTargetSet::solveMemberFunctionCall()**
    • pointer dereference exp: CallTargetSet::solveFunctionPointerCall() **
    • memberfunctionRefExp: very simple
    • functionRefExp: very simple

CallGraph.h 

class CallGraphBuilder
{
  public:
    CallGraphBuilder( SgProject *proj);
    //! Default builder filtering nothing in the call graph
    void buildCallGraph();
    //! Builder accepting user defined predicate to filter certain functions
    template<typename Predicate>
      void buildCallGraph(Predicate pred);
    //! Grab the call graph built
    SgIncidenceDirectedGraph *getGraph(); 
    //void classifyCallGraph();

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

  private:
    SgProject *project;
    SgIncidenceDirectedGraph *graph;
    //We map each function to the corresponding graph node
    boost::unordered_map<SgFunctionDeclaration*, SgGraphNode*> graphNodes;

};

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)

Usage

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);
}
This article is issued from Wikibooks. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.