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 1097877 : 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 1097877 : 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 1093063 : if (start->offset > offset)
258 0 : start = get_varinfo (start->head);
259 :
260 3060105 : 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 3060105 : if (offset >= start->offset
267 3060105 : && (offset - start->offset) < start->size)
268 : return start;
269 :
270 1967042 : 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 18840305 : 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 18840305 : if (start->offset > offset)
287 422099 : 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 71338106 : while (start->next
296 60961783 : && offset >= start->offset
297 132292574 : && !((offset - start->offset) < start->size))
298 52497801 : start = vi_next (start);
299 :
300 18840305 : 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 46626123 : determine_global_memory_access (gcall *stmt,
308 : bool *writes_global_memory,
309 : bool *reads_global_memory,
310 : bool *uses_global_memory)
311 : {
312 46626123 : tree callee;
313 46626123 : cgraph_node *node;
314 46626123 : modref_summary *summary;
315 :
316 : /* We need to determine reads to set uses. */
317 46626123 : gcc_assert (!uses_global_memory || reads_global_memory);
318 :
319 46626123 : if ((callee = gimple_call_fndecl (stmt)) != NULL_TREE
320 44466830 : && (node = cgraph_node::get (callee)) != NULL
321 91058847 : && (summary = get_modref_function_summary (node)))
322 : {
323 8768330 : if (writes_global_memory && *writes_global_memory)
324 5420420 : *writes_global_memory = summary->global_memory_written;
325 8768330 : if (reads_global_memory && *reads_global_memory)
326 6025627 : *reads_global_memory = summary->global_memory_read;
327 8768330 : if (reads_global_memory && uses_global_memory
328 3017738 : && !summary->calls_interposable
329 11149759 : && !*reads_global_memory && node->binds_to_current_def_p ())
330 451568 : *uses_global_memory = false;
331 : }
332 46626123 : if ((writes_global_memory && *writes_global_memory)
333 18712145 : || (uses_global_memory && *uses_global_memory)
334 2959316 : || (reads_global_memory && *reads_global_memory))
335 : {
336 44202681 : attr_fnspec fnspec = gimple_call_fnspec (stmt);
337 44202681 : if (fnspec.known_p ())
338 : {
339 6323241 : if (writes_global_memory
340 6323241 : && !fnspec.global_memory_written_p ())
341 1723453 : *writes_global_memory = false;
342 6323241 : if (reads_global_memory && !fnspec.global_memory_read_p ())
343 : {
344 2477079 : *reads_global_memory = false;
345 2477079 : if (uses_global_memory)
346 2069677 : *uses_global_memory = false;
347 : }
348 : }
349 : }
350 46626123 : }
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 228358565 : new_var_info (tree t, const char *name, bool add_id)
370 : {
371 228358565 : unsigned index = varmap.length ();
372 228358565 : varinfo_t ret = variable_info_pool.allocate ();
373 :
374 228358565 : if (dump_file && add_id)
375 : {
376 2361 : char *tempname = xasprintf ("%s(%d)", name, index);
377 2361 : name = ggc_strdup (tempname);
378 2361 : free (tempname);
379 : }
380 :
381 228358565 : ret->id = index;
382 228358565 : ret->name = name;
383 228358565 : ret->decl = t;
384 : /* Vars without decl are artificial and do not have sub-variables. */
385 228358565 : ret->is_artificial_var = (t == NULL_TREE);
386 228358565 : ret->is_special_var = false;
387 228358565 : ret->is_unknown_size_var = false;
388 228358565 : ret->is_full_var = (t == NULL_TREE);
389 228358565 : ret->is_heap_var = false;
390 228358565 : ret->may_have_pointers = true;
391 228358565 : ret->only_restrict_pointers = false;
392 228358565 : ret->is_restrict_var = false;
393 228358565 : ret->ruid = 0;
394 228358565 : ret->is_global_var = (t == NULL_TREE);
395 228358565 : ret->is_ipa_escape_point = false;
396 228358565 : ret->is_fn_info = false;
397 228358565 : ret->address_taken = false;
398 228358565 : if (t && DECL_P (t))
399 44157398 : ret->is_global_var = (is_global_var (t)
400 : /* We have to treat even local register variables
401 : as escape points. */
402 44157398 : || (VAR_P (t) && DECL_HARD_REGISTER (t)));
403 109209407 : ret->is_reg_var = (t && TREE_CODE (t) == SSA_NAME);
404 228358565 : ret->solution = BITMAP_ALLOC (&pta_obstack);
405 228358565 : ret->oldsolution = NULL;
406 228358565 : ret->next = 0;
407 228358565 : ret->shadow_var_uid = 0;
408 228358565 : ret->head = ret->id;
409 :
410 228358565 : stats.total_vars++;
411 :
412 228358565 : varmap.safe_push (ret);
413 :
414 228358565 : return ret;
415 : }
416 :
417 : /* Print out constraint C to FILE. */
418 :
419 : void
420 9503 : dump_constraint (FILE *file, constraint_t c)
421 : {
422 9503 : if (c->lhs.type == ADDRESSOF)
423 0 : fprintf (file, "&");
424 9503 : else if (c->lhs.type == DEREF)
425 869 : fprintf (file, "*");
426 9503 : if (dump_file)
427 9503 : fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
428 : else
429 0 : fprintf (file, "V%d", c->lhs.var);
430 9503 : if (c->lhs.offset == UNKNOWN_OFFSET)
431 6 : fprintf (file, " + UNKNOWN");
432 9497 : else if (c->lhs.offset != 0)
433 7 : fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
434 9503 : fprintf (file, " = ");
435 9503 : if (c->rhs.type == ADDRESSOF)
436 3410 : fprintf (file, "&");
437 6093 : else if (c->rhs.type == DEREF)
438 1217 : fprintf (file, "*");
439 9503 : if (dump_file)
440 9503 : fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
441 : else
442 0 : fprintf (file, "V%d", c->rhs.var);
443 9503 : if (c->rhs.offset == UNKNOWN_OFFSET)
444 1570 : fprintf (file, " + UNKNOWN");
445 7933 : else if (c->rhs.offset != 0)
446 106 : fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
447 9503 : }
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 9787 : for (i = from; constraints.iterate (i, &c); i++)
466 9398 : if (c)
467 : {
468 9398 : dump_constraint (file, c);
469 9398 : 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 5872 : dump_solution_for_var (FILE *file, unsigned int var)
485 : {
486 5872 : varinfo_t vi = get_varinfo (var);
487 5872 : unsigned int i;
488 5872 : bitmap_iterator bi;
489 :
490 : /* Dump the solution for unified vars anyway, this avoids difficulties
491 : in scanning dumps in the testsuite. */
492 5872 : fprintf (file, "%s = { ", vi->name);
493 5872 : vi = get_varinfo (var_rep[var]);
494 15436 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
495 9564 : fprintf (file, "%s ", get_varinfo (i)->name);
496 5872 : fprintf (file, "}");
497 :
498 : /* But note when the variable was unified. */
499 5872 : if (vi->id != var)
500 1238 : fprintf (file, " same as %s", vi->name);
501 :
502 5872 : fprintf (file, "\n");
503 5872 : }
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 7131 : for (unsigned i = 1; i < varmap.length (); i++)
542 : {
543 6529 : varinfo_t vi = get_varinfo (i);
544 6529 : if (!vi->may_have_pointers)
545 657 : continue;
546 5872 : 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 4216614 : shared_bitmap_hasher::hash (const shared_bitmap_info *bi)
690 : {
691 4216614 : return bi->hashcode;
692 : }
693 :
694 : /* Equality function for two shared_bitmap_info_t's. */
695 :
696 : inline bool
697 42793004 : shared_bitmap_hasher::equal (const shared_bitmap_info *sbi1,
698 : const shared_bitmap_info *sbi2)
699 : {
700 42793004 : 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 47461260 : shared_bitmap_lookup (bitmap pt_vars)
712 : {
713 47461260 : shared_bitmap_info **slot;
714 47461260 : struct shared_bitmap_info sbi;
715 :
716 47461260 : sbi.pt_vars = pt_vars;
717 47461260 : sbi.hashcode = bitmap_hash (pt_vars);
718 :
719 47461260 : slot = shared_bitmap_table->find_slot (&sbi, NO_INSERT);
720 47461260 : if (!slot)
721 : return NULL;
722 : else
723 38266122 : return (*slot)->pt_vars;
724 : }
725 :
726 : /* Add a bitmap to the shared bitmap hashtable. */
727 :
728 : static void
729 9195138 : shared_bitmap_add (bitmap pt_vars)
730 : {
731 9195138 : shared_bitmap_info **slot;
732 9195138 : shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
733 :
734 9195138 : sbi->pt_vars = pt_vars;
735 9195138 : sbi->hashcode = bitmap_hash (pt_vars);
736 :
737 9195138 : slot = shared_bitmap_table->find_slot (sbi, INSERT);
738 9195138 : gcc_assert (!*slot);
739 9195138 : *slot = sbi;
740 9195138 : }
741 :
742 : /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
743 :
744 : static void
745 47461260 : set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt,
746 : tree fndecl)
747 : {
748 47461260 : const varinfo_t escaped_vi = get_varinfo (var_rep[escaped_id]);
749 47461260 : const varinfo_t escaped_return_vi = get_varinfo (var_rep[escaped_return_id]);
750 47461260 : const bool everything_escaped
751 47461260 : = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id);
752 47461260 : const bool everything_escaped_return
753 47461260 : = escaped_return_vi->solution
754 47461260 : && bitmap_bit_p (escaped_return_vi->solution, anything_id);
755 47461260 : unsigned int i;
756 47461260 : bitmap_iterator bi;
757 :
758 276997326 : EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
759 : {
760 229536066 : varinfo_t vi = get_varinfo (i);
761 :
762 229536066 : if (vi->is_artificial_var)
763 84827236 : continue;
764 :
765 144708830 : if (everything_escaped
766 144708830 : || (escaped_vi->solution
767 144085459 : && bitmap_bit_p (escaped_vi->solution, i)))
768 : {
769 125171631 : pt->vars_contains_escaped = true;
770 125171631 : pt->vars_contains_escaped_heap |= vi->is_heap_var;
771 : }
772 :
773 144708830 : if (everything_escaped_return
774 144708830 : || (escaped_return_vi->solution
775 144673244 : && bitmap_bit_p (escaped_return_vi->solution, i)))
776 16488486 : pt->vars_contains_escaped_heap |= vi->is_heap_var;
777 :
778 144708830 : if (vi->is_restrict_var)
779 1748678 : pt->vars_contains_restrict = true;
780 :
781 144708830 : if (VAR_P (vi->decl)
782 : || TREE_CODE (vi->decl) == PARM_DECL
783 : || 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 142539701 : if (in_ipa_mode
788 142539701 : && !DECL_PT_UID_SET_P (vi->decl))
789 33388 : 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 142539701 : bitmap_set_bit (into, DECL_PT_UID (vi->decl));
794 142539701 : 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 142539701 : || (in_ipa_mode
805 272707 : && fndecl
806 247653 : && ! auto_var_in_fn_p (vi->decl, fndecl)))
807 80046306 : 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 142539701 : if (VAR_P (vi->decl)
813 142539701 : && auto_var_in_fn_p (vi->decl, fndecl))
814 57739187 : pt->vars_contains_auto = true;
815 :
816 : /* If we have a variable that is interposable record that fact
817 : for pointer comparison simplification. */
818 142539701 : if (VAR_P (vi->decl)
819 141986336 : && (TREE_STATIC (vi->decl) || DECL_EXTERNAL (vi->decl))
820 222441260 : && ! decl_binds_to_current_def_p (vi->decl))
821 57305097 : 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 142539701 : if (in_ipa_mode
827 331793 : && vi->shadow_var_uid != 0)
828 : {
829 204244 : bitmap_set_bit (into, vi->shadow_var_uid);
830 204244 : pt->vars_contains_nonlocal = true;
831 : }
832 : }
833 :
834 : else if (TREE_CODE (vi->decl) == FUNCTION_DECL
835 : || 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 2011529 : pt->vars_contains_nonlocal = true;
842 : }
843 : }
844 47461260 : }
845 :
846 :
847 : /* Compute the points-to solution *PT for the variable VI. */
848 :
849 : static struct pt_solution
850 62338663 : find_what_var_points_to (tree fndecl, varinfo_t orig_vi)
851 : {
852 62338663 : unsigned int i;
853 62338663 : bitmap_iterator bi;
854 62338663 : bitmap finished_solution;
855 62338663 : bitmap result;
856 62338663 : varinfo_t vi;
857 62338663 : struct pt_solution *pt;
858 :
859 : /* This variable may have been collapsed, let's get the real
860 : variable. */
861 62338663 : vi = get_varinfo (var_rep[orig_vi->id]);
862 :
863 : /* See if we have already computed the solution and return it. */
864 62338663 : pt_solution **slot = &final_solutions->get_or_insert (vi);
865 62338663 : if (*slot != NULL)
866 14339274 : return **slot;
867 :
868 47999389 : *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
869 47999389 : memset (pt, 0, sizeof (struct pt_solution));
870 :
871 : /* Translate artificial variables into SSA_NAME_PTR_INFO
872 : attributes. */
873 281219116 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
874 : {
875 233219727 : varinfo_t vi = get_varinfo (i);
876 :
877 233219727 : if (vi->is_artificial_var)
878 : {
879 86486977 : if (vi->id == nothing_id)
880 9902007 : pt->null = 1;
881 : else if (vi->id == escaped_id)
882 : {
883 33027983 : if (in_ipa_mode)
884 139055 : pt->ipa_escaped = 1;
885 : else
886 32888928 : pt->escaped = 1;
887 : /* Expand some special vars of ESCAPED in-place here. */
888 33027983 : varinfo_t evi = get_varinfo (var_rep[escaped_id]);
889 33027983 : if (bitmap_bit_p (evi->solution, nonlocal_id))
890 30672243 : pt->nonlocal = 1;
891 : }
892 : else if (vi->id == nonlocal_id)
893 36840095 : pt->nonlocal = 1;
894 : else if (vi->id == string_id)
895 6177778 : pt->const_pool = 1;
896 : else if (vi->id == anything_id
897 : || vi->id == integer_id)
898 538146 : 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 47999389 : if (pt->anything)
905 538129 : return *pt;
906 :
907 : /* Share the final set of variables when possible. */
908 47461260 : finished_solution = BITMAP_GGC_ALLOC ();
909 47461260 : stats.points_to_sets_created++;
910 :
911 47461260 : set_uids_in_ptset (finished_solution, vi->solution, pt, fndecl);
912 47461260 : result = shared_bitmap_lookup (finished_solution);
913 47461260 : if (!result)
914 : {
915 9195138 : shared_bitmap_add (finished_solution);
916 9195138 : pt->vars = finished_solution;
917 : }
918 : else
919 : {
920 38266122 : pt->vars = result;
921 38266122 : bitmap_clear (finished_solution);
922 : }
923 :
924 47461260 : return *pt;
925 : }
926 :
927 : /* Given a pointer variable P, fill in its points-to set. */
928 :
929 : static void
930 24882988 : find_what_p_points_to (tree fndecl, tree p)
931 : {
932 24882988 : struct ptr_info_def *pi;
933 24882988 : tree lookup_p = p;
934 24882988 : varinfo_t vi;
935 24882988 : prange vr;
936 49765976 : get_range_query (DECL_STRUCT_FUNCTION (fndecl))->range_of_expr (vr, p);
937 24882988 : bool nonnull = !vr.contains_zero_p ();
938 :
939 : /* For parameters, get at the points-to set for the actual parm
940 : decl. */
941 24882988 : if (TREE_CODE (p) == SSA_NAME
942 24882988 : && SSA_NAME_IS_DEFAULT_DEF (p)
943 30138218 : && (TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
944 958600 : || TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL))
945 4354586 : lookup_p = SSA_NAME_VAR (p);
946 :
947 24882988 : vi = lookup_vi_for_tree (lookup_p);
948 24882988 : if (!vi)
949 1041196 : return;
950 :
951 23841792 : pi = get_ptr_info (p);
952 23841792 : pi->pt = find_what_var_points_to (fndecl, vi);
953 : /* Conservatively set to NULL from PTA (to true). */
954 23841792 : pi->pt.null = 1;
955 : /* Preserve pointer nonnull globally computed. */
956 23841792 : if (nonnull)
957 3708806 : set_ptr_nonnull (p);
958 24882988 : }
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 70171989 : pt_solution_reset (struct pt_solution *pt)
994 : {
995 70171989 : memset (pt, 0, sizeof (struct pt_solution));
996 70171989 : pt->anything = true;
997 70171989 : pt->null = true;
998 70171989 : }
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 70642 : pt_solution_set (struct pt_solution *pt, bitmap vars,
1007 : bool vars_contains_nonlocal)
1008 : {
1009 70642 : memset (pt, 0, sizeof (struct pt_solution));
1010 70642 : pt->vars = vars;
1011 70642 : pt->vars_contains_nonlocal = vars_contains_nonlocal;
1012 70642 : pt->vars_contains_escaped
1013 141284 : = (cfun->gimple_df->escaped.anything
1014 70642 : || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars));
1015 70642 : }
1016 :
1017 : /* Set the points-to solution *PT to point only to the variable VAR. */
1018 :
1019 : void
1020 203670 : pt_solution_set_var (struct pt_solution *pt, tree var)
1021 : {
1022 203670 : memset (pt, 0, sizeof (struct pt_solution));
1023 203670 : pt->vars = BITMAP_GGC_ALLOC ();
1024 203670 : bitmap_set_bit (pt->vars, DECL_PT_UID (var));
1025 203670 : pt->vars_contains_nonlocal = is_global_var (var);
1026 203670 : pt->vars_contains_escaped
1027 407340 : = (cfun->gimple_df->escaped.anything
1028 203670 : || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var)));
1029 203670 : }
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 11590 : pt_solution_empty_p (const pt_solution *pt)
1067 : {
1068 11590 : if (pt->anything
1069 8133 : || 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 904846 : pt_solution_singleton_or_null_p (struct pt_solution *pt, unsigned *uid)
1094 : {
1095 900860 : if (pt->anything || pt->nonlocal || pt->escaped || pt->ipa_escaped
1096 233692 : || pt->vars == NULL
1097 1138538 : || !bitmap_single_bit_set_p (pt->vars))
1098 : return false;
1099 :
1100 225243 : *uid = bitmap_first_set_bit (pt->vars);
1101 225243 : 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 46997213 : pt_solution_includes_global (struct pt_solution *pt, bool escaped_local_p)
1110 : {
1111 46997213 : if (pt->anything
1112 46502334 : || pt->nonlocal
1113 11264218 : || 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 4426447 : || pt->vars_contains_escaped_heap)
1118 : return true;
1119 :
1120 2112880 : 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 2112339 : if (pt->escaped)
1125 0 : return pt_solution_includes_global (&cfun->gimple_df->escaped,
1126 0 : escaped_local_p);
1127 :
1128 2112339 : if (pt->ipa_escaped)
1129 : return pt_solution_includes_global (&ipa_escaped_pt,
1130 : 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 0 : pt_solution_includes_auto (struct pt_solution *pt)
1140 : {
1141 0 : if (pt->anything
1142 0 : || pt->vars_contains_auto)
1143 : return true;
1144 :
1145 : /* 'escaped' is also a placeholder so we have to look into it. */
1146 0 : if (pt->escaped)
1147 0 : return pt_solution_includes_auto (&cfun->gimple_df->escaped);
1148 :
1149 0 : 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 273780320 : pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
1161 : {
1162 275692279 : if (pt->anything)
1163 : return true;
1164 :
1165 269520758 : if (pt->nonlocal
1166 269520758 : && is_global_var (decl))
1167 : return true;
1168 :
1169 249112777 : if (pt->vars
1170 249112777 : && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
1171 : return true;
1172 :
1173 : /* If the solution includes ESCAPED, check it. */
1174 196513712 : if (pt->escaped
1175 196513712 : && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
1176 : return true;
1177 :
1178 : /* If the solution includes ESCAPED, check it. */
1179 169415934 : if (pt->ipa_escaped
1180 169415934 : && pt_solution_includes_1 (&ipa_escaped_pt, decl))
1181 : return true;
1182 :
1183 : return false;
1184 : }
1185 :
1186 : bool
1187 183614801 : pt_solution_includes (struct pt_solution *pt, const_tree decl)
1188 : {
1189 183614801 : bool res = pt_solution_includes_1 (pt, decl);
1190 183614801 : if (res)
1191 79178567 : ++pta_stats.pt_solution_includes_may_alias;
1192 : else
1193 104436234 : ++pta_stats.pt_solution_includes_no_alias;
1194 183614801 : 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 7948656 : pt_solution_includes_const_pool (struct pt_solution *pt)
1202 : {
1203 7948656 : return (pt->const_pool
1204 7873194 : || pt->nonlocal
1205 472533 : || (pt->escaped && (!cfun || cfun->gimple_df->escaped.const_pool))
1206 8421189 : || (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 88524978 : pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
1214 : {
1215 88524978 : 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 86553415 : if ((pt1->nonlocal
1221 57971837 : && (pt2->nonlocal
1222 13007431 : || pt2->vars_contains_nonlocal))
1223 39757370 : || (pt2->nonlocal
1224 9623597 : && 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 39343800 : if ((pt1->escaped
1230 8068910 : && (pt2->escaped
1231 8068910 : || pt2->vars_contains_escaped))
1232 35932892 : || (pt2->escaped
1233 7517894 : && 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 34144431 : if ((pt1->ipa_escaped || pt2->ipa_escaped)
1239 34155067 : && !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 10628 : 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 10628 : if ((pt1->ipa_escaped
1249 1265 : && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
1250 10836 : || (pt2->ipa_escaped
1251 9363 : && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
1252 : return true;
1253 : }
1254 :
1255 : /* Now both pointers alias if their points-to solution intersects. */
1256 34135662 : return (pt1->vars
1257 34135646 : && pt2->vars
1258 68271308 : && bitmap_intersect_p (pt1->vars, pt2->vars));
1259 : }
1260 :
1261 : bool
1262 88514350 : pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
1263 : {
1264 88514350 : bool res = pt_solutions_intersect_1 (pt1, pt2);
1265 88514350 : if (res)
1266 58123765 : ++pta_stats.pt_solutions_intersect_may_alias;
1267 : else
1268 30390585 : ++pta_stats.pt_solutions_intersect_no_alias;
1269 88514350 : return res;
1270 : }
1271 :
1272 :
1273 : /* Initialize things necessary to perform PTA. */
1274 :
1275 : static void
1276 4581907 : init_alias_vars (void)
1277 : {
1278 4581907 : use_field_sensitive = (param_max_fields_for_field_sensitive > 1);
1279 :
1280 4581907 : bitmap_obstack_initialize (&pta_obstack);
1281 4581907 : bitmap_obstack_initialize (&oldpta_obstack);
1282 :
1283 4581907 : constraints.create (8);
1284 4581907 : varmap.create (8);
1285 :
1286 4581907 : memset (&stats, 0, sizeof (stats));
1287 4581907 : shared_bitmap_table = new hash_table<shared_bitmap_hasher> (511);
1288 :
1289 4581907 : final_solutions = new hash_map<varinfo_t, pt_solution *>;
1290 4581907 : gcc_obstack_init (&final_solutions_obstack);
1291 :
1292 4581907 : init_constraint_builder ();
1293 4581907 : }
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 4577412 : compute_points_to_sets (void)
1300 : {
1301 4577412 : basic_block bb;
1302 4577412 : varinfo_t vi;
1303 :
1304 4577412 : timevar_push (TV_TREE_PTA);
1305 :
1306 4577412 : init_alias_vars ();
1307 :
1308 4577412 : intra_build_constraints ();
1309 :
1310 : /* From the constraints compute the points-to sets. */
1311 4577412 : solve_constraints ();
1312 :
1313 4577412 : if (dump_file && (dump_flags & TDF_STATS))
1314 150 : dump_sa_stats (dump_file);
1315 :
1316 4577412 : 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 4577412 : 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 4577412 : 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 4577412 : cfun->gimple_df->escaped_return
1331 4577412 : = find_what_var_points_to (cfun->decl, get_varinfo (escaped_return_id));
1332 4577412 : cfun->gimple_df->escaped_return.escaped = 1;
1333 :
1334 : /* Compute the points-to sets for pointer SSA_NAMEs. */
1335 4577412 : unsigned i;
1336 4577412 : tree ptr;
1337 :
1338 168268664 : FOR_EACH_SSA_NAME (i, ptr, cfun)
1339 : {
1340 128363513 : if (POINTER_TYPE_P (TREE_TYPE (ptr)))
1341 24774377 : find_what_p_points_to (cfun->decl, ptr);
1342 : }
1343 :
1344 : /* Compute the call-used/clobbered sets. */
1345 40596384 : FOR_EACH_BB_FN (bb, cfun)
1346 : {
1347 36018972 : gimple_stmt_iterator gsi;
1348 :
1349 340389122 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1350 : {
1351 268351178 : gcall *stmt;
1352 268351178 : struct pt_solution *pt;
1353 :
1354 268351178 : stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
1355 268351178 : if (!stmt)
1356 250226249 : continue;
1357 :
1358 18124929 : pt = gimple_call_use_set (stmt);
1359 18124929 : if (gimple_call_flags (stmt) & ECF_CONST)
1360 1920532 : memset (pt, 0, sizeof (struct pt_solution));
1361 : else
1362 : {
1363 16204397 : bool uses_global_memory = true;
1364 16204397 : bool reads_global_memory = true;
1365 :
1366 16204397 : determine_global_memory_access (stmt, NULL,
1367 : &reads_global_memory,
1368 : &uses_global_memory);
1369 16204397 : if ((vi = lookup_call_use_vi (stmt)) != NULL)
1370 : {
1371 15221238 : *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 15221238 : if (uses_global_memory)
1377 : {
1378 13681702 : pt->nonlocal = 1;
1379 13681702 : pt->escaped = 1;
1380 : }
1381 : }
1382 983159 : 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 1450 : *pt = cfun->gimple_df->escaped;
1387 1450 : pt->nonlocal = 1;
1388 : }
1389 : else
1390 981709 : memset (pt, 0, sizeof (struct pt_solution));
1391 : }
1392 :
1393 18124929 : pt = gimple_call_clobber_set (stmt);
1394 18124929 : if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
1395 3196190 : memset (pt, 0, sizeof (struct pt_solution));
1396 : else
1397 : {
1398 14928739 : bool writes_global_memory = true;
1399 :
1400 14928739 : determine_global_memory_access (stmt, &writes_global_memory,
1401 : NULL, NULL);
1402 :
1403 14928739 : if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
1404 : {
1405 13964801 : *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 13964801 : if (writes_global_memory)
1411 : {
1412 13107521 : pt->nonlocal = 1;
1413 13107521 : pt->escaped = 1;
1414 : }
1415 : }
1416 963938 : 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 0 : *pt = cfun->gimple_df->escaped;
1421 0 : pt->nonlocal = 1;
1422 : }
1423 : else
1424 963938 : memset (pt, 0, sizeof (struct pt_solution));
1425 : }
1426 : }
1427 : }
1428 :
1429 4577412 : timevar_pop (TV_TREE_PTA);
1430 4577412 : }
1431 :
1432 : /* Delete created points-to sets. */
1433 :
1434 : static void
1435 4581907 : delete_points_to_sets (void)
1436 : {
1437 4581907 : delete shared_bitmap_table;
1438 4581907 : shared_bitmap_table = NULL;
1439 4581907 : 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 4581907 : bitmap_obstack_release (&pta_obstack);
1444 4581907 : constraints.release ();
1445 :
1446 4581907 : free (var_rep);
1447 :
1448 4581907 : varmap.release ();
1449 4581907 : variable_info_pool.release ();
1450 :
1451 9163814 : delete final_solutions;
1452 4581907 : obstack_free (&final_solutions_obstack, NULL);
1453 :
1454 4581907 : delete_constraint_builder ();
1455 4581907 : }
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 4229206 : visit_loadstore (gimple *, tree base, tree ref, void *data)
1470 : {
1471 4229206 : unsigned short clique = ((vls_data *) data)->clique;
1472 4229206 : bitmap rvars = ((vls_data *) data)->rvars;
1473 4229206 : bool escaped_p = ((vls_data *) data)->escaped_p;
1474 4229206 : if (TREE_CODE (base) == MEM_REF
1475 4229206 : || TREE_CODE (base) == TARGET_MEM_REF)
1476 : {
1477 2985099 : tree ptr = TREE_OPERAND (base, 0);
1478 2985099 : if (TREE_CODE (ptr) == SSA_NAME)
1479 : {
1480 : /* For parameters, get at the points-to set for the actual parm
1481 : decl. */
1482 2815351 : if (SSA_NAME_IS_DEFAULT_DEF (ptr)
1483 2815351 : && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
1484 0 : || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
1485 1887462 : 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 2815351 : varinfo_t vi = lookup_vi_for_tree (ptr);
1490 2815351 : if (! vi)
1491 : return false;
1492 :
1493 2815351 : vi = get_varinfo (var_rep[vi->id]);
1494 2815351 : if (bitmap_intersect_p (rvars, vi->solution)
1495 2815351 : || (escaped_p && bitmap_bit_p (vi->solution, escaped_id)))
1496 : return false;
1497 : }
1498 :
1499 : /* Do not overwrite existing cliques (that includes clique, base
1500 : pairs we just set). */
1501 1077908 : if (MR_DEPENDENCE_CLIQUE (base) == 0)
1502 : {
1503 972918 : MR_DEPENDENCE_CLIQUE (base) = clique;
1504 972918 : 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 2322015 : if (VAR_P (base)
1511 1209657 : && is_global_var (base)
1512 : /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
1513 : ops callback. */
1514 2382064 : && base != ref)
1515 : {
1516 : tree *basep = &ref;
1517 91719 : while (handled_component_p (*basep))
1518 58131 : basep = &TREE_OPERAND (*basep, 0);
1519 33588 : gcc_assert (VAR_P (*basep));
1520 33588 : tree ptr = build_fold_addr_expr (*basep);
1521 33588 : tree zero = build_int_cst (TREE_TYPE (ptr), 0);
1522 33588 : *basep = build2 (MEM_REF, TREE_TYPE (*basep), ptr, zero);
1523 33588 : MR_DEPENDENCE_CLIQUE (*basep) = clique;
1524 33588 : 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 2047841 : maybe_set_dependence_info (gimple *, tree base, tree, void *data)
1543 : {
1544 2047841 : tree ptr = ((msdi_data *)data)->ptr;
1545 2047841 : unsigned short &clique = *((msdi_data *)data)->clique;
1546 2047841 : unsigned short &last_ruid = *((msdi_data *)data)->last_ruid;
1547 2047841 : varinfo_t restrict_var = ((msdi_data *)data)->restrict_var;
1548 2047841 : if ((TREE_CODE (base) == MEM_REF
1549 2047841 : || TREE_CODE (base) == TARGET_MEM_REF)
1550 2047841 : && 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 1918746 : if (MR_DEPENDENCE_CLIQUE (base) == 0)
1557 : {
1558 1573440 : if (clique == 0)
1559 : {
1560 319885 : if (cfun->last_clique == 0)
1561 160734 : cfun->last_clique = 1;
1562 319885 : clique = 1;
1563 : }
1564 1573440 : if (restrict_var->ruid == 0)
1565 413998 : restrict_var->ruid = ++last_ruid;
1566 1573440 : MR_DEPENDENCE_CLIQUE (base) = clique;
1567 1573440 : MR_DEPENDENCE_BASE (base) = restrict_var->ruid;
1568 1573440 : return true;
1569 : }
1570 : }
1571 : return false;
1572 : }
1573 :
1574 : /* Clear dependence info for the clique DATA. */
1575 :
1576 : static bool
1577 17820606 : clear_dependence_clique (gimple *, tree base, tree, void *data)
1578 : {
1579 17820606 : unsigned short clique = (uintptr_t)data;
1580 17820606 : if ((TREE_CODE (base) == MEM_REF
1581 17820606 : || TREE_CODE (base) == TARGET_MEM_REF)
1582 17820606 : && MR_DEPENDENCE_CLIQUE (base) == clique)
1583 : {
1584 1173375 : MR_DEPENDENCE_CLIQUE (base) = 0;
1585 1173375 : MR_DEPENDENCE_BASE (base) = 0;
1586 : }
1587 :
1588 17820606 : 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 4577412 : compute_dependence_clique (void)
1596 : {
1597 : /* First clear the special "local" clique. */
1598 4577412 : basic_block bb;
1599 4577412 : if (cfun->last_clique != 0)
1600 10875916 : FOR_EACH_BB_FN (bb, cfun)
1601 20693346 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
1602 148654223 : !gsi_end_p (gsi); gsi_next (&gsi))
1603 : {
1604 138307550 : gimple *stmt = gsi_stmt (gsi);
1605 138307550 : walk_stmt_load_store_ops (stmt, (void *)(uintptr_t) 1,
1606 : clear_dependence_clique,
1607 : clear_dependence_clique);
1608 : }
1609 :
1610 4577412 : unsigned short clique = 0;
1611 4577412 : unsigned short last_ruid = 0;
1612 4577412 : bitmap rvars = BITMAP_ALLOC (NULL);
1613 4577412 : bool escaped_p = false;
1614 177423488 : for (unsigned i = 0; i < num_ssa_names; ++i)
1615 : {
1616 168268664 : tree ptr = ssa_name (i);
1617 168268664 : if (!ptr || !POINTER_TYPE_P (TREE_TYPE (ptr)))
1618 144535278 : continue;
1619 :
1620 : /* Avoid all this when ptr is not dereferenced? */
1621 24774377 : tree p = ptr;
1622 24774377 : if (SSA_NAME_IS_DEFAULT_DEF (ptr)
1623 24774377 : && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
1624 958442 : || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
1625 4336307 : p = SSA_NAME_VAR (ptr);
1626 24774377 : varinfo_t vi = lookup_vi_for_tree (p);
1627 24774377 : if (!vi)
1628 1040991 : continue;
1629 23733386 : vi = get_varinfo (var_rep[vi->id]);
1630 23733386 : bitmap_iterator bi;
1631 23733386 : unsigned j;
1632 23733386 : varinfo_t restrict_var = NULL;
1633 29527496 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
1634 : {
1635 28241325 : varinfo_t oi = get_varinfo (j);
1636 28241325 : if (oi->head != j)
1637 958779 : oi = get_varinfo (oi->head);
1638 28241325 : if (oi->is_restrict_var)
1639 : {
1640 1793326 : if (restrict_var
1641 1793326 : && restrict_var != oi)
1642 : {
1643 1563 : 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 26447999 : 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 23731823 : if (restrict_var)
1668 : {
1669 : /* Now look at possible dereferences of ptr. */
1670 845147 : imm_use_iterator ui;
1671 845147 : gimple *use_stmt;
1672 845147 : bool used = false;
1673 845147 : msdi_data data = { ptr, &clique, &last_ruid, restrict_var };
1674 3851029 : FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
1675 3005882 : used |= walk_stmt_load_store_ops (use_stmt, &data,
1676 : maybe_set_dependence_info,
1677 845147 : maybe_set_dependence_info);
1678 845147 : if (used)
1679 : {
1680 : /* Add all subvars to the set of restrict pointed-to set. */
1681 2366558 : for (unsigned sv = restrict_var->head; sv != 0;
1682 955206 : sv = get_varinfo (sv)->next)
1683 955206 : bitmap_set_bit (rvars, sv);
1684 456146 : varinfo_t escaped = get_varinfo (var_rep[escaped_id]);
1685 456146 : if (bitmap_bit_p (escaped->solution, restrict_var->id))
1686 845147 : escaped_p = true;
1687 : }
1688 : }
1689 : }
1690 :
1691 4577412 : 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 319885 : vls_data data = { clique, escaped_p, rvars };
1701 319885 : basic_block bb;
1702 2959631 : FOR_EACH_BB_FN (bb, cfun)
1703 5279492 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
1704 20772828 : !gsi_end_p (gsi); gsi_next (&gsi))
1705 : {
1706 18133082 : gimple *stmt = gsi_stmt (gsi);
1707 18133082 : walk_stmt_load_store_ops (stmt, &data,
1708 : visit_loadstore, visit_loadstore);
1709 : }
1710 : }
1711 :
1712 4577412 : BITMAP_FREE (rvars);
1713 4577412 : }
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 4604540 : compute_may_aliases (void)
1722 : {
1723 4604540 : if (cfun->gimple_df->ipa_pta)
1724 : {
1725 27128 : 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 : 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 4577412 : compute_points_to_sets ();
1742 :
1743 : /* Debugging dumps. */
1744 4577412 : if (dump_file && (dump_flags & (TDF_DETAILS|TDF_ALIAS)))
1745 283 : dump_alias_info (dump_file);
1746 :
1747 : /* Compute restrict-based memory disambiguations. */
1748 4577412 : compute_dependence_clique ();
1749 :
1750 : /* Deallocate memory used by aliasing data structures and the internal
1751 : points-to solution. */
1752 4577412 : delete_points_to_sets ();
1753 :
1754 4577412 : 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 294196 : pass_build_alias (gcc::context *ctxt)
1781 588392 : : gimple_opt_pass (pass_data_build_alias, ctxt)
1782 : {}
1783 :
1784 : /* opt_pass methods: */
1785 1060389 : 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 294196 : make_pass_build_alias (gcc::context *ctxt)
1793 : {
1794 294196 : 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 294196 : pass_build_ealias (gcc::context *ctxt)
1819 588392 : : gimple_opt_pass (pass_data_build_ealias, ctxt)
1820 : {}
1821 :
1822 : /* opt_pass methods: */
1823 2541743 : 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 294196 : make_pass_build_ealias (gcc::context *ctxt)
1831 : {
1832 294196 : 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 4495 : ipa_pta_execute (void)
1845 : {
1846 4495 : struct cgraph_node *node;
1847 :
1848 4495 : in_ipa_mode = 1;
1849 :
1850 4495 : init_alias_vars ();
1851 :
1852 4495 : if (dump_file && (dump_flags & TDF_DETAILS))
1853 : {
1854 18 : symtab->dump (dump_file);
1855 18 : fprintf (dump_file, "\n");
1856 : }
1857 :
1858 4495 : 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 4495 : ipa_build_constraints ();
1866 :
1867 : /* From the constraints compute the points-to sets. */
1868 4495 : solve_constraints ();
1869 :
1870 4495 : if (dump_file && (dump_flags & TDF_STATS))
1871 0 : dump_sa_stats (dump_file);
1872 :
1873 4495 : 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 4495 : unsigned shadow_var_cnt = 0;
1879 1226754 : for (unsigned i = 1; i < varmap.length (); ++i)
1880 : {
1881 1222259 : varinfo_t fi = get_varinfo (i);
1882 1222259 : if (fi->is_fn_info
1883 23884 : && fi->decl)
1884 : /* Automatic variables pointed to by their containing functions
1885 : parameters need this treatment. */
1886 23884 : for (varinfo_t ai = first_vi_for_offset (fi, fi_parm_base);
1887 49524 : ai; ai = vi_next (ai))
1888 : {
1889 25640 : varinfo_t vi = get_varinfo (var_rep[ai->id]);
1890 25640 : bitmap_iterator bi;
1891 25640 : unsigned j;
1892 69215 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
1893 : {
1894 43575 : varinfo_t pt = get_varinfo (j);
1895 43575 : if (pt->shadow_var_uid == 0
1896 42278 : && pt->decl
1897 60203 : && 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 1198375 : else if (fi->is_global_var)
1907 : {
1908 868091 : for (varinfo_t ai = fi; ai; ai = vi_next (ai))
1909 : {
1910 462561 : varinfo_t vi = get_varinfo (var_rep[ai->id]);
1911 462561 : bitmap_iterator bi;
1912 462561 : unsigned j;
1913 1880856 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
1914 : {
1915 1418295 : varinfo_t pt = get_varinfo (j);
1916 1418295 : if (pt->shadow_var_uid == 0
1917 1137408 : && pt->decl
1918 1575758 : && auto_var_p (pt->decl))
1919 : {
1920 40952 : pt->shadow_var_uid = allocate_decl_uid ();
1921 40952 : shadow_var_cnt++;
1922 : }
1923 : }
1924 : }
1925 : }
1926 : }
1927 4495 : 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 4495 : 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 4495 : ipa_escaped_pt.ipa_escaped = 0;
1942 :
1943 : /* Assign the points-to sets to the SSA names in the unit. */
1944 28432 : FOR_EACH_DEFINED_FUNCTION (node)
1945 : {
1946 23937 : tree ptr;
1947 23937 : struct function *fn;
1948 23937 : unsigned i;
1949 23937 : basic_block bb;
1950 :
1951 : /* Nodes without a body in this partition are not interesting. */
1952 23990 : if (!node->has_gimple_body_p ()
1953 23884 : || node->in_other_partition
1954 47821 : || node->clone_of)
1955 53 : continue;
1956 :
1957 23884 : fn = DECL_STRUCT_FUNCTION (node->decl);
1958 :
1959 : /* Compute the points-to sets for pointer SSA_NAMEs. */
1960 1166548 : FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr)
1961 : {
1962 1142664 : if (ptr
1963 1142664 : && POINTER_TYPE_P (TREE_TYPE (ptr)))
1964 108611 : 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 363678 : FOR_EACH_BB_FN (bb, fn)
1970 : {
1971 339794 : gimple_stmt_iterator gsi;
1972 :
1973 1656368 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1974 : {
1975 976780 : gcall *stmt;
1976 976780 : struct pt_solution *pt;
1977 976780 : varinfo_t vi, fi;
1978 976780 : tree decl;
1979 :
1980 976780 : stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
1981 976780 : if (!stmt)
1982 714879 : continue;
1983 :
1984 : /* Handle direct calls to functions with body. */
1985 261901 : decl = gimple_call_fndecl (stmt);
1986 :
1987 261901 : {
1988 261901 : tree called_decl = NULL_TREE;
1989 261901 : if (gimple_call_builtin_p (stmt, BUILT_IN_GOMP_PARALLEL))
1990 13 : called_decl = TREE_OPERAND (gimple_call_arg (stmt, 0), 0);
1991 261888 : 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 261901 : if (decl
2000 80692 : && (fi = lookup_vi_for_tree (decl))
2001 339520 : && fi->is_fn_info)
2002 : {
2003 40338 : *gimple_call_clobber_set (stmt)
2004 20169 : = find_what_var_points_to
2005 20169 : (node->decl, first_vi_for_offset (fi, fi_clobbers));
2006 40338 : *gimple_call_use_set (stmt)
2007 20169 : = find_what_var_points_to
2008 20169 : (node->decl, first_vi_for_offset (fi, fi_uses));
2009 : }
2010 : /* Handle direct calls to external functions. */
2011 241732 : else if (decl && (!fi || fi->decl))
2012 : {
2013 60522 : pt = gimple_call_use_set (stmt);
2014 60522 : if (gimple_call_flags (stmt) & ECF_CONST)
2015 1516 : memset (pt, 0, sizeof (struct pt_solution));
2016 59006 : else if ((vi = lookup_call_use_vi (stmt)) != NULL)
2017 : {
2018 55662 : *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 55662 : pt->nonlocal = 1;
2024 55662 : 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 60522 : pt = gimple_call_clobber_set (stmt);
2035 60522 : if (gimple_call_flags (stmt) &
2036 : (ECF_CONST|ECF_PURE|ECF_NOVOPS))
2037 1717 : memset (pt, 0, sizeof (struct pt_solution));
2038 58805 : else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
2039 : {
2040 55477 : *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 55477 : pt->nonlocal = 1;
2046 55477 : 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 181210 : else if ((fi = get_fi_for_callee (stmt)))
2058 : {
2059 : /* We need to accumulate all clobbers/uses of all possible
2060 : callees. */
2061 181210 : 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 181210 : if (bitmap_bit_p (fi->solution, anything_id)
2065 678 : || bitmap_bit_p (fi->solution, nonlocal_id)
2066 181221 : || bitmap_bit_p (fi->solution, escaped_id))
2067 : {
2068 181199 : pt_solution_reset (gimple_call_clobber_set (stmt));
2069 181199 : 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 23884 : 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 23884 : final_solutions->empty ();
2123 23884 : obstack_free (&final_solutions_obstack, NULL);
2124 23884 : gcc_obstack_init (&final_solutions_obstack);
2125 : }
2126 :
2127 4495 : delete_points_to_sets ();
2128 :
2129 4495 : in_ipa_mode = 0;
2130 :
2131 4495 : 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 588392 : pass_ipa_pta (gcc::context *ctxt)
2153 1176784 : : simple_ipa_opt_pass (pass_data_ipa_pta, ctxt)
2154 : {}
2155 :
2156 : /* opt_pass methods: */
2157 239659 : bool gate (function *) final override
2158 : {
2159 239659 : return (optimize
2160 155381 : && flag_ipa_pta
2161 : /* Don't bother doing anything if the program has errors. */
2162 244154 : && !seen_error ());
2163 : }
2164 :
2165 294196 : opt_pass * clone () final override { return new pass_ipa_pta (m_ctxt); }
2166 :
2167 4495 : unsigned int execute (function *) final override
2168 : {
2169 4495 : return ipa_pta_execute ();
2170 : }
2171 :
2172 : }; // class pass_ipa_pta
2173 :
2174 : } // anon namespace
2175 :
2176 : simple_ipa_opt_pass *
2177 294196 : make_pass_ipa_pta (gcc::context *ctxt)
2178 : {
2179 294196 : return new pass_ipa_pta (ctxt);
2180 : }
|
