1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dberlin@dberlin.org>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or
11 (at your option) any later version.
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "tree-flow.h"
37 #include "tree-inline.h"
38 #include "diagnostic.h"
44 #include "tree-pass.h"
46 #include "alloc-pool.h"
47 #include "splay-tree.h"
51 #include "pointer-set.h"
53 /* The idea behind this analyzer is to generate set constraints from the
54 program, then solve the resulting constraints in order to generate the
57 Set constraints are a way of modeling program analysis problems that
58 involve sets. They consist of an inclusion constraint language,
59 describing the variables (each variable is a set) and operations that
60 are involved on the variables, and a set of rules that derive facts
61 from these operations. To solve a system of set constraints, you derive
62 all possible facts under the rules, which gives you the correct sets
65 See "Efficient Field-sensitive pointer analysis for C" by "David
66 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
67 http://citeseer.ist.psu.edu/pearce04efficient.html
69 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
70 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
71 http://citeseer.ist.psu.edu/heintze01ultrafast.html
73 There are three types of real constraint expressions, DEREF,
74 ADDRESSOF, and SCALAR. Each constraint expression consists
75 of a constraint type, a variable, and an offset.
77 SCALAR is a constraint expression type used to represent x, whether
78 it appears on the LHS or the RHS of a statement.
79 DEREF is a constraint expression type used to represent *x, whether
80 it appears on the LHS or the RHS of a statement.
81 ADDRESSOF is a constraint expression used to represent &x, whether
82 it appears on the LHS or the RHS of a statement.
84 Each pointer variable in the program is assigned an integer id, and
85 each field of a structure variable is assigned an integer id as well.
87 Structure variables are linked to their list of fields through a "next
88 field" in each variable that points to the next field in offset
90 Each variable for a structure field has
92 1. "size", that tells the size in bits of that field.
93 2. "fullsize, that tells the size in bits of the entire structure.
94 3. "offset", that tells the offset in bits from the beginning of the
95 structure to this field.
107 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
108 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
109 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
112 In order to solve the system of set constraints, the following is
115 1. Each constraint variable x has a solution set associated with it,
118 2. Constraints are separated into direct, copy, and complex.
119 Direct constraints are ADDRESSOF constraints that require no extra
120 processing, such as P = &Q
121 Copy constraints are those of the form P = Q.
122 Complex constraints are all the constraints involving dereferences
123 and offsets (including offsetted copies).
125 3. All direct constraints of the form P = &Q are processed, such
126 that Q is added to Sol(P)
128 4. All complex constraints for a given constraint variable are stored in a
129 linked list attached to that variable's node.
131 5. A directed graph is built out of the copy constraints. Each
132 constraint variable is a node in the graph, and an edge from
133 Q to P is added for each copy constraint of the form P = Q
135 6. The graph is then walked, and solution sets are
136 propagated along the copy edges, such that an edge from Q to P
137 causes Sol(P) <- Sol(P) union Sol(Q).
139 7. As we visit each node, all complex constraints associated with
140 that node are processed by adding appropriate copy edges to the graph, or the
141 appropriate variables to the solution set.
143 8. The process of walking the graph is iterated until no solution
146 Prior to walking the graph in steps 6 and 7, We perform static
147 cycle elimination on the constraint graph, as well
148 as off-line variable substitution.
150 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
151 on and turned into anything), but isn't. You can just see what offset
152 inside the pointed-to struct it's going to access.
154 TODO: Constant bounded arrays can be handled as if they were structs of the
155 same number of elements.
157 TODO: Modeling heap and incoming pointers becomes much better if we
158 add fields to them as we discover them, which we could do.
160 TODO: We could handle unions, but to be honest, it's probably not
161 worth the pain or slowdown. */
163 /* IPA-PTA optimizations possible.
165 When the indirect function called is ANYTHING we can add disambiguation
166 based on the function signatures (or simply the parameter count which
167 is the varinfo size). We also do not need to consider functions that
168 do not have their address taken.
170 The is_global_var bit which marks escape points is overly conservative
171 in IPA mode. Split it to is_escape_point and is_global_var - only
172 externally visible globals are escape points in IPA mode. This is
173 also needed to fix the pt_solution_includes_global predicate
174 (and thus ptr_deref_may_alias_global_p).
176 The way we introduce DECL_PT_UID to avoid fixing up all points-to
177 sets in the translation unit when we copy a DECL during inlining
178 pessimizes precision. The advantage is that the DECL_PT_UID keeps
179 compile-time and memory usage overhead low - the points-to sets
180 do not grow or get unshared as they would during a fixup phase.
181 An alternative solution is to delay IPA PTA until after all
182 inlining transformations have been applied.
184 The way we propagate clobber/use information isn't optimized.
185 It should use a new complex constraint that properly filters
186 out local variables of the callee (though that would make
187 the sets invalid after inlining). OTOH we might as well
188 admit defeat to WHOPR and simply do all the clobber/use analysis
189 and propagation after PTA finished but before we threw away
190 points-to information for memory variables. WHOPR and PTA
191 do not play along well anyway - the whole constraint solving
192 would need to be done in WPA phase and it will be very interesting
193 to apply the results to local SSA names during LTRANS phase.
195 We probably should compute a per-function unit-ESCAPE solution
196 propagating it simply like the clobber / uses solutions. The
197 solution can go alongside the non-IPA espaced solution and be
198 used to query which vars escape the unit through a function.
200 We never put function decls in points-to sets so we do not
201 keep the set of called functions for indirect calls.
203 And probably more. */
205 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
206 htab_t heapvar_for_stmt;
208 static bool use_field_sensitive = true;
209 static int in_ipa_mode = 0;
211 /* Used for predecessor bitmaps. */
212 static bitmap_obstack predbitmap_obstack;
214 /* Used for points-to sets. */
215 static bitmap_obstack pta_obstack;
217 /* Used for oldsolution members of variables. */
218 static bitmap_obstack oldpta_obstack;
220 /* Used for per-solver-iteration bitmaps. */
221 static bitmap_obstack iteration_obstack;
223 static unsigned int create_variable_info_for (tree, const char *);
224 typedef struct constraint_graph *constraint_graph_t;
225 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
228 typedef struct constraint *constraint_t;
230 DEF_VEC_P(constraint_t);
231 DEF_VEC_ALLOC_P(constraint_t,heap);
233 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
235 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
237 static struct constraint_stats
239 unsigned int total_vars;
240 unsigned int nonpointer_vars;
241 unsigned int unified_vars_static;
242 unsigned int unified_vars_dynamic;
243 unsigned int iterations;
244 unsigned int num_edges;
245 unsigned int num_implicit_edges;
246 unsigned int points_to_sets_created;
251 /* ID of this variable */
254 /* True if this is a variable created by the constraint analysis, such as
255 heap variables and constraints we had to break up. */
256 unsigned int is_artificial_var : 1;
258 /* True if this is a special variable whose solution set should not be
260 unsigned int is_special_var : 1;
262 /* True for variables whose size is not known or variable. */
263 unsigned int is_unknown_size_var : 1;
265 /* True for (sub-)fields that represent a whole variable. */
266 unsigned int is_full_var : 1;
268 /* True if this is a heap variable. */
269 unsigned int is_heap_var : 1;
271 /* True if this is a variable tracking a restrict pointer source. */
272 unsigned int is_restrict_var : 1;
274 /* True if this field may contain pointers. */
275 unsigned int may_have_pointers : 1;
277 /* True if this field has only restrict qualified pointers. */
278 unsigned int only_restrict_pointers : 1;
280 /* True if this represents a global variable. */
281 unsigned int is_global_var : 1;
283 /* True if this represents a IPA function info. */
284 unsigned int is_fn_info : 1;
286 /* A link to the variable for the next field in this structure. */
287 struct variable_info *next;
289 /* Offset of this variable, in bits, from the base variable */
290 unsigned HOST_WIDE_INT offset;
292 /* Size of the variable, in bits. */
293 unsigned HOST_WIDE_INT size;
295 /* Full size of the base variable, in bits. */
296 unsigned HOST_WIDE_INT fullsize;
298 /* Name of this variable */
301 /* Tree that this variable is associated with. */
304 /* Points-to set for this variable. */
307 /* Old points-to set for this variable. */
310 typedef struct variable_info *varinfo_t;
312 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
313 static varinfo_t first_or_preceding_vi_for_offset (varinfo_t,
314 unsigned HOST_WIDE_INT);
315 static varinfo_t lookup_vi_for_tree (tree);
317 /* Pool of variable info structures. */
318 static alloc_pool variable_info_pool;
320 DEF_VEC_P(varinfo_t);
322 DEF_VEC_ALLOC_P(varinfo_t, heap);
324 /* Table of variable info structures for constraint variables.
325 Indexed directly by variable info id. */
326 static VEC(varinfo_t,heap) *varmap;
328 /* Return the varmap element N */
330 static inline varinfo_t
331 get_varinfo (unsigned int n)
333 return VEC_index (varinfo_t, varmap, n);
336 /* Static IDs for the special variables. */
337 enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
338 escaped_id = 3, nonlocal_id = 4,
339 storedanything_id = 5, integer_id = 6 };
341 struct GTY(()) heapvar_map {
343 unsigned HOST_WIDE_INT offset;
347 heapvar_map_eq (const void *p1, const void *p2)
349 const struct heapvar_map *h1 = (const struct heapvar_map *)p1;
350 const struct heapvar_map *h2 = (const struct heapvar_map *)p2;
351 return (h1->map.base.from == h2->map.base.from
352 && h1->offset == h2->offset);
356 heapvar_map_hash (struct heapvar_map *h)
358 return iterative_hash_host_wide_int (h->offset,
359 htab_hash_pointer (h->map.base.from));
362 /* Lookup a heap var for FROM, and return it if we find one. */
365 heapvar_lookup (tree from, unsigned HOST_WIDE_INT offset)
367 struct heapvar_map *h, in;
368 in.map.base.from = from;
370 h = (struct heapvar_map *) htab_find_with_hash (heapvar_for_stmt, &in,
371 heapvar_map_hash (&in));
377 /* Insert a mapping FROM->TO in the heap var for statement
381 heapvar_insert (tree from, unsigned HOST_WIDE_INT offset, tree to)
383 struct heapvar_map *h;
386 h = GGC_NEW (struct heapvar_map);
387 h->map.base.from = from;
389 h->map.hash = heapvar_map_hash (h);
391 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->map.hash, INSERT);
392 gcc_assert (*loc == NULL);
393 *(struct heapvar_map **) loc = h;
396 /* Return a new variable info structure consisting for a variable
397 named NAME, and using constraint graph node NODE. Append it
398 to the vector of variable info structures. */
401 new_var_info (tree t, const char *name)
403 unsigned index = VEC_length (varinfo_t, varmap);
404 varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
409 /* Vars without decl are artificial and do not have sub-variables. */
410 ret->is_artificial_var = (t == NULL_TREE);
411 ret->is_special_var = false;
412 ret->is_unknown_size_var = false;
413 ret->is_full_var = (t == NULL_TREE);
414 ret->is_heap_var = false;
415 ret->is_restrict_var = false;
416 ret->may_have_pointers = true;
417 ret->only_restrict_pointers = false;
418 ret->is_global_var = (t == NULL_TREE);
419 ret->is_fn_info = false;
421 ret->is_global_var = is_global_var (t);
422 ret->solution = BITMAP_ALLOC (&pta_obstack);
423 ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
428 VEC_safe_push (varinfo_t, heap, varmap, ret);
434 /* A map mapping call statements to per-stmt variables for uses
435 and clobbers specific to the call. */
436 struct pointer_map_t *call_stmt_vars;
438 /* Lookup or create the variable for the call statement CALL. */
441 get_call_vi (gimple call)
446 slot_p = pointer_map_insert (call_stmt_vars, call);
448 return (varinfo_t) *slot_p;
450 vi = new_var_info (NULL_TREE, "CALLUSED");
454 vi->is_full_var = true;
456 vi->next = vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
460 vi2->is_full_var = true;
462 *slot_p = (void *) vi;
466 /* Lookup the variable for the call statement CALL representing
467 the uses. Returns NULL if there is nothing special about this call. */
470 lookup_call_use_vi (gimple call)
474 slot_p = pointer_map_contains (call_stmt_vars, call);
476 return (varinfo_t) *slot_p;
481 /* Lookup the variable for the call statement CALL representing
482 the clobbers. Returns NULL if there is nothing special about this call. */
485 lookup_call_clobber_vi (gimple call)
487 varinfo_t uses = lookup_call_use_vi (call);
494 /* Lookup or create the variable for the call statement CALL representing
498 get_call_use_vi (gimple call)
500 return get_call_vi (call);
503 /* Lookup or create the variable for the call statement CALL representing
506 static varinfo_t ATTRIBUTE_UNUSED
507 get_call_clobber_vi (gimple call)
509 return get_call_vi (call)->next;
513 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
515 /* An expression that appears in a constraint. */
517 struct constraint_expr
519 /* Constraint type. */
520 constraint_expr_type type;
522 /* Variable we are referring to in the constraint. */
525 /* Offset, in bits, of this constraint from the beginning of
526 variables it ends up referring to.
528 IOW, in a deref constraint, we would deref, get the result set,
529 then add OFFSET to each member. */
530 HOST_WIDE_INT offset;
533 /* Use 0x8000... as special unknown offset. */
534 #define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))
536 typedef struct constraint_expr ce_s;
538 DEF_VEC_ALLOC_O(ce_s, heap);
539 static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);
540 static void get_constraint_for (tree, VEC(ce_s, heap) **);
541 static void do_deref (VEC (ce_s, heap) **);
543 /* Our set constraints are made up of two constraint expressions, one
546 As described in the introduction, our set constraints each represent an
547 operation between set valued variables.
551 struct constraint_expr lhs;
552 struct constraint_expr rhs;
555 /* List of constraints that we use to build the constraint graph from. */
557 static VEC(constraint_t,heap) *constraints;
558 static alloc_pool constraint_pool;
560 /* The constraint graph is represented as an array of bitmaps
561 containing successor nodes. */
563 struct constraint_graph
565 /* Size of this graph, which may be different than the number of
566 nodes in the variable map. */
569 /* Explicit successors of each node. */
572 /* Implicit predecessors of each node (Used for variable
574 bitmap *implicit_preds;
576 /* Explicit predecessors of each node (Used for variable substitution). */
579 /* Indirect cycle representatives, or -1 if the node has no indirect
581 int *indirect_cycles;
583 /* Representative node for a node. rep[a] == a unless the node has
587 /* Equivalence class representative for a label. This is used for
588 variable substitution. */
591 /* Pointer equivalence label for a node. All nodes with the same
592 pointer equivalence label can be unified together at some point
593 (either during constraint optimization or after the constraint
597 /* Pointer equivalence representative for a label. This is used to
598 handle nodes that are pointer equivalent but not location
599 equivalent. We can unite these once the addressof constraints
600 are transformed into initial points-to sets. */
603 /* Pointer equivalence label for each node, used during variable
605 unsigned int *pointer_label;
607 /* Location equivalence label for each node, used during location
608 equivalence finding. */
609 unsigned int *loc_label;
611 /* Pointed-by set for each node, used during location equivalence
612 finding. This is pointed-by rather than pointed-to, because it
613 is constructed using the predecessor graph. */
616 /* Points to sets for pointer equivalence. This is *not* the actual
617 points-to sets for nodes. */
620 /* Bitmap of nodes where the bit is set if the node is a direct
621 node. Used for variable substitution. */
622 sbitmap direct_nodes;
624 /* Bitmap of nodes where the bit is set if the node is address
625 taken. Used for variable substitution. */
626 bitmap address_taken;
628 /* Vector of complex constraints for each graph node. Complex
629 constraints are those involving dereferences or offsets that are
631 VEC(constraint_t,heap) **complex;
634 static constraint_graph_t graph;
636 /* During variable substitution and the offline version of indirect
637 cycle finding, we create nodes to represent dereferences and
638 address taken constraints. These represent where these start and
640 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
641 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
643 /* Return the representative node for NODE, if NODE has been unioned
645 This function performs path compression along the way to finding
646 the representative. */
649 find (unsigned int node)
651 gcc_assert (node < graph->size);
652 if (graph->rep[node] != node)
653 return graph->rep[node] = find (graph->rep[node]);
657 /* Union the TO and FROM nodes to the TO nodes.
658 Note that at some point in the future, we may want to do
659 union-by-rank, in which case we are going to have to return the
660 node we unified to. */
663 unite (unsigned int to, unsigned int from)
665 gcc_assert (to < graph->size && from < graph->size);
666 if (to != from && graph->rep[from] != to)
668 graph->rep[from] = to;
674 /* Create a new constraint consisting of LHS and RHS expressions. */
677 new_constraint (const struct constraint_expr lhs,
678 const struct constraint_expr rhs)
680 constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
686 /* Print out constraint C to FILE. */
689 dump_constraint (FILE *file, constraint_t c)
691 if (c->lhs.type == ADDRESSOF)
693 else if (c->lhs.type == DEREF)
695 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
696 if (c->lhs.offset == UNKNOWN_OFFSET)
697 fprintf (file, " + UNKNOWN");
698 else if (c->lhs.offset != 0)
699 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
700 fprintf (file, " = ");
701 if (c->rhs.type == ADDRESSOF)
703 else if (c->rhs.type == DEREF)
705 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
706 if (c->rhs.offset == UNKNOWN_OFFSET)
707 fprintf (file, " + UNKNOWN");
708 else if (c->rhs.offset != 0)
709 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
710 fprintf (file, "\n");
714 void debug_constraint (constraint_t);
715 void debug_constraints (void);
716 void debug_constraint_graph (void);
717 void debug_solution_for_var (unsigned int);
718 void debug_sa_points_to_info (void);
720 /* Print out constraint C to stderr. */
723 debug_constraint (constraint_t c)
725 dump_constraint (stderr, c);
728 /* Print out all constraints to FILE */
731 dump_constraints (FILE *file, int from)
735 for (i = from; VEC_iterate (constraint_t, constraints, i, c); i++)
736 dump_constraint (file, c);
739 /* Print out all constraints to stderr. */
742 debug_constraints (void)
744 dump_constraints (stderr, 0);
747 /* Print out to FILE the edge in the constraint graph that is created by
748 constraint c. The edge may have a label, depending on the type of
749 constraint that it represents. If complex1, e.g: a = *b, then the label
750 is "=*", if complex2, e.g: *a = b, then the label is "*=", if
751 complex with an offset, e.g: a = b + 8, then the label is "+".
752 Otherwise the edge has no label. */
755 dump_constraint_edge (FILE *file, constraint_t c)
757 if (c->rhs.type != ADDRESSOF)
759 const char *src = get_varinfo (c->rhs.var)->name;
760 const char *dst = get_varinfo (c->lhs.var)->name;
761 fprintf (file, " \"%s\" -> \"%s\" ", src, dst);
762 /* Due to preprocessing of constraints, instructions like *a = *b are
763 illegal; thus, we do not have to handle such cases. */
764 if (c->lhs.type == DEREF)
765 fprintf (file, " [ label=\"*=\" ] ;\n");
766 else if (c->rhs.type == DEREF)
767 fprintf (file, " [ label=\"=*\" ] ;\n");
770 /* We must check the case where the constraint is an offset.
771 In this case, it is treated as a complex constraint. */
772 if (c->rhs.offset != c->lhs.offset)
773 fprintf (file, " [ label=\"+\" ] ;\n");
775 fprintf (file, " ;\n");
780 /* Print the constraint graph in dot format. */
783 dump_constraint_graph (FILE *file)
785 unsigned int i=0, size;
788 /* Only print the graph if it has already been initialized: */
792 /* Print the constraints used to produce the constraint graph. The
793 constraints will be printed as comments in the dot file: */
794 fprintf (file, "\n\n/* Constraints used in the constraint graph:\n");
795 dump_constraints (file, 0);
796 fprintf (file, "*/\n");
798 /* Prints the header of the dot file: */
799 fprintf (file, "\n\n// The constraint graph in dot format:\n");
800 fprintf (file, "strict digraph {\n");
801 fprintf (file, " node [\n shape = box\n ]\n");
802 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
803 fprintf (file, "\n // List of nodes in the constraint graph:\n");
805 /* The next lines print the nodes in the graph. In order to get the
806 number of nodes in the graph, we must choose the minimum between the
807 vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
808 yet been initialized, then graph->size == 0, otherwise we must only
809 read nodes that have an entry in VEC (varinfo_t, varmap). */
810 size = VEC_length (varinfo_t, varmap);
811 size = size < graph->size ? size : graph->size;
812 for (i = 0; i < size; i++)
814 const char *name = get_varinfo (graph->rep[i])->name;
815 fprintf (file, " \"%s\" ;\n", name);
818 /* Go over the list of constraints printing the edges in the constraint
820 fprintf (file, "\n // The constraint edges:\n");
821 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
823 dump_constraint_edge (file, c);
825 /* Prints the tail of the dot file. By now, only the closing bracket. */
826 fprintf (file, "}\n\n\n");
829 /* Print out the constraint graph to stderr. */
832 debug_constraint_graph (void)
834 dump_constraint_graph (stderr);
839 The solver is a simple worklist solver, that works on the following
842 sbitmap changed_nodes = all zeroes;
844 For each node that is not already collapsed:
846 set bit in changed nodes
848 while (changed_count > 0)
850 compute topological ordering for constraint graph
852 find and collapse cycles in the constraint graph (updating
853 changed if necessary)
855 for each node (n) in the graph in topological order:
858 Process each complex constraint associated with the node,
859 updating changed if necessary.
861 For each outgoing edge from n, propagate the solution from n to
862 the destination of the edge, updating changed as necessary.
866 /* Return true if two constraint expressions A and B are equal. */
869 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
871 return a.type == b.type && a.var == b.var && a.offset == b.offset;
874 /* Return true if constraint expression A is less than constraint expression
875 B. This is just arbitrary, but consistent, in order to give them an
879 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
881 if (a.type == b.type)
884 return a.offset < b.offset;
886 return a.var < b.var;
889 return a.type < b.type;
892 /* Return true if constraint A is less than constraint B. This is just
893 arbitrary, but consistent, in order to give them an ordering. */
896 constraint_less (const constraint_t a, const constraint_t b)
898 if (constraint_expr_less (a->lhs, b->lhs))
900 else if (constraint_expr_less (b->lhs, a->lhs))
903 return constraint_expr_less (a->rhs, b->rhs);
906 /* Return true if two constraints A and B are equal. */
909 constraint_equal (struct constraint a, struct constraint b)
911 return constraint_expr_equal (a.lhs, b.lhs)
912 && constraint_expr_equal (a.rhs, b.rhs);
916 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
919 constraint_vec_find (VEC(constraint_t,heap) *vec,
920 struct constraint lookfor)
928 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
929 if (place >= VEC_length (constraint_t, vec))
931 found = VEC_index (constraint_t, vec, place);
932 if (!constraint_equal (*found, lookfor))
937 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
940 constraint_set_union (VEC(constraint_t,heap) **to,
941 VEC(constraint_t,heap) **from)
946 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
948 if (constraint_vec_find (*to, *c) == NULL)
950 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
952 VEC_safe_insert (constraint_t, heap, *to, place, c);
957 /* Expands the solution in SET to all sub-fields of variables included.
958 Union the expanded result into RESULT. */
961 solution_set_expand (bitmap result, bitmap set)
967 /* In a first pass record all variables we need to add all
968 sub-fields off. This avoids quadratic behavior. */
969 EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
971 varinfo_t v = get_varinfo (j);
972 if (v->is_artificial_var
975 v = lookup_vi_for_tree (v->decl);
977 vars = BITMAP_ALLOC (NULL);
978 bitmap_set_bit (vars, v->id);
981 /* In the second pass now do the addition to the solution and
982 to speed up solving add it to the delta as well. */
985 EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
987 varinfo_t v = get_varinfo (j);
988 for (; v != NULL; v = v->next)
989 bitmap_set_bit (result, v->id);
995 /* Take a solution set SET, add OFFSET to each member of the set, and
996 overwrite SET with the result when done. */
999 solution_set_add (bitmap set, HOST_WIDE_INT offset)
1001 bitmap result = BITMAP_ALLOC (&iteration_obstack);
1005 /* If the offset is unknown we have to expand the solution to
1007 if (offset == UNKNOWN_OFFSET)
1009 solution_set_expand (set, set);
1013 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
1015 varinfo_t vi = get_varinfo (i);
1017 /* If this is a variable with just one field just set its bit
1019 if (vi->is_artificial_var
1020 || vi->is_unknown_size_var
1022 bitmap_set_bit (result, i);
1025 unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
1027 /* If the offset makes the pointer point to before the
1028 variable use offset zero for the field lookup. */
1030 && fieldoffset > vi->offset)
1034 vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
1036 bitmap_set_bit (result, vi->id);
1037 /* If the result is not exactly at fieldoffset include the next
1038 field as well. See get_constraint_for_ptr_offset for more
1040 if (vi->offset != fieldoffset
1041 && vi->next != NULL)
1042 bitmap_set_bit (result, vi->next->id);
1046 bitmap_copy (set, result);
1047 BITMAP_FREE (result);
1050 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
1054 set_union_with_increment (bitmap to, bitmap from, HOST_WIDE_INT inc)
1057 return bitmap_ior_into (to, from);
1063 tmp = BITMAP_ALLOC (&iteration_obstack);
1064 bitmap_copy (tmp, from);
1065 solution_set_add (tmp, inc);
1066 res = bitmap_ior_into (to, tmp);
1072 /* Insert constraint C into the list of complex constraints for graph
1076 insert_into_complex (constraint_graph_t graph,
1077 unsigned int var, constraint_t c)
1079 VEC (constraint_t, heap) *complex = graph->complex[var];
1080 unsigned int place = VEC_lower_bound (constraint_t, complex, c,
1083 /* Only insert constraints that do not already exist. */
1084 if (place >= VEC_length (constraint_t, complex)
1085 || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
1086 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
1090 /* Condense two variable nodes into a single variable node, by moving
1091 all associated info from SRC to TO. */
1094 merge_node_constraints (constraint_graph_t graph, unsigned int to,
1100 gcc_assert (find (from) == to);
1102 /* Move all complex constraints from src node into to node */
1103 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
1105 /* In complex constraints for node src, we may have either
1106 a = *src, and *src = a, or an offseted constraint which are
1107 always added to the rhs node's constraints. */
1109 if (c->rhs.type == DEREF)
1111 else if (c->lhs.type == DEREF)
1116 constraint_set_union (&graph->complex[to], &graph->complex[from]);
1117 VEC_free (constraint_t, heap, graph->complex[from]);
1118 graph->complex[from] = NULL;
1122 /* Remove edges involving NODE from GRAPH. */
1125 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
1127 if (graph->succs[node])
1128 BITMAP_FREE (graph->succs[node]);
1131 /* Merge GRAPH nodes FROM and TO into node TO. */
1134 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1137 if (graph->indirect_cycles[from] != -1)
1139 /* If we have indirect cycles with the from node, and we have
1140 none on the to node, the to node has indirect cycles from the
1141 from node now that they are unified.
1142 If indirect cycles exist on both, unify the nodes that they
1143 are in a cycle with, since we know they are in a cycle with
1145 if (graph->indirect_cycles[to] == -1)
1146 graph->indirect_cycles[to] = graph->indirect_cycles[from];
1149 /* Merge all the successor edges. */
1150 if (graph->succs[from])
1152 if (!graph->succs[to])
1153 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1154 bitmap_ior_into (graph->succs[to],
1155 graph->succs[from]);
1158 clear_edges_for_node (graph, from);
1162 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1163 it doesn't exist in the graph already. */
1166 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1172 if (!graph->implicit_preds[to])
1173 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1175 if (bitmap_set_bit (graph->implicit_preds[to], from))
1176 stats.num_implicit_edges++;
1179 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1180 it doesn't exist in the graph already.
1181 Return false if the edge already existed, true otherwise. */
1184 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1187 if (!graph->preds[to])
1188 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1189 bitmap_set_bit (graph->preds[to], from);
1192 /* Add a graph edge to GRAPH, going from FROM to TO if
1193 it doesn't exist in the graph already.
1194 Return false if the edge already existed, true otherwise. */
1197 add_graph_edge (constraint_graph_t graph, unsigned int to,
1208 if (!graph->succs[from])
1209 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1210 if (bitmap_set_bit (graph->succs[from], to))
1213 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1221 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1224 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1227 return (graph->succs[dest]
1228 && bitmap_bit_p (graph->succs[dest], src));
1231 /* Initialize the constraint graph structure to contain SIZE nodes. */
1234 init_graph (unsigned int size)
1238 graph = XCNEW (struct constraint_graph);
1240 graph->succs = XCNEWVEC (bitmap, graph->size);
1241 graph->indirect_cycles = XNEWVEC (int, graph->size);
1242 graph->rep = XNEWVEC (unsigned int, graph->size);
1243 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
1244 graph->pe = XCNEWVEC (unsigned int, graph->size);
1245 graph->pe_rep = XNEWVEC (int, graph->size);
1247 for (j = 0; j < graph->size; j++)
1250 graph->pe_rep[j] = -1;
1251 graph->indirect_cycles[j] = -1;
1255 /* Build the constraint graph, adding only predecessor edges right now. */
1258 build_pred_graph (void)
1264 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1265 graph->preds = XCNEWVEC (bitmap, graph->size);
1266 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1267 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1268 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1269 graph->points_to = XCNEWVEC (bitmap, graph->size);
1270 graph->eq_rep = XNEWVEC (int, graph->size);
1271 graph->direct_nodes = sbitmap_alloc (graph->size);
1272 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1273 sbitmap_zero (graph->direct_nodes);
1275 for (j = 0; j < FIRST_REF_NODE; j++)
1277 if (!get_varinfo (j)->is_special_var)
1278 SET_BIT (graph->direct_nodes, j);
1281 for (j = 0; j < graph->size; j++)
1282 graph->eq_rep[j] = -1;
1284 for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
1285 graph->indirect_cycles[j] = -1;
1287 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1289 struct constraint_expr lhs = c->lhs;
1290 struct constraint_expr rhs = c->rhs;
1291 unsigned int lhsvar = lhs.var;
1292 unsigned int rhsvar = rhs.var;
1294 if (lhs.type == DEREF)
1297 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1298 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1300 else if (rhs.type == DEREF)
1303 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1304 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1306 RESET_BIT (graph->direct_nodes, lhsvar);
1308 else if (rhs.type == ADDRESSOF)
1313 if (graph->points_to[lhsvar] == NULL)
1314 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1315 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1317 if (graph->pointed_by[rhsvar] == NULL)
1318 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1319 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1321 /* Implicitly, *x = y */
1322 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1324 /* All related variables are no longer direct nodes. */
1325 RESET_BIT (graph->direct_nodes, rhsvar);
1326 v = get_varinfo (rhsvar);
1327 if (!v->is_full_var)
1329 v = lookup_vi_for_tree (v->decl);
1332 RESET_BIT (graph->direct_nodes, v->id);
1337 bitmap_set_bit (graph->address_taken, rhsvar);
1339 else if (lhsvar > anything_id
1340 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1343 add_pred_graph_edge (graph, lhsvar, rhsvar);
1344 /* Implicitly, *x = *y */
1345 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1346 FIRST_REF_NODE + rhsvar);
1348 else if (lhs.offset != 0 || rhs.offset != 0)
1350 if (rhs.offset != 0)
1351 RESET_BIT (graph->direct_nodes, lhs.var);
1352 else if (lhs.offset != 0)
1353 RESET_BIT (graph->direct_nodes, rhs.var);
1358 /* Build the constraint graph, adding successor edges. */
1361 build_succ_graph (void)
1366 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1368 struct constraint_expr lhs;
1369 struct constraint_expr rhs;
1370 unsigned int lhsvar;
1371 unsigned int rhsvar;
1378 lhsvar = find (lhs.var);
1379 rhsvar = find (rhs.var);
1381 if (lhs.type == DEREF)
1383 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1384 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1386 else if (rhs.type == DEREF)
1388 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1389 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1391 else if (rhs.type == ADDRESSOF)
1394 gcc_assert (find (rhs.var) == rhs.var);
1395 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1397 else if (lhsvar > anything_id
1398 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1400 add_graph_edge (graph, lhsvar, rhsvar);
1404 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1405 receive pointers. */
1406 t = find (storedanything_id);
1407 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1409 if (!TEST_BIT (graph->direct_nodes, i)
1410 && get_varinfo (i)->may_have_pointers)
1411 add_graph_edge (graph, find (i), t);
1414 /* Everything stored to ANYTHING also potentially escapes. */
1415 add_graph_edge (graph, find (escaped_id), t);
1419 /* Changed variables on the last iteration. */
1420 static unsigned int changed_count;
1421 static sbitmap changed;
1423 /* Strongly Connected Component visitation info. */
1430 unsigned int *node_mapping;
1432 VEC(unsigned,heap) *scc_stack;
1436 /* Recursive routine to find strongly connected components in GRAPH.
1437 SI is the SCC info to store the information in, and N is the id of current
1438 graph node we are processing.
1440 This is Tarjan's strongly connected component finding algorithm, as
1441 modified by Nuutila to keep only non-root nodes on the stack.
1442 The algorithm can be found in "On finding the strongly connected
1443 connected components in a directed graph" by Esko Nuutila and Eljas
1444 Soisalon-Soininen, in Information Processing Letters volume 49,
1445 number 1, pages 9-14. */
1448 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1452 unsigned int my_dfs;
1454 SET_BIT (si->visited, n);
1455 si->dfs[n] = si->current_index ++;
1456 my_dfs = si->dfs[n];
1458 /* Visit all the successors. */
1459 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1463 if (i > LAST_REF_NODE)
1467 if (TEST_BIT (si->deleted, w))
1470 if (!TEST_BIT (si->visited, w))
1471 scc_visit (graph, si, w);
1473 unsigned int t = find (w);
1474 unsigned int nnode = find (n);
1475 gcc_assert (nnode == n);
1477 if (si->dfs[t] < si->dfs[nnode])
1478 si->dfs[n] = si->dfs[t];
1482 /* See if any components have been identified. */
1483 if (si->dfs[n] == my_dfs)
1485 if (VEC_length (unsigned, si->scc_stack) > 0
1486 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1488 bitmap scc = BITMAP_ALLOC (NULL);
1489 unsigned int lowest_node;
1492 bitmap_set_bit (scc, n);
1494 while (VEC_length (unsigned, si->scc_stack) != 0
1495 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1497 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1499 bitmap_set_bit (scc, w);
1502 lowest_node = bitmap_first_set_bit (scc);
1503 gcc_assert (lowest_node < FIRST_REF_NODE);
1505 /* Collapse the SCC nodes into a single node, and mark the
1507 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1509 if (i < FIRST_REF_NODE)
1511 if (unite (lowest_node, i))
1512 unify_nodes (graph, lowest_node, i, false);
1516 unite (lowest_node, i);
1517 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1521 SET_BIT (si->deleted, n);
1524 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1527 /* Unify node FROM into node TO, updating the changed count if
1528 necessary when UPDATE_CHANGED is true. */
1531 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1532 bool update_changed)
1535 gcc_assert (to != from && find (to) == to);
1536 if (dump_file && (dump_flags & TDF_DETAILS))
1537 fprintf (dump_file, "Unifying %s to %s\n",
1538 get_varinfo (from)->name,
1539 get_varinfo (to)->name);
1542 stats.unified_vars_dynamic++;
1544 stats.unified_vars_static++;
1546 merge_graph_nodes (graph, to, from);
1547 merge_node_constraints (graph, to, from);
1549 /* Mark TO as changed if FROM was changed. If TO was already marked
1550 as changed, decrease the changed count. */
1552 if (update_changed && TEST_BIT (changed, from))
1554 RESET_BIT (changed, from);
1555 if (!TEST_BIT (changed, to))
1556 SET_BIT (changed, to);
1559 gcc_assert (changed_count > 0);
1563 if (get_varinfo (from)->solution)
1565 /* If the solution changes because of the merging, we need to mark
1566 the variable as changed. */
1567 if (bitmap_ior_into (get_varinfo (to)->solution,
1568 get_varinfo (from)->solution))
1570 if (update_changed && !TEST_BIT (changed, to))
1572 SET_BIT (changed, to);
1577 BITMAP_FREE (get_varinfo (from)->solution);
1578 BITMAP_FREE (get_varinfo (from)->oldsolution);
1580 if (stats.iterations > 0)
1582 BITMAP_FREE (get_varinfo (to)->oldsolution);
1583 get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1586 if (valid_graph_edge (graph, to, to))
1588 if (graph->succs[to])
1589 bitmap_clear_bit (graph->succs[to], to);
1593 /* Information needed to compute the topological ordering of a graph. */
1597 /* sbitmap of visited nodes. */
1599 /* Array that stores the topological order of the graph, *in
1601 VEC(unsigned,heap) *topo_order;
1605 /* Initialize and return a topological info structure. */
1607 static struct topo_info *
1608 init_topo_info (void)
1610 size_t size = graph->size;
1611 struct topo_info *ti = XNEW (struct topo_info);
1612 ti->visited = sbitmap_alloc (size);
1613 sbitmap_zero (ti->visited);
1614 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1619 /* Free the topological sort info pointed to by TI. */
1622 free_topo_info (struct topo_info *ti)
1624 sbitmap_free (ti->visited);
1625 VEC_free (unsigned, heap, ti->topo_order);
1629 /* Visit the graph in topological order, and store the order in the
1630 topo_info structure. */
1633 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1639 SET_BIT (ti->visited, n);
1641 if (graph->succs[n])
1642 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1644 if (!TEST_BIT (ti->visited, j))
1645 topo_visit (graph, ti, j);
1648 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1651 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1652 starting solution for y. */
1655 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1658 unsigned int lhs = c->lhs.var;
1660 bitmap sol = get_varinfo (lhs)->solution;
1663 HOST_WIDE_INT roffset = c->rhs.offset;
1665 /* Our IL does not allow this. */
1666 gcc_assert (c->lhs.offset == 0);
1668 /* If the solution of Y contains anything it is good enough to transfer
1670 if (bitmap_bit_p (delta, anything_id))
1672 flag |= bitmap_set_bit (sol, anything_id);
1676 /* If we do not know at with offset the rhs is dereferenced compute
1677 the reachability set of DELTA, conservatively assuming it is
1678 dereferenced at all valid offsets. */
1679 if (roffset == UNKNOWN_OFFSET)
1681 solution_set_expand (delta, delta);
1682 /* No further offset processing is necessary. */
1686 /* For each variable j in delta (Sol(y)), add
1687 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1688 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1690 varinfo_t v = get_varinfo (j);
1691 HOST_WIDE_INT fieldoffset = v->offset + roffset;
1695 fieldoffset = v->offset;
1696 else if (roffset != 0)
1697 v = first_vi_for_offset (v, fieldoffset);
1698 /* If the access is outside of the variable we can ignore it. */
1706 /* Adding edges from the special vars is pointless.
1707 They don't have sets that can change. */
1708 if (get_varinfo (t)->is_special_var)
1709 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1710 /* Merging the solution from ESCAPED needlessly increases
1711 the set. Use ESCAPED as representative instead. */
1712 else if (v->id == escaped_id)
1713 flag |= bitmap_set_bit (sol, escaped_id);
1714 else if (v->may_have_pointers
1715 && add_graph_edge (graph, lhs, t))
1716 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1718 /* If the variable is not exactly at the requested offset
1719 we have to include the next one. */
1720 if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1725 fieldoffset = v->offset;
1731 /* If the LHS solution changed, mark the var as changed. */
1734 get_varinfo (lhs)->solution = sol;
1735 if (!TEST_BIT (changed, lhs))
1737 SET_BIT (changed, lhs);
1743 /* Process a constraint C that represents *(x + off) = y using DELTA
1744 as the starting solution for x. */
1747 do_ds_constraint (constraint_t c, bitmap delta)
1749 unsigned int rhs = c->rhs.var;
1750 bitmap sol = get_varinfo (rhs)->solution;
1753 HOST_WIDE_INT loff = c->lhs.offset;
1754 bool escaped_p = false;
1756 /* Our IL does not allow this. */
1757 gcc_assert (c->rhs.offset == 0);
1759 /* If the solution of y contains ANYTHING simply use the ANYTHING
1760 solution. This avoids needlessly increasing the points-to sets. */
1761 if (bitmap_bit_p (sol, anything_id))
1762 sol = get_varinfo (find (anything_id))->solution;
1764 /* If the solution for x contains ANYTHING we have to merge the
1765 solution of y into all pointer variables which we do via
1767 if (bitmap_bit_p (delta, anything_id))
1769 unsigned t = find (storedanything_id);
1770 if (add_graph_edge (graph, t, rhs))
1772 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1774 if (!TEST_BIT (changed, t))
1776 SET_BIT (changed, t);
1784 /* If we do not know at with offset the rhs is dereferenced compute
1785 the reachability set of DELTA, conservatively assuming it is
1786 dereferenced at all valid offsets. */
1787 if (loff == UNKNOWN_OFFSET)
1789 solution_set_expand (delta, delta);
1793 /* For each member j of delta (Sol(x)), add an edge from y to j and
1794 union Sol(y) into Sol(j) */
1795 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1797 varinfo_t v = get_varinfo (j);
1799 HOST_WIDE_INT fieldoffset = v->offset + loff;
1802 fieldoffset = v->offset;
1804 v = first_vi_for_offset (v, fieldoffset);
1805 /* If the access is outside of the variable we can ignore it. */
1811 if (v->may_have_pointers)
1813 /* If v is a global variable then this is an escape point. */
1814 if (v->is_global_var
1817 t = find (escaped_id);
1818 if (add_graph_edge (graph, t, rhs)
1819 && bitmap_ior_into (get_varinfo (t)->solution, sol)
1820 && !TEST_BIT (changed, t))
1822 SET_BIT (changed, t);
1825 /* Enough to let rhs escape once. */
1829 if (v->is_special_var)
1833 if (add_graph_edge (graph, t, rhs)
1834 && bitmap_ior_into (get_varinfo (t)->solution, sol)
1835 && !TEST_BIT (changed, t))
1837 SET_BIT (changed, t);
1842 /* If the variable is not exactly at the requested offset
1843 we have to include the next one. */
1844 if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1849 fieldoffset = v->offset;
1855 /* Handle a non-simple (simple meaning requires no iteration),
1856 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1859 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1861 if (c->lhs.type == DEREF)
1863 if (c->rhs.type == ADDRESSOF)
1870 do_ds_constraint (c, delta);
1873 else if (c->rhs.type == DEREF)
1876 if (!(get_varinfo (c->lhs.var)->is_special_var))
1877 do_sd_constraint (graph, c, delta);
1885 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1886 solution = get_varinfo (c->rhs.var)->solution;
1887 tmp = get_varinfo (c->lhs.var)->solution;
1889 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1893 get_varinfo (c->lhs.var)->solution = tmp;
1894 if (!TEST_BIT (changed, c->lhs.var))
1896 SET_BIT (changed, c->lhs.var);
1903 /* Initialize and return a new SCC info structure. */
1905 static struct scc_info *
1906 init_scc_info (size_t size)
1908 struct scc_info *si = XNEW (struct scc_info);
1911 si->current_index = 0;
1912 si->visited = sbitmap_alloc (size);
1913 sbitmap_zero (si->visited);
1914 si->deleted = sbitmap_alloc (size);
1915 sbitmap_zero (si->deleted);
1916 si->node_mapping = XNEWVEC (unsigned int, size);
1917 si->dfs = XCNEWVEC (unsigned int, size);
1919 for (i = 0; i < size; i++)
1920 si->node_mapping[i] = i;
1922 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1926 /* Free an SCC info structure pointed to by SI */
1929 free_scc_info (struct scc_info *si)
1931 sbitmap_free (si->visited);
1932 sbitmap_free (si->deleted);
1933 free (si->node_mapping);
1935 VEC_free (unsigned, heap, si->scc_stack);
1940 /* Find indirect cycles in GRAPH that occur, using strongly connected
1941 components, and note them in the indirect cycles map.
1943 This technique comes from Ben Hardekopf and Calvin Lin,
1944 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1945 Lines of Code", submitted to PLDI 2007. */
1948 find_indirect_cycles (constraint_graph_t graph)
1951 unsigned int size = graph->size;
1952 struct scc_info *si = init_scc_info (size);
1954 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1955 if (!TEST_BIT (si->visited, i) && find (i) == i)
1956 scc_visit (graph, si, i);
1961 /* Compute a topological ordering for GRAPH, and store the result in the
1962 topo_info structure TI. */
1965 compute_topo_order (constraint_graph_t graph,
1966 struct topo_info *ti)
1969 unsigned int size = graph->size;
1971 for (i = 0; i != size; ++i)
1972 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1973 topo_visit (graph, ti, i);
1976 /* Structure used to for hash value numbering of pointer equivalence
1979 typedef struct equiv_class_label
1982 unsigned int equivalence_class;
1984 } *equiv_class_label_t;
1985 typedef const struct equiv_class_label *const_equiv_class_label_t;
1987 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1989 static htab_t pointer_equiv_class_table;
1991 /* A hashtable for mapping a bitmap of labels->location equivalence
1993 static htab_t location_equiv_class_table;
1995 /* Hash function for a equiv_class_label_t */
1998 equiv_class_label_hash (const void *p)
2000 const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
2001 return ecl->hashcode;
2004 /* Equality function for two equiv_class_label_t's. */
2007 equiv_class_label_eq (const void *p1, const void *p2)
2009 const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
2010 const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
2011 return (eql1->hashcode == eql2->hashcode
2012 && bitmap_equal_p (eql1->labels, eql2->labels));
2015 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
2019 equiv_class_lookup (htab_t table, bitmap labels)
2022 struct equiv_class_label ecl;
2024 ecl.labels = labels;
2025 ecl.hashcode = bitmap_hash (labels);
2027 slot = htab_find_slot_with_hash (table, &ecl,
2028 ecl.hashcode, NO_INSERT);
2032 return ((equiv_class_label_t) *slot)->equivalence_class;
2036 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
2040 equiv_class_add (htab_t table, unsigned int equivalence_class,
2044 equiv_class_label_t ecl = XNEW (struct equiv_class_label);
2046 ecl->labels = labels;
2047 ecl->equivalence_class = equivalence_class;
2048 ecl->hashcode = bitmap_hash (labels);
2050 slot = htab_find_slot_with_hash (table, ecl,
2051 ecl->hashcode, INSERT);
2052 gcc_assert (!*slot);
2053 *slot = (void *) ecl;
2056 /* Perform offline variable substitution.
2058 This is a worst case quadratic time way of identifying variables
2059 that must have equivalent points-to sets, including those caused by
2060 static cycles, and single entry subgraphs, in the constraint graph.
2062 The technique is described in "Exploiting Pointer and Location
2063 Equivalence to Optimize Pointer Analysis. In the 14th International
2064 Static Analysis Symposium (SAS), August 2007." It is known as the
2065 "HU" algorithm, and is equivalent to value numbering the collapsed
2066 constraint graph including evaluating unions.
2068 The general method of finding equivalence classes is as follows:
2069 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
2070 Initialize all non-REF nodes to be direct nodes.
2071 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
2073 For each constraint containing the dereference, we also do the same
2076 We then compute SCC's in the graph and unify nodes in the same SCC,
2079 For each non-collapsed node x:
2080 Visit all unvisited explicit incoming edges.
2081 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
2083 Lookup the equivalence class for pts(x).
2084 If we found one, equivalence_class(x) = found class.
2085 Otherwise, equivalence_class(x) = new class, and new_class is
2086 added to the lookup table.
2088 All direct nodes with the same equivalence class can be replaced
2089 with a single representative node.
2090 All unlabeled nodes (label == 0) are not pointers and all edges
2091 involving them can be eliminated.
2092 We perform these optimizations during rewrite_constraints
2094 In addition to pointer equivalence class finding, we also perform
2095 location equivalence class finding. This is the set of variables
2096 that always appear together in points-to sets. We use this to
2097 compress the size of the points-to sets. */
2099 /* Current maximum pointer equivalence class id. */
2100 static int pointer_equiv_class;
2102 /* Current maximum location equivalence class id. */
2103 static int location_equiv_class;
2105 /* Recursive routine to find strongly connected components in GRAPH,
2106 and label it's nodes with DFS numbers. */
2109 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2113 unsigned int my_dfs;
2115 gcc_assert (si->node_mapping[n] == n);
2116 SET_BIT (si->visited, n);
2117 si->dfs[n] = si->current_index ++;
2118 my_dfs = si->dfs[n];
2120 /* Visit all the successors. */
2121 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2123 unsigned int w = si->node_mapping[i];
2125 if (TEST_BIT (si->deleted, w))
2128 if (!TEST_BIT (si->visited, w))
2129 condense_visit (graph, si, w);
2131 unsigned int t = si->node_mapping[w];
2132 unsigned int nnode = si->node_mapping[n];
2133 gcc_assert (nnode == n);
2135 if (si->dfs[t] < si->dfs[nnode])
2136 si->dfs[n] = si->dfs[t];
2140 /* Visit all the implicit predecessors. */
2141 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
2143 unsigned int w = si->node_mapping[i];
2145 if (TEST_BIT (si->deleted, w))
2148 if (!TEST_BIT (si->visited, w))
2149 condense_visit (graph, si, w);
2151 unsigned int t = si->node_mapping[w];
2152 unsigned int nnode = si->node_mapping[n];
2153 gcc_assert (nnode == n);
2155 if (si->dfs[t] < si->dfs[nnode])
2156 si->dfs[n] = si->dfs[t];
2160 /* See if any components have been identified. */
2161 if (si->dfs[n] == my_dfs)
2163 while (VEC_length (unsigned, si->scc_stack) != 0
2164 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
2166 unsigned int w = VEC_pop (unsigned, si->scc_stack);
2167 si->node_mapping[w] = n;
2169 if (!TEST_BIT (graph->direct_nodes, w))
2170 RESET_BIT (graph->direct_nodes, n);
2172 /* Unify our nodes. */
2173 if (graph->preds[w])
2175 if (!graph->preds[n])
2176 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2177 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2179 if (graph->implicit_preds[w])
2181 if (!graph->implicit_preds[n])
2182 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2183 bitmap_ior_into (graph->implicit_preds[n],
2184 graph->implicit_preds[w]);
2186 if (graph->points_to[w])
2188 if (!graph->points_to[n])
2189 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2190 bitmap_ior_into (graph->points_to[n],
2191 graph->points_to[w]);
2194 SET_BIT (si->deleted, n);
2197 VEC_safe_push (unsigned, heap, si->scc_stack, n);
2200 /* Label pointer equivalences. */
2203 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2207 SET_BIT (si->visited, n);
2209 if (!graph->points_to[n])
2210 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2212 /* Label and union our incoming edges's points to sets. */
2213 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2215 unsigned int w = si->node_mapping[i];
2216 if (!TEST_BIT (si->visited, w))
2217 label_visit (graph, si, w);
2219 /* Skip unused edges */
2220 if (w == n || graph->pointer_label[w] == 0)
2223 if (graph->points_to[w])
2224 bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
2226 /* Indirect nodes get fresh variables. */
2227 if (!TEST_BIT (graph->direct_nodes, n))
2228 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2230 if (!bitmap_empty_p (graph->points_to[n]))
2232 unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
2233 graph->points_to[n]);
2236 label = pointer_equiv_class++;
2237 equiv_class_add (pointer_equiv_class_table,
2238 label, graph->points_to[n]);
2240 graph->pointer_label[n] = label;
2244 /* Perform offline variable substitution, discovering equivalence
2245 classes, and eliminating non-pointer variables. */
2247 static struct scc_info *
2248 perform_var_substitution (constraint_graph_t graph)
2251 unsigned int size = graph->size;
2252 struct scc_info *si = init_scc_info (size);
2254 bitmap_obstack_initialize (&iteration_obstack);
2255 pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
2256 equiv_class_label_eq, free);
2257 location_equiv_class_table = htab_create (511, equiv_class_label_hash,
2258 equiv_class_label_eq, free);
2259 pointer_equiv_class = 1;
2260 location_equiv_class = 1;
2262 /* Condense the nodes, which means to find SCC's, count incoming
2263 predecessors, and unite nodes in SCC's. */
2264 for (i = 0; i < FIRST_REF_NODE; i++)
2265 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2266 condense_visit (graph, si, si->node_mapping[i]);
2268 sbitmap_zero (si->visited);
2269 /* Actually the label the nodes for pointer equivalences */
2270 for (i = 0; i < FIRST_REF_NODE; i++)
2271 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2272 label_visit (graph, si, si->node_mapping[i]);
2274 /* Calculate location equivalence labels. */
2275 for (i = 0; i < FIRST_REF_NODE; i++)
2282 if (!graph->pointed_by[i])
2284 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2286 /* Translate the pointed-by mapping for pointer equivalence
2288 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2290 bitmap_set_bit (pointed_by,
2291 graph->pointer_label[si->node_mapping[j]]);
2293 /* The original pointed_by is now dead. */
2294 BITMAP_FREE (graph->pointed_by[i]);
2296 /* Look up the location equivalence label if one exists, or make
2298 label = equiv_class_lookup (location_equiv_class_table,
2302 label = location_equiv_class++;
2303 equiv_class_add (location_equiv_class_table,
2308 if (dump_file && (dump_flags & TDF_DETAILS))
2309 fprintf (dump_file, "Found location equivalence for node %s\n",
2310 get_varinfo (i)->name);
2311 BITMAP_FREE (pointed_by);
2313 graph->loc_label[i] = label;
2317 if (dump_file && (dump_flags & TDF_DETAILS))
2318 for (i = 0; i < FIRST_REF_NODE; i++)
2320 bool direct_node = TEST_BIT (graph->direct_nodes, i);
2322 "Equivalence classes for %s node id %d:%s are pointer: %d"
2324 direct_node ? "Direct node" : "Indirect node", i,
2325 get_varinfo (i)->name,
2326 graph->pointer_label[si->node_mapping[i]],
2327 graph->loc_label[si->node_mapping[i]]);
2330 /* Quickly eliminate our non-pointer variables. */
2332 for (i = 0; i < FIRST_REF_NODE; i++)
2334 unsigned int node = si->node_mapping[i];
2336 if (graph->pointer_label[node] == 0)
2338 if (dump_file && (dump_flags & TDF_DETAILS))
2340 "%s is a non-pointer variable, eliminating edges.\n",
2341 get_varinfo (node)->name);
2342 stats.nonpointer_vars++;
2343 clear_edges_for_node (graph, node);
2350 /* Free information that was only necessary for variable
2354 free_var_substitution_info (struct scc_info *si)
2357 free (graph->pointer_label);
2358 free (graph->loc_label);
2359 free (graph->pointed_by);
2360 free (graph->points_to);
2361 free (graph->eq_rep);
2362 sbitmap_free (graph->direct_nodes);
2363 htab_delete (pointer_equiv_class_table);
2364 htab_delete (location_equiv_class_table);
2365 bitmap_obstack_release (&iteration_obstack);
2368 /* Return an existing node that is equivalent to NODE, which has
2369 equivalence class LABEL, if one exists. Return NODE otherwise. */
2372 find_equivalent_node (constraint_graph_t graph,
2373 unsigned int node, unsigned int label)
2375 /* If the address version of this variable is unused, we can
2376 substitute it for anything else with the same label.
2377 Otherwise, we know the pointers are equivalent, but not the
2378 locations, and we can unite them later. */
2380 if (!bitmap_bit_p (graph->address_taken, node))
2382 gcc_assert (label < graph->size);
2384 if (graph->eq_rep[label] != -1)
2386 /* Unify the two variables since we know they are equivalent. */
2387 if (unite (graph->eq_rep[label], node))
2388 unify_nodes (graph, graph->eq_rep[label], node, false);
2389 return graph->eq_rep[label];
2393 graph->eq_rep[label] = node;
2394 graph->pe_rep[label] = node;
2399 gcc_assert (label < graph->size);
2400 graph->pe[node] = label;
2401 if (graph->pe_rep[label] == -1)
2402 graph->pe_rep[label] = node;
2408 /* Unite pointer equivalent but not location equivalent nodes in
2409 GRAPH. This may only be performed once variable substitution is
2413 unite_pointer_equivalences (constraint_graph_t graph)
2417 /* Go through the pointer equivalences and unite them to their
2418 representative, if they aren't already. */
2419 for (i = 0; i < FIRST_REF_NODE; i++)
2421 unsigned int label = graph->pe[i];
2424 int label_rep = graph->pe_rep[label];
2426 if (label_rep == -1)
2429 label_rep = find (label_rep);
2430 if (label_rep >= 0 && unite (label_rep, find (i)))
2431 unify_nodes (graph, label_rep, i, false);
2436 /* Move complex constraints to the GRAPH nodes they belong to. */
2439 move_complex_constraints (constraint_graph_t graph)
2444 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2448 struct constraint_expr lhs = c->lhs;
2449 struct constraint_expr rhs = c->rhs;
2451 if (lhs.type == DEREF)
2453 insert_into_complex (graph, lhs.var, c);
2455 else if (rhs.type == DEREF)
2457 if (!(get_varinfo (lhs.var)->is_special_var))
2458 insert_into_complex (graph, rhs.var, c);
2460 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2461 && (lhs.offset != 0 || rhs.offset != 0))
2463 insert_into_complex (graph, rhs.var, c);
2470 /* Optimize and rewrite complex constraints while performing
2471 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2472 result of perform_variable_substitution. */
2475 rewrite_constraints (constraint_graph_t graph,
2476 struct scc_info *si)
2482 for (j = 0; j < graph->size; j++)
2483 gcc_assert (find (j) == j);
2485 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2487 struct constraint_expr lhs = c->lhs;
2488 struct constraint_expr rhs = c->rhs;
2489 unsigned int lhsvar = find (lhs.var);
2490 unsigned int rhsvar = find (rhs.var);
2491 unsigned int lhsnode, rhsnode;
2492 unsigned int lhslabel, rhslabel;
2494 lhsnode = si->node_mapping[lhsvar];
2495 rhsnode = si->node_mapping[rhsvar];
2496 lhslabel = graph->pointer_label[lhsnode];
2497 rhslabel = graph->pointer_label[rhsnode];
2499 /* See if it is really a non-pointer variable, and if so, ignore
2503 if (dump_file && (dump_flags & TDF_DETAILS))
2506 fprintf (dump_file, "%s is a non-pointer variable,"
2507 "ignoring constraint:",
2508 get_varinfo (lhs.var)->name);
2509 dump_constraint (dump_file, c);
2511 VEC_replace (constraint_t, constraints, i, NULL);
2517 if (dump_file && (dump_flags & TDF_DETAILS))
2520 fprintf (dump_file, "%s is a non-pointer variable,"
2521 "ignoring constraint:",
2522 get_varinfo (rhs.var)->name);
2523 dump_constraint (dump_file, c);
2525 VEC_replace (constraint_t, constraints, i, NULL);
2529 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2530 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2531 c->lhs.var = lhsvar;
2532 c->rhs.var = rhsvar;
2537 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2538 part of an SCC, false otherwise. */
2541 eliminate_indirect_cycles (unsigned int node)
2543 if (graph->indirect_cycles[node] != -1
2544 && !bitmap_empty_p (get_varinfo (node)->solution))
2547 VEC(unsigned,heap) *queue = NULL;
2549 unsigned int to = find (graph->indirect_cycles[node]);
2552 /* We can't touch the solution set and call unify_nodes
2553 at the same time, because unify_nodes is going to do
2554 bitmap unions into it. */
2556 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2558 if (find (i) == i && i != to)
2561 VEC_safe_push (unsigned, heap, queue, i);
2566 VEC_iterate (unsigned, queue, queuepos, i);
2569 unify_nodes (graph, to, i, true);
2571 VEC_free (unsigned, heap, queue);
2577 /* Solve the constraint graph GRAPH using our worklist solver.
2578 This is based on the PW* family of solvers from the "Efficient Field
2579 Sensitive Pointer Analysis for C" paper.
2580 It works by iterating over all the graph nodes, processing the complex
2581 constraints and propagating the copy constraints, until everything stops
2582 changed. This corresponds to steps 6-8 in the solving list given above. */
2585 solve_graph (constraint_graph_t graph)
2587 unsigned int size = graph->size;
2592 changed = sbitmap_alloc (size);
2593 sbitmap_zero (changed);
2595 /* Mark all initial non-collapsed nodes as changed. */
2596 for (i = 0; i < size; i++)
2598 varinfo_t ivi = get_varinfo (i);
2599 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2600 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2601 || VEC_length (constraint_t, graph->complex[i]) > 0))
2603 SET_BIT (changed, i);
2608 /* Allocate a bitmap to be used to store the changed bits. */
2609 pts = BITMAP_ALLOC (&pta_obstack);
2611 while (changed_count > 0)
2614 struct topo_info *ti = init_topo_info ();
2617 bitmap_obstack_initialize (&iteration_obstack);
2619 compute_topo_order (graph, ti);
2621 while (VEC_length (unsigned, ti->topo_order) != 0)
2624 i = VEC_pop (unsigned, ti->topo_order);
2626 /* If this variable is not a representative, skip it. */
2630 /* In certain indirect cycle cases, we may merge this
2631 variable to another. */
2632 if (eliminate_indirect_cycles (i) && find (i) != i)
2635 /* If the node has changed, we need to process the
2636 complex constraints and outgoing edges again. */
2637 if (TEST_BIT (changed, i))
2642 VEC(constraint_t,heap) *complex = graph->complex[i];
2643 bool solution_empty;
2645 RESET_BIT (changed, i);
2648 /* Compute the changed set of solution bits. */
2649 bitmap_and_compl (pts, get_varinfo (i)->solution,
2650 get_varinfo (i)->oldsolution);
2652 if (bitmap_empty_p (pts))
2655 bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2657 solution = get_varinfo (i)->solution;
2658 solution_empty = bitmap_empty_p (solution);
2660 /* Process the complex constraints */
2661 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2663 /* XXX: This is going to unsort the constraints in
2664 some cases, which will occasionally add duplicate
2665 constraints during unification. This does not
2666 affect correctness. */
2667 c->lhs.var = find (c->lhs.var);
2668 c->rhs.var = find (c->rhs.var);
2670 /* The only complex constraint that can change our
2671 solution to non-empty, given an empty solution,
2672 is a constraint where the lhs side is receiving
2673 some set from elsewhere. */
2674 if (!solution_empty || c->lhs.type != DEREF)
2675 do_complex_constraint (graph, c, pts);
2678 solution_empty = bitmap_empty_p (solution);
2680 if (!solution_empty)
2683 unsigned eff_escaped_id = find (escaped_id);
2685 /* Propagate solution to all successors. */
2686 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2692 unsigned int to = find (j);
2693 tmp = get_varinfo (to)->solution;
2696 /* Don't try to propagate to ourselves. */
2700 /* If we propagate from ESCAPED use ESCAPED as
2702 if (i == eff_escaped_id)
2703 flag = bitmap_set_bit (tmp, escaped_id);
2705 flag = set_union_with_increment (tmp, pts, 0);
2709 get_varinfo (to)->solution = tmp;
2710 if (!TEST_BIT (changed, to))
2712 SET_BIT (changed, to);
2720 free_topo_info (ti);
2721 bitmap_obstack_release (&iteration_obstack);
2725 sbitmap_free (changed);
2726 bitmap_obstack_release (&oldpta_obstack);
2729 /* Map from trees to variable infos. */
2730 static struct pointer_map_t *vi_for_tree;
2733 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2736 insert_vi_for_tree (tree t, varinfo_t vi)
2738 void **slot = pointer_map_insert (vi_for_tree, t);
2740 gcc_assert (*slot == NULL);
2744 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2745 exist in the map, return NULL, otherwise, return the varinfo we found. */
2748 lookup_vi_for_tree (tree t)
2750 void **slot = pointer_map_contains (vi_for_tree, t);
2754 return (varinfo_t) *slot;
2757 /* Return a printable name for DECL */
2760 alias_get_name (tree decl)
2762 const char *res = get_name (decl);
2764 int num_printed = 0;
2773 if (TREE_CODE (decl) == SSA_NAME)
2775 num_printed = asprintf (&temp, "%s_%u",
2776 alias_get_name (SSA_NAME_VAR (decl)),
2777 SSA_NAME_VERSION (decl));
2779 else if (DECL_P (decl))
2781 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2783 if (num_printed > 0)
2785 res = ggc_strdup (temp);
2791 /* Find the variable id for tree T in the map.
2792 If T doesn't exist in the map, create an entry for it and return it. */
2795 get_vi_for_tree (tree t)
2797 void **slot = pointer_map_contains (vi_for_tree, t);
2799 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2801 return (varinfo_t) *slot;
2804 /* Get a scalar constraint expression for a new temporary variable. */
2806 static struct constraint_expr
2807 new_scalar_tmp_constraint_exp (const char *name)
2809 struct constraint_expr tmp;
2812 vi = new_var_info (NULL_TREE, name);
2816 vi->is_full_var = 1;
2825 /* Get a constraint expression vector from an SSA_VAR_P node.
2826 If address_p is true, the result will be taken its address of. */
2829 get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
2831 struct constraint_expr cexpr;
2834 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2835 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2837 /* For parameters, get at the points-to set for the actual parm
2839 if (TREE_CODE (t) == SSA_NAME
2840 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2841 && SSA_NAME_IS_DEFAULT_DEF (t))
2843 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2847 vi = get_vi_for_tree (t);
2849 cexpr.type = SCALAR;
2851 /* If we determine the result is "anything", and we know this is readonly,
2852 say it points to readonly memory instead. */
2853 if (cexpr.var == anything_id && TREE_READONLY (t))
2856 cexpr.type = ADDRESSOF;
2857 cexpr.var = readonly_id;
2860 /* If we are not taking the address of the constraint expr, add all
2861 sub-fiels of the variable as well. */
2863 && !vi->is_full_var)
2865 for (; vi; vi = vi->next)
2868 VEC_safe_push (ce_s, heap, *results, &cexpr);
2873 VEC_safe_push (ce_s, heap, *results, &cexpr);
2876 /* Process constraint T, performing various simplifications and then
2877 adding it to our list of overall constraints. */
2880 process_constraint (constraint_t t)
2882 struct constraint_expr rhs = t->rhs;
2883 struct constraint_expr lhs = t->lhs;
2885 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2886 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2888 /* If we didn't get any useful constraint from the lhs we get
2889 &ANYTHING as fallback from get_constraint_for. Deal with
2890 it here by turning it into *ANYTHING. */
2891 if (lhs.type == ADDRESSOF
2892 && lhs.var == anything_id)
2895 /* ADDRESSOF on the lhs is invalid. */
2896 gcc_assert (lhs.type != ADDRESSOF);
2898 /* We shouldn't add constraints from things that cannot have pointers.
2899 It's not completely trivial to avoid in the callers, so do it here. */
2900 if (rhs.type != ADDRESSOF
2901 && !get_varinfo (rhs.var)->may_have_pointers)
2904 /* Likewise adding to the solution of a non-pointer var isn't useful. */
2905 if (!get_varinfo (lhs.var)->may_have_pointers)
2908 /* This can happen in our IR with things like n->a = *p */
2909 if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2911 /* Split into tmp = *rhs, *lhs = tmp */
2912 struct constraint_expr tmplhs;
2913 tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp");
2914 process_constraint (new_constraint (tmplhs, rhs));
2915 process_constraint (new_constraint (lhs, tmplhs));
2917 else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
2919 /* Split into tmp = &rhs, *lhs = tmp */
2920 struct constraint_expr tmplhs;
2921 tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp");
2922 process_constraint (new_constraint (tmplhs, rhs));
2923 process_constraint (new_constraint (lhs, tmplhs));
2927 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2928 VEC_safe_push (constraint_t, heap, constraints, t);
2932 /* Return true if T is a type that could contain pointers. */
2935 type_could_have_pointers (tree type)
2937 if (POINTER_TYPE_P (type))
2940 if (TREE_CODE (type) == ARRAY_TYPE)
2941 return type_could_have_pointers (TREE_TYPE (type));
2943 /* A function or method can consume pointers.
2944 ??? We could be more precise here. */
2945 if (TREE_CODE (type) == FUNCTION_TYPE
2946 || TREE_CODE (type) == METHOD_TYPE)
2949 return AGGREGATE_TYPE_P (type);
2952 /* Return true if T is a variable of a type that could contain
2956 could_have_pointers (tree t)
2958 return type_could_have_pointers (TREE_TYPE (t));
2961 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2964 static HOST_WIDE_INT
2965 bitpos_of_field (const tree fdecl)
2968 if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2969 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2972 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2973 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2977 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2978 resulting constraint expressions in *RESULTS. */
2981 get_constraint_for_ptr_offset (tree ptr, tree offset,
2982 VEC (ce_s, heap) **results)
2984 struct constraint_expr c;
2986 HOST_WIDE_INT rhsunitoffset, rhsoffset;
2988 /* If we do not do field-sensitive PTA adding offsets to pointers
2989 does not change the points-to solution. */
2990 if (!use_field_sensitive)
2992 get_constraint_for (ptr, results);
2996 /* If the offset is not a non-negative integer constant that fits
2997 in a HOST_WIDE_INT, we have to fall back to a conservative
2998 solution which includes all sub-fields of all pointed-to
2999 variables of ptr. */
3000 if (offset == NULL_TREE
3001 || !host_integerp (offset, 0))
3002 rhsoffset = UNKNOWN_OFFSET;
3005 /* Make sure the bit-offset also fits. */
3006 rhsunitoffset = TREE_INT_CST_LOW (offset);
3007 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
3008 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
3009 rhsoffset = UNKNOWN_OFFSET;
3012 get_constraint_for (ptr, results);
3016 /* As we are eventually appending to the solution do not use
3017 VEC_iterate here. */
3018 n = VEC_length (ce_s, *results);
3019 for (j = 0; j < n; j++)
3022 c = *VEC_index (ce_s, *results, j);
3023 curr = get_varinfo (c.var);
3025 if (c.type == ADDRESSOF
3026 /* If this varinfo represents a full variable just use it. */
3027 && curr->is_full_var)
3029 else if (c.type == ADDRESSOF
3030 /* If we do not know the offset add all subfields. */
3031 && rhsoffset == UNKNOWN_OFFSET)
3033 varinfo_t temp = lookup_vi_for_tree (curr->decl);
3036 struct constraint_expr c2;
3038 c2.type = ADDRESSOF;
3040 if (c2.var != c.var)
3041 VEC_safe_push (ce_s, heap, *results, &c2);
3046 else if (c.type == ADDRESSOF)
3049 unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
3051 /* Search the sub-field which overlaps with the
3052 pointed-to offset. If the result is outside of the variable
3053 we have to provide a conservative result, as the variable is
3054 still reachable from the resulting pointer (even though it
3055 technically cannot point to anything). The last and first
3056 sub-fields are such conservative results.
3057 ??? If we always had a sub-field for &object + 1 then
3058 we could represent this in a more precise way. */
3060 && curr->offset < offset)
3062 temp = first_or_preceding_vi_for_offset (curr, offset);
3064 /* If the found variable is not exactly at the pointed to
3065 result, we have to include the next variable in the
3066 solution as well. Otherwise two increments by offset / 2
3067 do not result in the same or a conservative superset
3069 if (temp->offset != offset
3070 && temp->next != NULL)
3072 struct constraint_expr c2;
3073 c2.var = temp->next->id;
3074 c2.type = ADDRESSOF;
3076 VEC_safe_push (ce_s, heap, *results, &c2);
3082 c.offset = rhsoffset;
3084 VEC_replace (ce_s, *results, j, &c);
3089 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3090 If address_p is true the result will be taken its address of. */
3093 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
3097 HOST_WIDE_INT bitsize = -1;
3098 HOST_WIDE_INT bitmaxsize = -1;
3099 HOST_WIDE_INT bitpos;
3101 struct constraint_expr *result;
3103 /* Some people like to do cute things like take the address of
3106 while (handled_component_p (forzero)
3107 || INDIRECT_REF_P (forzero))
3108 forzero = TREE_OPERAND (forzero, 0);
3110 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
3112 struct constraint_expr temp;
3115 temp.var = integer_id;
3117 VEC_safe_push (ce_s, heap, *results, &temp);
3121 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
3123 /* Pretend to take the address of the base, we'll take care of
3124 adding the required subset of sub-fields below. */
3125 get_constraint_for_1 (t, results, true);
3126 gcc_assert (VEC_length (ce_s, *results) == 1);
3127 result = VEC_last (ce_s, *results);
3129 if (result->type == SCALAR
3130 && get_varinfo (result->var)->is_full_var)
3131 /* For single-field vars do not bother about the offset. */
3133 else if (result->type == SCALAR)
3135 /* In languages like C, you can access one past the end of an
3136 array. You aren't allowed to dereference it, so we can
3137 ignore this constraint. When we handle pointer subtraction,
3138 we may have to do something cute here. */
3140 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
3143 /* It's also not true that the constraint will actually start at the
3144 right offset, it may start in some padding. We only care about
3145 setting the constraint to the first actual field it touches, so
3147 struct constraint_expr cexpr = *result;
3149 VEC_pop (ce_s, *results);
3151 for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
3153 if (ranges_overlap_p (curr->offset, curr->size,
3154 bitpos, bitmaxsize))
3156 cexpr.var = curr->id;
3157 VEC_safe_push (ce_s, heap, *results, &cexpr);
3162 /* If we are going to take the address of this field then
3163 to be able to compute reachability correctly add at least
3164 the last field of the variable. */
3166 && VEC_length (ce_s, *results) == 0)
3168 curr = get_varinfo (cexpr.var);
3169 while (curr->next != NULL)
3171 cexpr.var = curr->id;
3172 VEC_safe_push (ce_s, heap, *results, &cexpr);
3175 /* Assert that we found *some* field there. The user couldn't be
3176 accessing *only* padding. */
3177 /* Still the user could access one past the end of an array
3178 embedded in a struct resulting in accessing *only* padding. */
3179 gcc_assert (VEC_length (ce_s, *results) >= 1
3180 || ref_contains_array_ref (orig_t));
3182 else if (bitmaxsize == 0)
3184 if (dump_file && (dump_flags & TDF_DETAILS))
3185 fprintf (dump_file, "Access to zero-sized part of variable,"
3189 if (dump_file && (dump_flags & TDF_DETAILS))
3190 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3192 else if (result->type == DEREF)
3194 /* If we do not know exactly where the access goes say so. Note
3195 that only for non-structure accesses we know that we access
3196 at most one subfiled of any variable. */
3198 || bitsize != bitmaxsize
3199 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t)))
3200 result->offset = UNKNOWN_OFFSET;
3202 result->offset = bitpos;
3204 else if (result->type == ADDRESSOF)
3206 /* We can end up here for component references on a
3207 VIEW_CONVERT_EXPR <>(&foobar). */
3208 result->type = SCALAR;
3209 result->var = anything_id;
3217 /* Dereference the constraint expression CONS, and return the result.
3218 DEREF (ADDRESSOF) = SCALAR
3219 DEREF (SCALAR) = DEREF
3220 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3221 This is needed so that we can handle dereferencing DEREF constraints. */
3224 do_deref (VEC (ce_s, heap) **constraints)
3226 struct constraint_expr *c;
3229 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3231 if (c->type == SCALAR)
3233 else if (c->type == ADDRESSOF)
3235 else if (c->type == DEREF)
3237 struct constraint_expr tmplhs;
3238 tmplhs = new_scalar_tmp_constraint_exp ("dereftmp");
3239 process_constraint (new_constraint (tmplhs, *c));
3240 c->var = tmplhs.var;
3247 static void get_constraint_for_1 (tree, VEC (ce_s, heap) **, bool);
3249 /* Given a tree T, return the constraint expression for taking the
3253 get_constraint_for_address_of (tree t, VEC (ce_s, heap) **results)
3255 struct constraint_expr *c;
3258 get_constraint_for_1 (t, results, true);
3260 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3262 if (c->type == DEREF)
3265 c->type = ADDRESSOF;
3269 /* Given a tree T, return the constraint expression for it. */
3272 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3274 struct constraint_expr temp;
3276 /* x = integer is all glommed to a single variable, which doesn't
3277 point to anything by itself. That is, of course, unless it is an
3278 integer constant being treated as a pointer, in which case, we
3279 will return that this is really the addressof anything. This
3280 happens below, since it will fall into the default case. The only
3281 case we know something about an integer treated like a pointer is
3282 when it is the NULL pointer, and then we just say it points to
3285 Do not do that if -fno-delete-null-pointer-checks though, because
3286 in that case *NULL does not fail, so it _should_ alias *anything.
3287 It is not worth adding a new option or renaming the existing one,
3288 since this case is relatively obscure. */
3289 if (flag_delete_null_pointer_checks
3290 && ((TREE_CODE (t) == INTEGER_CST
3291 && integer_zerop (t))
3292 /* The only valid CONSTRUCTORs in gimple with pointer typed
3293 elements are zero-initializer. But in IPA mode we also
3294 process global initializers, so verify at least. */
3295 || (TREE_CODE (t) == CONSTRUCTOR
3296 && CONSTRUCTOR_NELTS (t) == 0)))
3298 temp.var = nothing_id;
3299 temp.type = ADDRESSOF;
3301 VEC_safe_push (ce_s, heap, *results, &temp);
3305 /* String constants are read-only. */
3306 if (TREE_CODE (t) == STRING_CST)
3308 temp.var = readonly_id;
3311 VEC_safe_push (ce_s, heap, *results, &temp);
3315 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3317 case tcc_expression:
3319 switch (TREE_CODE (t))
3322 get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3330 switch (TREE_CODE (t))
3334 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3339 case ARRAY_RANGE_REF:
3341 get_constraint_for_component_ref (t, results, address_p);
3343 case VIEW_CONVERT_EXPR:
3344 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3346 /* We are missing handling for TARGET_MEM_REF here. */
3351 case tcc_exceptional:
3353 switch (TREE_CODE (t))
3357 get_constraint_for_ssa_var (t, results, address_p);
3364 VEC (ce_s, heap) *tmp = NULL;
3365 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t), i, val)
3367 struct constraint_expr *rhsp;
3369 get_constraint_for_1 (val, &tmp, address_p);
3370 for (j = 0; VEC_iterate (ce_s, tmp, j, rhsp); ++j)
3371 VEC_safe_push (ce_s, heap, *results, rhsp);
3372 VEC_truncate (ce_s, tmp, 0);
3374 VEC_free (ce_s, heap, tmp);
3375 /* We do not know whether the constructor was complete,
3376 so technically we have to add &NOTHING or &ANYTHING
3377 like we do for an empty constructor as well. */
3384 case tcc_declaration:
3386 get_constraint_for_ssa_var (t, results, address_p);
3392 /* The default fallback is a constraint from anything. */
3393 temp.type = ADDRESSOF;
3394 temp.var = anything_id;
3396 VEC_safe_push (ce_s, heap, *results, &temp);
3399 /* Given a gimple tree T, return the constraint expression vector for it. */
3402 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3404 gcc_assert (VEC_length (ce_s, *results) == 0);
3406 get_constraint_for_1 (t, results, false);
3410 /* Efficiently generates constraints from all entries in *RHSC to all
3411 entries in *LHSC. */
3414 process_all_all_constraints (VEC (ce_s, heap) *lhsc, VEC (ce_s, heap) *rhsc)
3416 struct constraint_expr *lhsp, *rhsp;
3419 if (VEC_length (ce_s, lhsc) <= 1
3420 || VEC_length (ce_s, rhsc) <= 1)
3422 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3423 for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); ++j)
3424 process_constraint (new_constraint (*lhsp, *rhsp));
3428 struct constraint_expr tmp;
3429 tmp = new_scalar_tmp_constraint_exp ("allalltmp");
3430 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
3431 process_constraint (new_constraint (tmp, *rhsp));
3432 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3433 process_constraint (new_constraint (*lhsp, tmp));
3437 /* Handle aggregate copies by expanding into copies of the respective
3438 fields of the structures. */
3441 do_structure_copy (tree lhsop, tree rhsop)
3443 struct constraint_expr *lhsp, *rhsp;
3444 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3447 get_constraint_for (lhsop, &lhsc);
3448 get_constraint_for (rhsop, &rhsc);
3449 lhsp = VEC_index (ce_s, lhsc, 0);
3450 rhsp = VEC_index (ce_s, rhsc, 0);
3451 if (lhsp->type == DEREF
3452 || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3453 || rhsp->type == DEREF)
3455 if (lhsp->type == DEREF)
3457 gcc_assert (VEC_length (ce_s, lhsc) == 1);
3458 lhsp->offset = UNKNOWN_OFFSET;
3460 if (rhsp->type == DEREF)
3462 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3463 rhsp->offset = UNKNOWN_OFFSET;
3465 process_all_all_constraints (lhsc, rhsc);
3467 else if (lhsp->type == SCALAR
3468 && (rhsp->type == SCALAR
3469 || rhsp->type == ADDRESSOF))
3471 HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
3472 HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
3474 get_ref_base_and_extent (lhsop, &lhsoffset, &lhssize, &lhsmaxsize);
3475 get_ref_base_and_extent (rhsop, &rhsoffset, &rhssize, &rhsmaxsize);
3476 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp);)
3478 varinfo_t lhsv, rhsv;
3479 rhsp = VEC_index (ce_s, rhsc, k);
3480 lhsv = get_varinfo (lhsp->var);
3481 rhsv = get_varinfo (rhsp->var);
3482 if (lhsv->may_have_pointers
3483 && ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3484 rhsv->offset + lhsoffset, rhsv->size))
3485 process_constraint (new_constraint (*lhsp, *rhsp));
3486 if (lhsv->offset + rhsoffset + lhsv->size
3487 > rhsv->offset + lhsoffset + rhsv->size)
3490 if (k >= VEC_length (ce_s, rhsc))
3500 VEC_free (ce_s, heap, lhsc);
3501 VEC_free (ce_s, heap, rhsc);
3504 /* Create a constraint ID = OP. */
3507 make_constraint_to (unsigned id, tree op)
3509 VEC(ce_s, heap) *rhsc = NULL;
3510 struct constraint_expr *c;
3511 struct constraint_expr includes;
3515 includes.offset = 0;
3516 includes.type = SCALAR;
3518 get_constraint_for (op, &rhsc);
3519 for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3520 process_constraint (new_constraint (includes, *c));
3521 VEC_free (ce_s, heap, rhsc);
3524 /* Create a constraint ID = &FROM. */
3527 make_constraint_from (varinfo_t vi, int from)
3529 struct constraint_expr lhs, rhs;
3537 rhs.type = ADDRESSOF;
3538 process_constraint (new_constraint (lhs, rhs));
3541 /* Create a constraint ID = FROM. */
3544 make_copy_constraint (varinfo_t vi, int from)
3546 struct constraint_expr lhs, rhs;
3555 process_constraint (new_constraint (lhs, rhs));
3558 /* Make constraints necessary to make OP escape. */
3561 make_escape_constraint (tree op)
3563 make_constraint_to (escaped_id, op);
3566 /* Add constraints to that the solution of VI is transitively closed. */
3569 make_transitive_closure_constraints (varinfo_t vi)
3571 struct constraint_expr lhs, rhs;
3580 process_constraint (new_constraint (lhs, rhs));
3582 /* VAR = VAR + UNKNOWN; */
3588 rhs.offset = UNKNOWN_OFFSET;
3589 process_constraint (new_constraint (lhs, rhs));
3592 /* Create a new artificial heap variable with NAME and make a
3593 constraint from it to LHS. Return the created variable. */
3596 make_constraint_from_heapvar (varinfo_t lhs, const char *name)
3599 tree heapvar = heapvar_lookup (lhs->decl, lhs->offset);
3601 if (heapvar == NULL_TREE)
3604 heapvar = create_tmp_var_raw (ptr_type_node, name);
3605 DECL_EXTERNAL (heapvar) = 1;
3607 heapvar_insert (lhs->decl, lhs->offset, heapvar);
3609 ann = get_var_ann (heapvar);
3610 ann->is_heapvar = 1;
3613 /* For global vars we need to add a heapvar to the list of referenced
3614 vars of a different function than it was created for originally. */
3615 if (cfun && gimple_referenced_vars (cfun))
3616 add_referenced_var (heapvar);
3618 vi = new_var_info (heapvar, name);
3619 vi->is_artificial_var = true;
3620 vi->is_heap_var = true;
3621 vi->is_unknown_size_var = true;
3625 vi->is_full_var = true;
3626 insert_vi_for_tree (heapvar, vi);
3628 make_constraint_from (lhs, vi->id);
3633 /* Create a new artificial heap variable with NAME and make a
3634 constraint from it to LHS. Set flags according to a tag used
3635 for tracking restrict pointers. */
3638 make_constraint_from_restrict (varinfo_t lhs, const char *name)
3641 vi = make_constraint_from_heapvar (lhs, name);
3642 vi->is_restrict_var = 1;
3643 vi->is_global_var = 0;
3644 vi->is_special_var = 1;
3645 vi->may_have_pointers = 0;
3648 /* In IPA mode there are varinfos for different aspects of reach
3649 function designator. One for the points-to set of the return
3650 value, one for the variables that are clobbered by the function,
3651 one for its uses and one for each parameter (including a single
3652 glob for remaining variadic arguments). */
3654 enum { fi_clobbers = 1, fi_uses = 2,
3655 fi_static_chain = 3, fi_result = 4, fi_parm_base = 5 };
3657 /* Get a constraint for the requested part of a function designator FI
3658 when operating in IPA mode. */
3660 static struct constraint_expr
3661 get_function_part_constraint (varinfo_t fi, unsigned part)
3663 struct constraint_expr c;
3665 gcc_assert (in_ipa_mode);
3667 if (fi->id == anything_id)
3669 /* ??? We probably should have a ANYFN special variable. */
3670 c.var = anything_id;
3674 else if (TREE_CODE (fi->decl) == FUNCTION_DECL)
3676 varinfo_t ai = first_vi_for_offset (fi, part);
3680 c.var = anything_id;
3694 /* For non-IPA mode, generate constraints necessary for a call on the
3698 handle_rhs_call (gimple stmt, VEC(ce_s, heap) **results)
3700 struct constraint_expr rhsc;
3703 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3705 tree arg = gimple_call_arg (stmt, i);
3707 /* Find those pointers being passed, and make sure they end up
3708 pointing to anything. */
3709 if (could_have_pointers (arg))
3710 make_escape_constraint (arg);
3713 /* The static chain escapes as well. */
3714 if (gimple_call_chain (stmt))
3715 make_escape_constraint (gimple_call_chain (stmt));
3717 /* And if we applied NRV the address of the return slot escapes as well. */
3718 if (gimple_call_return_slot_opt_p (stmt)
3719 && gimple_call_lhs (stmt) != NULL_TREE
3720 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
3722 VEC(ce_s, heap) *tmpc = NULL;
3723 struct constraint_expr lhsc, *c;
3724 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
3725 lhsc.var = escaped_id;
3728 for (i = 0; VEC_iterate (ce_s, tmpc, i, c); ++i)
3729 process_constraint (new_constraint (lhsc, *c));
3730 VEC_free(ce_s, heap, tmpc);
3733 /* Regular functions return nonlocal memory. */
3734 rhsc.var = nonlocal_id;
3737 VEC_safe_push (ce_s, heap, *results, &rhsc);
3740 /* For non-IPA mode, generate constraints necessary for a call
3741 that returns a pointer and assigns it to LHS. This simply makes
3742 the LHS point to global and escaped variables. */
3745 handle_lhs_call (tree lhs, int flags, VEC(ce_s, heap) *rhsc, tree fndecl)
3747 VEC(ce_s, heap) *lhsc = NULL;
3749 get_constraint_for (lhs, &lhsc);
3751 if (flags & ECF_MALLOC)
3754 vi = make_constraint_from_heapvar (get_vi_for_tree (lhs), "HEAP");
3755 /* We delay marking allocated storage global until we know if
3757 DECL_EXTERNAL (vi->decl) = 0;
3758 vi->is_global_var = 0;
3759 /* If this is not a real malloc call assume the memory was
3760 initialized and thus may point to global memory. All
3761 builtin functions with the malloc attribute behave in a sane way. */
3763 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
3764 make_constraint_from (vi, nonlocal_id);
3766 else if (VEC_length (ce_s, rhsc) > 0)
3768 /* If the store is to a global decl make sure to
3769 add proper escape constraints. */
3770 lhs = get_base_address (lhs);
3773 && is_global_var (lhs))
3775 struct constraint_expr tmpc;
3776 tmpc.var = escaped_id;
3779 VEC_safe_push (ce_s, heap, lhsc, &tmpc);
3781 process_all_all_constraints (lhsc, rhsc);
3783 VEC_free (ce_s, heap, lhsc);
3786 /* For non-IPA mode, generate constraints necessary for a call of a
3787 const function that returns a pointer in the statement STMT. */
3790 handle_const_call (gimple stmt, VEC(ce_s, heap) **results)
3792 struct constraint_expr rhsc;
3795 /* Treat nested const functions the same as pure functions as far
3796 as the static chain is concerned. */
3797 if (gimple_call_chain (stmt))
3799 varinfo_t uses = get_call_use_vi (stmt);
3800 make_transitive_closure_constraints (uses);
3801 make_constraint_to (uses->id, gimple_call_chain (stmt));
3802 rhsc.var = uses->id;
3805 VEC_safe_push (ce_s, heap, *results, &rhsc);
3808 /* May return arguments. */
3809 for (k = 0; k < gimple_call_num_args (stmt); ++k)
3811 tree arg = gimple_call_arg (stmt, k);
3813 if (could_have_pointers (arg))
3815 VEC(ce_s, heap) *argc = NULL;
3817 struct constraint_expr *argp;
3818 get_constraint_for (arg, &argc);
3819 for (i = 0; VEC_iterate (ce_s, argc, i, argp); ++i)
3820 VEC_safe_push (ce_s, heap, *results, argp);
3821 VEC_free(ce_s, heap, argc);
3825 /* May return addresses of globals. */
3826 rhsc.var = nonlocal_id;
3828 rhsc.type = ADDRESSOF;
3829 VEC_safe_push (ce_s, heap, *results, &rhsc);
3832 /* For non-IPA mode, generate constraints necessary for a call to a
3833 pure function in statement STMT. */
3836 handle_pure_call (gimple stmt, VEC(ce_s, heap) **results)
3838 struct constraint_expr rhsc;
3840 varinfo_t uses = NULL;
3842 /* Memory reached from pointer arguments is call-used. */
3843 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3845 tree arg = gimple_call_arg (stmt, i);
3847 if (could_have_pointers (arg))
3851 uses = get_call_use_vi (stmt);
3852 make_transitive_closure_constraints (uses);
3854 make_constraint_to (uses->id, arg);
3858 /* The static chain is used as well. */
3859 if (gimple_call_chain (stmt))
3863 uses = get_call_use_vi (stmt);
3864 make_transitive_closure_constraints (uses);
3866 make_constraint_to (uses->id, gimple_call_chain (stmt));
3869 /* Pure functions may return call-used and nonlocal memory. */
3872 rhsc.var = uses->id;
3875 VEC_safe_push (ce_s, heap, *results, &rhsc);
3877 rhsc.var = nonlocal_id;
3880 VEC_safe_push (ce_s, heap, *results, &rhsc);
3884 /* Return the varinfo for the callee of CALL. */
3887 get_fi_for_callee (gimple call)
3891 /* If we can directly resolve the function being called, do so.
3892 Otherwise, it must be some sort of indirect expression that
3893 we should still be able to handle. */
3894 decl = gimple_call_fndecl (call);
3896 return get_vi_for_tree (decl);
3898 decl = gimple_call_fn (call);
3899 /* The function can be either an SSA name pointer or,
3900 worse, an OBJ_TYPE_REF. In this case we have no
3901 clue and should be getting ANYFN (well, ANYTHING for now). */
3902 if (TREE_CODE (decl) == SSA_NAME)
3904 if (TREE_CODE (decl) == SSA_NAME
3905 && TREE_CODE (SSA_NAME_VAR (decl)) == PARM_DECL
3906 && SSA_NAME_IS_DEFAULT_DEF (decl))
3907 decl = SSA_NAME_VAR (decl);
3908 return get_vi_for_tree (decl);
3910 else if (TREE_CODE (decl) == INTEGER_CST
3911 || TREE_CODE (decl) == OBJ_TYPE_REF)
3912 return get_varinfo (anything_id);
3917 /* Walk statement T setting up aliasing constraints according to the
3918 references found in T. This function is the main part of the
3919 constraint builder. AI points to auxiliary alias information used
3920 when building alias sets and computing alias grouping heuristics. */
3923 find_func_aliases (gimple origt)
3926 VEC(ce_s, heap) *lhsc = NULL;
3927 VEC(ce_s, heap) *rhsc = NULL;
3928 struct constraint_expr *c;
3931 /* Now build constraints expressions. */
3932 if (gimple_code (t) == GIMPLE_PHI)
3934 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (gimple_phi_result (t))));
3936 /* Only care about pointers and structures containing
3938 if (could_have_pointers (gimple_phi_result (t)))
3943 /* For a phi node, assign all the arguments to
3945 get_constraint_for (gimple_phi_result (t), &lhsc);
3946 for (i = 0; i < gimple_phi_num_args (t); i++)
3948 tree strippedrhs = PHI_ARG_DEF (t, i);
3950 STRIP_NOPS (strippedrhs);
3951 get_constraint_for (gimple_phi_arg_def (t, i), &rhsc);
3953 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3955 struct constraint_expr *c2;
3956 while (VEC_length (ce_s, rhsc) > 0)
3958 c2 = VEC_last (ce_s, rhsc);
3959 process_constraint (new_constraint (*c, *c2));
3960 VEC_pop (ce_s, rhsc);
3966 /* In IPA mode, we need to generate constraints to pass call
3967 arguments through their calls. There are two cases,
3968 either a GIMPLE_CALL returning a value, or just a plain
3969 GIMPLE_CALL when we are not.
3971 In non-ipa mode, we need to generate constraints for each
3972 pointer passed by address. */
3973 else if (is_gimple_call (t))
3975 tree fndecl = gimple_call_fndecl (t);
3976 if (fndecl != NULL_TREE
3977 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
3978 /* ??? All builtins that are handled here need to be handled
3979 in the alias-oracle query functions explicitly! */
3980 switch (DECL_FUNCTION_CODE (fndecl))
3982 /* All the following functions return a pointer to the same object
3983 as their first argument points to. The functions do not add
3984 to the ESCAPED solution. The functions make the first argument
3985 pointed to memory point to what the second argument pointed to
3986 memory points to. */
3987 case BUILT_IN_STRCPY:
3988 case BUILT_IN_STRNCPY:
3989 case BUILT_IN_BCOPY:
3990 case BUILT_IN_MEMCPY:
3991 case BUILT_IN_MEMMOVE:
3992 case BUILT_IN_MEMPCPY:
3993 case BUILT_IN_STPCPY:
3994 case BUILT_IN_STPNCPY:
3995 case BUILT_IN_STRCAT:
3996 case BUILT_IN_STRNCAT:
3998 tree res = gimple_call_lhs (t);
3999 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4000 == BUILT_IN_BCOPY ? 1 : 0));
4001 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4002 == BUILT_IN_BCOPY ? 0 : 1));
4003 if (res != NULL_TREE)
4005 get_constraint_for (res, &lhsc);
4006 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
4007 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
4008 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY)
4009 get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
4011 get_constraint_for (dest, &rhsc);
4012 process_all_all_constraints (lhsc, rhsc);
4013 VEC_free (ce_s, heap, lhsc);
4014 VEC_free (ce_s, heap, rhsc);
4016 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4017 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4020 process_all_all_constraints (lhsc, rhsc);
4021 VEC_free (ce_s, heap, lhsc);
4022 VEC_free (ce_s, heap, rhsc);
4025 case BUILT_IN_MEMSET:
4027 tree res = gimple_call_lhs (t);
4028 tree dest = gimple_call_arg (t, 0);
4031 struct constraint_expr ac;
4032 if (res != NULL_TREE)
4034 get_constraint_for (res, &lhsc);
4035 get_constraint_for (dest, &rhsc);
4036 process_all_all_constraints (lhsc, rhsc);
4037 VEC_free (ce_s, heap, lhsc);
4038 VEC_free (ce_s, heap, rhsc);
4040 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4042 if (flag_delete_null_pointer_checks
4043 && integer_zerop (gimple_call_arg (t, 1)))
4045 ac.type = ADDRESSOF;
4046 ac.var = nothing_id;
4051 ac.var = integer_id;
4054 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
4055 process_constraint (new_constraint (*lhsp, ac));
4056 VEC_free (ce_s, heap, lhsc);
4059 /* All the following functions do not return pointers, do not
4060 modify the points-to sets of memory reachable from their
4061 arguments and do not add to the ESCAPED solution. */
4062 case BUILT_IN_SINCOS:
4063 case BUILT_IN_SINCOSF:
4064 case BUILT_IN_SINCOSL:
4065 case BUILT_IN_FREXP:
4066 case BUILT_IN_FREXPF:
4067 case BUILT_IN_FREXPL:
4068 case BUILT_IN_GAMMA_R:
4069 case BUILT_IN_GAMMAF_R:
4070 case BUILT_IN_GAMMAL_R:
4071 case BUILT_IN_LGAMMA_R:
4072 case BUILT_IN_LGAMMAF_R:
4073 case BUILT_IN_LGAMMAL_R:
4075 case BUILT_IN_MODFF:
4076 case BUILT_IN_MODFL:
4077 case BUILT_IN_REMQUO:
4078 case BUILT_IN_REMQUOF:
4079 case BUILT_IN_REMQUOL:
4082 /* Trampolines are special - they set up passing the static
4084 case BUILT_IN_INIT_TRAMPOLINE:
4086 tree tramp = gimple_call_arg (t, 0);
4087 tree nfunc = gimple_call_arg (t, 1);
4088 tree frame = gimple_call_arg (t, 2);
4090 struct constraint_expr lhs, *rhsp;
4093 varinfo_t nfi = NULL;
4094 gcc_assert (TREE_CODE (nfunc) == ADDR_EXPR);
4095 nfi = lookup_vi_for_tree (TREE_OPERAND (nfunc, 0));
4098 lhs = get_function_part_constraint (nfi, fi_static_chain);
4099 get_constraint_for (frame, &rhsc);
4100 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
4101 process_constraint (new_constraint (lhs, *rhsp));
4102 VEC_free (ce_s, heap, rhsc);
4104 /* Make the frame point to the function for
4105 the trampoline adjustment call. */
4106 get_constraint_for (tramp, &lhsc);
4108 get_constraint_for (nfunc, &rhsc);
4109 process_all_all_constraints (lhsc, rhsc);
4110 VEC_free (ce_s, heap, rhsc);
4111 VEC_free (ce_s, heap, lhsc);
4116 /* Else fallthru to generic handling which will let
4117 the frame escape. */
4120 case BUILT_IN_ADJUST_TRAMPOLINE:
4122 tree tramp = gimple_call_arg (t, 0);
4123 tree res = gimple_call_lhs (t);
4124 if (in_ipa_mode && res)
4126 get_constraint_for (res, &lhsc);
4127 get_constraint_for (tramp, &rhsc);
4129 process_all_all_constraints (lhsc, rhsc);
4130 VEC_free (ce_s, heap, rhsc);
4131 VEC_free (ce_s, heap, lhsc);
4135 /* Variadic argument handling needs to be handled in IPA
4137 case BUILT_IN_VA_START:
4141 tree valist = gimple_call_arg (t, 0);
4142 struct constraint_expr rhs, *lhsp;
4144 /* The va_list gets access to pointers in variadic
4146 fi = lookup_vi_for_tree (cfun->decl);
4147 gcc_assert (fi != NULL);
4148 get_constraint_for (valist, &lhsc);
4150 rhs = get_function_part_constraint (fi, ~0);
4151 rhs.type = ADDRESSOF;
4152 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
4153 process_constraint (new_constraint (*lhsp, rhs));
4154 VEC_free (ce_s, heap, lhsc);
4155 /* va_list is clobbered. */
4156 make_constraint_to (get_call_clobber_vi (t)->id, valist);
4161 /* va_end doesn't have any effect that matters. */
4162 case BUILT_IN_VA_END:
4164 /* printf-style functions may have hooks to set pointers to
4165 point to somewhere into the generated string. Leave them
4166 for a later excercise... */
4168 /* Fallthru to general call handling. */;
4172 && (!(fi = lookup_vi_for_tree (fndecl))
4173 || !fi->is_fn_info)))
4175 VEC(ce_s, heap) *rhsc = NULL;
4176 int flags = gimple_call_flags (t);
4178 /* Const functions can return their arguments and addresses
4179 of global memory but not of escaped memory. */
4180 if (flags & (ECF_CONST|ECF_NOVOPS))
4182 if (gimple_call_lhs (t)
4183 && could_have_pointers (gimple_call_lhs (t)))
4184 handle_const_call (t, &rhsc);
4186 /* Pure functions can return addresses in and of memory
4187 reachable from their arguments, but they are not an escape
4188 point for reachable memory of their arguments. */
4189 else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE))
4190 handle_pure_call (t, &rhsc);
4192 handle_rhs_call (t, &rhsc);
4193 if (gimple_call_lhs (t)
4194 && could_have_pointers (gimple_call_lhs (t)))
4195 handle_lhs_call (gimple_call_lhs (t), flags, rhsc, fndecl);
4196 VEC_free (ce_s, heap, rhsc);
4203 fi = get_fi_for_callee (t);
4205 /* Assign all the passed arguments to the appropriate incoming
4206 parameters of the function. */
4207 for (j = 0; j < gimple_call_num_args (t); j++)
4209 struct constraint_expr lhs ;
4210 struct constraint_expr *rhsp;
4211 tree arg = gimple_call_arg (t, j);
4213 if (!could_have_pointers (arg))
4216 get_constraint_for (arg, &rhsc);
4217 lhs = get_function_part_constraint (fi, fi_parm_base + j);
4218 while (VEC_length (ce_s, rhsc) != 0)
4220 rhsp = VEC_last (ce_s, rhsc);
4221 process_constraint (new_constraint (lhs, *rhsp));
4222 VEC_pop (ce_s, rhsc);
4226 /* If we are returning a value, assign it to the result. */
4227 lhsop = gimple_call_lhs (t);
4229 && could_have_pointers (lhsop))
4231 struct constraint_expr rhs;
4232 struct constraint_expr *lhsp;
4234 get_constraint_for (lhsop, &lhsc);
4235 rhs = get_function_part_constraint (fi, fi_result);
4237 && DECL_RESULT (fndecl)
4238 && DECL_BY_REFERENCE (DECL_RESULT (fndecl)))
4240 VEC(ce_s, heap) *tem = NULL;
4241 VEC_safe_push (ce_s, heap, tem, &rhs);
4243 rhs = *VEC_index (ce_s, tem, 0);
4244 VEC_free(ce_s, heap, tem);
4246 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
4247 process_constraint (new_constraint (*lhsp, rhs));
4250 /* If we pass the result decl by reference, honor that. */
4253 && DECL_RESULT (fndecl)
4254 && DECL_BY_REFERENCE (DECL_RESULT (fndecl)))
4256 struct constraint_expr lhs;
4257 struct constraint_expr *rhsp;
4259 get_constraint_for_address_of (lhsop, &rhsc);
4260 lhs = get_function_part_constraint (fi, fi_result);
4261 for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); j++)
4262 process_constraint (new_constraint (lhs, *rhsp));
4263 VEC_free (ce_s, heap, rhsc);
4266 /* If we use a static chain, pass it along. */
4267 if (gimple_call_chain (t))
4269 struct constraint_expr lhs;
4270 struct constraint_expr *rhsp;
4272 get_constraint_for (gimple_call_chain (t), &rhsc);
4273 lhs = get_function_part_constraint (fi, fi_static_chain);
4274 for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); j++)
4275 process_constraint (new_constraint (lhs, *rhsp));
4279 /* Otherwise, just a regular assignment statement. Only care about
4280 operations with pointer result, others are dealt with as escape
4281 points if they have pointer operands. */
4282 else if (is_gimple_assign (t)
4283 && could_have_pointers (gimple_assign_lhs (t)))
4285 /* Otherwise, just a regular assignment statement. */
4286 tree lhsop = gimple_assign_lhs (t);
4287 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
4289 if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
4290 do_structure_copy (lhsop, rhsop);
4293 struct constraint_expr temp;
4294 get_constraint_for (lhsop, &lhsc);
4296 if (gimple_assign_rhs_code (t) == POINTER_PLUS_EXPR)
4297 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4298 gimple_assign_rhs2 (t), &rhsc);
4299 else if ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
4300 && !(POINTER_TYPE_P (gimple_expr_type (t))
4301 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
4302 || gimple_assign_single_p (t))
4303 get_constraint_for (rhsop, &rhsc);
4306 temp.type = ADDRESSOF;
4307 temp.var = anything_id;
4309 VEC_safe_push (ce_s, heap, rhsc, &temp);
4311 process_all_all_constraints (lhsc, rhsc);
4313 /* If there is a store to a global variable the rhs escapes. */
4314 if ((lhsop = get_base_address (lhsop)) != NULL_TREE
4316 && is_global_var (lhsop)
4318 || DECL_EXTERNAL (lhsop) || TREE_PUBLIC (lhsop)))
4319 make_escape_constraint (rhsop);
4320 /* If this is a conversion of a non-restrict pointer to a
4321 restrict pointer track it with a new heapvar. */
4322 else if (gimple_assign_cast_p (t)
4323 && POINTER_TYPE_P (TREE_TYPE (rhsop))
4324 && POINTER_TYPE_P (TREE_TYPE (lhsop))
4325 && !TYPE_RESTRICT (TREE_TYPE (rhsop))
4326 && TYPE_RESTRICT (TREE_TYPE (lhsop)))
4327 make_constraint_from_restrict (get_vi_for_tree (lhsop),
4330 /* For conversions of pointers to non-pointers the pointer escapes. */
4331 else if (gimple_assign_cast_p (t)
4332 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (t)))
4333 && !POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (t))))
4335 make_escape_constraint (gimple_assign_rhs1 (t));
4337 /* Handle escapes through return. */
4338 else if (gimple_code (t) == GIMPLE_RETURN
4339 && gimple_return_retval (t) != NULL_TREE
4340 && could_have_pointers (gimple_return_retval (t)))
4344 || !(fi = get_vi_for_tree (cfun->decl)))
4345 make_escape_constraint (gimple_return_retval (t));
4346 else if (in_ipa_mode
4349 struct constraint_expr lhs ;
4350 struct constraint_expr *rhsp;
4353 lhs = get_function_part_constraint (fi, fi_result);
4354 get_constraint_for (gimple_return_retval (t), &rhsc);
4355 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); i++)
4356 process_constraint (new_constraint (lhs, *rhsp));
4359 /* Handle asms conservatively by adding escape constraints to everything. */
4360 else if (gimple_code (t) == GIMPLE_ASM)
4362 unsigned i, noutputs;
4363 const char **oconstraints;
4364 const char *constraint;
4365 bool allows_mem, allows_reg, is_inout;
4367 noutputs = gimple_asm_noutputs (t);
4368 oconstraints = XALLOCAVEC (const char *, noutputs);
4370 for (i = 0; i < noutputs; ++i)
4372 tree link = gimple_asm_output_op (t, i);
4373 tree op = TREE_VALUE (link);
4375 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4376 oconstraints[i] = constraint;
4377 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
4378 &allows_reg, &is_inout);
4380 /* A memory constraint makes the address of the operand escape. */
4381 if (!allows_reg && allows_mem)
4382 make_escape_constraint (build_fold_addr_expr (op));
4384 /* The asm may read global memory, so outputs may point to
4385 any global memory. */
4386 if (op && could_have_pointers (op))
4388 VEC(ce_s, heap) *lhsc = NULL;
4389 struct constraint_expr rhsc, *lhsp;
4391 get_constraint_for (op, &lhsc);
4392 rhsc.var = nonlocal_id;
4395 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
4396 process_constraint (new_constraint (*lhsp, rhsc));
4397 VEC_free (ce_s, heap, lhsc);
4400 for (i = 0; i < gimple_asm_ninputs (t); ++i)
4402 tree link = gimple_asm_input_op (t, i);
4403 tree op = TREE_VALUE (link);
4405 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4407 parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
4408 &allows_mem, &allows_reg);
4410 /* A memory constraint makes the address of the operand escape. */
4411 if (!allows_reg && allows_mem)
4412 make_escape_constraint (build_fold_addr_expr (op));
4413 /* Strictly we'd only need the constraint to ESCAPED if
4414 the asm clobbers memory, otherwise using something
4415 along the lines of per-call clobbers/uses would be enough. */
4416 else if (op && could_have_pointers (op))
4417 make_escape_constraint (op);
4421 VEC_free (ce_s, heap, rhsc);
4422 VEC_free (ce_s, heap, lhsc);
4426 /* Create a constraint adding to the clobber set of FI the memory
4427 pointed to by PTR. */
4430 process_ipa_clobber (varinfo_t fi, tree ptr)
4432 VEC(ce_s, heap) *ptrc = NULL;
4433 struct constraint_expr *c, lhs;
4435 get_constraint_for (ptr, &ptrc);
4436 lhs = get_function_part_constraint (fi, fi_clobbers);
4437 for (i = 0; VEC_iterate (ce_s, ptrc, i, c); i++)
4438 process_constraint (new_constraint (lhs, *c));
4439 VEC_free (ce_s, heap, ptrc);
4442 /* Walk statement T setting up clobber and use constraints according to the
4443 references found in T. This function is a main part of the
4444 IPA constraint builder. */
4447 find_func_clobbers (gimple origt)
4450 VEC(ce_s, heap) *lhsc = NULL;
4451 VEC(ce_s, heap) *rhsc = NULL;
4454 /* Add constraints for clobbered/used in IPA mode.
4455 We are not interested in what automatic variables are clobbered
4456 or used as we only use the information in the caller to which
4457 they do not escape. */
4458 gcc_assert (in_ipa_mode);
4460 /* If the stmt refers to memory in any way it better had a VUSE. */
4461 if (gimple_vuse (t) == NULL_TREE)
4464 /* We'd better have function information for the current function. */
4465 fi = lookup_vi_for_tree (cfun->decl);
4466 gcc_assert (fi != NULL);
4468 /* Account for stores in assignments and calls. */
4469 if (gimple_vdef (t) != NULL_TREE
4470 && gimple_has_lhs (t))
4472 tree lhs = gimple_get_lhs (t);
4474 while (handled_component_p (tem))
4475 tem = TREE_OPERAND (tem, 0);
4477 && !auto_var_in_fn_p (tem, cfun->decl))
4478 || INDIRECT_REF_P (tem))
4480 struct constraint_expr lhsc, *rhsp;
4482 lhsc = get_function_part_constraint (fi, fi_clobbers);
4483 get_constraint_for_address_of (lhs, &rhsc);
4484 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); i++)
4485 process_constraint (new_constraint (lhsc, *rhsp));
4486 VEC_free (ce_s, heap, rhsc);
4490 /* Account for uses in assigments and returns. */
4491 if (gimple_assign_single_p (t)
4492 || (gimple_code (t) == GIMPLE_RETURN
4493 && gimple_return_retval (t) != NULL_TREE))
4495 tree rhs = (gimple_assign_single_p (t)
4496 ? gimple_assign_rhs1 (t) : gimple_return_retval (t));
4498 while (handled_component_p (tem))
4499 tem = TREE_OPERAND (tem, 0);
4501 && !auto_var_in_fn_p (tem, cfun->decl))
4502 || INDIRECT_REF_P (tem))
4504 struct constraint_expr lhs, *rhsp;
4506 lhs = get_function_part_constraint (fi, fi_uses);
4507 get_constraint_for_address_of (rhs, &rhsc);
4508 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); i++)
4509 process_constraint (new_constraint (lhs, *rhsp));
4510 VEC_free (ce_s, heap, rhsc);
4514 if (is_gimple_call (t))
4516 varinfo_t cfi = NULL;
4517 tree decl = gimple_call_fndecl (t);
4518 struct constraint_expr lhs, rhs;
4521 /* For builtins we do not have separate function info. For those
4522 we do not generate escapes for we have to generate clobbers/uses. */
4524 && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
4525 switch (DECL_FUNCTION_CODE (decl))
4527 /* The following functions use and clobber memory pointed to
4528 by their arguments. */
4529 case BUILT_IN_STRCPY:
4530 case BUILT_IN_STRNCPY:
4531 case BUILT_IN_BCOPY:
4532 case BUILT_IN_MEMCPY:
4533 case BUILT_IN_MEMMOVE:
4534 case BUILT_IN_MEMPCPY:
4535 case BUILT_IN_STPCPY:
4536 case BUILT_IN_STPNCPY:
4537 case BUILT_IN_STRCAT:
4538 case BUILT_IN_STRNCAT:
4540 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
4541 == BUILT_IN_BCOPY ? 1 : 0));
4542 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
4543 == BUILT_IN_BCOPY ? 0 : 1));
4545 struct constraint_expr *rhsp, *lhsp;
4546 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4547 lhs = get_function_part_constraint (fi, fi_clobbers);
4548 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); i++)
4549 process_constraint (new_constraint (lhs, *lhsp));
4550 VEC_free (ce_s, heap, lhsc);
4551 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4552 lhs = get_function_part_constraint (fi, fi_uses);
4553 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); i++)
4554 process_constraint (new_constraint (lhs, *rhsp));
4555 VEC_free (ce_s, heap, rhsc);
4558 /* The following function clobbers memory pointed to by
4560 case BUILT_IN_MEMSET:
4562 tree dest = gimple_call_arg (t, 0);
4565 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4566 lhs = get_function_part_constraint (fi, fi_clobbers);
4567 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); i++)
4568 process_constraint (new_constraint (lhs, *lhsp));
4569 VEC_free (ce_s, heap, lhsc);
4572 /* The following functions clobber their second and third
4574 case BUILT_IN_SINCOS:
4575 case BUILT_IN_SINCOSF:
4576 case BUILT_IN_SINCOSL:
4578 process_ipa_clobber (fi, gimple_call_arg (t, 1));
4579 process_ipa_clobber (fi, gimple_call_arg (t, 2));
4582 /* The following functions clobber their second argument. */
4583 case BUILT_IN_FREXP:
4584 case BUILT_IN_FREXPF:
4585 case BUILT_IN_FREXPL:
4586 case BUILT_IN_LGAMMA_R:
4587 case BUILT_IN_LGAMMAF_R:
4588 case BUILT_IN_LGAMMAL_R:
4589 case BUILT_IN_GAMMA_R:
4590 case BUILT_IN_GAMMAF_R:
4591 case BUILT_IN_GAMMAL_R:
4593 case BUILT_IN_MODFF:
4594 case BUILT_IN_MODFL:
4596 process_ipa_clobber (fi, gimple_call_arg (t, 1));
4599 /* The following functions clobber their third argument. */
4600 case BUILT_IN_REMQUO:
4601 case BUILT_IN_REMQUOF:
4602 case BUILT_IN_REMQUOL:
4604 process_ipa_clobber (fi, gimple_call_arg (t, 2));
4607 /* The following functions neither read nor clobber memory. */
4610 /* Trampolines are of no interest to us. */
4611 case BUILT_IN_INIT_TRAMPOLINE:
4612 case BUILT_IN_ADJUST_TRAMPOLINE:
4614 case BUILT_IN_VA_START:
4615 case BUILT_IN_VA_END:
4617 /* printf-style functions may have hooks to set pointers to
4618 point to somewhere into the generated string. Leave them
4619 for a later excercise... */
4621 /* Fallthru to general call handling. */;
4624 /* Parameters passed by value are used. */
4625 lhs = get_function_part_constraint (fi, fi_uses);
4626 for (i = 0; i < gimple_call_num_args (t); i++)
4628 struct constraint_expr *rhsp;
4629 tree arg = gimple_call_arg (t, i);
4631 if (TREE_CODE (arg) == SSA_NAME
4632 || is_gimple_min_invariant (arg))
4635 get_constraint_for_address_of (arg, &rhsc);
4636 for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); j++)
4637 process_constraint (new_constraint (lhs, *rhsp));
4638 VEC_free (ce_s, heap, rhsc);
4641 /* Build constraints for propagating clobbers/uses along the
4643 cfi = get_fi_for_callee (t);
4644 if (cfi->id == anything_id)
4646 if (gimple_vdef (t))
4647 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
4649 make_constraint_from (first_vi_for_offset (fi, fi_uses),
4654 /* For callees without function info (that's external functions),
4655 ESCAPED is clobbered and used. */
4656 if (gimple_call_fndecl (t)
4657 && !cfi->is_fn_info)
4661 if (gimple_vdef (t))
4662 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
4664 make_copy_constraint (first_vi_for_offset (fi, fi_uses), escaped_id);
4666 /* Also honor the call statement use/clobber info. */
4667 if ((vi = lookup_call_clobber_vi (t)) != NULL)
4668 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
4670 if ((vi = lookup_call_use_vi (t)) != NULL)
4671 make_copy_constraint (first_vi_for_offset (fi, fi_uses),
4676 /* Otherwise the caller clobbers and uses what the callee does.
4677 ??? This should use a new complex constraint that filters
4678 local variables of the callee. */
4679 if (gimple_vdef (t))
4681 lhs = get_function_part_constraint (fi, fi_clobbers);
4682 rhs = get_function_part_constraint (cfi, fi_clobbers);
4683 process_constraint (new_constraint (lhs, rhs));
4685 lhs = get_function_part_constraint (fi, fi_uses);
4686 rhs = get_function_part_constraint (cfi, fi_uses);
4687 process_constraint (new_constraint (lhs, rhs));
4689 else if (gimple_code (t) == GIMPLE_ASM)
4691 /* ??? Ick. We can do better. */
4692 if (gimple_vdef (t))
4693 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
4695 make_constraint_from (first_vi_for_offset (fi, fi_uses),
4699 VEC_free (ce_s, heap, rhsc);
4703 /* Find the first varinfo in the same variable as START that overlaps with
4704 OFFSET. Return NULL if we can't find one. */
4707 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
4709 /* If the offset is outside of the variable, bail out. */
4710 if (offset >= start->fullsize)
4713 /* If we cannot reach offset from start, lookup the first field
4714 and start from there. */
4715 if (start->offset > offset)
4716 start = lookup_vi_for_tree (start->decl);
4720 /* We may not find a variable in the field list with the actual
4721 offset when when we have glommed a structure to a variable.
4722 In that case, however, offset should still be within the size
4724 if (offset >= start->offset
4725 && (offset - start->offset) < start->size)
4734 /* Find the first varinfo in the same variable as START that overlaps with
4735 OFFSET. If there is no such varinfo the varinfo directly preceding
4736 OFFSET is returned. */
4739 first_or_preceding_vi_for_offset (varinfo_t start,
4740 unsigned HOST_WIDE_INT offset)
4742 /* If we cannot reach offset from start, lookup the first field
4743 and start from there. */
4744 if (start->offset > offset)
4745 start = lookup_vi_for_tree (start->decl);
4747 /* We may not find a variable in the field list with the actual
4748 offset when when we have glommed a structure to a variable.
4749 In that case, however, offset should still be within the size
4751 If we got beyond the offset we look for return the field
4752 directly preceding offset which may be the last field. */
4754 && offset >= start->offset
4755 && !((offset - start->offset) < start->size))
4756 start = start->next;
4762 /* This structure is used during pushing fields onto the fieldstack
4763 to track the offset of the field, since bitpos_of_field gives it
4764 relative to its immediate containing type, and we want it relative
4765 to the ultimate containing object. */
4769 /* Offset from the base of the base containing object to this field. */
4770 HOST_WIDE_INT offset;
4772 /* Size, in bits, of the field. */
4773 unsigned HOST_WIDE_INT size;
4775 unsigned has_unknown_size : 1;
4777 unsigned may_have_pointers : 1;
4779 unsigned only_restrict_pointers : 1;
4781 typedef struct fieldoff fieldoff_s;
4783 DEF_VEC_O(fieldoff_s);
4784 DEF_VEC_ALLOC_O(fieldoff_s,heap);
4786 /* qsort comparison function for two fieldoff's PA and PB */
4789 fieldoff_compare (const void *pa, const void *pb)
4791 const fieldoff_s *foa = (const fieldoff_s *)pa;
4792 const fieldoff_s *fob = (const fieldoff_s *)pb;
4793 unsigned HOST_WIDE_INT foasize, fobsize;
4795 if (foa->offset < fob->offset)
4797 else if (foa->offset > fob->offset)
4800 foasize = foa->size;
4801 fobsize = fob->size;
4802 if (foasize < fobsize)
4804 else if (foasize > fobsize)
4809 /* Sort a fieldstack according to the field offset and sizes. */
4811 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
4813 qsort (VEC_address (fieldoff_s, fieldstack),
4814 VEC_length (fieldoff_s, fieldstack),
4815 sizeof (fieldoff_s),
4819 /* Return true if V is a tree that we can have subvars for.
4820 Normally, this is any aggregate type. Also complex
4821 types which are not gimple registers can have subvars. */
4824 var_can_have_subvars (const_tree v)
4826 /* Volatile variables should never have subvars. */
4827 if (TREE_THIS_VOLATILE (v))
4830 /* Non decls or memory tags can never have subvars. */
4834 /* Aggregates without overlapping fields can have subvars. */
4835 if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
4841 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4842 the fields of TYPE onto fieldstack, recording their offsets along
4845 OFFSET is used to keep track of the offset in this entire
4846 structure, rather than just the immediately containing structure.
4847 Returns false if the caller is supposed to handle the field we
4851 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
4852 HOST_WIDE_INT offset)
4855 bool empty_p = true;
4857 if (TREE_CODE (type) != RECORD_TYPE)
4860 /* If the vector of fields is growing too big, bail out early.
4861 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4863 if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
4866 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
4867 if (TREE_CODE (field) == FIELD_DECL)
4870 HOST_WIDE_INT foff = bitpos_of_field (field);
4872 if (!var_can_have_subvars (field)
4873 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
4874 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
4876 else if (!push_fields_onto_fieldstack
4877 (TREE_TYPE (field), fieldstack, offset + foff)
4878 && (DECL_SIZE (field)
4879 && !integer_zerop (DECL_SIZE (field))))
4880 /* Empty structures may have actual size, like in C++. So
4881 see if we didn't push any subfields and the size is
4882 nonzero, push the field onto the stack. */
4887 fieldoff_s *pair = NULL;
4888 bool has_unknown_size = false;
4890 if (!VEC_empty (fieldoff_s, *fieldstack))
4891 pair = VEC_last (fieldoff_s, *fieldstack);
4893 if (!DECL_SIZE (field)
4894 || !host_integerp (DECL_SIZE (field), 1))
4895 has_unknown_size = true;
4897 /* If adjacent fields do not contain pointers merge them. */
4899 && !pair->may_have_pointers
4900 && !pair->has_unknown_size
4901 && !has_unknown_size
4902 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff
4903 && !could_have_pointers (field))
4905 pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
4909 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
4910 pair->offset = offset + foff;
4911 pair->has_unknown_size = has_unknown_size;
4912 if (!has_unknown_size)
4913 pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
4916 pair->may_have_pointers = could_have_pointers (field);
4917 pair->only_restrict_pointers
4918 = (!has_unknown_size
4919 && POINTER_TYPE_P (TREE_TYPE (field))
4920 && TYPE_RESTRICT (TREE_TYPE (field)));
4930 /* Count the number of arguments DECL has, and set IS_VARARGS to true
4931 if it is a varargs function. */
4934 count_num_arguments (tree decl, bool *is_varargs)
4936 unsigned int num = 0;
4939 /* Capture named arguments for K&R functions. They do not
4940 have a prototype and thus no TYPE_ARG_TYPES. */
4941 for (t = DECL_ARGUMENTS (decl); t; t = TREE_CHAIN (t))
4944 /* Check if the function has variadic arguments. */
4945 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); t; t = TREE_CHAIN (t))
4946 if (TREE_VALUE (t) == void_type_node)
4954 /* Creation function node for DECL, using NAME, and return the index
4955 of the variable we've created for the function. */
4958 create_function_info_for (tree decl, const char *name)
4960 struct function *fn = DECL_STRUCT_FUNCTION (decl);
4961 varinfo_t vi, prev_vi;
4964 bool is_varargs = false;
4965 unsigned int num_args = count_num_arguments (decl, &is_varargs);
4967 /* Create the variable info. */
4969 vi = new_var_info (decl, name);
4972 vi->fullsize = fi_parm_base + num_args;
4974 vi->may_have_pointers = false;
4977 insert_vi_for_tree (vi->decl, vi);
4981 /* Create a variable for things the function clobbers and one for
4982 things the function uses. */
4984 varinfo_t clobbervi, usevi;
4985 const char *newname;
4988 asprintf (&tempname, "%s.clobber", name);
4989 newname = ggc_strdup (tempname);
4992 clobbervi = new_var_info (NULL, newname);
4993 clobbervi->offset = fi_clobbers;
4994 clobbervi->size = 1;
4995 clobbervi->fullsize = vi->fullsize;
4996 clobbervi->is_full_var = true;
4997 clobbervi->is_global_var = false;
4998 gcc_assert (prev_vi->offset < clobbervi->offset);
4999 prev_vi->next = clobbervi;
5000 prev_vi = clobbervi;
5002 asprintf (&tempname, "%s.use", name);
5003 newname = ggc_strdup (tempname);
5006 usevi = new_var_info (NULL, newname);
5007 usevi->offset = fi_uses;
5009 usevi->fullsize = vi->fullsize;
5010 usevi->is_full_var = true;
5011 usevi->is_global_var = false;
5012 gcc_assert (prev_vi->offset < usevi->offset);
5013 prev_vi->next = usevi;
5017 /* And one for the static chain. */
5018 if (fn->static_chain_decl != NULL_TREE)
5021 const char *newname;
5024 asprintf (&tempname, "%s.chain", name);
5025 newname = ggc_strdup (tempname);
5028 chainvi = new_var_info (fn->static_chain_decl, newname);
5029 chainvi->offset = fi_static_chain;
5031 chainvi->fullsize = vi->fullsize;
5032 chainvi->is_full_var = true;
5033 chainvi->is_global_var = false;
5034 gcc_assert (prev_vi->offset < chainvi->offset);
5035 prev_vi->next = chainvi;
5037 insert_vi_for_tree (fn->static_chain_decl, chainvi);
5040 /* Create a variable for the return var. */
5041 if (DECL_RESULT (decl) != NULL
5042 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
5045 const char *newname;
5047 tree resultdecl = decl;
5049 if (DECL_RESULT (decl))
5050 resultdecl = DECL_RESULT (decl);
5052 asprintf (&tempname, "%s.result", name);
5053 newname = ggc_strdup (tempname);
5056 resultvi = new_var_info (resultdecl, newname);
5057 resultvi->offset = fi_result;
5059 resultvi->fullsize = vi->fullsize;
5060 resultvi->is_full_var = true;
5061 if (DECL_RESULT (decl))
5062 resultvi->may_have_pointers = could_have_pointers (DECL_RESULT (decl));
5063 gcc_assert (prev_vi->offset < resultvi->offset);
5064 prev_vi->next = resultvi;
5066 if (DECL_RESULT (decl))
5067 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
5070 /* Set up variables for each argument. */
5071 arg = DECL_ARGUMENTS (decl);
5072 for (i = 0; i < num_args; i++)
5075 const char *newname;
5077 tree argdecl = decl;
5082 asprintf (&tempname, "%s.arg%d", name, i);
5083 newname = ggc_strdup (tempname);
5086 argvi = new_var_info (argdecl, newname);
5087 argvi->offset = fi_parm_base + i;
5089 argvi->is_full_var = true;
5090 argvi->fullsize = vi->fullsize;
5092 argvi->may_have_pointers = could_have_pointers (arg);
5093 gcc_assert (prev_vi->offset < argvi->offset);
5094 prev_vi->next = argvi;
5098 insert_vi_for_tree (arg, argvi);
5099 arg = TREE_CHAIN (arg);
5103 /* Add one representative for all further args. */
5107 const char *newname;
5111 asprintf (&tempname, "%s.varargs", name);
5112 newname = ggc_strdup (tempname);
5115 /* We need sth that can be pointed to for va_start. */
5116 decl = create_tmp_var_raw (ptr_type_node, name);
5119 argvi = new_var_info (decl, newname);
5120 argvi->offset = fi_parm_base + num_args;
5122 argvi->is_full_var = true;
5123 argvi->is_heap_var = true;
5124 argvi->fullsize = vi->fullsize;
5125 gcc_assert (prev_vi->offset < argvi->offset);
5126 prev_vi->next = argvi;
5134 /* Return true if FIELDSTACK contains fields that overlap.
5135 FIELDSTACK is assumed to be sorted by offset. */
5138 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
5140 fieldoff_s *fo = NULL;
5142 HOST_WIDE_INT lastoffset = -1;
5144 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
5146 if (fo->offset == lastoffset)
5148 lastoffset = fo->offset;
5153 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5154 This will also create any varinfo structures necessary for fields
5158 create_variable_info_for_1 (tree decl, const char *name)
5160 varinfo_t vi, newvi;
5161 tree decl_type = TREE_TYPE (decl);
5162 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
5163 VEC (fieldoff_s,heap) *fieldstack = NULL;
5168 || !host_integerp (declsize, 1))
5170 vi = new_var_info (decl, name);
5174 vi->is_unknown_size_var = true;
5175 vi->is_full_var = true;
5176 vi->may_have_pointers = could_have_pointers (decl);
5180 /* Collect field information. */
5181 if (use_field_sensitive
5182 && var_can_have_subvars (decl)
5183 /* ??? Force us to not use subfields for global initializers
5184 in IPA mode. Else we'd have to parse arbitrary initializers. */
5186 && is_global_var (decl)
5187 && DECL_INITIAL (decl)))
5189 fieldoff_s *fo = NULL;
5190 bool notokay = false;
5193 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
5195 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
5196 if (fo->has_unknown_size
5203 /* We can't sort them if we have a field with a variable sized type,
5204 which will make notokay = true. In that case, we are going to return
5205 without creating varinfos for the fields anyway, so sorting them is a
5209 sort_fieldstack (fieldstack);
5210 /* Due to some C++ FE issues, like PR 22488, we might end up
5211 what appear to be overlapping fields even though they,
5212 in reality, do not overlap. Until the C++ FE is fixed,
5213 we will simply disable field-sensitivity for these cases. */
5214 notokay = check_for_overlaps (fieldstack);
5218 VEC_free (fieldoff_s, heap, fieldstack);
5221 /* If we didn't end up collecting sub-variables create a full
5222 variable for the decl. */
5223 if (VEC_length (fieldoff_s, fieldstack) <= 1
5224 || VEC_length (fieldoff_s, fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
5226 vi = new_var_info (decl, name);
5228 vi->may_have_pointers = could_have_pointers (decl);
5229 vi->fullsize = TREE_INT_CST_LOW (declsize);
5230 vi->size = vi->fullsize;
5231 vi->is_full_var = true;
5232 VEC_free (fieldoff_s, heap, fieldstack);
5236 vi = new_var_info (decl, name);
5237 vi->fullsize = TREE_INT_CST_LOW (declsize);
5238 for (i = 0, newvi = vi;
5239 VEC_iterate (fieldoff_s, fieldstack, i, fo);
5240 ++i, newvi = newvi->next)
5242 const char *newname = "NULL";
5247 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
5248 "+" HOST_WIDE_INT_PRINT_DEC, name, fo->offset, fo->size);
5249 newname = ggc_strdup (tempname);
5252 newvi->name = newname;
5253 newvi->offset = fo->offset;
5254 newvi->size = fo->size;
5255 newvi->fullsize = vi->fullsize;
5256 newvi->may_have_pointers = fo->may_have_pointers;
5257 newvi->only_restrict_pointers = fo->only_restrict_pointers;
5258 if (i + 1 < VEC_length (fieldoff_s, fieldstack))
5259 newvi->next = new_var_info (decl, name);
5262 VEC_free (fieldoff_s, heap, fieldstack);
5268 create_variable_info_for (tree decl, const char *name)
5270 varinfo_t vi = create_variable_info_for_1 (decl, name);
5271 unsigned int id = vi->id;
5273 insert_vi_for_tree (decl, vi);
5275 /* Create initial constraints for globals. */
5276 for (; vi; vi = vi->next)
5278 if (!vi->may_have_pointers
5279 || !vi->is_global_var)
5282 /* Mark global restrict qualified pointers. */
5283 if ((POINTER_TYPE_P (TREE_TYPE (decl))
5284 && TYPE_RESTRICT (TREE_TYPE (decl)))
5285 || vi->only_restrict_pointers)
5286 make_constraint_from_restrict (vi, "GLOBAL_RESTRICT");
5288 /* For escaped variables initialize them from nonlocal. */
5290 || DECL_EXTERNAL (decl) || TREE_PUBLIC (decl))
5291 make_copy_constraint (vi, nonlocal_id);
5293 /* If this is a global variable with an initializer and we are in
5294 IPA mode generate constraints for it. In non-IPA mode
5295 the initializer from nonlocal is all we need. */
5297 && DECL_INITIAL (decl))
5299 VEC (ce_s, heap) *rhsc = NULL;
5300 struct constraint_expr lhs, *rhsp;
5302 get_constraint_for (DECL_INITIAL (decl), &rhsc);
5306 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
5307 process_constraint (new_constraint (lhs, *rhsp));
5308 /* If this is a variable that escapes from the unit
5309 the initializer escapes as well. */
5310 if (DECL_EXTERNAL (decl) || TREE_PUBLIC (decl))
5312 lhs.var = escaped_id;
5315 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
5316 process_constraint (new_constraint (lhs, *rhsp));
5318 VEC_free (ce_s, heap, rhsc);
5325 /* Print out the points-to solution for VAR to FILE. */
5328 dump_solution_for_var (FILE *file, unsigned int var)
5330 varinfo_t vi = get_varinfo (var);
5334 /* Dump the solution for unified vars anyway, this avoids difficulties
5335 in scanning dumps in the testsuite. */
5336 fprintf (file, "%s = { ", vi->name);
5337 vi = get_varinfo (find (var));
5338 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
5339 fprintf (file, "%s ", get_varinfo (i)->name);
5340 fprintf (file, "}");
5342 /* But note when the variable was unified. */
5344 fprintf (file, " same as %s", vi->name);
5346 fprintf (file, "\n");
5349 /* Print the points-to solution for VAR to stdout. */
5352 debug_solution_for_var (unsigned int var)
5354 dump_solution_for_var (stdout, var);
5357 /* Create varinfo structures for all of the variables in the
5358 function for intraprocedural mode. */
5361 intra_create_variable_infos (void)
5365 /* For each incoming pointer argument arg, create the constraint ARG
5366 = NONLOCAL or a dummy variable if it is a restrict qualified
5367 passed-by-reference argument. */
5368 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
5372 if (!could_have_pointers (t))
5375 /* For restrict qualified pointers to objects passed by
5376 reference build a real representative for the pointed-to object. */
5377 if (DECL_BY_REFERENCE (t)
5378 && POINTER_TYPE_P (TREE_TYPE (t))
5379 && TYPE_RESTRICT (TREE_TYPE (t)))
5381 struct constraint_expr lhsc, rhsc;
5383 tree heapvar = heapvar_lookup (t, 0);
5384 if (heapvar == NULL_TREE)
5387 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
5389 DECL_EXTERNAL (heapvar) = 1;
5390 heapvar_insert (t, 0, heapvar);
5391 ann = get_var_ann (heapvar);
5392 ann->is_heapvar = 1;
5394 if (gimple_referenced_vars (cfun))
5395 add_referenced_var (heapvar);
5396 lhsc.var = get_vi_for_tree (t)->id;
5399 rhsc.var = (vi = get_vi_for_tree (heapvar))->id;
5400 rhsc.type = ADDRESSOF;
5402 process_constraint (new_constraint (lhsc, rhsc));
5403 vi->is_restrict_var = 1;
5407 for (p = get_vi_for_tree (t); p; p = p->next)
5409 if (p->may_have_pointers)
5410 make_constraint_from (p, nonlocal_id);
5411 if (p->only_restrict_pointers)
5412 make_constraint_from_restrict (p, "PARM_RESTRICT");
5414 if (POINTER_TYPE_P (TREE_TYPE (t))
5415 && TYPE_RESTRICT (TREE_TYPE (t)))
5416 make_constraint_from_restrict (get_vi_for_tree (t), "PARM_RESTRICT");
5419 /* Add a constraint for a result decl that is passed by reference. */
5420 if (DECL_RESULT (cfun->decl)
5421 && DECL_BY_REFERENCE (DECL_RESULT (cfun->decl)))
5423 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
5425 for (p = result_vi; p; p = p->next)
5426 make_constraint_from (p, nonlocal_id);
5429 /* Add a constraint for the incoming static chain parameter. */
5430 if (cfun->static_chain_decl != NULL_TREE)
5432 varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
5434 for (p = chain_vi; p; p = p->next)
5435 make_constraint_from (p, nonlocal_id);
5439 /* Structure used to put solution bitmaps in a hashtable so they can
5440 be shared among variables with the same points-to set. */
5442 typedef struct shared_bitmap_info
5446 } *shared_bitmap_info_t;
5447 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
5449 static htab_t shared_bitmap_table;
5451 /* Hash function for a shared_bitmap_info_t */
5454 shared_bitmap_hash (const void *p)
5456 const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
5457 return bi->hashcode;
5460 /* Equality function for two shared_bitmap_info_t's. */
5463 shared_bitmap_eq (const void *p1, const void *p2)
5465 const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
5466 const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
5467 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
5470 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
5471 existing instance if there is one, NULL otherwise. */
5474 shared_bitmap_lookup (bitmap pt_vars)
5477 struct shared_bitmap_info sbi;
5479 sbi.pt_vars = pt_vars;
5480 sbi.hashcode = bitmap_hash (pt_vars);
5482 slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
5483 sbi.hashcode, NO_INSERT);
5487 return ((shared_bitmap_info_t) *slot)->pt_vars;
5491 /* Add a bitmap to the shared bitmap hashtable. */
5494 shared_bitmap_add (bitmap pt_vars)
5497 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
5499 sbi->pt_vars = pt_vars;
5500 sbi->hashcode = bitmap_hash (pt_vars);
5502 slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
5503 sbi->hashcode, INSERT);
5504 gcc_assert (!*slot);
5505 *slot = (void *) sbi;
5509 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
5512 set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt)
5517 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
5519 varinfo_t vi = get_varinfo (i);
5521 /* The only artificial variables that are allowed in a may-alias
5522 set are heap variables. */
5523 if (vi->is_artificial_var && !vi->is_heap_var)
5526 if (TREE_CODE (vi->decl) == VAR_DECL
5527 || TREE_CODE (vi->decl) == PARM_DECL
5528 || TREE_CODE (vi->decl) == RESULT_DECL)
5530 /* If we are in IPA mode we will not recompute points-to
5531 sets after inlining so make sure they stay valid. */
5533 && !DECL_PT_UID_SET_P (vi->decl))
5534 SET_DECL_PT_UID (vi->decl, DECL_UID (vi->decl));
5536 /* Add the decl to the points-to set. Note that the points-to
5537 set contains global variables. */
5538 bitmap_set_bit (into, DECL_PT_UID (vi->decl));
5539 if (vi->is_global_var)
5540 pt->vars_contains_global = true;
5546 /* Compute the points-to solution *PT for the variable VI. */
5549 find_what_var_points_to (varinfo_t orig_vi, struct pt_solution *pt)
5553 bitmap finished_solution;
5557 memset (pt, 0, sizeof (struct pt_solution));
5559 /* This variable may have been collapsed, let's get the real
5561 vi = get_varinfo (find (orig_vi->id));
5563 /* Translate artificial variables into SSA_NAME_PTR_INFO
5565 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
5567 varinfo_t vi = get_varinfo (i);
5569 if (vi->is_artificial_var)
5571 if (vi->id == nothing_id)
5573 else if (vi->id == escaped_id)
5576 pt->ipa_escaped = 1;
5580 else if (vi->id == nonlocal_id)
5582 else if (vi->is_heap_var)
5583 /* We represent heapvars in the points-to set properly. */
5585 else if (vi->id == readonly_id)
5588 else if (vi->id == anything_id
5589 || vi->id == integer_id)
5592 if (vi->is_restrict_var)
5593 pt->vars_contains_restrict = true;
5596 /* Instead of doing extra work, simply do not create
5597 elaborate points-to information for pt_anything pointers. */
5599 && (orig_vi->is_artificial_var
5600 || !pt->vars_contains_restrict))
5603 /* Share the final set of variables when possible. */
5604 finished_solution = BITMAP_GGC_ALLOC ();
5605 stats.points_to_sets_created++;
5607 set_uids_in_ptset (finished_solution, vi->solution, pt);
5608 result = shared_bitmap_lookup (finished_solution);
5611 shared_bitmap_add (finished_solution);
5612 pt->vars = finished_solution;
5617 bitmap_clear (finished_solution);
5621 /* Given a pointer variable P, fill in its points-to set. */
5624 find_what_p_points_to (tree p)
5626 struct ptr_info_def *pi;
5630 /* For parameters, get at the points-to set for the actual parm
5632 if (TREE_CODE (p) == SSA_NAME
5633 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
5634 && SSA_NAME_IS_DEFAULT_DEF (p))
5635 lookup_p = SSA_NAME_VAR (p);
5637 vi = lookup_vi_for_tree (lookup_p);
5641 pi = get_ptr_info (p);
5642 find_what_var_points_to (vi, &pi->pt);
5646 /* Query statistics for points-to solutions. */
5649 unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
5650 unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
5651 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
5652 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
5656 dump_pta_stats (FILE *s)
5658 fprintf (s, "\nPTA query stats:\n");
5659 fprintf (s, " pt_solution_includes: "
5660 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
5661 HOST_WIDE_INT_PRINT_DEC" queries\n",
5662 pta_stats.pt_solution_includes_no_alias,
5663 pta_stats.pt_solution_includes_no_alias
5664 + pta_stats.pt_solution_includes_may_alias);
5665 fprintf (s, " pt_solutions_intersect: "
5666 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
5667 HOST_WIDE_INT_PRINT_DEC" queries\n",
5668 pta_stats.pt_solutions_intersect_no_alias,
5669 pta_stats.pt_solutions_intersect_no_alias
5670 + pta_stats.pt_solutions_intersect_may_alias);
5674 /* Reset the points-to solution *PT to a conservative default
5675 (point to anything). */
5678 pt_solution_reset (struct pt_solution *pt)
5680 memset (pt, 0, sizeof (struct pt_solution));
5681 pt->anything = true;
5684 /* Set the points-to solution *PT to point only to the variables
5685 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
5686 global variables and VARS_CONTAINS_RESTRICT specifies whether
5687 it contains restrict tag variables. */
5690 pt_solution_set (struct pt_solution *pt, bitmap vars,
5691 bool vars_contains_global, bool vars_contains_restrict)
5693 memset (pt, 0, sizeof (struct pt_solution));
5695 pt->vars_contains_global = vars_contains_global;
5696 pt->vars_contains_restrict = vars_contains_restrict;
5699 /* Computes the union of the points-to solutions *DEST and *SRC and
5700 stores the result in *DEST. This changes the points-to bitmap
5701 of *DEST and thus may not be used if that might be shared.
5702 The points-to bitmap of *SRC and *DEST will not be shared after
5703 this function if they were not before. */
5706 pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src)
5708 dest->anything |= src->anything;
5711 pt_solution_reset (dest);
5715 dest->nonlocal |= src->nonlocal;
5716 dest->escaped |= src->escaped;
5717 dest->ipa_escaped |= src->ipa_escaped;
5718 dest->null |= src->null;
5719 dest->vars_contains_global |= src->vars_contains_global;
5720 dest->vars_contains_restrict |= src->vars_contains_restrict;
5725 dest->vars = BITMAP_GGC_ALLOC ();
5726 bitmap_ior_into (dest->vars, src->vars);
5729 /* Return true if the points-to solution *PT is empty. */
5732 pt_solution_empty_p (struct pt_solution *pt)
5739 && !bitmap_empty_p (pt->vars))
5742 /* If the solution includes ESCAPED, check if that is empty. */
5744 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
5747 /* If the solution includes ESCAPED, check if that is empty. */
5749 && !pt_solution_empty_p (&ipa_escaped_pt))
5755 /* Return true if the points-to solution *PT includes global memory. */
5758 pt_solution_includes_global (struct pt_solution *pt)
5762 || pt->vars_contains_global)
5766 return pt_solution_includes_global (&cfun->gimple_df->escaped);
5768 if (pt->ipa_escaped)
5769 return pt_solution_includes_global (&ipa_escaped_pt);
5771 /* ??? This predicate is not correct for the IPA-PTA solution
5772 as we do not properly distinguish between unit escape points
5773 and global variables. */
5774 if (cfun->gimple_df->ipa_pta)
5780 /* Return true if the points-to solution *PT includes the variable
5781 declaration DECL. */
5784 pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
5790 && is_global_var (decl))
5794 && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
5797 /* If the solution includes ESCAPED, check it. */
5799 && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
5802 /* If the solution includes ESCAPED, check it. */
5804 && pt_solution_includes_1 (&ipa_escaped_pt, decl))
5811 pt_solution_includes (struct pt_solution *pt, const_tree decl)
5813 bool res = pt_solution_includes_1 (pt, decl);
5815 ++pta_stats.pt_solution_includes_may_alias;
5817 ++pta_stats.pt_solution_includes_no_alias;
5821 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
5825 pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
5827 if (pt1->anything || pt2->anything)
5830 /* If either points to unknown global memory and the other points to
5831 any global memory they alias. */
5834 || pt2->vars_contains_global))
5836 && pt1->vars_contains_global))
5839 /* Check the escaped solution if required. */
5840 if ((pt1->escaped || pt2->escaped)
5841 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
5843 /* If both point to escaped memory and that solution
5844 is not empty they alias. */
5845 if (pt1->escaped && pt2->escaped)
5848 /* If either points to escaped memory see if the escaped solution
5849 intersects with the other. */
5851 && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt2))
5853 && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt1)))
5857 /* Check the escaped solution if required.
5858 ??? Do we need to check the local against the IPA escaped sets? */
5859 if ((pt1->ipa_escaped || pt2->ipa_escaped)
5860 && !pt_solution_empty_p (&ipa_escaped_pt))
5862 /* If both point to escaped memory and that solution
5863 is not empty they alias. */
5864 if (pt1->ipa_escaped && pt2->ipa_escaped)
5867 /* If either points to escaped memory see if the escaped solution
5868 intersects with the other. */
5869 if ((pt1->ipa_escaped
5870 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
5871 || (pt2->ipa_escaped
5872 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
5876 /* Now both pointers alias if their points-to solution intersects. */
5879 && bitmap_intersect_p (pt1->vars, pt2->vars));
5883 pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
5885 bool res = pt_solutions_intersect_1 (pt1, pt2);
5887 ++pta_stats.pt_solutions_intersect_may_alias;
5889 ++pta_stats.pt_solutions_intersect_no_alias;
5893 /* Return true if both points-to solutions PT1 and PT2 for two restrict
5894 qualified pointers are possibly based on the same pointer. */
5897 pt_solutions_same_restrict_base (struct pt_solution *pt1,
5898 struct pt_solution *pt2)
5900 /* If we deal with points-to solutions of two restrict qualified
5901 pointers solely rely on the pointed-to variable bitmap intersection.
5902 For two pointers that are based on each other the bitmaps will
5904 if (pt1->vars_contains_restrict
5905 && pt2->vars_contains_restrict)
5907 gcc_assert (pt1->vars && pt2->vars);
5908 return bitmap_intersect_p (pt1->vars, pt2->vars);
5915 /* Dump points-to information to OUTFILE. */
5918 dump_sa_points_to_info (FILE *outfile)
5922 fprintf (outfile, "\nPoints-to sets\n\n");
5924 if (dump_flags & TDF_STATS)
5926 fprintf (outfile, "Stats:\n");
5927 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
5928 fprintf (outfile, "Non-pointer vars: %d\n",
5929 stats.nonpointer_vars);
5930 fprintf (outfile, "Statically unified vars: %d\n",
5931 stats.unified_vars_static);
5932 fprintf (outfile, "Dynamically unified vars: %d\n",
5933 stats.unified_vars_dynamic);
5934 fprintf (outfile, "Iterations: %d\n", stats.iterations);
5935 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
5936 fprintf (outfile, "Number of implicit edges: %d\n",
5937 stats.num_implicit_edges);
5940 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
5942 varinfo_t vi = get_varinfo (i);
5943 if (!vi->may_have_pointers)
5945 dump_solution_for_var (outfile, i);
5950 /* Debug points-to information to stderr. */
5953 debug_sa_points_to_info (void)
5955 dump_sa_points_to_info (stderr);
5959 /* Initialize the always-existing constraint variables for NULL
5960 ANYTHING, READONLY, and INTEGER */
5963 init_base_vars (void)
5965 struct constraint_expr lhs, rhs;
5966 varinfo_t var_anything;
5967 varinfo_t var_nothing;
5968 varinfo_t var_readonly;
5969 varinfo_t var_escaped;
5970 varinfo_t var_nonlocal;
5971 varinfo_t var_storedanything;
5972 varinfo_t var_integer;
5974 /* Create the NULL variable, used to represent that a variable points
5976 var_nothing = new_var_info (NULL_TREE, "NULL");
5977 gcc_assert (var_nothing->id == nothing_id);
5978 var_nothing->is_artificial_var = 1;
5979 var_nothing->offset = 0;
5980 var_nothing->size = ~0;
5981 var_nothing->fullsize = ~0;
5982 var_nothing->is_special_var = 1;
5983 var_nothing->may_have_pointers = 0;
5984 var_nothing->is_global_var = 0;
5986 /* Create the ANYTHING variable, used to represent that a variable
5987 points to some unknown piece of memory. */
5988 var_anything = new_var_info (NULL_TREE, "ANYTHING");
5989 gcc_assert (var_anything->id == anything_id);
5990 var_anything->is_artificial_var = 1;
5991 var_anything->size = ~0;
5992 var_anything->offset = 0;
5993 var_anything->next = NULL;
5994 var_anything->fullsize = ~0;
5995 var_anything->is_special_var = 1;
5997 /* Anything points to anything. This makes deref constraints just
5998 work in the presence of linked list and other p = *p type loops,
5999 by saying that *ANYTHING = ANYTHING. */
6001 lhs.var = anything_id;
6003 rhs.type = ADDRESSOF;
6004 rhs.var = anything_id;
6007 /* This specifically does not use process_constraint because
6008 process_constraint ignores all anything = anything constraints, since all
6009 but this one are redundant. */
6010 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
6012 /* Create the READONLY variable, used to represent that a variable
6013 points to readonly memory. */
6014 var_readonly = new_var_info (NULL_TREE, "READONLY");
6015 gcc_assert (var_readonly->id == readonly_id);
6016 var_readonly->is_artificial_var = 1;
6017 var_readonly->offset = 0;
6018 var_readonly->size = ~0;
6019 var_readonly->fullsize = ~0;
6020 var_readonly->next = NULL;
6021 var_readonly->is_special_var = 1;
6023 /* readonly memory points to anything, in order to make deref
6024 easier. In reality, it points to anything the particular
6025 readonly variable can point to, but we don't track this
6028 lhs.var = readonly_id;
6030 rhs.type = ADDRESSOF;
6031 rhs.var = readonly_id; /* FIXME */
6033 process_constraint (new_constraint (lhs, rhs));
6035 /* Create the ESCAPED variable, used to represent the set of escaped
6037 var_escaped = new_var_info (NULL_TREE, "ESCAPED");
6038 gcc_assert (var_escaped->id == escaped_id);
6039 var_escaped->is_artificial_var = 1;
6040 var_escaped->offset = 0;
6041 var_escaped->size = ~0;
6042 var_escaped->fullsize = ~0;
6043 var_escaped->is_special_var = 0;
6045 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6047 var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL");
6048 gcc_assert (var_nonlocal->id == nonlocal_id);
6049 var_nonlocal->is_artificial_var = 1;
6050 var_nonlocal->offset = 0;
6051 var_nonlocal->size = ~0;
6052 var_nonlocal->fullsize = ~0;
6053 var_nonlocal->is_special_var = 1;
6055 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6057 lhs.var = escaped_id;
6060 rhs.var = escaped_id;
6062 process_constraint (new_constraint (lhs, rhs));
6064 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6065 whole variable escapes. */
6067 lhs.var = escaped_id;
6070 rhs.var = escaped_id;
6071 rhs.offset = UNKNOWN_OFFSET;
6072 process_constraint (new_constraint (lhs, rhs));
6074 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6075 everything pointed to by escaped points to what global memory can
6078 lhs.var = escaped_id;
6081 rhs.var = nonlocal_id;
6083 process_constraint (new_constraint (lhs, rhs));
6085 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6086 global memory may point to global memory and escaped memory. */
6088 lhs.var = nonlocal_id;
6090 rhs.type = ADDRESSOF;
6091 rhs.var = nonlocal_id;
6093 process_constraint (new_constraint (lhs, rhs));
6094 rhs.type = ADDRESSOF;
6095 rhs.var = escaped_id;
6097 process_constraint (new_constraint (lhs, rhs));
6099 /* Create the STOREDANYTHING variable, used to represent the set of
6100 variables stored to *ANYTHING. */
6101 var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING");
6102 gcc_assert (var_storedanything->id == storedanything_id);
6103 var_storedanything->is_artificial_var = 1;
6104 var_storedanything->offset = 0;
6105 var_storedanything->size = ~0;
6106 var_storedanything->fullsize = ~0;
6107 var_storedanything->is_special_var = 0;
6109 /* Create the INTEGER variable, used to represent that a variable points
6110 to what an INTEGER "points to". */
6111 var_integer = new_var_info (NULL_TREE, "INTEGER");
6112 gcc_assert (var_integer->id == integer_id);
6113 var_integer->is_artificial_var = 1;
6114 var_integer->size = ~0;
6115 var_integer->fullsize = ~0;
6116 var_integer->offset = 0;
6117 var_integer->next = NULL;
6118 var_integer->is_special_var = 1;
6120 /* INTEGER = ANYTHING, because we don't know where a dereference of
6121 a random integer will point to. */
6123 lhs.var = integer_id;
6125 rhs.type = ADDRESSOF;
6126 rhs.var = anything_id;
6128 process_constraint (new_constraint (lhs, rhs));
6131 /* Initialize things necessary to perform PTA */
6134 init_alias_vars (void)
6136 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
6138 bitmap_obstack_initialize (&pta_obstack);
6139 bitmap_obstack_initialize (&oldpta_obstack);
6140 bitmap_obstack_initialize (&predbitmap_obstack);
6142 constraint_pool = create_alloc_pool ("Constraint pool",
6143 sizeof (struct constraint), 30);
6144 variable_info_pool = create_alloc_pool ("Variable info pool",
6145 sizeof (struct variable_info), 30);
6146 constraints = VEC_alloc (constraint_t, heap, 8);
6147 varmap = VEC_alloc (varinfo_t, heap, 8);
6148 vi_for_tree = pointer_map_create ();
6149 call_stmt_vars = pointer_map_create ();
6151 memset (&stats, 0, sizeof (stats));
6152 shared_bitmap_table = htab_create (511, shared_bitmap_hash,
6153 shared_bitmap_eq, free);
6157 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
6158 predecessor edges. */
6161 remove_preds_and_fake_succs (constraint_graph_t graph)
6165 /* Clear the implicit ref and address nodes from the successor
6167 for (i = 0; i < FIRST_REF_NODE; i++)
6169 if (graph->succs[i])
6170 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
6171 FIRST_REF_NODE * 2);
6174 /* Free the successor list for the non-ref nodes. */
6175 for (i = FIRST_REF_NODE; i < graph->size; i++)
6177 if (graph->succs[i])
6178 BITMAP_FREE (graph->succs[i]);
6181 /* Now reallocate the size of the successor list as, and blow away
6182 the predecessor bitmaps. */
6183 graph->size = VEC_length (varinfo_t, varmap);
6184 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
6186 free (graph->implicit_preds);
6187 graph->implicit_preds = NULL;
6188 free (graph->preds);
6189 graph->preds = NULL;
6190 bitmap_obstack_release (&predbitmap_obstack);
6193 /* Initialize the heapvar for statement mapping. */
6196 init_alias_heapvars (void)
6198 if (!heapvar_for_stmt)
6199 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, heapvar_map_eq,
6203 /* Delete the heapvar for statement mapping. */
6206 delete_alias_heapvars (void)
6208 if (heapvar_for_stmt)
6209 htab_delete (heapvar_for_stmt);
6210 heapvar_for_stmt = NULL;
6213 /* Solve the constraint set. */
6216 solve_constraints (void)
6218 struct scc_info *si;
6222 "\nCollapsing static cycles and doing variable "
6225 init_graph (VEC_length (varinfo_t, varmap) * 2);
6228 fprintf (dump_file, "Building predecessor graph\n");
6229 build_pred_graph ();
6232 fprintf (dump_file, "Detecting pointer and location "
6234 si = perform_var_substitution (graph);
6237 fprintf (dump_file, "Rewriting constraints and unifying "
6239 rewrite_constraints (graph, si);
6241 build_succ_graph ();
6242 free_var_substitution_info (si);
6244 if (dump_file && (dump_flags & TDF_GRAPH))
6245 dump_constraint_graph (dump_file);
6247 move_complex_constraints (graph);
6250 fprintf (dump_file, "Uniting pointer but not location equivalent "
6252 unite_pointer_equivalences (graph);
6255 fprintf (dump_file, "Finding indirect cycles\n");
6256 find_indirect_cycles (graph);
6258 /* Implicit nodes and predecessors are no longer necessary at this
6260 remove_preds_and_fake_succs (graph);
6263 fprintf (dump_file, "Solving graph\n");
6265 solve_graph (graph);
6268 dump_sa_points_to_info (dump_file);
6271 /* Create points-to sets for the current function. See the comments
6272 at the start of the file for an algorithmic overview. */
6275 compute_points_to_sets (void)
6281 timevar_push (TV_TREE_PTA);
6284 init_alias_heapvars ();
6286 intra_create_variable_infos ();
6288 /* Now walk all statements and build the constraint set. */
6291 gimple_stmt_iterator gsi;
6293 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6295 gimple phi = gsi_stmt (gsi);
6297 if (is_gimple_reg (gimple_phi_result (phi)))
6298 find_func_aliases (phi);
6301 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6303 gimple stmt = gsi_stmt (gsi);
6305 find_func_aliases (stmt);
6311 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
6312 dump_constraints (dump_file, 0);
6315 /* From the constraints compute the points-to sets. */
6316 solve_constraints ();
6318 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
6319 find_what_var_points_to (get_varinfo (escaped_id),
6320 &cfun->gimple_df->escaped);
6322 /* Make sure the ESCAPED solution (which is used as placeholder in
6323 other solutions) does not reference itself. This simplifies
6324 points-to solution queries. */
6325 cfun->gimple_df->escaped.escaped = 0;
6327 /* Mark escaped HEAP variables as global. */
6328 for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); ++i)
6330 && !vi->is_restrict_var
6331 && !vi->is_global_var)
6332 DECL_EXTERNAL (vi->decl) = vi->is_global_var
6333 = pt_solution_includes (&cfun->gimple_df->escaped, vi->decl);
6335 /* Compute the points-to sets for pointer SSA_NAMEs. */
6336 for (i = 0; i < num_ssa_names; ++i)
6338 tree ptr = ssa_name (i);
6340 && POINTER_TYPE_P (TREE_TYPE (ptr)))
6341 find_what_p_points_to (ptr);
6344 /* Compute the call-used/clobbered sets. */
6347 gimple_stmt_iterator gsi;
6349 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6351 gimple stmt = gsi_stmt (gsi);
6352 struct pt_solution *pt;
6353 if (!is_gimple_call (stmt))
6356 pt = gimple_call_use_set (stmt);
6357 if (gimple_call_flags (stmt) & ECF_CONST)
6358 memset (pt, 0, sizeof (struct pt_solution));
6359 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
6361 find_what_var_points_to (vi, pt);
6362 /* Escaped (and thus nonlocal) variables are always
6363 implicitly used by calls. */
6364 /* ??? ESCAPED can be empty even though NONLOCAL
6371 /* If there is nothing special about this call then
6372 we have made everything that is used also escape. */
6373 *pt = cfun->gimple_df->escaped;
6377 pt = gimple_call_clobber_set (stmt);
6378 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
6379 memset (pt, 0, sizeof (struct pt_solution));
6380 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
6382 find_what_var_points_to (vi, pt);
6383 /* Escaped (and thus nonlocal) variables are always
6384 implicitly clobbered by calls. */
6385 /* ??? ESCAPED can be empty even though NONLOCAL
6392 /* If there is nothing special about this call then
6393 we have made everything that is used also escape. */
6394 *pt = cfun->gimple_df->escaped;
6400 timevar_pop (TV_TREE_PTA);
6404 /* Delete created points-to sets. */
6407 delete_points_to_sets (void)
6411 htab_delete (shared_bitmap_table);
6412 if (dump_file && (dump_flags & TDF_STATS))
6413 fprintf (dump_file, "Points to sets created:%d\n",
6414 stats.points_to_sets_created);
6416 pointer_map_destroy (vi_for_tree);
6417 pointer_map_destroy (call_stmt_vars);
6418 bitmap_obstack_release (&pta_obstack);
6419 VEC_free (constraint_t, heap, constraints);
6421 for (i = 0; i < graph->size; i++)
6422 VEC_free (constraint_t, heap, graph->complex[i]);
6423 free (graph->complex);
6426 free (graph->succs);
6428 free (graph->pe_rep);
6429 free (graph->indirect_cycles);
6432 VEC_free (varinfo_t, heap, varmap);
6433 free_alloc_pool (variable_info_pool);
6434 free_alloc_pool (constraint_pool);
6438 /* Compute points-to information for every SSA_NAME pointer in the
6439 current function and compute the transitive closure of escaped
6440 variables to re-initialize the call-clobber states of local variables. */
6443 compute_may_aliases (void)
6445 if (cfun->gimple_df->ipa_pta)
6449 fprintf (dump_file, "\nNot re-computing points-to information "
6450 "because IPA points-to information is available.\n\n");
6452 /* But still dump what we have remaining it. */
6453 dump_alias_info (dump_file);
6455 if (dump_flags & TDF_DETAILS)
6456 dump_referenced_vars (dump_file);
6462 /* For each pointer P_i, determine the sets of variables that P_i may
6463 point-to. Compute the reachability set of escaped and call-used
6465 compute_points_to_sets ();
6467 /* Debugging dumps. */
6470 dump_alias_info (dump_file);
6472 if (dump_flags & TDF_DETAILS)
6473 dump_referenced_vars (dump_file);
6476 /* Deallocate memory used by aliasing data structures and the internal
6477 points-to solution. */
6478 delete_points_to_sets ();
6480 gcc_assert (!need_ssa_update_p (cfun));
6486 gate_tree_pta (void)
6488 return flag_tree_pta;
6491 /* A dummy pass to cause points-to information to be computed via
6492 TODO_rebuild_alias. */
6494 struct gimple_opt_pass pass_build_alias =
6499 gate_tree_pta, /* gate */
6503 0, /* static_pass_number */
6504 TV_NONE, /* tv_id */
6505 PROP_cfg | PROP_ssa, /* properties_required */
6506 0, /* properties_provided */
6507 0, /* properties_destroyed */
6508 0, /* todo_flags_start */
6509 TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */
6513 /* A dummy pass to cause points-to information to be computed via
6514 TODO_rebuild_alias. */
6516 struct gimple_opt_pass pass_build_ealias =
6520 "ealias", /* name */
6521 gate_tree_pta, /* gate */
6525 0, /* static_pass_number */
6526 TV_NONE, /* tv_id */
6527 PROP_cfg | PROP_ssa, /* properties_required */
6528 0, /* properties_provided */
6529 0, /* properties_destroyed */
6530 0, /* todo_flags_start */
6531 TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */
6536 /* Return true if we should execute IPA PTA. */
6542 /* Don't bother doing anything if the program has errors. */
6543 && !(errorcount || sorrycount));
6546 /* IPA PTA solutions for ESCAPED. */
6547 struct pt_solution ipa_escaped_pt
6548 = { true, false, false, false, false, false, false, NULL };
6550 /* Execute the driver for IPA PTA. */
6552 ipa_pta_execute (void)
6554 struct cgraph_node *node;
6555 struct varpool_node *var;
6560 init_alias_heapvars ();
6563 /* Build the constraints. */
6564 for (node = cgraph_nodes; node; node = node->next)
6566 /* Nodes without a body are not interesting. Especially do not
6567 visit clones at this point for now - we get duplicate decls
6568 there for inline clones at least. */
6569 if (!gimple_has_body_p (node->decl)
6573 create_function_info_for (node->decl,
6574 cgraph_node_name (node));
6577 /* Create constraints for global variables and their initializers. */
6578 for (var = varpool_nodes; var; var = var->next)
6579 get_vi_for_tree (var->decl);
6584 "Generating constraints for global initializers\n\n");
6585 dump_constraints (dump_file, 0);
6586 fprintf (dump_file, "\n");
6588 from = VEC_length (constraint_t, constraints);
6590 for (node = cgraph_nodes; node; node = node->next)
6592 struct function *func;
6596 /* Nodes without a body are not interesting. */
6597 if (!gimple_has_body_p (node->decl)
6603 "Generating constraints for %s\n",
6604 cgraph_node_name (node));
6606 func = DECL_STRUCT_FUNCTION (node->decl);
6607 old_func_decl = current_function_decl;
6609 current_function_decl = node->decl;
6611 /* For externally visible functions use local constraints for
6612 their arguments. For local functions we see all callers
6613 and thus do not need initial constraints for parameters. */
6614 if (node->local.externally_visible)
6615 intra_create_variable_infos ();
6617 /* Build constriants for the function body. */
6618 FOR_EACH_BB_FN (bb, func)
6620 gimple_stmt_iterator gsi;
6622 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
6625 gimple phi = gsi_stmt (gsi);
6627 if (is_gimple_reg (gimple_phi_result (phi)))
6628 find_func_aliases (phi);
6631 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6633 gimple stmt = gsi_stmt (gsi);
6635 find_func_aliases (stmt);
6636 find_func_clobbers (stmt);
6640 current_function_decl = old_func_decl;
6645 fprintf (dump_file, "\n");
6646 dump_constraints (dump_file, from);
6647 fprintf (dump_file, "\n");
6649 from = VEC_length (constraint_t, constraints);
6652 /* From the constraints compute the points-to sets. */
6653 solve_constraints ();
6655 /* Compute the global points-to sets for ESCAPED.
6656 ??? Note that the computed escape set is not correct
6657 for the whole unit as we fail to consider graph edges to
6658 externally visible functions. */
6659 find_what_var_points_to (get_varinfo (escaped_id), &ipa_escaped_pt);
6661 /* Make sure the ESCAPED solution (which is used as placeholder in
6662 other solutions) does not reference itself. This simplifies
6663 points-to solution queries. */
6664 ipa_escaped_pt.ipa_escaped = 0;
6666 /* Assign the points-to sets to the SSA names in the unit. */
6667 for (node = cgraph_nodes; node; node = node->next)
6670 struct function *fn;
6674 struct pt_solution uses, clobbers;
6675 struct cgraph_edge *e;
6677 /* Nodes without a body are not interesting. */
6678 if (!gimple_has_body_p (node->decl)
6682 fn = DECL_STRUCT_FUNCTION (node->decl);
6684 /* Compute the points-to sets for pointer SSA_NAMEs. */
6685 for (i = 0; VEC_iterate (tree, fn->gimple_df->ssa_names, i, ptr); ++i)
6688 && POINTER_TYPE_P (TREE_TYPE (ptr)))
6689 find_what_p_points_to (ptr);
6692 /* Compute the call-use and call-clobber sets for all direct calls. */
6693 fi = lookup_vi_for_tree (node->decl);
6694 gcc_assert (fi->is_fn_info);
6695 find_what_var_points_to (first_vi_for_offset (fi, fi_clobbers),
6697 find_what_var_points_to (first_vi_for_offset (fi, fi_uses), &uses);
6698 for (e = node->callers; e; e = e->next_caller)
6703 *gimple_call_clobber_set (e->call_stmt) = clobbers;
6704 *gimple_call_use_set (e->call_stmt) = uses;
6707 /* Compute the call-use and call-clobber sets for indirect calls
6708 and calls to external functions. */
6709 FOR_EACH_BB_FN (bb, fn)
6711 gimple_stmt_iterator gsi;
6713 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6715 gimple stmt = gsi_stmt (gsi);
6716 struct pt_solution *pt;
6720 if (!is_gimple_call (stmt))
6723 /* Handle direct calls to external functions. */
6724 decl = gimple_call_fndecl (stmt);
6726 && (!(fi = lookup_vi_for_tree (decl))
6727 || !fi->is_fn_info))
6729 pt = gimple_call_use_set (stmt);
6730 if (gimple_call_flags (stmt) & ECF_CONST)
6731 memset (pt, 0, sizeof (struct pt_solution));
6732 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
6734 find_what_var_points_to (vi, pt);
6735 /* Escaped (and thus nonlocal) variables are always
6736 implicitly used by calls. */
6737 /* ??? ESCAPED can be empty even though NONLOCAL
6740 pt->ipa_escaped = 1;
6744 /* If there is nothing special about this call then
6745 we have made everything that is used also escape. */
6746 *pt = ipa_escaped_pt;
6750 pt = gimple_call_clobber_set (stmt);
6751 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
6752 memset (pt, 0, sizeof (struct pt_solution));
6753 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
6755 find_what_var_points_to (vi, pt);
6756 /* Escaped (and thus nonlocal) variables are always
6757 implicitly clobbered by calls. */
6758 /* ??? ESCAPED can be empty even though NONLOCAL
6761 pt->ipa_escaped = 1;
6765 /* If there is nothing special about this call then
6766 we have made everything that is used also escape. */
6767 *pt = ipa_escaped_pt;
6772 /* Handle indirect calls. */
6774 && (fi = get_fi_for_callee (stmt)))
6776 /* We need to accumulate all clobbers/uses of all possible
6778 fi = get_varinfo (find (fi->id));
6779 /* If we cannot constrain the set of functions we'll end up
6780 calling we end up using/clobbering everything. */
6781 if (bitmap_bit_p (fi->solution, anything_id)
6782 || bitmap_bit_p (fi->solution, nonlocal_id)
6783 || bitmap_bit_p (fi->solution, escaped_id))
6785 pt_solution_reset (gimple_call_clobber_set (stmt));
6786 pt_solution_reset (gimple_call_use_set (stmt));
6792 struct pt_solution *uses, *clobbers;
6794 uses = gimple_call_use_set (stmt);
6795 clobbers = gimple_call_clobber_set (stmt);
6796 memset (uses, 0, sizeof (struct pt_solution));
6797 memset (clobbers, 0, sizeof (struct pt_solution));
6798 EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi)
6800 struct pt_solution sol;
6802 vi = get_varinfo (i);
6803 if (!vi->is_fn_info)
6805 /* ??? We could be more precise here? */
6807 uses->ipa_escaped = 1;
6808 clobbers->nonlocal = 1;
6809 clobbers->ipa_escaped = 1;
6813 if (!uses->anything)
6815 find_what_var_points_to
6816 (first_vi_for_offset (vi, fi_uses), &sol);
6817 pt_solution_ior_into (uses, &sol);
6819 if (!clobbers->anything)
6821 find_what_var_points_to
6822 (first_vi_for_offset (vi, fi_clobbers), &sol);
6823 pt_solution_ior_into (clobbers, &sol);
6831 fn->gimple_df->ipa_pta = true;
6834 delete_points_to_sets ();
6841 struct simple_ipa_opt_pass pass_ipa_pta =
6846 gate_ipa_pta, /* gate */
6847 ipa_pta_execute, /* execute */
6850 0, /* static_pass_number */
6851 TV_IPA_PTA, /* tv_id */
6852 0, /* properties_required */
6853 0, /* properties_provided */
6854 0, /* properties_destroyed */
6855 0, /* todo_flags_start */
6856 TODO_update_ssa /* todo_flags_finish */
6861 #include "gt-tree-ssa-structalias.h"