#include "irnodemap.h"
#include "irnodeset.h"
#include "iredges.h"
+#include "iropt_dbg.h"
#include "debug.h"
#include "irgraph_t.h"
ir_node *old_node; /**< The old node that will be replaced. */
ir_node *new_node; /**< The new node. */
struct elim_pair *next; /**< Links all entries in a list. */
+ int reason; /**< The reason for the replacement. */
} elim_pair;
/** The environment for the GVN-PRE algorithm */
ir_node *end_block; /**< The end block of the current graph */
block_info *list; /**< Links all block info entires for easier recovery. */
elim_pair *pairs; /**< A list of node pairs that must be eliminated. */
+ unsigned last_idx; /**< last node index of "old" nodes, all higher indexes are newly created once. */
char changes; /**< Non-zero, if calculation of Antic_in has changed. */
char first_iter; /**< non-zero for first iteration */
} pre_env;
/* ---------- Functions for Values ---------- */
/**
- * Add a node node representing the value value to the set.
+ * Add a node e representing the value v to the set.
+ *
+ * @param e a node representing an expression
+ * @param v a node representing a value
+ *
+ * @return the final value for the expression e
*/
static ir_node *add(ir_node *e, ir_node *v)
{
v = identify_remember(value_table, v);
ir_nodemap_insert(&value_map, e, v);
return v;
-}
+} /* add */
/**
* Lookup a value in a value set.
+ *
+ * @param e a node representing an expression
+ *
+ * @return a node representing the value or NULL if
+ * the given expression is not available
*/
static ir_node *lookup(ir_node *e)
{
if (value != NULL)
return identify_remember(value_table, value);
return NULL;
-}
+} /* lookup */
/**
- * Return the block info of a block
+ * Return the block info of a block.
+ *
+ * @param block the block
*/
static block_info *get_block_info(ir_node *block) {
return get_irn_link(block);
-}
+} /* get_block_info */
/**
- * allocate a block info
+ * Allocate a block info for a block.
+ *
+ * @param block the block
+ * @param env the environment
*/
static void alloc_blk_info(ir_node *block, pre_env *env) {
block_info *info = obstack_alloc(env->obst, sizeof(*info));
info->not_found = 0;
info->next = env->list;
env->list = info;
-}
+} /* alloc_blk_info */
/**
* Returns non-zero if a node is movable and a possible candidate for PRE.
+ *
+ * @param n the node
*/
static int is_nice_value(ir_node *n) {
ir_mode *mode;
#ifdef DEBUG_libfirm
/**
* Dump a value set.
+ *
+ * @param set the set to dump
+ * @param txt a text to describe the set
+ * @param block the owner block of the set
*/
static void dump_value_set(ir_valueset_t *set, char *txt, ir_node *block) {
ir_valueset_iterator_t iter;
* Precondition:
* This function must be called in the top-down dominance order:
* Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
+ *
+ * @param block the block
+ * @param ctx walker context
*/
static void compute_avail_top_down(ir_node *block, void *ctx)
{
value_union(info->avail_out, info->exp_gen);
dump_value_set(info->avail_out, "Avail_out", block);
-}
+} /* compute_avail_top_down */
/**
* check if a node n is clean in block block.
+ *
+ * @param n the node
+ * @param block the block
*/
static int _is_clean(ir_node *n, ir_node *block)
{
bad:
mark_irn_visited(n);
return 0;
-}
+} /* _is_clean */
/**
* check if a node n is clean.
+ *
+ * @param n the node to check
*/
static int is_clean(ir_node *n) {
int res = _is_clean(n, get_nodes_block(n));
return res;
-}
+} /* is_clean */
/**
- * Implements phi_translate.
+ * Implements phi_translate. Translate a expression above a Phi.
+ *
+ * @param node the node
+ * @param block the block in which the node is translated
+ * @param pos the input number of the destination block
+ * @param env the environment
+ *
+ * @return a node representing the translated value
*/
static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, pre_env *env)
{
} /* phi_translate */
/**
- * computes Antic_in(block):
+ * Block-walker, computes Antic_in(block).
+ *
+ * @param block the block
+ * @param ctx the walker environment
*/
static void compute_antic(ir_node *block, void *ctx) {
pre_env *env = ctx;
* 2c. Insert a new Phi merging the values of the predecessors.
* 2d. Insert the new Phi, and the new expressions, into the
* NEW_SETS set.
+ *
+ * @param block the block
+ * @param ctx the walker environment
*/
static void insert_nodes(ir_node *block, void *ctx)
{
*
* We cannot do the changes right here, as this would change
* the hash values of the nodes in the avail_out set!
+ *
+ * @param irn the node
+ * @param ctx the walker environment
*/
static void eliminate(ir_node *irn, void *ctx) {
pre_env *env = ctx;
p->old_node = irn;
p->new_node = expr;
p->next = env->pairs;
+ p->reason = get_irn_idx(expr) >= env->last_idx ? FS_OPT_GVN_PARTLY : FS_OPT_GVN_FULLY;
env->pairs = p;
}
}
/**
* Do all the recorded changes and optimize
* newly created Phi's.
+ *
+ * @param pairs list of elimination pairs
*/
static void eliminate_nodes(elim_pair *pairs) {
elim_pair *p;
if (res)
p->new_node = res;
}
+ DBG_OPT_GVN_PRE(p->old_node, p->new_node, p->reason);
exchange(p->old_node, p->new_node);
}
} /* eliminate_nodes */
*/
void do_gvn_pre(ir_graph *irg)
{
- struct obstack obst;
- pre_env a_env;
+ struct obstack obst;
+ pre_env a_env;
optimization_state_t state;
- block_info *bl_info;
- unsigned antic_iter, insert_iter;
+ block_info *bl_info;
+ unsigned antic_iter, insert_iter;
+ ir_node *value, *expr;
/* register a debug mask */
FIRM_DBG_REGISTER(dbg, "firm.opt.gvn_pre");
- firm_dbg_set_mask(dbg, SET_LEVEL_2);
/* edges will crash if enabled due to our allocate on other obstack trick */
edges_deactivate(irg);
/* allocate block info for all blocks */
irg_walk_blkwise_graph(irg, NULL, topo_walker, &a_env);
+ /* clean the exp_gen set. Doing this here saves the cleanup in the iteration. */
+ inc_irg_visited(irg);
+ for (bl_info = a_env.list; bl_info != NULL; bl_info = bl_info->next) {
+ ir_valueset_iterator_t iter;
+
+ foreach_valueset(bl_info->exp_gen, value, expr, iter) {
+ if (!is_clean(expr))
+ ir_valueset_remove_iterator(bl_info->exp_gen, &iter);
+ }
+ }
+
/* compute the available value sets for all blocks */
dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
do {
DB((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++antic_iter));
a_env.changes = 0;
- //irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
a_env.first_iter = 0;
DB((dbg, LEVEL_1, "------------------------\n"));
/* compute redundant expressions */
insert_iter = 0;
+ a_env.last_idx = get_irg_last_idx(irg);
do {
DB((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++insert_iter));
a_env.changes = 0;
projects / libfirm / blobdiff