1efe51d0cSJohn Levon /* Copyright © International Business Machines Corp., 2006
21f5207b7SJohn Levon * Adelard LLP, 2007
31f5207b7SJohn Levon *
41f5207b7SJohn Levon * Author: Josh Triplett <josh@freedesktop.org>
51f5207b7SJohn Levon * Dan Sheridan <djs@adelard.com>
61f5207b7SJohn Levon *
71f5207b7SJohn Levon * Permission is hereby granted, free of charge, to any person obtaining a copy
81f5207b7SJohn Levon * of this software and associated documentation files (the "Software"), to deal
91f5207b7SJohn Levon * in the Software without restriction, including without limitation the rights
101f5207b7SJohn Levon * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
111f5207b7SJohn Levon * copies of the Software, and to permit persons to whom the Software is
121f5207b7SJohn Levon * furnished to do so, subject to the following conditions:
131f5207b7SJohn Levon *
141f5207b7SJohn Levon * The above copyright notice and this permission notice shall be included in
151f5207b7SJohn Levon * all copies or substantial portions of the Software.
161f5207b7SJohn Levon *
171f5207b7SJohn Levon * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
181f5207b7SJohn Levon * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
191f5207b7SJohn Levon * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
201f5207b7SJohn Levon * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
211f5207b7SJohn Levon * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
221f5207b7SJohn Levon * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
231f5207b7SJohn Levon * THE SOFTWARE.
241f5207b7SJohn Levon */
251f5207b7SJohn Levon #include <stdarg.h>
261f5207b7SJohn Levon #include <stdlib.h>
271f5207b7SJohn Levon #include <stdio.h>
281f5207b7SJohn Levon #include <string.h>
291f5207b7SJohn Levon #include <ctype.h>
301f5207b7SJohn Levon #include <unistd.h>
311f5207b7SJohn Levon #include <fcntl.h>
321f5207b7SJohn Levon
331f5207b7SJohn Levon #include "lib.h"
341f5207b7SJohn Levon #include "allocate.h"
351f5207b7SJohn Levon #include "token.h"
361f5207b7SJohn Levon #include "parse.h"
371f5207b7SJohn Levon #include "symbol.h"
381f5207b7SJohn Levon #include "expression.h"
391f5207b7SJohn Levon #include "linearize.h"
401f5207b7SJohn Levon
411f5207b7SJohn Levon
421f5207b7SJohn Levon /* Draw the subgraph for a given entrypoint. Includes details of loads
431f5207b7SJohn Levon * and stores for globals, and marks return bbs */
graph_ep(struct entrypoint * ep)441f5207b7SJohn Levon static void graph_ep(struct entrypoint *ep)
451f5207b7SJohn Levon {
461f5207b7SJohn Levon struct basic_block *bb;
471f5207b7SJohn Levon struct instruction *insn;
481f5207b7SJohn Levon
491f5207b7SJohn Levon const char *fname, *sname;
501f5207b7SJohn Levon
511f5207b7SJohn Levon fname = show_ident(ep->name->ident);
521f5207b7SJohn Levon sname = stream_name(ep->entry->bb->pos.stream);
531f5207b7SJohn Levon
541f5207b7SJohn Levon printf("subgraph cluster%p {\n"
551f5207b7SJohn Levon " color=blue;\n"
561f5207b7SJohn Levon " label=<<TABLE BORDER=\"0\" CELLBORDER=\"0\">\n"
571f5207b7SJohn Levon " <TR><TD>%s</TD></TR>\n"
581f5207b7SJohn Levon " <TR><TD><FONT POINT-SIZE=\"21\">%s()</FONT></TD></TR>\n"
591f5207b7SJohn Levon " </TABLE>>;\n"
601f5207b7SJohn Levon " file=\"%s\";\n"
611f5207b7SJohn Levon " fun=\"%s\";\n"
621f5207b7SJohn Levon " ep=bb%p;\n",
631f5207b7SJohn Levon ep, sname, fname, sname, fname, ep->entry->bb);
641f5207b7SJohn Levon
651f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) {
661f5207b7SJohn Levon struct basic_block *child;
671f5207b7SJohn Levon int ret = 0;
681f5207b7SJohn Levon const char * s = ", ls=\"[";
691f5207b7SJohn Levon
701f5207b7SJohn Levon /* Node for the bb */
711f5207b7SJohn Levon printf(" bb%p [shape=ellipse,label=%d,line=%d,col=%d",
721f5207b7SJohn Levon bb, bb->pos.line, bb->pos.line, bb->pos.pos);
731f5207b7SJohn Levon
741f5207b7SJohn Levon
751f5207b7SJohn Levon /* List loads and stores */
761f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, insn) {
77*c85f09ccSJohn Levon if (!insn->bb)
78*c85f09ccSJohn Levon continue;
791f5207b7SJohn Levon switch(insn->opcode) {
801f5207b7SJohn Levon case OP_STORE:
81*c85f09ccSJohn Levon if (insn->src->type == PSEUDO_SYM) {
82*c85f09ccSJohn Levon printf("%s store(%s)", s, show_ident(insn->src->sym->ident));
831f5207b7SJohn Levon s = ",";
841f5207b7SJohn Levon }
851f5207b7SJohn Levon break;
861f5207b7SJohn Levon
871f5207b7SJohn Levon case OP_LOAD:
88*c85f09ccSJohn Levon if (insn->src->type == PSEUDO_SYM) {
89*c85f09ccSJohn Levon printf("%s load(%s)", s, show_ident(insn->src->sym->ident));
901f5207b7SJohn Levon s = ",";
911f5207b7SJohn Levon }
921f5207b7SJohn Levon break;
931f5207b7SJohn Levon
941f5207b7SJohn Levon case OP_RET:
951f5207b7SJohn Levon ret = 1;
961f5207b7SJohn Levon break;
971f5207b7SJohn Levon
981f5207b7SJohn Levon }
991f5207b7SJohn Levon } END_FOR_EACH_PTR(insn);
1001f5207b7SJohn Levon if (s[1] == 0)
1011f5207b7SJohn Levon printf("]\"");
1021f5207b7SJohn Levon if (ret)
1031f5207b7SJohn Levon printf(",op=ret");
1041f5207b7SJohn Levon printf("];\n");
1051f5207b7SJohn Levon
1061f5207b7SJohn Levon /* Edges between bbs; lower weight for upward edges */
1071f5207b7SJohn Levon FOR_EACH_PTR(bb->children, child) {
1081f5207b7SJohn Levon printf(" bb%p -> bb%p [op=br, %s];\n", bb, child,
1091f5207b7SJohn Levon (bb->pos.line > child->pos.line) ? "weight=5" : "weight=10");
1101f5207b7SJohn Levon } END_FOR_EACH_PTR(child);
1111f5207b7SJohn Levon } END_FOR_EACH_PTR(bb);
1121f5207b7SJohn Levon
1131f5207b7SJohn Levon printf("}\n");
1141f5207b7SJohn Levon }
1151f5207b7SJohn Levon
1161f5207b7SJohn Levon
1171f5207b7SJohn Levon /* Insert edges for intra- or inter-file calls, depending on the value
1181f5207b7SJohn Levon * of internal. Bold edges are used for calls with destinations;
1191f5207b7SJohn Levon * dashed for calls to external functions */
graph_calls(struct entrypoint * ep,int internal)1201f5207b7SJohn Levon static void graph_calls(struct entrypoint *ep, int internal)
1211f5207b7SJohn Levon {
1221f5207b7SJohn Levon struct basic_block *bb;
1231f5207b7SJohn Levon struct instruction *insn;
1241f5207b7SJohn Levon
1251f5207b7SJohn Levon show_ident(ep->name->ident);
1261f5207b7SJohn Levon stream_name(ep->entry->bb->pos.stream);
1271f5207b7SJohn Levon
1281f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) {
1291f5207b7SJohn Levon if (!bb)
1301f5207b7SJohn Levon continue;
1311f5207b7SJohn Levon if (!bb->parents && !bb->children && !bb->insns && verbose < 2)
1321f5207b7SJohn Levon continue;
1331f5207b7SJohn Levon
1341f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, insn) {
135*c85f09ccSJohn Levon if (!insn->bb)
136*c85f09ccSJohn Levon continue;
1371f5207b7SJohn Levon if (insn->opcode == OP_CALL &&
1381f5207b7SJohn Levon internal == !(insn->func->sym->ctype.modifiers & MOD_EXTERN)) {
1391f5207b7SJohn Levon
1401f5207b7SJohn Levon /* Find the symbol for the callee's definition */
1411f5207b7SJohn Levon struct symbol * sym;
1421f5207b7SJohn Levon if (insn->func->type == PSEUDO_SYM) {
1431f5207b7SJohn Levon for (sym = insn->func->sym->ident->symbols;
1441f5207b7SJohn Levon sym; sym = sym->next_id) {
1451f5207b7SJohn Levon if (sym->namespace & NS_SYMBOL && sym->ep)
1461f5207b7SJohn Levon break;
1471f5207b7SJohn Levon }
1481f5207b7SJohn Levon
1491f5207b7SJohn Levon if (sym)
1501f5207b7SJohn Levon printf("bb%p -> bb%p"
1511f5207b7SJohn Levon "[label=%d,line=%d,col=%d,op=call,style=bold,weight=30];\n",
1521f5207b7SJohn Levon bb, sym->ep->entry->bb,
1531f5207b7SJohn Levon insn->pos.line, insn->pos.line, insn->pos.pos);
1541f5207b7SJohn Levon else
1551f5207b7SJohn Levon printf("bb%p -> \"%s\" "
1561f5207b7SJohn Levon "[label=%d,line=%d,col=%d,op=extern,style=dashed];\n",
1571f5207b7SJohn Levon bb, show_pseudo(insn->func),
1581f5207b7SJohn Levon insn->pos.line, insn->pos.line, insn->pos.pos);
1591f5207b7SJohn Levon }
1601f5207b7SJohn Levon }
1611f5207b7SJohn Levon } END_FOR_EACH_PTR(insn);
1621f5207b7SJohn Levon } END_FOR_EACH_PTR(bb);
1631f5207b7SJohn Levon }
1641f5207b7SJohn Levon
main(int argc,char ** argv)1651f5207b7SJohn Levon int main(int argc, char **argv)
1661f5207b7SJohn Levon {
1671f5207b7SJohn Levon struct string_list *filelist = NULL;
1681f5207b7SJohn Levon char *file;
1691f5207b7SJohn Levon struct symbol *sym;
1701f5207b7SJohn Levon
1711f5207b7SJohn Levon struct symbol_list *fsyms, *all_syms=NULL;
1721f5207b7SJohn Levon
1731f5207b7SJohn Levon printf("digraph call_graph {\n");
1741f5207b7SJohn Levon fsyms = sparse_initialize(argc, argv, &filelist);
1751f5207b7SJohn Levon concat_symbol_list(fsyms, &all_syms);
1761f5207b7SJohn Levon
1771f5207b7SJohn Levon /* Linearize all symbols, graph internal basic block
1781f5207b7SJohn Levon * structures and intra-file calls */
179*c85f09ccSJohn Levon FOR_EACH_PTR(filelist, file) {
1801f5207b7SJohn Levon
1811f5207b7SJohn Levon fsyms = sparse(file);
1821f5207b7SJohn Levon concat_symbol_list(fsyms, &all_syms);
1831f5207b7SJohn Levon
1841f5207b7SJohn Levon FOR_EACH_PTR(fsyms, sym) {
1851f5207b7SJohn Levon expand_symbol(sym);
1861f5207b7SJohn Levon linearize_symbol(sym);
1871f5207b7SJohn Levon } END_FOR_EACH_PTR(sym);
1881f5207b7SJohn Levon
1891f5207b7SJohn Levon FOR_EACH_PTR(fsyms, sym) {
1901f5207b7SJohn Levon if (sym->ep) {
1911f5207b7SJohn Levon graph_ep(sym->ep);
1921f5207b7SJohn Levon graph_calls(sym->ep, 1);
1931f5207b7SJohn Levon }
194*c85f09ccSJohn Levon } END_FOR_EACH_PTR(sym);
1951f5207b7SJohn Levon
196*c85f09ccSJohn Levon } END_FOR_EACH_PTR(file);
1971f5207b7SJohn Levon
1981f5207b7SJohn Levon /* Graph inter-file calls */
1991f5207b7SJohn Levon FOR_EACH_PTR(all_syms, sym) {
2001f5207b7SJohn Levon if (sym->ep)
2011f5207b7SJohn Levon graph_calls(sym->ep, 0);
202*c85f09ccSJohn Levon } END_FOR_EACH_PTR(sym);
2031f5207b7SJohn Levon
2041f5207b7SJohn Levon printf("}\n");
2051f5207b7SJohn Levon return 0;
2061f5207b7SJohn Levon }
207