1/* Interprocedural analyses. 2 Copyright (C) 2005 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 2, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 1902110-1301, USA. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tree.h" 25#include "langhooks.h" 26#include "ggc.h" 27#include "target.h" 28#include "cgraph.h" 29#include "ipa-prop.h" 30#include "tree-flow.h" 31#include "tree-pass.h" 32#include "flags.h" 33#include "timevar.h" 34 35/* This file contains interfaces that can be used for various IPA 36 optimizations: 37 38 - ipa_methodlist interface - It is used to create and handle a temporary 39 worklist used in the propagation stage of IPCP. (can be used for more 40 IPA optimizations). 41 42 - ipa_callsite interface - for each callsite this interface creates and 43 handles ipa_edge structure associated with it. 44 45 - ipa_method interface - for each method this interface creates and 46 handles ipa_node structure associated with it. */ 47 48/* ipa_methodlist interface. */ 49 50/* Create a new worklist node. */ 51static inline ipa_methodlist_p 52ipa_create_methodlist_node (void) 53{ 54 return (ipa_methodlist_p) xcalloc (1, sizeof (struct ipa_methodlist)); 55} 56 57/* Return true if worklist WL is empty. */ 58bool 59ipa_methodlist_not_empty (ipa_methodlist_p wl) 60{ 61 return (wl != NULL); 62} 63 64/* Return the method in worklist element WL. */ 65static inline struct cgraph_node * 66ipa_methodlist_method (ipa_methodlist_p wl) 67{ 68 return wl->method_p; 69} 70 71/* Make worklist element WL point to method MT in the callgraph. */ 72static inline void 73ipa_methodlist_method_set (ipa_methodlist_p wl, struct cgraph_node *mt) 74{ 75 wl->method_p = mt; 76} 77 78/* Return the next element in the worklist following worklist 79 element WL. */ 80static inline ipa_methodlist_p 81ipa_methodlist_next_method (ipa_methodlist_p wl) 82{ 83 return wl->next_method; 84} 85 86/* Set worklist element WL1 to point to worklist element WL2. */ 87static inline void 88ipa_methodlist_next_method_set (ipa_methodlist_p wl1, ipa_methodlist_p wl2) 89{ 90 wl1->next_method = wl2; 91} 92 93/* Initialize worklist to contain all methods. */ 94ipa_methodlist_p 95ipa_methodlist_init (void) 96{ 97 struct cgraph_node *node; 98 ipa_methodlist_p wl; 99 100 wl = NULL; 101 for (node = cgraph_nodes; node; node = node->next) 102 ipa_add_method (&wl, node); 103 104 return wl; 105} 106 107/* Add method MT to the worklist. Set worklist element WL 108 to point to MT. */ 109void 110ipa_add_method (ipa_methodlist_p * wl, struct cgraph_node *mt) 111{ 112 ipa_methodlist_p temp; 113 114 temp = ipa_create_methodlist_node (); 115 ipa_methodlist_method_set (temp, mt); 116 ipa_methodlist_next_method_set (temp, *wl); 117 *wl = temp; 118} 119 120/* Remove a method from the worklist. WL points to the first 121 element in the list, which is removed. */ 122struct cgraph_node * 123ipa_remove_method (ipa_methodlist_p * wl) 124{ 125 ipa_methodlist_p first; 126 struct cgraph_node *return_method; 127 128 first = *wl; 129 *wl = ipa_methodlist_next_method (*wl); 130 return_method = ipa_methodlist_method (first); 131 free (first); 132 return return_method; 133} 134 135/* ipa_method interface. */ 136 137/* Return number of formals of method MT. */ 138int 139ipa_method_formal_count (struct cgraph_node *mt) 140{ 141 return IPA_NODE_REF (mt)->ipa_arg_num; 142} 143 144/* Set number of formals of method MT to I. */ 145void 146ipa_method_formal_count_set (struct cgraph_node *mt, int i) 147{ 148 IPA_NODE_REF (mt)->ipa_arg_num = i; 149} 150 151/* Return whether I-th formal of MT is modified in MT. */ 152static inline bool 153ipa_method_is_modified (struct cgraph_node *mt, int i) 154{ 155 return IPA_NODE_REF (mt)->ipa_mod[i]; 156} 157 158/* Return the tree of I-th formal of MT. */ 159tree 160ipa_method_get_tree (struct cgraph_node *mt, int i) 161{ 162 return IPA_NODE_REF (mt)->ipa_param_tree[i]; 163} 164 165/* Create tree map structure for MT. */ 166static inline void 167ipa_method_tree_map_create (struct cgraph_node *mt) 168{ 169 IPA_NODE_REF (mt)->ipa_param_tree = 170 XCNEWVEC (tree, ipa_method_formal_count (mt)); 171} 172 173/* Create modify structure for MT. */ 174static inline void 175ipa_method_modify_create (struct cgraph_node *mt) 176{ 177 ((struct ipa_node *) mt->aux)->ipa_mod = 178 XCNEWVEC (bool, ipa_method_formal_count (mt)); 179} 180 181/* Set modify of I-th formal of MT to VAL. */ 182static inline void 183ipa_method_modify_set (struct cgraph_node *mt, int i, bool val) 184{ 185 IPA_NODE_REF (mt)->ipa_mod[i] = val; 186} 187 188/* Return index of the formal whose tree is PTREE in method MT. */ 189static int 190ipa_method_tree_map (struct cgraph_node *mt, tree ptree) 191{ 192 int i, count; 193 194 count = ipa_method_formal_count (mt); 195 for (i = 0; i < count; i++) 196 if (IPA_NODE_REF (mt)->ipa_param_tree[i] == ptree) 197 return i; 198 199 return -1; 200} 201 202/* Insert the formal trees to the ipa_param_tree array in method MT. */ 203void 204ipa_method_compute_tree_map (struct cgraph_node *mt) 205{ 206 tree fndecl; 207 tree fnargs; 208 tree parm; 209 int param_num; 210 211 ipa_method_tree_map_create (mt); 212 fndecl = mt->decl; 213 fnargs = DECL_ARGUMENTS (fndecl); 214 param_num = 0; 215 for (parm = fnargs; parm; parm = TREE_CHAIN (parm)) 216 { 217 IPA_NODE_REF (mt)->ipa_param_tree[param_num] = parm; 218 param_num++; 219 } 220} 221 222/* Count number of formals in MT. Insert the result to the 223 ipa_node. */ 224void 225ipa_method_formal_compute_count (struct cgraph_node *mt) 226{ 227 tree fndecl; 228 tree fnargs; 229 tree parm; 230 int param_num; 231 232 fndecl = mt->decl; 233 fnargs = DECL_ARGUMENTS (fndecl); 234 param_num = 0; 235 for (parm = fnargs; parm; parm = TREE_CHAIN (parm)) 236 param_num++; 237 ipa_method_formal_count_set (mt, param_num); 238} 239 240/* Check STMT to detect whether a formal is modified within MT, 241 the appropriate entry is updated in the ipa_mod array of ipa_node 242 (associated with MT). */ 243static void 244ipa_method_modify_stmt (struct cgraph_node *mt, tree stmt) 245{ 246 int i, j; 247 248 switch (TREE_CODE (stmt)) 249 { 250 case MODIFY_EXPR: 251 if (TREE_CODE (TREE_OPERAND (stmt, 0)) == PARM_DECL) 252 { 253 i = ipa_method_tree_map (mt, TREE_OPERAND (stmt, 0)); 254 if (i >= 0) 255 ipa_method_modify_set (mt, i, true); 256 } 257 break; 258 case ASM_EXPR: 259 /* Asm code could modify any of the parameters. */ 260 for (j = 0; j < ipa_method_formal_count (mt); j++) 261 ipa_method_modify_set (mt, j, true); 262 break; 263 default: 264 break; 265 } 266} 267 268/* Initialize ipa_mod array of MT. */ 269static void 270ipa_method_modify_init (struct cgraph_node *mt) 271{ 272 int i, count; 273 274 ipa_method_modify_create (mt); 275 count = ipa_method_formal_count (mt); 276 for (i = 0; i < count; i++) 277 ipa_method_modify_set (mt, i, false); 278} 279 280/* The modify computation driver for MT. Compute which formal arguments 281 of method MT are locally modified. Formals may be modified in MT 282 if their address is taken, or if 283 they appear on the left hand side of an assignment. */ 284void 285ipa_method_compute_modify (struct cgraph_node *mt) 286{ 287 tree decl; 288 tree body; 289 int j, count; 290 basic_block bb; 291 struct function *func; 292 block_stmt_iterator bsi; 293 tree stmt, parm_tree; 294 295 ipa_method_modify_init (mt); 296 decl = mt->decl; 297 count = ipa_method_formal_count (mt); 298 /* ??? Handle pending sizes case. Set all parameters 299 of the method to be modified. */ 300 if (DECL_UNINLINABLE (decl)) 301 { 302 for (j = 0; j < count; j++) 303 ipa_method_modify_set (mt, j, true); 304 return; 305 } 306 /* Formals whose address is taken are considered modified. */ 307 for (j = 0; j < count; j++) 308 { 309 parm_tree = ipa_method_get_tree (mt, j); 310 if (TREE_ADDRESSABLE (parm_tree)) 311 ipa_method_modify_set (mt, j, true); 312 } 313 body = DECL_SAVED_TREE (decl); 314 if (body != NULL) 315 { 316 func = DECL_STRUCT_FUNCTION (decl); 317 FOR_EACH_BB_FN (bb, func) 318 { 319 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 320 { 321 stmt = bsi_stmt (bsi); 322 ipa_method_modify_stmt (mt, stmt); 323 } 324 } 325 } 326} 327 328 329/* ipa_callsite interface. */ 330 331/* Return number of arguments in callsite CS. */ 332int 333ipa_callsite_param_count (struct cgraph_edge *cs) 334{ 335 return IPA_EDGE_REF (cs)->ipa_param_num; 336} 337 338/* Set number of arguments in callsite CS to I. */ 339void 340ipa_callsite_param_count_set (struct cgraph_edge *cs, int i) 341{ 342 IPA_EDGE_REF (cs)->ipa_param_num = i; 343} 344 345/* Return the jump function (ipa_jump_func struct) for argument I of 346 callsite CS. */ 347struct ipa_jump_func * 348ipa_callsite_param (struct cgraph_edge *cs, int i) 349{ 350 return &(IPA_EDGE_REF (cs)->ipa_param_map[i]); 351} 352 353/* return the callee (cgraph_node) of callsite CS. */ 354struct cgraph_node * 355ipa_callsite_callee (struct cgraph_edge *cs) 356{ 357 return cs->callee; 358} 359 360/* Set field 'type' of jump function (ipa_jump_func struct) of argument I 361 in callsite CS. */ 362static inline void 363ipa_callsite_param_set_type (struct cgraph_edge *cs, int i, 364 enum jump_func_type type1) 365{ 366 IPA_EDGE_REF (cs)->ipa_param_map[i].type = type1; 367} 368 369/* Set FORMAL as 'info_type' field of jump function (ipa_jump_func struct) 370 of argument I of callsite CS. */ 371static inline void 372ipa_callsite_param_set_info_type_formal (struct cgraph_edge *cs, int i, 373 unsigned int formal) 374{ 375 ipa_callsite_param (cs, i)->info_type.formal_id = formal; 376} 377 378/* Set int-valued INFO_TYPE1 as 'info_type' field of 379 jump function (ipa_jump_func struct) of argument I of callsite CS. */ 380static inline void 381ipa_callsite_param_set_info_type (struct cgraph_edge *cs, int i, tree info_type1) 382{ 383 ipa_callsite_param (cs, i)->info_type.value = info_type1; 384} 385 386/* Allocate space for callsite CS. */ 387static inline void 388ipa_callsite_param_map_create (struct cgraph_edge *cs) 389{ 390 IPA_EDGE_REF (cs)->ipa_param_map = 391 XCNEWVEC (struct ipa_jump_func, ipa_callsite_param_count (cs)); 392} 393 394/* Return the call expr tree related to callsite CS. */ 395static inline tree 396ipa_callsite_tree (struct cgraph_edge *cs) 397{ 398 return cs->call_stmt; 399} 400 401/* Return the caller (cgraph_node) of CS. */ 402static inline struct cgraph_node * 403ipa_callsite_caller (struct cgraph_edge *cs) 404{ 405 return cs->caller; 406} 407 408/* Count number of arguments callsite CS has and store it in 409 ipa_edge structure corresponding to this callsite. */ 410void 411ipa_callsite_compute_count (struct cgraph_edge *cs) 412{ 413 tree call_tree; 414 tree arg; 415 int arg_num; 416 417 call_tree = get_call_expr_in (ipa_callsite_tree (cs)); 418 gcc_assert (TREE_CODE (call_tree) == CALL_EXPR); 419 arg = TREE_OPERAND (call_tree, 1); 420 arg_num = 0; 421 for (; arg != NULL_TREE; arg = TREE_CHAIN (arg)) 422 arg_num++; 423 ipa_callsite_param_count_set (cs, arg_num); 424} 425 426/* Compute jump function for all arguments of callsite CS 427 and insert the information in the ipa_param_map array 428 in the ipa_edge corresponding to this callsite. (Explanation 429 on jump functions is in ipa-prop.h). */ 430void 431ipa_callsite_compute_param (struct cgraph_edge *cs) 432{ 433 tree call_tree; 434 tree arg, cst_decl; 435 int arg_num; 436 int i; 437 struct cgraph_node *mt; 438 439 if (ipa_callsite_param_count (cs) == 0) 440 return; 441 ipa_callsite_param_map_create (cs); 442 call_tree = get_call_expr_in (ipa_callsite_tree (cs)); 443 gcc_assert (TREE_CODE (call_tree) == CALL_EXPR); 444 arg = TREE_OPERAND (call_tree, 1); 445 arg_num = 0; 446 447 for (; arg != NULL_TREE; arg = TREE_CHAIN (arg)) 448 { 449 /* If the formal parameter was passed as argument, we store 450 FORMAL_IPATYPE and its index in the caller as the jump function 451 of this argument. */ 452 if (TREE_CODE (TREE_VALUE (arg)) == PARM_DECL) 453 { 454 mt = ipa_callsite_caller (cs); 455 i = ipa_method_tree_map (mt, TREE_VALUE (arg)); 456 if (i < 0 || ipa_method_is_modified (mt, i)) 457 ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE); 458 else 459 { 460 ipa_callsite_param_set_type (cs, arg_num, FORMAL_IPATYPE); 461 ipa_callsite_param_set_info_type_formal (cs, arg_num, i); 462 } 463 } 464 /* If a constant value was passed as argument, 465 we store CONST_IPATYPE and its value as the jump function 466 of this argument. */ 467 else if (TREE_CODE (TREE_VALUE (arg)) == INTEGER_CST 468 || TREE_CODE (TREE_VALUE (arg)) == REAL_CST) 469 { 470 ipa_callsite_param_set_type (cs, arg_num, CONST_IPATYPE); 471 ipa_callsite_param_set_info_type (cs, arg_num, 472 TREE_VALUE (arg)); 473 } 474 /* This is for the case of Fortran. If the address of a const_decl 475 was passed as argument then we store 476 CONST_IPATYPE_REF/CONST_IPATYPE_REF and the constant 477 value as the jump function corresponding to this argument. */ 478 else if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR 479 && TREE_CODE (TREE_OPERAND (TREE_VALUE (arg), 0)) == 480 CONST_DECL) 481 { 482 cst_decl = TREE_OPERAND (TREE_VALUE (arg), 0); 483 if (TREE_CODE (DECL_INITIAL (cst_decl)) == INTEGER_CST 484 || TREE_CODE (DECL_INITIAL (cst_decl)) == REAL_CST) 485 { 486 ipa_callsite_param_set_type (cs, arg_num, 487 CONST_IPATYPE_REF); 488 ipa_callsite_param_set_info_type (cs, arg_num, 489 DECL_INITIAL (cst_decl)); 490 } 491 } 492 else 493 ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE); 494 arg_num++; 495 } 496} 497 498/* Return type of jump function JF. */ 499enum jump_func_type 500get_type (struct ipa_jump_func *jf) 501{ 502 return jf->type; 503} 504 505/* Return info type of jump function JF. */ 506union parameter_info * 507ipa_jf_get_info_type (struct ipa_jump_func *jf) 508{ 509 return &(jf->info_type); 510} 511 512/* Allocate and initialize ipa_node structure. 513 cgraph_node NODE points to the new allocated ipa_node. */ 514void 515ipa_node_create (struct cgraph_node *node) 516{ 517 node->aux = xcalloc (1, sizeof (struct ipa_node)); 518} 519 520/* Allocate and initialize ipa_node structure for all 521 nodes in callgraph. */ 522void 523ipa_nodes_create (void) 524{ 525 struct cgraph_node *node; 526 527 for (node = cgraph_nodes; node; node = node->next) 528 ipa_node_create (node); 529} 530 531/* Allocate and initialize ipa_edge structure. */ 532void 533ipa_edges_create (void) 534{ 535 struct cgraph_node *node; 536 struct cgraph_edge *cs; 537 538 for (node = cgraph_nodes; node; node = node->next) 539 for (cs = node->callees; cs; cs = cs->next_callee) 540 cs->aux = xcalloc (1, sizeof (struct ipa_edge)); 541} 542 543/* Free ipa_node structure. */ 544void 545ipa_nodes_free (void) 546{ 547 struct cgraph_node *node; 548 549 for (node = cgraph_nodes; node; node = node->next) 550 { 551 free (node->aux); 552 node->aux = NULL; 553 } 554} 555 556/* Free ipa_edge structure. */ 557void 558ipa_edges_free (void) 559{ 560 struct cgraph_node *node; 561 struct cgraph_edge *cs; 562 563 for (node = cgraph_nodes; node; node = node->next) 564 for (cs = node->callees; cs; cs = cs->next_callee) 565 { 566 free (cs->aux); 567 cs->aux = NULL; 568 } 569} 570 571/* Free ipa data structures of ipa_node and ipa_edge. */ 572void 573ipa_free (void) 574{ 575 struct cgraph_node *node; 576 struct cgraph_edge *cs; 577 578 for (node = cgraph_nodes; node; node = node->next) 579 { 580 if (node->aux == NULL) 581 continue; 582 if (IPA_NODE_REF (node)->ipcp_cval) 583 free (IPA_NODE_REF (node)->ipcp_cval); 584 if (IPA_NODE_REF (node)->ipa_param_tree) 585 free (IPA_NODE_REF (node)->ipa_param_tree); 586 if (IPA_NODE_REF (node)->ipa_mod) 587 free (IPA_NODE_REF (node)->ipa_mod); 588 for (cs = node->callees; cs; cs = cs->next_callee) 589 { 590 if (cs->aux) 591 if (IPA_EDGE_REF (cs)->ipa_param_map) 592 free (IPA_EDGE_REF (cs)->ipa_param_map); 593 } 594 } 595} 596 597/* Print ipa_tree_map data structures of all methods in the 598 callgraph to F. */ 599void 600ipa_method_tree_print (FILE * f) 601{ 602 int i, count; 603 tree temp; 604 struct cgraph_node *node; 605 606 fprintf (f, "\nPARAM TREE MAP PRINT\n"); 607 for (node = cgraph_nodes; node; node = node->next) 608 { 609 fprintf (f, "method %s Trees :: \n", cgraph_node_name (node)); 610 count = ipa_method_formal_count (node); 611 for (i = 0; i < count; i++) 612 { 613 temp = ipa_method_get_tree (node, i); 614 if (TREE_CODE (temp) == PARM_DECL) 615 fprintf (f, " param [%d] : %s\n", i, 616 (*lang_hooks.decl_printable_name) (temp, 2)); 617 } 618 619 } 620} 621 622/* Print ipa_modify data structures of all methods in the 623 callgraph to F. */ 624void 625ipa_method_modify_print (FILE * f) 626{ 627 int i, count; 628 bool temp; 629 struct cgraph_node *node; 630 631 fprintf (f, "\nMODIFY PRINT\n"); 632 for (node = cgraph_nodes; node; node = node->next) 633 { 634 fprintf (f, "method %s :: \n", cgraph_node_name (node)); 635 count = ipa_method_formal_count (node); 636 for (i = 0; i < count; i++) 637 { 638 temp = ipa_method_is_modified (node, i); 639 if (temp) 640 fprintf (f, " param [%d] true \n", i); 641 else 642 fprintf (f, " param [%d] false \n", i); 643 } 644 } 645} 646