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