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