mono/mini/ssa.c

   1 /*
   2  * ssa.c: Static single assign form support for the JIT compiler.
   3  *
   4  * Author:
   5  *    Dietmar Maurer (dietmar@ximian.com)
   6  *
   7  * (C) 2003 Ximian, Inc.
   8  */
   9 #include <string.h>
  10 #include <mono/metadata/debug-helpers.h>
  11
  12 #include "mini.h"
  13
  14 #ifndef DISABLE_SSA
  15
  16 #define USE_ORIGINAL_VARS
  17 #define CREATE_PRUNED_SSA
  18
  19 //#define DEBUG_SSA 1
  20
  21 #define NEW_PHI(cfg,dest,val) do {      \
  22                 (dest) = mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoInst));       \
  23                 (dest)->opcode = OP_PHI;        \
  24                 (dest)->inst_c0 = (val);        \
  25         } while (0)
  26
  27 #define NEW_ICONST(cfg,dest,val) do {   \
  28                 (dest) = mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoInst));       \
  29                 (dest)->opcode = OP_ICONST;     \
  30                 (dest)->inst_c0 = (val);        \
  31                 (dest)->type = STACK_I4;        \
  32         } while (0)
  33
  34
  35 static GList*
  36 g_list_prepend_mempool (GList* l, MonoMemPool* mp, gpointer datum)
  37 {
  38         GList* n = mono_mempool_alloc (mp, sizeof (GList));
  39         n->next = l;
  40         n->prev = NULL;
  41         n->data = datum;
  42         return n;
  43 }
  44
  45 static void
  46 unlink_target (MonoBasicBlock *bb, MonoBasicBlock *target)
  47 {
  48         int i;
  49
  50         for (i = 0; i < bb->out_count; i++) {
  51                 if (bb->out_bb [i] == target) {
  52                         bb->out_bb [i] = bb->out_bb [--bb->out_count];
  53                         break;
  54                 }
  55         }
  56         for (i = 0; i < target->in_count; i++) {
  57                 if (target->in_bb [i] == bb) {
  58                         target->in_bb [i] = target->in_bb [--target->in_count];
  59                         break;
  60
  61                 }
  62         }
  63 }
  64
  65 static void
  66 unlink_unused_bblocks (MonoCompile *cfg)
  67 {
  68         int i, j;
  69         MonoBasicBlock *bb;
  70
  71         g_assert (cfg->comp_done & MONO_COMP_REACHABILITY);
  72
  73         for (bb = cfg->bb_entry; bb && bb->next_bb;) {
  74                 if (!(bb->next_bb->flags & BB_REACHABLE)) {
  75                         bb->next_bb = bb->next_bb->next_bb;
  76                 } else
  77                         bb = bb->next_bb;
  78         }
  79
  80         for (i = 1; i < cfg->num_bblocks; i++) {
  81                 bb = cfg->bblocks [i];
  82
  83                 if (!(bb->flags & BB_REACHABLE)) {
  84                         for (j = 0; j < bb->in_count; j++) {
  85                                 unlink_target (bb->in_bb [j], bb);
  86                         }
  87                         for (j = 0; j < bb->out_count; j++) {
  88                                 unlink_target (bb, bb->out_bb [j]);
  89                         }
  90                 }
  91
  92         }
  93 }
  94
  95
  96
  97 static void
  98 replace_usage (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, MonoInst **stack)
  99 {
 100         int arity;
 101
 102         if (!inst)
 103                 return;
 104
 105         arity = mono_burg_arity [inst->opcode];
 106
 107         if ((inst->ssa_op == MONO_SSA_LOAD || inst->ssa_op == MONO_SSA_ADDRESS_TAKEN) &&
 108             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
 109                 MonoInst *new_var;
 110                 int idx = inst->inst_i0->inst_c0;
 111
 112                 if (stack [idx]) {
 113                         new_var = stack [idx];
 114                 } else {
 115                         new_var = cfg->varinfo [idx];
 116
 117                         if ((new_var->opcode != OP_ARG) && (new_var->opcode != OP_LOCAL)) {
 118                                 /* uninitialized variable ? */
 119                                 g_warning ("using uninitialized variables %d in BB%d (%s)", idx, bb->block_num,
 120                                            mono_method_full_name (cfg->method, TRUE));
 121                                 //g_assert_not_reached ();
 122                         }
 123                 }
 124 #ifdef DEBUG_SSA
 125                 printf ("REPLACE BB%d %d %d\n", bb->block_num, idx, new_var->inst_c0);
 126 #endif
 127                 inst->inst_i0 = new_var;
 128         } else {
 129
 130                 if (arity) {
 131                         if (inst->ssa_op != MONO_SSA_STORE)
 132                                 replace_usage (cfg, bb, inst->inst_left, stack);
 133                         if (arity > 1)
 134                                 replace_usage (cfg, bb, inst->inst_right, stack);
 135                 }
 136         }
 137 }
 138
 139 #if 0
 140
 141 static int
 142 extends_live (MonoInst *inst)
 143 {
 144         int arity;
 145
 146         if (!inst)
 147                 return 0;
 148
 149         arity = mono_burg_arity [inst->opcode];
 150
 151         if (inst->ssa_op == MONO_SSA_LOAD &&
 152             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
 153                 return 1;
 154         } else {
 155                 if (arity) {
 156                         if (inst->ssa_op != MONO_SSA_STORE)
 157                                 if (extends_live (inst->inst_left))
 158                                         return 1;
 159                         if (arity > 1)
 160                                 if (extends_live (inst->inst_right))
 161                                         return 1;
 162                 }
 163         }
 164
 165         return 0;
 166 }
 167
 168 static int
 169 replace_usage_new (MonoCompile *cfg, MonoInst *inst, int varnum, MonoInst *rep)
 170 {
 171         int arity;
 172
 173         if (!inst)
 174                 return 0;
 175
 176         arity = mono_burg_arity [inst->opcode];
 177
 178         if ((inst->ssa_op == MONO_SSA_LOAD) &&
 179             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
 180             inst->inst_i0->inst_c0 == varnum && rep->type == inst->type) {
 181                 *inst = *rep;
 182                 return 1;
 183         } else {
 184                 if (arity) {
 185                         if (inst->ssa_op != MONO_SSA_STORE)
 186                                 if (replace_usage_new (cfg, inst->inst_left, varnum, rep))
 187                                         return 1;
 188                         if (arity > 1)
 189                                 if (replace_usage_new (cfg, inst->inst_right, varnum, rep))
 190                                         return 1;
 191                 }
 192         }
 193
 194         return 0;
 195 }
 196
 197 #endif
 198
 199 static void
 200 mono_ssa_rename_vars (MonoCompile *cfg, int max_vars, MonoBasicBlock *bb, MonoInst **stack)
 201 {
 202         MonoInst *inst, *new_var;
 203         int i, j, idx;
 204         GSList *tmp;
 205         MonoInst **new_stack;
 206
 207 #ifdef DEBUG_SSA
 208         printf ("RENAME VARS BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
 209 #endif
 210
 211         MONO_BB_FOR_EACH_INS (bb, inst) {
 212                 if (inst->opcode != OP_PHI)
 213                         replace_usage (cfg, bb, inst, stack);
 214
 215                 if (inst->ssa_op == MONO_SSA_STORE &&
 216                     (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
 217                         idx = inst->inst_i0->inst_c0;
 218                         g_assert (idx < max_vars);
 219
 220                         if ((!stack [idx]) && (bb == cfg->bb_init) && (inst->inst_i0->opcode != OP_ARG)) {
 221                                 new_var = cfg->varinfo [idx];
 222                         } else {
 223                                 new_var = mono_compile_create_var (cfg, inst->inst_i0->inst_vtype,  inst->inst_i0->opcode);
 224                                 new_var->flags = inst->inst_i0->flags;
 225                         }
 226 #ifdef DEBUG_SSA
 227                         printf ("DEF %d %d\n", idx, new_var->inst_c0);
 228 #endif
 229                         inst->inst_i0 = new_var;
 230
 231 #ifdef USE_ORIGINAL_VARS
 232                         MONO_VARINFO (cfg, new_var->inst_c0)->reg = idx;
 233 #endif
 234
 235                         stack [idx] = new_var;
 236                 }
 237         }
 238
 239         for (i = 0; i < bb->out_count; i++) {
 240                 MonoBasicBlock *n = bb->out_bb [i];
 241
 242                 for (j = 0; j < n->in_count; j++)
 243                         if (n->in_bb [j] == bb)
 244                                 break;
 245
 246                 MONO_BB_FOR_EACH_INS (n, inst) {
 247                         if (inst->ssa_op == MONO_SSA_STORE && inst->inst_i1->opcode == OP_PHI) {
 248                                 idx = inst->inst_i1->inst_c0;
 249                                 if (stack [idx])
 250                                         new_var = stack [idx];
 251                                 else
 252                                         new_var = cfg->varinfo [idx];
 253 #ifdef DEBUG_SSA
 254                                 printf ("FOUND PHI %d (%d, %d)\n", idx, j, new_var->inst_c0);
 255 #endif
 256                                 inst->inst_i1->inst_phi_args [j + 1] = new_var->inst_c0;
 257
 258                         }
 259                 }
 260         }
 261
 262         if (bb->dominated) {
 263                 new_stack = g_new (MonoInst*, max_vars);
 264                 for (tmp = bb->dominated; tmp; tmp = tmp->next) {
 265                         memcpy (new_stack, stack, sizeof (MonoInst *) * max_vars);
 266                         mono_ssa_rename_vars (cfg, max_vars, (MonoBasicBlock *)tmp->data, new_stack);
 267                 }
 268                 g_free (new_stack);
 269         }
 270 }
 271
 272 void
 273 mono_ssa_compute (MonoCompile *cfg)
 274 {
 275         int i, idx;
 276         MonoBitSet *set;
 277         MonoMethodVar *vinfo = g_new0 (MonoMethodVar, cfg->num_varinfo);
 278         MonoInst *inst, *store, **stack;
 279
 280         g_assert (!(cfg->comp_done & MONO_COMP_SSA));
 281
 282         /* we dont support methods containing exception clauses */
 283         g_assert (mono_method_get_header (cfg->method)->num_clauses == 0);
 284         g_assert (!cfg->disable_ssa);
 285
 286         //printf ("COMPUTS SSA %s %d\n", mono_method_full_name (cfg->method, TRUE), cfg->num_varinfo);
 287
 288 #ifdef CREATE_PRUNED_SSA
 289         /* we need liveness for pruned SSA */
 290         if (!(cfg->comp_done & MONO_COMP_LIVENESS))
 291                 mono_analyze_liveness (cfg);
 292 #endif
 293
 294         mono_compile_dominator_info (cfg, MONO_COMP_DOM | MONO_COMP_IDOM | MONO_COMP_DFRONTIER);
 295
 296         for (i = 0; i < cfg->num_varinfo; ++i) {
 297                 vinfo [i].def_in = mono_bitset_new (cfg->num_bblocks, 0);
 298                 vinfo [i].idx = i;
 299                 /* implizit reference at start */
 300                 mono_bitset_set (vinfo [i].def_in, 0);
 301         }
 302         for (i = 0; i < cfg->num_bblocks; ++i) {
 303                 MONO_BB_FOR_EACH_INS (cfg->bblocks [i], inst) {
 304                         if (inst->ssa_op == MONO_SSA_STORE) {
 305                                 idx = inst->inst_i0->inst_c0;
 306                                 g_assert (idx < cfg->num_varinfo);
 307                                 mono_bitset_set (vinfo [idx].def_in, i);
 308                         }
 309                 }
 310         }
 311
 312         /* insert phi functions */
 313         for (i = 0; i < cfg->num_varinfo; ++i) {
 314                 set = mono_compile_iterated_dfrontier (cfg, vinfo [i].def_in);
 315                 mono_bitset_foreach_bit (set, idx, cfg->num_bblocks) {
 316                         MonoBasicBlock *bb = cfg->bblocks [idx];
 317
 318                         /* fixme: create pruned SSA? we would need liveness information for that */
 319
 320                         if (bb == cfg->bb_exit)
 321                                 continue;
 322
 323                         if ((cfg->comp_done & MONO_COMP_LIVENESS) && !mono_bitset_test_fast (bb->live_in_set, i)) {
 324                                 //printf ("%d is not live in BB%d %s\n", i, bb->block_num, mono_method_full_name (cfg->method, TRUE));
 325                                 continue;
 326                         }
 327
 328                         NEW_PHI (cfg, inst, i);
 329
 330                         inst->inst_phi_args =  mono_mempool_alloc0 (cfg->mempool, sizeof (int) * (cfg->bblocks [idx]->in_count + 1));
 331                         inst->inst_phi_args [0] = cfg->bblocks [idx]->in_count;
 332
 333                         store = mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoInst));
 334                         if (!cfg->varinfo [i]->inst_vtype->type)
 335                                 g_assert_not_reached ();
 336                         store->opcode = mono_type_to_stind (cfg->varinfo [i]->inst_vtype);
 337                         store->ssa_op = MONO_SSA_STORE;
 338                         store->inst_i0 = cfg->varinfo [i];
 339                         store->inst_i1 = inst;
 340                         store->klass = store->inst_i0->klass;
 341
 342                         store->next = bb->code;
 343                         bb->code = store;
 344                         if (!bb->last_ins)
 345                                 bb->last_ins = bb->code;
 346
 347 #ifdef DEBUG_SSA
 348                         printf ("ADD PHI BB%d %s\n", cfg->bblocks [idx]->block_num, mono_method_full_name (cfg->method, TRUE));
 349 #endif
 350                 }
 351         }
 352
 353         /* free the stuff */
 354         for (i = 0; i < cfg->num_varinfo; ++i)
 355                 mono_bitset_free (vinfo [i].def_in);
 356         g_free (vinfo);
 357
 358
 359         stack = alloca (sizeof (MonoInst *) * cfg->num_varinfo);
 360
 361         for (i = 0; i < cfg->num_varinfo; i++)
 362                 stack [i] = NULL;
 363
 364         mono_ssa_rename_vars (cfg, cfg->num_varinfo, cfg->bb_entry, stack);
 365
 366         cfg->comp_done |= MONO_COMP_SSA;
 367 }
 368
 369 #ifndef USE_ORIGINAL_VARS
 370 static GPtrArray *
 371 mono_ssa_get_allocatable_vars (MonoCompile *cfg)
 372 {
 373         GHashTable *type_hash;
 374         GPtrArray *varlist_array = g_ptr_array_new ();
 375         int tidx, i;
 376
 377         g_assert (cfg->comp_done & MONO_COMP_LIVENESS);
 378
 379         type_hash = g_hash_table_new (NULL, NULL);
 380
 381         for (i = 0; i < cfg->num_varinfo; i++) {
 382                 MonoInst *ins = cfg->varinfo [i];
 383                 MonoMethodVar *vmv = MONO_VARINFO (cfg, i);
 384
 385                 /* unused vars */
 386                 if (vmv->range.first_use.abs_pos > vmv->range.last_use.abs_pos)
 387                         continue;
 388
 389                 if (ins->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT) ||
 390                     (ins->opcode != OP_LOCAL && ins->opcode != OP_ARG) || vmv->reg != -1)
 391                         continue;
 392
 393                 g_assert (ins->inst_vtype);
 394                 g_assert (vmv->reg == -1);
 395                 g_assert (i == vmv->idx);
 396
 397                 if (!(tidx = (int)g_hash_table_lookup (type_hash, ins->inst_vtype))) {
 398                         GList *vars = g_list_append (NULL, vmv);
 399                         g_ptr_array_add (varlist_array, vars);
 400                         g_hash_table_insert (type_hash, ins->inst_vtype, (gpointer)varlist_array->len);
 401                 } else {
 402                         tidx--;
 403                         g_ptr_array_index (varlist_array, tidx) =
 404                                 mono_varlist_insert_sorted (cfg, g_ptr_array_index (varlist_array, tidx), vmv, FALSE);
 405                 }
 406         }
 407
 408         g_hash_table_destroy (type_hash);
 409
 410         return varlist_array;
 411 }
 412 #endif
 413
 414 static void
 415 mono_ssa_replace_copies (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, char *is_live)
 416 {
 417         int arity;
 418
 419         if (!inst)
 420                 return;
 421
 422         arity = mono_burg_arity [inst->opcode];
 423
 424         if ((inst->ssa_op == MONO_SSA_LOAD || inst->ssa_op == MONO_SSA_ADDRESS_TAKEN || inst->ssa_op == MONO_SSA_STORE) &&
 425             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
 426                 MonoInst *new_var;
 427                 int idx = inst->inst_i0->inst_c0;
 428                 MonoMethodVar *mv = MONO_VARINFO (cfg, idx);
 429
 430                 if (mv->reg != -1 && mv->reg != mv->idx) {
 431
 432                         is_live [mv->reg] = 1;
 433
 434                         new_var = cfg->varinfo [mv->reg];
 435
 436 #if 0
 437                         printf ("REPLACE COPY BB%d %d %d\n", bb->block_num, idx, new_var->inst_c0);
 438                         g_assert (cfg->varinfo [mv->reg]->inst_vtype == cfg->varinfo [idx]->inst_vtype);
 439 #endif
 440                         inst->inst_p0 = new_var;
 441                 } else {
 442                         is_live [mv->idx] = 1;
 443                 }
 444         }
 445
 446
 447         if (arity) {
 448                 mono_ssa_replace_copies (cfg, bb, inst->inst_left, is_live);
 449                 if (arity > 1)
 450                         mono_ssa_replace_copies (cfg, bb, inst->inst_right, is_live);
 451         }
 452
 453         if (inst->ssa_op == MONO_SSA_STORE && inst->inst_i1->ssa_op == MONO_SSA_LOAD &&
 454             inst->inst_i0->inst_c0 == inst->inst_i1->inst_i0->inst_c0) {
 455                 inst->ssa_op = MONO_SSA_NOP;
 456                 inst->opcode = OP_NOP;
 457         }
 458
 459 }
 460
 461 void
 462 mono_ssa_remove (MonoCompile *cfg)
 463 {
 464         MonoInst *inst, *phi;
 465         char *is_live;
 466         int i, j;
 467 #ifndef USE_ORIGINAL_VARS
 468         GPtrArray *varlist_array;
 469         GList *active;
 470 #endif
 471         g_assert (cfg->comp_done & MONO_COMP_SSA);
 472
 473         for (i = 0; i < cfg->num_bblocks; ++i) {
 474                 MonoBasicBlock *bb = cfg->bblocks [i];
 475                 MONO_BB_FOR_EACH_INS (bb, inst) {
 476                         if (inst->ssa_op == MONO_SSA_STORE && inst->inst_i1->opcode == OP_PHI) {
 477
 478                                 phi = inst->inst_i1;
 479                                 g_assert (phi->inst_phi_args [0] == bb->in_count);
 480
 481                                 for (j = 0; j < bb->in_count; j++) {
 482                                         MonoBasicBlock *pred = bb->in_bb [j];
 483                                         int idx = phi->inst_phi_args [j + 1];
 484                                         MonoMethodVar *mv = MONO_VARINFO (cfg, idx);
 485
 486                                         if (mv->reg != -1 && mv->reg != mv->idx) {
 487                                                 //printf ("PHICOPY %d %d -> %d\n", idx, mv->reg, inst->inst_i0->inst_c0);
 488                                                 idx = mv->reg;
 489                                         }
 490
 491
 492                                         if (idx != inst->inst_i0->inst_c0) {
 493 #ifdef DEBUG_SSA
 494                                                 printf ("MOVE %d to %d in BB%d\n", idx, inst->inst_i0->inst_c0, pred->block_num);
 495 #endif
 496                                                 mono_add_varcopy_to_end (cfg, pred, idx, inst->inst_i0->inst_c0);
 497                                         }
 498                                 }
 499
 500                                 /* remove the phi functions */
 501                                 inst->opcode = OP_NOP;
 502                                 inst->ssa_op = MONO_SSA_NOP;
 503                         }
 504                 }
 505         }
 506
 507 #ifndef USE_ORIGINAL_VARS
 508         /* we compute liveness again */
 509         cfg->comp_done &= ~MONO_COMP_LIVENESS;
 510         mono_analyze_liveness (cfg);
 511
 512         varlist_array = mono_ssa_get_allocatable_vars (cfg);
 513
 514         for (i = 0; i < varlist_array->len; i++) {
 515                 GList *l, *regs, *vars = g_ptr_array_index (varlist_array, i);
 516                 MonoMethodVar *vmv, *amv;
 517
 518                 if (g_list_length (vars) <= 1) {
 519                         continue;
 520                 }
 521
 522                 active = NULL;
 523                 regs = NULL;
 524
 525                 for (l = vars; l; l = l->next) {
 526                         vmv = l->data;
 527
 528                         /* expire old intervals in active */
 529                         while (active) {
 530                                 amv = (MonoMethodVar *)active->data;
 531
 532                                 if (amv->range.last_use.abs_pos >= vmv->range.first_use.abs_pos)
 533                                         break;
 534
 535                                 active = g_list_delete_link (active, active);
 536                                 regs = g_list_prepend (regs, (gpointer)amv->reg);
 537                         }
 538
 539                         if (!regs)
 540                                 regs = g_list_prepend (regs, (gpointer)vmv->idx);
 541
 542                         vmv->reg = (int)regs->data;
 543                         regs = g_list_delete_link (regs, regs);
 544                         active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
 545                 }
 546
 547                 g_list_free (active);
 548                 g_list_free (regs);
 549                 g_list_free (vars);
 550         }
 551
 552         g_ptr_array_free (varlist_array, TRUE);
 553
 554 #endif
 555
 556         is_live = alloca (cfg->num_varinfo);
 557         memset (is_live, 0, cfg->num_varinfo);
 558
 559         for (i = 0; i < cfg->num_bblocks; ++i) {
 560                 MonoBasicBlock *bb = cfg->bblocks [i];
 561
 562                 MONO_BB_FOR_EACH_INS (bb, inst)
 563                         mono_ssa_replace_copies (cfg, bb, inst, is_live);
 564         }
 565
 566         for (i = 0; i < cfg->num_varinfo; ++i) {
 567                 MONO_VARINFO (cfg, i)->reg = -1;
 568                 if (!is_live [i] && !(cfg->varinfo [i]->flags & MONO_INST_VOLATILE)) {
 569                         cfg->varinfo [i]->flags |= MONO_INST_IS_DEAD;
 570                 }
 571         }
 572
 573         if (cfg->comp_done & MONO_COMP_REACHABILITY)
 574                 unlink_unused_bblocks (cfg);
 575
 576         cfg->comp_done &= ~MONO_COMP_SSA;
 577 }
 578
 579
 580 #define IS_CALL(op) (op == CEE_CALLI || op == OP_CALL || op == OP_CALLVIRT || (op >= OP_VOIDCALL && op <= OP_CALL_MEMBASE))
 581
 582 typedef struct {
 583         MonoBasicBlock *bb;
 584         MonoInst *inst;
 585 } MonoVarUsageInfo;
 586
 587
 588
 589
 590 /*
 591  * Returns TRUE if the tree can have side effects.
 592  */
 593 static gboolean
 594 analyze_dev_use (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *root, MonoInst *inst)
 595 {
 596         MonoMethodVar *info;
 597         int i, idx, arity;
 598         gboolean has_side_effects;
 599
 600         if (!inst)
 601                 return FALSE;
 602
 603         arity = mono_burg_arity [inst->opcode];
 604         switch (inst->opcode) {
 605 #define ANALYZE_DEV_USE_SPECIFIC_OPS 1
 606 #define OPDEF(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) case a1:
 607 #include "simple-cee-ops.h"
 608 #undef OPDEF
 609 #define MINI_OP(a1,a2) case a1:
 610 #include "simple-mini-ops.h"
 611 #undef MINI_OP
 612 #undef ANALYZE_DEV_USE_SPECIFIC_OPS
 613                 has_side_effects = FALSE;
 614                 break;
 615         default:
 616                 has_side_effects = TRUE;
 617         }
 618
 619         if ((inst->ssa_op == MONO_SSA_STORE) &&
 620             (inst->inst_i0->opcode == OP_LOCAL /*|| inst->inst_i0->opcode == OP_ARG */)) {
 621                 idx = inst->inst_i0->inst_c0;
 622                 info = MONO_VARINFO (cfg, idx);
 623                 //printf ("%d defined in BB%d %p\n", idx, bb->block_num, root);
 624                 if (info->def) {
 625                         g_warning ("more than one definition of variable %d in %s", idx,
 626                                    mono_method_full_name (cfg->method, TRUE));
 627                         g_assert_not_reached ();
 628                 }
 629                 if (!IS_CALL (inst->inst_i1->opcode) /* && inst->inst_i1->opcode == OP_ICONST */) {
 630                         g_assert (inst == root);
 631                         info->def = root;
 632                         info->def_bb = bb;
 633                 }
 634
 635                 if (inst->inst_i1->opcode == OP_PHI) {
 636                         for (i = inst->inst_i1->inst_phi_args [0]; i > 0; i--) {
 637                                 MonoVarUsageInfo *ui = mono_mempool_alloc (cfg->mempool, sizeof (MonoVarUsageInfo));
 638                                 idx = inst->inst_i1->inst_phi_args [i];
 639                                 info = MONO_VARINFO (cfg, idx);
 640                                 //printf ("FOUND %d\n", idx);
 641                                 ui->bb = bb;
 642                                 ui->inst = root;
 643                                 info->uses = g_list_prepend_mempool (info->uses, cfg->mempool, ui);
 644                         }
 645                 }
 646         }
 647
 648         if ((inst->ssa_op == MONO_SSA_LOAD || inst->ssa_op == MONO_SSA_ADDRESS_TAKEN) &&
 649             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
 650                 MonoVarUsageInfo *ui = mono_mempool_alloc (cfg->mempool, sizeof (MonoVarUsageInfo));
 651                 idx = inst->inst_i0->inst_c0;
 652                 info = MONO_VARINFO (cfg, idx);
 653                 //printf ("FOUND %d\n", idx);
 654                 ui->bb = bb;
 655                 ui->inst = root;
 656                 info->uses = g_list_prepend_mempool (info->uses, cfg->mempool, ui);
 657         } else {
 658                 if (arity) {
 659                         //if (inst->ssa_op != MONO_SSA_STORE)
 660                         if (analyze_dev_use (cfg, bb, root, inst->inst_left))
 661                                 has_side_effects = TRUE;
 662                         if (arity > 1)
 663                                 if (analyze_dev_use (cfg, bb, root, inst->inst_right))
 664                                         has_side_effects = TRUE;
 665                 }
 666         }
 667
 668         return has_side_effects;
 669 }
 670
 671
 672 /* avoid unnecessary copies of variables:
 673  * Y <= X; Z = Y; is translated to Z = X;
 674  */
 675 static void
 676 mono_ssa_avoid_copies (MonoCompile *cfg)
 677 {
 678         MonoInst *inst, *next;
 679         MonoBasicBlock *bb;
 680         MonoMethodVar *i1, *i2;
 681
 682         g_assert ((cfg->comp_done & MONO_COMP_SSA_DEF_USE));
 683
 684         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 685                 MONO_BB_FOR_EACH_INS (bb, inst) {
 686                         if (inst->ssa_op == MONO_SSA_STORE && inst->inst_i0->opcode == OP_LOCAL &&
 687                             !IS_CALL (inst->inst_i1->opcode) && inst->inst_i1->opcode != OP_PHI && !inst->flags) {
 688                                 i1 = MONO_VARINFO (cfg, inst->inst_i0->inst_c0);
 689
 690 /* fixme: compiling mcs does not work when I enable this */
 691 #if 0
 692                                 if (g_list_length (i1->uses) == 1 && !extends_live (inst->inst_i1)) {
 693                                         MonoVarUsageInfo *vi = (MonoVarUsageInfo *)i1->uses->data;
 694                                         u = vi->inst;
 695
 696                                         //printf ("VAR %d %s\n", i1->idx, mono_method_full_name (cfg->method, TRUE));
 697                                         //mono_print_tree (inst); printf ("\n");
 698                                         //mono_print_tree (u); printf ("\n");
 699
 700                                         if (replace_usage_new (cfg, u, inst->inst_i0->inst_c0,  inst->inst_i1)) {
 701
 702                                                 //mono_print_tree (u); printf ("\n");
 703
 704                                                 inst->opcode = OP_NOP;
 705                                                 inst->ssa_op = MONO_SSA_NOP;
 706                                         }
 707                                 }
 708 #endif
 709                                 next = inst->next;
 710                                 if (next && next->ssa_op == MONO_SSA_STORE &&
 711                                                 next->inst_i0->opcode == OP_LOCAL &&
 712                                                 next->inst_i1->ssa_op == MONO_SSA_LOAD &&
 713                                                 next->inst_i1->inst_i0->opcode == OP_LOCAL &&
 714                                                 next->inst_i1->inst_i0->inst_c0 == inst->inst_i0->inst_c0 &&
 715                                                 g_list_length (i1->uses) == 1 &&
 716                                                 inst->opcode == next->opcode &&
 717                                                 inst->inst_i0->type == next->inst_i0->type) {
 718                                         i2 = MONO_VARINFO (cfg, next->inst_i0->inst_c0);
 719                                         //printf ("ELIM. COPY in BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
 720                                         inst->inst_i0 = next->inst_i0;
 721                                         i2->def = inst;
 722                                         i1->def = NULL;
 723                                         i1->uses = NULL;
 724                                         next->opcode = OP_NOP;
 725                                         next->ssa_op = MONO_SSA_NOP;
 726                                 }
 727                         }
 728                 }
 729         }
 730 }
 731
 732 static void
 733 mono_ssa_create_def_use (MonoCompile *cfg)
 734 {
 735         MonoBasicBlock *bb;
 736
 737         g_assert (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE));
 738
 739         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 740                 MonoInst *inst;
 741                 MONO_BB_FOR_EACH_INS (bb, inst) {
 742                         gboolean has_side_effects = analyze_dev_use (cfg, bb, inst, inst);
 743                         if (has_side_effects && (inst->ssa_op == MONO_SSA_STORE) &&
 744                                         (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
 745                                 inst->inst_i0->flags |= MONO_INST_DEFINITION_HAS_SIDE_EFFECTS;
 746                         }
 747                 }
 748         }
 749
 750         cfg->comp_done |= MONO_COMP_SSA_DEF_USE;
 751 }
 752
 753 static int
 754 simulate_compare (int opcode, int a, int b)
 755 {
 756         switch (opcode) {
 757         case CEE_BEQ:
 758                 return a == b;
 759         case CEE_BGE:
 760                 return a >= b;
 761         case CEE_BGT:
 762                 return a > b;
 763         case CEE_BLE:
 764                 return a <= b;
 765         case CEE_BLT:
 766                 return a < b;
 767         case CEE_BNE_UN:
 768                 return a != b;
 769         case CEE_BGE_UN:
 770                 return (unsigned)a >= (unsigned)b;
 771         case CEE_BGT_UN:
 772                 return (unsigned)a > (unsigned)b;
 773         case CEE_BLE_UN:
 774                 return (unsigned)a <= (unsigned)b;
 775         case CEE_BLT_UN:
 776                 return (unsigned)a < (unsigned)b;
 777         default:
 778                 g_assert_not_reached ();
 779         }
 780
 781         return 0;
 782 }
 783
 784 static int
 785 simulate_long_compare (int opcode, gint64 a, gint64 b)
 786 {
 787         switch (opcode) {
 788         case CEE_BEQ:
 789                 return a == b;
 790         case CEE_BGE:
 791                 return a >= b;
 792         case CEE_BGT:
 793                 return a > b;
 794         case CEE_BLE:
 795                 return a <= b;
 796         case CEE_BLT:
 797                 return a < b;
 798         case CEE_BNE_UN:
 799                 return a != b;
 800         case CEE_BGE_UN:
 801                 return (guint64)a >= (guint64)b;
 802         case CEE_BGT_UN:
 803                 return (guint64)a > (guint64)b;
 804         case CEE_BLE_UN:
 805                 return (guint64)a <= (guint64)b;
 806         case CEE_BLT_UN:
 807                 return (guint64)a < (guint64)b;
 808         default:
 809                 g_assert_not_reached ();
 810         }
 811
 812         return 0;
 813 }
 814
 815 #define EVAL_CXX(name,op,cast)  \
 816         case name:      \
 817                 if ((inst->inst_i0->opcode == OP_COMPARE) || (inst->inst_i0->opcode == OP_LCOMPARE)) { \
 818                         r1 = evaluate_const_tree (cfg, inst->inst_i0->inst_i0, &a, carray); \
 819                         r2 = evaluate_const_tree (cfg, inst->inst_i0->inst_i1, &b, carray); \
 820                         if (r1 == 1 && r2 == 1) { \
 821                                 *res = ((cast)a op (cast)b); \
 822                                 return 1; \
 823                         } else { \
 824                                 return MAX (r1, r2); \
 825                         } \
 826                 } \
 827                 break;
 828
 829 #define EVAL_BINOP(name,op)     \
 830         case name:      \
 831                 r1 = evaluate_const_tree (cfg, inst->inst_i0, &a, carray); \
 832                 r2 = evaluate_const_tree (cfg, inst->inst_i1, &b, carray); \
 833                 if (r1 == 1 && r2 == 1) { \
 834                         *res = (a op b); \
 835                         return 1; \
 836                 } else { \
 837                         return MAX (r1, r2); \
 838                 } \
 839                 break;
 840
 841
 842 /* fixme: this only works for interger constants, but not for other types (long, float) */
 843 static int
 844 evaluate_const_tree (MonoCompile *cfg, MonoInst *inst, int *res, MonoInst **carray)
 845 {
 846         MonoInst *c0;
 847         int a, b, r1, r2;
 848
 849         if (!inst)
 850                 return 0;
 851
 852         if (inst->ssa_op == MONO_SSA_LOAD &&
 853             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
 854             (c0 = carray [inst->inst_i0->inst_c0])) {
 855                 *res = c0->inst_c0;
 856                 return 1;
 857         }
 858
 859         switch (inst->opcode) {
 860         case OP_ICONST:
 861                 *res = inst->inst_c0;
 862                 return 1;
 863
 864         EVAL_CXX (OP_CEQ,==,gint32)
 865         EVAL_CXX (OP_CGT,>,gint32)
 866         EVAL_CXX (OP_CGT_UN,>,guint32)
 867         EVAL_CXX (OP_CLT,<,gint32)
 868         EVAL_CXX (OP_CLT_UN,<,guint32)
 869
 870         EVAL_BINOP (CEE_ADD,+)
 871         EVAL_BINOP (CEE_SUB,-)
 872         EVAL_BINOP (CEE_MUL,*)
 873         EVAL_BINOP (CEE_AND,&)
 874         EVAL_BINOP (CEE_OR,|)
 875         EVAL_BINOP (CEE_XOR,^)
 876         EVAL_BINOP (CEE_SHL,<<)
 877         EVAL_BINOP (CEE_SHR,>>)
 878
 879         default:
 880                 return 2;
 881         }
 882
 883         return 2;
 884 }
 885
 886 static void
 887 fold_tree (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, MonoInst **carray)
 888 {
 889         MonoInst *c0;
 890         int arity, a, b;
 891
 892         if (!inst)
 893                 return;
 894
 895         arity = mono_burg_arity [inst->opcode];
 896
 897         if (inst->ssa_op == MONO_SSA_STORE &&
 898             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
 899             inst->inst_i1->opcode == OP_PHI && (c0 = carray [inst->inst_i0->inst_c0])) {
 900                 //{static int cn = 0; printf ("PHICONST %d %d %s\n", cn++, c0->inst_c0, mono_method_full_name (cfg->method, TRUE));}
 901                 *inst->inst_i1 = *c0;
 902         } else if (inst->ssa_op == MONO_SSA_LOAD &&
 903             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
 904             (c0 = carray [inst->inst_i0->inst_c0])) {
 905                 //{static int cn = 0; printf ("YCCOPY %d %d %s\n", cn++, c0->inst_c0, mono_method_full_name (cfg->method, TRUE));}
 906                 *inst = *c0;
 907         } else {
 908
 909                 if (arity) {
 910                         fold_tree (cfg, bb, inst->inst_left, carray);
 911                         if (arity > 1)
 912                                 fold_tree (cfg, bb, inst->inst_right, carray);
 913                         mono_constant_fold_inst (inst, NULL);
 914                 }
 915         }
 916
 917         if ((inst->opcode >= CEE_BEQ && inst->opcode <= CEE_BLT_UN) &&
 918             ((inst->inst_i0->opcode == OP_COMPARE) || (inst->inst_i0->opcode == OP_LCOMPARE))) {
 919                 MonoInst *v0 = inst->inst_i0->inst_i0;
 920                 MonoInst *v1 = inst->inst_i0->inst_i1;
 921                 MonoBasicBlock *target = NULL;
 922
 923                 /* hack for longs to optimize the simply cases */
 924                 if (v0->opcode == OP_I8CONST && v1->opcode == OP_I8CONST) {
 925                         if (simulate_long_compare (inst->opcode, v0->inst_l, v1->inst_l)) {
 926                                 //unlink_target (bb, inst->inst_false_bb);
 927                                 target = inst->inst_true_bb;
 928                         } else {
 929                                 //unlink_target (bb, inst->inst_true_bb);
 930                                 target = inst->inst_false_bb;
 931                         }
 932                 } else if (evaluate_const_tree (cfg, v0, &a, carray) == 1 &&
 933                            evaluate_const_tree (cfg, v1, &b, carray) == 1) {
 934                         if (simulate_compare (inst->opcode, a, b)) {
 935                                 //unlink_target (bb, inst->inst_false_bb);
 936                                 target = inst->inst_true_bb;
 937                         } else {
 938                                 //unlink_target (bb, inst->inst_true_bb);
 939                                 target = inst->inst_false_bb;
 940                         }
 941                 }
 942
 943                 if (target) {
 944                         bb->out_bb [0] = target;
 945                         bb->out_count = 1;
 946                         inst->opcode = OP_BR;
 947                         inst->inst_target_bb = target;
 948                 }
 949         } else if (inst->opcode == OP_SWITCH && (evaluate_const_tree (cfg, inst->inst_left, &a, carray) == 1) && (a >= 0) && (a < GPOINTER_TO_INT (inst->klass))) {
 950                 bb->out_bb [0] = inst->inst_many_bb [a];
 951                 bb->out_count = 1;
 952                 inst->inst_target_bb = bb->out_bb [0];
 953                 inst->opcode = OP_BR;
 954         }
 955
 956 }
 957
 958 static void
 959 change_varstate (MonoCompile *cfg, GList **cvars, MonoMethodVar *info, int state, MonoInst *c0, MonoInst **carray)
 960 {
 961         if (info->cpstate >= state)
 962                 return;
 963
 964         info->cpstate = state;
 965
 966         //printf ("SETSTATE %d to %d\n", info->idx, info->cpstate);
 967
 968         if (state == 1)
 969                 carray [info->idx] = c0;
 970         else
 971                 carray [info->idx] = NULL;
 972
 973         if (!g_list_find (*cvars, info)) {
 974                 *cvars = g_list_prepend (*cvars, info);
 975         }
 976 }
 977
 978 static void
 979 visit_inst (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, GList **cvars, GList **bblist, MonoInst **carray)
 980 {
 981         g_assert (inst);
 982
 983         if (inst->opcode == OP_SWITCH) {
 984                 int r1, i, a;
 985                 int cases = GPOINTER_TO_INT (inst->klass);
 986
 987                 r1 = evaluate_const_tree (cfg, inst->inst_left, &a, carray);
 988                 if ((r1 == 1) && ((a < 0) || (a >= cases)))
 989                         r1 = 2;
 990                 if (r1 == 1) {
 991                         MonoBasicBlock *tb = inst->inst_many_bb [a];
 992                         if (!(tb->flags &  BB_REACHABLE)) {
 993                                 tb->flags |= BB_REACHABLE;
 994                                 *bblist = g_list_prepend (*bblist, tb);
 995                         }
 996                 } else if (r1 == 2) {
 997                         for (i = GPOINTER_TO_INT (inst->klass); i >= 0; i--) {
 998                                 MonoBasicBlock *tb = inst->inst_many_bb [i];
 999                                 if (!(tb->flags &  BB_REACHABLE)) {
1000                                         tb->flags |= BB_REACHABLE;
1001                                         *bblist = g_list_prepend (*bblist, tb);
1002                                 }
1003                         }
1004                 }
1005         } else if (inst->opcode == OP_BR) {
1006                 MonoBasicBlock *target = inst->inst_target_bb;
1007
1008                 if (!(target->flags &  BB_REACHABLE)) {
1009                         target->flags |= BB_REACHABLE;
1010                         *bblist = g_list_prepend (*bblist, target);
1011                 }
1012         } else if ((inst->opcode >= CEE_BEQ && inst->opcode <= CEE_BLT_UN) &&
1013             ((inst->inst_i0->opcode == OP_COMPARE) || (inst->inst_i0->opcode == OP_LCOMPARE))) {
1014                 int a, b, r1, r2;
1015                 MonoInst *v0 = inst->inst_i0->inst_i0;
1016                 MonoInst *v1 = inst->inst_i0->inst_i1;
1017
1018                 r1 = evaluate_const_tree (cfg, v0, &a, carray);
1019                 r2 = evaluate_const_tree (cfg, v1, &b, carray);
1020
1021                 if (r1 == 1 && r2 == 1) {
1022                         MonoBasicBlock *target;
1023
1024                         if (simulate_compare (inst->opcode, a, b)) {
1025                                 target = inst->inst_true_bb;
1026                         } else {
1027                                 target = inst->inst_false_bb;
1028                         }
1029                         if (!(target->flags &  BB_REACHABLE)) {
1030                                 target->flags |= BB_REACHABLE;
1031                                 *bblist = g_list_prepend (*bblist, target);
1032                         }
1033                 } else if (r1 == 2 || r2 == 2) {
1034                         if (!(inst->inst_true_bb->flags &  BB_REACHABLE)) {
1035                                 inst->inst_true_bb->flags |= BB_REACHABLE;
1036                                 *bblist = g_list_prepend (*bblist, inst->inst_true_bb);
1037                         }
1038                         if (!(inst->inst_false_bb->flags &  BB_REACHABLE)) {
1039                                 inst->inst_false_bb->flags |= BB_REACHABLE;
1040                                 *bblist = g_list_prepend (*bblist, inst->inst_false_bb);
1041                         }
1042                 }
1043         } else if (inst->ssa_op == MONO_SSA_STORE &&
1044                    (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
1045                 MonoMethodVar *info = MONO_VARINFO (cfg, inst->inst_i0->inst_c0);
1046                 MonoInst *i1 = inst->inst_i1;
1047                 int res;
1048
1049                 if (info->cpstate < 2) {
1050                         if (i1->opcode == OP_ICONST) {
1051                                 change_varstate (cfg, cvars, info, 1, i1, carray);
1052                         } else if (i1->opcode == OP_PHI) {
1053                                 MonoInst *c0 = NULL;
1054                                 int j;
1055
1056                                 for (j = 1; j <= i1->inst_phi_args [0]; j++) {
1057                                         MonoMethodVar *mv = MONO_VARINFO (cfg, i1->inst_phi_args [j]);
1058                                         MonoInst *src = mv->def;
1059
1060                                         if (mv->def_bb && !(mv->def_bb->flags & BB_REACHABLE)) {
1061                                                 continue;
1062                                         }
1063
1064                                         if (!mv->def || !src || src->ssa_op != MONO_SSA_STORE ||
1065                                             !(src->inst_i0->opcode == OP_LOCAL || src->inst_i0->opcode == OP_ARG) ||
1066                                             mv->cpstate == 2) {
1067                                                 change_varstate (cfg, cvars, info, 2, NULL, carray);
1068                                                 break;
1069                                         }
1070
1071                                         if (mv->cpstate == 0)
1072                                                 continue;
1073
1074                                         //g_assert (src->inst_i1->opcode == OP_ICONST);
1075                                         g_assert (carray [mv->idx]);
1076
1077                                         if (!c0) {
1078                                                 c0 = carray [mv->idx];
1079                                         }
1080
1081                                         if (carray [mv->idx]->inst_c0 != c0->inst_c0) {
1082                                                 change_varstate (cfg, cvars, info, 2, NULL, carray);
1083                                                 break;
1084                                         }
1085                                 }
1086
1087                                 if (c0 && info->cpstate < 1) {
1088                                         change_varstate (cfg, cvars, info, 1, c0, carray);
1089                                 }
1090                         } else {
1091                                 int state = evaluate_const_tree (cfg, i1, &res, carray);
1092                                 if (state == 1) {
1093                                         NEW_ICONST (cfg, i1, res);
1094                                         change_varstate (cfg, cvars, info, 1, i1, carray);
1095                                 } else {
1096                                         change_varstate (cfg, cvars, info, 2, NULL, carray);
1097                                 }
1098                         }
1099                 }
1100         }
1101 }
1102
1103 void
1104 mono_ssa_cprop (MonoCompile *cfg)
1105 {
1106         MonoInst **carray;
1107         MonoBasicBlock *bb;
1108         GList *bblock_list, *cvars;
1109         GList *tmp;
1110         int i;
1111         //printf ("SIMPLE OPTS BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
1112
1113         carray = g_new0 (MonoInst*, cfg->num_varinfo);
1114
1115         if (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE))
1116                 mono_ssa_create_def_use (cfg);
1117
1118         bblock_list = g_list_prepend (NULL, cfg->bb_entry);
1119         cfg->bb_entry->flags |= BB_REACHABLE;
1120
1121         memset (carray, 0, sizeof (MonoInst *) * cfg->num_varinfo);
1122
1123         for (i = 0; i < cfg->num_varinfo; i++) {
1124                 MonoMethodVar *info = MONO_VARINFO (cfg, i);
1125                 if (!info->def)
1126                         info->cpstate = 2;
1127         }
1128
1129         cvars = NULL;
1130
1131         while (bblock_list) {
1132                 MonoInst *inst;
1133
1134                 bb = (MonoBasicBlock *)bblock_list->data;
1135
1136                 bblock_list = g_list_delete_link (bblock_list, bblock_list);
1137
1138                 g_assert (bb->flags &  BB_REACHABLE);
1139
1140                 if (bb->out_count == 1) {
1141                         if (!(bb->out_bb [0]->flags &  BB_REACHABLE)) {
1142                                 bb->out_bb [0]->flags |= BB_REACHABLE;
1143                                 bblock_list = g_list_prepend (bblock_list, bb->out_bb [0]);
1144                         }
1145                 }
1146
1147                 MONO_BB_FOR_EACH_INS (bb, inst)
1148                         visit_inst (cfg, bb, inst, &cvars, &bblock_list, carray);
1149
1150                 while (cvars) {
1151                         MonoMethodVar *info = (MonoMethodVar *)cvars->data;
1152                         cvars = g_list_delete_link (cvars, cvars);
1153
1154                         for (tmp = info->uses; tmp; tmp = tmp->next) {
1155                                 MonoVarUsageInfo *ui = (MonoVarUsageInfo *)tmp->data;
1156                                 if (!(ui->bb->flags & BB_REACHABLE))
1157                                         continue;
1158                                 visit_inst (cfg, ui->bb, ui->inst, &cvars, &bblock_list, carray);
1159                         }
1160                 }
1161         }
1162
1163         for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
1164                 MonoInst *inst;
1165                 MONO_BB_FOR_EACH_INS (bb, inst)
1166                         fold_tree (cfg, bb, inst, carray);
1167         }
1168
1169         g_free (carray);
1170
1171         cfg->comp_done |= MONO_COMP_REACHABILITY;
1172 }
1173
1174 static void
1175 add_to_dce_worklist (MonoCompile *cfg, MonoMethodVar *var, MonoMethodVar *use, GList **wl)
1176 {
1177         GList *tmp;
1178
1179         *wl = g_list_prepend (*wl, use);
1180
1181         for (tmp = use->uses; tmp; tmp = tmp->next) {
1182                 MonoVarUsageInfo *ui = (MonoVarUsageInfo *)tmp->data;
1183                 if (ui->inst == var->def) {
1184                         /* from the mempool */
1185                         use->uses = g_list_remove_link (use->uses, tmp);
1186                         break;
1187                 }
1188         }
1189 }
1190
1191 void
1192 mono_ssa_deadce (MonoCompile *cfg)
1193 {
1194         int i;
1195         GList *work_list;
1196
1197         g_assert (cfg->comp_done & MONO_COMP_SSA);
1198
1199         //printf ("DEADCE %s\n", mono_method_full_name (cfg->method, TRUE));
1200
1201         /* fixme: we should update usage infos during cprop, instead of computing it again */
1202         cfg->comp_done &=  ~MONO_COMP_SSA_DEF_USE;
1203         for (i = 0; i < cfg->num_varinfo; i++) {
1204                 MonoMethodVar *info = MONO_VARINFO (cfg, i);
1205                 info->def = NULL;
1206                 info->uses = NULL;
1207         }
1208
1209         if (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE))
1210                 mono_ssa_create_def_use (cfg);
1211
1212         mono_ssa_avoid_copies (cfg);
1213
1214         work_list = NULL;
1215         for (i = 0; i < cfg->num_varinfo; i++) {
1216                 MonoMethodVar *info = MONO_VARINFO (cfg, i);
1217                 work_list = g_list_prepend (work_list, info);
1218
1219                 //if ((info->def != NULL) && (info->def->inst_i1->opcode != OP_PHI)) printf ("SSA DEADCE TOTAL LOCAL\n");
1220         }
1221
1222         while (work_list) {
1223                 MonoMethodVar *info = (MonoMethodVar *)work_list->data;
1224                 work_list = g_list_delete_link (work_list, work_list);
1225
1226                 if (!info->uses && info->def && (!(cfg->varinfo [info->idx]->flags & (MONO_INST_DEFINITION_HAS_SIDE_EFFECTS|MONO_INST_VOLATILE|MONO_INST_INDIRECT)))) {
1227                         MonoInst *i1;
1228                         //printf ("ELIMINATE %s: ", mono_method_full_name (cfg->method, TRUE)); mono_print_tree (info->def); printf ("\n");
1229
1230                         i1 = info->def->inst_i1;
1231                         if (i1->opcode == OP_PHI) {
1232                                 int j;
1233                                 for (j = i1->inst_phi_args [0]; j > 0; j--) {
1234                                         MonoMethodVar *u = MONO_VARINFO (cfg, i1->inst_phi_args [j]);
1235                                         add_to_dce_worklist (cfg, info, u, &work_list);
1236                                 }
1237                         } else if (i1->ssa_op == MONO_SSA_LOAD &&
1238                                    (i1->inst_i0->opcode == OP_LOCAL || i1->inst_i0->opcode == OP_ARG)) {
1239                                         MonoMethodVar *u = MONO_VARINFO (cfg, i1->inst_i0->inst_c0);
1240                                         add_to_dce_worklist (cfg, info, u, &work_list);
1241                         }
1242                         //if (i1->opcode != OP_PHI) printf ("SSA DEADCE DEAD LOCAL\n");
1243
1244                         info->def->opcode = OP_NOP;
1245                         info->def->ssa_op = MONO_SSA_NOP;
1246                 }
1247
1248         }
1249 }
1250
1251 #if 0
1252 void
1253 mono_ssa_strength_reduction (MonoCompile *cfg)
1254 {
1255         MonoBasicBlock *bb;
1256         int i;
1257
1258         g_assert (cfg->comp_done & MONO_COMP_SSA);
1259         g_assert (cfg->comp_done & MONO_COMP_LOOPS);
1260         g_assert (cfg->comp_done & MONO_COMP_SSA_DEF_USE);
1261
1262         for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
1263                 GList *lp = bb->loop_blocks;
1264
1265                 if (lp) {
1266                         MonoBasicBlock *h = (MonoBasicBlock *)lp->data;
1267
1268                         /* we only consider loops with 2 in bblocks */
1269                         if (!h->in_count == 2)
1270                                 continue;
1271
1272                         for (i = 0; i < cfg->num_varinfo; i++) {
1273                                 MonoMethodVar *info = MONO_VARINFO (cfg, i);
1274
1275                                 if (info->def && info->def->ssa_op == MONO_SSA_STORE &&
1276                                     info->def->inst_i0->opcode == OP_LOCAL && g_list_find (lp, info->def_bb)) {
1277                                         MonoInst *v = info->def->inst_i1;
1278
1279
1280                                         printf ("FOUND %d in %s\n", info->idx, mono_method_full_name (cfg->method, TRUE));
1281                                 }
1282                         }
1283                 }
1284         }
1285 }
1286 #endif
1287
1288 #endif /* DISABLE_SSA */
1289