From eb285d9224370de02302b8191132928add5a3318 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Thu, 8 Jun 2006 12:12:26 +0000 Subject: [PATCH] - fix wrong verify warnings about phi nodes using values before they are defined - beladie spiller completely ignores ignore register now --- ir/be/bespill.c | 2 +- ir/be/bespillbelady.c | 107 +++++++++++++++--------------------------- ir/be/bespillmorgan.c | 9 ++-- ir/be/beverify.c | 6 ++- 4 files changed, 48 insertions(+), 76 deletions(-) diff --git a/ir/be/bespill.c b/ir/be/bespill.c index e1f93bb34..66c150482 100644 --- a/ir/be/bespill.c +++ b/ir/be/bespill.c @@ -476,7 +476,7 @@ void be_insert_spills_reloads(spill_env_t *env) { for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { ir_node *pred_block = get_Block_cfgpred_block(get_nodes_block(node), i); ir_node *arg = get_irn_n(node, i); - ir_node* copy = insert_copy(env, pred_block, arg); + ir_node *copy = insert_copy(env, pred_block, arg); set_irn_n(node, i, copy); } diff --git a/ir/be/bespillbelady.c b/ir/be/bespillbelady.c index 8727e4fb8..0eaae3b93 100644 --- a/ir/be/bespillbelady.c +++ b/ir/be/bespillbelady.c @@ -70,7 +70,7 @@ typedef struct _belady_env_t { struct _workset_t { belady_env_t *bel; int len; /**< current length */ - loc_t vals[1]; /**< inlined array of the values/distances in this working set */ + loc_t vals[0]; /**< inlined array of the values/distances in this working set */ }; void workset_print(const workset_t *w) @@ -87,7 +87,7 @@ void workset_print(const workset_t *w) */ static INLINE workset_t *new_workset(struct obstack *ob, belady_env_t *bel) { workset_t *res; - size_t size = sizeof(*res) + (bel->n_regs-1)*sizeof(res->vals[0]); + size_t size = sizeof(*res) + (bel->n_regs)*sizeof(res->vals[0]); res = obstack_alloc(ob, size); memset(res, 0, size); res->bel = bel; @@ -99,7 +99,7 @@ static INLINE workset_t *new_workset(struct obstack *ob, belady_env_t *bel) { */ static INLINE workset_t *workset_clone(struct obstack *ob, workset_t *ws) { workset_t *res; - size_t size = sizeof(*res) + (ws->bel->n_regs-1)*sizeof(res->vals[0]); + size_t size = sizeof(*res) + (ws->bel->n_regs)*sizeof(res->vals[0]); res = obstack_alloc(ob, size); memcpy(res, ws, size); return res; @@ -110,7 +110,7 @@ static INLINE workset_t *workset_clone(struct obstack *ob, workset_t *ws) { * returns @param tgt for convinience */ static INLINE workset_t *workset_copy(workset_t *tgt, workset_t *src) { - size_t size = sizeof(*src) + (src->bel->n_regs-1)*sizeof(src->vals[0]); + size_t size = sizeof(*src) + (src->bel->n_regs)*sizeof(src->vals[0]); memcpy(tgt, src, size); return tgt; } @@ -130,7 +130,7 @@ static INLINE workset_t *workset_copy(workset_t *tgt, workset_t *src) { static INLINE void workset_insert(workset_t *ws, ir_node *val) { int i; /* check for current regclass */ - if (arch_get_irn_reg_class(ws->bel->arch, val, -1) != ws->bel->cls) { + if (!arch_irn_consider_in_reg_alloc(ws->bel->arch, ws->bel->cls, val)) { DBG((dbg, DBG_WORKSET, "Dropped %+F\n", val)); return; } @@ -145,40 +145,6 @@ static INLINE void workset_insert(workset_t *ws, ir_node *val) { ws->vals[ws->len++].irn = val; } -/** - * Inserts all values in array @p vals of length @p cnt - * into the workset. There must be enough space for the - * entries. - */ -static INLINE void workset_bulk_insert(workset_t *ws, int cnt, ir_node **vals) { - int i, o; - - for(o=0; obel->arch, val, -1) != ws->bel->cls) { - DBG((dbg, DBG_TRACE, "Wrong reg class\n")); - goto no_insert; - } - - /* check if val is already contained */ - for(i=0; ilen; ++i) - if (ws->vals[i].irn == val) { - DBG((dbg, DBG_TRACE, "Already contained\n")); - goto no_insert; - } - - /* insert val */ - assert(ws->len < ws->bel->n_regs && "Workset does not have enough room!"); - ws->vals[ws->len++].irn = val; - DBG((dbg, DBG_TRACE, "Inserted\n")); - -no_insert: - /*epsilon statement :)*/; - } -} - /** * Removes all entries from this workset */ @@ -189,18 +155,21 @@ no_insert: */ static INLINE void workset_remove(workset_t *ws, ir_node *val) { int i; - for(i=0; ilen; ++i) + for(i=0; ilen; ++i) { if (ws->vals[i].irn == val) { ws->vals[i] = ws->vals[--ws->len]; return; } + } } static INLINE int workset_contains(const workset_t *ws, const ir_node *val) { int i; - for(i=0; ilen; ++i) + for(i=0; ilen; ++i) { if (ws->vals[i].irn == val) return 1; + } + return 0; } @@ -242,13 +211,11 @@ static INLINE void *new_block_info(struct obstack *ob) { */ static INLINE unsigned get_distance(belady_env_t *bel, const ir_node *from, unsigned from_step, const ir_node *def, int skip_from_uses) { - arch_irn_flags_t fl = arch_irn_get_flags(bel->arch, def); unsigned dist = be_get_next_use(bel->uses, from, from_step, def, skip_from_uses); - if(!USES_IS_INIFINITE(dist) && (fl & (arch_irn_flags_ignore | arch_irn_flags_dont_spill)) != 0) - return 0; + assert(! (arch_irn_get_flags(bel->arch, def) & (arch_irn_flags_ignore | arch_irn_flags_dont_spill))); - return dist + 1; + return dist; } /** @@ -327,7 +294,8 @@ static void displace(belady_env_t *bel, workset_t *new_vals, int is_usage) { /* * 3. Insert the new values into the workset */ - workset_bulk_insert(bel->ws, demand, to_insert); + for(i = 0; i < demand; ++i) + workset_insert(bel->ws, to_insert[i]); } static void belady(ir_node *blk, void *env); @@ -345,7 +313,6 @@ static block_info_t *compute_block_start_info(ir_node *blk, void *data) { irn_live_t *li; int i, count, ws_count; loc_t loc, *starters; - ir_graph *irg = get_irn_irg(blk); struct obstack ob; block_info_t *res = get_block_info(blk); @@ -357,7 +324,6 @@ static block_info_t *compute_block_start_info(ir_node *blk, void *data) { res = new_block_info(&env->ob); set_block_info(blk, res); - /* Get all values living at the block start sorted by next use*/ obstack_init(&ob); @@ -365,24 +331,25 @@ static block_info_t *compute_block_start_info(ir_node *blk, void *data) { first = sched_first(blk); count = 0; sched_foreach(blk, irn) { - if (is_Phi(irn) && arch_get_irn_reg_class(env->arch, irn, -1) == env->cls) { - loc.irn = irn; - loc.time = get_distance(env, first, 0, irn, 0); - obstack_grow(&ob, &loc, sizeof(loc)); - DBG((dbg, DBG_START, " %+F:\n", irn)); - count++; - } else + if(!is_Phi(irn) || !arch_irn_consider_in_reg_alloc(env->arch, env->cls, irn)) break; + + loc.irn = irn; + loc.time = get_distance(env, first, 0, irn, 0); + obstack_grow(&ob, &loc, sizeof(loc)); + DBG((dbg, DBG_START, " %+F:\n", irn)); + count++; } live_foreach(blk, li) { - if (live_is_in(li) && arch_get_irn_reg_class(env->arch, li->irn, -1) == env->cls) { - loc.irn = (ir_node *)li->irn; - loc.time = get_distance(env, first, 0, li->irn, 0); - obstack_grow(&ob, &loc, sizeof(loc)); - DBG((dbg, DBG_START, " %+F:\n", li->irn)); - count++; - } + if (!live_is_in(li) || !arch_irn_consider_in_reg_alloc(env->arch, env->cls, li->irn)) + continue; + + loc.irn = (ir_node *)li->irn; + loc.time = get_distance(env, first, 0, li->irn, 0); + obstack_grow(&ob, &loc, sizeof(loc)); + DBG((dbg, DBG_START, " %+F:\n", li->irn)); + count++; } starters = obstack_finish(&ob); @@ -404,10 +371,8 @@ static block_info_t *compute_block_start_info(ir_node *blk, void *data) { assert(pred_info->ws_end && "The recursive call (above) is supposed to compute an end_set"); res->ws_start = workset_clone(&env->ob, pred_info->ws_end); - } else - - /* Else we want the start_set to be the values used 'the closest' */ - { + } else { + /* Else we want the start_set to be the values used 'the closest' */ /* Copy the best ones from starters to start workset */ ws_count = MIN(count, env->n_regs); res->ws_start = new_workset(&env->ob, env); @@ -415,7 +380,6 @@ static block_info_t *compute_block_start_info(ir_node *blk, void *data) { } - /* The phis of this block which are not in the start set have to be spilled later. * Therefore we add temporary copies in the pred_blocks so the spills can spill * into the same spill slot. @@ -466,6 +430,7 @@ static void belady(ir_node *blk, void *env) { bel->instr_nr = 0; new_vals = new_workset(&bel->ob, bel); sched_foreach(blk, irn) { + int i, arity; assert(workset_get_length(bel->ws) <= bel->n_regs && "Too much values in workset!"); /* projs are handled with the tuple value. @@ -482,7 +447,9 @@ static void belady(ir_node *blk, void *env) { /* allocate all values _used_ by this instruction */ workset_clear(new_vals); - workset_bulk_insert(new_vals, get_irn_arity(irn)+1, get_irn_in(irn)); + for(i = 0, arity = get_irn_arity(irn); i < arity; ++i) { + workset_insert(new_vals, get_irn_n(irn, i)); + } displace(bel, new_vals, 1); /* allocate all values _defined_ by this instruction */ @@ -545,7 +512,7 @@ static void fix_block_borders(ir_node *blk, void *env) { goto next_value; } - /* irnb is in memory at the end of pred, so we have to reload it */ + /* irnb is not in memory at the end of pred, so we have to reload it */ DBG((dbg, DBG_FIX, " reload %+F\n", irnb)); be_add_reload_on_edge(bel->senv, irnb, blk, i); @@ -568,7 +535,7 @@ void be_spill_belady_spill_env(const be_chordal_env_t *chordal_env, spill_env_t obstack_init(&bel.ob); bel.arch = chordal_env->birg->main_env->arch_env; bel.cls = chordal_env->cls; - bel.n_regs = arch_register_class_n_regs(bel.cls); + bel.n_regs = arch_count_non_ignore_regs(bel.arch, bel.cls); bel.ws = new_workset(&bel.ob, &bel); bel.uses = be_begin_uses(chordal_env->irg, chordal_env->birg->main_env->arch_env, bel.cls); if(spill_env == NULL) { diff --git a/ir/be/bespillmorgan.c b/ir/be/bespillmorgan.c index 9277e24dc..86c03423e 100644 --- a/ir/be/bespillmorgan.c +++ b/ir/be/bespillmorgan.c @@ -364,6 +364,9 @@ static int reduce_register_pressure_in_block(morgan_env_t *env, ir_node* block, 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)); + if(is_Phi(to_spill)) { + be_spill_phi(env->senv, to_spill); + } be_add_reload_on_edge(env->senv, to_spill, edge->src, edge->pos); } } @@ -485,6 +488,9 @@ void be_spill_morgan(const be_chordal_env_t *chordal_env) { assert(be_verify_schedule(env.irg)); } + // we have to remove dead nodes from schedule to not confuse liveness calculation + be_remove_dead_nodes_from_schedule(env.irg); + // cleanup be_dump(env.irg, "-spillmorgan", dump_ir_block_graph_sched); free_loop_out_edges(&env); @@ -492,9 +498,6 @@ void be_spill_morgan(const be_chordal_env_t *chordal_env) { del_set(env.block_attr_set); // fix the remaining places with too high register pressure with beladies algorithm - - // we have to remove dead nodes from schedule to not confuse liveness calculation - be_remove_dead_nodes_from_schedule(env.irg); be_liveness(env.irg); be_spill_belady_spill_env(chordal_env, env.senv); diff --git a/ir/be/beverify.c b/ir/be/beverify.c index cbf675bf8..3b3b153bf 100644 --- a/ir/be/beverify.c +++ b/ir/be/beverify.c @@ -164,8 +164,10 @@ static void verify_schedule_walker(ir_node *block, void *data) node, block, get_irg_dump_name(env->irg)); env->problem_found = 1; } - for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { - pset_insert_ptr(uses, get_irn_n(node, i)); + if(!is_Phi(node)) { + for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { + pset_insert_ptr(uses, get_irn_n(node, i)); + } } } del_pset(uses); -- 2.20.1