mono/mini/branch-opts.c

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