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
] = vreg_is_ref (cfg
, ins
->dreg
) ? mono_alloc_ireg_ref (cfg
) : 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
;
486 int bbindex
, i
, j
, first
;
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 (bbindex
= 0; bbindex
< cfg
->num_bblocks
; ++bbindex
) {
555 MonoBasicBlock
*bb
= cfg
->bblocks
[bbindex
];
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 (i
= 0; i
< num_sregs
; ++i
) {
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
;
689 MonoVarUsageInfo
*u
= (MonoVarUsageInfo
*)l
->data
;
690 MonoInst
*ins
= u
->inst
;
691 GList
*next
= l
->next
;
693 int sregs
[MONO_MAX_SRC_REGS
];
695 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
696 for (i
= 0; i
< num_sregs
; ++i
) {
697 if (sregs
[i
] == dreg
)
701 g_assert (sregs
[i
] == dreg
);
703 mono_inst_set_src_registers (ins
, sregs
);
704 } else if (MONO_IS_STORE_MEMBASE (ins
) && ins
->dreg
== dreg
) {
706 } else if (MONO_IS_PHI (ins
)) {
707 for (i
= ins
->inst_phi_args
[0]; i
> 0; i
--) {
708 int sreg
= ins
->inst_phi_args
[i
];
709 if (sreg
== var
->dreg
)
713 ins
->inst_phi_args
[i
] = sreg1
;
716 g_assert_not_reached ();
718 record_use (cfg
, var2
, u
->bb
, ins
);
728 if (cfg
->verbose_level
>= 4) {
731 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
)
732 mono_print_bb (bb
, "AFTER SSA COPYPROP");
737 evaluate_ins (MonoCompile
*cfg
, MonoInst
*ins
, MonoInst
**res
, MonoInst
**carray
)
739 MonoInst
*args
[MONO_MAX_SRC_REGS
];
740 int rs
[MONO_MAX_SRC_REGS
];
742 gboolean const_args
= TRUE
;
743 const char *spec
= INS_INFO (ins
->opcode
);
745 int sregs
[MONO_MAX_SRC_REGS
];
747 /* Short-circuit this */
748 if (ins
->opcode
== OP_ICONST
) {
753 if (ins
->opcode
== OP_NOP
)
756 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
757 for (i
= 0; i
< MONO_MAX_SRC_REGS
; ++i
)
759 for (i
= 0; i
< num_sregs
; ++i
) {
760 MonoInst
*var
= get_vreg_to_inst (cfg
, sregs
[i
]);
763 args
[i
] = carray
[sregs
[i
]];
766 else if (var
&& !(var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
)))
767 rs
[i
] = MONO_VARINFO (cfg
, var
->inst_c0
)->cpstate
;
774 if (num_sregs
> 0 && const_args
) {
775 g_assert (num_sregs
<= 2);
776 if ((spec
[MONO_INST_DEST
] != ' ') && carray
[ins
->dreg
]) {
778 *res
= carray
[ins
->dreg
];
781 c0
= mono_constant_fold_ins (cfg
, ins
, args
[0], args
[1], FALSE
);
783 if (G_UNLIKELY (cfg
->verbose_level
> 1)) {
784 printf ("\t cfold -> ");
791 /* Can't cfold this ins */
797 for (i
= 0; i
< num_sregs
; ++i
) {
805 change_varstate (MonoCompile
*cfg
, GList
**cvars
, MonoMethodVar
*info
, int state
, MonoInst
*c0
, MonoInst
**carray
)
807 if (info
->cpstate
>= state
)
810 info
->cpstate
= state
;
812 if (G_UNLIKELY (cfg
->verbose_level
> 1))
813 printf ("\tState of R%d set to %d\n", cfg
->varinfo
[info
->idx
]->dreg
, info
->cpstate
);
818 carray
[cfg
->varinfo
[info
->idx
]->dreg
] = c0
;
820 if (!g_list_find (*cvars
, info
)) {
821 *cvars
= g_list_prepend (*cvars
, info
);
826 add_cprop_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
, GList
**bblist
)
828 if (G_UNLIKELY (cfg
->verbose_level
> 1))
829 printf ("\tAdd BB%d to worklist\n", bb
->block_num
);
831 if (!(bb
->flags
& BB_REACHABLE
)) {
832 bb
->flags
|= BB_REACHABLE
;
833 *bblist
= g_list_prepend (*bblist
, bb
);
838 visit_inst (MonoCompile
*cfg
, MonoBasicBlock
*bb
, MonoInst
*ins
, GList
**cvars
, GList
**bblist
, MonoInst
**carray
)
840 const char *spec
= INS_INFO (ins
->opcode
);
842 if (ins
->opcode
== OP_NOP
)
845 if (cfg
->verbose_level
> 1)
846 mono_print_ins (ins
);
848 /* FIXME: Support longs/floats */
849 /* FIXME: Work on vregs as well */
851 if (MONO_IS_PHI (ins
)) {
852 MonoMethodVar
*info
= MONO_VARINFO (cfg
, get_vreg_to_inst (cfg
, ins
->dreg
)->inst_c0
);
856 for (j
= 1; j
<= ins
->inst_phi_args
[0]; j
++) {
857 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->inst_phi_args
[j
]);
858 MonoMethodVar
*mv
= MONO_VARINFO (cfg
, var
->inst_c0
);
859 MonoInst
*src
= mv
->def
;
861 if (mv
->def_bb
&& !(mv
->def_bb
->flags
& BB_REACHABLE
))
864 if (!mv
->def
|| !src
|| mv
->cpstate
== 2) {
865 change_varstate (cfg
, cvars
, info
, 2, NULL
, carray
);
869 if (mv
->cpstate
== 0)
872 g_assert (carray
[var
->dreg
]);
875 c0
= carray
[var
->dreg
];
878 if (c0
->opcode
!= OP_ICONST
) {
879 change_varstate (cfg
, cvars
, info
, 2, NULL
, carray
);
883 if (carray
[var
->dreg
]->inst_c0
!= c0
->inst_c0
) {
884 change_varstate (cfg
, cvars
, info
, 2, NULL
, carray
);
889 if (c0
&& info
->cpstate
< 1) {
890 change_varstate (cfg
, cvars
, info
, 1, c0
, carray
);
892 g_assert (c0
->opcode
== OP_ICONST
);
895 else if (!MONO_IS_STORE_MEMBASE (ins
) && ((spec
[MONO_INST_SRC1
] != ' ') || (spec
[MONO_INST_SRC2
] != ' ') || (spec
[MONO_INST_DEST
] != ' '))) {
899 if (spec
[MONO_INST_DEST
] != ' ')
900 var
= get_vreg_to_inst (cfg
, ins
->dreg
);
905 state
= evaluate_ins (cfg
, ins
, &c0
, carray
);
907 if (var
&& !(var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
908 MonoMethodVar
*info
= MONO_VARINFO (cfg
, var
->inst_c0
);
910 if (info
->cpstate
< 2) {
912 change_varstate (cfg
, cvars
, info
, 1, c0
, carray
);
914 change_varstate (cfg
, cvars
, info
, 2, NULL
, carray
);
917 else if (!var
&& (ins
->dreg
!= -1)) {
919 * We don't record def-use information for local vregs since it would be
920 * expensive. Instead, we depend on the fact that all uses of the vreg are in
921 * the same bblock, so they will be examined after the definition.
922 * FIXME: This isn't true if the ins is visited through an SSA edge.
925 carray
[ins
->dreg
] = c0
;
927 if (carray
[ins
->dreg
]) {
929 * The state of the vreg changed from constant to non-constant
930 * -> need to rescan the whole bblock.
932 carray
[ins
->dreg
] = NULL
;
933 /* FIXME: Speed this up */
935 if (!g_list_find (*bblist
, bb
))
936 *bblist
= g_list_prepend (*bblist
, bb
);
941 if (MONO_IS_JUMP_TABLE (ins
)) {
943 MonoJumpInfoBBTable
*table
= MONO_JUMP_TABLE_FROM_INS (ins
);
945 if (!ins
->next
|| ins
->next
->opcode
!= OP_PADD
) {
946 /* The PADD was optimized away */
947 /* FIXME: handle this as well */
948 for (i
= 0; i
< table
->table_size
; i
++)
949 if (table
->table
[i
])
950 add_cprop_bb (cfg
, table
->table
[i
], bblist
);
954 g_assert (ins
->next
->opcode
== OP_PADD
);
955 g_assert (ins
->next
->sreg1
== ins
->dreg
);
957 if (carray
[ins
->next
->sreg2
]) {
958 #if SIZEOF_REGISTER == 8
959 int idx
= carray
[ins
->next
->sreg2
]->inst_c0
>> 3;
961 int idx
= carray
[ins
->next
->sreg2
]->inst_c0
>> 2;
963 if ((idx
< 0) || (idx
>= table
->table_size
))
964 /* Out-of-range, no branch is executed */
967 if (table
->table
[idx
])
968 add_cprop_bb (cfg
, table
->table
[idx
], bblist
);
971 for (i
= 0; i
< table
->table_size
; i
++)
972 if (table
->table
[i
])
973 add_cprop_bb (cfg
, table
->table
[i
], bblist
);
977 if (ins
->opcode
== OP_SWITCH
) {
979 MonoJumpInfoBBTable
*table
= ins
->inst_p0
;
981 for (i
= 0; i
< table
->table_size
; i
++)
982 if (table
->table
[i
])
983 add_cprop_bb (cfg
, table
->table
[i
], bblist
);
986 /* Handle COMPARE+BRCOND pairs */
987 if (ins
->next
&& MONO_IS_COND_BRANCH_OP (ins
->next
)) {
989 g_assert (c0
->opcode
== OP_ICONST
);
992 ins
->next
->flags
|= MONO_INST_CFOLD_TAKEN
;
994 ins
->next
->flags
|= MONO_INST_CFOLD_NOT_TAKEN
;
997 ins
->next
->flags
&= ~(MONO_INST_CFOLD_TAKEN
| MONO_INST_CFOLD_NOT_TAKEN
);
1000 visit_inst (cfg
, bb
, ins
->next
, cvars
, bblist
, carray
);
1002 } else if (ins
->opcode
== OP_BR
) {
1003 add_cprop_bb (cfg
, ins
->inst_target_bb
, bblist
);
1004 } else if (MONO_IS_COND_BRANCH_OP (ins
)) {
1005 if (ins
->flags
& MONO_INST_CFOLD_TAKEN
) {
1006 add_cprop_bb (cfg
, ins
->inst_true_bb
, bblist
);
1007 } else if (ins
->flags
& MONO_INST_CFOLD_NOT_TAKEN
) {
1008 if (ins
->inst_false_bb
)
1009 add_cprop_bb (cfg
, ins
->inst_false_bb
, bblist
);
1011 add_cprop_bb (cfg
, ins
->inst_true_bb
, bblist
);
1012 if (ins
->inst_false_bb
)
1013 add_cprop_bb (cfg
, ins
->inst_false_bb
, bblist
);
1021 * Replace INS with its constant value, if it exists
1024 fold_ins (MonoCompile
*cfg
, MonoBasicBlock
*bb
, MonoInst
*ins
, MonoInst
**carray
)
1026 const char *spec
= INS_INFO (ins
->opcode
);
1028 int num_sregs
= mono_inst_get_num_src_registers (ins
);
1030 if ((ins
->opcode
!= OP_NOP
) && (ins
->dreg
!= -1) && !MONO_IS_STORE_MEMBASE (ins
)) {
1031 if (carray
[ins
->dreg
] && (spec
[MONO_INST_DEST
] == 'i') && (ins
->dreg
>= MONO_MAX_IREGS
)) {
1032 /* Perform constant folding */
1034 g_assert (carray
[ins
->dreg
]->opcode
== OP_ICONST
);
1035 ins
->opcode
= OP_ICONST
;
1036 ins
->inst_c0
= carray
[ins
->dreg
]->inst_c0
;
1037 MONO_INST_NULLIFY_SREGS (ins
);
1038 } else if (num_sregs
== 2 && carray
[ins
->sreg2
]) {
1039 /* Perform op->op_imm conversion */
1040 opcode2
= mono_op_to_op_imm (ins
->opcode
);
1041 if (opcode2
!= -1) {
1042 ins
->opcode
= opcode2
;
1043 ins
->inst_imm
= carray
[ins
->sreg2
]->inst_c0
;
1046 if ((opcode2
== OP_VOIDCALL
) || (opcode2
== OP_CALL
) || (opcode2
== OP_LCALL
) || (opcode2
== OP_FCALL
))
1047 ((MonoCallInst
*)ins
)->fptr
= (gpointer
)ins
->inst_imm
;
1050 /* FIXME: Handle 3 op insns */
1053 if (MONO_IS_JUMP_TABLE (ins
)) {
1055 MonoJumpInfoBBTable
*table
= MONO_JUMP_TABLE_FROM_INS (ins
);
1057 if (!ins
->next
|| ins
->next
->opcode
!= OP_PADD
) {
1058 /* The PADD was optimized away */
1059 /* FIXME: handle this as well */
1063 g_assert (ins
->next
->opcode
== OP_PADD
);
1064 g_assert (ins
->next
->sreg1
== ins
->dreg
);
1065 g_assert (ins
->next
->next
->opcode
== OP_LOAD_MEMBASE
);
1067 if (carray
[ins
->next
->sreg2
]) {
1068 /* Convert to a simple branch */
1069 #if SIZEOF_REGISTER == 8
1070 int idx
= carray
[ins
->next
->sreg2
]->inst_c0
>> 3;
1072 int idx
= carray
[ins
->next
->sreg2
]->inst_c0
>> 2;
1075 if (!((idx
>= 0) && (idx
< table
->table_size
))) {
1076 /* Out of range, eliminate the whole switch */
1077 for (i
= 0; i
< table
->table_size
; ++i
) {
1078 remove_bb_from_phis (cfg
, bb
, table
->table
[i
]);
1079 mono_unlink_bblock (cfg
, bb
, table
->table
[i
]);
1083 NULLIFY_INS (ins
->next
);
1084 NULLIFY_INS (ins
->next
->next
);
1085 if (ins
->next
->next
->next
)
1086 NULLIFY_INS (ins
->next
->next
->next
);
1091 if (!ins
->next
->next
->next
|| ins
->next
->next
->next
->opcode
!= OP_BR_REG
) {
1092 /* A one-way switch which got optimized away */
1093 if (G_UNLIKELY (cfg
->verbose_level
> 1)) {
1094 printf ("\tNo cfold on ");
1095 mono_print_ins (ins
);
1100 if (G_UNLIKELY (cfg
->verbose_level
> 1)) {
1101 printf ("\tcfold on ");
1102 mono_print_ins (ins
);
1105 /* Unlink target bblocks */
1106 for (i
= 0; i
< table
->table_size
; ++i
) {
1108 remove_bb_from_phis (cfg
, bb
, table
->table
[i
]);
1109 mono_unlink_bblock (cfg
, bb
, table
->table
[i
]);
1113 /* Change the OP_BR_REG to a simple branch */
1114 ins
->next
->next
->next
->opcode
= OP_BR
;
1115 ins
->next
->next
->next
->inst_target_bb
= table
->table
[idx
];
1116 ins
->next
->next
->next
->sreg1
= -1;
1118 /* Nullify the other instructions */
1120 NULLIFY_INS (ins
->next
);
1121 NULLIFY_INS (ins
->next
->next
);
1125 else if (MONO_IS_COND_BRANCH_OP (ins
)) {
1126 if (ins
->flags
& MONO_INST_CFOLD_TAKEN
) {
1127 remove_bb_from_phis (cfg
, bb
, ins
->inst_false_bb
);
1128 mono_unlink_bblock (cfg
, bb
, ins
->inst_false_bb
);
1129 ins
->opcode
= OP_BR
;
1130 ins
->inst_target_bb
= ins
->inst_true_bb
;
1131 } else if (ins
->flags
& MONO_INST_CFOLD_NOT_TAKEN
) {
1132 remove_bb_from_phis (cfg
, bb
, ins
->inst_true_bb
);
1133 mono_unlink_bblock (cfg
, bb
, ins
->inst_true_bb
);
1134 ins
->opcode
= OP_BR
;
1135 ins
->inst_target_bb
= ins
->inst_false_bb
;
1141 mono_ssa_cprop (MonoCompile
*cfg
)
1145 GList
*bblock_list
, *cvars
;
1148 //printf ("SIMPLE OPTS BB%d %s\n", bb->block_num, mono_method_full_name (cfg->method, TRUE));
1150 carray
= g_new0 (MonoInst
*, cfg
->next_vreg
);
1152 if (!(cfg
->comp_done
& MONO_COMP_SSA_DEF_USE
))
1153 mono_ssa_create_def_use (cfg
);
1155 bblock_list
= g_list_prepend (NULL
, cfg
->bb_entry
);
1156 cfg
->bb_entry
->flags
|= BB_REACHABLE
;
1158 memset (carray
, 0, sizeof (MonoInst
*) * cfg
->num_varinfo
);
1160 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
1161 MonoMethodVar
*info
= MONO_VARINFO (cfg
, i
);
1166 for (bb
= cfg
->bb_entry
->next_bb
; bb
; bb
= bb
->next_bb
) {
1168 * FIXME: This should be bb->flags & BB_FLAG_EXCEPTION_HANDLER, but
1169 * that would still allow unreachable try's to be removed.
1172 add_cprop_bb (cfg
, bb
, &bblock_list
);
1177 while (bblock_list
) {
1180 bb
= (MonoBasicBlock
*)bblock_list
->data
;
1182 bblock_list
= g_list_delete_link (bblock_list
, bblock_list
);
1184 g_assert (bb
->flags
& BB_REACHABLE
);
1187 * Some bblocks are linked to 2 others even through they fall through to the
1190 if (!(bb
->last_ins
&& MONO_IS_BRANCH_OP (bb
->last_ins
))) {
1191 for (i
= 0; i
< bb
->out_count
; ++i
)
1192 add_cprop_bb (cfg
, bb
->out_bb
[i
], &bblock_list
);
1195 if (cfg
->verbose_level
> 1)
1196 printf ("\nSSA CONSPROP BB%d:\n", bb
->block_num
);
1198 for (inst
= bb
->code
; inst
; inst
= inst
->next
) {
1199 visit_inst (cfg
, bb
, inst
, &cvars
, &bblock_list
, carray
);
1203 MonoMethodVar
*info
= (MonoMethodVar
*)cvars
->data
;
1204 cvars
= g_list_delete_link (cvars
, cvars
);
1206 for (tmp
= info
->uses
; tmp
; tmp
= tmp
->next
) {
1207 MonoVarUsageInfo
*ui
= (MonoVarUsageInfo
*)tmp
->data
;
1208 if (!(ui
->bb
->flags
& BB_REACHABLE
))
1210 visit_inst (cfg
, ui
->bb
, ui
->inst
, &cvars
, &bblock_list
, carray
);
1215 for (bb
= cfg
->bb_entry
->next_bb
; bb
; bb
= bb
->next_bb
) {
1217 for (inst
= bb
->code
; inst
; inst
= inst
->next
) {
1218 fold_ins (cfg
, bb
, inst
, carray
);
1224 cfg
->comp_done
|= MONO_COMP_REACHABILITY
;
1226 /* fixme: we should update usage infos during cprop, instead of computing it again */
1227 cfg
->comp_done
&= ~MONO_COMP_SSA_DEF_USE
;
1228 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
1229 MonoMethodVar
*info
= MONO_VARINFO (cfg
, i
);
1236 add_to_dce_worklist (MonoCompile
*cfg
, MonoMethodVar
*var
, MonoMethodVar
*use
, GList
**wl
)
1240 *wl
= g_list_prepend_mempool (cfg
->mempool
, *wl
, use
);
1242 for (tmp
= use
->uses
; tmp
; tmp
= tmp
->next
) {
1243 MonoVarUsageInfo
*ui
= (MonoVarUsageInfo
*)tmp
->data
;
1244 if (ui
->inst
== var
->def
) {
1245 /* from the mempool */
1246 use
->uses
= g_list_remove_link (use
->uses
, tmp
);
1253 mono_ssa_deadce (MonoCompile
*cfg
)
1258 g_assert (cfg
->comp_done
& MONO_COMP_SSA
);
1260 //printf ("DEADCE %s\n", mono_method_full_name (cfg->method, TRUE));
1262 if (!(cfg
->comp_done
& MONO_COMP_SSA_DEF_USE
))
1263 mono_ssa_create_def_use (cfg
);
1265 mono_ssa_copyprop (cfg
);
1268 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
1269 MonoMethodVar
*info
= MONO_VARINFO (cfg
, i
);
1270 work_list
= g_list_prepend_mempool (cfg
->mempool
, work_list
, info
);
1274 MonoMethodVar
*info
= (MonoMethodVar
*)work_list
->data
;
1275 work_list
= g_list_remove_link (work_list
, work_list
);
1278 * The second part of the condition happens often when PHI nodes have their dreg
1279 * as one of their arguments due to the fact that we use the original vars.
1281 if (info
->def
&& (!info
->uses
|| ((info
->uses
->next
== NULL
) && (((MonoVarUsageInfo
*)info
->uses
->data
)->inst
== info
->def
)))) {
1282 MonoInst
*def
= info
->def
;
1284 /* Eliminating FMOVE could screw up the fp stack */
1285 if (MONO_IS_MOVE (def
) && (!MONO_ARCH_USE_FPSTACK
|| (def
->opcode
!= OP_FMOVE
))) {
1286 MonoInst
*src_var
= get_vreg_to_inst (cfg
, def
->sreg1
);
1287 if (src_var
&& !(src_var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
)))
1288 add_to_dce_worklist (cfg
, info
, MONO_VARINFO (cfg
, src_var
->inst_c0
), &work_list
);
1289 def
->opcode
= OP_NOP
;
1290 def
->dreg
= def
->sreg1
= def
->sreg2
= -1;
1292 } else if ((def
->opcode
== OP_ICONST
) || (def
->opcode
== OP_I8CONST
) || MONO_IS_ZERO (def
)) {
1293 def
->opcode
= OP_NOP
;
1294 def
->dreg
= def
->sreg1
= def
->sreg2
= -1;
1296 } else if (MONO_IS_PHI (def
)) {
1298 for (j
= def
->inst_phi_args
[0]; j
> 0; j
--) {
1299 MonoMethodVar
*u
= MONO_VARINFO (cfg
, get_vreg_to_inst (cfg
, def
->inst_phi_args
[j
])->inst_c0
);
1300 add_to_dce_worklist (cfg
, info
, u
, &work_list
);
1302 def
->opcode
= OP_NOP
;
1303 def
->dreg
= def
->sreg1
= def
->sreg2
= -1;
1306 else if (def
->opcode
== OP_NOP
) {
1309 //mono_print_ins (def);
1317 mono_ssa_strength_reduction (MonoCompile
*cfg
)
1322 g_assert (cfg
->comp_done
& MONO_COMP_SSA
);
1323 g_assert (cfg
->comp_done
& MONO_COMP_LOOPS
);
1324 g_assert (cfg
->comp_done
& MONO_COMP_SSA_DEF_USE
);
1326 for (bb
= cfg
->bb_entry
->next_bb
; bb
; bb
= bb
->next_bb
) {
1327 GList
*lp
= bb
->loop_blocks
;
1330 MonoBasicBlock
*h
= (MonoBasicBlock
*)lp
->data
;
1332 /* we only consider loops with 2 in bblocks */
1333 if (!h
->in_count
== 2)
1336 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
1337 MonoMethodVar
*info
= MONO_VARINFO (cfg
, i
);
1339 if (info
->def
&& info
->def
->ssa_op
== MONO_SSA_STORE
&&
1340 info
->def
->inst_i0
->opcode
== OP_LOCAL
&& g_list_find (lp
, info
->def_bb
)) {
1341 MonoInst
*v
= info
->def
->inst_i1
;
1344 printf ("FOUND %d in %s\n", info
->idx
, mono_method_full_name (cfg
->method
, TRUE
));
1352 #endif /* DISABLE_JIT */