#include <mono/metadata/debug-helpers.h>
#include <mono/metadata/opcodes.h>
+#include "config.h"
+
+#ifndef DISABLE_SSA
#include "inssel.h"
#include "ssapre.h"
-extern guint8 mono_burg_arity [];
-
/* Logging conditions */
#define DUMP_LEVEL (4)
#define TRACE_LEVEL (3)
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));
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);
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);
- }
}
}
static void
analyze_expression (MonoInst *expression, MonoSsapreExpressionDescription *result) {
switch (expression->opcode) {
+#define SSAPRE_SPECIFIC_OPS 1
#define OPDEF(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) case a1:
-#include "ssapre-cee-ops.h"
+#include "simple-cee-ops.h"
#undef OPDEF
#define MINI_OP(a1,a2) case a1:
-#include "ssapre-mini-ops.h"
+#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) ||
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 {
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 {
* 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.
*/
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 {
*/
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 {
* (with all the info that comes from the MonoBasicBlock).
*/
static void
-process_bb (MonoSsapreWorkArea *area, MonoBasicBlock *bb, int *dt_dfn, int *upper_descendants) {
+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->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) {
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 (area->cfg->vars [variable_index]->def_bb == NULL) {
+ 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);
}
- area->cfg->vars [variable_index]->def_bb = bb_info->bb;
+ MONO_VARINFO (area->cfg, variable_index)->def_bb = bb_info->bb;
}
}
break;
}
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)) {
- process_bb (area, (MonoBasicBlock*) (dominated_bb->data), dt_dfn, &descendants);
+ 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);
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;
} 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
*/
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);
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) {
}
}
+ 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--;
+ }
}
/*
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).
}
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);
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
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) {
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;
}
(! ((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 {
}
}
+#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;
}
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;
+ }
}
/*
if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) {
original_variable_index = new_var->inst_c0;
}
- area->cfg->vars [new_var->inst_c0]->reg = original_variable_index;
- area->cfg->vars [new_var->inst_c0]->def_bb = current_bb->bb;
+ 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;
}
if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) {
original_variable_index = new_var->inst_c0;
}
- area->cfg->vars [new_var->inst_c0]->reg = original_variable_index;
- area->cfg->vars [new_var->inst_c0]->def_bb = current_bb->bb;
+ 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;
}
if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) {
original_variable_index = new_var->inst_c0;
}
- area->cfg->vars [new_var->inst_c0]->reg = original_variable_index;
- area->cfg->vars [new_var->inst_c0]->def_bb = current_bb->bb;
+ 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;
}
int in_bb;
NEW_INST (phi, OP_PHI);
- phi->inst_c0 = area->cfg->vars [current_bb->phi_variable_index]->reg;
+ 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++) {
store->next = current_bb->bb->code;
current_bb->bb->code = store;
}
- area->cfg->vars [current_bb->phi_variable_index]->def = store;
+ MONO_VARINFO (area->cfg, current_bb->phi_variable_index)->def = store;
current_bb->phi_insertion_point = store;
area->added_phis ++;
store->next = current_bb->bb->code;
current_bb->bb->code = store;
}
- area->cfg->vars [current_expression->variable_index]->def = 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);
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);
- area->cfg->vars [current_bb->phi_argument_variable_index]->def = store;
+ MONO_VARINFO (area->cfg, current_bb->phi_argument_variable_index)->def = store;
store->next = NULL;
mono_add_ins_to_end (current_bb->bb, store);
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");
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");
+ }
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);
+ 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;
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 */
+
projects / mono.git / blobdiff