X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=mono%2Fmini%2Fssapre.c;h=df1eaff9f4852e6dee6ae48699ab66d249e76d5b;hb=f233a1c472f36dd1d84e3d01de04eca9958262ea;hp=1b226c9e63964dd6afa9e337b2465c075e69367f;hpb=0abc2e6270020edc4a5b4c66f93b4ae582815f20;p=mono.git diff --git a/mono/mini/ssapre.c b/mono/mini/ssapre.c index 1b226c9e639..df1eaff9f48 100644 --- a/mono/mini/ssapre.c +++ b/mono/mini/ssapre.c @@ -9,15 +9,22 @@ #include #include +#include +#ifdef HAVE_ALLOCA_H +#include +#endif #include #include -#include "inssel.h" +#include "config.h" #include "ssapre.h" -extern guint8 mono_burg_arity []; +/* Disable for now to save space since it is not yet ported to linear IR */ +#if 0 + +#ifndef DISABLE_SSA /* Logging conditions */ #define DUMP_LEVEL (4) @@ -52,7 +59,7 @@ print_argument (MonoSsapreExpressionArgument *argument) { printf ("INTEGER_CONSTANT %d", argument->argument.integer_constant); break; case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT: - printf ("LONG_COSTANT %lld", *(argument->argument.long_constant)); + printf ("LONG_COSTANT %lld", (long long)*(argument->argument.long_constant)); break; case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT: printf ("FLOAT_COSTANT %f", *(argument->argument.float_constant)); @@ -79,6 +86,53 @@ print_expression_description (MonoSsapreExpressionDescription *expression_descri } } +#if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION) +static void +snprint_argument (GString *string, MonoSsapreExpressionArgument *argument) { + switch (argument->type) { + case MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY: + g_string_append_printf (string, "ANY"); + break; + case MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT: + g_string_append_printf (string, "NONE"); + break; + case MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE: + g_string_append_printf (string, "ORIGINAL_VARIABLE %d", argument->argument.original_variable); + break; + case MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE: + g_string_append_printf (string, "SSA_VARIABLE %d", argument->argument.ssa_variable); + break; + case MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT: + g_string_append_printf (string, "INTEGER_CONSTANT %d", argument->argument.integer_constant); + break; + case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT: + g_string_append_printf (string, "LONG_COSTANT %lld", *(argument->argument.long_constant)); + break; + case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT: + g_string_append_printf (string, "FLOAT_COSTANT %f", *(argument->argument.float_constant)); + break; + case MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT: + g_string_append_printf (string, "DOUBLE_COSTANT %f", *(argument->argument.double_constant)); + break; + default: + g_string_append_printf (string, "UNKNOWN: %d", argument->type); + } +} + +static void +snprint_expression_description (GString *string, MonoSsapreExpressionDescription *expression_description) { + if (expression_description->opcode != 0) { + g_string_append_printf (string, "%s ([", mono_inst_name (expression_description->opcode) ); + snprint_argument (string, &(expression_description->left_argument)); + g_string_append_printf (string, "],["); + snprint_argument (string, &(expression_description->right_argument)); + g_string_append_printf (string, "])"); + } else { + g_string_append_printf (string, "ANY"); + } +} +#endif + #define GBOOLEAN_TO_STRING(b) ((b)?"TRUE":"FALSE") static void @@ -138,6 +192,11 @@ print_bb_info (MonoSsapreBBInfo *bb_info, gboolean print_occurrences) { if (bb_info->next_interesting_bb != NULL) { printf (", NEXT %d [ID %d]", bb_info->next_interesting_bb->cfg_dfn, bb_info->next_interesting_bb->bb->block_num); } + if (bb_info->dt_covered_by_interesting_BBs) { + printf (" (COVERED)"); + } else { + printf (" (NEVER DOWN SAFE)"); + } printf ("\n"); if (bb_info->has_phi) { printf (" PHI, class %d [ ", bb_info->phi_redundancy_class); @@ -219,9 +278,8 @@ static void dump_code (MonoSsapreWorkArea *area) { MonoInst *current_inst; print_bb_info (current_bb, TRUE); - for (current_inst = current_bb->bb->code; current_inst != NULL; current_inst = current_inst->next) { + MONO_BB_FOR_EACH_INS (current_bb->bb, current_inst) mono_print_tree_nl (current_inst); - } } } @@ -244,7 +302,12 @@ analyze_argument (MonoInst *argument, MonoSsapreExpressionArgument *result) { case CEE_LDIND_R4: case CEE_LDIND_R8: case CEE_LDIND_REF: - analyze_argument (argument->inst_left, result); + if ((argument->inst_left->opcode == OP_LOCAL) || (argument->inst_left->opcode == OP_ARG)) { + result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE; + result->argument.ssa_variable = argument->inst_left->inst_c0; + } else { + result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY; + } break; case OP_ICONST: result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT; @@ -255,23 +318,27 @@ analyze_argument (MonoInst *argument, MonoSsapreExpressionArgument *result) { result->argument.long_constant = &(argument->inst_l); break; case OP_R4CONST: - result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT; - result->argument.float_constant = (float*)argument->inst_p0; + if (! isnan (*((float*)argument->inst_p0))) { + result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT; + result->argument.float_constant = (float*)argument->inst_p0; + } else { + result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY; + } break; case OP_R8CONST: - result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT; - result->argument.double_constant = (double*)argument->inst_p0; - break; - case OP_ARG: - case OP_LOCAL: - result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE; - result->argument.ssa_variable = argument->inst_c0; + if (! isnan (*((double*)argument->inst_p0))) { + result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT; + result->argument.double_constant = (double*)argument->inst_p0; + } else { + result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY; + } break; default: result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY; } } + /* * Given a MonoInst, it tries to describe it as an expression. * If this is not possible, the result will have opcode 0. @@ -279,85 +346,57 @@ analyze_argument (MonoInst *argument, MonoSsapreExpressionArgument *result) { static void analyze_expression (MonoInst *expression, MonoSsapreExpressionDescription *result) { switch (expression->opcode) { - case CEE_LDIND_I1: - case CEE_LDIND_U1: - case CEE_LDIND_I2: - case CEE_LDIND_U2: - case CEE_LDIND_I4: - case CEE_LDIND_U4: - case CEE_LDIND_I8: - case CEE_LDIND_I: - case CEE_LDIND_R4: - case CEE_LDIND_R8: - case CEE_LDIND_REF: - analyze_expression (expression->inst_left, result); - break; - case CEE_SWITCH: - case CEE_ISINST: - case CEE_CASTCLASS: - case OP_OUTARG: - case OP_CALL_REG: - case OP_FCALL_REG: - case OP_LCALL_REG: - case OP_VCALL_REG: - case OP_VOIDCALL_REG: - case CEE_CALL: - case CEE_CALLVIRT: - case OP_FCALL: - case OP_FCALLVIRT: - case OP_LCALL: - case OP_LCALLVIRT: - case OP_VCALL: - case OP_VCALLVIRT: - case OP_VOIDCALL: - case OP_VOIDCALLVIRT: - case OP_RENAME: - case OP_RETARG: -// case OP_OUTARG: - case OP_OUTARG_REG: - case OP_OUTARG_IMM: - case OP_OUTARG_R4: - case OP_OUTARG_R8: - case OP_OUTARG_VT: - case CEE_NOP: - case CEE_JMP: - case CEE_BREAK: - case OP_COMPARE: - case OP_COMPARE_IMM: - case OP_FCOMPARE: - case OP_LCOMPARE: - case OP_ICOMPARE: - case OP_ICOMPARE_IMM: - result->opcode = 0; - break; - default: +#define SSAPRE_SPECIFIC_OPS 1 +#define OPDEF(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) case a1: +#include "simple-cee-ops.h" +#undef OPDEF +#define MINI_OP(a1,a2) case a1: +#include "simple-mini-ops.h" +#undef MINI_OP +#undef SSAPRE_SPECIFIC_OPS if ( (expression->type == STACK_I4) || + (expression->type == STACK_PTR) || + (expression->type == STACK_MP) || (expression->type == STACK_I8) || (expression->type == STACK_R8) ) { if (mono_burg_arity [expression->opcode] > 0) { + result->opcode = expression->opcode; analyze_argument (expression->inst_left, &(result->left_argument)); - if (result->left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY) { - if (mono_burg_arity [expression->opcode] > 1) { - analyze_argument (expression->inst_right, &(result->right_argument)); - if (result->right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY) { - result->opcode = expression->opcode; - } else { - result->opcode = 0; - } - } else { - result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT; - result->opcode = expression->opcode; - } + if (mono_burg_arity [expression->opcode] > 1) { + analyze_argument (expression->inst_right, &(result->right_argument)); } else { - result->opcode = 0; + result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT; } } else { result->opcode = 0; } } else { result->opcode = 0; + //~ if (expression->type != 0) { + //~ MonoType *type = mono_type_from_stack_type (expression); + //~ printf ("SSAPRE refuses opcode %s (%d) with type %s (%d)\n", mono_inst_name (expression->opcode), expression->opcode, mono_type_full_name (type), expression->type); + //~ } else { + //~ printf ("SSAPRE cannot really handle expression of opcode %s (%d)\n", mono_inst_name (expression->opcode), expression->opcode); + //~ } } - } + break; + default: + result->opcode = 0; + result->left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY; + result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY; + } + //~ switch (expression->opcode) { + //~ case CEE_ADD: + //~ if ((result->left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT) && + //~ (result->right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT)) { + //~ break; + //~ } + //~ case CEE_LDELEMA: + //~ case CEE_LDLEN: + //~ result->opcode = 0; + //~ result->left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY; + //~ result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY; + //~ } } /* @@ -377,7 +416,7 @@ convert_ssa_variables_to_original_names (MonoSsapreExpressionDescription *result result->left_argument = expression->left_argument; } else { result->left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE; - original_variable = cfg->vars [expression->left_argument.argument.ssa_variable]->reg; + original_variable = MONO_VARINFO (cfg, expression->left_argument.argument.ssa_variable)->reg; if (original_variable >= 0) { result->left_argument.argument.original_variable = original_variable; } else { @@ -388,7 +427,7 @@ convert_ssa_variables_to_original_names (MonoSsapreExpressionDescription *result result->right_argument = expression->right_argument; } else { result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE; - original_variable = cfg->vars [expression->right_argument.argument.ssa_variable]->reg; + original_variable = MONO_VARINFO (cfg, expression->right_argument.argument.ssa_variable)->reg; if (original_variable >= 0) { result->right_argument.argument.original_variable = original_variable; } else { @@ -430,7 +469,7 @@ is_phi_definition (MonoInst *definition) { * Given a variable index, checks if it is a phi definition * (it assumes the "area" is visible). */ -#define IS_PHI_DEFINITION(v) is_phi_definition (area->cfg->vars [v]->def) +#define IS_PHI_DEFINITION(v) is_phi_definition (MONO_VARINFO (area->cfg, v)->def) /* * Given a variable index, checks if it is a phi definition. @@ -439,7 +478,7 @@ is_phi_definition (MonoInst *definition) { */ static int* get_phi_definition (MonoCompile *cfg, gssize variable) { - MonoInst *definition = cfg->vars [variable]->def; + MonoInst *definition = MONO_VARINFO (cfg, variable)->def; if (is_phi_definition (definition) && (definition->inst_left->inst_c0 == variable)) { return definition->inst_right->inst_phi_args; } else { @@ -455,7 +494,7 @@ get_phi_definition (MonoCompile *cfg, gssize variable) { */ static MonoSsapreBBInfo* get_bb_info_of_definition (MonoSsapreWorkArea *area, gssize variable) { - MonoBasicBlock *def_bb = area->cfg->vars [variable]->def_bb; + MonoBasicBlock *def_bb = MONO_VARINFO (area->cfg, variable)->def_bb; if (def_bb != NULL) { return area->bb_infos_in_cfg_dfn_order [def_bb->dfn]; } else { @@ -611,20 +650,58 @@ add_expression_to_tree (MonoSsapreExpression *tree, MonoSsapreExpression *expres } } +#if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION) +static char *mono_ssapre_expression_name = NULL; +static gboolean +check_ssapre_expression_name (MonoSsapreWorkArea *area, MonoSsapreExpressionDescription *expression_description) { + if (area->expression_is_handled_father) { + return TRUE; + } + if (mono_ssapre_expression_name == NULL) { + mono_ssapre_expression_name = getenv ("MONO_SSAPRE_EXPRESSION_NAME"); + } + if (mono_ssapre_expression_name != NULL) { + GString *expression_name = g_string_new_len ("", 256); + gboolean return_value; + snprint_expression_description (expression_name, expression_description); + if (strstr (expression_name->str, mono_ssapre_expression_name) != NULL) { + return_value = TRUE; + } else { + return_value = FALSE; + } + g_string_free (expression_name, TRUE); + return return_value; + } else { + return TRUE; + } +} +#endif + /* - * Adds an expression to the worklist (putting the given occurrence as first + * Adds an expression to the worklist (putting the current occurrence as first * occurrence of this expression). */ static void -add_expression_to_worklist (MonoSsapreWorkArea *area, MonoSsapreExpressionOccurrence *occurrence) { - MonoSsapreExpression *expression; - - expression = (MonoSsapreExpression*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreExpression)); +add_expression_to_worklist (MonoSsapreWorkArea *area) { + MonoSsapreExpressionOccurrence *occurrence = area->current_occurrence; + MonoSsapreExpression *expression = (MonoSsapreExpression*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreExpression)); convert_ssa_variables_to_original_names (&(expression->description), &(occurrence->description), area->cfg); + +#if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION) + if (! check_ssapre_expression_name (area, &(expression->description))) return; +#endif + expression->type = mono_type_from_stack_type (occurrence->occurrence); expression->occurrences = NULL; expression->last_occurrence = NULL; + expression->next_in_queue = NULL; + if (area->last_in_queue != NULL) { + area->last_in_queue->next_in_queue = expression; + } else { + area->first_in_queue = expression; + } + area->last_in_queue = expression; MONO_SSAPRE_ADD_EXPRESSION_OCCURRANCE (expression, occurrence); area->worklist = add_expression_to_tree (area->worklist, expression); @@ -632,16 +709,16 @@ add_expression_to_worklist (MonoSsapreWorkArea *area, MonoSsapreExpressionOccurr } /* - * Adds an expression occurrence to the worklist. + * Adds the current expression occurrence to the worklist. * If its expression is not yet in the worklist, it is created. */ static void -add_occurrence_to_worklist (MonoSsapreWorkArea *area, MonoSsapreExpressionOccurrence *occurrence) { +add_occurrence_to_worklist (MonoSsapreWorkArea *area) { MonoSsapreExpressionDescription description; MonoSsapreExpression *current_expression; int comparison; - convert_ssa_variables_to_original_names (&description, &(occurrence->description), area->cfg); + convert_ssa_variables_to_original_names (&description, &(area->current_occurrence->description), area->cfg); current_expression = area->worklist; do { @@ -653,66 +730,75 @@ add_occurrence_to_worklist (MonoSsapreWorkArea *area, MonoSsapreExpressionOccurr } else if (comparison < 0) { current_expression = current_expression->previous; } else { - MONO_SSAPRE_ADD_EXPRESSION_OCCURRANCE (current_expression, occurrence); + MONO_SSAPRE_ADD_EXPRESSION_OCCURRANCE (current_expression, area->current_occurrence); } } else { - add_expression_to_worklist (area, occurrence); + add_expression_to_worklist (area); comparison = 0; } } while (comparison != 0); + + area->current_occurrence = (MonoSsapreExpressionOccurrence*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreExpressionOccurrence)); } /* * Process a MonoInst, and of it is a valid expression add it to the worklist. */ -static MonoSsapreExpressionOccurrence* -process_inst (MonoSsapreWorkArea *area, MonoInst* inst, MonoInst* previous_inst, MonoSsapreBBInfo *bb_info, MonoSsapreExpressionOccurrence *current_occurrence) { - - /* Ugly hack to fix missing variable definitions */ - /* (the SSA construction code should have done it already!) */ - switch (inst->opcode) { - case CEE_STIND_REF: - case CEE_STIND_I: - case CEE_STIND_I4: - case CEE_STIND_I1: - case CEE_STIND_I2: - case CEE_STIND_I8: - case CEE_STIND_R4: - case CEE_STIND_R8: - if ((inst->inst_left->opcode == OP_LOCAL) || (inst->inst_left->opcode == OP_ARG)) { - int variable_index = inst->inst_left->inst_c0; - - if (area->cfg->vars [variable_index]->def_bb == NULL) { - if (area->cfg->verbose_level >= 4) { - printf ("SSAPRE WARNING: variable %d has no definition, fixing.\n", variable_index); - } - area->cfg->vars [variable_index]->def_bb = bb_info->bb; - } - } - break; - default: - break; - } +static void +process_inst (MonoSsapreWorkArea *area, MonoInst* inst, MonoInst* previous_inst, MonoSsapreFatherExpression*** father_in_tree, MonoSsapreBBInfo *bb_info) { + MonoSsapreFatherExpression** left_father_in_tree = NULL; + MonoSsapreFatherExpression** right_father_in_tree = NULL; if (mono_burg_arity [inst->opcode] > 0) { - current_occurrence = process_inst (area, inst->inst_left, previous_inst, bb_info, current_occurrence); + process_inst (area, inst->inst_left, previous_inst, &left_father_in_tree, bb_info); if (mono_burg_arity [inst->opcode] > 1) { - current_occurrence = process_inst (area, inst->inst_right, previous_inst, bb_info, current_occurrence); + process_inst (area, inst->inst_right, previous_inst, &right_father_in_tree, bb_info); } } - analyze_expression (inst, &(current_occurrence->description)); - if (current_occurrence->description.opcode != 0) { - current_occurrence->occurrence = inst; - current_occurrence->previous_tree = previous_inst; - current_occurrence->bb_info = bb_info; - current_occurrence->is_first_in_bb = FALSE; - current_occurrence->is_last_in_bb = FALSE; - add_occurrence_to_worklist (area, current_occurrence); - current_occurrence = (MonoSsapreExpressionOccurrence*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreExpressionOccurrence)); + analyze_expression (inst, &(area->current_occurrence->description)); + if (area->current_occurrence->description.opcode != 0) { + if ((left_father_in_tree != NULL) || (right_father_in_tree != NULL)) { + MonoSsapreFatherExpression *current_inst_as_father = (MonoSsapreFatherExpression*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreFatherExpression)); + current_inst_as_father->father_occurrence = inst; + current_inst_as_father->grand_father = NULL; + *father_in_tree = &(current_inst_as_father->grand_father); + if (left_father_in_tree != NULL) { + *left_father_in_tree = current_inst_as_father; + } + if (right_father_in_tree != NULL) { + *right_father_in_tree = current_inst_as_father; + } + if (DUMP_SSAPRE) { + printf ("Expression '"); + mono_print_tree (inst); + printf ("' is a potential father ( "); + if (left_father_in_tree != NULL) { + printf ("LEFT "); + } + if (right_father_in_tree != NULL) { + printf ("RIGHT "); + } + printf (")\n"); + } + } else if ((area->current_occurrence->description.left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY) && + (area->current_occurrence->description.right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY)) { + area->current_occurrence->occurrence = inst; + area->current_occurrence->previous_tree = previous_inst; + area->current_occurrence->bb_info = bb_info; + area->current_occurrence->is_first_in_bb = FALSE; + area->current_occurrence->is_last_in_bb = FALSE; + + area->current_occurrence->father_in_tree = NULL; + *father_in_tree = &(area->current_occurrence->father_in_tree); + + add_occurrence_to_worklist (area); + } else { + *father_in_tree = NULL; + } + } else { + *father_in_tree = NULL; } - - return current_occurrence; } /* @@ -721,13 +807,14 @@ process_inst (MonoSsapreWorkArea *area, MonoInst* inst, MonoInst* previous_inst, * auxiliary MonoSsapreBBInfo fields (dt_dfn, dt_descendants) are initialized * (with all the info that comes from the MonoBasicBlock). */ -static MonoSsapreExpressionOccurrence* -process_bb (MonoSsapreWorkArea *area, MonoBasicBlock *bb, int *dt_dfn, int *upper_descendants, MonoSsapreExpressionOccurrence *current_occurrence) { +static void +process_bb (MonoSsapreWorkArea *area, MonoBasicBlock *bb, int *dt_dfn, int *upper_descendants, int current_depth) { MonoSsapreBBInfo *bb_info; int descendants; - GList *dominated_bb; + GSList *dominated_bb; MonoInst* current_inst; MonoInst* previous_inst; + MonoSsapreFatherExpression** dummy_father_in_tree; bb_info = &(area->bb_infos [*dt_dfn]); bb_info->dt_dfn = *dt_dfn; @@ -740,29 +827,61 @@ process_bb (MonoSsapreWorkArea *area, MonoBasicBlock *bb, int *dt_dfn, int *uppe bb_info->bb = bb; bb_info->in_bb = (MonoSsapreBBInfo**) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreBBInfo*) * (bb->in_count)); bb_info->out_bb = (MonoSsapreBBInfo**) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreBBInfo*) * (bb->out_count)); - bb_info->phi_arguments_classes = (gssize*) mono_mempool_alloc (area->mempool, sizeof (gssize) * (bb->in_count)); + bb_info->phi_arguments_classes = (int*) mono_mempool_alloc (area->mempool, sizeof (int) * (bb->in_count)); bb_info->phi_insertion_point = NULL; - current_inst = bb->code; previous_inst = NULL; - while (current_inst != NULL) { + MONO_BB_FOR_EACH_INS (bb, current_inst) { + /* Ugly hack to fix missing variable definitions */ + /* (the SSA construction code should have done it already!) */ + switch (current_inst->opcode) { + case CEE_STIND_REF: + case CEE_STIND_I: + case CEE_STIND_I4: + case CEE_STIND_I1: + case CEE_STIND_I2: + case CEE_STIND_I8: + case CEE_STIND_R4: + case CEE_STIND_R8: + if ((current_inst->inst_left->opcode == OP_LOCAL) || (current_inst->inst_left->opcode == OP_ARG)) { + int variable_index = current_inst->inst_left->inst_c0; + + if (MONO_VARINFO (area->cfg, variable_index)->def_bb == NULL) { + if (area->cfg->verbose_level >= 4) { + printf ("SSAPRE WARNING: variable %d has no definition, fixing.\n", variable_index); + } + MONO_VARINFO (area->cfg, variable_index)->def_bb = bb_info->bb; + } + } + break; + default: + break; + } + if (is_phi_definition (current_inst)) { bb_info->phi_insertion_point = current_inst; } - current_occurrence = process_inst (area, current_inst, previous_inst, bb_info, current_occurrence); + + if (mono_burg_arity [current_inst->opcode] > 0) { + process_inst (area, current_inst->inst_left, previous_inst, &dummy_father_in_tree, bb_info); + if (mono_burg_arity [current_inst->opcode] > 1) { + process_inst (area, current_inst->inst_right, previous_inst, &dummy_father_in_tree, bb_info); + } + } + previous_inst = current_inst; - current_inst = current_inst->next; } + if (current_depth > area->dt_depth) { + area->dt_depth = current_depth; + } descendants = 0; - for (dominated_bb = g_list_first (bb->dominated); dominated_bb != NULL; dominated_bb = g_list_next (dominated_bb)) { - current_occurrence = process_bb (area, (MonoBasicBlock*) (dominated_bb->data), dt_dfn, &descendants, current_occurrence); + for (dominated_bb = bb->dominated; dominated_bb != NULL; dominated_bb = dominated_bb->next) { + process_bb (area, (MonoBasicBlock*) (dominated_bb->data), dt_dfn, &descendants, current_depth + 1); } bb_info->dt_descendants = descendants; *upper_descendants += (descendants + 1); - - return current_occurrence; } /* @@ -773,6 +892,7 @@ clean_bb_infos (MonoSsapreWorkArea *area) { int i; for (i = 0; i < area->num_bblocks; i++) { MonoSsapreBBInfo *bb_info = &(area->bb_infos [i]); + bb_info->dt_covered_by_interesting_BBs = FALSE; bb_info->has_phi = FALSE; bb_info->phi_defines_a_real_occurrence = FALSE; bb_info->phi_is_down_safe = FALSE; @@ -850,6 +970,18 @@ compute_combined_iterated_dfrontier (MonoSsapreWorkArea *area, MonoBitSet *resul } while (change); } +/* + * See paper, section 5.1, definition of "Dominate" + */ +static gboolean +dominates (MonoSsapreBBInfo *dominator, MonoSsapreBBInfo *dominated) { + if ((dominator->dt_dfn <= dominated->dt_dfn) && (dominated->dt_dfn <= (dominator->dt_dfn + dominator->dt_descendants))) { + return TRUE; + } else { + return FALSE; + } +} + /* * See paper, figure 18, function Set_var_phis */ @@ -857,7 +989,7 @@ static void process_phi_variable_in_phi_insertion (MonoSsapreWorkArea *area, gss int* phi_definition = get_phi_definition (area->cfg, variable); if (phi_definition != NULL) { - int definition_bb = area->cfg->vars [variable]->def_bb->dfn; + int definition_bb = MONO_VARINFO (area->cfg, variable)->def_bb->dfn; if (! mono_bitset_test (phi_bbs, definition_bb)) { int i; mono_bitset_set (phi_bbs, definition_bb); @@ -878,6 +1010,9 @@ phi_insertion (MonoSsapreWorkArea *area, MonoSsapreExpression *expression) { MonoSsapreBBInfo *current_bb = NULL; MonoSsapreBBInfo *previous_interesting_bb = NULL; int i, j, current_bb_dt_dfn; + int top; + MonoSsapreBBInfo **stack; + gboolean *interesting_stack; mono_bitset_clear_all (area->expression_occurrences_buffer); for (current_expression = expression->occurrences; current_expression != NULL; current_expression = current_expression->next) { @@ -917,16 +1052,60 @@ phi_insertion (MonoSsapreWorkArea *area, MonoSsapreExpression *expression) { } } + top = -1; + stack = (MonoSsapreBBInfo **) alloca (sizeof (MonoSsapreBBInfo *) * (area->dt_depth)); + interesting_stack = (gboolean *) alloca (sizeof (gboolean) * (area->dt_depth)); + + /* Setup the list of interesting BBs, and their "DT coverage" */ for (current_bb = area->bb_infos, current_bb_dt_dfn = 0; current_bb_dt_dfn < area->num_bblocks; current_bb++, current_bb_dt_dfn++) { + gboolean current_bb_is_interesting; + if ((current_bb->first_expression_in_bb != NULL) || (current_bb->has_phi) || (current_bb->has_phi_argument)) { + current_bb_is_interesting = TRUE; + if (previous_interesting_bb != NULL) { previous_interesting_bb->next_interesting_bb = current_bb; } else { area->first_interesting_bb = current_bb; } previous_interesting_bb = current_bb; + } else { + current_bb_is_interesting = FALSE; + } + + if (top >= 0) { + while ((top >= 0) && (! dominates (stack [top], current_bb))) { + gboolean top_covers_his_idominator = ((interesting_stack [top]) || (stack [top]->dt_covered_by_interesting_BBs)); + + if ((top > 0) && (! top_covers_his_idominator)) { + stack [top - 1]->dt_covered_by_interesting_BBs = FALSE; + } + + top--; + } + } else { + top = -1; + } + + top++; + + interesting_stack [top] = current_bb_is_interesting; + stack [top] = current_bb; + if (stack [top]->dt_descendants == 0) { + stack [top]->dt_covered_by_interesting_BBs = FALSE; + } else { + stack [top]->dt_covered_by_interesting_BBs = TRUE; } } + while (top > 0) { + gboolean top_covers_his_idominator = ((interesting_stack [top]) || (stack [top]->dt_covered_by_interesting_BBs)); + + if (! top_covers_his_idominator) { + stack [top - 1]->dt_covered_by_interesting_BBs = FALSE; + } + + top--; + } } /* @@ -958,18 +1137,6 @@ phi_insertion (MonoSsapreWorkArea *area, MonoSsapreExpression *expression) { area->bb_on_top_of_renaming_stack->phi_argument_has_real_use = FALSE; \ } while(0) -/* - * See paper, section 5.1, definition of "Dominate" - */ -static gboolean -dominates (MonoSsapreBBInfo *dominator, MonoSsapreBBInfo *dominated) { - if ((dominator->dt_dfn <= dominated->dt_dfn) && (dominated->dt_dfn <= (dominator->dt_dfn + dominator->dt_descendants))) { - return TRUE; - } else { - return FALSE; - } -} - /* * See paper, section 5.4. * The two passes are coded sequentially (no separate "rename1" and "rename2" functions). @@ -983,35 +1150,68 @@ renaming_pass (MonoSsapreWorkArea *area) { /* This loop is "rename1" */ for (current_bb = area->first_interesting_bb, previous_bb = NULL; current_bb != NULL; previous_bb = current_bb, current_bb = current_bb->next_interesting_bb) { - if ((previous_bb != NULL) && ! dominates (previous_bb, current_bb)) { - if ((area->bb_on_top_of_renaming_stack != NULL) && (area->top_of_renaming_stack == NULL) && (previous_bb->phi_argument_has_real_use == FALSE)) { - if (TRACE_SSAPRE) { - printf ("Clearing down safe in PHI %d because of backtracking (previous block is [bb %d [ID %d]])\n", - area->bb_on_top_of_renaming_stack->phi_redundancy_class, previous_bb->cfg_dfn, previous_bb->bb->block_num); + if (previous_bb != NULL) { + if (! dominates (previous_bb, current_bb)) { + /* This means we are backtracking in the dominator tree */ + MonoSsapreBBInfo *first_interesting_dominator = current_bb->idominator; + while ((first_interesting_dominator->next_interesting_bb == NULL) && (first_interesting_dominator->idominator != NULL)) { + first_interesting_dominator = first_interesting_dominator->idominator; } - area->bb_on_top_of_renaming_stack->phi_is_down_safe = FALSE; - } - while ((area->bb_on_top_of_renaming_stack != NULL) && ! dominates (area->bb_on_top_of_renaming_stack, current_bb)) { - MonoSsapreBBInfo *top_bb = area->bb_on_top_of_renaming_stack; - if (top_bb->next_in_renaming_stack != NULL) { - area->top_of_renaming_stack = top_bb->next_in_renaming_stack->top_of_local_renaming_stack; - } else { - area->top_of_renaming_stack = NULL; + current_bb->phi_argument_has_real_use = first_interesting_dominator->phi_argument_has_real_use; + + if ((area->bb_on_top_of_renaming_stack != NULL) && (area->top_of_renaming_stack == NULL) && (previous_bb->phi_argument_has_real_use == FALSE)) { + if (TRACE_SSAPRE) { + printf ("Clearing down safe in PHI %d because of backtracking (current block is [bb %d [ID %d]], previous block is [bb %d [ID %d]])\n", + area->bb_on_top_of_renaming_stack->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num, previous_bb->cfg_dfn, previous_bb->bb->block_num); + } + area->bb_on_top_of_renaming_stack->phi_is_down_safe = FALSE; } - area->bb_on_top_of_renaming_stack = top_bb->next_in_renaming_stack; + while ((area->bb_on_top_of_renaming_stack != NULL) && ! dominates (area->bb_on_top_of_renaming_stack, current_bb)) { + MonoSsapreBBInfo *top_bb = area->bb_on_top_of_renaming_stack; + if (top_bb->next_in_renaming_stack != NULL) { + area->top_of_renaming_stack = top_bb->next_in_renaming_stack->top_of_local_renaming_stack; + } else { + area->top_of_renaming_stack = NULL; + } + area->bb_on_top_of_renaming_stack = top_bb->next_in_renaming_stack; + } + if (DUMP_SSAPRE) { + printf ("Backtracked, getting real use flag from bb %d [ID %d], current top of the stack is class ", + first_interesting_dominator->cfg_dfn, first_interesting_dominator->bb->block_num); + if (area->top_of_renaming_stack != NULL) { + printf ("%d\n", area->top_of_renaming_stack->redundancy_class); + } else if (area->bb_on_top_of_renaming_stack != NULL) { + printf ("%d\n", area->bb_on_top_of_renaming_stack->phi_redundancy_class); + } else { + printf ("BOTTOM\n"); + } + } + } else { + /* With no backtracking we just propagate the flag */ + current_bb->phi_argument_has_real_use = previous_bb->phi_argument_has_real_use; } - } - if (current_bb->idominator != NULL) { - current_bb->phi_argument_has_real_use = current_bb->idominator->phi_argument_has_real_use; } else { + /* Start condition */ current_bb->phi_argument_has_real_use = FALSE; } + if (DUMP_SSAPRE) { + printf ("Real use flag is %s at the beginning of block [bb %d [ID %d]]\n", + GBOOLEAN_TO_STRING (current_bb->phi_argument_has_real_use), current_bb->cfg_dfn, current_bb->bb->block_num); + } if (current_bb->has_phi) { - current_bb->phi_is_down_safe = TRUE; + if (current_bb->dt_covered_by_interesting_BBs) { + current_bb->phi_is_down_safe = TRUE; + } else { + current_bb->phi_is_down_safe = FALSE; + } current_bb->phi_redundancy_class = current_class; current_class++; PUSH_PHI_OCCURRENCE (current_bb); + if (TRACE_SSAPRE) { + printf ("Assigning class %d to PHI in bb %d [ID %d]\n", + current_bb->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num); + } } for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) { @@ -1024,11 +1224,21 @@ renaming_pass (MonoSsapreWorkArea *area) { (current_expression->description.right_argument.argument.ssa_variable == top->description.right_argument.argument.ssa_variable))) { current_expression->redundancy_class = top->redundancy_class; current_expression->defined_by_real_occurrence = top; + if (DUMP_SSAPRE) { + printf ("Using class %d for occurrence '", current_expression->redundancy_class); + print_expression_description (&(current_expression->description)); + printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num); + } } else { current_expression->redundancy_class = current_class; current_class++; current_expression->defined_by_real_occurrence = NULL; PUSH_REAL_OCCURRENCE (current_expression); + if (TRACE_SSAPRE) { + printf ("Assigning class %d to occurrence '", current_expression->redundancy_class); + print_expression_description (&(current_expression->description)); + printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num); + } } current_expression->defined_by_phi = NULL; } else if (area->bb_on_top_of_renaming_stack != NULL) { @@ -1058,6 +1268,16 @@ renaming_pass (MonoSsapreWorkArea *area) { current_expression->redundancy_class = phi_bb->phi_redundancy_class; current_expression->defined_by_phi = phi_bb; + /* If this PHI was not "covered", it is not down safe. */ + /* However, if the real occurrence is in the same BB, it */ + /* actually is down safe */ + if (phi_bb == current_bb) { + if (DUMP_SSAPRE) { + printf ("PHI in bb %d [ID %d] defined occurrence %d in the same BB, so it is down safe\n", phi_bb->cfg_dfn, phi_bb->bb->block_num, current_expression->redundancy_class); + } + phi_bb->phi_is_down_safe = TRUE; + } + /* * Major difference from the paper here... * Instead of maintaining "set_for_rename2" (see figure 20), we just @@ -1076,6 +1296,11 @@ renaming_pass (MonoSsapreWorkArea *area) { right_argument_version, phi_bb, phi_argument); } } + if (DUMP_SSAPRE) { + printf ("Using class %d for occurrence '", current_expression->redundancy_class); + print_expression_description (&(current_expression->description)); + printf ("' in bb %d [ID %d] (Real use flag is now TRUE)\n", current_bb->cfg_dfn, current_bb->bb->block_num); + } } else { current_expression->redundancy_class = current_class; current_class++; @@ -1083,6 +1308,9 @@ renaming_pass (MonoSsapreWorkArea *area) { PUSH_REAL_OCCURRENCE (current_expression); phi_bb->phi_is_down_safe = FALSE; if (TRACE_SSAPRE) { + printf ("Assigning class %d to occurrence '", current_expression->redundancy_class); + print_expression_description (&(current_expression->description)); + printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num); printf ("Clearing down safe in PHI %d because of real occurrence %d\n", phi_bb->phi_redundancy_class, current_expression->redundancy_class); } @@ -1094,6 +1322,11 @@ renaming_pass (MonoSsapreWorkArea *area) { current_expression->defined_by_real_occurrence = NULL; current_expression->defined_by_phi = NULL; PUSH_REAL_OCCURRENCE (current_expression); + if (TRACE_SSAPRE) { + printf ("Assigning class %d to occurrence '", current_expression->redundancy_class); + print_expression_description (&(current_expression->description)); + printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num); + } } } @@ -1107,6 +1340,10 @@ renaming_pass (MonoSsapreWorkArea *area) { } else { current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS; } + if ((DUMP_SSAPRE) && (current_bb->phi_argument_class != BOTTOM_REDUNDANCY_CLASS)) { + printf ("Temporarily using class %d for PHI argument in bb %d [ID %d]\n", + current_bb->phi_argument_class, current_bb->cfg_dfn, current_bb->bb->block_num); + } } } if ((area->bb_on_top_of_renaming_stack != NULL) && (area->top_of_renaming_stack == NULL) && (previous_bb->phi_argument_has_real_use == FALSE)) { @@ -1161,6 +1398,11 @@ renaming_pass (MonoSsapreWorkArea *area) { current_bb->phi_argument_defined_by_phi->phi_is_down_safe = FALSE; } current_bb->phi_argument_has_real_use = FALSE; + + if (DUMP_SSAPRE) { + printf ("Cleared real use flag in block [bb %d [ID %d]] because phi argument class is now BOTTOM\n", + current_bb->cfg_dfn, current_bb->bb->block_num); + } } } } @@ -1187,9 +1429,6 @@ reset_down_safe (MonoSsapreBBInfo *phi_argument) { if ((phi_argument->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) && (! phi_argument->phi_argument_has_real_use) && (phi_argument->phi_argument_defined_by_phi != NULL) && (phi_argument->phi_argument_defined_by_phi->phi_is_down_safe)) { int i; MonoSsapreBBInfo *phi = phi_argument->phi_argument_defined_by_phi; -// if (TRACE_SSAPRE) { -// printf ("Clearing down safe in PHI %d inside reset_down_safe\n", phi->phi_redundancy_class); -// } phi->phi_is_down_safe = FALSE; for (i = 0; i < phi->in_count; i++) { reset_down_safe (phi->in_bb [i]); @@ -1223,6 +1462,11 @@ static void reset_can_be_available (MonoSsapreWorkArea *area, MonoSsapreBBInfo *phi) { MonoSsapreBBInfo *current_bb = NULL; + if (DUMP_SSAPRE) { + printf ("Resetting availability for PHI %d in block [bb %d [ID %d]]\n", + phi->phi_redundancy_class, phi->cfg_dfn, phi->bb->block_num); + } + phi->phi_can_be_available = FALSE; for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) { if (current_bb->has_phi) { @@ -1265,6 +1509,10 @@ compute_can_be_available (MonoSsapreWorkArea *area) { } if (phi_is_interesting) { + if (DUMP_SSAPRE) { + printf ("Availability computation working on PHI %d in block [bb %d [ID %d]]\n", + current_bb->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num); + } reset_can_be_available (area, current_bb); } } @@ -1343,6 +1591,10 @@ static void finalize_availability_and_reload (MonoSsapreWorkArea *area, MonoSsap MonoSsapreBBInfo *current_bb = NULL; MonoSsapreExpressionOccurrence *current_expression = NULL; + area->occurrences_scheduled_for_reloading = 0; + area->arguments_scheduled_for_insertion = 0; + area->dominating_arguments_scheduled_for_insertion = 0; + for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) { if (current_bb->has_phi) { if (current_bb->phi_can_be_available && ! current_bb->phi_is_later) { @@ -1366,6 +1618,9 @@ static void finalize_availability_and_reload (MonoSsapreWorkArea *area, MonoSsap availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence = current_expression; } else { current_expression->reload = TRUE; + + area->occurrences_scheduled_for_reloading ++; + current_expression->defined_by_phi = availability_table [current_expression->redundancy_class].class_defined_by_phi; current_expression->defined_by_real_occurrence = availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence; } @@ -1381,6 +1636,12 @@ static void finalize_availability_and_reload (MonoSsapreWorkArea *area, MonoSsap (! ((current_bb->phi_argument_defined_by_phi->phi_can_be_available) && (! current_bb->phi_argument_defined_by_phi->phi_is_later))) ))) { current_bb->phi_argument_needs_insert = TRUE; + + area->arguments_scheduled_for_insertion ++; + if (dominates (current_bb, phi_bb)) { + area->dominating_arguments_scheduled_for_insertion ++; + } + current_bb->phi_argument_defined_by_real_occurrence = NULL; current_bb->phi_argument_defined_by_phi = NULL; } else { @@ -1438,10 +1699,16 @@ static void finalize_save (MonoSsapreWorkArea *area) { } } +#define OP_IS_CHEAP(op) (((op)==CEE_ADD)||((op)==CEE_SUB)) +#define EXPRESSION_HAS_ICONST(d) (((d).left_argument.type==MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT)||((d).right_argument.type==MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT)) +#define EXPRESSION_IS_CHEAP(d) ((OP_IS_CHEAP ((d).opcode))&&(EXPRESSION_HAS_ICONST ((d)))) +#define REDUNDANCY_IS_SMALL(a) (((a)->occurrences_scheduled_for_reloading < 2)&&((a)->dominating_arguments_scheduled_for_insertion < 1)) + /* - * Perform all "finalize" steps + * Perform all "finalize" steps. + * Return TRUE if we must go on with code_motion. */ -static void finalize (MonoSsapreWorkArea *area) { +static gboolean finalize (MonoSsapreWorkArea *area) { MonoSsapreAvailabilityTableElement *availability_table = alloca (sizeof (MonoSsapreAvailabilityTableElement) * (area->number_of_classes)); int i; @@ -1451,7 +1718,14 @@ static void finalize (MonoSsapreWorkArea *area) { } finalize_availability_and_reload (area, availability_table); - finalize_save (area); + + /* Tuning: if the redundancy is not worth handling, give up */ + if ((EXPRESSION_IS_CHEAP (area->current_expression->description)) && (REDUNDANCY_IS_SMALL (area))) { + return FALSE; + } else { + finalize_save (area); + return TRUE; + } } /* @@ -1522,33 +1796,76 @@ create_expression_argument (MonoSsapreWorkArea *area, MonoSsapreExpressionArgume * Create a MonoInst that represents an expression */ static MonoInst* -create_expression (MonoSsapreWorkArea *area, MonoSsapreExpressionDescription *expression) { +create_expression (MonoSsapreWorkArea *area, MonoSsapreExpressionDescription *expression, MonoInst *prototype_occurrence) { MonoInst *result; NEW_INST (result, expression->opcode); + *result = *prototype_occurrence; result->inst_left = create_expression_argument (area, &(expression->left_argument)); result->inst_right = create_expression_argument (area, &(expression->right_argument)); return result; } +/* + * Handles the father expression of a MonoInst that has been turned + * into a load (eventually inserting it into the worklist). + * Assumes "current_expression->father_in_tree != NULL". + */ +static void +handle_father_expression (MonoSsapreWorkArea *area, MonoSsapreExpressionOccurrence *current_expression, MonoInst *previous_tree) { + if (DUMP_SSAPRE) { + printf ("After reload, father expression becomes "); + mono_print_tree_nl (current_expression->father_in_tree->father_occurrence); + } + + analyze_expression (current_expression->father_in_tree->father_occurrence, &(area->current_occurrence->description)); + if ((area->current_occurrence->description.opcode != 0) && + (area->current_occurrence->description.left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY) && + (area->current_occurrence->description.right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY)) { + area->current_occurrence->occurrence = current_expression->father_in_tree->father_occurrence; + area->current_occurrence->previous_tree = previous_tree; + area->current_occurrence->father_in_tree = current_expression->father_in_tree->grand_father; + area->current_occurrence->bb_info = current_expression->bb_info; + area->current_occurrence->is_first_in_bb = FALSE; + area->current_occurrence->is_last_in_bb = FALSE; + add_occurrence_to_worklist (area); + } +} + /* * See paper, section 3.6 */ static void code_motion (MonoSsapreWorkArea *area) { MonoSsapreBBInfo *current_bb = NULL; MonoSsapreExpressionOccurrence *current_expression = NULL; + gssize original_variable_index = BOTTOM_REDUNDANCY_CLASS; + MonoInst prototype_occurrence; + prototype_occurrence.opcode = 0; for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) { if ((current_bb->has_phi) && (current_bb->phi_can_be_available && ! current_bb->phi_is_later)) { MonoInst *new_var = mono_compile_create_var (area->cfg, area->current_expression->type, OP_LOCAL); current_bb->phi_variable_index = new_var->inst_c0; + if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) { + original_variable_index = new_var->inst_c0; + } + MONO_VARINFO (area->cfg, new_var->inst_c0)->reg = original_variable_index; + MONO_VARINFO (area->cfg, new_var->inst_c0)->def_bb = current_bb->bb; } else { current_bb->phi_variable_index = BOTTOM_REDUNDANCY_CLASS; } for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) { + if (prototype_occurrence.opcode == 0) { + prototype_occurrence = *(current_expression->occurrence); + } if (current_expression->save) { MonoInst *new_var = mono_compile_create_var (area->cfg, area->current_expression->type, OP_LOCAL); current_expression->variable_index = new_var->inst_c0; + if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) { + original_variable_index = new_var->inst_c0; + } + MONO_VARINFO (area->cfg, new_var->inst_c0)->reg = original_variable_index; + MONO_VARINFO (area->cfg, new_var->inst_c0)->def_bb = current_bb->bb; } else { current_expression->variable_index = BOTTOM_REDUNDANCY_CLASS; } @@ -1557,6 +1874,11 @@ static void code_motion (MonoSsapreWorkArea *area) { if ((current_bb->has_phi_argument) && (current_bb->phi_argument_needs_insert)) { MonoInst *new_var = mono_compile_create_var (area->cfg, area->current_expression->type, OP_LOCAL); current_bb->phi_argument_variable_index = new_var->inst_c0; + if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) { + original_variable_index = new_var->inst_c0; + } + MONO_VARINFO (area->cfg, new_var->inst_c0)->reg = original_variable_index; + MONO_VARINFO (area->cfg, new_var->inst_c0)->def_bb = current_bb->bb; } else { current_bb->phi_argument_variable_index = BOTTOM_REDUNDANCY_CLASS; } @@ -1569,6 +1891,7 @@ static void code_motion (MonoSsapreWorkArea *area) { int in_bb; NEW_INST (phi, OP_PHI); + phi->inst_c0 = MONO_VARINFO (area->cfg, current_bb->phi_variable_index)->reg; phi->inst_phi_args = mono_mempool_alloc (area->cfg->mempool, (sizeof (int) * ((current_bb->in_count) + 1))); phi->inst_phi_args [0] = current_bb->in_count; for (in_bb = 0; in_bb < current_bb->in_count; in_bb++) { @@ -1593,6 +1916,7 @@ static void code_motion (MonoSsapreWorkArea *area) { store->next = current_bb->bb->code; current_bb->bb->code = store; } + MONO_VARINFO (area->cfg, current_bb->phi_variable_index)->def = store; current_bb->phi_insertion_point = store; area->added_phis ++; @@ -1600,21 +1924,6 @@ static void code_motion (MonoSsapreWorkArea *area) { for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) { gboolean altered = FALSE; - if (current_expression->reload) { - gssize variable_index; - if (current_expression->defined_by_phi != NULL) { - variable_index = current_expression->defined_by_phi->phi_variable_index; - } else if (current_expression->defined_by_real_occurrence != NULL) { - variable_index = current_expression->defined_by_real_occurrence->variable_index; - } else { - variable_index = BOTTOM_REDUNDANCY_CLASS; - g_assert_not_reached (); - } - mono_compile_make_var_load (area->cfg, current_expression->occurrence, variable_index); - - area->reloaded_occurrences ++; - altered = TRUE; - } if (current_expression->save) { MonoInst *store; MonoInst *moved_expression = mono_mempool_alloc (area->cfg->mempool, sizeof (MonoInst)); @@ -1627,11 +1936,33 @@ static void code_motion (MonoSsapreWorkArea *area) { store->next = current_bb->bb->code; current_bb->bb->code = store; } + MONO_VARINFO (area->cfg, current_expression->variable_index)->def = store; mono_compile_make_var_load (area->cfg, current_expression->occurrence, current_expression->variable_index); - + if (current_expression->father_in_tree != NULL) { + handle_father_expression (area, current_expression, store); + } + area->saved_occurrences ++; altered = TRUE; } + if (current_expression->reload) { + gssize variable_index; + if (current_expression->defined_by_phi != NULL) { + variable_index = current_expression->defined_by_phi->phi_variable_index; + } else if (current_expression->defined_by_real_occurrence != NULL) { + variable_index = current_expression->defined_by_real_occurrence->variable_index; + } else { + variable_index = BOTTOM_REDUNDANCY_CLASS; + g_assert_not_reached (); + } + mono_compile_make_var_load (area->cfg, current_expression->occurrence, variable_index); + if (current_expression->father_in_tree != NULL) { + handle_father_expression (area, current_expression, current_expression->previous_tree); + } + + area->reloaded_occurrences ++; + altered = TRUE; + } if (! altered) { area->unaltered_occurrences ++; } @@ -1652,8 +1983,9 @@ static void code_motion (MonoSsapreWorkArea *area) { expression_description.right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE; } - inserted_expression = create_expression (area, &expression_description); + inserted_expression = create_expression (area, &expression_description, &prototype_occurrence); store = mono_compile_create_var_store (area->cfg, current_bb->phi_argument_variable_index, inserted_expression); + MONO_VARINFO (area->cfg, current_bb->phi_argument_variable_index)->def = store; store->next = NULL; mono_add_ins_to_end (current_bb->bb, store); @@ -1663,11 +1995,13 @@ static void code_motion (MonoSsapreWorkArea *area) { } /* - * Perform all SSAPRE steps for an expression + * Perform all SSAPRE steps for the current expression */ static void -process_expression (MonoSsapreWorkArea *area, MonoSsapreExpression *expression) { - if (area->cfg->verbose_level >= TRACE_LEVEL) { +process_expression (MonoSsapreWorkArea *area) { + MonoSsapreExpression *expression = area->current_expression; + + if (area->cfg->verbose_level >= STATISTICS_LEVEL) { printf ("SSAPRE STARTS PROCESSING EXPRESSION "); print_expression_description (&(expression->description)); printf ("\n"); @@ -1688,8 +2022,14 @@ process_expression (MonoSsapreWorkArea *area, MonoSsapreExpression *expression) down_safety (area); compute_can_be_available (area); compute_later (area); - finalize (area); - code_motion (area); + if (finalize (area)) { + code_motion (area); + } else { + if (area->cfg->verbose_level >= TRACE_LEVEL) { + printf ("SSAPRE CODE MOTION SKIPPED\n"); + } + } + if (area->cfg->verbose_level >= DUMP_LEVEL) { printf ("START DUMP OF BB INFOS\n"); @@ -1713,31 +2053,16 @@ process_expression (MonoSsapreWorkArea *area, MonoSsapreExpression *expression) } } -/* - * Perform all SSAPRE steps for all the expressions in the worklist - */ -static void -process_worklist (MonoSsapreWorkArea *area, MonoSsapreExpression *expression) { - if (expression != NULL) { - process_worklist (area, expression->previous); - process_expression (area, expression); - process_worklist (area, expression->next); - } -} - -/* - * Hack to apply SSAPRE only to a given method (invaluable in debugging) - */ -#define APPLY_SSAPRE_TO_SINGLE_METHOD 0 -#if (APPLY_SSAPRE_TO_SINGLE_METHOD) -static char *mono_ssapre_method_name = NULL; +#if (MONO_APPLY_SSAPRE_TO_SINGLE_METHOD) +static char* +mono_ssapre_method_name = NULL; static gboolean check_ssapre_method_name (MonoCompile *cfg) { if (mono_ssapre_method_name == NULL) { mono_ssapre_method_name = getenv ("MONO_SSAPRE_METHOD_NAME"); } if (mono_ssapre_method_name != NULL) { char *method_name = mono_method_full_name (cfg->method, TRUE); - if (strstr (mono_ssapre_method_name, method_name) != NULL) { + if (strstr (method_name, mono_ssapre_method_name) != NULL) { return TRUE; } else { return FALSE; @@ -1754,12 +2079,14 @@ static gboolean check_ssapre_method_name (MonoCompile *cfg) { void mono_perform_ssapre (MonoCompile *cfg) { MonoSsapreWorkArea area; - MonoSsapreExpressionOccurrence *current_occurrence; int dt_dfn, descendants, block, i; -#if (APPLY_SSAPRE_TO_SINGLE_METHOD) +#if (MONO_APPLY_SSAPRE_TO_SINGLE_METHOD) if (! check_ssapre_method_name (cfg)) return; #endif +#if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION) + area.expression_is_handled_father = FALSE; +#endif area.cfg = cfg; area.mempool = mono_mempool_new (); @@ -1780,11 +2107,17 @@ mono_perform_ssapre (MonoCompile *cfg) { if (area.cfg->verbose_level >= LOG_LEVEL) { printf ("SSAPRE STARTS PROCESSING METHOD %s\n", mono_method_full_name (cfg->method, TRUE)); } + if (area.cfg->verbose_level >= DUMP_LEVEL) { + mono_print_code (area.cfg, "BEFORE SSAPRE"); + } - current_occurrence = (MonoSsapreExpressionOccurrence*) mono_mempool_alloc (area.mempool, sizeof (MonoSsapreExpressionOccurrence)); + area.first_in_queue = NULL; + area.last_in_queue = NULL; + area.current_occurrence = (MonoSsapreExpressionOccurrence*) mono_mempool_alloc (area.mempool, sizeof (MonoSsapreExpressionOccurrence)); dt_dfn = 0; descendants = 0; - process_bb (&area, cfg->bblocks [0], &dt_dfn, &descendants, current_occurrence); + area.dt_depth = 0; + process_bb (&area, cfg->bblocks [0], &dt_dfn, &descendants, 1); for (block = 0; block < area.num_bblocks; block++) { MonoSsapreBBInfo *bb_info = &(area.bb_infos [block]); MonoBasicBlock *bb = bb_info->bb; @@ -1807,11 +2140,30 @@ mono_perform_ssapre (MonoCompile *cfg) { printf ("SSAPRE END WORKLIST\n"); } - process_worklist (&area, area.worklist); +#if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION) + area.expression_is_handled_father = TRUE; +#endif + for (area.current_expression = area.first_in_queue; area.current_expression != NULL; area.current_expression = area.current_expression->next_in_queue) { + process_expression (&area); + } + if (area.cfg->verbose_level >= DUMP_LEVEL) { + mono_print_code (area.cfg, "AFTER SSAPRE"); + } if (area.cfg->verbose_level >= TRACE_LEVEL) { printf ("SSAPRE ENDS PROCESSING METHOD %s\n", mono_method_full_name (cfg->method, TRUE)); } mono_mempool_destroy (area.mempool); } + +#endif /* DISABLE_SSA */ + +#else /* 0 */ + +void +mono_perform_ssapre (MonoCompile *cfg) +{ +} + +#endif /* 0 */