mono/mini/branch-opts.c

   1 /*
   2  * branch-opts.c: Branch optimizations support
   3  *
   4  * Authors:
   5  *   Patrik Torstensson (Patrik.Torstesson at gmail.com)
   6  *
   7  * (C) 2005 Ximian, Inc.  http://www.ximian.com
   8  */
   9  #include "mini.h"
  10
  11  /*
  12  * Used by the arch code to replace the exception handling
  13  * with a direct branch. This is safe to do if the
  14  * exception object isn't used, no rethrow statement and
  15  * no filter statement (verify).
  16  *
  17  */
  18 MonoInst *
  19 mono_branch_optimize_exception_target (MonoCompile *cfg, MonoBasicBlock *bb, const char * exname)
  20 {
  21         MonoMethod *method = cfg->method;
  22         MonoMethodHeader *header = mono_method_get_header (method);
  23         MonoExceptionClause *clause;
  24         MonoClass *exclass;
  25         int i;
  26
  27         if (!(cfg->opt & MONO_OPT_EXCEPTION))
  28                 return NULL;
  29
  30         if (bb->region == -1 || !MONO_BBLOCK_IS_IN_REGION (bb, MONO_REGION_TRY))
  31                 return NULL;
  32
  33         exclass = mono_class_from_name (mono_get_corlib (), "System", exname);
  34         /* search for the handler */
  35         for (i = 0; i < header->num_clauses; ++i) {
  36                 clause = &header->clauses [i];
  37                 if (MONO_OFFSET_IN_CLAUSE (clause, bb->real_offset)) {
  38                         if (clause->flags == MONO_EXCEPTION_CLAUSE_NONE && clause->data.catch_class && mono_class_is_assignable_from (clause->data.catch_class, exclass)) {
  39                                 MonoBasicBlock *tbb;
  40
  41                                 /* get the basic block for the handler and
  42                                  * check if the exception object is used.
  43                                  * Flag is set during method_to_ir due to
  44                                  * pop-op is optmized away in codegen (burg).
  45                                  */
  46                                 tbb = cfg->cil_offset_to_bb [clause->handler_offset];
  47                                 if (tbb && tbb->flags & BB_EXCEPTION_DEAD_OBJ && !(tbb->flags & BB_EXCEPTION_UNSAFE)) {
  48                                         MonoBasicBlock *targetbb = tbb;
  49                                         gboolean unsafe = FALSE;
  50
  51                                         /* Check if this catch clause is ok to optimize by
  52                                          * looking for the BB_EXCEPTION_UNSAFE in every BB that
  53                                          * belongs to the same region.
  54                                          *
  55                                          * UNSAFE flag is set during method_to_ir (OP_RETHROW)
  56                                          */
  57                                         while (!unsafe && tbb->next_bb && tbb->region == tbb->next_bb->region) {
  58                                                 if (tbb->next_bb->flags & BB_EXCEPTION_UNSAFE)  {
  59                                                         unsafe = TRUE;
  60                                                         break;
  61                                                 }
  62                                                 tbb = tbb->next_bb;
  63                                         }
  64
  65                                         if (!unsafe) {
  66                                                 MonoInst *jump;
  67
  68                                                 /* Create dummy inst to allow easier integration in
  69                                                  * arch dependent code (opcode ignored)
  70                                                  */
  71                                                 MONO_INST_NEW (cfg, jump, OP_BR);
  72
  73                                                 /* Allocate memory for our branch target */
  74                                                 jump->inst_i1 = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoInst));
  75                                                 jump->inst_true_bb = targetbb;
  76
  77                                                 if (cfg->verbose_level > 2)
  78                                                         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);
  79
  80                                                 return jump;
  81                                         }
  82
  83                                         return NULL;
  84                                 }
  85                         } else {
  86                                 /* Branching to an outer clause could skip inner clauses */
  87                                 return NULL;
  88                         }
  89                 }
  90         }
  91
  92         return NULL;
  93 }
  94
  95 static const int int_cmov_opcodes [] = {
  96         OP_CMOV_IEQ,
  97         OP_CMOV_INE_UN,
  98         OP_CMOV_ILE,
  99         OP_CMOV_IGE,
 100         OP_CMOV_ILT,
 101         OP_CMOV_IGT,
 102         OP_CMOV_ILE_UN,
 103         OP_CMOV_IGE_UN,
 104         OP_CMOV_ILT_UN,
 105         OP_CMOV_IGT_UN
 106 };
 107
 108 static const int long_cmov_opcodes [] = {
 109         OP_CMOV_LEQ,
 110         OP_CMOV_LNE_UN,
 111         OP_CMOV_LLE,
 112         OP_CMOV_LGE,
 113         OP_CMOV_LLT,
 114         OP_CMOV_LGT,
 115         OP_CMOV_LLE_UN,
 116         OP_CMOV_LGE_UN,
 117         OP_CMOV_LLT_UN,
 118         OP_CMOV_LGT_UN
 119 };
 120
 121 void
 122 mono_if_conversion (MonoCompile *cfg)
 123 {
 124 #ifdef MONO_ARCH_HAVE_CMOV_OPS
 125         MonoBasicBlock *bb;
 126         gboolean changed = FALSE;
 127
 128         if (!(cfg->opt & MONO_OPT_CMOV))
 129                 return;
 130
 131         // FIXME: Make this work with extended bblocks
 132
 133         /*
 134          * This pass requires somewhat optimized IR code so it should be run after
 135          * local cprop/deadce. Also, it should be run before dominator computation, since
 136          * it changes control flow.
 137          */
 138         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 139                 MonoBasicBlock *bb1, *bb2;
 140
 141         restart:
 142                 /* Look for the IR code generated from cond ? a : b
 143                  * which is:
 144                  * BB:
 145                  * b<cond> [BB1BB2]
 146                  * BB1:
 147                  * <var> <- <a>
 148                  * br BB3
 149                  * BB2:
 150                  * <var> <- <b>
 151                  * br BB3
 152                  */
 153                 if (!(bb->out_count == 2 && !bb->extended))
 154                         continue;
 155
 156                 bb1 = bb->out_bb [0];
 157                 bb2 = bb->out_bb [1];
 158
 159                 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]) {
 160                         MonoInst *prev, *compare, *branch, *ins1, *ins2, *cmov, *move, *tmp;
 161                         gboolean simple, ret;
 162                         int dreg, tmp_reg;
 163                         CompType comp_type;
 164
 165                         /*
 166                          * Check that bb1 and bb2 are 'simple' and both assign to the same
 167                          * variable.
 168                          */
 169                         /* FIXME: Get rid of the nops earlier */
 170                         ins1 = bb1->code;
 171                         while (ins1 && ins1->opcode == OP_NOP)
 172                                 ins1 = ins1->next;
 173                         ins2 = bb2->code;
 174                         while (ins2 && ins2->opcode == OP_NOP)
 175                                 ins2 = ins2->next;
 176                         if (!(ins1 && ins2 && ins1->dreg == ins2->dreg && ins1->dreg != -1))
 177                                 continue;
 178
 179                         simple = TRUE;
 180                         for (tmp = ins1->next; tmp; tmp = tmp->next)
 181                                 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_BR)))
 182                                         simple = FALSE;
 183
 184                         for (tmp = ins2->next; tmp; tmp = tmp->next)
 185                                 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_BR)))
 186                                         simple = FALSE;
 187
 188                         if (!simple)
 189                                 continue;
 190
 191                         /* We move ins1/ins2 before the compare so they should have no side effect */
 192                         if (!(MONO_INS_HAS_NO_SIDE_EFFECT (ins1) && MONO_INS_HAS_NO_SIDE_EFFECT (ins2)))
 193                                 continue;
 194
 195                         if (bb->last_ins && (bb->last_ins->opcode == OP_BR_REG || bb->last_ins->opcode == OP_BR))
 196                                 continue;
 197
 198                         /* Find the compare instruction */
 199                         /* FIXME: Optimize this using prev */
 200                         prev = NULL;
 201                         compare = bb->code;
 202                         g_assert (compare);
 203                         while (compare->next && !MONO_IS_COND_BRANCH_OP (compare->next)) {
 204                                 prev = compare;
 205                                 compare = compare->next;
 206                         }
 207                         g_assert (compare->next && MONO_IS_COND_BRANCH_OP (compare->next));
 208                         branch = compare->next;
 209
 210                         /* Moving ins1/ins2 could change the comparison */
 211                         /* FIXME: */
 212                         if (!((compare->sreg1 != ins1->dreg) && (compare->sreg2 != ins1->dreg)))
 213                                 continue;
 214
 215                         /* FIXME: */
 216                         comp_type = mono_opcode_to_type (branch->opcode, compare->opcode);
 217                         if (!((comp_type == CMP_TYPE_I) || (comp_type == CMP_TYPE_L)))
 218                                 continue;
 219
 220                         /* FIXME: */
 221                         /* ins->type might not be set */
 222                         if (INS_INFO (ins1->opcode) [MONO_INST_DEST] != 'i')
 223                                 continue;
 224
 225                         if (cfg->verbose_level > 2) {
 226                                 printf ("\tBranch -> CMove optimization in BB%d on\n", bb->block_num);
 227                                 printf ("\t\t"); mono_print_ins (compare);
 228                                 printf ("\t\t"); mono_print_ins (compare->next);
 229                                 printf ("\t\t"); mono_print_ins (ins1);
 230                                 printf ("\t\t"); mono_print_ins (ins2);
 231                         }
 232
 233                         changed = TRUE;
 234
 235                         //printf ("HIT!\n");
 236
 237                         /* Assignments to the return register must remain at the end of bbs */
 238                         if (cfg->ret)
 239                                 ret = ins1->dreg == cfg->ret->dreg;
 240                         else
 241                                 ret = FALSE;
 242
 243                         tmp_reg = mono_alloc_dreg (cfg, STACK_I4);
 244                         dreg = ins1->dreg;
 245
 246                         /* Rewrite ins1 to emit to tmp_reg */
 247                         ins1->dreg = tmp_reg;
 248
 249                         if (ret) {
 250                                 dreg = mono_alloc_dreg (cfg, STACK_I4);
 251                                 ins2->dreg = dreg;
 252                         }
 253
 254                         /* Remove ins1/ins2 from bb1/bb2 */
 255                         MONO_REMOVE_INS (bb1, ins1);
 256                         MONO_REMOVE_INS (bb2, ins2);
 257
 258                         /* Move ins1 and ins2 before the comparison */
 259                         /* ins1 comes first to avoid ins1 overwriting an argument of ins2 */
 260                         mono_bblock_insert_before_ins (bb, compare, ins2);
 261                         mono_bblock_insert_before_ins (bb, ins2, ins1);
 262
 263                         /* Add cmov instruction */
 264                         MONO_INST_NEW (cfg, cmov, OP_NOP);
 265                         cmov->dreg = dreg;
 266                         cmov->sreg1 = dreg;
 267                         cmov->sreg2 = tmp_reg;
 268                         switch (mono_opcode_to_type (branch->opcode, compare->opcode)) {
 269                         case CMP_TYPE_I:
 270                                 cmov->opcode = int_cmov_opcodes [mono_opcode_to_cond (branch->opcode)];
 271                                 break;
 272                         case CMP_TYPE_L:
 273                                 cmov->opcode = long_cmov_opcodes [mono_opcode_to_cond (branch->opcode)];
 274                                 break;
 275                         default:
 276                                 g_assert_not_reached ();
 277                         }
 278                         mono_bblock_insert_after_ins (bb, compare, cmov);
 279
 280                         if (ret) {
 281                                 /* Add an extra move */
 282                                 MONO_INST_NEW (cfg, move, OP_MOVE);
 283                                 move->dreg = cfg->ret->dreg;
 284                                 move->sreg1 = dreg;
 285                                 mono_bblock_insert_after_ins (bb, cmov, move);
 286                         }
 287
 288                         /* Rewrite the branch */
 289                         branch->opcode = OP_BR;
 290                         branch->inst_target_bb = bb1->out_bb [0];
 291                         mono_link_bblock (cfg, bb, branch->inst_target_bb);
 292
 293                         /* Reorder bblocks */
 294                         mono_unlink_bblock (cfg, bb, bb1);
 295                         mono_unlink_bblock (cfg, bb, bb2);
 296                         mono_unlink_bblock (cfg, bb1, bb1->out_bb [0]);
 297                         mono_unlink_bblock (cfg, bb2, bb2->out_bb [0]);
 298                         mono_remove_bblock (cfg, bb1);
 299                         mono_remove_bblock (cfg, bb2);
 300
 301                         /* Merge bb and its successor if possible */
 302                         if ((bb->out_bb [0]->in_count == 1) && (bb->out_bb [0] != cfg->bb_exit) &&
 303                                 (bb->region == bb->out_bb [0]->region)) {
 304                                 mono_merge_basic_blocks (cfg, bb, bb->out_bb [0]);
 305                                 goto restart;
 306                         }
 307                 }
 308
 309                 /* Look for the IR code generated from if (cond) <var> <- <a>
 310                  * which is:
 311                  * BB:
 312                  * b<cond> [BB1BB2]
 313                  * BB1:
 314                  * <var> <- <a>
 315                  * br BB2
 316                  */
 317
 318                 if ((bb2->in_count == 1 && bb2->out_count == 1 && bb2->out_bb [0] == bb1) ||
 319                         (bb1->in_count == 1 && bb1->out_count == 1 && bb1->out_bb [0] == bb2)) {
 320                         MonoInst *prev, *compare, *branch, *ins1, *cmov, *tmp;
 321                         gboolean simple;
 322                         int dreg, tmp_reg;
 323                         CompType comp_type;
 324                         CompRelation cond;
 325                         MonoBasicBlock *next_bb, *code_bb;
 326
 327                         /* code_bb is the bblock containing code, next_bb is the successor bblock */
 328                         if (bb2->in_count == 1 && bb2->out_count == 1 && bb2->out_bb [0] == bb1) {
 329                                 code_bb = bb2;
 330                                 next_bb = bb1;
 331                         } else {
 332                                 code_bb = bb1;
 333                                 next_bb = bb2;
 334                         }
 335
 336                         ins1 = code_bb->code;
 337
 338                         if (!ins1)
 339                                 continue;
 340
 341                         /* Check that code_bb is simple */
 342                         simple = TRUE;
 343                         for (tmp = ins1->next; tmp; tmp = tmp->next)
 344                                 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_BR)))
 345                                         simple = FALSE;
 346
 347                         if (!simple)
 348                                 continue;
 349
 350                         /* We move ins1 before the compare so it should have no side effect */
 351                         if (!MONO_INS_HAS_NO_SIDE_EFFECT (ins1))
 352                                 continue;
 353
 354                         if (bb->last_ins && bb->last_ins->opcode == OP_BR_REG)
 355                                 continue;
 356
 357                         /* Find the compare instruction */
 358                         /* FIXME: Optimize this using prev */
 359                         prev = NULL;
 360                         compare = bb->code;
 361                         g_assert (compare);
 362                         while (compare->next && !MONO_IS_COND_BRANCH_OP (compare->next)) {
 363                                 prev = compare;
 364                                 compare = compare->next;
 365                         }
 366                         g_assert (compare->next && MONO_IS_COND_BRANCH_OP (compare->next));
 367                         branch = compare->next;
 368
 369                         /* FIXME: */
 370                         comp_type = mono_opcode_to_type (branch->opcode, compare->opcode);
 371                         if (!((comp_type == CMP_TYPE_I) || (comp_type == CMP_TYPE_L)))
 372                                 continue;
 373
 374                         /* FIXME: */
 375                         /* ins->type might not be set */
 376                         if (INS_INFO (ins1->opcode) [MONO_INST_DEST] != 'i')
 377                                 continue;
 378
 379                         /* FIXME: */
 380                         if (cfg->ret && ins1->dreg == cfg->ret->dreg)
 381                                 continue;
 382
 383                         if (cfg->verbose_level > 2) {
 384                                 printf ("\tBranch -> CMove optimization (2) in BB%d on\n", bb->block_num);
 385                                 printf ("\t\t"); mono_print_ins (compare);
 386                                 printf ("\t\t"); mono_print_ins (compare->next);
 387                                 printf ("\t\t"); mono_print_ins (ins1);
 388                         }
 389
 390                         changed = TRUE;
 391
 392                         //printf ("HIT!\n");
 393
 394                         tmp_reg = mono_alloc_dreg (cfg, STACK_I4);
 395                         dreg = ins1->dreg;
 396
 397                         /* Rewrite ins1 to emit to tmp_reg */
 398                         ins1->dreg = tmp_reg;
 399
 400                         /* Remove ins1 from code_bb */
 401                         MONO_REMOVE_INS (code_bb, ins1);
 402
 403                         /* Move ins1 before the comparison */
 404                         mono_bblock_insert_before_ins (bb, compare, ins1);
 405
 406                         /* Add cmov instruction */
 407                         MONO_INST_NEW (cfg, cmov, OP_NOP);
 408                         cmov->dreg = dreg;
 409                         cmov->sreg1 = dreg;
 410                         cmov->sreg2 = tmp_reg;
 411                         cond = mono_opcode_to_cond (branch->opcode);
 412                         if (branch->inst_false_bb == code_bb)
 413                                 cond = mono_negate_cond (cond);
 414                         switch (mono_opcode_to_type (branch->opcode, compare->opcode)) {
 415                         case CMP_TYPE_I:
 416                                 cmov->opcode = int_cmov_opcodes [cond];
 417                                 break;
 418                         case CMP_TYPE_L:
 419                                 cmov->opcode = long_cmov_opcodes [cond];
 420                                 break;
 421                         default:
 422                                 g_assert_not_reached ();
 423                         }
 424                         mono_bblock_insert_after_ins (bb, compare, cmov);
 425
 426                         /* Rewrite the branch */
 427                         branch->opcode = OP_BR;
 428                         branch->inst_target_bb = next_bb;
 429                         mono_link_bblock (cfg, bb, branch->inst_target_bb);
 430
 431                         /* Nullify the branch at the end of code_bb */
 432                         if (code_bb->code) {
 433                                 branch = code_bb->code;
 434                                 MONO_DELETE_INS (code_bb, branch);
 435                         }
 436
 437                         /* Reorder bblocks */
 438                         mono_unlink_bblock (cfg, bb, code_bb);
 439                         mono_unlink_bblock (cfg, code_bb, next_bb);
 440
 441                         /* Merge bb and its successor if possible */
 442                         if ((bb->out_bb [0]->in_count == 1) && (bb->out_bb [0] != cfg->bb_exit) &&
 443                                 (bb->region == bb->out_bb [0]->region)) {
 444                                 mono_merge_basic_blocks (cfg, bb, bb->out_bb [0]);
 445                                 goto restart;
 446                         }
 447                 }
 448         }
 449
 450 #if 0
 451         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 452                 MonoBasicBlock *bb1, *bb2;
 453                 MonoInst *prev, *compare, *branch, *ins1, *ins2, *cmov, *move, *tmp;
 454                 gboolean simple, ret;
 455                 int dreg, tmp_reg;
 456                 CompType comp_type;
 457
 458                 /* Look for the IR code generated from if (cond) <var> <- <a>
 459                  * after branch opts which is:
 460                  * BB:
 461                  * compare
 462                  * b<cond> [BB1]
 463                  * <var> <- <a>
 464                  * BB1:
 465                  */
 466                 if (!(bb->out_count == 1 && bb->extended && bb->code && bb->code->next && bb->code->next->next))
 467                         continue;
 468
 469                 mono_print_bb (bb, "");
 470
 471                 /* Find the compare instruction */
 472                 prev = NULL;
 473                 compare = bb->code;
 474                 g_assert (compare);
 475                 while (compare->next->next && compare->next->next != bb->last_ins) {
 476                         prev = compare;
 477                         compare = compare->next;
 478                 }
 479                 branch = compare->next;
 480                 if (!MONO_IS_COND_BRANCH_OP (branch))
 481                         continue;
 482         }
 483 #endif
 484
 485         if (changed) {
 486                 if (cfg->opt & MONO_OPT_BRANCH)
 487                         mono_optimize_branches (cfg);
 488                 /* Merging bblocks could make some variables local */
 489                 mono_handle_global_vregs (cfg);
 490                 if (cfg->opt & (MONO_OPT_CONSPROP | MONO_OPT_COPYPROP))
 491                         mono_local_cprop2 (cfg);
 492                 mono_local_deadce (cfg);
 493         }
 494 #endif
 495 }
 496
 497 void
 498 mono_nullify_basic_block (MonoBasicBlock *bb)
 499 {
 500         bb->in_count = 0;
 501         bb->out_count = 0;
 502         bb->in_bb = NULL;
 503         bb->out_bb = NULL;
 504         bb->next_bb = NULL;
 505         bb->code = bb->last_ins = NULL;
 506         bb->cil_code = NULL;
 507 }
 508
 509 static void
 510 replace_out_block (MonoBasicBlock *bb, MonoBasicBlock *orig,  MonoBasicBlock *repl)
 511 {
 512         int i;
 513
 514         for (i = 0; i < bb->out_count; i++) {
 515                 MonoBasicBlock *ob = bb->out_bb [i];
 516                 if (ob == orig) {
 517                         if (!repl) {
 518                                 if (bb->out_count > 1) {
 519                                         bb->out_bb [i] = bb->out_bb [bb->out_count - 1];
 520                                 }
 521                                 bb->out_count--;
 522                         } else {
 523                                 bb->out_bb [i] = repl;
 524                         }
 525                 }
 526         }
 527 }
 528
 529 static void
 530 replace_in_block (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl)
 531 {
 532         int i;
 533
 534         for (i = 0; i < bb->in_count; i++) {
 535                 MonoBasicBlock *ib = bb->in_bb [i];
 536                 if (ib == orig) {
 537                         if (!repl) {
 538                                 if (bb->in_count > 1) {
 539                                         bb->in_bb [i] = bb->in_bb [bb->in_count - 1];
 540                                 }
 541                                 bb->in_count--;
 542                         } else {
 543                                 bb->in_bb [i] = repl;
 544                         }
 545                 }
 546         }
 547 }
 548
 549 static void
 550 replace_out_block_in_code (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl) {
 551         MonoInst *ins;
 552
 553         for (ins = bb->code; ins != NULL; ins = ins->next) {
 554                 switch (ins->opcode) {
 555                 case OP_BR:
 556                         if (ins->inst_target_bb == orig)
 557                                 ins->inst_target_bb = repl;
 558                         break;
 559                 case OP_CALL_HANDLER:
 560                         if (ins->inst_target_bb == orig)
 561                                 ins->inst_target_bb = repl;
 562                         break;
 563                 case OP_SWITCH: {
 564                         int i;
 565                         int n = GPOINTER_TO_INT (ins->klass);
 566                         for (i = 0; i < n; i++ ) {
 567                                 if (ins->inst_many_bb [i] == orig)
 568                                         ins->inst_many_bb [i] = repl;
 569                         }
 570                         break;
 571                 }
 572                 default:
 573                         if (MONO_IS_COND_BRANCH_OP (ins)) {
 574                                 if (ins->inst_true_bb == orig)
 575                                         ins->inst_true_bb = repl;
 576                                 if (ins->inst_false_bb == orig)
 577                                         ins->inst_false_bb = repl;
 578                         } else if (MONO_IS_JUMP_TABLE (ins)) {
 579                                 int i;
 580                                 MonoJumpInfoBBTable *table = MONO_JUMP_TABLE_FROM_INS (ins);
 581                                 for (i = 0; i < table->table_size; i++ ) {
 582                                         if (table->table [i] == orig)
 583                                                 table->table [i] = repl;
 584                                 }
 585                         }
 586
 587                         break;
 588                 }
 589         }
 590 }
 591
 592 /**
 593   * Check if a bb is useless (is just made of NOPs and ends with an
 594   * unconditional branch, or nothing).
 595   * If it is so, unlink it from the CFG and nullify it, and return TRUE.
 596   * Otherwise, return FALSE;
 597   */
 598 static gboolean
 599 remove_block_if_useless (MonoCompile *cfg, MonoBasicBlock *bb, MonoBasicBlock *previous_bb) {
 600         MonoBasicBlock *target_bb = NULL;
 601         MonoInst *inst;
 602
 603         /* Do not touch handlers */
 604         if (bb->region != -1) {
 605                 bb->not_useless = TRUE;
 606                 return FALSE;
 607         }
 608
 609         MONO_BB_FOR_EACH_INS (bb, inst) {
 610                 switch (inst->opcode) {
 611                 case OP_NOP:
 612                         break;
 613                 case OP_BR:
 614                         target_bb = inst->inst_target_bb;
 615                         break;
 616                 default:
 617                         bb->not_useless = TRUE;
 618                         return FALSE;
 619                 }
 620         }
 621
 622         if (target_bb == NULL) {
 623                 if ((bb->out_count == 1) && (bb->out_bb [0] == bb->next_bb)) {
 624                         target_bb = bb->next_bb;
 625                 } else {
 626                         /* Do not touch empty BBs that do not "fall through" to their next BB (like the exit BB) */
 627                         return FALSE;
 628                 }
 629         }
 630
 631         /* Do not touch BBs following a switch (they are the "default" branch) */
 632         if ((previous_bb->last_ins != NULL) && (previous_bb->last_ins->opcode == OP_SWITCH)) {
 633                 return FALSE;
 634         }
 635
 636         /* Do not touch BBs following the entry BB and jumping to something that is not */
 637         /* thiry "next" bb (the entry BB cannot contain the branch) */
 638         if ((previous_bb == cfg->bb_entry) && (bb->next_bb != target_bb)) {
 639                 return FALSE;
 640         }
 641
 642         /*
 643          * Do not touch BBs following a try block as the code in
 644          * mini_method_compile needs them to compute the length of the try block.
 645          */
 646         if (MONO_BBLOCK_IS_IN_REGION (previous_bb, MONO_REGION_TRY))
 647                 return FALSE;
 648
 649         /* Check that there is a target BB, and that bb is not an empty loop (Bug 75061) */
 650         if ((target_bb != NULL) && (target_bb != bb)) {
 651                 int i;
 652
 653                 if (cfg->verbose_level > 1) {
 654                         printf ("remove_block_if_useless, removed BB%d\n", bb->block_num);
 655                 }
 656
 657                 /* unlink_bblock () modifies the bb->in_bb array so can't use a for loop here */
 658                 while (bb->in_count) {
 659                         MonoBasicBlock *in_bb = bb->in_bb [0];
 660                         mono_unlink_bblock (cfg, in_bb, bb);
 661                         mono_link_bblock (cfg, in_bb, target_bb);
 662                         replace_out_block_in_code (in_bb, bb, target_bb);
 663                 }
 664
 665                 mono_unlink_bblock (cfg, bb, target_bb);
 666
 667                 if ((previous_bb != cfg->bb_entry) &&
 668                                 (previous_bb->region == bb->region) &&
 669                                 ((previous_bb->last_ins == NULL) ||
 670                                 ((previous_bb->last_ins->opcode != OP_BR) &&
 671                                 (! (MONO_IS_COND_BRANCH_OP (previous_bb->last_ins))) &&
 672                                 (previous_bb->last_ins->opcode != OP_SWITCH)))) {
 673                         for (i = 0; i < previous_bb->out_count; i++) {
 674                                 if (previous_bb->out_bb [i] == target_bb) {
 675                                         MonoInst *jump;
 676                                         MONO_INST_NEW (cfg, jump, OP_BR);
 677                                         MONO_ADD_INS (previous_bb, jump);
 678                                         jump->cil_code = previous_bb->cil_code;
 679                                         jump->inst_target_bb = target_bb;
 680                                         break;
 681                                 }
 682                         }
 683                 }
 684
 685                 previous_bb->next_bb = bb->next_bb;
 686                 mono_nullify_basic_block (bb);
 687
 688                 return TRUE;
 689         } else {
 690                 return FALSE;
 691         }
 692 }
 693
 694 void
 695 mono_merge_basic_blocks (MonoCompile *cfg, MonoBasicBlock *bb, MonoBasicBlock *bbn)
 696 {
 697         MonoInst *inst;
 698         MonoBasicBlock *prev_bb;
 699         int i;
 700
 701         bb->has_array_access |= bbn->has_array_access;
 702         bb->extended |= bbn->extended;
 703
 704         mono_unlink_bblock (cfg, bb, bbn);
 705         for (i = 0; i < bbn->out_count; ++i)
 706                 mono_link_bblock (cfg, bb, bbn->out_bb [i]);
 707         while (bbn->out_count)
 708                 mono_unlink_bblock (cfg, bbn, bbn->out_bb [0]);
 709
 710         /* Handle the branch at the end of the bb */
 711         for (inst = bb->code; inst != NULL; inst = inst->next) {
 712                 if (inst->opcode == OP_CALL_HANDLER) {
 713                         g_assert (inst->inst_target_bb == bbn);
 714                         NULLIFY_INS (inst);
 715                 }
 716                 if (MONO_IS_JUMP_TABLE (inst)) {
 717                         int i;
 718                         MonoJumpInfoBBTable *table = MONO_JUMP_TABLE_FROM_INS (inst);
 719                         for (i = 0; i < table->table_size; i++ ) {
 720                                 /* Might be already NULL from a previous merge */
 721                                 if (table->table [i])
 722                                         g_assert (table->table [i] == bbn);
 723                                 table->table [i] = NULL;
 724                         }
 725                         /* Can't nullify this as later instructions depend on it */
 726                 }
 727         }
 728         if (bb->last_ins && MONO_IS_COND_BRANCH_OP (bb->last_ins)) {
 729                 g_assert (bb->last_ins->inst_false_bb == bbn);
 730                 bb->last_ins->inst_false_bb = NULL;
 731                 bb->extended = TRUE;
 732         } else if (bb->last_ins && MONO_IS_BRANCH_OP (bb->last_ins)) {
 733                 NULLIFY_INS (bb->last_ins);
 734         }
 735
 736         if (bb->last_ins) {
 737                 if (bbn->code) {
 738                         bb->last_ins->next = bbn->code;
 739                         bbn->code->prev = bb->last_ins;
 740                         bb->last_ins = bbn->last_ins;
 741                 }
 742         } else {
 743                 bb->code = bbn->code;
 744                 bb->last_ins = bbn->last_ins;
 745         }
 746         for (prev_bb = cfg->bb_entry; prev_bb && prev_bb->next_bb != bbn; prev_bb = prev_bb->next_bb)
 747                 ;
 748         if (prev_bb) {
 749                 prev_bb->next_bb = bbn->next_bb;
 750         } else {
 751                 /* bbn might not be in the bb list yet */
 752                 if (bb->next_bb == bbn)
 753                         bb->next_bb = bbn->next_bb;
 754         }
 755         mono_nullify_basic_block (bbn);
 756 }
 757
 758 static void
 759 move_basic_block_to_end (MonoCompile *cfg, MonoBasicBlock *bb)
 760 {
 761         MonoBasicBlock *bbn, *next;
 762
 763         next = bb->next_bb;
 764
 765         /* Find the previous */
 766         for (bbn = cfg->bb_entry; bbn->next_bb && bbn->next_bb != bb; bbn = bbn->next_bb)
 767                 ;
 768         if (bbn->next_bb) {
 769                 bbn->next_bb = bb->next_bb;
 770         }
 771
 772         /* Find the last */
 773         for (bbn = cfg->bb_entry; bbn->next_bb; bbn = bbn->next_bb)
 774                 ;
 775         bbn->next_bb = bb;
 776         bb->next_bb = NULL;
 777
 778         /* Add a branch */
 779         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))))) {
 780                 MonoInst *ins;
 781
 782                 MONO_INST_NEW (cfg, ins, OP_BR);
 783                 MONO_ADD_INS (bb, ins);
 784                 mono_link_bblock (cfg, bb, next);
 785                 ins->inst_target_bb = next;
 786         }
 787 }
 788
 789 /*
 790  * mono_remove_block:
 791  *
 792  *   Remove BB from the control flow graph
 793  */
 794 void
 795 mono_remove_bblock (MonoCompile *cfg, MonoBasicBlock *bb)
 796 {
 797         MonoBasicBlock *tmp_bb;
 798
 799         for (tmp_bb = cfg->bb_entry; tmp_bb && tmp_bb->next_bb != bb; tmp_bb = tmp_bb->next_bb)
 800                 ;
 801
 802         g_assert (tmp_bb);
 803         tmp_bb->next_bb = bb->next_bb;
 804 }
 805
 806 void
 807 mono_remove_critical_edges (MonoCompile *cfg)
 808 {
 809         MonoBasicBlock *bb;
 810         MonoBasicBlock *previous_bb;
 811
 812         if (cfg->verbose_level > 3) {
 813                 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 814                         int i;
 815                         printf ("remove_critical_edges, BEFORE BB%d (in:", bb->block_num);
 816                         for (i = 0; i < bb->in_count; i++) {
 817                                 printf (" %d", bb->in_bb [i]->block_num);
 818                         }
 819                         printf (") (out:");
 820                         for (i = 0; i < bb->out_count; i++) {
 821                                 printf (" %d", bb->out_bb [i]->block_num);
 822                         }
 823                         printf (")");
 824                         if (bb->last_ins != NULL) {
 825                                 printf (" ");
 826                                 mono_print_tree (bb->last_ins);
 827                         }
 828                         printf ("\n");
 829                 }
 830         }
 831
 832         for (previous_bb = cfg->bb_entry, bb = previous_bb->next_bb; bb != NULL; previous_bb = previous_bb->next_bb, bb = bb->next_bb) {
 833                 if (bb->in_count > 1) {
 834                         int in_bb_index;
 835                         for (in_bb_index = 0; in_bb_index < bb->in_count; in_bb_index++) {
 836                                 MonoBasicBlock *in_bb = bb->in_bb [in_bb_index];
 837                                 if (in_bb->out_count > 1) {
 838                                         MonoBasicBlock *new_bb = mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoBasicBlock));
 839                                         new_bb->block_num = cfg->num_bblocks++;
 840 //                                      new_bb->real_offset = bb->real_offset;
 841                                         new_bb->region = bb->region;
 842
 843                                         /* Do not alter the CFG while altering the BB list */
 844                                         if (previous_bb->region == bb->region) {
 845                                                 if (previous_bb != cfg->bb_entry) {
 846                                                         /* If previous_bb "followed through" to bb, */
 847                                                         /* keep it linked with a OP_BR */
 848                                                         if ((previous_bb->last_ins == NULL) ||
 849                                                                         ((previous_bb->last_ins->opcode != OP_BR) &&
 850                                                                         (! (MONO_IS_COND_BRANCH_OP (previous_bb->last_ins))) &&
 851                                                                         (previous_bb->last_ins->opcode != OP_SWITCH))) {
 852                                                                 int i;
 853                                                                 /* Make sure previous_bb really falls through bb */
 854                                                                 for (i = 0; i < previous_bb->out_count; i++) {
 855                                                                         if (previous_bb->out_bb [i] == bb) {
 856                                                                                 MonoInst *jump;
 857                                                                                 MONO_INST_NEW (cfg, jump, OP_BR);
 858                                                                                 MONO_ADD_INS (previous_bb, jump);
 859                                                                                 jump->cil_code = previous_bb->cil_code;
 860                                                                                 jump->inst_target_bb = bb;
 861                                                                                 break;
 862                                                                         }
 863                                                                 }
 864                                                         }
 865                                                 } else {
 866                                                         /* We cannot add any inst to the entry BB, so we must */
 867                                                         /* put a new BB in the middle to hold the OP_BR */
 868                                                         MonoInst *jump;
 869                                                         MonoBasicBlock *new_bb_after_entry = mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoBasicBlock));
 870                                                         new_bb_after_entry->block_num = cfg->num_bblocks++;
 871 //                                                      new_bb_after_entry->real_offset = bb->real_offset;
 872                                                         new_bb_after_entry->region = bb->region;
 873
 874                                                         MONO_INST_NEW (cfg, jump, OP_BR);
 875                                                         MONO_ADD_INS (new_bb_after_entry, jump);
 876                                                         jump->cil_code = bb->cil_code;
 877                                                         jump->inst_target_bb = bb;
 878
 879                                                         previous_bb->next_bb = new_bb_after_entry;
 880                                                         previous_bb = new_bb_after_entry;
 881
 882                                                         if (cfg->verbose_level > 2) {
 883                                                                 printf ("remove_critical_edges, added helper BB%d jumping to BB%d\n", new_bb_after_entry->block_num, bb->block_num);
 884                                                         }
 885                                                 }
 886                                         }
 887
 888                                         /* Insert new_bb in the BB list */
 889                                         previous_bb->next_bb = new_bb;
 890                                         new_bb->next_bb = bb;
 891                                         previous_bb = new_bb;
 892
 893                                         /* Setup in_bb and out_bb */
 894                                         new_bb->in_bb = mono_mempool_alloc ((cfg)->mempool, sizeof (MonoBasicBlock*));
 895                                         new_bb->in_bb [0] = in_bb;
 896                                         new_bb->in_count = 1;
 897                                         new_bb->out_bb = mono_mempool_alloc ((cfg)->mempool, sizeof (MonoBasicBlock*));
 898                                         new_bb->out_bb [0] = bb;
 899                                         new_bb->out_count = 1;
 900
 901                                         /* Relink in_bb and bb to (from) new_bb */
 902                                         replace_out_block (in_bb, bb, new_bb);
 903                                         replace_out_block_in_code (in_bb, bb, new_bb);
 904                                         replace_in_block (bb, in_bb, new_bb);
 905
 906                                         if (cfg->verbose_level > 2) {
 907                                                 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);
 908                                         }
 909                                 }
 910                         }
 911                 }
 912         }
 913
 914         if (cfg->verbose_level > 3) {
 915                 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 916                         int i;
 917                         printf ("remove_critical_edges, AFTER BB%d (in:", bb->block_num);
 918                         for (i = 0; i < bb->in_count; i++) {
 919                                 printf (" %d", bb->in_bb [i]->block_num);
 920                         }
 921                         printf (") (out:");
 922                         for (i = 0; i < bb->out_count; i++) {
 923                                 printf (" %d", bb->out_bb [i]->block_num);
 924                         }
 925                         printf (")");
 926                         if (bb->last_ins != NULL) {
 927                                 printf (" ");
 928                                 mono_print_tree (bb->last_ins);
 929                         }
 930                         printf ("\n");
 931                 }
 932         }
 933 }
 934
 935 /* checks that a and b represent the same instructions, conservatively,
 936  * it can return FALSE also for two trees that are equal.
 937  * FIXME: also make sure there are no side effects.
 938  */
 939 static int
 940 same_trees (MonoInst *a, MonoInst *b)
 941 {
 942         int arity;
 943         if (a->opcode != b->opcode)
 944                 return FALSE;
 945         arity = mono_burg_arity [a->opcode];
 946         if (arity == 1) {
 947                 if (a->ssa_op == b->ssa_op && a->ssa_op == MONO_SSA_LOAD && a->inst_i0 == b->inst_i0)
 948                         return TRUE;
 949                 return same_trees (a->inst_left, b->inst_left);
 950         } else if (arity == 2) {
 951                 return same_trees (a->inst_left, b->inst_left) && same_trees (a->inst_right, b->inst_right);
 952         } else if (arity == 0) {
 953                 switch (a->opcode) {
 954                 case OP_ICONST:
 955                         return a->inst_c0 == b->inst_c0;
 956                 default:
 957                         return FALSE;
 958                 }
 959         }
 960         return FALSE;
 961 }
 962
 963 static int
 964 get_unsigned_condbranch (int opcode)
 965 {
 966         switch (opcode) {
 967         case CEE_BLE: return CEE_BLE_UN;
 968         case CEE_BLT: return CEE_BLT_UN;
 969         case CEE_BGE: return CEE_BGE_UN;
 970         case CEE_BGT: return CEE_BGT_UN;
 971         }
 972         g_assert_not_reached ();
 973         return 0;
 974 }
 975
 976 static int
 977 tree_is_unsigned (MonoInst* ins) {
 978         switch (ins->opcode) {
 979         case OP_ICONST:
 980                 return (int)ins->inst_c0 >= 0;
 981         /* array lengths are positive as are string sizes */
 982         case CEE_LDLEN:
 983         case OP_STRLEN:
 984                 return TRUE;
 985         case CEE_CONV_U1:
 986         case CEE_CONV_U2:
 987         case CEE_CONV_U4:
 988         case CEE_CONV_OVF_U1:
 989         case CEE_CONV_OVF_U2:
 990         case CEE_CONV_OVF_U4:
 991                 return TRUE;
 992         case CEE_LDIND_U1:
 993         case CEE_LDIND_U2:
 994         case CEE_LDIND_U4:
 995                 return TRUE;
 996         default:
 997                 return FALSE;
 998         }
 999 }
1000
1001 /* check if an unsigned compare can be used instead of two signed compares
1002  * for (val < 0 || val > limit) conditionals.
1003  * Returns TRUE if the optimization has been applied.
1004  * Note that this can't be applied if the second arg is not positive...
1005  */
1006 static int
1007 try_unsigned_compare (MonoCompile *cfg, MonoBasicBlock *bb)
1008 {
1009         MonoBasicBlock *truet, *falset;
1010         MonoInst *cmp_inst = bb->last_ins->inst_left;
1011         MonoInst *condb;
1012         if (!cmp_inst->inst_right->inst_c0 == 0)
1013                 return FALSE;
1014         truet = bb->last_ins->inst_true_bb;
1015         falset = bb->last_ins->inst_false_bb;
1016         if (falset->in_count != 1)
1017                 return FALSE;
1018         condb = falset->last_ins;
1019         /* target bb must have one instruction */
1020         if (!condb || (condb != falset->code))
1021                 return FALSE;
1022         if ((((condb->opcode == CEE_BLE || condb->opcode == CEE_BLT) && (condb->inst_false_bb == truet))
1023                         || ((condb->opcode == CEE_BGE || condb->opcode == CEE_BGT) && (condb->inst_true_bb == truet)))
1024                         && same_trees (cmp_inst->inst_left, condb->inst_left->inst_left)) {
1025                 if (!tree_is_unsigned (condb->inst_left->inst_right))
1026                         return FALSE;
1027                 condb->opcode = get_unsigned_condbranch (condb->opcode);
1028                 /* change the original condbranch to just point to the new unsigned check */
1029                 bb->last_ins->opcode = OP_BR;
1030                 bb->last_ins->inst_target_bb = falset;
1031                 replace_out_block (bb, truet, NULL);
1032                 replace_in_block (truet, bb, NULL);
1033                 return TRUE;
1034         }
1035         return FALSE;
1036 }
1037
1038 /*
1039  * Optimizes the branches on the Control Flow Graph
1040  *
1041  */
1042 void
1043 mono_optimize_branches (MonoCompile *cfg)
1044 {
1045         int i, changed = FALSE;
1046         MonoBasicBlock *bb, *bbn;
1047         guint32 niterations;
1048
1049         /*
1050          * Some crazy loops could cause the code below to go into an infinite
1051          * loop, see bug #53003 for an example. To prevent this, we put an upper
1052          * bound on the number of iterations.
1053          */
1054         if (cfg->num_bblocks > 1000)
1055                 niterations = cfg->num_bblocks * 2;
1056         else
1057                 niterations = 1000;
1058
1059         do {
1060                 MonoBasicBlock *previous_bb;
1061                 changed = FALSE;
1062                 niterations --;
1063
1064                 /* we skip the entry block (exit is handled specially instead ) */
1065                 for (previous_bb = cfg->bb_entry, bb = cfg->bb_entry->next_bb; bb; previous_bb = bb, bb = bb->next_bb) {
1066                         /* dont touch code inside exception clauses */
1067                         if (bb->region != -1)
1068                                 continue;
1069
1070                         if (!bb->not_useless && remove_block_if_useless (cfg, bb, previous_bb)) {
1071                                 changed = TRUE;
1072                                 continue;
1073                         }
1074
1075                         if ((bbn = bb->next_bb) && bbn->in_count == 0 && bb->region == bbn->region) {
1076                                 if (cfg->verbose_level > 2)
1077                                         g_print ("nullify block triggered %d\n", bbn->block_num);
1078
1079                                 bb->next_bb = bbn->next_bb;
1080
1081                                 for (i = 0; i < bbn->out_count; i++)
1082                                         replace_in_block (bbn->out_bb [i], bbn, NULL);
1083
1084                                 mono_nullify_basic_block (bbn);
1085                                 changed = TRUE;
1086                         }
1087
1088                         if (bb->out_count == 1) {
1089                                 bbn = bb->out_bb [0];
1090
1091                                 /* conditional branches where true and false targets are the same can be also replaced with OP_BR */
1092                                 if (bb->last_ins && (bb->last_ins->opcode != OP_BR) && MONO_IS_COND_BRANCH_OP (bb->last_ins)) {
1093                                         if (!cfg->new_ir) {
1094                                                 MonoInst *pop;
1095                                                 MONO_INST_NEW (cfg, pop, CEE_POP);
1096                                                 pop->inst_left = bb->last_ins->inst_left->inst_left;
1097                                                 mono_add_ins_to_end (bb, pop);
1098                                                 MONO_INST_NEW (cfg, pop, CEE_POP);
1099                                                 pop->inst_left = bb->last_ins->inst_left->inst_right;
1100                                                 mono_add_ins_to_end (bb, pop);
1101                                         }
1102                                         bb->last_ins->opcode = OP_BR;
1103                                         bb->last_ins->inst_target_bb = bb->last_ins->inst_true_bb;
1104                                         changed = TRUE;
1105                                         if (cfg->verbose_level > 2)
1106                                                 g_print ("cond branch removal triggered in %d %d\n", bb->block_num, bb->out_count);
1107                                 }
1108
1109                                 if (bb->region == bbn->region && bb->next_bb == bbn) {
1110                                         /* the block are in sequence anyway ... */
1111
1112                                         /* branches to the following block can be removed */
1113                                         if (bb->last_ins && bb->last_ins->opcode == OP_BR) {
1114                                                 bb->last_ins->opcode = OP_NOP;
1115                                                 changed = TRUE;
1116                                                 if (cfg->verbose_level > 2)
1117                                                         g_print ("br removal triggered %d -> %d\n", bb->block_num, bbn->block_num);
1118                                         }
1119
1120                                         if (bbn->in_count == 1 && !bb->extended) {
1121                                                 if (bbn != cfg->bb_exit) {
1122                                                         if (cfg->verbose_level > 2)
1123                                                                 g_print ("block merge triggered %d -> %d\n", bb->block_num, bbn->block_num);
1124                                                         mono_merge_basic_blocks (cfg, bb, bbn);
1125                                                         changed = TRUE;
1126                                                         continue;
1127                                                 }
1128
1129                                                 //mono_print_bb_code (bb);
1130                                         }
1131                                 }
1132                         }
1133
1134                         if ((bbn = bb->next_bb) && bbn->in_count == 0 && bb->region == bbn->region) {
1135                                 if (cfg->verbose_level > 2) {
1136                                         g_print ("nullify block triggered %d\n", bbn->block_num);
1137                                 }
1138                                 bb->next_bb = bbn->next_bb;
1139
1140                                 for (i = 0; i < bbn->out_count; i++)
1141                                         replace_in_block (bbn->out_bb [i], bbn, NULL);
1142
1143                                 mono_nullify_basic_block (bbn);
1144                                 changed = TRUE;
1145                                 continue;
1146                         }
1147
1148                         if (bb->out_count == 1) {
1149                                 bbn = bb->out_bb [0];
1150
1151                                 if (bb->last_ins && bb->last_ins->opcode == OP_BR) {
1152                                         bbn = bb->last_ins->inst_target_bb;
1153                                         if (bb->region == bbn->region && bbn->code && bbn->code->opcode == OP_BR &&
1154                                             bbn->code->inst_target_bb->region == bb->region) {
1155
1156                                                 if (cfg->verbose_level > 2)
1157                                                         g_print ("branch to branch triggered %d -> %d -> %d\n", bb->block_num, bbn->block_num, bbn->code->inst_target_bb->block_num);
1158
1159                                                 replace_in_block (bbn, bb, NULL);
1160                                                 replace_out_block (bb, bbn, bbn->code->inst_target_bb);
1161                                                 mono_link_bblock (cfg, bb, bbn->code->inst_target_bb);
1162                                                 bb->last_ins->inst_target_bb = bbn->code->inst_target_bb;
1163                                                 changed = TRUE;
1164                                                 continue;
1165                                         }
1166                                 }
1167                         } else if (bb->out_count == 2) {
1168                                 if (bb->last_ins && MONO_IS_COND_BRANCH_NOFP (bb->last_ins)) {
1169                                         int branch_result;
1170                                         MonoBasicBlock *taken_branch_target = NULL, *untaken_branch_target = NULL;
1171
1172                                         if (cfg->new_ir) {
1173                                                 if (bb->last_ins->flags & MONO_INST_CFOLD_TAKEN)
1174                                                         branch_result = BRANCH_TAKEN;
1175                                                 else if (bb->last_ins->flags & MONO_INST_CFOLD_NOT_TAKEN)
1176                                                         branch_result = BRANCH_NOT_TAKEN;
1177                                                 else
1178                                                         branch_result = BRANCH_UNDEF;
1179                                         }
1180                                         else
1181                                                 branch_result = mono_eval_cond_branch (bb->last_ins);
1182
1183                                         if (branch_result == BRANCH_TAKEN) {
1184                                                 taken_branch_target = bb->last_ins->inst_true_bb;
1185                                                 untaken_branch_target = bb->last_ins->inst_false_bb;
1186                                         } else if (branch_result == BRANCH_NOT_TAKEN) {
1187                                                 taken_branch_target = bb->last_ins->inst_false_bb;
1188                                                 untaken_branch_target = bb->last_ins->inst_true_bb;
1189                                         }
1190                                         if (taken_branch_target) {
1191                                                 /* if mono_eval_cond_branch () is ever taken to handle
1192                                                  * non-constant values to compare, issue a pop here.
1193                                                  */
1194                                                 bb->last_ins->opcode = OP_BR;
1195                                                 bb->last_ins->inst_target_bb = taken_branch_target;
1196                                                 if (!bb->extended)
1197                                                         mono_unlink_bblock (cfg, bb, untaken_branch_target);
1198                                                 changed = TRUE;
1199                                                 continue;
1200                                         }
1201                                         bbn = bb->last_ins->inst_true_bb;
1202                                         if (bb->region == bbn->region && bbn->code && bbn->code->opcode == OP_BR &&
1203                                             bbn->code->inst_target_bb->region == bb->region) {
1204                                                 if (cfg->verbose_level > 2)
1205                                                         g_print ("cbranch1 to branch triggered %d -> (%d) %d (0x%02x)\n",
1206                                                                  bb->block_num, bbn->block_num, bbn->code->inst_target_bb->block_num,
1207                                                                  bbn->code->opcode);
1208
1209                                                 /*
1210                                                  * Unlink, then relink bblocks to avoid various
1211                                                  * tricky situations when the two targets of the branch
1212                                                  * are equal, or will become equal after the change.
1213                                                  */
1214                                                 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1215                                                 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1216
1217                                                 bb->last_ins->inst_true_bb = bbn->code->inst_target_bb;
1218
1219                                                 mono_link_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1220                                                 mono_link_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1221
1222                                                 changed = TRUE;
1223                                                 continue;
1224                                         }
1225
1226                                         bbn = bb->last_ins->inst_false_bb;
1227                                         if (bbn && bb->region == bbn->region && bbn->code && bbn->code->opcode == OP_BR &&
1228                                             bbn->code->inst_target_bb->region == bb->region) {
1229                                                 if (cfg->verbose_level > 2)
1230                                                         g_print ("cbranch2 to branch triggered %d -> (%d) %d (0x%02x)\n",
1231                                                                  bb->block_num, bbn->block_num, bbn->code->inst_target_bb->block_num,
1232                                                                  bbn->code->opcode);
1233
1234                                                 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1235                                                 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1236
1237                                                 bb->last_ins->inst_false_bb = bbn->code->inst_target_bb;
1238
1239                                                 mono_link_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1240                                                 mono_link_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1241
1242                                                 changed = TRUE;
1243                                                 continue;
1244                                         }
1245
1246                                         bbn = bb->last_ins->inst_false_bb;
1247                                         /*
1248                                          * If bb is an extended bb, it could contain an inside branch to bbn.
1249                                          * FIXME: Enable the optimization if that is not true.
1250                                          * If bblocks_linked () is true, then merging bb and bbn
1251                                          * would require addition of an extra branch at the end of bbn
1252                                          * slowing down loops.
1253                                          */
1254                                         if (cfg->new_ir && 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)) {
1255                                                 g_assert (bbn->in_bb [0] == bb);
1256                                                 if (cfg->verbose_level > 2)
1257                                                         g_print ("merge false branch target triggered BB%d -> BB%d\n", bb->block_num, bbn->block_num);
1258                                                 mono_merge_basic_blocks (cfg, bb, bbn);
1259                                                 changed = TRUE;
1260                                                 continue;
1261                                         }
1262                                 }
1263
1264                                 /* detect and optimize to unsigned compares checks like: if (v < 0 || v > limit */
1265                                 if (bb->last_ins && bb->last_ins->opcode == CEE_BLT && !cfg->new_ir && bb->last_ins->inst_left->inst_right->opcode == OP_ICONST) {
1266                                         if (try_unsigned_compare (cfg, bb)) {
1267                                                 /*g_print ("applied in bb %d (->%d) %s\n", bb->block_num, bb->last_ins->inst_target_bb->block_num, mono_method_full_name (cfg->method, TRUE));*/
1268                                                 changed = TRUE;
1269                                                 continue;
1270                                         }
1271                                 }
1272
1273                                 if (bb->last_ins && MONO_IS_COND_BRANCH_NOFP (bb->last_ins)) {
1274                                         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)) {
1275                                                 /* Reverse the branch */
1276                                                 bb->last_ins->opcode = mono_reverse_branch_op (bb->last_ins->opcode);
1277                                                 bbn = bb->last_ins->inst_false_bb;
1278                                                 bb->last_ins->inst_false_bb = bb->last_ins->inst_true_bb;
1279                                                 bb->last_ins->inst_true_bb = bbn;
1280
1281                                                 move_basic_block_to_end (cfg, bb->last_ins->inst_true_bb);
1282                                                 if (cfg->verbose_level > 2)
1283                                                         g_print ("cbranch to throw block triggered %d.\n",
1284                                                                          bb->block_num);
1285                                         }
1286                                 }
1287                         }
1288                 }
1289         } while (changed && (niterations > 0));
1290 }