[PATCH 1/2] Improved graph generation using subgraph clusters for functions

[Dan Sheridan <djs@postman.org.uk>]

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>

---
 graph.c     |  161 +++++++++++++++++++++++++++++++++++++++++++++++++++--------
 linearize.c |    1 +
 symbol.h    |    1 +
 3 files changed, 142 insertions(+), 21 deletions(-)

diff --git a/graph.c b/graph.c
index 1a26ce0..106bba5 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;
 
-	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);
+	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);
+	
 	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)
-{
-	struct symbol *sym;
 
-	FOR_EACH_PTR(list, sym) {
-		struct entrypoint *ep;
+/* 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 basic_block *bb;
+	struct instruction *insn;
 
-		expand_symbol(sym);
-		ep = linearize_symbol(sym);
-		if (ep)
-			graph_ep(ep);
-	} END_FOR_EACH_PTR(sym);
+	const char *fname, *sname;
+	
+	fname = show_ident(ep->name->ident);
+	sname = stream_name(ep->entry->bb->pos.stream);
+	
+	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)) {
+				
+				/* 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;
 
-	printf("digraph control_flow {\n");
-	graph_symbols(sparse_initialize(argc, argv, &filelist));
+	struct symbol_list *fsyms, *all_syms=NULL;
+	
+	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 d428d92..d4e54e4 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 d1b2868..f12b9b3 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 */
 		};
 	};
-- 
1.4.4.2