-static void
-nullify_basic_block (MonoBasicBlock *bb)
-{
- bb->in_count = 0;
- bb->out_count = 0;
- bb->in_bb = NULL;
- bb->out_bb = NULL;
- bb->next_bb = NULL;
- MONO_INST_LIST_INIT (&bb->ins_list);
- bb->cil_code = NULL;
-}
-
-static void
-replace_out_block (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl)
-{
- int i;
-
- for (i = 0; i < bb->out_count; i++) {
- MonoBasicBlock *ob = bb->out_bb [i];
- if (ob == orig) {
- if (!repl) {
- if (bb->out_count > 1) {
- bb->out_bb [i] = bb->out_bb [bb->out_count - 1];
- }
- bb->out_count--;
- } else {
- bb->out_bb [i] = repl;
- }
- }
- }
-}
-
-static void
-replace_in_block (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl)
-{
- int i;
-
- for (i = 0; i < bb->in_count; i++) {
- MonoBasicBlock *ib = bb->in_bb [i];
- if (ib == orig) {
- if (!repl) {
- if (bb->in_count > 1) {
- bb->in_bb [i] = bb->in_bb [bb->in_count - 1];
- }
- bb->in_count--;
- } else {
- bb->in_bb [i] = repl;
- }
- }
- }
-}
-
-static void
-replace_out_block_in_code (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl) {
- MonoInst *inst;
-
- MONO_BB_FOR_EACH_INS (bb, inst) {
- if (inst->opcode == OP_CALL_HANDLER) {
- if (inst->inst_target_bb == orig)
- inst->inst_target_bb = repl;
- }
- }
-
- inst = mono_inst_list_last (&bb->ins_list);
- if (!inst)
- return;
-
- switch (inst->opcode) {
- case OP_BR:
- if (inst->inst_target_bb == orig)
- inst->inst_target_bb = repl;
- break;
- case OP_SWITCH: {
- int i;
- int n = GPOINTER_TO_INT (inst->klass);
- for (i = 0; i < n; i++ ) {
- if (inst->inst_many_bb [i] == orig)
- inst->inst_many_bb [i] = repl;
- }
- break;
- }
- case CEE_BNE_UN:
- case CEE_BEQ:
- case CEE_BLT:
- case CEE_BLT_UN:
- case CEE_BGT:
- case CEE_BGT_UN:
- case CEE_BGE:
- case CEE_BGE_UN:
- case CEE_BLE:
- case CEE_BLE_UN:
- if (inst->inst_true_bb == orig)
- inst->inst_true_bb = repl;
- if (inst->inst_false_bb == orig)
- inst->inst_false_bb = repl;
- break;
- default:
- break;
- }
-}
-
-static void
-replace_basic_block (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl)
-{
- int i, j;
-
- for (i = 0; i < bb->out_count; i++) {
- MonoBasicBlock *ob = bb->out_bb [i];
- for (j = 0; j < ob->in_count; j++) {
- if (ob->in_bb [j] == orig) {
- ob->in_bb [j] = repl;
- }
- }
- }
-
-}
-
-/**
- * Check if a bb is useless (is just made of NOPs and ends with an
- * unconditional branch, or nothing).
- * If it is so, unlink it from the CFG and nullify it, and return TRUE.
- * Otherwise, return FALSE;
- */
-static gboolean
-remove_block_if_useless (MonoCompile *cfg, MonoBasicBlock *bb, MonoBasicBlock *previous_bb) {
- MonoBasicBlock *target_bb = NULL;
- MonoInst *inst;
-
- /* Do not touch handlers */
- if (bb->region != -1) {
- bb->not_useless = TRUE;
- return FALSE;
- }
-
- MONO_BB_FOR_EACH_INS (bb, inst) {
- switch (inst->opcode) {
- case OP_NOP:
- break;
- case OP_BR:
- target_bb = inst->inst_target_bb;
- break;
- default:
- bb->not_useless = TRUE;
- return FALSE;
- }
- }
-
- if (target_bb == NULL) {
- if ((bb->out_count == 1) && (bb->out_bb [0] == bb->next_bb)) {
- target_bb = bb->next_bb;
- } else {
- /* Do not touch empty BBs that do not "fall through" to their next BB (like the exit BB) */
- return FALSE;
- }
- }
-
- /* Do not touch BBs following a switch (they are the "default" branch) */
- inst = mono_inst_list_last (&previous_bb->ins_list);
- if (inst && inst->opcode == OP_SWITCH)
- return FALSE;
-
- /* Do not touch BBs following the entry BB and jumping to something that is not */
- /* thiry "next" bb (the entry BB cannot contain the branch) */
- if ((previous_bb == cfg->bb_entry) && (bb->next_bb != target_bb)) {
- return FALSE;
- }
-
- /*
- * Do not touch BBs following a try block as the code in
- * mini_method_compile needs them to compute the length of the try block.
- */
- if (MONO_BBLOCK_IS_IN_REGION (previous_bb, MONO_REGION_TRY))
- return FALSE;
-
- /* Check that there is a target BB, and that bb is not an empty loop (Bug 75061) */
- if ((target_bb != NULL) && (target_bb != bb)) {
- MonoInst *last_ins;
- int i;
-
- if (cfg->verbose_level > 1) {
- printf ("remove_block_if_useless, removed BB%d\n", bb->block_num);
- }
-
- /* unlink_bblock () modifies the bb->in_bb array so can't use a for loop here */
- while (bb->in_count) {
- MonoBasicBlock *in_bb = bb->in_bb [0];
- mono_unlink_bblock (cfg, in_bb, bb);
- link_bblock (cfg, in_bb, target_bb);
- replace_out_block_in_code (in_bb, bb, target_bb);
- }
-
- mono_unlink_bblock (cfg, bb, target_bb);
-
- last_ins = mono_inst_list_last (&previous_bb->ins_list);
-
- if ((previous_bb != cfg->bb_entry) &&
- (previous_bb->region == bb->region) &&
- ((last_ins == NULL) ||
- ((last_ins->opcode != OP_BR) &&
- (!(MONO_IS_COND_BRANCH_OP (last_ins))) &&
- (last_ins->opcode != OP_SWITCH)))) {
- for (i = 0; i < previous_bb->out_count; i++) {
- if (previous_bb->out_bb [i] == target_bb) {
- MonoInst *jump;
- MONO_INST_NEW (cfg, jump, OP_BR);
- MONO_ADD_INS (previous_bb, jump);
- jump->cil_code = previous_bb->cil_code;
- jump->inst_target_bb = target_bb;
- break;
- }
- }
- }
-
- previous_bb->next_bb = bb->next_bb;
- nullify_basic_block (bb);
-
- return TRUE;
- } else {
- return FALSE;
- }
-}
-
-static void
-merge_basic_blocks (MonoBasicBlock *bb, MonoBasicBlock *bbn)
-{
- MonoInst *last_ins;
-
- bb->out_count = bbn->out_count;
- bb->out_bb = bbn->out_bb;
-
- replace_basic_block (bb, bbn, bb);
-
- last_ins = mono_inst_list_last (&bb->ins_list);
-
- /* Nullify branch at the end of bb */
- if (last_ins && MONO_IS_BRANCH_OP (last_ins))
- last_ins->opcode = OP_NOP;
-
- MONO_INST_LIST_SPLICE_TAIL_INIT (&bbn->ins_list, &bb->ins_list);
-
- bb->next_bb = bbn->next_bb;
- nullify_basic_block (bbn);
-}
-
-static void
-move_basic_block_to_end (MonoCompile *cfg, MonoBasicBlock *bb)
-{
- MonoBasicBlock *bbn, *next;
- MonoInst *last_ins;
-
- next = bb->next_bb;
-
- /* Find the previous */
- for (bbn = cfg->bb_entry; bbn->next_bb && bbn->next_bb != bb; bbn = bbn->next_bb)
- ;
- if (bbn->next_bb) {
- bbn->next_bb = bb->next_bb;
- }
-
- /* Find the last */
- for (bbn = cfg->bb_entry; bbn->next_bb; bbn = bbn->next_bb)
- ;
- bbn->next_bb = bb;
- bb->next_bb = NULL;
-
- last_ins = mono_inst_list_last (&bb->ins_list);
-
- /* Add a branch */
- if (next && (!last_ins || (last_ins->opcode != OP_NOT_REACHED))) {
- MonoInst *ins;
-
- MONO_INST_NEW (cfg, ins, OP_BR);
- MONO_ADD_INS (bb, ins);
- link_bblock (cfg, bb, next);
- ins->inst_target_bb = next;
- }
-}
-
-/* checks that a and b represent the same instructions, conservatively,
- * it can return FALSE also for two trees that are equal.
- * FIXME: also make sure there are no side effects.
- */
-static int
-same_trees (MonoInst *a, MonoInst *b)
-{
- int arity;
- if (a->opcode != b->opcode)
- return FALSE;
- arity = mono_burg_arity [a->opcode];
- if (arity == 1) {
- if (a->ssa_op == b->ssa_op && a->ssa_op == MONO_SSA_LOAD && a->inst_i0 == b->inst_i0)
- return TRUE;
- return same_trees (a->inst_left, b->inst_left);
- } else if (arity == 2) {
- return same_trees (a->inst_left, b->inst_left) && same_trees (a->inst_right, b->inst_right);
- } else if (arity == 0) {
- switch (a->opcode) {
- case OP_ICONST:
- return a->inst_c0 == b->inst_c0;
- default:
- return FALSE;
- }
- }
- return FALSE;
-}
-
-static int
-get_unsigned_condbranch (int opcode)
-{
- switch (opcode) {
- case CEE_BLE: return CEE_BLE_UN;
- case CEE_BLT: return CEE_BLT_UN;
- case CEE_BGE: return CEE_BGE_UN;
- case CEE_BGT: return CEE_BGT_UN;
- }
- g_assert_not_reached ();
- return 0;
-}
-
-static int
-tree_is_unsigned (MonoInst* ins) {
- switch (ins->opcode) {
- case OP_ICONST:
- return (int)ins->inst_c0 >= 0;
- /* array lengths are positive as are string sizes */
- case CEE_LDLEN:
- case OP_STRLEN:
- return TRUE;
- case CEE_CONV_U1:
- case CEE_CONV_U2:
- case CEE_CONV_U4:
- case CEE_CONV_OVF_U1:
- case CEE_CONV_OVF_U2:
- case CEE_CONV_OVF_U4:
- return TRUE;
- case CEE_LDIND_U1:
- case CEE_LDIND_U2:
- case CEE_LDIND_U4:
- return TRUE;
- default:
- return FALSE;
- }
-}
-
-/* check if an unsigned compare can be used instead of two signed compares
- * for (val < 0 || val > limit) conditionals.
- * Returns TRUE if the optimization has been applied.
- * Note that this can't be applied if the second arg is not positive...
- */
-static int
-try_unsigned_compare (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *bb_last)
-{
- MonoBasicBlock *truet, *falset;
- MonoInst *cmp_inst = bb_last->inst_left;
- MonoInst *condb;
- if (!cmp_inst->inst_right->inst_c0 == 0)
- return FALSE;
- truet = bb_last->inst_true_bb;
- falset = bb_last->inst_false_bb;
- if (falset->in_count != 1)
- return FALSE;
- condb = mono_inst_list_last (&falset->ins_list);
- /* target bb must have one instruction */
- if (!condb || (condb->node.next != &falset->ins_list))
- return FALSE;
- if ((((condb->opcode == CEE_BLE || condb->opcode == CEE_BLT) && (condb->inst_false_bb == truet))
- || ((condb->opcode == CEE_BGE || condb->opcode == CEE_BGT) && (condb->inst_true_bb == truet)))
- && same_trees (cmp_inst->inst_left, condb->inst_left->inst_left)) {
- if (!tree_is_unsigned (condb->inst_left->inst_right))
- return FALSE;
- condb->opcode = get_unsigned_condbranch (condb->opcode);
- /* change the original condbranch to just point to the new unsigned check */
- bb_last->opcode = OP_BR;
- bb_last->inst_target_bb = falset;
- replace_out_block (bb, truet, NULL);
- replace_in_block (truet, bb, NULL);
- return TRUE;
- }
- return FALSE;
-}
-
-/*
- * Optimizes the branches on the Control Flow Graph
- *
- */
-static void
-optimize_branches (MonoCompile *cfg)
-{
- int i, changed = FALSE;
- MonoBasicBlock *bb, *bbn;
- guint32 niterations;
-
- /*
- * Some crazy loops could cause the code below to go into an infinite
- * loop, see bug #53003 for an example. To prevent this, we put an upper
- * bound on the number of iterations.
- */
- if (cfg->num_bblocks > 1000)
- niterations = cfg->num_bblocks * 2;
- else
- niterations = 1000;
-
- do {
- MonoBasicBlock *previous_bb;
- changed = FALSE;
- niterations --;
-
- /* we skip the entry block (exit is handled specially instead ) */
- for (previous_bb = cfg->bb_entry, bb = cfg->bb_entry->next_bb; bb; previous_bb = bb, bb = bb->next_bb) {
- MonoInst *last_ins;
-
- /* dont touch code inside exception clauses */
- if (bb->region != -1)
- continue;
-
- if (!bb->not_useless && remove_block_if_useless (cfg, bb, previous_bb)) {
- changed = TRUE;
- continue;
- }
-
- if ((bbn = bb->next_bb) && bbn->in_count == 0 && bb->region == bbn->region) {
- if (cfg->verbose_level > 2)
- g_print ("nullify block triggered %d\n", bbn->block_num);
-
- bb->next_bb = bbn->next_bb;
-
- for (i = 0; i < bbn->out_count; i++)
- replace_in_block (bbn->out_bb [i], bbn, NULL);
-
- nullify_basic_block (bbn);
- changed = TRUE;
- }
-
- last_ins = mono_inst_list_last (&bb->ins_list);
- if (bb->out_count == 1) {
- bbn = bb->out_bb [0];
-
- /* conditional branches where true and false targets are the same can be also replaced with OP_BR */
- if (last_ins && MONO_IS_COND_BRANCH_OP (last_ins)) {
- MonoInst *pop;
- MONO_INST_NEW (cfg, pop, CEE_POP);
- pop->inst_left = last_ins->inst_left->inst_left;
- mono_add_ins_to_end (bb, pop);
- MONO_INST_NEW (cfg, pop, CEE_POP);
- pop->inst_left = last_ins->inst_left->inst_right;
- mono_add_ins_to_end (bb, pop);
- last_ins->opcode = OP_BR;
- last_ins->inst_target_bb = last_ins->inst_true_bb;
- changed = TRUE;
- if (cfg->verbose_level > 2)
- g_print ("cond branch removal triggered in %d %d\n", bb->block_num, bb->out_count);
- }
-
- if (bb->region == bbn->region && bb->next_bb == bbn) {
- /* the block are in sequence anyway ... */
-
- /* branches to the following block can be removed */
- if (last_ins && last_ins->opcode == OP_BR) {
- last_ins->opcode = OP_NOP;
- changed = TRUE;
- if (cfg->verbose_level > 2)
- g_print ("br removal triggered %d -> %d\n", bb->block_num, bbn->block_num);
- }
-
- if (bbn->in_count == 1) {
-
- if (bbn != cfg->bb_exit) {
- if (cfg->verbose_level > 2)
- g_print ("block merge triggered %d -> %d\n", bb->block_num, bbn->block_num);
- merge_basic_blocks (bb, bbn);
- changed = TRUE;
- continue;
- }
-
- //mono_print_bb_code (bb);
- }
- }
- }
- if ((bbn = bb->next_bb) && bbn->in_count == 0 && bb->region == bbn->region) {
- if (cfg->verbose_level > 2) {
- g_print ("nullify block triggered %d\n", bbn->block_num);
- }
- bb->next_bb = bbn->next_bb;
-
- for (i = 0; i < bbn->out_count; i++)
- replace_in_block (bbn->out_bb [i], bbn, NULL);
-
- nullify_basic_block (bbn);
- changed = TRUE;
- continue;
- }
-
- if (bb->out_count == 1) {
- bbn = bb->out_bb [0];
-
- if (last_ins && last_ins->opcode == OP_BR) {
- MonoInst *bbn_code;
-
- bbn = last_ins->inst_target_bb;
- bbn_code = mono_inst_list_first (&bbn->ins_list);
- if (bb->region == bbn->region && bbn_code &&
- bbn_code->opcode == OP_BR &&
- bbn_code->inst_target_bb->region == bb->region) {
- if (cfg->verbose_level > 2)
- g_print ("in %s branch to branch triggered %d -> %d -> %d\n", cfg->method->name,
- bb->block_num, bbn->block_num, bbn_code->inst_target_bb->block_num);
-
- replace_in_block (bbn, bb, NULL);
- replace_out_block (bb, bbn, bbn_code->inst_target_bb);
- link_bblock (cfg, bb, bbn_code->inst_target_bb);
- last_ins->inst_target_bb = bbn_code->inst_target_bb;
- changed = TRUE;
- continue;
- }
- }
- } else if (bb->out_count == 2) {
- if (last_ins && MONO_IS_COND_BRANCH_NOFP (last_ins)) {
- int branch_result = mono_eval_cond_branch (last_ins);
- MonoBasicBlock *taken_branch_target = NULL, *untaken_branch_target = NULL;
- MonoInst *bbn_code;
-
- if (branch_result == BRANCH_TAKEN) {
- taken_branch_target = last_ins->inst_true_bb;
- untaken_branch_target = last_ins->inst_false_bb;
- } else if (branch_result == BRANCH_NOT_TAKEN) {
- taken_branch_target = last_ins->inst_false_bb;
- untaken_branch_target = last_ins->inst_true_bb;
- }
- if (taken_branch_target) {
- /* if mono_eval_cond_branch () is ever taken to handle
- * non-constant values to compare, issue a pop here.
- */
- last_ins->opcode = OP_BR;
- last_ins->inst_target_bb = taken_branch_target;
- mono_unlink_bblock (cfg, bb, untaken_branch_target);
- changed = TRUE;
- continue;
- }
- bbn = last_ins->inst_true_bb;
- bbn_code = mono_inst_list_first (&bbn->ins_list);
- if (bb->region == bbn->region && bbn_code && bbn_code->opcode == OP_BR &&
- bbn_code->inst_target_bb->region == bb->region) {
- if (cfg->verbose_level > 2)
- g_print ("cbranch1 to branch triggered %d -> (%d) %d (0x%02x)\n",
- bb->block_num, bbn->block_num, bbn_code->inst_target_bb->block_num,
- bbn_code->opcode);
-
- /*
- * Unlink, then relink bblocks to avoid various
- * tricky situations when the two targets of the branch
- * are equal, or will become equal after the change.
- */
- mono_unlink_bblock (cfg, bb, last_ins->inst_true_bb);
- mono_unlink_bblock (cfg, bb, last_ins->inst_false_bb);
-
- last_ins->inst_true_bb = bbn_code->inst_target_bb;
-
- link_bblock (cfg, bb, last_ins->inst_true_bb);
- link_bblock (cfg, bb, last_ins->inst_false_bb);
-
- changed = TRUE;
- continue;
- }
-
- bbn = last_ins->inst_false_bb;
- bbn_code = mono_inst_list_first (&bbn->ins_list);
- if (bb->region == bbn->region && bbn_code && bbn_code->opcode == OP_BR &&
- bbn_code->inst_target_bb->region == bb->region) {
- if (cfg->verbose_level > 2)
- g_print ("cbranch2 to branch triggered %d -> (%d) %d (0x%02x)\n",
- bb->block_num, bbn->block_num, bbn_code->inst_target_bb->block_num,
- bbn_code->opcode);
-
- mono_unlink_bblock (cfg, bb, last_ins->inst_true_bb);
- mono_unlink_bblock (cfg, bb, last_ins->inst_false_bb);
-
- last_ins->inst_false_bb = bbn_code->inst_target_bb;
-
- link_bblock (cfg, bb, last_ins->inst_true_bb);
- link_bblock (cfg, bb, last_ins->inst_false_bb);
-
- changed = TRUE;
- continue;
- }
- }
-
- /* detect and optimize to unsigned compares checks like: if (v < 0 || v > limit */
- if (last_ins && last_ins->opcode == CEE_BLT && last_ins->inst_left->inst_right->opcode == OP_ICONST) {
- if (try_unsigned_compare (cfg, bb, last_ins)) {
- /*g_print ("applied in bb %d (->%d) %s\n", bb->block_num, last_ins->inst_target_bb->block_num, mono_method_full_name (cfg->method, TRUE));*/
- changed = TRUE;
- continue;
- }
- }
-
- if (last_ins && MONO_IS_COND_BRANCH_NOFP (last_ins)) {
- if (last_ins->inst_false_bb->out_of_line && (bb->region == last_ins->inst_false_bb->region)) {
- /* Reverse the branch */
- last_ins->opcode = reverse_branch_op (last_ins->opcode);
- bbn = last_ins->inst_false_bb;
- last_ins->inst_false_bb = last_ins->inst_true_bb;
- last_ins->inst_true_bb = bbn;
-
- move_basic_block_to_end (cfg, last_ins->inst_true_bb);
- if (cfg->verbose_level > 2)
- g_print ("cbranch to throw block triggered %d.\n",
- bb->block_num);
- }
- }
- }
- }
- } while (changed && (niterations > 0));
-
-}
-