1/* Interprocedural constant propagation 2 Copyright (C) 2005 Free Software Foundation, Inc. 3 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> 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 2, 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 COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22/* Interprocedural constant propagation. 23 The aim of interprocedural constant propagation (IPCP) is to find which 24 function's argument has the same constant value in each invocation throughout 25 the whole program. For example, for an application consisting of two files, 26 foo1.c, foo2.c: 27 28 foo1.c contains : 29 30 int f (int x) 31 { 32 g (x); 33 } 34 void main (void) 35 { 36 f (3); 37 h (3); 38 } 39 40 foo2.c contains : 41 42 int h (int y) 43 { 44 g (y); 45 } 46 int g (int y) 47 { 48 printf ("value is %d",y); 49 } 50 51 The IPCP algorithm will find that g's formal argument y 52 is always called with the value 3. 53 54 The algorithm used is based on "Interprocedural Constant Propagation", 55 by Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, 56 pg 152-161 57 58 The optimization is divided into three stages: 59 60 First stage - intraprocedural analysis 61 ======================================= 62 This phase computes jump_function and modify information. 63 64 A jump function for a callsite represents the values passed as actual 65 arguments 66 of the callsite. There are three types of values : 67 Formal - the caller's formal parameter is passed as an actual argument. 68 Constant - a constant is passed as a an actual argument. 69 Unknown - neither of the above. 70 71 In order to compute the jump functions, we need the modify information for 72 the formal parameters of methods. 73 74 The jump function info, ipa_jump_func, is defined in ipa_edge 75 structure (defined in ipa_prop.h and pointed to by cgraph_node->aux) 76 The modify info, ipa_modify, is defined in ipa_node structure 77 (defined in ipa_prop.h and pointed to by cgraph_edge->aux). 78 79 -ipcp_init_stage() is the first stage driver. 80 81 Second stage - interprocedural analysis 82 ======================================== 83 This phase does the interprocedural constant propagation. 84 It computes for all formal parameters in the program 85 their cval value that may be: 86 TOP - unknown. 87 BOTTOM - non constant. 88 CONSTANT_TYPE - constant value. 89 90 Cval of formal f will have a constant value if all callsites to this 91 function have the same constant value passed to f. 92 93 The cval info, ipcp_formal, is defined in ipa_node structure 94 (defined in ipa_prop.h and pointed to by cgraph_edge->aux). 95 96 -ipcp_iterate_stage() is the second stage driver. 97 98 Third phase - transformation of methods code 99 ============================================ 100 Propagates the constant-valued formals into the function. 101 For each method mt, whose parameters are consts, we create a clone/version. 102 103 We use two ways to annotate the versioned function with the constant 104 formal information: 105 1. We insert an assignment statement 'parameter = const' at the beginning 106 of the cloned method. 107 2. For read-only formals whose address is not taken, we replace all uses 108 of the formal with the constant (we provide versioning with an 109 ipa_replace_map struct representing the trees we want to replace). 110 111 We also need to modify some callsites to call to the cloned methods instead 112 of the original ones. For a callsite passing an argument found to be a 113 constant by IPCP, there are two different cases to handle: 114 1. A constant is passed as an argument. 115 2. A parameter (of the caller) passed as an argument (pass through argument). 116 117 In the first case, the callsite in the original caller should be redirected 118 to call the cloned callee. 119 In the second case, both the caller and the callee have clones 120 and the callsite of the cloned caller would be redirected to call to 121 the cloned callee. 122 123 The callgraph is updated accordingly. 124 125 This update is done in two stages: 126 First all cloned methods are created during a traversal of the callgraph, 127 during which all callsites are redirected to call the cloned method. 128 Then the callsites are traversed and updated as described above. 129 130 -ipcp_insert_stage() is the third phase driver. 131 132*/ 133 134#include "config.h" 135#include "system.h" 136#include "coretypes.h" 137#include "tree.h" 138#include "target.h" 139#include "cgraph.h" 140#include "ipa-prop.h" 141#include "tree-flow.h" 142#include "tree-pass.h" 143#include "flags.h" 144#include "timevar.h" 145#include "diagnostic.h" 146 147/* Get orig node field of ipa_node associated with method MT. */ 148static inline struct cgraph_node * 149ipcp_method_orig_node (struct cgraph_node *mt) 150{ 151 return IPA_NODE_REF (mt)->ipcp_orig_node; 152} 153 154/* Return true if NODE is a cloned/versioned method. */ 155static inline bool 156ipcp_method_is_cloned (struct cgraph_node *node) 157{ 158 return (ipcp_method_orig_node (node) != NULL); 159} 160 161/* Set ORIG_NODE in ipa_node associated with method NODE. */ 162static inline void 163ipcp_method_set_orig_node (struct cgraph_node *node, 164 struct cgraph_node *orig_node) 165{ 166 IPA_NODE_REF (node)->ipcp_orig_node = orig_node; 167} 168 169/* Create ipa_node and its data structures for NEW_NODE. 170 Set ORIG_NODE as the orig_node field in ipa_node. */ 171static void 172ipcp_cloned_create (struct cgraph_node *orig_node, 173 struct cgraph_node *new_node) 174{ 175 ipa_node_create (new_node); 176 ipcp_method_set_orig_node (new_node, orig_node); 177 ipa_method_formal_compute_count (new_node); 178 ipa_method_compute_tree_map (new_node); 179} 180 181/* Return cval_type field of CVAL. */ 182static inline enum cvalue_type 183ipcp_cval_get_cvalue_type (struct ipcp_formal *cval) 184{ 185 return cval->cval_type; 186} 187 188/* Return scale for MT. */ 189static inline gcov_type 190ipcp_method_get_scale (struct cgraph_node *mt) 191{ 192 return IPA_NODE_REF (mt)->count_scale; 193} 194 195/* Set COUNT as scale for MT. */ 196static inline void 197ipcp_method_set_scale (struct cgraph_node *node, gcov_type count) 198{ 199 IPA_NODE_REF (node)->count_scale = count; 200} 201 202/* Set TYPE as cval_type field of CVAL. */ 203static inline void 204ipcp_cval_set_cvalue_type (struct ipcp_formal *cval, enum cvalue_type type) 205{ 206 cval->cval_type = type; 207} 208 209/* Return cvalue field of CVAL. */ 210static inline union parameter_info * 211ipcp_cval_get_cvalue (struct ipcp_formal *cval) 212{ 213 return &(cval->cvalue); 214} 215 216/* Set VALUE as cvalue field CVAL. */ 217static inline void 218ipcp_cval_set_cvalue (struct ipcp_formal *cval, union parameter_info *value, 219 enum cvalue_type type) 220{ 221 if (type == CONST_VALUE || type == CONST_VALUE_REF) 222 cval->cvalue.value = value->value; 223} 224 225/* Return whether TYPE is a constant type. */ 226static bool 227ipcp_type_is_const (enum cvalue_type type) 228{ 229 if (type == CONST_VALUE || type == CONST_VALUE_REF) 230 return true; 231 else 232 return false; 233} 234 235/* Return true if CONST_VAL1 and CONST_VAL2 are equal. */ 236static inline bool 237ipcp_cval_equal_cvalues (union parameter_info *const_val1, 238 union parameter_info *const_val2, 239 enum cvalue_type type1, enum cvalue_type type2) 240{ 241 gcc_assert (ipcp_type_is_const (type1) && ipcp_type_is_const (type2)); 242 if (type1 != type2) 243 return false; 244 245 if (operand_equal_p (const_val1->value, const_val2->value, 0)) 246 return true; 247 248 return false; 249} 250 251/* Compute Meet arithmetics: 252 Meet (BOTTOM, x) = BOTTOM 253 Meet (TOP,x) = x 254 Meet (const_a,const_b) = BOTTOM, if const_a != const_b. 255 MEET (const_a,const_b) = const_a, if const_a == const_b.*/ 256static void 257ipcp_cval_meet (struct ipcp_formal *cval, struct ipcp_formal *cval1, 258 struct ipcp_formal *cval2) 259{ 260 if (ipcp_cval_get_cvalue_type (cval1) == BOTTOM 261 || ipcp_cval_get_cvalue_type (cval2) == BOTTOM) 262 { 263 ipcp_cval_set_cvalue_type (cval, BOTTOM); 264 return; 265 } 266 if (ipcp_cval_get_cvalue_type (cval1) == TOP) 267 { 268 ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval2)); 269 ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval2), 270 ipcp_cval_get_cvalue_type (cval2)); 271 return; 272 } 273 if (ipcp_cval_get_cvalue_type (cval2) == TOP) 274 { 275 ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval1)); 276 ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval1), 277 ipcp_cval_get_cvalue_type (cval1)); 278 return; 279 } 280 if (!ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1), 281 ipcp_cval_get_cvalue (cval2), 282 ipcp_cval_get_cvalue_type (cval1), 283 ipcp_cval_get_cvalue_type (cval2))) 284 { 285 ipcp_cval_set_cvalue_type (cval, BOTTOM); 286 return; 287 } 288 ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval1)); 289 ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval1), 290 ipcp_cval_get_cvalue_type (cval1)); 291} 292 293/* Return cval structure for the formal at index INFO_TYPE in MT. */ 294static inline struct ipcp_formal * 295ipcp_method_cval (struct cgraph_node *mt, int info_type) 296{ 297 return &(IPA_NODE_REF (mt)->ipcp_cval[info_type]); 298} 299 300/* Given the jump function (TYPE, INFO_TYPE), compute a new value of CVAL. 301 If TYPE is FORMAL_IPA_TYPE, the cval of the corresponding formal is 302 drawn from MT. */ 303static void 304ipcp_cval_compute (struct ipcp_formal *cval, struct cgraph_node *mt, 305 enum jump_func_type type, union parameter_info *info_type) 306{ 307 if (type == UNKNOWN_IPATYPE) 308 ipcp_cval_set_cvalue_type (cval, BOTTOM); 309 else if (type == CONST_IPATYPE) 310 { 311 ipcp_cval_set_cvalue_type (cval, CONST_VALUE); 312 ipcp_cval_set_cvalue (cval, info_type, CONST_VALUE); 313 } 314 else if (type == CONST_IPATYPE_REF) 315 { 316 ipcp_cval_set_cvalue_type (cval, CONST_VALUE_REF); 317 ipcp_cval_set_cvalue (cval, info_type, CONST_VALUE_REF); 318 } 319 else if (type == FORMAL_IPATYPE) 320 { 321 enum cvalue_type type = 322 ipcp_cval_get_cvalue_type (ipcp_method_cval 323 (mt, info_type->formal_id)); 324 ipcp_cval_set_cvalue_type (cval, type); 325 ipcp_cval_set_cvalue (cval, 326 ipcp_cval_get_cvalue (ipcp_method_cval 327 (mt, info_type->formal_id)), 328 type); 329 } 330} 331 332/* True when CVAL1 and CVAL2 values are not the same. */ 333static bool 334ipcp_cval_changed (struct ipcp_formal *cval1, struct ipcp_formal *cval2) 335{ 336 if (ipcp_cval_get_cvalue_type (cval1) == ipcp_cval_get_cvalue_type (cval2)) 337 { 338 if (ipcp_cval_get_cvalue_type (cval1) != CONST_VALUE && 339 ipcp_cval_get_cvalue_type (cval1) != CONST_VALUE_REF) 340 return false; 341 if (ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1), 342 ipcp_cval_get_cvalue (cval2), 343 ipcp_cval_get_cvalue_type (cval1), 344 ipcp_cval_get_cvalue_type (cval2))) 345 return false; 346 } 347 return true; 348} 349 350/* Create cval structure for method MT. */ 351static inline void 352ipcp_formal_create (struct cgraph_node *mt) 353{ 354 IPA_NODE_REF (mt)->ipcp_cval = 355 XCNEWVEC (struct ipcp_formal, ipa_method_formal_count (mt)); 356} 357 358/* Set cval structure of I-th formal of MT to CVAL. */ 359static inline void 360ipcp_method_cval_set (struct cgraph_node *mt, int i, struct ipcp_formal *cval) 361{ 362 IPA_NODE_REF (mt)->ipcp_cval[i].cval_type = cval->cval_type; 363 ipcp_cval_set_cvalue (ipcp_method_cval (mt, i), 364 ipcp_cval_get_cvalue (cval), cval->cval_type); 365} 366 367/* Set type of cval structure of formal I of MT to CVAL_TYPE1. */ 368static inline void 369ipcp_method_cval_set_cvalue_type (struct cgraph_node *mt, int i, 370 enum cvalue_type cval_type1) 371{ 372 IPA_NODE_REF (mt)->ipcp_cval[i].cval_type = cval_type1; 373} 374 375/* Print ipcp_cval data structures to F. */ 376static void 377ipcp_method_cval_print (FILE * f) 378{ 379 struct cgraph_node *node; 380 int i, count; 381 tree cvalue; 382 383 fprintf (f, "\nCVAL PRINT\n"); 384 for (node = cgraph_nodes; node; node = node->next) 385 { 386 fprintf (f, "Printing cvals %s:\n", cgraph_node_name (node)); 387 count = ipa_method_formal_count (node); 388 for (i = 0; i < count; i++) 389 { 390 if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) 391 == CONST_VALUE 392 || ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) == 393 CONST_VALUE_REF) 394 { 395 fprintf (f, " param [%d]: ", i); 396 fprintf (f, "type is CONST "); 397 cvalue = 398 ipcp_cval_get_cvalue (ipcp_method_cval (node, i))-> 399 value; 400 print_generic_expr (f, cvalue, 0); 401 fprintf (f, "\n"); 402 } 403 else if (ipcp_method_cval (node, i)->cval_type == TOP) 404 fprintf (f, "param [%d]: type is TOP \n", i); 405 else 406 fprintf (f, "param [%d]: type is BOTTOM \n", i); 407 } 408 } 409} 410 411/* Initialize ipcp_cval array of MT with TOP values. 412 All cvals for a method's formal parameters are initialized to BOTTOM 413 The currently supported types are integer types, real types and 414 Fortran constants (i.e. references to constants defined as 415 const_decls). All other types are not analyzed and therefore are 416 assigned with BOTTOM. */ 417static void 418ipcp_method_cval_init (struct cgraph_node *mt) 419{ 420 int i; 421 tree parm_tree; 422 423 ipcp_formal_create (mt); 424 for (i = 0; i < ipa_method_formal_count (mt); i++) 425 { 426 parm_tree = ipa_method_get_tree (mt, i); 427 if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree)) 428 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree)) 429 || POINTER_TYPE_P (TREE_TYPE (parm_tree))) 430 ipcp_method_cval_set_cvalue_type (mt, i, TOP); 431 else 432 ipcp_method_cval_set_cvalue_type (mt, i, BOTTOM); 433 } 434} 435 436/* Create a new assignment statment and make 437 it the first statement in the function FN 438 tree. 439 PARM1 is the lhs of the assignment and 440 VAL is the rhs. */ 441static void 442constant_val_insert (tree fn, tree parm1, tree val) 443{ 444 struct function *func; 445 tree init_stmt; 446 edge e_step; 447 edge_iterator ei; 448 449 init_stmt = build2 (MODIFY_EXPR, void_type_node, parm1, val); 450 func = DECL_STRUCT_FUNCTION (fn); 451 cfun = func; 452 current_function_decl = fn; 453 if (ENTRY_BLOCK_PTR_FOR_FUNCTION (func)->succs) 454 FOR_EACH_EDGE (e_step, ei, ENTRY_BLOCK_PTR_FOR_FUNCTION (func)->succs) 455 bsi_insert_on_edge_immediate (e_step, init_stmt); 456} 457 458/* build INTEGER_CST tree with type TREE_TYPE and 459 value according to CVALUE. Return the tree. */ 460static tree 461build_const_val (union parameter_info *cvalue, enum cvalue_type type, 462 tree tree_type) 463{ 464 tree const_val = NULL; 465 466 gcc_assert (ipcp_type_is_const (type)); 467 const_val = fold_convert (tree_type, cvalue->value); 468 return const_val; 469} 470 471/* Build the tree representing the constant and call 472 constant_val_insert(). */ 473static void 474ipcp_propagate_const (struct cgraph_node *mt, int param, 475 union parameter_info *cvalue ,enum cvalue_type type) 476{ 477 tree fndecl; 478 tree const_val; 479 tree parm_tree; 480 481 if (dump_file) 482 fprintf (dump_file, "propagating const to %s\n", cgraph_node_name (mt)); 483 fndecl = mt->decl; 484 parm_tree = ipa_method_get_tree (mt, param); 485 const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree)); 486 constant_val_insert (fndecl, parm_tree, const_val); 487} 488 489/* Compute the proper scale for NODE. It is the ratio between 490 the number of direct calls (represented on the incoming 491 cgraph_edges) and sum of all invocations of NODE (represented 492 as count in cgraph_node). */ 493static void 494ipcp_method_compute_scale (struct cgraph_node *node) 495{ 496 gcov_type sum; 497 struct cgraph_edge *cs; 498 499 sum = 0; 500 /* Compute sum of all counts of callers. */ 501 for (cs = node->callers; cs != NULL; cs = cs->next_caller) 502 sum += cs->count; 503 if (node->count == 0) 504 ipcp_method_set_scale (node, 0); 505 else 506 ipcp_method_set_scale (node, sum * REG_BR_PROB_BASE / node->count); 507} 508 509/* Initialization and computation of IPCP data structures. 510 It is an intraprocedural 511 analysis of methods, which gathers information to be propagated 512 later on. */ 513static void 514ipcp_init_stage (void) 515{ 516 struct cgraph_node *node; 517 struct cgraph_edge *cs; 518 519 for (node = cgraph_nodes; node; node = node->next) 520 { 521 ipa_method_formal_compute_count (node); 522 ipa_method_compute_tree_map (node); 523 ipcp_method_cval_init (node); 524 ipa_method_compute_modify (node); 525 ipcp_method_compute_scale (node); 526 } 527 for (node = cgraph_nodes; node; node = node->next) 528 { 529 /* building jump functions */ 530 for (cs = node->callees; cs; cs = cs->next_callee) 531 { 532 ipa_callsite_compute_count (cs); 533 if (ipa_callsite_param_count (cs) 534 != ipa_method_formal_count (cs->callee)) 535 { 536 /* Handle cases of functions with 537 a variable number of parameters. */ 538 ipa_callsite_param_count_set (cs, 0); 539 ipa_method_formal_count_set (cs->callee, 0); 540 } 541 else 542 ipa_callsite_compute_param (cs); 543 } 544 } 545} 546 547/* Return true if there are some formal parameters whose value is TOP. 548 Change their values to BOTTOM, since they weren't determined. */ 549static bool 550ipcp_after_propagate (void) 551{ 552 int i, count; 553 struct cgraph_node *node; 554 bool prop_again; 555 556 prop_again = false; 557 for (node = cgraph_nodes; node; node = node->next) 558 { 559 count = ipa_method_formal_count (node); 560 for (i = 0; i < count; i++) 561 if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) == TOP) 562 { 563 prop_again = true; 564 ipcp_method_cval_set_cvalue_type (node, i, BOTTOM); 565 } 566 } 567 return prop_again; 568} 569 570/* Interprocedural analysis. The algorithm propagates constants from 571 the caller's parameters to the callee's arguments. */ 572static void 573ipcp_propagate_stage (void) 574{ 575 int i; 576 struct ipcp_formal cval1 = { 0, {0} }, cval = { 0,{0} }; 577 struct ipcp_formal *cval2; 578 struct cgraph_node *mt, *callee; 579 struct cgraph_edge *cs; 580 struct ipa_jump_func *jump_func; 581 enum jump_func_type type; 582 union parameter_info *info_type; 583 ipa_methodlist_p wl; 584 int count; 585 586 /* Initialize worklist to contain all methods. */ 587 wl = ipa_methodlist_init (); 588 while (ipa_methodlist_not_empty (wl)) 589 { 590 mt = ipa_remove_method (&wl); 591 for (cs = mt->callees; cs; cs = cs->next_callee) 592 { 593 callee = ipa_callsite_callee (cs); 594 count = ipa_callsite_param_count (cs); 595 for (i = 0; i < count; i++) 596 { 597 jump_func = ipa_callsite_param (cs, i); 598 type = get_type (jump_func); 599 info_type = ipa_jf_get_info_type (jump_func); 600 ipcp_cval_compute (&cval1, mt, type, info_type); 601 cval2 = ipcp_method_cval (callee, i); 602 ipcp_cval_meet (&cval, &cval1, cval2); 603 if (ipcp_cval_changed (&cval, cval2)) 604 { 605 ipcp_method_cval_set (callee, i, &cval); 606 ipa_add_method (&wl, callee); 607 } 608 } 609 } 610 } 611} 612 613/* Call the constant propagation algorithm and re-call it if necessary 614 (if there are undetermined values left). */ 615static void 616ipcp_iterate_stage (void) 617{ 618 ipcp_propagate_stage (); 619 if (ipcp_after_propagate ()) 620 /* Some cvals have changed from TOP to BOTTOM. 621 This change should be propagated. */ 622 ipcp_propagate_stage (); 623} 624 625/* Check conditions to forbid constant insertion to MT. */ 626static bool 627ipcp_method_dont_insert_const (struct cgraph_node *mt) 628{ 629 /* ??? Handle pending sizes case. */ 630 if (DECL_UNINLINABLE (mt->decl)) 631 return true; 632 return false; 633} 634 635/* Print ipa_jump_func data structures to F. */ 636static void 637ipcp_callsite_param_print (FILE * f) 638{ 639 struct cgraph_node *node; 640 int i, count; 641 struct cgraph_edge *cs; 642 struct ipa_jump_func *jump_func; 643 enum jump_func_type type; 644 tree info_type; 645 646 fprintf (f, "\nCALLSITE PARAM PRINT\n"); 647 for (node = cgraph_nodes; node; node = node->next) 648 { 649 for (cs = node->callees; cs; cs = cs->next_callee) 650 { 651 fprintf (f, "callsite %s ", cgraph_node_name (node)); 652 fprintf (f, "-> %s :: \n", cgraph_node_name (cs->callee)); 653 count = ipa_callsite_param_count (cs); 654 for (i = 0; i < count; i++) 655 { 656 jump_func = ipa_callsite_param (cs, i); 657 type = get_type (jump_func); 658 659 fprintf (f, " param %d: ", i); 660 if (type == UNKNOWN_IPATYPE) 661 fprintf (f, "UNKNOWN\n"); 662 else if (type == CONST_IPATYPE || type == CONST_IPATYPE_REF) 663 { 664 info_type = 665 ipa_jf_get_info_type (jump_func)->value; 666 fprintf (f, "CONST : "); 667 print_generic_expr (f, info_type, 0); 668 fprintf (f, "\n"); 669 } 670 else if (type == FORMAL_IPATYPE) 671 { 672 fprintf (f, "FORMAL : "); 673 fprintf (f, "%d\n", 674 ipa_jf_get_info_type (jump_func)->formal_id); 675 } 676 } 677 } 678 } 679} 680 681/* Print count scale data structures. */ 682static void 683ipcp_method_scale_print (FILE * f) 684{ 685 struct cgraph_node *node; 686 687 for (node = cgraph_nodes; node; node = node->next) 688 { 689 fprintf (f, "printing scale for %s: ", cgraph_node_name (node)); 690 fprintf (f, "value is " HOST_WIDE_INT_PRINT_DEC 691 " \n", (HOST_WIDE_INT) ipcp_method_get_scale (node)); 692 } 693} 694 695/* Print counts of all cgraph nodes. */ 696static void 697ipcp_profile_mt_count_print (FILE * f) 698{ 699 struct cgraph_node *node; 700 701 for (node = cgraph_nodes; node; node = node->next) 702 { 703 fprintf (f, "method %s: ", cgraph_node_name (node)); 704 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC 705 " \n", (HOST_WIDE_INT) node->count); 706 } 707} 708 709/* Print counts of all cgraph edges. */ 710static void 711ipcp_profile_cs_count_print (FILE * f) 712{ 713 struct cgraph_node *node; 714 struct cgraph_edge *cs; 715 716 for (node = cgraph_nodes; node; node = node->next) 717 { 718 for (cs = node->callees; cs; cs = cs->next_callee) 719 { 720 fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller), 721 cgraph_node_name (cs->callee)); 722 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC " \n", 723 (HOST_WIDE_INT) cs->count); 724 } 725 } 726} 727 728/* Print all counts and probabilities of cfg edges of all methods. */ 729static void 730ipcp_profile_edge_print (FILE * f) 731{ 732 struct cgraph_node *node; 733 basic_block bb; 734 edge_iterator ei; 735 edge e; 736 737 for (node = cgraph_nodes; node; node = node->next) 738 { 739 fprintf (f, "method %s: \n", cgraph_node_name (node)); 740 if (DECL_SAVED_TREE (node->decl)) 741 { 742 bb = 743 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl)); 744 fprintf (f, "ENTRY: "); 745 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC 746 " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency); 747 748 if (bb->succs) 749 FOR_EACH_EDGE (e, ei, bb->succs) 750 { 751 if (e->dest == 752 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION 753 (node->decl))) 754 fprintf (f, "edge ENTRY -> EXIT, Count"); 755 else 756 fprintf (f, "edge ENTRY -> %d, Count", e->dest->index); 757 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC 758 " Prob %d\n", (HOST_WIDE_INT) e->count, 759 e->probability); 760 } 761 FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl)) 762 { 763 fprintf (f, "bb[%d]: ", bb->index); 764 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC 765 " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency); 766 FOR_EACH_EDGE (e, ei, bb->succs) 767 { 768 if (e->dest == 769 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION 770 (node->decl))) 771 fprintf (f, "edge %d -> EXIT, Count", e->src->index); 772 else 773 fprintf (f, "edge %d -> %d, Count", e->src->index, 774 e->dest->index); 775 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC " Prob %d\n", 776 (HOST_WIDE_INT) e->count, e->probability); 777 } 778 } 779 } 780 } 781} 782 783/* Print counts and frequencies for all basic blocks of all methods. */ 784static void 785ipcp_profile_bb_print (FILE * f) 786{ 787 basic_block bb; 788 struct cgraph_node *node; 789 790 for (node = cgraph_nodes; node; node = node->next) 791 { 792 fprintf (f, "method %s: \n", cgraph_node_name (node)); 793 if (DECL_SAVED_TREE (node->decl)) 794 { 795 bb = 796 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl)); 797 fprintf (f, "ENTRY: Count"); 798 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC 799 " Frquency %d\n", (HOST_WIDE_INT) bb->count, 800 bb->frequency); 801 802 FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl)) 803 { 804 fprintf (f, "bb[%d]: Count", bb->index); 805 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC 806 " Frequency %d\n", (HOST_WIDE_INT) bb->count, 807 bb->frequency); 808 } 809 bb = 810 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl)); 811 fprintf (f, "EXIT: Count"); 812 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC 813 " Frequency %d\n", (HOST_WIDE_INT) bb->count, 814 bb->frequency); 815 816 } 817 } 818} 819 820/* Print all IPCP data structures to F. */ 821static void 822ipcp_structures_print (FILE * f) 823{ 824 ipcp_method_cval_print (f); 825 ipcp_method_scale_print (f); 826 ipa_method_tree_print (f); 827 ipa_method_modify_print (f); 828 ipcp_callsite_param_print (f); 829} 830 831/* Print profile info for all methods. */ 832static void 833ipcp_profile_print (FILE * f) 834{ 835 fprintf (f, "\nNODE COUNTS :\n"); 836 ipcp_profile_mt_count_print (f); 837 fprintf (f, "\nCS COUNTS stage:\n"); 838 ipcp_profile_cs_count_print (f); 839 fprintf (f, "\nBB COUNTS and FREQUENCIES :\n"); 840 ipcp_profile_bb_print (f); 841 fprintf (f, "\nCFG EDGES COUNTS and PROBABILITIES :\n"); 842 ipcp_profile_edge_print (f); 843} 844 845/* Build and initialize ipa_replace_map struct 846 according to TYPE. This struct is read by versioning, which 847 operates according to the flags sent. PARM_TREE is the 848 formal's tree found to be constant. CVALUE represents the constant. */ 849static struct ipa_replace_map * 850ipcp_replace_map_create (enum cvalue_type type, tree parm_tree, 851 union parameter_info *cvalue) 852{ 853 struct ipa_replace_map *replace_map; 854 tree const_val; 855 856 replace_map = XCNEW (struct ipa_replace_map); 857 gcc_assert (ipcp_type_is_const (type)); 858 if (type == CONST_VALUE_REF ) 859 { 860 const_val = 861 build_const_val (cvalue, type, TREE_TYPE (TREE_TYPE (parm_tree))); 862 replace_map->old_tree = parm_tree; 863 replace_map->new_tree = const_val; 864 replace_map->replace_p = true; 865 replace_map->ref_p = true; 866 } 867 else if (TREE_READONLY (parm_tree) && !TREE_ADDRESSABLE (parm_tree)) 868 { 869 const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree)); 870 replace_map->old_tree = parm_tree; 871 replace_map->new_tree = const_val; 872 replace_map->replace_p = true; 873 replace_map->ref_p = false; 874 } 875 else 876 { 877 replace_map->old_tree = NULL; 878 replace_map->new_tree = NULL; 879 replace_map->replace_p = false; 880 replace_map->ref_p = false; 881 } 882 883 return replace_map; 884} 885 886/* Return true if this callsite should be redirected to 887 the orig callee (instead of the cloned one). */ 888static bool 889ipcp_redirect (struct cgraph_edge *cs) 890{ 891 struct cgraph_node *caller, *callee, *orig_callee; 892 int i, count; 893 struct ipa_jump_func *jump_func; 894 enum jump_func_type type; 895 enum cvalue_type cval_type; 896 897 caller = cs->caller; 898 callee = cs->callee; 899 orig_callee = ipcp_method_orig_node (callee); 900 count = ipa_method_formal_count (orig_callee); 901 for (i = 0; i < count; i++) 902 { 903 cval_type = 904 ipcp_cval_get_cvalue_type (ipcp_method_cval (orig_callee, i)); 905 if (ipcp_type_is_const (cval_type)) 906 { 907 jump_func = ipa_callsite_param (cs, i); 908 type = get_type (jump_func); 909 if (type != CONST_IPATYPE 910 && type != CONST_IPATYPE_REF) 911 return true; 912 } 913 } 914 915 return false; 916} 917 918/* Fix the callsites and the callgraph after function cloning was done. */ 919static void 920ipcp_update_callgraph (void) 921{ 922 struct cgraph_node *node, *orig_callee; 923 struct cgraph_edge *cs; 924 925 for (node = cgraph_nodes; node; node = node->next) 926 { 927 /* want to fix only original nodes */ 928 if (ipcp_method_is_cloned (node)) 929 continue; 930 for (cs = node->callees; cs; cs = cs->next_callee) 931 if (ipcp_method_is_cloned (cs->callee)) 932 { 933 /* Callee is a cloned node */ 934 orig_callee = ipcp_method_orig_node (cs->callee); 935 if (ipcp_redirect (cs)) 936 { 937 cgraph_redirect_edge_callee (cs, orig_callee); 938 TREE_OPERAND (TREE_OPERAND 939 (get_call_expr_in (cs->call_stmt), 0), 0) = 940 orig_callee->decl; 941 } 942 } 943 } 944} 945 946/* Update all cfg basic blocks in NODE according to SCALE. */ 947static void 948ipcp_update_bb_counts (struct cgraph_node *node, gcov_type scale) 949{ 950 basic_block bb; 951 952 FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl)) 953 bb->count = bb->count * scale / REG_BR_PROB_BASE; 954} 955 956/* Update all cfg edges in NODE according to SCALE. */ 957static void 958ipcp_update_edges_counts (struct cgraph_node *node, gcov_type scale) 959{ 960 basic_block bb; 961 edge_iterator ei; 962 edge e; 963 964 FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl)) 965 FOR_EACH_EDGE (e, ei, bb->succs) 966 e->count = e->count * scale / REG_BR_PROB_BASE; 967} 968 969/* Update profiling info for versioned methods and the 970 methods they were versioned from. */ 971static void 972ipcp_update_profiling (void) 973{ 974 struct cgraph_node *node, *orig_node; 975 gcov_type scale, scale_complement; 976 struct cgraph_edge *cs; 977 978 for (node = cgraph_nodes; node; node = node->next) 979 { 980 if (ipcp_method_is_cloned (node)) 981 { 982 orig_node = ipcp_method_orig_node (node); 983 scale = ipcp_method_get_scale (orig_node); 984 node->count = orig_node->count * scale / REG_BR_PROB_BASE; 985 scale_complement = REG_BR_PROB_BASE - scale; 986 orig_node->count = 987 orig_node->count * scale_complement / REG_BR_PROB_BASE; 988 for (cs = node->callees; cs; cs = cs->next_callee) 989 cs->count = cs->count * scale / REG_BR_PROB_BASE; 990 for (cs = orig_node->callees; cs; cs = cs->next_callee) 991 cs->count = cs->count * scale_complement / REG_BR_PROB_BASE; 992 ipcp_update_bb_counts (node, scale); 993 ipcp_update_bb_counts (orig_node, scale_complement); 994 ipcp_update_edges_counts (node, scale); 995 ipcp_update_edges_counts (orig_node, scale_complement); 996 } 997 } 998} 999 1000/* Propagate the constant parameters found by ipcp_iterate_stage() 1001 to the function's code. */ 1002static void 1003ipcp_insert_stage (void) 1004{ 1005 struct cgraph_node *node, *node1 = NULL; 1006 int i, const_param; 1007 union parameter_info *cvalue; 1008 VEC(cgraph_edge_p,heap) *redirect_callers; 1009 varray_type replace_trees; 1010 struct cgraph_edge *cs; 1011 int node_callers, count; 1012 tree parm_tree; 1013 enum cvalue_type type; 1014 struct ipa_replace_map *replace_param; 1015 1016 for (node = cgraph_nodes; node; node = node->next) 1017 { 1018 /* Propagation of the constant is forbidden in 1019 certain conditions. */ 1020 if (ipcp_method_dont_insert_const (node)) 1021 continue; 1022 const_param = 0; 1023 count = ipa_method_formal_count (node); 1024 for (i = 0; i < count; i++) 1025 { 1026 type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)); 1027 if (ipcp_type_is_const (type)) 1028 const_param++; 1029 } 1030 if (const_param == 0) 1031 continue; 1032 VARRAY_GENERIC_PTR_INIT (replace_trees, const_param, "replace_trees"); 1033 for (i = 0; i < count; i++) 1034 { 1035 type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)); 1036 if (ipcp_type_is_const (type)) 1037 { 1038 cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i)); 1039 parm_tree = ipa_method_get_tree (node, i); 1040 replace_param = 1041 ipcp_replace_map_create (type, parm_tree, cvalue); 1042 VARRAY_PUSH_GENERIC_PTR (replace_trees, replace_param); 1043 } 1044 } 1045 /* Compute how many callers node has. */ 1046 node_callers = 0; 1047 for (cs = node->callers; cs != NULL; cs = cs->next_caller) 1048 node_callers++; 1049 redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers); 1050 for (cs = node->callers; cs != NULL; cs = cs->next_caller) 1051 VEC_quick_push (cgraph_edge_p, redirect_callers, cs); 1052 /* Redirecting all the callers of the node to the 1053 new versioned node. */ 1054 node1 = 1055 cgraph_function_versioning (node, redirect_callers, replace_trees); 1056 VEC_free (cgraph_edge_p, heap, redirect_callers); 1057 VARRAY_CLEAR (replace_trees); 1058 if (node1 == NULL) 1059 continue; 1060 if (dump_file) 1061 fprintf (dump_file, "versioned function %s\n", 1062 cgraph_node_name (node)); 1063 ipcp_cloned_create (node, node1); 1064 for (i = 0; i < count; i++) 1065 { 1066 type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)); 1067 if (ipcp_type_is_const (type)) 1068 { 1069 cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i)); 1070 parm_tree = ipa_method_get_tree (node, i); 1071 if (type != CONST_VALUE_REF 1072 && !TREE_READONLY (parm_tree)) 1073 ipcp_propagate_const (node1, i, cvalue, type); 1074 } 1075 } 1076 } 1077 ipcp_update_callgraph (); 1078 ipcp_update_profiling (); 1079} 1080 1081/* The IPCP driver. */ 1082unsigned int 1083ipcp_driver (void) 1084{ 1085 if (dump_file) 1086 fprintf (dump_file, "\nIPA constant propagation start:\n"); 1087 ipa_nodes_create (); 1088 ipa_edges_create (); 1089 /* 1. Call the init stage to initialize 1090 the ipa_node and ipa_edge structures. */ 1091 ipcp_init_stage (); 1092 if (dump_file) 1093 { 1094 fprintf (dump_file, "\nIPA structures before propagation:\n"); 1095 ipcp_structures_print (dump_file); 1096 } 1097 /* 2. Do the interprocedural propagation. */ 1098 ipcp_iterate_stage (); 1099 if (dump_file) 1100 { 1101 fprintf (dump_file, "\nIPA structures after propagation:\n"); 1102 ipcp_structures_print (dump_file); 1103 fprintf (dump_file, "\nProfiling info before insert stage:\n"); 1104 ipcp_profile_print (dump_file); 1105 } 1106 /* 3. Insert the constants found to the functions. */ 1107 ipcp_insert_stage (); 1108 if (dump_file) 1109 { 1110 fprintf (dump_file, "\nProfiling info after insert stage:\n"); 1111 ipcp_profile_print (dump_file); 1112 } 1113 /* Free all IPCP structures. */ 1114 ipa_free (); 1115 ipa_nodes_free (); 1116 ipa_edges_free (); 1117 if (dump_file) 1118 fprintf (dump_file, "\nIPA constant propagation end\n"); 1119 cgraph_remove_unreachable_nodes (true, NULL); 1120 return 0; 1121} 1122 1123/* Gate for IPCP optimization. */ 1124static bool 1125cgraph_gate_cp (void) 1126{ 1127 return flag_ipa_cp; 1128} 1129 1130struct tree_opt_pass pass_ipa_cp = { 1131 "cp", /* name */ 1132 cgraph_gate_cp, /* gate */ 1133 ipcp_driver, /* execute */ 1134 NULL, /* sub */ 1135 NULL, /* next */ 1136 0, /* static_pass_number */ 1137 TV_IPA_CONSTANT_PROP, /* tv_id */ 1138 0, /* properties_required */ 1139 PROP_trees, /* properties_provided */ 1140 0, /* properties_destroyed */ 1141 0, /* todo_flags_start */ 1142 TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */ 1143 0 /* letter */ 1144}; 1145