X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbechordal_main.c;h=cec2bde7e3881799c4fb10333b0eb9e3f5a3286c;hb=e7cad2f17cb3e282d309bf95475a83f944236a6f;hp=7636168933ba0923a319707af9be2e64bcacd291;hpb=20c4c0094939c31f7ffbff1ad013466f9a16c065;p=libfirm

diff --git a/ir/be/bechordal_main.c b/ir/be/bechordal_main.c
index 763616893..cec2bde7e 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"
@@ -45,15 +47,19 @@
 #include "beifg_impl.h"
 
 #include "bespillbelady.h"
+#include "bespillmorgan.h"
 #include "belower.h"
 
 #ifdef WITH_ILP
 #include "bespillilp.h"
+#include "bespillremat.h"
+#include "bespillappel.h"
 #endif /* WITH_ILP */
 
 #include "becopystat.h"
 #include "becopyopt.h"
 #include "bessadestr.h"
+#include "beverify.h"
 
 
 void be_ra_chordal_check(be_chordal_env_t *chordal_env) {
@@ -97,59 +103,6 @@ void be_ra_chordal_check(be_chordal_env_t *chordal_env) {
 	obstack_free(&ob, NULL);
 }
 
-static void check_pressure_walker(ir_node *bl, void *data)
-{
-	be_chordal_env_t *env = data;
-	int n_regs            = arch_register_class_n_regs(env->cls);
-	bitset_t *live        = bitset_irg_malloc(env->irg);
-	int step              = 0;
-	ir_node *irn;
-	bitset_pos_t elm;
-	irn_live_t *li;
-	DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
-
-	live_foreach(bl, li)
-		if(live_is_end(li) && chordal_has_class(env, li->irn))
-			bitset_add_irn(live, li->irn);
-
-	DBG((dbg, LEVEL_1, "end set for %+F\n", bl));
-	bitset_foreach_irn(env->irg, live, elm, irn)
-		DBG((dbg, LEVEL_1, "\t%+F\n", irn));
-
-	sched_foreach_reverse(bl, irn) {
-		int pressure = bitset_popcnt(live);
-		int idx      = get_irn_idx(irn);
-		int i, n;
-
-		DBG((dbg, LEVEL_1, "%+10F@%+10F: pressure %d\n", bl, irn, pressure));
-
-		if(pressure > n_regs) {
-			ir_node *x;
-			ir_printf("%+10F@%+10F: pressure to high: %d\n", bl, irn, pressure);
-			bitset_foreach_irn(env->irg, live, elm, x)
-				ir_fprintf(stderr, "\t%+10F\n", x);
-		}
-
-		if(chordal_has_class(env, irn)) {
-			if(!bitset_is_set(live, idx))
-				ir_fprintf(stderr, "%+F is defined but was not live\n", irn);
-			bitset_remv_irn(live, irn);
-		}
-
-		for(i = 0, n = get_irn_arity(irn); i < n; i++) {
-			ir_node *op = get_irn_n(irn, i);
-			if(chordal_has_class(env, op) && !is_Phi(irn))
-				bitset_add_irn(live, op);
-		}
-		step++;
-	}
-}
-
-void be_check_pressure(const be_chordal_env_t *env)
-{
-	irg_block_walk_graph(env->irg, check_pressure_walker, NULL, (void *) env);
-}
-
 int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b)
 {
 	if(env->ifg)
@@ -165,33 +118,42 @@ static be_ra_chordal_opts_t options = {
 	BE_CH_COPYMIN_HEUR1,
 	BE_CH_IFG_STD,
 	BE_CH_LOWER_PERM_SWAP,
+	BE_CH_VRFY_WARN,
 };
 
 #ifdef WITH_LIBCORE
 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
+	{ "ilp",    BE_CH_SPILL_ILP    },
+	{ "remat",  BE_CH_SPILL_REMAT  },
+	{ "appel",  BE_CH_SPILL_APPEL  },
+#endif /* WITH_ILP */
 	{ NULL, 0 }
 };
 
 static const lc_opt_enum_int_items_t copymin_items[] = {
-	{ "none",  BE_CH_COPYMIN_NONE },
-	{ "heur1", BE_CH_COPYMIN_HEUR1 },
-	{ "heur2", BE_CH_COPYMIN_HEUR2 },
-	{ "stat",  BE_CH_COPYMIN_STAT  },
+	{ "none",  BE_CH_COPYMIN_NONE      },
+	{ "heur1", BE_CH_COPYMIN_HEUR1     },
+	{ "heur2", BE_CH_COPYMIN_HEUR2     },
+	{ "stat",  BE_CH_COPYMIN_STAT      },
+	{ "park",  BE_CH_COPYMIN_PARK_MOON },
 #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[] = {
@@ -205,14 +167,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 }
 };
 
@@ -225,7 +195,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 = {
@@ -236,12 +206,17 @@ 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 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_MASK("spill",	"spill method (belady, ilp, remat or appel)", &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_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),
 	{ NULL }
 };
 
@@ -256,21 +231,22 @@ static void be_ra_chordal_register_options(lc_opt_entry_t *grp)
 
 		lc_opt_add_table(chordal_grp, be_chordal_options);
 	}
+
+	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);
 	}
@@ -296,6 +272,33 @@ FILE *be_chordal_open(const be_chordal_env_t *env, const char *prefix, const cha
 	return fopen(buf, "wt");
 }
 
+void check_ifg_implementations(be_chordal_env_t *chordal_env)
+{
+	FILE *f;
+
+	f = be_chordal_open(chordal_env, "std", "log");
+	chordal_env->ifg = be_ifg_std_new(chordal_env);
+	be_ifg_check_sorted(chordal_env->ifg, f);
+	fclose(f);
+
+	f = be_chordal_open(chordal_env, "list", "log");
+	chordal_env->ifg = be_ifg_list_new(chordal_env);
+	be_ifg_check_sorted(chordal_env->ifg, f);
+	fclose(f);
+
+	f = be_chordal_open(chordal_env, "clique", "log");
+	chordal_env->ifg = be_ifg_clique_new(chordal_env);
+	be_ifg_check_sorted(chordal_env->ifg, f);
+	fclose(f);
+
+	f = be_chordal_open(chordal_env, "pointer", "log");
+	chordal_env->ifg = be_ifg_pointer_new(chordal_env);
+	be_ifg_check_sorted(chordal_env->ifg, f);
+	fclose(f);
+
+	chordal_env->ifg = NULL;
+};
+
 static void be_ra_chordal_main(const be_irg_t *bi)
 {
 	const be_main_env_t *main_env = bi->main_env;
@@ -306,6 +309,9 @@ static void be_ra_chordal_main(const be_irg_t *bi)
 	int j, m;
 	be_chordal_env_t chordal_env;
 
+	//lc_timer_t *timer = lc_timer_register("getTime","get Time of copy minimization using the ifg");
+	//unsigned long elapsed_milisec = 0;
+
 	compute_doms(irg);
 
 	chordal_env.opts          = &options;
@@ -330,6 +336,9 @@ static void be_ra_chordal_main(const be_irg_t *bi)
 
 		/* spilling */
 		switch(options.spill_method) {
+		case BE_CH_SPILL_MORGAN:
+			be_spill_morgan(&chordal_env);
+			break;
 		case BE_CH_SPILL_BELADY:
 			be_spill_belady(&chordal_env);
 			break;
@@ -337,6 +346,12 @@ static void be_ra_chordal_main(const be_irg_t *bi)
 		case BE_CH_SPILL_ILP:
 			be_spill_ilp(&chordal_env);
 			break;
+                case BE_CH_SPILL_REMAT:
+                        be_spill_remat(&chordal_env);
+                        break;
+		case BE_CH_SPILL_APPEL:
+			be_spill_appel(&chordal_env);
+			break;
 #endif /* WITH_ILP */
 		default:
 			fprintf(stderr, "no valid spiller selected. falling back to belady\n");
@@ -344,16 +359,52 @@ static void be_ra_chordal_main(const be_irg_t *bi)
 		}
 		dump(BE_CH_DUMP_SPILL, irg, chordal_env.cls, "-spill", dump_ir_block_graph_sched);
 		be_abi_fix_stack_nodes(bi->abi);
-		be_liveness(irg);
-		be_check_pressure(&chordal_env);
+
+		/* 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");
+		}
 
 		/* Color the graph. */
+		be_liveness(irg);
 		be_ra_chordal_color(&chordal_env);
 		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);
+		/* Check the implementations of the ifg */
+
+		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);
+				//be_ifg_check(chordal_env.ifg);
+				//be_ifg_check_sorted(chordal_env.ifg);
+				break;
+		}
+
+		/* start timer */
+		//lc_timer_reset_and_start(timer);
 
 		/* copy minimization */
 		co = NULL;
@@ -363,6 +414,12 @@ static void be_ra_chordal_main(const be_irg_t *bi)
 			co_build_graph_structure(co);
 		}
 
+		/* stop timer */
+		//lc_timer_stop(timer);
+		//elapsed_milisec = lc_timer_elapsed_msec(timer);
+
+		//ir_printf("%u\n", elapsed_milisec);
+
 		switch(options.copymin_method) {
 			case BE_CH_COPYMIN_HEUR1:
 				co_solve_heuristic(co);