/*
- * 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 <malloc.h>
-#endif
-#ifdef HAVE_ALLOCA_H
-#include <alloca.h>
-#endif
#include <stdlib.h>
#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);
}
projects / libfirm / blobdiff