2 * aliasing.c: Alias Analysis
5 * Massimiliano Mantione (massi@ximian.com)
7 * (C) 2005 Novell, Inc. http://www.novell.com
12 #include <mono/metadata/debug-helpers.h>
13 #include <mono/metadata/mempool.h>
14 #include <mono/metadata/opcodes.h>
18 #define MONO_APPLY_DEADCE_TO_SINGLE_METHOD 0
19 #define DEBUG_DEADCE 0
21 #define DEBUG_ALIAS_ANALYSIS 0
23 #define TRACE_ALIAS_ANALYSIS (info->cfg->verbose_level > 2)
24 #define DUMP_ALIAS_ANALYSIS (info->cfg->verbose_level > 4)
25 #define FOLLOW_ALIAS_ANALYSIS (info->cfg->verbose_level > 5)
27 static const char *mono_aliasing_value_names
[] = {
35 static const char *mono_stack_type_names
[] = {
47 #define NO_VARIABLE_INDEX MONO_ALIASING_INVALID_VARIABLE_INDEX
50 #define OP_IS_OUTARG(op) (((op)==OP_OUTARG)||((op)==OP_OUTARG_REG)||((op)==OP_OUTARG_IMM)||((op)==OP_OUTARG_R4)||((op)==OP_OUTARG_R8)||((op)==OP_OUTARG_VT))
51 #define OP_IS_CALL(op) (((op)==CEE_CALLI)||((op)==CEE_CALL)||((op)==CEE_CALLVIRT)||(((op)>=OP_VOIDCALL)&&((op)<=OP_CALL_MEMBASE)))
52 #define OP_IS_STORE(op) (((op)==CEE_STIND_REF)||((op)==CEE_STIND_I1)||((op)==CEE_STIND_I2)||((op)==CEE_STIND_I4)||((op)==CEE_STIND_I8)||((op)==CEE_STIND_R4)||((op)==CEE_STIND_R8)||((op)==CEE_STIND_I))
53 #define OP_IS_LOAD(op) (((op)==CEE_LDIND_REF)||((op)==CEE_LDIND_I1)||((op)==CEE_LDIND_I2)||((op)==CEE_LDIND_I4)||((op)==CEE_LDIND_U1)||((op)==CEE_LDIND_U2)||((op)==CEE_LDIND_U4)||((op)==CEE_LDIND_I8)||((op)==CEE_LDIND_R4)||((op)==CEE_LDIND_R8)||((op)==CEE_LDIND_I))
54 #define OP_IS_CONST(op) (((op)==OP_ICONST)||((op)==OP_I8CONST)||((op)==OP_R4CONST)||((op)==OP_R8CONST)||((op)==OP_AOTCONST))
55 #define OP_IS_ICONV(op) (((op)==CEE_CONV_I4)||((op)==CEE_CONV_U4)||((op)==CEE_CONV_I8)||((op)==CEE_CONV_U8)||\
56 ((op)==CEE_CONV_OVF_I4_UN)||((op)==CEE_CONV_OVF_I8_UN)||((op)==CEE_CONV_OVF_U4_UN)||((op)==CEE_CONV_OVF_U8_UN)||\
57 ((op)==CEE_CONV_OVF_I4)||((op)==CEE_CONV_OVF_U4)||((op)==CEE_CONV_OVF_I8)||((op)==CEE_CONV_OVF_U8)||\
58 ((op)==OP_LCONV_TO_I8)||((op)==OP_LCONV_TO_OVF_I8)||((op)==OP_LCONV_TO_OVF_I8_UN)||\
59 ((op)==OP_LCONV_TO_U8)||((op)==OP_LCONV_TO_OVF_U8)||((op)==OP_LCONV_TO_OVF_U8_UN))
60 #define OP_IS_PCONV(op) (((op)==CEE_CONV_OVF_I_UN)||((op)==CEE_CONV_OVF_U_UN)||\
61 ((op)==CEE_CONV_I)||((op)==CEE_CONV_U)||\
62 ((op)==CEE_CONV_OVF_I)||((op)==CEE_CONV_OVF_U)||\
63 ((op)==OP_LCONV_TO_I)||((op)==OP_LCONV_TO_OVF_I)||((op)==OP_LCONV_TO_OVF_I_UN)||\
64 ((op)==OP_LCONV_TO_U)||((op)==OP_LCONV_TO_OVF_U)||((op)==OP_LCONV_TO_OVF_U_UN))
65 #define LOAD_OF_LOCAL_GIVES_POINTER(load,local) ((local->opcode == OP_LOCAL) && (((load)->type == STACK_MP) || ((load)->type == STACK_PTR) || ((local)->inst_vtype->type == MONO_TYPE_PTR)))
69 * A struct representing the context of the traversal of a MonoInst tree.
70 * Used so that "update_aliasing_information_on_inst" can understand what
71 * its caller was doing, and expecially where the current value is going
72 * to be stored (if it is an alias, we must track it).
74 typedef struct MonoAliasingInformationContext
{
77 MonoAliasValue subtree_aliases
[2];
79 struct MonoAliasingInformationContext
*father
;
80 } MonoAliasingInformationContext
;
84 print_alias_value (MonoAliasValue
*alias_value
) {
85 printf ("[%s", mono_aliasing_value_names
[alias_value
->type
]);
86 if ((alias_value
->type
== MONO_ALIASING_TYPE_LOCAL
) || (alias_value
->type
== MONO_ALIASING_TYPE_LOCAL_FIELD
)) {
87 printf (":%d]", alias_value
->variable_index
);
94 print_ssaop_value (int ssaop_value
) {
96 if (ssaop_value
& MONO_SSA_ADDRESS_TAKEN
) printf ("I"); else printf (".");
97 if (ssaop_value
& MONO_SSA_LOAD
) printf ("R"); else printf (".");
98 if (ssaop_value
& MONO_SSA_STORE
) printf ("W"); else printf (".");
103 print_aliasing_context (MonoAliasingInformationContext
*context
) {
104 printf ("CONTEXT: left ");
105 print_alias_value (&(context
->subtree_aliases
[0]));
107 print_alias_value (&(context
->subtree_aliases
[1]));
108 if (context
->father
!= NULL
) {
109 printf (", father ");
110 print_alias_value (&(context
->father
->subtree_aliases
[context
->father
->current_subtree
]));
112 printf (", stack %s ", mono_stack_type_names
[context
->inst
->type
]);
113 if (context
->inst
->ssa_op
!= MONO_SSA_NOP
) {
114 print_ssaop_value (context
->inst
->ssa_op
);
118 mono_print_tree_nl (context
->inst
);
122 print_tree_node (MonoInst
*tree
) {
126 printf (mono_inst_name (tree
->opcode
));
128 if (OP_IS_OUTARG (tree
->opcode
)) {
129 printf ("[OUT:%ld]", (long)tree
->inst_c1
);
132 switch (tree
->opcode
) {
134 printf ("[%d]", (int)tree
->inst_c0
);
137 printf ("[%lld]", (long long)tree
->inst_l
);
140 printf ("[%f]", *(double*)tree
->inst_p0
);
143 printf ("[%f]", *(float*)tree
->inst_p0
);
147 printf ("[%d]", (int)tree
->inst_c0
);
150 if (tree
->inst_offset
< 0)
151 printf ("[-0x%x(%s)]", (int)(-tree
->inst_offset
), mono_arch_regname (tree
->inst_basereg
));
153 printf ("[0x%x(%s)]", (int)(tree
->inst_offset
), mono_arch_regname (tree
->inst_basereg
));
156 printf ("[%s]", mono_arch_regname (tree
->dreg
));
159 printf ("[%s]", tree
->inst_newa_class
->name
);
170 case OP_VOIDCALLVIRT
: {
171 MonoCallInst
*call
= (MonoCallInst
*)tree
;
173 printf ("[%s]", call
->method
->name
);
174 else if (call
->fptr
) {
175 MonoJitICallInfo
*info
= mono_find_jit_icall_by_addr (call
->fptr
);
177 printf ("[%s]", info
->name
);
179 printf ("[ARGS:%d]", call
->signature
->param_count
);
184 printf ("[%d (", (int)tree
->inst_c0
);
185 for (i
= 0; i
< tree
->inst_phi_args
[0]; i
++) {
188 printf ("%d", tree
->inst_phi_args
[i
+ 1]);
193 case OP_LOAD_MEMBASE
:
194 case OP_LOADI4_MEMBASE
:
195 case OP_LOADU4_MEMBASE
:
196 case OP_LOADU1_MEMBASE
:
197 case OP_LOADI1_MEMBASE
:
198 case OP_LOADU2_MEMBASE
:
199 case OP_LOADI2_MEMBASE
:
200 printf ("[%s] <- [%s + 0x%x]", mono_arch_regname (tree
->dreg
), mono_arch_regname (tree
->inst_basereg
), (int)tree
->inst_offset
);
203 case OP_CALL_HANDLER
:
204 printf ("[B%d]", tree
->inst_target_bb
->block_num
);
216 printf ("[B%dB%d]", tree
->inst_true_bb
->block_num
, tree
->inst_false_bb
->block_num
);
219 printf ("[%d]", (int)tree
->inst_i0
->inst_i0
->inst_c0
);
222 printf ("[%d]", (int)tree
->inst_i0
->inst_c0
);
230 print_variable_list (MonoLocalVariableList
* variables
) {
232 while (variables
!= NULL
) {
233 printf ("%d", variables
->variable_index
);
234 if (variables
->next
!= NULL
) {
237 variables
= variables
->next
;
243 print_used_aliases(MonoInst
*inst
, MonoLocalVariableList
* affected_variables
) {
244 if (inst
->ssa_op
!= MONO_SSA_NOP
) {
246 if (inst
->ssa_op
& MONO_SSA_ADDRESS_TAKEN
) printf ("I");
247 if (inst
->ssa_op
& MONO_SSA_LOAD
) printf ("R");
248 if (inst
->ssa_op
& MONO_SSA_STORE
) printf ("W");
249 if (inst
->ssa_op
!= MONO_SSA_ADDRESS_TAKEN
) {
250 print_variable_list (affected_variables
);
252 switch (inst
->inst_i0
->opcode
) {
255 printf ("{%ld}", (long)inst
->inst_i0
->inst_c0
);
270 print_tree_with_aliasing_information (MonoAliasingInformation
*info
, MonoInst
*tree
) {
272 MonoLocalVariableList
* affected_variables
;
275 printf ("NULL-INST");
279 arity
= mono_burg_arity
[tree
->opcode
];
281 print_tree_node (tree
);
283 if (OP_IS_CALL (tree
->opcode
) && arity
) {
289 print_tree_with_aliasing_information (info
, tree
->inst_i0
);
292 print_tree_with_aliasing_information (info
, tree
->inst_i1
);
297 affected_variables
= mono_aliasing_get_affected_variables_for_inst_traversing_code (info
, tree
);
298 print_used_aliases (tree
, affected_variables
);
302 print_code_with_aliasing_information (MonoAliasingInformation
*info
) {
303 char *name
= mono_method_full_name (info
->cfg
->method
, TRUE
);
306 printf ("ALIASING DATA START (METHOD %s)\n", name
);
307 printf ("ALIASED VARIABLES: ");
308 print_variable_list (info
->uncontrollably_aliased_variables
);
310 for (i
= 0; i
< info
->cfg
->num_bblocks
; i
++) {
311 MonoAliasingInformationInBB
*bb_info
= &(info
->bb
[i
]);
312 MonoAliasUsageInformation
*use
;
315 printf ("CODE FOR BB %d\n", bb_info
->bb
->block_num
);
316 mono_aliasing_initialize_code_traversal (info
, bb_info
->bb
);
317 for (inst
= bb_info
->bb
->code
; inst
!= NULL
; inst
= inst
->next
) {
318 print_tree_with_aliasing_information (info
, inst
);
322 printf ("USES FOR BB %d\n", bb_info
->bb
->block_num
);
323 for (use
= bb_info
->potential_alias_uses
; use
!= NULL
; use
= use
->next
) {
324 mono_print_tree (use
->inst
);
325 print_used_aliases (use
->inst
, use
->affected_variables
);
329 printf ("ALIASING DATA END (METHOD %s)\n", name
);
334 #define APPEND_USE(info,bb_info,use) do {\
336 if ((info)->next_interesting_inst != NULL) {\
337 (info)->next_interesting_inst->next = (use);\
339 (bb_info)->potential_alias_uses = (use);\
341 (info)->next_interesting_inst = (use);\
344 #define ADD_BAD_ALIAS(info,vi) do {\
345 if (FOLLOW_ALIAS_ANALYSIS) {\
346 printf ("ADDING BAD ALIAS FOR VARIABLE %d\n", vi);\
348 if (! ((info)->variable_is_uncontrollably_aliased [(vi)])) {\
349 MonoLocalVariableList *variable = mono_mempool_alloc ((info)->mempool, sizeof (MonoLocalVariableList));\
350 variable->variable_index = (vi);\
351 variable->next = (info)->uncontrollably_aliased_variables;\
352 (info)->uncontrollably_aliased_variables = variable;\
353 (info)->variable_is_uncontrollably_aliased [(vi)] = TRUE;\
357 #define ADD_ARGUMGENT(info,inst,alias) do {\
358 if ((info)->number_of_arguments == (info)->arguments_capacity) {\
359 MonoInst **new_arguments = mono_mempool_alloc ((info)->mempool, sizeof (MonoInst*) * ((info)->arguments_capacity * 2));\
360 MonoAliasValue *new_arguments_aliases = mono_mempool_alloc ((info)->mempool, sizeof (MonoAliasValue) * ((info)->arguments_capacity * 2));\
361 memcpy (new_arguments, (info)->arguments, sizeof (MonoInst*) * ((info)->arguments_capacity));\
362 memcpy (new_arguments_aliases, (info)->arguments_aliases, sizeof (MonoAliasValue) * ((info)->arguments_capacity));\
363 (info)->arguments = new_arguments;\
364 (info)->arguments_aliases = new_arguments_aliases;\
365 (info)->arguments_capacity = (info)->arguments_capacity * 2;\
367 (info)->arguments [(info)->number_of_arguments] = (inst);\
368 (info)->arguments_aliases [(info)->number_of_arguments] = (alias);\
369 (info)->number_of_arguments ++;\
372 #define ADD_UNIQUE_VARIABLE(info,list,vi) do {\
373 MonoLocalVariableList* target_element = (list);\
374 while ((target_element != NULL) && (target_element->variable_index != (vi))) {\
375 target_element = target_element->next;\
377 if (target_element == NULL) {\
378 target_element = mono_mempool_alloc ((info)->mempool, sizeof (MonoLocalVariableList));\
379 target_element->variable_index = (vi);\
380 target_element->next = (list);\
381 (list) = target_element;\
386 update_aliasing_information_on_inst (MonoAliasingInformation
*info
, MonoAliasingInformationInBB
*bb_info
, MonoInst
*inst
, MonoAliasingInformationContext
*father_context
) {
387 MonoAliasingInformationContext context
;
388 MonoAliasValue
*father_alias
;
391 context
.father
= father_context
;
392 if (father_context
!= NULL
) {
393 father_alias
= &(father_context
->subtree_aliases
[father_context
->current_subtree
]);
398 if (mono_burg_arity
[inst
->opcode
]) {
399 context
.current_subtree
= 0;
400 context
.subtree_aliases
[0].type
= MONO_ALIASING_TYPE_ANY
;
401 context
.subtree_aliases
[0].variable_index
= NO_VARIABLE_INDEX
;
402 update_aliasing_information_on_inst (info
, bb_info
, inst
->inst_i0
, &context
);
404 if (mono_burg_arity
[inst
->opcode
] > 1) {
405 context
.current_subtree
= 1;
406 context
.subtree_aliases
[1].type
= MONO_ALIASING_TYPE_ANY
;
407 context
.subtree_aliases
[1].variable_index
= NO_VARIABLE_INDEX
;
408 update_aliasing_information_on_inst (info
, bb_info
, inst
->inst_i1
, &context
);
410 context
.subtree_aliases
[1].type
= MONO_ALIASING_TYPE_NO_ALIAS
;
413 context
.subtree_aliases
[0].type
= MONO_ALIASING_TYPE_NO_ALIAS
;
414 context
.subtree_aliases
[1].type
= MONO_ALIASING_TYPE_NO_ALIAS
;
417 if (OP_IS_CONST (inst
->opcode
)) {
418 father_alias
->type
= MONO_ALIASING_TYPE_NO_ALIAS
;
419 } else if (inst
->ssa_op
== MONO_SSA_ADDRESS_TAKEN
) {
420 MonoInst
*local
= inst
->inst_i0
;
421 if ((local
->opcode
== OP_LOCAL
) || (local
->opcode
== OP_ARG
)) {
422 gssize variable_index
= local
->inst_c0
;
423 father_alias
->type
= MONO_ALIASING_TYPE_LOCAL
;
424 father_alias
->variable_index
= variable_index
;
425 } else if (local
->opcode
== OP_RETARG
) {
426 father_alias
->type
= MONO_ALIASING_TYPE_NO_ALIAS
;
428 father_alias
->type
= MONO_ALIASING_TYPE_ANY
;
430 } else if (inst
->ssa_op
== MONO_SSA_LOAD
) {
431 MonoInst
*local
= inst
->inst_i0
;
433 if (LOAD_OF_LOCAL_GIVES_POINTER (inst
,local
)) {
434 father_alias
->type
= MONO_ALIASING_TYPE_ANY
;
436 father_alias
->type
= MONO_ALIASING_TYPE_NO_ALIAS
;
438 } else if (OP_IS_LOAD (inst
->opcode
) || (inst
->opcode
== CEE_LDOBJ
)) {
439 MonoInst
*address
= inst
->inst_i0
;
440 MonoLocalVariableList
*affected_variables
= NULL
;
442 if ((address
->opcode
== OP_LOCAL
) || (address
->opcode
== OP_ARG
)) {
443 gssize variable_index
= address
->inst_c0
;
444 MonoInst
*local
= info
->cfg
->varinfo
[variable_index
];
446 affected_variables
= &(info
->variables
[variable_index
]);
447 if (LOAD_OF_LOCAL_GIVES_POINTER (inst
,local
)) {
448 father_alias
->type
= MONO_ALIASING_TYPE_ANY
;
450 father_alias
->type
= MONO_ALIASING_TYPE_NO_ALIAS
;
452 } else if (context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_LOCAL
) {
453 gssize variable_index
= context
.subtree_aliases
[0].variable_index
;
454 MonoInst
*local
= info
->cfg
->varinfo
[variable_index
];
456 affected_variables
= &(info
->variables
[variable_index
]);;
457 if (LOAD_OF_LOCAL_GIVES_POINTER (inst
,local
)) {
458 father_alias
->type
= MONO_ALIASING_TYPE_ANY
;
460 father_alias
->type
= MONO_ALIASING_TYPE_NO_ALIAS
;
462 } else if (context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_LOCAL_FIELD
) {
463 gssize variable_index
= context
.subtree_aliases
[0].variable_index
;
465 affected_variables
= &(info
->variables
[variable_index
]);;
466 if (inst
->type
== STACK_MP
) {
467 father_alias
->type
= MONO_ALIASING_TYPE_ANY
;
469 father_alias
->type
= MONO_ALIASING_TYPE_NO_ALIAS
;
472 if (context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_ANY
) {
473 affected_variables
= info
->temporary_uncontrollably_aliased_variables
;
475 if ((inst
->type
== STACK_MP
) && (inst
->inst_i0
->opcode
!= OP_OBJADDR
)) {
476 father_alias
->type
= MONO_ALIASING_TYPE_ANY
;
478 father_alias
->type
= MONO_ALIASING_TYPE_NO_ALIAS
;
482 if (affected_variables
!= NULL
) {
483 MonoAliasUsageInformation
*use
= mono_mempool_alloc (info
->mempool
, sizeof (MonoAliasUsageInformation
));
485 inst
->ssa_op
= MONO_SSA_INDIRECT_LOAD
;
487 use
->affected_variables
= affected_variables
;
488 APPEND_USE (info
,bb_info
,use
);
490 } else if (inst
->ssa_op
== MONO_SSA_STORE
) {
491 if (context
.subtree_aliases
[1].type
== MONO_ALIASING_TYPE_LOCAL
) {
492 ADD_BAD_ALIAS (info
, context
.subtree_aliases
[1].variable_index
);
494 } else if (OP_IS_STORE (inst
->opcode
) || (inst
->opcode
== CEE_STOBJ
)) {
495 MonoInst
*address
= inst
->inst_i0
;
496 MonoLocalVariableList
*affected_variables
= NULL
;
498 if (context
.subtree_aliases
[1].type
== MONO_ALIASING_TYPE_LOCAL
) {
499 ADD_BAD_ALIAS (info
, context
.subtree_aliases
[1].variable_index
);
502 if ((address
->opcode
== OP_LOCAL
) || (address
->opcode
== OP_ARG
)) {
503 gssize variable_index
= address
->inst_c0
;
505 affected_variables
= &(info
->variables
[variable_index
]);
506 } else if ((context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_LOCAL
) || (context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_LOCAL_FIELD
)) {
507 gssize variable_index
= context
.subtree_aliases
[0].variable_index
;
509 affected_variables
= &(info
->variables
[variable_index
]);;
510 } else if (context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_ANY
) {
511 affected_variables
= info
->temporary_uncontrollably_aliased_variables
;
514 if (affected_variables
!= NULL
) {
515 MonoAliasUsageInformation
*use
= mono_mempool_alloc (info
->mempool
, sizeof (MonoAliasUsageInformation
));
517 inst
->ssa_op
= MONO_SSA_INDIRECT_STORE
;
519 use
->affected_variables
= affected_variables
;
520 APPEND_USE (info
,bb_info
,use
);
522 } else if (OP_IS_OUTARG (inst
->opcode
)) {
523 ADD_ARGUMGENT (info
,inst
,context
.subtree_aliases
[0]);
524 } else if (OP_IS_CALL (inst
->opcode
)) {
525 MonoCallInst
*call
= (MonoCallInst
*) inst
;
526 MonoMethodSignature
*sig
= call
->signature
;
527 gboolean call_has_untracked_pointer_argument
= FALSE
;
528 MonoLocalVariableList
*alias_arguments
= NULL
;
531 if ((context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_LOCAL
) || (context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_LOCAL_FIELD
)) {
532 ADD_UNIQUE_VARIABLE (info
,alias_arguments
,context
.subtree_aliases
[0].variable_index
);
533 } else if (context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_ANY
) {
534 call_has_untracked_pointer_argument
= TRUE
;
537 if (FOLLOW_ALIAS_ANALYSIS
) {
538 printf ("CALL, scanning %d arguments\n", info
->number_of_arguments
);
540 for (i
= 0; i
< info
->number_of_arguments
; i
++) {
542 //MonoInst *argument = info->arguments [i];
543 MonoAliasValue arguments_alias
= info
->arguments_aliases
[i
];
545 if ((arguments_alias
.type
== MONO_ALIASING_TYPE_LOCAL
) || (arguments_alias
.type
== MONO_ALIASING_TYPE_LOCAL_FIELD
)) {
546 if (FOLLOW_ALIAS_ANALYSIS
) {
547 printf ("CALL, argument %d passes the address of local %d\n", i
, arguments_alias
.variable_index
);
549 ADD_UNIQUE_VARIABLE (info
,alias_arguments
,arguments_alias
.variable_index
);
552 if (((arguments_alias
.type
== MONO_ALIASING_TYPE_LOCAL
)) && (argument
->inst_c1
> 0)) {
553 int argument_index
= argument
->inst_c1
- 1;
554 if (argument_index
< sig
->param_count
) {
555 if (! (sig
->params
[argument_index
]->byref
)) {
556 ADD_BAD_ALIAS (info
, arguments_alias
.variable_index
);
559 printf ("*** ERROR: argument %d of %d: ", argument_index
, sig
->param_count
);
560 mono_print_tree_nl (argument
);
564 } else if (arguments_alias
.type
== MONO_ALIASING_TYPE_ANY
) {
565 if (FOLLOW_ALIAS_ANALYSIS
) {
566 printf ("CALL, argument %d could pass the address of any local\n", i
);
568 call_has_untracked_pointer_argument
= TRUE
;
572 else if (argument
->inst_c1
> 0) {
573 int argument_index
= argument
->inst_c1
- 1;
574 if (argument_index
< sig
->param_count
) {
575 if (sig
->params
[argument_index
]->type
== MONO_TYPE_PTR
) {
576 call_has_untracked_pointer_argument
= TRUE
;
579 printf ("*** ERROR: argument %d of %d: ", argument_index
, sig
->param_count
);
580 mono_print_tree_nl (argument
);
586 if ((alias_arguments
!= NULL
) || call_has_untracked_pointer_argument
) {
587 MonoAliasUsageInformation
*use
= mono_mempool_alloc (info
->mempool
, sizeof (MonoAliasUsageInformation
));
589 inst
->ssa_op
= MONO_SSA_INDIRECT_LOAD_STORE
;
591 use
->affected_variables
= alias_arguments
;
592 if (call_has_untracked_pointer_argument
) {
593 MonoLocalVariableList
*untracked_element
= mono_mempool_alloc ((info
)->mempool
, sizeof (MonoLocalVariableList
));
594 untracked_element
->variable_index
= NO_VARIABLE_INDEX
;
595 untracked_element
->next
= use
->affected_variables
;
596 use
->affected_variables
= untracked_element
;
598 APPEND_USE (info
,bb_info
,use
);
601 if ((sig
->ret
!= NULL
) && (father_alias
!= NULL
)) {
602 if (sig
->ret
->type
!= MONO_TYPE_PTR
) {
603 father_alias
->type
= MONO_ALIASING_TYPE_NO_ALIAS
;
605 father_alias
->type
= MONO_ALIASING_TYPE_ANY
;
609 info
->number_of_arguments
= 0;
610 } else if ((inst
->opcode
== CEE_ADD
) || (inst
->opcode
== OP_LADD
)){
611 if ((context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_LOCAL
) || (context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_LOCAL_FIELD
)) {
612 int variable_index
= context
.subtree_aliases
[0].variable_index
;
613 //ADD_BAD_ALIAS (info, variable_index);
614 father_alias
->type
= MONO_ALIASING_TYPE_LOCAL_FIELD
;
615 father_alias
->variable_index
= variable_index
;
616 } else if ((context
.subtree_aliases
[1].type
== MONO_ALIASING_TYPE_LOCAL
) || (context
.subtree_aliases
[1].type
== MONO_ALIASING_TYPE_LOCAL_FIELD
)) {
617 int variable_index
= context
.subtree_aliases
[1].variable_index
;
618 //ADD_BAD_ALIAS (info, variable_index);
619 father_alias
->type
= MONO_ALIASING_TYPE_LOCAL_FIELD
;
620 father_alias
->variable_index
= variable_index
;
621 } else if ((context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_ANY
) || (context
.subtree_aliases
[1].type
== MONO_ALIASING_TYPE_ANY
)) {
622 father_alias
->type
= MONO_ALIASING_TYPE_ANY
;
624 father_alias
->type
= MONO_ALIASING_TYPE_NO_ALIAS
;
626 } else if ((inst
->opcode
== OP_MEMCPY
) || (inst
->opcode
== OP_MEMSET
)) {
627 if ((context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_LOCAL
) || (context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_LOCAL_FIELD
)) {
628 MonoAliasUsageInformation
*use
= mono_mempool_alloc (info
->mempool
, sizeof (MonoAliasUsageInformation
));
630 inst
->ssa_op
= MONO_SSA_INDIRECT_STORE
;
632 use
->affected_variables
= &(info
->variables
[context
.subtree_aliases
[0].variable_index
]);
633 APPEND_USE (info
,bb_info
,use
);
634 } else if (context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_ANY
) {
635 MonoAliasUsageInformation
*use
= mono_mempool_alloc (info
->mempool
, sizeof (MonoAliasUsageInformation
));
637 inst
->ssa_op
= MONO_SSA_INDIRECT_STORE
;
639 use
->affected_variables
= info
->temporary_uncontrollably_aliased_variables
;
640 APPEND_USE (info
,bb_info
,use
);
642 } else if ((inst
->opcode
== OP_UNBOXCAST
) || OP_IS_PCONV (inst
->opcode
) || OP_IS_ICONV (inst
->opcode
)) {
643 father_alias
->type
= context
.subtree_aliases
[0].type
;
644 father_alias
->variable_index
= context
.subtree_aliases
[0].variable_index
;
645 } else if ((inst
->opcode
== CEE_LDELEMA
) || (inst
->opcode
== OP_COMPARE
) || (inst
->opcode
== CEE_SWITCH
)) {
646 if (father_alias
!= NULL
) {
647 father_alias
->type
= MONO_ALIASING_TYPE_NO_ALIAS
;
650 MonoAliasType father_type
= MONO_ALIASING_TYPE_NO_ALIAS
;
651 if ((context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_LOCAL
) || (context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_LOCAL_FIELD
)) {
652 MonoAliasUsageInformation
*use
= mono_mempool_alloc (info
->mempool
, sizeof (MonoAliasUsageInformation
));
654 inst
->ssa_op
= MONO_SSA_INDIRECT_LOAD_STORE
;
656 use
->affected_variables
= &(info
->variables
[context
.subtree_aliases
[0].variable_index
]);
657 APPEND_USE (info
, bb_info
, use
);
658 ADD_BAD_ALIAS (info
, context
.subtree_aliases
[0].variable_index
);
660 if ((context
.subtree_aliases
[1].type
== MONO_ALIASING_TYPE_LOCAL
) || (context
.subtree_aliases
[1].type
== MONO_ALIASING_TYPE_LOCAL_FIELD
)) {
661 MonoAliasUsageInformation
*use
= mono_mempool_alloc (info
->mempool
, sizeof (MonoAliasUsageInformation
));
663 inst
->ssa_op
= MONO_SSA_INDIRECT_LOAD_STORE
;
665 use
->affected_variables
= &(info
->variables
[context
.subtree_aliases
[1].variable_index
]);
666 APPEND_USE (info
, bb_info
, use
);
667 ADD_BAD_ALIAS (info
, context
.subtree_aliases
[1].variable_index
);
669 if (father_alias
!= NULL
) {
670 if ((context
.subtree_aliases
[0].type
== MONO_ALIASING_TYPE_ANY
) || (context
.subtree_aliases
[1].type
== MONO_ALIASING_TYPE_ANY
)) {
671 father_type
= MONO_ALIASING_TYPE_ANY
;
673 father_alias
->type
= father_type
;
677 if (FOLLOW_ALIAS_ANALYSIS
) {
678 print_aliasing_context (&context
);
685 * mono_build_aliasing_information:
686 * @cfg: Control Flow Graph
688 * Builds the aliasing information in a cfg.
689 * After this has run, all MonoInst.ssa_op fields will be properly
690 * set (it will use the MONO_SSA_ADDRESS_TAKEN, MONO_SSA_LOAD and
691 * MONO_SSA_STORE values as a starting point).
693 MonoAliasingInformation
*
694 mono_build_aliasing_information (MonoCompile
*cfg
) {
695 MonoMemPool
*pool
= mono_mempool_new ();
696 MonoAliasingInformation
*info
= mono_mempool_alloc (pool
, sizeof (MonoAliasingInformation
));
698 #if (DEBUG_ALIAS_ANALYSIS)
699 int verbose_level
= cfg
->verbose_level
;
700 cfg
->verbose_level
= 7;
703 info
->mempool
= pool
;
705 info
->bb
= mono_mempool_alloc (pool
, sizeof (MonoAliasingInformationInBB
) * cfg
->num_bblocks
);
706 info
->uncontrollably_aliased_variables
= NULL
;
707 info
->next_interesting_inst
= NULL
;
708 info
->variables
= mono_mempool_alloc (pool
, sizeof (MonoLocalVariableList
) * cfg
->num_varinfo
);
709 info
->variable_is_uncontrollably_aliased
= mono_mempool_alloc (pool
, sizeof (gboolean
) * cfg
->num_varinfo
);
710 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
711 info
->variables
[i
].next
= NULL
;
712 info
->variables
[i
].variable_index
= i
;
713 info
->variable_is_uncontrollably_aliased
[i
] = FALSE
;
715 info
->temporary_uncontrollably_aliased_variables
= mono_mempool_alloc (pool
, sizeof (MonoLocalVariableList
));
716 info
->temporary_uncontrollably_aliased_variables
->next
= NULL
;
717 info
->temporary_uncontrollably_aliased_variables
->variable_index
= NO_VARIABLE_INDEX
;
718 info
->arguments
= mono_mempool_alloc (pool
, sizeof (MonoInst
*) * 16);
719 info
->arguments_aliases
= mono_mempool_alloc (pool
, sizeof (MonoAliasValue
) * 16);
720 info
->arguments_capacity
= 16;
721 info
->number_of_arguments
= 0;
723 for (i
= 0; i
< cfg
->num_bblocks
; i
++) {
724 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
725 MonoAliasingInformationInBB
*bb_info
= &(info
->bb
[i
]);
728 if (FOLLOW_ALIAS_ANALYSIS
) {
729 printf ("TRAVERSING BB %d\n", bb
->block_num
);
733 bb_info
->potential_alias_uses
= NULL
;
734 info
->next_interesting_inst
= NULL
;
736 for (inst
= bb
->code
; inst
!= NULL
; inst
= inst
->next
) {
737 if (FOLLOW_ALIAS_ANALYSIS
) {
738 printf ("TRAVERSING INST: ");
739 mono_print_tree_nl (inst
);
741 update_aliasing_information_on_inst (info
, bb_info
, inst
, NULL
);
744 g_assert (info
->number_of_arguments
== 0);
749 for (i
= 0; i
< cfg
->num_bblocks
; i
++) {
750 MonoAliasingInformationInBB
*bb_info
= &(info
->bb
[i
]);
751 MonoAliasUsageInformation
*use
;
753 for (use
= bb_info
->potential_alias_uses
; use
!= NULL
; use
= use
->next
) {
754 if ((use
->affected_variables
!= NULL
) && (use
->affected_variables
->variable_index
== NO_VARIABLE_INDEX
)) {
755 if (use
->affected_variables
->next
== NULL
) {
756 use
->affected_variables
= info
->uncontrollably_aliased_variables
;
758 MonoLocalVariableList
*last
= use
->affected_variables
;
759 while (last
->next
!= NULL
) {
760 while (last
->next
&& info
->variable_is_uncontrollably_aliased
[last
->next
->variable_index
]) {
761 last
->next
= last
->next
->next
;
763 if (last
->next
!= NULL
) {
767 if (last
->variable_index
!= NO_VARIABLE_INDEX
) {
768 use
->affected_variables
= use
->affected_variables
->next
;
769 last
->next
= info
->uncontrollably_aliased_variables
;
771 use
->affected_variables
= info
->uncontrollably_aliased_variables
;
779 if (DUMP_ALIAS_ANALYSIS
) {
780 print_code_with_aliasing_information (info
);
783 #if (DEBUG_ALIAS_ANALYSIS)
784 cfg
->verbose_level
= verbose_level
;
792 mono_destroy_aliasing_information (MonoAliasingInformation
*info
) {
793 mono_mempool_destroy (info
->mempool
);
797 mono_aliasing_initialize_code_traversal (MonoAliasingInformation
*info
, MonoBasicBlock
*bb
) {
798 info
->next_interesting_inst
= info
->bb
[bb
->dfn
].potential_alias_uses
;
801 MonoLocalVariableList
*
802 mono_aliasing_get_affected_variables_for_inst_traversing_code (MonoAliasingInformation
*info
, MonoInst
*inst
) {
803 if ((inst
->ssa_op
== MONO_SSA_LOAD
) || (inst
->ssa_op
== MONO_SSA_STORE
)) {
804 return &(info
->variables
[inst
->inst_i0
->inst_c0
]);
805 } else if (info
->next_interesting_inst
!= NULL
) {
806 if (inst
== info
->next_interesting_inst
->inst
) {
807 MonoLocalVariableList
*result
= info
->next_interesting_inst
->affected_variables
;
808 info
->next_interesting_inst
= info
->next_interesting_inst
->next
;
810 } else if (inst
->ssa_op
!= MONO_SSA_NOP
) {
811 if (inst
->ssa_op
== MONO_SSA_ADDRESS_TAKEN
) {
814 printf ("ERROR: instruction not found '");
815 //print_tree_with_aliasing_information (info, inst);
816 mono_print_tree (inst
);
818 //g_assert_not_reached ();
829 static MonoLocalVariableList
*
830 mono_aliasing_get_affected_variables_for_inst_in_bb (MonoAliasingInformation
*info
, MonoInst
*inst
, MonoBasicBlock
*bb
) {
831 MonoAliasUsageInformation
*use
;
833 for (use
= info
->bb
[bb
->dfn
].potential_alias_uses
; use
!= NULL
; use
= use
->next
) {
834 if (use
->inst
== inst
) {
835 return use
->affected_variables
;
838 g_assert_not_reached ();
842 MonoLocalVariableList
*
843 mono_aliasing_get_affected_variables_for_inst (MonoAliasingInformation
*info
, MonoInst
*inst
) {
846 for (i
= 0; i
< info
->cfg
->num_bblocks
; i
++) {
847 MonoAliasingInformationInBB
*bb_info
= &(info
->bb
[i
]);
848 MonoAliasUsageInformation
*use
;
850 for (use
= info
->bb
[bb_info
->bb
->dfn
].potential_alias_uses
; use
!= NULL
; use
= use
->next
) {
851 if (use
->inst
== inst
) {
852 return use
->affected_variables
;
856 g_assert_not_reached ();
860 #if (MONO_APPLY_DEADCE_TO_SINGLE_METHOD)
862 mono_deadce_method_name
= NULL
;
863 static gboolean
check_deadce_method_name (MonoCompile
*cfg
) {
865 if (mono_deadce_method_name
== NULL
) {
866 mono_deadce_method_name
= getenv ("MONO_DEADCE_METHOD_NAME");
868 if (mono_deadce_method_name
!= NULL
) {
869 char *method_name
= mono_method_full_name (cfg
->method
, TRUE
);
870 if (strstr (method_name
, mono_deadce_method_name
) != NULL
) {
875 g_free (method_name
);
886 #define LOG_DEADCE (info->cfg->verbose_level > 0)
888 #define LOG_DEADCE (info->cfg->verbose_level > 4)
892 mono_aliasing_deadce_on_inst (MonoAliasingInformation
*info
, MonoInst
**possibly_dead_assignments
, MonoInst
*inst
) {
894 gboolean has_side_effects
;
895 MonoLocalVariableList
*affected_variables
;
897 arity
= mono_burg_arity
[inst
->opcode
];
899 switch (inst
->opcode
) {
900 #define OPDEF(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) case a1:
901 #include "simple-cee-ops.h"
903 #define MINI_OP(a1,a2) case a1:
904 #include "simple-mini-ops.h"
906 has_side_effects
= FALSE
;
909 has_side_effects
= TRUE
;
913 if (mono_aliasing_deadce_on_inst (info
, possibly_dead_assignments
, inst
->inst_i0
)) {
914 has_side_effects
= TRUE
;
917 if (mono_aliasing_deadce_on_inst (info
, possibly_dead_assignments
, inst
->inst_i1
)) {
918 has_side_effects
= TRUE
;
924 affected_variables
= mono_aliasing_get_affected_variables_for_inst_traversing_code (info
, inst
);
926 if (affected_variables
!= NULL
) {
927 if (inst
->ssa_op
& MONO_SSA_LOAD
) {
928 MonoLocalVariableList
*affected_variable
;
929 for (affected_variable
= affected_variables
; affected_variable
!= NULL
; affected_variable
= affected_variable
->next
) {
931 printf ("CLEARING slot %d at inst ", affected_variable
->variable_index
);
932 mono_print_tree_nl (inst
);
934 possibly_dead_assignments
[affected_variable
->variable_index
] = NULL
;
937 if (inst
->ssa_op
& MONO_SSA_STORE
) {
938 MonoLocalVariableList
*affected_variable
;
939 for (affected_variable
= affected_variables
; affected_variable
!= NULL
; affected_variable
= affected_variable
->next
) {
940 if (possibly_dead_assignments
[affected_variable
->variable_index
] != NULL
) {
942 printf ("KILLING slot %d at inst ", affected_variable
->variable_index
);
943 mono_print_tree_nl (inst
);
945 possibly_dead_assignments
[affected_variable
->variable_index
]->opcode
= CEE_NOP
;
946 possibly_dead_assignments
[affected_variable
->variable_index
]->ssa_op
= MONO_SSA_NOP
;
947 possibly_dead_assignments
[affected_variable
->variable_index
] = NULL
;
951 //printf ("FAST DEADCE TOTAL LOCAL\n");
956 if ((! has_side_effects
) && (inst
->ssa_op
== MONO_SSA_STORE
)) {
958 printf ("FILLING slot %d with inst ", (int)inst
->inst_i0
->inst_c0
);
959 mono_print_tree_nl (inst
);
961 possibly_dead_assignments
[inst
->inst_i0
->inst_c0
] = inst
;
964 return has_side_effects
;
969 mono_aliasing_deadce (MonoAliasingInformation
*info
) {
971 MonoInst
**possibly_dead_assignments
;
976 possibly_dead_assignments
= alloca (cfg
->num_varinfo
* sizeof (MonoInst
*));
979 printf ("BEFORE DEADCE START\n");
980 mono_print_code (cfg
);
981 printf ("BEFORE DEADCE END\n");
984 #if (MONO_APPLY_DEADCE_TO_SINGLE_METHOD)
985 if (! check_deadce_method_name (cfg
)) {
987 printf ("DEADCE disabled setting MONO_DEADCE_METHOD_NAME\n");
993 for (i
= 0; i
< cfg
->num_bblocks
; i
++) {
998 bb
= cfg
->bblocks
[i
];
999 memset (possibly_dead_assignments
, 0, cfg
->num_varinfo
* sizeof (MonoInst
*));
1000 mono_aliasing_initialize_code_traversal (info
, bb
);
1003 printf ("Working on BB %d\n", bb
->block_num
);
1006 for (inst
= bb
->code
; inst
!= NULL
; inst
= inst
->next
) {
1007 mono_aliasing_deadce_on_inst (info
, possibly_dead_assignments
, inst
);
1008 if (inst
->opcode
== CEE_JMP
) {
1009 /* Keep arguments live! */
1010 for (variable_index
= 0; variable_index
< cfg
->num_varinfo
; variable_index
++) {
1011 if (cfg
->varinfo
[variable_index
]->opcode
== OP_ARG
) {
1013 printf ("FINALLY CLEARING slot %d (JMP), inst was ", variable_index
);
1014 mono_print_tree_nl (possibly_dead_assignments
[variable_index
]);
1016 possibly_dead_assignments
[variable_index
] = NULL
;
1022 for (variable_index
= 0; variable_index
< cfg
->num_varinfo
; variable_index
++) {
1023 if ((possibly_dead_assignments
[variable_index
] != NULL
) && (! mono_bitset_test (bb
->live_out_set
, variable_index
))) {
1025 printf ("FINALLY KILLING slot %d, inst was ", variable_index
);
1026 mono_print_tree_nl (possibly_dead_assignments
[variable_index
]);
1029 //printf ("FAST DEADCE DEAD LOCAL\n");
1031 possibly_dead_assignments
[variable_index
]->opcode
= CEE_NOP
;
1032 possibly_dead_assignments
[variable_index
]->ssa_op
= MONO_SSA_NOP
;
1038 printf ("AFTER DEADCE START\n");
1039 mono_print_code (cfg
);
1040 printf ("AFTER DEADCE END\n");