Mercurial > hg > CbC > CbC_gcc
annotate gcc/ipa-cp.c @ 22:0eb6cac880f0
add cbc example of quicksort.
| author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 13 Oct 2009 17:15:58 +0900 |
| parents | 58ad6c70ea60 |
| children | 3bfb6c00c1e0 |
| rev | line source |
|---|---|
| 0 | 1 /* Interprocedural constant propagation |
| 2 Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc. | |
| 3 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> | |
| 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 /* Interprocedural constant propagation. The aim of interprocedural constant | |
| 22 propagation (IPCP) is to find which function's argument has the same | |
| 23 constant value in each invocation throughout the whole program. For example, | |
| 24 consider the following program: | |
| 25 | |
| 26 int g (int y) | |
| 27 { | |
| 28 printf ("value is %d",y); | |
| 29 } | |
| 30 | |
| 31 int f (int x) | |
| 32 { | |
| 33 g (x); | |
| 34 } | |
| 35 | |
| 36 int h (int y) | |
| 37 { | |
| 38 g (y); | |
| 39 } | |
| 40 | |
| 41 void main (void) | |
| 42 { | |
| 43 f (3); | |
| 44 h (3); | |
| 45 } | |
| 46 | |
| 47 | |
| 48 The IPCP algorithm will find that g's formal argument y is always called | |
| 49 with the value 3. | |
| 50 | |
| 51 The algorithm used is based on "Interprocedural Constant Propagation", by | |
| 52 Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, pg | |
| 53 152-161 | |
| 54 | |
| 55 The optimization is divided into three stages: | |
| 56 | |
| 57 First stage - intraprocedural analysis | |
| 58 ======================================= | |
| 59 This phase computes jump_function and modification flags. | |
| 60 | |
| 61 A jump function for a callsite represents the values passed as an actual | |
| 62 arguments of a given callsite. There are three types of values: | |
| 63 Pass through - the caller's formal parameter is passed as an actual argument. | |
| 64 Constant - a constant is passed as an actual argument. | |
| 65 Unknown - neither of the above. | |
| 66 | |
| 67 The jump function info, ipa_jump_func, is stored in ipa_edge_args | |
| 68 structure (defined in ipa_prop.h and pointed to by cgraph_node->aux) | |
| 69 modified_flags are defined in ipa_node_params structure | |
| 70 (defined in ipa_prop.h and pointed to by cgraph_edge->aux). | |
| 71 | |
| 72 -ipcp_init_stage() is the first stage driver. | |
| 73 | |
| 74 Second stage - interprocedural analysis | |
| 75 ======================================== | |
| 76 This phase does the interprocedural constant propagation. | |
| 77 It computes lattices for all formal parameters in the program | |
| 78 and their value that may be: | |
| 79 TOP - unknown. | |
| 80 BOTTOM - non constant. | |
| 81 CONSTANT - constant value. | |
| 82 | |
| 83 Lattice describing a formal parameter p will have a constant value if all | |
| 84 callsites invoking this function have the same constant value passed to p. | |
| 85 | |
| 86 The lattices are stored in ipcp_lattice which is itself in ipa_node_params | |
| 87 structure (defined in ipa_prop.h and pointed to by cgraph_edge->aux). | |
| 88 | |
| 89 -ipcp_iterate_stage() is the second stage driver. | |
| 90 | |
| 91 Third phase - transformation of function code | |
| 92 ============================================ | |
| 93 Propagates the constant-valued formals into the function. | |
| 94 For each function whose parameters are constants, we create its clone. | |
| 95 | |
| 96 Then we process the clone in two ways: | |
| 97 1. We insert an assignment statement 'parameter = const' at the beginning | |
| 98 of the cloned function. | |
| 99 2. For read-only parameters that do not live in memory, we replace all their | |
| 100 uses with the constant. | |
| 101 | |
| 102 We also need to modify some callsites to call the cloned functions instead | |
| 103 of the original ones. For a callsite passing an argument found to be a | |
| 104 constant by IPCP, there are two different cases to handle: | |
| 105 1. A constant is passed as an argument. In this case the callsite in the | |
| 106 should be redirected to call the cloned callee. | |
| 107 2. A parameter (of the caller) passed as an argument (pass through | |
| 108 argument). In such cases both the caller and the callee have clones and | |
| 109 only the callsite in the cloned caller is redirected to call to the | |
| 110 cloned callee. | |
| 111 | |
| 112 This update is done in two steps: First all cloned functions are created | |
| 113 during a traversal of the call graph, during which all callsites are | |
| 114 redirected to call the cloned function. Then the callsites are traversed | |
| 115 and many calls redirected back to fit the description above. | |
| 116 | |
| 117 -ipcp_insert_stage() is the third phase driver. | |
| 118 | |
| 119 */ | |
| 120 | |
| 121 #include "config.h" | |
| 122 #include "system.h" | |
| 123 #include "coretypes.h" | |
| 124 #include "tree.h" | |
| 125 #include "target.h" | |
| 126 #include "cgraph.h" | |
| 127 #include "ipa-prop.h" | |
| 128 #include "tree-flow.h" | |
| 129 #include "tree-pass.h" | |
| 130 #include "flags.h" | |
| 131 #include "timevar.h" | |
| 132 #include "diagnostic.h" | |
| 133 #include "tree-dump.h" | |
| 134 #include "tree-inline.h" | |
| 135 #include "fibheap.h" | |
| 136 #include "params.h" | |
| 137 | |
| 138 /* Number of functions identified as candidates for cloning. When not cloning | |
| 139 we can simplify iterate stage not forcing it to go through the decision | |
| 140 on what is profitable and what not. */ | |
| 141 static int n_cloning_candidates; | |
| 142 | |
| 143 /* Maximal count found in program. */ | |
| 144 static gcov_type max_count; | |
| 145 | |
| 146 /* Cgraph nodes that has been completely replaced by cloning during iterate | |
| 147 * stage and will be removed after ipcp is finished. */ | |
| 148 static bitmap dead_nodes; | |
| 149 | |
| 150 static void ipcp_print_profile_data (FILE *); | |
| 151 static void ipcp_function_scale_print (FILE *); | |
| 152 | |
| 153 /* Get the original node field of ipa_node_params associated with node NODE. */ | |
| 154 static inline struct cgraph_node * | |
| 155 ipcp_get_orig_node (struct cgraph_node *node) | |
| 156 { | |
| 157 return IPA_NODE_REF (node)->ipcp_orig_node; | |
| 158 } | |
| 159 | |
| 160 /* Return true if NODE describes a cloned/versioned function. */ | |
| 161 static inline bool | |
| 162 ipcp_node_is_clone (struct cgraph_node *node) | |
| 163 { | |
| 164 return (ipcp_get_orig_node (node) != NULL); | |
| 165 } | |
| 166 | |
| 167 /* Create ipa_node_params and its data structures for NEW_NODE. Set ORIG_NODE | |
| 168 as the ipcp_orig_node field in ipa_node_params. */ | |
| 169 static void | |
| 170 ipcp_init_cloned_node (struct cgraph_node *orig_node, | |
| 171 struct cgraph_node *new_node) | |
| 172 { | |
| 173 ipa_check_create_node_params (); | |
| 174 ipa_initialize_node_params (new_node); | |
| 175 IPA_NODE_REF (new_node)->ipcp_orig_node = orig_node; | |
| 176 } | |
| 177 | |
| 178 /* Perform intraprocedrual analysis needed for ipcp. */ | |
| 179 static void | |
| 180 ipcp_analyze_node (struct cgraph_node *node) | |
| 181 { | |
| 182 /* Unreachable nodes should have been eliminated before ipcp. */ | |
| 183 gcc_assert (node->needed || node->reachable); | |
| 184 | |
| 185 ipa_initialize_node_params (node); | |
| 186 ipa_detect_param_modifications (node); | |
| 187 } | |
| 188 | |
| 189 /* Recompute all local information since node might've got new | |
| 190 direct calls after cloning. */ | |
| 191 static void | |
| 192 ipcp_update_cloned_node (struct cgraph_node *new_node) | |
| 193 { | |
| 194 /* We might've introduced new direct calls. */ | |
| 195 push_cfun (DECL_STRUCT_FUNCTION (new_node->decl)); | |
| 196 current_function_decl = new_node->decl; | |
| 197 rebuild_cgraph_edges (); | |
| 198 | |
| 199 /* Indirect inlinng rely on fact that we've already analyzed | |
| 200 the body.. */ | |
| 201 if (flag_indirect_inlining) | |
| 202 { | |
| 203 struct cgraph_edge *cs; | |
| 204 | |
| 205 ipcp_analyze_node (new_node); | |
| 206 | |
| 207 for (cs = new_node->callees; cs; cs = cs->next_callee) | |
| 208 { | |
| 209 ipa_count_arguments (cs); | |
| 210 ipa_compute_jump_functions (cs); | |
| 211 } | |
| 212 } | |
| 213 pop_cfun (); | |
| 214 current_function_decl = NULL; | |
| 215 } | |
| 216 | |
| 217 /* Return scale for NODE. */ | |
| 218 static inline gcov_type | |
| 219 ipcp_get_node_scale (struct cgraph_node *node) | |
| 220 { | |
| 221 return IPA_NODE_REF (node)->count_scale; | |
| 222 } | |
| 223 | |
| 224 /* Set COUNT as scale for NODE. */ | |
| 225 static inline void | |
| 226 ipcp_set_node_scale (struct cgraph_node *node, gcov_type count) | |
| 227 { | |
| 228 IPA_NODE_REF (node)->count_scale = count; | |
| 229 } | |
| 230 | |
| 231 /* Return whether LAT is a constant lattice. */ | |
| 232 static inline bool | |
| 233 ipcp_lat_is_const (struct ipcp_lattice *lat) | |
| 234 { | |
| 235 if (lat->type == IPA_CONST_VALUE) | |
| 236 return true; | |
| 237 else | |
| 238 return false; | |
| 239 } | |
| 240 | |
| 241 /* Return whether LAT is a constant lattice that ipa-cp can actually insert | |
| 242 into the code (i.e. constants excluding member pointers and pointers). */ | |
| 243 static inline bool | |
| 244 ipcp_lat_is_insertable (struct ipcp_lattice *lat) | |
| 245 { | |
| 246 return lat->type == IPA_CONST_VALUE; | |
| 247 } | |
| 248 | |
| 249 /* Return true if LAT1 and LAT2 are equal. */ | |
| 250 static inline bool | |
| 251 ipcp_lats_are_equal (struct ipcp_lattice *lat1, struct ipcp_lattice *lat2) | |
| 252 { | |
| 253 gcc_assert (ipcp_lat_is_const (lat1) && ipcp_lat_is_const (lat2)); | |
| 254 if (lat1->type != lat2->type) | |
| 255 return false; | |
| 256 | |
| 257 if (operand_equal_p (lat1->constant, lat2->constant, 0)) | |
| 258 return true; | |
| 259 | |
| 260 return false; | |
| 261 } | |
| 262 | |
| 263 /* Compute Meet arithmetics: | |
| 264 Meet (IPA_BOTTOM, x) = IPA_BOTTOM | |
| 265 Meet (IPA_TOP,x) = x | |
| 266 Meet (const_a,const_b) = IPA_BOTTOM, if const_a != const_b. | |
| 267 MEET (const_a,const_b) = const_a, if const_a == const_b.*/ | |
| 268 static void | |
| 269 ipa_lattice_meet (struct ipcp_lattice *res, struct ipcp_lattice *lat1, | |
| 270 struct ipcp_lattice *lat2) | |
| 271 { | |
| 272 if (lat1->type == IPA_BOTTOM || lat2->type == IPA_BOTTOM) | |
| 273 { | |
| 274 res->type = IPA_BOTTOM; | |
| 275 return; | |
| 276 } | |
| 277 if (lat1->type == IPA_TOP) | |
| 278 { | |
| 279 res->type = lat2->type; | |
| 280 res->constant = lat2->constant; | |
| 281 return; | |
| 282 } | |
| 283 if (lat2->type == IPA_TOP) | |
| 284 { | |
| 285 res->type = lat1->type; | |
| 286 res->constant = lat1->constant; | |
| 287 return; | |
| 288 } | |
| 289 if (!ipcp_lats_are_equal (lat1, lat2)) | |
| 290 { | |
| 291 res->type = IPA_BOTTOM; | |
| 292 return; | |
| 293 } | |
| 294 res->type = lat1->type; | |
| 295 res->constant = lat1->constant; | |
| 296 } | |
| 297 | |
| 298 /* Return the lattice corresponding to the Ith formal parameter of the function | |
| 299 described by INFO. */ | |
| 300 static inline struct ipcp_lattice * | |
| 301 ipcp_get_lattice (struct ipa_node_params *info, int i) | |
| 302 { | |
| 303 return &(info->params[i].ipcp_lattice); | |
| 304 } | |
| 305 | |
| 306 /* Given the jump function JFUNC, compute the lattice LAT that describes the | |
| 307 value coming down the callsite. INFO describes the caller node so that | |
| 308 pass-through jump functions can be evaluated. */ | |
| 309 static void | |
| 310 ipcp_lattice_from_jfunc (struct ipa_node_params *info, struct ipcp_lattice *lat, | |
| 311 struct ipa_jump_func *jfunc) | |
| 312 { | |
| 313 if (jfunc->type == IPA_CONST) | |
| 314 { | |
| 315 lat->type = IPA_CONST_VALUE; | |
| 316 lat->constant = jfunc->value.constant; | |
| 317 } | |
| 318 else if (jfunc->type == IPA_PASS_THROUGH) | |
| 319 { | |
| 320 struct ipcp_lattice *caller_lat; | |
| 321 | |
| 322 caller_lat = ipcp_get_lattice (info, jfunc->value.formal_id); | |
| 323 lat->type = caller_lat->type; | |
| 324 lat->constant = caller_lat->constant; | |
| 325 } | |
| 326 else | |
| 327 lat->type = IPA_BOTTOM; | |
| 328 } | |
| 329 | |
| 330 /* True when OLD_LAT and NEW_LAT values are not the same. */ | |
| 331 | |
| 332 static bool | |
| 333 ipcp_lattice_changed (struct ipcp_lattice *old_lat, | |
| 334 struct ipcp_lattice *new_lat) | |
| 335 { | |
| 336 if (old_lat->type == new_lat->type) | |
| 337 { | |
| 338 if (!ipcp_lat_is_const (old_lat)) | |
| 339 return false; | |
| 340 if (ipcp_lats_are_equal (old_lat, new_lat)) | |
| 341 return false; | |
| 342 } | |
| 343 return true; | |
| 344 } | |
| 345 | |
| 346 /* Print all ipcp_lattices of all functions to F. */ | |
| 347 static void | |
| 348 ipcp_print_all_lattices (FILE * f) | |
| 349 { | |
| 350 struct cgraph_node *node; | |
| 351 int i, count; | |
| 352 | |
| 353 fprintf (f, "\nLattice:\n"); | |
| 354 for (node = cgraph_nodes; node; node = node->next) | |
| 355 { | |
| 356 struct ipa_node_params *info; | |
| 357 | |
| 358 if (!node->analyzed) | |
| 359 continue; | |
| 360 info = IPA_NODE_REF (node); | |
| 361 fprintf (f, " Node: %s:\n", cgraph_node_name (node)); | |
| 362 count = ipa_get_param_count (info); | |
| 363 for (i = 0; i < count; i++) | |
| 364 { | |
| 365 struct ipcp_lattice *lat = ipcp_get_lattice (info, i); | |
| 366 | |
| 367 fprintf (f, " param [%d]: ", i); | |
| 368 if (lat->type == IPA_CONST_VALUE) | |
| 369 { | |
| 370 fprintf (f, "type is CONST "); | |
| 371 print_generic_expr (f, lat->constant, 0); | |
| 372 fprintf (f, "\n"); | |
| 373 } | |
| 374 else if (lat->type == IPA_TOP) | |
| 375 fprintf (f, "type is TOP\n"); | |
| 376 else | |
| 377 fprintf (f, "type is BOTTOM\n"); | |
| 378 } | |
| 379 } | |
| 380 } | |
| 381 | |
| 382 /* Return true if this NODE is viable candidate for cloning. */ | |
| 383 static bool | |
| 384 ipcp_cloning_candidate_p (struct cgraph_node *node) | |
| 385 { | |
| 386 int n_calls = 0; | |
| 387 int n_hot_calls = 0; | |
| 388 gcov_type direct_call_sum = 0; | |
| 389 struct cgraph_edge *e; | |
| 390 | |
| 391 /* We never clone functions that are not visible from outside. | |
| 392 FIXME: in future we should clone such functions when they are called with | |
| 393 different constants, but current ipcp implementation is not good on this. | |
| 394 */ | |
| 395 if (!node->needed || !node->analyzed) | |
| 396 return false; | |
| 397 | |
| 398 if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE) | |
| 399 { | |
| 400 if (dump_file) | |
| 401 fprintf (dump_file, "Not considering %s for cloning; body is overwrittable.\n", | |
| 402 cgraph_node_name (node)); | |
| 403 return false; | |
| 404 } | |
| 405 if (!tree_versionable_function_p (node->decl)) | |
| 406 { | |
| 407 if (dump_file) | |
| 408 fprintf (dump_file, "Not considering %s for cloning; body is not versionable.\n", | |
| 409 cgraph_node_name (node)); | |
| 410 return false; | |
| 411 } | |
| 412 for (e = node->callers; e; e = e->next_caller) | |
| 413 { | |
| 414 direct_call_sum += e->count; | |
| 415 n_calls ++; | |
| 416 if (cgraph_maybe_hot_edge_p (e)) | |
| 417 n_hot_calls ++; | |
| 418 } | |
| 419 | |
| 420 if (!n_calls) | |
| 421 { | |
| 422 if (dump_file) | |
| 423 fprintf (dump_file, "Not considering %s for cloning; no direct calls.\n", | |
| 424 cgraph_node_name (node)); | |
| 425 return false; | |
| 426 } | |
| 427 if (node->local.inline_summary.self_insns < n_calls) | |
| 428 { | |
| 429 if (dump_file) | |
| 430 fprintf (dump_file, "Considering %s for cloning; code would shrink.\n", | |
| 431 cgraph_node_name (node)); | |
| 432 return true; | |
| 433 } | |
| 434 | |
| 435 if (!flag_ipa_cp_clone) | |
| 436 { | |
| 437 if (dump_file) | |
| 438 fprintf (dump_file, "Not considering %s for cloning; -fipa-cp-clone disabled.\n", | |
| 439 cgraph_node_name (node)); | |
| 440 return false; | |
| 441 } | |
| 442 | |
| 443 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl))) | |
| 444 { | |
| 445 if (dump_file) | |
| 446 fprintf (dump_file, "Not considering %s for cloning; optimizing it for size.\n", | |
| 447 cgraph_node_name (node)); | |
| 448 return false; | |
| 449 } | |
| 450 | |
| 451 /* When profile is available and function is hot, propagate into it even if | |
| 452 calls seems cold; constant propagation can improve function's speed | |
| 453 significandly. */ | |
| 454 if (max_count) | |
| 455 { | |
| 456 if (direct_call_sum > node->count * 90 / 100) | |
| 457 { | |
| 458 if (dump_file) | |
| 459 fprintf (dump_file, "Considering %s for cloning; usually called directly.\n", | |
| 460 cgraph_node_name (node)); | |
| 461 return true; | |
| 462 } | |
| 463 } | |
| 464 if (!n_hot_calls) | |
| 465 { | |
| 466 if (dump_file) | |
| 467 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n", | |
| 468 cgraph_node_name (node)); | |
|
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
469 return false; |
| 0 | 470 } |
| 471 if (dump_file) | |
| 472 fprintf (dump_file, "Considering %s for cloning.\n", | |
| 473 cgraph_node_name (node)); | |
| 474 return true; | |
| 475 } | |
| 476 | |
| 477 /* Initialize ipcp_lattices array. The lattices corresponding to supported | |
| 478 types (integers, real types and Fortran constants defined as const_decls) | |
| 479 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */ | |
| 480 static void | |
| 481 ipcp_initialize_node_lattices (struct cgraph_node *node) | |
| 482 { | |
| 483 int i; | |
| 484 struct ipa_node_params *info = IPA_NODE_REF (node); | |
| 485 enum ipa_lattice_type type; | |
| 486 | |
| 487 if (ipa_is_called_with_var_arguments (info)) | |
| 488 type = IPA_BOTTOM; | |
| 489 else if (!node->needed) | |
| 490 type = IPA_TOP; | |
| 491 /* When cloning is allowed, we can assume that externally visible functions | |
| 492 are not called. We will compensate this by cloning later. */ | |
| 493 else if (ipcp_cloning_candidate_p (node)) | |
| 494 type = IPA_TOP, n_cloning_candidates ++; | |
| 495 else | |
| 496 type = IPA_BOTTOM; | |
| 497 | |
| 498 for (i = 0; i < ipa_get_param_count (info) ; i++) | |
| 499 ipcp_get_lattice (info, i)->type = type; | |
| 500 } | |
| 501 | |
| 502 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT. | |
| 503 Return the tree. */ | |
| 504 static tree | |
| 505 build_const_val (struct ipcp_lattice *lat, tree tree_type) | |
| 506 { | |
| 507 tree val; | |
| 508 | |
| 509 gcc_assert (ipcp_lat_is_const (lat)); | |
| 510 val = lat->constant; | |
| 511 | |
| 512 if (!useless_type_conversion_p (tree_type, TREE_TYPE (val))) | |
| 513 { | |
| 514 if (fold_convertible_p (tree_type, val)) | |
| 515 return fold_build1 (NOP_EXPR, tree_type, val); | |
| 516 else | |
| 517 return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val); | |
| 518 } | |
| 519 return val; | |
| 520 } | |
| 521 | |
| 522 /* Compute the proper scale for NODE. It is the ratio between the number of | |
| 523 direct calls (represented on the incoming cgraph_edges) and sum of all | |
| 524 invocations of NODE (represented as count in cgraph_node). */ | |
| 525 static void | |
| 526 ipcp_compute_node_scale (struct cgraph_node *node) | |
| 527 { | |
| 528 gcov_type sum; | |
| 529 struct cgraph_edge *cs; | |
| 530 | |
| 531 sum = 0; | |
| 532 /* Compute sum of all counts of callers. */ | |
| 533 for (cs = node->callers; cs != NULL; cs = cs->next_caller) | |
| 534 sum += cs->count; | |
| 535 if (node->count == 0) | |
| 536 ipcp_set_node_scale (node, 0); | |
| 537 else | |
| 538 ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count); | |
| 539 } | |
| 540 | |
| 541 /* Initialization and computation of IPCP data structures. This is the initial | |
| 542 intraprocedural analysis of functions, which gathers information to be | |
| 543 propagated later on. */ | |
| 544 static void | |
| 545 ipcp_init_stage (void) | |
| 546 { | |
| 547 struct cgraph_node *node; | |
| 548 struct cgraph_edge *cs; | |
| 549 | |
| 550 for (node = cgraph_nodes; node; node = node->next) | |
| 551 if (node->analyzed) | |
| 552 ipcp_analyze_node (node); | |
| 553 for (node = cgraph_nodes; node; node = node->next) | |
| 554 { | |
| 555 if (!node->analyzed) | |
| 556 continue; | |
| 557 /* building jump functions */ | |
| 558 for (cs = node->callees; cs; cs = cs->next_callee) | |
| 559 { | |
| 560 if (!cs->callee->analyzed) | |
| 561 continue; | |
| 562 ipa_count_arguments (cs); | |
| 563 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs)) | |
| 564 != ipa_get_param_count (IPA_NODE_REF (cs->callee))) | |
| 565 { | |
| 566 /* Handle cases of functions with | |
| 567 a variable number of parameters. */ | |
| 568 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee)); | |
| 569 if (flag_indirect_inlining) | |
| 570 ipa_compute_jump_functions (cs); | |
| 571 } | |
| 572 else | |
| 573 ipa_compute_jump_functions (cs); | |
| 574 } | |
| 575 } | |
| 576 } | |
| 577 | |
| 578 /* Return true if there are some formal parameters whose value is IPA_TOP (in | |
| 579 the whole compilation unit). Change their values to IPA_BOTTOM, since they | |
| 580 most probably get their values from outside of this compilation unit. */ | |
| 581 static bool | |
| 582 ipcp_change_tops_to_bottom (void) | |
| 583 { | |
| 584 int i, count; | |
| 585 struct cgraph_node *node; | |
| 586 bool prop_again; | |
| 587 | |
| 588 prop_again = false; | |
| 589 for (node = cgraph_nodes; node; node = node->next) | |
| 590 { | |
| 591 struct ipa_node_params *info = IPA_NODE_REF (node); | |
| 592 count = ipa_get_param_count (info); | |
| 593 for (i = 0; i < count; i++) | |
| 594 { | |
| 595 struct ipcp_lattice *lat = ipcp_get_lattice (info, i); | |
| 596 if (lat->type == IPA_TOP) | |
| 597 { | |
| 598 prop_again = true; | |
| 599 if (dump_file) | |
| 600 { | |
| 601 fprintf (dump_file, "Forcing param "); | |
| 602 print_generic_expr (dump_file, ipa_get_param (info, i), 0); | |
| 603 fprintf (dump_file, " of node %s to bottom.\n", | |
| 604 cgraph_node_name (node)); | |
| 605 } | |
| 606 lat->type = IPA_BOTTOM; | |
| 607 } | |
| 608 } | |
| 609 } | |
| 610 return prop_again; | |
| 611 } | |
| 612 | |
| 613 /* Interprocedural analysis. The algorithm propagates constants from the | |
| 614 caller's parameters to the callee's arguments. */ | |
| 615 static void | |
| 616 ipcp_propagate_stage (void) | |
| 617 { | |
| 618 int i; | |
| 619 struct ipcp_lattice inc_lat = { IPA_BOTTOM, NULL }; | |
| 620 struct ipcp_lattice new_lat = { IPA_BOTTOM, NULL }; | |
| 621 struct ipcp_lattice *dest_lat; | |
| 622 struct cgraph_edge *cs; | |
| 623 struct ipa_jump_func *jump_func; | |
| 624 struct ipa_func_list *wl; | |
| 625 int count; | |
| 626 | |
| 627 ipa_check_create_node_params (); | |
| 628 ipa_check_create_edge_args (); | |
| 629 | |
| 630 /* Initialize worklist to contain all functions. */ | |
| 631 wl = ipa_init_func_list (); | |
| 632 while (wl) | |
| 633 { | |
| 634 struct cgraph_node *node = ipa_pop_func_from_list (&wl); | |
| 635 struct ipa_node_params *info = IPA_NODE_REF (node); | |
| 636 | |
| 637 for (cs = node->callees; cs; cs = cs->next_callee) | |
| 638 { | |
| 639 struct ipa_node_params *callee_info = IPA_NODE_REF (cs->callee); | |
| 640 struct ipa_edge_args *args = IPA_EDGE_REF (cs); | |
| 641 | |
| 642 if (ipa_is_called_with_var_arguments (callee_info)) | |
| 643 continue; | |
| 644 | |
| 645 count = ipa_get_cs_argument_count (args); | |
| 646 for (i = 0; i < count; i++) | |
| 647 { | |
| 648 jump_func = ipa_get_ith_jump_func (args, i); | |
| 649 ipcp_lattice_from_jfunc (info, &inc_lat, jump_func); | |
| 650 dest_lat = ipcp_get_lattice (callee_info, i); | |
| 651 ipa_lattice_meet (&new_lat, &inc_lat, dest_lat); | |
| 652 if (ipcp_lattice_changed (&new_lat, dest_lat)) | |
| 653 { | |
| 654 dest_lat->type = new_lat.type; | |
| 655 dest_lat->constant = new_lat.constant; | |
| 656 ipa_push_func_to_list (&wl, cs->callee); | |
| 657 } | |
| 658 } | |
| 659 } | |
| 660 } | |
| 661 } | |
| 662 | |
| 663 /* Call the constant propagation algorithm and re-call it if necessary | |
| 664 (if there are undetermined values left). */ | |
| 665 static void | |
| 666 ipcp_iterate_stage (void) | |
| 667 { | |
| 668 struct cgraph_node *node; | |
| 669 n_cloning_candidates = 0; | |
| 670 | |
| 671 if (dump_file) | |
| 672 fprintf (dump_file, "\nIPA iterate stage:\n\n"); | |
| 673 for (node = cgraph_nodes; node; node = node->next) | |
| 674 { | |
| 675 ipcp_initialize_node_lattices (node); | |
| 676 ipcp_compute_node_scale (node); | |
| 677 } | |
| 678 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 679 { | |
| 680 ipcp_print_all_lattices (dump_file); | |
| 681 ipcp_function_scale_print (dump_file); | |
| 682 } | |
| 683 | |
| 684 ipcp_propagate_stage (); | |
| 685 if (ipcp_change_tops_to_bottom ()) | |
| 686 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM. | |
| 687 This change should be propagated. */ | |
| 688 { | |
| 689 gcc_assert (n_cloning_candidates); | |
| 690 ipcp_propagate_stage (); | |
| 691 } | |
| 692 if (dump_file) | |
| 693 { | |
| 694 fprintf (dump_file, "\nIPA lattices after propagation:\n"); | |
| 695 ipcp_print_all_lattices (dump_file); | |
| 696 if (dump_flags & TDF_DETAILS) | |
| 697 ipcp_print_profile_data (dump_file); | |
| 698 } | |
| 699 } | |
| 700 | |
| 701 /* Check conditions to forbid constant insertion to function described by | |
| 702 NODE. */ | |
| 703 static inline bool | |
| 704 ipcp_node_modifiable_p (struct cgraph_node *node) | |
| 705 { | |
| 706 /* Once we will be able to do in-place replacement, we can be more | |
| 707 lax here. */ | |
| 708 return tree_versionable_function_p (node->decl); | |
| 709 } | |
| 710 | |
| 711 /* Print count scale data structures. */ | |
| 712 static void | |
| 713 ipcp_function_scale_print (FILE * f) | |
| 714 { | |
| 715 struct cgraph_node *node; | |
| 716 | |
| 717 for (node = cgraph_nodes; node; node = node->next) | |
| 718 { | |
| 719 if (!node->analyzed) | |
| 720 continue; | |
| 721 fprintf (f, "printing scale for %s: ", cgraph_node_name (node)); | |
| 722 fprintf (f, "value is " HOST_WIDE_INT_PRINT_DEC | |
| 723 " \n", (HOST_WIDE_INT) ipcp_get_node_scale (node)); | |
| 724 } | |
| 725 } | |
| 726 | |
| 727 /* Print counts of all cgraph nodes. */ | |
| 728 static void | |
| 729 ipcp_print_func_profile_counts (FILE * f) | |
| 730 { | |
| 731 struct cgraph_node *node; | |
| 732 | |
| 733 for (node = cgraph_nodes; node; node = node->next) | |
| 734 { | |
| 735 fprintf (f, "function %s: ", cgraph_node_name (node)); | |
| 736 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC | |
| 737 " \n", (HOST_WIDE_INT) node->count); | |
| 738 } | |
| 739 } | |
| 740 | |
| 741 /* Print counts of all cgraph edges. */ | |
| 742 static void | |
| 743 ipcp_print_call_profile_counts (FILE * f) | |
| 744 { | |
| 745 struct cgraph_node *node; | |
| 746 struct cgraph_edge *cs; | |
| 747 | |
| 748 for (node = cgraph_nodes; node; node = node->next) | |
| 749 { | |
| 750 for (cs = node->callees; cs; cs = cs->next_callee) | |
| 751 { | |
| 752 fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller), | |
| 753 cgraph_node_name (cs->callee)); | |
| 754 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC " \n", | |
| 755 (HOST_WIDE_INT) cs->count); | |
| 756 } | |
| 757 } | |
| 758 } | |
| 759 | |
| 760 /* Print all counts and probabilities of cfg edges of all functions. */ | |
| 761 static void | |
| 762 ipcp_print_edge_profiles (FILE * f) | |
| 763 { | |
| 764 struct cgraph_node *node; | |
| 765 basic_block bb; | |
| 766 edge_iterator ei; | |
| 767 edge e; | |
| 768 | |
| 769 for (node = cgraph_nodes; node; node = node->next) | |
| 770 { | |
| 771 fprintf (f, "function %s: \n", cgraph_node_name (node)); | |
| 772 if (node->analyzed) | |
| 773 { | |
| 774 bb = | |
| 775 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl)); | |
| 776 fprintf (f, "ENTRY: "); | |
| 777 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC | |
| 778 " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency); | |
| 779 | |
| 780 if (bb->succs) | |
| 781 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 782 { | |
| 783 if (e->dest == | |
| 784 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION | |
| 785 (node->decl))) | |
| 786 fprintf (f, "edge ENTRY -> EXIT, Count"); | |
| 787 else | |
| 788 fprintf (f, "edge ENTRY -> %d, Count", e->dest->index); | |
| 789 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC | |
| 790 " Prob %d\n", (HOST_WIDE_INT) e->count, | |
| 791 e->probability); | |
| 792 } | |
| 793 FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl)) | |
| 794 { | |
| 795 fprintf (f, "bb[%d]: ", bb->index); | |
| 796 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC | |
| 797 " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency); | |
| 798 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 799 { | |
| 800 if (e->dest == | |
| 801 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION | |
| 802 (node->decl))) | |
| 803 fprintf (f, "edge %d -> EXIT, Count", e->src->index); | |
| 804 else | |
| 805 fprintf (f, "edge %d -> %d, Count", e->src->index, | |
| 806 e->dest->index); | |
| 807 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC " Prob %d\n", | |
| 808 (HOST_WIDE_INT) e->count, e->probability); | |
| 809 } | |
| 810 } | |
| 811 } | |
| 812 } | |
| 813 } | |
| 814 | |
| 815 /* Print counts and frequencies for all basic blocks of all functions. */ | |
| 816 static void | |
| 817 ipcp_print_bb_profiles (FILE * f) | |
| 818 { | |
| 819 basic_block bb; | |
| 820 struct cgraph_node *node; | |
| 821 | |
| 822 for (node = cgraph_nodes; node; node = node->next) | |
| 823 { | |
| 824 fprintf (f, "function %s: \n", cgraph_node_name (node)); | |
| 825 if (node->analyzed) | |
| 826 { | |
| 827 bb = | |
| 828 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl)); | |
| 829 fprintf (f, "ENTRY: Count"); | |
| 830 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC | |
| 831 " Frequency %d\n", (HOST_WIDE_INT) bb->count, | |
| 832 bb->frequency); | |
| 833 | |
| 834 FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl)) | |
| 835 { | |
| 836 fprintf (f, "bb[%d]: Count", bb->index); | |
| 837 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC | |
| 838 " Frequency %d\n", (HOST_WIDE_INT) bb->count, | |
| 839 bb->frequency); | |
| 840 } | |
| 841 bb = | |
| 842 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl)); | |
| 843 fprintf (f, "EXIT: Count"); | |
| 844 fprintf (f, " " HOST_WIDE_INT_PRINT_DEC | |
| 845 " Frequency %d\n", (HOST_WIDE_INT) bb->count, | |
| 846 bb->frequency); | |
| 847 | |
| 848 } | |
| 849 } | |
| 850 } | |
| 851 | |
| 852 /* Print profile info for all functions. */ | |
| 853 static void | |
| 854 ipcp_print_profile_data (FILE * f) | |
| 855 { | |
| 856 fprintf (f, "\nNODE COUNTS :\n"); | |
| 857 ipcp_print_func_profile_counts (f); | |
| 858 fprintf (f, "\nCS COUNTS stage:\n"); | |
| 859 ipcp_print_call_profile_counts (f); | |
| 860 fprintf (f, "\nBB COUNTS and FREQUENCIES :\n"); | |
| 861 ipcp_print_bb_profiles (f); | |
| 862 fprintf (f, "\nCFG EDGES COUNTS and PROBABILITIES :\n"); | |
| 863 ipcp_print_edge_profiles (f); | |
| 864 } | |
| 865 | |
| 866 /* Build and initialize ipa_replace_map struct according to LAT. This struct is | |
| 867 processed by versioning, which operates according to the flags set. | |
| 868 PARM_TREE is the formal parameter found to be constant. LAT represents the | |
| 869 constant. */ | |
| 870 static struct ipa_replace_map * | |
| 871 ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat) | |
| 872 { | |
| 873 struct ipa_replace_map *replace_map; | |
| 874 tree const_val; | |
| 875 | |
| 876 replace_map = XCNEW (struct ipa_replace_map); | |
| 877 const_val = build_const_val (lat, TREE_TYPE (parm_tree)); | |
| 878 if (dump_file) | |
| 879 { | |
| 880 fprintf (dump_file, " replacing param "); | |
| 881 print_generic_expr (dump_file, parm_tree, 0); | |
| 882 fprintf (dump_file, " with const "); | |
| 883 print_generic_expr (dump_file, const_val, 0); | |
| 884 fprintf (dump_file, "\n"); | |
| 885 } | |
| 886 replace_map->old_tree = parm_tree; | |
| 887 replace_map->new_tree = const_val; | |
| 888 replace_map->replace_p = true; | |
| 889 replace_map->ref_p = false; | |
| 890 | |
| 891 return replace_map; | |
| 892 } | |
| 893 | |
| 894 /* Return true if this callsite should be redirected to the original callee | |
| 895 (instead of the cloned one). */ | |
| 896 static bool | |
| 897 ipcp_need_redirect_p (struct cgraph_edge *cs) | |
| 898 { | |
| 899 struct ipa_node_params *orig_callee_info; | |
| 900 int i, count; | |
| 901 struct ipa_jump_func *jump_func; | |
| 902 struct cgraph_node *node = cs->callee, *orig; | |
| 903 | |
| 904 if (!n_cloning_candidates) | |
| 905 return false; | |
| 906 | |
| 907 if ((orig = ipcp_get_orig_node (node)) != NULL) | |
| 908 node = orig; | |
| 909 if (ipcp_get_orig_node (cs->caller)) | |
| 910 return false; | |
| 911 | |
| 912 orig_callee_info = IPA_NODE_REF (node); | |
| 913 count = ipa_get_param_count (orig_callee_info); | |
| 914 for (i = 0; i < count; i++) | |
| 915 { | |
| 916 struct ipcp_lattice *lat = ipcp_get_lattice (orig_callee_info, i); | |
| 917 if (ipcp_lat_is_const (lat)) | |
| 918 { | |
| 919 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i); | |
| 920 if (jump_func->type != IPA_CONST) | |
| 921 return true; | |
| 922 } | |
| 923 } | |
| 924 | |
| 925 return false; | |
| 926 } | |
| 927 | |
| 928 /* Fix the callsites and the call graph after function cloning was done. */ | |
| 929 static void | |
| 930 ipcp_update_callgraph (void) | |
| 931 { | |
| 932 struct cgraph_node *node; | |
| 933 | |
| 934 for (node = cgraph_nodes; node; node = node->next) | |
| 935 if (node->analyzed && ipcp_node_is_clone (node)) | |
| 936 { | |
| 937 bitmap args_to_skip = BITMAP_ALLOC (NULL); | |
| 938 struct cgraph_node *orig_node = ipcp_get_orig_node (node); | |
| 939 struct ipa_node_params *info = IPA_NODE_REF (orig_node); | |
| 940 int i, count = ipa_get_param_count (info); | |
| 941 struct cgraph_edge *cs, *next; | |
| 942 | |
| 943 for (i = 0; i < count; i++) | |
| 944 { | |
| 945 struct ipcp_lattice *lat = ipcp_get_lattice (info, i); | |
| 946 tree parm_tree = ipa_get_param (info, i); | |
| 947 | |
| 948 /* We can proactively remove obviously unused arguments. */ | |
| 949 if (is_gimple_reg (parm_tree) | |
| 950 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node->decl), | |
| 951 parm_tree)) | |
| 952 { | |
| 953 bitmap_set_bit (args_to_skip, i); | |
| 954 continue; | |
| 955 } | |
| 956 | |
| 957 if (lat->type == IPA_CONST_VALUE) | |
| 958 bitmap_set_bit (args_to_skip, i); | |
| 959 } | |
| 960 for (cs = node->callers; cs; cs = next) | |
| 961 { | |
| 962 next = cs->next_caller; | |
| 963 if (ipcp_node_is_clone (cs->caller) || !ipcp_need_redirect_p (cs)) | |
| 964 { | |
| 965 gimple new_stmt; | |
| 966 gimple_stmt_iterator gsi; | |
| 967 | |
| 968 current_function_decl = cs->caller->decl; | |
| 969 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl)); | |
| 970 | |
| 971 new_stmt = gimple_call_copy_skip_args (cs->call_stmt, | |
| 972 args_to_skip); | |
| 973 gsi = gsi_for_stmt (cs->call_stmt); | |
| 974 gsi_replace (&gsi, new_stmt, true); | |
| 975 cgraph_set_call_stmt (cs, new_stmt); | |
| 976 pop_cfun (); | |
| 977 current_function_decl = NULL; | |
| 978 } | |
| 979 else | |
| 980 { | |
| 981 cgraph_redirect_edge_callee (cs, orig_node); | |
| 982 gimple_call_set_fndecl (cs->call_stmt, orig_node->decl); | |
| 983 } | |
| 984 } | |
| 985 } | |
| 986 } | |
| 987 | |
| 988 /* Update all cfg basic blocks in NODE according to SCALE. */ | |
| 989 static void | |
| 990 ipcp_update_bb_counts (struct cgraph_node *node, gcov_type scale) | |
| 991 { | |
| 992 basic_block bb; | |
| 993 | |
| 994 FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl)) | |
| 995 bb->count = bb->count * scale / REG_BR_PROB_BASE; | |
| 996 } | |
| 997 | |
| 998 /* Update all cfg edges in NODE according to SCALE. */ | |
| 999 static void | |
| 1000 ipcp_update_edges_counts (struct cgraph_node *node, gcov_type scale) | |
| 1001 { | |
| 1002 basic_block bb; | |
| 1003 edge_iterator ei; | |
| 1004 edge e; | |
| 1005 | |
| 1006 FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl)) | |
| 1007 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 1008 e->count = e->count * scale / REG_BR_PROB_BASE; | |
| 1009 } | |
| 1010 | |
| 1011 /* Update profiling info for versioned functions and the functions they were | |
| 1012 versioned from. */ | |
| 1013 static void | |
| 1014 ipcp_update_profiling (void) | |
| 1015 { | |
| 1016 struct cgraph_node *node, *orig_node; | |
| 1017 gcov_type scale, scale_complement; | |
| 1018 struct cgraph_edge *cs; | |
| 1019 | |
| 1020 for (node = cgraph_nodes; node; node = node->next) | |
| 1021 { | |
| 1022 if (ipcp_node_is_clone (node)) | |
| 1023 { | |
| 1024 orig_node = ipcp_get_orig_node (node); | |
| 1025 scale = ipcp_get_node_scale (orig_node); | |
| 1026 node->count = orig_node->count * scale / REG_BR_PROB_BASE; | |
| 1027 scale_complement = REG_BR_PROB_BASE - scale; | |
| 1028 orig_node->count = | |
| 1029 orig_node->count * scale_complement / REG_BR_PROB_BASE; | |
| 1030 for (cs = node->callees; cs; cs = cs->next_callee) | |
| 1031 cs->count = cs->count * scale / REG_BR_PROB_BASE; | |
| 1032 for (cs = orig_node->callees; cs; cs = cs->next_callee) | |
| 1033 cs->count = cs->count * scale_complement / REG_BR_PROB_BASE; | |
| 1034 ipcp_update_bb_counts (node, scale); | |
| 1035 ipcp_update_bb_counts (orig_node, scale_complement); | |
| 1036 ipcp_update_edges_counts (node, scale); | |
| 1037 ipcp_update_edges_counts (orig_node, scale_complement); | |
| 1038 } | |
| 1039 } | |
| 1040 } | |
| 1041 | |
| 1042 /* If NODE was cloned, how much would program grow? */ | |
| 1043 static long | |
| 1044 ipcp_estimate_growth (struct cgraph_node *node) | |
| 1045 { | |
| 1046 struct cgraph_edge *cs; | |
| 1047 int redirectable_node_callers = 0; | |
| 1048 int removable_args = 0; | |
| 1049 bool need_original = node->needed; | |
| 1050 struct ipa_node_params *info; | |
| 1051 int i, count; | |
| 1052 int growth; | |
| 1053 | |
| 1054 for (cs = node->callers; cs != NULL; cs = cs->next_caller) | |
| 1055 if (cs->caller == node || !ipcp_need_redirect_p (cs)) | |
| 1056 redirectable_node_callers++; | |
| 1057 else | |
| 1058 need_original = true; | |
| 1059 | |
| 1060 /* If we will be able to fully replace orignal node, we never increase | |
| 1061 program size. */ | |
| 1062 if (!need_original) | |
| 1063 return 0; | |
| 1064 | |
| 1065 info = IPA_NODE_REF (node); | |
| 1066 count = ipa_get_param_count (info); | |
| 1067 for (i = 0; i < count; i++) | |
| 1068 { | |
| 1069 struct ipcp_lattice *lat = ipcp_get_lattice (info, i); | |
| 1070 tree parm_tree = ipa_get_param (info, i); | |
| 1071 | |
| 1072 /* We can proactively remove obviously unused arguments. */ | |
| 1073 if (is_gimple_reg (parm_tree) | |
| 1074 && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl), | |
| 1075 parm_tree)) | |
| 1076 removable_args++; | |
| 1077 | |
| 1078 if (lat->type == IPA_CONST_VALUE) | |
| 1079 removable_args++; | |
| 1080 } | |
| 1081 | |
| 1082 /* We make just very simple estimate of savings for removal of operand from | |
| 1083 call site. Precise cost is dificult to get, as our size metric counts | |
| 1084 constants and moves as free. Generally we are looking for cases that | |
| 1085 small function is called very many times. */ | |
| 1086 growth = node->local.inline_summary.self_insns | |
| 1087 - removable_args * redirectable_node_callers; | |
| 1088 if (growth < 0) | |
| 1089 return 0; | |
| 1090 return growth; | |
| 1091 } | |
| 1092 | |
| 1093 | |
| 1094 /* Estimate cost of cloning NODE. */ | |
| 1095 static long | |
| 1096 ipcp_estimate_cloning_cost (struct cgraph_node *node) | |
| 1097 { | |
| 1098 int freq_sum = 1; | |
| 1099 gcov_type count_sum = 1; | |
| 1100 struct cgraph_edge *e; | |
| 1101 int cost; | |
| 1102 | |
| 1103 cost = ipcp_estimate_growth (node) * 1000; | |
| 1104 if (!cost) | |
| 1105 { | |
| 1106 if (dump_file) | |
| 1107 fprintf (dump_file, "Versioning of %s will save code size\n", | |
| 1108 cgraph_node_name (node)); | |
| 1109 return 0; | |
| 1110 } | |
| 1111 | |
| 1112 for (e = node->callers; e; e = e->next_caller) | |
| 1113 if (!bitmap_bit_p (dead_nodes, e->caller->uid) | |
| 1114 && !ipcp_need_redirect_p (e)) | |
| 1115 { | |
| 1116 count_sum += e->count; | |
| 1117 freq_sum += e->frequency + 1; | |
| 1118 } | |
| 1119 | |
| 1120 if (max_count) | |
| 1121 cost /= count_sum * 1000 / max_count + 1; | |
| 1122 else | |
| 1123 cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1; | |
| 1124 if (dump_file) | |
| 1125 fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n", | |
| 1126 cgraph_node_name (node), cost, node->local.inline_summary.self_insns, | |
| 1127 freq_sum); | |
| 1128 return cost + 1; | |
| 1129 } | |
| 1130 | |
| 1131 /* Return number of live constant parameters. */ | |
| 1132 static int | |
| 1133 ipcp_const_param_count (struct cgraph_node *node) | |
| 1134 { | |
| 1135 int const_param = 0; | |
| 1136 struct ipa_node_params *info = IPA_NODE_REF (node); | |
| 1137 int count = ipa_get_param_count (info); | |
| 1138 int i; | |
| 1139 | |
| 1140 for (i = 0; i < count; i++) | |
| 1141 { | |
| 1142 struct ipcp_lattice *lat = ipcp_get_lattice (info, i); | |
| 1143 tree parm_tree = ipa_get_param (info, i); | |
| 1144 if (ipcp_lat_is_insertable (lat) | |
| 1145 /* Do not count obviously unused arguments. */ | |
| 1146 && (!is_gimple_reg (parm_tree) | |
| 1147 || gimple_default_def (DECL_STRUCT_FUNCTION (node->decl), | |
| 1148 parm_tree))) | |
| 1149 const_param++; | |
| 1150 } | |
| 1151 return const_param; | |
| 1152 } | |
| 1153 | |
| 1154 /* Propagate the constant parameters found by ipcp_iterate_stage() | |
| 1155 to the function's code. */ | |
| 1156 static void | |
| 1157 ipcp_insert_stage (void) | |
| 1158 { | |
| 1159 struct cgraph_node *node, *node1 = NULL; | |
| 1160 int i; | |
| 1161 VEC (cgraph_edge_p, heap) * redirect_callers; | |
| 1162 varray_type replace_trees; | |
| 1163 int node_callers, count; | |
| 1164 tree parm_tree; | |
| 1165 struct ipa_replace_map *replace_param; | |
| 1166 fibheap_t heap; | |
| 1167 long overall_insns = 0, new_insns = 0; | |
| 1168 long max_new_insns; | |
| 1169 | |
| 1170 ipa_check_create_node_params (); | |
| 1171 ipa_check_create_edge_args (); | |
| 1172 if (dump_file) | |
| 1173 fprintf (dump_file, "\nIPA insert stage:\n\n"); | |
| 1174 | |
| 1175 dead_nodes = BITMAP_ALLOC (NULL); | |
| 1176 | |
| 1177 for (node = cgraph_nodes; node; node = node->next) | |
| 1178 if (node->analyzed) | |
| 1179 { | |
| 1180 if (node->count > max_count) | |
| 1181 max_count = node->count; | |
| 1182 overall_insns += node->local.inline_summary.self_insns; | |
| 1183 } | |
| 1184 | |
| 1185 max_new_insns = overall_insns; | |
| 1186 if (max_new_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS)) | |
| 1187 max_new_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS); | |
| 1188 max_new_insns = max_new_insns * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1; | |
| 1189 | |
| 1190 /* First collect all functions we proved to have constant arguments to heap. */ | |
| 1191 heap = fibheap_new (); | |
| 1192 for (node = cgraph_nodes; node; node = node->next) | |
| 1193 { | |
| 1194 struct ipa_node_params *info; | |
| 1195 /* Propagation of the constant is forbidden in certain conditions. */ | |
| 1196 if (!node->analyzed || !ipcp_node_modifiable_p (node)) | |
| 1197 continue; | |
| 1198 info = IPA_NODE_REF (node); | |
| 1199 if (ipa_is_called_with_var_arguments (info)) | |
| 1200 continue; | |
| 1201 if (ipcp_const_param_count (node)) | |
| 1202 node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node), node); | |
| 1203 } | |
| 1204 | |
| 1205 /* Now clone in priority order until code size growth limits are met or | |
| 1206 heap is emptied. */ | |
| 1207 while (!fibheap_empty (heap)) | |
| 1208 { | |
| 1209 struct ipa_node_params *info; | |
| 1210 int growth = 0; | |
| 1211 bitmap args_to_skip; | |
| 1212 struct cgraph_edge *cs; | |
| 1213 | |
| 1214 node = (struct cgraph_node *)fibheap_extract_min (heap); | |
| 1215 node->aux = NULL; | |
| 1216 if (dump_file) | |
| 1217 fprintf (dump_file, "considering function %s\n", | |
| 1218 cgraph_node_name (node)); | |
| 1219 | |
| 1220 growth = ipcp_estimate_growth (node); | |
| 1221 | |
| 1222 if (new_insns + growth > max_new_insns) | |
| 1223 break; | |
| 1224 if (growth | |
| 1225 && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl))) | |
| 1226 { | |
| 1227 if (dump_file) | |
| 1228 fprintf (dump_file, "Not versioning, cold code would grow"); | |
| 1229 continue; | |
| 1230 } | |
| 1231 | |
| 1232 new_insns += growth; | |
| 1233 | |
| 1234 /* Look if original function becomes dead after clonning. */ | |
| 1235 for (cs = node->callers; cs != NULL; cs = cs->next_caller) | |
| 1236 if (cs->caller == node || ipcp_need_redirect_p (cs)) | |
| 1237 break; | |
| 1238 if (!cs && !node->needed) | |
| 1239 bitmap_set_bit (dead_nodes, node->uid); | |
| 1240 | |
| 1241 info = IPA_NODE_REF (node); | |
| 1242 count = ipa_get_param_count (info); | |
| 1243 | |
| 1244 VARRAY_GENERIC_PTR_INIT (replace_trees, ipcp_const_param_count (node), | |
| 1245 "replace_trees"); | |
| 1246 args_to_skip = BITMAP_ALLOC (NULL); | |
| 1247 for (i = 0; i < count; i++) | |
| 1248 { | |
| 1249 struct ipcp_lattice *lat = ipcp_get_lattice (info, i); | |
| 1250 parm_tree = ipa_get_param (info, i); | |
| 1251 | |
| 1252 /* We can proactively remove obviously unused arguments. */ | |
| 1253 if (is_gimple_reg (parm_tree) | |
| 1254 && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl), | |
| 1255 parm_tree)) | |
| 1256 { | |
| 1257 bitmap_set_bit (args_to_skip, i); | |
| 1258 continue; | |
| 1259 } | |
| 1260 | |
| 1261 if (lat->type == IPA_CONST_VALUE) | |
| 1262 { | |
| 1263 replace_param = | |
| 1264 ipcp_create_replace_map (parm_tree, lat); | |
| 1265 VARRAY_PUSH_GENERIC_PTR (replace_trees, replace_param); | |
| 1266 bitmap_set_bit (args_to_skip, i); | |
| 1267 } | |
| 1268 } | |
| 1269 | |
| 1270 /* Compute how many callers node has. */ | |
| 1271 node_callers = 0; | |
| 1272 for (cs = node->callers; cs != NULL; cs = cs->next_caller) | |
| 1273 node_callers++; | |
| 1274 redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers); | |
| 1275 for (cs = node->callers; cs != NULL; cs = cs->next_caller) | |
| 1276 VEC_quick_push (cgraph_edge_p, redirect_callers, cs); | |
| 1277 | |
| 1278 /* Redirecting all the callers of the node to the | |
| 1279 new versioned node. */ | |
| 1280 node1 = | |
| 1281 cgraph_function_versioning (node, redirect_callers, replace_trees, | |
| 1282 args_to_skip); | |
| 1283 BITMAP_FREE (args_to_skip); | |
| 1284 VEC_free (cgraph_edge_p, heap, redirect_callers); | |
| 1285 VARRAY_CLEAR (replace_trees); | |
| 1286 if (node1 == NULL) | |
| 1287 continue; | |
| 1288 if (dump_file) | |
| 1289 fprintf (dump_file, "versioned function %s with growth %i, overall %i\n", | |
| 1290 cgraph_node_name (node), (int)growth, (int)new_insns); | |
| 1291 ipcp_init_cloned_node (node, node1); | |
| 1292 | |
| 1293 /* We've possibly introduced direct calls. */ | |
| 1294 ipcp_update_cloned_node (node1); | |
| 1295 | |
| 1296 if (dump_file) | |
| 1297 dump_function_to_file (node1->decl, dump_file, dump_flags); | |
| 1298 | |
| 1299 for (cs = node->callees; cs; cs = cs->next_callee) | |
| 1300 if (cs->callee->aux) | |
| 1301 { | |
| 1302 fibheap_delete_node (heap, (fibnode_t) cs->callee->aux); | |
| 1303 cs->callee->aux = fibheap_insert (heap, | |
| 1304 ipcp_estimate_cloning_cost (cs->callee), | |
| 1305 cs->callee); | |
| 1306 } | |
| 1307 } | |
| 1308 | |
| 1309 while (!fibheap_empty (heap)) | |
| 1310 { | |
| 1311 if (dump_file) | |
| 1312 fprintf (dump_file, "skipping function %s\n", | |
| 1313 cgraph_node_name (node)); | |
| 1314 node = (struct cgraph_node *) fibheap_extract_min (heap); | |
| 1315 node->aux = NULL; | |
| 1316 } | |
| 1317 fibheap_delete (heap); | |
| 1318 BITMAP_FREE (dead_nodes); | |
| 1319 ipcp_update_callgraph (); | |
| 1320 ipcp_update_profiling (); | |
| 1321 } | |
| 1322 | |
| 1323 /* The IPCP driver. */ | |
| 1324 static unsigned int | |
| 1325 ipcp_driver (void) | |
| 1326 { | |
| 1327 cgraph_remove_unreachable_nodes (true,dump_file); | |
| 1328 if (dump_file) | |
| 1329 { | |
| 1330 fprintf (dump_file, "\nIPA structures before propagation:\n"); | |
| 1331 if (dump_flags & TDF_DETAILS) | |
| 1332 ipa_print_all_params (dump_file); | |
| 1333 ipa_print_all_jump_functions (dump_file); | |
| 1334 } | |
| 1335 /* 2. Do the interprocedural propagation. */ | |
| 1336 ipcp_iterate_stage (); | |
| 1337 /* 3. Insert the constants found to the functions. */ | |
| 1338 ipcp_insert_stage (); | |
| 1339 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1340 { | |
| 1341 fprintf (dump_file, "\nProfiling info after insert stage:\n"); | |
| 1342 ipcp_print_profile_data (dump_file); | |
| 1343 } | |
| 1344 /* Free all IPCP structures. */ | |
| 1345 free_all_ipa_structures_after_ipa_cp (); | |
| 1346 if (dump_file) | |
| 1347 fprintf (dump_file, "\nIPA constant propagation end\n"); | |
| 1348 return 0; | |
| 1349 } | |
| 1350 | |
| 1351 /* Note function body size. */ | |
| 1352 static void | |
| 1353 ipcp_generate_summary (void) | |
| 1354 { | |
| 1355 if (dump_file) | |
| 1356 fprintf (dump_file, "\nIPA constant propagation start:\n"); | |
| 1357 ipa_check_create_node_params (); | |
| 1358 ipa_check_create_edge_args (); | |
| 1359 ipa_register_cgraph_hooks (); | |
| 1360 /* 1. Call the init stage to initialize | |
| 1361 the ipa_node_params and ipa_edge_args structures. */ | |
| 1362 ipcp_init_stage (); | |
| 1363 } | |
| 1364 | |
| 1365 /* Gate for IPCP optimization. */ | |
| 1366 static bool | |
| 1367 cgraph_gate_cp (void) | |
| 1368 { | |
| 1369 return flag_ipa_cp; | |
| 1370 } | |
| 1371 | |
| 1372 struct ipa_opt_pass pass_ipa_cp = | |
| 1373 { | |
| 1374 { | |
| 1375 IPA_PASS, | |
| 1376 "cp", /* name */ | |
| 1377 cgraph_gate_cp, /* gate */ | |
| 1378 ipcp_driver, /* execute */ | |
| 1379 NULL, /* sub */ | |
| 1380 NULL, /* next */ | |
| 1381 0, /* static_pass_number */ | |
| 1382 TV_IPA_CONSTANT_PROP, /* tv_id */ | |
| 1383 0, /* properties_required */ | |
| 1384 PROP_trees, /* properties_provided */ | |
| 1385 0, /* properties_destroyed */ | |
| 1386 0, /* todo_flags_start */ | |
| 1387 TODO_dump_cgraph | TODO_dump_func | | |
| 1388 TODO_remove_functions /* todo_flags_finish */ | |
| 1389 }, | |
| 1390 ipcp_generate_summary, /* generate_summary */ | |
| 1391 NULL, /* write_summary */ | |
| 1392 NULL, /* read_summary */ | |
| 1393 NULL, /* function_read_summary */ | |
| 1394 0, /* TODOs */ | |
| 1395 NULL, /* function_transform */ | |
| 1396 NULL, /* variable_transform */ | |
| 1397 }; |