mono/monograph/monograph.c

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