X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fifconv.c;h=56e5607996da45c3c012176a2970a8216e6920d6;hb=4cef2a70fbdc26498af3540fb1d07d96fbd56d56;hp=07dd0abbd0ca7b356f959779ced35bfd62cb2968;hpb=5f4a7559628fca2ee71c641e1eb14e8ee2e9c740;p=libfirm diff --git a/ir/opt/ifconv.c b/ir/opt/ifconv.c index 07dd0abbd..56e560799 100644 --- a/ir/opt/ifconv.c +++ b/ir/opt/ifconv.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -24,9 +24,7 @@ * @version $Id$ */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif #include #include "iroptimize.h" @@ -39,16 +37,15 @@ #include "irgopt.h" #include "irgwalk.h" #include "irtools.h" -#include "array.h" -#include "xmalloc.h" +#include "array_t.h" // debug #include "irdump.h" #include "debug.h" -DEBUG_ONLY(firm_dbg_module_t *dbg); +DEBUG_ONLY(static firm_dbg_module_t *dbg); -/** allow every Psi to be created. */ +/** allow every Mux to be created. */ static int default_allow_ifconv(ir_node *sel, ir_node* phi_list, int i, int j) { (void) sel; @@ -61,32 +58,16 @@ static int default_allow_ifconv(ir_node *sel, ir_node* phi_list, int i, int j) /** * Default options. */ -static const opt_if_conv_info_t default_info = { - 0, /* doesn't matter for Psi */ +static const ir_settings_if_conv_t default_info = { + 0, /* doesn't matter for Mux */ default_allow_ifconv }; -/** - * Additional block info. - */ -typedef struct block_info { - ir_node *phi; /**< head of the Phi list */ - int has_pinned; /**< set if the block contains instructions that cannot be moved */ -} block_info; - - -static INLINE block_info* get_block_blockinfo(const ir_node* block) -{ - return get_irn_link(block); -} - - /** * Returns non-zero if a Block can be emptied. */ -static int can_empty_block(ir_node *block) -{ - return !get_block_blockinfo(block)->has_pinned; +static int can_empty_block(ir_node *block) { + return get_Block_mark(block) == 0; } @@ -188,7 +169,7 @@ static void split_block(ir_node* block, int i, int j) ir_node* pred_block = get_nodes_block(get_irn_n(block, i)); int arity = get_irn_arity(block); int new_pred_arity; - ir_node* phi; + ir_node *phi, *next; ir_node **ins; ir_node **pred_ins; int k; @@ -197,7 +178,7 @@ static void split_block(ir_node* block, int i, int j) NEW_ARR_A(ir_node*, ins, arity + 1); - for (phi = get_block_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(phi)) { + for (phi = get_Block_phis(block); phi != NULL; phi = get_Phi_next(phi)) { ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j); for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k); @@ -218,10 +199,11 @@ static void split_block(ir_node* block, int i, int j) new_pred_arity = get_irn_arity(pred_block) - 1; NEW_ARR_A(ir_node*, pred_ins, new_pred_arity); - for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) { + for (phi = get_Block_phis(pred_block); phi != NULL; phi = next) { for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k); for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1); assert(k == new_pred_arity); + next = get_Phi_next(phi); if (new_pred_arity > 1) { set_irn_in(phi, new_pred_arity, pred_ins); } else { @@ -263,20 +245,20 @@ static void prepare_path(ir_node* block, int i, const ir_node* dependency) static void if_conv_walker(ir_node* block, void* env) { - opt_if_conv_info_t* opt_info = env; + ir_settings_if_conv_t* opt_info = env; int arity; int i; /* Bail out, if there are no Phis at all */ - if (get_block_blockinfo(block)->phi == NULL) return; + if (get_Block_phis(block) == NULL) return; restart: arity = get_irn_arity(block); for (i = 0; i < arity; ++i) { ir_node* pred0; - cdep* cdep; + ir_cdep* cdep; - pred0 = get_nodes_block(get_irn_n(block, i)); + pred0 = get_Block_cfgpred_block(block, i); for (cdep = find_cdep(pred0); cdep != NULL; cdep = cdep->next) { const ir_node* dependency = cdep->node; ir_node* projx0 = walk_to_projx(pred0, dependency); @@ -286,20 +268,21 @@ restart: if (projx0 == NULL) continue; cond = get_Proj_pred(projx0); - if (get_irn_op(cond) != op_Cond) continue; + if (! is_Cond(cond)) + continue; /* We only handle boolean decisions, no switches */ if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue; for (j = i + 1; j < arity; ++j) { ir_node* projx1; - ir_node* conds[1]; - ir_node* psi_block; + ir_node* sel; + ir_node* mux_block; ir_node* phi; ir_node* pred1; dbg_info* cond_dbg; - pred1 = get_nodes_block(get_irn_n(block, j)); + pred1 = get_Block_cfgpred_block(block, j); if (!is_cdep_on(pred1, dependency)) continue; @@ -307,7 +290,7 @@ restart: if (projx1 == NULL) continue; - phi = get_block_blockinfo(block)->phi; + phi = get_Block_phis(block); if (!opt_info->allow_ifconv(get_Cond_selector(cond), phi, i, j)) continue; DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n", @@ -318,70 +301,75 @@ restart: prepare_path(block, j, dependency); arity = get_irn_arity(block); - conds[0] = get_Cond_selector(cond); + sel = get_Cond_selector(cond); - psi_block = get_nodes_block(cond); + mux_block = get_nodes_block(cond); cond_dbg = get_irn_dbg_info(cond); do { ir_node* val_i = get_irn_n(phi, i); ir_node* val_j = get_irn_n(phi, j); - ir_node* psi; + ir_node* mux; ir_node* next_phi; if (val_i == val_j) { - psi = val_i; - DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n")); + mux = val_i; + DB((dbg, LEVEL_2, "Generating no Mux, because both values are equal\n")); } else { - ir_node* vals[2]; + ir_node *t, *f; /* Something is very fishy if two predecessors of a PhiM point into * one block, but not at the same memory node */ assert(get_irn_mode(phi) != mode_M); if (get_Proj_proj(projx0) == pn_Cond_true) { - vals[0] = val_i; - vals[1] = val_j; + t = val_i; + f = val_j; } else { - vals[0] = val_j; - vals[1] = val_i; + t = val_j; + f = val_i; } - psi = new_rd_Psi(cond_dbg, current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)); - DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi)); + mux = new_rd_Mux(cond_dbg, current_ir_graph, mux_block, sel, f, t, get_irn_mode(phi)); + DB((dbg, LEVEL_2, "Generating %+F for %+F\n", mux, phi)); } - next_phi = get_irn_link(phi); + next_phi = get_Phi_next(phi); if (arity == 2) { - exchange(phi, psi); + exchange(phi, mux); } else { - rewire(phi, i, j, psi); + rewire(phi, i, j, mux); } phi = next_phi; } while (phi != NULL); - exchange(get_nodes_block(get_irn_n(block, i)), psi_block); - exchange(get_nodes_block(get_irn_n(block, j)), psi_block); + exchange(get_nodes_block(get_irn_n(block, i)), mux_block); + exchange(get_nodes_block(get_irn_n(block, j)), mux_block); if (arity == 2) { + unsigned mark; #if 1 - DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, psi_block)); - /* copy the block-info from the Psi-block to the block before merging */ - get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned; - set_irn_link(block, get_irn_link(psi_block)); - - set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1); - exchange_cdep(psi_block, block); - exchange(psi_block, block); + DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, mux_block)); + /* copy the block-info from the Mux-block to the block before merging */ + + mark = get_Block_mark(mux_block) | get_Block_mark(block); + set_Block_mark(block, mark); + set_Block_phis(block, get_Block_phis(mux_block)); + + set_irn_in(block, get_irn_arity(mux_block), get_irn_in(mux_block) + 1); + exchange_cdep(mux_block, block); + exchange(mux_block, block); #else - DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block)); - get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned; - exchange(block, psi_block); + DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, mux_block)); + mark = get_Block_mark(mux_block) | get_Block_mark(block); + /* mark both block just to be sure, should be enough to mark mux_block */ + set_Block_mark(mux_block, mark); + exchange(block, mux_block); #endif return; } else { - rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block)); + rewire(block, i, j, new_r_Jmp(current_ir_graph, mux_block)); goto restart; } } @@ -390,33 +378,27 @@ restart: } /** - * Block walker: add additional data + * Block walker: clear block mark and Phi list */ static void init_block_link(ir_node *block, void *env) { - struct obstack *obst = env; - block_info *bi = obstack_alloc(obst, sizeof(*bi)); - - bi->phi = NULL; - bi->has_pinned = 0; - set_irn_link(block, bi); + (void)env; + set_Block_mark(block, 0); + set_Block_phis(block, NULL); } /** * Daisy-chain all phis in a block - * If a non-movable node is encountered set the has_pinned flag + * If a non-movable node is encountered set the has_pinned flag in its block. */ -static void collect_phis(ir_node *node, void *env) -{ +static void collect_phis(ir_node *node, void *env) { (void) env; if (is_Phi(node)) { ir_node *block = get_nodes_block(node); - block_info *bi = get_block_blockinfo(block); - set_irn_link(node, bi->phi); - bi->phi = node; + add_Block_phi(block, node); } else { if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) { /* @@ -425,124 +407,120 @@ static void collect_phis(ir_node *node, void *env) */ if (!is_cfop(node)) { ir_node *block = get_nodes_block(node); - block_info *bi = get_block_blockinfo(block); DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block)); - bi->has_pinned = 1; + set_Block_mark(block, 1); } } } } -static void optimise_psis_0(ir_node* psi, void* env) +static void optimise_muxs_0(ir_node* mux, void* env) { ir_node* t; ir_node* f; (void) env; - if (!is_Psi(psi)) return; + if (!is_Mux(mux)) return; - t = get_Psi_val(psi, 0); - f = get_Psi_default(psi); + t = get_Mux_true(mux); + f = get_Mux_false(mux); - DB((dbg, LEVEL_3, "Simplify %+F T=%+F F=%+F\n", psi, t, f)); + DB((dbg, LEVEL_3, "Simplify %+F T=%+F F=%+F\n", mux, t, f)); if (is_Unknown(t)) { - DB((dbg, LEVEL_3, "Replace Psi with unknown operand by %+F\n", f)); - exchange(psi, f); + DB((dbg, LEVEL_3, "Replace Mux with unknown operand by %+F\n", f)); + exchange(mux, f); return; } if (is_Unknown(f)) { - DB((dbg, LEVEL_3, "Replace Psi with unknown operand by %+F\n", t)); - exchange(psi, t); + DB((dbg, LEVEL_3, "Replace Mux with unknown operand by %+F\n", t)); + exchange(mux, t); return; } - if (is_Psi(t)) { + if (is_Mux(t)) { ir_graph* irg = current_ir_graph; - ir_node* block = get_nodes_block(psi); - ir_mode* mode = get_irn_mode(psi); - ir_node* c0 = get_Psi_cond(psi, 0); - ir_node* c1 = get_Psi_cond(t, 0); - ir_node* t1 = get_Psi_val(t, 0); - ir_node* f1 = get_Psi_default(t); + ir_node* block = get_nodes_block(mux); + ir_mode* mode = get_irn_mode(mux); + ir_node* c0 = get_Mux_sel(mux); + ir_node* c1 = get_Mux_sel(t); + ir_node* t1 = get_Mux_true(t); + ir_node* f1 = get_Mux_false(t); if (f == f1) { - /* Psi(c0, Psi(c1, x, y), y) -> typical if (c0 && c1) x else y */ + /* Mux(c0, Mux(c1, x, y), y) -> typical if (c0 && c1) x else y */ ir_node* and_ = new_r_And(irg, block, c0, c1, mode_b); - ir_node* vals[2] = { t1, f1 }; - ir_node* new_psi = new_r_Psi(irg, block, 1, &and_, vals, mode); - exchange(psi, new_psi); + ir_node* new_mux = new_r_Mux(irg, block, and_, f1, t1, mode); + exchange(mux, new_mux); } else if (f == t1) { - /* Psi(c0, Psi(c1, x, y), x) */ + /* Mux(c0, Mux(c1, x, y), x) */ ir_node* not_c1 = new_r_Not(irg, block, c1, mode_b); ir_node* and_ = new_r_And(irg, block, c0, not_c1, mode_b); - ir_node* vals[2] = { f1, t1 }; - ir_node* new_psi = new_r_Psi(irg, block, 1, &and_, vals, mode); - exchange(psi, new_psi); + ir_node* new_mux = new_r_Mux(irg, block, and_, t1, f1, mode); + exchange(mux, new_mux); } - } else if (is_Psi(f)) { + } else if (is_Mux(f)) { ir_graph* irg = current_ir_graph; - ir_node* block = get_nodes_block(psi); - ir_mode* mode = get_irn_mode(psi); - ir_node* c0 = get_Psi_cond(psi, 0); - ir_node* c1 = get_Psi_cond(f, 0); - ir_node* t1 = get_Psi_val(f, 0); - ir_node* f1 = get_Psi_default(f); + ir_node* block = get_nodes_block(mux); + ir_mode* mode = get_irn_mode(mux); + ir_node* c0 = get_Mux_sel(mux); + ir_node* c1 = get_Mux_sel(f); + ir_node* t1 = get_Mux_true(f); + ir_node* f1 = get_Mux_false(f); if (t == t1) { - /* Psi(c0, x, Psi(c1, x, y)) -> typical if (c0 || c1) x else y */ + /* Mux(c0, x, Mux(c1, x, y)) -> typical if (c0 || c1) x else y */ ir_node* or_ = new_r_Or(irg, block, c0, c1, mode_b); - ir_node* vals[2] = { t1, f1 }; - ir_node* new_psi = new_r_Psi(irg, block, 1, &or_, vals, mode); - exchange(psi, new_psi); + ir_node* new_mux = new_r_Mux(irg, block, or_, f1, t1, mode); + exchange(mux, new_mux); } else if (t == f1) { - /* Psi(c0, x, Psi(c1, y, x)) */ + /* Mux(c0, x, Mux(c1, y, x)) */ ir_node* not_c1 = new_r_Not(irg, block, c1, mode_b); ir_node* or_ = new_r_Or(irg, block, c0, not_c1, mode_b); - ir_node* vals[2] = { f1, t1 }; - ir_node* new_psi = new_r_Psi(irg, block, 1, &or_, vals, mode); - exchange(psi, new_psi); + ir_node* new_mux = new_r_Mux(irg, block, or_, t1, f1, mode); + exchange(mux, new_mux); } } } -static void optimise_psis_1(ir_node* psi, void* env) +static void optimise_muxs_1(ir_node* mux, void* env) { ir_node* t; ir_node* f; + ir_mode* mode; (void) env; - if (!is_Psi(psi)) return; + if (!is_Mux(mux)) return; + + t = get_Mux_true(mux); + f = get_Mux_false(mux); - t = get_Psi_val(psi, 0); - f = get_Psi_default(psi); + DB((dbg, LEVEL_3, "Simplify %+F T=%+F F=%+F\n", mux, t, f)); - DB((dbg, LEVEL_3, "Simplify %+F T=%+F F=%+F\n", psi, t, f)); + mode = get_irn_mode(mux); - if (is_Const(t) && is_Const(f)) { - ir_node* block = get_nodes_block(psi); - ir_mode* mode = get_irn_mode(psi); - ir_node* c = get_Psi_cond(psi, 0); + if (is_Const(t) && is_Const(f) && (mode_is_int(mode))) { + ir_node* block = get_nodes_block(mux); + ir_node* c = get_Mux_sel(mux); tarval* tv_t = get_Const_tarval(t); tarval* tv_f = get_Const_tarval(f); if (tarval_is_one(tv_t) && tarval_is_null(tv_f)) { ir_node* conv = new_r_Conv(current_ir_graph, block, c, mode); - exchange(psi, conv); + exchange(mux, conv); } else if (tarval_is_null(tv_t) && tarval_is_one(tv_f)) { ir_node* not_ = new_r_Not(current_ir_graph, block, c, mode_b); ir_node* conv = new_r_Conv(current_ir_graph, block, not_, mode); - exchange(psi, conv); + exchange(mux, conv); } } } -void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params) +void opt_if_conv(ir_graph *irg, const ir_settings_if_conv_t *params) { - struct obstack obst; - opt_if_conv_info_t p; + ir_settings_if_conv_t p; /* get the parameters */ p = (params != NULL ? *params : default_info); @@ -557,20 +535,26 @@ void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params) compute_cdep(irg); assure_doms(irg); - obstack_init(&obst); - irg_block_walk_graph(irg, init_block_link, NULL, &obst); + ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST); + + irg_block_walk_graph(irg, init_block_link, NULL, NULL); irg_walk_graph(irg, collect_phis, NULL, NULL); irg_block_walk_graph(irg, NULL, if_conv_walker, &p); + ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST); + local_optimize_graph(irg); - irg_walk_graph(irg, NULL, optimise_psis_0, NULL); + irg_walk_graph(irg, NULL, optimise_muxs_0, NULL); #if 1 - irg_walk_graph(irg, NULL, optimise_psis_1, NULL); + irg_walk_graph(irg, NULL, optimise_muxs_1, NULL); #endif - obstack_free(&obst, NULL); - + /* TODO: graph might be changed, handle more graceful */ + set_irg_outs_inconsistent(irg); + set_irg_extblk_inconsistent(irg); + set_irg_loopinfo_inconsistent(irg); free_dom(irg); + free_cdep(irg); }