1 /* Tree based points-to analysis
2 Copyright (C) 2005 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
43 #include "tree-gimple.h"
47 #include "tree-pass.h"
49 #include "alloc-pool.h"
50 #include "splay-tree.h"
51 #include "tree-ssa-structalias.h"
53 /* The idea behind this analyzer is to generate set constraints from the
54 program, then solve the resulting constraints in order to generate the
57 Set constraints are a way of modeling program analysis problems that
58 involve sets. They consist of an inclusion constraint language,
59 describing the variables (each variable is a set) and operations that
60 are involved on the variables, and a set of rules that derive facts
61 from these operations. To solve a system of set constraints, you derive
62 all possible facts under the rules, which gives you the correct sets
65 See "Efficient Field-sensitive pointer analysis for C" by "David
66 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
67 http://citeseer.ist.psu.edu/pearce04efficient.html
69 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
70 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
71 http://citeseer.ist.psu.edu/heintze01ultrafast.html
73 There are three types of constraint expressions, DEREF, ADDRESSOF, and
74 SCALAR. Each constraint expression consists of a constraint type,
75 a variable, and an offset.
77 SCALAR is a constraint expression type used to represent x, whether
78 it appears on the LHS or the RHS of a statement.
79 DEREF is a constraint expression type used to represent *x, whether
80 it appears on the LHS or the RHS of a statement.
81 ADDRESSOF is a constraint expression used to represent &x, whether
82 it appears on the LHS or the RHS of a statement.
84 Each pointer variable in the program is assigned an integer id, and
85 each field of a structure variable is assigned an integer id as well.
87 Structure variables are linked to their list of fields through a "next
88 field" in each variable that points to the next field in offset
90 Each variable for a structure field has
92 1. "size", that tells the size in bits of that field.
93 2. "fullsize, that tells the size in bits of the entire structure.
94 3. "offset", that tells the offset in bits from the beginning of the
95 structure to this field.
107 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
108 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
109 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
112 In order to solve the system of set constraints, the following is
115 1. Each constraint variable x has a solution set associated with it,
118 2. Constraints are separated into direct, copy, and complex.
119 Direct constraints are ADDRESSOF constraints that require no extra
120 processing, such as P = &Q
121 Copy constraints are those of the form P = Q.
122 Complex constraints are all the constraints involving dereferences.
124 3. All direct constraints of the form P = &Q are processed, such
125 that Q is added to Sol(P)
127 4. All complex constraints for a given constraint variable are stored in a
128 linked list attached to that variable's node.
130 5. A directed graph is built out of the copy constraints. Each
131 constraint variable is a node in the graph, and an edge from
132 Q to P is added for each copy constraint of the form P = Q
134 6. The graph is then walked, and solution sets are
135 propagated along the copy edges, such that an edge from Q to P
136 causes Sol(P) <- Sol(P) union Sol(Q).
138 7. As we visit each node, all complex constraints associated with
139 that node are processed by adding appropriate copy edges to the graph, or the
140 appropriate variables to the solution set.
142 8. The process of walking the graph is iterated until no solution
145 Prior to walking the graph in steps 6 and 7, We perform static
146 cycle elimination on the constraint graph, as well
147 as off-line variable substitution.
149 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
150 on and turned into anything), but isn't. You can just see what offset
151 inside the pointed-to struct it's going to access.
153 TODO: Constant bounded arrays can be handled as if they were structs of the
154 same number of elements.
156 TODO: Modeling heap and incoming pointers becomes much better if we
157 add fields to them as we discover them, which we could do.
159 TODO: We could handle unions, but to be honest, it's probably not
160 worth the pain or slowdown. */
162 static bool use_field_sensitive = true;
163 static unsigned int create_variable_info_for (tree, const char *);
164 static struct constraint_expr get_constraint_for (tree);
165 static void build_constraint_graph (void);
167 static bitmap_obstack ptabitmap_obstack;
168 static bitmap_obstack iteration_obstack;
169 DEF_VEC_P(constraint_t);
170 DEF_VEC_ALLOC_P(constraint_t,heap);
172 static struct constraint_stats
174 unsigned int total_vars;
175 unsigned int collapsed_vars;
176 unsigned int unified_vars_static;
177 unsigned int unified_vars_dynamic;
178 unsigned int iterations;
183 /* ID of this variable */
186 /* Name of this variable */
189 /* Tree that this variable is associated with. */
192 /* Offset of this variable, in bits, from the base variable */
193 unsigned HOST_WIDE_INT offset;
195 /* Size of the variable, in bits. */
196 unsigned HOST_WIDE_INT size;
198 /* Full size of the base variable, in bits. */
199 unsigned HOST_WIDE_INT fullsize;
201 /* A link to the variable for the next field in this structure. */
202 struct variable_info *next;
204 /* Node in the graph that represents the constraints and points-to
205 solution for the variable. */
208 /* True if the address of this variable is taken. Needed for
209 variable substitution. */
210 unsigned int address_taken:1;
212 /* True if this variable is the target of a dereference. Needed for
213 variable substitution. */
214 unsigned int indirect_target:1;
216 /* True if this is a variable created by the constraint analysis, such as
217 heap variables and constraints we had to break up. */
218 unsigned int is_artificial_var:1;
220 /* True for variables whose size is not known or variable. */
221 unsigned int is_unknown_size_var:1;
223 /* True for variables that have unions somewhere in them. */
224 unsigned int has_union:1;
226 /* True if this is a heap variable. */
227 unsigned int is_heap_var:1;
229 /* Points-to set for this variable. */
232 /* Variable ids represented by this node. */
235 /* Vector of complex constraints for this node. Complex
236 constraints are those involving dereferences. */
237 VEC(constraint_t,heap) *complex;
239 typedef struct variable_info *varinfo_t;
241 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
243 /* Pool of variable info structures. */
244 static alloc_pool variable_info_pool;
246 DEF_VEC_P(varinfo_t);
248 DEF_VEC_ALLOC_P(varinfo_t, heap);
250 /* Table of variable info structures for constraint variables. Indexed directly
251 by variable info id. */
252 static VEC(varinfo_t,heap) *varmap;
253 #define get_varinfo(n) VEC_index(varinfo_t, varmap, n)
255 /* Variable that represents the unknown pointer. */
256 static varinfo_t var_anything;
257 static tree anything_tree;
258 static unsigned int anything_id;
260 /* Variable that represents the NULL pointer. */
261 static varinfo_t var_nothing;
262 static tree nothing_tree;
263 static unsigned int nothing_id;
265 /* Variable that represents read only memory. */
266 static varinfo_t var_readonly;
267 static tree readonly_tree;
268 static unsigned int readonly_id;
270 /* Variable that represents integers. This is used for when people do things
272 static varinfo_t var_integer;
273 static tree integer_tree;
274 static unsigned int integer_id;
276 /* Variable that represents arbitrary offsets into an object. Used to
277 represent pointer arithmetic, which may not legally escape the
278 bounds of an object. */
279 static varinfo_t var_anyoffset;
280 static tree anyoffset_tree;
281 static unsigned int anyoffset_id;
283 /* Return a new variable info structure consisting for a variable
284 named NAME, and using constraint graph node NODE. */
287 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
289 varinfo_t ret = pool_alloc (variable_info_pool);
295 ret->address_taken = false;
296 ret->indirect_target = false;
297 ret->is_artificial_var = false;
298 ret->is_heap_var = false;
299 ret->is_unknown_size_var = false;
300 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
301 bitmap_clear (ret->solution);
302 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
303 bitmap_clear (ret->variables);
309 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
311 /* An expression that appears in a constraint. */
313 struct constraint_expr
315 /* Constraint type. */
316 constraint_expr_type type;
318 /* Variable we are referring to in the constraint. */
321 /* Offset, in bits, of this constraint from the beginning of
322 variables it ends up referring to.
324 IOW, in a deref constraint, we would deref, get the result set,
325 then add OFFSET to each member. */
326 unsigned HOST_WIDE_INT offset;
329 static struct constraint_expr do_deref (struct constraint_expr);
331 /* Our set constraints are made up of two constraint expressions, one
334 As described in the introduction, our set constraints each represent an
335 operation between set valued variables.
339 struct constraint_expr lhs;
340 struct constraint_expr rhs;
343 /* List of constraints that we use to build the constraint graph from. */
345 static VEC(constraint_t,heap) *constraints;
346 static alloc_pool constraint_pool;
348 /* An edge in the constraint graph. We technically have no use for
349 the src, since it will always be the same node that we are indexing
350 into the pred/succ arrays with, but it's nice for checking
351 purposes. The edges are weighted, with a bit set in weights for
352 each edge from src to dest with that weight. */
354 struct constraint_edge
361 typedef struct constraint_edge *constraint_edge_t;
362 static alloc_pool constraint_edge_pool;
364 /* Return a new constraint edge from SRC to DEST. */
366 static constraint_edge_t
367 new_constraint_edge (unsigned int src, unsigned int dest)
369 constraint_edge_t ret = pool_alloc (constraint_edge_pool);
376 DEF_VEC_P(constraint_edge_t);
377 DEF_VEC_ALLOC_P(constraint_edge_t,heap);
380 /* The constraint graph is simply a set of adjacency vectors, one per
381 variable. succs[x] is the vector of successors for variable x, and preds[x]
382 is the vector of predecessors for variable x.
383 IOW, all edges are "forward" edges, which is not like our CFG.
385 preds[x]->src == x, and
386 succs[x]->src == x. */
388 struct constraint_graph
390 VEC(constraint_edge_t,heap) **succs;
391 VEC(constraint_edge_t,heap) **preds;
394 typedef struct constraint_graph *constraint_graph_t;
396 static constraint_graph_t graph;
398 /* Create a new constraint consisting of LHS and RHS expressions. */
401 new_constraint (const struct constraint_expr lhs,
402 const struct constraint_expr rhs)
404 constraint_t ret = pool_alloc (constraint_pool);
410 /* Print out constraint C to FILE. */
413 dump_constraint (FILE *file, constraint_t c)
415 if (c->lhs.type == ADDRESSOF)
417 else if (c->lhs.type == DEREF)
419 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
420 if (c->lhs.offset != 0)
421 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
422 fprintf (file, " = ");
423 if (c->rhs.type == ADDRESSOF)
425 else if (c->rhs.type == DEREF)
427 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
428 if (c->rhs.offset != 0)
429 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
430 fprintf (file, "\n");
433 /* Print out constraint C to stderr. */
436 debug_constraint (constraint_t c)
438 dump_constraint (stderr, c);
441 /* Print out all constraints to FILE */
444 dump_constraints (FILE *file)
448 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
449 dump_constraint (file, c);
452 /* Print out all constraints to stderr. */
455 debug_constraints (void)
457 dump_constraints (stderr);
462 The solver is a simple worklist solver, that works on the following
465 sbitmap changed_nodes = all ones;
466 changed_count = number of nodes;
467 For each node that was already collapsed:
471 while (changed_count > 0)
473 compute topological ordering for constraint graph
475 find and collapse cycles in the constraint graph (updating
476 changed if necessary)
478 for each node (n) in the graph in topological order:
481 Process each complex constraint associated with the node,
482 updating changed if necessary.
484 For each outgoing edge from n, propagate the solution from n to
485 the destination of the edge, updating changed as necessary.
489 /* Return true if two constraint expressions A and B are equal. */
492 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
494 return a.type == b.type
496 && a.offset == b.offset;
499 /* Return true if constraint expression A is less than constraint expression
500 B. This is just arbitrary, but consistent, in order to give them an
504 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
506 if (a.type == b.type)
509 return a.offset < b.offset;
511 return a.var < b.var;
514 return a.type < b.type;
517 /* Return true if constraint A is less than constraint B. This is just
518 arbitrary, but consistent, in order to give them an ordering. */
521 constraint_less (const constraint_t a, const constraint_t b)
523 if (constraint_expr_less (a->lhs, b->lhs))
525 else if (constraint_expr_less (b->lhs, a->lhs))
528 return constraint_expr_less (a->rhs, b->rhs);
531 /* Return true if two constraints A and B are equal. */
534 constraint_equal (struct constraint a, struct constraint b)
536 return constraint_expr_equal (a.lhs, b.lhs)
537 && constraint_expr_equal (a.rhs, b.rhs);
541 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
544 constraint_vec_find (VEC(constraint_t,heap) *vec,
545 struct constraint lookfor)
553 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
554 if (place >= VEC_length (constraint_t, vec))
556 found = VEC_index (constraint_t, vec, place);
557 if (!constraint_equal (*found, lookfor))
562 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
565 constraint_set_union (VEC(constraint_t,heap) **to,
566 VEC(constraint_t,heap) **from)
571 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
573 if (constraint_vec_find (*to, *c) == NULL)
575 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
577 VEC_safe_insert (constraint_t, heap, *to, place, c);
582 /* Take a solution set SET, add OFFSET to each member of the set, and
583 overwrite SET with the result when done. */
586 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
588 bitmap result = BITMAP_ALLOC (&iteration_obstack);
592 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
594 /* If this is a properly sized variable, only add offset if it's
595 less than end. Otherwise, it is globbed to a single
598 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
600 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
601 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
602 bitmap_set_bit (result, v->id);
604 else if (get_varinfo (i)->is_artificial_var
605 || get_varinfo (i)->is_unknown_size_var)
607 bitmap_set_bit (result, i);
611 bitmap_copy (set, result);
612 BITMAP_FREE (result);
615 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
619 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
622 return bitmap_ior_into (to, from);
628 tmp = BITMAP_ALLOC (&iteration_obstack);
629 bitmap_copy (tmp, from);
630 solution_set_add (tmp, inc);
631 res = bitmap_ior_into (to, tmp);
637 /* Insert constraint C into the list of complex constraints for VAR. */
640 insert_into_complex (unsigned int var, constraint_t c)
642 varinfo_t vi = get_varinfo (var);
643 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
645 VEC_safe_insert (constraint_t, heap, vi->complex, place, c);
649 /* Compare two constraint edges A and B, return true if they are equal. */
652 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
654 return a.src == b.src && a.dest == b.dest;
657 /* Compare two constraint edges, return true if A is less than B */
660 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
662 if (a->dest < b->dest)
664 else if (a->dest == b->dest)
665 return a->src < b->src;
670 /* Find the constraint edge that matches LOOKFOR, in VEC.
671 Return the edge, if found, NULL otherwise. */
673 static constraint_edge_t
674 constraint_edge_vec_find (VEC(constraint_edge_t,heap) *vec,
675 struct constraint_edge lookfor)
678 constraint_edge_t edge;
680 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
681 constraint_edge_less);
682 edge = VEC_index (constraint_edge_t, vec, place);
683 if (!constraint_edge_equal (*edge, lookfor))
688 /* Condense two variable nodes into a single variable node, by moving
689 all associated info from SRC to TO. */
692 condense_varmap_nodes (unsigned int to, unsigned int src)
694 varinfo_t tovi = get_varinfo (to);
695 varinfo_t srcvi = get_varinfo (src);
700 /* the src node, and all its variables, are now the to node. */
702 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
703 get_varinfo (i)->node = to;
705 /* Merge the src node variables and the to node variables. */
706 bitmap_set_bit (tovi->variables, src);
707 bitmap_ior_into (tovi->variables, srcvi->variables);
708 bitmap_clear (srcvi->variables);
710 /* Move all complex constraints from src node into to node */
711 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
713 /* In complex constraints for node src, we may have either
714 a = *src, and *src = a. */
716 if (c->rhs.type == DEREF)
721 constraint_set_union (&tovi->complex, &srcvi->complex);
722 VEC_free (constraint_t, heap, srcvi->complex);
723 srcvi->complex = NULL;
726 /* Erase EDGE from GRAPH. This routine only handles self-edges
727 (e.g. an edge from a to a). */
730 erase_graph_self_edge (constraint_graph_t graph, struct constraint_edge edge)
732 VEC(constraint_edge_t,heap) *predvec = graph->preds[edge.src];
733 VEC(constraint_edge_t,heap) *succvec = graph->succs[edge.dest];
735 gcc_assert (edge.src == edge.dest);
737 /* Remove from the successors. */
738 place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
739 constraint_edge_less);
741 /* Make sure we found the edge. */
742 #ifdef ENABLE_CHECKING
744 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
745 gcc_assert (constraint_edge_equal (*tmp, edge));
748 VEC_ordered_remove (constraint_edge_t, succvec, place);
750 /* Remove from the predecessors. */
751 place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
752 constraint_edge_less);
754 /* Make sure we found the edge. */
755 #ifdef ENABLE_CHECKING
757 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
758 gcc_assert (constraint_edge_equal (*tmp, edge));
761 VEC_ordered_remove (constraint_edge_t, predvec, place);
764 /* Remove edges involving NODE from GRAPH. */
767 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
769 VEC(constraint_edge_t,heap) *succvec = graph->succs[node];
770 VEC(constraint_edge_t,heap) *predvec = graph->preds[node];
774 /* Walk the successors, erase the associated preds. */
775 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
779 struct constraint_edge lookfor;
780 lookfor.src = c->dest;
782 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
783 &lookfor, constraint_edge_less);
784 VEC_ordered_remove (constraint_edge_t, graph->preds[c->dest], place);
786 /* Walk the preds, erase the associated succs. */
787 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
791 struct constraint_edge lookfor;
792 lookfor.src = c->dest;
794 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
795 &lookfor, constraint_edge_less);
796 VEC_ordered_remove (constraint_edge_t, graph->succs[c->dest], place);
799 VEC_free (constraint_edge_t, heap, graph->preds[node]);
800 VEC_free (constraint_edge_t, heap, graph->succs[node]);
801 graph->preds[node] = NULL;
802 graph->succs[node] = NULL;
805 static bool edge_added = false;
807 /* Add edge NEWE to the graph. */
810 add_graph_edge (constraint_graph_t graph, struct constraint_edge newe)
813 unsigned int src = newe.src;
814 unsigned int dest = newe.dest;
815 VEC(constraint_edge_t,heap) *vec;
817 vec = graph->preds[src];
818 place = VEC_lower_bound (constraint_edge_t, vec, &newe,
819 constraint_edge_less);
820 if (place == VEC_length (constraint_edge_t, vec)
821 || VEC_index (constraint_edge_t, vec, place)->dest != dest)
823 constraint_edge_t edge = new_constraint_edge (src, dest);
826 weightbitmap = BITMAP_ALLOC (&ptabitmap_obstack);
827 edge->weights = weightbitmap;
828 VEC_safe_insert (constraint_edge_t, heap, graph->preds[edge->src],
830 edge = new_constraint_edge (dest, src);
831 edge->weights = weightbitmap;
832 place = VEC_lower_bound (constraint_edge_t, graph->succs[edge->src],
833 edge, constraint_edge_less);
834 VEC_safe_insert (constraint_edge_t, heap, graph->succs[edge->src],
844 /* Return the bitmap representing the weights of edge LOOKFOR */
847 get_graph_weights (constraint_graph_t graph, struct constraint_edge lookfor)
849 constraint_edge_t edge;
850 unsigned int src = lookfor.src;
851 VEC(constraint_edge_t,heap) *vec;
852 vec = graph->preds[src];
853 edge = constraint_edge_vec_find (vec, lookfor);
854 gcc_assert (edge != NULL);
855 return edge->weights;
859 /* Merge GRAPH nodes FROM and TO into node TO. */
862 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
865 VEC(constraint_edge_t,heap) *succvec = graph->succs[from];
866 VEC(constraint_edge_t,heap) *predvec = graph->preds[from];
870 /* Merge all the predecessor edges. */
872 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
874 unsigned int d = c->dest;
875 struct constraint_edge olde;
876 struct constraint_edge newe;
883 add_graph_edge (graph, newe);
886 temp = get_graph_weights (graph, olde);
887 weights = get_graph_weights (graph, newe);
888 bitmap_ior_into (weights, temp);
891 /* Merge all the successor edges. */
892 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
894 unsigned int d = c->dest;
895 struct constraint_edge olde;
896 struct constraint_edge newe;
903 add_graph_edge (graph, newe);
906 temp = get_graph_weights (graph, olde);
907 weights = get_graph_weights (graph, newe);
908 bitmap_ior_into (weights, temp);
910 clear_edges_for_node (graph, from);
913 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
914 it doesn't exist in the graph already.
915 Return false if the edge already existed, true otherwise. */
918 int_add_graph_edge (constraint_graph_t graph, unsigned int to,
919 unsigned int from, unsigned HOST_WIDE_INT weight)
921 if (to == from && weight == 0)
928 struct constraint_edge edge;
931 r = add_graph_edge (graph, edge);
932 r |= !bitmap_bit_p (get_graph_weights (graph, edge), weight);
933 bitmap_set_bit (get_graph_weights (graph, edge), weight);
939 /* Return true if LOOKFOR is an existing graph edge. */
942 valid_graph_edge (constraint_graph_t graph, struct constraint_edge lookfor)
944 return constraint_edge_vec_find (graph->preds[lookfor.src], lookfor) != NULL;
948 /* Build the constraint graph. */
951 build_constraint_graph (void)
956 graph = xmalloc (sizeof (struct constraint_graph));
957 graph->succs = xcalloc (VEC_length (varinfo_t, varmap),
958 sizeof (*graph->succs));
959 graph->preds = xcalloc (VEC_length (varinfo_t, varmap),
960 sizeof (*graph->preds));
962 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
964 struct constraint_expr lhs = c->lhs;
965 struct constraint_expr rhs = c->rhs;
966 if (lhs.type == DEREF)
968 /* *x = y or *x = &y (complex) */
969 if (rhs.type == ADDRESSOF || rhs.var > anything_id)
970 insert_into_complex (lhs.var, c);
972 else if (rhs.type == DEREF)
975 if (lhs.var > anything_id)
976 insert_into_complex (rhs.var, c);
978 else if (rhs.type == ADDRESSOF)
981 bitmap_set_bit (get_varinfo (lhs.var)->solution, rhs.var);
983 else if (rhs.var > anything_id && lhs.var > anything_id)
985 /* Ignore 0 weighted self edges, as they can't possibly contribute
987 if (lhs.var != rhs.var || rhs.offset != 0 || lhs.offset != 0)
990 struct constraint_edge edge;
994 add_graph_edge (graph, edge);
995 bitmap_set_bit (get_graph_weights (graph, edge),
1004 /* Changed variables on the last iteration. */
1005 static unsigned int changed_count;
1006 static sbitmap changed;
1008 DEF_VEC_I(unsigned);
1009 DEF_VEC_ALLOC_I(unsigned,heap);
1012 /* Strongly Connected Component visitation info. */
1017 sbitmap in_component;
1019 unsigned int *visited_index;
1020 VEC(unsigned,heap) *scc_stack;
1021 VEC(unsigned,heap) *unification_queue;
1025 /* Recursive routine to find strongly connected components in GRAPH.
1026 SI is the SCC info to store the information in, and N is the id of current
1027 graph node we are processing.
1029 This is Tarjan's strongly connected component finding algorithm, as
1030 modified by Nuutila to keep only non-root nodes on the stack.
1031 The algorithm can be found in "On finding the strongly connected
1032 connected components in a directed graph" by Esko Nuutila and Eljas
1033 Soisalon-Soininen, in Information Processing Letters volume 49,
1034 number 1, pages 9-14. */
1037 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1039 constraint_edge_t c;
1042 gcc_assert (get_varinfo (n)->node == n);
1043 SET_BIT (si->visited, n);
1044 RESET_BIT (si->in_component, n);
1045 si->visited_index[n] = si->current_index ++;
1047 /* Visit all the successors. */
1048 for (i = 0; VEC_iterate (constraint_edge_t, graph->succs[n], i, c); i++)
1050 /* We only want to find and collapse the zero weight edges. */
1051 if (bitmap_bit_p (c->weights, 0))
1053 unsigned int w = c->dest;
1054 if (!TEST_BIT (si->visited, w))
1055 scc_visit (graph, si, w);
1056 if (!TEST_BIT (si->in_component, w))
1058 unsigned int t = get_varinfo (w)->node;
1059 unsigned int nnode = get_varinfo (n)->node;
1060 if (si->visited_index[t] < si->visited_index[nnode])
1061 get_varinfo (n)->node = t;
1066 /* See if any components have been identified. */
1067 if (get_varinfo (n)->node == n)
1069 unsigned int t = si->visited_index[n];
1070 SET_BIT (si->in_component, n);
1071 while (VEC_length (unsigned, si->scc_stack) != 0
1072 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1074 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1075 get_varinfo (w)->node = n;
1076 SET_BIT (si->in_component, w);
1077 /* Mark this node for collapsing. */
1078 VEC_safe_push (unsigned, heap, si->unification_queue, w);
1082 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1086 /* Collapse two variables into one variable. */
1089 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1091 bitmap tosol, fromsol;
1092 struct constraint_edge edge;
1095 condense_varmap_nodes (to, from);
1096 tosol = get_varinfo (to)->solution;
1097 fromsol = get_varinfo (from)->solution;
1098 bitmap_ior_into (tosol, fromsol);
1099 merge_graph_nodes (graph, to, from);
1102 if (valid_graph_edge (graph, edge))
1104 bitmap weights = get_graph_weights (graph, edge);
1105 bitmap_clear_bit (weights, 0);
1106 if (bitmap_empty_p (weights))
1107 erase_graph_self_edge (graph, edge);
1109 bitmap_clear (fromsol);
1110 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1111 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1115 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1116 SI is the Strongly Connected Components information structure that tells us
1117 what components to unify.
1118 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1119 count should be updated to reflect the unification. */
1122 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1123 bool update_changed)
1126 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1129 /* We proceed as follows:
1131 For each component in the queue (components are delineated by
1132 when current_queue_element->node != next_queue_element->node):
1134 rep = representative node for component
1136 For each node (tounify) to be unified in the component,
1137 merge the solution for tounify into tmp bitmap
1139 clear solution for tounify
1141 merge edges from tounify into rep
1143 merge complex constraints from tounify into rep
1145 update changed count to note that tounify will never change
1148 Merge tmp into solution for rep, marking rep changed if this
1149 changed rep's solution.
1151 Delete any 0 weighted self-edges we now have for rep. */
1152 while (i != VEC_length (unsigned, si->unification_queue))
1154 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1155 unsigned int n = get_varinfo (tounify)->node;
1157 if (dump_file && (dump_flags & TDF_DETAILS))
1158 fprintf (dump_file, "Unifying %s to %s\n",
1159 get_varinfo (tounify)->name,
1160 get_varinfo (n)->name);
1162 stats.unified_vars_dynamic++;
1164 stats.unified_vars_static++;
1165 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1166 merge_graph_nodes (graph, n, tounify);
1167 condense_varmap_nodes (n, tounify);
1169 if (update_changed && TEST_BIT (changed, tounify))
1171 RESET_BIT (changed, tounify);
1172 if (!TEST_BIT (changed, n))
1173 SET_BIT (changed, n);
1176 gcc_assert (changed_count > 0);
1181 bitmap_clear (get_varinfo (tounify)->solution);
1184 /* If we've either finished processing the entire queue, or
1185 finished processing all nodes for component n, update the solution for
1187 if (i == VEC_length (unsigned, si->unification_queue)
1188 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1190 struct constraint_edge edge;
1192 /* If the solution changes because of the merging, we need to mark
1193 the variable as changed. */
1194 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1196 if (update_changed && !TEST_BIT (changed, n))
1198 SET_BIT (changed, n);
1205 if (valid_graph_edge (graph, edge))
1207 bitmap weights = get_graph_weights (graph, edge);
1208 bitmap_clear_bit (weights, 0);
1209 if (bitmap_empty_p (weights))
1210 erase_graph_self_edge (graph, edge);
1218 /* Information needed to compute the topological ordering of a graph. */
1222 /* sbitmap of visited nodes. */
1224 /* Array that stores the topological order of the graph, *in
1226 VEC(unsigned,heap) *topo_order;
1230 /* Initialize and return a topological info structure. */
1232 static struct topo_info *
1233 init_topo_info (void)
1235 size_t size = VEC_length (varinfo_t, varmap);
1236 struct topo_info *ti = xmalloc (sizeof (struct topo_info));
1237 ti->visited = sbitmap_alloc (size);
1238 sbitmap_zero (ti->visited);
1239 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1244 /* Free the topological sort info pointed to by TI. */
1247 free_topo_info (struct topo_info *ti)
1249 sbitmap_free (ti->visited);
1250 VEC_free (unsigned, heap, ti->topo_order);
1254 /* Visit the graph in topological order, and store the order in the
1255 topo_info structure. */
1258 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1261 VEC(constraint_edge_t,heap) *succs = graph->succs[n];
1262 constraint_edge_t c;
1264 SET_BIT (ti->visited, n);
1265 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1267 if (!TEST_BIT (ti->visited, c->dest))
1268 topo_visit (graph, ti, c->dest);
1270 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1273 /* Return true if variable N + OFFSET is a legal field of N. */
1276 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1278 varinfo_t ninfo = get_varinfo (n);
1280 /* For things we've globbed to single variables, any offset into the
1281 variable acts like the entire variable, so that it becomes offset
1283 if (n == anything_id
1284 || ninfo->is_artificial_var
1285 || ninfo->is_unknown_size_var)
1290 return n > anything_id
1291 && (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1294 /* Process a constraint C that represents *x = &y. */
1297 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1298 constraint_t c, bitmap delta)
1300 unsigned int rhs = c->rhs.var;
1301 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1305 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1306 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1308 if (type_safe (j, &offset))
1310 /* *x != NULL && *x != ANYTHING*/
1314 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1315 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1317 sol = get_varinfo (t)->solution;
1318 if (!bitmap_bit_p (sol, rhs))
1320 bitmap_set_bit (sol, rhs);
1321 if (!TEST_BIT (changed, t))
1323 SET_BIT (changed, t);
1329 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1334 /* Process a constraint C that represents x = *y, using DELTA as the
1335 starting solution. */
1338 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1341 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1342 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1344 bitmap sol = get_varinfo (lhs)->solution;
1348 /* For each variable j in delta (Sol(y)), add
1349 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1350 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1352 if (type_safe (j, &roffset))
1355 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1358 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1360 if (int_add_graph_edge (graph, lhs, t, 0))
1361 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1364 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1368 /* If the LHS solution changed, mark the var as changed. */
1371 get_varinfo (lhs)->solution = sol;
1372 if (!TEST_BIT (changed, lhs))
1374 SET_BIT (changed, lhs);
1380 /* Process a constraint C that represents *x = y. */
1383 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1385 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1386 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1387 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1388 bitmap sol = get_varinfo (rhs)->solution;
1392 /* For each member j of delta (Sol(x)), add an edge from y to j and
1393 union Sol(y) into Sol(j) */
1394 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1396 if (type_safe (j, &loff))
1400 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1402 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1404 if (int_add_graph_edge (graph, t, rhs, roff))
1406 bitmap tmp = get_varinfo (t)->solution;
1407 if (set_union_with_increment (tmp, sol, roff))
1409 get_varinfo (t)->solution = tmp;
1412 sol = get_varinfo (rhs)->solution;
1414 if (!TEST_BIT (changed, t))
1416 SET_BIT (changed, t);
1423 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1427 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1428 constraint (IE *x = &y, x = *y, and *x = y). */
1431 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1433 if (c->lhs.type == DEREF)
1435 if (c->rhs.type == ADDRESSOF)
1438 do_da_constraint (graph, c, delta);
1443 do_ds_constraint (graph, c, delta);
1449 do_sd_constraint (graph, c, delta);
1453 /* Initialize and return a new SCC info structure. */
1455 static struct scc_info *
1456 init_scc_info (void)
1458 struct scc_info *si = xmalloc (sizeof (struct scc_info));
1459 size_t size = VEC_length (varinfo_t, varmap);
1461 si->current_index = 0;
1462 si->visited = sbitmap_alloc (size);
1463 sbitmap_zero (si->visited);
1464 si->in_component = sbitmap_alloc (size);
1465 sbitmap_ones (si->in_component);
1466 si->visited_index = xcalloc (sizeof (unsigned int), size + 1);
1467 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1468 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1472 /* Free an SCC info structure pointed to by SI */
1475 free_scc_info (struct scc_info *si)
1477 sbitmap_free (si->visited);
1478 sbitmap_free (si->in_component);
1479 free (si->visited_index);
1480 VEC_free (unsigned, heap, si->scc_stack);
1481 VEC_free (unsigned, heap, si->unification_queue);
1486 /* Find cycles in GRAPH that occur, using strongly connected components, and
1487 collapse the cycles into a single representative node. if UPDATE_CHANGED
1488 is true, then update the changed sbitmap to note those nodes whose
1489 solutions have changed as a result of collapsing. */
1492 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1495 unsigned int size = VEC_length (varinfo_t, varmap);
1496 struct scc_info *si = init_scc_info ();
1498 for (i = 0; i != size; ++i)
1499 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1500 scc_visit (graph, si, i);
1501 process_unification_queue (graph, si, update_changed);
1505 /* Compute a topological ordering for GRAPH, and store the result in the
1506 topo_info structure TI. */
1509 compute_topo_order (constraint_graph_t graph,
1510 struct topo_info *ti)
1513 unsigned int size = VEC_length (varinfo_t, varmap);
1515 for (i = 0; i != size; ++i)
1516 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1517 topo_visit (graph, ti, i);
1520 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1523 bitmap_other_than_zero_bit_set (bitmap b)
1528 if (bitmap_empty_p (b))
1530 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1535 /* Perform offline variable substitution.
1537 This is a linear time way of identifying variables that must have
1538 equivalent points-to sets, including those caused by static cycles,
1539 and single entry subgraphs, in the constraint graph.
1541 The technique is described in "Off-line variable substitution for
1542 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1543 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1546 perform_var_substitution (constraint_graph_t graph)
1548 struct topo_info *ti = init_topo_info ();
1550 /* Compute the topological ordering of the graph, then visit each
1551 node in topological order. */
1552 compute_topo_order (graph, ti);
1554 while (VEC_length (unsigned, ti->topo_order) != 0)
1556 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1558 varinfo_t vi = get_varinfo (i);
1559 bool okay_to_elim = false;
1560 unsigned int root = VEC_length (varinfo_t, varmap);
1561 VEC(constraint_edge_t,heap) *predvec = graph->preds[i];
1562 constraint_edge_t ce;
1565 /* We can't eliminate things whose address is taken, or which is
1566 the target of a dereference. */
1567 if (vi->address_taken || vi->indirect_target)
1570 /* See if all predecessors of I are ripe for elimination */
1571 for (pred = 0; VEC_iterate (constraint_edge_t, predvec, pred, ce); pred++)
1575 weight = get_graph_weights (graph, *ce);
1577 /* We can't eliminate variables that have non-zero weighted
1578 edges between them. */
1579 if (bitmap_other_than_zero_bit_set (weight))
1581 okay_to_elim = false;
1584 w = get_varinfo (ce->dest)->node;
1586 /* We can't eliminate the node if one of the predecessors is
1587 part of a different strongly connected component. */
1591 okay_to_elim = true;
1595 okay_to_elim = false;
1599 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1600 then Solution(i) is a subset of Solution (w), where w is a
1601 predecessor in the graph.
1602 Corollary: If all predecessors of i have the same
1603 points-to set, then i has that same points-to set as
1604 those predecessors. */
1605 tmp = BITMAP_ALLOC (NULL);
1606 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1607 get_varinfo (w)->solution);
1608 if (!bitmap_empty_p (tmp))
1610 okay_to_elim = false;
1617 /* See if the root is different than the original node.
1618 If so, we've found an equivalence. */
1619 if (root != get_varinfo (i)->node && okay_to_elim)
1621 /* Found an equivalence */
1622 get_varinfo (i)->node = root;
1623 collapse_nodes (graph, root, i);
1624 if (dump_file && (dump_flags & TDF_DETAILS))
1625 fprintf (dump_file, "Collapsing %s into %s\n",
1626 get_varinfo (i)->name,
1627 get_varinfo (root)->name);
1628 stats.collapsed_vars++;
1632 free_topo_info (ti);
1636 /* Solve the constraint graph GRAPH using our worklist solver.
1637 This is based on the PW* family of solvers from the "Efficient Field
1638 Sensitive Pointer Analysis for C" paper.
1639 It works by iterating over all the graph nodes, processing the complex
1640 constraints and propagating the copy constraints, until everything stops
1641 changed. This corresponds to steps 6-8 in the solving list given above. */
1644 solve_graph (constraint_graph_t graph)
1646 unsigned int size = VEC_length (varinfo_t, varmap);
1649 changed_count = size;
1650 changed = sbitmap_alloc (size);
1651 sbitmap_ones (changed);
1653 /* The already collapsed/unreachable nodes will never change, so we
1654 need to account for them in changed_count. */
1655 for (i = 0; i < size; i++)
1656 if (get_varinfo (i)->node != i)
1659 while (changed_count > 0)
1662 struct topo_info *ti = init_topo_info ();
1665 bitmap_obstack_initialize (&iteration_obstack);
1669 /* We already did cycle elimination once, when we did
1670 variable substitution, so we don't need it again for the
1672 if (stats.iterations > 1)
1673 find_and_collapse_graph_cycles (graph, true);
1678 compute_topo_order (graph, ti);
1680 while (VEC_length (unsigned, ti->topo_order) != 0)
1682 i = VEC_pop (unsigned, ti->topo_order);
1683 gcc_assert (get_varinfo (i)->node == i);
1685 /* If the node has changed, we need to process the
1686 complex constraints and outgoing edges again. */
1687 if (TEST_BIT (changed, i))
1691 constraint_edge_t e;
1693 VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
1694 VEC(constraint_edge_t,heap) *succs;
1696 RESET_BIT (changed, i);
1699 /* Process the complex constraints */
1700 solution = get_varinfo (i)->solution;
1701 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
1702 do_complex_constraint (graph, c, solution);
1704 /* Propagate solution to all successors. */
1705 succs = graph->succs[i];
1706 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
1708 bitmap tmp = get_varinfo (e->dest)->solution;
1711 bitmap weights = e->weights;
1714 gcc_assert (!bitmap_empty_p (weights));
1715 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
1716 flag |= set_union_with_increment (tmp, solution, k);
1720 get_varinfo (e->dest)->solution = tmp;
1721 if (!TEST_BIT (changed, e->dest))
1723 SET_BIT (changed, e->dest);
1730 free_topo_info (ti);
1731 bitmap_obstack_release (&iteration_obstack);
1734 sbitmap_free (changed);
1738 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1740 /* Map from trees to variable ids. */
1741 static htab_t id_for_tree;
1743 typedef struct tree_id
1749 /* Hash a tree id structure. */
1752 tree_id_hash (const void *p)
1754 const tree_id_t ta = (tree_id_t) p;
1755 return htab_hash_pointer (ta->t);
1758 /* Return true if the tree in P1 and the tree in P2 are the same. */
1761 tree_id_eq (const void *p1, const void *p2)
1763 const tree_id_t ta1 = (tree_id_t) p1;
1764 const tree_id_t ta2 = (tree_id_t) p2;
1765 return ta1->t == ta2->t;
1768 /* Insert ID as the variable id for tree T in the hashtable. */
1771 insert_id_for_tree (tree t, int id)
1774 struct tree_id finder;
1778 slot = htab_find_slot (id_for_tree, &finder, INSERT);
1779 gcc_assert (*slot == NULL);
1780 new_pair = xmalloc (sizeof (struct tree_id));
1783 *slot = (void *)new_pair;
1786 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1787 exist in the hash table, return false, otherwise, return true and
1788 set *ID to the id we found. */
1791 lookup_id_for_tree (tree t, unsigned int *id)
1794 struct tree_id finder;
1797 pair = htab_find (id_for_tree, &finder);
1804 /* Return a printable name for DECL */
1807 alias_get_name (tree decl)
1809 const char *res = get_name (decl);
1811 int num_printed = 0;
1817 if (TREE_CODE (decl) == SSA_NAME)
1819 num_printed = asprintf (&temp, "%s_%u",
1820 alias_get_name (SSA_NAME_VAR (decl)),
1821 SSA_NAME_VERSION (decl));
1823 else if (DECL_P (decl))
1825 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
1827 if (num_printed > 0)
1829 res = ggc_strdup (temp);
1835 /* Find the variable id for tree T in the hashtable.
1836 If T doesn't exist in the hash table, create an entry for it. */
1839 get_id_for_tree (tree t)
1842 struct tree_id finder;
1845 pair = htab_find (id_for_tree, &finder);
1847 return create_variable_info_for (t, alias_get_name (t));
1852 /* Get a constraint expression from an SSA_VAR_P node. */
1854 static struct constraint_expr
1855 get_constraint_exp_from_ssa_var (tree t)
1857 struct constraint_expr cexpr;
1859 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
1861 /* For parameters, get at the points-to set for the actual parm
1863 if (TREE_CODE (t) == SSA_NAME
1864 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
1865 && default_def (SSA_NAME_VAR (t)) == t)
1866 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
1868 cexpr.type = SCALAR;
1870 cexpr.var = get_id_for_tree (t);
1871 /* If we determine the result is "anything", and we know this is readonly,
1872 say it points to readonly memory instead. */
1873 if (cexpr.var == anything_id && TREE_READONLY (t))
1875 cexpr.type = ADDRESSOF;
1876 cexpr.var = readonly_id;
1883 /* Process a completed constraint T, and add it to the constraint
1887 process_constraint (constraint_t t)
1889 struct constraint_expr rhs = t->rhs;
1890 struct constraint_expr lhs = t->lhs;
1892 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
1893 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
1895 /* ANYTHING == ANYTHING is pointless. */
1896 if (lhs.var == anything_id && rhs.var == anything_id)
1899 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1900 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
1905 process_constraint (t);
1907 /* This can happen in our IR with things like n->a = *p */
1908 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
1910 /* Split into tmp = *rhs, *lhs = tmp */
1911 tree rhsdecl = get_varinfo (rhs.var)->decl;
1912 tree pointertype = TREE_TYPE (rhsdecl);
1913 tree pointedtotype = TREE_TYPE (pointertype);
1914 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
1915 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
1917 /* If this is an aggregate of known size, we should have passed
1918 this off to do_structure_copy, and it should have broken it
1920 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
1921 || get_varinfo (rhs.var)->is_unknown_size_var);
1923 process_constraint (new_constraint (tmplhs, rhs));
1924 process_constraint (new_constraint (lhs, tmplhs));
1926 else if (rhs.type == ADDRESSOF)
1929 gcc_assert (rhs.offset == 0);
1931 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
1932 vi->address_taken = true;
1934 VEC_safe_push (constraint_t, heap, constraints, t);
1938 if (lhs.type != DEREF && rhs.type == DEREF)
1939 get_varinfo (lhs.var)->indirect_target = true;
1940 VEC_safe_push (constraint_t, heap, constraints, t);
1945 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1948 static unsigned HOST_WIDE_INT
1949 bitpos_of_field (const tree fdecl)
1952 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
1953 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
1956 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
1957 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
1961 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1962 overlaps with a field at [FIELDPOS, FIELDSIZE] */
1965 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
1966 const unsigned HOST_WIDE_INT fieldsize,
1967 const unsigned HOST_WIDE_INT accesspos,
1968 const unsigned HOST_WIDE_INT accesssize)
1970 if (fieldpos == accesspos && fieldsize == accesssize)
1972 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
1974 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
1980 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1982 static struct constraint_expr
1983 get_constraint_for_component_ref (tree t)
1985 struct constraint_expr result;
1986 HOST_WIDE_INT bitsize;
1987 HOST_WIDE_INT bitpos;
1989 enum machine_mode mode;
1995 result.type = SCALAR;
1998 /* Some people like to do cute things like take the address of
2001 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2002 forzero = TREE_OPERAND (forzero, 0);
2004 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2007 result.var = integer_id;
2008 result.type = SCALAR;
2012 t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode,
2013 &unsignedp, &volatilep, false);
2014 result = get_constraint_for (t);
2016 /* This can also happen due to weird offsetof type macros. */
2017 if (TREE_CODE (t) != ADDR_EXPR && result.type == ADDRESSOF)
2018 result.type = SCALAR;
2020 /* If we know where this goes, then yay. Otherwise, booo. */
2022 if (offset == NULL && bitsize != -1)
2024 result.offset = bitpos;
2028 result.var = anything_id;
2032 if (result.type == SCALAR)
2034 /* In languages like C, you can access one past the end of an
2035 array. You aren't allowed to dereference it, so we can
2036 ignore this constraint. When we handle pointer subtraction,
2037 we may have to do something cute here. */
2039 if (result.offset < get_varinfo (result.var)->fullsize)
2041 /* It's also not true that the constraint will actually start at the
2042 right offset, it may start in some padding. We only care about
2043 setting the constraint to the first actual field it touches, so
2046 for (curr = get_varinfo (result.var); curr; curr = curr->next)
2048 if (offset_overlaps_with_access (curr->offset, curr->size,
2049 result.offset, bitsize))
2051 result.var = curr->id;
2056 /* assert that we found *some* field there. The user couldn't be
2057 accessing *only* padding. */
2062 if (dump_file && (dump_flags & TDF_DETAILS))
2063 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2072 /* Dereference the constraint expression CONS, and return the result.
2073 DEREF (ADDRESSOF) = SCALAR
2074 DEREF (SCALAR) = DEREF
2075 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2076 This is needed so that we can handle dereferencing DEREF constraints. */
2078 static struct constraint_expr
2079 do_deref (struct constraint_expr cons)
2081 if (cons.type == SCALAR)
2086 else if (cons.type == ADDRESSOF)
2091 else if (cons.type == DEREF)
2093 tree tmpvar = create_tmp_var_raw (ptr_type_node, "derefmp");
2094 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2095 process_constraint (new_constraint (tmplhs, cons));
2096 cons.var = tmplhs.var;
2103 /* Given a tree T, return the constraint expression for it. */
2105 static struct constraint_expr
2106 get_constraint_for (tree t)
2108 struct constraint_expr temp;
2110 /* x = integer is all glommed to a single variable, which doesn't
2111 point to anything by itself. That is, of course, unless it is an
2112 integer constant being treated as a pointer, in which case, we
2113 will return that this is really the addressof anything. This
2114 happens below, since it will fall into the default case. The only
2115 case we know something about an integer treated like a pointer is
2116 when it is the NULL pointer, and then we just say it points to
2118 if (TREE_CODE (t) == INTEGER_CST
2119 && !POINTER_TYPE_P (TREE_TYPE (t)))
2121 temp.var = integer_id;
2126 else if (TREE_CODE (t) == INTEGER_CST
2127 && integer_zerop (t))
2129 temp.var = nothing_id;
2130 temp.type = ADDRESSOF;
2135 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2137 case tcc_expression:
2139 switch (TREE_CODE (t))
2143 temp = get_constraint_for (TREE_OPERAND (t, 0));
2144 if (temp.type == DEREF)
2147 temp.type = ADDRESSOF;
2153 /* XXX: In interprocedural mode, if we didn't have the
2154 body, we would need to do *each pointer argument =
2156 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2161 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2162 DECL_EXTERNAL (heapvar) = 1;
2163 add_referenced_tmp_var (heapvar);
2164 temp.var = create_variable_info_for (heapvar,
2165 alias_get_name (heapvar));
2167 vi = get_varinfo (temp.var);
2168 vi->is_artificial_var = 1;
2169 vi->is_heap_var = 1;
2170 temp.type = ADDRESSOF;
2177 temp.type = ADDRESSOF;
2178 temp.var = anything_id;
2186 switch (TREE_CODE (t))
2190 temp = get_constraint_for (TREE_OPERAND (t, 0));
2191 temp = do_deref (temp);
2196 temp = get_constraint_for_component_ref (t);
2200 temp.type = ADDRESSOF;
2201 temp.var = anything_id;
2209 switch (TREE_CODE (t))
2213 case NON_LVALUE_EXPR:
2215 tree op = TREE_OPERAND (t, 0);
2217 /* Cast from non-pointer to pointers are bad news for us.
2218 Anything else, we see through */
2219 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2220 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2221 return get_constraint_for (op);
2227 temp.type = ADDRESSOF;
2228 temp.var = anything_id;
2234 case tcc_exceptional:
2236 switch (TREE_CODE (t))
2239 return get_constraint_for (PHI_RESULT (t));
2241 return get_constraint_exp_from_ssa_var (t);
2244 temp.type = ADDRESSOF;
2245 temp.var = anything_id;
2251 case tcc_declaration:
2252 return get_constraint_exp_from_ssa_var (t);
2255 temp.type = ADDRESSOF;
2256 temp.var = anything_id;
2264 /* Handle the structure copy case where we have a simple structure copy
2265 between LHS and RHS that is of SIZE (in bits)
2267 For each field of the lhs variable (lhsfield)
2268 For each field of the rhs variable at lhsfield.offset (rhsfield)
2269 add the constraint lhsfield = rhsfield
2273 do_simple_structure_copy (const struct constraint_expr lhs,
2274 const struct constraint_expr rhs,
2275 const unsigned HOST_WIDE_INT size)
2277 varinfo_t p = get_varinfo (lhs.var);
2278 unsigned HOST_WIDE_INT pstart, last;
2280 last = p->offset + size;
2281 for (; p && p->offset < last; p = p->next)
2284 struct constraint_expr templhs = lhs;
2285 struct constraint_expr temprhs = rhs;
2286 unsigned HOST_WIDE_INT fieldoffset;
2288 templhs.var = p->id;
2289 q = get_varinfo (temprhs.var);
2290 fieldoffset = p->offset - pstart;
2291 q = first_vi_for_offset (q, q->offset + fieldoffset);
2292 temprhs.var = q->id;
2293 process_constraint (new_constraint (templhs, temprhs));
2298 /* Handle the structure copy case where we have a structure copy between a
2299 aggregate on the LHS and a dereference of a pointer on the RHS
2300 that is of SIZE (in bits)
2302 For each field of the lhs variable (lhsfield)
2303 rhs.offset = lhsfield->offset
2304 add the constraint lhsfield = rhs
2308 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2309 const struct constraint_expr rhs,
2310 const unsigned HOST_WIDE_INT size)
2312 varinfo_t p = get_varinfo (lhs.var);
2313 unsigned HOST_WIDE_INT pstart,last;
2315 last = p->offset + size;
2317 for (; p && p->offset < last; p = p->next)
2320 struct constraint_expr templhs = lhs;
2321 struct constraint_expr temprhs = rhs;
2322 unsigned HOST_WIDE_INT fieldoffset;
2325 if (templhs.type == SCALAR)
2326 templhs.var = p->id;
2328 templhs.offset = p->offset;
2330 q = get_varinfo (temprhs.var);
2331 fieldoffset = p->offset - pstart;
2332 temprhs.offset += fieldoffset;
2333 process_constraint (new_constraint (templhs, temprhs));
2337 /* Handle the structure copy case where we have a structure copy
2338 between a aggregate on the RHS and a dereference of a pointer on
2339 the LHS that is of SIZE (in bits)
2341 For each field of the rhs variable (rhsfield)
2342 lhs.offset = rhsfield->offset
2343 add the constraint lhs = rhsfield
2347 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2348 const struct constraint_expr rhs,
2349 const unsigned HOST_WIDE_INT size)
2351 varinfo_t p = get_varinfo (rhs.var);
2352 unsigned HOST_WIDE_INT pstart,last;
2354 last = p->offset + size;
2356 for (; p && p->offset < last; p = p->next)
2359 struct constraint_expr templhs = lhs;
2360 struct constraint_expr temprhs = rhs;
2361 unsigned HOST_WIDE_INT fieldoffset;
2364 if (temprhs.type == SCALAR)
2365 temprhs.var = p->id;
2367 temprhs.offset = p->offset;
2369 q = get_varinfo (templhs.var);
2370 fieldoffset = p->offset - pstart;
2371 templhs.offset += fieldoffset;
2372 process_constraint (new_constraint (templhs, temprhs));
2377 /* Handle aggregate copies by expanding into copies of the respective
2378 fields of the structures. */
2381 do_structure_copy (tree lhsop, tree rhsop)
2383 struct constraint_expr lhs, rhs, tmp;
2385 unsigned HOST_WIDE_INT lhssize;
2386 unsigned HOST_WIDE_INT rhssize;
2388 lhs = get_constraint_for (lhsop);
2389 rhs = get_constraint_for (rhsop);
2391 /* If we have special var = x, swap it around. */
2392 if (lhs.var <= integer_id && rhs.var > integer_id)
2399 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2400 possible it's something we could handle. However, most cases falling
2401 into this are dealing with transparent unions, which are slightly
2403 if (rhs.type == ADDRESSOF && rhs.var > integer_id)
2405 rhs.type = ADDRESSOF;
2406 rhs.var = anything_id;
2409 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2410 that special var. */
2411 if (rhs.var <= integer_id)
2413 for (p = get_varinfo (lhs.var); p; p = p->next)
2415 struct constraint_expr templhs = lhs;
2416 struct constraint_expr temprhs = rhs;
2417 if (templhs.type == SCALAR )
2418 templhs.var = p->id;
2420 templhs.offset += p->offset;
2421 process_constraint (new_constraint (templhs, temprhs));
2426 tree rhstype = TREE_TYPE (rhsop);
2427 tree lhstype = TREE_TYPE (lhsop);
2428 tree rhstypesize = TYPE_SIZE (rhstype);
2429 tree lhstypesize = TYPE_SIZE (lhstype);
2431 /* If we have a variably sized types on the rhs or lhs, and a deref
2432 constraint, add the constraint, lhsconstraint = &ANYTHING.
2433 This is conservatively correct because either the lhs is an unknown
2434 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2435 constraint, and every variable it can point to must be unknown sized
2436 anyway, so we don't need to worry about fields at all. */
2437 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2438 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2440 rhs.var = anything_id;
2441 rhs.type = ADDRESSOF;
2443 process_constraint (new_constraint (lhs, rhs));
2447 /* The size only really matters insofar as we don't set more or less of
2448 the variable. If we hit an unknown size var, the size should be the
2449 whole darn thing. */
2450 if (get_varinfo (rhs.var)->is_unknown_size_var)
2453 rhssize = TREE_INT_CST_LOW (rhstypesize);
2455 if (get_varinfo (lhs.var)->is_unknown_size_var)
2458 lhssize = TREE_INT_CST_LOW (lhstypesize);
2461 if (rhs.type == SCALAR && lhs.type == SCALAR)
2462 do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2463 else if (lhs.type != DEREF && rhs.type == DEREF)
2464 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2465 else if (lhs.type == DEREF && rhs.type != DEREF)
2466 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2469 tree pointedtotype = lhstype;
2472 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2473 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2474 do_structure_copy (tmpvar, rhsop);
2475 do_structure_copy (lhsop, tmpvar);
2481 /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere
2485 ref_contains_indirect_ref (tree ref)
2487 while (handled_component_p (ref))
2489 if (TREE_CODE (ref) == INDIRECT_REF)
2491 ref = TREE_OPERAND (ref, 0);
2497 /* Update related alias information kept in AI. This is used when
2498 building name tags, alias sets and deciding grouping heuristics.
2499 STMT is the statement to process. This function also updates
2500 ADDRESSABLE_VARS. */
2503 update_alias_info (tree stmt, struct alias_info *ai)
2506 use_operand_p use_p;
2508 bool stmt_escapes_p = is_escape_site (stmt, ai);
2511 /* Mark all the variables whose address are taken by the statement. */
2512 addr_taken = addresses_taken (stmt);
2515 bitmap_ior_into (addressable_vars, addr_taken);
2517 /* If STMT is an escape point, all the addresses taken by it are
2524 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
2525 mark_call_clobbered (referenced_var (i));
2529 /* Process each operand use. If an operand may be aliased, keep
2530 track of how many times it's being used. For pointers, determine
2531 whether they are dereferenced by the statement, or whether their
2532 value escapes, etc. */
2533 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2537 struct ptr_info_def *pi;
2539 unsigned num_uses, num_derefs;
2541 op = USE_FROM_PTR (use_p);
2543 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2544 to the set of addressable variables. */
2545 if (TREE_CODE (op) == ADDR_EXPR)
2547 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
2549 /* PHI nodes don't have annotations for pinning the set
2550 of addresses taken, so we collect them here.
2552 FIXME, should we allow PHI nodes to have annotations
2553 so that they can be treated like regular statements?
2554 Currently, they are treated as second-class
2556 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
2560 /* Ignore constants. */
2561 if (TREE_CODE (op) != SSA_NAME)
2564 var = SSA_NAME_VAR (op);
2565 v_ann = var_ann (var);
2567 /* If the operand's variable may be aliased, keep track of how
2568 many times we've referenced it. This is used for alias
2569 grouping in compute_flow_insensitive_aliasing. */
2570 if (may_be_aliased (var))
2571 NUM_REFERENCES_INC (v_ann);
2573 /* We are only interested in pointers. */
2574 if (!POINTER_TYPE_P (TREE_TYPE (op)))
2577 pi = get_ptr_info (op);
2579 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
2580 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
2582 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
2583 VARRAY_PUSH_TREE (ai->processed_ptrs, op);
2586 /* If STMT is a PHI node, then it will not have pointer
2587 dereferences and it will not be an escape point. */
2588 if (TREE_CODE (stmt) == PHI_NODE)
2591 /* Determine whether OP is a dereferenced pointer, and if STMT
2592 is an escape point, whether OP escapes. */
2593 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
2597 /* Mark OP as dereferenced. In a subsequent pass,
2598 dereferenced pointers that point to a set of
2599 variables will be assigned a name tag to alias
2600 all the variables OP points to. */
2601 pi->is_dereferenced = 1;
2603 /* Keep track of how many time we've dereferenced each
2605 NUM_REFERENCES_INC (v_ann);
2607 /* If this is a store operation, mark OP as being
2608 dereferenced to store, otherwise mark it as being
2609 dereferenced to load. */
2611 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
2613 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
2616 if (stmt_escapes_p && num_derefs < num_uses)
2618 /* If STMT is an escape point and STMT contains at
2619 least one direct use of OP, then the value of OP
2620 escapes and so the pointed-to variables need to
2621 be marked call-clobbered. */
2622 pi->value_escapes_p = 1;
2624 /* If the statement makes a function call, assume
2625 that pointer OP will be dereferenced in a store
2626 operation inside the called function. */
2627 if (get_call_expr_in (stmt))
2629 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
2630 pi->is_dereferenced = 1;
2635 if (TREE_CODE (stmt) == PHI_NODE)
2638 /* Update reference counter for definitions to any
2639 potentially aliased variable. This is used in the alias
2640 grouping heuristics. */
2641 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
2643 tree var = SSA_NAME_VAR (op);
2644 var_ann_t ann = var_ann (var);
2645 bitmap_set_bit (ai->written_vars, DECL_UID (var));
2646 if (may_be_aliased (var))
2647 NUM_REFERENCES_INC (ann);
2651 /* Mark variables in V_MAY_DEF operands as being written to. */
2652 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
2654 tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
2655 bitmap_set_bit (ai->written_vars, DECL_UID (var));
2660 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
2661 Expressions of the type PTR + CST can be handled in two ways:
2663 1- If the constraint for PTR is ADDRESSOF for a non-structure
2664 variable, then we can use it directly because adding or
2665 subtracting a constant may not alter the original ADDRESSOF
2666 constraing (i.e., pointer arithmetic may not legally go outside
2667 an object's boundaries).
2669 2- If the constraint for PTR is ADDRESSOF for a structure variable,
2670 then if CST is a compile-time constant that can be used as an
2671 offset, we can determine which sub-variable will be pointed-to
2674 Return true if the expression is handled. For any other kind of
2675 expression, return false so that each operand can be added as a
2676 separate constraint by the caller. */
2679 handle_ptr_arith (struct constraint_expr lhs, tree expr)
2682 struct constraint_expr base, offset;
2684 if (TREE_CODE (expr) != PLUS_EXPR)
2687 op0 = TREE_OPERAND (expr, 0);
2688 op1 = TREE_OPERAND (expr, 1);
2690 base = get_constraint_for (op0);
2692 offset.var = anyoffset_id;
2693 offset.type = ADDRESSOF;
2696 process_constraint (new_constraint (lhs, base));
2697 process_constraint (new_constraint (lhs, offset));
2703 /* Walk statement T setting up aliasing constraints according to the
2704 references found in T. This function is the main part of the
2705 constraint builder. AI points to auxiliary alias information used
2706 when building alias sets and computing alias grouping heuristics. */
2709 find_func_aliases (tree t, struct alias_info *ai)
2711 struct constraint_expr lhs, rhs;
2713 /* Update various related attributes like escaped addresses, pointer
2714 dereferences for loads and stores. This is used when creating
2715 name tags and alias sets. */
2716 update_alias_info (t, ai);
2718 /* Now build constraints expressions. */
2719 if (TREE_CODE (t) == PHI_NODE)
2721 /* Only care about pointers and structures containing
2723 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
2724 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
2728 lhs = get_constraint_for (PHI_RESULT (t));
2729 for (i = 0; i < PHI_NUM_ARGS (t); i++)
2731 rhs = get_constraint_for (PHI_ARG_DEF (t, i));
2732 process_constraint (new_constraint (lhs, rhs));
2736 else if (TREE_CODE (t) == MODIFY_EXPR)
2738 tree lhsop = TREE_OPERAND (t, 0);
2739 tree rhsop = TREE_OPERAND (t, 1);
2742 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2743 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
2745 do_structure_copy (lhsop, rhsop);
2749 /* Only care about operations with pointers, structures
2750 containing pointers, dereferences, and call expressions. */
2751 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
2752 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2753 || ref_contains_indirect_ref (lhsop)
2754 || TREE_CODE (rhsop) == CALL_EXPR)
2756 lhs = get_constraint_for (lhsop);
2757 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
2759 /* RHS that consist of unary operations,
2760 exceptional types, or bare decls/constants, get
2761 handled directly by get_constraint_for. */
2763 case tcc_declaration:
2765 case tcc_exceptional:
2766 case tcc_expression:
2769 rhs = get_constraint_for (rhsop);
2770 process_constraint (new_constraint (lhs, rhs));
2772 /* When taking the address of an aggregate
2773 type, from the LHS we can access any field
2775 if (rhs.type == ADDRESSOF
2776 && rhs.var > anything_id
2777 && AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (rhsop))))
2779 rhs.var = anyoffset_id;
2780 rhs.type = ADDRESSOF;
2782 process_constraint (new_constraint (lhs, rhs));
2789 /* For pointer arithmetic of the form
2790 PTR + CST, we can simply use PTR's
2791 constraint because pointer arithmetic is
2792 not allowed to go out of bounds. */
2793 if (handle_ptr_arith (lhs, rhsop))
2798 /* Otherwise, walk each operand. Notice that we
2799 can't use the operand interface because we need
2800 to process expressions other than simple operands
2801 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
2803 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
2805 tree op = TREE_OPERAND (rhsop, i);
2806 rhs = get_constraint_for (op);
2807 process_constraint (new_constraint (lhs, rhs));
2814 /* After promoting variables and computing aliasing we will
2815 need to re-scan most statements. FIXME: Try to minimize the
2816 number of statements re-scanned. It's not really necessary to
2817 re-scan *all* statements. */
2818 mark_stmt_modified (t);
2822 /* Find the first varinfo in the same variable as START that overlaps with
2824 Effectively, walk the chain of fields for the variable START to find the
2825 first field that overlaps with OFFSET.
2826 Abort if we can't find one. */
2829 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
2831 varinfo_t curr = start;
2834 /* We may not find a variable in the field list with the actual
2835 offset when when we have glommed a structure to a variable.
2836 In that case, however, offset should still be within the size
2838 if (offset >= curr->offset && offset < (curr->offset + curr->size))
2847 /* Insert the varinfo FIELD into the field list for BASE, ordered by
2851 insert_into_field_list (varinfo_t base, varinfo_t field)
2853 varinfo_t prev = base;
2854 varinfo_t curr = base->next;
2865 if (field->offset <= curr->offset)
2870 field->next = prev->next;
2875 /* qsort comparison function for two fieldoff's PA and PB */
2878 fieldoff_compare (const void *pa, const void *pb)
2880 const fieldoff_s *foa = (const fieldoff_s *)pa;
2881 const fieldoff_s *fob = (const fieldoff_s *)pb;
2882 HOST_WIDE_INT foasize, fobsize;
2884 if (foa->offset != fob->offset)
2885 return foa->offset - fob->offset;
2887 foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
2888 fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
2889 return foasize - fobsize;
2892 /* Sort a fieldstack according to the field offset and sizes. */
2893 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
2895 qsort (VEC_address (fieldoff_s, fieldstack),
2896 VEC_length (fieldoff_s, fieldstack),
2897 sizeof (fieldoff_s),
2901 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
2902 of TYPE onto fieldstack, recording their offsets along the way.
2903 OFFSET is used to keep track of the offset in this entire structure, rather
2904 than just the immediately containing structure. Returns the number
2906 HAS_UNION is set to true if we find a union type as a field of
2910 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
2911 HOST_WIDE_INT offset, bool *has_union)
2916 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2917 if (TREE_CODE (field) == FIELD_DECL)
2922 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
2923 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
2926 if (!var_can_have_subvars (field))
2928 else if (!(push_fields_onto_fieldstack
2929 (TREE_TYPE (field), fieldstack,
2930 offset + bitpos_of_field (field), has_union))
2931 && DECL_SIZE (field)
2932 && !integer_zerop (DECL_SIZE (field)))
2933 /* Empty structures may have actual size, like in C++. So
2934 see if we didn't push any subfields and the size is
2935 nonzero, push the field onto the stack */
2942 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
2943 pair->field = field;
2944 pair->offset = offset + bitpos_of_field (field);
2953 make_constraint_to_anything (varinfo_t vi)
2955 struct constraint_expr lhs, rhs;
2961 rhs.var = anything_id;
2963 rhs.type = ADDRESSOF;
2964 process_constraint (new_constraint (lhs, rhs));
2967 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
2968 This will also create any varinfo structures necessary for fields
2972 create_variable_info_for (tree decl, const char *name)
2974 unsigned int index = VEC_length (varinfo_t, varmap);
2976 tree decltype = TREE_TYPE (decl);
2977 bool notokay = false;
2979 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
2980 VEC (fieldoff_s,heap) *fieldstack = NULL;
2983 hasunion = TREE_CODE (decltype) == UNION_TYPE
2984 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
2985 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
2987 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
2990 VEC_free (fieldoff_s, heap, fieldstack);
2996 /* If the variable doesn't have subvars, we may end up needing to
2997 sort the field list and create fake variables for all the
2999 vi = new_var_info (decl, index, name, index);
3002 vi->has_union = hasunion;
3003 if (!TYPE_SIZE (decltype)
3004 || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
3005 || TREE_CODE (decltype) == ARRAY_TYPE
3006 || TREE_CODE (decltype) == UNION_TYPE
3007 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
3009 vi->is_unknown_size_var = true;
3015 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
3016 vi->size = vi->fullsize;
3019 insert_id_for_tree (vi->decl, index);
3020 VEC_safe_push (varinfo_t, heap, varmap, vi);
3022 make_constraint_to_anything (vi);
3025 if (use_field_sensitive
3027 && !vi->is_unknown_size_var
3028 && var_can_have_subvars (decl))
3030 unsigned int newindex = VEC_length (varinfo_t, varmap);
3031 fieldoff_s *fo = NULL;
3035 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3037 if (!DECL_SIZE (fo->field)
3038 || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
3039 || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE
3047 /* We can't sort them if we have a field with a variable sized type,
3048 which will make notokay = true. In that case, we are going to return
3049 without creating varinfos for the fields anyway, so sorting them is a
3052 sort_fieldstack (fieldstack);
3054 if (VEC_length (fieldoff_s, fieldstack) != 0)
3055 fo = VEC_index (fieldoff_s, fieldstack, 0);
3057 if (fo == NULL || notokay)
3059 vi->is_unknown_size_var = 1;
3062 VEC_free (fieldoff_s, heap, fieldstack);
3067 vi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
3068 for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3071 const char *newname;
3075 newindex = VEC_length (varinfo_t, varmap);
3076 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (field));
3077 newname = ggc_strdup (tempname);
3079 newvi = new_var_info (decl, newindex, newname, newindex);
3080 newvi->offset = fo->offset;
3081 newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
3082 newvi->fullsize = vi->fullsize;
3083 insert_into_field_list (vi, newvi);
3084 VEC_safe_push (varinfo_t, heap, varmap, newvi);
3086 make_constraint_to_anything (newvi);
3090 VEC_free (fieldoff_s, heap, fieldstack);
3095 /* Print out the points-to solution for VAR to FILE. */
3098 dump_solution_for_var (FILE *file, unsigned int var)
3100 varinfo_t vi = get_varinfo (var);
3104 fprintf (file, "%s = { ", vi->name);
3105 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
3107 fprintf (file, "%s ", get_varinfo (i)->name);
3109 fprintf (file, "}\n");
3112 /* Print the points-to solution for VAR to stdout. */
3115 debug_solution_for_var (unsigned int var)
3117 dump_solution_for_var (stdout, var);
3121 /* Create varinfo structures for all of the variables in the
3122 function for intraprocedural mode. */
3125 intra_create_variable_infos (void)
3129 /* For each incoming argument arg, ARG = &ANYTHING */
3130 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
3132 struct constraint_expr lhs;
3133 struct constraint_expr rhs;
3138 lhs.var = create_variable_info_for (t, alias_get_name (t));
3140 rhs.var = anything_id;
3141 rhs.type = ADDRESSOF;
3144 for (p = get_varinfo (lhs.var); p; p = p->next)
3146 struct constraint_expr temp = lhs;
3148 process_constraint (new_constraint (temp, rhs));
3154 /* Set bits in INTO corresponding to the variable uids in solution set
3158 set_uids_in_ptset (bitmap into, bitmap from)
3162 bool found_anyoffset = false;
3165 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
3167 varinfo_t vi = get_varinfo (i);
3169 /* If we find ANYOFFSET in the solution and the solution
3170 includes SFTs for some structure, then all the SFTs in that
3171 structure will need to be added to the alias set. */
3172 if (vi->id == anyoffset_id)
3174 found_anyoffset = true;
3178 /* The only artificial variables that are allowed in a may-alias
3179 set are heap variables. */
3180 if (vi->is_artificial_var && !vi->is_heap_var)
3183 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
3185 /* Variables containing unions may need to be converted to
3186 their SFT's, because SFT's can have unions and we cannot. */
3187 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
3188 bitmap_set_bit (into, DECL_UID (sv->var));
3190 else if (TREE_CODE (vi->decl) == VAR_DECL
3191 || TREE_CODE (vi->decl) == PARM_DECL)
3194 && var_can_have_subvars (vi->decl)
3195 && get_subvars_for_var (vi->decl))
3197 /* If ANYOFFSET is in the solution set and VI->DECL is
3198 an aggregate variable with sub-variables, then any of
3199 the SFTs inside VI->DECL may have been accessed. Add
3200 all the sub-vars for VI->DECL. */
3201 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
3202 bitmap_set_bit (into, DECL_UID (sv->var));
3204 else if (var_can_have_subvars (vi->decl)
3205 && get_subvars_for_var (vi->decl))
3207 /* If VI->DECL is an aggregate for which we created
3208 SFTs, add the SFT corresponding to VI->OFFSET. */
3209 tree sft = get_subvar_at (vi->decl, vi->offset);
3210 bitmap_set_bit (into, DECL_UID (sft));
3214 /* Otherwise, just add VI->DECL to the alias set. */
3215 bitmap_set_bit (into, DECL_UID (vi->decl));
3222 static bool have_alias_info = false;
3224 /* Given a pointer variable P, fill in its points-to set, or return
3225 false if we can't. */
3228 find_what_p_points_to (tree p)
3230 unsigned int id = 0;
3232 if (!have_alias_info)
3235 if (lookup_id_for_tree (p, &id))
3237 varinfo_t vi = get_varinfo (id);
3239 if (vi->is_artificial_var)
3242 /* See if this is a field or a structure. */
3243 if (vi->size != vi->fullsize)
3245 /* Nothing currently asks about structure fields directly,
3246 but when they do, we need code here to hand back the
3248 if (!var_can_have_subvars (vi->decl)
3249 || get_subvars_for_var (vi->decl) == NULL)
3254 struct ptr_info_def *pi = get_ptr_info (p);
3258 /* This variable may have been collapsed, let's get the real
3260 vi = get_varinfo (vi->node);
3262 /* Translate artificial variables into SSA_NAME_PTR_INFO
3264 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
3266 varinfo_t vi = get_varinfo (i);
3268 if (vi->is_artificial_var)
3270 /* FIXME. READONLY should be handled better so that
3271 flow insensitive aliasing can disregard writeable
3273 if (vi->id == nothing_id)
3275 else if (vi->id == anything_id)
3276 pi->pt_anything = 1;
3277 else if (vi->id == readonly_id)
3278 pi->pt_anything = 1;
3279 else if (vi->id == integer_id)
3280 pi->pt_anything = 1;
3281 else if (vi->is_heap_var)
3282 pi->pt_global_mem = 1;
3286 if (pi->pt_anything)
3290 pi->pt_vars = BITMAP_GGC_ALLOC ();
3292 set_uids_in_ptset (pi->pt_vars, vi->solution);
3294 if (bitmap_empty_p (pi->pt_vars))
3305 /* Initialize things necessary to perform PTA */
3308 init_alias_vars (void)
3310 bitmap_obstack_initialize (&ptabitmap_obstack);
3314 /* Dump points-to information to OUTFILE. */
3317 dump_sa_points_to_info (FILE *outfile)
3321 fprintf (outfile, "\nPoints-to sets\n\n");
3323 if (dump_flags & TDF_STATS)
3325 fprintf (outfile, "Stats:\n");
3326 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
3327 fprintf (outfile, "Statically unified vars: %d\n",
3328 stats.unified_vars_static);
3329 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
3330 fprintf (outfile, "Dynamically unified vars: %d\n",
3331 stats.unified_vars_dynamic);
3332 fprintf (outfile, "Iterations: %d\n", stats.iterations);
3335 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
3336 dump_solution_for_var (outfile, i);
3340 /* Debug points-to information to stderr. */
3343 debug_sa_points_to_info (void)
3345 dump_sa_points_to_info (stderr);
3349 /* Initialize the always-existing constraint variables for NULL
3350 ANYTHING, READONLY, and INTEGER */
3353 init_base_vars (void)
3355 struct constraint_expr lhs, rhs;
3357 /* Create the NULL variable, used to represent that a variable points
3359 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
3360 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
3361 insert_id_for_tree (nothing_tree, 0);
3362 var_nothing->is_artificial_var = 1;
3363 var_nothing->offset = 0;
3364 var_nothing->size = ~0;
3365 var_nothing->fullsize = ~0;
3367 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
3369 /* Create the ANYTHING variable, used to represent that a variable
3370 points to some unknown piece of memory. */
3371 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
3372 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
3373 insert_id_for_tree (anything_tree, 1);
3374 var_anything->is_artificial_var = 1;
3375 var_anything->size = ~0;
3376 var_anything->offset = 0;
3377 var_anything->next = NULL;
3378 var_anything->fullsize = ~0;
3381 /* Anything points to anything. This makes deref constraints just
3382 work in the presence of linked list and other p = *p type loops,
3383 by saying that *ANYTHING = ANYTHING. */
3384 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
3386 lhs.var = anything_id;
3388 rhs.type = ADDRESSOF;
3389 rhs.var = anything_id;
3391 var_anything->address_taken = true;
3393 /* This specifically does not use process_constraint because
3394 process_constraint ignores all anything = anything constraints, since all
3395 but this one are redundant. */
3396 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
3398 /* Create the READONLY variable, used to represent that a variable
3399 points to readonly memory. */
3400 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
3401 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
3402 var_readonly->is_artificial_var = 1;
3403 var_readonly->offset = 0;
3404 var_readonly->size = ~0;
3405 var_readonly->fullsize = ~0;
3406 var_readonly->next = NULL;
3407 insert_id_for_tree (readonly_tree, 2);
3409 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
3411 /* readonly memory points to anything, in order to make deref
3412 easier. In reality, it points to anything the particular
3413 readonly variable can point to, but we don't track this
3416 lhs.var = readonly_id;
3418 rhs.type = ADDRESSOF;
3419 rhs.var = anything_id;
3422 process_constraint (new_constraint (lhs, rhs));
3424 /* Create the INTEGER variable, used to represent that a variable points
3426 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
3427 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
3428 insert_id_for_tree (integer_tree, 3);
3429 var_integer->is_artificial_var = 1;
3430 var_integer->size = ~0;
3431 var_integer->fullsize = ~0;
3432 var_integer->offset = 0;
3433 var_integer->next = NULL;
3435 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
3437 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
3438 integer will point to. */
3440 lhs.var = integer_id;
3442 rhs.type = ADDRESSOF;
3443 rhs.var = anything_id;
3445 process_constraint (new_constraint (lhs, rhs));
3447 /* Create the ANYOFFSET variable, used to represent an arbitrary offset
3448 inside an object. This is similar to ANYTHING, but less drastic.
3449 It means that the pointer can point anywhere inside an object,
3450 but not outside of it. */
3451 anyoffset_tree = create_tmp_var_raw (void_type_node, "ANYOFFSET");
3453 var_anyoffset = new_var_info (anyoffset_tree, anyoffset_id, "ANYOFFSET",
3455 insert_id_for_tree (anyoffset_tree, anyoffset_id);
3456 var_anyoffset->is_artificial_var = 1;
3457 var_anyoffset->size = ~0;
3458 var_anyoffset->offset = 0;
3459 var_anyoffset->next = NULL;
3460 var_anyoffset->fullsize = ~0;
3461 VEC_safe_push (varinfo_t, heap, varmap, var_anyoffset);
3463 /* ANYOFFSET points to ANYOFFSET. */
3465 lhs.var = anyoffset_id;
3467 rhs.type = ADDRESSOF;
3468 rhs.var = anyoffset_id;
3470 process_constraint (new_constraint (lhs, rhs));
3474 /* Create points-to sets for the current function. See the comments
3475 at the start of the file for an algorithmic overview. */
3478 compute_points_to_sets (struct alias_info *ai)
3482 timevar_push (TV_TREE_PTA);
3486 constraint_pool = create_alloc_pool ("Constraint pool",
3487 sizeof (struct constraint), 30);
3488 variable_info_pool = create_alloc_pool ("Variable info pool",
3489 sizeof (struct variable_info), 30);
3490 constraint_edge_pool = create_alloc_pool ("Constraint edges",
3491 sizeof (struct constraint_edge), 30);
3493 constraints = VEC_alloc (constraint_t, heap, 8);
3494 varmap = VEC_alloc (varinfo_t, heap, 8);
3495 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
3496 memset (&stats, 0, sizeof (stats));
3500 intra_create_variable_infos ();
3502 /* Now walk all statements and derive aliases. */
3505 block_stmt_iterator bsi;
3508 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3509 if (is_gimple_reg (PHI_RESULT (phi)))
3510 find_func_aliases (phi, ai);
3512 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3513 find_func_aliases (bsi_stmt (bsi), ai);
3516 build_constraint_graph ();
3520 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
3521 dump_constraints (dump_file);
3525 fprintf (dump_file, "\nCollapsing static cycles and doing variable "
3528 find_and_collapse_graph_cycles (graph, false);
3529 perform_var_substitution (graph);
3532 fprintf (dump_file, "\nSolving graph:\n");
3534 solve_graph (graph);
3537 dump_sa_points_to_info (dump_file);
3539 have_alias_info = true;
3541 timevar_pop (TV_TREE_PTA);
3545 /* Delete created points-to sets. */
3548 delete_points_to_sets (void)
3553 htab_delete (id_for_tree);
3554 bitmap_obstack_release (&ptabitmap_obstack);
3555 VEC_free (constraint_t, heap, constraints);
3557 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
3559 VEC_free (constraint_edge_t, heap, graph->succs[i]);
3560 VEC_free (constraint_edge_t, heap, graph->preds[i]);
3561 VEC_free (constraint_t, heap, v->complex);
3563 free (graph->succs);
3564 free (graph->preds);
3567 VEC_free (varinfo_t, heap, varmap);
3568 free_alloc_pool (variable_info_pool);
3569 free_alloc_pool (constraint_pool);
3570 free_alloc_pool (constraint_edge_pool);
3572 have_alias_info = false;