X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fdata_flow_scalar_replace.c;h=5051970125de43fcbbf850e71c7122e828314147;hb=83d1882a9e3dd5f74aa87c6fdb534516c75cb857;hp=f923a5cb06edc838e0f726ec6c93187dfea655c8;hpb=b78bdd4d94de46de4156272e6dbfe44e97933a5b;p=libfirm diff --git a/ir/opt/data_flow_scalar_replace.c b/ir/opt/data_flow_scalar_replace.c index f923a5cb0..505197012 100644 --- a/ir/opt/data_flow_scalar_replace.c +++ b/ir/opt/data_flow_scalar_replace.c @@ -1,31 +1,34 @@ /* - * Project: libFIRM - * File name: ir/opt/data_flow_scalar_replace.c - * Purpose: scalar replacement of arrays and compounds - * Author: Beyhan Veliev - * Modified by: Michael Beck - * Created: - * CVS-ID: $Id$ - * Copyright: (c) 1998-2005 Universität Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif -#ifdef HAVE_ALLOCA_H -#include -#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" @@ -38,8 +41,8 @@ #include "irloop.h" #include "analyze_irg_args.h" #include "irprintf.h" -#include "compute_loop_info.h" #include "irgopt.h" +#include "xmalloc.h" #define SET_ENT_VNUM(ent, vnum) set_entity_link(ent, INT_TO_PTR(vnum)) #define GET_ENT_VNUM(ent) (unsigned)PTR_TO_INT(get_entity_link(ent)) @@ -49,13 +52,13 @@ typedef struct _ent_leaves_t{ - entity *ent; /**< An entity, that contains scalars for replace.*/ + ir_entity *ent; /**< An entity, that contains scalars for replace.*/ pset *leaves; /**< All leaves of this entity.*/ } ent_leaves_t; typedef struct _sels_t { ir_node *sel; /**< A sel node, thats entity have scalars.*/ - entity *ent; /**< The entity of this sel node.*/ + ir_entity *ent; /**< The entity of this sel node.*/ }sels_t; typedef struct _call_access_t { @@ -88,7 +91,7 @@ typedef struct _leave_t { * accesses like a.b.c[8].d */ typedef union { - entity *ent; + ir_entity *ent; tarval *tv; } path_elem_t; @@ -129,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; } @@ -140,8 +144,8 @@ static int ent_leaves_t_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; } @@ -155,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; } @@ -166,10 +171,10 @@ static int sels_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->attr.s.ent != c2->attr.s.ent; + return get_Sel_entity(c1) != get_Sel_entity(c2); } /** @@ -181,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; } @@ -194,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])); @@ -224,7 +231,7 @@ 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; @@ -234,7 +241,7 @@ static int is_const_sel(ir_node *sel) { * 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; @@ -257,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; @@ -285,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; @@ -293,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; /* @@ -310,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 */ @@ -352,8 +356,8 @@ 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); set_entity_link(ent, NULL); } } @@ -366,8 +370,8 @@ 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) @@ -388,7 +392,7 @@ static int find_possible_replacements(ir_graph *irg) /* 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); @@ -412,7 +416,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; } @@ -435,10 +439,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 @@ -450,7 +453,7 @@ static path_t *find_path(ir_node *sel, unsigned len) for (i = 0; i < n; ++i) { ir_node *index = get_Sel_index(sel, i); - if(get_irn_op(index) == op_Const) + if (is_Const(index)) res->path[pos++].tv = get_Const_tarval(index); } return res; @@ -468,7 +471,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; @@ -612,13 +615,13 @@ static void sync_stored_scalars(ir_node *blk, env_t *env) { val_arr = get_irn_link(pred); if(val_arr[GET_ENT_VNUM(value_ent->ent)].access_type == SYNCED) - /* This entity was synced.*/ - continue; + /* This entity was synced.*/ + continue; if(val_arr[GET_ENT_VNUM(value_ent->ent)].access_type <= 3) { - /* To avoid repeated sync of this entity in this block.*/ - val_arr[GET_ENT_VNUM(value_ent->ent)].access_type = SYNCED; + /* To avoid repeated sync of this entity in this block.*/ + val_arr[GET_ENT_VNUM(value_ent->ent)].access_type = SYNCED; /* In this predecessor block is this entity not acessed. * We must sync in the end ot this block.*/ if(get_Block_n_cfgpreds(blk) > 1) @@ -649,7 +652,7 @@ static void sync_stored_scalars(ir_node *blk, env_t *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) { + 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); @@ -754,9 +757,8 @@ static void split_phi_mem_edge(ir_node *irn, env_t *env) { 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); + 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) @@ -791,15 +793,12 @@ static void split_call_mem_edge(env_t *env, ir_node *call, pset *accessed_entiti call_access_t key_call, *value_call; ir_node *call_blk, *new_mem_state, *leave; ir_node *sync, **in; - entity *ent; + ir_entity *ent; unsigned ent_vnum; int fix_irn = 0; /**< Set to 1 if we must add this call to it fix list.*/ int *accessed_leaves_vnum = NULL; /**< An arraw, where are saved the value number, that are synced from call's sync node, if we need it.*/ - if(get_irn_node_nr(call) == 2763) - printf("\nHi\n"); - call_blk = get_nodes_block(call); val_arr = get_irn_link(call_blk); /* An array to save the memory edges, that must be @@ -879,8 +878,7 @@ static void split_call_mem_edge(env_t *env, ir_node *call, pset *accessed_entiti /* We must check this, why it is possible to get a Bad node * form new_r_Sync(), when the node can be optimized. * In this case we must do nothing.*/ - if(get_irn_op(sync) == op_Sync) { - + if (is_Sync(sync)) { set_Call_mem(call, sync); if(ARR_LEN(accessed_leaves_vnum)) /* We add this sync node to the sync's fix list.*/ @@ -915,7 +913,7 @@ static void split_memory_edge(ir_node *irn, void *ctx) { else irn_blk = get_nodes_block(irn); - if (Block_not_block_visited(irn_blk)) { + if (!Block_block_visited(irn_blk)) { /* We sync first the stored scalar address in this block.*/ mark_Block_block_visited(irn_blk); sync_stored_scalars(irn_blk, env); @@ -937,7 +935,7 @@ static void split_memory_edge(ir_node *irn, void *ctx) { /* Calls that have a NoMem input do neither read nor write memory. We can completely ignore them here. */ - if (get_irn_op(get_Call_mem(irn)) == op_NoMem) + if (is_NoMem(get_Call_mem(irn))) return; /* We save in this set all entities, @@ -949,7 +947,7 @@ static void split_memory_edge(ir_node *irn, void *ctx) { sel = get_Call_param(irn, i); value_sels = NULL; - if(get_irn_op(sel) == op_Sel) { + if (is_Sel(sel)) { key_sels.sel = sel; value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel)); @@ -976,13 +974,13 @@ static void split_memory_edge(ir_node *irn, void *ctx) { * @param block A block from the current ir graph. * @param vnum The value number, that must be found. */ -static ir_node *find_value(ir_node *block, unsigned vnum) +static ir_node *find_vnum_value(ir_node *block, unsigned vnum) { value_arr_entry_t *val_arr; int i; ir_node *res; - if (Block_not_block_visited(block)) { + if (!Block_block_visited(block)) { mark_Block_block_visited(block); val_arr = get_irn_link(block); @@ -993,7 +991,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; } @@ -1009,7 +1007,7 @@ static ir_node *find_value(ir_node *block, unsigned vnum) 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; @@ -1023,7 +1021,7 @@ 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; @@ -1031,12 +1029,12 @@ static void fix_ls(env_t *env) if(val) { if(op == op_Store) - set_Store_mem(irn, val); + set_Store_mem(irn, val); else - if(op == op_Load) - set_Load_mem(irn, val); - else - set_Call_mem(irn, val); + if(op == op_Load) + set_Load_mem(irn, val); + else + set_Call_mem(irn, val); } } } @@ -1062,7 +1060,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); @@ -1094,9 +1092,9 @@ 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); + val = find_vnum_value(pred, env->gl_mem_vnum); if(val) set_irn_n(sync, 0, val); @@ -1106,9 +1104,9 @@ static void fix_syncs(env_t *env) /* We repair the leaves*/ assert(k <= ARR_LEN(l->accessed_vnum) && "The algorythm for sync repair is wron"); - if(get_irn_op(get_irn_n(sync, i)) == op_Unknown) { + if (is_Unknown(get_irn_n(sync, i))) { inc_irg_block_visited(current_ir_graph); - val = find_value(pred, l->accessed_vnum[k++]); + val = find_vnum_value(pred, l->accessed_vnum[k++]); if(val) set_irn_n(sync, i, val); @@ -1140,13 +1138,13 @@ static void sync_mem_edges(env_t *env) { vnum_state++; /* We allocate the memory, that we need for the predecessors of the sync.*/ - in = xmalloc(sizeof(ir_node*) *vnum_state); + in = XMALLOCN(ir_node*, vnum_state); /* The global memory edge is the first predecessor of this sync node.*/ if(val_arr[env->gl_mem_vnum].mem_edge_state == NULL) { /* We must search through blocks for this memory state.*/ inc_irg_block_visited(current_ir_graph); - in[0] = find_value(Return_blk, env->gl_mem_vnum); + in[0] = find_vnum_value(Return_blk, env->gl_mem_vnum); } else in[0] = val_arr[env->gl_mem_vnum].mem_edge_state; @@ -1160,7 +1158,7 @@ static void sync_mem_edges(env_t *env) { if(val_arr[vnum].mem_edge_state == NULL) { /* We must search through blocks for this memory state.*/ inc_irg_block_visited(current_ir_graph); - in[i] = find_value(Return_blk, vnum); + in[i] = find_vnum_value(Return_blk, vnum); } else in[i] = val_arr[vnum].mem_edge_state; @@ -1212,26 +1210,25 @@ static void analyse_calls(ir_node *irn, void *ctx) { int i, vnum; unsigned int acces_type; ir_node *param, *call_ptr, *blk; - ir_op *op; - entity *meth_ent; + ir_entity *meth_ent; sels_t key_sels, *value_sels; call_access_t key_call, *value_call; value_arr_entry_t *val_arr; env_t *env; env = ctx; - if(get_irn_op(irn) != op_Call) + if (!is_Call(irn)) return; /* Calls that have a NoMem input do neither read nor write memory. We can completely ignore them here. */ - if (get_irn_op(get_Call_mem(irn)) == op_NoMem) + if (is_NoMem(get_Call_mem(irn))) return; /* We iterate over the parameters of this call nodes.*/ for ( i = get_Call_n_params(irn) - 1; i >= 0; i--) { param = get_Call_param(irn, i); - if(get_irn_op(param) == op_Sel) { + if (is_Sel(param)) { /* We have found a parameter with operation sel.*/ key_sels.sel = param; value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel)); @@ -1239,9 +1236,8 @@ static void analyse_calls(ir_node *irn, void *ctx) { /* We have found a call, that have as parameter a sel from our set_sels.*/ call_ptr = get_Call_ptr(irn); - op = get_irn_op(call_ptr); - if(op == op_SymConst && get_SymConst_kind(call_ptr) == symconst_addr_ent) { + if (is_SymConst(call_ptr) && get_SymConst_kind(call_ptr) == symconst_addr_ent) { meth_ent = get_SymConst_entity(call_ptr); /* we get the access type for our sel.*/ acces_type = get_method_param_access(meth_ent, i); @@ -1284,21 +1280,6 @@ static void analyse_calls(ir_node *irn, void *ctx) { } } -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; @@ -1345,7 +1326,7 @@ static void set_block_access(ir_node *irn, void *ctx){ vnum = GET_ENT_VNUM(value_leaves->ent); if((get_Block_n_cfgpreds(irn) > 1) && (val_arr[vnum].access_type > 3)) - env->changes = set_block_dominated_first_access(irn, vnum, val_arr[vnum].access_type); + env->changes = set_block_dominated_first_access(irn, vnum, val_arr[vnum].access_type); if((val_arr_pred[vnum].access_type > 3) && (val_arr[vnum].access_type < 3)) { /* We have found a block for update it access and value number information.*/ @@ -1508,13 +1489,13 @@ void data_flow_scalar_replacement_opt(ir_graph *irg) { remove_critical_cf_edges(irg); /* Call algorithm that computes the out edges.*/ - if (get_irg_outs_state(irg) != outs_consistent) - compute_irg_outs(irg); + assure_irg_outs(irg); /* Call algorithm that computes the loop information.*/ - compute_loop_info(irg); + construct_cf_backedges(irg); + /* Call algorithm that computes the dominance information.*/ - compute_doms(irg); + assure_doms(irg); /* Find possible scalar replacements */ if (find_possible_replacements(irg)) { @@ -1525,8 +1506,8 @@ void data_flow_scalar_replacement_opt(ir_graph *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; @@ -1540,9 +1521,6 @@ void data_flow_scalar_replacement_opt(ir_graph *irg) { } } - if(get_firm_verbosity()) - printf("vnumber in data flow= %i\n", vnum); - /* Allocate value number for the globule memory edge. * and a value number for the value numbers state.*/ vnum = vnum + 2;