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