2 * ssa.c: Static single assign form support for the JIT compiler.
5 * Dietmar Maurer (dietmar@ximian.com)
7 * (C) 2003 Ximian, Inc.
10 #include <mono/metadata/debug-helpers.h>
14 extern guint8 mono_burg_arity [];
16 #define USE_ORIGINAL_VARS
17 #define CREATE_PRUNED_SSA
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); \
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; \
36 unlink_target (MonoBasicBlock *bb, MonoBasicBlock *target)
40 for (i = 0; i < bb->out_count; i++) {
41 if (bb->out_bb [i] == target) {
42 bb->out_bb [i] = bb->out_bb [--bb->out_count];
46 for (i = 0; i < target->in_count; i++) {
47 if (target->in_bb [i] == bb) {
48 target->in_bb [i] = target->in_bb [--target->in_count];
56 unlink_unused_bblocks (MonoCompile *cfg)
61 g_assert (cfg->comp_done & MONO_COMP_REACHABILITY);
63 for (bb = cfg->bb_entry; bb && bb->next_bb;) {
64 if (!(bb->next_bb->flags & BB_REACHABLE)) {
65 bb->next_bb = bb->next_bb->next_bb;
70 for (i = 1; i < cfg->num_bblocks; i++) {
71 bb = cfg->bblocks [i];
73 if (!(bb->flags & BB_REACHABLE)) {
74 for (j = 0; j < bb->in_count; j++) {
75 unlink_target (bb->in_bb [j], bb);
77 for (j = 0; j < bb->out_count; j++) {
78 unlink_target (bb, bb->out_bb [j]);
88 replace_usage (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, MonoInst **stack)
95 arity = mono_burg_arity [inst->opcode];
97 if ((inst->ssa_op == MONO_SSA_LOAD || inst->ssa_op == MONO_SSA_MAYBE_LOAD) &&
98 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
100 int idx = inst->inst_i0->inst_c0;
103 new_var = stack [idx];
105 new_var = cfg->varinfo [idx];
107 if (new_var->opcode != OP_ARG) {
108 /* uninitialized variable ? */
109 g_warning ("using uninitialized variables %d in BB%d (%s)", idx, bb->block_num,
110 mono_method_full_name (cfg->method, TRUE));
111 //g_assert_not_reached ();
115 printf ("REPLACE BB%d %d %d\n", bb->block_num, idx, new_var->inst_c0);
117 inst->inst_i0 = new_var;
121 if (inst->ssa_op != MONO_SSA_STORE)
122 replace_usage (cfg, bb, inst->inst_left, stack);
124 replace_usage (cfg, bb, inst->inst_right, stack);
130 extends_live (MonoInst *inst)
137 arity = mono_burg_arity [inst->opcode];
139 if (inst->ssa_op == MONO_SSA_LOAD &&
140 (inst->inst_i0->opcode == OP_LOCAL /*|| inst->inst_i0->opcode == OP_ARG*/)) {
144 if (inst->ssa_op != MONO_SSA_STORE)
145 if (extends_live (inst->inst_left))
148 if (extends_live (inst->inst_right))
157 replace_usage_new (MonoCompile *cfg, MonoInst *inst, int varnum, MonoInst *rep)
164 arity = mono_burg_arity [inst->opcode];
166 if ((inst->ssa_op == MONO_SSA_LOAD) &&
167 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
168 inst->inst_i0->inst_c0 == varnum && rep->type == inst->type) {
173 if (inst->ssa_op != MONO_SSA_STORE)
174 if (replace_usage_new (cfg, inst->inst_left, varnum, rep))
177 if (replace_usage_new (cfg, inst->inst_right, varnum, rep))
186 mono_ssa_rename_vars (MonoCompile *cfg, int max_vars, MonoBasicBlock *bb, MonoInst **stack)
188 MonoInst *inst, *new_var;
191 MonoInst *new_stack [max_vars];
194 printf ("RENAME VARS BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
197 for (inst = bb->code; inst; inst = inst->next) {
198 if (inst->opcode != OP_PHI)
199 replace_usage (cfg, bb, inst, stack);
201 if (inst->ssa_op == MONO_SSA_STORE &&
202 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
203 idx = inst->inst_i0->inst_c0;
204 g_assert (idx < max_vars);
206 if (!stack [idx] && bb == cfg->bb_init) {
207 new_var = cfg->varinfo [idx];
209 new_var = mono_compile_create_var (cfg, inst->inst_i0->inst_vtype, inst->inst_i0->opcode);
210 new_var->flags = inst->inst_i0->flags;
213 printf ("DEF %d %d\n", idx, new_var->inst_c0);
215 inst->inst_i0 = new_var;
217 #ifdef USE_ORIGINAL_VARS
218 cfg->vars [new_var->inst_c0]->reg = idx;
221 stack [idx] = new_var;
225 for (i = 0; i < bb->out_count; i++) {
226 MonoBasicBlock *n = bb->out_bb [i];
228 for (j = 0; j < n->in_count; j++)
229 if (n->in_bb [j] == bb)
232 for (inst = n->code; inst; inst = inst->next) {
233 if (inst->ssa_op == MONO_SSA_STORE && inst->inst_i1->opcode == OP_PHI) {
234 idx = inst->inst_i1->inst_c0;
236 new_var = stack [idx];
238 new_var = cfg->varinfo [idx];
240 printf ("FOUND PHI %d (%d, %d)\n", idx, j, new_var->inst_c0);
242 inst->inst_i1->inst_phi_args [j + 1] = new_var->inst_c0;
248 for (tmp = bb->dominated; tmp; tmp = tmp->next) {
249 memcpy (new_stack, stack, sizeof (MonoInst *) * max_vars);
250 mono_ssa_rename_vars (cfg, max_vars, (MonoBasicBlock *)tmp->data, new_stack);
255 mono_ssa_compute (MonoCompile *cfg)
259 MonoMethodVar *vinfo = g_new0 (MonoMethodVar, cfg->num_varinfo);
260 MonoInst *inst, *store, **stack;
262 g_assert (!(cfg->comp_done & MONO_COMP_SSA));
264 /* we dont support methods containing exception clauses */
265 g_assert (((MonoMethodNormal *)cfg->method)->header->num_clauses == 0);
266 g_assert (!cfg->disable_ssa);
268 //printf ("COMPUTS SSA %s %d\n", mono_method_full_name (cfg->method, TRUE), cfg->num_varinfo);
270 #ifdef CREATE_PRUNED_SSA
271 /* we need liveness for pruned SSA */
272 if (!(cfg->comp_done & MONO_COMP_LIVENESS))
273 mono_analyze_liveness (cfg);
276 mono_compile_dominator_info (cfg, MONO_COMP_DOM | MONO_COMP_IDOM | MONO_COMP_DFRONTIER);
278 for (i = 0; i < cfg->num_varinfo; ++i) {
279 vinfo [i].def_in = mono_bitset_new (cfg->num_bblocks, 0);
281 /* implizit reference at start */
282 mono_bitset_set (vinfo [i].def_in, 0);
284 for (i = 0; i < cfg->num_bblocks; ++i) {
285 for (inst = cfg->bblocks [i]->code; inst; inst = inst->next) {
286 if (inst->ssa_op == MONO_SSA_STORE) {
287 idx = inst->inst_i0->inst_c0;
288 g_assert (idx < cfg->num_varinfo);
289 mono_bitset_set (vinfo [idx].def_in, i);
294 /* insert phi functions */
295 for (i = 0; i < cfg->num_varinfo; ++i) {
296 set = mono_compile_iterated_dfrontier (cfg, vinfo [i].def_in);
297 vinfo [i].dfrontier = set;
298 mono_bitset_foreach_bit (set, idx, cfg->num_bblocks) {
299 MonoBasicBlock *bb = cfg->bblocks [idx];
301 /* fixme: create pruned SSA? we would need liveness information for that */
303 if (bb == cfg->bb_exit)
306 if ((cfg->comp_done & MONO_COMP_LIVENESS) && !mono_bitset_test_fast (bb->live_in_set, i)) {
307 //printf ("%d is not live in BB%d %s\n", i, bb->block_num, mono_method_full_name (cfg->method, TRUE));
311 NEW_PHI (cfg, inst, i);
313 inst->inst_phi_args = mono_mempool_alloc0 (cfg->mempool, sizeof (int) * (cfg->bblocks [idx]->in_count + 1));
314 inst->inst_phi_args [0] = cfg->bblocks [idx]->in_count;
316 store = mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoInst));
317 if (!cfg->varinfo [i]->inst_vtype->type)
318 g_assert_not_reached ();
319 store->opcode = mono_type_to_stind (cfg->varinfo [i]->inst_vtype);
320 store->ssa_op = MONO_SSA_STORE;
321 store->inst_i0 = cfg->varinfo [i];
322 store->inst_i1 = inst;
323 store->klass = store->inst_i0->klass;
325 store->next = bb->code;
329 printf ("ADD PHI BB%d %s\n", cfg->bblocks [idx]->block_num, mono_method_full_name (cfg->method, TRUE));
335 for (i = 0; i < cfg->num_varinfo; ++i)
336 mono_bitset_free (vinfo [i].def_in);
340 stack = alloca (sizeof (MonoInst *) * cfg->num_varinfo);
342 for (i = 0; i < cfg->num_varinfo; i++)
345 mono_ssa_rename_vars (cfg, cfg->num_varinfo, cfg->bb_entry, stack);
347 cfg->comp_done |= MONO_COMP_SSA;
350 #ifndef USE_ORIGINAL_VARS
352 mono_ssa_get_allocatable_vars (MonoCompile *cfg)
354 GHashTable *type_hash;
355 GPtrArray *varlist_array = g_ptr_array_new ();
358 g_assert (cfg->comp_done & MONO_COMP_LIVENESS);
360 type_hash = g_hash_table_new (NULL, NULL);
362 for (i = 0; i < cfg->num_varinfo; i++) {
363 MonoInst *ins = cfg->varinfo [i];
364 MonoMethodVar *vmv = MONO_VARINFO (cfg, i);
367 if (vmv->range.first_use.abs_pos > vmv->range.last_use.abs_pos)
370 if (ins->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT) ||
371 (ins->opcode != OP_LOCAL && ins->opcode != OP_ARG) || vmv->reg != -1)
374 g_assert (ins->inst_vtype);
375 g_assert (vmv->reg == -1);
376 g_assert (i == vmv->idx);
378 if (!(tidx = (int)g_hash_table_lookup (type_hash, ins->inst_vtype))) {
379 GList *vars = g_list_append (NULL, vmv);
380 g_ptr_array_add (varlist_array, vars);
381 g_hash_table_insert (type_hash, ins->inst_vtype, (gpointer)varlist_array->len);
384 g_ptr_array_index (varlist_array, tidx) =
385 mono_varlist_insert_sorted (cfg, g_ptr_array_index (varlist_array, tidx), vmv, FALSE);
389 g_hash_table_destroy (type_hash);
391 return varlist_array;
396 mono_ssa_replace_copies (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, char *is_live)
403 arity = mono_burg_arity [inst->opcode];
405 if ((inst->ssa_op == MONO_SSA_LOAD || inst->ssa_op == MONO_SSA_MAYBE_LOAD || inst->ssa_op == MONO_SSA_STORE) &&
406 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
408 int idx = inst->inst_i0->inst_c0;
409 MonoMethodVar *mv = cfg->vars [idx];
411 if (mv->reg != -1 && mv->reg != mv->idx) {
413 is_live [mv->reg] = 1;
415 new_var = cfg->varinfo [mv->reg];
418 printf ("REPLACE COPY BB%d %d %d\n", bb->block_num, idx, new_var->inst_c0);
419 g_assert (cfg->varinfo [mv->reg]->inst_vtype == cfg->varinfo [idx]->inst_vtype);
421 inst->inst_i0 = new_var;
423 is_live [mv->idx] = 1;
429 mono_ssa_replace_copies (cfg, bb, inst->inst_left, is_live);
431 mono_ssa_replace_copies (cfg, bb, inst->inst_right, is_live);
434 if (inst->ssa_op == MONO_SSA_STORE && inst->inst_i1->ssa_op == MONO_SSA_LOAD &&
435 inst->inst_i0->inst_c0 == inst->inst_i1->inst_i0->inst_c0) {
436 inst->ssa_op = MONO_SSA_NOP;
437 inst->opcode = CEE_NOP;
443 mono_ssa_remove (MonoCompile *cfg)
445 MonoInst *inst, *phi;
448 #ifndef USE_ORIGINAL_VARS
449 GPtrArray *varlist_array;
452 g_assert (cfg->comp_done & MONO_COMP_SSA);
454 for (i = 0; i < cfg->num_bblocks; ++i) {
455 MonoBasicBlock *bb = cfg->bblocks [i];
456 for (inst = bb->code; inst; inst = inst->next) {
457 if (inst->ssa_op == MONO_SSA_STORE && inst->inst_i1->opcode == OP_PHI) {
460 g_assert (phi->inst_phi_args [0] == bb->in_count);
462 for (j = 0; j < bb->in_count; j++) {
463 MonoBasicBlock *pred = bb->in_bb [j];
464 int idx = phi->inst_phi_args [j + 1];
465 MonoMethodVar *mv = cfg->vars [idx];
467 if (mv->reg != -1 && mv->reg != mv->idx) {
468 //printf ("PHICOPY %d %d -> %d\n", idx, mv->reg, inst->inst_i0->inst_c0);
473 if (idx != inst->inst_i0->inst_c0) {
475 printf ("MOVE %d to %d in BB%d\n", idx, inst->inst_i0->inst_c0, pred->block_num);
477 mono_add_varcopy_to_end (cfg, pred, idx, inst->inst_i0->inst_c0);
481 /* remove the phi functions */
482 inst->opcode = CEE_NOP;
483 inst->ssa_op = MONO_SSA_NOP;
488 #ifndef USE_ORIGINAL_VARS
489 /* we compute liveness again */
490 cfg->comp_done &= ~MONO_COMP_LIVENESS;
491 mono_analyze_liveness (cfg);
493 varlist_array = mono_ssa_get_allocatable_vars (cfg);
495 for (i = 0; i < varlist_array->len; i++) {
496 GList *l, *regs, *vars = g_ptr_array_index (varlist_array, i);
497 MonoMethodVar *vmv, *amv;
499 if (g_list_length (vars) <= 1) {
506 for (l = vars; l; l = l->next) {
509 /* expire old intervals in active */
511 amv = (MonoMethodVar *)active->data;
513 if (amv->range.last_use.abs_pos >= vmv->range.first_use.abs_pos)
516 active = g_list_remove_link (active, active);
517 regs = g_list_prepend (regs, (gpointer)amv->reg);
521 regs = g_list_prepend (regs, (gpointer)vmv->idx);
523 vmv->reg = (int)regs->data;
524 regs = g_list_remove_link (regs, regs);
525 active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
528 g_list_free (active);
533 g_ptr_array_free (varlist_array, TRUE);
537 is_live = alloca (cfg->num_varinfo);
538 memset (is_live, 0, cfg->num_varinfo);
540 for (i = 0; i < cfg->num_bblocks; ++i) {
541 MonoBasicBlock *bb = cfg->bblocks [i];
543 for (inst = bb->code; inst; inst = inst->next)
544 mono_ssa_replace_copies (cfg, bb, inst, is_live);
547 for (i = 0; i < cfg->num_varinfo; ++i) {
548 cfg->vars [i]->reg = -1;
550 cfg->varinfo [i]->flags |= MONO_INST_IS_DEAD;
554 if (cfg->comp_done & MONO_COMP_REACHABILITY)
555 unlink_unused_bblocks (cfg);
557 cfg->comp_done &= ~MONO_COMP_SSA;
561 #define IS_CALL(op) (op == CEE_CALLI || op == CEE_CALL || op == CEE_CALLVIRT || (op >= OP_VOIDCALL && op <= OP_CALL_MEMBASE))
569 analyze_dev_use (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *root, MonoInst *inst)
577 arity = mono_burg_arity [inst->opcode];
579 if ((inst->ssa_op == MONO_SSA_STORE) &&
580 (inst->inst_i0->opcode == OP_LOCAL /*|| inst->inst_i0->opcode == OP_ARG */)) {
581 idx = inst->inst_i0->inst_c0;
582 info = cfg->vars [idx];
583 //printf ("%d defined in BB%d %p\n", idx, bb->block_num, root);
585 g_warning ("more than one definition of variable %d in %s", idx,
586 mono_method_full_name (cfg->method, TRUE));
587 g_assert_not_reached ();
589 if (!IS_CALL (inst->inst_i1->opcode) /* && inst->inst_i1->opcode == OP_ICONST */) {
590 g_assert (inst == root);
595 if (inst->inst_i1->opcode == OP_PHI) {
596 for (i = inst->inst_i1->inst_phi_args [0]; i > 0; i--) {
597 MonoVarUsageInfo *ui = mono_mempool_alloc (cfg->mempool, sizeof (MonoVarUsageInfo));
598 idx = inst->inst_i1->inst_phi_args [i];
599 info = cfg->vars [idx];
600 //printf ("FOUND %d\n", idx);
603 info->uses = g_list_prepend (info->uses, ui);
608 if ((inst->ssa_op == MONO_SSA_LOAD || inst->ssa_op == MONO_SSA_MAYBE_LOAD) &&
609 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
610 MonoVarUsageInfo *ui = mono_mempool_alloc (cfg->mempool, sizeof (MonoVarUsageInfo));
611 idx = inst->inst_i0->inst_c0;
612 info = cfg->vars [idx];
613 //printf ("FOUND %d\n", idx);
616 info->uses = g_list_prepend (info->uses, ui);
619 //if (inst->ssa_op != MONO_SSA_STORE)
620 analyze_dev_use (cfg, bb, root, inst->inst_left);
622 analyze_dev_use (cfg, bb, root, inst->inst_right);
628 /* avoid unnecessary copies of variables:
629 * Y <= X; Z = Y; is translated to Z = X;
632 mono_ssa_avoid_copies (MonoCompile *cfg)
634 MonoInst *inst, *next, *u;
636 MonoMethodVar *i1, *i2;
638 g_assert ((cfg->comp_done & MONO_COMP_SSA_DEF_USE));
640 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
641 for (inst = bb->code; inst; inst = inst->next) {
642 if (inst->ssa_op == MONO_SSA_STORE && inst->inst_i0->opcode == OP_LOCAL &&
643 !IS_CALL (inst->inst_i1->opcode) && inst->inst_i1->opcode != OP_PHI && !inst->flags) {
644 i1 = cfg->vars [inst->inst_i0->inst_c0];
646 /* fixme: compiling mcs does not work when I enable this */
648 if (g_list_length (i1->uses) == 1 && !extends_live (inst->inst_i1)) {
649 MonoVarUsageInfo *vi = (MonoVarUsageInfo *)i1->uses->data;
652 //printf ("VAR %d %s\n", i1->idx, mono_method_full_name (cfg->method, TRUE));
653 //mono_print_tree (inst); printf ("\n");
654 //mono_print_tree (u); printf ("\n");
656 if (replace_usage_new (cfg, u, inst->inst_i0->inst_c0, inst->inst_i1)) {
658 //mono_print_tree (u); printf ("\n");
660 inst->opcode = CEE_NOP;
661 inst->ssa_op = MONO_SSA_NOP;
665 if ((next = inst->next) && next->ssa_op == MONO_SSA_STORE && next->inst_i0->opcode == OP_LOCAL &&
666 next->inst_i1->ssa_op == MONO_SSA_LOAD && next->inst_i1->inst_i0->opcode == OP_LOCAL &&
667 next->inst_i1->inst_i0->inst_c0 == inst->inst_i0->inst_c0 && g_list_length (i1->uses) == 1 &&
668 inst->opcode == next->opcode && inst->inst_i0->type == next->inst_i0->type) {
669 i2 = cfg->vars [next->inst_i0->inst_c0];
670 //printf ("ELIM. COPY in BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
671 inst->inst_i0 = next->inst_i0;
674 g_list_free (i1->uses);
676 next->opcode = CEE_NOP;
677 next->ssa_op = MONO_SSA_NOP;
685 mono_ssa_create_def_use (MonoCompile *cfg)
689 g_assert (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE));
691 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
693 for (inst = bb->code; inst; inst = inst->next) {
694 analyze_dev_use (cfg, bb, inst, inst);
698 cfg->comp_done |= MONO_COMP_SSA_DEF_USE;
702 simulate_compare (int opcode, int a, int b)
718 return (unsigned)a >= (unsigned)b;
720 return (unsigned)a > (unsigned)b;
722 return (unsigned)a <= (unsigned)b;
724 return (unsigned)a < (unsigned)b;
726 g_assert_not_reached ();
733 simulate_long_compare (int opcode, gint64 a, gint64 b)
749 return (unsigned)a >= (unsigned)b;
751 return (unsigned)a > (unsigned)b;
753 return (unsigned)a <= (unsigned)b;
755 return (unsigned)a < (unsigned)b;
757 g_assert_not_reached ();
763 #define EVAL_CXX(name,op,cast) \
765 if (inst->inst_i0->opcode == OP_COMPARE) { \
766 r1 = evaluate_const_tree (cfg, inst->inst_i0->inst_i0, &a, carray); \
767 r2 = evaluate_const_tree (cfg, inst->inst_i0->inst_i1, &b, carray); \
768 if (r1 == 1 && r2 == 1) { \
769 *res = ((cast)a op (cast)b); \
772 return MAX (r1, r2); \
777 #define EVAL_BINOP(name,op) \
779 r1 = evaluate_const_tree (cfg, inst->inst_i0, &a, carray); \
780 r2 = evaluate_const_tree (cfg, inst->inst_i1, &b, carray); \
781 if (r1 == 1 && r2 == 1) { \
785 return MAX (r1, r2); \
790 /* fixme: this only works for interger constants, but not for other types (long, float) */
792 evaluate_const_tree (MonoCompile *cfg, MonoInst *inst, int *res, MonoInst **carray)
800 if (inst->ssa_op == MONO_SSA_LOAD &&
801 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
802 (c0 = carray [inst->inst_i0->inst_c0])) {
807 switch (inst->opcode) {
809 *res = inst->inst_c0;
812 EVAL_CXX (OP_CEQ,==,gint32)
813 EVAL_CXX (OP_CGT,>,gint32)
814 EVAL_CXX (OP_CGT_UN,>,guint32)
815 EVAL_CXX (OP_CLT,<,gint32)
816 EVAL_CXX (OP_CLT_UN,<,guint32)
818 EVAL_BINOP (CEE_ADD,+)
819 EVAL_BINOP (CEE_SUB,-)
820 EVAL_BINOP (CEE_MUL,*)
821 EVAL_BINOP (CEE_AND,&)
822 EVAL_BINOP (CEE_OR,|)
823 EVAL_BINOP (CEE_XOR,^)
824 EVAL_BINOP (CEE_SHL,<<)
825 EVAL_BINOP (CEE_SHR,>>)
835 fold_tree (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, MonoInst **carray)
843 arity = mono_burg_arity [inst->opcode];
845 if (inst->ssa_op == MONO_SSA_STORE &&
846 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
847 inst->inst_i1->opcode == OP_PHI && (c0 = carray [inst->inst_i0->inst_c0])) {
848 //{static int cn = 0; printf ("PHICONST %d %d %s\n", cn++, c0->inst_c0, mono_method_full_name (cfg->method, TRUE));}
849 *inst->inst_i1 = *c0;
850 } else if (inst->ssa_op == MONO_SSA_LOAD &&
851 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
852 (c0 = carray [inst->inst_i0->inst_c0])) {
853 //{static int cn = 0; printf ("YCCOPY %d %d %s\n", cn++, c0->inst_c0, mono_method_full_name (cfg->method, TRUE));}
858 fold_tree (cfg, bb, inst->inst_left, carray);
860 fold_tree (cfg, bb, inst->inst_right, carray);
861 mono_constant_fold_inst (inst, NULL);
865 if ((inst->opcode >= CEE_BEQ && inst->opcode <= CEE_BLT_UN) &&
866 inst->inst_i0->opcode == OP_COMPARE) {
867 MonoInst *v0 = inst->inst_i0->inst_i0;
868 MonoInst *v1 = inst->inst_i0->inst_i1;
869 MonoBasicBlock *target = NULL;
871 /* hack for longs to optimize the simply cases */
872 if (v0->opcode == OP_I8CONST && v1->opcode == OP_I8CONST) {
873 if (simulate_long_compare (inst->opcode, v0->inst_l, v1->inst_l)) {
874 //unlink_target (bb, inst->inst_false_bb);
875 target = inst->inst_true_bb;
877 //unlink_target (bb, inst->inst_true_bb);
878 target = inst->inst_false_bb;
880 } else if (evaluate_const_tree (cfg, v0, &a, carray) == 1 &&
881 evaluate_const_tree (cfg, v1, &b, carray) == 1) {
882 if (simulate_compare (inst->opcode, a, b)) {
883 //unlink_target (bb, inst->inst_false_bb);
884 target = inst->inst_true_bb;
886 //unlink_target (bb, inst->inst_true_bb);
887 target = inst->inst_false_bb;
892 bb->out_bb [0] = target;
894 inst->opcode = CEE_BR;
895 inst->inst_target_bb = target;
897 } else if (inst->opcode == CEE_SWITCH && evaluate_const_tree (cfg, inst->inst_left, &a, carray) == 1) {
898 bb->out_bb [0] = inst->inst_many_bb [a];
900 inst->inst_target_bb = bb->out_bb [0];
901 inst->opcode = CEE_BR;
907 change_varstate (MonoCompile *cfg, GList **cvars, MonoMethodVar *info, int state, MonoInst *c0, MonoInst **carray)
909 if (info->cpstate >= state)
912 info->cpstate = state;
914 //printf ("SETSTATE %d to %d\n", info->idx, info->cpstate);
917 carray [info->idx] = c0;
919 carray [info->idx] = NULL;
921 if (!g_list_find (*cvars, info)) {
922 *cvars = g_list_prepend (*cvars, info);
927 visit_inst (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, GList **cvars, GList **bblist, MonoInst **carray)
931 if (inst->opcode == CEE_SWITCH) {
934 r1 = evaluate_const_tree (cfg, inst->inst_left, &a, carray);
936 MonoBasicBlock *tb = inst->inst_many_bb [a];
937 if (!(tb->flags & BB_REACHABLE)) {
938 tb->flags |= BB_REACHABLE;
939 *bblist = g_list_prepend (*bblist, tb);
941 } else if (r1 == 2) {
942 for (i = (int)inst->klass; i >= 0; i--) {
943 MonoBasicBlock *tb = inst->inst_many_bb [i];
944 if (!(tb->flags & BB_REACHABLE)) {
945 tb->flags |= BB_REACHABLE;
946 *bblist = g_list_prepend (*bblist, tb);
950 } else if ((inst->opcode >= CEE_BEQ && inst->opcode <= CEE_BLT_UN) &&
951 inst->inst_i0->opcode == OP_COMPARE) {
953 MonoInst *v0 = inst->inst_i0->inst_i0;
954 MonoInst *v1 = inst->inst_i0->inst_i1;
956 r1 = evaluate_const_tree (cfg, v0, &a, carray);
957 r2 = evaluate_const_tree (cfg, v1, &b, carray);
959 if (r1 == 1 && r2 == 1) {
960 MonoBasicBlock *target;
962 if (simulate_compare (inst->opcode, a, b)) {
963 target = inst->inst_true_bb;
965 target = inst->inst_false_bb;
967 if (!(target->flags & BB_REACHABLE)) {
968 target->flags |= BB_REACHABLE;
969 *bblist = g_list_prepend (*bblist, target);
971 } else if (r1 == 2 || r2 == 2) {
972 if (!(inst->inst_true_bb->flags & BB_REACHABLE)) {
973 inst->inst_true_bb->flags |= BB_REACHABLE;
974 *bblist = g_list_prepend (*bblist, inst->inst_true_bb);
976 if (!(inst->inst_false_bb->flags & BB_REACHABLE)) {
977 inst->inst_false_bb->flags |= BB_REACHABLE;
978 *bblist = g_list_prepend (*bblist, inst->inst_false_bb);
981 } else if (inst->ssa_op == MONO_SSA_STORE &&
982 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
983 MonoMethodVar *info = cfg->vars [inst->inst_i0->inst_c0];
984 MonoInst *i1 = inst->inst_i1;
987 if (info->cpstate < 2) {
988 if (i1->opcode == OP_ICONST) {
989 change_varstate (cfg, cvars, info, 1, i1, carray);
990 } else if (i1->opcode == OP_PHI) {
994 for (j = 1; j <= i1->inst_phi_args [0]; j++) {
995 MonoMethodVar *mv = cfg->vars [i1->inst_phi_args [j]];
996 MonoInst *src = mv->def;
998 if (mv->def_bb && !(mv->def_bb->flags & BB_REACHABLE)) {
1002 if (!mv->def || !src || src->ssa_op != MONO_SSA_STORE ||
1003 !(src->inst_i0->opcode == OP_LOCAL || src->inst_i0->opcode == OP_ARG) ||
1005 change_varstate (cfg, cvars, info, 2, NULL, carray);
1009 if (mv->cpstate == 0)
1012 //g_assert (src->inst_i1->opcode == OP_ICONST);
1013 g_assert (carray [mv->idx]);
1016 c0 = carray [mv->idx];
1019 if (carray [mv->idx]->inst_c0 != c0->inst_c0) {
1020 change_varstate (cfg, cvars, info, 2, NULL, carray);
1025 if (c0 && info->cpstate < 1) {
1026 change_varstate (cfg, cvars, info, 1, c0, carray);
1029 int state = evaluate_const_tree (cfg, i1, &res, carray);
1031 NEW_ICONST (cfg, i1, res);
1032 change_varstate (cfg, cvars, info, 1, i1, carray);
1034 change_varstate (cfg, cvars, info, 2, NULL, carray);
1042 mono_ssa_cprop (MonoCompile *cfg)
1044 MonoInst *carray [cfg->num_varinfo];
1046 GList *bblock_list, *cvars;
1049 //printf ("SIMPLE OPTS BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
1051 if (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE))
1052 mono_ssa_create_def_use (cfg);
1054 bblock_list = g_list_prepend (NULL, cfg->bb_entry);
1055 cfg->bb_entry->flags |= BB_REACHABLE;
1057 memset (carray, 0, sizeof (MonoInst *) * cfg->num_varinfo);
1059 for (i = 0; i < cfg->num_varinfo; i++) {
1060 MonoMethodVar *info = cfg->vars [i];
1067 while (bblock_list) {
1070 bb = (MonoBasicBlock *)bblock_list->data;
1072 bblock_list = g_list_remove_link (bblock_list, bblock_list);
1074 g_assert (bb->flags & BB_REACHABLE);
1076 if (bb->out_count == 1) {
1077 if (!(bb->out_bb [0]->flags & BB_REACHABLE)) {
1078 bb->out_bb [0]->flags |= BB_REACHABLE;
1079 bblock_list = g_list_prepend (bblock_list, bb->out_bb [0]);
1083 for (inst = bb->code; inst; inst = inst->next) {
1084 visit_inst (cfg, bb, inst, &cvars, &bblock_list, carray);
1088 MonoMethodVar *info = (MonoMethodVar *)cvars->data;
1089 cvars = g_list_remove_link (cvars, cvars);
1091 for (tmp = info->uses; tmp; tmp = tmp->next) {
1092 MonoVarUsageInfo *ui = (MonoVarUsageInfo *)tmp->data;
1093 if (!(ui->bb->flags & BB_REACHABLE))
1095 visit_inst (cfg, ui->bb, ui->inst, &cvars, &bblock_list, carray);
1100 for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
1102 for (inst = bb->code; inst; inst = inst->next) {
1103 fold_tree (cfg, bb, inst, carray);
1107 cfg->comp_done |= MONO_COMP_REACHABILITY;
1111 add_to_dce_worklist (MonoCompile *cfg, MonoMethodVar *var, MonoMethodVar *use, GList **wl)
1115 *wl = g_list_prepend (*wl, use);
1117 for (tmp = use->uses; tmp; tmp = tmp->next) {
1118 MonoVarUsageInfo *ui = (MonoVarUsageInfo *)tmp->data;
1119 if (ui->inst == var->def) {
1120 use->uses = g_list_remove_link (use->uses, tmp);
1127 mono_ssa_deadce (MonoCompile *cfg)
1132 g_assert (cfg->comp_done & MONO_COMP_SSA);
1134 //printf ("DEADCE %s\n", mono_method_full_name (cfg->method, TRUE));
1136 /* fixme: we should update usage infos during cprop, instead of computing it again */
1137 cfg->comp_done &= ~MONO_COMP_SSA_DEF_USE;
1138 for (i = 0; i < cfg->num_varinfo; i++) {
1139 MonoMethodVar *info = cfg->vars [i];
1144 if (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE))
1145 mono_ssa_create_def_use (cfg);
1147 mono_ssa_avoid_copies (cfg);
1150 for (i = 0; i < cfg->num_varinfo; i++) {
1151 MonoMethodVar *info = cfg->vars [i];
1152 work_list = g_list_prepend (work_list, info);
1156 MonoMethodVar *info = (MonoMethodVar *)work_list->data;
1157 work_list = g_list_remove_link (work_list, work_list);
1159 if (!info->uses && info->def) {
1161 //printf ("ELIMINATE %s: ", mono_method_full_name (cfg->method, TRUE)); mono_print_tree (info->def); printf ("\n");
1163 i1 = info->def->inst_i1;
1164 if (i1->opcode == OP_PHI) {
1166 for (j = i1->inst_phi_args [0]; j > 0; j--) {
1167 MonoMethodVar *u = cfg->vars [i1->inst_phi_args [j]];
1168 add_to_dce_worklist (cfg, info, u, &work_list);
1170 } else if (i1->ssa_op == MONO_SSA_LOAD &&
1171 (i1->inst_i0->opcode == OP_LOCAL || i1->inst_i0->opcode == OP_ARG)) {
1172 MonoMethodVar *u = cfg->vars [i1->inst_i0->inst_c0];
1173 add_to_dce_worklist (cfg, info, u, &work_list);
1176 info->def->opcode = CEE_NOP;
1177 info->def->ssa_op = MONO_SSA_NOP;
1185 mono_ssa_strength_reduction (MonoCompile *cfg)
1190 g_assert (cfg->comp_done & MONO_COMP_SSA);
1191 g_assert (cfg->comp_done & MONO_COMP_LOOPS);
1192 g_assert (cfg->comp_done & MONO_COMP_SSA_DEF_USE);
1194 for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
1195 GList *lp = bb->loop_blocks;
1198 MonoBasicBlock *h = (MonoBasicBlock *)lp->data;
1200 /* we only consider loops with 2 in bblocks */
1201 if (!h->in_count == 2)
1204 for (i = 0; i < cfg->num_varinfo; i++) {
1205 MonoMethodVar *info = cfg->vars [i];
1207 if (info->def && info->def->ssa_op == MONO_SSA_STORE &&
1208 info->def->inst_i0->opcode == OP_LOCAL && g_list_find (lp, info->def_bb)) {
1209 MonoInst *v = info->def->inst_i1;
1212 printf ("FOUND %d in %s\n", info->idx, mono_method_full_name (cfg->method, TRUE));