2 * mono-basic-block.c: Routines for parsing basic blocks from the IL stream
5 * Rodrigo Kumpera (rkumpera@novell.com)
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.
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>
19 #include <mono/utils/mono-error-internals.h>
20 #include <mono/utils/mono-compiler.h>
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))
25 #if SIZEOF_VOID_P == 4
26 #define CHECK_ADDP_OVERFLOW_UN(a,b) CHECK_ADD4_OVERFLOW_UN(a, b)
28 #define CHECK_ADDP_OVERFLOW_UN(a,b) CHECK_ADD8_OVERFLOW_UN(a, b)
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))
44 dump_bb_list (MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root, const char *msg)
46 printf ("------- %s --- root is %x ---\n", msg, (*root)->start);
49 printf ("BB start %x end %x left ", bb->start, bb->end);
51 printf ("%x", bb->left->start);
57 printf ("%x", bb->right->start);
63 printf ("%x", bb->parent->start);
67 printf(" color %s out [", bb->colour == RED ? "red" : "black");
69 for (tmp = bb->out_bb; tmp; tmp = tmp->next) {
70 MonoSimpleBasicBlock *to = tmp->data;
71 printf ("%x ", to->start);
73 printf ("] %s\n", bb->dead ? "dead" : "alive");
81 bb_unlink (MonoSimpleBasicBlock *from, MonoSimpleBasicBlock *to)
84 from->out_bb = g_slist_remove (from->out_bb, to);
88 bb_link (MonoSimpleBasicBlock *from, MonoSimpleBasicBlock *to)
90 if (g_slist_find (from->out_bb, to))
92 from->out_bb = g_slist_prepend (from->out_bb, to);
96 static MonoSimpleBasicBlock*
97 bb_grandparent (MonoSimpleBasicBlock *bb)
99 return bb && bb->parent ? bb->parent->parent : NULL;
102 static MonoSimpleBasicBlock*
103 bb_uncle (MonoSimpleBasicBlock *bb)
105 MonoSimpleBasicBlock *gp = bb_grandparent (bb);
108 if (bb->parent == gp->left)
114 change_node (MonoSimpleBasicBlock *from, MonoSimpleBasicBlock *to, MonoSimpleBasicBlock **root)
116 MonoSimpleBasicBlock *parent = from->parent;
118 if (parent->left == from)
129 rotate_right (MonoSimpleBasicBlock *parent, MonoSimpleBasicBlock **root)
131 MonoSimpleBasicBlock *bb = parent->left;
133 parent->left = bb->right;
134 parent->left->parent = parent;
138 change_node (parent, bb, root);
143 rotate_left (MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root)
145 MonoSimpleBasicBlock *other = bb->right;
147 bb->right = other->left;
148 bb->right->parent = bb;
152 change_node (bb, other, root);
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
160 bb_insert (MonoSimpleBasicBlock *first, MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root)
162 MonoSimpleBasicBlock *parent, *uncle, *grandparent;
163 int bb_start = bb->start;
167 if (bb_start < parent->start) {
168 if (parent->left == NULL) {
172 parent = parent->left;
174 if (parent->right == NULL) {
178 parent = parent->right;
187 if (bb->parent == NULL) {
192 if (bb->parent->colour == BLACK)
195 uncle = bb_uncle (bb);
196 if (uncle && uncle->colour == RED) {
197 grandparent = bb_grandparent (bb);
199 bb->parent->colour = BLACK;
200 uncle->colour = BLACK;
201 grandparent->colour = RED;
206 grandparent = bb_grandparent (bb);
207 if ((bb == bb->parent->right) && (bb->parent == grandparent->left)) {
208 rotate_left (bb->parent, root);
210 } else if ((bb == bb->parent->left) && (bb->parent == grandparent->right)) {
211 rotate_right (bb->parent, root);
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);
221 rotate_left (grandparent, root);
227 bb_idx_is_contained (MonoSimpleBasicBlock *bb, int target)
229 return bb->start <= target && target < bb->end;
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)
238 static MonoSimpleBasicBlock*
239 bb_split (MonoSimpleBasicBlock *first, MonoSimpleBasicBlock *hint, MonoSimpleBasicBlock **root, guint target, gboolean link_blocks, MonoMethod *method, MonoError *error)
241 MonoSimpleBasicBlock *res, *bb = first;
243 mono_error_init (error);
245 if (bb_idx_is_contained (hint, target)) {
247 } else if (hint->next && bb_idx_is_contained (hint->next, target)) {
252 if (bb_idx_is_contained (first, target))
254 if (first->start > target)
257 first = first->right;
262 mono_error_set_not_verifiable (error, method, "Invalid instruction target %x", target);
266 if (first->start == target)
269 res = g_new0 (MonoSimpleBasicBlock, 1);
271 res->end = first->end;
272 res->next = first->next;
273 res->out_bb = first->out_bb;
276 first->end = res->start;
278 first->out_bb = NULL;
281 bb_link (first, res);
282 bb_insert (bb, res, root);
288 bb_liveness (MonoSimpleBasicBlock *bb)
290 GPtrArray* mark_stack = g_ptr_array_new ();
293 /*All function entry points (prologue, EH handler/filter) are already marked*/
296 g_ptr_array_add (mark_stack, bb);
300 while (mark_stack->len > 0) {
301 MonoSimpleBasicBlock *block = (MonoSimpleBasicBlock *)g_ptr_array_remove_index_fast (mark_stack, mark_stack->len - 1);
304 for (tmp = block->out_bb; tmp; tmp = tmp->next) {
305 MonoSimpleBasicBlock *to = (MonoSimpleBasicBlock *)tmp->data;
307 g_ptr_array_add (mark_stack, to);
311 g_ptr_array_free (mark_stack, TRUE);
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
319 mono_opcode_has_static_branch (int opcode)
324 case MONO_CEE_RETHROW:
325 case MONO_CEE_ENDFINALLY:
333 bb_formation_il_pass (const unsigned char *start, const unsigned char *end, MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root, MonoMethod *method, MonoError *error)
335 unsigned const char *ip = start;
337 guint cli_addr, offset;
338 MonoSimpleBasicBlock *branch, *next, *current;
339 const MonoOpcode *opcode;
341 mono_error_init (error);
346 cli_addr = ip - start;
347 size = mono_opcode_value_and_size (&ip, end, &value);
349 mono_error_set_not_verifiable (error, method, "Invalid instruction %x", *ip);
353 while (current && cli_addr >= current->end)
354 current = current->next;
357 opcode = &mono_opcodes [value];
358 switch (opcode->argument) {
361 if (!mono_opcode_has_static_branch (value) || ip >= end)
363 if (!(next = bb_split (bb, current, root, ip - start, FALSE, method, error)))
366 bb_unlink (current, next);
369 case MonoInlineString:
371 case MonoInlineField:
374 case MonoShortInlineR:
379 case MonoInlineMethod:
381 if (value != MONO_CEE_JMP || ip >= end)
383 if (!(next = bb_split (bb, current, root, ip - start, FALSE, method, error)))
386 bb_unlink (current, next);
393 case MonoShortInlineVar:
394 case MonoShortInlineI:
401 case MonoShortInlineBrTarget:
402 case MonoInlineBrTarget:
403 if (opcode->argument == MonoShortInlineBrTarget) {
404 offset = cli_addr + 2 + (signed char)ip [1];
407 offset = cli_addr + 5 + (gint32)read32 (ip + 1);
411 branch = bb_split (bb, current, root, offset, TRUE, method, error);
415 /*If we splitted the current BB*/
416 if (offset < cli_addr && branch->start > current->start)
419 next = bb_split (bb, current, root, ip - start, opcode->flow_type != MONO_FLOW_BRANCH, method, error);
426 bb_link (current, branch);
427 if (next && opcode->flow_type == MONO_FLOW_BRANCH && next != branch) {
428 bb_unlink (current, next);
432 case MonoInlineSwitch: {
433 MonoSimpleBasicBlock *tmp;
434 guint32 j, n = read32 (ip + 1);
437 offset = cli_addr + 5 + 4 * n;
438 if (!(next = bb_split (bb, current, root, offset, TRUE, method, error)))
441 bb_link (current, next);
444 for (j = 0; j < n; ++j) {
446 mono_error_set_not_verifiable (error, method, "Invalid switch instruction %x", cli_addr);
449 if (!(next = bb_split (bb, next, root, offset + (gint32)read32 (ip), TRUE, method, error)))
451 bb_link (current, next);
458 mono_error_set_not_verifiable (error, method, "Invalid instruction %x", *ip);
463 mono_error_set_not_verifiable (error, method, "Invalid last instruction");
467 bb_formation_eh_pass (MonoMethodHeader *header, MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root, MonoMethod *method, MonoError *error)
470 int end = header->code_size;
472 mono_error_init (error);
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;
479 if (!(try_block = bb_split (bb, bb, root, clause->try_offset, TRUE, method, error)))
482 handler = bb_split (bb, try_block, root, clause->handler_offset, FALSE, method, error);
485 handler->dead = FALSE;
487 if (clause->flags == MONO_EXCEPTION_CLAUSE_FILTER) {
488 MonoSimpleBasicBlock *filter = bb_split (bb, try_block, root, clause->data.filter_offset, FALSE, method, error);
491 filter->dead = FALSE;
494 if (clause->try_offset + clause->try_len < end && !bb_split (bb, try_block, root, clause->try_offset + clause->try_len, FALSE, method, error))
497 if (clause->handler_offset + clause->handler_len < end && !bb_split (bb, handler, root, clause->handler_offset + clause->handler_len, FALSE, method, error))
503 * mono_basic_block_free:
505 * Release the memory associated with the list of basis blocks @bb.
508 mono_basic_block_free (MonoSimpleBasicBlock *bb)
511 MonoSimpleBasicBlock *next = bb->next;
513 g_slist_free (bb->out_bb);
520 * mono_basic_block_split:
522 * Return the list of basic blocks of method. Return NULL on failure and set @error.
524 MonoSimpleBasicBlock*
525 mono_basic_block_split (MonoMethod *method, MonoError *error, MonoMethodHeader *header)
527 MonoSimpleBasicBlock *bb, *root;
528 const unsigned char *start, *end;
530 mono_error_init (error);
532 start = header->code;
533 end = start + header->code_size;
535 bb = g_new0 (MonoSimpleBasicBlock, 1);
537 bb->end = end - start;
542 bb_formation_il_pass (start, end, bb, &root, method, error);
543 if (!mono_error_ok (error))
546 bb_formation_eh_pass (header, bb, &root, method, error);
547 if (!mono_error_ok (error))
553 dump_bb_list (bb, &root, g_strdup_printf("AFTER LIVENESS %s", mono_method_full_name (method, TRUE)));
559 mono_basic_block_free (bb);
564 * mono_opcode_value_and_size:
566 * Returns the size of the opcode starting at *@ip, or -1 on error.
567 * Value is the opcode number.
570 mono_opcode_value_and_size (const unsigned char **ip, const unsigned char *end, int *value)
572 const unsigned char *start = *ip, *p;
573 int i = *value = mono_opcode_value (ip, end);
575 if (i < 0 || i >= MONO_CEE_LAST)
579 switch (mono_opcodes [i].argument) {
583 case MonoInlineString:
585 case MonoInlineField:
586 case MonoInlineMethod:
589 case MonoShortInlineR:
591 case MonoInlineBrTarget:
597 case MonoShortInlineVar:
598 case MonoShortInlineI:
599 case MonoShortInlineBrTarget:
606 case MonoInlineSwitch: {
608 if (ADDP_IS_GREATER_OR_OVF (p, 5, end))
610 entries = read32 (p + 1);
611 if (entries >= (0xFFFFFFFFU / 4))
613 size = 4 + 4 * entries;
617 g_error ("Invalid opcode %d argument %d max opcode %d\n", i, mono_opcodes [i].argument, MONO_CEE_LAST);
620 if (ADDP_IS_GREATER_OR_OVF (p, size, end))
623 return (p - start) + size;
629 * Returns the size of the opcode starting at @ip, or -1 on error.
632 mono_opcode_size (const unsigned char *ip, const unsigned char *end)
635 return mono_opcode_value_and_size (&ip, end, &tmp);