From 9738458b704ed24262f26d20cd7778b13bc21514 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Fri, 16 Feb 2007 08:56:04 +0000 Subject: [PATCH] remove old unused code from belady, improve schedule verifiy in beverify.c, removed the other schedule verifier in besched.c --- ir/be/besched.c | 109 ------------------------------------------ ir/be/besched_t.h | 14 ------ ir/be/bespillbelady.c | 63 +----------------------- ir/be/beverify.c | 43 ++++++++++++++--- 4 files changed, 39 insertions(+), 190 deletions(-) diff --git a/ir/be/besched.c b/ir/be/besched.c index 02bbe7934..93f968220 100644 --- a/ir/be/besched.c +++ b/ir/be/besched.c @@ -79,115 +79,6 @@ void sched_renumber(const ir_node *block) } } -/* Verify a schedule. */ -int sched_verify(const ir_node *block) -{ - int res = 1; - const ir_node *irn; - int i, n; - int *save_time_step; - const ir_node **save_nodes; - const ir_edge_t *edge; - pset *scheduled_nodes = pset_new_ptr_default(); - FIRM_DBG_REGISTER(firm_dbg_module_t *dbg_sched, "firm.be.sched"); - - /* Count the number of nodes in the schedule. */ - n = 0; - sched_foreach(block, irn) - n++; - - if(n <= 0) - return 1; - - save_time_step = xmalloc(n * sizeof(save_time_step[0])); - save_nodes = xmalloc(n * sizeof(save_nodes[0])); - - i = 0; - sched_foreach(block, irn) { - sched_info_t *info = get_irn_sched_info(irn); - save_time_step[i] = info->time_step; - save_nodes[i] = (ir_node *)irn; - info->time_step = i; - pset_insert_ptr(scheduled_nodes, irn); - - i += 1; - } - - /* - * Check if each relevant operand of a node is scheduled before - * the node itself. - */ - sched_foreach(block, irn) { - int i, n; - int step = sched_get_time_step(irn); - - for(i = 0, n = get_irn_arity(irn); i < n; i++) { - ir_node *op = get_irn_n(irn, i); - - if(to_appear_in_schedule(op) - && !is_Phi(irn) - && get_nodes_block(op) == block - && sched_get_time_step(op) > step) { - - DBG((dbg_sched, LEVEL_DEFAULT, - "%+F: %+F is operand of %+F but scheduled after\n", block, op, irn)); - res = 0; - } - } - } - - /* Check, if the time steps are correct */ - for(i = 1; i < n; ++i) { - if(save_time_step[i] - save_time_step[i - 1] <= 0) { - DBG((dbg_sched, LEVEL_DEFAULT, - "%+F from %+F(%d) -> %+F(%d) step shrinks from %d -> %d\n", - block, save_nodes[i - 1], i - 1, save_nodes[i], i, - save_time_step[i - 1], save_time_step[i])); - res = 0; - } - } - - /* Restore the old time steps */ - i = 0; - sched_foreach(block, irn) { - sched_info_t *info = get_irn_sched_info(irn); - info->time_step = save_time_step[i++]; - } - - /* Check for all nodes in the block if they are scheduled. */ - foreach_out_edge(block, edge) { - ir_node *irn = get_edge_src_irn(edge); - if(to_appear_in_schedule(irn) && !pset_find_ptr(scheduled_nodes, irn)) { - DBG((dbg_sched, LEVEL_DEFAULT, - "%+F: %+F is in block but not scheduled\n", block, irn)); - res = 0; - } - } - - del_pset(scheduled_nodes); - free(save_time_step); - free((void *) save_nodes); - return res; -} - -/** - * Block-Walker: verify the current block and update the status - */ -static void sched_verify_walker(ir_node *block, void *data) -{ - int *res = data; - *res &= sched_verify(block); -} - -/* Verify the schedules in all blocks of the irg. */ -int sched_verify_irg(ir_graph *irg) -{ - int res = 1; - irg_block_walk_graph(irg, sched_verify_walker, NULL, &res); - - return res; -} - int sched_skip_cf_predicator(const ir_node *irn, void *data) { arch_env_t *ae = data; return arch_irn_class_is(ae, irn, branch); diff --git a/ir/be/besched_t.h b/ir/be/besched_t.h index 15f201753..033434242 100644 --- a/ir/be/besched_t.h +++ b/ir/be/besched_t.h @@ -252,20 +252,6 @@ static INLINE int _sched_cmp(const ir_node *a, const ir_node *b) return get_irn_sched_info(a)->time_step - get_irn_sched_info(b)->time_step; } -/** - * Verify a schedule. - * @param block The block whose schedule to verify. - * @return 1, if the schedule is proper, 0 if not. - */ -int sched_verify(const ir_node *block); - -/** - * Verify the schedules in all blocks of the irg. - * @param irg The program graph. - * @return 1, if all schedules were right, 0 if not. - */ -int sched_verify_irg(ir_graph *irg); - /** * Checks, if one node is scheduled before another. * @param n1 A node. diff --git a/ir/be/bespillbelady.c b/ir/be/bespillbelady.c index 7f6248b82..8710ccc99 100644 --- a/ir/be/bespillbelady.c +++ b/ir/be/bespillbelady.c @@ -6,7 +6,7 @@ * */ #ifdef HAVE_CONFIG_H -#include "config.h" +#include #endif #ifdef HAVE_ALLOCA_H @@ -87,7 +87,7 @@ static int loc_compare(const void *a, const void *b) return p->time - q->time; } -void workset_print(const workset_t *w) +static INLINE void workset_print(const workset_t *w) { int i; @@ -246,48 +246,6 @@ static INLINE unsigned get_distance(belady_env_t *env, ir_node *from, unsigned f return use.time; } -#if 0 -/** - * Fix to remove dead nodes (especially don't spill nodes) from workset. - */ -static void fix_dead_values(workset_t *ws, ir_node *irn) { - int idx; - ir_node *node; - ir_node *block = get_nodes_block(irn); - - DBG((dbg, DBG_DECIDE, "fixing dead values at %+F:\n", irn)); - - workset_foreach(ws, node, idx) { - const ir_edge_t *edge; - int fixme = 1; - - /* skip already fixed nodes */ - if (workset_get_time(ws, idx) == INT_MAX) - continue; - - /* check all users */ - foreach_out_edge(node, edge) { - ir_node *user = get_edge_src_irn(edge); - - if ((get_nodes_block(user) != block) || /* user is in a different block */ - (sched_is_scheduled(user) && sched_comes_after(irn, user)) || /* user is scheduled after irn */ - user == irn) /* irn is the user */ - { /* => don't fix distance */ - fixme = 0; - break; - } - } - - /* all users scheduled prior to current irn in in same block as irn -> fix */ - if (fixme) { - workset_set_time(ws, idx, INT_MAX); - DBG((dbg, DBG_DECIDE, "\tfixing time for %+F to INT_MAX\n", node)); - } - } - -} -#endif - /** * Performs the actions necessary to grant the request that: * - new_vals can be held in registers @@ -344,19 +302,6 @@ static void displace(belady_env_t *env, workset_t *new_vals, int is_usage) { workset_set_time(ws, i, dist); } -#if 0 - /* - FIX for don't spill nodes: - Problem is that get_distance always returns 0 for those nodes even if they are not - needed anymore (all their usages have already been visited). - Even if we change this behavior, get_distance doesn't distinguish between not - used anymore (dead) and live out of block. - Solution: Set distances of all nodes having all their usages in schedule prior to - current instruction to MAX_INT. - */ - fix_dead_values(ws, env->instr); -#endif - /* sort entries by increasing nextuse-distance*/ workset_sort(ws); @@ -458,10 +403,6 @@ static void compute_live_ins(ir_node *block, void *data) { /* Collect all values living at start of block */ starters = NEW_ARR_F(loc_t, 0); - /* rebuild schedule time information, because it seems to be broken */ - // Matze: is this still true? - //sched_renumber(block); - DBG((dbg, DBG_START, "Living at start of %+F:\n", block)); first = sched_first(block); diff --git a/ir/be/beverify.c b/ir/be/beverify.c index 6f34c2995..a2fe62f8c 100644 --- a/ir/be/beverify.c +++ b/ir/be/beverify.c @@ -6,9 +6,11 @@ * CVS-Id: $Id$ */ #ifdef HAVE_CONFIG_H -#include "config.h" +#include #endif +#include + #include "bitset.h" #include "set.h" #include "array.h" @@ -108,6 +110,7 @@ int be_verify_register_pressure(const be_irg_t *birg, const arch_register_class_ typedef struct be_verify_schedule_env_t_ { int problem_found; /**< flags indicating if there was a problem */ + bitset_t *scheduled; /**< bitset of scheduled nodes */ ir_graph *irg; /**< the irg to check */ } be_verify_schedule_env_t; @@ -121,6 +124,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { int cfchange_found = 0; // TODO ask arch about delay branches int delay_branches = 0; + int last_timestep = INT_MIN; /* * Tests for the following things: @@ -130,8 +134,31 @@ static void verify_schedule_walker(ir_node *block, void *data) { */ sched_foreach(block, node) { int i, arity; + int timestep; + + // this node is scheduled + if(bitset_is_set(env->scheduled, get_irn_idx(node))) { + ir_fprintf(stderr, "Verify warning: %+F appears to be schedule twice\n"); + env->problem_found = 1; + } + bitset_set(env->scheduled, get_irn_idx(node)); + + // Check that scheduled nodes are in the correct block + if(get_nodes_block(node) != block) { + ir_fprintf(stderr, "Verify warning: %+F is in block %+F but scheduled in %+F\n", node, get_nodes_block(node), block); + env->problem_found = 1; + } + + // Check that timesteps are increasing + timestep = sched_get_time_step(node); + if(timestep <= last_timestep) { + ir_fprintf(stderr, "Verify warning: Schedule timestep did not increase at node %+F\n", + node); + env->problem_found = 1; + } + last_timestep = timestep; - // 1. Check for phis + // Check that phis come before any other node 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", @@ -142,7 +169,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { non_phi_found = 1; } - // 2. Check for control flow changing nodes + // 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) { @@ -165,7 +192,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { } } - // 3. Check for uses + // Check that all uses come before their definitions if(!is_Phi(node)) { int nodetime = sched_get_time_step(node); for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { @@ -182,7 +209,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { } } - // 4. check for dead nodes + // Check that no dead nodes are scheduled if(get_irn_n_edges(node) == 0) { ir_fprintf(stderr, "Verify warning: Node %+F is dead but scheduled in block %+F (%s)\n", node, block, get_irg_dump_name(env->irg)); @@ -229,12 +256,15 @@ static int should_be_scheduled(ir_node *node) { static void check_schedule(ir_node *node, void *data) { be_verify_schedule_env_t *env = data; int should_be; + int scheduled; should_be = should_be_scheduled(node); if(should_be == -1) return; - if(should_be ? !sched_is_scheduled(node) : sched_is_scheduled(node)) { + scheduled = bitset_is_set(env->scheduled, get_irn_idx(node)) ? 1 : 0; + should_be = should_be ? 1 : 0; + if(should_be != scheduled) { ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should%s be scheduled\n", node, get_nodes_block(node), get_irg_dump_name(env->irg), should_be ? "" : " not"); env->problem_found = 1; @@ -249,6 +279,7 @@ int be_verify_schedule(ir_graph *irg) be_verify_schedule_env_t env; env.problem_found = 0; + env.scheduled = bitset_alloca(get_irg_last_idx(irg)); env.irg = irg; irg_block_walk_graph(irg, verify_schedule_walker, NULL, &env); -- 2.20.1