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