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 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
165 htab_t heapvar_for_stmt;
167 static bool use_field_sensitive = true;
168 static int in_ipa_mode = 0;
170 /* Used for predecessor bitmaps. */
171 static bitmap_obstack predbitmap_obstack;
173 /* Used for points-to sets. */
174 static bitmap_obstack pta_obstack;
176 /* Used for oldsolution members of variables. */
177 static bitmap_obstack oldpta_obstack;
179 /* Used for per-solver-iteration bitmaps. */
180 static bitmap_obstack iteration_obstack;
182 static unsigned int create_variable_info_for (tree, const char *);
183 typedef struct constraint_graph *constraint_graph_t;
184 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
187 typedef struct constraint *constraint_t;
189 DEF_VEC_P(constraint_t);
190 DEF_VEC_ALLOC_P(constraint_t,heap);
192 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
194 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
196 static struct constraint_stats
198 unsigned int total_vars;
199 unsigned int nonpointer_vars;
200 unsigned int unified_vars_static;
201 unsigned int unified_vars_dynamic;
202 unsigned int iterations;
203 unsigned int num_edges;
204 unsigned int num_implicit_edges;
205 unsigned int points_to_sets_created;
210 /* ID of this variable */
213 /* True if this is a variable created by the constraint analysis, such as
214 heap variables and constraints we had to break up. */
215 unsigned int is_artificial_var : 1;
217 /* True if this is a special variable whose solution set should not be
219 unsigned int is_special_var : 1;
221 /* True for variables whose size is not known or variable. */
222 unsigned int is_unknown_size_var : 1;
224 /* True for (sub-)fields that represent a whole variable. */
225 unsigned int is_full_var : 1;
227 /* True if this is a heap variable. */
228 unsigned int is_heap_var : 1;
230 /* True if this is a variable tracking a restrict pointer source. */
231 unsigned int is_restrict_var : 1;
233 /* True if this field may contain pointers. */
234 unsigned int may_have_pointers : 1;
236 /* True if this represents a global variable. */
237 unsigned int is_global_var : 1;
239 /* A link to the variable for the next field in this structure. */
240 struct variable_info *next;
242 /* Offset of this variable, in bits, from the base variable */
243 unsigned HOST_WIDE_INT offset;
245 /* Size of the variable, in bits. */
246 unsigned HOST_WIDE_INT size;
248 /* Full size of the base variable, in bits. */
249 unsigned HOST_WIDE_INT fullsize;
251 /* Name of this variable */
254 /* Tree that this variable is associated with. */
257 /* Points-to set for this variable. */
260 /* Old points-to set for this variable. */
263 typedef struct variable_info *varinfo_t;
265 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
266 static varinfo_t first_or_preceding_vi_for_offset (varinfo_t,
267 unsigned HOST_WIDE_INT);
268 static varinfo_t lookup_vi_for_tree (tree);
270 /* Pool of variable info structures. */
271 static alloc_pool variable_info_pool;
273 DEF_VEC_P(varinfo_t);
275 DEF_VEC_ALLOC_P(varinfo_t, heap);
277 /* Table of variable info structures for constraint variables.
278 Indexed directly by variable info id. */
279 static VEC(varinfo_t,heap) *varmap;
281 /* Return the varmap element N */
283 static inline varinfo_t
284 get_varinfo (unsigned int n)
286 return VEC_index (varinfo_t, varmap, n);
289 /* Static IDs for the special variables. */
290 enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
291 escaped_id = 3, nonlocal_id = 4,
292 storedanything_id = 5, integer_id = 6 };
294 struct GTY(()) heapvar_map {
296 unsigned HOST_WIDE_INT offset;
300 heapvar_map_eq (const void *p1, const void *p2)
302 const struct heapvar_map *h1 = (const struct heapvar_map *)p1;
303 const struct heapvar_map *h2 = (const struct heapvar_map *)p2;
304 return (h1->map.base.from == h2->map.base.from
305 && h1->offset == h2->offset);
309 heapvar_map_hash (struct heapvar_map *h)
311 return iterative_hash_host_wide_int (h->offset,
312 htab_hash_pointer (h->map.base.from));
315 /* Lookup a heap var for FROM, and return it if we find one. */
318 heapvar_lookup (tree from, unsigned HOST_WIDE_INT offset)
320 struct heapvar_map *h, in;
321 in.map.base.from = from;
323 h = (struct heapvar_map *) htab_find_with_hash (heapvar_for_stmt, &in,
324 heapvar_map_hash (&in));
330 /* Insert a mapping FROM->TO in the heap var for statement
334 heapvar_insert (tree from, unsigned HOST_WIDE_INT offset, tree to)
336 struct heapvar_map *h;
339 h = GGC_NEW (struct heapvar_map);
340 h->map.base.from = from;
342 h->map.hash = heapvar_map_hash (h);
344 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->map.hash, INSERT);
345 gcc_assert (*loc == NULL);
346 *(struct heapvar_map **) loc = h;
349 /* Return a new variable info structure consisting for a variable
350 named NAME, and using constraint graph node NODE. Append it
351 to the vector of variable info structures. */
354 new_var_info (tree t, const char *name)
356 unsigned index = VEC_length (varinfo_t, varmap);
357 varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
362 /* Vars without decl are artificial and do not have sub-variables. */
363 ret->is_artificial_var = (t == NULL_TREE);
364 ret->is_special_var = false;
365 ret->is_unknown_size_var = false;
366 ret->is_full_var = (t == NULL_TREE);
367 ret->is_heap_var = false;
368 ret->is_restrict_var = false;
369 ret->may_have_pointers = true;
370 ret->is_global_var = (t == NULL_TREE);
372 ret->is_global_var = is_global_var (t);
373 ret->solution = BITMAP_ALLOC (&pta_obstack);
374 ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
377 VEC_safe_push (varinfo_t, heap, varmap, ret);
383 /* A map mapping call statements to per-stmt variables for uses
384 and clobbers specific to the call. */
385 struct pointer_map_t *call_stmt_vars;
387 /* Lookup or create the variable for the call statement CALL. */
390 get_call_vi (gimple call)
395 slot_p = pointer_map_insert (call_stmt_vars, call);
397 return (varinfo_t) *slot_p;
399 vi = new_var_info (NULL_TREE, "CALLUSED");
403 vi->is_full_var = true;
405 vi->next = vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
409 vi2->is_full_var = true;
411 *slot_p = (void *) vi;
415 /* Lookup the variable for the call statement CALL representing
416 the uses. Returns NULL if there is nothing special about this call. */
419 lookup_call_use_vi (gimple call)
423 slot_p = pointer_map_contains (call_stmt_vars, call);
425 return (varinfo_t) *slot_p;
430 /* Lookup the variable for the call statement CALL representing
431 the clobbers. Returns NULL if there is nothing special about this call. */
434 lookup_call_clobber_vi (gimple call)
436 varinfo_t uses = lookup_call_use_vi (call);
443 /* Lookup or create the variable for the call statement CALL representing
447 get_call_use_vi (gimple call)
449 return get_call_vi (call);
452 /* Lookup or create the variable for the call statement CALL representing
455 static varinfo_t ATTRIBUTE_UNUSED
456 get_call_clobber_vi (gimple call)
458 return get_call_vi (call)->next;
462 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
464 /* An expression that appears in a constraint. */
466 struct constraint_expr
468 /* Constraint type. */
469 constraint_expr_type type;
471 /* Variable we are referring to in the constraint. */
474 /* Offset, in bits, of this constraint from the beginning of
475 variables it ends up referring to.
477 IOW, in a deref constraint, we would deref, get the result set,
478 then add OFFSET to each member. */
479 HOST_WIDE_INT offset;
482 /* Use 0x8000... as special unknown offset. */
483 #define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))
485 typedef struct constraint_expr ce_s;
487 DEF_VEC_ALLOC_O(ce_s, heap);
488 static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);
489 static void get_constraint_for (tree, VEC(ce_s, heap) **);
490 static void do_deref (VEC (ce_s, heap) **);
492 /* Our set constraints are made up of two constraint expressions, one
495 As described in the introduction, our set constraints each represent an
496 operation between set valued variables.
500 struct constraint_expr lhs;
501 struct constraint_expr rhs;
504 /* List of constraints that we use to build the constraint graph from. */
506 static VEC(constraint_t,heap) *constraints;
507 static alloc_pool constraint_pool;
509 /* The constraint graph is represented as an array of bitmaps
510 containing successor nodes. */
512 struct constraint_graph
514 /* Size of this graph, which may be different than the number of
515 nodes in the variable map. */
518 /* Explicit successors of each node. */
521 /* Implicit predecessors of each node (Used for variable
523 bitmap *implicit_preds;
525 /* Explicit predecessors of each node (Used for variable substitution). */
528 /* Indirect cycle representatives, or -1 if the node has no indirect
530 int *indirect_cycles;
532 /* Representative node for a node. rep[a] == a unless the node has
536 /* Equivalence class representative for a label. This is used for
537 variable substitution. */
540 /* Pointer equivalence label for a node. All nodes with the same
541 pointer equivalence label can be unified together at some point
542 (either during constraint optimization or after the constraint
546 /* Pointer equivalence representative for a label. This is used to
547 handle nodes that are pointer equivalent but not location
548 equivalent. We can unite these once the addressof constraints
549 are transformed into initial points-to sets. */
552 /* Pointer equivalence label for each node, used during variable
554 unsigned int *pointer_label;
556 /* Location equivalence label for each node, used during location
557 equivalence finding. */
558 unsigned int *loc_label;
560 /* Pointed-by set for each node, used during location equivalence
561 finding. This is pointed-by rather than pointed-to, because it
562 is constructed using the predecessor graph. */
565 /* Points to sets for pointer equivalence. This is *not* the actual
566 points-to sets for nodes. */
569 /* Bitmap of nodes where the bit is set if the node is a direct
570 node. Used for variable substitution. */
571 sbitmap direct_nodes;
573 /* Bitmap of nodes where the bit is set if the node is address
574 taken. Used for variable substitution. */
575 bitmap address_taken;
577 /* Vector of complex constraints for each graph node. Complex
578 constraints are those involving dereferences or offsets that are
580 VEC(constraint_t,heap) **complex;
583 static constraint_graph_t graph;
585 /* During variable substitution and the offline version of indirect
586 cycle finding, we create nodes to represent dereferences and
587 address taken constraints. These represent where these start and
589 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
590 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
592 /* Return the representative node for NODE, if NODE has been unioned
594 This function performs path compression along the way to finding
595 the representative. */
598 find (unsigned int node)
600 gcc_assert (node < graph->size);
601 if (graph->rep[node] != node)
602 return graph->rep[node] = find (graph->rep[node]);
606 /* Union the TO and FROM nodes to the TO nodes.
607 Note that at some point in the future, we may want to do
608 union-by-rank, in which case we are going to have to return the
609 node we unified to. */
612 unite (unsigned int to, unsigned int from)
614 gcc_assert (to < graph->size && from < graph->size);
615 if (to != from && graph->rep[from] != to)
617 graph->rep[from] = to;
623 /* Create a new constraint consisting of LHS and RHS expressions. */
626 new_constraint (const struct constraint_expr lhs,
627 const struct constraint_expr rhs)
629 constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
635 /* Print out constraint C to FILE. */
638 dump_constraint (FILE *file, constraint_t c)
640 if (c->lhs.type == ADDRESSOF)
642 else if (c->lhs.type == DEREF)
644 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
645 if (c->lhs.offset == UNKNOWN_OFFSET)
646 fprintf (file, " + UNKNOWN");
647 else if (c->lhs.offset != 0)
648 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
649 fprintf (file, " = ");
650 if (c->rhs.type == ADDRESSOF)
652 else if (c->rhs.type == DEREF)
654 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
655 if (c->rhs.offset == UNKNOWN_OFFSET)
656 fprintf (file, " + UNKNOWN");
657 else if (c->rhs.offset != 0)
658 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
659 fprintf (file, "\n");
663 void debug_constraint (constraint_t);
664 void debug_constraints (void);
665 void debug_constraint_graph (void);
666 void debug_solution_for_var (unsigned int);
667 void debug_sa_points_to_info (void);
669 /* Print out constraint C to stderr. */
672 debug_constraint (constraint_t c)
674 dump_constraint (stderr, c);
677 /* Print out all constraints to FILE */
680 dump_constraints (FILE *file)
684 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
685 dump_constraint (file, c);
688 /* Print out all constraints to stderr. */
691 debug_constraints (void)
693 dump_constraints (stderr);
696 /* Print out to FILE the edge in the constraint graph that is created by
697 constraint c. The edge may have a label, depending on the type of
698 constraint that it represents. If complex1, e.g: a = *b, then the label
699 is "=*", if complex2, e.g: *a = b, then the label is "*=", if
700 complex with an offset, e.g: a = b + 8, then the label is "+".
701 Otherwise the edge has no label. */
704 dump_constraint_edge (FILE *file, constraint_t c)
706 if (c->rhs.type != ADDRESSOF)
708 const char *src = get_varinfo (c->rhs.var)->name;
709 const char *dst = get_varinfo (c->lhs.var)->name;
710 fprintf (file, " \"%s\" -> \"%s\" ", src, dst);
711 /* Due to preprocessing of constraints, instructions like *a = *b are
712 illegal; thus, we do not have to handle such cases. */
713 if (c->lhs.type == DEREF)
714 fprintf (file, " [ label=\"*=\" ] ;\n");
715 else if (c->rhs.type == DEREF)
716 fprintf (file, " [ label=\"=*\" ] ;\n");
719 /* We must check the case where the constraint is an offset.
720 In this case, it is treated as a complex constraint. */
721 if (c->rhs.offset != c->lhs.offset)
722 fprintf (file, " [ label=\"+\" ] ;\n");
724 fprintf (file, " ;\n");
729 /* Print the constraint graph in dot format. */
732 dump_constraint_graph (FILE *file)
734 unsigned int i=0, size;
737 /* Only print the graph if it has already been initialized: */
741 /* Print the constraints used to produce the constraint graph. The
742 constraints will be printed as comments in the dot file: */
743 fprintf (file, "\n\n/* Constraints used in the constraint graph:\n");
744 dump_constraints (file);
745 fprintf (file, "*/\n");
747 /* Prints the header of the dot file: */
748 fprintf (file, "\n\n// The constraint graph in dot format:\n");
749 fprintf (file, "strict digraph {\n");
750 fprintf (file, " node [\n shape = box\n ]\n");
751 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
752 fprintf (file, "\n // List of nodes in the constraint graph:\n");
754 /* The next lines print the nodes in the graph. In order to get the
755 number of nodes in the graph, we must choose the minimum between the
756 vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
757 yet been initialized, then graph->size == 0, otherwise we must only
758 read nodes that have an entry in VEC (varinfo_t, varmap). */
759 size = VEC_length (varinfo_t, varmap);
760 size = size < graph->size ? size : graph->size;
761 for (i = 0; i < size; i++)
763 const char *name = get_varinfo (graph->rep[i])->name;
764 fprintf (file, " \"%s\" ;\n", name);
767 /* Go over the list of constraints printing the edges in the constraint
769 fprintf (file, "\n // The constraint edges:\n");
770 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
772 dump_constraint_edge (file, c);
774 /* Prints the tail of the dot file. By now, only the closing bracket. */
775 fprintf (file, "}\n\n\n");
778 /* Print out the constraint graph to stderr. */
781 debug_constraint_graph (void)
783 dump_constraint_graph (stderr);
788 The solver is a simple worklist solver, that works on the following
791 sbitmap changed_nodes = all zeroes;
793 For each node that is not already collapsed:
795 set bit in changed nodes
797 while (changed_count > 0)
799 compute topological ordering for constraint graph
801 find and collapse cycles in the constraint graph (updating
802 changed if necessary)
804 for each node (n) in the graph in topological order:
807 Process each complex constraint associated with the node,
808 updating changed if necessary.
810 For each outgoing edge from n, propagate the solution from n to
811 the destination of the edge, updating changed as necessary.
815 /* Return true if two constraint expressions A and B are equal. */
818 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
820 return a.type == b.type && a.var == b.var && a.offset == b.offset;
823 /* Return true if constraint expression A is less than constraint expression
824 B. This is just arbitrary, but consistent, in order to give them an
828 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
830 if (a.type == b.type)
833 return a.offset < b.offset;
835 return a.var < b.var;
838 return a.type < b.type;
841 /* Return true if constraint A is less than constraint B. This is just
842 arbitrary, but consistent, in order to give them an ordering. */
845 constraint_less (const constraint_t a, const constraint_t b)
847 if (constraint_expr_less (a->lhs, b->lhs))
849 else if (constraint_expr_less (b->lhs, a->lhs))
852 return constraint_expr_less (a->rhs, b->rhs);
855 /* Return true if two constraints A and B are equal. */
858 constraint_equal (struct constraint a, struct constraint b)
860 return constraint_expr_equal (a.lhs, b.lhs)
861 && constraint_expr_equal (a.rhs, b.rhs);
865 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
868 constraint_vec_find (VEC(constraint_t,heap) *vec,
869 struct constraint lookfor)
877 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
878 if (place >= VEC_length (constraint_t, vec))
880 found = VEC_index (constraint_t, vec, place);
881 if (!constraint_equal (*found, lookfor))
886 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
889 constraint_set_union (VEC(constraint_t,heap) **to,
890 VEC(constraint_t,heap) **from)
895 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
897 if (constraint_vec_find (*to, *c) == NULL)
899 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
901 VEC_safe_insert (constraint_t, heap, *to, place, c);
906 /* Expands the solution in SET to all sub-fields of variables included.
907 Union the expanded result into RESULT. */
910 solution_set_expand (bitmap result, bitmap set)
916 /* In a first pass record all variables we need to add all
917 sub-fields off. This avoids quadratic behavior. */
918 EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
920 varinfo_t v = get_varinfo (j);
921 if (v->is_artificial_var
924 v = lookup_vi_for_tree (v->decl);
926 vars = BITMAP_ALLOC (NULL);
927 bitmap_set_bit (vars, v->id);
930 /* In the second pass now do the addition to the solution and
931 to speed up solving add it to the delta as well. */
934 EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
936 varinfo_t v = get_varinfo (j);
937 for (; v != NULL; v = v->next)
938 bitmap_set_bit (result, v->id);
944 /* Take a solution set SET, add OFFSET to each member of the set, and
945 overwrite SET with the result when done. */
948 solution_set_add (bitmap set, HOST_WIDE_INT offset)
950 bitmap result = BITMAP_ALLOC (&iteration_obstack);
954 /* If the offset is unknown we have to expand the solution to
956 if (offset == UNKNOWN_OFFSET)
958 solution_set_expand (set, set);
962 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
964 varinfo_t vi = get_varinfo (i);
966 /* If this is a variable with just one field just set its bit
968 if (vi->is_artificial_var
969 || vi->is_unknown_size_var
971 bitmap_set_bit (result, i);
974 unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
976 /* If the offset makes the pointer point to before the
977 variable use offset zero for the field lookup. */
979 && fieldoffset > vi->offset)
983 vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
985 bitmap_set_bit (result, vi->id);
986 /* If the result is not exactly at fieldoffset include the next
987 field as well. See get_constraint_for_ptr_offset for more
989 if (vi->offset != fieldoffset
991 bitmap_set_bit (result, vi->next->id);
995 bitmap_copy (set, result);
996 BITMAP_FREE (result);
999 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
1003 set_union_with_increment (bitmap to, bitmap from, HOST_WIDE_INT inc)
1006 return bitmap_ior_into (to, from);
1012 tmp = BITMAP_ALLOC (&iteration_obstack);
1013 bitmap_copy (tmp, from);
1014 solution_set_add (tmp, inc);
1015 res = bitmap_ior_into (to, tmp);
1021 /* Insert constraint C into the list of complex constraints for graph
1025 insert_into_complex (constraint_graph_t graph,
1026 unsigned int var, constraint_t c)
1028 VEC (constraint_t, heap) *complex = graph->complex[var];
1029 unsigned int place = VEC_lower_bound (constraint_t, complex, c,
1032 /* Only insert constraints that do not already exist. */
1033 if (place >= VEC_length (constraint_t, complex)
1034 || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
1035 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
1039 /* Condense two variable nodes into a single variable node, by moving
1040 all associated info from SRC to TO. */
1043 merge_node_constraints (constraint_graph_t graph, unsigned int to,
1049 gcc_assert (find (from) == to);
1051 /* Move all complex constraints from src node into to node */
1052 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
1054 /* In complex constraints for node src, we may have either
1055 a = *src, and *src = a, or an offseted constraint which are
1056 always added to the rhs node's constraints. */
1058 if (c->rhs.type == DEREF)
1060 else if (c->lhs.type == DEREF)
1065 constraint_set_union (&graph->complex[to], &graph->complex[from]);
1066 VEC_free (constraint_t, heap, graph->complex[from]);
1067 graph->complex[from] = NULL;
1071 /* Remove edges involving NODE from GRAPH. */
1074 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
1076 if (graph->succs[node])
1077 BITMAP_FREE (graph->succs[node]);
1080 /* Merge GRAPH nodes FROM and TO into node TO. */
1083 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1086 if (graph->indirect_cycles[from] != -1)
1088 /* If we have indirect cycles with the from node, and we have
1089 none on the to node, the to node has indirect cycles from the
1090 from node now that they are unified.
1091 If indirect cycles exist on both, unify the nodes that they
1092 are in a cycle with, since we know they are in a cycle with
1094 if (graph->indirect_cycles[to] == -1)
1095 graph->indirect_cycles[to] = graph->indirect_cycles[from];
1098 /* Merge all the successor edges. */
1099 if (graph->succs[from])
1101 if (!graph->succs[to])
1102 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1103 bitmap_ior_into (graph->succs[to],
1104 graph->succs[from]);
1107 clear_edges_for_node (graph, from);
1111 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1112 it doesn't exist in the graph already. */
1115 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1121 if (!graph->implicit_preds[to])
1122 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1124 if (bitmap_set_bit (graph->implicit_preds[to], from))
1125 stats.num_implicit_edges++;
1128 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1129 it doesn't exist in the graph already.
1130 Return false if the edge already existed, true otherwise. */
1133 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1136 if (!graph->preds[to])
1137 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1138 bitmap_set_bit (graph->preds[to], from);
1141 /* Add a graph edge to GRAPH, going from FROM to TO if
1142 it doesn't exist in the graph already.
1143 Return false if the edge already existed, true otherwise. */
1146 add_graph_edge (constraint_graph_t graph, unsigned int to,
1157 if (!graph->succs[from])
1158 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1159 if (bitmap_set_bit (graph->succs[from], to))
1162 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1170 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1173 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1176 return (graph->succs[dest]
1177 && bitmap_bit_p (graph->succs[dest], src));
1180 /* Initialize the constraint graph structure to contain SIZE nodes. */
1183 init_graph (unsigned int size)
1187 graph = XCNEW (struct constraint_graph);
1189 graph->succs = XCNEWVEC (bitmap, graph->size);
1190 graph->indirect_cycles = XNEWVEC (int, graph->size);
1191 graph->rep = XNEWVEC (unsigned int, graph->size);
1192 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
1193 graph->pe = XCNEWVEC (unsigned int, graph->size);
1194 graph->pe_rep = XNEWVEC (int, graph->size);
1196 for (j = 0; j < graph->size; j++)
1199 graph->pe_rep[j] = -1;
1200 graph->indirect_cycles[j] = -1;
1204 /* Build the constraint graph, adding only predecessor edges right now. */
1207 build_pred_graph (void)
1213 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1214 graph->preds = XCNEWVEC (bitmap, graph->size);
1215 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1216 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1217 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1218 graph->points_to = XCNEWVEC (bitmap, graph->size);
1219 graph->eq_rep = XNEWVEC (int, graph->size);
1220 graph->direct_nodes = sbitmap_alloc (graph->size);
1221 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1222 sbitmap_zero (graph->direct_nodes);
1224 for (j = 0; j < FIRST_REF_NODE; j++)
1226 if (!get_varinfo (j)->is_special_var)
1227 SET_BIT (graph->direct_nodes, j);
1230 for (j = 0; j < graph->size; j++)
1231 graph->eq_rep[j] = -1;
1233 for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
1234 graph->indirect_cycles[j] = -1;
1236 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1238 struct constraint_expr lhs = c->lhs;
1239 struct constraint_expr rhs = c->rhs;
1240 unsigned int lhsvar = lhs.var;
1241 unsigned int rhsvar = rhs.var;
1243 if (lhs.type == DEREF)
1246 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1247 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1249 else if (rhs.type == DEREF)
1252 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1253 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1255 RESET_BIT (graph->direct_nodes, lhsvar);
1257 else if (rhs.type == ADDRESSOF)
1262 if (graph->points_to[lhsvar] == NULL)
1263 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1264 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1266 if (graph->pointed_by[rhsvar] == NULL)
1267 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1268 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1270 /* Implicitly, *x = y */
1271 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1273 /* All related variables are no longer direct nodes. */
1274 RESET_BIT (graph->direct_nodes, rhsvar);
1275 v = get_varinfo (rhsvar);
1276 if (!v->is_full_var)
1278 v = lookup_vi_for_tree (v->decl);
1281 RESET_BIT (graph->direct_nodes, v->id);
1286 bitmap_set_bit (graph->address_taken, rhsvar);
1288 else if (lhsvar > anything_id
1289 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1292 add_pred_graph_edge (graph, lhsvar, rhsvar);
1293 /* Implicitly, *x = *y */
1294 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1295 FIRST_REF_NODE + rhsvar);
1297 else if (lhs.offset != 0 || rhs.offset != 0)
1299 if (rhs.offset != 0)
1300 RESET_BIT (graph->direct_nodes, lhs.var);
1301 else if (lhs.offset != 0)
1302 RESET_BIT (graph->direct_nodes, rhs.var);
1307 /* Build the constraint graph, adding successor edges. */
1310 build_succ_graph (void)
1315 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1317 struct constraint_expr lhs;
1318 struct constraint_expr rhs;
1319 unsigned int lhsvar;
1320 unsigned int rhsvar;
1327 lhsvar = find (lhs.var);
1328 rhsvar = find (rhs.var);
1330 if (lhs.type == DEREF)
1332 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1333 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1335 else if (rhs.type == DEREF)
1337 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1338 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1340 else if (rhs.type == ADDRESSOF)
1343 gcc_assert (find (rhs.var) == rhs.var);
1344 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1346 else if (lhsvar > anything_id
1347 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1349 add_graph_edge (graph, lhsvar, rhsvar);
1353 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1354 receive pointers. */
1355 t = find (storedanything_id);
1356 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1358 if (!TEST_BIT (graph->direct_nodes, i)
1359 && get_varinfo (i)->may_have_pointers)
1360 add_graph_edge (graph, find (i), t);
1363 /* Everything stored to ANYTHING also potentially escapes. */
1364 add_graph_edge (graph, find (escaped_id), t);
1368 /* Changed variables on the last iteration. */
1369 static unsigned int changed_count;
1370 static sbitmap changed;
1372 /* Strongly Connected Component visitation info. */
1379 unsigned int *node_mapping;
1381 VEC(unsigned,heap) *scc_stack;
1385 /* Recursive routine to find strongly connected components in GRAPH.
1386 SI is the SCC info to store the information in, and N is the id of current
1387 graph node we are processing.
1389 This is Tarjan's strongly connected component finding algorithm, as
1390 modified by Nuutila to keep only non-root nodes on the stack.
1391 The algorithm can be found in "On finding the strongly connected
1392 connected components in a directed graph" by Esko Nuutila and Eljas
1393 Soisalon-Soininen, in Information Processing Letters volume 49,
1394 number 1, pages 9-14. */
1397 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1401 unsigned int my_dfs;
1403 SET_BIT (si->visited, n);
1404 si->dfs[n] = si->current_index ++;
1405 my_dfs = si->dfs[n];
1407 /* Visit all the successors. */
1408 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1412 if (i > LAST_REF_NODE)
1416 if (TEST_BIT (si->deleted, w))
1419 if (!TEST_BIT (si->visited, w))
1420 scc_visit (graph, si, w);
1422 unsigned int t = find (w);
1423 unsigned int nnode = find (n);
1424 gcc_assert (nnode == n);
1426 if (si->dfs[t] < si->dfs[nnode])
1427 si->dfs[n] = si->dfs[t];
1431 /* See if any components have been identified. */
1432 if (si->dfs[n] == my_dfs)
1434 if (VEC_length (unsigned, si->scc_stack) > 0
1435 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1437 bitmap scc = BITMAP_ALLOC (NULL);
1438 unsigned int lowest_node;
1441 bitmap_set_bit (scc, n);
1443 while (VEC_length (unsigned, si->scc_stack) != 0
1444 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1446 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1448 bitmap_set_bit (scc, w);
1451 lowest_node = bitmap_first_set_bit (scc);
1452 gcc_assert (lowest_node < FIRST_REF_NODE);
1454 /* Collapse the SCC nodes into a single node, and mark the
1456 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1458 if (i < FIRST_REF_NODE)
1460 if (unite (lowest_node, i))
1461 unify_nodes (graph, lowest_node, i, false);
1465 unite (lowest_node, i);
1466 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1470 SET_BIT (si->deleted, n);
1473 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1476 /* Unify node FROM into node TO, updating the changed count if
1477 necessary when UPDATE_CHANGED is true. */
1480 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1481 bool update_changed)
1484 gcc_assert (to != from && find (to) == to);
1485 if (dump_file && (dump_flags & TDF_DETAILS))
1486 fprintf (dump_file, "Unifying %s to %s\n",
1487 get_varinfo (from)->name,
1488 get_varinfo (to)->name);
1491 stats.unified_vars_dynamic++;
1493 stats.unified_vars_static++;
1495 merge_graph_nodes (graph, to, from);
1496 merge_node_constraints (graph, to, from);
1498 /* Mark TO as changed if FROM was changed. If TO was already marked
1499 as changed, decrease the changed count. */
1501 if (update_changed && TEST_BIT (changed, from))
1503 RESET_BIT (changed, from);
1504 if (!TEST_BIT (changed, to))
1505 SET_BIT (changed, to);
1508 gcc_assert (changed_count > 0);
1512 if (get_varinfo (from)->solution)
1514 /* If the solution changes because of the merging, we need to mark
1515 the variable as changed. */
1516 if (bitmap_ior_into (get_varinfo (to)->solution,
1517 get_varinfo (from)->solution))
1519 if (update_changed && !TEST_BIT (changed, to))
1521 SET_BIT (changed, to);
1526 BITMAP_FREE (get_varinfo (from)->solution);
1527 BITMAP_FREE (get_varinfo (from)->oldsolution);
1529 if (stats.iterations > 0)
1531 BITMAP_FREE (get_varinfo (to)->oldsolution);
1532 get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1535 if (valid_graph_edge (graph, to, to))
1537 if (graph->succs[to])
1538 bitmap_clear_bit (graph->succs[to], to);
1542 /* Information needed to compute the topological ordering of a graph. */
1546 /* sbitmap of visited nodes. */
1548 /* Array that stores the topological order of the graph, *in
1550 VEC(unsigned,heap) *topo_order;
1554 /* Initialize and return a topological info structure. */
1556 static struct topo_info *
1557 init_topo_info (void)
1559 size_t size = graph->size;
1560 struct topo_info *ti = XNEW (struct topo_info);
1561 ti->visited = sbitmap_alloc (size);
1562 sbitmap_zero (ti->visited);
1563 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1568 /* Free the topological sort info pointed to by TI. */
1571 free_topo_info (struct topo_info *ti)
1573 sbitmap_free (ti->visited);
1574 VEC_free (unsigned, heap, ti->topo_order);
1578 /* Visit the graph in topological order, and store the order in the
1579 topo_info structure. */
1582 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1588 SET_BIT (ti->visited, n);
1590 if (graph->succs[n])
1591 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1593 if (!TEST_BIT (ti->visited, j))
1594 topo_visit (graph, ti, j);
1597 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1600 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1601 starting solution for y. */
1604 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1607 unsigned int lhs = c->lhs.var;
1609 bitmap sol = get_varinfo (lhs)->solution;
1612 HOST_WIDE_INT roffset = c->rhs.offset;
1614 /* Our IL does not allow this. */
1615 gcc_assert (c->lhs.offset == 0);
1617 /* If the solution of Y contains anything it is good enough to transfer
1619 if (bitmap_bit_p (delta, anything_id))
1621 flag |= bitmap_set_bit (sol, anything_id);
1625 /* If we do not know at with offset the rhs is dereferenced compute
1626 the reachability set of DELTA, conservatively assuming it is
1627 dereferenced at all valid offsets. */
1628 if (roffset == UNKNOWN_OFFSET)
1630 solution_set_expand (delta, delta);
1631 /* No further offset processing is necessary. */
1635 /* For each variable j in delta (Sol(y)), add
1636 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1637 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1639 varinfo_t v = get_varinfo (j);
1640 HOST_WIDE_INT fieldoffset = v->offset + roffset;
1644 fieldoffset = v->offset;
1645 else if (roffset != 0)
1646 v = first_vi_for_offset (v, fieldoffset);
1647 /* If the access is outside of the variable we can ignore it. */
1655 /* Adding edges from the special vars is pointless.
1656 They don't have sets that can change. */
1657 if (get_varinfo (t)->is_special_var)
1658 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1659 /* Merging the solution from ESCAPED needlessly increases
1660 the set. Use ESCAPED as representative instead. */
1661 else if (v->id == escaped_id)
1662 flag |= bitmap_set_bit (sol, escaped_id);
1663 else if (add_graph_edge (graph, lhs, t))
1664 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1666 /* If the variable is not exactly at the requested offset
1667 we have to include the next one. */
1668 if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1673 fieldoffset = v->offset;
1679 /* If the LHS solution changed, mark the var as changed. */
1682 get_varinfo (lhs)->solution = sol;
1683 if (!TEST_BIT (changed, lhs))
1685 SET_BIT (changed, lhs);
1691 /* Process a constraint C that represents *(x + off) = y using DELTA
1692 as the starting solution for x. */
1695 do_ds_constraint (constraint_t c, bitmap delta)
1697 unsigned int rhs = c->rhs.var;
1698 bitmap sol = get_varinfo (rhs)->solution;
1701 HOST_WIDE_INT loff = c->lhs.offset;
1703 /* Our IL does not allow this. */
1704 gcc_assert (c->rhs.offset == 0);
1706 /* If the solution of y contains ANYTHING simply use the ANYTHING
1707 solution. This avoids needlessly increasing the points-to sets. */
1708 if (bitmap_bit_p (sol, anything_id))
1709 sol = get_varinfo (find (anything_id))->solution;
1711 /* If the solution for x contains ANYTHING we have to merge the
1712 solution of y into all pointer variables which we do via
1714 if (bitmap_bit_p (delta, anything_id))
1716 unsigned t = find (storedanything_id);
1717 if (add_graph_edge (graph, t, rhs))
1719 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1721 if (!TEST_BIT (changed, t))
1723 SET_BIT (changed, t);
1731 /* If we do not know at with offset the rhs is dereferenced compute
1732 the reachability set of DELTA, conservatively assuming it is
1733 dereferenced at all valid offsets. */
1734 if (loff == UNKNOWN_OFFSET)
1736 solution_set_expand (delta, delta);
1740 /* For each member j of delta (Sol(x)), add an edge from y to j and
1741 union Sol(y) into Sol(j) */
1742 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1744 varinfo_t v = get_varinfo (j);
1746 HOST_WIDE_INT fieldoffset = v->offset + loff;
1748 /* If v is a global variable then this is an escape point. */
1749 if (v->is_global_var)
1751 t = find (escaped_id);
1752 if (add_graph_edge (graph, t, rhs)
1753 && bitmap_ior_into (get_varinfo (t)->solution, sol)
1754 && !TEST_BIT (changed, t))
1756 SET_BIT (changed, t);
1761 if (v->is_special_var)
1765 fieldoffset = v->offset;
1767 v = first_vi_for_offset (v, fieldoffset);
1768 /* If the access is outside of the variable we can ignore it. */
1774 if (v->may_have_pointers)
1777 if (add_graph_edge (graph, t, rhs)
1778 && bitmap_ior_into (get_varinfo (t)->solution, sol)
1779 && !TEST_BIT (changed, t))
1781 SET_BIT (changed, t);
1786 /* If the variable is not exactly at the requested offset
1787 we have to include the next one. */
1788 if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1793 fieldoffset = v->offset;
1799 /* Handle a non-simple (simple meaning requires no iteration),
1800 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1803 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1805 if (c->lhs.type == DEREF)
1807 if (c->rhs.type == ADDRESSOF)
1814 do_ds_constraint (c, delta);
1817 else if (c->rhs.type == DEREF)
1820 if (!(get_varinfo (c->lhs.var)->is_special_var))
1821 do_sd_constraint (graph, c, delta);
1829 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1830 solution = get_varinfo (c->rhs.var)->solution;
1831 tmp = get_varinfo (c->lhs.var)->solution;
1833 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1837 get_varinfo (c->lhs.var)->solution = tmp;
1838 if (!TEST_BIT (changed, c->lhs.var))
1840 SET_BIT (changed, c->lhs.var);
1847 /* Initialize and return a new SCC info structure. */
1849 static struct scc_info *
1850 init_scc_info (size_t size)
1852 struct scc_info *si = XNEW (struct scc_info);
1855 si->current_index = 0;
1856 si->visited = sbitmap_alloc (size);
1857 sbitmap_zero (si->visited);
1858 si->deleted = sbitmap_alloc (size);
1859 sbitmap_zero (si->deleted);
1860 si->node_mapping = XNEWVEC (unsigned int, size);
1861 si->dfs = XCNEWVEC (unsigned int, size);
1863 for (i = 0; i < size; i++)
1864 si->node_mapping[i] = i;
1866 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1870 /* Free an SCC info structure pointed to by SI */
1873 free_scc_info (struct scc_info *si)
1875 sbitmap_free (si->visited);
1876 sbitmap_free (si->deleted);
1877 free (si->node_mapping);
1879 VEC_free (unsigned, heap, si->scc_stack);
1884 /* Find indirect cycles in GRAPH that occur, using strongly connected
1885 components, and note them in the indirect cycles map.
1887 This technique comes from Ben Hardekopf and Calvin Lin,
1888 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1889 Lines of Code", submitted to PLDI 2007. */
1892 find_indirect_cycles (constraint_graph_t graph)
1895 unsigned int size = graph->size;
1896 struct scc_info *si = init_scc_info (size);
1898 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1899 if (!TEST_BIT (si->visited, i) && find (i) == i)
1900 scc_visit (graph, si, i);
1905 /* Compute a topological ordering for GRAPH, and store the result in the
1906 topo_info structure TI. */
1909 compute_topo_order (constraint_graph_t graph,
1910 struct topo_info *ti)
1913 unsigned int size = graph->size;
1915 for (i = 0; i != size; ++i)
1916 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1917 topo_visit (graph, ti, i);
1920 /* Structure used to for hash value numbering of pointer equivalence
1923 typedef struct equiv_class_label
1926 unsigned int equivalence_class;
1928 } *equiv_class_label_t;
1929 typedef const struct equiv_class_label *const_equiv_class_label_t;
1931 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1933 static htab_t pointer_equiv_class_table;
1935 /* A hashtable for mapping a bitmap of labels->location equivalence
1937 static htab_t location_equiv_class_table;
1939 /* Hash function for a equiv_class_label_t */
1942 equiv_class_label_hash (const void *p)
1944 const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
1945 return ecl->hashcode;
1948 /* Equality function for two equiv_class_label_t's. */
1951 equiv_class_label_eq (const void *p1, const void *p2)
1953 const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
1954 const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
1955 return (eql1->hashcode == eql2->hashcode
1956 && bitmap_equal_p (eql1->labels, eql2->labels));
1959 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
1963 equiv_class_lookup (htab_t table, bitmap labels)
1966 struct equiv_class_label ecl;
1968 ecl.labels = labels;
1969 ecl.hashcode = bitmap_hash (labels);
1971 slot = htab_find_slot_with_hash (table, &ecl,
1972 ecl.hashcode, NO_INSERT);
1976 return ((equiv_class_label_t) *slot)->equivalence_class;
1980 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
1984 equiv_class_add (htab_t table, unsigned int equivalence_class,
1988 equiv_class_label_t ecl = XNEW (struct equiv_class_label);
1990 ecl->labels = labels;
1991 ecl->equivalence_class = equivalence_class;
1992 ecl->hashcode = bitmap_hash (labels);
1994 slot = htab_find_slot_with_hash (table, ecl,
1995 ecl->hashcode, INSERT);
1996 gcc_assert (!*slot);
1997 *slot = (void *) ecl;
2000 /* Perform offline variable substitution.
2002 This is a worst case quadratic time way of identifying variables
2003 that must have equivalent points-to sets, including those caused by
2004 static cycles, and single entry subgraphs, in the constraint graph.
2006 The technique is described in "Exploiting Pointer and Location
2007 Equivalence to Optimize Pointer Analysis. In the 14th International
2008 Static Analysis Symposium (SAS), August 2007." It is known as the
2009 "HU" algorithm, and is equivalent to value numbering the collapsed
2010 constraint graph including evaluating unions.
2012 The general method of finding equivalence classes is as follows:
2013 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
2014 Initialize all non-REF nodes to be direct nodes.
2015 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
2017 For each constraint containing the dereference, we also do the same
2020 We then compute SCC's in the graph and unify nodes in the same SCC,
2023 For each non-collapsed node x:
2024 Visit all unvisited explicit incoming edges.
2025 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
2027 Lookup the equivalence class for pts(x).
2028 If we found one, equivalence_class(x) = found class.
2029 Otherwise, equivalence_class(x) = new class, and new_class is
2030 added to the lookup table.
2032 All direct nodes with the same equivalence class can be replaced
2033 with a single representative node.
2034 All unlabeled nodes (label == 0) are not pointers and all edges
2035 involving them can be eliminated.
2036 We perform these optimizations during rewrite_constraints
2038 In addition to pointer equivalence class finding, we also perform
2039 location equivalence class finding. This is the set of variables
2040 that always appear together in points-to sets. We use this to
2041 compress the size of the points-to sets. */
2043 /* Current maximum pointer equivalence class id. */
2044 static int pointer_equiv_class;
2046 /* Current maximum location equivalence class id. */
2047 static int location_equiv_class;
2049 /* Recursive routine to find strongly connected components in GRAPH,
2050 and label it's nodes with DFS numbers. */
2053 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2057 unsigned int my_dfs;
2059 gcc_assert (si->node_mapping[n] == n);
2060 SET_BIT (si->visited, n);
2061 si->dfs[n] = si->current_index ++;
2062 my_dfs = si->dfs[n];
2064 /* Visit all the successors. */
2065 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2067 unsigned int w = si->node_mapping[i];
2069 if (TEST_BIT (si->deleted, w))
2072 if (!TEST_BIT (si->visited, w))
2073 condense_visit (graph, si, w);
2075 unsigned int t = si->node_mapping[w];
2076 unsigned int nnode = si->node_mapping[n];
2077 gcc_assert (nnode == n);
2079 if (si->dfs[t] < si->dfs[nnode])
2080 si->dfs[n] = si->dfs[t];
2084 /* Visit all the implicit predecessors. */
2085 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
2087 unsigned int w = si->node_mapping[i];
2089 if (TEST_BIT (si->deleted, w))
2092 if (!TEST_BIT (si->visited, w))
2093 condense_visit (graph, si, w);
2095 unsigned int t = si->node_mapping[w];
2096 unsigned int nnode = si->node_mapping[n];
2097 gcc_assert (nnode == n);
2099 if (si->dfs[t] < si->dfs[nnode])
2100 si->dfs[n] = si->dfs[t];
2104 /* See if any components have been identified. */
2105 if (si->dfs[n] == my_dfs)
2107 while (VEC_length (unsigned, si->scc_stack) != 0
2108 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
2110 unsigned int w = VEC_pop (unsigned, si->scc_stack);
2111 si->node_mapping[w] = n;
2113 if (!TEST_BIT (graph->direct_nodes, w))
2114 RESET_BIT (graph->direct_nodes, n);
2116 /* Unify our nodes. */
2117 if (graph->preds[w])
2119 if (!graph->preds[n])
2120 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2121 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2123 if (graph->implicit_preds[w])
2125 if (!graph->implicit_preds[n])
2126 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2127 bitmap_ior_into (graph->implicit_preds[n],
2128 graph->implicit_preds[w]);
2130 if (graph->points_to[w])
2132 if (!graph->points_to[n])
2133 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2134 bitmap_ior_into (graph->points_to[n],
2135 graph->points_to[w]);
2138 SET_BIT (si->deleted, n);
2141 VEC_safe_push (unsigned, heap, si->scc_stack, n);
2144 /* Label pointer equivalences. */
2147 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2151 SET_BIT (si->visited, n);
2153 if (!graph->points_to[n])
2154 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2156 /* Label and union our incoming edges's points to sets. */
2157 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2159 unsigned int w = si->node_mapping[i];
2160 if (!TEST_BIT (si->visited, w))
2161 label_visit (graph, si, w);
2163 /* Skip unused edges */
2164 if (w == n || graph->pointer_label[w] == 0)
2167 if (graph->points_to[w])
2168 bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
2170 /* Indirect nodes get fresh variables. */
2171 if (!TEST_BIT (graph->direct_nodes, n))
2172 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2174 if (!bitmap_empty_p (graph->points_to[n]))
2176 unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
2177 graph->points_to[n]);
2180 label = pointer_equiv_class++;
2181 equiv_class_add (pointer_equiv_class_table,
2182 label, graph->points_to[n]);
2184 graph->pointer_label[n] = label;
2188 /* Perform offline variable substitution, discovering equivalence
2189 classes, and eliminating non-pointer variables. */
2191 static struct scc_info *
2192 perform_var_substitution (constraint_graph_t graph)
2195 unsigned int size = graph->size;
2196 struct scc_info *si = init_scc_info (size);
2198 bitmap_obstack_initialize (&iteration_obstack);
2199 pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
2200 equiv_class_label_eq, free);
2201 location_equiv_class_table = htab_create (511, equiv_class_label_hash,
2202 equiv_class_label_eq, free);
2203 pointer_equiv_class = 1;
2204 location_equiv_class = 1;
2206 /* Condense the nodes, which means to find SCC's, count incoming
2207 predecessors, and unite nodes in SCC's. */
2208 for (i = 0; i < FIRST_REF_NODE; i++)
2209 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2210 condense_visit (graph, si, si->node_mapping[i]);
2212 sbitmap_zero (si->visited);
2213 /* Actually the label the nodes for pointer equivalences */
2214 for (i = 0; i < FIRST_REF_NODE; i++)
2215 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2216 label_visit (graph, si, si->node_mapping[i]);
2218 /* Calculate location equivalence labels. */
2219 for (i = 0; i < FIRST_REF_NODE; i++)
2226 if (!graph->pointed_by[i])
2228 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2230 /* Translate the pointed-by mapping for pointer equivalence
2232 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2234 bitmap_set_bit (pointed_by,
2235 graph->pointer_label[si->node_mapping[j]]);
2237 /* The original pointed_by is now dead. */
2238 BITMAP_FREE (graph->pointed_by[i]);
2240 /* Look up the location equivalence label if one exists, or make
2242 label = equiv_class_lookup (location_equiv_class_table,
2246 label = location_equiv_class++;
2247 equiv_class_add (location_equiv_class_table,
2252 if (dump_file && (dump_flags & TDF_DETAILS))
2253 fprintf (dump_file, "Found location equivalence for node %s\n",
2254 get_varinfo (i)->name);
2255 BITMAP_FREE (pointed_by);
2257 graph->loc_label[i] = label;
2261 if (dump_file && (dump_flags & TDF_DETAILS))
2262 for (i = 0; i < FIRST_REF_NODE; i++)
2264 bool direct_node = TEST_BIT (graph->direct_nodes, i);
2266 "Equivalence classes for %s node id %d:%s are pointer: %d"
2268 direct_node ? "Direct node" : "Indirect node", i,
2269 get_varinfo (i)->name,
2270 graph->pointer_label[si->node_mapping[i]],
2271 graph->loc_label[si->node_mapping[i]]);
2274 /* Quickly eliminate our non-pointer variables. */
2276 for (i = 0; i < FIRST_REF_NODE; i++)
2278 unsigned int node = si->node_mapping[i];
2280 if (graph->pointer_label[node] == 0)
2282 if (dump_file && (dump_flags & TDF_DETAILS))
2284 "%s is a non-pointer variable, eliminating edges.\n",
2285 get_varinfo (node)->name);
2286 stats.nonpointer_vars++;
2287 clear_edges_for_node (graph, node);
2294 /* Free information that was only necessary for variable
2298 free_var_substitution_info (struct scc_info *si)
2301 free (graph->pointer_label);
2302 free (graph->loc_label);
2303 free (graph->pointed_by);
2304 free (graph->points_to);
2305 free (graph->eq_rep);
2306 sbitmap_free (graph->direct_nodes);
2307 htab_delete (pointer_equiv_class_table);
2308 htab_delete (location_equiv_class_table);
2309 bitmap_obstack_release (&iteration_obstack);
2312 /* Return an existing node that is equivalent to NODE, which has
2313 equivalence class LABEL, if one exists. Return NODE otherwise. */
2316 find_equivalent_node (constraint_graph_t graph,
2317 unsigned int node, unsigned int label)
2319 /* If the address version of this variable is unused, we can
2320 substitute it for anything else with the same label.
2321 Otherwise, we know the pointers are equivalent, but not the
2322 locations, and we can unite them later. */
2324 if (!bitmap_bit_p (graph->address_taken, node))
2326 gcc_assert (label < graph->size);
2328 if (graph->eq_rep[label] != -1)
2330 /* Unify the two variables since we know they are equivalent. */
2331 if (unite (graph->eq_rep[label], node))
2332 unify_nodes (graph, graph->eq_rep[label], node, false);
2333 return graph->eq_rep[label];
2337 graph->eq_rep[label] = node;
2338 graph->pe_rep[label] = node;
2343 gcc_assert (label < graph->size);
2344 graph->pe[node] = label;
2345 if (graph->pe_rep[label] == -1)
2346 graph->pe_rep[label] = node;
2352 /* Unite pointer equivalent but not location equivalent nodes in
2353 GRAPH. This may only be performed once variable substitution is
2357 unite_pointer_equivalences (constraint_graph_t graph)
2361 /* Go through the pointer equivalences and unite them to their
2362 representative, if they aren't already. */
2363 for (i = 0; i < FIRST_REF_NODE; i++)
2365 unsigned int label = graph->pe[i];
2368 int label_rep = graph->pe_rep[label];
2370 if (label_rep == -1)
2373 label_rep = find (label_rep);
2374 if (label_rep >= 0 && unite (label_rep, find (i)))
2375 unify_nodes (graph, label_rep, i, false);
2380 /* Move complex constraints to the GRAPH nodes they belong to. */
2383 move_complex_constraints (constraint_graph_t graph)
2388 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2392 struct constraint_expr lhs = c->lhs;
2393 struct constraint_expr rhs = c->rhs;
2395 if (lhs.type == DEREF)
2397 insert_into_complex (graph, lhs.var, c);
2399 else if (rhs.type == DEREF)
2401 if (!(get_varinfo (lhs.var)->is_special_var))
2402 insert_into_complex (graph, rhs.var, c);
2404 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2405 && (lhs.offset != 0 || rhs.offset != 0))
2407 insert_into_complex (graph, rhs.var, c);
2414 /* Optimize and rewrite complex constraints while performing
2415 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2416 result of perform_variable_substitution. */
2419 rewrite_constraints (constraint_graph_t graph,
2420 struct scc_info *si)
2426 for (j = 0; j < graph->size; j++)
2427 gcc_assert (find (j) == j);
2429 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2431 struct constraint_expr lhs = c->lhs;
2432 struct constraint_expr rhs = c->rhs;
2433 unsigned int lhsvar = find (lhs.var);
2434 unsigned int rhsvar = find (rhs.var);
2435 unsigned int lhsnode, rhsnode;
2436 unsigned int lhslabel, rhslabel;
2438 lhsnode = si->node_mapping[lhsvar];
2439 rhsnode = si->node_mapping[rhsvar];
2440 lhslabel = graph->pointer_label[lhsnode];
2441 rhslabel = graph->pointer_label[rhsnode];
2443 /* See if it is really a non-pointer variable, and if so, ignore
2447 if (dump_file && (dump_flags & TDF_DETAILS))
2450 fprintf (dump_file, "%s is a non-pointer variable,"
2451 "ignoring constraint:",
2452 get_varinfo (lhs.var)->name);
2453 dump_constraint (dump_file, c);
2455 VEC_replace (constraint_t, constraints, i, NULL);
2461 if (dump_file && (dump_flags & TDF_DETAILS))
2464 fprintf (dump_file, "%s is a non-pointer variable,"
2465 "ignoring constraint:",
2466 get_varinfo (rhs.var)->name);
2467 dump_constraint (dump_file, c);
2469 VEC_replace (constraint_t, constraints, i, NULL);
2473 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2474 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2475 c->lhs.var = lhsvar;
2476 c->rhs.var = rhsvar;
2481 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2482 part of an SCC, false otherwise. */
2485 eliminate_indirect_cycles (unsigned int node)
2487 if (graph->indirect_cycles[node] != -1
2488 && !bitmap_empty_p (get_varinfo (node)->solution))
2491 VEC(unsigned,heap) *queue = NULL;
2493 unsigned int to = find (graph->indirect_cycles[node]);
2496 /* We can't touch the solution set and call unify_nodes
2497 at the same time, because unify_nodes is going to do
2498 bitmap unions into it. */
2500 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2502 if (find (i) == i && i != to)
2505 VEC_safe_push (unsigned, heap, queue, i);
2510 VEC_iterate (unsigned, queue, queuepos, i);
2513 unify_nodes (graph, to, i, true);
2515 VEC_free (unsigned, heap, queue);
2521 /* Solve the constraint graph GRAPH using our worklist solver.
2522 This is based on the PW* family of solvers from the "Efficient Field
2523 Sensitive Pointer Analysis for C" paper.
2524 It works by iterating over all the graph nodes, processing the complex
2525 constraints and propagating the copy constraints, until everything stops
2526 changed. This corresponds to steps 6-8 in the solving list given above. */
2529 solve_graph (constraint_graph_t graph)
2531 unsigned int size = graph->size;
2536 changed = sbitmap_alloc (size);
2537 sbitmap_zero (changed);
2539 /* Mark all initial non-collapsed nodes as changed. */
2540 for (i = 0; i < size; i++)
2542 varinfo_t ivi = get_varinfo (i);
2543 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2544 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2545 || VEC_length (constraint_t, graph->complex[i]) > 0))
2547 SET_BIT (changed, i);
2552 /* Allocate a bitmap to be used to store the changed bits. */
2553 pts = BITMAP_ALLOC (&pta_obstack);
2555 while (changed_count > 0)
2558 struct topo_info *ti = init_topo_info ();
2561 bitmap_obstack_initialize (&iteration_obstack);
2563 compute_topo_order (graph, ti);
2565 while (VEC_length (unsigned, ti->topo_order) != 0)
2568 i = VEC_pop (unsigned, ti->topo_order);
2570 /* If this variable is not a representative, skip it. */
2574 /* In certain indirect cycle cases, we may merge this
2575 variable to another. */
2576 if (eliminate_indirect_cycles (i) && find (i) != i)
2579 /* If the node has changed, we need to process the
2580 complex constraints and outgoing edges again. */
2581 if (TEST_BIT (changed, i))
2586 VEC(constraint_t,heap) *complex = graph->complex[i];
2587 bool solution_empty;
2589 RESET_BIT (changed, i);
2592 /* Compute the changed set of solution bits. */
2593 bitmap_and_compl (pts, get_varinfo (i)->solution,
2594 get_varinfo (i)->oldsolution);
2596 if (bitmap_empty_p (pts))
2599 bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2601 solution = get_varinfo (i)->solution;
2602 solution_empty = bitmap_empty_p (solution);
2604 /* Process the complex constraints */
2605 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2607 /* XXX: This is going to unsort the constraints in
2608 some cases, which will occasionally add duplicate
2609 constraints during unification. This does not
2610 affect correctness. */
2611 c->lhs.var = find (c->lhs.var);
2612 c->rhs.var = find (c->rhs.var);
2614 /* The only complex constraint that can change our
2615 solution to non-empty, given an empty solution,
2616 is a constraint where the lhs side is receiving
2617 some set from elsewhere. */
2618 if (!solution_empty || c->lhs.type != DEREF)
2619 do_complex_constraint (graph, c, pts);
2622 solution_empty = bitmap_empty_p (solution);
2624 if (!solution_empty)
2627 unsigned eff_escaped_id = find (escaped_id);
2629 /* Propagate solution to all successors. */
2630 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2636 unsigned int to = find (j);
2637 tmp = get_varinfo (to)->solution;
2640 /* Don't try to propagate to ourselves. */
2644 /* If we propagate from ESCAPED use ESCAPED as
2646 if (i == eff_escaped_id)
2647 flag = bitmap_set_bit (tmp, escaped_id);
2649 flag = set_union_with_increment (tmp, pts, 0);
2653 get_varinfo (to)->solution = tmp;
2654 if (!TEST_BIT (changed, to))
2656 SET_BIT (changed, to);
2664 free_topo_info (ti);
2665 bitmap_obstack_release (&iteration_obstack);
2669 sbitmap_free (changed);
2670 bitmap_obstack_release (&oldpta_obstack);
2673 /* Map from trees to variable infos. */
2674 static struct pointer_map_t *vi_for_tree;
2677 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2680 insert_vi_for_tree (tree t, varinfo_t vi)
2682 void **slot = pointer_map_insert (vi_for_tree, t);
2684 gcc_assert (*slot == NULL);
2688 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2689 exist in the map, return NULL, otherwise, return the varinfo we found. */
2692 lookup_vi_for_tree (tree t)
2694 void **slot = pointer_map_contains (vi_for_tree, t);
2698 return (varinfo_t) *slot;
2701 /* Return a printable name for DECL */
2704 alias_get_name (tree decl)
2706 const char *res = get_name (decl);
2708 int num_printed = 0;
2717 if (TREE_CODE (decl) == SSA_NAME)
2719 num_printed = asprintf (&temp, "%s_%u",
2720 alias_get_name (SSA_NAME_VAR (decl)),
2721 SSA_NAME_VERSION (decl));
2723 else if (DECL_P (decl))
2725 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2727 if (num_printed > 0)
2729 res = ggc_strdup (temp);
2735 /* Find the variable id for tree T in the map.
2736 If T doesn't exist in the map, create an entry for it and return it. */
2739 get_vi_for_tree (tree t)
2741 void **slot = pointer_map_contains (vi_for_tree, t);
2743 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2745 return (varinfo_t) *slot;
2748 /* Get a scalar constraint expression for a new temporary variable. */
2750 static struct constraint_expr
2751 new_scalar_tmp_constraint_exp (const char *name)
2753 struct constraint_expr tmp;
2756 vi = new_var_info (NULL_TREE, name);
2760 vi->is_full_var = 1;
2769 /* Get a constraint expression vector from an SSA_VAR_P node.
2770 If address_p is true, the result will be taken its address of. */
2773 get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
2775 struct constraint_expr cexpr;
2778 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2779 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2781 /* For parameters, get at the points-to set for the actual parm
2783 if (TREE_CODE (t) == SSA_NAME
2784 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2785 && SSA_NAME_IS_DEFAULT_DEF (t))
2787 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2791 vi = get_vi_for_tree (t);
2793 cexpr.type = SCALAR;
2795 /* If we determine the result is "anything", and we know this is readonly,
2796 say it points to readonly memory instead. */
2797 if (cexpr.var == anything_id && TREE_READONLY (t))
2800 cexpr.type = ADDRESSOF;
2801 cexpr.var = readonly_id;
2804 /* If we are not taking the address of the constraint expr, add all
2805 sub-fiels of the variable as well. */
2807 && !vi->is_full_var)
2809 for (; vi; vi = vi->next)
2812 VEC_safe_push (ce_s, heap, *results, &cexpr);
2817 VEC_safe_push (ce_s, heap, *results, &cexpr);
2820 /* Process constraint T, performing various simplifications and then
2821 adding it to our list of overall constraints. */
2824 process_constraint (constraint_t t)
2826 struct constraint_expr rhs = t->rhs;
2827 struct constraint_expr lhs = t->lhs;
2829 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2830 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2832 /* If we didn't get any useful constraint from the lhs we get
2833 &ANYTHING as fallback from get_constraint_for. Deal with
2834 it here by turning it into *ANYTHING. */
2835 if (lhs.type == ADDRESSOF
2836 && lhs.var == anything_id)
2839 /* ADDRESSOF on the lhs is invalid. */
2840 gcc_assert (lhs.type != ADDRESSOF);
2842 /* This can happen in our IR with things like n->a = *p */
2843 if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2845 /* Split into tmp = *rhs, *lhs = tmp */
2846 struct constraint_expr tmplhs;
2847 tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp");
2848 process_constraint (new_constraint (tmplhs, rhs));
2849 process_constraint (new_constraint (lhs, tmplhs));
2851 else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
2853 /* Split into tmp = &rhs, *lhs = tmp */
2854 struct constraint_expr tmplhs;
2855 tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp");
2856 process_constraint (new_constraint (tmplhs, rhs));
2857 process_constraint (new_constraint (lhs, tmplhs));
2861 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2862 VEC_safe_push (constraint_t, heap, constraints, t);
2866 /* Return true if T is a type that could contain pointers. */
2869 type_could_have_pointers (tree type)
2871 if (POINTER_TYPE_P (type))
2874 if (TREE_CODE (type) == ARRAY_TYPE)
2875 return type_could_have_pointers (TREE_TYPE (type));
2877 return AGGREGATE_TYPE_P (type);
2880 /* Return true if T is a variable of a type that could contain
2884 could_have_pointers (tree t)
2886 return type_could_have_pointers (TREE_TYPE (t));
2889 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2892 static HOST_WIDE_INT
2893 bitpos_of_field (const tree fdecl)
2896 if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2897 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2900 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2901 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2905 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2906 resulting constraint expressions in *RESULTS. */
2909 get_constraint_for_ptr_offset (tree ptr, tree offset,
2910 VEC (ce_s, heap) **results)
2912 struct constraint_expr c;
2914 HOST_WIDE_INT rhsunitoffset, rhsoffset;
2916 /* If we do not do field-sensitive PTA adding offsets to pointers
2917 does not change the points-to solution. */
2918 if (!use_field_sensitive)
2920 get_constraint_for (ptr, results);
2924 /* If the offset is not a non-negative integer constant that fits
2925 in a HOST_WIDE_INT, we have to fall back to a conservative
2926 solution which includes all sub-fields of all pointed-to
2927 variables of ptr. */
2928 if (offset == NULL_TREE
2929 || !host_integerp (offset, 0))
2930 rhsoffset = UNKNOWN_OFFSET;
2933 /* Make sure the bit-offset also fits. */
2934 rhsunitoffset = TREE_INT_CST_LOW (offset);
2935 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
2936 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
2937 rhsoffset = UNKNOWN_OFFSET;
2940 get_constraint_for (ptr, results);
2944 /* As we are eventually appending to the solution do not use
2945 VEC_iterate here. */
2946 n = VEC_length (ce_s, *results);
2947 for (j = 0; j < n; j++)
2950 c = *VEC_index (ce_s, *results, j);
2951 curr = get_varinfo (c.var);
2953 if (c.type == ADDRESSOF
2954 /* If this varinfo represents a full variable just use it. */
2955 && curr->is_full_var)
2957 else if (c.type == ADDRESSOF
2958 /* If we do not know the offset add all subfields. */
2959 && rhsoffset == UNKNOWN_OFFSET)
2961 varinfo_t temp = lookup_vi_for_tree (curr->decl);
2964 struct constraint_expr c2;
2966 c2.type = ADDRESSOF;
2968 if (c2.var != c.var)
2969 VEC_safe_push (ce_s, heap, *results, &c2);
2974 else if (c.type == ADDRESSOF)
2977 unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
2979 /* Search the sub-field which overlaps with the
2980 pointed-to offset. If the result is outside of the variable
2981 we have to provide a conservative result, as the variable is
2982 still reachable from the resulting pointer (even though it
2983 technically cannot point to anything). The last and first
2984 sub-fields are such conservative results.
2985 ??? If we always had a sub-field for &object + 1 then
2986 we could represent this in a more precise way. */
2988 && curr->offset < offset)
2990 temp = first_or_preceding_vi_for_offset (curr, offset);
2992 /* If the found variable is not exactly at the pointed to
2993 result, we have to include the next variable in the
2994 solution as well. Otherwise two increments by offset / 2
2995 do not result in the same or a conservative superset
2997 if (temp->offset != offset
2998 && temp->next != NULL)
3000 struct constraint_expr c2;
3001 c2.var = temp->next->id;
3002 c2.type = ADDRESSOF;
3004 VEC_safe_push (ce_s, heap, *results, &c2);
3010 c.offset = rhsoffset;
3012 VEC_replace (ce_s, *results, j, &c);
3017 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3018 If address_p is true the result will be taken its address of. */
3021 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
3025 HOST_WIDE_INT bitsize = -1;
3026 HOST_WIDE_INT bitmaxsize = -1;
3027 HOST_WIDE_INT bitpos;
3029 struct constraint_expr *result;
3031 /* Some people like to do cute things like take the address of
3034 while (handled_component_p (forzero)
3035 || INDIRECT_REF_P (forzero))
3036 forzero = TREE_OPERAND (forzero, 0);
3038 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
3040 struct constraint_expr temp;
3043 temp.var = integer_id;
3045 VEC_safe_push (ce_s, heap, *results, &temp);
3049 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
3051 /* Pretend to take the address of the base, we'll take care of
3052 adding the required subset of sub-fields below. */
3053 get_constraint_for_1 (t, results, true);
3054 gcc_assert (VEC_length (ce_s, *results) == 1);
3055 result = VEC_last (ce_s, *results);
3057 if (result->type == SCALAR
3058 && get_varinfo (result->var)->is_full_var)
3059 /* For single-field vars do not bother about the offset. */
3061 else if (result->type == SCALAR)
3063 /* In languages like C, you can access one past the end of an
3064 array. You aren't allowed to dereference it, so we can
3065 ignore this constraint. When we handle pointer subtraction,
3066 we may have to do something cute here. */
3068 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
3071 /* It's also not true that the constraint will actually start at the
3072 right offset, it may start in some padding. We only care about
3073 setting the constraint to the first actual field it touches, so
3075 struct constraint_expr cexpr = *result;
3077 VEC_pop (ce_s, *results);
3079 for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
3081 if (ranges_overlap_p (curr->offset, curr->size,
3082 bitpos, bitmaxsize))
3084 cexpr.var = curr->id;
3085 VEC_safe_push (ce_s, heap, *results, &cexpr);
3090 /* If we are going to take the address of this field then
3091 to be able to compute reachability correctly add at least
3092 the last field of the variable. */
3094 && VEC_length (ce_s, *results) == 0)
3096 curr = get_varinfo (cexpr.var);
3097 while (curr->next != NULL)
3099 cexpr.var = curr->id;
3100 VEC_safe_push (ce_s, heap, *results, &cexpr);
3103 /* Assert that we found *some* field there. The user couldn't be
3104 accessing *only* padding. */
3105 /* Still the user could access one past the end of an array
3106 embedded in a struct resulting in accessing *only* padding. */
3107 gcc_assert (VEC_length (ce_s, *results) >= 1
3108 || ref_contains_array_ref (orig_t));
3110 else if (bitmaxsize == 0)
3112 if (dump_file && (dump_flags & TDF_DETAILS))
3113 fprintf (dump_file, "Access to zero-sized part of variable,"
3117 if (dump_file && (dump_flags & TDF_DETAILS))
3118 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3120 else if (result->type == DEREF)
3122 /* If we do not know exactly where the access goes say so. Note
3123 that only for non-structure accesses we know that we access
3124 at most one subfiled of any variable. */
3126 || bitsize != bitmaxsize
3127 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t)))
3128 result->offset = UNKNOWN_OFFSET;
3130 result->offset = bitpos;
3132 else if (result->type == ADDRESSOF)
3134 /* We can end up here for component references on a
3135 VIEW_CONVERT_EXPR <>(&foobar). */
3136 result->type = SCALAR;
3137 result->var = anything_id;
3145 /* Dereference the constraint expression CONS, and return the result.
3146 DEREF (ADDRESSOF) = SCALAR
3147 DEREF (SCALAR) = DEREF
3148 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3149 This is needed so that we can handle dereferencing DEREF constraints. */
3152 do_deref (VEC (ce_s, heap) **constraints)
3154 struct constraint_expr *c;
3157 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3159 if (c->type == SCALAR)
3161 else if (c->type == ADDRESSOF)
3163 else if (c->type == DEREF)
3165 struct constraint_expr tmplhs;
3166 tmplhs = new_scalar_tmp_constraint_exp ("dereftmp");
3167 process_constraint (new_constraint (tmplhs, *c));
3168 c->var = tmplhs.var;
3175 static void get_constraint_for_1 (tree, VEC (ce_s, heap) **, bool);
3177 /* Given a tree T, return the constraint expression for taking the
3181 get_constraint_for_address_of (tree t, VEC (ce_s, heap) **results)
3183 struct constraint_expr *c;
3186 get_constraint_for_1 (t, results, true);
3188 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3190 if (c->type == DEREF)
3193 c->type = ADDRESSOF;
3197 /* Given a tree T, return the constraint expression for it. */
3200 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3202 struct constraint_expr temp;
3204 /* x = integer is all glommed to a single variable, which doesn't
3205 point to anything by itself. That is, of course, unless it is an
3206 integer constant being treated as a pointer, in which case, we
3207 will return that this is really the addressof anything. This
3208 happens below, since it will fall into the default case. The only
3209 case we know something about an integer treated like a pointer is
3210 when it is the NULL pointer, and then we just say it points to
3213 Do not do that if -fno-delete-null-pointer-checks though, because
3214 in that case *NULL does not fail, so it _should_ alias *anything.
3215 It is not worth adding a new option or renaming the existing one,
3216 since this case is relatively obscure. */
3217 if (flag_delete_null_pointer_checks
3218 && ((TREE_CODE (t) == INTEGER_CST
3219 && integer_zerop (t))
3220 /* The only valid CONSTRUCTORs in gimple with pointer typed
3221 elements are zero-initializer. */
3222 || TREE_CODE (t) == CONSTRUCTOR))
3224 temp.var = nothing_id;
3225 temp.type = ADDRESSOF;
3227 VEC_safe_push (ce_s, heap, *results, &temp);
3231 /* String constants are read-only. */
3232 if (TREE_CODE (t) == STRING_CST)
3234 temp.var = readonly_id;
3237 VEC_safe_push (ce_s, heap, *results, &temp);
3241 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3243 case tcc_expression:
3245 switch (TREE_CODE (t))
3248 get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3256 switch (TREE_CODE (t))
3260 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3265 case ARRAY_RANGE_REF:
3267 get_constraint_for_component_ref (t, results, address_p);
3269 case VIEW_CONVERT_EXPR:
3270 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3272 /* We are missing handling for TARGET_MEM_REF here. */
3277 case tcc_exceptional:
3279 switch (TREE_CODE (t))
3283 get_constraint_for_ssa_var (t, results, address_p);
3290 case tcc_declaration:
3292 get_constraint_for_ssa_var (t, results, address_p);
3298 /* The default fallback is a constraint from anything. */
3299 temp.type = ADDRESSOF;
3300 temp.var = anything_id;
3302 VEC_safe_push (ce_s, heap, *results, &temp);
3305 /* Given a gimple tree T, return the constraint expression vector for it. */
3308 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3310 gcc_assert (VEC_length (ce_s, *results) == 0);
3312 get_constraint_for_1 (t, results, false);
3316 /* Efficiently generates constraints from all entries in *RHSC to all
3317 entries in *LHSC. */
3320 process_all_all_constraints (VEC (ce_s, heap) *lhsc, VEC (ce_s, heap) *rhsc)
3322 struct constraint_expr *lhsp, *rhsp;
3325 if (VEC_length (ce_s, lhsc) <= 1
3326 || VEC_length (ce_s, rhsc) <= 1)
3328 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3329 for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); ++j)
3330 process_constraint (new_constraint (*lhsp, *rhsp));
3334 struct constraint_expr tmp;
3335 tmp = new_scalar_tmp_constraint_exp ("allalltmp");
3336 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
3337 process_constraint (new_constraint (tmp, *rhsp));
3338 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3339 process_constraint (new_constraint (*lhsp, tmp));
3343 /* Handle aggregate copies by expanding into copies of the respective
3344 fields of the structures. */
3347 do_structure_copy (tree lhsop, tree rhsop)
3349 struct constraint_expr *lhsp, *rhsp;
3350 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3353 get_constraint_for (lhsop, &lhsc);
3354 get_constraint_for (rhsop, &rhsc);
3355 lhsp = VEC_index (ce_s, lhsc, 0);
3356 rhsp = VEC_index (ce_s, rhsc, 0);
3357 if (lhsp->type == DEREF
3358 || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3359 || rhsp->type == DEREF)
3360 process_all_all_constraints (lhsc, rhsc);
3361 else if (lhsp->type == SCALAR
3362 && (rhsp->type == SCALAR
3363 || rhsp->type == ADDRESSOF))
3365 HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
3366 HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
3368 get_ref_base_and_extent (lhsop, &lhsoffset, &lhssize, &lhsmaxsize);
3369 get_ref_base_and_extent (rhsop, &rhsoffset, &rhssize, &rhsmaxsize);
3370 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp);)
3372 varinfo_t lhsv, rhsv;
3373 rhsp = VEC_index (ce_s, rhsc, k);
3374 lhsv = get_varinfo (lhsp->var);
3375 rhsv = get_varinfo (rhsp->var);
3376 if (lhsv->may_have_pointers
3377 && ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3378 rhsv->offset + lhsoffset, rhsv->size))
3379 process_constraint (new_constraint (*lhsp, *rhsp));
3380 if (lhsv->offset + rhsoffset + lhsv->size
3381 > rhsv->offset + lhsoffset + rhsv->size)
3384 if (k >= VEC_length (ce_s, rhsc))
3394 VEC_free (ce_s, heap, lhsc);
3395 VEC_free (ce_s, heap, rhsc);
3398 /* Create a constraint ID = OP. */
3401 make_constraint_to (unsigned id, tree op)
3403 VEC(ce_s, heap) *rhsc = NULL;
3404 struct constraint_expr *c;
3405 struct constraint_expr includes;
3409 includes.offset = 0;
3410 includes.type = SCALAR;
3412 get_constraint_for (op, &rhsc);
3413 for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3414 process_constraint (new_constraint (includes, *c));
3415 VEC_free (ce_s, heap, rhsc);
3418 /* Create a constraint ID = &FROM. */
3421 make_constraint_from (varinfo_t vi, int from)
3423 struct constraint_expr lhs, rhs;
3431 rhs.type = ADDRESSOF;
3432 process_constraint (new_constraint (lhs, rhs));
3435 /* Create a constraint ID = FROM. */
3438 make_copy_constraint (varinfo_t vi, int from)
3440 struct constraint_expr lhs, rhs;
3449 process_constraint (new_constraint (lhs, rhs));
3452 /* Make constraints necessary to make OP escape. */
3455 make_escape_constraint (tree op)
3457 make_constraint_to (escaped_id, op);
3460 /* Add constraints to that the solution of VI is transitively closed. */
3463 make_transitive_closure_constraints (varinfo_t vi)
3465 struct constraint_expr lhs, rhs;
3474 process_constraint (new_constraint (lhs, rhs));
3476 /* VAR = VAR + UNKNOWN; */
3482 rhs.offset = UNKNOWN_OFFSET;
3483 process_constraint (new_constraint (lhs, rhs));
3486 /* Create a new artificial heap variable with NAME and make a
3487 constraint from it to LHS. Return the created variable. */
3490 make_constraint_from_heapvar (varinfo_t lhs, const char *name)
3493 tree heapvar = heapvar_lookup (lhs->decl, lhs->offset);
3495 if (heapvar == NULL_TREE)
3498 heapvar = create_tmp_var_raw (ptr_type_node, name);
3499 DECL_EXTERNAL (heapvar) = 1;
3501 heapvar_insert (lhs->decl, lhs->offset, heapvar);
3503 ann = get_var_ann (heapvar);
3504 ann->is_heapvar = 1;
3507 /* For global vars we need to add a heapvar to the list of referenced
3508 vars of a different function than it was created for originally. */
3509 if (gimple_referenced_vars (cfun))
3510 add_referenced_var (heapvar);
3512 vi = new_var_info (heapvar, name);
3513 vi->is_artificial_var = true;
3514 vi->is_heap_var = true;
3515 vi->is_unknown_size_var = true;
3519 vi->is_full_var = true;
3520 insert_vi_for_tree (heapvar, vi);
3522 make_constraint_from (lhs, vi->id);
3527 /* Create a new artificial heap variable with NAME and make a
3528 constraint from it to LHS. Set flags according to a tag used
3529 for tracking restrict pointers. */
3532 make_constraint_from_restrict (varinfo_t lhs, const char *name)
3535 vi = make_constraint_from_heapvar (lhs, name);
3536 vi->is_restrict_var = 1;
3537 vi->is_global_var = 0;
3538 vi->is_special_var = 1;
3539 vi->may_have_pointers = 0;
3542 /* For non-IPA mode, generate constraints necessary for a call on the
3546 handle_rhs_call (gimple stmt, VEC(ce_s, heap) **results)
3548 struct constraint_expr rhsc;
3551 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3553 tree arg = gimple_call_arg (stmt, i);
3555 /* Find those pointers being passed, and make sure they end up
3556 pointing to anything. */
3557 if (could_have_pointers (arg))
3558 make_escape_constraint (arg);
3561 /* The static chain escapes as well. */
3562 if (gimple_call_chain (stmt))
3563 make_escape_constraint (gimple_call_chain (stmt));
3565 /* And if we applied NRV the address of the return slot escapes as well. */
3566 if (gimple_call_return_slot_opt_p (stmt)
3567 && gimple_call_lhs (stmt) != NULL_TREE
3568 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
3570 VEC(ce_s, heap) *tmpc = NULL;
3571 struct constraint_expr lhsc, *c;
3572 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
3573 lhsc.var = escaped_id;
3576 for (i = 0; VEC_iterate (ce_s, tmpc, i, c); ++i)
3577 process_constraint (new_constraint (lhsc, *c));
3578 VEC_free(ce_s, heap, tmpc);
3581 /* Regular functions return nonlocal memory. */
3582 rhsc.var = nonlocal_id;
3585 VEC_safe_push (ce_s, heap, *results, &rhsc);
3588 /* For non-IPA mode, generate constraints necessary for a call
3589 that returns a pointer and assigns it to LHS. This simply makes
3590 the LHS point to global and escaped variables. */
3593 handle_lhs_call (tree lhs, int flags, VEC(ce_s, heap) *rhsc, tree fndecl)
3595 VEC(ce_s, heap) *lhsc = NULL;
3597 get_constraint_for (lhs, &lhsc);
3599 if (flags & ECF_MALLOC)
3602 vi = make_constraint_from_heapvar (get_vi_for_tree (lhs), "HEAP");
3603 /* We delay marking allocated storage global until we know if
3605 DECL_EXTERNAL (vi->decl) = 0;
3606 vi->is_global_var = 0;
3607 /* If this is not a real malloc call assume the memory was
3608 initialized and thus may point to global memory. All
3609 builtin functions with the malloc attribute behave in a sane way. */
3611 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
3612 make_constraint_from (vi, nonlocal_id);
3614 else if (VEC_length (ce_s, rhsc) > 0)
3616 /* If the store is to a global decl make sure to
3617 add proper escape constraints. */
3618 lhs = get_base_address (lhs);
3621 && is_global_var (lhs))
3623 struct constraint_expr tmpc;
3624 tmpc.var = escaped_id;
3627 VEC_safe_push (ce_s, heap, lhsc, &tmpc);
3629 process_all_all_constraints (lhsc, rhsc);
3631 VEC_free (ce_s, heap, lhsc);
3634 /* For non-IPA mode, generate constraints necessary for a call of a
3635 const function that returns a pointer in the statement STMT. */
3638 handle_const_call (gimple stmt, VEC(ce_s, heap) **results)
3640 struct constraint_expr rhsc;
3643 /* Treat nested const functions the same as pure functions as far
3644 as the static chain is concerned. */
3645 if (gimple_call_chain (stmt))
3647 varinfo_t uses = get_call_use_vi (stmt);
3648 make_transitive_closure_constraints (uses);
3649 make_constraint_to (uses->id, gimple_call_chain (stmt));
3650 rhsc.var = uses->id;
3653 VEC_safe_push (ce_s, heap, *results, &rhsc);
3656 /* May return arguments. */
3657 for (k = 0; k < gimple_call_num_args (stmt); ++k)
3659 tree arg = gimple_call_arg (stmt, k);
3661 if (could_have_pointers (arg))
3663 VEC(ce_s, heap) *argc = NULL;
3665 struct constraint_expr *argp;
3666 get_constraint_for (arg, &argc);
3667 for (i = 0; VEC_iterate (ce_s, argc, i, argp); ++i)
3668 VEC_safe_push (ce_s, heap, *results, argp);
3669 VEC_free(ce_s, heap, argc);
3673 /* May return addresses of globals. */
3674 rhsc.var = nonlocal_id;
3676 rhsc.type = ADDRESSOF;
3677 VEC_safe_push (ce_s, heap, *results, &rhsc);
3680 /* For non-IPA mode, generate constraints necessary for a call to a
3681 pure function in statement STMT. */
3684 handle_pure_call (gimple stmt, VEC(ce_s, heap) **results)
3686 struct constraint_expr rhsc;
3688 varinfo_t uses = NULL;
3690 /* Memory reached from pointer arguments is call-used. */
3691 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3693 tree arg = gimple_call_arg (stmt, i);
3695 if (could_have_pointers (arg))
3699 uses = get_call_use_vi (stmt);
3700 make_transitive_closure_constraints (uses);
3702 make_constraint_to (uses->id, arg);
3706 /* The static chain is used as well. */
3707 if (gimple_call_chain (stmt))
3711 uses = get_call_use_vi (stmt);
3712 make_transitive_closure_constraints (uses);
3714 make_constraint_to (uses->id, gimple_call_chain (stmt));
3717 /* Pure functions may return call-used and nonlocal memory. */
3720 rhsc.var = uses->id;
3723 VEC_safe_push (ce_s, heap, *results, &rhsc);
3725 rhsc.var = nonlocal_id;
3728 VEC_safe_push (ce_s, heap, *results, &rhsc);
3731 /* Walk statement T setting up aliasing constraints according to the
3732 references found in T. This function is the main part of the
3733 constraint builder. AI points to auxiliary alias information used
3734 when building alias sets and computing alias grouping heuristics. */
3737 find_func_aliases (gimple origt)
3740 VEC(ce_s, heap) *lhsc = NULL;
3741 VEC(ce_s, heap) *rhsc = NULL;
3742 struct constraint_expr *c;
3744 /* Now build constraints expressions. */
3745 if (gimple_code (t) == GIMPLE_PHI)
3747 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (gimple_phi_result (t))));
3749 /* Only care about pointers and structures containing
3751 if (could_have_pointers (gimple_phi_result (t)))
3756 /* For a phi node, assign all the arguments to
3758 get_constraint_for (gimple_phi_result (t), &lhsc);
3759 for (i = 0; i < gimple_phi_num_args (t); i++)
3761 tree strippedrhs = PHI_ARG_DEF (t, i);
3763 STRIP_NOPS (strippedrhs);
3764 get_constraint_for (gimple_phi_arg_def (t, i), &rhsc);
3766 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3768 struct constraint_expr *c2;
3769 while (VEC_length (ce_s, rhsc) > 0)
3771 c2 = VEC_last (ce_s, rhsc);
3772 process_constraint (new_constraint (*c, *c2));
3773 VEC_pop (ce_s, rhsc);
3779 /* In IPA mode, we need to generate constraints to pass call
3780 arguments through their calls. There are two cases,
3781 either a GIMPLE_CALL returning a value, or just a plain
3782 GIMPLE_CALL when we are not.
3784 In non-ipa mode, we need to generate constraints for each
3785 pointer passed by address. */
3786 else if (is_gimple_call (t))
3788 tree fndecl = gimple_call_fndecl (t);
3789 if (fndecl != NULL_TREE
3790 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
3791 /* ??? All builtins that are handled here need to be handled
3792 in the alias-oracle query functions explicitly! */
3793 switch (DECL_FUNCTION_CODE (fndecl))
3795 /* All the following functions return a pointer to the same object
3796 as their first argument points to. The functions do not add
3797 to the ESCAPED solution. The functions make the first argument
3798 pointed to memory point to what the second argument pointed to
3799 memory points to. */
3800 case BUILT_IN_STRCPY:
3801 case BUILT_IN_STRNCPY:
3802 case BUILT_IN_BCOPY:
3803 case BUILT_IN_MEMCPY:
3804 case BUILT_IN_MEMMOVE:
3805 case BUILT_IN_MEMPCPY:
3806 case BUILT_IN_STPCPY:
3807 case BUILT_IN_STPNCPY:
3808 case BUILT_IN_STRCAT:
3809 case BUILT_IN_STRNCAT:
3811 tree res = gimple_call_lhs (t);
3812 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
3813 == BUILT_IN_BCOPY ? 1 : 0));
3814 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
3815 == BUILT_IN_BCOPY ? 0 : 1));
3816 if (res != NULL_TREE)
3818 get_constraint_for (res, &lhsc);
3819 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
3820 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
3821 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY)
3822 get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
3824 get_constraint_for (dest, &rhsc);
3825 process_all_all_constraints (lhsc, rhsc);
3826 VEC_free (ce_s, heap, lhsc);
3827 VEC_free (ce_s, heap, rhsc);
3829 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
3830 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
3833 process_all_all_constraints (lhsc, rhsc);
3834 VEC_free (ce_s, heap, lhsc);
3835 VEC_free (ce_s, heap, rhsc);
3838 case BUILT_IN_MEMSET:
3840 tree res = gimple_call_lhs (t);
3841 tree dest = gimple_call_arg (t, 0);
3844 struct constraint_expr ac;
3845 if (res != NULL_TREE)
3847 get_constraint_for (res, &lhsc);
3848 get_constraint_for (dest, &rhsc);
3849 process_all_all_constraints (lhsc, rhsc);
3850 VEC_free (ce_s, heap, lhsc);
3851 VEC_free (ce_s, heap, rhsc);
3853 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
3855 if (flag_delete_null_pointer_checks
3856 && integer_zerop (gimple_call_arg (t, 1)))
3858 ac.type = ADDRESSOF;
3859 ac.var = nothing_id;
3864 ac.var = integer_id;
3867 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3868 process_constraint (new_constraint (*lhsp, ac));
3869 VEC_free (ce_s, heap, lhsc);
3872 /* All the following functions do not return pointers, do not
3873 modify the points-to sets of memory reachable from their
3874 arguments and do not add to the ESCAPED solution. */
3875 case BUILT_IN_SINCOS:
3876 case BUILT_IN_SINCOSF:
3877 case BUILT_IN_SINCOSL:
3878 case BUILT_IN_FREXP:
3879 case BUILT_IN_FREXPF:
3880 case BUILT_IN_FREXPL:
3881 case BUILT_IN_GAMMA_R:
3882 case BUILT_IN_GAMMAF_R:
3883 case BUILT_IN_GAMMAL_R:
3884 case BUILT_IN_LGAMMA_R:
3885 case BUILT_IN_LGAMMAF_R:
3886 case BUILT_IN_LGAMMAL_R:
3888 case BUILT_IN_MODFF:
3889 case BUILT_IN_MODFL:
3890 case BUILT_IN_REMQUO:
3891 case BUILT_IN_REMQUOF:
3892 case BUILT_IN_REMQUOL:
3895 /* printf-style functions may have hooks to set pointers to
3896 point to somewhere into the generated string. Leave them
3897 for a later excercise... */
3899 /* Fallthru to general call handling. */;
3903 && !lookup_vi_for_tree (fndecl)))
3905 VEC(ce_s, heap) *rhsc = NULL;
3906 int flags = gimple_call_flags (t);
3908 /* Const functions can return their arguments and addresses
3909 of global memory but not of escaped memory. */
3910 if (flags & (ECF_CONST|ECF_NOVOPS))
3912 if (gimple_call_lhs (t)
3913 && could_have_pointers (gimple_call_lhs (t)))
3914 handle_const_call (t, &rhsc);
3916 /* Pure functions can return addresses in and of memory
3917 reachable from their arguments, but they are not an escape
3918 point for reachable memory of their arguments. */
3919 else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE))
3920 handle_pure_call (t, &rhsc);
3922 handle_rhs_call (t, &rhsc);
3923 if (gimple_call_lhs (t)
3924 && could_have_pointers (gimple_call_lhs (t)))
3925 handle_lhs_call (gimple_call_lhs (t), flags, rhsc, fndecl);
3926 VEC_free (ce_s, heap, rhsc);
3936 lhsop = gimple_call_lhs (t);
3937 decl = gimple_call_fndecl (t);
3939 /* If we can directly resolve the function being called, do so.
3940 Otherwise, it must be some sort of indirect expression that
3941 we should still be able to handle. */
3943 fi = get_vi_for_tree (decl);
3946 decl = gimple_call_fn (t);
3947 fi = get_vi_for_tree (decl);
3950 /* Assign all the passed arguments to the appropriate incoming
3951 parameters of the function. */
3952 for (j = 0; j < gimple_call_num_args (t); j++)
3954 struct constraint_expr lhs ;
3955 struct constraint_expr *rhsp;
3956 tree arg = gimple_call_arg (t, j);
3958 get_constraint_for (arg, &rhsc);
3959 if (TREE_CODE (decl) != FUNCTION_DECL)
3968 lhs.var = first_vi_for_offset (fi, i)->id;
3971 while (VEC_length (ce_s, rhsc) != 0)
3973 rhsp = VEC_last (ce_s, rhsc);
3974 process_constraint (new_constraint (lhs, *rhsp));
3975 VEC_pop (ce_s, rhsc);
3980 /* If we are returning a value, assign it to the result. */
3983 struct constraint_expr rhs;
3984 struct constraint_expr *lhsp;
3987 get_constraint_for (lhsop, &lhsc);
3988 if (TREE_CODE (decl) != FUNCTION_DECL)
3997 rhs.var = first_vi_for_offset (fi, i)->id;
4000 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
4001 process_constraint (new_constraint (*lhsp, rhs));
4005 /* Otherwise, just a regular assignment statement. Only care about
4006 operations with pointer result, others are dealt with as escape
4007 points if they have pointer operands. */
4008 else if (is_gimple_assign (t)
4009 && could_have_pointers (gimple_assign_lhs (t)))
4011 /* Otherwise, just a regular assignment statement. */
4012 tree lhsop = gimple_assign_lhs (t);
4013 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
4015 if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
4016 do_structure_copy (lhsop, rhsop);
4019 struct constraint_expr temp;
4020 get_constraint_for (lhsop, &lhsc);
4022 if (gimple_assign_rhs_code (t) == POINTER_PLUS_EXPR)
4023 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
4024 gimple_assign_rhs2 (t), &rhsc);
4025 else if ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
4026 && !(POINTER_TYPE_P (gimple_expr_type (t))
4027 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
4028 || gimple_assign_single_p (t))
4029 get_constraint_for (rhsop, &rhsc);
4032 temp.type = ADDRESSOF;
4033 temp.var = anything_id;
4035 VEC_safe_push (ce_s, heap, rhsc, &temp);
4037 process_all_all_constraints (lhsc, rhsc);
4039 /* If there is a store to a global variable the rhs escapes. */
4040 if ((lhsop = get_base_address (lhsop)) != NULL_TREE
4042 && is_global_var (lhsop))
4043 make_escape_constraint (rhsop);
4044 /* If this is a conversion of a non-restrict pointer to a
4045 restrict pointer track it with a new heapvar. */
4046 else if (gimple_assign_cast_p (t)
4047 && POINTER_TYPE_P (TREE_TYPE (rhsop))
4048 && POINTER_TYPE_P (TREE_TYPE (lhsop))
4049 && !TYPE_RESTRICT (TREE_TYPE (rhsop))
4050 && TYPE_RESTRICT (TREE_TYPE (lhsop)))
4051 make_constraint_from_restrict (get_vi_for_tree (lhsop),
4054 /* For conversions of pointers to non-pointers the pointer escapes. */
4055 else if (gimple_assign_cast_p (t)
4056 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (t)))
4057 && !POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (t))))
4059 make_escape_constraint (gimple_assign_rhs1 (t));
4061 /* Handle escapes through return. */
4062 else if (gimple_code (t) == GIMPLE_RETURN
4063 && gimple_return_retval (t) != NULL_TREE
4064 && could_have_pointers (gimple_return_retval (t)))
4066 make_escape_constraint (gimple_return_retval (t));
4068 /* Handle asms conservatively by adding escape constraints to everything. */
4069 else if (gimple_code (t) == GIMPLE_ASM)
4071 unsigned i, noutputs;
4072 const char **oconstraints;
4073 const char *constraint;
4074 bool allows_mem, allows_reg, is_inout;
4076 noutputs = gimple_asm_noutputs (t);
4077 oconstraints = XALLOCAVEC (const char *, noutputs);
4079 for (i = 0; i < noutputs; ++i)
4081 tree link = gimple_asm_output_op (t, i);
4082 tree op = TREE_VALUE (link);
4084 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4085 oconstraints[i] = constraint;
4086 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
4087 &allows_reg, &is_inout);
4089 /* A memory constraint makes the address of the operand escape. */
4090 if (!allows_reg && allows_mem)
4091 make_escape_constraint (build_fold_addr_expr (op));
4093 /* The asm may read global memory, so outputs may point to
4094 any global memory. */
4095 if (op && could_have_pointers (op))
4097 VEC(ce_s, heap) *lhsc = NULL;
4098 struct constraint_expr rhsc, *lhsp;
4100 get_constraint_for (op, &lhsc);
4101 rhsc.var = nonlocal_id;
4104 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
4105 process_constraint (new_constraint (*lhsp, rhsc));
4106 VEC_free (ce_s, heap, lhsc);
4109 for (i = 0; i < gimple_asm_ninputs (t); ++i)
4111 tree link = gimple_asm_input_op (t, i);
4112 tree op = TREE_VALUE (link);
4114 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
4116 parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
4117 &allows_mem, &allows_reg);
4119 /* A memory constraint makes the address of the operand escape. */
4120 if (!allows_reg && allows_mem)
4121 make_escape_constraint (build_fold_addr_expr (op));
4122 /* Strictly we'd only need the constraint to ESCAPED if
4123 the asm clobbers memory, otherwise using something
4124 along the lines of per-call clobbers/uses would be enough. */
4125 else if (op && could_have_pointers (op))
4126 make_escape_constraint (op);
4130 VEC_free (ce_s, heap, rhsc);
4131 VEC_free (ce_s, heap, lhsc);
4135 /* Find the first varinfo in the same variable as START that overlaps with
4136 OFFSET. Return NULL if we can't find one. */
4139 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
4141 /* If the offset is outside of the variable, bail out. */
4142 if (offset >= start->fullsize)
4145 /* If we cannot reach offset from start, lookup the first field
4146 and start from there. */
4147 if (start->offset > offset)
4148 start = lookup_vi_for_tree (start->decl);
4152 /* We may not find a variable in the field list with the actual
4153 offset when when we have glommed a structure to a variable.
4154 In that case, however, offset should still be within the size
4156 if (offset >= start->offset
4157 && (offset - start->offset) < start->size)
4166 /* Find the first varinfo in the same variable as START that overlaps with
4167 OFFSET. If there is no such varinfo the varinfo directly preceding
4168 OFFSET is returned. */
4171 first_or_preceding_vi_for_offset (varinfo_t start,
4172 unsigned HOST_WIDE_INT offset)
4174 /* If we cannot reach offset from start, lookup the first field
4175 and start from there. */
4176 if (start->offset > offset)
4177 start = lookup_vi_for_tree (start->decl);
4179 /* We may not find a variable in the field list with the actual
4180 offset when when we have glommed a structure to a variable.
4181 In that case, however, offset should still be within the size
4183 If we got beyond the offset we look for return the field
4184 directly preceding offset which may be the last field. */
4186 && offset >= start->offset
4187 && !((offset - start->offset) < start->size))
4188 start = start->next;
4194 /* Insert the varinfo FIELD into the field list for BASE, at the front
4198 insert_into_field_list (varinfo_t base, varinfo_t field)
4200 varinfo_t prev = base;
4201 varinfo_t curr = base->next;
4207 /* Insert the varinfo FIELD into the field list for BASE, ordered by
4211 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
4213 varinfo_t prev = base;
4214 varinfo_t curr = base->next;
4225 if (field->offset <= curr->offset)
4230 field->next = prev->next;
4235 /* This structure is used during pushing fields onto the fieldstack
4236 to track the offset of the field, since bitpos_of_field gives it
4237 relative to its immediate containing type, and we want it relative
4238 to the ultimate containing object. */
4242 /* Offset from the base of the base containing object to this field. */
4243 HOST_WIDE_INT offset;
4245 /* Size, in bits, of the field. */
4246 unsigned HOST_WIDE_INT size;
4248 unsigned has_unknown_size : 1;
4250 unsigned may_have_pointers : 1;
4252 unsigned only_restrict_pointers : 1;
4254 typedef struct fieldoff fieldoff_s;
4256 DEF_VEC_O(fieldoff_s);
4257 DEF_VEC_ALLOC_O(fieldoff_s,heap);
4259 /* qsort comparison function for two fieldoff's PA and PB */
4262 fieldoff_compare (const void *pa, const void *pb)
4264 const fieldoff_s *foa = (const fieldoff_s *)pa;
4265 const fieldoff_s *fob = (const fieldoff_s *)pb;
4266 unsigned HOST_WIDE_INT foasize, fobsize;
4268 if (foa->offset < fob->offset)
4270 else if (foa->offset > fob->offset)
4273 foasize = foa->size;
4274 fobsize = fob->size;
4275 if (foasize < fobsize)
4277 else if (foasize > fobsize)
4282 /* Sort a fieldstack according to the field offset and sizes. */
4284 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
4286 qsort (VEC_address (fieldoff_s, fieldstack),
4287 VEC_length (fieldoff_s, fieldstack),
4288 sizeof (fieldoff_s),
4292 /* Return true if V is a tree that we can have subvars for.
4293 Normally, this is any aggregate type. Also complex
4294 types which are not gimple registers can have subvars. */
4297 var_can_have_subvars (const_tree v)
4299 /* Volatile variables should never have subvars. */
4300 if (TREE_THIS_VOLATILE (v))
4303 /* Non decls or memory tags can never have subvars. */
4307 /* Aggregates without overlapping fields can have subvars. */
4308 if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
4314 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4315 the fields of TYPE onto fieldstack, recording their offsets along
4318 OFFSET is used to keep track of the offset in this entire
4319 structure, rather than just the immediately containing structure.
4320 Returns the number of fields pushed. */
4323 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
4324 HOST_WIDE_INT offset)
4329 if (TREE_CODE (type) != RECORD_TYPE)
4332 /* If the vector of fields is growing too big, bail out early.
4333 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4335 if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
4338 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
4339 if (TREE_CODE (field) == FIELD_DECL)
4343 HOST_WIDE_INT foff = bitpos_of_field (field);
4345 if (!var_can_have_subvars (field)
4346 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
4347 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
4349 else if (!(pushed = push_fields_onto_fieldstack
4350 (TREE_TYPE (field), fieldstack, offset + foff))
4351 && (DECL_SIZE (field)
4352 && !integer_zerop (DECL_SIZE (field))))
4353 /* Empty structures may have actual size, like in C++. So
4354 see if we didn't push any subfields and the size is
4355 nonzero, push the field onto the stack. */
4360 fieldoff_s *pair = NULL;
4361 bool has_unknown_size = false;
4363 if (!VEC_empty (fieldoff_s, *fieldstack))
4364 pair = VEC_last (fieldoff_s, *fieldstack);
4366 if (!DECL_SIZE (field)
4367 || !host_integerp (DECL_SIZE (field), 1))
4368 has_unknown_size = true;
4370 /* If adjacent fields do not contain pointers merge them. */
4372 && !pair->may_have_pointers
4373 && !could_have_pointers (field)
4374 && !pair->has_unknown_size
4375 && !has_unknown_size
4376 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
4378 pair = VEC_last (fieldoff_s, *fieldstack);
4379 pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
4383 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
4384 pair->offset = offset + foff;
4385 pair->has_unknown_size = has_unknown_size;
4386 if (!has_unknown_size)
4387 pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
4390 pair->may_have_pointers = could_have_pointers (field);
4391 pair->only_restrict_pointers
4392 = (!has_unknown_size
4393 && POINTER_TYPE_P (TREE_TYPE (field))
4394 && TYPE_RESTRICT (TREE_TYPE (field)));
4405 /* Count the number of arguments DECL has, and set IS_VARARGS to true
4406 if it is a varargs function. */
4409 count_num_arguments (tree decl, bool *is_varargs)
4411 unsigned int num = 0;
4414 /* Capture named arguments for K&R functions. They do not
4415 have a prototype and thus no TYPE_ARG_TYPES. */
4416 for (t = DECL_ARGUMENTS (decl); t; t = TREE_CHAIN (t))
4419 /* Check if the function has variadic arguments. */
4420 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); t; t = TREE_CHAIN (t))
4421 if (TREE_VALUE (t) == void_type_node)
4429 /* Creation function node for DECL, using NAME, and return the index
4430 of the variable we've created for the function. */
4433 create_function_info_for (tree decl, const char *name)
4438 bool is_varargs = false;
4440 /* Create the variable info. */
4442 vi = new_var_info (decl, name);
4445 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
4446 insert_vi_for_tree (vi->decl, vi);
4450 /* If it's varargs, we don't know how many arguments it has, so we
4456 vi->is_unknown_size_var = true;
4460 arg = DECL_ARGUMENTS (decl);
4462 /* Set up variables for each argument. */
4463 for (i = 1; i < vi->fullsize; i++)
4466 const char *newname;
4468 tree argdecl = decl;
4473 asprintf (&tempname, "%s.arg%d", name, i-1);
4474 newname = ggc_strdup (tempname);
4477 argvi = new_var_info (argdecl, newname);
4480 argvi->is_full_var = true;
4481 argvi->fullsize = vi->fullsize;
4482 insert_into_field_list_sorted (vi, argvi);
4483 stats.total_vars ++;
4486 insert_vi_for_tree (arg, argvi);
4487 arg = TREE_CHAIN (arg);
4491 /* Create a variable for the return var. */
4492 if (DECL_RESULT (decl) != NULL
4493 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
4496 const char *newname;
4498 tree resultdecl = decl;
4502 if (DECL_RESULT (decl))
4503 resultdecl = DECL_RESULT (decl);
4505 asprintf (&tempname, "%s.result", name);
4506 newname = ggc_strdup (tempname);
4509 resultvi = new_var_info (resultdecl, newname);
4510 resultvi->offset = i;
4512 resultvi->fullsize = vi->fullsize;
4513 resultvi->is_full_var = true;
4514 insert_into_field_list_sorted (vi, resultvi);
4515 stats.total_vars ++;
4516 if (DECL_RESULT (decl))
4517 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
4524 /* Return true if FIELDSTACK contains fields that overlap.
4525 FIELDSTACK is assumed to be sorted by offset. */
4528 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
4530 fieldoff_s *fo = NULL;
4532 HOST_WIDE_INT lastoffset = -1;
4534 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4536 if (fo->offset == lastoffset)
4538 lastoffset = fo->offset;
4543 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4544 This will also create any varinfo structures necessary for fields
4548 create_variable_info_for (tree decl, const char *name)
4551 tree decl_type = TREE_TYPE (decl);
4552 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
4553 VEC (fieldoff_s,heap) *fieldstack = NULL;
4555 if (var_can_have_subvars (decl) && use_field_sensitive)
4556 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
4558 /* If the variable doesn't have subvars, we may end up needing to
4559 sort the field list and create fake variables for all the
4561 vi = new_var_info (decl, name);
4563 vi->may_have_pointers = could_have_pointers (decl);
4565 || !host_integerp (declsize, 1))
4567 vi->is_unknown_size_var = true;
4573 vi->fullsize = TREE_INT_CST_LOW (declsize);
4574 vi->size = vi->fullsize;
4577 insert_vi_for_tree (vi->decl, vi);
4578 if (vi->is_global_var
4579 && (!flag_whole_program || !in_ipa_mode)
4580 && vi->may_have_pointers)
4582 if (POINTER_TYPE_P (TREE_TYPE (decl))
4583 && TYPE_RESTRICT (TREE_TYPE (decl)))
4584 make_constraint_from_restrict (vi, "GLOBAL_RESTRICT");
4585 make_copy_constraint (vi, nonlocal_id);
4589 if (use_field_sensitive
4590 && !vi->is_unknown_size_var
4591 && var_can_have_subvars (decl)
4592 && VEC_length (fieldoff_s, fieldstack) > 1
4593 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4595 fieldoff_s *fo = NULL;
4596 bool notokay = false;
4599 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4601 if (fo->has_unknown_size
4609 /* We can't sort them if we have a field with a variable sized type,
4610 which will make notokay = true. In that case, we are going to return
4611 without creating varinfos for the fields anyway, so sorting them is a
4615 sort_fieldstack (fieldstack);
4616 /* Due to some C++ FE issues, like PR 22488, we might end up
4617 what appear to be overlapping fields even though they,
4618 in reality, do not overlap. Until the C++ FE is fixed,
4619 we will simply disable field-sensitivity for these cases. */
4620 notokay = check_for_overlaps (fieldstack);
4624 if (VEC_length (fieldoff_s, fieldstack) != 0)
4625 fo = VEC_index (fieldoff_s, fieldstack, 0);
4627 if (fo == NULL || notokay)
4629 vi->is_unknown_size_var = 1;
4632 vi->is_full_var = true;
4633 VEC_free (fieldoff_s, heap, fieldstack);
4637 vi->size = fo->size;
4638 vi->offset = fo->offset;
4639 vi->may_have_pointers = fo->may_have_pointers;
4640 if (vi->is_global_var
4641 && (!flag_whole_program || !in_ipa_mode)
4642 && vi->may_have_pointers)
4644 if (fo->only_restrict_pointers)
4645 make_constraint_from_restrict (vi, "GLOBAL_RESTRICT");
4647 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4648 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4652 const char *newname = "NULL";
4657 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
4658 "+" HOST_WIDE_INT_PRINT_DEC,
4659 vi->name, fo->offset, fo->size);
4660 newname = ggc_strdup (tempname);
4663 newvi = new_var_info (decl, newname);
4664 newvi->offset = fo->offset;
4665 newvi->size = fo->size;
4666 newvi->fullsize = vi->fullsize;
4667 newvi->may_have_pointers = fo->may_have_pointers;
4668 insert_into_field_list (vi, newvi);
4669 if ((newvi->is_global_var || TREE_CODE (decl) == PARM_DECL)
4670 && newvi->may_have_pointers)
4672 if (fo->only_restrict_pointers)
4673 make_constraint_from_restrict (newvi, "GLOBAL_RESTRICT");
4674 if (newvi->is_global_var && !in_ipa_mode)
4675 make_copy_constraint (newvi, nonlocal_id);
4682 vi->is_full_var = true;
4684 VEC_free (fieldoff_s, heap, fieldstack);
4689 /* Print out the points-to solution for VAR to FILE. */
4692 dump_solution_for_var (FILE *file, unsigned int var)
4694 varinfo_t vi = get_varinfo (var);
4698 if (find (var) != var)
4700 varinfo_t vipt = get_varinfo (find (var));
4701 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4705 fprintf (file, "%s = { ", vi->name);
4706 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4708 fprintf (file, "%s ", get_varinfo (i)->name);
4710 fprintf (file, "}\n");
4714 /* Print the points-to solution for VAR to stdout. */
4717 debug_solution_for_var (unsigned int var)
4719 dump_solution_for_var (stdout, var);
4722 /* Create varinfo structures for all of the variables in the
4723 function for intraprocedural mode. */
4726 intra_create_variable_infos (void)
4730 /* For each incoming pointer argument arg, create the constraint ARG
4731 = NONLOCAL or a dummy variable if it is a restrict qualified
4732 passed-by-reference argument. */
4733 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4737 if (!could_have_pointers (t))
4740 /* For restrict qualified pointers to objects passed by
4741 reference build a real representative for the pointed-to object. */
4742 if (DECL_BY_REFERENCE (t)
4743 && POINTER_TYPE_P (TREE_TYPE (t))
4744 && TYPE_RESTRICT (TREE_TYPE (t)))
4746 struct constraint_expr lhsc, rhsc;
4748 tree heapvar = heapvar_lookup (t, 0);
4749 if (heapvar == NULL_TREE)
4752 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4754 DECL_EXTERNAL (heapvar) = 1;
4755 heapvar_insert (t, 0, heapvar);
4756 ann = get_var_ann (heapvar);
4757 ann->is_heapvar = 1;
4759 if (gimple_referenced_vars (cfun))
4760 add_referenced_var (heapvar);
4761 lhsc.var = get_vi_for_tree (t)->id;
4764 rhsc.var = (vi = get_vi_for_tree (heapvar))->id;
4765 rhsc.type = ADDRESSOF;
4767 process_constraint (new_constraint (lhsc, rhsc));
4768 vi->is_restrict_var = 1;
4772 for (p = get_vi_for_tree (t); p; p = p->next)
4773 if (p->may_have_pointers)
4774 make_constraint_from (p, nonlocal_id);
4775 if (POINTER_TYPE_P (TREE_TYPE (t))
4776 && TYPE_RESTRICT (TREE_TYPE (t)))
4777 make_constraint_from_restrict (get_vi_for_tree (t), "PARM_RESTRICT");
4780 /* Add a constraint for a result decl that is passed by reference. */
4781 if (DECL_RESULT (cfun->decl)
4782 && DECL_BY_REFERENCE (DECL_RESULT (cfun->decl)))
4784 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
4786 for (p = result_vi; p; p = p->next)
4787 make_constraint_from (p, nonlocal_id);
4790 /* Add a constraint for the incoming static chain parameter. */
4791 if (cfun->static_chain_decl != NULL_TREE)
4793 varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
4795 for (p = chain_vi; p; p = p->next)
4796 make_constraint_from (p, nonlocal_id);
4800 /* Structure used to put solution bitmaps in a hashtable so they can
4801 be shared among variables with the same points-to set. */
4803 typedef struct shared_bitmap_info
4807 } *shared_bitmap_info_t;
4808 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
4810 static htab_t shared_bitmap_table;
4812 /* Hash function for a shared_bitmap_info_t */
4815 shared_bitmap_hash (const void *p)
4817 const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
4818 return bi->hashcode;
4821 /* Equality function for two shared_bitmap_info_t's. */
4824 shared_bitmap_eq (const void *p1, const void *p2)
4826 const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
4827 const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
4828 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
4831 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4832 existing instance if there is one, NULL otherwise. */
4835 shared_bitmap_lookup (bitmap pt_vars)
4838 struct shared_bitmap_info sbi;
4840 sbi.pt_vars = pt_vars;
4841 sbi.hashcode = bitmap_hash (pt_vars);
4843 slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
4844 sbi.hashcode, NO_INSERT);
4848 return ((shared_bitmap_info_t) *slot)->pt_vars;
4852 /* Add a bitmap to the shared bitmap hashtable. */
4855 shared_bitmap_add (bitmap pt_vars)
4858 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
4860 sbi->pt_vars = pt_vars;
4861 sbi->hashcode = bitmap_hash (pt_vars);
4863 slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
4864 sbi->hashcode, INSERT);
4865 gcc_assert (!*slot);
4866 *slot = (void *) sbi;
4870 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
4873 set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt)
4878 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4880 varinfo_t vi = get_varinfo (i);
4882 /* The only artificial variables that are allowed in a may-alias
4883 set are heap variables. */
4884 if (vi->is_artificial_var && !vi->is_heap_var)
4887 if (TREE_CODE (vi->decl) == VAR_DECL
4888 || TREE_CODE (vi->decl) == PARM_DECL
4889 || TREE_CODE (vi->decl) == RESULT_DECL)
4891 /* Add the decl to the points-to set. Note that the points-to
4892 set contains global variables. */
4893 bitmap_set_bit (into, DECL_UID (vi->decl));
4894 if (vi->is_global_var)
4895 pt->vars_contains_global = true;
4901 /* Compute the points-to solution *PT for the variable VI. */
4904 find_what_var_points_to (varinfo_t orig_vi, struct pt_solution *pt)
4908 bitmap finished_solution;
4912 memset (pt, 0, sizeof (struct pt_solution));
4914 /* This variable may have been collapsed, let's get the real
4916 vi = get_varinfo (find (orig_vi->id));
4918 /* Translate artificial variables into SSA_NAME_PTR_INFO
4920 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4922 varinfo_t vi = get_varinfo (i);
4924 if (vi->is_artificial_var)
4926 if (vi->id == nothing_id)
4928 else if (vi->id == escaped_id)
4930 else if (vi->id == nonlocal_id)
4932 else if (vi->is_heap_var)
4933 /* We represent heapvars in the points-to set properly. */
4935 else if (vi->id == readonly_id)
4938 else if (vi->id == anything_id
4939 || vi->id == integer_id)
4942 if (vi->is_restrict_var)
4943 pt->vars_contains_restrict = true;
4946 /* Instead of doing extra work, simply do not create
4947 elaborate points-to information for pt_anything pointers. */
4949 && (orig_vi->is_artificial_var
4950 || !pt->vars_contains_restrict))
4953 /* Share the final set of variables when possible. */
4954 finished_solution = BITMAP_GGC_ALLOC ();
4955 stats.points_to_sets_created++;
4957 set_uids_in_ptset (finished_solution, vi->solution, pt);
4958 result = shared_bitmap_lookup (finished_solution);
4961 shared_bitmap_add (finished_solution);
4962 pt->vars = finished_solution;
4967 bitmap_clear (finished_solution);
4971 /* Given a pointer variable P, fill in its points-to set. */
4974 find_what_p_points_to (tree p)
4976 struct ptr_info_def *pi;
4980 /* For parameters, get at the points-to set for the actual parm
4982 if (TREE_CODE (p) == SSA_NAME
4983 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4984 && SSA_NAME_IS_DEFAULT_DEF (p))
4985 lookup_p = SSA_NAME_VAR (p);
4987 vi = lookup_vi_for_tree (lookup_p);
4991 pi = get_ptr_info (p);
4992 find_what_var_points_to (vi, &pi->pt);
4996 /* Query statistics for points-to solutions. */
4999 unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
5000 unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
5001 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
5002 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
5006 dump_pta_stats (FILE *s)
5008 fprintf (s, "\nPTA query stats:\n");
5009 fprintf (s, " pt_solution_includes: "
5010 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
5011 HOST_WIDE_INT_PRINT_DEC" queries\n",
5012 pta_stats.pt_solution_includes_no_alias,
5013 pta_stats.pt_solution_includes_no_alias
5014 + pta_stats.pt_solution_includes_may_alias);
5015 fprintf (s, " pt_solutions_intersect: "
5016 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
5017 HOST_WIDE_INT_PRINT_DEC" queries\n",
5018 pta_stats.pt_solutions_intersect_no_alias,
5019 pta_stats.pt_solutions_intersect_no_alias
5020 + pta_stats.pt_solutions_intersect_may_alias);
5024 /* Reset the points-to solution *PT to a conservative default
5025 (point to anything). */
5028 pt_solution_reset (struct pt_solution *pt)
5030 memset (pt, 0, sizeof (struct pt_solution));
5031 pt->anything = true;
5034 /* Set the points-to solution *PT to point only to the variables
5038 pt_solution_set (struct pt_solution *pt, bitmap vars)
5043 memset (pt, 0, sizeof (struct pt_solution));
5045 EXECUTE_IF_SET_IN_BITMAP (vars, 0, i, bi)
5047 tree var = referenced_var_lookup (i);
5048 if (is_global_var (var))
5050 pt->vars_contains_global = true;
5056 /* Return true if the points-to solution *PT is empty. */
5059 pt_solution_empty_p (struct pt_solution *pt)
5066 && !bitmap_empty_p (pt->vars))
5069 /* If the solution includes ESCAPED, check if that is empty. */
5071 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
5077 /* Return true if the points-to solution *PT includes global memory. */
5080 pt_solution_includes_global (struct pt_solution *pt)
5084 || pt->vars_contains_global)
5088 return pt_solution_includes_global (&cfun->gimple_df->escaped);
5093 /* Return true if the points-to solution *PT includes the variable
5094 declaration DECL. */
5097 pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
5103 && is_global_var (decl))
5107 && bitmap_bit_p (pt->vars, DECL_UID (decl)))
5110 /* If the solution includes ESCAPED, check it. */
5112 && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
5119 pt_solution_includes (struct pt_solution *pt, const_tree decl)
5121 bool res = pt_solution_includes_1 (pt, decl);
5123 ++pta_stats.pt_solution_includes_may_alias;
5125 ++pta_stats.pt_solution_includes_no_alias;
5129 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
5133 pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
5135 if (pt1->anything || pt2->anything)
5138 /* If either points to unknown global memory and the other points to
5139 any global memory they alias. */
5142 || pt2->vars_contains_global))
5144 && pt1->vars_contains_global))
5147 /* Check the escaped solution if required. */
5148 if ((pt1->escaped || pt2->escaped)
5149 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
5151 /* If both point to escaped memory and that solution
5152 is not empty they alias. */
5153 if (pt1->escaped && pt2->escaped)
5156 /* If either points to escaped memory see if the escaped solution
5157 intersects with the other. */
5159 && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt2))
5161 && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt1)))
5165 /* Now both pointers alias if their points-to solution intersects. */
5168 && bitmap_intersect_p (pt1->vars, pt2->vars));
5172 pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
5174 bool res = pt_solutions_intersect_1 (pt1, pt2);
5176 ++pta_stats.pt_solutions_intersect_may_alias;
5178 ++pta_stats.pt_solutions_intersect_no_alias;
5182 /* Return true if both points-to solutions PT1 and PT2 for two restrict
5183 qualified pointers are possibly based on the same pointer. */
5186 pt_solutions_same_restrict_base (struct pt_solution *pt1,
5187 struct pt_solution *pt2)
5189 /* If we deal with points-to solutions of two restrict qualified
5190 pointers solely rely on the pointed-to variable bitmap intersection.
5191 For two pointers that are based on each other the bitmaps will
5193 if (pt1->vars_contains_restrict
5194 && pt2->vars_contains_restrict)
5196 gcc_assert (pt1->vars && pt2->vars);
5197 return bitmap_intersect_p (pt1->vars, pt2->vars);
5204 /* Dump points-to information to OUTFILE. */
5207 dump_sa_points_to_info (FILE *outfile)
5211 fprintf (outfile, "\nPoints-to sets\n\n");
5213 if (dump_flags & TDF_STATS)
5215 fprintf (outfile, "Stats:\n");
5216 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
5217 fprintf (outfile, "Non-pointer vars: %d\n",
5218 stats.nonpointer_vars);
5219 fprintf (outfile, "Statically unified vars: %d\n",
5220 stats.unified_vars_static);
5221 fprintf (outfile, "Dynamically unified vars: %d\n",
5222 stats.unified_vars_dynamic);
5223 fprintf (outfile, "Iterations: %d\n", stats.iterations);
5224 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
5225 fprintf (outfile, "Number of implicit edges: %d\n",
5226 stats.num_implicit_edges);
5229 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
5230 dump_solution_for_var (outfile, i);
5234 /* Debug points-to information to stderr. */
5237 debug_sa_points_to_info (void)
5239 dump_sa_points_to_info (stderr);
5243 /* Initialize the always-existing constraint variables for NULL
5244 ANYTHING, READONLY, and INTEGER */
5247 init_base_vars (void)
5249 struct constraint_expr lhs, rhs;
5250 varinfo_t var_anything;
5251 varinfo_t var_nothing;
5252 varinfo_t var_readonly;
5253 varinfo_t var_escaped;
5254 varinfo_t var_nonlocal;
5255 varinfo_t var_storedanything;
5256 varinfo_t var_integer;
5258 /* Create the NULL variable, used to represent that a variable points
5260 var_nothing = new_var_info (NULL_TREE, "NULL");
5261 gcc_assert (var_nothing->id == nothing_id);
5262 var_nothing->is_artificial_var = 1;
5263 var_nothing->offset = 0;
5264 var_nothing->size = ~0;
5265 var_nothing->fullsize = ~0;
5266 var_nothing->is_special_var = 1;
5268 /* Create the ANYTHING variable, used to represent that a variable
5269 points to some unknown piece of memory. */
5270 var_anything = new_var_info (NULL_TREE, "ANYTHING");
5271 gcc_assert (var_anything->id == anything_id);
5272 var_anything->is_artificial_var = 1;
5273 var_anything->size = ~0;
5274 var_anything->offset = 0;
5275 var_anything->next = NULL;
5276 var_anything->fullsize = ~0;
5277 var_anything->is_special_var = 1;
5279 /* Anything points to anything. This makes deref constraints just
5280 work in the presence of linked list and other p = *p type loops,
5281 by saying that *ANYTHING = ANYTHING. */
5283 lhs.var = anything_id;
5285 rhs.type = ADDRESSOF;
5286 rhs.var = anything_id;
5289 /* This specifically does not use process_constraint because
5290 process_constraint ignores all anything = anything constraints, since all
5291 but this one are redundant. */
5292 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
5294 /* Create the READONLY variable, used to represent that a variable
5295 points to readonly memory. */
5296 var_readonly = new_var_info (NULL_TREE, "READONLY");
5297 gcc_assert (var_readonly->id == readonly_id);
5298 var_readonly->is_artificial_var = 1;
5299 var_readonly->offset = 0;
5300 var_readonly->size = ~0;
5301 var_readonly->fullsize = ~0;
5302 var_readonly->next = NULL;
5303 var_readonly->is_special_var = 1;
5305 /* readonly memory points to anything, in order to make deref
5306 easier. In reality, it points to anything the particular
5307 readonly variable can point to, but we don't track this
5310 lhs.var = readonly_id;
5312 rhs.type = ADDRESSOF;
5313 rhs.var = readonly_id; /* FIXME */
5315 process_constraint (new_constraint (lhs, rhs));
5317 /* Create the ESCAPED variable, used to represent the set of escaped
5319 var_escaped = new_var_info (NULL_TREE, "ESCAPED");
5320 gcc_assert (var_escaped->id == escaped_id);
5321 var_escaped->is_artificial_var = 1;
5322 var_escaped->offset = 0;
5323 var_escaped->size = ~0;
5324 var_escaped->fullsize = ~0;
5325 var_escaped->is_special_var = 0;
5327 /* Create the NONLOCAL variable, used to represent the set of nonlocal
5329 var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL");
5330 gcc_assert (var_nonlocal->id == nonlocal_id);
5331 var_nonlocal->is_artificial_var = 1;
5332 var_nonlocal->offset = 0;
5333 var_nonlocal->size = ~0;
5334 var_nonlocal->fullsize = ~0;
5335 var_nonlocal->is_special_var = 1;
5337 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
5339 lhs.var = escaped_id;
5342 rhs.var = escaped_id;
5344 process_constraint (new_constraint (lhs, rhs));
5346 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
5347 whole variable escapes. */
5349 lhs.var = escaped_id;
5352 rhs.var = escaped_id;
5353 rhs.offset = UNKNOWN_OFFSET;
5354 process_constraint (new_constraint (lhs, rhs));
5356 /* *ESCAPED = NONLOCAL. This is true because we have to assume
5357 everything pointed to by escaped points to what global memory can
5360 lhs.var = escaped_id;
5363 rhs.var = nonlocal_id;
5365 process_constraint (new_constraint (lhs, rhs));
5367 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
5368 global memory may point to global memory and escaped memory. */
5370 lhs.var = nonlocal_id;
5372 rhs.type = ADDRESSOF;
5373 rhs.var = nonlocal_id;
5375 process_constraint (new_constraint (lhs, rhs));
5376 rhs.type = ADDRESSOF;
5377 rhs.var = escaped_id;
5379 process_constraint (new_constraint (lhs, rhs));
5381 /* Create the STOREDANYTHING variable, used to represent the set of
5382 variables stored to *ANYTHING. */
5383 var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING");
5384 gcc_assert (var_storedanything->id == storedanything_id);
5385 var_storedanything->is_artificial_var = 1;
5386 var_storedanything->offset = 0;
5387 var_storedanything->size = ~0;
5388 var_storedanything->fullsize = ~0;
5389 var_storedanything->is_special_var = 0;
5391 /* Create the INTEGER variable, used to represent that a variable points
5392 to what an INTEGER "points to". */
5393 var_integer = new_var_info (NULL_TREE, "INTEGER");
5394 gcc_assert (var_integer->id == integer_id);
5395 var_integer->is_artificial_var = 1;
5396 var_integer->size = ~0;
5397 var_integer->fullsize = ~0;
5398 var_integer->offset = 0;
5399 var_integer->next = NULL;
5400 var_integer->is_special_var = 1;
5402 /* INTEGER = ANYTHING, because we don't know where a dereference of
5403 a random integer will point to. */
5405 lhs.var = integer_id;
5407 rhs.type = ADDRESSOF;
5408 rhs.var = anything_id;
5410 process_constraint (new_constraint (lhs, rhs));
5413 /* Initialize things necessary to perform PTA */
5416 init_alias_vars (void)
5418 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
5420 bitmap_obstack_initialize (&pta_obstack);
5421 bitmap_obstack_initialize (&oldpta_obstack);
5422 bitmap_obstack_initialize (&predbitmap_obstack);
5424 constraint_pool = create_alloc_pool ("Constraint pool",
5425 sizeof (struct constraint), 30);
5426 variable_info_pool = create_alloc_pool ("Variable info pool",
5427 sizeof (struct variable_info), 30);
5428 constraints = VEC_alloc (constraint_t, heap, 8);
5429 varmap = VEC_alloc (varinfo_t, heap, 8);
5430 vi_for_tree = pointer_map_create ();
5431 call_stmt_vars = pointer_map_create ();
5433 memset (&stats, 0, sizeof (stats));
5434 shared_bitmap_table = htab_create (511, shared_bitmap_hash,
5435 shared_bitmap_eq, free);
5439 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
5440 predecessor edges. */
5443 remove_preds_and_fake_succs (constraint_graph_t graph)
5447 /* Clear the implicit ref and address nodes from the successor
5449 for (i = 0; i < FIRST_REF_NODE; i++)
5451 if (graph->succs[i])
5452 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
5453 FIRST_REF_NODE * 2);
5456 /* Free the successor list for the non-ref nodes. */
5457 for (i = FIRST_REF_NODE; i < graph->size; i++)
5459 if (graph->succs[i])
5460 BITMAP_FREE (graph->succs[i]);
5463 /* Now reallocate the size of the successor list as, and blow away
5464 the predecessor bitmaps. */
5465 graph->size = VEC_length (varinfo_t, varmap);
5466 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
5468 free (graph->implicit_preds);
5469 graph->implicit_preds = NULL;
5470 free (graph->preds);
5471 graph->preds = NULL;
5472 bitmap_obstack_release (&predbitmap_obstack);
5475 /* Initialize the heapvar for statement mapping. */
5478 init_alias_heapvars (void)
5480 if (!heapvar_for_stmt)
5481 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, heapvar_map_eq,
5485 /* Delete the heapvar for statement mapping. */
5488 delete_alias_heapvars (void)
5490 if (heapvar_for_stmt)
5491 htab_delete (heapvar_for_stmt);
5492 heapvar_for_stmt = NULL;
5495 /* Solve the constraint set. */
5498 solve_constraints (void)
5500 struct scc_info *si;
5504 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5505 dump_constraints (dump_file);
5510 "\nCollapsing static cycles and doing variable "
5513 init_graph (VEC_length (varinfo_t, varmap) * 2);
5516 fprintf (dump_file, "Building predecessor graph\n");
5517 build_pred_graph ();
5520 fprintf (dump_file, "Detecting pointer and location "
5522 si = perform_var_substitution (graph);
5525 fprintf (dump_file, "Rewriting constraints and unifying "
5527 rewrite_constraints (graph, si);
5529 build_succ_graph ();
5530 free_var_substitution_info (si);
5532 if (dump_file && (dump_flags & TDF_GRAPH))
5533 dump_constraint_graph (dump_file);
5535 move_complex_constraints (graph);
5538 fprintf (dump_file, "Uniting pointer but not location equivalent "
5540 unite_pointer_equivalences (graph);
5543 fprintf (dump_file, "Finding indirect cycles\n");
5544 find_indirect_cycles (graph);
5546 /* Implicit nodes and predecessors are no longer necessary at this
5548 remove_preds_and_fake_succs (graph);
5551 fprintf (dump_file, "Solving graph\n");
5553 solve_graph (graph);
5556 dump_sa_points_to_info (dump_file);
5559 /* Create points-to sets for the current function. See the comments
5560 at the start of the file for an algorithmic overview. */
5563 compute_points_to_sets (void)
5569 timevar_push (TV_TREE_PTA);
5572 init_alias_heapvars ();
5574 intra_create_variable_infos ();
5576 /* Now walk all statements and derive aliases. */
5579 gimple_stmt_iterator gsi;
5581 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5583 gimple phi = gsi_stmt (gsi);
5585 if (is_gimple_reg (gimple_phi_result (phi)))
5586 find_func_aliases (phi);
5589 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5591 gimple stmt = gsi_stmt (gsi);
5593 find_func_aliases (stmt);
5597 /* From the constraints compute the points-to sets. */
5598 solve_constraints ();
5600 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
5601 find_what_var_points_to (get_varinfo (escaped_id),
5602 &cfun->gimple_df->escaped);
5604 /* Make sure the ESCAPED solution (which is used as placeholder in
5605 other solutions) does not reference itself. This simplifies
5606 points-to solution queries. */
5607 cfun->gimple_df->escaped.escaped = 0;
5609 /* Mark escaped HEAP variables as global. */
5610 for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); ++i)
5612 && !vi->is_restrict_var
5613 && !vi->is_global_var)
5614 DECL_EXTERNAL (vi->decl) = vi->is_global_var
5615 = pt_solution_includes (&cfun->gimple_df->escaped, vi->decl);
5617 /* Compute the points-to sets for pointer SSA_NAMEs. */
5618 for (i = 0; i < num_ssa_names; ++i)
5620 tree ptr = ssa_name (i);
5622 && POINTER_TYPE_P (TREE_TYPE (ptr)))
5623 find_what_p_points_to (ptr);
5626 /* Compute the call-used/clobbered sets. */
5629 gimple_stmt_iterator gsi;
5631 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5633 gimple stmt = gsi_stmt (gsi);
5634 struct pt_solution *pt;
5635 if (!is_gimple_call (stmt))
5638 pt = gimple_call_use_set (stmt);
5639 if (gimple_call_flags (stmt) & ECF_CONST)
5640 memset (pt, 0, sizeof (struct pt_solution));
5641 else if ((vi = lookup_call_use_vi (stmt)) != NULL)
5643 find_what_var_points_to (vi, pt);
5644 /* Escaped (and thus nonlocal) variables are always
5645 implicitly used by calls. */
5646 /* ??? ESCAPED can be empty even though NONLOCAL
5653 /* If there is nothing special about this call then
5654 we have made everything that is used also escape. */
5655 *pt = cfun->gimple_df->escaped;
5659 pt = gimple_call_clobber_set (stmt);
5660 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
5661 memset (pt, 0, sizeof (struct pt_solution));
5662 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
5664 find_what_var_points_to (vi, pt);
5665 /* Escaped (and thus nonlocal) variables are always
5666 implicitly clobbered by calls. */
5667 /* ??? ESCAPED can be empty even though NONLOCAL
5674 /* If there is nothing special about this call then
5675 we have made everything that is used also escape. */
5676 *pt = cfun->gimple_df->escaped;
5682 timevar_pop (TV_TREE_PTA);
5686 /* Delete created points-to sets. */
5689 delete_points_to_sets (void)
5693 htab_delete (shared_bitmap_table);
5694 if (dump_file && (dump_flags & TDF_STATS))
5695 fprintf (dump_file, "Points to sets created:%d\n",
5696 stats.points_to_sets_created);
5698 pointer_map_destroy (vi_for_tree);
5699 pointer_map_destroy (call_stmt_vars);
5700 bitmap_obstack_release (&pta_obstack);
5701 VEC_free (constraint_t, heap, constraints);
5703 for (i = 0; i < graph->size; i++)
5704 VEC_free (constraint_t, heap, graph->complex[i]);
5705 free (graph->complex);
5708 free (graph->succs);
5710 free (graph->pe_rep);
5711 free (graph->indirect_cycles);
5714 VEC_free (varinfo_t, heap, varmap);
5715 free_alloc_pool (variable_info_pool);
5716 free_alloc_pool (constraint_pool);
5720 /* Compute points-to information for every SSA_NAME pointer in the
5721 current function and compute the transitive closure of escaped
5722 variables to re-initialize the call-clobber states of local variables. */
5725 compute_may_aliases (void)
5727 /* For each pointer P_i, determine the sets of variables that P_i may
5728 point-to. Compute the reachability set of escaped and call-used
5730 compute_points_to_sets ();
5732 /* Debugging dumps. */
5735 dump_alias_info (dump_file);
5737 if (dump_flags & TDF_DETAILS)
5738 dump_referenced_vars (dump_file);
5741 /* Deallocate memory used by aliasing data structures and the internal
5742 points-to solution. */
5743 delete_points_to_sets ();
5745 gcc_assert (!need_ssa_update_p (cfun));
5751 gate_tree_pta (void)
5753 return flag_tree_pta;
5756 /* A dummy pass to cause points-to information to be computed via
5757 TODO_rebuild_alias. */
5759 struct gimple_opt_pass pass_build_alias =
5764 gate_tree_pta, /* gate */
5768 0, /* static_pass_number */
5769 TV_NONE, /* tv_id */
5770 PROP_cfg | PROP_ssa, /* properties_required */
5771 0, /* properties_provided */
5772 0, /* properties_destroyed */
5773 0, /* todo_flags_start */
5774 TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */
5778 /* A dummy pass to cause points-to information to be computed via
5779 TODO_rebuild_alias. */
5781 struct gimple_opt_pass pass_build_ealias =
5785 "ealias", /* name */
5786 gate_tree_pta, /* gate */
5790 0, /* static_pass_number */
5791 TV_NONE, /* tv_id */
5792 PROP_cfg | PROP_ssa, /* properties_required */
5793 0, /* properties_provided */
5794 0, /* properties_destroyed */
5795 0, /* todo_flags_start */
5796 TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */
5801 /* Return true if we should execute IPA PTA. */
5807 /* Don't bother doing anything if the program has errors. */
5808 && !(errorcount || sorrycount));
5811 /* Execute the driver for IPA PTA. */
5813 ipa_pta_execute (void)
5815 struct cgraph_node *node;
5819 init_alias_heapvars ();
5822 /* Build the constraints. */
5823 for (node = cgraph_nodes; node; node = node->next)
5825 /* Nodes without a body are not interesting. Especially do not
5826 visit clones at this point for now - we get duplicate decls
5827 there for inline clones at least. */
5828 if (!gimple_has_body_p (node->decl)
5832 /* It does not make sense to have graph edges into or out of
5833 externally visible functions. There is no extra information
5834 we can gather from them. */
5835 if (node->local.externally_visible)
5838 create_function_info_for (node->decl,
5839 cgraph_node_name (node));
5842 for (node = cgraph_nodes; node; node = node->next)
5844 struct function *func;
5848 /* Nodes without a body are not interesting. */
5849 if (!gimple_has_body_p (node->decl)
5855 "Generating constraints for %s\n",
5856 cgraph_node_name (node));
5858 func = DECL_STRUCT_FUNCTION (node->decl);
5859 old_func_decl = current_function_decl;
5861 current_function_decl = node->decl;
5863 /* For externally visible functions use local constraints for
5864 their arguments. For local functions we see all callers
5865 and thus do not need initial constraints for parameters. */
5866 if (node->local.externally_visible)
5867 intra_create_variable_infos ();
5869 /* Build constriants for the function body. */
5870 FOR_EACH_BB_FN (bb, func)
5872 gimple_stmt_iterator gsi;
5874 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
5877 gimple phi = gsi_stmt (gsi);
5879 if (is_gimple_reg (gimple_phi_result (phi)))
5880 find_func_aliases (phi);
5883 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5885 gimple stmt = gsi_stmt (gsi);
5887 find_func_aliases (stmt);
5891 current_function_decl = old_func_decl;
5895 /* From the constraints compute the points-to sets. */
5896 solve_constraints ();
5898 delete_points_to_sets ();
5905 struct simple_ipa_opt_pass pass_ipa_pta =
5910 gate_ipa_pta, /* gate */
5911 ipa_pta_execute, /* execute */
5914 0, /* static_pass_number */
5915 TV_IPA_PTA, /* tv_id */
5916 0, /* properties_required */
5917 0, /* properties_provided */
5918 0, /* properties_destroyed */
5919 0, /* todo_flags_start */
5920 TODO_update_ssa /* todo_flags_finish */
5925 #include "gt-tree-ssa-structalias.h"