mono/mini/branch-opts.c

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