1/* Interprocedural analyses. 2 Copyright (C) 2005, 2007, 2008, 2009 3 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21#ifndef IPA_PROP_H 22#define IPA_PROP_H 23 24#include "tree.h" 25#include "vec.h" 26#include "cgraph.h" 27 28/* The following definitions and interfaces are used by 29 interprocedural analyses or parameters. */ 30 31/* ipa-prop.c stuff (ipa-cp, indirect inlining): */ 32 33/* A jump function for a callsite represents the values passed as actual 34 arguments of the callsite. There are three main types of values : 35 36 Pass-through - the caller's formal parameter is passed as an actual 37 argument, possibly one simple operation performed on it. 38 Constant - a constant (is_gimple_ip_invariant)is passed as an actual 39 argument. 40 Unknown - neither of the above. 41 42 IPA_JF_CONST_MEMBER_PTR stands for C++ member pointers, other constants are 43 represented with IPA_JF_CONST. 44 45 In addition to "ordinary" pass through functions represented by 46 IPA_JF_PASS_THROUGH, IPA_JF_ANCESTOR represents getting addresses of of 47 ancestor fields in C++ (e.g. &this_1(D)->D.1766.D.1756). */ 48enum jump_func_type 49{ 50 IPA_JF_UNKNOWN = 0, /* newly allocated and zeroed jump functions default */ 51 IPA_JF_CONST, 52 IPA_JF_CONST_MEMBER_PTR, 53 IPA_JF_PASS_THROUGH, 54 IPA_JF_ANCESTOR 55}; 56 57/* All formal parameters in the program have a lattice associated with it 58 computed by the interprocedural stage of IPCP. 59 There are three main values of the lattice: 60 IPA_TOP - unknown, 61 IPA_BOTTOM - non constant, 62 IPA_CONST_VALUE - simple scalar constant, 63 Cval of formal f will have a constant value if all callsites to this 64 function have the same constant value passed to f. 65 Integer and real constants are represented as IPA_CONST_VALUE. */ 66enum ipa_lattice_type 67{ 68 IPA_BOTTOM, 69 IPA_CONST_VALUE, 70 IPA_TOP 71}; 72 73 74/* Structure holding data required to describe a pass-through jump function. */ 75 76struct GTY(()) ipa_pass_through_data 77{ 78 /* If an operation is to be performed on the original parameter, this is the 79 second (constant) operand. */ 80 tree operand; 81 /* Number of the caller's formal parameter being passed. */ 82 int formal_id; 83 /* Operation that is performed on the argument before it is passed on. 84 NOP_EXPR means no operation. Otherwise oper must be a simple binary 85 arithmetic operation where the caller's parameter is the first operand and 86 operand field from this structure is the second one. */ 87 enum tree_code operation; 88}; 89 90/* Structure holding data required to describe and ancestor pass throu 91 funkci. */ 92 93struct GTY(()) ipa_ancestor_jf_data 94{ 95 /* Offset of the field representing the ancestor. */ 96 HOST_WIDE_INT offset; 97 /* TYpe of the result. */ 98 tree type; 99 /* Number of the caller's formal parameter being passed. */ 100 int formal_id; 101}; 102 103/* Structure holding a C++ member pointer constant. Holds a pointer to the 104 method and delta offset. */ 105struct GTY(()) ipa_member_ptr_cst 106{ 107 tree pfn; 108 tree delta; 109}; 110 111/* A jump function for a callsite represents the values passed as actual 112 arguments of the callsite. See enum jump_func_type for the various 113 types of jump functions supported. */ 114struct GTY (()) ipa_jump_func 115{ 116 enum jump_func_type type; 117 /* Represents a value of a jump function. pass_through is used only in jump 118 function context. constant represents the actual constant in constant jump 119 functions and member_cst holds constant c++ member functions. */ 120 union jump_func_value 121 { 122 tree GTY ((tag ("IPA_JF_CONST"))) constant; 123 struct ipa_pass_through_data GTY ((tag ("IPA_JF_PASS_THROUGH"))) pass_through; 124 struct ipa_ancestor_jf_data GTY ((tag ("IPA_JF_ANCESTOR"))) ancestor; 125 struct ipa_member_ptr_cst GTY ((tag ("IPA_JF_CONST_MEMBER_PTR"))) member_cst; 126 } GTY ((desc ("%1.type"))) value; 127}; 128 129/* All formal parameters in the program have a cval computed by 130 the interprocedural stage of IPCP. See enum ipa_lattice_type for 131 the various types of lattices supported */ 132struct ipcp_lattice 133{ 134 enum ipa_lattice_type type; 135 tree constant; 136}; 137 138/* Each instance of the following structure describes a statement that calls a 139 function parameter. Those referring to statements within the same function 140 are linked in a list. */ 141struct ipa_param_call_note 142{ 143 /* Expected number of executions: calculated in profile.c. */ 144 gcov_type count; 145 /* Linked list's next */ 146 struct ipa_param_call_note *next; 147 /* Statement that contains the call to the parameter above. */ 148 gimple stmt; 149 /* When in LTO, we the above stmt will be NULL and we need an uid. */ 150 unsigned int lto_stmt_uid; 151 /* Index of the parameter that is called. */ 152 int formal_id; 153 /* Expected frequency of executions within the function. see cgraph_edge in 154 cgraph.h for more on this. */ 155 int frequency; 156 /* Depth of loop nest, 1 means no loop nest. */ 157 unsigned short int loop_nest; 158 /* Set when we have already found the target to be a compile time constant 159 and turned this into an edge or when the note was found unusable for some 160 reason. */ 161 bool processed; 162}; 163 164/* Structure describing a single formal parameter. */ 165struct ipa_param_descriptor 166{ 167 /* IPA-CP lattice. */ 168 struct ipcp_lattice ipcp_lattice; 169 /* PARAM_DECL of this parameter. */ 170 tree decl; 171 /* Whether the value parameter has been modified within the function. */ 172 unsigned modified : 1; 173}; 174 175/* ipa_node_params stores information related to formal parameters of functions 176 and some other information for interprocedural passes that operate on 177 parameters (such as ipa-cp). */ 178struct ipa_node_params 179{ 180 /* Number of formal parameters of this function. When set to 0, 181 this function's parameters would not be analyzed by the different 182 stages of IPA CP. */ 183 int param_count; 184 /* Pointer to an array of structures describing individual formal 185 parameters. */ 186 struct ipa_param_descriptor *params; 187 /* List of structures enumerating calls to a formal parameter. */ 188 struct ipa_param_call_note *param_calls; 189 /* Only for versioned nodes this field would not be NULL, 190 it points to the node that IPA cp cloned from. */ 191 struct cgraph_node *ipcp_orig_node; 192 /* Meaningful only for original functions. Expresses the 193 ratio between the direct calls and sum of all invocations of 194 this function (given by profiling info). It is used to calculate 195 the profiling information of the original function and the versioned 196 one. */ 197 gcov_type count_scale; 198 199 /* Whether this function is called with variable number of actual 200 arguments. */ 201 unsigned called_with_var_arguments : 1; 202 /* Whether the modification analysis has already been performed. */ 203 unsigned modification_analysis_done : 1; 204 /* Whether the param uses analysis has already been performed. */ 205 unsigned uses_analysis_done : 1; 206 /* Whether the function is enqueued in an ipa_func_list. */ 207 unsigned node_enqueued : 1; 208}; 209 210/* ipa_node_params access functions. Please use these to access fields that 211 are or will be shared among various passes. */ 212 213/* Set the number of formal parameters. */ 214 215static inline void 216ipa_set_param_count (struct ipa_node_params *info, int count) 217{ 218 info->param_count = count; 219} 220 221/* Return the number of formal parameters. */ 222 223static inline int 224ipa_get_param_count (struct ipa_node_params *info) 225{ 226 return info->param_count; 227} 228 229/* Return the declaration of Ith formal parameter of the function corresponding 230 to INFO. Note there is no setter function as this array is built just once 231 using ipa_initialize_node_params. */ 232 233static inline tree 234ipa_get_param (struct ipa_node_params *info, int i) 235{ 236 return info->params[i].decl; 237} 238 239/* Return the modification flag corresponding to the Ith formal parameter of 240 the function associated with INFO. Note that there is no setter method as 241 the goal is to set all flags when building the array in 242 ipa_detect_param_modifications. */ 243 244static inline bool 245ipa_is_param_modified (struct ipa_node_params *info, int i) 246{ 247 return info->params[i].modified; 248} 249 250/* Flag this node as having callers with variable number of arguments. */ 251 252static inline void 253ipa_set_called_with_variable_arg (struct ipa_node_params *info) 254{ 255 info->called_with_var_arguments = 1; 256} 257 258/* Have we detected this node was called with variable number of arguments? */ 259 260static inline bool 261ipa_is_called_with_var_arguments (struct ipa_node_params *info) 262{ 263 return info->called_with_var_arguments; 264} 265 266 267 268/* ipa_edge_args stores information related to a callsite and particularly 269 its arguments. It is pointed to by a field in the 270 callsite's corresponding cgraph_edge. */ 271typedef struct GTY(()) ipa_edge_args 272{ 273 /* Number of actual arguments in this callsite. When set to 0, 274 this callsite's parameters would not be analyzed by the different 275 stages of IPA CP. */ 276 int argument_count; 277 /* Array of the callsite's jump function of each parameter. */ 278 struct ipa_jump_func GTY ((length ("%h.argument_count"))) *jump_functions; 279} ipa_edge_args_t; 280 281/* ipa_edge_args access functions. Please use these to access fields that 282 are or will be shared among various passes. */ 283 284/* Set the number of actual arguments. */ 285 286static inline void 287ipa_set_cs_argument_count (struct ipa_edge_args *args, int count) 288{ 289 args->argument_count = count; 290} 291 292/* Return the number of actual arguments. */ 293 294static inline int 295ipa_get_cs_argument_count (struct ipa_edge_args *args) 296{ 297 return args->argument_count; 298} 299 300/* Returns a pointer to the jump function for the ith argument. Please note 301 there is no setter function as jump functions are all set up in 302 ipa_compute_jump_functions. */ 303 304static inline struct ipa_jump_func * 305ipa_get_ith_jump_func (struct ipa_edge_args *args, int i) 306{ 307 return &args->jump_functions[i]; 308} 309 310/* Vectors need to have typedefs of structures. */ 311typedef struct ipa_node_params ipa_node_params_t; 312 313/* Types of vectors holding the infos. */ 314DEF_VEC_O (ipa_node_params_t); 315DEF_VEC_ALLOC_O (ipa_node_params_t, heap); 316DEF_VEC_O (ipa_edge_args_t); 317DEF_VEC_ALLOC_O (ipa_edge_args_t, gc); 318 319/* Vector where the parameter infos are actually stored. */ 320extern VEC (ipa_node_params_t, heap) *ipa_node_params_vector; 321/* Vector where the parameter infos are actually stored. */ 322extern GTY(()) VEC (ipa_edge_args_t, gc) *ipa_edge_args_vector; 323 324/* Return the associated parameter/argument info corresponding to the given 325 node/edge. */ 326#define IPA_NODE_REF(NODE) (VEC_index (ipa_node_params_t, \ 327 ipa_node_params_vector, (NODE)->uid)) 328#define IPA_EDGE_REF(EDGE) (VEC_index (ipa_edge_args_t, \ 329 ipa_edge_args_vector, (EDGE)->uid)) 330/* This macro checks validity of index returned by 331 ipa_get_param_decl_index function. */ 332#define IS_VALID_JUMP_FUNC_INDEX(I) ((I) != -1) 333 334/* Creating and freeing ipa_node_params and ipa_edge_args. */ 335void ipa_create_all_node_params (void); 336void ipa_create_all_edge_args (void); 337void ipa_free_edge_args_substructures (struct ipa_edge_args *); 338void ipa_free_node_params_substructures (struct ipa_node_params *); 339void ipa_free_all_node_params (void); 340void ipa_free_all_edge_args (void); 341void free_all_ipa_structures_after_ipa_cp (void); 342void free_all_ipa_structures_after_iinln (void); 343void ipa_register_cgraph_hooks (void); 344 345/* This function ensures the array of node param infos is big enough to 346 accommodate a structure for all nodes and reallocates it if not. */ 347 348static inline void 349ipa_check_create_node_params (void) 350{ 351 if (!ipa_node_params_vector) 352 ipa_node_params_vector = VEC_alloc (ipa_node_params_t, heap, 353 cgraph_max_uid); 354 355 if (VEC_length (ipa_node_params_t, ipa_node_params_vector) 356 <= (unsigned) cgraph_max_uid) 357 VEC_safe_grow_cleared (ipa_node_params_t, heap, 358 ipa_node_params_vector, cgraph_max_uid + 1); 359} 360 361/* This function ensures the array of edge arguments infos is big enough to 362 accommodate a structure for all edges and reallocates it if not. */ 363 364static inline void 365ipa_check_create_edge_args (void) 366{ 367 if (!ipa_edge_args_vector) 368 ipa_edge_args_vector = VEC_alloc (ipa_edge_args_t, gc, 369 cgraph_edge_max_uid); 370 371 if (VEC_length (ipa_edge_args_t, ipa_edge_args_vector) 372 <= (unsigned) cgraph_edge_max_uid) 373 VEC_safe_grow_cleared (ipa_edge_args_t, gc, ipa_edge_args_vector, 374 cgraph_edge_max_uid + 1); 375} 376 377/* Returns true if the array of edge infos is large enough to accommodate an 378 info for EDGE. The main purpose of this function is that debug dumping 379 function can check info availability without causing reallocations. */ 380 381static inline bool 382ipa_edge_args_info_available_for_edge_p (struct cgraph_edge *edge) 383{ 384 return ((unsigned) edge->uid < VEC_length (ipa_edge_args_t, 385 ipa_edge_args_vector)); 386} 387 388/* A function list element. It is used to create a temporary worklist used in 389 the propagation stage of IPCP. (can be used for more IPA optimizations) */ 390struct ipa_func_list 391{ 392 struct cgraph_node *node; 393 struct ipa_func_list *next; 394}; 395 396/* ipa_func_list interface. */ 397struct ipa_func_list *ipa_init_func_list (void); 398void ipa_push_func_to_list_1 (struct ipa_func_list **, struct cgraph_node *, 399 struct ipa_node_params *); 400struct cgraph_node *ipa_pop_func_from_list (struct ipa_func_list **); 401 402/* Add cgraph NODE to the worklist WL if it is not already in one. */ 403 404static inline void 405ipa_push_func_to_list (struct ipa_func_list **wl, struct cgraph_node *node) 406{ 407 struct ipa_node_params *info = IPA_NODE_REF (node); 408 409 if (!info->node_enqueued) 410 ipa_push_func_to_list_1 (wl, node, info); 411} 412 413/* Callsite related calculations. */ 414void ipa_compute_jump_functions (struct cgraph_edge *); 415void ipa_count_arguments (struct cgraph_edge *); 416 417/* Function formal parameters related computations. */ 418void ipa_initialize_node_params (struct cgraph_node *node); 419void ipa_detect_param_modifications (struct cgraph_node *); 420void ipa_analyze_params_uses (struct cgraph_node *); 421bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs, 422 VEC (cgraph_edge_p, heap) **new_edges); 423 424/* Debugging interface. */ 425void ipa_print_node_params (FILE *, struct cgraph_node *node); 426void ipa_print_all_params (FILE *); 427void ipa_print_node_jump_functions (FILE *f, struct cgraph_node *node); 428void ipa_print_all_jump_functions (FILE * f); 429 430/* Structure to describe transformations of formal parameters and actual 431 arguments. Each instance describes one new parameter and they are meant to 432 be stored in a vector. Additionally, most users will probably want to store 433 adjustments about parameters that are being removed altogether so that SSA 434 names belonging to them can be replaced by SSA names of an artificial 435 variable. */ 436struct ipa_parm_adjustment 437{ 438 /* The original PARM_DECL itself, helpful for processing of the body of the 439 function itself. Intended for traversing function bodies. 440 ipa_modify_formal_parameters, ipa_modify_call_arguments and 441 ipa_combine_adjustments ignore this and use base_index. 442 ipa_modify_formal_parameters actually sets this. */ 443 tree base; 444 445 /* Type of the new parameter. However, if by_ref is true, the real type will 446 be a pointer to this type. */ 447 tree type; 448 449 /* The new declaration when creating/replacing a parameter. Created by 450 ipa_modify_formal_parameters, useful for functions modifying the body 451 accordingly. */ 452 tree reduction; 453 454 /* New declaration of a substitute variable that we may use to replace all 455 non-default-def ssa names when a parm decl is going away. */ 456 tree new_ssa_base; 457 458 /* If non-NULL and the original parameter is to be removed (copy_param below 459 is NULL), this is going to be its nonlocalized vars value. */ 460 tree nonlocal_value; 461 462 /* Offset into the original parameter (for the cases when the new parameter 463 is a component of an original one). */ 464 HOST_WIDE_INT offset; 465 466 /* Zero based index of the original parameter this one is based on. (ATM 467 there is no way to insert a new parameter out of the blue because there is 468 no need but if it arises the code can be easily exteded to do so.) */ 469 int base_index; 470 471 /* This new parameter is an unmodified parameter at index base_index. */ 472 unsigned copy_param : 1; 473 474 /* This adjustment describes a parameter that is about to be removed 475 completely. Most users will probably need to book keep those so that they 476 don't leave behinfd any non default def ssa names belonging to them. */ 477 unsigned remove_param : 1; 478 479 /* The parameter is to be passed by reference. */ 480 unsigned by_ref : 1; 481}; 482 483typedef struct ipa_parm_adjustment ipa_parm_adjustment_t; 484DEF_VEC_O (ipa_parm_adjustment_t); 485DEF_VEC_ALLOC_O (ipa_parm_adjustment_t, heap); 486 487typedef VEC (ipa_parm_adjustment_t, heap) *ipa_parm_adjustment_vec; 488 489VEC(tree, heap) *ipa_get_vector_of_formal_parms (tree fndecl); 490void ipa_modify_formal_parameters (tree fndecl, ipa_parm_adjustment_vec, 491 const char *); 492void ipa_modify_call_arguments (struct cgraph_edge *, gimple, 493 ipa_parm_adjustment_vec); 494ipa_parm_adjustment_vec ipa_combine_adjustments (ipa_parm_adjustment_vec, 495 ipa_parm_adjustment_vec); 496void ipa_dump_param_adjustments (FILE *, ipa_parm_adjustment_vec, tree); 497 498void ipa_prop_write_jump_functions (cgraph_node_set set); 499void ipa_prop_read_jump_functions (void); 500void ipa_update_after_lto_read (void); 501void lto_ipa_fixup_call_notes (struct cgraph_node *, gimple *); 502 503/* From tree-sra.c: */ 504bool build_ref_for_offset (tree *, tree, HOST_WIDE_INT, tree, bool); 505 506#endif /* IPA_PROP_H */ 507