From c5e94f039082de17df10b34a3445c15c0af12f71 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Fri, 8 Sep 2006 17:47:17 +0000 Subject: [PATCH] random scheduler, fix no spillslot coalescing flag --- ir/be/be_t.h | 3 +- ir/be/bechordal_main.c | 3 +- ir/be/belistsched.c | 3 ++ ir/be/belistsched.h | 2 ++ ir/be/bemain.c | 1 + ir/be/beschedrand.c | 78 ++++++++++++++++++++++++++++++++++++++++++ ir/be/bespillslots.c | 5 +-- ir/be/bespillslots.h | 2 +- 8 files changed, 91 insertions(+), 6 deletions(-) create mode 100644 ir/be/beschedrand.c diff --git a/ir/be/be_t.h b/ir/be/be_t.h index 882e3fa9d..b86d4974c 100644 --- a/ir/be/be_t.h +++ b/ir/be/be_t.h @@ -42,7 +42,8 @@ enum { BE_SCHED_SELECT_REGPRESS = 1, BE_SCHED_SELECT_MUCHNIK = 2, BE_SCHED_SELECT_HEUR = 3, - BE_SCHED_SELECT_HMUCHNIK = 4 + BE_SCHED_SELECT_HMUCHNIK = 4, + BE_SCHED_SELECT_RANDOM = 5 }; struct _be_options_t { diff --git a/ir/be/bechordal_main.c b/ir/be/bechordal_main.c index fd8d87479..8dcff9031 100644 --- a/ir/be/bechordal_main.c +++ b/ir/be/bechordal_main.c @@ -766,8 +766,7 @@ static be_ra_timer_t *be_ra_chordal_main(const be_irg_t *bi) BE_TIMER_PUSH(ra_timer.t_spillslots); - if(coalesce_spill_slots) - be_coalesce_spillslots(&chordal_env); + be_coalesce_spillslots(&chordal_env, coalesce_spill_slots); dump(BE_CH_DUMP_SPILLSLOTS, irg, NULL, "-spillslots", dump_ir_block_graph_sched); BE_TIMER_POP(ra_timer.t_spillslots); diff --git a/ir/be/belistsched.c b/ir/be/belistsched.c index 4875439a2..dfaaad37b 100644 --- a/ir/be/belistsched.c +++ b/ir/be/belistsched.c @@ -495,6 +495,9 @@ void list_sched(const be_irg_t *birg, be_options_t *be_opts) case BE_SCHED_SELECT_TRIVIAL: memcpy(&sel, trivial_selector, sizeof(sel)); break; + case BE_SCHED_SELECT_RANDOM: + memcpy(&sel, random_selector, sizeof(sel)); + break; case BE_SCHED_SELECT_REGPRESS: memcpy(&sel, reg_pressure_selector, sizeof(sel)); break; diff --git a/ir/be/belistsched.h b/ir/be/belistsched.h index 57da1ecae..7e5e61509 100644 --- a/ir/be/belistsched.h +++ b/ir/be/belistsched.h @@ -112,6 +112,8 @@ struct _list_sched_selector_t { */ extern const list_sched_selector_t *trivial_selector; +extern const list_sched_selector_t *random_selector; + /** * A selector that tries to minimize the register pressure. * @note Not really operational yet. diff --git a/ir/be/bemain.c b/ir/be/bemain.c index 3f30e7089..47e37b66b 100644 --- a/ir/be/bemain.c +++ b/ir/be/bemain.c @@ -135,6 +135,7 @@ static const lc_opt_enum_int_items_t vrfy_items[] = { /* schedule selector options. */ static const lc_opt_enum_int_items_t sched_select_items[] = { { "trivial", BE_SCHED_SELECT_TRIVIAL }, + { "random", BE_SCHED_SELECT_RANDOM }, { "regpress", BE_SCHED_SELECT_REGPRESS }, { "muchnik", BE_SCHED_SELECT_MUCHNIK }, { "heur", BE_SCHED_SELECT_HEUR }, diff --git a/ir/be/beschedrand.c b/ir/be/beschedrand.c new file mode 100644 index 000000000..8524abb2c --- /dev/null +++ b/ir/be/beschedrand.c @@ -0,0 +1,78 @@ +/** + * Trivial node selector. + * @author Christian Wuerdig + * @date 29.08.2006 + * @cvs-id $Id$ + */ + +#include + +#include "besched_t.h" +#include "belistsched.h" + +/** + * The random selector: + * Just assure that branches are executed last, otherwise select a random node + */ +static ir_node *random_select(void *block_env, nodeset *ready_set, nodeset *live_set) +{ + const arch_env_t *arch_env = block_env; + ir_node *irn = NULL; + int only_branches_left = 1; + + /* assure that branches and constants are executed last */ + for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) { + if (! arch_irn_class_is(arch_env, irn, branch)) { + only_branches_left = 0; + nodeset_break(ready_set); + break; + } + } + + if(only_branches_left) { + /* at last: schedule branches */ + irn = nodeset_first(ready_set); + nodeset_break(ready_set); + } else { + do { + // take 1 random node + int n = rand() % pset_count(ready_set); + int i = 0; + for(irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) { + if(i == n) { + nodeset_break(ready_set); + break; + } + ++i; + } + } while(arch_irn_class_is(arch_env, irn, branch)); + } + + return irn; +} + +static void *random_init_graph(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg) +{ + srand(time(0)); + return (void *)arch_env; +} + +static void *random_init_block(void *graph_env, ir_node *bl) +{ + return graph_env; +} + +static const list_sched_selector_t random_selector_struct = { + random_init_graph, + random_init_block, + random_select, + NULL, /* to_appear_in_schedule */ + NULL, /* node_ready */ + NULL, /* node_selected */ + NULL, /* exectime */ + NULL, /* latency */ + NULL, /* finish_block */ + NULL /* finish_graph */ +}; + +const list_sched_selector_t *random_selector = &random_selector_struct; diff --git a/ir/be/bespillslots.c b/ir/be/bespillslots.c index 9cbe76e80..cee2464b8 100644 --- a/ir/be/bespillslots.c +++ b/ir/be/bespillslots.c @@ -741,7 +741,7 @@ static void create_memperms(ss_env_t *env) { } } -void be_coalesce_spillslots(const be_chordal_env_t *chordal_env) { +void be_coalesce_spillslots(const be_chordal_env_t *chordal_env, int coalesce_spillslots) { ss_env_t env; obstack_init(&env.obst); @@ -757,7 +757,8 @@ void be_coalesce_spillslots(const be_chordal_env_t *chordal_env) { /* Get initial spill slots */ irg_walk_graph(chordal_env->irg, NULL, collect_spills_walker, &env); - do_greedy_coalescing(&env); + if(coalesce_spillslots) + do_greedy_coalescing(&env); assign_spillslots(&env); diff --git a/ir/be/bespillslots.h b/ir/be/bespillslots.h index 21dce054f..65e8419b7 100644 --- a/ir/be/bespillslots.h +++ b/ir/be/bespillslots.h @@ -12,6 +12,6 @@ /** * Computes the spill offsets for all spill nodes in the irg */ -void be_coalesce_spillslots(const be_chordal_env_t *chordal_env); +void be_coalesce_spillslots(const be_chordal_env_t *chordal_env, int coalesce_spillslots); #endif -- 2.20.1