match_asm_constraints: Use copy_rtx where needed (PR88001)
[official-gcc.git] / gcc / tree-ssa-structalias.c
blobfc85e9ded5e83ed9ff9d5f277e868fc7252f960b
1 /* Tree based points-to analysis
2 Copyright (C) 2005-2018 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
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.
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.
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/>. */
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 #include "varasm.h"
43 #include "stringpool.h"
44 #include "attribs.h"
45 #include "tree-ssa.h"
47 /* The idea behind this analyzer is to generate set constraints from the
48 program, then solve the resulting constraints in order to generate the
49 points-to sets.
51 Set constraints are a way of modeling program analysis problems that
52 involve sets. They consist of an inclusion constraint language,
53 describing the variables (each variable is a set) and operations that
54 are involved on the variables, and a set of rules that derive facts
55 from these operations. To solve a system of set constraints, you derive
56 all possible facts under the rules, which gives you the correct sets
57 as a consequence.
59 See "Efficient Field-sensitive pointer analysis for C" by "David
60 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
61 http://citeseer.ist.psu.edu/pearce04efficient.html
63 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
64 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
65 http://citeseer.ist.psu.edu/heintze01ultrafast.html
67 There are three types of real constraint expressions, DEREF,
68 ADDRESSOF, and SCALAR. Each constraint expression consists
69 of a constraint type, a variable, and an offset.
71 SCALAR is a constraint expression type used to represent x, whether
72 it appears on the LHS or the RHS of a statement.
73 DEREF is a constraint expression type used to represent *x, whether
74 it appears on the LHS or the RHS of a statement.
75 ADDRESSOF is a constraint expression used to represent &x, whether
76 it appears on the LHS or the RHS of a statement.
78 Each pointer variable in the program is assigned an integer id, and
79 each field of a structure variable is assigned an integer id as well.
81 Structure variables are linked to their list of fields through a "next
82 field" in each variable that points to the next field in offset
83 order.
84 Each variable for a structure field has
86 1. "size", that tells the size in bits of that field.
87 2. "fullsize, that tells the size in bits of the entire structure.
88 3. "offset", that tells the offset in bits from the beginning of the
89 structure to this field.
91 Thus,
92 struct f
94 int a;
95 int b;
96 } foo;
97 int *bar;
99 looks like
101 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
102 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
103 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
106 In order to solve the system of set constraints, the following is
107 done:
109 1. Each constraint variable x has a solution set associated with it,
110 Sol(x).
112 2. Constraints are separated into direct, copy, and complex.
113 Direct constraints are ADDRESSOF constraints that require no extra
114 processing, such as P = &Q
115 Copy constraints are those of the form P = Q.
116 Complex constraints are all the constraints involving dereferences
117 and offsets (including offsetted copies).
119 3. All direct constraints of the form P = &Q are processed, such
120 that Q is added to Sol(P)
122 4. All complex constraints for a given constraint variable are stored in a
123 linked list attached to that variable's node.
125 5. A directed graph is built out of the copy constraints. Each
126 constraint variable is a node in the graph, and an edge from
127 Q to P is added for each copy constraint of the form P = Q
129 6. The graph is then walked, and solution sets are
130 propagated along the copy edges, such that an edge from Q to P
131 causes Sol(P) <- Sol(P) union Sol(Q).
133 7. As we visit each node, all complex constraints associated with
134 that node are processed by adding appropriate copy edges to the graph, or the
135 appropriate variables to the solution set.
137 8. The process of walking the graph is iterated until no solution
138 sets change.
140 Prior to walking the graph in steps 6 and 7, We perform static
141 cycle elimination on the constraint graph, as well
142 as off-line variable substitution.
144 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
145 on and turned into anything), but isn't. You can just see what offset
146 inside the pointed-to struct it's going to access.
148 TODO: Constant bounded arrays can be handled as if they were structs of the
149 same number of elements.
151 TODO: Modeling heap and incoming pointers becomes much better if we
152 add fields to them as we discover them, which we could do.
154 TODO: We could handle unions, but to be honest, it's probably not
155 worth the pain or slowdown. */
157 /* IPA-PTA optimizations possible.
159 When the indirect function called is ANYTHING we can add disambiguation
160 based on the function signatures (or simply the parameter count which
161 is the varinfo size). We also do not need to consider functions that
162 do not have their address taken.
164 The is_global_var bit which marks escape points is overly conservative
165 in IPA mode. Split it to is_escape_point and is_global_var - only
166 externally visible globals are escape points in IPA mode.
167 There is now is_ipa_escape_point but this is only used in a few
168 selected places.
170 The way we introduce DECL_PT_UID to avoid fixing up all points-to
171 sets in the translation unit when we copy a DECL during inlining
172 pessimizes precision. The advantage is that the DECL_PT_UID keeps
173 compile-time and memory usage overhead low - the points-to sets
174 do not grow or get unshared as they would during a fixup phase.
175 An alternative solution is to delay IPA PTA until after all
176 inlining transformations have been applied.
178 The way we propagate clobber/use information isn't optimized.
179 It should use a new complex constraint that properly filters
180 out local variables of the callee (though that would make
181 the sets invalid after inlining). OTOH we might as well
182 admit defeat to WHOPR and simply do all the clobber/use analysis
183 and propagation after PTA finished but before we threw away
184 points-to information for memory variables. WHOPR and PTA
185 do not play along well anyway - the whole constraint solving
186 would need to be done in WPA phase and it will be very interesting
187 to apply the results to local SSA names during LTRANS phase.
189 We probably should compute a per-function unit-ESCAPE solution
190 propagating it simply like the clobber / uses solutions. The
191 solution can go alongside the non-IPA espaced solution and be
192 used to query which vars escape the unit through a function.
193 This is also required to make the escaped-HEAP trick work in IPA mode.
195 We never put function decls in points-to sets so we do not
196 keep the set of called functions for indirect calls.
198 And probably more. */
200 static bool use_field_sensitive = true;
201 static int in_ipa_mode = 0;
203 /* Used for predecessor bitmaps. */
204 static bitmap_obstack predbitmap_obstack;
206 /* Used for points-to sets. */
207 static bitmap_obstack pta_obstack;
209 /* Used for oldsolution members of variables. */
210 static bitmap_obstack oldpta_obstack;
212 /* Used for per-solver-iteration bitmaps. */
213 static bitmap_obstack iteration_obstack;
215 static unsigned int create_variable_info_for (tree, const char *, bool);
216 typedef struct constraint_graph *constraint_graph_t;
217 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
219 struct constraint;
220 typedef struct constraint *constraint_t;
223 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
224 if (a) \
225 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
227 static struct constraint_stats
229 unsigned int total_vars;
230 unsigned int nonpointer_vars;
231 unsigned int unified_vars_static;
232 unsigned int unified_vars_dynamic;
233 unsigned int iterations;
234 unsigned int num_edges;
235 unsigned int num_implicit_edges;
236 unsigned int points_to_sets_created;
237 } stats;
239 struct variable_info
241 /* ID of this variable */
242 unsigned int id;
244 /* True if this is a variable created by the constraint analysis, such as
245 heap variables and constraints we had to break up. */
246 unsigned int is_artificial_var : 1;
248 /* True if this is a special variable whose solution set should not be
249 changed. */
250 unsigned int is_special_var : 1;
252 /* True for variables whose size is not known or variable. */
253 unsigned int is_unknown_size_var : 1;
255 /* True for (sub-)fields that represent a whole variable. */
256 unsigned int is_full_var : 1;
258 /* True if this is a heap variable. */
259 unsigned int is_heap_var : 1;
261 /* True if this is a register variable. */
262 unsigned int is_reg_var : 1;
264 /* True if this field may contain pointers. */
265 unsigned int may_have_pointers : 1;
267 /* True if this field has only restrict qualified pointers. */
268 unsigned int only_restrict_pointers : 1;
270 /* True if this represents a heap var created for a restrict qualified
271 pointer. */
272 unsigned int is_restrict_var : 1;
274 /* True if this represents a global variable. */
275 unsigned int is_global_var : 1;
277 /* True if this represents a module escape point for IPA analysis. */
278 unsigned int is_ipa_escape_point : 1;
280 /* True if this represents a IPA function info. */
281 unsigned int is_fn_info : 1;
283 /* ??? Store somewhere better. */
284 unsigned short ruid;
286 /* The ID of the variable for the next field in this structure
287 or zero for the last field in this structure. */
288 unsigned next;
290 /* The ID of the variable for the first field in this structure. */
291 unsigned head;
293 /* Offset of this variable, in bits, from the base variable */
294 unsigned HOST_WIDE_INT offset;
296 /* Size of the variable, in bits. */
297 unsigned HOST_WIDE_INT size;
299 /* Full size of the base variable, in bits. */
300 unsigned HOST_WIDE_INT fullsize;
302 /* Name of this variable */
303 const char *name;
305 /* Tree that this variable is associated with. */
306 tree decl;
308 /* Points-to set for this variable. */
309 bitmap solution;
311 /* Old points-to set for this variable. */
312 bitmap oldsolution;
314 typedef struct variable_info *varinfo_t;
316 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
317 static varinfo_t first_or_preceding_vi_for_offset (varinfo_t,
318 unsigned HOST_WIDE_INT);
319 static varinfo_t lookup_vi_for_tree (tree);
320 static inline bool type_can_have_subvars (const_tree);
321 static void make_param_constraints (varinfo_t);
323 /* Pool of variable info structures. */
324 static object_allocator<variable_info> variable_info_pool
325 ("Variable info pool");
327 /* Map varinfo to final pt_solution. */
328 static hash_map<varinfo_t, pt_solution *> *final_solutions;
329 struct obstack final_solutions_obstack;
331 /* Table of variable info structures for constraint variables.
332 Indexed directly by variable info id. */
333 static vec<varinfo_t> varmap;
335 /* Return the varmap element N */
337 static inline varinfo_t
338 get_varinfo (unsigned int n)
340 return varmap[n];
343 /* Return the next variable in the list of sub-variables of VI
344 or NULL if VI is the last sub-variable. */
346 static inline varinfo_t
347 vi_next (varinfo_t vi)
349 return get_varinfo (vi->next);
352 /* Static IDs for the special variables. Variable ID zero is unused
353 and used as terminator for the sub-variable chain. */
354 enum { nothing_id = 1, anything_id = 2, string_id = 3,
355 escaped_id = 4, nonlocal_id = 5,
356 storedanything_id = 6, integer_id = 7 };
358 /* Return a new variable info structure consisting for a variable
359 named NAME, and using constraint graph node NODE. Append it
360 to the vector of variable info structures. */
362 static varinfo_t
363 new_var_info (tree t, const char *name, bool add_id)
365 unsigned index = varmap.length ();
366 varinfo_t ret = variable_info_pool.allocate ();
368 if (dump_file && add_id)
370 char *tempname = xasprintf ("%s(%d)", name, index);
371 name = ggc_strdup (tempname);
372 free (tempname);
375 ret->id = index;
376 ret->name = name;
377 ret->decl = t;
378 /* Vars without decl are artificial and do not have sub-variables. */
379 ret->is_artificial_var = (t == NULL_TREE);
380 ret->is_special_var = false;
381 ret->is_unknown_size_var = false;
382 ret->is_full_var = (t == NULL_TREE);
383 ret->is_heap_var = false;
384 ret->may_have_pointers = true;
385 ret->only_restrict_pointers = false;
386 ret->is_restrict_var = false;
387 ret->ruid = 0;
388 ret->is_global_var = (t == NULL_TREE);
389 ret->is_ipa_escape_point = false;
390 ret->is_fn_info = false;
391 if (t && DECL_P (t))
392 ret->is_global_var = (is_global_var (t)
393 /* We have to treat even local register variables
394 as escape points. */
395 || (VAR_P (t) && DECL_HARD_REGISTER (t)));
396 ret->is_reg_var = (t && TREE_CODE (t) == SSA_NAME);
397 ret->solution = BITMAP_ALLOC (&pta_obstack);
398 ret->oldsolution = NULL;
399 ret->next = 0;
400 ret->head = ret->id;
402 stats.total_vars++;
404 varmap.safe_push (ret);
406 return ret;
409 /* A map mapping call statements to per-stmt variables for uses
410 and clobbers specific to the call. */
411 static hash_map<gimple *, varinfo_t> *call_stmt_vars;
413 /* Lookup or create the variable for the call statement CALL. */
415 static varinfo_t
416 get_call_vi (gcall *call)
418 varinfo_t vi, vi2;
420 bool existed;
421 varinfo_t *slot_p = &call_stmt_vars->get_or_insert (call, &existed);
422 if (existed)
423 return *slot_p;
425 vi = new_var_info (NULL_TREE, "CALLUSED", true);
426 vi->offset = 0;
427 vi->size = 1;
428 vi->fullsize = 2;
429 vi->is_full_var = true;
430 vi->is_reg_var = true;
432 vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED", true);
433 vi2->offset = 1;
434 vi2->size = 1;
435 vi2->fullsize = 2;
436 vi2->is_full_var = true;
437 vi2->is_reg_var = true;
439 vi->next = vi2->id;
441 *slot_p = vi;
442 return vi;
445 /* Lookup the variable for the call statement CALL representing
446 the uses. Returns NULL if there is nothing special about this call. */
448 static varinfo_t
449 lookup_call_use_vi (gcall *call)
451 varinfo_t *slot_p = call_stmt_vars->get (call);
452 if (slot_p)
453 return *slot_p;
455 return NULL;
458 /* Lookup the variable for the call statement CALL representing
459 the clobbers. Returns NULL if there is nothing special about this call. */
461 static varinfo_t
462 lookup_call_clobber_vi (gcall *call)
464 varinfo_t uses = lookup_call_use_vi (call);
465 if (!uses)
466 return NULL;
468 return vi_next (uses);
471 /* Lookup or create the variable for the call statement CALL representing
472 the uses. */
474 static varinfo_t
475 get_call_use_vi (gcall *call)
477 return get_call_vi (call);
480 /* Lookup or create the variable for the call statement CALL representing
481 the clobbers. */
483 static varinfo_t ATTRIBUTE_UNUSED
484 get_call_clobber_vi (gcall *call)
486 return vi_next (get_call_vi (call));
490 enum constraint_expr_type {SCALAR, DEREF, ADDRESSOF};
492 /* An expression that appears in a constraint. */
494 struct constraint_expr
496 /* Constraint type. */
497 constraint_expr_type type;
499 /* Variable we are referring to in the constraint. */
500 unsigned int var;
502 /* Offset, in bits, of this constraint from the beginning of
503 variables it ends up referring to.
505 IOW, in a deref constraint, we would deref, get the result set,
506 then add OFFSET to each member. */
507 HOST_WIDE_INT offset;
510 /* Use 0x8000... as special unknown offset. */
511 #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
513 typedef struct constraint_expr ce_s;
514 static void get_constraint_for_1 (tree, vec<ce_s> *, bool, bool);
515 static void get_constraint_for (tree, vec<ce_s> *);
516 static void get_constraint_for_rhs (tree, vec<ce_s> *);
517 static void do_deref (vec<ce_s> *);
519 /* Our set constraints are made up of two constraint expressions, one
520 LHS, and one RHS.
522 As described in the introduction, our set constraints each represent an
523 operation between set valued variables.
525 struct constraint
527 struct constraint_expr lhs;
528 struct constraint_expr rhs;
531 /* List of constraints that we use to build the constraint graph from. */
533 static vec<constraint_t> constraints;
534 static object_allocator<constraint> constraint_pool ("Constraint pool");
536 /* The constraint graph is represented as an array of bitmaps
537 containing successor nodes. */
539 struct constraint_graph
541 /* Size of this graph, which may be different than the number of
542 nodes in the variable map. */
543 unsigned int size;
545 /* Explicit successors of each node. */
546 bitmap *succs;
548 /* Implicit predecessors of each node (Used for variable
549 substitution). */
550 bitmap *implicit_preds;
552 /* Explicit predecessors of each node (Used for variable substitution). */
553 bitmap *preds;
555 /* Indirect cycle representatives, or -1 if the node has no indirect
556 cycles. */
557 int *indirect_cycles;
559 /* Representative node for a node. rep[a] == a unless the node has
560 been unified. */
561 unsigned int *rep;
563 /* Equivalence class representative for a label. This is used for
564 variable substitution. */
565 int *eq_rep;
567 /* Pointer equivalence label for a node. All nodes with the same
568 pointer equivalence label can be unified together at some point
569 (either during constraint optimization or after the constraint
570 graph is built). */
571 unsigned int *pe;
573 /* Pointer equivalence representative for a label. This is used to
574 handle nodes that are pointer equivalent but not location
575 equivalent. We can unite these once the addressof constraints
576 are transformed into initial points-to sets. */
577 int *pe_rep;
579 /* Pointer equivalence label for each node, used during variable
580 substitution. */
581 unsigned int *pointer_label;
583 /* Location equivalence label for each node, used during location
584 equivalence finding. */
585 unsigned int *loc_label;
587 /* Pointed-by set for each node, used during location equivalence
588 finding. This is pointed-by rather than pointed-to, because it
589 is constructed using the predecessor graph. */
590 bitmap *pointed_by;
592 /* Points to sets for pointer equivalence. This is *not* the actual
593 points-to sets for nodes. */
594 bitmap *points_to;
596 /* Bitmap of nodes where the bit is set if the node is a direct
597 node. Used for variable substitution. */
598 sbitmap direct_nodes;
600 /* Bitmap of nodes where the bit is set if the node is address
601 taken. Used for variable substitution. */
602 bitmap address_taken;
604 /* Vector of complex constraints for each graph node. Complex
605 constraints are those involving dereferences or offsets that are
606 not 0. */
607 vec<constraint_t> *complex;
610 static constraint_graph_t graph;
612 /* During variable substitution and the offline version of indirect
613 cycle finding, we create nodes to represent dereferences and
614 address taken constraints. These represent where these start and
615 end. */
616 #define FIRST_REF_NODE (varmap).length ()
617 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
619 /* Return the representative node for NODE, if NODE has been unioned
620 with another NODE.
621 This function performs path compression along the way to finding
622 the representative. */
624 static unsigned int
625 find (unsigned int node)
627 gcc_checking_assert (node < graph->size);
628 if (graph->rep[node] != node)
629 return graph->rep[node] = find (graph->rep[node]);
630 return node;
633 /* Union the TO and FROM nodes to the TO nodes.
634 Note that at some point in the future, we may want to do
635 union-by-rank, in which case we are going to have to return the
636 node we unified to. */
638 static bool
639 unite (unsigned int to, unsigned int from)
641 gcc_checking_assert (to < graph->size && from < graph->size);
642 if (to != from && graph->rep[from] != to)
644 graph->rep[from] = to;
645 return true;
647 return false;
650 /* Create a new constraint consisting of LHS and RHS expressions. */
652 static constraint_t
653 new_constraint (const struct constraint_expr lhs,
654 const struct constraint_expr rhs)
656 constraint_t ret = constraint_pool.allocate ();
657 ret->lhs = lhs;
658 ret->rhs = rhs;
659 return ret;
662 /* Print out constraint C to FILE. */
664 static void
665 dump_constraint (FILE *file, constraint_t c)
667 if (c->lhs.type == ADDRESSOF)
668 fprintf (file, "&");
669 else if (c->lhs.type == DEREF)
670 fprintf (file, "*");
671 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
672 if (c->lhs.offset == UNKNOWN_OFFSET)
673 fprintf (file, " + UNKNOWN");
674 else if (c->lhs.offset != 0)
675 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
676 fprintf (file, " = ");
677 if (c->rhs.type == ADDRESSOF)
678 fprintf (file, "&");
679 else if (c->rhs.type == DEREF)
680 fprintf (file, "*");
681 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
682 if (c->rhs.offset == UNKNOWN_OFFSET)
683 fprintf (file, " + UNKNOWN");
684 else if (c->rhs.offset != 0)
685 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
689 void debug_constraint (constraint_t);
690 void debug_constraints (void);
691 void debug_constraint_graph (void);
692 void debug_solution_for_var (unsigned int);
693 void debug_sa_points_to_info (void);
694 void debug_varinfo (varinfo_t);
695 void debug_varmap (void);
697 /* Print out constraint C to stderr. */
699 DEBUG_FUNCTION void
700 debug_constraint (constraint_t c)
702 dump_constraint (stderr, c);
703 fprintf (stderr, "\n");
706 /* Print out all constraints to FILE */
708 static void
709 dump_constraints (FILE *file, int from)
711 int i;
712 constraint_t c;
713 for (i = from; constraints.iterate (i, &c); i++)
714 if (c)
716 dump_constraint (file, c);
717 fprintf (file, "\n");
721 /* Print out all constraints to stderr. */
723 DEBUG_FUNCTION void
724 debug_constraints (void)
726 dump_constraints (stderr, 0);
729 /* Print the constraint graph in dot format. */
731 static void
732 dump_constraint_graph (FILE *file)
734 unsigned int i;
736 /* Only print the graph if it has already been initialized: */
737 if (!graph)
738 return;
740 /* Prints the header of the dot file: */
741 fprintf (file, "strict digraph {\n");
742 fprintf (file, " node [\n shape = box\n ]\n");
743 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
744 fprintf (file, "\n // List of nodes and complex constraints in "
745 "the constraint graph:\n");
747 /* The next lines print the nodes in the graph together with the
748 complex constraints attached to them. */
749 for (i = 1; i < graph->size; i++)
751 if (i == FIRST_REF_NODE)
752 continue;
753 if (find (i) != i)
754 continue;
755 if (i < FIRST_REF_NODE)
756 fprintf (file, "\"%s\"", get_varinfo (i)->name);
757 else
758 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
759 if (graph->complex[i].exists ())
761 unsigned j;
762 constraint_t c;
763 fprintf (file, " [label=\"\\N\\n");
764 for (j = 0; graph->complex[i].iterate (j, &c); ++j)
766 dump_constraint (file, c);
767 fprintf (file, "\\l");
769 fprintf (file, "\"]");
771 fprintf (file, ";\n");
774 /* Go over the edges. */
775 fprintf (file, "\n // Edges in the constraint graph:\n");
776 for (i = 1; i < graph->size; i++)
778 unsigned j;
779 bitmap_iterator bi;
780 if (find (i) != i)
781 continue;
782 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
784 unsigned to = find (j);
785 if (i == to)
786 continue;
787 if (i < FIRST_REF_NODE)
788 fprintf (file, "\"%s\"", get_varinfo (i)->name);
789 else
790 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
791 fprintf (file, " -> ");
792 if (to < FIRST_REF_NODE)
793 fprintf (file, "\"%s\"", get_varinfo (to)->name);
794 else
795 fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name);
796 fprintf (file, ";\n");
800 /* Prints the tail of the dot file. */
801 fprintf (file, "}\n");
804 /* Print out the constraint graph to stderr. */
806 DEBUG_FUNCTION void
807 debug_constraint_graph (void)
809 dump_constraint_graph (stderr);
812 /* SOLVER FUNCTIONS
814 The solver is a simple worklist solver, that works on the following
815 algorithm:
817 sbitmap changed_nodes = all zeroes;
818 changed_count = 0;
819 For each node that is not already collapsed:
820 changed_count++;
821 set bit in changed nodes
823 while (changed_count > 0)
825 compute topological ordering for constraint graph
827 find and collapse cycles in the constraint graph (updating
828 changed if necessary)
830 for each node (n) in the graph in topological order:
831 changed_count--;
833 Process each complex constraint associated with the node,
834 updating changed if necessary.
836 For each outgoing edge from n, propagate the solution from n to
837 the destination of the edge, updating changed as necessary.
839 } */
841 /* Return true if two constraint expressions A and B are equal. */
843 static bool
844 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
846 return a.type == b.type && a.var == b.var && a.offset == b.offset;
849 /* Return true if constraint expression A is less than constraint expression
850 B. This is just arbitrary, but consistent, in order to give them an
851 ordering. */
853 static bool
854 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
856 if (a.type == b.type)
858 if (a.var == b.var)
859 return a.offset < b.offset;
860 else
861 return a.var < b.var;
863 else
864 return a.type < b.type;
867 /* Return true if constraint A is less than constraint B. This is just
868 arbitrary, but consistent, in order to give them an ordering. */
870 static bool
871 constraint_less (const constraint_t &a, const constraint_t &b)
873 if (constraint_expr_less (a->lhs, b->lhs))
874 return true;
875 else if (constraint_expr_less (b->lhs, a->lhs))
876 return false;
877 else
878 return constraint_expr_less (a->rhs, b->rhs);
881 /* Return true if two constraints A and B are equal. */
883 static bool
884 constraint_equal (struct constraint a, struct constraint b)
886 return constraint_expr_equal (a.lhs, b.lhs)
887 && constraint_expr_equal (a.rhs, b.rhs);
891 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
893 static constraint_t
894 constraint_vec_find (vec<constraint_t> vec,
895 struct constraint lookfor)
897 unsigned int place;
898 constraint_t found;
900 if (!vec.exists ())
901 return NULL;
903 place = vec.lower_bound (&lookfor, constraint_less);
904 if (place >= vec.length ())
905 return NULL;
906 found = vec[place];
907 if (!constraint_equal (*found, lookfor))
908 return NULL;
909 return found;
912 /* Union two constraint vectors, TO and FROM. Put the result in TO.
913 Returns true of TO set is changed. */
915 static bool
916 constraint_set_union (vec<constraint_t> *to,
917 vec<constraint_t> *from)
919 int i;
920 constraint_t c;
921 bool any_change = false;
923 FOR_EACH_VEC_ELT (*from, i, c)
925 if (constraint_vec_find (*to, *c) == NULL)
927 unsigned int place = to->lower_bound (c, constraint_less);
928 to->safe_insert (place, c);
929 any_change = true;
932 return any_change;
935 /* Expands the solution in SET to all sub-fields of variables included. */
937 static bitmap
938 solution_set_expand (bitmap set, bitmap *expanded)
940 bitmap_iterator bi;
941 unsigned j;
943 if (*expanded)
944 return *expanded;
946 *expanded = BITMAP_ALLOC (&iteration_obstack);
948 /* In a first pass expand to the head of the variables we need to
949 add all sub-fields off. This avoids quadratic behavior. */
950 EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
952 varinfo_t v = get_varinfo (j);
953 if (v->is_artificial_var
954 || v->is_full_var)
955 continue;
956 bitmap_set_bit (*expanded, v->head);
959 /* In the second pass now expand all head variables with subfields. */
960 EXECUTE_IF_SET_IN_BITMAP (*expanded, 0, j, bi)
962 varinfo_t v = get_varinfo (j);
963 if (v->head != j)
964 continue;
965 for (v = vi_next (v); v != NULL; v = vi_next (v))
966 bitmap_set_bit (*expanded, v->id);
969 /* And finally set the rest of the bits from SET. */
970 bitmap_ior_into (*expanded, set);
972 return *expanded;
975 /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
976 process. */
978 static bool
979 set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
980 bitmap *expanded_delta)
982 bool changed = false;
983 bitmap_iterator bi;
984 unsigned int i;
986 /* If the solution of DELTA contains anything it is good enough to transfer
987 this to TO. */
988 if (bitmap_bit_p (delta, anything_id))
989 return bitmap_set_bit (to, anything_id);
991 /* If the offset is unknown we have to expand the solution to
992 all subfields. */
993 if (inc == UNKNOWN_OFFSET)
995 delta = solution_set_expand (delta, expanded_delta);
996 changed |= bitmap_ior_into (to, delta);
997 return changed;
1000 /* For non-zero offset union the offsetted solution into the destination. */
1001 EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
1003 varinfo_t vi = get_varinfo (i);
1005 /* If this is a variable with just one field just set its bit
1006 in the result. */
1007 if (vi->is_artificial_var
1008 || vi->is_unknown_size_var
1009 || vi->is_full_var)
1010 changed |= bitmap_set_bit (to, i);
1011 else
1013 HOST_WIDE_INT fieldoffset = vi->offset + inc;
1014 unsigned HOST_WIDE_INT size = vi->size;
1016 /* If the offset makes the pointer point to before the
1017 variable use offset zero for the field lookup. */
1018 if (fieldoffset < 0)
1019 vi = get_varinfo (vi->head);
1020 else
1021 vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
1025 changed |= bitmap_set_bit (to, vi->id);
1026 if (vi->is_full_var
1027 || vi->next == 0)
1028 break;
1030 /* We have to include all fields that overlap the current field
1031 shifted by inc. */
1032 vi = vi_next (vi);
1034 while (vi->offset < fieldoffset + size);
1038 return changed;
1041 /* Insert constraint C into the list of complex constraints for graph
1042 node VAR. */
1044 static void
1045 insert_into_complex (constraint_graph_t graph,
1046 unsigned int var, constraint_t c)
1048 vec<constraint_t> complex = graph->complex[var];
1049 unsigned int place = complex.lower_bound (c, constraint_less);
1051 /* Only insert constraints that do not already exist. */
1052 if (place >= complex.length ()
1053 || !constraint_equal (*c, *complex[place]))
1054 graph->complex[var].safe_insert (place, c);
1058 /* Condense two variable nodes into a single variable node, by moving
1059 all associated info from FROM to TO. Returns true if TO node's
1060 constraint set changes after the merge. */
1062 static bool
1063 merge_node_constraints (constraint_graph_t graph, unsigned int to,
1064 unsigned int from)
1066 unsigned int i;
1067 constraint_t c;
1068 bool any_change = false;
1070 gcc_checking_assert (find (from) == to);
1072 /* Move all complex constraints from src node into to node */
1073 FOR_EACH_VEC_ELT (graph->complex[from], i, c)
1075 /* In complex constraints for node FROM, we may have either
1076 a = *FROM, and *FROM = a, or an offseted constraint which are
1077 always added to the rhs node's constraints. */
1079 if (c->rhs.type == DEREF)
1080 c->rhs.var = to;
1081 else if (c->lhs.type == DEREF)
1082 c->lhs.var = to;
1083 else
1084 c->rhs.var = to;
1087 any_change = constraint_set_union (&graph->complex[to],
1088 &graph->complex[from]);
1089 graph->complex[from].release ();
1090 return any_change;
1094 /* Remove edges involving NODE from GRAPH. */
1096 static void
1097 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
1099 if (graph->succs[node])
1100 BITMAP_FREE (graph->succs[node]);
1103 /* Merge GRAPH nodes FROM and TO into node TO. */
1105 static void
1106 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1107 unsigned int from)
1109 if (graph->indirect_cycles[from] != -1)
1111 /* If we have indirect cycles with the from node, and we have
1112 none on the to node, the to node has indirect cycles from the
1113 from node now that they are unified.
1114 If indirect cycles exist on both, unify the nodes that they
1115 are in a cycle with, since we know they are in a cycle with
1116 each other. */
1117 if (graph->indirect_cycles[to] == -1)
1118 graph->indirect_cycles[to] = graph->indirect_cycles[from];
1121 /* Merge all the successor edges. */
1122 if (graph->succs[from])
1124 if (!graph->succs[to])
1125 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1126 bitmap_ior_into (graph->succs[to],
1127 graph->succs[from]);
1130 clear_edges_for_node (graph, from);
1134 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1135 it doesn't exist in the graph already. */
1137 static void
1138 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1139 unsigned int from)
1141 if (to == from)
1142 return;
1144 if (!graph->implicit_preds[to])
1145 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1147 if (bitmap_set_bit (graph->implicit_preds[to], from))
1148 stats.num_implicit_edges++;
1151 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1152 it doesn't exist in the graph already.
1153 Return false if the edge already existed, true otherwise. */
1155 static void
1156 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1157 unsigned int from)
1159 if (!graph->preds[to])
1160 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1161 bitmap_set_bit (graph->preds[to], from);
1164 /* Add a graph edge to GRAPH, going from FROM to TO if
1165 it doesn't exist in the graph already.
1166 Return false if the edge already existed, true otherwise. */
1168 static bool
1169 add_graph_edge (constraint_graph_t graph, unsigned int to,
1170 unsigned int from)
1172 if (to == from)
1174 return false;
1176 else
1178 bool r = false;
1180 if (!graph->succs[from])
1181 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1182 if (bitmap_set_bit (graph->succs[from], to))
1184 r = true;
1185 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1186 stats.num_edges++;
1188 return r;
1193 /* Initialize the constraint graph structure to contain SIZE nodes. */
1195 static void
1196 init_graph (unsigned int size)
1198 unsigned int j;
1200 graph = XCNEW (struct constraint_graph);
1201 graph->size = size;
1202 graph->succs = XCNEWVEC (bitmap, graph->size);
1203 graph->indirect_cycles = XNEWVEC (int, graph->size);
1204 graph->rep = XNEWVEC (unsigned int, graph->size);
1205 /* ??? Macros do not support template types with multiple arguments,
1206 so we use a typedef to work around it. */
1207 typedef vec<constraint_t> vec_constraint_t_heap;
1208 graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
1209 graph->pe = XCNEWVEC (unsigned int, graph->size);
1210 graph->pe_rep = XNEWVEC (int, graph->size);
1212 for (j = 0; j < graph->size; j++)
1214 graph->rep[j] = j;
1215 graph->pe_rep[j] = -1;
1216 graph->indirect_cycles[j] = -1;
1220 /* Build the constraint graph, adding only predecessor edges right now. */
1222 static void
1223 build_pred_graph (void)
1225 int i;
1226 constraint_t c;
1227 unsigned int j;
1229 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1230 graph->preds = XCNEWVEC (bitmap, graph->size);
1231 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1232 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1233 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1234 graph->points_to = XCNEWVEC (bitmap, graph->size);
1235 graph->eq_rep = XNEWVEC (int, graph->size);
1236 graph->direct_nodes = sbitmap_alloc (graph->size);
1237 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1238 bitmap_clear (graph->direct_nodes);
1240 for (j = 1; j < FIRST_REF_NODE; j++)
1242 if (!get_varinfo (j)->is_special_var)
1243 bitmap_set_bit (graph->direct_nodes, j);
1246 for (j = 0; j < graph->size; j++)
1247 graph->eq_rep[j] = -1;
1249 for (j = 0; j < varmap.length (); j++)
1250 graph->indirect_cycles[j] = -1;
1252 FOR_EACH_VEC_ELT (constraints, i, c)
1254 struct constraint_expr lhs = c->lhs;
1255 struct constraint_expr rhs = c->rhs;
1256 unsigned int lhsvar = lhs.var;
1257 unsigned int rhsvar = rhs.var;
1259 if (lhs.type == DEREF)
1261 /* *x = y. */
1262 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1263 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1265 else if (rhs.type == DEREF)
1267 /* x = *y */
1268 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1269 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1270 else
1271 bitmap_clear_bit (graph->direct_nodes, lhsvar);
1273 else if (rhs.type == ADDRESSOF)
1275 varinfo_t v;
1277 /* x = &y */
1278 if (graph->points_to[lhsvar] == NULL)
1279 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1280 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1282 if (graph->pointed_by[rhsvar] == NULL)
1283 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1284 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1286 /* Implicitly, *x = y */
1287 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1289 /* All related variables are no longer direct nodes. */
1290 bitmap_clear_bit (graph->direct_nodes, rhsvar);
1291 v = get_varinfo (rhsvar);
1292 if (!v->is_full_var)
1294 v = get_varinfo (v->head);
1297 bitmap_clear_bit (graph->direct_nodes, v->id);
1298 v = vi_next (v);
1300 while (v != NULL);
1302 bitmap_set_bit (graph->address_taken, rhsvar);
1304 else if (lhsvar > anything_id
1305 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1307 /* x = y */
1308 add_pred_graph_edge (graph, lhsvar, rhsvar);
1309 /* Implicitly, *x = *y */
1310 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1311 FIRST_REF_NODE + rhsvar);
1313 else if (lhs.offset != 0 || rhs.offset != 0)
1315 if (rhs.offset != 0)
1316 bitmap_clear_bit (graph->direct_nodes, lhs.var);
1317 else if (lhs.offset != 0)
1318 bitmap_clear_bit (graph->direct_nodes, rhs.var);
1323 /* Build the constraint graph, adding successor edges. */
1325 static void
1326 build_succ_graph (void)
1328 unsigned i, t;
1329 constraint_t c;
1331 FOR_EACH_VEC_ELT (constraints, i, c)
1333 struct constraint_expr lhs;
1334 struct constraint_expr rhs;
1335 unsigned int lhsvar;
1336 unsigned int rhsvar;
1338 if (!c)
1339 continue;
1341 lhs = c->lhs;
1342 rhs = c->rhs;
1343 lhsvar = find (lhs.var);
1344 rhsvar = find (rhs.var);
1346 if (lhs.type == DEREF)
1348 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1349 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1351 else if (rhs.type == DEREF)
1353 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1354 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1356 else if (rhs.type == ADDRESSOF)
1358 /* x = &y */
1359 gcc_checking_assert (find (rhs.var) == rhs.var);
1360 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1362 else if (lhsvar > anything_id
1363 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1365 add_graph_edge (graph, lhsvar, rhsvar);
1369 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1370 receive pointers. */
1371 t = find (storedanything_id);
1372 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1374 if (!bitmap_bit_p (graph->direct_nodes, i)
1375 && get_varinfo (i)->may_have_pointers)
1376 add_graph_edge (graph, find (i), t);
1379 /* Everything stored to ANYTHING also potentially escapes. */
1380 add_graph_edge (graph, find (escaped_id), t);
1384 /* Changed variables on the last iteration. */
1385 static bitmap changed;
1387 /* Strongly Connected Component visitation info. */
1389 struct scc_info
1391 scc_info (size_t size);
1392 ~scc_info ();
1394 auto_sbitmap visited;
1395 auto_sbitmap deleted;
1396 unsigned int *dfs;
1397 unsigned int *node_mapping;
1398 int current_index;
1399 auto_vec<unsigned> scc_stack;
1403 /* Recursive routine to find strongly connected components in GRAPH.
1404 SI is the SCC info to store the information in, and N is the id of current
1405 graph node we are processing.
1407 This is Tarjan's strongly connected component finding algorithm, as
1408 modified by Nuutila to keep only non-root nodes on the stack.
1409 The algorithm can be found in "On finding the strongly connected
1410 connected components in a directed graph" by Esko Nuutila and Eljas
1411 Soisalon-Soininen, in Information Processing Letters volume 49,
1412 number 1, pages 9-14. */
1414 static void
1415 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1417 unsigned int i;
1418 bitmap_iterator bi;
1419 unsigned int my_dfs;
1421 bitmap_set_bit (si->visited, n);
1422 si->dfs[n] = si->current_index ++;
1423 my_dfs = si->dfs[n];
1425 /* Visit all the successors. */
1426 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1428 unsigned int w;
1430 if (i > LAST_REF_NODE)
1431 break;
1433 w = find (i);
1434 if (bitmap_bit_p (si->deleted, w))
1435 continue;
1437 if (!bitmap_bit_p (si->visited, w))
1438 scc_visit (graph, si, w);
1440 unsigned int t = find (w);
1441 gcc_checking_assert (find (n) == n);
1442 if (si->dfs[t] < si->dfs[n])
1443 si->dfs[n] = si->dfs[t];
1446 /* See if any components have been identified. */
1447 if (si->dfs[n] == my_dfs)
1449 if (si->scc_stack.length () > 0
1450 && si->dfs[si->scc_stack.last ()] >= my_dfs)
1452 bitmap scc = BITMAP_ALLOC (NULL);
1453 unsigned int lowest_node;
1454 bitmap_iterator bi;
1456 bitmap_set_bit (scc, n);
1458 while (si->scc_stack.length () != 0
1459 && si->dfs[si->scc_stack.last ()] >= my_dfs)
1461 unsigned int w = si->scc_stack.pop ();
1463 bitmap_set_bit (scc, w);
1466 lowest_node = bitmap_first_set_bit (scc);
1467 gcc_assert (lowest_node < FIRST_REF_NODE);
1469 /* Collapse the SCC nodes into a single node, and mark the
1470 indirect cycles. */
1471 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1473 if (i < FIRST_REF_NODE)
1475 if (unite (lowest_node, i))
1476 unify_nodes (graph, lowest_node, i, false);
1478 else
1480 unite (lowest_node, i);
1481 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1485 bitmap_set_bit (si->deleted, n);
1487 else
1488 si->scc_stack.safe_push (n);
1491 /* Unify node FROM into node TO, updating the changed count if
1492 necessary when UPDATE_CHANGED is true. */
1494 static void
1495 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1496 bool update_changed)
1498 gcc_checking_assert (to != from && find (to) == to);
1500 if (dump_file && (dump_flags & TDF_DETAILS))
1501 fprintf (dump_file, "Unifying %s to %s\n",
1502 get_varinfo (from)->name,
1503 get_varinfo (to)->name);
1505 if (update_changed)
1506 stats.unified_vars_dynamic++;
1507 else
1508 stats.unified_vars_static++;
1510 merge_graph_nodes (graph, to, from);
1511 if (merge_node_constraints (graph, to, from))
1513 if (update_changed)
1514 bitmap_set_bit (changed, to);
1517 /* Mark TO as changed if FROM was changed. If TO was already marked
1518 as changed, decrease the changed count. */
1520 if (update_changed
1521 && bitmap_clear_bit (changed, from))
1522 bitmap_set_bit (changed, to);
1523 varinfo_t fromvi = get_varinfo (from);
1524 if (fromvi->solution)
1526 /* If the solution changes because of the merging, we need to mark
1527 the variable as changed. */
1528 varinfo_t tovi = get_varinfo (to);
1529 if (bitmap_ior_into (tovi->solution, fromvi->solution))
1531 if (update_changed)
1532 bitmap_set_bit (changed, to);
1535 BITMAP_FREE (fromvi->solution);
1536 if (fromvi->oldsolution)
1537 BITMAP_FREE (fromvi->oldsolution);
1539 if (stats.iterations > 0
1540 && tovi->oldsolution)
1541 BITMAP_FREE (tovi->oldsolution);
1543 if (graph->succs[to])
1544 bitmap_clear_bit (graph->succs[to], to);
1547 /* Information needed to compute the topological ordering of a graph. */
1549 struct topo_info
1551 /* sbitmap of visited nodes. */
1552 sbitmap visited;
1553 /* Array that stores the topological order of the graph, *in
1554 reverse*. */
1555 vec<unsigned> topo_order;
1559 /* Initialize and return a topological info structure. */
1561 static struct topo_info *
1562 init_topo_info (void)
1564 size_t size = graph->size;
1565 struct topo_info *ti = XNEW (struct topo_info);
1566 ti->visited = sbitmap_alloc (size);
1567 bitmap_clear (ti->visited);
1568 ti->topo_order.create (1);
1569 return ti;
1573 /* Free the topological sort info pointed to by TI. */
1575 static void
1576 free_topo_info (struct topo_info *ti)
1578 sbitmap_free (ti->visited);
1579 ti->topo_order.release ();
1580 free (ti);
1583 /* Visit the graph in topological order, and store the order in the
1584 topo_info structure. */
1586 static void
1587 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1588 unsigned int n)
1590 bitmap_iterator bi;
1591 unsigned int j;
1593 bitmap_set_bit (ti->visited, n);
1595 if (graph->succs[n])
1596 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1598 if (!bitmap_bit_p (ti->visited, j))
1599 topo_visit (graph, ti, j);
1602 ti->topo_order.safe_push (n);
1605 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1606 starting solution for y. */
1608 static void
1609 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1610 bitmap delta, bitmap *expanded_delta)
1612 unsigned int lhs = c->lhs.var;
1613 bool flag = false;
1614 bitmap sol = get_varinfo (lhs)->solution;
1615 unsigned int j;
1616 bitmap_iterator bi;
1617 HOST_WIDE_INT roffset = c->rhs.offset;
1619 /* Our IL does not allow this. */
1620 gcc_checking_assert (c->lhs.offset == 0);
1622 /* If the solution of Y contains anything it is good enough to transfer
1623 this to the LHS. */
1624 if (bitmap_bit_p (delta, anything_id))
1626 flag |= bitmap_set_bit (sol, anything_id);
1627 goto done;
1630 /* If we do not know at with offset the rhs is dereferenced compute
1631 the reachability set of DELTA, conservatively assuming it is
1632 dereferenced at all valid offsets. */
1633 if (roffset == UNKNOWN_OFFSET)
1635 delta = solution_set_expand (delta, expanded_delta);
1636 /* No further offset processing is necessary. */
1637 roffset = 0;
1640 /* For each variable j in delta (Sol(y)), add
1641 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1642 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1644 varinfo_t v = get_varinfo (j);
1645 HOST_WIDE_INT fieldoffset = v->offset + roffset;
1646 unsigned HOST_WIDE_INT size = v->size;
1647 unsigned int t;
1649 if (v->is_full_var)
1651 else if (roffset != 0)
1653 if (fieldoffset < 0)
1654 v = get_varinfo (v->head);
1655 else
1656 v = first_or_preceding_vi_for_offset (v, fieldoffset);
1659 /* We have to include all fields that overlap the current field
1660 shifted by roffset. */
1663 t = find (v->id);
1665 /* Adding edges from the special vars is pointless.
1666 They don't have sets that can change. */
1667 if (get_varinfo (t)->is_special_var)
1668 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1669 /* Merging the solution from ESCAPED needlessly increases
1670 the set. Use ESCAPED as representative instead. */
1671 else if (v->id == escaped_id)
1672 flag |= bitmap_set_bit (sol, escaped_id);
1673 else if (v->may_have_pointers
1674 && add_graph_edge (graph, lhs, t))
1675 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1677 if (v->is_full_var
1678 || v->next == 0)
1679 break;
1681 v = vi_next (v);
1683 while (v->offset < fieldoffset + size);
1686 done:
1687 /* If the LHS solution changed, mark the var as changed. */
1688 if (flag)
1690 get_varinfo (lhs)->solution = sol;
1691 bitmap_set_bit (changed, lhs);
1695 /* Process a constraint C that represents *(x + off) = y using DELTA
1696 as the starting solution for x. */
1698 static void
1699 do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1701 unsigned int rhs = c->rhs.var;
1702 bitmap sol = get_varinfo (rhs)->solution;
1703 unsigned int j;
1704 bitmap_iterator bi;
1705 HOST_WIDE_INT loff = c->lhs.offset;
1706 bool escaped_p = false;
1708 /* Our IL does not allow this. */
1709 gcc_checking_assert (c->rhs.offset == 0);
1711 /* If the solution of y contains ANYTHING simply use the ANYTHING
1712 solution. This avoids needlessly increasing the points-to sets. */
1713 if (bitmap_bit_p (sol, anything_id))
1714 sol = get_varinfo (find (anything_id))->solution;
1716 /* If the solution for x contains ANYTHING we have to merge the
1717 solution of y into all pointer variables which we do via
1718 STOREDANYTHING. */
1719 if (bitmap_bit_p (delta, anything_id))
1721 unsigned t = find (storedanything_id);
1722 if (add_graph_edge (graph, t, rhs))
1724 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1725 bitmap_set_bit (changed, t);
1727 return;
1730 /* If we do not know at with offset the rhs is dereferenced compute
1731 the reachability set of DELTA, conservatively assuming it is
1732 dereferenced at all valid offsets. */
1733 if (loff == UNKNOWN_OFFSET)
1735 delta = solution_set_expand (delta, expanded_delta);
1736 loff = 0;
1739 /* For each member j of delta (Sol(x)), add an edge from y to j and
1740 union Sol(y) into Sol(j) */
1741 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1743 varinfo_t v = get_varinfo (j);
1744 unsigned int t;
1745 HOST_WIDE_INT fieldoffset = v->offset + loff;
1746 unsigned HOST_WIDE_INT size = v->size;
1748 if (v->is_full_var)
1750 else if (loff != 0)
1752 if (fieldoffset < 0)
1753 v = get_varinfo (v->head);
1754 else
1755 v = first_or_preceding_vi_for_offset (v, fieldoffset);
1758 /* We have to include all fields that overlap the current field
1759 shifted by loff. */
1762 if (v->may_have_pointers)
1764 /* If v is a global variable then this is an escape point. */
1765 if (v->is_global_var
1766 && !escaped_p)
1768 t = find (escaped_id);
1769 if (add_graph_edge (graph, t, rhs)
1770 && bitmap_ior_into (get_varinfo (t)->solution, sol))
1771 bitmap_set_bit (changed, t);
1772 /* Enough to let rhs escape once. */
1773 escaped_p = true;
1776 if (v->is_special_var)
1777 break;
1779 t = find (v->id);
1780 if (add_graph_edge (graph, t, rhs)
1781 && bitmap_ior_into (get_varinfo (t)->solution, sol))
1782 bitmap_set_bit (changed, t);
1785 if (v->is_full_var
1786 || v->next == 0)
1787 break;
1789 v = vi_next (v);
1791 while (v->offset < fieldoffset + size);
1795 /* Handle a non-simple (simple meaning requires no iteration),
1796 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1798 static void
1799 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1800 bitmap *expanded_delta)
1802 if (c->lhs.type == DEREF)
1804 if (c->rhs.type == ADDRESSOF)
1806 gcc_unreachable ();
1808 else
1810 /* *x = y */
1811 do_ds_constraint (c, delta, expanded_delta);
1814 else if (c->rhs.type == DEREF)
1816 /* x = *y */
1817 if (!(get_varinfo (c->lhs.var)->is_special_var))
1818 do_sd_constraint (graph, c, delta, expanded_delta);
1820 else
1822 bitmap tmp;
1823 bool flag = false;
1825 gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1826 && c->rhs.offset != 0 && c->lhs.offset == 0);
1827 tmp = get_varinfo (c->lhs.var)->solution;
1829 flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1830 expanded_delta);
1832 if (flag)
1833 bitmap_set_bit (changed, c->lhs.var);
1837 /* Initialize and return a new SCC info structure. */
1839 scc_info::scc_info (size_t size) :
1840 visited (size), deleted (size), current_index (0), scc_stack (1)
1842 bitmap_clear (visited);
1843 bitmap_clear (deleted);
1844 node_mapping = XNEWVEC (unsigned int, size);
1845 dfs = XCNEWVEC (unsigned int, size);
1847 for (size_t i = 0; i < size; i++)
1848 node_mapping[i] = i;
1851 /* Free an SCC info structure pointed to by SI */
1853 scc_info::~scc_info ()
1855 free (node_mapping);
1856 free (dfs);
1860 /* Find indirect cycles in GRAPH that occur, using strongly connected
1861 components, and note them in the indirect cycles map.
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. */
1867 static void
1868 find_indirect_cycles (constraint_graph_t graph)
1870 unsigned int i;
1871 unsigned int size = graph->size;
1872 scc_info si (size);
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);
1879 /* Compute a topological ordering for GRAPH, and store the result in the
1880 topo_info structure TI. */
1882 static void
1883 compute_topo_order (constraint_graph_t graph,
1884 struct topo_info *ti)
1886 unsigned int i;
1887 unsigned int size = graph->size;
1889 for (i = 0; i != size; ++i)
1890 if (!bitmap_bit_p (ti->visited, i) && find (i) == i)
1891 topo_visit (graph, ti, i);
1894 /* Structure used to for hash value numbering of pointer equivalence
1895 classes. */
1897 typedef struct equiv_class_label
1899 hashval_t hashcode;
1900 unsigned int equivalence_class;
1901 bitmap labels;
1902 } *equiv_class_label_t;
1903 typedef const struct equiv_class_label *const_equiv_class_label_t;
1905 /* Equiv_class_label hashtable helpers. */
1907 struct equiv_class_hasher : free_ptr_hash <equiv_class_label>
1909 static inline hashval_t hash (const equiv_class_label *);
1910 static inline bool equal (const equiv_class_label *,
1911 const equiv_class_label *);
1914 /* Hash function for a equiv_class_label_t */
1916 inline hashval_t
1917 equiv_class_hasher::hash (const equiv_class_label *ecl)
1919 return ecl->hashcode;
1922 /* Equality function for two equiv_class_label_t's. */
1924 inline bool
1925 equiv_class_hasher::equal (const equiv_class_label *eql1,
1926 const equiv_class_label *eql2)
1928 return (eql1->hashcode == eql2->hashcode
1929 && bitmap_equal_p (eql1->labels, eql2->labels));
1932 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1933 classes. */
1934 static hash_table<equiv_class_hasher> *pointer_equiv_class_table;
1936 /* A hashtable for mapping a bitmap of labels->location equivalence
1937 classes. */
1938 static hash_table<equiv_class_hasher> *location_equiv_class_table;
1940 /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1941 hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1942 is equivalent to. */
1944 static equiv_class_label *
1945 equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1946 bitmap labels)
1948 equiv_class_label **slot;
1949 equiv_class_label ecl;
1951 ecl.labels = labels;
1952 ecl.hashcode = bitmap_hash (labels);
1953 slot = table->find_slot (&ecl, INSERT);
1954 if (!*slot)
1956 *slot = XNEW (struct equiv_class_label);
1957 (*slot)->labels = labels;
1958 (*slot)->hashcode = ecl.hashcode;
1959 (*slot)->equivalence_class = 0;
1962 return *slot;
1965 /* Perform offline variable substitution.
1967 This is a worst case quadratic time way of identifying variables
1968 that must have equivalent points-to sets, including those caused by
1969 static cycles, and single entry subgraphs, in the constraint graph.
1971 The technique is described in "Exploiting Pointer and Location
1972 Equivalence to Optimize Pointer Analysis. In the 14th International
1973 Static Analysis Symposium (SAS), August 2007." It is known as the
1974 "HU" algorithm, and is equivalent to value numbering the collapsed
1975 constraint graph including evaluating unions.
1977 The general method of finding equivalence classes is as follows:
1978 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1979 Initialize all non-REF nodes to be direct nodes.
1980 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1981 variable}
1982 For each constraint containing the dereference, we also do the same
1983 thing.
1985 We then compute SCC's in the graph and unify nodes in the same SCC,
1986 including pts sets.
1988 For each non-collapsed node x:
1989 Visit all unvisited explicit incoming edges.
1990 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1991 where y->x.
1992 Lookup the equivalence class for pts(x).
1993 If we found one, equivalence_class(x) = found class.
1994 Otherwise, equivalence_class(x) = new class, and new_class is
1995 added to the lookup table.
1997 All direct nodes with the same equivalence class can be replaced
1998 with a single representative node.
1999 All unlabeled nodes (label == 0) are not pointers and all edges
2000 involving them can be eliminated.
2001 We perform these optimizations during rewrite_constraints
2003 In addition to pointer equivalence class finding, we also perform
2004 location equivalence class finding. This is the set of variables
2005 that always appear together in points-to sets. We use this to
2006 compress the size of the points-to sets. */
2008 /* Current maximum pointer equivalence class id. */
2009 static int pointer_equiv_class;
2011 /* Current maximum location equivalence class id. */
2012 static int location_equiv_class;
2014 /* Recursive routine to find strongly connected components in GRAPH,
2015 and label it's nodes with DFS numbers. */
2017 static void
2018 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2020 unsigned int i;
2021 bitmap_iterator bi;
2022 unsigned int my_dfs;
2024 gcc_checking_assert (si->node_mapping[n] == n);
2025 bitmap_set_bit (si->visited, n);
2026 si->dfs[n] = si->current_index ++;
2027 my_dfs = si->dfs[n];
2029 /* Visit all the successors. */
2030 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2032 unsigned int w = si->node_mapping[i];
2034 if (bitmap_bit_p (si->deleted, w))
2035 continue;
2037 if (!bitmap_bit_p (si->visited, w))
2038 condense_visit (graph, si, w);
2040 unsigned int t = si->node_mapping[w];
2041 gcc_checking_assert (si->node_mapping[n] == n);
2042 if (si->dfs[t] < si->dfs[n])
2043 si->dfs[n] = si->dfs[t];
2046 /* Visit all the implicit predecessors. */
2047 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
2049 unsigned int w = si->node_mapping[i];
2051 if (bitmap_bit_p (si->deleted, w))
2052 continue;
2054 if (!bitmap_bit_p (si->visited, w))
2055 condense_visit (graph, si, w);
2057 unsigned int t = si->node_mapping[w];
2058 gcc_assert (si->node_mapping[n] == n);
2059 if (si->dfs[t] < si->dfs[n])
2060 si->dfs[n] = si->dfs[t];
2063 /* See if any components have been identified. */
2064 if (si->dfs[n] == my_dfs)
2066 while (si->scc_stack.length () != 0
2067 && si->dfs[si->scc_stack.last ()] >= my_dfs)
2069 unsigned int w = si->scc_stack.pop ();
2070 si->node_mapping[w] = n;
2072 if (!bitmap_bit_p (graph->direct_nodes, w))
2073 bitmap_clear_bit (graph->direct_nodes, n);
2075 /* Unify our nodes. */
2076 if (graph->preds[w])
2078 if (!graph->preds[n])
2079 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2080 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2082 if (graph->implicit_preds[w])
2084 if (!graph->implicit_preds[n])
2085 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2086 bitmap_ior_into (graph->implicit_preds[n],
2087 graph->implicit_preds[w]);
2089 if (graph->points_to[w])
2091 if (!graph->points_to[n])
2092 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2093 bitmap_ior_into (graph->points_to[n],
2094 graph->points_to[w]);
2097 bitmap_set_bit (si->deleted, n);
2099 else
2100 si->scc_stack.safe_push (n);
2103 /* Label pointer equivalences.
2105 This performs a value numbering of the constraint graph to
2106 discover which variables will always have the same points-to sets
2107 under the current set of constraints.
2109 The way it value numbers is to store the set of points-to bits
2110 generated by the constraints and graph edges. This is just used as a
2111 hash and equality comparison. The *actual set of points-to bits* is
2112 completely irrelevant, in that we don't care about being able to
2113 extract them later.
2115 The equality values (currently bitmaps) just have to satisfy a few
2116 constraints, the main ones being:
2117 1. The combining operation must be order independent.
2118 2. The end result of a given set of operations must be unique iff the
2119 combination of input values is unique
2120 3. Hashable. */
2122 static void
2123 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2125 unsigned int i, first_pred;
2126 bitmap_iterator bi;
2128 bitmap_set_bit (si->visited, n);
2130 /* Label and union our incoming edges's points to sets. */
2131 first_pred = -1U;
2132 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2134 unsigned int w = si->node_mapping[i];
2135 if (!bitmap_bit_p (si->visited, w))
2136 label_visit (graph, si, w);
2138 /* Skip unused edges */
2139 if (w == n || graph->pointer_label[w] == 0)
2140 continue;
2142 if (graph->points_to[w])
2144 if (!graph->points_to[n])
2146 if (first_pred == -1U)
2147 first_pred = w;
2148 else
2150 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2151 bitmap_ior (graph->points_to[n],
2152 graph->points_to[first_pred],
2153 graph->points_to[w]);
2156 else
2157 bitmap_ior_into (graph->points_to[n], graph->points_to[w]);
2161 /* Indirect nodes get fresh variables and a new pointer equiv class. */
2162 if (!bitmap_bit_p (graph->direct_nodes, n))
2164 if (!graph->points_to[n])
2166 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2167 if (first_pred != -1U)
2168 bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
2170 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2171 graph->pointer_label[n] = pointer_equiv_class++;
2172 equiv_class_label_t ecl;
2173 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
2174 graph->points_to[n]);
2175 ecl->equivalence_class = graph->pointer_label[n];
2176 return;
2179 /* If there was only a single non-empty predecessor the pointer equiv
2180 class is the same. */
2181 if (!graph->points_to[n])
2183 if (first_pred != -1U)
2185 graph->pointer_label[n] = graph->pointer_label[first_pred];
2186 graph->points_to[n] = graph->points_to[first_pred];
2188 return;
2191 if (!bitmap_empty_p (graph->points_to[n]))
2193 equiv_class_label_t ecl;
2194 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
2195 graph->points_to[n]);
2196 if (ecl->equivalence_class == 0)
2197 ecl->equivalence_class = pointer_equiv_class++;
2198 else
2200 BITMAP_FREE (graph->points_to[n]);
2201 graph->points_to[n] = ecl->labels;
2203 graph->pointer_label[n] = ecl->equivalence_class;
2207 /* Print the pred graph in dot format. */
2209 static void
2210 dump_pred_graph (struct scc_info *si, FILE *file)
2212 unsigned int i;
2214 /* Only print the graph if it has already been initialized: */
2215 if (!graph)
2216 return;
2218 /* Prints the header of the dot file: */
2219 fprintf (file, "strict digraph {\n");
2220 fprintf (file, " node [\n shape = box\n ]\n");
2221 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
2222 fprintf (file, "\n // List of nodes and complex constraints in "
2223 "the constraint graph:\n");
2225 /* The next lines print the nodes in the graph together with the
2226 complex constraints attached to them. */
2227 for (i = 1; i < graph->size; i++)
2229 if (i == FIRST_REF_NODE)
2230 continue;
2231 if (si->node_mapping[i] != i)
2232 continue;
2233 if (i < FIRST_REF_NODE)
2234 fprintf (file, "\"%s\"", get_varinfo (i)->name);
2235 else
2236 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
2237 if (graph->points_to[i]
2238 && !bitmap_empty_p (graph->points_to[i]))
2240 if (i < FIRST_REF_NODE)
2241 fprintf (file, "[label=\"%s = {", get_varinfo (i)->name);
2242 else
2243 fprintf (file, "[label=\"*%s = {",
2244 get_varinfo (i - FIRST_REF_NODE)->name);
2245 unsigned j;
2246 bitmap_iterator bi;
2247 EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi)
2248 fprintf (file, " %d", j);
2249 fprintf (file, " }\"]");
2251 fprintf (file, ";\n");
2254 /* Go over the edges. */
2255 fprintf (file, "\n // Edges in the constraint graph:\n");
2256 for (i = 1; i < graph->size; i++)
2258 unsigned j;
2259 bitmap_iterator bi;
2260 if (si->node_mapping[i] != i)
2261 continue;
2262 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
2264 unsigned from = si->node_mapping[j];
2265 if (from < FIRST_REF_NODE)
2266 fprintf (file, "\"%s\"", get_varinfo (from)->name);
2267 else
2268 fprintf (file, "\"*%s\"", get_varinfo (from - FIRST_REF_NODE)->name);
2269 fprintf (file, " -> ");
2270 if (i < FIRST_REF_NODE)
2271 fprintf (file, "\"%s\"", get_varinfo (i)->name);
2272 else
2273 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
2274 fprintf (file, ";\n");
2278 /* Prints the tail of the dot file. */
2279 fprintf (file, "}\n");
2282 /* Perform offline variable substitution, discovering equivalence
2283 classes, and eliminating non-pointer variables. */
2285 static struct scc_info *
2286 perform_var_substitution (constraint_graph_t graph)
2288 unsigned int i;
2289 unsigned int size = graph->size;
2290 scc_info *si = new scc_info (size);
2292 bitmap_obstack_initialize (&iteration_obstack);
2293 pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
2294 location_equiv_class_table
2295 = new hash_table<equiv_class_hasher> (511);
2296 pointer_equiv_class = 1;
2297 location_equiv_class = 1;
2299 /* Condense the nodes, which means to find SCC's, count incoming
2300 predecessors, and unite nodes in SCC's. */
2301 for (i = 1; i < FIRST_REF_NODE; i++)
2302 if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
2303 condense_visit (graph, si, si->node_mapping[i]);
2305 if (dump_file && (dump_flags & TDF_GRAPH))
2307 fprintf (dump_file, "\n\n// The constraint graph before var-substitution "
2308 "in dot format:\n");
2309 dump_pred_graph (si, dump_file);
2310 fprintf (dump_file, "\n\n");
2313 bitmap_clear (si->visited);
2314 /* Actually the label the nodes for pointer equivalences */
2315 for (i = 1; i < FIRST_REF_NODE; i++)
2316 if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
2317 label_visit (graph, si, si->node_mapping[i]);
2319 /* Calculate location equivalence labels. */
2320 for (i = 1; i < FIRST_REF_NODE; i++)
2322 bitmap pointed_by;
2323 bitmap_iterator bi;
2324 unsigned int j;
2326 if (!graph->pointed_by[i])
2327 continue;
2328 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2330 /* Translate the pointed-by mapping for pointer equivalence
2331 labels. */
2332 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2334 bitmap_set_bit (pointed_by,
2335 graph->pointer_label[si->node_mapping[j]]);
2337 /* The original pointed_by is now dead. */
2338 BITMAP_FREE (graph->pointed_by[i]);
2340 /* Look up the location equivalence label if one exists, or make
2341 one otherwise. */
2342 equiv_class_label_t ecl;
2343 ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
2344 if (ecl->equivalence_class == 0)
2345 ecl->equivalence_class = location_equiv_class++;
2346 else
2348 if (dump_file && (dump_flags & TDF_DETAILS))
2349 fprintf (dump_file, "Found location equivalence for node %s\n",
2350 get_varinfo (i)->name);
2351 BITMAP_FREE (pointed_by);
2353 graph->loc_label[i] = ecl->equivalence_class;
2357 if (dump_file && (dump_flags & TDF_DETAILS))
2358 for (i = 1; i < FIRST_REF_NODE; i++)
2360 unsigned j = si->node_mapping[i];
2361 if (j != i)
2363 fprintf (dump_file, "%s node id %d ",
2364 bitmap_bit_p (graph->direct_nodes, i)
2365 ? "Direct" : "Indirect", i);
2366 if (i < FIRST_REF_NODE)
2367 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
2368 else
2369 fprintf (dump_file, "\"*%s\"",
2370 get_varinfo (i - FIRST_REF_NODE)->name);
2371 fprintf (dump_file, " mapped to SCC leader node id %d ", j);
2372 if (j < FIRST_REF_NODE)
2373 fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name);
2374 else
2375 fprintf (dump_file, "\"*%s\"\n",
2376 get_varinfo (j - FIRST_REF_NODE)->name);
2378 else
2380 fprintf (dump_file,
2381 "Equivalence classes for %s node id %d ",
2382 bitmap_bit_p (graph->direct_nodes, i)
2383 ? "direct" : "indirect", i);
2384 if (i < FIRST_REF_NODE)
2385 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
2386 else
2387 fprintf (dump_file, "\"*%s\"",
2388 get_varinfo (i - FIRST_REF_NODE)->name);
2389 fprintf (dump_file,
2390 ": pointer %d, location %d\n",
2391 graph->pointer_label[i], graph->loc_label[i]);
2395 /* Quickly eliminate our non-pointer variables. */
2397 for (i = 1; i < FIRST_REF_NODE; i++)
2399 unsigned int node = si->node_mapping[i];
2401 if (graph->pointer_label[node] == 0)
2403 if (dump_file && (dump_flags & TDF_DETAILS))
2404 fprintf (dump_file,
2405 "%s is a non-pointer variable, eliminating edges.\n",
2406 get_varinfo (node)->name);
2407 stats.nonpointer_vars++;
2408 clear_edges_for_node (graph, node);
2412 return si;
2415 /* Free information that was only necessary for variable
2416 substitution. */
2418 static void
2419 free_var_substitution_info (struct scc_info *si)
2421 delete si;
2422 free (graph->pointer_label);
2423 free (graph->loc_label);
2424 free (graph->pointed_by);
2425 free (graph->points_to);
2426 free (graph->eq_rep);
2427 sbitmap_free (graph->direct_nodes);
2428 delete pointer_equiv_class_table;
2429 pointer_equiv_class_table = NULL;
2430 delete location_equiv_class_table;
2431 location_equiv_class_table = NULL;
2432 bitmap_obstack_release (&iteration_obstack);
2435 /* Return an existing node that is equivalent to NODE, which has
2436 equivalence class LABEL, if one exists. Return NODE otherwise. */
2438 static unsigned int
2439 find_equivalent_node (constraint_graph_t graph,
2440 unsigned int node, unsigned int label)
2442 /* If the address version of this variable is unused, we can
2443 substitute it for anything else with the same label.
2444 Otherwise, we know the pointers are equivalent, but not the
2445 locations, and we can unite them later. */
2447 if (!bitmap_bit_p (graph->address_taken, node))
2449 gcc_checking_assert (label < graph->size);
2451 if (graph->eq_rep[label] != -1)
2453 /* Unify the two variables since we know they are equivalent. */
2454 if (unite (graph->eq_rep[label], node))
2455 unify_nodes (graph, graph->eq_rep[label], node, false);
2456 return graph->eq_rep[label];
2458 else
2460 graph->eq_rep[label] = node;
2461 graph->pe_rep[label] = node;
2464 else
2466 gcc_checking_assert (label < graph->size);
2467 graph->pe[node] = label;
2468 if (graph->pe_rep[label] == -1)
2469 graph->pe_rep[label] = node;
2472 return node;
2475 /* Unite pointer equivalent but not location equivalent nodes in
2476 GRAPH. This may only be performed once variable substitution is
2477 finished. */
2479 static void
2480 unite_pointer_equivalences (constraint_graph_t graph)
2482 unsigned int i;
2484 /* Go through the pointer equivalences and unite them to their
2485 representative, if they aren't already. */
2486 for (i = 1; i < FIRST_REF_NODE; i++)
2488 unsigned int label = graph->pe[i];
2489 if (label)
2491 int label_rep = graph->pe_rep[label];
2493 if (label_rep == -1)
2494 continue;
2496 label_rep = find (label_rep);
2497 if (label_rep >= 0 && unite (label_rep, find (i)))
2498 unify_nodes (graph, label_rep, i, false);
2503 /* Move complex constraints to the GRAPH nodes they belong to. */
2505 static void
2506 move_complex_constraints (constraint_graph_t graph)
2508 int i;
2509 constraint_t c;
2511 FOR_EACH_VEC_ELT (constraints, i, c)
2513 if (c)
2515 struct constraint_expr lhs = c->lhs;
2516 struct constraint_expr rhs = c->rhs;
2518 if (lhs.type == DEREF)
2520 insert_into_complex (graph, lhs.var, c);
2522 else if (rhs.type == DEREF)
2524 if (!(get_varinfo (lhs.var)->is_special_var))
2525 insert_into_complex (graph, rhs.var, c);
2527 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2528 && (lhs.offset != 0 || rhs.offset != 0))
2530 insert_into_complex (graph, rhs.var, c);
2537 /* Optimize and rewrite complex constraints while performing
2538 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2539 result of perform_variable_substitution. */
2541 static void
2542 rewrite_constraints (constraint_graph_t graph,
2543 struct scc_info *si)
2545 int i;
2546 constraint_t c;
2548 if (flag_checking)
2550 for (unsigned int j = 0; j < graph->size; j++)
2551 gcc_assert (find (j) == j);
2554 FOR_EACH_VEC_ELT (constraints, i, c)
2556 struct constraint_expr lhs = c->lhs;
2557 struct constraint_expr rhs = c->rhs;
2558 unsigned int lhsvar = find (lhs.var);
2559 unsigned int rhsvar = find (rhs.var);
2560 unsigned int lhsnode, rhsnode;
2561 unsigned int lhslabel, rhslabel;
2563 lhsnode = si->node_mapping[lhsvar];
2564 rhsnode = si->node_mapping[rhsvar];
2565 lhslabel = graph->pointer_label[lhsnode];
2566 rhslabel = graph->pointer_label[rhsnode];
2568 /* See if it is really a non-pointer variable, and if so, ignore
2569 the constraint. */
2570 if (lhslabel == 0)
2572 if (dump_file && (dump_flags & TDF_DETAILS))
2575 fprintf (dump_file, "%s is a non-pointer variable, "
2576 "ignoring constraint:",
2577 get_varinfo (lhs.var)->name);
2578 dump_constraint (dump_file, c);
2579 fprintf (dump_file, "\n");
2581 constraints[i] = NULL;
2582 continue;
2585 if (rhslabel == 0)
2587 if (dump_file && (dump_flags & TDF_DETAILS))
2590 fprintf (dump_file, "%s is a non-pointer variable, "
2591 "ignoring constraint:",
2592 get_varinfo (rhs.var)->name);
2593 dump_constraint (dump_file, c);
2594 fprintf (dump_file, "\n");
2596 constraints[i] = NULL;
2597 continue;
2600 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2601 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2602 c->lhs.var = lhsvar;
2603 c->rhs.var = rhsvar;
2607 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2608 part of an SCC, false otherwise. */
2610 static bool
2611 eliminate_indirect_cycles (unsigned int node)
2613 if (graph->indirect_cycles[node] != -1
2614 && !bitmap_empty_p (get_varinfo (node)->solution))
2616 unsigned int i;
2617 auto_vec<unsigned> queue;
2618 int queuepos;
2619 unsigned int to = find (graph->indirect_cycles[node]);
2620 bitmap_iterator bi;
2622 /* We can't touch the solution set and call unify_nodes
2623 at the same time, because unify_nodes is going to do
2624 bitmap unions into it. */
2626 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2628 if (find (i) == i && i != to)
2630 if (unite (to, i))
2631 queue.safe_push (i);
2635 for (queuepos = 0;
2636 queue.iterate (queuepos, &i);
2637 queuepos++)
2639 unify_nodes (graph, to, i, true);
2641 return true;
2643 return false;
2646 /* Solve the constraint graph GRAPH using our worklist solver.
2647 This is based on the PW* family of solvers from the "Efficient Field
2648 Sensitive Pointer Analysis for C" paper.
2649 It works by iterating over all the graph nodes, processing the complex
2650 constraints and propagating the copy constraints, until everything stops
2651 changed. This corresponds to steps 6-8 in the solving list given above. */
2653 static void
2654 solve_graph (constraint_graph_t graph)
2656 unsigned int size = graph->size;
2657 unsigned int i;
2658 bitmap pts;
2660 changed = BITMAP_ALLOC (NULL);
2662 /* Mark all initial non-collapsed nodes as changed. */
2663 for (i = 1; i < size; i++)
2665 varinfo_t ivi = get_varinfo (i);
2666 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2667 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2668 || graph->complex[i].length () > 0))
2669 bitmap_set_bit (changed, i);
2672 /* Allocate a bitmap to be used to store the changed bits. */
2673 pts = BITMAP_ALLOC (&pta_obstack);
2675 while (!bitmap_empty_p (changed))
2677 unsigned int i;
2678 struct topo_info *ti = init_topo_info ();
2679 stats.iterations++;
2681 bitmap_obstack_initialize (&iteration_obstack);
2683 compute_topo_order (graph, ti);
2685 while (ti->topo_order.length () != 0)
2688 i = ti->topo_order.pop ();
2690 /* If this variable is not a representative, skip it. */
2691 if (find (i) != i)
2692 continue;
2694 /* In certain indirect cycle cases, we may merge this
2695 variable to another. */
2696 if (eliminate_indirect_cycles (i) && find (i) != i)
2697 continue;
2699 /* If the node has changed, we need to process the
2700 complex constraints and outgoing edges again. */
2701 if (bitmap_clear_bit (changed, i))
2703 unsigned int j;
2704 constraint_t c;
2705 bitmap solution;
2706 vec<constraint_t> complex = graph->complex[i];
2707 varinfo_t vi = get_varinfo (i);
2708 bool solution_empty;
2710 /* Compute the changed set of solution bits. If anything
2711 is in the solution just propagate that. */
2712 if (bitmap_bit_p (vi->solution, anything_id))
2714 /* If anything is also in the old solution there is
2715 nothing to do.
2716 ??? But we shouldn't ended up with "changed" set ... */
2717 if (vi->oldsolution
2718 && bitmap_bit_p (vi->oldsolution, anything_id))
2719 continue;
2720 bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2722 else if (vi->oldsolution)
2723 bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2724 else
2725 bitmap_copy (pts, vi->solution);
2727 if (bitmap_empty_p (pts))
2728 continue;
2730 if (vi->oldsolution)
2731 bitmap_ior_into (vi->oldsolution, pts);
2732 else
2734 vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2735 bitmap_copy (vi->oldsolution, pts);
2738 solution = vi->solution;
2739 solution_empty = bitmap_empty_p (solution);
2741 /* Process the complex constraints */
2742 bitmap expanded_pts = NULL;
2743 FOR_EACH_VEC_ELT (complex, j, c)
2745 /* XXX: This is going to unsort the constraints in
2746 some cases, which will occasionally add duplicate
2747 constraints during unification. This does not
2748 affect correctness. */
2749 c->lhs.var = find (c->lhs.var);
2750 c->rhs.var = find (c->rhs.var);
2752 /* The only complex constraint that can change our
2753 solution to non-empty, given an empty solution,
2754 is a constraint where the lhs side is receiving
2755 some set from elsewhere. */
2756 if (!solution_empty || c->lhs.type != DEREF)
2757 do_complex_constraint (graph, c, pts, &expanded_pts);
2759 BITMAP_FREE (expanded_pts);
2761 solution_empty = bitmap_empty_p (solution);
2763 if (!solution_empty)
2765 bitmap_iterator bi;
2766 unsigned eff_escaped_id = find (escaped_id);
2768 /* Propagate solution to all successors. */
2769 unsigned to_remove = ~0U;
2770 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2771 0, j, bi)
2773 if (to_remove != ~0U)
2775 bitmap_clear_bit (graph->succs[i], to_remove);
2776 to_remove = ~0U;
2778 unsigned int to = find (j);
2779 if (to != j)
2781 /* Update the succ graph, avoiding duplicate
2782 work. */
2783 to_remove = j;
2784 if (! bitmap_set_bit (graph->succs[i], to))
2785 continue;
2786 /* We eventually end up processing 'to' twice
2787 as it is undefined whether bitmap iteration
2788 iterates over bits set during iteration.
2789 Play safe instead of doing tricks. */
2791 /* Don't try to propagate to ourselves. */
2792 if (to == i)
2793 continue;
2795 bitmap tmp = get_varinfo (to)->solution;
2796 bool flag = false;
2798 /* If we propagate from ESCAPED use ESCAPED as
2799 placeholder. */
2800 if (i == eff_escaped_id)
2801 flag = bitmap_set_bit (tmp, escaped_id);
2802 else
2803 flag = bitmap_ior_into (tmp, pts);
2805 if (flag)
2806 bitmap_set_bit (changed, to);
2808 if (to_remove != ~0U)
2809 bitmap_clear_bit (graph->succs[i], to_remove);
2813 free_topo_info (ti);
2814 bitmap_obstack_release (&iteration_obstack);
2817 BITMAP_FREE (pts);
2818 BITMAP_FREE (changed);
2819 bitmap_obstack_release (&oldpta_obstack);
2822 /* Map from trees to variable infos. */
2823 static hash_map<tree, varinfo_t> *vi_for_tree;
2826 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2828 static void
2829 insert_vi_for_tree (tree t, varinfo_t vi)
2831 gcc_assert (vi);
2832 gcc_assert (!vi_for_tree->put (t, vi));
2835 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2836 exist in the map, return NULL, otherwise, return the varinfo we found. */
2838 static varinfo_t
2839 lookup_vi_for_tree (tree t)
2841 varinfo_t *slot = vi_for_tree->get (t);
2842 if (slot == NULL)
2843 return NULL;
2845 return *slot;
2848 /* Return a printable name for DECL */
2850 static const char *
2851 alias_get_name (tree decl)
2853 const char *res = "NULL";
2854 if (dump_file)
2856 char *temp = NULL;
2857 if (TREE_CODE (decl) == SSA_NAME)
2859 res = get_name (decl);
2860 temp = xasprintf ("%s_%u", res ? res : "", SSA_NAME_VERSION (decl));
2862 else if (HAS_DECL_ASSEMBLER_NAME_P (decl)
2863 && DECL_ASSEMBLER_NAME_SET_P (decl))
2864 res = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME_RAW (decl));
2865 else if (DECL_P (decl))
2867 res = get_name (decl);
2868 if (!res)
2869 temp = xasprintf ("D.%u", DECL_UID (decl));
2872 if (temp)
2874 res = ggc_strdup (temp);
2875 free (temp);
2879 return res;
2882 /* Find the variable id for tree T in the map.
2883 If T doesn't exist in the map, create an entry for it and return it. */
2885 static varinfo_t
2886 get_vi_for_tree (tree t)
2888 varinfo_t *slot = vi_for_tree->get (t);
2889 if (slot == NULL)
2891 unsigned int id = create_variable_info_for (t, alias_get_name (t), false);
2892 return get_varinfo (id);
2895 return *slot;
2898 /* Get a scalar constraint expression for a new temporary variable. */
2900 static struct constraint_expr
2901 new_scalar_tmp_constraint_exp (const char *name, bool add_id)
2903 struct constraint_expr tmp;
2904 varinfo_t vi;
2906 vi = new_var_info (NULL_TREE, name, add_id);
2907 vi->offset = 0;
2908 vi->size = -1;
2909 vi->fullsize = -1;
2910 vi->is_full_var = 1;
2911 vi->is_reg_var = 1;
2913 tmp.var = vi->id;
2914 tmp.type = SCALAR;
2915 tmp.offset = 0;
2917 return tmp;
2920 /* Get a constraint expression vector from an SSA_VAR_P node.
2921 If address_p is true, the result will be taken its address of. */
2923 static void
2924 get_constraint_for_ssa_var (tree t, vec<ce_s> *results, bool address_p)
2926 struct constraint_expr cexpr;
2927 varinfo_t vi;
2929 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2930 gcc_assert (TREE_CODE (t) == SSA_NAME || DECL_P (t));
2932 if (TREE_CODE (t) == SSA_NAME
2933 && SSA_NAME_IS_DEFAULT_DEF (t))
2935 /* For parameters, get at the points-to set for the actual parm
2936 decl. */
2937 if (TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2938 || TREE_CODE (SSA_NAME_VAR (t)) == RESULT_DECL)
2940 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2941 return;
2943 /* For undefined SSA names return nothing. */
2944 else if (!ssa_defined_default_def_p (t))
2946 cexpr.var = nothing_id;
2947 cexpr.type = SCALAR;
2948 cexpr.offset = 0;
2949 results->safe_push (cexpr);
2950 return;
2954 /* For global variables resort to the alias target. */
2955 if (VAR_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
2957 varpool_node *node = varpool_node::get (t);
2958 if (node && node->alias && node->analyzed)
2960 node = node->ultimate_alias_target ();
2961 /* Canonicalize the PT uid of all aliases to the ultimate target.
2962 ??? Hopefully the set of aliases can't change in a way that
2963 changes the ultimate alias target. */
2964 gcc_assert ((! DECL_PT_UID_SET_P (node->decl)
2965 || DECL_PT_UID (node->decl) == DECL_UID (node->decl))
2966 && (! DECL_PT_UID_SET_P (t)
2967 || DECL_PT_UID (t) == DECL_UID (node->decl)));
2968 DECL_PT_UID (t) = DECL_UID (node->decl);
2969 t = node->decl;
2972 /* If this is decl may bind to NULL note that. */
2973 if (address_p
2974 && (! node || ! node->nonzero_address ()))
2976 cexpr.var = nothing_id;
2977 cexpr.type = SCALAR;
2978 cexpr.offset = 0;
2979 results->safe_push (cexpr);
2983 vi = get_vi_for_tree (t);
2984 cexpr.var = vi->id;
2985 cexpr.type = SCALAR;
2986 cexpr.offset = 0;
2988 /* If we are not taking the address of the constraint expr, add all
2989 sub-fiels of the variable as well. */
2990 if (!address_p
2991 && !vi->is_full_var)
2993 for (; vi; vi = vi_next (vi))
2995 cexpr.var = vi->id;
2996 results->safe_push (cexpr);
2998 return;
3001 results->safe_push (cexpr);
3004 /* Process constraint T, performing various simplifications and then
3005 adding it to our list of overall constraints. */
3007 static void
3008 process_constraint (constraint_t t)
3010 struct constraint_expr rhs = t->rhs;
3011 struct constraint_expr lhs = t->lhs;
3013 gcc_assert (rhs.var < varmap.length ());
3014 gcc_assert (lhs.var < varmap.length ());
3016 /* If we didn't get any useful constraint from the lhs we get
3017 &ANYTHING as fallback from get_constraint_for. Deal with
3018 it here by turning it into *ANYTHING. */
3019 if (lhs.type == ADDRESSOF
3020 && lhs.var == anything_id)
3021 lhs.type = DEREF;
3023 /* ADDRESSOF on the lhs is invalid. */
3024 gcc_assert (lhs.type != ADDRESSOF);
3026 /* We shouldn't add constraints from things that cannot have pointers.
3027 It's not completely trivial to avoid in the callers, so do it here. */
3028 if (rhs.type != ADDRESSOF
3029 && !get_varinfo (rhs.var)->may_have_pointers)
3030 return;
3032 /* Likewise adding to the solution of a non-pointer var isn't useful. */
3033 if (!get_varinfo (lhs.var)->may_have_pointers)
3034 return;
3036 /* This can happen in our IR with things like n->a = *p */
3037 if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
3039 /* Split into tmp = *rhs, *lhs = tmp */
3040 struct constraint_expr tmplhs;
3041 tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp", true);
3042 process_constraint (new_constraint (tmplhs, rhs));
3043 process_constraint (new_constraint (lhs, tmplhs));
3045 else if ((rhs.type != SCALAR || rhs.offset != 0) && lhs.type == DEREF)
3047 /* Split into tmp = &rhs, *lhs = tmp */
3048 struct constraint_expr tmplhs;
3049 tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp", true);
3050 process_constraint (new_constraint (tmplhs, rhs));
3051 process_constraint (new_constraint (lhs, tmplhs));
3053 else
3055 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
3056 constraints.safe_push (t);
3061 /* Return the position, in bits, of FIELD_DECL from the beginning of its
3062 structure. */
3064 static HOST_WIDE_INT
3065 bitpos_of_field (const tree fdecl)
3067 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl))
3068 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl)))
3069 return -1;
3071 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl)) * BITS_PER_UNIT
3072 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl)));
3076 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
3077 resulting constraint expressions in *RESULTS. */
3079 static void
3080 get_constraint_for_ptr_offset (tree ptr, tree offset,
3081 vec<ce_s> *results)
3083 struct constraint_expr c;
3084 unsigned int j, n;
3085 HOST_WIDE_INT rhsoffset;
3087 /* If we do not do field-sensitive PTA adding offsets to pointers
3088 does not change the points-to solution. */
3089 if (!use_field_sensitive)
3091 get_constraint_for_rhs (ptr, results);
3092 return;
3095 /* If the offset is not a non-negative integer constant that fits
3096 in a HOST_WIDE_INT, we have to fall back to a conservative
3097 solution which includes all sub-fields of all pointed-to
3098 variables of ptr. */
3099 if (offset == NULL_TREE
3100 || TREE_CODE (offset) != INTEGER_CST)
3101 rhsoffset = UNKNOWN_OFFSET;
3102 else
3104 /* Sign-extend the offset. */
3105 offset_int soffset = offset_int::from (wi::to_wide (offset), SIGNED);
3106 if (!wi::fits_shwi_p (soffset))
3107 rhsoffset = UNKNOWN_OFFSET;
3108 else
3110 /* Make sure the bit-offset also fits. */
3111 HOST_WIDE_INT rhsunitoffset = soffset.to_shwi ();
3112 rhsoffset = rhsunitoffset * (unsigned HOST_WIDE_INT) BITS_PER_UNIT;
3113 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
3114 rhsoffset = UNKNOWN_OFFSET;
3118 get_constraint_for_rhs (ptr, results);
3119 if (rhsoffset == 0)
3120 return;
3122 /* As we are eventually appending to the solution do not use
3123 vec::iterate here. */
3124 n = results->length ();
3125 for (j = 0; j < n; j++)
3127 varinfo_t curr;
3128 c = (*results)[j];
3129 curr = get_varinfo (c.var);
3131 if (c.type == ADDRESSOF
3132 /* If this varinfo represents a full variable just use it. */
3133 && curr->is_full_var)
3135 else if (c.type == ADDRESSOF
3136 /* If we do not know the offset add all subfields. */
3137 && rhsoffset == UNKNOWN_OFFSET)
3139 varinfo_t temp = get_varinfo (curr->head);
3142 struct constraint_expr c2;
3143 c2.var = temp->id;
3144 c2.type = ADDRESSOF;
3145 c2.offset = 0;
3146 if (c2.var != c.var)
3147 results->safe_push (c2);
3148 temp = vi_next (temp);
3150 while (temp);
3152 else if (c.type == ADDRESSOF)
3154 varinfo_t temp;
3155 unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
3157 /* If curr->offset + rhsoffset is less than zero adjust it. */
3158 if (rhsoffset < 0
3159 && curr->offset < offset)
3160 offset = 0;
3162 /* We have to include all fields that overlap the current
3163 field shifted by rhsoffset. And we include at least
3164 the last or the first field of the variable to represent
3165 reachability of off-bound addresses, in particular &object + 1,
3166 conservatively correct. */
3167 temp = first_or_preceding_vi_for_offset (curr, offset);
3168 c.var = temp->id;
3169 c.offset = 0;
3170 temp = vi_next (temp);
3171 while (temp
3172 && temp->offset < offset + curr->size)
3174 struct constraint_expr c2;
3175 c2.var = temp->id;
3176 c2.type = ADDRESSOF;
3177 c2.offset = 0;
3178 results->safe_push (c2);
3179 temp = vi_next (temp);
3182 else if (c.type == SCALAR)
3184 gcc_assert (c.offset == 0);
3185 c.offset = rhsoffset;
3187 else
3188 /* We shouldn't get any DEREFs here. */
3189 gcc_unreachable ();
3191 (*results)[j] = c;
3196 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3197 If address_p is true the result will be taken its address of.
3198 If lhs_p is true then the constraint expression is assumed to be used
3199 as the lhs. */
3201 static void
3202 get_constraint_for_component_ref (tree t, vec<ce_s> *results,
3203 bool address_p, bool lhs_p)
3205 tree orig_t = t;
3206 poly_int64 bitsize = -1;
3207 poly_int64 bitmaxsize = -1;
3208 poly_int64 bitpos;
3209 bool reverse;
3210 tree forzero;
3212 /* Some people like to do cute things like take the address of
3213 &0->a.b */
3214 forzero = t;
3215 while (handled_component_p (forzero)
3216 || INDIRECT_REF_P (forzero)
3217 || TREE_CODE (forzero) == MEM_REF)
3218 forzero = TREE_OPERAND (forzero, 0);
3220 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
3222 struct constraint_expr temp;
3224 temp.offset = 0;
3225 temp.var = integer_id;
3226 temp.type = SCALAR;
3227 results->safe_push (temp);
3228 return;
3231 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize, &reverse);
3233 /* We can end up here for component references on a
3234 VIEW_CONVERT_EXPR <>(&foobar) or things like a
3235 BIT_FIELD_REF <&MEM[(void *)&b + 4B], ...>. So for
3236 symbolic constants simply give up. */
3237 if (TREE_CODE (t) == ADDR_EXPR)
3239 constraint_expr result;
3240 result.type = SCALAR;
3241 result.var = anything_id;
3242 result.offset = 0;
3243 results->safe_push (result);
3244 return;
3247 /* Pretend to take the address of the base, we'll take care of
3248 adding the required subset of sub-fields below. */
3249 get_constraint_for_1 (t, results, true, lhs_p);
3250 /* Strip off nothing_id. */
3251 if (results->length () == 2)
3253 gcc_assert ((*results)[0].var == nothing_id);
3254 results->unordered_remove (0);
3256 gcc_assert (results->length () == 1);
3257 struct constraint_expr &result = results->last ();
3259 if (result.type == SCALAR
3260 && get_varinfo (result.var)->is_full_var)
3261 /* For single-field vars do not bother about the offset. */
3262 result.offset = 0;
3263 else if (result.type == SCALAR)
3265 /* In languages like C, you can access one past the end of an
3266 array. You aren't allowed to dereference it, so we can
3267 ignore this constraint. When we handle pointer subtraction,
3268 we may have to do something cute here. */
3270 if (maybe_lt (poly_uint64 (bitpos), get_varinfo (result.var)->fullsize)
3271 && maybe_ne (bitmaxsize, 0))
3273 /* It's also not true that the constraint will actually start at the
3274 right offset, it may start in some padding. We only care about
3275 setting the constraint to the first actual field it touches, so
3276 walk to find it. */
3277 struct constraint_expr cexpr = result;
3278 varinfo_t curr;
3279 results->pop ();
3280 cexpr.offset = 0;
3281 for (curr = get_varinfo (cexpr.var); curr; curr = vi_next (curr))
3283 if (ranges_maybe_overlap_p (poly_int64 (curr->offset),
3284 curr->size, bitpos, bitmaxsize))
3286 cexpr.var = curr->id;
3287 results->safe_push (cexpr);
3288 if (address_p)
3289 break;
3292 /* If we are going to take the address of this field then
3293 to be able to compute reachability correctly add at least
3294 the last field of the variable. */
3295 if (address_p && results->length () == 0)
3297 curr = get_varinfo (cexpr.var);
3298 while (curr->next != 0)
3299 curr = vi_next (curr);
3300 cexpr.var = curr->id;
3301 results->safe_push (cexpr);
3303 else if (results->length () == 0)
3304 /* Assert that we found *some* field there. The user couldn't be
3305 accessing *only* padding. */
3306 /* Still the user could access one past the end of an array
3307 embedded in a struct resulting in accessing *only* padding. */
3308 /* Or accessing only padding via type-punning to a type
3309 that has a filed just in padding space. */
3311 cexpr.type = SCALAR;
3312 cexpr.var = anything_id;
3313 cexpr.offset = 0;
3314 results->safe_push (cexpr);
3317 else if (known_eq (bitmaxsize, 0))
3319 if (dump_file && (dump_flags & TDF_DETAILS))
3320 fprintf (dump_file, "Access to zero-sized part of variable, "
3321 "ignoring\n");
3323 else
3324 if (dump_file && (dump_flags & TDF_DETAILS))
3325 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3327 else if (result.type == DEREF)
3329 /* If we do not know exactly where the access goes say so. Note
3330 that only for non-structure accesses we know that we access
3331 at most one subfiled of any variable. */
3332 HOST_WIDE_INT const_bitpos;
3333 if (!bitpos.is_constant (&const_bitpos)
3334 || const_bitpos == -1
3335 || maybe_ne (bitsize, bitmaxsize)
3336 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t))
3337 || result.offset == UNKNOWN_OFFSET)
3338 result.offset = UNKNOWN_OFFSET;
3339 else
3340 result.offset += const_bitpos;
3342 else if (result.type == ADDRESSOF)
3344 /* We can end up here for component references on constants like
3345 VIEW_CONVERT_EXPR <>({ 0, 1, 2, 3 })[i]. */
3346 result.type = SCALAR;
3347 result.var = anything_id;
3348 result.offset = 0;
3350 else
3351 gcc_unreachable ();
3355 /* Dereference the constraint expression CONS, and return the result.
3356 DEREF (ADDRESSOF) = SCALAR
3357 DEREF (SCALAR) = DEREF
3358 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3359 This is needed so that we can handle dereferencing DEREF constraints. */
3361 static void
3362 do_deref (vec<ce_s> *constraints)
3364 struct constraint_expr *c;
3365 unsigned int i = 0;
3367 FOR_EACH_VEC_ELT (*constraints, i, c)
3369 if (c->type == SCALAR)
3370 c->type = DEREF;
3371 else if (c->type == ADDRESSOF)
3372 c->type = SCALAR;
3373 else if (c->type == DEREF)
3375 struct constraint_expr tmplhs;
3376 tmplhs = new_scalar_tmp_constraint_exp ("dereftmp", true);
3377 process_constraint (new_constraint (tmplhs, *c));
3378 c->var = tmplhs.var;
3380 else
3381 gcc_unreachable ();
3385 /* Given a tree T, return the constraint expression for taking the
3386 address of it. */
3388 static void
3389 get_constraint_for_address_of (tree t, vec<ce_s> *results)
3391 struct constraint_expr *c;
3392 unsigned int i;
3394 get_constraint_for_1 (t, results, true, true);
3396 FOR_EACH_VEC_ELT (*results, i, c)
3398 if (c->type == DEREF)
3399 c->type = SCALAR;
3400 else
3401 c->type = ADDRESSOF;
3405 /* Given a tree T, return the constraint expression for it. */
3407 static void
3408 get_constraint_for_1 (tree t, vec<ce_s> *results, bool address_p,
3409 bool lhs_p)
3411 struct constraint_expr temp;
3413 /* x = integer is all glommed to a single variable, which doesn't
3414 point to anything by itself. That is, of course, unless it is an
3415 integer constant being treated as a pointer, in which case, we
3416 will return that this is really the addressof anything. This
3417 happens below, since it will fall into the default case. The only
3418 case we know something about an integer treated like a pointer is
3419 when it is the NULL pointer, and then we just say it points to
3420 NULL.
3422 Do not do that if -fno-delete-null-pointer-checks though, because
3423 in that case *NULL does not fail, so it _should_ alias *anything.
3424 It is not worth adding a new option or renaming the existing one,
3425 since this case is relatively obscure. */
3426 if ((TREE_CODE (t) == INTEGER_CST
3427 && integer_zerop (t))
3428 /* The only valid CONSTRUCTORs in gimple with pointer typed
3429 elements are zero-initializer. But in IPA mode we also
3430 process global initializers, so verify at least. */
3431 || (TREE_CODE (t) == CONSTRUCTOR
3432 && CONSTRUCTOR_NELTS (t) == 0))
3434 if (flag_delete_null_pointer_checks)
3435 temp.var = nothing_id;
3436 else
3437 temp.var = nonlocal_id;
3438 temp.type = ADDRESSOF;
3439 temp.offset = 0;
3440 results->safe_push (temp);
3441 return;
3444 /* String constants are read-only, ideally we'd have a CONST_DECL
3445 for those. */
3446 if (TREE_CODE (t) == STRING_CST)
3448 temp.var = string_id;
3449 temp.type = SCALAR;
3450 temp.offset = 0;
3451 results->safe_push (temp);
3452 return;
3455 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3457 case tcc_expression:
3459 switch (TREE_CODE (t))
3461 case ADDR_EXPR:
3462 get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3463 return;
3464 default:;
3466 break;
3468 case tcc_reference:
3470 switch (TREE_CODE (t))
3472 case MEM_REF:
3474 struct constraint_expr cs;
3475 varinfo_t vi, curr;
3476 get_constraint_for_ptr_offset (TREE_OPERAND (t, 0),
3477 TREE_OPERAND (t, 1), results);
3478 do_deref (results);
3480 /* If we are not taking the address then make sure to process
3481 all subvariables we might access. */
3482 if (address_p)
3483 return;
3485 cs = results->last ();
3486 if (cs.type == DEREF
3487 && type_can_have_subvars (TREE_TYPE (t)))
3489 /* For dereferences this means we have to defer it
3490 to solving time. */
3491 results->last ().offset = UNKNOWN_OFFSET;
3492 return;
3494 if (cs.type != SCALAR)
3495 return;
3497 vi = get_varinfo (cs.var);
3498 curr = vi_next (vi);
3499 if (!vi->is_full_var
3500 && curr)
3502 unsigned HOST_WIDE_INT size;
3503 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t))))
3504 size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t)));
3505 else
3506 size = -1;
3507 for (; curr; curr = vi_next (curr))
3509 if (curr->offset - vi->offset < size)
3511 cs.var = curr->id;
3512 results->safe_push (cs);
3514 else
3515 break;
3518 return;
3520 case ARRAY_REF:
3521 case ARRAY_RANGE_REF:
3522 case COMPONENT_REF:
3523 case IMAGPART_EXPR:
3524 case REALPART_EXPR:
3525 case BIT_FIELD_REF:
3526 get_constraint_for_component_ref (t, results, address_p, lhs_p);
3527 return;
3528 case VIEW_CONVERT_EXPR:
3529 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p,
3530 lhs_p);
3531 return;
3532 /* We are missing handling for TARGET_MEM_REF here. */
3533 default:;
3535 break;
3537 case tcc_exceptional:
3539 switch (TREE_CODE (t))
3541 case SSA_NAME:
3543 get_constraint_for_ssa_var (t, results, address_p);
3544 return;
3546 case CONSTRUCTOR:
3548 unsigned int i;
3549 tree val;
3550 auto_vec<ce_s> tmp;
3551 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t), i, val)
3553 struct constraint_expr *rhsp;
3554 unsigned j;
3555 get_constraint_for_1 (val, &tmp, address_p, lhs_p);
3556 FOR_EACH_VEC_ELT (tmp, j, rhsp)
3557 results->safe_push (*rhsp);
3558 tmp.truncate (0);
3560 /* We do not know whether the constructor was complete,
3561 so technically we have to add &NOTHING or &ANYTHING
3562 like we do for an empty constructor as well. */
3563 return;
3565 default:;
3567 break;
3569 case tcc_declaration:
3571 get_constraint_for_ssa_var (t, results, address_p);
3572 return;
3574 case tcc_constant:
3576 /* We cannot refer to automatic variables through constants. */
3577 temp.type = ADDRESSOF;
3578 temp.var = nonlocal_id;
3579 temp.offset = 0;
3580 results->safe_push (temp);
3581 return;
3583 default:;
3586 /* The default fallback is a constraint from anything. */
3587 temp.type = ADDRESSOF;
3588 temp.var = anything_id;
3589 temp.offset = 0;
3590 results->safe_push (temp);
3593 /* Given a gimple tree T, return the constraint expression vector for it. */
3595 static void
3596 get_constraint_for (tree t, vec<ce_s> *results)
3598 gcc_assert (results->length () == 0);
3600 get_constraint_for_1 (t, results, false, true);
3603 /* Given a gimple tree T, return the constraint expression vector for it
3604 to be used as the rhs of a constraint. */
3606 static void
3607 get_constraint_for_rhs (tree t, vec<ce_s> *results)
3609 gcc_assert (results->length () == 0);
3611 get_constraint_for_1 (t, results, false, false);
3615 /* Efficiently generates constraints from all entries in *RHSC to all
3616 entries in *LHSC. */
3618 static void
3619 process_all_all_constraints (vec<ce_s> lhsc,
3620 vec<ce_s> rhsc)
3622 struct constraint_expr *lhsp, *rhsp;
3623 unsigned i, j;
3625 if (lhsc.length () <= 1 || rhsc.length () <= 1)
3627 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
3628 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
3629 process_constraint (new_constraint (*lhsp, *rhsp));
3631 else
3633 struct constraint_expr tmp;
3634 tmp = new_scalar_tmp_constraint_exp ("allalltmp", true);
3635 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
3636 process_constraint (new_constraint (tmp, *rhsp));
3637 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
3638 process_constraint (new_constraint (*lhsp, tmp));
3642 /* Handle aggregate copies by expanding into copies of the respective
3643 fields of the structures. */
3645 static void
3646 do_structure_copy (tree lhsop, tree rhsop)
3648 struct constraint_expr *lhsp, *rhsp;
3649 auto_vec<ce_s> lhsc;
3650 auto_vec<ce_s> rhsc;
3651 unsigned j;
3653 get_constraint_for (lhsop, &lhsc);
3654 get_constraint_for_rhs (rhsop, &rhsc);
3655 lhsp = &lhsc[0];
3656 rhsp = &rhsc[0];
3657 if (lhsp->type == DEREF
3658 || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3659 || rhsp->type == DEREF)
3661 if (lhsp->type == DEREF)
3663 gcc_assert (lhsc.length () == 1);
3664 lhsp->offset = UNKNOWN_OFFSET;
3666 if (rhsp->type == DEREF)
3668 gcc_assert (rhsc.length () == 1);
3669 rhsp->offset = UNKNOWN_OFFSET;
3671 process_all_all_constraints (lhsc, rhsc);
3673 else if (lhsp->type == SCALAR
3674 && (rhsp->type == SCALAR
3675 || rhsp->type == ADDRESSOF))
3677 HOST_WIDE_INT lhssize, lhsoffset;
3678 HOST_WIDE_INT rhssize, rhsoffset;
3679 bool reverse;
3680 unsigned k = 0;
3681 if (!get_ref_base_and_extent_hwi (lhsop, &lhsoffset, &lhssize, &reverse)
3682 || !get_ref_base_and_extent_hwi (rhsop, &rhsoffset, &rhssize,
3683 &reverse))
3685 process_all_all_constraints (lhsc, rhsc);
3686 return;
3688 for (j = 0; lhsc.iterate (j, &lhsp);)
3690 varinfo_t lhsv, rhsv;
3691 rhsp = &rhsc[k];
3692 lhsv = get_varinfo (lhsp->var);
3693 rhsv = get_varinfo (rhsp->var);
3694 if (lhsv->may_have_pointers
3695 && (lhsv->is_full_var
3696 || rhsv->is_full_var
3697 || ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3698 rhsv->offset + lhsoffset, rhsv->size)))
3699 process_constraint (new_constraint (*lhsp, *rhsp));
3700 if (!rhsv->is_full_var
3701 && (lhsv->is_full_var
3702 || (lhsv->offset + rhsoffset + lhsv->size
3703 > rhsv->offset + lhsoffset + rhsv->size)))
3705 ++k;
3706 if (k >= rhsc.length ())
3707 break;
3709 else
3710 ++j;
3713 else
3714 gcc_unreachable ();
3717 /* Create constraints ID = { rhsc }. */
3719 static void
3720 make_constraints_to (unsigned id, vec<ce_s> rhsc)
3722 struct constraint_expr *c;
3723 struct constraint_expr includes;
3724 unsigned int j;
3726 includes.var = id;
3727 includes.offset = 0;
3728 includes.type = SCALAR;
3730 FOR_EACH_VEC_ELT (rhsc, j, c)
3731 process_constraint (new_constraint (includes, *c));
3734 /* Create a constraint ID = OP. */
3736 static void
3737 make_constraint_to (unsigned id, tree op)
3739 auto_vec<ce_s> rhsc;
3740 get_constraint_for_rhs (op, &rhsc);
3741 make_constraints_to (id, rhsc);
3744 /* Create a constraint ID = &FROM. */
3746 static void
3747 make_constraint_from (varinfo_t vi, int from)
3749 struct constraint_expr lhs, rhs;
3751 lhs.var = vi->id;
3752 lhs.offset = 0;
3753 lhs.type = SCALAR;
3755 rhs.var = from;
3756 rhs.offset = 0;
3757 rhs.type = ADDRESSOF;
3758 process_constraint (new_constraint (lhs, rhs));
3761 /* Create a constraint ID = FROM. */
3763 static void
3764 make_copy_constraint (varinfo_t vi, int from)
3766 struct constraint_expr lhs, rhs;
3768 lhs.var = vi->id;
3769 lhs.offset = 0;
3770 lhs.type = SCALAR;
3772 rhs.var = from;
3773 rhs.offset = 0;
3774 rhs.type = SCALAR;
3775 process_constraint (new_constraint (lhs, rhs));
3778 /* Make constraints necessary to make OP escape. */
3780 static void
3781 make_escape_constraint (tree op)
3783 make_constraint_to (escaped_id, op);
3786 /* Add constraints to that the solution of VI is transitively closed. */
3788 static void
3789 make_transitive_closure_constraints (varinfo_t vi)
3791 struct constraint_expr lhs, rhs;
3793 /* VAR = *(VAR + UNKNOWN); */
3794 lhs.type = SCALAR;
3795 lhs.var = vi->id;
3796 lhs.offset = 0;
3797 rhs.type = DEREF;
3798 rhs.var = vi->id;
3799 rhs.offset = UNKNOWN_OFFSET;
3800 process_constraint (new_constraint (lhs, rhs));
3803 /* Add constraints to that the solution of VI has all subvariables added. */
3805 static void
3806 make_any_offset_constraints (varinfo_t vi)
3808 struct constraint_expr lhs, rhs;
3810 /* VAR = VAR + UNKNOWN; */
3811 lhs.type = SCALAR;
3812 lhs.var = vi->id;
3813 lhs.offset = 0;
3814 rhs.type = SCALAR;
3815 rhs.var = vi->id;
3816 rhs.offset = UNKNOWN_OFFSET;
3817 process_constraint (new_constraint (lhs, rhs));
3820 /* Temporary storage for fake var decls. */
3821 struct obstack fake_var_decl_obstack;
3823 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3825 static tree
3826 build_fake_var_decl (tree type)
3828 tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
3829 memset (decl, 0, sizeof (struct tree_var_decl));
3830 TREE_SET_CODE (decl, VAR_DECL);
3831 TREE_TYPE (decl) = type;
3832 DECL_UID (decl) = allocate_decl_uid ();
3833 SET_DECL_PT_UID (decl, -1);
3834 layout_decl (decl, 0);
3835 return decl;
3838 /* Create a new artificial heap variable with NAME.
3839 Return the created variable. */
3841 static varinfo_t
3842 make_heapvar (const char *name, bool add_id)
3844 varinfo_t vi;
3845 tree heapvar;
3847 heapvar = build_fake_var_decl (ptr_type_node);
3848 DECL_EXTERNAL (heapvar) = 1;
3850 vi = new_var_info (heapvar, name, add_id);
3851 vi->is_artificial_var = true;
3852 vi->is_heap_var = true;
3853 vi->is_unknown_size_var = true;
3854 vi->offset = 0;
3855 vi->fullsize = ~0;
3856 vi->size = ~0;
3857 vi->is_full_var = true;
3858 insert_vi_for_tree (heapvar, vi);
3860 return vi;
3863 /* Create a new artificial heap variable with NAME and make a
3864 constraint from it to LHS. Set flags according to a tag used
3865 for tracking restrict pointers. */
3867 static varinfo_t
3868 make_constraint_from_restrict (varinfo_t lhs, const char *name, bool add_id)
3870 varinfo_t vi = make_heapvar (name, add_id);
3871 vi->is_restrict_var = 1;
3872 vi->is_global_var = 1;
3873 vi->may_have_pointers = 1;
3874 make_constraint_from (lhs, vi->id);
3875 return vi;
3878 /* Create a new artificial heap variable with NAME and make a
3879 constraint from it to LHS. Set flags according to a tag used
3880 for tracking restrict pointers and make the artificial heap
3881 point to global memory. */
3883 static varinfo_t
3884 make_constraint_from_global_restrict (varinfo_t lhs, const char *name,
3885 bool add_id)
3887 varinfo_t vi = make_constraint_from_restrict (lhs, name, add_id);
3888 make_copy_constraint (vi, nonlocal_id);
3889 return vi;
3892 /* In IPA mode there are varinfos for different aspects of reach
3893 function designator. One for the points-to set of the return
3894 value, one for the variables that are clobbered by the function,
3895 one for its uses and one for each parameter (including a single
3896 glob for remaining variadic arguments). */
3898 enum { fi_clobbers = 1, fi_uses = 2,
3899 fi_static_chain = 3, fi_result = 4, fi_parm_base = 5 };
3901 /* Get a constraint for the requested part of a function designator FI
3902 when operating in IPA mode. */
3904 static struct constraint_expr
3905 get_function_part_constraint (varinfo_t fi, unsigned part)
3907 struct constraint_expr c;
3909 gcc_assert (in_ipa_mode);
3911 if (fi->id == anything_id)
3913 /* ??? We probably should have a ANYFN special variable. */
3914 c.var = anything_id;
3915 c.offset = 0;
3916 c.type = SCALAR;
3918 else if (fi->decl && TREE_CODE (fi->decl) == FUNCTION_DECL)
3920 varinfo_t ai = first_vi_for_offset (fi, part);
3921 if (ai)
3922 c.var = ai->id;
3923 else
3924 c.var = anything_id;
3925 c.offset = 0;
3926 c.type = SCALAR;
3928 else
3930 c.var = fi->id;
3931 c.offset = part;
3932 c.type = DEREF;
3935 return c;
3938 /* For non-IPA mode, generate constraints necessary for a call on the
3939 RHS. */
3941 static void
3942 handle_rhs_call (gcall *stmt, vec<ce_s> *results)
3944 struct constraint_expr rhsc;
3945 unsigned i;
3946 bool returns_uses = false;
3948 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3950 tree arg = gimple_call_arg (stmt, i);
3951 int flags = gimple_call_arg_flags (stmt, i);
3953 /* If the argument is not used we can ignore it. */
3954 if (flags & EAF_UNUSED)
3955 continue;
3957 /* As we compute ESCAPED context-insensitive we do not gain
3958 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3959 set. The argument would still get clobbered through the
3960 escape solution. */
3961 if ((flags & EAF_NOCLOBBER)
3962 && (flags & EAF_NOESCAPE))
3964 varinfo_t uses = get_call_use_vi (stmt);
3965 varinfo_t tem = new_var_info (NULL_TREE, "callarg", true);
3966 tem->is_reg_var = true;
3967 make_constraint_to (tem->id, arg);
3968 make_any_offset_constraints (tem);
3969 if (!(flags & EAF_DIRECT))
3970 make_transitive_closure_constraints (tem);
3971 make_copy_constraint (uses, tem->id);
3972 returns_uses = true;
3974 else if (flags & EAF_NOESCAPE)
3976 struct constraint_expr lhs, rhs;
3977 varinfo_t uses = get_call_use_vi (stmt);
3978 varinfo_t clobbers = get_call_clobber_vi (stmt);
3979 varinfo_t tem = new_var_info (NULL_TREE, "callarg", true);
3980 tem->is_reg_var = true;
3981 make_constraint_to (tem->id, arg);
3982 make_any_offset_constraints (tem);
3983 if (!(flags & EAF_DIRECT))
3984 make_transitive_closure_constraints (tem);
3985 make_copy_constraint (uses, tem->id);
3986 make_copy_constraint (clobbers, tem->id);
3987 /* Add *tem = nonlocal, do not add *tem = callused as
3988 EAF_NOESCAPE parameters do not escape to other parameters
3989 and all other uses appear in NONLOCAL as well. */
3990 lhs.type = DEREF;
3991 lhs.var = tem->id;
3992 lhs.offset = 0;
3993 rhs.type = SCALAR;
3994 rhs.var = nonlocal_id;
3995 rhs.offset = 0;
3996 process_constraint (new_constraint (lhs, rhs));
3997 returns_uses = true;
3999 else
4000 make_escape_constraint (arg);
4003 /* If we added to the calls uses solution make sure we account for
4004 pointers to it to be returned. */
4005 if (returns_uses)
4007 rhsc.var = get_call_use_vi (stmt)->id;
4008 rhsc.offset = UNKNOWN_OFFSET;
4009 rhsc.type = SCALAR;
4010 results->safe_push (rhsc);
4013 /* The static chain escapes as well. */
4014 if (gimple_call_chain (stmt))
4015 make_escape_constraint (gimple_call_chain (stmt));
4017 /* And if we applied NRV the address of the return slot escapes as well. */
4018 if (gimple_call_return_slot_opt_p (stmt)
4019 && gimple_call_lhs (stmt) != NULL_TREE
4020 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4022 auto_vec<ce_s> tmpc;
4023 struct constraint_expr lhsc, *c;
4024 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
4025 lhsc.var = escaped_id;
4026 lhsc.offset = 0;
4027 lhsc.type = SCALAR;
4028 FOR_EACH_VEC_ELT (tmpc, i, c)
4029 process_constraint (new_constraint (lhsc, *c));
4032 /* Regular functions return nonlocal memory. */
4033 rhsc.var = nonlocal_id;
4034 rhsc.offset = 0;
4035 rhsc.type = SCALAR;
4036 results->safe_push (rhsc);
4039 /* For non-IPA mode, generate constraints necessary for a call
4040 that returns a pointer and assigns it to LHS. This simply makes
4041 the LHS point to global and escaped variables. */
4043 static void
4044 handle_lhs_call (gcall *stmt, tree lhs, int flags, vec<ce_s> rhsc,
4045 tree fndecl)
4047 auto_vec<ce_s> lhsc;
4049 get_constraint_for (lhs, &lhsc);
4050 /* If the store is to a global decl make sure to
4051 add proper escape constraints. */
4052 lhs = get_base_address (lhs);
4053 if (lhs
4054 && DECL_P (lhs)
4055 && is_global_var (lhs))
4057 struct constraint_expr tmpc;
4058 tmpc.var = escaped_id;
4059 tmpc.offset = 0;
4060 tmpc.type = SCALAR;
4061 lhsc.safe_push (tmpc);
4064 /* If the call returns an argument unmodified override the rhs
4065 constraints. */
4066 if (flags & ERF_RETURNS_ARG
4067 && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
4069 tree arg;
4070 rhsc.create (0);
4071 arg = gimple_call_arg (stmt, flags & ERF_RETURN_ARG_MASK);
4072 get_constraint_for (arg, &rhsc);
4073 process_all_all_constraints (lhsc, rhsc);
4074 rhsc.release ();
4076 else if (flags & ERF_NOALIAS)
4078 varinfo_t vi;
4079 struct constraint_expr tmpc;
4080 rhsc.create (0);
4081 vi = make_heapvar ("HEAP", true);
4082 /* We are marking allocated storage local, we deal with it becoming
4083 global by escaping and setting of vars_contains_escaped_heap. */
4084 DECL_EXTERNAL (vi->decl) = 0;
4085 vi->is_global_var = 0;
4086 /* If this is not a real malloc call assume the memory was
4087 initialized and thus may point to global memory. All
4088 builtin functions with the malloc attribute behave in a sane way. */
4089 if (!fndecl
4090 || !fndecl_built_in_p (fndecl, BUILT_IN_NORMAL))
4091 make_constraint_from (vi, nonlocal_id);
4092 tmpc.var = vi->id;
4093 tmpc.offset = 0;
4094 tmpc.type = ADDRESSOF;
4095 rhsc.safe_push (tmpc);
4096 process_all_all_constraints (lhsc, rhsc);
4097 rhsc.release ();
4099 else
4100 process_all_all_constraints (lhsc, rhsc);
4103 /* For non-IPA mode, generate constraints necessary for a call of a
4104 const function that returns a pointer in the statement STMT. */
4106 static void
4107 handle_const_call (gcall *stmt, vec<ce_s> *results)
4109 struct constraint_expr rhsc;
4110 unsigned int k;
4111 bool need_uses = false;
4113 /* Treat nested const functions the same as pure functions as far
4114 as the static chain is concerned. */
4115 if (gimple_call_chain (stmt))
4117 varinfo_t uses = get_call_use_vi (stmt);
4118 make_constraint_to (uses->id, gimple_call_chain (stmt));
4119 need_uses = true;
4122 /* And if we applied NRV the address of the return slot escapes as well. */
4123 if (gimple_call_return_slot_opt_p (stmt)
4124 && gimple_call_lhs (stmt) != NULL_TREE
4125 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4127 varinfo_t uses = get_call_use_vi (stmt);
4128 auto_vec<ce_s> tmpc;
4129 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
4130 make_constraints_to (uses->id, tmpc);
4131 need_uses = true;
4134 if (need_uses)
4136 varinfo_t uses = get_call_use_vi (stmt);
4137 make_any_offset_constraints (uses);
4138 make_transitive_closure_constraints (uses);
4139 rhsc.var = uses->id;
4140 rhsc.offset = 0;
4141 rhsc.type = SCALAR;
4142 results->safe_push (rhsc);
4145 /* May return offsetted arguments. */
4146 varinfo_t tem = NULL;
4147 if (gimple_call_num_args (stmt) != 0)
4149 tem = new_var_info (NULL_TREE, "callarg", true);
4150 tem->is_reg_var = true;
4152 for (k = 0; k < gimple_call_num_args (stmt); ++k)
4154 tree arg = gimple_call_arg (stmt, k);
4155 auto_vec<ce_s> argc;
4156 get_constraint_for_rhs (arg, &argc);
4157 make_constraints_to (tem->id, argc);
4159 if (tem)
4161 ce_s ce;
4162 ce.type = SCALAR;
4163 ce.var = tem->id;
4164 ce.offset = UNKNOWN_OFFSET;
4165 results->safe_push (ce);
4168 /* May return addresses of globals. */
4169 rhsc.var = nonlocal_id;
4170 rhsc.offset = 0;
4171 rhsc.type = ADDRESSOF;
4172 results->safe_push (rhsc);
4175 /* For non-IPA mode, generate constraints necessary for a call to a
4176 pure function in statement STMT. */
4178 static void
4179 handle_pure_call (gcall *stmt, vec<ce_s> *results)
4181 struct constraint_expr rhsc;
4182 unsigned i;
4183 varinfo_t uses = NULL;
4185 /* Memory reached from pointer arguments is call-used. */
4186 for (i = 0; i < gimple_call_num_args (stmt); ++i)
4188 tree arg = gimple_call_arg (stmt, i);
4189 if (!uses)
4191 uses = get_call_use_vi (stmt);
4192 make_any_offset_constraints (uses);
4193 make_transitive_closure_constraints (uses);
4195 make_constraint_to (uses->id, arg);
4198 /* The static chain is used as well. */
4199 if (gimple_call_chain (stmt))
4201 if (!uses)
4203 uses = get_call_use_vi (stmt);
4204 make_any_offset_constraints (uses);
4205 make_transitive_closure_constraints (uses);
4207 make_constraint_to (uses->id, gimple_call_chain (stmt));
4210 /* And if we applied NRV the address of the return slot. */
4211 if (gimple_call_return_slot_opt_p (stmt)
4212 && gimple_call_lhs (stmt) != NULL_TREE
4213 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4215 if (!uses)
4217 uses = get_call_use_vi (stmt);
4218 make_any_offset_constraints (uses);
4219 make_transitive_closure_constraints (uses);
4221 auto_vec<ce_s> tmpc;
4222 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
4223 make_constraints_to (uses->id, tmpc);
4226 /* Pure functions may return call-used and nonlocal memory. */
4227 if (uses)
4229 rhsc.var = uses->id;
4230 rhsc.offset = 0;
4231 rhsc.type = SCALAR;
4232 results->safe_push (rhsc);
4234 rhsc.var = nonlocal_id;
4235 rhsc.offset = 0;
4236 rhsc.type = SCALAR;
4237 results->safe_push (rhsc);
4241 /* Return the varinfo for the callee of CALL. */
4243 static varinfo_t
4244 get_fi_for_callee (gcall *call)
4246 tree decl, fn = gimple_call_fn (call);
4248 if (fn && TREE_CODE (fn) == OBJ_TYPE_REF)
4249 fn = OBJ_TYPE_REF_EXPR (fn);
4251 /* If we can directly resolve the function being called, do so.
4252 Otherwise, it must be some sort of indirect expression that
4253 we should still be able to handle. */
4254 decl = gimple_call_addr_fndecl (fn);
4255 if (decl)
4256 return get_vi_for_tree (decl);
4258 /* If the function is anything other than a SSA name pointer we have no
4259 clue and should be getting ANYFN (well, ANYTHING for now). */
4260 if (!fn || TREE_CODE (fn) != SSA_NAME)
4261 return get_varinfo (anything_id);
4263 if (SSA_NAME_IS_DEFAULT_DEF (fn)
4264 && (TREE_CODE (SSA_NAME_VAR (fn)) == PARM_DECL
4265 || TREE_CODE (SSA_NAME_VAR (fn)) == RESULT_DECL))
4266 fn = SSA_NAME_VAR (fn);
4268 return get_vi_for_tree (fn);
4271 /* Create constraints for assigning call argument ARG to the incoming parameter
4272 INDEX of function FI. */
4274 static void
4275 find_func_aliases_for_call_arg (varinfo_t fi, unsigned index, tree arg)
4277 struct constraint_expr lhs;
4278 lhs = get_function_part_constraint (fi, fi_parm_base + index);
4280 auto_vec<ce_s, 2> rhsc;
4281 get_constraint_for_rhs (arg, &rhsc);
4283 unsigned j;
4284 struct constraint_expr *rhsp;
4285 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4286 process_constraint (new_constraint (lhs, *rhsp));
4289 /* Return true if FNDECL may be part of another lto partition. */
4291 static bool
4292 fndecl_maybe_in_other_partition (tree fndecl)
4294 cgraph_node *fn_node = cgraph_node::get (fndecl);
4295 if (fn_node == NULL)
4296 return true;
4298 return fn_node->in_other_partition;
4301 /* Create constraints for the builtin call T. Return true if the call
4302 was handled, otherwise false. */
4304 static bool
4305 find_func_aliases_for_builtin_call (struct function *fn, gcall *t)
4307 tree fndecl = gimple_call_fndecl (t);
4308 auto_vec<ce_s, 2> lhsc;
4309 auto_vec<ce_s, 4> rhsc;
4310 varinfo_t fi;
4312 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
4313 /* ??? All builtins that are handled here need to be handled
4314 in the alias-oracle query functions explicitly! */
4315 switch (DECL_FUNCTION_CODE (fndecl))
4317 /* All the following functions return a pointer to the same object
4318 as their first argument points to. The functions do not add
4319 to the ESCAPED solution. The functions make the first argument
4320 pointed to memory point to what the second argument pointed to
4321 memory points to. */
4322 case BUILT_IN_STRCPY:
4323 case BUILT_IN_STRNCPY:
4324 case BUILT_IN_BCOPY:
4325 case BUILT_IN_MEMCPY:
4326 case BUILT_IN_MEMMOVE:
4327 case BUILT_IN_MEMPCPY:
4328 case BUILT_IN_STPCPY:
4329 case BUILT_IN_STPNCPY:
4330 case BUILT_IN_STRCAT:
4331 case BUILT_IN_STRNCAT:
4332 case BUILT_IN_STRCPY_CHK:
4333 case BUILT_IN_STRNCPY_CHK:
4334 case BUILT_IN_MEMCPY_CHK:
4335 case BUILT_IN_MEMMOVE_CHK:
4336 case BUILT_IN_MEMPCPY_CHK:
4337 case BUILT_IN_STPCPY_CHK:
4338 case BUILT_IN_STPNCPY_CHK:
4339 case BUILT_IN_STRCAT_CHK:
4340 case BUILT_IN_STRNCAT_CHK:
4341 case BUILT_IN_TM_MEMCPY:
4342 case BUILT_IN_TM_MEMMOVE:
4344 tree res = gimple_call_lhs (t);
4345 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4346 == BUILT_IN_BCOPY ? 1 : 0));
4347 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4348 == BUILT_IN_BCOPY ? 0 : 1));
4349 if (res != NULL_TREE)
4351 get_constraint_for (res, &lhsc);
4352 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
4353 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
4354 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY
4355 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY_CHK
4356 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY_CHK
4357 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY_CHK)
4358 get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
4359 else
4360 get_constraint_for (dest, &rhsc);
4361 process_all_all_constraints (lhsc, rhsc);
4362 lhsc.truncate (0);
4363 rhsc.truncate (0);
4365 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4366 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4367 do_deref (&lhsc);
4368 do_deref (&rhsc);
4369 process_all_all_constraints (lhsc, rhsc);
4370 return true;
4372 case BUILT_IN_MEMSET:
4373 case BUILT_IN_MEMSET_CHK:
4374 case BUILT_IN_TM_MEMSET:
4376 tree res = gimple_call_lhs (t);
4377 tree dest = gimple_call_arg (t, 0);
4378 unsigned i;
4379 ce_s *lhsp;
4380 struct constraint_expr ac;
4381 if (res != NULL_TREE)
4383 get_constraint_for (res, &lhsc);
4384 get_constraint_for (dest, &rhsc);
4385 process_all_all_constraints (lhsc, rhsc);
4386 lhsc.truncate (0);
4388 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4389 do_deref (&lhsc);
4390 if (flag_delete_null_pointer_checks
4391 && integer_zerop (gimple_call_arg (t, 1)))
4393 ac.type = ADDRESSOF;
4394 ac.var = nothing_id;
4396 else
4398 ac.type = SCALAR;
4399 ac.var = integer_id;
4401 ac.offset = 0;
4402 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
4403 process_constraint (new_constraint (*lhsp, ac));
4404 return true;
4406 case BUILT_IN_POSIX_MEMALIGN:
4408 tree ptrptr = gimple_call_arg (t, 0);
4409 get_constraint_for (ptrptr, &lhsc);
4410 do_deref (&lhsc);
4411 varinfo_t vi = make_heapvar ("HEAP", true);
4412 /* We are marking allocated storage local, we deal with it becoming
4413 global by escaping and setting of vars_contains_escaped_heap. */
4414 DECL_EXTERNAL (vi->decl) = 0;
4415 vi->is_global_var = 0;
4416 struct constraint_expr tmpc;
4417 tmpc.var = vi->id;
4418 tmpc.offset = 0;
4419 tmpc.type = ADDRESSOF;
4420 rhsc.safe_push (tmpc);
4421 process_all_all_constraints (lhsc, rhsc);
4422 return true;
4424 case BUILT_IN_ASSUME_ALIGNED:
4426 tree res = gimple_call_lhs (t);
4427 tree dest = gimple_call_arg (t, 0);
4428 if (res != NULL_TREE)
4430 get_constraint_for (res, &lhsc);
4431 get_constraint_for (dest, &rhsc);
4432 process_all_all_constraints (lhsc, rhsc);
4434 return true;
4436 /* All the following functions do not return pointers, do not
4437 modify the points-to sets of memory reachable from their
4438 arguments and do not add to the ESCAPED solution. */
4439 case BUILT_IN_SINCOS:
4440 case BUILT_IN_SINCOSF:
4441 case BUILT_IN_SINCOSL:
4442 case BUILT_IN_FREXP:
4443 case BUILT_IN_FREXPF:
4444 case BUILT_IN_FREXPL:
4445 case BUILT_IN_GAMMA_R:
4446 case BUILT_IN_GAMMAF_R:
4447 case BUILT_IN_GAMMAL_R:
4448 case BUILT_IN_LGAMMA_R:
4449 case BUILT_IN_LGAMMAF_R:
4450 case BUILT_IN_LGAMMAL_R:
4451 case BUILT_IN_MODF:
4452 case BUILT_IN_MODFF:
4453 case BUILT_IN_MODFL:
4454 case BUILT_IN_REMQUO:
4455 case BUILT_IN_REMQUOF:
4456 case BUILT_IN_REMQUOL:
4457 case BUILT_IN_FREE:
4458 return true;
4459 case BUILT_IN_STRDUP:
4460 case BUILT_IN_STRNDUP:
4461 case BUILT_IN_REALLOC:
4462 if (gimple_call_lhs (t))
4464 handle_lhs_call (t, gimple_call_lhs (t),
4465 gimple_call_return_flags (t) | ERF_NOALIAS,
4466 vNULL, fndecl);
4467 get_constraint_for_ptr_offset (gimple_call_lhs (t),
4468 NULL_TREE, &lhsc);
4469 get_constraint_for_ptr_offset (gimple_call_arg (t, 0),
4470 NULL_TREE, &rhsc);
4471 do_deref (&lhsc);
4472 do_deref (&rhsc);
4473 process_all_all_constraints (lhsc, rhsc);
4474 lhsc.truncate (0);
4475 rhsc.truncate (0);
4476 /* For realloc the resulting pointer can be equal to the
4477 argument as well. But only doing this wouldn't be
4478 correct because with ptr == 0 realloc behaves like malloc. */
4479 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_REALLOC)
4481 get_constraint_for (gimple_call_lhs (t), &lhsc);
4482 get_constraint_for (gimple_call_arg (t, 0), &rhsc);
4483 process_all_all_constraints (lhsc, rhsc);
4485 return true;
4487 break;
4488 /* String / character search functions return a pointer into the
4489 source string or NULL. */
4490 case BUILT_IN_INDEX:
4491 case BUILT_IN_STRCHR:
4492 case BUILT_IN_STRRCHR:
4493 case BUILT_IN_MEMCHR:
4494 case BUILT_IN_STRSTR:
4495 case BUILT_IN_STRPBRK:
4496 if (gimple_call_lhs (t))
4498 tree src = gimple_call_arg (t, 0);
4499 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4500 constraint_expr nul;
4501 nul.var = nothing_id;
4502 nul.offset = 0;
4503 nul.type = ADDRESSOF;
4504 rhsc.safe_push (nul);
4505 get_constraint_for (gimple_call_lhs (t), &lhsc);
4506 process_all_all_constraints (lhsc, rhsc);
4508 return true;
4509 /* Pure functions that return something not based on any object and
4510 that use the memory pointed to by their arguments (but not
4511 transitively). */
4512 case BUILT_IN_STRCMP:
4513 case BUILT_IN_STRCMP_EQ:
4514 case BUILT_IN_STRNCMP:
4515 case BUILT_IN_STRNCMP_EQ:
4516 case BUILT_IN_STRCASECMP:
4517 case BUILT_IN_STRNCASECMP:
4518 case BUILT_IN_MEMCMP:
4519 case BUILT_IN_BCMP:
4520 case BUILT_IN_STRSPN:
4521 case BUILT_IN_STRCSPN:
4523 varinfo_t uses = get_call_use_vi (t);
4524 make_any_offset_constraints (uses);
4525 make_constraint_to (uses->id, gimple_call_arg (t, 0));
4526 make_constraint_to (uses->id, gimple_call_arg (t, 1));
4527 /* No constraints are necessary for the return value. */
4528 return true;
4530 case BUILT_IN_STRLEN:
4532 varinfo_t uses = get_call_use_vi (t);
4533 make_any_offset_constraints (uses);
4534 make_constraint_to (uses->id, gimple_call_arg (t, 0));
4535 /* No constraints are necessary for the return value. */
4536 return true;
4538 case BUILT_IN_OBJECT_SIZE:
4539 case BUILT_IN_CONSTANT_P:
4541 /* No constraints are necessary for the return value or the
4542 arguments. */
4543 return true;
4545 /* Trampolines are special - they set up passing the static
4546 frame. */
4547 case BUILT_IN_INIT_TRAMPOLINE:
4549 tree tramp = gimple_call_arg (t, 0);
4550 tree nfunc = gimple_call_arg (t, 1);
4551 tree frame = gimple_call_arg (t, 2);
4552 unsigned i;
4553 struct constraint_expr lhs, *rhsp;
4554 if (in_ipa_mode)
4556 varinfo_t nfi = NULL;
4557 gcc_assert (TREE_CODE (nfunc) == ADDR_EXPR);
4558 nfi = lookup_vi_for_tree (TREE_OPERAND (nfunc, 0));
4559 if (nfi)
4561 lhs = get_function_part_constraint (nfi, fi_static_chain);
4562 get_constraint_for (frame, &rhsc);
4563 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4564 process_constraint (new_constraint (lhs, *rhsp));
4565 rhsc.truncate (0);
4567 /* Make the frame point to the function for
4568 the trampoline adjustment call. */
4569 get_constraint_for (tramp, &lhsc);
4570 do_deref (&lhsc);
4571 get_constraint_for (nfunc, &rhsc);
4572 process_all_all_constraints (lhsc, rhsc);
4574 return true;
4577 /* Else fallthru to generic handling which will let
4578 the frame escape. */
4579 break;
4581 case BUILT_IN_ADJUST_TRAMPOLINE:
4583 tree tramp = gimple_call_arg (t, 0);
4584 tree res = gimple_call_lhs (t);
4585 if (in_ipa_mode && res)
4587 get_constraint_for (res, &lhsc);
4588 get_constraint_for (tramp, &rhsc);
4589 do_deref (&rhsc);
4590 process_all_all_constraints (lhsc, rhsc);
4592 return true;
4594 CASE_BUILT_IN_TM_STORE (1):
4595 CASE_BUILT_IN_TM_STORE (2):
4596 CASE_BUILT_IN_TM_STORE (4):
4597 CASE_BUILT_IN_TM_STORE (8):
4598 CASE_BUILT_IN_TM_STORE (FLOAT):
4599 CASE_BUILT_IN_TM_STORE (DOUBLE):
4600 CASE_BUILT_IN_TM_STORE (LDOUBLE):
4601 CASE_BUILT_IN_TM_STORE (M64):
4602 CASE_BUILT_IN_TM_STORE (M128):
4603 CASE_BUILT_IN_TM_STORE (M256):
4605 tree addr = gimple_call_arg (t, 0);
4606 tree src = gimple_call_arg (t, 1);
4608 get_constraint_for (addr, &lhsc);
4609 do_deref (&lhsc);
4610 get_constraint_for (src, &rhsc);
4611 process_all_all_constraints (lhsc, rhsc);
4612 return true;
4614 CASE_BUILT_IN_TM_LOAD (1):
4615 CASE_BUILT_IN_TM_LOAD (2):
4616 CASE_BUILT_IN_TM_LOAD (4):
4617 CASE_BUILT_IN_TM_LOAD (8):
4618 CASE_BUILT_IN_TM_LOAD (FLOAT):
4619 CASE_BUILT_IN_TM_LOAD (DOUBLE):
4620 CASE_BUILT_IN_TM_LOAD (LDOUBLE):
4621 CASE_BUILT_IN_TM_LOAD (M64):
4622 CASE_BUILT_IN_TM_LOAD (M128):
4623 CASE_BUILT_IN_TM_LOAD (M256):
4625 tree dest = gimple_call_lhs (t);
4626 tree addr = gimple_call_arg (t, 0);
4628 get_constraint_for (dest, &lhsc);
4629 get_constraint_for (addr, &rhsc);
4630 do_deref (&rhsc);
4631 process_all_all_constraints (lhsc, rhsc);
4632 return true;
4634 /* Variadic argument handling needs to be handled in IPA
4635 mode as well. */
4636 case BUILT_IN_VA_START:
4638 tree valist = gimple_call_arg (t, 0);
4639 struct constraint_expr rhs, *lhsp;
4640 unsigned i;
4641 get_constraint_for_ptr_offset (valist, NULL_TREE, &lhsc);
4642 do_deref (&lhsc);
4643 /* The va_list gets access to pointers in variadic
4644 arguments. Which we know in the case of IPA analysis
4645 and otherwise are just all nonlocal variables. */
4646 if (in_ipa_mode)
4648 fi = lookup_vi_for_tree (fn->decl);
4649 rhs = get_function_part_constraint (fi, ~0);
4650 rhs.type = ADDRESSOF;
4652 else
4654 rhs.var = nonlocal_id;
4655 rhs.type = ADDRESSOF;
4656 rhs.offset = 0;
4658 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
4659 process_constraint (new_constraint (*lhsp, rhs));
4660 /* va_list is clobbered. */
4661 make_constraint_to (get_call_clobber_vi (t)->id, valist);
4662 return true;
4664 /* va_end doesn't have any effect that matters. */
4665 case BUILT_IN_VA_END:
4666 return true;
4667 /* Alternate return. Simply give up for now. */
4668 case BUILT_IN_RETURN:
4670 fi = NULL;
4671 if (!in_ipa_mode
4672 || !(fi = get_vi_for_tree (fn->decl)))
4673 make_constraint_from (get_varinfo (escaped_id), anything_id);
4674 else if (in_ipa_mode
4675 && fi != NULL)
4677 struct constraint_expr lhs, rhs;
4678 lhs = get_function_part_constraint (fi, fi_result);
4679 rhs.var = anything_id;
4680 rhs.offset = 0;
4681 rhs.type = SCALAR;
4682 process_constraint (new_constraint (lhs, rhs));
4684 return true;
4686 case BUILT_IN_GOMP_PARALLEL:
4687 case BUILT_IN_GOACC_PARALLEL:
4689 if (in_ipa_mode)
4691 unsigned int fnpos, argpos;
4692 switch (DECL_FUNCTION_CODE (fndecl))
4694 case BUILT_IN_GOMP_PARALLEL:
4695 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
4696 fnpos = 0;
4697 argpos = 1;
4698 break;
4699 case BUILT_IN_GOACC_PARALLEL:
4700 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
4701 sizes, kinds, ...). */
4702 fnpos = 1;
4703 argpos = 3;
4704 break;
4705 default:
4706 gcc_unreachable ();
4709 tree fnarg = gimple_call_arg (t, fnpos);
4710 gcc_assert (TREE_CODE (fnarg) == ADDR_EXPR);
4711 tree fndecl = TREE_OPERAND (fnarg, 0);
4712 if (fndecl_maybe_in_other_partition (fndecl))
4713 /* Fallthru to general call handling. */
4714 break;
4716 tree arg = gimple_call_arg (t, argpos);
4718 varinfo_t fi = get_vi_for_tree (fndecl);
4719 find_func_aliases_for_call_arg (fi, 0, arg);
4720 return true;
4722 /* Else fallthru to generic call handling. */
4723 break;
4725 /* printf-style functions may have hooks to set pointers to
4726 point to somewhere into the generated string. Leave them
4727 for a later exercise... */
4728 default:
4729 /* Fallthru to general call handling. */;
4732 return false;
4735 /* Create constraints for the call T. */
4737 static void
4738 find_func_aliases_for_call (struct function *fn, gcall *t)
4740 tree fndecl = gimple_call_fndecl (t);
4741 varinfo_t fi;
4743 if (fndecl != NULL_TREE
4744 && fndecl_built_in_p (fndecl)
4745 && find_func_aliases_for_builtin_call (fn, t))
4746 return;
4748 fi = get_fi_for_callee (t);
4749 if (!in_ipa_mode
4750 || (fi->decl && fndecl && !fi->is_fn_info))
4752 auto_vec<ce_s, 16> rhsc;
4753 int flags = gimple_call_flags (t);
4755 /* Const functions can return their arguments and addresses
4756 of global memory but not of escaped memory. */
4757 if (flags & (ECF_CONST|ECF_NOVOPS))
4759 if (gimple_call_lhs (t))
4760 handle_const_call (t, &rhsc);
4762 /* Pure functions can return addresses in and of memory
4763 reachable from their arguments, but they are not an escape
4764 point for reachable memory of their arguments. */
4765 else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE))
4766 handle_pure_call (t, &rhsc);
4767 else
4768 handle_rhs_call (t, &rhsc);
4769 if (gimple_call_lhs (t))
4770 handle_lhs_call (t, gimple_call_lhs (t),
4771 gimple_call_return_flags (t), rhsc, fndecl);
4773 else
4775 auto_vec<ce_s, 2> rhsc;
4776 tree lhsop;
4777 unsigned j;
4779 /* Assign all the passed arguments to the appropriate incoming
4780 parameters of the function. */
4781 for (j = 0; j < gimple_call_num_args (t); j++)
4783 tree arg = gimple_call_arg (t, j);
4784 find_func_aliases_for_call_arg (fi, j, arg);
4787 /* If we are returning a value, assign it to the result. */
4788 lhsop = gimple_call_lhs (t);
4789 if (lhsop)
4791 auto_vec<ce_s, 2> lhsc;
4792 struct constraint_expr rhs;
4793 struct constraint_expr *lhsp;
4794 bool aggr_p = aggregate_value_p (lhsop, gimple_call_fntype (t));
4796 get_constraint_for (lhsop, &lhsc);
4797 rhs = get_function_part_constraint (fi, fi_result);
4798 if (aggr_p)
4800 auto_vec<ce_s, 2> tem;
4801 tem.quick_push (rhs);
4802 do_deref (&tem);
4803 gcc_checking_assert (tem.length () == 1);
4804 rhs = tem[0];
4806 FOR_EACH_VEC_ELT (lhsc, j, lhsp)
4807 process_constraint (new_constraint (*lhsp, rhs));
4809 /* If we pass the result decl by reference, honor that. */
4810 if (aggr_p)
4812 struct constraint_expr lhs;
4813 struct constraint_expr *rhsp;
4815 get_constraint_for_address_of (lhsop, &rhsc);
4816 lhs = get_function_part_constraint (fi, fi_result);
4817 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4818 process_constraint (new_constraint (lhs, *rhsp));
4819 rhsc.truncate (0);
4823 /* If we use a static chain, pass it along. */
4824 if (gimple_call_chain (t))
4826 struct constraint_expr lhs;
4827 struct constraint_expr *rhsp;
4829 get_constraint_for (gimple_call_chain (t), &rhsc);
4830 lhs = get_function_part_constraint (fi, fi_static_chain);
4831 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4832 process_constraint (new_constraint (lhs, *rhsp));
4837 /* Walk statement T setting up aliasing constraints according to the
4838 references found in T. This function is the main part of the
4839 constraint builder. AI points to auxiliary alias information used
4840 when building alias sets and computing alias grouping heuristics. */
4842 static void
4843 find_func_aliases (struct function *fn, gimple *origt)
4845 gimple *t = origt;
4846 auto_vec<ce_s, 16> lhsc;
4847 auto_vec<ce_s, 16> rhsc;
4848 varinfo_t fi;
4850 /* Now build constraints expressions. */
4851 if (gimple_code (t) == GIMPLE_PHI)
4853 /* For a phi node, assign all the arguments to
4854 the result. */
4855 get_constraint_for (gimple_phi_result (t), &lhsc);
4856 for (unsigned i = 0; i < gimple_phi_num_args (t); i++)
4858 get_constraint_for_rhs (gimple_phi_arg_def (t, i), &rhsc);
4859 process_all_all_constraints (lhsc, rhsc);
4860 rhsc.truncate (0);
4863 /* In IPA mode, we need to generate constraints to pass call
4864 arguments through their calls. There are two cases,
4865 either a GIMPLE_CALL returning a value, or just a plain
4866 GIMPLE_CALL when we are not.
4868 In non-ipa mode, we need to generate constraints for each
4869 pointer passed by address. */
4870 else if (is_gimple_call (t))
4871 find_func_aliases_for_call (fn, as_a <gcall *> (t));
4873 /* Otherwise, just a regular assignment statement. Only care about
4874 operations with pointer result, others are dealt with as escape
4875 points if they have pointer operands. */
4876 else if (is_gimple_assign (t))
4878 /* Otherwise, just a regular assignment statement. */
4879 tree lhsop = gimple_assign_lhs (t);
4880 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
4882 if (rhsop && TREE_CLOBBER_P (rhsop))
4883 /* Ignore clobbers, they don't actually store anything into
4884 the LHS. */
4886 else if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
4887 do_structure_copy (lhsop, rhsop);
4888 else
4890 enum tree_code code = gimple_assign_rhs_code (t);
4892 get_constraint_for (lhsop, &lhsc);
4894 if (code == POINTER_PLUS_EXPR)
4895 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4896 gimple_assign_rhs2 (t), &rhsc);
4897 else if (code == BIT_AND_EXPR
4898 && TREE_CODE (gimple_assign_rhs2 (t)) == INTEGER_CST)
4900 /* Aligning a pointer via a BIT_AND_EXPR is offsetting
4901 the pointer. Handle it by offsetting it by UNKNOWN. */
4902 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4903 NULL_TREE, &rhsc);
4905 else if ((CONVERT_EXPR_CODE_P (code)
4906 && !(POINTER_TYPE_P (gimple_expr_type (t))
4907 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
4908 || gimple_assign_single_p (t))
4909 get_constraint_for_rhs (rhsop, &rhsc);
4910 else if (code == COND_EXPR)
4912 /* The result is a merge of both COND_EXPR arms. */
4913 auto_vec<ce_s, 2> tmp;
4914 struct constraint_expr *rhsp;
4915 unsigned i;
4916 get_constraint_for_rhs (gimple_assign_rhs2 (t), &rhsc);
4917 get_constraint_for_rhs (gimple_assign_rhs3 (t), &tmp);
4918 FOR_EACH_VEC_ELT (tmp, i, rhsp)
4919 rhsc.safe_push (*rhsp);
4921 else if (truth_value_p (code))
4922 /* Truth value results are not pointer (parts). Or at least
4923 very unreasonable obfuscation of a part. */
4925 else
4927 /* All other operations are merges. */
4928 auto_vec<ce_s, 4> tmp;
4929 struct constraint_expr *rhsp;
4930 unsigned i, j;
4931 get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
4932 for (i = 2; i < gimple_num_ops (t); ++i)
4934 get_constraint_for_rhs (gimple_op (t, i), &tmp);
4935 FOR_EACH_VEC_ELT (tmp, j, rhsp)
4936 rhsc.safe_push (*rhsp);
4937 tmp.truncate (0);
4940 process_all_all_constraints (lhsc, rhsc);
4942 /* If there is a store to a global variable the rhs escapes. */
4943 if ((lhsop = get_base_address (lhsop)) != NULL_TREE
4944 && DECL_P (lhsop))
4946 varinfo_t vi = get_vi_for_tree (lhsop);
4947 if ((! in_ipa_mode && vi->is_global_var)
4948 || vi->is_ipa_escape_point)
4949 make_escape_constraint (rhsop);
4952 /* Handle escapes through return. */
4953 else if (gimple_code (t) == GIMPLE_RETURN
4954 && gimple_return_retval (as_a <greturn *> (t)) != NULL_TREE)
4956 greturn *return_stmt = as_a <greturn *> (t);
4957 fi = NULL;
4958 if (!in_ipa_mode
4959 || !(fi = get_vi_for_tree (fn->decl)))
4960 make_escape_constraint (gimple_return_retval (return_stmt));
4961 else if (in_ipa_mode)
4963 struct constraint_expr lhs ;
4964 struct constraint_expr *rhsp;
4965 unsigned i;
4967 lhs = get_function_part_constraint (fi, fi_result);
4968 get_constraint_for_rhs (gimple_return_retval (return_stmt), &rhsc);
4969 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
4970 process_constraint (new_constraint (lhs, *rhsp));
4973 /* Handle asms conservatively by adding escape constraints to everything. */
4974 else if (gasm *asm_stmt = dyn_cast <gasm *> (t))
4976 unsigned i, noutputs;
4977 const char **oconstraints;
4978 const char *constraint;
4979 bool allows_mem, allows_reg, is_inout;
4981 noutputs = gimple_asm_noutputs (asm_stmt);
4982 oconstraints = XALLOCAVEC (const char *, noutputs);
4984 for (i = 0; i < noutputs; ++i)
4986 tree link = gimple_asm_output_op (asm_stmt, i);
4987 tree op = TREE_VALUE (link);
4989 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4990 oconstraints[i] = constraint;
4991 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
4992 &allows_reg, &is_inout);
4994 /* A memory constraint makes the address of the operand escape. */
4995 if (!allows_reg && allows_mem)
4996 make_escape_constraint (build_fold_addr_expr (op));
4998 /* The asm may read global memory, so outputs may point to
4999 any global memory. */
5000 if (op)
5002 auto_vec<ce_s, 2> lhsc;
5003 struct constraint_expr rhsc, *lhsp;
5004 unsigned j;
5005 get_constraint_for (op, &lhsc);
5006 rhsc.var = nonlocal_id;
5007 rhsc.offset = 0;
5008 rhsc.type = SCALAR;
5009 FOR_EACH_VEC_ELT (lhsc, j, lhsp)
5010 process_constraint (new_constraint (*lhsp, rhsc));
5013 for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
5015 tree link = gimple_asm_input_op (asm_stmt, i);
5016 tree op = TREE_VALUE (link);
5018 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
5020 parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
5021 &allows_mem, &allows_reg);
5023 /* A memory constraint makes the address of the operand escape. */
5024 if (!allows_reg && allows_mem)
5025 make_escape_constraint (build_fold_addr_expr (op));
5026 /* Strictly we'd only need the constraint to ESCAPED if
5027 the asm clobbers memory, otherwise using something
5028 along the lines of per-call clobbers/uses would be enough. */
5029 else if (op)
5030 make_escape_constraint (op);
5036 /* Create a constraint adding to the clobber set of FI the memory
5037 pointed to by PTR. */
5039 static void
5040 process_ipa_clobber (varinfo_t fi, tree ptr)
5042 vec<ce_s> ptrc = vNULL;
5043 struct constraint_expr *c, lhs;
5044 unsigned i;
5045 get_constraint_for_rhs (ptr, &ptrc);
5046 lhs = get_function_part_constraint (fi, fi_clobbers);
5047 FOR_EACH_VEC_ELT (ptrc, i, c)
5048 process_constraint (new_constraint (lhs, *c));
5049 ptrc.release ();
5052 /* Walk statement T setting up clobber and use constraints according to the
5053 references found in T. This function is a main part of the
5054 IPA constraint builder. */
5056 static void
5057 find_func_clobbers (struct function *fn, gimple *origt)
5059 gimple *t = origt;
5060 auto_vec<ce_s, 16> lhsc;
5061 auto_vec<ce_s, 16> rhsc;
5062 varinfo_t fi;
5064 /* Add constraints for clobbered/used in IPA mode.
5065 We are not interested in what automatic variables are clobbered
5066 or used as we only use the information in the caller to which
5067 they do not escape. */
5068 gcc_assert (in_ipa_mode);
5070 /* If the stmt refers to memory in any way it better had a VUSE. */
5071 if (gimple_vuse (t) == NULL_TREE)
5072 return;
5074 /* We'd better have function information for the current function. */
5075 fi = lookup_vi_for_tree (fn->decl);
5076 gcc_assert (fi != NULL);
5078 /* Account for stores in assignments and calls. */
5079 if (gimple_vdef (t) != NULL_TREE
5080 && gimple_has_lhs (t))
5082 tree lhs = gimple_get_lhs (t);
5083 tree tem = lhs;
5084 while (handled_component_p (tem))
5085 tem = TREE_OPERAND (tem, 0);
5086 if ((DECL_P (tem)
5087 && !auto_var_in_fn_p (tem, fn->decl))
5088 || INDIRECT_REF_P (tem)
5089 || (TREE_CODE (tem) == MEM_REF
5090 && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
5091 && auto_var_in_fn_p
5092 (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl))))
5094 struct constraint_expr lhsc, *rhsp;
5095 unsigned i;
5096 lhsc = get_function_part_constraint (fi, fi_clobbers);
5097 get_constraint_for_address_of (lhs, &rhsc);
5098 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5099 process_constraint (new_constraint (lhsc, *rhsp));
5100 rhsc.truncate (0);
5104 /* Account for uses in assigments and returns. */
5105 if (gimple_assign_single_p (t)
5106 || (gimple_code (t) == GIMPLE_RETURN
5107 && gimple_return_retval (as_a <greturn *> (t)) != NULL_TREE))
5109 tree rhs = (gimple_assign_single_p (t)
5110 ? gimple_assign_rhs1 (t)
5111 : gimple_return_retval (as_a <greturn *> (t)));
5112 tree tem = rhs;
5113 while (handled_component_p (tem))
5114 tem = TREE_OPERAND (tem, 0);
5115 if ((DECL_P (tem)
5116 && !auto_var_in_fn_p (tem, fn->decl))
5117 || INDIRECT_REF_P (tem)
5118 || (TREE_CODE (tem) == MEM_REF
5119 && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
5120 && auto_var_in_fn_p
5121 (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl))))
5123 struct constraint_expr lhs, *rhsp;
5124 unsigned i;
5125 lhs = get_function_part_constraint (fi, fi_uses);
5126 get_constraint_for_address_of (rhs, &rhsc);
5127 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5128 process_constraint (new_constraint (lhs, *rhsp));
5129 rhsc.truncate (0);
5133 if (gcall *call_stmt = dyn_cast <gcall *> (t))
5135 varinfo_t cfi = NULL;
5136 tree decl = gimple_call_fndecl (t);
5137 struct constraint_expr lhs, rhs;
5138 unsigned i, j;
5140 /* For builtins we do not have separate function info. For those
5141 we do not generate escapes for we have to generate clobbers/uses. */
5142 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
5143 switch (DECL_FUNCTION_CODE (decl))
5145 /* The following functions use and clobber memory pointed to
5146 by their arguments. */
5147 case BUILT_IN_STRCPY:
5148 case BUILT_IN_STRNCPY:
5149 case BUILT_IN_BCOPY:
5150 case BUILT_IN_MEMCPY:
5151 case BUILT_IN_MEMMOVE:
5152 case BUILT_IN_MEMPCPY:
5153 case BUILT_IN_STPCPY:
5154 case BUILT_IN_STPNCPY:
5155 case BUILT_IN_STRCAT:
5156 case BUILT_IN_STRNCAT:
5157 case BUILT_IN_STRCPY_CHK:
5158 case BUILT_IN_STRNCPY_CHK:
5159 case BUILT_IN_MEMCPY_CHK:
5160 case BUILT_IN_MEMMOVE_CHK:
5161 case BUILT_IN_MEMPCPY_CHK:
5162 case BUILT_IN_STPCPY_CHK:
5163 case BUILT_IN_STPNCPY_CHK:
5164 case BUILT_IN_STRCAT_CHK:
5165 case BUILT_IN_STRNCAT_CHK:
5167 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
5168 == BUILT_IN_BCOPY ? 1 : 0));
5169 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
5170 == BUILT_IN_BCOPY ? 0 : 1));
5171 unsigned i;
5172 struct constraint_expr *rhsp, *lhsp;
5173 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
5174 lhs = get_function_part_constraint (fi, fi_clobbers);
5175 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
5176 process_constraint (new_constraint (lhs, *lhsp));
5177 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
5178 lhs = get_function_part_constraint (fi, fi_uses);
5179 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
5180 process_constraint (new_constraint (lhs, *rhsp));
5181 return;
5183 /* The following function clobbers memory pointed to by
5184 its argument. */
5185 case BUILT_IN_MEMSET:
5186 case BUILT_IN_MEMSET_CHK:
5187 case BUILT_IN_POSIX_MEMALIGN:
5189 tree dest = gimple_call_arg (t, 0);
5190 unsigned i;
5191 ce_s *lhsp;
5192 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
5193 lhs = get_function_part_constraint (fi, fi_clobbers);
5194 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
5195 process_constraint (new_constraint (lhs, *lhsp));
5196 return;
5198 /* The following functions clobber their second and third
5199 arguments. */
5200 case BUILT_IN_SINCOS:
5201 case BUILT_IN_SINCOSF:
5202 case BUILT_IN_SINCOSL:
5204 process_ipa_clobber (fi, gimple_call_arg (t, 1));
5205 process_ipa_clobber (fi, gimple_call_arg (t, 2));
5206 return;
5208 /* The following functions clobber their second argument. */
5209 case BUILT_IN_FREXP:
5210 case BUILT_IN_FREXPF:
5211 case BUILT_IN_FREXPL:
5212 case BUILT_IN_LGAMMA_R:
5213 case BUILT_IN_LGAMMAF_R:
5214 case BUILT_IN_LGAMMAL_R:
5215 case BUILT_IN_GAMMA_R:
5216 case BUILT_IN_GAMMAF_R:
5217 case BUILT_IN_GAMMAL_R:
5218 case BUILT_IN_MODF:
5219 case BUILT_IN_MODFF:
5220 case BUILT_IN_MODFL:
5222 process_ipa_clobber (fi, gimple_call_arg (t, 1));
5223 return;
5225 /* The following functions clobber their third argument. */
5226 case BUILT_IN_REMQUO:
5227 case BUILT_IN_REMQUOF:
5228 case BUILT_IN_REMQUOL:
5230 process_ipa_clobber (fi, gimple_call_arg (t, 2));
5231 return;
5233 /* The following functions neither read nor clobber memory. */
5234 case BUILT_IN_ASSUME_ALIGNED:
5235 case BUILT_IN_FREE:
5236 return;
5237 /* Trampolines are of no interest to us. */
5238 case BUILT_IN_INIT_TRAMPOLINE:
5239 case BUILT_IN_ADJUST_TRAMPOLINE:
5240 return;
5241 case BUILT_IN_VA_START:
5242 case BUILT_IN_VA_END:
5243 return;
5244 case BUILT_IN_GOMP_PARALLEL:
5245 case BUILT_IN_GOACC_PARALLEL:
5247 unsigned int fnpos, argpos;
5248 unsigned int implicit_use_args[2];
5249 unsigned int num_implicit_use_args = 0;
5250 switch (DECL_FUNCTION_CODE (decl))
5252 case BUILT_IN_GOMP_PARALLEL:
5253 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */
5254 fnpos = 0;
5255 argpos = 1;
5256 break;
5257 case BUILT_IN_GOACC_PARALLEL:
5258 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
5259 sizes, kinds, ...). */
5260 fnpos = 1;
5261 argpos = 3;
5262 implicit_use_args[num_implicit_use_args++] = 4;
5263 implicit_use_args[num_implicit_use_args++] = 5;
5264 break;
5265 default:
5266 gcc_unreachable ();
5269 tree fnarg = gimple_call_arg (t, fnpos);
5270 gcc_assert (TREE_CODE (fnarg) == ADDR_EXPR);
5271 tree fndecl = TREE_OPERAND (fnarg, 0);
5272 if (fndecl_maybe_in_other_partition (fndecl))
5273 /* Fallthru to general call handling. */
5274 break;
5276 varinfo_t cfi = get_vi_for_tree (fndecl);
5278 tree arg = gimple_call_arg (t, argpos);
5280 /* Parameter passed by value is used. */
5281 lhs = get_function_part_constraint (fi, fi_uses);
5282 struct constraint_expr *rhsp;
5283 get_constraint_for (arg, &rhsc);
5284 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
5285 process_constraint (new_constraint (lhs, *rhsp));
5286 rhsc.truncate (0);
5288 /* Handle parameters used by the call, but not used in cfi, as
5289 implicitly used by cfi. */
5290 lhs = get_function_part_constraint (cfi, fi_uses);
5291 for (unsigned i = 0; i < num_implicit_use_args; ++i)
5293 tree arg = gimple_call_arg (t, implicit_use_args[i]);
5294 get_constraint_for (arg, &rhsc);
5295 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
5296 process_constraint (new_constraint (lhs, *rhsp));
5297 rhsc.truncate (0);
5300 /* The caller clobbers what the callee does. */
5301 lhs = get_function_part_constraint (fi, fi_clobbers);
5302 rhs = get_function_part_constraint (cfi, fi_clobbers);
5303 process_constraint (new_constraint (lhs, rhs));
5305 /* The caller uses what the callee does. */
5306 lhs = get_function_part_constraint (fi, fi_uses);
5307 rhs = get_function_part_constraint (cfi, fi_uses);
5308 process_constraint (new_constraint (lhs, rhs));
5310 return;
5312 /* printf-style functions may have hooks to set pointers to
5313 point to somewhere into the generated string. Leave them
5314 for a later exercise... */
5315 default:
5316 /* Fallthru to general call handling. */;
5319 /* Parameters passed by value are used. */
5320 lhs = get_function_part_constraint (fi, fi_uses);
5321 for (i = 0; i < gimple_call_num_args (t); i++)
5323 struct constraint_expr *rhsp;
5324 tree arg = gimple_call_arg (t, i);
5326 if (TREE_CODE (arg) == SSA_NAME
5327 || is_gimple_min_invariant (arg))
5328 continue;
5330 get_constraint_for_address_of (arg, &rhsc);
5331 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
5332 process_constraint (new_constraint (lhs, *rhsp));
5333 rhsc.truncate (0);
5336 /* Build constraints for propagating clobbers/uses along the
5337 callgraph edges. */
5338 cfi = get_fi_for_callee (call_stmt);
5339 if (cfi->id == anything_id)
5341 if (gimple_vdef (t))
5342 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
5343 anything_id);
5344 make_constraint_from (first_vi_for_offset (fi, fi_uses),
5345 anything_id);
5346 return;
5349 /* For callees without function info (that's external functions),
5350 ESCAPED is clobbered and used. */
5351 if (cfi->decl
5352 && TREE_CODE (cfi->decl) == FUNCTION_DECL
5353 && !cfi->is_fn_info)
5355 varinfo_t vi;
5357 if (gimple_vdef (t))
5358 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
5359 escaped_id);
5360 make_copy_constraint (first_vi_for_offset (fi, fi_uses), escaped_id);
5362 /* Also honor the call statement use/clobber info. */
5363 if ((vi = lookup_call_clobber_vi (call_stmt)) != NULL)
5364 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
5365 vi->id);
5366 if ((vi = lookup_call_use_vi (call_stmt)) != NULL)
5367 make_copy_constraint (first_vi_for_offset (fi, fi_uses),
5368 vi->id);
5369 return;
5372 /* Otherwise the caller clobbers and uses what the callee does.
5373 ??? This should use a new complex constraint that filters
5374 local variables of the callee. */
5375 if (gimple_vdef (t))
5377 lhs = get_function_part_constraint (fi, fi_clobbers);
5378 rhs = get_function_part_constraint (cfi, fi_clobbers);
5379 process_constraint (new_constraint (lhs, rhs));
5381 lhs = get_function_part_constraint (fi, fi_uses);
5382 rhs = get_function_part_constraint (cfi, fi_uses);
5383 process_constraint (new_constraint (lhs, rhs));
5385 else if (gimple_code (t) == GIMPLE_ASM)
5387 /* ??? Ick. We can do better. */
5388 if (gimple_vdef (t))
5389 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
5390 anything_id);
5391 make_constraint_from (first_vi_for_offset (fi, fi_uses),
5392 anything_id);
5397 /* Find the first varinfo in the same variable as START that overlaps with
5398 OFFSET. Return NULL if we can't find one. */
5400 static varinfo_t
5401 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
5403 /* If the offset is outside of the variable, bail out. */
5404 if (offset >= start->fullsize)
5405 return NULL;
5407 /* If we cannot reach offset from start, lookup the first field
5408 and start from there. */
5409 if (start->offset > offset)
5410 start = get_varinfo (start->head);
5412 while (start)
5414 /* We may not find a variable in the field list with the actual
5415 offset when we have glommed a structure to a variable.
5416 In that case, however, offset should still be within the size
5417 of the variable. */
5418 if (offset >= start->offset
5419 && (offset - start->offset) < start->size)
5420 return start;
5422 start = vi_next (start);
5425 return NULL;
5428 /* Find the first varinfo in the same variable as START that overlaps with
5429 OFFSET. If there is no such varinfo the varinfo directly preceding
5430 OFFSET is returned. */
5432 static varinfo_t
5433 first_or_preceding_vi_for_offset (varinfo_t start,
5434 unsigned HOST_WIDE_INT offset)
5436 /* If we cannot reach offset from start, lookup the first field
5437 and start from there. */
5438 if (start->offset > offset)
5439 start = get_varinfo (start->head);
5441 /* We may not find a variable in the field list with the actual
5442 offset when we have glommed a structure to a variable.
5443 In that case, however, offset should still be within the size
5444 of the variable.
5445 If we got beyond the offset we look for return the field
5446 directly preceding offset which may be the last field. */
5447 while (start->next
5448 && offset >= start->offset
5449 && !((offset - start->offset) < start->size))
5450 start = vi_next (start);
5452 return start;
5456 /* This structure is used during pushing fields onto the fieldstack
5457 to track the offset of the field, since bitpos_of_field gives it
5458 relative to its immediate containing type, and we want it relative
5459 to the ultimate containing object. */
5461 struct fieldoff
5463 /* Offset from the base of the base containing object to this field. */
5464 HOST_WIDE_INT offset;
5466 /* Size, in bits, of the field. */
5467 unsigned HOST_WIDE_INT size;
5469 unsigned has_unknown_size : 1;
5471 unsigned must_have_pointers : 1;
5473 unsigned may_have_pointers : 1;
5475 unsigned only_restrict_pointers : 1;
5477 tree restrict_pointed_type;
5479 typedef struct fieldoff fieldoff_s;
5482 /* qsort comparison function for two fieldoff's PA and PB */
5484 static int
5485 fieldoff_compare (const void *pa, const void *pb)
5487 const fieldoff_s *foa = (const fieldoff_s *)pa;
5488 const fieldoff_s *fob = (const fieldoff_s *)pb;
5489 unsigned HOST_WIDE_INT foasize, fobsize;
5491 if (foa->offset < fob->offset)
5492 return -1;
5493 else if (foa->offset > fob->offset)
5494 return 1;
5496 foasize = foa->size;
5497 fobsize = fob->size;
5498 if (foasize < fobsize)
5499 return -1;
5500 else if (foasize > fobsize)
5501 return 1;
5502 return 0;
5505 /* Sort a fieldstack according to the field offset and sizes. */
5506 static void
5507 sort_fieldstack (vec<fieldoff_s> fieldstack)
5509 fieldstack.qsort (fieldoff_compare);
5512 /* Return true if T is a type that can have subvars. */
5514 static inline bool
5515 type_can_have_subvars (const_tree t)
5517 /* Aggregates without overlapping fields can have subvars. */
5518 return TREE_CODE (t) == RECORD_TYPE;
5521 /* Return true if V is a tree that we can have subvars for.
5522 Normally, this is any aggregate type. Also complex
5523 types which are not gimple registers can have subvars. */
5525 static inline bool
5526 var_can_have_subvars (const_tree v)
5528 /* Volatile variables should never have subvars. */
5529 if (TREE_THIS_VOLATILE (v))
5530 return false;
5532 /* Non decls or memory tags can never have subvars. */
5533 if (!DECL_P (v))
5534 return false;
5536 return type_can_have_subvars (TREE_TYPE (v));
5539 /* Return true if T is a type that does contain pointers. */
5541 static bool
5542 type_must_have_pointers (tree type)
5544 if (POINTER_TYPE_P (type))
5545 return true;
5547 if (TREE_CODE (type) == ARRAY_TYPE)
5548 return type_must_have_pointers (TREE_TYPE (type));
5550 /* A function or method can have pointers as arguments, so track
5551 those separately. */
5552 if (TREE_CODE (type) == FUNCTION_TYPE
5553 || TREE_CODE (type) == METHOD_TYPE)
5554 return true;
5556 return false;
5559 static bool
5560 field_must_have_pointers (tree t)
5562 return type_must_have_pointers (TREE_TYPE (t));
5565 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
5566 the fields of TYPE onto fieldstack, recording their offsets along
5567 the way.
5569 OFFSET is used to keep track of the offset in this entire
5570 structure, rather than just the immediately containing structure.
5571 Returns false if the caller is supposed to handle the field we
5572 recursed for. */
5574 static bool
5575 push_fields_onto_fieldstack (tree type, vec<fieldoff_s> *fieldstack,
5576 HOST_WIDE_INT offset)
5578 tree field;
5579 bool empty_p = true;
5581 if (TREE_CODE (type) != RECORD_TYPE)
5582 return false;
5584 /* If the vector of fields is growing too big, bail out early.
5585 Callers check for vec::length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
5586 sure this fails. */
5587 if (fieldstack->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
5588 return false;
5590 for (field = TYPE_FIELDS (type); field; field = DECL_CHAIN (field))
5591 if (TREE_CODE (field) == FIELD_DECL)
5593 bool push = false;
5594 HOST_WIDE_INT foff = bitpos_of_field (field);
5595 tree field_type = TREE_TYPE (field);
5597 if (!var_can_have_subvars (field)
5598 || TREE_CODE (field_type) == QUAL_UNION_TYPE
5599 || TREE_CODE (field_type) == UNION_TYPE)
5600 push = true;
5601 else if (!push_fields_onto_fieldstack
5602 (field_type, fieldstack, offset + foff)
5603 && (DECL_SIZE (field)
5604 && !integer_zerop (DECL_SIZE (field))))
5605 /* Empty structures may have actual size, like in C++. So
5606 see if we didn't push any subfields and the size is
5607 nonzero, push the field onto the stack. */
5608 push = true;
5610 if (push)
5612 fieldoff_s *pair = NULL;
5613 bool has_unknown_size = false;
5614 bool must_have_pointers_p;
5616 if (!fieldstack->is_empty ())
5617 pair = &fieldstack->last ();
5619 /* If there isn't anything at offset zero, create sth. */
5620 if (!pair
5621 && offset + foff != 0)
5623 fieldoff_s e
5624 = {0, offset + foff, false, false, true, false, NULL_TREE};
5625 pair = fieldstack->safe_push (e);
5628 if (!DECL_SIZE (field)
5629 || !tree_fits_uhwi_p (DECL_SIZE (field)))
5630 has_unknown_size = true;
5632 /* If adjacent fields do not contain pointers merge them. */
5633 must_have_pointers_p = field_must_have_pointers (field);
5634 if (pair
5635 && !has_unknown_size
5636 && !must_have_pointers_p
5637 && !pair->must_have_pointers
5638 && !pair->has_unknown_size
5639 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
5641 pair->size += tree_to_uhwi (DECL_SIZE (field));
5643 else
5645 fieldoff_s e;
5646 e.offset = offset + foff;
5647 e.has_unknown_size = has_unknown_size;
5648 if (!has_unknown_size)
5649 e.size = tree_to_uhwi (DECL_SIZE (field));
5650 else
5651 e.size = -1;
5652 e.must_have_pointers = must_have_pointers_p;
5653 e.may_have_pointers = true;
5654 e.only_restrict_pointers
5655 = (!has_unknown_size
5656 && POINTER_TYPE_P (field_type)
5657 && TYPE_RESTRICT (field_type));
5658 if (e.only_restrict_pointers)
5659 e.restrict_pointed_type = TREE_TYPE (field_type);
5660 fieldstack->safe_push (e);
5664 empty_p = false;
5667 return !empty_p;
5670 /* Count the number of arguments DECL has, and set IS_VARARGS to true
5671 if it is a varargs function. */
5673 static unsigned int
5674 count_num_arguments (tree decl, bool *is_varargs)
5676 unsigned int num = 0;
5677 tree t;
5679 /* Capture named arguments for K&R functions. They do not
5680 have a prototype and thus no TYPE_ARG_TYPES. */
5681 for (t = DECL_ARGUMENTS (decl); t; t = DECL_CHAIN (t))
5682 ++num;
5684 /* Check if the function has variadic arguments. */
5685 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); t; t = TREE_CHAIN (t))
5686 if (TREE_VALUE (t) == void_type_node)
5687 break;
5688 if (!t)
5689 *is_varargs = true;
5691 return num;
5694 /* Creation function node for DECL, using NAME, and return the index
5695 of the variable we've created for the function. If NONLOCAL_p, create
5696 initial constraints. */
5698 static varinfo_t
5699 create_function_info_for (tree decl, const char *name, bool add_id,
5700 bool nonlocal_p)
5702 struct function *fn = DECL_STRUCT_FUNCTION (decl);
5703 varinfo_t vi, prev_vi;
5704 tree arg;
5705 unsigned int i;
5706 bool is_varargs = false;
5707 unsigned int num_args = count_num_arguments (decl, &is_varargs);
5709 /* Create the variable info. */
5711 vi = new_var_info (decl, name, add_id);
5712 vi->offset = 0;
5713 vi->size = 1;
5714 vi->fullsize = fi_parm_base + num_args;
5715 vi->is_fn_info = 1;
5716 vi->may_have_pointers = false;
5717 if (is_varargs)
5718 vi->fullsize = ~0;
5719 insert_vi_for_tree (vi->decl, vi);
5721 prev_vi = vi;
5723 /* Create a variable for things the function clobbers and one for
5724 things the function uses. */
5726 varinfo_t clobbervi, usevi;
5727 const char *newname;
5728 char *tempname;
5730 tempname = xasprintf ("%s.clobber", name);
5731 newname = ggc_strdup (tempname);
5732 free (tempname);
5734 clobbervi = new_var_info (NULL, newname, false);
5735 clobbervi->offset = fi_clobbers;
5736 clobbervi->size = 1;
5737 clobbervi->fullsize = vi->fullsize;
5738 clobbervi->is_full_var = true;
5739 clobbervi->is_global_var = false;
5740 clobbervi->is_reg_var = true;
5742 gcc_assert (prev_vi->offset < clobbervi->offset);
5743 prev_vi->next = clobbervi->id;
5744 prev_vi = clobbervi;
5746 tempname = xasprintf ("%s.use", name);
5747 newname = ggc_strdup (tempname);
5748 free (tempname);
5750 usevi = new_var_info (NULL, newname, false);
5751 usevi->offset = fi_uses;
5752 usevi->size = 1;
5753 usevi->fullsize = vi->fullsize;
5754 usevi->is_full_var = true;
5755 usevi->is_global_var = false;
5756 usevi->is_reg_var = true;
5758 gcc_assert (prev_vi->offset < usevi->offset);
5759 prev_vi->next = usevi->id;
5760 prev_vi = usevi;
5763 /* And one for the static chain. */
5764 if (fn->static_chain_decl != NULL_TREE)
5766 varinfo_t chainvi;
5767 const char *newname;
5768 char *tempname;
5770 tempname = xasprintf ("%s.chain", name);
5771 newname = ggc_strdup (tempname);
5772 free (tempname);
5774 chainvi = new_var_info (fn->static_chain_decl, newname, false);
5775 chainvi->offset = fi_static_chain;
5776 chainvi->size = 1;
5777 chainvi->fullsize = vi->fullsize;
5778 chainvi->is_full_var = true;
5779 chainvi->is_global_var = false;
5781 insert_vi_for_tree (fn->static_chain_decl, chainvi);
5783 if (nonlocal_p
5784 && chainvi->may_have_pointers)
5785 make_constraint_from (chainvi, nonlocal_id);
5787 gcc_assert (prev_vi->offset < chainvi->offset);
5788 prev_vi->next = chainvi->id;
5789 prev_vi = chainvi;
5792 /* Create a variable for the return var. */
5793 if (DECL_RESULT (decl) != NULL
5794 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
5796 varinfo_t resultvi;
5797 const char *newname;
5798 char *tempname;
5799 tree resultdecl = decl;
5801 if (DECL_RESULT (decl))
5802 resultdecl = DECL_RESULT (decl);
5804 tempname = xasprintf ("%s.result", name);
5805 newname = ggc_strdup (tempname);
5806 free (tempname);
5808 resultvi = new_var_info (resultdecl, newname, false);
5809 resultvi->offset = fi_result;
5810 resultvi->size = 1;
5811 resultvi->fullsize = vi->fullsize;
5812 resultvi->is_full_var = true;
5813 if (DECL_RESULT (decl))
5814 resultvi->may_have_pointers = true;
5816 if (DECL_RESULT (decl))
5817 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
5819 if (nonlocal_p
5820 && DECL_RESULT (decl)
5821 && DECL_BY_REFERENCE (DECL_RESULT (decl)))
5822 make_constraint_from (resultvi, nonlocal_id);
5824 gcc_assert (prev_vi->offset < resultvi->offset);
5825 prev_vi->next = resultvi->id;
5826 prev_vi = resultvi;
5829 /* We also need to make function return values escape. Nothing
5830 escapes by returning from main though. */
5831 if (nonlocal_p
5832 && !MAIN_NAME_P (DECL_NAME (decl)))
5834 varinfo_t fi, rvi;
5835 fi = lookup_vi_for_tree (decl);
5836 rvi = first_vi_for_offset (fi, fi_result);
5837 if (rvi && rvi->offset == fi_result)
5838 make_copy_constraint (get_varinfo (escaped_id), rvi->id);
5841 /* Set up variables for each argument. */
5842 arg = DECL_ARGUMENTS (decl);
5843 for (i = 0; i < num_args; i++)
5845 varinfo_t argvi;
5846 const char *newname;
5847 char *tempname;
5848 tree argdecl = decl;
5850 if (arg)
5851 argdecl = arg;
5853 tempname = xasprintf ("%s.arg%d", name, i);
5854 newname = ggc_strdup (tempname);
5855 free (tempname);
5857 argvi = new_var_info (argdecl, newname, false);
5858 argvi->offset = fi_parm_base + i;
5859 argvi->size = 1;
5860 argvi->is_full_var = true;
5861 argvi->fullsize = vi->fullsize;
5862 if (arg)
5863 argvi->may_have_pointers = true;
5865 if (arg)
5866 insert_vi_for_tree (arg, argvi);
5868 if (nonlocal_p
5869 && argvi->may_have_pointers)
5870 make_constraint_from (argvi, nonlocal_id);
5872 gcc_assert (prev_vi->offset < argvi->offset);
5873 prev_vi->next = argvi->id;
5874 prev_vi = argvi;
5875 if (arg)
5876 arg = DECL_CHAIN (arg);
5879 /* Add one representative for all further args. */
5880 if (is_varargs)
5882 varinfo_t argvi;
5883 const char *newname;
5884 char *tempname;
5885 tree decl;
5887 tempname = xasprintf ("%s.varargs", name);
5888 newname = ggc_strdup (tempname);
5889 free (tempname);
5891 /* We need sth that can be pointed to for va_start. */
5892 decl = build_fake_var_decl (ptr_type_node);
5894 argvi = new_var_info (decl, newname, false);
5895 argvi->offset = fi_parm_base + num_args;
5896 argvi->size = ~0;
5897 argvi->is_full_var = true;
5898 argvi->is_heap_var = true;
5899 argvi->fullsize = vi->fullsize;
5901 if (nonlocal_p
5902 && argvi->may_have_pointers)
5903 make_constraint_from (argvi, nonlocal_id);
5905 gcc_assert (prev_vi->offset < argvi->offset);
5906 prev_vi->next = argvi->id;
5907 prev_vi = argvi;
5910 return vi;
5914 /* Return true if FIELDSTACK contains fields that overlap.
5915 FIELDSTACK is assumed to be sorted by offset. */
5917 static bool
5918 check_for_overlaps (vec<fieldoff_s> fieldstack)
5920 fieldoff_s *fo = NULL;
5921 unsigned int i;
5922 HOST_WIDE_INT lastoffset = -1;
5924 FOR_EACH_VEC_ELT (fieldstack, i, fo)
5926 if (fo->offset == lastoffset)
5927 return true;
5928 lastoffset = fo->offset;
5930 return false;
5933 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5934 This will also create any varinfo structures necessary for fields
5935 of DECL. DECL is a function parameter if HANDLE_PARAM is set.
5936 HANDLED_STRUCT_TYPE is used to register struct types reached by following
5937 restrict pointers. This is needed to prevent infinite recursion.
5938 If ADD_RESTRICT, pretend that the pointer NAME is restrict even if DECL
5939 does not advertise it. */
5941 static varinfo_t
5942 create_variable_info_for_1 (tree decl, const char *name, bool add_id,
5943 bool handle_param, bitmap handled_struct_type,
5944 bool add_restrict = false)
5946 varinfo_t vi, newvi;
5947 tree decl_type = TREE_TYPE (decl);
5948 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
5949 auto_vec<fieldoff_s> fieldstack;
5950 fieldoff_s *fo;
5951 unsigned int i;
5953 if (!declsize
5954 || !tree_fits_uhwi_p (declsize))
5956 vi = new_var_info (decl, name, add_id);
5957 vi->offset = 0;
5958 vi->size = ~0;
5959 vi->fullsize = ~0;
5960 vi->is_unknown_size_var = true;
5961 vi->is_full_var = true;
5962 vi->may_have_pointers = true;
5963 return vi;
5966 /* Collect field information. */
5967 if (use_field_sensitive
5968 && var_can_have_subvars (decl)
5969 /* ??? Force us to not use subfields for globals in IPA mode.
5970 Else we'd have to parse arbitrary initializers. */
5971 && !(in_ipa_mode
5972 && is_global_var (decl)))
5974 fieldoff_s *fo = NULL;
5975 bool notokay = false;
5976 unsigned int i;
5978 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
5980 for (i = 0; !notokay && fieldstack.iterate (i, &fo); i++)
5981 if (fo->has_unknown_size
5982 || fo->offset < 0)
5984 notokay = true;
5985 break;
5988 /* We can't sort them if we have a field with a variable sized type,
5989 which will make notokay = true. In that case, we are going to return
5990 without creating varinfos for the fields anyway, so sorting them is a
5991 waste to boot. */
5992 if (!notokay)
5994 sort_fieldstack (fieldstack);
5995 /* Due to some C++ FE issues, like PR 22488, we might end up
5996 what appear to be overlapping fields even though they,
5997 in reality, do not overlap. Until the C++ FE is fixed,
5998 we will simply disable field-sensitivity for these cases. */
5999 notokay = check_for_overlaps (fieldstack);
6002 if (notokay)
6003 fieldstack.release ();
6006 /* If we didn't end up collecting sub-variables create a full
6007 variable for the decl. */
6008 if (fieldstack.length () == 0
6009 || fieldstack.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
6011 vi = new_var_info (decl, name, add_id);
6012 vi->offset = 0;
6013 vi->may_have_pointers = true;
6014 vi->fullsize = tree_to_uhwi (declsize);
6015 vi->size = vi->fullsize;
6016 vi->is_full_var = true;
6017 if (POINTER_TYPE_P (decl_type)
6018 && (TYPE_RESTRICT (decl_type) || add_restrict))
6019 vi->only_restrict_pointers = 1;
6020 if (vi->only_restrict_pointers
6021 && !type_contains_placeholder_p (TREE_TYPE (decl_type))
6022 && handle_param
6023 && !bitmap_bit_p (handled_struct_type,
6024 TYPE_UID (TREE_TYPE (decl_type))))
6026 varinfo_t rvi;
6027 tree heapvar = build_fake_var_decl (TREE_TYPE (decl_type));
6028 DECL_EXTERNAL (heapvar) = 1;
6029 if (var_can_have_subvars (heapvar))
6030 bitmap_set_bit (handled_struct_type,
6031 TYPE_UID (TREE_TYPE (decl_type)));
6032 rvi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS", true,
6033 true, handled_struct_type);
6034 if (var_can_have_subvars (heapvar))
6035 bitmap_clear_bit (handled_struct_type,
6036 TYPE_UID (TREE_TYPE (decl_type)));
6037 rvi->is_restrict_var = 1;
6038 insert_vi_for_tree (heapvar, rvi);
6039 make_constraint_from (vi, rvi->id);
6040 make_param_constraints (rvi);
6042 fieldstack.release ();
6043 return vi;
6046 vi = new_var_info (decl, name, add_id);
6047 vi->fullsize = tree_to_uhwi (declsize);
6048 if (fieldstack.length () == 1)
6049 vi->is_full_var = true;
6050 for (i = 0, newvi = vi;
6051 fieldstack.iterate (i, &fo);
6052 ++i, newvi = vi_next (newvi))
6054 const char *newname = NULL;
6055 char *tempname;
6057 if (dump_file)
6059 if (fieldstack.length () != 1)
6061 tempname
6062 = xasprintf ("%s." HOST_WIDE_INT_PRINT_DEC
6063 "+" HOST_WIDE_INT_PRINT_DEC, name,
6064 fo->offset, fo->size);
6065 newname = ggc_strdup (tempname);
6066 free (tempname);
6069 else
6070 newname = "NULL";
6072 if (newname)
6073 newvi->name = newname;
6074 newvi->offset = fo->offset;
6075 newvi->size = fo->size;
6076 newvi->fullsize = vi->fullsize;
6077 newvi->may_have_pointers = fo->may_have_pointers;
6078 newvi->only_restrict_pointers = fo->only_restrict_pointers;
6079 if (handle_param
6080 && newvi->only_restrict_pointers
6081 && !type_contains_placeholder_p (fo->restrict_pointed_type)
6082 && !bitmap_bit_p (handled_struct_type,
6083 TYPE_UID (fo->restrict_pointed_type)))
6085 varinfo_t rvi;
6086 tree heapvar = build_fake_var_decl (fo->restrict_pointed_type);
6087 DECL_EXTERNAL (heapvar) = 1;
6088 if (var_can_have_subvars (heapvar))
6089 bitmap_set_bit (handled_struct_type,
6090 TYPE_UID (fo->restrict_pointed_type));
6091 rvi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS", true,
6092 true, handled_struct_type);
6093 if (var_can_have_subvars (heapvar))
6094 bitmap_clear_bit (handled_struct_type,
6095 TYPE_UID (fo->restrict_pointed_type));
6096 rvi->is_restrict_var = 1;
6097 insert_vi_for_tree (heapvar, rvi);
6098 make_constraint_from (newvi, rvi->id);
6099 make_param_constraints (rvi);
6101 if (i + 1 < fieldstack.length ())
6103 varinfo_t tem = new_var_info (decl, name, false);
6104 newvi->next = tem->id;
6105 tem->head = vi->id;
6109 return vi;
6112 static unsigned int
6113 create_variable_info_for (tree decl, const char *name, bool add_id)
6115 /* First see if we are dealing with an ifunc resolver call and
6116 assiociate that with a call to the resolver function result. */
6117 cgraph_node *node;
6118 if (in_ipa_mode
6119 && TREE_CODE (decl) == FUNCTION_DECL
6120 && (node = cgraph_node::get (decl))
6121 && node->ifunc_resolver)
6123 varinfo_t fi = get_vi_for_tree (node->get_alias_target ()->decl);
6124 constraint_expr rhs
6125 = get_function_part_constraint (fi, fi_result);
6126 fi = new_var_info (NULL_TREE, "ifuncres", true);
6127 fi->is_reg_var = true;
6128 constraint_expr lhs;
6129 lhs.type = SCALAR;
6130 lhs.var = fi->id;
6131 lhs.offset = 0;
6132 process_constraint (new_constraint (lhs, rhs));
6133 insert_vi_for_tree (decl, fi);
6134 return fi->id;
6137 varinfo_t vi = create_variable_info_for_1 (decl, name, add_id, false, NULL);
6138 unsigned int id = vi->id;
6140 insert_vi_for_tree (decl, vi);
6142 if (!VAR_P (decl))
6143 return id;
6145 /* Create initial constraints for globals. */
6146 for (; vi; vi = vi_next (vi))
6148 if (!vi->may_have_pointers
6149 || !vi->is_global_var)
6150 continue;
6152 /* Mark global restrict qualified pointers. */
6153 if ((POINTER_TYPE_P (TREE_TYPE (decl))
6154 && TYPE_RESTRICT (TREE_TYPE (decl)))
6155 || vi->only_restrict_pointers)
6157 varinfo_t rvi
6158 = make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT",
6159 true);
6160 /* ??? For now exclude reads from globals as restrict sources
6161 if those are not (indirectly) from incoming parameters. */
6162 rvi->is_restrict_var = false;
6163 continue;
6166 /* In non-IPA mode the initializer from nonlocal is all we need. */
6167 if (!in_ipa_mode
6168 || DECL_HARD_REGISTER (decl))
6169 make_copy_constraint (vi, nonlocal_id);
6171 /* In IPA mode parse the initializer and generate proper constraints
6172 for it. */
6173 else
6175 varpool_node *vnode = varpool_node::get (decl);
6177 /* For escaped variables initialize them from nonlocal. */
6178 if (!vnode->all_refs_explicit_p ())
6179 make_copy_constraint (vi, nonlocal_id);
6181 /* If this is a global variable with an initializer and we are in
6182 IPA mode generate constraints for it. */
6183 ipa_ref *ref;
6184 for (unsigned idx = 0; vnode->iterate_reference (idx, ref); ++idx)
6186 auto_vec<ce_s> rhsc;
6187 struct constraint_expr lhs, *rhsp;
6188 unsigned i;
6189 get_constraint_for_address_of (ref->referred->decl, &rhsc);
6190 lhs.var = vi->id;
6191 lhs.offset = 0;
6192 lhs.type = SCALAR;
6193 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
6194 process_constraint (new_constraint (lhs, *rhsp));
6195 /* If this is a variable that escapes from the unit
6196 the initializer escapes as well. */
6197 if (!vnode->all_refs_explicit_p ())
6199 lhs.var = escaped_id;
6200 lhs.offset = 0;
6201 lhs.type = SCALAR;
6202 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
6203 process_constraint (new_constraint (lhs, *rhsp));
6209 return id;
6212 /* Print out the points-to solution for VAR to FILE. */
6214 static void
6215 dump_solution_for_var (FILE *file, unsigned int var)
6217 varinfo_t vi = get_varinfo (var);
6218 unsigned int i;
6219 bitmap_iterator bi;
6221 /* Dump the solution for unified vars anyway, this avoids difficulties
6222 in scanning dumps in the testsuite. */
6223 fprintf (file, "%s = { ", vi->name);
6224 vi = get_varinfo (find (var));
6225 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
6226 fprintf (file, "%s ", get_varinfo (i)->name);
6227 fprintf (file, "}");
6229 /* But note when the variable was unified. */
6230 if (vi->id != var)
6231 fprintf (file, " same as %s", vi->name);
6233 fprintf (file, "\n");
6236 /* Print the points-to solution for VAR to stderr. */
6238 DEBUG_FUNCTION void
6239 debug_solution_for_var (unsigned int var)
6241 dump_solution_for_var (stderr, var);
6244 /* Register the constraints for function parameter related VI. */
6246 static void
6247 make_param_constraints (varinfo_t vi)
6249 for (; vi; vi = vi_next (vi))
6251 if (vi->only_restrict_pointers)
6253 else if (vi->may_have_pointers)
6254 make_constraint_from (vi, nonlocal_id);
6256 if (vi->is_full_var)
6257 break;
6261 /* Create varinfo structures for all of the variables in the
6262 function for intraprocedural mode. */
6264 static void
6265 intra_create_variable_infos (struct function *fn)
6267 tree t;
6268 bitmap handled_struct_type = NULL;
6269 bool this_parm_in_ctor = DECL_CXX_CONSTRUCTOR_P (fn->decl);
6271 /* For each incoming pointer argument arg, create the constraint ARG
6272 = NONLOCAL or a dummy variable if it is a restrict qualified
6273 passed-by-reference argument. */
6274 for (t = DECL_ARGUMENTS (fn->decl); t; t = DECL_CHAIN (t))
6276 if (handled_struct_type == NULL)
6277 handled_struct_type = BITMAP_ALLOC (NULL);
6279 varinfo_t p
6280 = create_variable_info_for_1 (t, alias_get_name (t), false, true,
6281 handled_struct_type, this_parm_in_ctor);
6282 insert_vi_for_tree (t, p);
6284 make_param_constraints (p);
6286 this_parm_in_ctor = false;
6289 if (handled_struct_type != NULL)
6290 BITMAP_FREE (handled_struct_type);
6292 /* Add a constraint for a result decl that is passed by reference. */
6293 if (DECL_RESULT (fn->decl)
6294 && DECL_BY_REFERENCE (DECL_RESULT (fn->decl)))
6296 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (fn->decl));
6298 for (p = result_vi; p; p = vi_next (p))
6299 make_constraint_from (p, nonlocal_id);
6302 /* Add a constraint for the incoming static chain parameter. */
6303 if (fn->static_chain_decl != NULL_TREE)
6305 varinfo_t p, chain_vi = get_vi_for_tree (fn->static_chain_decl);
6307 for (p = chain_vi; p; p = vi_next (p))
6308 make_constraint_from (p, nonlocal_id);
6312 /* Structure used to put solution bitmaps in a hashtable so they can
6313 be shared among variables with the same points-to set. */
6315 typedef struct shared_bitmap_info
6317 bitmap pt_vars;
6318 hashval_t hashcode;
6319 } *shared_bitmap_info_t;
6320 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
6322 /* Shared_bitmap hashtable helpers. */
6324 struct shared_bitmap_hasher : free_ptr_hash <shared_bitmap_info>
6326 static inline hashval_t hash (const shared_bitmap_info *);
6327 static inline bool equal (const shared_bitmap_info *,
6328 const shared_bitmap_info *);
6331 /* Hash function for a shared_bitmap_info_t */
6333 inline hashval_t
6334 shared_bitmap_hasher::hash (const shared_bitmap_info *bi)
6336 return bi->hashcode;
6339 /* Equality function for two shared_bitmap_info_t's. */
6341 inline bool
6342 shared_bitmap_hasher::equal (const shared_bitmap_info *sbi1,
6343 const shared_bitmap_info *sbi2)
6345 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
6348 /* Shared_bitmap hashtable. */
6350 static hash_table<shared_bitmap_hasher> *shared_bitmap_table;
6352 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
6353 existing instance if there is one, NULL otherwise. */
6355 static bitmap
6356 shared_bitmap_lookup (bitmap pt_vars)
6358 shared_bitmap_info **slot;
6359 struct shared_bitmap_info sbi;
6361 sbi.pt_vars = pt_vars;
6362 sbi.hashcode = bitmap_hash (pt_vars);
6364 slot = shared_bitmap_table->find_slot (&sbi, NO_INSERT);
6365 if (!slot)
6366 return NULL;
6367 else
6368 return (*slot)->pt_vars;
6372 /* Add a bitmap to the shared bitmap hashtable. */
6374 static void
6375 shared_bitmap_add (bitmap pt_vars)
6377 shared_bitmap_info **slot;
6378 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
6380 sbi->pt_vars = pt_vars;
6381 sbi->hashcode = bitmap_hash (pt_vars);
6383 slot = shared_bitmap_table->find_slot (sbi, INSERT);
6384 gcc_assert (!*slot);
6385 *slot = sbi;
6389 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
6391 static void
6392 set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt,
6393 tree fndecl)
6395 unsigned int i;
6396 bitmap_iterator bi;
6397 varinfo_t escaped_vi = get_varinfo (find (escaped_id));
6398 bool everything_escaped
6399 = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id);
6401 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
6403 varinfo_t vi = get_varinfo (i);
6405 /* The only artificial variables that are allowed in a may-alias
6406 set are heap variables. */
6407 if (vi->is_artificial_var && !vi->is_heap_var)
6408 continue;
6410 if (everything_escaped
6411 || (escaped_vi->solution
6412 && bitmap_bit_p (escaped_vi->solution, i)))
6414 pt->vars_contains_escaped = true;
6415 pt->vars_contains_escaped_heap = vi->is_heap_var;
6418 if (vi->is_restrict_var)
6419 pt->vars_contains_restrict = true;
6421 if (VAR_P (vi->decl)
6422 || TREE_CODE (vi->decl) == PARM_DECL
6423 || TREE_CODE (vi->decl) == RESULT_DECL)
6425 /* If we are in IPA mode we will not recompute points-to
6426 sets after inlining so make sure they stay valid. */
6427 if (in_ipa_mode
6428 && !DECL_PT_UID_SET_P (vi->decl))
6429 SET_DECL_PT_UID (vi->decl, DECL_UID (vi->decl));
6431 /* Add the decl to the points-to set. Note that the points-to
6432 set contains global variables. */
6433 bitmap_set_bit (into, DECL_PT_UID (vi->decl));
6434 if (vi->is_global_var
6435 /* In IPA mode the escaped_heap trick doesn't work as
6436 ESCAPED is escaped from the unit but
6437 pt_solution_includes_global needs to answer true for
6438 all variables not automatic within a function.
6439 For the same reason is_global_var is not the
6440 correct flag to track - local variables from other
6441 functions also need to be considered global.
6442 Conveniently all HEAP vars are not put in function
6443 scope. */
6444 || (in_ipa_mode
6445 && fndecl
6446 && ! auto_var_in_fn_p (vi->decl, fndecl)))
6447 pt->vars_contains_nonlocal = true;
6449 /* If we have a variable that is interposable record that fact
6450 for pointer comparison simplification. */
6451 if (VAR_P (vi->decl)
6452 && (TREE_STATIC (vi->decl) || DECL_EXTERNAL (vi->decl))
6453 && ! decl_binds_to_current_def_p (vi->decl))
6454 pt->vars_contains_interposable = true;
6457 else if (TREE_CODE (vi->decl) == FUNCTION_DECL
6458 || TREE_CODE (vi->decl) == LABEL_DECL)
6460 /* Nothing should read/write from/to code so we can
6461 save bits by not including them in the points-to bitmaps.
6462 Still mark the points-to set as containing global memory
6463 to make code-patching possible - see PR70128. */
6464 pt->vars_contains_nonlocal = true;
6470 /* Compute the points-to solution *PT for the variable VI. */
6472 static struct pt_solution
6473 find_what_var_points_to (tree fndecl, varinfo_t orig_vi)
6475 unsigned int i;
6476 bitmap_iterator bi;
6477 bitmap finished_solution;
6478 bitmap result;
6479 varinfo_t vi;
6480 struct pt_solution *pt;
6482 /* This variable may have been collapsed, let's get the real
6483 variable. */
6484 vi = get_varinfo (find (orig_vi->id));
6486 /* See if we have already computed the solution and return it. */
6487 pt_solution **slot = &final_solutions->get_or_insert (vi);
6488 if (*slot != NULL)
6489 return **slot;
6491 *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
6492 memset (pt, 0, sizeof (struct pt_solution));
6494 /* Translate artificial variables into SSA_NAME_PTR_INFO
6495 attributes. */
6496 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
6498 varinfo_t vi = get_varinfo (i);
6500 if (vi->is_artificial_var)
6502 if (vi->id == nothing_id)
6503 pt->null = 1;
6504 else if (vi->id == escaped_id)
6506 if (in_ipa_mode)
6507 pt->ipa_escaped = 1;
6508 else
6509 pt->escaped = 1;
6510 /* Expand some special vars of ESCAPED in-place here. */
6511 varinfo_t evi = get_varinfo (find (escaped_id));
6512 if (bitmap_bit_p (evi->solution, nonlocal_id))
6513 pt->nonlocal = 1;
6515 else if (vi->id == nonlocal_id)
6516 pt->nonlocal = 1;
6517 else if (vi->is_heap_var)
6518 /* We represent heapvars in the points-to set properly. */
6520 else if (vi->id == string_id)
6521 /* Nobody cares - STRING_CSTs are read-only entities. */
6523 else if (vi->id == anything_id
6524 || vi->id == integer_id)
6525 pt->anything = 1;
6529 /* Instead of doing extra work, simply do not create
6530 elaborate points-to information for pt_anything pointers. */
6531 if (pt->anything)
6532 return *pt;
6534 /* Share the final set of variables when possible. */
6535 finished_solution = BITMAP_GGC_ALLOC ();
6536 stats.points_to_sets_created++;
6538 set_uids_in_ptset (finished_solution, vi->solution, pt, fndecl);
6539 result = shared_bitmap_lookup (finished_solution);
6540 if (!result)
6542 shared_bitmap_add (finished_solution);
6543 pt->vars = finished_solution;
6545 else
6547 pt->vars = result;
6548 bitmap_clear (finished_solution);
6551 return *pt;
6554 /* Given a pointer variable P, fill in its points-to set. */
6556 static void
6557 find_what_p_points_to (tree fndecl, tree p)
6559 struct ptr_info_def *pi;
6560 tree lookup_p = p;
6561 varinfo_t vi;
6562 bool nonnull = get_ptr_nonnull (p);
6564 /* For parameters, get at the points-to set for the actual parm
6565 decl. */
6566 if (TREE_CODE (p) == SSA_NAME
6567 && SSA_NAME_IS_DEFAULT_DEF (p)
6568 && (TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
6569 || TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL))
6570 lookup_p = SSA_NAME_VAR (p);
6572 vi = lookup_vi_for_tree (lookup_p);
6573 if (!vi)
6574 return;
6576 pi = get_ptr_info (p);
6577 pi->pt = find_what_var_points_to (fndecl, vi);
6578 /* Conservatively set to NULL from PTA (to true). */
6579 pi->pt.null = 1;
6580 /* Preserve pointer nonnull computed by VRP. See get_ptr_nonnull
6581 in gcc/tree-ssaname.c for more information. */
6582 if (nonnull)
6583 set_ptr_nonnull (p);
6587 /* Query statistics for points-to solutions. */
6589 static struct {
6590 unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
6591 unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
6592 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
6593 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
6594 } pta_stats;
6596 void
6597 dump_pta_stats (FILE *s)
6599 fprintf (s, "\nPTA query stats:\n");
6600 fprintf (s, " pt_solution_includes: "
6601 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
6602 HOST_WIDE_INT_PRINT_DEC" queries\n",
6603 pta_stats.pt_solution_includes_no_alias,
6604 pta_stats.pt_solution_includes_no_alias
6605 + pta_stats.pt_solution_includes_may_alias);
6606 fprintf (s, " pt_solutions_intersect: "
6607 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
6608 HOST_WIDE_INT_PRINT_DEC" queries\n",
6609 pta_stats.pt_solutions_intersect_no_alias,
6610 pta_stats.pt_solutions_intersect_no_alias
6611 + pta_stats.pt_solutions_intersect_may_alias);
6615 /* Reset the points-to solution *PT to a conservative default
6616 (point to anything). */
6618 void
6619 pt_solution_reset (struct pt_solution *pt)
6621 memset (pt, 0, sizeof (struct pt_solution));
6622 pt->anything = true;
6623 pt->null = true;
6626 /* Set the points-to solution *PT to point only to the variables
6627 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
6628 global variables and VARS_CONTAINS_RESTRICT specifies whether
6629 it contains restrict tag variables. */
6631 void
6632 pt_solution_set (struct pt_solution *pt, bitmap vars,
6633 bool vars_contains_nonlocal)
6635 memset (pt, 0, sizeof (struct pt_solution));
6636 pt->vars = vars;
6637 pt->vars_contains_nonlocal = vars_contains_nonlocal;
6638 pt->vars_contains_escaped
6639 = (cfun->gimple_df->escaped.anything
6640 || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars));
6643 /* Set the points-to solution *PT to point only to the variable VAR. */
6645 void
6646 pt_solution_set_var (struct pt_solution *pt, tree var)
6648 memset (pt, 0, sizeof (struct pt_solution));
6649 pt->vars = BITMAP_GGC_ALLOC ();
6650 bitmap_set_bit (pt->vars, DECL_PT_UID (var));
6651 pt->vars_contains_nonlocal = is_global_var (var);
6652 pt->vars_contains_escaped
6653 = (cfun->gimple_df->escaped.anything
6654 || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var)));
6657 /* Computes the union of the points-to solutions *DEST and *SRC and
6658 stores the result in *DEST. This changes the points-to bitmap
6659 of *DEST and thus may not be used if that might be shared.
6660 The points-to bitmap of *SRC and *DEST will not be shared after
6661 this function if they were not before. */
6663 static void
6664 pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src)
6666 dest->anything |= src->anything;
6667 if (dest->anything)
6669 pt_solution_reset (dest);
6670 return;
6673 dest->nonlocal |= src->nonlocal;
6674 dest->escaped |= src->escaped;
6675 dest->ipa_escaped |= src->ipa_escaped;
6676 dest->null |= src->null;
6677 dest->vars_contains_nonlocal |= src->vars_contains_nonlocal;
6678 dest->vars_contains_escaped |= src->vars_contains_escaped;
6679 dest->vars_contains_escaped_heap |= src->vars_contains_escaped_heap;
6680 if (!src->vars)
6681 return;
6683 if (!dest->vars)
6684 dest->vars = BITMAP_GGC_ALLOC ();
6685 bitmap_ior_into (dest->vars, src->vars);
6688 /* Return true if the points-to solution *PT is empty. */
6690 bool
6691 pt_solution_empty_p (struct pt_solution *pt)
6693 if (pt->anything
6694 || pt->nonlocal)
6695 return false;
6697 if (pt->vars
6698 && !bitmap_empty_p (pt->vars))
6699 return false;
6701 /* If the solution includes ESCAPED, check if that is empty. */
6702 if (pt->escaped
6703 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
6704 return false;
6706 /* If the solution includes ESCAPED, check if that is empty. */
6707 if (pt->ipa_escaped
6708 && !pt_solution_empty_p (&ipa_escaped_pt))
6709 return false;
6711 return true;
6714 /* Return true if the points-to solution *PT only point to a single var, and
6715 return the var uid in *UID. */
6717 bool
6718 pt_solution_singleton_or_null_p (struct pt_solution *pt, unsigned *uid)
6720 if (pt->anything || pt->nonlocal || pt->escaped || pt->ipa_escaped
6721 || pt->vars == NULL
6722 || !bitmap_single_bit_set_p (pt->vars))
6723 return false;
6725 *uid = bitmap_first_set_bit (pt->vars);
6726 return true;
6729 /* Return true if the points-to solution *PT includes global memory. */
6731 bool
6732 pt_solution_includes_global (struct pt_solution *pt)
6734 if (pt->anything
6735 || pt->nonlocal
6736 || pt->vars_contains_nonlocal
6737 /* The following is a hack to make the malloc escape hack work.
6738 In reality we'd need different sets for escaped-through-return
6739 and escaped-to-callees and passes would need to be updated. */
6740 || pt->vars_contains_escaped_heap)
6741 return true;
6743 /* 'escaped' is also a placeholder so we have to look into it. */
6744 if (pt->escaped)
6745 return pt_solution_includes_global (&cfun->gimple_df->escaped);
6747 if (pt->ipa_escaped)
6748 return pt_solution_includes_global (&ipa_escaped_pt);
6750 return false;
6753 /* Return true if the points-to solution *PT includes the variable
6754 declaration DECL. */
6756 static bool
6757 pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
6759 if (pt->anything)
6760 return true;
6762 if (pt->nonlocal
6763 && is_global_var (decl))
6764 return true;
6766 if (pt->vars
6767 && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
6768 return true;
6770 /* If the solution includes ESCAPED, check it. */
6771 if (pt->escaped
6772 && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
6773 return true;
6775 /* If the solution includes ESCAPED, check it. */
6776 if (pt->ipa_escaped
6777 && pt_solution_includes_1 (&ipa_escaped_pt, decl))
6778 return true;
6780 return false;
6783 bool
6784 pt_solution_includes (struct pt_solution *pt, const_tree decl)
6786 bool res = pt_solution_includes_1 (pt, decl);
6787 if (res)
6788 ++pta_stats.pt_solution_includes_may_alias;
6789 else
6790 ++pta_stats.pt_solution_includes_no_alias;
6791 return res;
6794 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
6795 intersection. */
6797 static bool
6798 pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
6800 if (pt1->anything || pt2->anything)
6801 return true;
6803 /* If either points to unknown global memory and the other points to
6804 any global memory they alias. */
6805 if ((pt1->nonlocal
6806 && (pt2->nonlocal
6807 || pt2->vars_contains_nonlocal))
6808 || (pt2->nonlocal
6809 && pt1->vars_contains_nonlocal))
6810 return true;
6812 /* If either points to all escaped memory and the other points to
6813 any escaped memory they alias. */
6814 if ((pt1->escaped
6815 && (pt2->escaped
6816 || pt2->vars_contains_escaped))
6817 || (pt2->escaped
6818 && pt1->vars_contains_escaped))
6819 return true;
6821 /* Check the escaped solution if required.
6822 ??? Do we need to check the local against the IPA escaped sets? */
6823 if ((pt1->ipa_escaped || pt2->ipa_escaped)
6824 && !pt_solution_empty_p (&ipa_escaped_pt))
6826 /* If both point to escaped memory and that solution
6827 is not empty they alias. */
6828 if (pt1->ipa_escaped && pt2->ipa_escaped)
6829 return true;
6831 /* If either points to escaped memory see if the escaped solution
6832 intersects with the other. */
6833 if ((pt1->ipa_escaped
6834 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
6835 || (pt2->ipa_escaped
6836 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
6837 return true;
6840 /* Now both pointers alias if their points-to solution intersects. */
6841 return (pt1->vars
6842 && pt2->vars
6843 && bitmap_intersect_p (pt1->vars, pt2->vars));
6846 bool
6847 pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
6849 bool res = pt_solutions_intersect_1 (pt1, pt2);
6850 if (res)
6851 ++pta_stats.pt_solutions_intersect_may_alias;
6852 else
6853 ++pta_stats.pt_solutions_intersect_no_alias;
6854 return res;
6858 /* Dump points-to information to OUTFILE. */
6860 static void
6861 dump_sa_points_to_info (FILE *outfile)
6863 unsigned int i;
6865 fprintf (outfile, "\nPoints-to sets\n\n");
6867 if (dump_flags & TDF_STATS)
6869 fprintf (outfile, "Stats:\n");
6870 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
6871 fprintf (outfile, "Non-pointer vars: %d\n",
6872 stats.nonpointer_vars);
6873 fprintf (outfile, "Statically unified vars: %d\n",
6874 stats.unified_vars_static);
6875 fprintf (outfile, "Dynamically unified vars: %d\n",
6876 stats.unified_vars_dynamic);
6877 fprintf (outfile, "Iterations: %d\n", stats.iterations);
6878 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
6879 fprintf (outfile, "Number of implicit edges: %d\n",
6880 stats.num_implicit_edges);
6883 for (i = 1; i < varmap.length (); i++)
6885 varinfo_t vi = get_varinfo (i);
6886 if (!vi->may_have_pointers)
6887 continue;
6888 dump_solution_for_var (outfile, i);
6893 /* Debug points-to information to stderr. */
6895 DEBUG_FUNCTION void
6896 debug_sa_points_to_info (void)
6898 dump_sa_points_to_info (stderr);
6902 /* Initialize the always-existing constraint variables for NULL
6903 ANYTHING, READONLY, and INTEGER */
6905 static void
6906 init_base_vars (void)
6908 struct constraint_expr lhs, rhs;
6909 varinfo_t var_anything;
6910 varinfo_t var_nothing;
6911 varinfo_t var_string;
6912 varinfo_t var_escaped;
6913 varinfo_t var_nonlocal;
6914 varinfo_t var_storedanything;
6915 varinfo_t var_integer;
6917 /* Variable ID zero is reserved and should be NULL. */
6918 varmap.safe_push (NULL);
6920 /* Create the NULL variable, used to represent that a variable points
6921 to NULL. */
6922 var_nothing = new_var_info (NULL_TREE, "NULL", false);
6923 gcc_assert (var_nothing->id == nothing_id);
6924 var_nothing->is_artificial_var = 1;
6925 var_nothing->offset = 0;
6926 var_nothing->size = ~0;
6927 var_nothing->fullsize = ~0;
6928 var_nothing->is_special_var = 1;
6929 var_nothing->may_have_pointers = 0;
6930 var_nothing->is_global_var = 0;
6932 /* Create the ANYTHING variable, used to represent that a variable
6933 points to some unknown piece of memory. */
6934 var_anything = new_var_info (NULL_TREE, "ANYTHING", false);
6935 gcc_assert (var_anything->id == anything_id);
6936 var_anything->is_artificial_var = 1;
6937 var_anything->size = ~0;
6938 var_anything->offset = 0;
6939 var_anything->fullsize = ~0;
6940 var_anything->is_special_var = 1;
6942 /* Anything points to anything. This makes deref constraints just
6943 work in the presence of linked list and other p = *p type loops,
6944 by saying that *ANYTHING = ANYTHING. */
6945 lhs.type = SCALAR;
6946 lhs.var = anything_id;
6947 lhs.offset = 0;
6948 rhs.type = ADDRESSOF;
6949 rhs.var = anything_id;
6950 rhs.offset = 0;
6952 /* This specifically does not use process_constraint because
6953 process_constraint ignores all anything = anything constraints, since all
6954 but this one are redundant. */
6955 constraints.safe_push (new_constraint (lhs, rhs));
6957 /* Create the STRING variable, used to represent that a variable
6958 points to a string literal. String literals don't contain
6959 pointers so STRING doesn't point to anything. */
6960 var_string = new_var_info (NULL_TREE, "STRING", false);
6961 gcc_assert (var_string->id == string_id);
6962 var_string->is_artificial_var = 1;
6963 var_string->offset = 0;
6964 var_string->size = ~0;
6965 var_string->fullsize = ~0;
6966 var_string->is_special_var = 1;
6967 var_string->may_have_pointers = 0;
6969 /* Create the ESCAPED variable, used to represent the set of escaped
6970 memory. */
6971 var_escaped = new_var_info (NULL_TREE, "ESCAPED", false);
6972 gcc_assert (var_escaped->id == escaped_id);
6973 var_escaped->is_artificial_var = 1;
6974 var_escaped->offset = 0;
6975 var_escaped->size = ~0;
6976 var_escaped->fullsize = ~0;
6977 var_escaped->is_special_var = 0;
6979 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6980 memory. */
6981 var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL", false);
6982 gcc_assert (var_nonlocal->id == nonlocal_id);
6983 var_nonlocal->is_artificial_var = 1;
6984 var_nonlocal->offset = 0;
6985 var_nonlocal->size = ~0;
6986 var_nonlocal->fullsize = ~0;
6987 var_nonlocal->is_special_var = 1;
6989 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6990 lhs.type = SCALAR;
6991 lhs.var = escaped_id;
6992 lhs.offset = 0;
6993 rhs.type = DEREF;
6994 rhs.var = escaped_id;
6995 rhs.offset = 0;
6996 process_constraint (new_constraint (lhs, rhs));
6998 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6999 whole variable escapes. */
7000 lhs.type = SCALAR;
7001 lhs.var = escaped_id;
7002 lhs.offset = 0;
7003 rhs.type = SCALAR;
7004 rhs.var = escaped_id;
7005 rhs.offset = UNKNOWN_OFFSET;
7006 process_constraint (new_constraint (lhs, rhs));
7008 /* *ESCAPED = NONLOCAL. This is true because we have to assume
7009 everything pointed to by escaped points to what global memory can
7010 point to. */
7011 lhs.type = DEREF;
7012 lhs.var = escaped_id;
7013 lhs.offset = 0;
7014 rhs.type = SCALAR;
7015 rhs.var = nonlocal_id;
7016 rhs.offset = 0;
7017 process_constraint (new_constraint (lhs, rhs));
7019 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
7020 global memory may point to global memory and escaped memory. */
7021 lhs.type = SCALAR;
7022 lhs.var = nonlocal_id;
7023 lhs.offset = 0;
7024 rhs.type = ADDRESSOF;
7025 rhs.var = nonlocal_id;
7026 rhs.offset = 0;
7027 process_constraint (new_constraint (lhs, rhs));
7028 rhs.type = ADDRESSOF;
7029 rhs.var = escaped_id;
7030 rhs.offset = 0;
7031 process_constraint (new_constraint (lhs, rhs));
7033 /* Create the STOREDANYTHING variable, used to represent the set of
7034 variables stored to *ANYTHING. */
7035 var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING", false);
7036 gcc_assert (var_storedanything->id == storedanything_id);
7037 var_storedanything->is_artificial_var = 1;
7038 var_storedanything->offset = 0;
7039 var_storedanything->size = ~0;
7040 var_storedanything->fullsize = ~0;
7041 var_storedanything->is_special_var = 0;
7043 /* Create the INTEGER variable, used to represent that a variable points
7044 to what an INTEGER "points to". */
7045 var_integer = new_var_info (NULL_TREE, "INTEGER", false);
7046 gcc_assert (var_integer->id == integer_id);
7047 var_integer->is_artificial_var = 1;
7048 var_integer->size = ~0;
7049 var_integer->fullsize = ~0;
7050 var_integer->offset = 0;
7051 var_integer->is_special_var = 1;
7053 /* INTEGER = ANYTHING, because we don't know where a dereference of
7054 a random integer will point to. */
7055 lhs.type = SCALAR;
7056 lhs.var = integer_id;
7057 lhs.offset = 0;
7058 rhs.type = ADDRESSOF;
7059 rhs.var = anything_id;
7060 rhs.offset = 0;
7061 process_constraint (new_constraint (lhs, rhs));
7064 /* Initialize things necessary to perform PTA */
7066 static void
7067 init_alias_vars (void)
7069 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
7071 bitmap_obstack_initialize (&pta_obstack);
7072 bitmap_obstack_initialize (&oldpta_obstack);
7073 bitmap_obstack_initialize (&predbitmap_obstack);
7075 constraints.create (8);
7076 varmap.create (8);
7077 vi_for_tree = new hash_map<tree, varinfo_t>;
7078 call_stmt_vars = new hash_map<gimple *, varinfo_t>;
7080 memset (&stats, 0, sizeof (stats));
7081 shared_bitmap_table = new hash_table<shared_bitmap_hasher> (511);
7082 init_base_vars ();
7084 gcc_obstack_init (&fake_var_decl_obstack);
7086 final_solutions = new hash_map<varinfo_t, pt_solution *>;
7087 gcc_obstack_init (&final_solutions_obstack);
7090 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
7091 predecessor edges. */
7093 static void
7094 remove_preds_and_fake_succs (constraint_graph_t graph)
7096 unsigned int i;
7098 /* Clear the implicit ref and address nodes from the successor
7099 lists. */
7100 for (i = 1; i < FIRST_REF_NODE; i++)
7102 if (graph->succs[i])
7103 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
7104 FIRST_REF_NODE * 2);
7107 /* Free the successor list for the non-ref nodes. */
7108 for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
7110 if (graph->succs[i])
7111 BITMAP_FREE (graph->succs[i]);
7114 /* Now reallocate the size of the successor list as, and blow away
7115 the predecessor bitmaps. */
7116 graph->size = varmap.length ();
7117 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
7119 free (graph->implicit_preds);
7120 graph->implicit_preds = NULL;
7121 free (graph->preds);
7122 graph->preds = NULL;
7123 bitmap_obstack_release (&predbitmap_obstack);
7126 /* Solve the constraint set. */
7128 static void
7129 solve_constraints (void)
7131 struct scc_info *si;
7133 /* Sort varinfos so that ones that cannot be pointed to are last.
7134 This makes bitmaps more efficient. */
7135 unsigned int *map = XNEWVEC (unsigned int, varmap.length ());
7136 for (unsigned i = 0; i < integer_id + 1; ++i)
7137 map[i] = i;
7138 /* Start with non-register vars (as possibly address-taken), followed
7139 by register vars as conservative set of vars never appearing in
7140 the points-to solution bitmaps. */
7141 unsigned j = integer_id + 1;
7142 for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
7143 if (! varmap[i]->is_reg_var)
7144 map[i] = j++;
7145 for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
7146 if (varmap[i]->is_reg_var)
7147 map[i] = j++;
7148 /* Shuffle varmap according to map. */
7149 for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
7151 while (map[varmap[i]->id] != i)
7152 std::swap (varmap[i], varmap[map[varmap[i]->id]]);
7153 gcc_assert (bitmap_empty_p (varmap[i]->solution));
7154 varmap[i]->id = i;
7155 varmap[i]->next = map[varmap[i]->next];
7156 varmap[i]->head = map[varmap[i]->head];
7158 /* Finally rewrite constraints. */
7159 for (unsigned i = 0; i < constraints.length (); ++i)
7161 constraints[i]->lhs.var = map[constraints[i]->lhs.var];
7162 constraints[i]->rhs.var = map[constraints[i]->rhs.var];
7164 free (map);
7166 if (dump_file)
7167 fprintf (dump_file,
7168 "\nCollapsing static cycles and doing variable "
7169 "substitution\n");
7171 init_graph (varmap.length () * 2);
7173 if (dump_file)
7174 fprintf (dump_file, "Building predecessor graph\n");
7175 build_pred_graph ();
7177 if (dump_file)
7178 fprintf (dump_file, "Detecting pointer and location "
7179 "equivalences\n");
7180 si = perform_var_substitution (graph);
7182 if (dump_file)
7183 fprintf (dump_file, "Rewriting constraints and unifying "
7184 "variables\n");
7185 rewrite_constraints (graph, si);
7187 build_succ_graph ();
7189 free_var_substitution_info (si);
7191 /* Attach complex constraints to graph nodes. */
7192 move_complex_constraints (graph);
7194 if (dump_file)
7195 fprintf (dump_file, "Uniting pointer but not location equivalent "
7196 "variables\n");
7197 unite_pointer_equivalences (graph);
7199 if (dump_file)
7200 fprintf (dump_file, "Finding indirect cycles\n");
7201 find_indirect_cycles (graph);
7203 /* Implicit nodes and predecessors are no longer necessary at this
7204 point. */
7205 remove_preds_and_fake_succs (graph);
7207 if (dump_file && (dump_flags & TDF_GRAPH))
7209 fprintf (dump_file, "\n\n// The constraint graph before solve-graph "
7210 "in dot format:\n");
7211 dump_constraint_graph (dump_file);
7212 fprintf (dump_file, "\n\n");
7215 if (dump_file)
7216 fprintf (dump_file, "Solving graph\n");
7218 solve_graph (graph);
7220 if (dump_file && (dump_flags & TDF_GRAPH))
7222 fprintf (dump_file, "\n\n// The constraint graph after solve-graph "
7223 "in dot format:\n");
7224 dump_constraint_graph (dump_file);
7225 fprintf (dump_file, "\n\n");
7228 if (dump_file)
7229 dump_sa_points_to_info (dump_file);
7232 /* Create points-to sets for the current function. See the comments
7233 at the start of the file for an algorithmic overview. */
7235 static void
7236 compute_points_to_sets (void)
7238 basic_block bb;
7239 varinfo_t vi;
7241 timevar_push (TV_TREE_PTA);
7243 init_alias_vars ();
7245 intra_create_variable_infos (cfun);
7247 /* Now walk all statements and build the constraint set. */
7248 FOR_EACH_BB_FN (bb, cfun)
7250 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
7251 gsi_next (&gsi))
7253 gphi *phi = gsi.phi ();
7255 if (! virtual_operand_p (gimple_phi_result (phi)))
7256 find_func_aliases (cfun, phi);
7259 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
7260 gsi_next (&gsi))
7262 gimple *stmt = gsi_stmt (gsi);
7264 find_func_aliases (cfun, stmt);
7268 if (dump_file)
7270 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
7271 dump_constraints (dump_file, 0);
7274 /* From the constraints compute the points-to sets. */
7275 solve_constraints ();
7277 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
7278 cfun->gimple_df->escaped = find_what_var_points_to (cfun->decl,
7279 get_varinfo (escaped_id));
7281 /* Make sure the ESCAPED solution (which is used as placeholder in
7282 other solutions) does not reference itself. This simplifies
7283 points-to solution queries. */
7284 cfun->gimple_df->escaped.escaped = 0;
7286 /* Compute the points-to sets for pointer SSA_NAMEs. */
7287 unsigned i;
7288 tree ptr;
7290 FOR_EACH_SSA_NAME (i, ptr, cfun)
7292 if (POINTER_TYPE_P (TREE_TYPE (ptr)))
7293 find_what_p_points_to (cfun->decl, ptr);
7296 /* Compute the call-used/clobbered sets. */
7297 FOR_EACH_BB_FN (bb, cfun)
7299 gimple_stmt_iterator gsi;
7301 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
7303 gcall *stmt;
7304 struct pt_solution *pt;
7306 stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
7307 if (!stmt)
7308 continue;
7310 pt = gimple_call_use_set (stmt);
7311 if (gimple_call_flags (stmt) & ECF_CONST)
7312 memset (pt, 0, sizeof (struct pt_solution));
7313 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
7315 *pt = find_what_var_points_to (cfun->decl, vi);
7316 /* Escaped (and thus nonlocal) variables are always
7317 implicitly used by calls. */
7318 /* ??? ESCAPED can be empty even though NONLOCAL
7319 always escaped. */
7320 pt->nonlocal = 1;
7321 pt->escaped = 1;
7323 else
7325 /* If there is nothing special about this call then
7326 we have made everything that is used also escape. */
7327 *pt = cfun->gimple_df->escaped;
7328 pt->nonlocal = 1;
7331 pt = gimple_call_clobber_set (stmt);
7332 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
7333 memset (pt, 0, sizeof (struct pt_solution));
7334 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
7336 *pt = find_what_var_points_to (cfun->decl, vi);
7337 /* Escaped (and thus nonlocal) variables are always
7338 implicitly clobbered by calls. */
7339 /* ??? ESCAPED can be empty even though NONLOCAL
7340 always escaped. */
7341 pt->nonlocal = 1;
7342 pt->escaped = 1;
7344 else
7346 /* If there is nothing special about this call then
7347 we have made everything that is used also escape. */
7348 *pt = cfun->gimple_df->escaped;
7349 pt->nonlocal = 1;
7354 timevar_pop (TV_TREE_PTA);
7358 /* Delete created points-to sets. */
7360 static void
7361 delete_points_to_sets (void)
7363 unsigned int i;
7365 delete shared_bitmap_table;
7366 shared_bitmap_table = NULL;
7367 if (dump_file && (dump_flags & TDF_STATS))
7368 fprintf (dump_file, "Points to sets created:%d\n",
7369 stats.points_to_sets_created);
7371 delete vi_for_tree;
7372 delete call_stmt_vars;
7373 bitmap_obstack_release (&pta_obstack);
7374 constraints.release ();
7376 for (i = 0; i < graph->size; i++)
7377 graph->complex[i].release ();
7378 free (graph->complex);
7380 free (graph->rep);
7381 free (graph->succs);
7382 free (graph->pe);
7383 free (graph->pe_rep);
7384 free (graph->indirect_cycles);
7385 free (graph);
7387 varmap.release ();
7388 variable_info_pool.release ();
7389 constraint_pool.release ();
7391 obstack_free (&fake_var_decl_obstack, NULL);
7393 delete final_solutions;
7394 obstack_free (&final_solutions_obstack, NULL);
7397 struct vls_data
7399 unsigned short clique;
7400 bool escaped_p;
7401 bitmap rvars;
7404 /* Mark "other" loads and stores as belonging to CLIQUE and with
7405 base zero. */
7407 static bool
7408 visit_loadstore (gimple *, tree base, tree ref, void *data)
7410 unsigned short clique = ((vls_data *) data)->clique;
7411 bitmap rvars = ((vls_data *) data)->rvars;
7412 bool escaped_p = ((vls_data *) data)->escaped_p;
7413 if (TREE_CODE (base) == MEM_REF
7414 || TREE_CODE (base) == TARGET_MEM_REF)
7416 tree ptr = TREE_OPERAND (base, 0);
7417 if (TREE_CODE (ptr) == SSA_NAME)
7419 /* For parameters, get at the points-to set for the actual parm
7420 decl. */
7421 if (SSA_NAME_IS_DEFAULT_DEF (ptr)
7422 && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
7423 || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
7424 ptr = SSA_NAME_VAR (ptr);
7426 /* We need to make sure 'ptr' doesn't include any of
7427 the restrict tags we added bases for in its points-to set. */
7428 varinfo_t vi = lookup_vi_for_tree (ptr);
7429 if (! vi)
7430 return false;
7432 vi = get_varinfo (find (vi->id));
7433 if (bitmap_intersect_p (rvars, vi->solution)
7434 || (escaped_p && bitmap_bit_p (vi->solution, escaped_id)))
7435 return false;
7438 /* Do not overwrite existing cliques (that includes clique, base
7439 pairs we just set). */
7440 if (MR_DEPENDENCE_CLIQUE (base) == 0)
7442 MR_DEPENDENCE_CLIQUE (base) = clique;
7443 MR_DEPENDENCE_BASE (base) = 0;
7447 /* For plain decl accesses see whether they are accesses to globals
7448 and rewrite them to MEM_REFs with { clique, 0 }. */
7449 if (VAR_P (base)
7450 && is_global_var (base)
7451 /* ??? We can't rewrite a plain decl with the walk_stmt_load_store
7452 ops callback. */
7453 && base != ref)
7455 tree *basep = &ref;
7456 while (handled_component_p (*basep))
7457 basep = &TREE_OPERAND (*basep, 0);
7458 gcc_assert (VAR_P (*basep));
7459 tree ptr = build_fold_addr_expr (*basep);
7460 tree zero = build_int_cst (TREE_TYPE (ptr), 0);
7461 *basep = build2 (MEM_REF, TREE_TYPE (*basep), ptr, zero);
7462 MR_DEPENDENCE_CLIQUE (*basep) = clique;
7463 MR_DEPENDENCE_BASE (*basep) = 0;
7466 return false;
7469 struct msdi_data {
7470 tree ptr;
7471 unsigned short *clique;
7472 unsigned short *last_ruid;
7473 varinfo_t restrict_var;
7476 /* If BASE is a MEM_REF then assign a clique, base pair to it, updating
7477 CLIQUE, *RESTRICT_VAR and LAST_RUID as passed via DATA.
7478 Return whether dependence info was assigned to BASE. */
7480 static bool
7481 maybe_set_dependence_info (gimple *, tree base, tree, void *data)
7483 tree ptr = ((msdi_data *)data)->ptr;
7484 unsigned short &clique = *((msdi_data *)data)->clique;
7485 unsigned short &last_ruid = *((msdi_data *)data)->last_ruid;
7486 varinfo_t restrict_var = ((msdi_data *)data)->restrict_var;
7487 if ((TREE_CODE (base) == MEM_REF
7488 || TREE_CODE (base) == TARGET_MEM_REF)
7489 && TREE_OPERAND (base, 0) == ptr)
7491 /* Do not overwrite existing cliques. This avoids overwriting dependence
7492 info inlined from a function with restrict parameters inlined
7493 into a function with restrict parameters. This usually means we
7494 prefer to be precise in innermost loops. */
7495 if (MR_DEPENDENCE_CLIQUE (base) == 0)
7497 if (clique == 0)
7498 clique = ++cfun->last_clique;
7499 if (restrict_var->ruid == 0)
7500 restrict_var->ruid = ++last_ruid;
7501 MR_DEPENDENCE_CLIQUE (base) = clique;
7502 MR_DEPENDENCE_BASE (base) = restrict_var->ruid;
7503 return true;
7506 return false;
7509 /* Compute the set of independend memory references based on restrict
7510 tags and their conservative propagation to the points-to sets. */
7512 static void
7513 compute_dependence_clique (void)
7515 unsigned short clique = 0;
7516 unsigned short last_ruid = 0;
7517 bitmap rvars = BITMAP_ALLOC (NULL);
7518 bool escaped_p = false;
7519 for (unsigned i = 0; i < num_ssa_names; ++i)
7521 tree ptr = ssa_name (i);
7522 if (!ptr || !POINTER_TYPE_P (TREE_TYPE (ptr)))
7523 continue;
7525 /* Avoid all this when ptr is not dereferenced? */
7526 tree p = ptr;
7527 if (SSA_NAME_IS_DEFAULT_DEF (ptr)
7528 && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
7529 || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
7530 p = SSA_NAME_VAR (ptr);
7531 varinfo_t vi = lookup_vi_for_tree (p);
7532 if (!vi)
7533 continue;
7534 vi = get_varinfo (find (vi->id));
7535 bitmap_iterator bi;
7536 unsigned j;
7537 varinfo_t restrict_var = NULL;
7538 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
7540 varinfo_t oi = get_varinfo (j);
7541 if (oi->is_restrict_var)
7543 if (restrict_var)
7545 if (dump_file && (dump_flags & TDF_DETAILS))
7547 fprintf (dump_file, "found restrict pointed-to "
7548 "for ");
7549 print_generic_expr (dump_file, ptr);
7550 fprintf (dump_file, " but not exclusively\n");
7552 restrict_var = NULL;
7553 break;
7555 restrict_var = oi;
7557 /* NULL is the only other valid points-to entry. */
7558 else if (oi->id != nothing_id)
7560 restrict_var = NULL;
7561 break;
7564 /* Ok, found that ptr must(!) point to a single(!) restrict
7565 variable. */
7566 /* ??? PTA isn't really a proper propagation engine to compute
7567 this property.
7568 ??? We could handle merging of two restricts by unifying them. */
7569 if (restrict_var)
7571 /* Now look at possible dereferences of ptr. */
7572 imm_use_iterator ui;
7573 gimple *use_stmt;
7574 bool used = false;
7575 msdi_data data = { ptr, &clique, &last_ruid, restrict_var };
7576 FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
7577 used |= walk_stmt_load_store_ops (use_stmt, &data,
7578 maybe_set_dependence_info,
7579 maybe_set_dependence_info);
7580 if (used)
7582 bitmap_set_bit (rvars, restrict_var->id);
7583 varinfo_t escaped = get_varinfo (find (escaped_id));
7584 if (bitmap_bit_p (escaped->solution, restrict_var->id))
7585 escaped_p = true;
7590 if (clique != 0)
7592 /* Assign the BASE id zero to all accesses not based on a restrict
7593 pointer. That way they get disambiguated against restrict
7594 accesses but not against each other. */
7595 /* ??? For restricts derived from globals (thus not incoming
7596 parameters) we can't restrict scoping properly thus the following
7597 is too aggressive there. For now we have excluded those globals from
7598 getting into the MR_DEPENDENCE machinery. */
7599 vls_data data = { clique, escaped_p, rvars };
7600 basic_block bb;
7601 FOR_EACH_BB_FN (bb, cfun)
7602 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
7603 !gsi_end_p (gsi); gsi_next (&gsi))
7605 gimple *stmt = gsi_stmt (gsi);
7606 walk_stmt_load_store_ops (stmt, &data,
7607 visit_loadstore, visit_loadstore);
7611 BITMAP_FREE (rvars);
7614 /* Compute points-to information for every SSA_NAME pointer in the
7615 current function and compute the transitive closure of escaped
7616 variables to re-initialize the call-clobber states of local variables. */
7618 unsigned int
7619 compute_may_aliases (void)
7621 if (cfun->gimple_df->ipa_pta)
7623 if (dump_file)
7625 fprintf (dump_file, "\nNot re-computing points-to information "
7626 "because IPA points-to information is available.\n\n");
7628 /* But still dump what we have remaining it. */
7629 dump_alias_info (dump_file);
7632 return 0;
7635 /* For each pointer P_i, determine the sets of variables that P_i may
7636 point-to. Compute the reachability set of escaped and call-used
7637 variables. */
7638 compute_points_to_sets ();
7640 /* Debugging dumps. */
7641 if (dump_file)
7642 dump_alias_info (dump_file);
7644 /* Compute restrict-based memory disambiguations. */
7645 compute_dependence_clique ();
7647 /* Deallocate memory used by aliasing data structures and the internal
7648 points-to solution. */
7649 delete_points_to_sets ();
7651 gcc_assert (!need_ssa_update_p (cfun));
7653 return 0;
7656 /* A dummy pass to cause points-to information to be computed via
7657 TODO_rebuild_alias. */
7659 namespace {
7661 const pass_data pass_data_build_alias =
7663 GIMPLE_PASS, /* type */
7664 "alias", /* name */
7665 OPTGROUP_NONE, /* optinfo_flags */
7666 TV_NONE, /* tv_id */
7667 ( PROP_cfg | PROP_ssa ), /* properties_required */
7668 0, /* properties_provided */
7669 0, /* properties_destroyed */
7670 0, /* todo_flags_start */
7671 TODO_rebuild_alias, /* todo_flags_finish */
7674 class pass_build_alias : public gimple_opt_pass
7676 public:
7677 pass_build_alias (gcc::context *ctxt)
7678 : gimple_opt_pass (pass_data_build_alias, ctxt)
7681 /* opt_pass methods: */
7682 virtual bool gate (function *) { return flag_tree_pta; }
7684 }; // class pass_build_alias
7686 } // anon namespace
7688 gimple_opt_pass *
7689 make_pass_build_alias (gcc::context *ctxt)
7691 return new pass_build_alias (ctxt);
7694 /* A dummy pass to cause points-to information to be computed via
7695 TODO_rebuild_alias. */
7697 namespace {
7699 const pass_data pass_data_build_ealias =
7701 GIMPLE_PASS, /* type */
7702 "ealias", /* name */
7703 OPTGROUP_NONE, /* optinfo_flags */
7704 TV_NONE, /* tv_id */
7705 ( PROP_cfg | PROP_ssa ), /* properties_required */
7706 0, /* properties_provided */
7707 0, /* properties_destroyed */
7708 0, /* todo_flags_start */
7709 TODO_rebuild_alias, /* todo_flags_finish */
7712 class pass_build_ealias : public gimple_opt_pass
7714 public:
7715 pass_build_ealias (gcc::context *ctxt)
7716 : gimple_opt_pass (pass_data_build_ealias, ctxt)
7719 /* opt_pass methods: */
7720 virtual bool gate (function *) { return flag_tree_pta; }
7722 }; // class pass_build_ealias
7724 } // anon namespace
7726 gimple_opt_pass *
7727 make_pass_build_ealias (gcc::context *ctxt)
7729 return new pass_build_ealias (ctxt);
7733 /* IPA PTA solutions for ESCAPED. */
7734 struct pt_solution ipa_escaped_pt
7735 = { true, false, false, false, false,
7736 false, false, false, false, false, NULL };
7738 /* Associate node with varinfo DATA. Worker for
7739 cgraph_for_symbol_thunks_and_aliases. */
7740 static bool
7741 associate_varinfo_to_alias (struct cgraph_node *node, void *data)
7743 if ((node->alias
7744 || (node->thunk.thunk_p
7745 && ! node->global.inlined_to))
7746 && node->analyzed
7747 && !node->ifunc_resolver)
7748 insert_vi_for_tree (node->decl, (varinfo_t)data);
7749 return false;
7752 /* Dump varinfo VI to FILE. */
7754 static void
7755 dump_varinfo (FILE *file, varinfo_t vi)
7757 if (vi == NULL)
7758 return;
7760 fprintf (file, "%u: %s\n", vi->id, vi->name);
7762 const char *sep = " ";
7763 if (vi->is_artificial_var)
7764 fprintf (file, "%sartificial", sep);
7765 if (vi->is_special_var)
7766 fprintf (file, "%sspecial", sep);
7767 if (vi->is_unknown_size_var)
7768 fprintf (file, "%sunknown-size", sep);
7769 if (vi->is_full_var)
7770 fprintf (file, "%sfull", sep);
7771 if (vi->is_heap_var)
7772 fprintf (file, "%sheap", sep);
7773 if (vi->may_have_pointers)
7774 fprintf (file, "%smay-have-pointers", sep);
7775 if (vi->only_restrict_pointers)
7776 fprintf (file, "%sonly-restrict-pointers", sep);
7777 if (vi->is_restrict_var)
7778 fprintf (file, "%sis-restrict-var", sep);
7779 if (vi->is_global_var)
7780 fprintf (file, "%sglobal", sep);
7781 if (vi->is_ipa_escape_point)
7782 fprintf (file, "%sipa-escape-point", sep);
7783 if (vi->is_fn_info)
7784 fprintf (file, "%sfn-info", sep);
7785 if (vi->ruid)
7786 fprintf (file, "%srestrict-uid:%u", sep, vi->ruid);
7787 if (vi->next)
7788 fprintf (file, "%snext:%u", sep, vi->next);
7789 if (vi->head != vi->id)
7790 fprintf (file, "%shead:%u", sep, vi->head);
7791 if (vi->offset)
7792 fprintf (file, "%soffset:" HOST_WIDE_INT_PRINT_DEC, sep, vi->offset);
7793 if (vi->size != ~(unsigned HOST_WIDE_INT)0)
7794 fprintf (file, "%ssize:" HOST_WIDE_INT_PRINT_DEC, sep, vi->size);
7795 if (vi->fullsize != ~(unsigned HOST_WIDE_INT)0
7796 && vi->fullsize != vi->size)
7797 fprintf (file, "%sfullsize:" HOST_WIDE_INT_PRINT_DEC, sep,
7798 vi->fullsize);
7799 fprintf (file, "\n");
7801 if (vi->solution && !bitmap_empty_p (vi->solution))
7803 bitmap_iterator bi;
7804 unsigned i;
7805 fprintf (file, " solution: {");
7806 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
7807 fprintf (file, " %u", i);
7808 fprintf (file, " }\n");
7811 if (vi->oldsolution && !bitmap_empty_p (vi->oldsolution)
7812 && !bitmap_equal_p (vi->solution, vi->oldsolution))
7814 bitmap_iterator bi;
7815 unsigned i;
7816 fprintf (file, " oldsolution: {");
7817 EXECUTE_IF_SET_IN_BITMAP (vi->oldsolution, 0, i, bi)
7818 fprintf (file, " %u", i);
7819 fprintf (file, " }\n");
7823 /* Dump varinfo VI to stderr. */
7825 DEBUG_FUNCTION void
7826 debug_varinfo (varinfo_t vi)
7828 dump_varinfo (stderr, vi);
7831 /* Dump varmap to FILE. */
7833 static void
7834 dump_varmap (FILE *file)
7836 if (varmap.length () == 0)
7837 return;
7839 fprintf (file, "variables:\n");
7841 for (unsigned int i = 0; i < varmap.length (); ++i)
7843 varinfo_t vi = get_varinfo (i);
7844 dump_varinfo (file, vi);
7847 fprintf (file, "\n");
7850 /* Dump varmap to stderr. */
7852 DEBUG_FUNCTION void
7853 debug_varmap (void)
7855 dump_varmap (stderr);
7858 /* Compute whether node is refered to non-locally. Worker for
7859 cgraph_for_symbol_thunks_and_aliases. */
7860 static bool
7861 refered_from_nonlocal_fn (struct cgraph_node *node, void *data)
7863 bool *nonlocal_p = (bool *)data;
7864 *nonlocal_p |= (node->used_from_other_partition
7865 || node->externally_visible
7866 || node->force_output
7867 || lookup_attribute ("noipa", DECL_ATTRIBUTES (node->decl)));
7868 return false;
7871 /* Same for varpool nodes. */
7872 static bool
7873 refered_from_nonlocal_var (struct varpool_node *node, void *data)
7875 bool *nonlocal_p = (bool *)data;
7876 *nonlocal_p |= (node->used_from_other_partition
7877 || node->externally_visible
7878 || node->force_output);
7879 return false;
7882 /* Execute the driver for IPA PTA. */
7883 static unsigned int
7884 ipa_pta_execute (void)
7886 struct cgraph_node *node;
7887 varpool_node *var;
7888 unsigned int from = 0;
7890 in_ipa_mode = 1;
7892 init_alias_vars ();
7894 if (dump_file && (dump_flags & TDF_DETAILS))
7896 symtab->dump (dump_file);
7897 fprintf (dump_file, "\n");
7900 if (dump_file)
7902 fprintf (dump_file, "Generating generic constraints\n\n");
7903 dump_constraints (dump_file, from);
7904 fprintf (dump_file, "\n");
7905 from = constraints.length ();
7908 /* Build the constraints. */
7909 FOR_EACH_DEFINED_FUNCTION (node)
7911 varinfo_t vi;
7912 /* Nodes without a body are not interesting. Especially do not
7913 visit clones at this point for now - we get duplicate decls
7914 there for inline clones at least. */
7915 if (!node->has_gimple_body_p () || node->global.inlined_to)
7916 continue;
7917 node->get_body ();
7919 gcc_assert (!node->clone_of);
7921 /* For externally visible or attribute used annotated functions use
7922 local constraints for their arguments.
7923 For local functions we see all callers and thus do not need initial
7924 constraints for parameters. */
7925 bool nonlocal_p = (node->used_from_other_partition
7926 || node->externally_visible
7927 || node->force_output
7928 || lookup_attribute ("noipa",
7929 DECL_ATTRIBUTES (node->decl)));
7930 node->call_for_symbol_thunks_and_aliases (refered_from_nonlocal_fn,
7931 &nonlocal_p, true);
7933 vi = create_function_info_for (node->decl,
7934 alias_get_name (node->decl), false,
7935 nonlocal_p);
7936 if (dump_file
7937 && from != constraints.length ())
7939 fprintf (dump_file,
7940 "Generating intial constraints for %s", node->name ());
7941 if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
7942 fprintf (dump_file, " (%s)",
7943 IDENTIFIER_POINTER
7944 (DECL_ASSEMBLER_NAME (node->decl)));
7945 fprintf (dump_file, "\n\n");
7946 dump_constraints (dump_file, from);
7947 fprintf (dump_file, "\n");
7949 from = constraints.length ();
7952 node->call_for_symbol_thunks_and_aliases
7953 (associate_varinfo_to_alias, vi, true);
7956 /* Create constraints for global variables and their initializers. */
7957 FOR_EACH_VARIABLE (var)
7959 if (var->alias && var->analyzed)
7960 continue;
7962 varinfo_t vi = get_vi_for_tree (var->decl);
7964 /* For the purpose of IPA PTA unit-local globals are not
7965 escape points. */
7966 bool nonlocal_p = (var->used_from_other_partition
7967 || var->externally_visible
7968 || var->force_output);
7969 var->call_for_symbol_and_aliases (refered_from_nonlocal_var,
7970 &nonlocal_p, true);
7971 if (nonlocal_p)
7972 vi->is_ipa_escape_point = true;
7975 if (dump_file
7976 && from != constraints.length ())
7978 fprintf (dump_file,
7979 "Generating constraints for global initializers\n\n");
7980 dump_constraints (dump_file, from);
7981 fprintf (dump_file, "\n");
7982 from = constraints.length ();
7985 FOR_EACH_DEFINED_FUNCTION (node)
7987 struct function *func;
7988 basic_block bb;
7990 /* Nodes without a body are not interesting. */
7991 if (!node->has_gimple_body_p () || node->clone_of)
7992 continue;
7994 if (dump_file)
7996 fprintf (dump_file,
7997 "Generating constraints for %s", node->name ());
7998 if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
7999 fprintf (dump_file, " (%s)",
8000 IDENTIFIER_POINTER
8001 (DECL_ASSEMBLER_NAME (node->decl)));
8002 fprintf (dump_file, "\n");
8005 func = DECL_STRUCT_FUNCTION (node->decl);
8006 gcc_assert (cfun == NULL);
8008 /* Build constriants for the function body. */
8009 FOR_EACH_BB_FN (bb, func)
8011 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
8012 gsi_next (&gsi))
8014 gphi *phi = gsi.phi ();
8016 if (! virtual_operand_p (gimple_phi_result (phi)))
8017 find_func_aliases (func, phi);
8020 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
8021 gsi_next (&gsi))
8023 gimple *stmt = gsi_stmt (gsi);
8025 find_func_aliases (func, stmt);
8026 find_func_clobbers (func, stmt);
8030 if (dump_file)
8032 fprintf (dump_file, "\n");
8033 dump_constraints (dump_file, from);
8034 fprintf (dump_file, "\n");
8035 from = constraints.length ();
8039 /* From the constraints compute the points-to sets. */
8040 solve_constraints ();
8042 /* Compute the global points-to sets for ESCAPED.
8043 ??? Note that the computed escape set is not correct
8044 for the whole unit as we fail to consider graph edges to
8045 externally visible functions. */
8046 ipa_escaped_pt = find_what_var_points_to (NULL, get_varinfo (escaped_id));
8048 /* Make sure the ESCAPED solution (which is used as placeholder in
8049 other solutions) does not reference itself. This simplifies
8050 points-to solution queries. */
8051 ipa_escaped_pt.ipa_escaped = 0;
8053 /* Assign the points-to sets to the SSA names in the unit. */
8054 FOR_EACH_DEFINED_FUNCTION (node)
8056 tree ptr;
8057 struct function *fn;
8058 unsigned i;
8059 basic_block bb;
8061 /* Nodes without a body are not interesting. */
8062 if (!node->has_gimple_body_p () || node->clone_of)
8063 continue;
8065 fn = DECL_STRUCT_FUNCTION (node->decl);
8067 /* Compute the points-to sets for pointer SSA_NAMEs. */
8068 FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr)
8070 if (ptr
8071 && POINTER_TYPE_P (TREE_TYPE (ptr)))
8072 find_what_p_points_to (node->decl, ptr);
8075 /* Compute the call-use and call-clobber sets for indirect calls
8076 and calls to external functions. */
8077 FOR_EACH_BB_FN (bb, fn)
8079 gimple_stmt_iterator gsi;
8081 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
8083 gcall *stmt;
8084 struct pt_solution *pt;
8085 varinfo_t vi, fi;
8086 tree decl;
8088 stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
8089 if (!stmt)
8090 continue;
8092 /* Handle direct calls to functions with body. */
8093 decl = gimple_call_fndecl (stmt);
8096 tree called_decl = NULL_TREE;
8097 if (gimple_call_builtin_p (stmt, BUILT_IN_GOMP_PARALLEL))
8098 called_decl = TREE_OPERAND (gimple_call_arg (stmt, 0), 0);
8099 else if (gimple_call_builtin_p (stmt, BUILT_IN_GOACC_PARALLEL))
8100 called_decl = TREE_OPERAND (gimple_call_arg (stmt, 1), 0);
8102 if (called_decl != NULL_TREE
8103 && !fndecl_maybe_in_other_partition (called_decl))
8104 decl = called_decl;
8107 if (decl
8108 && (fi = lookup_vi_for_tree (decl))
8109 && fi->is_fn_info)
8111 *gimple_call_clobber_set (stmt)
8112 = find_what_var_points_to
8113 (node->decl, first_vi_for_offset (fi, fi_clobbers));
8114 *gimple_call_use_set (stmt)
8115 = find_what_var_points_to
8116 (node->decl, first_vi_for_offset (fi, fi_uses));
8118 /* Handle direct calls to external functions. */
8119 else if (decl && (!fi || fi->decl))
8121 pt = gimple_call_use_set (stmt);
8122 if (gimple_call_flags (stmt) & ECF_CONST)
8123 memset (pt, 0, sizeof (struct pt_solution));
8124 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
8126 *pt = find_what_var_points_to (node->decl, vi);
8127 /* Escaped (and thus nonlocal) variables are always
8128 implicitly used by calls. */
8129 /* ??? ESCAPED can be empty even though NONLOCAL
8130 always escaped. */
8131 pt->nonlocal = 1;
8132 pt->ipa_escaped = 1;
8134 else
8136 /* If there is nothing special about this call then
8137 we have made everything that is used also escape. */
8138 *pt = ipa_escaped_pt;
8139 pt->nonlocal = 1;
8142 pt = gimple_call_clobber_set (stmt);
8143 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
8144 memset (pt, 0, sizeof (struct pt_solution));
8145 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
8147 *pt = find_what_var_points_to (node->decl, vi);
8148 /* Escaped (and thus nonlocal) variables are always
8149 implicitly clobbered by calls. */
8150 /* ??? ESCAPED can be empty even though NONLOCAL
8151 always escaped. */
8152 pt->nonlocal = 1;
8153 pt->ipa_escaped = 1;
8155 else
8157 /* If there is nothing special about this call then
8158 we have made everything that is used also escape. */
8159 *pt = ipa_escaped_pt;
8160 pt->nonlocal = 1;
8163 /* Handle indirect calls. */
8164 else if ((fi = get_fi_for_callee (stmt)))
8166 /* We need to accumulate all clobbers/uses of all possible
8167 callees. */
8168 fi = get_varinfo (find (fi->id));
8169 /* If we cannot constrain the set of functions we'll end up
8170 calling we end up using/clobbering everything. */
8171 if (bitmap_bit_p (fi->solution, anything_id)
8172 || bitmap_bit_p (fi->solution, nonlocal_id)
8173 || bitmap_bit_p (fi->solution, escaped_id))
8175 pt_solution_reset (gimple_call_clobber_set (stmt));
8176 pt_solution_reset (gimple_call_use_set (stmt));
8178 else
8180 bitmap_iterator bi;
8181 unsigned i;
8182 struct pt_solution *uses, *clobbers;
8184 uses = gimple_call_use_set (stmt);
8185 clobbers = gimple_call_clobber_set (stmt);
8186 memset (uses, 0, sizeof (struct pt_solution));
8187 memset (clobbers, 0, sizeof (struct pt_solution));
8188 EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi)
8190 struct pt_solution sol;
8192 vi = get_varinfo (i);
8193 if (!vi->is_fn_info)
8195 /* ??? We could be more precise here? */
8196 uses->nonlocal = 1;
8197 uses->ipa_escaped = 1;
8198 clobbers->nonlocal = 1;
8199 clobbers->ipa_escaped = 1;
8200 continue;
8203 if (!uses->anything)
8205 sol = find_what_var_points_to
8206 (node->decl,
8207 first_vi_for_offset (vi, fi_uses));
8208 pt_solution_ior_into (uses, &sol);
8210 if (!clobbers->anything)
8212 sol = find_what_var_points_to
8213 (node->decl,
8214 first_vi_for_offset (vi, fi_clobbers));
8215 pt_solution_ior_into (clobbers, &sol);
8220 else
8221 gcc_unreachable ();
8225 fn->gimple_df->ipa_pta = true;
8227 /* We have to re-set the final-solution cache after each function
8228 because what is a "global" is dependent on function context. */
8229 final_solutions->empty ();
8230 obstack_free (&final_solutions_obstack, NULL);
8231 gcc_obstack_init (&final_solutions_obstack);
8234 delete_points_to_sets ();
8236 in_ipa_mode = 0;
8238 return 0;
8241 namespace {
8243 const pass_data pass_data_ipa_pta =
8245 SIMPLE_IPA_PASS, /* type */
8246 "pta", /* name */
8247 OPTGROUP_NONE, /* optinfo_flags */
8248 TV_IPA_PTA, /* tv_id */
8249 0, /* properties_required */
8250 0, /* properties_provided */
8251 0, /* properties_destroyed */
8252 0, /* todo_flags_start */
8253 0, /* todo_flags_finish */
8256 class pass_ipa_pta : public simple_ipa_opt_pass
8258 public:
8259 pass_ipa_pta (gcc::context *ctxt)
8260 : simple_ipa_opt_pass (pass_data_ipa_pta, ctxt)
8263 /* opt_pass methods: */
8264 virtual bool gate (function *)
8266 return (optimize
8267 && flag_ipa_pta
8268 /* Don't bother doing anything if the program has errors. */
8269 && !seen_error ());
8272 opt_pass * clone () { return new pass_ipa_pta (m_ctxt); }
8274 virtual unsigned int execute (function *) { return ipa_pta_execute (); }
8276 }; // class pass_ipa_pta
8278 } // anon namespace
8280 simple_ipa_opt_pass *
8281 make_pass_ipa_pta (gcc::context *ctxt)
8283 return new pass_ipa_pta (ctxt);