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