graph.c

   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  * Licensed under the Open Software License version 1.1
   8  */
   9 #include <stdarg.h>
  10 #include <stdlib.h>
  11 #include <stdio.h>
  12 #include <string.h>
  13 #include <ctype.h>
  14 #include <unistd.h>
  15 #include <fcntl.h>
  16
  17 #include "lib.h"
  18 #include "allocate.h"
  19 #include "token.h"
  20 #include "parse.h"
  21 #include "symbol.h"
  22 #include "expression.h"
  23 #include "linearize.h"
  24
  25
  26 /* Draw the subgraph for a given entrypoint. Includes details of loads
  27  * and stores for globals, and marks return bbs */
  28 static void graph_ep(struct entrypoint *ep)
  29 {
  30         struct basic_block *bb;
  31         struct instruction *insn;
  32
  33         const char *fname, *sname;
  34
  35         fname = show_ident(ep->name->ident);
  36         sname = stream_name(ep->entry->bb->pos.stream);
  37
  38         printf("subgraph cluster%p {\n"
  39                "    color=blue;\n"
  40                "    label=<<TABLE BORDER=\"0\" CELLBORDER=\"0\">\n"
  41                "             <TR><TD>%s</TD></TR>\n"
  42                "             <TR><TD><FONT POINT-SIZE=\"21\">%s()</FONT></TD></TR>\n"
  43                "           </TABLE>>;\n"
  44                "    file=\"%s\";\n"
  45                "    fun=\"%s\";\n"
  46                "    ep=bb%p;\n",
  47                ep, sname, fname, sname, fname, ep->entry->bb);
  48
  49         FOR_EACH_PTR(ep->bbs, bb) {
  50                 struct basic_block *child;
  51                 int ret = 0;
  52                 const char * s = ", ls=\"[";
  53
  54                 /* Node for the bb */
  55                 printf("    bb%p [shape=ellipse,label=%d,line=%d,col=%d",
  56                        bb, bb->pos.line, bb->pos.line, bb->pos.pos);
  57
  58
  59                 /* List loads and stores */
  60                 FOR_EACH_PTR(bb->insns, insn) {
  61                         switch(insn->opcode) {
  62                         case OP_STORE:
  63                                 if (insn->symbol->type == PSEUDO_SYM) {
  64                                   printf("%s store(%s)", s, show_ident(insn->symbol->sym->ident));
  65                                   s = ",";
  66                                 }
  67                                 break;
  68
  69                         case OP_LOAD:
  70                                 if (insn->symbol->type == PSEUDO_SYM) {
  71                                   printf("%s load(%s)", s, show_ident(insn->symbol->sym->ident));
  72                                   s = ",";
  73                                 }
  74                                 break;
  75
  76                         case OP_RET:
  77                                 ret = 1;
  78                                 break;
  79
  80                         }
  81                 } END_FOR_EACH_PTR(insn);
  82                 if (s[1] == 0)
  83                         printf("]\"");
  84                 if (ret)
  85                         printf(",op=ret");
  86                 printf("];\n");
  87
  88                 /* Edges between bbs; lower weight for upward edges */
  89                 FOR_EACH_PTR(bb->children, child) {
  90                         printf("    bb%p -> bb%p [op=br, %s];\n", bb, child,
  91                                (bb->pos.line > child->pos.line) ? "weight=5" : "weight=10");
  92                 } END_FOR_EACH_PTR(child);
  93         } END_FOR_EACH_PTR(bb);
  94
  95         printf("}\n");
  96 }
  97
  98
  99 /* Insert edges for intra- or inter-file calls, depending on the value
 100  * of internal. Bold edges are used for calls with destinations;
 101  * dashed for calls to external functions */
 102 static void graph_calls(struct entrypoint *ep, int internal)
 103 {
 104         struct basic_block *bb;
 105         struct instruction *insn;
 106
 107         const char *fname, *sname;
 108
 109         fname = show_ident(ep->name->ident);
 110         sname = stream_name(ep->entry->bb->pos.stream);
 111
 112         FOR_EACH_PTR(ep->bbs, bb) {
 113                 if (!bb)
 114                         continue;
 115                 if (!bb->parents && !bb->children && !bb->insns && verbose < 2)
 116                         continue;
 117
 118                 FOR_EACH_PTR(bb->insns, insn) {
 119                         if (insn->opcode == OP_CALL &&
 120                             internal == !(insn->func->sym->ctype.modifiers & MOD_EXTERN)) {
 121
 122                                 /* Find the symbol for the callee's definition */
 123                                 struct symbol * sym;
 124                                 if (insn->func->type == PSEUDO_SYM) {
 125                                         for (sym = insn->func->sym->ident->symbols;
 126                                              sym; sym = sym->next_id) {
 127                                                 if (sym->namespace & NS_SYMBOL && sym->ep)
 128                                                         break;
 129                                         }
 130
 131                                         if (sym)
 132                                                 printf("bb%p -> bb%p"
 133                                                        "[label=%d,line=%d,col=%d,op=call,style=bold,weight=30];\n",
 134                                                        bb, sym->ep->entry->bb,
 135                                                        insn->pos.line, insn->pos.line, insn->pos.pos);
 136                                         else
 137                                                 printf("bb%p -> \"%s\" "
 138                                                        "[label=%d,line=%d,col=%d,op=extern,style=dashed];\n",
 139                                                        bb, show_pseudo(insn->func),
 140                                                        insn->pos.line, insn->pos.line, insn->pos.pos);
 141                                 }
 142                         }
 143                 } END_FOR_EACH_PTR(insn);
 144         } END_FOR_EACH_PTR(bb);
 145 }
 146
 147 int main(int argc, char **argv)
 148 {
 149         struct string_list *filelist = NULL;
 150         char *file;
 151         struct symbol *sym;
 152
 153         struct symbol_list *fsyms, *all_syms=NULL;
 154
 155         printf("digraph call_graph {\n");
 156         fsyms = sparse_initialize(argc, argv, &filelist);
 157         concat_symbol_list(fsyms, &all_syms);
 158
 159         /* Linearize all symbols, graph internal basic block
 160          * structures and intra-file calls */
 161         FOR_EACH_PTR_NOTAG(filelist, file) {
 162
 163                 fsyms = sparse(file);
 164                 concat_symbol_list(fsyms, &all_syms);
 165
 166                 FOR_EACH_PTR(fsyms, sym) {
 167                         expand_symbol(sym);
 168                         linearize_symbol(sym);
 169                 } END_FOR_EACH_PTR(sym);
 170
 171                 FOR_EACH_PTR(fsyms, sym) {
 172                         if (sym->ep) {
 173                                 graph_ep(sym->ep);
 174                                 graph_calls(sym->ep, 1);
 175                         }
 176                 } END_FOR_EACH_PTR_NOTAG(sym);
 177
 178         } END_FOR_EACH_PTR_NOTAG(file);
 179
 180         /* Graph inter-file calls */
 181         FOR_EACH_PTR(all_syms, sym) {
 182                 if (sym->ep)
 183                         graph_calls(sym->ep, 0);
 184         } END_FOR_EACH_PTR_NOTAG(sym);
 185
 186         printf("}\n");
 187         return 0;
 188 }