mono/mini/liveness.c

   1 /*
   2  * liveness.c: liveness analysis
   3  *
   4  * Author:
   5  *   Dietmar Maurer (dietmar@ximian.com)
   6  *
   7  * (C) 2002 Ximian, Inc.
   8  */
   9
  10 #include "mini.h"
  11 #include "inssel.h"
  12 #include "aliasing.h"
  13
  14 #define SPILL_COST_INCREMENT (1 << (bb->nesting << 1))
  15
  16 //#define DEBUG_LIVENESS
  17
  18 #if SIZEOF_VOID_P == 8
  19 #define BITS_PER_CHUNK 64
  20 #else
  21 #define BITS_PER_CHUNK 32
  22 #endif
  23
  24 static void
  25 optimize_initlocals (MonoCompile *cfg);
  26
  27 /* mono_bitset_mp_new:
  28  *
  29  * allocates a MonoBitSet inside a memory pool
  30  */
  31 static inline MonoBitSet*
  32 mono_bitset_mp_new (MonoMemPool *mp,  guint32 max_size)
  33 {
  34         int size = mono_bitset_alloc_size (max_size, 0);
  35         gpointer mem;
  36
  37         mem = mono_mempool_alloc0 (mp, size);
  38         return mono_bitset_mem_new (mem, max_size, MONO_BITSET_DONT_FREE);
  39 }
  40
  41 static inline MonoBitSet*
  42 mono_bitset_mp_new_noinit (MonoMemPool *mp,  guint32 max_size)
  43 {
  44         int size = mono_bitset_alloc_size (max_size, 0);
  45         gpointer mem;
  46
  47         mem = mono_mempool_alloc (mp, size);
  48         return mono_bitset_mem_new (mem, max_size, MONO_BITSET_DONT_FREE);
  49 }
  50
  51 G_GNUC_UNUSED static void
  52 mono_bitset_print (MonoBitSet *set)
  53 {
  54         int i;
  55
  56         printf ("{");
  57         for (i = 0; i < mono_bitset_size (set); i++) {
  58
  59                 if (mono_bitset_test (set, i))
  60                         printf ("%d, ", i);
  61
  62         }
  63         printf ("}\n");
  64 }
  65
  66 static inline void
  67 update_live_range (MonoCompile *cfg, int idx, int block_dfn, int tree_pos)
  68 {
  69         MonoLiveRange *range = &MONO_VARINFO (cfg, idx)->range;
  70         guint32 abs_pos = (block_dfn << 16) | tree_pos;
  71
  72         if (range->first_use.abs_pos > abs_pos)
  73                 range->first_use.abs_pos = abs_pos;
  74
  75         if (range->last_use.abs_pos < abs_pos)
  76                 range->last_use.abs_pos = abs_pos;
  77 }
  78
  79 static void
  80 update_gen_kill_set (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, int inst_num)
  81 {
  82         int arity = mono_burg_arity [inst->opcode];
  83         int max_vars = cfg->num_varinfo;
  84
  85         if (arity)
  86                 update_gen_kill_set (cfg, bb, inst->inst_i0, inst_num);
  87
  88         if (arity > 1)
  89                 update_gen_kill_set (cfg, bb, inst->inst_i1, inst_num);
  90
  91         if ((inst->ssa_op & MONO_SSA_LOAD_STORE) || (inst->opcode == OP_DUMMY_STORE)) {
  92                 MonoLocalVariableList* affected_variables;
  93                 MonoLocalVariableList local_affected_variable;
  94
  95                 if (cfg->aliasing_info == NULL) {
  96                         if ((inst->ssa_op == MONO_SSA_LOAD) || (inst->ssa_op == MONO_SSA_STORE) || (inst->opcode == OP_DUMMY_STORE)) {
  97                                 local_affected_variable.variable_index = inst->inst_i0->inst_c0;
  98                                 local_affected_variable.next = NULL;
  99                                 affected_variables = &local_affected_variable;
 100                         } else {
 101                                 affected_variables = NULL;
 102                         }
 103                 } else {
 104                         affected_variables = mono_aliasing_get_affected_variables_for_inst_traversing_code (cfg->aliasing_info, inst);
 105                 }
 106
 107                 if (inst->ssa_op & MONO_SSA_LOAD) {
 108                         MonoLocalVariableList* affected_variable = affected_variables;
 109                         while (affected_variable != NULL) {
 110                                 int idx = affected_variable->variable_index;
 111                                 MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
 112                                 g_assert (idx < max_vars);
 113                                 if ((bb->region != -1) && !MONO_BBLOCK_IS_IN_REGION (bb, MONO_REGION_TRY)) {
 114                                         /*
 115                                          * Variables used in exception regions can't be allocated to
 116                                          * registers.
 117                                          */
 118                                         cfg->varinfo [vi->idx]->flags |= MONO_INST_VOLATILE;
 119                                 }
 120                                 update_live_range (cfg, idx, bb->dfn, inst_num);
 121                                 if (!mono_bitset_test_fast (bb->kill_set, idx))
 122                                         mono_bitset_set_fast (bb->gen_set, idx);
 123                                 if (inst->ssa_op == MONO_SSA_LOAD)
 124                                         vi->spill_costs += SPILL_COST_INCREMENT;
 125
 126                                 affected_variable = affected_variable->next;
 127                         }
 128                 } else if ((inst->ssa_op == MONO_SSA_STORE) || (inst->opcode == OP_DUMMY_STORE)) {
 129                         MonoLocalVariableList* affected_variable = affected_variables;
 130                         while (affected_variable != NULL) {
 131                                 int idx = affected_variable->variable_index;
 132                                 MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
 133                                 g_assert (idx < max_vars);
 134                                 //if (arity > 0)
 135                                         //g_assert (inst->inst_i1->opcode != OP_PHI);
 136                                 if ((bb->region != -1) && !MONO_BBLOCK_IS_IN_REGION (bb, MONO_REGION_TRY)) {
 137                                         /*
 138                                          * Variables used in exception regions can't be allocated to
 139                                          * registers.
 140                                          */
 141                                         cfg->varinfo [vi->idx]->flags |= MONO_INST_VOLATILE;
 142                                 }
 143                                 update_live_range (cfg, idx, bb->dfn, inst_num);
 144                                 mono_bitset_set_fast (bb->kill_set, idx);
 145                                 if (inst->ssa_op == MONO_SSA_STORE)
 146                                         vi->spill_costs += SPILL_COST_INCREMENT;
 147
 148                                 affected_variable = affected_variable->next;
 149                         }
 150                 }
 151         } else if (inst->opcode == CEE_JMP) {
 152                 /* Keep arguments live! */
 153                 int i;
 154                 for (i = 0; i < cfg->num_varinfo; i++) {
 155                         if (cfg->varinfo [i]->opcode == OP_ARG) {
 156                                 if (!mono_bitset_test_fast (bb->kill_set, i))
 157                                         mono_bitset_set_fast (bb->gen_set, i);
 158                         }
 159                 }
 160         }
 161 }
 162
 163 static void
 164 update_volatile (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, int inst_num)
 165 {
 166         int arity = mono_burg_arity [inst->opcode];
 167         int max_vars = cfg->num_varinfo;
 168
 169         if (arity)
 170                 update_volatile (cfg, bb, inst->inst_i0, inst_num);
 171
 172         if (arity > 1)
 173                 update_volatile (cfg, bb, inst->inst_i1, inst_num);
 174
 175         if (inst->ssa_op & MONO_SSA_LOAD_STORE) {
 176                 MonoLocalVariableList* affected_variables;
 177                 MonoLocalVariableList local_affected_variable;
 178
 179                 if (cfg->aliasing_info == NULL) {
 180                         if ((inst->ssa_op == MONO_SSA_LOAD) || (inst->ssa_op == MONO_SSA_STORE)) {
 181                                 local_affected_variable.variable_index = inst->inst_i0->inst_c0;
 182                                 local_affected_variable.next = NULL;
 183                                 affected_variables = &local_affected_variable;
 184                         } else {
 185                                 affected_variables = NULL;
 186                         }
 187                 } else {
 188                         affected_variables = mono_aliasing_get_affected_variables_for_inst_traversing_code (cfg->aliasing_info, inst);
 189                 }
 190
 191                 while (affected_variables != NULL) {
 192                         int idx = affected_variables->variable_index;
 193                         MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
 194                         g_assert (idx < max_vars);
 195                         cfg->varinfo [vi->idx]->flags |= MONO_INST_VOLATILE;
 196
 197                         affected_variables = affected_variables->next;
 198                 }
 199         }
 200 }
 201
 202 static void
 203 visit_bb (MonoCompile *cfg, MonoBasicBlock *bb, GSList **visited)
 204 {
 205         int i, tree_num;
 206         MonoInst *inst;
 207
 208         if (g_slist_find (*visited, bb))
 209                 return;
 210
 211         if (cfg->aliasing_info != NULL)
 212                 mono_aliasing_initialize_code_traversal (cfg->aliasing_info, bb);
 213
 214         for (tree_num = 0, inst = bb->code; inst; inst = inst->next, tree_num++) {
 215                 update_volatile (cfg, bb, inst, tree_num);
 216         }
 217
 218         *visited = g_slist_append (*visited, bb);
 219
 220         /*
 221          * Need to visit all bblocks reachable from this one since they can be
 222          * reached during exception handling.
 223          */
 224         for (i = 0; i < bb->out_count; ++i) {
 225                 visit_bb (cfg, bb->out_bb [i], visited);
 226         }
 227 }
 228
 229 void
 230 mono_liveness_handle_exception_clauses (MonoCompile *cfg)
 231 {
 232         MonoBasicBlock *bb;
 233         GSList *visited = NULL;
 234
 235         /*
 236          * Variables in exception handler register cannot be allocated to registers
 237          * so make them volatile. See bug #42136. This will not be neccessary when
 238          * the back ends could guarantee that the variables will be in the
 239          * correct registers when a handler is called.
 240          * This includes try blocks too, since a variable in a try block might be
 241          * accessed after an exception handler has been run.
 242          */
 243         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 244
 245                 if (bb->region == -1 || MONO_BBLOCK_IS_IN_REGION (bb, MONO_REGION_TRY))
 246                         continue;
 247
 248                 visit_bb (cfg, bb, &visited);
 249         }
 250         g_slist_free (visited);
 251 }
 252
 253 /* generic liveness analysis code. CFG specific parts are
 254  * in update_gen_kill_set()
 255  */
 256 void
 257 mono_analyze_liveness (MonoCompile *cfg)
 258 {
 259         MonoBitSet *old_live_out_set;
 260         int i, j, max_vars = cfg->num_varinfo;
 261         int out_iter;
 262         gboolean *in_worklist;
 263         MonoBasicBlock **worklist;
 264         guint32 l_end;
 265         int bitsize;
 266         guint8 *mem;
 267
 268 #ifdef DEBUG_LIVENESS
 269         printf ("LIVENESS %s\n", mono_method_full_name (cfg->method, TRUE));
 270 #endif
 271
 272         g_assert (!(cfg->comp_done & MONO_COMP_LIVENESS));
 273
 274         cfg->comp_done |= MONO_COMP_LIVENESS;
 275
 276         if (max_vars == 0)
 277                 return;
 278
 279         bitsize = mono_bitset_alloc_size (max_vars, 0);
 280         mem = mono_mempool_alloc0 (cfg->mempool, cfg->num_bblocks * bitsize * 4);
 281
 282         for (i = 0; i < cfg->num_bblocks; ++i) {
 283                 MonoBasicBlock *bb = cfg->bblocks [i];
 284
 285                 bb->gen_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
 286                 mem += bitsize;
 287                 bb->kill_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
 288                 mem += bitsize;
 289                 /* Initialized later */
 290                 bb->live_in_set = NULL;
 291                 bb->live_out_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
 292                 mem += bitsize;
 293         }
 294         for (i = 0; i < max_vars; i ++) {
 295                 MONO_VARINFO (cfg, i)->range.first_use.abs_pos = ~ 0;
 296                 MONO_VARINFO (cfg, i)->range.last_use .abs_pos =   0;
 297                 MONO_VARINFO (cfg, i)->spill_costs = 0;
 298         }
 299
 300         for (i = 0; i < cfg->num_bblocks; ++i) {
 301                 MonoBasicBlock *bb = cfg->bblocks [i];
 302                 MonoInst *inst;
 303                 int tree_num;
 304
 305                 if (cfg->aliasing_info != NULL)
 306                         mono_aliasing_initialize_code_traversal (cfg->aliasing_info, bb);
 307
 308                 for (tree_num = 0, inst = bb->code; inst; inst = inst->next, tree_num++) {
 309 #ifdef DEBUG_LIVENESS
 310                         mono_print_tree (inst); printf ("\n");
 311 #endif
 312                         update_gen_kill_set (cfg, bb, inst, tree_num);
 313                 }
 314
 315 #ifdef DEBUG_LIVENESS
 316                 printf ("BLOCK BB%d (", bb->block_num);
 317                 for (j = 0; j < bb->out_count; j++)
 318                         printf ("BB%d, ", bb->out_bb [j]->block_num);
 319
 320                 printf (")\n");
 321                 printf ("GEN  BB%d: ", bb->block_num); mono_bitset_print (bb->gen_set);
 322                 printf ("KILL BB%d: ", bb->block_num); mono_bitset_print (bb->kill_set);
 323 #endif
 324         }
 325
 326         old_live_out_set = mono_bitset_new (max_vars, 0);
 327         in_worklist = g_new0 (gboolean, cfg->num_bblocks + 1);
 328
 329         worklist = g_new (MonoBasicBlock *, cfg->num_bblocks + 1);
 330         l_end = 0;
 331
 332         /*
 333          * This is a backward dataflow analysis problem, so we process blocks in
 334          * decreasing dfn order, this speeds up the iteration.
 335          */
 336         for (i = 0; i < cfg->num_bblocks; i ++) {
 337                 MonoBasicBlock *bb = cfg->bblocks [i];
 338
 339                 worklist [l_end ++] = bb;
 340                 in_worklist [bb->dfn] = TRUE;
 341         }
 342
 343         out_iter = 0;
 344
 345         while (l_end != 0) {
 346                 MonoBasicBlock *bb = worklist [--l_end];
 347                 MonoBasicBlock *out_bb;
 348                 gboolean changed;
 349
 350                 in_worklist [bb->dfn] = FALSE;
 351
 352 #ifdef DEBUG_LIVENESS
 353                 printf ("P: %d(%d): IN: ", bb->block_num, bb->dfn);
 354                 for (j = 0; j < bb->in_count; ++j)
 355                         printf ("BB%d ", bb->in_bb [j]->block_num);
 356                 printf ("OUT:");
 357                 for (j = 0; j < bb->out_count; ++j)
 358                         printf ("BB%d ", bb->out_bb [j]->block_num);
 359                 printf ("\n");
 360 #endif
 361
 362                 if (bb->out_count == 0)
 363                         continue;
 364
 365                 out_iter ++;
 366
 367                 if (!bb->live_in_set) {
 368                         /* First pass over this bblock */
 369                         changed = TRUE;
 370                 }
 371                 else {
 372                         changed = FALSE;
 373                         mono_bitset_copyto (bb->live_out_set, old_live_out_set);
 374                 }
 375
 376                 for (j = 0; j < bb->out_count; j++) {
 377                         out_bb = bb->out_bb [j];
 378
 379                         if (!out_bb->live_in_set) {
 380                                 out_bb->live_in_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
 381                                 mem += bitsize;
 382
 383                                 mono_bitset_copyto (out_bb->live_out_set, out_bb->live_in_set);
 384                                 mono_bitset_sub (out_bb->live_in_set, out_bb->kill_set);
 385                                 mono_bitset_union (out_bb->live_in_set, out_bb->gen_set);
 386                         }
 387
 388                         mono_bitset_union (bb->live_out_set, out_bb->live_in_set);
 389                 }
 390
 391                 if (changed || !mono_bitset_equal (old_live_out_set, bb->live_out_set)) {
 392                         if (!bb->live_in_set) {
 393                                 bb->live_in_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
 394                                 mem += bitsize;
 395                         }
 396                         mono_bitset_copyto (bb->live_out_set, bb->live_in_set);
 397                         mono_bitset_sub (bb->live_in_set, bb->kill_set);
 398                         mono_bitset_union (bb->live_in_set, bb->gen_set);
 399
 400                         for (j = 0; j < bb->in_count; j++) {
 401                                 MonoBasicBlock *in_bb = bb->in_bb [j];
 402                                 /*
 403                                  * Some basic blocks do not seem to be in the
 404                                  * cfg->bblocks array...
 405                                  */
 406                                 if (in_bb->gen_set && !in_worklist [in_bb->dfn]) {
 407 #ifdef DEBUG_LIVENESS
 408                                         printf ("\tADD: %d\n", in_bb->block_num);
 409 #endif
 410                                         /*
 411                                          * Put the block at the top of the stack, so it
 412                                          * will be processed right away.
 413                                          */
 414                                         worklist [l_end ++] = in_bb;
 415                                         in_worklist [in_bb->dfn] = TRUE;
 416                                 }
 417                         }
 418                 }
 419         }
 420
 421         //printf ("IT: %d %d %d.\n", iterations, in_iter, out_iter);
 422
 423         mono_bitset_free (old_live_out_set);
 424
 425         g_free (worklist);
 426         g_free (in_worklist);
 427
 428         /* Compute live_in_set for bblocks skipped earlier */
 429         for (i = 0; i < cfg->num_bblocks; ++i) {
 430                 MonoBasicBlock *bb = cfg->bblocks [i];
 431
 432                 if (!bb->live_in_set) {
 433                         bb->live_in_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
 434                         mem += bitsize;
 435
 436                         mono_bitset_copyto (bb->live_out_set, bb->live_in_set);
 437                         mono_bitset_sub (bb->live_in_set, bb->kill_set);
 438                         mono_bitset_union (bb->live_in_set, bb->gen_set);
 439                 }
 440         }
 441
 442         /*
 443          * This code can be slow for large methods so inline the calls to
 444          * mono_bitset_test.
 445          */
 446         for (i = 0; i < cfg->num_bblocks; ++i) {
 447                 MonoBasicBlock *bb = cfg->bblocks [i];
 448                 guint32 rem, max;
 449
 450                 if (!bb->live_out_set)
 451                         continue;
 452
 453                 rem = max_vars % BITS_PER_CHUNK;
 454                 max = ((max_vars + (BITS_PER_CHUNK -1)) / BITS_PER_CHUNK);
 455                 for (j = 0; j < max; ++j) {
 456                         gsize bits_in;
 457                         gsize bits_out;
 458                         int k, end;
 459
 460                         bits_in = mono_bitset_get_fast (bb->live_in_set, j);
 461                         bits_out = mono_bitset_get_fast (bb->live_out_set, j);
 462
 463                         if (j == max)
 464                                 end = (j * BITS_PER_CHUNK) + rem;
 465                         else
 466                                 end = (j * BITS_PER_CHUNK) + BITS_PER_CHUNK;
 467
 468                         k = (j * BITS_PER_CHUNK);
 469                         while ((bits_in || bits_out)) {
 470                                 if (bits_in & 1)
 471                                         update_live_range (cfg, k, bb->dfn, 0);
 472                                 if (bits_out & 1)
 473                                         update_live_range (cfg, k, bb->dfn, 0xffff);
 474                                 bits_in >>= 1;
 475                                 bits_out >>= 1;
 476                                 k ++;
 477                         }
 478                 }
 479         }
 480
 481         /*
 482          * Arguments need to have their live ranges extended to the beginning of
 483          * the method to account for the arg reg/memory -> global register copies
 484          * in the prolog (bug #74992).
 485          */
 486
 487         for (i = 0; i < max_vars; i ++) {
 488                 MonoMethodVar *vi = MONO_VARINFO (cfg, i);
 489                 if (cfg->varinfo [vi->idx]->opcode == OP_ARG)
 490                         vi->range.first_use.abs_pos = 0;
 491         }
 492
 493 #ifdef DEBUG_LIVENESS
 494         for (i = cfg->num_bblocks - 1; i >= 0; i--) {
 495                 MonoBasicBlock *bb = cfg->bblocks [i];
 496
 497                 printf ("LIVE IN  BB%d: ", bb->block_num);
 498                 mono_bitset_print (bb->live_in_set);
 499                 printf ("LIVE OUT BB%d: ", bb->block_num);
 500                 mono_bitset_print (bb->live_out_set);
 501         }
 502 #endif
 503
 504         optimize_initlocals (cfg);
 505 }
 506
 507 static void
 508 update_used (MonoCompile *cfg, MonoInst *inst, MonoBitSet *used)
 509 {
 510         int arity = mono_burg_arity [inst->opcode];
 511
 512         if (arity)
 513                 update_used (cfg, inst->inst_i0, used);
 514
 515         if (arity > 1)
 516                 update_used (cfg, inst->inst_i1, used);
 517
 518         if (inst->ssa_op & MONO_SSA_LOAD_STORE) {
 519                 if (inst->ssa_op == MONO_SSA_LOAD) {
 520                         int idx = inst->inst_i0->inst_c0;
 521
 522                         mono_bitset_set_fast (used, idx);
 523                 }
 524         }
 525 }
 526
 527 /**
 528  * optimize_initlocals:
 529  *
 530  * Try to optimize away some of the redundant initialization code inserted because of
 531  * 'locals init' using the liveness information.
 532  */
 533 static void
 534 optimize_initlocals (MonoCompile *cfg)
 535 {
 536         MonoBitSet *used;
 537         MonoInst *ins;
 538         MonoBasicBlock *initlocals_bb;
 539
 540         used = mono_bitset_new (cfg->num_varinfo, 0);
 541
 542         mono_bitset_clear_all (used);
 543         initlocals_bb = cfg->bb_entry->next_bb;
 544         for (ins = initlocals_bb->code; ins; ins = ins->next) {
 545                 update_used (cfg, ins, used);
 546         }
 547
 548         for (ins = initlocals_bb->code; ins; ins = ins->next) {
 549                 if (ins->ssa_op == MONO_SSA_STORE) {
 550                         int idx = ins->inst_i0->inst_c0;
 551                         MonoInst *var = cfg->varinfo [idx];
 552
 553                         if (var && !mono_bitset_test_fast (used, idx) && !mono_bitset_test_fast (initlocals_bb->live_out_set, var->inst_c0) && (var != cfg->ret) && !(var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT))) {
 554                                 if (ins->inst_i1 && ((ins->inst_i1->opcode == OP_ICONST) || (ins->inst_i1->opcode == OP_I8CONST))) {
 555                                         NULLIFY_INS (ins);
 556                                         ins->ssa_op = MONO_SSA_NOP;
 557                                         MONO_VARINFO (cfg, var->inst_c0)->spill_costs -= 1;
 558                                 }
 559                         }
 560                 }
 561         }
 562
 563         g_free (used);
 564 }