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 if this is a special variable whose solution set should not be
222 unsigned int is_special_var:1;
224 /* True for variables whose size is not known or variable. */
225 unsigned int is_unknown_size_var:1;
227 /* True for variables that have unions somewhere in them. */
228 unsigned int has_union:1;
230 /* True if this is a heap variable. */
231 unsigned int is_heap_var:1;
233 /* Points-to set for this variable. */
236 /* Variable ids represented by this node. */
239 /* Vector of complex constraints for this node. Complex
240 constraints are those involving dereferences. */
241 VEC(constraint_t,heap) *complex;
243 typedef struct variable_info *varinfo_t;
245 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
247 /* Pool of variable info structures. */
248 static alloc_pool variable_info_pool;
250 DEF_VEC_P(varinfo_t);
252 DEF_VEC_ALLOC_P(varinfo_t, heap);
254 /* Table of variable info structures for constraint variables. Indexed directly
255 by variable info id. */
256 static VEC(varinfo_t,heap) *varmap;
258 /* Return the varmap element N */
260 static inline varinfo_t
261 get_varinfo(unsigned int n)
263 return VEC_index(varinfo_t, varmap, n);
266 /* Variable that represents the unknown pointer. */
267 static varinfo_t var_anything;
268 static tree anything_tree;
269 static unsigned int anything_id;
271 /* Variable that represents the NULL pointer. */
272 static varinfo_t var_nothing;
273 static tree nothing_tree;
274 static unsigned int nothing_id;
276 /* Variable that represents read only memory. */
277 static varinfo_t var_readonly;
278 static tree readonly_tree;
279 static unsigned int readonly_id;
281 /* Variable that represents integers. This is used for when people do things
283 static varinfo_t var_integer;
284 static tree integer_tree;
285 static unsigned int integer_id;
287 /* Variable that represents arbitrary offsets into an object. Used to
288 represent pointer arithmetic, which may not legally escape the
289 bounds of an object. */
290 static varinfo_t var_anyoffset;
291 static tree anyoffset_tree;
292 static unsigned int anyoffset_id;
294 /* Return a new variable info structure consisting for a variable
295 named NAME, and using constraint graph node NODE. */
298 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
300 varinfo_t ret = pool_alloc (variable_info_pool);
306 ret->address_taken = false;
307 ret->indirect_target = false;
308 ret->is_artificial_var = false;
309 ret->is_heap_var = false;
310 ret->is_special_var = false;
311 ret->is_unknown_size_var = false;
312 ret->has_union = false;
313 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
314 bitmap_clear (ret->solution);
315 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
316 bitmap_clear (ret->variables);
322 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
324 /* An expression that appears in a constraint. */
326 struct constraint_expr
328 /* Constraint type. */
329 constraint_expr_type type;
331 /* Variable we are referring to in the constraint. */
334 /* Offset, in bits, of this constraint from the beginning of
335 variables it ends up referring to.
337 IOW, in a deref constraint, we would deref, get the result set,
338 then add OFFSET to each member. */
339 unsigned HOST_WIDE_INT offset;
342 static struct constraint_expr do_deref (struct constraint_expr);
344 /* Our set constraints are made up of two constraint expressions, one
347 As described in the introduction, our set constraints each represent an
348 operation between set valued variables.
352 struct constraint_expr lhs;
353 struct constraint_expr rhs;
356 /* List of constraints that we use to build the constraint graph from. */
358 static VEC(constraint_t,heap) *constraints;
359 static alloc_pool constraint_pool;
361 /* An edge in the constraint graph. We technically have no use for
362 the src, since it will always be the same node that we are indexing
363 into the pred/succ arrays with, but it's nice for checking
364 purposes. The edges are weighted, with a bit set in weights for
365 each edge from src to dest with that weight. */
367 struct constraint_edge
374 typedef struct constraint_edge *constraint_edge_t;
375 static alloc_pool constraint_edge_pool;
377 /* Return a new constraint edge from SRC to DEST. */
379 static constraint_edge_t
380 new_constraint_edge (unsigned int src, unsigned int dest)
382 constraint_edge_t ret = pool_alloc (constraint_edge_pool);
389 DEF_VEC_P(constraint_edge_t);
390 DEF_VEC_ALLOC_P(constraint_edge_t,heap);
393 /* The constraint graph is simply a set of adjacency vectors, one per
394 variable. succs[x] is the vector of successors for variable x, and preds[x]
395 is the vector of predecessors for variable x.
396 IOW, all edges are "forward" edges, which is not like our CFG.
398 preds[x]->src == x, and
399 succs[x]->src == x. */
401 struct constraint_graph
403 VEC(constraint_edge_t,heap) **succs;
404 VEC(constraint_edge_t,heap) **preds;
407 typedef struct constraint_graph *constraint_graph_t;
409 static constraint_graph_t graph;
411 /* Create a new constraint consisting of LHS and RHS expressions. */
414 new_constraint (const struct constraint_expr lhs,
415 const struct constraint_expr rhs)
417 constraint_t ret = pool_alloc (constraint_pool);
423 /* Print out constraint C to FILE. */
426 dump_constraint (FILE *file, constraint_t c)
428 if (c->lhs.type == ADDRESSOF)
430 else if (c->lhs.type == DEREF)
432 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
433 if (c->lhs.offset != 0)
434 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
435 fprintf (file, " = ");
436 if (c->rhs.type == ADDRESSOF)
438 else if (c->rhs.type == DEREF)
440 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
441 if (c->rhs.offset != 0)
442 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
443 fprintf (file, "\n");
446 /* Print out constraint C to stderr. */
449 debug_constraint (constraint_t c)
451 dump_constraint (stderr, c);
454 /* Print out all constraints to FILE */
457 dump_constraints (FILE *file)
461 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
462 dump_constraint (file, c);
465 /* Print out all constraints to stderr. */
468 debug_constraints (void)
470 dump_constraints (stderr);
475 The solver is a simple worklist solver, that works on the following
478 sbitmap changed_nodes = all ones;
479 changed_count = number of nodes;
480 For each node that was already collapsed:
484 while (changed_count > 0)
486 compute topological ordering for constraint graph
488 find and collapse cycles in the constraint graph (updating
489 changed if necessary)
491 for each node (n) in the graph in topological order:
494 Process each complex constraint associated with the node,
495 updating changed if necessary.
497 For each outgoing edge from n, propagate the solution from n to
498 the destination of the edge, updating changed as necessary.
502 /* Return true if two constraint expressions A and B are equal. */
505 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
507 return a.type == b.type
509 && a.offset == b.offset;
512 /* Return true if constraint expression A is less than constraint expression
513 B. This is just arbitrary, but consistent, in order to give them an
517 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
519 if (a.type == b.type)
522 return a.offset < b.offset;
524 return a.var < b.var;
527 return a.type < b.type;
530 /* Return true if constraint A is less than constraint B. This is just
531 arbitrary, but consistent, in order to give them an ordering. */
534 constraint_less (const constraint_t a, const constraint_t b)
536 if (constraint_expr_less (a->lhs, b->lhs))
538 else if (constraint_expr_less (b->lhs, a->lhs))
541 return constraint_expr_less (a->rhs, b->rhs);
544 /* Return true if two constraints A and B are equal. */
547 constraint_equal (struct constraint a, struct constraint b)
549 return constraint_expr_equal (a.lhs, b.lhs)
550 && constraint_expr_equal (a.rhs, b.rhs);
554 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
557 constraint_vec_find (VEC(constraint_t,heap) *vec,
558 struct constraint lookfor)
566 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
567 if (place >= VEC_length (constraint_t, vec))
569 found = VEC_index (constraint_t, vec, place);
570 if (!constraint_equal (*found, lookfor))
575 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
578 constraint_set_union (VEC(constraint_t,heap) **to,
579 VEC(constraint_t,heap) **from)
584 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
586 if (constraint_vec_find (*to, *c) == NULL)
588 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
590 VEC_safe_insert (constraint_t, heap, *to, place, c);
595 /* Take a solution set SET, add OFFSET to each member of the set, and
596 overwrite SET with the result when done. */
599 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
601 bitmap result = BITMAP_ALLOC (&iteration_obstack);
605 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
607 /* If this is a properly sized variable, only add offset if it's
608 less than end. Otherwise, it is globbed to a single
611 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
613 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
614 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
615 bitmap_set_bit (result, v->id);
617 else if (get_varinfo (i)->is_artificial_var
618 || get_varinfo (i)->has_union
619 || get_varinfo (i)->is_unknown_size_var)
621 bitmap_set_bit (result, i);
625 bitmap_copy (set, result);
626 BITMAP_FREE (result);
629 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
633 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
636 return bitmap_ior_into (to, from);
642 tmp = BITMAP_ALLOC (&iteration_obstack);
643 bitmap_copy (tmp, from);
644 solution_set_add (tmp, inc);
645 res = bitmap_ior_into (to, tmp);
651 /* Insert constraint C into the list of complex constraints for VAR. */
654 insert_into_complex (unsigned int var, constraint_t c)
656 varinfo_t vi = get_varinfo (var);
657 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
659 VEC_safe_insert (constraint_t, heap, vi->complex, place, c);
663 /* Compare two constraint edges A and B, return true if they are equal. */
666 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
668 return a.src == b.src && a.dest == b.dest;
671 /* Compare two constraint edges, return true if A is less than B */
674 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
676 if (a->dest < b->dest)
678 else if (a->dest == b->dest)
679 return a->src < b->src;
684 /* Find the constraint edge that matches LOOKFOR, in VEC.
685 Return the edge, if found, NULL otherwise. */
687 static constraint_edge_t
688 constraint_edge_vec_find (VEC(constraint_edge_t,heap) *vec,
689 struct constraint_edge lookfor)
692 constraint_edge_t edge;
694 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
695 constraint_edge_less);
696 edge = VEC_index (constraint_edge_t, vec, place);
697 if (!constraint_edge_equal (*edge, lookfor))
702 /* Condense two variable nodes into a single variable node, by moving
703 all associated info from SRC to TO. */
706 condense_varmap_nodes (unsigned int to, unsigned int src)
708 varinfo_t tovi = get_varinfo (to);
709 varinfo_t srcvi = get_varinfo (src);
714 /* the src node, and all its variables, are now the to node. */
716 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
717 get_varinfo (i)->node = to;
719 /* Merge the src node variables and the to node variables. */
720 bitmap_set_bit (tovi->variables, src);
721 bitmap_ior_into (tovi->variables, srcvi->variables);
722 bitmap_clear (srcvi->variables);
724 /* Move all complex constraints from src node into to node */
725 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
727 /* In complex constraints for node src, we may have either
728 a = *src, and *src = a. */
730 if (c->rhs.type == DEREF)
735 constraint_set_union (&tovi->complex, &srcvi->complex);
736 VEC_free (constraint_t, heap, srcvi->complex);
737 srcvi->complex = NULL;
740 /* Erase EDGE from GRAPH. This routine only handles self-edges
741 (e.g. an edge from a to a). */
744 erase_graph_self_edge (constraint_graph_t graph, struct constraint_edge edge)
746 VEC(constraint_edge_t,heap) *predvec = graph->preds[edge.src];
747 VEC(constraint_edge_t,heap) *succvec = graph->succs[edge.dest];
749 gcc_assert (edge.src == edge.dest);
751 /* Remove from the successors. */
752 place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
753 constraint_edge_less);
755 /* Make sure we found the edge. */
756 #ifdef ENABLE_CHECKING
758 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
759 gcc_assert (constraint_edge_equal (*tmp, edge));
762 VEC_ordered_remove (constraint_edge_t, succvec, place);
764 /* Remove from the predecessors. */
765 place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
766 constraint_edge_less);
768 /* Make sure we found the edge. */
769 #ifdef ENABLE_CHECKING
771 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
772 gcc_assert (constraint_edge_equal (*tmp, edge));
775 VEC_ordered_remove (constraint_edge_t, predvec, place);
778 /* Remove edges involving NODE from GRAPH. */
781 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
783 VEC(constraint_edge_t,heap) *succvec = graph->succs[node];
784 VEC(constraint_edge_t,heap) *predvec = graph->preds[node];
788 /* Walk the successors, erase the associated preds. */
789 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
793 struct constraint_edge lookfor;
794 lookfor.src = c->dest;
796 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
797 &lookfor, constraint_edge_less);
798 VEC_ordered_remove (constraint_edge_t, graph->preds[c->dest], place);
800 /* Walk the preds, erase the associated succs. */
801 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
805 struct constraint_edge lookfor;
806 lookfor.src = c->dest;
808 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
809 &lookfor, constraint_edge_less);
810 VEC_ordered_remove (constraint_edge_t, graph->succs[c->dest], place);
813 VEC_free (constraint_edge_t, heap, graph->preds[node]);
814 VEC_free (constraint_edge_t, heap, graph->succs[node]);
815 graph->preds[node] = NULL;
816 graph->succs[node] = NULL;
819 static bool edge_added = false;
821 /* Add edge NEWE to the graph. */
824 add_graph_edge (constraint_graph_t graph, struct constraint_edge newe)
827 unsigned int src = newe.src;
828 unsigned int dest = newe.dest;
829 VEC(constraint_edge_t,heap) *vec;
831 vec = graph->preds[src];
832 place = VEC_lower_bound (constraint_edge_t, vec, &newe,
833 constraint_edge_less);
834 if (place == VEC_length (constraint_edge_t, vec)
835 || VEC_index (constraint_edge_t, vec, place)->dest != dest)
837 constraint_edge_t edge = new_constraint_edge (src, dest);
840 weightbitmap = BITMAP_ALLOC (&ptabitmap_obstack);
841 edge->weights = weightbitmap;
842 VEC_safe_insert (constraint_edge_t, heap, graph->preds[edge->src],
844 edge = new_constraint_edge (dest, src);
845 edge->weights = weightbitmap;
846 place = VEC_lower_bound (constraint_edge_t, graph->succs[edge->src],
847 edge, constraint_edge_less);
848 VEC_safe_insert (constraint_edge_t, heap, graph->succs[edge->src],
858 /* Return the bitmap representing the weights of edge LOOKFOR */
861 get_graph_weights (constraint_graph_t graph, struct constraint_edge lookfor)
863 constraint_edge_t edge;
864 unsigned int src = lookfor.src;
865 VEC(constraint_edge_t,heap) *vec;
866 vec = graph->preds[src];
867 edge = constraint_edge_vec_find (vec, lookfor);
868 gcc_assert (edge != NULL);
869 return edge->weights;
873 /* Merge GRAPH nodes FROM and TO into node TO. */
876 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
879 VEC(constraint_edge_t,heap) *succvec = graph->succs[from];
880 VEC(constraint_edge_t,heap) *predvec = graph->preds[from];
884 /* Merge all the predecessor edges. */
886 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
888 unsigned int d = c->dest;
889 struct constraint_edge olde;
890 struct constraint_edge newe;
897 add_graph_edge (graph, newe);
900 temp = get_graph_weights (graph, olde);
901 weights = get_graph_weights (graph, newe);
902 bitmap_ior_into (weights, temp);
905 /* Merge all the successor edges. */
906 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
908 unsigned int d = c->dest;
909 struct constraint_edge olde;
910 struct constraint_edge newe;
917 add_graph_edge (graph, newe);
920 temp = get_graph_weights (graph, olde);
921 weights = get_graph_weights (graph, newe);
922 bitmap_ior_into (weights, temp);
924 clear_edges_for_node (graph, from);
927 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
928 it doesn't exist in the graph already.
929 Return false if the edge already existed, true otherwise. */
932 int_add_graph_edge (constraint_graph_t graph, unsigned int to,
933 unsigned int from, unsigned HOST_WIDE_INT weight)
935 if (to == from && weight == 0)
942 struct constraint_edge edge;
945 r = add_graph_edge (graph, edge);
946 r |= !bitmap_bit_p (get_graph_weights (graph, edge), weight);
947 bitmap_set_bit (get_graph_weights (graph, edge), weight);
953 /* Return true if LOOKFOR is an existing graph edge. */
956 valid_graph_edge (constraint_graph_t graph, struct constraint_edge lookfor)
958 return constraint_edge_vec_find (graph->preds[lookfor.src], lookfor) != NULL;
962 /* Build the constraint graph. */
965 build_constraint_graph (void)
970 graph = xmalloc (sizeof (struct constraint_graph));
971 graph->succs = xcalloc (VEC_length (varinfo_t, varmap),
972 sizeof (*graph->succs));
973 graph->preds = xcalloc (VEC_length (varinfo_t, varmap),
974 sizeof (*graph->preds));
976 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
978 struct constraint_expr lhs = c->lhs;
979 struct constraint_expr rhs = c->rhs;
980 if (lhs.type == DEREF)
982 /* *x = y or *x = &y (complex) */
983 if (rhs.type == ADDRESSOF || rhs.var > anything_id)
984 insert_into_complex (lhs.var, c);
986 else if (rhs.type == DEREF)
988 /* !special var= *y */
989 if (!(get_varinfo (lhs.var)->is_special_var))
990 insert_into_complex (rhs.var, c);
992 else if (rhs.type == ADDRESSOF)
995 bitmap_set_bit (get_varinfo (lhs.var)->solution, rhs.var);
997 else if (rhs.var > anything_id && lhs.var > anything_id)
999 /* Ignore 0 weighted self edges, as they can't possibly contribute
1001 if (lhs.var != rhs.var || rhs.offset != 0 || lhs.offset != 0)
1004 struct constraint_edge edge;
1006 edge.dest = rhs.var;
1007 /* x = y (simple) */
1008 add_graph_edge (graph, edge);
1009 bitmap_set_bit (get_graph_weights (graph, edge),
1018 /* Changed variables on the last iteration. */
1019 static unsigned int changed_count;
1020 static sbitmap changed;
1022 DEF_VEC_I(unsigned);
1023 DEF_VEC_ALLOC_I(unsigned,heap);
1026 /* Strongly Connected Component visitation info. */
1031 sbitmap in_component;
1033 unsigned int *visited_index;
1034 VEC(unsigned,heap) *scc_stack;
1035 VEC(unsigned,heap) *unification_queue;
1039 /* Recursive routine to find strongly connected components in GRAPH.
1040 SI is the SCC info to store the information in, and N is the id of current
1041 graph node we are processing.
1043 This is Tarjan's strongly connected component finding algorithm, as
1044 modified by Nuutila to keep only non-root nodes on the stack.
1045 The algorithm can be found in "On finding the strongly connected
1046 connected components in a directed graph" by Esko Nuutila and Eljas
1047 Soisalon-Soininen, in Information Processing Letters volume 49,
1048 number 1, pages 9-14. */
1051 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1053 constraint_edge_t c;
1056 gcc_assert (get_varinfo (n)->node == n);
1057 SET_BIT (si->visited, n);
1058 RESET_BIT (si->in_component, n);
1059 si->visited_index[n] = si->current_index ++;
1061 /* Visit all the successors. */
1062 for (i = 0; VEC_iterate (constraint_edge_t, graph->succs[n], i, c); i++)
1064 /* We only want to find and collapse the zero weight edges. */
1065 if (bitmap_bit_p (c->weights, 0))
1067 unsigned int w = c->dest;
1068 if (!TEST_BIT (si->visited, w))
1069 scc_visit (graph, si, w);
1070 if (!TEST_BIT (si->in_component, w))
1072 unsigned int t = get_varinfo (w)->node;
1073 unsigned int nnode = get_varinfo (n)->node;
1074 if (si->visited_index[t] < si->visited_index[nnode])
1075 get_varinfo (n)->node = t;
1080 /* See if any components have been identified. */
1081 if (get_varinfo (n)->node == n)
1083 unsigned int t = si->visited_index[n];
1084 SET_BIT (si->in_component, n);
1085 while (VEC_length (unsigned, si->scc_stack) != 0
1086 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1088 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1089 get_varinfo (w)->node = n;
1090 SET_BIT (si->in_component, w);
1091 /* Mark this node for collapsing. */
1092 VEC_safe_push (unsigned, heap, si->unification_queue, w);
1096 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1100 /* Collapse two variables into one variable. */
1103 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1105 bitmap tosol, fromsol;
1106 struct constraint_edge edge;
1109 condense_varmap_nodes (to, from);
1110 tosol = get_varinfo (to)->solution;
1111 fromsol = get_varinfo (from)->solution;
1112 bitmap_ior_into (tosol, fromsol);
1113 merge_graph_nodes (graph, to, from);
1116 if (valid_graph_edge (graph, edge))
1118 bitmap weights = get_graph_weights (graph, edge);
1119 bitmap_clear_bit (weights, 0);
1120 if (bitmap_empty_p (weights))
1121 erase_graph_self_edge (graph, edge);
1123 bitmap_clear (fromsol);
1124 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1125 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1129 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1130 SI is the Strongly Connected Components information structure that tells us
1131 what components to unify.
1132 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1133 count should be updated to reflect the unification. */
1136 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1137 bool update_changed)
1140 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1143 /* We proceed as follows:
1145 For each component in the queue (components are delineated by
1146 when current_queue_element->node != next_queue_element->node):
1148 rep = representative node for component
1150 For each node (tounify) to be unified in the component,
1151 merge the solution for tounify into tmp bitmap
1153 clear solution for tounify
1155 merge edges from tounify into rep
1157 merge complex constraints from tounify into rep
1159 update changed count to note that tounify will never change
1162 Merge tmp into solution for rep, marking rep changed if this
1163 changed rep's solution.
1165 Delete any 0 weighted self-edges we now have for rep. */
1166 while (i != VEC_length (unsigned, si->unification_queue))
1168 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1169 unsigned int n = get_varinfo (tounify)->node;
1171 if (dump_file && (dump_flags & TDF_DETAILS))
1172 fprintf (dump_file, "Unifying %s to %s\n",
1173 get_varinfo (tounify)->name,
1174 get_varinfo (n)->name);
1176 stats.unified_vars_dynamic++;
1178 stats.unified_vars_static++;
1179 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1180 merge_graph_nodes (graph, n, tounify);
1181 condense_varmap_nodes (n, tounify);
1183 if (update_changed && TEST_BIT (changed, tounify))
1185 RESET_BIT (changed, tounify);
1186 if (!TEST_BIT (changed, n))
1187 SET_BIT (changed, n);
1190 gcc_assert (changed_count > 0);
1195 bitmap_clear (get_varinfo (tounify)->solution);
1198 /* If we've either finished processing the entire queue, or
1199 finished processing all nodes for component n, update the solution for
1201 if (i == VEC_length (unsigned, si->unification_queue)
1202 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1204 struct constraint_edge edge;
1206 /* If the solution changes because of the merging, we need to mark
1207 the variable as changed. */
1208 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1210 if (update_changed && !TEST_BIT (changed, n))
1212 SET_BIT (changed, n);
1219 if (valid_graph_edge (graph, edge))
1221 bitmap weights = get_graph_weights (graph, edge);
1222 bitmap_clear_bit (weights, 0);
1223 if (bitmap_empty_p (weights))
1224 erase_graph_self_edge (graph, edge);
1232 /* Information needed to compute the topological ordering of a graph. */
1236 /* sbitmap of visited nodes. */
1238 /* Array that stores the topological order of the graph, *in
1240 VEC(unsigned,heap) *topo_order;
1244 /* Initialize and return a topological info structure. */
1246 static struct topo_info *
1247 init_topo_info (void)
1249 size_t size = VEC_length (varinfo_t, varmap);
1250 struct topo_info *ti = xmalloc (sizeof (struct topo_info));
1251 ti->visited = sbitmap_alloc (size);
1252 sbitmap_zero (ti->visited);
1253 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1258 /* Free the topological sort info pointed to by TI. */
1261 free_topo_info (struct topo_info *ti)
1263 sbitmap_free (ti->visited);
1264 VEC_free (unsigned, heap, ti->topo_order);
1268 /* Visit the graph in topological order, and store the order in the
1269 topo_info structure. */
1272 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1275 VEC(constraint_edge_t,heap) *succs = graph->succs[n];
1276 constraint_edge_t c;
1278 SET_BIT (ti->visited, n);
1279 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1281 if (!TEST_BIT (ti->visited, c->dest))
1282 topo_visit (graph, ti, c->dest);
1284 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1287 /* Return true if variable N + OFFSET is a legal field of N. */
1290 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1292 varinfo_t ninfo = get_varinfo (n);
1294 /* For things we've globbed to single variables, any offset into the
1295 variable acts like the entire variable, so that it becomes offset
1297 if (ninfo->is_special_var
1298 || ninfo->is_artificial_var
1299 || ninfo->is_unknown_size_var)
1304 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1307 /* Process a constraint C that represents *x = &y. */
1310 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1311 constraint_t c, bitmap delta)
1313 unsigned int rhs = c->rhs.var;
1317 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1318 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1320 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1321 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
1323 /* *x != NULL && *x != ANYTHING*/
1327 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1329 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1331 sol = get_varinfo (t)->solution;
1332 if (!bitmap_bit_p (sol, rhs))
1334 bitmap_set_bit (sol, rhs);
1335 if (!TEST_BIT (changed, t))
1337 SET_BIT (changed, t);
1342 else if (dump_file && !(get_varinfo (j)->is_special_var))
1343 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1348 /* Process a constraint C that represents x = *y, using DELTA as the
1349 starting solution. */
1352 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1355 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1357 bitmap sol = get_varinfo (lhs)->solution;
1361 /* For each variable j in delta (Sol(y)), add
1362 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1363 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1365 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1366 if (type_safe (j, &roffset))
1369 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1372 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1374 if (int_add_graph_edge (graph, lhs, t, 0))
1375 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1377 else if (dump_file && !(get_varinfo (j)->is_special_var))
1378 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1382 /* If the LHS solution changed, mark the var as changed. */
1385 get_varinfo (lhs)->solution = sol;
1386 if (!TEST_BIT (changed, lhs))
1388 SET_BIT (changed, lhs);
1394 /* Process a constraint C that represents *x = y. */
1397 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1399 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1400 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1401 bitmap sol = get_varinfo (rhs)->solution;
1405 /* For each member j of delta (Sol(x)), add an edge from y to j and
1406 union Sol(y) into Sol(j) */
1407 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1409 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1410 if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var))
1414 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1416 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1418 if (int_add_graph_edge (graph, t, rhs, roff))
1420 bitmap tmp = get_varinfo (t)->solution;
1421 if (set_union_with_increment (tmp, sol, roff))
1423 get_varinfo (t)->solution = tmp;
1426 sol = get_varinfo (rhs)->solution;
1428 if (!TEST_BIT (changed, t))
1430 SET_BIT (changed, t);
1436 else if (dump_file && !(get_varinfo (j)->is_special_var))
1437 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1441 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1442 constraint (IE *x = &y, x = *y, and *x = y). */
1445 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1447 if (c->lhs.type == DEREF)
1449 if (c->rhs.type == ADDRESSOF)
1452 do_da_constraint (graph, c, delta);
1457 do_ds_constraint (graph, c, delta);
1463 if (!(get_varinfo (c->lhs.var)->is_special_var))
1464 do_sd_constraint (graph, c, delta);
1468 /* Initialize and return a new SCC info structure. */
1470 static struct scc_info *
1471 init_scc_info (void)
1473 struct scc_info *si = xmalloc (sizeof (struct scc_info));
1474 size_t size = VEC_length (varinfo_t, varmap);
1476 si->current_index = 0;
1477 si->visited = sbitmap_alloc (size);
1478 sbitmap_zero (si->visited);
1479 si->in_component = sbitmap_alloc (size);
1480 sbitmap_ones (si->in_component);
1481 si->visited_index = xcalloc (sizeof (unsigned int), size + 1);
1482 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1483 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1487 /* Free an SCC info structure pointed to by SI */
1490 free_scc_info (struct scc_info *si)
1492 sbitmap_free (si->visited);
1493 sbitmap_free (si->in_component);
1494 free (si->visited_index);
1495 VEC_free (unsigned, heap, si->scc_stack);
1496 VEC_free (unsigned, heap, si->unification_queue);
1501 /* Find cycles in GRAPH that occur, using strongly connected components, and
1502 collapse the cycles into a single representative node. if UPDATE_CHANGED
1503 is true, then update the changed sbitmap to note those nodes whose
1504 solutions have changed as a result of collapsing. */
1507 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1510 unsigned int size = VEC_length (varinfo_t, varmap);
1511 struct scc_info *si = init_scc_info ();
1513 for (i = 0; i != size; ++i)
1514 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1515 scc_visit (graph, si, i);
1516 process_unification_queue (graph, si, update_changed);
1520 /* Compute a topological ordering for GRAPH, and store the result in the
1521 topo_info structure TI. */
1524 compute_topo_order (constraint_graph_t graph,
1525 struct topo_info *ti)
1528 unsigned int size = VEC_length (varinfo_t, varmap);
1530 for (i = 0; i != size; ++i)
1531 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1532 topo_visit (graph, ti, i);
1535 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1538 bitmap_other_than_zero_bit_set (bitmap b)
1543 if (bitmap_empty_p (b))
1545 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1550 /* Perform offline variable substitution.
1552 This is a linear time way of identifying variables that must have
1553 equivalent points-to sets, including those caused by static cycles,
1554 and single entry subgraphs, in the constraint graph.
1556 The technique is described in "Off-line variable substitution for
1557 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1558 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1561 perform_var_substitution (constraint_graph_t graph)
1563 struct topo_info *ti = init_topo_info ();
1565 /* Compute the topological ordering of the graph, then visit each
1566 node in topological order. */
1567 compute_topo_order (graph, ti);
1569 while (VEC_length (unsigned, ti->topo_order) != 0)
1571 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1573 varinfo_t vi = get_varinfo (i);
1574 bool okay_to_elim = false;
1575 unsigned int root = VEC_length (varinfo_t, varmap);
1576 VEC(constraint_edge_t,heap) *predvec = graph->preds[i];
1577 constraint_edge_t ce;
1580 /* We can't eliminate things whose address is taken, or which is
1581 the target of a dereference. */
1582 if (vi->address_taken || vi->indirect_target)
1585 /* See if all predecessors of I are ripe for elimination */
1586 for (pred = 0; VEC_iterate (constraint_edge_t, predvec, pred, ce); pred++)
1590 weight = get_graph_weights (graph, *ce);
1592 /* We can't eliminate variables that have non-zero weighted
1593 edges between them. */
1594 if (bitmap_other_than_zero_bit_set (weight))
1596 okay_to_elim = false;
1599 w = get_varinfo (ce->dest)->node;
1601 /* We can't eliminate the node if one of the predecessors is
1602 part of a different strongly connected component. */
1606 okay_to_elim = true;
1610 okay_to_elim = false;
1614 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1615 then Solution(i) is a subset of Solution (w), where w is a
1616 predecessor in the graph.
1617 Corollary: If all predecessors of i have the same
1618 points-to set, then i has that same points-to set as
1619 those predecessors. */
1620 tmp = BITMAP_ALLOC (NULL);
1621 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1622 get_varinfo (w)->solution);
1623 if (!bitmap_empty_p (tmp))
1625 okay_to_elim = false;
1632 /* See if the root is different than the original node.
1633 If so, we've found an equivalence. */
1634 if (root != get_varinfo (i)->node && okay_to_elim)
1636 /* Found an equivalence */
1637 get_varinfo (i)->node = root;
1638 collapse_nodes (graph, root, i);
1639 if (dump_file && (dump_flags & TDF_DETAILS))
1640 fprintf (dump_file, "Collapsing %s into %s\n",
1641 get_varinfo (i)->name,
1642 get_varinfo (root)->name);
1643 stats.collapsed_vars++;
1647 free_topo_info (ti);
1651 /* Solve the constraint graph GRAPH using our worklist solver.
1652 This is based on the PW* family of solvers from the "Efficient Field
1653 Sensitive Pointer Analysis for C" paper.
1654 It works by iterating over all the graph nodes, processing the complex
1655 constraints and propagating the copy constraints, until everything stops
1656 changed. This corresponds to steps 6-8 in the solving list given above. */
1659 solve_graph (constraint_graph_t graph)
1661 unsigned int size = VEC_length (varinfo_t, varmap);
1664 changed_count = size;
1665 changed = sbitmap_alloc (size);
1666 sbitmap_ones (changed);
1668 /* The already collapsed/unreachable nodes will never change, so we
1669 need to account for them in changed_count. */
1670 for (i = 0; i < size; i++)
1671 if (get_varinfo (i)->node != i)
1674 while (changed_count > 0)
1677 struct topo_info *ti = init_topo_info ();
1680 bitmap_obstack_initialize (&iteration_obstack);
1684 /* We already did cycle elimination once, when we did
1685 variable substitution, so we don't need it again for the
1687 if (stats.iterations > 1)
1688 find_and_collapse_graph_cycles (graph, true);
1693 compute_topo_order (graph, ti);
1695 while (VEC_length (unsigned, ti->topo_order) != 0)
1697 i = VEC_pop (unsigned, ti->topo_order);
1698 gcc_assert (get_varinfo (i)->node == i);
1700 /* If the node has changed, we need to process the
1701 complex constraints and outgoing edges again. */
1702 if (TEST_BIT (changed, i))
1706 constraint_edge_t e;
1708 VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
1709 VEC(constraint_edge_t,heap) *succs;
1711 RESET_BIT (changed, i);
1714 /* Process the complex constraints */
1715 solution = get_varinfo (i)->solution;
1716 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
1717 do_complex_constraint (graph, c, solution);
1719 /* Propagate solution to all successors. */
1720 succs = graph->succs[i];
1721 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
1723 bitmap tmp = get_varinfo (e->dest)->solution;
1726 bitmap weights = e->weights;
1729 gcc_assert (!bitmap_empty_p (weights));
1730 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
1731 flag |= set_union_with_increment (tmp, solution, k);
1735 get_varinfo (e->dest)->solution = tmp;
1736 if (!TEST_BIT (changed, e->dest))
1738 SET_BIT (changed, e->dest);
1745 free_topo_info (ti);
1746 bitmap_obstack_release (&iteration_obstack);
1749 sbitmap_free (changed);
1753 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1755 /* Map from trees to variable ids. */
1756 static htab_t id_for_tree;
1758 typedef struct tree_id
1764 /* Hash a tree id structure. */
1767 tree_id_hash (const void *p)
1769 const tree_id_t ta = (tree_id_t) p;
1770 return htab_hash_pointer (ta->t);
1773 /* Return true if the tree in P1 and the tree in P2 are the same. */
1776 tree_id_eq (const void *p1, const void *p2)
1778 const tree_id_t ta1 = (tree_id_t) p1;
1779 const tree_id_t ta2 = (tree_id_t) p2;
1780 return ta1->t == ta2->t;
1783 /* Insert ID as the variable id for tree T in the hashtable. */
1786 insert_id_for_tree (tree t, int id)
1789 struct tree_id finder;
1793 slot = htab_find_slot (id_for_tree, &finder, INSERT);
1794 gcc_assert (*slot == NULL);
1795 new_pair = xmalloc (sizeof (struct tree_id));
1798 *slot = (void *)new_pair;
1801 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1802 exist in the hash table, return false, otherwise, return true and
1803 set *ID to the id we found. */
1806 lookup_id_for_tree (tree t, unsigned int *id)
1809 struct tree_id finder;
1812 pair = htab_find (id_for_tree, &finder);
1819 /* Return a printable name for DECL */
1822 alias_get_name (tree decl)
1824 const char *res = get_name (decl);
1826 int num_printed = 0;
1832 if (TREE_CODE (decl) == SSA_NAME)
1834 num_printed = asprintf (&temp, "%s_%u",
1835 alias_get_name (SSA_NAME_VAR (decl)),
1836 SSA_NAME_VERSION (decl));
1838 else if (DECL_P (decl))
1840 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
1842 if (num_printed > 0)
1844 res = ggc_strdup (temp);
1850 /* Find the variable id for tree T in the hashtable.
1851 If T doesn't exist in the hash table, create an entry for it. */
1854 get_id_for_tree (tree t)
1857 struct tree_id finder;
1860 pair = htab_find (id_for_tree, &finder);
1862 return create_variable_info_for (t, alias_get_name (t));
1867 /* Get a constraint expression from an SSA_VAR_P node. */
1869 static struct constraint_expr
1870 get_constraint_exp_from_ssa_var (tree t)
1872 struct constraint_expr cexpr;
1874 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
1876 /* For parameters, get at the points-to set for the actual parm
1878 if (TREE_CODE (t) == SSA_NAME
1879 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
1880 && default_def (SSA_NAME_VAR (t)) == t)
1881 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
1883 cexpr.type = SCALAR;
1885 cexpr.var = get_id_for_tree (t);
1886 /* If we determine the result is "anything", and we know this is readonly,
1887 say it points to readonly memory instead. */
1888 if (cexpr.var == anything_id && TREE_READONLY (t))
1890 cexpr.type = ADDRESSOF;
1891 cexpr.var = readonly_id;
1898 /* Process a completed constraint T, and add it to the constraint
1902 process_constraint (constraint_t t)
1904 struct constraint_expr rhs = t->rhs;
1905 struct constraint_expr lhs = t->lhs;
1907 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
1908 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
1910 /* ANYTHING == ANYTHING is pointless. */
1911 if (lhs.var == anything_id && rhs.var == anything_id)
1914 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1915 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
1920 process_constraint (t);
1922 /* This can happen in our IR with things like n->a = *p */
1923 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
1925 /* Split into tmp = *rhs, *lhs = tmp */
1926 tree rhsdecl = get_varinfo (rhs.var)->decl;
1927 tree pointertype = TREE_TYPE (rhsdecl);
1928 tree pointedtotype = TREE_TYPE (pointertype);
1929 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
1930 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
1932 /* If this is an aggregate of known size, we should have passed
1933 this off to do_structure_copy, and it should have broken it
1935 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
1936 || get_varinfo (rhs.var)->is_unknown_size_var);
1938 process_constraint (new_constraint (tmplhs, rhs));
1939 process_constraint (new_constraint (lhs, tmplhs));
1941 else if (rhs.type == ADDRESSOF)
1944 gcc_assert (rhs.offset == 0);
1946 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
1947 vi->address_taken = true;
1949 VEC_safe_push (constraint_t, heap, constraints, t);
1953 if (lhs.type != DEREF && rhs.type == DEREF)
1954 get_varinfo (lhs.var)->indirect_target = true;
1955 VEC_safe_push (constraint_t, heap, constraints, t);
1960 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1963 static unsigned HOST_WIDE_INT
1964 bitpos_of_field (const tree fdecl)
1967 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
1968 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
1971 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
1972 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
1976 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1977 overlaps with a field at [FIELDPOS, FIELDSIZE] */
1980 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
1981 const unsigned HOST_WIDE_INT fieldsize,
1982 const unsigned HOST_WIDE_INT accesspos,
1983 const unsigned HOST_WIDE_INT accesssize)
1985 if (fieldpos == accesspos && fieldsize == accesssize)
1987 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
1989 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
1995 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1997 static struct constraint_expr
1998 get_constraint_for_component_ref (tree t)
2000 struct constraint_expr result;
2001 HOST_WIDE_INT bitsize;
2002 HOST_WIDE_INT bitpos;
2004 enum machine_mode mode;
2010 result.type = SCALAR;
2013 /* Some people like to do cute things like take the address of
2016 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2017 forzero = TREE_OPERAND (forzero, 0);
2019 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2022 result.var = integer_id;
2023 result.type = SCALAR;
2027 t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode,
2028 &unsignedp, &volatilep, false);
2029 result = get_constraint_for (t);
2031 /* This can also happen due to weird offsetof type macros. */
2032 if (TREE_CODE (t) != ADDR_EXPR && result.type == ADDRESSOF)
2033 result.type = SCALAR;
2035 /* If we know where this goes, then yay. Otherwise, booo. */
2037 if (offset == NULL && bitsize != -1)
2039 result.offset = bitpos;
2043 result.var = anything_id;
2047 if (result.type == SCALAR)
2049 /* In languages like C, you can access one past the end of an
2050 array. You aren't allowed to dereference it, so we can
2051 ignore this constraint. When we handle pointer subtraction,
2052 we may have to do something cute here. */
2054 if (result.offset < get_varinfo (result.var)->fullsize)
2056 /* It's also not true that the constraint will actually start at the
2057 right offset, it may start in some padding. We only care about
2058 setting the constraint to the first actual field it touches, so
2061 for (curr = get_varinfo (result.var); curr; curr = curr->next)
2063 if (offset_overlaps_with_access (curr->offset, curr->size,
2064 result.offset, bitsize))
2066 result.var = curr->id;
2071 /* assert that we found *some* field there. The user couldn't be
2072 accessing *only* padding. */
2077 if (dump_file && (dump_flags & TDF_DETAILS))
2078 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2087 /* Dereference the constraint expression CONS, and return the result.
2088 DEREF (ADDRESSOF) = SCALAR
2089 DEREF (SCALAR) = DEREF
2090 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2091 This is needed so that we can handle dereferencing DEREF constraints. */
2093 static struct constraint_expr
2094 do_deref (struct constraint_expr cons)
2096 if (cons.type == SCALAR)
2101 else if (cons.type == ADDRESSOF)
2106 else if (cons.type == DEREF)
2108 tree tmpvar = create_tmp_var_raw (ptr_type_node, "derefmp");
2109 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2110 process_constraint (new_constraint (tmplhs, cons));
2111 cons.var = tmplhs.var;
2118 /* Given a tree T, return the constraint expression for it. */
2120 static struct constraint_expr
2121 get_constraint_for (tree t)
2123 struct constraint_expr temp;
2125 /* x = integer is all glommed to a single variable, which doesn't
2126 point to anything by itself. That is, of course, unless it is an
2127 integer constant being treated as a pointer, in which case, we
2128 will return that this is really the addressof anything. This
2129 happens below, since it will fall into the default case. The only
2130 case we know something about an integer treated like a pointer is
2131 when it is the NULL pointer, and then we just say it points to
2133 if (TREE_CODE (t) == INTEGER_CST
2134 && !POINTER_TYPE_P (TREE_TYPE (t)))
2136 temp.var = integer_id;
2141 else if (TREE_CODE (t) == INTEGER_CST
2142 && integer_zerop (t))
2144 temp.var = nothing_id;
2145 temp.type = ADDRESSOF;
2150 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2152 case tcc_expression:
2154 switch (TREE_CODE (t))
2158 temp = get_constraint_for (TREE_OPERAND (t, 0));
2159 if (temp.type == DEREF)
2162 temp.type = ADDRESSOF;
2168 /* XXX: In interprocedural mode, if we didn't have the
2169 body, we would need to do *each pointer argument =
2171 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2176 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2177 DECL_EXTERNAL (heapvar) = 1;
2178 add_referenced_tmp_var (heapvar);
2179 temp.var = create_variable_info_for (heapvar,
2180 alias_get_name (heapvar));
2182 vi = get_varinfo (temp.var);
2183 vi->is_artificial_var = 1;
2184 vi->is_heap_var = 1;
2185 temp.type = ADDRESSOF;
2192 temp.type = ADDRESSOF;
2193 temp.var = anything_id;
2201 switch (TREE_CODE (t))
2205 temp = get_constraint_for (TREE_OPERAND (t, 0));
2206 temp = do_deref (temp);
2211 temp = get_constraint_for_component_ref (t);
2215 temp.type = ADDRESSOF;
2216 temp.var = anything_id;
2224 switch (TREE_CODE (t))
2228 case NON_LVALUE_EXPR:
2230 tree op = TREE_OPERAND (t, 0);
2232 /* Cast from non-pointer to pointers are bad news for us.
2233 Anything else, we see through */
2234 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2235 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2236 return get_constraint_for (op);
2242 temp.type = ADDRESSOF;
2243 temp.var = anything_id;
2249 case tcc_exceptional:
2251 switch (TREE_CODE (t))
2254 return get_constraint_for (PHI_RESULT (t));
2256 return get_constraint_exp_from_ssa_var (t);
2259 temp.type = ADDRESSOF;
2260 temp.var = anything_id;
2266 case tcc_declaration:
2267 return get_constraint_exp_from_ssa_var (t);
2270 temp.type = ADDRESSOF;
2271 temp.var = anything_id;
2279 /* Handle the structure copy case where we have a simple structure copy
2280 between LHS and RHS that is of SIZE (in bits)
2282 For each field of the lhs variable (lhsfield)
2283 For each field of the rhs variable at lhsfield.offset (rhsfield)
2284 add the constraint lhsfield = rhsfield
2288 do_simple_structure_copy (const struct constraint_expr lhs,
2289 const struct constraint_expr rhs,
2290 const unsigned HOST_WIDE_INT size)
2292 varinfo_t p = get_varinfo (lhs.var);
2293 unsigned HOST_WIDE_INT pstart, last;
2295 last = p->offset + size;
2296 for (; p && p->offset < last; p = p->next)
2299 struct constraint_expr templhs = lhs;
2300 struct constraint_expr temprhs = rhs;
2301 unsigned HOST_WIDE_INT fieldoffset;
2303 templhs.var = p->id;
2304 q = get_varinfo (temprhs.var);
2305 fieldoffset = p->offset - pstart;
2306 q = first_vi_for_offset (q, q->offset + fieldoffset);
2307 temprhs.var = q->id;
2308 process_constraint (new_constraint (templhs, temprhs));
2313 /* Handle the structure copy case where we have a structure copy between a
2314 aggregate on the LHS and a dereference of a pointer on the RHS
2315 that is of SIZE (in bits)
2317 For each field of the lhs variable (lhsfield)
2318 rhs.offset = lhsfield->offset
2319 add the constraint lhsfield = rhs
2323 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2324 const struct constraint_expr rhs,
2325 const unsigned HOST_WIDE_INT size)
2327 varinfo_t p = get_varinfo (lhs.var);
2328 unsigned HOST_WIDE_INT pstart,last;
2330 last = p->offset + size;
2332 for (; p && p->offset < last; p = p->next)
2335 struct constraint_expr templhs = lhs;
2336 struct constraint_expr temprhs = rhs;
2337 unsigned HOST_WIDE_INT fieldoffset;
2340 if (templhs.type == SCALAR)
2341 templhs.var = p->id;
2343 templhs.offset = p->offset;
2345 q = get_varinfo (temprhs.var);
2346 fieldoffset = p->offset - pstart;
2347 temprhs.offset += fieldoffset;
2348 process_constraint (new_constraint (templhs, temprhs));
2352 /* Handle the structure copy case where we have a structure copy
2353 between a aggregate on the RHS and a dereference of a pointer on
2354 the LHS that is of SIZE (in bits)
2356 For each field of the rhs variable (rhsfield)
2357 lhs.offset = rhsfield->offset
2358 add the constraint lhs = rhsfield
2362 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2363 const struct constraint_expr rhs,
2364 const unsigned HOST_WIDE_INT size)
2366 varinfo_t p = get_varinfo (rhs.var);
2367 unsigned HOST_WIDE_INT pstart,last;
2369 last = p->offset + size;
2371 for (; p && p->offset < last; p = p->next)
2374 struct constraint_expr templhs = lhs;
2375 struct constraint_expr temprhs = rhs;
2376 unsigned HOST_WIDE_INT fieldoffset;
2379 if (temprhs.type == SCALAR)
2380 temprhs.var = p->id;
2382 temprhs.offset = p->offset;
2384 q = get_varinfo (templhs.var);
2385 fieldoffset = p->offset - pstart;
2386 templhs.offset += fieldoffset;
2387 process_constraint (new_constraint (templhs, temprhs));
2392 /* Handle aggregate copies by expanding into copies of the respective
2393 fields of the structures. */
2396 do_structure_copy (tree lhsop, tree rhsop)
2398 struct constraint_expr lhs, rhs, tmp;
2400 unsigned HOST_WIDE_INT lhssize;
2401 unsigned HOST_WIDE_INT rhssize;
2403 lhs = get_constraint_for (lhsop);
2404 rhs = get_constraint_for (rhsop);
2406 /* If we have special var = x, swap it around. */
2407 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2414 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2415 possible it's something we could handle. However, most cases falling
2416 into this are dealing with transparent unions, which are slightly
2418 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2420 rhs.type = ADDRESSOF;
2421 rhs.var = anything_id;
2424 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2425 that special var. */
2426 if (rhs.var <= integer_id)
2428 for (p = get_varinfo (lhs.var); p; p = p->next)
2430 struct constraint_expr templhs = lhs;
2431 struct constraint_expr temprhs = rhs;
2432 if (templhs.type == SCALAR )
2433 templhs.var = p->id;
2435 templhs.offset += p->offset;
2436 process_constraint (new_constraint (templhs, temprhs));
2441 tree rhstype = TREE_TYPE (rhsop);
2442 tree lhstype = TREE_TYPE (lhsop);
2443 tree rhstypesize = TYPE_SIZE (rhstype);
2444 tree lhstypesize = TYPE_SIZE (lhstype);
2446 /* If we have a variably sized types on the rhs or lhs, and a deref
2447 constraint, add the constraint, lhsconstraint = &ANYTHING.
2448 This is conservatively correct because either the lhs is an unknown
2449 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2450 constraint, and every variable it can point to must be unknown sized
2451 anyway, so we don't need to worry about fields at all. */
2452 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2453 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2455 rhs.var = anything_id;
2456 rhs.type = ADDRESSOF;
2458 process_constraint (new_constraint (lhs, rhs));
2462 /* The size only really matters insofar as we don't set more or less of
2463 the variable. If we hit an unknown size var, the size should be the
2464 whole darn thing. */
2465 if (get_varinfo (rhs.var)->is_unknown_size_var)
2468 rhssize = TREE_INT_CST_LOW (rhstypesize);
2470 if (get_varinfo (lhs.var)->is_unknown_size_var)
2473 lhssize = TREE_INT_CST_LOW (lhstypesize);
2476 if (rhs.type == SCALAR && lhs.type == SCALAR)
2477 do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2478 else if (lhs.type != DEREF && rhs.type == DEREF)
2479 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2480 else if (lhs.type == DEREF && rhs.type != DEREF)
2481 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2484 tree pointedtotype = lhstype;
2487 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2488 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2489 do_structure_copy (tmpvar, rhsop);
2490 do_structure_copy (lhsop, tmpvar);
2496 /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere
2500 ref_contains_indirect_ref (tree ref)
2502 while (handled_component_p (ref))
2504 if (TREE_CODE (ref) == INDIRECT_REF)
2506 ref = TREE_OPERAND (ref, 0);
2512 /* Update related alias information kept in AI. This is used when
2513 building name tags, alias sets and deciding grouping heuristics.
2514 STMT is the statement to process. This function also updates
2515 ADDRESSABLE_VARS. */
2518 update_alias_info (tree stmt, struct alias_info *ai)
2521 use_operand_p use_p;
2523 bool stmt_escapes_p = is_escape_site (stmt, ai);
2526 /* Mark all the variables whose address are taken by the statement. */
2527 addr_taken = addresses_taken (stmt);
2530 bitmap_ior_into (addressable_vars, addr_taken);
2532 /* If STMT is an escape point, all the addresses taken by it are
2539 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
2540 mark_call_clobbered (referenced_var (i));
2544 /* Process each operand use. If an operand may be aliased, keep
2545 track of how many times it's being used. For pointers, determine
2546 whether they are dereferenced by the statement, or whether their
2547 value escapes, etc. */
2548 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2552 struct ptr_info_def *pi;
2554 unsigned num_uses, num_derefs;
2556 op = USE_FROM_PTR (use_p);
2558 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2559 to the set of addressable variables. */
2560 if (TREE_CODE (op) == ADDR_EXPR)
2562 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
2564 /* PHI nodes don't have annotations for pinning the set
2565 of addresses taken, so we collect them here.
2567 FIXME, should we allow PHI nodes to have annotations
2568 so that they can be treated like regular statements?
2569 Currently, they are treated as second-class
2571 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
2575 /* Ignore constants. */
2576 if (TREE_CODE (op) != SSA_NAME)
2579 var = SSA_NAME_VAR (op);
2580 v_ann = var_ann (var);
2582 /* If the operand's variable may be aliased, keep track of how
2583 many times we've referenced it. This is used for alias
2584 grouping in compute_flow_insensitive_aliasing. */
2585 if (may_be_aliased (var))
2586 NUM_REFERENCES_INC (v_ann);
2588 /* We are only interested in pointers. */
2589 if (!POINTER_TYPE_P (TREE_TYPE (op)))
2592 pi = get_ptr_info (op);
2594 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
2595 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
2597 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
2598 VARRAY_PUSH_TREE (ai->processed_ptrs, op);
2601 /* If STMT is a PHI node, then it will not have pointer
2602 dereferences and it will not be an escape point. */
2603 if (TREE_CODE (stmt) == PHI_NODE)
2606 /* Determine whether OP is a dereferenced pointer, and if STMT
2607 is an escape point, whether OP escapes. */
2608 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
2612 /* Mark OP as dereferenced. In a subsequent pass,
2613 dereferenced pointers that point to a set of
2614 variables will be assigned a name tag to alias
2615 all the variables OP points to. */
2616 pi->is_dereferenced = 1;
2618 /* Keep track of how many time we've dereferenced each
2620 NUM_REFERENCES_INC (v_ann);
2622 /* If this is a store operation, mark OP as being
2623 dereferenced to store, otherwise mark it as being
2624 dereferenced to load. */
2626 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
2628 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
2631 if (stmt_escapes_p && num_derefs < num_uses)
2633 /* If STMT is an escape point and STMT contains at
2634 least one direct use of OP, then the value of OP
2635 escapes and so the pointed-to variables need to
2636 be marked call-clobbered. */
2637 pi->value_escapes_p = 1;
2639 /* If the statement makes a function call, assume
2640 that pointer OP will be dereferenced in a store
2641 operation inside the called function. */
2642 if (get_call_expr_in (stmt))
2644 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
2645 pi->is_dereferenced = 1;
2650 if (TREE_CODE (stmt) == PHI_NODE)
2653 /* Update reference counter for definitions to any
2654 potentially aliased variable. This is used in the alias
2655 grouping heuristics. */
2656 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
2658 tree var = SSA_NAME_VAR (op);
2659 var_ann_t ann = var_ann (var);
2660 bitmap_set_bit (ai->written_vars, DECL_UID (var));
2661 if (may_be_aliased (var))
2662 NUM_REFERENCES_INC (ann);
2666 /* Mark variables in V_MAY_DEF operands as being written to. */
2667 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
2669 tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
2670 bitmap_set_bit (ai->written_vars, DECL_UID (var));
2675 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
2676 Expressions of the type PTR + CST can be handled in two ways:
2678 1- If the constraint for PTR is ADDRESSOF for a non-structure
2679 variable, then we can use it directly because adding or
2680 subtracting a constant may not alter the original ADDRESSOF
2681 constraing (i.e., pointer arithmetic may not legally go outside
2682 an object's boundaries).
2684 2- If the constraint for PTR is ADDRESSOF for a structure variable,
2685 then if CST is a compile-time constant that can be used as an
2686 offset, we can determine which sub-variable will be pointed-to
2689 Return true if the expression is handled. For any other kind of
2690 expression, return false so that each operand can be added as a
2691 separate constraint by the caller. */
2694 handle_ptr_arith (struct constraint_expr lhs, tree expr)
2697 struct constraint_expr base, offset;
2699 if (TREE_CODE (expr) != PLUS_EXPR)
2702 op0 = TREE_OPERAND (expr, 0);
2703 op1 = TREE_OPERAND (expr, 1);
2705 base = get_constraint_for (op0);
2707 offset.var = anyoffset_id;
2708 offset.type = ADDRESSOF;
2711 process_constraint (new_constraint (lhs, base));
2712 process_constraint (new_constraint (lhs, offset));
2718 /* Walk statement T setting up aliasing constraints according to the
2719 references found in T. This function is the main part of the
2720 constraint builder. AI points to auxiliary alias information used
2721 when building alias sets and computing alias grouping heuristics. */
2724 find_func_aliases (tree t, struct alias_info *ai)
2726 struct constraint_expr lhs, rhs;
2728 /* Update various related attributes like escaped addresses, pointer
2729 dereferences for loads and stores. This is used when creating
2730 name tags and alias sets. */
2731 update_alias_info (t, ai);
2733 /* Now build constraints expressions. */
2734 if (TREE_CODE (t) == PHI_NODE)
2736 /* Only care about pointers and structures containing
2738 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
2739 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
2743 lhs = get_constraint_for (PHI_RESULT (t));
2744 for (i = 0; i < PHI_NUM_ARGS (t); i++)
2746 rhs = get_constraint_for (PHI_ARG_DEF (t, i));
2747 process_constraint (new_constraint (lhs, rhs));
2751 else if (TREE_CODE (t) == MODIFY_EXPR)
2753 tree lhsop = TREE_OPERAND (t, 0);
2754 tree rhsop = TREE_OPERAND (t, 1);
2757 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2758 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
2760 do_structure_copy (lhsop, rhsop);
2764 /* Only care about operations with pointers, structures
2765 containing pointers, dereferences, and call expressions. */
2766 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
2767 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2768 || ref_contains_indirect_ref (lhsop)
2769 || TREE_CODE (rhsop) == CALL_EXPR)
2771 lhs = get_constraint_for (lhsop);
2772 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
2774 /* RHS that consist of unary operations,
2775 exceptional types, or bare decls/constants, get
2776 handled directly by get_constraint_for. */
2778 case tcc_declaration:
2780 case tcc_exceptional:
2781 case tcc_expression:
2784 rhs = get_constraint_for (rhsop);
2785 process_constraint (new_constraint (lhs, rhs));
2787 /* When taking the address of an aggregate
2788 type, from the LHS we can access any field
2790 if (rhs.type == ADDRESSOF
2791 && !(get_varinfo (rhs.var)->is_special_var)
2792 && AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (rhsop))))
2794 rhs.var = anyoffset_id;
2795 rhs.type = ADDRESSOF;
2797 process_constraint (new_constraint (lhs, rhs));
2804 /* For pointer arithmetic of the form
2805 PTR + CST, we can simply use PTR's
2806 constraint because pointer arithmetic is
2807 not allowed to go out of bounds. */
2808 if (handle_ptr_arith (lhs, rhsop))
2813 /* Otherwise, walk each operand. Notice that we
2814 can't use the operand interface because we need
2815 to process expressions other than simple operands
2816 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
2818 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
2820 tree op = TREE_OPERAND (rhsop, i);
2821 rhs = get_constraint_for (op);
2822 process_constraint (new_constraint (lhs, rhs));
2829 /* After promoting variables and computing aliasing we will
2830 need to re-scan most statements. FIXME: Try to minimize the
2831 number of statements re-scanned. It's not really necessary to
2832 re-scan *all* statements. */
2833 mark_stmt_modified (t);
2837 /* Find the first varinfo in the same variable as START that overlaps with
2839 Effectively, walk the chain of fields for the variable START to find the
2840 first field that overlaps with OFFSET.
2841 Abort if we can't find one. */
2844 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
2846 varinfo_t curr = start;
2849 /* We may not find a variable in the field list with the actual
2850 offset when when we have glommed a structure to a variable.
2851 In that case, however, offset should still be within the size
2853 if (offset >= curr->offset && offset < (curr->offset + curr->size))
2862 /* Insert the varinfo FIELD into the field list for BASE, ordered by
2866 insert_into_field_list (varinfo_t base, varinfo_t field)
2868 varinfo_t prev = base;
2869 varinfo_t curr = base->next;
2880 if (field->offset <= curr->offset)
2885 field->next = prev->next;
2890 /* qsort comparison function for two fieldoff's PA and PB */
2893 fieldoff_compare (const void *pa, const void *pb)
2895 const fieldoff_s *foa = (const fieldoff_s *)pa;
2896 const fieldoff_s *fob = (const fieldoff_s *)pb;
2897 HOST_WIDE_INT foasize, fobsize;
2899 if (foa->offset != fob->offset)
2900 return foa->offset - fob->offset;
2902 foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
2903 fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
2904 return foasize - fobsize;
2907 /* Sort a fieldstack according to the field offset and sizes. */
2908 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
2910 qsort (VEC_address (fieldoff_s, fieldstack),
2911 VEC_length (fieldoff_s, fieldstack),
2912 sizeof (fieldoff_s),
2916 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
2917 of TYPE onto fieldstack, recording their offsets along the way.
2918 OFFSET is used to keep track of the offset in this entire structure, rather
2919 than just the immediately containing structure. Returns the number
2921 HAS_UNION is set to true if we find a union type as a field of
2925 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
2926 HOST_WIDE_INT offset, bool *has_union)
2931 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2932 if (TREE_CODE (field) == FIELD_DECL)
2937 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
2938 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
2941 if (!var_can_have_subvars (field))
2943 else if (!(push_fields_onto_fieldstack
2944 (TREE_TYPE (field), fieldstack,
2945 offset + bitpos_of_field (field), has_union))
2946 && DECL_SIZE (field)
2947 && !integer_zerop (DECL_SIZE (field)))
2948 /* Empty structures may have actual size, like in C++. So
2949 see if we didn't push any subfields and the size is
2950 nonzero, push the field onto the stack */
2957 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
2958 pair->field = field;
2959 pair->offset = offset + bitpos_of_field (field);
2968 make_constraint_to_anything (varinfo_t vi)
2970 struct constraint_expr lhs, rhs;
2976 rhs.var = anything_id;
2978 rhs.type = ADDRESSOF;
2979 process_constraint (new_constraint (lhs, rhs));
2982 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
2983 This will also create any varinfo structures necessary for fields
2987 create_variable_info_for (tree decl, const char *name)
2989 unsigned int index = VEC_length (varinfo_t, varmap);
2991 tree decltype = TREE_TYPE (decl);
2992 bool notokay = false;
2994 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
2995 VEC (fieldoff_s,heap) *fieldstack = NULL;
2998 hasunion = TREE_CODE (decltype) == UNION_TYPE
2999 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
3000 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
3002 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
3005 VEC_free (fieldoff_s, heap, fieldstack);
3011 /* If the variable doesn't have subvars, we may end up needing to
3012 sort the field list and create fake variables for all the
3014 vi = new_var_info (decl, index, name, index);
3017 vi->has_union = hasunion;
3018 if (!TYPE_SIZE (decltype)
3019 || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
3020 || TREE_CODE (decltype) == ARRAY_TYPE
3021 || TREE_CODE (decltype) == UNION_TYPE
3022 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
3024 vi->is_unknown_size_var = true;
3030 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
3031 vi->size = vi->fullsize;
3034 insert_id_for_tree (vi->decl, index);
3035 VEC_safe_push (varinfo_t, heap, varmap, vi);
3037 make_constraint_to_anything (vi);
3040 if (use_field_sensitive
3042 && !vi->is_unknown_size_var
3043 && var_can_have_subvars (decl))
3045 unsigned int newindex = VEC_length (varinfo_t, varmap);
3046 fieldoff_s *fo = NULL;
3050 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3052 if (!DECL_SIZE (fo->field)
3053 || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
3054 || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE
3062 /* We can't sort them if we have a field with a variable sized type,
3063 which will make notokay = true. In that case, we are going to return
3064 without creating varinfos for the fields anyway, so sorting them is a
3067 sort_fieldstack (fieldstack);
3069 if (VEC_length (fieldoff_s, fieldstack) != 0)
3070 fo = VEC_index (fieldoff_s, fieldstack, 0);
3072 if (fo == NULL || notokay)
3074 vi->is_unknown_size_var = 1;
3077 VEC_free (fieldoff_s, heap, fieldstack);
3082 vi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
3083 vi->offset = fo->offset;
3084 for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3087 const char *newname;
3091 newindex = VEC_length (varinfo_t, varmap);
3092 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (field));
3093 newname = ggc_strdup (tempname);
3095 newvi = new_var_info (decl, newindex, newname, newindex);
3096 newvi->offset = fo->offset;
3097 newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
3098 newvi->fullsize = vi->fullsize;
3099 insert_into_field_list (vi, newvi);
3100 VEC_safe_push (varinfo_t, heap, varmap, newvi);
3102 make_constraint_to_anything (newvi);
3106 VEC_free (fieldoff_s, heap, fieldstack);
3111 /* Print out the points-to solution for VAR to FILE. */
3114 dump_solution_for_var (FILE *file, unsigned int var)
3116 varinfo_t vi = get_varinfo (var);
3120 fprintf (file, "%s = { ", vi->name);
3121 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
3123 fprintf (file, "%s ", get_varinfo (i)->name);
3125 fprintf (file, "}\n");
3128 /* Print the points-to solution for VAR to stdout. */
3131 debug_solution_for_var (unsigned int var)
3133 dump_solution_for_var (stdout, var);
3137 /* Create varinfo structures for all of the variables in the
3138 function for intraprocedural mode. */
3141 intra_create_variable_infos (void)
3145 /* For each incoming argument arg, ARG = &ANYTHING */
3146 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
3148 struct constraint_expr lhs;
3149 struct constraint_expr rhs;
3154 lhs.var = create_variable_info_for (t, alias_get_name (t));
3156 rhs.var = anything_id;
3157 rhs.type = ADDRESSOF;
3160 for (p = get_varinfo (lhs.var); p; p = p->next)
3162 struct constraint_expr temp = lhs;
3164 process_constraint (new_constraint (temp, rhs));
3170 /* Set bits in INTO corresponding to the variable uids in solution set
3174 set_uids_in_ptset (bitmap into, bitmap from)
3178 bool found_anyoffset = false;
3181 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
3183 varinfo_t vi = get_varinfo (i);
3185 /* If we find ANYOFFSET in the solution and the solution
3186 includes SFTs for some structure, then all the SFTs in that
3187 structure will need to be added to the alias set. */
3188 if (vi->id == anyoffset_id)
3190 found_anyoffset = true;
3194 /* The only artificial variables that are allowed in a may-alias
3195 set are heap variables. */
3196 if (vi->is_artificial_var && !vi->is_heap_var)
3199 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
3201 /* Variables containing unions may need to be converted to
3202 their SFT's, because SFT's can have unions and we cannot. */
3203 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
3204 bitmap_set_bit (into, DECL_UID (sv->var));
3206 else if (TREE_CODE (vi->decl) == VAR_DECL
3207 || TREE_CODE (vi->decl) == PARM_DECL)
3210 && var_can_have_subvars (vi->decl)
3211 && get_subvars_for_var (vi->decl))
3213 /* If ANYOFFSET is in the solution set and VI->DECL is
3214 an aggregate variable with sub-variables, then any of
3215 the SFTs inside VI->DECL may have been accessed. Add
3216 all the sub-vars for VI->DECL. */
3217 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
3218 bitmap_set_bit (into, DECL_UID (sv->var));
3220 else if (var_can_have_subvars (vi->decl)
3221 && get_subvars_for_var (vi->decl))
3223 /* If VI->DECL is an aggregate for which we created
3224 SFTs, add the SFT corresponding to VI->OFFSET. */
3225 tree sft = get_subvar_at (vi->decl, vi->offset);
3226 bitmap_set_bit (into, DECL_UID (sft));
3230 /* Otherwise, just add VI->DECL to the alias set. */
3231 bitmap_set_bit (into, DECL_UID (vi->decl));
3238 static bool have_alias_info = false;
3240 /* Given a pointer variable P, fill in its points-to set, or return
3241 false if we can't. */
3244 find_what_p_points_to (tree p)
3246 unsigned int id = 0;
3248 if (!have_alias_info)
3251 if (lookup_id_for_tree (p, &id))
3253 varinfo_t vi = get_varinfo (id);
3255 if (vi->is_artificial_var)
3258 /* See if this is a field or a structure. */
3259 if (vi->size != vi->fullsize)
3261 /* Nothing currently asks about structure fields directly,
3262 but when they do, we need code here to hand back the
3264 if (!var_can_have_subvars (vi->decl)
3265 || get_subvars_for_var (vi->decl) == NULL)
3270 struct ptr_info_def *pi = get_ptr_info (p);
3274 /* This variable may have been collapsed, let's get the real
3276 vi = get_varinfo (vi->node);
3278 /* Translate artificial variables into SSA_NAME_PTR_INFO
3280 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
3282 varinfo_t vi = get_varinfo (i);
3284 if (vi->is_artificial_var)
3286 /* FIXME. READONLY should be handled better so that
3287 flow insensitive aliasing can disregard writeable
3289 if (vi->id == nothing_id)
3291 else if (vi->id == anything_id)
3292 pi->pt_anything = 1;
3293 else if (vi->id == readonly_id)
3294 pi->pt_anything = 1;
3295 else if (vi->id == integer_id)
3296 pi->pt_anything = 1;
3297 else if (vi->is_heap_var)
3298 pi->pt_global_mem = 1;
3302 if (pi->pt_anything)
3306 pi->pt_vars = BITMAP_GGC_ALLOC ();
3308 set_uids_in_ptset (pi->pt_vars, vi->solution);
3310 if (bitmap_empty_p (pi->pt_vars))
3321 /* Initialize things necessary to perform PTA */
3324 init_alias_vars (void)
3326 bitmap_obstack_initialize (&ptabitmap_obstack);
3330 /* Dump points-to information to OUTFILE. */
3333 dump_sa_points_to_info (FILE *outfile)
3337 fprintf (outfile, "\nPoints-to sets\n\n");
3339 if (dump_flags & TDF_STATS)
3341 fprintf (outfile, "Stats:\n");
3342 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
3343 fprintf (outfile, "Statically unified vars: %d\n",
3344 stats.unified_vars_static);
3345 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
3346 fprintf (outfile, "Dynamically unified vars: %d\n",
3347 stats.unified_vars_dynamic);
3348 fprintf (outfile, "Iterations: %d\n", stats.iterations);
3351 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
3352 dump_solution_for_var (outfile, i);
3356 /* Debug points-to information to stderr. */
3359 debug_sa_points_to_info (void)
3361 dump_sa_points_to_info (stderr);
3365 /* Initialize the always-existing constraint variables for NULL
3366 ANYTHING, READONLY, and INTEGER */
3369 init_base_vars (void)
3371 struct constraint_expr lhs, rhs;
3373 /* Create the NULL variable, used to represent that a variable points
3375 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
3376 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
3377 insert_id_for_tree (nothing_tree, 0);
3378 var_nothing->is_artificial_var = 1;
3379 var_nothing->offset = 0;
3380 var_nothing->size = ~0;
3381 var_nothing->fullsize = ~0;
3382 var_nothing->is_special_var = 1;
3384 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
3386 /* Create the ANYTHING variable, used to represent that a variable
3387 points to some unknown piece of memory. */
3388 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
3389 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
3390 insert_id_for_tree (anything_tree, 1);
3391 var_anything->is_artificial_var = 1;
3392 var_anything->size = ~0;
3393 var_anything->offset = 0;
3394 var_anything->next = NULL;
3395 var_anything->fullsize = ~0;
3396 var_anything->is_special_var = 1;
3399 /* Anything points to anything. This makes deref constraints just
3400 work in the presence of linked list and other p = *p type loops,
3401 by saying that *ANYTHING = ANYTHING. */
3402 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
3404 lhs.var = anything_id;
3406 rhs.type = ADDRESSOF;
3407 rhs.var = anything_id;
3409 var_anything->address_taken = true;
3411 /* This specifically does not use process_constraint because
3412 process_constraint ignores all anything = anything constraints, since all
3413 but this one are redundant. */
3414 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
3416 /* Create the READONLY variable, used to represent that a variable
3417 points to readonly memory. */
3418 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
3419 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
3420 var_readonly->is_artificial_var = 1;
3421 var_readonly->offset = 0;
3422 var_readonly->size = ~0;
3423 var_readonly->fullsize = ~0;
3424 var_readonly->next = NULL;
3425 var_readonly->is_special_var = 1;
3426 insert_id_for_tree (readonly_tree, 2);
3428 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
3430 /* readonly memory points to anything, in order to make deref
3431 easier. In reality, it points to anything the particular
3432 readonly variable can point to, but we don't track this
3435 lhs.var = readonly_id;
3437 rhs.type = ADDRESSOF;
3438 rhs.var = anything_id;
3441 process_constraint (new_constraint (lhs, rhs));
3443 /* Create the INTEGER variable, used to represent that a variable points
3445 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
3446 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
3447 insert_id_for_tree (integer_tree, 3);
3448 var_integer->is_artificial_var = 1;
3449 var_integer->size = ~0;
3450 var_integer->fullsize = ~0;
3451 var_integer->offset = 0;
3452 var_integer->next = NULL;
3453 var_integer->is_special_var = 1;
3455 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
3457 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
3458 integer will point to. */
3460 lhs.var = integer_id;
3462 rhs.type = ADDRESSOF;
3463 rhs.var = anything_id;
3465 process_constraint (new_constraint (lhs, rhs));
3467 /* Create the ANYOFFSET variable, used to represent an arbitrary offset
3468 inside an object. This is similar to ANYTHING, but less drastic.
3469 It means that the pointer can point anywhere inside an object,
3470 but not outside of it. */
3471 anyoffset_tree = create_tmp_var_raw (void_type_node, "ANYOFFSET");
3473 var_anyoffset = new_var_info (anyoffset_tree, anyoffset_id, "ANYOFFSET",
3475 insert_id_for_tree (anyoffset_tree, anyoffset_id);
3476 var_anyoffset->is_artificial_var = 1;
3477 var_anyoffset->size = ~0;
3478 var_anyoffset->offset = 0;
3479 var_anyoffset->next = NULL;
3480 var_anyoffset->fullsize = ~0;
3481 var_anyoffset->is_special_var = 1;
3482 VEC_safe_push (varinfo_t, heap, varmap, var_anyoffset);
3484 /* ANYOFFSET points to ANYOFFSET. */
3486 lhs.var = anyoffset_id;
3488 rhs.type = ADDRESSOF;
3489 rhs.var = anyoffset_id;
3491 process_constraint (new_constraint (lhs, rhs));
3494 /* Return true if we actually need to solve the constraint graph in order to
3495 get our points-to sets. This is false when, for example, no addresses are
3496 taken other than special vars, or all points-to sets with members already
3497 contain the anything variable. */
3500 need_to_solve (void)
3504 bool found_address_taken = false;
3505 bool found_non_anything = false;
3507 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
3509 if (v->is_special_var)
3512 if (v->address_taken)
3513 found_address_taken = true;
3516 && !bitmap_empty_p (v->solution)
3517 && !bitmap_bit_p (v->solution, anything_id))
3518 found_non_anything = true;
3520 if (found_address_taken && found_non_anything)
3527 /* Create points-to sets for the current function. See the comments
3528 at the start of the file for an algorithmic overview. */
3531 compute_points_to_sets (struct alias_info *ai)
3535 timevar_push (TV_TREE_PTA);
3539 constraint_pool = create_alloc_pool ("Constraint pool",
3540 sizeof (struct constraint), 30);
3541 variable_info_pool = create_alloc_pool ("Variable info pool",
3542 sizeof (struct variable_info), 30);
3543 constraint_edge_pool = create_alloc_pool ("Constraint edges",
3544 sizeof (struct constraint_edge), 30);
3546 constraints = VEC_alloc (constraint_t, heap, 8);
3547 varmap = VEC_alloc (varinfo_t, heap, 8);
3548 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
3549 memset (&stats, 0, sizeof (stats));
3553 intra_create_variable_infos ();
3555 /* Now walk all statements and derive aliases. */
3558 block_stmt_iterator bsi;
3561 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3562 if (is_gimple_reg (PHI_RESULT (phi)))
3563 find_func_aliases (phi, ai);
3565 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3566 find_func_aliases (bsi_stmt (bsi), ai);
3569 build_constraint_graph ();
3573 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
3574 dump_constraints (dump_file);
3577 if (need_to_solve ())
3580 fprintf (dump_file, "\nCollapsing static cycles and doing variable "
3583 find_and_collapse_graph_cycles (graph, false);
3584 perform_var_substitution (graph);
3587 fprintf (dump_file, "\nSolving graph:\n");
3589 solve_graph (graph);
3593 dump_sa_points_to_info (dump_file);
3595 have_alias_info = true;
3597 timevar_pop (TV_TREE_PTA);
3601 /* Delete created points-to sets. */
3604 delete_points_to_sets (void)
3609 htab_delete (id_for_tree);
3610 bitmap_obstack_release (&ptabitmap_obstack);
3611 VEC_free (constraint_t, heap, constraints);
3613 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
3615 VEC_free (constraint_edge_t, heap, graph->succs[i]);
3616 VEC_free (constraint_edge_t, heap, graph->preds[i]);
3617 VEC_free (constraint_t, heap, v->complex);
3619 free (graph->succs);
3620 free (graph->preds);
3623 VEC_free (varinfo_t, heap, varmap);
3624 free_alloc_pool (variable_info_pool);
3625 free_alloc_pool (constraint_pool);
3626 free_alloc_pool (constraint_edge_pool);
3628 have_alias_info = false;