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