mono/monograph/monograph.c

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