From d6a329898caaf412be1561a8345c7aeccc5f5a5a Mon Sep 17 00:00:00 2001 From: Michael Beck Date: Tue, 28 Sep 2004 16:48:13 +0000 Subject: [PATCH] Move Stores below the CF. [r3990] --- ir/opt/ldstopt.c | 169 +++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 162 insertions(+), 7 deletions(-) diff --git a/ir/opt/ldstopt.c b/ir/opt/ldstopt.c index 43926ca2e..86a34c233 100644 --- a/ir/opt/ldstopt.c +++ b/ir/opt/ldstopt.c @@ -20,6 +20,7 @@ # include "dbginfo_t.h" # include "iropt_dbg.h" # include "irflag_t.h" +# include "array.h" # include "firmstat.h" #undef IMAX @@ -40,6 +41,8 @@ typedef struct _walk_env_t { */ typedef struct _ldst_info_t { ir_node *projs[MAX_PROJ]; /**< list of Proj's of this node */ + ir_node *exc_block; /**< the exception block if available */ + int exc_idx; /**< predecessor index in the exception block */ } ldst_info_t; /** @@ -68,9 +71,9 @@ static ldst_info_t *get_info(ir_node *node, walk_env_t *env) } /** - * update the info for a Load/Store + * update the projection info for a Load/Store */ -static void update_projs(ldst_info_t *info, ir_node *proj) +static int update_projs(ldst_info_t *info, ir_node *proj) { long nr = get_Proj_proj(proj); @@ -79,27 +82,55 @@ static void update_projs(ldst_info_t *info, ir_node *proj) if (info->projs[nr]) { /* there is already one, do CSE */ exchange(proj, info->projs[nr]); + return 1; } - else + else { info->projs[nr] = proj; + return 0; + } +} + +/** + * update the exception block info for a Load/Store + */ +static int update_exc(ldst_info_t *info, ir_node *block, int pos) +{ + assert(info->exc_block == NULL && "more than one exception block found"); + + info->exc_block = block; + info->exc_idx = pos; + return 0; } /** * walker, collects all Load/Store/Proj nodes */ -static void collect_nodes(ir_node *n, void *env) +static void collect_nodes(ir_node *node, void *env) { ir_node *pred; ldst_info_t *info; walk_env_t *wenv = env; - if (get_irn_op(n) == op_Proj) { - pred = get_Proj_pred(n); + if (get_irn_op(node) == op_Proj) { + pred = get_Proj_pred(node); if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) { info = get_info(pred, wenv); - update_projs(info, n); + wenv->changes |= update_projs(info, node); + } + } + else if (get_irn_op(node) == op_Block) { /* check, if it's an exception block */ + int i, n; + + for (i = 0, n = get_Block_n_cfgpreds(node); i < n; ++i) { + pred = skip_Proj(get_Block_cfgpred(node, i)); + + if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) { + info = get_info(pred, wenv); + + wenv->changes |= update_exc(info, node, i); + } } } } @@ -248,6 +279,127 @@ static int optimize_store(ir_node *store) return res; } +/** + * walker, optimizes Phi after Stores: + * Does the following optimization: + * + * val1 val2 val3 val1 val2 val3 + * | | | \ | / + * Str Str Str \ | / + * \ | / Phi + * \ | / | + * \ | / Str + * Phi + * + * This removes teh number of stores and allows for predicated execution. + * Moves Stores back to the end of a function which may be bad + * + * Note: that even works, if one of the Stores is already in our current block + */ +static int optimize_phi(ir_node *phi) +{ + int i, n; + ir_node *store, *ptr, *block, *phiM, *phiD, *exc; + ir_mode *mode; + ir_node **inM, **inD; + int *idx; + dbg_info *db = NULL; + ldst_info_t *info; + + /* Must be a memory Phi */ + if (get_irn_mode(phi) != mode_M) + return 0; + + n = get_Phi_n_preds(phi); + if (n <= 0) + return 0; + + store = skip_Proj(get_Phi_pred(phi, 0)); + if (get_irn_op(store) != op_Store) + return 0; + + /* this is the address of the store */ + ptr = get_Store_ptr(store); + mode = get_irn_mode(get_Store_value(store)); + info = get_irn_link(store); + exc = info->exc_block; + + for (i = 1; i < n; ++i) { + ir_node *pred = skip_Proj(get_Phi_pred(phi, i)); + + if (get_irn_op(pred) != op_Store) + return 0; + + if (mode != get_irn_mode(get_Store_value(pred)) || ptr != get_Store_ptr(pred)) + return 0; + + info = get_irn_link(pred); + + /* check, if all stores have the same exception flow */ + if (exc != info->exc_block) + return 0; + } + + /* + * ok, when we are here, we found all predecessors of a Phi that + * are Stores to the same address. That means whatever we do before + * we enter the block of the Phi, we do a Store. + * So, we can move the store to the current block: + * + * val1 val2 val3 val1 val2 val3 + * | | | \ | / + * | Str | | Str | | Str | \ | / + * \ | / Phi + * \ | / | + * \ | / Str + * Phi + * + * Note: that even works, if one of the Stores is already in our current block + */ + + /* first step: collect all inputs */ + NEW_ARR_A(ir_node *, inM, n); + NEW_ARR_A(ir_node *, inD, n); + NEW_ARR_A(int, idx, n); + + for (i = 0; i < n; ++i) { + ir_node *pred = skip_Proj(get_Phi_pred(phi, i)); + info = get_irn_link(pred); + + inM[i] = get_Store_mem(pred); + inD[i] = get_Store_value(pred); + idx[i] = info->exc_idx; + } + block = get_nodes_block(phi); + + /* second step: create a new memory Phi */ + phiM = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inM, mode_M); + + /* third step: create a new data Phi */ + phiD = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inD, mode); + + /* fourth step: create the Store */ + store = new_rd_Store(db, current_ir_graph, block, phiM, ptr, phiD); + + /* fifths step: repair exception flow */ + if (exc) { + ir_node *projX = new_rd_Proj(NULL, current_ir_graph, block, store, mode_X, pn_Store_X_except); + + for (i = 0; i < n; ++i) { + set_Block_cfgpred(exc, idx[i], projX); + } + + if (n > 1) { + /* the exception block should be optimized as some inputs are identical now */ + } + } + + /* sixt step: replace old Phi */ + exchange(phi, new_rd_Proj(NULL, current_ir_graph, block, store, mode_M, pn_Store_M)); + + return 1; +} + /** * walker, collects all Load/Store/Proj nodes */ @@ -265,6 +417,9 @@ static void do_load_store_optimize(ir_node *n, void *env) wenv->changes |= optimize_store(n); break; + case iro_Phi: + wenv->changes |= optimize_phi(n); + default: ; } -- 2.20.1