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"
29 #include "tree-ssa-structalias.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
38 #include "diagnostic.h"
41 #include "tree-flow.h"
42 #include "tree-inline.h"
45 #include "tree-gimple.h"
49 #include "tree-pass.h"
51 #include "alloc-pool.h"
52 #include "splay-tree.h"
54 /* The idea behind this analyzer is to generate set constraints from the
55 program, then solve the resulting constraints in order to generate the
58 Set constraints are a way of modeling program analysis problems that
59 involve sets. They consist of an inclusion constraint language,
60 describing the variables (each variable is a set) and operations that
61 are involved on the variables, and a set of rules that derive facts
62 from these operations. To solve a system of set constraints, you derive
63 all possible facts under the rules, which gives you the correct sets
66 See "Efficient Field-sensitive pointer analysis for C" by "David
67 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
68 http://citeseer.ist.psu.edu/pearce04efficient.html
70 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
71 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
72 http://citeseer.ist.psu.edu/heintze01ultrafast.html
74 There are three types of constraint expressions, DEREF, ADDRESSOF, and
75 SCALAR. Each constraint expression consists of a constraint type,
76 a variable, and an offset.
78 SCALAR is a constraint expression type used to represent x, whether
79 it appears on the LHS or the RHS of a statement.
80 DEREF is a constraint expression type used to represent *x, whether
81 it appears on the LHS or the RHS of a statement.
82 ADDRESSOF is a constraint expression used to represent &x, whether
83 it appears on the LHS or the RHS of a statement.
85 Each pointer variable in the program is assigned an integer id, and
86 each field of a structure variable is assigned an integer id as well.
88 Structure variables are linked to their list of fields through a "next
89 field" in each variable that points to the next field in offset
91 Each variable for a structure field has
93 1. "size", that tells the size in bits of that field.
94 2. "fullsize, that tells the size in bits of the entire structure.
95 3. "offset", that tells the offset in bits from the beginning of the
96 structure to this field.
108 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
109 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
110 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
113 In order to solve the system of set constraints, the following is
116 1. Each constraint variable x has a solution set associated with it,
119 2. Constraints are separated into direct, copy, and complex.
120 Direct constraints are ADDRESSOF constraints that require no extra
121 processing, such as P = &Q
122 Copy constraints are those of the form P = Q.
123 Complex constraints are all the constraints involving dereferences.
125 3. All direct constraints of the form P = &Q are processed, such
126 that Q is added to Sol(P)
128 4. All complex constraints for a given constraint variable are stored in a
129 linked list attached to that variable's node.
131 5. A directed graph is built out of the copy constraints. Each
132 constraint variable is a node in the graph, and an edge from
133 Q to P is added for each copy constraint of the form P = Q
135 6. The graph is then walked, and solution sets are
136 propagated along the copy edges, such that an edge from Q to P
137 causes Sol(P) <- Sol(P) union Sol(Q).
139 7. As we visit each node, all complex constraints associated with
140 that node are processed by adding appropriate copy edges to the graph, or the
141 appropriate variables to the solution set.
143 8. The process of walking the graph is iterated until no solution
146 Prior to walking the graph in steps 6 and 7, We perform static
147 cycle elimination on the constraint graph, as well
148 as off-line variable substitution.
150 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
151 on and turned into anything), but isn't. You can just see what offset
152 inside the pointed-to struct it's going to access.
154 TODO: Constant bounded arrays can be handled as if they were structs of the
155 same number of elements.
157 TODO: Modeling heap and incoming pointers becomes much better if we
158 add fields to them as we discover them, which we could do.
160 TODO: We could handle unions, but to be honest, it's probably not
161 worth the pain or slowdown. */
163 static bool use_field_sensitive = true;
164 static unsigned int create_variable_info_for (tree, const char *);
165 static struct constraint_expr get_constraint_for (tree);
166 static void build_constraint_graph (void);
168 static bitmap_obstack ptabitmap_obstack;
169 static bitmap_obstack iteration_obstack;
170 DEF_VEC_P(constraint_t);
171 DEF_VEC_ALLOC_P(constraint_t,gc);
173 static struct constraint_stats
175 unsigned int total_vars;
176 unsigned int collapsed_vars;
177 unsigned int unified_vars_static;
178 unsigned int unified_vars_dynamic;
179 unsigned int iterations;
184 /* ID of this variable */
187 /* Name of this variable */
190 /* Tree that this variable is associated with. */
193 /* Offset of this variable, in bits, from the base variable */
194 unsigned HOST_WIDE_INT offset;
196 /* Size of the variable, in bits. */
197 unsigned HOST_WIDE_INT size;
199 /* Full size of the base variable, in bits. */
200 unsigned HOST_WIDE_INT fullsize;
202 /* A link to the variable for the next field in this structure. */
203 struct variable_info *next;
205 /* Node in the graph that represents the constraints and points-to
206 solution for the variable. */
209 /* True if the address of this variable is taken. Needed for
210 variable substitution. */
211 unsigned int address_taken:1;
213 /* True if this variable is the target of a dereference. Needed for
214 variable substitution. */
215 unsigned int indirect_target:1;
217 /* True if this is a variable created by the constraint analysis, such as
218 heap variables and constraints we had to break up. */
219 unsigned int is_artificial_var:1;
221 /* True for variables whose size is not known or variable. */
222 unsigned int is_unknown_size_var:1;
224 /* True for variables that have unions somewhere in them. */
225 unsigned int has_union:1;
227 /* Points-to set for this variable. */
230 /* Variable ids represented by this node. */
233 /* Vector of complex constraints for this node. Complex
234 constraints are those involving dereferences. */
235 VEC(constraint_t,gc) *complex;
237 typedef struct variable_info *varinfo_t;
239 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
241 /* Pool of variable info structures. */
242 static alloc_pool variable_info_pool;
244 DEF_VEC_P(varinfo_t);
246 DEF_VEC_ALLOC_P(varinfo_t, gc);
248 /* Table of variable info structures for constraint variables. Indexed directly
249 by variable info id. */
250 static VEC(varinfo_t,gc) *varmap;
251 #define get_varinfo(n) VEC_index(varinfo_t, varmap, n)
253 /* Variable that represents the unknown pointer. */
254 static varinfo_t var_anything;
255 static tree anything_tree;
256 static unsigned int anything_id;
258 /* Variable that represents the NULL pointer. */
259 static varinfo_t var_nothing;
260 static tree nothing_tree;
261 static unsigned int nothing_id;
263 /* Variable that represents read only memory. */
264 static varinfo_t var_readonly;
265 static tree readonly_tree;
266 static unsigned int readonly_id;
268 /* Variable that represents integers. This is used for when people do things
270 static varinfo_t var_integer;
271 static tree integer_tree;
272 static unsigned int integer_id;
275 /* Return a new variable info structure consisting for a variable
276 named NAME, and using constraint graph node NODE. */
279 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
281 varinfo_t ret = pool_alloc (variable_info_pool);
287 ret->address_taken = false;
288 ret->indirect_target = false;
289 ret->is_artificial_var = false;
290 ret->is_unknown_size_var = false;
291 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
292 bitmap_clear (ret->solution);
293 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
294 bitmap_clear (ret->variables);
300 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
302 /* An expression that appears in a constraint. */
304 struct constraint_expr
306 /* Constraint type. */
307 constraint_expr_type type;
309 /* Variable we are referring to in the constraint. */
312 /* Offset, in bits, of this constraint from the beginning of
313 variables it ends up referring to.
315 IOW, in a deref constraint, we would deref, get the result set,
316 then add OFFSET to each member. */
317 unsigned HOST_WIDE_INT offset;
320 static struct constraint_expr do_deref (struct constraint_expr);
322 /* Our set constraints are made up of two constraint expressions, one
325 As described in the introduction, our set constraints each represent an
326 operation between set valued variables.
330 struct constraint_expr lhs;
331 struct constraint_expr rhs;
334 /* List of constraints that we use to build the constraint graph from. */
336 static VEC(constraint_t,gc) *constraints;
337 static alloc_pool constraint_pool;
339 /* An edge in the constraint graph. We technically have no use for
340 the src, since it will always be the same node that we are indexing
341 into the pred/succ arrays with, but it's nice for checking
342 purposes. The edges are weighted, with a bit set in weights for
343 each edge from src to dest with that weight. */
345 struct constraint_edge
352 typedef struct constraint_edge *constraint_edge_t;
353 static alloc_pool constraint_edge_pool;
355 /* Return a new constraint edge from SRC to DEST. */
357 static constraint_edge_t
358 new_constraint_edge (unsigned int src, unsigned int dest)
360 constraint_edge_t ret = pool_alloc (constraint_edge_pool);
367 DEF_VEC_P(constraint_edge_t);
368 DEF_VEC_ALLOC_P(constraint_edge_t,gc);
371 /* The constraint graph is simply a set of adjacency vectors, one per
372 variable. succs[x] is the vector of successors for variable x, and preds[x]
373 is the vector of predecessors for variable x.
374 IOW, all edges are "forward" edges, which is not like our CFG.
376 preds[x]->src == x, and
379 struct constraint_graph
381 VEC(constraint_edge_t,gc) **succs;
382 VEC(constraint_edge_t,gc) **preds;
385 typedef struct constraint_graph *constraint_graph_t;
387 static constraint_graph_t graph;
389 /* Create a new constraint consisting of LHS and RHS expressions. */
392 new_constraint (const struct constraint_expr lhs,
393 const struct constraint_expr rhs)
395 constraint_t ret = pool_alloc (constraint_pool);
401 /* Print out constraint C to FILE. */
404 dump_constraint (FILE *file, constraint_t c)
406 if (c->lhs.type == ADDRESSOF)
408 else if (c->lhs.type == DEREF)
410 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
411 if (c->lhs.offset != 0)
412 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
413 fprintf (file, " = ");
414 if (c->rhs.type == ADDRESSOF)
416 else if (c->rhs.type == DEREF)
418 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
419 if (c->rhs.offset != 0)
420 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
421 fprintf (file, "\n");
424 /* Print out constraint C to stderr. */
427 debug_constraint (constraint_t c)
429 dump_constraint (stderr, c);
432 /* Print out all constraints to FILE */
435 dump_constraints (FILE *file)
439 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
440 dump_constraint (file, c);
443 /* Print out all constraints to stderr. */
446 debug_constraints (void)
448 dump_constraints (stderr);
453 The solver is a simple worklist solver, that works on the following
456 sbitmap changed_nodes = all ones;
457 changed_count = number of nodes;
458 For each node that was already collapsed:
462 while (changed_count > 0)
464 compute topological ordering for constraint graph
466 find and collapse cycles in the constraint graph (updating
467 changed if necessary)
469 for each node (n) in the graph in topological order:
472 Process each complex constraint associated with the node,
473 updating changed if necessary.
475 For each outgoing edge from n, propagate the solution from n to
476 the destination of the edge, updating changed as necessary.
480 /* Return true if two constraint expressions A and B are equal. */
483 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
485 return a.type == b.type
487 && a.offset == b.offset;
490 /* Return true if constraint expression A is less than constraint expression
491 B. This is just arbitrary, but consistent, in order to give them an
495 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
497 if (a.type == b.type)
500 return a.offset < b.offset;
502 return a.var < b.var;
505 return a.type < b.type;
508 /* Return true if constraint A is less than constraint B. This is just
509 arbitrary, but consistent, in order to give them an ordering. */
512 constraint_less (const constraint_t a, const constraint_t b)
514 if (constraint_expr_less (a->lhs, b->lhs))
516 else if (constraint_expr_less (b->lhs, a->lhs))
519 return constraint_expr_less (a->rhs, b->rhs);
522 /* Return true if two constraints A and B are equal. */
525 constraint_equal (struct constraint a, struct constraint b)
527 return constraint_expr_equal (a.lhs, b.lhs)
528 && constraint_expr_equal (a.rhs, b.rhs);
532 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
535 constraint_vec_find (VEC(constraint_t,gc) *vec,
536 struct constraint lookfor)
544 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
545 if (place >= VEC_length (constraint_t, vec))
547 found = VEC_index (constraint_t, vec, place);
548 if (!constraint_equal (*found, lookfor))
553 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
556 constraint_set_union (VEC(constraint_t,gc) **to,
557 VEC(constraint_t,gc) **from)
562 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
564 if (constraint_vec_find (*to, *c) == NULL)
566 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
568 VEC_safe_insert (constraint_t, gc, *to, place, c);
573 /* Take a solution set SET, add OFFSET to each member of the set, and
574 overwrite SET with the result when done. */
577 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
579 bitmap result = BITMAP_ALLOC (&iteration_obstack);
583 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
585 /* If this is a properly sized variable, only add offset if it's
586 less than end. Otherwise, it is globbed to a single
589 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
591 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
592 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
593 bitmap_set_bit (result, v->id);
595 else if (get_varinfo (i)->is_artificial_var
596 || get_varinfo (i)->is_unknown_size_var)
598 bitmap_set_bit (result, i);
602 bitmap_copy (set, result);
603 BITMAP_FREE (result);
606 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
610 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
613 return bitmap_ior_into (to, from);
619 tmp = BITMAP_ALLOC (&iteration_obstack);
620 bitmap_copy (tmp, from);
621 solution_set_add (tmp, inc);
622 res = bitmap_ior_into (to, tmp);
628 /* Insert constraint C into the list of complex constraints for VAR. */
631 insert_into_complex (unsigned int var, constraint_t c)
633 varinfo_t vi = get_varinfo (var);
634 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
636 VEC_safe_insert (constraint_t, gc, vi->complex, place, c);
640 /* Compare two constraint edges A and B, return true if they are equal. */
643 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
645 return a.src == b.src && a.dest == b.dest;
648 /* Compare two constraint edges, return true if A is less than B */
651 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
653 if (a->dest < b->dest)
655 else if (a->dest == b->dest)
656 return a->src < b->src;
661 /* Find the constraint edge that matches LOOKFOR, in VEC.
662 Return the edge, if found, NULL otherwise. */
664 static constraint_edge_t
665 constraint_edge_vec_find (VEC(constraint_edge_t,gc) *vec,
666 struct constraint_edge lookfor)
669 constraint_edge_t edge;
671 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
672 constraint_edge_less);
673 edge = VEC_index (constraint_edge_t, vec, place);
674 if (!constraint_edge_equal (*edge, lookfor))
679 /* Condense two variable nodes into a single variable node, by moving
680 all associated info from SRC to TO. */
683 condense_varmap_nodes (unsigned int to, unsigned int src)
685 varinfo_t tovi = get_varinfo (to);
686 varinfo_t srcvi = get_varinfo (src);
691 /* the src node, and all its variables, are now the to node. */
693 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
694 get_varinfo (i)->node = to;
696 /* Merge the src node variables and the to node variables. */
697 bitmap_set_bit (tovi->variables, src);
698 bitmap_ior_into (tovi->variables, srcvi->variables);
699 bitmap_clear (srcvi->variables);
701 /* Move all complex constraints from src node into to node */
702 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
704 /* In complex constraints for node src, we may have either
705 a = *src, and *src = a. */
707 if (c->rhs.type == DEREF)
712 constraint_set_union (&tovi->complex, &srcvi->complex);
713 srcvi->complex = NULL;
716 /* Erase EDGE from GRAPH. This routine only handles self-edges
717 (e.g. an edge from a to a). */
720 erase_graph_self_edge (constraint_graph_t graph, struct constraint_edge edge)
722 VEC(constraint_edge_t,gc) *predvec = graph->preds[edge.src];
723 VEC(constraint_edge_t,gc) *succvec = graph->succs[edge.dest];
725 gcc_assert (edge.src == edge.dest);
727 /* Remove from the successors. */
728 place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
729 constraint_edge_less);
731 /* Make sure we found the edge. */
732 #ifdef ENABLE_CHECKING
734 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
735 gcc_assert (constraint_edge_equal (*tmp, edge));
738 VEC_ordered_remove (constraint_edge_t, succvec, place);
740 /* Remove from the predecessors. */
741 place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
742 constraint_edge_less);
744 /* Make sure we found the edge. */
745 #ifdef ENABLE_CHECKING
747 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
748 gcc_assert (constraint_edge_equal (*tmp, edge));
751 VEC_ordered_remove (constraint_edge_t, predvec, place);
754 /* Remove edges involving NODE from GRAPH. */
757 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
759 VEC(constraint_edge_t,gc) *succvec = graph->succs[node];
760 VEC(constraint_edge_t,gc) *predvec = graph->preds[node];
764 /* Walk the successors, erase the associated preds. */
765 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
769 struct constraint_edge lookfor;
770 lookfor.src = c->dest;
772 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
773 &lookfor, constraint_edge_less);
774 VEC_ordered_remove (constraint_edge_t, graph->preds[c->dest], place);
776 /* Walk the preds, erase the associated succs. */
777 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
781 struct constraint_edge lookfor;
782 lookfor.src = c->dest;
784 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
785 &lookfor, constraint_edge_less);
786 VEC_ordered_remove (constraint_edge_t, graph->succs[c->dest], place);
789 graph->preds[node] = NULL;
790 graph->succs[node] = NULL;
793 static bool edge_added = false;
795 /* Add edge NEWE to the graph. */
798 add_graph_edge (constraint_graph_t graph, struct constraint_edge newe)
801 unsigned int src = newe.src;
802 unsigned int dest = newe.dest;
803 VEC(constraint_edge_t,gc) *vec;
805 vec = graph->preds[src];
806 place = VEC_lower_bound (constraint_edge_t, vec, &newe,
807 constraint_edge_less);
808 if (place == VEC_length (constraint_edge_t, vec)
809 || VEC_index (constraint_edge_t, vec, place)->dest != dest)
811 constraint_edge_t edge = new_constraint_edge (src, dest);
814 weightbitmap = BITMAP_ALLOC (&ptabitmap_obstack);
815 edge->weights = weightbitmap;
816 VEC_safe_insert (constraint_edge_t, gc, graph->preds[edge->src],
818 edge = new_constraint_edge (dest, src);
819 edge->weights = weightbitmap;
820 place = VEC_lower_bound (constraint_edge_t, graph->succs[edge->src],
821 edge, constraint_edge_less);
822 VEC_safe_insert (constraint_edge_t, gc, graph->succs[edge->src],
832 /* Return the bitmap representing the weights of edge LOOKFOR */
835 get_graph_weights (constraint_graph_t graph, struct constraint_edge lookfor)
837 constraint_edge_t edge;
838 unsigned int src = lookfor.src;
839 VEC(constraint_edge_t,gc) *vec;
840 vec = graph->preds[src];
841 edge = constraint_edge_vec_find (vec, lookfor);
842 gcc_assert (edge != NULL);
843 return edge->weights;
847 /* Merge GRAPH nodes FROM and TO into node TO. */
850 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
853 VEC(constraint_edge_t,gc) *succvec = graph->succs[from];
854 VEC(constraint_edge_t,gc) *predvec = graph->preds[from];
858 /* Merge all the predecessor edges. */
860 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
862 unsigned int d = c->dest;
863 struct constraint_edge olde;
864 struct constraint_edge newe;
871 add_graph_edge (graph, newe);
874 temp = get_graph_weights (graph, olde);
875 weights = get_graph_weights (graph, newe);
876 bitmap_ior_into (weights, temp);
879 /* Merge all the successor edges. */
880 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
882 unsigned int d = c->dest;
883 struct constraint_edge olde;
884 struct constraint_edge newe;
891 add_graph_edge (graph, newe);
894 temp = get_graph_weights (graph, olde);
895 weights = get_graph_weights (graph, newe);
896 bitmap_ior_into (weights, temp);
898 clear_edges_for_node (graph, from);
901 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
902 it doesn't exist in the graph already.
903 Return false if the edge already existed, true otherwise. */
906 int_add_graph_edge (constraint_graph_t graph, unsigned int to,
907 unsigned int from, unsigned HOST_WIDE_INT weight)
909 if (to == from && weight == 0)
916 struct constraint_edge edge;
919 r = add_graph_edge (graph, edge);
920 r |= !bitmap_bit_p (get_graph_weights (graph, edge), weight);
921 bitmap_set_bit (get_graph_weights (graph, edge), weight);
927 /* Return true if LOOKFOR is an existing graph edge. */
930 valid_graph_edge (constraint_graph_t graph, struct constraint_edge lookfor)
932 return constraint_edge_vec_find (graph->preds[lookfor.src], lookfor) != NULL;
936 /* Build the constraint graph. */
939 build_constraint_graph (void)
944 graph = ggc_alloc (sizeof (struct constraint_graph));
945 graph->succs = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->succs));
946 graph->preds = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->preds));
947 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
949 struct constraint_expr lhs = c->lhs;
950 struct constraint_expr rhs = c->rhs;
951 if (lhs.type == DEREF)
953 /* *x = y or *x = &y (complex) */
954 if (rhs.type == ADDRESSOF || rhs.var > anything_id)
955 insert_into_complex (lhs.var, c);
957 else if (rhs.type == DEREF)
960 if (lhs.var > anything_id)
961 insert_into_complex (rhs.var, c);
963 else if (rhs.type == ADDRESSOF)
966 bitmap_set_bit (get_varinfo (lhs.var)->solution, rhs.var);
968 else if (rhs.var > anything_id && lhs.var > anything_id)
970 /* Ignore 0 weighted self edges, as they can't possibly contribute
972 if (lhs.var != rhs.var || rhs.offset != 0 || lhs.offset != 0)
975 struct constraint_edge edge;
979 add_graph_edge (graph, edge);
980 bitmap_set_bit (get_graph_weights (graph, edge),
987 /* Changed variables on the last iteration. */
988 static unsigned int changed_count;
989 static sbitmap changed;
992 DEF_VEC_ALLOC_I(unsigned,heap);
995 /* Strongly Connected Component visitation info. */
1000 sbitmap in_component;
1002 unsigned int *visited_index;
1003 VEC(unsigned,heap) *scc_stack;
1004 VEC(unsigned,heap) *unification_queue;
1008 /* Recursive routine to find strongly connected components in GRAPH.
1009 SI is the SCC info to store the information in, and N is the id of current
1010 graph node we are processing.
1012 This is Tarjan's strongly connected component finding algorithm, as
1013 modified by Nuutila to keep only non-root nodes on the stack.
1014 The algorithm can be found in "On finding the strongly connected
1015 connected components in a directed graph" by Esko Nuutila and Eljas
1016 Soisalon-Soininen, in Information Processing Letters volume 49,
1017 number 1, pages 9-14. */
1020 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1022 constraint_edge_t c;
1025 gcc_assert (get_varinfo (n)->node == n);
1026 SET_BIT (si->visited, n);
1027 RESET_BIT (si->in_component, n);
1028 si->visited_index[n] = si->current_index ++;
1030 /* Visit all the successors. */
1031 for (i = 0; VEC_iterate (constraint_edge_t, graph->succs[n], i, c); i++)
1033 /* We only want to find and collapse the zero weight edges. */
1034 if (bitmap_bit_p (c->weights, 0))
1036 unsigned int w = c->dest;
1037 if (!TEST_BIT (si->visited, w))
1038 scc_visit (graph, si, w);
1039 if (!TEST_BIT (si->in_component, w))
1041 unsigned int t = get_varinfo (w)->node;
1042 unsigned int nnode = get_varinfo (n)->node;
1043 if (si->visited_index[t] < si->visited_index[nnode])
1044 get_varinfo (n)->node = t;
1049 /* See if any components have been identified. */
1050 if (get_varinfo (n)->node == n)
1052 unsigned int t = si->visited_index[n];
1053 SET_BIT (si->in_component, n);
1054 while (VEC_length (unsigned, si->scc_stack) != 0
1055 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1057 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1058 get_varinfo (w)->node = n;
1059 SET_BIT (si->in_component, w);
1060 /* Mark this node for collapsing. */
1061 VEC_safe_push (unsigned, heap, si->unification_queue, w);
1065 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1069 /* Collapse two variables into one variable. */
1072 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1074 bitmap tosol, fromsol;
1075 struct constraint_edge edge;
1078 condense_varmap_nodes (to, from);
1079 tosol = get_varinfo (to)->solution;
1080 fromsol = get_varinfo (from)->solution;
1081 bitmap_ior_into (tosol, fromsol);
1082 merge_graph_nodes (graph, to, from);
1085 if (valid_graph_edge (graph, edge))
1087 bitmap weights = get_graph_weights (graph, edge);
1088 bitmap_clear_bit (weights, 0);
1089 if (bitmap_empty_p (weights))
1090 erase_graph_self_edge (graph, edge);
1092 bitmap_clear (fromsol);
1093 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1094 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1098 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1099 SI is the Strongly Connected Components information structure that tells us
1100 what components to unify.
1101 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1102 count should be updated to reflect the unification. */
1105 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1106 bool update_changed)
1109 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1112 /* We proceed as follows:
1114 For each component in the queue (components are delineated by
1115 when current_queue_element->node != next_queue_element->node):
1117 rep = representative node for component
1119 For each node (tounify) to be unified in the component,
1120 merge the solution for tounify into tmp bitmap
1122 clear solution for tounify
1124 merge edges from tounify into rep
1126 merge complex constraints from tounify into rep
1128 update changed count to note that tounify will never change
1131 Merge tmp into solution for rep, marking rep changed if this
1132 changed rep's solution.
1134 Delete any 0 weighted self-edges we now have for rep. */
1135 while (i != VEC_length (unsigned, si->unification_queue))
1137 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1138 unsigned int n = get_varinfo (tounify)->node;
1140 if (dump_file && (dump_flags & TDF_DETAILS))
1141 fprintf (dump_file, "Unifying %s to %s\n",
1142 get_varinfo (tounify)->name,
1143 get_varinfo (n)->name);
1145 stats.unified_vars_dynamic++;
1147 stats.unified_vars_static++;
1148 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1149 merge_graph_nodes (graph, n, tounify);
1150 condense_varmap_nodes (n, tounify);
1152 if (update_changed && TEST_BIT (changed, tounify))
1154 RESET_BIT (changed, tounify);
1155 if (!TEST_BIT (changed, n))
1156 SET_BIT (changed, n);
1159 gcc_assert (changed_count > 0);
1164 bitmap_clear (get_varinfo (tounify)->solution);
1167 /* If we've either finished processing the entire queue, or
1168 finished processing all nodes for component n, update the solution for
1170 if (i == VEC_length (unsigned, si->unification_queue)
1171 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1173 struct constraint_edge edge;
1175 /* If the solution changes because of the merging, we need to mark
1176 the variable as changed. */
1177 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1179 if (update_changed && !TEST_BIT (changed, n))
1181 SET_BIT (changed, n);
1188 if (valid_graph_edge (graph, edge))
1190 bitmap weights = get_graph_weights (graph, edge);
1191 bitmap_clear_bit (weights, 0);
1192 if (bitmap_empty_p (weights))
1193 erase_graph_self_edge (graph, edge);
1201 /* Information needed to compute the topological ordering of a graph. */
1205 /* sbitmap of visited nodes. */
1207 /* Array that stores the topological order of the graph, *in
1209 VEC(unsigned,heap) *topo_order;
1213 /* Initialize and return a topological info structure. */
1215 static struct topo_info *
1216 init_topo_info (void)
1218 size_t size = VEC_length (varinfo_t, varmap);
1219 struct topo_info *ti = xmalloc (sizeof (struct topo_info));
1220 ti->visited = sbitmap_alloc (size);
1221 sbitmap_zero (ti->visited);
1222 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1227 /* Free the topological sort info pointed to by TI. */
1230 free_topo_info (struct topo_info *ti)
1232 sbitmap_free (ti->visited);
1233 VEC_free (unsigned, heap, ti->topo_order);
1237 /* Visit the graph in topological order, and store the order in the
1238 topo_info structure. */
1241 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1244 VEC(constraint_edge_t,gc) *succs = graph->succs[n];
1245 constraint_edge_t c;
1247 SET_BIT (ti->visited, n);
1248 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1250 if (!TEST_BIT (ti->visited, c->dest))
1251 topo_visit (graph, ti, c->dest);
1253 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1256 /* Return true if variable N + OFFSET is a legal field of N. */
1259 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1261 varinfo_t ninfo = get_varinfo (n);
1263 /* For things we've globbed to single variables, any offset into the
1264 variable acts like the entire variable, so that it becomes offset
1266 if (n == anything_id
1267 || ninfo->is_artificial_var
1268 || ninfo->is_unknown_size_var)
1273 return n > anything_id
1274 && (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1277 /* Process a constraint C that represents *x = &y. */
1280 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1281 constraint_t c, bitmap delta)
1283 unsigned int rhs = c->rhs.var;
1284 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1288 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1289 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1291 if (type_safe (j, &offset))
1293 /* *x != NULL && *x != ANYTHING*/
1297 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1298 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1300 sol = get_varinfo (t)->solution;
1301 if (!bitmap_bit_p (sol, rhs))
1303 bitmap_set_bit (sol, rhs);
1304 if (!TEST_BIT (changed, t))
1306 SET_BIT (changed, t);
1312 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1317 /* Process a constraint C that represents x = *y, using DELTA as the
1318 starting solution. */
1321 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1324 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1325 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1327 bitmap sol = get_varinfo (lhs)->solution;
1331 /* For each variable j in delta (Sol(y)), add
1332 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1333 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1335 if (type_safe (j, &roffset))
1338 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1341 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1343 if (int_add_graph_edge (graph, lhs, t, 0))
1344 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1347 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1351 /* If the LHS solution changed, mark the var as changed. */
1354 get_varinfo (lhs)->solution = sol;
1355 if (!TEST_BIT (changed, lhs))
1357 SET_BIT (changed, lhs);
1363 /* Process a constraint C that represents *x = y. */
1366 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1368 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1369 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1370 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1371 bitmap sol = get_varinfo (rhs)->solution;
1375 /* For each member j of delta (Sol(x)), add an edge from y to j and
1376 union Sol(y) into Sol(j) */
1377 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1379 if (type_safe (j, &loff))
1383 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1385 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1387 if (int_add_graph_edge (graph, t, rhs, roff))
1389 bitmap tmp = get_varinfo (t)->solution;
1390 if (set_union_with_increment (tmp, sol, roff))
1392 get_varinfo (t)->solution = tmp;
1395 sol = get_varinfo (rhs)->solution;
1397 if (!TEST_BIT (changed, t))
1399 SET_BIT (changed, t);
1406 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1410 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1411 constraint (IE *x = &y, x = *y, and *x = y). */
1414 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1416 if (c->lhs.type == DEREF)
1418 if (c->rhs.type == ADDRESSOF)
1421 do_da_constraint (graph, c, delta);
1426 do_ds_constraint (graph, c, delta);
1432 do_sd_constraint (graph, c, delta);
1436 /* Initialize and return a new SCC info structure. */
1438 static struct scc_info *
1439 init_scc_info (void)
1441 struct scc_info *si = xmalloc (sizeof (struct scc_info));
1442 size_t size = VEC_length (varinfo_t, varmap);
1444 si->current_index = 0;
1445 si->visited = sbitmap_alloc (size);
1446 sbitmap_zero (si->visited);
1447 si->in_component = sbitmap_alloc (size);
1448 sbitmap_ones (si->in_component);
1449 si->visited_index = xcalloc (sizeof (unsigned int), size + 1);
1450 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1451 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1455 /* Free an SCC info structure pointed to by SI */
1458 free_scc_info (struct scc_info *si)
1460 sbitmap_free (si->visited);
1461 sbitmap_free (si->in_component);
1462 free (si->visited_index);
1463 VEC_free (unsigned, heap, si->scc_stack);
1464 VEC_free (unsigned, heap, si->unification_queue);
1469 /* Find cycles in GRAPH that occur, using strongly connected components, and
1470 collapse the cycles into a single representative node. if UPDATE_CHANGED
1471 is true, then update the changed sbitmap to note those nodes whose
1472 solutions have changed as a result of collapsing. */
1475 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1478 unsigned int size = VEC_length (varinfo_t, varmap);
1479 struct scc_info *si = init_scc_info ();
1481 for (i = 0; i != size; ++i)
1482 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1483 scc_visit (graph, si, i);
1484 process_unification_queue (graph, si, update_changed);
1488 /* Compute a topological ordering for GRAPH, and store the result in the
1489 topo_info structure TI. */
1492 compute_topo_order (constraint_graph_t graph,
1493 struct topo_info *ti)
1496 unsigned int size = VEC_length (varinfo_t, varmap);
1498 for (i = 0; i != size; ++i)
1499 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1500 topo_visit (graph, ti, i);
1503 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1506 bitmap_other_than_zero_bit_set (bitmap b)
1511 if (bitmap_empty_p (b))
1513 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1518 /* Perform offline variable substitution.
1520 This is a linear time way of identifying variables that must have
1521 equivalent points-to sets, including those caused by static cycles,
1522 and single entry subgraphs, in the constraint graph.
1524 The technique is described in "Off-line variable substitution for
1525 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1526 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1529 perform_var_substitution (constraint_graph_t graph)
1531 struct topo_info *ti = init_topo_info ();
1533 /* Compute the topological ordering of the graph, then visit each
1534 node in topological order. */
1535 compute_topo_order (graph, ti);
1537 while (VEC_length (unsigned, ti->topo_order) != 0)
1539 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1541 varinfo_t vi = get_varinfo (i);
1542 bool okay_to_elim = false;
1543 unsigned int root = VEC_length (varinfo_t, varmap);
1544 VEC(constraint_edge_t,gc) *predvec = graph->preds[i];
1545 constraint_edge_t ce;
1548 /* We can't eliminate things whose address is taken, or which is
1549 the target of a dereference. */
1550 if (vi->address_taken || vi->indirect_target)
1553 /* See if all predecessors of I are ripe for elimination */
1554 for (pred = 0; VEC_iterate (constraint_edge_t, predvec, pred, ce); pred++)
1558 weight = get_graph_weights (graph, *ce);
1560 /* We can't eliminate variables that have non-zero weighted
1561 edges between them. */
1562 if (bitmap_other_than_zero_bit_set (weight))
1564 okay_to_elim = false;
1567 w = get_varinfo (ce->dest)->node;
1569 /* We can't eliminate the node if one of the predecessors is
1570 part of a different strongly connected component. */
1574 okay_to_elim = true;
1578 okay_to_elim = false;
1582 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1583 then Solution(i) is a subset of Solution (w), where w is a
1584 predecessor in the graph.
1585 Corollary: If all predecessors of i have the same
1586 points-to set, then i has that same points-to set as
1587 those predecessors. */
1588 tmp = BITMAP_ALLOC (NULL);
1589 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1590 get_varinfo (w)->solution);
1591 if (!bitmap_empty_p (tmp))
1593 okay_to_elim = false;
1600 /* See if the root is different than the original node.
1601 If so, we've found an equivalence. */
1602 if (root != get_varinfo (i)->node && okay_to_elim)
1604 /* Found an equivalence */
1605 get_varinfo (i)->node = root;
1606 collapse_nodes (graph, root, i);
1607 if (dump_file && (dump_flags & TDF_DETAILS))
1608 fprintf (dump_file, "Collapsing %s into %s\n",
1609 get_varinfo (i)->name,
1610 get_varinfo (root)->name);
1611 stats.collapsed_vars++;
1615 free_topo_info (ti);
1619 /* Solve the constraint graph GRAPH using our worklist solver.
1620 This is based on the PW* family of solvers from the "Efficient Field
1621 Sensitive Pointer Analysis for C" paper.
1622 It works by iterating over all the graph nodes, processing the complex
1623 constraints and propagating the copy constraints, until everything stops
1624 changed. This corresponds to steps 6-8 in the solving list given above. */
1627 solve_graph (constraint_graph_t graph)
1629 unsigned int size = VEC_length (varinfo_t, varmap);
1632 changed_count = size;
1633 changed = sbitmap_alloc (size);
1634 sbitmap_ones (changed);
1636 /* The already collapsed/unreachable nodes will never change, so we
1637 need to account for them in changed_count. */
1638 for (i = 0; i < size; i++)
1639 if (get_varinfo (i)->node != i)
1642 while (changed_count > 0)
1645 struct topo_info *ti = init_topo_info ();
1648 bitmap_obstack_initialize (&iteration_obstack);
1652 /* We already did cycle elimination once, when we did
1653 variable substitution, so we don't need it again for the
1655 if (stats.iterations > 1)
1656 find_and_collapse_graph_cycles (graph, true);
1661 compute_topo_order (graph, ti);
1663 while (VEC_length (unsigned, ti->topo_order) != 0)
1665 i = VEC_pop (unsigned, ti->topo_order);
1666 gcc_assert (get_varinfo (i)->node == i);
1668 /* If the node has changed, we need to process the
1669 complex constraints and outgoing edges again. */
1670 if (TEST_BIT (changed, i))
1674 constraint_edge_t e;
1676 VEC(constraint_t,gc) *complex = get_varinfo (i)->complex;
1677 VEC(constraint_edge_t,gc) *succs;
1679 RESET_BIT (changed, i);
1682 /* Process the complex constraints */
1683 solution = get_varinfo (i)->solution;
1684 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
1685 do_complex_constraint (graph, c, solution);
1687 /* Propagate solution to all successors. */
1688 succs = graph->succs[i];
1689 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
1691 bitmap tmp = get_varinfo (e->dest)->solution;
1694 bitmap weights = e->weights;
1697 gcc_assert (!bitmap_empty_p (weights));
1698 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
1699 flag |= set_union_with_increment (tmp, solution, k);
1703 get_varinfo (e->dest)->solution = tmp;
1704 if (!TEST_BIT (changed, e->dest))
1706 SET_BIT (changed, e->dest);
1713 free_topo_info (ti);
1714 bitmap_obstack_release (&iteration_obstack);
1717 sbitmap_free (changed);
1721 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1723 /* Map from trees to variable ids. */
1724 static htab_t id_for_tree;
1726 typedef struct tree_id
1732 /* Hash a tree id structure. */
1735 tree_id_hash (const void *p)
1737 const tree_id_t ta = (tree_id_t) p;
1738 return htab_hash_pointer (ta->t);
1741 /* Return true if the tree in P1 and the tree in P2 are the same. */
1744 tree_id_eq (const void *p1, const void *p2)
1746 const tree_id_t ta1 = (tree_id_t) p1;
1747 const tree_id_t ta2 = (tree_id_t) p2;
1748 return ta1->t == ta2->t;
1751 /* Insert ID as the variable id for tree T in the hashtable. */
1754 insert_id_for_tree (tree t, int id)
1757 struct tree_id finder;
1761 slot = htab_find_slot (id_for_tree, &finder, INSERT);
1762 gcc_assert (*slot == NULL);
1763 new_pair = xmalloc (sizeof (struct tree_id));
1766 *slot = (void *)new_pair;
1769 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1770 exist in the hash table, return false, otherwise, return true and
1771 set *ID to the id we found. */
1774 lookup_id_for_tree (tree t, unsigned int *id)
1777 struct tree_id finder;
1780 pair = htab_find (id_for_tree, &finder);
1787 /* Return a printable name for DECL */
1790 alias_get_name (tree decl)
1792 const char *res = get_name (decl);
1794 int num_printed = 0;
1800 if (TREE_CODE (decl) == SSA_NAME)
1802 num_printed = asprintf (&temp, "%s_%u",
1803 alias_get_name (SSA_NAME_VAR (decl)),
1804 SSA_NAME_VERSION (decl));
1806 else if (DECL_P (decl))
1808 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
1810 if (num_printed > 0)
1812 res = ggc_strdup (temp);
1818 /* Find the variable id for tree T in the hashtable.
1819 If T doesn't exist in the hash table, create an entry for it. */
1822 get_id_for_tree (tree t)
1825 struct tree_id finder;
1828 pair = htab_find (id_for_tree, &finder);
1830 return create_variable_info_for (t, alias_get_name (t));
1835 /* Get a constraint expression from an SSA_VAR_P node. */
1837 static struct constraint_expr
1838 get_constraint_exp_from_ssa_var (tree t)
1840 struct constraint_expr cexpr;
1842 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
1844 /* For parameters, get at the points-to set for the actual parm
1846 if (TREE_CODE (t) == SSA_NAME
1847 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
1848 && default_def (SSA_NAME_VAR (t)) == t)
1849 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
1851 cexpr.type = SCALAR;
1853 if (TREE_READONLY (t))
1855 cexpr.type = ADDRESSOF;
1856 cexpr.var = readonly_id;
1859 cexpr.var = get_id_for_tree (t);
1865 /* Process a completed constraint T, and add it to the constraint
1869 process_constraint (constraint_t t)
1871 struct constraint_expr rhs = t->rhs;
1872 struct constraint_expr lhs = t->lhs;
1874 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
1875 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
1877 /* ANYTHING == ANYTHING is pointless. */
1878 if (lhs.var == anything_id && rhs.var == anything_id)
1881 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1882 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
1887 process_constraint (t);
1889 /* This can happen in our IR with things like n->a = *p */
1890 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
1892 /* Split into tmp = *rhs, *lhs = tmp */
1893 tree rhsdecl = get_varinfo (rhs.var)->decl;
1894 tree pointertype = TREE_TYPE (rhsdecl);
1895 tree pointedtotype = TREE_TYPE (pointertype);
1896 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
1897 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
1899 /* If this is an aggregate of known size, we should have passed
1900 this off to do_structure_copy, and it should have broken it
1902 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
1903 || get_varinfo (rhs.var)->is_unknown_size_var);
1905 process_constraint (new_constraint (tmplhs, rhs));
1906 process_constraint (new_constraint (lhs, tmplhs));
1908 else if (rhs.type == ADDRESSOF)
1911 gcc_assert (rhs.offset == 0);
1913 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
1914 vi->address_taken = true;
1916 VEC_safe_push (constraint_t, gc, constraints, t);
1920 if (lhs.type != DEREF && rhs.type == DEREF)
1921 get_varinfo (lhs.var)->indirect_target = true;
1922 VEC_safe_push (constraint_t, gc, constraints, t);
1927 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1930 static unsigned HOST_WIDE_INT
1931 bitpos_of_field (const tree fdecl)
1934 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
1935 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
1938 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
1939 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
1943 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1944 overlaps with a field at [FIELDPOS, FIELDSIZE] */
1947 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
1948 const unsigned HOST_WIDE_INT fieldsize,
1949 const unsigned HOST_WIDE_INT accesspos,
1950 const unsigned HOST_WIDE_INT accesssize)
1952 if (fieldpos == accesspos && fieldsize == accesssize)
1954 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
1956 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
1962 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1964 static struct constraint_expr
1965 get_constraint_for_component_ref (tree t)
1967 struct constraint_expr result;
1968 HOST_WIDE_INT bitsize;
1969 HOST_WIDE_INT bitpos;
1971 enum machine_mode mode;
1977 result.type = SCALAR;
1980 /* Some people like to do cute things like take the address of
1983 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
1984 forzero = TREE_OPERAND (forzero, 0);
1986 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
1989 result.var = integer_id;
1990 result.type = SCALAR;
1994 t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode,
1995 &unsignedp, &volatilep, false);
1996 result = get_constraint_for (t);
1998 /* This can also happen due to weird offsetof type macros. */
1999 if (TREE_CODE (t) != ADDR_EXPR && result.type == ADDRESSOF)
2000 result.type = SCALAR;
2002 /* If we know where this goes, then yay. Otherwise, booo. */
2004 if (offset == NULL && bitsize != -1)
2006 result.offset = bitpos;
2010 result.var = anything_id;
2014 if (result.type == SCALAR)
2016 /* In languages like C, you can access one past the end of an
2017 array. You aren't allowed to dereference it, so we can
2018 ignore this constraint. When we handle pointer subtraction,
2019 we may have to do something cute here. */
2021 if (result.offset < get_varinfo (result.var)->fullsize)
2023 /* It's also not true that the constraint will actually start at the
2024 right offset, it may start in some padding. We only care about
2025 setting the constraint to the first actual field it touches, so
2028 for (curr = get_varinfo (result.var); curr; curr = curr->next)
2030 if (offset_overlaps_with_access (curr->offset, curr->size,
2031 result.offset, bitsize))
2033 result.var = curr->id;
2038 /* assert that we found *some* field there. The user couldn't be
2039 accessing *only* padding. */
2044 if (dump_file && (dump_flags & TDF_DETAILS))
2045 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2054 /* Dereference the constraint expression CONS, and return the result.
2055 DEREF (ADDRESSOF) = SCALAR
2056 DEREF (SCALAR) = DEREF
2057 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2058 This is needed so that we can handle dereferencing DEREF constraints. */
2060 static struct constraint_expr
2061 do_deref (struct constraint_expr cons)
2063 if (cons.type == SCALAR)
2068 else if (cons.type == ADDRESSOF)
2073 else if (cons.type == DEREF)
2075 tree tmpvar = create_tmp_var_raw (ptr_type_node, "derefmp");
2076 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2077 process_constraint (new_constraint (tmplhs, cons));
2078 cons.var = tmplhs.var;
2085 /* Given a tree T, return the constraint expression for it. */
2087 static struct constraint_expr
2088 get_constraint_for (tree t)
2090 struct constraint_expr temp;
2092 /* x = integer is all glommed to a single variable, which doesn't
2093 point to anything by itself. That is, of course, unless it is an
2094 integer constant being treated as a pointer, in which case, we
2095 will return that this is really the addressof anything. This
2096 happens below, since it will fall into the default case. The only
2097 case we know something about an integer treated like a pointer is
2098 when it is the NULL pointer, and then we just say it points to
2100 if (TREE_CODE (t) == INTEGER_CST
2101 && !POINTER_TYPE_P (TREE_TYPE (t)))
2103 temp.var = integer_id;
2108 else if (TREE_CODE (t) == INTEGER_CST
2109 && integer_zerop (t))
2111 temp.var = nothing_id;
2112 temp.type = ADDRESSOF;
2117 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2119 case tcc_expression:
2121 switch (TREE_CODE (t))
2125 temp = get_constraint_for (TREE_OPERAND (t, 0));
2126 if (temp.type == DEREF)
2129 temp.type = ADDRESSOF;
2135 /* XXX: In interprocedural mode, if we didn't have the
2136 body, we would need to do *each pointer argument =
2138 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2140 tree heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2141 temp.var = create_variable_info_for (heapvar,
2142 alias_get_name (heapvar));
2144 get_varinfo (temp.var)->is_artificial_var = 1;
2145 temp.type = ADDRESSOF;
2152 temp.type = ADDRESSOF;
2153 temp.var = anything_id;
2161 switch (TREE_CODE (t))
2165 temp = get_constraint_for (TREE_OPERAND (t, 0));
2166 temp = do_deref (temp);
2171 temp = get_constraint_for_component_ref (t);
2175 temp.type = ADDRESSOF;
2176 temp.var = anything_id;
2184 switch (TREE_CODE (t))
2188 case NON_LVALUE_EXPR:
2190 tree op = TREE_OPERAND (t, 0);
2192 /* Cast from non-pointer to pointers are bad news for us.
2193 Anything else, we see through */
2194 if (!(POINTER_TYPE_P (TREE_TYPE (t)) &&
2195 ! POINTER_TYPE_P (TREE_TYPE (op))))
2196 return get_constraint_for (op);
2200 temp.type = ADDRESSOF;
2201 temp.var = anything_id;
2207 case tcc_exceptional:
2209 switch (TREE_CODE (t))
2212 return get_constraint_for (PHI_RESULT (t));
2214 return get_constraint_exp_from_ssa_var (t);
2217 temp.type = ADDRESSOF;
2218 temp.var = anything_id;
2224 case tcc_declaration:
2225 return get_constraint_exp_from_ssa_var (t);
2228 temp.type = ADDRESSOF;
2229 temp.var = anything_id;
2237 /* Handle the structure copy case where we have a simple structure copy
2238 between LHS and RHS that is of SIZE (in bits)
2240 For each field of the lhs variable (lhsfield)
2241 For each field of the rhs variable at lhsfield.offset (rhsfield)
2242 add the constraint lhsfield = rhsfield
2246 do_simple_structure_copy (const struct constraint_expr lhs,
2247 const struct constraint_expr rhs,
2248 const unsigned HOST_WIDE_INT size)
2250 varinfo_t p = get_varinfo (lhs.var);
2251 unsigned HOST_WIDE_INT pstart, last;
2253 last = p->offset + size;
2254 for (; p && p->offset < last; p = p->next)
2257 struct constraint_expr templhs = lhs;
2258 struct constraint_expr temprhs = rhs;
2259 unsigned HOST_WIDE_INT fieldoffset;
2261 templhs.var = p->id;
2262 q = get_varinfo (temprhs.var);
2263 fieldoffset = p->offset - pstart;
2264 q = first_vi_for_offset (q, q->offset + fieldoffset);
2265 temprhs.var = q->id;
2266 process_constraint (new_constraint (templhs, temprhs));
2271 /* Handle the structure copy case where we have a structure copy between a
2272 aggregate on the LHS and a dereference of a pointer on the RHS
2273 that is of SIZE (in bits)
2275 For each field of the lhs variable (lhsfield)
2276 rhs.offset = lhsfield->offset
2277 add the constraint lhsfield = rhs
2281 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2282 const struct constraint_expr rhs,
2283 const unsigned HOST_WIDE_INT size)
2285 varinfo_t p = get_varinfo (lhs.var);
2286 unsigned HOST_WIDE_INT pstart,last;
2288 last = p->offset + size;
2290 for (; p && p->offset < last; p = p->next)
2293 struct constraint_expr templhs = lhs;
2294 struct constraint_expr temprhs = rhs;
2295 unsigned HOST_WIDE_INT fieldoffset;
2298 if (templhs.type == SCALAR)
2299 templhs.var = p->id;
2301 templhs.offset = p->offset;
2303 q = get_varinfo (temprhs.var);
2304 fieldoffset = p->offset - pstart;
2305 temprhs.offset += fieldoffset;
2306 process_constraint (new_constraint (templhs, temprhs));
2310 /* Handle the structure copy case where we have a structure copy
2311 between a aggregate on the RHS and a dereference of a pointer on
2312 the LHS that is of SIZE (in bits)
2314 For each field of the rhs variable (rhsfield)
2315 lhs.offset = rhsfield->offset
2316 add the constraint lhs = rhsfield
2320 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2321 const struct constraint_expr rhs,
2322 const unsigned HOST_WIDE_INT size)
2324 varinfo_t p = get_varinfo (rhs.var);
2325 unsigned HOST_WIDE_INT pstart,last;
2327 last = p->offset + size;
2329 for (; p && p->offset < last; p = p->next)
2332 struct constraint_expr templhs = lhs;
2333 struct constraint_expr temprhs = rhs;
2334 unsigned HOST_WIDE_INT fieldoffset;
2337 if (temprhs.type == SCALAR)
2338 temprhs.var = p->id;
2340 temprhs.offset = p->offset;
2342 q = get_varinfo (templhs.var);
2343 fieldoffset = p->offset - pstart;
2344 templhs.offset += fieldoffset;
2345 process_constraint (new_constraint (templhs, temprhs));
2350 /* Handle aggregate copies by expanding into copies of the respective
2351 fields of the structures. */
2354 do_structure_copy (tree lhsop, tree rhsop)
2356 struct constraint_expr lhs, rhs, tmp;
2358 unsigned HOST_WIDE_INT lhssize;
2359 unsigned HOST_WIDE_INT rhssize;
2361 lhs = get_constraint_for (lhsop);
2362 rhs = get_constraint_for (rhsop);
2364 /* If we have special var = x, swap it around. */
2365 if (lhs.var <= integer_id && rhs.var > integer_id)
2372 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2373 possible it's something we could handle. However, most cases falling
2374 into this are dealing with transparent unions, which are slightly
2376 if (rhs.type == ADDRESSOF && rhs.var > integer_id)
2378 rhs.type = ADDRESSOF;
2379 rhs.var = anything_id;
2382 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2383 that special var. */
2384 if (rhs.var <= integer_id)
2386 for (p = get_varinfo (lhs.var); p; p = p->next)
2388 struct constraint_expr templhs = lhs;
2389 struct constraint_expr temprhs = rhs;
2390 if (templhs.type == SCALAR )
2391 templhs.var = p->id;
2393 templhs.offset += p->offset;
2394 process_constraint (new_constraint (templhs, temprhs));
2399 /* The size only really matters insofar as we don't set more or less of
2400 the variable. If we hit an unknown size var, the size should be the
2401 whole darn thing. */
2402 if (get_varinfo (rhs.var)->is_unknown_size_var)
2405 rhssize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (rhsop)));
2407 if (get_varinfo (lhs.var)->is_unknown_size_var)
2410 lhssize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (lhsop)));
2413 if (rhs.type == SCALAR && lhs.type == SCALAR)
2414 do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2415 else if (lhs.type != DEREF && rhs.type == DEREF)
2416 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2417 else if (lhs.type == DEREF && rhs.type != DEREF)
2418 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2421 tree rhsdecl = get_varinfo (rhs.var)->decl;
2422 tree pointertype = TREE_TYPE (rhsdecl);
2423 tree pointedtotype = TREE_TYPE (pointertype);
2426 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2427 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2428 do_structure_copy (tmpvar, rhsop);
2429 do_structure_copy (lhsop, tmpvar);
2435 /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere
2439 ref_contains_indirect_ref (tree ref)
2441 while (handled_component_p (ref))
2443 if (TREE_CODE (ref) == INDIRECT_REF)
2445 ref = TREE_OPERAND (ref, 0);
2451 /* Tree walker that is the heart of the aliasing infrastructure.
2452 TP is a pointer to the current tree.
2453 WALK_SUBTREES specifies whether to continue traversing subtrees or
2455 Returns NULL_TREE when we should stop.
2457 This function is the main part of the constraint builder. It
2458 walks the trees, calling the appropriate building functions
2459 to process various statements. */
2462 find_func_aliases (tree t)
2464 struct constraint_expr lhs, rhs;
2465 switch (TREE_CODE (t))
2471 /* Only care about pointers and structures containing
2473 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
2474 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
2476 lhs = get_constraint_for (PHI_RESULT (t));
2477 for (i = 0; i < PHI_NUM_ARGS (t); i++)
2479 rhs = get_constraint_for (PHI_ARG_DEF (t, i));
2480 process_constraint (new_constraint (lhs, rhs));
2488 tree lhsop = TREE_OPERAND (t, 0);
2489 tree rhsop = TREE_OPERAND (t, 1);
2492 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2493 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
2495 do_structure_copy (lhsop, rhsop);
2499 /* Only care about operations with pointers, structures
2500 containing pointers, dereferences, and call
2502 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
2503 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2504 || ref_contains_indirect_ref (lhsop)
2505 || TREE_CODE (rhsop) == CALL_EXPR)
2507 lhs = get_constraint_for (lhsop);
2508 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
2510 /* RHS that consist of unary operations,
2511 exceptional types, or bare decls/constants, get
2512 handled directly by get_constraint_for. */
2514 case tcc_declaration:
2516 case tcc_exceptional:
2517 case tcc_expression:
2520 rhs = get_constraint_for (rhsop);
2521 process_constraint (new_constraint (lhs, rhs));
2525 /* Otherwise, walk each operand. */
2527 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
2529 tree op = TREE_OPERAND (rhsop, i);
2530 rhs = get_constraint_for (op);
2531 process_constraint (new_constraint (lhs, rhs));
2545 /* Find the first varinfo in the same variable as START that overlaps with
2547 Effectively, walk the chain of fields for the variable START to find the
2548 first field that overlaps with OFFSET.
2549 Abort if we can't find one. */
2552 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
2554 varinfo_t curr = start;
2557 /* We may not find a variable in the field list with the actual
2558 offset when when we have glommed a structure to a variable.
2559 In that case, however, offset should still be within the size
2561 if (offset >= curr->offset && offset < (curr->offset + curr->size))
2570 /* Insert the varinfo FIELD into the field list for BASE, ordered by
2574 insert_into_field_list (varinfo_t base, varinfo_t field)
2576 varinfo_t prev = base;
2577 varinfo_t curr = base->next;
2588 if (field->offset <= curr->offset)
2593 field->next = prev->next;
2598 /* qsort comparison function for two fieldoff's PA and PB */
2601 fieldoff_compare (const void *pa, const void *pb)
2603 const fieldoff_s *foa = (const fieldoff_s *)pa;
2604 const fieldoff_s *fob = (const fieldoff_s *)pb;
2605 HOST_WIDE_INT foasize, fobsize;
2607 if (foa->offset != fob->offset)
2608 return foa->offset - fob->offset;
2610 foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
2611 fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
2612 return foasize - fobsize;
2615 /* Sort a fieldstack according to the field offset and sizes. */
2616 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
2618 qsort (VEC_address (fieldoff_s, fieldstack),
2619 VEC_length (fieldoff_s, fieldstack),
2620 sizeof (fieldoff_s),
2624 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
2625 of TYPE onto fieldstack, recording their offsets along the way.
2626 OFFSET is used to keep track of the offset in this entire structure, rather
2627 than just the immediately containing structure. Returns the number
2629 HAS_UNION is set to true if we find a union type as a field of
2633 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
2634 HOST_WIDE_INT offset, bool *has_union)
2639 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2640 if (TREE_CODE (field) == FIELD_DECL)
2645 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
2646 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
2649 if (!var_can_have_subvars (field))
2651 else if (!(push_fields_onto_fieldstack
2652 (TREE_TYPE (field), fieldstack,
2653 offset + bitpos_of_field (field), has_union))
2654 && DECL_SIZE (field)
2655 && !integer_zerop (DECL_SIZE (field)))
2656 /* Empty structures may have actual size, like in C++. So
2657 see if we didn't push any subfields and the size is
2658 nonzero, push the field onto the stack */
2665 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
2666 pair->field = field;
2667 pair->offset = offset + bitpos_of_field (field);
2676 make_constraint_to_anything (varinfo_t vi)
2678 struct constraint_expr lhs, rhs;
2684 rhs.var = anything_id;
2686 rhs.type = ADDRESSOF;
2687 process_constraint (new_constraint (lhs, rhs));
2690 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
2691 This will also create any varinfo structures necessary for fields
2695 create_variable_info_for (tree decl, const char *name)
2697 unsigned int index = VEC_length (varinfo_t, varmap);
2699 tree decltype = TREE_TYPE (decl);
2700 bool notokay = false;
2703 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
2704 VEC (fieldoff_s,heap) *fieldstack = NULL;
2707 hasunion = TREE_CODE (decltype) == UNION_TYPE || TREE_CODE (decltype) == QUAL_UNION_TYPE;
2708 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
2710 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
2713 VEC_free (fieldoff_s, heap, fieldstack);
2718 /* If this variable already has subvars, just create the variables for the
2719 subvars and we are done.
2720 NOTE: This assumes things haven't generated uses of previously
2721 unused structure fields. */
2722 if (use_field_sensitive
2724 && var_can_have_subvars (decl)
2726 && (svars = get_subvars_for_var (decl)))
2729 varinfo_t base = NULL;
2730 unsigned int firstindex = index;
2732 for (sv = svars; sv; sv = sv->next)
2734 /* For debugging purposes, this will print the names of the
2735 fields as "<var>.<offset>.<size>"
2736 This is only for debugging purposes. */
2737 #define PRINT_LONG_NAMES
2738 #ifdef PRINT_LONG_NAMES
2740 const char *newname;
2742 asprintf (&tempname,
2743 "%s." HOST_WIDE_INT_PRINT_DEC "." HOST_WIDE_INT_PRINT_DEC,
2744 alias_get_name (decl), sv->offset, sv->size);
2745 newname = ggc_strdup (tempname);
2747 vi = new_var_info (sv->var, index, newname, index);
2749 vi = new_var_info (sv->var, index, alias_get_name (sv->var), index);
2752 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2753 vi->size = sv->size;
2754 vi->offset = sv->offset;
2758 insert_id_for_tree (decl, index);
2762 insert_into_field_list (base, vi);
2764 insert_id_for_tree (sv->var, index);
2765 VEC_safe_push (varinfo_t, gc, varmap, vi);
2767 make_constraint_to_anything (vi);
2775 /* If the variable doesn't have subvars, we may end up needing to
2776 sort the field list and create fake variables for all the
2778 vi = new_var_info (decl, index, name, index);
2781 vi->has_union = hasunion;
2782 if (!TYPE_SIZE (decltype)
2783 || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
2784 || TREE_CODE (decltype) == ARRAY_TYPE
2785 || TREE_CODE (decltype) == UNION_TYPE
2786 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
2788 vi->is_unknown_size_var = true;
2794 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2795 vi->size = vi->fullsize;
2798 insert_id_for_tree (vi->decl, index);
2799 VEC_safe_push (varinfo_t, gc, varmap, vi);
2801 make_constraint_to_anything (vi);
2804 if (use_field_sensitive
2806 && !vi->is_unknown_size_var
2807 && var_can_have_subvars (decl))
2809 unsigned int newindex = VEC_length (varinfo_t, varmap);
2810 fieldoff_s *fo = NULL;
2814 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
2816 if (!DECL_SIZE (fo->field)
2817 || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
2818 || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE
2826 /* We can't sort them if we have a field with a variable sized type,
2827 which will make notokay = true. In that case, we are going to return
2828 without creating varinfos for the fields anyway, so sorting them is a
2831 sort_fieldstack (fieldstack);
2833 if (VEC_length (fieldoff_s, fieldstack) != 0)
2834 fo = VEC_index (fieldoff_s, fieldstack, 0);
2836 if (fo == NULL || notokay)
2838 vi->is_unknown_size_var = 1;
2841 VEC_free (fieldoff_s, heap, fieldstack);
2846 vi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
2847 for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
2850 const char *newname;
2854 newindex = VEC_length (varinfo_t, varmap);
2855 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (field));
2856 newname = ggc_strdup (tempname);
2858 newvi = new_var_info (decl, newindex, newname, newindex);
2859 newvi->offset = fo->offset;
2860 newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
2861 newvi->fullsize = vi->fullsize;
2862 insert_into_field_list (vi, newvi);
2863 VEC_safe_push (varinfo_t, gc, varmap, newvi);
2865 make_constraint_to_anything (newvi);
2869 VEC_free (fieldoff_s, heap, fieldstack);
2874 /* Print out the points-to solution for VAR to FILE. */
2877 dump_solution_for_var (FILE *file, unsigned int var)
2879 varinfo_t vi = get_varinfo (var);
2883 fprintf (file, "%s = { ", vi->name);
2884 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
2886 fprintf (file, "%s ", get_varinfo (i)->name);
2888 fprintf (file, "}\n");
2891 /* Print the points-to solution for VAR to stdout. */
2894 debug_solution_for_var (unsigned int var)
2896 dump_solution_for_var (stdout, var);
2900 /* Create varinfo structures for all of the variables in the
2901 function for intraprocedural mode. */
2904 intra_create_variable_infos (void)
2908 /* For each incoming argument arg, ARG = &ANYTHING */
2909 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
2911 struct constraint_expr lhs;
2912 struct constraint_expr rhs;
2917 lhs.var = create_variable_info_for (t, alias_get_name (t));
2919 get_varinfo (lhs.var)->is_artificial_var = true;
2920 rhs.var = anything_id;
2921 rhs.type = ADDRESSOF;
2924 for (p = get_varinfo (lhs.var); p; p = p->next)
2926 struct constraint_expr temp = lhs;
2928 process_constraint (new_constraint (temp, rhs));
2934 /* Set bits in INTO corresponding to the variable uids in solution set
2938 set_uids_in_ptset (bitmap into, bitmap from)
2943 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
2945 varinfo_t vi = get_varinfo (i);
2947 /* Variables containing unions may need to be converted to their
2948 SFT's, because SFT's can have unions and we cannot. */
2949 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
2951 subvar_t svars = get_subvars_for_var (vi->decl);
2953 for (sv = svars; sv; sv = sv->next)
2954 bitmap_set_bit (into, DECL_UID (sv->var));
2956 /* We may end up with labels in the points-to set because people
2957 take their address, and they are _DECL's. */
2958 else if (TREE_CODE (vi->decl) == VAR_DECL
2959 || TREE_CODE (vi->decl) == PARM_DECL)
2960 bitmap_set_bit (into, DECL_UID (vi->decl));
2965 static int have_alias_info = false;
2967 /* Given a pointer variable P, fill in its points-to set, or return
2968 false if we can't. */
2971 find_what_p_points_to (tree p)
2973 unsigned int id = 0;
2974 if (!have_alias_info)
2976 if (lookup_id_for_tree (p, &id))
2978 varinfo_t vi = get_varinfo (id);
2980 if (vi->is_artificial_var)
2983 /* See if this is a field or a structure */
2984 if (vi->size != vi->fullsize)
2986 if (!var_can_have_subvars (vi->decl)
2987 || get_subvars_for_var (vi->decl) == NULL)
2989 /* Nothing currently asks about structure fields directly, but when
2990 they do, we need code here to hand back the points-to set. */
2994 struct ptr_info_def *pi = get_ptr_info (p);
2998 /* This variable may have been collapsed, let's get the real
3000 vi = get_varinfo (vi->node);
3002 /* Make sure there aren't any artificial vars in the points to set.
3003 XXX: Note that we need to translate our heap variables to
3005 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
3007 if (get_varinfo (i)->is_artificial_var)
3010 pi->pt_anything = false;
3012 pi->pt_vars = BITMAP_GGC_ALLOC ();
3013 set_uids_in_ptset (pi->pt_vars, vi->solution);
3021 /* Initialize things necessary to perform PTA */
3024 init_alias_vars (void)
3026 bitmap_obstack_initialize (&ptabitmap_obstack);
3030 /* Dump points-to information to OUTFILE. */
3033 dump_sa_points_to_info (FILE *outfile)
3037 fprintf (outfile, "\nPoints-to information\n\n");
3039 if (dump_flags & TDF_STATS)
3041 fprintf (outfile, "Stats:\n");
3042 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
3043 fprintf (outfile, "Statically unified vars: %d\n",
3044 stats.unified_vars_static);
3045 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
3046 fprintf (outfile, "Dynamically unified vars: %d\n",
3047 stats.unified_vars_dynamic);
3048 fprintf (outfile, "Iterations: %d\n", stats.iterations);
3051 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
3052 dump_solution_for_var (outfile, i);
3056 /* Debug points-to information to stderr. */
3059 debug_sa_points_to_info (void)
3061 dump_sa_points_to_info (stderr);
3065 /* Initialize the always-existing constraint variables for NULL
3066 ANYTHING, READONLY, and INTEGER */
3069 init_base_vars (void)
3071 struct constraint_expr lhs, rhs;
3073 /* Create the NULL variable, used to represent that a variable points
3075 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
3076 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
3077 insert_id_for_tree (nothing_tree, 0);
3078 var_nothing->is_artificial_var = 1;
3079 var_nothing->offset = 0;
3080 var_nothing->size = ~0;
3081 var_nothing->fullsize = ~0;
3083 VEC_safe_push (varinfo_t, gc, varmap, var_nothing);
3085 /* Create the ANYTHING variable, used to represent that a variable
3086 points to some unknown piece of memory. */
3087 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
3088 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
3089 insert_id_for_tree (anything_tree, 1);
3090 var_anything->is_artificial_var = 1;
3091 var_anything->size = ~0;
3092 var_anything->offset = 0;
3093 var_anything->next = NULL;
3094 var_anything->fullsize = ~0;
3097 /* Anything points to anything. This makes deref constraints just
3098 work in the presence of linked list and other p = *p type loops,
3099 by saying that *ANYTHING = ANYTHING. */
3100 VEC_safe_push (varinfo_t, gc, varmap, var_anything);
3102 lhs.var = anything_id;
3104 rhs.type = ADDRESSOF;
3105 rhs.var = anything_id;
3107 var_anything->address_taken = true;
3108 /* This specifically does not use process_constraint because
3109 process_constraint ignores all anything = anything constraints, since all
3110 but this one are redundant. */
3111 VEC_safe_push (constraint_t, gc, constraints, new_constraint (lhs, rhs));
3113 /* Create the READONLY variable, used to represent that a variable
3114 points to readonly memory. */
3115 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
3116 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
3117 var_readonly->is_artificial_var = 1;
3118 var_readonly->offset = 0;
3119 var_readonly->size = ~0;
3120 var_readonly->fullsize = ~0;
3121 var_readonly->next = NULL;
3122 insert_id_for_tree (readonly_tree, 2);
3124 VEC_safe_push (varinfo_t, gc, varmap, var_readonly);
3126 /* readonly memory points to anything, in order to make deref
3127 easier. In reality, it points to anything the particular
3128 readonly variable can point to, but we don't track this
3131 lhs.var = readonly_id;
3133 rhs.type = ADDRESSOF;
3134 rhs.var = anything_id;
3137 process_constraint (new_constraint (lhs, rhs));
3139 /* Create the INTEGER variable, used to represent that a variable points
3141 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
3142 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
3143 insert_id_for_tree (integer_tree, 3);
3144 var_integer->is_artificial_var = 1;
3145 var_integer->size = ~0;
3146 var_integer->fullsize = ~0;
3147 var_integer->offset = 0;
3148 var_integer->next = NULL;
3150 VEC_safe_push (varinfo_t, gc, varmap, var_integer);
3152 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
3153 integer will point to. */
3155 lhs.var = integer_id;
3157 rhs.type = ADDRESSOF;
3158 rhs.var = anything_id;
3160 process_constraint (new_constraint (lhs, rhs));
3164 /* Create points-to sets for the current function. See the comments
3165 at the start of the file for an algorithmic overview. */
3168 create_alias_vars (void)
3174 constraint_pool = create_alloc_pool ("Constraint pool",
3175 sizeof (struct constraint), 30);
3176 variable_info_pool = create_alloc_pool ("Variable info pool",
3177 sizeof (struct variable_info), 30);
3178 constraint_edge_pool = create_alloc_pool ("Constraint edges",
3179 sizeof (struct constraint_edge), 30);
3181 constraints = VEC_alloc (constraint_t, gc, 8);
3182 varmap = VEC_alloc (varinfo_t, gc, 8);
3183 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
3184 memset (&stats, 0, sizeof (stats));
3188 intra_create_variable_infos ();
3190 /* Now walk all statements and derive aliases. */
3193 block_stmt_iterator bsi;
3196 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3197 if (is_gimple_reg (PHI_RESULT (phi)))
3198 find_func_aliases (phi);
3200 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3201 find_func_aliases (bsi_stmt (bsi));
3204 build_constraint_graph ();
3208 fprintf (dump_file, "Constraints:\n");
3209 dump_constraints (dump_file);
3213 fprintf (dump_file, "Collapsing static cycles and doing variable substitution:\n");
3215 find_and_collapse_graph_cycles (graph, false);
3216 perform_var_substitution (graph);
3219 fprintf (dump_file, "Solving graph:\n");
3221 solve_graph (graph);
3224 dump_sa_points_to_info (dump_file);
3226 have_alias_info = true;
3229 struct tree_opt_pass pass_build_pta =
3233 create_alias_vars, /* execute */
3236 0, /* static_pass_number */
3237 TV_TREE_PTA, /* tv_id */
3238 PROP_cfg, /* properties_required */
3239 PROP_pta, /* properties_provided */
3240 0, /* properties_destroyed */
3241 0, /* todo_flags_start */
3242 0, /* todo_flags_finish */
3247 /* Delete created points-to sets. */
3250 delete_alias_vars (void)
3252 htab_delete (id_for_tree);
3253 free_alloc_pool (variable_info_pool);
3254 free_alloc_pool (constraint_pool);
3255 free_alloc_pool (constraint_edge_pool);
3256 bitmap_obstack_release (&ptabitmap_obstack);
3257 have_alias_info = false;
3260 struct tree_opt_pass pass_del_pta =
3264 delete_alias_vars, /* execute */
3267 0, /* static_pass_number */
3268 TV_TREE_PTA, /* tv_id */
3269 PROP_pta, /* properties_required */
3270 0, /* properties_provided */
3271 PROP_pta, /* properties_destroyed */
3272 0, /* todo_flags_start */
3273 0, /* todo_flags_finish */