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