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>

1 files changed, 139 insertions, 20 deletions

diff --git a/graph.c b/graph.c
index 1a26ce0..1a77d75 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;
 }