for TARGET_J2EE only:
[mono.git] / mono / mini / ssa.c
1 /*
2  * ssa.c: Static single assign form support for the JIT compiler.
3  *
4  * Author:
5  *    Dietmar Maurer (dietmar@ximian.com)
6  *
7  * (C) 2003 Ximian, Inc.
8  */
9 #include <string.h>
10 #include <mono/metadata/debug-helpers.h>
11
12 #include "mini.h"
13
14 #ifndef DISABLE_SSA
15
16 #define USE_ORIGINAL_VARS
17 #define CREATE_PRUNED_SSA
18
19 //#define DEBUG_SSA 1
20
21 #define NEW_PHI(cfg,dest,val) do {      \
22                 (dest) = mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoInst));       \
23                 (dest)->opcode = OP_PHI;        \
24                 (dest)->inst_c0 = (val);        \
25         } while (0)
26
27 #define NEW_ICONST(cfg,dest,val) do {   \
28                 (dest) = mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoInst));       \
29                 (dest)->opcode = OP_ICONST;     \
30                 (dest)->inst_c0 = (val);        \
31                 (dest)->type = STACK_I4;        \
32         } while (0)
33
34
35 static GList*
36 g_list_prepend_mempool (GList* l, MonoMemPool* mp, gpointer datum)
37 {
38         GList* n = mono_mempool_alloc (mp, sizeof (GList));
39         n->next = l;
40         n->prev = NULL;
41         n->data = datum;
42         return n;
43 }
44
45 static void 
46 unlink_target (MonoBasicBlock *bb, MonoBasicBlock *target)
47 {
48         int i;
49
50         for (i = 0; i < bb->out_count; i++) {
51                 if (bb->out_bb [i] == target) {
52                         bb->out_bb [i] = bb->out_bb [--bb->out_count];
53                         break;
54                 }
55         }
56         for (i = 0; i < target->in_count; i++) {
57                 if (target->in_bb [i] == bb) {
58                         target->in_bb [i] = target->in_bb [--target->in_count];
59                         break;
60                         
61                 }
62         }
63 }
64
65 static void
66 unlink_unused_bblocks (MonoCompile *cfg) 
67 {
68         int i, j;
69         MonoBasicBlock *bb;
70
71         g_assert (cfg->comp_done & MONO_COMP_REACHABILITY);
72
73         for (bb = cfg->bb_entry; bb && bb->next_bb;) {
74                 if (!(bb->next_bb->flags & BB_REACHABLE)) {
75                         bb->next_bb = bb->next_bb->next_bb;
76                 } else 
77                         bb = bb->next_bb;
78         }
79
80         for (i = 1; i < cfg->num_bblocks; i++) {
81                 bb = cfg->bblocks [i];
82                
83                 if (!(bb->flags & BB_REACHABLE)) {
84                         for (j = 0; j < bb->in_count; j++) {
85                                 unlink_target (bb->in_bb [j], bb);      
86                         }
87                         for (j = 0; j < bb->out_count; j++) {
88                                 unlink_target (bb, bb->out_bb [j]);     
89                         }
90                 }
91  
92         }
93 }
94
95
96
97 static void
98 replace_usage (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, MonoInst **stack)
99 {
100         int arity;
101
102         if (!inst)
103                 return;
104
105         arity = mono_burg_arity [inst->opcode];
106
107         if ((inst->ssa_op == MONO_SSA_LOAD || inst->ssa_op == MONO_SSA_ADDRESS_TAKEN) && 
108             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
109                 MonoInst *new_var;
110                 int idx = inst->inst_i0->inst_c0;
111                         
112                 if (stack [idx]) {
113                         new_var = stack [idx];
114                 } else {
115                         new_var = cfg->varinfo [idx];
116
117                         if ((new_var->opcode != OP_ARG) && (new_var->opcode != OP_LOCAL)) {
118                                 /* uninitialized variable ? */
119                                 g_warning ("using uninitialized variables %d in BB%d (%s)", idx, bb->block_num,
120                                            mono_method_full_name (cfg->method, TRUE));
121                                 //g_assert_not_reached ();
122                         }
123                 }
124 #ifdef DEBUG_SSA
125                 printf ("REPLACE BB%d %d %d\n", bb->block_num, idx, new_var->inst_c0);
126 #endif
127                 inst->inst_i0 = new_var;
128         } else {
129
130                 if (arity) {
131                         if (inst->ssa_op != MONO_SSA_STORE)
132                                 replace_usage (cfg, bb, inst->inst_left, stack);
133                         if (arity > 1)
134                                 replace_usage (cfg, bb, inst->inst_right, stack);
135                 }
136         }
137 }
138
139 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         GSList *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_ADDRESS_TAKEN || 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 = OP_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 = OP_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
585
586
587 /*
588  * Returns TRUE if the tree can have side effects.
589  */
590 static gboolean
591 analyze_dev_use (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *root, MonoInst *inst)
592 {
593         MonoMethodVar *info;
594         int i, idx, arity;
595         gboolean has_side_effects;
596
597         if (!inst)
598                 return FALSE;
599
600         arity = mono_burg_arity [inst->opcode];
601         switch (inst->opcode) {
602 #define ANALYZE_DEV_USE_SPECIFIC_OPS 1
603 #define OPDEF(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) case a1:
604 #include "simple-cee-ops.h"
605 #undef OPDEF
606 #define MINI_OP(a1,a2) case a1:
607 #include "simple-mini-ops.h"
608 #undef MINI_OP
609 #undef ANALYZE_DEV_USE_SPECIFIC_OPS
610                 has_side_effects = FALSE;
611                 break;
612         default:
613                 has_side_effects = TRUE;
614         }
615
616         if ((inst->ssa_op == MONO_SSA_STORE) && 
617             (inst->inst_i0->opcode == OP_LOCAL /*|| inst->inst_i0->opcode == OP_ARG */)) {
618                 idx = inst->inst_i0->inst_c0;
619                 info = cfg->vars [idx];
620                 //printf ("%d defined in BB%d %p\n", idx, bb->block_num, root);
621                 if (info->def) {
622                         g_warning ("more than one definition of variable %d in %s", idx,
623                                    mono_method_full_name (cfg->method, TRUE));
624                         g_assert_not_reached ();
625                 }
626                 if (!IS_CALL (inst->inst_i1->opcode) /* && inst->inst_i1->opcode == OP_ICONST */) {
627                         g_assert (inst == root);
628                         info->def = root;
629                         info->def_bb = bb;
630                 }
631
632                 if (inst->inst_i1->opcode == OP_PHI) {
633                         for (i = inst->inst_i1->inst_phi_args [0]; i > 0; i--) {
634                                 MonoVarUsageInfo *ui = mono_mempool_alloc (cfg->mempool, sizeof (MonoVarUsageInfo));
635                                 idx = inst->inst_i1->inst_phi_args [i]; 
636                                 info = cfg->vars [idx];
637                                 //printf ("FOUND %d\n", idx);
638                                 ui->bb = bb;
639                                 ui->inst = root;
640                                 info->uses = g_list_prepend_mempool (info->uses, cfg->mempool, ui);
641                         }
642                 }
643         }
644
645         if ((inst->ssa_op == MONO_SSA_LOAD || inst->ssa_op == MONO_SSA_ADDRESS_TAKEN) && 
646             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
647                 MonoVarUsageInfo *ui = mono_mempool_alloc (cfg->mempool, sizeof (MonoVarUsageInfo));
648                 idx = inst->inst_i0->inst_c0;   
649                 info = cfg->vars [idx];
650                 //printf ("FOUND %d\n", idx);
651                 ui->bb = bb;
652                 ui->inst = root;
653                 info->uses = g_list_prepend_mempool (info->uses, cfg->mempool, ui);
654         } else {
655                 if (arity) {
656                         //if (inst->ssa_op != MONO_SSA_STORE)
657                         if (analyze_dev_use (cfg, bb, root, inst->inst_left))
658                                 has_side_effects = TRUE;
659                         if (arity > 1)
660                                 if (analyze_dev_use (cfg, bb, root, inst->inst_right))
661                                         has_side_effects = TRUE;
662                 }
663         }
664         
665         return has_side_effects;
666 }
667
668
669 /* avoid unnecessary copies of variables:
670  * Y <= X; Z = Y; is translated to Z = X;
671  */
672 static void
673 mono_ssa_avoid_copies (MonoCompile *cfg)
674 {
675         MonoInst *inst, *next;
676         MonoBasicBlock *bb;
677         MonoMethodVar *i1, *i2;
678
679         g_assert ((cfg->comp_done & MONO_COMP_SSA_DEF_USE));
680
681         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
682                 for (inst = bb->code; inst; inst = inst->next) {
683                         if (inst->ssa_op == MONO_SSA_STORE && inst->inst_i0->opcode == OP_LOCAL &&
684                             !IS_CALL (inst->inst_i1->opcode) && inst->inst_i1->opcode != OP_PHI && !inst->flags) {
685                                 i1 = cfg->vars [inst->inst_i0->inst_c0];
686
687 /* fixme: compiling mcs does not work when I enable this */
688 #if 0
689                                 if (g_list_length (i1->uses) == 1 && !extends_live (inst->inst_i1)) {
690                                         MonoVarUsageInfo *vi = (MonoVarUsageInfo *)i1->uses->data;
691                                         u = vi->inst;
692
693                                         //printf ("VAR %d %s\n", i1->idx, mono_method_full_name (cfg->method, TRUE));
694                                         //mono_print_tree (inst); printf ("\n");
695                                         //mono_print_tree (u); printf ("\n");
696
697                                         if (replace_usage_new (cfg, u, inst->inst_i0->inst_c0,  inst->inst_i1)) {
698                                                                                                                 
699                                                 //mono_print_tree (u); printf ("\n");
700                                                         
701                                                 inst->opcode = OP_NOP;
702                                                 inst->ssa_op = MONO_SSA_NOP;
703                                         }
704                                 }
705 #endif                  
706                                 if ((next = inst->next) && next->ssa_op == MONO_SSA_STORE && next->inst_i0->opcode == OP_LOCAL &&
707                                     next->inst_i1->ssa_op == MONO_SSA_LOAD &&  next->inst_i1->inst_i0->opcode == OP_LOCAL &&
708                                     next->inst_i1->inst_i0->inst_c0 == inst->inst_i0->inst_c0 && g_list_length (i1->uses) == 1 &&
709                                     inst->opcode == next->opcode && inst->inst_i0->type == next->inst_i0->type) {
710                                         i2 = cfg->vars [next->inst_i0->inst_c0];
711                                         //printf ("ELIM. COPY in BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
712                                         inst->inst_i0 = next->inst_i0;
713                                         i2->def = inst;
714                                         i1->def = NULL;
715                                         i1->uses = NULL;
716                                         next->opcode = OP_NOP;
717                                         next->ssa_op = MONO_SSA_NOP;
718                                 }
719                         }
720                 }
721         }
722 }
723
724 static void
725 mono_ssa_create_def_use (MonoCompile *cfg) 
726 {
727         MonoBasicBlock *bb;
728
729         g_assert (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE));
730
731         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
732                 MonoInst *inst;
733                 for (inst = bb->code; inst; inst = inst->next) {
734                         gboolean has_side_effects = analyze_dev_use (cfg, bb, inst, inst);
735                         if (has_side_effects && (inst->ssa_op == MONO_SSA_STORE) && 
736                                         (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
737                                 inst->inst_i0->flags |= MONO_INST_DEFINITION_HAS_SIDE_EFFECTS;
738                         }
739                 }
740         }
741
742         cfg->comp_done |= MONO_COMP_SSA_DEF_USE;
743 }
744
745 static int
746 simulate_compare (int opcode, int a, int b)
747 {
748         switch (opcode) {
749         case CEE_BEQ:
750                 return a == b;
751         case CEE_BGE:
752                 return a >= b;
753         case CEE_BGT:
754                 return a > b;
755         case CEE_BLE:
756                 return a <= b;
757         case CEE_BLT:
758                 return a < b;
759         case CEE_BNE_UN:
760                 return a != b;
761         case CEE_BGE_UN:
762                 return (unsigned)a >= (unsigned)b;
763         case CEE_BGT_UN:
764                 return (unsigned)a > (unsigned)b;
765         case CEE_BLE_UN:
766                 return (unsigned)a <= (unsigned)b;
767         case CEE_BLT_UN:
768                 return (unsigned)a < (unsigned)b;
769         default:
770                 g_assert_not_reached ();
771         }
772
773         return 0;
774 }
775
776 static int
777 simulate_long_compare (int opcode, gint64 a, gint64 b)
778 {
779         switch (opcode) {
780         case CEE_BEQ:
781                 return a == b;
782         case CEE_BGE:
783                 return a >= b;
784         case CEE_BGT:
785                 return a > b;
786         case CEE_BLE:
787                 return a <= b;
788         case CEE_BLT:
789                 return a < b;
790         case CEE_BNE_UN:
791                 return a != b;
792         case CEE_BGE_UN:
793                 return (guint64)a >= (guint64)b;
794         case CEE_BGT_UN:
795                 return (guint64)a > (guint64)b;
796         case CEE_BLE_UN:
797                 return (guint64)a <= (guint64)b;
798         case CEE_BLT_UN:
799                 return (guint64)a < (guint64)b;
800         default:
801                 g_assert_not_reached ();
802         }
803
804         return 0;
805 }
806
807 #define EVAL_CXX(name,op,cast)  \
808         case name:      \
809                 if ((inst->inst_i0->opcode == OP_COMPARE) || (inst->inst_i0->opcode == OP_LCOMPARE)) { \
810                         r1 = evaluate_const_tree (cfg, inst->inst_i0->inst_i0, &a, carray); \
811                         r2 = evaluate_const_tree (cfg, inst->inst_i0->inst_i1, &b, carray); \
812                         if (r1 == 1 && r2 == 1) { \
813                                 *res = ((cast)a op (cast)b); \
814                                 return 1; \
815                         } else { \
816                                 return MAX (r1, r2); \
817                         } \
818                 } \
819                 break;
820
821 #define EVAL_BINOP(name,op)     \
822         case name:      \
823                 r1 = evaluate_const_tree (cfg, inst->inst_i0, &a, carray); \
824                 r2 = evaluate_const_tree (cfg, inst->inst_i1, &b, carray); \
825                 if (r1 == 1 && r2 == 1) { \
826                         *res = (a op b); \
827                         return 1; \
828                 } else { \
829                         return MAX (r1, r2); \
830                 } \
831                 break;
832
833
834 /* fixme: this only works for interger constants, but not for other types (long, float) */
835 static int
836 evaluate_const_tree (MonoCompile *cfg, MonoInst *inst, int *res, MonoInst **carray)
837 {
838         MonoInst *c0;
839         int a, b, r1, r2;
840
841         if (!inst)
842                 return 0;
843
844         if (inst->ssa_op == MONO_SSA_LOAD && 
845             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
846             (c0 = carray [inst->inst_i0->inst_c0])) {
847                 *res = c0->inst_c0;
848                 return 1;
849         }
850
851         switch (inst->opcode) {
852         case OP_ICONST:
853                 *res = inst->inst_c0;
854                 return 1;
855
856         EVAL_CXX (OP_CEQ,==,gint32)
857         EVAL_CXX (OP_CGT,>,gint32)
858         EVAL_CXX (OP_CGT_UN,>,guint32)
859         EVAL_CXX (OP_CLT,<,gint32)
860         EVAL_CXX (OP_CLT_UN,<,guint32)
861
862         EVAL_BINOP (CEE_ADD,+)
863         EVAL_BINOP (CEE_SUB,-)
864         EVAL_BINOP (CEE_MUL,*)
865         EVAL_BINOP (CEE_AND,&)
866         EVAL_BINOP (CEE_OR,|)
867         EVAL_BINOP (CEE_XOR,^)
868         EVAL_BINOP (CEE_SHL,<<)
869         EVAL_BINOP (CEE_SHR,>>)
870
871         default:
872                 return 2;
873         }
874
875         return 2;
876 }
877
878 static void
879 fold_tree (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, MonoInst **carray)
880 {
881         MonoInst *c0;
882         int arity, a, b;
883
884         if (!inst)
885                 return;
886
887         arity = mono_burg_arity [inst->opcode];
888
889         if (inst->ssa_op == MONO_SSA_STORE && 
890             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
891             inst->inst_i1->opcode == OP_PHI && (c0 = carray [inst->inst_i0->inst_c0])) {
892                 //{static int cn = 0; printf ("PHICONST %d %d %s\n", cn++, c0->inst_c0, mono_method_full_name (cfg->method, TRUE));}
893                 *inst->inst_i1 = *c0;           
894         } else if (inst->ssa_op == MONO_SSA_LOAD && 
895             (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
896             (c0 = carray [inst->inst_i0->inst_c0])) {
897                 //{static int cn = 0; printf ("YCCOPY %d %d %s\n", cn++, c0->inst_c0, mono_method_full_name (cfg->method, TRUE));}
898                 *inst = *c0;
899         } else {
900
901                 if (arity) {
902                         fold_tree (cfg, bb, inst->inst_left, carray);
903                         if (arity > 1)
904                                 fold_tree (cfg, bb, inst->inst_right, carray);
905                         mono_constant_fold_inst (inst, NULL); 
906                 }
907         }
908
909         if ((inst->opcode >= CEE_BEQ && inst->opcode <= CEE_BLT_UN) &&
910             ((inst->inst_i0->opcode == OP_COMPARE) || (inst->inst_i0->opcode == OP_LCOMPARE))) {
911                 MonoInst *v0 = inst->inst_i0->inst_i0;
912                 MonoInst *v1 = inst->inst_i0->inst_i1;
913                 MonoBasicBlock *target = NULL;
914
915                 /* hack for longs to optimize the simply cases */
916                 if (v0->opcode == OP_I8CONST && v1->opcode == OP_I8CONST) {
917                         if (simulate_long_compare (inst->opcode, v0->inst_l, v1->inst_l)) {
918                                 //unlink_target (bb, inst->inst_false_bb);
919                                 target = inst->inst_true_bb;
920                         } else {
921                                 //unlink_target (bb, inst->inst_true_bb);
922                                 target = inst->inst_false_bb;
923                         }                       
924                 } else if (evaluate_const_tree (cfg, v0, &a, carray) == 1 &&
925                            evaluate_const_tree (cfg, v1, &b, carray) == 1) {                            
926                         if (simulate_compare (inst->opcode, a, b)) {
927                                 //unlink_target (bb, inst->inst_false_bb);
928                                 target = inst->inst_true_bb;
929                         } else {
930                                 //unlink_target (bb, inst->inst_true_bb);
931                                 target = inst->inst_false_bb;
932                         }
933                 }
934
935                 if (target) {
936                         bb->out_bb [0] = target;
937                         bb->out_count = 1;
938                         inst->opcode = OP_BR;
939                         inst->inst_target_bb = target;
940                 }
941         } else if (inst->opcode == OP_SWITCH && (evaluate_const_tree (cfg, inst->inst_left, &a, carray) == 1) && (a >= 0) && (a < GPOINTER_TO_INT (inst->klass))) {
942                 bb->out_bb [0] = inst->inst_many_bb [a];
943                 bb->out_count = 1;
944                 inst->inst_target_bb = bb->out_bb [0];
945                 inst->opcode = OP_BR;
946         }
947
948 }
949
950 static void
951 change_varstate (MonoCompile *cfg, GList **cvars, MonoMethodVar *info, int state, MonoInst *c0, MonoInst **carray)
952 {
953         if (info->cpstate >= state)
954                 return;
955
956         info->cpstate = state;
957
958         //printf ("SETSTATE %d to %d\n", info->idx, info->cpstate);
959
960         if (state == 1)
961                 carray [info->idx] = c0;
962         else
963                 carray [info->idx] = NULL;
964
965         if (!g_list_find (*cvars, info)) {
966                 *cvars = g_list_prepend (*cvars, info);
967         }
968 }
969
970 static void
971 visit_inst (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, GList **cvars, GList **bblist, MonoInst **carray)
972 {
973         g_assert (inst);
974
975         if (inst->opcode == OP_SWITCH) {
976                 int r1, i, a;
977                 int cases = GPOINTER_TO_INT (inst->klass);
978
979                 r1 = evaluate_const_tree (cfg, inst->inst_left, &a, carray);
980                 if ((r1 == 1) && ((a < 0) || (a >= cases)))
981                         r1 = 2;
982                 if (r1 == 1) {
983                         MonoBasicBlock *tb = inst->inst_many_bb [a];
984                         if (!(tb->flags &  BB_REACHABLE)) {
985                                 tb->flags |= BB_REACHABLE;
986                                 *bblist = g_list_prepend (*bblist, tb);
987                         }
988                 } else if (r1 == 2) {
989                         for (i = GPOINTER_TO_INT (inst->klass); i >= 0; i--) {
990                                 MonoBasicBlock *tb = inst->inst_many_bb [i];
991                                 if (!(tb->flags &  BB_REACHABLE)) {
992                                         tb->flags |= BB_REACHABLE;
993                                         *bblist = g_list_prepend (*bblist, tb);
994                                 }
995                         }
996                 }
997         } else if (inst->opcode == OP_BR) {
998                 MonoBasicBlock *target = inst->inst_target_bb;
999
1000                 if (!(target->flags &  BB_REACHABLE)) {
1001                         target->flags |= BB_REACHABLE;
1002                         *bblist = g_list_prepend (*bblist, target);
1003                 }
1004         } else if ((inst->opcode >= CEE_BEQ && inst->opcode <= CEE_BLT_UN) &&
1005             ((inst->inst_i0->opcode == OP_COMPARE) || (inst->inst_i0->opcode == OP_LCOMPARE))) {
1006                 int a, b, r1, r2;
1007                 MonoInst *v0 = inst->inst_i0->inst_i0;
1008                 MonoInst *v1 = inst->inst_i0->inst_i1;
1009
1010                 r1 = evaluate_const_tree (cfg, v0, &a, carray);
1011                 r2 = evaluate_const_tree (cfg, v1, &b, carray);
1012
1013                 if (r1 == 1 && r2 == 1) {
1014                         MonoBasicBlock *target;
1015                                 
1016                         if (simulate_compare (inst->opcode, a, b)) {
1017                                 target = inst->inst_true_bb;
1018                         } else {
1019                                 target = inst->inst_false_bb;
1020                         }
1021                         if (!(target->flags &  BB_REACHABLE)) {
1022                                 target->flags |= BB_REACHABLE;
1023                                 *bblist = g_list_prepend (*bblist, target);
1024                         }
1025                 } else if (r1 == 2 || r2 == 2) {
1026                         if (!(inst->inst_true_bb->flags &  BB_REACHABLE)) {
1027                                 inst->inst_true_bb->flags |= BB_REACHABLE;
1028                                 *bblist = g_list_prepend (*bblist, inst->inst_true_bb);
1029                         }
1030                         if (!(inst->inst_false_bb->flags &  BB_REACHABLE)) {
1031                                 inst->inst_false_bb->flags |= BB_REACHABLE;
1032                                 *bblist = g_list_prepend (*bblist, inst->inst_false_bb);
1033                         }
1034                 }       
1035         } else if (inst->ssa_op == MONO_SSA_STORE && 
1036                    (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
1037                 MonoMethodVar *info = cfg->vars [inst->inst_i0->inst_c0];
1038                 MonoInst *i1 = inst->inst_i1;
1039                 int res;
1040                 
1041                 if (info->cpstate < 2) {
1042                         if (i1->opcode == OP_ICONST) { 
1043                                 change_varstate (cfg, cvars, info, 1, i1, carray);
1044                         } else if (i1->opcode == OP_PHI) {
1045                                 MonoInst *c0 = NULL;
1046                                 int j;
1047
1048                                 for (j = 1; j <= i1->inst_phi_args [0]; j++) {
1049                                         MonoMethodVar *mv = cfg->vars [i1->inst_phi_args [j]];
1050                                         MonoInst *src = mv->def;
1051
1052                                         if (mv->def_bb && !(mv->def_bb->flags & BB_REACHABLE)) {
1053                                                 continue;
1054                                         }
1055
1056                                         if (!mv->def || !src || src->ssa_op != MONO_SSA_STORE ||
1057                                             !(src->inst_i0->opcode == OP_LOCAL || src->inst_i0->opcode == OP_ARG) ||
1058                                             mv->cpstate == 2) {
1059                                                 change_varstate (cfg, cvars, info, 2, NULL, carray);
1060                                                 break;
1061                                         }
1062                                         
1063                                         if (mv->cpstate == 0)
1064                                                 continue;
1065
1066                                         //g_assert (src->inst_i1->opcode == OP_ICONST);
1067                                         g_assert (carray [mv->idx]);
1068
1069                                         if (!c0) {
1070                                                 c0 = carray [mv->idx];
1071                                         }
1072                                         
1073                                         if (carray [mv->idx]->inst_c0 != c0->inst_c0) {
1074                                                 change_varstate (cfg, cvars, info, 2, NULL, carray);
1075                                                 break;
1076                                         }
1077                                 }
1078                                 
1079                                 if (c0 && info->cpstate < 1) {
1080                                         change_varstate (cfg, cvars, info, 1, c0, carray);
1081                                 }
1082                         } else {
1083                                 int state = evaluate_const_tree (cfg, i1, &res, carray);
1084                                 if (state == 1) {
1085                                         NEW_ICONST (cfg, i1, res);
1086                                         change_varstate (cfg, cvars, info, 1, i1, carray);
1087                                 } else {
1088                                         change_varstate (cfg, cvars, info, 2, NULL, carray);
1089                                 }
1090                         }
1091                 }
1092         }
1093 }
1094
1095 void
1096 mono_ssa_cprop (MonoCompile *cfg) 
1097 {
1098         MonoInst **carray;
1099         MonoBasicBlock *bb;
1100         GList *bblock_list, *cvars;
1101         GList *tmp;
1102         int i;
1103         //printf ("SIMPLE OPTS BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
1104
1105         carray = g_new0 (MonoInst*, cfg->num_varinfo);
1106
1107         if (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE))
1108                 mono_ssa_create_def_use (cfg);
1109
1110         bblock_list = g_list_prepend (NULL, cfg->bb_entry);
1111         cfg->bb_entry->flags |= BB_REACHABLE;
1112
1113         memset (carray, 0, sizeof (MonoInst *) * cfg->num_varinfo);
1114
1115         for (i = 0; i < cfg->num_varinfo; i++) {
1116                 MonoMethodVar *info = cfg->vars [i];
1117                 if (!info->def)
1118                         info->cpstate = 2;
1119         }
1120
1121         cvars = NULL;
1122
1123         while (bblock_list) {
1124                 MonoInst *inst;
1125
1126                 bb = (MonoBasicBlock *)bblock_list->data;
1127
1128                 bblock_list = g_list_delete_link (bblock_list, bblock_list);
1129
1130                 g_assert (bb->flags &  BB_REACHABLE);
1131
1132                 if (bb->out_count == 1) {
1133                         if (!(bb->out_bb [0]->flags &  BB_REACHABLE)) {
1134                                 bb->out_bb [0]->flags |= BB_REACHABLE;
1135                                 bblock_list = g_list_prepend (bblock_list, bb->out_bb [0]);
1136                         }
1137                 }
1138
1139                 for (inst = bb->code; inst; inst = inst->next) {
1140                         visit_inst (cfg, bb, inst, &cvars, &bblock_list, carray);
1141                 }
1142
1143                 while (cvars) {
1144                         MonoMethodVar *info = (MonoMethodVar *)cvars->data;                     
1145                         cvars = g_list_delete_link (cvars, cvars);
1146
1147                         for (tmp = info->uses; tmp; tmp = tmp->next) {
1148                                 MonoVarUsageInfo *ui = (MonoVarUsageInfo *)tmp->data;
1149                                 if (!(ui->bb->flags & BB_REACHABLE))
1150                                         continue;
1151                                 visit_inst (cfg, ui->bb, ui->inst, &cvars, &bblock_list, carray);
1152                         }
1153                 }
1154         }
1155
1156         for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
1157                 MonoInst *inst;
1158                 for (inst = bb->code; inst; inst = inst->next) {
1159                         fold_tree (cfg, bb, inst, carray);
1160                 }
1161         }
1162
1163         g_free (carray);
1164
1165         cfg->comp_done |= MONO_COMP_REACHABILITY;
1166 }
1167
1168 static void
1169 add_to_dce_worklist (MonoCompile *cfg, MonoMethodVar *var, MonoMethodVar *use, GList **wl)
1170 {
1171         GList *tmp;
1172
1173         *wl = g_list_prepend (*wl, use);
1174
1175         for (tmp = use->uses; tmp; tmp = tmp->next) {
1176                 MonoVarUsageInfo *ui = (MonoVarUsageInfo *)tmp->data;
1177                 if (ui->inst == var->def) {
1178                         /* from the mempool */
1179                         use->uses = g_list_remove_link (use->uses, tmp);
1180                         break;
1181                 }
1182         }       
1183 }
1184
1185 void
1186 mono_ssa_deadce (MonoCompile *cfg) 
1187 {
1188         int i;
1189         GList *work_list;
1190
1191         g_assert (cfg->comp_done & MONO_COMP_SSA);
1192
1193         //printf ("DEADCE %s\n", mono_method_full_name (cfg->method, TRUE));
1194
1195         /* fixme: we should update usage infos during cprop, instead of computing it again */
1196         cfg->comp_done &=  ~MONO_COMP_SSA_DEF_USE;
1197         for (i = 0; i < cfg->num_varinfo; i++) {
1198                 MonoMethodVar *info = cfg->vars [i];
1199                 info->def = NULL;
1200                 info->uses = NULL;
1201         }
1202
1203         if (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE))
1204                 mono_ssa_create_def_use (cfg);
1205
1206         mono_ssa_avoid_copies (cfg);
1207
1208         work_list = NULL;
1209         for (i = 0; i < cfg->num_varinfo; i++) {
1210                 MonoMethodVar *info = cfg->vars [i];
1211                 work_list = g_list_prepend (work_list, info);
1212                 
1213                 //if ((info->def != NULL) && (info->def->inst_i1->opcode != OP_PHI)) printf ("SSA DEADCE TOTAL LOCAL\n");
1214         }
1215
1216         while (work_list) {
1217                 MonoMethodVar *info = (MonoMethodVar *)work_list->data;
1218                 work_list = g_list_delete_link (work_list, work_list);
1219
1220                 if (!info->uses && info->def && (!(cfg->varinfo [info->idx]->flags & (MONO_INST_DEFINITION_HAS_SIDE_EFFECTS|MONO_INST_VOLATILE|MONO_INST_INDIRECT)))) {
1221                         MonoInst *i1;
1222                         //printf ("ELIMINATE %s: ", mono_method_full_name (cfg->method, TRUE)); mono_print_tree (info->def); printf ("\n");
1223
1224                         i1 = info->def->inst_i1;
1225                         if (i1->opcode == OP_PHI) {
1226                                 int j;
1227                                 for (j = i1->inst_phi_args [0]; j > 0; j--) {
1228                                         MonoMethodVar *u = cfg->vars [i1->inst_phi_args [j]];
1229                                         add_to_dce_worklist (cfg, info, u, &work_list);
1230                                 }
1231                         } else if (i1->ssa_op == MONO_SSA_LOAD &&
1232                                    (i1->inst_i0->opcode == OP_LOCAL || i1->inst_i0->opcode == OP_ARG)) {
1233                                         MonoMethodVar *u = cfg->vars [i1->inst_i0->inst_c0];
1234                                         add_to_dce_worklist (cfg, info, u, &work_list);
1235                         }
1236                         //if (i1->opcode != OP_PHI) printf ("SSA DEADCE DEAD LOCAL\n");
1237
1238                         info->def->opcode = OP_NOP;
1239                         info->def->ssa_op = MONO_SSA_NOP;
1240                 }
1241
1242         }
1243 }
1244
1245 #if 0
1246 void
1247 mono_ssa_strength_reduction (MonoCompile *cfg)
1248 {
1249         MonoBasicBlock *bb;
1250         int i;
1251
1252         g_assert (cfg->comp_done & MONO_COMP_SSA);
1253         g_assert (cfg->comp_done & MONO_COMP_LOOPS);
1254         g_assert (cfg->comp_done & MONO_COMP_SSA_DEF_USE);
1255
1256         for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
1257                 GList *lp = bb->loop_blocks;
1258
1259                 if (lp) {
1260                         MonoBasicBlock *h = (MonoBasicBlock *)lp->data;
1261
1262                         /* we only consider loops with 2 in bblocks */
1263                         if (!h->in_count == 2)
1264                                 continue;
1265
1266                         for (i = 0; i < cfg->num_varinfo; i++) {
1267                                 MonoMethodVar *info = cfg->vars [i];
1268                         
1269                                 if (info->def && info->def->ssa_op == MONO_SSA_STORE &&
1270                                     info->def->inst_i0->opcode == OP_LOCAL && g_list_find (lp, info->def_bb)) {
1271                                         MonoInst *v = info->def->inst_i1;
1272
1273
1274                                         printf ("FOUND %d in %s\n", info->idx, mono_method_full_name (cfg->method, TRUE));
1275                                 }
1276                         }
1277                 }
1278         }
1279 }
1280 #endif
1281
1282 #endif /* DISABLE_SSA */
1283