3 * Branch optimizations support
6 * Patrik Torstensson (Patrik.Torstesson at gmail.com)
8 * (C) 2005 Ximian, Inc. http://www.ximian.com
9 * Copyright 2011 Xamarin Inc. http://www.xamarin.com
10 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
14 #include <mono/utils/mono-compiler.h>
20 * Returns true if @bb is a basic block which falls through the next block.
21 * TODO verify if it helps to check if the bb last ins is a branch to its successor.
24 mono_bb_is_fall_through (MonoCompile *cfg, MonoBasicBlock *bb)
26 return bb->next_bb && bb->next_bb->region == bb->region && /*fall throught between regions is not really interesting or useful*/
27 (bb->last_ins == NULL || !MONO_IS_BRANCH_OP (bb->last_ins)); /*and the last op can't be a branch too*/
31 * Used by the arch code to replace the exception handling
32 * with a direct branch. This is safe to do if the
33 * exception object isn't used, no rethrow statement and
34 * no filter statement (verify).
38 mono_branch_optimize_exception_target (MonoCompile *cfg, MonoBasicBlock *bb, const char * exname)
40 MonoMethodHeader *header = cfg->header;
41 MonoExceptionClause *clause;
45 if (!(cfg->opt & MONO_OPT_EXCEPTION))
48 if (bb->region == -1 || !MONO_BBLOCK_IS_IN_REGION (bb, MONO_REGION_TRY))
51 exclass = mono_class_load_from_name (mono_get_corlib (), "System", exname);
52 /* search for the handler */
53 for (i = 0; i < header->num_clauses; ++i) {
54 clause = &header->clauses [i];
55 if (MONO_OFFSET_IN_CLAUSE (clause, bb->real_offset)) {
56 if (clause->flags == MONO_EXCEPTION_CLAUSE_NONE && clause->data.catch_class && mono_class_is_assignable_from (clause->data.catch_class, exclass)) {
59 /* get the basic block for the handler and
60 * check if the exception object is used.
61 * Flag is set during method_to_ir due to
62 * pop-op is optmized away in codegen (burg).
64 tbb = cfg->cil_offset_to_bb [clause->handler_offset];
65 if (tbb && tbb->flags & BB_EXCEPTION_DEAD_OBJ && !(tbb->flags & BB_EXCEPTION_UNSAFE)) {
66 MonoBasicBlock *targetbb = tbb;
67 gboolean unsafe = FALSE;
69 /* Check if this catch clause is ok to optimize by
70 * looking for the BB_EXCEPTION_UNSAFE in every BB that
71 * belongs to the same region.
73 * UNSAFE flag is set during method_to_ir (OP_RETHROW)
75 while (!unsafe && tbb->next_bb && tbb->region == tbb->next_bb->region) {
76 if (tbb->next_bb->flags & BB_EXCEPTION_UNSAFE) {
86 /* Create dummy inst to allow easier integration in
87 * arch dependent code (opcode ignored)
89 MONO_INST_NEW (cfg, jump, OP_BR);
91 /* Allocate memory for our branch target */
92 jump->inst_i1 = (MonoInst *)mono_mempool_alloc0 (cfg->mempool, sizeof (MonoInst));
93 jump->inst_true_bb = targetbb;
95 if (cfg->verbose_level > 2)
96 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);
103 /* Branching to an outer clause could skip inner clauses */
107 /* Branching to an outer clause could skip inner clauses */
116 static const int int_cmov_opcodes [] = {
129 static const int long_cmov_opcodes [] = {
142 static G_GNUC_UNUSED int
143 br_to_br_un (int opcode)
159 g_assert_not_reached ();
167 * Replace INS with its decomposition which is stored in a series of bblocks starting
168 * at FIRST_BB and ending at LAST_BB. On enter, PREV points to the predecessor of INS.
169 * On return, it will be set to the last ins of the decomposition.
172 mono_replace_ins (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *ins, MonoInst **prev, MonoBasicBlock *first_bb, MonoBasicBlock *last_bb)
174 MonoInst *next = ins->next;
176 if (next && next->opcode == OP_NOP) {
177 /* Avoid NOPs following branches */
178 ins->next = next->next;
182 if (first_bb == last_bb) {
184 * Only one replacement bb, merge the code into
188 /* Delete links between the first_bb and its successors */
189 while (first_bb->out_count)
190 mono_unlink_bblock (cfg, first_bb, first_bb->out_bb [0]);
194 (*prev)->next = first_bb->code;
195 first_bb->code->prev = (*prev);
197 bb->code = first_bb->code;
201 last_bb->last_ins->next = next;
203 next->prev = last_bb->last_ins;
205 bb->last_ins = last_bb->last_ins;
206 *prev = last_bb->last_ins;
207 bb->has_array_access |= first_bb->has_array_access;
210 MonoBasicBlock **tmp_bblocks, *tmp;
215 /* Set region/real_offset */
216 for (tmp = first_bb; tmp; tmp = tmp->next_bb) {
217 tmp->region = bb->region;
218 tmp->real_offset = bb->real_offset;
221 /* Split the original bb */
223 ins->next->prev = NULL;
227 /* Merge the second part of the original bb into the last bb */
228 if (last_bb->last_ins) {
229 last_bb->last_ins->next = next;
231 next->prev = last_bb->last_ins;
233 last_bb->code = next;
235 last_bb->has_array_access |= bb->has_array_access;
238 for (last = next; last->next != NULL; last = last->next)
240 last_bb->last_ins = last;
243 for (i = 0; i < bb->out_count; ++i)
244 mono_link_bblock (cfg, last_bb, bb->out_bb [i]);
246 /* Merge the first (dummy) bb to the original bb */
248 (*prev)->next = first_bb->code;
249 first_bb->code->prev = (*prev);
251 bb->code = first_bb->code;
253 bb->last_ins = first_bb->last_ins;
254 bb->has_array_access |= first_bb->has_array_access;
256 /* Delete the links between the original bb and its successors */
257 tmp_bblocks = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoBasicBlock*) * bb->out_count);
258 memcpy (tmp_bblocks, bb->out_bb, sizeof (MonoBasicBlock*) * bb->out_count);
259 count = bb->out_count;
260 for (i = 0; i < count; ++i)
261 mono_unlink_bblock (cfg, bb, tmp_bblocks [i]);
263 /* Add links between the original bb and the first_bb's successors */
264 for (i = 0; i < first_bb->out_count; ++i) {
265 MonoBasicBlock *out_bb = first_bb->out_bb [i];
267 mono_link_bblock (cfg, bb, out_bb);
269 /* Delete links between the first_bb and its successors */
270 for (i = 0; i < bb->out_count; ++i) {
271 MonoBasicBlock *out_bb = bb->out_bb [i];
273 mono_unlink_bblock (cfg, first_bb, out_bb);
275 last_bb->next_bb = bb->next_bb;
276 bb->next_bb = first_bb->next_bb;
283 mono_if_conversion (MonoCompile *cfg)
285 #ifdef MONO_ARCH_HAVE_CMOV_OPS
287 gboolean changed = FALSE;
288 int filter = FILTER_NOP | FILTER_IL_SEQ_POINT;
290 if (!(cfg->opt & MONO_OPT_CMOV))
293 // FIXME: Make this work with extended bblocks
296 * This pass requires somewhat optimized IR code so it should be run after
297 * local cprop/deadce. Also, it should be run before dominator computation, since
298 * it changes control flow.
300 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
301 MonoBasicBlock *bb1, *bb2;
304 /* Look for the IR code generated from cond ? a : b
315 if (!(bb->out_count == 2 && !bb->extended))
318 bb1 = bb->out_bb [0];
319 bb2 = bb->out_bb [1];
321 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]) {
322 MonoInst *compare, *branch, *ins1, *ins2, *cmov, *move, *tmp;
323 MonoBasicBlock *true_bb, *false_bb;
324 gboolean simple, ret;
328 branch = mono_bb_last_inst (bb, filter);
330 if (!branch || branch->opcode == OP_BR_REG || branch->opcode == OP_BR)
333 /* Find the compare instruction */
334 compare = mono_inst_prev (branch, filter);
338 if (!MONO_IS_COND_BRANCH_OP (branch))
339 /* This can happen if a cond branch is optimized away */
342 true_bb = branch->inst_true_bb;
343 false_bb = branch->inst_false_bb;
346 * Check that bb1 and bb2 are 'simple' and both assign to the same
349 /* FIXME: Get rid of the nops earlier */
350 ins1 = mono_bb_first_inst (true_bb, filter);
351 ins2 = mono_bb_first_inst (false_bb, filter);
353 if (!(ins1 && ins2 && ins1->dreg == ins2->dreg && ins1->dreg != -1))
357 for (tmp = ins1->next; tmp; tmp = tmp->next)
358 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_IL_SEQ_POINT) || (tmp->opcode == OP_BR)))
361 for (tmp = ins2->next; tmp; tmp = tmp->next)
362 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_IL_SEQ_POINT) || (tmp->opcode == OP_BR)))
368 /* We move ins1/ins2 before the compare so they should have no side effect */
369 if (!(MONO_INS_HAS_NO_SIDE_EFFECT (ins1) && MONO_INS_HAS_NO_SIDE_EFFECT (ins2)))
372 /* Moving ins1/ins2 could change the comparison */
374 if (!((compare->sreg1 != ins1->dreg) && (compare->sreg2 != ins1->dreg)))
378 comp_type = mono_opcode_to_type (branch->opcode, compare->opcode);
379 if (!((comp_type == CMP_TYPE_I) || (comp_type == CMP_TYPE_L)))
383 /* ins->type might not be set */
384 if (INS_INFO (ins1->opcode) [MONO_INST_DEST] != 'i')
387 if (cfg->verbose_level > 2) {
388 printf ("\tBranch -> CMove optimization in BB%d on\n", bb->block_num);
389 printf ("\t\t"); mono_print_ins (compare);
390 printf ("\t\t"); mono_print_ins (mono_inst_next (compare, filter));
391 printf ("\t\t"); mono_print_ins (ins1);
392 printf ("\t\t"); mono_print_ins (ins2);
399 /* Assignments to the return register must remain at the end of bbs */
401 ret = ins1->dreg == cfg->ret->dreg;
405 tmp_reg = mono_alloc_dreg (cfg, STACK_I4);
408 /* Rewrite ins1 to emit to tmp_reg */
409 ins1->dreg = tmp_reg;
412 dreg = mono_alloc_dreg (cfg, STACK_I4);
416 /* Remove ins1/ins2 from bb1/bb2 */
417 MONO_REMOVE_INS (true_bb, ins1);
418 MONO_REMOVE_INS (false_bb, ins2);
420 /* Move ins1 and ins2 before the comparison */
421 /* ins1 comes first to avoid ins1 overwriting an argument of ins2 */
422 mono_bblock_insert_before_ins (bb, compare, ins2);
423 mono_bblock_insert_before_ins (bb, ins2, ins1);
425 /* Add cmov instruction */
426 MONO_INST_NEW (cfg, cmov, OP_NOP);
429 cmov->sreg2 = tmp_reg;
430 switch (mono_opcode_to_type (branch->opcode, compare->opcode)) {
432 cmov->opcode = int_cmov_opcodes [mono_opcode_to_cond (branch->opcode)];
435 cmov->opcode = long_cmov_opcodes [mono_opcode_to_cond (branch->opcode)];
438 g_assert_not_reached ();
440 mono_bblock_insert_after_ins (bb, compare, cmov);
443 /* Add an extra move */
444 MONO_INST_NEW (cfg, move, OP_MOVE);
445 move->dreg = cfg->ret->dreg;
447 mono_bblock_insert_after_ins (bb, cmov, move);
450 /* Rewrite the branch */
451 branch->opcode = OP_BR;
452 branch->inst_target_bb = true_bb->out_bb [0];
453 mono_link_bblock (cfg, bb, branch->inst_target_bb);
455 /* Reorder bblocks */
456 mono_unlink_bblock (cfg, bb, true_bb);
457 mono_unlink_bblock (cfg, bb, false_bb);
458 mono_unlink_bblock (cfg, true_bb, true_bb->out_bb [0]);
459 mono_unlink_bblock (cfg, false_bb, false_bb->out_bb [0]);
460 mono_remove_bblock (cfg, true_bb);
461 mono_remove_bblock (cfg, false_bb);
463 /* Merge bb and its successor if possible */
464 if ((bb->out_bb [0]->in_count == 1) && (bb->out_bb [0] != cfg->bb_exit) &&
465 (bb->region == bb->out_bb [0]->region)) {
466 mono_merge_basic_blocks (cfg, bb, bb->out_bb [0]);
471 /* Look for the IR code generated from if (cond) <var> <- <a>
480 if ((bb2->in_count == 1 && bb2->out_count == 1 && bb2->out_bb [0] == bb1) ||
481 (bb1->in_count == 1 && bb1->out_count == 1 && bb1->out_bb [0] == bb2)) {
482 MonoInst *compare, *branch, *ins1, *cmov, *tmp;
487 MonoBasicBlock *next_bb, *code_bb;
489 /* code_bb is the bblock containing code, next_bb is the successor bblock */
490 if (bb2->in_count == 1 && bb2->out_count == 1 && bb2->out_bb [0] == bb1) {
498 ins1 = mono_bb_first_inst (code_bb, filter);
503 /* Check that code_bb is simple */
505 for (tmp = ins1; tmp; tmp = tmp->next)
506 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_IL_SEQ_POINT) || (tmp->opcode == OP_BR)))
512 /* We move ins1 before the compare so it should have no side effect */
513 if (!MONO_INS_HAS_NO_SIDE_EFFECT (ins1))
516 branch = mono_bb_last_inst (bb, filter);
518 if (!branch || branch->opcode == OP_BR_REG)
521 /* Find the compare instruction */
522 compare = mono_inst_prev (branch, filter);
526 if (!MONO_IS_COND_BRANCH_OP (branch))
527 /* This can happen if a cond branch is optimized away */
531 comp_type = mono_opcode_to_type (branch->opcode, compare->opcode);
532 if (!((comp_type == CMP_TYPE_I) || (comp_type == CMP_TYPE_L)))
536 /* ins->type might not be set */
537 if (INS_INFO (ins1->opcode) [MONO_INST_DEST] != 'i')
541 if (cfg->ret && ins1->dreg == cfg->ret->dreg)
544 if (!(cfg->opt & MONO_OPT_DEADCE))
546 * It is possible that dreg is never set before, so we can't use
547 * it as an sreg of the cmov instruction (#582322).
551 if (cfg->verbose_level > 2) {
552 printf ("\tBranch -> CMove optimization (2) in BB%d on\n", bb->block_num);
553 printf ("\t\t"); mono_print_ins (compare);
554 printf ("\t\t"); mono_print_ins (mono_inst_next (compare, filter));
555 printf ("\t\t"); mono_print_ins (ins1);
562 tmp_reg = mono_alloc_dreg (cfg, STACK_I4);
565 /* Rewrite ins1 to emit to tmp_reg */
566 ins1->dreg = tmp_reg;
568 /* Remove ins1 from code_bb */
569 MONO_REMOVE_INS (code_bb, ins1);
571 /* Move ins1 before the comparison */
572 mono_bblock_insert_before_ins (bb, compare, ins1);
574 /* Add cmov instruction */
575 MONO_INST_NEW (cfg, cmov, OP_NOP);
578 cmov->sreg2 = tmp_reg;
579 cond = mono_opcode_to_cond (branch->opcode);
580 if (branch->inst_false_bb == code_bb)
581 cond = mono_negate_cond (cond);
582 switch (mono_opcode_to_type (branch->opcode, compare->opcode)) {
584 cmov->opcode = int_cmov_opcodes [cond];
587 cmov->opcode = long_cmov_opcodes [cond];
590 g_assert_not_reached ();
592 mono_bblock_insert_after_ins (bb, compare, cmov);
594 /* Rewrite the branch */
595 branch->opcode = OP_BR;
596 branch->inst_target_bb = next_bb;
597 mono_link_bblock (cfg, bb, branch->inst_target_bb);
599 /* Nullify the branch at the end of code_bb */
601 branch = code_bb->code;
602 MONO_DELETE_INS (code_bb, branch);
605 /* Reorder bblocks */
606 mono_unlink_bblock (cfg, bb, code_bb);
607 mono_unlink_bblock (cfg, code_bb, next_bb);
609 /* Merge bb and its successor if possible */
610 if ((bb->out_bb [0]->in_count == 1) && (bb->out_bb [0] != cfg->bb_exit) &&
611 (bb->region == bb->out_bb [0]->region)) {
612 mono_merge_basic_blocks (cfg, bb, bb->out_bb [0]);
615 * bbn might have fallen through to the next bb without a branch,
616 * have to add one now (#474718).
617 * FIXME: Maybe need to do this more generally in
618 * merge_basic_blocks () ?
620 if (!(bb->last_ins && MONO_IS_BRANCH_OP (bb->last_ins)) && bb->out_count) {
621 MONO_INST_NEW (cfg, ins1, OP_BR);
622 ins1->inst_target_bb = bb->out_bb [0];
623 MONO_ADD_INS (bb, ins1);
631 * Optimize checks like: if (v < 0 || v > limit) by changing then to unsigned
632 * compares. This isn't really if conversion, but it easier to do here than in
633 * optimize_branches () since the IR is already optimized.
635 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
636 MonoBasicBlock *bb1, *bb2, *next_bb;
637 MonoInst *branch1, *branch2, *compare1, *ins, *next;
639 /* Look for the IR code generated from if (<var> < 0 || v > <limit>)
640 * after branch opts which is:
645 * icompare_imm R [<limit>]
648 if (!(bb->out_count == 2 && !bb->extended))
651 bb1 = bb->out_bb [0];
652 bb2 = bb->out_bb [1];
654 // FIXME: Add more cases
656 /* Check structure */
657 if (!(bb1->in_count == 2 && bb1->in_bb [0] == bb && bb1->in_bb [1] == bb2 && bb2->in_count == 1 && bb2->out_count == 2))
662 /* Check first branch */
663 branch1 = mono_bb_last_inst (bb, filter);
664 if (!(branch1 && ((branch1->opcode == OP_IBLT) || (branch1->opcode == OP_LBLT)) && (branch1->inst_false_bb == next_bb)))
667 /* Check second branch */
668 branch2 = mono_bb_last_inst (next_bb, filter);
672 /* mcs sometimes generates inverted branches */
673 if (((branch2->opcode == OP_IBGT) || (branch2->opcode == OP_LBGT)) && branch2->inst_true_bb == branch1->inst_true_bb)
675 else if (((branch2->opcode == OP_IBLE) || (branch2->opcode == OP_LBLE)) && branch2->inst_false_bb == branch1->inst_true_bb)
680 /* Check first compare */
681 compare1 = mono_inst_prev (mono_bb_last_inst (bb, filter), filter);
682 if (!(compare1 && ((compare1->opcode == OP_ICOMPARE_IMM) || (compare1->opcode == OP_LCOMPARE_IMM)) && compare1->inst_imm == 0))
685 /* Check second bblock */
686 ins = mono_bb_first_inst (next_bb, filter);
689 next = mono_inst_next (ins, filter);
690 if (((ins->opcode == OP_ICOMPARE_IMM) || (ins->opcode == OP_LCOMPARE_IMM)) && ins->sreg1 == compare1->sreg1 && next == branch2) {
691 /* The second arg must be positive */
692 if (ins->inst_imm < 0)
694 } else if (((ins->opcode == OP_LDLEN) || (ins->opcode == OP_STRLEN)) && ins->dreg != compare1->sreg1 && next && next->opcode == OP_ICOMPARE && next->sreg1 == compare1->sreg1 && next->sreg2 == ins->dreg && mono_inst_next (next, filter) == branch2) {
695 /* Another common case: if (index < 0 || index > arr.Length) */
700 if (cfg->verbose_level > 2) {
701 printf ("\tSigned->unsigned compare optimization in BB%d on\n", bb->block_num);
702 printf ("\t\t"); mono_print_ins (compare1);
703 printf ("\t\t"); mono_print_ins (mono_inst_next (compare1, filter));
704 printf ("\t\t"); mono_print_ins (ins);
707 /* Rewrite the first compare+branch */
708 MONO_DELETE_INS (bb, compare1);
709 branch1->opcode = OP_BR;
710 mono_unlink_bblock (cfg, bb, branch1->inst_true_bb);
711 mono_unlink_bblock (cfg, bb, branch1->inst_false_bb);
712 branch1->inst_target_bb = next_bb;
713 mono_link_bblock (cfg, bb, next_bb);
715 /* Rewrite the second branch */
716 branch2->opcode = br_to_br_un (branch2->opcode);
718 mono_merge_basic_blocks (cfg, bb, next_bb);
722 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
723 MonoBasicBlock *bb1, *bb2;
724 MonoInst *prev, *compare, *branch, *ins1, *ins2, *cmov, *move, *tmp;
725 gboolean simple, ret;
729 /* Look for the IR code generated from if (cond) <var> <- <a>
730 * after branch opts which is:
737 if (!(bb->out_count == 1 && bb->extended && bb->code && bb->code->next && bb->code->next->next))
740 mono_print_bb (bb, "");
742 /* Find the compare instruction */
746 while (compare->next->next && compare->next->next != bb->last_ins) {
748 compare = compare->next;
750 branch = compare->next;
751 if (!MONO_IS_COND_BRANCH_OP (branch))
757 if (cfg->opt & MONO_OPT_BRANCH)
758 mono_optimize_branches (cfg);
759 /* Merging bblocks could make some variables local */
760 mono_handle_global_vregs (cfg);
761 if (cfg->opt & (MONO_OPT_CONSPROP | MONO_OPT_COPYPROP))
762 mono_local_cprop (cfg);
763 if (cfg->opt & MONO_OPT_DEADCE)
764 mono_local_deadce (cfg);
770 mono_nullify_basic_block (MonoBasicBlock *bb)
777 bb->code = bb->last_ins = NULL;
782 replace_out_block (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl)
786 for (i = 0; i < bb->out_count; i++) {
787 MonoBasicBlock *ob = bb->out_bb [i];
790 if (bb->out_count > 1) {
791 bb->out_bb [i] = bb->out_bb [bb->out_count - 1];
795 bb->out_bb [i] = repl;
802 replace_in_block (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl)
806 for (i = 0; i < bb->in_count; i++) {
807 MonoBasicBlock *ib = bb->in_bb [i];
810 if (bb->in_count > 1) {
811 bb->in_bb [i] = bb->in_bb [bb->in_count - 1];
815 bb->in_bb [i] = repl;
822 replace_out_block_in_code (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl)
826 for (ins = bb->code; ins != NULL; ins = ins->next) {
827 switch (ins->opcode) {
829 if (ins->inst_target_bb == orig)
830 ins->inst_target_bb = repl;
832 case OP_CALL_HANDLER:
833 if (ins->inst_target_bb == orig)
834 ins->inst_target_bb = repl;
838 int n = GPOINTER_TO_INT (ins->klass);
839 for (i = 0; i < n; i++ ) {
840 if (ins->inst_many_bb [i] == orig)
841 ins->inst_many_bb [i] = repl;
846 if (MONO_IS_COND_BRANCH_OP (ins)) {
847 if (ins->inst_true_bb == orig)
848 ins->inst_true_bb = repl;
849 if (ins->inst_false_bb == orig)
850 ins->inst_false_bb = repl;
851 } else if (MONO_IS_JUMP_TABLE (ins)) {
853 MonoJumpInfoBBTable *table = (MonoJumpInfoBBTable *)MONO_JUMP_TABLE_FROM_INS (ins);
854 for (i = 0; i < table->table_size; i++ ) {
855 if (table->table [i] == orig)
856 table->table [i] = repl;
866 * Check if a bb is useless (is just made of NOPs and ends with an
867 * unconditional branch, or nothing).
868 * If it is so, unlink it from the CFG and nullify it, and return TRUE.
869 * Otherwise, return FALSE;
872 remove_block_if_useless (MonoCompile *cfg, MonoBasicBlock *bb, MonoBasicBlock *previous_bb) {
873 MonoBasicBlock *target_bb = NULL;
876 /* Do not touch handlers */
877 if (bb->region != -1) {
878 bb->not_useless = TRUE;
882 MONO_BB_FOR_EACH_INS (bb, inst) {
883 switch (inst->opcode) {
885 case OP_IL_SEQ_POINT:
888 target_bb = inst->inst_target_bb;
891 bb->not_useless = TRUE;
896 if (target_bb == NULL) {
897 if ((bb->out_count == 1) && (bb->out_bb [0] == bb->next_bb)) {
898 target_bb = bb->next_bb;
900 /* Do not touch empty BBs that do not "fall through" to their next BB (like the exit BB) */
905 /* Do not touch BBs following a switch (they are the "default" branch) */
906 if ((previous_bb->last_ins != NULL) && (previous_bb->last_ins->opcode == OP_SWITCH)) {
910 /* Do not touch BBs following the entry BB and jumping to something that is not */
911 /* thiry "next" bb (the entry BB cannot contain the branch) */
912 if ((previous_bb == cfg->bb_entry) && (bb->next_bb != target_bb)) {
917 * Do not touch BBs following a try block as the code in
918 * mini_method_compile needs them to compute the length of the try block.
920 if (MONO_BBLOCK_IS_IN_REGION (previous_bb, MONO_REGION_TRY))
923 /* Check that there is a target BB, and that bb is not an empty loop (Bug 75061) */
924 if ((target_bb != NULL) && (target_bb != bb)) {
927 if (cfg->verbose_level > 1) {
928 printf ("remove_block_if_useless, removed BB%d\n", bb->block_num);
931 /* unlink_bblock () modifies the bb->in_bb array so can't use a for loop here */
932 while (bb->in_count) {
933 MonoBasicBlock *in_bb = bb->in_bb [0];
934 mono_unlink_bblock (cfg, in_bb, bb);
935 mono_link_bblock (cfg, in_bb, target_bb);
936 replace_out_block_in_code (in_bb, bb, target_bb);
939 mono_unlink_bblock (cfg, bb, target_bb);
940 if (previous_bb != cfg->bb_entry && mono_bb_is_fall_through (cfg, previous_bb)) {
941 for (i = 0; i < previous_bb->out_count; i++) {
942 if (previous_bb->out_bb [i] == target_bb) {
944 MONO_INST_NEW (cfg, jump, OP_BR);
945 MONO_ADD_INS (previous_bb, jump);
946 jump->cil_code = previous_bb->cil_code;
947 jump->inst_target_bb = target_bb;
953 previous_bb->next_bb = bb->next_bb;
954 mono_nullify_basic_block (bb);
963 mono_merge_basic_blocks (MonoCompile *cfg, MonoBasicBlock *bb, MonoBasicBlock *bbn)
966 MonoBasicBlock *prev_bb;
969 /* There may be only one control flow edge between two BBs that we merge, and it should connect these BBs together. */
970 g_assert (bb->out_count == 1 && bbn->in_count == 1 && bb->out_bb [0] == bbn && bbn->in_bb [0] == bb);
972 bb->has_array_access |= bbn->has_array_access;
973 bb->extended |= bbn->extended;
975 mono_unlink_bblock (cfg, bb, bbn);
976 for (i = 0; i < bbn->out_count; ++i)
977 mono_link_bblock (cfg, bb, bbn->out_bb [i]);
978 while (bbn->out_count)
979 mono_unlink_bblock (cfg, bbn, bbn->out_bb [0]);
981 /* Handle the branch at the end of the bb */
982 if (bb->has_call_handler) {
983 for (inst = bb->code; inst != NULL; inst = inst->next) {
984 if (inst->opcode == OP_CALL_HANDLER) {
985 g_assert (inst->inst_target_bb == bbn);
990 if (bb->has_jump_table) {
991 for (inst = bb->code; inst != NULL; inst = inst->next) {
992 if (MONO_IS_JUMP_TABLE (inst)) {
994 MonoJumpInfoBBTable *table = (MonoJumpInfoBBTable *)MONO_JUMP_TABLE_FROM_INS (inst);
995 for (i = 0; i < table->table_size; i++ ) {
996 /* Might be already NULL from a previous merge */
997 if (table->table [i])
998 g_assert (table->table [i] == bbn);
999 table->table [i] = NULL;
1001 /* Can't nullify this as later instructions depend on it */
1005 if (bb->last_ins && MONO_IS_COND_BRANCH_OP (bb->last_ins)) {
1006 g_assert (bb->last_ins->inst_false_bb == bbn);
1007 bb->last_ins->inst_false_bb = NULL;
1008 bb->extended = TRUE;
1009 } else if (bb->last_ins && MONO_IS_BRANCH_OP (bb->last_ins)) {
1010 NULLIFY_INS (bb->last_ins);
1013 bb->has_call_handler |= bbn->has_call_handler;
1014 bb->has_jump_table |= bbn->has_jump_table;
1018 bb->last_ins->next = bbn->code;
1019 bbn->code->prev = bb->last_ins;
1020 bb->last_ins = bbn->last_ins;
1023 bb->code = bbn->code;
1024 bb->last_ins = bbn->last_ins;
1028 /* Check if the control flow predecessor is also the linear IL predecessor. */
1029 if (bbn->in_bb [0]->next_bb == bbn)
1030 prev_bb = bbn->in_bb [0];
1032 /* If it isn't, look for one among all basic blocks. */
1033 for (prev_bb = cfg->bb_entry; prev_bb && prev_bb->next_bb != bbn; prev_bb = prev_bb->next_bb)
1036 prev_bb->next_bb = bbn->next_bb;
1038 /* bbn might not be in the bb list yet */
1039 if (bb->next_bb == bbn)
1040 bb->next_bb = bbn->next_bb;
1042 mono_nullify_basic_block (bbn);
1045 * If bbn fell through to its next bblock, have to add a branch, since bb
1046 * will not fall though to the same bblock (#513931).
1048 if (bb->last_ins && bb->out_count == 1 && bb->out_bb [0] != bb->next_bb && !MONO_IS_BRANCH_OP (bb->last_ins)) {
1049 MONO_INST_NEW (cfg, inst, OP_BR);
1050 inst->inst_target_bb = bb->out_bb [0];
1051 MONO_ADD_INS (bb, inst);
1056 move_basic_block_to_end (MonoCompile *cfg, MonoBasicBlock *bb)
1058 MonoBasicBlock *bbn, *next;
1062 /* Find the previous */
1063 for (bbn = cfg->bb_entry; bbn->next_bb && bbn->next_bb != bb; bbn = bbn->next_bb)
1066 bbn->next_bb = bb->next_bb;
1070 for (bbn = cfg->bb_entry; bbn->next_bb; bbn = bbn->next_bb)
1076 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))))) {
1079 MONO_INST_NEW (cfg, ins, OP_BR);
1080 MONO_ADD_INS (bb, ins);
1081 mono_link_bblock (cfg, bb, next);
1082 ins->inst_target_bb = next;
1087 * mono_remove_block:
1089 * Remove BB from the control flow graph
1092 mono_remove_bblock (MonoCompile *cfg, MonoBasicBlock *bb)
1094 MonoBasicBlock *tmp_bb;
1096 for (tmp_bb = cfg->bb_entry; tmp_bb && tmp_bb->next_bb != bb; tmp_bb = tmp_bb->next_bb)
1100 tmp_bb->next_bb = bb->next_bb;
1104 mono_remove_critical_edges (MonoCompile *cfg)
1107 MonoBasicBlock *previous_bb;
1109 if (cfg->verbose_level > 3) {
1110 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1112 printf ("remove_critical_edges, BEFORE BB%d (in:", bb->block_num);
1113 for (i = 0; i < bb->in_count; i++) {
1114 printf (" %d", bb->in_bb [i]->block_num);
1117 for (i = 0; i < bb->out_count; i++) {
1118 printf (" %d", bb->out_bb [i]->block_num);
1121 if (bb->last_ins != NULL) {
1123 mono_print_ins (bb->last_ins);
1129 for (previous_bb = cfg->bb_entry, bb = previous_bb->next_bb; bb != NULL; previous_bb = previous_bb->next_bb, bb = bb->next_bb) {
1130 if (bb->in_count > 1) {
1132 for (in_bb_index = 0; in_bb_index < bb->in_count; in_bb_index++) {
1133 MonoBasicBlock *in_bb = bb->in_bb [in_bb_index];
1135 * Have to remove non-critical edges whose source ends with a BR_REG
1136 * ins too, since inserting a computation before the BR_REG could
1137 * overwrite the sreg1 of the ins.
1139 if ((in_bb->out_count > 1) || (in_bb->out_count == 1 && in_bb->last_ins && in_bb->last_ins->opcode == OP_BR_REG)) {
1140 MonoBasicBlock *new_bb = (MonoBasicBlock *)mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoBasicBlock));
1141 new_bb->block_num = cfg->num_bblocks++;
1142 // new_bb->real_offset = bb->real_offset;
1143 new_bb->region = bb->region;
1145 /* Do not alter the CFG while altering the BB list */
1146 if (mono_bb_is_fall_through (cfg, previous_bb)) {
1147 if (previous_bb != cfg->bb_entry) {
1149 /* Make sure previous_bb really falls through bb */
1150 for (i = 0; i < previous_bb->out_count; i++) {
1151 if (previous_bb->out_bb [i] == bb) {
1153 MONO_INST_NEW (cfg, jump, OP_BR);
1154 MONO_ADD_INS (previous_bb, jump);
1155 jump->cil_code = previous_bb->cil_code;
1156 jump->inst_target_bb = bb;
1161 /* We cannot add any inst to the entry BB, so we must */
1162 /* put a new BB in the middle to hold the OP_BR */
1164 MonoBasicBlock *new_bb_after_entry = (MonoBasicBlock *)mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoBasicBlock));
1165 new_bb_after_entry->block_num = cfg->num_bblocks++;
1166 // new_bb_after_entry->real_offset = bb->real_offset;
1167 new_bb_after_entry->region = bb->region;
1169 MONO_INST_NEW (cfg, jump, OP_BR);
1170 MONO_ADD_INS (new_bb_after_entry, jump);
1171 jump->cil_code = bb->cil_code;
1172 jump->inst_target_bb = bb;
1174 mono_unlink_bblock (cfg, previous_bb, bb);
1175 mono_link_bblock (cfg, new_bb_after_entry, bb);
1176 mono_link_bblock (cfg, previous_bb, new_bb_after_entry);
1178 previous_bb->next_bb = new_bb_after_entry;
1179 previous_bb = new_bb_after_entry;
1181 if (cfg->verbose_level > 2) {
1182 printf ("remove_critical_edges, added helper BB%d jumping to BB%d\n", new_bb_after_entry->block_num, bb->block_num);
1187 /* Insert new_bb in the BB list */
1188 previous_bb->next_bb = new_bb;
1189 new_bb->next_bb = bb;
1190 previous_bb = new_bb;
1192 /* Setup in_bb and out_bb */
1193 new_bb->in_bb = (MonoBasicBlock **)mono_mempool_alloc ((cfg)->mempool, sizeof (MonoBasicBlock*));
1194 new_bb->in_bb [0] = in_bb;
1195 new_bb->in_count = 1;
1196 new_bb->out_bb = (MonoBasicBlock **)mono_mempool_alloc ((cfg)->mempool, sizeof (MonoBasicBlock*));
1197 new_bb->out_bb [0] = bb;
1198 new_bb->out_count = 1;
1200 /* Relink in_bb and bb to (from) new_bb */
1201 replace_out_block (in_bb, bb, new_bb);
1202 replace_out_block_in_code (in_bb, bb, new_bb);
1203 replace_in_block (bb, in_bb, new_bb);
1205 if (cfg->verbose_level > 2) {
1206 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);
1213 if (cfg->verbose_level > 3) {
1214 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1216 printf ("remove_critical_edges, AFTER BB%d (in:", bb->block_num);
1217 for (i = 0; i < bb->in_count; i++) {
1218 printf (" %d", bb->in_bb [i]->block_num);
1221 for (i = 0; i < bb->out_count; i++) {
1222 printf (" %d", bb->out_bb [i]->block_num);
1225 if (bb->last_ins != NULL) {
1227 mono_print_ins (bb->last_ins);
1235 * Optimizes the branches on the Control Flow Graph
1239 mono_optimize_branches (MonoCompile *cfg)
1241 int i, count = 0, changed = FALSE;
1242 MonoBasicBlock *bb, *bbn;
1243 guint32 niterations;
1244 MonoInst *bbn_first_inst;
1245 int filter = FILTER_IL_SEQ_POINT;
1248 * Some crazy loops could cause the code below to go into an infinite
1249 * loop, see bug #53003 for an example. To prevent this, we put an upper
1250 * bound on the number of iterations.
1252 if (cfg->num_bblocks > 1000)
1253 niterations = cfg->num_bblocks * 2;
1258 MonoBasicBlock *previous_bb;
1262 /* we skip the entry block (exit is handled specially instead ) */
1263 for (previous_bb = cfg->bb_entry, bb = cfg->bb_entry->next_bb; bb; previous_bb = bb, bb = bb->next_bb) {
1265 if (count == 1000) {
1266 mono_threads_safepoint ();
1269 /* dont touch code inside exception clauses */
1270 if (bb->region != -1)
1273 if (!bb->not_useless && remove_block_if_useless (cfg, bb, previous_bb)) {
1278 if ((bbn = bb->next_bb) && bbn->in_count == 0 && bbn != cfg->bb_exit && bb->region == bbn->region) {
1279 if (cfg->verbose_level > 2)
1280 g_print ("nullify block triggered %d\n", bbn->block_num);
1282 bb->next_bb = bbn->next_bb;
1284 for (i = 0; i < bbn->out_count; i++)
1285 replace_in_block (bbn->out_bb [i], bbn, NULL);
1287 mono_nullify_basic_block (bbn);
1291 if (bb->out_count == 1) {
1292 bbn = bb->out_bb [0];
1294 /* conditional branches where true and false targets are the same can be also replaced with OP_BR */
1295 if (bb->last_ins && (bb->last_ins->opcode != OP_BR) && MONO_IS_COND_BRANCH_OP (bb->last_ins)) {
1296 bb->last_ins->opcode = OP_BR;
1297 bb->last_ins->inst_target_bb = bb->last_ins->inst_true_bb;
1299 if (cfg->verbose_level > 2)
1300 g_print ("cond branch removal triggered in %d %d\n", bb->block_num, bb->out_count);
1303 if (bb->region == bbn->region && bb->next_bb == bbn) {
1304 /* the block are in sequence anyway ... */
1306 /* branches to the following block can be removed */
1307 if (bb->last_ins && bb->last_ins->opcode == OP_BR && !bbn->out_of_line) {
1308 NULLIFY_INS (bb->last_ins);
1310 if (cfg->verbose_level > 2)
1311 g_print ("br removal triggered %d -> %d\n", bb->block_num, bbn->block_num);
1314 if (bbn->in_count == 1 && !bb->extended) {
1315 if (bbn != cfg->bb_exit) {
1316 if (cfg->verbose_level > 2)
1317 g_print ("block merge triggered %d -> %d\n", bb->block_num, bbn->block_num);
1318 mono_merge_basic_blocks (cfg, bb, bbn);
1323 //mono_print_bb_code (bb);
1328 if ((bbn = bb->next_bb) && bbn->in_count == 0 && bbn != cfg->bb_exit && bb->region == bbn->region) {
1329 if (cfg->verbose_level > 2) {
1330 g_print ("nullify block triggered %d\n", bbn->block_num);
1332 bb->next_bb = bbn->next_bb;
1334 for (i = 0; i < bbn->out_count; i++)
1335 replace_in_block (bbn->out_bb [i], bbn, NULL);
1337 mono_nullify_basic_block (bbn);
1342 if (bb->out_count == 1) {
1343 bbn = bb->out_bb [0];
1345 if (bb->last_ins && bb->last_ins->opcode == OP_BR) {
1346 bbn = bb->last_ins->inst_target_bb;
1347 bbn_first_inst = mono_bb_first_inst (bbn, filter);
1348 if (bb->region == bbn->region && bbn_first_inst && bbn_first_inst->opcode == OP_BR &&
1349 bbn_first_inst->inst_target_bb != bbn &&
1350 bbn_first_inst->inst_target_bb->region == bb->region) {
1352 if (cfg->verbose_level > 2)
1353 g_print ("branch to branch triggered %d -> %d -> %d\n", bb->block_num, bbn->block_num, bbn_first_inst->inst_target_bb->block_num);
1355 replace_in_block (bbn, bb, NULL);
1356 replace_out_block (bb, bbn, bbn_first_inst->inst_target_bb);
1357 mono_link_bblock (cfg, bb, bbn_first_inst->inst_target_bb);
1358 bb->last_ins->inst_target_bb = bbn_first_inst->inst_target_bb;
1363 } else if (bb->out_count == 2) {
1364 if (bb->last_ins && MONO_IS_COND_BRANCH_NOFP (bb->last_ins)) {
1366 MonoBasicBlock *taken_branch_target = NULL, *untaken_branch_target = NULL;
1368 if (bb->last_ins->flags & MONO_INST_CFOLD_TAKEN)
1369 branch_result = BRANCH_TAKEN;
1370 else if (bb->last_ins->flags & MONO_INST_CFOLD_NOT_TAKEN)
1371 branch_result = BRANCH_NOT_TAKEN;
1373 branch_result = BRANCH_UNDEF;
1375 if (branch_result == BRANCH_TAKEN) {
1376 taken_branch_target = bb->last_ins->inst_true_bb;
1377 untaken_branch_target = bb->last_ins->inst_false_bb;
1378 } else if (branch_result == BRANCH_NOT_TAKEN) {
1379 taken_branch_target = bb->last_ins->inst_false_bb;
1380 untaken_branch_target = bb->last_ins->inst_true_bb;
1382 if (taken_branch_target) {
1383 /* if mono_eval_cond_branch () is ever taken to handle
1384 * non-constant values to compare, issue a pop here.
1386 bb->last_ins->opcode = OP_BR;
1387 bb->last_ins->inst_target_bb = taken_branch_target;
1389 mono_unlink_bblock (cfg, bb, untaken_branch_target);
1393 bbn = bb->last_ins->inst_true_bb;
1394 bbn_first_inst = mono_bb_first_inst (bbn, filter);
1395 if (bb->region == bbn->region && bbn_first_inst && bbn_first_inst->opcode == OP_BR &&
1396 bbn_first_inst->inst_target_bb->region == bb->region) {
1397 if (cfg->verbose_level > 2)
1398 g_print ("cbranch1 to branch triggered %d -> (%d) %d (0x%02x)\n",
1399 bb->block_num, bbn->block_num, bbn_first_inst->inst_target_bb->block_num,
1400 bbn_first_inst->opcode);
1403 * Unlink, then relink bblocks to avoid various
1404 * tricky situations when the two targets of the branch
1405 * are equal, or will become equal after the change.
1407 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1408 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1410 bb->last_ins->inst_true_bb = bbn_first_inst->inst_target_bb;
1412 mono_link_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1413 mono_link_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1419 bbn = bb->last_ins->inst_false_bb;
1420 bbn_first_inst = mono_bb_first_inst (bbn, filter);
1421 if (bbn && bb->region == bbn->region && bbn_first_inst && bbn_first_inst->opcode == OP_BR &&
1422 bbn_first_inst->inst_target_bb->region == bb->region) {
1423 if (cfg->verbose_level > 2)
1424 g_print ("cbranch2 to branch triggered %d -> (%d) %d (0x%02x)\n",
1425 bb->block_num, bbn->block_num, bbn_first_inst->inst_target_bb->block_num,
1426 bbn_first_inst->opcode);
1428 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1429 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1431 bb->last_ins->inst_false_bb = bbn_first_inst->inst_target_bb;
1433 mono_link_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1434 mono_link_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1440 bbn = bb->last_ins->inst_false_bb;
1442 * If bb is an extended bb, it could contain an inside branch to bbn.
1443 * FIXME: Enable the optimization if that is not true.
1444 * If bblocks_linked () is true, then merging bb and bbn
1445 * would require addition of an extra branch at the end of bbn
1446 * slowing down loops.
1448 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)) {
1449 g_assert (bbn->in_bb [0] == bb);
1450 if (cfg->verbose_level > 2)
1451 g_print ("merge false branch target triggered BB%d -> BB%d\n", bb->block_num, bbn->block_num);
1452 mono_merge_basic_blocks (cfg, bb, bbn);
1458 if (bb->last_ins && MONO_IS_COND_BRANCH_NOFP (bb->last_ins)) {
1459 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) {
1460 /* Reverse the branch */
1461 bb->last_ins->opcode = mono_reverse_branch_op (bb->last_ins->opcode);
1462 bbn = bb->last_ins->inst_false_bb;
1463 bb->last_ins->inst_false_bb = bb->last_ins->inst_true_bb;
1464 bb->last_ins->inst_true_bb = bbn;
1466 move_basic_block_to_end (cfg, bb->last_ins->inst_true_bb);
1467 if (cfg->verbose_level > 2)
1468 g_print ("cbranch to throw block triggered %d.\n",
1474 } while (changed && (niterations > 0));
1477 #else /* !DISABLE_JIT */
1479 MONO_EMPTY_SOURCE_FILE (branch_opts);
1481 #endif /* !DISABLE_JIT */