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         if (bb_idx_is_contained (hint, target)) {
 244                 first = hint;
 245         } else if (hint->next && bb_idx_is_contained (hint->next, target)) {
 246                 first = hint->next;
 247         } else {
 248                 first = *root;
 249                 do {
 250                         if (bb_idx_is_contained (first, target))
 251                                 break;
 252                         if (first->start > target)
 253                                 first = first->left;
 254                         else
 255                                 first = first->right;
 256                 } while (first);
 257         }
 258
 259         if (first == NULL) {
 260                 mono_error_set_not_verifiable (error, method, "Invalid instruction target %x", target);
 261                 return NULL;
 262         }
 263
 264         if (first->start == target)
 265                 return first;
 266
 267         res = g_new0 (MonoSimpleBasicBlock, 1);
 268         res->start = target;
 269         res->end = first->end;
 270         res->next = first->next;
 271         res->out_bb = first->out_bb;
 272         res->dead = TRUE;
 273
 274         first->end = res->start;
 275         first->next = res;
 276         first->out_bb = NULL;
 277
 278         if (link_blocks)
 279                 bb_link (first, res);
 280         bb_insert (bb, res, root);
 281
 282         return res;
 283 }
 284
 285 static void
 286 bb_liveness (MonoSimpleBasicBlock *bb)
 287 {
 288         GPtrArray* mark_stack = g_ptr_array_new ();
 289         GSList *tmp;
 290
 291         /*All function entry points (prologue, EH handler/filter) are already marked*/
 292         while (bb) {
 293                 if (!bb->dead)
 294                         g_ptr_array_add (mark_stack, bb);
 295                 bb = bb->next;
 296         }
 297
 298         while (mark_stack->len > 0) {
 299                 MonoSimpleBasicBlock *block = (MonoSimpleBasicBlock *)g_ptr_array_remove_index_fast (mark_stack, mark_stack->len - 1);
 300                 block->dead = FALSE;
 301
 302                 for (tmp = block->out_bb; tmp; tmp = tmp->next) {
 303                         MonoSimpleBasicBlock *to = (MonoSimpleBasicBlock *)tmp->data;
 304                         if (to->dead)
 305                                 g_ptr_array_add (mark_stack, to);
 306                 }
 307         }
 308
 309         g_ptr_array_free (mark_stack, TRUE);
 310 }
 311
 312 /*This doesn't returns endfilter because it's not useful to split at its boundary.
 313 Endfilter must be the last instruction of a filter clause and MS enforces this, so we can't have
 314 dead code after it.
 315 */
 316 static gboolean
 317 mono_opcode_has_static_branch (int opcode)
 318 {
 319         switch (opcode) {
 320         case MONO_CEE_RET:
 321         case MONO_CEE_THROW:
 322         case MONO_CEE_RETHROW:
 323         case MONO_CEE_ENDFINALLY:
 324                 return TRUE;
 325         }
 326         return FALSE;
 327 }
 328
 329
 330 static void
 331 bb_formation_il_pass (const unsigned char *start, const unsigned char *end, MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root, MonoMethod *method, MonoError *error)
 332 {
 333         unsigned const char *ip = start;
 334         int value, size;
 335         guint cli_addr, offset;
 336         MonoSimpleBasicBlock *branch, *next, *current;
 337         const MonoOpcode *opcode;
 338
 339         current = bb;
 340
 341         while (ip < end) {
 342                 cli_addr = ip - start;
 343                 size = mono_opcode_value_and_size (&ip, end, &value);
 344                 if (size < 0) {
 345                         mono_error_set_not_verifiable (error, method, "Invalid instruction %x", *ip);
 346                         return;
 347                 }
 348
 349                 while (current && cli_addr >= current->end)
 350                         current = current->next;
 351                 g_assert (current);
 352
 353                 opcode = &mono_opcodes [value];
 354                 switch (opcode->argument) {
 355                 case MonoInlineNone:
 356                         ip++;
 357                         if (!mono_opcode_has_static_branch (value) || ip >= end)
 358                                 break;
 359                         if (!(next = bb_split (bb, current, root, ip - start, FALSE, method, error)))
 360                                 return;
 361
 362                         bb_unlink (current, next);
 363                         current = next;
 364                         break;
 365                 case MonoInlineString:
 366                 case MonoInlineType:
 367                 case MonoInlineField:
 368                 case MonoInlineTok:
 369                 case MonoInlineSig:
 370                 case MonoShortInlineR:
 371                 case MonoInlineI:
 372                         ip += 5;
 373                         break;
 374
 375                 case MonoInlineMethod:
 376                         ip += 5;
 377                         if (value != MONO_CEE_JMP || ip >= end)
 378                                 break;
 379                         if (!(next = bb_split (bb, current, root, ip - start, FALSE, method, error)))
 380                                 return;
 381
 382                         bb_unlink (current, next);
 383                         current = next;
 384
 385                         break;
 386                 case MonoInlineVar:
 387                         ip += 3;
 388                         break;
 389                 case MonoShortInlineVar:
 390                 case MonoShortInlineI:
 391                         ip += 2;
 392                         break;
 393                 case MonoInlineR:
 394                 case MonoInlineI8:
 395                         ip += 9;
 396                         break;
 397                 case MonoShortInlineBrTarget:
 398                 case MonoInlineBrTarget:
 399                         if (opcode->argument == MonoShortInlineBrTarget) {
 400                                 offset = cli_addr + 2 + (signed char)ip [1];
 401                                 ip += 2;
 402                         } else {
 403                                 offset = cli_addr + 5 + (gint32)read32 (ip + 1);
 404                                 ip += 5;
 405                         }
 406
 407                         branch = bb_split (bb, current, root, offset, TRUE, method, error);
 408                         if (!branch)
 409                                 return;
 410
 411                         /*If we splitted the current BB*/
 412                         if (offset < cli_addr && branch->start > current->start)
 413                                 current = branch;
 414                         if (ip < end) {
 415                                 next = bb_split (bb, current, root, ip - start, opcode->flow_type != MONO_FLOW_BRANCH, method, error);
 416                                 if (!next)
 417                                         return;
 418                         } else {
 419                                 next = NULL;
 420                         }
 421
 422                         bb_link (current, branch);
 423                         if (next && opcode->flow_type == MONO_FLOW_BRANCH && next != branch) {
 424                                 bb_unlink (current, next);
 425                                 current = next;
 426                         }
 427                         break;
 428                 case MonoInlineSwitch: {
 429                         MonoSimpleBasicBlock *tmp;
 430                         guint32 j, n = read32 (ip + 1);
 431
 432                         ip += 5;
 433                         offset = cli_addr + 5 + 4 * n;
 434                         if (!(next = bb_split (bb, current, root, offset, TRUE, method, error)))
 435                                 return;
 436
 437                         bb_link (current, next);
 438                         tmp = next;
 439
 440                         for (j = 0; j < n; ++j) {
 441                                 if (ip >= end) {
 442                                         mono_error_set_not_verifiable (error, method, "Invalid switch instruction %x", cli_addr);
 443                                         return;
 444                                 }
 445                                 if (!(next = bb_split (bb, next, root, offset + (gint32)read32 (ip), TRUE, method, error)))
 446                                         return;
 447                                 bb_link (current, next);
 448                                 ip += 4;
 449                         }
 450                         current = tmp;
 451                         break;
 452                 }
 453                 default:
 454                         mono_error_set_not_verifiable (error, method, "Invalid instruction %x", *ip);
 455                         return;
 456                 }
 457         }
 458         if (ip != end)
 459                 mono_error_set_not_verifiable (error, method, "Invalid last instruction");
 460 }
 461
 462 static void
 463 bb_formation_eh_pass (MonoMethodHeader *header, MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root, MonoMethod *method, MonoError *error)
 464 {
 465         int i;
 466         int end = header->code_size;
 467         /*We must split at all points to verify for targets in the middle of an instruction*/
 468         for (i = 0; i < header->num_clauses; ++i) {
 469                 MonoExceptionClause *clause = header->clauses + i;
 470                 MonoSimpleBasicBlock *try_block, *handler;
 471
 472                 if (!(try_block = bb_split (bb, bb, root, clause->try_offset, TRUE, method, error)))
 473                         return;
 474
 475                 handler = bb_split (bb, try_block, root, clause->handler_offset, FALSE, method, error);
 476                 if (!handler)
 477                         return;
 478                 handler->dead = FALSE;
 479
 480                 if (clause->flags == MONO_EXCEPTION_CLAUSE_FILTER) {
 481                         MonoSimpleBasicBlock *filter = bb_split (bb, try_block, root, clause->data.filter_offset, FALSE, method, error);
 482                         if (!filter)
 483                                 return;
 484                         filter->dead = FALSE;
 485                 }
 486
 487                 if (clause->try_offset + clause->try_len < end && !bb_split (bb, try_block, root, clause->try_offset + clause->try_len, FALSE, method, error))
 488                         return;
 489
 490                 if (clause->handler_offset + clause->handler_len < end && !bb_split (bb, handler, root, clause->handler_offset + clause->handler_len, FALSE, method, error))
 491                         return;
 492         }
 493 }
 494
 495 /*
 496  * mono_basic_block_free:
 497  *
 498  * Release the memory associated with the list of basis blocks @bb.
 499 */
 500 void
 501 mono_basic_block_free (MonoSimpleBasicBlock *bb)
 502 {
 503         while (bb) {
 504                 MonoSimpleBasicBlock *next = bb->next;
 505                 if (bb->out_bb)
 506                         g_slist_free (bb->out_bb);
 507                 g_free (bb);
 508                 bb = next;
 509         }
 510 }
 511
 512 /*
 513  * mono_basic_block_split:
 514  *
 515  * Return the list of basic blocks of method. Return NULL on failure and set @error.
 516 */
 517 MonoSimpleBasicBlock*
 518 mono_basic_block_split (MonoMethod *method, MonoError *error, MonoMethodHeader *header)
 519 {
 520         MonoError inner_error;
 521         MonoSimpleBasicBlock *bb, *root;
 522         const unsigned char *start, *end;
 523
 524         start = header->code;
 525         end = start + header->code_size;
 526
 527         bb = g_new0 (MonoSimpleBasicBlock, 1);
 528         bb->start = 0;
 529         bb->end = end - start;
 530         bb->colour = BLACK;
 531         bb->dead = FALSE;
 532
 533         root = bb;
 534         bb_formation_il_pass (start, end, bb, &root, method, error);
 535         if (!mono_error_ok (error))
 536                 goto fail;
 537
 538         bb_formation_eh_pass (header, bb, &root, method, error);
 539         if (!mono_error_ok (error))
 540                 goto fail;
 541
 542         bb_liveness (bb);
 543
 544 #if DEBUG_BB
 545         dump_bb_list (bb, &root, g_strdup_printf("AFTER LIVENESS %s", mono_method_full_name (method, TRUE)));
 546 #endif
 547
 548         return bb;
 549
 550 fail:
 551         mono_basic_block_free (bb);
 552         return NULL;
 553 }
 554
 555 /*
 556  * mono_opcode_value_and_size:
 557  *
 558  * Returns the size of the opcode starting at *@ip, or -1 on error.
 559  * Value is the opcode number.
 560 */
 561 int
 562 mono_opcode_value_and_size (const unsigned char **ip, const unsigned char *end, int *value)
 563 {
 564         const unsigned char *start = *ip, *p;
 565         int i = *value = mono_opcode_value (ip, end);
 566         int size = 0;
 567         if (i < 0 || i >= MONO_CEE_LAST)
 568                 return -1;
 569         p = *ip;
 570
 571         switch (mono_opcodes [i].argument) {
 572         case MonoInlineNone:
 573                 size = 1;
 574                 break;
 575         case MonoInlineString:
 576         case MonoInlineType:
 577         case MonoInlineField:
 578         case MonoInlineMethod:
 579         case MonoInlineTok:
 580         case MonoInlineSig:
 581         case MonoShortInlineR:
 582         case MonoInlineI:
 583         case MonoInlineBrTarget:
 584                 size = 5;
 585                 break;
 586         case MonoInlineVar:
 587                 size = 3;
 588                 break;
 589         case MonoShortInlineVar:
 590         case MonoShortInlineI:
 591         case MonoShortInlineBrTarget:
 592                 size = 2;
 593                 break;
 594         case MonoInlineR:
 595         case MonoInlineI8:
 596                 size = 9;
 597                 break;
 598         case MonoInlineSwitch: {
 599                 guint32 entries;
 600                 if (ADDP_IS_GREATER_OR_OVF (p, 5, end))
 601                         return -1;
 602                 entries = read32 (p + 1);
 603                 if (entries >= (0xFFFFFFFFU / 4))
 604                         return -1;
 605                 size = 4 + 4 * entries;
 606                 break;
 607         }
 608         default:
 609                 g_error ("Invalid opcode %d argument %d max opcode %d\n", i, mono_opcodes [i].argument, MONO_CEE_LAST);
 610         }
 611
 612         if (ADDP_IS_GREATER_OR_OVF (p, size, end))
 613                 return -1;
 614
 615         return (p - start) + size;
 616 }
 617
 618 /*
 619  * mono_opcode_size:
 620  *
 621  * Returns the size of the opcode starting at @ip, or -1 on error.
 622 */
 623 int
 624 mono_opcode_size (const unsigned char *ip, const unsigned char *end)
 625 {
 626         int tmp;
 627         return mono_opcode_value_and_size (&ip, end, &tmp);
 628 }
 629