X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbechordal_main.c;h=1cd4dbebdc2dc00f153e6d927a996f207f6232b7;hb=4a9b94f493b9f161050b2ad406e4c22ea6c81cd5;hp=6f3a4c0636e2eae700f6c7976c0072c0d73b3a0b;hpb=f712b4e87d2a8aa13a45b4a2f5b270f8ed10a7ec;p=libfirm

diff --git a/ir/be/bechordal_main.c b/ir/be/bechordal_main.c
index 6f3a4c063..1cd4dbebd 100644
--- a/ir/be/bechordal_main.c
+++ b/ir/be/bechordal_main.c
@@ -17,10 +17,12 @@
 #include "list.h"
 #include "bitset.h"
 #include "iterator.h"
+#include "firm_config.h"
 
 #ifdef WITH_LIBCORE
 #include <libcore/lc_opts.h>
 #include <libcore/lc_opts_enum.h>
+#include <libcore/lc_timing.h>
 #endif /* WITH_LIBCORE */
 
 #include "irmode_t.h"
@@ -32,6 +34,7 @@
 #include "irbitset.h"
 #include "debug.h"
 #include "xmalloc.h"
+#include "execfreq.h"
 
 #include "bechordal_t.h"
 #include "beabi.h"
@@ -49,7 +52,7 @@
 #include "belower.h"
 
 #ifdef WITH_ILP
-#include "bespillilp.h"
+#include "bespillremat.h"
 #endif /* WITH_ILP */
 
 #include "becopystat.h"
@@ -57,7 +60,6 @@
 #include "bessadestr.h"
 #include "beverify.h"
 
-
 void be_ra_chordal_check(be_chordal_env_t *chordal_env) {
 	const arch_env_t *arch_env = chordal_env->birg->main_env->arch_env;
 	struct obstack ob;
@@ -91,7 +93,7 @@ void be_ra_chordal_check(be_chordal_env_t *chordal_env) {
 		for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o]) {
 			n2_reg = arch_get_irn_register(arch_env, n2);
 			if (values_interfere(n1, n2) && n1_reg == n2_reg) {
-				DBG((dbg, 0, "Values %+F and %+F interfere and have the same register assigned\n", n1, n2));
+				DBG((dbg, 0, "Values %+F and %+F interfere and have the same register assigned: %s\n", n1, n2, n1_reg->name));
 				assert(0 && "Interfering values have the same color!");
 			}
 		}
@@ -111,9 +113,23 @@ int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node
 static be_ra_chordal_opts_t options = {
 	BE_CH_DUMP_NONE,
 	BE_CH_SPILL_BELADY,
-	BE_CH_COPYMIN_HEUR1,
+	BE_CH_COPYMIN_HEUR2,
 	BE_CH_IFG_STD,
 	BE_CH_LOWER_PERM_SWAP,
+	BE_CH_VRFY_WARN,
+};
+
+static be_ra_timer_t ra_timer = {
+	NULL,
+	NULL,
+	NULL,
+	NULL,
+	NULL,
+	NULL,
+	NULL,
+	NULL,
+	NULL,
+	NULL,
 };
 
 #ifdef WITH_LIBCORE
@@ -121,8 +137,8 @@ static const lc_opt_enum_int_items_t spill_items[] = {
 	{ "morgan", BE_CH_SPILL_MORGAN },
 	{ "belady", BE_CH_SPILL_BELADY },
 #ifdef WITH_ILP
-	{ "ilp",	BE_CH_SPILL_ILP },
-#endif
+	{ "remat",  BE_CH_SPILL_REMAT },
+#endif /* WITH_ILP */
 	{ NULL, 0 }
 };
 
@@ -135,14 +151,18 @@ static const lc_opt_enum_int_items_t copymin_items[] = {
 #ifdef WITH_ILP
 	{ "ilp1",  BE_CH_COPYMIN_ILP1 },
 	{ "ilp2",  BE_CH_COPYMIN_ILP2 },
-#endif
+#endif /* WITH_ILP */
 	{ NULL, 0 }
 };
 
 static const lc_opt_enum_int_items_t ifg_flavor_items[] = {
-	{ "std",  BE_CH_IFG_STD },
-	{ "fast", BE_CH_IFG_FAST },
-	{ NULL, 0 }
+	{ "std",     BE_CH_IFG_STD     },
+	{ "fast",    BE_CH_IFG_FAST    },
+	{ "clique",  BE_CH_IFG_CLIQUE  },
+	{ "pointer", BE_CH_IFG_POINTER },
+	{ "list",    BE_CH_IFG_LIST    },
+	{ "check",   BE_CH_IFG_CHECK   },
+	{ NULL,      0                 }
 };
 
 static const lc_opt_enum_int_items_t lower_perm_items[] = {
@@ -156,14 +176,22 @@ static const lc_opt_enum_int_items_t lower_perm_stat_items[] = {
 };
 
 static const lc_opt_enum_int_items_t dump_items[] = {
-	{ "spill",    BE_CH_DUMP_SPILL },
-	{ "live",     BE_CH_DUMP_LIVE },
-	{ "color",    BE_CH_DUMP_COLOR },
-	{ "copymin",  BE_CH_DUMP_COPYMIN },
-	{ "ssadestr", BE_CH_DUMP_SSADESTR },
+	{ "spill",    BE_CH_DUMP_SPILL     },
+	{ "live",     BE_CH_DUMP_LIVE      },
+	{ "color",    BE_CH_DUMP_COLOR     },
+	{ "copymin",  BE_CH_DUMP_COPYMIN   },
+	{ "ssadestr", BE_CH_DUMP_SSADESTR  },
 	{ "tree",     BE_CH_DUMP_TREE_INTV },
-	{ "constr",   BE_CH_DUMP_CONSTR },
-	{ "lower",    BE_CH_DUMP_LOWER },
+	{ "constr",   BE_CH_DUMP_CONSTR    },
+	{ "lower",    BE_CH_DUMP_LOWER     },
+	{ "all",      BE_CH_DUMP_ALL       },
+	{ NULL, 0 }
+};
+
+static const lc_opt_enum_int_items_t be_ch_vrfy_items[] = {
+	{ "off",    BE_CH_VRFY_OFF    },
+	{ "warn",   BE_CH_VRFY_WARN   },
+	{ "assert", BE_CH_VRFY_ASSERT },
 	{ NULL, 0 }
 };
 
@@ -176,7 +204,7 @@ static lc_opt_enum_int_var_t copymin_var = {
 };
 
 static lc_opt_enum_int_var_t ifg_flavor_var = {
-	&options.spill_method, ifg_flavor_items
+	&options.ifg_flavor, ifg_flavor_items
 };
 
 static lc_opt_enum_int_var_t lower_perm_var = {
@@ -187,12 +215,24 @@ static lc_opt_enum_int_var_t dump_var = {
 	&options.dump_flags, dump_items
 };
 
+static lc_opt_enum_int_var_t be_ch_vrfy_var = {
+	&options.vrfy_option, be_ch_vrfy_items
+};
+
+static int be_copymin_stats = 0;
+
+/** Assumed loop iteration count for execution frequency estimation. */
+static int be_loop_weight = 9;
+
 static const lc_opt_table_entry_t be_chordal_options[] = {
-	LC_OPT_ENT_ENUM_MASK("spill",   "spill method (belady or ilp)", &spill_var),
-	LC_OPT_ENT_ENUM_PTR ("copymin", "copymin method (none, heur1, heur2, ilp1, ilp2 or stat)", &copymin_var),
-	LC_OPT_ENT_ENUM_PTR ("ifg",     "interference graph flavour (std or fast)", &ifg_flavor_var),
-	LC_OPT_ENT_ENUM_MASK("perm",    "perm lowering options (copy or swap)", &lower_perm_var),
-	LC_OPT_ENT_ENUM_MASK("dump",    "select dump phases", &dump_var),
+	LC_OPT_ENT_ENUM_INT ("spill",	      "spill method (belady, morgan or remat)", &spill_var),
+	LC_OPT_ENT_ENUM_PTR ("copymin",       "copymin method (none, heur1, heur2, ilp1, ilp2 or stat)", &copymin_var),
+	LC_OPT_ENT_ENUM_PTR ("ifg",           "interference graph flavour (std, fast, clique, pointer, list, check)", &ifg_flavor_var),
+	LC_OPT_ENT_ENUM_PTR ("perm",          "perm lowering options (copy or swap)", &lower_perm_var),
+	LC_OPT_ENT_ENUM_MASK("dump",          "select dump phases", &dump_var),
+	LC_OPT_ENT_ENUM_PTR ("vrfy",          "verify options (off, warn, assert)", &be_ch_vrfy_var),
+	LC_OPT_ENT_BOOL     ("copymin_stats", "dump statistics of copy minimization", &be_copymin_stats),
+	LC_OPT_ENT_INT      ("loop_weight",   "assumed amount of loop iterations for guessing the execution frequency", &be_loop_weight),
 	{ NULL }
 };
 
@@ -210,20 +250,19 @@ static void be_ra_chordal_register_options(lc_opt_entry_t *grp)
 
 	co_register_options(chordal_grp);
 }
-#endif
+#endif /* WITH_LIBCORE */
 
 static void dump(unsigned mask, ir_graph *irg,
 				 const arch_register_class_t *cls,
 				 const char *suffix,
 				 void (*dump_func)(ir_graph *, const char *))
 {
-	if(1 || ((options.dump_flags & mask) == mask)) {
-		if(cls) {
+	if((options.dump_flags & mask) == mask) {
+		if (cls) {
 			char buf[256];
 			snprintf(buf, sizeof(buf), "-%s%s", cls->name, suffix);
 			be_dump(irg, buf, dump_func);
 		}
-
 		else
 			be_dump(irg, suffix, dump_func);
 	}
@@ -249,38 +288,110 @@ FILE *be_chordal_open(const be_chordal_env_t *env, const char *prefix, const cha
 	return fopen(buf, "wt");
 }
 
-static void be_ra_chordal_main(const be_irg_t *bi)
+void check_ifg_implementations(be_chordal_env_t *chordal_env)
 {
-	const be_main_env_t *main_env = bi->main_env;
-	const arch_isa_t    *isa      = arch_env_get_isa(main_env->arch_env);
-	ir_graph            *irg      = bi->irg;
+	FILE *f;
+
+	f = be_chordal_open(chordal_env, "std", "log");
+	chordal_env->ifg = be_ifg_std_new(chordal_env);
+	be_ifg_check_sorted_to_file(chordal_env->ifg, f);
+	fclose(f);
+
+	f = be_chordal_open(chordal_env, "list", "log");
+	be_ifg_free(chordal_env->ifg);
+	chordal_env->ifg = be_ifg_list_new(chordal_env);
+	be_ifg_check_sorted_to_file(chordal_env->ifg, f);
+	fclose(f);
+
+	f = be_chordal_open(chordal_env, "clique", "log");
+	be_ifg_free(chordal_env->ifg);
+	chordal_env->ifg = be_ifg_clique_new(chordal_env);
+	be_ifg_check_sorted_to_file(chordal_env->ifg, f);
+	fclose(f);
+
+	f = be_chordal_open(chordal_env, "pointer", "log");
+	be_ifg_free(chordal_env->ifg);
+	chordal_env->ifg = be_ifg_pointer_new(chordal_env);
+	be_ifg_check_sorted_to_file(chordal_env->ifg, f);
+	fclose(f);
+
+	chordal_env->ifg = NULL;
+};
+
+static be_ra_timer_t *be_ra_chordal_main(const be_irg_t *bi)
+{
+	const be_main_env_t *main_env  = bi->main_env;
+	const arch_isa_t    *isa       = arch_env_get_isa(main_env->arch_env);
+	ir_graph            *irg       = bi->irg;
+	be_options_t        *main_opts = main_env->options;
 	copy_opt_t          *co;
 
 	int j, m;
 	be_chordal_env_t chordal_env;
 
+	if (main_opts->timing == BE_TIME_ON) {
+		ra_timer.t_prolog  = lc_timer_register("prolog",   "regalloc prolog");
+		ra_timer.t_epilog  = lc_timer_register("epilog",   "regalloc epilog");
+		ra_timer.t_live    = lc_timer_register("liveness", "be liveness");
+		ra_timer.t_spill   = lc_timer_register("spill",    "spiller");
+		ra_timer.t_color   = lc_timer_register("color",    "graph coloring");
+		ra_timer.t_ifg     = lc_timer_register("ifg",      "interference graph");
+		ra_timer.t_copymin = lc_timer_register("copymin",  "copy minimization");
+		ra_timer.t_ssa     = lc_timer_register("ssadestr", "ssa destruction");
+		ra_timer.t_verify  = lc_timer_register("verify",   "graph verification");
+		ra_timer.t_other   = lc_timer_register("other",    "other time");
+
+		LC_STOP_AND_RESET_TIMER(ra_timer.t_prolog);
+		LC_STOP_AND_RESET_TIMER(ra_timer.t_epilog);
+		LC_STOP_AND_RESET_TIMER(ra_timer.t_live);
+		LC_STOP_AND_RESET_TIMER(ra_timer.t_spill);
+		LC_STOP_AND_RESET_TIMER(ra_timer.t_color);
+		LC_STOP_AND_RESET_TIMER(ra_timer.t_ifg);
+		LC_STOP_AND_RESET_TIMER(ra_timer.t_copymin);
+		LC_STOP_AND_RESET_TIMER(ra_timer.t_ssa);
+		LC_STOP_AND_RESET_TIMER(ra_timer.t_verify);
+		LC_STOP_AND_RESET_TIMER(ra_timer.t_other);
+	}
+
+#define BE_TIMER_PUSH(timer)  if (main_opts->timing == BE_TIME_ON) lc_timer_push(timer)
+#define BE_TIMER_POP()        if (main_opts->timing == BE_TIME_ON) lc_timer_pop()
+
+	BE_TIMER_PUSH(ra_timer.t_other);
+	BE_TIMER_PUSH(ra_timer.t_prolog);
+
 	compute_doms(irg);
 
-	chordal_env.opts          = &options;
-	chordal_env.irg           = irg;
-	chordal_env.birg          = bi;
-	chordal_env.dom_front     = be_compute_dominance_frontiers(irg);
+	chordal_env.opts      = &options;
+	chordal_env.irg       = irg;
+	chordal_env.birg      = bi;
+	chordal_env.dom_front = be_compute_dominance_frontiers(irg);
+	chordal_env.exec_freq = compute_execfreq(irg, be_loop_weight);
 	FIRM_DBG_REGISTER(chordal_env.dbg, "firm.be.chordal");
 
 	obstack_init(&chordal_env.obst);
 
+	BE_TIMER_POP();
+
 	/* Perform the following for each register class. */
 	for(j = 0, m = arch_isa_get_n_reg_class(isa); j < m; ++j) {
+		FILE *f;
 		chordal_env.cls           = arch_isa_get_reg_class(isa, j);
 		chordal_env.border_heads  = pmap_create();
 		chordal_env.ignore_colors = bitset_malloc(chordal_env.cls->n_regs);
 
+		BE_TIMER_PUSH(ra_timer.t_live);
+
 		/* put all ignore registers into the ignore register set. */
 		put_ignore_colors(&chordal_env);
 
 		be_liveness(irg);
+
+		BE_TIMER_POP();
+
 		dump(BE_CH_DUMP_LIVE, irg, chordal_env.cls, "-live", dump_ir_block_graph_sched);
 
+		BE_TIMER_PUSH(ra_timer.t_spill);
+
 		/* spilling */
 		switch(options.spill_method) {
 		case BE_CH_SPILL_MORGAN:
@@ -290,35 +401,120 @@ static void be_ra_chordal_main(const be_irg_t *bi)
 			be_spill_belady(&chordal_env);
 			break;
 #ifdef WITH_ILP
-		case BE_CH_SPILL_ILP:
-			be_spill_ilp(&chordal_env);
+		case BE_CH_SPILL_REMAT:
+			be_spill_remat(&chordal_env);
 			break;
 #endif /* WITH_ILP */
 		default:
 			fprintf(stderr, "no valid spiller selected. falling back to belady\n");
 			be_spill_belady(&chordal_env);
 		}
+
+		BE_TIMER_POP();
+
 		dump(BE_CH_DUMP_SPILL, irg, chordal_env.cls, "-spill", dump_ir_block_graph_sched);
 		be_abi_fix_stack_nodes(bi->abi);
 
-		assert(be_verify_schedule(irg));
-		assert(be_verify_register_pressure(chordal_env.birg->main_env->arch_env, chordal_env.cls, irg));
+		BE_TIMER_PUSH(ra_timer.t_verify);
 
-		/* Color the graph. */
+		/* verify schedule and register pressure */
+		if (options.vrfy_option == BE_CH_VRFY_WARN) {
+			be_verify_schedule(irg);
+			be_verify_register_pressure(chordal_env.birg->main_env->arch_env, chordal_env.cls, irg);
+		}
+		else if (options.vrfy_option == BE_CH_VRFY_ASSERT) {
+			assert(be_verify_schedule(irg) && "Schedule verification failed");
+			assert(be_verify_register_pressure(chordal_env.birg->main_env->arch_env, chordal_env.cls, irg)
+				&& "Register pressure verification failed");
+		}
+
+		BE_TIMER_POP();
+		BE_TIMER_PUSH(ra_timer.t_live);
 		be_liveness(irg);
+		BE_TIMER_POP();
+		BE_TIMER_PUSH(ra_timer.t_color);
+
+		/* Color the graph. */
 		be_ra_chordal_color(&chordal_env);
+
+		BE_TIMER_POP();
+
 		dump(BE_CH_DUMP_CONSTR, irg, chordal_env.cls, "-color", dump_ir_block_graph_sched);
 
-		/* Build the interference graph. */
-		chordal_env.ifg = be_ifg_std_new(&chordal_env);
-		be_ifg_check(chordal_env.ifg);
+		BE_TIMER_PUSH(ra_timer.t_ifg);
+
+		/* Create the ifg with the selected flavor */
+		switch (options.ifg_flavor) {
+			default:
+				fprintf(stderr, "no valid ifg flavour selected. falling back to std\n");
+			case BE_CH_IFG_STD:
+			case BE_CH_IFG_FAST:
+				chordal_env.ifg = be_ifg_std_new(&chordal_env);
+				break;
+			case BE_CH_IFG_CLIQUE:
+				chordal_env.ifg = be_ifg_clique_new(&chordal_env);
+				break;
+			case BE_CH_IFG_POINTER:
+				chordal_env.ifg = be_ifg_pointer_new(&chordal_env);
+				break;
+			case BE_CH_IFG_LIST:
+				chordal_env.ifg = be_ifg_list_new(&chordal_env);
+				break;
+			case BE_CH_IFG_CHECK:
+				check_ifg_implementations(&chordal_env);
+				/* Build the interference graph. */
+				chordal_env.ifg = be_ifg_std_new(&chordal_env);
+				break;
+		}
+
+
+#if 0
+		{
+			be_ifg_t *std = be_ifg_std_new(&chordal_env);
+			f = be_chordal_open(&chordal_env, "std", "csv");
+			be_ifg_check_sorted_to_file(std, f);
+			be_ifg_free(std);
+			fclose(f);
+		}
+
+		f = be_chordal_open(&chordal_env, "clique", "csv");
+		be_ifg_check_sorted_to_file(chordal_env.ifg, f);
+		fclose(f);
+#endif
+		BE_TIMER_POP();
+
+		BE_TIMER_PUSH(ra_timer.t_verify);
+
+		if (options.vrfy_option != BE_CH_VRFY_OFF)
+			be_ra_chordal_check(&chordal_env);
+
+//		be_ifg_check_sorted(chordal_env.ifg);
+		BE_TIMER_POP();
+		BE_TIMER_PUSH(ra_timer.t_copymin);
 
 		/* copy minimization */
 		co = NULL;
 		if (options.copymin_method != BE_CH_COPYMIN_NONE && options.copymin_method != BE_CH_COPYMIN_STAT) {
+			FILE *f;
 			co = new_copy_opt(&chordal_env, co_get_costs_loop_depth);
 			co_build_ou_structure(co);
 			co_build_graph_structure(co);
+			if(be_copymin_stats) {
+				ir_printf("%40F %20s\n", current_ir_graph, chordal_env.cls->name);
+				printf("max copy costs:         %d\n", co_get_max_copy_costs(co));
+				printf("init copy costs:        %d\n", co_get_copy_costs(co));
+				printf("inevit copy costs:      %d\n", co_get_inevit_copy_costs(co));
+				printf("copy costs lower bound: %d\n", co_get_lower_bound(co));
+			}
+
+#if 0
+			f = be_chordal_open(&chordal_env, "appel-", "apl");
+			co_dump_appel_graph(co, f);
+			fclose(f);
+			f = be_chordal_open(&chordal_env, "appel-clique-", "p");
+			co_dump_appel_graph_cliques(co, f);
+			fclose(f);
+#endif
 		}
 
 		switch(options.copymin_method) {
@@ -349,27 +545,50 @@ static void be_ra_chordal_main(const be_irg_t *bi)
 		}
 
 		if (co) {
+			if(be_copymin_stats) {
+				printf("final copy costs      : %d\n", co_get_copy_costs(co));
+			}
 			co_free_graph_structure(co);
 			co_free_ou_structure(co);
 			free_copy_opt(co);
 		}
 
+		BE_TIMER_POP();
+
 		dump(BE_CH_DUMP_COPYMIN, irg, chordal_env.cls, "-copymin", dump_ir_block_graph_sched);
-		be_ra_chordal_check(&chordal_env);
+
+		BE_TIMER_PUSH(ra_timer.t_verify);
+
+		if (options.vrfy_option != BE_CH_VRFY_OFF)
+			be_ra_chordal_check(&chordal_env);
+
+		BE_TIMER_POP();
+		BE_TIMER_PUSH(ra_timer.t_ssa);
 
 		/* ssa destruction */
 		be_ssa_destruction(&chordal_env);
+
+		BE_TIMER_POP();
+
 		dump(BE_CH_DUMP_SSADESTR, irg, chordal_env.cls, "-ssadestr", dump_ir_block_graph_sched);
-		be_ssa_destruction_check(&chordal_env);
-		be_ra_chordal_check(&chordal_env);
 
-		copystat_dump(irg);
+		BE_TIMER_PUSH(ra_timer.t_verify);
+		if (options.vrfy_option != BE_CH_VRFY_OFF) {
+			be_ssa_destruction_check(&chordal_env);
+			be_ra_chordal_check(&chordal_env);
+		}
+		BE_TIMER_POP();
+
+		if (options.copymin_method == BE_CH_COPYMIN_STAT)
+			copystat_dump(irg);
 
 		be_ifg_free(chordal_env.ifg);
 		pmap_destroy(chordal_env.border_heads);
 		bitset_free(chordal_env.ignore_colors);
 	}
 
+	BE_TIMER_PUSH(ra_timer.t_epilog);
+
 	be_compute_spill_offsets(&chordal_env);
 
 	dump(BE_CH_DUMP_LOWER, irg, NULL, "-spilloff", dump_ir_block_graph_sched);
@@ -379,6 +598,15 @@ static void be_ra_chordal_main(const be_irg_t *bi)
 
 	obstack_free(&chordal_env.obst, NULL);
 	be_free_dominance_frontiers(chordal_env.dom_front);
+	free_execfreq(chordal_env.exec_freq);
+
+	BE_TIMER_POP();
+	BE_TIMER_POP();
+
+#undef BE_TIMER_PUSH
+#undef BE_TIMER_POP
+
+	return main_opts->timing == BE_TIME_ON ? &ra_timer : NULL;
 }
 
 const be_ra_t be_ra_chordal_allocator = {