mono/metadata/mono-basic-block.c

   1 /*
   2  * mono-basic-block.c: Routines for parsing basic blocks from the IL stream
   3  *
   4  * Authors:
   5  *   Rodrigo Kumpera (rkumpera@novell.com)
   6  *
   7  * Copyright 2010 Novell, Inc (http://www.novell.com)
   8  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   9  */
  10
  11 #include <config.h>
  12
  13 #include <mono/metadata/debug-helpers.h>
  14 #include <mono/metadata/metadata-internals.h>
  15 #include <mono/metadata/mono-endian.h>
  16 #include <mono/metadata/mono-basic-block.h>
  17 #include <mono/metadata/opcodes.h>
  18
  19 #include <mono/utils/mono-error-internals.h>
  20 #include <mono/utils/mono-compiler.h>
  21
  22 #define CHECK_ADD4_OVERFLOW_UN(a, b) ((guint32)(0xFFFFFFFFU) - (guint32)(b) < (guint32)(a))
  23 #define CHECK_ADD8_OVERFLOW_UN(a, b) ((guint64)(0xFFFFFFFFFFFFFFFFUL) - (guint64)(b) < (guint64)(a))
  24
  25 #if SIZEOF_VOID_P == 4
  26 #define CHECK_ADDP_OVERFLOW_UN(a,b) CHECK_ADD4_OVERFLOW_UN(a, b)
  27 #else
  28 #define CHECK_ADDP_OVERFLOW_UN(a,b) CHECK_ADD8_OVERFLOW_UN(a, b)
  29 #endif
  30
  31 #define ADDP_IS_GREATER_OR_OVF(a, b, c) (((a) + (b) > (c)) || CHECK_ADDP_OVERFLOW_UN (a, b))
  32 #define ADD_IS_GREATER_OR_OVF(a, b, c) (((a) + (b) > (c)) || CHECK_ADD4_OVERFLOW_UN (a, b))
  33
  34 #define DEBUG_BB 0
  35
  36 enum {
  37         RED,
  38         BLACK
  39 };
  40
  41 #if DEBUG_BB
  42
  43 static void
  44 dump_bb_list (MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root, const char *msg)
  45 {
  46         printf ("------- %s --- root is %x ---\n", msg, (*root)->start);
  47         while (bb) {
  48                 GSList *tmp;
  49                 printf ("BB start %x end %x left ", bb->start, bb->end);
  50                 if (bb->left)
  51                         printf ("%x", bb->left->start);
  52                 else
  53                         printf ("NIL");
  54
  55                 printf (" right ");
  56                 if (bb->right)
  57                         printf ("%x", bb->right->start);
  58                 else
  59                         printf ("NIL");
  60
  61                 printf (" parent ");
  62                 if (bb->parent)
  63                         printf ("%x", bb->parent->start);
  64                 else
  65                         printf ("NIL");
  66
  67                 printf(" color %s out [", bb->colour == RED ? "red" : "black");
  68
  69                 for (tmp = bb->out_bb; tmp; tmp = tmp->next) {
  70                         MonoSimpleBasicBlock *to = tmp->data;
  71                         printf ("%x ", to->start);
  72                 }
  73                 printf ("] %s\n", bb->dead ? "dead" : "alive");
  74                 bb = bb->next;
  75         }
  76 }
  77
  78 #endif
  79
  80 static void
  81 bb_unlink (MonoSimpleBasicBlock *from, MonoSimpleBasicBlock *to)
  82 {
  83         if (from->out_bb)
  84                 from->out_bb = g_slist_remove (from->out_bb, to);
  85 }
  86
  87 static void
  88 bb_link (MonoSimpleBasicBlock *from, MonoSimpleBasicBlock *to)
  89 {
  90         if (g_slist_find (from->out_bb, to))
  91                 return;
  92         from->out_bb = g_slist_prepend (from->out_bb, to);
  93 }
  94
  95
  96 static MonoSimpleBasicBlock*
  97 bb_grandparent (MonoSimpleBasicBlock *bb)
  98 {
  99         return bb && bb->parent ? bb->parent->parent : NULL;
 100 }
 101
 102 static MonoSimpleBasicBlock*
 103 bb_uncle (MonoSimpleBasicBlock *bb)
 104 {
 105         MonoSimpleBasicBlock *gp = bb_grandparent (bb);
 106         if (gp == NULL)
 107                 return NULL;
 108         if (bb->parent == gp->left)
 109                 return gp->right;
 110         return gp->left;
 111 }
 112
 113 static void
 114 change_node (MonoSimpleBasicBlock *from, MonoSimpleBasicBlock *to, MonoSimpleBasicBlock **root)
 115 {
 116         MonoSimpleBasicBlock *parent = from->parent;
 117         if (parent) {
 118                 if (parent->left == from)
 119                         parent->left = to;
 120                 else
 121                         parent->right = to;
 122         } else {
 123                 *root = to;
 124         }
 125         to->parent = parent;
 126 }
 127
 128 static void
 129 rotate_right (MonoSimpleBasicBlock *parent, MonoSimpleBasicBlock **root)
 130 {
 131         MonoSimpleBasicBlock *bb = parent->left;
 132         if (bb->right) {
 133                 parent->left = bb->right;
 134                 parent->left->parent = parent;
 135         } else
 136                 parent->left = NULL;
 137         bb->right = parent;
 138         change_node (parent, bb, root);
 139         parent->parent = bb;
 140 }
 141
 142 static void
 143 rotate_left (MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root)
 144 {
 145         MonoSimpleBasicBlock *other = bb->right;
 146         if (other->left) {
 147                 bb->right = other->left;
 148                 bb->right->parent = bb;
 149         } else
 150                 bb->right = NULL;
 151         other->left = bb;
 152         change_node (bb, other, root);
 153         bb->parent = other;
 154 }
 155
 156 /* School book implementation of a RB tree with insert then fix (which requires a parent pointer)
 157  * TODO implement Sedgewick's version that doesn't require parent pointers
 158  */
 159 static void
 160 bb_insert (MonoSimpleBasicBlock *first, MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root)
 161 {
 162         MonoSimpleBasicBlock *parent, *uncle, *grandparent;
 163         int bb_start = bb->start;
 164
 165         parent = *root;
 166         do {
 167                 if (bb_start < parent->start) {
 168                         if (parent->left == NULL) {
 169                                 parent->left = bb;
 170                                 break;
 171                         }
 172                         parent = parent->left;
 173                 } else {
 174                         if (parent->right == NULL) {
 175                                 parent->right = bb;
 176                                 break;
 177                         }
 178                         parent = parent->right;
 179                 }
 180         } while (parent);
 181         g_assert (parent);
 182         bb->parent = parent;
 183
 184         bb->colour = RED;
 185
 186         do {
 187                 if (bb->parent == NULL) {
 188                         bb->colour = BLACK;
 189                         break;
 190                 }
 191
 192                 if (bb->parent->colour == BLACK)
 193                         break;
 194
 195                 uncle = bb_uncle (bb);
 196                 if (uncle && uncle->colour == RED) {
 197                         grandparent = bb_grandparent (bb);
 198
 199                         bb->parent->colour = BLACK;
 200                         uncle->colour = BLACK;
 201                         grandparent->colour = RED;
 202                         bb = grandparent;
 203                         continue;
 204                 }
 205
 206                 grandparent = bb_grandparent (bb);
 207                 if ((bb == bb->parent->right) && (bb->parent == grandparent->left)) {
 208                         rotate_left (bb->parent, root);
 209                         bb = bb->left;
 210                 } else if ((bb == bb->parent->left) && (bb->parent == grandparent->right)) {
 211                         rotate_right (bb->parent, root);
 212                         bb = bb->right;
 213                 }
 214
 215                 grandparent = bb_grandparent (bb);
 216                 bb->parent->colour = BLACK;
 217                 grandparent->colour = RED;
 218                 if ((bb == bb->parent->left) && (bb->parent == grandparent->left))
 219                         rotate_right (grandparent, root);
 220                 else
 221                         rotate_left (grandparent, root);
 222                 break;
 223         } while (TRUE);
 224 }
 225
 226 static gboolean
 227 bb_idx_is_contained (MonoSimpleBasicBlock *bb, int target)
 228 {
 229         return bb->start <= target && target < bb->end;
 230 }
 231
 232 /*
 233  * Split the basic blocks from @first at @target.
 234  * @hint is a guess of a very close to the target basic block. It is probed before the RB tree as it's often possible
 235  * to provide a near to exact guess (next block splits, switch branch targets, etc)
 236  *
 237  */
 238 static MonoSimpleBasicBlock*
 239 bb_split (MonoSimpleBasicBlock *first, MonoSimpleBasicBlock *hint, MonoSimpleBasicBlock **root, guint target, gboolean link_blocks, MonoMethod *method, MonoError *error)
 240 {
 241         MonoSimpleBasicBlock *res, *bb = first;
 242
 243         mono_error_init (error);
 244
 245         if (bb_idx_is_contained (hint, target)) {
 246                 first = hint;
 247         } else if (hint->next && bb_idx_is_contained (hint->next, target)) {
 248                 first = hint->next;
 249         } else {
 250                 first = *root;
 251                 do {
 252                         if (bb_idx_is_contained (first, target))
 253                                 break;
 254                         if (first->start > target)
 255                                 first = first->left;
 256                         else
 257                                 first = first->right;
 258                 } while (first);
 259         }
 260
 261         if (first == NULL) {
 262                 mono_error_set_not_verifiable (error, method, "Invalid instruction target %x", target);
 263                 return NULL;
 264         }
 265
 266         if (first->start == target)
 267                 return first;
 268
 269         res = g_new0 (MonoSimpleBasicBlock, 1);
 270         res->start = target;
 271         res->end = first->end;
 272         res->next = first->next;
 273         res->out_bb = first->out_bb;
 274         res->dead = TRUE;
 275
 276         first->end = res->start;
 277         first->next = res;
 278         first->out_bb = NULL;
 279
 280         if (link_blocks)
 281                 bb_link (first, res);
 282         bb_insert (bb, res, root);
 283
 284         return res;
 285 }
 286
 287 static void
 288 bb_liveness (MonoSimpleBasicBlock *bb)
 289 {
 290         GPtrArray* mark_stack = g_ptr_array_new ();
 291         GSList *tmp;
 292
 293         /*All function entry points (prologue, EH handler/filter) are already marked*/
 294         while (bb) {
 295                 if (!bb->dead)
 296                         g_ptr_array_add (mark_stack, bb);
 297                 bb = bb->next;
 298         }
 299
 300         while (mark_stack->len > 0) {
 301                 MonoSimpleBasicBlock *block = (MonoSimpleBasicBlock *)g_ptr_array_remove_index_fast (mark_stack, mark_stack->len - 1);
 302                 block->dead = FALSE;
 303
 304                 for (tmp = block->out_bb; tmp; tmp = tmp->next) {
 305                         MonoSimpleBasicBlock *to = (MonoSimpleBasicBlock *)tmp->data;
 306                         if (to->dead)
 307                                 g_ptr_array_add (mark_stack, to);
 308                 }
 309         }
 310
 311         g_ptr_array_free (mark_stack, TRUE);
 312 }
 313
 314 /*This doesn't returns endfilter because it's not useful to split at its boundary.
 315 Endfilter must be the last instruction of a filter clause and MS enforces this, so we can't have
 316 dead code after it.
 317 */
 318 static gboolean
 319 mono_opcode_has_static_branch (int opcode)
 320 {
 321         switch (opcode) {
 322         case MONO_CEE_RET:
 323         case MONO_CEE_THROW:
 324         case MONO_CEE_RETHROW:
 325         case MONO_CEE_ENDFINALLY:
 326                 return TRUE;
 327         }
 328         return FALSE;
 329 }
 330
 331
 332 static void
 333 bb_formation_il_pass (const unsigned char *start, const unsigned char *end, MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root, MonoMethod *method, MonoError *error)
 334 {
 335         unsigned const char *ip = start;
 336         int value, size;
 337         guint cli_addr, offset;
 338         MonoSimpleBasicBlock *branch, *next, *current;
 339         const MonoOpcode *opcode;
 340
 341         mono_error_init (error);
 342
 343         current = bb;
 344
 345         while (ip < end) {
 346                 cli_addr = ip - start;
 347                 size = mono_opcode_value_and_size (&ip, end, &value);
 348                 if (size < 0) {
 349                         mono_error_set_not_verifiable (error, method, "Invalid instruction %x", *ip);
 350                         return;
 351                 }
 352
 353                 while (current && cli_addr >= current->end)
 354                         current = current->next;
 355                 g_assert (current);
 356
 357                 opcode = &mono_opcodes [value];
 358                 switch (opcode->argument) {
 359                 case MonoInlineNone:
 360                         ip++;
 361                         if (!mono_opcode_has_static_branch (value) || ip >= end)
 362                                 break;
 363                         if (!(next = bb_split (bb, current, root, ip - start, FALSE, method, error)))
 364                                 return;
 365
 366                         bb_unlink (current, next);
 367                         current = next;
 368                         break;
 369                 case MonoInlineString:
 370                 case MonoInlineType:
 371                 case MonoInlineField:
 372                 case MonoInlineTok:
 373                 case MonoInlineSig:
 374                 case MonoShortInlineR:
 375                 case MonoInlineI:
 376                         ip += 5;
 377                         break;
 378
 379                 case MonoInlineMethod:
 380                         ip += 5;
 381                         if (value != MONO_CEE_JMP || ip >= end)
 382                                 break;
 383                         if (!(next = bb_split (bb, current, root, ip - start, FALSE, method, error)))
 384                                 return;
 385
 386                         bb_unlink (current, next);
 387                         current = next;
 388
 389                         break;
 390                 case MonoInlineVar:
 391                         ip += 3;
 392                         break;
 393                 case MonoShortInlineVar:
 394                 case MonoShortInlineI:
 395                         ip += 2;
 396                         break;
 397                 case MonoInlineR:
 398                 case MonoInlineI8:
 399                         ip += 9;
 400                         break;
 401                 case MonoShortInlineBrTarget:
 402                 case MonoInlineBrTarget:
 403                         if (opcode->argument == MonoShortInlineBrTarget) {
 404                                 offset = cli_addr + 2 + (signed char)ip [1];
 405                                 ip += 2;
 406                         } else {
 407                                 offset = cli_addr + 5 + (gint32)read32 (ip + 1);
 408                                 ip += 5;
 409                         }
 410
 411                         branch = bb_split (bb, current, root, offset, TRUE, method, error);
 412                         if (!branch)
 413                                 return;
 414
 415                         /*If we splitted the current BB*/
 416                         if (offset < cli_addr && branch->start > current->start)
 417                                 current = branch;
 418                         if (ip < end) {
 419                                 next = bb_split (bb, current, root, ip - start, opcode->flow_type != MONO_FLOW_BRANCH, method, error);
 420                                 if (!next)
 421                                         return;
 422                         } else {
 423                                 next = NULL;
 424                         }
 425
 426                         bb_link (current, branch);
 427                         if (next && opcode->flow_type == MONO_FLOW_BRANCH && next != branch) {
 428                                 bb_unlink (current, next);
 429                                 current = next;
 430                         }
 431                         break;
 432                 case MonoInlineSwitch: {
 433                         MonoSimpleBasicBlock *tmp;
 434                         guint32 j, n = read32 (ip + 1);
 435
 436                         ip += 5;
 437                         offset = cli_addr + 5 + 4 * n;
 438                         if (!(next = bb_split (bb, current, root, offset, TRUE, method, error)))
 439                                 return;
 440
 441                         bb_link (current, next);
 442                         tmp = next;
 443
 444                         for (j = 0; j < n; ++j) {
 445                                 if (ip >= end) {
 446                                         mono_error_set_not_verifiable (error, method, "Invalid switch instruction %x", cli_addr);
 447                                         return;
 448                                 }
 449                                 if (!(next = bb_split (bb, next, root, offset + (gint32)read32 (ip), TRUE, method, error)))
 450                                         return;
 451                                 bb_link (current, next);
 452                                 ip += 4;
 453                         }
 454                         current = tmp;
 455                         break;
 456                 }
 457                 default:
 458                         mono_error_set_not_verifiable (error, method, "Invalid instruction %x", *ip);
 459                         return;
 460                 }
 461         }
 462         if (ip != end)
 463                 mono_error_set_not_verifiable (error, method, "Invalid last instruction");
 464 }
 465
 466 static void
 467 bb_formation_eh_pass (MonoMethodHeader *header, MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root, MonoMethod *method, MonoError *error)
 468 {
 469         int i;
 470         int end = header->code_size;
 471
 472         mono_error_init (error);
 473
 474         /*We must split at all points to verify for targets in the middle of an instruction*/
 475         for (i = 0; i < header->num_clauses; ++i) {
 476                 MonoExceptionClause *clause = header->clauses + i;
 477                 MonoSimpleBasicBlock *try_block, *handler;
 478
 479                 if (!(try_block = bb_split (bb, bb, root, clause->try_offset, TRUE, method, error)))
 480                         return;
 481
 482                 handler = bb_split (bb, try_block, root, clause->handler_offset, FALSE, method, error);
 483                 if (!handler)
 484                         return;
 485                 handler->dead = FALSE;
 486
 487                 if (clause->flags == MONO_EXCEPTION_CLAUSE_FILTER) {
 488                         MonoSimpleBasicBlock *filter = bb_split (bb, try_block, root, clause->data.filter_offset, FALSE, method, error);
 489                         if (!filter)
 490                                 return;
 491                         filter->dead = FALSE;
 492                 }
 493
 494                 if (clause->try_offset + clause->try_len < end && !bb_split (bb, try_block, root, clause->try_offset + clause->try_len, FALSE, method, error))
 495                         return;
 496
 497                 if (clause->handler_offset + clause->handler_len < end && !bb_split (bb, handler, root, clause->handler_offset + clause->handler_len, FALSE, method, error))
 498                         return;
 499         }
 500 }
 501
 502 /*
 503  * mono_basic_block_free:
 504  *
 505  * Release the memory associated with the list of basis blocks @bb.
 506 */
 507 void
 508 mono_basic_block_free (MonoSimpleBasicBlock *bb)
 509 {
 510         while (bb) {
 511                 MonoSimpleBasicBlock *next = bb->next;
 512                 if (bb->out_bb)
 513                         g_slist_free (bb->out_bb);
 514                 g_free (bb);
 515                 bb = next;
 516         }
 517 }
 518
 519 /*
 520  * mono_basic_block_split:
 521  *
 522  * Return the list of basic blocks of method. Return NULL on failure and set @error.
 523 */
 524 MonoSimpleBasicBlock*
 525 mono_basic_block_split (MonoMethod *method, MonoError *error, MonoMethodHeader *header)
 526 {
 527         MonoSimpleBasicBlock *bb, *root;
 528         const unsigned char *start, *end;
 529
 530         mono_error_init (error);
 531
 532         start = header->code;
 533         end = start + header->code_size;
 534
 535         bb = g_new0 (MonoSimpleBasicBlock, 1);
 536         bb->start = 0;
 537         bb->end = end - start;
 538         bb->colour = BLACK;
 539         bb->dead = FALSE;
 540
 541         root = bb;
 542         bb_formation_il_pass (start, end, bb, &root, method, error);
 543         if (!mono_error_ok (error))
 544                 goto fail;
 545
 546         bb_formation_eh_pass (header, bb, &root, method, error);
 547         if (!mono_error_ok (error))
 548                 goto fail;
 549
 550         bb_liveness (bb);
 551
 552 #if DEBUG_BB
 553         dump_bb_list (bb, &root, g_strdup_printf("AFTER LIVENESS %s", mono_method_full_name (method, TRUE)));
 554 #endif
 555
 556         return bb;
 557
 558 fail:
 559         mono_basic_block_free (bb);
 560         return NULL;
 561 }
 562
 563 /*
 564  * mono_opcode_value_and_size:
 565  *
 566  * Returns the size of the opcode starting at *@ip, or -1 on error.
 567  * Value is the opcode number.
 568 */
 569 int
 570 mono_opcode_value_and_size (const unsigned char **ip, const unsigned char *end, int *value)
 571 {
 572         const unsigned char *start = *ip, *p;
 573         int i = *value = mono_opcode_value (ip, end);
 574         int size = 0;
 575         if (i < 0 || i >= MONO_CEE_LAST)
 576                 return -1;
 577         p = *ip;
 578
 579         switch (mono_opcodes [i].argument) {
 580         case MonoInlineNone:
 581                 size = 1;
 582                 break;
 583         case MonoInlineString:
 584         case MonoInlineType:
 585         case MonoInlineField:
 586         case MonoInlineMethod:
 587         case MonoInlineTok:
 588         case MonoInlineSig:
 589         case MonoShortInlineR:
 590         case MonoInlineI:
 591         case MonoInlineBrTarget:
 592                 size = 5;
 593                 break;
 594         case MonoInlineVar:
 595                 size = 3;
 596                 break;
 597         case MonoShortInlineVar:
 598         case MonoShortInlineI:
 599         case MonoShortInlineBrTarget:
 600                 size = 2;
 601                 break;
 602         case MonoInlineR:
 603         case MonoInlineI8:
 604                 size = 9;
 605                 break;
 606         case MonoInlineSwitch: {
 607                 guint32 entries;
 608                 if (ADDP_IS_GREATER_OR_OVF (p, 5, end))
 609                         return -1;
 610                 entries = read32 (p + 1);
 611                 if (entries >= (0xFFFFFFFFU / 4))
 612                         return -1;
 613                 size = 4 + 4 * entries;
 614                 break;
 615         }
 616         default:
 617                 g_error ("Invalid opcode %d argument %d max opcode %d\n", i, mono_opcodes [i].argument, MONO_CEE_LAST);
 618         }
 619
 620         if (ADDP_IS_GREATER_OR_OVF (p, size, end))
 621                 return -1;
 622
 623         return (p - start) + size;
 624 }
 625
 626 /*
 627  * mono_opcode_size:
 628  *
 629  * Returns the size of the opcode starting at @ip, or -1 on error.
 630 */
 631 int
 632 mono_opcode_size (const unsigned char *ip, const unsigned char *end)
 633 {
 634         int tmp;
 635         return mono_opcode_value_and_size (&ip, end, &tmp);
 636 }
 637