From 70f361d8ab87aace8b4de4e44e2911aa3a54c43e Mon Sep 17 00:00:00 2001 From: Sebastian Hack Date: Sun, 16 Mar 2008 14:42:33 +0000 Subject: [PATCH] Belady2 fixes [r18135] --- ir/be/bespill.c | 42 ++++++++++++++++++++++++++++++++++++++++-- ir/be/bespill.h | 9 +++++++++ ir/be/bespillbelady2.c | 37 ++++++++++++++++++++++++++++--------- 3 files changed, 77 insertions(+), 11 deletions(-) diff --git a/ir/be/bespill.c b/ir/be/bespill.c index 9f88ad595..0cef0af5a 100644 --- a/ir/be/bespill.c +++ b/ir/be/bespill.c @@ -205,6 +205,9 @@ void be_add_spill(spill_env_t *env, ir_node *to_spill, ir_node *before) assert(! arch_irn_is(env->arch_env, to_spill, dont_spill)); DB((dbg, LEVEL_1, "Add spill of %+F before %+F\n", to_spill, before)); + /* Just for safety make sure that we do not insert the spill in front of a phi */ + for (; is_Phi(before); before = sched_next(before)); + /* spills that are dominated by others are not needed */ last = NULL; s = spill_info->spills; @@ -443,8 +446,9 @@ static void spill_irn(spill_env_t *env, spill_info_t *spillinfo) ir_node *before = spill->before; /* place all spills before the reloads (as we can't guarantee the - * same order as the be_add_spill and be_add_reload calls */ - while(get_irn_idx(sched_prev(before)) > env->new_nodes_idx) { + * same order as the be_add_spill and be_add_reload calls. + * Also make sure that we do not run into Phis when going up. */ + while(get_irn_idx(sched_prev(before)) > env->new_nodes_idx && !is_Phi(sched_prev(before))) { before = sched_prev(before); } @@ -878,6 +882,40 @@ static void determine_spill_costs(spill_env_t *env, spill_info_t *spillinfo) DB((dbg, LEVEL_1, "spill %+F after definition\n", to_spill)); } +void make_spill_locations_dominate_irn(spill_env_t *env, ir_node *irn) +{ + const spill_info_t *si = get_spillinfo(env, irn); + ir_node *start_block = get_irg_start_block(get_irn_irg(irn)); + int n_blocks = get_Block_dom_max_subtree_pre_num(start_block); + bitset_t *reloads = bitset_alloca(n_blocks); + reloader_t *r; + spill_t *s; + + if (si == NULL) + return; + + /* Fill the bitset with the dominance pre-order numbers + * of the blocks the reloads are located in. */ + for (r = si->reloaders; r != NULL; r = r->next) { + ir_node *bl = get_nodes_block(r->reloader); + bitset_set(reloads, get_Block_dom_tree_pre_num(bl)); + } + + /* Now, cancel out all the blocks that are dominated by each spill. + * If the bitset is not empty after that, we have reloads that are + * not dominated by any spill. */ + for (s = si->spills; s != NULL; s = s->next) { + ir_node *bl = get_nodes_block(s->before); + int start = get_Block_dom_tree_pre_num(bl); + int end = get_Block_dom_max_subtree_pre_num(bl); + + bitset_clear_range(reloads, start, end); + } + + if (!bitset_is_empty(reloads)) + be_add_spill(env, si->to_spill, sched_next(si->to_spill)); +} + void be_insert_spills_reloads(spill_env_t *env) { ir_graph *irg = env->irg; diff --git a/ir/be/bespill.h b/ir/be/bespill.h index 563a9aa5c..5863a887e 100644 --- a/ir/be/bespill.h +++ b/ir/be/bespill.h @@ -146,6 +146,15 @@ typedef struct { double reload_costs; } be_total_spill_costs_t; +/** + * Insert a spill after the definition of the given node if there is a reload that is not dominated by some spill. + * This function checks whether there is a reload that is not dominated by some spill for that node. + * If so, it inserts a spill right after the definition of the node. + * @param env The spill environment. + * @param irn The node to check for. + */ +void make_spill_locations_dominate_irn(spill_env_t *env, ir_node *irn); + /** * Collect spill/reload cost statistics for a graph. * @param birg The backend graph. diff --git a/ir/be/bespillbelady2.c b/ir/be/bespillbelady2.c index 3336458a2..43f72e51b 100644 --- a/ir/be/bespillbelady2.c +++ b/ir/be/bespillbelady2.c @@ -127,15 +127,16 @@ typedef struct _belady_env_t { be_lv_t *lv; ir_exec_freq *ef; - ir_node **blocks; /**< Array of all blocks. */ - int n_blocks; /**< Number of blocks in the graph. */ - int n_regs; /**< number of regs in this reg-class */ - workset_t *ws; /**< the main workset used while processing a block. ob-allocated */ - ir_node *instr; /**< current instruction */ - int instr_nr; /**< current instruction number (relative to block start) */ - - spill_env_t *senv; /**< see bespill.h */ - bitset_t *spilled; /**< bitset to keep all the irns which have already been spilled. */ + ir_node **blocks; /**< Array of all blocks. */ + int n_blocks; /**< Number of blocks in the graph. */ + int n_regs; /**< number of regs in this reg-class */ + workset_t *ws; /**< the main workset used while processing a block. ob-allocated */ + ir_node *instr; /**< current instruction */ + int instr_nr; /**< current instruction number (relative to block start) */ + + spill_env_t *senv; /**< see bespill.h */ + bitset_t *spilled; /**< bitset to keep all the irns which have already been spilled. */ + ir_nodeset_t *extra_spilled; /** All nodes for which a special spill location has been computed. */ } belady_env_t; @@ -1328,6 +1329,7 @@ static void optimize_variable(global_end_state_t *ges, bring_in_t *br) br->first_use, better_spill_loc)); be_add_reload(env->senv, irn, br->first_use, env->cls, 1); be_add_spill(env->senv, irn, sched_next(better_spill_loc)); + ir_nodeset_insert(env->extra_spilled, irn); } /* @@ -1398,8 +1400,10 @@ static bring_in_t **determine_global_order(belady_env_t *env) static void global_assign(belady_env_t *env) { + ir_nodeset_iterator_t iter; global_end_state_t ges; bring_in_t **br; + ir_node *irn; int i, j; /* @@ -1448,6 +1452,10 @@ static void global_assign(belady_env_t *env) be_spill_phi(env->senv, irn); } } + + /* check dominance for specially spilled nodes. */ + foreach_ir_nodeset (env->extra_spilled, irn, iter) + make_spill_locations_dominate_irn(env->senv, irn); } static void collect_blocks(ir_node *bl, void *data) @@ -1490,6 +1498,7 @@ void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls) env.senv = be_new_spill_env(birg); env.ef = be_get_birg_exec_freq(birg); env.spilled = bitset_irg_obstack_alloc(&env.ob, irg); + env.extra_spilled = ir_nodeset_new(64); env.n_blocks = 0; irg_block_walk_graph(irg, NULL, collect_blocks, &env); @@ -1508,11 +1517,21 @@ void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls) global_assign(&env); + /* check dominance for specially spilled nodes. */ + { + ir_nodeset_iterator_t iter; + ir_node *irn; + + foreach_ir_nodeset (env.extra_spilled, irn, iter) + make_spill_locations_dominate_irn(env.senv, irn); + } + /* Insert spill/reload nodes into the graph and fix usages */ be_insert_spills_reloads(env.senv); /* clean up */ be_delete_spill_env(env.senv); + ir_nodeset_del(env.extra_spilled); obstack_free(&env.ob, NULL); } -- 2.20.1