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