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