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, bool *);
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);
617 bitmap_set_bit (result, v->id);
619 else if (get_varinfo (i)->is_artificial_var
620 || get_varinfo (i)->has_union
621 || get_varinfo (i)->is_unknown_size_var)
623 bitmap_set_bit (result, i);
627 bitmap_copy (set, result);
628 BITMAP_FREE (result);
631 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
635 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
638 return bitmap_ior_into (to, from);
644 tmp = BITMAP_ALLOC (&iteration_obstack);
645 bitmap_copy (tmp, from);
646 solution_set_add (tmp, inc);
647 res = bitmap_ior_into (to, tmp);
653 /* Insert constraint C into the list of complex constraints for VAR. */
656 insert_into_complex (unsigned int var, constraint_t c)
658 varinfo_t vi = get_varinfo (var);
659 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
661 VEC_safe_insert (constraint_t, heap, vi->complex, place, c);
665 /* Compare two constraint edges A and B, return true if they are equal. */
668 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
670 return a.src == b.src && a.dest == b.dest;
673 /* Compare two constraint edges, return true if A is less than B */
676 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
678 if (a->dest < b->dest)
680 else if (a->dest == b->dest)
681 return a->src < b->src;
686 /* Find the constraint edge that matches LOOKFOR, in VEC.
687 Return the edge, if found, NULL otherwise. */
689 static constraint_edge_t
690 constraint_edge_vec_find (VEC(constraint_edge_t,heap) *vec,
691 struct constraint_edge lookfor)
694 constraint_edge_t edge;
696 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
697 constraint_edge_less);
698 edge = VEC_index (constraint_edge_t, vec, place);
699 if (!constraint_edge_equal (*edge, lookfor))
704 /* Condense two variable nodes into a single variable node, by moving
705 all associated info from SRC to TO. */
708 condense_varmap_nodes (unsigned int to, unsigned int src)
710 varinfo_t tovi = get_varinfo (to);
711 varinfo_t srcvi = get_varinfo (src);
716 /* the src node, and all its variables, are now the to node. */
718 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
719 get_varinfo (i)->node = to;
721 /* Merge the src node variables and the to node variables. */
722 bitmap_set_bit (tovi->variables, src);
723 bitmap_ior_into (tovi->variables, srcvi->variables);
724 bitmap_clear (srcvi->variables);
726 /* Move all complex constraints from src node into to node */
727 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
729 /* In complex constraints for node src, we may have either
730 a = *src, and *src = a. */
732 if (c->rhs.type == DEREF)
737 constraint_set_union (&tovi->complex, &srcvi->complex);
738 VEC_free (constraint_t, heap, srcvi->complex);
739 srcvi->complex = NULL;
742 /* Erase EDGE from GRAPH. This routine only handles self-edges
743 (e.g. an edge from a to a). */
746 erase_graph_self_edge (constraint_graph_t graph, struct constraint_edge edge)
748 VEC(constraint_edge_t,heap) *predvec = graph->preds[edge.src];
749 VEC(constraint_edge_t,heap) *succvec = graph->succs[edge.dest];
751 gcc_assert (edge.src == edge.dest);
753 /* Remove from the successors. */
754 place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
755 constraint_edge_less);
757 /* Make sure we found the edge. */
758 #ifdef ENABLE_CHECKING
760 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
761 gcc_assert (constraint_edge_equal (*tmp, edge));
764 VEC_ordered_remove (constraint_edge_t, succvec, place);
766 /* Remove from the predecessors. */
767 place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
768 constraint_edge_less);
770 /* Make sure we found the edge. */
771 #ifdef ENABLE_CHECKING
773 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
774 gcc_assert (constraint_edge_equal (*tmp, edge));
777 VEC_ordered_remove (constraint_edge_t, predvec, place);
780 /* Remove edges involving NODE from GRAPH. */
783 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
785 VEC(constraint_edge_t,heap) *succvec = graph->succs[node];
786 VEC(constraint_edge_t,heap) *predvec = graph->preds[node];
790 /* Walk the successors, erase the associated preds. */
791 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
795 struct constraint_edge lookfor;
796 lookfor.src = c->dest;
798 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
799 &lookfor, constraint_edge_less);
800 VEC_ordered_remove (constraint_edge_t, graph->preds[c->dest], place);
802 /* Walk the preds, erase the associated succs. */
803 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
807 struct constraint_edge lookfor;
808 lookfor.src = c->dest;
810 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
811 &lookfor, constraint_edge_less);
812 VEC_ordered_remove (constraint_edge_t, graph->succs[c->dest], place);
815 VEC_free (constraint_edge_t, heap, graph->preds[node]);
816 VEC_free (constraint_edge_t, heap, graph->succs[node]);
817 graph->preds[node] = NULL;
818 graph->succs[node] = NULL;
821 static bool edge_added = false;
823 /* Add edge NEWE to the graph. */
826 add_graph_edge (constraint_graph_t graph, struct constraint_edge newe)
829 unsigned int src = newe.src;
830 unsigned int dest = newe.dest;
831 VEC(constraint_edge_t,heap) *vec;
833 vec = graph->preds[src];
834 place = VEC_lower_bound (constraint_edge_t, vec, &newe,
835 constraint_edge_less);
836 if (place == VEC_length (constraint_edge_t, vec)
837 || VEC_index (constraint_edge_t, vec, place)->dest != dest)
839 constraint_edge_t edge = new_constraint_edge (src, dest);
842 weightbitmap = BITMAP_ALLOC (&ptabitmap_obstack);
843 edge->weights = weightbitmap;
844 VEC_safe_insert (constraint_edge_t, heap, graph->preds[edge->src],
846 edge = new_constraint_edge (dest, src);
847 edge->weights = weightbitmap;
848 place = VEC_lower_bound (constraint_edge_t, graph->succs[edge->src],
849 edge, constraint_edge_less);
850 VEC_safe_insert (constraint_edge_t, heap, graph->succs[edge->src],
860 /* Return the bitmap representing the weights of edge LOOKFOR */
863 get_graph_weights (constraint_graph_t graph, struct constraint_edge lookfor)
865 constraint_edge_t edge;
866 unsigned int src = lookfor.src;
867 VEC(constraint_edge_t,heap) *vec;
868 vec = graph->preds[src];
869 edge = constraint_edge_vec_find (vec, lookfor);
870 gcc_assert (edge != NULL);
871 return edge->weights;
875 /* Merge GRAPH nodes FROM and TO into node TO. */
878 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
881 VEC(constraint_edge_t,heap) *succvec = graph->succs[from];
882 VEC(constraint_edge_t,heap) *predvec = graph->preds[from];
886 /* Merge all the predecessor edges. */
888 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
890 unsigned int d = c->dest;
891 struct constraint_edge olde;
892 struct constraint_edge newe;
899 add_graph_edge (graph, newe);
903 temp = get_graph_weights (graph, olde);
904 weights = get_graph_weights (graph, newe);
905 bitmap_ior_into (weights, temp);
908 /* Merge all the successor edges. */
909 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
911 unsigned int d = c->dest;
912 struct constraint_edge olde;
913 struct constraint_edge newe;
920 add_graph_edge (graph, newe);
924 temp = get_graph_weights (graph, olde);
925 weights = get_graph_weights (graph, newe);
926 bitmap_ior_into (weights, temp);
928 clear_edges_for_node (graph, from);
931 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
932 it doesn't exist in the graph already.
933 Return false if the edge already existed, true otherwise. */
936 int_add_graph_edge (constraint_graph_t graph, unsigned int to,
937 unsigned int from, unsigned HOST_WIDE_INT weight)
939 if (to == from && weight == 0)
946 struct constraint_edge edge;
950 r = add_graph_edge (graph, edge);
951 r |= !bitmap_bit_p (get_graph_weights (graph, edge), weight);
952 bitmap_set_bit (get_graph_weights (graph, edge), weight);
958 /* Return true if LOOKFOR is an existing graph edge. */
961 valid_graph_edge (constraint_graph_t graph, struct constraint_edge lookfor)
963 return constraint_edge_vec_find (graph->preds[lookfor.src], lookfor) != NULL;
967 /* Build the constraint graph. */
970 build_constraint_graph (void)
975 graph = xmalloc (sizeof (struct constraint_graph));
976 graph->succs = xcalloc (VEC_length (varinfo_t, varmap),
977 sizeof (*graph->succs));
978 graph->preds = xcalloc (VEC_length (varinfo_t, varmap),
979 sizeof (*graph->preds));
981 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
983 struct constraint_expr lhs = c->lhs;
984 struct constraint_expr rhs = c->rhs;
985 if (lhs.type == DEREF)
987 /* *x = y or *x = &y (complex) */
988 if (rhs.type == ADDRESSOF || rhs.var > anything_id)
989 insert_into_complex (lhs.var, c);
991 else if (rhs.type == DEREF)
993 /* !special var= *y */
994 if (!(get_varinfo (lhs.var)->is_special_var))
995 insert_into_complex (rhs.var, c);
997 else if (rhs.type == ADDRESSOF)
1000 bitmap_set_bit (get_varinfo (lhs.var)->solution, rhs.var);
1002 else if (lhs.var > anything_id)
1004 /* Ignore 0 weighted self edges, as they can't possibly contribute
1006 if (lhs.var != rhs.var || rhs.offset != 0 || lhs.offset != 0)
1009 struct constraint_edge edge;
1011 edge.dest = rhs.var;
1012 /* x = y (simple) */
1013 add_graph_edge (graph, edge);
1014 bitmap_set_bit (get_graph_weights (graph, edge),
1023 /* Changed variables on the last iteration. */
1024 static unsigned int changed_count;
1025 static sbitmap changed;
1027 DEF_VEC_I(unsigned);
1028 DEF_VEC_ALLOC_I(unsigned,heap);
1031 /* Strongly Connected Component visitation info. */
1036 sbitmap in_component;
1038 unsigned int *visited_index;
1039 VEC(unsigned,heap) *scc_stack;
1040 VEC(unsigned,heap) *unification_queue;
1044 /* Recursive routine to find strongly connected components in GRAPH.
1045 SI is the SCC info to store the information in, and N is the id of current
1046 graph node we are processing.
1048 This is Tarjan's strongly connected component finding algorithm, as
1049 modified by Nuutila to keep only non-root nodes on the stack.
1050 The algorithm can be found in "On finding the strongly connected
1051 connected components in a directed graph" by Esko Nuutila and Eljas
1052 Soisalon-Soininen, in Information Processing Letters volume 49,
1053 number 1, pages 9-14. */
1056 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1058 constraint_edge_t c;
1061 gcc_assert (get_varinfo (n)->node == n);
1062 SET_BIT (si->visited, n);
1063 RESET_BIT (si->in_component, n);
1064 si->visited_index[n] = si->current_index ++;
1066 /* Visit all the successors. */
1067 for (i = 0; VEC_iterate (constraint_edge_t, graph->succs[n], i, c); i++)
1069 /* We only want to find and collapse the zero weight edges. */
1070 if (bitmap_bit_p (c->weights, 0))
1072 unsigned int w = c->dest;
1073 if (!TEST_BIT (si->visited, w))
1074 scc_visit (graph, si, w);
1075 if (!TEST_BIT (si->in_component, w))
1077 unsigned int t = get_varinfo (w)->node;
1078 unsigned int nnode = get_varinfo (n)->node;
1079 if (si->visited_index[t] < si->visited_index[nnode])
1080 get_varinfo (n)->node = t;
1085 /* See if any components have been identified. */
1086 if (get_varinfo (n)->node == n)
1088 unsigned int t = si->visited_index[n];
1089 SET_BIT (si->in_component, n);
1090 while (VEC_length (unsigned, si->scc_stack) != 0
1091 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1093 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1094 get_varinfo (w)->node = n;
1095 SET_BIT (si->in_component, w);
1096 /* Mark this node for collapsing. */
1097 VEC_safe_push (unsigned, heap, si->unification_queue, w);
1101 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1105 /* Collapse two variables into one variable. */
1108 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1110 bitmap tosol, fromsol;
1111 struct constraint_edge edge;
1114 condense_varmap_nodes (to, from);
1115 tosol = get_varinfo (to)->solution;
1116 fromsol = get_varinfo (from)->solution;
1117 bitmap_ior_into (tosol, fromsol);
1118 merge_graph_nodes (graph, to, from);
1121 edge.weights = NULL;
1122 if (valid_graph_edge (graph, edge))
1124 bitmap weights = get_graph_weights (graph, edge);
1125 bitmap_clear_bit (weights, 0);
1126 if (bitmap_empty_p (weights))
1127 erase_graph_self_edge (graph, edge);
1129 bitmap_clear (fromsol);
1130 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1131 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1135 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1136 SI is the Strongly Connected Components information structure that tells us
1137 what components to unify.
1138 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1139 count should be updated to reflect the unification. */
1142 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1143 bool update_changed)
1146 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1149 /* We proceed as follows:
1151 For each component in the queue (components are delineated by
1152 when current_queue_element->node != next_queue_element->node):
1154 rep = representative node for component
1156 For each node (tounify) to be unified in the component,
1157 merge the solution for tounify into tmp bitmap
1159 clear solution for tounify
1161 merge edges from tounify into rep
1163 merge complex constraints from tounify into rep
1165 update changed count to note that tounify will never change
1168 Merge tmp into solution for rep, marking rep changed if this
1169 changed rep's solution.
1171 Delete any 0 weighted self-edges we now have for rep. */
1172 while (i != VEC_length (unsigned, si->unification_queue))
1174 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1175 unsigned int n = get_varinfo (tounify)->node;
1177 if (dump_file && (dump_flags & TDF_DETAILS))
1178 fprintf (dump_file, "Unifying %s to %s\n",
1179 get_varinfo (tounify)->name,
1180 get_varinfo (n)->name);
1182 stats.unified_vars_dynamic++;
1184 stats.unified_vars_static++;
1185 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1186 merge_graph_nodes (graph, n, tounify);
1187 condense_varmap_nodes (n, tounify);
1189 if (update_changed && TEST_BIT (changed, tounify))
1191 RESET_BIT (changed, tounify);
1192 if (!TEST_BIT (changed, n))
1193 SET_BIT (changed, n);
1196 gcc_assert (changed_count > 0);
1201 bitmap_clear (get_varinfo (tounify)->solution);
1204 /* If we've either finished processing the entire queue, or
1205 finished processing all nodes for component n, update the solution for
1207 if (i == VEC_length (unsigned, si->unification_queue)
1208 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1210 struct constraint_edge edge;
1212 /* If the solution changes because of the merging, we need to mark
1213 the variable as changed. */
1214 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1216 if (update_changed && !TEST_BIT (changed, n))
1218 SET_BIT (changed, n);
1225 edge.weights = NULL;
1226 if (valid_graph_edge (graph, edge))
1228 bitmap weights = get_graph_weights (graph, edge);
1229 bitmap_clear_bit (weights, 0);
1230 if (bitmap_empty_p (weights))
1231 erase_graph_self_edge (graph, edge);
1239 /* Information needed to compute the topological ordering of a graph. */
1243 /* sbitmap of visited nodes. */
1245 /* Array that stores the topological order of the graph, *in
1247 VEC(unsigned,heap) *topo_order;
1251 /* Initialize and return a topological info structure. */
1253 static struct topo_info *
1254 init_topo_info (void)
1256 size_t size = VEC_length (varinfo_t, varmap);
1257 struct topo_info *ti = xmalloc (sizeof (struct topo_info));
1258 ti->visited = sbitmap_alloc (size);
1259 sbitmap_zero (ti->visited);
1260 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1265 /* Free the topological sort info pointed to by TI. */
1268 free_topo_info (struct topo_info *ti)
1270 sbitmap_free (ti->visited);
1271 VEC_free (unsigned, heap, ti->topo_order);
1275 /* Visit the graph in topological order, and store the order in the
1276 topo_info structure. */
1279 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1282 VEC(constraint_edge_t,heap) *succs = graph->succs[n];
1283 constraint_edge_t c;
1285 SET_BIT (ti->visited, n);
1286 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1288 if (!TEST_BIT (ti->visited, c->dest))
1289 topo_visit (graph, ti, c->dest);
1291 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1294 /* Return true if variable N + OFFSET is a legal field of N. */
1297 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1299 varinfo_t ninfo = get_varinfo (n);
1301 /* For things we've globbed to single variables, any offset into the
1302 variable acts like the entire variable, so that it becomes offset
1304 if (ninfo->is_special_var
1305 || ninfo->is_artificial_var
1306 || ninfo->is_unknown_size_var)
1311 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1314 /* Process a constraint C that represents *x = &y. */
1317 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1318 constraint_t c, bitmap delta)
1320 unsigned int rhs = c->rhs.var;
1324 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1325 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1327 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1328 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
1330 /* *x != NULL && *x != ANYTHING*/
1334 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1336 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1340 sol = get_varinfo (t)->solution;
1341 if (!bitmap_bit_p (sol, rhs))
1343 bitmap_set_bit (sol, rhs);
1344 if (!TEST_BIT (changed, t))
1346 SET_BIT (changed, t);
1351 else if (dump_file && !(get_varinfo (j)->is_special_var))
1352 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1357 /* Process a constraint C that represents x = *y, using DELTA as the
1358 starting solution. */
1361 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1364 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1366 bitmap sol = get_varinfo (lhs)->solution;
1370 /* For each variable j in delta (Sol(y)), add
1371 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1372 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1374 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1375 if (type_safe (j, &roffset))
1378 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1381 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1385 if (int_add_graph_edge (graph, lhs, t, 0))
1386 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1388 else if (dump_file && !(get_varinfo (j)->is_special_var))
1389 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1393 /* If the LHS solution changed, mark the var as changed. */
1396 get_varinfo (lhs)->solution = sol;
1397 if (!TEST_BIT (changed, lhs))
1399 SET_BIT (changed, lhs);
1405 /* Process a constraint C that represents *x = y. */
1408 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1410 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1411 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1412 bitmap sol = get_varinfo (rhs)->solution;
1416 /* For each member j of delta (Sol(x)), add an edge from y to j and
1417 union Sol(y) into Sol(j) */
1418 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1420 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1421 if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var))
1425 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1427 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1431 if (int_add_graph_edge (graph, t, rhs, roff))
1433 bitmap tmp = get_varinfo (t)->solution;
1434 if (set_union_with_increment (tmp, sol, roff))
1436 get_varinfo (t)->solution = tmp;
1439 sol = get_varinfo (rhs)->solution;
1441 if (!TEST_BIT (changed, t))
1443 SET_BIT (changed, t);
1449 else if (dump_file && !(get_varinfo (j)->is_special_var))
1450 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1454 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1455 constraint (IE *x = &y, x = *y, and *x = y). */
1458 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1460 if (c->lhs.type == DEREF)
1462 if (c->rhs.type == ADDRESSOF)
1465 do_da_constraint (graph, c, delta);
1470 do_ds_constraint (graph, c, delta);
1476 if (!(get_varinfo (c->lhs.var)->is_special_var))
1477 do_sd_constraint (graph, c, delta);
1481 /* Initialize and return a new SCC info structure. */
1483 static struct scc_info *
1484 init_scc_info (void)
1486 struct scc_info *si = xmalloc (sizeof (struct scc_info));
1487 size_t size = VEC_length (varinfo_t, varmap);
1489 si->current_index = 0;
1490 si->visited = sbitmap_alloc (size);
1491 sbitmap_zero (si->visited);
1492 si->in_component = sbitmap_alloc (size);
1493 sbitmap_ones (si->in_component);
1494 si->visited_index = xcalloc (sizeof (unsigned int), size + 1);
1495 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1496 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1500 /* Free an SCC info structure pointed to by SI */
1503 free_scc_info (struct scc_info *si)
1505 sbitmap_free (si->visited);
1506 sbitmap_free (si->in_component);
1507 free (si->visited_index);
1508 VEC_free (unsigned, heap, si->scc_stack);
1509 VEC_free (unsigned, heap, si->unification_queue);
1514 /* Find cycles in GRAPH that occur, using strongly connected components, and
1515 collapse the cycles into a single representative node. if UPDATE_CHANGED
1516 is true, then update the changed sbitmap to note those nodes whose
1517 solutions have changed as a result of collapsing. */
1520 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1523 unsigned int size = VEC_length (varinfo_t, varmap);
1524 struct scc_info *si = init_scc_info ();
1526 for (i = 0; i != size; ++i)
1527 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1528 scc_visit (graph, si, i);
1529 process_unification_queue (graph, si, update_changed);
1533 /* Compute a topological ordering for GRAPH, and store the result in the
1534 topo_info structure TI. */
1537 compute_topo_order (constraint_graph_t graph,
1538 struct topo_info *ti)
1541 unsigned int size = VEC_length (varinfo_t, varmap);
1543 for (i = 0; i != size; ++i)
1544 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1545 topo_visit (graph, ti, i);
1548 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1551 bitmap_other_than_zero_bit_set (bitmap b)
1556 if (bitmap_empty_p (b))
1558 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1563 /* Perform offline variable substitution.
1565 This is a linear time way of identifying variables that must have
1566 equivalent points-to sets, including those caused by static cycles,
1567 and single entry subgraphs, in the constraint graph.
1569 The technique is described in "Off-line variable substitution for
1570 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1571 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1574 perform_var_substitution (constraint_graph_t graph)
1576 struct topo_info *ti = init_topo_info ();
1578 /* Compute the topological ordering of the graph, then visit each
1579 node in topological order. */
1580 compute_topo_order (graph, ti);
1582 while (VEC_length (unsigned, ti->topo_order) != 0)
1584 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1586 varinfo_t vi = get_varinfo (i);
1587 bool okay_to_elim = false;
1588 unsigned int root = VEC_length (varinfo_t, varmap);
1589 VEC(constraint_edge_t,heap) *predvec = graph->preds[i];
1590 constraint_edge_t ce;
1593 /* We can't eliminate things whose address is taken, or which is
1594 the target of a dereference. */
1595 if (vi->address_taken || vi->indirect_target)
1598 /* See if all predecessors of I are ripe for elimination */
1599 for (pred = 0; VEC_iterate (constraint_edge_t, predvec, pred, ce); pred++)
1603 weight = get_graph_weights (graph, *ce);
1605 /* We can't eliminate variables that have nonzero weighted
1606 edges between them. */
1607 if (bitmap_other_than_zero_bit_set (weight))
1609 okay_to_elim = false;
1612 w = get_varinfo (ce->dest)->node;
1614 /* We can't eliminate the node if one of the predecessors is
1615 part of a different strongly connected component. */
1619 okay_to_elim = true;
1623 okay_to_elim = false;
1627 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1628 then Solution(i) is a subset of Solution (w), where w is a
1629 predecessor in the graph.
1630 Corollary: If all predecessors of i have the same
1631 points-to set, then i has that same points-to set as
1632 those predecessors. */
1633 tmp = BITMAP_ALLOC (NULL);
1634 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1635 get_varinfo (w)->solution);
1636 if (!bitmap_empty_p (tmp))
1638 okay_to_elim = false;
1645 /* See if the root is different than the original node.
1646 If so, we've found an equivalence. */
1647 if (root != get_varinfo (i)->node && okay_to_elim)
1649 /* Found an equivalence */
1650 get_varinfo (i)->node = root;
1651 collapse_nodes (graph, root, i);
1652 if (dump_file && (dump_flags & TDF_DETAILS))
1653 fprintf (dump_file, "Collapsing %s into %s\n",
1654 get_varinfo (i)->name,
1655 get_varinfo (root)->name);
1656 stats.collapsed_vars++;
1660 free_topo_info (ti);
1664 /* Solve the constraint graph GRAPH using our worklist solver.
1665 This is based on the PW* family of solvers from the "Efficient Field
1666 Sensitive Pointer Analysis for C" paper.
1667 It works by iterating over all the graph nodes, processing the complex
1668 constraints and propagating the copy constraints, until everything stops
1669 changed. This corresponds to steps 6-8 in the solving list given above. */
1672 solve_graph (constraint_graph_t graph)
1674 unsigned int size = VEC_length (varinfo_t, varmap);
1677 changed_count = size;
1678 changed = sbitmap_alloc (size);
1679 sbitmap_ones (changed);
1681 /* The already collapsed/unreachable nodes will never change, so we
1682 need to account for them in changed_count. */
1683 for (i = 0; i < size; i++)
1684 if (get_varinfo (i)->node != i)
1687 while (changed_count > 0)
1690 struct topo_info *ti = init_topo_info ();
1693 bitmap_obstack_initialize (&iteration_obstack);
1697 /* We already did cycle elimination once, when we did
1698 variable substitution, so we don't need it again for the
1700 if (stats.iterations > 1)
1701 find_and_collapse_graph_cycles (graph, true);
1706 compute_topo_order (graph, ti);
1708 while (VEC_length (unsigned, ti->topo_order) != 0)
1710 i = VEC_pop (unsigned, ti->topo_order);
1711 gcc_assert (get_varinfo (i)->node == i);
1713 /* If the node has changed, we need to process the
1714 complex constraints and outgoing edges again. */
1715 if (TEST_BIT (changed, i))
1719 constraint_edge_t e;
1721 VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
1722 VEC(constraint_edge_t,heap) *succs;
1724 RESET_BIT (changed, i);
1727 /* Process the complex constraints */
1728 solution = get_varinfo (i)->solution;
1729 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
1730 do_complex_constraint (graph, c, solution);
1732 /* Propagate solution to all successors. */
1733 succs = graph->succs[i];
1734 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
1736 bitmap tmp = get_varinfo (e->dest)->solution;
1739 bitmap weights = e->weights;
1742 gcc_assert (!bitmap_empty_p (weights));
1743 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
1744 flag |= set_union_with_increment (tmp, solution, k);
1748 get_varinfo (e->dest)->solution = tmp;
1749 if (!TEST_BIT (changed, e->dest))
1751 SET_BIT (changed, e->dest);
1758 free_topo_info (ti);
1759 bitmap_obstack_release (&iteration_obstack);
1762 sbitmap_free (changed);
1766 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1768 /* Map from trees to variable ids. */
1769 static htab_t id_for_tree;
1771 typedef struct tree_id
1777 /* Hash a tree id structure. */
1780 tree_id_hash (const void *p)
1782 const tree_id_t ta = (tree_id_t) p;
1783 return htab_hash_pointer (ta->t);
1786 /* Return true if the tree in P1 and the tree in P2 are the same. */
1789 tree_id_eq (const void *p1, const void *p2)
1791 const tree_id_t ta1 = (tree_id_t) p1;
1792 const tree_id_t ta2 = (tree_id_t) p2;
1793 return ta1->t == ta2->t;
1796 /* Insert ID as the variable id for tree T in the hashtable. */
1799 insert_id_for_tree (tree t, int id)
1802 struct tree_id finder;
1806 slot = htab_find_slot (id_for_tree, &finder, INSERT);
1807 gcc_assert (*slot == NULL);
1808 new_pair = xmalloc (sizeof (struct tree_id));
1811 *slot = (void *)new_pair;
1814 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1815 exist in the hash table, return false, otherwise, return true and
1816 set *ID to the id we found. */
1819 lookup_id_for_tree (tree t, unsigned int *id)
1822 struct tree_id finder;
1825 pair = htab_find (id_for_tree, &finder);
1832 /* Return a printable name for DECL */
1835 alias_get_name (tree decl)
1837 const char *res = get_name (decl);
1839 int num_printed = 0;
1845 if (TREE_CODE (decl) == SSA_NAME)
1847 num_printed = asprintf (&temp, "%s_%u",
1848 alias_get_name (SSA_NAME_VAR (decl)),
1849 SSA_NAME_VERSION (decl));
1851 else if (DECL_P (decl))
1853 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
1855 if (num_printed > 0)
1857 res = ggc_strdup (temp);
1863 /* Find the variable id for tree T in the hashtable.
1864 If T doesn't exist in the hash table, create an entry for it. */
1867 get_id_for_tree (tree t)
1870 struct tree_id finder;
1873 pair = htab_find (id_for_tree, &finder);
1875 return create_variable_info_for (t, alias_get_name (t));
1880 /* Get a constraint expression from an SSA_VAR_P node. */
1882 static struct constraint_expr
1883 get_constraint_exp_from_ssa_var (tree t)
1885 struct constraint_expr cexpr;
1887 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
1889 /* For parameters, get at the points-to set for the actual parm
1891 if (TREE_CODE (t) == SSA_NAME
1892 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
1893 && default_def (SSA_NAME_VAR (t)) == t)
1894 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
1896 cexpr.type = SCALAR;
1898 cexpr.var = get_id_for_tree (t);
1899 /* If we determine the result is "anything", and we know this is readonly,
1900 say it points to readonly memory instead. */
1901 if (cexpr.var == anything_id && TREE_READONLY (t))
1903 cexpr.type = ADDRESSOF;
1904 cexpr.var = readonly_id;
1911 /* Process a completed constraint T, and add it to the constraint
1915 process_constraint (constraint_t t)
1917 struct constraint_expr rhs = t->rhs;
1918 struct constraint_expr lhs = t->lhs;
1920 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
1921 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
1923 /* ANYTHING == ANYTHING is pointless. */
1924 if (lhs.var == anything_id && rhs.var == anything_id)
1927 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1928 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
1933 process_constraint (t);
1935 /* This can happen in our IR with things like n->a = *p */
1936 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
1938 /* Split into tmp = *rhs, *lhs = tmp */
1939 tree rhsdecl = get_varinfo (rhs.var)->decl;
1940 tree pointertype = TREE_TYPE (rhsdecl);
1941 tree pointedtotype = TREE_TYPE (pointertype);
1942 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
1943 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
1945 /* If this is an aggregate of known size, we should have passed
1946 this off to do_structure_copy, and it should have broken it
1948 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
1949 || get_varinfo (rhs.var)->is_unknown_size_var);
1951 process_constraint (new_constraint (tmplhs, rhs));
1952 process_constraint (new_constraint (lhs, tmplhs));
1954 else if (rhs.type == ADDRESSOF)
1957 gcc_assert (rhs.offset == 0);
1959 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
1960 vi->address_taken = true;
1962 VEC_safe_push (constraint_t, heap, constraints, t);
1966 if (lhs.type != DEREF && rhs.type == DEREF)
1967 get_varinfo (lhs.var)->indirect_target = true;
1968 VEC_safe_push (constraint_t, heap, constraints, t);
1973 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1976 static unsigned HOST_WIDE_INT
1977 bitpos_of_field (const tree fdecl)
1980 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
1981 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
1984 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
1985 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
1989 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1990 overlaps with a field at [FIELDPOS, FIELDSIZE] */
1993 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
1994 const unsigned HOST_WIDE_INT fieldsize,
1995 const unsigned HOST_WIDE_INT accesspos,
1996 const unsigned HOST_WIDE_INT accesssize)
1998 if (fieldpos == accesspos && fieldsize == accesssize)
2000 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
2002 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2008 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2010 static struct constraint_expr
2011 get_constraint_for_component_ref (tree t, bool *needs_anyoffset)
2013 struct constraint_expr result;
2014 HOST_WIDE_INT bitsize;
2015 HOST_WIDE_INT bitpos;
2017 enum machine_mode mode;
2023 result.type = SCALAR;
2026 /* Some people like to do cute things like take the address of
2029 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2030 forzero = TREE_OPERAND (forzero, 0);
2032 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2035 result.var = integer_id;
2036 result.type = SCALAR;
2040 t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode,
2041 &unsignedp, &volatilep, false);
2042 result = get_constraint_for (t, needs_anyoffset);
2044 /* This can also happen due to weird offsetof type macros. */
2045 if (TREE_CODE (t) != ADDR_EXPR && result.type == ADDRESSOF)
2046 result.type = SCALAR;
2048 /* If we know where this goes, then yay. Otherwise, booo. */
2050 if (offset == NULL && bitsize != -1)
2052 result.offset = bitpos;
2054 else if (needs_anyoffset)
2057 *needs_anyoffset = true;
2061 result.var = anything_id;
2065 if (result.type == SCALAR)
2067 /* In languages like C, you can access one past the end of an
2068 array. You aren't allowed to dereference it, so we can
2069 ignore this constraint. When we handle pointer subtraction,
2070 we may have to do something cute here. */
2072 if (result.offset < get_varinfo (result.var)->fullsize)
2074 /* It's also not true that the constraint will actually start at the
2075 right offset, it may start in some padding. We only care about
2076 setting the constraint to the first actual field it touches, so
2079 for (curr = get_varinfo (result.var); curr; curr = curr->next)
2081 if (offset_overlaps_with_access (curr->offset, curr->size,
2082 result.offset, bitsize))
2084 result.var = curr->id;
2089 /* assert that we found *some* field there. The user couldn't be
2090 accessing *only* padding. */
2095 if (dump_file && (dump_flags & TDF_DETAILS))
2096 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2105 /* Dereference the constraint expression CONS, and return the result.
2106 DEREF (ADDRESSOF) = SCALAR
2107 DEREF (SCALAR) = DEREF
2108 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2109 This is needed so that we can handle dereferencing DEREF constraints. */
2111 static struct constraint_expr
2112 do_deref (struct constraint_expr cons)
2114 if (cons.type == SCALAR)
2119 else if (cons.type == ADDRESSOF)
2124 else if (cons.type == DEREF)
2126 tree tmpvar = create_tmp_var_raw (ptr_type_node, "derefmp");
2127 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2128 process_constraint (new_constraint (tmplhs, cons));
2129 cons.var = tmplhs.var;
2136 /* Given a tree T, return the constraint expression for it. */
2138 static struct constraint_expr
2139 get_constraint_for (tree t, bool *need_anyoffset)
2141 struct constraint_expr temp;
2143 /* x = integer is all glommed to a single variable, which doesn't
2144 point to anything by itself. That is, of course, unless it is an
2145 integer constant being treated as a pointer, in which case, we
2146 will return that this is really the addressof anything. This
2147 happens below, since it will fall into the default case. The only
2148 case we know something about an integer treated like a pointer is
2149 when it is the NULL pointer, and then we just say it points to
2151 if (TREE_CODE (t) == INTEGER_CST
2152 && !POINTER_TYPE_P (TREE_TYPE (t)))
2154 temp.var = integer_id;
2159 else if (TREE_CODE (t) == INTEGER_CST
2160 && integer_zerop (t))
2162 temp.var = nothing_id;
2163 temp.type = ADDRESSOF;
2168 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2170 case tcc_expression:
2172 switch (TREE_CODE (t))
2176 temp = get_constraint_for (TREE_OPERAND (t, 0), need_anyoffset);
2177 if (temp.type == DEREF)
2180 temp.type = ADDRESSOF;
2186 /* XXX: In interprocedural mode, if we didn't have the
2187 body, we would need to do *each pointer argument =
2189 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2194 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2195 DECL_EXTERNAL (heapvar) = 1;
2196 add_referenced_tmp_var (heapvar);
2197 temp.var = create_variable_info_for (heapvar,
2198 alias_get_name (heapvar));
2200 vi = get_varinfo (temp.var);
2201 vi->is_artificial_var = 1;
2202 vi->is_heap_var = 1;
2203 temp.type = ADDRESSOF;
2210 temp.type = ADDRESSOF;
2211 temp.var = anything_id;
2219 switch (TREE_CODE (t))
2223 temp = get_constraint_for (TREE_OPERAND (t, 0), need_anyoffset);
2224 temp = do_deref (temp);
2229 temp = get_constraint_for_component_ref (t, need_anyoffset);
2233 temp.type = ADDRESSOF;
2234 temp.var = anything_id;
2242 switch (TREE_CODE (t))
2246 case NON_LVALUE_EXPR:
2248 tree op = TREE_OPERAND (t, 0);
2250 /* Cast from non-pointer to pointers are bad news for us.
2251 Anything else, we see through */
2252 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2253 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2254 return get_constraint_for (op, need_anyoffset);
2260 temp.type = ADDRESSOF;
2261 temp.var = anything_id;
2267 case tcc_exceptional:
2269 switch (TREE_CODE (t))
2272 return get_constraint_for (PHI_RESULT (t), need_anyoffset);
2274 return get_constraint_exp_from_ssa_var (t);
2277 temp.type = ADDRESSOF;
2278 temp.var = anything_id;
2284 case tcc_declaration:
2285 return get_constraint_exp_from_ssa_var (t);
2288 temp.type = ADDRESSOF;
2289 temp.var = anything_id;
2297 /* Handle the structure copy case where we have a simple structure copy
2298 between LHS and RHS that is of SIZE (in bits)
2300 For each field of the lhs variable (lhsfield)
2301 For each field of the rhs variable at lhsfield.offset (rhsfield)
2302 add the constraint lhsfield = rhsfield
2306 do_simple_structure_copy (const struct constraint_expr lhs,
2307 const struct constraint_expr rhs,
2308 const unsigned HOST_WIDE_INT size)
2310 varinfo_t p = get_varinfo (lhs.var);
2311 unsigned HOST_WIDE_INT pstart, last;
2313 last = p->offset + size;
2314 for (; p && p->offset < last; p = p->next)
2317 struct constraint_expr templhs = lhs;
2318 struct constraint_expr temprhs = rhs;
2319 unsigned HOST_WIDE_INT fieldoffset;
2321 templhs.var = p->id;
2322 q = get_varinfo (temprhs.var);
2323 fieldoffset = p->offset - pstart;
2324 q = first_vi_for_offset (q, q->offset + fieldoffset);
2325 temprhs.var = q->id;
2326 process_constraint (new_constraint (templhs, temprhs));
2331 /* Handle the structure copy case where we have a structure copy between a
2332 aggregate on the LHS and a dereference of a pointer on the RHS
2333 that is of SIZE (in bits)
2335 For each field of the lhs variable (lhsfield)
2336 rhs.offset = lhsfield->offset
2337 add the constraint lhsfield = rhs
2341 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2342 const struct constraint_expr rhs,
2343 const unsigned HOST_WIDE_INT size)
2345 varinfo_t p = get_varinfo (lhs.var);
2346 unsigned HOST_WIDE_INT pstart,last;
2348 last = p->offset + size;
2350 for (; p && p->offset < last; p = p->next)
2353 struct constraint_expr templhs = lhs;
2354 struct constraint_expr temprhs = rhs;
2355 unsigned HOST_WIDE_INT fieldoffset;
2358 if (templhs.type == SCALAR)
2359 templhs.var = p->id;
2361 templhs.offset = p->offset;
2363 q = get_varinfo (temprhs.var);
2364 fieldoffset = p->offset - pstart;
2365 temprhs.offset += fieldoffset;
2366 process_constraint (new_constraint (templhs, temprhs));
2370 /* Handle the structure copy case where we have a structure copy
2371 between a aggregate on the RHS and a dereference of a pointer on
2372 the LHS that is of SIZE (in bits)
2374 For each field of the rhs variable (rhsfield)
2375 lhs.offset = rhsfield->offset
2376 add the constraint lhs = rhsfield
2380 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2381 const struct constraint_expr rhs,
2382 const unsigned HOST_WIDE_INT size)
2384 varinfo_t p = get_varinfo (rhs.var);
2385 unsigned HOST_WIDE_INT pstart,last;
2387 last = p->offset + size;
2389 for (; p && p->offset < last; p = p->next)
2392 struct constraint_expr templhs = lhs;
2393 struct constraint_expr temprhs = rhs;
2394 unsigned HOST_WIDE_INT fieldoffset;
2397 if (temprhs.type == SCALAR)
2398 temprhs.var = p->id;
2400 temprhs.offset = p->offset;
2402 q = get_varinfo (templhs.var);
2403 fieldoffset = p->offset - pstart;
2404 templhs.offset += fieldoffset;
2405 process_constraint (new_constraint (templhs, temprhs));
2410 /* Handle aggregate copies by expanding into copies of the respective
2411 fields of the structures. */
2414 do_structure_copy (tree lhsop, tree rhsop)
2416 struct constraint_expr lhs, rhs, tmp;
2418 unsigned HOST_WIDE_INT lhssize;
2419 unsigned HOST_WIDE_INT rhssize;
2421 lhs = get_constraint_for (lhsop, NULL);
2422 rhs = get_constraint_for (rhsop, NULL);
2424 /* If we have special var = x, swap it around. */
2425 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2432 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2433 possible it's something we could handle. However, most cases falling
2434 into this are dealing with transparent unions, which are slightly
2436 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2438 rhs.type = ADDRESSOF;
2439 rhs.var = anything_id;
2442 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2443 that special var. */
2444 if (rhs.var <= integer_id)
2446 for (p = get_varinfo (lhs.var); p; p = p->next)
2448 struct constraint_expr templhs = lhs;
2449 struct constraint_expr temprhs = rhs;
2450 if (templhs.type == SCALAR )
2451 templhs.var = p->id;
2453 templhs.offset += p->offset;
2454 process_constraint (new_constraint (templhs, temprhs));
2459 tree rhstype = TREE_TYPE (rhsop);
2460 tree lhstype = TREE_TYPE (lhsop);
2461 tree rhstypesize = TYPE_SIZE (rhstype);
2462 tree lhstypesize = TYPE_SIZE (lhstype);
2464 /* If we have a variably sized types on the rhs or lhs, and a deref
2465 constraint, add the constraint, lhsconstraint = &ANYTHING.
2466 This is conservatively correct because either the lhs is an unknown
2467 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2468 constraint, and every variable it can point to must be unknown sized
2469 anyway, so we don't need to worry about fields at all. */
2470 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2471 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2473 rhs.var = anything_id;
2474 rhs.type = ADDRESSOF;
2476 process_constraint (new_constraint (lhs, rhs));
2480 /* The size only really matters insofar as we don't set more or less of
2481 the variable. If we hit an unknown size var, the size should be the
2482 whole darn thing. */
2483 if (get_varinfo (rhs.var)->is_unknown_size_var)
2486 rhssize = TREE_INT_CST_LOW (rhstypesize);
2488 if (get_varinfo (lhs.var)->is_unknown_size_var)
2491 lhssize = TREE_INT_CST_LOW (lhstypesize);
2494 if (rhs.type == SCALAR && lhs.type == SCALAR)
2495 do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2496 else if (lhs.type != DEREF && rhs.type == DEREF)
2497 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2498 else if (lhs.type == DEREF && rhs.type != DEREF)
2499 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2502 tree pointedtotype = lhstype;
2505 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2506 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2507 do_structure_copy (tmpvar, rhsop);
2508 do_structure_copy (lhsop, tmpvar);
2514 /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere
2518 ref_contains_indirect_ref (tree ref)
2520 while (handled_component_p (ref))
2522 if (TREE_CODE (ref) == INDIRECT_REF)
2524 ref = TREE_OPERAND (ref, 0);
2530 /* Update related alias information kept in AI. This is used when
2531 building name tags, alias sets and deciding grouping heuristics.
2532 STMT is the statement to process. This function also updates
2533 ADDRESSABLE_VARS. */
2536 update_alias_info (tree stmt, struct alias_info *ai)
2539 use_operand_p use_p;
2541 bool stmt_escapes_p = is_escape_site (stmt, ai);
2544 /* Mark all the variables whose address are taken by the statement. */
2545 addr_taken = addresses_taken (stmt);
2548 bitmap_ior_into (addressable_vars, addr_taken);
2550 /* If STMT is an escape point, all the addresses taken by it are
2557 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
2558 mark_call_clobbered (referenced_var (i));
2562 /* Process each operand use. If an operand may be aliased, keep
2563 track of how many times it's being used. For pointers, determine
2564 whether they are dereferenced by the statement, or whether their
2565 value escapes, etc. */
2566 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2570 struct ptr_info_def *pi;
2571 bool is_store, is_potential_deref;
2572 unsigned num_uses, num_derefs;
2574 op = USE_FROM_PTR (use_p);
2576 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2577 to the set of addressable variables. */
2578 if (TREE_CODE (op) == ADDR_EXPR)
2580 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
2582 /* PHI nodes don't have annotations for pinning the set
2583 of addresses taken, so we collect them here.
2585 FIXME, should we allow PHI nodes to have annotations
2586 so that they can be treated like regular statements?
2587 Currently, they are treated as second-class
2589 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
2593 /* Ignore constants. */
2594 if (TREE_CODE (op) != SSA_NAME)
2597 var = SSA_NAME_VAR (op);
2598 v_ann = var_ann (var);
2600 /* If the operand's variable may be aliased, keep track of how
2601 many times we've referenced it. This is used for alias
2602 grouping in compute_flow_insensitive_aliasing. */
2603 if (may_be_aliased (var))
2604 NUM_REFERENCES_INC (v_ann);
2606 /* We are only interested in pointers. */
2607 if (!POINTER_TYPE_P (TREE_TYPE (op)))
2610 pi = get_ptr_info (op);
2612 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
2613 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
2615 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
2616 VARRAY_PUSH_TREE (ai->processed_ptrs, op);
2619 /* If STMT is a PHI node, then it will not have pointer
2620 dereferences and it will not be an escape point. */
2621 if (TREE_CODE (stmt) == PHI_NODE)
2624 /* Determine whether OP is a dereferenced pointer, and if STMT
2625 is an escape point, whether OP escapes. */
2626 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
2628 /* Handle a corner case involving address expressions of the
2629 form '&PTR->FLD'. The problem with these expressions is that
2630 they do not represent a dereference of PTR. However, if some
2631 other transformation propagates them into an INDIRECT_REF
2632 expression, we end up with '*(&PTR->FLD)' which is folded
2635 So, if the original code had no other dereferences of PTR,
2636 the aliaser will not create memory tags for it, and when
2637 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
2638 memory operations will receive no V_MAY_DEF/VUSE operands.
2640 One solution would be to have count_uses_and_derefs consider
2641 &PTR->FLD a dereference of PTR. But that is wrong, since it
2642 is not really a dereference but an offset calculation.
2644 What we do here is to recognize these special ADDR_EXPR
2645 nodes. Since these expressions are never GIMPLE values (they
2646 are not GIMPLE invariants), they can only appear on the RHS
2647 of an assignment and their base address is always an
2648 INDIRECT_REF expression. */
2649 is_potential_deref = false;
2650 if (TREE_CODE (stmt) == MODIFY_EXPR
2651 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
2652 && !is_gimple_val (TREE_OPERAND (stmt, 1)))
2654 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
2655 this represents a potential dereference of PTR. */
2656 tree rhs = TREE_OPERAND (stmt, 1);
2657 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2658 if (TREE_CODE (base) == INDIRECT_REF
2659 && TREE_OPERAND (base, 0) == op)
2660 is_potential_deref = true;
2663 if (num_derefs > 0 || is_potential_deref)
2665 /* Mark OP as dereferenced. In a subsequent pass,
2666 dereferenced pointers that point to a set of
2667 variables will be assigned a name tag to alias
2668 all the variables OP points to. */
2669 pi->is_dereferenced = 1;
2671 /* Keep track of how many time we've dereferenced each
2673 NUM_REFERENCES_INC (v_ann);
2675 /* If this is a store operation, mark OP as being
2676 dereferenced to store, otherwise mark it as being
2677 dereferenced to load. */
2679 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
2681 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
2684 if (stmt_escapes_p && num_derefs < num_uses)
2686 /* If STMT is an escape point and STMT contains at
2687 least one direct use of OP, then the value of OP
2688 escapes and so the pointed-to variables need to
2689 be marked call-clobbered. */
2690 pi->value_escapes_p = 1;
2692 /* If the statement makes a function call, assume
2693 that pointer OP will be dereferenced in a store
2694 operation inside the called function. */
2695 if (get_call_expr_in (stmt))
2697 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
2698 pi->is_dereferenced = 1;
2703 if (TREE_CODE (stmt) == PHI_NODE)
2706 /* Update reference counter for definitions to any
2707 potentially aliased variable. This is used in the alias
2708 grouping heuristics. */
2709 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
2711 tree var = SSA_NAME_VAR (op);
2712 var_ann_t ann = var_ann (var);
2713 bitmap_set_bit (ai->written_vars, DECL_UID (var));
2714 if (may_be_aliased (var))
2715 NUM_REFERENCES_INC (ann);
2719 /* Mark variables in V_MAY_DEF operands as being written to. */
2720 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
2722 tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
2723 bitmap_set_bit (ai->written_vars, DECL_UID (var));
2728 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
2729 Expressions of the type PTR + CST can be handled in two ways:
2731 1- If the constraint for PTR is ADDRESSOF for a non-structure
2732 variable, then we can use it directly because adding or
2733 subtracting a constant may not alter the original ADDRESSOF
2734 constraint (i.e., pointer arithmetic may not legally go outside
2735 an object's boundaries).
2737 2- If the constraint for PTR is ADDRESSOF for a structure variable,
2738 then if CST is a compile-time constant that can be used as an
2739 offset, we can determine which sub-variable will be pointed-to
2742 Return true if the expression is handled. For any other kind of
2743 expression, return false so that each operand can be added as a
2744 separate constraint by the caller. */
2747 handle_ptr_arith (struct constraint_expr lhs, tree expr)
2750 struct constraint_expr base, offset;
2752 if (TREE_CODE (expr) != PLUS_EXPR)
2755 op0 = TREE_OPERAND (expr, 0);
2756 op1 = TREE_OPERAND (expr, 1);
2758 base = get_constraint_for (op0, NULL);
2760 offset.var = anyoffset_id;
2761 offset.type = ADDRESSOF;
2764 process_constraint (new_constraint (lhs, base));
2765 process_constraint (new_constraint (lhs, offset));
2771 /* Walk statement T setting up aliasing constraints according to the
2772 references found in T. This function is the main part of the
2773 constraint builder. AI points to auxiliary alias information used
2774 when building alias sets and computing alias grouping heuristics. */
2777 find_func_aliases (tree t, struct alias_info *ai)
2779 struct constraint_expr lhs, rhs;
2781 /* Update various related attributes like escaped addresses, pointer
2782 dereferences for loads and stores. This is used when creating
2783 name tags and alias sets. */
2784 update_alias_info (t, ai);
2786 /* Now build constraints expressions. */
2787 if (TREE_CODE (t) == PHI_NODE)
2789 /* Only care about pointers and structures containing
2791 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
2792 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
2796 lhs = get_constraint_for (PHI_RESULT (t), NULL);
2797 for (i = 0; i < PHI_NUM_ARGS (t); i++)
2799 rhs = get_constraint_for (PHI_ARG_DEF (t, i), NULL);
2800 process_constraint (new_constraint (lhs, rhs));
2804 else if (TREE_CODE (t) == MODIFY_EXPR)
2806 tree lhsop = TREE_OPERAND (t, 0);
2807 tree rhsop = TREE_OPERAND (t, 1);
2810 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2811 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
2813 do_structure_copy (lhsop, rhsop);
2817 /* Only care about operations with pointers, structures
2818 containing pointers, dereferences, and call expressions. */
2819 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
2820 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2821 || ref_contains_indirect_ref (lhsop)
2822 || TREE_CODE (rhsop) == CALL_EXPR)
2824 lhs = get_constraint_for (lhsop, NULL);
2825 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
2827 /* RHS that consist of unary operations,
2828 exceptional types, or bare decls/constants, get
2829 handled directly by get_constraint_for. */
2831 case tcc_declaration:
2833 case tcc_exceptional:
2834 case tcc_expression:
2837 bool need_anyoffset = false;
2838 rhs = get_constraint_for (rhsop, &need_anyoffset);
2839 process_constraint (new_constraint (lhs, rhs));
2841 /* When taking the address of an aggregate
2842 type, from the LHS we can access any field
2844 if (need_anyoffset || (rhs.type == ADDRESSOF
2845 && !(get_varinfo (rhs.var)->is_special_var)
2846 && AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (rhsop)))))
2848 rhs.var = anyoffset_id;
2849 rhs.type = ADDRESSOF;
2851 process_constraint (new_constraint (lhs, rhs));
2858 /* For pointer arithmetic of the form
2859 PTR + CST, we can simply use PTR's
2860 constraint because pointer arithmetic is
2861 not allowed to go out of bounds. */
2862 if (handle_ptr_arith (lhs, rhsop))
2867 /* Otherwise, walk each operand. Notice that we
2868 can't use the operand interface because we need
2869 to process expressions other than simple operands
2870 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
2872 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
2874 tree op = TREE_OPERAND (rhsop, i);
2875 rhs = get_constraint_for (op, NULL);
2876 process_constraint (new_constraint (lhs, rhs));
2883 /* After promoting variables and computing aliasing we will
2884 need to re-scan most statements. FIXME: Try to minimize the
2885 number of statements re-scanned. It's not really necessary to
2886 re-scan *all* statements. */
2887 mark_stmt_modified (t);
2891 /* Find the first varinfo in the same variable as START that overlaps with
2893 Effectively, walk the chain of fields for the variable START to find the
2894 first field that overlaps with OFFSET.
2895 Return NULL if we can't find one. */
2898 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
2900 varinfo_t curr = start;
2903 /* We may not find a variable in the field list with the actual
2904 offset when when we have glommed a structure to a variable.
2905 In that case, however, offset should still be within the size
2907 if (offset >= curr->offset && offset < (curr->offset + curr->size))
2915 /* Insert the varinfo FIELD into the field list for BASE, ordered by
2919 insert_into_field_list (varinfo_t base, varinfo_t field)
2921 varinfo_t prev = base;
2922 varinfo_t curr = base->next;
2933 if (field->offset <= curr->offset)
2938 field->next = prev->next;
2943 /* qsort comparison function for two fieldoff's PA and PB */
2946 fieldoff_compare (const void *pa, const void *pb)
2948 const fieldoff_s *foa = (const fieldoff_s *)pa;
2949 const fieldoff_s *fob = (const fieldoff_s *)pb;
2950 HOST_WIDE_INT foasize, fobsize;
2952 if (foa->offset != fob->offset)
2953 return foa->offset - fob->offset;
2955 foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
2956 fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
2957 return foasize - fobsize;
2960 /* Sort a fieldstack according to the field offset and sizes. */
2961 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
2963 qsort (VEC_address (fieldoff_s, fieldstack),
2964 VEC_length (fieldoff_s, fieldstack),
2965 sizeof (fieldoff_s),
2969 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
2970 of TYPE onto fieldstack, recording their offsets along the way.
2971 OFFSET is used to keep track of the offset in this entire structure, rather
2972 than just the immediately containing structure. Returns the number
2974 HAS_UNION is set to true if we find a union type as a field of
2978 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
2979 HOST_WIDE_INT offset, bool *has_union)
2984 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2985 if (TREE_CODE (field) == FIELD_DECL)
2991 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
2992 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
2995 if (!var_can_have_subvars (field))
2997 else if (!(pushed = push_fields_onto_fieldstack
2998 (TREE_TYPE (field), fieldstack,
2999 offset + bitpos_of_field (field), has_union))
3000 && DECL_SIZE (field)
3001 && !integer_zerop (DECL_SIZE (field)))
3002 /* Empty structures may have actual size, like in C++. So
3003 see if we didn't push any subfields and the size is
3004 nonzero, push the field onto the stack */
3011 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3012 pair->field = field;
3013 pair->offset = offset + bitpos_of_field (field);
3024 make_constraint_to_anything (varinfo_t vi)
3026 struct constraint_expr lhs, rhs;
3032 rhs.var = anything_id;
3034 rhs.type = ADDRESSOF;
3035 process_constraint (new_constraint (lhs, rhs));
3038 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3039 This will also create any varinfo structures necessary for fields
3043 create_variable_info_for (tree decl, const char *name)
3045 unsigned int index = VEC_length (varinfo_t, varmap);
3047 tree decltype = TREE_TYPE (decl);
3048 bool notokay = false;
3050 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
3051 VEC (fieldoff_s,heap) *fieldstack = NULL;
3054 hasunion = TREE_CODE (decltype) == UNION_TYPE
3055 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
3056 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
3058 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
3061 VEC_free (fieldoff_s, heap, fieldstack);
3067 /* If the variable doesn't have subvars, we may end up needing to
3068 sort the field list and create fake variables for all the
3070 vi = new_var_info (decl, index, name, index);
3073 vi->has_union = hasunion;
3074 if (!TYPE_SIZE (decltype)
3075 || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
3076 || TREE_CODE (decltype) == ARRAY_TYPE
3077 || TREE_CODE (decltype) == UNION_TYPE
3078 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
3080 vi->is_unknown_size_var = true;
3086 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
3087 vi->size = vi->fullsize;
3090 insert_id_for_tree (vi->decl, index);
3091 VEC_safe_push (varinfo_t, heap, varmap, vi);
3093 make_constraint_to_anything (vi);
3096 if (use_field_sensitive
3098 && !vi->is_unknown_size_var
3099 && var_can_have_subvars (decl))
3101 unsigned int newindex = VEC_length (varinfo_t, varmap);
3102 fieldoff_s *fo = NULL;
3106 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3108 if (!DECL_SIZE (fo->field)
3109 || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
3110 || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE
3118 /* We can't sort them if we have a field with a variable sized type,
3119 which will make notokay = true. In that case, we are going to return
3120 without creating varinfos for the fields anyway, so sorting them is a
3123 sort_fieldstack (fieldstack);
3125 if (VEC_length (fieldoff_s, fieldstack) != 0)
3126 fo = VEC_index (fieldoff_s, fieldstack, 0);
3128 if (fo == NULL || notokay)
3130 vi->is_unknown_size_var = 1;
3133 VEC_free (fieldoff_s, heap, fieldstack);
3138 vi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
3139 vi->offset = fo->offset;
3140 for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3143 const char *newname;
3147 newindex = VEC_length (varinfo_t, varmap);
3148 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (field));
3149 newname = ggc_strdup (tempname);
3151 newvi = new_var_info (decl, newindex, newname, newindex);
3152 newvi->offset = fo->offset;
3153 newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
3154 newvi->fullsize = vi->fullsize;
3155 insert_into_field_list (vi, newvi);
3156 VEC_safe_push (varinfo_t, heap, varmap, newvi);
3158 make_constraint_to_anything (newvi);
3162 VEC_free (fieldoff_s, heap, fieldstack);
3167 /* Print out the points-to solution for VAR to FILE. */
3170 dump_solution_for_var (FILE *file, unsigned int var)
3172 varinfo_t vi = get_varinfo (var);
3176 fprintf (file, "%s = { ", vi->name);
3177 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
3179 fprintf (file, "%s ", get_varinfo (i)->name);
3181 fprintf (file, "}\n");
3184 /* Print the points-to solution for VAR to stdout. */
3187 debug_solution_for_var (unsigned int var)
3189 dump_solution_for_var (stdout, var);
3193 /* Create varinfo structures for all of the variables in the
3194 function for intraprocedural mode. */
3197 intra_create_variable_infos (void)
3201 /* For each incoming argument arg, ARG = &ANYTHING */
3202 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
3204 struct constraint_expr lhs;
3205 struct constraint_expr rhs;
3210 lhs.var = create_variable_info_for (t, alias_get_name (t));
3212 rhs.var = anything_id;
3213 rhs.type = ADDRESSOF;
3216 for (p = get_varinfo (lhs.var); p; p = p->next)
3218 struct constraint_expr temp = lhs;
3220 process_constraint (new_constraint (temp, rhs));
3226 /* Set bits in INTO corresponding to the variable uids in solution set
3230 set_uids_in_ptset (bitmap into, bitmap from)
3234 bool found_anyoffset = false;
3237 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
3239 varinfo_t vi = get_varinfo (i);
3241 /* If we find ANYOFFSET in the solution and the solution
3242 includes SFTs for some structure, then all the SFTs in that
3243 structure will need to be added to the alias set. */
3244 if (vi->id == anyoffset_id)
3246 found_anyoffset = true;
3250 /* The only artificial variables that are allowed in a may-alias
3251 set are heap variables. */
3252 if (vi->is_artificial_var && !vi->is_heap_var)
3255 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
3257 /* Variables containing unions may need to be converted to
3258 their SFT's, because SFT's can have unions and we cannot. */
3259 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
3260 bitmap_set_bit (into, DECL_UID (sv->var));
3262 else if (TREE_CODE (vi->decl) == VAR_DECL
3263 || TREE_CODE (vi->decl) == PARM_DECL)
3266 && var_can_have_subvars (vi->decl)
3267 && get_subvars_for_var (vi->decl))
3269 /* If ANYOFFSET is in the solution set and VI->DECL is
3270 an aggregate variable with sub-variables, then any of
3271 the SFTs inside VI->DECL may have been accessed. Add
3272 all the sub-vars for VI->DECL. */
3273 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
3274 bitmap_set_bit (into, DECL_UID (sv->var));
3276 else if (var_can_have_subvars (vi->decl)
3277 && get_subvars_for_var (vi->decl))
3279 /* If VI->DECL is an aggregate for which we created
3280 SFTs, add the SFT corresponding to VI->OFFSET. */
3281 tree sft = get_subvar_at (vi->decl, vi->offset);
3282 bitmap_set_bit (into, DECL_UID (sft));
3286 /* Otherwise, just add VI->DECL to the alias set. */
3287 bitmap_set_bit (into, DECL_UID (vi->decl));
3294 static bool have_alias_info = false;
3296 /* Given a pointer variable P, fill in its points-to set, or return
3297 false if we can't. */
3300 find_what_p_points_to (tree p)
3302 unsigned int id = 0;
3304 if (!have_alias_info)
3307 if (lookup_id_for_tree (p, &id))
3309 varinfo_t vi = get_varinfo (id);
3311 if (vi->is_artificial_var)
3314 /* See if this is a field or a structure. */
3315 if (vi->size != vi->fullsize)
3317 /* Nothing currently asks about structure fields directly,
3318 but when they do, we need code here to hand back the
3320 if (!var_can_have_subvars (vi->decl)
3321 || get_subvars_for_var (vi->decl) == NULL)
3326 struct ptr_info_def *pi = get_ptr_info (p);
3330 /* This variable may have been collapsed, let's get the real
3332 vi = get_varinfo (vi->node);
3334 /* Translate artificial variables into SSA_NAME_PTR_INFO
3336 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
3338 varinfo_t vi = get_varinfo (i);
3340 if (vi->is_artificial_var)
3342 /* FIXME. READONLY should be handled better so that
3343 flow insensitive aliasing can disregard writable
3345 if (vi->id == nothing_id)
3347 else if (vi->id == anything_id)
3348 pi->pt_anything = 1;
3349 else if (vi->id == readonly_id)
3350 pi->pt_anything = 1;
3351 else if (vi->id == integer_id)
3352 pi->pt_anything = 1;
3353 else if (vi->is_heap_var)
3354 pi->pt_global_mem = 1;
3358 if (pi->pt_anything)
3362 pi->pt_vars = BITMAP_GGC_ALLOC ();
3364 set_uids_in_ptset (pi->pt_vars, vi->solution);
3366 if (bitmap_empty_p (pi->pt_vars))
3377 /* Initialize things necessary to perform PTA */
3380 init_alias_vars (void)
3382 bitmap_obstack_initialize (&ptabitmap_obstack);
3386 /* Dump points-to information to OUTFILE. */
3389 dump_sa_points_to_info (FILE *outfile)
3393 fprintf (outfile, "\nPoints-to sets\n\n");
3395 if (dump_flags & TDF_STATS)
3397 fprintf (outfile, "Stats:\n");
3398 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
3399 fprintf (outfile, "Statically unified vars: %d\n",
3400 stats.unified_vars_static);
3401 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
3402 fprintf (outfile, "Dynamically unified vars: %d\n",
3403 stats.unified_vars_dynamic);
3404 fprintf (outfile, "Iterations: %d\n", stats.iterations);
3407 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
3408 dump_solution_for_var (outfile, i);
3412 /* Debug points-to information to stderr. */
3415 debug_sa_points_to_info (void)
3417 dump_sa_points_to_info (stderr);
3421 /* Initialize the always-existing constraint variables for NULL
3422 ANYTHING, READONLY, and INTEGER */
3425 init_base_vars (void)
3427 struct constraint_expr lhs, rhs;
3429 /* Create the NULL variable, used to represent that a variable points
3431 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
3432 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
3433 insert_id_for_tree (nothing_tree, 0);
3434 var_nothing->is_artificial_var = 1;
3435 var_nothing->offset = 0;
3436 var_nothing->size = ~0;
3437 var_nothing->fullsize = ~0;
3438 var_nothing->is_special_var = 1;
3440 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
3442 /* Create the ANYTHING variable, used to represent that a variable
3443 points to some unknown piece of memory. */
3444 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
3445 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
3446 insert_id_for_tree (anything_tree, 1);
3447 var_anything->is_artificial_var = 1;
3448 var_anything->size = ~0;
3449 var_anything->offset = 0;
3450 var_anything->next = NULL;
3451 var_anything->fullsize = ~0;
3452 var_anything->is_special_var = 1;
3455 /* Anything points to anything. This makes deref constraints just
3456 work in the presence of linked list and other p = *p type loops,
3457 by saying that *ANYTHING = ANYTHING. */
3458 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
3460 lhs.var = anything_id;
3462 rhs.type = ADDRESSOF;
3463 rhs.var = anything_id;
3465 var_anything->address_taken = true;
3467 /* This specifically does not use process_constraint because
3468 process_constraint ignores all anything = anything constraints, since all
3469 but this one are redundant. */
3470 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
3472 /* Create the READONLY variable, used to represent that a variable
3473 points to readonly memory. */
3474 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
3475 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
3476 var_readonly->is_artificial_var = 1;
3477 var_readonly->offset = 0;
3478 var_readonly->size = ~0;
3479 var_readonly->fullsize = ~0;
3480 var_readonly->next = NULL;
3481 var_readonly->is_special_var = 1;
3482 insert_id_for_tree (readonly_tree, 2);
3484 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
3486 /* readonly memory points to anything, in order to make deref
3487 easier. In reality, it points to anything the particular
3488 readonly variable can point to, but we don't track this
3491 lhs.var = readonly_id;
3493 rhs.type = ADDRESSOF;
3494 rhs.var = anything_id;
3497 process_constraint (new_constraint (lhs, rhs));
3499 /* Create the INTEGER variable, used to represent that a variable points
3501 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
3502 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
3503 insert_id_for_tree (integer_tree, 3);
3504 var_integer->is_artificial_var = 1;
3505 var_integer->size = ~0;
3506 var_integer->fullsize = ~0;
3507 var_integer->offset = 0;
3508 var_integer->next = NULL;
3509 var_integer->is_special_var = 1;
3511 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
3513 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
3514 integer will point to. */
3516 lhs.var = integer_id;
3518 rhs.type = ADDRESSOF;
3519 rhs.var = anything_id;
3521 process_constraint (new_constraint (lhs, rhs));
3523 /* Create the ANYOFFSET variable, used to represent an arbitrary offset
3524 inside an object. This is similar to ANYTHING, but less drastic.
3525 It means that the pointer can point anywhere inside an object,
3526 but not outside of it. */
3527 anyoffset_tree = create_tmp_var_raw (void_type_node, "ANYOFFSET");
3529 var_anyoffset = new_var_info (anyoffset_tree, anyoffset_id, "ANYOFFSET",
3531 insert_id_for_tree (anyoffset_tree, anyoffset_id);
3532 var_anyoffset->is_artificial_var = 1;
3533 var_anyoffset->size = ~0;
3534 var_anyoffset->offset = 0;
3535 var_anyoffset->next = NULL;
3536 var_anyoffset->fullsize = ~0;
3537 var_anyoffset->is_special_var = 1;
3538 VEC_safe_push (varinfo_t, heap, varmap, var_anyoffset);
3540 /* ANYOFFSET points to ANYOFFSET. */
3542 lhs.var = anyoffset_id;
3544 rhs.type = ADDRESSOF;
3545 rhs.var = anyoffset_id;
3547 process_constraint (new_constraint (lhs, rhs));
3550 /* Return true if we actually need to solve the constraint graph in order to
3551 get our points-to sets. This is false when, for example, no addresses are
3552 taken other than special vars, or all points-to sets with members already
3553 contain the anything variable and there are no predecessors for other
3557 need_to_solve (void)
3561 bool found_address_taken = false;
3562 bool found_non_anything = false;
3564 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
3566 if (v->is_special_var)
3569 if (v->address_taken)
3570 found_address_taken = true;
3573 && !bitmap_empty_p (v->solution)
3574 && !bitmap_bit_p (v->solution, anything_id))
3575 found_non_anything = true;
3576 else if (bitmap_empty_p (v->solution)
3577 && VEC_length (constraint_edge_t, graph->preds[v->id]) != 0)
3578 found_non_anything = true;
3580 if (found_address_taken && found_non_anything)
3587 /* Create points-to sets for the current function. See the comments
3588 at the start of the file for an algorithmic overview. */
3591 compute_points_to_sets (struct alias_info *ai)
3595 timevar_push (TV_TREE_PTA);
3599 constraint_pool = create_alloc_pool ("Constraint pool",
3600 sizeof (struct constraint), 30);
3601 variable_info_pool = create_alloc_pool ("Variable info pool",
3602 sizeof (struct variable_info), 30);
3603 constraint_edge_pool = create_alloc_pool ("Constraint edges",
3604 sizeof (struct constraint_edge), 30);
3606 constraints = VEC_alloc (constraint_t, heap, 8);
3607 varmap = VEC_alloc (varinfo_t, heap, 8);
3608 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
3609 memset (&stats, 0, sizeof (stats));
3613 intra_create_variable_infos ();
3615 /* Now walk all statements and derive aliases. */
3618 block_stmt_iterator bsi;
3621 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3622 if (is_gimple_reg (PHI_RESULT (phi)))
3623 find_func_aliases (phi, ai);
3625 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3626 find_func_aliases (bsi_stmt (bsi), ai);
3629 build_constraint_graph ();
3633 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
3634 dump_constraints (dump_file);
3637 if (need_to_solve ())
3640 fprintf (dump_file, "\nCollapsing static cycles and doing variable "
3643 find_and_collapse_graph_cycles (graph, false);
3644 perform_var_substitution (graph);
3647 fprintf (dump_file, "\nSolving graph:\n");
3649 solve_graph (graph);
3653 dump_sa_points_to_info (dump_file);
3655 have_alias_info = true;
3657 timevar_pop (TV_TREE_PTA);
3661 /* Delete created points-to sets. */
3664 delete_points_to_sets (void)
3669 htab_delete (id_for_tree);
3670 bitmap_obstack_release (&ptabitmap_obstack);
3671 VEC_free (constraint_t, heap, constraints);
3673 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
3675 VEC_free (constraint_edge_t, heap, graph->succs[i]);
3676 VEC_free (constraint_edge_t, heap, graph->preds[i]);
3677 VEC_free (constraint_t, heap, v->complex);
3679 free (graph->succs);
3680 free (graph->preds);
3683 VEC_free (varinfo_t, heap, varmap);
3684 free_alloc_pool (variable_info_pool);
3685 free_alloc_pool (constraint_pool);
3686 free_alloc_pool (constraint_edge_pool);
3688 have_alias_info = false;