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 g_list_prepend_mempool (GList* l, MonoMemPool* mp, gpointer datum)
38 GList* n = mono_mempool_alloc (mp, sizeof (GList));
46 unlink_target (MonoBasicBlock *bb, MonoBasicBlock *target)
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];
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];
66 unlink_unused_bblocks (MonoCompile *cfg)
71 g_assert (cfg->comp_done & MONO_COMP_REACHABILITY);
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;
80 for (i = 1; i < cfg->num_bblocks; i++) {
81 bb = cfg->bblocks [i];
83 if (!(bb->flags & BB_REACHABLE)) {
84 for (j = 0; j < bb->in_count; j++) {
85 unlink_target (bb->in_bb [j], bb);
87 for (j = 0; j < bb->out_count; j++) {
88 unlink_target (bb, bb->out_bb [j]);
98 replace_usage (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, MonoInst **stack)
105 arity = mono_burg_arity [inst->opcode];
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)) {
110 int idx = inst->inst_i0->inst_c0;
113 new_var = stack [idx];
115 new_var = cfg->varinfo [idx];
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 ();
125 printf ("REPLACE BB%d %d %d\n", bb->block_num, idx, new_var->inst_c0);
127 inst->inst_i0 = new_var;
131 if (inst->ssa_op != MONO_SSA_STORE)
132 replace_usage (cfg, bb, inst->inst_left, stack);
134 replace_usage (cfg, bb, inst->inst_right, stack);
140 extends_live (MonoInst *inst)
147 arity = mono_burg_arity [inst->opcode];
149 if (inst->ssa_op == MONO_SSA_LOAD &&
150 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
154 if (inst->ssa_op != MONO_SSA_STORE)
155 if (extends_live (inst->inst_left))
158 if (extends_live (inst->inst_right))
167 replace_usage_new (MonoCompile *cfg, MonoInst *inst, int varnum, MonoInst *rep)
174 arity = mono_burg_arity [inst->opcode];
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) {
183 if (inst->ssa_op != MONO_SSA_STORE)
184 if (replace_usage_new (cfg, inst->inst_left, varnum, rep))
187 if (replace_usage_new (cfg, inst->inst_right, varnum, rep))
196 mono_ssa_rename_vars (MonoCompile *cfg, int max_vars, MonoBasicBlock *bb, MonoInst **stack)
198 MonoInst *inst, *new_var;
201 MonoInst **new_stack;
204 printf ("RENAME VARS BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
207 for (inst = bb->code; inst; inst = inst->next) {
208 if (inst->opcode != OP_PHI)
209 replace_usage (cfg, bb, inst, stack);
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);
216 if ((!stack [idx]) && (bb == cfg->bb_init) && (inst->inst_i0->opcode != OP_ARG)) {
217 new_var = cfg->varinfo [idx];
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;
223 printf ("DEF %d %d\n", idx, new_var->inst_c0);
225 inst->inst_i0 = new_var;
227 #ifdef USE_ORIGINAL_VARS
228 cfg->vars [new_var->inst_c0]->reg = idx;
231 stack [idx] = new_var;
235 for (i = 0; i < bb->out_count; i++) {
236 MonoBasicBlock *n = bb->out_bb [i];
238 for (j = 0; j < n->in_count; j++)
239 if (n->in_bb [j] == bb)
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;
246 new_var = stack [idx];
248 new_var = cfg->varinfo [idx];
250 printf ("FOUND PHI %d (%d, %d)\n", idx, j, new_var->inst_c0);
252 inst->inst_i1->inst_phi_args [j + 1] = new_var->inst_c0;
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);
269 mono_ssa_compute (MonoCompile *cfg)
273 MonoMethodVar *vinfo = g_new0 (MonoMethodVar, cfg->num_varinfo);
274 MonoInst *inst, *store, **stack;
276 g_assert (!(cfg->comp_done & MONO_COMP_SSA));
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);
282 //printf ("COMPUTS SSA %s %d\n", mono_method_full_name (cfg->method, TRUE), cfg->num_varinfo);
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);
290 mono_compile_dominator_info (cfg, MONO_COMP_DOM | MONO_COMP_IDOM | MONO_COMP_DFRONTIER);
292 for (i = 0; i < cfg->num_varinfo; ++i) {
293 vinfo [i].def_in = mono_bitset_new (cfg->num_bblocks, 0);
295 /* implizit reference at start */
296 mono_bitset_set (vinfo [i].def_in, 0);
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);
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];
315 /* fixme: create pruned SSA? we would need liveness information for that */
317 if (bb == cfg->bb_exit)
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));
325 NEW_PHI (cfg, inst, i);
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;
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;
339 store->next = bb->code;
342 bb->last_ins = bb->code;
345 printf ("ADD PHI BB%d %s\n", cfg->bblocks [idx]->block_num, mono_method_full_name (cfg->method, TRUE));
351 for (i = 0; i < cfg->num_varinfo; ++i)
352 mono_bitset_free (vinfo [i].def_in);
356 stack = alloca (sizeof (MonoInst *) * cfg->num_varinfo);
358 for (i = 0; i < cfg->num_varinfo; i++)
361 mono_ssa_rename_vars (cfg, cfg->num_varinfo, cfg->bb_entry, stack);
363 cfg->comp_done |= MONO_COMP_SSA;
366 #ifndef USE_ORIGINAL_VARS
368 mono_ssa_get_allocatable_vars (MonoCompile *cfg)
370 GHashTable *type_hash;
371 GPtrArray *varlist_array = g_ptr_array_new ();
374 g_assert (cfg->comp_done & MONO_COMP_LIVENESS);
376 type_hash = g_hash_table_new (NULL, NULL);
378 for (i = 0; i < cfg->num_varinfo; i++) {
379 MonoInst *ins = cfg->varinfo [i];
380 MonoMethodVar *vmv = MONO_VARINFO (cfg, i);
383 if (vmv->range.first_use.abs_pos > vmv->range.last_use.abs_pos)
386 if (ins->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT) ||
387 (ins->opcode != OP_LOCAL && ins->opcode != OP_ARG) || vmv->reg != -1)
390 g_assert (ins->inst_vtype);
391 g_assert (vmv->reg == -1);
392 g_assert (i == vmv->idx);
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);
400 g_ptr_array_index (varlist_array, tidx) =
401 mono_varlist_insert_sorted (cfg, g_ptr_array_index (varlist_array, tidx), vmv, FALSE);
405 g_hash_table_destroy (type_hash);
407 return varlist_array;
412 mono_ssa_replace_copies (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, char *is_live)
419 arity = mono_burg_arity [inst->opcode];
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)) {
424 int idx = inst->inst_i0->inst_c0;
425 MonoMethodVar *mv = cfg->vars [idx];
427 if (mv->reg != -1 && mv->reg != mv->idx) {
429 is_live [mv->reg] = 1;
431 new_var = cfg->varinfo [mv->reg];
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);
437 inst->inst_i0 = new_var;
439 is_live [mv->idx] = 1;
445 mono_ssa_replace_copies (cfg, bb, inst->inst_left, is_live);
447 mono_ssa_replace_copies (cfg, bb, inst->inst_right, is_live);
450 if (inst->ssa_op == MONO_SSA_STORE && inst->inst_i1->ssa_op == MONO_SSA_LOAD &&
451 inst->inst_i0->inst_c0 == inst->inst_i1->inst_i0->inst_c0) {
452 inst->ssa_op = MONO_SSA_NOP;
453 inst->opcode = CEE_NOP;
459 mono_ssa_remove (MonoCompile *cfg)
461 MonoInst *inst, *phi;
464 #ifndef USE_ORIGINAL_VARS
465 GPtrArray *varlist_array;
468 g_assert (cfg->comp_done & MONO_COMP_SSA);
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) {
476 g_assert (phi->inst_phi_args [0] == bb->in_count);
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];
483 if (mv->reg != -1 && mv->reg != mv->idx) {
484 //printf ("PHICOPY %d %d -> %d\n", idx, mv->reg, inst->inst_i0->inst_c0);
489 if (idx != inst->inst_i0->inst_c0) {
491 printf ("MOVE %d to %d in BB%d\n", idx, inst->inst_i0->inst_c0, pred->block_num);
493 mono_add_varcopy_to_end (cfg, pred, idx, inst->inst_i0->inst_c0);
497 /* remove the phi functions */
498 inst->opcode = CEE_NOP;
499 inst->ssa_op = MONO_SSA_NOP;
504 #ifndef USE_ORIGINAL_VARS
505 /* we compute liveness again */
506 cfg->comp_done &= ~MONO_COMP_LIVENESS;
507 mono_analyze_liveness (cfg);
509 varlist_array = mono_ssa_get_allocatable_vars (cfg);
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;
515 if (g_list_length (vars) <= 1) {
522 for (l = vars; l; l = l->next) {
525 /* expire old intervals in active */
527 amv = (MonoMethodVar *)active->data;
529 if (amv->range.last_use.abs_pos >= vmv->range.first_use.abs_pos)
532 active = g_list_delete_link (active, active);
533 regs = g_list_prepend (regs, (gpointer)amv->reg);
537 regs = g_list_prepend (regs, (gpointer)vmv->idx);
539 vmv->reg = (int)regs->data;
540 regs = g_list_delete_link (regs, regs);
541 active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
544 g_list_free (active);
549 g_ptr_array_free (varlist_array, TRUE);
553 is_live = alloca (cfg->num_varinfo);
554 memset (is_live, 0, cfg->num_varinfo);
556 for (i = 0; i < cfg->num_bblocks; ++i) {
557 MonoBasicBlock *bb = cfg->bblocks [i];
559 for (inst = bb->code; inst; inst = inst->next)
560 mono_ssa_replace_copies (cfg, bb, inst, is_live);
563 for (i = 0; i < cfg->num_varinfo; ++i) {
564 cfg->vars [i]->reg = -1;
566 cfg->varinfo [i]->flags |= MONO_INST_IS_DEAD;
570 if (cfg->comp_done & MONO_COMP_REACHABILITY)
571 unlink_unused_bblocks (cfg);
573 cfg->comp_done &= ~MONO_COMP_SSA;
577 #define IS_CALL(op) (op == CEE_CALLI || op == CEE_CALL || op == CEE_CALLVIRT || (op >= OP_VOIDCALL && op <= OP_CALL_MEMBASE))
585 analyze_dev_use (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *root, MonoInst *inst)
593 arity = mono_burg_arity [inst->opcode];
595 if ((inst->ssa_op == MONO_SSA_STORE) &&
596 (inst->inst_i0->opcode == OP_LOCAL /*|| inst->inst_i0->opcode == OP_ARG */)) {
597 idx = inst->inst_i0->inst_c0;
598 info = cfg->vars [idx];
599 //printf ("%d defined in BB%d %p\n", idx, bb->block_num, root);
601 g_warning ("more than one definition of variable %d in %s", idx,
602 mono_method_full_name (cfg->method, TRUE));
603 g_assert_not_reached ();
605 if (!IS_CALL (inst->inst_i1->opcode) /* && inst->inst_i1->opcode == OP_ICONST */) {
606 g_assert (inst == root);
611 if (inst->inst_i1->opcode == OP_PHI) {
612 for (i = inst->inst_i1->inst_phi_args [0]; i > 0; i--) {
613 MonoVarUsageInfo *ui = mono_mempool_alloc (cfg->mempool, sizeof (MonoVarUsageInfo));
614 idx = inst->inst_i1->inst_phi_args [i];
615 info = cfg->vars [idx];
616 //printf ("FOUND %d\n", idx);
619 info->uses = g_list_prepend_mempool (info->uses, cfg->mempool, ui);
624 if ((inst->ssa_op == MONO_SSA_LOAD || inst->ssa_op == MONO_SSA_ADDRESS_TAKEN) &&
625 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
626 MonoVarUsageInfo *ui = mono_mempool_alloc (cfg->mempool, sizeof (MonoVarUsageInfo));
627 idx = inst->inst_i0->inst_c0;
628 info = cfg->vars [idx];
629 //printf ("FOUND %d\n", idx);
632 info->uses = g_list_prepend_mempool (info->uses, cfg->mempool, ui);
635 //if (inst->ssa_op != MONO_SSA_STORE)
636 analyze_dev_use (cfg, bb, root, inst->inst_left);
638 analyze_dev_use (cfg, bb, root, inst->inst_right);
644 /* avoid unnecessary copies of variables:
645 * Y <= X; Z = Y; is translated to Z = X;
648 mono_ssa_avoid_copies (MonoCompile *cfg)
650 MonoInst *inst, *next;
652 MonoMethodVar *i1, *i2;
654 g_assert ((cfg->comp_done & MONO_COMP_SSA_DEF_USE));
656 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
657 for (inst = bb->code; inst; inst = inst->next) {
658 if (inst->ssa_op == MONO_SSA_STORE && inst->inst_i0->opcode == OP_LOCAL &&
659 !IS_CALL (inst->inst_i1->opcode) && inst->inst_i1->opcode != OP_PHI && !inst->flags) {
660 i1 = cfg->vars [inst->inst_i0->inst_c0];
662 /* fixme: compiling mcs does not work when I enable this */
664 if (g_list_length (i1->uses) == 1 && !extends_live (inst->inst_i1)) {
665 MonoVarUsageInfo *vi = (MonoVarUsageInfo *)i1->uses->data;
668 //printf ("VAR %d %s\n", i1->idx, mono_method_full_name (cfg->method, TRUE));
669 //mono_print_tree (inst); printf ("\n");
670 //mono_print_tree (u); printf ("\n");
672 if (replace_usage_new (cfg, u, inst->inst_i0->inst_c0, inst->inst_i1)) {
674 //mono_print_tree (u); printf ("\n");
676 inst->opcode = CEE_NOP;
677 inst->ssa_op = MONO_SSA_NOP;
681 if ((next = inst->next) && next->ssa_op == MONO_SSA_STORE && next->inst_i0->opcode == OP_LOCAL &&
682 next->inst_i1->ssa_op == MONO_SSA_LOAD && next->inst_i1->inst_i0->opcode == OP_LOCAL &&
683 next->inst_i1->inst_i0->inst_c0 == inst->inst_i0->inst_c0 && g_list_length (i1->uses) == 1 &&
684 inst->opcode == next->opcode && inst->inst_i0->type == next->inst_i0->type) {
685 i2 = cfg->vars [next->inst_i0->inst_c0];
686 //printf ("ELIM. COPY in BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
687 inst->inst_i0 = next->inst_i0;
691 next->opcode = CEE_NOP;
692 next->ssa_op = MONO_SSA_NOP;
700 mono_ssa_create_def_use (MonoCompile *cfg)
704 g_assert (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE));
706 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
708 for (inst = bb->code; inst; inst = inst->next) {
709 analyze_dev_use (cfg, bb, inst, inst);
713 cfg->comp_done |= MONO_COMP_SSA_DEF_USE;
717 simulate_compare (int opcode, int a, int b)
733 return (unsigned)a >= (unsigned)b;
735 return (unsigned)a > (unsigned)b;
737 return (unsigned)a <= (unsigned)b;
739 return (unsigned)a < (unsigned)b;
741 g_assert_not_reached ();
748 simulate_long_compare (int opcode, gint64 a, gint64 b)
764 return (guint64)a >= (guint64)b;
766 return (guint64)a > (guint64)b;
768 return (guint64)a <= (guint64)b;
770 return (guint64)a < (guint64)b;
772 g_assert_not_reached ();
778 #define EVAL_CXX(name,op,cast) \
780 if ((inst->inst_i0->opcode == OP_COMPARE) || (inst->inst_i0->opcode == OP_LCOMPARE)) { \
781 r1 = evaluate_const_tree (cfg, inst->inst_i0->inst_i0, &a, carray); \
782 r2 = evaluate_const_tree (cfg, inst->inst_i0->inst_i1, &b, carray); \
783 if (r1 == 1 && r2 == 1) { \
784 *res = ((cast)a op (cast)b); \
787 return MAX (r1, r2); \
792 #define EVAL_BINOP(name,op) \
794 r1 = evaluate_const_tree (cfg, inst->inst_i0, &a, carray); \
795 r2 = evaluate_const_tree (cfg, inst->inst_i1, &b, carray); \
796 if (r1 == 1 && r2 == 1) { \
800 return MAX (r1, r2); \
805 /* fixme: this only works for interger constants, but not for other types (long, float) */
807 evaluate_const_tree (MonoCompile *cfg, MonoInst *inst, int *res, MonoInst **carray)
815 if (inst->ssa_op == MONO_SSA_LOAD &&
816 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
817 (c0 = carray [inst->inst_i0->inst_c0])) {
822 switch (inst->opcode) {
824 *res = inst->inst_c0;
827 EVAL_CXX (OP_CEQ,==,gint32)
828 EVAL_CXX (OP_CGT,>,gint32)
829 EVAL_CXX (OP_CGT_UN,>,guint32)
830 EVAL_CXX (OP_CLT,<,gint32)
831 EVAL_CXX (OP_CLT_UN,<,guint32)
833 EVAL_BINOP (CEE_ADD,+)
834 EVAL_BINOP (CEE_SUB,-)
835 EVAL_BINOP (CEE_MUL,*)
836 EVAL_BINOP (CEE_AND,&)
837 EVAL_BINOP (CEE_OR,|)
838 EVAL_BINOP (CEE_XOR,^)
839 EVAL_BINOP (CEE_SHL,<<)
840 EVAL_BINOP (CEE_SHR,>>)
850 fold_tree (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, MonoInst **carray)
858 arity = mono_burg_arity [inst->opcode];
860 if (inst->ssa_op == MONO_SSA_STORE &&
861 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
862 inst->inst_i1->opcode == OP_PHI && (c0 = carray [inst->inst_i0->inst_c0])) {
863 //{static int cn = 0; printf ("PHICONST %d %d %s\n", cn++, c0->inst_c0, mono_method_full_name (cfg->method, TRUE));}
864 *inst->inst_i1 = *c0;
865 } else if (inst->ssa_op == MONO_SSA_LOAD &&
866 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG) &&
867 (c0 = carray [inst->inst_i0->inst_c0])) {
868 //{static int cn = 0; printf ("YCCOPY %d %d %s\n", cn++, c0->inst_c0, mono_method_full_name (cfg->method, TRUE));}
873 fold_tree (cfg, bb, inst->inst_left, carray);
875 fold_tree (cfg, bb, inst->inst_right, carray);
876 mono_constant_fold_inst (inst, NULL);
880 if ((inst->opcode >= CEE_BEQ && inst->opcode <= CEE_BLT_UN) &&
881 ((inst->inst_i0->opcode == OP_COMPARE) || (inst->inst_i0->opcode == OP_LCOMPARE))) {
882 MonoInst *v0 = inst->inst_i0->inst_i0;
883 MonoInst *v1 = inst->inst_i0->inst_i1;
884 MonoBasicBlock *target = NULL;
886 /* hack for longs to optimize the simply cases */
887 if (v0->opcode == OP_I8CONST && v1->opcode == OP_I8CONST) {
888 if (simulate_long_compare (inst->opcode, v0->inst_l, v1->inst_l)) {
889 //unlink_target (bb, inst->inst_false_bb);
890 target = inst->inst_true_bb;
892 //unlink_target (bb, inst->inst_true_bb);
893 target = inst->inst_false_bb;
895 } else if (evaluate_const_tree (cfg, v0, &a, carray) == 1 &&
896 evaluate_const_tree (cfg, v1, &b, carray) == 1) {
897 if (simulate_compare (inst->opcode, a, b)) {
898 //unlink_target (bb, inst->inst_false_bb);
899 target = inst->inst_true_bb;
901 //unlink_target (bb, inst->inst_true_bb);
902 target = inst->inst_false_bb;
907 bb->out_bb [0] = target;
909 inst->opcode = CEE_BR;
910 inst->inst_target_bb = target;
912 } else if (inst->opcode == CEE_SWITCH && (evaluate_const_tree (cfg, inst->inst_left, &a, carray) == 1) && (a >= 0) && (a < GPOINTER_TO_INT (inst->klass))) {
913 bb->out_bb [0] = inst->inst_many_bb [a];
915 inst->inst_target_bb = bb->out_bb [0];
916 inst->opcode = CEE_BR;
922 change_varstate (MonoCompile *cfg, GList **cvars, MonoMethodVar *info, int state, MonoInst *c0, MonoInst **carray)
924 if (info->cpstate >= state)
927 info->cpstate = state;
929 //printf ("SETSTATE %d to %d\n", info->idx, info->cpstate);
932 carray [info->idx] = c0;
934 carray [info->idx] = NULL;
936 if (!g_list_find (*cvars, info)) {
937 *cvars = g_list_prepend (*cvars, info);
942 visit_inst (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *inst, GList **cvars, GList **bblist, MonoInst **carray)
946 if (inst->opcode == CEE_SWITCH) {
948 int cases = GPOINTER_TO_INT (inst->klass);
950 r1 = evaluate_const_tree (cfg, inst->inst_left, &a, carray);
951 if ((r1 == 1) && ((a < 0) || (a >= cases)))
954 MonoBasicBlock *tb = inst->inst_many_bb [a];
955 if (!(tb->flags & BB_REACHABLE)) {
956 tb->flags |= BB_REACHABLE;
957 *bblist = g_list_prepend (*bblist, tb);
959 } else if (r1 == 2) {
960 for (i = GPOINTER_TO_INT (inst->klass); i >= 0; i--) {
961 MonoBasicBlock *tb = inst->inst_many_bb [i];
962 if (!(tb->flags & BB_REACHABLE)) {
963 tb->flags |= BB_REACHABLE;
964 *bblist = g_list_prepend (*bblist, tb);
968 } else if ((inst->opcode >= CEE_BEQ && inst->opcode <= CEE_BLT_UN) &&
969 ((inst->inst_i0->opcode == OP_COMPARE) || (inst->inst_i0->opcode == OP_LCOMPARE))) {
971 MonoInst *v0 = inst->inst_i0->inst_i0;
972 MonoInst *v1 = inst->inst_i0->inst_i1;
974 r1 = evaluate_const_tree (cfg, v0, &a, carray);
975 r2 = evaluate_const_tree (cfg, v1, &b, carray);
977 if (r1 == 1 && r2 == 1) {
978 MonoBasicBlock *target;
980 if (simulate_compare (inst->opcode, a, b)) {
981 target = inst->inst_true_bb;
983 target = inst->inst_false_bb;
985 if (!(target->flags & BB_REACHABLE)) {
986 target->flags |= BB_REACHABLE;
987 *bblist = g_list_prepend (*bblist, target);
989 } else if (r1 == 2 || r2 == 2) {
990 if (!(inst->inst_true_bb->flags & BB_REACHABLE)) {
991 inst->inst_true_bb->flags |= BB_REACHABLE;
992 *bblist = g_list_prepend (*bblist, inst->inst_true_bb);
994 if (!(inst->inst_false_bb->flags & BB_REACHABLE)) {
995 inst->inst_false_bb->flags |= BB_REACHABLE;
996 *bblist = g_list_prepend (*bblist, inst->inst_false_bb);
999 } else if (inst->ssa_op == MONO_SSA_STORE &&
1000 (inst->inst_i0->opcode == OP_LOCAL || inst->inst_i0->opcode == OP_ARG)) {
1001 MonoMethodVar *info = cfg->vars [inst->inst_i0->inst_c0];
1002 MonoInst *i1 = inst->inst_i1;
1005 if (info->cpstate < 2) {
1006 if (i1->opcode == OP_ICONST) {
1007 change_varstate (cfg, cvars, info, 1, i1, carray);
1008 } else if (i1->opcode == OP_PHI) {
1009 MonoInst *c0 = NULL;
1012 for (j = 1; j <= i1->inst_phi_args [0]; j++) {
1013 MonoMethodVar *mv = cfg->vars [i1->inst_phi_args [j]];
1014 MonoInst *src = mv->def;
1016 if (mv->def_bb && !(mv->def_bb->flags & BB_REACHABLE)) {
1020 if (!mv->def || !src || src->ssa_op != MONO_SSA_STORE ||
1021 !(src->inst_i0->opcode == OP_LOCAL || src->inst_i0->opcode == OP_ARG) ||
1023 change_varstate (cfg, cvars, info, 2, NULL, carray);
1027 if (mv->cpstate == 0)
1030 //g_assert (src->inst_i1->opcode == OP_ICONST);
1031 g_assert (carray [mv->idx]);
1034 c0 = carray [mv->idx];
1037 if (carray [mv->idx]->inst_c0 != c0->inst_c0) {
1038 change_varstate (cfg, cvars, info, 2, NULL, carray);
1043 if (c0 && info->cpstate < 1) {
1044 change_varstate (cfg, cvars, info, 1, c0, carray);
1047 int state = evaluate_const_tree (cfg, i1, &res, carray);
1049 NEW_ICONST (cfg, i1, res);
1050 change_varstate (cfg, cvars, info, 1, i1, carray);
1052 change_varstate (cfg, cvars, info, 2, NULL, carray);
1060 mono_ssa_cprop (MonoCompile *cfg)
1064 GList *bblock_list, *cvars;
1067 //printf ("SIMPLE OPTS BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
1069 carray = g_new0 (MonoInst*, cfg->num_varinfo);
1071 if (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE))
1072 mono_ssa_create_def_use (cfg);
1074 bblock_list = g_list_prepend (NULL, cfg->bb_entry);
1075 cfg->bb_entry->flags |= BB_REACHABLE;
1077 memset (carray, 0, sizeof (MonoInst *) * cfg->num_varinfo);
1079 for (i = 0; i < cfg->num_varinfo; i++) {
1080 MonoMethodVar *info = cfg->vars [i];
1087 while (bblock_list) {
1090 bb = (MonoBasicBlock *)bblock_list->data;
1092 bblock_list = g_list_delete_link (bblock_list, bblock_list);
1094 g_assert (bb->flags & BB_REACHABLE);
1096 if (bb->out_count == 1) {
1097 if (!(bb->out_bb [0]->flags & BB_REACHABLE)) {
1098 bb->out_bb [0]->flags |= BB_REACHABLE;
1099 bblock_list = g_list_prepend (bblock_list, bb->out_bb [0]);
1103 for (inst = bb->code; inst; inst = inst->next) {
1104 visit_inst (cfg, bb, inst, &cvars, &bblock_list, carray);
1108 MonoMethodVar *info = (MonoMethodVar *)cvars->data;
1109 cvars = g_list_delete_link (cvars, cvars);
1111 for (tmp = info->uses; tmp; tmp = tmp->next) {
1112 MonoVarUsageInfo *ui = (MonoVarUsageInfo *)tmp->data;
1113 if (!(ui->bb->flags & BB_REACHABLE))
1115 visit_inst (cfg, ui->bb, ui->inst, &cvars, &bblock_list, carray);
1120 for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
1122 for (inst = bb->code; inst; inst = inst->next) {
1123 fold_tree (cfg, bb, inst, carray);
1129 cfg->comp_done |= MONO_COMP_REACHABILITY;
1133 add_to_dce_worklist (MonoCompile *cfg, MonoMethodVar *var, MonoMethodVar *use, GList **wl)
1137 *wl = g_list_prepend (*wl, use);
1139 for (tmp = use->uses; tmp; tmp = tmp->next) {
1140 MonoVarUsageInfo *ui = (MonoVarUsageInfo *)tmp->data;
1141 if (ui->inst == var->def) {
1142 /* from the mempool */
1143 use->uses = g_list_remove_link (use->uses, tmp);
1150 mono_ssa_deadce (MonoCompile *cfg)
1155 g_assert (cfg->comp_done & MONO_COMP_SSA);
1157 //printf ("DEADCE %s\n", mono_method_full_name (cfg->method, TRUE));
1159 /* fixme: we should update usage infos during cprop, instead of computing it again */
1160 cfg->comp_done &= ~MONO_COMP_SSA_DEF_USE;
1161 for (i = 0; i < cfg->num_varinfo; i++) {
1162 MonoMethodVar *info = cfg->vars [i];
1167 if (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE))
1168 mono_ssa_create_def_use (cfg);
1170 mono_ssa_avoid_copies (cfg);
1173 for (i = 0; i < cfg->num_varinfo; i++) {
1174 MonoMethodVar *info = cfg->vars [i];
1175 work_list = g_list_prepend (work_list, info);
1177 //if ((info->def != NULL) && (info->def->inst_i1->opcode != OP_PHI)) printf ("SSA DEADCE TOTAL LOCAL\n");
1181 MonoMethodVar *info = (MonoMethodVar *)work_list->data;
1182 work_list = g_list_delete_link (work_list, work_list);
1184 if (!info->uses && info->def && (!(cfg->varinfo [info->idx]->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT)))) {
1186 //printf ("ELIMINATE %s: ", mono_method_full_name (cfg->method, TRUE)); mono_print_tree (info->def); printf ("\n");
1188 i1 = info->def->inst_i1;
1189 if (i1->opcode == OP_PHI) {
1191 for (j = i1->inst_phi_args [0]; j > 0; j--) {
1192 MonoMethodVar *u = cfg->vars [i1->inst_phi_args [j]];
1193 add_to_dce_worklist (cfg, info, u, &work_list);
1195 } else if (i1->ssa_op == MONO_SSA_LOAD &&
1196 (i1->inst_i0->opcode == OP_LOCAL || i1->inst_i0->opcode == OP_ARG)) {
1197 MonoMethodVar *u = cfg->vars [i1->inst_i0->inst_c0];
1198 add_to_dce_worklist (cfg, info, u, &work_list);
1200 //if (i1->opcode != OP_PHI) printf ("SSA DEADCE DEAD LOCAL\n");
1202 info->def->opcode = CEE_NOP;
1203 info->def->ssa_op = MONO_SSA_NOP;
1211 mono_ssa_strength_reduction (MonoCompile *cfg)
1216 g_assert (cfg->comp_done & MONO_COMP_SSA);
1217 g_assert (cfg->comp_done & MONO_COMP_LOOPS);
1218 g_assert (cfg->comp_done & MONO_COMP_SSA_DEF_USE);
1220 for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
1221 GList *lp = bb->loop_blocks;
1224 MonoBasicBlock *h = (MonoBasicBlock *)lp->data;
1226 /* we only consider loops with 2 in bblocks */
1227 if (!h->in_count == 2)
1230 for (i = 0; i < cfg->num_varinfo; i++) {
1231 MonoMethodVar *info = cfg->vars [i];
1233 if (info->def && info->def->ssa_op == MONO_SSA_STORE &&
1234 info->def->inst_i0->opcode == OP_LOCAL && g_list_find (lp, info->def_bb)) {
1235 MonoInst *v = info->def->inst_i1;
1238 printf ("FOUND %d in %s\n", info->idx, mono_method_full_name (cfg->method, TRUE));