/*
* Project: libFIRM
- * File name: ir/opt/scalar_replace.c
+ * File name: ir/opt/data_flow_scalar_replace.c
* Purpose: scalar replacement of arrays and compounds
* Author: Beyhan Veliev
* Modified by: Michael Beck
#include "ircons_t.h"
#include "hashptr.h"
#include "irgwalk.h"
-#include "irgmod.h"
#include "irnode_t.h"
#include "irtools.h"
#include "irdump.h"
#include "irloop.h"
#include "analyze_irg_args.h"
#include "irprintf.h"
+#include "compute_loop_info.h"
+#include "irgopt.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))
#define SET_IRN_VNUM(irn, vnum) set_irn_link(irn, INT_TO_PTR(vnum))
#define GET_IRN_VNUM(irn) (unsigned)PTR_TO_INT(get_irn_link(irn))
+#define SYNCED 8
-/* To save for an entity all leaves for that the memory
- * edge was split.*/
typedef struct _ent_leaves_t{
- entity *ent;
- pset *leaves;
+ 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;
- entity *ent;
+ ir_node *sel; /**< A sel node, thats entity have scalars.*/
+ entity *ent; /**< The entity of this sel node.*/
}sels_t;
typedef struct _call_access_t {
- ir_node *call;
- unsigned int access_type;
+ ir_node *call; /**< A call node, that have as parameter a scalar.*/
+ unsigned int access_type; /**< The access type, with that this call access this scalar.*/
}call_access_t;
typedef struct _fixlist_entry_t {
- ir_node *irn;
- unsigned int vnum;
+ ir_node *irn; /**< An ir node, that must be fixed.*/
+ unsigned int vnum; /**< The value number, that must became this ir node.*/
}fixlist_entry_t;
typedef struct _syncs_fixlist_entry_t {
- ir_node *irn;
- int *accessed_vnum;
+ ir_node *irn; /**< A sync node that must be fixed.*/
+ int *accessed_vnum; /**< A pointer to save an array with value numbers, that must became this sync.*/
}syncs_fixlist_entry_t;
/* A entry, that save the memory
* edge state and the access state for this leave
* int the array,that is created for every block.*/
typedef struct _leave_t {
- ir_node *mem_edge_state; /**< memory state for this scalar.*/
- unsigned int access_type; /**< access state for this scalar.*/
- set *calls; /**< call nodes,that change this scalar.*/
+ ir_node *mem_edge_state; /**< memory state for this scalar in this block.*/
+ unsigned int access_type; /**< access state for this scalar in this block.*/
+ set *calls; /**< call nodes,that change this scalar in this block.*/
}value_arr_entry_t;
-/**
- * environment for memory walker
- */
-typedef struct _env_t {
- struct obstack obst; /**< a obstack for the memory edge */
- set *set_sels; /**< a set with all sels, that are reachable from an entity with a scalar.*/
- set *set_ent; /**< a set with all entities that have one or more scalars.*/
- fixlist_entry_t *fix_phis; /**< list of all Phi nodes that must be fixed */
- fixlist_entry_t *fix_ls; /**< list of all Load or Store nodes that must be fixed */
- syncs_fixlist_entry_t *fix_syncs; /**< list of all Sync nodes that must be fixed */
- unsigned int nvals; /**< to save the number of scalars.*/
- unsigned int gl_mem_vnum; /**< indicate the position of the globule memory edge state in var_arr.*/
- unsigned int vnum_state; /**< indicate the position of the value number state in var_arr.*/
- unsigned int changes; /**< to save if by anlyse_calls is changed anything.*/
-} env_t;
-
/**
* A path element entry: it is either an entity
* or a tarval, because we evaluate only constant array
path_elem_t path[1]; /**< the path */
} path_t;
-/* we need a special address that serves as an address stored. */
-static char _s;
-static void *ADDRESS_STORED = &_s;
+/**
+ * environment for memory walker
+ */
+typedef struct _env_t {
+ struct obstack obst; /**< a obstack for the memory edge */
+ set *set_sels; /**< a set with all sels, that are reachable from an entity with a scalar.*/
+ set *set_ent; /**< a set with all entities that have one or more scalars.*/
+ fixlist_entry_t *fix_phis; /**< list of all Phi nodes that must be fixed */
+ fixlist_entry_t *fix_ls; /**< list of all Load or Store nodes that must be fixed */
+ syncs_fixlist_entry_t *fix_syncs; /**< list of all Sync nodes that must be fixed */
+ unsigned int nvals; /**< to save the number of scalars.*/
+ unsigned int gl_mem_vnum; /**< indicate the position of the globule memory edge state in var_arr.*/
+ unsigned int vnum_state; /**< indicate the position of the value number state in var_arr.*/
+ unsigned int changes; /**< to save if by anlyse_calls is changed anything.*/
+} env_t;
+
/**
*
* @return 0 if they are identically
*/
-static int ent_cmp(const void *elt, const void *key, size_t size)
+static int ent_cmp(const void *elt, const void *key)
{
const entity *c1 = elt;
const entity *c2 = key;
*
* @return 0 if they are identically
*/
-static int leave_cmp(const void *elt, const void *key, size_t size)
+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 != c2;
+ return get_Sel_entity(c1) != get_Sel_entity(c2);
}
/**
return 1;
}
-/*
+/**
* Returns non-zero, if the address of an entity
* represented by a Sel node (or it's successor Sels) is taken.
*/
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 */
for (i = 0; i < n; ++i) {
ir_node *index = get_Sel_index(sel, i);
- res->path[pos++].tv = get_Const_tarval(index);
+ if(get_irn_op(index) == op_Const)
+ res->path[pos++].tv = get_Const_tarval(index);
}
return res;
}
if(! is_leave_sel(sel))
continue;
-
/* We have found a leave and we add it to the pset of this entity.*/
- pset_insert_ptr(leaves, sel);
+ pset_insert(leaves, sel, HASH_PTR(get_Sel_entity(sel)));
key = find_path(sel, 0);
path = set_find(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
set_entity_link(ent, NULL);
return vnum;
}
-/* Analyze if this scalar was stored in this block
- or earlier.*/
-static int is_scalar_stored(ir_node *call_blk, int ent_vnum) {
+/**
+ * Add a sync node to it fix list.
+ *
+ * @param sync The sync node, that myst be addet to the fix list.
+ * @param unk_vnum An array whit the value number, that are synced with this sync node.
+ * @param env The enviroment pinter.
+ */
+static void add_sync_to_fixlist(ir_node *sync, int *unk_vnum, env_t *env) {
- value_arr_entry_t *val_arr, *val_arr_pred;
- ir_node *pred;
- int n;
+ syncs_fixlist_entry_t *s;
+
+ s = obstack_alloc(&env->obst, sizeof(*s));
+ s->irn = sync;
+ s->accessed_vnum = unk_vnum;
+ set_irn_link(sync, env->fix_syncs);
+ env->fix_syncs = s;
+}
+/**
+ * Add a ir node to it fix list.
+ *
+ * @param irn The ir node, that myst be addet to the fix list.
+ * @param vnum The value number, that must baceme this ir node as predecessor later.
+ * @param env The enviroment pinter.
+ */
+static void add_ls_to_fixlist(ir_node *irn, int vnum, env_t *env) {
- val_arr = get_irn_link(call_blk);
+ fixlist_entry_t *l;
- if(val_arr[ent_vnum].access_type == 0)
- return 0;
+ l = obstack_alloc(&env->obst, sizeof(*l));
+ l->irn = irn;
+ l->vnum = vnum;
- n = get_Block_n_cfgpreds(call_blk) - 1;
+ if(get_irn_op(irn) == op_Phi) {
+ set_irn_link(l->irn, env->fix_phis);
+ env->fix_phis = l;
+ }else {
+ set_irn_link(l->irn, env->fix_ls);
+ env->fix_ls = l;
+ }
+}
- for( ; n >= 0; n--) {
- pred = get_Block_cfgpred(call_blk, n);
- pred = get_nodes_block(pred);
- val_arr_pred = get_irn_link(pred);
+static void add_mem_edge(value_arr_entry_t *val_arr, int vnum, ir_node ***in, int **accessed_vnum) {
- if(val_arr_pred[ent_vnum].access_type != 0)
- /* This scalar wasn't stored in this block.*/
- return 1;
+ if(val_arr[vnum].mem_edge_state != NULL)
+ ARR_APP1(ir_node *, *in, val_arr[vnum].mem_edge_state);
+ else {
+ ARR_APP1(int, *accessed_vnum, vnum);
+ ARR_APP1(ir_node *, *in, new_Unknown(mode_M));
}
- return 0;
}
+/**
+ * The function handles the scalars, that wase stored
+ * in this block.
+ *
+ * @param blk The block, that must be handled.
+ * @param env The enviroment pinter.
+ */
+/* Return the memory successor of the call node.*/
+static ir_node *get_Call_mem_out(ir_node *call) {
-/* The function handles the call nodes, that have
- * as parameter a scalar*/
-static void handle_call(env_t *env, ir_node *call, pset *accessed_entities) {
+ int i;
+ ir_node *mem;
- ent_leaves_t key_ent, *value_ent;
- value_arr_entry_t *val_arr;
- call_access_t key_call, *value_call;
- ir_node *call_blk, *new_mem_state, *leave;
- ir_node *sync, **in;
- entity *ent;
- fixlist_entry_t *l;
- syncs_fixlist_entry_t *s;
- int fix_irn = 0, *accessed_leaves_vnum = NULL;
- unsigned ent_vnum;
+ for(i = get_irn_n_outs(call) - 1; i >= 0; i--) {
+ mem = get_irn_out(call, i);
+ if(get_irn_mode(mem) == mode_M)
+ return mem;
+ }
+ /* is not reachable*/
+ return NULL;
+}
+
+
+static void sync_stored_scalars(ir_node *blk, env_t *env) {
+
+ int i;
+ int *unk_vnum; /**< An arraw, where are saved the value number, that
+ are synced from this sync node.*/
+ ent_leaves_t *value_ent;
+ value_arr_entry_t *val_arr_blk, *val_arr;
+ ir_node *pred, *leave, *sync, **in;
+ ir_node *sync_blk; /**< The block, where the sync node must be created.*/
+
+
+ val_arr_blk = get_irn_link(blk);
+
+ for(value_ent = set_first(env->set_ent); value_ent; value_ent = set_next(env->set_ent)) {
+
+
+ if(val_arr_blk[GET_ENT_VNUM(value_ent->ent)].access_type <= 3)
+ /* This entity is not stored in this block.*/
+ continue;
+
+ for(i = get_Block_n_cfgpreds(blk) - 1; i >= 0; i--) {
+
+ pred = get_Block_cfgpred(blk, i);
+ pred = get_nodes_block(pred);
+ val_arr = get_irn_link(pred);
+
+ if(val_arr[GET_ENT_VNUM(value_ent->ent)].access_type == SYNCED)
+ /* 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;
+ /* 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)
+ sync_blk = get_nodes_block(get_Block_cfgpred(blk, i));
+ else
+ sync_blk = blk;
+
+ val_arr = get_irn_link(sync_blk);
+ /* An array to save the memory edges, that must be
+ * synced.*/
+ in = NEW_ARR_F(ir_node *, 1);
+
+ /* An array to save the value numbers,
+ * that must be repaired.*/
+ unk_vnum = NEW_ARR_F(int, 0);
+ /* The global memory edge.*/
+ if(val_arr[env->gl_mem_vnum].mem_edge_state == NULL)
+ in[0] = new_Unknown(mode_M);
+ else
+ in[0] = val_arr[env->gl_mem_vnum].mem_edge_state;
+
+ for(leave = pset_first(value_ent->leaves); leave; leave = pset_next(value_ent->leaves))
+ /* All this memory edges must be synced.*/
+ add_mem_edge(val_arr, GET_IRN_VNUM(leave), &in, &unk_vnum);
+
+ /* We create the sync and set it in the global memory state.*/
+ sync = new_r_Sync(current_ir_graph, sync_blk, ARR_LEN(in), in);
+ /* 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) {
+ 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);
+ }
+ DEL_ARR_F(in);
+ }
+ }
+ }
+}
+/**
+ * The function split the memory edge of load and store nodes, that have
+ * as predecessor a scalar
+ *
+ * @param irn The node, that memory edge must be spleted.
+ * @param env The enviroment pinter.
+ */
+static void split_ls_mem_edge(ir_node *irn, env_t *env) {
+
+ ir_op *op;
+ ir_node *leave, *irn_blk, *mem_state, *new_mem_state;
+ unsigned ent_vnum, sel_vnum, i;
+ value_arr_entry_t *val_arr;
+ sels_t key_sels, *value_sels;
+ ent_leaves_t key_ent, *value_ent;
+
+ op = get_irn_op(irn);
+
+ if(op == op_Load)
+ key_sels.sel = get_Load_ptr(irn);
+ else
+ key_sels.sel = get_Store_ptr(irn);
+
+ value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
+
+ if(value_sels != NULL) {
+ /* we have found a load or store, that use a sel of our set
+ * and we must split or extend, if the memory edge have been
+ * split for this sel, the memory edge.*/
+
+ key_ent.ent = value_sels->ent;
+ value_ent = set_find(env->set_ent, &key_ent, sizeof(key_ent), HASH_PTR(key_ent.ent));
+ /*To check if the enities set is right filled. */
+ assert(value_ent && " This sel's entity isn't int the entity set.");
+
+ leave = pset_find(value_ent->leaves, key_sels.sel, HASH_PTR(get_Sel_entity(key_sels.sel)));
+ /*To check if the leaves set is right filled. */
+ assert(leave && "Anything in data_flow_scalar_replacment algorithm is wrong.");
+
+ ent_vnum = GET_ENT_VNUM(value_ent->ent);
+ sel_vnum = GET_IRN_VNUM(leave);
+ irn_blk = get_nodes_block(irn);
+ val_arr = get_irn_link(irn_blk);
+
+ if(val_arr[ent_vnum].access_type == 0)
+ /* We have found a scalar, that address is not stored as jet.*/
+ i = sel_vnum;
+ else
+ /* This scalar have been stored.*/
+ i = env->gl_mem_vnum;
+
+ if(val_arr[i].mem_edge_state == NULL) {
+ /* We split now for this sel the memory edge in this block.*/
+ mem_state = new_Unknown(mode_M);
+ /* We must mark this node to fix later*/
+ add_ls_to_fixlist(irn, i, env);
+ }
+ else
+ /* We have split the memory edge and the current state is saved.*/
+ mem_state = val_arr[i].mem_edge_state;
+
+ /* We set this Load or Store to the memory edge of this
+ * sel.*/
+ if(op == op_Load)
+ set_Load_mem(irn, mem_state);
+ else
+ set_Store_mem(irn, mem_state);
+
+ /* When we have split or extended the memory edge we must
+ * update the memory_edge_state of this sel*/
+ new_mem_state = get_irn_out(irn, 0);
+ if(get_irn_mode(new_mem_state) == mode_M)
+ val_arr[i].mem_edge_state = new_mem_state;
+ else
+ val_arr[i].mem_edge_state = get_irn_out(irn, 1);
+ }
+}
+
+/**
+ * The function split the memory edge of phi nodes, that have
+ * as predecessor a scalar
+ *
+ * @param irn The phi node, that memory edge must be spleted.
+ * @param env The enviroment pinter.
+ */
+static void split_phi_mem_edge(ir_node *irn, env_t *env) {
+
+ ir_node *irn_blk, *unk, *leave, **in;
+ int n, j;
+ ent_leaves_t *value_ent;
+ value_arr_entry_t *val_arr;
+
+ irn_blk = get_nodes_block(irn);
+ val_arr = get_irn_link(irn_blk);
+
+ n = get_Block_n_cfgpreds(irn_blk);
+
+ in = alloca(sizeof(*in) * n);
+
+ for(value_ent = set_first(env->set_ent); value_ent; value_ent = set_next(env->set_ent))
+ if(val_arr[GET_ENT_VNUM(value_ent->ent)].access_type < 3)
+ /* This scalar wasn't be saved and we need to produce a phi for it.*/
+ for(leave = pset_first(value_ent->leaves); leave; leave = pset_next(value_ent->leaves)){
+
+ unk = new_Unknown(mode_M);
+ for (j = n - 1; j >= 0; --j)
+ in[j] = unk;
+
+ val_arr[GET_IRN_VNUM(leave)].mem_edge_state = new_r_Phi(current_ir_graph, irn_blk, n, in, mode_M);
+
+ add_ls_to_fixlist(val_arr[GET_IRN_VNUM(leave)].mem_edge_state, GET_IRN_VNUM(leave), env);
+ }
+
+ /* We use for the global memory the phi node, that
+ * is already available.*/
+ val_arr[env->gl_mem_vnum].mem_edge_state = irn;
+}
+
+/**
+ * The function handles the call nodes, that have
+ * as parameter a scalar
+ *
+ * @param env The enviroment pinter.
+ * @param call The call node, that must be handled.
+ * @param accessed_entities A set wit all entities, that are accessed from this call node.*/
+static void split_call_mem_edge(env_t *env, ir_node *call, pset *accessed_entities) {
+
+ ent_leaves_t key_ent, *value_ent;
+ value_arr_entry_t *val_arr;
+ call_access_t key_call, *value_call;
+ ir_node *call_blk, *new_mem_state, *leave;
+ ir_node *sync, **in;
+ 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);
- /* To save the memory edges, that must be
+ /* An array to save the memory edges, that must be
* synced.*/
in = NEW_ARR_F(ir_node *, 1);
- /* To save the value numbers of the memory
+ /* An array to save the value numbers of the memory
* edges that must be repaired.*/
accessed_leaves_vnum = NEW_ARR_F(int, 0);
/* We get the memory successor of the call node.
* It is the new memory state for all synced memory
* edges.*/
- new_mem_state = get_irn_out(call, 0);
- if(get_irn_mode(new_mem_state) != mode_M)
- new_mem_state = get_irn_out(call,1);
+ new_mem_state = get_Call_mem_out(call);
+ /* The global memory is the first predecessor of the create sync node.*/
if(val_arr[env->gl_mem_vnum].mem_edge_state == NULL) {
in[0] = new_Unknown(mode_M);
fix_irn = 1;
- } else
+ }
+ else
in[0] = val_arr[env->gl_mem_vnum].mem_edge_state;
+
for(ent = pset_first(accessed_entities); ent; ent = pset_next(accessed_entities)) {
- /* Whit this loop we iterate all accessed entities an collect
+ /* Whit this loop we iterate all accessed entities from this call and collect
* all memory edges, that we must sync.*/
ent_vnum = GET_ENT_VNUM(ent);
key_call.call = call;
- value_call = set_find(val_arr[ent_vnum].calls, &key_call, sizeof(key_call), HASH_PTR(key_call.call));
+ value_call = set_find(val_arr[ent_vnum].calls, &key_call, sizeof(key_call), HASH_PTR(key_call.call));
- key_ent.ent = ent;
- value_ent = set_find(env->set_ent, &key_ent, sizeof(key_ent), HASH_PTR(key_ent.ent));
+ key_ent.ent = ent;
+ value_ent = set_find(env->set_ent, &key_ent, sizeof(key_ent), HASH_PTR(key_ent.ent));
- if(!is_scalar_stored(call_blk, ent_vnum)) {
+ if(val_arr[ent_vnum].access_type <= 3) {
/* This scalar's address wasn't stored in this block.*/
switch(value_call->access_type) {
case ptr_access_read:
case ptr_access_write:
case ptr_access_rw:
- case 5:
- case ptr_access_all:
/* All this cases must be traded equal.*/
for(leave = pset_first(value_ent->leaves); leave; leave = pset_next(value_ent->leaves)){
/* All this memory edges must be synced.*/
- if(val_arr[GET_IRN_VNUM(leave)].mem_edge_state != NULL)
- ARR_APP1(ir_node *, in, val_arr[GET_IRN_VNUM(leave)].mem_edge_state);
- else {
- ARR_APP1(int, accessed_leaves_vnum, GET_IRN_VNUM(leave));
- ARR_APP1(ir_node *, in, new_Unknown(mode_M));
- fix_irn = 1;
- }
+ add_mem_edge(val_arr, GET_IRN_VNUM(leave), &in, &accessed_leaves_vnum);
+
/* We update the memory state of this leave.*/
if(value_call->access_type != ptr_access_read)
- val_arr[GET_IRN_VNUM(leave)].mem_edge_state = new_mem_state;
+ val_arr[GET_IRN_VNUM(leave)].mem_edge_state = new_mem_state;
}
/* We are ready.*/
/* we must set the call memory to gobale momory*/
set_Call_mem(call,in[0]);
- if(fix_irn) {
+ if(fix_irn)
/* We add this call node to the call fix list..*/
- l = obstack_alloc(&env->obst, sizeof(*l));
- l->irn = call;
- l->vnum = env->gl_mem_vnum;
- set_irn_link(l->irn, env->fix_ls);
- env->fix_ls = l;
- }
+ add_ls_to_fixlist(call, env->gl_mem_vnum, env);
+
} else {
/* We create the sync and set it as memory predecessor of the call node.*/
sync = new_r_Sync(current_ir_graph, call_blk, ARR_LEN(in), in);
- set_Call_mem(call, sync);
-
- if(fix_irn) {
- /* We add this sync node to the sync's fix list.*/
- s = obstack_alloc(&env->obst, sizeof(*s));
- s->irn = sync;
- s->accessed_vnum = accessed_leaves_vnum;
- set_irn_link(sync, env->fix_syncs);
- env->fix_syncs = s;
+ /* 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) {
+
+ set_Call_mem(call, sync);
+ if(ARR_LEN(accessed_leaves_vnum))
+ /* We add this sync node to the sync's fix list.*/
+ add_sync_to_fixlist(sync, accessed_leaves_vnum, env);
}
}
DEL_ARR_F(in);
}
-/* The function split the memory edge.*/
+/**
+ * The function split the memory edge from the passed
+ * ir node if this is needed
+ *
+ * @param irn The node, that memory edge must be spleted.
+ * @param env The enviroment pinter.
+ */
static void split_memory_edge(ir_node *irn, void *ctx) {
- env_t *env = ctx;
- ir_node *new_mem_state, *mem_state, *unk;
- ir_node *leave, *sel, *irn_blk, **in;
- ir_op *op;
- sels_t key_sels, *value_sels;
- ent_leaves_t key_ent, *value_ent;
- value_arr_entry_t *val_arr;
- fixlist_entry_t *l;
- pset *accessed_entities;
- unsigned ent_vnum, sel_vnum;
- int i, j, n;
+ env_t *env = ctx;
+ ir_node *sel, *irn_blk;
+ ir_op *op;
+ sels_t key_sels, *value_sels;
+ value_arr_entry_t *val_arr;
+ pset *accessed_entities; /**< A set to save all entities accessed from a call.*/
+ int i;
op = get_irn_op(irn);
- if(op == op_Load || op == op_Store) {
-
- if(op == op_Load)
- key_sels.sel = get_Load_ptr(irn);
- else
- key_sels.sel = get_Store_ptr(irn);
-
- value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
-
- if(value_sels != NULL) {
- /* we have found a load or store, that use a sel of our set
- * and we must split or extend, if the memory edge have been
- * split for this sel, the memory edge.*/
+ if(op == op_Block)
+ irn_blk = irn;
+ else
+ irn_blk = get_nodes_block(irn);
- key_ent.ent = value_sels->ent;
- value_ent = set_find(env->set_ent, &key_ent, sizeof(key_ent), HASH_PTR(key_ent.ent));
- assert(value_ent && " This sel's entity isn't int the entity set.");
-
- leave = pset_find_ptr(value_ent->leaves, key_sels.sel);
-
- assert(leave && "Anything in data_flow_scalar_replacment algorithm is wrong.");
-
- ent_vnum = GET_ENT_VNUM(value_ent->ent);
- sel_vnum = GET_IRN_VNUM(leave);
-
- irn_blk = get_nodes_block(irn);
- val_arr = get_irn_link(irn_blk);
-
- if(val_arr[ent_vnum].access_type == 0)
- /* We have found a scalar, that address i not stored as jet.*/
- i = sel_vnum;
- else
- /* This scalar have been stored.*/
- i = env->gl_mem_vnum;
+ if (Block_not_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);
+ }
- if(val_arr[i].mem_edge_state == NULL) {
- /* We split now for this sel the memory edge in this block.*/
- mem_state = new_Unknown(mode_M);
- /* We must mark this node to fix later*/
- l = obstack_alloc(&env->obst, sizeof(*l));
- l->irn = irn;
- l->vnum = i;
+ if(op == op_Load || op == op_Store)
- set_irn_link(irn, env->fix_ls);
- env->fix_ls = l;
- }else
- /* We have split the memory edge and the current state is saved.*/
- mem_state = val_arr[i].mem_edge_state;
+ split_ls_mem_edge(irn, env);
- /* We set this Load or Store to the memory edge of this
- * sel.*/
- if(op == op_Load)
- set_Load_mem(irn, mem_state);
- else
- set_Store_mem(irn, mem_state);
-
- /* When we have split or extended the memory edge we must
- * update the memory_edge_state of this sel*/
- new_mem_state = get_irn_out(irn, 0);
- if(get_irn_mode(new_mem_state) == mode_M)
- val_arr[i].mem_edge_state = new_mem_state;
- else
- val_arr[i].mem_edge_state = get_irn_out(irn, 1);
- }
- }
- else
+ else {
if (op == op_Phi && get_irn_mode(irn) == mode_M) {
/*
* found a memory Phi: Here, we must create new Phi nodes
*/
- irn_blk = get_nodes_block(irn);
- val_arr = get_irn_link(irn_blk);
-
- n = get_Block_n_cfgpreds(irn_blk);
-
- in = alloca(sizeof(*in) * n);
-
- for (i = val_arr[env->gl_mem_vnum].access_type - 1; i >= 0; --i) {
- unk = new_Unknown(mode_M);
- for (j = n - 1; j >= 0; --j)
- in[j] = unk;
-
- val_arr[i].mem_edge_state = new_r_Phi(current_ir_graph, irn_blk, n, in, mode_M);
+ split_phi_mem_edge(irn, env);
+ }
+ else {
+ if(op == op_Call) {
+
+ /* 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)
+ return;
+
+ /* We save in this set all entities,
+ * that are accessed from this call node.*/
+ accessed_entities = new_pset(ent_cmp, 8);
+ val_arr = get_irn_link(get_nodes_block(irn));
+
+ for ( i = get_Call_n_params(irn) - 1; i >= 0; i--) {
+
+ sel = get_Call_param(irn, i);
+ value_sels = NULL;
+ if(get_irn_op(sel) == op_Sel) {
+ key_sels.sel = sel;
+ value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
+
+ if(value_sels != NULL && val_arr[GET_ENT_VNUM(value_sels->ent)].access_type <= 3)
+ /* We save in this set all accessed entities from this call node whit
+ * access none, read, write or rw..*/
+ pset_insert(accessed_entities, value_sels->ent, HASH_PTR(value_sels->ent));
+ }
+ }
- l = obstack_alloc(&env->obst, sizeof(*l));
- l->irn = val_arr[i].mem_edge_state;
- l->vnum = i;
+ if(pset_count(accessed_entities))
+ split_call_mem_edge(env, irn, accessed_entities);
- set_irn_link(val_arr[i].mem_edge_state, env->fix_phis);
- env->fix_phis = l;
- }
- }
- if(op == op_Call) {
- /* We save in this set all entities,
- * that are accessed from this call node.*/
- accessed_entities = new_pset(ent_cmp, 8);
-
- for ( i = get_Call_n_params(irn) - 1; i >= 0; i--) {
- sel = get_Call_param(irn, i);
- if(get_irn_op(sel) == op_Sel) {
- key_sels.sel = sel;
- value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
- }
-
- if(value_sels != NULL)
- /* We save in this set all accessed entities from this call node.*/
- pset_insert(accessed_entities, value_sels->ent, HASH_PTR(value_sels->ent));
+ del_pset(accessed_entities);
+ }
}
- if(pset_count(accessed_entities))
- handle_call(env, irn, accessed_entities);
- }
+ }
}
/**
* searches through blocks beginning from block for value
* vnum and return it.
+ *
+ * @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;
+ int i;
+ ir_node *res;
if (Block_not_block_visited(block)) {
mark_Block_block_visited(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;
}
/**
* fix the Load/Store or Call list
+ *
+ * @param The enviroment pinter.
*/
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(op == op_Store)
- set_Store_mem(irn, val);
- else
- if(op == op_Load)
- set_Load_mem(irn, val);
+ if(val) {
+ if(op == op_Store)
+ set_Store_mem(irn, val);
else
- set_Call_mem(irn, val);
+ if(op == op_Load)
+ set_Load_mem(irn, val);
+ else
+ set_Call_mem(irn, val);
+ }
}
}
/**
* fix the Phi list
+ *
+ * @param The enviroment pinter.
*/
static void fix_phis(env_t *env)
{
fixlist_entry_t *l;
- ir_node *phi, *block, *pred, *val;
- int i;
+ ir_node *phi, *block, *pred, *val;
+ int i;
for (l = env->fix_phis; l; l = get_irn_link(phi)) {
phi = l->irn;
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);
/**
* fix the Sync list
+ *
+ * @param The enviroment pinter.
*/
static void fix_syncs(env_t *env)
{
syncs_fixlist_entry_t *l;
- ir_node *sync, *block, *pred, *val;
- int i, k = 0;
+ ir_node *sync, *block, *pred, *val;
+ int i, k;
for (l = env->fix_syncs; l; l = get_irn_link(sync)) {
sync = l->irn;
+ k = 0;
/* The sync block must have one predecessor, when it
have unknown nodes as predecessor.*/
/* 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) {
inc_irg_block_visited(current_ir_graph);
- val = find_value(pred, env->gl_mem_vnum);
- set_irn_n(sync, 0, val);
+ val = find_vnum_value(pred, env->gl_mem_vnum);
+
+ if(val)
+ set_irn_n(sync, 0, val);
}
- for (i = get_irn_arity(sync) - 1; i >= 0; --i) {
+ for (i = get_irn_arity(sync) - 1; i >= 1; --i) {
/* 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) {
inc_irg_block_visited(current_ir_graph);
- val = find_value(pred, l->accessed_vnum[k++]);
- set_irn_n(sync, i, val);
+ val = find_vnum_value(pred, l->accessed_vnum[k++]);
+
+ if(val)
+ set_irn_n(sync, i, val);
}
}
+ DEL_ARR_F(l->accessed_vnum);
}
}
-/* For the end node we must sync all memory edges.*/
+/**
+ * For the end node we must sync all memory edges.
+ *
+ * @param The enviroment pinter.
+ */
static void sync_mem_edges(env_t *env) {
- ent_leaves_t *entry_ent;
- ir_node *leave;
value_arr_entry_t *val_arr;
- ir_node **in, *sync, *Return, *Return_blk;
- int i = 1;
+ ir_node **in, *sync, *Return, *Return_blk;
+ int i, vnum, vnum_state;
Return = get_Block_cfgpred(get_irg_end_block(current_ir_graph), 0);
Return_blk = get_nodes_block(Return);
val_arr = get_irn_link(Return_blk);
- /* We allocate the memory, that we need for the successors of the sync.*/
- in = malloc(sizeof(ir_node*) *val_arr[env->vnum_state].access_type);
+
+ vnum_state = 0;
+
+ for(i = 0; i <= (int)env->gl_mem_vnum; i++)
+ /* we get the current state of non saved scalars.*/
+ if(val_arr[i].access_type <= 3)
+ vnum_state++;
+
+ /* We allocate the memory, that we need for the predecessors of the sync.*/
+ in = xmalloc(sizeof(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;
- for(entry_ent = set_first(env->set_ent); entry_ent; entry_ent = set_next(env->set_ent)) {
- if(val_arr[GET_ENT_VNUM(entry_ent->ent)].access_type ==0)
- /* The address of this entity was not stored. We must sync the memory edges of it's scalars.*/
- for(leave = pset_first(entry_ent->leaves); leave; leave = pset_next(entry_ent->leaves)) {
- if(val_arr[GET_IRN_VNUM(leave)].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, GET_IRN_VNUM(leave));
- }
- else
- in[i] = val_arr[GET_IRN_VNUM(leave)].mem_edge_state;
- i++;
+ for(i = 1, vnum = 0; vnum < (int)env->gl_mem_vnum; vnum++) {
+
+ if(val_arr[vnum].access_type <= 3) {
+ /* we add the non saved scalars as predecessors of the sync.*/
+
+ 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_vnum_value(Return_blk, vnum);
+ }
+ else
+ in[i] = val_arr[vnum].mem_edge_state;
+ i++;
}
}
- //assert(i < env->nvals && "Our nvals algorithm is baggy." );
-
- sync = new_r_Sync(current_ir_graph, Return_blk, val_arr[env->vnum_state].access_type, in);
+ sync = new_r_Sync(current_ir_graph, Return_blk, vnum_state, in);
set_Return_mem(Return, sync);
free(in);
/**
* Walker: allocate the value array for every block.
+ *
+ * @param block A block from the current ir graph for that must be allocated a value array.
+ * @param ctx The enviroment pinter.
*/
static void alloc_value_arr(ir_node *block, void *ctx)
{
env_t *env = ctx;
- int i;
+ int i;
+
value_arr_entry_t *var_arr = obstack_alloc(&env->obst, sizeof(value_arr_entry_t) *(env->nvals + set_count(env->set_ent) + 1));
/* the value array is empty at start */
memset(var_arr, 0, sizeof(value_arr_entry_t) * (env->nvals + set_count(env->set_ent) + 1));
set_irn_link(block, var_arr);
+
/* We set the block value number state to optimal and later we update this.*/
var_arr[env->vnum_state].access_type = env->nvals;
if(get_irg_start_block(current_ir_graph) == block)
+ /* We initilize the startblocks array with the irg initilize memory, why
+ * it must be the start point of all memory edges.*/
for(i = (env->nvals + set_count(env->set_ent)) ; i >=0; i--)
var_arr[i].mem_edge_state = get_irg_initial_mem(current_ir_graph);
}
-/* Analyze call nodes to get information, if they store the address of a scalar. */
+/* Analyze call nodes to get information, if they store the address of a scalar.
+ *
+ * @param *irn An ir node from the current_ir_graph.
+ * @param *env The enviroment pointer.
+*/
static void analyse_calls(ir_node *irn, void *ctx) {
- int i, vnum;
- unsigned int acces_type;
- env_t *env = ctx;
- ir_node *param, *call_ptr, *blk;
- ir_op *op;
- entity *meth_ent;
- sels_t key_sels, *value_sels;
- call_access_t key_call, *value_call;
- value_arr_entry_t *val_arr;
- ent_leaves_t key_ent, *value_ent;
-
+ int i, vnum;
+ unsigned int acces_type;
+ ir_node *param, *call_ptr, *blk;
+ ir_op *op;
+ 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)
return;
- for ( i = get_Call_n_params(irn) - 1; i >= 0; i--) {
- param = get_Call_param(irn, i);
- if(get_irn_op(param) == op_Sel) {
-
- key_sels.sel = param;
- value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
- if(value_sels != NULL ) {
- /* 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)
- meth_ent = get_SymConst_entity(call_ptr);
- else
- continue;
- /* we get the access type for our sel.*/
- acces_type = get_method_param_access(meth_ent, i);
- /* we save the access type and this call in the array allocated for this block.
- * The value number of this entity get us the position in the array to save this
- * information. Why we expect more calls as one we allocate a set.*/
- vnum = GET_ENT_VNUM(value_sels->ent);
- blk = get_nodes_block(irn);
- val_arr = get_irn_link(blk);
-
- if(val_arr[vnum].access_type > 3)
- /* The address of this entity have been stored.*/
- continue;
-
- if(val_arr[vnum].calls == NULL)
- /* for this entity i have found the firs call in this block and we must allocate the set.*/
- val_arr[vnum].calls = new_set(call_cmp, 8);
-
- /* This call performs anything with the scalar and we must mark it.*/
- key_call.call = irn;
- key_call.access_type = acces_type;
- value_call = set_insert(val_arr[vnum].calls, &key_call, sizeof(key_call), HASH_PTR(key_call.call));
-
- if(value_call->access_type < acces_type)
- /* this case tread, when a call access an entity more at once.
- * Than we must save the highest access type.*/
- value_call->access_type = acces_type;
-
- if(acces_type > 3) {
- /* This call save the address of our scalar and we can't
- * use the scalars of this entity for optimization as from now.
- * we mark this.*/
- val_arr[vnum].access_type = acces_type;
- /* We must update our scalars number.*/
- key_ent.ent = value_sels->ent;
- value_ent = set_find(env->set_ent, &key_ent, sizeof(key_ent), HASH_PTR(key_ent.ent));
- val_arr[env->vnum_state].access_type -= pset_count(value_ent->leaves);
- }
- }
- }
+ /* 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)
+ 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) {
+ /* 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));
+ if(value_sels != NULL ) {
+
+ /* 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) {
+ meth_ent = get_SymConst_entity(call_ptr);
+ /* we get the access type for our sel.*/
+ acces_type = get_method_param_access(meth_ent, i);
+ } else
+ /* We can't analyze this function and we asume, that it store the address.*/
+ acces_type = ptr_access_store;
+
+ /* we save the access type and this call in the array allocated for this block.
+ * The value number of this entity get us the position in the array to save this
+ * information. Why we expect more calls as one we allocate a set.*/
+ vnum = GET_ENT_VNUM(value_sels->ent);
+ blk = get_nodes_block(irn);
+ val_arr = get_irn_link(blk);
+
+ if(val_arr[vnum].access_type > 3)
+ /* The address of this entity have been stored.*/
+ continue;
+
+ if(val_arr[vnum].calls == NULL)
+ /* for this entity i have found the firs call in this block and we must allocate the set.*/
+ val_arr[vnum].calls = new_set(call_cmp, 8);
+
+ /* This call performs anything with the scalar and we must mark it.*/
+ key_call.call = irn;
+ key_call.access_type = acces_type;
+ value_call = set_insert(val_arr[vnum].calls, &key_call, sizeof(key_call), HASH_PTR(key_call.call));
+
+ if(value_call->access_type < acces_type)
+ /* this case tread, when a call access an entity more at once.
+ * Than we must save the highest access type.*/
+ value_call->access_type = acces_type;
+
+ if(acces_type > 3)
+ /* This call save the address of our scalar and we can't
+ * use the scalars of this entity for optimization as from now.
+ * we mark this.*/
+ val_arr[vnum].access_type = acces_type;
+ }
+ }
+ }
+}
+
+static int set_block_dominated_first_access(ir_node *blk, int vnum, unsigned int access) {
+
+ ir_node *idom, *succ;
+ value_arr_entry_t *val_arr;
+ int i, changes = 0;
+
+ idom = get_Block_idom(blk);
+ for(i = get_Block_n_cfg_outs(idom) - 1; i >=1; i--) {
+ succ = get_Block_cfg_out(idom, i);
+ val_arr = get_irn_link(succ);
+ if(val_arr[vnum].access_type < 3) {
+ val_arr[vnum].access_type = access;
+ changes++;
}
+ }
+ return changes;
}
/* Update the access information of a block if a predecessor of
- * this black have a store access for an entity.*/
+ * this black have a higher access for an entity.
+ *
+ * @param *irn An ir node from the current_ir_graph.
+ * @param *env The enviroment pointer.
+ */
static void set_block_access(ir_node *irn, void *ctx){
value_arr_entry_t *val_arr, *val_arr_pred;
ent_leaves_t *value_leaves;
- env_t *env = ctx;
- ir_node *pred, *pred_blk;
+ ir_node *pred, *pred_blk, *leave;
+ env_t *env;
int i, vnum;
+ env = ctx;
val_arr = get_irn_link(irn);
for( i = get_Block_n_cfgpreds(irn) - 1; i >= 0; i--) {
* be updated.*/
pred = get_Block_cfgpred(irn, i);
pred_blk = get_nodes_block(pred);
+
val_arr_pred = get_irn_link(pred_blk);
for(value_leaves = set_first(env->set_ent); value_leaves; value_leaves = set_next(env->set_ent)) {
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);
+
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.*/
- val_arr[vnum].access_type = val_arr_pred[vnum].access_type;
- val_arr[env->vnum_state].access_type = val_arr_pred[env->vnum_state].access_type;
- env->changes++;
- }
+ val_arr[vnum].access_type = val_arr_pred[vnum].access_type;
+ /* We update the access information of all leave, that belong to
+ * this entity.*/
+
+ for(leave = pset_first(value_leaves->leaves); leave; leave = pset_next(value_leaves->leaves))
+ val_arr[GET_IRN_VNUM(leave)].access_type = val_arr[vnum].access_type;
+
+ /* In this way can't be got the actuall number of value numbers.
+ val_arr[env->vnum_state].access_type = val_arr_pred[env->vnum_state].access_type; */
+ env->changes++;
}
+ }
}
}
+/* Free the allocated call sets.
+ *
+ * @param irn A block form the ir graph.
+ * @param env The enviroment pinter.
+ */
+static void free_call_info(ir_node *irn, void *ctx) {
-static void print_block_state(ir_node *irn, void *ctx) {
-
- env_t *env = ctx;
+ int i;
+ env_t *env;
value_arr_entry_t *val_arr;
- ent_leaves_t *value_leaves;
- call_access_t *value_calls;
- int vnum;
+ env = ctx;
val_arr = get_irn_link(irn);
- ir_printf("\n\nThe actual value number state of this block is: %i \n", val_arr[env->vnum_state].access_type - 1);
+ for(i = env->nvals + set_count(env->set_ent); i >= 0; i--) {
+ if(val_arr[i].calls != NULL)
+
+ del_set(val_arr[i].calls);
+ }
+}
+
+static void print_block_state(ir_node *irn, void *ctx) {
+
+ value_arr_entry_t *val_arr;
+ ent_leaves_t *value_leaves;
+ call_access_t *value_calls;
+ env_t *env;
+ int vnum;
+
+ env = ctx;
+ val_arr = get_irn_link(irn);
+ ir_printf("\n\nThe actual value number state of this block is: %i \n",
+ val_arr[env->vnum_state].access_type - 1);
for(value_leaves = set_first(env->set_ent); value_leaves; value_leaves = set_next(env->set_ent)) {
+
vnum = GET_ENT_VNUM(value_leaves->ent);
- ir_printf("The entity %F access type in the block with nr %u is %i \n", value_leaves->ent, get_irn_node_nr(irn),
- val_arr[vnum].access_type);
+ ir_printf("The entity %F access type in the block with nr %u is %i \n",
+ value_leaves->ent, get_irn_node_nr(irn), val_arr[vnum].access_type);
+
if(val_arr[vnum].calls != NULL)
for(value_calls = set_first(val_arr[vnum].calls); value_calls; value_calls = set_next(val_arr[vnum].calls))
+
ir_printf("A call with nr %i acess a element of this entity with access %u \n",
get_irn_node_nr(value_calls->call), value_calls->access_type);
}
/** Optimize the found scalar replacements.
*
-* @param sels A pset with all sels nodes,
-* that belong to our scalars.
+* @param set_sels A set with all entities, that
+* have scala(s).
+* @param set_ent A set with all sels nodes,
+* that belong to our scalars.
+* @param vnum The number of scalars.
*/
static void do_data_flow_scalar_replacement(set *set_ent, set *set_sels, int vnum) {
/* first step: allocate the value arrays for every block */
irg_block_walk_graph(current_ir_graph, NULL, alloc_value_arr, &env);
- /* second step: we analyze all calls, that have as parameter scalar(s)
- * and we mark this calls. If the call save the address of a scalar we
+ /* second step: we analyze all calls, that have as parameter scalar(s).
+ * We mark the calls, that save the address of a scalar and we
* mark the entity owner of this scalar as not optimizeble by now.*/
irg_walk_graph(current_ir_graph, NULL, analyse_calls, &env);
irg_block_walk_graph(current_ir_graph, NULL, set_block_access, &env);
}
- /* Debug info to see if analyse_calls work properly.*/
- irg_block_walk_graph(current_ir_graph, NULL, print_block_state, &env);
+
+ // if(get_firm_verbosity())
+ /* Debug info to see if analyse_calls work properly.*/
+ irg_block_walk_graph(current_ir_graph, NULL, print_block_state, &env);
+
/*
* fourth step: walk over the graph blockwise in topological order
* and split the memrory edge.
*/
+ inc_irg_block_visited(current_ir_graph);
irg_walk_blkwise_graph(current_ir_graph, NULL, split_memory_edge, &env);
+
+
/* fifth step: fix all nodes, that have as predecessor Unknown.*/
fix_ls(&env);
fix_phis(&env);
fix_syncs(&env);
+ /* sixth step: sync memory enges for the end block.*/
sync_mem_edges(&env);
+
+ /*seventh step: free the allocated memory*/
+ irg_block_walk_graph(current_ir_graph, NULL, free_call_info, &env);
+ obstack_free(&env.obst, NULL);
}
/*
*
* @param irg The current ir graph.
*/
-void data_flow_scalar_replacement_opt(ir_graph *irg)
-{
+void data_flow_scalar_replacement_opt(ir_graph *irg) {
+
int i, vnum = 0;
ir_node *irg_frame;
set *set_sels;
set *set_ent;
- ir_graph *rem;
ent_leaves_t key_leaves, *value_leaves;
if (! get_opt_scalar_replacement())
return;
- rem = current_ir_graph;
set_sels = new_set(sels_cmp, 8);
set_ent = new_set(ent_leaves_t_cmp, 8);
- /* Call algorithm that computes the out edges */
+ /* Call algorithm that remove the critical edges of a ir graph. */
+ remove_critical_cf_edges(irg);
+
+ /* Call algorithm that computes the out edges.*/
if (get_irg_outs_state(irg) != outs_consistent)
compute_irg_outs(irg);
+ /* Call algorithm that computes the loop information.*/
+ compute_loop_info(irg);
+ /* Call algorithm that computes the dominance information.*/
+ compute_doms(irg);
+
/* Find possible scalar replacements */
if (find_possible_replacements(irg)) {
- if (get_opt_scalar_replacement_verbose()) {
- printf("Scalar Replacement: %s\n", get_entity_name(get_irg_entity(irg)));
- }
-
/* Insert in set the scalar replacements. */
irg_frame = get_irg_frame(irg);
vnum = allocate_value_numbers(set_sels, value_leaves->leaves, ent, vnum);
}
}
- printf("vnumber in data flow= %i\n", vnum);
+
+ 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.*/
for(i = vnum,value_leaves = set_first(set_ent); value_leaves; i++, value_leaves = set_next(set_ent))
SET_ENT_VNUM(value_leaves->ent, i);
- if (vnum) {
+ if (vnum)
do_data_flow_scalar_replacement(set_ent, set_sels, vnum);
- }
+
+ /*free the allocated memory.*/
+ for(value_leaves = set_first(set_ent); value_leaves; value_leaves = set_next(set_ent))
+ del_pset(value_leaves->leaves);
+ del_set(set_ent);
+ del_set(set_sels);
}
}
projects / libfirm / blobdiff