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"
39 #include "diagnostic.h"
45 #include "tree-pass.h"
47 #include "alloc-pool.h"
48 #include "splay-tree.h"
52 #include "pointer-set.h"
54 /* The idea behind this analyzer is to generate set constraints from the
55 program, then solve the resulting constraints in order to generate the
58 Set constraints are a way of modeling program analysis problems that
59 involve sets. They consist of an inclusion constraint language,
60 describing the variables (each variable is a set) and operations that
61 are involved on the variables, and a set of rules that derive facts
62 from these operations. To solve a system of set constraints, you derive
63 all possible facts under the rules, which gives you the correct sets
66 See "Efficient Field-sensitive pointer analysis for C" by "David
67 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
68 http://citeseer.ist.psu.edu/pearce04efficient.html
70 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
71 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
72 http://citeseer.ist.psu.edu/heintze01ultrafast.html
74 There are three types of real constraint expressions, DEREF,
75 ADDRESSOF, and SCALAR. Each constraint expression consists
76 of a constraint type, a variable, and an offset.
78 SCALAR is a constraint expression type used to represent x, whether
79 it appears on the LHS or the RHS of a statement.
80 DEREF is a constraint expression type used to represent *x, whether
81 it appears on the LHS or the RHS of a statement.
82 ADDRESSOF is a constraint expression used to represent &x, whether
83 it appears on the LHS or the RHS of a statement.
85 Each pointer variable in the program is assigned an integer id, and
86 each field of a structure variable is assigned an integer id as well.
88 Structure variables are linked to their list of fields through a "next
89 field" in each variable that points to the next field in offset
91 Each variable for a structure field has
93 1. "size", that tells the size in bits of that field.
94 2. "fullsize, that tells the size in bits of the entire structure.
95 3. "offset", that tells the offset in bits from the beginning of the
96 structure to this field.
108 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
109 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
110 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
113 In order to solve the system of set constraints, the following is
116 1. Each constraint variable x has a solution set associated with it,
119 2. Constraints are separated into direct, copy, and complex.
120 Direct constraints are ADDRESSOF constraints that require no extra
121 processing, such as P = &Q
122 Copy constraints are those of the form P = Q.
123 Complex constraints are all the constraints involving dereferences
124 and offsets (including offsetted copies).
126 3. All direct constraints of the form P = &Q are processed, such
127 that Q is added to Sol(P)
129 4. All complex constraints for a given constraint variable are stored in a
130 linked list attached to that variable's node.
132 5. A directed graph is built out of the copy constraints. Each
133 constraint variable is a node in the graph, and an edge from
134 Q to P is added for each copy constraint of the form P = Q
136 6. The graph is then walked, and solution sets are
137 propagated along the copy edges, such that an edge from Q to P
138 causes Sol(P) <- Sol(P) union Sol(Q).
140 7. As we visit each node, all complex constraints associated with
141 that node are processed by adding appropriate copy edges to the graph, or the
142 appropriate variables to the solution set.
144 8. The process of walking the graph is iterated until no solution
147 Prior to walking the graph in steps 6 and 7, We perform static
148 cycle elimination on the constraint graph, as well
149 as off-line variable substitution.
151 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
152 on and turned into anything), but isn't. You can just see what offset
153 inside the pointed-to struct it's going to access.
155 TODO: Constant bounded arrays can be handled as if they were structs of the
156 same number of elements.
158 TODO: Modeling heap and incoming pointers becomes much better if we
159 add fields to them as we discover them, which we could do.
161 TODO: We could handle unions, but to be honest, it's probably not
162 worth the pain or slowdown. */
164 /* IPA-PTA optimizations possible.
166 When the indirect function called is ANYTHING we can add disambiguation
167 based on the function signatures (or simply the parameter count which
168 is the varinfo size). We also do not need to consider functions that
169 do not have their address taken.
171 The is_global_var bit which marks escape points is overly conservative
172 in IPA mode. Split it to is_escape_point and is_global_var - only
173 externally visible globals are escape points in IPA mode. This is
174 also needed to fix the pt_solution_includes_global predicate
175 (and thus ptr_deref_may_alias_global_p).
177 The way we introduce DECL_PT_UID to avoid fixing up all points-to
178 sets in the translation unit when we copy a DECL during inlining
179 pessimizes precision. The advantage is that the DECL_PT_UID keeps
180 compile-time and memory usage overhead low - the points-to sets
181 do not grow or get unshared as they would during a fixup phase.
182 An alternative solution is to delay IPA PTA until after all
183 inlining transformations have been applied.
185 The way we propagate clobber/use information isn't optimized.
186 It should use a new complex constraint that properly filters
187 out local variables of the callee (though that would make
188 the sets invalid after inlining). OTOH we might as well
189 admit defeat to WHOPR and simply do all the clobber/use analysis
190 and propagation after PTA finished but before we threw away
191 points-to information for memory variables. WHOPR and PTA
192 do not play along well anyway - the whole constraint solving
193 would need to be done in WPA phase and it will be very interesting
194 to apply the results to local SSA names during LTRANS phase.
196 We probably should compute a per-function unit-ESCAPE solution
197 propagating it simply like the clobber / uses solutions. The
198 solution can go alongside the non-IPA espaced solution and be
199 used to query which vars escape the unit through a function.
201 We never put function decls in points-to sets so we do not
202 keep the set of called functions for indirect calls.
204 And probably more. */
206 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
207 htab_t heapvar_for_stmt;
209 static bool use_field_sensitive = true;
210 static int in_ipa_mode = 0;
212 /* Used for predecessor bitmaps. */
213 static bitmap_obstack predbitmap_obstack;
215 /* Used for points-to sets. */
216 static bitmap_obstack pta_obstack;
218 /* Used for oldsolution members of variables. */
219 static bitmap_obstack oldpta_obstack;
221 /* Used for per-solver-iteration bitmaps. */
222 static bitmap_obstack iteration_obstack;
224 static unsigned int create_variable_info_for (tree, const char *);
225 typedef struct constraint_graph *constraint_graph_t;
226 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
229 typedef struct constraint *constraint_t;
231 DEF_VEC_P(constraint_t);
232 DEF_VEC_ALLOC_P(constraint_t,heap);
234 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
236 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
238 static struct constraint_stats
240 unsigned int total_vars;
241 unsigned int nonpointer_vars;
242 unsigned int unified_vars_static;
243 unsigned int unified_vars_dynamic;
244 unsigned int iterations;
245 unsigned int num_edges;
246 unsigned int num_implicit_edges;
247 unsigned int points_to_sets_created;
252 /* ID of this variable */
255 /* True if this is a variable created by the constraint analysis, such as
256 heap variables and constraints we had to break up. */
257 unsigned int is_artificial_var : 1;
259 /* True if this is a special variable whose solution set should not be
261 unsigned int is_special_var : 1;
263 /* True for variables whose size is not known or variable. */
264 unsigned int is_unknown_size_var : 1;
266 /* True for (sub-)fields that represent a whole variable. */
267 unsigned int is_full_var : 1;
269 /* True if this is a heap variable. */
270 unsigned int is_heap_var : 1;
272 /* True if this is a variable tracking a restrict pointer source. */
273 unsigned int is_restrict_var : 1;
275 /* True if this field may contain pointers. */
276 unsigned int may_have_pointers : 1;
278 /* True if this represents a global variable. */
279 unsigned int is_global_var : 1;
281 /* True if this represents a IPA function info. */
282 unsigned int is_fn_info : 1;
284 /* A link to the variable for the next field in this structure. */
285 struct variable_info *next;
287 /* Offset of this variable, in bits, from the base variable */
288 unsigned HOST_WIDE_INT offset;
290 /* Size of the variable, in bits. */
291 unsigned HOST_WIDE_INT size;
293 /* Full size of the base variable, in bits. */
294 unsigned HOST_WIDE_INT fullsize;
296 /* Name of this variable */
299 /* Tree that this variable is associated with. */
302 /* Points-to set for this variable. */
305 /* Old points-to set for this variable. */
308 typedef struct variable_info *varinfo_t;
310 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
311 static varinfo_t first_or_preceding_vi_for_offset (varinfo_t,
312 unsigned HOST_WIDE_INT);
313 static varinfo_t lookup_vi_for_tree (tree);
315 /* Pool of variable info structures. */
316 static alloc_pool variable_info_pool;
318 DEF_VEC_P(varinfo_t);
320 DEF_VEC_ALLOC_P(varinfo_t, heap);
322 /* Table of variable info structures for constraint variables.
323 Indexed directly by variable info id. */
324 static VEC(varinfo_t,heap) *varmap;
326 /* Return the varmap element N */
328 static inline varinfo_t
329 get_varinfo (unsigned int n)
331 return VEC_index (varinfo_t, varmap, n);
334 /* Static IDs for the special variables. */
335 enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
336 escaped_id = 3, nonlocal_id = 4,
337 storedanything_id = 5, integer_id = 6 };
339 struct GTY(()) heapvar_map {
341 unsigned HOST_WIDE_INT offset;
345 heapvar_map_eq (const void *p1, const void *p2)
347 const struct heapvar_map *h1 = (const struct heapvar_map *)p1;
348 const struct heapvar_map *h2 = (const struct heapvar_map *)p2;
349 return (h1->map.base.from == h2->map.base.from
350 && h1->offset == h2->offset);
354 heapvar_map_hash (struct heapvar_map *h)
356 return iterative_hash_host_wide_int (h->offset,
357 htab_hash_pointer (h->map.base.from));
360 /* Lookup a heap var for FROM, and return it if we find one. */
363 heapvar_lookup (tree from, unsigned HOST_WIDE_INT offset)
365 struct heapvar_map *h, in;
366 in.map.base.from = from;
368 h = (struct heapvar_map *) htab_find_with_hash (heapvar_for_stmt, &in,
369 heapvar_map_hash (&in));
375 /* Insert a mapping FROM->TO in the heap var for statement
379 heapvar_insert (tree from, unsigned HOST_WIDE_INT offset, tree to)
381 struct heapvar_map *h;
384 h = GGC_NEW (struct heapvar_map);
385 h->map.base.from = from;
387 h->map.hash = heapvar_map_hash (h);
389 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->map.hash, INSERT);
390 gcc_assert (*loc == NULL);
391 *(struct heapvar_map **) loc = h;
394 /* Return a new variable info structure consisting for a variable
395 named NAME, and using constraint graph node NODE. Append it
396 to the vector of variable info structures. */
399 new_var_info (tree t, const char *name)
401 unsigned index = VEC_length (varinfo_t, varmap);
402 varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
407 /* Vars without decl are artificial and do not have sub-variables. */
408 ret->is_artificial_var = (t == NULL_TREE);
409 ret->is_special_var = false;
410 ret->is_unknown_size_var = false;
411 ret->is_full_var = (t == NULL_TREE);
412 ret->is_heap_var = false;
413 ret->is_restrict_var = false;
414 ret->may_have_pointers = true;
415 ret->is_global_var = (t == NULL_TREE);
416 ret->is_fn_info = false;
418 ret->is_global_var = is_global_var (t);
419 ret->solution = BITMAP_ALLOC (&pta_obstack);
420 ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
423 VEC_safe_push (varinfo_t, heap, varmap, ret);
429 /* A map mapping call statements to per-stmt variables for uses
430 and clobbers specific to the call. */
431 struct pointer_map_t *call_stmt_vars;
433 /* Lookup or create the variable for the call statement CALL. */
436 get_call_vi (gimple call)
441 slot_p = pointer_map_insert (call_stmt_vars, call);
443 return (varinfo_t) *slot_p;
445 vi = new_var_info (NULL_TREE, "CALLUSED");
449 vi->is_full_var = true;
451 vi->next = vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
455 vi2->is_full_var = true;
457 *slot_p = (void *) vi;
461 /* Lookup the variable for the call statement CALL representing
462 the uses. Returns NULL if there is nothing special about this call. */
465 lookup_call_use_vi (gimple call)
469 slot_p = pointer_map_contains (call_stmt_vars, call);
471 return (varinfo_t) *slot_p;
476 /* Lookup the variable for the call statement CALL representing
477 the clobbers. Returns NULL if there is nothing special about this call. */
480 lookup_call_clobber_vi (gimple call)
482 varinfo_t uses = lookup_call_use_vi (call);
489 /* Lookup or create the variable for the call statement CALL representing
493 get_call_use_vi (gimple call)
495 return get_call_vi (call);
498 /* Lookup or create the variable for the call statement CALL representing
501 static varinfo_t ATTRIBUTE_UNUSED
502 get_call_clobber_vi (gimple call)
504 return get_call_vi (call)->next;
508 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
510 /* An expression that appears in a constraint. */
512 struct constraint_expr
514 /* Constraint type. */
515 constraint_expr_type type;
517 /* Variable we are referring to in the constraint. */
520 /* Offset, in bits, of this constraint from the beginning of
521 variables it ends up referring to.
523 IOW, in a deref constraint, we would deref, get the result set,
524 then add OFFSET to each member. */
525 HOST_WIDE_INT offset;
528 /* Use 0x8000... as special unknown offset. */
529 #define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))
531 typedef struct constraint_expr ce_s;
533 DEF_VEC_ALLOC_O(ce_s, heap);
534 static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);
535 static void get_constraint_for (tree, VEC(ce_s, heap) **);
536 static void do_deref (VEC (ce_s, heap) **);
538 /* Our set constraints are made up of two constraint expressions, one
541 As described in the introduction, our set constraints each represent an
542 operation between set valued variables.
546 struct constraint_expr lhs;
547 struct constraint_expr rhs;
550 /* List of constraints that we use to build the constraint graph from. */
552 static VEC(constraint_t,heap) *constraints;
553 static alloc_pool constraint_pool;
555 /* The constraint graph is represented as an array of bitmaps
556 containing successor nodes. */
558 struct constraint_graph
560 /* Size of this graph, which may be different than the number of
561 nodes in the variable map. */
564 /* Explicit successors of each node. */
567 /* Implicit predecessors of each node (Used for variable
569 bitmap *implicit_preds;
571 /* Explicit predecessors of each node (Used for variable substitution). */
574 /* Indirect cycle representatives, or -1 if the node has no indirect
576 int *indirect_cycles;
578 /* Representative node for a node. rep[a] == a unless the node has
582 /* Equivalence class representative for a label. This is used for
583 variable substitution. */
586 /* Pointer equivalence label for a node. All nodes with the same
587 pointer equivalence label can be unified together at some point
588 (either during constraint optimization or after the constraint
592 /* Pointer equivalence representative for a label. This is used to
593 handle nodes that are pointer equivalent but not location
594 equivalent. We can unite these once the addressof constraints
595 are transformed into initial points-to sets. */
598 /* Pointer equivalence label for each node, used during variable
600 unsigned int *pointer_label;
602 /* Location equivalence label for each node, used during location
603 equivalence finding. */
604 unsigned int *loc_label;
606 /* Pointed-by set for each node, used during location equivalence
607 finding. This is pointed-by rather than pointed-to, because it
608 is constructed using the predecessor graph. */
611 /* Points to sets for pointer equivalence. This is *not* the actual
612 points-to sets for nodes. */
615 /* Bitmap of nodes where the bit is set if the node is a direct
616 node. Used for variable substitution. */
617 sbitmap direct_nodes;
619 /* Bitmap of nodes where the bit is set if the node is address
620 taken. Used for variable substitution. */
621 bitmap address_taken;
623 /* Vector of complex constraints for each graph node. Complex
624 constraints are those involving dereferences or offsets that are
626 VEC(constraint_t,heap) **complex;
629 static constraint_graph_t graph;
631 /* During variable substitution and the offline version of indirect
632 cycle finding, we create nodes to represent dereferences and
633 address taken constraints. These represent where these start and
635 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
636 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
638 /* Return the representative node for NODE, if NODE has been unioned
640 This function performs path compression along the way to finding
641 the representative. */
644 find (unsigned int node)
646 gcc_assert (node < graph->size);
647 if (graph->rep[node] != node)
648 return graph->rep[node] = find (graph->rep[node]);
652 /* Union the TO and FROM nodes to the TO nodes.
653 Note that at some point in the future, we may want to do
654 union-by-rank, in which case we are going to have to return the
655 node we unified to. */
658 unite (unsigned int to, unsigned int from)
660 gcc_assert (to < graph->size && from < graph->size);
661 if (to != from && graph->rep[from] != to)
663 graph->rep[from] = to;
669 /* Create a new constraint consisting of LHS and RHS expressions. */
672 new_constraint (const struct constraint_expr lhs,
673 const struct constraint_expr rhs)
675 constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
681 /* Print out constraint C to FILE. */
684 dump_constraint (FILE *file, constraint_t c)
686 if (c->lhs.type == ADDRESSOF)
688 else if (c->lhs.type == DEREF)
690 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
691 if (c->lhs.offset == UNKNOWN_OFFSET)
692 fprintf (file, " + UNKNOWN");
693 else if (c->lhs.offset != 0)
694 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
695 fprintf (file, " = ");
696 if (c->rhs.type == ADDRESSOF)
698 else if (c->rhs.type == DEREF)
700 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
701 if (c->rhs.offset == UNKNOWN_OFFSET)
702 fprintf (file, " + UNKNOWN");
703 else if (c->rhs.offset != 0)
704 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
705 fprintf (file, "\n");
709 void debug_constraint (constraint_t);
710 void debug_constraints (void);
711 void debug_constraint_graph (void);
712 void debug_solution_for_var (unsigned int);
713 void debug_sa_points_to_info (void);
715 /* Print out constraint C to stderr. */
718 debug_constraint (constraint_t c)
720 dump_constraint (stderr, c);
723 /* Print out all constraints to FILE */
726 dump_constraints (FILE *file, int from)
730 for (i = from; VEC_iterate (constraint_t, constraints, i, c); i++)
731 dump_constraint (file, c);
734 /* Print out all constraints to stderr. */
737 debug_constraints (void)
739 dump_constraints (stderr, 0);
742 /* Print out to FILE the edge in the constraint graph that is created by
743 constraint c. The edge may have a label, depending on the type of
744 constraint that it represents. If complex1, e.g: a = *b, then the label
745 is "=*", if complex2, e.g: *a = b, then the label is "*=", if
746 complex with an offset, e.g: a = b + 8, then the label is "+".
747 Otherwise the edge has no label. */
750 dump_constraint_edge (FILE *file, constraint_t c)
752 if (c->rhs.type != ADDRESSOF)
754 const char *src = get_varinfo (c->rhs.var)->name;
755 const char *dst = get_varinfo (c->lhs.var)->name;
756 fprintf (file, " \"%s\" -> \"%s\" ", src, dst);
757 /* Due to preprocessing of constraints, instructions like *a = *b are
758 illegal; thus, we do not have to handle such cases. */
759 if (c->lhs.type == DEREF)
760 fprintf (file, " [ label=\"*=\" ] ;\n");
761 else if (c->rhs.type == DEREF)
762 fprintf (file, " [ label=\"=*\" ] ;\n");
765 /* We must check the case where the constraint is an offset.
766 In this case, it is treated as a complex constraint. */
767 if (c->rhs.offset != c->lhs.offset)
768 fprintf (file, " [ label=\"+\" ] ;\n");
770 fprintf (file, " ;\n");
775 /* Print the constraint graph in dot format. */
778 dump_constraint_graph (FILE *file)
780 unsigned int i=0, size;
783 /* Only print the graph if it has already been initialized: */
787 /* Print the constraints used to produce the constraint graph. The
788 constraints will be printed as comments in the dot file: */
789 fprintf (file, "\n\n/* Constraints used in the constraint graph:\n");
790 dump_constraints (file, 0);
791 fprintf (file, "*/\n");
793 /* Prints the header of the dot file: */
794 fprintf (file, "\n\n// The constraint graph in dot format:\n");
795 fprintf (file, "strict digraph {\n");
796 fprintf (file, " node [\n shape = box\n ]\n");
797 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
798 fprintf (file, "\n // List of nodes in the constraint graph:\n");
800 /* The next lines print the nodes in the graph. In order to get the
801 number of nodes in the graph, we must choose the minimum between the
802 vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
803 yet been initialized, then graph->size == 0, otherwise we must only
804 read nodes that have an entry in VEC (varinfo_t, varmap). */
805 size = VEC_length (varinfo_t, varmap);
806 size = size < graph->size ? size : graph->size;
807 for (i = 0; i < size; i++)
809 const char *name = get_varinfo (graph->rep[i])->name;
810 fprintf (file, " \"%s\" ;\n", name);
813 /* Go over the list of constraints printing the edges in the constraint
815 fprintf (file, "\n // The constraint edges:\n");
816 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
818 dump_constraint_edge (file, c);
820 /* Prints the tail of the dot file. By now, only the closing bracket. */
821 fprintf (file, "}\n\n\n");
824 /* Print out the constraint graph to stderr. */
827 debug_constraint_graph (void)
829 dump_constraint_graph (stderr);
834 The solver is a simple worklist solver, that works on the following
837 sbitmap changed_nodes = all zeroes;
839 For each node that is not already collapsed:
841 set bit in changed nodes
843 while (changed_count > 0)
845 compute topological ordering for constraint graph
847 find and collapse cycles in the constraint graph (updating
848 changed if necessary)
850 for each node (n) in the graph in topological order:
853 Process each complex constraint associated with the node,
854 updating changed if necessary.
856 For each outgoing edge from n, propagate the solution from n to
857 the destination of the edge, updating changed as necessary.
861 /* Return true if two constraint expressions A and B are equal. */
864 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
866 return a.type == b.type && a.var == b.var && a.offset == b.offset;
869 /* Return true if constraint expression A is less than constraint expression
870 B. This is just arbitrary, but consistent, in order to give them an
874 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
876 if (a.type == b.type)
879 return a.offset < b.offset;
881 return a.var < b.var;
884 return a.type < b.type;
887 /* Return true if constraint A is less than constraint B. This is just
888 arbitrary, but consistent, in order to give them an ordering. */
891 constraint_less (const constraint_t a, const constraint_t b)
893 if (constraint_expr_less (a->lhs, b->lhs))
895 else if (constraint_expr_less (b->lhs, a->lhs))
898 return constraint_expr_less (a->rhs, b->rhs);
901 /* Return true if two constraints A and B are equal. */
904 constraint_equal (struct constraint a, struct constraint b)
906 return constraint_expr_equal (a.lhs, b.lhs)
907 && constraint_expr_equal (a.rhs, b.rhs);
911 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
914 constraint_vec_find (VEC(constraint_t,heap) *vec,
915 struct constraint lookfor)
923 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
924 if (place >= VEC_length (constraint_t, vec))
926 found = VEC_index (constraint_t, vec, place);
927 if (!constraint_equal (*found, lookfor))
932 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
935 constraint_set_union (VEC(constraint_t,heap) **to,
936 VEC(constraint_t,heap) **from)
941 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
943 if (constraint_vec_find (*to, *c) == NULL)
945 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
947 VEC_safe_insert (constraint_t, heap, *to, place, c);
952 /* Expands the solution in SET to all sub-fields of variables included.
953 Union the expanded result into RESULT. */
956 solution_set_expand (bitmap result, bitmap set)
962 /* In a first pass record all variables we need to add all
963 sub-fields off. This avoids quadratic behavior. */
964 EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
966 varinfo_t v = get_varinfo (j);
967 if (v->is_artificial_var
970 v = lookup_vi_for_tree (v->decl);
972 vars = BITMAP_ALLOC (NULL);
973 bitmap_set_bit (vars, v->id);
976 /* In the second pass now do the addition to the solution and
977 to speed up solving add it to the delta as well. */
980 EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
982 varinfo_t v = get_varinfo (j);
983 for (; v != NULL; v = v->next)
984 bitmap_set_bit (result, v->id);
990 /* Take a solution set SET, add OFFSET to each member of the set, and
991 overwrite SET with the result when done. */
994 solution_set_add (bitmap set, HOST_WIDE_INT offset)
996 bitmap result = BITMAP_ALLOC (&iteration_obstack);
1000 /* If the offset is unknown we have to expand the solution to
1002 if (offset == UNKNOWN_OFFSET)
1004 solution_set_expand (set, set);
1008 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
1010 varinfo_t vi = get_varinfo (i);
1012 /* If this is a variable with just one field just set its bit
1014 if (vi->is_artificial_var
1015 || vi->is_unknown_size_var
1017 bitmap_set_bit (result, i);
1020 unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
1022 /* If the offset makes the pointer point to before the
1023 variable use offset zero for the field lookup. */
1025 && fieldoffset > vi->offset)
1029 vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
1031 bitmap_set_bit (result, vi->id);
1032 /* If the result is not exactly at fieldoffset include the next
1033 field as well. See get_constraint_for_ptr_offset for more
1035 if (vi->offset != fieldoffset
1036 && vi->next != NULL)
1037 bitmap_set_bit (result, vi->next->id);
1041 bitmap_copy (set, result);
1042 BITMAP_FREE (result);
1045 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
1049 set_union_with_increment (bitmap to, bitmap from, HOST_WIDE_INT inc)
1052 return bitmap_ior_into (to, from);
1058 tmp = BITMAP_ALLOC (&iteration_obstack);
1059 bitmap_copy (tmp, from);
1060 solution_set_add (tmp, inc);
1061 res = bitmap_ior_into (to, tmp);
1067 /* Insert constraint C into the list of complex constraints for graph
1071 insert_into_complex (constraint_graph_t graph,
1072 unsigned int var, constraint_t c)
1074 VEC (constraint_t, heap) *complex = graph->complex[var];
1075 unsigned int place = VEC_lower_bound (constraint_t, complex, c,
1078 /* Only insert constraints that do not already exist. */
1079 if (place >= VEC_length (constraint_t, complex)
1080 || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
1081 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
1085 /* Condense two variable nodes into a single variable node, by moving
1086 all associated info from SRC to TO. */
1089 merge_node_constraints (constraint_graph_t graph, unsigned int to,
1095 gcc_assert (find (from) == to);
1097 /* Move all complex constraints from src node into to node */
1098 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
1100 /* In complex constraints for node src, we may have either
1101 a = *src, and *src = a, or an offseted constraint which are
1102 always added to the rhs node's constraints. */
1104 if (c->rhs.type == DEREF)
1106 else if (c->lhs.type == DEREF)
1111 constraint_set_union (&graph->complex[to], &graph->complex[from]);
1112 VEC_free (constraint_t, heap, graph->complex[from]);
1113 graph->complex[from] = NULL;
1117 /* Remove edges involving NODE from GRAPH. */
1120 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
1122 if (graph->succs[node])
1123 BITMAP_FREE (graph->succs[node]);
1126 /* Merge GRAPH nodes FROM and TO into node TO. */
1129 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1132 if (graph->indirect_cycles[from] != -1)
1134 /* If we have indirect cycles with the from node, and we have
1135 none on the to node, the to node has indirect cycles from the
1136 from node now that they are unified.
1137 If indirect cycles exist on both, unify the nodes that they
1138 are in a cycle with, since we know they are in a cycle with
1140 if (graph->indirect_cycles[to] == -1)
1141 graph->indirect_cycles[to] = graph->indirect_cycles[from];
1144 /* Merge all the successor edges. */
1145 if (graph->succs[from])
1147 if (!graph->succs[to])
1148 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1149 bitmap_ior_into (graph->succs[to],
1150 graph->succs[from]);
1153 clear_edges_for_node (graph, from);
1157 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1158 it doesn't exist in the graph already. */
1161 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1167 if (!graph->implicit_preds[to])
1168 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1170 if (bitmap_set_bit (graph->implicit_preds[to], from))
1171 stats.num_implicit_edges++;
1174 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1175 it doesn't exist in the graph already.
1176 Return false if the edge already existed, true otherwise. */
1179 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1182 if (!graph->preds[to])
1183 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1184 bitmap_set_bit (graph->preds[to], from);
1187 /* Add a graph edge to GRAPH, going from FROM to TO if
1188 it doesn't exist in the graph already.
1189 Return false if the edge already existed, true otherwise. */
1192 add_graph_edge (constraint_graph_t graph, unsigned int to,
1203 if (!graph->succs[from])
1204 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1205 if (bitmap_set_bit (graph->succs[from], to))
1208 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1216 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1219 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1222 return (graph->succs[dest]
1223 && bitmap_bit_p (graph->succs[dest], src));
1226 /* Initialize the constraint graph structure to contain SIZE nodes. */
1229 init_graph (unsigned int size)
1233 graph = XCNEW (struct constraint_graph);
1235 graph->succs = XCNEWVEC (bitmap, graph->size);
1236 graph->indirect_cycles = XNEWVEC (int, graph->size);
1237 graph->rep = XNEWVEC (unsigned int, graph->size);
1238 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
1239 graph->pe = XCNEWVEC (unsigned int, graph->size);
1240 graph->pe_rep = XNEWVEC (int, graph->size);
1242 for (j = 0; j < graph->size; j++)
1245 graph->pe_rep[j] = -1;
1246 graph->indirect_cycles[j] = -1;
1250 /* Build the constraint graph, adding only predecessor edges right now. */
1253 build_pred_graph (void)
1259 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1260 graph->preds = XCNEWVEC (bitmap, graph->size);
1261 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1262 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1263 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1264 graph->points_to = XCNEWVEC (bitmap, graph->size);
1265 graph->eq_rep = XNEWVEC (int, graph->size);
1266 graph->direct_nodes = sbitmap_alloc (graph->size);
1267 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1268 sbitmap_zero (graph->direct_nodes);
1270 for (j = 0; j < FIRST_REF_NODE; j++)
1272 if (!get_varinfo (j)->is_special_var)
1273 SET_BIT (graph->direct_nodes, j);
1276 for (j = 0; j < graph->size; j++)
1277 graph->eq_rep[j] = -1;
1279 for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
1280 graph->indirect_cycles[j] = -1;
1282 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1284 struct constraint_expr lhs = c->lhs;
1285 struct constraint_expr rhs = c->rhs;
1286 unsigned int lhsvar = lhs.var;
1287 unsigned int rhsvar = rhs.var;
1289 if (lhs.type == DEREF)
1292 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1293 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1295 else if (rhs.type == DEREF)
1298 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1299 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1301 RESET_BIT (graph->direct_nodes, lhsvar);
1303 else if (rhs.type == ADDRESSOF)
1308 if (graph->points_to[lhsvar] == NULL)
1309 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1310 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1312 if (graph->pointed_by[rhsvar] == NULL)
1313 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1314 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1316 /* Implicitly, *x = y */
1317 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1319 /* All related variables are no longer direct nodes. */
1320 RESET_BIT (graph->direct_nodes, rhsvar);
1321 v = get_varinfo (rhsvar);
1322 if (!v->is_full_var)
1324 v = lookup_vi_for_tree (v->decl);
1327 RESET_BIT (graph->direct_nodes, v->id);
1332 bitmap_set_bit (graph->address_taken, rhsvar);
1334 else if (lhsvar > anything_id
1335 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1338 add_pred_graph_edge (graph, lhsvar, rhsvar);
1339 /* Implicitly, *x = *y */
1340 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1341 FIRST_REF_NODE + rhsvar);
1343 else if (lhs.offset != 0 || rhs.offset != 0)
1345 if (rhs.offset != 0)
1346 RESET_BIT (graph->direct_nodes, lhs.var);
1347 else if (lhs.offset != 0)
1348 RESET_BIT (graph->direct_nodes, rhs.var);
1353 /* Build the constraint graph, adding successor edges. */
1356 build_succ_graph (void)
1361 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1363 struct constraint_expr lhs;
1364 struct constraint_expr rhs;
1365 unsigned int lhsvar;
1366 unsigned int rhsvar;
1373 lhsvar = find (lhs.var);
1374 rhsvar = find (rhs.var);
1376 if (lhs.type == DEREF)
1378 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1379 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1381 else if (rhs.type == DEREF)
1383 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1384 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1386 else if (rhs.type == ADDRESSOF)
1389 gcc_assert (find (rhs.var) == rhs.var);
1390 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1392 else if (lhsvar > anything_id
1393 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1395 add_graph_edge (graph, lhsvar, rhsvar);
1399 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1400 receive pointers. */
1401 t = find (storedanything_id);
1402 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1404 if (!TEST_BIT (graph->direct_nodes, i)
1405 && get_varinfo (i)->may_have_pointers)
1406 add_graph_edge (graph, find (i), t);
1409 /* Everything stored to ANYTHING also potentially escapes. */
1410 add_graph_edge (graph, find (escaped_id), t);
1414 /* Changed variables on the last iteration. */
1415 static unsigned int changed_count;
1416 static sbitmap changed;
1418 /* Strongly Connected Component visitation info. */
1425 unsigned int *node_mapping;
1427 VEC(unsigned,heap) *scc_stack;
1431 /* Recursive routine to find strongly connected components in GRAPH.
1432 SI is the SCC info to store the information in, and N is the id of current
1433 graph node we are processing.
1435 This is Tarjan's strongly connected component finding algorithm, as
1436 modified by Nuutila to keep only non-root nodes on the stack.
1437 The algorithm can be found in "On finding the strongly connected
1438 connected components in a directed graph" by Esko Nuutila and Eljas
1439 Soisalon-Soininen, in Information Processing Letters volume 49,
1440 number 1, pages 9-14. */
1443 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1447 unsigned int my_dfs;
1449 SET_BIT (si->visited, n);
1450 si->dfs[n] = si->current_index ++;
1451 my_dfs = si->dfs[n];
1453 /* Visit all the successors. */
1454 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1458 if (i > LAST_REF_NODE)
1462 if (TEST_BIT (si->deleted, w))
1465 if (!TEST_BIT (si->visited, w))
1466 scc_visit (graph, si, w);
1468 unsigned int t = find (w);
1469 unsigned int nnode = find (n);
1470 gcc_assert (nnode == n);
1472 if (si->dfs[t] < si->dfs[nnode])
1473 si->dfs[n] = si->dfs[t];
1477 /* See if any components have been identified. */
1478 if (si->dfs[n] == my_dfs)
1480 if (VEC_length (unsigned, si->scc_stack) > 0
1481 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1483 bitmap scc = BITMAP_ALLOC (NULL);
1484 unsigned int lowest_node;
1487 bitmap_set_bit (scc, n);
1489 while (VEC_length (unsigned, si->scc_stack) != 0
1490 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1492 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1494 bitmap_set_bit (scc, w);
1497 lowest_node = bitmap_first_set_bit (scc);
1498 gcc_assert (lowest_node < FIRST_REF_NODE);
1500 /* Collapse the SCC nodes into a single node, and mark the
1502 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1504 if (i < FIRST_REF_NODE)
1506 if (unite (lowest_node, i))
1507 unify_nodes (graph, lowest_node, i, false);
1511 unite (lowest_node, i);
1512 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1516 SET_BIT (si->deleted, n);
1519 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1522 /* Unify node FROM into node TO, updating the changed count if
1523 necessary when UPDATE_CHANGED is true. */
1526 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1527 bool update_changed)
1530 gcc_assert (to != from && find (to) == to);
1531 if (dump_file && (dump_flags & TDF_DETAILS))
1532 fprintf (dump_file, "Unifying %s to %s\n",
1533 get_varinfo (from)->name,
1534 get_varinfo (to)->name);
1537 stats.unified_vars_dynamic++;
1539 stats.unified_vars_static++;
1541 merge_graph_nodes (graph, to, from);
1542 merge_node_constraints (graph, to, from);
1544 /* Mark TO as changed if FROM was changed. If TO was already marked
1545 as changed, decrease the changed count. */
1547 if (update_changed && TEST_BIT (changed, from))
1549 RESET_BIT (changed, from);
1550 if (!TEST_BIT (changed, to))
1551 SET_BIT (changed, to);
1554 gcc_assert (changed_count > 0);
1558 if (get_varinfo (from)->solution)
1560 /* If the solution changes because of the merging, we need to mark
1561 the variable as changed. */
1562 if (bitmap_ior_into (get_varinfo (to)->solution,
1563 get_varinfo (from)->solution))
1565 if (update_changed && !TEST_BIT (changed, to))
1567 SET_BIT (changed, to);
1572 BITMAP_FREE (get_varinfo (from)->solution);
1573 BITMAP_FREE (get_varinfo (from)->oldsolution);
1575 if (stats.iterations > 0)
1577 BITMAP_FREE (get_varinfo (to)->oldsolution);
1578 get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1581 if (valid_graph_edge (graph, to, to))
1583 if (graph->succs[to])
1584 bitmap_clear_bit (graph->succs[to], to);
1588 /* Information needed to compute the topological ordering of a graph. */
1592 /* sbitmap of visited nodes. */
1594 /* Array that stores the topological order of the graph, *in
1596 VEC(unsigned,heap) *topo_order;
1600 /* Initialize and return a topological info structure. */
1602 static struct topo_info *
1603 init_topo_info (void)
1605 size_t size = graph->size;
1606 struct topo_info *ti = XNEW (struct topo_info);
1607 ti->visited = sbitmap_alloc (size);
1608 sbitmap_zero (ti->visited);
1609 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1614 /* Free the topological sort info pointed to by TI. */
1617 free_topo_info (struct topo_info *ti)
1619 sbitmap_free (ti->visited);
1620 VEC_free (unsigned, heap, ti->topo_order);
1624 /* Visit the graph in topological order, and store the order in the
1625 topo_info structure. */
1628 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1634 SET_BIT (ti->visited, n);
1636 if (graph->succs[n])
1637 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1639 if (!TEST_BIT (ti->visited, j))
1640 topo_visit (graph, ti, j);
1643 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1646 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1647 starting solution for y. */
1650 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1653 unsigned int lhs = c->lhs.var;
1655 bitmap sol = get_varinfo (lhs)->solution;
1658 HOST_WIDE_INT roffset = c->rhs.offset;
1660 /* Our IL does not allow this. */
1661 gcc_assert (c->lhs.offset == 0);
1663 /* If the solution of Y contains anything it is good enough to transfer
1665 if (bitmap_bit_p (delta, anything_id))
1667 flag |= bitmap_set_bit (sol, anything_id);
1671 /* If we do not know at with offset the rhs is dereferenced compute
1672 the reachability set of DELTA, conservatively assuming it is
1673 dereferenced at all valid offsets. */
1674 if (roffset == UNKNOWN_OFFSET)
1676 solution_set_expand (delta, delta);
1677 /* No further offset processing is necessary. */
1681 /* For each variable j in delta (Sol(y)), add
1682 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1683 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1685 varinfo_t v = get_varinfo (j);
1686 HOST_WIDE_INT fieldoffset = v->offset + roffset;
1690 fieldoffset = v->offset;
1691 else if (roffset != 0)
1692 v = first_vi_for_offset (v, fieldoffset);
1693 /* If the access is outside of the variable we can ignore it. */
1701 /* Adding edges from the special vars is pointless.
1702 They don't have sets that can change. */
1703 if (get_varinfo (t)->is_special_var)
1704 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1705 /* Merging the solution from ESCAPED needlessly increases
1706 the set. Use ESCAPED as representative instead. */
1707 else if (v->id == escaped_id)
1708 flag |= bitmap_set_bit (sol, escaped_id);
1709 else if (add_graph_edge (graph, lhs, t))
1710 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1712 /* If the variable is not exactly at the requested offset
1713 we have to include the next one. */
1714 if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1719 fieldoffset = v->offset;
1725 /* If the LHS solution changed, mark the var as changed. */
1728 get_varinfo (lhs)->solution = sol;
1729 if (!TEST_BIT (changed, lhs))
1731 SET_BIT (changed, lhs);
1737 /* Process a constraint C that represents *(x + off) = y using DELTA
1738 as the starting solution for x. */
1741 do_ds_constraint (constraint_t c, bitmap delta)
1743 unsigned int rhs = c->rhs.var;
1744 bitmap sol = get_varinfo (rhs)->solution;
1747 HOST_WIDE_INT loff = c->lhs.offset;
1749 /* Our IL does not allow this. */
1750 gcc_assert (c->rhs.offset == 0);
1752 /* If the solution of y contains ANYTHING simply use the ANYTHING
1753 solution. This avoids needlessly increasing the points-to sets. */
1754 if (bitmap_bit_p (sol, anything_id))
1755 sol = get_varinfo (find (anything_id))->solution;
1757 /* If the solution for x contains ANYTHING we have to merge the
1758 solution of y into all pointer variables which we do via
1760 if (bitmap_bit_p (delta, anything_id))
1762 unsigned t = find (storedanything_id);
1763 if (add_graph_edge (graph, t, rhs))
1765 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1767 if (!TEST_BIT (changed, t))
1769 SET_BIT (changed, t);
1777 /* If we do not know at with offset the rhs is dereferenced compute
1778 the reachability set of DELTA, conservatively assuming it is
1779 dereferenced at all valid offsets. */
1780 if (loff == UNKNOWN_OFFSET)
1782 solution_set_expand (delta, delta);
1786 /* For each member j of delta (Sol(x)), add an edge from y to j and
1787 union Sol(y) into Sol(j) */
1788 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1790 varinfo_t v = get_varinfo (j);
1792 HOST_WIDE_INT fieldoffset = v->offset + loff;
1794 /* If v is a global variable then this is an escape point. */
1795 if (v->is_global_var)
1797 t = find (escaped_id);
1798 if (add_graph_edge (graph, t, rhs)
1799 && bitmap_ior_into (get_varinfo (t)->solution, sol)
1800 && !TEST_BIT (changed, t))
1802 SET_BIT (changed, t);
1807 if (v->is_special_var)
1811 fieldoffset = v->offset;
1813 v = first_vi_for_offset (v, fieldoffset);
1814 /* If the access is outside of the variable we can ignore it. */
1820 if (v->may_have_pointers)
1823 if (add_graph_edge (graph, t, rhs)
1824 && bitmap_ior_into (get_varinfo (t)->solution, sol)
1825 && !TEST_BIT (changed, t))
1827 SET_BIT (changed, t);
1832 /* If the variable is not exactly at the requested offset
1833 we have to include the next one. */
1834 if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1839 fieldoffset = v->offset;
1845 /* Handle a non-simple (simple meaning requires no iteration),
1846 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1849 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1851 if (c->lhs.type == DEREF)
1853 if (c->rhs.type == ADDRESSOF)
1860 do_ds_constraint (c, delta);
1863 else if (c->rhs.type == DEREF)
1866 if (!(get_varinfo (c->lhs.var)->is_special_var))
1867 do_sd_constraint (graph, c, delta);
1875 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1876 solution = get_varinfo (c->rhs.var)->solution;
1877 tmp = get_varinfo (c->lhs.var)->solution;
1879 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1883 get_varinfo (c->lhs.var)->solution = tmp;
1884 if (!TEST_BIT (changed, c->lhs.var))
1886 SET_BIT (changed, c->lhs.var);
1893 /* Initialize and return a new SCC info structure. */
1895 static struct scc_info *
1896 init_scc_info (size_t size)
1898 struct scc_info *si = XNEW (struct scc_info);
1901 si->current_index = 0;
1902 si->visited = sbitmap_alloc (size);
1903 sbitmap_zero (si->visited);
1904 si->deleted = sbitmap_alloc (size);
1905 sbitmap_zero (si->deleted);
1906 si->node_mapping = XNEWVEC (unsigned int, size);
1907 si->dfs = XCNEWVEC (unsigned int, size);
1909 for (i = 0; i < size; i++)
1910 si->node_mapping[i] = i;
1912 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1916 /* Free an SCC info structure pointed to by SI */
1919 free_scc_info (struct scc_info *si)
1921 sbitmap_free (si->visited);
1922 sbitmap_free (si->deleted);
1923 free (si->node_mapping);
1925 VEC_free (unsigned, heap, si->scc_stack);
1930 /* Find indirect cycles in GRAPH that occur, using strongly connected
1931 components, and note them in the indirect cycles map.
1933 This technique comes from Ben Hardekopf and Calvin Lin,
1934 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1935 Lines of Code", submitted to PLDI 2007. */
1938 find_indirect_cycles (constraint_graph_t graph)
1941 unsigned int size = graph->size;
1942 struct scc_info *si = init_scc_info (size);
1944 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1945 if (!TEST_BIT (si->visited, i) && find (i) == i)
1946 scc_visit (graph, si, i);
1951 /* Compute a topological ordering for GRAPH, and store the result in the
1952 topo_info structure TI. */
1955 compute_topo_order (constraint_graph_t graph,
1956 struct topo_info *ti)
1959 unsigned int size = graph->size;
1961 for (i = 0; i != size; ++i)
1962 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1963 topo_visit (graph, ti, i);
1966 /* Structure used to for hash value numbering of pointer equivalence
1969 typedef struct equiv_class_label
1972 unsigned int equivalence_class;
1974 } *equiv_class_label_t;
1975 typedef const struct equiv_class_label *const_equiv_class_label_t;
1977 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1979 static htab_t pointer_equiv_class_table;
1981 /* A hashtable for mapping a bitmap of labels->location equivalence
1983 static htab_t location_equiv_class_table;
1985 /* Hash function for a equiv_class_label_t */
1988 equiv_class_label_hash (const void *p)
1990 const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
1991 return ecl->hashcode;
1994 /* Equality function for two equiv_class_label_t's. */
1997 equiv_class_label_eq (const void *p1, const void *p2)
1999 const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
2000 const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
2001 return (eql1->hashcode == eql2->hashcode
2002 && bitmap_equal_p (eql1->labels, eql2->labels));
2005 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
2009 equiv_class_lookup (htab_t table, bitmap labels)
2012 struct equiv_class_label ecl;
2014 ecl.labels = labels;
2015 ecl.hashcode = bitmap_hash (labels);
2017 slot = htab_find_slot_with_hash (table, &ecl,
2018 ecl.hashcode, NO_INSERT);
2022 return ((equiv_class_label_t) *slot)->equivalence_class;
2026 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
2030 equiv_class_add (htab_t table, unsigned int equivalence_class,
2034 equiv_class_label_t ecl = XNEW (struct equiv_class_label);
2036 ecl->labels = labels;
2037 ecl->equivalence_class = equivalence_class;
2038 ecl->hashcode = bitmap_hash (labels);
2040 slot = htab_find_slot_with_hash (table, ecl,
2041 ecl->hashcode, INSERT);
2042 gcc_assert (!*slot);
2043 *slot = (void *) ecl;
2046 /* Perform offline variable substitution.
2048 This is a worst case quadratic time way of identifying variables
2049 that must have equivalent points-to sets, including those caused by
2050 static cycles, and single entry subgraphs, in the constraint graph.
2052 The technique is described in "Exploiting Pointer and Location
2053 Equivalence to Optimize Pointer Analysis. In the 14th International
2054 Static Analysis Symposium (SAS), August 2007." It is known as the
2055 "HU" algorithm, and is equivalent to value numbering the collapsed
2056 constraint graph including evaluating unions.
2058 The general method of finding equivalence classes is as follows:
2059 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
2060 Initialize all non-REF nodes to be direct nodes.
2061 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
2063 For each constraint containing the dereference, we also do the same
2066 We then compute SCC's in the graph and unify nodes in the same SCC,
2069 For each non-collapsed node x:
2070 Visit all unvisited explicit incoming edges.
2071 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
2073 Lookup the equivalence class for pts(x).
2074 If we found one, equivalence_class(x) = found class.
2075 Otherwise, equivalence_class(x) = new class, and new_class is
2076 added to the lookup table.
2078 All direct nodes with the same equivalence class can be replaced
2079 with a single representative node.
2080 All unlabeled nodes (label == 0) are not pointers and all edges
2081 involving them can be eliminated.
2082 We perform these optimizations during rewrite_constraints
2084 In addition to pointer equivalence class finding, we also perform
2085 location equivalence class finding. This is the set of variables
2086 that always appear together in points-to sets. We use this to
2087 compress the size of the points-to sets. */
2089 /* Current maximum pointer equivalence class id. */
2090 static int pointer_equiv_class;
2092 /* Current maximum location equivalence class id. */
2093 static int location_equiv_class;
2095 /* Recursive routine to find strongly connected components in GRAPH,
2096 and label it's nodes with DFS numbers. */
2099 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2103 unsigned int my_dfs;
2105 gcc_assert (si->node_mapping[n] == n);
2106 SET_BIT (si->visited, n);
2107 si->dfs[n] = si->current_index ++;
2108 my_dfs = si->dfs[n];
2110 /* Visit all the successors. */
2111 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2113 unsigned int w = si->node_mapping[i];
2115 if (TEST_BIT (si->deleted, w))
2118 if (!TEST_BIT (si->visited, w))
2119 condense_visit (graph, si, w);
2121 unsigned int t = si->node_mapping[w];
2122 unsigned int nnode = si->node_mapping[n];
2123 gcc_assert (nnode == n);
2125 if (si->dfs[t] < si->dfs[nnode])
2126 si->dfs[n] = si->dfs[t];
2130 /* Visit all the implicit predecessors. */
2131 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
2133 unsigned int w = si->node_mapping[i];
2135 if (TEST_BIT (si->deleted, w))
2138 if (!TEST_BIT (si->visited, w))
2139 condense_visit (graph, si, w);
2141 unsigned int t = si->node_mapping[w];
2142 unsigned int nnode = si->node_mapping[n];
2143 gcc_assert (nnode == n);
2145 if (si->dfs[t] < si->dfs[nnode])
2146 si->dfs[n] = si->dfs[t];
2150 /* See if any components have been identified. */
2151 if (si->dfs[n] == my_dfs)
2153 while (VEC_length (unsigned, si->scc_stack) != 0
2154 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
2156 unsigned int w = VEC_pop (unsigned, si->scc_stack);
2157 si->node_mapping[w] = n;
2159 if (!TEST_BIT (graph->direct_nodes, w))
2160 RESET_BIT (graph->direct_nodes, n);
2162 /* Unify our nodes. */
2163 if (graph->preds[w])
2165 if (!graph->preds[n])
2166 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2167 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2169 if (graph->implicit_preds[w])
2171 if (!graph->implicit_preds[n])
2172 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2173 bitmap_ior_into (graph->implicit_preds[n],
2174 graph->implicit_preds[w]);
2176 if (graph->points_to[w])
2178 if (!graph->points_to[n])
2179 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2180 bitmap_ior_into (graph->points_to[n],
2181 graph->points_to[w]);
2184 SET_BIT (si->deleted, n);
2187 VEC_safe_push (unsigned, heap, si->scc_stack, n);
2190 /* Label pointer equivalences. */
2193 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2197 SET_BIT (si->visited, n);
2199 if (!graph->points_to[n])
2200 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2202 /* Label and union our incoming edges's points to sets. */
2203 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2205 unsigned int w = si->node_mapping[i];
2206 if (!TEST_BIT (si->visited, w))
2207 label_visit (graph, si, w);
2209 /* Skip unused edges */
2210 if (w == n || graph->pointer_label[w] == 0)
2213 if (graph->points_to[w])
2214 bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
2216 /* Indirect nodes get fresh variables. */
2217 if (!TEST_BIT (graph->direct_nodes, n))
2218 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2220 if (!bitmap_empty_p (graph->points_to[n]))
2222 unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
2223 graph->points_to[n]);
2226 label = pointer_equiv_class++;
2227 equiv_class_add (pointer_equiv_class_table,
2228 label, graph->points_to[n]);
2230 graph->pointer_label[n] = label;
2234 /* Perform offline variable substitution, discovering equivalence
2235 classes, and eliminating non-pointer variables. */
2237 static struct scc_info *
2238 perform_var_substitution (constraint_graph_t graph)
2241 unsigned int size = graph->size;
2242 struct scc_info *si = init_scc_info (size);
2244 bitmap_obstack_initialize (&iteration_obstack);
2245 pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
2246 equiv_class_label_eq, free);
2247 location_equiv_class_table = htab_create (511, equiv_class_label_hash,
2248 equiv_class_label_eq, free);
2249 pointer_equiv_class = 1;
2250 location_equiv_class = 1;
2252 /* Condense the nodes, which means to find SCC's, count incoming
2253 predecessors, and unite nodes in SCC's. */
2254 for (i = 0; i < FIRST_REF_NODE; i++)
2255 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2256 condense_visit (graph, si, si->node_mapping[i]);
2258 sbitmap_zero (si->visited);
2259 /* Actually the label the nodes for pointer equivalences */
2260 for (i = 0; i < FIRST_REF_NODE; i++)
2261 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2262 label_visit (graph, si, si->node_mapping[i]);
2264 /* Calculate location equivalence labels. */
2265 for (i = 0; i < FIRST_REF_NODE; i++)
2272 if (!graph->pointed_by[i])
2274 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2276 /* Translate the pointed-by mapping for pointer equivalence
2278 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2280 bitmap_set_bit (pointed_by,
2281 graph->pointer_label[si->node_mapping[j]]);
2283 /* The original pointed_by is now dead. */
2284 BITMAP_FREE (graph->pointed_by[i]);
2286 /* Look up the location equivalence label if one exists, or make
2288 label = equiv_class_lookup (location_equiv_class_table,
2292 label = location_equiv_class++;
2293 equiv_class_add (location_equiv_class_table,
2298 if (dump_file && (dump_flags & TDF_DETAILS))
2299 fprintf (dump_file, "Found location equivalence for node %s\n",
2300 get_varinfo (i)->name);
2301 BITMAP_FREE (pointed_by);
2303 graph->loc_label[i] = label;
2307 if (dump_file && (dump_flags & TDF_DETAILS))
2308 for (i = 0; i < FIRST_REF_NODE; i++)
2310 bool direct_node = TEST_BIT (graph->direct_nodes, i);
2312 "Equivalence classes for %s node id %d:%s are pointer: %d"
2314 direct_node ? "Direct node" : "Indirect node", i,
2315 get_varinfo (i)->name,
2316 graph->pointer_label[si->node_mapping[i]],
2317 graph->loc_label[si->node_mapping[i]]);
2320 /* Quickly eliminate our non-pointer variables. */
2322 for (i = 0; i < FIRST_REF_NODE; i++)
2324 unsigned int node = si->node_mapping[i];
2326 if (graph->pointer_label[node] == 0)
2328 if (dump_file && (dump_flags & TDF_DETAILS))
2330 "%s is a non-pointer variable, eliminating edges.\n",
2331 get_varinfo (node)->name);
2332 stats.nonpointer_vars++;
2333 clear_edges_for_node (graph, node);
2340 /* Free information that was only necessary for variable
2344 free_var_substitution_info (struct scc_info *si)
2347 free (graph->pointer_label);
2348 free (graph->loc_label);
2349 free (graph->pointed_by);
2350 free (graph->points_to);
2351 free (graph->eq_rep);
2352 sbitmap_free (graph->direct_nodes);
2353 htab_delete (pointer_equiv_class_table);
2354 htab_delete (location_equiv_class_table);
2355 bitmap_obstack_release (&iteration_obstack);
2358 /* Return an existing node that is equivalent to NODE, which has
2359 equivalence class LABEL, if one exists. Return NODE otherwise. */
2362 find_equivalent_node (constraint_graph_t graph,
2363 unsigned int node, unsigned int label)
2365 /* If the address version of this variable is unused, we can
2366 substitute it for anything else with the same label.
2367 Otherwise, we know the pointers are equivalent, but not the
2368 locations, and we can unite them later. */
2370 if (!bitmap_bit_p (graph->address_taken, node))
2372 gcc_assert (label < graph->size);
2374 if (graph->eq_rep[label] != -1)
2376 /* Unify the two variables since we know they are equivalent. */
2377 if (unite (graph->eq_rep[label], node))
2378 unify_nodes (graph, graph->eq_rep[label], node, false);
2379 return graph->eq_rep[label];
2383 graph->eq_rep[label] = node;
2384 graph->pe_rep[label] = node;
2389 gcc_assert (label < graph->size);
2390 graph->pe[node] = label;
2391 if (graph->pe_rep[label] == -1)
2392 graph->pe_rep[label] = node;
2398 /* Unite pointer equivalent but not location equivalent nodes in
2399 GRAPH. This may only be performed once variable substitution is
2403 unite_pointer_equivalences (constraint_graph_t graph)
2407 /* Go through the pointer equivalences and unite them to their
2408 representative, if they aren't already. */
2409 for (i = 0; i < FIRST_REF_NODE; i++)
2411 unsigned int label = graph->pe[i];
2414 int label_rep = graph->pe_rep[label];
2416 if (label_rep == -1)
2419 label_rep = find (label_rep);
2420 if (label_rep >= 0 && unite (label_rep, find (i)))
2421 unify_nodes (graph, label_rep, i, false);
2426 /* Move complex constraints to the GRAPH nodes they belong to. */
2429 move_complex_constraints (constraint_graph_t graph)
2434 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2438 struct constraint_expr lhs = c->lhs;
2439 struct constraint_expr rhs = c->rhs;
2441 if (lhs.type == DEREF)
2443 insert_into_complex (graph, lhs.var, c);
2445 else if (rhs.type == DEREF)
2447 if (!(get_varinfo (lhs.var)->is_special_var))
2448 insert_into_complex (graph, rhs.var, c);
2450 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2451 && (lhs.offset != 0 || rhs.offset != 0))
2453 insert_into_complex (graph, rhs.var, c);
2460 /* Optimize and rewrite complex constraints while performing
2461 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2462 result of perform_variable_substitution. */
2465 rewrite_constraints (constraint_graph_t graph,
2466 struct scc_info *si)
2472 for (j = 0; j < graph->size; j++)
2473 gcc_assert (find (j) == j);
2475 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2477 struct constraint_expr lhs = c->lhs;
2478 struct constraint_expr rhs = c->rhs;
2479 unsigned int lhsvar = find (lhs.var);
2480 unsigned int rhsvar = find (rhs.var);
2481 unsigned int lhsnode, rhsnode;
2482 unsigned int lhslabel, rhslabel;
2484 lhsnode = si->node_mapping[lhsvar];
2485 rhsnode = si->node_mapping[rhsvar];
2486 lhslabel = graph->pointer_label[lhsnode];
2487 rhslabel = graph->pointer_label[rhsnode];
2489 /* See if it is really a non-pointer variable, and if so, ignore
2493 if (dump_file && (dump_flags & TDF_DETAILS))
2496 fprintf (dump_file, "%s is a non-pointer variable,"
2497 "ignoring constraint:",
2498 get_varinfo (lhs.var)->name);
2499 dump_constraint (dump_file, c);
2501 VEC_replace (constraint_t, constraints, i, NULL);
2507 if (dump_file && (dump_flags & TDF_DETAILS))
2510 fprintf (dump_file, "%s is a non-pointer variable,"
2511 "ignoring constraint:",
2512 get_varinfo (rhs.var)->name);
2513 dump_constraint (dump_file, c);
2515 VEC_replace (constraint_t, constraints, i, NULL);
2519 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2520 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2521 c->lhs.var = lhsvar;
2522 c->rhs.var = rhsvar;
2527 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2528 part of an SCC, false otherwise. */
2531 eliminate_indirect_cycles (unsigned int node)
2533 if (graph->indirect_cycles[node] != -1
2534 && !bitmap_empty_p (get_varinfo (node)->solution))
2537 VEC(unsigned,heap) *queue = NULL;
2539 unsigned int to = find (graph->indirect_cycles[node]);
2542 /* We can't touch the solution set and call unify_nodes
2543 at the same time, because unify_nodes is going to do
2544 bitmap unions into it. */
2546 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2548 if (find (i) == i && i != to)
2551 VEC_safe_push (unsigned, heap, queue, i);
2556 VEC_iterate (unsigned, queue, queuepos, i);
2559 unify_nodes (graph, to, i, true);
2561 VEC_free (unsigned, heap, queue);
2567 /* Solve the constraint graph GRAPH using our worklist solver.
2568 This is based on the PW* family of solvers from the "Efficient Field
2569 Sensitive Pointer Analysis for C" paper.
2570 It works by iterating over all the graph nodes, processing the complex
2571 constraints and propagating the copy constraints, until everything stops
2572 changed. This corresponds to steps 6-8 in the solving list given above. */
2575 solve_graph (constraint_graph_t graph)
2577 unsigned int size = graph->size;
2582 changed = sbitmap_alloc (size);
2583 sbitmap_zero (changed);
2585 /* Mark all initial non-collapsed nodes as changed. */
2586 for (i = 0; i < size; i++)
2588 varinfo_t ivi = get_varinfo (i);
2589 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2590 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2591 || VEC_length (constraint_t, graph->complex[i]) > 0))
2593 SET_BIT (changed, i);
2598 /* Allocate a bitmap to be used to store the changed bits. */
2599 pts = BITMAP_ALLOC (&pta_obstack);
2601 while (changed_count > 0)
2604 struct topo_info *ti = init_topo_info ();
2607 bitmap_obstack_initialize (&iteration_obstack);
2609 compute_topo_order (graph, ti);
2611 while (VEC_length (unsigned, ti->topo_order) != 0)
2614 i = VEC_pop (unsigned, ti->topo_order);
2616 /* If this variable is not a representative, skip it. */
2620 /* In certain indirect cycle cases, we may merge this
2621 variable to another. */
2622 if (eliminate_indirect_cycles (i) && find (i) != i)
2625 /* If the node has changed, we need to process the
2626 complex constraints and outgoing edges again. */
2627 if (TEST_BIT (changed, i))
2632 VEC(constraint_t,heap) *complex = graph->complex[i];
2633 bool solution_empty;
2635 RESET_BIT (changed, i);
2638 /* Compute the changed set of solution bits. */
2639 bitmap_and_compl (pts, get_varinfo (i)->solution,
2640 get_varinfo (i)->oldsolution);
2642 if (bitmap_empty_p (pts))
2645 bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2647 solution = get_varinfo (i)->solution;
2648 solution_empty = bitmap_empty_p (solution);
2650 /* Process the complex constraints */
2651 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2653 /* XXX: This is going to unsort the constraints in
2654 some cases, which will occasionally add duplicate
2655 constraints during unification. This does not
2656 affect correctness. */
2657 c->lhs.var = find (c->lhs.var);
2658 c->rhs.var = find (c->rhs.var);
2660 /* The only complex constraint that can change our
2661 solution to non-empty, given an empty solution,
2662 is a constraint where the lhs side is receiving
2663 some set from elsewhere. */
2664 if (!solution_empty || c->lhs.type != DEREF)
2665 do_complex_constraint (graph, c, pts);
2668 solution_empty = bitmap_empty_p (solution);
2670 if (!solution_empty)
2673 unsigned eff_escaped_id = find (escaped_id);
2675 /* Propagate solution to all successors. */
2676 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2682 unsigned int to = find (j);
2683 tmp = get_varinfo (to)->solution;
2686 /* Don't try to propagate to ourselves. */
2690 /* If we propagate from ESCAPED use ESCAPED as
2692 if (i == eff_escaped_id)
2693 flag = bitmap_set_bit (tmp, escaped_id);
2695 flag = set_union_with_increment (tmp, pts, 0);
2699 get_varinfo (to)->solution = tmp;
2700 if (!TEST_BIT (changed, to))
2702 SET_BIT (changed, to);
2710 free_topo_info (ti);
2711 bitmap_obstack_release (&iteration_obstack);
2715 sbitmap_free (changed);
2716 bitmap_obstack_release (&oldpta_obstack);
2719 /* Map from trees to variable infos. */
2720 static struct pointer_map_t *vi_for_tree;
2723 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2726 insert_vi_for_tree (tree t, varinfo_t vi)
2728 void **slot = pointer_map_insert (vi_for_tree, t);
2730 gcc_assert (*slot == NULL);
2734 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2735 exist in the map, return NULL, otherwise, return the varinfo we found. */
2738 lookup_vi_for_tree (tree t)
2740 void **slot = pointer_map_contains (vi_for_tree, t);
2744 return (varinfo_t) *slot;
2747 /* Return a printable name for DECL */
2750 alias_get_name (tree decl)
2752 const char *res = get_name (decl);
2754 int num_printed = 0;
2763 if (TREE_CODE (decl) == SSA_NAME)
2765 num_printed = asprintf (&temp, "%s_%u",
2766 alias_get_name (SSA_NAME_VAR (decl)),
2767 SSA_NAME_VERSION (decl));
2769 else if (DECL_P (decl))
2771 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2773 if (num_printed > 0)
2775 res = ggc_strdup (temp);
2781 /* Find the variable id for tree T in the map.
2782 If T doesn't exist in the map, create an entry for it and return it. */
2785 get_vi_for_tree (tree t)
2787 void **slot = pointer_map_contains (vi_for_tree, t);
2789 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2791 return (varinfo_t) *slot;
2794 /* Get a scalar constraint expression for a new temporary variable. */
2796 static struct constraint_expr
2797 new_scalar_tmp_constraint_exp (const char *name)
2799 struct constraint_expr tmp;
2802 vi = new_var_info (NULL_TREE, name);
2806 vi->is_full_var = 1;
2815 /* Get a constraint expression vector from an SSA_VAR_P node.
2816 If address_p is true, the result will be taken its address of. */
2819 get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
2821 struct constraint_expr cexpr;
2824 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2825 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2827 /* For parameters, get at the points-to set for the actual parm
2829 if (TREE_CODE (t) == SSA_NAME
2830 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2831 && SSA_NAME_IS_DEFAULT_DEF (t))
2833 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2837 vi = get_vi_for_tree (t);
2839 cexpr.type = SCALAR;
2841 /* If we determine the result is "anything", and we know this is readonly,
2842 say it points to readonly memory instead. */
2843 if (cexpr.var == anything_id && TREE_READONLY (t))
2846 cexpr.type = ADDRESSOF;
2847 cexpr.var = readonly_id;
2850 /* If we are not taking the address of the constraint expr, add all
2851 sub-fiels of the variable as well. */
2853 && !vi->is_full_var)
2855 for (; vi; vi = vi->next)
2858 VEC_safe_push (ce_s, heap, *results, &cexpr);
2863 VEC_safe_push (ce_s, heap, *results, &cexpr);
2866 /* Process constraint T, performing various simplifications and then
2867 adding it to our list of overall constraints. */
2870 process_constraint (constraint_t t)
2872 struct constraint_expr rhs = t->rhs;
2873 struct constraint_expr lhs = t->lhs;
2875 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2876 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2878 /* If we didn't get any useful constraint from the lhs we get
2879 &ANYTHING as fallback from get_constraint_for. Deal with
2880 it here by turning it into *ANYTHING. */
2881 if (lhs.type == ADDRESSOF
2882 && lhs.var == anything_id)
2885 /* ADDRESSOF on the lhs is invalid. */
2886 gcc_assert (lhs.type != ADDRESSOF);
2888 /* This can happen in our IR with things like n->a = *p */
2889 if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2891 /* Split into tmp = *rhs, *lhs = tmp */
2892 struct constraint_expr tmplhs;
2893 tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp");
2894 process_constraint (new_constraint (tmplhs, rhs));
2895 process_constraint (new_constraint (lhs, tmplhs));
2897 else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
2899 /* Split into tmp = &rhs, *lhs = tmp */
2900 struct constraint_expr tmplhs;
2901 tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp");
2902 process_constraint (new_constraint (tmplhs, rhs));
2903 process_constraint (new_constraint (lhs, tmplhs));
2907 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2908 VEC_safe_push (constraint_t, heap, constraints, t);
2912 /* Return true if T is a type that could contain pointers. */
2915 type_could_have_pointers (tree type)
2917 if (POINTER_TYPE_P (type))
2920 if (TREE_CODE (type) == ARRAY_TYPE)
2921 return type_could_have_pointers (TREE_TYPE (type));
2923 return AGGREGATE_TYPE_P (type);
2926 /* Return true if T is a variable of a type that could contain
2930 could_have_pointers (tree t)
2932 return type_could_have_pointers (TREE_TYPE (t));
2935 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2938 static HOST_WIDE_INT
2939 bitpos_of_field (const tree fdecl)
2942 if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2943 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2946 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2947 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2951 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2952 resulting constraint expressions in *RESULTS. */
2955 get_constraint_for_ptr_offset (tree ptr, tree offset,
2956 VEC (ce_s, heap) **results)
2958 struct constraint_expr c;
2960 HOST_WIDE_INT rhsunitoffset, rhsoffset;
2962 /* If we do not do field-sensitive PTA adding offsets to pointers
2963 does not change the points-to solution. */
2964 if (!use_field_sensitive)
2966 get_constraint_for (ptr, results);
2970 /* If the offset is not a non-negative integer constant that fits
2971 in a HOST_WIDE_INT, we have to fall back to a conservative
2972 solution which includes all sub-fields of all pointed-to
2973 variables of ptr. */
2974 if (offset == NULL_TREE
2975 || !host_integerp (offset, 0))
2976 rhsoffset = UNKNOWN_OFFSET;
2979 /* Make sure the bit-offset also fits. */
2980 rhsunitoffset = TREE_INT_CST_LOW (offset);
2981 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
2982 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
2983 rhsoffset = UNKNOWN_OFFSET;
2986 get_constraint_for (ptr, results);
2990 /* As we are eventually appending to the solution do not use
2991 VEC_iterate here. */
2992 n = VEC_length (ce_s, *results);
2993 for (j = 0; j < n; j++)
2996 c = *VEC_index (ce_s, *results, j);
2997 curr = get_varinfo (c.var);
2999 if (c.type == ADDRESSOF
3000 /* If this varinfo represents a full variable just use it. */
3001 && curr->is_full_var)
3003 else if (c.type == ADDRESSOF
3004 /* If we do not know the offset add all subfields. */
3005 && rhsoffset == UNKNOWN_OFFSET)
3007 varinfo_t temp = lookup_vi_for_tree (curr->decl);
3010 struct constraint_expr c2;
3012 c2.type = ADDRESSOF;
3014 if (c2.var != c.var)
3015 VEC_safe_push (ce_s, heap, *results, &c2);
3020 else if (c.type == ADDRESSOF)
3023 unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
3025 /* Search the sub-field which overlaps with the
3026 pointed-to offset. If the result is outside of the variable
3027 we have to provide a conservative result, as the variable is
3028 still reachable from the resulting pointer (even though it
3029 technically cannot point to anything). The last and first
3030 sub-fields are such conservative results.
3031 ??? If we always had a sub-field for &object + 1 then
3032 we could represent this in a more precise way. */
3034 && curr->offset < offset)
3036 temp = first_or_preceding_vi_for_offset (curr, offset);
3038 /* If the found variable is not exactly at the pointed to
3039 result, we have to include the next variable in the
3040 solution as well. Otherwise two increments by offset / 2
3041 do not result in the same or a conservative superset
3043 if (temp->offset != offset
3044 && temp->next != NULL)
3046 struct constraint_expr c2;
3047 c2.var = temp->next->id;
3048 c2.type = ADDRESSOF;
3050 VEC_safe_push (ce_s, heap, *results, &c2);
3056 c.offset = rhsoffset;
3058 VEC_replace (ce_s, *results, j, &c);
3063 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3064 If address_p is true the result will be taken its address of. */
3067 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
3071 HOST_WIDE_INT bitsize = -1;
3072 HOST_WIDE_INT bitmaxsize = -1;
3073 HOST_WIDE_INT bitpos;
3075 struct constraint_expr *result;
3077 /* Some people like to do cute things like take the address of
3080 while (handled_component_p (forzero)
3081 || INDIRECT_REF_P (forzero))
3082 forzero = TREE_OPERAND (forzero, 0);
3084 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
3086 struct constraint_expr temp;
3089 temp.var = integer_id;
3091 VEC_safe_push (ce_s, heap, *results, &temp);
3095 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
3097 /* Pretend to take the address of the base, we'll take care of
3098 adding the required subset of sub-fields below. */
3099 get_constraint_for_1 (t, results, true);
3100 gcc_assert (VEC_length (ce_s, *results) == 1);
3101 result = VEC_last (ce_s, *results);
3103 if (result->type == SCALAR
3104 && get_varinfo (result->var)->is_full_var)
3105 /* For single-field vars do not bother about the offset. */
3107 else if (result->type == SCALAR)
3109 /* In languages like C, you can access one past the end of an
3110 array. You aren't allowed to dereference it, so we can
3111 ignore this constraint. When we handle pointer subtraction,
3112 we may have to do something cute here. */
3114 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
3117 /* It's also not true that the constraint will actually start at the
3118 right offset, it may start in some padding. We only care about
3119 setting the constraint to the first actual field it touches, so
3121 struct constraint_expr cexpr = *result;
3123 VEC_pop (ce_s, *results);
3125 for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
3127 if (ranges_overlap_p (curr->offset, curr->size,
3128 bitpos, bitmaxsize))
3130 cexpr.var = curr->id;
3131 VEC_safe_push (ce_s, heap, *results, &cexpr);
3136 /* If we are going to take the address of this field then
3137 to be able to compute reachability correctly add at least
3138 the last field of the variable. */
3140 && VEC_length (ce_s, *results) == 0)
3142 curr = get_varinfo (cexpr.var);
3143 while (curr->next != NULL)
3145 cexpr.var = curr->id;
3146 VEC_safe_push (ce_s, heap, *results, &cexpr);
3149 /* Assert that we found *some* field there. The user couldn't be
3150 accessing *only* padding. */
3151 /* Still the user could access one past the end of an array
3152 embedded in a struct resulting in accessing *only* padding. */
3153 gcc_assert (VEC_length (ce_s, *results) >= 1
3154 || ref_contains_array_ref (orig_t));
3156 else if (bitmaxsize == 0)
3158 if (dump_file && (dump_flags & TDF_DETAILS))
3159 fprintf (dump_file, "Access to zero-sized part of variable,"
3163 if (dump_file && (dump_flags & TDF_DETAILS))
3164 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3166 else if (result->type == DEREF)
3168 /* If we do not know exactly where the access goes say so. Note
3169 that only for non-structure accesses we know that we access
3170 at most one subfiled of any variable. */
3172 || bitsize != bitmaxsize
3173 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t)))
3174 result->offset = UNKNOWN_OFFSET;
3176 result->offset = bitpos;
3178 else if (result->type == ADDRESSOF)
3180 /* We can end up here for component references on a
3181 VIEW_CONVERT_EXPR <>(&foobar). */
3182 result->type = SCALAR;
3183 result->var = anything_id;
3191 /* Dereference the constraint expression CONS, and return the result.
3192 DEREF (ADDRESSOF) = SCALAR
3193 DEREF (SCALAR) = DEREF
3194 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3195 This is needed so that we can handle dereferencing DEREF constraints. */
3198 do_deref (VEC (ce_s, heap) **constraints)
3200 struct constraint_expr *c;
3203 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3205 if (c->type == SCALAR)
3207 else if (c->type == ADDRESSOF)
3209 else if (c->type == DEREF)
3211 struct constraint_expr tmplhs;
3212 tmplhs = new_scalar_tmp_constraint_exp ("dereftmp");
3213 process_constraint (new_constraint (tmplhs, *c));
3214 c->var = tmplhs.var;
3221 static void get_constraint_for_1 (tree, VEC (ce_s, heap) **, bool);
3223 /* Given a tree T, return the constraint expression for taking the
3227 get_constraint_for_address_of (tree t, VEC (ce_s, heap) **results)
3229 struct constraint_expr *c;
3232 get_constraint_for_1 (t, results, true);
3234 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3236 if (c->type == DEREF)
3239 c->type = ADDRESSOF;
3243 /* Given a tree T, return the constraint expression for it. */
3246 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3248 struct constraint_expr temp;
3250 /* x = integer is all glommed to a single variable, which doesn't
3251 point to anything by itself. That is, of course, unless it is an
3252 integer constant being treated as a pointer, in which case, we
3253 will return that this is really the addressof anything. This
3254 happens below, since it will fall into the default case. The only
3255 case we know something about an integer treated like a pointer is
3256 when it is the NULL pointer, and then we just say it points to
3259 Do not do that if -fno-delete-null-pointer-checks though, because
3260 in that case *NULL does not fail, so it _should_ alias *anything.
3261 It is not worth adding a new option or renaming the existing one,
3262 since this case is relatively obscure. */
3263 if (flag_delete_null_pointer_checks
3264 && ((TREE_CODE (t) == INTEGER_CST
3265 && integer_zerop (t))
3266 /* The only valid CONSTRUCTORs in gimple with pointer typed
3267 elements are zero-initializer. */
3268 || TREE_CODE (t) == CONSTRUCTOR))
3270 temp.var = nothing_id;
3271 temp.type = ADDRESSOF;
3273 VEC_safe_push (ce_s, heap, *results, &temp);
3277 /* String constants are read-only. */
3278 if (TREE_CODE (t) == STRING_CST)
3280 temp.var = readonly_id;
3283 VEC_safe_push (ce_s, heap, *results, &temp);
3287 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3289 case tcc_expression:
3291 switch (TREE_CODE (t))
3294 get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3302 switch (TREE_CODE (t))
3306 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3311 case ARRAY_RANGE_REF:
3313 get_constraint_for_component_ref (t, results, address_p);
3315 case VIEW_CONVERT_EXPR:
3316 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3318 /* We are missing handling for TARGET_MEM_REF here. */
3323 case tcc_exceptional:
3325 switch (TREE_CODE (t))
3329 get_constraint_for_ssa_var (t, results, address_p);
3336 case tcc_declaration:
3338 get_constraint_for_ssa_var (t, results, address_p);
3344 /* The default fallback is a constraint from anything. */
3345 temp.type = ADDRESSOF;
3346 temp.var = anything_id;
3348 VEC_safe_push (ce_s, heap, *results, &temp);
3351 /* Given a gimple tree T, return the constraint expression vector for it. */
3354 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3356 gcc_assert (VEC_length (ce_s, *results) == 0);
3358 get_constraint_for_1 (t, results, false);
3362 /* Efficiently generates constraints from all entries in *RHSC to all
3363 entries in *LHSC. */
3366 process_all_all_constraints (VEC (ce_s, heap) *lhsc, VEC (ce_s, heap) *rhsc)
3368 struct constraint_expr *lhsp, *rhsp;
3371 if (VEC_length (ce_s, lhsc) <= 1
3372 || VEC_length (ce_s, rhsc) <= 1)
3374 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3375 for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); ++j)
3376 process_constraint (new_constraint (*lhsp, *rhsp));
3380 struct constraint_expr tmp;
3381 tmp = new_scalar_tmp_constraint_exp ("allalltmp");
3382 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
3383 process_constraint (new_constraint (tmp, *rhsp));
3384 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3385 process_constraint (new_constraint (*lhsp, tmp));
3389 /* Handle aggregate copies by expanding into copies of the respective
3390 fields of the structures. */
3393 do_structure_copy (tree lhsop, tree rhsop)
3395 struct constraint_expr *lhsp, *rhsp;
3396 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3399 get_constraint_for (lhsop, &lhsc);
3400 get_constraint_for (rhsop, &rhsc);
3401 lhsp = VEC_index (ce_s, lhsc, 0);
3402 rhsp = VEC_index (ce_s, rhsc, 0);
3403 if (lhsp->type == DEREF
3404 || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3405 || rhsp->type == DEREF)
3407 if (lhsp->type == DEREF)
3409 gcc_assert (VEC_length (ce_s, lhsc) == 1);
3410 lhsp->offset = UNKNOWN_OFFSET;
3412 if (rhsp->type == DEREF)
3414 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3415 rhsp->offset = UNKNOWN_OFFSET;
3417 process_all_all_constraints (lhsc, rhsc);
3419 else if (lhsp->type == SCALAR
3420 && (rhsp->type == SCALAR
3421 || rhsp->type == ADDRESSOF))
3423 HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
3424 HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
3426 get_ref_base_and_extent (lhsop, &lhsoffset, &lhssize, &lhsmaxsize);
3427 get_ref_base_and_extent (rhsop, &rhsoffset, &rhssize, &rhsmaxsize);
3428 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp);)
3430 varinfo_t lhsv, rhsv;
3431 rhsp = VEC_index (ce_s, rhsc, k);
3432 lhsv = get_varinfo (lhsp->var);
3433 rhsv = get_varinfo (rhsp->var);
3434 if (lhsv->may_have_pointers
3435 && ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3436 rhsv->offset + lhsoffset, rhsv->size))
3437 process_constraint (new_constraint (*lhsp, *rhsp));
3438 if (lhsv->offset + rhsoffset + lhsv->size
3439 > rhsv->offset + lhsoffset + rhsv->size)
3442 if (k >= VEC_length (ce_s, rhsc))
3452 VEC_free (ce_s, heap, lhsc);
3453 VEC_free (ce_s, heap, rhsc);
3456 /* Create a constraint ID = OP. */
3459 make_constraint_to (unsigned id, tree op)
3461 VEC(ce_s, heap) *rhsc = NULL;
3462 struct constraint_expr *c;
3463 struct constraint_expr includes;
3467 includes.offset = 0;
3468 includes.type = SCALAR;
3470 get_constraint_for (op, &rhsc);
3471 for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3472 process_constraint (new_constraint (includes, *c));
3473 VEC_free (ce_s, heap, rhsc);
3476 /* Create a constraint ID = &FROM. */
3479 make_constraint_from (varinfo_t vi, int from)
3481 struct constraint_expr lhs, rhs;
3489 rhs.type = ADDRESSOF;
3490 process_constraint (new_constraint (lhs, rhs));
3493 /* Create a constraint ID = FROM. */
3496 make_copy_constraint (varinfo_t vi, int from)
3498 struct constraint_expr lhs, rhs;
3507 process_constraint (new_constraint (lhs, rhs));
3510 /* Make constraints necessary to make OP escape. */
3513 make_escape_constraint (tree op)
3515 make_constraint_to (escaped_id, op);
3518 /* Add constraints to that the solution of VI is transitively closed. */
3521 make_transitive_closure_constraints (varinfo_t vi)
3523 struct constraint_expr lhs, rhs;
3532 process_constraint (new_constraint (lhs, rhs));
3534 /* VAR = VAR + UNKNOWN; */
3540 rhs.offset = UNKNOWN_OFFSET;
3541 process_constraint (new_constraint (lhs, rhs));
3544 /* Create a new artificial heap variable with NAME and make a
3545 constraint from it to LHS. Return the created variable. */
3548 make_constraint_from_heapvar (varinfo_t lhs, const char *name)
3551 tree heapvar = heapvar_lookup (lhs->decl, lhs->offset);
3553 if (heapvar == NULL_TREE)
3556 heapvar = create_tmp_var_raw (ptr_type_node, name);
3557 DECL_EXTERNAL (heapvar) = 1;
3559 heapvar_insert (lhs->decl, lhs->offset, heapvar);
3561 ann = get_var_ann (heapvar);
3562 ann->is_heapvar = 1;
3565 /* For global vars we need to add a heapvar to the list of referenced
3566 vars of a different function than it was created for originally. */
3567 if (cfun && gimple_referenced_vars (cfun))
3568 add_referenced_var (heapvar);
3570 vi = new_var_info (heapvar, name);
3571 vi->is_artificial_var = true;
3572 vi->is_heap_var = true;
3573 vi->is_unknown_size_var = true;
3577 vi->is_full_var = true;
3578 insert_vi_for_tree (heapvar, vi);
3580 make_constraint_from (lhs, vi->id);
3585 /* Create a new artificial heap variable with NAME and make a
3586 constraint from it to LHS. Set flags according to a tag used
3587 for tracking restrict pointers. */
3590 make_constraint_from_restrict (varinfo_t lhs, const char *name)
3593 vi = make_constraint_from_heapvar (lhs, name);
3594 vi->is_restrict_var = 1;
3595 vi->is_global_var = 0;
3596 vi->is_special_var = 1;
3597 vi->may_have_pointers = 0;
3600 /* In IPA mode there are varinfos for different aspects of reach
3601 function designator. One for the points-to set of the return
3602 value, one for the variables that are clobbered by the function,
3603 one for its uses and one for each parameter (including a single
3604 glob for remaining variadic arguments). */
3606 enum { fi_clobbers = 1, fi_uses = 2,
3607 fi_static_chain = 3, fi_result = 4, fi_parm_base = 5 };
3609 /* Get a constraint for the requested part of a function designator FI
3610 when operating in IPA mode. */
3612 static struct constraint_expr
3613 get_function_part_constraint (varinfo_t fi, unsigned part)
3615 struct constraint_expr c;
3617 gcc_assert (in_ipa_mode);
3619 if (fi->id == anything_id)
3621 /* ??? We probably should have a ANYFN special variable. */
3622 c.var = anything_id;
3626 else if (TREE_CODE (fi->decl) == FUNCTION_DECL)
3628 varinfo_t ai = first_vi_for_offset (fi, part);
3629 c.var = ai ? ai->id : anything_id;
3643 /* For non-IPA mode, generate constraints necessary for a call on the
3647 handle_rhs_call (gimple stmt, VEC(ce_s, heap) **results)
3649 struct constraint_expr rhsc;
3652 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3654 tree arg = gimple_call_arg (stmt, i);
3656 /* Find those pointers being passed, and make sure they end up
3657 pointing to anything. */
3658 if (could_have_pointers (arg))
3659 make_escape_constraint (arg);
3662 /* The static chain escapes as well. */
3663 if (gimple_call_chain (stmt))
3664 make_escape_constraint (gimple_call_chain (stmt));
3666 /* And if we applied NRV the address of the return slot escapes as well. */
3667 if (gimple_call_return_slot_opt_p (stmt)
3668 && gimple_call_lhs (stmt) != NULL_TREE
3669 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
3671 VEC(ce_s, heap) *tmpc = NULL;
3672 struct constraint_expr lhsc, *c;
3673 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
3674 lhsc.var = escaped_id;
3677 for (i = 0; VEC_iterate (ce_s, tmpc, i, c); ++i)
3678 process_constraint (new_constraint (lhsc, *c));
3679 VEC_free(ce_s, heap, tmpc);
3682 /* Regular functions return nonlocal memory. */
3683 rhsc.var = nonlocal_id;
3686 VEC_safe_push (ce_s, heap, *results, &rhsc);
3689 /* For non-IPA mode, generate constraints necessary for a call
3690 that returns a pointer and assigns it to LHS. This simply makes
3691 the LHS point to global and escaped variables. */
3694 handle_lhs_call (tree lhs, int flags, VEC(ce_s, heap) *rhsc, tree fndecl)
3696 VEC(ce_s, heap) *lhsc = NULL;
3698 get_constraint_for (lhs, &lhsc);
3700 if (flags & ECF_MALLOC)
3703 vi = make_constraint_from_heapvar (get_vi_for_tree (lhs), "HEAP");
3704 /* We delay marking allocated storage global until we know if
3706 DECL_EXTERNAL (vi->decl) = 0;
3707 vi->is_global_var = 0;
3708 /* If this is not a real malloc call assume the memory was
3709 initialized and thus may point to global memory. All
3710 builtin functions with the malloc attribute behave in a sane way. */
3712 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
3713 make_constraint_from (vi, nonlocal_id);
3715 else if (VEC_length (ce_s, rhsc) > 0)
3717 /* If the store is to a global decl make sure to
3718 add proper escape constraints. */
3719 lhs = get_base_address (lhs);
3722 && is_global_var (lhs))
3724 struct constraint_expr tmpc;
3725 tmpc.var = escaped_id;
3728 VEC_safe_push (ce_s, heap, lhsc, &tmpc);
3730 process_all_all_constraints (lhsc, rhsc);
3732 VEC_free (ce_s, heap, lhsc);
3735 /* For non-IPA mode, generate constraints necessary for a call of a
3736 const function that returns a pointer in the statement STMT. */
3739 handle_const_call (gimple stmt, VEC(ce_s, heap) **results)
3741 struct constraint_expr rhsc;
3744 /* Treat nested const functions the same as pure functions as far
3745 as the static chain is concerned. */
3746 if (gimple_call_chain (stmt))
3748 varinfo_t uses = get_call_use_vi (stmt);
3749 make_transitive_closure_constraints (uses);
3750 make_constraint_to (uses->id, gimple_call_chain (stmt));
3751 rhsc.var = uses->id;
3754 VEC_safe_push (ce_s, heap, *results, &rhsc);
3757 /* May return arguments. */
3758 for (k = 0; k < gimple_call_num_args (stmt); ++k)
3760 tree arg = gimple_call_arg (stmt, k);
3762 if (could_have_pointers (arg))
3764 VEC(ce_s, heap) *argc = NULL;
3766 struct constraint_expr *argp;
3767 get_constraint_for (arg, &argc);
3768 for (i = 0; VEC_iterate (ce_s, argc, i, argp); ++i)
3769 VEC_safe_push (ce_s, heap, *results, argp);
3770 VEC_free(ce_s, heap, argc);
3774 /* May return addresses of globals. */
3775 rhsc.var = nonlocal_id;
3777 rhsc.type = ADDRESSOF;
3778 VEC_safe_push (ce_s, heap, *results, &rhsc);
3781 /* For non-IPA mode, generate constraints necessary for a call to a
3782 pure function in statement STMT. */
3785 handle_pure_call (gimple stmt, VEC(ce_s, heap) **results)
3787 struct constraint_expr rhsc;
3789 varinfo_t uses = NULL;
3791 /* Memory reached from pointer arguments is call-used. */
3792 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3794 tree arg = gimple_call_arg (stmt, i);
3796 if (could_have_pointers (arg))
3800 uses = get_call_use_vi (stmt);
3801 make_transitive_closure_constraints (uses);
3803 make_constraint_to (uses->id, arg);
3807 /* The static chain is used as well. */
3808 if (gimple_call_chain (stmt))
3812 uses = get_call_use_vi (stmt);
3813 make_transitive_closure_constraints (uses);
3815 make_constraint_to (uses->id, gimple_call_chain (stmt));
3818 /* Pure functions may return call-used and nonlocal memory. */
3821 rhsc.var = uses->id;
3824 VEC_safe_push (ce_s, heap, *results, &rhsc);
3826 rhsc.var = nonlocal_id;
3829 VEC_safe_push (ce_s, heap, *results, &rhsc);
3833 /* Return the varinfo for the callee of CALL. */
3836 get_fi_for_callee (gimple call)
3840 /* If we can directly resolve the function being called, do so.
3841 Otherwise, it must be some sort of indirect expression that
3842 we should still be able to handle. */
3843 decl = gimple_call_fndecl (call);
3845 return get_vi_for_tree (decl);
3847 decl = gimple_call_fn (call);
3848 /* The function can be either an SSA name pointer or,
3849 worse, an OBJ_TYPE_REF. In this case we have no
3850 clue and should be getting ANYFN (well, ANYTHING for now). */
3851 if (TREE_CODE (decl) == SSA_NAME)
3853 if (TREE_CODE (decl) == SSA_NAME
3854 && TREE_CODE (SSA_NAME_VAR (decl)) == PARM_DECL
3855 && SSA_NAME_IS_DEFAULT_DEF (decl))
3856 decl = SSA_NAME_VAR (decl);
3857 return get_vi_for_tree (decl);
3859 else if (TREE_CODE (decl) == INTEGER_CST
3860 || TREE_CODE (decl) == OBJ_TYPE_REF)
3861 return get_varinfo (anything_id);
3866 /* Walk statement T setting up aliasing constraints according to the
3867 references found in T. This function is the main part of the
3868 constraint builder. AI points to auxiliary alias information used
3869 when building alias sets and computing alias grouping heuristics. */
3872 find_func_aliases (gimple origt)
3875 VEC(ce_s, heap) *lhsc = NULL;
3876 VEC(ce_s, heap) *rhsc = NULL;
3877 struct constraint_expr *c;
3880 /* Now build constraints expressions. */
3881 if (gimple_code (t) == GIMPLE_PHI)
3883 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (gimple_phi_result (t))));
3885 /* Only care about pointers and structures containing
3887 if (could_have_pointers (gimple_phi_result (t)))
3892 /* For a phi node, assign all the arguments to
3894 get_constraint_for (gimple_phi_result (t), &lhsc);
3895 for (i = 0; i < gimple_phi_num_args (t); i++)
3897 tree strippedrhs = PHI_ARG_DEF (t, i);
3899 STRIP_NOPS (strippedrhs);
3900 get_constraint_for (gimple_phi_arg_def (t, i), &rhsc);
3902 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3904 struct constraint_expr *c2;
3905 while (VEC_length (ce_s, rhsc) > 0)
3907 c2 = VEC_last (ce_s, rhsc);
3908 process_constraint (new_constraint (*c, *c2));
3909 VEC_pop (ce_s, rhsc);
3915 /* In IPA mode, we need to generate constraints to pass call
3916 arguments through their calls. There are two cases,
3917 either a GIMPLE_CALL returning a value, or just a plain
3918 GIMPLE_CALL when we are not.
3920 In non-ipa mode, we need to generate constraints for each
3921 pointer passed by address. */
3922 else if (is_gimple_call (t))
3924 tree fndecl = gimple_call_fndecl (t);
3925 if (fndecl != NULL_TREE
3926 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
3927 /* ??? All builtins that are handled here need to be handled
3928 in the alias-oracle query functions explicitly! */
3929 switch (DECL_FUNCTION_CODE (fndecl))
3931 /* All the following functions return a pointer to the same object
3932 as their first argument points to. The functions do not add
3933 to the ESCAPED solution. The functions make the first argument
3934 pointed to memory point to what the second argument pointed to
3935 memory points to. */
3936 case BUILT_IN_STRCPY:
3937 case BUILT_IN_STRNCPY:
3938 case BUILT_IN_BCOPY:
3939 case BUILT_IN_MEMCPY:
3940 case BUILT_IN_MEMMOVE:
3941 case BUILT_IN_MEMPCPY:
3942 case BUILT_IN_STPCPY:
3943 case BUILT_IN_STPNCPY:
3944 case BUILT_IN_STRCAT:
3945 case BUILT_IN_STRNCAT:
3947 tree res = gimple_call_lhs (t);
3948 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
3949 == BUILT_IN_BCOPY ? 1 : 0));
3950 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
3951 == BUILT_IN_BCOPY ? 0 : 1));
3952 if (res != NULL_TREE)
3954 get_constraint_for (res, &lhsc);
3955 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
3956 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
3957 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY)
3958 get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
3960 get_constraint_for (dest, &rhsc);
3961 process_all_all_constraints (lhsc, rhsc);
3962 VEC_free (ce_s, heap, lhsc);
3963 VEC_free (ce_s, heap, rhsc);
3965 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
3966 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
3969 process_all_all_constraints (lhsc, rhsc);
3970 VEC_free (ce_s, heap, lhsc);
3971 VEC_free (ce_s, heap, rhsc);
3974 case BUILT_IN_MEMSET:
3976 tree res = gimple_call_lhs (t);
3977 tree dest = gimple_call_arg (t, 0);
3980 struct constraint_expr ac;
3981 if (res != NULL_TREE)
3983 get_constraint_for (res, &lhsc);
3984 get_constraint_for (dest, &rhsc);
3985 process_all_all_constraints (lhsc, rhsc);
3986 VEC_free (ce_s, heap, lhsc);
3987 VEC_free (ce_s, heap, rhsc);
3989 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
3991 if (flag_delete_null_pointer_checks
3992 && integer_zerop (gimple_call_arg (t, 1)))
3994 ac.type = ADDRESSOF;
3995 ac.var = nothing_id;
4000 ac.var = integer_id;
4003 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
4004 process_constraint (new_constraint (*lhsp, ac));
4005 VEC_free (ce_s, heap, lhsc);
4008 /* All the following functions do not return pointers, do not
4009 modify the points-to sets of memory reachable from their
4010 arguments and do not add to the ESCAPED solution. */
4011 case BUILT_IN_SINCOS:
4012 case BUILT_IN_SINCOSF:
4013 case BUILT_IN_SINCOSL:
4014 case BUILT_IN_FREXP:
4015 case BUILT_IN_FREXPF:
4016 case BUILT_IN_FREXPL:
4017 case BUILT_IN_GAMMA_R:
4018 case BUILT_IN_GAMMAF_R:
4019 case BUILT_IN_GAMMAL_R:
4020 case BUILT_IN_LGAMMA_R:
4021 case BUILT_IN_LGAMMAF_R:
4022 case BUILT_IN_LGAMMAL_R:
4024 case BUILT_IN_MODFF:
4025 case BUILT_IN_MODFL:
4026 case BUILT_IN_REMQUO:
4027 case BUILT_IN_REMQUOF:
4028 case BUILT_IN_REMQUOL:
4031 /* Trampolines are special - they set up passing the static
4033 case BUILT_IN_INIT_TRAMPOLINE:
4035 tree tramp = gimple_call_arg (t, 0);
4036 tree nfunc = gimple_call_arg (t, 1);
4037 tree frame = gimple_call_arg (t, 2);
4039 struct constraint_expr lhs, *rhsp;
4042 varinfo_t nfi = NULL;
4043 gcc_assert (TREE_CODE (nfunc) == ADDR_EXPR);
4044 nfi = lookup_vi_for_tree (TREE_OPERAND (nfunc, 0));
4047 lhs = get_function_part_constraint (nfi, fi_static_chain);
4048 get_constraint_for (frame, &rhsc);
4049 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
4050 process_constraint (new_constraint (lhs, *rhsp));
4051 VEC_free (ce_s, heap, rhsc);
4053 /* Make the frame point to the function for
4054 the trampoline adjustment call. */
4055 get_constraint_for (tramp, &lhsc);
4057 get_constraint_for (nfunc, &rhsc);
4058 process_all_all_constraints (lhsc, rhsc);
4059 VEC_free (ce_s, heap, rhsc);
4060 VEC_free (ce_s, heap, lhsc);
4065 /* Else fallthru to generic handling which will let
4066 the frame escape. */
4069 case BUILT_IN_ADJUST_TRAMPOLINE:
4071 tree tramp = gimple_call_arg (t, 0);
4072 tree res = gimple_call_lhs (t);
4073 if (in_ipa_mode && res)
4075 get_constraint_for (res, &lhsc);
4076 get_constraint_for (tramp, &rhsc);
4078 process_all_all_constraints (lhsc, rhsc);
4079 VEC_free (ce_s, heap, rhsc);
4080 VEC_free (ce_s, heap, lhsc);
4084 /* Variadic argument handling needs to be handled in IPA
4086 case BUILT_IN_VA_START:
4090 tree valist = gimple_call_arg (t, 0);
4091 struct constraint_expr rhs, *lhsp;
4093 /* The va_list gets access to pointers in variadic
4095 fi = lookup_vi_for_tree (cfun->decl);
4096 gcc_assert (fi != NULL);
4097 get_constraint_for (valist, &lhsc);
4099 rhs = get_function_part_constraint (fi, ~0);
4100 rhs.type = ADDRESSOF;
4101 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
4102 process_constraint (new_constraint (*lhsp, rhs));
4103 VEC_free (ce_s, heap, lhsc);
4104 /* va_list is clobbered. */
4105 make_constraint_to (get_call_clobber_vi (t)->id, valist);
4110 /* va_end doesn't have any effect that matters. */
4111 case BUILT_IN_VA_END:
4113 /* printf-style functions may have hooks to set pointers to
4114 point to somewhere into the generated string. Leave them
4115 for a later excercise... */
4117 /* Fallthru to general call handling. */;
4121 && (!(fi = lookup_vi_for_tree (fndecl))
4122 || !fi->is_fn_info)))
4124 VEC(ce_s, heap) *rhsc = NULL;
4125 int flags = gimple_call_flags (t);
4127 /* Const functions can return their arguments and addresses
4128 of global memory but not of escaped memory. */
4129 if (flags & (ECF_CONST|ECF_NOVOPS))
4131 if (gimple_call_lhs (t)
4132 && could_have_pointers (gimple_call_lhs (t)))
4133 handle_const_call (t, &rhsc);
4135 /* Pure functions can return addresses in and of memory
4136 reachable from their arguments, but they are not an escape
4137 point for reachable memory of their arguments. */
4138 else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE))
4139 handle_pure_call (t, &rhsc);
4141 handle_rhs_call (t, &rhsc);
4142 if (gimple_call_lhs (t)
4143 && could_have_pointers (gimple_call_lhs (t)))
4144 handle_lhs_call (gimple_call_lhs (t), flags, rhsc, fndecl);
4145 VEC_free (ce_s, heap, rhsc);
4152 fi = get_fi_for_callee (t);
4154 /* Assign all the passed arguments to the appropriate incoming
4155 parameters of the function. */
4156 for (j = 0; j < gimple_call_num_args (t); j++)
4158 struct constraint_expr lhs ;
4159 struct constraint_expr *rhsp;
4160 tree arg = gimple_call_arg (t, j);
4162 if (!could_have_pointers (arg))
4165 get_constraint_for (arg, &rhsc);
4166 lhs = get_function_part_constraint (fi, fi_parm_base + j);
4167 while (VEC_length (ce_s, rhsc) != 0)
4169 rhsp = VEC_last (ce_s, rhsc);
4170 process_constraint (new_constraint (lhs, *rhsp));
4171 VEC_pop (ce_s, rhsc);
4175 /* If we are returning a value, assign it to the result. */
4176 lhsop = gimple_call_lhs (t);
4178 && could_have_pointers (lhsop))
4180 struct constraint_expr rhs;
4181 struct constraint_expr *lhsp;
4183 get_constraint_for (lhsop, &lhsc);
4184 rhs = get_function_part_constraint (fi, fi_result);
4186 && DECL_RESULT (fndecl)
4187 && DECL_BY_REFERENCE (DECL_RESULT (fndecl)))
4189 VEC(ce_s, heap) *tem = NULL;
4190 VEC_safe_push (ce_s, heap, tem, &rhs);
4192 rhs = *VEC_index (ce_s, tem, 0);
4193 VEC_free(ce_s, heap, tem);
4195 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
4196 process_constraint (new_constraint (*lhsp, rhs));
4199 /* If we pass the result decl by reference, honor that. */
4202 && DECL_RESULT (fndecl)
4203 && DECL_BY_REFERENCE (DECL_RESULT (fndecl)))
4205 struct constraint_expr lhs;
4206 struct constraint_expr *rhsp;
4208 get_constraint_for_address_of (lhsop, &rhsc);
4209 lhs = get_function_part_constraint (fi, fi_result);
4210 for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); j++)
4211 process_constraint (new_constraint (lhs, *rhsp));
4212 VEC_free (ce_s, heap, rhsc);
4215 /* If we use a static chain, pass it along. */
4216 if (gimple_call_chain (t))
4218 struct constraint_expr lhs;
4219 struct constraint_expr *rhsp;
4221 get_constraint_for (gimple_call_chain (t), &rhsc);
4222 lhs = get_function_part_constraint (fi, fi_static_chain);
4223 for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); j++)
4224 process_constraint (new_constraint (lhs, *rhsp));
4228 /* Otherwise, just a regular assignment statement. Only care about
4229 operations with pointer result, others are dealt with as escape
4230 points if they have pointer operands. */
4231 else if (is_gimple_assign (t)
4232 && could_have_pointers (gimple_assign_lhs (t)))
4234 /* Otherwise, just a regular assignment statement. */
4235 tree lhsop = gimple_assign_lhs (t);
4236 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
4238 if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
4239 do_structure_copy (lhsop, rhsop);
4242 struct constraint_expr temp;
4243 get_constraint_for (lhsop, &lhsc);
4245 if (gimple_assign_rhs_code (t) == POINTER_PLUS_EXPR)
4246 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4247 gimple_assign_rhs2 (t), &rhsc);
4248 else if ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
4249 && !(POINTER_TYPE_P (gimple_expr_type (t))
4250 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
4251 || gimple_assign_single_p (t))
4252 get_constraint_for (rhsop, &rhsc);
4255 temp.type = ADDRESSOF;
4256 temp.var = anything_id;
4258 VEC_safe_push (ce_s, heap, rhsc, &temp);
4260 process_all_all_constraints (lhsc, rhsc);
4262 /* If there is a store to a global variable the rhs escapes. */
4263 if ((lhsop = get_base_address (lhsop)) != NULL_TREE
4265 && is_global_var (lhsop)
4267 || DECL_EXTERNAL (lhsop) || TREE_PUBLIC (lhsop)))
4268 make_escape_constraint (rhsop);
4269 /* If this is a conversion of a non-restrict pointer to a
4270 restrict pointer track it with a new heapvar. */
4271 else if (gimple_assign_cast_p (t)
4272 && POINTER_TYPE_P (TREE_TYPE (rhsop))
4273 && POINTER_TYPE_P (TREE_TYPE (lhsop))
4274 && !TYPE_RESTRICT (TREE_TYPE (rhsop))
4275 && TYPE_RESTRICT (TREE_TYPE (lhsop)))
4276 make_constraint_from_restrict (get_vi_for_tree (lhsop),
4279 /* For conversions of pointers to non-pointers the pointer escapes. */
4280 else if (gimple_assign_cast_p (t)
4281 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (t)))
4282 && !POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (t))))
4284 make_escape_constraint (gimple_assign_rhs1 (t));
4286 /* Handle escapes through return. */
4287 else if (gimple_code (t) == GIMPLE_RETURN
4288 && gimple_return_retval (t) != NULL_TREE
4289 && could_have_pointers (gimple_return_retval (t)))
4293 || !(fi = get_vi_for_tree (cfun->decl)))
4294 make_escape_constraint (gimple_return_retval (t));
4295 else if (in_ipa_mode
4298 struct constraint_expr lhs ;
4299 struct constraint_expr *rhsp;
4302 lhs = get_function_part_constraint (fi, fi_result);
4303 get_constraint_for (gimple_return_retval (t), &rhsc);
4304 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); i++)
4305 process_constraint (new_constraint (lhs, *rhsp));
4308 /* Handle asms conservatively by adding escape constraints to everything. */
4309 else if (gimple_code (t) == GIMPLE_ASM)
4311 unsigned i, noutputs;
4312 const char **oconstraints;
4313 const char *constraint;
4314 bool allows_mem, allows_reg, is_inout;
4316 noutputs = gimple_asm_noutputs (t);
4317 oconstraints = XALLOCAVEC (const char *, noutputs);
4319 for (i = 0; i < noutputs; ++i)
4321 tree link = gimple_asm_output_op (t, i);
4322 tree op = TREE_VALUE (link);
4324 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4325 oconstraints[i] = constraint;
4326 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
4327 &allows_reg, &is_inout);
4329 /* A memory constraint makes the address of the operand escape. */
4330 if (!allows_reg && allows_mem)
4331 make_escape_constraint (build_fold_addr_expr (op));
4333 /* The asm may read global memory, so outputs may point to
4334 any global memory. */
4335 if (op && could_have_pointers (op))
4337 VEC(ce_s, heap) *lhsc = NULL;
4338 struct constraint_expr rhsc, *lhsp;
4340 get_constraint_for (op, &lhsc);
4341 rhsc.var = nonlocal_id;
4344 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
4345 process_constraint (new_constraint (*lhsp, rhsc));
4346 VEC_free (ce_s, heap, lhsc);
4349 for (i = 0; i < gimple_asm_ninputs (t); ++i)
4351 tree link = gimple_asm_input_op (t, i);
4352 tree op = TREE_VALUE (link);
4354 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4356 parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
4357 &allows_mem, &allows_reg);
4359 /* A memory constraint makes the address of the operand escape. */
4360 if (!allows_reg && allows_mem)
4361 make_escape_constraint (build_fold_addr_expr (op));
4362 /* Strictly we'd only need the constraint to ESCAPED if
4363 the asm clobbers memory, otherwise using something
4364 along the lines of per-call clobbers/uses would be enough. */
4365 else if (op && could_have_pointers (op))
4366 make_escape_constraint (op);
4370 VEC_free (ce_s, heap, rhsc);
4371 VEC_free (ce_s, heap, lhsc);
4375 /* Create a constraint adding to the clobber set of FI the memory
4376 pointed to by PTR. */
4379 process_ipa_clobber (varinfo_t fi, tree ptr)
4381 VEC(ce_s, heap) *ptrc = NULL;
4382 struct constraint_expr *c, lhs;
4384 get_constraint_for (ptr, &ptrc);
4385 lhs = get_function_part_constraint (fi, fi_clobbers);
4386 for (i = 0; VEC_iterate (ce_s, ptrc, i, c); i++)
4387 process_constraint (new_constraint (lhs, *c));
4388 VEC_free (ce_s, heap, ptrc);
4391 /* Walk statement T setting up clobber and use constraints according to the
4392 references found in T. This function is a main part of the
4393 IPA constraint builder. */
4396 find_func_clobbers (gimple origt)
4399 VEC(ce_s, heap) *lhsc = NULL;
4400 VEC(ce_s, heap) *rhsc = NULL;
4403 /* Add constraints for clobbered/used in IPA mode.
4404 We are not interested in what automatic variables are clobbered
4405 or used as we only use the information in the caller to which
4406 they do not escape. */
4407 gcc_assert (in_ipa_mode);
4409 /* If the stmt refers to memory in any way it better had a VUSE. */
4410 if (gimple_vuse (t) == NULL_TREE)
4413 /* We'd better have function information for the current function. */
4414 fi = lookup_vi_for_tree (cfun->decl);
4415 gcc_assert (fi != NULL);
4417 /* Account for stores in assignments and calls. */
4418 if (gimple_vdef (t) != NULL_TREE
4419 && gimple_has_lhs (t))
4421 tree lhs = gimple_get_lhs (t);
4423 while (handled_component_p (tem))
4424 tem = TREE_OPERAND (tem, 0);
4426 && !auto_var_in_fn_p (tem, cfun->decl))
4427 || INDIRECT_REF_P (tem))
4429 struct constraint_expr lhsc, *rhsp;
4431 lhsc = get_function_part_constraint (fi, fi_clobbers);
4432 get_constraint_for_address_of (lhs, &rhsc);
4433 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); i++)
4434 process_constraint (new_constraint (lhsc, *rhsp));
4435 VEC_free (ce_s, heap, rhsc);
4439 /* Account for uses in assigments and returns. */
4440 if (gimple_assign_single_p (t)
4441 || (gimple_code (t) == GIMPLE_RETURN
4442 && gimple_return_retval (t) != NULL_TREE))
4444 tree rhs = (gimple_assign_single_p (t)
4445 ? gimple_assign_rhs1 (t) : gimple_return_retval (t));
4447 while (handled_component_p (tem))
4448 tem = TREE_OPERAND (tem, 0);
4450 && !auto_var_in_fn_p (tem, cfun->decl))
4451 || INDIRECT_REF_P (tem))
4453 struct constraint_expr lhs, *rhsp;
4455 lhs = get_function_part_constraint (fi, fi_uses);
4456 get_constraint_for_address_of (rhs, &rhsc);
4457 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); i++)
4458 process_constraint (new_constraint (lhs, *rhsp));
4459 VEC_free (ce_s, heap, rhsc);
4463 if (is_gimple_call (t))
4465 varinfo_t cfi = NULL;
4466 tree decl = gimple_call_fndecl (t);
4467 struct constraint_expr lhs, rhs;
4470 /* For builtins we do not have separate function info. For those
4471 we do not generate escapes for we have to generate clobbers/uses. */
4473 && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
4474 switch (DECL_FUNCTION_CODE (decl))
4476 /* The following functions use and clobber memory pointed to
4477 by their arguments. */
4478 case BUILT_IN_STRCPY:
4479 case BUILT_IN_STRNCPY:
4480 case BUILT_IN_BCOPY:
4481 case BUILT_IN_MEMCPY:
4482 case BUILT_IN_MEMMOVE:
4483 case BUILT_IN_MEMPCPY:
4484 case BUILT_IN_STPCPY:
4485 case BUILT_IN_STPNCPY:
4486 case BUILT_IN_STRCAT:
4487 case BUILT_IN_STRNCAT:
4489 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
4490 == BUILT_IN_BCOPY ? 1 : 0));
4491 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
4492 == BUILT_IN_BCOPY ? 0 : 1));
4494 struct constraint_expr *rhsp, *lhsp;
4495 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4496 lhs = get_function_part_constraint (fi, fi_clobbers);
4497 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); i++)
4498 process_constraint (new_constraint (lhs, *lhsp));
4499 VEC_free (ce_s, heap, lhsc);
4500 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4501 lhs = get_function_part_constraint (fi, fi_uses);
4502 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); i++)
4503 process_constraint (new_constraint (lhs, *rhsp));
4504 VEC_free (ce_s, heap, rhsc);
4507 /* The following function clobbers memory pointed to by
4509 case BUILT_IN_MEMSET:
4511 tree dest = gimple_call_arg (t, 0);
4514 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4515 lhs = get_function_part_constraint (fi, fi_clobbers);
4516 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); i++)
4517 process_constraint (new_constraint (lhs, *lhsp));
4518 VEC_free (ce_s, heap, lhsc);
4521 /* The following functions clobber their second and third
4523 case BUILT_IN_SINCOS:
4524 case BUILT_IN_SINCOSF:
4525 case BUILT_IN_SINCOSL:
4527 process_ipa_clobber (fi, gimple_call_arg (t, 1));
4528 process_ipa_clobber (fi, gimple_call_arg (t, 2));
4531 /* The following functions clobber their second argument. */
4532 case BUILT_IN_FREXP:
4533 case BUILT_IN_FREXPF:
4534 case BUILT_IN_FREXPL:
4535 case BUILT_IN_LGAMMA_R:
4536 case BUILT_IN_LGAMMAF_R:
4537 case BUILT_IN_LGAMMAL_R:
4538 case BUILT_IN_GAMMA_R:
4539 case BUILT_IN_GAMMAF_R:
4540 case BUILT_IN_GAMMAL_R:
4542 case BUILT_IN_MODFF:
4543 case BUILT_IN_MODFL:
4545 process_ipa_clobber (fi, gimple_call_arg (t, 1));
4548 /* The following functions clobber their third argument. */
4549 case BUILT_IN_REMQUO:
4550 case BUILT_IN_REMQUOF:
4551 case BUILT_IN_REMQUOL:
4553 process_ipa_clobber (fi, gimple_call_arg (t, 2));
4556 /* The following functions neither read nor clobber memory. */
4559 /* Trampolines are of no interest to us. */
4560 case BUILT_IN_INIT_TRAMPOLINE:
4561 case BUILT_IN_ADJUST_TRAMPOLINE:
4563 case BUILT_IN_VA_START:
4564 case BUILT_IN_VA_END:
4566 /* printf-style functions may have hooks to set pointers to
4567 point to somewhere into the generated string. Leave them
4568 for a later excercise... */
4570 /* Fallthru to general call handling. */;
4573 /* Parameters passed by value are used. */
4574 lhs = get_function_part_constraint (fi, fi_uses);
4575 for (i = 0; i < gimple_call_num_args (t); i++)
4577 struct constraint_expr *rhsp;
4578 tree arg = gimple_call_arg (t, i);
4580 if (TREE_CODE (arg) == SSA_NAME
4581 || is_gimple_min_invariant (arg))
4584 get_constraint_for_address_of (arg, &rhsc);
4585 for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); j++)
4586 process_constraint (new_constraint (lhs, *rhsp));
4587 VEC_free (ce_s, heap, rhsc);
4590 /* Build constraints for propagating clobbers/uses along the
4592 cfi = get_fi_for_callee (t);
4593 if (cfi->id == anything_id)
4595 if (gimple_vdef (t))
4596 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
4598 make_constraint_from (first_vi_for_offset (fi, fi_uses),
4603 /* For callees without function info (that's external functions),
4604 ESCAPED is clobbered and used. */
4605 if (gimple_call_fndecl (t)
4606 && !cfi->is_fn_info)
4610 if (gimple_vdef (t))
4611 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
4613 make_copy_constraint (first_vi_for_offset (fi, fi_uses), escaped_id);
4615 /* Also honor the call statement use/clobber info. */
4616 if ((vi = lookup_call_clobber_vi (t)) != NULL)
4617 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
4619 if ((vi = lookup_call_use_vi (t)) != NULL)
4620 make_copy_constraint (first_vi_for_offset (fi, fi_uses),
4625 /* Otherwise the caller clobbers and uses what the callee does.
4626 ??? This should use a new complex constraint that filters
4627 local variables of the callee. */
4628 if (gimple_vdef (t))
4630 lhs = get_function_part_constraint (fi, fi_clobbers);
4631 rhs = get_function_part_constraint (cfi, fi_clobbers);
4632 process_constraint (new_constraint (lhs, rhs));
4634 lhs = get_function_part_constraint (fi, fi_uses);
4635 rhs = get_function_part_constraint (cfi, fi_uses);
4636 process_constraint (new_constraint (lhs, rhs));
4638 else if (gimple_code (t) == GIMPLE_ASM)
4640 /* ??? Ick. We can do better. */
4641 if (gimple_vdef (t))
4642 make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
4644 make_constraint_from (first_vi_for_offset (fi, fi_uses),
4648 VEC_free (ce_s, heap, rhsc);
4652 /* Find the first varinfo in the same variable as START that overlaps with
4653 OFFSET. Return NULL if we can't find one. */
4656 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
4658 /* If the offset is outside of the variable, bail out. */
4659 if (offset >= start->fullsize)
4662 /* If we cannot reach offset from start, lookup the first field
4663 and start from there. */
4664 if (start->offset > offset)
4665 start = lookup_vi_for_tree (start->decl);
4669 /* We may not find a variable in the field list with the actual
4670 offset when when we have glommed a structure to a variable.
4671 In that case, however, offset should still be within the size
4673 if (offset >= start->offset
4674 && (offset - start->offset) < start->size)
4683 /* Find the first varinfo in the same variable as START that overlaps with
4684 OFFSET. If there is no such varinfo the varinfo directly preceding
4685 OFFSET is returned. */
4688 first_or_preceding_vi_for_offset (varinfo_t start,
4689 unsigned HOST_WIDE_INT offset)
4691 /* If we cannot reach offset from start, lookup the first field
4692 and start from there. */
4693 if (start->offset > offset)
4694 start = lookup_vi_for_tree (start->decl);
4696 /* We may not find a variable in the field list with the actual
4697 offset when when we have glommed a structure to a variable.
4698 In that case, however, offset should still be within the size
4700 If we got beyond the offset we look for return the field
4701 directly preceding offset which may be the last field. */
4703 && offset >= start->offset
4704 && !((offset - start->offset) < start->size))
4705 start = start->next;
4711 /* Insert the varinfo FIELD into the field list for BASE, at the front
4715 insert_into_field_list (varinfo_t base, varinfo_t field)
4717 varinfo_t prev = base;
4718 varinfo_t curr = base->next;
4724 /* This structure is used during pushing fields onto the fieldstack
4725 to track the offset of the field, since bitpos_of_field gives it
4726 relative to its immediate containing type, and we want it relative
4727 to the ultimate containing object. */
4731 /* Offset from the base of the base containing object to this field. */
4732 HOST_WIDE_INT offset;
4734 /* Size, in bits, of the field. */
4735 unsigned HOST_WIDE_INT size;
4737 unsigned has_unknown_size : 1;
4739 unsigned may_have_pointers : 1;
4741 unsigned only_restrict_pointers : 1;
4743 typedef struct fieldoff fieldoff_s;
4745 DEF_VEC_O(fieldoff_s);
4746 DEF_VEC_ALLOC_O(fieldoff_s,heap);
4748 /* qsort comparison function for two fieldoff's PA and PB */
4751 fieldoff_compare (const void *pa, const void *pb)
4753 const fieldoff_s *foa = (const fieldoff_s *)pa;
4754 const fieldoff_s *fob = (const fieldoff_s *)pb;
4755 unsigned HOST_WIDE_INT foasize, fobsize;
4757 if (foa->offset < fob->offset)
4759 else if (foa->offset > fob->offset)
4762 foasize = foa->size;
4763 fobsize = fob->size;
4764 if (foasize < fobsize)
4766 else if (foasize > fobsize)
4771 /* Sort a fieldstack according to the field offset and sizes. */
4773 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
4775 qsort (VEC_address (fieldoff_s, fieldstack),
4776 VEC_length (fieldoff_s, fieldstack),
4777 sizeof (fieldoff_s),
4781 /* Return true if V is a tree that we can have subvars for.
4782 Normally, this is any aggregate type. Also complex
4783 types which are not gimple registers can have subvars. */
4786 var_can_have_subvars (const_tree v)
4788 /* Volatile variables should never have subvars. */
4789 if (TREE_THIS_VOLATILE (v))
4792 /* Non decls or memory tags can never have subvars. */
4796 /* Aggregates without overlapping fields can have subvars. */
4797 if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
4803 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4804 the fields of TYPE onto fieldstack, recording their offsets along
4807 OFFSET is used to keep track of the offset in this entire
4808 structure, rather than just the immediately containing structure.
4809 Returns the number of fields pushed. */
4812 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
4813 HOST_WIDE_INT offset)
4818 if (TREE_CODE (type) != RECORD_TYPE)
4821 /* If the vector of fields is growing too big, bail out early.
4822 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4824 if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
4827 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
4828 if (TREE_CODE (field) == FIELD_DECL)
4832 HOST_WIDE_INT foff = bitpos_of_field (field);
4834 if (!var_can_have_subvars (field)
4835 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
4836 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
4838 else if (!(pushed = push_fields_onto_fieldstack
4839 (TREE_TYPE (field), fieldstack, offset + foff))
4840 && (DECL_SIZE (field)
4841 && !integer_zerop (DECL_SIZE (field))))
4842 /* Empty structures may have actual size, like in C++. So
4843 see if we didn't push any subfields and the size is
4844 nonzero, push the field onto the stack. */
4849 fieldoff_s *pair = NULL;
4850 bool has_unknown_size = false;
4852 if (!VEC_empty (fieldoff_s, *fieldstack))
4853 pair = VEC_last (fieldoff_s, *fieldstack);
4855 if (!DECL_SIZE (field)
4856 || !host_integerp (DECL_SIZE (field), 1))
4857 has_unknown_size = true;
4859 /* If adjacent fields do not contain pointers merge them. */
4861 && !pair->may_have_pointers
4862 && !could_have_pointers (field)
4863 && !pair->has_unknown_size
4864 && !has_unknown_size
4865 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
4867 pair = VEC_last (fieldoff_s, *fieldstack);
4868 pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
4872 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
4873 pair->offset = offset + foff;
4874 pair->has_unknown_size = has_unknown_size;
4875 if (!has_unknown_size)
4876 pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
4879 pair->may_have_pointers = could_have_pointers (field);
4880 pair->only_restrict_pointers
4881 = (!has_unknown_size
4882 && POINTER_TYPE_P (TREE_TYPE (field))
4883 && TYPE_RESTRICT (TREE_TYPE (field)));
4894 /* Count the number of arguments DECL has, and set IS_VARARGS to true
4895 if it is a varargs function. */
4898 count_num_arguments (tree decl, bool *is_varargs)
4900 unsigned int num = 0;
4903 /* Capture named arguments for K&R functions. They do not
4904 have a prototype and thus no TYPE_ARG_TYPES. */
4905 for (t = DECL_ARGUMENTS (decl); t; t = TREE_CHAIN (t))
4908 /* Check if the function has variadic arguments. */
4909 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); t; t = TREE_CHAIN (t))
4910 if (TREE_VALUE (t) == void_type_node)
4918 /* Creation function node for DECL, using NAME, and return the index
4919 of the variable we've created for the function. */
4922 create_function_info_for (tree decl, const char *name)
4924 struct function *fn = DECL_STRUCT_FUNCTION (decl);
4925 varinfo_t vi, prev_vi;
4928 bool is_varargs = false;
4929 unsigned int num_args = count_num_arguments (decl, &is_varargs);
4931 /* Create the variable info. */
4933 vi = new_var_info (decl, name);
4936 vi->fullsize = fi_parm_base + num_args;
4938 vi->may_have_pointers = false;
4941 insert_vi_for_tree (vi->decl, vi);
4947 /* Create a variable for things the function clobbers and one for
4948 things the function uses. */
4950 varinfo_t clobbervi, usevi;
4951 const char *newname;
4954 asprintf (&tempname, "%s.clobber", name);
4955 newname = ggc_strdup (tempname);
4958 clobbervi = new_var_info (NULL, newname);
4959 clobbervi->offset = fi_clobbers;
4960 clobbervi->size = 1;
4961 clobbervi->fullsize = vi->fullsize;
4962 clobbervi->is_full_var = true;
4963 clobbervi->is_global_var = false;
4964 gcc_assert (prev_vi->offset < clobbervi->offset);
4965 prev_vi->next = clobbervi;
4966 prev_vi = clobbervi;
4969 asprintf (&tempname, "%s.use", name);
4970 newname = ggc_strdup (tempname);
4973 usevi = new_var_info (NULL, newname);
4974 usevi->offset = fi_uses;
4976 usevi->fullsize = vi->fullsize;
4977 usevi->is_full_var = true;
4978 usevi->is_global_var = false;
4979 gcc_assert (prev_vi->offset < usevi->offset);
4980 prev_vi->next = usevi;
4985 /* And one for the static chain. */
4986 if (fn->static_chain_decl != NULL_TREE)
4989 const char *newname;
4992 asprintf (&tempname, "%s.chain", name);
4993 newname = ggc_strdup (tempname);
4996 chainvi = new_var_info (fn->static_chain_decl, newname);
4997 chainvi->offset = fi_static_chain;
4999 chainvi->fullsize = vi->fullsize;
5000 chainvi->is_full_var = true;
5001 chainvi->is_global_var = false;
5002 gcc_assert (prev_vi->offset < chainvi->offset);
5003 prev_vi->next = chainvi;
5006 insert_vi_for_tree (fn->static_chain_decl, chainvi);
5009 /* Create a variable for the return var. */
5010 if (DECL_RESULT (decl) != NULL
5011 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
5014 const char *newname;
5016 tree resultdecl = decl;
5018 if (DECL_RESULT (decl))
5019 resultdecl = DECL_RESULT (decl);
5021 asprintf (&tempname, "%s.result", name);
5022 newname = ggc_strdup (tempname);
5025 resultvi = new_var_info (resultdecl, newname);
5026 resultvi->offset = fi_result;
5028 resultvi->fullsize = vi->fullsize;
5029 resultvi->is_full_var = true;
5030 if (DECL_RESULT (decl))
5031 resultvi->may_have_pointers = could_have_pointers (DECL_RESULT (decl));
5032 gcc_assert (prev_vi->offset < resultvi->offset);
5033 prev_vi->next = resultvi;
5036 if (DECL_RESULT (decl))
5037 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
5040 /* Set up variables for each argument. */
5041 arg = DECL_ARGUMENTS (decl);
5042 for (i = 0; i < num_args; i++)
5045 const char *newname;
5047 tree argdecl = decl;
5052 asprintf (&tempname, "%s.arg%d", name, i);
5053 newname = ggc_strdup (tempname);
5056 argvi = new_var_info (argdecl, newname);
5057 argvi->offset = fi_parm_base + i;
5059 argvi->is_full_var = true;
5060 argvi->fullsize = vi->fullsize;
5062 argvi->may_have_pointers = could_have_pointers (arg);
5063 gcc_assert (prev_vi->offset < argvi->offset);
5064 prev_vi->next = argvi;
5069 insert_vi_for_tree (arg, argvi);
5070 arg = TREE_CHAIN (arg);
5074 /* Add one representative for all further args. */
5078 const char *newname;
5082 asprintf (&tempname, "%s.varargs", name);
5083 newname = ggc_strdup (tempname);
5086 /* We need sth that can be pointed to for va_start. */
5087 decl = create_tmp_var_raw (ptr_type_node, name);
5090 argvi = new_var_info (decl, newname);
5091 argvi->offset = fi_parm_base + num_args;
5093 argvi->is_full_var = true;
5094 argvi->is_heap_var = true;
5095 argvi->fullsize = vi->fullsize;
5096 gcc_assert (prev_vi->offset < argvi->offset);
5097 prev_vi->next = argvi;
5106 /* Return true if FIELDSTACK contains fields that overlap.
5107 FIELDSTACK is assumed to be sorted by offset. */
5110 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
5112 fieldoff_s *fo = NULL;
5114 HOST_WIDE_INT lastoffset = -1;
5116 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
5118 if (fo->offset == lastoffset)
5120 lastoffset = fo->offset;
5125 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
5126 This will also create any varinfo structures necessary for fields
5130 create_variable_info_for (tree decl, const char *name)
5133 tree decl_type = TREE_TYPE (decl);
5134 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
5135 VEC (fieldoff_s,heap) *fieldstack = NULL;
5137 if (var_can_have_subvars (decl) && use_field_sensitive)
5138 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
5140 /* If the variable doesn't have subvars, we may end up needing to
5141 sort the field list and create fake variables for all the
5143 vi = new_var_info (decl, name);
5145 vi->may_have_pointers = could_have_pointers (decl);
5147 || !host_integerp (declsize, 1))
5149 vi->is_unknown_size_var = true;
5155 vi->fullsize = TREE_INT_CST_LOW (declsize);
5156 vi->size = vi->fullsize;
5159 insert_vi_for_tree (vi->decl, vi);
5161 /* ??? The setting of vi->may_have_pointers is too conservative here
5162 and may get refined below. Thus we have superfluous constraints
5163 here sometimes which triggers the commented assert in
5164 dump_sa_points_to_info. */
5165 if (vi->is_global_var
5166 && vi->may_have_pointers)
5168 /* Mark global restrict qualified pointers. */
5169 if (POINTER_TYPE_P (TREE_TYPE (decl))
5170 && TYPE_RESTRICT (TREE_TYPE (decl)))
5171 make_constraint_from_restrict (vi, "GLOBAL_RESTRICT");
5173 /* For escaped variables initialize them from nonlocal. */
5175 || DECL_EXTERNAL (decl) || TREE_PUBLIC (decl))
5176 make_copy_constraint (vi, nonlocal_id);
5178 /* If this is a global variable with an initializer and we are in
5179 IPA mode generate constraints for it. In non-IPA mode
5180 the initializer from nonlocal is all we need. */
5182 && DECL_INITIAL (vi->decl))
5184 VEC (ce_s, heap) *rhsc = NULL;
5185 struct constraint_expr lhs, *rhsp;
5187 get_constraint_for (DECL_INITIAL (vi->decl), &rhsc);
5191 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
5192 process_constraint (new_constraint (lhs, *rhsp));
5193 /* If this is a variable that escapes from the unit
5194 the initializer escapes as well. */
5195 if (DECL_EXTERNAL (decl) || TREE_PUBLIC (decl))
5197 lhs.var = escaped_id;
5200 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
5201 process_constraint (new_constraint (lhs, *rhsp));
5203 VEC_free (ce_s, heap, rhsc);
5204 /* ??? Force us to not use subfields. Else we'd have to parse
5205 arbitrary initializers. */
5206 VEC_free (fieldoff_s, heap, fieldstack);
5211 if (use_field_sensitive
5212 && !vi->is_unknown_size_var
5213 && var_can_have_subvars (decl)
5214 && VEC_length (fieldoff_s, fieldstack) > 1
5215 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
5217 fieldoff_s *fo = NULL;
5218 bool notokay = false;
5221 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
5223 if (fo->has_unknown_size
5231 /* We can't sort them if we have a field with a variable sized type,
5232 which will make notokay = true. In that case, we are going to return
5233 without creating varinfos for the fields anyway, so sorting them is a
5237 sort_fieldstack (fieldstack);
5238 /* Due to some C++ FE issues, like PR 22488, we might end up
5239 what appear to be overlapping fields even though they,
5240 in reality, do not overlap. Until the C++ FE is fixed,
5241 we will simply disable field-sensitivity for these cases. */
5242 notokay = check_for_overlaps (fieldstack);
5246 if (VEC_length (fieldoff_s, fieldstack) != 0)
5247 fo = VEC_index (fieldoff_s, fieldstack, 0);
5249 if (fo == NULL || notokay)
5251 vi->is_unknown_size_var = 1;
5254 vi->is_full_var = true;
5255 VEC_free (fieldoff_s, heap, fieldstack);
5259 vi->size = fo->size;
5260 vi->offset = fo->offset;
5261 vi->may_have_pointers = fo->may_have_pointers;
5262 if (vi->is_global_var
5263 && vi->may_have_pointers)
5265 if (fo->only_restrict_pointers)
5266 make_constraint_from_restrict (vi, "GLOBAL_RESTRICT");
5268 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
5269 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
5273 const char *newname = "NULL";
5278 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
5279 "+" HOST_WIDE_INT_PRINT_DEC,
5280 vi->name, fo->offset, fo->size);
5281 newname = ggc_strdup (tempname);
5284 newvi = new_var_info (decl, newname);
5285 newvi->offset = fo->offset;
5286 newvi->size = fo->size;
5287 newvi->fullsize = vi->fullsize;
5288 newvi->may_have_pointers = fo->may_have_pointers;
5289 insert_into_field_list (vi, newvi);
5290 if ((newvi->is_global_var || TREE_CODE (decl) == PARM_DECL)
5291 && newvi->may_have_pointers)
5293 if (fo->only_restrict_pointers)
5294 make_constraint_from_restrict (newvi, "GLOBAL_RESTRICT");
5295 if (newvi->is_global_var && !in_ipa_mode)
5296 make_copy_constraint (newvi, nonlocal_id);
5303 vi->is_full_var = true;
5305 VEC_free (fieldoff_s, heap, fieldstack);
5310 /* Print out the points-to solution for VAR to FILE. */
5313 dump_solution_for_var (FILE *file, unsigned int var)
5315 varinfo_t vi = get_varinfo (var);
5319 /* Dump the solution for unified vars anyway, this avoids difficulties
5320 in scanning dumps in the testsuite. */
5321 fprintf (file, "%s = { ", vi->name);
5322 vi = get_varinfo (find (var));
5323 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
5324 fprintf (file, "%s ", get_varinfo (i)->name);
5325 fprintf (file, "}");
5327 /* But note when the variable was unified. */
5329 fprintf (file, " same as %s", vi->name);
5331 fprintf (file, "\n");
5334 /* Print the points-to solution for VAR to stdout. */
5337 debug_solution_for_var (unsigned int var)
5339 dump_solution_for_var (stdout, var);
5342 /* Create varinfo structures for all of the variables in the
5343 function for intraprocedural mode. */
5346 intra_create_variable_infos (void)
5350 /* For each incoming pointer argument arg, create the constraint ARG
5351 = NONLOCAL or a dummy variable if it is a restrict qualified
5352 passed-by-reference argument. */
5353 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
5357 if (!could_have_pointers (t))
5360 /* For restrict qualified pointers to objects passed by
5361 reference build a real representative for the pointed-to object. */
5362 if (DECL_BY_REFERENCE (t)
5363 && POINTER_TYPE_P (TREE_TYPE (t))
5364 && TYPE_RESTRICT (TREE_TYPE (t)))
5366 struct constraint_expr lhsc, rhsc;
5368 tree heapvar = heapvar_lookup (t, 0);
5369 if (heapvar == NULL_TREE)
5372 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
5374 DECL_EXTERNAL (heapvar) = 1;
5375 heapvar_insert (t, 0, heapvar);
5376 ann = get_var_ann (heapvar);
5377 ann->is_heapvar = 1;
5379 if (gimple_referenced_vars (cfun))
5380 add_referenced_var (heapvar);
5381 lhsc.var = get_vi_for_tree (t)->id;
5384 rhsc.var = (vi = get_vi_for_tree (heapvar))->id;
5385 rhsc.type = ADDRESSOF;
5387 process_constraint (new_constraint (lhsc, rhsc));
5388 vi->is_restrict_var = 1;
5392 for (p = get_vi_for_tree (t); p; p = p->next)
5393 if (p->may_have_pointers)
5394 make_constraint_from (p, nonlocal_id);
5395 if (POINTER_TYPE_P (TREE_TYPE (t))
5396 && TYPE_RESTRICT (TREE_TYPE (t)))
5397 make_constraint_from_restrict (get_vi_for_tree (t), "PARM_RESTRICT");
5400 /* Add a constraint for a result decl that is passed by reference. */
5401 if (DECL_RESULT (cfun->decl)
5402 && DECL_BY_REFERENCE (DECL_RESULT (cfun->decl)))
5404 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
5406 for (p = result_vi; p; p = p->next)
5407 make_constraint_from (p, nonlocal_id);
5410 /* Add a constraint for the incoming static chain parameter. */
5411 if (cfun->static_chain_decl != NULL_TREE)
5413 varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
5415 for (p = chain_vi; p; p = p->next)
5416 make_constraint_from (p, nonlocal_id);
5420 /* Structure used to put solution bitmaps in a hashtable so they can
5421 be shared among variables with the same points-to set. */
5423 typedef struct shared_bitmap_info
5427 } *shared_bitmap_info_t;
5428 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
5430 static htab_t shared_bitmap_table;
5432 /* Hash function for a shared_bitmap_info_t */
5435 shared_bitmap_hash (const void *p)
5437 const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
5438 return bi->hashcode;
5441 /* Equality function for two shared_bitmap_info_t's. */
5444 shared_bitmap_eq (const void *p1, const void *p2)
5446 const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
5447 const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
5448 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
5451 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
5452 existing instance if there is one, NULL otherwise. */
5455 shared_bitmap_lookup (bitmap pt_vars)
5458 struct shared_bitmap_info sbi;
5460 sbi.pt_vars = pt_vars;
5461 sbi.hashcode = bitmap_hash (pt_vars);
5463 slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
5464 sbi.hashcode, NO_INSERT);
5468 return ((shared_bitmap_info_t) *slot)->pt_vars;
5472 /* Add a bitmap to the shared bitmap hashtable. */
5475 shared_bitmap_add (bitmap pt_vars)
5478 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
5480 sbi->pt_vars = pt_vars;
5481 sbi->hashcode = bitmap_hash (pt_vars);
5483 slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
5484 sbi->hashcode, INSERT);
5485 gcc_assert (!*slot);
5486 *slot = (void *) sbi;
5490 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
5493 set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt)
5498 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
5500 varinfo_t vi = get_varinfo (i);
5502 /* The only artificial variables that are allowed in a may-alias
5503 set are heap variables. */
5504 if (vi->is_artificial_var && !vi->is_heap_var)
5507 if (TREE_CODE (vi->decl) == VAR_DECL
5508 || TREE_CODE (vi->decl) == PARM_DECL
5509 || TREE_CODE (vi->decl) == RESULT_DECL)
5511 /* If we are in IPA mode we will not recompute points-to
5512 sets after inlining so make sure they stay valid. */
5514 && !DECL_PT_UID_SET_P (vi->decl))
5515 SET_DECL_PT_UID (vi->decl, DECL_UID (vi->decl));
5517 /* Add the decl to the points-to set. Note that the points-to
5518 set contains global variables. */
5519 bitmap_set_bit (into, DECL_PT_UID (vi->decl));
5520 if (vi->is_global_var)
5521 pt->vars_contains_global = true;
5527 /* Compute the points-to solution *PT for the variable VI. */
5530 find_what_var_points_to (varinfo_t orig_vi, struct pt_solution *pt)
5534 bitmap finished_solution;
5538 memset (pt, 0, sizeof (struct pt_solution));
5540 /* This variable may have been collapsed, let's get the real
5542 vi = get_varinfo (find (orig_vi->id));
5544 /* Translate artificial variables into SSA_NAME_PTR_INFO
5546 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
5548 varinfo_t vi = get_varinfo (i);
5550 if (vi->is_artificial_var)
5552 if (vi->id == nothing_id)
5554 else if (vi->id == escaped_id)
5557 pt->ipa_escaped = 1;
5561 else if (vi->id == nonlocal_id)
5563 else if (vi->is_heap_var)
5564 /* We represent heapvars in the points-to set properly. */
5566 else if (vi->id == readonly_id)
5569 else if (vi->id == anything_id
5570 || vi->id == integer_id)
5573 if (vi->is_restrict_var)
5574 pt->vars_contains_restrict = true;
5577 /* Instead of doing extra work, simply do not create
5578 elaborate points-to information for pt_anything pointers. */
5580 && (orig_vi->is_artificial_var
5581 || !pt->vars_contains_restrict))
5584 /* Share the final set of variables when possible. */
5585 finished_solution = BITMAP_GGC_ALLOC ();
5586 stats.points_to_sets_created++;
5588 set_uids_in_ptset (finished_solution, vi->solution, pt);
5589 result = shared_bitmap_lookup (finished_solution);
5592 shared_bitmap_add (finished_solution);
5593 pt->vars = finished_solution;
5598 bitmap_clear (finished_solution);
5602 /* Given a pointer variable P, fill in its points-to set. */
5605 find_what_p_points_to (tree p)
5607 struct ptr_info_def *pi;
5611 /* For parameters, get at the points-to set for the actual parm
5613 if (TREE_CODE (p) == SSA_NAME
5614 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
5615 && SSA_NAME_IS_DEFAULT_DEF (p))
5616 lookup_p = SSA_NAME_VAR (p);
5618 vi = lookup_vi_for_tree (lookup_p);
5622 pi = get_ptr_info (p);
5623 find_what_var_points_to (vi, &pi->pt);
5627 /* Query statistics for points-to solutions. */
5630 unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
5631 unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
5632 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
5633 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
5637 dump_pta_stats (FILE *s)
5639 fprintf (s, "\nPTA query stats:\n");
5640 fprintf (s, " pt_solution_includes: "
5641 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
5642 HOST_WIDE_INT_PRINT_DEC" queries\n",
5643 pta_stats.pt_solution_includes_no_alias,
5644 pta_stats.pt_solution_includes_no_alias
5645 + pta_stats.pt_solution_includes_may_alias);
5646 fprintf (s, " pt_solutions_intersect: "
5647 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
5648 HOST_WIDE_INT_PRINT_DEC" queries\n",
5649 pta_stats.pt_solutions_intersect_no_alias,
5650 pta_stats.pt_solutions_intersect_no_alias
5651 + pta_stats.pt_solutions_intersect_may_alias);
5655 /* Reset the points-to solution *PT to a conservative default
5656 (point to anything). */
5659 pt_solution_reset (struct pt_solution *pt)
5661 memset (pt, 0, sizeof (struct pt_solution));
5662 pt->anything = true;
5665 /* Set the points-to solution *PT to point only to the variables
5666 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
5667 global variables and VARS_CONTAINS_RESTRICT specifies whether
5668 it contains restrict tag variables. */
5671 pt_solution_set (struct pt_solution *pt, bitmap vars,
5672 bool vars_contains_global, bool vars_contains_restrict)
5674 memset (pt, 0, sizeof (struct pt_solution));
5676 pt->vars_contains_global = vars_contains_global;
5677 pt->vars_contains_restrict = vars_contains_restrict;
5680 /* Computes the union of the points-to solutions *DEST and *SRC and
5681 stores the result in *DEST. This changes the points-to bitmap
5682 of *DEST and thus may not be used if that might be shared.
5683 The points-to bitmap of *SRC and *DEST will not be shared after
5684 this function if they were not before. */
5687 pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src)
5689 dest->anything |= src->anything;
5692 pt_solution_reset (dest);
5696 dest->nonlocal |= src->nonlocal;
5697 dest->escaped |= src->escaped;
5698 dest->ipa_escaped |= src->ipa_escaped;
5699 dest->null |= src->null;
5700 dest->vars_contains_global |= src->vars_contains_global;
5701 dest->vars_contains_restrict |= src->vars_contains_restrict;
5706 dest->vars = BITMAP_GGC_ALLOC ();
5707 bitmap_ior_into (dest->vars, src->vars);
5710 /* Return true if the points-to solution *PT is empty. */
5713 pt_solution_empty_p (struct pt_solution *pt)
5720 && !bitmap_empty_p (pt->vars))
5723 /* If the solution includes ESCAPED, check if that is empty. */
5725 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
5728 /* If the solution includes ESCAPED, check if that is empty. */
5730 && !pt_solution_empty_p (&ipa_escaped_pt))
5736 /* Return true if the points-to solution *PT includes global memory. */
5739 pt_solution_includes_global (struct pt_solution *pt)
5743 || pt->vars_contains_global)
5747 return pt_solution_includes_global (&cfun->gimple_df->escaped);
5749 if (pt->ipa_escaped)
5750 return pt_solution_includes_global (&ipa_escaped_pt);
5752 /* ??? This predicate is not correct for the IPA-PTA solution
5753 as we do not properly distinguish between unit escape points
5754 and global variables. */
5755 if (cfun->gimple_df->ipa_pta)
5761 /* Return true if the points-to solution *PT includes the variable
5762 declaration DECL. */
5765 pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
5771 && is_global_var (decl))
5775 && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
5778 /* If the solution includes ESCAPED, check it. */
5780 && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
5783 /* If the solution includes ESCAPED, check it. */
5785 && pt_solution_includes_1 (&ipa_escaped_pt, decl))
5792 pt_solution_includes (struct pt_solution *pt, const_tree decl)
5794 bool res = pt_solution_includes_1 (pt, decl);
5796 ++pta_stats.pt_solution_includes_may_alias;
5798 ++pta_stats.pt_solution_includes_no_alias;
5802 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
5806 pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
5808 if (pt1->anything || pt2->anything)
5811 /* If either points to unknown global memory and the other points to
5812 any global memory they alias. */
5815 || pt2->vars_contains_global))
5817 && pt1->vars_contains_global))
5820 /* Check the escaped solution if required. */
5821 if ((pt1->escaped || pt2->escaped)
5822 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
5824 /* If both point to escaped memory and that solution
5825 is not empty they alias. */
5826 if (pt1->escaped && pt2->escaped)
5829 /* If either points to escaped memory see if the escaped solution
5830 intersects with the other. */
5832 && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt2))
5834 && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt1)))
5838 /* Check the escaped solution if required.
5839 ??? Do we need to check the local against the IPA escaped sets? */
5840 if ((pt1->ipa_escaped || pt2->ipa_escaped)
5841 && !pt_solution_empty_p (&ipa_escaped_pt))
5843 /* If both point to escaped memory and that solution
5844 is not empty they alias. */
5845 if (pt1->ipa_escaped && pt2->ipa_escaped)
5848 /* If either points to escaped memory see if the escaped solution
5849 intersects with the other. */
5850 if ((pt1->ipa_escaped
5851 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
5852 || (pt2->ipa_escaped
5853 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
5857 /* Now both pointers alias if their points-to solution intersects. */
5860 && bitmap_intersect_p (pt1->vars, pt2->vars));
5864 pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
5866 bool res = pt_solutions_intersect_1 (pt1, pt2);
5868 ++pta_stats.pt_solutions_intersect_may_alias;
5870 ++pta_stats.pt_solutions_intersect_no_alias;
5874 /* Return true if both points-to solutions PT1 and PT2 for two restrict
5875 qualified pointers are possibly based on the same pointer. */
5878 pt_solutions_same_restrict_base (struct pt_solution *pt1,
5879 struct pt_solution *pt2)
5881 /* If we deal with points-to solutions of two restrict qualified
5882 pointers solely rely on the pointed-to variable bitmap intersection.
5883 For two pointers that are based on each other the bitmaps will
5885 if (pt1->vars_contains_restrict
5886 && pt2->vars_contains_restrict)
5888 gcc_assert (pt1->vars && pt2->vars);
5889 return bitmap_intersect_p (pt1->vars, pt2->vars);
5896 /* Dump points-to information to OUTFILE. */
5899 dump_sa_points_to_info (FILE *outfile)
5903 fprintf (outfile, "\nPoints-to sets\n\n");
5905 if (dump_flags & TDF_STATS)
5907 fprintf (outfile, "Stats:\n");
5908 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
5909 fprintf (outfile, "Non-pointer vars: %d\n",
5910 stats.nonpointer_vars);
5911 fprintf (outfile, "Statically unified vars: %d\n",
5912 stats.unified_vars_static);
5913 fprintf (outfile, "Dynamically unified vars: %d\n",
5914 stats.unified_vars_dynamic);
5915 fprintf (outfile, "Iterations: %d\n", stats.iterations);
5916 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
5917 fprintf (outfile, "Number of implicit edges: %d\n",
5918 stats.num_implicit_edges);
5921 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
5923 varinfo_t vi = get_varinfo (i);
5924 if (!vi->may_have_pointers)
5926 dump_solution_for_var (outfile, i);
5931 /* Debug points-to information to stderr. */
5934 debug_sa_points_to_info (void)
5936 dump_sa_points_to_info (stderr);
5940 /* Initialize the always-existing constraint variables for NULL
5941 ANYTHING, READONLY, and INTEGER */
5944 init_base_vars (void)
5946 struct constraint_expr lhs, rhs;
5947 varinfo_t var_anything;
5948 varinfo_t var_nothing;
5949 varinfo_t var_readonly;
5950 varinfo_t var_escaped;
5951 varinfo_t var_nonlocal;
5952 varinfo_t var_storedanything;
5953 varinfo_t var_integer;
5955 /* Create the NULL variable, used to represent that a variable points
5957 var_nothing = new_var_info (NULL_TREE, "NULL");
5958 gcc_assert (var_nothing->id == nothing_id);
5959 var_nothing->is_artificial_var = 1;
5960 var_nothing->offset = 0;
5961 var_nothing->size = ~0;
5962 var_nothing->fullsize = ~0;
5963 var_nothing->is_special_var = 1;
5964 var_nothing->may_have_pointers = 0;
5965 var_nothing->is_global_var = 0;
5967 /* Create the ANYTHING variable, used to represent that a variable
5968 points to some unknown piece of memory. */
5969 var_anything = new_var_info (NULL_TREE, "ANYTHING");
5970 gcc_assert (var_anything->id == anything_id);
5971 var_anything->is_artificial_var = 1;
5972 var_anything->size = ~0;
5973 var_anything->offset = 0;
5974 var_anything->next = NULL;
5975 var_anything->fullsize = ~0;
5976 var_anything->is_special_var = 1;
5978 /* Anything points to anything. This makes deref constraints just
5979 work in the presence of linked list and other p = *p type loops,
5980 by saying that *ANYTHING = ANYTHING. */
5982 lhs.var = anything_id;
5984 rhs.type = ADDRESSOF;
5985 rhs.var = anything_id;
5988 /* This specifically does not use process_constraint because
5989 process_constraint ignores all anything = anything constraints, since all
5990 but this one are redundant. */
5991 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
5993 /* Create the READONLY variable, used to represent that a variable
5994 points to readonly memory. */
5995 var_readonly = new_var_info (NULL_TREE, "READONLY");
5996 gcc_assert (var_readonly->id == readonly_id);
5997 var_readonly->is_artificial_var = 1;
5998 var_readonly->offset = 0;
5999 var_readonly->size = ~0;
6000 var_readonly->fullsize = ~0;
6001 var_readonly->next = NULL;
6002 var_readonly->is_special_var = 1;
6004 /* readonly memory points to anything, in order to make deref
6005 easier. In reality, it points to anything the particular
6006 readonly variable can point to, but we don't track this
6009 lhs.var = readonly_id;
6011 rhs.type = ADDRESSOF;
6012 rhs.var = readonly_id; /* FIXME */
6014 process_constraint (new_constraint (lhs, rhs));
6016 /* Create the ESCAPED variable, used to represent the set of escaped
6018 var_escaped = new_var_info (NULL_TREE, "ESCAPED");
6019 gcc_assert (var_escaped->id == escaped_id);
6020 var_escaped->is_artificial_var = 1;
6021 var_escaped->offset = 0;
6022 var_escaped->size = ~0;
6023 var_escaped->fullsize = ~0;
6024 var_escaped->is_special_var = 0;
6026 /* Create the NONLOCAL variable, used to represent the set of nonlocal
6028 var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL");
6029 gcc_assert (var_nonlocal->id == nonlocal_id);
6030 var_nonlocal->is_artificial_var = 1;
6031 var_nonlocal->offset = 0;
6032 var_nonlocal->size = ~0;
6033 var_nonlocal->fullsize = ~0;
6034 var_nonlocal->is_special_var = 1;
6036 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
6038 lhs.var = escaped_id;
6041 rhs.var = escaped_id;
6043 process_constraint (new_constraint (lhs, rhs));
6045 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
6046 whole variable escapes. */
6048 lhs.var = escaped_id;
6051 rhs.var = escaped_id;
6052 rhs.offset = UNKNOWN_OFFSET;
6053 process_constraint (new_constraint (lhs, rhs));
6055 /* *ESCAPED = NONLOCAL. This is true because we have to assume
6056 everything pointed to by escaped points to what global memory can
6059 lhs.var = escaped_id;
6062 rhs.var = nonlocal_id;
6064 process_constraint (new_constraint (lhs, rhs));
6066 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
6067 global memory may point to global memory and escaped memory. */
6069 lhs.var = nonlocal_id;
6071 rhs.type = ADDRESSOF;
6072 rhs.var = nonlocal_id;
6074 process_constraint (new_constraint (lhs, rhs));
6075 rhs.type = ADDRESSOF;
6076 rhs.var = escaped_id;
6078 process_constraint (new_constraint (lhs, rhs));
6080 /* Create the STOREDANYTHING variable, used to represent the set of
6081 variables stored to *ANYTHING. */
6082 var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING");
6083 gcc_assert (var_storedanything->id == storedanything_id);
6084 var_storedanything->is_artificial_var = 1;
6085 var_storedanything->offset = 0;
6086 var_storedanything->size = ~0;
6087 var_storedanything->fullsize = ~0;
6088 var_storedanything->is_special_var = 0;
6090 /* Create the INTEGER variable, used to represent that a variable points
6091 to what an INTEGER "points to". */
6092 var_integer = new_var_info (NULL_TREE, "INTEGER");
6093 gcc_assert (var_integer->id == integer_id);
6094 var_integer->is_artificial_var = 1;
6095 var_integer->size = ~0;
6096 var_integer->fullsize = ~0;
6097 var_integer->offset = 0;
6098 var_integer->next = NULL;
6099 var_integer->is_special_var = 1;
6101 /* INTEGER = ANYTHING, because we don't know where a dereference of
6102 a random integer will point to. */
6104 lhs.var = integer_id;
6106 rhs.type = ADDRESSOF;
6107 rhs.var = anything_id;
6109 process_constraint (new_constraint (lhs, rhs));
6112 /* Initialize things necessary to perform PTA */
6115 init_alias_vars (void)
6117 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
6119 bitmap_obstack_initialize (&pta_obstack);
6120 bitmap_obstack_initialize (&oldpta_obstack);
6121 bitmap_obstack_initialize (&predbitmap_obstack);
6123 constraint_pool = create_alloc_pool ("Constraint pool",
6124 sizeof (struct constraint), 30);
6125 variable_info_pool = create_alloc_pool ("Variable info pool",
6126 sizeof (struct variable_info), 30);
6127 constraints = VEC_alloc (constraint_t, heap, 8);
6128 varmap = VEC_alloc (varinfo_t, heap, 8);
6129 vi_for_tree = pointer_map_create ();
6130 call_stmt_vars = pointer_map_create ();
6132 memset (&stats, 0, sizeof (stats));
6133 shared_bitmap_table = htab_create (511, shared_bitmap_hash,
6134 shared_bitmap_eq, free);
6138 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
6139 predecessor edges. */
6142 remove_preds_and_fake_succs (constraint_graph_t graph)
6146 /* Clear the implicit ref and address nodes from the successor
6148 for (i = 0; i < FIRST_REF_NODE; i++)
6150 if (graph->succs[i])
6151 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
6152 FIRST_REF_NODE * 2);
6155 /* Free the successor list for the non-ref nodes. */
6156 for (i = FIRST_REF_NODE; i < graph->size; i++)
6158 if (graph->succs[i])
6159 BITMAP_FREE (graph->succs[i]);
6162 /* Now reallocate the size of the successor list as, and blow away
6163 the predecessor bitmaps. */
6164 graph->size = VEC_length (varinfo_t, varmap);
6165 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
6167 free (graph->implicit_preds);
6168 graph->implicit_preds = NULL;
6169 free (graph->preds);
6170 graph->preds = NULL;
6171 bitmap_obstack_release (&predbitmap_obstack);
6174 /* Initialize the heapvar for statement mapping. */
6177 init_alias_heapvars (void)
6179 if (!heapvar_for_stmt)
6180 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, heapvar_map_eq,
6184 /* Delete the heapvar for statement mapping. */
6187 delete_alias_heapvars (void)
6189 if (heapvar_for_stmt)
6190 htab_delete (heapvar_for_stmt);
6191 heapvar_for_stmt = NULL;
6194 /* Solve the constraint set. */
6197 solve_constraints (void)
6199 struct scc_info *si;
6203 "\nCollapsing static cycles and doing variable "
6206 init_graph (VEC_length (varinfo_t, varmap) * 2);
6209 fprintf (dump_file, "Building predecessor graph\n");
6210 build_pred_graph ();
6213 fprintf (dump_file, "Detecting pointer and location "
6215 si = perform_var_substitution (graph);
6218 fprintf (dump_file, "Rewriting constraints and unifying "
6220 rewrite_constraints (graph, si);
6222 build_succ_graph ();
6223 free_var_substitution_info (si);
6225 if (dump_file && (dump_flags & TDF_GRAPH))
6226 dump_constraint_graph (dump_file);
6228 move_complex_constraints (graph);
6231 fprintf (dump_file, "Uniting pointer but not location equivalent "
6233 unite_pointer_equivalences (graph);
6236 fprintf (dump_file, "Finding indirect cycles\n");
6237 find_indirect_cycles (graph);
6239 /* Implicit nodes and predecessors are no longer necessary at this
6241 remove_preds_and_fake_succs (graph);
6244 fprintf (dump_file, "Solving graph\n");
6246 solve_graph (graph);
6249 dump_sa_points_to_info (dump_file);
6252 /* Create points-to sets for the current function. See the comments
6253 at the start of the file for an algorithmic overview. */
6256 compute_points_to_sets (void)
6262 timevar_push (TV_TREE_PTA);
6265 init_alias_heapvars ();
6267 intra_create_variable_infos ();
6269 /* Now walk all statements and build the constraint set. */
6272 gimple_stmt_iterator gsi;
6274 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6276 gimple phi = gsi_stmt (gsi);
6278 if (is_gimple_reg (gimple_phi_result (phi)))
6279 find_func_aliases (phi);
6282 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6284 gimple stmt = gsi_stmt (gsi);
6286 find_func_aliases (stmt);
6292 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
6293 dump_constraints (dump_file, 0);
6296 /* From the constraints compute the points-to sets. */
6297 solve_constraints ();
6299 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
6300 find_what_var_points_to (get_varinfo (escaped_id),
6301 &cfun->gimple_df->escaped);
6303 /* Make sure the ESCAPED solution (which is used as placeholder in
6304 other solutions) does not reference itself. This simplifies
6305 points-to solution queries. */
6306 cfun->gimple_df->escaped.escaped = 0;
6308 /* Mark escaped HEAP variables as global. */
6309 for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); ++i)
6311 && !vi->is_restrict_var
6312 && !vi->is_global_var)
6313 DECL_EXTERNAL (vi->decl) = vi->is_global_var
6314 = pt_solution_includes (&cfun->gimple_df->escaped, vi->decl);
6316 /* Compute the points-to sets for pointer SSA_NAMEs. */
6317 for (i = 0; i < num_ssa_names; ++i)
6319 tree ptr = ssa_name (i);
6321 && POINTER_TYPE_P (TREE_TYPE (ptr)))
6322 find_what_p_points_to (ptr);
6325 /* Compute the call-used/clobbered sets. */
6328 gimple_stmt_iterator gsi;
6330 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6332 gimple stmt = gsi_stmt (gsi);
6333 struct pt_solution *pt;
6334 if (!is_gimple_call (stmt))
6337 pt = gimple_call_use_set (stmt);
6338 if (gimple_call_flags (stmt) & ECF_CONST)
6339 memset (pt, 0, sizeof (struct pt_solution));
6340 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
6342 find_what_var_points_to (vi, pt);
6343 /* Escaped (and thus nonlocal) variables are always
6344 implicitly used by calls. */
6345 /* ??? ESCAPED can be empty even though NONLOCAL
6352 /* If there is nothing special about this call then
6353 we have made everything that is used also escape. */
6354 *pt = cfun->gimple_df->escaped;
6358 pt = gimple_call_clobber_set (stmt);
6359 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
6360 memset (pt, 0, sizeof (struct pt_solution));
6361 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
6363 find_what_var_points_to (vi, pt);
6364 /* Escaped (and thus nonlocal) variables are always
6365 implicitly clobbered by calls. */
6366 /* ??? ESCAPED can be empty even though NONLOCAL
6373 /* If there is nothing special about this call then
6374 we have made everything that is used also escape. */
6375 *pt = cfun->gimple_df->escaped;
6381 timevar_pop (TV_TREE_PTA);
6385 /* Delete created points-to sets. */
6388 delete_points_to_sets (void)
6392 htab_delete (shared_bitmap_table);
6393 if (dump_file && (dump_flags & TDF_STATS))
6394 fprintf (dump_file, "Points to sets created:%d\n",
6395 stats.points_to_sets_created);
6397 pointer_map_destroy (vi_for_tree);
6398 pointer_map_destroy (call_stmt_vars);
6399 bitmap_obstack_release (&pta_obstack);
6400 VEC_free (constraint_t, heap, constraints);
6402 for (i = 0; i < graph->size; i++)
6403 VEC_free (constraint_t, heap, graph->complex[i]);
6404 free (graph->complex);
6407 free (graph->succs);
6409 free (graph->pe_rep);
6410 free (graph->indirect_cycles);
6413 VEC_free (varinfo_t, heap, varmap);
6414 free_alloc_pool (variable_info_pool);
6415 free_alloc_pool (constraint_pool);
6419 /* Compute points-to information for every SSA_NAME pointer in the
6420 current function and compute the transitive closure of escaped
6421 variables to re-initialize the call-clobber states of local variables. */
6424 compute_may_aliases (void)
6426 if (cfun->gimple_df->ipa_pta)
6430 fprintf (dump_file, "\nNot re-computing points-to information "
6431 "because IPA points-to information is available.\n\n");
6433 /* But still dump what we have remaining it. */
6434 dump_alias_info (dump_file);
6436 if (dump_flags & TDF_DETAILS)
6437 dump_referenced_vars (dump_file);
6443 /* For each pointer P_i, determine the sets of variables that P_i may
6444 point-to. Compute the reachability set of escaped and call-used
6446 compute_points_to_sets ();
6448 /* Debugging dumps. */
6451 dump_alias_info (dump_file);
6453 if (dump_flags & TDF_DETAILS)
6454 dump_referenced_vars (dump_file);
6457 /* Deallocate memory used by aliasing data structures and the internal
6458 points-to solution. */
6459 delete_points_to_sets ();
6461 gcc_assert (!need_ssa_update_p (cfun));
6467 gate_tree_pta (void)
6469 return flag_tree_pta;
6472 /* A dummy pass to cause points-to information to be computed via
6473 TODO_rebuild_alias. */
6475 struct gimple_opt_pass pass_build_alias =
6480 gate_tree_pta, /* gate */
6484 0, /* static_pass_number */
6485 TV_NONE, /* tv_id */
6486 PROP_cfg | PROP_ssa, /* properties_required */
6487 0, /* properties_provided */
6488 0, /* properties_destroyed */
6489 0, /* todo_flags_start */
6490 TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */
6494 /* A dummy pass to cause points-to information to be computed via
6495 TODO_rebuild_alias. */
6497 struct gimple_opt_pass pass_build_ealias =
6501 "ealias", /* name */
6502 gate_tree_pta, /* gate */
6506 0, /* static_pass_number */
6507 TV_NONE, /* tv_id */
6508 PROP_cfg | PROP_ssa, /* properties_required */
6509 0, /* properties_provided */
6510 0, /* properties_destroyed */
6511 0, /* todo_flags_start */
6512 TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */
6517 /* Return true if we should execute IPA PTA. */
6523 /* Don't bother doing anything if the program has errors. */
6524 && !(errorcount || sorrycount));
6527 /* IPA PTA solutions for ESCAPED. */
6528 struct pt_solution ipa_escaped_pt
6529 = { true, false, false, false, false, false, false, NULL };
6531 /* Execute the driver for IPA PTA. */
6533 ipa_pta_execute (void)
6535 struct cgraph_node *node;
6536 struct varpool_node *var;
6541 init_alias_heapvars ();
6544 /* Build the constraints. */
6545 for (node = cgraph_nodes; node; node = node->next)
6547 /* Nodes without a body are not interesting. Especially do not
6548 visit clones at this point for now - we get duplicate decls
6549 there for inline clones at least. */
6550 if (!gimple_has_body_p (node->decl)
6554 create_function_info_for (node->decl,
6555 cgraph_node_name (node));
6558 /* Create constraints for global variables and their initializers. */
6559 for (var = varpool_nodes; var; var = var->next)
6560 get_vi_for_tree (var->decl);
6565 "Generating constraints for global initializers\n\n");
6566 dump_constraints (dump_file, 0);
6567 fprintf (dump_file, "\n");
6569 from = VEC_length (constraint_t, constraints);
6571 for (node = cgraph_nodes; node; node = node->next)
6573 struct function *func;
6577 /* Nodes without a body are not interesting. */
6578 if (!gimple_has_body_p (node->decl)
6584 "Generating constraints for %s\n",
6585 cgraph_node_name (node));
6587 func = DECL_STRUCT_FUNCTION (node->decl);
6588 old_func_decl = current_function_decl;
6590 current_function_decl = node->decl;
6592 /* For externally visible functions use local constraints for
6593 their arguments. For local functions we see all callers
6594 and thus do not need initial constraints for parameters. */
6595 if (node->local.externally_visible)
6596 intra_create_variable_infos ();
6598 /* Build constriants for the function body. */
6599 FOR_EACH_BB_FN (bb, func)
6601 gimple_stmt_iterator gsi;
6603 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
6606 gimple phi = gsi_stmt (gsi);
6608 if (is_gimple_reg (gimple_phi_result (phi)))
6609 find_func_aliases (phi);
6612 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6614 gimple stmt = gsi_stmt (gsi);
6616 find_func_aliases (stmt);
6617 find_func_clobbers (stmt);
6621 current_function_decl = old_func_decl;
6626 fprintf (dump_file, "\n");
6627 dump_constraints (dump_file, from);
6628 fprintf (dump_file, "\n");
6630 from = VEC_length (constraint_t, constraints);
6633 /* From the constraints compute the points-to sets. */
6634 solve_constraints ();
6636 /* Compute the global points-to sets for ESCAPED.
6637 ??? Note that the computed escape set is not correct
6638 for the whole unit as we fail to consider graph edges to
6639 externally visible functions. */
6640 find_what_var_points_to (get_varinfo (escaped_id), &ipa_escaped_pt);
6642 /* Make sure the ESCAPED solution (which is used as placeholder in
6643 other solutions) does not reference itself. This simplifies
6644 points-to solution queries. */
6645 ipa_escaped_pt.ipa_escaped = 0;
6647 /* Assign the points-to sets to the SSA names in the unit. */
6648 for (node = cgraph_nodes; node; node = node->next)
6651 struct function *fn;
6655 struct pt_solution uses, clobbers;
6656 struct cgraph_edge *e;
6658 /* Nodes without a body are not interesting. */
6659 if (!gimple_has_body_p (node->decl)
6663 fn = DECL_STRUCT_FUNCTION (node->decl);
6665 /* Compute the points-to sets for pointer SSA_NAMEs. */
6666 for (i = 0; VEC_iterate (tree, fn->gimple_df->ssa_names, i, ptr); ++i)
6669 && POINTER_TYPE_P (TREE_TYPE (ptr)))
6670 find_what_p_points_to (ptr);
6673 /* Compute the call-use and call-clobber sets for all direct calls. */
6674 fi = lookup_vi_for_tree (node->decl);
6675 gcc_assert (fi->is_fn_info);
6676 find_what_var_points_to (first_vi_for_offset (fi, fi_clobbers),
6678 find_what_var_points_to (first_vi_for_offset (fi, fi_uses), &uses);
6679 for (e = node->callers; e; e = e->next_caller)
6684 *gimple_call_clobber_set (e->call_stmt) = clobbers;
6685 *gimple_call_use_set (e->call_stmt) = uses;
6688 /* Compute the call-use and call-clobber sets for indirect calls
6689 and calls to external functions. */
6690 FOR_EACH_BB_FN (bb, fn)
6692 gimple_stmt_iterator gsi;
6694 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6696 gimple stmt = gsi_stmt (gsi);
6697 struct pt_solution *pt;
6701 if (!is_gimple_call (stmt))
6704 /* Handle direct calls to external functions. */
6705 decl = gimple_call_fndecl (stmt);
6707 && (!(fi = lookup_vi_for_tree (decl))
6708 || !fi->is_fn_info))
6710 pt = gimple_call_use_set (stmt);
6711 if (gimple_call_flags (stmt) & ECF_CONST)
6712 memset (pt, 0, sizeof (struct pt_solution));
6713 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
6715 find_what_var_points_to (vi, pt);
6716 /* Escaped (and thus nonlocal) variables are always
6717 implicitly used by calls. */
6718 /* ??? ESCAPED can be empty even though NONLOCAL
6721 pt->ipa_escaped = 1;
6725 /* If there is nothing special about this call then
6726 we have made everything that is used also escape. */
6727 *pt = ipa_escaped_pt;
6731 pt = gimple_call_clobber_set (stmt);
6732 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
6733 memset (pt, 0, sizeof (struct pt_solution));
6734 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
6736 find_what_var_points_to (vi, pt);
6737 /* Escaped (and thus nonlocal) variables are always
6738 implicitly clobbered by calls. */
6739 /* ??? ESCAPED can be empty even though NONLOCAL
6742 pt->ipa_escaped = 1;
6746 /* If there is nothing special about this call then
6747 we have made everything that is used also escape. */
6748 *pt = ipa_escaped_pt;
6753 /* Handle indirect calls. */
6755 && (fi = get_fi_for_callee (stmt)))
6757 /* We need to accumulate all clobbers/uses of all possible
6759 fi = get_varinfo (find (fi->id));
6760 /* If we cannot constrain the set of functions we'll end up
6761 calling we end up using/clobbering everything. */
6762 if (bitmap_bit_p (fi->solution, anything_id)
6763 || bitmap_bit_p (fi->solution, nonlocal_id)
6764 || bitmap_bit_p (fi->solution, escaped_id))
6766 pt_solution_reset (gimple_call_clobber_set (stmt));
6767 pt_solution_reset (gimple_call_use_set (stmt));
6773 struct pt_solution *uses, *clobbers;
6775 uses = gimple_call_use_set (stmt);
6776 clobbers = gimple_call_clobber_set (stmt);
6777 memset (uses, 0, sizeof (struct pt_solution));
6778 memset (clobbers, 0, sizeof (struct pt_solution));
6779 EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi)
6781 struct pt_solution sol;
6783 vi = get_varinfo (i);
6784 if (!vi->is_fn_info)
6786 /* ??? We could be more precise here? */
6788 uses->ipa_escaped = 1;
6789 clobbers->nonlocal = 1;
6790 clobbers->ipa_escaped = 1;
6794 if (!uses->anything)
6796 find_what_var_points_to
6797 (first_vi_for_offset (vi, fi_uses), &sol);
6798 pt_solution_ior_into (uses, &sol);
6800 if (!clobbers->anything)
6802 find_what_var_points_to
6803 (first_vi_for_offset (vi, fi_clobbers), &sol);
6804 pt_solution_ior_into (clobbers, &sol);
6812 fn->gimple_df->ipa_pta = true;
6815 delete_points_to_sets ();
6822 struct simple_ipa_opt_pass pass_ipa_pta =
6827 gate_ipa_pta, /* gate */
6828 ipa_pta_execute, /* execute */
6831 0, /* static_pass_number */
6832 TV_IPA_PTA, /* tv_id */
6833 0, /* properties_required */
6834 0, /* properties_provided */
6835 0, /* properties_destroyed */
6836 0, /* todo_flags_start */
6837 TODO_update_ssa /* todo_flags_finish */
6842 #include "gt-tree-ssa-structalias.h"