mono/mini/branch-opts.c

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