3 * Static single assign form support for the JIT compiler.
6 * Dietmar Maurer (dietmar@ximian.com)
8 * (C) 2003 Ximian, Inc.
9 * Copyright 2011 Xamarin, Inc (http://www.xamarin.com)
10 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
14 #include <mono/metadata/debug-helpers.h>
15 #include <mono/metadata/mempool.h>
16 #include <mono/metadata/mempool-internals.h>
17 #include <mono/utils/mono-compiler.h>
26 #define CREATE_PRUNED_SSA
30 #define NEW_PHI(cfg,dest,val) do { \
31 MONO_INST_NEW ((cfg), (dest), OP_PHI); \
32 (dest)->inst_c0 = (val); \
41 unlink_target (MonoBasicBlock *bb, MonoBasicBlock *target)
45 for (i = 0; i < bb->out_count; i++) {
46 if (bb->out_bb [i] == target) {
47 bb->out_bb [i] = bb->out_bb [--bb->out_count];
51 for (i = 0; i < target->in_count; i++) {
52 if (target->in_bb [i] == bb) {
53 target->in_bb [i] = target->in_bb [--target->in_count];
61 unlink_unused_bblocks (MonoCompile *cfg)
66 g_assert (cfg->comp_done & MONO_COMP_REACHABILITY);
68 if (G_UNLIKELY (cfg->verbose_level > 1))
69 printf ("\nUNLINK UNUSED BBLOCKS:\n");
71 for (bb = cfg->bb_entry; bb && bb->next_bb;) {
72 if (!(bb->next_bb->flags & BB_REACHABLE)) {
73 bb->next_bb = bb->next_bb->next_bb;
78 for (i = 1; i < cfg->num_bblocks; i++) {
79 bb = cfg->bblocks [i];
81 if (!(bb->flags & BB_REACHABLE)) {
82 for (j = 0; j < bb->in_count; j++) {
83 unlink_target (bb->in_bb [j], bb);
85 for (j = 0; j < bb->out_count; j++) {
86 unlink_target (bb, bb->out_bb [j]);
88 if (G_UNLIKELY (cfg->verbose_level > 1))
89 printf ("\tUnlinked BB%d\n", bb->block_num);
96 * remove_bb_from_phis:
98 * Remove BB from the PHI statements in TARGET.
101 remove_bb_from_phis (MonoCompile *cfg, MonoBasicBlock *bb, MonoBasicBlock *target)
106 for (i = 0; i < target->in_count; i++) {
107 if (target->in_bb [i] == bb) {
111 g_assert (i < target->in_count);
113 for (ins = target->code; ins; ins = ins->next) {
114 if (MONO_IS_PHI (ins)) {
115 for (j = i; j < ins->inst_phi_args [0] - 1; ++j)
116 ins->inst_phi_args [j + 1] = ins->inst_phi_args [j + 2];
117 ins->inst_phi_args [0] --;
125 op_phi_to_move (int opcode)
137 g_assert_not_reached ();
144 record_use (MonoCompile *cfg, MonoInst *var, MonoBasicBlock *bb, MonoInst *ins)
147 MonoVarUsageInfo *ui = (MonoVarUsageInfo *)mono_mempool_alloc (cfg->mempool, sizeof (MonoVarUsageInfo));
149 info = MONO_VARINFO (cfg, var->inst_c0);
153 info->uses = g_list_prepend_mempool (cfg->mempool, info->uses, ui);
162 * mono_ssa_rename_vars:
163 * Implement renaming of SSA variables. Also compute def-use information in parallel.
164 * \p stack_history points to an area of memory which can be used for storing changes
165 * made to the stack, so they can be reverted later.
168 mono_ssa_rename_vars (MonoCompile *cfg, int max_vars, MonoBasicBlock *bb, gboolean *originals_used, MonoInst **stack, guint32 *lvreg_stack, gboolean *lvreg_defined, RenameInfo *stack_history, int stack_history_size)
170 MonoInst *ins, *new_var;
173 int stack_history_len = 0;
175 if (cfg->verbose_level >= 4)
176 printf ("\nRENAME VARS BLOCK %d:\n", bb->block_num);
178 /* First pass: Create new vars */
179 for (ins = bb->code; ins; ins = ins->next) {
180 const char *spec = INS_INFO (ins->opcode);
182 int sregs [MONO_MAX_SRC_REGS];
185 printf ("\tProcessing "); mono_print_ins (ins);
187 if (ins->opcode == OP_NOP)
191 num_sregs = mono_inst_get_src_registers (ins, sregs);
192 for (i = 0; i < num_sregs; ++i) {
193 if (spec [MONO_INST_SRC1 + i] != ' ') {
194 MonoInst *var = get_vreg_to_inst (cfg, sregs [i]);
195 if (var && !(var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT))) {
196 int idx = var->inst_c0;
198 if (var->opcode != OP_ARG)
199 g_assert (stack [idx]);
200 sregs [i] = stack [idx]->dreg;
201 record_use (cfg, stack [idx], bb, ins);
204 record_use (cfg, var, bb, ins);
206 else if (G_UNLIKELY (!var && lvreg_stack [sregs [i]]))
207 sregs [i] = lvreg_stack [sregs [i]];
210 mono_inst_set_src_registers (ins, sregs);
212 if (MONO_IS_STORE_MEMBASE (ins)) {
213 MonoInst *var = get_vreg_to_inst (cfg, ins->dreg);
214 if (var && !(var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT))) {
215 int idx = var->inst_c0;
217 if (var->opcode != OP_ARG)
218 g_assert (stack [idx]);
219 ins->dreg = stack [idx]->dreg;
220 record_use (cfg, stack [idx], bb, ins);
223 record_use (cfg, var, bb, ins);
225 else if (G_UNLIKELY (!var && lvreg_stack [ins->dreg]))
226 ins->dreg = lvreg_stack [ins->dreg];
230 if ((spec [MONO_INST_DEST] != ' ') && !MONO_IS_STORE_MEMBASE (ins)) {
231 MonoInst *var = get_vreg_to_inst (cfg, ins->dreg);
234 if (var && !(var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT))) {
236 g_assert (idx < max_vars);
238 if (var->opcode == OP_ARG)
239 originals_used [idx] = TRUE;
241 if (stack_history_len + 128 > stack_history_size) {
242 stack_history_size += 1024;
243 RenameInfo *new_history = mono_mempool_alloc (cfg->mempool, sizeof (RenameInfo) * stack_history_size);
244 memcpy (new_history, stack_history, stack_history_len * sizeof (RenameInfo));
245 stack_history = new_history;
248 stack_history [stack_history_len].var = stack [idx];
249 stack_history [stack_history_len].idx = idx;
250 stack_history_len ++;
252 if (originals_used [idx]) {
253 new_var = mono_compile_create_var (cfg, var->inst_vtype, OP_LOCAL);
254 new_var->flags = var->flags;
255 MONO_VARINFO (cfg, new_var->inst_c0)->reg = idx;
257 if (cfg->verbose_level >= 4)
258 printf (" R%d -> R%d\n", var->dreg, new_var->dreg);
260 stack [idx] = new_var;
262 ins->dreg = new_var->dreg;
267 originals_used [idx] = TRUE;
270 info = MONO_VARINFO (cfg, var->inst_c0);
274 else if (G_UNLIKELY (!var && lvreg_defined [ins->dreg] && (ins->dreg >= MONO_MAX_IREGS))) {
275 /* Perform renaming for local vregs */
276 lvreg_stack [ins->dreg] = vreg_is_ref (cfg, ins->dreg) ? mono_alloc_ireg_ref (cfg) : mono_alloc_preg (cfg);
277 ins->dreg = lvreg_stack [ins->dreg];
280 lvreg_defined [ins->dreg] = TRUE;
284 printf ("\tAfter processing "); mono_print_ins (ins);
289 /* Rename PHI arguments in succeeding bblocks */
290 for (i = 0; i < bb->out_count; i++) {
291 MonoBasicBlock *n = bb->out_bb [i];
293 for (j = 0; j < n->in_count; j++)
294 if (n->in_bb [j] == bb)
297 for (ins = n->code; ins; ins = ins->next) {
298 if (MONO_IS_PHI (ins)) {
301 new_var = stack [idx];
303 new_var = cfg->varinfo [idx];
305 printf ("FOUND PHI %d (%d, %d)\n", idx, j, new_var->inst_c0);
307 ins->inst_phi_args [j + 1] = new_var->dreg;
308 record_use (cfg, new_var, n, ins);
309 if (G_UNLIKELY (cfg->verbose_level >= 4))
310 printf ("\tAdd PHI R%d <- R%d to BB%d\n", ins->dreg, new_var->dreg, n->block_num);
313 /* The phi nodes are at the beginning of the bblock */
319 for (tmp = bb->dominated; tmp; tmp = tmp->next) {
320 mono_ssa_rename_vars (cfg, max_vars, (MonoBasicBlock *)tmp->data, originals_used, stack, lvreg_stack, lvreg_defined, stack_history + stack_history_len, stack_history_size - stack_history_len);
325 for (i = stack_history_len - 1; i >= 0; i--) {
326 stack [stack_history [i].idx] = stack_history [i].var;
329 cfg->comp_done |= MONO_COMP_SSA_DEF_USE;
333 mono_ssa_compute (MonoCompile *cfg)
335 int i, j, idx, bitsize;
337 MonoMethodVar *vinfo = g_new0 (MonoMethodVar, cfg->num_varinfo);
338 MonoInst *ins, **stack;
339 guint8 *buf, *buf_start;
340 RenameInfo *stack_history;
341 int stack_history_size;
343 guint32 *lvreg_stack;
344 gboolean *lvreg_defined;
346 g_assert (!(cfg->comp_done & MONO_COMP_SSA));
348 g_assert (!cfg->disable_ssa);
350 if (cfg->verbose_level >= 4)
351 printf ("\nCOMPUTE SSA %d (R%d-)\n\n", cfg->num_varinfo, cfg->next_vreg);
353 #ifdef CREATE_PRUNED_SSA
354 /* we need liveness for pruned SSA */
355 if (!(cfg->comp_done & MONO_COMP_LIVENESS))
356 mono_analyze_liveness (cfg);
359 mono_compile_dominator_info (cfg, MONO_COMP_DOM | MONO_COMP_IDOM | MONO_COMP_DFRONTIER);
361 bitsize = mono_bitset_alloc_size (cfg->num_bblocks, 0);
362 buf = buf_start = (guint8 *)g_malloc0 (mono_bitset_alloc_size (cfg->num_bblocks, 0) * cfg->num_varinfo);
364 for (i = 0; i < cfg->num_varinfo; ++i) {
365 vinfo [i].def_in = mono_bitset_mem_new (buf, cfg->num_bblocks, 0);
368 /* implicit reference at start */
369 if (cfg->varinfo [i]->opcode == OP_ARG)
370 mono_bitset_set_fast (vinfo [i].def_in, 0);
373 for (i = 0; i < cfg->num_bblocks; ++i) {
374 MONO_BB_FOR_EACH_INS (cfg->bblocks [i], ins) {
375 if (ins->opcode == OP_NOP)
378 if (!MONO_IS_STORE_MEMBASE (ins) && get_vreg_to_inst (cfg, ins->dreg)) {
379 mono_bitset_set_fast (vinfo [get_vreg_to_inst (cfg, ins->dreg)->inst_c0].def_in, i);
384 /* insert phi functions */
385 for (i = 0; i < cfg->num_varinfo; ++i) {
386 MonoInst *var = cfg->varinfo [i];
388 #if SIZEOF_REGISTER == 4
389 if (var->type == STACK_I8 && !COMPILE_LLVM (cfg))
392 if (var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT))
395 /* Most variables have only one definition */
396 if (mono_bitset_count (vinfo [i].def_in) <= 1)
399 set = mono_compile_iterated_dfrontier (cfg, vinfo [i].def_in);
401 if (cfg->verbose_level >= 4) {
402 if (mono_bitset_count (set) > 0) {
403 printf ("\tR%d needs PHI functions in ", var->dreg);
404 mono_blockset_print (cfg, set, "", -1);
408 mono_bitset_foreach_bit (set, idx, cfg->num_bblocks) {
409 MonoBasicBlock *bb = cfg->bblocks [idx];
411 /* fixme: create pruned SSA? we would need liveness information for that */
413 if (bb == cfg->bb_exit && !COMPILE_LLVM (cfg))
416 if ((cfg->comp_done & MONO_COMP_LIVENESS) && !mono_bitset_test_fast (bb->live_in_set, i)) {
417 //printf ("%d is not live in BB%d %s\n", i, bb->block_num, mono_method_full_name (cfg->method, TRUE));
421 NEW_PHI (cfg, ins, i);
429 ins->opcode = OP_PHI;
432 ins->opcode = OP_FPHI;
435 ins->opcode = MONO_CLASS_IS_SIMD (cfg, var->klass) ? OP_XPHI : OP_VPHI;
439 if (var->inst_vtype->byref)
440 ins->klass = mono_defaults.int_class;
442 ins->klass = var->klass;
444 ins->inst_phi_args = (int *)mono_mempool_alloc0 (cfg->mempool, sizeof (int) * (cfg->bblocks [idx]->in_count + 1));
445 ins->inst_phi_args [0] = cfg->bblocks [idx]->in_count;
448 for (j = 0; j < cfg->bblocks [idx]->in_count; ++j)
449 ins->inst_phi_args [j + 1] = -1;
451 ins->dreg = cfg->varinfo [i]->dreg;
453 mono_bblock_insert_before_ins (bb, bb->code, ins);
456 printf ("ADD PHI BB%d %s\n", cfg->bblocks [idx]->block_num, mono_method_full_name (cfg->method, TRUE));
467 stack = (MonoInst **)alloca (sizeof (MonoInst *) * cfg->num_varinfo);
468 memset (stack, 0, sizeof (MonoInst *) * cfg->num_varinfo);
470 lvreg_stack = g_new0 (guint32, cfg->next_vreg);
471 lvreg_defined = g_new0 (gboolean, cfg->next_vreg);
472 stack_history_size = 10240;
473 stack_history = g_new (RenameInfo, stack_history_size);
474 originals = g_new0 (gboolean, cfg->num_varinfo);
475 mono_ssa_rename_vars (cfg, cfg->num_varinfo, cfg->bb_entry, originals, stack, lvreg_stack, lvreg_defined, stack_history, stack_history_size);
476 g_free (stack_history);
478 g_free (lvreg_stack);
479 g_free (lvreg_defined);
481 if (cfg->verbose_level >= 4)
482 printf ("\nEND COMPUTE SSA.\n\n");
484 cfg->comp_done |= MONO_COMP_SSA;
488 * mono_ssa_remove_gsharedvt:
490 * Same as mono_ssa_remove, but only remove phi nodes for gsharedvt variables.
493 mono_ssa_remove_gsharedvt (MonoCompile *cfg)
495 MonoInst *ins, *var, *move;
499 * When compiling gsharedvt code, we need to get rid of the VPHI instructions,
500 * since they cannot be handled later in the llvm backend.
502 g_assert (cfg->comp_done & MONO_COMP_SSA);
504 for (i = 0; i < cfg->num_bblocks; ++i) {
505 MonoBasicBlock *bb = cfg->bblocks [i];
507 if (cfg->verbose_level >= 4)
508 printf ("\nREMOVE SSA %d:\n", bb->block_num);
510 for (ins = bb->code; ins; ins = ins->next) {
511 if (!(MONO_IS_PHI (ins) && ins->opcode == OP_VPHI && mini_is_gsharedvt_variable_type (&ins->klass->byval_arg)))
514 g_assert (ins->inst_phi_args [0] == bb->in_count);
515 var = get_vreg_to_inst (cfg, ins->dreg);
517 /* Check for PHI nodes where all the inputs are the same */
518 first = ins->inst_phi_args [1];
520 for (j = 1; j < bb->in_count; ++j)
521 if (first != ins->inst_phi_args [j + 1])
524 if ((bb->in_count > 1) && (j == bb->in_count)) {
525 ins->opcode = op_phi_to_move (ins->opcode);
526 if (ins->opcode == OP_VMOVE)
527 g_assert (ins->klass);
530 for (j = 0; j < bb->in_count; j++) {
531 MonoBasicBlock *pred = bb->in_bb [j];
532 int sreg = ins->inst_phi_args [j + 1];
534 if (cfg->verbose_level >= 4)
535 printf ("\tADD R%d <- R%d in BB%d\n", var->dreg, sreg, pred->block_num);
536 if (var->dreg != sreg) {
537 MONO_INST_NEW (cfg, move, op_phi_to_move (ins->opcode));
538 if (move->opcode == OP_VMOVE) {
539 g_assert (ins->klass);
540 move->klass = ins->klass;
542 move->dreg = var->dreg;
544 mono_add_ins_to_end (pred, move);
555 mono_ssa_remove (MonoCompile *cfg)
557 MonoInst *ins, *var, *move;
558 int bbindex, i, j, first;
560 g_assert (cfg->comp_done & MONO_COMP_SSA);
562 for (i = 0; i < cfg->num_bblocks; ++i) {
563 MonoBasicBlock *bb = cfg->bblocks [i];
565 if (cfg->verbose_level >= 4)
566 printf ("\nREMOVE SSA %d:\n", bb->block_num);
568 for (ins = bb->code; ins; ins = ins->next) {
569 if (MONO_IS_PHI (ins)) {
570 g_assert (ins->inst_phi_args [0] == bb->in_count);
571 var = get_vreg_to_inst (cfg, ins->dreg);
573 /* Check for PHI nodes where all the inputs are the same */
574 first = ins->inst_phi_args [1];
576 for (j = 1; j < bb->in_count; ++j)
577 if (first != ins->inst_phi_args [j + 1])
580 if ((bb->in_count > 1) && (j == bb->in_count)) {
581 ins->opcode = op_phi_to_move (ins->opcode);
582 if (ins->opcode == OP_VMOVE)
583 g_assert (ins->klass);
586 for (j = 0; j < bb->in_count; j++) {
587 MonoBasicBlock *pred = bb->in_bb [j];
588 int sreg = ins->inst_phi_args [j + 1];
590 if (cfg->verbose_level >= 4)
591 printf ("\tADD R%d <- R%d in BB%d\n", var->dreg, sreg, pred->block_num);
592 if (var->dreg != sreg) {
593 MONO_INST_NEW (cfg, move, op_phi_to_move (ins->opcode));
594 if (move->opcode == OP_VMOVE) {
595 g_assert (ins->klass);
596 move->klass = ins->klass;
598 move->dreg = var->dreg;
600 mono_add_ins_to_end (pred, move);
610 if (cfg->verbose_level >= 4) {
611 for (i = 0; i < cfg->num_bblocks; ++i) {
612 MonoBasicBlock *bb = cfg->bblocks [i];
614 mono_print_bb (bb, "AFTER REMOVE SSA:");
619 * Removal of SSA form introduces many copies. To avoid this, we tyry to coalesce
620 * the variables if possible. Since the newly introduced SSA variables don't
621 * have overlapping live ranges (because we don't do agressive optimization), we
622 * can coalesce them into the original variable.
625 for (bbindex = 0; bbindex < cfg->num_bblocks; ++bbindex) {
626 MonoBasicBlock *bb = cfg->bblocks [bbindex];
628 for (ins = bb->code; ins; ins = ins->next) {
629 const char *spec = INS_INFO (ins->opcode);
631 int sregs [MONO_MAX_SRC_REGS];
633 if (ins->opcode == OP_NOP)
636 if (spec [MONO_INST_DEST] != ' ') {
637 MonoInst *var = get_vreg_to_inst (cfg, ins->dreg);
640 MonoMethodVar *vmv = MONO_VARINFO (cfg, var->inst_c0);
643 * The third condition avoids coalescing with variables eliminated
646 if ((vmv->reg != -1) && (vmv->idx != vmv->reg) && (MONO_VARINFO (cfg, vmv->reg)->reg != -1)) {
647 printf ("COALESCE: R%d -> R%d\n", ins->dreg, cfg->varinfo [vmv->reg]->dreg);
648 ins->dreg = cfg->varinfo [vmv->reg]->dreg;
653 num_sregs = mono_inst_get_src_registers (ins, sregs);
654 for (i = 0; i < num_sregs; ++i) {
655 MonoInst *var = get_vreg_to_inst (cfg, sregs [i]);
658 MonoMethodVar *vmv = MONO_VARINFO (cfg, var->inst_c0);
660 if ((vmv->reg != -1) && (vmv->idx != vmv->reg) && (MONO_VARINFO (cfg, vmv->reg)->reg != -1)) {
661 printf ("COALESCE: R%d -> R%d\n", sregs [i], cfg->varinfo [vmv->reg]->dreg);
662 sregs [i] = cfg->varinfo [vmv->reg]->dreg;
666 mono_inst_set_src_registers (ins, sregs);
670 for (i = 0; i < cfg->num_varinfo; ++i) {
671 MONO_VARINFO (cfg, i)->reg = -1;
674 if (cfg->comp_done & MONO_COMP_REACHABILITY)
675 unlink_unused_bblocks (cfg);
677 cfg->comp_done &= ~MONO_COMP_LIVENESS;
679 cfg->comp_done &= ~MONO_COMP_SSA;
683 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) {
692 for (ins = bb->code; ins; ins = ins->next) {
693 const char *spec = INS_INFO (ins->opcode);
696 int sregs [MONO_MAX_SRC_REGS];
698 if (ins->opcode == OP_NOP)
702 num_sregs = mono_inst_get_src_registers (ins, sregs);
703 for (i = 0; i < num_sregs; ++i) {
704 MonoInst *var = get_vreg_to_inst (cfg, sregs [i]);
705 if (var && !(var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT)))
706 record_use (cfg, var, bb, ins);
709 if (MONO_IS_STORE_MEMBASE (ins)) {
710 MonoInst *var = get_vreg_to_inst (cfg, ins->dreg);
711 if (var && !(var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT)))
712 record_use (cfg, var, bb, ins);
715 if (MONO_IS_PHI (ins)) {
716 for (i = ins->inst_phi_args [0]; i > 0; i--) {
717 g_assert (ins->inst_phi_args [i] != -1);
718 record_use (cfg, get_vreg_to_inst (cfg, ins->inst_phi_args [i]), bb, ins);
723 if ((spec [MONO_INST_DEST] != ' ') && !MONO_IS_STORE_MEMBASE (ins)) {
724 MonoInst *var = get_vreg_to_inst (cfg, ins->dreg);
726 if (var && !(var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT))) {
727 info = MONO_VARINFO (cfg, var->inst_c0);
735 cfg->comp_done |= MONO_COMP_SSA_DEF_USE;
739 mono_ssa_copyprop (MonoCompile *cfg)
744 g_assert ((cfg->comp_done & MONO_COMP_SSA_DEF_USE));
746 for (index = 0; index < cfg->num_varinfo; ++index) {
747 MonoInst *var = cfg->varinfo [index];
748 MonoMethodVar *info = MONO_VARINFO (cfg, index);
750 if (info->def && (MONO_IS_MOVE (info->def))) {
751 MonoInst *var2 = get_vreg_to_inst (cfg, info->def->sreg1);
753 if (var2 && !(var2->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT)) && MONO_VARINFO (cfg, var2->inst_c0)->def && (!MONO_IS_PHI (MONO_VARINFO (cfg, var2->inst_c0)->def))) {
754 /* Rewrite all uses of var to be uses of var2 */
755 int dreg = var->dreg;
756 int sreg1 = var2->dreg;
760 MonoVarUsageInfo *u = (MonoVarUsageInfo*)l->data;
761 MonoInst *ins = u->inst;
762 GList *next = l->next;
764 int sregs [MONO_MAX_SRC_REGS];
766 num_sregs = mono_inst_get_src_registers (ins, sregs);
767 for (i = 0; i < num_sregs; ++i) {
768 if (sregs [i] == dreg)
772 g_assert (sregs [i] == dreg);
774 mono_inst_set_src_registers (ins, sregs);
775 } else if (MONO_IS_STORE_MEMBASE (ins) && ins->dreg == dreg) {
777 } else if (MONO_IS_PHI (ins)) {
778 for (i = ins->inst_phi_args [0]; i > 0; i--) {
779 int sreg = ins->inst_phi_args [i];
780 if (sreg == var->dreg)
784 ins->inst_phi_args [i] = sreg1;
787 g_assert_not_reached ();
789 record_use (cfg, var2, u->bb, ins);
799 if (cfg->verbose_level >= 4) {
802 for (bb = cfg->bb_entry; bb; bb = bb->next_bb)
803 mono_print_bb (bb, "AFTER SSA COPYPROP");
808 evaluate_ins (MonoCompile *cfg, MonoInst *ins, MonoInst **res, MonoInst **carray)
810 MonoInst *args [MONO_MAX_SRC_REGS];
811 int rs [MONO_MAX_SRC_REGS];
813 gboolean const_args = TRUE;
814 const char *spec = INS_INFO (ins->opcode);
816 int sregs [MONO_MAX_SRC_REGS];
818 /* Short-circuit this */
819 if (ins->opcode == OP_ICONST) {
824 if (ins->opcode == OP_NOP)
827 num_sregs = mono_inst_get_src_registers (ins, sregs);
828 for (i = 0; i < MONO_MAX_SRC_REGS; ++i)
830 for (i = 0; i < num_sregs; ++i) {
831 MonoInst *var = get_vreg_to_inst (cfg, sregs [i]);
834 args [i] = carray [sregs [i]];
837 else if (var && !(var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT)))
838 rs [i] = MONO_VARINFO (cfg, var->inst_c0)->cpstate;
845 if (num_sregs > 0 && const_args) {
846 g_assert (num_sregs <= 2);
847 if ((spec [MONO_INST_DEST] != ' ') && carray [ins->dreg]) {
849 *res = carray [ins->dreg];
852 c0 = mono_constant_fold_ins (cfg, ins, args [0], args [1], FALSE);
854 if (G_UNLIKELY (cfg->verbose_level > 1)) {
855 printf ("\t cfold -> ");
862 /* Can't cfold this ins */
868 for (i = 0; i < num_sregs; ++i) {
876 change_varstate (MonoCompile *cfg, GList **cvars, MonoMethodVar *info, int state, MonoInst *c0, MonoInst **carray)
878 if (info->cpstate >= state)
881 info->cpstate = state;
883 if (G_UNLIKELY (cfg->verbose_level > 1))
884 printf ("\tState of R%d set to %d\n", cfg->varinfo [info->idx]->dreg, info->cpstate);
889 carray [cfg->varinfo [info->idx]->dreg] = c0;
891 if (!g_list_find (*cvars, info)) {
892 *cvars = g_list_prepend (*cvars, info);
897 add_cprop_bb (MonoCompile *cfg, MonoBasicBlock *bb, GList **bblist)
899 if (G_UNLIKELY (cfg->verbose_level > 1))
900 printf ("\tAdd BB%d to worklist\n", bb->block_num);
902 if (!(bb->flags & BB_REACHABLE)) {
903 bb->flags |= BB_REACHABLE;
904 *bblist = g_list_prepend (*bblist, bb);
909 visit_inst (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *ins, GList **cvars, GList **bblist, MonoInst **carray)
911 const char *spec = INS_INFO (ins->opcode);
913 if (ins->opcode == OP_NOP)
916 if (cfg->verbose_level > 1)
917 mono_print_ins (ins);
919 /* FIXME: Support longs/floats */
920 /* FIXME: Work on vregs as well */
922 if (MONO_IS_PHI (ins)) {
923 MonoMethodVar *info = MONO_VARINFO (cfg, get_vreg_to_inst (cfg, ins->dreg)->inst_c0);
927 for (j = 1; j <= ins->inst_phi_args [0]; j++) {
928 MonoInst *var = get_vreg_to_inst (cfg, ins->inst_phi_args [j]);
929 MonoMethodVar *mv = MONO_VARINFO (cfg, var->inst_c0);
930 MonoInst *src = mv->def;
932 if (mv->def_bb && !(mv->def_bb->flags & BB_REACHABLE))
935 if (!mv->def || !src || mv->cpstate == 2) {
936 change_varstate (cfg, cvars, info, 2, NULL, carray);
940 if (mv->cpstate == 0)
943 g_assert (carray [var->dreg]);
946 c0 = carray [var->dreg];
949 if (c0->opcode != OP_ICONST) {
950 change_varstate (cfg, cvars, info, 2, NULL, carray);
954 if (carray [var->dreg]->inst_c0 != c0->inst_c0) {
955 change_varstate (cfg, cvars, info, 2, NULL, carray);
960 if (c0 && info->cpstate < 1) {
961 change_varstate (cfg, cvars, info, 1, c0, carray);
963 g_assert (c0->opcode == OP_ICONST);
966 else if (!MONO_IS_STORE_MEMBASE (ins) && ((spec [MONO_INST_SRC1] != ' ') || (spec [MONO_INST_SRC2] != ' ') || (spec [MONO_INST_DEST] != ' '))) {
970 if (spec [MONO_INST_DEST] != ' ')
971 var = get_vreg_to_inst (cfg, ins->dreg);
976 state = evaluate_ins (cfg, ins, &c0, carray);
978 if (var && !(var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT))) {
979 MonoMethodVar *info = MONO_VARINFO (cfg, var->inst_c0);
981 if (info->cpstate < 2) {
983 change_varstate (cfg, cvars, info, 1, c0, carray);
985 change_varstate (cfg, cvars, info, 2, NULL, carray);
988 else if (!var && (ins->dreg != -1)) {
990 * We don't record def-use information for local vregs since it would be
991 * expensive. Instead, we depend on the fact that all uses of the vreg are in
992 * the same bblock, so they will be examined after the definition.
993 * FIXME: This isn't true if the ins is visited through an SSA edge.
996 carray [ins->dreg] = c0;
998 if (carray [ins->dreg]) {
1000 * The state of the vreg changed from constant to non-constant
1001 * -> need to rescan the whole bblock.
1003 carray [ins->dreg] = NULL;
1004 /* FIXME: Speed this up */
1006 if (!g_list_find (*bblist, bb))
1007 *bblist = g_list_prepend (*bblist, bb);
1012 if (MONO_IS_JUMP_TABLE (ins)) {
1014 MonoJumpInfoBBTable *table = (MonoJumpInfoBBTable *)MONO_JUMP_TABLE_FROM_INS (ins);
1016 if (!ins->next || ins->next->opcode != OP_PADD) {
1017 /* The PADD was optimized away */
1018 /* FIXME: handle this as well */
1019 for (i = 0; i < table->table_size; i++)
1020 if (table->table [i])
1021 add_cprop_bb (cfg, table->table [i], bblist);
1025 g_assert (ins->next->opcode == OP_PADD);
1026 g_assert (ins->next->sreg1 == ins->dreg);
1028 if (carray [ins->next->sreg2]) {
1029 #if SIZEOF_REGISTER == 8
1030 int idx = carray [ins->next->sreg2]->inst_c0 >> 3;
1032 int idx = carray [ins->next->sreg2]->inst_c0 >> 2;
1034 if ((idx < 0) || (idx >= table->table_size))
1035 /* Out-of-range, no branch is executed */
1038 if (table->table [idx])
1039 add_cprop_bb (cfg, table->table [idx], bblist);
1042 for (i = 0; i < table->table_size; i++)
1043 if (table->table [i])
1044 add_cprop_bb (cfg, table->table [i], bblist);
1048 if (ins->opcode == OP_SWITCH) {
1050 MonoJumpInfoBBTable *table = (MonoJumpInfoBBTable *)ins->inst_p0;
1052 for (i = 0; i < table->table_size; i++)
1053 if (table->table [i])
1054 add_cprop_bb (cfg, table->table [i], bblist);
1057 /* Handle COMPARE+BRCOND pairs */
1058 if (ins->next && MONO_IS_COND_BRANCH_OP (ins->next)) {
1060 g_assert (c0->opcode == OP_ICONST);
1063 ins->next->flags |= MONO_INST_CFOLD_TAKEN;
1065 ins->next->flags |= MONO_INST_CFOLD_NOT_TAKEN;
1068 ins->next->flags &= ~(MONO_INST_CFOLD_TAKEN | MONO_INST_CFOLD_NOT_TAKEN);
1071 visit_inst (cfg, bb, ins->next, cvars, bblist, carray);
1073 } else if (ins->opcode == OP_BR) {
1074 add_cprop_bb (cfg, ins->inst_target_bb, bblist);
1075 } else if (MONO_IS_COND_BRANCH_OP (ins)) {
1076 if (ins->flags & MONO_INST_CFOLD_TAKEN) {
1077 add_cprop_bb (cfg, ins->inst_true_bb, bblist);
1078 } else if (ins->flags & MONO_INST_CFOLD_NOT_TAKEN) {
1079 if (ins->inst_false_bb)
1080 add_cprop_bb (cfg, ins->inst_false_bb, bblist);
1082 add_cprop_bb (cfg, ins->inst_true_bb, bblist);
1083 if (ins->inst_false_bb)
1084 add_cprop_bb (cfg, ins->inst_false_bb, bblist);
1092 * Replace INS with its constant value, if it exists
1095 fold_ins (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *ins, MonoInst **carray)
1097 const char *spec = INS_INFO (ins->opcode);
1099 int num_sregs = mono_inst_get_num_src_registers (ins);
1101 if ((ins->opcode != OP_NOP) && (ins->dreg != -1) && !MONO_IS_STORE_MEMBASE (ins)) {
1102 if (carray [ins->dreg] && (spec [MONO_INST_DEST] == 'i') && (ins->dreg >= MONO_MAX_IREGS)) {
1103 /* Perform constant folding */
1105 g_assert (carray [ins->dreg]->opcode == OP_ICONST);
1106 ins->opcode = OP_ICONST;
1107 ins->inst_c0 = carray [ins->dreg]->inst_c0;
1108 MONO_INST_NULLIFY_SREGS (ins);
1109 } else if (num_sregs == 2 && carray [ins->sreg2]) {
1110 /* Perform op->op_imm conversion */
1111 opcode2 = mono_op_to_op_imm (ins->opcode);
1112 if (opcode2 != -1) {
1113 ins->opcode = opcode2;
1114 ins->inst_imm = carray [ins->sreg2]->inst_c0;
1117 if ((opcode2 == OP_VOIDCALL) || (opcode2 == OP_CALL) || (opcode2 == OP_LCALL) || (opcode2 == OP_FCALL))
1118 ((MonoCallInst*)ins)->fptr = (gpointer)ins->inst_imm;
1121 /* FIXME: Handle 3 op insns */
1124 if (MONO_IS_JUMP_TABLE (ins)) {
1126 MonoJumpInfoBBTable *table = (MonoJumpInfoBBTable *)MONO_JUMP_TABLE_FROM_INS (ins);
1128 if (!ins->next || ins->next->opcode != OP_PADD) {
1129 /* The PADD was optimized away */
1130 /* FIXME: handle this as well */
1134 g_assert (ins->next->opcode == OP_PADD);
1135 g_assert (ins->next->sreg1 == ins->dreg);
1136 g_assert (ins->next->next->opcode == OP_LOAD_MEMBASE);
1138 if (carray [ins->next->sreg2]) {
1139 /* Convert to a simple branch */
1140 #if SIZEOF_REGISTER == 8
1141 int idx = carray [ins->next->sreg2]->inst_c0 >> 3;
1143 int idx = carray [ins->next->sreg2]->inst_c0 >> 2;
1146 if (!((idx >= 0) && (idx < table->table_size))) {
1147 /* Out of range, eliminate the whole switch */
1148 for (i = 0; i < table->table_size; ++i) {
1149 remove_bb_from_phis (cfg, bb, table->table [i]);
1150 mono_unlink_bblock (cfg, bb, table->table [i]);
1154 NULLIFY_INS (ins->next);
1155 NULLIFY_INS (ins->next->next);
1156 if (ins->next->next->next)
1157 NULLIFY_INS (ins->next->next->next);
1162 if (!ins->next->next->next || ins->next->next->next->opcode != OP_BR_REG) {
1163 /* A one-way switch which got optimized away */
1164 if (G_UNLIKELY (cfg->verbose_level > 1)) {
1165 printf ("\tNo cfold on ");
1166 mono_print_ins (ins);
1171 if (G_UNLIKELY (cfg->verbose_level > 1)) {
1172 printf ("\tcfold on ");
1173 mono_print_ins (ins);
1176 /* Unlink target bblocks */
1177 for (i = 0; i < table->table_size; ++i) {
1178 if (table->table [i] != table->table [idx]) {
1179 remove_bb_from_phis (cfg, bb, table->table [i]);
1180 mono_unlink_bblock (cfg, bb, table->table [i]);
1184 /* Change the OP_BR_REG to a simple branch */
1185 ins->next->next->next->opcode = OP_BR;
1186 ins->next->next->next->inst_target_bb = table->table [idx];
1187 ins->next->next->next->sreg1 = -1;
1189 /* Nullify the other instructions */
1191 NULLIFY_INS (ins->next);
1192 NULLIFY_INS (ins->next->next);
1196 else if (MONO_IS_COND_BRANCH_OP (ins)) {
1197 if (ins->flags & MONO_INST_CFOLD_TAKEN) {
1198 remove_bb_from_phis (cfg, bb, ins->inst_false_bb);
1199 mono_unlink_bblock (cfg, bb, ins->inst_false_bb);
1200 ins->opcode = OP_BR;
1201 ins->inst_target_bb = ins->inst_true_bb;
1202 } else if (ins->flags & MONO_INST_CFOLD_NOT_TAKEN) {
1203 remove_bb_from_phis (cfg, bb, ins->inst_true_bb);
1204 mono_unlink_bblock (cfg, bb, ins->inst_true_bb);
1205 ins->opcode = OP_BR;
1206 ins->inst_target_bb = ins->inst_false_bb;
1212 mono_ssa_cprop (MonoCompile *cfg)
1216 GList *bblock_list, *cvars;
1219 //printf ("SIMPLE OPTS BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
1221 carray = g_new0 (MonoInst*, cfg->next_vreg);
1223 if (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE))
1224 mono_ssa_create_def_use (cfg);
1226 bblock_list = g_list_prepend (NULL, cfg->bb_entry);
1227 cfg->bb_entry->flags |= BB_REACHABLE;
1229 memset (carray, 0, sizeof (MonoInst *) * cfg->num_varinfo);
1231 for (i = 0; i < cfg->num_varinfo; i++) {
1232 MonoMethodVar *info = MONO_VARINFO (cfg, i);
1237 for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
1239 * FIXME: This should be bb->flags & BB_FLAG_EXCEPTION_HANDLER, but
1240 * that would still allow unreachable try's to be removed.
1243 add_cprop_bb (cfg, bb, &bblock_list);
1248 while (bblock_list) {
1251 bb = (MonoBasicBlock *)bblock_list->data;
1253 bblock_list = g_list_delete_link (bblock_list, bblock_list);
1255 g_assert (bb->flags & BB_REACHABLE);
1258 * Some bblocks are linked to 2 others even through they fall through to the
1261 if (!(bb->last_ins && MONO_IS_BRANCH_OP (bb->last_ins))) {
1262 for (i = 0; i < bb->out_count; ++i)
1263 add_cprop_bb (cfg, bb->out_bb [i], &bblock_list);
1266 if (cfg->verbose_level > 1)
1267 printf ("\nSSA CONSPROP BB%d:\n", bb->block_num);
1269 for (inst = bb->code; inst; inst = inst->next) {
1270 visit_inst (cfg, bb, inst, &cvars, &bblock_list, carray);
1274 MonoMethodVar *info = (MonoMethodVar *)cvars->data;
1275 cvars = g_list_delete_link (cvars, cvars);
1277 for (tmp = info->uses; tmp; tmp = tmp->next) {
1278 MonoVarUsageInfo *ui = (MonoVarUsageInfo *)tmp->data;
1279 if (!(ui->bb->flags & BB_REACHABLE))
1281 visit_inst (cfg, ui->bb, ui->inst, &cvars, &bblock_list, carray);
1286 for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
1288 for (inst = bb->code; inst; inst = inst->next) {
1289 fold_ins (cfg, bb, inst, carray);
1295 cfg->comp_done |= MONO_COMP_REACHABILITY;
1297 /* fixme: we should update usage infos during cprop, instead of computing it again */
1298 cfg->comp_done &= ~MONO_COMP_SSA_DEF_USE;
1299 for (i = 0; i < cfg->num_varinfo; i++) {
1300 MonoMethodVar *info = MONO_VARINFO (cfg, i);
1307 add_to_dce_worklist (MonoCompile *cfg, MonoMethodVar *var, MonoMethodVar *use, GList **wl)
1311 *wl = g_list_prepend_mempool (cfg->mempool, *wl, use);
1313 for (tmp = use->uses; tmp; tmp = tmp->next) {
1314 MonoVarUsageInfo *ui = (MonoVarUsageInfo *)tmp->data;
1315 if (ui->inst == var->def) {
1316 /* from the mempool */
1317 use->uses = g_list_remove_link (use->uses, tmp);
1324 mono_ssa_deadce (MonoCompile *cfg)
1329 g_assert (cfg->comp_done & MONO_COMP_SSA);
1331 //printf ("DEADCE %s\n", mono_method_full_name (cfg->method, TRUE));
1333 if (!(cfg->comp_done & MONO_COMP_SSA_DEF_USE))
1334 mono_ssa_create_def_use (cfg);
1336 mono_ssa_copyprop (cfg);
1339 for (i = 0; i < cfg->num_varinfo; i++) {
1340 MonoMethodVar *info = MONO_VARINFO (cfg, i);
1341 work_list = g_list_prepend_mempool (cfg->mempool, work_list, info);
1345 MonoMethodVar *info = (MonoMethodVar *)work_list->data;
1346 work_list = g_list_remove_link (work_list, work_list);
1349 * The second part of the condition happens often when PHI nodes have their dreg
1350 * as one of their arguments due to the fact that we use the original vars.
1352 if (info->def && (!info->uses || ((info->uses->next == NULL) && (((MonoVarUsageInfo*)info->uses->data)->inst == info->def)))) {
1353 MonoInst *def = info->def;
1355 /* Eliminating FMOVE could screw up the fp stack */
1356 if (MONO_IS_MOVE (def) && (!MONO_ARCH_USE_FPSTACK || (def->opcode != OP_FMOVE))) {
1357 MonoInst *src_var = get_vreg_to_inst (cfg, def->sreg1);
1358 if (src_var && !(src_var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT)))
1359 add_to_dce_worklist (cfg, info, MONO_VARINFO (cfg, src_var->inst_c0), &work_list);
1362 } else if ((def->opcode == OP_ICONST) || (def->opcode == OP_I8CONST) || MONO_IS_ZERO (def)) {
1365 } else if (MONO_IS_PHI (def)) {
1367 for (j = def->inst_phi_args [0]; j > 0; j--) {
1368 MonoMethodVar *u = MONO_VARINFO (cfg, get_vreg_to_inst (cfg, def->inst_phi_args [j])->inst_c0);
1369 add_to_dce_worklist (cfg, info, u, &work_list);
1374 else if (def->opcode == OP_NOP) {
1377 //mono_print_ins (def);
1385 mono_ssa_strength_reduction (MonoCompile *cfg)
1390 g_assert (cfg->comp_done & MONO_COMP_SSA);
1391 g_assert (cfg->comp_done & MONO_COMP_LOOPS);
1392 g_assert (cfg->comp_done & MONO_COMP_SSA_DEF_USE);
1394 for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
1395 GList *lp = bb->loop_blocks;
1398 MonoBasicBlock *h = (MonoBasicBlock *)lp->data;
1400 /* we only consider loops with 2 in bblocks */
1401 if (!h->in_count == 2)
1404 for (i = 0; i < cfg->num_varinfo; i++) {
1405 MonoMethodVar *info = MONO_VARINFO (cfg, i);
1407 if (info->def && info->def->ssa_op == MONO_SSA_STORE &&
1408 info->def->inst_i0->opcode == OP_LOCAL && g_list_find (lp, info->def_bb)) {
1409 MonoInst *v = info->def->inst_i1;
1412 printf ("FOUND %d in %s\n", info->idx, mono_method_full_name (cfg->method, TRUE));
1421 mono_ssa_loop_invariant_code_motion (MonoCompile *cfg)
1423 MonoBasicBlock *bb, *h, *idom;
1424 MonoInst *ins, *n, *tins;
1427 g_assert (cfg->comp_done & MONO_COMP_SSA);
1428 if (!(cfg->comp_done & MONO_COMP_LOOPS) || !(cfg->comp_done & MONO_COMP_SSA_DEF_USE))
1431 for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
1432 GList *lp = bb->loop_blocks;
1436 h = (MonoBasicBlock *)lp->data;
1439 MONO_BB_FOR_EACH_INS_SAFE (bb, n, ins) {
1441 * Try to move instructions out of loop headers into the preceeding bblock.
1443 if (ins->opcode == OP_LDLEN || ins->opcode == OP_STRLEN || ins->opcode == OP_CHECK_THIS || ins->opcode == OP_AOTCONST || ins->opcode == OP_GENERIC_CLASS_INIT) {
1449 * h->nesting is needed to work around:
1450 * http://llvm.org/bugs/show_bug.cgi?id=17868
1452 if (!(idom && idom->last_ins && idom->last_ins->opcode == OP_BR && idom->last_ins->inst_target_bb == h && h->nesting == 1)) {
1457 * Make sure there are no instructions with side effects before ins.
1460 MONO_BB_FOR_EACH_INS (bb, tins) {
1463 if (!MONO_INS_HAS_NO_SIDE_EFFECT (tins)) {
1470 printf ("%s\n", mono_method_full_name (cfg->method, TRUE));
1471 mono_print_ins (tins);
1476 /* Make sure we don't move the instruction before the def of its sreg */
1477 if (ins->opcode == OP_LDLEN || ins->opcode == OP_STRLEN || ins->opcode == OP_CHECK_THIS)
1482 MonoInst *tins, *var;
1485 for (tins = ins->prev; tins; tins = tins->prev) {
1486 const char *spec = INS_INFO (tins->opcode);
1488 if (tins->opcode == OP_MOVE && tins->dreg == sreg) {
1490 } if (spec [MONO_INST_DEST] != ' ' && tins->dreg == sreg) {
1497 var = get_vreg_to_inst (cfg, sreg);
1498 if (var && (var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT)))
1503 if (cfg->verbose_level > 1) {
1504 printf ("licm in BB%d on ", bb->block_num);
1505 mono_print_ins (ins);
1507 //{ static int count = 0; count ++; printf ("%d\n", count); }
1508 MONO_REMOVE_INS (bb, ins);
1509 mono_bblock_insert_before_ins (idom, idom->last_ins, ins);
1510 if (ins->opcode == OP_LDLEN || ins->opcode == OP_STRLEN)
1511 idom->has_array_access = TRUE;
1516 cfg->comp_done &= ~MONO_COMP_SSA_DEF_USE;
1517 for (i = 0; i < cfg->num_varinfo; i++) {
1518 MonoMethodVar *info = MONO_VARINFO (cfg, i);
1524 #else /* !DISABLE_JIT */
1526 MONO_EMPTY_SOURCE_FILE (ssa);
1528 #endif /* !DISABLE_JIT */