2 * branch-opts.c: Branch optimizations support
5 * Patrik Torstensson (Patrik.Torstesson at gmail.com)
7 * (C) 2005 Ximian, Inc. http://www.ximian.com
15 * Returns true if @bb is a basic block which falls through the next block.
16 * TODO verify if it helps to check if the bb last ins is a branch to its successor.
19 mono_bb_is_fall_through (MonoCompile *cfg, MonoBasicBlock *bb)
21 return bb->next_bb && bb->next_bb->region == bb->region && /*fall throught between regions is not really interesting or useful*/
22 (bb->last_ins == NULL || !MONO_IS_BRANCH_OP (bb->last_ins)); /*and the last op can't be a branch too*/
26 * Used by the arch code to replace the exception handling
27 * with a direct branch. This is safe to do if the
28 * exception object isn't used, no rethrow statement and
29 * no filter statement (verify).
33 mono_branch_optimize_exception_target (MonoCompile *cfg, MonoBasicBlock *bb, const char * exname)
35 MonoMethod *method = cfg->method;
36 MonoMethodHeader *header = mono_method_get_header (method);
37 MonoExceptionClause *clause;
41 if (!(cfg->opt & MONO_OPT_EXCEPTION))
44 if (bb->region == -1 || !MONO_BBLOCK_IS_IN_REGION (bb, MONO_REGION_TRY))
47 exclass = mono_class_from_name (mono_get_corlib (), "System", exname);
48 /* search for the handler */
49 for (i = 0; i < header->num_clauses; ++i) {
50 clause = &header->clauses [i];
51 if (MONO_OFFSET_IN_CLAUSE (clause, bb->real_offset)) {
52 if (clause->flags == MONO_EXCEPTION_CLAUSE_NONE && clause->data.catch_class && mono_class_is_assignable_from (clause->data.catch_class, exclass)) {
55 /* get the basic block for the handler and
56 * check if the exception object is used.
57 * Flag is set during method_to_ir due to
58 * pop-op is optmized away in codegen (burg).
60 tbb = cfg->cil_offset_to_bb [clause->handler_offset];
61 if (tbb && tbb->flags & BB_EXCEPTION_DEAD_OBJ && !(tbb->flags & BB_EXCEPTION_UNSAFE)) {
62 MonoBasicBlock *targetbb = tbb;
63 gboolean unsafe = FALSE;
65 /* Check if this catch clause is ok to optimize by
66 * looking for the BB_EXCEPTION_UNSAFE in every BB that
67 * belongs to the same region.
69 * UNSAFE flag is set during method_to_ir (OP_RETHROW)
71 while (!unsafe && tbb->next_bb && tbb->region == tbb->next_bb->region) {
72 if (tbb->next_bb->flags & BB_EXCEPTION_UNSAFE) {
82 /* Create dummy inst to allow easier integration in
83 * arch dependent code (opcode ignored)
85 MONO_INST_NEW (cfg, jump, OP_BR);
87 /* Allocate memory for our branch target */
88 jump->inst_i1 = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoInst));
89 jump->inst_true_bb = targetbb;
91 if (cfg->verbose_level > 2)
92 g_print ("found exception to optimize - returning branch to BB%d (%s) (instead of throw) for method %s:%s\n", targetbb->block_num, clause->data.catch_class->name, cfg->method->klass->name, cfg->method->name);
99 /* Branching to an outer clause could skip inner clauses */
103 /* Branching to an outer clause could skip inner clauses */
112 static const int int_cmov_opcodes [] = {
125 static const int long_cmov_opcodes [] = {
139 br_to_br_un (int opcode)
155 g_assert_not_reached ();
163 * Replace INS with its decomposition which is stored in a series of bblocks starting
164 * at FIRST_BB and ending at LAST_BB. On enter, PREV points to the predecessor of INS.
165 * On return, it will be set to the last ins of the decomposition.
168 mono_replace_ins (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *ins, MonoInst **prev, MonoBasicBlock *first_bb, MonoBasicBlock *last_bb)
170 MonoInst *next = ins->next;
172 if (next && next->opcode == OP_NOP) {
173 /* Avoid NOPs following branches */
174 ins->next = next->next;
178 if (first_bb == last_bb) {
180 * Only one replacement bb, merge the code into
184 /* Delete links between the first_bb and its successors */
185 while (first_bb->out_count)
186 mono_unlink_bblock (cfg, first_bb, first_bb->out_bb [0]);
190 (*prev)->next = first_bb->code;
191 first_bb->code->prev = (*prev);
193 bb->code = first_bb->code;
197 last_bb->last_ins->next = next;
199 next->prev = last_bb->last_ins;
201 bb->last_ins = last_bb->last_ins;
202 *prev = last_bb->last_ins;
203 bb->has_array_access |= first_bb->has_array_access;
206 MonoBasicBlock **tmp_bblocks, *tmp;
212 for (tmp = first_bb; tmp; tmp = tmp->next_bb)
213 tmp->region = bb->region;
215 /* Split the original bb */
217 ins->next->prev = NULL;
221 /* Merge the second part of the original bb into the last bb */
222 if (last_bb->last_ins) {
223 last_bb->last_ins->next = next;
225 next->prev = last_bb->last_ins;
227 last_bb->code = next;
229 last_bb->has_array_access |= bb->has_array_access;
232 for (last = next; last->next != NULL; last = last->next)
234 last_bb->last_ins = last;
237 for (i = 0; i < bb->out_count; ++i)
238 mono_link_bblock (cfg, last_bb, bb->out_bb [i]);
240 /* Merge the first (dummy) bb to the original bb */
242 (*prev)->next = first_bb->code;
243 first_bb->code->prev = (*prev);
245 bb->code = first_bb->code;
247 bb->last_ins = first_bb->last_ins;
248 bb->has_array_access |= first_bb->has_array_access;
250 /* Delete the links between the original bb and its successors */
251 tmp_bblocks = bb->out_bb;
252 count = bb->out_count;
253 for (i = 0; i < count; ++i)
254 mono_unlink_bblock (cfg, bb, tmp_bblocks [i]);
256 /* Add links between the original bb and the first_bb's successors */
257 for (i = 0; i < first_bb->out_count; ++i) {
258 MonoBasicBlock *out_bb = first_bb->out_bb [i];
260 mono_link_bblock (cfg, bb, out_bb);
262 /* Delete links between the first_bb and its successors */
263 for (i = 0; i < bb->out_count; ++i) {
264 MonoBasicBlock *out_bb = bb->out_bb [i];
266 mono_unlink_bblock (cfg, first_bb, out_bb);
268 last_bb->next_bb = bb->next_bb;
269 bb->next_bb = first_bb->next_bb;
276 mono_if_conversion (MonoCompile *cfg)
278 #ifdef MONO_ARCH_HAVE_CMOV_OPS
280 gboolean changed = FALSE;
282 if (!(cfg->opt & MONO_OPT_CMOV))
285 // FIXME: Make this work with extended bblocks
288 * This pass requires somewhat optimized IR code so it should be run after
289 * local cprop/deadce. Also, it should be run before dominator computation, since
290 * it changes control flow.
292 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
293 MonoBasicBlock *bb1, *bb2;
296 /* Look for the IR code generated from cond ? a : b
307 if (!(bb->out_count == 2 && !bb->extended))
310 bb1 = bb->out_bb [0];
311 bb2 = bb->out_bb [1];
313 if (bb1->in_count == 1 && bb2->in_count == 1 && bb1->out_count == 1 && bb2->out_count == 1 && bb1->out_bb [0] == bb2->out_bb [0]) {
314 MonoInst *compare, *branch, *ins1, *ins2, *cmov, *move, *tmp;
315 MonoBasicBlock *true_bb, *false_bb;
316 gboolean simple, ret;
320 if (bb->last_ins && (bb->last_ins->opcode == OP_BR_REG || bb->last_ins->opcode == OP_BR))
323 /* Find the compare instruction */
324 if (!bb->last_ins || !bb->last_ins->prev)
326 branch = bb->last_ins;
327 compare = branch->prev;
329 if (!MONO_IS_COND_BRANCH_OP (branch))
330 /* This can happen if a cond branch is optimized away */
333 true_bb = branch->inst_true_bb;
334 false_bb = branch->inst_false_bb;
337 * Check that bb1 and bb2 are 'simple' and both assign to the same
340 /* FIXME: Get rid of the nops earlier */
341 ins1 = true_bb->code;
342 while (ins1 && ins1->opcode == OP_NOP)
344 ins2 = false_bb->code;
345 while (ins2 && ins2->opcode == OP_NOP)
347 if (!(ins1 && ins2 && ins1->dreg == ins2->dreg && ins1->dreg != -1))
351 for (tmp = ins1->next; tmp; tmp = tmp->next)
352 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_BR)))
355 for (tmp = ins2->next; tmp; tmp = tmp->next)
356 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_BR)))
362 /* We move ins1/ins2 before the compare so they should have no side effect */
363 if (!(MONO_INS_HAS_NO_SIDE_EFFECT (ins1) && MONO_INS_HAS_NO_SIDE_EFFECT (ins2)))
366 /* Moving ins1/ins2 could change the comparison */
368 if (!((compare->sreg1 != ins1->dreg) && (compare->sreg2 != ins1->dreg)))
372 comp_type = mono_opcode_to_type (branch->opcode, compare->opcode);
373 if (!((comp_type == CMP_TYPE_I) || (comp_type == CMP_TYPE_L)))
377 /* ins->type might not be set */
378 if (INS_INFO (ins1->opcode) [MONO_INST_DEST] != 'i')
381 if (cfg->verbose_level > 2) {
382 printf ("\tBranch -> CMove optimization in BB%d on\n", bb->block_num);
383 printf ("\t\t"); mono_print_ins (compare);
384 printf ("\t\t"); mono_print_ins (compare->next);
385 printf ("\t\t"); mono_print_ins (ins1);
386 printf ("\t\t"); mono_print_ins (ins2);
393 /* Assignments to the return register must remain at the end of bbs */
395 ret = ins1->dreg == cfg->ret->dreg;
399 tmp_reg = mono_alloc_dreg (cfg, STACK_I4);
402 /* Rewrite ins1 to emit to tmp_reg */
403 ins1->dreg = tmp_reg;
406 dreg = mono_alloc_dreg (cfg, STACK_I4);
410 /* Remove ins1/ins2 from bb1/bb2 */
411 MONO_REMOVE_INS (true_bb, ins1);
412 MONO_REMOVE_INS (false_bb, ins2);
414 /* Move ins1 and ins2 before the comparison */
415 /* ins1 comes first to avoid ins1 overwriting an argument of ins2 */
416 mono_bblock_insert_before_ins (bb, compare, ins2);
417 mono_bblock_insert_before_ins (bb, ins2, ins1);
419 /* Add cmov instruction */
420 MONO_INST_NEW (cfg, cmov, OP_NOP);
423 cmov->sreg2 = tmp_reg;
424 switch (mono_opcode_to_type (branch->opcode, compare->opcode)) {
426 cmov->opcode = int_cmov_opcodes [mono_opcode_to_cond (branch->opcode)];
429 cmov->opcode = long_cmov_opcodes [mono_opcode_to_cond (branch->opcode)];
432 g_assert_not_reached ();
434 mono_bblock_insert_after_ins (bb, compare, cmov);
437 /* Add an extra move */
438 MONO_INST_NEW (cfg, move, OP_MOVE);
439 move->dreg = cfg->ret->dreg;
441 mono_bblock_insert_after_ins (bb, cmov, move);
444 /* Rewrite the branch */
445 branch->opcode = OP_BR;
446 branch->inst_target_bb = true_bb->out_bb [0];
447 mono_link_bblock (cfg, bb, branch->inst_target_bb);
449 /* Reorder bblocks */
450 mono_unlink_bblock (cfg, bb, true_bb);
451 mono_unlink_bblock (cfg, bb, false_bb);
452 mono_unlink_bblock (cfg, true_bb, true_bb->out_bb [0]);
453 mono_unlink_bblock (cfg, false_bb, false_bb->out_bb [0]);
454 mono_remove_bblock (cfg, true_bb);
455 mono_remove_bblock (cfg, false_bb);
457 /* Merge bb and its successor if possible */
458 if ((bb->out_bb [0]->in_count == 1) && (bb->out_bb [0] != cfg->bb_exit) &&
459 (bb->region == bb->out_bb [0]->region)) {
460 mono_merge_basic_blocks (cfg, bb, bb->out_bb [0]);
465 /* Look for the IR code generated from if (cond) <var> <- <a>
474 if ((bb2->in_count == 1 && bb2->out_count == 1 && bb2->out_bb [0] == bb1) ||
475 (bb1->in_count == 1 && bb1->out_count == 1 && bb1->out_bb [0] == bb2)) {
476 MonoInst *compare, *branch, *ins1, *cmov, *tmp;
481 MonoBasicBlock *next_bb, *code_bb;
483 /* code_bb is the bblock containing code, next_bb is the successor bblock */
484 if (bb2->in_count == 1 && bb2->out_count == 1 && bb2->out_bb [0] == bb1) {
492 ins1 = code_bb->code;
497 /* Check that code_bb is simple */
499 for (tmp = ins1->next; tmp; tmp = tmp->next)
500 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_BR)))
506 /* We move ins1 before the compare so it should have no side effect */
507 if (!MONO_INS_HAS_NO_SIDE_EFFECT (ins1))
510 if (bb->last_ins && bb->last_ins->opcode == OP_BR_REG)
513 /* Find the compare instruction */
515 if (!bb->last_ins || !bb->last_ins->prev)
517 branch = bb->last_ins;
518 compare = branch->prev;
520 if (!MONO_IS_COND_BRANCH_OP (branch))
521 /* This can happen if a cond branch is optimized away */
525 comp_type = mono_opcode_to_type (branch->opcode, compare->opcode);
526 if (!((comp_type == CMP_TYPE_I) || (comp_type == CMP_TYPE_L)))
530 /* ins->type might not be set */
531 if (INS_INFO (ins1->opcode) [MONO_INST_DEST] != 'i')
535 if (cfg->ret && ins1->dreg == cfg->ret->dreg)
538 if (cfg->verbose_level > 2) {
539 printf ("\tBranch -> CMove optimization (2) in BB%d on\n", bb->block_num);
540 printf ("\t\t"); mono_print_ins (compare);
541 printf ("\t\t"); mono_print_ins (compare->next);
542 printf ("\t\t"); mono_print_ins (ins1);
549 tmp_reg = mono_alloc_dreg (cfg, STACK_I4);
552 /* Rewrite ins1 to emit to tmp_reg */
553 ins1->dreg = tmp_reg;
555 /* Remove ins1 from code_bb */
556 MONO_REMOVE_INS (code_bb, ins1);
558 /* Move ins1 before the comparison */
559 mono_bblock_insert_before_ins (bb, compare, ins1);
561 /* Add cmov instruction */
562 MONO_INST_NEW (cfg, cmov, OP_NOP);
565 cmov->sreg2 = tmp_reg;
566 cond = mono_opcode_to_cond (branch->opcode);
567 if (branch->inst_false_bb == code_bb)
568 cond = mono_negate_cond (cond);
569 switch (mono_opcode_to_type (branch->opcode, compare->opcode)) {
571 cmov->opcode = int_cmov_opcodes [cond];
574 cmov->opcode = long_cmov_opcodes [cond];
577 g_assert_not_reached ();
579 mono_bblock_insert_after_ins (bb, compare, cmov);
581 /* Rewrite the branch */
582 branch->opcode = OP_BR;
583 branch->inst_target_bb = next_bb;
584 mono_link_bblock (cfg, bb, branch->inst_target_bb);
586 /* Nullify the branch at the end of code_bb */
588 branch = code_bb->code;
589 MONO_DELETE_INS (code_bb, branch);
592 /* Reorder bblocks */
593 mono_unlink_bblock (cfg, bb, code_bb);
594 mono_unlink_bblock (cfg, code_bb, next_bb);
596 /* Merge bb and its successor if possible */
597 if ((bb->out_bb [0]->in_count == 1) && (bb->out_bb [0] != cfg->bb_exit) &&
598 (bb->region == bb->out_bb [0]->region)) {
599 mono_merge_basic_blocks (cfg, bb, bb->out_bb [0]);
602 * bbn might have fallen through to the next bb without a branch,
603 * have to add one now (#474718).
604 * FIXME: Maybe need to do this more generally in
605 * merge_basic_blocks () ?
607 if (!(bb->last_ins && MONO_IS_BRANCH_OP (bb->last_ins)) && bb->out_count) {
608 MONO_INST_NEW (cfg, ins1, OP_BR);
609 ins1->inst_target_bb = bb->out_bb [0];
610 MONO_ADD_INS (bb, ins1);
618 * Optimize checks like: if (v < 0 || v > limit) by changing then to unsigned
619 * compares. This isn't really if conversion, but it easier to do here than in
620 * optimize_branches () since the IR is already optimized.
622 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
623 MonoBasicBlock *bb1, *bb2, *true_bb, *false_bb, *next_bb;
624 MonoInst *branch1, *branch2, *compare1, *ins;
626 /* Look for the IR code generated from if (<var> < 0 || v > <limit>)
627 * after branch opts which is:
632 * icompare_imm R [<limit>]
635 if (!(bb->out_count == 2 && !bb->extended))
638 bb1 = bb->out_bb [0];
639 bb2 = bb->out_bb [1];
641 // FIXME: Add more cases
643 /* Check structure */
644 if (!(bb1->in_count == 2 && bb1->in_bb [0] == bb && bb1->in_bb [1] == bb2 && bb2->in_count == 1 && bb2->out_count == 2))
649 /* Check first branch */
650 branch1 = bb->last_ins;
651 if (!(branch1 && ((branch1->opcode == OP_IBLT) || (branch1->opcode == OP_LBLT)) && (branch1->inst_false_bb == next_bb)))
654 true_bb = branch1->inst_true_bb;
656 /* Check second branch */
657 branch2 = next_bb->last_ins;
661 /* mcs sometimes generates inverted branches */
662 if (((branch2->opcode == OP_IBGT) || (branch2->opcode == OP_LBGT)) && branch2->inst_true_bb == branch1->inst_true_bb)
663 false_bb = branch2->inst_false_bb;
664 else if (((branch2->opcode == OP_IBLE) || (branch2->opcode == OP_LBLE)) && branch2->inst_false_bb == branch1->inst_true_bb)
665 false_bb = branch2->inst_true_bb;
669 /* Check first compare */
670 compare1 = bb->last_ins->prev;
671 if (!(compare1 && ((compare1->opcode == OP_ICOMPARE_IMM) || (compare1->opcode == OP_LCOMPARE_IMM)) && compare1->inst_imm == 0))
674 /* Check second bblock */
678 if (((ins->opcode == OP_ICOMPARE_IMM) || (ins->opcode == OP_LCOMPARE_IMM)) && ins->sreg1 == compare1->sreg1 && ins->next == branch2) {
679 /* The second arg must be positive */
680 if (ins->inst_imm < 0)
682 } else if (((ins->opcode == OP_LDLEN) || (ins->opcode == OP_STRLEN)) && ins->dreg != compare1->sreg1 && ins->next && ins->next->opcode == OP_ICOMPARE && ins->next->sreg1 == compare1->sreg1 && ins->next->sreg2 == ins->dreg && ins->next->next == branch2) {
683 /* Another common case: if (index < 0 || index > arr.Length) */
688 if (cfg->verbose_level > 2) {
689 printf ("\tSigned->unsigned compare optimization in BB%d on\n", bb->block_num);
690 printf ("\t\t"); mono_print_ins (compare1);
691 printf ("\t\t"); mono_print_ins (compare1->next);
692 printf ("\t\t"); mono_print_ins (ins);
695 /* Rewrite the first compare+branch */
696 MONO_DELETE_INS (bb, compare1);
697 branch1->opcode = OP_BR;
698 mono_unlink_bblock (cfg, bb, branch1->inst_true_bb);
699 mono_unlink_bblock (cfg, bb, branch1->inst_false_bb);
700 branch1->inst_target_bb = next_bb;
701 mono_link_bblock (cfg, bb, next_bb);
703 /* Rewrite the second branch */
704 branch2->opcode = br_to_br_un (branch2->opcode);
706 mono_merge_basic_blocks (cfg, bb, next_bb);
710 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
711 MonoBasicBlock *bb1, *bb2;
712 MonoInst *prev, *compare, *branch, *ins1, *ins2, *cmov, *move, *tmp;
713 gboolean simple, ret;
717 /* Look for the IR code generated from if (cond) <var> <- <a>
718 * after branch opts which is:
725 if (!(bb->out_count == 1 && bb->extended && bb->code && bb->code->next && bb->code->next->next))
728 mono_print_bb (bb, "");
730 /* Find the compare instruction */
734 while (compare->next->next && compare->next->next != bb->last_ins) {
736 compare = compare->next;
738 branch = compare->next;
739 if (!MONO_IS_COND_BRANCH_OP (branch))
745 if (cfg->opt & MONO_OPT_BRANCH)
746 mono_optimize_branches (cfg);
747 /* Merging bblocks could make some variables local */
748 mono_handle_global_vregs (cfg);
749 if (cfg->opt & (MONO_OPT_CONSPROP | MONO_OPT_COPYPROP))
750 mono_local_cprop (cfg);
751 if (cfg->opt & MONO_OPT_DEADCE)
752 mono_local_deadce (cfg);
758 mono_nullify_basic_block (MonoBasicBlock *bb)
765 bb->code = bb->last_ins = NULL;
770 replace_out_block (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl)
774 for (i = 0; i < bb->out_count; i++) {
775 MonoBasicBlock *ob = bb->out_bb [i];
778 if (bb->out_count > 1) {
779 bb->out_bb [i] = bb->out_bb [bb->out_count - 1];
783 bb->out_bb [i] = repl;
790 replace_in_block (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl)
794 for (i = 0; i < bb->in_count; i++) {
795 MonoBasicBlock *ib = bb->in_bb [i];
798 if (bb->in_count > 1) {
799 bb->in_bb [i] = bb->in_bb [bb->in_count - 1];
803 bb->in_bb [i] = repl;
810 replace_out_block_in_code (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl) {
813 for (ins = bb->code; ins != NULL; ins = ins->next) {
814 switch (ins->opcode) {
816 if (ins->inst_target_bb == orig)
817 ins->inst_target_bb = repl;
819 case OP_CALL_HANDLER:
820 if (ins->inst_target_bb == orig)
821 ins->inst_target_bb = repl;
825 int n = GPOINTER_TO_INT (ins->klass);
826 for (i = 0; i < n; i++ ) {
827 if (ins->inst_many_bb [i] == orig)
828 ins->inst_many_bb [i] = repl;
833 if (MONO_IS_COND_BRANCH_OP (ins)) {
834 if (ins->inst_true_bb == orig)
835 ins->inst_true_bb = repl;
836 if (ins->inst_false_bb == orig)
837 ins->inst_false_bb = repl;
838 } else if (MONO_IS_JUMP_TABLE (ins)) {
840 MonoJumpInfoBBTable *table = MONO_JUMP_TABLE_FROM_INS (ins);
841 for (i = 0; i < table->table_size; i++ ) {
842 if (table->table [i] == orig)
843 table->table [i] = repl;
853 * Check if a bb is useless (is just made of NOPs and ends with an
854 * unconditional branch, or nothing).
855 * If it is so, unlink it from the CFG and nullify it, and return TRUE.
856 * Otherwise, return FALSE;
859 remove_block_if_useless (MonoCompile *cfg, MonoBasicBlock *bb, MonoBasicBlock *previous_bb) {
860 MonoBasicBlock *target_bb = NULL;
863 /* Do not touch handlers */
864 if (bb->region != -1) {
865 bb->not_useless = TRUE;
869 MONO_BB_FOR_EACH_INS (bb, inst) {
870 switch (inst->opcode) {
874 target_bb = inst->inst_target_bb;
877 bb->not_useless = TRUE;
882 if (target_bb == NULL) {
883 if ((bb->out_count == 1) && (bb->out_bb [0] == bb->next_bb)) {
884 target_bb = bb->next_bb;
886 /* Do not touch empty BBs that do not "fall through" to their next BB (like the exit BB) */
891 /* Do not touch BBs following a switch (they are the "default" branch) */
892 if ((previous_bb->last_ins != NULL) && (previous_bb->last_ins->opcode == OP_SWITCH)) {
896 /* Do not touch BBs following the entry BB and jumping to something that is not */
897 /* thiry "next" bb (the entry BB cannot contain the branch) */
898 if ((previous_bb == cfg->bb_entry) && (bb->next_bb != target_bb)) {
903 * Do not touch BBs following a try block as the code in
904 * mini_method_compile needs them to compute the length of the try block.
906 if (MONO_BBLOCK_IS_IN_REGION (previous_bb, MONO_REGION_TRY))
909 /* Check that there is a target BB, and that bb is not an empty loop (Bug 75061) */
910 if ((target_bb != NULL) && (target_bb != bb)) {
913 if (cfg->verbose_level > 1) {
914 printf ("remove_block_if_useless, removed BB%d\n", bb->block_num);
917 /* unlink_bblock () modifies the bb->in_bb array so can't use a for loop here */
918 while (bb->in_count) {
919 MonoBasicBlock *in_bb = bb->in_bb [0];
920 mono_unlink_bblock (cfg, in_bb, bb);
921 mono_link_bblock (cfg, in_bb, target_bb);
922 replace_out_block_in_code (in_bb, bb, target_bb);
925 mono_unlink_bblock (cfg, bb, target_bb);
926 if (previous_bb != cfg->bb_entry && mono_bb_is_fall_through (cfg, previous_bb)) {
927 for (i = 0; i < previous_bb->out_count; i++) {
928 if (previous_bb->out_bb [i] == target_bb) {
930 MONO_INST_NEW (cfg, jump, OP_BR);
931 MONO_ADD_INS (previous_bb, jump);
932 jump->cil_code = previous_bb->cil_code;
933 jump->inst_target_bb = target_bb;
939 previous_bb->next_bb = bb->next_bb;
940 mono_nullify_basic_block (bb);
949 mono_merge_basic_blocks (MonoCompile *cfg, MonoBasicBlock *bb, MonoBasicBlock *bbn)
952 MonoBasicBlock *prev_bb;
955 bb->has_array_access |= bbn->has_array_access;
956 bb->extended |= bbn->extended;
958 mono_unlink_bblock (cfg, bb, bbn);
959 for (i = 0; i < bbn->out_count; ++i)
960 mono_link_bblock (cfg, bb, bbn->out_bb [i]);
961 while (bbn->out_count)
962 mono_unlink_bblock (cfg, bbn, bbn->out_bb [0]);
964 /* Handle the branch at the end of the bb */
965 if (bb->has_call_handler) {
966 for (inst = bb->code; inst != NULL; inst = inst->next) {
967 if (inst->opcode == OP_CALL_HANDLER) {
968 g_assert (inst->inst_target_bb == bbn);
973 if (bb->has_jump_table) {
974 for (inst = bb->code; inst != NULL; inst = inst->next) {
975 if (MONO_IS_JUMP_TABLE (inst)) {
977 MonoJumpInfoBBTable *table = MONO_JUMP_TABLE_FROM_INS (inst);
978 for (i = 0; i < table->table_size; i++ ) {
979 /* Might be already NULL from a previous merge */
980 if (table->table [i])
981 g_assert (table->table [i] == bbn);
982 table->table [i] = NULL;
984 /* Can't nullify this as later instructions depend on it */
988 if (bb->last_ins && MONO_IS_COND_BRANCH_OP (bb->last_ins)) {
989 g_assert (bb->last_ins->inst_false_bb == bbn);
990 bb->last_ins->inst_false_bb = NULL;
992 } else if (bb->last_ins && MONO_IS_BRANCH_OP (bb->last_ins)) {
993 NULLIFY_INS (bb->last_ins);
996 bb->has_call_handler |= bbn->has_call_handler;
997 bb->has_jump_table |= bbn->has_jump_table;
1001 bb->last_ins->next = bbn->code;
1002 bbn->code->prev = bb->last_ins;
1003 bb->last_ins = bbn->last_ins;
1006 bb->code = bbn->code;
1007 bb->last_ins = bbn->last_ins;
1010 for (prev_bb = cfg->bb_entry; prev_bb && prev_bb->next_bb != bbn; prev_bb = prev_bb->next_bb)
1013 prev_bb->next_bb = bbn->next_bb;
1015 /* bbn might not be in the bb list yet */
1016 if (bb->next_bb == bbn)
1017 bb->next_bb = bbn->next_bb;
1019 mono_nullify_basic_block (bbn);
1022 * If bbn fell through to its next bblock, have to add a branch, since bb
1023 * will not fall though to the same bblock (#513931).
1025 if (bb->last_ins && bb->out_count == 1 && bb->out_bb [0] != bb->next_bb && !MONO_IS_BRANCH_OP (bb->last_ins)) {
1026 MONO_INST_NEW (cfg, inst, OP_BR);
1027 inst->inst_target_bb = bb->out_bb [0];
1028 MONO_ADD_INS (bb, inst);
1033 move_basic_block_to_end (MonoCompile *cfg, MonoBasicBlock *bb)
1035 MonoBasicBlock *bbn, *next;
1039 /* Find the previous */
1040 for (bbn = cfg->bb_entry; bbn->next_bb && bbn->next_bb != bb; bbn = bbn->next_bb)
1043 bbn->next_bb = bb->next_bb;
1047 for (bbn = cfg->bb_entry; bbn->next_bb; bbn = bbn->next_bb)
1053 if (next && (!bb->last_ins || ((bb->last_ins->opcode != OP_NOT_REACHED) && (bb->last_ins->opcode != OP_BR) && (bb->last_ins->opcode != OP_BR_REG) && (!MONO_IS_COND_BRANCH_OP (bb->last_ins))))) {
1056 MONO_INST_NEW (cfg, ins, OP_BR);
1057 MONO_ADD_INS (bb, ins);
1058 mono_link_bblock (cfg, bb, next);
1059 ins->inst_target_bb = next;
1064 * mono_remove_block:
1066 * Remove BB from the control flow graph
1069 mono_remove_bblock (MonoCompile *cfg, MonoBasicBlock *bb)
1071 MonoBasicBlock *tmp_bb;
1073 for (tmp_bb = cfg->bb_entry; tmp_bb && tmp_bb->next_bb != bb; tmp_bb = tmp_bb->next_bb)
1077 tmp_bb->next_bb = bb->next_bb;
1081 mono_remove_critical_edges (MonoCompile *cfg)
1084 MonoBasicBlock *previous_bb;
1086 if (cfg->verbose_level > 3) {
1087 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1089 printf ("remove_critical_edges, BEFORE BB%d (in:", bb->block_num);
1090 for (i = 0; i < bb->in_count; i++) {
1091 printf (" %d", bb->in_bb [i]->block_num);
1094 for (i = 0; i < bb->out_count; i++) {
1095 printf (" %d", bb->out_bb [i]->block_num);
1098 if (bb->last_ins != NULL) {
1100 mono_print_ins (bb->last_ins);
1106 for (previous_bb = cfg->bb_entry, bb = previous_bb->next_bb; bb != NULL; previous_bb = previous_bb->next_bb, bb = bb->next_bb) {
1107 if (bb->in_count > 1) {
1109 for (in_bb_index = 0; in_bb_index < bb->in_count; in_bb_index++) {
1110 MonoBasicBlock *in_bb = bb->in_bb [in_bb_index];
1112 * Have to remove non-critical edges whose source ends with a BR_REG
1113 * ins too, since inserting a computation before the BR_REG could
1114 * overwrite the sreg1 of the ins.
1116 if ((in_bb->out_count > 1) || (in_bb->out_count == 1 && in_bb->last_ins && in_bb->last_ins->opcode == OP_BR_REG)) {
1117 MonoBasicBlock *new_bb = mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoBasicBlock));
1118 new_bb->block_num = cfg->num_bblocks++;
1119 // new_bb->real_offset = bb->real_offset;
1120 new_bb->region = bb->region;
1122 /* Do not alter the CFG while altering the BB list */
1123 if (mono_bb_is_fall_through (cfg, previous_bb)) {
1124 if (previous_bb != cfg->bb_entry) {
1126 /* Make sure previous_bb really falls through bb */
1127 for (i = 0; i < previous_bb->out_count; i++) {
1128 if (previous_bb->out_bb [i] == bb) {
1130 MONO_INST_NEW (cfg, jump, OP_BR);
1131 MONO_ADD_INS (previous_bb, jump);
1132 jump->cil_code = previous_bb->cil_code;
1133 jump->inst_target_bb = bb;
1138 /* We cannot add any inst to the entry BB, so we must */
1139 /* put a new BB in the middle to hold the OP_BR */
1141 MonoBasicBlock *new_bb_after_entry = mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoBasicBlock));
1142 new_bb_after_entry->block_num = cfg->num_bblocks++;
1143 // new_bb_after_entry->real_offset = bb->real_offset;
1144 new_bb_after_entry->region = bb->region;
1146 MONO_INST_NEW (cfg, jump, OP_BR);
1147 MONO_ADD_INS (new_bb_after_entry, jump);
1148 jump->cil_code = bb->cil_code;
1149 jump->inst_target_bb = bb;
1151 mono_unlink_bblock (cfg, previous_bb, bb);
1152 mono_link_bblock (cfg, new_bb_after_entry, bb);
1153 mono_link_bblock (cfg, previous_bb, new_bb_after_entry);
1155 previous_bb->next_bb = new_bb_after_entry;
1156 previous_bb = new_bb_after_entry;
1158 if (cfg->verbose_level > 2) {
1159 printf ("remove_critical_edges, added helper BB%d jumping to BB%d\n", new_bb_after_entry->block_num, bb->block_num);
1164 /* Insert new_bb in the BB list */
1165 previous_bb->next_bb = new_bb;
1166 new_bb->next_bb = bb;
1167 previous_bb = new_bb;
1169 /* Setup in_bb and out_bb */
1170 new_bb->in_bb = mono_mempool_alloc ((cfg)->mempool, sizeof (MonoBasicBlock*));
1171 new_bb->in_bb [0] = in_bb;
1172 new_bb->in_count = 1;
1173 new_bb->out_bb = mono_mempool_alloc ((cfg)->mempool, sizeof (MonoBasicBlock*));
1174 new_bb->out_bb [0] = bb;
1175 new_bb->out_count = 1;
1177 /* Relink in_bb and bb to (from) new_bb */
1178 replace_out_block (in_bb, bb, new_bb);
1179 replace_out_block_in_code (in_bb, bb, new_bb);
1180 replace_in_block (bb, in_bb, new_bb);
1182 if (cfg->verbose_level > 2) {
1183 printf ("remove_critical_edges, removed critical edge from BB%d to BB%d (added BB%d)\n", in_bb->block_num, bb->block_num, new_bb->block_num);
1190 if (cfg->verbose_level > 3) {
1191 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1193 printf ("remove_critical_edges, AFTER BB%d (in:", bb->block_num);
1194 for (i = 0; i < bb->in_count; i++) {
1195 printf (" %d", bb->in_bb [i]->block_num);
1198 for (i = 0; i < bb->out_count; i++) {
1199 printf (" %d", bb->out_bb [i]->block_num);
1202 if (bb->last_ins != NULL) {
1204 mono_print_ins (bb->last_ins);
1212 * Optimizes the branches on the Control Flow Graph
1216 mono_optimize_branches (MonoCompile *cfg)
1218 int i, changed = FALSE;
1219 MonoBasicBlock *bb, *bbn;
1220 guint32 niterations;
1223 * Some crazy loops could cause the code below to go into an infinite
1224 * loop, see bug #53003 for an example. To prevent this, we put an upper
1225 * bound on the number of iterations.
1227 if (cfg->num_bblocks > 1000)
1228 niterations = cfg->num_bblocks * 2;
1233 MonoBasicBlock *previous_bb;
1237 /* we skip the entry block (exit is handled specially instead ) */
1238 for (previous_bb = cfg->bb_entry, bb = cfg->bb_entry->next_bb; bb; previous_bb = bb, bb = bb->next_bb) {
1239 /* dont touch code inside exception clauses */
1240 if (bb->region != -1)
1243 if (!bb->not_useless && remove_block_if_useless (cfg, bb, previous_bb)) {
1248 if ((bbn = bb->next_bb) && bbn->in_count == 0 && bbn != cfg->bb_exit && bb->region == bbn->region) {
1249 if (cfg->verbose_level > 2)
1250 g_print ("nullify block triggered %d\n", bbn->block_num);
1252 bb->next_bb = bbn->next_bb;
1254 for (i = 0; i < bbn->out_count; i++)
1255 replace_in_block (bbn->out_bb [i], bbn, NULL);
1257 mono_nullify_basic_block (bbn);
1261 if (bb->out_count == 1) {
1262 bbn = bb->out_bb [0];
1264 /* conditional branches where true and false targets are the same can be also replaced with OP_BR */
1265 if (bb->last_ins && (bb->last_ins->opcode != OP_BR) && MONO_IS_COND_BRANCH_OP (bb->last_ins)) {
1266 bb->last_ins->opcode = OP_BR;
1267 bb->last_ins->inst_target_bb = bb->last_ins->inst_true_bb;
1269 if (cfg->verbose_level > 2)
1270 g_print ("cond branch removal triggered in %d %d\n", bb->block_num, bb->out_count);
1273 if (bb->region == bbn->region && bb->next_bb == bbn) {
1274 /* the block are in sequence anyway ... */
1276 /* branches to the following block can be removed */
1277 if (bb->last_ins && bb->last_ins->opcode == OP_BR) {
1278 bb->last_ins->opcode = OP_NOP;
1280 if (cfg->verbose_level > 2)
1281 g_print ("br removal triggered %d -> %d\n", bb->block_num, bbn->block_num);
1284 if (bbn->in_count == 1 && !bb->extended) {
1285 if (bbn != cfg->bb_exit) {
1286 if (cfg->verbose_level > 2)
1287 g_print ("block merge triggered %d -> %d\n", bb->block_num, bbn->block_num);
1288 mono_merge_basic_blocks (cfg, bb, bbn);
1293 //mono_print_bb_code (bb);
1298 if ((bbn = bb->next_bb) && bbn->in_count == 0 && bbn != cfg->bb_exit && bb->region == bbn->region) {
1299 if (cfg->verbose_level > 2) {
1300 g_print ("nullify block triggered %d\n", bbn->block_num);
1302 bb->next_bb = bbn->next_bb;
1304 for (i = 0; i < bbn->out_count; i++)
1305 replace_in_block (bbn->out_bb [i], bbn, NULL);
1307 mono_nullify_basic_block (bbn);
1312 if (bb->out_count == 1) {
1313 bbn = bb->out_bb [0];
1315 if (bb->last_ins && bb->last_ins->opcode == OP_BR) {
1316 bbn = bb->last_ins->inst_target_bb;
1317 if (bb->region == bbn->region && bbn->code && bbn->code->opcode == OP_BR &&
1318 bbn->code->inst_target_bb != bbn &&
1319 bbn->code->inst_target_bb->region == bb->region) {
1321 if (cfg->verbose_level > 2)
1322 g_print ("branch to branch triggered %d -> %d -> %d\n", bb->block_num, bbn->block_num, bbn->code->inst_target_bb->block_num);
1324 replace_in_block (bbn, bb, NULL);
1325 replace_out_block (bb, bbn, bbn->code->inst_target_bb);
1326 mono_link_bblock (cfg, bb, bbn->code->inst_target_bb);
1327 bb->last_ins->inst_target_bb = bbn->code->inst_target_bb;
1332 } else if (bb->out_count == 2) {
1333 if (bb->last_ins && MONO_IS_COND_BRANCH_NOFP (bb->last_ins)) {
1335 MonoBasicBlock *taken_branch_target = NULL, *untaken_branch_target = NULL;
1337 if (bb->last_ins->flags & MONO_INST_CFOLD_TAKEN)
1338 branch_result = BRANCH_TAKEN;
1339 else if (bb->last_ins->flags & MONO_INST_CFOLD_NOT_TAKEN)
1340 branch_result = BRANCH_NOT_TAKEN;
1342 branch_result = BRANCH_UNDEF;
1344 if (branch_result == BRANCH_TAKEN) {
1345 taken_branch_target = bb->last_ins->inst_true_bb;
1346 untaken_branch_target = bb->last_ins->inst_false_bb;
1347 } else if (branch_result == BRANCH_NOT_TAKEN) {
1348 taken_branch_target = bb->last_ins->inst_false_bb;
1349 untaken_branch_target = bb->last_ins->inst_true_bb;
1351 if (taken_branch_target) {
1352 /* if mono_eval_cond_branch () is ever taken to handle
1353 * non-constant values to compare, issue a pop here.
1355 bb->last_ins->opcode = OP_BR;
1356 bb->last_ins->inst_target_bb = taken_branch_target;
1358 mono_unlink_bblock (cfg, bb, untaken_branch_target);
1362 bbn = bb->last_ins->inst_true_bb;
1363 if (bb->region == bbn->region && bbn->code && bbn->code->opcode == OP_BR &&
1364 bbn->code->inst_target_bb->region == bb->region) {
1365 if (cfg->verbose_level > 2)
1366 g_print ("cbranch1 to branch triggered %d -> (%d) %d (0x%02x)\n",
1367 bb->block_num, bbn->block_num, bbn->code->inst_target_bb->block_num,
1371 * Unlink, then relink bblocks to avoid various
1372 * tricky situations when the two targets of the branch
1373 * are equal, or will become equal after the change.
1375 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1376 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1378 bb->last_ins->inst_true_bb = bbn->code->inst_target_bb;
1380 mono_link_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1381 mono_link_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1387 bbn = bb->last_ins->inst_false_bb;
1388 if (bbn && bb->region == bbn->region && bbn->code && bbn->code->opcode == OP_BR &&
1389 bbn->code->inst_target_bb->region == bb->region) {
1390 if (cfg->verbose_level > 2)
1391 g_print ("cbranch2 to branch triggered %d -> (%d) %d (0x%02x)\n",
1392 bb->block_num, bbn->block_num, bbn->code->inst_target_bb->block_num,
1395 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1396 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1398 bb->last_ins->inst_false_bb = bbn->code->inst_target_bb;
1400 mono_link_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1401 mono_link_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1407 bbn = bb->last_ins->inst_false_bb;
1409 * If bb is an extended bb, it could contain an inside branch to bbn.
1410 * FIXME: Enable the optimization if that is not true.
1411 * If bblocks_linked () is true, then merging bb and bbn
1412 * would require addition of an extra branch at the end of bbn
1413 * slowing down loops.
1415 if (bbn && bb->region == bbn->region && bbn->in_count == 1 && cfg->enable_extended_bblocks && bbn != cfg->bb_exit && !bb->extended && !bbn->out_of_line && !mono_bblocks_linked (bbn, bb)) {
1416 g_assert (bbn->in_bb [0] == bb);
1417 if (cfg->verbose_level > 2)
1418 g_print ("merge false branch target triggered BB%d -> BB%d\n", bb->block_num, bbn->block_num);
1419 mono_merge_basic_blocks (cfg, bb, bbn);
1425 if (bb->last_ins && MONO_IS_COND_BRANCH_NOFP (bb->last_ins)) {
1426 if (bb->last_ins->inst_false_bb && bb->last_ins->inst_false_bb->out_of_line && (bb->region == bb->last_ins->inst_false_bb->region) && !cfg->disable_out_of_line_bblocks) {
1427 /* Reverse the branch */
1428 bb->last_ins->opcode = mono_reverse_branch_op (bb->last_ins->opcode);
1429 bbn = bb->last_ins->inst_false_bb;
1430 bb->last_ins->inst_false_bb = bb->last_ins->inst_true_bb;
1431 bb->last_ins->inst_true_bb = bbn;
1433 move_basic_block_to_end (cfg, bb->last_ins->inst_true_bb);
1434 if (cfg->verbose_level > 2)
1435 g_print ("cbranch to throw block triggered %d.\n",
1441 } while (changed && (niterations > 0));
1444 #endif /* DISABLE_JIT */