X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fdata_flow_scalar_replace.c;h=2b535e42c871a7392d249fbe657a06da4f5e2b45;hb=1268a295e95b532b46e2aed04505d5206181afda;hp=eeccbb0b81f2999bb356ae6ac0b9b8e63fc55fd8;hpb=529678cf846e774807b0e3e1b58de1e76019789c;p=libfirm diff --git a/ir/opt/data_flow_scalar_replace.c b/ir/opt/data_flow_scalar_replace.c index eeccbb0b8..2b535e42c 100644 --- a/ir/opt/data_flow_scalar_replace.c +++ b/ir/opt/data_flow_scalar_replace.c @@ -1,110 +1,97 @@ /* - * Project: libFIRM - * File name: ir/opt/scalar_replace.c - * Purpose: scalar replacement of arrays and compounds - * Author: Beyhan Veliev - * Modified by: Michael Beck - * Created: - * CVS-ID: $Id$ - * Copyright: (c) 1998-2005 Universität Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif -#ifdef HAVE_ALLOCA_H -#include -#endif +/** + * @file + * @brief scalar replacement of arrays and compounds + * @author Beyhan Veliev, Michael Beck + * @version $Id$ + */ +#include "config.h" -#ifdef HAVE_MALLOC_H -#include -#endif +#include "iroptimize.h" -#ifdef HAVE_STRING_H #include -#endif -#include "data_flow_scalar_replace.h" #include "irflag_t.h" #include "irouts.h" #include "pset.h" #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 "irgopt.h" +#include "xmalloc.h" #define SET_ENT_VNUM(ent, vnum) set_entity_link(ent, INT_TO_PTR(vnum)) #define GET_ENT_VNUM(ent) (unsigned)PTR_TO_INT(get_entity_link(ent)) #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; + ir_entity *ent; /**< An entity, that contains scalars for replace.*/ + pset *leaves; /**< All leaves of this entity.*/ } ent_leaves_t; typedef struct _sels_t { - ir_node *sel; - entity *ent; + ir_node *sel; /**< A sel node, thats entity have scalars.*/ + ir_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 * accesses like a.b.c[8].d */ typedef union { - entity *ent; + ir_entity *ent; tarval *tv; } path_elem_t; @@ -118,9 +105,22 @@ typedef struct _path_t { 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; + /** @@ -132,6 +132,7 @@ static int ent_leaves_t_cmp(const void *elt, const void *key, size_t size) { const ent_leaves_t *c1 = elt; const ent_leaves_t *c2 = key; + (void) size; return c1->ent != c2->ent; } @@ -141,10 +142,10 @@ 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; + const ir_entity *c1 = elt; + const ir_entity *c2 = key; return c1 != c2; } @@ -158,6 +159,7 @@ static int sels_cmp(const void *elt, const void *key, size_t size) { const sels_t *c1 = elt; const sels_t *c2 = key; + (void) size; return c1->sel != c2->sel; } @@ -167,12 +169,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; + ir_node *c1 = (ir_node *)elt; + ir_node *c2 = (ir_node *)key; - return c1 != c2; + return get_Sel_entity(c1) != get_Sel_entity(c2); } /** @@ -184,6 +186,7 @@ static int call_cmp(const void *elt, const void *key, size_t size) { const call_access_t *c1 = elt; const call_access_t *c2 = key; + (void) size; return c1->call != c2->call; } @@ -197,6 +200,7 @@ static int path_cmp(const void *elt, const void *key, size_t size) { const path_t *p1 = elt; const path_t *p2 = key; + (void) size; /* we can use memcmp here, because identical tarvals should have identical addresses */ return memcmp(p1->path, p2->path, p1->path_len * sizeof(p1->path[0])); @@ -227,17 +231,17 @@ static int is_const_sel(ir_node *sel) { for (i = 0; i < n; ++i) { ir_node *idx = get_Sel_index(sel, i); - if (get_irn_op(idx) != op_Const) + if (!is_Const(idx)) return 0; } return 1; } -/* +/** * Returns non-zero, if the address of an entity * represented by a Sel node (or it's successor Sels) is taken. */ -static int is_address_taken(ir_node *sel) +static int is_address_taken_2(ir_node *sel) { int i; @@ -260,7 +264,7 @@ static int is_address_taken(ir_node *sel) case iro_Sel: { /* Check the Sel successor of Sel */ - int res = is_address_taken(succ); + int res = is_address_taken_2(succ); if (res) return 1; @@ -288,7 +292,7 @@ static int is_address_taken(ir_node *sel) * @param ent the entity that will be scalar replaced * @param sel a Sel node that selects some fields of this entity */ -static void link_all_leave_sels(entity *ent, ir_node *sel) +static void link_all_leave_sels(ir_entity *ent, ir_node *sel) { int i, n; @@ -296,16 +300,15 @@ static void link_all_leave_sels(entity *ent, ir_node *sel) for (i = 0; i < n; ++i) { ir_node *succ = get_irn_out(sel, i); - if (get_irn_op(succ) == op_Sel) + if (is_Sel(succ)) link_all_leave_sels(ent, succ); - } /* if Sel nodes with memory inputs are used, a entity can be * visited more than once causing a ring here, so we use the * node flag to mark linked nodes */ - if (irn_visited(sel)) + if (irn_visited_else_mark(sel)) return; /* @@ -313,8 +316,6 @@ static void link_all_leave_sels(entity *ent, ir_node *sel) */ set_irn_link(sel, get_entity_link(ent)); set_entity_link(ent, sel); - - mark_irn_visited(sel); } /* we need a special address that serves as an address taken marker */ @@ -338,6 +339,7 @@ static void *ADDRESS_TAKEN = &_x; static int find_possible_replacements(ir_graph *irg) { ir_node *irg_frame = get_irg_frame(irg); + ir_type *frame_tp; int i, n; int res = 0; @@ -346,19 +348,12 @@ static int find_possible_replacements(ir_graph *irg) n = get_irn_n_outs(irg_frame); /* - * First, clear the link field of all interestingentities. - * Note that we did not rely on the fact that there is only - * one Sel node per entity, so we might access one entity - * more than once here. - * That's why we have need two loops. + * First, clear the link field of all interesting entities. */ - for (i = 0; i < n; ++i) { - ir_node *succ = get_irn_out(irg_frame, i); - - if (get_irn_op(succ) == op_Sel) { - entity *ent = get_Sel_entity(succ); - set_entity_link(ent, NULL); - } + frame_tp = get_irg_frame_type(irg); + for (i = get_class_n_members(frame_tp) - 1; i >= 0; --i) { + ir_entity *ent = get_class_member(frame_tp, i); + set_entity_link(ent, NULL); } /* @@ -369,18 +364,34 @@ static int find_possible_replacements(ir_graph *irg) for (i = 0; i < n; ++i) { ir_node *succ = get_irn_out(irg_frame, i); - if (get_irn_op(succ) == op_Sel) { - entity *ent = get_Sel_entity(succ); + if (is_Sel(succ)) { + ir_entity *ent = get_Sel_entity(succ); ir_type *ent_type; - if (get_entity_link(ent) == ADDRESS_TAKEN) + /* we are only interested in entities on the frame, NOT + on the value type */ + if (get_entity_owner(ent) != frame_tp) + continue; + + 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 */ if (is_Array_type(ent_type) || is_Struct_type(ent_type) || is_atomic_type(ent_type)) { - if (is_address_taken(succ)) { + if (is_address_taken_2(succ)) { if (get_entity_link(ent)) /* killing one */ --res; set_entity_link(ent, ADDRESS_TAKEN); @@ -404,7 +415,7 @@ static int is_leave_sel(ir_node *sel) { for(i = get_irn_n_outs(sel) - 1; i >= 0; i--) { succ = get_irn_out(sel, i); - if(get_irn_op(succ) == op_Sel) + if (is_Sel(succ)) return 0; } @@ -427,10 +438,9 @@ static path_t *find_path(ir_node *sel, unsigned len) n = get_Sel_n_indexs(sel); len += n + 1; - if (get_irn_op(pred) != op_Sel) { + if (!is_Sel(pred)) { /* we found the root */ - - res = xmalloc(sizeof(*res) + (len - 1) * sizeof(res->path)); + res = XMALLOCF(path_t, path, len); res->path_len = len; } else @@ -442,7 +452,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 (is_Const(index)) + res->path[pos++].tv = get_Const_tarval(index); } return res; } @@ -459,7 +470,7 @@ static path_t *find_path(ir_node *sel, unsigned len) * * @return the next free value number */ -static unsigned allocate_value_numbers(set *set_sels, pset *leaves, entity *ent, unsigned vnum) +static unsigned allocate_value_numbers(set *set_sels, pset *leaves, ir_entity *ent, unsigned vnum) { ir_node *sel, *next; path_t *key, *path; @@ -479,9 +490,8 @@ 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_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)); @@ -503,83 +513,326 @@ static unsigned allocate_value_numbers(set *set_sels, pset *leaves, entity *ent, 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) { + + 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) { - value_arr_entry_t *val_arr, *val_arr_pred; - ir_node *pred; - int n; + fixlist_entry_t *l; - val_arr = get_irn_link(call_blk); + l = obstack_alloc(&env->obst, sizeof(*l)); + l->irn = irn; + l->vnum = vnum; - if(val_arr[ent_vnum].access_type == 0) - return 0; + 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; + } +} - n = get_Block_n_cfgpreds(call_blk) - 1; +static void add_mem_edge(value_arr_entry_t *val_arr, int vnum, ir_node ***in, int **accessed_vnum) { - for( ; n >= 0; n--) { - pred = get_Block_cfgpred(call_blk, n); - pred = get_nodes_block(pred); - val_arr_pred = get_irn_link(pred); + 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)); + } +} +/** + * The function handles the scalars, that wase stored + * in this block. + * + * @param blk The block, that must be handled. + * @param env The enviroment pinter. + */ - if(val_arr_pred[ent_vnum].access_type != 0) - /* This scalar wasn't stored in this block.*/ - return 1; +/* 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; } - return 0; + /* is not reachable*/ + return NULL; } -/* 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) { +static void sync_stored_scalars(ir_node *blk, env_t *env) { - 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; + 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 (is_Sync(sync)) { + val_arr[env->gl_mem_vnum].mem_edge_state = sync; + /* We add this sync node to the sync's fix list.*/ + add_sync_to_fixlist(val_arr[env->gl_mem_vnum].mem_edge_state, unk_vnum, env); + } + 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 = ALLOCAN(ir_node*, 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; + ir_entity *ent; + unsigned ent_vnum; + int fix_irn = 0; /**< Set to 1 if we must add this call to it fix list.*/ + int *accessed_leaves_vnum = NULL; /**< An arraw, where are saved the value number, that + are synced from call's sync node, if we need it.*/ 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) { @@ -590,22 +843,15 @@ static void handle_call(env_t *env, ir_node *call, pset *accessed_entities) { 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.*/ @@ -621,173 +867,119 @@ static void handle_call(env_t *env, ir_node *call, pset *accessed_entities) { /* 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 (is_Sync(sync)) { + set_Call_mem(call, sync); + if(ARR_LEN(accessed_leaves_vnum)) + /* We add this sync node to the sync's fix list.*/ + 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.*/ - - 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."); + if(op == op_Block) + irn_blk = irn; + else + irn_blk = get_nodes_block(irn); - 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_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 (is_NoMem(get_Call_mem(irn))) + 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 (is_Sel(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)) { + if (!Block_block_visited(block)) { mark_Block_block_visited(block); val_arr = get_irn_link(block); @@ -798,7 +990,7 @@ static ir_node *find_value(ir_node *block, unsigned vnum) 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; } @@ -808,11 +1000,13 @@ 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) { fixlist_entry_t *l; - ir_node *irn, *block, *pred, *val; + ir_node *irn, *block, *pred, *val = NULL; ir_op *op; int i; @@ -826,30 +1020,34 @@ static void fix_ls(env_t *env) 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; @@ -861,7 +1059,7 @@ static void fix_phis(env_t *env) 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); @@ -872,16 +1070,19 @@ 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 = 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.*/ @@ -890,64 +1091,81 @@ static void fix_syncs(env_t *env) pred = get_nodes_block(pred); /* We first repair the global memory edge at the first position of sync predecessors.*/ - if(get_irn_op(get_irn_n(sync, 0)) == op_Unknown) { + if (is_Unknown(get_irn_n(sync, 0))) { inc_irg_block_visited(current_ir_graph); - val = find_value(pred, env->gl_mem_vnum); - 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*/ - if(get_irn_op(get_irn_n(sync, i)) == op_Unknown) { + + assert(k <= ARR_LEN(l->accessed_vnum) && "The algorythm for sync repair is wron"); + if (is_Unknown(get_irn_n(sync, i))) { 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 = XMALLOCN(ir_node*, vnum_state); + /* The global memory edge is the first predecessor of this sync node.*/ if(val_arr[env->gl_mem_vnum].mem_edge_state == NULL) { /* We must search through blocks for this memory state.*/ inc_irg_block_visited(current_ir_graph); - in[0] = find_value(Return_blk, env->gl_mem_vnum); + in[0] = find_vnum_value(Return_blk, env->gl_mem_vnum); } else in[0] = val_arr[env->gl_mem_vnum].mem_edge_state; - 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); @@ -955,108 +1173,144 @@ 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_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 (!is_Call(irn)) + return; - if(get_irn_op(irn) != op_Call) + /* Calls that have a NoMem input do neither read nor write memory. + We can completely ignore them here. */ + if (is_NoMem(get_Call_mem(irn))) 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); - } - } - } + /* 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 (is_Sel(param)) { + /* We have found a parameter with operation sel.*/ + key_sels.sel = param; + value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel)); + 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); + + if (is_SymConst(call_ptr) && get_SymConst_kind(call_ptr) == symconst_addr_ent) { + meth_ent = get_SymConst_entity(call_ptr); + /* we get the access type for our sel.*/ + acces_type = get_method_param_access(meth_ent, i); + } 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--) { @@ -1064,39 +1318,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); + 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); } @@ -1105,8 +1394,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) { @@ -1129,8 +1421,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); @@ -1145,20 +1437,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); + + // 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); } /* @@ -1166,42 +1469,44 @@ 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 computes the out edges */ - if (get_irg_outs_state(irg) != outs_consistent) - compute_irg_outs(irg); + /* Call algorithm that remove the critical edges of a ir graph. */ + remove_critical_cf_edges(irg); + + /* Call algorithm that computes the out edges.*/ + assure_irg_outs(irg); + + /* Call algorithm that computes the loop information.*/ + construct_cf_backedges(irg); + + /* Call algorithm that computes the dominance information.*/ + assure_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); for (i = 0 ; i < get_irn_n_outs(irg_frame); i++) { ir_node *succ = get_irn_out(irg_frame, i); - if (get_irn_op(succ) == op_Sel) { - entity *ent = get_Sel_entity(succ); + if (is_Sel(succ)) { + ir_entity *ent = get_Sel_entity(succ); if (get_entity_link(ent) == NULL || get_entity_link(ent) == ADDRESS_TAKEN) continue; @@ -1214,7 +1519,6 @@ 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); /* Allocate value number for the globule memory edge. * and a value number for the value numbers state.*/ @@ -1224,8 +1528,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); } }