From 05413b49d91e03ba18a82a0ee55b358184e1afc9 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Sun, 27 Aug 2006 18:25:07 +0000 Subject: [PATCH] - Fix perform_memop stuff in bechordal_main after adams gammlig commit - Cleanup remat code a little bit - Adjust remat cost limit to new costs in ia32 backend - Don't spill unused livethroughs around blocks anymore in bespill_morgan (but only around loops), this makes the code faster smaller and the results slightly better as belady performs better for basic blocks --- ir/be/bearch.h | 2 +- ir/be/bechordal_main.c | 8 +++- ir/be/benode.c | 15 +++---- ir/be/bespill.c | 51 ++++++++++++++++-------- ir/be/bespillbelady.c | 2 +- ir/be/bespillmorgan.c | 84 ++++++++-------------------------------- ir/be/ia32/bearch_ia32.c | 2 +- 7 files changed, 67 insertions(+), 97 deletions(-) diff --git a/ir/be/bearch.h b/ir/be/bearch.h index d1f84e552..1804f77cf 100644 --- a/ir/be/bearch.h +++ b/ir/be/bearch.h @@ -209,7 +209,7 @@ typedef struct _arch_inverse_t { typedef enum _arch_irn_flags_t { arch_irn_flags_none = 0, /**< Node flags. */ arch_irn_flags_dont_spill = 1, /**< This must not be spilled. */ - arch_irn_flags_rematerializable = 2, /**< This should be replicated instead of spilled/reloaded. */ + arch_irn_flags_rematerializable = 2, /**< This can be replicated instead of spilled/reloaded. */ arch_irn_flags_ignore = 4, /**< Ignore node during register allocation. */ arch_irn_flags_modify_sp = 8, /**< I modify the stack pointer. */ arch_irn_flags_last = arch_irn_flags_modify_sp diff --git a/ir/be/bechordal_main.c b/ir/be/bechordal_main.c index a7159f971..7849e5991 100644 --- a/ir/be/bechordal_main.c +++ b/ir/be/bechordal_main.c @@ -329,10 +329,16 @@ static void memory_operand_walker(ir_node *irn, void *env) { const arch_env_t *aenv = cenv->birg->main_env->arch_env; const ir_edge_t *edge, *ne; ir_node *block; + ir_node *spill; if (! be_is_Reload(irn)) return; + // only use memory operands, if the reload is only used by 1 node + if(get_irn_n_edges(irn) > 1) + return; + + spill = be_get_Reload_mem(irn); block = get_nodes_block(irn); foreach_out_edge_safe(irn, edge, ne) { @@ -344,7 +350,7 @@ static void memory_operand_walker(ir_node *irn, void *env) { if (get_nodes_block(src) == block && arch_possible_memory_operand(aenv, src, pos)) { DBG((cenv->dbg, LEVEL_3, "performing memory operand %+F at %+F\n", irn, src)); - arch_perform_memory_operand(aenv, src, irn, pos); + arch_perform_memory_operand(aenv, src, spill, pos); } } diff --git a/ir/be/benode.c b/ir/be/benode.c index 00d5c44bb..8e2ba8337 100644 --- a/ir/be/benode.c +++ b/ir/be/benode.c @@ -364,6 +364,7 @@ ir_node *be_new_Reload(const arch_register_class_t *cls, const arch_register_cla init_node_attr(res, 2); be_node_set_reg_class(res, 0, cls_frame); be_node_set_reg_class(res, -1, cls); + be_node_set_flags(res, -1, arch_irn_flags_rematerializable); return res; } @@ -944,22 +945,18 @@ ir_node *be_reload(const arch_env_t *arch_env, const arch_register_class_t *cls, { ir_node *reload; - ir_node *bl = is_Block(insert) ? insert : get_nodes_block(insert); - ir_graph *irg = get_irn_irg(bl); + ir_node *block = get_nodes_block(insert); + ir_graph *irg = get_irn_irg(block); ir_node *frame = get_irg_frame(irg); const arch_register_class_t *cls_frame = arch_get_irn_reg_class(arch_env, frame, -1); assert(be_is_Spill(spill) || (is_Phi(spill) && get_irn_mode(spill) == mode_M)); - reload = be_new_Reload(cls, cls_frame, irg, bl, frame, spill, mode); + reload = be_new_Reload(cls, cls_frame, irg, block, frame, spill, mode); - if(is_Block(insert)) { - insert = sched_skip(insert, 0, sched_skip_cf_predicator, (void *) arch_env); - sched_add_after(insert, reload); - } + assert(!is_Block(insert)); - else - sched_add_before(insert, reload); + sched_add_before(insert, reload); return reload; } diff --git a/ir/be/bespill.c b/ir/be/bespill.c index 449f8ba7a..366439f8a 100644 --- a/ir/be/bespill.c +++ b/ir/be/bespill.c @@ -35,7 +35,7 @@ // only rematerialise when costs are less than REMAT_COST_LIMIT // TODO determine a good value here... -#define REMAT_COST_LIMIT 80 +#define REMAT_COST_LIMIT 20 typedef struct _reloader_t reloader_t; @@ -45,10 +45,16 @@ struct _reloader_t { }; typedef struct _spill_info_t { + /** the value that should get spilled */ ir_node *spilled_node; + /** list of places where the value should get reloaded */ reloader_t *reloaders; + /** the spill node, or a PhiM node */ ir_node *spill; + /** if we had the value of a phi spilled before but not the phi itself then + * this field contains the spill for the phi value */ + ir_node *old_spill; } spill_info_t; struct _spill_env_t { @@ -84,6 +90,7 @@ static spill_info_t *get_spillinfo(const spill_env_t *env, ir_node *value) { if (res == NULL) { info.reloaders = NULL; info.spill = NULL; + info.old_spill = NULL; res = set_insert(env->spills, &info, sizeof(info), hash); } @@ -185,11 +192,19 @@ void be_spill_phi(spill_env_t *env, ir_node *node) { pset_insert_ptr(env->mem_phis, node); // create spillinfos for the phi arguments - get_spillinfo(env, node); + spill_info_t* spill = get_spillinfo(env, node); for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { ir_node *arg = get_irn_n(node, i); get_spillinfo(env, arg); } + + // if we had a spill for the phi value before, then remove this spill from + // schedule, as we will remove it in the insert spill/reload phase + if(spill->spill != NULL && !is_Phi(spill->spill)) { + //sched_remove(spill->spill); + spill->old_spill = spill->spill; + spill->spill = NULL; + } } /* @@ -292,6 +307,17 @@ static void spill_phi(spill_env_t *env, spill_info_t *spillinfo) { set_irn_n(spillinfo->spill, i, arg_info->spill); } + + // rewire reloads from old_spill to phi + if(spillinfo->old_spill != NULL) { + const ir_edge_t *edge, *next; + foreach_out_edge_safe(spillinfo->old_spill, edge, next) { + ir_node* reload = get_edge_src_irn(edge); + assert(be_is_Reload(reload) || is_Phi(reload)); + set_irn_n(reload, get_edge_src_pos(edge), spillinfo->spill); + } + spillinfo->old_spill = NULL; + } } /** @@ -377,15 +403,9 @@ static int is_remat_node(spill_env_t *env, ir_node *node) { assert(!be_is_Spill(node)); - if(be_is_Reload(node)) - return 1; - - // TODO why does arch_irn_is say rematerializable anyway? - if(be_is_Barrier(node)) - return 0; - - if(arch_irn_is(arch_env, node, rematerializable)) + if(arch_irn_is(arch_env, node, rematerializable)) { return 1; + } if(be_is_StackParam(node)) return 1; @@ -416,8 +436,9 @@ static int check_remat_conditions_costs(spill_env_t *env, ir_node *spilled, ir_n } else { costs += arch_get_op_estimated_cost(env->arch_env, spilled); } - if(parentcosts + costs >= REMAT_COST_LIMIT) + if(parentcosts + costs >= REMAT_COST_LIMIT) { return REMAT_COST_LIMIT; + } argremats = 0; for(i = 0, arity = get_irn_arity(spilled); i < arity; ++i) { @@ -435,7 +456,6 @@ static int check_remat_conditions_costs(spill_env_t *env, ir_node *spilled, ir_n } argremats++; - // TODO can we get more accurate costs than +1? costs += check_remat_conditions_costs(env, arg, reloader, parentcosts + costs); if(parentcosts + costs >= REMAT_COST_LIMIT) return REMAT_COST_LIMIT; @@ -536,13 +556,10 @@ void be_insert_spills_reloads(spill_env_t *env) { } del_pset(values); - } - // reloads are placed now, but we might reuse the spill environment for further spilling decisions - del_set(env->spills); - env->spills = new_set(cmp_spillinfo, 1024); + si->reloaders = NULL; + } be_remove_dead_nodes_from_schedule(env->chordal_env->irg); - //be_liveness_add_missing(env->chordal_env->lv); be_liveness_recompute(env->chordal_env->lv); } diff --git a/ir/be/bespillbelady.c b/ir/be/bespillbelady.c index 6462e1b9a..e8fdf8a14 100644 --- a/ir/be/bespillbelady.c +++ b/ir/be/bespillbelady.c @@ -619,7 +619,7 @@ void be_spill_belady_spill_env(const be_chordal_env_t *chordal_env, spill_env_t belady_env_t env; FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady"); - //firm_dbg_set_mask(dbg, DBG_WSETS); + //firm_dbg_set_mask(dbg, DBG_START); /* init belady env */ obstack_init(&env.ob); diff --git a/ir/be/bespillmorgan.c b/ir/be/bespillmorgan.c index 84d103984..db86172ae 100644 --- a/ir/be/bespillmorgan.c +++ b/ir/be/bespillmorgan.c @@ -248,10 +248,6 @@ static bitset_t *construct_block_livethrough_unused(morgan_env_t* env, const ir_ ir_node *irn = be_lv_get_irn(env->cenv->lv, block, i); int node_idx; - /* - if(!live_is_in(li) || !live_is_out(li)) - continue; - */ if(!consider_for_spilling(env->arch, env->cls, irn)) continue; @@ -344,90 +340,42 @@ static bitset_t *construct_loop_livethrough_unused(morgan_env_t *env, const ir_l /*---------------------------------------------------------------------------*/ static int reduce_register_pressure_in_block(morgan_env_t *env, const ir_node* block, int loop_unused_spills_possible) { - int pressure; - ir_node *irn; - int max_pressure = 0; - int spills_needed; + ir_node *node; + int max_pressure; int loop_unused_spills_needed; - block_attr_t *block_attr = get_block_attr(env, block); - int block_unused_spills_possible = bitset_popcnt(block_attr->livethrough_unused); - int unused_spills_possible = loop_unused_spills_possible + block_unused_spills_possible; pset *live_nodes = pset_new_ptr_default(); be_liveness_end_of_block(env->cenv->lv, env->arch, env->cls, block, live_nodes); - pressure = pset_count(live_nodes); + max_pressure = pset_count(live_nodes); DBG((dbg, DBG_LIVE, "Reduce pressure to %d In Block %+F:\n", env->registers_available, block)); /** - * Walk over all irns in the schedule and check register pressure for each of them + * Determine register pressure in block */ - sched_foreach_reverse(block, irn) { - // do we need more spills than possible with unused libethroughs? - int spills_needed = pressure - env->registers_available - unused_spills_possible; - if(spills_needed > 0) { - DBG((dbg, DBG_PRESSURE, "\tWARNING %d more spills needed at %+F\n", spills_needed, irn)); - // TODO further spills needed - //assert(0); - } - if(pressure > max_pressure) { - max_pressure = pressure; - } + sched_foreach_reverse(block, node) { + int pressure; - /* Register pressure is only important until we reach the first phi (the rest of the block - * will only be phis.) - */ - if(is_Phi(irn)) + if(is_Phi(node)) break; - // update pressure - be_liveness_transfer(env->arch, env->cls, irn, live_nodes); + be_liveness_transfer(env->arch, env->cls, node, live_nodes); pressure = pset_count(live_nodes); + if(pressure > max_pressure) + max_pressure = pressure; } + del_pset(live_nodes); DBG((dbg, DBG_PRESSURE, "\tMax Pressure in %+F: %d\n", block, max_pressure)); - /* - * Calculate number of spills from loop_unused_spills_possible that we want to use, - * and spill unused livethroughs from the block if we still don't have enough registers - */ - spills_needed = max_pressure - env->registers_available; - if(spills_needed < 0) { - loop_unused_spills_needed = 0; - } else if(spills_needed > loop_unused_spills_possible) { - int i, spills; - int block_unused_spills_needed; + loop_unused_spills_needed = max_pressure - env->registers_available; + if(loop_unused_spills_needed < 0) { + loop_unused_spills_needed = 0; + } else if(loop_unused_spills_needed > loop_unused_spills_possible) { loop_unused_spills_needed = loop_unused_spills_possible; - block_unused_spills_needed = spills_needed - loop_unused_spills_possible; - if(block_unused_spills_needed > block_unused_spills_possible) { - block_unused_spills_needed = block_unused_spills_possible; - } - - spills = 0; - /* - * Spill/Reload unused livethroughs from the block - */ - bitset_foreach(block_attr->livethrough_unused, i) { - ir_node *to_spill; - const ir_edge_t *edge; - - if(spills >= block_unused_spills_needed) - break; - - to_spill = get_idx_irn(env->irg, i); - foreach_block_succ(block, edge) { - DBG((dbg, DBG_PRESSURE, "Spilling node %+F around block %+F\n", to_spill, block)); - be_add_reload_on_edge(env->senv, to_spill, edge->src, edge->pos); - } - spills++; - } - } else { - loop_unused_spills_needed = spills_needed; } - del_pset(live_nodes); - DBG((dbg, DBG_PRESSURE, "Unused spills for Block %+F needed: %d\n", block, loop_unused_spills_needed)); return loop_unused_spills_needed; } @@ -453,6 +401,7 @@ static int reduce_register_pressure_in_loop(morgan_env_t *env, const ir_loop *lo int needed; assert(is_Block(elem.node)); needed = reduce_register_pressure_in_block(env, elem.node, spills_possible); + assert(needed >= 0); assert(needed <= spills_possible); if(needed > spills_needed) spills_needed = needed; @@ -460,6 +409,7 @@ static int reduce_register_pressure_in_loop(morgan_env_t *env, const ir_loop *lo } case k_ir_loop: { int needed = reduce_register_pressure_in_loop(env, elem.son, spills_possible); + assert(needed >= 0); assert(needed <= spills_possible); if(needed > spills_needed) spills_needed = needed; diff --git a/ir/be/ia32/bearch_ia32.c b/ir/be/ia32/bearch_ia32.c index bd1ffacc7..751e60d6d 100644 --- a/ir/be/ia32/bearch_ia32.c +++ b/ir/be/ia32/bearch_ia32.c @@ -703,7 +703,7 @@ static int ia32_possible_memory_operand(const void *self, const ir_node *irn, un get_irn_arity(irn) != 5 || /* must be a binary operation */ get_ia32_op_type(irn) != ia32_Normal || /* must not already be a addressmode irn */ ! (get_ia32_am_support(irn) & ia32_am_Source) || /* must be capable of source addressmode */ - (i != 2 && i != 3) || /* a "real" operand position must be requested */ + (i != 2 && i != 3) || /* a "real" operand position must be requested */ (i == 2 && ! is_ia32_commutative(irn)) || /* if first operand requested irn must be commutative */ is_ia32_use_frame(irn)) /* must not already use frame */ return 0; -- 2.20.1