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 <djs@adelard.com>
author: Dan Sheridan <djs@postman.org.uk> 2007-05-15 12:26:53 +0100
committer: Josh Triplett <josh@freedesktop.org> 2007-05-22 14:51:30 -0700
commit: bb7ff206a0a1afca8eefbf3fedd7b5962cdec6f1 (patch)
tree: bb4becf132b9023b86c11d6ee0836d2e75b71d01
parent: 1906791681c6f058ffa7bcec20d79aec18414f34 (diff)
download: sparse-dev-bb7ff206a0a1afca8eefbf3fedd7b5962cdec6f1.tar.gz
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 <josh@freedesktop.org>
+ *         Dan Sheridan <djs@adelard.com>
  *
  * 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=<<TABLE BORDER=\"0\" CELLBORDER=\"0\">\n"
+	       "             <TR><TD>%s</TD></TR>\n"
+	       "             <TR><TD><FONT POINT-SIZE=\"21\">%s()</FONT></TD></TR>\n"
+	       "           </TABLE>>;\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 */
 		};
 	};
author	Dan Sheridan <djs@postman.org.uk>	2007-05-15 12:26:53 +0100
committer	Josh Triplett <josh@freedesktop.org>	2007-05-22 14:51:30 -0700
commit	bb7ff206a0a1afca8eefbf3fedd7b5962cdec6f1 (patch)
tree	bb4becf132b9023b86c11d6ee0836d2e75b71d01
parent	1906791681c6f058ffa7bcec20d79aec18414f34 (diff)
download	sparse-dev-bb7ff206a0a1afca8eefbf3fedd7b5962cdec6f1.tar.gz