/*
- * Project: libFIRM
- * File name: ir/opt/cfopt.c
- * Purpose: Partial condition evaluation
- * Author: Christoph Mallon, Matthias Braun
- * Created: 10. Sep. 2006
- * CVS-ID: $Id$
- * Copyright: (c) 1998-2006 Universität Karlsruhe
- * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
+ * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
+ */
+
+/**
+ * @file
+ * @brief Partial condition evaluation
+ * @date 10. Sep. 2006
+ * @author Christoph Mallon, Matthias Braun
+ * @version $Id$
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
+#include "iroptimize.h"
+
#include <assert.h>
#include "array.h"
-#include "condeval.h"
#include "debug.h"
#include "ircons.h"
#include "irgmod.h"
#include "iredges.h"
#include "iredges_t.h"
#include "irtools.h"
+#include "irgraph.h"
#include "tv.h"
DEBUG_ONLY(static firm_dbg_module_t *dbg);
set_irn_in(node, n + 1, ins);
}
-/**
- * Remove predecessor j from node, which is either a Block or a Phi
- * returns true if only one predecessor is left
- */
-static int remove_pred(ir_node* node, int j)
-{
- int n;
-
- assert(is_Block(node) || is_Phi(node));
-
- n = get_irn_arity(node);
- if (n == 2) {
- ir_node* pred = get_irn_n(node, 1 - j);
-
- if (is_Block(node)) {
- pred = get_nodes_block(pred);
- edges_reroute(node, pred, current_ir_graph);
- } else {
- exchange(node, pred);
- }
- return 1;
- } else {
- ir_node** ins;
- int i;
-
- NEW_ARR_A(ir_node*, ins, n - 1);
- for (i = 0; i < j; i++)
- ins[i] = get_irn_n(node, i);
- for (i++; i < n; i++)
- ins[i - 1] = get_irn_n(node, i);
-
- set_irn_in(node, n - 1, ins);
- return 0;
- }
-}
-
static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
{
int i;
ir_node *phi;
ir_node **in;
- assert(!is_Bad(block));
+ // This is needed because we create bads sometimes
+ if(is_Bad(block))
+ return new_Bad();
// already processed this block?
if(irn_visited(block)) {
}
// create a new phi
- in = alloca(sizeof(in[0]) * n_cfgpreds);
+ NEW_ARR_A(ir_node*, in, n_cfgpreds);
for(i = 0; i < n_cfgpreds; ++i)
in[i] = new_Unknown(mode);
// set phi preds
for(i = 0; i < n_cfgpreds; ++i) {
ir_node *pred_block = get_Block_cfgpred_block(block, i);
- ir_node *pred_val;
+ ir_node *pred_val = search_def_and_create_phis(pred_block, mode);
- pred_val = search_def_and_create_phis(pred_block, mode);
set_irn_n(phi, i, pred_val);
}
}
/**
- * Given a set of values this function constructs SSA-form for all users of the
- * values (the user are determined through the out-edges of the values). Uses
- * the irn_visited flags. Works without using the dominance tree.
+ * Given a set of values this function constructs SSA-form for the users of the
+ * first value (the users are determined through the out-edges of the value).
+ * Uses the irn_visited flags. Works without using the dominance tree.
*/
static void construct_ssa(ir_node * const *blocks, ir_node * const *vals, int n_vals)
{
int i;
ir_graph *irg;
ir_mode *mode;
+ const ir_edge_t *edge;
+ const ir_edge_t *next;
+ ir_node *value;
assert(n_vals > 0);
mark_irn_visited(value_block);
}
- for(i = 0; i < n_vals; ++i) {
- const ir_edge_t *edge, *next;
- ir_node *value = vals[i];
+ // Only fix the users of the first, i.e. the original node
+ value = vals[0];
- // this can happen when fixing phi preds, we mustn't fix the users
- if(get_nodes_block(value) != blocks[i]) {
- continue;
- }
+ // this can happen when fixing phi preds, we mustn't fix the users
+ if(get_nodes_block(value) != blocks[0]) return;
- foreach_out_edge_safe(value, edge, next) {
- ir_node *user = get_edge_src_irn(edge);
- int j = get_edge_src_pos(edge);
- ir_node *user_block = get_nodes_block(user);
- ir_node *newval;
+ foreach_out_edge_safe(value, edge, next) {
+ ir_node *user = get_edge_src_irn(edge);
+ int j = get_edge_src_pos(edge);
+ ir_node *user_block = get_nodes_block(user);
+ ir_node *newval;
- // ignore keeps
- if(get_irn_op(user) == op_End)
- continue;
+ // ignore keeps
+ if(get_irn_op(user) == op_End)
+ continue;
- if(is_Phi(user)) {
- ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
- newval = search_def_and_create_phis(pred_block, mode);
- } else {
- newval = search_def_and_create_phis(user_block, mode);
- }
+ DB((dbg, LEVEL_3, ">>> Fixing user %+F (pred %d == %+F)\n", user, j, get_irn_n(user, j)));
+
+ if(is_Phi(user)) {
+ ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
+ newval = search_def_and_create_phis(pred_block, mode);
+ } else {
+ newval = search_def_and_create_phis(user_block, mode);
+ }
- // don't fix newly created phis from the SSA construction
- if(newval != user)
- set_irn_n(user, j, newval);
+ // don't fix newly created phis from the SSA construction
+ if (newval != user) {
+ DB((dbg, LEVEL_4, ">>>> Setting input %d of %+F to %+F\n", j, user, newval));
+ set_irn_n(user, j, newval);
}
}
}
ir_node *true_block;
pn_Cmp pnc;
ir_node *cnst;
- int visited_nr;
+ unsigned long visited_nr;
ir_node *cnst_pred; /**< the block before the constant */
int cnst_pos; /**< the pos to the constant block (needed to kill that edge later) */
foreach_out_edge(block, edge) {
ir_node *node = get_edge_src_irn(edge);
ir_node *copy;
+ ir_mode *mode = get_irn_mode(node);
/* ignore control flow */
- if (get_irn_mode(node) == mode_X)
+ if (mode == mode_X || is_Cond(node))
continue;
+ /* we may not copy mode_b nodes, because this could produce phi with mode_bs which can't
+ be handled in all backends. Instead we duplicate the node and move it to it's users */
+ if (mode == mode_b) {
+ const ir_edge_t *edge, *next;
+ ir_node *pred;
+ int pn;
+
+ assert(is_Proj(node));
+
+ pred = get_Proj_pred(node);
+ pn = get_Proj_proj(node);
+
+ foreach_out_edge_safe(node, edge, next) {
+ ir_node *cmp_copy;
+ ir_node *user = get_edge_src_irn(edge);
+ int pos = get_edge_src_pos(edge);
+ ir_node *user_block = get_nodes_block(user);
+
+ if(user_block == block)
+ continue;
+
+ cmp_copy = exact_copy(pred);
+ set_nodes_block(cmp_copy, user_block);
+ copy = new_r_Proj(current_ir_graph, user_block, cmp_copy, mode_b, pn);
+ set_irn_n(user, pos, copy);
+ }
+ continue;
+ }
/* we can evaluate Phis right now, all other nodes get copied */
if (is_Phi(node)) {
foreach_out_edge(block, edge) {
ir_node *vals[2];
ir_node *blocks[2];
-
ir_node *node = get_edge_src_irn(edge);
+ ir_mode *mode = get_irn_mode(node);
- if (get_irn_mode(node) == mode_X)
+ if (mode == mode_X || is_Cond(node))
+ continue;
+ if (mode == mode_b)
continue;
+ DB((dbg, LEVEL_2, ">> Fixing users of %+F\n", node));
+
blocks[0] = block;
vals[0] = node;
blocks[1] = copy_block;
/**
- * Block-walker: searchs for the following construct
+ * Block-walker: searches for the following construct
*
* Const or Phi with constants
* |
if(is_Const(left)) {
tarval *tv1 = get_Const_tarval(left);
tarval *tv2 = get_Const_tarval(right);
+ ir_node *pred;
if(eval_cmp(pnc, tv1, tv2)) {
- ir_node *jmp = new_r_Jmp(irg, cond_block);
- set_Block_cfgpred(block, 0, jmp);
+ pred = new_r_Jmp(irg, cond_block);
} else {
- set_Block_cfgpred(block, 0, new_Bad());
+ pred = new_Bad();
}
+ set_Block_cfgpred(block, 0, pred);
*changed = 1;
set_irg_doms_inconsistent(irg);
set_irg_extblk_inconsistent(irg);
* jumps into the true_block. We also have to shorten phis
* in our block because of this */
const ir_edge_t *edge, *next;
+ ir_node* bad = new_Bad();
+ size_t cnst_pos = env.cnst_pos;
/* shorten phis */
foreach_out_edge_safe(env.cnst_pred, edge, next) {
ir_node *node = get_edge_src_irn(edge);
if(is_Phi(node))
- remove_pred(node, env.cnst_pos);
+ set_Phi_pred(node, cnst_pos, bad);
}
- remove_pred(env.cnst_pred, env.cnst_pos);
+ set_Block_cfgpred(env.cnst_pred, cnst_pos, bad);
- // the graph is changed now
+ /* the graph is changed now */
*changed = 1;
- set_irg_doms_inconsistent(irg);
- set_irg_extblk_inconsistent(irg);
- set_irg_loopinfo_inconsistent(irg);
}
}
}
void opt_cond_eval(ir_graph* irg)
{
- int changed;
+ int changed, rerun;
FIRM_DBG_REGISTER(dbg, "firm.opt.condeval");
- //firm_dbg_set_mask(dbg, SET_LEVEL_5);
DB((dbg, LEVEL_1, "===> Performing condition evaluation on %+F\n", irg));
- edges_assure(irg);
remove_critical_cf_edges(irg);
-
normalize_proj_nodes(irg);
+ edges_assure(irg);
+ set_using_irn_link(irg);
+ set_using_visited(irg);
+
+ changed = 0;
do {
- changed = 0;
- irg_block_walk_graph(irg, cond_eval, NULL, &changed);
- } while(changed);
+ rerun = 0;
+ irg_block_walk_graph(irg, cond_eval, NULL, &rerun);
+ changed |= rerun;
+ } while (rerun);
+
+ if (changed) {
+ /* control flow changed, some blocks may become dead */
+ set_irg_outs_inconsistent(irg);
+ set_irg_doms_inconsistent(irg);
+ set_irg_extblk_inconsistent(irg);
+ set_irg_loopinfo_inconsistent(irg);
+ }
+
+ clear_using_visited(irg);
+ clear_using_irn_link(irg);
}