mono/mini/branch-opts.c

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