# include "dbginfo_t.h"
# include "iropt_dbg.h"
# include "irflag_t.h"
+# include "array.h"
# include "firmstat.h"
#undef IMAX
*/
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;
+/**
+ * flags for control flow
+ */
+enum block_flags_t {
+ BLOCK_HAS_COND = 1, /**< Block has conditional control flow */
+ BLOCK_HAS_EXC = 2 /**< Block has exceptionl control flow */
+};
+
+/**
+ * a Block info
+ */
+typedef struct _block_info_t {
+ unsigned flags; /**< flags for the block */
+} block_info_t;
+
/**
* walker, clears all links first
*/
/**
* get the Load/Store info of a node
*/
-static ldst_info_t *get_info(ir_node *node, walk_env_t *env)
+static ldst_info_t *get_ldst_info(ir_node *node, walk_env_t *env)
{
ldst_info_t *info = get_irn_link(node);
}
/**
- * update the info for a Load/Store
+ * get the Block info of a node
*/
-static void update_projs(ldst_info_t *info, ir_node *proj)
+static block_info_t *get_block_info(ir_node *node, walk_env_t *env)
+{
+ block_info_t *info = get_irn_link(node);
+
+ if (! info) {
+ info = obstack_alloc(&env->obst, sizeof(*info));
+
+ memset(info, 0, sizeof(*info));
+
+ set_irn_link(node, info);
+ }
+ return info;
+}
+
+/**
+ * update the projection info for a Load/Store
+ */
+static int update_projs(ldst_info_t *info, ir_node *proj)
{
long nr = get_Proj_proj(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
+ *
+ * walks form Start -> End
*/
-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;
+ ldst_info_t *ldst_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);
+ ldst_info = get_ldst_info(pred, wenv);
+
+ wenv->changes |= update_projs(ldst_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) {
+ ir_node *pred_block;
+ block_info_t *bl_info;
+
+ pred = skip_Proj(get_Block_cfgpred(node, i));
- update_projs(info, n);
+ /* ignore Bad predecessors, they will be removed later */
+ if (is_Bad(pred))
+ continue;
+
+ pred_block = get_nodes_block(pred);
+ bl_info = get_block_info(pred_block, wenv);
+
+ if (is_fragile_op(pred))
+ bl_info->flags |= BLOCK_HAS_EXC;
+ else if (is_forking_op(pred))
+ bl_info->flags |= BLOCK_HAS_COND;
+
+ if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) {
+ ldst_info = get_ldst_info(pred, wenv);
+
+ wenv->changes |= update_exc(ldst_info, node, i);
+ }
}
}
}
* throw an exception when the previous Store was quiet.
*/
if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
+ DBG_OPT_RAW(pred, load);
exchange( info->projs[pn_Load_res], get_Store_value(pred) );
+
if (info->projs[pn_Load_M])
exchange(info->projs[pn_Load_M], mem);
if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
ldst_info_t *pred_info = get_irn_link(pred);
+ DBG_OPT_RAR(pred, load);
+
if (pred_info->projs[pn_Load_res]) {
/* we need a data proj from the previous load for this optimization */
exchange( info->projs[pn_Load_res], pred_info->projs[pn_Load_res] );
* TODO: What, if both have the same exception handler ???
*/
if (get_Store_volatility(pred) != volatility_is_volatile && !pred_info->projs[pn_Store_X_except]) {
+ DBG_OPT_WAW(pred, store);
exchange( pred_info->projs[pn_Store_M], get_Store_mem(pred) );
res = 1;
}
* We may remove the second Store, if it does not have an exception handler.
*/
if (! info->projs[pn_Store_X_except]) {
+ DBG_OPT_WAR(pred, store);
exchange( info->projs[pn_Store_M], mem );
res = 1;
}
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 the number of stores and allows for predicated execution.
+ * Moves Stores back to the end of a function which may be bad
+ *
+ * Is only allowed if the predecessor blocks have only one successor.
+ */
+static int optimize_phi(ir_node *phi, void *env)
+{
+ walk_env_t *wenv = env;
+ int i, n;
+ ir_node *store, *ptr, *block, *phiM, *phiD, *exc, *projM;
+ ir_mode *mode;
+ ir_node **inM, **inD;
+ int *idx;
+ dbg_info *db = NULL;
+ ldst_info_t *info;
+ block_info_t *bl_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;
+
+ /* abort on bad blocks */
+ if (is_Bad(get_nodes_block(store)))
+ return 0;
+
+ /* check if the block has only one output */
+ bl_info = get_irn_link(get_nodes_block(store));
+ if (bl_info->flags)
+ 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;
+
+ /* abort on bad blocks */
+ if (is_Bad(get_nodes_block(store)))
+ return 0;
+
+ /* check if the block has only one output */
+ bl_info = get_irn_link(get_nodes_block(store));
+ if (bl_info->flags)
+ 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
+ *
+ * Is only allowed if the predecessor blocks have only one successor.
+ */
+
+ /* 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);
+ projM = new_rd_Proj(NULL, current_ir_graph, block, store, mode_M, pn_Store_M);
+
+ info = get_ldst_info(store, wenv);
+ info->projs[pn_Store_M] = projM;
+
+ /* 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);
+
+ info->projs[pn_Store_X_except] = projX;
+ info->exc_block = exc;
+ info->exc_idx = idx[0];
+
+ 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, projM);
+
+ return 1;
+}
+
/**
* walker, collects all Load/Store/Proj nodes
*/
wenv->changes |= optimize_store(n);
break;
+ case iro_Phi:
+ wenv->changes |= optimize_phi(n, env);
+
default:
;
}
projects / libfirm / blobdiff