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