1 /* Tree based points-to analysis
2 Copyright (C) 2005-2016 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 "params.h"
41 #include "gimple-walk.h"
42
43 /* The idea behind this analyzer is to generate set constraints from the
44 program, then solve the resulting constraints in order to generate the
45 points-to sets.
46
47 Set constraints are a way of modeling program analysis problems that
48 involve sets. They consist of an inclusion constraint language,
49 describing the variables (each variable is a set) and operations that
50 are involved on the variables, and a set of rules that derive facts
51 from these operations. To solve a system of set constraints, you derive
52 all possible facts under the rules, which gives you the correct sets
53 as a consequence.
54
55 See "Efficient Field-sensitive pointer analysis for C" by "David
56 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
57 http://citeseer.ist.psu.edu/pearce04efficient.html
58
59 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
60 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
61 http://citeseer.ist.psu.edu/heintze01ultrafast.html
62
63 There are three types of real constraint expressions, DEREF,
64 ADDRESSOF, and SCALAR. Each constraint expression consists
65 of a constraint type, a variable, and an offset.
66
67 SCALAR is a constraint expression type used to represent x, whether
68 it appears on the LHS or the RHS of a statement.
69 DEREF is a constraint expression type used to represent *x, whether
70 it appears on the LHS or the RHS of a statement.
71 ADDRESSOF is a constraint expression used to represent &x, whether
72 it appears on the LHS or the RHS of a statement.
73
74 Each pointer variable in the program is assigned an integer id, and
75 each field of a structure variable is assigned an integer id as well.
76
77 Structure variables are linked to their list of fields through a "next
78 field" in each variable that points to the next field in offset
79 order.
80 Each variable for a structure field has
81
82 1. "size", that tells the size in bits of that field.
83 2. "fullsize, that tells the size in bits of the entire structure.
84 3. "offset", that tells the offset in bits from the beginning of the
85 structure to this field.
86
87 Thus,
88 struct f
89 {
90 int a;
91 int b;
92 } foo;
93 int *bar;
94
95 looks like
96
97 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
98 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
99 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
100
101
102 In order to solve the system of set constraints, the following is
103 done:
104
105 1. Each constraint variable x has a solution set associated with it,
106 Sol(x).
107
108 2. Constraints are separated into direct, copy, and complex.
109 Direct constraints are ADDRESSOF constraints that require no extra
110 processing, such as P = &Q
111 Copy constraints are those of the form P = Q.
112 Complex constraints are all the constraints involving dereferences
113 and offsets (including offsetted copies).
114
115 3. All direct constraints of the form P = &Q are processed, such
116 that Q is added to Sol(P)
117
118 4. All complex constraints for a given constraint variable are stored in a
119 linked list attached to that variable's node.
120
121 5. A directed graph is built out of the copy constraints. Each
122 constraint variable is a node in the graph, and an edge from
123 Q to P is added for each copy constraint of the form P = Q
124
125 6. The graph is then walked, and solution sets are
126 propagated along the copy edges, such that an edge from Q to P
127 causes Sol(P) <- Sol(P) union Sol(Q).
128
129 7. As we visit each node, all complex constraints associated with
130 that node are processed by adding appropriate copy edges to the graph, or the
131 appropriate variables to the solution set.
132
133 8. The process of walking the graph is iterated until no solution
134 sets change.
135
136 Prior to walking the graph in steps 6 and 7, We perform static
137 cycle elimination on the constraint graph, as well
138 as off-line variable substitution.
139
140 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
141 on and turned into anything), but isn't. You can just see what offset
142 inside the pointed-to struct it's going to access.
143
144 TODO: Constant bounded arrays can be handled as if they were structs of the
145 same number of elements.
146
147 TODO: Modeling heap and incoming pointers becomes much better if we
148 add fields to them as we discover them, which we could do.
149
150 TODO: We could handle unions, but to be honest, it's probably not
151 worth the pain or slowdown. */
152
153 /* IPA-PTA optimizations possible.
154
155 When the indirect function called is ANYTHING we can add disambiguation
156 based on the function signatures (or simply the parameter count which
157 is the varinfo size). We also do not need to consider functions that
158 do not have their address taken.
159
160 The is_global_var bit which marks escape points is overly conservative
161 in IPA mode. Split it to is_escape_point and is_global_var - only
162 externally visible globals are escape points in IPA mode.
163 There is now is_ipa_escape_point but this is only used in a few
164 selected places.
165
166 The way we introduce DECL_PT_UID to avoid fixing up all points-to
167 sets in the translation unit when we copy a DECL during inlining
168 pessimizes precision. The advantage is that the DECL_PT_UID keeps
169 compile-time and memory usage overhead low - the points-to sets
170 do not grow or get unshared as they would during a fixup phase.
171 An alternative solution is to delay IPA PTA until after all
172 inlining transformations have been applied.
173
174 The way we propagate clobber/use information isn't optimized.
175 It should use a new complex constraint that properly filters
176 out local variables of the callee (though that would make
177 the sets invalid after inlining). OTOH we might as well
178 admit defeat to WHOPR and simply do all the clobber/use analysis
179 and propagation after PTA finished but before we threw away
180 points-to information for memory variables. WHOPR and PTA
181 do not play along well anyway - the whole constraint solving
182 would need to be done in WPA phase and it will be very interesting
183 to apply the results to local SSA names during LTRANS phase.
184
185 We probably should compute a per-function unit-ESCAPE solution
186 propagating it simply like the clobber / uses solutions. The
187 solution can go alongside the non-IPA espaced solution and be
188 used to query which vars escape the unit through a function.
189 This is also required to make the escaped-HEAP trick work in IPA mode.
190
191 We never put function decls in points-to sets so we do not
192 keep the set of called functions for indirect calls.
193
194 And probably more. */
195
196 static bool use_field_sensitive = true;
197 static int in_ipa_mode = 0;
198
199 /* Used for predecessor bitmaps. */
200 static bitmap_obstack predbitmap_obstack;
201
202 /* Used for points-to sets. */
203 static bitmap_obstack pta_obstack;
204
205 /* Used for oldsolution members of variables. */
206 static bitmap_obstack oldpta_obstack;
207
208 /* Used for per-solver-iteration bitmaps. */
209 static bitmap_obstack iteration_obstack;
210
211 static unsigned int create_variable_info_for (tree, const char *, bool);
212 typedef struct constraint_graph *constraint_graph_t;
213 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
214
215 struct constraint;
216 typedef struct constraint *constraint_t;
217
218
219 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
220 if (a) \
221 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
222
223 static struct constraint_stats
224 {
225 unsigned int total_vars;
226 unsigned int nonpointer_vars;
227 unsigned int unified_vars_static;
228 unsigned int unified_vars_dynamic;
229 unsigned int iterations;
230 unsigned int num_edges;
231 unsigned int num_implicit_edges;
232 unsigned int points_to_sets_created;
233 } stats;
234
235 struct variable_info
236 {
237 /* ID of this variable */
238 unsigned int id;
239
240 /* True if this is a variable created by the constraint analysis, such as
241 heap variables and constraints we had to break up. */
242 unsigned int is_artificial_var : 1;
243
244 /* True if this is a special variable whose solution set should not be
245 changed. */
246 unsigned int is_special_var : 1;
247
248 /* True for variables whose size is not known or variable. */
249 unsigned int is_unknown_size_var : 1;
250
251 /* True for (sub-)fields that represent a whole variable. */
252 unsigned int is_full_var : 1;
253
254 /* True if this is a heap variable. */
255 unsigned int is_heap_var : 1;
256
257 /* True if this field may contain pointers. */
258 unsigned int may_have_pointers : 1;
259
260 /* True if this field has only restrict qualified pointers. */
261 unsigned int only_restrict_pointers : 1;
262
263 /* True if this represents a heap var created for a restrict qualified
264 pointer. */
265 unsigned int is_restrict_var : 1;
266
267 /* True if this represents a global variable. */
268 unsigned int is_global_var : 1;
269
270 /* True if this represents a module escape point for IPA analysis. */
271 unsigned int is_ipa_escape_point : 1;
272
273 /* True if this represents a IPA function info. */
274 unsigned int is_fn_info : 1;
275
276 /* ??? Store somewhere better. */
277 unsigned short ruid;
278
279 /* The ID of the variable for the next field in this structure
280 or zero for the last field in this structure. */
281 unsigned next;
282
283 /* The ID of the variable for the first field in this structure. */
284 unsigned head;
285
286 /* Offset of this variable, in bits, from the base variable */
287 unsigned HOST_WIDE_INT offset;
288
289 /* Size of the variable, in bits. */
290 unsigned HOST_WIDE_INT size;
291
292 /* Full size of the base variable, in bits. */
293 unsigned HOST_WIDE_INT fullsize;
294
295 /* Name of this variable */
296 const char *name;
297
298 /* Tree that this variable is associated with. */
299 tree decl;
300
301 /* Points-to set for this variable. */
302 bitmap solution;
303
304 /* Old points-to set for this variable. */
305 bitmap oldsolution;
306 };
307 typedef struct variable_info *varinfo_t;
308
309 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
310 static varinfo_t first_or_preceding_vi_for_offset (varinfo_t,
311 unsigned HOST_WIDE_INT);
312 static varinfo_t lookup_vi_for_tree (tree);
313 static inline bool type_can_have_subvars (const_tree);
314 static void make_param_constraints (varinfo_t);
315
316 /* Pool of variable info structures. */
317 static object_allocator<variable_info> variable_info_pool
318 ("Variable info pool");
319
320 /* Map varinfo to final pt_solution. */
321 static hash_map<varinfo_t, pt_solution *> *final_solutions;
322 struct obstack final_solutions_obstack;
323
324 /* Table of variable info structures for constraint variables.
325 Indexed directly by variable info id. */
326 static vec<varinfo_t> varmap;
327
328 /* Return the varmap element N */
329
330 static inline varinfo_t
get_varinfo(unsigned int n)331 get_varinfo (unsigned int n)
332 {
333 return varmap[n];
334 }
335
336 /* Return the next variable in the list of sub-variables of VI
337 or NULL if VI is the last sub-variable. */
338
339 static inline varinfo_t
vi_next(varinfo_t vi)340 vi_next (varinfo_t vi)
341 {
342 return get_varinfo (vi->next);
343 }
344
345 /* Static IDs for the special variables. Variable ID zero is unused
346 and used as terminator for the sub-variable chain. */
347 enum { nothing_id = 1, anything_id = 2, string_id = 3,
348 escaped_id = 4, nonlocal_id = 5,
349 storedanything_id = 6, integer_id = 7 };
350
351 /* Return a new variable info structure consisting for a variable
352 named NAME, and using constraint graph node NODE. Append it
353 to the vector of variable info structures. */
354
355 static varinfo_t
new_var_info(tree t,const char * name,bool add_id)356 new_var_info (tree t, const char *name, bool add_id)
357 {
358 unsigned index = varmap.length ();
359 varinfo_t ret = variable_info_pool.allocate ();
360
361 if (dump_file && add_id)
362 {
363 char *tempname = xasprintf ("%s(%d)", name, index);
364 name = ggc_strdup (tempname);
365 free (tempname);
366 }
367
368 ret->id = index;
369 ret->name = name;
370 ret->decl = t;
371 /* Vars without decl are artificial and do not have sub-variables. */
372 ret->is_artificial_var = (t == NULL_TREE);
373 ret->is_special_var = false;
374 ret->is_unknown_size_var = false;
375 ret->is_full_var = (t == NULL_TREE);
376 ret->is_heap_var = false;
377 ret->may_have_pointers = true;
378 ret->only_restrict_pointers = false;
379 ret->is_restrict_var = false;
380 ret->ruid = 0;
381 ret->is_global_var = (t == NULL_TREE);
382 ret->is_ipa_escape_point = false;
383 ret->is_fn_info = false;
384 if (t && DECL_P (t))
385 ret->is_global_var = (is_global_var (t)
386 /* We have to treat even local register variables
387 as escape points. */
388 || (TREE_CODE (t) == VAR_DECL
389 && DECL_HARD_REGISTER (t)));
390 ret->solution = BITMAP_ALLOC (&pta_obstack);
391 ret->oldsolution = NULL;
392 ret->next = 0;
393 ret->head = ret->id;
394
395 stats.total_vars++;
396
397 varmap.safe_push (ret);
398
399 return ret;
400 }
401
402 /* A map mapping call statements to per-stmt variables for uses
403 and clobbers specific to the call. */
404 static hash_map<gimple *, varinfo_t> *call_stmt_vars;
405
406 /* Lookup or create the variable for the call statement CALL. */
407
408 static varinfo_t
get_call_vi(gcall * call)409 get_call_vi (gcall *call)
410 {
411 varinfo_t vi, vi2;
412
413 bool existed;
414 varinfo_t *slot_p = &call_stmt_vars->get_or_insert (call, &existed);
415 if (existed)
416 return *slot_p;
417
418 vi = new_var_info (NULL_TREE, "CALLUSED", true);
419 vi->offset = 0;
420 vi->size = 1;
421 vi->fullsize = 2;
422 vi->is_full_var = true;
423
424 vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED", true);
425 vi2->offset = 1;
426 vi2->size = 1;
427 vi2->fullsize = 2;
428 vi2->is_full_var = true;
429
430 vi->next = vi2->id;
431
432 *slot_p = vi;
433 return vi;
434 }
435
436 /* Lookup the variable for the call statement CALL representing
437 the uses. Returns NULL if there is nothing special about this call. */
438
439 static varinfo_t
lookup_call_use_vi(gcall * call)440 lookup_call_use_vi (gcall *call)
441 {
442 varinfo_t *slot_p = call_stmt_vars->get (call);
443 if (slot_p)
444 return *slot_p;
445
446 return NULL;
447 }
448
449 /* Lookup the variable for the call statement CALL representing
450 the clobbers. Returns NULL if there is nothing special about this call. */
451
452 static varinfo_t
lookup_call_clobber_vi(gcall * call)453 lookup_call_clobber_vi (gcall *call)
454 {
455 varinfo_t uses = lookup_call_use_vi (call);
456 if (!uses)
457 return NULL;
458
459 return vi_next (uses);
460 }
461
462 /* Lookup or create the variable for the call statement CALL representing
463 the uses. */
464
465 static varinfo_t
get_call_use_vi(gcall * call)466 get_call_use_vi (gcall *call)
467 {
468 return get_call_vi (call);
469 }
470
471 /* Lookup or create the variable for the call statement CALL representing
472 the clobbers. */
473
474 static varinfo_t ATTRIBUTE_UNUSED
get_call_clobber_vi(gcall * call)475 get_call_clobber_vi (gcall *call)
476 {
477 return vi_next (get_call_vi (call));
478 }
479
480
481 enum constraint_expr_type {SCALAR, DEREF, ADDRESSOF};
482
483 /* An expression that appears in a constraint. */
484
485 struct constraint_expr
486 {
487 /* Constraint type. */
488 constraint_expr_type type;
489
490 /* Variable we are referring to in the constraint. */
491 unsigned int var;
492
493 /* Offset, in bits, of this constraint from the beginning of
494 variables it ends up referring to.
495
496 IOW, in a deref constraint, we would deref, get the result set,
497 then add OFFSET to each member. */
498 HOST_WIDE_INT offset;
499 };
500
501 /* Use 0x8000... as special unknown offset. */
502 #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
503
504 typedef struct constraint_expr ce_s;
505 static void get_constraint_for_1 (tree, vec<ce_s> *, bool, bool);
506 static void get_constraint_for (tree, vec<ce_s> *);
507 static void get_constraint_for_rhs (tree, vec<ce_s> *);
508 static void do_deref (vec<ce_s> *);
509
510 /* Our set constraints are made up of two constraint expressions, one
511 LHS, and one RHS.
512
513 As described in the introduction, our set constraints each represent an
514 operation between set valued variables.
515 */
516 struct constraint
517 {
518 struct constraint_expr lhs;
519 struct constraint_expr rhs;
520 };
521
522 /* List of constraints that we use to build the constraint graph from. */
523
524 static vec<constraint_t> constraints;
525 static object_allocator<constraint> constraint_pool ("Constraint pool");
526
527 /* The constraint graph is represented as an array of bitmaps
528 containing successor nodes. */
529
530 struct constraint_graph
531 {
532 /* Size of this graph, which may be different than the number of
533 nodes in the variable map. */
534 unsigned int size;
535
536 /* Explicit successors of each node. */
537 bitmap *succs;
538
539 /* Implicit predecessors of each node (Used for variable
540 substitution). */
541 bitmap *implicit_preds;
542
543 /* Explicit predecessors of each node (Used for variable substitution). */
544 bitmap *preds;
545
546 /* Indirect cycle representatives, or -1 if the node has no indirect
547 cycles. */
548 int *indirect_cycles;
549
550 /* Representative node for a node. rep[a] == a unless the node has
551 been unified. */
552 unsigned int *rep;
553
554 /* Equivalence class representative for a label. This is used for
555 variable substitution. */
556 int *eq_rep;
557
558 /* Pointer equivalence label for a node. All nodes with the same
559 pointer equivalence label can be unified together at some point
560 (either during constraint optimization or after the constraint
561 graph is built). */
562 unsigned int *pe;
563
564 /* Pointer equivalence representative for a label. This is used to
565 handle nodes that are pointer equivalent but not location
566 equivalent. We can unite these once the addressof constraints
567 are transformed into initial points-to sets. */
568 int *pe_rep;
569
570 /* Pointer equivalence label for each node, used during variable
571 substitution. */
572 unsigned int *pointer_label;
573
574 /* Location equivalence label for each node, used during location
575 equivalence finding. */
576 unsigned int *loc_label;
577
578 /* Pointed-by set for each node, used during location equivalence
579 finding. This is pointed-by rather than pointed-to, because it
580 is constructed using the predecessor graph. */
581 bitmap *pointed_by;
582
583 /* Points to sets for pointer equivalence. This is *not* the actual
584 points-to sets for nodes. */
585 bitmap *points_to;
586
587 /* Bitmap of nodes where the bit is set if the node is a direct
588 node. Used for variable substitution. */
589 sbitmap direct_nodes;
590
591 /* Bitmap of nodes where the bit is set if the node is address
592 taken. Used for variable substitution. */
593 bitmap address_taken;
594
595 /* Vector of complex constraints for each graph node. Complex
596 constraints are those involving dereferences or offsets that are
597 not 0. */
598 vec<constraint_t> *complex;
599 };
600
601 static constraint_graph_t graph;
602
603 /* During variable substitution and the offline version of indirect
604 cycle finding, we create nodes to represent dereferences and
605 address taken constraints. These represent where these start and
606 end. */
607 #define FIRST_REF_NODE (varmap).length ()
608 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
609
610 /* Return the representative node for NODE, if NODE has been unioned
611 with another NODE.
612 This function performs path compression along the way to finding
613 the representative. */
614
615 static unsigned int
find(unsigned int node)616 find (unsigned int node)
617 {
618 gcc_checking_assert (node < graph->size);
619 if (graph->rep[node] != node)
620 return graph->rep[node] = find (graph->rep[node]);
621 return node;
622 }
623
624 /* Union the TO and FROM nodes to the TO nodes.
625 Note that at some point in the future, we may want to do
626 union-by-rank, in which case we are going to have to return the
627 node we unified to. */
628
629 static bool
unite(unsigned int to,unsigned int from)630 unite (unsigned int to, unsigned int from)
631 {
632 gcc_checking_assert (to < graph->size && from < graph->size);
633 if (to != from && graph->rep[from] != to)
634 {
635 graph->rep[from] = to;
636 return true;
637 }
638 return false;
639 }
640
641 /* Create a new constraint consisting of LHS and RHS expressions. */
642
643 static constraint_t
new_constraint(const struct constraint_expr lhs,const struct constraint_expr rhs)644 new_constraint (const struct constraint_expr lhs,
645 const struct constraint_expr rhs)
646 {
647 constraint_t ret = constraint_pool.allocate ();
648 ret->lhs = lhs;
649 ret->rhs = rhs;
650 return ret;
651 }
652
653 /* Print out constraint C to FILE. */
654
655 static void
dump_constraint(FILE * file,constraint_t c)656 dump_constraint (FILE *file, constraint_t c)
657 {
658 if (c->lhs.type == ADDRESSOF)
659 fprintf (file, "&");
660 else if (c->lhs.type == DEREF)
661 fprintf (file, "*");
662 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
663 if (c->lhs.offset == UNKNOWN_OFFSET)
664 fprintf (file, " + UNKNOWN");
665 else if (c->lhs.offset != 0)
666 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
667 fprintf (file, " = ");
668 if (c->rhs.type == ADDRESSOF)
669 fprintf (file, "&");
670 else if (c->rhs.type == DEREF)
671 fprintf (file, "*");
672 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
673 if (c->rhs.offset == UNKNOWN_OFFSET)
674 fprintf (file, " + UNKNOWN");
675 else if (c->rhs.offset != 0)
676 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
677 }
678
679
680 void debug_constraint (constraint_t);
681 void debug_constraints (void);
682 void debug_constraint_graph (void);
683 void debug_solution_for_var (unsigned int);
684 void debug_sa_points_to_info (void);
685
686 /* Print out constraint C to stderr. */
687
688 DEBUG_FUNCTION void
debug_constraint(constraint_t c)689 debug_constraint (constraint_t c)
690 {
691 dump_constraint (stderr, c);
692 fprintf (stderr, "\n");
693 }
694
695 /* Print out all constraints to FILE */
696
697 static void
dump_constraints(FILE * file,int from)698 dump_constraints (FILE *file, int from)
699 {
700 int i;
701 constraint_t c;
702 for (i = from; constraints.iterate (i, &c); i++)
703 if (c)
704 {
705 dump_constraint (file, c);
706 fprintf (file, "\n");
707 }
708 }
709
710 /* Print out all constraints to stderr. */
711
712 DEBUG_FUNCTION void
debug_constraints(void)713 debug_constraints (void)
714 {
715 dump_constraints (stderr, 0);
716 }
717
718 /* Print the constraint graph in dot format. */
719
720 static void
dump_constraint_graph(FILE * file)721 dump_constraint_graph (FILE *file)
722 {
723 unsigned int i;
724
725 /* Only print the graph if it has already been initialized: */
726 if (!graph)
727 return;
728
729 /* Prints the header of the dot file: */
730 fprintf (file, "strict digraph {\n");
731 fprintf (file, " node [\n shape = box\n ]\n");
732 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
733 fprintf (file, "\n // List of nodes and complex constraints in "
734 "the constraint graph:\n");
735
736 /* The next lines print the nodes in the graph together with the
737 complex constraints attached to them. */
738 for (i = 1; i < graph->size; i++)
739 {
740 if (i == FIRST_REF_NODE)
741 continue;
742 if (find (i) != i)
743 continue;
744 if (i < FIRST_REF_NODE)
745 fprintf (file, "\"%s\"", get_varinfo (i)->name);
746 else
747 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
748 if (graph->complex[i].exists ())
749 {
750 unsigned j;
751 constraint_t c;
752 fprintf (file, " [label=\"\\N\\n");
753 for (j = 0; graph->complex[i].iterate (j, &c); ++j)
754 {
755 dump_constraint (file, c);
756 fprintf (file, "\\l");
757 }
758 fprintf (file, "\"]");
759 }
760 fprintf (file, ";\n");
761 }
762
763 /* Go over the edges. */
764 fprintf (file, "\n // Edges in the constraint graph:\n");
765 for (i = 1; i < graph->size; i++)
766 {
767 unsigned j;
768 bitmap_iterator bi;
769 if (find (i) != i)
770 continue;
771 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
772 {
773 unsigned to = find (j);
774 if (i == to)
775 continue;
776 if (i < FIRST_REF_NODE)
777 fprintf (file, "\"%s\"", get_varinfo (i)->name);
778 else
779 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
780 fprintf (file, " -> ");
781 if (to < FIRST_REF_NODE)
782 fprintf (file, "\"%s\"", get_varinfo (to)->name);
783 else
784 fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name);
785 fprintf (file, ";\n");
786 }
787 }
788
789 /* Prints the tail of the dot file. */
790 fprintf (file, "}\n");
791 }
792
793 /* Print out the constraint graph to stderr. */
794
795 DEBUG_FUNCTION void
debug_constraint_graph(void)796 debug_constraint_graph (void)
797 {
798 dump_constraint_graph (stderr);
799 }
800
801 /* SOLVER FUNCTIONS
802
803 The solver is a simple worklist solver, that works on the following
804 algorithm:
805
806 sbitmap changed_nodes = all zeroes;
807 changed_count = 0;
808 For each node that is not already collapsed:
809 changed_count++;
810 set bit in changed nodes
811
812 while (changed_count > 0)
813 {
814 compute topological ordering for constraint graph
815
816 find and collapse cycles in the constraint graph (updating
817 changed if necessary)
818
819 for each node (n) in the graph in topological order:
820 changed_count--;
821
822 Process each complex constraint associated with the node,
823 updating changed if necessary.
824
825 For each outgoing edge from n, propagate the solution from n to
826 the destination of the edge, updating changed as necessary.
827
828 } */
829
830 /* Return true if two constraint expressions A and B are equal. */
831
832 static bool
constraint_expr_equal(struct constraint_expr a,struct constraint_expr b)833 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
834 {
835 return a.type == b.type && a.var == b.var && a.offset == b.offset;
836 }
837
838 /* Return true if constraint expression A is less than constraint expression
839 B. This is just arbitrary, but consistent, in order to give them an
840 ordering. */
841
842 static bool
constraint_expr_less(struct constraint_expr a,struct constraint_expr b)843 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
844 {
845 if (a.type == b.type)
846 {
847 if (a.var == b.var)
848 return a.offset < b.offset;
849 else
850 return a.var < b.var;
851 }
852 else
853 return a.type < b.type;
854 }
855
856 /* Return true if constraint A is less than constraint B. This is just
857 arbitrary, but consistent, in order to give them an ordering. */
858
859 static bool
constraint_less(const constraint_t & a,const constraint_t & b)860 constraint_less (const constraint_t &a, const constraint_t &b)
861 {
862 if (constraint_expr_less (a->lhs, b->lhs))
863 return true;
864 else if (constraint_expr_less (b->lhs, a->lhs))
865 return false;
866 else
867 return constraint_expr_less (a->rhs, b->rhs);
868 }
869
870 /* Return true if two constraints A and B are equal. */
871
872 static bool
constraint_equal(struct constraint a,struct constraint b)873 constraint_equal (struct constraint a, struct constraint b)
874 {
875 return constraint_expr_equal (a.lhs, b.lhs)
876 && constraint_expr_equal (a.rhs, b.rhs);
877 }
878
879
880 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
881
882 static constraint_t
constraint_vec_find(vec<constraint_t> vec,struct constraint lookfor)883 constraint_vec_find (vec<constraint_t> vec,
884 struct constraint lookfor)
885 {
886 unsigned int place;
887 constraint_t found;
888
889 if (!vec.exists ())
890 return NULL;
891
892 place = vec.lower_bound (&lookfor, constraint_less);
893 if (place >= vec.length ())
894 return NULL;
895 found = vec[place];
896 if (!constraint_equal (*found, lookfor))
897 return NULL;
898 return found;
899 }
900
901 /* Union two constraint vectors, TO and FROM. Put the result in TO.
902 Returns true of TO set is changed. */
903
904 static bool
constraint_set_union(vec<constraint_t> * to,vec<constraint_t> * from)905 constraint_set_union (vec<constraint_t> *to,
906 vec<constraint_t> *from)
907 {
908 int i;
909 constraint_t c;
910 bool any_change = false;
911
912 FOR_EACH_VEC_ELT (*from, i, c)
913 {
914 if (constraint_vec_find (*to, *c) == NULL)
915 {
916 unsigned int place = to->lower_bound (c, constraint_less);
917 to->safe_insert (place, c);
918 any_change = true;
919 }
920 }
921 return any_change;
922 }
923
924 /* Expands the solution in SET to all sub-fields of variables included. */
925
926 static bitmap
solution_set_expand(bitmap set,bitmap * expanded)927 solution_set_expand (bitmap set, bitmap *expanded)
928 {
929 bitmap_iterator bi;
930 unsigned j;
931
932 if (*expanded)
933 return *expanded;
934
935 *expanded = BITMAP_ALLOC (&iteration_obstack);
936
937 /* In a first pass expand to the head of the variables we need to
938 add all sub-fields off. This avoids quadratic behavior. */
939 EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
940 {
941 varinfo_t v = get_varinfo (j);
942 if (v->is_artificial_var
943 || v->is_full_var)
944 continue;
945 bitmap_set_bit (*expanded, v->head);
946 }
947
948 /* In the second pass now expand all head variables with subfields. */
949 EXECUTE_IF_SET_IN_BITMAP (*expanded, 0, j, bi)
950 {
951 varinfo_t v = get_varinfo (j);
952 if (v->head != j)
953 continue;
954 for (v = vi_next (v); v != NULL; v = vi_next (v))
955 bitmap_set_bit (*expanded, v->id);
956 }
957
958 /* And finally set the rest of the bits from SET. */
959 bitmap_ior_into (*expanded, set);
960
961 return *expanded;
962 }
963
964 /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
965 process. */
966
967 static bool
set_union_with_increment(bitmap to,bitmap delta,HOST_WIDE_INT inc,bitmap * expanded_delta)968 set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
969 bitmap *expanded_delta)
970 {
971 bool changed = false;
972 bitmap_iterator bi;
973 unsigned int i;
974
975 /* If the solution of DELTA contains anything it is good enough to transfer
976 this to TO. */
977 if (bitmap_bit_p (delta, anything_id))
978 return bitmap_set_bit (to, anything_id);
979
980 /* If the offset is unknown we have to expand the solution to
981 all subfields. */
982 if (inc == UNKNOWN_OFFSET)
983 {
984 delta = solution_set_expand (delta, expanded_delta);
985 changed |= bitmap_ior_into (to, delta);
986 return changed;
987 }
988
989 /* For non-zero offset union the offsetted solution into the destination. */
990 EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
991 {
992 varinfo_t vi = get_varinfo (i);
993
994 /* If this is a variable with just one field just set its bit
995 in the result. */
996 if (vi->is_artificial_var
997 || vi->is_unknown_size_var
998 || vi->is_full_var)
999 changed |= bitmap_set_bit (to, i);
1000 else
1001 {
1002 HOST_WIDE_INT fieldoffset = vi->offset + inc;
1003 unsigned HOST_WIDE_INT size = vi->size;
1004
1005 /* If the offset makes the pointer point to before the
1006 variable use offset zero for the field lookup. */
1007 if (fieldoffset < 0)
1008 vi = get_varinfo (vi->head);
1009 else
1010 vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
1011
1012 do
1013 {
1014 changed |= bitmap_set_bit (to, vi->id);
1015 if (vi->is_full_var
1016 || vi->next == 0)
1017 break;
1018
1019 /* We have to include all fields that overlap the current field
1020 shifted by inc. */
1021 vi = vi_next (vi);
1022 }
1023 while (vi->offset < fieldoffset + size);
1024 }
1025 }
1026
1027 return changed;
1028 }
1029
1030 /* Insert constraint C into the list of complex constraints for graph
1031 node VAR. */
1032
1033 static void
insert_into_complex(constraint_graph_t graph,unsigned int var,constraint_t c)1034 insert_into_complex (constraint_graph_t graph,
1035 unsigned int var, constraint_t c)
1036 {
1037 vec<constraint_t> complex = graph->complex[var];
1038 unsigned int place = complex.lower_bound (c, constraint_less);
1039
1040 /* Only insert constraints that do not already exist. */
1041 if (place >= complex.length ()
1042 || !constraint_equal (*c, *complex[place]))
1043 graph->complex[var].safe_insert (place, c);
1044 }
1045
1046
1047 /* Condense two variable nodes into a single variable node, by moving
1048 all associated info from FROM to TO. Returns true if TO node's
1049 constraint set changes after the merge. */
1050
1051 static bool
merge_node_constraints(constraint_graph_t graph,unsigned int to,unsigned int from)1052 merge_node_constraints (constraint_graph_t graph, unsigned int to,
1053 unsigned int from)
1054 {
1055 unsigned int i;
1056 constraint_t c;
1057 bool any_change = false;
1058
1059 gcc_checking_assert (find (from) == to);
1060
1061 /* Move all complex constraints from src node into to node */
1062 FOR_EACH_VEC_ELT (graph->complex[from], i, c)
1063 {
1064 /* In complex constraints for node FROM, we may have either
1065 a = *FROM, and *FROM = a, or an offseted constraint which are
1066 always added to the rhs node's constraints. */
1067
1068 if (c->rhs.type == DEREF)
1069 c->rhs.var = to;
1070 else if (c->lhs.type == DEREF)
1071 c->lhs.var = to;
1072 else
1073 c->rhs.var = to;
1074
1075 }
1076 any_change = constraint_set_union (&graph->complex[to],
1077 &graph->complex[from]);
1078 graph->complex[from].release ();
1079 return any_change;
1080 }
1081
1082
1083 /* Remove edges involving NODE from GRAPH. */
1084
1085 static void
clear_edges_for_node(constraint_graph_t graph,unsigned int node)1086 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
1087 {
1088 if (graph->succs[node])
1089 BITMAP_FREE (graph->succs[node]);
1090 }
1091
1092 /* Merge GRAPH nodes FROM and TO into node TO. */
1093
1094 static void
merge_graph_nodes(constraint_graph_t graph,unsigned int to,unsigned int from)1095 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1096 unsigned int from)
1097 {
1098 if (graph->indirect_cycles[from] != -1)
1099 {
1100 /* If we have indirect cycles with the from node, and we have
1101 none on the to node, the to node has indirect cycles from the
1102 from node now that they are unified.
1103 If indirect cycles exist on both, unify the nodes that they
1104 are in a cycle with, since we know they are in a cycle with
1105 each other. */
1106 if (graph->indirect_cycles[to] == -1)
1107 graph->indirect_cycles[to] = graph->indirect_cycles[from];
1108 }
1109
1110 /* Merge all the successor edges. */
1111 if (graph->succs[from])
1112 {
1113 if (!graph->succs[to])
1114 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1115 bitmap_ior_into (graph->succs[to],
1116 graph->succs[from]);
1117 }
1118
1119 clear_edges_for_node (graph, from);
1120 }
1121
1122
1123 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1124 it doesn't exist in the graph already. */
1125
1126 static void
add_implicit_graph_edge(constraint_graph_t graph,unsigned int to,unsigned int from)1127 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1128 unsigned int from)
1129 {
1130 if (to == from)
1131 return;
1132
1133 if (!graph->implicit_preds[to])
1134 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1135
1136 if (bitmap_set_bit (graph->implicit_preds[to], from))
1137 stats.num_implicit_edges++;
1138 }
1139
1140 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1141 it doesn't exist in the graph already.
1142 Return false if the edge already existed, true otherwise. */
1143
1144 static void
add_pred_graph_edge(constraint_graph_t graph,unsigned int to,unsigned int from)1145 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1146 unsigned int from)
1147 {
1148 if (!graph->preds[to])
1149 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1150 bitmap_set_bit (graph->preds[to], from);
1151 }
1152
1153 /* Add a graph edge to GRAPH, going from FROM to TO if
1154 it doesn't exist in the graph already.
1155 Return false if the edge already existed, true otherwise. */
1156
1157 static bool
add_graph_edge(constraint_graph_t graph,unsigned int to,unsigned int from)1158 add_graph_edge (constraint_graph_t graph, unsigned int to,
1159 unsigned int from)
1160 {
1161 if (to == from)
1162 {
1163 return false;
1164 }
1165 else
1166 {
1167 bool r = false;
1168
1169 if (!graph->succs[from])
1170 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1171 if (bitmap_set_bit (graph->succs[from], to))
1172 {
1173 r = true;
1174 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1175 stats.num_edges++;
1176 }
1177 return r;
1178 }
1179 }
1180
1181
1182 /* Initialize the constraint graph structure to contain SIZE nodes. */
1183
1184 static void
init_graph(unsigned int size)1185 init_graph (unsigned int size)
1186 {
1187 unsigned int j;
1188
1189 graph = XCNEW (struct constraint_graph);
1190 graph->size = size;
1191 graph->succs = XCNEWVEC (bitmap, graph->size);
1192 graph->indirect_cycles = XNEWVEC (int, graph->size);
1193 graph->rep = XNEWVEC (unsigned int, graph->size);
1194 /* ??? Macros do not support template types with multiple arguments,
1195 so we use a typedef to work around it. */
1196 typedef vec<constraint_t> vec_constraint_t_heap;
1197 graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
1198 graph->pe = XCNEWVEC (unsigned int, graph->size);
1199 graph->pe_rep = XNEWVEC (int, graph->size);
1200
1201 for (j = 0; j < graph->size; j++)
1202 {
1203 graph->rep[j] = j;
1204 graph->pe_rep[j] = -1;
1205 graph->indirect_cycles[j] = -1;
1206 }
1207 }
1208
1209 /* Build the constraint graph, adding only predecessor edges right now. */
1210
1211 static void
build_pred_graph(void)1212 build_pred_graph (void)
1213 {
1214 int i;
1215 constraint_t c;
1216 unsigned int j;
1217
1218 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1219 graph->preds = XCNEWVEC (bitmap, graph->size);
1220 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1221 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1222 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1223 graph->points_to = XCNEWVEC (bitmap, graph->size);
1224 graph->eq_rep = XNEWVEC (int, graph->size);
1225 graph->direct_nodes = sbitmap_alloc (graph->size);
1226 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1227 bitmap_clear (graph->direct_nodes);
1228
1229 for (j = 1; j < FIRST_REF_NODE; j++)
1230 {
1231 if (!get_varinfo (j)->is_special_var)
1232 bitmap_set_bit (graph->direct_nodes, j);
1233 }
1234
1235 for (j = 0; j < graph->size; j++)
1236 graph->eq_rep[j] = -1;
1237
1238 for (j = 0; j < varmap.length (); j++)
1239 graph->indirect_cycles[j] = -1;
1240
1241 FOR_EACH_VEC_ELT (constraints, i, c)
1242 {
1243 struct constraint_expr lhs = c->lhs;
1244 struct constraint_expr rhs = c->rhs;
1245 unsigned int lhsvar = lhs.var;
1246 unsigned int rhsvar = rhs.var;
1247
1248 if (lhs.type == DEREF)
1249 {
1250 /* *x = y. */
1251 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1252 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1253 }
1254 else if (rhs.type == DEREF)
1255 {
1256 /* x = *y */
1257 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1258 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1259 else
1260 bitmap_clear_bit (graph->direct_nodes, lhsvar);
1261 }
1262 else if (rhs.type == ADDRESSOF)
1263 {
1264 varinfo_t v;
1265
1266 /* x = &y */
1267 if (graph->points_to[lhsvar] == NULL)
1268 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1269 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1270
1271 if (graph->pointed_by[rhsvar] == NULL)
1272 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1273 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1274
1275 /* Implicitly, *x = y */
1276 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1277
1278 /* All related variables are no longer direct nodes. */
1279 bitmap_clear_bit (graph->direct_nodes, rhsvar);
1280 v = get_varinfo (rhsvar);
1281 if (!v->is_full_var)
1282 {
1283 v = get_varinfo (v->head);
1284 do
1285 {
1286 bitmap_clear_bit (graph->direct_nodes, v->id);
1287 v = vi_next (v);
1288 }
1289 while (v != NULL);
1290 }
1291 bitmap_set_bit (graph->address_taken, rhsvar);
1292 }
1293 else if (lhsvar > anything_id
1294 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1295 {
1296 /* x = y */
1297 add_pred_graph_edge (graph, lhsvar, rhsvar);
1298 /* Implicitly, *x = *y */
1299 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1300 FIRST_REF_NODE + rhsvar);
1301 }
1302 else if (lhs.offset != 0 || rhs.offset != 0)
1303 {
1304 if (rhs.offset != 0)
1305 bitmap_clear_bit (graph->direct_nodes, lhs.var);
1306 else if (lhs.offset != 0)
1307 bitmap_clear_bit (graph->direct_nodes, rhs.var);
1308 }
1309 }
1310 }
1311
1312 /* Build the constraint graph, adding successor edges. */
1313
1314 static void
build_succ_graph(void)1315 build_succ_graph (void)
1316 {
1317 unsigned i, t;
1318 constraint_t c;
1319
1320 FOR_EACH_VEC_ELT (constraints, i, c)
1321 {
1322 struct constraint_expr lhs;
1323 struct constraint_expr rhs;
1324 unsigned int lhsvar;
1325 unsigned int rhsvar;
1326
1327 if (!c)
1328 continue;
1329
1330 lhs = c->lhs;
1331 rhs = c->rhs;
1332 lhsvar = find (lhs.var);
1333 rhsvar = find (rhs.var);
1334
1335 if (lhs.type == DEREF)
1336 {
1337 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1338 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1339 }
1340 else if (rhs.type == DEREF)
1341 {
1342 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1343 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1344 }
1345 else if (rhs.type == ADDRESSOF)
1346 {
1347 /* x = &y */
1348 gcc_checking_assert (find (rhs.var) == rhs.var);
1349 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1350 }
1351 else if (lhsvar > anything_id
1352 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1353 {
1354 add_graph_edge (graph, lhsvar, rhsvar);
1355 }
1356 }
1357
1358 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1359 receive pointers. */
1360 t = find (storedanything_id);
1361 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1362 {
1363 if (!bitmap_bit_p (graph->direct_nodes, i)
1364 && get_varinfo (i)->may_have_pointers)
1365 add_graph_edge (graph, find (i), t);
1366 }
1367
1368 /* Everything stored to ANYTHING also potentially escapes. */
1369 add_graph_edge (graph, find (escaped_id), t);
1370 }
1371
1372
1373 /* Changed variables on the last iteration. */
1374 static bitmap changed;
1375
1376 /* Strongly Connected Component visitation info. */
1377
1378 struct scc_info
1379 {
1380 sbitmap visited;
1381 sbitmap deleted;
1382 unsigned int *dfs;
1383 unsigned int *node_mapping;
1384 int current_index;
1385 vec<unsigned> scc_stack;
1386 };
1387
1388
1389 /* Recursive routine to find strongly connected components in GRAPH.
1390 SI is the SCC info to store the information in, and N is the id of current
1391 graph node we are processing.
1392
1393 This is Tarjan's strongly connected component finding algorithm, as
1394 modified by Nuutila to keep only non-root nodes on the stack.
1395 The algorithm can be found in "On finding the strongly connected
1396 connected components in a directed graph" by Esko Nuutila and Eljas
1397 Soisalon-Soininen, in Information Processing Letters volume 49,
1398 number 1, pages 9-14. */
1399
1400 static void
scc_visit(constraint_graph_t graph,struct scc_info * si,unsigned int n)1401 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1402 {
1403 unsigned int i;
1404 bitmap_iterator bi;
1405 unsigned int my_dfs;
1406
1407 bitmap_set_bit (si->visited, n);
1408 si->dfs[n] = si->current_index ++;
1409 my_dfs = si->dfs[n];
1410
1411 /* Visit all the successors. */
1412 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1413 {
1414 unsigned int w;
1415
1416 if (i > LAST_REF_NODE)
1417 break;
1418
1419 w = find (i);
1420 if (bitmap_bit_p (si->deleted, w))
1421 continue;
1422
1423 if (!bitmap_bit_p (si->visited, w))
1424 scc_visit (graph, si, w);
1425
1426 unsigned int t = find (w);
1427 gcc_checking_assert (find (n) == n);
1428 if (si->dfs[t] < si->dfs[n])
1429 si->dfs[n] = si->dfs[t];
1430 }
1431
1432 /* See if any components have been identified. */
1433 if (si->dfs[n] == my_dfs)
1434 {
1435 if (si->scc_stack.length () > 0
1436 && si->dfs[si->scc_stack.last ()] >= my_dfs)
1437 {
1438 bitmap scc = BITMAP_ALLOC (NULL);
1439 unsigned int lowest_node;
1440 bitmap_iterator bi;
1441
1442 bitmap_set_bit (scc, n);
1443
1444 while (si->scc_stack.length () != 0
1445 && si->dfs[si->scc_stack.last ()] >= my_dfs)
1446 {
1447 unsigned int w = si->scc_stack.pop ();
1448
1449 bitmap_set_bit (scc, w);
1450 }
1451
1452 lowest_node = bitmap_first_set_bit (scc);
1453 gcc_assert (lowest_node < FIRST_REF_NODE);
1454
1455 /* Collapse the SCC nodes into a single node, and mark the
1456 indirect cycles. */
1457 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1458 {
1459 if (i < FIRST_REF_NODE)
1460 {
1461 if (unite (lowest_node, i))
1462 unify_nodes (graph, lowest_node, i, false);
1463 }
1464 else
1465 {
1466 unite (lowest_node, i);
1467 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1468 }
1469 }
1470 }
1471 bitmap_set_bit (si->deleted, n);
1472 }
1473 else
1474 si->scc_stack.safe_push (n);
1475 }
1476
1477 /* Unify node FROM into node TO, updating the changed count if
1478 necessary when UPDATE_CHANGED is true. */
1479
1480 static void
unify_nodes(constraint_graph_t graph,unsigned int to,unsigned int from,bool update_changed)1481 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1482 bool update_changed)
1483 {
1484 gcc_checking_assert (to != from && find (to) == to);
1485
1486 if (dump_file && (dump_flags & TDF_DETAILS))
1487 fprintf (dump_file, "Unifying %s to %s\n",
1488 get_varinfo (from)->name,
1489 get_varinfo (to)->name);
1490
1491 if (update_changed)
1492 stats.unified_vars_dynamic++;
1493 else
1494 stats.unified_vars_static++;
1495
1496 merge_graph_nodes (graph, to, from);
1497 if (merge_node_constraints (graph, to, from))
1498 {
1499 if (update_changed)
1500 bitmap_set_bit (changed, to);
1501 }
1502
1503 /* Mark TO as changed if FROM was changed. If TO was already marked
1504 as changed, decrease the changed count. */
1505
1506 if (update_changed
1507 && bitmap_clear_bit (changed, from))
1508 bitmap_set_bit (changed, to);
1509 varinfo_t fromvi = get_varinfo (from);
1510 if (fromvi->solution)
1511 {
1512 /* If the solution changes because of the merging, we need to mark
1513 the variable as changed. */
1514 varinfo_t tovi = get_varinfo (to);
1515 if (bitmap_ior_into (tovi->solution, fromvi->solution))
1516 {
1517 if (update_changed)
1518 bitmap_set_bit (changed, to);
1519 }
1520
1521 BITMAP_FREE (fromvi->solution);
1522 if (fromvi->oldsolution)
1523 BITMAP_FREE (fromvi->oldsolution);
1524
1525 if (stats.iterations > 0
1526 && tovi->oldsolution)
1527 BITMAP_FREE (tovi->oldsolution);
1528 }
1529 if (graph->succs[to])
1530 bitmap_clear_bit (graph->succs[to], to);
1531 }
1532
1533 /* Information needed to compute the topological ordering of a graph. */
1534
1535 struct topo_info
1536 {
1537 /* sbitmap of visited nodes. */
1538 sbitmap visited;
1539 /* Array that stores the topological order of the graph, *in
1540 reverse*. */
1541 vec<unsigned> topo_order;
1542 };
1543
1544
1545 /* Initialize and return a topological info structure. */
1546
1547 static struct topo_info *
init_topo_info(void)1548 init_topo_info (void)
1549 {
1550 size_t size = graph->size;
1551 struct topo_info *ti = XNEW (struct topo_info);
1552 ti->visited = sbitmap_alloc (size);
1553 bitmap_clear (ti->visited);
1554 ti->topo_order.create (1);
1555 return ti;
1556 }
1557
1558
1559 /* Free the topological sort info pointed to by TI. */
1560
1561 static void
free_topo_info(struct topo_info * ti)1562 free_topo_info (struct topo_info *ti)
1563 {
1564 sbitmap_free (ti->visited);
1565 ti->topo_order.release ();
1566 free (ti);
1567 }
1568
1569 /* Visit the graph in topological order, and store the order in the
1570 topo_info structure. */
1571
1572 static void
topo_visit(constraint_graph_t graph,struct topo_info * ti,unsigned int n)1573 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1574 unsigned int n)
1575 {
1576 bitmap_iterator bi;
1577 unsigned int j;
1578
1579 bitmap_set_bit (ti->visited, n);
1580
1581 if (graph->succs[n])
1582 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1583 {
1584 if (!bitmap_bit_p (ti->visited, j))
1585 topo_visit (graph, ti, j);
1586 }
1587
1588 ti->topo_order.safe_push (n);
1589 }
1590
1591 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1592 starting solution for y. */
1593
1594 static void
do_sd_constraint(constraint_graph_t graph,constraint_t c,bitmap delta,bitmap * expanded_delta)1595 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1596 bitmap delta, bitmap *expanded_delta)
1597 {
1598 unsigned int lhs = c->lhs.var;
1599 bool flag = false;
1600 bitmap sol = get_varinfo (lhs)->solution;
1601 unsigned int j;
1602 bitmap_iterator bi;
1603 HOST_WIDE_INT roffset = c->rhs.offset;
1604
1605 /* Our IL does not allow this. */
1606 gcc_checking_assert (c->lhs.offset == 0);
1607
1608 /* If the solution of Y contains anything it is good enough to transfer
1609 this to the LHS. */
1610 if (bitmap_bit_p (delta, anything_id))
1611 {
1612 flag |= bitmap_set_bit (sol, anything_id);
1613 goto done;
1614 }
1615
1616 /* If we do not know at with offset the rhs is dereferenced compute
1617 the reachability set of DELTA, conservatively assuming it is
1618 dereferenced at all valid offsets. */
1619 if (roffset == UNKNOWN_OFFSET)
1620 {
1621 delta = solution_set_expand (delta, expanded_delta);
1622 /* No further offset processing is necessary. */
1623 roffset = 0;
1624 }
1625
1626 /* For each variable j in delta (Sol(y)), add
1627 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1628 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1629 {
1630 varinfo_t v = get_varinfo (j);
1631 HOST_WIDE_INT fieldoffset = v->offset + roffset;
1632 unsigned HOST_WIDE_INT size = v->size;
1633 unsigned int t;
1634
1635 if (v->is_full_var)
1636 ;
1637 else if (roffset != 0)
1638 {
1639 if (fieldoffset < 0)
1640 v = get_varinfo (v->head);
1641 else
1642 v = first_or_preceding_vi_for_offset (v, fieldoffset);
1643 }
1644
1645 /* We have to include all fields that overlap the current field
1646 shifted by roffset. */
1647 do
1648 {
1649 t = find (v->id);
1650
1651 /* Adding edges from the special vars is pointless.
1652 They don't have sets that can change. */
1653 if (get_varinfo (t)->is_special_var)
1654 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1655 /* Merging the solution from ESCAPED needlessly increases
1656 the set. Use ESCAPED as representative instead. */
1657 else if (v->id == escaped_id)
1658 flag |= bitmap_set_bit (sol, escaped_id);
1659 else if (v->may_have_pointers
1660 && add_graph_edge (graph, lhs, t))
1661 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1662
1663 if (v->is_full_var
1664 || v->next == 0)
1665 break;
1666
1667 v = vi_next (v);
1668 }
1669 while (v->offset < fieldoffset + size);
1670 }
1671
1672 done:
1673 /* If the LHS solution changed, mark the var as changed. */
1674 if (flag)
1675 {
1676 get_varinfo (lhs)->solution = sol;
1677 bitmap_set_bit (changed, lhs);
1678 }
1679 }
1680
1681 /* Process a constraint C that represents *(x + off) = y using DELTA
1682 as the starting solution for x. */
1683
1684 static void
do_ds_constraint(constraint_t c,bitmap delta,bitmap * expanded_delta)1685 do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1686 {
1687 unsigned int rhs = c->rhs.var;
1688 bitmap sol = get_varinfo (rhs)->solution;
1689 unsigned int j;
1690 bitmap_iterator bi;
1691 HOST_WIDE_INT loff = c->lhs.offset;
1692 bool escaped_p = false;
1693
1694 /* Our IL does not allow this. */
1695 gcc_checking_assert (c->rhs.offset == 0);
1696
1697 /* If the solution of y contains ANYTHING simply use the ANYTHING
1698 solution. This avoids needlessly increasing the points-to sets. */
1699 if (bitmap_bit_p (sol, anything_id))
1700 sol = get_varinfo (find (anything_id))->solution;
1701
1702 /* If the solution for x contains ANYTHING we have to merge the
1703 solution of y into all pointer variables which we do via
1704 STOREDANYTHING. */
1705 if (bitmap_bit_p (delta, anything_id))
1706 {
1707 unsigned t = find (storedanything_id);
1708 if (add_graph_edge (graph, t, rhs))
1709 {
1710 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1711 bitmap_set_bit (changed, t);
1712 }
1713 return;
1714 }
1715
1716 /* If we do not know at with offset the rhs is dereferenced compute
1717 the reachability set of DELTA, conservatively assuming it is
1718 dereferenced at all valid offsets. */
1719 if (loff == UNKNOWN_OFFSET)
1720 {
1721 delta = solution_set_expand (delta, expanded_delta);
1722 loff = 0;
1723 }
1724
1725 /* For each member j of delta (Sol(x)), add an edge from y to j and
1726 union Sol(y) into Sol(j) */
1727 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1728 {
1729 varinfo_t v = get_varinfo (j);
1730 unsigned int t;
1731 HOST_WIDE_INT fieldoffset = v->offset + loff;
1732 unsigned HOST_WIDE_INT size = v->size;
1733
1734 if (v->is_full_var)
1735 ;
1736 else if (loff != 0)
1737 {
1738 if (fieldoffset < 0)
1739 v = get_varinfo (v->head);
1740 else
1741 v = first_or_preceding_vi_for_offset (v, fieldoffset);
1742 }
1743
1744 /* We have to include all fields that overlap the current field
1745 shifted by loff. */
1746 do
1747 {
1748 if (v->may_have_pointers)
1749 {
1750 /* If v is a global variable then this is an escape point. */
1751 if (v->is_global_var
1752 && !escaped_p)
1753 {
1754 t = find (escaped_id);
1755 if (add_graph_edge (graph, t, rhs)
1756 && bitmap_ior_into (get_varinfo (t)->solution, sol))
1757 bitmap_set_bit (changed, t);
1758 /* Enough to let rhs escape once. */
1759 escaped_p = true;
1760 }
1761
1762 if (v->is_special_var)
1763 break;
1764
1765 t = find (v->id);
1766 if (add_graph_edge (graph, t, rhs)
1767 && bitmap_ior_into (get_varinfo (t)->solution, sol))
1768 bitmap_set_bit (changed, t);
1769 }
1770
1771 if (v->is_full_var
1772 || v->next == 0)
1773 break;
1774
1775 v = vi_next (v);
1776 }
1777 while (v->offset < fieldoffset + size);
1778 }
1779 }
1780
1781 /* Handle a non-simple (simple meaning requires no iteration),
1782 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1783
1784 static void
do_complex_constraint(constraint_graph_t graph,constraint_t c,bitmap delta,bitmap * expanded_delta)1785 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1786 bitmap *expanded_delta)
1787 {
1788 if (c->lhs.type == DEREF)
1789 {
1790 if (c->rhs.type == ADDRESSOF)
1791 {
1792 gcc_unreachable ();
1793 }
1794 else
1795 {
1796 /* *x = y */
1797 do_ds_constraint (c, delta, expanded_delta);
1798 }
1799 }
1800 else if (c->rhs.type == DEREF)
1801 {
1802 /* x = *y */
1803 if (!(get_varinfo (c->lhs.var)->is_special_var))
1804 do_sd_constraint (graph, c, delta, expanded_delta);
1805 }
1806 else
1807 {
1808 bitmap tmp;
1809 bool flag = false;
1810
1811 gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1812 && c->rhs.offset != 0 && c->lhs.offset == 0);
1813 tmp = get_varinfo (c->lhs.var)->solution;
1814
1815 flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1816 expanded_delta);
1817
1818 if (flag)
1819 bitmap_set_bit (changed, c->lhs.var);
1820 }
1821 }
1822
1823 /* Initialize and return a new SCC info structure. */
1824
1825 static struct scc_info *
init_scc_info(size_t size)1826 init_scc_info (size_t size)
1827 {
1828 struct scc_info *si = XNEW (struct scc_info);
1829 size_t i;
1830
1831 si->current_index = 0;
1832 si->visited = sbitmap_alloc (size);
1833 bitmap_clear (si->visited);
1834 si->deleted = sbitmap_alloc (size);
1835 bitmap_clear (si->deleted);
1836 si->node_mapping = XNEWVEC (unsigned int, size);
1837 si->dfs = XCNEWVEC (unsigned int, size);
1838
1839 for (i = 0; i < size; i++)
1840 si->node_mapping[i] = i;
1841
1842 si->scc_stack.create (1);
1843 return si;
1844 }
1845
1846 /* Free an SCC info structure pointed to by SI */
1847
1848 static void
free_scc_info(struct scc_info * si)1849 free_scc_info (struct scc_info *si)
1850 {
1851 sbitmap_free (si->visited);
1852 sbitmap_free (si->deleted);
1853 free (si->node_mapping);
1854 free (si->dfs);
1855 si->scc_stack.release ();
1856 free (si);
1857 }
1858
1859
1860 /* Find indirect cycles in GRAPH that occur, using strongly connected
1861 components, and note them in the indirect cycles map.
1862
1863 This technique comes from Ben Hardekopf and Calvin Lin,
1864 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1865 Lines of Code", submitted to PLDI 2007. */
1866
1867 static void
find_indirect_cycles(constraint_graph_t graph)1868 find_indirect_cycles (constraint_graph_t graph)
1869 {
1870 unsigned int i;
1871 unsigned int size = graph->size;
1872 struct scc_info *si = init_scc_info (size);
1873
1874 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1875 if (!bitmap_bit_p (si->visited, i) && find (i) == i)
1876 scc_visit (graph, si, i);
1877
1878 free_scc_info (si);
1879 }
1880
1881 /* Compute a topological ordering for GRAPH, and store the result in the
1882 topo_info structure TI. */
1883
1884 static void
compute_topo_order(constraint_graph_t graph,struct topo_info * ti)1885 compute_topo_order (constraint_graph_t graph,
1886 struct topo_info *ti)
1887 {
1888 unsigned int i;
1889 unsigned int size = graph->size;
1890
1891 for (i = 0; i != size; ++i)
1892 if (!bitmap_bit_p (ti->visited, i) && find (i) == i)
1893 topo_visit (graph, ti, i);
1894 }
1895
1896 /* Structure used to for hash value numbering of pointer equivalence
1897 classes. */
1898
1899 typedef struct equiv_class_label
1900 {
1901 hashval_t hashcode;
1902 unsigned int equivalence_class;
1903 bitmap labels;
1904 } *equiv_class_label_t;
1905 typedef const struct equiv_class_label *const_equiv_class_label_t;
1906
1907 /* Equiv_class_label hashtable helpers. */
1908
1909 struct equiv_class_hasher : free_ptr_hash <equiv_class_label>
1910 {
1911 static inline hashval_t hash (const equiv_class_label *);
1912 static inline bool equal (const equiv_class_label *,
1913 const equiv_class_label *);
1914 };
1915
1916 /* Hash function for a equiv_class_label_t */
1917
1918 inline hashval_t
hash(const equiv_class_label * ecl)1919 equiv_class_hasher::hash (const equiv_class_label *ecl)
1920 {
1921 return ecl->hashcode;
1922 }
1923
1924 /* Equality function for two equiv_class_label_t's. */
1925
1926 inline bool
equal(const equiv_class_label * eql1,const equiv_class_label * eql2)1927 equiv_class_hasher::equal (const equiv_class_label *eql1,
1928 const equiv_class_label *eql2)
1929 {
1930 return (eql1->hashcode == eql2->hashcode
1931 && bitmap_equal_p (eql1->labels, eql2->labels));
1932 }
1933
1934 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1935 classes. */
1936 static hash_table<equiv_class_hasher> *pointer_equiv_class_table;
1937
1938 /* A hashtable for mapping a bitmap of labels->location equivalence
1939 classes. */
1940 static hash_table<equiv_class_hasher> *location_equiv_class_table;
1941
1942 /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1943 hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1944 is equivalent to. */
1945
1946 static equiv_class_label *
equiv_class_lookup_or_add(hash_table<equiv_class_hasher> * table,bitmap labels)1947 equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1948 bitmap labels)
1949 {
1950 equiv_class_label **slot;
1951 equiv_class_label ecl;
1952
1953 ecl.labels = labels;
1954 ecl.hashcode = bitmap_hash (labels);
1955 slot = table->find_slot (&ecl, INSERT);
1956 if (!*slot)
1957 {
1958 *slot = XNEW (struct equiv_class_label);
1959 (*slot)->labels = labels;
1960 (*slot)->hashcode = ecl.hashcode;
1961 (*slot)->equivalence_class = 0;
1962 }
1963
1964 return *slot;
1965 }
1966
1967 /* Perform offline variable substitution.
1968
1969 This is a worst case quadratic time way of identifying variables
1970 that must have equivalent points-to sets, including those caused by
1971 static cycles, and single entry subgraphs, in the constraint graph.
1972
1973 The technique is described in "Exploiting Pointer and Location
1974 Equivalence to Optimize Pointer Analysis. In the 14th International
1975 Static Analysis Symposium (SAS), August 2007." It is known as the
1976 "HU" algorithm, and is equivalent to value numbering the collapsed
1977 constraint graph including evaluating unions.
1978
1979 The general method of finding equivalence classes is as follows:
1980 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1981 Initialize all non-REF nodes to be direct nodes.
1982 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1983 variable}
1984 For each constraint containing the dereference, we also do the same
1985 thing.
1986
1987 We then compute SCC's in the graph and unify nodes in the same SCC,
1988 including pts sets.
1989
1990 For each non-collapsed node x:
1991 Visit all unvisited explicit incoming edges.
1992 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1993 where y->x.
1994 Lookup the equivalence class for pts(x).
1995 If we found one, equivalence_class(x) = found class.
1996 Otherwise, equivalence_class(x) = new class, and new_class is
1997 added to the lookup table.
1998
1999 All direct nodes with the same equivalence class can be replaced
2000 with a single representative node.
2001 All unlabeled nodes (label == 0) are not pointers and all edges
2002 involving them can be eliminated.
2003 We perform these optimizations during rewrite_constraints
2004
2005 In addition to pointer equivalence class finding, we also perform
2006 location equivalence class finding. This is the set of variables
2007 that always appear together in points-to sets. We use this to
2008 compress the size of the points-to sets. */
2009
2010 /* Current maximum pointer equivalence class id. */
2011 static int pointer_equiv_class;
2012
2013 /* Current maximum location equivalence class id. */
2014 static int location_equiv_class;
2015
2016 /* Recursive routine to find strongly connected components in GRAPH,
2017 and label it's nodes with DFS numbers. */
2018
2019 static void
condense_visit(constraint_graph_t graph,struct scc_info * si,unsigned int n)2020 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2021 {
2022 unsigned int i;
2023 bitmap_iterator bi;
2024 unsigned int my_dfs;
2025
2026 gcc_checking_assert (si->node_mapping[n] == n);
2027 bitmap_set_bit (si->visited, n);
2028 si->dfs[n] = si->current_index ++;
2029 my_dfs = si->dfs[n];
2030
2031 /* Visit all the successors. */
2032 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2033 {
2034 unsigned int w = si->node_mapping[i];
2035
2036 if (bitmap_bit_p (si->deleted, w))
2037 continue;
2038
2039 if (!bitmap_bit_p (si->visited, w))
2040 condense_visit (graph, si, w);
2041
2042 unsigned int t = si->node_mapping[w];
2043 gcc_checking_assert (si->node_mapping[n] == n);
2044 if (si->dfs[t] < si->dfs[n])
2045 si->dfs[n] = si->dfs[t];
2046 }
2047
2048 /* Visit all the implicit predecessors. */
2049 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
2050 {
2051 unsigned int w = si->node_mapping[i];
2052
2053 if (bitmap_bit_p (si->deleted, w))
2054 continue;
2055
2056 if (!bitmap_bit_p (si->visited, w))
2057 condense_visit (graph, si, w);
2058
2059 unsigned int t = si->node_mapping[w];
2060 gcc_assert (si->node_mapping[n] == n);
2061 if (si->dfs[t] < si->dfs[n])
2062 si->dfs[n] = si->dfs[t];
2063 }
2064
2065 /* See if any components have been identified. */
2066 if (si->dfs[n] == my_dfs)
2067 {
2068 while (si->scc_stack.length () != 0
2069 && si->dfs[si->scc_stack.last ()] >= my_dfs)
2070 {
2071 unsigned int w = si->scc_stack.pop ();
2072 si->node_mapping[w] = n;
2073
2074 if (!bitmap_bit_p (graph->direct_nodes, w))
2075 bitmap_clear_bit (graph->direct_nodes, n);
2076
2077 /* Unify our nodes. */
2078 if (graph->preds[w])
2079 {
2080 if (!graph->preds[n])
2081 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2082 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2083 }
2084 if (graph->implicit_preds[w])
2085 {
2086 if (!graph->implicit_preds[n])
2087 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2088 bitmap_ior_into (graph->implicit_preds[n],
2089 graph->implicit_preds[w]);
2090 }
2091 if (graph->points_to[w])
2092 {
2093 if (!graph->points_to[n])
2094 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2095 bitmap_ior_into (graph->points_to[n],
2096 graph->points_to[w]);
2097 }
2098 }
2099 bitmap_set_bit (si->deleted, n);
2100 }
2101 else
2102 si->scc_stack.safe_push (n);
2103 }
2104
2105 /* Label pointer equivalences.
2106
2107 This performs a value numbering of the constraint graph to
2108 discover which variables will always have the same points-to sets
2109 under the current set of constraints.
2110
2111 The way it value numbers is to store the set of points-to bits
2112 generated by the constraints and graph edges. This is just used as a
2113 hash and equality comparison. The *actual set of points-to bits* is
2114 completely irrelevant, in that we don't care about being able to
2115 extract them later.
2116
2117 The equality values (currently bitmaps) just have to satisfy a few
2118 constraints, the main ones being:
2119 1. The combining operation must be order independent.
2120 2. The end result of a given set of operations must be unique iff the
2121 combination of input values is unique
2122 3. Hashable. */
2123
2124 static void
label_visit(constraint_graph_t graph,struct scc_info * si,unsigned int n)2125 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2126 {
2127 unsigned int i, first_pred;
2128 bitmap_iterator bi;
2129
2130 bitmap_set_bit (si->visited, n);
2131
2132 /* Label and union our incoming edges's points to sets. */
2133 first_pred = -1U;
2134 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2135 {
2136 unsigned int w = si->node_mapping[i];
2137 if (!bitmap_bit_p (si->visited, w))
2138 label_visit (graph, si, w);
2139
2140 /* Skip unused edges */
2141 if (w == n || graph->pointer_label[w] == 0)
2142 continue;
2143
2144 if (graph->points_to[w])
2145 {
2146 if (!graph->points_to[n])
2147 {
2148 if (first_pred == -1U)
2149 first_pred = w;
2150 else
2151 {
2152 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2153 bitmap_ior (graph->points_to[n],
2154 graph->points_to[first_pred],
2155 graph->points_to[w]);
2156 }
2157 }
2158 else
2159 bitmap_ior_into (graph->points_to[n], graph->points_to[w]);
2160 }
2161 }
2162
2163 /* Indirect nodes get fresh variables and a new pointer equiv class. */
2164 if (!bitmap_bit_p (graph->direct_nodes, n))
2165 {
2166 if (!graph->points_to[n])
2167 {
2168 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2169 if (first_pred != -1U)
2170 bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
2171 }
2172 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2173 graph->pointer_label[n] = pointer_equiv_class++;
2174 equiv_class_label_t ecl;
2175 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
2176 graph->points_to[n]);
2177 ecl->equivalence_class = graph->pointer_label[n];
2178 return;
2179 }
2180
2181 /* If there was only a single non-empty predecessor the pointer equiv
2182 class is the same. */
2183 if (!graph->points_to[n])
2184 {
2185 if (first_pred != -1U)
2186 {
2187 graph->pointer_label[n] = graph->pointer_label[first_pred];
2188 graph->points_to[n] = graph->points_to[first_pred];
2189 }
2190 return;
2191 }
2192
2193 if (!bitmap_empty_p (graph->points_to[n]))
2194 {
2195 equiv_class_label_t ecl;
2196 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
2197 graph->points_to[n]);
2198 if (ecl->equivalence_class == 0)
2199 ecl->equivalence_class = pointer_equiv_class++;
2200 else
2201 {
2202 BITMAP_FREE (graph->points_to[n]);
2203 graph->points_to[n] = ecl->labels;
2204 }
2205 graph->pointer_label[n] = ecl->equivalence_class;
2206 }
2207 }
2208
2209 /* Print the pred graph in dot format. */
2210
2211 static void
dump_pred_graph(struct scc_info * si,FILE * file)2212 dump_pred_graph (struct scc_info *si, FILE *file)
2213 {
2214 unsigned int i;
2215
2216 /* Only print the graph if it has already been initialized: */
2217 if (!graph)
2218 return;
2219
2220 /* Prints the header of the dot file: */
2221 fprintf (file, "strict digraph {\n");
2222 fprintf (file, " node [\n shape = box\n ]\n");
2223 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
2224 fprintf (file, "\n // List of nodes and complex constraints in "
2225 "the constraint graph:\n");
2226
2227 /* The next lines print the nodes in the graph together with the
2228 complex constraints attached to them. */
2229 for (i = 1; i < graph->size; i++)
2230 {
2231 if (i == FIRST_REF_NODE)
2232 continue;
2233 if (si->node_mapping[i] != i)
2234 continue;
2235 if (i < FIRST_REF_NODE)
2236 fprintf (file, "\"%s\"", get_varinfo (i)->name);
2237 else
2238 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
2239 if (graph->points_to[i]
2240 && !bitmap_empty_p (graph->points_to[i]))
2241 {
2242 fprintf (file, "[label=\"%s = {", get_varinfo (i)->name);
2243 unsigned j;
2244 bitmap_iterator bi;
2245 EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi)
2246 fprintf (file, " %d", j);
2247 fprintf (file, " }\"]");
2248 }
2249 fprintf (file, ";\n");
2250 }
2251
2252 /* Go over the edges. */
2253 fprintf (file, "\n // Edges in the constraint graph:\n");
2254 for (i = 1; i < graph->size; i++)
2255 {
2256 unsigned j;
2257 bitmap_iterator bi;
2258 if (si->node_mapping[i] != i)
2259 continue;
2260 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
2261 {
2262 unsigned from = si->node_mapping[j];
2263 if (from < FIRST_REF_NODE)
2264 fprintf (file, "\"%s\"", get_varinfo (from)->name);
2265 else
2266 fprintf (file, "\"*%s\"", get_varinfo (from - FIRST_REF_NODE)->name);
2267 fprintf (file, " -> ");
2268 if (i < FIRST_REF_NODE)
2269 fprintf (file, "\"%s\"", get_varinfo (i)->name);
2270 else
2271 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
2272 fprintf (file, ";\n");
2273 }
2274 }
2275
2276 /* Prints the tail of the dot file. */
2277 fprintf (file, "}\n");
2278 }
2279
2280 /* Perform offline variable substitution, discovering equivalence
2281 classes, and eliminating non-pointer variables. */
2282
2283 static struct scc_info *
perform_var_substitution(constraint_graph_t graph)2284 perform_var_substitution (constraint_graph_t graph)
2285 {
2286 unsigned int i;
2287 unsigned int size = graph->size;
2288 struct scc_info *si = init_scc_info (size);
2289
2290 bitmap_obstack_initialize (&iteration_obstack);
2291 pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
2292 location_equiv_class_table
2293 = new hash_table<equiv_class_hasher> (511);
2294 pointer_equiv_class = 1;
2295 location_equiv_class = 1;
2296
2297 /* Condense the nodes, which means to find SCC's, count incoming
2298 predecessors, and unite nodes in SCC's. */
2299 for (i = 1; i < FIRST_REF_NODE; i++)
2300 if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
2301 condense_visit (graph, si, si->node_mapping[i]);
2302
2303 if (dump_file && (dump_flags & TDF_GRAPH))
2304 {
2305 fprintf (dump_file, "\n\n// The constraint graph before var-substitution "
2306 "in dot format:\n");
2307 dump_pred_graph (si, dump_file);
2308 fprintf (dump_file, "\n\n");
2309 }
2310
2311 bitmap_clear (si->visited);
2312 /* Actually the label the nodes for pointer equivalences */
2313 for (i = 1; i < FIRST_REF_NODE; i++)
2314 if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
2315 label_visit (graph, si, si->node_mapping[i]);
2316
2317 /* Calculate location equivalence labels. */
2318 for (i = 1; i < FIRST_REF_NODE; i++)
2319 {
2320 bitmap pointed_by;
2321 bitmap_iterator bi;
2322 unsigned int j;
2323
2324 if (!graph->pointed_by[i])
2325 continue;
2326 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2327
2328 /* Translate the pointed-by mapping for pointer equivalence
2329 labels. */
2330 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2331 {
2332 bitmap_set_bit (pointed_by,
2333 graph->pointer_label[si->node_mapping[j]]);
2334 }
2335 /* The original pointed_by is now dead. */
2336 BITMAP_FREE (graph->pointed_by[i]);
2337
2338 /* Look up the location equivalence label if one exists, or make
2339 one otherwise. */
2340 equiv_class_label_t ecl;
2341 ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
2342 if (ecl->equivalence_class == 0)
2343 ecl->equivalence_class = location_equiv_class++;
2344 else
2345 {
2346 if (dump_file && (dump_flags & TDF_DETAILS))
2347 fprintf (dump_file, "Found location equivalence for node %s\n",
2348 get_varinfo (i)->name);
2349 BITMAP_FREE (pointed_by);
2350 }
2351 graph->loc_label[i] = ecl->equivalence_class;
2352
2353 }
2354
2355 if (dump_file && (dump_flags & TDF_DETAILS))
2356 for (i = 1; i < FIRST_REF_NODE; i++)
2357 {
2358 unsigned j = si->node_mapping[i];
2359 if (j != i)
2360 {
2361 fprintf (dump_file, "%s node id %d ",
2362 bitmap_bit_p (graph->direct_nodes, i)
2363 ? "Direct" : "Indirect", i);
2364 if (i < FIRST_REF_NODE)
2365 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
2366 else
2367 fprintf (dump_file, "\"*%s\"",
2368 get_varinfo (i - FIRST_REF_NODE)->name);
2369 fprintf (dump_file, " mapped to SCC leader node id %d ", j);
2370 if (j < FIRST_REF_NODE)
2371 fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name);
2372 else
2373 fprintf (dump_file, "\"*%s\"\n",
2374 get_varinfo (j - FIRST_REF_NODE)->name);
2375 }
2376 else
2377 {
2378 fprintf (dump_file,
2379 "Equivalence classes for %s node id %d ",
2380 bitmap_bit_p (graph->direct_nodes, i)
2381 ? "direct" : "indirect", i);
2382 if (i < FIRST_REF_NODE)
2383 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
2384 else
2385 fprintf (dump_file, "\"*%s\"",
2386 get_varinfo (i - FIRST_REF_NODE)->name);
2387 fprintf (dump_file,
2388 ": pointer %d, location %d\n",
2389 graph->pointer_label[i], graph->loc_label[i]);
2390 }
2391 }
2392
2393 /* Quickly eliminate our non-pointer variables. */
2394
2395 for (i = 1; i < FIRST_REF_NODE; i++)
2396 {
2397 unsigned int node = si->node_mapping[i];
2398
2399 if (graph->pointer_label[node] == 0)
2400 {
2401 if (dump_file && (dump_flags & TDF_DETAILS))
2402 fprintf (dump_file,
2403 "%s is a non-pointer variable, eliminating edges.\n",
2404 get_varinfo (node)->name);
2405 stats.nonpointer_vars++;
2406 clear_edges_for_node (graph, node);
2407 }
2408 }
2409
2410 return si;
2411 }
2412
2413 /* Free information that was only necessary for variable
2414 substitution. */
2415
2416 static void
free_var_substitution_info(struct scc_info * si)2417 free_var_substitution_info (struct scc_info *si)
2418 {
2419 free_scc_info (si);
2420 free (graph->pointer_label);
2421 free (graph->loc_label);
2422 free (graph->pointed_by);
2423 free (graph->points_to);
2424 free (graph->eq_rep);
2425 sbitmap_free (graph->direct_nodes);
2426 delete pointer_equiv_class_table;
2427 pointer_equiv_class_table = NULL;
2428 delete location_equiv_class_table;
2429 location_equiv_class_table = NULL;
2430 bitmap_obstack_release (&iteration_obstack);
2431 }
2432
2433 /* Return an existing node that is equivalent to NODE, which has
2434 equivalence class LABEL, if one exists. Return NODE otherwise. */
2435
2436 static unsigned int
find_equivalent_node(constraint_graph_t graph,unsigned int node,unsigned int label)2437 find_equivalent_node (constraint_graph_t graph,
2438 unsigned int node, unsigned int label)
2439 {
2440 /* If the address version of this variable is unused, we can
2441 substitute it for anything else with the same label.
2442 Otherwise, we know the pointers are equivalent, but not the
2443 locations, and we can unite them later. */
2444
2445 if (!bitmap_bit_p (graph->address_taken, node))
2446 {
2447 gcc_checking_assert (label < graph->size);
2448
2449 if (graph->eq_rep[label] != -1)
2450 {
2451 /* Unify the two variables since we know they are equivalent. */
2452 if (unite (graph->eq_rep[label], node))
2453 unify_nodes (graph, graph->eq_rep[label], node, false);
2454 return graph->eq_rep[label];
2455 }
2456 else
2457 {
2458 graph->eq_rep[label] = node;
2459 graph->pe_rep[label] = node;
2460 }
2461 }
2462 else
2463 {
2464 gcc_checking_assert (label < graph->size);
2465 graph->pe[node] = label;
2466 if (graph->pe_rep[label] == -1)
2467 graph->pe_rep[label] = node;
2468 }
2469
2470 return node;
2471 }
2472
2473 /* Unite pointer equivalent but not location equivalent nodes in
2474 GRAPH. This may only be performed once variable substitution is
2475 finished. */
2476
2477 static void
unite_pointer_equivalences(constraint_graph_t graph)2478 unite_pointer_equivalences (constraint_graph_t graph)
2479 {
2480 unsigned int i;
2481
2482 /* Go through the pointer equivalences and unite them to their
2483 representative, if they aren't already. */
2484 for (i = 1; i < FIRST_REF_NODE; i++)
2485 {
2486 unsigned int label = graph->pe[i];
2487 if (label)
2488 {
2489 int label_rep = graph->pe_rep[label];
2490
2491 if (label_rep == -1)
2492 continue;
2493
2494 label_rep = find (label_rep);
2495 if (label_rep >= 0 && unite (label_rep, find (i)))
2496 unify_nodes (graph, label_rep, i, false);
2497 }
2498 }
2499 }
2500
2501 /* Move complex constraints to the GRAPH nodes they belong to. */
2502
2503 static void
move_complex_constraints(constraint_graph_t graph)2504 move_complex_constraints (constraint_graph_t graph)
2505 {
2506 int i;
2507 constraint_t c;
2508
2509 FOR_EACH_VEC_ELT (constraints, i, c)
2510 {
2511 if (c)
2512 {
2513 struct constraint_expr lhs = c->lhs;
2514 struct constraint_expr rhs = c->rhs;
2515
2516 if (lhs.type == DEREF)
2517 {
2518 insert_into_complex (graph, lhs.var, c);
2519 }
2520 else if (rhs.type == DEREF)
2521 {
2522 if (!(get_varinfo (lhs.var)->is_special_var))
2523 insert_into_complex (graph, rhs.var, c);
2524 }
2525 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2526 && (lhs.offset != 0 || rhs.offset != 0))
2527 {
2528 insert_into_complex (graph, rhs.var, c);
2529 }
2530 }
2531 }
2532 }
2533
2534
2535 /* Optimize and rewrite complex constraints while performing
2536 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2537 result of perform_variable_substitution. */
2538
2539 static void
rewrite_constraints(constraint_graph_t graph,struct scc_info * si)2540 rewrite_constraints (constraint_graph_t graph,
2541 struct scc_info *si)
2542 {
2543 int i;
2544 constraint_t c;
2545
2546 if (flag_checking)
2547 {
2548 for (unsigned int j = 0; j < graph->size; j++)
2549 gcc_assert (find (j) == j);
2550 }
2551
2552 FOR_EACH_VEC_ELT (constraints, i, c)
2553 {
2554 struct constraint_expr lhs = c->lhs;
2555 struct constraint_expr rhs = c->rhs;
2556 unsigned int lhsvar = find (lhs.var);
2557 unsigned int rhsvar = find (rhs.var);
2558 unsigned int lhsnode, rhsnode;
2559 unsigned int lhslabel, rhslabel;
2560
2561 lhsnode = si->node_mapping[lhsvar];
2562 rhsnode = si->node_mapping[rhsvar];
2563 lhslabel = graph->pointer_label[lhsnode];
2564 rhslabel = graph->pointer_label[rhsnode];
2565
2566 /* See if it is really a non-pointer variable, and if so, ignore
2567 the constraint. */
2568 if (lhslabel == 0)
2569 {
2570 if (dump_file && (dump_flags & TDF_DETAILS))
2571 {
2572
2573 fprintf (dump_file, "%s is a non-pointer variable,"
2574 "ignoring constraint:",
2575 get_varinfo (lhs.var)->name);
2576 dump_constraint (dump_file, c);
2577 fprintf (dump_file, "\n");
2578 }
2579 constraints[i] = NULL;
2580 continue;
2581 }
2582
2583 if (rhslabel == 0)
2584 {
2585 if (dump_file && (dump_flags & TDF_DETAILS))
2586 {
2587
2588 fprintf (dump_file, "%s is a non-pointer variable,"
2589 "ignoring constraint:",
2590 get_varinfo (rhs.var)->name);
2591 dump_constraint (dump_file, c);
2592 fprintf (dump_file, "\n");
2593 }
2594 constraints[i] = NULL;
2595 continue;
2596 }
2597
2598 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2599 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2600 c->lhs.var = lhsvar;
2601 c->rhs.var = rhsvar;
2602 }
2603 }
2604
2605 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2606 part of an SCC, false otherwise. */
2607
2608 static bool
eliminate_indirect_cycles(unsigned int node)2609 eliminate_indirect_cycles (unsigned int node)
2610 {
2611 if (graph->indirect_cycles[node] != -1
2612 && !bitmap_empty_p (get_varinfo (node)->solution))
2613 {
2614 unsigned int i;
2615 auto_vec<unsigned> queue;
2616 int queuepos;
2617 unsigned int to = find (graph->indirect_cycles[node]);
2618 bitmap_iterator bi;
2619
2620 /* We can't touch the solution set and call unify_nodes
2621 at the same time, because unify_nodes is going to do
2622 bitmap unions into it. */
2623
2624 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2625 {
2626 if (find (i) == i && i != to)
2627 {
2628 if (unite (to, i))
2629 queue.safe_push (i);
2630 }
2631 }
2632
2633 for (queuepos = 0;
2634 queue.iterate (queuepos, &i);
2635 queuepos++)
2636 {
2637 unify_nodes (graph, to, i, true);
2638 }
2639 return true;
2640 }
2641 return false;
2642 }
2643
2644 /* Solve the constraint graph GRAPH using our worklist solver.
2645 This is based on the PW* family of solvers from the "Efficient Field
2646 Sensitive Pointer Analysis for C" paper.
2647 It works by iterating over all the graph nodes, processing the complex
2648 constraints and propagating the copy constraints, until everything stops
2649 changed. This corresponds to steps 6-8 in the solving list given above. */
2650
2651 static void
solve_graph(constraint_graph_t graph)2652 solve_graph (constraint_graph_t graph)
2653 {
2654 unsigned int size = graph->size;
2655 unsigned int i;
2656 bitmap pts;
2657
2658 changed = BITMAP_ALLOC (NULL);
2659
2660 /* Mark all initial non-collapsed nodes as changed. */
2661 for (i = 1; i < size; i++)
2662 {
2663 varinfo_t ivi = get_varinfo (i);
2664 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2665 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2666 || graph->complex[i].length () > 0))
2667 bitmap_set_bit (changed, i);
2668 }
2669
2670 /* Allocate a bitmap to be used to store the changed bits. */
2671 pts = BITMAP_ALLOC (&pta_obstack);
2672
2673 while (!bitmap_empty_p (changed))
2674 {
2675 unsigned int i;
2676 struct topo_info *ti = init_topo_info ();
2677 stats.iterations++;
2678
2679 bitmap_obstack_initialize (&iteration_obstack);
2680
2681 compute_topo_order (graph, ti);
2682
2683 while (ti->topo_order.length () != 0)
2684 {
2685
2686 i = ti->topo_order.pop ();
2687
2688 /* If this variable is not a representative, skip it. */
2689 if (find (i) != i)
2690 continue;
2691
2692 /* In certain indirect cycle cases, we may merge this
2693 variable to another. */
2694 if (eliminate_indirect_cycles (i) && find (i) != i)
2695 continue;
2696
2697 /* If the node has changed, we need to process the
2698 complex constraints and outgoing edges again. */
2699 if (bitmap_clear_bit (changed, i))
2700 {
2701 unsigned int j;
2702 constraint_t c;
2703 bitmap solution;
2704 vec<constraint_t> complex = graph->complex[i];
2705 varinfo_t vi = get_varinfo (i);
2706 bool solution_empty;
2707
2708 /* Compute the changed set of solution bits. If anything
2709 is in the solution just propagate that. */
2710 if (bitmap_bit_p (vi->solution, anything_id))
2711 {
2712 /* If anything is also in the old solution there is
2713 nothing to do.
2714 ??? But we shouldn't ended up with "changed" set ... */
2715 if (vi->oldsolution
2716 && bitmap_bit_p (vi->oldsolution, anything_id))
2717 continue;
2718 bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2719 }
2720 else if (vi->oldsolution)
2721 bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2722 else
2723 bitmap_copy (pts, vi->solution);
2724
2725 if (bitmap_empty_p (pts))
2726 continue;
2727
2728 if (vi->oldsolution)
2729 bitmap_ior_into (vi->oldsolution, pts);
2730 else
2731 {
2732 vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2733 bitmap_copy (vi->oldsolution, pts);
2734 }
2735
2736 solution = vi->solution;
2737 solution_empty = bitmap_empty_p (solution);
2738
2739 /* Process the complex constraints */
2740 bitmap expanded_pts = NULL;
2741 FOR_EACH_VEC_ELT (complex, j, c)
2742 {
2743 /* XXX: This is going to unsort the constraints in
2744 some cases, which will occasionally add duplicate
2745 constraints during unification. This does not
2746 affect correctness. */
2747 c->lhs.var = find (c->lhs.var);
2748 c->rhs.var = find (c->rhs.var);
2749
2750 /* The only complex constraint that can change our
2751 solution to non-empty, given an empty solution,
2752 is a constraint where the lhs side is receiving
2753 some set from elsewhere. */
2754 if (!solution_empty || c->lhs.type != DEREF)
2755 do_complex_constraint (graph, c, pts, &expanded_pts);
2756 }
2757 BITMAP_FREE (expanded_pts);
2758
2759 solution_empty = bitmap_empty_p (solution);
2760
2761 if (!solution_empty)
2762 {
2763 bitmap_iterator bi;
2764 unsigned eff_escaped_id = find (escaped_id);
2765
2766 /* Propagate solution to all successors. */
2767 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2768 0, j, bi)
2769 {
2770 bitmap tmp;
2771 bool flag;
2772
2773 unsigned int to = find (j);
2774 tmp = get_varinfo (to)->solution;
2775 flag = false;
2776
2777 /* Don't try to propagate to ourselves. */
2778 if (to == i)
2779 continue;
2780
2781 /* If we propagate from ESCAPED use ESCAPED as
2782 placeholder. */
2783 if (i == eff_escaped_id)
2784 flag = bitmap_set_bit (tmp, escaped_id);
2785 else
2786 flag = bitmap_ior_into (tmp, pts);
2787
2788 if (flag)
2789 bitmap_set_bit (changed, to);
2790 }
2791 }
2792 }
2793 }
2794 free_topo_info (ti);
2795 bitmap_obstack_release (&iteration_obstack);
2796 }
2797
2798 BITMAP_FREE (pts);
2799 BITMAP_FREE (changed);
2800 bitmap_obstack_release (&oldpta_obstack);
2801 }
2802
2803 /* Map from trees to variable infos. */
2804 static hash_map<tree, varinfo_t> *vi_for_tree;
2805
2806
2807 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2808
2809 static void
insert_vi_for_tree(tree t,varinfo_t vi)2810 insert_vi_for_tree (tree t, varinfo_t vi)
2811 {
2812 gcc_assert (vi);
2813 gcc_assert (!vi_for_tree->put (t, vi));
2814 }
2815
2816 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2817 exist in the map, return NULL, otherwise, return the varinfo we found. */
2818
2819 static varinfo_t
lookup_vi_for_tree(tree t)2820 lookup_vi_for_tree (tree t)
2821 {
2822 varinfo_t *slot = vi_for_tree->get (t);
2823 if (slot == NULL)
2824 return NULL;
2825
2826 return *slot;
2827 }
2828
2829 /* Return a printable name for DECL */
2830
2831 static const char *
alias_get_name(tree decl)2832 alias_get_name (tree decl)
2833 {
2834 const char *res = NULL;
2835 char *temp;
2836
2837 if (!dump_file)
2838 return "NULL";
2839
2840 if (TREE_CODE (decl) == SSA_NAME)
2841 {
2842 res = get_name (decl);
2843 if (res)
2844 temp = xasprintf ("%s_%u", res, SSA_NAME_VERSION (decl));
2845 else
2846 temp = xasprintf ("_%u", SSA_NAME_VERSION (decl));
2847 res = ggc_strdup (temp);
2848 free (temp);
2849 }
2850 else if (DECL_P (decl))
2851 {
2852 if (DECL_ASSEMBLER_NAME_SET_P (decl))
2853 res = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
2854 else
2855 {
2856 res = get_name (decl);
2857 if (!res)
2858 {
2859 temp = xasprintf ("D.%u", DECL_UID (decl));
2860 res = ggc_strdup (temp);
2861 free (temp);
2862 }
2863 }
2864 }
2865 if (res != NULL)
2866 return res;
2867
2868 return "NULL";
2869 }
2870
2871 /* Find the variable id for tree T in the map.
2872 If T doesn't exist in the map, create an entry for it and return it. */
2873
2874 static varinfo_t
get_vi_for_tree(tree t)2875 get_vi_for_tree (tree t)
2876 {
2877 varinfo_t *slot = vi_for_tree->get (t);
2878 if (slot == NULL)
2879 {
2880 unsigned int id = create_variable_info_for (t, alias_get_name (t), false);
2881 return get_varinfo (id);
2882 }
2883
2884 return *slot;
2885 }
2886
2887 /* Get a scalar constraint expression for a new temporary variable. */
2888
2889 static struct constraint_expr
new_scalar_tmp_constraint_exp(const char * name,bool add_id)2890 new_scalar_tmp_constraint_exp (const char *name, bool add_id)
2891 {
2892 struct constraint_expr tmp;
2893 varinfo_t vi;
2894
2895 vi = new_var_info (NULL_TREE, name, add_id);
2896 vi->offset = 0;
2897 vi->size = -1;
2898 vi->fullsize = -1;
2899 vi->is_full_var = 1;
2900
2901 tmp.var = vi->id;
2902 tmp.type = SCALAR;
2903 tmp.offset = 0;
2904
2905 return tmp;
2906 }
2907
2908 /* Get a constraint expression vector from an SSA_VAR_P node.
2909 If address_p is true, the result will be taken its address of. */
2910
2911 static void
get_constraint_for_ssa_var(tree t,vec<ce_s> * results,bool address_p)2912 get_constraint_for_ssa_var (tree t, vec<ce_s> *results, bool address_p)
2913 {
2914 struct constraint_expr cexpr;
2915 varinfo_t vi;
2916
2917 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2918 gcc_assert (TREE_CODE (t) == SSA_NAME || DECL_P (t));
2919
2920 /* For parameters, get at the points-to set for the actual parm
2921 decl. */
2922 if (TREE_CODE (t) == SSA_NAME
2923 && SSA_NAME_IS_DEFAULT_DEF (t)
2924 && (TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2925 || TREE_CODE (SSA_NAME_VAR (t)) == RESULT_DECL))
2926 {
2927 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2928 return;
2929 }
2930
2931 /* For global variables resort to the alias target. */
2932 if (TREE_CODE (t) == VAR_DECL
2933 && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
2934 {
2935 varpool_node *node = varpool_node::get (t);
2936 if (node && node->alias && node->analyzed)
2937 {
2938 node = node->ultimate_alias_target ();
2939 /* Canonicalize the PT uid of all aliases to the ultimate target.
2940 ??? Hopefully the set of aliases can't change in a way that
2941 changes the ultimate alias target. */
2942 gcc_assert ((! DECL_PT_UID_SET_P (node->decl)
2943 || DECL_PT_UID (node->decl) == DECL_UID (node->decl))
2944 && (! DECL_PT_UID_SET_P (t)
2945 || DECL_PT_UID (t) == DECL_UID (node->decl)));
2946 DECL_PT_UID (t) = DECL_UID (node->decl);
2947 t = node->decl;
2948 }
2949 }
2950
2951 vi = get_vi_for_tree (t);
2952 cexpr.var = vi->id;
2953 cexpr.type = SCALAR;
2954 cexpr.offset = 0;
2955
2956 /* If we are not taking the address of the constraint expr, add all
2957 sub-fiels of the variable as well. */
2958 if (!address_p
2959 && !vi->is_full_var)
2960 {
2961 for (; vi; vi = vi_next (vi))
2962 {
2963 cexpr.var = vi->id;
2964 results->safe_push (cexpr);
2965 }
2966 return;
2967 }
2968
2969 results->safe_push (cexpr);
2970 }
2971
2972 /* Process constraint T, performing various simplifications and then
2973 adding it to our list of overall constraints. */
2974
2975 static void
process_constraint(constraint_t t)2976 process_constraint (constraint_t t)
2977 {
2978 struct constraint_expr rhs = t->rhs;
2979 struct constraint_expr lhs = t->lhs;
2980
2981 gcc_assert (rhs.var < varmap.length ());
2982 gcc_assert (lhs.var < varmap.length ());
2983
2984 /* If we didn't get any useful constraint from the lhs we get
2985 &ANYTHING as fallback from get_constraint_for. Deal with
2986 it here by turning it into *ANYTHING. */
2987 if (lhs.type == ADDRESSOF
2988 && lhs.var == anything_id)
2989 lhs.type = DEREF;
2990
2991 /* ADDRESSOF on the lhs is invalid. */
2992 gcc_assert (lhs.type != ADDRESSOF);
2993
2994 /* We shouldn't add constraints from things that cannot have pointers.
2995 It's not completely trivial to avoid in the callers, so do it here. */
2996 if (rhs.type != ADDRESSOF
2997 && !get_varinfo (rhs.var)->may_have_pointers)
2998 return;
2999
3000 /* Likewise adding to the solution of a non-pointer var isn't useful. */
3001 if (!get_varinfo (lhs.var)->may_have_pointers)
3002 return;
3003
3004 /* This can happen in our IR with things like n->a = *p */
3005 if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
3006 {
3007 /* Split into tmp = *rhs, *lhs = tmp */
3008 struct constraint_expr tmplhs;
3009 tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp", true);
3010 process_constraint (new_constraint (tmplhs, rhs));
3011 process_constraint (new_constraint (lhs, tmplhs));
3012 }
3013 else if ((rhs.type != SCALAR || rhs.offset != 0) && lhs.type == DEREF)
3014 {
3015 /* Split into tmp = &rhs, *lhs = tmp */
3016 struct constraint_expr tmplhs;
3017 tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp", true);
3018 process_constraint (new_constraint (tmplhs, rhs));
3019 process_constraint (new_constraint (lhs, tmplhs));
3020 }
3021 else
3022 {
3023 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
3024 constraints.safe_push (t);
3025 }
3026 }
3027
3028
3029 /* Return the position, in bits, of FIELD_DECL from the beginning of its
3030 structure. */
3031
3032 static HOST_WIDE_INT
bitpos_of_field(const tree fdecl)3033 bitpos_of_field (const tree fdecl)
3034 {
3035 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl))
3036 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl)))
3037 return -1;
3038
3039 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl)) * BITS_PER_UNIT
3040 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl)));
3041 }
3042
3043
3044 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
3045 resulting constraint expressions in *RESULTS. */
3046
3047 static void
get_constraint_for_ptr_offset(tree ptr,tree offset,vec<ce_s> * results)3048 get_constraint_for_ptr_offset (tree ptr, tree offset,
3049 vec<ce_s> *results)
3050 {
3051 struct constraint_expr c;
3052 unsigned int j, n;
3053 HOST_WIDE_INT rhsoffset;
3054
3055 /* If we do not do field-sensitive PTA adding offsets to pointers
3056 does not change the points-to solution. */
3057 if (!use_field_sensitive)
3058 {
3059 get_constraint_for_rhs (ptr, results);
3060 return;
3061 }
3062
3063 /* If the offset is not a non-negative integer constant that fits
3064 in a HOST_WIDE_INT, we have to fall back to a conservative
3065 solution which includes all sub-fields of all pointed-to
3066 variables of ptr. */
3067 if (offset == NULL_TREE
3068 || TREE_CODE (offset) != INTEGER_CST)
3069 rhsoffset = UNKNOWN_OFFSET;
3070 else
3071 {
3072 /* Sign-extend the offset. */
3073 offset_int soffset = offset_int::from (offset, SIGNED);
3074 if (!wi::fits_shwi_p (soffset))
3075 rhsoffset = UNKNOWN_OFFSET;
3076 else
3077 {
3078 /* Make sure the bit-offset also fits. */
3079 HOST_WIDE_INT rhsunitoffset = soffset.to_shwi ();
3080 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
3081 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
3082 rhsoffset = UNKNOWN_OFFSET;
3083 }
3084 }
3085
3086 get_constraint_for_rhs (ptr, results);
3087 if (rhsoffset == 0)
3088 return;
3089
3090 /* As we are eventually appending to the solution do not use
3091 vec::iterate here. */
3092 n = results->length ();
3093 for (j = 0; j < n; j++)
3094 {
3095 varinfo_t curr;
3096 c = (*results)[j];
3097 curr = get_varinfo (c.var);
3098
3099 if (c.type == ADDRESSOF
3100 /* If this varinfo represents a full variable just use it. */
3101 && curr->is_full_var)
3102 ;
3103 else if (c.type == ADDRESSOF
3104 /* If we do not know the offset add all subfields. */
3105 && rhsoffset == UNKNOWN_OFFSET)
3106 {
3107 varinfo_t temp = get_varinfo (curr->head);
3108 do
3109 {
3110 struct constraint_expr c2;
3111 c2.var = temp->id;
3112 c2.type = ADDRESSOF;
3113 c2.offset = 0;
3114 if (c2.var != c.var)
3115 results->safe_push (c2);
3116 temp = vi_next (temp);
3117 }
3118 while (temp);
3119 }
3120 else if (c.type == ADDRESSOF)
3121 {
3122 varinfo_t temp;
3123 unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
3124
3125 /* If curr->offset + rhsoffset is less than zero adjust it. */
3126 if (rhsoffset < 0
3127 && curr->offset < offset)
3128 offset = 0;
3129
3130 /* We have to include all fields that overlap the current
3131 field shifted by rhsoffset. And we include at least
3132 the last or the first field of the variable to represent
3133 reachability of off-bound addresses, in particular &object + 1,
3134 conservatively correct. */
3135 temp = first_or_preceding_vi_for_offset (curr, offset);
3136 c.var = temp->id;
3137 c.offset = 0;
3138 temp = vi_next (temp);
3139 while (temp
3140 && temp->offset < offset + curr->size)
3141 {
3142 struct constraint_expr c2;
3143 c2.var = temp->id;
3144 c2.type = ADDRESSOF;
3145 c2.offset = 0;
3146 results->safe_push (c2);
3147 temp = vi_next (temp);
3148 }
3149 }
3150 else if (c.type == SCALAR)
3151 {
3152 gcc_assert (c.offset == 0);
3153 c.offset = rhsoffset;
3154 }
3155 else
3156 /* We shouldn't get any DEREFs here. */
3157 gcc_unreachable ();
3158
3159 (*results)[j] = c;
3160 }
3161 }
3162
3163
3164 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3165 If address_p is true the result will be taken its address of.
3166 If lhs_p is true then the constraint expression is assumed to be used
3167 as the lhs. */
3168
3169 static void
get_constraint_for_component_ref(tree t,vec<ce_s> * results,bool address_p,bool lhs_p)3170 get_constraint_for_component_ref (tree t, vec<ce_s> *results,
3171 bool address_p, bool lhs_p)
3172 {
3173 tree orig_t = t;
3174 HOST_WIDE_INT bitsize = -1;
3175 HOST_WIDE_INT bitmaxsize = -1;
3176 HOST_WIDE_INT bitpos;
3177 bool reverse;
3178 tree forzero;
3179
3180 /* Some people like to do cute things like take the address of
3181 &0->a.b */
3182 forzero = t;
3183 while (handled_component_p (forzero)
3184 || INDIRECT_REF_P (forzero)
3185 || TREE_CODE (forzero) == MEM_REF)
3186 forzero = TREE_OPERAND (forzero, 0);
3187
3188 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
3189 {
3190 struct constraint_expr temp;
3191
3192 temp.offset = 0;
3193 temp.var = integer_id;
3194 temp.type = SCALAR;
3195 results->safe_push (temp);
3196 return;
3197 }
3198
3199 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize, &reverse);
3200
3201 /* Pretend to take the address of the base, we'll take care of
3202 adding the required subset of sub-fields below. */
3203 get_constraint_for_1 (t, results, true, lhs_p);
3204 gcc_assert (results->length () == 1);
3205 struct constraint_expr &result = results->last ();
3206
3207 if (result.type == SCALAR
3208 && get_varinfo (result.var)->is_full_var)
3209 /* For single-field vars do not bother about the offset. */
3210 result.offset = 0;
3211 else if (result.type == SCALAR)
3212 {
3213 /* In languages like C, you can access one past the end of an
3214 array. You aren't allowed to dereference it, so we can
3215 ignore this constraint. When we handle pointer subtraction,
3216 we may have to do something cute here. */
3217
3218 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result.var)->fullsize
3219 && bitmaxsize != 0)
3220 {
3221 /* It's also not true that the constraint will actually start at the
3222 right offset, it may start in some padding. We only care about
3223 setting the constraint to the first actual field it touches, so
3224 walk to find it. */
3225 struct constraint_expr cexpr = result;
3226 varinfo_t curr;
3227 results->pop ();
3228 cexpr.offset = 0;
3229 for (curr = get_varinfo (cexpr.var); curr; curr = vi_next (curr))
3230 {
3231 if (ranges_overlap_p (curr->offset, curr->size,
3232 bitpos, bitmaxsize))
3233 {
3234 cexpr.var = curr->id;
3235 results->safe_push (cexpr);
3236 if (address_p)
3237 break;
3238 }
3239 }
3240 /* If we are going to take the address of this field then
3241 to be able to compute reachability correctly add at least
3242 the last field of the variable. */
3243 if (address_p && results->length () == 0)
3244 {
3245 curr = get_varinfo (cexpr.var);
3246 while (curr->next != 0)
3247 curr = vi_next (curr);
3248 cexpr.var = curr->id;
3249 results->safe_push (cexpr);
3250 }
3251 else if (results->length () == 0)
3252 /* Assert that we found *some* field there. The user couldn't be
3253 accessing *only* padding. */
3254 /* Still the user could access one past the end of an array
3255 embedded in a struct resulting in accessing *only* padding. */
3256 /* Or accessing only padding via type-punning to a type
3257 that has a filed just in padding space. */
3258 {
3259 cexpr.type = SCALAR;
3260 cexpr.var = anything_id;
3261 cexpr.offset = 0;
3262 results->safe_push (cexpr);
3263 }
3264 }
3265 else if (bitmaxsize == 0)
3266 {
3267 if (dump_file && (dump_flags & TDF_DETAILS))
3268 fprintf (dump_file, "Access to zero-sized part of variable,"
3269 "ignoring\n");
3270 }
3271 else
3272 if (dump_file && (dump_flags & TDF_DETAILS))
3273 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3274 }
3275 else if (result.type == DEREF)
3276 {
3277 /* If we do not know exactly where the access goes say so. Note
3278 that only for non-structure accesses we know that we access
3279 at most one subfiled of any variable. */
3280 if (bitpos == -1
3281 || bitsize != bitmaxsize
3282 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t))
3283 || result.offset == UNKNOWN_OFFSET)
3284 result.offset = UNKNOWN_OFFSET;
3285 else
3286 result.offset += bitpos;
3287 }
3288 else if (result.type == ADDRESSOF)
3289 {
3290 /* We can end up here for component references on a
3291 VIEW_CONVERT_EXPR <>(&foobar). */
3292 result.type = SCALAR;
3293 result.var = anything_id;
3294 result.offset = 0;
3295 }
3296 else
3297 gcc_unreachable ();
3298 }
3299
3300
3301 /* Dereference the constraint expression CONS, and return the result.
3302 DEREF (ADDRESSOF) = SCALAR
3303 DEREF (SCALAR) = DEREF
3304 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3305 This is needed so that we can handle dereferencing DEREF constraints. */
3306
3307 static void
do_deref(vec<ce_s> * constraints)3308 do_deref (vec<ce_s> *constraints)
3309 {
3310 struct constraint_expr *c;
3311 unsigned int i = 0;
3312
3313 FOR_EACH_VEC_ELT (*constraints, i, c)
3314 {
3315 if (c->type == SCALAR)
3316 c->type = DEREF;
3317 else if (c->type == ADDRESSOF)
3318 c->type = SCALAR;
3319 else if (c->type == DEREF)
3320 {
3321 struct constraint_expr tmplhs;
3322 tmplhs = new_scalar_tmp_constraint_exp ("dereftmp", true);
3323 process_constraint (new_constraint (tmplhs, *c));
3324 c->var = tmplhs.var;
3325 }
3326 else
3327 gcc_unreachable ();
3328 }
3329 }
3330
3331 /* Given a tree T, return the constraint expression for taking the
3332 address of it. */
3333
3334 static void
get_constraint_for_address_of(tree t,vec<ce_s> * results)3335 get_constraint_for_address_of (tree t, vec<ce_s> *results)
3336 {
3337 struct constraint_expr *c;
3338 unsigned int i;
3339
3340 get_constraint_for_1 (t, results, true, true);
3341
3342 FOR_EACH_VEC_ELT (*results, i, c)
3343 {
3344 if (c->type == DEREF)
3345 c->type = SCALAR;
3346 else
3347 c->type = ADDRESSOF;
3348 }
3349 }
3350
3351 /* Given a tree T, return the constraint expression for it. */
3352
3353 static void
get_constraint_for_1(tree t,vec<ce_s> * results,bool address_p,bool lhs_p)3354 get_constraint_for_1 (tree t, vec<ce_s> *results, bool address_p,
3355 bool lhs_p)
3356 {
3357 struct constraint_expr temp;
3358
3359 /* x = integer is all glommed to a single variable, which doesn't
3360 point to anything by itself. That is, of course, unless it is an
3361 integer constant being treated as a pointer, in which case, we
3362 will return that this is really the addressof anything. This
3363 happens below, since it will fall into the default case. The only
3364 case we know something about an integer treated like a pointer is
3365 when it is the NULL pointer, and then we just say it points to
3366 NULL.
3367
3368 Do not do that if -fno-delete-null-pointer-checks though, because
3369 in that case *NULL does not fail, so it _should_ alias *anything.
3370 It is not worth adding a new option or renaming the existing one,
3371 since this case is relatively obscure. */
3372 if ((TREE_CODE (t) == INTEGER_CST
3373 && integer_zerop (t))
3374 /* The only valid CONSTRUCTORs in gimple with pointer typed
3375 elements are zero-initializer. But in IPA mode we also
3376 process global initializers, so verify at least. */
3377 || (TREE_CODE (t) == CONSTRUCTOR
3378 && CONSTRUCTOR_NELTS (t) == 0))
3379 {
3380 if (flag_delete_null_pointer_checks)
3381 temp.var = nothing_id;
3382 else
3383 temp.var = nonlocal_id;
3384 temp.type = ADDRESSOF;
3385 temp.offset = 0;
3386 results->safe_push (temp);
3387 return;
3388 }
3389
3390 /* String constants are read-only, ideally we'd have a CONST_DECL
3391 for those. */
3392 if (TREE_CODE (t) == STRING_CST)
3393 {
3394 temp.var = string_id;
3395 temp.type = SCALAR;
3396 temp.offset = 0;
3397 results->safe_push (temp);
3398 return;
3399 }
3400
3401 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3402 {
3403 case tcc_expression:
3404 {
3405 switch (TREE_CODE (t))
3406 {
3407 case ADDR_EXPR:
3408 get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3409 return;
3410 default:;
3411 }
3412 break;
3413 }
3414 case tcc_reference:
3415 {
3416 switch (TREE_CODE (t))
3417 {
3418 case MEM_REF:
3419 {
3420 struct constraint_expr cs;
3421 varinfo_t vi, curr;
3422 get_constraint_for_ptr_offset (TREE_OPERAND (t, 0),
3423 TREE_OPERAND (t, 1), results);
3424 do_deref (results);
3425
3426 /* If we are not taking the address then make sure to process
3427 all subvariables we might access. */
3428 if (address_p)
3429 return;
3430
3431 cs = results->last ();
3432 if (cs.type == DEREF
3433 && type_can_have_subvars (TREE_TYPE (t)))
3434 {
3435 /* For dereferences this means we have to defer it
3436 to solving time. */
3437 results->last ().offset = UNKNOWN_OFFSET;
3438 return;
3439 }
3440 if (cs.type != SCALAR)
3441 return;
3442
3443 vi = get_varinfo (cs.var);
3444 curr = vi_next (vi);
3445 if (!vi->is_full_var
3446 && curr)
3447 {
3448 unsigned HOST_WIDE_INT size;
3449 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t))))
3450 size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t)));
3451 else
3452 size = -1;
3453 for (; curr; curr = vi_next (curr))
3454 {
3455 if (curr->offset - vi->offset < size)
3456 {
3457 cs.var = curr->id;
3458 results->safe_push (cs);
3459 }
3460 else
3461 break;
3462 }
3463 }
3464 return;
3465 }
3466 case ARRAY_REF:
3467 case ARRAY_RANGE_REF:
3468 case COMPONENT_REF:
3469 case IMAGPART_EXPR:
3470 case REALPART_EXPR:
3471 case BIT_FIELD_REF:
3472 get_constraint_for_component_ref (t, results, address_p, lhs_p);
3473 return;
3474 case VIEW_CONVERT_EXPR:
3475 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p,
3476 lhs_p);
3477 return;
3478 /* We are missing handling for TARGET_MEM_REF here. */
3479 default:;
3480 }
3481 break;
3482 }
3483 case tcc_exceptional:
3484 {
3485 switch (TREE_CODE (t))
3486 {
3487 case SSA_NAME:
3488 {
3489 get_constraint_for_ssa_var (t, results, address_p);
3490 return;
3491 }
3492 case CONSTRUCTOR:
3493 {
3494 unsigned int i;
3495 tree val;
3496 auto_vec<ce_s> tmp;
3497 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t), i, val)
3498 {
3499 struct constraint_expr *rhsp;
3500 unsigned j;
3501 get_constraint_for_1 (val, &tmp, address_p, lhs_p);
3502 FOR_EACH_VEC_ELT (tmp, j, rhsp)
3503 results->safe_push (*rhsp);
3504 tmp.truncate (0);
3505 }
3506 /* We do not know whether the constructor was complete,
3507 so technically we have to add &NOTHING or &ANYTHING
3508 like we do for an empty constructor as well. */
3509 return;
3510 }
3511 default:;
3512 }
3513 break;
3514 }
3515 case tcc_declaration:
3516 {
3517 get_constraint_for_ssa_var (t, results, address_p);
3518 return;
3519 }
3520 case tcc_constant:
3521 {
3522 /* We cannot refer to automatic variables through constants. */
3523 temp.type = ADDRESSOF;
3524 temp.var = nonlocal_id;
3525 temp.offset = 0;
3526 results->safe_push (temp);
3527 return;
3528 }
3529 default:;
3530 }
3531
3532 /* The default fallback is a constraint from anything. */
3533 temp.type = ADDRESSOF;
3534 temp.var = anything_id;
3535 temp.offset = 0;
3536 results->safe_push (temp);
3537 }
3538
3539 /* Given a gimple tree T, return the constraint expression vector for it. */
3540
3541 static void
get_constraint_for(tree t,vec<ce_s> * results)3542 get_constraint_for (tree t, vec<ce_s> *results)
3543 {
3544 gcc_assert (results->length () == 0);
3545
3546 get_constraint_for_1 (t, results, false, true);
3547 }
3548
3549 /* Given a gimple tree T, return the constraint expression vector for it
3550 to be used as the rhs of a constraint. */
3551
3552 static void
get_constraint_for_rhs(tree t,vec<ce_s> * results)3553 get_constraint_for_rhs (tree t, vec<ce_s> *results)
3554 {
3555 gcc_assert (results->length () == 0);
3556
3557 get_constraint_for_1 (t, results, false, false);
3558 }
3559
3560
3561 /* Efficiently generates constraints from all entries in *RHSC to all
3562 entries in *LHSC. */
3563
3564 static void
process_all_all_constraints(vec<ce_s> lhsc,vec<ce_s> rhsc)3565 process_all_all_constraints (vec<ce_s> lhsc,
3566 vec<ce_s> rhsc)
3567 {
3568 struct constraint_expr *lhsp, *rhsp;
3569 unsigned i, j;
3570
3571 if (lhsc.length () <= 1 || rhsc.length () <= 1)
3572 {
3573 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
3574 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
3575 process_constraint (new_constraint (*lhsp, *rhsp));
3576 }
3577 else
3578 {
3579 struct constraint_expr tmp;
3580 tmp = new_scalar_tmp_constraint_exp ("allalltmp", true);
3581 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
3582 process_constraint (new_constraint (tmp, *rhsp));
3583 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
3584 process_constraint (new_constraint (*lhsp, tmp));
3585 }
3586 }
3587
3588 /* Handle aggregate copies by expanding into copies of the respective
3589 fields of the structures. */
3590
3591 static void
do_structure_copy(tree lhsop,tree rhsop)3592 do_structure_copy (tree lhsop, tree rhsop)
3593 {
3594 struct constraint_expr *lhsp, *rhsp;
3595 auto_vec<ce_s> lhsc;
3596 auto_vec<ce_s> rhsc;
3597 unsigned j;
3598
3599 get_constraint_for (lhsop, &lhsc);
3600 get_constraint_for_rhs (rhsop, &rhsc);
3601 lhsp = &lhsc[0];
3602 rhsp = &rhsc[0];
3603 if (lhsp->type == DEREF
3604 || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3605 || rhsp->type == DEREF)
3606 {
3607 if (lhsp->type == DEREF)
3608 {
3609 gcc_assert (lhsc.length () == 1);
3610 lhsp->offset = UNKNOWN_OFFSET;
3611 }
3612 if (rhsp->type == DEREF)
3613 {
3614 gcc_assert (rhsc.length () == 1);
3615 rhsp->offset = UNKNOWN_OFFSET;
3616 }
3617 process_all_all_constraints (lhsc, rhsc);
3618 }
3619 else if (lhsp->type == SCALAR
3620 && (rhsp->type == SCALAR
3621 || rhsp->type == ADDRESSOF))
3622 {
3623 HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
3624 HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
3625 bool reverse;
3626 unsigned k = 0;
3627 get_ref_base_and_extent (lhsop, &lhsoffset, &lhssize, &lhsmaxsize,
3628 &reverse);
3629 get_ref_base_and_extent (rhsop, &rhsoffset, &rhssize, &rhsmaxsize,
3630 &reverse);
3631 for (j = 0; lhsc.iterate (j, &lhsp);)
3632 {
3633 varinfo_t lhsv, rhsv;
3634 rhsp = &rhsc[k];
3635 lhsv = get_varinfo (lhsp->var);
3636 rhsv = get_varinfo (rhsp->var);
3637 if (lhsv->may_have_pointers
3638 && (lhsv->is_full_var
3639 || rhsv->is_full_var
3640 || ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3641 rhsv->offset + lhsoffset, rhsv->size)))
3642 process_constraint (new_constraint (*lhsp, *rhsp));
3643 if (!rhsv->is_full_var
3644 && (lhsv->is_full_var
3645 || (lhsv->offset + rhsoffset + lhsv->size
3646 > rhsv->offset + lhsoffset + rhsv->size)))
3647 {
3648 ++k;
3649 if (k >= rhsc.length ())
3650 break;
3651 }
3652 else
3653 ++j;
3654 }
3655 }
3656 else
3657 gcc_unreachable ();
3658 }
3659
3660 /* Create constraints ID = { rhsc }. */
3661
3662 static void
make_constraints_to(unsigned id,vec<ce_s> rhsc)3663 make_constraints_to (unsigned id, vec<ce_s> rhsc)
3664 {
3665 struct constraint_expr *c;
3666 struct constraint_expr includes;
3667 unsigned int j;
3668
3669 includes.var = id;
3670 includes.offset = 0;
3671 includes.type = SCALAR;
3672
3673 FOR_EACH_VEC_ELT (rhsc, j, c)
3674 process_constraint (new_constraint (includes, *c));
3675 }
3676
3677 /* Create a constraint ID = OP. */
3678
3679 static void
make_constraint_to(unsigned id,tree op)3680 make_constraint_to (unsigned id, tree op)
3681 {
3682 auto_vec<ce_s> rhsc;
3683 get_constraint_for_rhs (op, &rhsc);
3684 make_constraints_to (id, rhsc);
3685 }
3686
3687 /* Create a constraint ID = &FROM. */
3688
3689 static void
make_constraint_from(varinfo_t vi,int from)3690 make_constraint_from (varinfo_t vi, int from)
3691 {
3692 struct constraint_expr lhs, rhs;
3693
3694 lhs.var = vi->id;
3695 lhs.offset = 0;
3696 lhs.type = SCALAR;
3697
3698 rhs.var = from;
3699 rhs.offset = 0;
3700 rhs.type = ADDRESSOF;
3701 process_constraint (new_constraint (lhs, rhs));
3702 }
3703
3704 /* Create a constraint ID = FROM. */
3705
3706 static void
make_copy_constraint(varinfo_t vi,int from)3707 make_copy_constraint (varinfo_t vi, int from)
3708 {
3709 struct constraint_expr lhs, rhs;
3710
3711 lhs.var = vi->id;
3712 lhs.offset = 0;
3713 lhs.type = SCALAR;
3714
3715 rhs.var = from;
3716 rhs.offset = 0;
3717 rhs.type = SCALAR;
3718 process_constraint (new_constraint (lhs, rhs));
3719 }
3720
3721 /* Make constraints necessary to make OP escape. */
3722
3723 static void
make_escape_constraint(tree op)3724 make_escape_constraint (tree op)
3725 {
3726 make_constraint_to (escaped_id, op);
3727 }
3728
3729 /* Add constraints to that the solution of VI is transitively closed. */
3730
3731 static void
make_transitive_closure_constraints(varinfo_t vi)3732 make_transitive_closure_constraints (varinfo_t vi)
3733 {
3734 struct constraint_expr lhs, rhs;
3735
3736 /* VAR = *(VAR + UNKNOWN); */
3737 lhs.type = SCALAR;
3738 lhs.var = vi->id;
3739 lhs.offset = 0;
3740 rhs.type = DEREF;
3741 rhs.var = vi->id;
3742 rhs.offset = UNKNOWN_OFFSET;
3743 process_constraint (new_constraint (lhs, rhs));
3744 }
3745
3746 /* Add constraints to that the solution of VI has all subvariables added. */
3747
3748 static void
make_any_offset_constraints(varinfo_t vi)3749 make_any_offset_constraints (varinfo_t vi)
3750 {
3751 struct constraint_expr lhs, rhs;
3752
3753 /* VAR = VAR + UNKNOWN; */
3754 lhs.type = SCALAR;
3755 lhs.var = vi->id;
3756 lhs.offset = 0;
3757 rhs.type = SCALAR;
3758 rhs.var = vi->id;
3759 rhs.offset = UNKNOWN_OFFSET;
3760 process_constraint (new_constraint (lhs, rhs));
3761 }
3762
3763 /* Temporary storage for fake var decls. */
3764 struct obstack fake_var_decl_obstack;
3765
3766 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3767
3768 static tree
build_fake_var_decl(tree type)3769 build_fake_var_decl (tree type)
3770 {
3771 tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
3772 memset (decl, 0, sizeof (struct tree_var_decl));
3773 TREE_SET_CODE (decl, VAR_DECL);
3774 TREE_TYPE (decl) = type;
3775 DECL_UID (decl) = allocate_decl_uid ();
3776 SET_DECL_PT_UID (decl, -1);
3777 layout_decl (decl, 0);
3778 return decl;
3779 }
3780
3781 /* Create a new artificial heap variable with NAME.
3782 Return the created variable. */
3783
3784 static varinfo_t
make_heapvar(const char * name,bool add_id)3785 make_heapvar (const char *name, bool add_id)
3786 {
3787 varinfo_t vi;
3788 tree heapvar;
3789
3790 heapvar = build_fake_var_decl (ptr_type_node);
3791 DECL_EXTERNAL (heapvar) = 1;
3792
3793 vi = new_var_info (heapvar, name, add_id);
3794 vi->is_artificial_var = true;
3795 vi->is_heap_var = true;
3796 vi->is_unknown_size_var = true;
3797 vi->offset = 0;
3798 vi->fullsize = ~0;
3799 vi->size = ~0;
3800 vi->is_full_var = true;
3801 insert_vi_for_tree (heapvar, vi);
3802
3803 return vi;
3804 }
3805
3806 /* Create a new artificial heap variable with NAME and make a
3807 constraint from it to LHS. Set flags according to a tag used
3808 for tracking restrict pointers. */
3809
3810 static varinfo_t
make_constraint_from_restrict(varinfo_t lhs,const char * name,bool add_id)3811 make_constraint_from_restrict (varinfo_t lhs, const char *name, bool add_id)
3812 {
3813 varinfo_t vi = make_heapvar (name, add_id);
3814 vi->is_restrict_var = 1;
3815 vi->is_global_var = 1;
3816 vi->may_have_pointers = 1;
3817 make_constraint_from (lhs, vi->id);
3818 return vi;
3819 }
3820
3821 /* Create a new artificial heap variable with NAME and make a
3822 constraint from it to LHS. Set flags according to a tag used
3823 for tracking restrict pointers and make the artificial heap
3824 point to global memory. */
3825
3826 static varinfo_t
make_constraint_from_global_restrict(varinfo_t lhs,const char * name,bool add_id)3827 make_constraint_from_global_restrict (varinfo_t lhs, const char *name,
3828 bool add_id)
3829 {
3830 varinfo_t vi = make_constraint_from_restrict (lhs, name, add_id);
3831 make_copy_constraint (vi, nonlocal_id);
3832 return vi;
3833 }
3834
3835 /* In IPA mode there are varinfos for different aspects of reach
3836 function designator. One for the points-to set of the return
3837 value, one for the variables that are clobbered by the function,
3838 one for its uses and one for each parameter (including a single
3839 glob for remaining variadic arguments). */
3840
3841 enum { fi_clobbers = 1, fi_uses = 2,
3842 fi_static_chain = 3, fi_result = 4, fi_parm_base = 5 };
3843
3844 /* Get a constraint for the requested part of a function designator FI
3845 when operating in IPA mode. */
3846
3847 static struct constraint_expr
get_function_part_constraint(varinfo_t fi,unsigned part)3848 get_function_part_constraint (varinfo_t fi, unsigned part)
3849 {
3850 struct constraint_expr c;
3851
3852 gcc_assert (in_ipa_mode);
3853
3854 if (fi->id == anything_id)
3855 {
3856 /* ??? We probably should have a ANYFN special variable. */
3857 c.var = anything_id;
3858 c.offset = 0;
3859 c.type = SCALAR;
3860 }
3861 else if (TREE_CODE (fi->decl) == FUNCTION_DECL)
3862 {
3863 varinfo_t ai = first_vi_for_offset (fi, part);
3864 if (ai)
3865 c.var = ai->id;
3866 else
3867 c.var = anything_id;
3868 c.offset = 0;
3869 c.type = SCALAR;
3870 }
3871 else
3872 {
3873 c.var = fi->id;
3874 c.offset = part;
3875 c.type = DEREF;
3876 }
3877
3878 return c;
3879 }
3880
3881 /* For non-IPA mode, generate constraints necessary for a call on the
3882 RHS. */
3883
3884 static void
handle_rhs_call(gcall * stmt,vec<ce_s> * results)3885 handle_rhs_call (gcall *stmt, vec<ce_s> *results)
3886 {
3887 struct constraint_expr rhsc;
3888 unsigned i;
3889 bool returns_uses = false;
3890
3891 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3892 {
3893 tree arg = gimple_call_arg (stmt, i);
3894 int flags = gimple_call_arg_flags (stmt, i);
3895
3896 /* If the argument is not used we can ignore it. */
3897 if (flags & EAF_UNUSED)
3898 continue;
3899
3900 /* As we compute ESCAPED context-insensitive we do not gain
3901 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3902 set. The argument would still get clobbered through the
3903 escape solution. */
3904 if ((flags & EAF_NOCLOBBER)
3905 && (flags & EAF_NOESCAPE))
3906 {
3907 varinfo_t uses = get_call_use_vi (stmt);
3908 varinfo_t tem = new_var_info (NULL_TREE, "callarg", true);
3909 make_constraint_to (tem->id, arg);
3910 make_any_offset_constraints (tem);
3911 if (!(flags & EAF_DIRECT))
3912 make_transitive_closure_constraints (tem);
3913 make_copy_constraint (uses, tem->id);
3914 returns_uses = true;
3915 }
3916 else if (flags & EAF_NOESCAPE)
3917 {
3918 struct constraint_expr lhs, rhs;
3919 varinfo_t uses = get_call_use_vi (stmt);
3920 varinfo_t clobbers = get_call_clobber_vi (stmt);
3921 varinfo_t tem = new_var_info (NULL_TREE, "callarg", true);
3922 make_constraint_to (tem->id, arg);
3923 make_any_offset_constraints (tem);
3924 if (!(flags & EAF_DIRECT))
3925 make_transitive_closure_constraints (tem);
3926 make_copy_constraint (uses, tem->id);
3927 make_copy_constraint (clobbers, tem->id);
3928 /* Add *tem = nonlocal, do not add *tem = callused as
3929 EAF_NOESCAPE parameters do not escape to other parameters
3930 and all other uses appear in NONLOCAL as well. */
3931 lhs.type = DEREF;
3932 lhs.var = tem->id;
3933 lhs.offset = 0;
3934 rhs.type = SCALAR;
3935 rhs.var = nonlocal_id;
3936 rhs.offset = 0;
3937 process_constraint (new_constraint (lhs, rhs));
3938 returns_uses = true;
3939 }
3940 else
3941 make_escape_constraint (arg);
3942 }
3943
3944 /* If we added to the calls uses solution make sure we account for
3945 pointers to it to be returned. */
3946 if (returns_uses)
3947 {
3948 rhsc.var = get_call_use_vi (stmt)->id;
3949 rhsc.offset = UNKNOWN_OFFSET;
3950 rhsc.type = SCALAR;
3951 results->safe_push (rhsc);
3952 }
3953
3954 /* The static chain escapes as well. */
3955 if (gimple_call_chain (stmt))
3956 make_escape_constraint (gimple_call_chain (stmt));
3957
3958 /* And if we applied NRV the address of the return slot escapes as well. */
3959 if (gimple_call_return_slot_opt_p (stmt)
3960 && gimple_call_lhs (stmt) != NULL_TREE
3961 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
3962 {
3963 auto_vec<ce_s> tmpc;
3964 struct constraint_expr lhsc, *c;
3965 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
3966 lhsc.var = escaped_id;
3967 lhsc.offset = 0;
3968 lhsc.type = SCALAR;
3969 FOR_EACH_VEC_ELT (tmpc, i, c)
3970 process_constraint (new_constraint (lhsc, *c));
3971 }
3972
3973 /* Regular functions return nonlocal memory. */
3974 rhsc.var = nonlocal_id;
3975 rhsc.offset = 0;
3976 rhsc.type = SCALAR;
3977 results->safe_push (rhsc);
3978 }
3979
3980 /* For non-IPA mode, generate constraints necessary for a call
3981 that returns a pointer and assigns it to LHS. This simply makes
3982 the LHS point to global and escaped variables. */
3983
3984 static void
handle_lhs_call(gcall * stmt,tree lhs,int flags,vec<ce_s> rhsc,tree fndecl)3985 handle_lhs_call (gcall *stmt, tree lhs, int flags, vec<ce_s> rhsc,
3986 tree fndecl)
3987 {
3988 auto_vec<ce_s> lhsc;
3989
3990 get_constraint_for (lhs, &lhsc);
3991 /* If the store is to a global decl make sure to
3992 add proper escape constraints. */
3993 lhs = get_base_address (lhs);
3994 if (lhs
3995 && DECL_P (lhs)
3996 && is_global_var (lhs))
3997 {
3998 struct constraint_expr tmpc;
3999 tmpc.var = escaped_id;
4000 tmpc.offset = 0;
4001 tmpc.type = SCALAR;
4002 lhsc.safe_push (tmpc);
4003 }
4004
4005 /* If the call returns an argument unmodified override the rhs
4006 constraints. */
4007 if (flags & ERF_RETURNS_ARG
4008 && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
4009 {
4010 tree arg;
4011 rhsc.create (0);
4012 arg = gimple_call_arg (stmt, flags & ERF_RETURN_ARG_MASK);
4013 get_constraint_for (arg, &rhsc);
4014 process_all_all_constraints (lhsc, rhsc);
4015 rhsc.release ();
4016 }
4017 else if (flags & ERF_NOALIAS)
4018 {
4019 varinfo_t vi;
4020 struct constraint_expr tmpc;
4021 rhsc.create (0);
4022 vi = make_heapvar ("HEAP", true);
4023 /* We are marking allocated storage local, we deal with it becoming
4024 global by escaping and setting of vars_contains_escaped_heap. */
4025 DECL_EXTERNAL (vi->decl) = 0;
4026 vi->is_global_var = 0;
4027 /* If this is not a real malloc call assume the memory was
4028 initialized and thus may point to global memory. All
4029 builtin functions with the malloc attribute behave in a sane way. */
4030 if (!fndecl
4031 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
4032 make_constraint_from (vi, nonlocal_id);
4033 tmpc.var = vi->id;
4034 tmpc.offset = 0;
4035 tmpc.type = ADDRESSOF;
4036 rhsc.safe_push (tmpc);
4037 process_all_all_constraints (lhsc, rhsc);
4038 rhsc.release ();
4039 }
4040 else
4041 process_all_all_constraints (lhsc, rhsc);
4042 }
4043
4044 /* For non-IPA mode, generate constraints necessary for a call of a
4045 const function that returns a pointer in the statement STMT. */
4046
4047 static void
handle_const_call(gcall * stmt,vec<ce_s> * results)4048 handle_const_call (gcall *stmt, vec<ce_s> *results)
4049 {
4050 struct constraint_expr rhsc;
4051 unsigned int k;
4052 bool need_uses = false;
4053
4054 /* Treat nested const functions the same as pure functions as far
4055 as the static chain is concerned. */
4056 if (gimple_call_chain (stmt))
4057 {
4058 varinfo_t uses = get_call_use_vi (stmt);
4059 make_constraint_to (uses->id, gimple_call_chain (stmt));
4060 need_uses = true;
4061 }
4062
4063 /* And if we applied NRV the address of the return slot escapes as well. */
4064 if (gimple_call_return_slot_opt_p (stmt)
4065 && gimple_call_lhs (stmt) != NULL_TREE
4066 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4067 {
4068 varinfo_t uses = get_call_use_vi (stmt);
4069 auto_vec<ce_s> tmpc;
4070 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
4071 make_constraints_to (uses->id, tmpc);
4072 need_uses = true;
4073 }
4074
4075 if (need_uses)
4076 {
4077 varinfo_t uses = get_call_use_vi (stmt);
4078 make_any_offset_constraints (uses);
4079 make_transitive_closure_constraints (uses);
4080 rhsc.var = uses->id;
4081 rhsc.offset = 0;
4082 rhsc.type = SCALAR;
4083 results->safe_push (rhsc);
4084 }
4085
4086 /* May return offsetted arguments. */
4087 varinfo_t tem = NULL;
4088 if (gimple_call_num_args (stmt) != 0)
4089 tem = new_var_info (NULL_TREE, "callarg", true);
4090 for (k = 0; k < gimple_call_num_args (stmt); ++k)
4091 {
4092 tree arg = gimple_call_arg (stmt, k);
4093 auto_vec<ce_s> argc;
4094 get_constraint_for_rhs (arg, &argc);
4095 make_constraints_to (tem->id, argc);
4096 }
4097 if (tem)
4098 {
4099 ce_s ce;
4100 ce.type = SCALAR;
4101 ce.var = tem->id;
4102 ce.offset = UNKNOWN_OFFSET;
4103 results->safe_push (ce);
4104 }
4105
4106 /* May return addresses of globals. */
4107 rhsc.var = nonlocal_id;
4108 rhsc.offset = 0;
4109 rhsc.type = ADDRESSOF;
4110 results->safe_push (rhsc);
4111 }
4112
4113 /* For non-IPA mode, generate constraints necessary for a call to a
4114 pure function in statement STMT. */
4115
4116 static void
handle_pure_call(gcall * stmt,vec<ce_s> * results)4117 handle_pure_call (gcall *stmt, vec<ce_s> *results)
4118 {
4119 struct constraint_expr rhsc;
4120 unsigned i;
4121 varinfo_t uses = NULL;
4122
4123 /* Memory reached from pointer arguments is call-used. */
4124 for (i = 0; i < gimple_call_num_args (stmt); ++i)
4125 {
4126 tree arg = gimple_call_arg (stmt, i);
4127 if (!uses)
4128 {
4129 uses = get_call_use_vi (stmt);
4130 make_any_offset_constraints (uses);
4131 make_transitive_closure_constraints (uses);
4132 }
4133 make_constraint_to (uses->id, arg);
4134 }
4135
4136 /* The static chain is used as well. */
4137 if (gimple_call_chain (stmt))
4138 {
4139 if (!uses)
4140 {
4141 uses = get_call_use_vi (stmt);
4142 make_any_offset_constraints (uses);
4143 make_transitive_closure_constraints (uses);
4144 }
4145 make_constraint_to (uses->id, gimple_call_chain (stmt));
4146 }
4147
4148 /* And if we applied NRV the address of the return slot. */
4149 if (gimple_call_return_slot_opt_p (stmt)
4150 && gimple_call_lhs (stmt) != NULL_TREE
4151 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4152 {
4153 if (!uses)
4154 {
4155 uses = get_call_use_vi (stmt);
4156 make_any_offset_constraints (uses);
4157 make_transitive_closure_constraints (uses);
4158 }
4159 auto_vec<ce_s> tmpc;
4160 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
4161 make_constraints_to (uses->id, tmpc);
4162 }
4163
4164 /* Pure functions may return call-used and nonlocal memory. */
4165 if (uses)
4166 {
4167 rhsc.var = uses->id;
4168 rhsc.offset = 0;
4169 rhsc.type = SCALAR;
4170 results->safe_push (rhsc);
4171 }
4172 rhsc.var = nonlocal_id;
4173 rhsc.offset = 0;
4174 rhsc.type = SCALAR;
4175 results->safe_push (rhsc);
4176 }
4177
4178
4179 /* Return the varinfo for the callee of CALL. */
4180
4181 static varinfo_t
get_fi_for_callee(gcall * call)4182 get_fi_for_callee (gcall *call)
4183 {
4184 tree decl, fn = gimple_call_fn (call);
4185
4186 if (fn && TREE_CODE (fn) == OBJ_TYPE_REF)
4187 fn = OBJ_TYPE_REF_EXPR (fn);
4188
4189 /* If we can directly resolve the function being called, do so.
4190 Otherwise, it must be some sort of indirect expression that
4191 we should still be able to handle. */
4192 decl = gimple_call_addr_fndecl (fn);
4193 if (decl)
4194 return get_vi_for_tree (decl);
4195
4196 /* If the function is anything other than a SSA name pointer we have no
4197 clue and should be getting ANYFN (well, ANYTHING for now). */
4198 if (!fn || TREE_CODE (fn) != SSA_NAME)
4199 return get_varinfo (anything_id);
4200
4201 if (SSA_NAME_IS_DEFAULT_DEF (fn)
4202 && (TREE_CODE (SSA_NAME_VAR (fn)) == PARM_DECL
4203 || TREE_CODE (SSA_NAME_VAR (fn)) == RESULT_DECL))
4204 fn = SSA_NAME_VAR (fn);
4205
4206 return get_vi_for_tree (fn);
4207 }
4208
4209 /* Create constraints for assigning call argument ARG to the incoming parameter
4210 INDEX of function FI. */
4211
4212 static void
find_func_aliases_for_call_arg(varinfo_t fi,unsigned index,tree arg)4213 find_func_aliases_for_call_arg (varinfo_t fi, unsigned index, tree arg)
4214 {
4215 struct constraint_expr lhs;
4216 lhs = get_function_part_constraint (fi, fi_parm_base + index);
4217
4218 auto_vec<ce_s, 2> rhsc;
4219 get_constraint_for_rhs (arg, &rhsc);
4220
4221 unsigned j;
4222 struct constraint_expr *rhsp;
4223 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4224 process_constraint (new_constraint (lhs, *rhsp));
4225 }
4226
4227 /* Return true if FNDECL may be part of another lto partition. */
4228
4229 static bool
fndecl_maybe_in_other_partition(tree fndecl)4230 fndecl_maybe_in_other_partition (tree fndecl)
4231 {
4232 cgraph_node *fn_node = cgraph_node::get (fndecl);
4233 if (fn_node == NULL)
4234 return true;
4235
4236 return fn_node->in_other_partition;
4237 }
4238
4239 /* Create constraints for the builtin call T. Return true if the call
4240 was handled, otherwise false. */
4241
4242 static bool
find_func_aliases_for_builtin_call(struct function * fn,gcall * t)4243 find_func_aliases_for_builtin_call (struct function *fn, gcall *t)
4244 {
4245 tree fndecl = gimple_call_fndecl (t);
4246 auto_vec<ce_s, 2> lhsc;
4247 auto_vec<ce_s, 4> rhsc;
4248 varinfo_t fi;
4249
4250 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
4251 /* ??? All builtins that are handled here need to be handled
4252 in the alias-oracle query functions explicitly! */
4253 switch (DECL_FUNCTION_CODE (fndecl))
4254 {
4255 /* All the following functions return a pointer to the same object
4256 as their first argument points to. The functions do not add
4257 to the ESCAPED solution. The functions make the first argument
4258 pointed to memory point to what the second argument pointed to
4259 memory points to. */
4260 case BUILT_IN_STRCPY:
4261 case BUILT_IN_STRNCPY:
4262 case BUILT_IN_BCOPY:
4263 case BUILT_IN_MEMCPY:
4264 case BUILT_IN_MEMMOVE:
4265 case BUILT_IN_MEMPCPY:
4266 case BUILT_IN_STPCPY:
4267 case BUILT_IN_STPNCPY:
4268 case BUILT_IN_STRCAT:
4269 case BUILT_IN_STRNCAT:
4270 case BUILT_IN_STRCPY_CHK:
4271 case BUILT_IN_STRNCPY_CHK:
4272 case BUILT_IN_MEMCPY_CHK:
4273 case BUILT_IN_MEMMOVE_CHK:
4274 case BUILT_IN_MEMPCPY_CHK:
4275 case BUILT_IN_STPCPY_CHK:
4276 case BUILT_IN_STPNCPY_CHK:
4277 case BUILT_IN_STRCAT_CHK:
4278 case BUILT_IN_STRNCAT_CHK:
4279 case BUILT_IN_TM_MEMCPY:
4280 case BUILT_IN_TM_MEMMOVE:
4281 {
4282 tree res = gimple_call_lhs (t);
4283 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4284 == BUILT_IN_BCOPY ? 1 : 0));
4285 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4286 == BUILT_IN_BCOPY ? 0 : 1));
4287 if (res != NULL_TREE)
4288 {
4289 get_constraint_for (res, &lhsc);
4290 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
4291 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
4292 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY
4293 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY_CHK
4294 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY_CHK
4295 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY_CHK)
4296 get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
4297 else
4298 get_constraint_for (dest, &rhsc);
4299 process_all_all_constraints (lhsc, rhsc);
4300 lhsc.truncate (0);
4301 rhsc.truncate (0);
4302 }
4303 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4304 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4305 do_deref (&lhsc);
4306 do_deref (&rhsc);
4307 process_all_all_constraints (lhsc, rhsc);
4308 return true;
4309 }
4310 case BUILT_IN_MEMSET:
4311 case BUILT_IN_MEMSET_CHK:
4312 case BUILT_IN_TM_MEMSET:
4313 {
4314 tree res = gimple_call_lhs (t);
4315 tree dest = gimple_call_arg (t, 0);
4316 unsigned i;
4317 ce_s *lhsp;
4318 struct constraint_expr ac;
4319 if (res != NULL_TREE)
4320 {
4321 get_constraint_for (res, &lhsc);
4322 get_constraint_for (dest, &rhsc);
4323 process_all_all_constraints (lhsc, rhsc);
4324 lhsc.truncate (0);
4325 }
4326 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4327 do_deref (&lhsc);
4328 if (flag_delete_null_pointer_checks
4329 && integer_zerop (gimple_call_arg (t, 1)))
4330 {
4331 ac.type = ADDRESSOF;
4332 ac.var = nothing_id;
4333 }
4334 else
4335 {
4336 ac.type = SCALAR;
4337 ac.var = integer_id;
4338 }
4339 ac.offset = 0;
4340 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
4341 process_constraint (new_constraint (*lhsp, ac));
4342 return true;
4343 }
4344 case BUILT_IN_POSIX_MEMALIGN:
4345 {
4346 tree ptrptr = gimple_call_arg (t, 0);
4347 get_constraint_for (ptrptr, &lhsc);
4348 do_deref (&lhsc);
4349 varinfo_t vi = make_heapvar ("HEAP", true);
4350 /* We are marking allocated storage local, we deal with it becoming
4351 global by escaping and setting of vars_contains_escaped_heap. */
4352 DECL_EXTERNAL (vi->decl) = 0;
4353 vi->is_global_var = 0;
4354 struct constraint_expr tmpc;
4355 tmpc.var = vi->id;
4356 tmpc.offset = 0;
4357 tmpc.type = ADDRESSOF;
4358 rhsc.safe_push (tmpc);
4359 process_all_all_constraints (lhsc, rhsc);
4360 return true;
4361 }
4362 case BUILT_IN_ASSUME_ALIGNED:
4363 {
4364 tree res = gimple_call_lhs (t);
4365 tree dest = gimple_call_arg (t, 0);
4366 if (res != NULL_TREE)
4367 {
4368 get_constraint_for (res, &lhsc);
4369 get_constraint_for (dest, &rhsc);
4370 process_all_all_constraints (lhsc, rhsc);
4371 }
4372 return true;
4373 }
4374 /* All the following functions do not return pointers, do not
4375 modify the points-to sets of memory reachable from their
4376 arguments and do not add to the ESCAPED solution. */
4377 case BUILT_IN_SINCOS:
4378 case BUILT_IN_SINCOSF:
4379 case BUILT_IN_SINCOSL:
4380 case BUILT_IN_FREXP:
4381 case BUILT_IN_FREXPF:
4382 case BUILT_IN_FREXPL:
4383 case BUILT_IN_GAMMA_R:
4384 case BUILT_IN_GAMMAF_R:
4385 case BUILT_IN_GAMMAL_R:
4386 case BUILT_IN_LGAMMA_R:
4387 case BUILT_IN_LGAMMAF_R:
4388 case BUILT_IN_LGAMMAL_R:
4389 case BUILT_IN_MODF:
4390 case BUILT_IN_MODFF:
4391 case BUILT_IN_MODFL:
4392 case BUILT_IN_REMQUO:
4393 case BUILT_IN_REMQUOF:
4394 case BUILT_IN_REMQUOL:
4395 case BUILT_IN_FREE:
4396 return true;
4397 case BUILT_IN_STRDUP:
4398 case BUILT_IN_STRNDUP:
4399 case BUILT_IN_REALLOC:
4400 if (gimple_call_lhs (t))
4401 {
4402 handle_lhs_call (t, gimple_call_lhs (t),
4403 gimple_call_return_flags (t) | ERF_NOALIAS,
4404 vNULL, fndecl);
4405 get_constraint_for_ptr_offset (gimple_call_lhs (t),
4406 NULL_TREE, &lhsc);
4407 get_constraint_for_ptr_offset (gimple_call_arg (t, 0),
4408 NULL_TREE, &rhsc);
4409 do_deref (&lhsc);
4410 do_deref (&rhsc);
4411 process_all_all_constraints (lhsc, rhsc);
4412 lhsc.truncate (0);
4413 rhsc.truncate (0);
4414 /* For realloc the resulting pointer can be equal to the
4415 argument as well. But only doing this wouldn't be
4416 correct because with ptr == 0 realloc behaves like malloc. */
4417 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_REALLOC)
4418 {
4419 get_constraint_for (gimple_call_lhs (t), &lhsc);
4420 get_constraint_for (gimple_call_arg (t, 0), &rhsc);
4421 process_all_all_constraints (lhsc, rhsc);
4422 }
4423 return true;
4424 }
4425 break;
4426 /* String / character search functions return a pointer into the
4427 source string or NULL. */
4428 case BUILT_IN_INDEX:
4429 case BUILT_IN_STRCHR:
4430 case BUILT_IN_STRRCHR:
4431 case BUILT_IN_MEMCHR:
4432 case BUILT_IN_STRSTR:
4433 case BUILT_IN_STRPBRK:
4434 if (gimple_call_lhs (t))
4435 {
4436 tree src = gimple_call_arg (t, 0);
4437 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4438 constraint_expr nul;
4439 nul.var = nothing_id;
4440 nul.offset = 0;
4441 nul.type = ADDRESSOF;
4442 rhsc.safe_push (nul);
4443 get_constraint_for (gimple_call_lhs (t), &lhsc);
4444 process_all_all_constraints (lhsc, rhsc);
4445 }
4446 return true;
4447 /* Trampolines are special - they set up passing the static
4448 frame. */
4449 case BUILT_IN_INIT_TRAMPOLINE:
4450 {
4451 tree tramp = gimple_call_arg (t, 0);
4452 tree nfunc = gimple_call_arg (t, 1);
4453 tree frame = gimple_call_arg (t, 2);
4454 unsigned i;
4455 struct constraint_expr lhs, *rhsp;
4456 if (in_ipa_mode)
4457 {
4458 varinfo_t nfi = NULL;
4459 gcc_assert (TREE_CODE (nfunc) == ADDR_EXPR);
4460 nfi = lookup_vi_for_tree (TREE_OPERAND (nfunc, 0));
4461 if (nfi)
4462 {
4463 lhs = get_function_part_constraint (nfi, fi_static_chain);
4464 get_constraint_for (frame, &rhsc);
4465 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4466 process_constraint (new_constraint (lhs, *rhsp));
4467 rhsc.truncate (0);
4468
4469 /* Make the frame point to the function for
4470 the trampoline adjustment call. */
4471 get_constraint_for (tramp, &lhsc);
4472 do_deref (&lhsc);
4473 get_constraint_for (nfunc, &rhsc);
4474 process_all_all_constraints (lhsc, rhsc);
4475
4476 return true;
4477 }
4478 }
4479 /* Else fallthru to generic handling which will let
4480 the frame escape. */
4481 break;
4482 }
4483 case BUILT_IN_ADJUST_TRAMPOLINE:
4484 {
4485 tree tramp = gimple_call_arg (t, 0);
4486 tree res = gimple_call_lhs (t);
4487 if (in_ipa_mode && res)
4488 {
4489 get_constraint_for (res, &lhsc);
4490 get_constraint_for (tramp, &rhsc);
4491 do_deref (&rhsc);
4492 process_all_all_constraints (lhsc, rhsc);
4493 }
4494 return true;
4495 }
4496 CASE_BUILT_IN_TM_STORE (1):
4497 CASE_BUILT_IN_TM_STORE (2):
4498 CASE_BUILT_IN_TM_STORE (4):
4499 CASE_BUILT_IN_TM_STORE (8):
4500 CASE_BUILT_IN_TM_STORE (FLOAT):
4501 CASE_BUILT_IN_TM_STORE (DOUBLE):
4502 CASE_BUILT_IN_TM_STORE (LDOUBLE):
4503 CASE_BUILT_IN_TM_STORE (M64):
4504 CASE_BUILT_IN_TM_STORE (M128):
4505 CASE_BUILT_IN_TM_STORE (M256):
4506 {
4507 tree addr = gimple_call_arg (t, 0);
4508 tree src = gimple_call_arg (t, 1);
4509
4510 get_constraint_for (addr, &lhsc);
4511 do_deref (&lhsc);
4512 get_constraint_for (src, &rhsc);
4513 process_all_all_constraints (lhsc, rhsc);
4514 return true;
4515 }
4516 CASE_BUILT_IN_TM_LOAD (1):
4517 CASE_BUILT_IN_TM_LOAD (2):
4518 CASE_BUILT_IN_TM_LOAD (4):
4519 CASE_BUILT_IN_TM_LOAD (8):
4520 CASE_BUILT_IN_TM_LOAD (FLOAT):
4521 CASE_BUILT_IN_TM_LOAD (DOUBLE):
4522 CASE_BUILT_IN_TM_LOAD (LDOUBLE):
4523 CASE_BUILT_IN_TM_LOAD (M64):
4524 CASE_BUILT_IN_TM_LOAD (M128):
4525 CASE_BUILT_IN_TM_LOAD (M256):
4526 {
4527 tree dest = gimple_call_lhs (t);
4528 tree addr = gimple_call_arg (t, 0);
4529
4530 get_constraint_for (dest, &lhsc);
4531 get_constraint_for (addr, &rhsc);
4532 do_deref (&rhsc);
4533 process_all_all_constraints (lhsc, rhsc);
4534 return true;
4535 }
4536 /* Variadic argument handling needs to be handled in IPA
4537 mode as well. */
4538 case BUILT_IN_VA_START:
4539 {
4540 tree valist = gimple_call_arg (t, 0);
4541 struct constraint_expr rhs, *lhsp;
4542 unsigned i;
4543 get_constraint_for (valist, &lhsc);
4544 do_deref (&lhsc);
4545 /* The va_list gets access to pointers in variadic
4546 arguments. Which we know in the case of IPA analysis
4547 and otherwise are just all nonlocal variables. */
4548 if (in_ipa_mode)
4549 {
4550 fi = lookup_vi_for_tree (fn->decl);
4551 rhs = get_function_part_constraint (fi, ~0);
4552 rhs.type = ADDRESSOF;
4553 }
4554 else
4555 {
4556 rhs.var = nonlocal_id;
4557 rhs.type = ADDRESSOF;
4558 rhs.offset = 0;
4559 }
4560 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
4561 process_constraint (new_constraint (*lhsp, rhs));
4562 /* va_list is clobbered. */
4563 make_constraint_to (get_call_clobber_vi (t)->id, valist);
4564 return true;
4565 }
4566 /* va_end doesn't have any effect that matters. */
4567 case BUILT_IN_VA_END:
4568 return true;
4569 /* Alternate return. Simply give up for now. */
4570 case BUILT_IN_RETURN:
4571 {
4572 fi = NULL;
4573 if (!in_ipa_mode
4574 || !(fi = get_vi_for_tree (fn->decl)))
4575 make_constraint_from (get_varinfo (escaped_id), anything_id);
4576 else if (in_ipa_mode
4577 && fi != NULL)
4578 {
4579 struct constraint_expr lhs, rhs;
4580 lhs = get_function_part_constraint (fi, fi_result);
4581 rhs.var = anything_id;
4582 rhs.offset = 0;
4583 rhs.type = SCALAR;
4584 process_constraint (new_constraint (lhs, rhs));
4585 }
4586 return true;
4587 }
4588 case BUILT_IN_GOMP_PARALLEL:
4589 case BUILT_IN_GOACC_PARALLEL:
4590 {
4591 if (in_ipa_mode)
4592 {
4593 unsigned int fnpos, argpos;
4594 switch (DECL_FUNCTION_CODE (fndecl))
4595 {
4596 case BUILT_IN_GOMP_PARALLEL:
4597 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
4598 fnpos = 0;
4599 argpos = 1;
4600 break;
4601 case BUILT_IN_GOACC_PARALLEL:
4602 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
4603 sizes, kinds, ...). */
4604 fnpos = 1;
4605 argpos = 3;
4606 break;
4607 default:
4608 gcc_unreachable ();
4609 }
4610
4611 tree fnarg = gimple_call_arg (t, fnpos);
4612 gcc_assert (TREE_CODE (fnarg) == ADDR_EXPR);
4613 tree fndecl = TREE_OPERAND (fnarg, 0);
4614 if (fndecl_maybe_in_other_partition (fndecl))
4615 /* Fallthru to general call handling. */
4616 break;
4617
4618 tree arg = gimple_call_arg (t, argpos);
4619
4620 varinfo_t fi = get_vi_for_tree (fndecl);
4621 find_func_aliases_for_call_arg (fi, 0, arg);
4622 return true;
4623 }
4624 /* Else fallthru to generic call handling. */
4625 break;
4626 }
4627 /* printf-style functions may have hooks to set pointers to
4628 point to somewhere into the generated string. Leave them
4629 for a later exercise... */
4630 default:
4631 /* Fallthru to general call handling. */;
4632 }
4633
4634 return false;
4635 }
4636
4637 /* Create constraints for the call T. */
4638
4639 static void
find_func_aliases_for_call(struct function * fn,gcall * t)4640 find_func_aliases_for_call (struct function *fn, gcall *t)
4641 {
4642 tree fndecl = gimple_call_fndecl (t);
4643 varinfo_t fi;
4644
4645 if (fndecl != NULL_TREE
4646 && DECL_BUILT_IN (fndecl)
4647 && find_func_aliases_for_builtin_call (fn, t))
4648 return;
4649
4650 fi = get_fi_for_callee (t);
4651 if (!in_ipa_mode
4652 || (fndecl && !fi->is_fn_info))
4653 {
4654 auto_vec<ce_s, 16> rhsc;
4655 int flags = gimple_call_flags (t);
4656
4657 /* Const functions can return their arguments and addresses
4658 of global memory but not of escaped memory. */
4659 if (flags & (ECF_CONST|ECF_NOVOPS))
4660 {
4661 if (gimple_call_lhs (t))
4662 handle_const_call (t, &rhsc);
4663 }
4664 /* Pure functions can return addresses in and of memory
4665 reachable from their arguments, but they are not an escape
4666 point for reachable memory of their arguments. */
4667 else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE))
4668 handle_pure_call (t, &rhsc);
4669 else
4670 handle_rhs_call (t, &rhsc);
4671 if (gimple_call_lhs (t))
4672 handle_lhs_call (t, gimple_call_lhs (t),
4673 gimple_call_return_flags (t), rhsc, fndecl);
4674 }
4675 else
4676 {
4677 auto_vec<ce_s, 2> rhsc;
4678 tree lhsop;
4679 unsigned j;
4680
4681 /* Assign all the passed arguments to the appropriate incoming
4682 parameters of the function. */
4683 for (j = 0; j < gimple_call_num_args (t); j++)
4684 {
4685 tree arg = gimple_call_arg (t, j);
4686 find_func_aliases_for_call_arg (fi, j, arg);
4687 }
4688
4689 /* If we are returning a value, assign it to the result. */
4690 lhsop = gimple_call_lhs (t);
4691 if (lhsop)
4692 {
4693 auto_vec<ce_s, 2> lhsc;
4694 struct constraint_expr rhs;
4695 struct constraint_expr *lhsp;
4696 bool aggr_p = aggregate_value_p (lhsop, gimple_call_fntype (t));
4697
4698 get_constraint_for (lhsop, &lhsc);
4699 rhs = get_function_part_constraint (fi, fi_result);
4700 if (aggr_p)
4701 {
4702 auto_vec<ce_s, 2> tem;
4703 tem.quick_push (rhs);
4704 do_deref (&tem);
4705 gcc_checking_assert (tem.length () == 1);
4706 rhs = tem[0];
4707 }
4708 FOR_EACH_VEC_ELT (lhsc, j, lhsp)
4709 process_constraint (new_constraint (*lhsp, rhs));
4710
4711 /* If we pass the result decl by reference, honor that. */
4712 if (aggr_p)
4713 {
4714 struct constraint_expr lhs;
4715 struct constraint_expr *rhsp;
4716
4717 get_constraint_for_address_of (lhsop, &rhsc);
4718 lhs = get_function_part_constraint (fi, fi_result);
4719 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4720 process_constraint (new_constraint (lhs, *rhsp));
4721 rhsc.truncate (0);
4722 }
4723 }
4724
4725 /* If we use a static chain, pass it along. */
4726 if (gimple_call_chain (t))
4727 {
4728 struct constraint_expr lhs;
4729 struct constraint_expr *rhsp;
4730
4731 get_constraint_for (gimple_call_chain (t), &rhsc);
4732 lhs = get_function_part_constraint (fi, fi_static_chain);
4733 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4734 process_constraint (new_constraint (lhs, *rhsp));
4735 }
4736 }
4737 }
4738
4739 /* Walk statement T setting up aliasing constraints according to the
4740 references found in T. This function is the main part of the
4741 constraint builder. AI points to auxiliary alias information used
4742 when building alias sets and computing alias grouping heuristics. */
4743
4744 static void
find_func_aliases(struct function * fn,gimple * origt)4745 find_func_aliases (struct function *fn, gimple *origt)
4746 {
4747 gimple *t = origt;
4748 auto_vec<ce_s, 16> lhsc;
4749 auto_vec<ce_s, 16> rhsc;
4750 struct constraint_expr *c;
4751 varinfo_t fi;
4752
4753 /* Now build constraints expressions. */
4754 if (gimple_code (t) == GIMPLE_PHI)
4755 {
4756 size_t i;
4757 unsigned int j;
4758
4759 /* For a phi node, assign all the arguments to
4760 the result. */
4761 get_constraint_for (gimple_phi_result (t), &lhsc);
4762 for (i = 0; i < gimple_phi_num_args (t); i++)
4763 {
4764 tree strippedrhs = PHI_ARG_DEF (t, i);
4765
4766 STRIP_NOPS (strippedrhs);
4767 get_constraint_for_rhs (gimple_phi_arg_def (t, i), &rhsc);
4768
4769 FOR_EACH_VEC_ELT (lhsc, j, c)
4770 {
4771 struct constraint_expr *c2;
4772 while (rhsc.length () > 0)
4773 {
4774 c2 = &rhsc.last ();
4775 process_constraint (new_constraint (*c, *c2));
4776 rhsc.pop ();
4777 }
4778 }
4779 }
4780 }
4781 /* In IPA mode, we need to generate constraints to pass call
4782 arguments through their calls. There are two cases,
4783 either a GIMPLE_CALL returning a value, or just a plain
4784 GIMPLE_CALL when we are not.
4785
4786 In non-ipa mode, we need to generate constraints for each
4787 pointer passed by address. */
4788 else if (is_gimple_call (t))
4789 find_func_aliases_for_call (fn, as_a <gcall *> (t));
4790
4791 /* Otherwise, just a regular assignment statement. Only care about
4792 operations with pointer result, others are dealt with as escape
4793 points if they have pointer operands. */
4794 else if (is_gimple_assign (t))
4795 {
4796 /* Otherwise, just a regular assignment statement. */
4797 tree lhsop = gimple_assign_lhs (t);
4798 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
4799
4800 if (rhsop && TREE_CLOBBER_P (rhsop))
4801 /* Ignore clobbers, they don't actually store anything into
4802 the LHS. */
4803 ;
4804 else if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
4805 do_structure_copy (lhsop, rhsop);
4806 else
4807 {
4808 enum tree_code code = gimple_assign_rhs_code (t);
4809
4810 get_constraint_for (lhsop, &lhsc);
4811
4812 if (code == POINTER_PLUS_EXPR)
4813 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4814 gimple_assign_rhs2 (t), &rhsc);
4815 else if (code == BIT_AND_EXPR
4816 && TREE_CODE (gimple_assign_rhs2 (t)) == INTEGER_CST)
4817 {
4818 /* Aligning a pointer via a BIT_AND_EXPR is offsetting
4819 the pointer. Handle it by offsetting it by UNKNOWN. */
4820 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4821 NULL_TREE, &rhsc);
4822 }
4823 else if ((CONVERT_EXPR_CODE_P (code)
4824 && !(POINTER_TYPE_P (gimple_expr_type (t))
4825 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
4826 || gimple_assign_single_p (t))
4827 get_constraint_for_rhs (rhsop, &rhsc);
4828 else if (code == COND_EXPR)
4829 {
4830 /* The result is a merge of both COND_EXPR arms. */
4831 auto_vec<ce_s, 2> tmp;
4832 struct constraint_expr *rhsp;
4833 unsigned i;
4834 get_constraint_for_rhs (gimple_assign_rhs2 (t), &rhsc);
4835 get_constraint_for_rhs (gimple_assign_rhs3 (t), &tmp);
4836 FOR_EACH_VEC_ELT (tmp, i, rhsp)
4837 rhsc.safe_push (*rhsp);
4838 }
4839 else if (truth_value_p (code))
4840 /* Truth value results are not pointer (parts). Or at least
4841 very unreasonable obfuscation of a part. */
4842 ;
4843 else
4844 {
4845 /* All other operations are merges. */
4846 auto_vec<ce_s, 4> tmp;
4847 struct constraint_expr *rhsp;
4848 unsigned i, j;
4849 get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
4850 for (i = 2; i < gimple_num_ops (t); ++i)
4851 {
4852 get_constraint_for_rhs (gimple_op (t, i), &tmp);
4853 FOR_EACH_VEC_ELT (tmp, j, rhsp)
4854 rhsc.safe_push (*rhsp);
4855 tmp.truncate (0);
4856 }
4857 }
4858 process_all_all_constraints (lhsc, rhsc);
4859 }
4860 /* If there is a store to a global variable the rhs escapes. */
4861 if ((lhsop = get_base_address (lhsop)) != NULL_TREE
4862 && DECL_P (lhsop))
4863 {
4864 varinfo_t vi = get_vi_for_tree (lhsop);
4865 if ((! in_ipa_mode && vi->is_global_var)
4866 || vi->is_ipa_escape_point)
4867 make_escape_constraint (rhsop);
4868 }
4869 }
4870 /* Handle escapes through return. */
4871 else if (gimple_code (t) == GIMPLE_RETURN
4872 && gimple_return_retval (as_a <greturn *> (t)) != NULL_TREE)
4873 {
4874 greturn *return_stmt = as_a <greturn *> (t);
4875 fi = NULL;
4876 if (!in_ipa_mode
4877 || !(fi = get_vi_for_tree (fn->decl)))
4878 make_escape_constraint (gimple_return_retval (return_stmt));
4879 else if (in_ipa_mode)
4880 {
4881 struct constraint_expr lhs ;
4882 struct constraint_expr *rhsp;
4883 unsigned i;
4884
4885 lhs = get_function_part_constraint (fi, fi_result);
4886 get_constraint_for_rhs (gimple_return_retval (return_stmt), &rhsc);
4887 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4888 process_constraint (new_constraint (lhs, *rhsp));
4889 }
4890 }
4891 /* Handle asms conservatively by adding escape constraints to everything. */
4892 else if (gasm *asm_stmt = dyn_cast <gasm *> (t))
4893 {
4894 unsigned i, noutputs;
4895 const char **oconstraints;
4896 const char *constraint;
4897 bool allows_mem, allows_reg, is_inout;
4898
4899 noutputs = gimple_asm_noutputs (asm_stmt);
4900 oconstraints = XALLOCAVEC (const char *, noutputs);
4901
4902 for (i = 0; i < noutputs; ++i)
4903 {
4904 tree link = gimple_asm_output_op (asm_stmt, i);
4905 tree op = TREE_VALUE (link);
4906
4907 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4908 oconstraints[i] = constraint;
4909 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
4910 &allows_reg, &is_inout);
4911
4912 /* A memory constraint makes the address of the operand escape. */
4913 if (!allows_reg && allows_mem)
4914 make_escape_constraint (build_fold_addr_expr (op));
4915
4916 /* The asm may read global memory, so outputs may point to
4917 any global memory. */
4918 if (op)
4919 {
4920 auto_vec<ce_s, 2> lhsc;
4921 struct constraint_expr rhsc, *lhsp;
4922 unsigned j;
4923 get_constraint_for (op, &lhsc);
4924 rhsc.var = nonlocal_id;
4925 rhsc.offset = 0;
4926 rhsc.type = SCALAR;
4927 FOR_EACH_VEC_ELT (lhsc, j, lhsp)
4928 process_constraint (new_constraint (*lhsp, rhsc));
4929 }
4930 }
4931 for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
4932 {
4933 tree link = gimple_asm_input_op (asm_stmt, i);
4934 tree op = TREE_VALUE (link);
4935
4936 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4937
4938 parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
4939 &allows_mem, &allows_reg);
4940
4941 /* A memory constraint makes the address of the operand escape. */
4942 if (!allows_reg && allows_mem)
4943 make_escape_constraint (build_fold_addr_expr (op));
4944 /* Strictly we'd only need the constraint to ESCAPED if
4945 the asm clobbers memory, otherwise using something
4946 along the lines of per-call clobbers/uses would be enough. */
4947 else if (op)
4948 make_escape_constraint (op);
4949 }
4950 }
4951 }
4952
4953
4954 /* Create a constraint adding to the clobber set of FI the memory
4955 pointed to by PTR. */
4956
4957 static void
process_ipa_clobber(varinfo_t fi,tree ptr)4958 process_ipa_clobber (varinfo_t fi, tree ptr)
4959 {
4960 vec<ce_s> ptrc = vNULL;
4961 struct constraint_expr *c, lhs;
4962 unsigned i;
4963 get_constraint_for_rhs (ptr, &ptrc);
4964 lhs = get_function_part_constraint (fi, fi_clobbers);
4965 FOR_EACH_VEC_ELT (ptrc, i, c)
4966 process_constraint (new_constraint (lhs, *c));
4967 ptrc.release ();
4968 }
4969
4970 /* Walk statement T setting up clobber and use constraints according to the
4971 references found in T. This function is a main part of the
4972 IPA constraint builder. */
4973
4974 static void
find_func_clobbers(struct function * fn,gimple * origt)4975 find_func_clobbers (struct function *fn, gimple *origt)
4976 {
4977 gimple *t = origt;
4978 auto_vec<ce_s, 16> lhsc;
4979 auto_vec<ce_s, 16> rhsc;
4980 varinfo_t fi;
4981
4982 /* Add constraints for clobbered/used in IPA mode.
4983 We are not interested in what automatic variables are clobbered
4984 or used as we only use the information in the caller to which
4985 they do not escape. */
4986 gcc_assert (in_ipa_mode);
4987
4988 /* If the stmt refers to memory in any way it better had a VUSE. */
4989 if (gimple_vuse (t) == NULL_TREE)
4990 return;
4991
4992 /* We'd better have function information for the current function. */
4993 fi = lookup_vi_for_tree (fn->decl);
4994 gcc_assert (fi != NULL);
4995
4996 /* Account for stores in assignments and calls. */
4997 if (gimple_vdef (t) != NULL_TREE
4998 && gimple_has_lhs (t))
4999 {
5000 tree lhs = gimple_get_lhs (t);
5001 tree tem = lhs;
5002 while (handled_component_p (tem))
5003 tem = TREE_OPERAND (tem, 0);
5004 if ((DECL_P (tem)
5005 && !auto_var_in_fn_p (tem, fn->decl))
5006 || INDIRECT_REF_P (tem)
5007 || (TREE_CODE (tem) == MEM_REF
5008 && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
5009 && auto_var_in_fn_p
5010 (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl))))
5011 {
5012 struct constraint_expr lhsc, *rhsp;
5013 unsigned i;
5014 lhsc = get_function_part_constraint (fi, fi_clobbers);
5015 get_constraint_for_address_of (lhs, &rhsc);
5016 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5017 process_constraint (new_constraint (lhsc, *rhsp));
5018 rhsc.truncate (0);
5019 }
5020 }
5021
5022 /* Account for uses in assigments and returns. */
5023 if (gimple_assign_single_p (t)
5024 || (gimple_code (t) == GIMPLE_RETURN
5025 && gimple_return_retval (as_a <greturn *> (t)) != NULL_TREE))
5026 {
5027 tree rhs = (gimple_assign_single_p (t)
5028 ? gimple_assign_rhs1 (t)
5029 : gimple_return_retval (as_a <greturn *> (t)));
5030 tree tem = rhs;
5031 while (handled_component_p (tem))
5032 tem = TREE_OPERAND (tem, 0);
5033 if ((DECL_P (tem)
5034 && !auto_var_in_fn_p (tem, fn->decl))
5035 || INDIRECT_REF_P (tem)
5036 || (TREE_CODE (tem) == MEM_REF
5037 && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
5038 && auto_var_in_fn_p
5039 (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl))))
5040 {
5041 struct constraint_expr lhs, *rhsp;
5042 unsigned i;
5043 lhs = get_function_part_constraint (fi, fi_uses);
5044 get_constraint_for_address_of (rhs, &rhsc);
5045 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5046 process_constraint (new_constraint (lhs, *rhsp));
5047 rhsc.truncate (0);
5048 }
5049 }
5050
5051 if (gcall *call_stmt = dyn_cast <gcall *> (t))
5052 {
5053 varinfo_t cfi = NULL;
5054 tree decl = gimple_call_fndecl (t);
5055 struct constraint_expr lhs, rhs;
5056 unsigned i, j;
5057
5058 /* For builtins we do not have separate function info. For those
5059 we do not generate escapes for we have to generate clobbers/uses. */
5060 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
5061 switch (DECL_FUNCTION_CODE (decl))
5062 {
5063 /* The following functions use and clobber memory pointed to
5064 by their arguments. */
5065 case BUILT_IN_STRCPY:
5066 case BUILT_IN_STRNCPY:
5067 case BUILT_IN_BCOPY:
5068 case BUILT_IN_MEMCPY:
5069 case BUILT_IN_MEMMOVE:
5070 case BUILT_IN_MEMPCPY:
5071 case BUILT_IN_STPCPY:
5072 case BUILT_IN_STPNCPY:
5073 case BUILT_IN_STRCAT:
5074 case BUILT_IN_STRNCAT:
5075 case BUILT_IN_STRCPY_CHK:
5076 case BUILT_IN_STRNCPY_CHK:
5077 case BUILT_IN_MEMCPY_CHK:
5078 case BUILT_IN_MEMMOVE_CHK:
5079 case BUILT_IN_MEMPCPY_CHK:
5080 case BUILT_IN_STPCPY_CHK:
5081 case BUILT_IN_STPNCPY_CHK:
5082 case BUILT_IN_STRCAT_CHK:
5083 case BUILT_IN_STRNCAT_CHK:
5084 {
5085 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
5086 == BUILT_IN_BCOPY ? 1 : 0));
5087 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
5088 == BUILT_IN_BCOPY ? 0 : 1));
5089 unsigned i;
5090 struct constraint_expr *rhsp, *lhsp;
5091 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
5092 lhs = get_function_part_constraint (fi, fi_clobbers);
5093 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
5094 process_constraint (new_constraint (lhs, *lhsp));
5095 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
5096 lhs = get_function_part_constraint (fi, fi_uses);
5097 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5098 process_constraint (new_constraint (lhs, *rhsp));
5099 return;
5100 }
5101 /* The following function clobbers memory pointed to by
5102 its argument. */
5103 case BUILT_IN_MEMSET:
5104 case BUILT_IN_MEMSET_CHK:
5105 case BUILT_IN_POSIX_MEMALIGN:
5106 {
5107 tree dest = gimple_call_arg (t, 0);
5108 unsigned i;
5109 ce_s *lhsp;
5110 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
5111 lhs = get_function_part_constraint (fi, fi_clobbers);
5112 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
5113 process_constraint (new_constraint (lhs, *lhsp));
5114 return;
5115 }
5116 /* The following functions clobber their second and third
5117 arguments. */
5118 case BUILT_IN_SINCOS:
5119 case BUILT_IN_SINCOSF:
5120 case BUILT_IN_SINCOSL:
5121 {
5122 process_ipa_clobber (fi, gimple_call_arg (t, 1));
5123 process_ipa_clobber (fi, gimple_call_arg (t, 2));
5124 return;
5125 }
5126 /* The following functions clobber their second argument. */
5127 case BUILT_IN_FREXP:
5128 case BUILT_IN_FREXPF:
5129 case BUILT_IN_FREXPL:
5130 case BUILT_IN_LGAMMA_R:
5131 case BUILT_IN_LGAMMAF_R:
5132 case BUILT_IN_LGAMMAL_R:
5133 case BUILT_IN_GAMMA_R:
5134 case BUILT_IN_GAMMAF_R:
5135 case BUILT_IN_GAMMAL_R:
5136 case BUILT_IN_MODF:
5137 case BUILT_IN_MODFF:
5138 case BUILT_IN_MODFL:
5139 {
5140 process_ipa_clobber (fi, gimple_call_arg (t, 1));
5141 return;
5142 }
5143 /* The following functions clobber their third argument. */
5144 case BUILT_IN_REMQUO:
5145 case BUILT_IN_REMQUOF:
5146 case BUILT_IN_REMQUOL:
5147 {
5148 process_ipa_clobber (fi, gimple_call_arg (t, 2));
5149 return;
5150 }
5151 /* The following functions neither read nor clobber memory. */
5152 case BUILT_IN_ASSUME_ALIGNED:
5153 case BUILT_IN_FREE:
5154 return;
5155 /* Trampolines are of no interest to us. */
5156 case BUILT_IN_INIT_TRAMPOLINE:
5157 case BUILT_IN_ADJUST_TRAMPOLINE:
5158 return;
5159 case BUILT_IN_VA_START:
5160 case BUILT_IN_VA_END:
5161 return;
5162 case BUILT_IN_GOMP_PARALLEL:
5163 case BUILT_IN_GOACC_PARALLEL:
5164 {
5165 unsigned int fnpos, argpos;
5166 unsigned int implicit_use_args[2];
5167 unsigned int num_implicit_use_args = 0;
5168 switch (DECL_FUNCTION_CODE (decl))
5169 {
5170 case BUILT_IN_GOMP_PARALLEL:
5171 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
5172 fnpos = 0;
5173 argpos = 1;
5174 break;
5175 case BUILT_IN_GOACC_PARALLEL:
5176 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
5177 sizes, kinds, ...). */
5178 fnpos = 1;
5179 argpos = 3;
5180 implicit_use_args[num_implicit_use_args++] = 4;
5181 implicit_use_args[num_implicit_use_args++] = 5;
5182 break;
5183 default:
5184 gcc_unreachable ();
5185 }
5186
5187 tree fnarg = gimple_call_arg (t, fnpos);
5188 gcc_assert (TREE_CODE (fnarg) == ADDR_EXPR);
5189 tree fndecl = TREE_OPERAND (fnarg, 0);
5190 if (fndecl_maybe_in_other_partition (fndecl))
5191 /* Fallthru to general call handling. */
5192 break;
5193
5194 varinfo_t cfi = get_vi_for_tree (fndecl);
5195
5196 tree arg = gimple_call_arg (t, argpos);
5197
5198 /* Parameter passed by value is used. */
5199 lhs = get_function_part_constraint (fi, fi_uses);
5200 struct constraint_expr *rhsp;
5201 get_constraint_for (arg, &rhsc);
5202 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
5203 process_constraint (new_constraint (lhs, *rhsp));
5204 rhsc.truncate (0);
5205
5206 /* Handle parameters used by the call, but not used in cfi, as
5207 implicitly used by cfi. */
5208 lhs = get_function_part_constraint (cfi, fi_uses);
5209 for (unsigned i = 0; i < num_implicit_use_args; ++i)
5210 {
5211 tree arg = gimple_call_arg (t, implicit_use_args[i]);
5212 get_constraint_for (arg, &rhsc);
5213 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
5214 process_constraint (new_constraint (lhs, *rhsp));
5215 rhsc.truncate (0);
5216 }
5217
5218 /* The caller clobbers what the callee does. */
5219 lhs = get_function_part_constraint (fi, fi_clobbers);
5220 rhs = get_function_part_constraint (cfi, fi_clobbers);
5221 process_constraint (new_constraint (lhs, rhs));
5222
5223 /* The caller uses what the callee does. */
5224 lhs = get_function_part_constraint (fi, fi_uses);
5225 rhs = get_function_part_constraint (cfi, fi_uses);
5226 process_constraint (new_constraint (lhs, rhs));
5227
5228 return;
5229 }
5230 /* printf-style functions may have hooks to set pointers to
5231 point to somewhere into the generated string. Leave them
5232 for a later exercise... */
5233 default:
5234 /* Fallthru to general call handling. */;
5235 }
5236
5237 /* Parameters passed by value are used. */
5238 lhs = get_function_part_constraint (fi, fi_uses);
5239 for (i = 0; i < gimple_call_num_args (t); i++)
5240 {
5241 struct constraint_expr *rhsp;
5242 tree arg = gimple_call_arg (t, i);
5243
5244 if (TREE_CODE (arg) == SSA_NAME
5245 || is_gimple_min_invariant (arg))
5246 continue;
5247
5248 get_constraint_for_address_of (arg, &rhsc);
5249 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
5250 process_constraint (new_constraint (lhs, *rhsp));
5251 rhsc.truncate (0);
5252 }
5253
5254 /* Build constraints for propagating clobbers/uses along the
5255 callgraph edges. */
5256 cfi = get_fi_for_callee (call_stmt);
5257 if (cfi->id == anything_id)
5258 {
5259 if (gimple_vdef (t))
5260 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
5261 anything_id);
5262 make_constraint_from (first_vi_for_offset (fi, fi_uses),
5263 anything_id);
5264 return;
5265 }
5266
5267 /* For callees without function info (that's external functions),
5268 ESCAPED is clobbered and used. */
5269 if (gimple_call_fndecl (t)
5270 && !cfi->is_fn_info)
5271 {
5272 varinfo_t vi;
5273
5274 if (gimple_vdef (t))
5275 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
5276 escaped_id);
5277 make_copy_constraint (first_vi_for_offset (fi, fi_uses), escaped_id);
5278
5279 /* Also honor the call statement use/clobber info. */
5280 if ((vi = lookup_call_clobber_vi (call_stmt)) != NULL)
5281 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
5282 vi->id);
5283 if ((vi = lookup_call_use_vi (call_stmt)) != NULL)
5284 make_copy_constraint (first_vi_for_offset (fi, fi_uses),
5285 vi->id);
5286 return;
5287 }
5288
5289 /* Otherwise the caller clobbers and uses what the callee does.
5290 ??? This should use a new complex constraint that filters
5291 local variables of the callee. */
5292 if (gimple_vdef (t))
5293 {
5294 lhs = get_function_part_constraint (fi, fi_clobbers);
5295 rhs = get_function_part_constraint (cfi, fi_clobbers);
5296 process_constraint (new_constraint (lhs, rhs));
5297 }
5298 lhs = get_function_part_constraint (fi, fi_uses);
5299 rhs = get_function_part_constraint (cfi, fi_uses);
5300 process_constraint (new_constraint (lhs, rhs));
5301 }
5302 else if (gimple_code (t) == GIMPLE_ASM)
5303 {
5304 /* ??? Ick. We can do better. */
5305 if (gimple_vdef (t))
5306 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
5307 anything_id);
5308 make_constraint_from (first_vi_for_offset (fi, fi_uses),
5309 anything_id);
5310 }
5311 }
5312
5313
5314 /* Find the first varinfo in the same variable as START that overlaps with
5315 OFFSET. Return NULL if we can't find one. */
5316
5317 static varinfo_t
first_vi_for_offset(varinfo_t start,unsigned HOST_WIDE_INT offset)5318 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
5319 {
5320 /* If the offset is outside of the variable, bail out. */
5321 if (offset >= start->fullsize)
5322 return NULL;
5323
5324 /* If we cannot reach offset from start, lookup the first field
5325 and start from there. */
5326 if (start->offset > offset)
5327 start = get_varinfo (start->head);
5328
5329 while (start)
5330 {
5331 /* We may not find a variable in the field list with the actual
5332 offset when we have glommed a structure to a variable.
5333 In that case, however, offset should still be within the size
5334 of the variable. */
5335 if (offset >= start->offset
5336 && (offset - start->offset) < start->size)
5337 return start;
5338
5339 start = vi_next (start);
5340 }
5341
5342 return NULL;
5343 }
5344
5345 /* Find the first varinfo in the same variable as START that overlaps with
5346 OFFSET. If there is no such varinfo the varinfo directly preceding
5347 OFFSET is returned. */
5348
5349 static varinfo_t
first_or_preceding_vi_for_offset(varinfo_t start,unsigned HOST_WIDE_INT offset)5350 first_or_preceding_vi_for_offset (varinfo_t start,
5351 unsigned HOST_WIDE_INT offset)
5352 {
5353 /* If we cannot reach offset from start, lookup the first field
5354 and start from there. */
5355 if (start->offset > offset)
5356 start = get_varinfo (start->head);
5357
5358 /* We may not find a variable in the field list with the actual
5359 offset when we have glommed a structure to a variable.
5360 In that case, however, offset should still be within the size
5361 of the variable.
5362 If we got beyond the offset we look for return the field
5363 directly preceding offset which may be the last field. */
5364 while (start->next
5365 && offset >= start->offset
5366 && !((offset - start->offset) < start->size))
5367 start = vi_next (start);
5368
5369 return start;
5370 }
5371
5372
5373 /* This structure is used during pushing fields onto the fieldstack
5374 to track the offset of the field, since bitpos_of_field gives it
5375 relative to its immediate containing type, and we want it relative
5376 to the ultimate containing object. */
5377
5378 struct fieldoff
5379 {
5380 /* Offset from the base of the base containing object to this field. */
5381 HOST_WIDE_INT offset;
5382
5383 /* Size, in bits, of the field. */
5384 unsigned HOST_WIDE_INT size;
5385
5386 unsigned has_unknown_size : 1;
5387
5388 unsigned must_have_pointers : 1;
5389
5390 unsigned may_have_pointers : 1;
5391
5392 unsigned only_restrict_pointers : 1;
5393
5394 tree restrict_pointed_type;
5395 };
5396 typedef struct fieldoff fieldoff_s;
5397
5398
5399 /* qsort comparison function for two fieldoff's PA and PB */
5400
5401 static int
fieldoff_compare(const void * pa,const void * pb)5402 fieldoff_compare (const void *pa, const void *pb)
5403 {
5404 const fieldoff_s *foa = (const fieldoff_s *)pa;
5405 const fieldoff_s *fob = (const fieldoff_s *)pb;
5406 unsigned HOST_WIDE_INT foasize, fobsize;
5407
5408 if (foa->offset < fob->offset)
5409 return -1;
5410 else if (foa->offset > fob->offset)
5411 return 1;
5412
5413 foasize = foa->size;
5414 fobsize = fob->size;
5415 if (foasize < fobsize)
5416 return -1;
5417 else if (foasize > fobsize)
5418 return 1;
5419 return 0;
5420 }
5421
5422 /* Sort a fieldstack according to the field offset and sizes. */
5423 static void
sort_fieldstack(vec<fieldoff_s> fieldstack)5424 sort_fieldstack (vec<fieldoff_s> fieldstack)
5425 {
5426 fieldstack.qsort (fieldoff_compare);
5427 }
5428
5429 /* Return true if T is a type that can have subvars. */
5430
5431 static inline bool
type_can_have_subvars(const_tree t)5432 type_can_have_subvars (const_tree t)
5433 {
5434 /* Aggregates without overlapping fields can have subvars. */
5435 return TREE_CODE (t) == RECORD_TYPE;
5436 }
5437
5438 /* Return true if V is a tree that we can have subvars for.
5439 Normally, this is any aggregate type. Also complex
5440 types which are not gimple registers can have subvars. */
5441
5442 static inline bool
var_can_have_subvars(const_tree v)5443 var_can_have_subvars (const_tree v)
5444 {
5445 /* Volatile variables should never have subvars. */
5446 if (TREE_THIS_VOLATILE (v))
5447 return false;
5448
5449 /* Non decls or memory tags can never have subvars. */
5450 if (!DECL_P (v))
5451 return false;
5452
5453 return type_can_have_subvars (TREE_TYPE (v));
5454 }
5455
5456 /* Return true if T is a type that does contain pointers. */
5457
5458 static bool
type_must_have_pointers(tree type)5459 type_must_have_pointers (tree type)
5460 {
5461 if (POINTER_TYPE_P (type))
5462 return true;
5463
5464 if (TREE_CODE (type) == ARRAY_TYPE)
5465 return type_must_have_pointers (TREE_TYPE (type));
5466
5467 /* A function or method can have pointers as arguments, so track
5468 those separately. */
5469 if (TREE_CODE (type) == FUNCTION_TYPE
5470 || TREE_CODE (type) == METHOD_TYPE)
5471 return true;
5472
5473 return false;
5474 }
5475
5476 static bool
field_must_have_pointers(tree t)5477 field_must_have_pointers (tree t)
5478 {
5479 return type_must_have_pointers (TREE_TYPE (t));
5480 }
5481
5482 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
5483 the fields of TYPE onto fieldstack, recording their offsets along
5484 the way.
5485
5486 OFFSET is used to keep track of the offset in this entire
5487 structure, rather than just the immediately containing structure.
5488 Returns false if the caller is supposed to handle the field we
5489 recursed for. */
5490
5491 static bool
push_fields_onto_fieldstack(tree type,vec<fieldoff_s> * fieldstack,HOST_WIDE_INT offset)5492 push_fields_onto_fieldstack (tree type, vec<fieldoff_s> *fieldstack,
5493 HOST_WIDE_INT offset)
5494 {
5495 tree field;
5496 bool empty_p = true;
5497
5498 if (TREE_CODE (type) != RECORD_TYPE)
5499 return false;
5500
5501 /* If the vector of fields is growing too big, bail out early.
5502 Callers check for vec::length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
5503 sure this fails. */
5504 if (fieldstack->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
5505 return false;
5506
5507 for (field = TYPE_FIELDS (type); field; field = DECL_CHAIN (field))
5508 if (TREE_CODE (field) == FIELD_DECL)
5509 {
5510 bool push = false;
5511 HOST_WIDE_INT foff = bitpos_of_field (field);
5512 tree field_type = TREE_TYPE (field);
5513
5514 if (!var_can_have_subvars (field)
5515 || TREE_CODE (field_type) == QUAL_UNION_TYPE
5516 || TREE_CODE (field_type) == UNION_TYPE)
5517 push = true;
5518 else if (!push_fields_onto_fieldstack
5519 (field_type, fieldstack, offset + foff)
5520 && (DECL_SIZE (field)
5521 && !integer_zerop (DECL_SIZE (field))))
5522 /* Empty structures may have actual size, like in C++. So
5523 see if we didn't push any subfields and the size is
5524 nonzero, push the field onto the stack. */
5525 push = true;
5526
5527 if (push)
5528 {
5529 fieldoff_s *pair = NULL;
5530 bool has_unknown_size = false;
5531 bool must_have_pointers_p;
5532
5533 if (!fieldstack->is_empty ())
5534 pair = &fieldstack->last ();
5535
5536 /* If there isn't anything at offset zero, create sth. */
5537 if (!pair
5538 && offset + foff != 0)
5539 {
5540 fieldoff_s e
5541 = {0, offset + foff, false, false, true, false, NULL_TREE};
5542 pair = fieldstack->safe_push (e);
5543 }
5544
5545 if (!DECL_SIZE (field)
5546 || !tree_fits_uhwi_p (DECL_SIZE (field)))
5547 has_unknown_size = true;
5548
5549 /* If adjacent fields do not contain pointers merge them. */
5550 must_have_pointers_p = field_must_have_pointers (field);
5551 if (pair
5552 && !has_unknown_size
5553 && !must_have_pointers_p
5554 && !pair->must_have_pointers
5555 && !pair->has_unknown_size
5556 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
5557 {
5558 pair->size += tree_to_uhwi (DECL_SIZE (field));
5559 }
5560 else
5561 {
5562 fieldoff_s e;
5563 e.offset = offset + foff;
5564 e.has_unknown_size = has_unknown_size;
5565 if (!has_unknown_size)
5566 e.size = tree_to_uhwi (DECL_SIZE (field));
5567 else
5568 e.size = -1;
5569 e.must_have_pointers = must_have_pointers_p;
5570 e.may_have_pointers = true;
5571 e.only_restrict_pointers
5572 = (!has_unknown_size
5573 && POINTER_TYPE_P (field_type)
5574 && TYPE_RESTRICT (field_type));
5575 if (e.only_restrict_pointers)
5576 e.restrict_pointed_type = TREE_TYPE (field_type);
5577 fieldstack->safe_push (e);
5578 }
5579 }
5580
5581 empty_p = false;
5582 }
5583
5584 return !empty_p;
5585 }
5586
5587 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5588 if it is a varargs function. */
5589
5590 static unsigned int
count_num_arguments(tree decl,bool * is_varargs)5591 count_num_arguments (tree decl, bool *is_varargs)
5592 {
5593 unsigned int num = 0;
5594 tree t;
5595
5596 /* Capture named arguments for K&R functions. They do not
5597 have a prototype and thus no TYPE_ARG_TYPES. */
5598 for (t = DECL_ARGUMENTS (decl); t; t = DECL_CHAIN (t))
5599 ++num;
5600
5601 /* Check if the function has variadic arguments. */
5602 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); t; t = TREE_CHAIN (t))
5603 if (TREE_VALUE (t) == void_type_node)
5604 break;
5605 if (!t)
5606 *is_varargs = true;
5607
5608 return num;
5609 }
5610
5611 /* Creation function node for DECL, using NAME, and return the index
5612 of the variable we've created for the function. If NONLOCAL_p, create
5613 initial constraints. */
5614
5615 static varinfo_t
create_function_info_for(tree decl,const char * name,bool add_id,bool nonlocal_p)5616 create_function_info_for (tree decl, const char *name, bool add_id,
5617 bool nonlocal_p)
5618 {
5619 struct function *fn = DECL_STRUCT_FUNCTION (decl);
5620 varinfo_t vi, prev_vi;
5621 tree arg;
5622 unsigned int i;
5623 bool is_varargs = false;
5624 unsigned int num_args = count_num_arguments (decl, &is_varargs);
5625
5626 /* Create the variable info. */
5627
5628 vi = new_var_info (decl, name, add_id);
5629 vi->offset = 0;
5630 vi->size = 1;
5631 vi->fullsize = fi_parm_base + num_args;
5632 vi->is_fn_info = 1;
5633 vi->may_have_pointers = false;
5634 if (is_varargs)
5635 vi->fullsize = ~0;
5636 insert_vi_for_tree (vi->decl, vi);
5637
5638 prev_vi = vi;
5639
5640 /* Create a variable for things the function clobbers and one for
5641 things the function uses. */
5642 {
5643 varinfo_t clobbervi, usevi;
5644 const char *newname;
5645 char *tempname;
5646
5647 tempname = xasprintf ("%s.clobber", name);
5648 newname = ggc_strdup (tempname);
5649 free (tempname);
5650
5651 clobbervi = new_var_info (NULL, newname, false);
5652 clobbervi->offset = fi_clobbers;
5653 clobbervi->size = 1;
5654 clobbervi->fullsize = vi->fullsize;
5655 clobbervi->is_full_var = true;
5656 clobbervi->is_global_var = false;
5657
5658 gcc_assert (prev_vi->offset < clobbervi->offset);
5659 prev_vi->next = clobbervi->id;
5660 prev_vi = clobbervi;
5661
5662 tempname = xasprintf ("%s.use", name);
5663 newname = ggc_strdup (tempname);
5664 free (tempname);
5665
5666 usevi = new_var_info (NULL, newname, false);
5667 usevi->offset = fi_uses;
5668 usevi->size = 1;
5669 usevi->fullsize = vi->fullsize;
5670 usevi->is_full_var = true;
5671 usevi->is_global_var = false;
5672
5673 gcc_assert (prev_vi->offset < usevi->offset);
5674 prev_vi->next = usevi->id;
5675 prev_vi = usevi;
5676 }
5677
5678 /* And one for the static chain. */
5679 if (fn->static_chain_decl != NULL_TREE)
5680 {
5681 varinfo_t chainvi;
5682 const char *newname;
5683 char *tempname;
5684
5685 tempname = xasprintf ("%s.chain", name);
5686 newname = ggc_strdup (tempname);
5687 free (tempname);
5688
5689 chainvi = new_var_info (fn->static_chain_decl, newname, false);
5690 chainvi->offset = fi_static_chain;
5691 chainvi->size = 1;
5692 chainvi->fullsize = vi->fullsize;
5693 chainvi->is_full_var = true;
5694 chainvi->is_global_var = false;
5695
5696 insert_vi_for_tree (fn->static_chain_decl, chainvi);
5697
5698 if (nonlocal_p
5699 && chainvi->may_have_pointers)
5700 make_constraint_from (chainvi, nonlocal_id);
5701
5702 gcc_assert (prev_vi->offset < chainvi->offset);
5703 prev_vi->next = chainvi->id;
5704 prev_vi = chainvi;
5705 }
5706
5707 /* Create a variable for the return var. */
5708 if (DECL_RESULT (decl) != NULL
5709 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
5710 {
5711 varinfo_t resultvi;
5712 const char *newname;
5713 char *tempname;
5714 tree resultdecl = decl;
5715
5716 if (DECL_RESULT (decl))
5717 resultdecl = DECL_RESULT (decl);
5718
5719 tempname = xasprintf ("%s.result", name);
5720 newname = ggc_strdup (tempname);
5721 free (tempname);
5722
5723 resultvi = new_var_info (resultdecl, newname, false);
5724 resultvi->offset = fi_result;
5725 resultvi->size = 1;
5726 resultvi->fullsize = vi->fullsize;
5727 resultvi->is_full_var = true;
5728 if (DECL_RESULT (decl))
5729 resultvi->may_have_pointers = true;
5730
5731 if (DECL_RESULT (decl))
5732 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
5733
5734 if (nonlocal_p
5735 && DECL_RESULT (decl)
5736 && DECL_BY_REFERENCE (DECL_RESULT (decl)))
5737 make_constraint_from (resultvi, nonlocal_id);
5738
5739 gcc_assert (prev_vi->offset < resultvi->offset);
5740 prev_vi->next = resultvi->id;
5741 prev_vi = resultvi;
5742 }
5743
5744 /* We also need to make function return values escape. Nothing
5745 escapes by returning from main though. */
5746 if (nonlocal_p
5747 && !MAIN_NAME_P (DECL_NAME (decl)))
5748 {
5749 varinfo_t fi, rvi;
5750 fi = lookup_vi_for_tree (decl);
5751 rvi = first_vi_for_offset (fi, fi_result);
5752 if (rvi && rvi->offset == fi_result)
5753 make_copy_constraint (get_varinfo (escaped_id), rvi->id);
5754 }
5755
5756 /* Set up variables for each argument. */
5757 arg = DECL_ARGUMENTS (decl);
5758 for (i = 0; i < num_args; i++)
5759 {
5760 varinfo_t argvi;
5761 const char *newname;
5762 char *tempname;
5763 tree argdecl = decl;
5764
5765 if (arg)
5766 argdecl = arg;
5767
5768 tempname = xasprintf ("%s.arg%d", name, i);
5769 newname = ggc_strdup (tempname);
5770 free (tempname);
5771
5772 argvi = new_var_info (argdecl, newname, false);
5773 argvi->offset = fi_parm_base + i;
5774 argvi->size = 1;
5775 argvi->is_full_var = true;
5776 argvi->fullsize = vi->fullsize;
5777 if (arg)
5778 argvi->may_have_pointers = true;
5779
5780 if (arg)
5781 insert_vi_for_tree (arg, argvi);
5782
5783 if (nonlocal_p
5784 && argvi->may_have_pointers)
5785 make_constraint_from (argvi, nonlocal_id);
5786
5787 gcc_assert (prev_vi->offset < argvi->offset);
5788 prev_vi->next = argvi->id;
5789 prev_vi = argvi;
5790 if (arg)
5791 arg = DECL_CHAIN (arg);
5792 }
5793
5794 /* Add one representative for all further args. */
5795 if (is_varargs)
5796 {
5797 varinfo_t argvi;
5798 const char *newname;
5799 char *tempname;
5800 tree decl;
5801
5802 tempname = xasprintf ("%s.varargs", name);
5803 newname = ggc_strdup (tempname);
5804 free (tempname);
5805
5806 /* We need sth that can be pointed to for va_start. */
5807 decl = build_fake_var_decl (ptr_type_node);
5808
5809 argvi = new_var_info (decl, newname, false);
5810 argvi->offset = fi_parm_base + num_args;
5811 argvi->size = ~0;
5812 argvi->is_full_var = true;
5813 argvi->is_heap_var = true;
5814 argvi->fullsize = vi->fullsize;
5815
5816 if (nonlocal_p
5817 && argvi->may_have_pointers)
5818 make_constraint_from (argvi, nonlocal_id);
5819
5820 gcc_assert (prev_vi->offset < argvi->offset);
5821 prev_vi->next = argvi->id;
5822 prev_vi = argvi;
5823 }
5824
5825 return vi;
5826 }
5827
5828
5829 /* Return true if FIELDSTACK contains fields that overlap.
5830 FIELDSTACK is assumed to be sorted by offset. */
5831
5832 static bool
check_for_overlaps(vec<fieldoff_s> fieldstack)5833 check_for_overlaps (vec<fieldoff_s> fieldstack)
5834 {
5835 fieldoff_s *fo = NULL;
5836 unsigned int i;
5837 HOST_WIDE_INT lastoffset = -1;
5838
5839 FOR_EACH_VEC_ELT (fieldstack, i, fo)
5840 {
5841 if (fo->offset == lastoffset)
5842 return true;
5843 lastoffset = fo->offset;
5844 }
5845 return false;
5846 }
5847
5848 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5849 This will also create any varinfo structures necessary for fields
5850 of DECL. DECL is a function parameter if HANDLE_PARAM is set.
5851 HANDLED_STRUCT_TYPE is used to register struct types reached by following
5852 restrict pointers. This is needed to prevent infinite recursion. */
5853
5854 static varinfo_t
create_variable_info_for_1(tree decl,const char * name,bool add_id,bool handle_param,bitmap handled_struct_type)5855 create_variable_info_for_1 (tree decl, const char *name, bool add_id,
5856 bool handle_param, bitmap handled_struct_type)
5857 {
5858 varinfo_t vi, newvi;
5859 tree decl_type = TREE_TYPE (decl);
5860 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
5861 auto_vec<fieldoff_s> fieldstack;
5862 fieldoff_s *fo;
5863 unsigned int i;
5864
5865 if (!declsize
5866 || !tree_fits_uhwi_p (declsize))
5867 {
5868 vi = new_var_info (decl, name, add_id);
5869 vi->offset = 0;
5870 vi->size = ~0;
5871 vi->fullsize = ~0;
5872 vi->is_unknown_size_var = true;
5873 vi->is_full_var = true;
5874 vi->may_have_pointers = true;
5875 return vi;
5876 }
5877
5878 /* Collect field information. */
5879 if (use_field_sensitive
5880 && var_can_have_subvars (decl)
5881 /* ??? Force us to not use subfields for globals in IPA mode.
5882 Else we'd have to parse arbitrary initializers. */
5883 && !(in_ipa_mode
5884 && is_global_var (decl)))
5885 {
5886 fieldoff_s *fo = NULL;
5887 bool notokay = false;
5888 unsigned int i;
5889
5890 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
5891
5892 for (i = 0; !notokay && fieldstack.iterate (i, &fo); i++)
5893 if (fo->has_unknown_size
5894 || fo->offset < 0)
5895 {
5896 notokay = true;
5897 break;
5898 }
5899
5900 /* We can't sort them if we have a field with a variable sized type,
5901 which will make notokay = true. In that case, we are going to return
5902 without creating varinfos for the fields anyway, so sorting them is a
5903 waste to boot. */
5904 if (!notokay)
5905 {
5906 sort_fieldstack (fieldstack);
5907 /* Due to some C++ FE issues, like PR 22488, we might end up
5908 what appear to be overlapping fields even though they,
5909 in reality, do not overlap. Until the C++ FE is fixed,
5910 we will simply disable field-sensitivity for these cases. */
5911 notokay = check_for_overlaps (fieldstack);
5912 }
5913
5914 if (notokay)
5915 fieldstack.release ();
5916 }
5917
5918 /* If we didn't end up collecting sub-variables create a full
5919 variable for the decl. */
5920 if (fieldstack.length () == 0
5921 || fieldstack.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
5922 {
5923 vi = new_var_info (decl, name, add_id);
5924 vi->offset = 0;
5925 vi->may_have_pointers = true;
5926 vi->fullsize = tree_to_uhwi (declsize);
5927 vi->size = vi->fullsize;
5928 vi->is_full_var = true;
5929 if (POINTER_TYPE_P (decl_type)
5930 && TYPE_RESTRICT (decl_type))
5931 vi->only_restrict_pointers = 1;
5932 if (vi->only_restrict_pointers
5933 && !type_contains_placeholder_p (TREE_TYPE (decl_type))
5934 && handle_param
5935 && !bitmap_bit_p (handled_struct_type,
5936 TYPE_UID (TREE_TYPE (decl_type))))
5937 {
5938 varinfo_t rvi;
5939 tree heapvar = build_fake_var_decl (TREE_TYPE (decl_type));
5940 DECL_EXTERNAL (heapvar) = 1;
5941 if (var_can_have_subvars (heapvar))
5942 bitmap_set_bit (handled_struct_type,
5943 TYPE_UID (TREE_TYPE (decl_type)));
5944 rvi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS", true,
5945 true, handled_struct_type);
5946 if (var_can_have_subvars (heapvar))
5947 bitmap_clear_bit (handled_struct_type,
5948 TYPE_UID (TREE_TYPE (decl_type)));
5949 rvi->is_restrict_var = 1;
5950 insert_vi_for_tree (heapvar, rvi);
5951 make_constraint_from (vi, rvi->id);
5952 make_param_constraints (rvi);
5953 }
5954 fieldstack.release ();
5955 return vi;
5956 }
5957
5958 vi = new_var_info (decl, name, add_id);
5959 vi->fullsize = tree_to_uhwi (declsize);
5960 if (fieldstack.length () == 1)
5961 vi->is_full_var = true;
5962 for (i = 0, newvi = vi;
5963 fieldstack.iterate (i, &fo);
5964 ++i, newvi = vi_next (newvi))
5965 {
5966 const char *newname = NULL;
5967 char *tempname;
5968
5969 if (dump_file)
5970 {
5971 if (fieldstack.length () != 1)
5972 {
5973 tempname
5974 = xasprintf ("%s." HOST_WIDE_INT_PRINT_DEC
5975 "+" HOST_WIDE_INT_PRINT_DEC, name,
5976 fo->offset, fo->size);
5977 newname = ggc_strdup (tempname);
5978 free (tempname);
5979 }
5980 }
5981 else
5982 newname = "NULL";
5983
5984 if (newname)
5985 newvi->name = newname;
5986 newvi->offset = fo->offset;
5987 newvi->size = fo->size;
5988 newvi->fullsize = vi->fullsize;
5989 newvi->may_have_pointers = fo->may_have_pointers;
5990 newvi->only_restrict_pointers = fo->only_restrict_pointers;
5991 if (handle_param
5992 && newvi->only_restrict_pointers
5993 && !type_contains_placeholder_p (fo->restrict_pointed_type)
5994 && !bitmap_bit_p (handled_struct_type,
5995 TYPE_UID (fo->restrict_pointed_type)))
5996 {
5997 varinfo_t rvi;
5998 tree heapvar = build_fake_var_decl (fo->restrict_pointed_type);
5999 DECL_EXTERNAL (heapvar) = 1;
6000 if (var_can_have_subvars (heapvar))
6001 bitmap_set_bit (handled_struct_type,
6002 TYPE_UID (fo->restrict_pointed_type));
6003 rvi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS", true,
6004 true, handled_struct_type);
6005 if (var_can_have_subvars (heapvar))
6006 bitmap_clear_bit (handled_struct_type,
6007 TYPE_UID (fo->restrict_pointed_type));
6008 rvi->is_restrict_var = 1;
6009 insert_vi_for_tree (heapvar, rvi);
6010 make_constraint_from (newvi, rvi->id);
6011 make_param_constraints (rvi);
6012 }
6013 if (i + 1 < fieldstack.length ())
6014 {
6015 varinfo_t tem = new_var_info (decl, name, false);
6016 newvi->next = tem->id;
6017 tem->head = vi->id;
6018 }
6019 }
6020
6021 return vi;
6022 }
6023
6024 static unsigned int
create_variable_info_for(tree decl,const char * name,bool add_id)6025 create_variable_info_for (tree decl, const char *name, bool add_id)
6026 {
6027 varinfo_t vi = create_variable_info_for_1 (decl, name, add_id, false, NULL);
6028 unsigned int id = vi->id;
6029
6030 insert_vi_for_tree (decl, vi);
6031
6032 if (TREE_CODE (decl) != VAR_DECL)
6033 return id;
6034
6035 /* Create initial constraints for globals. */
6036 for (; vi; vi = vi_next (vi))
6037 {
6038 if (!vi->may_have_pointers
6039 || !vi->is_global_var)
6040 continue;
6041
6042 /* Mark global restrict qualified pointers. */
6043 if ((POINTER_TYPE_P (TREE_TYPE (decl))
6044 && TYPE_RESTRICT (TREE_TYPE (decl)))
6045 || vi->only_restrict_pointers)
6046 {
6047 varinfo_t rvi
6048 = make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT",
6049 true);
6050 /* ??? For now exclude reads from globals as restrict sources
6051 if those are not (indirectly) from incoming parameters. */
6052 rvi->is_restrict_var = false;
6053 continue;
6054 }
6055
6056 /* In non-IPA mode the initializer from nonlocal is all we need. */
6057 if (!in_ipa_mode
6058 || DECL_HARD_REGISTER (decl))
6059 make_copy_constraint (vi, nonlocal_id);
6060
6061 /* In IPA mode parse the initializer and generate proper constraints
6062 for it. */
6063 else
6064 {
6065 varpool_node *vnode = varpool_node::get (decl);
6066
6067 /* For escaped variables initialize them from nonlocal. */
6068 if (!vnode->all_refs_explicit_p ())
6069 make_copy_constraint (vi, nonlocal_id);
6070
6071 /* If this is a global variable with an initializer and we are in
6072 IPA mode generate constraints for it. */
6073 ipa_ref *ref;
6074 for (unsigned idx = 0; vnode->iterate_reference (idx, ref); ++idx)
6075 {
6076 auto_vec<ce_s> rhsc;
6077 struct constraint_expr lhs, *rhsp;
6078 unsigned i;
6079 get_constraint_for_address_of (ref->referred->decl, &rhsc);
6080 lhs.var = vi->id;
6081 lhs.offset = 0;
6082 lhs.type = SCALAR;
6083 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
6084 process_constraint (new_constraint (lhs, *rhsp));
6085 /* If this is a variable that escapes from the unit
6086 the initializer escapes as well. */
6087 if (!vnode->all_refs_explicit_p ())
6088 {
6089 lhs.var = escaped_id;
6090 lhs.offset = 0;
6091 lhs.type = SCALAR;
6092 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
6093 process_constraint (new_constraint (lhs, *rhsp));
6094 }
6095 }
6096 }
6097 }
6098
6099 return id;
6100 }
6101
6102 /* Print out the points-to solution for VAR to FILE. */
6103
6104 static void
dump_solution_for_var(FILE * file,unsigned int var)6105 dump_solution_for_var (FILE *file, unsigned int var)
6106 {
6107 varinfo_t vi = get_varinfo (var);
6108 unsigned int i;
6109 bitmap_iterator bi;
6110
6111 /* Dump the solution for unified vars anyway, this avoids difficulties
6112 in scanning dumps in the testsuite. */
6113 fprintf (file, "%s = { ", vi->name);
6114 vi = get_varinfo (find (var));
6115 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
6116 fprintf (file, "%s ", get_varinfo (i)->name);
6117 fprintf (file, "}");
6118
6119 /* But note when the variable was unified. */
6120 if (vi->id != var)
6121 fprintf (file, " same as %s", vi->name);
6122
6123 fprintf (file, "\n");
6124 }
6125
6126 /* Print the points-to solution for VAR to stderr. */
6127
6128 DEBUG_FUNCTION void
debug_solution_for_var(unsigned int var)6129 debug_solution_for_var (unsigned int var)
6130 {
6131 dump_solution_for_var (stderr, var);
6132 }
6133
6134 /* Register the constraints for function parameter related VI. */
6135
6136 static void
make_param_constraints(varinfo_t vi)6137 make_param_constraints (varinfo_t vi)
6138 {
6139 for (; vi; vi = vi_next (vi))
6140 {
6141 if (vi->only_restrict_pointers)
6142 ;
6143 else if (vi->may_have_pointers)
6144 make_constraint_from (vi, nonlocal_id);
6145
6146 if (vi->is_full_var)
6147 break;
6148 }
6149 }
6150
6151 /* Create varinfo structures for all of the variables in the
6152 function for intraprocedural mode. */
6153
6154 static void
intra_create_variable_infos(struct function * fn)6155 intra_create_variable_infos (struct function *fn)
6156 {
6157 tree t;
6158 bitmap handled_struct_type = NULL;
6159
6160 /* For each incoming pointer argument arg, create the constraint ARG
6161 = NONLOCAL or a dummy variable if it is a restrict qualified
6162 passed-by-reference argument. */
6163 for (t = DECL_ARGUMENTS (fn->decl); t; t = DECL_CHAIN (t))
6164 {
6165 if (handled_struct_type == NULL)
6166 handled_struct_type = BITMAP_ALLOC (NULL);
6167
6168 varinfo_t p
6169 = create_variable_info_for_1 (t, alias_get_name (t), false, true,
6170 handled_struct_type);
6171 insert_vi_for_tree (t, p);
6172
6173 make_param_constraints (p);
6174 }
6175
6176 if (handled_struct_type != NULL)
6177 BITMAP_FREE (handled_struct_type);
6178
6179 /* Add a constraint for a result decl that is passed by reference. */
6180 if (DECL_RESULT (fn->decl)
6181 && DECL_BY_REFERENCE (DECL_RESULT (fn->decl)))
6182 {
6183 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (fn->decl));
6184
6185 for (p = result_vi; p; p = vi_next (p))
6186 make_constraint_from (p, nonlocal_id);
6187 }
6188
6189 /* Add a constraint for the incoming static chain parameter. */
6190 if (fn->static_chain_decl != NULL_TREE)
6191 {
6192 varinfo_t p, chain_vi = get_vi_for_tree (fn->static_chain_decl);
6193
6194 for (p = chain_vi; p; p = vi_next (p))
6195 make_constraint_from (p, nonlocal_id);
6196 }
6197 }
6198
6199 /* Structure used to put solution bitmaps in a hashtable so they can
6200 be shared among variables with the same points-to set. */
6201
6202 typedef struct shared_bitmap_info
6203 {
6204 bitmap pt_vars;
6205 hashval_t hashcode;
6206 } *shared_bitmap_info_t;
6207 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
6208
6209 /* Shared_bitmap hashtable helpers. */
6210
6211 struct shared_bitmap_hasher : free_ptr_hash <shared_bitmap_info>
6212 {
6213 static inline hashval_t hash (const shared_bitmap_info *);
6214 static inline bool equal (const shared_bitmap_info *,
6215 const shared_bitmap_info *);
6216 };
6217
6218 /* Hash function for a shared_bitmap_info_t */
6219
6220 inline hashval_t
hash(const shared_bitmap_info * bi)6221 shared_bitmap_hasher::hash (const shared_bitmap_info *bi)
6222 {
6223 return bi->hashcode;
6224 }
6225
6226 /* Equality function for two shared_bitmap_info_t's. */
6227
6228 inline bool
equal(const shared_bitmap_info * sbi1,const shared_bitmap_info * sbi2)6229 shared_bitmap_hasher::equal (const shared_bitmap_info *sbi1,
6230 const shared_bitmap_info *sbi2)
6231 {
6232 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
6233 }
6234
6235 /* Shared_bitmap hashtable. */
6236
6237 static hash_table<shared_bitmap_hasher> *shared_bitmap_table;
6238
6239 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
6240 existing instance if there is one, NULL otherwise. */
6241
6242 static bitmap
shared_bitmap_lookup(bitmap pt_vars)6243 shared_bitmap_lookup (bitmap pt_vars)
6244 {
6245 shared_bitmap_info **slot;
6246 struct shared_bitmap_info sbi;
6247
6248 sbi.pt_vars = pt_vars;
6249 sbi.hashcode = bitmap_hash (pt_vars);
6250
6251 slot = shared_bitmap_table->find_slot (&sbi, NO_INSERT);
6252 if (!slot)
6253 return NULL;
6254 else
6255 return (*slot)->pt_vars;
6256 }
6257
6258
6259 /* Add a bitmap to the shared bitmap hashtable. */
6260
6261 static void
shared_bitmap_add(bitmap pt_vars)6262 shared_bitmap_add (bitmap pt_vars)
6263 {
6264 shared_bitmap_info **slot;
6265 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
6266
6267 sbi->pt_vars = pt_vars;
6268 sbi->hashcode = bitmap_hash (pt_vars);
6269
6270 slot = shared_bitmap_table->find_slot (sbi, INSERT);
6271 gcc_assert (!*slot);
6272 *slot = sbi;
6273 }
6274
6275
6276 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
6277
6278 static void
set_uids_in_ptset(bitmap into,bitmap from,struct pt_solution * pt,tree fndecl)6279 set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt,
6280 tree fndecl)
6281 {
6282 unsigned int i;
6283 bitmap_iterator bi;
6284 varinfo_t escaped_vi = get_varinfo (find (escaped_id));
6285 bool everything_escaped
6286 = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id);
6287
6288 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
6289 {
6290 varinfo_t vi = get_varinfo (i);
6291
6292 /* The only artificial variables that are allowed in a may-alias
6293 set are heap variables. */
6294 if (vi->is_artificial_var && !vi->is_heap_var)
6295 continue;
6296
6297 if (everything_escaped
6298 || (escaped_vi->solution
6299 && bitmap_bit_p (escaped_vi->solution, i)))
6300 {
6301 pt->vars_contains_escaped = true;
6302 pt->vars_contains_escaped_heap = vi->is_heap_var;
6303 }
6304
6305 if (TREE_CODE (vi->decl) == VAR_DECL
6306 || TREE_CODE (vi->decl) == PARM_DECL
6307 || TREE_CODE (vi->decl) == RESULT_DECL)
6308 {
6309 /* If we are in IPA mode we will not recompute points-to
6310 sets after inlining so make sure they stay valid. */
6311 if (in_ipa_mode
6312 && !DECL_PT_UID_SET_P (vi->decl))
6313 SET_DECL_PT_UID (vi->decl, DECL_UID (vi->decl));
6314
6315 /* Add the decl to the points-to set. Note that the points-to
6316 set contains global variables. */
6317 bitmap_set_bit (into, DECL_PT_UID (vi->decl));
6318 if (vi->is_global_var
6319 /* In IPA mode the escaped_heap trick doesn't work as
6320 ESCAPED is escaped from the unit but
6321 pt_solution_includes_global needs to answer true for
6322 all variables not automatic within a function.
6323 For the same reason is_global_var is not the
6324 correct flag to track - local variables from other
6325 functions also need to be considered global.
6326 Conveniently all HEAP vars are not put in function
6327 scope. */
6328 || (in_ipa_mode
6329 && fndecl
6330 && ! auto_var_in_fn_p (vi->decl, fndecl)))
6331 pt->vars_contains_nonlocal = true;
6332 }
6333
6334 else if (TREE_CODE (vi->decl) == FUNCTION_DECL
6335 || TREE_CODE (vi->decl) == LABEL_DECL)
6336 {
6337 /* Nothing should read/write from/to code so we can
6338 save bits by not including them in the points-to bitmaps.
6339 Still mark the points-to set as containing global memory
6340 to make code-patching possible - see PR70128. */
6341 pt->vars_contains_nonlocal = true;
6342 }
6343 }
6344 }
6345
6346
6347 /* Compute the points-to solution *PT for the variable VI. */
6348
6349 static struct pt_solution
find_what_var_points_to(tree fndecl,varinfo_t orig_vi)6350 find_what_var_points_to (tree fndecl, varinfo_t orig_vi)
6351 {
6352 unsigned int i;
6353 bitmap_iterator bi;
6354 bitmap finished_solution;
6355 bitmap result;
6356 varinfo_t vi;
6357 struct pt_solution *pt;
6358
6359 /* This variable may have been collapsed, let's get the real
6360 variable. */
6361 vi = get_varinfo (find (orig_vi->id));
6362
6363 /* See if we have already computed the solution and return it. */
6364 pt_solution **slot = &final_solutions->get_or_insert (vi);
6365 if (*slot != NULL)
6366 return **slot;
6367
6368 *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
6369 memset (pt, 0, sizeof (struct pt_solution));
6370
6371 /* Translate artificial variables into SSA_NAME_PTR_INFO
6372 attributes. */
6373 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
6374 {
6375 varinfo_t vi = get_varinfo (i);
6376
6377 if (vi->is_artificial_var)
6378 {
6379 if (vi->id == nothing_id)
6380 pt->null = 1;
6381 else if (vi->id == escaped_id)
6382 {
6383 if (in_ipa_mode)
6384 pt->ipa_escaped = 1;
6385 else
6386 pt->escaped = 1;
6387 /* Expand some special vars of ESCAPED in-place here. */
6388 varinfo_t evi = get_varinfo (find (escaped_id));
6389 if (bitmap_bit_p (evi->solution, nonlocal_id))
6390 pt->nonlocal = 1;
6391 }
6392 else if (vi->id == nonlocal_id)
6393 pt->nonlocal = 1;
6394 else if (vi->is_heap_var)
6395 /* We represent heapvars in the points-to set properly. */
6396 ;
6397 else if (vi->id == string_id)
6398 /* Nobody cares - STRING_CSTs are read-only entities. */
6399 ;
6400 else if (vi->id == anything_id
6401 || vi->id == integer_id)
6402 pt->anything = 1;
6403 }
6404 }
6405
6406 /* Instead of doing extra work, simply do not create
6407 elaborate points-to information for pt_anything pointers. */
6408 if (pt->anything)
6409 return *pt;
6410
6411 /* Share the final set of variables when possible. */
6412 finished_solution = BITMAP_GGC_ALLOC ();
6413 stats.points_to_sets_created++;
6414
6415 set_uids_in_ptset (finished_solution, vi->solution, pt, fndecl);
6416 result = shared_bitmap_lookup (finished_solution);
6417 if (!result)
6418 {
6419 shared_bitmap_add (finished_solution);
6420 pt->vars = finished_solution;
6421 }
6422 else
6423 {
6424 pt->vars = result;
6425 bitmap_clear (finished_solution);
6426 }
6427
6428 return *pt;
6429 }
6430
6431 /* Given a pointer variable P, fill in its points-to set. */
6432
6433 static void
find_what_p_points_to(tree fndecl,tree p)6434 find_what_p_points_to (tree fndecl, tree p)
6435 {
6436 struct ptr_info_def *pi;
6437 tree lookup_p = p;
6438 varinfo_t vi;
6439
6440 /* For parameters, get at the points-to set for the actual parm
6441 decl. */
6442 if (TREE_CODE (p) == SSA_NAME
6443 && SSA_NAME_IS_DEFAULT_DEF (p)
6444 && (TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
6445 || TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL))
6446 lookup_p = SSA_NAME_VAR (p);
6447
6448 vi = lookup_vi_for_tree (lookup_p);
6449 if (!vi)
6450 return;
6451
6452 pi = get_ptr_info (p);
6453 pi->pt = find_what_var_points_to (fndecl, vi);
6454 }
6455
6456
6457 /* Query statistics for points-to solutions. */
6458
6459 static struct {
6460 unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
6461 unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
6462 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
6463 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
6464 } pta_stats;
6465
6466 void
dump_pta_stats(FILE * s)6467 dump_pta_stats (FILE *s)
6468 {
6469 fprintf (s, "\nPTA query stats:\n");
6470 fprintf (s, " pt_solution_includes: "
6471 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
6472 HOST_WIDE_INT_PRINT_DEC" queries\n",
6473 pta_stats.pt_solution_includes_no_alias,
6474 pta_stats.pt_solution_includes_no_alias
6475 + pta_stats.pt_solution_includes_may_alias);
6476 fprintf (s, " pt_solutions_intersect: "
6477 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
6478 HOST_WIDE_INT_PRINT_DEC" queries\n",
6479 pta_stats.pt_solutions_intersect_no_alias,
6480 pta_stats.pt_solutions_intersect_no_alias
6481 + pta_stats.pt_solutions_intersect_may_alias);
6482 }
6483
6484
6485 /* Reset the points-to solution *PT to a conservative default
6486 (point to anything). */
6487
6488 void
pt_solution_reset(struct pt_solution * pt)6489 pt_solution_reset (struct pt_solution *pt)
6490 {
6491 memset (pt, 0, sizeof (struct pt_solution));
6492 pt->anything = true;
6493 }
6494
6495 /* Set the points-to solution *PT to point only to the variables
6496 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
6497 global variables and VARS_CONTAINS_RESTRICT specifies whether
6498 it contains restrict tag variables. */
6499
6500 void
pt_solution_set(struct pt_solution * pt,bitmap vars,bool vars_contains_nonlocal)6501 pt_solution_set (struct pt_solution *pt, bitmap vars,
6502 bool vars_contains_nonlocal)
6503 {
6504 memset (pt, 0, sizeof (struct pt_solution));
6505 pt->vars = vars;
6506 pt->vars_contains_nonlocal = vars_contains_nonlocal;
6507 pt->vars_contains_escaped
6508 = (cfun->gimple_df->escaped.anything
6509 || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars));
6510 }
6511
6512 /* Set the points-to solution *PT to point only to the variable VAR. */
6513
6514 void
pt_solution_set_var(struct pt_solution * pt,tree var)6515 pt_solution_set_var (struct pt_solution *pt, tree var)
6516 {
6517 memset (pt, 0, sizeof (struct pt_solution));
6518 pt->vars = BITMAP_GGC_ALLOC ();
6519 bitmap_set_bit (pt->vars, DECL_PT_UID (var));
6520 pt->vars_contains_nonlocal = is_global_var (var);
6521 pt->vars_contains_escaped
6522 = (cfun->gimple_df->escaped.anything
6523 || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var)));
6524 }
6525
6526 /* Computes the union of the points-to solutions *DEST and *SRC and
6527 stores the result in *DEST. This changes the points-to bitmap
6528 of *DEST and thus may not be used if that might be shared.
6529 The points-to bitmap of *SRC and *DEST will not be shared after
6530 this function if they were not before. */
6531
6532 static void
pt_solution_ior_into(struct pt_solution * dest,struct pt_solution * src)6533 pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src)
6534 {
6535 dest->anything |= src->anything;
6536 if (dest->anything)
6537 {
6538 pt_solution_reset (dest);
6539 return;
6540 }
6541
6542 dest->nonlocal |= src->nonlocal;
6543 dest->escaped |= src->escaped;
6544 dest->ipa_escaped |= src->ipa_escaped;
6545 dest->null |= src->null;
6546 dest->vars_contains_nonlocal |= src->vars_contains_nonlocal;
6547 dest->vars_contains_escaped |= src->vars_contains_escaped;
6548 dest->vars_contains_escaped_heap |= src->vars_contains_escaped_heap;
6549 if (!src->vars)
6550 return;
6551
6552 if (!dest->vars)
6553 dest->vars = BITMAP_GGC_ALLOC ();
6554 bitmap_ior_into (dest->vars, src->vars);
6555 }
6556
6557 /* Return true if the points-to solution *PT is empty. */
6558
6559 bool
pt_solution_empty_p(struct pt_solution * pt)6560 pt_solution_empty_p (struct pt_solution *pt)
6561 {
6562 if (pt->anything
6563 || pt->nonlocal)
6564 return false;
6565
6566 if (pt->vars
6567 && !bitmap_empty_p (pt->vars))
6568 return false;
6569
6570 /* If the solution includes ESCAPED, check if that is empty. */
6571 if (pt->escaped
6572 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
6573 return false;
6574
6575 /* If the solution includes ESCAPED, check if that is empty. */
6576 if (pt->ipa_escaped
6577 && !pt_solution_empty_p (&ipa_escaped_pt))
6578 return false;
6579
6580 return true;
6581 }
6582
6583 /* Return true if the points-to solution *PT only point to a single var, and
6584 return the var uid in *UID. */
6585
6586 bool
pt_solution_singleton_p(struct pt_solution * pt,unsigned * uid)6587 pt_solution_singleton_p (struct pt_solution *pt, unsigned *uid)
6588 {
6589 if (pt->anything || pt->nonlocal || pt->escaped || pt->ipa_escaped
6590 || pt->null || pt->vars == NULL
6591 || !bitmap_single_bit_set_p (pt->vars))
6592 return false;
6593
6594 *uid = bitmap_first_set_bit (pt->vars);
6595 return true;
6596 }
6597
6598 /* Return true if the points-to solution *PT includes global memory. */
6599
6600 bool
pt_solution_includes_global(struct pt_solution * pt)6601 pt_solution_includes_global (struct pt_solution *pt)
6602 {
6603 if (pt->anything
6604 || pt->nonlocal
6605 || pt->vars_contains_nonlocal
6606 /* The following is a hack to make the malloc escape hack work.
6607 In reality we'd need different sets for escaped-through-return
6608 and escaped-to-callees and passes would need to be updated. */
6609 || pt->vars_contains_escaped_heap)
6610 return true;
6611
6612 /* 'escaped' is also a placeholder so we have to look into it. */
6613 if (pt->escaped)
6614 return pt_solution_includes_global (&cfun->gimple_df->escaped);
6615
6616 if (pt->ipa_escaped)
6617 return pt_solution_includes_global (&ipa_escaped_pt);
6618
6619 return false;
6620 }
6621
6622 /* Return true if the points-to solution *PT includes the variable
6623 declaration DECL. */
6624
6625 static bool
pt_solution_includes_1(struct pt_solution * pt,const_tree decl)6626 pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
6627 {
6628 if (pt->anything)
6629 return true;
6630
6631 if (pt->nonlocal
6632 && is_global_var (decl))
6633 return true;
6634
6635 if (pt->vars
6636 && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
6637 return true;
6638
6639 /* If the solution includes ESCAPED, check it. */
6640 if (pt->escaped
6641 && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
6642 return true;
6643
6644 /* If the solution includes ESCAPED, check it. */
6645 if (pt->ipa_escaped
6646 && pt_solution_includes_1 (&ipa_escaped_pt, decl))
6647 return true;
6648
6649 return false;
6650 }
6651
6652 bool
pt_solution_includes(struct pt_solution * pt,const_tree decl)6653 pt_solution_includes (struct pt_solution *pt, const_tree decl)
6654 {
6655 bool res = pt_solution_includes_1 (pt, decl);
6656 if (res)
6657 ++pta_stats.pt_solution_includes_may_alias;
6658 else
6659 ++pta_stats.pt_solution_includes_no_alias;
6660 return res;
6661 }
6662
6663 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
6664 intersection. */
6665
6666 static bool
pt_solutions_intersect_1(struct pt_solution * pt1,struct pt_solution * pt2)6667 pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
6668 {
6669 if (pt1->anything || pt2->anything)
6670 return true;
6671
6672 /* If either points to unknown global memory and the other points to
6673 any global memory they alias. */
6674 if ((pt1->nonlocal
6675 && (pt2->nonlocal
6676 || pt2->vars_contains_nonlocal))
6677 || (pt2->nonlocal
6678 && pt1->vars_contains_nonlocal))
6679 return true;
6680
6681 /* If either points to all escaped memory and the other points to
6682 any escaped memory they alias. */
6683 if ((pt1->escaped
6684 && (pt2->escaped
6685 || pt2->vars_contains_escaped))
6686 || (pt2->escaped
6687 && pt1->vars_contains_escaped))
6688 return true;
6689
6690 /* Check the escaped solution if required.
6691 ??? Do we need to check the local against the IPA escaped sets? */
6692 if ((pt1->ipa_escaped || pt2->ipa_escaped)
6693 && !pt_solution_empty_p (&ipa_escaped_pt))
6694 {
6695 /* If both point to escaped memory and that solution
6696 is not empty they alias. */
6697 if (pt1->ipa_escaped && pt2->ipa_escaped)
6698 return true;
6699
6700 /* If either points to escaped memory see if the escaped solution
6701 intersects with the other. */
6702 if ((pt1->ipa_escaped
6703 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
6704 || (pt2->ipa_escaped
6705 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
6706 return true;
6707 }
6708
6709 /* Now both pointers alias if their points-to solution intersects. */
6710 return (pt1->vars
6711 && pt2->vars
6712 && bitmap_intersect_p (pt1->vars, pt2->vars));
6713 }
6714
6715 bool
pt_solutions_intersect(struct pt_solution * pt1,struct pt_solution * pt2)6716 pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
6717 {
6718 bool res = pt_solutions_intersect_1 (pt1, pt2);
6719 if (res)
6720 ++pta_stats.pt_solutions_intersect_may_alias;
6721 else
6722 ++pta_stats.pt_solutions_intersect_no_alias;
6723 return res;
6724 }
6725
6726
6727 /* Dump points-to information to OUTFILE. */
6728
6729 static void
dump_sa_points_to_info(FILE * outfile)6730 dump_sa_points_to_info (FILE *outfile)
6731 {
6732 unsigned int i;
6733
6734 fprintf (outfile, "\nPoints-to sets\n\n");
6735
6736 if (dump_flags & TDF_STATS)
6737 {
6738 fprintf (outfile, "Stats:\n");
6739 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
6740 fprintf (outfile, "Non-pointer vars: %d\n",
6741 stats.nonpointer_vars);
6742 fprintf (outfile, "Statically unified vars: %d\n",
6743 stats.unified_vars_static);
6744 fprintf (outfile, "Dynamically unified vars: %d\n",
6745 stats.unified_vars_dynamic);
6746 fprintf (outfile, "Iterations: %d\n", stats.iterations);
6747 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
6748 fprintf (outfile, "Number of implicit edges: %d\n",
6749 stats.num_implicit_edges);
6750 }
6751
6752 for (i = 1; i < varmap.length (); i++)
6753 {
6754 varinfo_t vi = get_varinfo (i);
6755 if (!vi->may_have_pointers)
6756 continue;
6757 dump_solution_for_var (outfile, i);
6758 }
6759 }
6760
6761
6762 /* Debug points-to information to stderr. */
6763
6764 DEBUG_FUNCTION void
debug_sa_points_to_info(void)6765 debug_sa_points_to_info (void)
6766 {
6767 dump_sa_points_to_info (stderr);
6768 }
6769
6770
6771 /* Initialize the always-existing constraint variables for NULL
6772 ANYTHING, READONLY, and INTEGER */
6773
6774 static void
init_base_vars(void)6775 init_base_vars (void)
6776 {
6777 struct constraint_expr lhs, rhs;
6778 varinfo_t var_anything;
6779 varinfo_t var_nothing;
6780 varinfo_t var_string;
6781 varinfo_t var_escaped;
6782 varinfo_t var_nonlocal;
6783 varinfo_t var_storedanything;
6784 varinfo_t var_integer;
6785
6786 /* Variable ID zero is reserved and should be NULL. */
6787 varmap.safe_push (NULL);
6788
6789 /* Create the NULL variable, used to represent that a variable points
6790 to NULL. */
6791 var_nothing = new_var_info (NULL_TREE, "NULL", false);
6792 gcc_assert (var_nothing->id == nothing_id);
6793 var_nothing->is_artificial_var = 1;
6794 var_nothing->offset = 0;
6795 var_nothing->size = ~0;
6796 var_nothing->fullsize = ~0;
6797 var_nothing->is_special_var = 1;
6798 var_nothing->may_have_pointers = 0;
6799 var_nothing->is_global_var = 0;
6800
6801 /* Create the ANYTHING variable, used to represent that a variable
6802 points to some unknown piece of memory. */
6803 var_anything = new_var_info (NULL_TREE, "ANYTHING", false);
6804 gcc_assert (var_anything->id == anything_id);
6805 var_anything->is_artificial_var = 1;
6806 var_anything->size = ~0;
6807 var_anything->offset = 0;
6808 var_anything->fullsize = ~0;
6809 var_anything->is_special_var = 1;
6810
6811 /* Anything points to anything. This makes deref constraints just
6812 work in the presence of linked list and other p = *p type loops,
6813 by saying that *ANYTHING = ANYTHING. */
6814 lhs.type = SCALAR;
6815 lhs.var = anything_id;
6816 lhs.offset = 0;
6817 rhs.type = ADDRESSOF;
6818 rhs.var = anything_id;
6819 rhs.offset = 0;
6820
6821 /* This specifically does not use process_constraint because
6822 process_constraint ignores all anything = anything constraints, since all
6823 but this one are redundant. */
6824 constraints.safe_push (new_constraint (lhs, rhs));
6825
6826 /* Create the STRING variable, used to represent that a variable
6827 points to a string literal. String literals don't contain
6828 pointers so STRING doesn't point to anything. */
6829 var_string = new_var_info (NULL_TREE, "STRING", false);
6830 gcc_assert (var_string->id == string_id);
6831 var_string->is_artificial_var = 1;
6832 var_string->offset = 0;
6833 var_string->size = ~0;
6834 var_string->fullsize = ~0;
6835 var_string->is_special_var = 1;
6836 var_string->may_have_pointers = 0;
6837
6838 /* Create the ESCAPED variable, used to represent the set of escaped
6839 memory. */
6840 var_escaped = new_var_info (NULL_TREE, "ESCAPED", false);
6841 gcc_assert (var_escaped->id == escaped_id);
6842 var_escaped->is_artificial_var = 1;
6843 var_escaped->offset = 0;
6844 var_escaped->size = ~0;
6845 var_escaped->fullsize = ~0;
6846 var_escaped->is_special_var = 0;
6847
6848 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6849 memory. */
6850 var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL", false);
6851 gcc_assert (var_nonlocal->id == nonlocal_id);
6852 var_nonlocal->is_artificial_var = 1;
6853 var_nonlocal->offset = 0;
6854 var_nonlocal->size = ~0;
6855 var_nonlocal->fullsize = ~0;
6856 var_nonlocal->is_special_var = 1;
6857
6858 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6859 lhs.type = SCALAR;
6860 lhs.var = escaped_id;
6861 lhs.offset = 0;
6862 rhs.type = DEREF;
6863 rhs.var = escaped_id;
6864 rhs.offset = 0;
6865 process_constraint (new_constraint (lhs, rhs));
6866
6867 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6868 whole variable escapes. */
6869 lhs.type = SCALAR;
6870 lhs.var = escaped_id;
6871 lhs.offset = 0;
6872 rhs.type = SCALAR;
6873 rhs.var = escaped_id;
6874 rhs.offset = UNKNOWN_OFFSET;
6875 process_constraint (new_constraint (lhs, rhs));
6876
6877 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6878 everything pointed to by escaped points to what global memory can
6879 point to. */
6880 lhs.type = DEREF;
6881 lhs.var = escaped_id;
6882 lhs.offset = 0;
6883 rhs.type = SCALAR;
6884 rhs.var = nonlocal_id;
6885 rhs.offset = 0;
6886 process_constraint (new_constraint (lhs, rhs));
6887
6888 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6889 global memory may point to global memory and escaped memory. */
6890 lhs.type = SCALAR;
6891 lhs.var = nonlocal_id;
6892 lhs.offset = 0;
6893 rhs.type = ADDRESSOF;
6894 rhs.var = nonlocal_id;
6895 rhs.offset = 0;
6896 process_constraint (new_constraint (lhs, rhs));
6897 rhs.type = ADDRESSOF;
6898 rhs.var = escaped_id;
6899 rhs.offset = 0;
6900 process_constraint (new_constraint (lhs, rhs));
6901
6902 /* Create the STOREDANYTHING variable, used to represent the set of
6903 variables stored to *ANYTHING. */
6904 var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING", false);
6905 gcc_assert (var_storedanything->id == storedanything_id);
6906 var_storedanything->is_artificial_var = 1;
6907 var_storedanything->offset = 0;
6908 var_storedanything->size = ~0;
6909 var_storedanything->fullsize = ~0;
6910 var_storedanything->is_special_var = 0;
6911
6912 /* Create the INTEGER variable, used to represent that a variable points
6913 to what an INTEGER "points to". */
6914 var_integer = new_var_info (NULL_TREE, "INTEGER", false);
6915 gcc_assert (var_integer->id == integer_id);
6916 var_integer->is_artificial_var = 1;
6917 var_integer->size = ~0;
6918 var_integer->fullsize = ~0;
6919 var_integer->offset = 0;
6920 var_integer->is_special_var = 1;
6921
6922 /* INTEGER = ANYTHING, because we don't know where a dereference of
6923 a random integer will point to. */
6924 lhs.type = SCALAR;
6925 lhs.var = integer_id;
6926 lhs.offset = 0;
6927 rhs.type = ADDRESSOF;
6928 rhs.var = anything_id;
6929 rhs.offset = 0;
6930 process_constraint (new_constraint (lhs, rhs));
6931 }
6932
6933 /* Initialize things necessary to perform PTA */
6934
6935 static void
init_alias_vars(void)6936 init_alias_vars (void)
6937 {
6938 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
6939
6940 bitmap_obstack_initialize (&pta_obstack);
6941 bitmap_obstack_initialize (&oldpta_obstack);
6942 bitmap_obstack_initialize (&predbitmap_obstack);
6943
6944 constraints.create (8);
6945 varmap.create (8);
6946 vi_for_tree = new hash_map<tree, varinfo_t>;
6947 call_stmt_vars = new hash_map<gimple *, varinfo_t>;
6948
6949 memset (&stats, 0, sizeof (stats));
6950 shared_bitmap_table = new hash_table<shared_bitmap_hasher> (511);
6951 init_base_vars ();
6952
6953 gcc_obstack_init (&fake_var_decl_obstack);
6954
6955 final_solutions = new hash_map<varinfo_t, pt_solution *>;
6956 gcc_obstack_init (&final_solutions_obstack);
6957 }
6958
6959 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
6960 predecessor edges. */
6961
6962 static void
remove_preds_and_fake_succs(constraint_graph_t graph)6963 remove_preds_and_fake_succs (constraint_graph_t graph)
6964 {
6965 unsigned int i;
6966
6967 /* Clear the implicit ref and address nodes from the successor
6968 lists. */
6969 for (i = 1; i < FIRST_REF_NODE; i++)
6970 {
6971 if (graph->succs[i])
6972 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
6973 FIRST_REF_NODE * 2);
6974 }
6975
6976 /* Free the successor list for the non-ref nodes. */
6977 for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
6978 {
6979 if (graph->succs[i])
6980 BITMAP_FREE (graph->succs[i]);
6981 }
6982
6983 /* Now reallocate the size of the successor list as, and blow away
6984 the predecessor bitmaps. */
6985 graph->size = varmap.length ();
6986 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
6987
6988 free (graph->implicit_preds);
6989 graph->implicit_preds = NULL;
6990 free (graph->preds);
6991 graph->preds = NULL;
6992 bitmap_obstack_release (&predbitmap_obstack);
6993 }
6994
6995 /* Solve the constraint set. */
6996
6997 static void
solve_constraints(void)6998 solve_constraints (void)
6999 {
7000 struct scc_info *si;
7001
7002 if (dump_file)
7003 fprintf (dump_file,
7004 "\nCollapsing static cycles and doing variable "
7005 "substitution\n");
7006
7007 init_graph (varmap.length () * 2);
7008
7009 if (dump_file)
7010 fprintf (dump_file, "Building predecessor graph\n");
7011 build_pred_graph ();
7012
7013 if (dump_file)
7014 fprintf (dump_file, "Detecting pointer and location "
7015 "equivalences\n");
7016 si = perform_var_substitution (graph);
7017
7018 if (dump_file)
7019 fprintf (dump_file, "Rewriting constraints and unifying "
7020 "variables\n");
7021 rewrite_constraints (graph, si);
7022
7023 build_succ_graph ();
7024
7025 free_var_substitution_info (si);
7026
7027 /* Attach complex constraints to graph nodes. */
7028 move_complex_constraints (graph);
7029
7030 if (dump_file)
7031 fprintf (dump_file, "Uniting pointer but not location equivalent "
7032 "variables\n");
7033 unite_pointer_equivalences (graph);
7034
7035 if (dump_file)
7036 fprintf (dump_file, "Finding indirect cycles\n");
7037 find_indirect_cycles (graph);
7038
7039 /* Implicit nodes and predecessors are no longer necessary at this
7040 point. */
7041 remove_preds_and_fake_succs (graph);
7042
7043 if (dump_file && (dump_flags & TDF_GRAPH))
7044 {
7045 fprintf (dump_file, "\n\n// The constraint graph before solve-graph "
7046 "in dot format:\n");
7047 dump_constraint_graph (dump_file);
7048 fprintf (dump_file, "\n\n");
7049 }
7050
7051 if (dump_file)
7052 fprintf (dump_file, "Solving graph\n");
7053
7054 solve_graph (graph);
7055
7056 if (dump_file && (dump_flags & TDF_GRAPH))
7057 {
7058 fprintf (dump_file, "\n\n// The constraint graph after solve-graph "
7059 "in dot format:\n");
7060 dump_constraint_graph (dump_file);
7061 fprintf (dump_file, "\n\n");
7062 }
7063
7064 if (dump_file)
7065 dump_sa_points_to_info (dump_file);
7066 }
7067
7068 /* Create points-to sets for the current function. See the comments
7069 at the start of the file for an algorithmic overview. */
7070
7071 static void
compute_points_to_sets(void)7072 compute_points_to_sets (void)
7073 {
7074 basic_block bb;
7075 unsigned i;
7076 varinfo_t vi;
7077
7078 timevar_push (TV_TREE_PTA);
7079
7080 init_alias_vars ();
7081
7082 intra_create_variable_infos (cfun);
7083
7084 /* Now walk all statements and build the constraint set. */
7085 FOR_EACH_BB_FN (bb, cfun)
7086 {
7087 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
7088 gsi_next (&gsi))
7089 {
7090 gphi *phi = gsi.phi ();
7091
7092 if (! virtual_operand_p (gimple_phi_result (phi)))
7093 find_func_aliases (cfun, phi);
7094 }
7095
7096 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
7097 gsi_next (&gsi))
7098 {
7099 gimple *stmt = gsi_stmt (gsi);
7100
7101 find_func_aliases (cfun, stmt);
7102 }
7103 }
7104
7105 if (dump_file)
7106 {
7107 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
7108 dump_constraints (dump_file, 0);
7109 }
7110
7111 /* From the constraints compute the points-to sets. */
7112 solve_constraints ();
7113
7114 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
7115 cfun->gimple_df->escaped = find_what_var_points_to (cfun->decl,
7116 get_varinfo (escaped_id));
7117
7118 /* Make sure the ESCAPED solution (which is used as placeholder in
7119 other solutions) does not reference itself. This simplifies
7120 points-to solution queries. */
7121 cfun->gimple_df->escaped.escaped = 0;
7122
7123 /* Compute the points-to sets for pointer SSA_NAMEs. */
7124 for (i = 0; i < num_ssa_names; ++i)
7125 {
7126 tree ptr = ssa_name (i);
7127 if (ptr
7128 && POINTER_TYPE_P (TREE_TYPE (ptr)))
7129 find_what_p_points_to (cfun->decl, ptr);
7130 }
7131
7132 /* Compute the call-used/clobbered sets. */
7133 FOR_EACH_BB_FN (bb, cfun)
7134 {
7135 gimple_stmt_iterator gsi;
7136
7137 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
7138 {
7139 gcall *stmt;
7140 struct pt_solution *pt;
7141
7142 stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
7143 if (!stmt)
7144 continue;
7145
7146 pt = gimple_call_use_set (stmt);
7147 if (gimple_call_flags (stmt) & ECF_CONST)
7148 memset (pt, 0, sizeof (struct pt_solution));
7149 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
7150 {
7151 *pt = find_what_var_points_to (cfun->decl, vi);
7152 /* Escaped (and thus nonlocal) variables are always
7153 implicitly used by calls. */
7154 /* ??? ESCAPED can be empty even though NONLOCAL
7155 always escaped. */
7156 pt->nonlocal = 1;
7157 pt->escaped = 1;
7158 }
7159 else
7160 {
7161 /* If there is nothing special about this call then
7162 we have made everything that is used also escape. */
7163 *pt = cfun->gimple_df->escaped;
7164 pt->nonlocal = 1;
7165 }
7166
7167 pt = gimple_call_clobber_set (stmt);
7168 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
7169 memset (pt, 0, sizeof (struct pt_solution));
7170 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
7171 {
7172 *pt = find_what_var_points_to (cfun->decl, vi);
7173 /* Escaped (and thus nonlocal) variables are always
7174 implicitly clobbered by calls. */
7175 /* ??? ESCAPED can be empty even though NONLOCAL
7176 always escaped. */
7177 pt->nonlocal = 1;
7178 pt->escaped = 1;
7179 }
7180 else
7181 {
7182 /* If there is nothing special about this call then
7183 we have made everything that is used also escape. */
7184 *pt = cfun->gimple_df->escaped;
7185 pt->nonlocal = 1;
7186 }
7187 }
7188 }
7189
7190 timevar_pop (TV_TREE_PTA);
7191 }
7192
7193
7194 /* Delete created points-to sets. */
7195
7196 static void
delete_points_to_sets(void)7197 delete_points_to_sets (void)
7198 {
7199 unsigned int i;
7200
7201 delete shared_bitmap_table;
7202 shared_bitmap_table = NULL;
7203 if (dump_file && (dump_flags & TDF_STATS))
7204 fprintf (dump_file, "Points to sets created:%d\n",
7205 stats.points_to_sets_created);
7206
7207 delete vi_for_tree;
7208 delete call_stmt_vars;
7209 bitmap_obstack_release (&pta_obstack);
7210 constraints.release ();
7211
7212 for (i = 0; i < graph->size; i++)
7213 graph->complex[i].release ();
7214 free (graph->complex);
7215
7216 free (graph->rep);
7217 free (graph->succs);
7218 free (graph->pe);
7219 free (graph->pe_rep);
7220 free (graph->indirect_cycles);
7221 free (graph);
7222
7223 varmap.release ();
7224 variable_info_pool.release ();
7225 constraint_pool.release ();
7226
7227 obstack_free (&fake_var_decl_obstack, NULL);
7228
7229 delete final_solutions;
7230 obstack_free (&final_solutions_obstack, NULL);
7231 }
7232
7233 struct vls_data
7234 {
7235 unsigned short clique;
7236 bitmap rvars;
7237 };
7238
7239 /* Mark "other" loads and stores as belonging to CLIQUE and with
7240 base zero. */
7241
7242 static bool
visit_loadstore(gimple *,tree base,tree ref,void * data)7243 visit_loadstore (gimple *, tree base, tree ref, void *data)
7244 {
7245 unsigned short clique = ((vls_data *) data)->clique;
7246 bitmap rvars = ((vls_data *) data)->rvars;
7247 if (TREE_CODE (base) == MEM_REF
7248 || TREE_CODE (base) == TARGET_MEM_REF)
7249 {
7250 tree ptr = TREE_OPERAND (base, 0);
7251 if (TREE_CODE (ptr) == SSA_NAME)
7252 {
7253 /* For parameters, get at the points-to set for the actual parm
7254 decl. */
7255 if (SSA_NAME_IS_DEFAULT_DEF (ptr)
7256 && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
7257 || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
7258 ptr = SSA_NAME_VAR (ptr);
7259
7260 /* We need to make sure 'ptr' doesn't include any of
7261 the restrict tags we added bases for in its points-to set. */
7262 varinfo_t vi = lookup_vi_for_tree (ptr);
7263 if (! vi)
7264 return false;
7265
7266 vi = get_varinfo (find (vi->id));
7267 if (bitmap_intersect_p (rvars, vi->solution))
7268 return false;
7269 }
7270
7271 /* Do not overwrite existing cliques (that includes clique, base
7272 pairs we just set). */
7273 if (MR_DEPENDENCE_CLIQUE (base) == 0)
7274 {
7275 MR_DEPENDENCE_CLIQUE (base) = clique;
7276 MR_DEPENDENCE_BASE (base) = 0;
7277 }
7278 }
7279
7280 /* For plain decl accesses see whether they are accesses to globals
7281 and rewrite them to MEM_REFs with { clique, 0 }. */
7282 if (TREE_CODE (base) == VAR_DECL
7283 && is_global_var (base)
7284 /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
7285 ops callback. */
7286 && base != ref)
7287 {
7288 tree *basep = &ref;
7289 while (handled_component_p (*basep))
7290 basep = &TREE_OPERAND (*basep, 0);
7291 gcc_assert (TREE_CODE (*basep) == VAR_DECL);
7292 tree ptr = build_fold_addr_expr (*basep);
7293 tree zero = build_int_cst (TREE_TYPE (ptr), 0);
7294 *basep = build2 (MEM_REF, TREE_TYPE (*basep), ptr, zero);
7295 MR_DEPENDENCE_CLIQUE (*basep) = clique;
7296 MR_DEPENDENCE_BASE (*basep) = 0;
7297 }
7298
7299 return false;
7300 }
7301
7302 /* If REF is a MEM_REF then assign a clique, base pair to it, updating
7303 CLIQUE, *RESTRICT_VAR and LAST_RUID. Return whether dependence info
7304 was assigned to REF. */
7305
7306 static bool
maybe_set_dependence_info(tree ref,tree ptr,unsigned short & clique,varinfo_t restrict_var,unsigned short & last_ruid)7307 maybe_set_dependence_info (tree ref, tree ptr,
7308 unsigned short &clique, varinfo_t restrict_var,
7309 unsigned short &last_ruid)
7310 {
7311 while (handled_component_p (ref))
7312 ref = TREE_OPERAND (ref, 0);
7313 if ((TREE_CODE (ref) == MEM_REF
7314 || TREE_CODE (ref) == TARGET_MEM_REF)
7315 && TREE_OPERAND (ref, 0) == ptr)
7316 {
7317 /* Do not overwrite existing cliques. This avoids overwriting dependence
7318 info inlined from a function with restrict parameters inlined
7319 into a function with restrict parameters. This usually means we
7320 prefer to be precise in innermost loops. */
7321 if (MR_DEPENDENCE_CLIQUE (ref) == 0)
7322 {
7323 if (clique == 0)
7324 clique = ++cfun->last_clique;
7325 if (restrict_var->ruid == 0)
7326 restrict_var->ruid = ++last_ruid;
7327 MR_DEPENDENCE_CLIQUE (ref) = clique;
7328 MR_DEPENDENCE_BASE (ref) = restrict_var->ruid;
7329 return true;
7330 }
7331 }
7332 return false;
7333 }
7334
7335 /* Compute the set of independend memory references based on restrict
7336 tags and their conservative propagation to the points-to sets. */
7337
7338 static void
compute_dependence_clique(void)7339 compute_dependence_clique (void)
7340 {
7341 unsigned short clique = 0;
7342 unsigned short last_ruid = 0;
7343 bitmap rvars = BITMAP_ALLOC (NULL);
7344 for (unsigned i = 0; i < num_ssa_names; ++i)
7345 {
7346 tree ptr = ssa_name (i);
7347 if (!ptr || !POINTER_TYPE_P (TREE_TYPE (ptr)))
7348 continue;
7349
7350 /* Avoid all this when ptr is not dereferenced? */
7351 tree p = ptr;
7352 if (SSA_NAME_IS_DEFAULT_DEF (ptr)
7353 && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
7354 || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
7355 p = SSA_NAME_VAR (ptr);
7356 varinfo_t vi = lookup_vi_for_tree (p);
7357 if (!vi)
7358 continue;
7359 vi = get_varinfo (find (vi->id));
7360 bitmap_iterator bi;
7361 unsigned j;
7362 varinfo_t restrict_var = NULL;
7363 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
7364 {
7365 varinfo_t oi = get_varinfo (j);
7366 if (oi->is_restrict_var)
7367 {
7368 if (restrict_var)
7369 {
7370 if (dump_file && (dump_flags & TDF_DETAILS))
7371 {
7372 fprintf (dump_file, "found restrict pointed-to "
7373 "for ");
7374 print_generic_expr (dump_file, ptr, 0);
7375 fprintf (dump_file, " but not exclusively\n");
7376 }
7377 restrict_var = NULL;
7378 break;
7379 }
7380 restrict_var = oi;
7381 }
7382 /* NULL is the only other valid points-to entry. */
7383 else if (oi->id != nothing_id)
7384 {
7385 restrict_var = NULL;
7386 break;
7387 }
7388 }
7389 /* Ok, found that ptr must(!) point to a single(!) restrict
7390 variable. */
7391 /* ??? PTA isn't really a proper propagation engine to compute
7392 this property.
7393 ??? We could handle merging of two restricts by unifying them. */
7394 if (restrict_var)
7395 {
7396 /* Now look at possible dereferences of ptr. */
7397 imm_use_iterator ui;
7398 gimple *use_stmt;
7399 bool used = false;
7400 FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
7401 {
7402 /* ??? Calls and asms. */
7403 if (!gimple_assign_single_p (use_stmt))
7404 continue;
7405 used |= maybe_set_dependence_info (gimple_assign_lhs (use_stmt),
7406 ptr, clique, restrict_var,
7407 last_ruid);
7408 used |= maybe_set_dependence_info (gimple_assign_rhs1 (use_stmt),
7409 ptr, clique, restrict_var,
7410 last_ruid);
7411 }
7412 if (used)
7413 bitmap_set_bit (rvars, restrict_var->id);
7414 }
7415 }
7416
7417 if (clique != 0)
7418 {
7419 /* Assign the BASE id zero to all accesses not based on a restrict
7420 pointer. That way they get disambiguated against restrict
7421 accesses but not against each other. */
7422 /* ??? For restricts derived from globals (thus not incoming
7423 parameters) we can't restrict scoping properly thus the following
7424 is too aggressive there. For now we have excluded those globals from
7425 getting into the MR_DEPENDENCE machinery. */
7426 vls_data data = { clique, rvars };
7427 basic_block bb;
7428 FOR_EACH_BB_FN (bb, cfun)
7429 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
7430 !gsi_end_p (gsi); gsi_next (&gsi))
7431 {
7432 gimple *stmt = gsi_stmt (gsi);
7433 walk_stmt_load_store_ops (stmt, &data,
7434 visit_loadstore, visit_loadstore);
7435 }
7436 }
7437
7438 BITMAP_FREE (rvars);
7439 }
7440
7441 /* Compute points-to information for every SSA_NAME pointer in the
7442 current function and compute the transitive closure of escaped
7443 variables to re-initialize the call-clobber states of local variables. */
7444
7445 unsigned int
compute_may_aliases(void)7446 compute_may_aliases (void)
7447 {
7448 if (cfun->gimple_df->ipa_pta)
7449 {
7450 if (dump_file)
7451 {
7452 fprintf (dump_file, "\nNot re-computing points-to information "
7453 "because IPA points-to information is available.\n\n");
7454
7455 /* But still dump what we have remaining it. */
7456 dump_alias_info (dump_file);
7457 }
7458
7459 return 0;
7460 }
7461
7462 /* For each pointer P_i, determine the sets of variables that P_i may
7463 point-to. Compute the reachability set of escaped and call-used
7464 variables. */
7465 compute_points_to_sets ();
7466
7467 /* Debugging dumps. */
7468 if (dump_file)
7469 dump_alias_info (dump_file);
7470
7471 /* Compute restrict-based memory disambiguations. */
7472 compute_dependence_clique ();
7473
7474 /* Deallocate memory used by aliasing data structures and the internal
7475 points-to solution. */
7476 delete_points_to_sets ();
7477
7478 gcc_assert (!need_ssa_update_p (cfun));
7479
7480 return 0;
7481 }
7482
7483 /* A dummy pass to cause points-to information to be computed via
7484 TODO_rebuild_alias. */
7485
7486 namespace {
7487
7488 const pass_data pass_data_build_alias =
7489 {
7490 GIMPLE_PASS, /* type */
7491 "alias", /* name */
7492 OPTGROUP_NONE, /* optinfo_flags */
7493 TV_NONE, /* tv_id */
7494 ( PROP_cfg | PROP_ssa ), /* properties_required */
7495 0, /* properties_provided */
7496 0, /* properties_destroyed */
7497 0, /* todo_flags_start */
7498 TODO_rebuild_alias, /* todo_flags_finish */
7499 };
7500
7501 class pass_build_alias : public gimple_opt_pass
7502 {
7503 public:
pass_build_alias(gcc::context * ctxt)7504 pass_build_alias (gcc::context *ctxt)
7505 : gimple_opt_pass (pass_data_build_alias, ctxt)
7506 {}
7507
7508 /* opt_pass methods: */
gate(function *)7509 virtual bool gate (function *) { return flag_tree_pta; }
7510
7511 }; // class pass_build_alias
7512
7513 } // anon namespace
7514
7515 gimple_opt_pass *
make_pass_build_alias(gcc::context * ctxt)7516 make_pass_build_alias (gcc::context *ctxt)
7517 {
7518 return new pass_build_alias (ctxt);
7519 }
7520
7521 /* A dummy pass to cause points-to information to be computed via
7522 TODO_rebuild_alias. */
7523
7524 namespace {
7525
7526 const pass_data pass_data_build_ealias =
7527 {
7528 GIMPLE_PASS, /* type */
7529 "ealias", /* name */
7530 OPTGROUP_NONE, /* optinfo_flags */
7531 TV_NONE, /* tv_id */
7532 ( PROP_cfg | PROP_ssa ), /* properties_required */
7533 0, /* properties_provided */
7534 0, /* properties_destroyed */
7535 0, /* todo_flags_start */
7536 TODO_rebuild_alias, /* todo_flags_finish */
7537 };
7538
7539 class pass_build_ealias : public gimple_opt_pass
7540 {
7541 public:
pass_build_ealias(gcc::context * ctxt)7542 pass_build_ealias (gcc::context *ctxt)
7543 : gimple_opt_pass (pass_data_build_ealias, ctxt)
7544 {}
7545
7546 /* opt_pass methods: */
gate(function *)7547 virtual bool gate (function *) { return flag_tree_pta; }
7548
7549 }; // class pass_build_ealias
7550
7551 } // anon namespace
7552
7553 gimple_opt_pass *
make_pass_build_ealias(gcc::context * ctxt)7554 make_pass_build_ealias (gcc::context *ctxt)
7555 {
7556 return new pass_build_ealias (ctxt);
7557 }
7558
7559
7560 /* IPA PTA solutions for ESCAPED. */
7561 struct pt_solution ipa_escaped_pt
7562 = { true, false, false, false, false, false, false, false, NULL };
7563
7564 /* Associate node with varinfo DATA. Worker for
7565 cgraph_for_symbol_thunks_and_aliases. */
7566 static bool
associate_varinfo_to_alias(struct cgraph_node * node,void * data)7567 associate_varinfo_to_alias (struct cgraph_node *node, void *data)
7568 {
7569 if ((node->alias || node->thunk.thunk_p)
7570 && node->analyzed)
7571 insert_vi_for_tree (node->decl, (varinfo_t)data);
7572 return false;
7573 }
7574
7575 /* Compute whether node is refered to non-locally. Worker for
7576 cgraph_for_symbol_thunks_and_aliases. */
7577 static bool
refered_from_nonlocal_fn(struct cgraph_node * node,void * data)7578 refered_from_nonlocal_fn (struct cgraph_node *node, void *data)
7579 {
7580 bool *nonlocal_p = (bool *)data;
7581 *nonlocal_p |= (node->used_from_other_partition
7582 || node->externally_visible
7583 || node->force_output);
7584 return false;
7585 }
7586
7587 /* Same for varpool nodes. */
7588 static bool
refered_from_nonlocal_var(struct varpool_node * node,void * data)7589 refered_from_nonlocal_var (struct varpool_node *node, void *data)
7590 {
7591 bool *nonlocal_p = (bool *)data;
7592 *nonlocal_p |= (node->used_from_other_partition
7593 || node->externally_visible
7594 || node->force_output);
7595 return false;
7596 }
7597
7598 /* Execute the driver for IPA PTA. */
7599 static unsigned int
ipa_pta_execute(void)7600 ipa_pta_execute (void)
7601 {
7602 struct cgraph_node *node;
7603 varpool_node *var;
7604 unsigned int from = 0;
7605
7606 in_ipa_mode = 1;
7607
7608 init_alias_vars ();
7609
7610 if (dump_file && (dump_flags & TDF_DETAILS))
7611 {
7612 symtab_node::dump_table (dump_file);
7613 fprintf (dump_file, "\n");
7614 }
7615
7616 if (dump_file)
7617 {
7618 fprintf (dump_file, "Generating generic constraints\n\n");
7619 dump_constraints (dump_file, from);
7620 fprintf (dump_file, "\n");
7621 from = constraints.length ();
7622 }
7623
7624 /* Build the constraints. */
7625 FOR_EACH_DEFINED_FUNCTION (node)
7626 {
7627 varinfo_t vi;
7628 /* Nodes without a body are not interesting. Especially do not
7629 visit clones at this point for now - we get duplicate decls
7630 there for inline clones at least. */
7631 if (!node->has_gimple_body_p () || node->global.inlined_to)
7632 continue;
7633 node->get_body ();
7634
7635 gcc_assert (!node->clone_of);
7636
7637 /* When parallelizing a code region, we split the region off into a
7638 separate function, to be run by several threads in parallel. So for a
7639 function foo, we split off a region into a function
7640 foo._0 (void *foodata), and replace the region with some variant of a
7641 function call run_on_threads (&foo._0, data). The '&foo._0' sets the
7642 address_taken bit for function foo._0, which would make it non-local.
7643 But for the purpose of ipa-pta, we can regard the run_on_threads call
7644 as a local call foo._0 (data), so we ignore address_taken on nodes
7645 with parallelized_function set.
7646 Note: this is only safe, if foo and foo._0 are in the same lto
7647 partition. */
7648 bool node_address_taken = ((node->parallelized_function
7649 && !node->used_from_other_partition)
7650 ? false
7651 : node->address_taken);
7652
7653 /* For externally visible or attribute used annotated functions use
7654 local constraints for their arguments.
7655 For local functions we see all callers and thus do not need initial
7656 constraints for parameters. */
7657 bool nonlocal_p = (node->used_from_other_partition
7658 || node->externally_visible
7659 || node->force_output
7660 || node_address_taken);
7661 node->call_for_symbol_thunks_and_aliases (refered_from_nonlocal_fn,
7662 &nonlocal_p, true);
7663
7664 vi = create_function_info_for (node->decl,
7665 alias_get_name (node->decl), false,
7666 nonlocal_p);
7667 if (dump_file
7668 && from != constraints.length ())
7669 {
7670 fprintf (dump_file,
7671 "Generating intial constraints for %s", node->name ());
7672 if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
7673 fprintf (dump_file, " (%s)",
7674 IDENTIFIER_POINTER
7675 (DECL_ASSEMBLER_NAME (node->decl)));
7676 fprintf (dump_file, "\n\n");
7677 dump_constraints (dump_file, from);
7678 fprintf (dump_file, "\n");
7679
7680 from = constraints.length ();
7681 }
7682
7683 node->call_for_symbol_thunks_and_aliases
7684 (associate_varinfo_to_alias, vi, true);
7685 }
7686
7687 /* Create constraints for global variables and their initializers. */
7688 FOR_EACH_VARIABLE (var)
7689 {
7690 if (var->alias && var->analyzed)
7691 continue;
7692
7693 varinfo_t vi = get_vi_for_tree (var->decl);
7694
7695 /* For the purpose of IPA PTA unit-local globals are not
7696 escape points. */
7697 bool nonlocal_p = (var->used_from_other_partition
7698 || var->externally_visible
7699 || var->force_output);
7700 var->call_for_symbol_and_aliases (refered_from_nonlocal_var,
7701 &nonlocal_p, true);
7702 if (nonlocal_p)
7703 vi->is_ipa_escape_point = true;
7704 }
7705
7706 if (dump_file
7707 && from != constraints.length ())
7708 {
7709 fprintf (dump_file,
7710 "Generating constraints for global initializers\n\n");
7711 dump_constraints (dump_file, from);
7712 fprintf (dump_file, "\n");
7713 from = constraints.length ();
7714 }
7715
7716 FOR_EACH_DEFINED_FUNCTION (node)
7717 {
7718 struct function *func;
7719 basic_block bb;
7720
7721 /* Nodes without a body are not interesting. */
7722 if (!node->has_gimple_body_p () || node->clone_of)
7723 continue;
7724
7725 if (dump_file)
7726 {
7727 fprintf (dump_file,
7728 "Generating constraints for %s", node->name ());
7729 if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
7730 fprintf (dump_file, " (%s)",
7731 IDENTIFIER_POINTER
7732 (DECL_ASSEMBLER_NAME (node->decl)));
7733 fprintf (dump_file, "\n");
7734 }
7735
7736 func = DECL_STRUCT_FUNCTION (node->decl);
7737 gcc_assert (cfun == NULL);
7738
7739 /* Build constriants for the function body. */
7740 FOR_EACH_BB_FN (bb, func)
7741 {
7742 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
7743 gsi_next (&gsi))
7744 {
7745 gphi *phi = gsi.phi ();
7746
7747 if (! virtual_operand_p (gimple_phi_result (phi)))
7748 find_func_aliases (func, phi);
7749 }
7750
7751 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
7752 gsi_next (&gsi))
7753 {
7754 gimple *stmt = gsi_stmt (gsi);
7755
7756 find_func_aliases (func, stmt);
7757 find_func_clobbers (func, stmt);
7758 }
7759 }
7760
7761 if (dump_file)
7762 {
7763 fprintf (dump_file, "\n");
7764 dump_constraints (dump_file, from);
7765 fprintf (dump_file, "\n");
7766 from = constraints.length ();
7767 }
7768 }
7769
7770 /* From the constraints compute the points-to sets. */
7771 solve_constraints ();
7772
7773 /* Compute the global points-to sets for ESCAPED.
7774 ??? Note that the computed escape set is not correct
7775 for the whole unit as we fail to consider graph edges to
7776 externally visible functions. */
7777 ipa_escaped_pt = find_what_var_points_to (NULL, get_varinfo (escaped_id));
7778
7779 /* Make sure the ESCAPED solution (which is used as placeholder in
7780 other solutions) does not reference itself. This simplifies
7781 points-to solution queries. */
7782 ipa_escaped_pt.ipa_escaped = 0;
7783
7784 /* Assign the points-to sets to the SSA names in the unit. */
7785 FOR_EACH_DEFINED_FUNCTION (node)
7786 {
7787 tree ptr;
7788 struct function *fn;
7789 unsigned i;
7790 basic_block bb;
7791
7792 /* Nodes without a body are not interesting. */
7793 if (!node->has_gimple_body_p () || node->clone_of)
7794 continue;
7795
7796 fn = DECL_STRUCT_FUNCTION (node->decl);
7797
7798 /* Compute the points-to sets for pointer SSA_NAMEs. */
7799 FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr)
7800 {
7801 if (ptr
7802 && POINTER_TYPE_P (TREE_TYPE (ptr)))
7803 find_what_p_points_to (node->decl, ptr);
7804 }
7805
7806 /* Compute the call-use and call-clobber sets for indirect calls
7807 and calls to external functions. */
7808 FOR_EACH_BB_FN (bb, fn)
7809 {
7810 gimple_stmt_iterator gsi;
7811
7812 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
7813 {
7814 gcall *stmt;
7815 struct pt_solution *pt;
7816 varinfo_t vi, fi;
7817 tree decl;
7818
7819 stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
7820 if (!stmt)
7821 continue;
7822
7823 /* Handle direct calls to functions with body. */
7824 decl = gimple_call_fndecl (stmt);
7825
7826 {
7827 tree called_decl = NULL_TREE;
7828 if (gimple_call_builtin_p (stmt, BUILT_IN_GOMP_PARALLEL))
7829 called_decl = TREE_OPERAND (gimple_call_arg (stmt, 0), 0);
7830 else if (gimple_call_builtin_p (stmt, BUILT_IN_GOACC_PARALLEL))
7831 called_decl = TREE_OPERAND (gimple_call_arg (stmt, 1), 0);
7832
7833 if (called_decl != NULL_TREE
7834 && !fndecl_maybe_in_other_partition (called_decl))
7835 decl = called_decl;
7836 }
7837
7838 if (decl
7839 && (fi = lookup_vi_for_tree (decl))
7840 && fi->is_fn_info)
7841 {
7842 *gimple_call_clobber_set (stmt)
7843 = find_what_var_points_to
7844 (node->decl, first_vi_for_offset (fi, fi_clobbers));
7845 *gimple_call_use_set (stmt)
7846 = find_what_var_points_to
7847 (node->decl, first_vi_for_offset (fi, fi_uses));
7848 }
7849 /* Handle direct calls to external functions. */
7850 else if (decl)
7851 {
7852 pt = gimple_call_use_set (stmt);
7853 if (gimple_call_flags (stmt) & ECF_CONST)
7854 memset (pt, 0, sizeof (struct pt_solution));
7855 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
7856 {
7857 *pt = find_what_var_points_to (node->decl, vi);
7858 /* Escaped (and thus nonlocal) variables are always
7859 implicitly used by calls. */
7860 /* ??? ESCAPED can be empty even though NONLOCAL
7861 always escaped. */
7862 pt->nonlocal = 1;
7863 pt->ipa_escaped = 1;
7864 }
7865 else
7866 {
7867 /* If there is nothing special about this call then
7868 we have made everything that is used also escape. */
7869 *pt = ipa_escaped_pt;
7870 pt->nonlocal = 1;
7871 }
7872
7873 pt = gimple_call_clobber_set (stmt);
7874 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
7875 memset (pt, 0, sizeof (struct pt_solution));
7876 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
7877 {
7878 *pt = find_what_var_points_to (node->decl, vi);
7879 /* Escaped (and thus nonlocal) variables are always
7880 implicitly clobbered by calls. */
7881 /* ??? ESCAPED can be empty even though NONLOCAL
7882 always escaped. */
7883 pt->nonlocal = 1;
7884 pt->ipa_escaped = 1;
7885 }
7886 else
7887 {
7888 /* If there is nothing special about this call then
7889 we have made everything that is used also escape. */
7890 *pt = ipa_escaped_pt;
7891 pt->nonlocal = 1;
7892 }
7893 }
7894 /* Handle indirect calls. */
7895 else if (!decl
7896 && (fi = get_fi_for_callee (stmt)))
7897 {
7898 /* We need to accumulate all clobbers/uses of all possible
7899 callees. */
7900 fi = get_varinfo (find (fi->id));
7901 /* If we cannot constrain the set of functions we'll end up
7902 calling we end up using/clobbering everything. */
7903 if (bitmap_bit_p (fi->solution, anything_id)
7904 || bitmap_bit_p (fi->solution, nonlocal_id)
7905 || bitmap_bit_p (fi->solution, escaped_id))
7906 {
7907 pt_solution_reset (gimple_call_clobber_set (stmt));
7908 pt_solution_reset (gimple_call_use_set (stmt));
7909 }
7910 else
7911 {
7912 bitmap_iterator bi;
7913 unsigned i;
7914 struct pt_solution *uses, *clobbers;
7915
7916 uses = gimple_call_use_set (stmt);
7917 clobbers = gimple_call_clobber_set (stmt);
7918 memset (uses, 0, sizeof (struct pt_solution));
7919 memset (clobbers, 0, sizeof (struct pt_solution));
7920 EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi)
7921 {
7922 struct pt_solution sol;
7923
7924 vi = get_varinfo (i);
7925 if (!vi->is_fn_info)
7926 {
7927 /* ??? We could be more precise here? */
7928 uses->nonlocal = 1;
7929 uses->ipa_escaped = 1;
7930 clobbers->nonlocal = 1;
7931 clobbers->ipa_escaped = 1;
7932 continue;
7933 }
7934
7935 if (!uses->anything)
7936 {
7937 sol = find_what_var_points_to
7938 (node->decl,
7939 first_vi_for_offset (vi, fi_uses));
7940 pt_solution_ior_into (uses, &sol);
7941 }
7942 if (!clobbers->anything)
7943 {
7944 sol = find_what_var_points_to
7945 (node->decl,
7946 first_vi_for_offset (vi, fi_clobbers));
7947 pt_solution_ior_into (clobbers, &sol);
7948 }
7949 }
7950 }
7951 }
7952 }
7953 }
7954
7955 fn->gimple_df->ipa_pta = true;
7956
7957 /* We have to re-set the final-solution cache after each function
7958 because what is a "global" is dependent on function context. */
7959 final_solutions->empty ();
7960 obstack_free (&final_solutions_obstack, NULL);
7961 gcc_obstack_init (&final_solutions_obstack);
7962 }
7963
7964 delete_points_to_sets ();
7965
7966 in_ipa_mode = 0;
7967
7968 return 0;
7969 }
7970
7971 namespace {
7972
7973 const pass_data pass_data_ipa_pta =
7974 {
7975 SIMPLE_IPA_PASS, /* type */
7976 "pta", /* name */
7977 OPTGROUP_NONE, /* optinfo_flags */
7978 TV_IPA_PTA, /* tv_id */
7979 0, /* properties_required */
7980 0, /* properties_provided */
7981 0, /* properties_destroyed */
7982 0, /* todo_flags_start */
7983 0, /* todo_flags_finish */
7984 };
7985
7986 class pass_ipa_pta : public simple_ipa_opt_pass
7987 {
7988 public:
pass_ipa_pta(gcc::context * ctxt)7989 pass_ipa_pta (gcc::context *ctxt)
7990 : simple_ipa_opt_pass (pass_data_ipa_pta, ctxt)
7991 {}
7992
7993 /* opt_pass methods: */
gate(function *)7994 virtual bool gate (function *)
7995 {
7996 return (optimize
7997 && flag_ipa_pta
7998 /* Don't bother doing anything if the program has errors. */
7999 && !seen_error ());
8000 }
8001
clone()8002 opt_pass * clone () { return new pass_ipa_pta (m_ctxt); }
8003
execute(function *)8004 virtual unsigned int execute (function *) { return ipa_pta_execute (); }
8005
8006 }; // class pass_ipa_pta
8007
8008 } // anon namespace
8009
8010 simple_ipa_opt_pass *
make_pass_ipa_pta(gcc::context * ctxt)8011 make_pass_ipa_pta (gcc::context *ctxt)
8012 {
8013 return new pass_ipa_pta (ctxt);
8014 }
8015