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 ();
830 static MonoLocalVariableList*
831 mono_aliasing_get_affected_variables_for_inst_in_bb (MonoAliasingInformation *info, MonoInst *inst, MonoBasicBlock *bb) {
832 MonoAliasUsageInformation *use;
834 for (use = info->bb [bb->dfn].potential_alias_uses; use != NULL; use = use->next) {
835 if (use->inst == inst) {
836 return use->affected_variables;
839 g_assert_not_reached ();
844 MonoLocalVariableList*
845 mono_aliasing_get_affected_variables_for_inst (MonoAliasingInformation *info, MonoInst *inst) {
848 for (i = 0; i < info->cfg->num_bblocks; i++) {
849 MonoAliasingInformationInBB *bb_info = &(info->bb [i]);
850 MonoAliasUsageInformation *use;
852 for (use = info->bb [bb_info->bb->dfn].potential_alias_uses; use != NULL; use = use->next) {
853 if (use->inst == inst) {
854 return use->affected_variables;
858 g_assert_not_reached ();
862 #if (MONO_APPLY_DEADCE_TO_SINGLE_METHOD)
864 mono_deadce_method_name = NULL;
865 static gboolean check_deadce_method_name (MonoCompile *cfg) {
867 if (mono_deadce_method_name == NULL) {
868 mono_deadce_method_name = getenv ("MONO_DEADCE_METHOD_NAME");
870 if (mono_deadce_method_name != NULL) {
871 char *method_name = mono_method_full_name (cfg->method, TRUE);
872 if (strstr (method_name, mono_deadce_method_name) != NULL) {
877 g_free (method_name);
888 #define LOG_DEADCE (info->cfg->verbose_level > 0)
890 #define LOG_DEADCE (info->cfg->verbose_level > 4)
894 mono_aliasing_deadce_on_inst (MonoAliasingInformation *info, MonoInst **possibly_dead_assignments, MonoInst *inst) {
896 gboolean has_side_effects;
897 MonoLocalVariableList *affected_variables;
899 arity = mono_burg_arity [inst->opcode];
901 switch (inst->opcode) {
902 #define OPDEF(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) case a1:
903 #include "simple-cee-ops.h"
905 #define MINI_OP(a1,a2) case a1:
906 #include "simple-mini-ops.h"
908 has_side_effects = FALSE;
911 has_side_effects = TRUE;
915 if (mono_aliasing_deadce_on_inst (info, possibly_dead_assignments, inst->inst_i0)) {
916 has_side_effects = TRUE;
919 if (mono_aliasing_deadce_on_inst (info, possibly_dead_assignments, inst->inst_i1)) {
920 has_side_effects = TRUE;
926 affected_variables = mono_aliasing_get_affected_variables_for_inst_traversing_code (info, inst);
928 if (affected_variables != NULL) {
929 if (inst->ssa_op & MONO_SSA_LOAD) {
930 MonoLocalVariableList *affected_variable;
931 for (affected_variable = affected_variables; affected_variable != NULL; affected_variable = affected_variable->next) {
933 printf ("CLEARING slot %d at inst ", affected_variable->variable_index);
934 mono_print_tree_nl (inst);
936 possibly_dead_assignments [affected_variable->variable_index] = NULL;
939 if (inst->ssa_op & MONO_SSA_STORE) {
940 MonoLocalVariableList *affected_variable;
941 for (affected_variable = affected_variables; affected_variable != NULL; affected_variable = affected_variable->next) {
942 if (possibly_dead_assignments [affected_variable->variable_index] != NULL) {
944 printf ("KILLING slot %d at inst ", affected_variable->variable_index);
945 mono_print_tree_nl (inst);
947 possibly_dead_assignments [affected_variable->variable_index]->opcode = OP_NOP;
948 possibly_dead_assignments [affected_variable->variable_index]->ssa_op = MONO_SSA_NOP;
949 possibly_dead_assignments [affected_variable->variable_index] = NULL;
953 //printf ("FAST DEADCE TOTAL LOCAL\n");
958 if ((! has_side_effects) && (inst->ssa_op == MONO_SSA_STORE)) {
960 printf ("FILLING slot %d with inst ", (int)inst->inst_i0->inst_c0);
961 mono_print_tree_nl (inst);
963 possibly_dead_assignments [inst->inst_i0->inst_c0] = inst;
966 return has_side_effects;
971 mono_aliasing_deadce (MonoAliasingInformation *info) {
973 MonoInst **possibly_dead_assignments;
978 possibly_dead_assignments = alloca (cfg->num_varinfo * sizeof (MonoInst*));
981 printf ("BEFORE DEADCE START\n");
982 mono_print_code (cfg);
983 printf ("BEFORE DEADCE END\n");
986 #if (MONO_APPLY_DEADCE_TO_SINGLE_METHOD)
987 if (! check_deadce_method_name (cfg)) {
989 printf ("DEADCE disabled setting MONO_DEADCE_METHOD_NAME\n");
995 for (i = 0; i < cfg->num_bblocks; i++) {
1000 bb = cfg->bblocks [i];
1001 memset (possibly_dead_assignments, 0, cfg->num_varinfo * sizeof (MonoInst*));
1002 mono_aliasing_initialize_code_traversal (info, bb);
1005 printf ("Working on BB %d\n", bb->block_num);
1008 for (inst = bb->code; inst != NULL; inst = inst->next) {
1009 mono_aliasing_deadce_on_inst (info, possibly_dead_assignments, inst);
1010 if (inst->opcode == OP_JMP) {
1011 /* Keep arguments live! */
1012 for (variable_index = 0; variable_index < cfg->num_varinfo; variable_index++) {
1013 if (cfg->varinfo [variable_index]->opcode == OP_ARG) {
1015 printf ("FINALLY CLEARING slot %d (JMP), inst was ", variable_index);
1016 mono_print_tree_nl (possibly_dead_assignments [variable_index]);
1018 possibly_dead_assignments [variable_index] = NULL;
1024 for (variable_index = 0; variable_index < cfg->num_varinfo; variable_index++) {
1025 if ((possibly_dead_assignments [variable_index] != NULL) && (! mono_bitset_test (bb->live_out_set, variable_index))) {
1027 printf ("FINALLY KILLING slot %d, inst was ", variable_index);
1028 mono_print_tree_nl (possibly_dead_assignments [variable_index]);
1031 //printf ("FAST DEADCE DEAD LOCAL\n");
1033 possibly_dead_assignments [variable_index]->opcode = OP_NOP;
1034 possibly_dead_assignments [variable_index]->ssa_op = MONO_SSA_NOP;
1040 printf ("AFTER DEADCE START\n");
1041 mono_print_code (cfg);
1042 printf ("AFTER DEADCE END\n");