ROSE 编译器框架/调用图分析
src/midend/programAnalysis/CallGraphAnalysis/CallGraph.h
rose/tutorial/callGraphAnalysis.C 和 buildCallGraph.C
类接口
class CallGraphBuilder
{
public:
CallGraphBuilder( SgProject *proj );
void buildCallGraph();
template<typename Predicate>
void buildCallGraph(Predicate pred);
CallGraphCreate *getGraph();
void classifyCallGraph();
private:
SgProject *project;
CallGraphCreate *graph;
};
SgGraph
- FunctionData: 对于一个函数声明，存储（被调用者？）函数声明列表（functionList）***，hasDefinition，findPointsToVirtualFunction()
- FunctionData::FunctionData() 找到所有被调用者并填充每个节点（函数）的 functionList
- FuntionData * 列表 --> callGraphData
- CallGraphCreate typedef DAGCreate<CallGraphNode, CallGraphEdge> CallGraphCreate;
- CallGraphNode * 节点列表：标签，hasDefinition，函数声明，
- CallGraphEdge ：标签
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);
SgGraphNode *startingNode, *endNode;
...
if (returnGraph->checkIfDirectedGraphEdgeExists(startingNode, endNode) == false)
{
ROSE_ASSERT(startingNode != NULL && endNode != NULL);
returnGraph->addDirectedEdge(startingNode, endNode);
}
- CallGraphBuilder::buildCallGraph() CallGraph.C L1553
- 查询所有函数声明的内存池，包括成员函数声明
仅获取第一个非定义声明
- 为每个声明创建 FunctionData
- 将 FunctionData 添加到 callGraphData 列表中。
FunctionData::FunctionData () //CallGraph.C L1096
- 获取定义声明
- querySubTree(def, V_SgFunctionCallExp)
- 几种情况：函数指针作为参数传递怎么办？
- dotStartOp ：CallTargetSet::solveMemberFunctionPointerCall() **
- .func 和 ->func: CallTargetSet::solveMemberFunctionPointerCall()**
- 指针解引用表达式：CallTargetSet::solveFunctionPointerCall() **
- 成员函数引用表达式：非常简单
- 函数引用表达式：非常简单
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;
};
第一个非定义声明优先于定义声明。
+++ 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)
您可以传递一个谓词来过滤掉一些函数
// 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());
没有谓词也可以
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}
class CallGraphBuilder
{
public:
//We map each function to the corresponding graph node , a hash table
boost::unordered_map<SgFunctionDeclaration*, SgGraphNode*>& getGraphNodesMapping(){ return graphNodes; }
};
参见 SgGraph
类层次结构
#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
一个函数可以有多个调用图节点：为什么？
// 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);
}
}
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());
./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);
}