1/* Copyright �� International Business Machines Corp., 2006
2 *              Adelard LLP, 2007
3 *
4 * Author: Josh Triplett <josh@freedesktop.org>
5 *         Dan Sheridan <djs@adelard.com>
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23 * THE SOFTWARE.
24 */
25#include <stdarg.h>
26#include <stdlib.h>
27#include <stdio.h>
28#include <string.h>
29#include <ctype.h>
30#include <unistd.h>
31#include <fcntl.h>
32
33#include "lib.h"
34#include "allocate.h"
35#include "token.h"
36#include "parse.h"
37#include "symbol.h"
38#include "expression.h"
39#include "linearize.h"
40
41
42/* Draw the subgraph for a given entrypoint. Includes details of loads
43 * and stores for globals, and marks return bbs */
44static void graph_ep(struct entrypoint *ep)
45{
46	struct basic_block *bb;
47	struct instruction *insn;
48
49	const char *fname, *sname;
50
51	fname = show_ident(ep->name->ident);
52	sname = stream_name(ep->entry->bb->pos.stream);
53
54	printf("subgraph cluster%p {\n"
55	       "    color=blue;\n"
56	       "    label=<<TABLE BORDER=\"0\" CELLBORDER=\"0\">\n"
57	       "             <TR><TD>%s</TD></TR>\n"
58	       "             <TR><TD><FONT POINT-SIZE=\"21\">%s()</FONT></TD></TR>\n"
59	       "           </TABLE>>;\n"
60	       "    file=\"%s\";\n"
61	       "    fun=\"%s\";\n"
62	       "    ep=bb%p;\n",
63	       ep, sname, fname, sname, fname, ep->entry->bb);
64
65	FOR_EACH_PTR(ep->bbs, bb) {
66		struct basic_block *child;
67		int ret = 0;
68		const char * s = ", ls=\"[";
69
70		/* Node for the bb */
71		printf("    bb%p [shape=ellipse,label=%d,line=%d,col=%d",
72		       bb, bb->pos.line, bb->pos.line, bb->pos.pos);
73
74
75		/* List loads and stores */
76		FOR_EACH_PTR(bb->insns, insn) {
77			if (!insn->bb)
78				continue;
79			switch(insn->opcode) {
80			case OP_STORE:
81				if (insn->src->type == PSEUDO_SYM) {
82				  printf("%s store(%s)", s, show_ident(insn->src->sym->ident));
83				  s = ",";
84				}
85				break;
86
87			case OP_LOAD:
88				if (insn->src->type == PSEUDO_SYM) {
89				  printf("%s load(%s)", s, show_ident(insn->src->sym->ident));
90				  s = ",";
91				}
92				break;
93
94			case OP_RET:
95				ret = 1;
96				break;
97
98			}
99		} END_FOR_EACH_PTR(insn);
100		if (s[1] == 0)
101			printf("]\"");
102		if (ret)
103			printf(",op=ret");
104		printf("];\n");
105
106		/* Edges between bbs; lower weight for upward edges */
107		FOR_EACH_PTR(bb->children, child) {
108			printf("    bb%p -> bb%p [op=br, %s];\n", bb, child,
109			       (bb->pos.line > child->pos.line) ? "weight=5" : "weight=10");
110		} END_FOR_EACH_PTR(child);
111	} END_FOR_EACH_PTR(bb);
112
113	printf("}\n");
114}
115
116
117/* Insert edges for intra- or inter-file calls, depending on the value
118 * of internal. Bold edges are used for calls with destinations;
119 * dashed for calls to external functions */
120static void graph_calls(struct entrypoint *ep, int internal)
121{
122	struct basic_block *bb;
123	struct instruction *insn;
124
125	show_ident(ep->name->ident);
126	stream_name(ep->entry->bb->pos.stream);
127
128	FOR_EACH_PTR(ep->bbs, bb) {
129		if (!bb)
130			continue;
131		if (!bb->parents && !bb->children && !bb->insns && verbose < 2)
132			continue;
133
134		FOR_EACH_PTR(bb->insns, insn) {
135			if (!insn->bb)
136				continue;
137			if (insn->opcode == OP_CALL &&
138			    internal == !(insn->func->sym->ctype.modifiers & MOD_EXTERN)) {
139
140				/* Find the symbol for the callee's definition */
141				struct symbol * sym;
142				if (insn->func->type == PSEUDO_SYM) {
143					for (sym = insn->func->sym->ident->symbols;
144					     sym; sym = sym->next_id) {
145						if (sym->namespace & NS_SYMBOL && sym->ep)
146							break;
147					}
148
149					if (sym)
150						printf("bb%p -> bb%p"
151						       "[label=%d,line=%d,col=%d,op=call,style=bold,weight=30];\n",
152						       bb, sym->ep->entry->bb,
153						       insn->pos.line, insn->pos.line, insn->pos.pos);
154					else
155						printf("bb%p -> \"%s\" "
156						       "[label=%d,line=%d,col=%d,op=extern,style=dashed];\n",
157						       bb, show_pseudo(insn->func),
158						       insn->pos.line, insn->pos.line, insn->pos.pos);
159				}
160			}
161		} END_FOR_EACH_PTR(insn);
162	} END_FOR_EACH_PTR(bb);
163}
164
165int main(int argc, char **argv)
166{
167	struct string_list *filelist = NULL;
168	char *file;
169	struct symbol *sym;
170
171	struct symbol_list *fsyms, *all_syms=NULL;
172
173	printf("digraph call_graph {\n");
174	fsyms = sparse_initialize(argc, argv, &filelist);
175	concat_symbol_list(fsyms, &all_syms);
176
177	/* Linearize all symbols, graph internal basic block
178	 * structures and intra-file calls */
179	FOR_EACH_PTR(filelist, file) {
180
181		fsyms = sparse(file);
182		concat_symbol_list(fsyms, &all_syms);
183
184		FOR_EACH_PTR(fsyms, sym) {
185			expand_symbol(sym);
186			linearize_symbol(sym);
187		} END_FOR_EACH_PTR(sym);
188
189		FOR_EACH_PTR(fsyms, sym) {
190			if (sym->ep) {
191				graph_ep(sym->ep);
192				graph_calls(sym->ep, 1);
193			}
194		} END_FOR_EACH_PTR(sym);
195
196	} END_FOR_EACH_PTR(file);
197
198	/* Graph inter-file calls */
199	FOR_EACH_PTR(all_syms, sym) {
200		if (sym->ep)
201			graph_calls(sym->ep, 0);
202	} END_FOR_EACH_PTR(sym);
203
204	printf("}\n");
205	return 0;
206}
207