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  /*
  12  * Used by the arch code to replace the exception handling
  13  * with a direct branch. This is safe to do if the
  14  * exception object isn't used, no rethrow statement and
  15  * no filter statement (verify).
  16  *
  17  */
  18 MonoInst *
  19 mono_branch_optimize_exception_target (MonoCompile *cfg, MonoBasicBlock *bb, const char * exname)
  20 {
  21         MonoMethod *method = cfg->method;
  22         MonoMethodHeader *header = mono_method_get_header (method);
  23         MonoExceptionClause *clause;
  24         MonoClass *exclass;
  25         int i;
  26
  27         if (!(cfg->opt & MONO_OPT_EXCEPTION))
  28                 return NULL;
  29
  30         if (bb->region == -1 || !MONO_BBLOCK_IS_IN_REGION (bb, MONO_REGION_TRY))
  31                 return NULL;
  32
  33         exclass = mono_class_from_name (mono_get_corlib (), "System", exname);
  34         /* search for the handler */
  35         for (i = 0; i < header->num_clauses; ++i) {
  36                 clause = &header->clauses [i];
  37                 if (MONO_OFFSET_IN_CLAUSE (clause, bb->real_offset)) {
  38                         if (clause->flags == MONO_EXCEPTION_CLAUSE_NONE && clause->data.catch_class && mono_class_is_assignable_from (clause->data.catch_class, exclass)) {
  39                                 MonoBasicBlock *tbb;
  40
  41                                 /* get the basic block for the handler and
  42                                  * check if the exception object is used.
  43                                  * Flag is set during method_to_ir due to
  44                                  * pop-op is optmized away in codegen (burg).
  45                                  */
  46                                 tbb = cfg->cil_offset_to_bb [clause->handler_offset];
  47                                 if (tbb && tbb->flags & BB_EXCEPTION_DEAD_OBJ && !(tbb->flags & BB_EXCEPTION_UNSAFE)) {
  48                                         MonoBasicBlock *targetbb = tbb;
  49                                         gboolean unsafe = FALSE;
  50
  51                                         /* Check if this catch clause is ok to optimize by
  52                                          * looking for the BB_EXCEPTION_UNSAFE in every BB that
  53                                          * belongs to the same region.
  54                                          *
  55                                          * UNSAFE flag is set during method_to_ir (OP_RETHROW)
  56                                          */
  57                                         while (!unsafe && tbb->next_bb && tbb->region == tbb->next_bb->region) {
  58                                                 if (tbb->next_bb->flags & BB_EXCEPTION_UNSAFE)  {
  59                                                         unsafe = TRUE;
  60                                                         break;
  61                                                 }
  62                                                 tbb = tbb->next_bb;
  63                                         }
  64
  65                                         if (!unsafe) {
  66                                                 MonoInst *jump;
  67
  68                                                 /* Create dummy inst to allow easier integration in
  69                                                  * arch dependent code (opcode ignored)
  70                                                  */
  71                                                 MONO_INST_NEW (cfg, jump, OP_BR);
  72
  73                                                 /* Allocate memory for our branch target */
  74                                                 jump->inst_i1 = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoInst));
  75                                                 jump->inst_true_bb = targetbb;
  76
  77                                                 if (cfg->verbose_level > 2)
  78                                                         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);
  79
  80                                                 return jump;
  81                                         }
  82
  83                                         return NULL;
  84                                 }
  85                         } else {
  86                                 /* Branching to an outer clause could skip inner clauses */
  87                                 return NULL;
  88                         }
  89                 }
  90         }
  91
  92         return NULL;
  93 }
  94
  95 static const int int_cmov_opcodes [] = {
  96         OP_CMOV_IEQ,
  97         OP_CMOV_INE_UN,
  98         OP_CMOV_ILE,
  99         OP_CMOV_IGE,
 100         OP_CMOV_ILT,
 101         OP_CMOV_IGT,
 102         OP_CMOV_ILE_UN,
 103         OP_CMOV_IGE_UN,
 104         OP_CMOV_ILT_UN,
 105         OP_CMOV_IGT_UN
 106 };
 107
 108 static const int long_cmov_opcodes [] = {
 109         OP_CMOV_LEQ,
 110         OP_CMOV_LNE_UN,
 111         OP_CMOV_LLE,
 112         OP_CMOV_LGE,
 113         OP_CMOV_LLT,
 114         OP_CMOV_LGT,
 115         OP_CMOV_LLE_UN,
 116         OP_CMOV_LGE_UN,
 117         OP_CMOV_LLT_UN,
 118         OP_CMOV_LGT_UN
 119 };
 120
 121 void
 122 mono_if_conversion (MonoCompile *cfg)
 123 {
 124 #ifdef MONO_ARCH_HAVE_CMOV_OPS
 125         MonoBasicBlock *bb;
 126         gboolean changed = FALSE;
 127
 128         if (!(cfg->opt & MONO_OPT_CMOV))
 129                 return;
 130
 131         // FIXME: Make this work with extended bblocks
 132
 133         /*
 134          * This pass requires somewhat optimized IR code so it should be run after
 135          * local cprop/deadce. Also, it should be run before dominator computation, since
 136          * it changes control flow.
 137          */
 138         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 139                 MonoBasicBlock *bb1, *bb2;
 140
 141         restart:
 142                 /* Look for the IR code generated from cond ? a : b
 143                  * which is:
 144                  * BB:
 145                  * b<cond> [BB1BB2]
 146                  * BB1:
 147                  * <var> <- <a>
 148                  * br BB3
 149                  * BB2:
 150                  * <var> <- <b>
 151                  * br BB3
 152                  */
 153                 if (!(bb->out_count == 2 && !bb->extended))
 154                         continue;
 155
 156                 bb1 = bb->out_bb [0];
 157                 bb2 = bb->out_bb [1];
 158
 159                 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]) {
 160                         MonoInst *prev, *compare, *branch, *ins1, *ins2, *cmov, *move, *tmp;
 161                         gboolean simple, ret;
 162                         int dreg, tmp_reg;
 163                         CompType comp_type;
 164
 165                         /*
 166                          * Check that bb1 and bb2 are 'simple' and both assign to the same
 167                          * variable.
 168                          */
 169                         /* FIXME: Get rid of the nops earlier */
 170                         ins1 = bb1->code;
 171                         while (ins1 && ins1->opcode == OP_NOP)
 172                                 ins1 = ins1->next;
 173                         ins2 = bb2->code;
 174                         while (ins2 && ins2->opcode == OP_NOP)
 175                                 ins2 = ins2->next;
 176                         if (!(ins1 && ins2 && ins1->dreg == ins2->dreg && ins1->dreg != -1))
 177                                 continue;
 178
 179                         simple = TRUE;
 180                         for (tmp = ins1->next; tmp; tmp = tmp->next)
 181                                 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_BR)))
 182                                         simple = FALSE;
 183
 184                         for (tmp = ins2->next; tmp; tmp = tmp->next)
 185                                 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_BR)))
 186                                         simple = FALSE;
 187
 188                         if (!simple)
 189                                 continue;
 190
 191                         /* We move ins1/ins2 before the compare so they should have no side effect */
 192                         if (!(MONO_INS_HAS_NO_SIDE_EFFECT (ins1) && MONO_INS_HAS_NO_SIDE_EFFECT (ins2)))
 193                                 continue;
 194
 195                         if (bb->last_ins && (bb->last_ins->opcode == OP_BR_REG || bb->last_ins->opcode == OP_BR))
 196                                 continue;
 197
 198                         /* Find the compare instruction */
 199                         /* FIXME: Optimize this using prev */
 200                         prev = NULL;
 201                         compare = bb->code;
 202                         g_assert (compare);
 203                         while (compare->next && !MONO_IS_COND_BRANCH_OP (compare->next)) {
 204                                 prev = compare;
 205                                 compare = compare->next;
 206                         }
 207                         g_assert (compare->next && MONO_IS_COND_BRANCH_OP (compare->next));
 208                         branch = compare->next;
 209
 210                         /* Moving ins1/ins2 could change the comparison */
 211                         /* FIXME: */
 212                         if (!((compare->sreg1 != ins1->dreg) && (compare->sreg2 != ins1->dreg)))
 213                                 continue;
 214
 215                         /* FIXME: */
 216                         comp_type = mono_opcode_to_type (branch->opcode, compare->opcode);
 217                         if (!((comp_type == CMP_TYPE_I) || (comp_type == CMP_TYPE_L)))
 218                                 continue;
 219
 220                         /* FIXME: */
 221                         /* ins->type might not be set */
 222                         if (INS_INFO (ins1->opcode) [MONO_INST_DEST] != 'i')
 223                                 continue;
 224
 225                         if (cfg->verbose_level > 2) {
 226                                 printf ("\tBranch -> CMove optimization in BB%d on\n", bb->block_num);
 227                                 printf ("\t\t"); mono_print_ins (compare);
 228                                 printf ("\t\t"); mono_print_ins (compare->next);
 229                                 printf ("\t\t"); mono_print_ins (ins1);
 230                                 printf ("\t\t"); mono_print_ins (ins2);
 231                         }
 232
 233                         changed = TRUE;
 234
 235                         //printf ("HIT!\n");
 236
 237                         /* Assignments to the return register must remain at the end of bbs */
 238                         if (cfg->ret)
 239                                 ret = ins1->dreg == cfg->ret->dreg;
 240                         else
 241                                 ret = FALSE;
 242
 243                         tmp_reg = mono_alloc_dreg (cfg, STACK_I4);
 244                         dreg = ins1->dreg;
 245
 246                         /* Rewrite ins1 to emit to tmp_reg */
 247                         ins1->dreg = tmp_reg;
 248
 249                         if (ret) {
 250                                 dreg = mono_alloc_dreg (cfg, STACK_I4);
 251                                 ins2->dreg = dreg;
 252                         }
 253
 254                         /* Remove ins1/ins2 from bb1/bb2 */
 255                         MONO_REMOVE_INS (bb1, ins1);
 256                         MONO_REMOVE_INS (bb2, ins2);
 257
 258                         /* Move ins1 and ins2 before the comparison */
 259                         /* ins1 comes first to avoid ins1 overwriting an argument of ins2 */
 260                         mono_bblock_insert_before_ins (bb, compare, ins2);
 261                         mono_bblock_insert_before_ins (bb, ins2, ins1);
 262
 263                         /* Add cmov instruction */
 264                         MONO_INST_NEW (cfg, cmov, OP_NOP);
 265                         cmov->dreg = dreg;
 266                         cmov->sreg1 = dreg;
 267                         cmov->sreg2 = tmp_reg;
 268                         switch (mono_opcode_to_type (branch->opcode, compare->opcode)) {
 269                         case CMP_TYPE_I:
 270                                 cmov->opcode = int_cmov_opcodes [mono_opcode_to_cond (branch->opcode)];
 271                                 break;
 272                         case CMP_TYPE_L:
 273                                 cmov->opcode = long_cmov_opcodes [mono_opcode_to_cond (branch->opcode)];
 274                                 break;
 275                         default:
 276                                 g_assert_not_reached ();
 277                         }
 278                         mono_bblock_insert_after_ins (bb, compare, cmov);
 279
 280                         if (ret) {
 281                                 /* Add an extra move */
 282                                 MONO_INST_NEW (cfg, move, OP_MOVE);
 283                                 move->dreg = cfg->ret->dreg;
 284                                 move->sreg1 = dreg;
 285                                 mono_bblock_insert_after_ins (bb, cmov, move);
 286                         }
 287
 288                         /* Rewrite the branch */
 289                         branch->opcode = OP_BR;
 290                         branch->inst_target_bb = bb1->out_bb [0];
 291                         mono_link_bblock (cfg, bb, branch->inst_target_bb);
 292
 293                         /* Reorder bblocks */
 294                         mono_unlink_bblock (cfg, bb, bb1);
 295                         mono_unlink_bblock (cfg, bb, bb2);
 296                         mono_unlink_bblock (cfg, bb1, bb1->out_bb [0]);
 297                         mono_unlink_bblock (cfg, bb2, bb2->out_bb [0]);
 298                         mono_remove_bblock (cfg, bb1);
 299                         mono_remove_bblock (cfg, bb2);
 300
 301                         /* Merge bb and its successor if possible */
 302                         if ((bb->out_bb [0]->in_count == 1) && (bb->out_bb [0] != cfg->bb_exit) &&
 303                                 (bb->region == bb->out_bb [0]->region)) {
 304                                 mono_merge_basic_blocks (cfg, bb, bb->out_bb [0]);
 305                                 goto restart;
 306                         }
 307                 }
 308
 309                 /* Look for the IR code generated from if (cond) <var> <- <a>
 310                  * which is:
 311                  * BB:
 312                  * b<cond> [BB1BB2]
 313                  * BB1:
 314                  * <var> <- <a>
 315                  * br BB2
 316                  */
 317
 318                 if ((bb2->in_count == 1 && bb2->out_count == 1 && bb2->out_bb [0] == bb1) ||
 319                         (bb1->in_count == 1 && bb1->out_count == 1 && bb1->out_bb [0] == bb2)) {
 320                         MonoInst *prev, *compare, *branch, *ins1, *cmov, *tmp;
 321                         gboolean simple;
 322                         int dreg, tmp_reg;
 323                         CompType comp_type;
 324                         CompRelation cond;
 325                         MonoBasicBlock *next_bb, *code_bb;
 326
 327                         /* code_bb is the bblock containing code, next_bb is the successor bblock */
 328                         if (bb2->in_count == 1 && bb2->out_count == 1 && bb2->out_bb [0] == bb1) {
 329                                 code_bb = bb2;
 330                                 next_bb = bb1;
 331                         } else {
 332                                 code_bb = bb1;
 333                                 next_bb = bb2;
 334                         }
 335
 336                         ins1 = code_bb->code;
 337
 338                         if (!ins1)
 339                                 continue;
 340
 341                         /* Check that code_bb is simple */
 342                         simple = TRUE;
 343                         for (tmp = ins1->next; tmp; tmp = tmp->next)
 344                                 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_BR)))
 345                                         simple = FALSE;
 346
 347                         if (!simple)
 348                                 continue;
 349
 350                         /* We move ins1 before the compare so it should have no side effect */
 351                         if (!MONO_INS_HAS_NO_SIDE_EFFECT (ins1))
 352                                 continue;
 353
 354                         if (bb->last_ins && bb->last_ins->opcode == OP_BR_REG)
 355                                 continue;
 356
 357                         /* Find the compare instruction */
 358                         /* FIXME: Optimize this using prev */
 359                         prev = NULL;
 360                         compare = bb->code;
 361                         g_assert (compare);
 362                         while (compare->next && !MONO_IS_COND_BRANCH_OP (compare->next)) {
 363                                 prev = compare;
 364                                 compare = compare->next;
 365                         }
 366                         g_assert (compare->next && MONO_IS_COND_BRANCH_OP (compare->next));
 367                         branch = compare->next;
 368
 369                         /* FIXME: */
 370                         comp_type = mono_opcode_to_type (branch->opcode, compare->opcode);
 371                         if (!((comp_type == CMP_TYPE_I) || (comp_type == CMP_TYPE_L)))
 372                                 continue;
 373
 374                         /* FIXME: */
 375                         /* ins->type might not be set */
 376                         if (INS_INFO (ins1->opcode) [MONO_INST_DEST] != 'i')
 377                                 continue;
 378
 379                         /* FIXME: */
 380                         if (cfg->ret && ins1->dreg == cfg->ret->dreg)
 381                                 continue;
 382
 383                         if (cfg->verbose_level > 2) {
 384                                 printf ("\tBranch -> CMove optimization (2) in BB%d on\n", bb->block_num);
 385                                 printf ("\t\t"); mono_print_ins (compare);
 386                                 printf ("\t\t"); mono_print_ins (compare->next);
 387                                 printf ("\t\t"); mono_print_ins (ins1);
 388                         }
 389
 390                         changed = TRUE;
 391
 392                         //printf ("HIT!\n");
 393
 394                         tmp_reg = mono_alloc_dreg (cfg, STACK_I4);
 395                         dreg = ins1->dreg;
 396
 397                         /* Rewrite ins1 to emit to tmp_reg */
 398                         ins1->dreg = tmp_reg;
 399
 400                         /* Remove ins1 from code_bb */
 401                         MONO_REMOVE_INS (code_bb, ins1);
 402
 403                         /* Move ins1 before the comparison */
 404                         mono_bblock_insert_before_ins (bb, compare, ins1);
 405
 406                         /* Add cmov instruction */
 407                         MONO_INST_NEW (cfg, cmov, OP_NOP);
 408                         cmov->dreg = dreg;
 409                         cmov->sreg1 = dreg;
 410                         cmov->sreg2 = tmp_reg;
 411                         cond = mono_opcode_to_cond (branch->opcode);
 412                         if (branch->inst_false_bb == code_bb)
 413                                 cond = mono_negate_cond (cond);
 414                         switch (mono_opcode_to_type (branch->opcode, compare->opcode)) {
 415                         case CMP_TYPE_I:
 416                                 cmov->opcode = int_cmov_opcodes [cond];
 417                                 break;
 418                         case CMP_TYPE_L:
 419                                 cmov->opcode = long_cmov_opcodes [cond];
 420                                 break;
 421                         default:
 422                                 g_assert_not_reached ();
 423                         }
 424                         mono_bblock_insert_after_ins (bb, compare, cmov);
 425
 426                         /* Rewrite the branch */
 427                         branch->opcode = OP_BR;
 428                         branch->inst_target_bb = next_bb;
 429                         mono_link_bblock (cfg, bb, branch->inst_target_bb);
 430
 431                         /* Nullify the branch at the end of code_bb */
 432                         if (code_bb->code) {
 433                                 branch = code_bb->code;
 434                                 MONO_DELETE_INS (code_bb, branch);
 435                         }
 436
 437                         /* Reorder bblocks */
 438                         mono_unlink_bblock (cfg, bb, code_bb);
 439                         mono_unlink_bblock (cfg, code_bb, next_bb);
 440
 441                         /* Merge bb and its successor if possible */
 442                         if ((bb->out_bb [0]->in_count == 1) && (bb->out_bb [0] != cfg->bb_exit) &&
 443                                 (bb->region == bb->out_bb [0]->region)) {
 444                                 mono_merge_basic_blocks (cfg, bb, bb->out_bb [0]);
 445                                 goto restart;
 446                         }
 447                 }
 448         }
 449
 450 #if 0
 451         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 452                 MonoBasicBlock *bb1, *bb2;
 453                 MonoInst *prev, *compare, *branch, *ins1, *ins2, *cmov, *move, *tmp;
 454                 gboolean simple, ret;
 455                 int dreg, tmp_reg;
 456                 CompType comp_type;
 457
 458                 /* Look for the IR code generated from if (cond) <var> <- <a>
 459                  * after branch opts which is:
 460                  * BB:
 461                  * compare
 462                  * b<cond> [BB1]
 463                  * <var> <- <a>
 464                  * BB1:
 465                  */
 466                 if (!(bb->out_count == 1 && bb->extended && bb->code && bb->code->next && bb->code->next->next))
 467                         continue;
 468
 469                 mono_print_bb (bb, "");
 470
 471                 /* Find the compare instruction */
 472                 prev = NULL;
 473                 compare = bb->code;
 474                 g_assert (compare);
 475                 while (compare->next->next && compare->next->next != bb->last_ins) {
 476                         prev = compare;
 477                         compare = compare->next;
 478                 }
 479                 branch = compare->next;
 480                 if (!MONO_IS_COND_BRANCH_OP (branch))
 481                         continue;
 482         }
 483 #endif
 484
 485         if (changed) {
 486                 if (cfg->opt & MONO_OPT_BRANCH)
 487                         mono_optimize_branches (cfg);
 488                 /* Merging bblocks could make some variables local */
 489                 mono_handle_global_vregs (cfg);
 490                 if (cfg->opt & (MONO_OPT_CONSPROP | MONO_OPT_COPYPROP))
 491                         mono_local_cprop2 (cfg);
 492                 mono_local_deadce (cfg);
 493         }
 494 #endif
 495 }