X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fanalyze_irg_args.c;h=9cf6b2b1c14c398e00a1298b851ddb277758b34f;hb=847c1b62a1eae1e8055645996049f7f5db0a0d8b;hp=50f981e894d2ded71c5bc83297305f3eb9463847;hpb=ff250a974bfc97f7a9acf86ad77bbfaed855cb04;p=libfirm diff --git a/ir/ana/analyze_irg_args.c b/ir/ana/analyze_irg_args.c index 50f981e89..9cf6b2b1c 100644 --- a/ir/ana/analyze_irg_args.c +++ b/ir/ana/analyze_irg_args.c @@ -1,274 +1,483 @@ /* - * Project: libFIRM - * File name: ir/ana/analyze_irg_agrs.c - * Purpose: read/write analyze of graph argument, which have mode reference. - * Author: Beyhan Veliev - * 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. */ /** - * @file analyze_irg_agrs.c - * + * @file + * @brief read/write analyze of graph argument, which have mode reference. + * @author Beyhan Veliev */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif -#ifdef HAVE_MALLOC_H -#include -#endif -#ifdef HAVE_ALLOCA_H -#include -#endif #include #include "irouts.h" #include "irnode_t.h" #include "irmode_t.h" -#include "array.h" +#include "array_t.h" #include "irprog.h" #include "entity_t.h" #include "analyze_irg_args.h" -/** - * A struct to save if a graph argument with mode reference is - * read/write or both. - */ -typedef struct { - unsigned char read; - unsigned char write; -} rw_info_t; - -enum access { - ACC_UNKNOWN, - ACC_ACCESSED, - ACC_NOT_ACCESSED -}; - -#define ACCESS(a) if ((a) == ACC_UNKNOWN) (a) = ACC_ACCESSED -#define NOT_ACCESS(a) if ((a) == ACC_UNKNOWN) (a) = ACC_NOT_ACCESSED - -static char v; -static void *VISITED = &v; - /** * Walk recursive the successors of a graph argument - * with mode reference and mark in the "irg_args" if it will be read, - * written or both. + * with mode reference and mark if it will be read, + * written or stored. * * @param arg The graph argument with mode reference, * that must be checked. */ -static unsigned analyze_arg(ir_node *arg, unsigned bits) +static ptr_access_kind analyze_arg(ir_node *arg, ptr_access_kind bits) { - int i, p; - ir_node *succ; - - /* We must visit a node once to avoid endless recursion.*/ - set_irn_link(arg, VISITED); - - for (i = get_irn_n_outs(arg) - 1; i >= 0; --i) { - succ = get_irn_out(arg, i); - - /* We was here.*/ - if (get_irn_link(succ) == VISITED) - continue; - - /* We should not walk over the memory edge.*/ - if (get_irn_mode(succ) == mode_M) - continue; - - /* A addition or subtraction of the argument with output, that - isn't with mode reference must not be checked.*/ - if ((get_irn_op(succ) == op_Add || get_irn_op(succ) == op_Sub) && - !mode_is_reference(get_irn_mode(succ))) - continue; - - /* A Block as successor isn't interesting.*/ - if (get_irn_op(succ) == op_Block) - continue; - - /* If we reach with the recursion a Call node and our reference - isn't the address of this Call we accept that the reference will - be read and written if the graph of the method represented by - "Call" isn't computed else we analyze that graph. If our - reference is the address of this - Call node that mean the reference will be read.*/ - if (get_irn_op(succ) == op_Call) { - ir_node *Call_ptr = get_Call_ptr(succ); - - if (Call_ptr == arg) - return bits | ptr_access_read; - else if (op_SymConst == get_irn_op(Call_ptr) && - get_SymConst_kind(Call_ptr) == symconst_addr_ent) { - entity *meth_ent = get_SymConst_entity(Call_ptr); - - for (p = get_Call_n_params(succ) - 1; p >= 0; --p){ - if (get_Call_param(succ, p) == arg) { - /* an arg can be used more than once ! */ - bits |= get_method_param_access(meth_ent, p); - } - } - } else - bits |= ptr_access_rw; - } - else if (get_irn_op(succ) == op_Store) { - /* We have reached a Store node => the reference is written. */ - bits |= ptr_access_write; - } - else if (get_irn_op(succ) == op_Load) { - /* We have reached a Load node => the reference is read. */ - bits |= ptr_access_read; - } - - /* If we know that, the argument will be read and written, we - can break the recursion.*/ - if (bits == ptr_access_rw) - return ptr_access_rw; - - bits = analyze_arg(succ, bits); - } - set_irn_link(arg, NULL); - return bits; + int i, p; + ir_node *succ; + + /* We must visit a node once to avoid endless recursion.*/ + mark_irn_visited(arg); + + for (i = get_irn_n_outs(arg) - 1; i >= 0; --i) { + succ = get_irn_out(arg, i); + + /* We was here.*/ + if (irn_visited(succ)) + continue; + + /* We should not walk over the memory edge.*/ + if (get_irn_mode(succ) == mode_M) + continue; + + /* If we reach with the recursion a Call node and our reference + isn't the address of this Call we accept that the reference will + be read and written if the graph of the method represented by + "Call" isn't computed else we analyze that graph. If our + reference is the address of this + Call node that mean the reference will be read.*/ + switch (get_irn_opcode(succ)) { + + case iro_Call: { + ir_node *ptr = get_Call_ptr(succ); + + if (ptr == arg) { + /* Hmm: not sure what this is, most likely a read */ + bits |= ptr_access_read; + } else { + ir_entity *meth_ent; + + if (is_SymConst_addr_ent(ptr)) { + meth_ent = get_SymConst_entity(ptr); + + for (p = get_Call_n_params(succ) - 1; p >= 0; --p) { + if (get_Call_param(succ, p) == arg) { + /* an arg can be used more than once ! */ + bits |= get_method_param_access(meth_ent, p); + } + } + } else if (is_Sel(ptr) && get_irp_callee_info_state() == irg_callee_info_consistent) { + /* is be a polymorphic call but callee information is available */ + int n_params = get_Call_n_params(succ); + int c; + + /* simply look into ALL possible callees */ + for (c = get_Call_n_callees(succ) - 1; c >= 0; --c) { + meth_ent = get_Call_callee(succ, c); + + /* unknown_entity is used to signal that we don't know what is called */ + if (is_unknown_entity(meth_ent)) { + bits |= ptr_access_all; + break; + } + + for (p = n_params - 1; p >= 0; --p) { + if (get_Call_param(succ, p) == arg) { + /* an arg can be used more than once ! */ + bits |= get_method_param_access(meth_ent, p); + } + } + } + } else /* can do anything */ + bits |= ptr_access_all; + } + + /* search stops here anyway */ + continue; + } + case iro_Store: + /* We have reached a Store node => the reference is written or stored. */ + if (get_Store_ptr(succ) == arg) { + /* written to */ + bits |= ptr_access_write; + } else { + /* stored itself */ + bits |= ptr_access_store; + } + + /* search stops here anyway */ + continue; + + case iro_Load: + /* We have reached a Load node => the reference is read. */ + bits |= ptr_access_read; + + /* search stops here anyway */ + continue; + + case iro_Conv: + /* our address is casted into something unknown. Break our search. */ + bits = ptr_access_all; + break; + + default: + break; + } + + /* If we know that, the argument will be read, write and stored, we + can break the recursion.*/ + if (bits == ptr_access_all) { + bits = ptr_access_all; + break; + } + + /* + * A calculation that do not lead to a reference mode ends our search. + * This is dangerous: It would allow to cast into integer and that cast back ... + * so, when we detect a Conv we go mad, see the Conv case above. + */ + if (!mode_is_reference(get_irn_mode(succ))) + continue; + + /* follow further the address calculation */ + bits = analyze_arg(succ, bits); + } + set_irn_link(arg, NULL); + return bits; } - /** * Check if a argument of the ir graph with mode * reference is read, write or both. * * @param irg The ir graph to analyze. */ -static void analyze_ent_args(entity *ent) +static void analyze_ent_args(ir_entity *ent) { - ir_graph *irg; - ir_node *irg_args, *arg; - ir_mode *arg_mode; - int nparams, i; - long proj_nr; - type *mtp; - unsigned bits; - rw_info_t *rw_info; - - mtp = get_entity_type(ent); - nparams = get_method_n_params(mtp); - - ent->param_access = NEW_ARR_F(ptr_access_kind, nparams); - - /* If the method haven't parameters we have - * nothing to do.*/ - if (nparams <= 0) - return; - - irg = get_entity_irg(ent); - - if (! irg) { - /* if we could not determine the graph, set RW access */ - for (i = nparams - 1; i >= 0; --i) - ent->param_access[i] = - is_Pointer_type(get_method_param_type(mtp, i)) ? ptr_access_rw : ptr_access_none; - - return; - } - - /* Call algorithm that computes the out edges */ - if (get_irg_outs_state(irg) != outs_consistent) - compute_outs(irg); - - irg_args = get_irg_args(irg); - - /* A array to save the information for each argument with - mode reference.*/ - NEW_ARR_A(rw_info_t, rw_info, nparams); - - /* We initialize the element with UNKNOWN state. */ - for (i = nparams - 1; i >= 0; --i) { - rw_info[i].read = ACC_UNKNOWN; - rw_info[i].write = ACC_UNKNOWN; - } - - /* search for arguments with mode reference - to analyze them.*/ - for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) { - arg = get_irn_out(irg_args, i); - arg_mode = get_irn_mode(arg); - proj_nr = get_Proj_proj(arg); - - if (mode_is_reference(arg_mode)) { - bits = analyze_arg(arg, ptr_access_none); - - if (bits & ptr_access_read) - ACCESS(rw_info[proj_nr].read); - if (bits & ptr_access_write) - ACCESS(rw_info[proj_nr].write); - } - } - - /* set all unknown values to NOT_ACCESSED */ - for (i = nparams - 1; i >= 0; --i) { - NOT_ACCESS(rw_info[i].read); - NOT_ACCESS(rw_info[i].write); - - ent->param_access[i] = (rw_info[i].read == ACC_ACCESSED ? ptr_access_read : ptr_access_none) | - (rw_info[i].write == ACC_ACCESSED ? ptr_access_write : ptr_access_none); - } - - printf("%s:\n", get_entity_name(ent)); - for (i = 0; i < nparams; ++i) { - if (is_Pointer_type(get_method_param_type(mtp, i))) - printf("Pointer Arg %i wird %s %s\n", i, - ent->param_access[i] & ptr_access_read ? "gelesen" : "", - ent->param_access[i] & ptr_access_write ? "geschrieben" : ""); - } + ir_graph *irg; + ir_node *irg_args, *arg; + ir_mode *arg_mode; + int nparams, i; + long proj_nr; + ir_type *mtp; + ptr_access_kind *rw_info; + + mtp = get_entity_type(ent); + nparams = get_method_n_params(mtp); + + ent->attr.mtd_attr.param_access = NEW_ARR_F(ptr_access_kind, nparams); + + /* If the method haven't parameters we have + * nothing to do. + */ + if (nparams <= 0) + return; + + irg = get_entity_irg(ent); + + /* we have not yet analyzed the graph, set ALL access for pointer args */ + for (i = nparams - 1; i >= 0; --i) { + ir_type *type = get_method_param_type(mtp, i); + ent->attr.mtd_attr.param_access[i] = is_Pointer_type(type) ? ptr_access_all : ptr_access_none; + } + + if (! irg) { + /* no graph, no better info */ + return; + } + + assure_irg_outs(irg); + + irg_args = get_irg_args(irg); + + /* A array to save the information for each argument with + mode reference.*/ + NEW_ARR_A(ptr_access_kind, rw_info, nparams); + + /* We initialize the element with none state. */ + for (i = nparams - 1; i >= 0; --i) + rw_info[i] = ptr_access_none; + + /* search for arguments with mode reference + to analyze them.*/ + for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) { + arg = get_irn_out(irg_args, i); + arg_mode = get_irn_mode(arg); + proj_nr = get_Proj_proj(arg); + + if (mode_is_reference(arg_mode)) + rw_info[proj_nr] |= analyze_arg(arg, rw_info[proj_nr]); + } + + /* copy the temporary info */ + memcpy(ent->attr.mtd_attr.param_access, rw_info, + nparams * sizeof(ent->attr.mtd_attr.param_access[0])); + +#if 0 + printf("\n%s:\n", get_entity_name(ent)); + for (i = 0; i < nparams; ++i) { + if (is_Pointer_type(get_method_param_type(mtp, i))) + if (ent->attr.mtd_attr.param_access[i] != ptr_access_none) { + printf(" Pointer Arg %d access: ", i); + if (ent->attr.mtd_attr.param_access[i] & ptr_access_read) + printf("READ "); + if (ent->attr.mtd_attr.param_access[i] & ptr_access_write) + printf("WRITE "); + if (ent->attr.mtd_attr.param_access[i] & ptr_access_store) + printf("STORE "); + printf("\n"); + } + } +#endif } -/* - * Compute for a method with pointer parameter(s) - * if they will be read or written. - */ -ptr_access_kind get_method_param_access(entity *ent, int pos) +void analyze_irg_args(ir_graph *irg) { - type *mtp = get_entity_type(ent); - int is_variadic = get_method_variadicity(mtp) == variadicity_variadic; + ir_entity *ent; - assert(0 <= pos && (is_variadic || pos < get_method_n_params(mtp))); + if (irg == get_const_code_irg()) + return; - if (ent->param_access) { - if (pos < ARR_LEN(ent->param_access)) - return ent->param_access[pos]; - else - return ptr_access_rw; - } + ent = get_irg_entity(irg); + if (! ent) + return; - analyze_ent_args(ent); + if (! ent->attr.mtd_attr.param_access) + analyze_ent_args(ent); +} - if (pos < ARR_LEN(ent->param_access)) - return ent->param_access[pos]; - else - return ptr_access_rw; +ptr_access_kind get_method_param_access(ir_entity *ent, size_t pos) +{ +#ifndef NDEBUG + ir_type *mtp = get_entity_type(ent); + int is_variadic = get_method_variadicity(mtp) == variadicity_variadic; + + assert(is_variadic || pos < get_method_n_params(mtp)); +#endif + + if (ent->attr.mtd_attr.param_access) { + if (pos < ARR_LEN(ent->attr.mtd_attr.param_access)) + return ent->attr.mtd_attr.param_access[pos]; + else + return ptr_access_all; + } + + analyze_ent_args(ent); + + if (pos < ARR_LEN(ent->attr.mtd_attr.param_access)) + return ent->attr.mtd_attr.param_access[pos]; + else + return ptr_access_all; } +/* Weights for parameters */ +enum args_weight { + null_weight = 0, /**< If can't be anything optimized. */ + binop_weight = 1, /**< If the argument have mode_weight and take part in binop. */ + const_binop_weight = 1, /**< If the argument have mode_weight and take part in binop with a constant.*/ + cmp_weight = 4, /**< If the argument take part in cmp. */ + const_cmp_weight = 10, /**< If the argument take part in cmp with a constant. */ + indirect_call_weight = 125, /**< If the argument is the address of an indirect Call. */ +}; + /** - * Analyze how pointer arguments of a given - * ir graph are accessed. + * Compute the weight of a method parameter * - * @param irg The ir graph to analyze. + * @param arg The parameter them weight muss be computed. */ -void analyze_irg_args(ir_graph *irg) +static unsigned calc_method_param_weight(ir_node *arg) { - entity *ent; + int i, j, k; + ir_node *succ, *op; + unsigned weight = null_weight; + + /* We mark the nodes to avoid endless recursion */ + mark_irn_visited(arg); + + for (i = get_irn_n_outs(arg) - 1; i >= 0; i--) { + succ = get_irn_out(arg, i); + + /* We was here.*/ + if (irn_visited(succ)) + continue; + + /* We should not walk over the memory edge.*/ + if (get_irn_mode(succ) == mode_M) + continue; + + switch (get_irn_opcode(succ)) { + case iro_Call: + if (get_Call_ptr(succ) == arg) { + /* the arguments is used as an pointer input for a call, + we can probably change an indirect Call into a direct one. */ + weight += indirect_call_weight; + } + break; + case iro_Cmp: + /* We have reached a cmp and we must increase the + weight with the cmp_weight. */ + if (get_Cmp_left(succ) == arg) + op = get_Cmp_right(succ); + else + op = get_Cmp_left(succ); + + if (is_irn_constlike(op)) { + weight += const_cmp_weight; + } else + weight += cmp_weight; + break; + case iro_Cond: + /* the argument is used for a SwitchCond, a big win */ + weight += const_cmp_weight * get_irn_n_outs(succ); + break; + case iro_Id: + /* when looking backward we might find Id nodes */ + weight += calc_method_param_weight(succ); + break; + case iro_Tuple: + /* unoptimized tuple */ + for (j = get_Tuple_n_preds(succ) - 1; j >= 0; --j) { + ir_node *pred = get_Tuple_pred(succ, j); + if (pred == arg) { + /* look for Proj(j) */ + for (k = get_irn_n_outs(succ) - 1; k >= 0; --k) { + ir_node *succ_succ = get_irn_out(succ, k); + if (is_Proj(succ_succ)) { + if (get_Proj_proj(succ_succ) == j) { + /* found */ + weight += calc_method_param_weight(succ_succ); + } + } else { + /* this should NOT happen */ + } + } + } + } + break; + default: + if (is_binop(succ)) { + /* We have reached a BinOp and we must increase the + weight with the binop_weight. If the other operand of the + BinOp is a constant we increase the weight with const_binop_weight + and call the function recursive. + */ + if (get_binop_left(succ) == arg) + op = get_binop_right(succ); + else + op = get_binop_left(succ); + + if (is_irn_constlike(op)) { + weight += const_binop_weight; + weight += calc_method_param_weight(succ); + } else + weight += binop_weight; + } else if (is_unop(succ)) { + /* We have reached a binop and we must increase the + weight with the const_binop_weight and call the function recursive.*/ + weight += const_binop_weight; + weight += calc_method_param_weight(succ); + } + break; + } + } + set_irn_link(arg, NULL); + return weight; +} - if (irg == get_const_code_irg()) - return; +/** + * Calculate a weight for each argument of an entity. + * + * @param ent The entity of the ir_graph. + */ +static void analyze_method_params_weight(ir_entity *ent) +{ + ir_type *mtp; + ir_graph *irg; + int nparams, i, proj_nr; + ir_node *irg_args, *arg; + + mtp = get_entity_type(ent); + nparams = get_method_n_params(mtp); + + /* allocate a new array. currently used as 'analysed' flag */ + ent->attr.mtd_attr.param_weight = NEW_ARR_F(unsigned, nparams); + + /* If the method haven't parameters we have nothing to do. */ + if (nparams <= 0) + return; + + /* First we initialize the parameter weights with 0. */ + for (i = nparams - 1; i >= 0; i--) + ent->attr.mtd_attr.param_weight[i] = null_weight; + + irg = get_entity_irg(ent); + if (irg == NULL) { + /* no graph, no better info */ + return; + } + + /* Call algorithm that computes the out edges */ + assure_irg_outs(irg); + + irg_args = get_irg_args(irg); + for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) { + arg = get_irn_out(irg_args, i); + proj_nr = get_Proj_proj(arg); + ent->attr.mtd_attr.param_weight[proj_nr] += calc_method_param_weight(arg); + } +} - ent = get_irg_entity(irg); - if (! ent) - return; +unsigned get_method_param_weight(ir_entity *ent, size_t pos) +{ + if (ent->attr.mtd_attr.param_weight) { + if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight)) + return ent->attr.mtd_attr.param_weight[pos]; + else + return null_weight; + } + + analyze_method_params_weight(ent); + + if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight)) + return ent->attr.mtd_attr.param_weight[pos]; + else + return null_weight; +} - if (! ent->param_access) - analyze_ent_args(ent); +void analyze_irg_args_weight(ir_graph *irg) +{ + ir_entity *entity = get_irg_entity(irg); + if (entity == NULL) + return; + + assert(is_method_entity(entity)); + if (entity->attr.mtd_attr.param_weight != NULL) + return; + + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); + inc_irg_visited(irg); + analyze_method_params_weight(entity); + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); }