Line data Source code
1 : /* Tree based points-to analysis
2 : Copyright (C) 2005-2026 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 1088248 : 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 1088248 : 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 1083501 : if (start->offset > offset)
258 0 : start = get_varinfo (start->head);
259 :
260 3034906 : 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 3034906 : if (offset >= start->offset
267 3034906 : && (offset - start->offset) < start->size)
268 : return start;
269 :
270 1951405 : 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 18633892 : 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 18633892 : if (start->offset > offset)
287 414668 : 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 70824399 : while (start->next
296 60602762 : && offset >= start->offset
297 131419806 : && !((offset - start->offset) < start->size))
298 52190507 : start = vi_next (start);
299 :
300 18633892 : 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 46395662 : determine_global_memory_access (gcall *stmt,
308 : bool *writes_global_memory,
309 : bool *reads_global_memory,
310 : bool *uses_global_memory)
311 : {
312 46395662 : tree callee;
313 46395662 : cgraph_node *node;
314 46395662 : modref_summary *summary;
315 :
316 : /* We need to determine reads to set uses. */
317 46395662 : gcc_assert (!uses_global_memory || reads_global_memory);
318 :
319 46395662 : if ((callee = gimple_call_fndecl (stmt)) != NULL_TREE
320 44244239 : && (node = cgraph_node::get (callee)) != NULL
321 90606021 : && (summary = get_modref_function_summary (node)))
322 : {
323 8712456 : if (writes_global_memory && *writes_global_memory)
324 5381051 : *writes_global_memory = summary->global_memory_written;
325 8712456 : if (reads_global_memory && *reads_global_memory)
326 5989386 : *reads_global_memory = summary->global_memory_read;
327 8712456 : if (reads_global_memory && uses_global_memory
328 2999625 : && !summary->calls_interposable
329 11083219 : && !*reads_global_memory && node->binds_to_current_def_p ())
330 450215 : *uses_global_memory = false;
331 : }
332 46395662 : if ((writes_global_memory && *writes_global_memory)
333 18625659 : || (uses_global_memory && *uses_global_memory)
334 2950590 : || (reads_global_memory && *reads_global_memory))
335 : {
336 43978924 : attr_fnspec fnspec = gimple_call_fnspec (stmt);
337 43978924 : if (fnspec.known_p ())
338 : {
339 6257315 : if (writes_global_memory
340 6257315 : && !fnspec.global_memory_written_p ())
341 1699028 : *writes_global_memory = false;
342 6257315 : if (reads_global_memory && !fnspec.global_memory_read_p ())
343 : {
344 2451346 : *reads_global_memory = false;
345 2451346 : if (uses_global_memory)
346 2050337 : *uses_global_memory = false;
347 : }
348 : }
349 : }
350 46395662 : }
351 :
352 : /* Return true if FNDECL may be part of another lto partition. */
353 :
354 : bool
355 42276 : fndecl_maybe_in_other_partition (tree fndecl)
356 : {
357 42276 : cgraph_node *fn_node = cgraph_node::get (fndecl);
358 42276 : if (fn_node == NULL)
359 : return true;
360 :
361 42276 : 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 227150042 : new_var_info (tree t, const char *name, bool add_id)
370 : {
371 227150042 : unsigned index = varmap.length ();
372 227150042 : varinfo_t ret = variable_info_pool.allocate ();
373 :
374 227150042 : if (dump_file && add_id)
375 : {
376 2354 : char *tempname = xasprintf ("%s(%d)", name, index);
377 2354 : name = ggc_strdup (tempname);
378 2354 : free (tempname);
379 : }
380 :
381 227150042 : ret->id = index;
382 227150042 : ret->name = name;
383 227150042 : ret->decl = t;
384 : /* Vars without decl are artificial and do not have sub-variables. */
385 227150042 : ret->is_artificial_var = (t == NULL_TREE);
386 227150042 : ret->is_special_var = false;
387 227150042 : ret->is_unknown_size_var = false;
388 227150042 : ret->is_full_var = (t == NULL_TREE);
389 227150042 : ret->is_heap_var = false;
390 227150042 : ret->may_have_pointers = true;
391 227150042 : ret->only_restrict_pointers = false;
392 227150042 : ret->is_restrict_var = false;
393 227150042 : ret->ruid = 0;
394 227150042 : ret->is_global_var = (t == NULL_TREE);
395 227150042 : ret->is_ipa_escape_point = false;
396 227150042 : ret->is_fn_info = false;
397 227150042 : ret->address_taken = false;
398 227150042 : if (t && DECL_P (t))
399 43964743 : ret->is_global_var = (is_global_var (t)
400 : /* We have to treat even local register variables
401 : as escape points. */
402 43964743 : || (VAR_P (t) && DECL_HARD_REGISTER (t)));
403 108594345 : ret->is_reg_var = (t && TREE_CODE (t) == SSA_NAME);
404 227150042 : ret->solution = BITMAP_ALLOC (&pta_obstack);
405 227150042 : ret->oldsolution = NULL;
406 227150042 : ret->next = 0;
407 227150042 : ret->shadow_var_uid = 0;
408 227150042 : ret->head = ret->id;
409 :
410 227150042 : stats.total_vars++;
411 :
412 227150042 : varmap.safe_push (ret);
413 :
414 227150042 : return ret;
415 : }
416 :
417 : /* Print out constraint C to FILE. */
418 :
419 : void
420 9502 : dump_constraint (FILE *file, constraint_t c)
421 : {
422 9502 : if (c->lhs.type == ADDRESSOF)
423 0 : fprintf (file, "&");
424 9502 : else if (c->lhs.type == DEREF)
425 869 : fprintf (file, "*");
426 9502 : if (dump_file)
427 9502 : fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
428 : else
429 0 : fprintf (file, "V%d", c->lhs.var);
430 9502 : if (c->lhs.offset == UNKNOWN_OFFSET)
431 6 : fprintf (file, " + UNKNOWN");
432 9496 : else if (c->lhs.offset != 0)
433 7 : fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
434 9502 : fprintf (file, " = ");
435 9502 : if (c->rhs.type == ADDRESSOF)
436 3411 : fprintf (file, "&");
437 6091 : else if (c->rhs.type == DEREF)
438 1217 : fprintf (file, "*");
439 9502 : if (dump_file)
440 9502 : fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
441 : else
442 0 : fprintf (file, "V%d", c->rhs.var);
443 9502 : if (c->rhs.offset == UNKNOWN_OFFSET)
444 1569 : fprintf (file, " + UNKNOWN");
445 7933 : else if (c->rhs.offset != 0)
446 106 : fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
447 9502 : }
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 389 : dump_constraints (FILE *file, int from)
462 : {
463 389 : int i;
464 389 : constraint_t c;
465 9786 : for (i = from; constraints.iterate (i, &c); i++)
466 9397 : if (c)
467 : {
468 9397 : dump_constraint (file, c);
469 9397 : fprintf (file, "\n");
470 : }
471 389 : }
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 5871 : dump_solution_for_var (FILE *file, unsigned int var)
485 : {
486 5871 : varinfo_t vi = get_varinfo (var);
487 5871 : unsigned int i;
488 5871 : bitmap_iterator bi;
489 :
490 : /* Dump the solution for unified vars anyway, this avoids difficulties
491 : in scanning dumps in the testsuite. */
492 5871 : fprintf (file, "%s = { ", vi->name);
493 5871 : vi = get_varinfo (var_rep[var]);
494 15432 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
495 9561 : fprintf (file, "%s ", get_varinfo (i)->name);
496 5871 : fprintf (file, "}");
497 :
498 : /* But note when the variable was unified. */
499 5871 : if (vi->id != var)
500 1237 : fprintf (file, " same as %s", vi->name);
501 :
502 5871 : fprintf (file, "\n");
503 5871 : }
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 301 : dump_sa_points_to_info (FILE *outfile)
538 : {
539 301 : fprintf (outfile, "\nPoints-to sets\n\n");
540 :
541 6829 : for (unsigned i = 1; i < varmap.length (); i++)
542 : {
543 6528 : varinfo_t vi = get_varinfo (i);
544 6528 : if (!vi->may_have_pointers)
545 657 : continue;
546 5871 : dump_solution_for_var (outfile, i);
547 : }
548 301 : }
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 4355961 : shared_bitmap_hasher::hash (const shared_bitmap_info *bi)
690 : {
691 4355961 : return bi->hashcode;
692 : }
693 :
694 : /* Equality function for two shared_bitmap_info_t's. */
695 :
696 : inline bool
697 42835434 : shared_bitmap_hasher::equal (const shared_bitmap_info *sbi1,
698 : const shared_bitmap_info *sbi2)
699 : {
700 42835434 : 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 47239063 : shared_bitmap_lookup (bitmap pt_vars)
712 : {
713 47239063 : shared_bitmap_info **slot;
714 47239063 : struct shared_bitmap_info sbi;
715 :
716 47239063 : sbi.pt_vars = pt_vars;
717 47239063 : sbi.hashcode = bitmap_hash (pt_vars);
718 :
719 47239063 : slot = shared_bitmap_table->find_slot (&sbi, NO_INSERT);
720 47239063 : if (!slot)
721 : return NULL;
722 : else
723 38088509 : return (*slot)->pt_vars;
724 : }
725 :
726 : /* Add a bitmap to the shared bitmap hashtable. */
727 :
728 : static void
729 9150554 : shared_bitmap_add (bitmap pt_vars)
730 : {
731 9150554 : shared_bitmap_info **slot;
732 9150554 : shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
733 :
734 9150554 : sbi->pt_vars = pt_vars;
735 9150554 : sbi->hashcode = bitmap_hash (pt_vars);
736 :
737 9150554 : slot = shared_bitmap_table->find_slot (sbi, INSERT);
738 9150554 : gcc_assert (!*slot);
739 9150554 : *slot = sbi;
740 9150554 : }
741 :
742 : /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
743 :
744 : static void
745 47239063 : set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt,
746 : tree fndecl)
747 : {
748 47239063 : const varinfo_t escaped_vi = get_varinfo (var_rep[escaped_id]);
749 47239063 : const varinfo_t escaped_return_vi = get_varinfo (var_rep[escaped_return_id]);
750 47239063 : const bool everything_escaped
751 47239063 : = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id);
752 47239063 : const bool everything_escaped_return
753 47239063 : = escaped_return_vi->solution
754 47239063 : && bitmap_bit_p (escaped_return_vi->solution, anything_id);
755 47239063 : unsigned int i;
756 47239063 : bitmap_iterator bi;
757 :
758 275945883 : EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
759 : {
760 228706820 : varinfo_t vi = get_varinfo (i);
761 :
762 228706820 : if (vi->is_artificial_var)
763 84505048 : continue;
764 :
765 144201772 : if (everything_escaped
766 144201772 : || (escaped_vi->solution
767 143577241 : && bitmap_bit_p (escaped_vi->solution, i)))
768 : {
769 124730602 : pt->vars_contains_escaped = true;
770 124730602 : pt->vars_contains_escaped_heap |= vi->is_heap_var;
771 : }
772 :
773 144201772 : if (everything_escaped_return
774 144201772 : || (escaped_return_vi->solution
775 144166186 : && bitmap_bit_p (escaped_return_vi->solution, i)))
776 16435723 : pt->vars_contains_escaped_heap |= vi->is_heap_var;
777 :
778 144201772 : if (vi->is_restrict_var)
779 1750820 : pt->vars_contains_restrict = true;
780 :
781 144201772 : if (VAR_P (vi->decl)
782 2705716 : || TREE_CODE (vi->decl) == PARM_DECL
783 2163722 : || TREE_CODE (vi->decl) == RESULT_DECL)
784 : {
785 : /* If we are in IPA mode we will not recompute points-to
786 : sets after inlining so make sure they stay valid. */
787 142048804 : if (in_ipa_mode
788 142048804 : && !DECL_PT_UID_SET_P (vi->decl))
789 33338 : SET_DECL_PT_UID (vi->decl, DECL_UID (vi->decl));
790 :
791 : /* Add the decl to the points-to set. Note that the points-to
792 : set contains global variables. */
793 142048804 : bitmap_set_bit (into, DECL_PT_UID (vi->decl));
794 142048804 : if (vi->is_global_var
795 : /* In IPA mode the escaped_heap trick doesn't work as
796 : ESCAPED is escaped from the unit but
797 : pt_solution_includes_global needs to answer true for
798 : all variables not automatic within a function.
799 : For the same reason is_global_var is not the
800 : correct flag to track - local variables from other
801 : functions also need to be considered global.
802 : Conveniently all HEAP vars are not put in function
803 : scope. */
804 142048804 : || (in_ipa_mode
805 272700 : && fndecl
806 247646 : && ! auto_var_in_fn_p (vi->decl, fndecl)))
807 79932780 : pt->vars_contains_nonlocal = true;
808 :
809 : /* If the variable is an automatic in the local stack frame, record
810 : that. Note this does not include PARM_DECL and RESULT_DECL which
811 : are managed by the caller. */
812 142048804 : if (VAR_P (vi->decl)
813 142048804 : && auto_var_in_fn_p (vi->decl, fndecl))
814 57455046 : pt->vars_contains_auto = true;
815 :
816 : /* If we have a variable that is interposable record that fact
817 : for pointer comparison simplification. */
818 142048804 : if (VAR_P (vi->decl)
819 141496056 : && (TREE_STATIC (vi->decl) || DECL_EXTERNAL (vi->decl))
820 221836785 : && ! decl_binds_to_current_def_p (vi->decl))
821 57288575 : pt->vars_contains_interposable = true;
822 :
823 : /* If this is a local variable we can have overlapping lifetime
824 : of different function invocations through recursion duplicate
825 : it with its shadow variable. */
826 142048804 : if (in_ipa_mode
827 331716 : && vi->shadow_var_uid != 0)
828 : {
829 204271 : bitmap_set_bit (into, vi->shadow_var_uid);
830 204271 : pt->vars_contains_nonlocal = true;
831 : }
832 : }
833 :
834 2152968 : else if (TREE_CODE (vi->decl) == FUNCTION_DECL
835 2152968 : || TREE_CODE (vi->decl) == LABEL_DECL)
836 : {
837 : /* Nothing should read/write from/to code so we can
838 : save bits by not including them in the points-to bitmaps.
839 : Still mark the points-to set as containing global memory
840 : to make code-patching possible - see PR70128. */
841 1998126 : pt->vars_contains_nonlocal = true;
842 : }
843 : }
844 47239063 : }
845 :
846 :
847 : /* Compute the points-to solution *PT for the variable VI. */
848 :
849 : static struct pt_solution
850 61987299 : find_what_var_points_to (tree fndecl, varinfo_t orig_vi)
851 : {
852 61987299 : unsigned int i;
853 61987299 : bitmap_iterator bi;
854 61987299 : bitmap finished_solution;
855 61987299 : bitmap result;
856 61987299 : varinfo_t vi;
857 61987299 : struct pt_solution *pt;
858 :
859 : /* This variable may have been collapsed, let's get the real
860 : variable. */
861 61987299 : vi = get_varinfo (var_rep[orig_vi->id]);
862 :
863 : /* See if we have already computed the solution and return it. */
864 61987299 : pt_solution **slot = &final_solutions->get_or_insert (vi);
865 61987299 : if (*slot != NULL)
866 14250992 : return **slot;
867 :
868 47736307 : *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
869 47736307 : memset (pt, 0, sizeof (struct pt_solution));
870 :
871 : /* Translate artificial variables into SSA_NAME_PTR_INFO
872 : attributes. */
873 279775585 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
874 : {
875 232039278 : varinfo_t vi = get_varinfo (i);
876 :
877 232039278 : if (vi->is_artificial_var)
878 : {
879 86013505 : if (vi->id == nothing_id)
880 9869336 : pt->null = 1;
881 : else if (vi->id == escaped_id)
882 : {
883 32845339 : if (in_ipa_mode)
884 135640 : pt->ipa_escaped = 1;
885 : else
886 32709699 : pt->escaped = 1;
887 : /* Expand some special vars of ESCAPED in-place here. */
888 32845339 : varinfo_t evi = get_varinfo (var_rep[escaped_id]);
889 32845339 : if (bitmap_bit_p (evi->solution, nonlocal_id))
890 30505634 : pt->nonlocal = 1;
891 : }
892 : else if (vi->id == nonlocal_id)
893 36641011 : pt->nonlocal = 1;
894 : else if (vi->id == string_id)
895 6159592 : pt->const_pool = 1;
896 : else if (vi->id == anything_id
897 : || vi->id == integer_id)
898 497259 : pt->anything = 1;
899 : }
900 : }
901 :
902 : /* Instead of doing extra work, simply do not create
903 : elaborate points-to information for pt_anything pointers. */
904 47736307 : if (pt->anything)
905 497244 : return *pt;
906 :
907 : /* Share the final set of variables when possible. */
908 47239063 : finished_solution = BITMAP_GGC_ALLOC ();
909 47239063 : stats.points_to_sets_created++;
910 :
911 47239063 : set_uids_in_ptset (finished_solution, vi->solution, pt, fndecl);
912 47239063 : result = shared_bitmap_lookup (finished_solution);
913 47239063 : if (!result)
914 : {
915 9150554 : shared_bitmap_add (finished_solution);
916 9150554 : pt->vars = finished_solution;
917 : }
918 : else
919 : {
920 38088509 : pt->vars = result;
921 38088509 : bitmap_clear (finished_solution);
922 : }
923 :
924 47239063 : return *pt;
925 : }
926 :
927 : /* Given a pointer variable P, fill in its points-to set. */
928 :
929 : static void
930 24707616 : find_what_p_points_to (tree fndecl, tree p)
931 : {
932 24707616 : struct ptr_info_def *pi;
933 24707616 : tree lookup_p = p;
934 24707616 : varinfo_t vi;
935 24707616 : prange vr;
936 49415232 : get_range_query (DECL_STRUCT_FUNCTION (fndecl))->range_of_expr (vr, p);
937 24707616 : bool nonnull = vr.nonzero_p ();
938 :
939 : /* For parameters, get at the points-to set for the actual parm
940 : decl. */
941 24707616 : if (TREE_CODE (p) == SSA_NAME
942 24707616 : && SSA_NAME_IS_DEFAULT_DEF (p)
943 29933865 : && (TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
944 949333 : || TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL))
945 4334432 : lookup_p = SSA_NAME_VAR (p);
946 :
947 24707616 : vi = lookup_vi_for_tree (lookup_p);
948 24707616 : if (!vi)
949 1031405 : return;
950 :
951 23676211 : pi = get_ptr_info (p);
952 23676211 : pi->pt = find_what_var_points_to (fndecl, vi);
953 : /* Conservatively set to NULL from PTA (to true). */
954 23676211 : pi->pt.null = 1;
955 : /* Preserve pointer nonnull globally computed. */
956 23676211 : if (nonnull)
957 3663004 : set_ptr_nonnull (p);
958 24707616 : }
959 :
960 :
961 : /* Query statistics for points-to solutions. */
962 :
963 : static struct {
964 : unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
965 : unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
966 : unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
967 : unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
968 : } pta_stats;
969 :
970 : void
971 0 : dump_pta_stats (FILE *s)
972 : {
973 0 : fprintf (s, "\nPTA query stats:\n");
974 0 : fprintf (s, " pt_solution_includes: "
975 : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
976 : HOST_WIDE_INT_PRINT_DEC" queries\n",
977 : pta_stats.pt_solution_includes_no_alias,
978 0 : pta_stats.pt_solution_includes_no_alias
979 0 : + pta_stats.pt_solution_includes_may_alias);
980 0 : fprintf (s, " pt_solutions_intersect: "
981 : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
982 : HOST_WIDE_INT_PRINT_DEC" queries\n",
983 : pta_stats.pt_solutions_intersect_no_alias,
984 0 : pta_stats.pt_solutions_intersect_no_alias
985 0 : + pta_stats.pt_solutions_intersect_may_alias);
986 0 : }
987 :
988 :
989 : /* Reset the points-to solution *PT to a conservative default
990 : (point to anything). */
991 :
992 : void
993 69697528 : pt_solution_reset (struct pt_solution *pt)
994 : {
995 69697528 : memset (pt, 0, sizeof (struct pt_solution));
996 69697528 : pt->anything = true;
997 69697528 : pt->null = true;
998 69697528 : }
999 :
1000 : /* Set the points-to solution *PT to point only to the variables
1001 : in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
1002 : global variables and VARS_CONTAINS_RESTRICT specifies whether
1003 : it contains restrict tag variables. */
1004 :
1005 : void
1006 69801 : pt_solution_set (struct pt_solution *pt, bitmap vars,
1007 : bool vars_contains_nonlocal)
1008 : {
1009 69801 : memset (pt, 0, sizeof (struct pt_solution));
1010 69801 : pt->vars = vars;
1011 69801 : pt->vars_contains_nonlocal = vars_contains_nonlocal;
1012 69801 : pt->vars_contains_escaped
1013 139602 : = (cfun->gimple_df->escaped.anything
1014 69801 : || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars));
1015 69801 : }
1016 :
1017 : /* Set the points-to solution *PT to point only to the variable VAR. */
1018 :
1019 : void
1020 202883 : pt_solution_set_var (struct pt_solution *pt, tree var)
1021 : {
1022 202883 : memset (pt, 0, sizeof (struct pt_solution));
1023 202883 : pt->vars = BITMAP_GGC_ALLOC ();
1024 202883 : bitmap_set_bit (pt->vars, DECL_PT_UID (var));
1025 202883 : pt->vars_contains_nonlocal = is_global_var (var);
1026 202883 : pt->vars_contains_escaped
1027 405766 : = (cfun->gimple_df->escaped.anything
1028 202883 : || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var)));
1029 202883 : }
1030 :
1031 : /* Computes the union of the points-to solutions *DEST and *SRC and
1032 : stores the result in *DEST. This changes the points-to bitmap
1033 : of *DEST and thus may not be used if that might be shared.
1034 : The points-to bitmap of *SRC and *DEST will not be shared after
1035 : this function if they were not before. */
1036 :
1037 : static void
1038 36 : pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src)
1039 : {
1040 36 : dest->anything |= src->anything;
1041 36 : if (dest->anything)
1042 : {
1043 2 : pt_solution_reset (dest);
1044 2 : return;
1045 : }
1046 :
1047 34 : dest->nonlocal |= src->nonlocal;
1048 34 : dest->escaped |= src->escaped;
1049 34 : dest->ipa_escaped |= src->ipa_escaped;
1050 34 : dest->null |= src->null;
1051 34 : dest->const_pool |= src->const_pool ;
1052 34 : dest->vars_contains_nonlocal |= src->vars_contains_nonlocal;
1053 34 : dest->vars_contains_escaped |= src->vars_contains_escaped;
1054 34 : dest->vars_contains_escaped_heap |= src->vars_contains_escaped_heap;
1055 34 : if (!src->vars)
1056 : return;
1057 :
1058 34 : if (!dest->vars)
1059 20 : dest->vars = BITMAP_GGC_ALLOC ();
1060 34 : bitmap_ior_into (dest->vars, src->vars);
1061 : }
1062 :
1063 : /* Return true if the points-to solution *PT is empty. */
1064 :
1065 : bool
1066 11605 : pt_solution_empty_p (const pt_solution *pt)
1067 : {
1068 11605 : if (pt->anything
1069 8143 : || pt->nonlocal)
1070 : return false;
1071 :
1072 204 : if (pt->vars
1073 204 : && !bitmap_empty_p (pt->vars))
1074 : return false;
1075 :
1076 : /* If the solution includes ESCAPED, check if that is empty. */
1077 202 : if (pt->escaped
1078 202 : && !pt_solution_empty_p (&cfun->gimple_df->escaped))
1079 : return false;
1080 :
1081 : /* If the solution includes ESCAPED, check if that is empty. */
1082 202 : if (pt->ipa_escaped
1083 202 : && !pt_solution_empty_p (&ipa_escaped_pt))
1084 : return false;
1085 :
1086 : return true;
1087 : }
1088 :
1089 : /* Return true if the points-to solution *PT only point to a single var, and
1090 : return the var uid in *UID. */
1091 :
1092 : bool
1093 902929 : pt_solution_singleton_or_null_p (struct pt_solution *pt, unsigned *uid)
1094 : {
1095 898942 : if (pt->anything || pt->nonlocal || pt->escaped || pt->ipa_escaped
1096 230964 : || pt->vars == NULL
1097 1133893 : || !bitmap_single_bit_set_p (pt->vars))
1098 680205 : return false;
1099 :
1100 222724 : *uid = bitmap_first_set_bit (pt->vars);
1101 222724 : return true;
1102 : }
1103 :
1104 : /* Return true if the points-to solution *PT includes global memory.
1105 : If ESCAPED_LOCAL_P is true then escaped local variables are also
1106 : considered global. */
1107 :
1108 : bool
1109 47609161 : pt_solution_includes_global (struct pt_solution *pt, bool escaped_local_p)
1110 : {
1111 47609161 : if (pt->anything
1112 47152589 : || pt->nonlocal
1113 12103260 : || pt->vars_contains_nonlocal
1114 : /* The following is a hack to make the malloc escape hack work.
1115 : In reality we'd need different sets for escaped-through-return
1116 : and escaped-to-callees and passes would need to be updated. */
1117 5336008 : || pt->vars_contains_escaped_heap)
1118 : return true;
1119 :
1120 2090445 : if (escaped_local_p && pt->vars_contains_escaped)
1121 : return true;
1122 :
1123 : /* 'escaped' is also a placeholder so we have to look into it. */
1124 2089904 : if (pt->escaped)
1125 0 : return pt_solution_includes_global (&cfun->gimple_df->escaped,
1126 0 : escaped_local_p);
1127 :
1128 2089904 : if (pt->ipa_escaped)
1129 0 : return pt_solution_includes_global (&ipa_escaped_pt,
1130 0 : escaped_local_p);
1131 :
1132 : return false;
1133 : }
1134 :
1135 : /* Return true if the points-to solution *PT includes local automatic
1136 : storage. */
1137 :
1138 : bool
1139 6711 : pt_solution_includes_auto (struct pt_solution *pt)
1140 : {
1141 8584 : if (pt->anything
1142 8508 : || pt->vars_contains_auto)
1143 : return true;
1144 :
1145 : /* 'escaped' is also a placeholder so we have to look into it. */
1146 8424 : if (pt->escaped)
1147 1873 : return pt_solution_includes_auto (&cfun->gimple_df->escaped);
1148 :
1149 6551 : if (pt->ipa_escaped)
1150 : return pt_solution_includes_auto (&ipa_escaped_pt);
1151 :
1152 : return false;
1153 : }
1154 :
1155 :
1156 : /* Return true if the points-to solution *PT includes the variable
1157 : declaration DECL. */
1158 :
1159 : static bool
1160 274021860 : pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
1161 : {
1162 274021860 : if (pt->anything)
1163 : return true;
1164 :
1165 268206846 : if (pt->nonlocal
1166 268206846 : && is_global_var (decl))
1167 : return true;
1168 :
1169 247915234 : if (pt->vars
1170 247915234 : && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
1171 : return true;
1172 :
1173 : /* If the solution includes ESCAPED, check it. */
1174 195577448 : if (pt->escaped
1175 195577448 : && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
1176 : return true;
1177 :
1178 : /* If the solution includes ESCAPED, check it. */
1179 168590896 : if (pt->ipa_escaped
1180 168590896 : && pt_solution_includes_1 (&ipa_escaped_pt, decl))
1181 : return true;
1182 :
1183 : return false;
1184 : }
1185 :
1186 : bool
1187 182303815 : pt_solution_includes (struct pt_solution *pt, const_tree decl)
1188 : {
1189 182303815 : bool res = pt_solution_includes_1 (pt, decl);
1190 182303815 : if (res)
1191 78444412 : ++pta_stats.pt_solution_includes_may_alias;
1192 : else
1193 103859403 : ++pta_stats.pt_solution_includes_no_alias;
1194 182303815 : return res;
1195 : }
1196 :
1197 : /* Return true if the points-to solution *PT contains a reference to a
1198 : constant pool entry. */
1199 :
1200 : bool
1201 7891174 : pt_solution_includes_const_pool (struct pt_solution *pt)
1202 : {
1203 7891174 : return (pt->const_pool
1204 7803713 : || pt->nonlocal
1205 460489 : || (pt->escaped && (!cfun || cfun->gimple_df->escaped.const_pool))
1206 8351663 : || (pt->ipa_escaped && ipa_escaped_pt.const_pool));
1207 : }
1208 :
1209 : /* Return true if both points-to solutions PT1 and PT2 have a non-empty
1210 : intersection. */
1211 :
1212 : static bool
1213 87646426 : pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
1214 : {
1215 87646426 : if (pt1->anything || pt2->anything)
1216 : return true;
1217 :
1218 : /* If either points to unknown global memory and the other points to
1219 : any global memory they alias. */
1220 85755214 : if ((pt1->nonlocal
1221 57673920 : && (pt2->nonlocal
1222 12873466 : || pt2->vars_contains_nonlocal))
1223 39153724 : || (pt2->nonlocal
1224 9255145 : && pt1->vars_contains_nonlocal))
1225 : return true;
1226 :
1227 : /* If either points to all escaped memory and the other points to
1228 : any escaped memory they alias. */
1229 38742648 : if ((pt1->escaped
1230 7990340 : && (pt2->escaped
1231 7990340 : || pt2->vars_contains_escaped))
1232 35368024 : || (pt2->escaped
1233 7171309 : && pt1->vars_contains_escaped))
1234 : return true;
1235 :
1236 : /* Check the escaped solution if required.
1237 : ??? Do we need to check the local against the IPA escaped sets? */
1238 33590436 : if ((pt1->ipa_escaped || pt2->ipa_escaped)
1239 33601075 : && !pt_solution_empty_p (&ipa_escaped_pt))
1240 : {
1241 : /* If both point to escaped memory and that solution
1242 : is not empty they alias. */
1243 10631 : if (pt1->ipa_escaped && pt2->ipa_escaped)
1244 : return true;
1245 :
1246 : /* If either points to escaped memory see if the escaped solution
1247 : intersects with the other. */
1248 10631 : if ((pt1->ipa_escaped
1249 1265 : && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
1250 10839 : || (pt2->ipa_escaped
1251 9366 : && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
1252 10045 : return true;
1253 : }
1254 :
1255 : /* Now both pointers alias if their points-to solution intersects. */
1256 33581664 : return (pt1->vars
1257 33581648 : && pt2->vars
1258 67163312 : && bitmap_intersect_p (pt1->vars, pt2->vars));
1259 : }
1260 :
1261 : bool
1262 87635795 : pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
1263 : {
1264 87635795 : bool res = pt_solutions_intersect_1 (pt1, pt2);
1265 87635795 : if (res)
1266 57762309 : ++pta_stats.pt_solutions_intersect_may_alias;
1267 : else
1268 29873486 : ++pta_stats.pt_solutions_intersect_no_alias;
1269 87635795 : return res;
1270 : }
1271 :
1272 :
1273 : /* Initialize things necessary to perform PTA. */
1274 :
1275 : static void
1276 4558211 : init_alias_vars (void)
1277 : {
1278 4558211 : use_field_sensitive = (param_max_fields_for_field_sensitive > 1);
1279 :
1280 4558211 : bitmap_obstack_initialize (&pta_obstack);
1281 4558211 : bitmap_obstack_initialize (&oldpta_obstack);
1282 :
1283 4558211 : constraints.create (8);
1284 4558211 : varmap.create (8);
1285 :
1286 4558211 : memset (&stats, 0, sizeof (stats));
1287 4558211 : shared_bitmap_table = new hash_table<shared_bitmap_hasher> (511);
1288 :
1289 4558211 : final_solutions = new hash_map<varinfo_t, pt_solution *>;
1290 4558211 : gcc_obstack_init (&final_solutions_obstack);
1291 :
1292 4558211 : init_constraint_builder ();
1293 4558211 : }
1294 :
1295 : /* Create points-to sets for the current function. See the comments
1296 : at the start of the file for an algorithmic overview. */
1297 :
1298 : static void
1299 4553792 : compute_points_to_sets (void)
1300 : {
1301 4553792 : basic_block bb;
1302 4553792 : varinfo_t vi;
1303 :
1304 4553792 : timevar_push (TV_TREE_PTA);
1305 :
1306 4553792 : init_alias_vars ();
1307 :
1308 4553792 : intra_build_constraints ();
1309 :
1310 : /* From the constraints compute the points-to sets. */
1311 4553792 : solve_constraints ();
1312 :
1313 4553792 : if (dump_file && (dump_flags & TDF_STATS))
1314 150 : dump_sa_stats (dump_file);
1315 :
1316 4553792 : if (dump_file && (dump_flags & TDF_DETAILS))
1317 283 : dump_sa_points_to_info (dump_file);
1318 :
1319 : /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
1320 4553792 : cfun->gimple_df->escaped = find_what_var_points_to (cfun->decl,
1321 : get_varinfo (escaped_id));
1322 :
1323 : /* Make sure the ESCAPED solution (which is used as placeholder in
1324 : other solutions) does not reference itself. This simplifies
1325 : points-to solution queries. */
1326 4553792 : cfun->gimple_df->escaped.escaped = 0;
1327 :
1328 : /* The ESCAPED_RETURN solution is what contains all memory that needs
1329 : to be considered global. */
1330 4553792 : cfun->gimple_df->escaped_return
1331 4553792 : = find_what_var_points_to (cfun->decl, get_varinfo (escaped_return_id));
1332 4553792 : cfun->gimple_df->escaped_return.escaped = 1;
1333 :
1334 : /* Compute the points-to sets for pointer SSA_NAMEs. */
1335 4553792 : unsigned i;
1336 4553792 : tree ptr;
1337 :
1338 167309636 : FOR_EACH_SSA_NAME (i, ptr, cfun)
1339 : {
1340 127541911 : if (POINTER_TYPE_P (TREE_TYPE (ptr)))
1341 24599199 : find_what_p_points_to (cfun->decl, ptr);
1342 : }
1343 :
1344 : /* Compute the call-used/clobbered sets. */
1345 40349845 : FOR_EACH_BB_FN (bb, cfun)
1346 : {
1347 35796053 : gimple_stmt_iterator gsi;
1348 :
1349 335487870 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1350 : {
1351 263895764 : gcall *stmt;
1352 263895764 : struct pt_solution *pt;
1353 :
1354 263895764 : stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
1355 263895764 : if (!stmt)
1356 245868115 : continue;
1357 :
1358 18027649 : pt = gimple_call_use_set (stmt);
1359 18027649 : if (gimple_call_flags (stmt) & ECF_CONST)
1360 1902365 : memset (pt, 0, sizeof (struct pt_solution));
1361 : else
1362 : {
1363 16125284 : bool uses_global_memory = true;
1364 16125284 : bool reads_global_memory = true;
1365 :
1366 16125284 : determine_global_memory_access (stmt, NULL,
1367 : &reads_global_memory,
1368 : &uses_global_memory);
1369 16125284 : if ((vi = lookup_call_use_vi (stmt)) != NULL)
1370 : {
1371 15153833 : *pt = find_what_var_points_to (cfun->decl, vi);
1372 : /* Escaped (and thus nonlocal) variables are always
1373 : implicitly used by calls. */
1374 : /* ??? ESCAPED can be empty even though NONLOCAL
1375 : always escaped. */
1376 15153833 : if (uses_global_memory)
1377 : {
1378 13622796 : pt->nonlocal = 1;
1379 13622796 : pt->escaped = 1;
1380 : }
1381 : }
1382 971451 : else if (uses_global_memory)
1383 : {
1384 : /* If there is nothing special about this call then
1385 : we have made everything that is used also escape. */
1386 1936 : *pt = cfun->gimple_df->escaped;
1387 1936 : pt->nonlocal = 1;
1388 : }
1389 : else
1390 969515 : memset (pt, 0, sizeof (struct pt_solution));
1391 : }
1392 :
1393 18027649 : pt = gimple_call_clobber_set (stmt);
1394 18027649 : if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
1395 3177868 : memset (pt, 0, sizeof (struct pt_solution));
1396 : else
1397 : {
1398 14849781 : bool writes_global_memory = true;
1399 :
1400 14849781 : determine_global_memory_access (stmt, &writes_global_memory,
1401 : NULL, NULL);
1402 :
1403 14849781 : if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
1404 : {
1405 13897441 : *pt = find_what_var_points_to (cfun->decl, vi);
1406 : /* Escaped (and thus nonlocal) variables are always
1407 : implicitly clobbered by calls. */
1408 : /* ??? ESCAPED can be empty even though NONLOCAL
1409 : always escaped. */
1410 13897441 : if (writes_global_memory)
1411 : {
1412 13048101 : pt->nonlocal = 1;
1413 13048101 : pt->escaped = 1;
1414 : }
1415 : }
1416 952340 : else if (writes_global_memory)
1417 : {
1418 : /* If there is nothing special about this call then
1419 : we have made everything that is used also escape. */
1420 512 : *pt = cfun->gimple_df->escaped;
1421 512 : pt->nonlocal = 1;
1422 : }
1423 : else
1424 951828 : memset (pt, 0, sizeof (struct pt_solution));
1425 : }
1426 : }
1427 : }
1428 :
1429 4553792 : timevar_pop (TV_TREE_PTA);
1430 4553792 : }
1431 :
1432 : /* Delete created points-to sets. */
1433 :
1434 : static void
1435 4558211 : delete_points_to_sets (void)
1436 : {
1437 4558211 : delete shared_bitmap_table;
1438 4558211 : shared_bitmap_table = NULL;
1439 4558211 : if (dump_file && (dump_flags & TDF_STATS))
1440 150 : fprintf (dump_file, "Points to sets created:%d\n",
1441 : stats.points_to_sets_created);
1442 :
1443 4558211 : bitmap_obstack_release (&pta_obstack);
1444 4558211 : constraints.release ();
1445 :
1446 4558211 : free (var_rep);
1447 :
1448 4558211 : varmap.release ();
1449 4558211 : variable_info_pool.release ();
1450 :
1451 9116422 : delete final_solutions;
1452 4558211 : obstack_free (&final_solutions_obstack, NULL);
1453 :
1454 4558211 : delete_constraint_builder ();
1455 4558211 : }
1456 :
1457 :
1458 : struct vls_data
1459 : {
1460 : unsigned short clique;
1461 : bool escaped_p;
1462 : bitmap rvars;
1463 : };
1464 :
1465 : /* Mark "other" loads and stores as belonging to CLIQUE and with
1466 : base zero. */
1467 :
1468 : static bool
1469 4168828 : visit_loadstore (gimple *, tree base, tree ref, void *data)
1470 : {
1471 4168828 : unsigned short clique = ((vls_data *) data)->clique;
1472 4168828 : bitmap rvars = ((vls_data *) data)->rvars;
1473 4168828 : bool escaped_p = ((vls_data *) data)->escaped_p;
1474 4168828 : if (TREE_CODE (base) == MEM_REF
1475 4168828 : || TREE_CODE (base) == TARGET_MEM_REF)
1476 : {
1477 2941765 : tree ptr = TREE_OPERAND (base, 0);
1478 2941765 : if (TREE_CODE (ptr) == SSA_NAME)
1479 : {
1480 : /* For parameters, get at the points-to set for the actual parm
1481 : decl. */
1482 2776469 : if (SSA_NAME_IS_DEFAULT_DEF (ptr)
1483 2776469 : && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
1484 0 : || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
1485 1863301 : ptr = SSA_NAME_VAR (ptr);
1486 :
1487 : /* We need to make sure 'ptr' doesn't include any of
1488 : the restrict tags we added bases for in its points-to set. */
1489 2776469 : varinfo_t vi = lookup_vi_for_tree (ptr);
1490 2776469 : if (! vi)
1491 : return false;
1492 :
1493 2776469 : vi = get_varinfo (var_rep[vi->id]);
1494 2776469 : if (bitmap_intersect_p (rvars, vi->solution)
1495 2776469 : || (escaped_p && bitmap_bit_p (vi->solution, escaped_id)))
1496 1884453 : return false;
1497 : }
1498 :
1499 : /* Do not overwrite existing cliques (that includes clique, base
1500 : pairs we just set). */
1501 1057312 : if (MR_DEPENDENCE_CLIQUE (base) == 0)
1502 : {
1503 954246 : MR_DEPENDENCE_CLIQUE (base) = clique;
1504 954246 : MR_DEPENDENCE_BASE (base) = 0;
1505 : }
1506 : }
1507 :
1508 : /* For plain decl accesses see whether they are accesses to globals
1509 : and rewrite them to MEM_REFs with { clique, 0 }. */
1510 2284375 : if (VAR_P (base)
1511 1192897 : && is_global_var (base)
1512 : /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
1513 : ops callback. */
1514 2343419 : && base != ref)
1515 : {
1516 : tree *basep = &ref;
1517 89807 : while (handled_component_p (*basep))
1518 56913 : basep = &TREE_OPERAND (*basep, 0);
1519 32894 : gcc_assert (VAR_P (*basep));
1520 32894 : tree ptr = build_fold_addr_expr (*basep);
1521 32894 : tree zero = build_int_cst (TREE_TYPE (ptr), 0);
1522 32894 : *basep = build2 (MEM_REF, TREE_TYPE (*basep), ptr, zero);
1523 32894 : MR_DEPENDENCE_CLIQUE (*basep) = clique;
1524 32894 : MR_DEPENDENCE_BASE (*basep) = 0;
1525 : }
1526 :
1527 : return false;
1528 : }
1529 :
1530 : struct msdi_data {
1531 : tree ptr;
1532 : unsigned short *clique;
1533 : unsigned short *last_ruid;
1534 : varinfo_t restrict_var;
1535 : };
1536 :
1537 : /* If BASE is a MEM_REF then assign a clique, base pair to it, updating
1538 : CLIQUE, *RESTRICT_VAR and LAST_RUID as passed via DATA.
1539 : Return whether dependence info was assigned to BASE. */
1540 :
1541 : static bool
1542 2022776 : maybe_set_dependence_info (gimple *, tree base, tree, void *data)
1543 : {
1544 2022776 : tree ptr = ((msdi_data *)data)->ptr;
1545 2022776 : unsigned short &clique = *((msdi_data *)data)->clique;
1546 2022776 : unsigned short &last_ruid = *((msdi_data *)data)->last_ruid;
1547 2022776 : varinfo_t restrict_var = ((msdi_data *)data)->restrict_var;
1548 2022776 : if ((TREE_CODE (base) == MEM_REF
1549 2022776 : || TREE_CODE (base) == TARGET_MEM_REF)
1550 2022776 : && TREE_OPERAND (base, 0) == ptr)
1551 : {
1552 : /* Do not overwrite existing cliques. This avoids overwriting dependence
1553 : info inlined from a function with restrict parameters inlined
1554 : into a function with restrict parameters. This usually means we
1555 : prefer to be precise in innermost loops. */
1556 1895481 : if (MR_DEPENDENCE_CLIQUE (base) == 0)
1557 : {
1558 1554188 : if (clique == 0)
1559 : {
1560 317369 : if (cfun->last_clique == 0)
1561 159540 : cfun->last_clique = 1;
1562 317369 : clique = 1;
1563 : }
1564 1554188 : if (restrict_var->ruid == 0)
1565 410536 : restrict_var->ruid = ++last_ruid;
1566 1554188 : MR_DEPENDENCE_CLIQUE (base) = clique;
1567 1554188 : MR_DEPENDENCE_BASE (base) = restrict_var->ruid;
1568 1554188 : return true;
1569 : }
1570 : }
1571 : return false;
1572 : }
1573 :
1574 : /* Clear dependence info for the clique DATA. */
1575 :
1576 : static bool
1577 17532255 : clear_dependence_clique (gimple *, tree base, tree, void *data)
1578 : {
1579 17532255 : unsigned short clique = (uintptr_t)data;
1580 17532255 : if ((TREE_CODE (base) == MEM_REF
1581 17532255 : || TREE_CODE (base) == TARGET_MEM_REF)
1582 17532255 : && MR_DEPENDENCE_CLIQUE (base) == clique)
1583 : {
1584 1154750 : MR_DEPENDENCE_CLIQUE (base) = 0;
1585 1154750 : MR_DEPENDENCE_BASE (base) = 0;
1586 : }
1587 :
1588 17532255 : return false;
1589 : }
1590 :
1591 : /* Compute the set of independent memory references based on restrict
1592 : tags and their conservative propagation to the points-to sets. */
1593 :
1594 : static void
1595 4553792 : compute_dependence_clique (void)
1596 : {
1597 : /* First clear the special "local" clique. */
1598 4553792 : basic_block bb;
1599 4553792 : if (cfun->last_clique != 0)
1600 10698277 : FOR_EACH_BB_FN (bb, cfun)
1601 20346632 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
1602 144968078 : !gsi_end_p (gsi); gsi_next (&gsi))
1603 : {
1604 134794762 : gimple *stmt = gsi_stmt (gsi);
1605 134794762 : walk_stmt_load_store_ops (stmt, (void *)(uintptr_t) 1,
1606 : clear_dependence_clique,
1607 : clear_dependence_clique);
1608 : }
1609 :
1610 4553792 : unsigned short clique = 0;
1611 4553792 : unsigned short last_ruid = 0;
1612 4553792 : bitmap rvars = BITMAP_ALLOC (NULL);
1613 4553792 : bool escaped_p = false;
1614 171863428 : for (unsigned i = 0; i < num_ssa_names; ++i)
1615 : {
1616 167309636 : tree ptr = ssa_name (i);
1617 167309636 : if (!ptr || !POINTER_TYPE_P (TREE_TYPE (ptr)))
1618 143741647 : continue;
1619 :
1620 : /* Avoid all this when ptr is not dereferenced? */
1621 24599199 : tree p = ptr;
1622 24599199 : if (SSA_NAME_IS_DEFAULT_DEF (ptr)
1623 24599199 : && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
1624 949185 : || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
1625 4316223 : p = SSA_NAME_VAR (ptr);
1626 24599199 : varinfo_t vi = lookup_vi_for_tree (p);
1627 24599199 : if (!vi)
1628 1031210 : continue;
1629 23567989 : vi = get_varinfo (var_rep[vi->id]);
1630 23567989 : bitmap_iterator bi;
1631 23567989 : unsigned j;
1632 23567989 : varinfo_t restrict_var = NULL;
1633 29315334 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
1634 : {
1635 28039970 : varinfo_t oi = get_varinfo (j);
1636 28039970 : if (oi->head != j)
1637 926177 : oi = get_varinfo (oi->head);
1638 28039970 : if (oi->is_restrict_var)
1639 : {
1640 1751025 : if (restrict_var
1641 1751025 : && restrict_var != oi)
1642 : {
1643 1515 : if (dump_file && (dump_flags & TDF_DETAILS))
1644 : {
1645 0 : fprintf (dump_file, "found restrict pointed-to "
1646 : "for ");
1647 0 : print_generic_expr (dump_file, ptr);
1648 0 : fprintf (dump_file, " but not exclusively\n");
1649 : }
1650 : restrict_var = NULL;
1651 : break;
1652 : }
1653 : restrict_var = oi;
1654 : }
1655 : /* NULL is the only other valid points-to entry. */
1656 26288945 : else if (oi->id != nothing_id)
1657 : {
1658 : restrict_var = NULL;
1659 : break;
1660 : }
1661 : }
1662 : /* Ok, found that ptr must(!) point to a single(!) restrict
1663 : variable. */
1664 : /* ??? PTA isn't really a proper propagation engine to compute
1665 : this property.
1666 : ??? We could handle merging of two restricts by unifying them. */
1667 23566474 : if (restrict_var)
1668 : {
1669 : /* Now look at possible dereferences of ptr. */
1670 835468 : imm_use_iterator ui;
1671 835468 : gimple *use_stmt;
1672 835468 : bool used = false;
1673 835468 : msdi_data data = { ptr, &clique, &last_ruid, restrict_var };
1674 4637115 : FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
1675 2966179 : used |= walk_stmt_load_store_ops (use_stmt, &data,
1676 : maybe_set_dependence_info,
1677 835468 : maybe_set_dependence_info);
1678 835468 : if (used)
1679 : {
1680 : /* Add all subvars to the set of restrict pointed-to set. */
1681 2341086 : for (unsigned sv = restrict_var->head; sv != 0;
1682 944382 : sv = get_varinfo (sv)->next)
1683 944382 : bitmap_set_bit (rvars, sv);
1684 452322 : varinfo_t escaped = get_varinfo (var_rep[escaped_id]);
1685 452322 : if (bitmap_bit_p (escaped->solution, restrict_var->id))
1686 835468 : escaped_p = true;
1687 : }
1688 : }
1689 : }
1690 :
1691 4553792 : if (clique != 0)
1692 : {
1693 : /* Assign the BASE id zero to all accesses not based on a restrict
1694 : pointer. That way they get disambiguated against restrict
1695 : accesses but not against each other. */
1696 : /* ??? For restricts derived from globals (thus not incoming
1697 : parameters) we can't restrict scoping properly thus the following
1698 : is too aggressive there. For now we have excluded those globals from
1699 : getting into the MR_DEPENDENCE machinery. */
1700 317369 : vls_data data = { clique, escaped_p, rvars };
1701 317369 : basic_block bb;
1702 2934543 : FOR_EACH_BB_FN (bb, cfun)
1703 5234348 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
1704 20474308 : !gsi_end_p (gsi); gsi_next (&gsi))
1705 : {
1706 17857134 : gimple *stmt = gsi_stmt (gsi);
1707 17857134 : walk_stmt_load_store_ops (stmt, &data,
1708 : visit_loadstore, visit_loadstore);
1709 : }
1710 : }
1711 :
1712 4553792 : BITMAP_FREE (rvars);
1713 4553792 : }
1714 :
1715 :
1716 : /* Compute points-to information for every SSA_NAME pointer in the
1717 : current function and compute the transitive closure of escaped
1718 : variables to re-initialize the call-clobber states of local variables. */
1719 :
1720 : unsigned int
1721 4580838 : compute_may_aliases (void)
1722 : {
1723 4580838 : if (cfun->gimple_df->ipa_pta)
1724 : {
1725 27046 : if (dump_file)
1726 : {
1727 0 : fprintf (dump_file, "\nNot re-computing points-to information "
1728 : "because IPA points-to information is available.\n\n");
1729 :
1730 : /* But still dump what we have remaining it. */
1731 0 : if (dump_flags & (TDF_DETAILS|TDF_ALIAS))
1732 0 : dump_alias_info (dump_file);
1733 : }
1734 :
1735 27046 : return 0;
1736 : }
1737 :
1738 : /* For each pointer P_i, determine the sets of variables that P_i may
1739 : point-to. Compute the reachability set of escaped and call-used
1740 : variables. */
1741 4553792 : compute_points_to_sets ();
1742 :
1743 : /* Debugging dumps. */
1744 4553792 : if (dump_file && (dump_flags & (TDF_DETAILS|TDF_ALIAS)))
1745 283 : dump_alias_info (dump_file);
1746 :
1747 : /* Compute restrict-based memory disambiguations. */
1748 4553792 : compute_dependence_clique ();
1749 :
1750 : /* Deallocate memory used by aliasing data structures and the internal
1751 : points-to solution. */
1752 4553792 : delete_points_to_sets ();
1753 :
1754 4553792 : gcc_assert (!need_ssa_update_p (cfun));
1755 :
1756 : return 0;
1757 : }
1758 :
1759 : /* A dummy pass to cause points-to information to be computed via
1760 : TODO_rebuild_alias. */
1761 :
1762 : namespace {
1763 :
1764 : const pass_data pass_data_build_alias =
1765 : {
1766 : GIMPLE_PASS, /* type */
1767 : "alias", /* name */
1768 : OPTGROUP_NONE, /* optinfo_flags */
1769 : TV_NONE, /* tv_id */
1770 : ( PROP_cfg | PROP_ssa ), /* properties_required */
1771 : 0, /* properties_provided */
1772 : 0, /* properties_destroyed */
1773 : 0, /* todo_flags_start */
1774 : TODO_rebuild_alias, /* todo_flags_finish */
1775 : };
1776 :
1777 : class pass_build_alias : public gimple_opt_pass
1778 : {
1779 : public:
1780 292371 : pass_build_alias (gcc::context *ctxt)
1781 584742 : : gimple_opt_pass (pass_data_build_alias, ctxt)
1782 : {}
1783 :
1784 : /* opt_pass methods: */
1785 1055105 : bool gate (function *) final override { return flag_tree_pta; }
1786 :
1787 : }; // class pass_build_alias
1788 :
1789 : } // anon namespace
1790 :
1791 : gimple_opt_pass *
1792 292371 : make_pass_build_alias (gcc::context *ctxt)
1793 : {
1794 292371 : return new pass_build_alias (ctxt);
1795 : }
1796 :
1797 : /* A dummy pass to cause points-to information to be computed via
1798 : TODO_rebuild_alias. */
1799 :
1800 : namespace {
1801 :
1802 : const pass_data pass_data_build_ealias =
1803 : {
1804 : GIMPLE_PASS, /* type */
1805 : "ealias", /* name */
1806 : OPTGROUP_NONE, /* optinfo_flags */
1807 : TV_NONE, /* tv_id */
1808 : ( PROP_cfg | PROP_ssa ), /* properties_required */
1809 : 0, /* properties_provided */
1810 : 0, /* properties_destroyed */
1811 : 0, /* todo_flags_start */
1812 : TODO_rebuild_alias, /* todo_flags_finish */
1813 : };
1814 :
1815 : class pass_build_ealias : public gimple_opt_pass
1816 : {
1817 : public:
1818 292371 : pass_build_ealias (gcc::context *ctxt)
1819 584742 : : gimple_opt_pass (pass_data_build_ealias, ctxt)
1820 : {}
1821 :
1822 : /* opt_pass methods: */
1823 2528185 : bool gate (function *) final override { return flag_tree_pta; }
1824 :
1825 : }; // class pass_build_ealias
1826 :
1827 : } // anon namespace
1828 :
1829 : gimple_opt_pass *
1830 292371 : make_pass_build_ealias (gcc::context *ctxt)
1831 : {
1832 292371 : return new pass_build_ealias (ctxt);
1833 : }
1834 :
1835 :
1836 : /* IPA PTA solutions for ESCAPED. */
1837 : struct pt_solution ipa_escaped_pt
1838 : = { true, false, false, false, false, false,
1839 : false, false, false, false, false, false, NULL };
1840 :
1841 :
1842 : /* Execute the driver for IPA PTA. */
1843 : static unsigned int
1844 4419 : ipa_pta_execute (void)
1845 : {
1846 4419 : struct cgraph_node *node;
1847 :
1848 4419 : in_ipa_mode = 1;
1849 :
1850 4419 : init_alias_vars ();
1851 :
1852 4419 : if (dump_file && (dump_flags & TDF_DETAILS))
1853 : {
1854 18 : symtab->dump (dump_file);
1855 18 : fprintf (dump_file, "\n");
1856 : }
1857 :
1858 4419 : if (dump_file && (dump_flags & TDF_DETAILS))
1859 : {
1860 18 : fprintf (dump_file, "Generating generic constraints\n\n");
1861 18 : dump_constraints (dump_file, 0);
1862 18 : fprintf (dump_file, "\n");
1863 : }
1864 :
1865 4419 : ipa_build_constraints ();
1866 :
1867 : /* From the constraints compute the points-to sets. */
1868 4419 : solve_constraints ();
1869 :
1870 4419 : if (dump_file && (dump_flags & TDF_STATS))
1871 0 : dump_sa_stats (dump_file);
1872 :
1873 4419 : if (dump_file && (dump_flags & TDF_DETAILS))
1874 18 : dump_sa_points_to_info (dump_file);
1875 :
1876 : /* Now post-process solutions to handle locals from different
1877 : runtime instantiations coming in through recursive invocations. */
1878 : unsigned shadow_var_cnt = 0;
1879 1215806 : for (unsigned i = 1; i < varmap.length (); ++i)
1880 : {
1881 1211387 : varinfo_t fi = get_varinfo (i);
1882 1211387 : if (fi->is_fn_info
1883 23741 : && fi->decl)
1884 : /* Automatic variables pointed to by their containing functions
1885 : parameters need this treatment. */
1886 23741 : for (varinfo_t ai = first_vi_for_offset (fi, fi_parm_base);
1887 49235 : ai; ai = vi_next (ai))
1888 : {
1889 25494 : varinfo_t vi = get_varinfo (var_rep[ai->id]);
1890 25494 : bitmap_iterator bi;
1891 25494 : unsigned j;
1892 68926 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
1893 : {
1894 43432 : varinfo_t pt = get_varinfo (j);
1895 43432 : if (pt->shadow_var_uid == 0
1896 42132 : && pt->decl
1897 60054 : && auto_var_in_fn_p (pt->decl, fi->decl))
1898 : {
1899 56 : pt->shadow_var_uid = allocate_decl_uid ();
1900 56 : shadow_var_cnt++;
1901 : }
1902 : }
1903 : }
1904 : /* As well as global variables which are another way of passing
1905 : arguments to recursive invocations. */
1906 1187646 : else if (fi->is_global_var)
1907 : {
1908 846435 : for (varinfo_t ai = fi; ai; ai = vi_next (ai))
1909 : {
1910 450825 : varinfo_t vi = get_varinfo (var_rep[ai->id]);
1911 450825 : bitmap_iterator bi;
1912 450825 : unsigned j;
1913 1844428 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
1914 : {
1915 1393603 : varinfo_t pt = get_varinfo (j);
1916 1393603 : if (pt->shadow_var_uid == 0
1917 1112430 : && pt->decl
1918 1548904 : && auto_var_p (pt->decl))
1919 : {
1920 40940 : pt->shadow_var_uid = allocate_decl_uid ();
1921 40940 : shadow_var_cnt++;
1922 : }
1923 : }
1924 : }
1925 : }
1926 : }
1927 4419 : if (shadow_var_cnt && dump_file && (dump_flags & TDF_DETAILS))
1928 11 : fprintf (dump_file, "Allocated %u shadow variables for locals "
1929 : "maybe leaking into recursive invocations of their containing "
1930 : "functions\n", shadow_var_cnt);
1931 :
1932 : /* Compute the global points-to sets for ESCAPED.
1933 : ??? Note that the computed escape set is not correct
1934 : for the whole unit as we fail to consider graph edges to
1935 : externally visible functions. */
1936 4419 : ipa_escaped_pt = find_what_var_points_to (NULL, get_varinfo (escaped_id));
1937 :
1938 : /* Make sure the ESCAPED solution (which is used as placeholder in
1939 : other solutions) does not reference itself. This simplifies
1940 : points-to solution queries. */
1941 4419 : ipa_escaped_pt.ipa_escaped = 0;
1942 :
1943 : /* Assign the points-to sets to the SSA names in the unit. */
1944 28213 : FOR_EACH_DEFINED_FUNCTION (node)
1945 : {
1946 23794 : tree ptr;
1947 23794 : struct function *fn;
1948 23794 : unsigned i;
1949 23794 : basic_block bb;
1950 :
1951 : /* Nodes without a body in this partition are not interesting. */
1952 23847 : if (!node->has_gimple_body_p ()
1953 23741 : || node->in_other_partition
1954 47535 : || node->clone_of)
1955 53 : continue;
1956 :
1957 23741 : fn = DECL_STRUCT_FUNCTION (node->decl);
1958 :
1959 : /* Compute the points-to sets for pointer SSA_NAMEs. */
1960 1163796 : FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr)
1961 : {
1962 1140055 : if (ptr
1963 1140055 : && POINTER_TYPE_P (TREE_TYPE (ptr)))
1964 108417 : find_what_p_points_to (node->decl, ptr);
1965 : }
1966 :
1967 : /* Compute the call-use and call-clobber sets for indirect calls
1968 : and calls to external functions. */
1969 362281 : FOR_EACH_BB_FN (bb, fn)
1970 : {
1971 338540 : gimple_stmt_iterator gsi;
1972 :
1973 1651737 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1974 : {
1975 974657 : gcall *stmt;
1976 974657 : struct pt_solution *pt;
1977 974657 : varinfo_t vi, fi;
1978 974657 : tree decl;
1979 :
1980 974657 : stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
1981 974657 : if (!stmt)
1982 714627 : continue;
1983 :
1984 : /* Handle direct calls to functions with body. */
1985 260030 : decl = gimple_call_fndecl (stmt);
1986 :
1987 260030 : {
1988 260030 : tree called_decl = NULL_TREE;
1989 260030 : if (gimple_call_builtin_p (stmt, BUILT_IN_GOMP_PARALLEL))
1990 13 : called_decl = TREE_OPERAND (gimple_call_arg (stmt, 0), 0);
1991 260017 : else if (gimple_call_builtin_p (stmt, BUILT_IN_GOACC_PARALLEL))
1992 14079 : called_decl = TREE_OPERAND (gimple_call_arg (stmt, 1), 0);
1993 :
1994 14092 : if (called_decl != NULL_TREE
1995 14092 : && !fndecl_maybe_in_other_partition (called_decl))
1996 : decl = called_decl;
1997 : }
1998 :
1999 260030 : if (decl
2000 78841 : && (fi = lookup_vi_for_tree (decl))
2001 335798 : && fi->is_fn_info)
2002 : {
2003 40268 : *gimple_call_clobber_set (stmt)
2004 20134 : = find_what_var_points_to
2005 20134 : (node->decl, first_vi_for_offset (fi, fi_clobbers));
2006 40268 : *gimple_call_use_set (stmt)
2007 20134 : = find_what_var_points_to
2008 20134 : (node->decl, first_vi_for_offset (fi, fi_uses));
2009 : }
2010 : /* Handle direct calls to external functions. */
2011 239896 : else if (decl && (!fi || fi->decl))
2012 : {
2013 58706 : pt = gimple_call_use_set (stmt);
2014 58706 : if (gimple_call_flags (stmt) & ECF_CONST)
2015 1516 : memset (pt, 0, sizeof (struct pt_solution));
2016 57190 : else if ((vi = lookup_call_use_vi (stmt)) != NULL)
2017 : {
2018 53846 : *pt = find_what_var_points_to (node->decl, vi);
2019 : /* Escaped (and thus nonlocal) variables are always
2020 : implicitly used by calls. */
2021 : /* ??? ESCAPED can be empty even though NONLOCAL
2022 : always escaped. */
2023 53846 : pt->nonlocal = 1;
2024 53846 : pt->ipa_escaped = 1;
2025 : }
2026 : else
2027 : {
2028 : /* If there is nothing special about this call then
2029 : we have made everything that is used also escape. */
2030 3344 : *pt = ipa_escaped_pt;
2031 3344 : pt->nonlocal = 1;
2032 : }
2033 :
2034 58706 : pt = gimple_call_clobber_set (stmt);
2035 58706 : if (gimple_call_flags (stmt) &
2036 : (ECF_CONST|ECF_PURE|ECF_NOVOPS))
2037 1717 : memset (pt, 0, sizeof (struct pt_solution));
2038 56989 : else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
2039 : {
2040 53661 : *pt = find_what_var_points_to (node->decl, vi);
2041 : /* Escaped (and thus nonlocal) variables are always
2042 : implicitly clobbered by calls. */
2043 : /* ??? ESCAPED can be empty even though NONLOCAL
2044 : always escaped. */
2045 53661 : pt->nonlocal = 1;
2046 53661 : pt->ipa_escaped = 1;
2047 : }
2048 : else
2049 : {
2050 : /* If there is nothing special about this call then
2051 : we have made everything that is used also escape. */
2052 3328 : *pt = ipa_escaped_pt;
2053 3328 : pt->nonlocal = 1;
2054 : }
2055 : }
2056 : /* Handle indirect calls. */
2057 181190 : else if ((fi = get_fi_for_callee (stmt)))
2058 : {
2059 : /* We need to accumulate all clobbers/uses of all possible
2060 : callees. */
2061 181190 : fi = get_varinfo (var_rep[fi->id]);
2062 : /* If we cannot constrain the set of functions we'll end up
2063 : calling we end up using/clobbering everything. */
2064 181190 : if (bitmap_bit_p (fi->solution, anything_id)
2065 678 : || bitmap_bit_p (fi->solution, nonlocal_id)
2066 181201 : || bitmap_bit_p (fi->solution, escaped_id))
2067 : {
2068 181179 : pt_solution_reset (gimple_call_clobber_set (stmt));
2069 181179 : pt_solution_reset (gimple_call_use_set (stmt));
2070 : }
2071 : else
2072 : {
2073 11 : bitmap_iterator bi;
2074 11 : unsigned i;
2075 11 : struct pt_solution *uses, *clobbers;
2076 :
2077 11 : uses = gimple_call_use_set (stmt);
2078 11 : clobbers = gimple_call_clobber_set (stmt);
2079 11 : memset (uses, 0, sizeof (struct pt_solution));
2080 11 : memset (clobbers, 0, sizeof (struct pt_solution));
2081 29 : EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi)
2082 : {
2083 18 : struct pt_solution sol;
2084 :
2085 18 : vi = get_varinfo (i);
2086 18 : if (!vi->is_fn_info)
2087 : {
2088 : /* ??? We could be more precise here? */
2089 0 : uses->nonlocal = 1;
2090 0 : uses->ipa_escaped = 1;
2091 0 : clobbers->nonlocal = 1;
2092 0 : clobbers->ipa_escaped = 1;
2093 0 : continue;
2094 : }
2095 :
2096 18 : if (!uses->anything)
2097 : {
2098 18 : sol = find_what_var_points_to
2099 18 : (node->decl,
2100 : first_vi_for_offset (vi, fi_uses));
2101 18 : pt_solution_ior_into (uses, &sol);
2102 : }
2103 18 : if (!clobbers->anything)
2104 : {
2105 18 : sol = find_what_var_points_to
2106 18 : (node->decl,
2107 : first_vi_for_offset (vi, fi_clobbers));
2108 18 : pt_solution_ior_into (clobbers, &sol);
2109 : }
2110 : }
2111 : }
2112 : }
2113 : else
2114 0 : gcc_unreachable ();
2115 : }
2116 : }
2117 :
2118 23741 : fn->gimple_df->ipa_pta = true;
2119 :
2120 : /* We have to re-set the final-solution cache after each function
2121 : because what is a "global" is dependent on function context. */
2122 23741 : final_solutions->empty ();
2123 23741 : obstack_free (&final_solutions_obstack, NULL);
2124 23741 : gcc_obstack_init (&final_solutions_obstack);
2125 : }
2126 :
2127 4419 : delete_points_to_sets ();
2128 :
2129 4419 : in_ipa_mode = 0;
2130 :
2131 4419 : return 0;
2132 : }
2133 :
2134 : namespace {
2135 :
2136 : const pass_data pass_data_ipa_pta =
2137 : {
2138 : SIMPLE_IPA_PASS, /* type */
2139 : "pta", /* name */
2140 : OPTGROUP_NONE, /* optinfo_flags */
2141 : TV_IPA_PTA, /* tv_id */
2142 : 0, /* properties_required */
2143 : 0, /* properties_provided */
2144 : 0, /* properties_destroyed */
2145 : 0, /* todo_flags_start */
2146 : 0, /* todo_flags_finish */
2147 : };
2148 :
2149 : class pass_ipa_pta : public simple_ipa_opt_pass
2150 : {
2151 : public:
2152 584742 : pass_ipa_pta (gcc::context *ctxt)
2153 1169484 : : simple_ipa_opt_pass (pass_data_ipa_pta, ctxt)
2154 : {}
2155 :
2156 : /* opt_pass methods: */
2157 238190 : bool gate (function *) final override
2158 : {
2159 238190 : return (optimize
2160 154325 : && flag_ipa_pta
2161 : /* Don't bother doing anything if the program has errors. */
2162 242609 : && !seen_error ());
2163 : }
2164 :
2165 292371 : opt_pass * clone () final override { return new pass_ipa_pta (m_ctxt); }
2166 :
2167 4419 : unsigned int execute (function *) final override
2168 : {
2169 4419 : return ipa_pta_execute ();
2170 : }
2171 :
2172 : }; // class pass_ipa_pta
2173 :
2174 : } // anon namespace
2175 :
2176 : simple_ipa_opt_pass *
2177 292371 : make_pass_ipa_pta (gcc::context *ctxt)
2178 : {
2179 292371 : return new pass_ipa_pta (ctxt);
2180 : }
|
