diff options
| -rw-r--r-- | gcc/ipa-cp.c | 1143 | ||||
| -rw-r--r-- | gcc/ipa-prop.c | 676 | ||||
| -rw-r--r-- | gcc/ipa-prop.h | 204 |
3 files changed, 2023 insertions, 0 deletions
diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c new file mode 100644 index 0000000..f7dad3f --- /dev/null +++ b/gcc/ipa-cp.c @@ -0,0 +1,1143 @@ +/* Interprocedural constant propagation + Copyright (C) 2005 Free Software Foundation, Inc. + Contributed by Razya Ladelsky <RAZYA@il.ibm.com> + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +/* Interprocedural constant propagation. + The aim of interprocedural constant propagation (IPCP) is to find which + function's argument has the same constant value in each invocation throughout + the whole program. For example, for an application consisting of two files, + foo1.c, foo2.c: + + foo1.c contains : + + int f (int x) + { + g (x); + } + void main (void) + { + f (3); + h (3); + } + + foo2.c contains : + + int h (int y) + { + g (y); + } + int g (int y) + { + printf ("value is %d",y); + } + + The IPCP algorithm will find that g's formal argument y + is always called with the value 3. + + The algorithm used is based on "Interprocedural Constant Propagation", + by Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, + pg 152-161 + + The optimization is divided into three stages: + + First stage - intraprocedural analysis + ======================================= + This phase computes jump_function and modify information. + + A jump function for a callsite represents the values passed as actual + arguments + of the callsite. There are three types of values : + Formal - the caller's formal parameter is passed as an actual argument. + Constant - a constant is passed as a an actual argument. + Unknown - neither of the above. + + In order to compute the jump functions, we need the modify information for + the formal parameters of methods. + + The jump function info, ipa_jump_func, is defined in ipa_edge + structure (defined in ipa_prop.h and pointed to by cgraph_node->aux) + The modify info, ipa_modify, is defined in ipa_node structure + (defined in ipa_prop.h and pointed to by cgraph_edge->aux). + + -ipcp_init_stage() is the first stage driver. + + Second stage - interprocedural analysis + ======================================== + This phase does the interprocedural constant propagation. + It computes for all formal parameters in the program + their cval value that may be: + TOP - unknown. + BOTTOM - non constant. + CONSTANT_TYPE - constant value. + + Cval of formal f will have a constant value if all callsites to this + function have the same constant value passed to f. + + The cval info, ipcp_formal, is defined in ipa_node structure + (defined in ipa_prop.h and pointed to by cgraph_edge->aux). + + -ipcp_iterate_stage() is the second stage driver. + + Third phase - transformation of methods code + ============================================ + Propagates the constant-valued formals into the function. + For each method mt, whose parameters are consts, we create a clone/version. + + We use two ways to annotate the versioned function with the constant + formal information: + 1. We insert an assignment statement 'parameter = const' at the beginning + of the cloned method. + 2. For read-only formals whose address is not taken, we replace all uses + of the formal with the constant (we provide versioning with an + ipa_replace_map struct representing the trees we want to replace). + + We also need to modify some callsites to call to the cloned methods instead + of the original ones. For a callsite passing an argument found to be a + constant by IPCP, there are two different cases to handle: + 1. A constant is passed as an argument. + 2. A parameter (of the caller) passed as an argument (pass through argument). + + In the first case, the callsite in the original caller should be redirected + to call the cloned callee. + In the second case, both the caller and the callee have clones + and the callsite of the cloned caller would be redirected to call to + the cloned callee. + + The callgraph is updated accordingly. + + This update is done in two stages: + First all cloned methods are created during a traversal of the callgraph, + during which all callsites are redirected to call the cloned method. + Then the callsites are traversed and updated as described above. + + -ipcp_insert_stage() is the third phase driver. + +*/ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "target.h" +#include "cgraph.h" +#include "ipa-prop.h" +#include "tree-flow.h" +#include "tree-pass.h" +#include "flags.h" +#include "timevar.h" +#include "diagnostic.h" + +/* Get orig node field of ipa_node associated with method MT. */ +static inline struct cgraph_node * +ipcp_method_orig_node (struct cgraph_node *mt) +{ + return IPA_NODE_REF (mt)->ipcp_orig_node; +} + +/* Return true if NODE is a cloned/versioned method. */ +static inline bool +ipcp_method_is_cloned (struct cgraph_node *node) +{ + return (ipcp_method_orig_node (node) != NULL); +} + +/* Set ORIG_NODE in ipa_node associated with method NODE. */ +static inline void +ipcp_method_set_orig_node (struct cgraph_node *node, + struct cgraph_node *orig_node) +{ + IPA_NODE_REF (node)->ipcp_orig_node = orig_node; +} + +/* Create ipa_node and its data strutures for NEW_NODE. + Set ORIG_NODE as the orig_node field in ipa_node. */ +static void +ipcp_cloned_create (struct cgraph_node *orig_node, + struct cgraph_node *new_node) +{ + ipa_node_create (new_node); + ipcp_method_set_orig_node (new_node, orig_node); + ipa_method_formal_compute_count (new_node); + ipa_method_compute_tree_map (new_node); +} + +/* Return cval_type field of CVAL. */ +static inline enum cvalue_type +ipcp_cval_get_cvalue_type (struct ipcp_formal *cval) +{ + return cval->cval_type; +} + +/* Return scale for MT. */ +static inline gcov_type +ipcp_method_get_scale (struct cgraph_node *mt) +{ + return IPA_NODE_REF (mt)->count_scale; +} + +/* Set COUNT as scale for MT. */ +static inline void +ipcp_method_set_scale (struct cgraph_node *node, gcov_type count) +{ + IPA_NODE_REF (node)->count_scale = count; +} + +/* Set TYPE as cval_type field of CVAL. */ +static inline void +ipcp_cval_set_cvalue_type (struct ipcp_formal *cval, enum cvalue_type type) +{ + cval->cval_type = type; +} + +/* Return cvalue field of CVAL. */ +static inline union parameter_info * +ipcp_cval_get_cvalue (struct ipcp_formal *cval) +{ + return &(cval->cvalue); +} + +/* Set VALUE as cvalue field CVAL. */ +static inline void +ipcp_cval_set_cvalue (struct ipcp_formal *cval, union parameter_info *value, + enum cvalue_type type) +{ + if (type == CONST_VALUE || type == CONST_VALUE_REF) + cval->cvalue.value = value->value; +} + +/* Return whether TYPE is a constant type. */ +static bool +ipcp_type_is_const (enum cvalue_type type) +{ + if (type == CONST_VALUE || type == CONST_VALUE_REF) + return true; + else + return false; +} + +/* Return true if CONST_VAL1 and CONST_VAL2 are equal. */ +static inline bool +ipcp_cval_equal_cvalues (union parameter_info *const_val1, + union parameter_info *const_val2, + enum cvalue_type type1, enum cvalue_type type2) +{ + gcc_assert (ipcp_type_is_const (type1) && ipcp_type_is_const (type2)); + if (type1 != type2) + return false; + + if (operand_equal_p (const_val1->value, const_val2->value, 0)) + return true; + + return false; +} + +/* Compute Meet arithmetics: + Meet (BOTTOM, x) = BOTTOM + Meet (TOP,x) = x + Meet (const_a,const_b) = BOTTOM, if const_a != const_b. + MEET (const_a,const_b) = const_a, if const_a == const_b.*/ +static void +ipcp_cval_meet (struct ipcp_formal *cval, struct ipcp_formal *cval1, + struct ipcp_formal *cval2) +{ + if (ipcp_cval_get_cvalue_type (cval1) == BOTTOM + || ipcp_cval_get_cvalue_type (cval2) == BOTTOM) + { + ipcp_cval_set_cvalue_type (cval, BOTTOM); + return; + } + if (ipcp_cval_get_cvalue_type (cval1) == TOP) + { + ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval2)); + ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval2), + ipcp_cval_get_cvalue_type (cval2)); + return; + } + if (ipcp_cval_get_cvalue_type (cval2) == TOP) + { + ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval1)); + ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval1), + ipcp_cval_get_cvalue_type (cval1)); + return; + } + if (!ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1), + ipcp_cval_get_cvalue (cval2), + ipcp_cval_get_cvalue_type (cval1), + ipcp_cval_get_cvalue_type (cval2))) + { + ipcp_cval_set_cvalue_type (cval, BOTTOM); + return; + } + ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval1)); + ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval1), + ipcp_cval_get_cvalue_type (cval1)); +} + +/* Return cval structure for the formal at index INFO_TYPE in MT. */ +static inline struct ipcp_formal * +ipcp_method_cval (struct cgraph_node *mt, int info_type) +{ + return &(IPA_NODE_REF (mt)->ipcp_cval[info_type]); +} + +/* Given the jump function (TYPE, INFO_TYPE), compute a new value of CVAL. + If TYPE is FORMAL_IPA_TYPE, the cval of the corresponding formal is + drawn from MT. */ +static void +ipcp_cval_compute (struct ipcp_formal *cval, struct cgraph_node *mt, + enum jump_func_type type, union parameter_info *info_type) +{ + if (type == UNKNOWN_IPATYPE) + ipcp_cval_set_cvalue_type (cval, BOTTOM); + else if (type == CONST_IPATYPE) + { + ipcp_cval_set_cvalue_type (cval, CONST_VALUE); + ipcp_cval_set_cvalue (cval, info_type, CONST_VALUE); + } + else if (type == CONST_IPATYPE_REF) + { + ipcp_cval_set_cvalue_type (cval, CONST_VALUE_REF); + ipcp_cval_set_cvalue (cval, info_type, CONST_VALUE_REF); + } + else if (type == FORMAL_IPATYPE) + { + enum cvalue_type type = + ipcp_cval_get_cvalue_type (ipcp_method_cval + (mt, info_type->formal_id)); + ipcp_cval_set_cvalue_type (cval, type); + ipcp_cval_set_cvalue (cval, + ipcp_cval_get_cvalue (ipcp_method_cval + (mt, info_type->formal_id)), + type); + } +} + +/* True when CVAL1 and CVAL2 values are not the same. */ +static bool +ipcp_cval_changed (struct ipcp_formal *cval1, struct ipcp_formal *cval2) +{ + if (ipcp_cval_get_cvalue_type (cval1) == ipcp_cval_get_cvalue_type (cval2)) + { + if (ipcp_cval_get_cvalue_type (cval1) != CONST_VALUE && + ipcp_cval_get_cvalue_type (cval1) != CONST_VALUE_REF) + return false; + if (ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1), + ipcp_cval_get_cvalue (cval2), + ipcp_cval_get_cvalue_type (cval1), + ipcp_cval_get_cvalue_type (cval2))) + return false; + } + return true; +} + +/* Create cval structure for method MT. */ +static inline void +ipcp_formal_create (struct cgraph_node *mt) +{ + IPA_NODE_REF (mt)->ipcp_cval = + xcalloc (ipa_method_formal_count (mt), sizeof (struct ipcp_formal)); +} + +/* Set cval structure of I-th formal of MT to CVAL. */ +static inline void +ipcp_method_cval_set (struct cgraph_node *mt, int i, struct ipcp_formal *cval) +{ + IPA_NODE_REF (mt)->ipcp_cval[i].cval_type = cval->cval_type; + ipcp_cval_set_cvalue (ipcp_method_cval (mt, i), + ipcp_cval_get_cvalue (cval), cval->cval_type); +} + +/* Set type of cval structure of formal I of MT to CVAL_TYPE1. */ +static inline void +ipcp_method_cval_set_cvalue_type (struct cgraph_node *mt, int i, + enum cvalue_type cval_type1) +{ + IPA_NODE_REF (mt)->ipcp_cval[i].cval_type = cval_type1; +} + +/* Print ipcp_cval data structures to F. */ +static void +ipcp_method_cval_print (FILE * f) +{ + struct cgraph_node *node; + int i, count; + tree cvalue; + + fprintf (f, "\nCVAL PRINT\n"); + for (node = cgraph_nodes; node; node = node->next) + { + fprintf (f, "Printing cvals %s:\n", cgraph_node_name (node)); + count = ipa_method_formal_count (node); + for (i = 0; i < count; i++) + { + if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) + == CONST_VALUE + || ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) == + CONST_VALUE_REF) + { + fprintf (f, " param [%d]: ", i); + fprintf (f, "type is CONST "); + cvalue = + ipcp_cval_get_cvalue (ipcp_method_cval (node, i))-> + value; + print_generic_expr (f, cvalue, 0); + fprintf (f, "\n"); + } + else if (ipcp_method_cval (node, i)->cval_type == TOP) + fprintf (f, "param [%d]: type is TOP \n", i); + else + fprintf (f, "param [%d]: type is BOTTOM \n", i); + } + } +} + +/* Initialize ipcp_cval array of MT with TOP values. + All cvals for a method's formal parameters are initialized to BOTTOM + The currently supported types are integer types, real types and + Fortran constants (i.e. references to constants defined as + const_decls). All other types are not analyzed and therefore are + assigned with BOTTOM. */ +static void +ipcp_method_cval_init (struct cgraph_node *mt) +{ + int i; + tree parm_tree; + + ipcp_formal_create (mt); + for (i = 0; i < ipa_method_formal_count (mt); i++) + { + parm_tree = ipa_method_get_tree (mt, i); + if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree)) + || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree)) + || POINTER_TYPE_P (TREE_TYPE (parm_tree))) + ipcp_method_cval_set_cvalue_type (mt, i, TOP); + else + ipcp_method_cval_set_cvalue_type (mt, i, BOTTOM); + } +} + +/* Create a new assignment statment and make + it the first statemant in the function FN + tree. + PARM1 is the lhs of the assignment and + VAL is the rhs. */ +static void +constant_val_insert (tree fn, tree parm1, tree val) +{ + struct function *func; + tree init_stmt; + edge e_step; + edge_iterator ei; + + init_stmt = build2 (MODIFY_EXPR, void_type_node, parm1, val); + func = DECL_STRUCT_FUNCTION (fn); + cfun = func; + current_function_decl = fn; + if (ENTRY_BLOCK_PTR_FOR_FUNCTION (func)->succs) + FOR_EACH_EDGE (e_step, ei, ENTRY_BLOCK_PTR_FOR_FUNCTION (func)->succs) + bsi_insert_on_edge_immediate (e_step, init_stmt); +} + +/* build INTEGER_CST tree with type TREE_TYPE and + value according to CVALUE. Return the tree. */ +static tree +build_const_val (union parameter_info *cvalue, enum cvalue_type type, + tree tree_type) +{ + tree const_val = NULL; + + gcc_assert (ipcp_type_is_const (type)); + const_val = fold_convert (tree_type, cvalue->value); + return const_val; +} + +/* Build the tree representing the constant and call + constant_val_insert(). */ +static void +ipcp_propagate_const (struct cgraph_node *mt, int param, + union parameter_info *cvalue ,enum cvalue_type type) +{ + tree fndecl; + tree const_val; + tree parm_tree; + + if (dump_file) + fprintf (dump_file, "propagating const to %s\n", cgraph_node_name (mt)); + fndecl = mt->decl; + parm_tree = ipa_method_get_tree (mt, param); + const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree)); + constant_val_insert (fndecl, parm_tree, const_val); +} + +/* Compute the proper scale for NODE. It is the ratio between + the number of direct calls (represented on the incoming + cgraph_edges) and sum of all invocations of NODE (represented + as count in cgraph_node). */ +static void +ipcp_method_compute_scale (struct cgraph_node *node) +{ + gcov_type sum; + struct cgraph_edge *cs; + + sum = 0; + /* Compute sum of all counts of callers. */ + for (cs = node->callers; cs != NULL; cs = cs->next_caller) + sum += cs->count; + if (node->count == 0) + ipcp_method_set_scale (node, 0); + else + ipcp_method_set_scale (node, sum * REG_BR_PROB_BASE / node->count); +} + +/* Initialization and computation of IPCP data structures. + It is an intraprocedural + analysis of methods, which gathers information to be propagated + later on. */ +static void +ipcp_init_stage (void) +{ + struct cgraph_node *node; + struct cgraph_edge *cs; + + for (node = cgraph_nodes; node; node = node->next) + { + ipa_method_formal_compute_count (node); + ipa_method_compute_tree_map (node); + ipcp_method_cval_init (node); + ipa_method_compute_modify (node); + ipcp_method_compute_scale (node); + } + for (node = cgraph_nodes; node; node = node->next) + { + /* building jump functions */ + for (cs = node->callees; cs; cs = cs->next_callee) + { + ipa_callsite_compute_count (cs); + if (ipa_callsite_param_count (cs) + != ipa_method_formal_count (cs->callee)) + { + /* Handle cases of functions with + a variable number of parameters. */ + ipa_callsite_param_count_set (cs, 0); + ipa_method_formal_count_set (cs->callee, 0); + } + else + ipa_callsite_compute_param (cs); + } + } +} + +/* Return true if there are some formal parameters whose value is TOP. + Change their values to BOTTOM, since they weren't determined. */ +static bool +ipcp_after_propagate (void) +{ + int i, count; + struct cgraph_node *node; + bool prop_again; + + prop_again = false; + for (node = cgraph_nodes; node; node = node->next) + { + count = ipa_method_formal_count (node); + for (i = 0; i < count; i++) + if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) == TOP) + { + prop_again = true; + ipcp_method_cval_set_cvalue_type (node, i, BOTTOM); + } + } + return prop_again; +} + +/* Interprocedural analysis. The algorithm propagates constants from + the caller's parameters to the callee's arguments. */ +static void +ipcp_propagate_stage (void) +{ + int i; + struct ipcp_formal cval1 = { 0, {0} }, cval = { 0,{0} }; + struct ipcp_formal *cval2; + struct cgraph_node *mt, *callee; + struct cgraph_edge *cs; + struct ipa_jump_func *jump_func; + enum jump_func_type type; + union parameter_info *info_type; + ipa_methodlist_p wl; + int count; + + /* Initialize worklist to contain all methods. */ + wl = ipa_methodlist_init (); + while (ipa_methodlist_not_empty (wl)) + { + mt = ipa_remove_method (&wl); + for (cs = mt->callees; cs; cs = cs->next_callee) + { + callee = ipa_callsite_callee (cs); + count = ipa_callsite_param_count (cs); + for (i = 0; i < count; i++) + { + jump_func = ipa_callsite_param (cs, i); + type = get_type (jump_func); + info_type = ipa_jf_get_info_type (jump_func); + ipcp_cval_compute (&cval1, mt, type, info_type); + cval2 = ipcp_method_cval (callee, i); + ipcp_cval_meet (&cval, &cval1, cval2); + if (ipcp_cval_changed (&cval, cval2)) + { + ipcp_method_cval_set (callee, i, &cval); + ipa_add_method (&wl, callee); + } + } + } + } +} + +/* Call the constant propagation algorithm and re-call it if necessary + (if there are undetermined values left). */ +static void +ipcp_iterate_stage (void) +{ + ipcp_propagate_stage (); + if (ipcp_after_propagate ()) + /* Some cvals have changed from TOP to BOTTOM. + This change should be propagated. */ + ipcp_propagate_stage (); +} + +/* Check conditions to forbid constant insertion to MT. */ +static bool +ipcp_method_dont_insert_const (struct cgraph_node *mt) +{ + /* ??? Handle pending sizes case. */ + if (DECL_UNINLINABLE (mt->decl)) + return true; + return false; +} + +/* Print ipa_jump_func data structures to F. */ +static void +ipcp_callsite_param_print (FILE * f) +{ + struct cgraph_node *node; + int i, count; + struct cgraph_edge *cs; + struct ipa_jump_func *jump_func; + enum jump_func_type type; + tree info_type; + + fprintf (f, "\nCALLSITE PARAM PRINT\n"); + for (node = cgraph_nodes; node; node = node->next) + { + for (cs = node->callees; cs; cs = cs->next_callee) + { + fprintf (f, "callsite %s ", cgraph_node_name (node)); + fprintf (f, "-> %s :: \n", cgraph_node_name (cs->callee)); + count = ipa_callsite_param_count (cs); + for (i = 0; i < count; i++) + { + jump_func = ipa_callsite_param (cs, i); + type = get_type (jump_func); + + fprintf (f, " param %d: ", i); + if (type == UNKNOWN_IPATYPE) + fprintf (f, "UNKNOWN\n"); + else if (type == CONST_IPATYPE || type == CONST_IPATYPE_REF) + { + info_type = + ipa_jf_get_info_type (jump_func)->value; + fprintf (f, "CONST : "); + print_generic_expr (f, info_type, 0); + fprintf (f, "\n"); + } + else if (type == FORMAL_IPATYPE) + { + fprintf (f, "FORMAL : "); + fprintf (f, "%d\n", + ipa_jf_get_info_type (jump_func)->formal_id); + } + } + } + } +} + +/* Print count scale data structures. */ +static void +ipcp_method_scale_print (FILE * f) +{ + struct cgraph_node *node; + + for (node = cgraph_nodes; node; node = node->next) + { + fprintf (f, "printing scale for %s: ", cgraph_node_name (node)); + fprintf (f, "value is " HOST_WIDE_INT_PRINT_DEC + " \n", (HOST_WIDE_INT) ipcp_method_get_scale (node)); + } +} + +/* Print counts of all cgraph nodes. */ +static void +ipcp_profile_mt_count_print (FILE * f) +{ + struct cgraph_node *node; + + for (node = cgraph_nodes; node; node = node->next) + { + fprintf (f, "method %s: ", cgraph_node_name (node)); + fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC + " \n", (HOST_WIDE_INT) node->count); + } +} + +/* Print counts of all cgraph edgess. */ +static void +ipcp_profile_cs_count_print (FILE * f) +{ + struct cgraph_node *node; + struct cgraph_edge *cs; + + for (node = cgraph_nodes; node; node = node->next) + { + for (cs = node->callees; cs; cs = cs->next_callee) + { + fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller), + cgraph_node_name (cs->callee)); + fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC " \n", + (HOST_WIDE_INT) cs->count); + } + } +} + +/* Print all counts and probabilities of cfg edges of all methods. */ +static void +ipcp_profile_edge_print (FILE * f) +{ + struct cgraph_node *node; + basic_block bb; + edge_iterator ei; + edge e; + + for (node = cgraph_nodes; node; node = node->next) + { + fprintf (f, "method %s: \n", cgraph_node_name (node)); + if (DECL_SAVED_TREE (node->decl)) + { + bb = + ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl)); + fprintf (f, "ENTRY: "); + fprintf (f, " " HOST_WIDE_INT_PRINT_DEC + " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency); + + if (bb->succs) + FOR_EACH_EDGE (e, ei, bb->succs) + { + if (e->dest == + EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION + (node->decl))) + fprintf (f, "edge ENTRY -> EXIT, Count"); + else + fprintf (f, "edge ENTRY -> %d, Count", e->dest->index); + fprintf (f, " " HOST_WIDE_INT_PRINT_DEC + " Prob %d\n", (HOST_WIDE_INT) e->count, + e->probability); + } + FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl)) + { + fprintf (f, "bb[%d]: ", bb->index); + fprintf (f, " " HOST_WIDE_INT_PRINT_DEC + " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency); + FOR_EACH_EDGE (e, ei, bb->succs) + { + if (e->dest == + EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION + (node->decl))) + fprintf (f, "edge %d -> EXIT, Count", e->src->index); + else + fprintf (f, "edge %d -> %d, Count", e->src->index, + e->dest->index); + fprintf (f, " " HOST_WIDE_INT_PRINT_DEC " Prob %d\n", + (HOST_WIDE_INT) e->count, e->probability); + } + } + } + } +} + +/* Print counts and frequencies for all basic blocks of all methods. */ +static void +ipcp_profile_bb_print (FILE * f) +{ + basic_block bb; + struct cgraph_node *node; + + for (node = cgraph_nodes; node; node = node->next) + { + fprintf (f, "method %s: \n", cgraph_node_name (node)); + if (DECL_SAVED_TREE (node->decl)) + { + bb = + ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl)); + fprintf (f, "ENTRY: Count"); + fprintf (f, " " HOST_WIDE_INT_PRINT_DEC + " Frquency %d\n", (HOST_WIDE_INT) bb->count, + bb->frequency); + + FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl)) + { + fprintf (f, "bb[%d]: Count", bb->index); + fprintf (f, " " HOST_WIDE_INT_PRINT_DEC + " Frequency %d\n", (HOST_WIDE_INT) bb->count, + bb->frequency); + } + bb = + EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl)); + fprintf (f, "EXIT: Count"); + fprintf (f, " " HOST_WIDE_INT_PRINT_DEC + " Frequency %d\n", (HOST_WIDE_INT) bb->count, + bb->frequency); + + } + } +} + +/* Print all IPCP data structures to F. */ +static void +ipcp_structures_print (FILE * f) +{ + ipcp_method_cval_print (f); + ipcp_method_scale_print (f); + ipa_method_tree_print (f); + ipa_method_modify_print (f); + ipcp_callsite_param_print (f); +} + +/* Print profile info for all methods. */ +static void +ipcp_profile_print (FILE * f) +{ + fprintf (f, "\nNODE COUNTS :\n"); + ipcp_profile_mt_count_print (f); + fprintf (f, "\nCS COUNTS stage:\n"); + ipcp_profile_cs_count_print (f); + fprintf (f, "\nBB COUNTS and FREQUENCIES :\n"); + ipcp_profile_bb_print (f); + fprintf (f, "\nCFG EDGES COUNTS and PROBABILITIES :\n"); + ipcp_profile_edge_print (f); +} + +/* Build and initialize ipa_replace_map struct + according to TYPE. This struct is read by versioning, which + operates according to the flags sent. PARM_TREE is the + formal's tree found to be constant. CVALUE represents the constant. */ +static struct ipa_replace_map * +ipcp_replace_map_create (enum cvalue_type type, tree parm_tree, + union parameter_info *cvalue) +{ + struct ipa_replace_map *replace_map; + tree const_val; + + replace_map = xcalloc (1, sizeof (struct ipa_replace_map)); + gcc_assert (ipcp_type_is_const (type)); + if (type == CONST_VALUE_REF ) + { + const_val = + build_const_val (cvalue, type, TREE_TYPE (TREE_TYPE (parm_tree))); + replace_map->old_tree = parm_tree; + replace_map->new_tree = const_val; + replace_map->replace_p = true; + replace_map->ref_p = true; + } + else if (TREE_READONLY (parm_tree) && !TREE_ADDRESSABLE (parm_tree)) + { + const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree)); + replace_map->old_tree = parm_tree; + replace_map->new_tree = const_val; + replace_map->replace_p = true; + replace_map->ref_p = false; + } + else + { + replace_map->old_tree = NULL; + replace_map->new_tree = NULL; + replace_map->replace_p = false; + replace_map->ref_p = false; + } + + return replace_map; +} + +/* Return true if this callsite should be redirected to + the orig callee (instead of the cloned one). */ +static bool +ipcp_redirect (struct cgraph_edge *cs) +{ + struct cgraph_node *caller, *callee, *orig_callee; + int i, count; + struct ipa_jump_func *jump_func; + enum jump_func_type type; + enum cvalue_type cval_type; + + caller = cs->caller; + callee = cs->callee; + orig_callee = ipcp_method_orig_node (callee); + count = ipa_method_formal_count (orig_callee); + for (i = 0; i < count; i++) + { + cval_type = + ipcp_cval_get_cvalue_type (ipcp_method_cval (orig_callee, i)); + if (ipcp_type_is_const (cval_type)) + { + jump_func = ipa_callsite_param (cs, i); + type = get_type (jump_func); + if (type != CONST_IPATYPE + && type != CONST_IPATYPE_REF) + return true; + } + } + + return false; +} + +/* Fix the callsites and the callgraph after function cloning was done. */ +static void +ipcp_update_callgraph (void) +{ + struct cgraph_node *node, *orig_callee; + struct cgraph_edge *cs; + + for (node = cgraph_nodes; node; node = node->next) + { + /* want to fix only original nodes */ + if (ipcp_method_is_cloned (node)) + continue; + for (cs = node->callees; cs; cs = cs->next_callee) + if (ipcp_method_is_cloned (cs->callee)) + { + /* Callee is a cloned node */ + orig_callee = ipcp_method_orig_node (cs->callee); + if (ipcp_redirect (cs)) + { + cgraph_redirect_edge_callee (cs, orig_callee); + TREE_OPERAND (TREE_OPERAND + (get_call_expr_in (cs->call_stmt), 0), 0) = + orig_callee->decl; + } + } + } +} + +/* Update all cfg basic blocks in NODE according to SCALE. */ +static void +ipcp_update_bb_counts (struct cgraph_node *node, gcov_type scale) +{ + basic_block bb; + + FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl)) + bb->count = bb->count * scale / REG_BR_PROB_BASE; +} + +/* Update all cfg edges in NODE according to SCALE. */ +static void +ipcp_update_edges_counts (struct cgraph_node *node, gcov_type scale) +{ + basic_block bb; + edge_iterator ei; + edge e; + + FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl)) + FOR_EACH_EDGE (e, ei, bb->succs) + e->count = e->count * scale / REG_BR_PROB_BASE; +} + +/* Update profiling info for versioned methods and the + methods they were versioned from. */ +static void +ipcp_update_profiling (void) +{ + struct cgraph_node *node, *orig_node; + gcov_type scale, scale_complement; + struct cgraph_edge *cs; + + for (node = cgraph_nodes; node; node = node->next) + { + if (ipcp_method_is_cloned (node)) + { + orig_node = ipcp_method_orig_node (node); + scale = ipcp_method_get_scale (orig_node); + node->count = orig_node->count * scale / REG_BR_PROB_BASE; + scale_complement = REG_BR_PROB_BASE - scale; + orig_node->count = + orig_node->count * scale_complement / REG_BR_PROB_BASE; + for (cs = node->callees; cs; cs = cs->next_callee) + cs->count = cs->count * scale / REG_BR_PROB_BASE; + for (cs = orig_node->callees; cs; cs = cs->next_callee) + cs->count = cs->count * scale_complement / REG_BR_PROB_BASE; + ipcp_update_bb_counts (node, scale); + ipcp_update_bb_counts (orig_node, scale_complement); + ipcp_update_edges_counts (node, scale); + ipcp_update_edges_counts (orig_node, scale_complement); + } + } +} + +/* Propagate the constant parameters found by ipcp_iterate_stage() + to the function's code. */ +static void +ipcp_insert_stage (void) +{ + struct cgraph_node *node, *node1 = NULL; + int i, const_param; + union parameter_info *cvalue; + varray_type redirect_callers, replace_trees; + struct cgraph_edge *cs; + int node_callers, count; + tree parm_tree; + enum cvalue_type type; + struct ipa_replace_map *replace_param; + + for (node = cgraph_nodes; node; node = node->next) + { + /* Propagation of the constant is forbidden in + certain conditions. */ + if (ipcp_method_dont_insert_const (node)) + continue; + const_param = 0; + count = ipa_method_formal_count (node); + for (i = 0; i < count; i++) + { + type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)); + if (ipcp_type_is_const (type)) + const_param++; + } + if (const_param == 0) + continue; + VARRAY_GENERIC_PTR_INIT (replace_trees, const_param, "replace_trees"); + for (i = 0; i < count; i++) + { + type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)); + if (ipcp_type_is_const (type)) + { + cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i)); + parm_tree = ipa_method_get_tree (node, i); + replace_param = + ipcp_replace_map_create (type, parm_tree, cvalue); + VARRAY_PUSH_GENERIC_PTR (replace_trees, replace_param); + } + } + /* Compute how many callers node has. */ + node_callers = 0; + for (cs = node->callers; cs != NULL; cs = cs->next_caller) + node_callers++; + VARRAY_GENERIC_PTR_INIT (redirect_callers, node_callers, + "redirect_callers"); + for (cs = node->callers; cs != NULL; cs = cs->next_caller) + VARRAY_PUSH_GENERIC_PTR (redirect_callers, cs); + /* Redirecting all the callers of the node to the + new versioned node. */ + node1 = + cgraph_function_versioning (node, redirect_callers, replace_trees); + VARRAY_CLEAR (redirect_callers); + VARRAY_CLEAR (replace_trees); + if (node1 == NULL) + continue; + if (dump_file) + fprintf (dump_file, "versioned function %s\n", + cgraph_node_name (node)); + ipcp_cloned_create (node, node1); + for (i = 0; i < count; i++) + { + type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)); + if (ipcp_type_is_const (type)) + { + cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i)); + parm_tree = ipa_method_get_tree (node, i); + if (type != CONST_VALUE_REF + && !TREE_READONLY (parm_tree)) + ipcp_propagate_const (node1, i, cvalue, type); + } + } + } + ipcp_update_callgraph (); + ipcp_update_profiling (); +} + +/* The IPCP driver. */ +void +ipcp_driver (void) +{ + if (dump_file) + fprintf (dump_file, "\nIPA constant propagation start:\n"); + ipa_nodes_create (); + ipa_edges_create (); + /* 1. Call the init stage to initialize + the ipa_node and ipa_edge structures. */ + ipcp_init_stage (); + if (dump_file) + { + fprintf (dump_file, "\nIPA structures before propagation:\n"); + ipcp_structures_print (dump_file); + } + /* 2. Do the interprocedural propagation. */ + ipcp_iterate_stage (); + if (dump_file) + { + fprintf (dump_file, "\nIPA structures after propagation:\n"); + ipcp_structures_print (dump_file); + fprintf (dump_file, "\nProfiling info before insert stage:\n"); + ipcp_profile_print (dump_file); + } + /* 3. Insert the constants found to the functions. */ + ipcp_insert_stage (); + if (dump_file) + { + fprintf (dump_file, "\nProfiling info after insert stage:\n"); + ipcp_profile_print (dump_file); + } + /* Free all IPCP structures. */ + ipa_free (); + ipa_nodes_free (); + ipa_edges_free (); + if (dump_file) + fprintf (dump_file, "\nIPA constant propagation end\n"); + cgraph_remove_unreachable_nodes (true, NULL); +} + +/* Gate for IPCP optimization. */ +static bool +cgraph_gate_cp (void) +{ + return flag_ipa_cp; +} + +struct tree_opt_pass pass_ipa_cp = { + "cp", /* name */ + cgraph_gate_cp, /* gate */ + ipcp_driver, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_IPA_CONSTANT_PROP, /* tv_id */ + 0, /* properties_required */ + PROP_trees, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */ + 0 /* letter */ +}; diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c new file mode 100644 index 0000000..cdbf94b --- /dev/null +++ b/gcc/ipa-prop.c @@ -0,0 +1,676 @@ +/* Interprocedural analyses. + Copyright (C) 2005 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "langhooks.h" +#include "ggc.h" +#include "target.h" +#include "cgraph.h" +#include "ipa-prop.h" +#include "tree-flow.h" +#include "tree-pass.h" +#include "flags.h" +#include "timevar.h" + +/* This file contains interfaces that can be used for various IPA + optimizations: + + - ipa_methodlist interface - It is used to create and handle a temporary + worklist used in the propagation stage of IPCP. (can be used for more + IPA optimizations). + + - ipa_callsite interface - for each callsite this interface creates and + handles ipa_edge structure associated with it. + + - ipa_method interface - for each method this interface creates and + handles ipa_node structure associated with it. */ + +/* ipa_methodlist interface. */ + +/* Create a new worklist node. */ +static inline ipa_methodlist_p +ipa_create_methodlist_node (void) +{ + return (ipa_methodlist_p) xcalloc (1, sizeof (struct ipa_methodlist)); +} + +/* Return true if worklist WL is empty. */ +bool +ipa_methodlist_not_empty (ipa_methodlist_p wl) +{ + return (wl != NULL); +} + +/* Return the method in worklist element WL. */ +static inline struct cgraph_node * +ipa_methodlist_method (ipa_methodlist_p wl) +{ + return wl->method_p; +} + +/* Make worklist element WL point to method MT in the callgraph. */ +static inline void +ipa_methodlist_method_set (ipa_methodlist_p wl, struct cgraph_node *mt) +{ + wl->method_p = mt; +} + +/* Return the next element in the worklist following worklist + element WL. */ +static inline ipa_methodlist_p +ipa_methodlist_next_method (ipa_methodlist_p wl) +{ + return wl->next_method; +} + +/* Set worklist element WL1 to point to worklist element WL2. */ +static inline void +ipa_methodlist_next_method_set (ipa_methodlist_p wl1, ipa_methodlist_p wl2) +{ + wl1->next_method = wl2; +} + +/* Initialize worklist to contain all methods. */ +ipa_methodlist_p +ipa_methodlist_init (void) +{ + struct cgraph_node *node; + ipa_methodlist_p wl; + + wl = NULL; + for (node = cgraph_nodes; node; node = node->next) + ipa_add_method (&wl, node); + + return wl; +} + +/* Add method MT to the worklist. Set worklist element WL + to point to MT. */ +void +ipa_add_method (ipa_methodlist_p * wl, struct cgraph_node *mt) +{ + ipa_methodlist_p temp; + + temp = ipa_create_methodlist_node (); + ipa_methodlist_method_set (temp, mt); + ipa_methodlist_next_method_set (temp, *wl); + *wl = temp; +} + +/* Remove a method from the worklist. WL points to the first + element in the list, which is removed. */ +struct cgraph_node * +ipa_remove_method (ipa_methodlist_p * wl) +{ + ipa_methodlist_p first; + struct cgraph_node *return_method; + + first = *wl; + *wl = ipa_methodlist_next_method (*wl); + return_method = ipa_methodlist_method (first); + free (first); + return return_method; +} + +/* ipa_method interface. */ + +/* Return number of formals of method MT. */ +int +ipa_method_formal_count (struct cgraph_node *mt) +{ + return IPA_NODE_REF (mt)->ipa_arg_num; +} + +/* Set number of formals of method MT to I. */ +void +ipa_method_formal_count_set (struct cgraph_node *mt, int i) +{ + IPA_NODE_REF (mt)->ipa_arg_num = i; +} + +/* Return whether I-th formal of MT is modified in MT. */ +static inline bool +ipa_method_is_modified (struct cgraph_node *mt, int i) +{ + return IPA_NODE_REF (mt)->ipa_mod[i]; +} + +/* Return the tree of I-th formal of MT. */ +tree +ipa_method_get_tree (struct cgraph_node *mt, int i) +{ + return IPA_NODE_REF (mt)->ipa_param_tree[i]; +} + +/* Create tree map structure for MT. */ +static inline void +ipa_method_tree_map_create (struct cgraph_node *mt) +{ + IPA_NODE_REF (mt)->ipa_param_tree = + xcalloc (ipa_method_formal_count (mt), sizeof (tree)); +} + +/* Create modify structure for MT. */ +static inline void +ipa_method_modify_create (struct cgraph_node *mt) +{ + ((struct ipa_node *) mt->aux)->ipa_mod = + xcalloc (ipa_method_formal_count (mt), sizeof (bool)); +} + +/* Set modify of I-th formal of MT to VAL. */ +static inline void +ipa_method_modify_set (struct cgraph_node *mt, int i, bool val) +{ + IPA_NODE_REF (mt)->ipa_mod[i] = val; +} + +/* Return index of the formal whose tree is PTREE in method MT. */ +static int +ipa_method_tree_map (struct cgraph_node *mt, tree ptree) +{ + int i, count; + + count = ipa_method_formal_count (mt); + for (i = 0; i < count; i++) + if (IPA_NODE_REF (mt)->ipa_param_tree[i] == ptree) + return i; + + return -1; +} + +/* Insert the formal trees to the ipa_param_tree array in method MT. */ +void +ipa_method_compute_tree_map (struct cgraph_node *mt) +{ + tree fndecl; + tree fnargs; + tree parm; + int param_num; + + ipa_method_tree_map_create (mt); + fndecl = mt->decl; + fnargs = DECL_ARGUMENTS (fndecl); + param_num = 0; + for (parm = fnargs; parm; parm = TREE_CHAIN (parm)) + { + IPA_NODE_REF (mt)->ipa_param_tree[param_num] = parm; + param_num++; + } +} + +/* Count number of formals in MT. Insert the result to the + ipa_node. */ +void +ipa_method_formal_compute_count (struct cgraph_node *mt) +{ + tree fndecl; + tree fnargs; + tree parm; + int param_num; + + fndecl = mt->decl; + fnargs = DECL_ARGUMENTS (fndecl); + param_num = 0; + for (parm = fnargs; parm; parm = TREE_CHAIN (parm)) + param_num++; + ipa_method_formal_count_set (mt, param_num); +} + +/* Check STMT to detect whether a formal is modified within MT, + the appropriate entry is updated in the ipa_mod array of ipa_node + (associated with MT). */ +static void +ipa_method_modify_stmt (struct cgraph_node *mt, tree stmt) +{ + int i, j; + + switch (TREE_CODE (stmt)) + { + case MODIFY_EXPR: + if (TREE_CODE (TREE_OPERAND (stmt, 0)) == PARM_DECL) + { + i = ipa_method_tree_map (mt, TREE_OPERAND (stmt, 0)); + if (i >= 0) + ipa_method_modify_set (mt, i, true); + } + break; + case ASM_EXPR: + /* Asm code could modify any of the parameters. */ + for (j = 0; j < ipa_method_formal_count (mt); j++) + ipa_method_modify_set (mt, j, true); + break; + default: + break; + } +} + +/* Initialize ipa_mod array of MT. */ +static void +ipa_method_modify_init (struct cgraph_node *mt) +{ + int i, count; + + ipa_method_modify_create (mt); + count = ipa_method_formal_count (mt); + for (i = 0; i < count; i++) + ipa_method_modify_set (mt, i, false); +} + +/* The modify computation driver for MT. Compute which formal arguments + of method MT are locally modified. Formals may be modified in MT + if their address is taken, or if + they appear on the left hand side of an assignment. */ +void +ipa_method_compute_modify (struct cgraph_node *mt) +{ + tree decl; + tree body; + int j, count; + basic_block bb; + struct function *func; + block_stmt_iterator bsi; + tree stmt, parm_tree; + + ipa_method_modify_init (mt); + decl = mt->decl; + count = ipa_method_formal_count (mt); + /* ??? Handle pending sizes case. Set all parameters + of the method to be modified. */ + if (DECL_UNINLINABLE (decl)) + { + for (j = 0; j < count; j++) + ipa_method_modify_set (mt, j, true); + return; + } + /* Formals whose address is taken are considered modified. */ + for (j = 0; j < count; j++) + { + parm_tree = ipa_method_get_tree (mt, j); + if (TREE_ADDRESSABLE (parm_tree)) + ipa_method_modify_set (mt, j, true); + } + body = DECL_SAVED_TREE (decl); + if (body != NULL) + { + func = DECL_STRUCT_FUNCTION (decl); + FOR_EACH_BB_FN (bb, func) + { + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + { + stmt = bsi_stmt (bsi); + ipa_method_modify_stmt (mt, stmt); + } + } + } +} + + +/* ipa_callsite interface. */ + +/* Return number of arguments in callsite CS. */ +int +ipa_callsite_param_count (struct cgraph_edge *cs) +{ + return IPA_EDGE_REF (cs)->ipa_param_num; +} + +/* Set number of arguments in callsite CS to I. */ +void +ipa_callsite_param_count_set (struct cgraph_edge *cs, int i) +{ + IPA_EDGE_REF (cs)->ipa_param_num = i; +} + +/* Return the jump function (ipa_jump_func struct) for argument I of + callsite CS. */ +struct ipa_jump_func * +ipa_callsite_param (struct cgraph_edge *cs, int i) +{ + return &(IPA_EDGE_REF (cs)->ipa_param_map[i]); +} + +/* return the callee (cgraph_node) of callsite CS. */ +struct cgraph_node * +ipa_callsite_callee (struct cgraph_edge *cs) +{ + return cs->callee; +} + +/* Set field 'type' of jump function (ipa_jump_func struct) of argument I + in callsite CS. */ +static inline void +ipa_callsite_param_set_type (struct cgraph_edge *cs, int i, + enum jump_func_type type1) +{ + IPA_EDGE_REF (cs)->ipa_param_map[i].type = type1; +} + +/* Set FORMAL as 'info_type' field of jump function (ipa_jump_func struct) + of argument I of callsite CS. */ +static inline void +ipa_callsite_param_set_info_type_formal (struct cgraph_edge *cs, int i, + unsigned int formal) +{ + ipa_callsite_param (cs, i)->info_type.formal_id = formal; +} + +/* Set int-valued INFO_TYPE1 as 'info_type' field of + jump function (ipa_jump_func struct) of argument I of callsite CS. */ +static inline void +ipa_callsite_param_set_info_type (struct cgraph_edge *cs, int i, tree info_type1) +{ + ipa_callsite_param (cs, i)->info_type.value = info_type1; +} + +/* Allocate space for callsite CS. */ +static inline void +ipa_callsite_param_map_create (struct cgraph_edge *cs) +{ + IPA_EDGE_REF (cs)->ipa_param_map = + xcalloc (ipa_callsite_param_count (cs), sizeof (struct ipa_jump_func)); +} + +/* Return the call expr tree related to callsite CS. */ +static inline tree +ipa_callsite_tree (struct cgraph_edge *cs) +{ + return cs->call_stmt; +} + +/* Return the caller (cgraph_node) of CS. */ +static inline struct cgraph_node * +ipa_callsite_caller (struct cgraph_edge *cs) +{ + return cs->caller; +} + +/* Count number of arguments callsite CS has and store it in + ipa_edge structure corresponding to this callsite. */ +void +ipa_callsite_compute_count (struct cgraph_edge *cs) +{ + tree call_tree; + tree arg; + int arg_num; + + call_tree = get_call_expr_in (ipa_callsite_tree (cs)); + gcc_assert (TREE_CODE (call_tree) == CALL_EXPR); + arg = TREE_OPERAND (call_tree, 1); + arg_num = 0; + for (; arg != NULL_TREE; arg = TREE_CHAIN (arg)) + arg_num++; + ipa_callsite_param_count_set (cs, arg_num); +} + +/* Compute jump function for all arguments of callsite CS + and insert the information in the ipa_param_map array + in the ipa_edge corresponding to this callsite. (Explanation + on jump functions is in ipa-prop.h). */ +void +ipa_callsite_compute_param (struct cgraph_edge *cs) +{ + tree call_tree; + tree arg, cst_decl, arg_type, formal_type; + int arg_num; + int i; + struct cgraph_node *mt; + + if (ipa_callsite_param_count (cs) == 0) + return; + ipa_callsite_param_map_create (cs); + call_tree = get_call_expr_in (ipa_callsite_tree (cs)); + gcc_assert (TREE_CODE (call_tree) == CALL_EXPR); + arg = TREE_OPERAND (call_tree, 1); + arg_num = 0; + + for (; arg != NULL_TREE; arg = TREE_CHAIN (arg)) + { + /* If the formal parameter was passed as argument, we store + FORMAL_IPATYPE and its index in the caller as the jump function + of this argument. */ + if (TREE_CODE (TREE_VALUE (arg)) == PARM_DECL) + { + mt = ipa_callsite_caller (cs); + i = ipa_method_tree_map (mt, TREE_VALUE (arg)); + if (i < 0 || ipa_method_is_modified (mt, i)) + ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE); + else + { + arg_type = TREE_TYPE (TREE_VALUE (arg)); + formal_type = TREE_TYPE (ipa_method_get_tree (cs->callee, arg_num)); + if (TYPE_NAME (arg_type) == TYPE_NAME (formal_type) + && TYPE_CONTEXT (arg_type) == TYPE_CONTEXT (formal_type) + && attribute_list_equal (TYPE_ATTRIBUTES (arg_type), + TYPE_ATTRIBUTES (formal_type))) + { + ipa_callsite_param_set_type (cs, arg_num, FORMAL_IPATYPE); + ipa_callsite_param_set_info_type_formal (cs, arg_num, i); + } + else + ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE); + } + } + /* If a constant value was passed as argument, + we store CONST_IPATYPE and its value as the jump function + of this argument. */ + else if (TREE_CODE (TREE_VALUE (arg)) == INTEGER_CST + || TREE_CODE (TREE_VALUE (arg)) == REAL_CST) + { + arg_type = TREE_TYPE (TREE_VALUE (arg)); + formal_type = TREE_TYPE (ipa_method_get_tree (cs->callee, arg_num)); + if (TYPE_NAME (arg_type) == TYPE_NAME (formal_type) + && TYPE_CONTEXT (arg_type) == TYPE_CONTEXT (formal_type) + && attribute_list_equal (TYPE_ATTRIBUTES (arg_type), + TYPE_ATTRIBUTES (formal_type))) + { + ipa_callsite_param_set_type (cs, arg_num, CONST_IPATYPE); + ipa_callsite_param_set_info_type (cs, arg_num, TREE_VALUE (arg)); + } + else + ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE); + } + /* This is for the case of Fortran. If the address of a const_decl + was passed as argument then we store + CONST_IPATYPE_REF/CONST_IPATYPE_REF and the costant + value as the jump function corresponding to this argument. */ + else if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR + && TREE_CODE (TREE_OPERAND (TREE_VALUE (arg), 0)) == + CONST_DECL) + { + cst_decl = TREE_OPERAND (TREE_VALUE (arg), 0); + arg_type = TREE_TYPE (DECL_INITIAL (cst_decl)); + formal_type = + TREE_TYPE (TREE_TYPE (ipa_method_get_tree (cs->callee, arg_num))); + if (TREE_CODE (DECL_INITIAL (cst_decl)) == INTEGER_CST + || TREE_CODE (DECL_INITIAL (cst_decl)) == REAL_CST) + { + if (TYPE_NAME (arg_type) == TYPE_NAME (formal_type) + && TYPE_CONTEXT (arg_type) == TYPE_CONTEXT (formal_type) + && attribute_list_equal (TYPE_ATTRIBUTES (arg_type), + TYPE_ATTRIBUTES (formal_type))) + + { + ipa_callsite_param_set_type (cs, arg_num, + CONST_IPATYPE_REF); + ipa_callsite_param_set_info_type (cs, arg_num, DECL_INITIAL (cst_decl)); + + } + else + ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE); + } + } + else + ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE); + arg_num++; + } +} + +/* Return type of jump function JF. */ +enum jump_func_type +get_type (struct ipa_jump_func *jf) +{ + return jf->type; +} + +/* Return info type of jump function JF. */ +union parameter_info * +ipa_jf_get_info_type (struct ipa_jump_func *jf) +{ + return &(jf->info_type); +} + +/* Allocate and initialize ipa_node structure. + cgraph_node NODE points to the new allocated ipa_node. */ +void +ipa_node_create (struct cgraph_node *node) +{ + node->aux = xcalloc (1, sizeof (struct ipa_node)); +} + +/* Allocate and initialize ipa_node structure for all + nodes in callgraph. */ +void +ipa_nodes_create (void) +{ + struct cgraph_node *node; + + for (node = cgraph_nodes; node; node = node->next) + ipa_node_create (node); +} + +/* Allocate and initialize ipa_edge structure. */ +void +ipa_edges_create (void) +{ + struct cgraph_node *node; + struct cgraph_edge *cs; + + for (node = cgraph_nodes; node; node = node->next) + for (cs = node->callees; cs; cs = cs->next_callee) + cs->aux = xcalloc (1, sizeof (struct ipa_edge)); +} + +/* Free ipa_node structure. */ +void +ipa_nodes_free (void) +{ + struct cgraph_node *node; + + for (node = cgraph_nodes; node; node = node->next) + { + free (node->aux); + node->aux = NULL; + } +} + +/* Free ipa_edge structure. */ +void +ipa_edges_free (void) +{ + struct cgraph_node *node; + struct cgraph_edge *cs; + + for (node = cgraph_nodes; node; node = node->next) + for (cs = node->callees; cs; cs = cs->next_callee) + { + free (cs->aux); + cs->aux = NULL; + } +} + +/* Free ipa data structures of ipa_node and ipa_edge. */ +void +ipa_free (void) +{ + struct cgraph_node *node; + struct cgraph_edge *cs; + + for (node = cgraph_nodes; node; node = node->next) + { + if (node->aux == NULL) + continue; + if (IPA_NODE_REF (node)->ipcp_cval) + free (IPA_NODE_REF (node)->ipcp_cval); + if (IPA_NODE_REF (node)->ipa_param_tree) + free (IPA_NODE_REF (node)->ipa_param_tree); + if (IPA_NODE_REF (node)->ipa_mod) + free (IPA_NODE_REF (node)->ipa_mod); + for (cs = node->callees; cs; cs = cs->next_callee) + { + if (cs->aux) + if (IPA_EDGE_REF (cs)->ipa_param_map) + free (IPA_EDGE_REF (cs)->ipa_param_map); + } + } +} + +/* Print ipa_tree_map data structures of all methods in the + callgraph to F. */ +void +ipa_method_tree_print (FILE * f) +{ + int i, count; + tree temp; + struct cgraph_node *node; + + fprintf (f, "\nPARAM TREE MAP PRINT\n"); + for (node = cgraph_nodes; node; node = node->next) + { + fprintf (f, "method %s Trees :: \n", cgraph_node_name (node)); + count = ipa_method_formal_count (node); + for (i = 0; i < count; i++) + { + temp = ipa_method_get_tree (node, i); + if (TREE_CODE (temp) == PARM_DECL) + fprintf (f, " param [%d] : %s\n", i, + (*lang_hooks.decl_printable_name) (temp, 2)); + } + + } +} + +/* Print ipa_modify data structures of all methods in the + callgraph to F. */ +void +ipa_method_modify_print (FILE * f) +{ + int i, count; + bool temp; + struct cgraph_node *node; + + fprintf (f, "\nMODIFY PRINT\n"); + for (node = cgraph_nodes; node; node = node->next) + { + fprintf (f, "method %s :: \n", cgraph_node_name (node)); + count = ipa_method_formal_count (node); + for (i = 0; i < count; i++) + { + temp = ipa_method_is_modified (node, i); + if (temp) + fprintf (f, " param [%d] true \n", i); + else + fprintf (f, " param [%d] false \n", i); + } + } +} diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h new file mode 100644 index 0000000..db9b916 --- /dev/null +++ b/gcc/ipa-prop.h @@ -0,0 +1,204 @@ +/* Interprocedural analyses. + Copyright (C) 2005 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#ifndef IPA_PROP_H +#define IPA_PROP_H + +#include "tree.h" + +/* The following definitions and interfaces are used by + interprocedural analyses. */ + +/* A jump function for a callsite represents the values passed as actual + arguments of the callsite. There are three main types of values : + Formal - the caller's formal parameter is passed as an actual argument. + Constant - a constant is passed as a an actual argument. + Unknown - neither of the above. + Integer and real constants are represented as CONST_IPATYPE and Fortran + constants are represented as CONST_IPATYPE_REF. */ +enum jump_func_type +{ + UNKNOWN_IPATYPE, + CONST_IPATYPE, + CONST_IPATYPE_REF, + FORMAL_IPATYPE +}; + +/* All formal parameters in the program have a cval computed by + the interprocedural stage of IPCP. + There are three main values of cval : + TOP - unknown. + BOTTOM - non constant. + CONSTANT_TYPE - constant value. + Cval of formal f will have a constant value if all callsites to this + function have the same constant value passed to f. + Integer and real constants are represented as CONST_IPATYPE and Fortran + constants are represented as CONST_IPATYPE_REF. */ +enum cvalue_type +{ + BOTTOM, + CONST_VALUE, + CONST_VALUE_REF, + TOP +}; + +/* Represents the value of either jump function or cval. + value represnts a constant. + formal_id is used only in jump function context and represents + pass-through parameter (the formal of caller is passed + as argument). */ +union parameter_info +{ + unsigned int formal_id; + tree value; +}; + +/* A jump function for a callsite represents the values passed as actual + arguments of the callsite. See enum jump_func_type for the various + types of jump functions supported. */ +struct ipa_jump_func +{ + enum jump_func_type type; + union parameter_info info_type; +}; + +/* All formal parameters in the program have a cval computed by + the interprocedural stage of IPCP. See enum cvalue_type for + the various types of cvals supported */ +struct ipcp_formal +{ + enum cvalue_type cval_type; + union parameter_info cvalue; +}; + +/* Represent which DECL tree (or reference to such tree) + will be replaced by another tree while versioning. */ +struct ipa_replace_map +{ + /* The tree that will be replaced. */ + tree old_tree; + /* The new (replacing) tree. */ + tree new_tree; + /* True when a substitution should be done, false otherwise. */ + bool replace_p; + /* True when we replace a reference to old_tree. */ + bool ref_p; +}; + +/* Return the field in cgraph_node/cgraph_edge struct that points + to ipa_node/ipa_edge struct. */ +#define IPA_NODE_REF(MT) ((struct ipa_node *)(MT)->aux) +#define IPA_EDGE_REF(EDGE) ((struct ipa_edge *)(EDGE)->aux) + +/* ipa_node stores information related to a method and + its formal parameters. It is pointed to by a field in the + method's corresponding cgraph_node. + + ipa_edge stores information related to a callsite and + its arguments. It is pointed to by a field in the + callsite's corresponding cgraph_edge. */ +struct ipa_node +{ + /* Number of formal parameters of this method. When set to 0, + this method's parameters would not be analyzed by the different + stages of IPA CP. */ + int ipa_arg_num; + /* Array of cvals. */ + struct ipcp_formal *ipcp_cval; + /* Mapping each parameter to its PARM_DECL tree. */ + tree *ipa_param_tree; + /* Indicating which parameter is modified in its method. */ + bool *ipa_mod; + /* Only for versioned nodes this field would not be NULL, + it points to the node that IPA cp cloned from. */ + struct cgraph_node *ipcp_orig_node; + /* Meaningful only for original methods. Expresses the + ratio between the direct calls and sum of all invocations of + this function (given by profiling info). It is used to calculate + the profiling information of the original function and the versioned + one. */ + gcov_type count_scale; +}; + +struct ipa_edge +{ + /* Number of actual arguments in this callsite. When set to 0, + this callsite's parameters would not be analyzed by the different + stages of IPA CP. */ + int ipa_param_num; + /* Array of the callsite's jump function of each parameter. */ + struct ipa_jump_func *ipa_param_map; +}; + +/* A methodlist element (referred to also as methodlist node). It is used + to create a temporary worklist used in + the propagation stage of IPCP. (can be used for more IPA + optimizations) */ +struct ipa_methodlist +{ + struct cgraph_node *method_p; + struct ipa_methodlist *next_method; +}; + +/* A pointer to a methodlist elemement. */ +typedef struct ipa_methodlist *ipa_methodlist_p; + +/* ipa_methodlist interface. */ +ipa_methodlist_p ipa_methodlist_init (void); +bool ipa_methodlist_not_empty (ipa_methodlist_p); +void ipa_add_method (ipa_methodlist_p *, struct cgraph_node *); +struct cgraph_node *ipa_remove_method (ipa_methodlist_p *); + +/* ipa_callsite interface. */ +int ipa_callsite_param_count (struct cgraph_edge *); +void ipa_callsite_param_count_set (struct cgraph_edge *, int); +struct ipa_jump_func *ipa_callsite_param (struct cgraph_edge *, int); +struct cgraph_node *ipa_callsite_callee (struct cgraph_edge *); +void ipa_callsite_compute_param (struct cgraph_edge *); +void ipa_callsite_compute_count (struct cgraph_edge *); + +/* ipa_method interface. */ +int ipa_method_formal_count (struct cgraph_node *); +void ipa_method_formal_count_set (struct cgraph_node *, int); +tree ipa_method_get_tree (struct cgraph_node *, int); +void ipa_method_compute_tree_map (struct cgraph_node *); +void ipa_method_formal_compute_count (struct cgraph_node *); +void ipa_method_compute_modify (struct cgraph_node *); + +/* jump function interface. */ +enum jump_func_type get_type (struct ipa_jump_func *); +union parameter_info *ipa_jf_get_info_type (struct ipa_jump_func *); + +/* ipa_node and ipa_edge interfaces. */ +void ipa_node_create (struct cgraph_node *); +void ipa_free (void); +void ipa_nodes_create (void); +void ipa_edges_create (void); +void ipa_edges_free (void); +void ipa_nodes_free (void); + + +/* Debugging interface. */ +void ipa_method_tree_print (FILE *); +void ipa_method_modify_print (FILE *); + +void ipcp_driver (void); + +#endif /* IPA_PROP_H */ |