2 * local-propagation.c: Local constant, copy and tree propagation.
4 * To make some sense of the tree mover, read mono/docs/tree-mover.txt
7 * Paolo Molaro (lupus@ximian.com)
8 * Dietmar Maurer (dietmar@ximian.com)
9 * Massimiliano Mantione (massi@ximian.com)
11 * (C) 2006 Novell, Inc. http://www.novell.com
21 #include <mono/metadata/debug-helpers.h>
22 #include <mono/metadata/mempool.h>
23 #include <mono/metadata/opcodes.h>
27 #ifndef MONO_ARCH_IS_OP_MEMBASE
28 #define MONO_ARCH_IS_OP_MEMBASE(opcode) FALSE
31 static inline MonoBitSet
*
32 mono_bitset_mp_new_noinit (MonoMemPool
*mp
, guint32 max_size
)
34 int size
= mono_bitset_alloc_size (max_size
, 0);
37 mem
= mono_mempool_alloc (mp
, size
);
38 return mono_bitset_mem_new (mem
, max_size
, MONO_BITSET_DONT_FREE
);
44 * A combined local copy and constant propagation pass.
47 mono_local_cprop (MonoCompile
*cfg
)
57 defs
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * (cfg
->next_vreg
+ 1));
58 def_index
= mono_mempool_alloc (cfg
->mempool
, sizeof (guint32
) * (cfg
->next_vreg
+ 1));
60 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
65 /* Manually init the defs entries used by the bblock */
66 MONO_BB_FOR_EACH_INS (bb
, ins
) {
67 int sregs
[MONO_MAX_SRC_REGS
];
70 if ((ins
->dreg
!= -1) && (ins
->dreg
< max
)) {
71 defs
[ins
->dreg
] = NULL
;
72 #if SIZEOF_REGISTER == 4
73 defs
[ins
->dreg
+ 1] = NULL
;
77 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
78 for (i
= 0; i
< num_sregs
; ++i
) {
82 #if SIZEOF_REGISTER == 4
83 defs
[sreg
+ 1] = NULL
;
91 MONO_BB_FOR_EACH_INS (bb
, ins
) {
92 const char *spec
= INS_INFO (ins
->opcode
);
93 int regtype
, srcindex
, sreg
;
95 int sregs
[MONO_MAX_SRC_REGS
];
97 if (ins
->opcode
== OP_NOP
) {
98 MONO_DELETE_INS (bb
, ins
);
102 g_assert (ins
->opcode
> MONO_CEE_LAST
);
104 /* FIXME: Optimize this */
105 if (ins
->opcode
== OP_LDADDR
) {
106 MonoInst
*var
= ins
->inst_p0
;
108 defs
[var
->dreg
] = NULL
;
110 if (!MONO_TYPE_ISSTRUCT (var->inst_vtype))
115 if (MONO_IS_STORE_MEMBASE (ins
)) {
119 if ((regtype
== 'i') && (sreg
!= -1) && defs
[sreg
]) {
120 MonoInst
*def
= defs
[sreg
];
122 if ((def
->opcode
== OP_MOVE
) && (!defs
[def
->sreg1
] || (def_index
[def
->sreg1
] < def_index
[sreg
])) && !vreg_is_volatile (cfg
, def
->sreg1
)) {
123 int vreg
= def
->sreg1
;
124 if (cfg
->verbose_level
> 2) printf ("CCOPY: R%d -> R%d\n", sreg
, vreg
);
130 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
131 for (srcindex
= 0; srcindex
< num_sregs
; ++srcindex
) {
135 nsregs
= mono_inst_get_src_registers (ins
, sregs
);
137 regtype
= spec
[MONO_INST_SRC1
+ srcindex
];
138 sreg
= sregs
[srcindex
];
140 if ((regtype
== ' ') || (sreg
== -1) || (!defs
[sreg
]))
145 /* Copy propagation */
147 * The first check makes sure the source of the copy did not change since
149 * The second check avoids volatile variables.
150 * The third check avoids copy propagating local vregs through a call,
151 * since the lvreg will be spilled
152 * The fourth check avoids copy propagating a vreg in cases where
153 * it would be eliminated anyway by reverse copy propagation later,
154 * because propagating it would create another use for it, thus making
155 * it impossible to use reverse copy propagation.
157 /* Enabling this for floats trips up the fp stack */
159 * Enabling this for floats on amd64 seems to cause a failure in
160 * basic-math.cs, most likely because it gets rid of some r8->r4
163 if (MONO_IS_MOVE (def
) &&
164 (!defs
[def
->sreg1
] || (def_index
[def
->sreg1
] < def_index
[sreg
])) &&
165 !vreg_is_volatile (cfg
, def
->sreg1
) &&
166 /* This avoids propagating local vregs across calls */
167 ((get_vreg_to_inst (cfg
, def
->sreg1
) || !defs
[def
->sreg1
] || (def_index
[def
->sreg1
] >= last_call_index
) || (def
->opcode
== OP_VMOVE
))) &&
168 !(defs
[def
->sreg1
] && defs
[def
->sreg1
]->next
== def
) &&
169 (!MONO_ARCH_USE_FPSTACK
|| (def
->opcode
!= OP_FMOVE
)) &&
170 (def
->opcode
!= OP_FMOVE
)) {
171 int vreg
= def
->sreg1
;
173 if (cfg
->verbose_level
> 2) printf ("CCOPY/2: R%d -> R%d\n", sreg
, vreg
);
174 sregs
[srcindex
] = vreg
;
175 mono_inst_set_src_registers (ins
, sregs
);
177 /* Allow further iterations */
182 /* Constant propagation */
183 /* FIXME: Make is_inst_imm a macro */
184 /* FIXME: Make is_inst_imm take an opcode argument */
185 /* is_inst_imm is only needed for binops */
186 if ((((def
->opcode
== OP_ICONST
) || ((sizeof (gpointer
) == 8) && (def
->opcode
== OP_I8CONST
))) &&
187 (((srcindex
== 0) && (ins
->sreg2
== -1)) || mono_arch_is_inst_imm (def
->inst_c0
))) ||
188 (!MONO_ARCH_USE_FPSTACK
&& (def
->opcode
== OP_R8CONST
))) {
191 /* srcindex == 1 -> binop, ins->sreg2 == -1 -> unop */
192 if ((srcindex
== 1) && (ins
->sreg1
!= -1) && defs
[ins
->sreg1
] && (defs
[ins
->sreg1
]->opcode
== OP_ICONST
) && defs
[ins
->sreg2
]) {
193 /* Both arguments are constants, perform cfold */
194 mono_constant_fold_ins (cfg
, ins
, defs
[ins
->sreg1
], defs
[ins
->sreg2
], TRUE
);
195 } else if ((srcindex
== 0) && (ins
->sreg2
!= -1) && defs
[ins
->sreg2
]) {
196 /* Arg 1 is constant, swap arguments if possible */
197 int opcode
= ins
->opcode
;
198 mono_constant_fold_ins (cfg
, ins
, defs
[ins
->sreg1
], defs
[ins
->sreg2
], TRUE
);
199 if (ins
->opcode
!= opcode
) {
200 /* Allow further iterations */
204 } else if ((srcindex
== 0) && (ins
->sreg2
== -1)) {
205 /* Constant unop, perform cfold */
206 mono_constant_fold_ins (cfg
, ins
, defs
[ins
->sreg1
], NULL
, TRUE
);
209 opcode2
= mono_op_to_op_imm (ins
->opcode
);
210 if ((opcode2
!= -1) && mono_arch_is_inst_imm (def
->inst_c0
) && ((srcindex
== 1) || (ins
->sreg2
== -1))) {
211 ins
->opcode
= opcode2
;
212 if ((def
->opcode
== OP_I8CONST
) && (sizeof (gpointer
) == 4)) {
213 ins
->inst_ls_word
= def
->inst_ls_word
;
214 ins
->inst_ms_word
= def
->inst_ms_word
;
216 ins
->inst_imm
= def
->inst_c0
;
218 sregs
[srcindex
] = -1;
219 mono_inst_set_src_registers (ins
, sregs
);
221 if ((opcode2
== OP_VOIDCALL
) || (opcode2
== OP_CALL
) || (opcode2
== OP_LCALL
) || (opcode2
== OP_FCALL
))
222 ((MonoCallInst
*)ins
)->fptr
= (gpointer
)ins
->inst_imm
;
224 /* Allow further iterations */
230 #if defined(TARGET_X86) || defined(TARGET_AMD64)
231 if ((ins
->opcode
== OP_X86_LEA
) && (srcindex
== 1)) {
232 #if SIZEOF_REGISTER == 8
233 /* FIXME: Use OP_PADD_IMM when the new JIT is done */
234 ins
->opcode
= OP_LADD_IMM
;
236 ins
->opcode
= OP_ADD_IMM
;
238 ins
->inst_imm
+= def
->inst_c0
<< ins
->backend
.shift_amount
;
242 opcode2
= mono_load_membase_to_load_mem (ins
->opcode
);
243 if ((srcindex
== 0) && (opcode2
!= -1) && mono_arch_is_inst_imm (def
->inst_c0
)) {
244 ins
->opcode
= opcode2
;
245 ins
->inst_imm
= def
->inst_c0
+ ins
->inst_offset
;
250 else if (((def
->opcode
== OP_ADD_IMM
) || (def
->opcode
== OP_LADD_IMM
)) && (MONO_IS_LOAD_MEMBASE (ins
) || MONO_ARCH_IS_OP_MEMBASE (ins
->opcode
))) {
251 /* ADD_IMM is created by spill_global_vars */
253 * We have to guarantee that def->sreg1 haven't changed since def->dreg
254 * was defined. cfg->frame_reg is assumed to remain constant.
256 if ((def
->sreg1
== cfg
->frame_reg
) || ((def
->next
== ins
) && (def
->dreg
!= def
->sreg1
))) {
257 ins
->inst_basereg
= def
->sreg1
;
258 ins
->inst_offset
+= def
->inst_imm
;
260 } else if ((ins
->opcode
== OP_ISUB_IMM
) && (def
->opcode
== OP_IADD_IMM
) && (def
->next
== ins
) && (def
->dreg
!= def
->sreg1
)) {
261 ins
->sreg1
= def
->sreg1
;
262 ins
->inst_imm
-= def
->inst_imm
;
263 } else if ((ins
->opcode
== OP_IADD_IMM
) && (def
->opcode
== OP_ISUB_IMM
) && (def
->next
== ins
) && (def
->dreg
!= def
->sreg1
)) {
264 ins
->sreg1
= def
->sreg1
;
265 ins
->inst_imm
-= def
->inst_imm
;
266 } else if (ins
->opcode
== OP_STOREI1_MEMBASE_REG
&&
267 (def
->opcode
== OP_ICONV_TO_U1
|| def
->opcode
== OP_ICONV_TO_I1
|| def
->opcode
== OP_SEXT_I4
|| (SIZEOF_REGISTER
== 8 && def
->opcode
== OP_LCONV_TO_U1
)) &&
268 (!defs
[def
->sreg1
] || (def_index
[def
->sreg1
] < def_index
[sreg
]))) {
269 /* Avoid needless sign extension */
270 ins
->sreg1
= def
->sreg1
;
271 } else if (ins
->opcode
== OP_STOREI2_MEMBASE_REG
&&
272 (def
->opcode
== OP_ICONV_TO_U2
|| def
->opcode
== OP_ICONV_TO_I2
|| def
->opcode
== OP_SEXT_I4
|| (SIZEOF_REGISTER
== 8 && def
->opcode
== OP_LCONV_TO_I2
)) &&
273 (!defs
[def
->sreg1
] || (def_index
[def
->sreg1
] < def_index
[sreg
]))) {
274 /* Avoid needless sign extension */
275 ins
->sreg1
= def
->sreg1
;
279 /* Do strength reduction here */
280 /* FIXME: Add long/float */
281 switch (ins
->opcode
) {
284 if (ins
->dreg
== ins
->sreg1
) {
285 MONO_DELETE_INS (bb
, ins
);
286 spec
= INS_INFO (ins
->opcode
);
293 #if SIZEOF_REGISTER == 8
297 if (ins
->inst_imm
== 0) {
298 ins
->opcode
= OP_MOVE
;
299 spec
= INS_INFO (ins
->opcode
);
304 #if SIZEOF_REGISTER == 8
307 if (ins
->inst_imm
== 0) {
308 ins
->opcode
= (ins
->opcode
== OP_LMUL_IMM
) ? OP_I8CONST
: OP_ICONST
;
311 } else if (ins
->inst_imm
== 1) {
312 ins
->opcode
= OP_MOVE
;
313 } else if ((ins
->opcode
== OP_IMUL_IMM
) && (ins
->inst_imm
== -1)) {
314 ins
->opcode
= OP_INEG
;
315 } else if ((ins
->opcode
== OP_LMUL_IMM
) && (ins
->inst_imm
== -1)) {
316 ins
->opcode
= OP_LNEG
;
318 int power2
= mono_is_power_of_two (ins
->inst_imm
);
320 ins
->opcode
= (ins
->opcode
== OP_MUL_IMM
) ? OP_SHL_IMM
: ((ins
->opcode
== OP_LMUL_IMM
) ? OP_LSHL_IMM
: OP_ISHL_IMM
);
321 ins
->inst_imm
= power2
;
324 spec
= INS_INFO (ins
->opcode
);
327 case OP_IDIV_UN_IMM
: {
328 int c
= ins
->inst_imm
;
329 int power2
= mono_is_power_of_two (c
);
332 if (ins
->opcode
== OP_IREM_UN_IMM
) {
333 ins
->opcode
= OP_IAND_IMM
;
335 ins
->inst_imm
= (1 << power2
) - 1;
336 } else if (ins
->opcode
== OP_IDIV_UN_IMM
) {
337 ins
->opcode
= OP_ISHR_UN_IMM
;
339 ins
->inst_imm
= power2
;
342 spec
= INS_INFO (ins
->opcode
);
346 int c
= ins
->inst_imm
;
347 int power2
= mono_is_power_of_two (c
);
348 MonoInst
*tmp1
, *tmp2
, *tmp3
, *tmp4
;
350 /* FIXME: Move this elsewhere cause its hard to implement it here */
352 int r1
= mono_alloc_ireg (cfg
);
354 NEW_BIALU_IMM (cfg
, tmp1
, OP_ISHR_UN_IMM
, r1
, ins
->sreg1
, 31);
355 mono_bblock_insert_after_ins (bb
, ins
, tmp1
);
356 NEW_BIALU (cfg
, tmp2
, OP_IADD
, r1
, r1
, ins
->sreg1
);
357 mono_bblock_insert_after_ins (bb
, tmp1
, tmp2
);
358 NEW_BIALU_IMM (cfg
, tmp3
, OP_ISHR_IMM
, ins
->dreg
, r1
, 1);
359 mono_bblock_insert_after_ins (bb
, tmp2
, tmp3
);
363 // We allocated a new vreg, so need to restart
365 } else if (power2
> 0) {
366 int r1
= mono_alloc_ireg (cfg
);
368 NEW_BIALU_IMM (cfg
, tmp1
, OP_ISHR_IMM
, r1
, ins
->sreg1
, 31);
369 mono_bblock_insert_after_ins (bb
, ins
, tmp1
);
370 NEW_BIALU_IMM (cfg
, tmp2
, OP_ISHR_UN_IMM
, r1
, r1
, (32 - power2
));
371 mono_bblock_insert_after_ins (bb
, tmp1
, tmp2
);
372 NEW_BIALU (cfg
, tmp3
, OP_IADD
, r1
, r1
, ins
->sreg1
);
373 mono_bblock_insert_after_ins (bb
, tmp2
, tmp3
);
374 NEW_BIALU_IMM (cfg
, tmp4
, OP_ISHR_IMM
, ins
->dreg
, r1
, power2
);
375 mono_bblock_insert_after_ins (bb
, tmp3
, tmp4
);
379 // We allocated a new vreg, so need to restart
386 if (spec
[MONO_INST_DEST
] != ' ') {
387 MonoInst
*def
= defs
[ins
->dreg
];
389 if (def
&& (def
->opcode
== OP_ADD_IMM
) && (def
->sreg1
== cfg
->frame_reg
) && (MONO_IS_STORE_MEMBASE (ins
))) {
390 /* ADD_IMM is created by spill_global_vars */
391 /* cfg->frame_reg is assumed to remain constant */
392 ins
->inst_destbasereg
= def
->sreg1
;
393 ins
->inst_offset
+= def
->inst_imm
;
397 if ((spec
[MONO_INST_DEST
] != ' ') && !MONO_IS_STORE_MEMBASE (ins
) && !vreg_is_volatile (cfg
, ins
->dreg
)) {
398 defs
[ins
->dreg
] = ins
;
399 def_index
[ins
->dreg
] = ins_index
;
402 if (MONO_IS_CALL (ins
))
403 last_call_index
= ins_index
;
410 static inline gboolean
411 reg_is_softreg_no_fpstack (int reg
, const char spec
)
413 return (spec
== 'i' && reg
>= MONO_MAX_IREGS
)
414 || ((spec
== 'f' && reg
>= MONO_MAX_FREGS
) && !MONO_ARCH_USE_FPSTACK
)
415 #ifdef MONO_ARCH_SIMD_INTRINSICS
416 || (spec
== 'x' && reg
>= MONO_MAX_XREGS
)
421 static inline gboolean
422 reg_is_softreg (int reg
, const char spec
)
424 return (spec
== 'i' && reg
>= MONO_MAX_IREGS
)
425 || (spec
== 'f' && reg
>= MONO_MAX_FREGS
)
426 #ifdef MONO_ARCH_SIMD_INTRINSICS
427 || (spec
== 'x' && reg
>= MONO_MAX_XREGS
)
435 * Get rid of the dead assignments to local vregs like the ones created by the
439 mono_local_deadce (MonoCompile
*cfg
)
442 MonoInst
*ins
, *prev
;
443 MonoBitSet
*used
, *defined
;
445 //mono_print_code (cfg, "BEFORE LOCAL-DEADCE");
448 * Assignments to global vregs can't be eliminated so this pass must come
449 * after the handle_global_vregs () pass.
452 used
= mono_bitset_mp_new_noinit (cfg
->mempool
, cfg
->next_vreg
+ 1);
453 defined
= mono_bitset_mp_new_noinit (cfg
->mempool
, cfg
->next_vreg
+ 1);
455 /* First pass: collect liveness info */
456 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
457 /* Manually init the defs entries used by the bblock */
458 MONO_BB_FOR_EACH_INS (bb
, ins
) {
459 const char *spec
= INS_INFO (ins
->opcode
);
460 int sregs
[MONO_MAX_SRC_REGS
];
463 if (spec
[MONO_INST_DEST
] != ' ') {
464 mono_bitset_clear_fast (used
, ins
->dreg
);
465 mono_bitset_clear_fast (defined
, ins
->dreg
);
466 #if SIZEOF_REGISTER == 4
468 mono_bitset_clear_fast (used
, ins
->dreg
+ 1);
469 mono_bitset_clear_fast (defined
, ins
->dreg
+ 1);
472 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
473 for (i
= 0; i
< num_sregs
; ++i
) {
474 mono_bitset_clear_fast (used
, sregs
[i
]);
475 #if SIZEOF_REGISTER == 4
476 mono_bitset_clear_fast (used
, sregs
[i
] + 1);
482 * Make a reverse pass over the instruction list
484 MONO_BB_FOR_EACH_INS_REVERSE_SAFE (bb
, prev
, ins
) {
485 const char *spec
= INS_INFO (ins
->opcode
);
486 int sregs
[MONO_MAX_SRC_REGS
];
489 if (ins
->opcode
== OP_NOP
) {
490 MONO_DELETE_INS (bb
, ins
);
494 g_assert (ins
->opcode
> MONO_CEE_LAST
);
496 if (MONO_IS_NON_FP_MOVE (ins
) && ins
->prev
) {
501 while (def
->prev
&& (def
->opcode
== OP_NOP
))
503 spec2
= INS_INFO (def
->opcode
);
506 * Perform a limited kind of reverse copy propagation, i.e.
507 * transform B <- FOO; A <- B into A <- FOO
508 * This isn't copyprop, not deadce, but it can only be performed
509 * after handle_global_vregs () has run.
511 if (!get_vreg_to_inst (cfg
, ins
->sreg1
) && (spec2
[MONO_INST_DEST
] != ' ') && (def
->dreg
== ins
->sreg1
) && !mono_bitset_test_fast (used
, ins
->sreg1
) && !MONO_IS_STORE_MEMBASE (def
) && reg_is_softreg (ins
->sreg1
, spec
[MONO_INST_DEST
])) {
512 if (cfg
->verbose_level
> 2) {
513 printf ("\tReverse copyprop in BB%d on ", bb
->block_num
);
514 mono_print_ins (ins
);
517 def
->dreg
= ins
->dreg
;
518 MONO_DELETE_INS (bb
, ins
);
519 spec
= INS_INFO (ins
->opcode
);
523 /* Enabling this on x86 could screw up the fp stack */
524 if (reg_is_softreg_no_fpstack (ins
->dreg
, spec
[MONO_INST_DEST
])) {
526 * Assignments to global vregs can only be eliminated if there is another
527 * assignment to the same vreg later in the same bblock.
529 if (!mono_bitset_test_fast (used
, ins
->dreg
) &&
530 (!get_vreg_to_inst (cfg
, ins
->dreg
) || (!bb
->extended
&& !vreg_is_volatile (cfg
, ins
->dreg
) && mono_bitset_test_fast (defined
, ins
->dreg
))) &&
531 MONO_INS_HAS_NO_SIDE_EFFECT (ins
)) {
532 /* Happens with CMOV instructions */
533 if (ins
->prev
&& ins
->prev
->opcode
== OP_ICOMPARE_IMM
) {
534 MonoInst
*prev
= ins
->prev
;
536 * Can't use DELETE_INS since that would interfere with the
541 //printf ("DEADCE: "); mono_print_ins (ins);
542 MONO_DELETE_INS (bb
, ins
);
543 spec
= INS_INFO (ins
->opcode
);
546 if (spec
[MONO_INST_DEST
] != ' ')
547 mono_bitset_clear_fast (used
, ins
->dreg
);
550 if (spec
[MONO_INST_DEST
] != ' ')
551 mono_bitset_set_fast (defined
, ins
->dreg
);
552 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
553 for (i
= 0; i
< num_sregs
; ++i
)
554 mono_bitset_set_fast (used
, sregs
[i
]);
555 if (MONO_IS_STORE_MEMBASE (ins
))
556 mono_bitset_set_fast (used
, ins
->dreg
);
558 if (MONO_IS_CALL (ins
)) {
559 MonoCallInst
*call
= (MonoCallInst
*)ins
;
562 if (call
->out_ireg_args
) {
563 for (l
= call
->out_ireg_args
; l
; l
= l
->next
) {
564 guint32 regpair
, reg
;
566 regpair
= (guint32
)(gssize
)(l
->data
);
567 reg
= regpair
& 0xffffff;
569 mono_bitset_set_fast (used
, reg
);
573 if (call
->out_freg_args
) {
574 for (l
= call
->out_freg_args
; l
; l
= l
->next
) {
575 guint32 regpair
, reg
;
577 regpair
= (guint32
)(gssize
)(l
->data
);
578 reg
= regpair
& 0xffffff;
580 mono_bitset_set_fast (used
, reg
);
587 //mono_print_code (cfg, "AFTER LOCAL-DEADCE");