From fe43982e128771c98ee2b2d4fcc77881e72080e5 Mon Sep 17 00:00:00 2001 From: Michael Beck Date: Sun, 6 Feb 2011 15:05:57 +0000 Subject: [PATCH] Removed unused parameter from_step of be_get_next_use(). Additionally - switched the type of a visitor counter to ir_visited_t - add some doxygen docu [r28328] --- ir/be/bespillbelady.c | 16 +++------ ir/be/bestate.c | 6 ++-- ir/be/beuses.c | 77 ++++++++++++++++++++++++++++++++----------- ir/be/beuses.h | 19 +++++++++-- 4 files changed, 81 insertions(+), 37 deletions(-) diff --git a/ir/be/bespillbelady.c b/ir/be/bespillbelady.c index f1945d8a6..6a19d880b 100644 --- a/ir/be/bespillbelady.c +++ b/ir/be/bespillbelady.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -89,8 +89,6 @@ static workset_t *ws; /**< the main workset used while processing a block. */ static be_uses_t *uses; /**< env for the next-use magic */ static ir_node *instr; /**< current instruction */ -static unsigned instr_nr; /**< current instruction number - (relative to block start) */ static spill_env_t *senv; /**< see bespill.h */ static ir_node **blocklist; @@ -281,8 +279,7 @@ static inline void set_block_info(ir_node *block, block_info_t *info) /** * @return The distance to the next use or 0 if irn has dont_spill flag set */ -static unsigned get_distance(ir_node *from, unsigned from_step, - const ir_node *def, int skip_from_uses) +static unsigned get_distance(ir_node *from, const ir_node *def, int skip_from_uses) { be_next_use_t use; unsigned costs; @@ -290,7 +287,7 @@ static unsigned get_distance(ir_node *from, unsigned from_step, assert(!arch_irn_is_ignore(def)); - use = be_get_next_use(uses, from, from_step, def, skip_from_uses); + use = be_get_next_use(uses, from, def, skip_from_uses); time = use.time; if (USES_IS_INFINITE(time)) return USES_INFINITY; @@ -365,7 +362,7 @@ static void displace(workset_t *new_vals, int is_usage) /* calculate current next-use distance for live values */ for (i = 0; i < len; ++i) { ir_node *val = workset_get_val(ws, i); - unsigned dist = get_distance(instr, instr_nr, val, !is_usage); + unsigned dist = get_distance(instr, val, !is_usage); workset_set_time(ws, i, dist); } @@ -488,7 +485,7 @@ static loc_t to_take_or_not_to_take(ir_node* first, ir_node *node, return loc; } - next_use = be_get_next_use(uses, first, 0, node, 0); + next_use = be_get_next_use(uses, first, node, 0); if (USES_IS_INFINITE(next_use.time)) { /* the nodes marked as live in shouldn't be dead, so it must be a phi */ assert(is_Phi(node)); @@ -795,7 +792,6 @@ static void process_block(ir_node *block) /* process the block from start to end */ DB((dbg, DBG_WSETS, "Processing...\n")); - instr_nr = 0; /* TODO: this leaks (into the obstack)... */ new_vals = new_workset(); @@ -832,8 +828,6 @@ static void process_block(ir_node *block) workset_insert(new_vals, value, false); ); displace(new_vals, 0); - - instr_nr++; } /* Remember end-workset for this block */ diff --git a/ir/be/bestate.c b/ir/be/bestate.c index cd3a3a847..521929d83 100644 --- a/ir/be/bestate.c +++ b/ir/be/bestate.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -260,7 +260,7 @@ static block_info_t *compute_block_start_state(minibelady_env_t *env, ir_node *b continue; DBG((dbg, LEVEL_2, "\t...checking %+F\n", node)); - next_use = be_get_next_use(env->uses, first, 0, node, 0); + next_use = be_get_next_use(env->uses, first, node, 0); if (USES_IS_INFINITE(next_use.time)) { DBG((dbg, LEVEL_2, "\tnot taken (dead)\n")); @@ -310,7 +310,7 @@ static block_info_t *compute_block_start_state(minibelady_env_t *env, ir_node *b continue; DBG((dbg, LEVEL_2, "\t...checking %+F\n", node)); - next_use = be_get_next_use(env->uses, first, 0, node, 0); + next_use = be_get_next_use(env->uses, first, node, 0); if (USES_IS_INFINITE(next_use.time)) { DBG((dbg, LEVEL_2, "\tnot taken (dead)\n")); diff --git a/ir/be/beuses.c b/ir/be/beuses.c index 57453e946..40849aee3 100644 --- a/ir/be/beuses.c +++ b/ir/be/beuses.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -55,17 +55,23 @@ typedef struct be_use_t { const ir_node *node; int outermost_loop; unsigned next_use; - unsigned visited; + ir_visited_t visited; } be_use_t; +/** + * The "uses" environment. + */ struct be_uses_t { - set *uses; - ir_graph *irg; - const be_lv_t *lv; - unsigned visited_counter; - DEBUG_ONLY(firm_dbg_module_t *dbg;) + set *uses; /**< cache: contains all computed uses so far. */ + ir_graph *irg; /**< the graph for this environment. */ + const be_lv_t *lv; /**< the liveness for the graph. */ + ir_visited_t visited_counter; /**< current search counter. */ + DEBUG_ONLY(firm_dbg_module_t *dbg; /**< debug module for debug messages. */) }; +/** + * Set-compare two uses. + */ static int cmp_use(const void *a, const void *b, size_t n) { const be_use_t *p = (const be_use_t*)a; @@ -76,9 +82,16 @@ static int cmp_use(const void *a, const void *b, size_t n) } static be_next_use_t get_next_use(be_uses_t *env, ir_node *from, - unsigned from_step, const ir_node *def, - int skip_from_uses); + const ir_node *def, int skip_from_uses); +/** + * Return the use for the given definition in the given block if exists, + * else create it. + * + * @param env the uses environment + * @param block the block we search the use in + * @param def the definition of the value we are searching + */ static const be_use_t *get_or_set_use_block(be_uses_t *env, const ir_node *block, const ir_node *def) @@ -104,17 +117,28 @@ static const be_use_t *get_or_set_use_block(be_uses_t *env, be_next_use_t next_use; result->visited = env->visited_counter; - next_use = get_next_use(env, sched_first(block), 0, def, 0); + next_use = get_next_use(env, sched_first(block), def, 0); if (next_use.outermost_loop >= 0) { result->next_use = next_use.time; result->outermost_loop = next_use.outermost_loop; - DBG((env->dbg, LEVEL_5, "Setting nextuse of %+F in block %+F to %u (outermostloop %d)\n", def, block, result->next_use, result->outermost_loop)); + DBG((env->dbg, LEVEL_5, "Setting nextuse of %+F in block %+F to %u (outermostloop %d)\n", + def, block, result->next_use, result->outermost_loop)); } } return result; } +/** + * Check if a value of the given definition is used in the given block + * as a Phi argument. + * + * @param block the block to check + * @param def the definition of the value + * + * @return non-zero if the value is used in the given block as a Phi argument + * in one of its successor blocks. + */ static int be_is_phi_argument(const ir_node *block, const ir_node *def) { ir_node *node; @@ -131,20 +155,27 @@ static int be_is_phi_argument(const ir_node *block, const ir_node *def) succ_block = get_first_block_succ(block); arity = get_Block_n_cfgpreds(succ_block); - if (arity <= 1) + if (arity <= 1) { + /* no Phis in the successor */ return 0; + } + /* find the index of block in its successor */ for (i = 0; i < arity; ++i) { if (get_Block_cfgpred_block(succ_block, i) == block) break; } assert(i < arity); + /* iterate over the Phi nodes in the successor and check if def is + * one of its arguments */ sched_foreach(succ_block, node) { ir_node *arg; - if (!is_Phi(node)) + if (!is_Phi(node)) { + /* found first non-Phi node, we can stop the search here */ break; + } arg = get_irn_n(node, i); if (arg == def) @@ -177,11 +208,18 @@ static inline void set_step(ir_node *node, unsigned step) set_irn_link(node, INT_TO_PTR(step)); } +/** + * Find the next use of a value defined by def, starting at node from. + * + * @param env the uses environment + * @param from the node at which we should start the search + * @param def the definition of the value + * @param skip_from_uses if non-zero, ignore from uses + */ static be_next_use_t get_next_use(be_uses_t *env, ir_node *from, - unsigned from_step, const ir_node *def, - int skip_from_uses) + const ir_node *def, int skip_from_uses) { - unsigned step = from_step; + unsigned step; ir_node *block = get_nodes_block(from); ir_node *next_use; ir_node *node; @@ -314,11 +352,10 @@ static be_next_use_t get_next_use(be_uses_t *env, ir_node *from, } be_next_use_t be_get_next_use(be_uses_t *env, ir_node *from, - unsigned from_step, const ir_node *def, - int skip_from_uses) + const ir_node *def, int skip_from_uses) { - env->visited_counter++; - return get_next_use(env, from, from_step, def, skip_from_uses); + ++env->visited_counter; + return get_next_use(env, from, def, skip_from_uses); } /** diff --git a/ir/be/beuses.h b/ir/be/beuses.h index 836f4ee90..f033061be 100644 --- a/ir/be/beuses.h +++ b/ir/be/beuses.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -30,6 +30,9 @@ #include "firm_types.h" #include "belive.h" +/** + * Describes a use of a value. + */ typedef struct be_next_use_t { unsigned time; int outermost_loop; @@ -52,11 +55,21 @@ static inline int USES_IS_PENDING(unsigned time) typedef struct be_uses_t be_uses_t; be_next_use_t be_get_next_use(be_uses_t *uses, ir_node *from, - unsigned from_step, const ir_node *def, - int skip_from_uses); + const ir_node *def, int skip_from_uses); +/** + * Creates a new uses environment for a graph. + * + * @param irg the graph + * @param lv liveness information for the graph + */ be_uses_t *be_begin_uses(ir_graph *irg, const be_lv_t *lv); +/** + * Destroys the given uses environment. + * + * @param uses the environment + */ void be_end_uses(be_uses_t *uses); #endif /* FIRM_BE_BEUSES_H */ -- 2.20.1