/*
- * Project: libFIRM
- * File name: ir/opt/data_flow_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-2008 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.
*/
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-#ifdef HAVE_ALLOCA_H
-#include <alloca.h>
-#endif
+/**
+ * @file
+ * @brief scalar replacement of arrays and compounds
+ * @author Beyhan Veliev, Michael Beck
+ * @version $Id$
+ */
+#include "config.h"
-#ifdef HAVE_MALLOC_H
-#include <malloc.h>
-#endif
+#include "iroptimize.h"
-#ifdef HAVE_STRING_H
#include <string.h>
-#endif
-#include "data_flow_scalar_replace.h"
#include "irflag_t.h"
#include "irouts.h"
#include "pset.h"
#include "irloop.h"
#include "analyze_irg_args.h"
#include "irprintf.h"
-#include "compute_loop_info.h"
#include "irgopt.h"
+#include "xmalloc.h"
#define SET_ENT_VNUM(ent, vnum) set_entity_link(ent, INT_TO_PTR(vnum))
#define GET_ENT_VNUM(ent) (unsigned)PTR_TO_INT(get_entity_link(ent))
typedef struct _ent_leaves_t{
- entity *ent; /**< An entity, that contains scalars for replace.*/
+ ir_entity *ent; /**< An entity, that contains scalars for replace.*/
pset *leaves; /**< All leaves of this entity.*/
} ent_leaves_t;
typedef struct _sels_t {
ir_node *sel; /**< A sel node, thats entity have scalars.*/
- entity *ent; /**< The entity of this sel node.*/
+ ir_entity *ent; /**< The entity of this sel node.*/
}sels_t;
typedef struct _call_access_t {
* accesses like a.b.c[8].d
*/
typedef union {
- entity *ent;
+ ir_entity *ent;
tarval *tv;
} path_elem_t;
{
const ent_leaves_t *c1 = elt;
const ent_leaves_t *c2 = key;
+ (void) size;
return c1->ent != c2->ent;
}
*/
static int ent_cmp(const void *elt, const void *key)
{
- const entity *c1 = elt;
- const entity *c2 = key;
+ const ir_entity *c1 = elt;
+ const ir_entity *c2 = key;
return c1 != c2;
}
{
const sels_t *c1 = elt;
const sels_t *c2 = key;
+ (void) size;
return c1->sel != c2->sel;
}
*/
static int leave_cmp(const void *elt, const void *key)
{
- const ir_node *c1 = elt;
- const ir_node *c2 = key;
+ ir_node *c1 = (ir_node *)elt;
+ ir_node *c2 = (ir_node *)key;
- return c1->attr.s.ent != c2->attr.s.ent;
+ return get_Sel_entity(c1) != get_Sel_entity(c2);
}
/**
{
const call_access_t *c1 = elt;
const call_access_t *c2 = key;
+ (void) size;
return c1->call != c2->call;
}
{
const path_t *p1 = elt;
const path_t *p2 = key;
+ (void) size;
/* we can use memcmp here, because identical tarvals should have identical addresses */
return memcmp(p1->path, p2->path, p1->path_len * sizeof(p1->path[0]));
for (i = 0; i < n; ++i) {
ir_node *idx = get_Sel_index(sel, i);
- if (get_irn_op(idx) != op_Const)
+ if (!is_Const(idx))
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.
*/
-static int is_address_taken(ir_node *sel)
+static int is_address_taken_2(ir_node *sel)
{
int i;
case iro_Sel: {
/* Check the Sel successor of Sel */
- int res = is_address_taken(succ);
+ int res = is_address_taken_2(succ);
if (res)
return 1;
* @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;
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);
-
}
/* if Sel nodes with memory inputs are used, a entity can be
* visited more than once causing a ring here, so we use the
* node flag to mark linked nodes
*/
- if (irn_visited(sel))
+ if (irn_visited_else_mark(sel))
return;
/*
*/
set_irn_link(sel, get_entity_link(ent));
set_entity_link(ent, sel);
-
- mark_irn_visited(sel);
}
/* we need a special address that serves as an address taken marker */
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);
+ if (is_Sel(succ)) {
+ ir_entity *ent = get_Sel_entity(succ);
ir_type *ent_type;
if (get_entity_link(ent) == ADDRESS_TAKEN)
/* we can handle arrays, structs and atomic types yet */
if (is_Array_type(ent_type) || is_Struct_type(ent_type) || is_atomic_type(ent_type)) {
- if (is_address_taken(succ)) {
+ if (is_address_taken_2(succ)) {
if (get_entity_link(ent)) /* killing one */
--res;
set_entity_link(ent, ADDRESS_TAKEN);
for(i = get_irn_n_outs(sel) - 1; i >= 0; i--) {
succ = get_irn_out(sel, i);
- if(get_irn_op(succ) == op_Sel)
+ if (is_Sel(succ))
return 0;
}
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));
+ res = XMALLOCF(path_t, path, len);
res->path_len = len;
}
else
for (i = 0; i < n; ++i) {
ir_node *index = get_Sel_index(sel, i);
- if(get_irn_op(index) == op_Const)
+ if (is_Const(index))
res->path[pos++].tv = get_Const_tarval(index);
}
return res;
*
* @return the next free value number
*/
-static unsigned allocate_value_numbers(set *set_sels, pset *leaves, entity *ent, unsigned vnum)
+static unsigned allocate_value_numbers(set *set_sels, pset *leaves, ir_entity *ent, unsigned vnum)
{
ir_node *sel, *next;
path_t *key, *path;
val_arr = get_irn_link(pred);
if(val_arr[GET_ENT_VNUM(value_ent->ent)].access_type == SYNCED)
- /* This entity was synced.*/
- continue;
+ /* This entity was synced.*/
+ continue;
if(val_arr[GET_ENT_VNUM(value_ent->ent)].access_type <= 3) {
- /* To avoid repeated sync of this entity in this block.*/
- val_arr[GET_ENT_VNUM(value_ent->ent)].access_type = SYNCED;
+ /* To avoid repeated sync of this entity in this block.*/
+ val_arr[GET_ENT_VNUM(value_ent->ent)].access_type = SYNCED;
/* In this predecessor block is this entity not acessed.
* We must sync in the end ot this block.*/
if(get_Block_n_cfgpreds(blk) > 1)
/* We must check this, why it is possible to get a Bad node
* form new_r_Sync(), when the node can be optimized.
* In this case we must do nothing.*/
- if(get_irn_op(sync) == op_Sync) {
+ if (is_Sync(sync)) {
val_arr[env->gl_mem_vnum].mem_edge_state = sync;
/* We add this sync node to the sync's fix list.*/
add_sync_to_fixlist(val_arr[env->gl_mem_vnum].mem_edge_state, unk_vnum, env);
call_access_t key_call, *value_call;
ir_node *call_blk, *new_mem_state, *leave;
ir_node *sync, **in;
- entity *ent;
+ ir_entity *ent;
unsigned ent_vnum;
int fix_irn = 0; /**< Set to 1 if we must add this call to it fix list.*/
int *accessed_leaves_vnum = NULL; /**< An arraw, where are saved the value number, that
are synced from call's sync node, if we need it.*/
- if(get_irn_node_nr(call) == 2763)
- printf("\nHi\n");
-
call_blk = get_nodes_block(call);
val_arr = get_irn_link(call_blk);
/* An array to save the memory edges, that must be
/* We must check this, why it is possible to get a Bad node
* form new_r_Sync(), when the node can be optimized.
* In this case we must do nothing.*/
- if(get_irn_op(sync) == op_Sync) {
-
+ if (is_Sync(sync)) {
set_Call_mem(call, sync);
if(ARR_LEN(accessed_leaves_vnum))
/* We add this sync node to the sync's fix list.*/
else
irn_blk = get_nodes_block(irn);
- if (Block_not_block_visited(irn_blk)) {
+ if (!Block_block_visited(irn_blk)) {
/* We sync first the stored scalar address in this block.*/
mark_Block_block_visited(irn_blk);
sync_stored_scalars(irn_blk, env);
/* Calls that have a NoMem input do neither read nor write memory.
We can completely ignore them here. */
- if (get_irn_op(get_Call_mem(irn)) == op_NoMem)
+ if (is_NoMem(get_Call_mem(irn)))
return;
/* We save in this set all entities,
sel = get_Call_param(irn, i);
value_sels = NULL;
- if(get_irn_op(sel) == op_Sel) {
+ if (is_Sel(sel)) {
key_sels.sel = sel;
value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
* @param block A block from the current ir graph.
* @param vnum The value number, that must be found.
*/
-static ir_node *find_value(ir_node *block, unsigned vnum)
+static ir_node *find_vnum_value(ir_node *block, unsigned vnum)
{
value_arr_entry_t *val_arr;
int i;
ir_node *res;
- if (Block_not_block_visited(block)) {
+ if (!Block_block_visited(block)) {
mark_Block_block_visited(block);
val_arr = get_irn_link(block);
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;
}
static void fix_ls(env_t *env)
{
fixlist_entry_t *l;
- ir_node *irn, *block, *pred, *val;
+ ir_node *irn, *block, *pred, *val = NULL;
ir_op *op;
int i;
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;
if(val) {
if(op == op_Store)
- set_Store_mem(irn, val);
+ set_Store_mem(irn, val);
else
- if(op == op_Load)
- set_Load_mem(irn, val);
- else
- set_Call_mem(irn, val);
+ if(op == op_Load)
+ set_Load_mem(irn, val);
+ else
+ set_Call_mem(irn, val);
}
}
}
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);
pred = get_nodes_block(pred);
/* We first repair the global memory edge at the first position of sync predecessors.*/
- if(get_irn_op(get_irn_n(sync, 0)) == op_Unknown) {
+ if (is_Unknown(get_irn_n(sync, 0))) {
inc_irg_block_visited(current_ir_graph);
- val = find_value(pred, env->gl_mem_vnum);
+ val = find_vnum_value(pred, env->gl_mem_vnum);
if(val)
set_irn_n(sync, 0, val);
/* We repair the leaves*/
assert(k <= ARR_LEN(l->accessed_vnum) && "The algorythm for sync repair is wron");
- if(get_irn_op(get_irn_n(sync, i)) == op_Unknown) {
+ if (is_Unknown(get_irn_n(sync, i))) {
inc_irg_block_visited(current_ir_graph);
- val = find_value(pred, l->accessed_vnum[k++]);
+ val = find_vnum_value(pred, l->accessed_vnum[k++]);
if(val)
set_irn_n(sync, i, val);
vnum_state++;
/* We allocate the memory, that we need for the predecessors of the sync.*/
- in = xmalloc(sizeof(ir_node*) *vnum_state);
+ in = XMALLOCN(ir_node*, vnum_state);
/* The global memory edge is the first predecessor of this sync node.*/
if(val_arr[env->gl_mem_vnum].mem_edge_state == NULL) {
/* We must search through blocks for this memory state.*/
inc_irg_block_visited(current_ir_graph);
- in[0] = find_value(Return_blk, env->gl_mem_vnum);
+ in[0] = find_vnum_value(Return_blk, env->gl_mem_vnum);
}
else
in[0] = val_arr[env->gl_mem_vnum].mem_edge_state;
if(val_arr[vnum].mem_edge_state == NULL) {
/* We must search through blocks for this memory state.*/
inc_irg_block_visited(current_ir_graph);
- in[i] = find_value(Return_blk, vnum);
+ in[i] = find_vnum_value(Return_blk, vnum);
}
else
in[i] = val_arr[vnum].mem_edge_state;
int i, vnum;
unsigned int acces_type;
ir_node *param, *call_ptr, *blk;
- ir_op *op;
- entity *meth_ent;
+ ir_entity *meth_ent;
sels_t key_sels, *value_sels;
call_access_t key_call, *value_call;
value_arr_entry_t *val_arr;
env_t *env;
env = ctx;
- if(get_irn_op(irn) != op_Call)
+ if (!is_Call(irn))
return;
/* Calls that have a NoMem input do neither read nor write memory.
We can completely ignore them here. */
- if (get_irn_op(get_Call_mem(irn)) == op_NoMem)
+ if (is_NoMem(get_Call_mem(irn)))
return;
/* We iterate over the parameters of this call nodes.*/
for ( i = get_Call_n_params(irn) - 1; i >= 0; i--) {
param = get_Call_param(irn, i);
- if(get_irn_op(param) == op_Sel) {
+ if (is_Sel(param)) {
/* We have found a parameter with operation sel.*/
key_sels.sel = param;
value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
/* We have found a call, that have as parameter a sel from our set_sels.*/
call_ptr = get_Call_ptr(irn);
- op = get_irn_op(call_ptr);
- if(op == op_SymConst && get_SymConst_kind(call_ptr) == symconst_addr_ent) {
+ if (is_SymConst(call_ptr) && get_SymConst_kind(call_ptr) == symconst_addr_ent) {
meth_ent = get_SymConst_entity(call_ptr);
/* we get the access type for our sel.*/
acces_type = get_method_param_access(meth_ent, i);
}
}
-static int have_blk_phi_mem(ir_node *blk) {
-
- int i;
- ir_node *out;
-
- for(i = get_irn_n_outs(blk) - 1; i >= 0; i--) {
-
- out = get_irn_out(blk, i);
- if(get_irn_op(out) == op_Phi)
- return 1;
- }
-
- return 0;
-}
-
static int set_block_dominated_first_access(ir_node *blk, int vnum, unsigned int access) {
ir_node *idom, *succ;
vnum = GET_ENT_VNUM(value_leaves->ent);
if((get_Block_n_cfgpreds(irn) > 1) && (val_arr[vnum].access_type > 3))
- env->changes = set_block_dominated_first_access(irn, vnum, val_arr[vnum].access_type);
+ env->changes = set_block_dominated_first_access(irn, vnum, val_arr[vnum].access_type);
if((val_arr_pred[vnum].access_type > 3) && (val_arr[vnum].access_type < 3)) {
/* We have found a block for update it access and value number information.*/
remove_critical_cf_edges(irg);
/* Call algorithm that computes the out edges.*/
- if (get_irg_outs_state(irg) != outs_consistent)
- compute_irg_outs(irg);
+ assure_irg_outs(irg);
/* Call algorithm that computes the loop information.*/
- compute_loop_info(irg);
+ construct_cf_backedges(irg);
+
/* Call algorithm that computes the dominance information.*/
- compute_doms(irg);
+ assure_doms(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;
}
}
- if(get_firm_verbosity())
- printf("vnumber in data flow= %i\n", vnum);
-
/* Allocate value number for the globule memory edge.
* and a value number for the value numbers state.*/
vnum = vnum + 2;