2 * ssa.c: Static single assign form support for the JIT compiler.
5 * Dietmar Maurer (dietmar@ximian.com)
7 * (C) 2003 Ximian, Inc.
11 #include <mono/metadata/debug-helpers.h>
12 #include <mono/metadata/mempool.h>
13 #include <mono/metadata/mempool-internals.h>
22 #define USE_ORIGINAL_VARS
23 #define CREATE_PRUNED_SSA
27 #define NEW_PHI(cfg,dest,val) do { \
28 (dest) = mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoInst)); \
29 (dest)->opcode = OP_PHI; \
30 (dest)->inst_c0 = (val); \
31 (dest)->dreg = (dest)->sreg1 = (dest)->sreg2 = -1; \
40 unlink_target (MonoBasicBlock
*bb
, MonoBasicBlock
*target
)
44 for (i
= 0; i
< bb
->out_count
; i
++) {
45 if (bb
->out_bb
[i
] == target
) {
46 bb
->out_bb
[i
] = bb
->out_bb
[--bb
->out_count
];
50 for (i
= 0; i
< target
->in_count
; i
++) {
51 if (target
->in_bb
[i
] == bb
) {
52 target
->in_bb
[i
] = target
->in_bb
[--target
->in_count
];
60 unlink_unused_bblocks (MonoCompile
*cfg
)
65 g_assert (cfg
->comp_done
& MONO_COMP_REACHABILITY
);
67 if (G_UNLIKELY (cfg
->verbose_level
> 1))
68 printf ("\nUNLINK UNUSED BBLOCKS:\n");
70 for (bb
= cfg
->bb_entry
; bb
&& bb
->next_bb
;) {
71 if (!(bb
->next_bb
->flags
& BB_REACHABLE
)) {
72 bb
->next_bb
= bb
->next_bb
->next_bb
;
77 for (i
= 1; i
< cfg
->num_bblocks
; i
++) {
78 bb
= cfg
->bblocks
[i
];
80 if (!(bb
->flags
& BB_REACHABLE
)) {
81 for (j
= 0; j
< bb
->in_count
; j
++) {
82 unlink_target (bb
->in_bb
[j
], bb
);
84 for (j
= 0; j
< bb
->out_count
; j
++) {
85 unlink_target (bb
, bb
->out_bb
[j
]);
87 if (G_UNLIKELY (cfg
->verbose_level
> 1))
88 printf ("\tUnlinked BB%d\n", bb
->block_num
);
95 * remove_bb_from_phis:
97 * Remove BB from the PHI statements in TARGET.
100 remove_bb_from_phis (MonoCompile
*cfg
, MonoBasicBlock
*bb
, MonoBasicBlock
*target
)
105 for (i
= 0; i
< target
->in_count
; i
++) {
106 if (target
->in_bb
[i
] == bb
) {
110 g_assert (i
< target
->in_count
);
112 for (ins
= target
->code
; ins
; ins
= ins
->next
) {
113 if (MONO_IS_PHI (ins
)) {
114 for (j
= i
; j
< ins
->inst_phi_args
[0] - 1; ++j
)
115 ins
->inst_phi_args
[j
+ 1] = ins
->inst_phi_args
[j
+ 2];
116 ins
->inst_phi_args
[0] --;
124 op_phi_to_move (int opcode
)
136 g_assert_not_reached ();
143 record_use (MonoCompile
*cfg
, MonoInst
*var
, MonoBasicBlock
*bb
, MonoInst
*ins
)
146 MonoVarUsageInfo
*ui
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoVarUsageInfo
));
148 info
= MONO_VARINFO (cfg
, var
->inst_c0
);
152 info
->uses
= g_list_prepend_mempool (cfg
->mempool
, info
->uses
, ui
);
161 * mono_ssa_rename_vars:
163 * Implement renaming of SSA variables. Also compute def-use information in parallel.
164 * @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
;
242 g_assert (stack_history_len
< stack_history_size
);
243 stack_history
[stack_history_len
].var
= stack
[idx
];
244 stack_history
[stack_history_len
].idx
= idx
;
245 stack_history_len
++;
247 if (originals_used
[idx
]) {
248 new_var
= mono_compile_create_var (cfg
, var
->inst_vtype
, OP_LOCAL
);
249 new_var
->flags
= var
->flags
;
250 MONO_VARINFO (cfg
, new_var
->inst_c0
)->reg
= idx
;
252 if (cfg
->verbose_level
>= 4)
253 printf (" R%d -> R%d\n", var
->dreg
, new_var
->dreg
);
255 stack
[idx
] = new_var
;
257 ins
->dreg
= new_var
->dreg
;
262 originals_used
[idx
] = TRUE
;
265 info
= MONO_VARINFO (cfg
, var
->inst_c0
);
269 else if (G_UNLIKELY (!var
&& lvreg_defined
[ins
->dreg
] && (ins
->dreg
>= MONO_MAX_IREGS
))) {
270 /* Perform renaming for local vregs */
271 lvreg_stack
[ins
->dreg
] = mono_alloc_preg (cfg
);
272 ins
->dreg
= lvreg_stack
[ins
->dreg
];
275 lvreg_defined
[ins
->dreg
] = TRUE
;
279 printf ("\tAfter processing "); mono_print_ins (ins
);
284 /* Rename PHI arguments in succeeding bblocks */
285 for (i
= 0; i
< bb
->out_count
; i
++) {
286 MonoBasicBlock
*n
= bb
->out_bb
[i
];
288 for (j
= 0; j
< n
->in_count
; j
++)
289 if (n
->in_bb
[j
] == bb
)
292 for (ins
= n
->code
; ins
; ins
= ins
->next
) {
293 if (MONO_IS_PHI (ins
)) {
296 new_var
= stack
[idx
];
298 new_var
= cfg
->varinfo
[idx
];
300 printf ("FOUND PHI %d (%d, %d)\n", idx
, j
, new_var
->inst_c0
);
302 ins
->inst_phi_args
[j
+ 1] = new_var
->dreg
;
303 record_use (cfg
, new_var
, n
, ins
);
304 if (G_UNLIKELY (cfg
->verbose_level
>= 4))
305 printf ("\tAdd PHI R%d <- R%d to BB%d\n", ins
->dreg
, new_var
->dreg
, n
->block_num
);
308 /* The phi nodes are at the beginning of the bblock */
314 for (tmp
= bb
->dominated
; tmp
; tmp
= tmp
->next
) {
315 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
);
320 for (i
= stack_history_len
- 1; i
>= 0; i
--) {
321 stack
[stack_history
[i
].idx
] = stack_history
[i
].var
;
324 cfg
->comp_done
|= MONO_COMP_SSA_DEF_USE
;
328 mono_ssa_compute (MonoCompile
*cfg
)
330 int i
, j
, idx
, bitsize
;
332 MonoMethodVar
*vinfo
= g_new0 (MonoMethodVar
, cfg
->num_varinfo
);
333 MonoInst
*ins
, **stack
;
334 guint8
*buf
, *buf_start
;
335 RenameInfo
*stack_history
;
336 int stack_history_size
;
338 guint32
*lvreg_stack
;
339 gboolean
*lvreg_defined
;
341 g_assert (!(cfg
->comp_done
& MONO_COMP_SSA
));
343 g_assert (!cfg
->disable_ssa
);
345 if (cfg
->verbose_level
>= 4)
346 printf ("\nCOMPUTE SSA %d (R%d-)\n\n", cfg
->num_varinfo
, cfg
->next_vreg
);
348 #ifdef CREATE_PRUNED_SSA
349 /* we need liveness for pruned SSA */
350 if (!(cfg
->comp_done
& MONO_COMP_LIVENESS
))
351 mono_analyze_liveness (cfg
);
354 mono_compile_dominator_info (cfg
, MONO_COMP_DOM
| MONO_COMP_IDOM
| MONO_COMP_DFRONTIER
);
356 bitsize
= mono_bitset_alloc_size (cfg
->num_bblocks
, 0);
357 buf
= buf_start
= g_malloc0 (mono_bitset_alloc_size (cfg
->num_bblocks
, 0) * cfg
->num_varinfo
);
359 for (i
= 0; i
< cfg
->num_varinfo
; ++i
) {
360 vinfo
[i
].def_in
= mono_bitset_mem_new (buf
, cfg
->num_bblocks
, 0);
363 /* implicit reference at start */
364 if (cfg
->varinfo
[i
]->opcode
== OP_ARG
)
365 mono_bitset_set_fast (vinfo
[i
].def_in
, 0);
368 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
369 MONO_BB_FOR_EACH_INS (cfg
->bblocks
[i
], ins
) {
370 if (ins
->opcode
== OP_NOP
)
373 if (!MONO_IS_STORE_MEMBASE (ins
) && get_vreg_to_inst (cfg
, ins
->dreg
)) {
374 mono_bitset_set_fast (vinfo
[get_vreg_to_inst (cfg
, ins
->dreg
)->inst_c0
].def_in
, i
);
379 /* insert phi functions */
380 for (i
= 0; i
< cfg
->num_varinfo
; ++i
) {
381 MonoInst
*var
= cfg
->varinfo
[i
];
383 #if SIZEOF_REGISTER == 4
384 if (var
->type
== STACK_I8
&& !COMPILE_LLVM (cfg
))
387 if (var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))
390 /* Most variables have only one definition */
391 if (mono_bitset_count (vinfo
[i
].def_in
) <= 1)
394 set
= mono_compile_iterated_dfrontier (cfg
, vinfo
[i
].def_in
);
396 if (cfg
->verbose_level
>= 4) {
397 if (mono_bitset_count (set
) > 0) {
398 printf ("\tR%d needs PHI functions in ", var
->dreg
);
399 mono_blockset_print (cfg
, set
, "", -1);
403 mono_bitset_foreach_bit (set
, idx
, cfg
->num_bblocks
) {
404 MonoBasicBlock
*bb
= cfg
->bblocks
[idx
];
406 /* fixme: create pruned SSA? we would need liveness information for that */
408 if (bb
== cfg
->bb_exit
&& !COMPILE_LLVM (cfg
))
411 if ((cfg
->comp_done
& MONO_COMP_LIVENESS
) && !mono_bitset_test_fast (bb
->live_in_set
, i
)) {
412 //printf ("%d is not live in BB%d %s\n", i, bb->block_num, mono_method_full_name (cfg->method, TRUE));
416 NEW_PHI (cfg
, ins
, i
);
424 ins
->opcode
= OP_PHI
;
427 ins
->opcode
= OP_FPHI
;
430 ins
->opcode
= MONO_CLASS_IS_SIMD (cfg
, var
->klass
) ? OP_XPHI
: OP_VPHI
;
434 if (var
->inst_vtype
->byref
)
435 ins
->klass
= mono_defaults
.int_class
;
437 ins
->klass
= var
->klass
;
439 ins
->inst_phi_args
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (int) * (cfg
->bblocks
[idx
]->in_count
+ 1));
440 ins
->inst_phi_args
[0] = cfg
->bblocks
[idx
]->in_count
;
443 for (j
= 0; j
< cfg
->bblocks
[idx
]->in_count
; ++j
)
444 ins
->inst_phi_args
[j
+ 1] = -1;
446 ins
->dreg
= cfg
->varinfo
[i
]->dreg
;
448 mono_bblock_insert_before_ins (bb
, bb
->code
, ins
);
451 printf ("ADD PHI BB%d %s\n", cfg
->bblocks
[idx
]->block_num
, mono_method_full_name (cfg
->method
, TRUE
));
462 stack
= alloca (sizeof (MonoInst
*) * cfg
->num_varinfo
);
463 memset (stack
, 0, sizeof (MonoInst
*) * cfg
->num_varinfo
);
465 lvreg_stack
= g_new0 (guint32
, cfg
->next_vreg
);
466 lvreg_defined
= g_new0 (gboolean
, cfg
->next_vreg
);
467 stack_history_size
= 10240;
468 stack_history
= g_new (RenameInfo
, stack_history_size
);
469 originals
= g_new0 (gboolean
, cfg
->num_varinfo
);
470 mono_ssa_rename_vars (cfg
, cfg
->num_varinfo
, cfg
->bb_entry
, originals
, stack
, lvreg_stack
, lvreg_defined
, stack_history
, stack_history_size
);
471 g_free (stack_history
);
473 g_free (lvreg_stack
);
474 g_free (lvreg_defined
);
476 if (cfg
->verbose_level
>= 4)
477 printf ("\nEND COMPUTE SSA.\n\n");
479 cfg
->comp_done
|= MONO_COMP_SSA
;
483 mono_ssa_remove (MonoCompile
*cfg
)
485 MonoInst
*ins
, *var
, *move
;
488 g_assert (cfg
->comp_done
& MONO_COMP_SSA
);
490 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
491 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
493 if (cfg
->verbose_level
>= 4)
494 printf ("\nREMOVE SSA %d:\n", bb
->block_num
);
496 for (ins
= bb
->code
; ins
; ins
= ins
->next
) {
497 if (MONO_IS_PHI (ins
)) {
498 g_assert (ins
->inst_phi_args
[0] == bb
->in_count
);
499 var
= get_vreg_to_inst (cfg
, ins
->dreg
);
501 /* Check for PHI nodes where all the inputs are the same */
502 first
= ins
->inst_phi_args
[1];
504 for (j
= 1; j
< bb
->in_count
; ++j
)
505 if (first
!= ins
->inst_phi_args
[j
+ 1])
508 if ((bb
->in_count
> 1) && (j
== bb
->in_count
)) {
509 ins
->opcode
= op_phi_to_move (ins
->opcode
);
510 if (ins
->opcode
== OP_VMOVE
)
511 g_assert (ins
->klass
);
514 for (j
= 0; j
< bb
->in_count
; j
++) {
515 MonoBasicBlock
*pred
= bb
->in_bb
[j
];
516 int sreg
= ins
->inst_phi_args
[j
+ 1];
518 if (cfg
->verbose_level
>= 4)
519 printf ("\tADD R%d <- R%d in BB%d\n", var
->dreg
, sreg
, pred
->block_num
);
520 if (var
->dreg
!= sreg
) {
521 MONO_INST_NEW (cfg
, move
, op_phi_to_move (ins
->opcode
));
522 if (move
->opcode
== OP_VMOVE
) {
523 g_assert (ins
->klass
);
524 move
->klass
= ins
->klass
;
526 move
->dreg
= var
->dreg
;
528 mono_add_ins_to_end (pred
, move
);
532 ins
->opcode
= OP_NOP
;
539 if (cfg
->verbose_level
>= 4) {
540 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
541 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
543 mono_print_bb (bb
, "AFTER REMOVE SSA:");
548 * Removal of SSA form introduces many copies. To avoid this, we tyry to coalesce
549 * the variables if possible. Since the newly introduced SSA variables don't
550 * have overlapping live ranges (because we don't do agressive optimization), we
551 * can coalesce them into the original variable.
554 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
555 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
557 for (ins
= bb
->code
; ins
; ins
= ins
->next
) {
558 const char *spec
= INS_INFO (ins
->opcode
);
560 int sregs
[MONO_MAX_SRC_REGS
];
562 if (ins
->opcode
== OP_NOP
)
565 if (spec
[MONO_INST_DEST
] != ' ') {
566 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
569 MonoMethodVar
*vmv
= MONO_VARINFO (cfg
, var
->inst_c0
);
572 * The third condition avoids coalescing with variables eliminated
575 if ((vmv
->reg
!= -1) && (vmv
->idx
!= vmv
->reg
) && (MONO_VARINFO (cfg
, vmv
->reg
)->reg
!= -1)) {
576 printf ("COALESCE: R%d -> R%d\n", ins
->dreg
, cfg
->varinfo
[vmv
->reg
]->dreg
);
577 ins
->dreg
= cfg
->varinfo
[vmv
->reg
]->dreg
;
582 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
583 for (j
= 0; j
< num_sregs
; ++j
) {
584 MonoInst
*var
= get_vreg_to_inst (cfg
, sregs
[i
]);
587 MonoMethodVar
*vmv
= MONO_VARINFO (cfg
, var
->inst_c0
);
589 if ((vmv
->reg
!= -1) && (vmv
->idx
!= vmv
->reg
) && (MONO_VARINFO (cfg
, vmv
->reg
)->reg
!= -1)) {
590 printf ("COALESCE: R%d -> R%d\n", sregs
[i
], cfg
->varinfo
[vmv
->reg
]->dreg
);
591 sregs
[i
] = cfg
->varinfo
[vmv
->reg
]->dreg
;
595 mono_inst_set_src_registers (ins
, sregs
);
599 for (i
= 0; i
< cfg
->num_varinfo
; ++i
) {
600 MONO_VARINFO (cfg
, i
)->reg
= -1;
603 if (cfg
->comp_done
& MONO_COMP_REACHABILITY
)
604 unlink_unused_bblocks (cfg
);
606 cfg
->comp_done
&= ~MONO_COMP_LIVENESS
;
608 cfg
->comp_done
&= ~MONO_COMP_SSA
;
612 mono_ssa_create_def_use (MonoCompile
*cfg
)
618 g_assert (!(cfg
->comp_done
& MONO_COMP_SSA_DEF_USE
));
620 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
621 for (ins
= bb
->code
; ins
; ins
= ins
->next
) {
622 const char *spec
= INS_INFO (ins
->opcode
);
625 int sregs
[MONO_MAX_SRC_REGS
];
627 if (ins
->opcode
== OP_NOP
)
631 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
632 for (i
= 0; i
< num_sregs
; ++i
) {
633 MonoInst
*var
= get_vreg_to_inst (cfg
, sregs
[i
]);
634 if (var
&& !(var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
)))
635 record_use (cfg
, var
, bb
, ins
);
638 if (MONO_IS_STORE_MEMBASE (ins
)) {
639 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
640 if (var
&& !(var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
)))
641 record_use (cfg
, var
, bb
, ins
);
644 if (MONO_IS_PHI (ins
)) {
645 for (i
= ins
->inst_phi_args
[0]; i
> 0; i
--) {
646 g_assert (ins
->inst_phi_args
[i
] != -1);
647 record_use (cfg
, get_vreg_to_inst (cfg
, ins
->inst_phi_args
[i
]), bb
, ins
);
652 if ((spec
[MONO_INST_DEST
] != ' ') && !MONO_IS_STORE_MEMBASE (ins
)) {
653 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
655 if (var
&& !(var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
656 info
= MONO_VARINFO (cfg
, var
->inst_c0
);
664 cfg
->comp_done
|= MONO_COMP_SSA_DEF_USE
;
668 mono_ssa_copyprop (MonoCompile
*cfg
)
673 g_assert ((cfg
->comp_done
& MONO_COMP_SSA_DEF_USE
));
675 for (index
= 0; index
< cfg
->num_varinfo
; ++index
) {
676 MonoInst
*var
= cfg
->varinfo
[index
];
677 MonoMethodVar
*info
= MONO_VARINFO (cfg
, index
);
679 if (info
->def
&& (MONO_IS_MOVE (info
->def
))) {
680 MonoInst
*var2
= get_vreg_to_inst (cfg
, info
->def
->sreg1
);
682 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
))) {
683 /* Rewrite all uses of var to be uses of var2 */
684 int dreg
= var
->dreg
;
685 int sreg1
= var2
->dreg
;
690 MonoVarUsageInfo
*u
= (MonoVarUsageInfo
*)l
->data
;
691 MonoInst
*ins
= u
->inst
;
692 GList
*next
= l
->next
;
694 int sregs
[MONO_MAX_SRC_REGS
];
696 spec
= INS_INFO (ins
->opcode
);
698 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
699 for (i
= 0; i
< num_sregs
; ++i
) {
700 if (sregs
[i
] == dreg
)
704 g_assert (sregs
[i
] == dreg
);
706 mono_inst_set_src_registers (ins
, sregs
);
707 } else if (MONO_IS_STORE_MEMBASE (ins
) && ins
->dreg
== dreg
) {
709 } else if (MONO_IS_PHI (ins
)) {
710 for (i
= ins
->inst_phi_args
[0]; i
> 0; i
--) {
711 int sreg
= ins
->inst_phi_args
[i
];
712 if (sreg
== var
->dreg
)
716 ins
->inst_phi_args
[i
] = sreg1
;
719 g_assert_not_reached ();
721 record_use (cfg
, var2
, u
->bb
, ins
);
731 if (cfg
->verbose_level
>= 4) {
734 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
)
735 mono_print_bb (bb
, "AFTER SSA COPYPROP");
740 evaluate_ins (MonoCompile
*cfg
, MonoInst
*ins
, MonoInst
**res
, MonoInst
**carray
)
742 MonoInst
*args
[MONO_MAX_SRC_REGS
];
743 int rs
[MONO_MAX_SRC_REGS
];
745 gboolean const_args
= TRUE
;
746 const char *spec
= INS_INFO (ins
->opcode
);
748 int sregs
[MONO_MAX_SRC_REGS
];
750 /* Short-circuit this */
751 if (ins
->opcode
== OP_ICONST
) {
756 if (ins
->opcode
== OP_NOP
)
759 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
760 for (i
= 0; i
< MONO_MAX_SRC_REGS
; ++i
)
762 for (i
= 0; i
< num_sregs
; ++i
) {
763 MonoInst
*var
= get_vreg_to_inst (cfg
, sregs
[i
]);
766 args
[i
] = carray
[sregs
[i
]];
769 else if (var
&& !(var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
)))
770 rs
[i
] = MONO_VARINFO (cfg
, var
->inst_c0
)->cpstate
;
777 if (num_sregs
> 0 && const_args
) {
778 g_assert (num_sregs
<= 2);
779 if ((spec
[MONO_INST_DEST
] != ' ') && carray
[ins
->dreg
]) {
781 *res
= carray
[ins
->dreg
];
784 c0
= mono_constant_fold_ins (cfg
, ins
, args
[0], args
[1], FALSE
);
786 if (G_UNLIKELY (cfg
->verbose_level
> 1)) {
787 printf ("\t cfold -> ");
794 /* Can't cfold this ins */
800 for (i
= 0; i
< num_sregs
; ++i
) {
808 change_varstate (MonoCompile
*cfg
, GList
**cvars
, MonoMethodVar
*info
, int state
, MonoInst
*c0
, MonoInst
**carray
)
810 if (info
->cpstate
>= state
)
813 info
->cpstate
= state
;
815 if (G_UNLIKELY (cfg
->verbose_level
> 1))
816 printf ("\tState of R%d set to %d\n", cfg
->varinfo
[info
->idx
]->dreg
, info
->cpstate
);
821 carray
[cfg
->varinfo
[info
->idx
]->dreg
] = c0
;
823 if (!g_list_find (*cvars
, info
)) {
824 *cvars
= g_list_prepend (*cvars
, info
);
829 add_cprop_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
, GList
**bblist
)
831 if (G_UNLIKELY (cfg
->verbose_level
> 1))
832 printf ("\tAdd BB%d to worklist\n", bb
->block_num
);
834 if (!(bb
->flags
& BB_REACHABLE
)) {
835 bb
->flags
|= BB_REACHABLE
;
836 *bblist
= g_list_prepend (*bblist
, bb
);
841 visit_inst (MonoCompile
*cfg
, MonoBasicBlock
*bb
, MonoInst
*ins
, GList
**cvars
, GList
**bblist
, MonoInst
**carray
)
843 const char *spec
= INS_INFO (ins
->opcode
);
845 if (ins
->opcode
== OP_NOP
)
848 if (cfg
->verbose_level
> 1)
849 mono_print_ins (ins
);
851 /* FIXME: Support longs/floats */
852 /* FIXME: Work on vregs as well */
854 if (MONO_IS_PHI (ins
)) {
855 MonoMethodVar
*info
= MONO_VARINFO (cfg
, get_vreg_to_inst (cfg
, ins
->dreg
)->inst_c0
);
859 for (j
= 1; j
<= ins
->inst_phi_args
[0]; j
++) {
860 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->inst_phi_args
[j
]);
861 MonoMethodVar
*mv
= MONO_VARINFO (cfg
, var
->inst_c0
);
862 MonoInst
*src
= mv
->def
;
864 if (mv
->def_bb
&& !(mv
->def_bb
->flags
& BB_REACHABLE
))
867 if (!mv
->def
|| !src
|| mv
->cpstate
== 2) {
868 change_varstate (cfg
, cvars
, info
, 2, NULL
, carray
);
872 if (mv
->cpstate
== 0)
875 g_assert (carray
[var
->dreg
]);
878 c0
= carray
[var
->dreg
];
881 if (c0
->opcode
!= OP_ICONST
) {
882 change_varstate (cfg
, cvars
, info
, 2, NULL
, carray
);
886 if (carray
[var
->dreg
]->inst_c0
!= c0
->inst_c0
) {
887 change_varstate (cfg
, cvars
, info
, 2, NULL
, carray
);
892 if (c0
&& info
->cpstate
< 1) {
893 change_varstate (cfg
, cvars
, info
, 1, c0
, carray
);
895 g_assert (c0
->opcode
== OP_ICONST
);
898 else if (!MONO_IS_STORE_MEMBASE (ins
) && ((spec
[MONO_INST_SRC1
] != ' ') || (spec
[MONO_INST_SRC2
] != ' ') || (spec
[MONO_INST_DEST
] != ' '))) {
902 if (spec
[MONO_INST_DEST
] != ' ')
903 var
= get_vreg_to_inst (cfg
, ins
->dreg
);
908 state
= evaluate_ins (cfg
, ins
, &c0
, carray
);
910 if (var
&& !(var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
911 MonoMethodVar
*info
= MONO_VARINFO (cfg
, var
->inst_c0
);
913 if (info
->cpstate
< 2) {
915 change_varstate (cfg
, cvars
, info
, 1, c0
, carray
);
917 change_varstate (cfg
, cvars
, info
, 2, NULL
, carray
);
920 else if (!var
&& (ins
->dreg
!= -1)) {
922 * We don't record def-use information for local vregs since it would be
923 * expensive. Instead, we depend on the fact that all uses of the vreg are in
924 * the same bblock, so they will be examined after the definition.
925 * FIXME: This isn't true if the ins is visited through an SSA edge.
928 carray
[ins
->dreg
] = c0
;
930 if (carray
[ins
->dreg
]) {
932 * The state of the vreg changed from constant to non-constant
933 * -> need to rescan the whole bblock.
935 carray
[ins
->dreg
] = NULL
;
936 /* FIXME: Speed this up */
938 if (!g_list_find (*bblist
, bb
))
939 *bblist
= g_list_prepend (*bblist
, bb
);
944 if (MONO_IS_JUMP_TABLE (ins
)) {
946 MonoJumpInfoBBTable
*table
= MONO_JUMP_TABLE_FROM_INS (ins
);
948 if (!ins
->next
|| ins
->next
->opcode
!= OP_PADD
) {
949 /* The PADD was optimized away */
950 /* FIXME: handle this as well */
951 for (i
= 0; i
< table
->table_size
; i
++)
952 if (table
->table
[i
])
953 add_cprop_bb (cfg
, table
->table
[i
], bblist
);
957 g_assert (ins
->next
->opcode
== OP_PADD
);
958 g_assert (ins
->next
->sreg1
== ins
->dreg
);
960 if (carray
[ins
->next
->sreg2
]) {
961 #if SIZEOF_REGISTER == 8
962 int idx
= carray
[ins
->next
->sreg2
]->inst_c0
>> 3;
964 int idx
= carray
[ins
->next
->sreg2
]->inst_c0
>> 2;
966 if ((idx
< 0) || (idx
>= table
->table_size
))
967 /* Out-of-range, no branch is executed */
970 if (table
->table
[idx
])
971 add_cprop_bb (cfg
, table
->table
[idx
], bblist
);
974 for (i
= 0; i
< table
->table_size
; i
++)
975 if (table
->table
[i
])
976 add_cprop_bb (cfg
, table
->table
[i
], bblist
);
980 if (ins
->opcode
== OP_SWITCH
) {
982 MonoJumpInfoBBTable
*table
= ins
->inst_p0
;
984 for (i
= 0; i
< table
->table_size
; i
++)
985 if (table
->table
[i
])
986 add_cprop_bb (cfg
, table
->table
[i
], bblist
);
989 /* Handle COMPARE+BRCOND pairs */
990 if (ins
->next
&& MONO_IS_COND_BRANCH_OP (ins
->next
)) {
992 g_assert (c0
->opcode
== OP_ICONST
);
995 ins
->next
->flags
|= MONO_INST_CFOLD_TAKEN
;
997 ins
->next
->flags
|= MONO_INST_CFOLD_NOT_TAKEN
;
1000 ins
->next
->flags
&= ~(MONO_INST_CFOLD_TAKEN
| MONO_INST_CFOLD_NOT_TAKEN
);
1003 visit_inst (cfg
, bb
, ins
->next
, cvars
, bblist
, carray
);
1005 } else if (ins
->opcode
== OP_BR
) {
1006 add_cprop_bb (cfg
, ins
->inst_target_bb
, bblist
);
1007 } else if (MONO_IS_COND_BRANCH_OP (ins
)) {
1008 if (ins
->flags
& MONO_INST_CFOLD_TAKEN
) {
1009 add_cprop_bb (cfg
, ins
->inst_true_bb
, bblist
);
1010 } else if (ins
->flags
& MONO_INST_CFOLD_NOT_TAKEN
) {
1011 if (ins
->inst_false_bb
)
1012 add_cprop_bb (cfg
, ins
->inst_false_bb
, bblist
);
1014 add_cprop_bb (cfg
, ins
->inst_true_bb
, bblist
);
1015 if (ins
->inst_false_bb
)
1016 add_cprop_bb (cfg
, ins
->inst_false_bb
, bblist
);
1024 * Replace INS with its constant value, if it exists
1027 fold_ins (MonoCompile
*cfg
, MonoBasicBlock
*bb
, MonoInst
*ins
, MonoInst
**carray
)
1029 const char *spec
= INS_INFO (ins
->opcode
);
1031 int num_sregs
= mono_inst_get_num_src_registers (ins
);
1033 if ((ins
->opcode
!= OP_NOP
) && (ins
->dreg
!= -1) && !MONO_IS_STORE_MEMBASE (ins
)) {
1034 if (carray
[ins
->dreg
] && (spec
[MONO_INST_DEST
] == 'i') && (ins
->dreg
>= MONO_MAX_IREGS
)) {
1035 /* Perform constant folding */
1037 g_assert (carray
[ins
->dreg
]->opcode
== OP_ICONST
);
1038 ins
->opcode
= OP_ICONST
;
1039 ins
->inst_c0
= carray
[ins
->dreg
]->inst_c0
;
1040 MONO_INST_NULLIFY_SREGS (ins
);
1041 } else if (num_sregs
== 2 && carray
[ins
->sreg2
]) {
1042 /* Perform op->op_imm conversion */
1043 opcode2
= mono_op_to_op_imm (ins
->opcode
);
1044 if (opcode2
!= -1) {
1045 ins
->opcode
= opcode2
;
1046 ins
->inst_imm
= carray
[ins
->sreg2
]->inst_c0
;
1049 if ((opcode2
== OP_VOIDCALL
) || (opcode2
== OP_CALL
) || (opcode2
== OP_LCALL
) || (opcode2
== OP_FCALL
))
1050 ((MonoCallInst
*)ins
)->fptr
= (gpointer
)ins
->inst_imm
;
1053 /* FIXME: Handle 3 op insns */
1056 if (MONO_IS_JUMP_TABLE (ins
)) {
1058 MonoJumpInfoBBTable
*table
= MONO_JUMP_TABLE_FROM_INS (ins
);
1060 if (!ins
->next
|| ins
->next
->opcode
!= OP_PADD
) {
1061 /* The PADD was optimized away */
1062 /* FIXME: handle this as well */
1066 g_assert (ins
->next
->opcode
== OP_PADD
);
1067 g_assert (ins
->next
->sreg1
== ins
->dreg
);
1068 g_assert (ins
->next
->next
->opcode
== OP_LOAD_MEMBASE
);
1070 if (carray
[ins
->next
->sreg2
]) {
1071 /* Convert to a simple branch */
1072 #if SIZEOF_REGISTER == 8
1073 int idx
= carray
[ins
->next
->sreg2
]->inst_c0
>> 3;
1075 int idx
= carray
[ins
->next
->sreg2
]->inst_c0
>> 2;
1078 if (!((idx
>= 0) && (idx
< table
->table_size
))) {
1079 /* Out of range, eliminate the whole switch */
1080 for (i
= 0; i
< table
->table_size
; ++i
) {
1081 remove_bb_from_phis (cfg
, bb
, table
->table
[i
]);
1082 mono_unlink_bblock (cfg
, bb
, table
->table
[i
]);
1086 NULLIFY_INS (ins
->next
);
1087 NULLIFY_INS (ins
->next
->next
);
1088 if (ins
->next
->next
->next
)
1089 NULLIFY_INS (ins
->next
->next
->next
);
1094 if (!ins
->next
->next
->next
|| ins
->next
->next
->next
->opcode
!= OP_BR_REG
) {
1095 /* A one-way switch which got optimized away */
1096 if (G_UNLIKELY (cfg
->verbose_level
> 1)) {
1097 printf ("\tNo cfold on ");
1098 mono_print_ins (ins
);
1103 if (G_UNLIKELY (cfg
->verbose_level
> 1)) {
1104 printf ("\tcfold on ");
1105 mono_print_ins (ins
);
1108 /* Unlink target bblocks */
1109 for (i
= 0; i
< table
->table_size
; ++i
) {
1111 remove_bb_from_phis (cfg
, bb
, table
->table
[i
]);
1112 mono_unlink_bblock (cfg
, bb
, table
->table
[i
]);
1116 /* Change the OP_BR_REG to a simple branch */
1117 ins
->next
->next
->next
->opcode
= OP_BR
;
1118 ins
->next
->next
->next
->inst_target_bb
= table
->table
[idx
];
1119 ins
->next
->next
->next
->sreg1
= -1;
1121 /* Nullify the other instructions */
1123 NULLIFY_INS (ins
->next
);
1124 NULLIFY_INS (ins
->next
->next
);
1128 else if (MONO_IS_COND_BRANCH_OP (ins
)) {
1129 if (ins
->flags
& MONO_INST_CFOLD_TAKEN
) {
1130 remove_bb_from_phis (cfg
, bb
, ins
->inst_false_bb
);
1131 mono_unlink_bblock (cfg
, bb
, ins
->inst_false_bb
);
1132 ins
->opcode
= OP_BR
;
1133 ins
->inst_target_bb
= ins
->inst_true_bb
;
1134 } else if (ins
->flags
& MONO_INST_CFOLD_NOT_TAKEN
) {
1135 remove_bb_from_phis (cfg
, bb
, ins
->inst_true_bb
);
1136 mono_unlink_bblock (cfg
, bb
, ins
->inst_true_bb
);
1137 ins
->opcode
= OP_BR
;
1138 ins
->inst_target_bb
= ins
->inst_false_bb
;
1144 mono_ssa_cprop (MonoCompile
*cfg
)
1148 GList
*bblock_list
, *cvars
;
1151 //printf ("SIMPLE OPTS BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
1153 carray
= g_new0 (MonoInst
*, cfg
->next_vreg
);
1155 if (!(cfg
->comp_done
& MONO_COMP_SSA_DEF_USE
))
1156 mono_ssa_create_def_use (cfg
);
1158 bblock_list
= g_list_prepend (NULL
, cfg
->bb_entry
);
1159 cfg
->bb_entry
->flags
|= BB_REACHABLE
;
1161 memset (carray
, 0, sizeof (MonoInst
*) * cfg
->num_varinfo
);
1163 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
1164 MonoMethodVar
*info
= MONO_VARINFO (cfg
, i
);
1169 for (bb
= cfg
->bb_entry
->next_bb
; bb
; bb
= bb
->next_bb
) {
1171 * FIXME: This should be bb->flags & BB_FLAG_EXCEPTION_HANDLER, but
1172 * that would still allow unreachable try's to be removed.
1175 add_cprop_bb (cfg
, bb
, &bblock_list
);
1180 while (bblock_list
) {
1183 bb
= (MonoBasicBlock
*)bblock_list
->data
;
1185 bblock_list
= g_list_delete_link (bblock_list
, bblock_list
);
1187 g_assert (bb
->flags
& BB_REACHABLE
);
1190 * Some bblocks are linked to 2 others even through they fall through to the
1193 if (!(bb
->last_ins
&& MONO_IS_BRANCH_OP (bb
->last_ins
))) {
1194 for (i
= 0; i
< bb
->out_count
; ++i
)
1195 add_cprop_bb (cfg
, bb
->out_bb
[i
], &bblock_list
);
1198 if (cfg
->verbose_level
> 1)
1199 printf ("\nSSA CONSPROP BB%d:\n", bb
->block_num
);
1201 for (inst
= bb
->code
; inst
; inst
= inst
->next
) {
1202 visit_inst (cfg
, bb
, inst
, &cvars
, &bblock_list
, carray
);
1206 MonoMethodVar
*info
= (MonoMethodVar
*)cvars
->data
;
1207 cvars
= g_list_delete_link (cvars
, cvars
);
1209 for (tmp
= info
->uses
; tmp
; tmp
= tmp
->next
) {
1210 MonoVarUsageInfo
*ui
= (MonoVarUsageInfo
*)tmp
->data
;
1211 if (!(ui
->bb
->flags
& BB_REACHABLE
))
1213 visit_inst (cfg
, ui
->bb
, ui
->inst
, &cvars
, &bblock_list
, carray
);
1218 for (bb
= cfg
->bb_entry
->next_bb
; bb
; bb
= bb
->next_bb
) {
1220 for (inst
= bb
->code
; inst
; inst
= inst
->next
) {
1221 fold_ins (cfg
, bb
, inst
, carray
);
1227 cfg
->comp_done
|= MONO_COMP_REACHABILITY
;
1229 /* fixme: we should update usage infos during cprop, instead of computing it again */
1230 cfg
->comp_done
&= ~MONO_COMP_SSA_DEF_USE
;
1231 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
1232 MonoMethodVar
*info
= MONO_VARINFO (cfg
, i
);
1239 add_to_dce_worklist (MonoCompile
*cfg
, MonoMethodVar
*var
, MonoMethodVar
*use
, GList
**wl
)
1243 *wl
= g_list_prepend_mempool (cfg
->mempool
, *wl
, use
);
1245 for (tmp
= use
->uses
; tmp
; tmp
= tmp
->next
) {
1246 MonoVarUsageInfo
*ui
= (MonoVarUsageInfo
*)tmp
->data
;
1247 if (ui
->inst
== var
->def
) {
1248 /* from the mempool */
1249 use
->uses
= g_list_remove_link (use
->uses
, tmp
);
1256 mono_ssa_deadce (MonoCompile
*cfg
)
1261 g_assert (cfg
->comp_done
& MONO_COMP_SSA
);
1263 //printf ("DEADCE %s\n", mono_method_full_name (cfg->method, TRUE));
1265 if (!(cfg
->comp_done
& MONO_COMP_SSA_DEF_USE
))
1266 mono_ssa_create_def_use (cfg
);
1268 mono_ssa_copyprop (cfg
);
1271 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
1272 MonoMethodVar
*info
= MONO_VARINFO (cfg
, i
);
1273 work_list
= g_list_prepend_mempool (cfg
->mempool
, work_list
, info
);
1277 MonoMethodVar
*info
= (MonoMethodVar
*)work_list
->data
;
1278 work_list
= g_list_remove_link (work_list
, work_list
);
1281 * The second part of the condition happens often when PHI nodes have their dreg
1282 * as one of their arguments due to the fact that we use the original vars.
1284 if (info
->def
&& (!info
->uses
|| ((info
->uses
->next
== NULL
) && (((MonoVarUsageInfo
*)info
->uses
->data
)->inst
== info
->def
)))) {
1285 MonoInst
*def
= info
->def
;
1287 /* Eliminating FMOVE could screw up the fp stack */
1288 if (MONO_IS_MOVE (def
) && (!MONO_ARCH_USE_FPSTACK
|| (def
->opcode
!= OP_FMOVE
))) {
1289 MonoInst
*src_var
= get_vreg_to_inst (cfg
, def
->sreg1
);
1290 if (src_var
&& !(src_var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
)))
1291 add_to_dce_worklist (cfg
, info
, MONO_VARINFO (cfg
, src_var
->inst_c0
), &work_list
);
1292 def
->opcode
= OP_NOP
;
1293 def
->dreg
= def
->sreg1
= def
->sreg2
= -1;
1295 } else if ((def
->opcode
== OP_ICONST
) || (def
->opcode
== OP_I8CONST
) || MONO_IS_ZERO (def
)) {
1296 def
->opcode
= OP_NOP
;
1297 def
->dreg
= def
->sreg1
= def
->sreg2
= -1;
1299 } else if (MONO_IS_PHI (def
)) {
1301 for (j
= def
->inst_phi_args
[0]; j
> 0; j
--) {
1302 MonoMethodVar
*u
= MONO_VARINFO (cfg
, get_vreg_to_inst (cfg
, def
->inst_phi_args
[j
])->inst_c0
);
1303 add_to_dce_worklist (cfg
, info
, u
, &work_list
);
1305 def
->opcode
= OP_NOP
;
1306 def
->dreg
= def
->sreg1
= def
->sreg2
= -1;
1309 else if (def
->opcode
== OP_NOP
) {
1312 //mono_print_ins (def);
1320 mono_ssa_strength_reduction (MonoCompile
*cfg
)
1325 g_assert (cfg
->comp_done
& MONO_COMP_SSA
);
1326 g_assert (cfg
->comp_done
& MONO_COMP_LOOPS
);
1327 g_assert (cfg
->comp_done
& MONO_COMP_SSA_DEF_USE
);
1329 for (bb
= cfg
->bb_entry
->next_bb
; bb
; bb
= bb
->next_bb
) {
1330 GList
*lp
= bb
->loop_blocks
;
1333 MonoBasicBlock
*h
= (MonoBasicBlock
*)lp
->data
;
1335 /* we only consider loops with 2 in bblocks */
1336 if (!h
->in_count
== 2)
1339 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
1340 MonoMethodVar
*info
= MONO_VARINFO (cfg
, i
);
1342 if (info
->def
&& info
->def
->ssa_op
== MONO_SSA_STORE
&&
1343 info
->def
->inst_i0
->opcode
== OP_LOCAL
&& g_list_find (lp
, info
->def_bb
)) {
1344 MonoInst
*v
= info
->def
->inst_i1
;
1347 printf ("FOUND %d in %s\n", info
->idx
, mono_method_full_name (cfg
->method
, TRUE
));
1355 #endif /* DISABLE_JIT */