]>
Commit | Line | Data |
---|---|---|
ea900239 | 1 | /* Callgraph based analysis of static variables. |
fa10beec | 2 | Copyright (C) 2004, 2005, 2007, 2008 Free Software Foundation, Inc. |
ea900239 DB |
3 | Contributed by Kenneth Zadeck <zadeck@naturalbridge.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 | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
ea900239 DB |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
ea900239 | 20 | |
fa10beec RW |
21 | /* This file marks functions as being either const (TREE_READONLY) or |
22 | pure (DECL_PURE_P). It can also set a variant of these that | |
23 | are allowed to loop indefinitely (DECL_LOOPING_CONST_PURE_P). | |
ea900239 DB |
24 | |
25 | This must be run after inlining decisions have been made since | |
26 | otherwise, the local sets will not contain information that is | |
27 | consistent with post inlined state. The global sets are not prone | |
28 | to this problem since they are by definition transitive. */ | |
29 | ||
30 | /* The code in this module is called by the ipa pass manager. It | |
31 | should be one of the later passes since it's information is used by | |
32 | the rest of the compilation. */ | |
33 | ||
34 | #include "config.h" | |
35 | #include "system.h" | |
36 | #include "coretypes.h" | |
37 | #include "tm.h" | |
38 | #include "tree.h" | |
39 | #include "tree-flow.h" | |
40 | #include "tree-inline.h" | |
41 | #include "tree-pass.h" | |
42 | #include "langhooks.h" | |
43 | #include "pointer-set.h" | |
44 | #include "ggc.h" | |
45 | #include "ipa-utils.h" | |
46 | #include "c-common.h" | |
726a989a | 47 | #include "gimple.h" |
ea900239 DB |
48 | #include "cgraph.h" |
49 | #include "output.h" | |
50 | #include "flags.h" | |
51 | #include "timevar.h" | |
52 | #include "diagnostic.h" | |
53 | #include "langhooks.h" | |
5d35c171 | 54 | #include "target.h" |
ea900239 DB |
55 | |
56 | static struct pointer_set_t *visited_nodes; | |
57 | ||
58 | /* Lattice values for const and pure functions. Everything starts out | |
59 | being const, then may drop to pure and then neither depending on | |
60 | what is found. */ | |
61 | enum pure_const_state_e | |
62 | { | |
63 | IPA_CONST, | |
64 | IPA_PURE, | |
65 | IPA_NEITHER | |
66 | }; | |
67 | ||
812dbce5 JH |
68 | /* Holder for the const_state. There is one of these per function |
69 | decl. */ | |
ea900239 DB |
70 | struct funct_state_d |
71 | { | |
812dbce5 | 72 | /* See above. */ |
ea900239 | 73 | enum pure_const_state_e pure_const_state; |
812dbce5 JH |
74 | |
75 | /* True if the function could possibly infinite loop. There are a | |
76 | lot of ways that this could be determined. We are pretty | |
77 | conservative here. While it is possible to cse pure and const | |
78 | calls, it is not legal to have dce get rid of the call if there | |
79 | is a possibility that the call could infinite loop since this is | |
80 | a behavioral change. */ | |
becfd6e5 | 81 | bool looping; |
812dbce5 JH |
82 | |
83 | /* If the state of the function was set in the source, then assume | |
84 | that it was done properly even if the analysis we do would be | |
85 | more pessimestic. */ | |
86 | bool state_set_in_source; | |
ea900239 DB |
87 | }; |
88 | ||
89 | typedef struct funct_state_d * funct_state; | |
90 | ||
812dbce5 JH |
91 | /* The storage of the funct_state is abstracted because there is the |
92 | possibility that it may be desirable to move this to the cgraph | |
93 | local info. */ | |
94 | ||
95 | /* Array, indexed by cgraph node uid, of function states. */ | |
96 | ||
e2c9111c JH |
97 | DEF_VEC_P (funct_state); |
98 | DEF_VEC_ALLOC_P (funct_state, heap); | |
99 | static VEC (funct_state, heap) *funct_state_vec; | |
812dbce5 | 100 | |
129a37fc JH |
101 | /* Holders of ipa cgraph hooks: */ |
102 | static struct cgraph_node_hook_list *function_insertion_hook_holder; | |
e2c9111c JH |
103 | static struct cgraph_2node_hook_list *node_duplication_hook_holder; |
104 | static struct cgraph_node_hook_list *node_removal_hook_holder; | |
812dbce5 JH |
105 | |
106 | /* Init the function state. */ | |
107 | ||
108 | static void | |
109 | finish_state (void) | |
110 | { | |
111 | free (funct_state_vec); | |
112 | } | |
113 | ||
114 | ||
ea900239 DB |
115 | /* Return the function state from NODE. */ |
116 | ||
117 | static inline funct_state | |
118 | get_function_state (struct cgraph_node *node) | |
119 | { | |
e2c9111c JH |
120 | if (!funct_state_vec |
121 | || VEC_length (funct_state, funct_state_vec) <= (unsigned int)node->uid) | |
122 | return NULL; | |
123 | return VEC_index (funct_state, funct_state_vec, node->uid); | |
812dbce5 JH |
124 | } |
125 | ||
126 | /* Set the function state S for NODE. */ | |
127 | ||
128 | static inline void | |
129 | set_function_state (struct cgraph_node *node, funct_state s) | |
130 | { | |
e2c9111c JH |
131 | if (!funct_state_vec |
132 | || VEC_length (funct_state, funct_state_vec) <= (unsigned int)node->uid) | |
133 | VEC_safe_grow_cleared (funct_state, heap, funct_state_vec, node->uid + 1); | |
134 | VEC_replace (funct_state, funct_state_vec, node->uid, s); | |
ea900239 DB |
135 | } |
136 | ||
fa10beec | 137 | /* Check to see if the use (or definition when CHECKING_WRITE is true) |
ea900239 DB |
138 | variable T is legal in a function that is either pure or const. */ |
139 | ||
140 | static inline void | |
141 | check_decl (funct_state local, | |
142 | tree t, bool checking_write) | |
143 | { | |
144 | /* If the variable has the "used" attribute, treat it as if it had a | |
145 | been touched by the devil. */ | |
146 | if (lookup_attribute ("used", DECL_ATTRIBUTES (t))) | |
147 | { | |
148 | local->pure_const_state = IPA_NEITHER; | |
becfd6e5 | 149 | local->looping = false; |
ea900239 DB |
150 | return; |
151 | } | |
152 | ||
153 | /* Do not want to do anything with volatile except mark any | |
154 | function that uses one to be not const or pure. */ | |
155 | if (TREE_THIS_VOLATILE (t)) | |
156 | { | |
157 | local->pure_const_state = IPA_NEITHER; | |
becfd6e5 | 158 | local->looping = false; |
ea900239 DB |
159 | return; |
160 | } | |
161 | ||
162 | /* Do not care about a local automatic that is not static. */ | |
163 | if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) | |
164 | return; | |
165 | ||
166 | /* Since we have dealt with the locals and params cases above, if we | |
167 | are CHECKING_WRITE, this cannot be a pure or constant | |
168 | function. */ | |
169 | if (checking_write) | |
eb80272a ST |
170 | { |
171 | local->pure_const_state = IPA_NEITHER; | |
becfd6e5 | 172 | local->looping = false; |
eb80272a ST |
173 | return; |
174 | } | |
ea900239 DB |
175 | |
176 | if (DECL_EXTERNAL (t) || TREE_PUBLIC (t)) | |
177 | { | |
178 | /* If the front end set the variable to be READONLY and | |
179 | constant, we can allow this variable in pure or const | |
180 | functions but the scope is too large for our analysis to set | |
181 | these bits ourselves. */ | |
182 | ||
183 | if (TREE_READONLY (t) | |
184 | && DECL_INITIAL (t) | |
185 | && is_gimple_min_invariant (DECL_INITIAL (t))) | |
186 | ; /* Read of a constant, do not change the function state. */ | |
187 | else | |
188 | { | |
189 | /* Just a regular read. */ | |
190 | if (local->pure_const_state == IPA_CONST) | |
191 | local->pure_const_state = IPA_PURE; | |
192 | } | |
193 | } | |
194 | ||
195 | /* Compilation level statics can be read if they are readonly | |
196 | variables. */ | |
197 | if (TREE_READONLY (t)) | |
198 | return; | |
199 | ||
200 | /* Just a regular read. */ | |
201 | if (local->pure_const_state == IPA_CONST) | |
202 | local->pure_const_state = IPA_PURE; | |
203 | } | |
204 | ||
205 | /* If T is a VAR_DECL check to see if it is an allowed reference. */ | |
206 | ||
207 | static void | |
208 | check_operand (funct_state local, | |
209 | tree t, bool checking_write) | |
210 | { | |
211 | if (!t) return; | |
212 | ||
213 | if (TREE_CODE (t) == VAR_DECL) | |
214 | check_decl (local, t, checking_write); | |
215 | } | |
216 | ||
217 | /* Examine tree T for references. */ | |
218 | ||
219 | static void | |
220 | check_tree (funct_state local, tree t, bool checking_write) | |
221 | { | |
54e7d067 JH |
222 | if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR) |
223 | || TREE_CODE (t) == SSA_NAME) | |
ea900239 DB |
224 | return; |
225 | ||
fa10beec | 226 | /* Any tree which is volatile disqualifies this function from being |
13335ae6 AP |
227 | const or pure. */ |
228 | if (TREE_THIS_VOLATILE (t)) | |
229 | { | |
230 | local->pure_const_state = IPA_NEITHER; | |
becfd6e5 | 231 | local->looping = false; |
13335ae6 AP |
232 | return; |
233 | } | |
234 | ||
ea900239 DB |
235 | while (TREE_CODE (t) == REALPART_EXPR |
236 | || TREE_CODE (t) == IMAGPART_EXPR | |
237 | || handled_component_p (t)) | |
238 | { | |
239 | if (TREE_CODE (t) == ARRAY_REF) | |
240 | check_operand (local, TREE_OPERAND (t, 1), false); | |
241 | t = TREE_OPERAND (t, 0); | |
242 | } | |
243 | ||
244 | /* The bottom of an indirect reference can only be read, not | |
245 | written. */ | |
246 | if (INDIRECT_REF_P (t)) | |
247 | { | |
248 | check_tree (local, TREE_OPERAND (t, 0), false); | |
249 | ||
250 | /* Any indirect reference that occurs on the lhs | |
251 | disqualifies the function from being pure or const. Any | |
13335ae6 | 252 | indirect reference that occurs on the rhs disqualifies the |
1b0d2d17 | 253 | function from being const. */ |
13335ae6 AP |
254 | if (checking_write) |
255 | { | |
256 | local->pure_const_state = IPA_NEITHER; | |
becfd6e5 | 257 | local->looping = false; |
13335ae6 AP |
258 | return; |
259 | } | |
1b0d2d17 JC |
260 | else if (local->pure_const_state == IPA_CONST) |
261 | local->pure_const_state = IPA_PURE; | |
ea900239 DB |
262 | } |
263 | ||
264 | if (SSA_VAR_P (t)) | |
265 | check_operand (local, t, checking_write); | |
266 | } | |
267 | ||
268 | /* Scan tree T to see if there are any addresses taken in within T. */ | |
269 | ||
270 | static void | |
271 | look_for_address_of (funct_state local, tree t) | |
272 | { | |
273 | if (TREE_CODE (t) == ADDR_EXPR) | |
274 | { | |
275 | tree x = get_base_var (t); | |
276 | if (TREE_CODE (x) == VAR_DECL) | |
277 | { | |
278 | check_decl (local, x, false); | |
279 | ||
280 | /* Taking the address of something appears to be reasonable | |
281 | in PURE code. Not allowed in const. */ | |
282 | if (local->pure_const_state == IPA_CONST) | |
283 | local->pure_const_state = IPA_PURE; | |
284 | } | |
285 | } | |
286 | } | |
287 | ||
288 | /* Check to see if T is a read or address of operation on a var we are | |
289 | interested in analyzing. LOCAL is passed in to get access to its | |
290 | bit vectors. */ | |
291 | ||
292 | static void | |
293 | check_rhs_var (funct_state local, tree t) | |
294 | { | |
295 | look_for_address_of (local, t); | |
296 | ||
297 | /* Memcmp and strlen can both trap and they are declared pure. */ | |
298 | if (tree_could_trap_p (t) | |
299 | && local->pure_const_state == IPA_CONST) | |
300 | local->pure_const_state = IPA_PURE; | |
301 | ||
302 | check_tree(local, t, false); | |
303 | } | |
304 | ||
305 | /* Check to see if T is an assignment to a var we are interested in | |
306 | analyzing. LOCAL is passed in to get access to its bit vectors. */ | |
307 | ||
308 | static void | |
309 | check_lhs_var (funct_state local, tree t) | |
310 | { | |
311 | /* Memcmp and strlen can both trap and they are declared pure. | |
312 | Which seems to imply that we can apply the same rule here. */ | |
313 | if (tree_could_trap_p (t) | |
314 | && local->pure_const_state == IPA_CONST) | |
315 | local->pure_const_state = IPA_PURE; | |
316 | ||
317 | check_tree(local, t, true); | |
318 | } | |
319 | ||
320 | /* This is a scaled down version of get_asm_expr_operands from | |
321 | tree_ssa_operands.c. The version there runs much later and assumes | |
322 | that aliasing information is already available. Here we are just | |
323 | trying to find if the set of inputs and outputs contain references | |
324 | or address of operations to local static variables. STMT is the | |
325 | actual asm statement. */ | |
326 | ||
327 | static void | |
726a989a | 328 | get_asm_expr_operands (funct_state local, gimple stmt) |
ea900239 | 329 | { |
726a989a | 330 | size_t noutputs = gimple_asm_noutputs (stmt); |
ea900239 DB |
331 | const char **oconstraints |
332 | = (const char **) alloca ((noutputs) * sizeof (const char *)); | |
726a989a RB |
333 | size_t i; |
334 | tree op; | |
ea900239 DB |
335 | const char *constraint; |
336 | bool allows_mem, allows_reg, is_inout; | |
337 | ||
726a989a | 338 | for (i = 0; i < noutputs; i++) |
ea900239 | 339 | { |
726a989a | 340 | op = gimple_asm_output_op (stmt, i); |
ea900239 | 341 | oconstraints[i] = constraint |
726a989a | 342 | = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op))); |
ea900239 DB |
343 | parse_output_constraint (&constraint, i, 0, 0, |
344 | &allows_mem, &allows_reg, &is_inout); | |
345 | ||
726a989a | 346 | check_lhs_var (local, TREE_VALUE (op)); |
ea900239 DB |
347 | } |
348 | ||
726a989a | 349 | for (i = 0; i < gimple_asm_ninputs (stmt); i++) |
ea900239 | 350 | { |
726a989a | 351 | op = gimple_asm_input_op (stmt, i); |
ea900239 | 352 | constraint |
726a989a | 353 | = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op))); |
ea900239 DB |
354 | parse_input_constraint (&constraint, 0, 0, noutputs, 0, |
355 | oconstraints, &allows_mem, &allows_reg); | |
356 | ||
726a989a | 357 | check_rhs_var (local, TREE_VALUE (op)); |
ea900239 DB |
358 | } |
359 | ||
726a989a RB |
360 | for (i = 0; i < gimple_asm_nclobbers (stmt); i++) |
361 | { | |
362 | op = gimple_asm_clobber_op (stmt, i); | |
363 | if (simple_cst_equal(TREE_VALUE (op), memory_identifier_string) == 1) | |
364 | /* Abandon all hope, ye who enter here. */ | |
365 | local->pure_const_state = IPA_NEITHER; | |
366 | } | |
ea900239 | 367 | |
726a989a | 368 | if (gimple_asm_volatile_p (stmt)) |
ea900239 DB |
369 | local->pure_const_state = IPA_NEITHER; |
370 | } | |
371 | ||
372 | /* Check the parameters of a function call to CALL_EXPR to see if | |
373 | there are any references in the parameters that are not allowed for | |
374 | pure or const functions. Also check to see if this is either an | |
375 | indirect call, a call outside the compilation unit, or has special | |
376 | attributes that may also effect the purity. The CALL_EXPR node for | |
377 | the entire call expression. */ | |
378 | ||
379 | static void | |
726a989a | 380 | check_call (funct_state local, gimple call) |
ea900239 | 381 | { |
726a989a RB |
382 | int flags = gimple_call_flags (call); |
383 | tree lhs, callee_t = gimple_call_fndecl (call); | |
ea900239 DB |
384 | struct cgraph_node* callee; |
385 | enum availability avail = AVAIL_NOT_AVAILABLE; | |
726a989a RB |
386 | size_t i; |
387 | ||
388 | lhs = gimple_call_lhs (call); | |
389 | if (lhs) | |
390 | check_lhs_var (local, lhs); | |
ea900239 | 391 | |
726a989a RB |
392 | for (i = 0; i < gimple_call_num_args (call); i++) |
393 | check_rhs_var (local, gimple_call_arg (call, i)); | |
ea900239 DB |
394 | |
395 | /* The const and pure flags are set by a variety of places in the | |
396 | compiler (including here). If someone has already set the flags | |
397 | for the callee, (such as for some of the builtins) we will use | |
398 | them, otherwise we will compute our own information. | |
399 | ||
400 | Const and pure functions have less clobber effects than other | |
401 | functions so we process these first. Otherwise if it is a call | |
402 | outside the compilation unit or an indirect call we punt. This | |
403 | leaves local calls which will be processed by following the call | |
404 | graph. */ | |
405 | if (callee_t) | |
406 | { | |
407 | callee = cgraph_node(callee_t); | |
408 | avail = cgraph_function_body_availability (callee); | |
409 | ||
410 | /* When bad things happen to bad functions, they cannot be const | |
411 | or pure. */ | |
412 | if (setjmp_call_p (callee_t)) | |
becfd6e5 KZ |
413 | { |
414 | local->pure_const_state = IPA_NEITHER; | |
415 | local->looping = false; | |
416 | } | |
ea900239 DB |
417 | |
418 | if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL) | |
419 | switch (DECL_FUNCTION_CODE (callee_t)) | |
420 | { | |
421 | case BUILT_IN_LONGJMP: | |
422 | case BUILT_IN_NONLOCAL_GOTO: | |
423 | local->pure_const_state = IPA_NEITHER; | |
becfd6e5 | 424 | local->looping = false; |
ea900239 DB |
425 | break; |
426 | default: | |
427 | break; | |
428 | } | |
429 | } | |
430 | ||
431 | /* The callee is either unknown (indirect call) or there is just no | |
432 | scannable code for it (external call) . We look to see if there | |
433 | are any bits available for the callee (such as by declaration or | |
434 | because it is builtin) and process solely on the basis of those | |
435 | bits. */ | |
436 | if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE) | |
437 | { | |
438 | if (flags & ECF_PURE) | |
439 | { | |
440 | if (local->pure_const_state == IPA_CONST) | |
441 | local->pure_const_state = IPA_PURE; | |
442 | } | |
443 | else | |
444 | local->pure_const_state = IPA_NEITHER; | |
445 | } | |
446 | else | |
447 | { | |
448 | /* We have the code and we will scan it for the effects. */ | |
449 | if (flags & ECF_PURE) | |
450 | { | |
451 | if (local->pure_const_state == IPA_CONST) | |
452 | local->pure_const_state = IPA_PURE; | |
453 | } | |
454 | } | |
455 | } | |
456 | ||
457 | /* TP is the part of the tree currently under the microscope. | |
458 | WALK_SUBTREES is part of the walk_tree api but is unused here. | |
459 | DATA is cgraph_node of the function being walked. */ | |
460 | ||
461 | /* FIXME: When this is converted to run over SSA form, this code | |
462 | should be converted to use the operand scanner. */ | |
463 | ||
464 | static tree | |
726a989a | 465 | scan_function_op (tree *tp, int *walk_subtrees, void *data) |
ea900239 | 466 | { |
726a989a RB |
467 | struct walk_stmt_info *wi = (struct walk_stmt_info *) data; |
468 | struct cgraph_node *fn = (struct cgraph_node *) wi->info; | |
ea900239 DB |
469 | tree t = *tp; |
470 | funct_state local = get_function_state (fn); | |
471 | ||
472 | switch (TREE_CODE (t)) | |
473 | { | |
474 | case VAR_DECL: | |
475 | if (DECL_INITIAL (t)) | |
726a989a RB |
476 | walk_tree (&DECL_INITIAL (t), scan_function_op, data, visited_nodes); |
477 | *walk_subtrees = 0; | |
478 | break; | |
479 | ||
480 | case ADDR_EXPR: | |
481 | /* This case is here to find addresses on rhs of constructors in | |
482 | decl_initial of static variables. */ | |
483 | check_rhs_var (local, t); | |
ea900239 DB |
484 | *walk_subtrees = 0; |
485 | break; | |
486 | ||
726a989a RB |
487 | default: |
488 | break; | |
489 | } | |
490 | return NULL; | |
491 | } | |
492 | ||
493 | static tree | |
494 | scan_function_stmt (gimple_stmt_iterator *gsi_p, | |
495 | bool *handled_ops_p, | |
496 | struct walk_stmt_info *wi) | |
497 | { | |
498 | struct cgraph_node *fn = (struct cgraph_node *) wi->info; | |
499 | gimple stmt = gsi_stmt (*gsi_p); | |
500 | funct_state local = get_function_state (fn); | |
501 | ||
502 | switch (gimple_code (stmt)) | |
503 | { | |
504 | case GIMPLE_ASSIGN: | |
ea900239 DB |
505 | { |
506 | /* First look on the lhs and see what variable is stored to */ | |
726a989a RB |
507 | tree lhs = gimple_assign_lhs (stmt); |
508 | tree rhs1 = gimple_assign_rhs1 (stmt); | |
509 | tree rhs2 = gimple_assign_rhs2 (stmt); | |
510 | enum tree_code code = gimple_assign_rhs_code (stmt); | |
511 | ||
ea900239 DB |
512 | check_lhs_var (local, lhs); |
513 | ||
514 | /* For the purposes of figuring out what the cast affects */ | |
515 | ||
516 | /* Next check the operands on the rhs to see if they are ok. */ | |
726a989a | 517 | switch (TREE_CODE_CLASS (code)) |
ea900239 DB |
518 | { |
519 | case tcc_binary: | |
520 | { | |
726a989a RB |
521 | check_rhs_var (local, rhs1); |
522 | check_rhs_var (local, rhs2); | |
ea900239 DB |
523 | } |
524 | break; | |
525 | case tcc_unary: | |
526 | { | |
726a989a | 527 | check_rhs_var (local, rhs1); |
ea900239 DB |
528 | } |
529 | ||
530 | break; | |
531 | case tcc_reference: | |
726a989a | 532 | check_rhs_var (local, rhs1); |
ea900239 DB |
533 | break; |
534 | case tcc_declaration: | |
726a989a | 535 | check_rhs_var (local, rhs1); |
ea900239 DB |
536 | break; |
537 | case tcc_expression: | |
726a989a | 538 | switch (code) |
ea900239 DB |
539 | { |
540 | case ADDR_EXPR: | |
726a989a | 541 | check_rhs_var (local, rhs1); |
ea900239 DB |
542 | break; |
543 | default: | |
544 | break; | |
545 | } | |
546 | break; | |
547 | default: | |
548 | break; | |
549 | } | |
726a989a | 550 | *handled_ops_p = true; |
ea900239 DB |
551 | } |
552 | break; | |
553 | ||
726a989a RB |
554 | case GIMPLE_LABEL: |
555 | if (DECL_NONLOCAL (gimple_label_label (stmt))) | |
ea900239 | 556 | /* Target of long jump. */ |
becfd6e5 KZ |
557 | { |
558 | local->pure_const_state = IPA_NEITHER; | |
559 | local->looping = false; | |
560 | } | |
ea900239 DB |
561 | break; |
562 | ||
726a989a RB |
563 | case GIMPLE_CALL: |
564 | check_call (local, stmt); | |
565 | *handled_ops_p = true; | |
ea900239 DB |
566 | break; |
567 | ||
726a989a RB |
568 | case GIMPLE_ASM: |
569 | get_asm_expr_operands (local, stmt); | |
570 | *handled_ops_p = true; | |
ea900239 DB |
571 | break; |
572 | ||
573 | default: | |
574 | break; | |
575 | } | |
576 | return NULL; | |
577 | } | |
578 | ||
812dbce5 | 579 | |
ea900239 DB |
580 | /* This is the main routine for finding the reference patterns for |
581 | global variables within a function FN. */ | |
582 | ||
583 | static void | |
584 | analyze_function (struct cgraph_node *fn) | |
585 | { | |
ea900239 | 586 | tree decl = fn->decl; |
812dbce5 | 587 | funct_state l = XCNEW (struct funct_state_d); |
ea900239 | 588 | |
e2c9111c JH |
589 | if (cgraph_function_body_availability (fn) <= AVAIL_OVERWRITABLE) |
590 | return; | |
591 | ||
812dbce5 | 592 | set_function_state (fn, l); |
ea900239 DB |
593 | |
594 | l->pure_const_state = IPA_CONST; | |
595 | l->state_set_in_source = false; | |
becfd6e5 KZ |
596 | if (DECL_LOOPING_CONST_OR_PURE_P (decl)) |
597 | l->looping = true; | |
598 | else | |
599 | l->looping = false; | |
ea900239 | 600 | |
5d35c171 RG |
601 | /* If this function does not return normally or does not bind local, |
602 | do not touch this unless it has been marked as const or pure by the | |
603 | front end. */ | |
604 | if (TREE_THIS_VOLATILE (decl) | |
605 | || !targetm.binds_local_p (decl)) | |
ea900239 DB |
606 | { |
607 | l->pure_const_state = IPA_NEITHER; | |
608 | return; | |
609 | } | |
610 | ||
611 | if (TREE_READONLY (decl)) | |
612 | { | |
613 | l->pure_const_state = IPA_CONST; | |
614 | l->state_set_in_source = true; | |
615 | } | |
becfd6e5 | 616 | if (DECL_PURE_P (decl)) |
ea900239 DB |
617 | { |
618 | l->pure_const_state = IPA_PURE; | |
619 | l->state_set_in_source = true; | |
620 | } | |
621 | ||
622 | if (dump_file) | |
623 | { | |
624 | fprintf (dump_file, "\n local analysis of %s with initial value = %d\n ", | |
625 | cgraph_node_name (fn), | |
626 | l->pure_const_state); | |
627 | } | |
628 | ||
629 | if (!l->state_set_in_source) | |
630 | { | |
631 | struct function *this_cfun = DECL_STRUCT_FUNCTION (decl); | |
632 | basic_block this_block; | |
633 | ||
634 | FOR_EACH_BB_FN (this_block, this_cfun) | |
635 | { | |
726a989a RB |
636 | gimple_stmt_iterator gsi; |
637 | struct walk_stmt_info wi; | |
638 | ||
639 | memset (&wi, 0, sizeof(wi)); | |
640 | for (gsi = gsi_start_bb (this_block); | |
641 | !gsi_end_p (gsi); | |
642 | gsi_next (&gsi)) | |
ea900239 | 643 | { |
726a989a RB |
644 | wi.info = fn; |
645 | wi.pset = visited_nodes; | |
646 | walk_gimple_stmt (&gsi, scan_function_stmt, scan_function_op, | |
647 | &wi); | |
ea900239 | 648 | if (l->pure_const_state == IPA_NEITHER) |
13335ae6 | 649 | goto end; |
ea900239 DB |
650 | } |
651 | } | |
652 | ||
653 | if (l->pure_const_state != IPA_NEITHER) | |
654 | { | |
655 | tree old_decl = current_function_decl; | |
656 | /* Const functions cannot have back edges (an | |
657 | indication of possible infinite loop side | |
658 | effect. */ | |
659 | ||
660 | current_function_decl = fn->decl; | |
661 | ||
662 | /* The C++ front end, has a tendency to some times jerk away | |
663 | a function after it has created it. This should have | |
664 | been fixed. */ | |
665 | gcc_assert (DECL_STRUCT_FUNCTION (fn->decl)); | |
666 | ||
667 | push_cfun (DECL_STRUCT_FUNCTION (fn->decl)); | |
668 | ||
669 | if (mark_dfs_back_edges ()) | |
670 | l->pure_const_state = IPA_NEITHER; | |
671 | ||
672 | current_function_decl = old_decl; | |
673 | pop_cfun (); | |
674 | } | |
675 | } | |
13335ae6 AP |
676 | |
677 | end: | |
678 | if (dump_file) | |
679 | { | |
680 | fprintf (dump_file, "after local analysis of %s with initial value = %d\n ", | |
681 | cgraph_node_name (fn), | |
682 | l->pure_const_state); | |
683 | } | |
ea900239 DB |
684 | } |
685 | ||
129a37fc JH |
686 | /* Called when new function is inserted to callgraph late. */ |
687 | static void | |
688 | add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED) | |
689 | { | |
e2c9111c JH |
690 | if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE) |
691 | return; | |
129a37fc JH |
692 | /* There are some shared nodes, in particular the initializers on |
693 | static declarations. We do not need to scan them more than once | |
694 | since all we would be interested in are the addressof | |
695 | operations. */ | |
696 | visited_nodes = pointer_set_create (); | |
697 | analyze_function (node); | |
698 | pointer_set_destroy (visited_nodes); | |
699 | visited_nodes = NULL; | |
700 | } | |
701 | ||
e2c9111c JH |
702 | /* Called when new clone is inserted to callgraph late. */ |
703 | ||
704 | static void | |
705 | duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst, | |
706 | void *data ATTRIBUTE_UNUSED) | |
707 | { | |
708 | if (get_function_state (src)) | |
709 | { | |
710 | funct_state l = XNEW (struct funct_state_d); | |
711 | gcc_assert (!get_function_state (dst)); | |
712 | memcpy (l, get_function_state (src), sizeof (*l)); | |
713 | set_function_state (dst, l); | |
714 | } | |
715 | } | |
716 | ||
717 | /* Called when new clone is inserted to callgraph late. */ | |
718 | ||
719 | static void | |
720 | remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED) | |
721 | { | |
722 | if (get_function_state (node)) | |
723 | { | |
724 | free (get_function_state (node)); | |
725 | set_function_state (node, NULL); | |
726 | } | |
727 | } | |
728 | ||
ea900239 | 729 | \f |
812dbce5 JH |
730 | /* Analyze each function in the cgraph to see if it is locally PURE or |
731 | CONST. */ | |
ea900239 | 732 | |
812dbce5 JH |
733 | static void |
734 | generate_summary (void) | |
ea900239 DB |
735 | { |
736 | struct cgraph_node *node; | |
ea900239 | 737 | |
e2c9111c JH |
738 | node_removal_hook_holder = |
739 | cgraph_add_node_removal_hook (&remove_node_data, NULL); | |
740 | node_duplication_hook_holder = | |
741 | cgraph_add_node_duplication_hook (&duplicate_node_data, NULL); | |
129a37fc JH |
742 | function_insertion_hook_holder = |
743 | cgraph_add_function_insertion_hook (&add_new_function, NULL); | |
ea900239 DB |
744 | /* There are some shared nodes, in particular the initializers on |
745 | static declarations. We do not need to scan them more than once | |
746 | since all we would be interested in are the addressof | |
747 | operations. */ | |
748 | visited_nodes = pointer_set_create (); | |
749 | ||
750 | /* Process all of the functions. | |
751 | ||
e2c9111c | 752 | We do NOT process any AVAIL_OVERWRITABLE functions, we cannot |
ea900239 | 753 | guarantee that what we learn about the one we see will be true |
fa10beec | 754 | for the one that overrides it. |
ea900239 DB |
755 | */ |
756 | for (node = cgraph_nodes; node; node = node->next) | |
e2c9111c | 757 | if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE) |
ea900239 DB |
758 | analyze_function (node); |
759 | ||
760 | pointer_set_destroy (visited_nodes); | |
761 | visited_nodes = NULL; | |
812dbce5 JH |
762 | } |
763 | ||
764 | /* Produce the global information by preforming a transitive closure | |
765 | on the local information that was produced by generate_summary. | |
766 | Note that there is no function_transform pass since this only | |
767 | updates the function_decl. */ | |
768 | ||
769 | static unsigned int | |
770 | propagate (void) | |
771 | { | |
772 | struct cgraph_node *node; | |
773 | struct cgraph_node *w; | |
774 | struct cgraph_node **order = | |
775 | XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); | |
776 | int order_pos; | |
777 | int i; | |
778 | struct ipa_dfs_info * w_info; | |
779 | ||
129a37fc | 780 | cgraph_remove_function_insertion_hook (function_insertion_hook_holder); |
e2c9111c JH |
781 | cgraph_remove_node_duplication_hook (node_duplication_hook_holder); |
782 | cgraph_remove_node_removal_hook (node_removal_hook_holder); | |
812dbce5 | 783 | order_pos = ipa_utils_reduced_inorder (order, true, false); |
ea900239 DB |
784 | if (dump_file) |
785 | { | |
786 | dump_cgraph (dump_file); | |
787 | ipa_utils_print_order(dump_file, "reduced", order, order_pos); | |
788 | } | |
789 | ||
790 | /* Propagate the local information thru the call graph to produce | |
791 | the global information. All the nodes within a cycle will have | |
792 | the same info so we collapse cycles first. Then we can do the | |
793 | propagation in one pass from the leaves to the roots. */ | |
794 | for (i = 0; i < order_pos; i++ ) | |
795 | { | |
796 | enum pure_const_state_e pure_const_state = IPA_CONST; | |
becfd6e5 | 797 | bool looping = false; |
17541d72 | 798 | int count = 0; |
ea900239 DB |
799 | node = order[i]; |
800 | ||
801 | /* Find the worst state for any node in the cycle. */ | |
802 | w = node; | |
803 | while (w) | |
804 | { | |
805 | funct_state w_l = get_function_state (w); | |
806 | if (pure_const_state < w_l->pure_const_state) | |
807 | pure_const_state = w_l->pure_const_state; | |
808 | ||
becfd6e5 KZ |
809 | if (w_l->looping) |
810 | looping = true; | |
811 | ||
ea900239 DB |
812 | if (pure_const_state == IPA_NEITHER) |
813 | break; | |
814 | ||
815 | if (!w_l->state_set_in_source) | |
816 | { | |
817 | struct cgraph_edge *e; | |
17541d72 KZ |
818 | count++; |
819 | ||
17541d72 | 820 | if (count > 1) |
becfd6e5 | 821 | looping = true; |
17541d72 | 822 | |
ea900239 DB |
823 | for (e = w->callees; e; e = e->next_callee) |
824 | { | |
825 | struct cgraph_node *y = e->callee; | |
17541d72 | 826 | |
e2c9111c | 827 | if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE) |
ea900239 DB |
828 | { |
829 | funct_state y_l = get_function_state (y); | |
830 | if (pure_const_state < y_l->pure_const_state) | |
831 | pure_const_state = y_l->pure_const_state; | |
832 | if (pure_const_state == IPA_NEITHER) | |
833 | break; | |
becfd6e5 KZ |
834 | if (y_l->looping) |
835 | looping = true; | |
ea900239 DB |
836 | } |
837 | } | |
838 | } | |
c5274326 | 839 | w_info = (struct ipa_dfs_info *) w->aux; |
ea900239 DB |
840 | w = w_info->next_cycle; |
841 | } | |
842 | ||
843 | /* Copy back the region's pure_const_state which is shared by | |
844 | all nodes in the region. */ | |
845 | w = node; | |
846 | while (w) | |
847 | { | |
848 | funct_state w_l = get_function_state (w); | |
849 | ||
850 | /* All nodes within a cycle share the same info. */ | |
851 | if (!w_l->state_set_in_source) | |
852 | { | |
853 | w_l->pure_const_state = pure_const_state; | |
812dbce5 JH |
854 | w_l->looping = looping; |
855 | ||
ea900239 DB |
856 | switch (pure_const_state) |
857 | { | |
858 | case IPA_CONST: | |
859 | TREE_READONLY (w->decl) = 1; | |
becfd6e5 | 860 | DECL_LOOPING_CONST_OR_PURE_P (w->decl) = looping; |
ea900239 | 861 | if (dump_file) |
becfd6e5 KZ |
862 | fprintf (dump_file, "Function found to be %sconst: %s\n", |
863 | looping ? "looping " : "", | |
ea900239 DB |
864 | lang_hooks.decl_printable_name(w->decl, 2)); |
865 | break; | |
866 | ||
867 | case IPA_PURE: | |
becfd6e5 KZ |
868 | DECL_PURE_P (w->decl) = 1; |
869 | DECL_LOOPING_CONST_OR_PURE_P (w->decl) = looping; | |
ea900239 | 870 | if (dump_file) |
becfd6e5 KZ |
871 | fprintf (dump_file, "Function found to be %spure: %s\n", |
872 | looping ? "looping " : "", | |
ea900239 DB |
873 | lang_hooks.decl_printable_name(w->decl, 2)); |
874 | break; | |
875 | ||
876 | default: | |
877 | break; | |
878 | } | |
879 | } | |
c5274326 | 880 | w_info = (struct ipa_dfs_info *) w->aux; |
ea900239 DB |
881 | w = w_info->next_cycle; |
882 | } | |
883 | } | |
884 | ||
885 | /* Cleanup. */ | |
886 | for (node = cgraph_nodes; node; node = node->next) | |
812dbce5 JH |
887 | { |
888 | /* Get rid of the aux information. */ | |
889 | if (node->aux) | |
890 | { | |
891 | w_info = (struct ipa_dfs_info *) node->aux; | |
892 | free (node->aux); | |
893 | node->aux = NULL; | |
894 | } | |
e2c9111c | 895 | if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE) |
812dbce5 JH |
896 | free (get_function_state (node)); |
897 | } | |
898 | ||
ea900239 | 899 | free (order); |
e2c9111c | 900 | VEC_free (funct_state, heap, funct_state_vec); |
812dbce5 | 901 | finish_state (); |
c2924966 | 902 | return 0; |
ea900239 DB |
903 | } |
904 | ||
905 | static bool | |
906 | gate_pure_const (void) | |
907 | { | |
e2c9111c | 908 | return (flag_ipa_pure_const |
ea900239 DB |
909 | /* Don't bother doing anything if the program has errors. */ |
910 | && !(errorcount || sorrycount)); | |
911 | } | |
912 | ||
812dbce5 | 913 | struct ipa_opt_pass pass_ipa_pure_const = |
ea900239 | 914 | { |
8ddbbcae | 915 | { |
812dbce5 | 916 | IPA_PASS, |
d4feded7 | 917 | "pure-const", /* name */ |
ea900239 | 918 | gate_pure_const, /* gate */ |
812dbce5 | 919 | propagate, /* execute */ |
ea900239 DB |
920 | NULL, /* sub */ |
921 | NULL, /* next */ | |
922 | 0, /* static_pass_number */ | |
923 | TV_IPA_PURE_CONST, /* tv_id */ | |
924 | 0, /* properties_required */ | |
925 | 0, /* properties_provided */ | |
926 | 0, /* properties_destroyed */ | |
927 | 0, /* todo_flags_start */ | |
8ddbbcae | 928 | 0 /* todo_flags_finish */ |
812dbce5 JH |
929 | }, |
930 | generate_summary, /* generate_summary */ | |
931 | NULL, /* write_summary */ | |
932 | NULL, /* read_summary */ | |
933 | NULL, /* function_read_summary */ | |
934 | 0, /* TODOs */ | |
935 | NULL, /* function_transform */ | |
936 | NULL /* variable_transform */ | |
ea900239 | 937 | }; |