From e9137de01e1ed5e7a8baee8d23a59e82ad634af5 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Thu, 1 Jun 2006 09:10:55 +0000 Subject: [PATCH] - belady spiller places its copy nodes smarter now - new verifier test, that values in a block aren't used before they are defined --- ir/be/bespillbelady.c | 93 +++++++++++++++++++++++++++++++------------ ir/be/beverify.c | 65 +++++++++++++++++++++--------- ir/be/beverify.h | 6 +-- ir/be/test/Makefile | 2 +- 4 files changed, 117 insertions(+), 49 deletions(-) diff --git a/ir/be/bespillbelady.c b/ir/be/bespillbelady.c index 99c5a9277..cd9d4b0fd 100644 --- a/ir/be/bespillbelady.c +++ b/ir/be/bespillbelady.c @@ -63,7 +63,7 @@ typedef struct _belady_env_t { ir_node *instr; /**< current instruction */ unsigned instr_nr; /**< current instruction number (relative to block start) */ pset *used; /**< holds the values used (so far) in the current BB */ - pset *copies; /**< holds all copies placed due to phi-spilling */ + ir_node **copies; /**< holds all copies placed due to phi-spilling */ spill_env_t *senv; /**< see bespill.h */ } belady_env_t; @@ -343,6 +343,47 @@ static void displace(belady_env_t *bel, workset_t *new_vals, int is_usage) { static void belady(ir_node *blk, void *env); +/** + * Inserts a spill of a value at the earliest possible location in a block. + * That is after the last use of the value or at the beginning of the block if + * there is no use + */ +static ir_node *insert_copy(belady_env_t *env, ir_node *block, ir_node *value) { + ir_node* node; + ir_graph *irg = get_irn_irg(block); + ir_node *copy = be_new_Copy(env->cls, irg, block, value); + + ARR_APP1(ir_node*, env->copies, copy); + + // walk schedule backwards until we find a usage, or until we have reached the first phi + // TODO can we do this faster somehow? This makes insert_copy O(n) in block_size... + sched_foreach_reverse(block, node) { + int i, arity; + + if(is_Phi(node)) { + sched_add_after(node, copy); + goto placed; + } + if(value == node) { + sched_add_after(node, copy); + goto placed; + } + for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { + ir_node *arg = get_irn_n(node, i); + if(arg == value) { + sched_add_after(node, copy); + goto placed; + } + } + } + // we didn't find a use or a phi yet, so place the copy at the beginning of the block + sched_add_before(sched_first(block), copy); + +placed: + + return copy; +} + /** * Collects all values live-in at block @p blk and all phi results in this block. * Then it adds the best values (at most n_regs) to the blocks start_workset. @@ -350,8 +391,8 @@ static void belady(ir_node *blk, void *env); * their args to break interference and make it possible to spill them to the * same spill slot. */ -static block_info_t *compute_block_start_info(ir_node *blk, void *env) { - belady_env_t *bel = env; +static block_info_t *compute_block_start_info(ir_node *blk, void *data) { + belady_env_t *env = data; ir_node *irn, *first; irn_live_t *li; int i, count, ws_count; @@ -365,7 +406,7 @@ static block_info_t *compute_block_start_info(ir_node *blk, void *env) { return res; /* Create the block info for this block. */ - res = new_block_info(&bel->ob); + res = new_block_info(&env->ob); set_block_info(blk, res); @@ -376,9 +417,9 @@ static block_info_t *compute_block_start_info(ir_node *blk, void *env) { first = sched_first(blk); count = 0; sched_foreach(blk, irn) { - if (is_Phi(irn) && arch_get_irn_reg_class(bel->arch, irn, -1) == bel->cls) { + if (is_Phi(irn) && arch_get_irn_reg_class(env->arch, irn, -1) == env->cls) { loc.irn = irn; - loc.time = get_distance(bel, first, 0, irn, 0); + loc.time = get_distance(env, first, 0, irn, 0); obstack_grow(&ob, &loc, sizeof(loc)); DBG((dbg, DBG_START, " %+F:\n", irn)); count++; @@ -387,9 +428,9 @@ static block_info_t *compute_block_start_info(ir_node *blk, void *env) { } live_foreach(blk, li) { - if (live_is_in(li) && arch_get_irn_reg_class(bel->arch, li->irn, -1) == bel->cls) { + 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(bel, first, 0, li->irn, 0); + 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++; @@ -407,25 +448,26 @@ static block_info_t *compute_block_start_info(ir_node *blk, void *env) { /* if pred block has not been processed yet, do it now */ if (! pred_info) { - belady(pred_blk, bel); + belady(pred_blk, env); pred_info = get_block_info(pred_blk); } /* now we have an end_set of pred */ assert(pred_info->ws_end && "The recursive call (above) is supposed to compute an end_set"); - res->ws_start = workset_clone(&bel->ob, pred_info->ws_end); + 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' */ { /* Copy the best ones from starters to start workset */ - ws_count = MIN(count, bel->n_regs); - res->ws_start = new_workset(&bel->ob, bel); + ws_count = MIN(count, env->n_regs); + res->ws_start = new_workset(&env->ob, env); workset_bulk_fill(res->ws_start, ws_count, starters); } + /* 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. @@ -440,14 +482,11 @@ static block_info_t *compute_block_start_info(ir_node *blk, void *env) { DBG((dbg, DBG_START, "For %+F:\n", irn)); for (max=get_irn_arity(irn), o=0; ocls, irg, pred_block, arg); - pset_insert_ptr(bel->copies, cpy); - DBG((dbg, DBG_START, " place a %+F of %+F in %+F\n", cpy, arg, pred_block)); - /* TODO: Place copies before jumps! */ - sched_add_before(sched_last(pred_block), cpy); - set_irn_n(irn, o, cpy); + ir_node *arg = get_irn_n(irn, o); + ir_node* copy = insert_copy(env, pred_block, arg); + + set_irn_n(irn, o, copy); } } @@ -582,17 +621,18 @@ next_value: /** * Removes all copies introduced for phi-spills */ -static void remove_copies(belady_env_t *bel) { - ir_node *irn; +static void remove_copies(belady_env_t *env) { + int i; - foreach_pset(bel->copies, irn) { + for(i = 0; i < ARR_LEN(env->copies); ++i) { + ir_node *node = env->copies[i]; ir_node *src; const ir_edge_t *edge, *ne; - assert(be_is_Copy(irn)); + assert(be_is_Copy(node)); - src = be_get_Copy_op(irn); - foreach_out_edge_safe(irn, edge, ne) { + src = be_get_Copy_op(node); + foreach_out_edge_safe(node, edge, ne) { ir_node *user = get_edge_src_irn(edge); int user_pos = get_edge_src_pos(edge); @@ -624,7 +664,7 @@ void be_spill_belady_spill_env(const be_chordal_env_t *chordal_env, spill_env_t be_set_is_spilled_phi(bel.senv, is_mem_phi, NULL); } DEBUG_ONLY(be_set_spill_env_dbg_module(bel.senv, dbg);) - bel.copies = pset_new_ptr_default(); + bel.copies = NEW_ARR_F(ir_node*, 0); DBG((dbg, LEVEL_1, "running on register class: %s\n", bel.cls->name)); @@ -634,6 +674,7 @@ void be_spill_belady_spill_env(const be_chordal_env_t *chordal_env, spill_env_t irg_block_walk_graph(chordal_env->irg, fix_block_borders, NULL, &bel); be_insert_spills_reloads(bel.senv); remove_copies(&bel); + DEL_ARR_F(bel.copies); be_remove_dead_nodes_from_schedule(chordal_env->irg); diff --git a/ir/be/beverify.c b/ir/be/beverify.c index e1264181a..853f54a7a 100644 --- a/ir/be/beverify.c +++ b/ir/be/beverify.c @@ -44,29 +44,38 @@ static void print_living_values(FILE *F, pset *live_nodes) /** * Check if number of live nodes never exceeds the number of available registers. */ -static void verify_liveness_walker(ir_node *bl, void *data) +static void verify_liveness_walker(ir_node *block, void *data) { be_verify_register_pressure_env_t *env = (be_verify_register_pressure_env_t *)data; pset *live_nodes = pset_new_ptr_default(); ir_node *irn; + int pressure; /* collect register pressure info, start with end of a block */ - be_liveness_end_of_block(env->arch_env, env->cls, bl, live_nodes); + be_liveness_end_of_block(env->arch_env, env->cls, block, live_nodes); - sched_foreach_reverse(bl, irn) { - int pressure = pset_count(live_nodes); + pressure = pset_count(live_nodes); + if(pressure > env->registers_available) { + ir_fprintf(stderr, "Verify Warning: Register pressure too high at end of block %+F(%s) (%d/%d):\n", + block, get_irg_dump_name(env->irg), pressure, env->registers_available); + print_living_values(stderr, live_nodes); + env->problem_found = 1; + } + sched_foreach_reverse(block, irn) { if (is_Phi(irn)) break; + be_liveness_transfer(env->arch_env, env->cls, irn, live_nodes); + + pressure = pset_count(live_nodes); + if(pressure > env->registers_available) { - ir_fprintf(stderr, "Verify Warning: Register pressure too high at end of block %+F(%s) (%d/%d):\n", - bl, get_irg_dump_name(env->irg), pressure, env->registers_available); + ir_fprintf(stderr, "Verify Warning: Register pressure too high before node %+F in %+F(%s) (%d/%d):\n", + irn, block, get_irg_dump_name(env->irg), pressure, env->registers_available); print_living_values(stderr, live_nodes); env->problem_found = 1; } - - be_liveness_transfer(env->arch_env, env->cls, irn, live_nodes); } del_pset(live_nodes); } @@ -99,35 +108,42 @@ typedef struct be_verify_schedule_env_t_ { /** * Simple schedule checker. */ -static void verify_schedule_walker(ir_node *bl, void *data) +static void verify_schedule_walker(ir_node *block, void *data) { be_verify_schedule_env_t *env = (be_verify_schedule_env_t*) data; - ir_node *irn; + ir_node *node; int non_phi_found = 0; int cfchange_found = 0; // TODO ask ABI about delay branches int delay_branches = 0; + pset *uses = pset_new_ptr_default(); /* - * Make sure that all phi nodes are scheduled at the beginning of the block, and that there - * is 1 or no control flow changing node scheduled and exactly delay_branches operations after it. + * Tests for the following things: + * 1. Make sure that all phi nodes are scheduled at the beginning of the block + * 2. There is 1 or no control flow changing node scheduled and exactly delay_branches operations after it. + * 3. No value is defined after it has been used */ - sched_foreach(bl, irn) { - if (is_Phi(irn)) { + sched_foreach(block, node) { + int i, arity; + + // 1. Check for phis + if (is_Phi(node)) { if (non_phi_found) { ir_fprintf(stderr, "Verify Warning: Phi node %+F scheduled after non-Phi nodes in block %+F (%s)\n", - irn, bl, get_irg_dump_name(env->irg)); + node, block, get_irg_dump_name(env->irg)); env->problem_found = 1; } continue; } non_phi_found = 1; - if (is_cfop(irn) && get_irn_opcode(irn) != iro_Start) { + // 2. Check for control flow changing nodes + if (is_cfop(node) && get_irn_opcode(node) != iro_Start) { /* check, that only one CF operation is scheduled */ if (cfchange_found == 1) { ir_fprintf(stderr, "Verify Warning: More than 1 control flow changing node (%+F) scheduled in block %+F (%s)\n", - irn, bl, get_irg_dump_name(env->irg)); + node, block, get_irg_dump_name(env->irg)); env->problem_found = 1; } cfchange_found = 1; @@ -135,18 +151,29 @@ static void verify_schedule_walker(ir_node *bl, void *data) /* check for delay branches */ if (delay_branches == 0) { ir_fprintf(stderr, "Verify Warning: Node %+F scheduled after control flow changing node (+delay branches) in block %+F (%s)\n", - irn, bl, get_irg_dump_name(env->irg)); + node, block, get_irg_dump_name(env->irg)); env->problem_found = 1; } else { delay_branches--; } } + + // 3. Check for uses + if(pset_find_ptr(uses, node)) { + ir_fprintf(stderr, "Verify Warning: Value %+F used before it was defined in block %+F (%s)\n", + 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)); + } } + del_pset(uses); /* check that all delay branches are used (at least with NOPs) */ if (cfchange_found && delay_branches != 0) { ir_fprintf(stderr, "Not all delay slots filled after jump (%d/%d) in block %+F (%s)\n", - bl, get_irg_dump_name(env->irg)); + block, get_irg_dump_name(env->irg)); env->problem_found = 1; } } diff --git a/ir/be/beverify.h b/ir/be/beverify.h index 238f3a06c..ebfb98008 100644 --- a/ir/be/beverify.h +++ b/ir/be/beverify.h @@ -25,15 +25,15 @@ * @param arch_env An architecture environment * @param cls The register class to check * @param irg The irg to check - * @return 1 on success, 0 otherwise + * @return 1 if the pressure is valid, 0 otherwise */ int be_verify_register_pressure(const arch_env_t *arch_env, const arch_register_class_t* cls, ir_graph *irg); /** * Does some sanity checks on the schedule. * - * @param irg The irg to check - * @return 1 on success, 0 otherwise + * @param irg The irg to check + * @return 1 if the schedule is valid, 0 otherwise */ int be_verify_schedule(ir_graph *irg); diff --git a/ir/be/test/Makefile b/ir/be/test/Makefile index 6babba207..942be40e1 100644 --- a/ir/be/test/Makefile +++ b/ir/be/test/Makefile @@ -3,7 +3,7 @@ EDG=edg GCC=gcc GCC_CFLAGS=-O3 -g -EDG_CFLAGS=-b nomris -f win32 -b ra-chordal-spill=morgan --c -Ic:\\devstudio\\include +EDG_CFLAGS=-f win32 -b ra-chordal-spill=morgan --c -Ic:\\devstudio\\include EXCLUDE=bf_localinit.c bf_store.c calls.c compress95.c convtest.c \ fe_bug.c gnu_def.c harness.c if.c psi_test.c -- 2.20.1