X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=mono%2Fmini%2Fssapre.c;h=e2ea4ec5f86bda6d8a5c990432483076f6249197;hb=824e66edd228b294f297e1d2257342db834a423b;hp=eafdccfa36043fc767ceda2ae9a9e5d38eddc2ef;hpb=de732ca380c880722623be96e9dc4bdead52365f;p=mono.git

diff --git a/mono/mini/ssapre.c b/mono/mini/ssapre.c
index eafdccfa360..e2ea4ec5f86 100644
--- a/mono/mini/ssapre.c
+++ b/mono/mini/ssapre.c
@@ -18,8 +18,6 @@
 
 #include "ssapre.h"
 
-extern guint8 mono_burg_arity [];
-
 /* Logging conditions */
 #define DUMP_LEVEL (4)
 #define TRACE_LEVEL (3)
@@ -53,7 +51,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));
@@ -186,6 +184,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);
@@ -796,7 +799,7 @@ process_inst (MonoSsapreWorkArea *area, MonoInst* inst, MonoInst* previous_inst,
  * (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;
@@ -815,7 +818,7 @@ 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;
 	
@@ -863,9 +866,12 @@ process_bb (MonoSsapreWorkArea *area, MonoBasicBlock *bb, int *dt_dfn, int *uppe
 		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);
+		process_bb (area, (MonoBasicBlock*) (dominated_bb->data), dt_dfn, &descendants, current_depth + 1);
 	}
 	bb_info->dt_descendants = descendants;
 	*upper_descendants += (descendants + 1);
@@ -879,6 +885,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;
@@ -956,6 +963,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
  */
@@ -984,6 +1003,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) {
@@ -1023,15 +1045,59 @@ 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--;
 	}
 }
 
@@ -1064,18 +1130,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).
@@ -1139,7 +1193,11 @@ renaming_pass (MonoSsapreWorkArea *area) {
 		}
 		
 		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);
@@ -1203,6 +1261,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
@@ -1516,6 +1584,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) {
@@ -1539,6 +1611,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;
 	 		}
@@ -1554,6 +1629,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 {
@@ -1611,10 +1692,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;
 	
@@ -1624,7 +1711,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;
+	}
 }
 
 /*
@@ -1921,8 +2015,14 @@ process_expression (MonoSsapreWorkArea *area) {
 	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");
@@ -2000,13 +2100,19 @@ 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) {
+		printf ("BEFORE SSAPRE START\n");
+		mono_print_code (area.cfg);
+		printf ("BEFORE SSAPRE END\n");
+	}
 	
 	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;
@@ -2036,6 +2142,11 @@ mono_perform_ssapre (MonoCompile *cfg) {
 		process_expression (&area);		
 	}
 	
+	if (area.cfg->verbose_level >= DUMP_LEVEL) {
+		printf ("AFTER SSAPRE START\n");
+		mono_print_code (area.cfg);
+		printf ("AFTER SSAPRE END\n");
+	}
 	if (area.cfg->verbose_level >= TRACE_LEVEL) {
 		printf ("SSAPRE ENDS PROCESSING METHOD %s\n", mono_method_full_name (cfg->method, TRUE));
 	}