mono/mini/ssa.c

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