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 1097845 : 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 1097845 : 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 1093030 : if (start->offset > offset)
258 0 : start = get_varinfo (start->head);
259 :
260 3060012 : 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 3060012 : if (offset >= start->offset
267 3060012 : && (offset - start->offset) < start->size)
268 : return start;
269 :
270 1966982 : 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 11941380 : 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 11941380 : if (start->offset > offset)
287 45775 : 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 37351683 : while (start->next
296 30871806 : && offset >= start->offset
297 68217446 : && !((offset - start->offset) < start->size))
298 25410303 : start = vi_next (start);
299 :
300 11941380 : 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 46954642 : determine_global_memory_access (gcall *stmt,
308 : bool *writes_global_memory,
309 : bool *reads_global_memory,
310 : bool *uses_global_memory)
311 : {
312 46954642 : tree callee;
313 46954642 : cgraph_node *node;
314 46954642 : modref_summary *summary;
315 :
316 : /* We need to determine reads to set uses. */
317 46954642 : gcc_assert (!uses_global_memory || reads_global_memory);
318 :
319 46954642 : if ((callee = gimple_call_fndecl (stmt)) != NULL_TREE
320 44790967 : && (node = cgraph_node::get (callee)) != NULL
321 91705887 : && (summary = get_modref_function_summary (node)))
322 : {
323 8776060 : if (writes_global_memory && *writes_global_memory)
324 5439712 : *writes_global_memory = summary->global_memory_written;
325 8776060 : if (reads_global_memory && *reads_global_memory)
326 6024367 : *reads_global_memory = summary->global_memory_read;
327 8776060 : if (reads_global_memory && uses_global_memory
328 3017108 : && !summary->calls_interposable
329 11148705 : && !*reads_global_memory && node->binds_to_current_def_p ())
330 451106 : *uses_global_memory = false;
331 : }
332 46954642 : if ((writes_global_memory && *writes_global_memory)
333 18803821 : || (uses_global_memory && *uses_global_memory)
334 2954078 : || (reads_global_memory && *reads_global_memory))
335 : {
336 44546232 : attr_fnspec fnspec = gimple_call_fnspec (stmt);
337 44546232 : if (fnspec.known_p ())
338 : {
339 6319458 : if (writes_global_memory
340 6319458 : && !fnspec.global_memory_written_p ())
341 1708916 : *writes_global_memory = false;
342 6319458 : if (reads_global_memory && !fnspec.global_memory_read_p ())
343 : {
344 2463458 : *reads_global_memory = false;
345 2463458 : if (uses_global_memory)
346 2048110 : *uses_global_memory = false;
347 : }
348 : }
349 : }
350 46954642 : }
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 229315008 : new_var_info (tree t, const char *name, bool add_id)
370 : {
371 229315008 : unsigned index = varmap.length ();
372 229315008 : varinfo_t ret = variable_info_pool.allocate ();
373 :
374 229315008 : 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 229315008 : ret->id = index;
382 229315008 : ret->name = name;
383 229315008 : ret->decl = t;
384 : /* Vars without decl are artificial and do not have sub-variables. */
385 229315008 : ret->is_artificial_var = (t == NULL_TREE);
386 229315008 : ret->is_special_var = false;
387 229315008 : ret->is_unknown_size_var = false;
388 229315008 : ret->is_full_var = (t == NULL_TREE);
389 229315008 : ret->is_heap_var = false;
390 229315008 : ret->may_have_pointers = true;
391 229315008 : ret->only_restrict_pointers = false;
392 229315008 : ret->is_restrict_var = false;
393 229315008 : ret->ruid = 0;
394 229315008 : ret->is_global_var = (t == NULL_TREE);
395 229315008 : ret->is_ipa_escape_point = false;
396 229315008 : ret->is_fn_info = false;
397 229315008 : ret->address_taken = false;
398 229315008 : if (t && DECL_P (t))
399 44257104 : ret->is_global_var = (is_global_var (t)
400 : /* We have to treat even local register variables
401 : as escape points. */
402 44257104 : || (VAR_P (t) && DECL_HARD_REGISTER (t)));
403 109630954 : ret->is_reg_var = (t && TREE_CODE (t) == SSA_NAME);
404 229315008 : ret->solution = BITMAP_ALLOC (&pta_obstack);
405 229315008 : ret->oldsolution = NULL;
406 229315008 : ret->next = 0;
407 229315008 : ret->shadow_var_uid = 0;
408 229315008 : ret->head = ret->id;
409 :
410 229315008 : stats.total_vars++;
411 :
412 229315008 : varmap.safe_push (ret);
413 :
414 229315008 : 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 15461 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
495 9589 : 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 573 : 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 5633407 : shared_bitmap_hasher::hash (const shared_bitmap_info *bi)
690 : {
691 5633407 : return bi->hashcode;
692 : }
693 :
694 : /* Equality function for two shared_bitmap_info_t's. */
695 :
696 : inline bool
697 50374595 : shared_bitmap_hasher::equal (const shared_bitmap_info *sbi1,
698 : const shared_bitmap_info *sbi2)
699 : {
700 50374595 : 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 53796579 : shared_bitmap_lookup (bitmap pt_vars)
712 : {
713 53796579 : shared_bitmap_info **slot;
714 53796579 : struct shared_bitmap_info sbi;
715 :
716 53796579 : sbi.pt_vars = pt_vars;
717 53796579 : sbi.hashcode = bitmap_hash (pt_vars);
718 :
719 53796579 : slot = shared_bitmap_table->find_slot (&sbi, NO_INSERT);
720 53796579 : if (!slot)
721 : return NULL;
722 : else
723 44343039 : return (*slot)->pt_vars;
724 : }
725 :
726 : /* Add a bitmap to the shared bitmap hashtable. */
727 :
728 : static void
729 9453540 : shared_bitmap_add (bitmap pt_vars)
730 : {
731 9453540 : shared_bitmap_info **slot;
732 9453540 : shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
733 :
734 9453540 : sbi->pt_vars = pt_vars;
735 9453540 : sbi->hashcode = bitmap_hash (pt_vars);
736 :
737 9453540 : slot = shared_bitmap_table->find_slot (sbi, INSERT);
738 9453540 : gcc_assert (!*slot);
739 9453540 : *slot = sbi;
740 9453540 : }
741 :
742 : /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
743 :
744 : static void
745 53796579 : set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt,
746 : tree fndecl)
747 : {
748 53796579 : const varinfo_t escaped_vi = get_varinfo (var_rep[escaped_id]);
749 53796579 : const varinfo_t escaped_return_vi = get_varinfo (var_rep[escaped_return_id]);
750 53796579 : const bool everything_escaped
751 53796579 : = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id);
752 53796579 : const bool everything_escaped_return
753 53796579 : = escaped_return_vi->solution
754 53796579 : && bitmap_bit_p (escaped_return_vi->solution, anything_id);
755 53796579 : unsigned int i;
756 53796579 : bitmap_iterator bi;
757 :
758 291061950 : EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
759 : {
760 237265371 : varinfo_t vi = get_varinfo (i);
761 :
762 237265371 : if (vi->is_artificial_var)
763 100504259 : continue;
764 :
765 136761112 : if (everything_escaped
766 136761112 : || (escaped_vi->solution
767 136118431 : && bitmap_bit_p (escaped_vi->solution, i)))
768 : {
769 117134617 : pt->vars_contains_escaped = true;
770 117134617 : pt->vars_contains_escaped_heap |= vi->is_heap_var;
771 : }
772 :
773 136761112 : if (everything_escaped_return
774 136761112 : || (escaped_return_vi->solution
775 136725363 : && bitmap_bit_p (escaped_return_vi->solution, i)))
776 15016289 : pt->vars_contains_escaped_heap |= vi->is_heap_var;
777 :
778 136761112 : if (vi->is_restrict_var)
779 1861098 : pt->vars_contains_restrict = true;
780 :
781 136761112 : 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 134619438 : if (in_ipa_mode
788 134619438 : && !DECL_PT_UID_SET_P (vi->decl))
789 33384 : 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 134619438 : bitmap_set_bit (into, DECL_PT_UID (vi->decl));
794 134619438 : 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 134619438 : || (in_ipa_mode
805 274995 : && fndecl
806 249941 : && ! auto_var_in_fn_p (vi->decl, fndecl)))
807 75869480 : 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 134619438 : if (VAR_P (vi->decl)
813 134619438 : && auto_var_in_fn_p (vi->decl, fndecl))
814 53665735 : pt->vars_contains_auto = true;
815 :
816 : /* If we have a variable that is interposable record that fact
817 : for pointer comparison simplification. */
818 134619438 : if (VAR_P (vi->decl)
819 133992222 : && (TREE_STATIC (vi->decl) || DECL_EXTERNAL (vi->decl))
820 210342770 : && ! decl_binds_to_current_def_p (vi->decl))
821 56035946 : 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 134619438 : if (in_ipa_mode
827 334335 : && vi->shadow_var_uid != 0)
828 : {
829 206492 : bitmap_set_bit (into, vi->shadow_var_uid);
830 206492 : 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 1980294 : pt->vars_contains_nonlocal = true;
842 : }
843 : }
844 53796579 : }
845 :
846 :
847 : /* Compute the points-to solution *PT for the variable VI. */
848 :
849 : static struct pt_solution
850 62592617 : find_what_var_points_to (tree fndecl, varinfo_t orig_vi)
851 : {
852 62592617 : unsigned int i;
853 62592617 : bitmap_iterator bi;
854 62592617 : bitmap finished_solution;
855 62592617 : bitmap result;
856 62592617 : varinfo_t vi;
857 62592617 : struct pt_solution *pt;
858 :
859 : /* This variable may have been collapsed, let's get the real
860 : variable. */
861 62592617 : vi = get_varinfo (var_rep[orig_vi->id]);
862 :
863 : /* See if we have already computed the solution and return it. */
864 62592617 : pt_solution **slot = &final_solutions->get_or_insert (vi);
865 62592617 : if (*slot != NULL)
866 8203669 : return **slot;
867 :
868 54388948 : *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
869 54388948 : memset (pt, 0, sizeof (struct pt_solution));
870 :
871 : /* Translate artificial variables into points-to info
872 : attributes. */
873 295252273 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
874 : {
875 240863325 : varinfo_t vi = get_varinfo (i);
876 :
877 240863325 : if (vi->is_artificial_var && vi->id != nothing_id)
878 : {
879 : if (vi->id == escaped_id)
880 : {
881 39323610 : if (in_ipa_mode)
882 149845 : pt->ipa_escaped = 1;
883 : else
884 39173765 : pt->escaped = 1;
885 : /* Expand some special vars of ESCAPED in-place here. */
886 39323610 : varinfo_t evi = get_varinfo (var_rep[escaped_id]);
887 39323610 : if (bitmap_bit_p (evi->solution, nonlocal_id))
888 36647786 : pt->nonlocal = 1;
889 : }
890 : else if (vi->id == nonlocal_id)
891 44437927 : pt->nonlocal = 1;
892 : else if (vi->id == string_id)
893 7158257 : pt->const_pool = 1;
894 : else if (vi->id == anything_id
895 : || vi->id == integer_id)
896 592386 : pt->anything = 1;
897 : }
898 : }
899 :
900 : /* Instead of doing extra work, simply do not create
901 : elaborate points-to information for pt_anything pointers. */
902 54388948 : if (pt->anything)
903 592369 : return *pt;
904 :
905 : /* Share the final set of variables when possible. */
906 53796579 : finished_solution = BITMAP_GGC_ALLOC ();
907 53796579 : stats.points_to_sets_created++;
908 :
909 53796579 : set_uids_in_ptset (finished_solution, vi->solution, pt, fndecl);
910 53796579 : result = shared_bitmap_lookup (finished_solution);
911 53796579 : if (!result)
912 : {
913 9453540 : shared_bitmap_add (finished_solution);
914 9453540 : pt->vars = finished_solution;
915 : }
916 : else
917 : {
918 44343039 : pt->vars = result;
919 44343039 : bitmap_clear (finished_solution);
920 : }
921 :
922 53796579 : return *pt;
923 : }
924 :
925 : /* Given a pointer variable P, fill in its points-to set. */
926 :
927 : static void
928 24912444 : find_what_p_points_to (tree fndecl, tree p)
929 : {
930 24912444 : tree lookup_p = p;
931 24912444 : varinfo_t vi;
932 24912444 : prange vr;
933 49824888 : get_range_query (DECL_STRUCT_FUNCTION (fndecl))->range_of_expr (vr, p);
934 24912444 : bool nonnull = !vr.contains_zero_p ();
935 :
936 : /* For parameters, get at the points-to set for the actual parm
937 : decl. */
938 24912444 : if (TREE_CODE (p) == SSA_NAME
939 24912444 : && SSA_NAME_IS_DEFAULT_DEF (p)
940 30127490 : && (TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
941 954729 : || TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL))
942 4318306 : lookup_p = SSA_NAME_VAR (p);
943 :
944 24912444 : vi = lookup_vi_for_tree (lookup_p);
945 24912444 : if (!vi)
946 1037452 : return;
947 :
948 23874992 : pt_solution pt = find_what_var_points_to (fndecl, vi);
949 23874992 : set_ssa_name_pt_solution (p, pt);
950 : /* Preserve pointer nonnull globally computed. */
951 23874992 : if (nonnull)
952 4704060 : set_ptr_nonnull (p);
953 24912444 : }
954 :
955 :
956 : /* Query statistics for points-to solutions. */
957 :
958 : static struct {
959 : unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
960 : unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
961 : unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
962 : unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
963 : } pta_stats;
964 :
965 : void
966 0 : dump_pta_stats (FILE *s)
967 : {
968 0 : fprintf (s, "\nPTA query stats:\n");
969 0 : fprintf (s, " pt_solution_includes: "
970 : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
971 : HOST_WIDE_INT_PRINT_DEC" queries\n",
972 : pta_stats.pt_solution_includes_no_alias,
973 0 : pta_stats.pt_solution_includes_no_alias
974 0 : + pta_stats.pt_solution_includes_may_alias);
975 0 : fprintf (s, " pt_solutions_intersect: "
976 : HOST_WIDE_INT_PRINT_DEC" disambiguations, "
977 : HOST_WIDE_INT_PRINT_DEC" queries\n",
978 : pta_stats.pt_solutions_intersect_no_alias,
979 0 : pta_stats.pt_solutions_intersect_no_alias
980 0 : + pta_stats.pt_solutions_intersect_may_alias);
981 0 : }
982 :
983 :
984 : /* Reset the points-to solution *PT to a conservative default
985 : (point to anything). */
986 :
987 : void
988 69843066 : pt_solution_reset (struct pt_solution *pt)
989 : {
990 69843066 : memset (pt, 0, sizeof (struct pt_solution));
991 69843066 : pt->anything = true;
992 69843066 : }
993 :
994 : /* Set the points-to solution *PT to point only to the variables
995 : in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
996 : global variables and VARS_CONTAINS_RESTRICT specifies whether
997 : it contains restrict tag variables. */
998 :
999 : void
1000 72380 : pt_solution_set (struct pt_solution *pt, bitmap vars,
1001 : bool vars_contains_nonlocal)
1002 : {
1003 72380 : memset (pt, 0, sizeof (struct pt_solution));
1004 72380 : pt->vars = vars;
1005 72380 : pt->vars_contains_nonlocal = vars_contains_nonlocal;
1006 72380 : pt->vars_contains_escaped
1007 144760 : = (cfun->gimple_df->escaped.anything
1008 72380 : || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars));
1009 72380 : }
1010 :
1011 : /* Set the points-to solution *PT to point only to the variable VAR. */
1012 :
1013 : void
1014 215654 : pt_solution_set_var (struct pt_solution *pt, tree var)
1015 : {
1016 215654 : memset (pt, 0, sizeof (struct pt_solution));
1017 215654 : pt->vars = BITMAP_GGC_ALLOC ();
1018 215654 : bitmap_set_bit (pt->vars, DECL_PT_UID (var));
1019 215654 : pt->vars_contains_nonlocal = is_global_var (var);
1020 215654 : pt->vars_contains_escaped
1021 431308 : = (cfun->gimple_df->escaped.anything
1022 215654 : || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var)));
1023 215654 : }
1024 :
1025 : /* Computes the union of the points-to solutions *DEST and *SRC and
1026 : stores the result in *DEST. This changes the points-to bitmap
1027 : of *DEST and thus may not be used if that might be shared.
1028 : The points-to bitmap of *SRC and *DEST will not be shared after
1029 : this function if they were not before. */
1030 :
1031 : static void
1032 36 : pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src)
1033 : {
1034 36 : dest->anything |= src->anything;
1035 36 : if (dest->anything)
1036 : {
1037 2 : pt_solution_reset (dest);
1038 2 : return;
1039 : }
1040 :
1041 34 : dest->nonlocal |= src->nonlocal;
1042 34 : dest->escaped |= src->escaped;
1043 34 : dest->ipa_escaped |= src->ipa_escaped;
1044 34 : dest->const_pool |= src->const_pool ;
1045 34 : dest->vars_contains_nonlocal |= src->vars_contains_nonlocal;
1046 34 : dest->vars_contains_escaped |= src->vars_contains_escaped;
1047 34 : dest->vars_contains_escaped_heap |= src->vars_contains_escaped_heap;
1048 34 : if (!src->vars)
1049 : return;
1050 :
1051 34 : if (!dest->vars)
1052 20 : dest->vars = BITMAP_GGC_ALLOC ();
1053 34 : bitmap_ior_into (dest->vars, src->vars);
1054 : }
1055 :
1056 : /* Return true if the points-to solution *PT is empty. */
1057 :
1058 : bool
1059 11460 : pt_solution_empty_p (const pt_solution *pt)
1060 : {
1061 11460 : if (pt->anything
1062 8112 : || pt->nonlocal)
1063 : return false;
1064 :
1065 204 : if (pt->vars
1066 204 : && !bitmap_empty_p (pt->vars))
1067 : return false;
1068 :
1069 : /* If the solution includes ESCAPED, check if that is empty. */
1070 202 : if (pt->escaped
1071 202 : && !pt_solution_empty_p (&cfun->gimple_df->escaped))
1072 : return false;
1073 :
1074 : /* If the solution includes ESCAPED, check if that is empty. */
1075 202 : if (pt->ipa_escaped
1076 202 : && !pt_solution_empty_p (&ipa_escaped_pt))
1077 : return false;
1078 :
1079 : return true;
1080 : }
1081 :
1082 : /* Return true if the points-to solution *PT only point to a single var, and
1083 : return the var uid in *UID. */
1084 :
1085 : bool
1086 903820 : pt_solution_singleton_or_null_p (const pt_solution *pt, unsigned *uid)
1087 : {
1088 900530 : if (pt->anything || pt->nonlocal || pt->escaped || pt->ipa_escaped
1089 233334 : || pt->vars == NULL
1090 1137154 : || !bitmap_single_bit_set_p (pt->vars))
1091 : return false;
1092 :
1093 224954 : *uid = bitmap_first_set_bit (pt->vars);
1094 224954 : return true;
1095 : }
1096 :
1097 : /* Return true if the points-to solution *PT includes global memory.
1098 : If ESCAPED_LOCAL_P is true then escaped local variables are also
1099 : considered global. */
1100 :
1101 : bool
1102 47008597 : pt_solution_includes_global (const pt_solution *pt, bool escaped_local_p)
1103 : {
1104 47008597 : if (pt->anything
1105 46685383 : || pt->nonlocal
1106 11378181 : || pt->vars_contains_nonlocal
1107 : /* The following is a hack to make the malloc escape hack work.
1108 : In reality we'd need different sets for escaped-through-return
1109 : and escaped-to-callees and passes would need to be updated. */
1110 4500778 : || pt->vars_contains_escaped_heap)
1111 : return true;
1112 :
1113 2172231 : if (escaped_local_p && pt->vars_contains_escaped)
1114 : return true;
1115 :
1116 : /* 'escaped' is also a placeholder so we have to look into it. */
1117 2171680 : if (pt->escaped)
1118 0 : return pt_solution_includes_global (&cfun->gimple_df->escaped,
1119 0 : escaped_local_p);
1120 :
1121 2171680 : if (pt->ipa_escaped)
1122 : return pt_solution_includes_global (&ipa_escaped_pt,
1123 : escaped_local_p);
1124 :
1125 : return false;
1126 : }
1127 :
1128 : /* Return true if the points-to solution *PT includes local automatic
1129 : storage. */
1130 :
1131 : bool
1132 0 : pt_solution_includes_auto (const pt_solution *pt)
1133 : {
1134 0 : if (pt->anything
1135 0 : || pt->vars_contains_auto)
1136 : return true;
1137 :
1138 : /* 'escaped' is also a placeholder so we have to look into it. */
1139 0 : if (pt->escaped)
1140 0 : return pt_solution_includes_auto (&cfun->gimple_df->escaped);
1141 :
1142 0 : if (pt->ipa_escaped)
1143 : return pt_solution_includes_auto (&ipa_escaped_pt);
1144 :
1145 : return false;
1146 : }
1147 :
1148 :
1149 : /* Return true if the points-to solution *PT includes the variable
1150 : declaration DECL. */
1151 :
1152 : static bool
1153 278538729 : pt_solution_includes_1 (const pt_solution *pt, const_tree decl)
1154 : {
1155 280450629 : if (pt->anything)
1156 : return true;
1157 :
1158 274299470 : if (pt->nonlocal
1159 274299470 : && is_global_var (decl))
1160 : return true;
1161 :
1162 253808641 : if (pt->vars
1163 253808641 : && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
1164 : return true;
1165 :
1166 : /* If the solution includes ESCAPED, check it. */
1167 201620765 : if (pt->escaped
1168 201620765 : && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
1169 : return true;
1170 :
1171 : /* If the solution includes ESCAPED, check it. */
1172 169939112 : if (pt->ipa_escaped
1173 169939112 : && pt_solution_includes_1 (&ipa_escaped_pt, decl))
1174 : return true;
1175 :
1176 : return false;
1177 : }
1178 :
1179 : bool
1180 183860011 : pt_solution_includes (const pt_solution *pt, const_tree decl)
1181 : {
1182 183860011 : bool res = pt_solution_includes_1 (pt, decl);
1183 183860011 : if (res)
1184 78829864 : ++pta_stats.pt_solution_includes_may_alias;
1185 : else
1186 105030147 : ++pta_stats.pt_solution_includes_no_alias;
1187 183860011 : return res;
1188 : }
1189 :
1190 : /* Return true if the points-to solution *PT contains a reference to a
1191 : constant pool entry. */
1192 :
1193 : bool
1194 8045360 : pt_solution_includes_const_pool (const pt_solution *pt)
1195 : {
1196 8045360 : return (pt->const_pool
1197 7979888 : || pt->nonlocal
1198 334304 : || (pt->escaped && (!cfun || cfun->gimple_df->escaped.const_pool))
1199 8379664 : || (pt->ipa_escaped && ipa_escaped_pt.const_pool));
1200 : }
1201 :
1202 : /* Return true if both points-to solutions PT1 and PT2 have a non-empty
1203 : intersection. */
1204 :
1205 : static bool
1206 91965558 : pt_solutions_intersect_1 (const pt_solution *pt1, const pt_solution *pt2)
1207 : {
1208 91965558 : if (pt1->anything || pt2->anything)
1209 : return true;
1210 :
1211 : /* If either points to unknown global memory and the other points to
1212 : any global memory they alias. */
1213 91200358 : if ((pt1->nonlocal
1214 59312953 : && (pt2->nonlocal
1215 13113267 : || pt2->vars_contains_nonlocal))
1216 43153869 : || (pt2->nonlocal
1217 9627247 : && pt1->vars_contains_nonlocal))
1218 : return true;
1219 :
1220 : /* If either points to all escaped memory and the other points to
1221 : any escaped memory they alias. */
1222 42736066 : if ((pt1->escaped
1223 8137464 : && (pt2->escaped
1224 8137464 : || pt2->vars_contains_escaped))
1225 39332447 : || (pt2->escaped
1226 7503038 : && pt1->vars_contains_escaped))
1227 : return true;
1228 :
1229 : /* Check the escaped solution if required.
1230 : ??? Do we need to check the local against the IPA escaped sets? */
1231 37526953 : if ((pt1->ipa_escaped || pt2->ipa_escaped)
1232 37537461 : && !pt_solution_empty_p (&ipa_escaped_pt))
1233 : {
1234 : /* If both point to escaped memory and that solution
1235 : is not empty they alias. */
1236 10500 : if (pt1->ipa_escaped && pt2->ipa_escaped)
1237 : return true;
1238 :
1239 : /* If either points to escaped memory see if the escaped solution
1240 : intersects with the other. */
1241 10500 : if ((pt1->ipa_escaped
1242 1261 : && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
1243 10702 : || (pt2->ipa_escaped
1244 9239 : && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
1245 : return true;
1246 : }
1247 :
1248 : /* Now both pointers alias if their points-to solution intersects. */
1249 37518308 : return (pt1->vars
1250 37518292 : && pt2->vars
1251 75036600 : && bitmap_intersect_p (pt1->vars, pt2->vars));
1252 : }
1253 :
1254 : bool
1255 91955058 : pt_solutions_intersect (const pt_solution *pt1, const pt_solution *pt2)
1256 : {
1257 91955058 : bool res = pt_solutions_intersect_1 (pt1, pt2);
1258 91955058 : if (res)
1259 60474699 : ++pta_stats.pt_solutions_intersect_may_alias;
1260 : else
1261 31480359 : ++pta_stats.pt_solutions_intersect_no_alias;
1262 91955058 : return res;
1263 : }
1264 :
1265 :
1266 : /* Initialize things necessary to perform PTA. */
1267 :
1268 : static void
1269 4568954 : init_alias_vars (void)
1270 : {
1271 4568954 : use_field_sensitive = (param_max_fields_for_field_sensitive > 1);
1272 :
1273 4568954 : bitmap_obstack_initialize (&pta_obstack);
1274 4568954 : bitmap_obstack_initialize (&oldpta_obstack);
1275 :
1276 4568954 : constraints.create (8);
1277 4568954 : varmap.create (8);
1278 :
1279 4568954 : memset (&stats, 0, sizeof (stats));
1280 4568954 : shared_bitmap_table = new hash_table<shared_bitmap_hasher> (511);
1281 :
1282 4568954 : final_solutions = new hash_map<varinfo_t, pt_solution *>;
1283 4568954 : gcc_obstack_init (&final_solutions_obstack);
1284 :
1285 4568954 : init_constraint_builder ();
1286 4568954 : }
1287 :
1288 : /* Create points-to sets for the current function. See the comments
1289 : at the start of the file for an algorithmic overview. */
1290 :
1291 : static void
1292 4564459 : compute_points_to_sets (void)
1293 : {
1294 4564459 : basic_block bb;
1295 4564459 : varinfo_t vi;
1296 :
1297 4564459 : timevar_push (TV_TREE_PTA);
1298 :
1299 4564459 : init_alias_vars ();
1300 :
1301 4564459 : intra_build_constraints ();
1302 :
1303 : /* From the constraints compute the points-to sets. */
1304 4564459 : solve_constraints ();
1305 :
1306 4564459 : if (dump_file && (dump_flags & TDF_STATS))
1307 150 : dump_sa_stats (dump_file);
1308 :
1309 4564459 : if (dump_file && (dump_flags & TDF_DETAILS))
1310 283 : dump_sa_points_to_info (dump_file);
1311 :
1312 : /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
1313 4564459 : cfun->gimple_df->escaped = find_what_var_points_to (cfun->decl,
1314 : get_varinfo (escaped_id));
1315 :
1316 : /* Make sure the ESCAPED solution (which is used as placeholder in
1317 : other solutions) does not reference itself. This simplifies
1318 : points-to solution queries. */
1319 4564459 : cfun->gimple_df->escaped.escaped = 0;
1320 :
1321 : /* The ESCAPED_RETURN solution is what contains all memory that needs
1322 : to be considered global. */
1323 4564459 : cfun->gimple_df->escaped_return
1324 4564459 : = find_what_var_points_to (cfun->decl, get_varinfo (escaped_return_id));
1325 4564459 : cfun->gimple_df->escaped_return.escaped = 1;
1326 :
1327 : /* Compute the points-to sets for pointer SSA_NAMEs. */
1328 4564459 : unsigned i;
1329 4564459 : tree ptr;
1330 :
1331 169010817 : FOR_EACH_SSA_NAME (i, ptr, cfun)
1332 : {
1333 129064132 : if (POINTER_TYPE_P (TREE_TYPE (ptr)))
1334 24803964 : find_what_p_points_to (cfun->decl, ptr);
1335 : }
1336 :
1337 : /* Compute the call-used/clobbered sets. */
1338 40602741 : FOR_EACH_BB_FN (bb, cfun)
1339 : {
1340 36038282 : gimple_stmt_iterator gsi;
1341 :
1342 339440021 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1343 : {
1344 267363457 : gcall *stmt;
1345 267363457 : struct pt_solution *pt;
1346 :
1347 267363457 : stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
1348 267363457 : if (!stmt)
1349 249174099 : continue;
1350 :
1351 18189358 : pt = gimple_call_use_set (stmt);
1352 18189358 : if (gimple_call_flags (stmt) & ECF_CONST)
1353 1888509 : memset (pt, 0, sizeof (struct pt_solution));
1354 : else
1355 : {
1356 16300849 : bool uses_global_memory = true;
1357 16300849 : bool reads_global_memory = true;
1358 :
1359 16300849 : determine_global_memory_access (stmt, NULL,
1360 : &reads_global_memory,
1361 : &uses_global_memory);
1362 16300849 : if ((vi = lookup_call_use_vi (stmt)) != NULL)
1363 : {
1364 15341841 : *pt = find_what_var_points_to (cfun->decl, vi);
1365 : /* Escaped (and thus nonlocal) variables are always
1366 : implicitly used by calls. */
1367 : /* ??? ESCAPED can be empty even though NONLOCAL
1368 : always escaped. */
1369 15341841 : if (uses_global_memory)
1370 : {
1371 13799681 : pt->nonlocal = 1;
1372 13799681 : pt->escaped = 1;
1373 : }
1374 : }
1375 959008 : else if (uses_global_memory)
1376 : {
1377 : /* If there is nothing special about this call then
1378 : we have made everything that is used also escape. */
1379 1952 : *pt = cfun->gimple_df->escaped;
1380 1952 : pt->nonlocal = 1;
1381 : }
1382 : else
1383 957056 : memset (pt, 0, sizeof (struct pt_solution));
1384 : }
1385 :
1386 18189358 : pt = gimple_call_clobber_set (stmt);
1387 18189358 : if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
1388 3157154 : memset (pt, 0, sizeof (struct pt_solution));
1389 : else
1390 : {
1391 15032204 : bool writes_global_memory = true;
1392 :
1393 15032204 : determine_global_memory_access (stmt, &writes_global_memory,
1394 : NULL, NULL);
1395 :
1396 15032204 : if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
1397 : {
1398 14090852 : *pt = find_what_var_points_to (cfun->decl, vi);
1399 : /* Escaped (and thus nonlocal) variables are always
1400 : implicitly clobbered by calls. */
1401 : /* ??? ESCAPED can be empty even though NONLOCAL
1402 : always escaped. */
1403 14090852 : if (writes_global_memory)
1404 : {
1405 13237145 : pt->nonlocal = 1;
1406 13237145 : pt->escaped = 1;
1407 : }
1408 : }
1409 941352 : else if (writes_global_memory)
1410 : {
1411 : /* If there is nothing special about this call then
1412 : we have made everything that is used also escape. */
1413 0 : *pt = cfun->gimple_df->escaped;
1414 0 : pt->nonlocal = 1;
1415 : }
1416 : else
1417 941352 : memset (pt, 0, sizeof (struct pt_solution));
1418 : }
1419 : }
1420 : }
1421 :
1422 4564459 : timevar_pop (TV_TREE_PTA);
1423 4564459 : }
1424 :
1425 : /* Delete created points-to sets. */
1426 :
1427 : static void
1428 4568954 : delete_points_to_sets (void)
1429 : {
1430 4568954 : delete shared_bitmap_table;
1431 4568954 : shared_bitmap_table = NULL;
1432 4568954 : if (dump_file && (dump_flags & TDF_STATS))
1433 150 : fprintf (dump_file, "Points to sets created:%d\n",
1434 : stats.points_to_sets_created);
1435 :
1436 4568954 : bitmap_obstack_release (&pta_obstack);
1437 4568954 : constraints.release ();
1438 :
1439 4568954 : free (var_rep);
1440 :
1441 4568954 : varmap.release ();
1442 4568954 : variable_info_pool.release ();
1443 :
1444 9137908 : delete final_solutions;
1445 4568954 : obstack_free (&final_solutions_obstack, NULL);
1446 :
1447 4568954 : delete_constraint_builder ();
1448 4568954 : }
1449 :
1450 :
1451 : struct vls_data
1452 : {
1453 : unsigned short clique;
1454 : bool escaped_p;
1455 : bitmap rvars;
1456 : };
1457 :
1458 : /* Mark "other" loads and stores as belonging to CLIQUE and with
1459 : base zero. */
1460 :
1461 : static bool
1462 4260293 : visit_loadstore (gimple *, tree base, tree ref, void *data)
1463 : {
1464 4260293 : unsigned short clique = ((vls_data *) data)->clique;
1465 4260293 : bitmap rvars = ((vls_data *) data)->rvars;
1466 4260293 : bool escaped_p = ((vls_data *) data)->escaped_p;
1467 4260293 : if (TREE_CODE (base) == MEM_REF
1468 4260293 : || TREE_CODE (base) == TARGET_MEM_REF)
1469 : {
1470 3004280 : tree ptr = TREE_OPERAND (base, 0);
1471 3004280 : if (TREE_CODE (ptr) == SSA_NAME)
1472 : {
1473 : /* For parameters, get at the points-to set for the actual parm
1474 : decl. */
1475 2840057 : if (SSA_NAME_IS_DEFAULT_DEF (ptr)
1476 2840057 : && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
1477 0 : || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
1478 1900273 : ptr = SSA_NAME_VAR (ptr);
1479 :
1480 : /* We need to make sure 'ptr' doesn't include any of
1481 : the restrict tags we added bases for in its points-to set. */
1482 2840057 : varinfo_t vi = lookup_vi_for_tree (ptr);
1483 2840057 : if (! vi)
1484 : return false;
1485 :
1486 2840057 : vi = get_varinfo (var_rep[vi->id]);
1487 2840057 : if (bitmap_intersect_p (rvars, vi->solution)
1488 2840057 : || (escaped_p && bitmap_bit_p (vi->solution, escaped_id)))
1489 : return false;
1490 : }
1491 :
1492 : /* Do not overwrite existing cliques (that includes clique, base
1493 : pairs we just set). */
1494 1082699 : if (MR_DEPENDENCE_CLIQUE (base) == 0)
1495 : {
1496 975027 : MR_DEPENDENCE_CLIQUE (base) = clique;
1497 975027 : MR_DEPENDENCE_BASE (base) = 0;
1498 : }
1499 : }
1500 :
1501 : /* For plain decl accesses see whether they are accesses to globals
1502 : and rewrite them to MEM_REFs with { clique, 0 }. */
1503 2338712 : if (VAR_P (base)
1504 1221222 : && is_global_var (base)
1505 : /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
1506 : ops callback. */
1507 2399791 : && base != ref)
1508 : {
1509 : tree *basep = &ref;
1510 92471 : while (handled_component_p (*basep))
1511 58580 : basep = &TREE_OPERAND (*basep, 0);
1512 33891 : gcc_assert (VAR_P (*basep));
1513 33891 : tree ptr = build_fold_addr_expr (*basep);
1514 33891 : tree zero = build_int_cst (TREE_TYPE (ptr), 0);
1515 33891 : *basep = build2 (MEM_REF, TREE_TYPE (*basep), ptr, zero);
1516 33891 : MR_DEPENDENCE_CLIQUE (*basep) = clique;
1517 33891 : MR_DEPENDENCE_BASE (*basep) = 0;
1518 : }
1519 :
1520 : return false;
1521 : }
1522 :
1523 : struct msdi_data {
1524 : tree ptr;
1525 : unsigned short *clique;
1526 : unsigned short *last_ruid;
1527 : varinfo_t restrict_var;
1528 : };
1529 :
1530 : /* If BASE is a MEM_REF then assign a clique, base pair to it, updating
1531 : CLIQUE, *RESTRICT_VAR and LAST_RUID as passed via DATA.
1532 : Return whether dependence info was assigned to BASE. */
1533 :
1534 : static bool
1535 2062047 : maybe_set_dependence_info (gimple *, tree base, tree, void *data)
1536 : {
1537 2062047 : tree ptr = ((msdi_data *)data)->ptr;
1538 2062047 : unsigned short &clique = *((msdi_data *)data)->clique;
1539 2062047 : unsigned short &last_ruid = *((msdi_data *)data)->last_ruid;
1540 2062047 : varinfo_t restrict_var = ((msdi_data *)data)->restrict_var;
1541 2062047 : if ((TREE_CODE (base) == MEM_REF
1542 2062047 : || TREE_CODE (base) == TARGET_MEM_REF)
1543 2062047 : && TREE_OPERAND (base, 0) == ptr)
1544 : {
1545 : /* Do not overwrite existing cliques. This avoids overwriting dependence
1546 : info inlined from a function with restrict parameters inlined
1547 : into a function with restrict parameters. This usually means we
1548 : prefer to be precise in innermost loops. */
1549 1932207 : if (MR_DEPENDENCE_CLIQUE (base) == 0)
1550 : {
1551 1587896 : if (clique == 0)
1552 : {
1553 320663 : if (cfun->last_clique == 0)
1554 160179 : cfun->last_clique = 1;
1555 320663 : clique = 1;
1556 : }
1557 1587896 : if (restrict_var->ruid == 0)
1558 417289 : restrict_var->ruid = ++last_ruid;
1559 1587896 : MR_DEPENDENCE_CLIQUE (base) = clique;
1560 1587896 : MR_DEPENDENCE_BASE (base) = restrict_var->ruid;
1561 1587896 : return true;
1562 : }
1563 : }
1564 : return false;
1565 : }
1566 :
1567 : /* Clear dependence info for the clique DATA. */
1568 :
1569 : static bool
1570 17880502 : clear_dependence_clique (gimple *, tree base, tree, void *data)
1571 : {
1572 17880502 : unsigned short clique = (uintptr_t)data;
1573 17880502 : if ((TREE_CODE (base) == MEM_REF
1574 17880502 : || TREE_CODE (base) == TARGET_MEM_REF)
1575 17880502 : && MR_DEPENDENCE_CLIQUE (base) == clique)
1576 : {
1577 1188392 : MR_DEPENDENCE_CLIQUE (base) = 0;
1578 1188392 : MR_DEPENDENCE_BASE (base) = 0;
1579 : }
1580 :
1581 17880502 : return false;
1582 : }
1583 :
1584 : /* Compute the set of independent memory references based on restrict
1585 : tags and their conservative propagation to the points-to sets. */
1586 :
1587 : static void
1588 4564459 : compute_dependence_clique (void)
1589 : {
1590 : /* First clear the special "local" clique. */
1591 4564459 : basic_block bb;
1592 4564459 : if (cfun->last_clique != 0)
1593 10855250 : FOR_EACH_BB_FN (bb, cfun)
1594 20644520 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
1595 147353874 : !gsi_end_p (gsi); gsi_next (&gsi))
1596 : {
1597 137031614 : gimple *stmt = gsi_stmt (gsi);
1598 137031614 : walk_stmt_load_store_ops (stmt, (void *)(uintptr_t) 1,
1599 : clear_dependence_clique,
1600 : clear_dependence_clique);
1601 : }
1602 :
1603 4564459 : unsigned short clique = 0;
1604 4564459 : unsigned short last_ruid = 0;
1605 4564459 : bitmap rvars = BITMAP_ALLOC (NULL);
1606 4564459 : bool escaped_p = false;
1607 178139735 : for (unsigned i = 0; i < num_ssa_names; ++i)
1608 : {
1609 169010817 : tree ptr = ssa_name (i);
1610 169010817 : if (!ptr || !POINTER_TYPE_P (TREE_TYPE (ptr)))
1611 145244113 : continue;
1612 :
1613 : /* Avoid all this when ptr is not dereferenced? */
1614 24803964 : tree p = ptr;
1615 24803964 : if (SSA_NAME_IS_DEFAULT_DEF (ptr)
1616 24803964 : && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
1617 954581 : || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
1618 4300027 : p = SSA_NAME_VAR (ptr);
1619 24803964 : varinfo_t vi = lookup_vi_for_tree (p);
1620 24803964 : if (!vi)
1621 1037260 : continue;
1622 23766704 : vi = get_varinfo (var_rep[vi->id]);
1623 23766704 : bitmap_iterator bi;
1624 23766704 : unsigned j;
1625 23766704 : varinfo_t restrict_var = NULL;
1626 29216087 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
1627 : {
1628 27926717 : varinfo_t oi = get_varinfo (j);
1629 27926717 : if (oi->head != j)
1630 927736 : oi = get_varinfo (oi->head);
1631 27926717 : if (oi->is_restrict_var)
1632 : {
1633 1765463 : if (restrict_var
1634 1765463 : && restrict_var != oi)
1635 : {
1636 1659 : if (dump_file && (dump_flags & TDF_DETAILS))
1637 : {
1638 0 : fprintf (dump_file, "found restrict pointed-to "
1639 : "for ");
1640 0 : print_generic_expr (dump_file, ptr);
1641 0 : fprintf (dump_file, " but not exclusively\n");
1642 : }
1643 : restrict_var = NULL;
1644 : break;
1645 : }
1646 : restrict_var = oi;
1647 : }
1648 : /* NULL is the only other valid points-to entry. */
1649 26161254 : else if (oi->id != nothing_id)
1650 : {
1651 : restrict_var = NULL;
1652 : break;
1653 : }
1654 : }
1655 : /* Ok, found that ptr must(!) point to a single(!) restrict
1656 : variable. */
1657 : /* ??? PTA isn't really a proper propagation engine to compute
1658 : this property.
1659 : ??? We could handle merging of two restricts by unifying them. */
1660 23765045 : if (restrict_var)
1661 : {
1662 : /* Now look at possible dereferences of ptr. */
1663 847217 : imm_use_iterator ui;
1664 847217 : gimple *use_stmt;
1665 847217 : bool used = false;
1666 847217 : msdi_data data = { ptr, &clique, &last_ruid, restrict_var };
1667 3851452 : FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
1668 3004235 : used |= walk_stmt_load_store_ops (use_stmt, &data,
1669 : maybe_set_dependence_info,
1670 847217 : maybe_set_dependence_info);
1671 847217 : if (used)
1672 : {
1673 : /* Add all subvars to the set of restrict pointed-to set. */
1674 2365368 : for (unsigned sv = restrict_var->head; sv != 0;
1675 952983 : sv = get_varinfo (sv)->next)
1676 952983 : bitmap_set_bit (rvars, sv);
1677 459402 : varinfo_t escaped = get_varinfo (var_rep[escaped_id]);
1678 459402 : if (bitmap_bit_p (escaped->solution, restrict_var->id))
1679 847217 : escaped_p = true;
1680 : }
1681 : }
1682 : }
1683 :
1684 4564459 : if (clique != 0)
1685 : {
1686 : /* Assign the BASE id zero to all accesses not based on a restrict
1687 : pointer. That way they get disambiguated against restrict
1688 : accesses but not against each other. */
1689 : /* ??? For restricts derived from globals (thus not incoming
1690 : parameters) we can't restrict scoping properly thus the following
1691 : is too aggressive there. For now we have excluded those globals from
1692 : getting into the MR_DEPENDENCE machinery. */
1693 320663 : vls_data data = { clique, escaped_p, rvars };
1694 320663 : basic_block bb;
1695 2981355 : FOR_EACH_BB_FN (bb, cfun)
1696 5321384 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
1697 20922879 : !gsi_end_p (gsi); gsi_next (&gsi))
1698 : {
1699 18262187 : gimple *stmt = gsi_stmt (gsi);
1700 18262187 : walk_stmt_load_store_ops (stmt, &data,
1701 : visit_loadstore, visit_loadstore);
1702 : }
1703 : }
1704 :
1705 4564459 : BITMAP_FREE (rvars);
1706 4564459 : }
1707 :
1708 :
1709 : /* Compute points-to information for every SSA_NAME pointer in the
1710 : current function and compute the transitive closure of escaped
1711 : variables to re-initialize the call-clobber states of local variables. */
1712 :
1713 : unsigned int
1714 4591589 : compute_may_aliases (void)
1715 : {
1716 4591589 : if (cfun->gimple_df->ipa_pta)
1717 : {
1718 27130 : if (dump_file)
1719 : {
1720 0 : fprintf (dump_file, "\nNot re-computing points-to information "
1721 : "because IPA points-to information is available.\n\n");
1722 :
1723 : /* But still dump what we have remaining it. */
1724 0 : if (dump_flags & (TDF_DETAILS|TDF_ALIAS))
1725 0 : dump_alias_info (dump_file);
1726 : }
1727 :
1728 : return 0;
1729 : }
1730 :
1731 : /* For each pointer P_i, determine the sets of variables that P_i may
1732 : point-to. Compute the reachability set of escaped and call-used
1733 : variables. */
1734 4564459 : compute_points_to_sets ();
1735 :
1736 : /* Debugging dumps. */
1737 4564459 : if (dump_file && (dump_flags & (TDF_DETAILS|TDF_ALIAS)))
1738 283 : dump_alias_info (dump_file);
1739 :
1740 : /* Compute restrict-based memory disambiguations. */
1741 4564459 : compute_dependence_clique ();
1742 :
1743 : /* Deallocate memory used by aliasing data structures and the internal
1744 : points-to solution. */
1745 4564459 : delete_points_to_sets ();
1746 :
1747 4564459 : gcc_assert (!need_ssa_update_p (cfun));
1748 :
1749 : return 0;
1750 : }
1751 :
1752 : /* A dummy pass to cause points-to information to be computed via
1753 : TODO_rebuild_alias. */
1754 :
1755 : namespace {
1756 :
1757 : const pass_data pass_data_build_alias =
1758 : {
1759 : GIMPLE_PASS, /* type */
1760 : "alias", /* name */
1761 : OPTGROUP_NONE, /* optinfo_flags */
1762 : TV_NONE, /* tv_id */
1763 : ( PROP_cfg | PROP_ssa ), /* properties_required */
1764 : 0, /* properties_provided */
1765 : 0, /* properties_destroyed */
1766 : 0, /* todo_flags_start */
1767 : TODO_rebuild_alias, /* todo_flags_finish */
1768 : };
1769 :
1770 : class pass_build_alias : public gimple_opt_pass
1771 : {
1772 : public:
1773 297180 : pass_build_alias (gcc::context *ctxt)
1774 594360 : : gimple_opt_pass (pass_data_build_alias, ctxt)
1775 : {}
1776 :
1777 : /* opt_pass methods: */
1778 1063018 : bool gate (function *) final override { return flag_tree_pta; }
1779 :
1780 : }; // class pass_build_alias
1781 :
1782 : } // anon namespace
1783 :
1784 : gimple_opt_pass *
1785 297180 : make_pass_build_alias (gcc::context *ctxt)
1786 : {
1787 297180 : return new pass_build_alias (ctxt);
1788 : }
1789 :
1790 : /* A dummy pass to cause points-to information to be computed via
1791 : TODO_rebuild_alias. */
1792 :
1793 : namespace {
1794 :
1795 : const pass_data pass_data_build_ealias =
1796 : {
1797 : GIMPLE_PASS, /* type */
1798 : "ealias", /* name */
1799 : OPTGROUP_NONE, /* optinfo_flags */
1800 : TV_NONE, /* tv_id */
1801 : ( PROP_cfg | PROP_ssa ), /* properties_required */
1802 : 0, /* properties_provided */
1803 : 0, /* properties_destroyed */
1804 : 0, /* todo_flags_start */
1805 : TODO_rebuild_alias, /* todo_flags_finish */
1806 : };
1807 :
1808 : class pass_build_ealias : public gimple_opt_pass
1809 : {
1810 : public:
1811 297180 : pass_build_ealias (gcc::context *ctxt)
1812 594360 : : gimple_opt_pass (pass_data_build_ealias, ctxt)
1813 : {}
1814 :
1815 : /* opt_pass methods: */
1816 2524717 : bool gate (function *) final override { return flag_tree_pta; }
1817 :
1818 : }; // class pass_build_ealias
1819 :
1820 : } // anon namespace
1821 :
1822 : gimple_opt_pass *
1823 297180 : make_pass_build_ealias (gcc::context *ctxt)
1824 : {
1825 297180 : return new pass_build_ealias (ctxt);
1826 : }
1827 :
1828 :
1829 : /* IPA PTA solutions for ESCAPED. */
1830 : struct pt_solution ipa_escaped_pt
1831 : = { true, false, false, false, false,
1832 : false, false, false, false, false, false, NULL };
1833 :
1834 :
1835 : /* Execute the driver for IPA PTA. */
1836 : static unsigned int
1837 4495 : ipa_pta_execute (void)
1838 : {
1839 4495 : struct cgraph_node *node;
1840 :
1841 4495 : in_ipa_mode = 1;
1842 :
1843 4495 : init_alias_vars ();
1844 :
1845 4495 : if (dump_file && (dump_flags & TDF_DETAILS))
1846 : {
1847 18 : symtab->dump (dump_file);
1848 18 : fprintf (dump_file, "\n");
1849 : }
1850 :
1851 4495 : if (dump_file && (dump_flags & TDF_DETAILS))
1852 : {
1853 18 : fprintf (dump_file, "Generating generic constraints\n\n");
1854 18 : dump_constraints (dump_file, 0);
1855 18 : fprintf (dump_file, "\n");
1856 : }
1857 :
1858 4495 : ipa_build_constraints ();
1859 :
1860 : /* From the constraints compute the points-to sets. */
1861 4495 : solve_constraints ();
1862 :
1863 4495 : if (dump_file && (dump_flags & TDF_STATS))
1864 0 : dump_sa_stats (dump_file);
1865 :
1866 4495 : if (dump_file && (dump_flags & TDF_DETAILS))
1867 18 : dump_sa_points_to_info (dump_file);
1868 :
1869 : /* Now post-process solutions to handle locals from different
1870 : runtime instantiations coming in through recursive invocations. */
1871 4495 : unsigned shadow_var_cnt = 0;
1872 1226112 : for (unsigned i = 1; i < varmap.length (); ++i)
1873 : {
1874 1221617 : varinfo_t fi = get_varinfo (i);
1875 1221617 : if (fi->is_fn_info
1876 23885 : && fi->decl)
1877 : /* Automatic variables pointed to by their containing functions
1878 : parameters need this treatment. */
1879 23885 : for (varinfo_t ai = first_vi_for_offset (fi, fi_parm_base);
1880 49525 : ai; ai = vi_next (ai))
1881 : {
1882 25640 : varinfo_t vi = get_varinfo (var_rep[ai->id]);
1883 25640 : bitmap_iterator bi;
1884 25640 : unsigned j;
1885 69599 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
1886 : {
1887 43959 : varinfo_t pt = get_varinfo (j);
1888 43959 : if (pt->shadow_var_uid == 0
1889 42483 : && pt->decl
1890 60581 : && auto_var_in_fn_p (pt->decl, fi->decl))
1891 : {
1892 56 : pt->shadow_var_uid = allocate_decl_uid ();
1893 56 : shadow_var_cnt++;
1894 : }
1895 : }
1896 : }
1897 : /* As well as global variables which are another way of passing
1898 : arguments to recursive invocations. */
1899 1197732 : else if (fi->is_global_var)
1900 : {
1901 868123 : for (varinfo_t ai = fi; ai; ai = vi_next (ai))
1902 : {
1903 462578 : varinfo_t vi = get_varinfo (var_rep[ai->id]);
1904 462578 : bitmap_iterator bi;
1905 462578 : unsigned j;
1906 1882593 : EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
1907 : {
1908 1420015 : varinfo_t pt = get_varinfo (j);
1909 1420015 : if (pt->shadow_var_uid == 0
1910 1138024 : && pt->decl
1911 1577581 : && auto_var_p (pt->decl))
1912 : {
1913 40963 : pt->shadow_var_uid = allocate_decl_uid ();
1914 40963 : shadow_var_cnt++;
1915 : }
1916 : }
1917 : }
1918 : }
1919 : }
1920 4495 : if (shadow_var_cnt && dump_file && (dump_flags & TDF_DETAILS))
1921 11 : fprintf (dump_file, "Allocated %u shadow variables for locals "
1922 : "maybe leaking into recursive invocations of their containing "
1923 : "functions\n", shadow_var_cnt);
1924 :
1925 : /* Compute the global points-to sets for ESCAPED.
1926 : ??? Note that the computed escape set is not correct
1927 : for the whole unit as we fail to consider graph edges to
1928 : externally visible functions. */
1929 4495 : ipa_escaped_pt = find_what_var_points_to (NULL, get_varinfo (escaped_id));
1930 :
1931 : /* Make sure the ESCAPED solution (which is used as placeholder in
1932 : other solutions) does not reference itself. This simplifies
1933 : points-to solution queries. */
1934 4495 : ipa_escaped_pt.ipa_escaped = 0;
1935 :
1936 : /* Assign the points-to sets to the SSA names in the unit. */
1937 28433 : FOR_EACH_DEFINED_FUNCTION (node)
1938 : {
1939 23938 : tree ptr;
1940 23938 : struct function *fn;
1941 23938 : unsigned i;
1942 23938 : basic_block bb;
1943 :
1944 : /* Nodes without a body in this partition are not interesting. */
1945 23991 : if (!node->has_gimple_body_p ()
1946 23885 : || node->in_other_partition
1947 47823 : || node->clone_of)
1948 53 : continue;
1949 :
1950 23885 : fn = DECL_STRUCT_FUNCTION (node->decl);
1951 :
1952 : /* Compute the points-to sets for pointer SSA_NAMEs. */
1953 1166089 : FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr)
1954 : {
1955 1142204 : if (ptr
1956 1142204 : && POINTER_TYPE_P (TREE_TYPE (ptr)))
1957 108480 : find_what_p_points_to (node->decl, ptr);
1958 : }
1959 :
1960 : /* Compute the call-use and call-clobber sets for indirect calls
1961 : and calls to external functions. */
1962 363549 : FOR_EACH_BB_FN (bb, fn)
1963 : {
1964 339664 : gimple_stmt_iterator gsi;
1965 :
1966 1655483 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1967 : {
1968 976155 : gcall *stmt;
1969 976155 : struct pt_solution *pt;
1970 976155 : varinfo_t vi, fi;
1971 976155 : tree decl;
1972 :
1973 976155 : stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
1974 976155 : if (!stmt)
1975 714281 : continue;
1976 :
1977 : /* Handle direct calls to functions with body. */
1978 261874 : decl = gimple_call_fndecl (stmt);
1979 :
1980 261874 : {
1981 261874 : tree called_decl = NULL_TREE;
1982 261874 : if (gimple_call_builtin_p (stmt, BUILT_IN_GOMP_PARALLEL))
1983 13 : called_decl = TREE_OPERAND (gimple_call_arg (stmt, 0), 0);
1984 261861 : else if (gimple_call_builtin_p (stmt, BUILT_IN_GOACC_PARALLEL))
1985 14079 : called_decl = TREE_OPERAND (gimple_call_arg (stmt, 1), 0);
1986 :
1987 14092 : if (called_decl != NULL_TREE
1988 14092 : && !fndecl_maybe_in_other_partition (called_decl))
1989 : decl = called_decl;
1990 : }
1991 :
1992 261874 : if (decl
1993 80685 : && (fi = lookup_vi_for_tree (decl))
1994 339496 : && fi->is_fn_info)
1995 : {
1996 40340 : *gimple_call_clobber_set (stmt)
1997 20170 : = find_what_var_points_to
1998 20170 : (node->decl, first_vi_for_offset (fi, fi_clobbers));
1999 40340 : *gimple_call_use_set (stmt)
2000 20170 : = find_what_var_points_to
2001 20170 : (node->decl, first_vi_for_offset (fi, fi_uses));
2002 : }
2003 : /* Handle direct calls to external functions. */
2004 241704 : else if (decl && (!fi || fi->decl))
2005 : {
2006 60514 : pt = gimple_call_use_set (stmt);
2007 60514 : if (gimple_call_flags (stmt) & ECF_CONST)
2008 1516 : memset (pt, 0, sizeof (struct pt_solution));
2009 58998 : else if ((vi = lookup_call_use_vi (stmt)) != NULL)
2010 : {
2011 55664 : *pt = find_what_var_points_to (node->decl, vi);
2012 : /* Escaped (and thus nonlocal) variables are always
2013 : implicitly used by calls. */
2014 : /* ??? ESCAPED can be empty even though NONLOCAL
2015 : always escaped. */
2016 55664 : pt->nonlocal = 1;
2017 55664 : pt->ipa_escaped = 1;
2018 : }
2019 : else
2020 : {
2021 : /* If there is nothing special about this call then
2022 : we have made everything that is used also escape. */
2023 3334 : *pt = ipa_escaped_pt;
2024 3334 : pt->nonlocal = 1;
2025 : }
2026 :
2027 60514 : pt = gimple_call_clobber_set (stmt);
2028 60514 : if (gimple_call_flags (stmt) &
2029 : (ECF_CONST|ECF_PURE|ECF_NOVOPS))
2030 1717 : memset (pt, 0, sizeof (struct pt_solution));
2031 58797 : else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
2032 : {
2033 55479 : *pt = find_what_var_points_to (node->decl, vi);
2034 : /* Escaped (and thus nonlocal) variables are always
2035 : implicitly clobbered by calls. */
2036 : /* ??? ESCAPED can be empty even though NONLOCAL
2037 : always escaped. */
2038 55479 : pt->nonlocal = 1;
2039 55479 : pt->ipa_escaped = 1;
2040 : }
2041 : else
2042 : {
2043 : /* If there is nothing special about this call then
2044 : we have made everything that is used also escape. */
2045 3318 : *pt = ipa_escaped_pt;
2046 3318 : pt->nonlocal = 1;
2047 : }
2048 : }
2049 : /* Handle indirect calls. */
2050 181190 : else if ((fi = get_fi_for_callee (stmt)))
2051 : {
2052 : /* We need to accumulate all clobbers/uses of all possible
2053 : callees. */
2054 181190 : fi = get_varinfo (var_rep[fi->id]);
2055 : /* If we cannot constrain the set of functions we'll end up
2056 : calling we end up using/clobbering everything. */
2057 181190 : if (bitmap_bit_p (fi->solution, anything_id)
2058 678 : || bitmap_bit_p (fi->solution, nonlocal_id)
2059 181201 : || bitmap_bit_p (fi->solution, escaped_id))
2060 : {
2061 181179 : pt_solution_reset (gimple_call_clobber_set (stmt));
2062 181179 : pt_solution_reset (gimple_call_use_set (stmt));
2063 : }
2064 : else
2065 : {
2066 11 : bitmap_iterator bi;
2067 11 : unsigned i;
2068 11 : struct pt_solution *uses, *clobbers;
2069 :
2070 11 : uses = gimple_call_use_set (stmt);
2071 11 : clobbers = gimple_call_clobber_set (stmt);
2072 11 : memset (uses, 0, sizeof (struct pt_solution));
2073 11 : memset (clobbers, 0, sizeof (struct pt_solution));
2074 29 : EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi)
2075 : {
2076 18 : struct pt_solution sol;
2077 :
2078 18 : vi = get_varinfo (i);
2079 18 : if (!vi->is_fn_info)
2080 : {
2081 : /* ??? We could be more precise here? */
2082 0 : uses->nonlocal = 1;
2083 0 : uses->ipa_escaped = 1;
2084 0 : clobbers->nonlocal = 1;
2085 0 : clobbers->ipa_escaped = 1;
2086 0 : continue;
2087 : }
2088 :
2089 18 : if (!uses->anything)
2090 : {
2091 18 : sol = find_what_var_points_to
2092 18 : (node->decl,
2093 : first_vi_for_offset (vi, fi_uses));
2094 18 : pt_solution_ior_into (uses, &sol);
2095 : }
2096 18 : if (!clobbers->anything)
2097 : {
2098 18 : sol = find_what_var_points_to
2099 18 : (node->decl,
2100 : first_vi_for_offset (vi, fi_clobbers));
2101 18 : pt_solution_ior_into (clobbers, &sol);
2102 : }
2103 : }
2104 : }
2105 : }
2106 : else
2107 0 : gcc_unreachable ();
2108 : }
2109 : }
2110 :
2111 23885 : fn->gimple_df->ipa_pta = true;
2112 :
2113 : /* We have to re-set the final-solution cache after each function
2114 : because what is a "global" is dependent on function context. */
2115 23885 : final_solutions->empty ();
2116 23885 : obstack_free (&final_solutions_obstack, NULL);
2117 23885 : gcc_obstack_init (&final_solutions_obstack);
2118 : }
2119 :
2120 4495 : delete_points_to_sets ();
2121 :
2122 4495 : in_ipa_mode = 0;
2123 :
2124 4495 : return 0;
2125 : }
2126 :
2127 : namespace {
2128 :
2129 : const pass_data pass_data_ipa_pta =
2130 : {
2131 : SIMPLE_IPA_PASS, /* type */
2132 : "pta", /* name */
2133 : OPTGROUP_NONE, /* optinfo_flags */
2134 : TV_IPA_PTA, /* tv_id */
2135 : 0, /* properties_required */
2136 : 0, /* properties_provided */
2137 : 0, /* properties_destroyed */
2138 : 0, /* todo_flags_start */
2139 : 0, /* todo_flags_finish */
2140 : };
2141 :
2142 : class pass_ipa_pta : public simple_ipa_opt_pass
2143 : {
2144 : public:
2145 594360 : pass_ipa_pta (gcc::context *ctxt)
2146 1188720 : : simple_ipa_opt_pass (pass_data_ipa_pta, ctxt)
2147 : {}
2148 :
2149 : /* opt_pass methods: */
2150 241820 : bool gate (function *) final override
2151 : {
2152 241820 : return (optimize
2153 157477 : && flag_ipa_pta
2154 : /* Don't bother doing anything if the program has errors. */
2155 246315 : && !seen_error ());
2156 : }
2157 :
2158 297180 : opt_pass * clone () final override { return new pass_ipa_pta (m_ctxt); }
2159 :
2160 4495 : unsigned int execute (function *) final override
2161 : {
2162 4495 : return ipa_pta_execute ();
2163 : }
2164 :
2165 : }; // class pass_ipa_pta
2166 :
2167 : } // anon namespace
2168 :
2169 : simple_ipa_opt_pass *
2170 297180 : make_pass_ipa_pta (gcc::context *ctxt)
2171 : {
2172 297180 : return new pass_ipa_pta (ctxt);
2173 : }
|