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 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1945 static struct constraint_expr
1946 get_constraint_for_component_ref (tree t)
1948 struct constraint_expr result;
1949 HOST_WIDE_INT bitsize;
1950 HOST_WIDE_INT bitpos;
1952 enum machine_mode mode;
1958 result.type = SCALAR;
1961 /* Some people like to do cute things like take the address of
1964 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
1965 forzero = TREE_OPERAND (forzero, 0);
1967 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
1970 result.var = integer_id;
1971 result.type = SCALAR;
1975 t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode,
1976 &unsignedp, &volatilep, false);
1977 result = get_constraint_for (t);
1979 /* This can also happen due to weird offsetof type macros. */
1980 if (TREE_CODE (t) != ADDR_EXPR && result.type == ADDRESSOF)
1981 result.type = SCALAR;
1983 /* If we know where this goes, then yay. Otherwise, booo. */
1985 if (offset == NULL && bitsize != -1)
1987 result.offset = bitpos;
1991 result.var = anything_id;
1995 if (result.type == SCALAR)
1997 /* In languages like C, you can access one past the end of an
1998 array. You aren't allowed to dereference it, so we can
1999 ignore this constraint. When we handle pointer subtraction,
2000 we may have to do something cute here. */
2002 if (result.offset < get_varinfo (result.var)->fullsize)
2003 result.var = first_vi_for_offset (get_varinfo (result.var),
2006 if (dump_file && (dump_flags & TDF_DETAILS))
2007 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2016 /* Dereference the constraint expression CONS, and return the result.
2017 DEREF (ADDRESSOF) = SCALAR
2018 DEREF (SCALAR) = DEREF
2019 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2020 This is needed so that we can handle dereferencing DEREF constraints. */
2022 static struct constraint_expr
2023 do_deref (struct constraint_expr cons)
2025 if (cons.type == SCALAR)
2030 else if (cons.type == ADDRESSOF)
2035 else if (cons.type == DEREF)
2037 tree tmpvar = create_tmp_var_raw (ptr_type_node, "derefmp");
2038 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2039 process_constraint (new_constraint (tmplhs, cons));
2040 cons.var = tmplhs.var;
2047 /* Given a tree T, return the constraint expression for it. */
2049 static struct constraint_expr
2050 get_constraint_for (tree t)
2052 struct constraint_expr temp;
2054 /* x = integer is all glommed to a single variable, which doesn't
2055 point to anything by itself. That is, of course, unless it is an
2056 integer constant being treated as a pointer, in which case, we
2057 will return that this is really the addressof anything. This
2058 happens below, since it will fall into the default case. The only
2059 case we know something about an integer treated like a pointer is
2060 when it is the NULL pointer, and then we just say it points to
2062 if (TREE_CODE (t) == INTEGER_CST
2063 && !POINTER_TYPE_P (TREE_TYPE (t)))
2065 temp.var = integer_id;
2070 else if (TREE_CODE (t) == INTEGER_CST
2071 && integer_zerop (t))
2073 temp.var = nothing_id;
2074 temp.type = ADDRESSOF;
2079 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2081 case tcc_expression:
2083 switch (TREE_CODE (t))
2087 temp = get_constraint_for (TREE_OPERAND (t, 0));
2088 if (temp.type == DEREF)
2091 temp.type = ADDRESSOF;
2097 /* XXX: In interprocedural mode, if we didn't have the
2098 body, we would need to do *each pointer argument =
2100 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2102 tree heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2103 temp.var = create_variable_info_for (heapvar,
2104 alias_get_name (heapvar));
2106 get_varinfo (temp.var)->is_artificial_var = 1;
2107 temp.type = ADDRESSOF;
2114 temp.type = ADDRESSOF;
2115 temp.var = anything_id;
2123 switch (TREE_CODE (t))
2127 temp = get_constraint_for (TREE_OPERAND (t, 0));
2128 temp = do_deref (temp);
2133 temp = get_constraint_for_component_ref (t);
2137 temp.type = ADDRESSOF;
2138 temp.var = anything_id;
2146 switch (TREE_CODE (t))
2150 case NON_LVALUE_EXPR:
2152 tree op = TREE_OPERAND (t, 0);
2154 /* Cast from non-pointer to pointers are bad news for us.
2155 Anything else, we see through */
2156 if (!(POINTER_TYPE_P (TREE_TYPE (t)) &&
2157 ! POINTER_TYPE_P (TREE_TYPE (op))))
2158 return get_constraint_for (op);
2162 temp.type = ADDRESSOF;
2163 temp.var = anything_id;
2169 case tcc_exceptional:
2171 switch (TREE_CODE (t))
2174 return get_constraint_for (PHI_RESULT (t));
2176 return get_constraint_exp_from_ssa_var (t);
2179 temp.type = ADDRESSOF;
2180 temp.var = anything_id;
2186 case tcc_declaration:
2187 return get_constraint_exp_from_ssa_var (t);
2190 temp.type = ADDRESSOF;
2191 temp.var = anything_id;
2199 /* Handle the structure copy case where we have a simple structure copy
2200 between LHS and RHS that is of SIZE (in bits)
2202 For each field of the lhs variable (lhsfield)
2203 For each field of the rhs variable at lhsfield.offset (rhsfield)
2204 add the constraint lhsfield = rhsfield
2208 do_simple_structure_copy (const struct constraint_expr lhs,
2209 const struct constraint_expr rhs,
2210 const unsigned HOST_WIDE_INT size)
2212 varinfo_t p = get_varinfo (lhs.var);
2213 unsigned HOST_WIDE_INT pstart, last;
2215 last = p->offset + size;
2216 for (; p && p->offset < last; p = p->next)
2219 struct constraint_expr templhs = lhs;
2220 struct constraint_expr temprhs = rhs;
2221 unsigned HOST_WIDE_INT fieldoffset;
2223 templhs.var = p->id;
2224 q = get_varinfo (temprhs.var);
2225 fieldoffset = p->offset - pstart;
2226 q = first_vi_for_offset (q, q->offset + fieldoffset);
2227 temprhs.var = q->id;
2228 process_constraint (new_constraint (templhs, temprhs));
2233 /* Handle the structure copy case where we have a structure copy between a
2234 aggregate on the LHS and a dereference of a pointer on the RHS
2235 that is of SIZE (in bits)
2237 For each field of the lhs variable (lhsfield)
2238 rhs.offset = lhsfield->offset
2239 add the constraint lhsfield = rhs
2243 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2244 const struct constraint_expr rhs,
2245 const unsigned HOST_WIDE_INT size)
2247 varinfo_t p = get_varinfo (lhs.var);
2248 unsigned HOST_WIDE_INT pstart,last;
2250 last = p->offset + size;
2252 for (; p && p->offset < last; p = p->next)
2255 struct constraint_expr templhs = lhs;
2256 struct constraint_expr temprhs = rhs;
2257 unsigned HOST_WIDE_INT fieldoffset;
2260 if (templhs.type == SCALAR)
2261 templhs.var = p->id;
2263 templhs.offset = p->offset;
2265 q = get_varinfo (temprhs.var);
2266 fieldoffset = p->offset - pstart;
2267 temprhs.offset += fieldoffset;
2268 process_constraint (new_constraint (templhs, temprhs));
2272 /* Handle the structure copy case where we have a structure copy
2273 between a aggregate on the RHS and a dereference of a pointer on
2274 the LHS that is of SIZE (in bits)
2276 For each field of the rhs variable (rhsfield)
2277 lhs.offset = rhsfield->offset
2278 add the constraint lhs = rhsfield
2282 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2283 const struct constraint_expr rhs,
2284 const unsigned HOST_WIDE_INT size)
2286 varinfo_t p = get_varinfo (rhs.var);
2287 unsigned HOST_WIDE_INT pstart,last;
2289 last = p->offset + size;
2291 for (; p && p->offset < last; p = p->next)
2294 struct constraint_expr templhs = lhs;
2295 struct constraint_expr temprhs = rhs;
2296 unsigned HOST_WIDE_INT fieldoffset;
2299 if (temprhs.type == SCALAR)
2300 temprhs.var = p->id;
2302 temprhs.offset = p->offset;
2304 q = get_varinfo (templhs.var);
2305 fieldoffset = p->offset - pstart;
2306 templhs.offset += fieldoffset;
2307 process_constraint (new_constraint (templhs, temprhs));
2312 /* Handle aggregate copies by expanding into copies of the respective
2313 fields of the structures. */
2316 do_structure_copy (tree lhsop, tree rhsop)
2318 struct constraint_expr lhs, rhs, tmp;
2320 unsigned HOST_WIDE_INT lhssize;
2321 unsigned HOST_WIDE_INT rhssize;
2323 lhs = get_constraint_for (lhsop);
2324 rhs = get_constraint_for (rhsop);
2326 /* If we have special var = x, swap it around. */
2327 if (lhs.var <= integer_id && rhs.var > integer_id)
2334 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2335 possible it's something we could handle. However, most cases falling
2336 into this are dealing with transparent unions, which are slightly
2338 if (rhs.type == ADDRESSOF && rhs.var > integer_id)
2340 rhs.type = ADDRESSOF;
2341 rhs.var = anything_id;
2344 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2345 that special var. */
2346 if (rhs.var <= integer_id)
2348 for (p = get_varinfo (lhs.var); p; p = p->next)
2350 struct constraint_expr templhs = lhs;
2351 struct constraint_expr temprhs = rhs;
2352 if (templhs.type == SCALAR )
2353 templhs.var = p->id;
2355 templhs.offset += p->offset;
2356 process_constraint (new_constraint (templhs, temprhs));
2361 /* The size only really matters insofar as we don't set more or less of
2362 the variable. If we hit an unknown size var, the size should be the
2363 whole darn thing. */
2364 if (get_varinfo (rhs.var)->is_unknown_size_var)
2367 rhssize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (rhsop)));
2369 if (get_varinfo (lhs.var)->is_unknown_size_var)
2372 lhssize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (lhsop)));
2375 if (rhs.type == SCALAR && lhs.type == SCALAR)
2376 do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2377 else if (lhs.type != DEREF && rhs.type == DEREF)
2378 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2379 else if (lhs.type == DEREF && rhs.type != DEREF)
2380 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2383 tree rhsdecl = get_varinfo (rhs.var)->decl;
2384 tree pointertype = TREE_TYPE (rhsdecl);
2385 tree pointedtotype = TREE_TYPE (pointertype);
2388 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2389 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2390 do_structure_copy (tmpvar, rhsop);
2391 do_structure_copy (lhsop, tmpvar);
2397 /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere
2401 ref_contains_indirect_ref (tree ref)
2403 while (handled_component_p (ref))
2405 if (TREE_CODE (ref) == INDIRECT_REF)
2407 ref = TREE_OPERAND (ref, 0);
2413 /* Tree walker that is the heart of the aliasing infrastructure.
2414 TP is a pointer to the current tree.
2415 WALK_SUBTREES specifies whether to continue traversing subtrees or
2417 Returns NULL_TREE when we should stop.
2419 This function is the main part of the constraint builder. It
2420 walks the trees, calling the appropriate building functions
2421 to process various statements. */
2424 find_func_aliases (tree t)
2426 struct constraint_expr lhs, rhs;
2427 switch (TREE_CODE (t))
2433 /* Only care about pointers and structures containing
2435 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
2436 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
2438 lhs = get_constraint_for (PHI_RESULT (t));
2439 for (i = 0; i < PHI_NUM_ARGS (t); i++)
2441 rhs = get_constraint_for (PHI_ARG_DEF (t, i));
2442 process_constraint (new_constraint (lhs, rhs));
2450 tree lhsop = TREE_OPERAND (t, 0);
2451 tree rhsop = TREE_OPERAND (t, 1);
2454 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2455 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
2457 do_structure_copy (lhsop, rhsop);
2461 /* Only care about operations with pointers, structures
2462 containing pointers, dereferences, and call
2464 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
2465 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2466 || ref_contains_indirect_ref (lhsop)
2467 || TREE_CODE (rhsop) == CALL_EXPR)
2469 lhs = get_constraint_for (lhsop);
2470 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
2472 /* RHS that consist of unary operations,
2473 exceptional types, or bare decls/constants, get
2474 handled directly by get_constraint_for. */
2476 case tcc_declaration:
2478 case tcc_exceptional:
2479 case tcc_expression:
2482 rhs = get_constraint_for (rhsop);
2483 process_constraint (new_constraint (lhs, rhs));
2487 /* Otherwise, walk each operand. */
2489 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
2491 tree op = TREE_OPERAND (rhsop, i);
2492 rhs = get_constraint_for (op);
2493 process_constraint (new_constraint (lhs, rhs));
2507 /* Find the first varinfo in the same variable as START that overlaps with
2509 Effectively, walk the chain of fields for the variable START to find the
2510 first field that overlaps with OFFSET.
2511 Abort if we can't find one. */
2514 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
2516 varinfo_t curr = start;
2519 /* We may not find a variable in the field list with the actual
2520 offset when when we have glommed a structure to a variable.
2521 In that case, however, offset should still be within the size
2523 if (offset >= curr->offset && offset < (curr->offset + curr->size))
2532 /* Insert the varinfo FIELD into the field list for BASE, ordered by
2536 insert_into_field_list (varinfo_t base, varinfo_t field)
2538 varinfo_t prev = base;
2539 varinfo_t curr = base->next;
2550 if (field->offset <= curr->offset)
2555 field->next = prev->next;
2560 /* qsort comparison function for two fieldoff's PA and PB */
2563 fieldoff_compare (const void *pa, const void *pb)
2565 const fieldoff_s *foa = (const fieldoff_s *)pa;
2566 const fieldoff_s *fob = (const fieldoff_s *)pb;
2567 HOST_WIDE_INT foasize, fobsize;
2569 if (foa->offset != fob->offset)
2570 return foa->offset - fob->offset;
2572 foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
2573 fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
2574 return foasize - fobsize;
2577 /* Sort a fieldstack according to the field offset and sizes. */
2578 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
2580 qsort (VEC_address (fieldoff_s, fieldstack),
2581 VEC_length (fieldoff_s, fieldstack),
2582 sizeof (fieldoff_s),
2586 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
2587 of TYPE onto fieldstack, recording their offsets along the way.
2588 OFFSET is used to keep track of the offset in this entire structure, rather
2589 than just the immediately containing structure. Returns the number
2591 HAS_UNION is set to true if we find a union type as a field of
2595 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
2596 HOST_WIDE_INT offset, bool *has_union)
2601 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2602 if (TREE_CODE (field) == FIELD_DECL)
2607 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
2608 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
2611 if (!var_can_have_subvars (field))
2613 else if (!(push_fields_onto_fieldstack
2614 (TREE_TYPE (field), fieldstack,
2615 offset + bitpos_of_field (field), has_union))
2616 && DECL_SIZE (field)
2617 && !integer_zerop (DECL_SIZE (field)))
2618 /* Empty structures may have actual size, like in C++. So
2619 see if we didn't push any subfields and the size is
2620 nonzero, push the field onto the stack */
2627 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
2628 pair->field = field;
2629 pair->offset = offset + bitpos_of_field (field);
2638 make_constraint_to_anything (varinfo_t vi)
2640 struct constraint_expr lhs, rhs;
2646 rhs.var = anything_id;
2648 rhs.type = ADDRESSOF;
2649 process_constraint (new_constraint (lhs, rhs));
2652 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
2653 This will also create any varinfo structures necessary for fields
2657 create_variable_info_for (tree decl, const char *name)
2659 unsigned int index = VEC_length (varinfo_t, varmap);
2661 tree decltype = TREE_TYPE (decl);
2662 bool notokay = false;
2665 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
2666 VEC (fieldoff_s,heap) *fieldstack = NULL;
2669 hasunion = TREE_CODE (decltype) == UNION_TYPE || TREE_CODE (decltype) == QUAL_UNION_TYPE;
2670 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
2672 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
2675 VEC_free (fieldoff_s, heap, fieldstack);
2680 /* If this variable already has subvars, just create the variables for the
2681 subvars and we are done.
2682 NOTE: This assumes things haven't generated uses of previously
2683 unused structure fields. */
2684 if (use_field_sensitive
2686 && var_can_have_subvars (decl)
2688 && (svars = get_subvars_for_var (decl)))
2691 varinfo_t base = NULL;
2692 unsigned int firstindex = index;
2694 for (sv = svars; sv; sv = sv->next)
2696 /* For debugging purposes, this will print the names of the
2697 fields as "<var>.<offset>.<size>"
2698 This is only for debugging purposes. */
2699 #define PRINT_LONG_NAMES
2700 #ifdef PRINT_LONG_NAMES
2702 const char *newname;
2704 asprintf (&tempname,
2705 "%s." HOST_WIDE_INT_PRINT_DEC "." HOST_WIDE_INT_PRINT_DEC,
2706 alias_get_name (decl), sv->offset, sv->size);
2707 newname = ggc_strdup (tempname);
2709 vi = new_var_info (sv->var, index, newname, index);
2711 vi = new_var_info (sv->var, index, alias_get_name (sv->var), index);
2714 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2715 vi->size = sv->size;
2716 vi->offset = sv->offset;
2720 insert_id_for_tree (decl, index);
2724 insert_into_field_list (base, vi);
2726 insert_id_for_tree (sv->var, index);
2727 VEC_safe_push (varinfo_t, gc, varmap, vi);
2729 make_constraint_to_anything (vi);
2737 /* If the variable doesn't have subvars, we may end up needing to
2738 sort the field list and create fake variables for all the
2740 vi = new_var_info (decl, index, name, index);
2743 vi->has_union = hasunion;
2744 if (!TYPE_SIZE (decltype)
2745 || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
2746 || TREE_CODE (decltype) == ARRAY_TYPE
2747 || TREE_CODE (decltype) == UNION_TYPE
2748 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
2750 vi->is_unknown_size_var = true;
2756 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2757 vi->size = vi->fullsize;
2760 insert_id_for_tree (vi->decl, index);
2761 VEC_safe_push (varinfo_t, gc, varmap, vi);
2763 make_constraint_to_anything (vi);
2766 if (use_field_sensitive
2768 && !vi->is_unknown_size_var
2769 && var_can_have_subvars (decl))
2771 unsigned int newindex = VEC_length (varinfo_t, varmap);
2772 fieldoff_s *fo = NULL;
2776 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
2778 if (!DECL_SIZE (fo->field)
2779 || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
2780 || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE
2788 /* We can't sort them if we have a field with a variable sized type,
2789 which will make notokay = true. In that case, we are going to return
2790 without creating varinfos for the fields anyway, so sorting them is a
2793 sort_fieldstack (fieldstack);
2795 if (VEC_length (fieldoff_s, fieldstack) != 0)
2796 fo = VEC_index (fieldoff_s, fieldstack, 0);
2798 if (fo == NULL || notokay)
2800 vi->is_unknown_size_var = 1;
2803 VEC_free (fieldoff_s, heap, fieldstack);
2808 vi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
2809 for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
2812 const char *newname;
2816 newindex = VEC_length (varinfo_t, varmap);
2817 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (field));
2818 newname = ggc_strdup (tempname);
2820 newvi = new_var_info (decl, newindex, newname, newindex);
2821 newvi->offset = fo->offset;
2822 newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
2823 newvi->fullsize = vi->fullsize;
2824 insert_into_field_list (vi, newvi);
2825 VEC_safe_push (varinfo_t, gc, varmap, newvi);
2827 make_constraint_to_anything (newvi);
2831 VEC_free (fieldoff_s, heap, fieldstack);
2836 /* Print out the points-to solution for VAR to FILE. */
2839 dump_solution_for_var (FILE *file, unsigned int var)
2841 varinfo_t vi = get_varinfo (var);
2845 fprintf (file, "%s = { ", vi->name);
2846 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
2848 fprintf (file, "%s ", get_varinfo (i)->name);
2850 fprintf (file, "}\n");
2853 /* Print the points-to solution for VAR to stdout. */
2856 debug_solution_for_var (unsigned int var)
2858 dump_solution_for_var (stdout, var);
2862 /* Create varinfo structures for all of the variables in the
2863 function for intraprocedural mode. */
2866 intra_create_variable_infos (void)
2870 /* For each incoming argument arg, ARG = &ANYTHING */
2871 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
2873 struct constraint_expr lhs;
2874 struct constraint_expr rhs;
2879 lhs.var = create_variable_info_for (t, alias_get_name (t));
2881 get_varinfo (lhs.var)->is_artificial_var = true;
2882 rhs.var = anything_id;
2883 rhs.type = ADDRESSOF;
2886 for (p = get_varinfo (lhs.var); p; p = p->next)
2888 struct constraint_expr temp = lhs;
2890 process_constraint (new_constraint (temp, rhs));
2896 /* Set bits in INTO corresponding to the variable uids in solution set
2900 set_uids_in_ptset (bitmap into, bitmap from)
2905 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
2907 varinfo_t vi = get_varinfo (i);
2909 /* Variables containing unions may need to be converted to their
2910 SFT's, because SFT's can have unions and we cannot. */
2911 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
2913 subvar_t svars = get_subvars_for_var (vi->decl);
2915 for (sv = svars; sv; sv = sv->next)
2916 bitmap_set_bit (into, DECL_UID (sv->var));
2918 /* We may end up with labels in the points-to set because people
2919 take their address, and they are _DECL's. */
2920 else if (TREE_CODE (vi->decl) == VAR_DECL
2921 || TREE_CODE (vi->decl) == PARM_DECL)
2922 bitmap_set_bit (into, DECL_UID (vi->decl));
2927 static int have_alias_info = false;
2929 /* Given a pointer variable P, fill in its points-to set, or return
2930 false if we can't. */
2933 find_what_p_points_to (tree p)
2935 unsigned int id = 0;
2936 if (!have_alias_info)
2938 if (lookup_id_for_tree (p, &id))
2940 varinfo_t vi = get_varinfo (id);
2942 if (vi->is_artificial_var)
2945 /* See if this is a field or a structure */
2946 if (vi->size != vi->fullsize)
2948 if (!var_can_have_subvars (vi->decl)
2949 || get_subvars_for_var (vi->decl) == NULL)
2951 /* Nothing currently asks about structure fields directly, but when
2952 they do, we need code here to hand back the points-to set. */
2956 struct ptr_info_def *pi = get_ptr_info (p);
2960 /* This variable may have been collapsed, let's get the real
2962 vi = get_varinfo (vi->node);
2964 /* Make sure there aren't any artificial vars in the points to set.
2965 XXX: Note that we need to translate our heap variables to
2967 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
2969 if (get_varinfo (i)->is_artificial_var)
2972 pi->pt_anything = false;
2974 pi->pt_vars = BITMAP_GGC_ALLOC ();
2975 set_uids_in_ptset (pi->pt_vars, vi->solution);
2983 /* Initialize things necessary to perform PTA */
2986 init_alias_vars (void)
2988 bitmap_obstack_initialize (&ptabitmap_obstack);
2992 /* Dump points-to information to OUTFILE. */
2995 dump_sa_points_to_info (FILE *outfile)
2999 fprintf (outfile, "\nPoints-to information\n\n");
3001 if (dump_flags & TDF_STATS)
3003 fprintf (outfile, "Stats:\n");
3004 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
3005 fprintf (outfile, "Statically unified vars: %d\n",
3006 stats.unified_vars_static);
3007 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
3008 fprintf (outfile, "Dynamically unified vars: %d\n",
3009 stats.unified_vars_dynamic);
3010 fprintf (outfile, "Iterations: %d\n", stats.iterations);
3013 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
3014 dump_solution_for_var (outfile, i);
3018 /* Debug points-to information to stderr. */
3021 debug_sa_points_to_info (void)
3023 dump_sa_points_to_info (stderr);
3027 /* Initialize the always-existing constraint variables for NULL
3028 ANYTHING, READONLY, and INTEGER */
3031 init_base_vars (void)
3033 struct constraint_expr lhs, rhs;
3035 /* Create the NULL variable, used to represent that a variable points
3037 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
3038 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
3039 insert_id_for_tree (nothing_tree, 0);
3040 var_nothing->is_artificial_var = 1;
3041 var_nothing->offset = 0;
3042 var_nothing->size = ~0;
3043 var_nothing->fullsize = ~0;
3045 VEC_safe_push (varinfo_t, gc, varmap, var_nothing);
3047 /* Create the ANYTHING variable, used to represent that a variable
3048 points to some unknown piece of memory. */
3049 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
3050 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
3051 insert_id_for_tree (anything_tree, 1);
3052 var_anything->is_artificial_var = 1;
3053 var_anything->size = ~0;
3054 var_anything->offset = 0;
3055 var_anything->next = NULL;
3056 var_anything->fullsize = ~0;
3059 /* Anything points to anything. This makes deref constraints just
3060 work in the presence of linked list and other p = *p type loops,
3061 by saying that *ANYTHING = ANYTHING. */
3062 VEC_safe_push (varinfo_t, gc, varmap, var_anything);
3064 lhs.var = anything_id;
3066 rhs.type = ADDRESSOF;
3067 rhs.var = anything_id;
3069 var_anything->address_taken = true;
3070 /* This specifically does not use process_constraint because
3071 process_constraint ignores all anything = anything constraints, since all
3072 but this one are redundant. */
3073 VEC_safe_push (constraint_t, gc, constraints, new_constraint (lhs, rhs));
3075 /* Create the READONLY variable, used to represent that a variable
3076 points to readonly memory. */
3077 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
3078 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
3079 var_readonly->is_artificial_var = 1;
3080 var_readonly->offset = 0;
3081 var_readonly->size = ~0;
3082 var_readonly->fullsize = ~0;
3083 var_readonly->next = NULL;
3084 insert_id_for_tree (readonly_tree, 2);
3086 VEC_safe_push (varinfo_t, gc, varmap, var_readonly);
3088 /* readonly memory points to anything, in order to make deref
3089 easier. In reality, it points to anything the particular
3090 readonly variable can point to, but we don't track this
3093 lhs.var = readonly_id;
3095 rhs.type = ADDRESSOF;
3096 rhs.var = anything_id;
3099 process_constraint (new_constraint (lhs, rhs));
3101 /* Create the INTEGER variable, used to represent that a variable points
3103 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
3104 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
3105 insert_id_for_tree (integer_tree, 3);
3106 var_integer->is_artificial_var = 1;
3107 var_integer->size = ~0;
3108 var_integer->fullsize = ~0;
3109 var_integer->offset = 0;
3110 var_integer->next = NULL;
3112 VEC_safe_push (varinfo_t, gc, varmap, var_integer);
3114 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
3115 integer will point to. */
3117 lhs.var = integer_id;
3119 rhs.type = ADDRESSOF;
3120 rhs.var = anything_id;
3122 process_constraint (new_constraint (lhs, rhs));
3126 /* Create points-to sets for the current function. See the comments
3127 at the start of the file for an algorithmic overview. */
3130 create_alias_vars (void)
3136 constraint_pool = create_alloc_pool ("Constraint pool",
3137 sizeof (struct constraint), 30);
3138 variable_info_pool = create_alloc_pool ("Variable info pool",
3139 sizeof (struct variable_info), 30);
3140 constraint_edge_pool = create_alloc_pool ("Constraint edges",
3141 sizeof (struct constraint_edge), 30);
3143 constraints = VEC_alloc (constraint_t, gc, 8);
3144 varmap = VEC_alloc (varinfo_t, gc, 8);
3145 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
3146 memset (&stats, 0, sizeof (stats));
3150 intra_create_variable_infos ();
3152 /* Now walk all statements and derive aliases. */
3155 block_stmt_iterator bsi;
3158 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3159 if (is_gimple_reg (PHI_RESULT (phi)))
3160 find_func_aliases (phi);
3162 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3163 find_func_aliases (bsi_stmt (bsi));
3166 build_constraint_graph ();
3170 fprintf (dump_file, "Constraints:\n");
3171 dump_constraints (dump_file);
3175 fprintf (dump_file, "Collapsing static cycles and doing variable substitution:\n");
3177 find_and_collapse_graph_cycles (graph, false);
3178 perform_var_substitution (graph);
3181 fprintf (dump_file, "Solving graph:\n");
3183 solve_graph (graph);
3186 dump_sa_points_to_info (dump_file);
3188 have_alias_info = true;
3191 struct tree_opt_pass pass_build_pta =
3195 create_alias_vars, /* execute */
3198 0, /* static_pass_number */
3199 TV_TREE_PTA, /* tv_id */
3200 PROP_cfg, /* properties_required */
3201 PROP_pta, /* properties_provided */
3202 0, /* properties_destroyed */
3203 0, /* todo_flags_start */
3204 0, /* todo_flags_finish */
3209 /* Delete created points-to sets. */
3212 delete_alias_vars (void)
3214 htab_delete (id_for_tree);
3215 free_alloc_pool (variable_info_pool);
3216 free_alloc_pool (constraint_pool);
3217 free_alloc_pool (constraint_edge_pool);
3218 bitmap_obstack_release (&ptabitmap_obstack);
3219 have_alias_info = false;
3222 struct tree_opt_pass pass_del_pta =
3226 delete_alias_vars, /* execute */
3229 0, /* static_pass_number */
3230 TV_TREE_PTA, /* tv_id */
3231 PROP_pta, /* properties_required */
3232 0, /* properties_provided */
3233 PROP_pta, /* properties_destroyed */
3234 0, /* todo_flags_start */
3235 0, /* todo_flags_finish */