#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
typedef struct _ent_leaves_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;
- return get_Sel_entity(c1) != get_Sel_entity(c2);
+ return c1->attr.s.ent != c2->attr.s.ent;
}
/**
return 1;
}
-/*
+/**
* Returns non-zero, if the address of an entity
* represented by a Sel node (or it's successor Sels) is taken.
*/
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(leaves, sel, HASH_PTR(get_Sel_entity(sel)));
set_entity_link(ent, NULL);
return vnum;
}
-/* Add a sync node to it fix list.
+/**
+ * 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.
set_irn_link(sync, env->fix_syncs);
env->fix_syncs = s;
}
-/* Add a ir node to it fix list.
+/**
+ * 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.
ARR_APP1(ir_node *, *in, new_Unknown(mode_M));
}
}
-/** The function handles the scalars, that wase stored
- * in this block.
+/**
+ * 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) {
+
+ int i;
+ ir_node *mem;
+
+ 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;
are synced from this sync node.*/
ent_leaves_t *value_ent;
value_arr_entry_t *val_arr_blk, *val_arr;
- ir_node *pred, *leave, **in;
+ ir_node *pred, *leave, *sync, **in;
ir_node *sync_blk; /**< The block, where the sync node must be created.*/
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)
add_mem_edge(val_arr, GET_IRN_VNUM(leave), &in, &unk_vnum);
/* We create the sync and set it in the global memory state.*/
- val_arr[env->gl_mem_vnum].mem_edge_state = new_r_Sync(current_ir_graph, sync_blk, ARR_LEN(in), in);
- /* 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);
+ 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
+/**
+ * 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.
}
}
+/**
+ * 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, **in;
- int n, i, j;
+ 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);
in = alloca(sizeof(*in) * n);
- for (i = env->gl_mem_vnum; i >= 0; --i) {
+ 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)){
- if(val_arr[i].access_type > 3)
- /* This scalar was saved and we don't need
- * to produce a phi for it.*/
- continue;
+ unk = new_Unknown(mode_M);
+ for (j = n - 1; j >= 0; --j)
+ in[j] = unk;
- unk = new_Unknown(mode_M);
- for (j = n - 1; j >= 0; --j)
- in[j] = unk;
- if(i != env->gl_mem_vnum)
- val_arr[i].mem_edge_state = new_r_Phi(current_ir_graph, irn_blk, n, in, mode_M);
- else{
- /* We use for the global memory the phi node, that
- * is already available.*/
- val_arr[i].mem_edge_state = irn;
- }
+ 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[i].mem_edge_state, i, env);
- }
+ 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
+/**
+ * The function handles the call nodes, that have
* as parameter a scalar
*
* @param env The enviroment pinter.
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 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) {
/* 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.*/
} 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(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);
+ /* 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_op *op;
sels_t key_sels, *value_sels;
value_arr_entry_t *val_arr;
- pset *accessed_entities;
+ pset *accessed_entities; /**< A set to save all entities accessed from a call.*/
int i;
irn_blk = get_nodes_block(irn);
if (Block_not_block_visited(irn_blk)) {
- /* We sync first the stored scalar address in this block.*/
+ /* We sync first the stored scalar address in this block.*/
mark_Block_block_visited(irn_blk);
sync_stored_scalars(irn_blk, 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));
+ }
}
- split_call_mem_edge(env, irn, accessed_entities);
+ if(pset_count(accessed_entities))
+ split_call_mem_edge(env, irn, accessed_entities);
+
+ del_pset(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)
{
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);
/**
* fix the Load/Store or Call list
+ *
+ * @param The enviroment pinter.
*/
static void fix_ls(env_t *env)
{
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;
/**
* 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;
+ ir_node *sync, *block, *pred, *val;
+ int i, k;
for (l = env->fix_syncs; l; l = get_irn_link(sync)) {
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);
+
+ if(val)
+ set_irn_n(sync, 0, val);
}
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);
+
+ 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) {
value_arr_entry_t *val_arr;
- ir_node **in, *sync, *Return, *Return_blk;
- int i, vnum, vnum_state;
+ 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);
vnum_state = 0;
- for(i = 0; i <= env->gl_mem_vnum; i++)
+
+ 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 successors of the sync.*/
+ /* We allocate the memory, that we need for the predecessors of the sync.*/
in = malloc(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.*/
in[0] = val_arr[env->gl_mem_vnum].mem_edge_state;
- for(i = 1, vnum = 0; vnum < env->gl_mem_vnum; vnum++) {
+ for(i = 1, vnum = 0; vnum < (int)env->gl_mem_vnum; vnum++) {
- if(val_arr[vnum].access_type > 3)
- /* this scalar was saved and we must not sync it memory edge.*/
- continue;
+ 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_value(Return_blk, vnum);
+ 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);
+ }
+ else
+ in[i] = val_arr[vnum].mem_edge_state;
+ i++;
}
- 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, vnum_state, in);
set_Return_mem(Return, sync);
/**
* 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));
- }
- }
- }
+ /* 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 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;
+ 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, *leave;
- ir_loop *blk_loop;
+ 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);
- blk_loop = get_irn_loop(pred_blk);
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;
- /* 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;
-
- 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);
- inc_irg_block_visited(current_ir_graph);
+ // 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 remove the critical edges of a ir graph. */
remove_critical_cf_edges(irg);
- /* Call algorithm that computes the out edges */
+ /* 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 */
+ /* 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);
}
}