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