Branch data Line data Source code
1 : : /* Tree based points-to analysis
2 : : Copyright (C) 2005-2025 Free Software Foundation, Inc.
3 : : Contributed by Daniel Berlin <dberlin@dberlin.org>
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify
8 : : under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3 of the License, or
10 : : (at your option) any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful,
13 : : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : GNU General Public License 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 : : #include "config.h"
22 : : #include "system.h"
23 : : #include "coretypes.h"
24 : : #include "backend.h"
25 : : #include "rtl.h"
26 : : #include "tree.h"
27 : : #include "gimple.h"
28 : : #include "alloc-pool.h"
29 : : #include "tree-pass.h"
30 : : #include "ssa.h"
31 : : #include "cgraph.h"
32 : : #include "tree-pretty-print.h"
33 : : #include "diagnostic-core.h"
34 : : #include "fold-const.h"
35 : : #include "stor-layout.h"
36 : : #include "stmt.h"
37 : : #include "gimple-iterator.h"
38 : : #include "tree-into-ssa.h"
39 : : #include "tree-dfa.h"
40 : : #include "gimple-walk.h"
41 : : #include "varasm.h"
42 : : #include "stringpool.h"
43 : : #include "attribs.h"
44 : : #include "tree-ssa.h"
45 : : #include "tree-cfg.h"
46 : : #include "gimple-range.h"
47 : : #include "ipa-modref-tree.h"
48 : : #include "ipa-modref.h"
49 : : #include "attr-fnspec.h"
50 : :
51 : : #include "tree-ssa-structalias.h"
52 : : #include "pta-andersen.h"
53 : : #include "gimple-ssa-pta-constraints.h"
54 : :
55 : : /* The idea behind this analyzer is to generate set constraints from the
56 : : program, then solve the resulting constraints in order to generate the
57 : : points-to sets.
58 : :
59 : : Set constraints are a way of modeling program analysis problems that
60 : : involve sets. They consist of an inclusion constraint language,
61 : : describing the variables (each variable is a set) and operations that
62 : : are involved on the variables, and a set of rules that derive facts
63 : : from these operations. To solve a system of set constraints, you derive
64 : : all possible facts under the rules, which gives you the correct sets
65 : : as a consequence.
66 : :
67 : : See "Efficient Field-sensitive pointer analysis for C" by "David
68 : : J. Pearce and Paul H. J. Kelly and Chris Hankin", at
69 : : http://citeseer.ist.psu.edu/pearce04efficient.html
70 : :
71 : : Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
72 : : of C Code in a Second" by "Nevin Heintze and Olivier Tardieu" at
73 : : http://citeseer.ist.psu.edu/heintze01ultrafast.html
74 : :
75 : : There are three types of real constraint expressions, DEREF,
76 : : ADDRESSOF, and SCALAR. Each constraint expression consists
77 : : of a constraint type, a variable, and an offset.
78 : :
79 : : SCALAR is a constraint expression type used to represent x, whether
80 : : it appears on the LHS or the RHS of a statement.
81 : : DEREF is a constraint expression type used to represent *x, whether
82 : : it appears on the LHS or the RHS of a statement.
83 : : ADDRESSOF is a constraint expression used to represent &x, whether
84 : : it appears on the LHS or the RHS of a statement.
85 : :
86 : : Each pointer variable in the program is assigned an integer id, and
87 : : each field of a structure variable is assigned an integer id as well.
88 : :
89 : : Structure variables are linked to their list of fields through a "next
90 : : field" in each variable that points to the next field in offset
91 : : order.
92 : : Each variable for a structure field has
93 : :
94 : : 1. "size", that tells the size in bits of that field.
95 : : 2. "fullsize", that tells the size in bits of the entire structure.
96 : : 3. "offset", that tells the offset in bits from the beginning of the
97 : : structure to this field.
98 : :
99 : : Thus,
100 : : struct f
101 : : {
102 : : int a;
103 : : int b;
104 : : } foo;
105 : : int *bar;
106 : :
107 : : looks like
108 : :
109 : : foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
110 : : foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
111 : : bar -> id 3, size 32, offset 0, fullsize 32, next NULL
112 : :
113 : :
114 : : In order to solve the system of set constraints, the following is
115 : : done:
116 : :
117 : : 1. Each constraint variable x has a solution set associated with it,
118 : : Sol(x).
119 : :
120 : : 2. Constraints are separated into direct, copy, and complex.
121 : : Direct constraints are ADDRESSOF constraints that require no extra
122 : : processing, such as P = &Q
123 : : Copy constraints are those of the form P = Q.
124 : : Complex constraints are all the constraints involving dereferences
125 : : and offsets (including offsetted copies).
126 : :
127 : : 3. All direct constraints of the form P = &Q are processed, such
128 : : that Q is added to Sol(P)
129 : :
130 : : 4. All complex constraints for a given constraint variable are stored in a
131 : : linked list attached to that variable's node.
132 : :
133 : : 5. A directed graph is built out of the copy constraints. Each
134 : : constraint variable is a node in the graph, and an edge from
135 : : Q to P is added for each copy constraint of the form P = Q
136 : :
137 : : 6. The graph is then walked, and solution sets are
138 : : propagated along the copy edges, such that an edge from Q to P
139 : : causes Sol(P) <- Sol(P) union Sol(Q).
140 : :
141 : : 7. As we visit each node, all complex constraints associated with
142 : : that node are processed by adding appropriate copy edges to the graph, or the
143 : : appropriate variables to the solution set.
144 : :
145 : : 8. The process of walking the graph is iterated until no solution
146 : : sets change.
147 : :
148 : : Prior to walking the graph in steps 6 and 7, We perform static
149 : : cycle elimination on the constraint graph, as well
150 : : as off-line variable substitution.
151 : :
152 : : TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
153 : : on and turned into anything), but isn't. You can just see what offset
154 : : inside the pointed-to struct it's going to access.
155 : :
156 : : TODO: Constant bounded arrays can be handled as if they were structs of the
157 : : same number of elements.
158 : :
159 : : TODO: Modeling heap and incoming pointers becomes much better if we
160 : : add fields to them as we discover them, which we could do.
161 : :
162 : : TODO: We could handle unions, but to be honest, it's probably not
163 : : worth the pain or slowdown. */
164 : :
165 : : /* IPA-PTA optimizations possible.
166 : :
167 : : When the indirect function called is ANYTHING we can add disambiguation
168 : : based on the function signatures (or simply the parameter count which
169 : : is the varinfo size). We also do not need to consider functions that
170 : : do not have their address taken.
171 : :
172 : : The is_global_var bit which marks escape points is overly conservative
173 : : in IPA mode. Split it to is_escape_point and is_global_var - only
174 : : externally visible globals are escape points in IPA mode.
175 : : There is now is_ipa_escape_point but this is only used in a few
176 : : selected places.
177 : :
178 : : The way we introduce DECL_PT_UID to avoid fixing up all points-to
179 : : sets in the translation unit when we copy a DECL during inlining
180 : : pessimizes precision. The advantage is that the DECL_PT_UID keeps
181 : : compile-time and memory usage overhead low - the points-to sets
182 : : do not grow or get unshared as they would during a fixup phase.
183 : : An alternative solution is to delay IPA PTA until after all
184 : : inlining transformations have been applied.
185 : :
186 : : The way we propagate clobber/use information isn't optimized.
187 : : It should use a new complex constraint that properly filters
188 : : out local variables of the callee (though that would make
189 : : the sets invalid after inlining). OTOH we might as well
190 : : admit defeat to WHOPR and simply do all the clobber/use analysis
191 : : and propagation after PTA finished but before we threw away
192 : : points-to information for memory variables. WHOPR and PTA
193 : : do not play along well anyway - the whole constraint solving
194 : : would need to be done in WPA phase and it will be very interesting
195 : : to apply the results to local SSA names during LTRANS phase.
196 : :
197 : : We probably should compute a per-function unit-ESCAPE solution
198 : : propagating it simply like the clobber / uses solutions. The
199 : : solution can go alongside the non-IPA escaped solution and be
200 : : used to query which vars escape the unit through a function.
201 : : This is also required to make the escaped-HEAP trick work in IPA mode.
202 : :
203 : : We never put function decls in points-to sets so we do not
204 : : keep the set of called functions for indirect calls.
205 : :
206 : : And probably more. */
207 : :
208 : : using namespace pointer_analysis;
209 : :
210 : : /* Pool of variable info structures. */
211 : : static object_allocator<variable_info> variable_info_pool
212 : : ("Variable info pool");
213 : :
214 : : /* Map varinfo to final pt_solution. */
215 : : static hash_map<varinfo_t, pt_solution *> *final_solutions;
216 : : static struct obstack final_solutions_obstack;
217 : :
218 : :
219 : : namespace pointer_analysis {
220 : :
221 : : bool use_field_sensitive = true;
222 : : int in_ipa_mode = 0;
223 : :
224 : : /* Used for points-to sets. */
225 : : bitmap_obstack pta_obstack;
226 : :
227 : : /* Used for oldsolution members of variables. */
228 : : bitmap_obstack oldpta_obstack;
229 : :
230 : : /* Table of variable info structures for constraint variables.
231 : : Indexed directly by variable info id. */
232 : : vec<varinfo_t> varmap;
233 : :
234 : : /* List of constraints that we use to build the constraint graph from. */
235 : : vec<constraint_t> constraints;
236 : :
237 : : /* The representative variable for a variable. The points-to solution for a
238 : : var can be found in its rep. Trivially, a var can be its own rep.
239 : :
240 : : The solver provides this array once it is done solving. */
241 : : unsigned int *var_rep;
242 : :
243 : : struct constraint_stats stats;
244 : :
245 : : /* Find the first varinfo in the same variable as START that overlaps with
246 : : OFFSET. Return NULL if we can't find one. */
247 : :
248 : : varinfo_t
249 : 1061610 : first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
250 : : {
251 : : /* If the offset is outside of the variable, bail out. */
252 : 1061610 : if (offset >= start->fullsize)
253 : : return NULL;
254 : :
255 : : /* If we cannot reach offset from start, lookup the first field
256 : : and start from there. */
257 : 1056866 : if (start->offset > offset)
258 : 0 : start = get_varinfo (start->head);
259 : :
260 : 2961709 : while (start)
261 : : {
262 : : /* We may not find a variable in the field list with the actual
263 : : offset when we have glommed a structure to a variable.
264 : : In that case, however, offset should still be within the size
265 : : of the variable. */
266 : 2961709 : if (offset >= start->offset
267 : 2961709 : && (offset - start->offset) < start->size)
268 : : return start;
269 : :
270 : 1904843 : start = vi_next (start);
271 : : }
272 : :
273 : : return NULL;
274 : : }
275 : :
276 : : /* Find the first varinfo in the same variable as START that overlaps with
277 : : OFFSET. If there is no such varinfo the varinfo directly preceding
278 : : OFFSET is returned. */
279 : :
280 : : varinfo_t
281 : 17252726 : first_or_preceding_vi_for_offset (varinfo_t start,
282 : : unsigned HOST_WIDE_INT offset)
283 : : {
284 : : /* If we cannot reach offset from start, lookup the first field
285 : : and start from there. */
286 : 17252726 : if (start->offset > offset)
287 : 300084 : start = get_varinfo (start->head);
288 : :
289 : : /* We may not find a variable in the field list with the actual
290 : : offset when we have glommed a structure to a variable.
291 : : In that case, however, offset should still be within the size
292 : : of the variable.
293 : : If we got beyond the offset we look for return the field
294 : : directly preceding offset which may be the last field. */
295 : 64213037 : while (start->next
296 : 54725687 : && offset >= start->offset
297 : 118932685 : && !((offset - start->offset) < start->size))
298 : 46960311 : start = vi_next (start);
299 : :
300 : 17252726 : return start;
301 : : }
302 : :
303 : : /* Determine global memory access of call STMT and update
304 : : WRITES_GLOBAL_MEMORY, READS_GLOBAL_MEMORY and USES_GLOBAL_MEMORY. */
305 : :
306 : : void
307 : 45225457 : determine_global_memory_access (gcall *stmt,
308 : : bool *writes_global_memory,
309 : : bool *reads_global_memory,
310 : : bool *uses_global_memory)
311 : : {
312 : 45225457 : tree callee;
313 : 45225457 : cgraph_node *node;
314 : 45225457 : modref_summary *summary;
315 : :
316 : : /* We need to detrmine reads to set uses. */
317 : 45225457 : gcc_assert (!uses_global_memory || reads_global_memory);
318 : :
319 : 45225457 : if ((callee = gimple_call_fndecl (stmt)) != NULL_TREE
320 : 43033223 : && (node = cgraph_node::get (callee)) != NULL
321 : 88227171 : && (summary = get_modref_function_summary (node)))
322 : : {
323 : 8394017 : if (writes_global_memory && *writes_global_memory)
324 : 5202910 : *writes_global_memory = summary->global_memory_written;
325 : 8394017 : if (reads_global_memory && *reads_global_memory)
326 : 5761939 : *reads_global_memory = summary->global_memory_read;
327 : 8394017 : if (reads_global_memory && uses_global_memory
328 : 2885985 : && !summary->calls_interposable
329 : 10659710 : && !*reads_global_memory && node->binds_to_current_def_p ())
330 : 442282 : *uses_global_memory = false;
331 : : }
332 : 45225457 : if ((writes_global_memory && *writes_global_memory)
333 : 18145521 : || (uses_global_memory && *uses_global_memory)
334 : 2900773 : || (reads_global_memory && *reads_global_memory))
335 : : {
336 : 42855920 : attr_fnspec fnspec = gimple_call_fnspec (stmt);
337 : 42855920 : if (fnspec.known_p ())
338 : : {
339 : 5734715 : if (writes_global_memory
340 : 5734715 : && !fnspec.global_memory_written_p ())
341 : 1463501 : *writes_global_memory = false;
342 : 5734715 : if (reads_global_memory && !fnspec.global_memory_read_p ())
343 : : {
344 : 2197129 : *reads_global_memory = false;
345 : 2197129 : if (uses_global_memory)
346 : 1867653 : *uses_global_memory = false;
347 : : }
348 : : }
349 : : }
350 : 45225457 : }
351 : :
352 : : /* Return true if FNDECL may be part of another lto partition. */
353 : :
354 : : bool
355 : 41220 : fndecl_maybe_in_other_partition (tree fndecl)
356 : : {
357 : 41220 : cgraph_node *fn_node = cgraph_node::get (fndecl);
358 : 41220 : if (fn_node == NULL)
359 : : return true;
360 : :
361 : 41220 : return fn_node->in_other_partition;
362 : : }
363 : :
364 : : /* Return a new variable info structure consisting for a variable
365 : : named NAME, and using constraint graph node NODE. Append it
366 : : to the vector of variable info structures. */
367 : :
368 : : varinfo_t
369 : 222399080 : new_var_info (tree t, const char *name, bool add_id)
370 : : {
371 : 222399080 : unsigned index = varmap.length ();
372 : 222399080 : varinfo_t ret = variable_info_pool.allocate ();
373 : :
374 : 222399080 : if (dump_file && add_id)
375 : : {
376 : 2326 : char *tempname = xasprintf ("%s(%d)", name, index);
377 : 2326 : name = ggc_strdup (tempname);
378 : 2326 : free (tempname);
379 : : }
380 : :
381 : 222399080 : ret->id = index;
382 : 222399080 : ret->name = name;
383 : 222399080 : ret->decl = t;
384 : : /* Vars without decl are artificial and do not have sub-variables. */
385 : 222399080 : ret->is_artificial_var = (t == NULL_TREE);
386 : 222399080 : ret->is_special_var = false;
387 : 222399080 : ret->is_unknown_size_var = false;
388 : 222399080 : ret->is_full_var = (t == NULL_TREE);
389 : 222399080 : ret->is_heap_var = false;
390 : 222399080 : ret->may_have_pointers = true;
391 : 222399080 : ret->only_restrict_pointers = false;
392 : 222399080 : ret->is_restrict_var = false;
393 : 222399080 : ret->ruid = 0;
394 : 222399080 : ret->is_global_var = (t == NULL_TREE);
395 : 222399080 : ret->is_ipa_escape_point = false;
396 : 222399080 : ret->is_fn_info = false;
397 : 222399080 : ret->address_taken = false;
398 : 222399080 : if (t && DECL_P (t))
399 : 42928459 : ret->is_global_var = (is_global_var (t)
400 : : /* We have to treat even local register variables
401 : : as escape points. */
402 : 42928459 : || (VAR_P (t) && DECL_HARD_REGISTER (t)));
403 : 106410208 : ret->is_reg_var = (t && TREE_CODE (t) == SSA_NAME);
404 : 222399080 : ret->solution = BITMAP_ALLOC (&pta_obstack);
405 : 222399080 : ret->oldsolution = NULL;
406 : 222399080 : ret->next = 0;
407 : 222399080 : ret->shadow_var_uid = 0;
408 : 222399080 : ret->head = ret->id;
409 : :
410 : 222399080 : stats.total_vars++;
411 : :
412 : 222399080 : varmap.safe_push (ret);
413 : :
414 : 222399080 : return ret;
415 : : }
416 : :
417 : : /* Print out constraint C to FILE. */
418 : :
419 : : void
420 : 9448 : dump_constraint (FILE *file, constraint_t c)
421 : : {
422 : 9448 : if (c->lhs.type == ADDRESSOF)
423 : 0 : fprintf (file, "&");
424 : 9448 : else if (c->lhs.type == DEREF)
425 : 864 : fprintf (file, "*");
426 : 9448 : if (dump_file)
427 : 9448 : fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
428 : : else
429 : 0 : fprintf (file, "V%d", c->lhs.var);
430 : 9448 : if (c->lhs.offset == UNKNOWN_OFFSET)
431 : 6 : fprintf (file, " + UNKNOWN");
432 : 9442 : else if (c->lhs.offset != 0)
433 : 4 : fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
434 : 9448 : fprintf (file, " = ");
435 : 9448 : if (c->rhs.type == ADDRESSOF)
436 : 3384 : fprintf (file, "&");
437 : 6064 : else if (c->rhs.type == DEREF)
438 : 1206 : fprintf (file, "*");
439 : 9448 : if (dump_file)
440 : 9448 : fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
441 : : else
442 : 0 : fprintf (file, "V%d", c->rhs.var);
443 : 9448 : if (c->rhs.offset == UNKNOWN_OFFSET)
444 : 1570 : fprintf (file, " + UNKNOWN");
445 : 7878 : else if (c->rhs.offset != 0)
446 : 103 : fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
447 : 9448 : }
448 : :
449 : : /* Print out constraint C to stderr. */
450 : :
451 : : DEBUG_FUNCTION void
452 : 0 : debug_constraint (constraint_t c)
453 : : {
454 : 0 : dump_constraint (stderr, c);
455 : 0 : fprintf (stderr, "\n");
456 : 0 : }
457 : :
458 : : /* Print out all constraints to FILE. */
459 : :
460 : : void
461 : 384 : dump_constraints (FILE *file, int from)
462 : : {
463 : 384 : int i;
464 : 384 : constraint_t c;
465 : 9728 : for (i = from; constraints.iterate (i, &c); i++)
466 : 9344 : if (c)
467 : : {
468 : 9344 : dump_constraint (file, c);
469 : 9344 : fprintf (file, "\n");
470 : : }
471 : 384 : }
472 : :
473 : : /* Print out all constraints to stderr. */
474 : :
475 : : DEBUG_FUNCTION void
476 : 0 : debug_constraints (void)
477 : : {
478 : 0 : dump_constraints (stderr, 0);
479 : 0 : }
480 : :
481 : : /* Print out the points-to solution for VAR to FILE. */
482 : :
483 : : void
484 : 5822 : dump_solution_for_var (FILE *file, unsigned int var)
485 : : {
486 : 5822 : varinfo_t vi = get_varinfo (var);
487 : 5822 : unsigned int i;
488 : 5822 : bitmap_iterator bi;
489 : :
490 : : /* Dump the solution for unified vars anyway, this avoids difficulties
491 : : in scanning dumps in the testsuite. */
492 : 5822 : fprintf (file, "%s = { ", vi->name);
493 : 5822 : vi = get_varinfo (var_rep[var]);
494 : 15346 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
495 : 9524 : fprintf (file, "%s ", get_varinfo (i)->name);
496 : 5822 : fprintf (file, "}");
497 : :
498 : : /* But note when the variable was unified. */
499 : 5822 : if (vi->id != var)
500 : 1224 : fprintf (file, " same as %s", vi->name);
501 : :
502 : 5822 : fprintf (file, "\n");
503 : 5822 : }
504 : :
505 : : /* Print the points-to solution for VAR to stderr. */
506 : :
507 : : DEBUG_FUNCTION void
508 : 0 : debug_solution_for_var (unsigned int var)
509 : : {
510 : 0 : dump_solution_for_var (stderr, var);
511 : 0 : }
512 : :
513 : : /* Dump stats information to OUTFILE. */
514 : :
515 : : void
516 : 150 : dump_sa_stats (FILE *outfile)
517 : : {
518 : 150 : fprintf (outfile, "Points-to Stats:\n");
519 : 150 : fprintf (outfile, "Total vars: %d\n", stats.total_vars);
520 : 150 : fprintf (outfile, "Non-pointer vars: %d\n",
521 : : stats.nonpointer_vars);
522 : 150 : fprintf (outfile, "Statically unified vars: %d\n",
523 : : stats.unified_vars_static);
524 : 150 : fprintf (outfile, "Dynamically unified vars: %d\n",
525 : : stats.unified_vars_dynamic);
526 : 150 : fprintf (outfile, "Iterations: %d\n", stats.iterations);
527 : 150 : fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
528 : 150 : fprintf (outfile, "Number of implicit edges: %d\n",
529 : : stats.num_implicit_edges);
530 : 150 : fprintf (outfile, "Number of avoided edges: %d\n",
531 : : stats.num_avoided_edges);
532 : 150 : }
533 : :
534 : : /* Dump points-to information to OUTFILE. */
535 : :
536 : : void
537 : 299 : dump_sa_points_to_info (FILE *outfile)
538 : : {
539 : 299 : fprintf (outfile, "\nPoints-to sets\n\n");
540 : :
541 : 6771 : for (unsigned i = 1; i < varmap.length (); i++)
542 : : {
543 : 6472 : varinfo_t vi = get_varinfo (i);
544 : 6472 : if (!vi->may_have_pointers)
545 : 650 : continue;
546 : 5822 : dump_solution_for_var (outfile, i);
547 : : }
548 : 299 : }
549 : :
550 : :
551 : : /* Debug points-to information to stderr. */
552 : :
553 : : DEBUG_FUNCTION void
554 : 0 : debug_sa_points_to_info (void)
555 : : {
556 : 0 : dump_sa_points_to_info (stderr);
557 : 0 : }
558 : :
559 : : /* Dump varinfo VI to FILE. */
560 : :
561 : : void
562 : 0 : dump_varinfo (FILE *file, varinfo_t vi)
563 : : {
564 : 0 : if (vi == NULL)
565 : : return;
566 : :
567 : 0 : fprintf (file, "%u: %s\n", vi->id, vi->name);
568 : :
569 : 0 : const char *sep = " ";
570 : 0 : if (vi->is_artificial_var)
571 : 0 : fprintf (file, "%sartificial", sep);
572 : 0 : if (vi->is_special_var)
573 : 0 : fprintf (file, "%sspecial", sep);
574 : 0 : if (vi->is_unknown_size_var)
575 : 0 : fprintf (file, "%sunknown-size", sep);
576 : 0 : if (vi->is_full_var)
577 : 0 : fprintf (file, "%sfull", sep);
578 : 0 : if (vi->is_heap_var)
579 : 0 : fprintf (file, "%sheap", sep);
580 : 0 : if (vi->may_have_pointers)
581 : 0 : fprintf (file, "%smay-have-pointers", sep);
582 : 0 : if (vi->only_restrict_pointers)
583 : 0 : fprintf (file, "%sonly-restrict-pointers", sep);
584 : 0 : if (vi->is_restrict_var)
585 : 0 : fprintf (file, "%sis-restrict-var", sep);
586 : 0 : if (vi->is_global_var)
587 : 0 : fprintf (file, "%sglobal", sep);
588 : 0 : if (vi->is_ipa_escape_point)
589 : 0 : fprintf (file, "%sipa-escape-point", sep);
590 : 0 : if (vi->is_fn_info)
591 : 0 : fprintf (file, "%sfn-info", sep);
592 : 0 : if (vi->ruid)
593 : 0 : fprintf (file, "%srestrict-uid:%u", sep, vi->ruid);
594 : 0 : if (vi->next)
595 : 0 : fprintf (file, "%snext:%u", sep, vi->next);
596 : 0 : if (vi->head != vi->id)
597 : 0 : fprintf (file, "%shead:%u", sep, vi->head);
598 : 0 : if (vi->offset)
599 : 0 : fprintf (file, "%soffset:" HOST_WIDE_INT_PRINT_DEC, sep, vi->offset);
600 : 0 : if (vi->size != ~HOST_WIDE_INT_0U)
601 : 0 : fprintf (file, "%ssize:" HOST_WIDE_INT_PRINT_DEC, sep, vi->size);
602 : 0 : if (vi->fullsize != ~HOST_WIDE_INT_0U && vi->fullsize != vi->size)
603 : 0 : fprintf (file, "%sfullsize:" HOST_WIDE_INT_PRINT_DEC, sep,
604 : : vi->fullsize);
605 : 0 : fprintf (file, "\n");
606 : :
607 : 0 : if (vi->solution && !bitmap_empty_p (vi->solution))
608 : : {
609 : 0 : bitmap_iterator bi;
610 : 0 : unsigned i;
611 : 0 : fprintf (file, " solution: {");
612 : 0 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
613 : 0 : fprintf (file, " %u", i);
614 : 0 : fprintf (file, " }\n");
615 : : }
616 : :
617 : 0 : if (vi->oldsolution && !bitmap_empty_p (vi->oldsolution)
618 : 0 : && !bitmap_equal_p (vi->solution, vi->oldsolution))
619 : : {
620 : 0 : bitmap_iterator bi;
621 : 0 : unsigned i;
622 : 0 : fprintf (file, " oldsolution: {");
623 : 0 : EXECUTE_IF_SET_IN_BITMAP (vi->oldsolution, 0, i, bi)
624 : 0 : fprintf (file, " %u", i);
625 : 0 : fprintf (file, " }\n");
626 : : }
627 : : }
628 : :
629 : : /* Dump varinfo VI to stderr. */
630 : :
631 : : DEBUG_FUNCTION void
632 : 0 : debug_varinfo (varinfo_t vi)
633 : : {
634 : 0 : dump_varinfo (stderr, vi);
635 : 0 : }
636 : :
637 : : /* Dump varmap to FILE. */
638 : :
639 : : void
640 : 0 : dump_varmap (FILE *file)
641 : : {
642 : 0 : if (varmap.length () == 0)
643 : : return;
644 : :
645 : 0 : fprintf (file, "variables:\n");
646 : :
647 : 0 : for (unsigned int i = 0; i < varmap.length (); ++i)
648 : : {
649 : 0 : varinfo_t vi = get_varinfo (i);
650 : 0 : dump_varinfo (file, vi);
651 : : }
652 : :
653 : 0 : fprintf (file, "\n");
654 : : }
655 : :
656 : : /* Dump varmap to stderr. */
657 : :
658 : : DEBUG_FUNCTION void
659 : 0 : debug_varmap (void)
660 : : {
661 : 0 : dump_varmap (stderr);
662 : 0 : }
663 : :
664 : : } // namespace pointer_analysis
665 : :
666 : :
667 : : /* Structure used to put solution bitmaps in a hashtable so they can
668 : : be shared among variables with the same points-to set. */
669 : :
670 : : typedef struct shared_bitmap_info
671 : : {
672 : : bitmap pt_vars;
673 : : hashval_t hashcode;
674 : : } *shared_bitmap_info_t;
675 : : typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
676 : :
677 : : /* Shared_bitmap hashtable helpers. */
678 : :
679 : : struct shared_bitmap_hasher : free_ptr_hash <shared_bitmap_info>
680 : : {
681 : : static inline hashval_t hash (const shared_bitmap_info *);
682 : : static inline bool equal (const shared_bitmap_info *,
683 : : const shared_bitmap_info *);
684 : : };
685 : :
686 : : /* Hash function for a shared_bitmap_info_t. */
687 : :
688 : : inline hashval_t
689 : 4572771 : shared_bitmap_hasher::hash (const shared_bitmap_info *bi)
690 : : {
691 : 4572771 : return bi->hashcode;
692 : : }
693 : :
694 : : /* Equality function for two shared_bitmap_info_t's. */
695 : :
696 : : inline bool
697 : 42246946 : shared_bitmap_hasher::equal (const shared_bitmap_info *sbi1,
698 : : const shared_bitmap_info *sbi2)
699 : : {
700 : 42246946 : return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
701 : : }
702 : :
703 : : /* Shared_bitmap hashtable. */
704 : :
705 : : static hash_table<shared_bitmap_hasher> *shared_bitmap_table;
706 : :
707 : : /* Lookup a bitmap in the shared bitmap hashtable, and return an already
708 : : existing instance if there is one, NULL otherwise. */
709 : :
710 : : static bitmap
711 : 46195949 : shared_bitmap_lookup (bitmap pt_vars)
712 : : {
713 : 46195949 : shared_bitmap_info **slot;
714 : 46195949 : struct shared_bitmap_info sbi;
715 : :
716 : 46195949 : sbi.pt_vars = pt_vars;
717 : 46195949 : sbi.hashcode = bitmap_hash (pt_vars);
718 : :
719 : 46195949 : slot = shared_bitmap_table->find_slot (&sbi, NO_INSERT);
720 : 46195949 : if (!slot)
721 : : return NULL;
722 : : else
723 : 37409030 : return (*slot)->pt_vars;
724 : : }
725 : :
726 : : /* Add a bitmap to the shared bitmap hashtable. */
727 : :
728 : : static void
729 : 8786919 : shared_bitmap_add (bitmap pt_vars)
730 : : {
731 : 8786919 : shared_bitmap_info **slot;
732 : 8786919 : shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
733 : :
734 : 8786919 : sbi->pt_vars = pt_vars;
735 : 8786919 : sbi->hashcode = bitmap_hash (pt_vars);
736 : :
737 : 8786919 : slot = shared_bitmap_table->find_slot (sbi, INSERT);
738 : 8786919 : gcc_assert (!*slot);
739 : 8786919 : *slot = sbi;
740 : 8786919 : }
741 : :
742 : : /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
743 : :
744 : : static void
745 : 46195949 : set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt,
746 : : tree fndecl)
747 : : {
748 : 46195949 : unsigned int i;
749 : 46195949 : bitmap_iterator bi;
750 : 46195949 : varinfo_t escaped_vi = get_varinfo (var_rep[escaped_id]);
751 : 46195949 : varinfo_t escaped_return_vi = get_varinfo (var_rep[escaped_return_id]);
752 : 46195949 : bool everything_escaped
753 : 46195949 : = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id);
754 : :
755 : 267841714 : EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
756 : : {
757 : 221645765 : varinfo_t vi = get_varinfo (i);
758 : :
759 : 221645765 : if (vi->is_artificial_var)
760 : 82862691 : continue;
761 : :
762 : 138783074 : if (everything_escaped
763 : 138783074 : || (escaped_vi->solution
764 : 138188073 : && bitmap_bit_p (escaped_vi->solution, i)))
765 : : {
766 : 120235078 : pt->vars_contains_escaped = true;
767 : 120235078 : pt->vars_contains_escaped_heap |= vi->is_heap_var;
768 : : }
769 : 138783074 : if (escaped_return_vi->solution
770 : 138783074 : && bitmap_bit_p (escaped_return_vi->solution, i))
771 : 16810737 : pt->vars_contains_escaped_heap |= vi->is_heap_var;
772 : :
773 : 138783074 : if (vi->is_restrict_var)
774 : 1724460 : pt->vars_contains_restrict = true;
775 : :
776 : 138783074 : if (VAR_P (vi->decl)
777 : 2475439 : || TREE_CODE (vi->decl) == PARM_DECL
778 : 1956258 : || TREE_CODE (vi->decl) == RESULT_DECL)
779 : : {
780 : : /* If we are in IPA mode we will not recompute points-to
781 : : sets after inlining so make sure they stay valid. */
782 : 136839207 : if (in_ipa_mode
783 : 136839207 : && !DECL_PT_UID_SET_P (vi->decl))
784 : 33289 : SET_DECL_PT_UID (vi->decl, DECL_UID (vi->decl));
785 : :
786 : : /* Add the decl to the points-to set. Note that the points-to
787 : : set contains global variables. */
788 : 136839207 : bitmap_set_bit (into, DECL_PT_UID (vi->decl));
789 : 136839207 : if (vi->is_global_var
790 : : /* In IPA mode the escaped_heap trick doesn't work as
791 : : ESCAPED is escaped from the unit but
792 : : pt_solution_includes_global needs to answer true for
793 : : all variables not automatic within a function.
794 : : For the same reason is_global_var is not the
795 : : correct flag to track - local variables from other
796 : : functions also need to be considered global.
797 : : Conveniently all HEAP vars are not put in function
798 : : scope. */
799 : 136839207 : || (in_ipa_mode
800 : 272530 : && fndecl
801 : 247498 : && ! auto_var_in_fn_p (vi->decl, fndecl)))
802 : 77369692 : pt->vars_contains_nonlocal = true;
803 : :
804 : : /* If we have a variable that is interposable record that fact
805 : : for pointer comparison simplification. */
806 : 136839207 : if (VAR_P (vi->decl)
807 : 136307635 : && (TREE_STATIC (vi->decl) || DECL_EXTERNAL (vi->decl))
808 : 214064187 : && ! decl_binds_to_current_def_p (vi->decl))
809 : 55067620 : pt->vars_contains_interposable = true;
810 : :
811 : : /* If this is a local variable we can have overlapping lifetime
812 : : of different function invocations through recursion duplicate
813 : : it with its shadow variable. */
814 : 136839207 : if (in_ipa_mode
815 : 331467 : && vi->shadow_var_uid != 0)
816 : : {
817 : 204192 : bitmap_set_bit (into, vi->shadow_var_uid);
818 : 204192 : pt->vars_contains_nonlocal = true;
819 : : }
820 : : }
821 : :
822 : 1943867 : else if (TREE_CODE (vi->decl) == FUNCTION_DECL
823 : 1943867 : || TREE_CODE (vi->decl) == LABEL_DECL)
824 : : {
825 : : /* Nothing should read/write from/to code so we can
826 : : save bits by not including them in the points-to bitmaps.
827 : : Still mark the points-to set as containing global memory
828 : : to make code-patching possible - see PR70128. */
829 : 1789437 : pt->vars_contains_nonlocal = true;
830 : : }
831 : : }
832 : 46195949 : }
833 : :
834 : :
835 : : /* Compute the points-to solution *PT for the variable VI. */
836 : :
837 : : static struct pt_solution
838 : 60884521 : find_what_var_points_to (tree fndecl, varinfo_t orig_vi)
839 : : {
840 : 60884521 : unsigned int i;
841 : 60884521 : bitmap_iterator bi;
842 : 60884521 : bitmap finished_solution;
843 : 60884521 : bitmap result;
844 : 60884521 : varinfo_t vi;
845 : 60884521 : struct pt_solution *pt;
846 : :
847 : : /* This variable may have been collapsed, let's get the real
848 : : variable. */
849 : 60884521 : vi = get_varinfo (var_rep[orig_vi->id]);
850 : :
851 : : /* See if we have already computed the solution and return it. */
852 : 60884521 : pt_solution **slot = &final_solutions->get_or_insert (vi);
853 : 60884521 : if (*slot != NULL)
854 : 14065703 : return **slot;
855 : :
856 : 46818818 : *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
857 : 46818818 : memset (pt, 0, sizeof (struct pt_solution));
858 : :
859 : : /* Translate artificial variables into SSA_NAME_PTR_INFO
860 : : attributes. */
861 : 273960260 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
862 : : {
863 : 227141442 : varinfo_t vi = get_varinfo (i);
864 : :
865 : 227141442 : if (vi->is_artificial_var)
866 : : {
867 : 84952847 : if (vi->id == nothing_id)
868 : 10116665 : pt->null = 1;
869 : : else if (vi->id == escaped_id)
870 : : {
871 : 32310095 : if (in_ipa_mode)
872 : 133900 : pt->ipa_escaped = 1;
873 : : else
874 : 32176195 : pt->escaped = 1;
875 : : /* Expand some special vars of ESCAPED in-place here. */
876 : 32310095 : varinfo_t evi = get_varinfo (var_rep[escaped_id]);
877 : 32310095 : if (bitmap_bit_p (evi->solution, nonlocal_id))
878 : 30039394 : pt->nonlocal = 1;
879 : : }
880 : : else if (vi->id == nonlocal_id)
881 : 35948495 : pt->nonlocal = 1;
882 : : else if (vi->id == string_id)
883 : 5953732 : pt->const_pool = 1;
884 : : else if (vi->id == anything_id
885 : : || vi->id == integer_id)
886 : 622884 : pt->anything = 1;
887 : : }
888 : : }
889 : :
890 : : /* Instead of doing extra work, simply do not create
891 : : elaborate points-to information for pt_anything pointers. */
892 : 46818818 : if (pt->anything)
893 : 622869 : return *pt;
894 : :
895 : : /* Share the final set of variables when possible. */
896 : 46195949 : finished_solution = BITMAP_GGC_ALLOC ();
897 : 46195949 : stats.points_to_sets_created++;
898 : :
899 : 46195949 : set_uids_in_ptset (finished_solution, vi->solution, pt, fndecl);
900 : 46195949 : result = shared_bitmap_lookup (finished_solution);
901 : 46195949 : if (!result)
902 : : {
903 : 8786919 : shared_bitmap_add (finished_solution);
904 : 8786919 : pt->vars = finished_solution;
905 : : }
906 : : else
907 : : {
908 : 37409030 : pt->vars = result;
909 : 37409030 : bitmap_clear (finished_solution);
910 : : }
911 : :
912 : 46195949 : return *pt;
913 : : }
914 : :
915 : : /* Given a pointer variable P, fill in its points-to set. */
916 : :
917 : : static void
918 : 24446184 : find_what_p_points_to (tree fndecl, tree p)
919 : : {
920 : 24446184 : struct ptr_info_def *pi;
921 : 24446184 : tree lookup_p = p;
922 : 24446184 : varinfo_t vi;
923 : 24446184 : prange vr;
924 : 48892368 : get_range_query (DECL_STRUCT_FUNCTION (fndecl))->range_of_expr (vr, p);
925 : 24446184 : bool nonnull = vr.nonzero_p ();
926 : :
927 : : /* For parameters, get at the points-to set for the actual parm
928 : : decl. */
929 : 24446184 : if (TREE_CODE (p) == SSA_NAME
930 : 24446184 : && SSA_NAME_IS_DEFAULT_DEF (p)
931 : 29584391 : && (TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
932 : 943511 : || TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL))
933 : 4252714 : lookup_p = SSA_NAME_VAR (p);
934 : :
935 : 24446184 : vi = lookup_vi_for_tree (lookup_p);
936 : 24446184 : if (!vi)
937 : 1031447 : return;
938 : :
939 : 23414737 : pi = get_ptr_info (p);
940 : 23414737 : pi->pt = find_what_var_points_to (fndecl, vi);
941 : : /* Conservatively set to NULL from PTA (to true). */
942 : 23414737 : pi->pt.null = 1;
943 : : /* Preserve pointer nonnull globally computed. */
944 : 23414737 : if (nonnull)
945 : 3656777 : set_ptr_nonnull (p);
946 : 24446184 : }
947 : :
948 : :
949 : : /* Query statistics for points-to solutions. */
950 : :
951 : : static struct {
952 : : unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
953 : : unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
954 : : unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
955 : : unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
956 : : } pta_stats;
957 : :
958 : : void
959 : 0 : dump_pta_stats (FILE *s)
960 : : {
961 : 0 : fprintf (s, "\nPTA query stats:\n");
962 : 0 : fprintf (s, " pt_solution_includes: "
963 : : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
964 : : HOST_WIDE_INT_PRINT_DEC" queries\n",
965 : : pta_stats.pt_solution_includes_no_alias,
966 : 0 : pta_stats.pt_solution_includes_no_alias
967 : 0 : + pta_stats.pt_solution_includes_may_alias);
968 : 0 : fprintf (s, " pt_solutions_intersect: "
969 : : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
970 : : HOST_WIDE_INT_PRINT_DEC" queries\n",
971 : : pta_stats.pt_solutions_intersect_no_alias,
972 : 0 : pta_stats.pt_solutions_intersect_no_alias
973 : 0 : + pta_stats.pt_solutions_intersect_may_alias);
974 : 0 : }
975 : :
976 : :
977 : : /* Reset the points-to solution *PT to a conservative default
978 : : (point to anything). */
979 : :
980 : : void
981 : 66850486 : pt_solution_reset (struct pt_solution *pt)
982 : : {
983 : 66850486 : memset (pt, 0, sizeof (struct pt_solution));
984 : 66850486 : pt->anything = true;
985 : 66850486 : pt->null = true;
986 : 66850486 : }
987 : :
988 : : /* Set the points-to solution *PT to point only to the variables
989 : : in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
990 : : global variables and VARS_CONTAINS_RESTRICT specifies whether
991 : : it contains restrict tag variables. */
992 : :
993 : : void
994 : 70742 : pt_solution_set (struct pt_solution *pt, bitmap vars,
995 : : bool vars_contains_nonlocal)
996 : : {
997 : 70742 : memset (pt, 0, sizeof (struct pt_solution));
998 : 70742 : pt->vars = vars;
999 : 70742 : pt->vars_contains_nonlocal = vars_contains_nonlocal;
1000 : 70742 : pt->vars_contains_escaped
1001 : 141484 : = (cfun->gimple_df->escaped.anything
1002 : 70742 : || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars));
1003 : 70742 : }
1004 : :
1005 : : /* Set the points-to solution *PT to point only to the variable VAR. */
1006 : :
1007 : : void
1008 : 69012 : pt_solution_set_var (struct pt_solution *pt, tree var)
1009 : : {
1010 : 69012 : memset (pt, 0, sizeof (struct pt_solution));
1011 : 69012 : pt->vars = BITMAP_GGC_ALLOC ();
1012 : 69012 : bitmap_set_bit (pt->vars, DECL_PT_UID (var));
1013 : 69012 : pt->vars_contains_nonlocal = is_global_var (var);
1014 : 69012 : pt->vars_contains_escaped
1015 : 138024 : = (cfun->gimple_df->escaped.anything
1016 : 69012 : || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var)));
1017 : 69012 : }
1018 : :
1019 : : /* Computes the union of the points-to solutions *DEST and *SRC and
1020 : : stores the result in *DEST. This changes the points-to bitmap
1021 : : of *DEST and thus may not be used if that might be shared.
1022 : : The points-to bitmap of *SRC and *DEST will not be shared after
1023 : : this function if they were not before. */
1024 : :
1025 : : static void
1026 : 34 : pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src)
1027 : : {
1028 : 34 : dest->anything |= src->anything;
1029 : 34 : if (dest->anything)
1030 : : {
1031 : 0 : pt_solution_reset (dest);
1032 : 0 : return;
1033 : : }
1034 : :
1035 : 34 : dest->nonlocal |= src->nonlocal;
1036 : 34 : dest->escaped |= src->escaped;
1037 : 34 : dest->ipa_escaped |= src->ipa_escaped;
1038 : 34 : dest->null |= src->null;
1039 : 34 : dest->const_pool |= src->const_pool ;
1040 : 34 : dest->vars_contains_nonlocal |= src->vars_contains_nonlocal;
1041 : 34 : dest->vars_contains_escaped |= src->vars_contains_escaped;
1042 : 34 : dest->vars_contains_escaped_heap |= src->vars_contains_escaped_heap;
1043 : 34 : if (!src->vars)
1044 : : return;
1045 : :
1046 : 34 : if (!dest->vars)
1047 : 20 : dest->vars = BITMAP_GGC_ALLOC ();
1048 : 34 : bitmap_ior_into (dest->vars, src->vars);
1049 : : }
1050 : :
1051 : : /* Return true if the points-to solution *PT is empty. */
1052 : :
1053 : : bool
1054 : 11755 : pt_solution_empty_p (const pt_solution *pt)
1055 : : {
1056 : 11755 : if (pt->anything
1057 : 8315 : || pt->nonlocal)
1058 : : return false;
1059 : :
1060 : 264 : if (pt->vars
1061 : 264 : && !bitmap_empty_p (pt->vars))
1062 : : return false;
1063 : :
1064 : : /* If the solution includes ESCAPED, check if that is empty. */
1065 : 262 : if (pt->escaped
1066 : 262 : && !pt_solution_empty_p (&cfun->gimple_df->escaped))
1067 : : return false;
1068 : :
1069 : : /* If the solution includes ESCAPED, check if that is empty. */
1070 : 262 : if (pt->ipa_escaped
1071 : 262 : && !pt_solution_empty_p (&ipa_escaped_pt))
1072 : : return false;
1073 : :
1074 : : return true;
1075 : : }
1076 : :
1077 : : /* Return true if the points-to solution *PT only point to a single var, and
1078 : : return the var uid in *UID. */
1079 : :
1080 : : bool
1081 : 835772 : pt_solution_singleton_or_null_p (struct pt_solution *pt, unsigned *uid)
1082 : : {
1083 : 830713 : if (pt->anything || pt->nonlocal || pt->escaped || pt->ipa_escaped
1084 : 186258 : || pt->vars == NULL
1085 : 1022030 : || !bitmap_single_bit_set_p (pt->vars))
1086 : 655777 : return false;
1087 : :
1088 : 179995 : *uid = bitmap_first_set_bit (pt->vars);
1089 : 179995 : return true;
1090 : : }
1091 : :
1092 : : /* Return true if the points-to solution *PT includes global memory.
1093 : : If ESCAPED_LOCAL_P is true then escaped local variables are also
1094 : : considered global. */
1095 : :
1096 : : bool
1097 : 46372190 : pt_solution_includes_global (struct pt_solution *pt, bool escaped_local_p)
1098 : : {
1099 : 46372190 : if (pt->anything
1100 : 45526945 : || pt->nonlocal
1101 : 11029753 : || pt->vars_contains_nonlocal
1102 : : /* The following is a hack to make the malloc escape hack work.
1103 : : In reality we'd need different sets for escaped-through-return
1104 : : and escaped-to-callees and passes would need to be updated. */
1105 : 4109798 : || pt->vars_contains_escaped_heap)
1106 : : return true;
1107 : :
1108 : 2235124 : if (escaped_local_p && pt->vars_contains_escaped)
1109 : : return true;
1110 : :
1111 : : /* 'escaped' is also a placeholder so we have to look into it. */
1112 : 2234189 : if (pt->escaped)
1113 : 92 : return pt_solution_includes_global (&cfun->gimple_df->escaped,
1114 : 92 : escaped_local_p);
1115 : :
1116 : 2234097 : if (pt->ipa_escaped)
1117 : 24394 : return pt_solution_includes_global (&ipa_escaped_pt,
1118 : 24394 : escaped_local_p);
1119 : :
1120 : : return false;
1121 : : }
1122 : :
1123 : : /* Return true if the points-to solution *PT includes the variable
1124 : : declaration DECL. */
1125 : :
1126 : : static bool
1127 : 260476969 : pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
1128 : : {
1129 : 260476969 : if (pt->anything)
1130 : : return true;
1131 : :
1132 : 253584593 : if (pt->nonlocal
1133 : 253584593 : && is_global_var (decl))
1134 : : return true;
1135 : :
1136 : 234772987 : if (pt->vars
1137 : 234772987 : && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
1138 : : return true;
1139 : :
1140 : : /* If the solution includes ESCAPED, check it. */
1141 : 183419718 : if (pt->escaped
1142 : 183419718 : && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
1143 : : return true;
1144 : :
1145 : : /* If the solution includes ESCAPED, check it. */
1146 : 157572089 : if (pt->ipa_escaped
1147 : 157572089 : && pt_solution_includes_1 (&ipa_escaped_pt, decl))
1148 : : return true;
1149 : :
1150 : : return false;
1151 : : }
1152 : :
1153 : : bool
1154 : 174083594 : pt_solution_includes (struct pt_solution *pt, const_tree decl)
1155 : : {
1156 : 174083594 : bool res = pt_solution_includes_1 (pt, decl);
1157 : 174083594 : if (res)
1158 : 77057251 : ++pta_stats.pt_solution_includes_may_alias;
1159 : : else
1160 : 97026343 : ++pta_stats.pt_solution_includes_no_alias;
1161 : 174083594 : return res;
1162 : : }
1163 : :
1164 : : /* Return true if the points-to solution *PT contains a reference to a
1165 : : constant pool entry. */
1166 : :
1167 : : bool
1168 : 6861582 : pt_solution_includes_const_pool (struct pt_solution *pt)
1169 : : {
1170 : 6861582 : return (pt->const_pool
1171 : 6722792 : || pt->nonlocal
1172 : 446279 : || (pt->escaped && (!cfun || cfun->gimple_df->escaped.const_pool))
1173 : 7307861 : || (pt->ipa_escaped && ipa_escaped_pt.const_pool));
1174 : : }
1175 : :
1176 : : /* Return true if both points-to solutions PT1 and PT2 have a non-empty
1177 : : intersection. */
1178 : :
1179 : : static bool
1180 : 81561517 : pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
1181 : : {
1182 : 81561517 : if (pt1->anything || pt2->anything)
1183 : : return true;
1184 : :
1185 : : /* If either points to unknown global memory and the other points to
1186 : : any global memory they alias. */
1187 : 79070770 : if ((pt1->nonlocal
1188 : 55366989 : && (pt2->nonlocal
1189 : 12302934 : || pt2->vars_contains_nonlocal))
1190 : 34352936 : || (pt2->nonlocal
1191 : 9024624 : && pt1->vars_contains_nonlocal))
1192 : : return true;
1193 : :
1194 : : /* If either points to all escaped memory and the other points to
1195 : : any escaped memory they alias. */
1196 : 33980706 : if ((pt1->escaped
1197 : 7503368 : && (pt2->escaped
1198 : 7503368 : || pt2->vars_contains_escaped))
1199 : 30859833 : || (pt2->escaped
1200 : 7092767 : && pt1->vars_contains_escaped))
1201 : : return true;
1202 : :
1203 : : /* Check the escaped solution if required.
1204 : : ??? Do we need to check the local against the IPA escaped sets? */
1205 : 29013578 : if ((pt1->ipa_escaped || pt2->ipa_escaped)
1206 : 29024313 : && !pt_solution_empty_p (&ipa_escaped_pt))
1207 : : {
1208 : : /* If both point to escaped memory and that solution
1209 : : is not empty they alias. */
1210 : 10727 : if (pt1->ipa_escaped && pt2->ipa_escaped)
1211 : : return true;
1212 : :
1213 : : /* If either points to escaped memory see if the escaped solution
1214 : : intersects with the other. */
1215 : 10727 : if ((pt1->ipa_escaped
1216 : 1237 : && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
1217 : 10935 : || (pt2->ipa_escaped
1218 : 9490 : && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
1219 : 10147 : return true;
1220 : : }
1221 : :
1222 : : /* Now both pointers alias if their points-to solution intersects. */
1223 : 29004676 : return (pt1->vars
1224 : 29004660 : && pt2->vars
1225 : 58009336 : && bitmap_intersect_p (pt1->vars, pt2->vars));
1226 : : }
1227 : :
1228 : : bool
1229 : 81550790 : pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
1230 : : {
1231 : 81550790 : bool res = pt_solutions_intersect_1 (pt1, pt2);
1232 : 81550790 : if (res)
1233 : 56055810 : ++pta_stats.pt_solutions_intersect_may_alias;
1234 : : else
1235 : 25494980 : ++pta_stats.pt_solutions_intersect_no_alias;
1236 : 81550790 : return res;
1237 : : }
1238 : :
1239 : :
1240 : : /* Initialize things necessary to perform PTA. */
1241 : :
1242 : : static void
1243 : 4459820 : init_alias_vars (void)
1244 : : {
1245 : 4459820 : use_field_sensitive = (param_max_fields_for_field_sensitive > 1);
1246 : :
1247 : 4459820 : bitmap_obstack_initialize (&pta_obstack);
1248 : 4459820 : bitmap_obstack_initialize (&oldpta_obstack);
1249 : :
1250 : 4459820 : constraints.create (8);
1251 : 4459820 : varmap.create (8);
1252 : :
1253 : 4459820 : memset (&stats, 0, sizeof (stats));
1254 : 4459820 : shared_bitmap_table = new hash_table<shared_bitmap_hasher> (511);
1255 : :
1256 : 4459820 : final_solutions = new hash_map<varinfo_t, pt_solution *>;
1257 : 4459820 : gcc_obstack_init (&final_solutions_obstack);
1258 : :
1259 : 4459820 : init_constraint_builder ();
1260 : 4459820 : }
1261 : :
1262 : : /* Create points-to sets for the current function. See the comments
1263 : : at the start of the file for an algorithmic overview. */
1264 : :
1265 : : static void
1266 : 4455410 : compute_points_to_sets (void)
1267 : : {
1268 : 4455410 : basic_block bb;
1269 : 4455410 : varinfo_t vi;
1270 : :
1271 : 4455410 : timevar_push (TV_TREE_PTA);
1272 : :
1273 : 4455410 : init_alias_vars ();
1274 : :
1275 : 4455410 : intra_build_constraints ();
1276 : :
1277 : : /* From the constraints compute the points-to sets. */
1278 : 4455410 : solve_constraints ();
1279 : :
1280 : 4455410 : if (dump_file && (dump_flags & TDF_STATS))
1281 : 150 : dump_sa_stats (dump_file);
1282 : :
1283 : 4455410 : if (dump_file && (dump_flags & TDF_DETAILS))
1284 : 282 : dump_sa_points_to_info (dump_file);
1285 : :
1286 : : /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
1287 : 4455410 : cfun->gimple_df->escaped = find_what_var_points_to (cfun->decl,
1288 : : get_varinfo (escaped_id));
1289 : :
1290 : : /* Make sure the ESCAPED solution (which is used as placeholder in
1291 : : other solutions) does not reference itself. This simplifies
1292 : : points-to solution queries. */
1293 : 4455410 : cfun->gimple_df->escaped.escaped = 0;
1294 : :
1295 : : /* The ESCAPED_RETURN solution is what contains all memory that needs
1296 : : to be considered global. */
1297 : 4455410 : cfun->gimple_df->escaped_return
1298 : 4455410 : = find_what_var_points_to (cfun->decl, get_varinfo (escaped_return_id));
1299 : 4455410 : cfun->gimple_df->escaped_return.escaped = 1;
1300 : :
1301 : : /* Compute the points-to sets for pointer SSA_NAMEs. */
1302 : 4455410 : unsigned i;
1303 : 4455410 : tree ptr;
1304 : :
1305 : 163170202 : FOR_EACH_SSA_NAME (i, ptr, cfun)
1306 : : {
1307 : 125189668 : if (POINTER_TYPE_P (TREE_TYPE (ptr)))
1308 : 24339204 : find_what_p_points_to (cfun->decl, ptr);
1309 : : }
1310 : :
1311 : : /* Compute the call-used/clobbered sets. */
1312 : 39847851 : FOR_EACH_BB_FN (bb, cfun)
1313 : : {
1314 : 35392441 : gimple_stmt_iterator gsi;
1315 : :
1316 : 319581151 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1317 : : {
1318 : 248796269 : gcall *stmt;
1319 : 248796269 : struct pt_solution *pt;
1320 : :
1321 : 248796269 : stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
1322 : 248796269 : if (!stmt)
1323 : 231314481 : continue;
1324 : :
1325 : 17481788 : pt = gimple_call_use_set (stmt);
1326 : 17481788 : if (gimple_call_flags (stmt) & ECF_CONST)
1327 : 1794758 : memset (pt, 0, sizeof (struct pt_solution));
1328 : : else
1329 : : {
1330 : 15687030 : bool uses_global_memory = true;
1331 : 15687030 : bool reads_global_memory = true;
1332 : :
1333 : 15687030 : determine_global_memory_access (stmt, NULL,
1334 : : &reads_global_memory,
1335 : : &uses_global_memory);
1336 : 15687030 : if ((vi = lookup_call_use_vi (stmt)) != NULL)
1337 : : {
1338 : 14814001 : *pt = find_what_var_points_to (cfun->decl, vi);
1339 : : /* Escaped (and thus nonlocal) variables are always
1340 : : implicitly used by calls. */
1341 : : /* ??? ESCAPED can be empty even though NONLOCAL
1342 : : always escaped. */
1343 : 14814001 : if (uses_global_memory)
1344 : : {
1345 : 13375258 : pt->nonlocal = 1;
1346 : 13375258 : pt->escaped = 1;
1347 : : }
1348 : : }
1349 : 873029 : else if (uses_global_memory)
1350 : : {
1351 : : /* If there is nothing special about this call then
1352 : : we have made everything that is used also escape. */
1353 : 1837 : *pt = cfun->gimple_df->escaped;
1354 : 1837 : pt->nonlocal = 1;
1355 : : }
1356 : : else
1357 : 871192 : memset (pt, 0, sizeof (struct pt_solution));
1358 : : }
1359 : :
1360 : 17481788 : pt = gimple_call_clobber_set (stmt);
1361 : 17481788 : if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
1362 : 3029579 : memset (pt, 0, sizeof (struct pt_solution));
1363 : : else
1364 : : {
1365 : 14452209 : bool writes_global_memory = true;
1366 : :
1367 : 14452209 : determine_global_memory_access (stmt, &writes_global_memory,
1368 : : NULL, NULL);
1369 : :
1370 : 14452209 : if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
1371 : : {
1372 : 13596224 : *pt = find_what_var_points_to (cfun->decl, vi);
1373 : : /* Escaped (and thus nonlocal) variables are always
1374 : : implicitly clobbered by calls. */
1375 : : /* ??? ESCAPED can be empty even though NONLOCAL
1376 : : always escaped. */
1377 : 13596224 : if (writes_global_memory)
1378 : : {
1379 : 12815272 : pt->nonlocal = 1;
1380 : 12815272 : pt->escaped = 1;
1381 : : }
1382 : : }
1383 : 855985 : else if (writes_global_memory)
1384 : : {
1385 : : /* If there is nothing special about this call then
1386 : : we have made everything that is used also escape. */
1387 : 488 : *pt = cfun->gimple_df->escaped;
1388 : 488 : pt->nonlocal = 1;
1389 : : }
1390 : : else
1391 : 855497 : memset (pt, 0, sizeof (struct pt_solution));
1392 : : }
1393 : : }
1394 : : }
1395 : :
1396 : 4455410 : timevar_pop (TV_TREE_PTA);
1397 : 4455410 : }
1398 : :
1399 : : /* Delete created points-to sets. */
1400 : :
1401 : : static void
1402 : 4459820 : delete_points_to_sets (void)
1403 : : {
1404 : 4459820 : delete shared_bitmap_table;
1405 : 4459820 : shared_bitmap_table = NULL;
1406 : 4459820 : if (dump_file && (dump_flags & TDF_STATS))
1407 : 150 : fprintf (dump_file, "Points to sets created:%d\n",
1408 : : stats.points_to_sets_created);
1409 : :
1410 : 4459820 : bitmap_obstack_release (&pta_obstack);
1411 : 4459820 : constraints.release ();
1412 : :
1413 : 4459820 : free (var_rep);
1414 : :
1415 : 4459820 : varmap.release ();
1416 : 4459820 : variable_info_pool.release ();
1417 : :
1418 : 8919640 : delete final_solutions;
1419 : 4459820 : obstack_free (&final_solutions_obstack, NULL);
1420 : :
1421 : 4459820 : delete_constraint_builder ();
1422 : 4459820 : }
1423 : :
1424 : :
1425 : : struct vls_data
1426 : : {
1427 : : unsigned short clique;
1428 : : bool escaped_p;
1429 : : bitmap rvars;
1430 : : };
1431 : :
1432 : : /* Mark "other" loads and stores as belonging to CLIQUE and with
1433 : : base zero. */
1434 : :
1435 : : static bool
1436 : 3933092 : visit_loadstore (gimple *, tree base, tree ref, void *data)
1437 : : {
1438 : 3933092 : unsigned short clique = ((vls_data *) data)->clique;
1439 : 3933092 : bitmap rvars = ((vls_data *) data)->rvars;
1440 : 3933092 : bool escaped_p = ((vls_data *) data)->escaped_p;
1441 : 3933092 : if (TREE_CODE (base) == MEM_REF
1442 : 3933092 : || TREE_CODE (base) == TARGET_MEM_REF)
1443 : : {
1444 : 2773995 : tree ptr = TREE_OPERAND (base, 0);
1445 : 2773995 : if (TREE_CODE (ptr) == SSA_NAME)
1446 : : {
1447 : : /* For parameters, get at the points-to set for the actual parm
1448 : : decl. */
1449 : 2619288 : if (SSA_NAME_IS_DEFAULT_DEF (ptr)
1450 : 2619288 : && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
1451 : 0 : || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
1452 : 1772206 : ptr = SSA_NAME_VAR (ptr);
1453 : :
1454 : : /* We need to make sure 'ptr' doesn't include any of
1455 : : the restrict tags we added bases for in its points-to set. */
1456 : 2619288 : varinfo_t vi = lookup_vi_for_tree (ptr);
1457 : 2619288 : if (! vi)
1458 : : return false;
1459 : :
1460 : 2619288 : vi = get_varinfo (var_rep[vi->id]);
1461 : 2619288 : if (bitmap_intersect_p (rvars, vi->solution)
1462 : 2619288 : || (escaped_p && bitmap_bit_p (vi->solution, escaped_id)))
1463 : 1804962 : return false;
1464 : : }
1465 : :
1466 : : /* Do not overwrite existing cliques (that includes clique, base
1467 : : pairs we just set). */
1468 : 969033 : if (MR_DEPENDENCE_CLIQUE (base) == 0)
1469 : : {
1470 : 870905 : MR_DEPENDENCE_CLIQUE (base) = clique;
1471 : 870905 : MR_DEPENDENCE_BASE (base) = 0;
1472 : : }
1473 : : }
1474 : :
1475 : : /* For plain decl accesses see whether they are accesses to globals
1476 : : and rewrite them to MEM_REFs with { clique, 0 }. */
1477 : 2128130 : if (VAR_P (base)
1478 : 1129086 : && is_global_var (base)
1479 : : /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
1480 : : ops callback. */
1481 : 2185743 : && base != ref)
1482 : : {
1483 : : tree *basep = &ref;
1484 : 88429 : while (handled_component_p (*basep))
1485 : 56088 : basep = &TREE_OPERAND (*basep, 0);
1486 : 32341 : gcc_assert (VAR_P (*basep));
1487 : 32341 : tree ptr = build_fold_addr_expr (*basep);
1488 : 32341 : tree zero = build_int_cst (TREE_TYPE (ptr), 0);
1489 : 32341 : *basep = build2 (MEM_REF, TREE_TYPE (*basep), ptr, zero);
1490 : 32341 : MR_DEPENDENCE_CLIQUE (*basep) = clique;
1491 : 32341 : MR_DEPENDENCE_BASE (*basep) = 0;
1492 : : }
1493 : :
1494 : : return false;
1495 : : }
1496 : :
1497 : : struct msdi_data {
1498 : : tree ptr;
1499 : : unsigned short *clique;
1500 : : unsigned short *last_ruid;
1501 : : varinfo_t restrict_var;
1502 : : };
1503 : :
1504 : : /* If BASE is a MEM_REF then assign a clique, base pair to it, updating
1505 : : CLIQUE, *RESTRICT_VAR and LAST_RUID as passed via DATA.
1506 : : Return whether dependence info was assigned to BASE. */
1507 : :
1508 : : static bool
1509 : 1934176 : maybe_set_dependence_info (gimple *, tree base, tree, void *data)
1510 : : {
1511 : 1934176 : tree ptr = ((msdi_data *)data)->ptr;
1512 : 1934176 : unsigned short &clique = *((msdi_data *)data)->clique;
1513 : 1934176 : unsigned short &last_ruid = *((msdi_data *)data)->last_ruid;
1514 : 1934176 : varinfo_t restrict_var = ((msdi_data *)data)->restrict_var;
1515 : 1934176 : if ((TREE_CODE (base) == MEM_REF
1516 : 1934176 : || TREE_CODE (base) == TARGET_MEM_REF)
1517 : 1934176 : && TREE_OPERAND (base, 0) == ptr)
1518 : : {
1519 : : /* Do not overwrite existing cliques. This avoids overwriting dependence
1520 : : info inlined from a function with restrict parameters inlined
1521 : : into a function with restrict parameters. This usually means we
1522 : : prefer to be precise in innermost loops. */
1523 : 1805058 : if (MR_DEPENDENCE_CLIQUE (base) == 0)
1524 : : {
1525 : 1457603 : if (clique == 0)
1526 : : {
1527 : 309483 : if (cfun->last_clique == 0)
1528 : 156816 : cfun->last_clique = 1;
1529 : 309483 : clique = 1;
1530 : : }
1531 : 1457603 : if (restrict_var->ruid == 0)
1532 : 397791 : restrict_var->ruid = ++last_ruid;
1533 : 1457603 : MR_DEPENDENCE_CLIQUE (base) = clique;
1534 : 1457603 : MR_DEPENDENCE_BASE (base) = restrict_var->ruid;
1535 : 1457603 : return true;
1536 : : }
1537 : : }
1538 : : return false;
1539 : : }
1540 : :
1541 : : /* Clear dependence info for the clique DATA. */
1542 : :
1543 : : static bool
1544 : 17426147 : clear_dependence_clique (gimple *, tree base, tree, void *data)
1545 : : {
1546 : 17426147 : unsigned short clique = (uintptr_t)data;
1547 : 17426147 : if ((TREE_CODE (base) == MEM_REF
1548 : 17426147 : || TREE_CODE (base) == TARGET_MEM_REF)
1549 : 17426147 : && MR_DEPENDENCE_CLIQUE (base) == clique)
1550 : : {
1551 : 1049571 : MR_DEPENDENCE_CLIQUE (base) = 0;
1552 : 1049571 : MR_DEPENDENCE_BASE (base) = 0;
1553 : : }
1554 : :
1555 : 17426147 : return false;
1556 : : }
1557 : :
1558 : : /* Compute the set of independend memory references based on restrict
1559 : : tags and their conservative propagation to the points-to sets. */
1560 : :
1561 : : static void
1562 : 4455410 : compute_dependence_clique (void)
1563 : : {
1564 : : /* First clear the special "local" clique. */
1565 : 4455410 : basic_block bb;
1566 : 4455410 : if (cfun->last_clique != 0)
1567 : 10705371 : FOR_EACH_BB_FN (bb, cfun)
1568 : 20346918 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
1569 : 136902117 : !gsi_end_p (gsi); gsi_next (&gsi))
1570 : : {
1571 : 126728658 : gimple *stmt = gsi_stmt (gsi);
1572 : 126728658 : walk_stmt_load_store_ops (stmt, (void *)(uintptr_t) 1,
1573 : : clear_dependence_clique,
1574 : : clear_dependence_clique);
1575 : : }
1576 : :
1577 : 4455410 : unsigned short clique = 0;
1578 : 4455410 : unsigned short last_ruid = 0;
1579 : 4455410 : bitmap rvars = BITMAP_ALLOC (NULL);
1580 : 4455410 : bool escaped_p = false;
1581 : 167625612 : for (unsigned i = 0; i < num_ssa_names; ++i)
1582 : : {
1583 : 163170202 : tree ptr = ssa_name (i);
1584 : 163170202 : if (!ptr || !POINTER_TYPE_P (TREE_TYPE (ptr)))
1585 : 139862291 : continue;
1586 : :
1587 : : /* Avoid all this when ptr is not dereferenced? */
1588 : 24339204 : tree p = ptr;
1589 : 24339204 : if (SSA_NAME_IS_DEFAULT_DEF (ptr)
1590 : 24339204 : && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
1591 : 943404 : || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
1592 : 4234863 : p = SSA_NAME_VAR (ptr);
1593 : 24339204 : varinfo_t vi = lookup_vi_for_tree (p);
1594 : 24339204 : if (!vi)
1595 : 1031293 : continue;
1596 : 23307911 : vi = get_varinfo (var_rep[vi->id]);
1597 : 23307911 : bitmap_iterator bi;
1598 : 23307911 : unsigned j;
1599 : 23307911 : varinfo_t restrict_var = NULL;
1600 : 29146699 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
1601 : : {
1602 : 27903428 : varinfo_t oi = get_varinfo (j);
1603 : 27903428 : if (oi->head != j)
1604 : 922929 : oi = get_varinfo (oi->head);
1605 : 27903428 : if (oi->is_restrict_var)
1606 : : {
1607 : 1728241 : if (restrict_var
1608 : 1728241 : && restrict_var != oi)
1609 : : {
1610 : 40 : if (dump_file && (dump_flags & TDF_DETAILS))
1611 : : {
1612 : 0 : fprintf (dump_file, "found restrict pointed-to "
1613 : : "for ");
1614 : 0 : print_generic_expr (dump_file, ptr);
1615 : 0 : fprintf (dump_file, " but not exclusively\n");
1616 : : }
1617 : : restrict_var = NULL;
1618 : : break;
1619 : : }
1620 : : restrict_var = oi;
1621 : : }
1622 : : /* NULL is the only other valid points-to entry. */
1623 : 26175187 : else if (oi->id != nothing_id)
1624 : : {
1625 : : restrict_var = NULL;
1626 : : break;
1627 : : }
1628 : : }
1629 : : /* Ok, found that ptr must(!) point to a single(!) restrict
1630 : : variable. */
1631 : : /* ??? PTA isn't really a proper propagation engine to compute
1632 : : this property.
1633 : : ??? We could handle merging of two restricts by unifying them. */
1634 : 23307871 : if (restrict_var)
1635 : : {
1636 : : /* Now look at possible dereferences of ptr. */
1637 : 814698 : imm_use_iterator ui;
1638 : 814698 : gimple *use_stmt;
1639 : 814698 : bool used = false;
1640 : 814698 : msdi_data data = { ptr, &clique, &last_ruid, restrict_var };
1641 : 3661568 : FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
1642 : 2846870 : used |= walk_stmt_load_store_ops (use_stmt, &data,
1643 : : maybe_set_dependence_info,
1644 : 814698 : maybe_set_dependence_info);
1645 : 814698 : if (used)
1646 : : {
1647 : : /* Add all subvars to the set of restrict pointed-to set. */
1648 : 2299330 : for (unsigned sv = restrict_var->head; sv != 0;
1649 : 931071 : sv = get_varinfo (sv)->next)
1650 : 931071 : bitmap_set_bit (rvars, sv);
1651 : 437188 : varinfo_t escaped = get_varinfo (var_rep[escaped_id]);
1652 : 437188 : if (bitmap_bit_p (escaped->solution, restrict_var->id))
1653 : 814698 : escaped_p = true;
1654 : : }
1655 : : }
1656 : : }
1657 : :
1658 : 4455410 : if (clique != 0)
1659 : : {
1660 : : /* Assign the BASE id zero to all accesses not based on a restrict
1661 : : pointer. That way they get disambiguated against restrict
1662 : : accesses but not against each other. */
1663 : : /* ??? For restricts derived from globals (thus not incoming
1664 : : parameters) we can't restrict scoping properly thus the following
1665 : : is too aggressive there. For now we have excluded those globals from
1666 : : getting into the MR_DEPENDENCE machinery. */
1667 : 309483 : vls_data data = { clique, escaped_p, rvars };
1668 : 309483 : basic_block bb;
1669 : 2836685 : FOR_EACH_BB_FN (bb, cfun)
1670 : 5054404 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
1671 : 19212483 : !gsi_end_p (gsi); gsi_next (&gsi))
1672 : : {
1673 : 16685281 : gimple *stmt = gsi_stmt (gsi);
1674 : 16685281 : walk_stmt_load_store_ops (stmt, &data,
1675 : : visit_loadstore, visit_loadstore);
1676 : : }
1677 : : }
1678 : :
1679 : 4455410 : BITMAP_FREE (rvars);
1680 : 4455410 : }
1681 : :
1682 : :
1683 : : /* Compute points-to information for every SSA_NAME pointer in the
1684 : : current function and compute the transitive closure of escaped
1685 : : variables to re-initialize the call-clobber states of local variables. */
1686 : :
1687 : : unsigned int
1688 : 4481923 : compute_may_aliases (void)
1689 : : {
1690 : 4481923 : if (cfun->gimple_df->ipa_pta)
1691 : : {
1692 : 26513 : if (dump_file)
1693 : : {
1694 : 0 : fprintf (dump_file, "\nNot re-computing points-to information "
1695 : : "because IPA points-to information is available.\n\n");
1696 : :
1697 : : /* But still dump what we have remaining it. */
1698 : 0 : if (dump_flags & (TDF_DETAILS|TDF_ALIAS))
1699 : 0 : dump_alias_info (dump_file);
1700 : : }
1701 : :
1702 : 26513 : return 0;
1703 : : }
1704 : :
1705 : : /* For each pointer P_i, determine the sets of variables that P_i may
1706 : : point-to. Compute the reachability set of escaped and call-used
1707 : : variables. */
1708 : 4455410 : compute_points_to_sets ();
1709 : :
1710 : : /* Debugging dumps. */
1711 : 4455410 : if (dump_file && (dump_flags & (TDF_DETAILS|TDF_ALIAS)))
1712 : 282 : dump_alias_info (dump_file);
1713 : :
1714 : : /* Compute restrict-based memory disambiguations. */
1715 : 4455410 : compute_dependence_clique ();
1716 : :
1717 : : /* Deallocate memory used by aliasing data structures and the internal
1718 : : points-to solution. */
1719 : 4455410 : delete_points_to_sets ();
1720 : :
1721 : 4455410 : gcc_assert (!need_ssa_update_p (cfun));
1722 : :
1723 : : return 0;
1724 : : }
1725 : :
1726 : : /* A dummy pass to cause points-to information to be computed via
1727 : : TODO_rebuild_alias. */
1728 : :
1729 : : namespace {
1730 : :
1731 : : const pass_data pass_data_build_alias =
1732 : : {
1733 : : GIMPLE_PASS, /* type */
1734 : : "alias", /* name */
1735 : : OPTGROUP_NONE, /* optinfo_flags */
1736 : : TV_NONE, /* tv_id */
1737 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
1738 : : 0, /* properties_provided */
1739 : : 0, /* properties_destroyed */
1740 : : 0, /* todo_flags_start */
1741 : : TODO_rebuild_alias, /* todo_flags_finish */
1742 : : };
1743 : :
1744 : : class pass_build_alias : public gimple_opt_pass
1745 : : {
1746 : : public:
1747 : 289080 : pass_build_alias (gcc::context *ctxt)
1748 : 578160 : : gimple_opt_pass (pass_data_build_alias, ctxt)
1749 : : {}
1750 : :
1751 : : /* opt_pass methods: */
1752 : 1035897 : bool gate (function *) final override { return flag_tree_pta; }
1753 : :
1754 : : }; // class pass_build_alias
1755 : :
1756 : : } // anon namespace
1757 : :
1758 : : gimple_opt_pass *
1759 : 289080 : make_pass_build_alias (gcc::context *ctxt)
1760 : : {
1761 : 289080 : return new pass_build_alias (ctxt);
1762 : : }
1763 : :
1764 : : /* A dummy pass to cause points-to information to be computed via
1765 : : TODO_rebuild_alias. */
1766 : :
1767 : : namespace {
1768 : :
1769 : : const pass_data pass_data_build_ealias =
1770 : : {
1771 : : GIMPLE_PASS, /* type */
1772 : : "ealias", /* name */
1773 : : OPTGROUP_NONE, /* optinfo_flags */
1774 : : TV_NONE, /* tv_id */
1775 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
1776 : : 0, /* properties_provided */
1777 : : 0, /* properties_destroyed */
1778 : : 0, /* todo_flags_start */
1779 : : TODO_rebuild_alias, /* todo_flags_finish */
1780 : : };
1781 : :
1782 : : class pass_build_ealias : public gimple_opt_pass
1783 : : {
1784 : : public:
1785 : 289080 : pass_build_ealias (gcc::context *ctxt)
1786 : 578160 : : gimple_opt_pass (pass_data_build_ealias, ctxt)
1787 : : {}
1788 : :
1789 : : /* opt_pass methods: */
1790 : 2466470 : bool gate (function *) final override { return flag_tree_pta; }
1791 : :
1792 : : }; // class pass_build_ealias
1793 : :
1794 : : } // anon namespace
1795 : :
1796 : : gimple_opt_pass *
1797 : 289080 : make_pass_build_ealias (gcc::context *ctxt)
1798 : : {
1799 : 289080 : return new pass_build_ealias (ctxt);
1800 : : }
1801 : :
1802 : :
1803 : : /* IPA PTA solutions for ESCAPED. */
1804 : : struct pt_solution ipa_escaped_pt
1805 : : = { true, false, false, false, false, false,
1806 : : false, false, false, false, false, NULL };
1807 : :
1808 : :
1809 : : /* Execute the driver for IPA PTA. */
1810 : : static unsigned int
1811 : 4410 : ipa_pta_execute (void)
1812 : : {
1813 : 4410 : struct cgraph_node *node;
1814 : :
1815 : 4410 : in_ipa_mode = 1;
1816 : :
1817 : 4410 : init_alias_vars ();
1818 : :
1819 : 4410 : if (dump_file && (dump_flags & TDF_DETAILS))
1820 : : {
1821 : 17 : symtab->dump (dump_file);
1822 : 17 : fprintf (dump_file, "\n");
1823 : : }
1824 : :
1825 : 4410 : if (dump_file && (dump_flags & TDF_DETAILS))
1826 : : {
1827 : 17 : fprintf (dump_file, "Generating generic constraints\n\n");
1828 : 17 : dump_constraints (dump_file, 0);
1829 : 17 : fprintf (dump_file, "\n");
1830 : : }
1831 : :
1832 : 4410 : ipa_build_constraints ();
1833 : :
1834 : : /* From the constraints compute the points-to sets. */
1835 : 4410 : solve_constraints ();
1836 : :
1837 : 4410 : if (dump_file && (dump_flags & TDF_STATS))
1838 : 0 : dump_sa_stats (dump_file);
1839 : :
1840 : 4410 : if (dump_file && (dump_flags & TDF_DETAILS))
1841 : 17 : dump_sa_points_to_info (dump_file);
1842 : :
1843 : : /* Now post-process solutions to handle locals from different
1844 : : runtime instantiations coming in through recursive invocations. */
1845 : : unsigned shadow_var_cnt = 0;
1846 : 1193972 : for (unsigned i = 1; i < varmap.length (); ++i)
1847 : : {
1848 : 1189562 : varinfo_t fi = get_varinfo (i);
1849 : 1189562 : if (fi->is_fn_info
1850 : 23378 : && fi->decl)
1851 : : /* Automatic variables pointed to by their containing functions
1852 : : parameters need this treatment. */
1853 : 23378 : for (varinfo_t ai = first_vi_for_offset (fi, fi_parm_base);
1854 : 48507 : ai; ai = vi_next (ai))
1855 : : {
1856 : 25129 : varinfo_t vi = get_varinfo (var_rep[ai->id]);
1857 : 25129 : bitmap_iterator bi;
1858 : 25129 : unsigned j;
1859 : 67122 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
1860 : : {
1861 : 41993 : varinfo_t pt = get_varinfo (j);
1862 : 41993 : if (pt->shadow_var_uid == 0
1863 : 40693 : && pt->decl
1864 : 58217 : && auto_var_in_fn_p (pt->decl, fi->decl))
1865 : : {
1866 : 56 : pt->shadow_var_uid = allocate_decl_uid ();
1867 : 56 : shadow_var_cnt++;
1868 : : }
1869 : : }
1870 : : }
1871 : : /* As well as global variables which are another way of passing
1872 : : arguments to recursive invocations. */
1873 : 1166184 : else if (fi->is_global_var)
1874 : : {
1875 : 830683 : for (varinfo_t ai = fi; ai; ai = vi_next (ai))
1876 : : {
1877 : 442257 : varinfo_t vi = get_varinfo (var_rep[ai->id]);
1878 : 442257 : bitmap_iterator bi;
1879 : 442257 : unsigned j;
1880 : 1795470 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
1881 : : {
1882 : 1353213 : varinfo_t pt = get_varinfo (j);
1883 : 1353213 : if (pt->shadow_var_uid == 0
1884 : 1080396 : && pt->decl
1885 : 1507009 : && auto_var_p (pt->decl))
1886 : : {
1887 : 39540 : pt->shadow_var_uid = allocate_decl_uid ();
1888 : 39540 : shadow_var_cnt++;
1889 : : }
1890 : : }
1891 : : }
1892 : : }
1893 : : }
1894 : 4410 : if (shadow_var_cnt && dump_file && (dump_flags & TDF_DETAILS))
1895 : 10 : fprintf (dump_file, "Allocated %u shadow variables for locals "
1896 : : "maybe leaking into recursive invocations of their containing "
1897 : : "functions\n", shadow_var_cnt);
1898 : :
1899 : : /* Compute the global points-to sets for ESCAPED.
1900 : : ??? Note that the computed escape set is not correct
1901 : : for the whole unit as we fail to consider graph edges to
1902 : : externally visible functions. */
1903 : 4410 : ipa_escaped_pt = find_what_var_points_to (NULL, get_varinfo (escaped_id));
1904 : :
1905 : : /* Make sure the ESCAPED solution (which is used as placeholder in
1906 : : other solutions) does not reference itself. This simplifies
1907 : : points-to solution queries. */
1908 : 4410 : ipa_escaped_pt.ipa_escaped = 0;
1909 : :
1910 : : /* Assign the points-to sets to the SSA names in the unit. */
1911 : 27841 : FOR_EACH_DEFINED_FUNCTION (node)
1912 : : {
1913 : 23431 : tree ptr;
1914 : 23431 : struct function *fn;
1915 : 23431 : unsigned i;
1916 : 23431 : basic_block bb;
1917 : :
1918 : : /* Nodes without a body in this partition are not interesting. */
1919 : 23484 : if (!node->has_gimple_body_p ()
1920 : 23378 : || node->in_other_partition
1921 : 46809 : || node->clone_of)
1922 : 53 : continue;
1923 : :
1924 : 23378 : fn = DECL_STRUCT_FUNCTION (node->decl);
1925 : :
1926 : : /* Compute the points-to sets for pointer SSA_NAMEs. */
1927 : 1138141 : FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr)
1928 : : {
1929 : 1114763 : if (ptr
1930 : 1114763 : && POINTER_TYPE_P (TREE_TYPE (ptr)))
1931 : 106980 : find_what_p_points_to (node->decl, ptr);
1932 : : }
1933 : :
1934 : : /* Compute the call-use and call-clobber sets for indirect calls
1935 : : and calls to external functions. */
1936 : 354520 : FOR_EACH_BB_FN (bb, fn)
1937 : : {
1938 : 331142 : gimple_stmt_iterator gsi;
1939 : :
1940 : 1617290 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1941 : : {
1942 : 955006 : gcall *stmt;
1943 : 955006 : struct pt_solution *pt;
1944 : 955006 : varinfo_t vi, fi;
1945 : 955006 : tree decl;
1946 : :
1947 : 955006 : stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
1948 : 955006 : if (!stmt)
1949 : 701736 : continue;
1950 : :
1951 : : /* Handle direct calls to functions with body. */
1952 : 253270 : decl = gimple_call_fndecl (stmt);
1953 : :
1954 : 253270 : {
1955 : 253270 : tree called_decl = NULL_TREE;
1956 : 253270 : if (gimple_call_builtin_p (stmt, BUILT_IN_GOMP_PARALLEL))
1957 : 13 : called_decl = TREE_OPERAND (gimple_call_arg (stmt, 0), 0);
1958 : 253257 : else if (gimple_call_builtin_p (stmt, BUILT_IN_GOACC_PARALLEL))
1959 : 13727 : called_decl = TREE_OPERAND (gimple_call_arg (stmt, 1), 0);
1960 : :
1961 : 13740 : if (called_decl != NULL_TREE
1962 : 13740 : && !fndecl_maybe_in_other_partition (called_decl))
1963 : : decl = called_decl;
1964 : : }
1965 : :
1966 : 253270 : if (decl
1967 : 77092 : && (fi = lookup_vi_for_tree (decl))
1968 : 327297 : && fi->is_fn_info)
1969 : : {
1970 : 39554 : *gimple_call_clobber_set (stmt)
1971 : 19777 : = find_what_var_points_to
1972 : 19777 : (node->decl, first_vi_for_offset (fi, fi_clobbers));
1973 : 39554 : *gimple_call_use_set (stmt)
1974 : 19777 : = find_what_var_points_to
1975 : 19777 : (node->decl, first_vi_for_offset (fi, fi_uses));
1976 : : }
1977 : : /* Handle direct calls to external functions. */
1978 : 233493 : else if (decl && (!fi || fi->decl))
1979 : : {
1980 : 57314 : pt = gimple_call_use_set (stmt);
1981 : 57314 : if (gimple_call_flags (stmt) & ECF_CONST)
1982 : 1524 : memset (pt, 0, sizeof (struct pt_solution));
1983 : 55790 : else if ((vi = lookup_call_use_vi (stmt)) != NULL)
1984 : : {
1985 : 52463 : *pt = find_what_var_points_to (node->decl, vi);
1986 : : /* Escaped (and thus nonlocal) variables are always
1987 : : implicitly used by calls. */
1988 : : /* ??? ESCAPED can be empty even though NONLOCAL
1989 : : always escaped. */
1990 : 52463 : pt->nonlocal = 1;
1991 : 52463 : pt->ipa_escaped = 1;
1992 : : }
1993 : : else
1994 : : {
1995 : : /* If there is nothing special about this call then
1996 : : we have made everything that is used also escape. */
1997 : 3327 : *pt = ipa_escaped_pt;
1998 : 3327 : pt->nonlocal = 1;
1999 : : }
2000 : :
2001 : 57314 : pt = gimple_call_clobber_set (stmt);
2002 : 57314 : if (gimple_call_flags (stmt) &
2003 : : (ECF_CONST|ECF_PURE|ECF_NOVOPS))
2004 : 1725 : memset (pt, 0, sizeof (struct pt_solution));
2005 : 55589 : else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
2006 : : {
2007 : 52278 : *pt = find_what_var_points_to (node->decl, vi);
2008 : : /* Escaped (and thus nonlocal) variables are always
2009 : : implicitly clobbered by calls. */
2010 : : /* ??? ESCAPED can be empty even though NONLOCAL
2011 : : always escaped. */
2012 : 52278 : pt->nonlocal = 1;
2013 : 52278 : pt->ipa_escaped = 1;
2014 : : }
2015 : : else
2016 : : {
2017 : : /* If there is nothing special about this call then
2018 : : we have made everything that is used also escape. */
2019 : 3311 : *pt = ipa_escaped_pt;
2020 : 3311 : pt->nonlocal = 1;
2021 : : }
2022 : : }
2023 : : /* Handle indirect calls. */
2024 : 176179 : else if ((fi = get_fi_for_callee (stmt)))
2025 : : {
2026 : : /* We need to accumulate all clobbers/uses of all possible
2027 : : callees. */
2028 : 176179 : fi = get_varinfo (var_rep[fi->id]);
2029 : : /* If we cannot constrain the set of functions we'll end up
2030 : : calling we end up using/clobbering everything. */
2031 : 176179 : if (bitmap_bit_p (fi->solution, anything_id)
2032 : 677 : || bitmap_bit_p (fi->solution, nonlocal_id)
2033 : 176189 : || bitmap_bit_p (fi->solution, escaped_id))
2034 : : {
2035 : 176169 : pt_solution_reset (gimple_call_clobber_set (stmt));
2036 : 176169 : pt_solution_reset (gimple_call_use_set (stmt));
2037 : : }
2038 : : else
2039 : : {
2040 : 10 : bitmap_iterator bi;
2041 : 10 : unsigned i;
2042 : 10 : struct pt_solution *uses, *clobbers;
2043 : :
2044 : 10 : uses = gimple_call_use_set (stmt);
2045 : 10 : clobbers = gimple_call_clobber_set (stmt);
2046 : 10 : memset (uses, 0, sizeof (struct pt_solution));
2047 : 10 : memset (clobbers, 0, sizeof (struct pt_solution));
2048 : 27 : EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi)
2049 : : {
2050 : 17 : struct pt_solution sol;
2051 : :
2052 : 17 : vi = get_varinfo (i);
2053 : 17 : if (!vi->is_fn_info)
2054 : : {
2055 : : /* ??? We could be more precise here? */
2056 : 0 : uses->nonlocal = 1;
2057 : 0 : uses->ipa_escaped = 1;
2058 : 0 : clobbers->nonlocal = 1;
2059 : 0 : clobbers->ipa_escaped = 1;
2060 : 0 : continue;
2061 : : }
2062 : :
2063 : 17 : if (!uses->anything)
2064 : : {
2065 : 17 : sol = find_what_var_points_to
2066 : 17 : (node->decl,
2067 : : first_vi_for_offset (vi, fi_uses));
2068 : 17 : pt_solution_ior_into (uses, &sol);
2069 : : }
2070 : 17 : if (!clobbers->anything)
2071 : : {
2072 : 17 : sol = find_what_var_points_to
2073 : 17 : (node->decl,
2074 : : first_vi_for_offset (vi, fi_clobbers));
2075 : 17 : pt_solution_ior_into (clobbers, &sol);
2076 : : }
2077 : : }
2078 : : }
2079 : : }
2080 : : else
2081 : 0 : gcc_unreachable ();
2082 : : }
2083 : : }
2084 : :
2085 : 23378 : fn->gimple_df->ipa_pta = true;
2086 : :
2087 : : /* We have to re-set the final-solution cache after each function
2088 : : because what is a "global" is dependent on function context. */
2089 : 23378 : final_solutions->empty ();
2090 : 23378 : obstack_free (&final_solutions_obstack, NULL);
2091 : 23378 : gcc_obstack_init (&final_solutions_obstack);
2092 : : }
2093 : :
2094 : 4410 : delete_points_to_sets ();
2095 : :
2096 : 4410 : in_ipa_mode = 0;
2097 : :
2098 : 4410 : return 0;
2099 : : }
2100 : :
2101 : : namespace {
2102 : :
2103 : : const pass_data pass_data_ipa_pta =
2104 : : {
2105 : : SIMPLE_IPA_PASS, /* type */
2106 : : "pta", /* name */
2107 : : OPTGROUP_NONE, /* optinfo_flags */
2108 : : TV_IPA_PTA, /* tv_id */
2109 : : 0, /* properties_required */
2110 : : 0, /* properties_provided */
2111 : : 0, /* properties_destroyed */
2112 : : 0, /* todo_flags_start */
2113 : : 0, /* todo_flags_finish */
2114 : : };
2115 : :
2116 : : class pass_ipa_pta : public simple_ipa_opt_pass
2117 : : {
2118 : : public:
2119 : 578160 : pass_ipa_pta (gcc::context *ctxt)
2120 : 1156320 : : simple_ipa_opt_pass (pass_data_ipa_pta, ctxt)
2121 : : {}
2122 : :
2123 : : /* opt_pass methods: */
2124 : 233194 : bool gate (function *) final override
2125 : : {
2126 : 233194 : return (optimize
2127 : 150756 : && flag_ipa_pta
2128 : : /* Don't bother doing anything if the program has errors. */
2129 : 237604 : && !seen_error ());
2130 : : }
2131 : :
2132 : 289080 : opt_pass * clone () final override { return new pass_ipa_pta (m_ctxt); }
2133 : :
2134 : 4410 : unsigned int execute (function *) final override
2135 : : {
2136 : 4410 : return ipa_pta_execute ();
2137 : : }
2138 : :
2139 : : }; // class pass_ipa_pta
2140 : :
2141 : : } // anon namespace
2142 : :
2143 : : simple_ipa_opt_pass *
2144 : 289080 : make_pass_ipa_pta (gcc::context *ctxt)
2145 : : {
2146 : 289080 : return new pass_ipa_pta (ctxt);
2147 : : }
|
