|
0
|
1 /* Callgraph based analysis of static variables.
|
|
|
2 Copyright (C) 2004, 2005, 2007, 2008 Free Software Foundation, Inc.
|
|
|
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
|
|
|
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 /* 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).
|
|
|
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"
|
|
|
47 #include "gimple.h"
|
|
|
48 #include "cgraph.h"
|
|
|
49 #include "output.h"
|
|
|
50 #include "flags.h"
|
|
|
51 #include "timevar.h"
|
|
|
52 #include "diagnostic.h"
|
|
|
53 #include "langhooks.h"
|
|
|
54 #include "target.h"
|
|
|
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
|
|
|
68 /* Holder for the const_state. There is one of these per function
|
|
|
69 decl. */
|
|
|
70 struct funct_state_d
|
|
|
71 {
|
|
|
72 /* See above. */
|
|
|
73 enum pure_const_state_e pure_const_state;
|
|
|
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. */
|
|
|
81 bool looping;
|
|
|
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;
|
|
|
87 };
|
|
|
88
|
|
|
89 typedef struct funct_state_d * funct_state;
|
|
|
90
|
|
|
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 DEF_VEC_P (funct_state);
|
|
|
98 DEF_VEC_ALLOC_P (funct_state, heap);
|
|
|
99 static VEC (funct_state, heap) *funct_state_vec;
|
|
|
100
|
|
|
101 /* Holders of ipa cgraph hooks: */
|
|
|
102 static struct cgraph_node_hook_list *function_insertion_hook_holder;
|
|
|
103 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
|
|
|
104 static struct cgraph_node_hook_list *node_removal_hook_holder;
|
|
|
105
|
|
|
106 /* Init the function state. */
|
|
|
107
|
|
|
108 static void
|
|
|
109 finish_state (void)
|
|
|
110 {
|
|
|
111 free (funct_state_vec);
|
|
|
112 }
|
|
|
113
|
|
|
114
|
|
|
115 /* Return the function state from NODE. */
|
|
|
116
|
|
|
117 static inline funct_state
|
|
|
118 get_function_state (struct cgraph_node *node)
|
|
|
119 {
|
|
|
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);
|
|
|
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 {
|
|
|
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);
|
|
|
135 }
|
|
|
136
|
|
|
137 /* Check to see if the use (or definition when CHECKING_WRITE is true)
|
|
|
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;
|
|
|
149 local->looping = false;
|
|
|
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;
|
|
|
158 local->looping = false;
|
|
|
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)
|
|
|
170 {
|
|
|
171 local->pure_const_state = IPA_NEITHER;
|
|
|
172 local->looping = false;
|
|
|
173 return;
|
|
|
174 }
|
|
|
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 {
|
|
|
222 if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)
|
|
|
223 || TREE_CODE (t) == SSA_NAME)
|
|
|
224 return;
|
|
|
225
|
|
|
226 /* Any tree which is volatile disqualifies this function from being
|
|
|
227 const or pure. */
|
|
|
228 if (TREE_THIS_VOLATILE (t))
|
|
|
229 {
|
|
|
230 local->pure_const_state = IPA_NEITHER;
|
|
|
231 local->looping = false;
|
|
|
232 return;
|
|
|
233 }
|
|
|
234
|
|
|
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
|
|
|
252 indirect reference that occurs on the rhs disqualifies the
|
|
|
253 function from being const. */
|
|
|
254 if (checking_write)
|
|
|
255 {
|
|
|
256 local->pure_const_state = IPA_NEITHER;
|
|
|
257 local->looping = false;
|
|
|
258 return;
|
|
|
259 }
|
|
|
260 else if (local->pure_const_state == IPA_CONST)
|
|
|
261 local->pure_const_state = IPA_PURE;
|
|
|
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
|
|
|
328 get_asm_expr_operands (funct_state local, gimple stmt)
|
|
|
329 {
|
|
|
330 size_t noutputs = gimple_asm_noutputs (stmt);
|
|
|
331 const char **oconstraints
|
|
|
332 = (const char **) alloca ((noutputs) * sizeof (const char *));
|
|
|
333 size_t i;
|
|
|
334 tree op;
|
|
|
335 const char *constraint;
|
|
|
336 bool allows_mem, allows_reg, is_inout;
|
|
|
337
|
|
|
338 for (i = 0; i < noutputs; i++)
|
|
|
339 {
|
|
|
340 op = gimple_asm_output_op (stmt, i);
|
|
|
341 oconstraints[i] = constraint
|
|
|
342 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op)));
|
|
|
343 parse_output_constraint (&constraint, i, 0, 0,
|
|
|
344 &allows_mem, &allows_reg, &is_inout);
|
|
|
345
|
|
|
346 check_lhs_var (local, TREE_VALUE (op));
|
|
|
347 }
|
|
|
348
|
|
|
349 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
|
|
|
350 {
|
|
|
351 op = gimple_asm_input_op (stmt, i);
|
|
|
352 constraint
|
|
|
353 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op)));
|
|
|
354 parse_input_constraint (&constraint, 0, 0, noutputs, 0,
|
|
|
355 oconstraints, &allows_mem, &allows_reg);
|
|
|
356
|
|
|
357 check_rhs_var (local, TREE_VALUE (op));
|
|
|
358 }
|
|
|
359
|
|
|
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 }
|
|
|
367
|
|
|
368 if (gimple_asm_volatile_p (stmt))
|
|
|
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
|
|
|
380 check_call (funct_state local, gimple call)
|
|
|
381 {
|
|
|
382 int flags = gimple_call_flags (call);
|
|
|
383 tree lhs, callee_t = gimple_call_fndecl (call);
|
|
|
384 struct cgraph_node* callee;
|
|
|
385 enum availability avail = AVAIL_NOT_AVAILABLE;
|
|
|
386 size_t i;
|
|
|
387
|
|
|
388 lhs = gimple_call_lhs (call);
|
|
|
389 if (lhs)
|
|
|
390 check_lhs_var (local, lhs);
|
|
|
391
|
|
|
392 for (i = 0; i < gimple_call_num_args (call); i++)
|
|
|
393 check_rhs_var (local, gimple_call_arg (call, i));
|
|
|
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))
|
|
|
413 {
|
|
|
414 local->pure_const_state = IPA_NEITHER;
|
|
|
415 local->looping = false;
|
|
|
416 }
|
|
|
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;
|
|
|
424 local->looping = false;
|
|
|
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
|
|
|
465 scan_function_op (tree *tp, int *walk_subtrees, void *data)
|
|
|
466 {
|
|
|
467 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
|
|
|
468 struct cgraph_node *fn = (struct cgraph_node *) wi->info;
|
|
|
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))
|
|
|
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);
|
|
|
484 *walk_subtrees = 0;
|
|
|
485 break;
|
|
|
486
|
|
|
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:
|
|
|
505 {
|
|
|
506 /* First look on the lhs and see what variable is stored to */
|
|
|
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
|
|
|
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. */
|
|
|
517 switch (TREE_CODE_CLASS (code))
|
|
|
518 {
|
|
|
519 case tcc_binary:
|
|
|
520 {
|
|
|
521 check_rhs_var (local, rhs1);
|
|
|
522 check_rhs_var (local, rhs2);
|
|
|
523 }
|
|
|
524 break;
|
|
|
525 case tcc_unary:
|
|
|
526 {
|
|
|
527 check_rhs_var (local, rhs1);
|
|
|
528 }
|
|
|
529
|
|
|
530 break;
|
|
|
531 case tcc_reference:
|
|
|
532 check_rhs_var (local, rhs1);
|
|
|
533 break;
|
|
|
534 case tcc_declaration:
|
|
|
535 check_rhs_var (local, rhs1);
|
|
|
536 break;
|
|
|
537 case tcc_expression:
|
|
|
538 switch (code)
|
|
|
539 {
|
|
|
540 case ADDR_EXPR:
|
|
|
541 check_rhs_var (local, rhs1);
|
|
|
542 break;
|
|
|
543 default:
|
|
|
544 break;
|
|
|
545 }
|
|
|
546 break;
|
|
|
547 default:
|
|
|
548 break;
|
|
|
549 }
|
|
|
550 *handled_ops_p = true;
|
|
|
551 }
|
|
|
552 break;
|
|
|
553
|
|
|
554 case GIMPLE_LABEL:
|
|
|
555 if (DECL_NONLOCAL (gimple_label_label (stmt)))
|
|
|
556 /* Target of long jump. */
|
|
|
557 {
|
|
|
558 local->pure_const_state = IPA_NEITHER;
|
|
|
559 local->looping = false;
|
|
|
560 }
|
|
|
561 break;
|
|
|
562
|
|
|
563 case GIMPLE_CALL:
|
|
|
564 check_call (local, stmt);
|
|
|
565 *handled_ops_p = true;
|
|
|
566 break;
|
|
|
567
|
|
|
568 case GIMPLE_ASM:
|
|
|
569 get_asm_expr_operands (local, stmt);
|
|
|
570 *handled_ops_p = true;
|
|
|
571 break;
|
|
|
572
|
|
|
573 default:
|
|
|
574 break;
|
|
|
575 }
|
|
|
576 return NULL;
|
|
|
577 }
|
|
|
578
|
|
|
579
|
|
|
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 {
|
|
|
586 tree decl = fn->decl;
|
|
|
587 funct_state l = XCNEW (struct funct_state_d);
|
|
|
588
|
|
|
589 if (cgraph_function_body_availability (fn) <= AVAIL_OVERWRITABLE)
|
|
|
590 return;
|
|
|
591
|
|
|
592 set_function_state (fn, l);
|
|
|
593
|
|
|
594 l->pure_const_state = IPA_CONST;
|
|
|
595 l->state_set_in_source = false;
|
|
|
596 if (DECL_LOOPING_CONST_OR_PURE_P (decl))
|
|
|
597 l->looping = true;
|
|
|
598 else
|
|
|
599 l->looping = false;
|
|
|
600
|
|
|
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))
|
|
|
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 }
|
|
|
616 if (DECL_PURE_P (decl))
|
|
|
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 {
|
|
|
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))
|
|
|
643 {
|
|
|
644 wi.info = fn;
|
|
|
645 wi.pset = visited_nodes;
|
|
|
646 walk_gimple_stmt (&gsi, scan_function_stmt, scan_function_op,
|
|
|
647 &wi);
|
|
|
648 if (l->pure_const_state == IPA_NEITHER)
|
|
|
649 goto end;
|
|
|
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 }
|
|
|
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 }
|
|
|
684 }
|
|
|
685
|
|
|
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 {
|
|
|
690 if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
|
|
|
691 return;
|
|
|
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
|
|
|
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
|
|
|
729
|
|
|
730 /* Analyze each function in the cgraph to see if it is locally PURE or
|
|
|
731 CONST. */
|
|
|
732
|
|
|
733 static void
|
|
|
734 generate_summary (void)
|
|
|
735 {
|
|
|
736 struct cgraph_node *node;
|
|
|
737
|
|
|
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);
|
|
|
742 function_insertion_hook_holder =
|
|
|
743 cgraph_add_function_insertion_hook (&add_new_function, NULL);
|
|
|
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
|
|
|
752 We do NOT process any AVAIL_OVERWRITABLE functions, we cannot
|
|
|
753 guarantee that what we learn about the one we see will be true
|
|
|
754 for the one that overrides it.
|
|
|
755 */
|
|
|
756 for (node = cgraph_nodes; node; node = node->next)
|
|
|
757 if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
|
|
|
758 analyze_function (node);
|
|
|
759
|
|
|
760 pointer_set_destroy (visited_nodes);
|
|
|
761 visited_nodes = NULL;
|
|
|
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
|
|
|
780 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
|
|
|
781 cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
|
|
|
782 cgraph_remove_node_removal_hook (node_removal_hook_holder);
|
|
|
783 order_pos = ipa_utils_reduced_inorder (order, true, false);
|
|
|
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;
|
|
|
797 bool looping = false;
|
|
|
798 int count = 0;
|
|
|
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
|
|
|
809 if (w_l->looping)
|
|
|
810 looping = true;
|
|
|
811
|
|
|
812 if (pure_const_state == IPA_NEITHER)
|
|
|
813 break;
|
|
|
814
|
|
|
815 if (!w_l->state_set_in_source)
|
|
|
816 {
|
|
|
817 struct cgraph_edge *e;
|
|
|
818 count++;
|
|
|
819
|
|
|
820 if (count > 1)
|
|
|
821 looping = true;
|
|
|
822
|
|
|
823 for (e = w->callees; e; e = e->next_callee)
|
|
|
824 {
|
|
|
825 struct cgraph_node *y = e->callee;
|
|
|
826
|
|
|
827 if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
|
|
|
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;
|
|
|
834 if (y_l->looping)
|
|
|
835 looping = true;
|
|
|
836 }
|
|
|
837 }
|
|
|
838 }
|
|
|
839 w_info = (struct ipa_dfs_info *) w->aux;
|
|
|
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;
|
|
|
854 w_l->looping = looping;
|
|
|
855
|
|
|
856 switch (pure_const_state)
|
|
|
857 {
|
|
|
858 case IPA_CONST:
|
|
|
859 TREE_READONLY (w->decl) = 1;
|
|
|
860 DECL_LOOPING_CONST_OR_PURE_P (w->decl) = looping;
|
|
|
861 if (dump_file)
|
|
|
862 fprintf (dump_file, "Function found to be %sconst: %s\n",
|
|
|
863 looping ? "looping " : "",
|
|
|
864 lang_hooks.decl_printable_name(w->decl, 2));
|
|
|
865 break;
|
|
|
866
|
|
|
867 case IPA_PURE:
|
|
|
868 DECL_PURE_P (w->decl) = 1;
|
|
|
869 DECL_LOOPING_CONST_OR_PURE_P (w->decl) = looping;
|
|
|
870 if (dump_file)
|
|
|
871 fprintf (dump_file, "Function found to be %spure: %s\n",
|
|
|
872 looping ? "looping " : "",
|
|
|
873 lang_hooks.decl_printable_name(w->decl, 2));
|
|
|
874 break;
|
|
|
875
|
|
|
876 default:
|
|
|
877 break;
|
|
|
878 }
|
|
|
879 }
|
|
|
880 w_info = (struct ipa_dfs_info *) w->aux;
|
|
|
881 w = w_info->next_cycle;
|
|
|
882 }
|
|
|
883 }
|
|
|
884
|
|
|
885 /* Cleanup. */
|
|
|
886 for (node = cgraph_nodes; node; node = node->next)
|
|
|
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 }
|
|
|
895 if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
|
|
|
896 free (get_function_state (node));
|
|
|
897 }
|
|
|
898
|
|
|
899 free (order);
|
|
|
900 VEC_free (funct_state, heap, funct_state_vec);
|
|
|
901 finish_state ();
|
|
|
902 return 0;
|
|
|
903 }
|
|
|
904
|
|
|
905 static bool
|
|
|
906 gate_pure_const (void)
|
|
|
907 {
|
|
|
908 return (flag_ipa_pure_const
|
|
|
909 /* Don't bother doing anything if the program has errors. */
|
|
|
910 && !(errorcount || sorrycount));
|
|
|
911 }
|
|
|
912
|
|
|
913 struct ipa_opt_pass pass_ipa_pure_const =
|
|
|
914 {
|
|
|
915 {
|
|
|
916 IPA_PASS,
|
|
|
917 "pure-const", /* name */
|
|
|
918 gate_pure_const, /* gate */
|
|
|
919 propagate, /* execute */
|
|
|
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 */
|
|
|
928 0 /* todo_flags_finish */
|
|
|
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 */
|
|
|
937 };
|
