mono/monograph/monograph.c

   1 #include <glib.h>
   2 #include <string.h>
   3 #include "mono/metadata/class-internals.h"
   4 #include "mono/metadata/assembly.h"
   5 #include "mono/metadata/tokentype.h"
   6 #include "mono/metadata/opcodes.h"
   7 #include "mono/metadata/tabledefs.h"
   8 #include "mono/metadata/mono-endian.h"
   9 #include "mono/metadata/appdomain.h" /* mono_init */
  10 #include "mono/metadata/debug-helpers.h"
  11 #include "mono/utils/mono-compiler.h"
  12
  13 static FILE *output;
  14 static int include_namespace = 0;
  15 static int max_depth = 6;
  16 static int verbose = 0;
  17 static const char *graph_properties = "\tnode [fontsize=8.0]\n\tedge [len=2,color=red]\n";
  18
  19 static void
  20 output_type_edge (MonoClass *first, MonoClass *second) {
  21         if (include_namespace)
  22                 fprintf (output, "\t\"%s.%s\" -> \"%s.%s\"\n", first->name_space, first->name, second->name_space, second->name);
  23         else
  24                 fprintf (output, "\t\"%s\" -> \"%s\"\n", first->name, second->name);
  25 }
  26
  27 static void
  28 print_subtypes (MonoImage *image, MonoClass *class, int depth) {
  29         int i, token;
  30         const MonoTableInfo *t;
  31         MonoClass *child;
  32
  33         if (depth++ > max_depth)
  34                 return;
  35
  36         t = mono_image_get_table_info (image, MONO_TABLE_TYPEDEF);
  37
  38         token = mono_metadata_token_index (class->type_token);
  39         token <<= MONO_TYPEDEFORREF_BITS;
  40         token |= MONO_TYPEDEFORREF_TYPEDEF;
  41
  42         /* use a subgraph? */
  43         for (i = 0; i < mono_table_info_get_rows (t); ++i) {
  44                 if (token == mono_metadata_decode_row_col (t, i, MONO_TYPEDEF_EXTENDS)) {
  45                         child = mono_class_get (image, MONO_TOKEN_TYPE_DEF | (i + 1));
  46                         output_type_edge (class, child);
  47                         print_subtypes (image, child, depth);
  48                 }
  49         }
  50 }
  51
  52 static void
  53 type_graph (MonoImage *image, const char* cname) {
  54         MonoClass *class;
  55         MonoClass *parent;
  56         MonoClass *child;
  57         const char *name_space;
  58         char *p;
  59         int depth = 0;
  60
  61         cname = g_strdup (cname);
  62         p = strrchr (cname, '.');
  63         if (p) {
  64                 name_space = cname;
  65                 *p++ = 0;
  66                 cname = p;
  67         } else {
  68                 name_space = "";
  69         }
  70         class = mono_class_from_name (image, name_space, cname);
  71         if (!class) {
  72                 g_print ("class %s.%s not found\n", name_space, cname);
  73                 exit (1);
  74         }
  75         fprintf (output, "digraph blah {\n");
  76         fprintf (output, "%s", graph_properties);
  77         child = class;
  78         /* go back and print the parents for the node as well: not sure it's a good idea */
  79         for (parent = class->parent; parent; parent = parent->parent) {
  80                 output_type_edge (parent, child);
  81                 child = parent;
  82         }
  83         print_subtypes (image, class, depth);
  84         fprintf (output, "}\n");
  85 }
  86
  87 static void
  88 interface_graph (MonoImage *image, const char* cname) {
  89         MonoClass *class;
  90         MonoClass *child;
  91         const char *name_space;
  92         char *p;
  93         guint32 cols [MONO_INTERFACEIMPL_SIZE];
  94         guint32 token, i, count = 0;
  95         const MonoTableInfo *intf = mono_image_get_table_info (image, MONO_TABLE_INTERFACEIMPL);
  96
  97         cname = g_strdup (cname);
  98         p = strrchr (cname, '.');
  99         if (p) {
 100                 name_space = cname;
 101                 *p++ = 0;
 102                 cname = p;
 103         } else {
 104                 name_space = "";
 105         }
 106         class = mono_class_from_name (image, name_space, cname);
 107         if (!class) {
 108                 g_print ("interface %s.%s not found\n", name_space, cname);
 109                 exit (1);
 110         }
 111         /* chek if it's really an interface... */
 112         fprintf (output, "digraph interface {\n");
 113         fprintf (output, "%s", graph_properties);
 114         /* TODO: handle inetrface defined in one image and class defined in another. */
 115         token = mono_metadata_token_index (class->type_token);
 116         token <<= MONO_TYPEDEFORREF_BITS;
 117         token |= MONO_TYPEDEFORREF_TYPEDEF;
 118         for (i = 0; i < mono_table_info_get_rows (intf); ++i) {
 119                 mono_metadata_decode_row (intf, i, cols, MONO_INTERFACEIMPL_SIZE);
 120                 /*g_print ("index: %d [%d implements %d]\n", index, cols [MONO_INTERFACEIMPL_CLASS], cols [MONO_INTERFACEIMPL_INTERFACE]);*/
 121                 if (token == cols [MONO_INTERFACEIMPL_INTERFACE]) {
 122                         child = mono_class_get (image, MONO_TOKEN_TYPE_DEF | cols [MONO_INTERFACEIMPL_CLASS]);
 123                         output_type_edge (class, child);
 124                         count++;
 125                 }
 126         }
 127         fprintf (output, "}\n");
 128         if (verbose && !count)
 129                 g_print ("No class implements %s.%s\n", class->name_space, class->name);
 130
 131 }
 132
 133 static int back_branch_waste = 0;
 134 static int branch_waste = 0;
 135 static int var_waste = 0;
 136 static int int_waste = 0;
 137 static int nop_waste = 0;
 138 static int has_exceptions = 0;
 139 static int num_exceptions = 0;
 140 static int max_exceptions = 0;
 141 static int has_locals = 0;
 142 static int num_locals = 0;
 143 static int max_locals = 0;
 144 static int has_args = 0;
 145 static int num_args = 0;
 146 static int max_args = 0;
 147 static int has_maxstack = 0;
 148 static int num_maxstack = 0;
 149 static int max_maxstack = 0;
 150 static int has_code = 0;
 151 static int num_code = 0;
 152 static int max_code = 0;
 153 static int has_branch = 0;
 154 static int num_branch = 0;
 155 static int max_branch = 0;
 156 static int has_condbranch = 0;
 157 static int num_condbranch = 0;
 158 static int max_condbranch = 0;
 159 static int has_calls = 0;
 160 static int num_calls = 0;
 161 static int max_calls = 0;
 162 static int has_throw = 0;
 163 static int num_throw = 0;
 164 static int max_throw = 0;
 165 static int has_switch = 0;
 166 static int num_switch = 0;
 167 static int max_switch = 0;
 168 static int cast_sealed = 0;
 169 static int cast_iface = 0;
 170 static int total_cast = 0;
 171 static int nonvirt_callvirt = 0;
 172 static int total_callvirt = 0;
 173
 174 static void
 175 method_stats (MonoMethod *method) {
 176         const MonoOpcode *opcode;
 177         MonoMethodHeader *header;
 178         const unsigned char *ip;
 179         int i, n;
 180         int local_branch = 0, local_condbranch = 0, local_throw = 0, local_calls = 0;
 181         gint64 l;
 182
 183         if (method->iflags & (METHOD_IMPL_ATTRIBUTE_INTERNAL_CALL | METHOD_IMPL_ATTRIBUTE_RUNTIME))
 184                 return;
 185         if (method->flags & (METHOD_ATTRIBUTE_PINVOKE_IMPL | METHOD_ATTRIBUTE_ABSTRACT))
 186                 return;
 187
 188         header = mono_method_get_header (method);
 189         if (header->num_clauses)
 190                 has_exceptions++;
 191         num_exceptions += header->num_clauses;
 192         if (max_exceptions < header->num_clauses)
 193                 max_exceptions = header->num_clauses;
 194         if (header->num_locals)
 195                 has_locals++;
 196         num_locals += header->num_locals;
 197         if (max_locals < header->num_locals)
 198                 max_locals = header->num_locals;
 199
 200         if (max_maxstack < header->max_stack)
 201                 max_maxstack = header->max_stack;
 202         num_maxstack += header->max_stack;
 203         if (header->max_stack != 8) /* just a guess */
 204                 has_maxstack++;
 205
 206         n = method->signature->hasthis + method->signature->param_count;
 207         if (max_args < n)
 208                 max_args = n;
 209         num_args += n;
 210         if (n)
 211                 has_args++;
 212
 213         has_code++;
 214         if (max_code < header->code_size)
 215                 max_code = header->code_size;
 216         num_code += header->code_size;
 217
 218         ip = header->code;
 219
 220         while (ip < (header->code + header->code_size)) {
 221                 if (*ip == 0xfe) {
 222                         ++ip;
 223                         i = *ip + 256;
 224                 } else {
 225                         i = *ip;
 226                 }
 227
 228                 opcode = &mono_opcodes [i];
 229
 230                 switch (opcode->argument) {
 231                 case MonoInlineNone:
 232                         if (i == MONO_CEE_NOP)
 233                                 nop_waste++;
 234                         ++ip;
 235                         break;
 236                 case MonoInlineI:
 237                         n = read32 (ip + 1);
 238                         if (n >= -1 && n <= 8) {
 239                                 int_waste += 4;
 240                                 g_print ("%s %d\n", mono_opcode_name (i), n);
 241                         } else if (n < 128 && n >= -128) {
 242                                 int_waste += 3;
 243                                 g_print ("%s %d\n", mono_opcode_name (i), n);
 244                         }
 245                         ip += 5;
 246                         break;
 247                 case MonoInlineType:
 248                         if (i == MONO_CEE_CASTCLASS || i == MONO_CEE_ISINST) {
 249                                 guint32 token = read32 (ip + 1);
 250                                 MonoClass *k = mono_class_get (method->klass->image, token);
 251                                 if (k && k->flags & TYPE_ATTRIBUTE_SEALED)
 252                                         cast_sealed++;
 253                                 if (k && k->flags & TYPE_ATTRIBUTE_INTERFACE)
 254                                         cast_iface++;
 255                                 total_cast++;
 256                         }
 257                         ip += 5;
 258                         break;
 259                 case MonoInlineField:
 260                 case MonoInlineTok:
 261                 case MonoInlineString:
 262                 case MonoInlineSig:
 263                 case MonoShortInlineR:
 264                         ip += 5;
 265                         break;
 266                 case MonoInlineBrTarget:
 267                         n = read32 (ip + 1);
 268                         if (n < 128 && n >= -128) {
 269                                 branch_waste += 3;
 270                                 if (n < 0)
 271                                         back_branch_waste += 3;
 272                         }
 273                         ip += 5;
 274                         break;
 275                 case MonoInlineVar:
 276                         n = read16 (ip + 1);
 277                         if (n < 256) {
 278                                 if (n < 4) {
 279                                         switch (i) {
 280                                         case MONO_CEE_LDARG:
 281                                         case MONO_CEE_LDLOC:
 282                                         case MONO_CEE_STLOC:
 283                                                 var_waste += 3;
 284                                                 g_print ("%s %d\n", mono_opcode_name (i), n);
 285                                                 break;
 286                                         default:
 287                                                 var_waste += 2;
 288                                                 g_print ("%s %d\n", mono_opcode_name (i), n);
 289                                                 break;
 290                                         }
 291                                 } else {
 292                                         var_waste += 2;
 293                                         g_print ("%s %d\n", mono_opcode_name (i), n);
 294                                 }
 295                         }
 296                         ip += 3;
 297                         break;
 298                 case MonoShortInlineVar:
 299                         if ((signed char)ip [1] < 4 && (signed char)ip [1] >= 0) {
 300                                 switch (i) {
 301                                 case MONO_CEE_LDARG_S:
 302                                 case MONO_CEE_LDLOC_S:
 303                                 case MONO_CEE_STLOC_S:
 304                                         var_waste++;
 305                                         g_print ("%s %d\n", mono_opcode_name (i), (signed char)ip [1]);
 306                                         break;
 307                                 default:
 308                                         break;
 309                                 }
 310                         }
 311                         ip += 2;
 312                         break;
 313                 case MonoShortInlineI:
 314                         if ((signed char)ip [1] <= 8 && (signed char)ip [1] >= -1) {
 315                                 g_print ("%s %d\n", mono_opcode_name (i), (signed char)ip [1]);
 316                                 int_waste ++;
 317                         }
 318                         ip += 2;
 319                         break;
 320                 case MonoShortInlineBrTarget:
 321                         ip += 2;
 322                         break;
 323                 case MonoInlineSwitch: {
 324                         gint32 n;
 325                         ++ip;
 326                         n = read32 (ip);
 327                         ip += 4;
 328                         ip += 4 * n;
 329                         num_switch += n;
 330                         has_switch++;
 331                         if (max_switch < n)
 332                                 max_switch = n;
 333                         break;
 334                 }
 335                 case MonoInlineR:
 336                         ip += 9;
 337                         break;
 338                 case MonoInlineI8:
 339                         l = read64 (ip + 1);
 340                         /* should load and convert */
 341                         if (l >= -1 && l <= 8) {
 342                                 int_waste += 7;
 343                         } else if (l < 128 && l >= -128) {
 344                                 int_waste += 6;
 345                         } else if (l <= 2147483647 && l >= (-2147483647 -1)) {
 346                                 int_waste += 3;
 347                         }
 348                         ip += 9;
 349                         break;
 350                 case MonoInlineMethod:
 351                         if (i == MONO_CEE_CALLVIRT) {
 352                                 MonoMethod *cm = mono_get_method (method->klass->image, read32 (ip + 1), NULL);
 353                                 if (cm && !(cm->flags & METHOD_ATTRIBUTE_VIRTUAL))
 354                                         nonvirt_callvirt++;
 355                                 total_callvirt++;
 356                         }
 357                         ip += 5;
 358                         break;
 359                 default:
 360                         g_assert_not_reached ();
 361                 }
 362
 363                 switch (opcode->flow_type) {
 364                 case MONO_FLOW_BRANCH:
 365                         local_branch++;
 366                         break;
 367                 case MONO_FLOW_COND_BRANCH:
 368                         local_condbranch++;
 369                         break;
 370                 case MONO_FLOW_CALL:
 371                         local_calls++;
 372                         break;
 373                 case MONO_FLOW_ERROR:
 374                         local_throw++;
 375                         break;
 376                 }
 377         }
 378
 379         if (local_branch)
 380                 has_branch++;
 381         if (max_branch < local_branch)
 382                 max_branch = local_branch;
 383         num_branch += local_branch;
 384
 385         if (local_condbranch)
 386                 has_condbranch++;
 387         if (max_condbranch < local_condbranch)
 388                 max_condbranch = local_condbranch;
 389         num_condbranch += local_condbranch;
 390
 391         if (local_calls)
 392                 has_calls++;
 393         if (max_calls < local_calls)
 394                 max_calls = local_calls;
 395         num_calls += local_calls;
 396
 397         if (local_throw)
 398                 has_throw++;
 399         if (max_throw < local_throw)
 400                 max_throw = local_throw;
 401         num_throw += local_throw;
 402
 403         return;
 404 }
 405
 406 static int num_pdepth = 0;
 407 static int max_pdepth = 0;
 408 static int num_ifaces = 0;
 409
 410 static void
 411 type_stats (MonoClass *klass) {
 412         MonoClass *parent;
 413         int depth = 0;
 414
 415         if (klass->flags & TYPE_ATTRIBUTE_INTERFACE) {
 416                 num_ifaces++;
 417                 return;
 418         }
 419         parent = klass->parent;
 420         while (parent) {
 421                 depth++;
 422                 parent = parent->parent;
 423         }
 424         num_pdepth += depth;
 425         if (max_pdepth < depth)
 426                 max_pdepth = depth;
 427 }
 428
 429 static void
 430 stats (MonoImage *image, const char *name) {
 431         int i, num_methods, num_types;
 432         MonoMethod *method;
 433         MonoClass *klass;
 434
 435         num_methods = mono_image_get_table_rows (image, MONO_TABLE_METHOD);
 436         for (i = 0; i < num_methods; ++i) {
 437                 method = mono_get_method (image, MONO_TOKEN_METHOD_DEF | (i + 1), NULL);
 438                 method_stats (method);
 439         }
 440         num_types = mono_image_get_table_rows (image, MONO_TABLE_TYPEDEF);
 441         for (i = 0; i < num_types; ++i) {
 442                 klass = mono_class_get (image, MONO_TOKEN_TYPE_DEF | (i + 1));
 443                 type_stats (klass);
 444         }
 445
 446         g_print ("Methods and code stats:\n");
 447         g_print ("back branch waste: %d\n", back_branch_waste);
 448         g_print ("branch waste: %d\n", branch_waste);
 449         g_print ("var waste: %d\n", var_waste);
 450         g_print ("int waste: %d\n", int_waste);
 451         g_print ("nop waste: %d\n", nop_waste);
 452         g_print ("has exceptions: %d/%d, total: %d, max: %d, mean: %f\n", has_exceptions, num_methods, num_exceptions, max_exceptions, num_exceptions/(double)has_exceptions);
 453         g_print ("has locals: %d/%d, total: %d, max: %d, mean: %f\n", has_locals, num_methods, num_locals, max_locals, num_locals/(double)has_locals);
 454         g_print ("has args: %d/%d, total: %d, max: %d, mean: %f\n", has_args, num_methods, num_args, max_args, num_args/(double)has_args);
 455         g_print ("has maxstack: %d/%d, total: %d, max: %d, mean: %f\n", has_maxstack, num_methods, num_maxstack, max_maxstack, num_maxstack/(double)i);
 456         g_print ("has code: %d/%d, total: %d, max: %d, mean: %f\n", has_code, num_methods, num_code, max_code, num_code/(double)has_code);
 457         g_print ("has branch: %d/%d, total: %d, max: %d, mean: %f\n", has_branch, num_methods, num_branch, max_branch, num_branch/(double)has_branch);
 458         g_print ("has condbranch: %d/%d, total: %d, max: %d, mean: %f\n", has_condbranch, num_methods, num_condbranch, max_condbranch, num_condbranch/(double)has_condbranch);
 459         g_print ("has switch: %d/%d, total: %d, max: %d, mean: %f\n", has_switch, num_methods, num_switch, max_switch, num_switch/(double)has_switch);
 460         g_print ("has calls: %d/%d, total: %d, max: %d, mean: %f\n", has_calls, num_methods, num_calls, max_calls, num_calls/(double)has_calls);
 461         g_print ("has throw: %d/%d, total: %d, max: %d, mean: %f\n", has_throw, num_methods, num_throw, max_throw, num_throw/(double)has_throw);
 462         g_print ("sealed type cast: %d/%d\n", cast_sealed, total_cast);
 463         g_print ("interface type cast: %d/%d\n", cast_iface, total_cast);
 464         g_print ("non virtual callvirt: %d/%d\n", nonvirt_callvirt, total_callvirt);
 465
 466         g_print ("\nType stats:\n");
 467         g_print ("interface types: %d/%d\n", num_ifaces, num_types);
 468         g_print ("parent depth: max: %d, mean: %d\n", max_pdepth, num_pdepth/(num_types - num_ifaces));
 469 }
 470
 471 static char *
 472 get_signature (MonoMethod *method) {
 473         GString *res;
 474         static GHashTable *hash = NULL;
 475         char *result;
 476
 477         if (!hash)
 478                 hash = g_hash_table_new (g_direct_hash, g_direct_equal);
 479         if ((result = g_hash_table_lookup (hash, method)))
 480                 return result;
 481
 482         res = g_string_new ("");
 483         if (include_namespace && *(method->klass->name_space))
 484                 g_string_sprintfa (res, "%s.", method->klass->name_space);
 485         result = mono_signature_get_desc (method->signature, include_namespace);
 486         g_string_sprintfa (res, "%s:%s(%s)", method->klass->name, method->name, result);
 487         g_free (result);
 488         g_hash_table_insert (hash, method, res->str);
 489
 490         result = res->str;
 491         g_string_free (res, FALSE);
 492         return result;
 493
 494 }
 495
 496 static void
 497 output_method_edge (MonoMethod *first, MonoMethod *second) {
 498         char * f = get_signature (first);
 499         char * s = get_signature (second);
 500
 501         fprintf (output, "\t\"%s\" -> \"%s\"\n", f, s);
 502 }
 503
 504 /*
 505  * We need to handle virtual calls is derived types.
 506  * We could check what types implement the method and
 507  * disassemble all of them: this can make the graph to explode.
 508  * We could try and keep track of the 'this' pointer type and
 509  * consider only the methods in the classes derived from that:
 510  * this can reduce the graph complexity somewhat (and it would
 511  * be the more correct approach).
 512  */
 513 static void
 514 print_method (MonoMethod *method, int depth) {
 515         const MonoOpcode *opcode;
 516         MonoMethodHeader *header;
 517         GHashTable *hash;
 518         static GHashTable *visited = NULL;
 519         const unsigned char *ip;
 520         int i;
 521
 522         if (depth++ > max_depth)
 523                 return;
 524
 525         if (! visited)
 526                 visited = g_hash_table_new (NULL, NULL);
 527
 528         if (g_hash_table_lookup (visited, method))
 529                 return;
 530
 531         g_hash_table_insert (visited, method, method);
 532
 533         if (method->iflags & (METHOD_IMPL_ATTRIBUTE_INTERNAL_CALL | METHOD_IMPL_ATTRIBUTE_RUNTIME))
 534                 return;
 535         if (method->flags & (METHOD_ATTRIBUTE_PINVOKE_IMPL | METHOD_ATTRIBUTE_ABSTRACT))
 536                 return;
 537
 538         header = mono_method_get_header (method);
 539         ip = header->code;
 540
 541         hash = g_hash_table_new (g_direct_hash, g_direct_equal);
 542
 543         while (ip < (header->code + header->code_size)) {
 544                 if (*ip == 0xfe) {
 545                         ++ip;
 546                         i = *ip + 256;
 547                 } else {
 548                         i = *ip;
 549                 }
 550
 551                 opcode = &mono_opcodes [i];
 552
 553                 switch (opcode->argument) {
 554                 case MonoInlineNone:
 555                         ++ip;
 556                         break;
 557                 case MonoInlineType:
 558                 case MonoInlineField:
 559                 case MonoInlineTok:
 560                 case MonoInlineString:
 561                 case MonoInlineSig:
 562                 case MonoShortInlineR:
 563                 case MonoInlineI:
 564                 case MonoInlineBrTarget:
 565                         ip += 5;
 566                         break;
 567                 case MonoInlineVar:
 568                         ip += 3;
 569                         break;
 570                 case MonoShortInlineVar:
 571                 case MonoShortInlineI:
 572                 case MonoShortInlineBrTarget:
 573                         ip += 2;
 574                         break;
 575                 case MonoInlineSwitch: {
 576                         gint32 n;
 577                         ++ip;
 578                         n = read32 (ip);
 579                         ip += 4;
 580                         ip += 4 * n;
 581                         break;
 582                 }
 583                 case MonoInlineR:
 584                 case MonoInlineI8:
 585                         ip += 9;
 586                         break;
 587                 case MonoInlineMethod: {
 588                         guint32 token;
 589                         MonoMethod *called;
 590                         ip++;
 591                         token = read32 (ip);
 592                         ip += 4;
 593                         called = mono_get_method (method->klass->image, token, NULL);
 594                         if (!called)
 595                                 break; /* warn? */
 596                         if (g_hash_table_lookup (hash, called))
 597                                 break;
 598                         g_hash_table_insert (hash, called, called);
 599                         output_method_edge (method, called);
 600                         print_method (called, depth);
 601                         break;
 602                 }
 603                 default:
 604                         g_assert_not_reached ();
 605                 }
 606         }
 607         g_hash_table_destroy (hash);
 608 }
 609
 610 static void
 611 method_graph (MonoImage *image, const char *name) {
 612         int depth = 0;
 613         MonoMethod *method = NULL;
 614
 615         if (!name) {
 616                 guint32 token = mono_image_get_entry_point (image);
 617                 if (!token || !(method = mono_get_method (image, token, NULL))) {
 618                         g_print ("Cannot find entry point in %s: specify an explict method name.\n", mono_image_get_filename (image));
 619                         exit (1);
 620                 }
 621         } else {
 622                 /* search the method */
 623                 MonoMethodDesc *desc;
 624
 625                 desc = mono_method_desc_new (name, include_namespace);
 626                 if (!desc) {
 627                         g_print ("Invalid method name %s\n", name);
 628                         exit (1);
 629                 }
 630                 method = mono_method_desc_search_in_image (desc, image);
 631                 if (!method) {
 632                         g_print ("Cannot find method %s\n", name);
 633                         exit (1);
 634                 }
 635         }
 636         fprintf (output, "digraph blah {\n");
 637         fprintf (output, "%s", graph_properties);
 638
 639         print_method (method, depth);
 640
 641         fprintf (output, "}\n");
 642 }
 643
 644 typedef struct MonoBasicBlock MonoBasicBlock;
 645
 646 struct MonoBasicBlock {
 647         const unsigned char* cil_code;
 648         gint32 cil_length;
 649         gint dfn;
 650         GList *in_bb;
 651         GList *out_bb;
 652 };
 653
 654 static const unsigned char *debug_start;
 655
 656 static void
 657 link_bblock (MonoBasicBlock *from, MonoBasicBlock* to)
 658 {
 659         from->out_bb = g_list_prepend (from->out_bb, to);
 660         to->in_bb = g_list_prepend (to->in_bb, from);
 661         /*fprintf (stderr, "linking IL_%04x to IL_%04x\n", from->cil_code-debug_start, to->cil_code-debug_start);*/
 662 }
 663
 664 static int
 665 compare_bblock (const void *a, const void *b)
 666 {
 667         MonoBasicBlock * const *ab = a;
 668         MonoBasicBlock * const *bb = b;
 669
 670         return (*ab)->cil_code - (*bb)->cil_code;
 671 }
 672
 673 static GPtrArray*
 674 mono_method_find_bblocks (MonoMethodHeader *header)
 675 {
 676         const unsigned char *ip, *end, *start;
 677         const MonoOpcode *opcode;
 678         int i, block_end = 0;
 679         GPtrArray *result = g_ptr_array_new ();
 680         GHashTable *table = g_hash_table_new (g_direct_hash, g_direct_equal);
 681         MonoBasicBlock *entry_bb, *end_bb, *bb, *target;
 682
 683         ip = header->code;
 684         end = ip + header->code_size;
 685         debug_start = ip;
 686
 687         entry_bb = g_new0 (MonoBasicBlock, 1);
 688         end_bb = g_new0 (MonoBasicBlock, 1);
 689         g_ptr_array_add (result, entry_bb);
 690         g_ptr_array_add (result, end_bb);
 691
 692         bb = g_new0 (MonoBasicBlock, 1);
 693         bb->cil_code = ip;
 694         g_ptr_array_add (result, bb);
 695         link_bblock (entry_bb, bb);
 696         g_hash_table_insert (table, (char*)ip, bb);
 697         block_end = TRUE;
 698
 699         /* handle exception code blocks... */
 700         while (ip < end) {
 701                 start = ip;
 702                 if ((target = g_hash_table_lookup (table, ip)) && target != bb) {
 703                         if (!block_end)
 704                                 link_bblock (bb, target);
 705                         bb = target;
 706                         block_end = FALSE;
 707                 }
 708                 if (block_end) {
 709                         /*fprintf (stderr, "processing bbclok at IL_%04x\n", ip - header->code);*/
 710                         if (!(bb = g_hash_table_lookup (table, ip))) {
 711                                 bb = g_new0 (MonoBasicBlock, 1);
 712                                 bb->cil_code = ip;
 713                                 g_ptr_array_add (result, bb);
 714                                 g_hash_table_insert (table, (char*)ip, bb);
 715                         }
 716                         block_end = FALSE;
 717                 }
 718                 if (*ip == 0xfe) {
 719                         ++ip;
 720                         i = *ip + 256;
 721                 } else {
 722                         i = *ip;
 723                 }
 724
 725                 opcode = &mono_opcodes [i];
 726                 switch (opcode->flow_type) {
 727                 case MONO_FLOW_RETURN:
 728                         link_bblock (bb, end_bb);
 729                 case MONO_FLOW_ERROR:
 730                         block_end = 1;
 731                         break;
 732                 case MONO_FLOW_BRANCH: /* we handle branch when checking the argument type */
 733                 case MONO_FLOW_COND_BRANCH:
 734                 case MONO_FLOW_CALL:
 735                 case MONO_FLOW_NEXT:
 736                 case MONO_FLOW_META:
 737                         break;
 738                 default:
 739                         g_assert_not_reached ();
 740                 }
 741                 switch (opcode->argument) {
 742                 case MonoInlineNone:
 743                         ++ip;
 744                         break;
 745                 case MonoInlineType:
 746                 case MonoInlineField:
 747                 case MonoInlineMethod:
 748                 case MonoInlineTok:
 749                 case MonoInlineString:
 750                 case MonoInlineSig:
 751                 case MonoShortInlineR:
 752                 case MonoInlineI:
 753                         ip += 5;
 754                         break;
 755                 case MonoInlineVar:
 756                         ip += 3;
 757                         break;
 758                 case MonoShortInlineVar:
 759                 case MonoShortInlineI:
 760                         ip += 2;
 761                         break;
 762                 case MonoShortInlineBrTarget:
 763                 case MonoInlineBrTarget:
 764                         ip++;
 765                         if (opcode->argument == MonoShortInlineBrTarget) {
 766                                 i = (signed char)*ip;
 767                                 ip++;
 768                         } else {
 769                                 i = (gint32) read32 (ip);
 770                                 ip += 4;
 771                         }
 772                         if (opcode->flow_type == MONO_FLOW_COND_BRANCH) {
 773                                 if (!(target = g_hash_table_lookup (table, ip))) {
 774                                         target = g_new0 (MonoBasicBlock, 1);
 775                                         target->cil_code = ip;
 776                                         g_ptr_array_add (result, target);
 777                                         g_hash_table_insert (table, (char*)ip, target);
 778                                 }
 779                                 link_bblock (bb, target);
 780                         }
 781                         if (!(target = g_hash_table_lookup (table, ip + i))) {
 782                                 target = g_new0 (MonoBasicBlock, 1);
 783                                 target->cil_code = ip + i;
 784                                 g_ptr_array_add (result, target);
 785                                 g_hash_table_insert (table, (char*)ip + i, target);
 786                         }
 787                         link_bblock (bb, target);
 788                         block_end = 1;
 789                         break;
 790                 case MonoInlineSwitch: {
 791                         gint32 n;
 792                         const char *itarget, *st;
 793                         ++ip;
 794                         n = read32 (ip);
 795                         ip += 4;
 796                         st = (const char*)ip + 4 * n;
 797
 798                         for (i = 0; i < n; i++) {
 799                                 itarget = st + read32 (ip);
 800                                 ip += 4;
 801                                 if (!(target = g_hash_table_lookup (table, itarget))) {
 802                                         target = g_new0 (MonoBasicBlock, 1);
 803                                         target->cil_code = itarget;
 804                                         g_ptr_array_add (result, target);
 805                                         g_hash_table_insert (table, (gpointer) itarget, target);
 806                                 }
 807                                 link_bblock (bb, target);
 808                         }
 809                         /*
 810                          * Note: the code didn't set block_end in switch.
 811                          */
 812                         break;
 813                 }
 814                 case MonoInlineR:
 815                 case MonoInlineI8:
 816                         ip += 9;
 817                         break;
 818                 default:
 819                         g_assert_not_reached ();
 820                 }
 821
 822         }
 823         g_hash_table_destroy (table);
 824         qsort (result->pdata, result->len, sizeof (gpointer), compare_bblock);
 825         /* skip entry and end */
 826         bb = target = NULL;
 827         for (i = 2; i < result->len; ++i) {
 828                 bb = (MonoBasicBlock*)g_ptr_array_index (result, i);
 829                 if (target)
 830                         target->cil_length = bb->cil_code - target->cil_code;
 831                 target = bb;
 832                 /*fprintf (stderr, "bblock %d at IL_%04x:\n", i, bb->cil_code - header->code);*/
 833         }
 834         bb->cil_length = header->code + header->code_size - bb->cil_code;
 835         return result;
 836 }
 837
 838 static char*
 839 indenter (MonoDisHelper *dh, MonoMethod *method, guint32 ip_offset)
 840 {
 841         return g_strdup (" ");
 842 }
 843
 844 static MonoDisHelper graph_dh = {
 845         "\\l",
 846         NULL,
 847         "IL_%04x",
 848         indenter,
 849         NULL,
 850         NULL
 851 };
 852
 853 static void
 854 df_visit (MonoBasicBlock *bb, int *dfn, const unsigned char* code)
 855 {
 856         GList *tmp;
 857         MonoBasicBlock *next;
 858
 859         if (bb->dfn)
 860                 return;
 861         ++(*dfn);
 862         bb->dfn = *dfn;
 863         for (tmp = bb->out_bb; tmp; tmp = tmp->next) {
 864                 next = tmp->data;
 865                 if (!next->dfn) {
 866                         if (!bb->cil_code)
 867                                 fprintf (output, "\t\"DF entry\" -> \"IL_%04x (%d)\"\n", next->cil_code - code, *dfn + 1);
 868                         else
 869                                 fprintf (output, "\t\"IL_%04x (%d)\" -> \"IL_%04x (%d)\"\n", bb->cil_code - code, bb->dfn, next->cil_code - code, *dfn + 1);
 870                         df_visit (next, dfn, code);
 871                 }
 872         }
 873 }
 874
 875 static void
 876 print_method_cfg (MonoMethod *method) {
 877         GPtrArray *bblocks;
 878         GList *tmp;
 879         MonoBasicBlock *bb, *target;
 880         MonoMethodHeader *header;
 881         int i, dfn;
 882         char *code;
 883
 884         header = mono_method_get_header (method);
 885         bblocks = mono_method_find_bblocks (header);
 886         for (i = 0; i < bblocks->len; ++i) {
 887                 bb = (MonoBasicBlock*)g_ptr_array_index (bblocks, i);
 888                 if (i == 0)
 889                         fprintf (output, "\tB%p [shape=record,label=\"entry\"]\n", bb);
 890                 else if (i == 1)
 891                         fprintf (output, "\tB%p [shape=record,label=\"end\"]\n", bb);
 892                 else {
 893                         code = mono_disasm_code (&graph_dh, method, bb->cil_code, bb->cil_code + bb->cil_length);
 894                         fprintf (output, "\tB%p [shape=record,label=\"IL_%04x\\n%s\"]\n", bb, bb->cil_code - header->code, code);
 895                         g_free (code);
 896                 }
 897         }
 898         for (i = 0; i < bblocks->len; ++i) {
 899                 bb = (MonoBasicBlock*)g_ptr_array_index (bblocks, i);
 900                 for (tmp = bb->out_bb; tmp; tmp = tmp->next) {
 901                         target = tmp->data;
 902                         fprintf (output, "\tB%p -> B%p\n", bb, target);
 903                 }
 904         }
 905 #if 1
 906         for (i = 0; i < bblocks->len; ++i) {
 907                 bb = (MonoBasicBlock*)g_ptr_array_index (bblocks, i);
 908                 bb->dfn = 0;
 909         }
 910         dfn = 0;
 911         for (i = 0; i < bblocks->len; ++i) {
 912                 bb = (MonoBasicBlock*)g_ptr_array_index (bblocks, i);
 913                 df_visit (bb, &dfn, header->code);
 914         }
 915 #endif
 916 }
 917
 918 /*
 919  * TODO: change to create the DF tree, dominance relation etc.
 920  */
 921 static void
 922 method_cfg (MonoImage *image, const char *name) {
 923         MonoMethod *method = NULL;
 924         const static char *cfg_graph_properties = "\tnode [fontsize=8.0]\n\tedge [len=1.5,color=red]\n";
 925
 926         if (!name) {
 927                 guint32 token = mono_image_get_entry_point (image);
 928                 if (!token || !(method = mono_get_method (image, token, NULL))) {
 929                         g_print ("Cannot find entry point in %s: specify an explict method name.\n", mono_image_get_filename (image));
 930                         exit (1);
 931                 }
 932         } else {
 933                 /* search the method */
 934                 MonoMethodDesc *desc;
 935
 936                 desc = mono_method_desc_new (name, include_namespace);
 937                 if (!desc) {
 938                         g_print ("Invalid method name %s\n", name);
 939                         exit (1);
 940                 }
 941                 method = mono_method_desc_search_in_image (desc, image);
 942                 if (!method) {
 943                         g_print ("Cannot find method %s\n", name);
 944                         exit (1);
 945                 }
 946         }
 947         fprintf (output, "digraph blah {\n");
 948         fprintf (output, "%s", cfg_graph_properties);
 949
 950         print_method_cfg (method);
 951
 952         fprintf (output, "}\n");
 953 }
 954
 955 static void
 956 usage (void) {
 957         printf ("monograph 0.2 Copyright (c) 2002 Ximian, Inc\n");
 958         printf ("Create call graph or type hierarchy information from CIL assemblies.\n");
 959         printf ("Usage: monograph [options] [assembly [typename|methodname]]\n\n");
 960         printf ("Valid options are:\n");
 961         printf ("\t-c|--call             output call graph instead of type hierarchy\n");
 962         printf ("\t-C|--control-flow     output control flow of methodname\n");
 963         printf ("\t--stats               output some statistics about the assembly\n");
 964         printf ("\t-d|--depth num        max depth recursion (default: 6)\n");
 965         printf ("\t-o|--output filename  write graph to file filename (default: stdout)\n");
 966         printf ("\t-f|--fullname         include namespace in type and method names\n");
 967         printf ("\t-n|--neato            invoke neato directly\n");
 968         printf ("\t-v|--verbose          verbose operation\n\n");
 969         printf ("The default assembly is mscorlib.dll. The default method for\n");
 970         printf ("the --call and --control-flow options is the entrypoint.\n\n");
 971         printf ("When the --neato option is used the output type info is taken\n");
 972         printf ("from the output filename extension. You need the graphviz package\n");
 973         printf ("installed to be able to use this option and build bitmap files.\n");
 974         printf ("Without --neato, monograph will create .dot files, a description\n");
 975         printf ("file for a graph.\n\n");
 976         printf ("Sample runs:\n");
 977         printf ("\tmonograph -n -o vt.png mscorlib.dll System.ValueType\n");
 978         printf ("\tmonograph -n -o expr.png mcs.exe Mono.CSharp.Expression\n");
 979         printf ("\tmonograph -n -o cfg.png -C mcs.exe Driver:Main\n");
 980         printf ("\tmonograph -d 3 -n -o callgraph.png -c mis.exe\n");
 981         exit (1);
 982 }
 983
 984 enum {
 985         GRAPH_TYPES,
 986         GRAPH_CALL,
 987         GRAPH_INTERFACE,
 988         GRAPH_CONTROL_FLOW,
 989         GRAPH_STATS
 990 };
 991
 992 /*
 993  * TODO:
 994  * * virtual method calls as explained above
 995  * * maybe track field references
 996  * * track what exceptions a method could throw?
 997  * * for some inputs neato appears to hang or take a long time: kill it?
 998  * * allow passing additional command-line arguments to neato
 999  * * allow setting different graph/node/edge options directly
1000  * * option to avoid specialname methods
1001  * * make --neato option the default?
1002  * * use multiple classes/method roots?
1003  * * write a manpage
1004  * * reverse call graph: given a method what methods call it?
1005  */
1006 int
1007 main (int argc, char *argv[]) {
1008         MonoAssembly *assembly;
1009         MonoImage *image;
1010         const char *cname = NULL;
1011         const char *aname = NULL;
1012         char *outputfile = NULL;
1013         int graphtype = GRAPH_TYPES;
1014         int callneato = 0;
1015         int i;
1016
1017         mono_init (argv [0]);
1018         output = stdout;
1019
1020         for (i = 1; i < argc; ++i) {
1021                 if (argv [i] [0] != '-')
1022                         break;
1023                 if (strcmp (argv [i], "--call") == 0 || strcmp (argv [i], "-c") == 0) {
1024                         graphtype = GRAPH_CALL;
1025                 } else if (strcmp (argv [i], "--control-flow") == 0 || strcmp (argv [i], "-C") == 0) {
1026                         graphtype = GRAPH_CONTROL_FLOW;
1027                 } else if (strcmp (argv [i], "--interface") == 0 || strcmp (argv [i], "-i") == 0) {
1028                         graphtype = GRAPH_INTERFACE;
1029                 } else if (strcmp (argv [i], "--stats") == 0) {
1030                         graphtype = GRAPH_STATS;
1031                 } else if (strcmp (argv [i], "--fullname") == 0 || strcmp (argv [i], "-f") == 0) {
1032                         include_namespace = 1;
1033                 } else if (strcmp (argv [i], "--neato") == 0 || strcmp (argv [i], "-n") == 0) {
1034                         callneato = 1;
1035                 } else if (strcmp (argv [i], "--verbose") == 0 || strcmp (argv [i], "-v") == 0) {
1036                         verbose++;
1037                 } else if (strcmp (argv [i], "--output") == 0 || strcmp (argv [i], "-o") == 0) {
1038                         if (i + 1 >= argc)
1039                                 usage ();
1040                         outputfile = argv [++i];
1041                 } else if (strcmp (argv [i], "--depth") == 0 || strcmp (argv [i], "-d") == 0) {
1042                         if (i + 1 >= argc)
1043                                 usage ();
1044                         max_depth = atoi (argv [++i]);
1045                 } else {
1046                         usage ();
1047                 }
1048
1049         }
1050         if (argc > i)
1051                 aname = argv [i];
1052         if (argc > i + 1)
1053                 cname = argv [i + 1];
1054         if (aname) {
1055                 assembly = mono_assembly_open (aname, NULL);
1056         } else {
1057                 assembly = mono_image_get_assembly (mono_get_corlib ());
1058         }
1059         if (!cname && (graphtype == GRAPH_TYPES))
1060                 cname = "System.Object";
1061
1062         if (!assembly) {
1063                 g_print ("cannot open assembly %s\n", aname);
1064                 exit (1);
1065         }
1066
1067         if (callneato) {
1068                 GString *command = g_string_new ("neato");
1069                 char *type = NULL;
1070
1071                 if (outputfile) {
1072                         type = strrchr (outputfile, '.');
1073                         g_string_sprintfa (command, " -o %s", outputfile);
1074                 }
1075                 if (type)
1076                         g_string_sprintfa (command, " -T%s", type + 1);
1077                 output = popen (command->str, "w");
1078                 if (!output) {
1079                         g_print ("Cannot run neato: you may need to install the graphviz package.\n");
1080                         exit (1);
1081                 }
1082         } else if (outputfile) {
1083                 output = fopen (outputfile, "w");
1084                 if (!output) {
1085                         g_print ("Cannot open file: %s\n", outputfile);
1086                         exit (1);
1087                 }
1088         }
1089         /* if it looks like a method name, we want a callgraph. */
1090         if (cname && strchr (cname, ':') && graphtype == GRAPH_TYPES)
1091                 graphtype = GRAPH_CALL;
1092
1093         image = mono_assembly_get_image (assembly);
1094         switch (graphtype) {
1095         case GRAPH_TYPES:
1096                 type_graph (image, cname);
1097                 break;
1098         case GRAPH_CALL:
1099                 method_graph (image, cname);
1100                 break;
1101         case GRAPH_INTERFACE:
1102                 interface_graph (image, cname);
1103                 break;
1104         case GRAPH_CONTROL_FLOW:
1105                 method_cfg (image, cname);
1106                 break;
1107         case GRAPH_STATS:
1108                 stats (image, cname);
1109                 break;
1110         default:
1111                 g_error ("wrong graph type");
1112         }
1113
1114         if (callneato) {
1115                 if (verbose)
1116                         g_print ("waiting for neato.\n");
1117                 pclose (output);
1118         } else if (outputfile)
1119                 fclose (output);
1120         return 0;
1121 }
1122
1123