/*
- * Project: libFIRM
- * File name: ir/opt/scalar_replace.c
- * Purpose: scalar replacement of arrays and compounds
- * Author: Beyhan Veliev
- * Modified by: Michael Beck
- * Created:
- * CVS-ID: $Id$
- * Copyright: (c) 1998-2005 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 Scalar replacement of compounds.
+ * @author Beyhan Veliev, 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 "iroptimize.h"
#include "scalar_replace.h"
#include "irflag_t.h"
#include "irouts.h"
#include "irgmod.h"
#include "irnode_t.h"
#include "irtools.h"
+#include "xmalloc.h"
#define SET_VNUM(node, vnum) set_irn_link(node, INT_TO_PTR(vnum))
#define GET_VNUM(node) (unsigned)PTR_TO_INT(get_irn_link(node))
* accesses like a.b.c[8].d
*/
typedef union {
- entity *ent;
+ ir_entity *ent;
tarval *tv;
} path_elem_t;
/**
* An access path, used to assign value numbers
- * to variables that will be scalar replaced
+ * to variables that will be scalar replaced.
*/
typedef struct _path_t {
- unsigned vnum; /**< the value number */
- unsigned path_len; /**< the length of the access path */
- path_elem_t path[1]; /**< the path */
+ unsigned vnum; /**< The value number. */
+ unsigned path_len; /**< The length of the access path. */
+ path_elem_t path[1]; /**< The path. */
} path_t;
+/** The size of a path in bytes. */
+#define PATH_SIZE(p) (sizeof(*(p)) + sizeof((p)->path[0]) * ((p)->path_len - 1))
+
typedef struct _scalars_t {
- entity *ent; /**< A entity for scalar replacement. */
- type *ent_owner; /**< The owner of this entity. */
+ ir_entity *ent; /**< A entity for scalar replacement. */
+ ir_type *ent_owner; /**< The owner of this entity. */
} scalars_t;
}
/**
+ * Check the mode of a Load/Store with the mode of the entity
+ * that is accessed.
+ * If the mode of the entity and the Load/Store mode do not match, we
+ * have the bad reinterpret case:
+ *
+ * int i;
+ * char b = *(char *)&i;
+ *
+ * We do NOT count this as one value and return address_taken
+ * in that case.
+ * However, we support an often used case. If the mode is two-complement
+ * we allow casts between signed/unsigned.
+ *
+ * @param mode the mode of the Load/Store
+ * @param ent_mode the mode of the accessed entity
+ */
+static int check_load_store_mode(ir_mode *mode, ir_mode *ent_mode) {
+ if (ent_mode != mode) {
+ if (ent_mode == NULL ||
+ get_mode_size_bits(ent_mode) != get_mode_size_bits(mode) ||
+ get_mode_sort(ent_mode) != get_mode_sort(mode) ||
+ get_mode_arithmetic(ent_mode) != irma_twos_complement ||
+ get_mode_arithmetic(mode) != irma_twos_complement)
+ return 0;
+ }
+ return 1;
+}
+
+/*
* Returns non-zero, if the address of an entity
* represented by a Sel node (or it's successor Sels) is taken.
- *
- * @param sel the Sel node
*/
-static int is_address_taken(ir_node *sel)
+int is_address_taken(ir_node *sel)
{
- int i, n;
+ int i;
+ ir_mode *emode, *mode;
+ ir_node *value;
+ ir_entity *ent;
if (! is_const_sel(sel))
return 1;
- n = get_irn_n_outs(sel);
- for (i = 0; i < n; ++i) {
+ for (i = get_irn_n_outs(sel) - 1; i >= 0; --i) {
ir_node *succ = get_irn_out(sel, i);
switch (get_irn_opcode(succ)) {
case iro_Load:
- /* ok, we just load from that entity */
+ /* check if this load is not a hidden conversion */
+ mode = get_Load_mode(succ);
+ ent = get_Sel_entity(sel);
+ emode = get_type_mode(get_entity_type(ent));
+ if (! check_load_store_mode(mode, emode))
+ return 1;
break;
case iro_Store:
/* check that Sel is not the Store's value */
- if (get_Store_value(succ) == sel)
+ value = get_Store_value(succ);
+ if (value == sel)
+ return 1;
+ /* check if this Store is not a hidden conversion */
+ mode = get_irn_mode(value);
+ ent = get_Sel_entity(sel);
+ emode = get_type_mode(get_entity_type(ent));
+ if (! check_load_store_mode(mode, emode))
return 1;
break;
* @param ent the entity that will be scalar replaced
* @param sel a Sel node that selects some fields of this entity
*/
-static void link_all_leave_sels(entity *ent, ir_node *sel)
+static void link_all_leave_sels(ir_entity *ent, ir_node *sel)
{
int i, n, flag = 1;
for (i = 0; i < n; ++i) {
ir_node *succ = get_irn_out(sel, i);
- if (get_irn_op(succ) == op_Sel) {
+ if (is_Sel(succ)) {
link_all_leave_sels(ent, succ);
flag = 0;
}
for (i = 0; i < n; ++i) {
ir_node *succ = get_irn_out(irg_frame, i);
- if (get_irn_op(succ) == op_Sel) {
- entity *ent = get_Sel_entity(succ);
+ if (is_Sel(succ)) {
+ ir_entity *ent = get_Sel_entity(succ);
set_entity_link(ent, NULL);
}
}
for (i = 0; i < n; ++i) {
ir_node *succ = get_irn_out(irg_frame, i);
- if (get_irn_op(succ) == op_Sel) {
- entity *ent = get_Sel_entity(succ);
- type *ent_type;
+ if (is_Sel(succ)) {
+ ir_entity *ent = get_Sel_entity(succ);
+ ir_type *ent_type;
if (get_entity_link(ent) == ADDRESS_TAKEN)
continue;
+ /*
+ * Beware: in rare cases even entities on the frame might be
+ * volatile. This might happen if the entity serves as a store
+ * to a value that must survive a exception. Do not optimize
+ * such entities away.
+ */
+ if (get_entity_volatility(ent) == volatility_is_volatile) {
+ set_entity_link(ent, ADDRESS_TAKEN);
+ continue;
+ }
+
ent_type = get_entity_type(ent);
/* we can handle arrays, structs and atomic types yet */
n = get_Sel_n_indexs(sel);
len += n + 1;
- if (get_irn_op(pred) != op_Sel) {
+ if (! is_Sel(pred)) {
/* we found the root */
res = xmalloc(sizeof(*res) + (len - 1) * sizeof(res->path));
*
* @return the next free value number
*/
-static unsigned allocate_value_numbers(pset *sels, entity *ent, unsigned vnum, ir_mode ***modes)
+static unsigned allocate_value_numbers(pset *sels, ir_entity *ent, unsigned vnum, ir_mode ***modes)
{
ir_node *sel, *next;
path_t *key, *path;
pset_insert_ptr(sels, sel);
key = find_path(sel, 0);
- path = set_find(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
+ path = set_find(pathes, key, PATH_SIZE(key), path_hash(key));
if (path)
SET_VNUM(sel, path->vnum);
else {
- unsigned i;
-
key->vnum = vnum++;
- set_insert(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
+ set_insert(pathes, key, PATH_SIZE(key), path_hash(key));
SET_VNUM(sel, key->vnum);
ARR_EXTO(ir_mode *, *modes, (key->vnum + 15) & ~15);
#ifdef DEBUG_libfirm
/* Debug output */
if (get_opt_scalar_replacement_verbose() && get_firm_verbosity() > 1) {
- printf(" %s", get_entity_name(ent));
+ unsigned i;
+ printf(" %s", get_entity_name(key->path[0].ent));
for (i = 1; i < key->path_len; ++i) {
if (is_entity(key->path[i].ent))
printf(".%s", get_entity_name(key->path[i].ent));
} env_t;
/**
- * Walker
+ * topological walker.
*/
-static void handle_first(ir_node *node, void *ctx)
+static void topologic_walker(ir_node *node, void *ctx)
{
env_t *env = ctx;
ir_op *op = get_irn_op(node);
- ir_node *adr, *block, *mem, *unk, **value_arr, **in;
+ ir_node *adr, *block, *mem, *unk, **value_arr, **in, *val;
+ ir_mode *mode;
unsigned vnum;
int i, j, n;
list_entry_t *l;
/* a load, check if we can resolve it */
adr = get_Load_ptr(node);
- if (get_irn_op(adr) != op_Sel)
+ if (! is_Sel(adr))
return;
if (! pset_find_ptr(env->sels, adr))
if (value_arr[vnum]) {
mem = get_Load_mem(node);
+ /* Beware: A Load can contain a hidden conversion in Firm.
+ This happens for instance in the following code:
+
+ int i;
+ unsigned j = *(unsigned *)&i;
+
+ Handle this here. */
+ val = value_arr[vnum];
+ mode = get_Load_mode(node);
+ if (mode != get_irn_mode(val))
+ val = new_d_Conv(get_irn_dbg_info(node), val, mode);
+
turn_into_tuple(node, pn_Load_max);
- set_Tuple_pred(node, pn_Load_M, mem);
- set_Tuple_pred(node, pn_Load_res, value_arr[vnum]);
- set_Tuple_pred(node, pn_Load_X_except, new_Bad());
- }
- else {
+ set_Tuple_pred(node, pn_Load_M, mem);
+ set_Tuple_pred(node, pn_Load_res, val);
+ set_Tuple_pred(node, pn_Load_X_regular, new_r_Jmp(current_ir_graph, block));
+ set_Tuple_pred(node, pn_Load_X_except, new_Bad());
+ } else {
l = obstack_alloc(&env->obst, sizeof(*l));
l->node = node;
l->vnum = vnum;
set_irn_link(node, env->fix_loads);
env->fix_loads = l;
}
- }
- else if (op == op_Store) {
+ } else if (op == op_Store) {
/* a Store always can be replaced */
adr = get_Store_ptr(node);
- if (get_irn_op(adr) != op_Sel)
+ if (! is_Sel(adr))
return;
if (! pset_find_ptr(env->sels, adr))
block = get_nodes_block(node);
value_arr = get_irn_link(block);
- value_arr[vnum] = get_Store_value(node);
+ /* Beware: A Store can contain a hidden conversion in Firm. */
+ val = get_Store_value(node);
+ if (get_irn_mode(val) != env->modes[vnum])
+ val = new_d_Conv(get_irn_dbg_info(node), val, env->modes[vnum]);
+ value_arr[vnum] = val;
mem = get_Store_mem(node);
+ block = get_nodes_block(node);
turn_into_tuple(node, pn_Store_max);
- set_Tuple_pred(node, pn_Store_M, mem);
- set_Tuple_pred(node, pn_Store_X_except, new_Bad());
- }
- else if (op == op_Phi && get_irn_mode(node) == mode_M) {
+ set_Tuple_pred(node, pn_Store_M, mem);
+ set_Tuple_pred(node, pn_Store_X_regular, new_r_Jmp(current_ir_graph, block));
+ set_Tuple_pred(node, pn_Store_X_except, new_Bad());
+ } else if (op == op_Phi && get_irn_mode(node) == mode_M) {
/*
* found a memory Phi: Here, we must create new Phi nodes
*/
* searches through blocks beginning from block for value
* vnum and return it.
*/
-static ir_node *find_value(ir_node *block, unsigned vnum)
+static ir_node *find_vnum_value(ir_node *block, unsigned vnum)
{
ir_node **value_arr;
int i;
for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
ir_node *pred = get_Block_cfgpred(block, i);
- res = find_value(get_nodes_block(pred), vnum);
+ res = find_vnum_value(get_nodes_block(pred), vnum);
if (res)
return res;
}
pred = get_nodes_block(pred);
inc_irg_block_visited(current_ir_graph);
- val = find_value(pred, l->vnum);
+ val = find_vnum_value(pred, l->vnum);
if (val)
set_irn_n(phi, i, val);
static void fix_loads(env_t *env)
{
list_entry_t *l;
- ir_node *load, *block, *pred, *val, *mem;
+ ir_node *load, *block, *pred, *val = NULL, *mem;
+ ir_mode *mode;
int i;
for (l = env->fix_loads; l; l = get_irn_link(load)) {
pred = get_nodes_block(pred);
inc_irg_block_visited(current_ir_graph);
- val = find_value(pred, l->vnum);
+ val = find_vnum_value(pred, l->vnum);
if (val)
break;
val = new_Unknown(env->modes[l->vnum]);
}
- mem = get_Load_mem(load);
+ /* Beware: A Load can contain a hidden conversion in Firm.
+ Handle this here. */
+ mode = get_Load_mode(load);
+ if (mode != get_irn_mode(val))
+ val = new_d_Conv(get_irn_dbg_info(load), val, mode);
+
+ mem = get_Load_mem(load);
turn_into_tuple(load, pn_Load_max);
- set_Tuple_pred(load, pn_Load_M, mem);
- set_Tuple_pred(load, pn_Load_res, val);
- set_Tuple_pred(load, pn_Load_X_except, new_Bad());
+ set_Tuple_pred(load, pn_Load_M, mem);
+ set_Tuple_pred(load, pn_Load_res, val);
+ set_Tuple_pred(load, pn_Load_X_regular, new_r_Jmp(current_ir_graph, block));
+ set_Tuple_pred(load, pn_Load_X_except, new_Bad());
}
}
* second step: walk over the graph blockwise in topological order
* and fill the array as much as possible.
*/
- irg_walk_blkwise_graph(current_ir_graph, NULL, handle_first, &env);
+ irg_walk_blkwise_graph(current_ir_graph, NULL, topologic_walker, &env);
/* third, fix the list of Phis, then the list of Loads */
fix_phis(&env);
ir_mode **modes;
set *set_ent;
pset *sels;
- type *ent_type;
+ ir_type *ent_type;
ir_graph *rem;
if (! get_opt_scalar_replacement())
rem = current_ir_graph;
/* Call algorithm that computes the out edges */
- if (get_irg_outs_state(irg) != outs_consistent)
- compute_irg_outs(irg);
+ assure_irg_outs(irg);
/* Find possible scalar replacements */
if (find_possible_replacements(irg)) {
for (i = 0 ; i < get_irn_n_outs(irg_frame); i++) {
ir_node *succ = get_irn_out(irg_frame, i);
- if (get_irn_op(succ) == op_Sel) {
- entity *ent = get_Sel_entity(succ);
+ if (is_Sel(succ)) {
+ ir_entity *ent = get_Sel_entity(succ);
if (get_entity_link(ent) == NULL || get_entity_link(ent) == ADDRESS_TAKEN)
continue;
projects / libfirm / blobdiff