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