mono/monograph/monograph.c

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