From 9d61e03d333104a4f31b4ca66b424c98c1d31e26 Mon Sep 17 00:00:00 2001 From: Michael Beck Date: Fri, 17 Jun 2005 11:43:53 +0000 Subject: [PATCH] Construction of Confirm nodes [r6046] --- ir/ana/irconsconfirm.c | 279 +++++++++++++++++++++++++++++++++++++++++ ir/ana/irconsconfirm.h | 55 ++++++++ 2 files changed, 334 insertions(+) create mode 100644 ir/ana/irconsconfirm.c create mode 100644 ir/ana/irconsconfirm.h diff --git a/ir/ana/irconsconfirm.c b/ir/ana/irconsconfirm.c new file mode 100644 index 000000000..0a9f2508a --- /dev/null +++ b/ir/ana/irconsconfirm.c @@ -0,0 +1,279 @@ +/* + * Project: libFIRM + * File name: ir/ana/irconsconfirm.c + * Purpose: Construction of Confirm nodes + * Author: Michael Beck + * Modified by: + * Created: 6.2005 + * CVS-ID: $Id$ + * Copyright: (C) 2002-2005 Universität Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +/** + * @file irconsconfirm.c + * + * Construction of Confirm nodes + * + * @author Michael Beck + */ +#include "irgraph_t.h" +#include "irnode_t.h" +#include "ircons_t.h" +#include "irgmod.h" +#include "iropt_dbg.h" +#include "iredges_t.h" + +/** + * Walker environment. + */ +typedef struct _env_t { + unsigned num_confirms; /**< number of inserted Confirm nodes */ + unsigned num_consts; /**< number of constants placed */ + unsigned num_eq; /**< number of equalities placed */ +} env_t; + +/** + * Handle a CASE-branch. + * + * @param block the block which is entered by the branch + * @param irn the node expressing the switch value + * @param pnc the branch label + * @param env statistical environment + * + * Branch labels are a simple case. We can replace the value + * by a Const with the branch label. + */ +static void handle_case(ir_node *block, ir_node *irn, long nr, env_t *env) +{ + int pos; + const ir_edge_t *edge, *next; + ir_node *c = NULL; + + for (edge = get_irn_out_edge_first(irn); edge; edge = next) { + ir_node *succ = get_edge_src_irn(edge); + ir_node *blk = get_nodes_block(succ); + + next = get_irn_out_edge_next(irn, edge); + + if (block_dominates(block, blk)) { + /* + * Ok, we found a user of irn that is placed + * in a block dominated by the branch block. + * We can replace the input with the Constant + * branch label. + */ + + if (! c) { + ir_mode *mode = get_irn_mode(irn); + type *tp = get_irn_type(irn); + tarval *tv = new_tarval_from_long(nr, mode); + c = new_r_Const_type(current_ir_graph, block, mode, tv, tp); + } + + pos = get_edge_src_pos(edge); + set_irn_n(succ, pos, c); + DBG_OPT_CONFIRM(irn, c); + + env->num_consts += 1; + } + } +} + +/** + * Handle an IF-branch. + * + * @param block the block which is entered by the branch + * @param cmp the Cmp node expressing the branch condition + * @param pnc the Compare relation for taking this branch + * @param env statistical environment + */ +static void handle_if(ir_node *block, ir_node *cmp, pn_Cmp pnc, env_t *env) +{ + ir_node *left = get_Cmp_left(cmp); + ir_node *right = get_Cmp_right(cmp); + const ir_edge_t *edge, *next; + + /* remove unordered if it's an integer compare */ + if (mode_is_int(get_irn_mode(left))) + pnc &= ~pn_Cmp_Uo; + + /* try to place the constant on the right side */ + if (get_irn_op(left) == op_Const) { + ir_node *t = left; + + left = right; + right = t; + + pnc = get_inversed_pnc(pnc); + } + + /* + * First case: both values are identical. + * replace the left one by the right one. + */ + if (pnc == pn_Cmp_Eq) { + int pos; + + for (edge = get_irn_out_edge_first(left); edge; edge = next) { + ir_node *succ = get_edge_src_irn(edge); + ir_node *blk = get_nodes_block(succ); + + next = get_irn_out_edge_next(left, edge); + if (block_dominates(block, blk)) { + /* + * Ok, we found a user of left that is placed + * in a block dominated by the branch block. + * We can replace the input with right. + */ + pos = get_edge_src_pos(edge); + set_irn_n(succ, pos, right); + DBG_OPT_CONFIRM(left, right); + + env->num_eq += 1; + } + } + } + else { /* not == cases */ + int pos; + ir_node *c = NULL; + + for (edge = get_irn_out_edge_first(left); edge; edge = next) { + ir_node *succ = get_edge_src_irn(edge); + ir_node *blk = get_nodes_block(succ); + + next = get_irn_out_edge_next(left, edge); + if (block_dominates(block, blk)) { + /* + * Ok, we found a user of left that is placed + * in a block dominated by the branch block. + * We can replace the input with a Confirm(left, pnc, right). + */ + + if (! c) + c = new_r_Confirm(current_ir_graph, block, left, right, pnc); + + pos = get_edge_src_pos(edge); + set_irn_n(succ, pos, c); + DBG_OPT_CONFIRM(left, c); + + env->num_confirms += 1; + } + } + } +} + +/** + * Pre-walker: Called for every block to insert Confirm nodes + */ +static void insert_Confirm(ir_node *block, void *env) +{ + ir_node *cond, *proj, *selector; + ir_mode *mode; + + /* + * we can only handle blocks with only ONE control flow + * predecessor + */ + if (get_Block_n_cfgpreds(block) != 1) + return; + + proj = get_Block_cfgpred(block, 0); + if (get_irn_op(proj) != op_Proj) + return; + + cond = get_Proj_pred(proj); + if (get_irn_op(cond) != op_Cond) + return; + + selector = get_Cond_selector(cond); + mode = get_irn_mode(selector); + + if (mode == mode_b) { + ir_node *cmp; + pn_Cmp pnc; + + /* this should be an IF, check this */ + if (get_irn_op(selector) != op_Proj) + return; + + cmp = get_Proj_pred(selector); + if (get_irn_op(cmp) != op_Cmp) + return; + + pnc = get_Proj_proj(selector); + + if (get_Proj_proj(proj) != pn_Cond_true) { + /* it's the false branch */ + pnc = get_negated_pnc(pnc); + } + handle_if(block, cmp, pnc, env); + } + else if (mode_is_int(mode)) { + long proj_nr = get_Proj_proj(proj); + + /* this is a CASE, but we cannot handle the default case */ + if (proj_nr == get_Cond_defaultProj(cond)) + return; + + handle_case(block, get_Cond_selector(cond), proj_nr, env); + } +} + +/* + * Construct Confirm nodes + */ +void construct_confirms(ir_graph *irg) +{ + env_t env; + int edges_active = edges_activated(irg); + + if (get_irg_dom_state(irg) != dom_consistent) { + /* we need dominance info */ + compute_doms(irg); + } + + if (! edges_active) { + /* We need edges */ + edges_activate(irg); + } + + env.num_confirms = 0; + env.num_consts = 0; + env.num_eq = 0; + + /* now, visit all blocks and add Confirms where possible */ + irg_block_walk_graph(irg, insert_Confirm, NULL, &env); + + if (env.num_confirms | env.num_consts | env.num_eq) { + /* we have add nodes or changed DF edges */ + set_irg_outs_inconsistent(irg); + + /* the new nodes are not in the loop info */ + set_irg_loopinfo_inconsistent(irg); + } + + printf("No Confirms inserted : %u\n", env.num_confirms); + printf("No Const replacements: %u\n", env.num_consts); + printf("No node equalities : %u\n", env.num_eq); + + /* deactivate edges if they where off */ + if (! edges_active) + edges_deactivate(irg); +} + +/** + * Post-walker: Remove COnfirm nodes + */ +static void rem_Confirm(ir_node *n, void *env) { + if (get_irn_op(n) == op_Confirm) { + exchange(n, get_Confirm_value(n)); + } +} + +/* + * Remove all Confirm nodes from a graph. + */ +void remove_confirms(ir_graph *irg) { + irg_walk_graph(irg, NULL, rem_Confirm, NULL); +} diff --git a/ir/ana/irconsconfirm.h b/ir/ana/irconsconfirm.h new file mode 100644 index 000000000..2e0aa9526 --- /dev/null +++ b/ir/ana/irconsconfirm.h @@ -0,0 +1,55 @@ +/* + * Project: libFIRM + * File name: ir/ana/irconsconfirm.h + * Purpose: Construction of Confirm nodes + * Author: Michael Beck + * Modified by: + * Created: 6.2005 + * CVS-ID: $Id$ + * Copyright: (C) 2002-2005 Universität Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +/** + * @file irconsconfirm.h + * + * Construction of Confirm nodes + * + * @author Michael Beck + */ +#ifndef _IRCONSCONFIRM_H_ +#define _IRCONSCONFIRM_H_ + +#include "irgraph.h" + +/* + * Inject Confirm nodes into a graph. + * + * @param irg the graph + * + * Confirm nodes carry confirmation information, such as + * a relation between a value a and another value (or a constant) + * b. + * + * These allows to do some range dependent optimizations for Cmp, + * Abs, Min, Max nodes as well as bounds checking removement. + * + * The heap analysis might profit also. On the other side, Confirm + * nodes disturb local optimizations, because patterns are destroyed. + * + * It is possible to avoid this by skipping Confirm nodes, but this + * is not implemented and is not cheap. The same happens with Casts + * nodes too. The current solution is to remove Confirms at a later + * pass. + */ +void construct_confirms(ir_graph *irg); + +/** + * Remove all Confirm nodes from a graph. + * + * Note that local_optimize() can handle this if + * the remove Confirm node setting is on (set_opt_remove_Confirm(1)). + */ +void remove_confirms(ir_graph *irg); + +#endif /* _IRCONSCONFIRM_H_ */ -- 2.20.1