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