X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fdata_flow_scalar_replace.c;h=6a45fdab9edb022554db12aa3beda7093b780121;hb=ee5c07444d26eaae35ff78a7b2a7605ad3dc3f2b;hp=dc65fdb1306e6f9bad77bc8ff2228fe2cd3d3a2c;hpb=3d7cd58108a2de89e0d3f69f0411461169243047;p=libfirm diff --git a/ir/opt/data_flow_scalar_replace.c b/ir/opt/data_flow_scalar_replace.c index dc65fdb13..6a45fdab9 100644 --- a/ir/opt/data_flow_scalar_replace.c +++ b/ir/opt/data_flow_scalar_replace.c @@ -32,19 +32,20 @@ #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{ @@ -137,7 +138,7 @@ static int ent_leaves_t_cmp(const void *elt, const void *key, size_t size) * * @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; @@ -163,12 +164,12 @@ static int sels_cmp(const void *elt, const void *key, size_t size) * * @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; } /** @@ -229,7 +230,7 @@ static int is_const_sel(ir_node *sel) { return 1; } -/* +/** * Returns non-zero, if the address of an entity * represented by a Sel node (or it's successor Sels) is taken. */ @@ -438,7 +439,8 @@ static path_t *find_path(ir_node *sel, unsigned len) 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; } @@ -475,7 +477,6 @@ static unsigned allocate_value_numbers(set *set_sels, pset *leaves, entity *ent, 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))); @@ -499,7 +500,8 @@ static unsigned allocate_value_numbers(set *set_sels, pset *leaves, entity *ent, 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. @@ -515,7 +517,8 @@ static void add_sync_to_fixlist(ir_node *sync, int *unk_vnum, env_t *env) { 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. @@ -547,13 +550,30 @@ static void add_mem_edge(value_arr_entry_t *val_arr, int vnum, ir_node ***in, in 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; @@ -561,7 +581,7 @@ static void sync_stored_scalars(ir_node *blk, env_t *env) { 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.*/ @@ -580,7 +600,14 @@ static void sync_stored_scalars(ir_node *blk, env_t *env) { 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) @@ -607,16 +634,22 @@ static void sync_stored_scalars(ir_node *blk, env_t *env) { 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. @@ -693,10 +726,18 @@ static void split_ls_mem_edge(ir_node *irn, env_t *env) { } } +/** + * 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); @@ -706,29 +747,27 @@ static void split_phi_mem_edge(ir_node *irn, env_t *env) { 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. @@ -747,6 +786,9 @@ static void split_call_mem_edge(env_t *env, ir_node *call, pset *accessed_entiti 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 @@ -759,9 +801,7 @@ static void split_call_mem_edge(env_t *env, ir_node *call, pset *accessed_entiti /* 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) { @@ -802,7 +842,7 @@ static void split_call_mem_edge(env_t *env, ir_node *call, pset *accessed_entiti /* 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.*/ @@ -825,16 +865,27 @@ static void split_call_mem_edge(env_t *env, ir_node *call, pset *accessed_entiti } 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; @@ -842,7 +893,7 @@ static void split_memory_edge(ir_node *irn, void *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; @@ -854,7 +905,7 @@ static void split_memory_edge(ir_node *irn, void *ctx) { 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); } @@ -872,25 +923,36 @@ static void split_memory_edge(ir_node *irn, void *ctx) { } 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); } } } @@ -899,12 +961,15 @@ static void split_memory_edge(ir_node *irn, void *ctx) { /** * 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); @@ -927,6 +992,8 @@ static ir_node *find_value(ir_node *block, unsigned vnum) /** * fix the Load/Store or Call list + * + * @param The enviroment pinter. */ static void fix_ls(env_t *env) { @@ -951,24 +1018,28 @@ 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; @@ -991,12 +1062,14 @@ static void fix_phis(env_t *env) /** * 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)) { @@ -1013,39 +1086,51 @@ static void fix_syncs(env_t *env) 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.*/ @@ -1056,24 +1141,22 @@ static void sync_mem_edges(env_t *env) { 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); @@ -1082,108 +1165,161 @@ static void sync_mem_edges(env_t *env) { /** * 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--) { @@ -1191,46 +1327,74 @@ static void set_block_access(ir_node *irn, void *ctx){ * 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); } @@ -1239,8 +1403,11 @@ static void print_block_state(ir_node *irn, void *ctx) { /** 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) { @@ -1263,8 +1430,8 @@ static void do_data_flow_scalar_replacement(set *set_ent, set *set_sels, int vnu /* 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); @@ -1279,22 +1446,31 @@ static void do_data_flow_scalar_replacement(set *set_ent, set *set_sels, int vnu 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); } /* @@ -1302,40 +1478,36 @@ static void do_data_flow_scalar_replacement(set *set_ent, set *set_sels, int vnu * * @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); @@ -1356,7 +1528,9 @@ void data_flow_scalar_replacement_opt(ir_graph *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.*/ @@ -1366,8 +1540,13 @@ void data_flow_scalar_replacement_opt(ir_graph *irg) 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); } }