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