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