From bb7ff206a0a1afca8eefbf3fedd7b5962cdec6f1 Mon Sep 17 00:00:00 2001 From: Dan Sheridan Date: Tue, 15 May 2007 12:26:53 +0100 Subject: [PATCH] Improved graph generation using subgraph clusters for functions Improve the dot files generated by graph.c to put the basic blocks for each function into their own labelled subgraph cluster and to distinguish between branches and function calls using different edge types. Requires a change to struct symbol to keep track of the entrypoint associated with a given function identifier. Currently, no attempt is made to handle indirect function calls -- they are just ignored. Signed-off-by: Dan Sheridan --- graph.c | 159 ++++++++++++++++++++++++++++++++++++++++++++++++++++-------- linearize.c | 1 + symbol.h | 1 + 3 files changed, 141 insertions(+), 20 deletions(-) diff --git a/graph.c b/graph.c index 1a26ce0f..1a77d750 100644 --- a/graph.c +++ b/graph.c @@ -1,6 +1,8 @@ /* Copyright © International Business Machines Corp., 2006 + * Adelard LLP, 2007 * * Author: Josh Triplett + * Dan Sheridan * * Licensed under the Open Software License version 1.1 */ @@ -20,50 +22,167 @@ #include "expression.h" #include "linearize.h" + +/* Draw the subgraph for a given entrypoint. Includes details of loads + * and stores for globals, and marks return bbs */ static void graph_ep(struct entrypoint *ep) { struct basic_block *bb; + struct instruction *insn; + + const char *fname, *sname; + + fname = show_ident(ep->name->ident); + sname = stream_name(ep->entry->bb->pos.stream); + + printf("subgraph cluster%p {\n" + " color=blue;\n" + " label=<\n" + " \n" + " \n" + "
%s
%s()
>;\n" + " file=\"%s\";\n" + " fun=\"%s\";\n" + " ep=bb%p;\n", + ep, sname, fname, sname, fname, ep->entry->bb); - printf("ep%p [label=\"%s\",shape=ellipse];\n", - ep, show_ident(ep->name->ident)); - FOR_EACH_PTR(ep->bbs, bb) { - printf("bb%p [shape=record,label=\"%s:%d:%d\"]\n", bb, - stream_name(bb->pos.stream), bb->pos.line, bb->pos.pos); - } END_FOR_EACH_PTR(bb); FOR_EACH_PTR(ep->bbs, bb) { struct basic_block *child; + int ret = 0; + const char * s = ", ls=\"["; + + /* Node for the bb */ + printf(" bb%p [shape=ellipse,label=%d,line=%d,col=%d", + bb, bb->pos.line, bb->pos.line, bb->pos.pos); + + + /* List loads and stores */ + FOR_EACH_PTR(bb->insns, insn) { + switch(insn->opcode) { + case OP_STORE: + if (insn->symbol->type == PSEUDO_SYM) { + printf("%s store(%s)", s, show_ident(insn->symbol->sym->ident)); + s = ","; + } + break; + + case OP_LOAD: + if (insn->symbol->type == PSEUDO_SYM) { + printf("%s load(%s)", s, show_ident(insn->symbol->sym->ident)); + s = ","; + } + break; + + case OP_RET: + ret = 1; + break; + + } + } END_FOR_EACH_PTR(insn); + if (s[1] == 0) + printf("]\""); + if (ret) + printf(",op=ret"); + printf("];\n"); + + /* Edges between bbs; lower weight for upward edges */ FOR_EACH_PTR(bb->children, child) { - printf("bb%p -> bb%p;\n", bb, child); + printf(" bb%p -> bb%p [op=br, %s];\n", bb, child, + (bb->pos.line > child->pos.line) ? "weight=5" : "weight=10"); } END_FOR_EACH_PTR(child); } END_FOR_EACH_PTR(bb); - printf("ep%p -> bb%p;\n", ep, ep->entry->bb); + + printf("}\n"); } -static void graph_symbols(struct symbol_list *list) + +/* Insert edges for intra- or inter-file calls, depending on the value + * of internal. Bold edges are used for calls with destinations; + * dashed for calls to external functions */ +static void graph_calls(struct entrypoint *ep, int internal) { - struct symbol *sym; + struct basic_block *bb; + struct instruction *insn; + + const char *fname, *sname; + + fname = show_ident(ep->name->ident); + sname = stream_name(ep->entry->bb->pos.stream); - FOR_EACH_PTR(list, sym) { - struct entrypoint *ep; + FOR_EACH_PTR(ep->bbs, bb) { + if (!bb) + continue; + if (!bb->parents && !bb->children && !bb->insns && verbose < 2) + continue; + + FOR_EACH_PTR(bb->insns, insn) { + if (insn->opcode == OP_CALL && + internal == !(insn->func->sym->ctype.modifiers & MOD_EXTERN)) { - expand_symbol(sym); - ep = linearize_symbol(sym); - if (ep) - graph_ep(ep); - } END_FOR_EACH_PTR(sym); + /* Find the symbol for the callee's definition */ + struct symbol * sym; + if (insn->func->type == PSEUDO_SYM) { + for (sym = insn->func->sym->ident->symbols; + sym; sym = sym->next_id) { + if (sym->namespace & NS_SYMBOL && sym->ep) + break; + } + + if (sym) + printf("bb%p -> bb%p" + "[label=%d,line=%d,col=%d,op=call,style=bold,weight=30];\n", + bb, sym->ep->entry->bb, + insn->pos.line, insn->pos.line, insn->pos.pos); + else + printf("bb%p -> \"%s\" " + "[label=%d,line=%d,col=%d,op=extern,style=dashed];\n", + bb, show_pseudo(insn->func), + insn->pos.line, insn->pos.line, insn->pos.pos); + } + } + } END_FOR_EACH_PTR(insn); + } END_FOR_EACH_PTR(bb); } int main(int argc, char **argv) { struct string_list *filelist = NULL; char *file; + struct symbol *sym; + + struct symbol_list *fsyms, *all_syms=NULL; - printf("digraph control_flow {\n"); - graph_symbols(sparse_initialize(argc, argv, &filelist)); + printf("digraph call_graph {\n"); + fsyms = sparse_initialize(argc, argv, &filelist); + concat_symbol_list(fsyms, &all_syms); + /* Linearize all symbols, graph internal basic block + * structures and intra-file calls */ FOR_EACH_PTR_NOTAG(filelist, file) { - graph_symbols(sparse(file)); + + fsyms = sparse(file); + concat_symbol_list(fsyms, &all_syms); + + FOR_EACH_PTR(fsyms, sym) { + expand_symbol(sym); + linearize_symbol(sym); + } END_FOR_EACH_PTR(sym); + + FOR_EACH_PTR(fsyms, sym) { + if (sym->ep) { + graph_ep(sym->ep); + graph_calls(sym->ep, 1); + } + } END_FOR_EACH_PTR_NOTAG(sym); + } END_FOR_EACH_PTR_NOTAG(file); + + /* Graph inter-file calls */ + FOR_EACH_PTR(all_syms, sym) { + if (sym->ep) + graph_calls(sym->ep, 0); + } END_FOR_EACH_PTR_NOTAG(sym); + printf("}\n"); return 0; } diff --git a/linearize.c b/linearize.c index c38dd7d5..3a078237 100644 --- a/linearize.c +++ b/linearize.c @@ -2107,6 +2107,7 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t bb = alloc_basic_block(ep, sym->pos); ep->name = sym; + sym->ep = ep; set_activeblock(ep, bb); entry = alloc_instruction(OP_ENTRY, 0); diff --git a/symbol.h b/symbol.h index d1b2868e..79e88e1f 100644 --- a/symbol.h +++ b/symbol.h @@ -148,6 +148,7 @@ struct symbol { struct statement *inline_stmt; struct symbol_list *inline_symbol_list; struct expression *initializer; + struct entrypoint *ep; long long value; /* Initial value */ }; }; -- 2.11.4.GIT