/*
- * Project: libFIRM
- * File name: ir/opt/ldstopt.c
- * Purpose: load store optimizations
- * Author: Michael Beck
- * Created:
- * CVS-ID: $Id$
- * Copyright: (c) 1998-2007 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 Load/Store optimizations.
+ * @author Michael Beck
+ * @version $Id$
*/
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
-#ifdef HAVE_ALLOCA_H
-#include <alloca.h>
-#endif
-#ifdef HAVE_MALLOC_H
-#include <malloc.h>
-#endif
-#ifdef HAVE_STRING_H
-# include <string.h>
-#endif
+#include <string.h>
+#include "iroptimize.h"
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irmode_t.h"
#include "irtools.h"
#include "opt_polymorphy.h"
#include "irmemory.h"
+#include "xmalloc.h"
#ifdef DO_CACHEOPT
#include "cacheopt/cachesim.h"
}
} /* reduce_adr_usage */
+/**
+ * Check, if an already existing value of mode old_mode can be converted
+ * into the needed one new_mode without loss.
+ */
+static int can_use_stored_value(ir_mode *old_mode, ir_mode *new_mode) {
+ if (old_mode == new_mode)
+ return 1;
+
+ /* if both modes are two-complement ones, we can always convert the
+ Stored value into the needed one. */
+ if (get_mode_size_bits(old_mode) >= get_mode_size_bits(new_mode) &&
+ get_mode_arithmetic(old_mode) == irma_twos_complement &&
+ get_mode_arithmetic(new_mode) == irma_twos_complement)
+ return 1;
+ return 0;
+} /* can_use_stored_value */
+
/**
* Follow the memory chain as long as there are only Loads
* and alias free Stores and try to replace current Load or Store
* is possible a = *(ir_type1 *)p; b = *(ir_type2 *)p ...
*/
if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
- get_irn_mode(get_Store_value(pred)) == load_mode) {
+ can_use_stored_value(get_irn_mode(get_Store_value(pred)), load_mode)) {
/*
* a Load immediately after a Store -- a read after write.
* We may remove the Load, if both Load & Store does not have an exception handler
* We could make it a little bit better if we would know that the exception
* handler of the Store jumps directly to the end...
*/
- if ((!pred_info->projs[pn_Store_X_except] && !info->projs[pn_Load_X_except]) ||
+ if ((pred_info->projs[pn_Store_X_except] == NULL && info->projs[pn_Load_X_except] == NULL) ||
get_nodes_block(load) == get_nodes_block(pred)) {
ir_node *value = get_Store_value(pred);
DBG_OPT_RAW(load, value);
+
+ /* add an convert if needed */
+ if (get_irn_mode(get_Store_value(pred)) != load_mode) {
+ value = new_r_Conv(current_ir_graph, get_nodes_block(load), value, load_mode);
+ }
+
if (info->projs[pn_Load_M])
exchange(info->projs[pn_Load_M], mem);
return res | DF_CHANGED;
}
} else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
- get_Load_mode(pred) == load_mode) {
+ can_use_stored_value(get_Load_mode(pred), load_mode)) {
/*
* a Load after a Load -- a read after read.
* We may remove the second Load, if it does not have an exception handler
* Here, there is no need to check if the previous Load has an exception
* hander because they would have exact the same exception...
*/
- if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
- DBG_OPT_RAR(load, pred);
+ if (info->projs[pn_Load_X_except] == NULL || get_nodes_block(load) == get_nodes_block(pred)) {
+ ir_node *value;
- if (pred_info->projs[pn_Load_res]) {
- /* we need a data proj from the previous load for this optimization */
- if (info->projs[pn_Load_res])
- exchange(info->projs[pn_Load_res], pred_info->projs[pn_Load_res]);
+ DBG_OPT_RAR(load, pred);
- if (info->projs[pn_Load_M])
- exchange(info->projs[pn_Load_M], mem);
- } else {
- if (info->projs[pn_Load_res]) {
- set_Proj_pred(info->projs[pn_Load_res], pred);
- set_nodes_block(info->projs[pn_Load_res], get_nodes_block(pred));
- pred_info->projs[pn_Load_res] = info->projs[pn_Load_res];
+ /* the result is used */
+ if (info->projs[pn_Load_res]) {
+ if (pred_info->projs[pn_Load_res] == NULL) {
+ /* create a new Proj again */
+ pred_info->projs[pn_Load_res] = new_r_Proj(current_ir_graph, get_nodes_block(pred), pred, get_Load_mode(pred), pn_Load_res);
}
- if (info->projs[pn_Load_M]) {
- /* Actually, this if should not be necessary. Construct the Loads
- properly!!! */
- exchange(info->projs[pn_Load_M], mem);
+ value = pred_info->projs[pn_Load_res];
+
+ /* add an convert if needed */
+ if (get_Load_mode(pred) != load_mode) {
+ value = new_r_Conv(current_ir_graph, get_nodes_block(load), value, load_mode);
}
+
+ exchange(info->projs[pn_Load_res], value);
}
+ if (info->projs[pn_Load_M])
+ exchange(info->projs[pn_Load_M], mem);
+
/* no exception */
if (info->projs[pn_Load_X_except]) {
exchange(info->projs[pn_Load_X_except], new_Bad());
}
if (get_irn_op(pred) == op_Store) {
- /* check if we can pass thru this store */
+ /* check if we can pass through this store */
ir_alias_relation rel = get_alias_relation(
current_ir_graph,
get_Store_ptr(pred),
get_irn_mode(get_Store_value(pred)),
- ptr, load_mode, opt_non_opt);
+ ptr, load_mode);
/* if the might be an alias, we cannot pass this Store */
if (rel != no_alias)
break;
return res;
} /* optimize_load */
+/**
+ * Check whether a value of mode new_mode would completely overwrite a value
+ * of mode old_mode in memory.
+ */
+static int is_completely_overwritten(ir_mode *old_mode, ir_mode *new_mode)
+{
+ return get_mode_size_bits(new_mode) >= get_mode_size_bits(old_mode);
+} /* is_completely_overwritten */
+
/**
* follow the memory chain as long as there are only Loads and alias free Stores.
*
* if the pointers are identical, they refer to the same object.
* This is only true in strong typed languages, not is C were the following
* is possible *(ir_type1 *)p = a; *(ir_type2 *)p = b ...
+ * However, if the mode that is written have a bigger or equal size the the old
+ * one, the old value is completely overwritten and can be killed ...
*/
if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
- get_nodes_block(pred) == block && get_irn_mode(get_Store_value(pred)) == mode) {
+ get_nodes_block(pred) == block &&
+ is_completely_overwritten(get_irn_mode(get_Store_value(pred)), mode)) {
/*
* a Store after a Store in the same block -- a write after write.
* We may remove the first Store, if it does not have an exception handler.
current_ir_graph,
get_Store_ptr(pred),
get_irn_mode(get_Store_value(pred)),
- ptr, mode, opt_non_opt);
+ ptr, mode);
/* if the might be an alias, we cannot pass this Store */
if (rel != no_alias)
break;
int i, n;
ir_node *store, *old_store, *ptr, *block, *phi_block, *phiM, *phiD, *exc, *projM;
ir_mode *mode;
- ir_node **inM, **inD, **stores;
+ ir_node **inM, **inD, **projMs;
int *idx;
dbg_info *db = NULL;
ldst_info_t *info;
if (n <= 0)
return 0;
- store = skip_Proj(get_Phi_pred(phi, 0));
+ /* must be only one user */
+ projM = get_Phi_pred(phi, 0);
+ if (get_irn_n_edges(projM) != 1)
+ return 0;
+
+ store = skip_Proj(projM);
old_store = store;
if (get_irn_op(store) != op_Store)
return 0;
return 0;
phi_block = get_nodes_block(phi);
- if (! block_postdominates(phi_block, block))
+ if (! block_strictly_postdominates(phi_block, block))
return 0;
/* this is the address of the store */
exc = info->exc_block;
for (i = 1; i < n; ++i) {
- ir_node *pred = skip_Proj(get_Phi_pred(phi, i));
+ ir_node *pred = get_Phi_pred(phi, i);
+
+ if (get_irn_n_edges(pred) != 1)
+ return 0;
+ pred = skip_Proj(pred);
if (get_irn_op(pred) != op_Store)
return 0;
* Is only allowed if the predecessor blocks have only one successor.
*/
- NEW_ARR_A(ir_node *, stores, n);
+ NEW_ARR_A(ir_node *, projMs, n);
NEW_ARR_A(ir_node *, inM, n);
NEW_ARR_A(ir_node *, inD, n);
NEW_ARR_A(int, idx, n);
first because we otherwise may loose a store when exchanging its
memory Proj.
*/
- for (i = 0; i < n; ++i)
- stores[i] = skip_Proj(get_Phi_pred(phi, i));
-
- /* Prepare: Skip the memory Proj: we need this in the case some stores
- are cascaded.
- Beware: One Store might be included more than once in the stores[]
- list, so we must prevent to do the exchange more than once.
- */
- for (i = 0; i < n; ++i) {
- ir_node *store = stores[i];
- ir_node *proj_m;
+ for (i = n - 1; i >= 0; --i) {
+ ir_node *store;
- info = get_irn_link(store);
- proj_m = info->projs[pn_Store_M];
+ projMs[i] = get_Phi_pred(phi, i);
+ assert(is_Proj(projMs[i]));
- if (is_Proj(proj_m) && get_Proj_pred(proj_m) == store)
- exchange(proj_m, get_Store_mem(store));
- }
-
- /* first step: collect all inputs */
- for (i = 0; i < n; ++i) {
- ir_node *store = stores[i];
- info = get_irn_link(store);
+ store = get_Proj_pred(projMs[i]);
+ info = get_irn_link(store);
inM[i] = get_Store_mem(store);
inD[i] = get_Store_value(store);
/* third step: create a new data Phi */
phiD = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inD, mode);
+ /* rewire memory and kill the node */
+ for (i = n - 1; i >= 0; --i) {
+ ir_node *proj = projMs[i];
+
+ if(is_Proj(proj)) {
+ ir_node *store = get_Proj_pred(proj);
+ exchange(proj, inM[i]);
+ kill_node(store);
+ }
+ }
+
/* fourth step: create the Store */
store = new_rd_Store(db, current_ir_graph, block, phiM, ptr, phiD);
#ifdef DO_CACHEOPT
switch (get_irn_opcode(n)) {
- case iro_Load:
- wenv->changes |= optimize_load(n);
- break;
+ case iro_Load:
+ wenv->changes |= optimize_load(n);
+ break;
- case iro_Store:
- wenv->changes |= optimize_store(n);
- break;
+ case iro_Store:
+ wenv->changes |= optimize_store(n);
+ break;
- case iro_Phi:
- wenv->changes |= optimize_phi(n, wenv);
+ case iro_Phi:
+ wenv->changes |= optimize_phi(n, wenv);
- default:
- ;
+ default:
+ ;
}
} /* do_load_store_optimize */
/* Handle graph state */
if (env.changes) {
- if (get_irg_outs_state(irg) == outs_consistent)
- set_irg_outs_inconsistent(irg);
+ set_irg_outs_inconsistent(irg);
}
if (env.changes & CF_CHANGED) {