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"
37 #include "diagnostic.h"
40 #include "tree-flow.h"
41 #include "tree-inline.h"
44 #include "tree-gimple.h"
48 #include "tree-pass.h"
50 #include "alloc-pool.h"
51 #include "splay-tree.h"
53 /* The idea behind this analyzer is to generate set constraints from the
54 program, then solve the resulting constraints in order to generate the
57 Set constraints are a way of modeling program analysis problems that
58 involve sets. They consist of an inclusion constraint language,
59 describing the variables (each variable is a set) and operations that
60 are involved on the variables, and a set of rules that derive facts
61 from these operations. To solve a system of set constraints, you derive
62 all possible facts under the rules, which gives you the correct sets
65 See "Efficient Field-sensitive pointer analysis for C" by "David
66 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
67 http://citeseer.ist.psu.edu/pearce04efficient.html
69 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
70 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
71 http://citeseer.ist.psu.edu/heintze01ultrafast.html
73 There are three types of constraint expressions, DEREF, ADDRESSOF, and
74 SCALAR. Each constraint expression consists of a constraint type,
75 a variable, and an offset.
77 SCALAR is a constraint expression type used to represent x, whether
78 it appears on the LHS or the RHS of a statement.
79 DEREF is a constraint expression type used to represent *x, whether
80 it appears on the LHS or the RHS of a statement.
81 ADDRESSOF is a constraint expression used to represent &x, whether
82 it appears on the LHS or the RHS of a statement.
84 Each pointer variable in the program is assigned an integer id, and
85 each field of a structure variable is assigned an integer id as well.
87 Structure variables are linked to their list of fields through a "next
88 field" in each variable that points to the next field in offset
90 Each variable for a structure field has
92 1. "size", that tells the size in bits of that field.
93 2. "fullsize, that tells the size in bits of the entire structure.
94 3. "offset", that tells the offset in bits from the beginning of the
95 structure to this field.
107 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
108 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
109 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
112 In order to solve the system of set constraints, the following is
115 1. Each constraint variable x has a solution set associated with it,
118 2. Constraints are separated into direct, copy, and complex.
119 Direct constraints are ADDRESSOF constraints that require no extra
120 processing, such as P = &Q
121 Copy constraints are those of the form P = Q.
122 Complex constraints are all the constraints involving dereferences.
124 3. All direct constraints of the form P = &Q are processed, such
125 that Q is added to Sol(P)
127 4. All complex constraints for a given constraint variable are stored in a
128 linked list attached to that variable's node.
130 5. A directed graph is built out of the copy constraints. Each
131 constraint variable is a node in the graph, and an edge from
132 Q to P is added for each copy constraint of the form P = Q
134 6. The graph is then walked, and solution sets are
135 propagated along the copy edges, such that an edge from Q to P
136 causes Sol(P) <- Sol(P) union Sol(Q).
138 7. As we visit each node, all complex constraints associated with
139 that node are processed by adding appropriate copy edges to the graph, or the
140 appropriate variables to the solution set.
142 8. The process of walking the graph is iterated until no solution
145 Prior to walking the graph in steps 6 and 7, We perform static
146 cycle elimination on the constraint graph, as well
147 as off-line variable substitution.
149 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
150 on and turned into anything), but isn't. You can just see what offset
151 inside the pointed-to struct it's going to access.
153 TODO: Constant bounded arrays can be handled as if they were structs of the
154 same number of elements.
156 TODO: Modeling heap and incoming pointers becomes much better if we
157 add fields to them as we discover them, which we could do.
159 TODO: We could handle unions, but to be honest, it's probably not
160 worth the pain or slowdown. */
162 static bool use_field_sensitive = true;
163 static unsigned int create_variable_info_for (tree, const char *);
164 static struct constraint_expr get_constraint_for (tree);
165 static void build_constraint_graph (void);
167 static bitmap_obstack ptabitmap_obstack;
168 static bitmap_obstack iteration_obstack;
169 DEF_VEC_P(constraint_t);
170 DEF_VEC_ALLOC_P(constraint_t,gc);
172 static struct constraint_stats
174 unsigned int total_vars;
175 unsigned int collapsed_vars;
176 unsigned int unified_vars_static;
177 unsigned int unified_vars_dynamic;
178 unsigned int iterations;
183 /* ID of this variable */
186 /* Name of this variable */
189 /* Tree that this variable is associated with. */
192 /* Offset of this variable, in bits, from the base variable */
193 unsigned HOST_WIDE_INT offset;
195 /* Size of the variable, in bits. */
196 unsigned HOST_WIDE_INT size;
198 /* Full size of the base variable, in bits. */
199 unsigned HOST_WIDE_INT fullsize;
201 /* A link to the variable for the next field in this structure. */
202 struct variable_info *next;
204 /* Node in the graph that represents the constraints and points-to
205 solution for the variable. */
208 /* True if the address of this variable is taken. Needed for
209 variable substitution. */
210 unsigned int address_taken:1;
212 /* True if this variable is the target of a dereference. Needed for
213 variable substitution. */
214 unsigned int indirect_target:1;
216 /* True if this is a variable created by the constraint analysis, such as
217 heap variables and constraints we had to break up. */
218 unsigned int is_artificial_var:1;
220 /* True for variables whose size is not known or variable. */
221 unsigned int is_unknown_size_var:1;
223 /* True for variables that have unions somewhere in them. */
224 unsigned int has_union:1;
226 /* Points-to set for this variable. */
229 /* Variable ids represented by this node. */
232 /* Vector of complex constraints for this node. Complex
233 constraints are those involving dereferences. */
234 VEC(constraint_t,gc) *complex;
236 typedef struct variable_info *varinfo_t;
238 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
240 /* Pool of variable info structures. */
241 static alloc_pool variable_info_pool;
243 DEF_VEC_P(varinfo_t);
245 DEF_VEC_ALLOC_P(varinfo_t, gc);
247 /* Table of variable info structures for constraint variables. Indexed directly
248 by variable info id. */
249 static VEC(varinfo_t,gc) *varmap;
250 #define get_varinfo(n) VEC_index(varinfo_t, varmap, n)
252 /* Variable that represents the unknown pointer. */
253 static varinfo_t var_anything;
254 static tree anything_tree;
255 static unsigned int anything_id;
257 /* Variable that represents the NULL pointer. */
258 static varinfo_t var_nothing;
259 static tree nothing_tree;
260 static unsigned int nothing_id;
262 /* Variable that represents read only memory. */
263 static varinfo_t var_readonly;
264 static tree readonly_tree;
265 static unsigned int readonly_id;
267 /* Variable that represents integers. This is used for when people do things
269 static varinfo_t var_integer;
270 static tree integer_tree;
271 static unsigned int integer_id;
274 /* Return a new variable info structure consisting for a variable
275 named NAME, and using constraint graph node NODE. */
278 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
280 varinfo_t ret = pool_alloc (variable_info_pool);
286 ret->address_taken = false;
287 ret->indirect_target = false;
288 ret->is_artificial_var = false;
289 ret->is_unknown_size_var = false;
290 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
291 bitmap_clear (ret->solution);
292 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
293 bitmap_clear (ret->variables);
299 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
301 /* An expression that appears in a constraint. */
303 struct constraint_expr
305 /* Constraint type. */
306 constraint_expr_type type;
308 /* Variable we are referring to in the constraint. */
311 /* Offset, in bits, of this constraint from the beginning of
312 variables it ends up referring to.
314 IOW, in a deref constraint, we would deref, get the result set,
315 then add OFFSET to each member. */
316 unsigned HOST_WIDE_INT offset;
319 static struct constraint_expr do_deref (struct constraint_expr);
321 /* Our set constraints are made up of two constraint expressions, one
324 As described in the introduction, our set constraints each represent an
325 operation between set valued variables.
329 struct constraint_expr lhs;
330 struct constraint_expr rhs;
333 /* List of constraints that we use to build the constraint graph from. */
335 static VEC(constraint_t,gc) *constraints;
336 static alloc_pool constraint_pool;
338 /* An edge in the constraint graph. We technically have no use for
339 the src, since it will always be the same node that we are indexing
340 into the pred/succ arrays with, but it's nice for checking
341 purposes. The edges are weighted, with a bit set in weights for
342 each edge from src to dest with that weight. */
344 struct constraint_edge
351 typedef struct constraint_edge *constraint_edge_t;
352 static alloc_pool constraint_edge_pool;
354 /* Return a new constraint edge from SRC to DEST. */
356 static constraint_edge_t
357 new_constraint_edge (unsigned int src, unsigned int dest)
359 constraint_edge_t ret = pool_alloc (constraint_edge_pool);
366 DEF_VEC_P(constraint_edge_t);
367 DEF_VEC_ALLOC_P(constraint_edge_t,gc);
370 /* The constraint graph is simply a set of adjacency vectors, one per
371 variable. succs[x] is the vector of successors for variable x, and preds[x]
372 is the vector of predecessors for variable x.
373 IOW, all edges are "forward" edges, which is not like our CFG.
375 preds[x]->src == x, and
378 struct constraint_graph
380 VEC(constraint_edge_t,gc) **succs;
381 VEC(constraint_edge_t,gc) **preds;
384 typedef struct constraint_graph *constraint_graph_t;
386 static constraint_graph_t graph;
388 /* Create a new constraint consisting of LHS and RHS expressions. */
391 new_constraint (const struct constraint_expr lhs,
392 const struct constraint_expr rhs)
394 constraint_t ret = pool_alloc (constraint_pool);
400 /* Print out constraint C to FILE. */
403 dump_constraint (FILE *file, constraint_t c)
405 if (c->lhs.type == ADDRESSOF)
407 else if (c->lhs.type == DEREF)
409 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
410 if (c->lhs.offset != 0)
411 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
412 fprintf (file, " = ");
413 if (c->rhs.type == ADDRESSOF)
415 else if (c->rhs.type == DEREF)
417 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
418 if (c->rhs.offset != 0)
419 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
420 fprintf (file, "\n");
423 /* Print out constraint C to stderr. */
426 debug_constraint (constraint_t c)
428 dump_constraint (stderr, c);
431 /* Print out all constraints to FILE */
434 dump_constraints (FILE *file)
438 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
439 dump_constraint (file, c);
442 /* Print out all constraints to stderr. */
445 debug_constraints (void)
447 dump_constraints (stderr);
452 The solver is a simple worklist solver, that works on the following
455 sbitmap changed_nodes = all ones;
456 changed_count = number of nodes;
457 For each node that was already collapsed:
461 while (changed_count > 0)
463 compute topological ordering for constraint graph
465 find and collapse cycles in the constraint graph (updating
466 changed if necessary)
468 for each node (n) in the graph in topological order:
471 Process each complex constraint associated with the node,
472 updating changed if necessary.
474 For each outgoing edge from n, propagate the solution from n to
475 the destination of the edge, updating changed as necessary.
479 /* Return true if two constraint expressions A and B are equal. */
482 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
484 return a.type == b.type
486 && a.offset == b.offset;
489 /* Return true if constraint expression A is less than constraint expression
490 B. This is just arbitrary, but consistent, in order to give them an
494 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
496 if (a.type == b.type)
499 return a.offset < b.offset;
501 return a.var < b.var;
504 return a.type < b.type;
507 /* Return true if constraint A is less than constraint B. This is just
508 arbitrary, but consistent, in order to give them an ordering. */
511 constraint_less (const constraint_t a, const constraint_t b)
513 if (constraint_expr_less (a->lhs, b->lhs))
515 else if (constraint_expr_less (b->lhs, a->lhs))
518 return constraint_expr_less (a->rhs, b->rhs);
521 /* Return true if two constraints A and B are equal. */
524 constraint_equal (struct constraint a, struct constraint b)
526 return constraint_expr_equal (a.lhs, b.lhs)
527 && constraint_expr_equal (a.rhs, b.rhs);
531 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
534 constraint_vec_find (VEC(constraint_t,gc) *vec,
535 struct constraint lookfor)
543 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
544 if (place >= VEC_length (constraint_t, vec))
546 found = VEC_index (constraint_t, vec, place);
547 if (!constraint_equal (*found, lookfor))
552 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
555 constraint_set_union (VEC(constraint_t,gc) **to,
556 VEC(constraint_t,gc) **from)
561 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
563 if (constraint_vec_find (*to, *c) == NULL)
565 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
567 VEC_safe_insert (constraint_t, gc, *to, place, c);
572 /* Take a solution set SET, add OFFSET to each member of the set, and
573 overwrite SET with the result when done. */
576 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
578 bitmap result = BITMAP_ALLOC (&iteration_obstack);
582 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
584 /* If this is a properly sized variable, only add offset if it's
585 less than end. Otherwise, it is globbed to a single
588 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
590 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
591 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
592 bitmap_set_bit (result, v->id);
594 else if (get_varinfo (i)->is_artificial_var
595 || get_varinfo (i)->is_unknown_size_var)
597 bitmap_set_bit (result, i);
601 bitmap_copy (set, result);
602 BITMAP_FREE (result);
605 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
609 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
612 return bitmap_ior_into (to, from);
618 tmp = BITMAP_ALLOC (&iteration_obstack);
619 bitmap_copy (tmp, from);
620 solution_set_add (tmp, inc);
621 res = bitmap_ior_into (to, tmp);
627 /* Insert constraint C into the list of complex constraints for VAR. */
630 insert_into_complex (unsigned int var, constraint_t c)
632 varinfo_t vi = get_varinfo (var);
633 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
635 VEC_safe_insert (constraint_t, gc, vi->complex, place, c);
639 /* Compare two constraint edges A and B, return true if they are equal. */
642 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
644 return a.src == b.src && a.dest == b.dest;
647 /* Compare two constraint edges, return true if A is less than B */
650 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
652 if (a->dest < b->dest)
654 else if (a->dest == b->dest)
655 return a->src < b->src;
660 /* Find the constraint edge that matches LOOKFOR, in VEC.
661 Return the edge, if found, NULL otherwise. */
663 static constraint_edge_t
664 constraint_edge_vec_find (VEC(constraint_edge_t,gc) *vec,
665 struct constraint_edge lookfor)
668 constraint_edge_t edge;
670 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
671 constraint_edge_less);
672 edge = VEC_index (constraint_edge_t, vec, place);
673 if (!constraint_edge_equal (*edge, lookfor))
678 /* Condense two variable nodes into a single variable node, by moving
679 all associated info from SRC to TO. */
682 condense_varmap_nodes (unsigned int to, unsigned int src)
684 varinfo_t tovi = get_varinfo (to);
685 varinfo_t srcvi = get_varinfo (src);
690 /* the src node, and all its variables, are now the to node. */
692 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
693 get_varinfo (i)->node = to;
695 /* Merge the src node variables and the to node variables. */
696 bitmap_set_bit (tovi->variables, src);
697 bitmap_ior_into (tovi->variables, srcvi->variables);
698 bitmap_clear (srcvi->variables);
700 /* Move all complex constraints from src node into to node */
701 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
703 /* In complex constraints for node src, we may have either
704 a = *src, and *src = a. */
706 if (c->rhs.type == DEREF)
711 constraint_set_union (&tovi->complex, &srcvi->complex);
712 srcvi->complex = NULL;
715 /* Erase EDGE from GRAPH. This routine only handles self-edges
716 (e.g. an edge from a to a). */
719 erase_graph_self_edge (constraint_graph_t graph, struct constraint_edge edge)
721 VEC(constraint_edge_t,gc) *predvec = graph->preds[edge.src];
722 VEC(constraint_edge_t,gc) *succvec = graph->succs[edge.dest];
724 gcc_assert (edge.src == edge.dest);
726 /* Remove from the successors. */
727 place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
728 constraint_edge_less);
730 /* Make sure we found the edge. */
731 #ifdef ENABLE_CHECKING
733 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
734 gcc_assert (constraint_edge_equal (*tmp, edge));
737 VEC_ordered_remove (constraint_edge_t, succvec, place);
739 /* Remove from the predecessors. */
740 place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
741 constraint_edge_less);
743 /* Make sure we found the edge. */
744 #ifdef ENABLE_CHECKING
746 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
747 gcc_assert (constraint_edge_equal (*tmp, edge));
750 VEC_ordered_remove (constraint_edge_t, predvec, place);
753 /* Remove edges involving NODE from GRAPH. */
756 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
758 VEC(constraint_edge_t,gc) *succvec = graph->succs[node];
759 VEC(constraint_edge_t,gc) *predvec = graph->preds[node];
763 /* Walk the successors, erase the associated preds. */
764 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
768 struct constraint_edge lookfor;
769 lookfor.src = c->dest;
771 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
772 &lookfor, constraint_edge_less);
773 VEC_ordered_remove (constraint_edge_t, graph->preds[c->dest], place);
775 /* Walk the preds, erase the associated succs. */
776 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
780 struct constraint_edge lookfor;
781 lookfor.src = c->dest;
783 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
784 &lookfor, constraint_edge_less);
785 VEC_ordered_remove (constraint_edge_t, graph->succs[c->dest], place);
788 graph->preds[node] = NULL;
789 graph->succs[node] = NULL;
792 static bool edge_added = false;
794 /* Add edge NEWE to the graph. */
797 add_graph_edge (constraint_graph_t graph, struct constraint_edge newe)
800 unsigned int src = newe.src;
801 unsigned int dest = newe.dest;
802 VEC(constraint_edge_t,gc) *vec;
804 vec = graph->preds[src];
805 place = VEC_lower_bound (constraint_edge_t, vec, &newe,
806 constraint_edge_less);
807 if (place == VEC_length (constraint_edge_t, vec)
808 || VEC_index (constraint_edge_t, vec, place)->dest != dest)
810 constraint_edge_t edge = new_constraint_edge (src, dest);
813 weightbitmap = BITMAP_ALLOC (&ptabitmap_obstack);
814 edge->weights = weightbitmap;
815 VEC_safe_insert (constraint_edge_t, gc, graph->preds[edge->src],
817 edge = new_constraint_edge (dest, src);
818 edge->weights = weightbitmap;
819 place = VEC_lower_bound (constraint_edge_t, graph->succs[edge->src],
820 edge, constraint_edge_less);
821 VEC_safe_insert (constraint_edge_t, gc, graph->succs[edge->src],
831 /* Return the bitmap representing the weights of edge LOOKFOR */
834 get_graph_weights (constraint_graph_t graph, struct constraint_edge lookfor)
836 constraint_edge_t edge;
837 unsigned int src = lookfor.src;
838 VEC(constraint_edge_t,gc) *vec;
839 vec = graph->preds[src];
840 edge = constraint_edge_vec_find (vec, lookfor);
841 gcc_assert (edge != NULL);
842 return edge->weights;
846 /* Merge GRAPH nodes FROM and TO into node TO. */
849 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
852 VEC(constraint_edge_t,gc) *succvec = graph->succs[from];
853 VEC(constraint_edge_t,gc) *predvec = graph->preds[from];
857 /* Merge all the predecessor edges. */
859 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
861 unsigned int d = c->dest;
862 struct constraint_edge olde;
863 struct constraint_edge newe;
870 add_graph_edge (graph, newe);
873 temp = get_graph_weights (graph, olde);
874 weights = get_graph_weights (graph, newe);
875 bitmap_ior_into (weights, temp);
878 /* Merge all the successor edges. */
879 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
881 unsigned int d = c->dest;
882 struct constraint_edge olde;
883 struct constraint_edge newe;
890 add_graph_edge (graph, newe);
893 temp = get_graph_weights (graph, olde);
894 weights = get_graph_weights (graph, newe);
895 bitmap_ior_into (weights, temp);
897 clear_edges_for_node (graph, from);
900 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
901 it doesn't exist in the graph already.
902 Return false if the edge already existed, true otherwise. */
905 int_add_graph_edge (constraint_graph_t graph, unsigned int to,
906 unsigned int from, unsigned HOST_WIDE_INT weight)
908 if (to == from && weight == 0)
915 struct constraint_edge edge;
918 r = add_graph_edge (graph, edge);
919 r |= !bitmap_bit_p (get_graph_weights (graph, edge), weight);
920 bitmap_set_bit (get_graph_weights (graph, edge), weight);
926 /* Return true if LOOKFOR is an existing graph edge. */
929 valid_graph_edge (constraint_graph_t graph, struct constraint_edge lookfor)
931 return constraint_edge_vec_find (graph->preds[lookfor.src], lookfor) != NULL;
935 /* Build the constraint graph. */
938 build_constraint_graph (void)
943 graph = ggc_alloc (sizeof (struct constraint_graph));
944 graph->succs = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->succs));
945 graph->preds = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->preds));
946 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
948 struct constraint_expr lhs = c->lhs;
949 struct constraint_expr rhs = c->rhs;
950 if (lhs.type == DEREF)
952 /* *x = y or *x = &y (complex) */
953 if (rhs.type == ADDRESSOF || rhs.var > anything_id)
954 insert_into_complex (lhs.var, c);
956 else if (rhs.type == DEREF)
959 if (lhs.var > anything_id)
960 insert_into_complex (rhs.var, c);
962 else if (rhs.type == ADDRESSOF)
965 bitmap_set_bit (get_varinfo (lhs.var)->solution, rhs.var);
967 else if (rhs.var > anything_id && lhs.var > anything_id)
969 /* Ignore 0 weighted self edges, as they can't possibly contribute
971 if (lhs.var != rhs.var || rhs.offset != 0 || lhs.offset != 0)
974 struct constraint_edge edge;
978 add_graph_edge (graph, edge);
979 bitmap_set_bit (get_graph_weights (graph, edge),
986 /* Changed variables on the last iteration. */
987 static unsigned int changed_count;
988 static sbitmap changed;
991 DEF_VEC_ALLOC_I(unsigned,heap);
994 /* Strongly Connected Component visitation info. */
999 sbitmap in_component;
1001 unsigned int *visited_index;
1002 VEC(unsigned,heap) *scc_stack;
1003 VEC(unsigned,heap) *unification_queue;
1007 /* Recursive routine to find strongly connected components in GRAPH.
1008 SI is the SCC info to store the information in, and N is the id of current
1009 graph node we are processing.
1011 This is Tarjan's strongly connected component finding algorithm, as
1012 modified by Nuutila to keep only non-root nodes on the stack.
1013 The algorithm can be found in "On finding the strongly connected
1014 connected components in a directed graph" by Esko Nuutila and Eljas
1015 Soisalon-Soininen, in Information Processing Letters volume 49,
1016 number 1, pages 9-14. */
1019 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1021 constraint_edge_t c;
1024 gcc_assert (get_varinfo (n)->node == n);
1025 SET_BIT (si->visited, n);
1026 RESET_BIT (si->in_component, n);
1027 si->visited_index[n] = si->current_index ++;
1029 /* Visit all the successors. */
1030 for (i = 0; VEC_iterate (constraint_edge_t, graph->succs[n], i, c); i++)
1032 /* We only want to find and collapse the zero weight edges. */
1033 if (bitmap_bit_p (c->weights, 0))
1035 unsigned int w = c->dest;
1036 if (!TEST_BIT (si->visited, w))
1037 scc_visit (graph, si, w);
1038 if (!TEST_BIT (si->in_component, w))
1040 unsigned int t = get_varinfo (w)->node;
1041 unsigned int nnode = get_varinfo (n)->node;
1042 if (si->visited_index[t] < si->visited_index[nnode])
1043 get_varinfo (n)->node = t;
1048 /* See if any components have been identified. */
1049 if (get_varinfo (n)->node == n)
1051 unsigned int t = si->visited_index[n];
1052 SET_BIT (si->in_component, n);
1053 while (VEC_length (unsigned, si->scc_stack) != 0
1054 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1056 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1057 get_varinfo (w)->node = n;
1058 SET_BIT (si->in_component, w);
1059 /* Mark this node for collapsing. */
1060 VEC_safe_push (unsigned, heap, si->unification_queue, w);
1064 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1068 /* Collapse two variables into one variable. */
1071 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1073 bitmap tosol, fromsol;
1074 struct constraint_edge edge;
1077 condense_varmap_nodes (to, from);
1078 tosol = get_varinfo (to)->solution;
1079 fromsol = get_varinfo (from)->solution;
1080 bitmap_ior_into (tosol, fromsol);
1081 merge_graph_nodes (graph, to, from);
1084 if (valid_graph_edge (graph, edge))
1086 bitmap weights = get_graph_weights (graph, edge);
1087 bitmap_clear_bit (weights, 0);
1088 if (bitmap_empty_p (weights))
1089 erase_graph_self_edge (graph, edge);
1091 bitmap_clear (fromsol);
1092 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1093 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1097 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1098 SI is the Strongly Connected Components information structure that tells us
1099 what components to unify.
1100 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1101 count should be updated to reflect the unification. */
1104 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1105 bool update_changed)
1108 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1111 /* We proceed as follows:
1113 For each component in the queue (components are delineated by
1114 when current_queue_element->node != next_queue_element->node):
1116 rep = representative node for component
1118 For each node (tounify) to be unified in the component,
1119 merge the solution for tounify into tmp bitmap
1121 clear solution for tounify
1123 merge edges from tounify into rep
1125 merge complex constraints from tounify into rep
1127 update changed count to note that tounify will never change
1130 Merge tmp into solution for rep, marking rep changed if this
1131 changed rep's solution.
1133 Delete any 0 weighted self-edges we now have for rep. */
1134 while (i != VEC_length (unsigned, si->unification_queue))
1136 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1137 unsigned int n = get_varinfo (tounify)->node;
1139 if (dump_file && (dump_flags & TDF_DETAILS))
1140 fprintf (dump_file, "Unifying %s to %s\n",
1141 get_varinfo (tounify)->name,
1142 get_varinfo (n)->name);
1144 stats.unified_vars_dynamic++;
1146 stats.unified_vars_static++;
1147 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1148 merge_graph_nodes (graph, n, tounify);
1149 condense_varmap_nodes (n, tounify);
1151 if (update_changed && TEST_BIT (changed, tounify))
1153 RESET_BIT (changed, tounify);
1154 if (!TEST_BIT (changed, n))
1155 SET_BIT (changed, n);
1158 gcc_assert (changed_count > 0);
1163 bitmap_clear (get_varinfo (tounify)->solution);
1166 /* If we've either finished processing the entire queue, or
1167 finished processing all nodes for component n, update the solution for
1169 if (i == VEC_length (unsigned, si->unification_queue)
1170 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1172 struct constraint_edge edge;
1174 /* If the solution changes because of the merging, we need to mark
1175 the variable as changed. */
1176 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1178 if (update_changed && !TEST_BIT (changed, n))
1180 SET_BIT (changed, n);
1187 if (valid_graph_edge (graph, edge))
1189 bitmap weights = get_graph_weights (graph, edge);
1190 bitmap_clear_bit (weights, 0);
1191 if (bitmap_empty_p (weights))
1192 erase_graph_self_edge (graph, edge);
1200 /* Information needed to compute the topological ordering of a graph. */
1204 /* sbitmap of visited nodes. */
1206 /* Array that stores the topological order of the graph, *in
1208 VEC(unsigned,heap) *topo_order;
1212 /* Initialize and return a topological info structure. */
1214 static struct topo_info *
1215 init_topo_info (void)
1217 size_t size = VEC_length (varinfo_t, varmap);
1218 struct topo_info *ti = xmalloc (sizeof (struct topo_info));
1219 ti->visited = sbitmap_alloc (size);
1220 sbitmap_zero (ti->visited);
1221 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1226 /* Free the topological sort info pointed to by TI. */
1229 free_topo_info (struct topo_info *ti)
1231 sbitmap_free (ti->visited);
1232 VEC_free (unsigned, heap, ti->topo_order);
1236 /* Visit the graph in topological order, and store the order in the
1237 topo_info structure. */
1240 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1243 VEC(constraint_edge_t,gc) *succs = graph->succs[n];
1244 constraint_edge_t c;
1246 SET_BIT (ti->visited, n);
1247 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1249 if (!TEST_BIT (ti->visited, c->dest))
1250 topo_visit (graph, ti, c->dest);
1252 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1255 /* Return true if variable N + OFFSET is a legal field of N. */
1258 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1260 varinfo_t ninfo = get_varinfo (n);
1262 /* For things we've globbed to single variables, any offset into the
1263 variable acts like the entire variable, so that it becomes offset
1265 if (n == anything_id
1266 || ninfo->is_artificial_var
1267 || ninfo->is_unknown_size_var)
1272 return n > anything_id
1273 && (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1276 /* Process a constraint C that represents *x = &y. */
1279 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1280 constraint_t c, bitmap delta)
1282 unsigned int rhs = c->rhs.var;
1283 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1287 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1288 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1290 if (type_safe (j, &offset))
1292 /* *x != NULL && *x != ANYTHING*/
1296 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1297 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1299 sol = get_varinfo (t)->solution;
1300 if (!bitmap_bit_p (sol, rhs))
1302 bitmap_set_bit (sol, rhs);
1303 if (!TEST_BIT (changed, t))
1305 SET_BIT (changed, t);
1311 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1316 /* Process a constraint C that represents x = *y, using DELTA as the
1317 starting solution. */
1320 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1323 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1324 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1326 bitmap sol = get_varinfo (lhs)->solution;
1330 /* For each variable j in delta (Sol(y)), add
1331 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1332 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1334 if (type_safe (j, &roffset))
1337 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1340 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1342 if (int_add_graph_edge (graph, lhs, t, 0))
1343 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1346 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1350 /* If the LHS solution changed, mark the var as changed. */
1353 get_varinfo (lhs)->solution = sol;
1354 if (!TEST_BIT (changed, lhs))
1356 SET_BIT (changed, lhs);
1362 /* Process a constraint C that represents *x = y. */
1365 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1367 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1368 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1369 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1370 bitmap sol = get_varinfo (rhs)->solution;
1374 /* For each member j of delta (Sol(x)), add an edge from y to j and
1375 union Sol(y) into Sol(j) */
1376 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1378 if (type_safe (j, &loff))
1382 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1384 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1386 if (int_add_graph_edge (graph, t, rhs, roff))
1388 bitmap tmp = get_varinfo (t)->solution;
1389 if (set_union_with_increment (tmp, sol, roff))
1391 get_varinfo (t)->solution = tmp;
1394 sol = get_varinfo (rhs)->solution;
1396 if (!TEST_BIT (changed, t))
1398 SET_BIT (changed, t);
1405 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1409 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1410 constraint (IE *x = &y, x = *y, and *x = y). */
1413 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1415 if (c->lhs.type == DEREF)
1417 if (c->rhs.type == ADDRESSOF)
1420 do_da_constraint (graph, c, delta);
1425 do_ds_constraint (graph, c, delta);
1431 do_sd_constraint (graph, c, delta);
1435 /* Initialize and return a new SCC info structure. */
1437 static struct scc_info *
1438 init_scc_info (void)
1440 struct scc_info *si = xmalloc (sizeof (struct scc_info));
1441 size_t size = VEC_length (varinfo_t, varmap);
1443 si->current_index = 0;
1444 si->visited = sbitmap_alloc (size);
1445 sbitmap_zero (si->visited);
1446 si->in_component = sbitmap_alloc (size);
1447 sbitmap_ones (si->in_component);
1448 si->visited_index = xcalloc (sizeof (unsigned int), size + 1);
1449 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1450 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1454 /* Free an SCC info structure pointed to by SI */
1457 free_scc_info (struct scc_info *si)
1459 sbitmap_free (si->visited);
1460 sbitmap_free (si->in_component);
1461 free (si->visited_index);
1462 VEC_free (unsigned, heap, si->scc_stack);
1463 VEC_free (unsigned, heap, si->unification_queue);
1468 /* Find cycles in GRAPH that occur, using strongly connected components, and
1469 collapse the cycles into a single representative node. if UPDATE_CHANGED
1470 is true, then update the changed sbitmap to note those nodes whose
1471 solutions have changed as a result of collapsing. */
1474 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1477 unsigned int size = VEC_length (varinfo_t, varmap);
1478 struct scc_info *si = init_scc_info ();
1480 for (i = 0; i != size; ++i)
1481 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1482 scc_visit (graph, si, i);
1483 process_unification_queue (graph, si, update_changed);
1487 /* Compute a topological ordering for GRAPH, and store the result in the
1488 topo_info structure TI. */
1491 compute_topo_order (constraint_graph_t graph,
1492 struct topo_info *ti)
1495 unsigned int size = VEC_length (varinfo_t, varmap);
1497 for (i = 0; i != size; ++i)
1498 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1499 topo_visit (graph, ti, i);
1502 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1505 bitmap_other_than_zero_bit_set (bitmap b)
1510 if (bitmap_empty_p (b))
1512 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1517 /* Perform offline variable substitution.
1519 This is a linear time way of identifying variables that must have
1520 equivalent points-to sets, including those caused by static cycles,
1521 and single entry subgraphs, in the constraint graph.
1523 The technique is described in "Off-line variable substitution for
1524 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1525 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1528 perform_var_substitution (constraint_graph_t graph)
1530 struct topo_info *ti = init_topo_info ();
1532 /* Compute the topological ordering of the graph, then visit each
1533 node in topological order. */
1534 compute_topo_order (graph, ti);
1536 while (VEC_length (unsigned, ti->topo_order) != 0)
1538 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1540 varinfo_t vi = get_varinfo (i);
1541 bool okay_to_elim = false;
1542 unsigned int root = VEC_length (varinfo_t, varmap);
1543 VEC(constraint_edge_t,gc) *predvec = graph->preds[i];
1544 constraint_edge_t ce;
1547 /* We can't eliminate things whose address is taken, or which is
1548 the target of a dereference. */
1549 if (vi->address_taken || vi->indirect_target)
1552 /* See if all predecessors of I are ripe for elimination */
1553 for (pred = 0; VEC_iterate (constraint_edge_t, predvec, pred, ce); pred++)
1557 weight = get_graph_weights (graph, *ce);
1559 /* We can't eliminate variables that have non-zero weighted
1560 edges between them. */
1561 if (bitmap_other_than_zero_bit_set (weight))
1563 okay_to_elim = false;
1566 w = get_varinfo (ce->dest)->node;
1568 /* We can't eliminate the node if one of the predecessors is
1569 part of a different strongly connected component. */
1573 okay_to_elim = true;
1577 okay_to_elim = false;
1581 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1582 then Solution(i) is a subset of Solution (w), where w is a
1583 predecessor in the graph.
1584 Corollary: If all predecessors of i have the same
1585 points-to set, then i has that same points-to set as
1586 those predecessors. */
1587 tmp = BITMAP_ALLOC (NULL);
1588 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1589 get_varinfo (w)->solution);
1590 if (!bitmap_empty_p (tmp))
1592 okay_to_elim = false;
1599 /* See if the root is different than the original node.
1600 If so, we've found an equivalence. */
1601 if (root != get_varinfo (i)->node && okay_to_elim)
1603 /* Found an equivalence */
1604 get_varinfo (i)->node = root;
1605 collapse_nodes (graph, root, i);
1606 if (dump_file && (dump_flags & TDF_DETAILS))
1607 fprintf (dump_file, "Collapsing %s into %s\n",
1608 get_varinfo (i)->name,
1609 get_varinfo (root)->name);
1610 stats.collapsed_vars++;
1614 free_topo_info (ti);
1618 /* Solve the constraint graph GRAPH using our worklist solver.
1619 This is based on the PW* family of solvers from the "Efficient Field
1620 Sensitive Pointer Analysis for C" paper.
1621 It works by iterating over all the graph nodes, processing the complex
1622 constraints and propagating the copy constraints, until everything stops
1623 changed. This corresponds to steps 6-8 in the solving list given above. */
1626 solve_graph (constraint_graph_t graph)
1628 unsigned int size = VEC_length (varinfo_t, varmap);
1631 changed_count = size;
1632 changed = sbitmap_alloc (size);
1633 sbitmap_ones (changed);
1635 /* The already collapsed/unreachable nodes will never change, so we
1636 need to account for them in changed_count. */
1637 for (i = 0; i < size; i++)
1638 if (get_varinfo (i)->node != i)
1641 while (changed_count > 0)
1644 struct topo_info *ti = init_topo_info ();
1647 bitmap_obstack_initialize (&iteration_obstack);
1651 /* We already did cycle elimination once, when we did
1652 variable substitution, so we don't need it again for the
1654 if (stats.iterations > 1)
1655 find_and_collapse_graph_cycles (graph, true);
1660 compute_topo_order (graph, ti);
1662 while (VEC_length (unsigned, ti->topo_order) != 0)
1664 i = VEC_pop (unsigned, ti->topo_order);
1665 gcc_assert (get_varinfo (i)->node == i);
1667 /* If the node has changed, we need to process the
1668 complex constraints and outgoing edges again. */
1669 if (TEST_BIT (changed, i))
1673 constraint_edge_t e;
1675 VEC(constraint_t,gc) *complex = get_varinfo (i)->complex;
1676 VEC(constraint_edge_t,gc) *succs;
1678 RESET_BIT (changed, i);
1681 /* Process the complex constraints */
1682 solution = get_varinfo (i)->solution;
1683 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
1684 do_complex_constraint (graph, c, solution);
1686 /* Propagate solution to all successors. */
1687 succs = graph->succs[i];
1688 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
1690 bitmap tmp = get_varinfo (e->dest)->solution;
1693 bitmap weights = e->weights;
1696 gcc_assert (!bitmap_empty_p (weights));
1697 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
1698 flag |= set_union_with_increment (tmp, solution, k);
1702 get_varinfo (e->dest)->solution = tmp;
1703 if (!TEST_BIT (changed, e->dest))
1705 SET_BIT (changed, e->dest);
1712 free_topo_info (ti);
1713 bitmap_obstack_release (&iteration_obstack);
1716 sbitmap_free (changed);
1720 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1722 /* Map from trees to variable ids. */
1723 static htab_t id_for_tree;
1725 typedef struct tree_id
1731 /* Hash a tree id structure. */
1734 tree_id_hash (const void *p)
1736 const tree_id_t ta = (tree_id_t) p;
1737 return htab_hash_pointer (ta->t);
1740 /* Return true if the tree in P1 and the tree in P2 are the same. */
1743 tree_id_eq (const void *p1, const void *p2)
1745 const tree_id_t ta1 = (tree_id_t) p1;
1746 const tree_id_t ta2 = (tree_id_t) p2;
1747 return ta1->t == ta2->t;
1750 /* Insert ID as the variable id for tree T in the hashtable. */
1753 insert_id_for_tree (tree t, int id)
1756 struct tree_id finder;
1760 slot = htab_find_slot (id_for_tree, &finder, INSERT);
1761 gcc_assert (*slot == NULL);
1762 new_pair = xmalloc (sizeof (struct tree_id));
1765 *slot = (void *)new_pair;
1768 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1769 exist in the hash table, return false, otherwise, return true and
1770 set *ID to the id we found. */
1773 lookup_id_for_tree (tree t, unsigned int *id)
1776 struct tree_id finder;
1779 pair = htab_find (id_for_tree, &finder);
1786 /* Return a printable name for DECL */
1789 alias_get_name (tree decl)
1791 const char *res = get_name (decl);
1793 int num_printed = 0;
1799 if (TREE_CODE (decl) == SSA_NAME)
1801 num_printed = asprintf (&temp, "%s_%u",
1802 alias_get_name (SSA_NAME_VAR (decl)),
1803 SSA_NAME_VERSION (decl));
1805 else if (DECL_P (decl))
1807 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
1809 if (num_printed > 0)
1811 res = ggc_strdup (temp);
1817 /* Find the variable id for tree T in the hashtable.
1818 If T doesn't exist in the hash table, create an entry for it. */
1821 get_id_for_tree (tree t)
1824 struct tree_id finder;
1827 pair = htab_find (id_for_tree, &finder);
1829 return create_variable_info_for (t, alias_get_name (t));
1834 /* Get a constraint expression from an SSA_VAR_P node. */
1836 static struct constraint_expr
1837 get_constraint_exp_from_ssa_var (tree t)
1839 struct constraint_expr cexpr;
1841 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
1843 /* For parameters, get at the points-to set for the actual parm
1845 if (TREE_CODE (t) == SSA_NAME
1846 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
1847 && default_def (SSA_NAME_VAR (t)) == t)
1848 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
1850 cexpr.type = SCALAR;
1852 if (TREE_READONLY (t))
1854 cexpr.type = ADDRESSOF;
1855 cexpr.var = readonly_id;
1858 cexpr.var = get_id_for_tree (t);
1864 /* Process a completed constraint T, and add it to the constraint
1868 process_constraint (constraint_t t)
1870 struct constraint_expr rhs = t->rhs;
1871 struct constraint_expr lhs = t->lhs;
1873 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
1874 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
1876 /* ANYTHING == ANYTHING is pointless. */
1877 if (lhs.var == anything_id && rhs.var == anything_id)
1880 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1881 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
1886 process_constraint (t);
1888 /* This can happen in our IR with things like n->a = *p */
1889 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
1891 /* Split into tmp = *rhs, *lhs = tmp */
1892 tree rhsdecl = get_varinfo (rhs.var)->decl;
1893 tree pointertype = TREE_TYPE (rhsdecl);
1894 tree pointedtotype = TREE_TYPE (pointertype);
1895 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
1896 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
1898 /* If this is an aggregate of known size, we should have passed
1899 this off to do_structure_copy, and it should have broken it
1901 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
1902 || get_varinfo (rhs.var)->is_unknown_size_var);
1904 process_constraint (new_constraint (tmplhs, rhs));
1905 process_constraint (new_constraint (lhs, tmplhs));
1907 else if (rhs.type == ADDRESSOF)
1910 gcc_assert (rhs.offset == 0);
1912 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
1913 vi->address_taken = true;
1915 VEC_safe_push (constraint_t, gc, constraints, t);
1919 if (lhs.type != DEREF && rhs.type == DEREF)
1920 get_varinfo (lhs.var)->indirect_target = true;
1921 VEC_safe_push (constraint_t, gc, constraints, t);
1926 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1929 static unsigned HOST_WIDE_INT
1930 bitpos_of_field (const tree fdecl)
1933 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
1934 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
1937 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
1938 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
1942 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1943 overlaps with a field at [FIELDPOS, FIELDSIZE] */
1946 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
1947 const unsigned HOST_WIDE_INT fieldsize,
1948 const unsigned HOST_WIDE_INT accesspos,
1949 const unsigned HOST_WIDE_INT accesssize)
1951 if (fieldpos == accesspos && fieldsize == accesssize)
1953 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
1955 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
1961 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1963 static struct constraint_expr
1964 get_constraint_for_component_ref (tree t)
1966 struct constraint_expr result;
1967 HOST_WIDE_INT bitsize;
1968 HOST_WIDE_INT bitpos;
1970 enum machine_mode mode;
1976 result.type = SCALAR;
1979 /* Some people like to do cute things like take the address of
1982 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
1983 forzero = TREE_OPERAND (forzero, 0);
1985 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
1988 result.var = integer_id;
1989 result.type = SCALAR;
1993 t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode,
1994 &unsignedp, &volatilep, false);
1995 result = get_constraint_for (t);
1997 /* This can also happen due to weird offsetof type macros. */
1998 if (TREE_CODE (t) != ADDR_EXPR && result.type == ADDRESSOF)
1999 result.type = SCALAR;
2001 /* If we know where this goes, then yay. Otherwise, booo. */
2003 if (offset == NULL && bitsize != -1)
2005 result.offset = bitpos;
2009 result.var = anything_id;
2013 if (result.type == SCALAR)
2015 /* In languages like C, you can access one past the end of an
2016 array. You aren't allowed to dereference it, so we can
2017 ignore this constraint. When we handle pointer subtraction,
2018 we may have to do something cute here. */
2020 if (result.offset < get_varinfo (result.var)->fullsize)
2022 /* It's also not true that the constraint will actually start at the
2023 right offset, it may start in some padding. We only care about
2024 setting the constraint to the first actual field it touches, so
2027 for (curr = get_varinfo (result.var); curr; curr = curr->next)
2029 if (offset_overlaps_with_access (curr->offset, curr->size,
2030 result.offset, bitsize))
2032 result.var = curr->id;
2037 /* assert that we found *some* field there. The user couldn't be
2038 accessing *only* padding. */
2043 if (dump_file && (dump_flags & TDF_DETAILS))
2044 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2053 /* Dereference the constraint expression CONS, and return the result.
2054 DEREF (ADDRESSOF) = SCALAR
2055 DEREF (SCALAR) = DEREF
2056 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2057 This is needed so that we can handle dereferencing DEREF constraints. */
2059 static struct constraint_expr
2060 do_deref (struct constraint_expr cons)
2062 if (cons.type == SCALAR)
2067 else if (cons.type == ADDRESSOF)
2072 else if (cons.type == DEREF)
2074 tree tmpvar = create_tmp_var_raw (ptr_type_node, "derefmp");
2075 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2076 process_constraint (new_constraint (tmplhs, cons));
2077 cons.var = tmplhs.var;
2084 /* Given a tree T, return the constraint expression for it. */
2086 static struct constraint_expr
2087 get_constraint_for (tree t)
2089 struct constraint_expr temp;
2091 /* x = integer is all glommed to a single variable, which doesn't
2092 point to anything by itself. That is, of course, unless it is an
2093 integer constant being treated as a pointer, in which case, we
2094 will return that this is really the addressof anything. This
2095 happens below, since it will fall into the default case. The only
2096 case we know something about an integer treated like a pointer is
2097 when it is the NULL pointer, and then we just say it points to
2099 if (TREE_CODE (t) == INTEGER_CST
2100 && !POINTER_TYPE_P (TREE_TYPE (t)))
2102 temp.var = integer_id;
2107 else if (TREE_CODE (t) == INTEGER_CST
2108 && integer_zerop (t))
2110 temp.var = nothing_id;
2111 temp.type = ADDRESSOF;
2116 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2118 case tcc_expression:
2120 switch (TREE_CODE (t))
2124 temp = get_constraint_for (TREE_OPERAND (t, 0));
2125 if (temp.type == DEREF)
2128 temp.type = ADDRESSOF;
2134 /* XXX: In interprocedural mode, if we didn't have the
2135 body, we would need to do *each pointer argument =
2137 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2139 tree heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2140 temp.var = create_variable_info_for (heapvar,
2141 alias_get_name (heapvar));
2143 get_varinfo (temp.var)->is_artificial_var = 1;
2144 temp.type = ADDRESSOF;
2151 temp.type = ADDRESSOF;
2152 temp.var = anything_id;
2160 switch (TREE_CODE (t))
2164 temp = get_constraint_for (TREE_OPERAND (t, 0));
2165 temp = do_deref (temp);
2170 temp = get_constraint_for_component_ref (t);
2174 temp.type = ADDRESSOF;
2175 temp.var = anything_id;
2183 switch (TREE_CODE (t))
2187 case NON_LVALUE_EXPR:
2189 tree op = TREE_OPERAND (t, 0);
2191 /* Cast from non-pointer to pointers are bad news for us.
2192 Anything else, we see through */
2193 if (!(POINTER_TYPE_P (TREE_TYPE (t)) &&
2194 ! POINTER_TYPE_P (TREE_TYPE (op))))
2195 return get_constraint_for (op);
2199 temp.type = ADDRESSOF;
2200 temp.var = anything_id;
2206 case tcc_exceptional:
2208 switch (TREE_CODE (t))
2211 return get_constraint_for (PHI_RESULT (t));
2213 return get_constraint_exp_from_ssa_var (t);
2216 temp.type = ADDRESSOF;
2217 temp.var = anything_id;
2223 case tcc_declaration:
2224 return get_constraint_exp_from_ssa_var (t);
2227 temp.type = ADDRESSOF;
2228 temp.var = anything_id;
2236 /* Handle the structure copy case where we have a simple structure copy
2237 between LHS and RHS that is of SIZE (in bits)
2239 For each field of the lhs variable (lhsfield)
2240 For each field of the rhs variable at lhsfield.offset (rhsfield)
2241 add the constraint lhsfield = rhsfield
2245 do_simple_structure_copy (const struct constraint_expr lhs,
2246 const struct constraint_expr rhs,
2247 const unsigned HOST_WIDE_INT size)
2249 varinfo_t p = get_varinfo (lhs.var);
2250 unsigned HOST_WIDE_INT pstart, last;
2252 last = p->offset + size;
2253 for (; p && p->offset < last; p = p->next)
2256 struct constraint_expr templhs = lhs;
2257 struct constraint_expr temprhs = rhs;
2258 unsigned HOST_WIDE_INT fieldoffset;
2260 templhs.var = p->id;
2261 q = get_varinfo (temprhs.var);
2262 fieldoffset = p->offset - pstart;
2263 q = first_vi_for_offset (q, q->offset + fieldoffset);
2264 temprhs.var = q->id;
2265 process_constraint (new_constraint (templhs, temprhs));
2270 /* Handle the structure copy case where we have a structure copy between a
2271 aggregate on the LHS and a dereference of a pointer on the RHS
2272 that is of SIZE (in bits)
2274 For each field of the lhs variable (lhsfield)
2275 rhs.offset = lhsfield->offset
2276 add the constraint lhsfield = rhs
2280 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2281 const struct constraint_expr rhs,
2282 const unsigned HOST_WIDE_INT size)
2284 varinfo_t p = get_varinfo (lhs.var);
2285 unsigned HOST_WIDE_INT pstart,last;
2287 last = p->offset + size;
2289 for (; p && p->offset < last; p = p->next)
2292 struct constraint_expr templhs = lhs;
2293 struct constraint_expr temprhs = rhs;
2294 unsigned HOST_WIDE_INT fieldoffset;
2297 if (templhs.type == SCALAR)
2298 templhs.var = p->id;
2300 templhs.offset = p->offset;
2302 q = get_varinfo (temprhs.var);
2303 fieldoffset = p->offset - pstart;
2304 temprhs.offset += fieldoffset;
2305 process_constraint (new_constraint (templhs, temprhs));
2309 /* Handle the structure copy case where we have a structure copy
2310 between a aggregate on the RHS and a dereference of a pointer on
2311 the LHS that is of SIZE (in bits)
2313 For each field of the rhs variable (rhsfield)
2314 lhs.offset = rhsfield->offset
2315 add the constraint lhs = rhsfield
2319 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2320 const struct constraint_expr rhs,
2321 const unsigned HOST_WIDE_INT size)
2323 varinfo_t p = get_varinfo (rhs.var);
2324 unsigned HOST_WIDE_INT pstart,last;
2326 last = p->offset + size;
2328 for (; p && p->offset < last; p = p->next)
2331 struct constraint_expr templhs = lhs;
2332 struct constraint_expr temprhs = rhs;
2333 unsigned HOST_WIDE_INT fieldoffset;
2336 if (temprhs.type == SCALAR)
2337 temprhs.var = p->id;
2339 temprhs.offset = p->offset;
2341 q = get_varinfo (templhs.var);
2342 fieldoffset = p->offset - pstart;
2343 templhs.offset += fieldoffset;
2344 process_constraint (new_constraint (templhs, temprhs));
2349 /* Handle aggregate copies by expanding into copies of the respective
2350 fields of the structures. */
2353 do_structure_copy (tree lhsop, tree rhsop)
2355 struct constraint_expr lhs, rhs, tmp;
2357 unsigned HOST_WIDE_INT lhssize;
2358 unsigned HOST_WIDE_INT rhssize;
2360 lhs = get_constraint_for (lhsop);
2361 rhs = get_constraint_for (rhsop);
2363 /* If we have special var = x, swap it around. */
2364 if (lhs.var <= integer_id && rhs.var > integer_id)
2371 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2372 possible it's something we could handle. However, most cases falling
2373 into this are dealing with transparent unions, which are slightly
2375 if (rhs.type == ADDRESSOF && rhs.var > integer_id)
2377 rhs.type = ADDRESSOF;
2378 rhs.var = anything_id;
2381 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2382 that special var. */
2383 if (rhs.var <= integer_id)
2385 for (p = get_varinfo (lhs.var); p; p = p->next)
2387 struct constraint_expr templhs = lhs;
2388 struct constraint_expr temprhs = rhs;
2389 if (templhs.type == SCALAR )
2390 templhs.var = p->id;
2392 templhs.offset += p->offset;
2393 process_constraint (new_constraint (templhs, temprhs));
2398 /* The size only really matters insofar as we don't set more or less of
2399 the variable. If we hit an unknown size var, the size should be the
2400 whole darn thing. */
2401 if (get_varinfo (rhs.var)->is_unknown_size_var)
2404 rhssize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (rhsop)));
2406 if (get_varinfo (lhs.var)->is_unknown_size_var)
2409 lhssize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (lhsop)));
2412 if (rhs.type == SCALAR && lhs.type == SCALAR)
2413 do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2414 else if (lhs.type != DEREF && rhs.type == DEREF)
2415 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2416 else if (lhs.type == DEREF && rhs.type != DEREF)
2417 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2420 tree rhsdecl = get_varinfo (rhs.var)->decl;
2421 tree pointertype = TREE_TYPE (rhsdecl);
2422 tree pointedtotype = TREE_TYPE (pointertype);
2425 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2426 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2427 do_structure_copy (tmpvar, rhsop);
2428 do_structure_copy (lhsop, tmpvar);
2434 /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere
2438 ref_contains_indirect_ref (tree ref)
2440 while (handled_component_p (ref))
2442 if (TREE_CODE (ref) == INDIRECT_REF)
2444 ref = TREE_OPERAND (ref, 0);
2450 /* Tree walker that is the heart of the aliasing infrastructure.
2451 TP is a pointer to the current tree.
2452 WALK_SUBTREES specifies whether to continue traversing subtrees or
2454 Returns NULL_TREE when we should stop.
2456 This function is the main part of the constraint builder. It
2457 walks the trees, calling the appropriate building functions
2458 to process various statements. */
2461 find_func_aliases (tree t)
2463 struct constraint_expr lhs, rhs;
2464 switch (TREE_CODE (t))
2470 /* Only care about pointers and structures containing
2472 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
2473 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
2475 lhs = get_constraint_for (PHI_RESULT (t));
2476 for (i = 0; i < PHI_NUM_ARGS (t); i++)
2478 rhs = get_constraint_for (PHI_ARG_DEF (t, i));
2479 process_constraint (new_constraint (lhs, rhs));
2487 tree lhsop = TREE_OPERAND (t, 0);
2488 tree rhsop = TREE_OPERAND (t, 1);
2491 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2492 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
2494 do_structure_copy (lhsop, rhsop);
2498 /* Only care about operations with pointers, structures
2499 containing pointers, dereferences, and call
2501 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
2502 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2503 || ref_contains_indirect_ref (lhsop)
2504 || TREE_CODE (rhsop) == CALL_EXPR)
2506 lhs = get_constraint_for (lhsop);
2507 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
2509 /* RHS that consist of unary operations,
2510 exceptional types, or bare decls/constants, get
2511 handled directly by get_constraint_for. */
2513 case tcc_declaration:
2515 case tcc_exceptional:
2516 case tcc_expression:
2519 rhs = get_constraint_for (rhsop);
2520 process_constraint (new_constraint (lhs, rhs));
2524 /* Otherwise, walk each operand. */
2526 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
2528 tree op = TREE_OPERAND (rhsop, i);
2529 rhs = get_constraint_for (op);
2530 process_constraint (new_constraint (lhs, rhs));
2544 /* Find the first varinfo in the same variable as START that overlaps with
2546 Effectively, walk the chain of fields for the variable START to find the
2547 first field that overlaps with OFFSET.
2548 Abort if we can't find one. */
2551 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
2553 varinfo_t curr = start;
2556 /* We may not find a variable in the field list with the actual
2557 offset when when we have glommed a structure to a variable.
2558 In that case, however, offset should still be within the size
2560 if (offset >= curr->offset && offset < (curr->offset + curr->size))
2569 /* Insert the varinfo FIELD into the field list for BASE, ordered by
2573 insert_into_field_list (varinfo_t base, varinfo_t field)
2575 varinfo_t prev = base;
2576 varinfo_t curr = base->next;
2587 if (field->offset <= curr->offset)
2592 field->next = prev->next;
2597 /* qsort comparison function for two fieldoff's PA and PB */
2600 fieldoff_compare (const void *pa, const void *pb)
2602 const fieldoff_s *foa = (const fieldoff_s *)pa;
2603 const fieldoff_s *fob = (const fieldoff_s *)pb;
2604 HOST_WIDE_INT foasize, fobsize;
2606 if (foa->offset != fob->offset)
2607 return foa->offset - fob->offset;
2609 foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
2610 fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
2611 return foasize - fobsize;
2614 /* Sort a fieldstack according to the field offset and sizes. */
2615 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
2617 qsort (VEC_address (fieldoff_s, fieldstack),
2618 VEC_length (fieldoff_s, fieldstack),
2619 sizeof (fieldoff_s),
2623 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
2624 of TYPE onto fieldstack, recording their offsets along the way.
2625 OFFSET is used to keep track of the offset in this entire structure, rather
2626 than just the immediately containing structure. Returns the number
2628 HAS_UNION is set to true if we find a union type as a field of
2632 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
2633 HOST_WIDE_INT offset, bool *has_union)
2638 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2639 if (TREE_CODE (field) == FIELD_DECL)
2644 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
2645 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
2648 if (!var_can_have_subvars (field))
2650 else if (!(push_fields_onto_fieldstack
2651 (TREE_TYPE (field), fieldstack,
2652 offset + bitpos_of_field (field), has_union))
2653 && DECL_SIZE (field)
2654 && !integer_zerop (DECL_SIZE (field)))
2655 /* Empty structures may have actual size, like in C++. So
2656 see if we didn't push any subfields and the size is
2657 nonzero, push the field onto the stack */
2664 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
2665 pair->field = field;
2666 pair->offset = offset + bitpos_of_field (field);
2675 make_constraint_to_anything (varinfo_t vi)
2677 struct constraint_expr lhs, rhs;
2683 rhs.var = anything_id;
2685 rhs.type = ADDRESSOF;
2686 process_constraint (new_constraint (lhs, rhs));
2689 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
2690 This will also create any varinfo structures necessary for fields
2694 create_variable_info_for (tree decl, const char *name)
2696 unsigned int index = VEC_length (varinfo_t, varmap);
2698 tree decltype = TREE_TYPE (decl);
2699 bool notokay = false;
2702 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
2703 VEC (fieldoff_s,heap) *fieldstack = NULL;
2706 hasunion = TREE_CODE (decltype) == UNION_TYPE || TREE_CODE (decltype) == QUAL_UNION_TYPE;
2707 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
2709 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
2712 VEC_free (fieldoff_s, heap, fieldstack);
2717 /* If this variable already has subvars, just create the variables for the
2718 subvars and we are done.
2719 NOTE: This assumes things haven't generated uses of previously
2720 unused structure fields. */
2721 if (use_field_sensitive
2723 && var_can_have_subvars (decl)
2725 && (svars = get_subvars_for_var (decl)))
2728 varinfo_t base = NULL;
2729 unsigned int firstindex = index;
2731 for (sv = svars; sv; sv = sv->next)
2733 /* For debugging purposes, this will print the names of the
2734 fields as "<var>.<offset>.<size>"
2735 This is only for debugging purposes. */
2736 #define PRINT_LONG_NAMES
2737 #ifdef PRINT_LONG_NAMES
2739 const char *newname;
2741 asprintf (&tempname,
2742 "%s." HOST_WIDE_INT_PRINT_DEC "." HOST_WIDE_INT_PRINT_DEC,
2743 alias_get_name (decl), sv->offset, sv->size);
2744 newname = ggc_strdup (tempname);
2746 vi = new_var_info (sv->var, index, newname, index);
2748 vi = new_var_info (sv->var, index, alias_get_name (sv->var), index);
2751 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2752 vi->size = sv->size;
2753 vi->offset = sv->offset;
2757 insert_id_for_tree (decl, index);
2761 insert_into_field_list (base, vi);
2763 insert_id_for_tree (sv->var, index);
2764 VEC_safe_push (varinfo_t, gc, varmap, vi);
2766 make_constraint_to_anything (vi);
2774 /* If the variable doesn't have subvars, we may end up needing to
2775 sort the field list and create fake variables for all the
2777 vi = new_var_info (decl, index, name, index);
2780 vi->has_union = hasunion;
2781 if (!TYPE_SIZE (decltype)
2782 || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
2783 || TREE_CODE (decltype) == ARRAY_TYPE
2784 || TREE_CODE (decltype) == UNION_TYPE
2785 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
2787 vi->is_unknown_size_var = true;
2793 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2794 vi->size = vi->fullsize;
2797 insert_id_for_tree (vi->decl, index);
2798 VEC_safe_push (varinfo_t, gc, varmap, vi);
2800 make_constraint_to_anything (vi);
2803 if (use_field_sensitive
2805 && !vi->is_unknown_size_var
2806 && var_can_have_subvars (decl))
2808 unsigned int newindex = VEC_length (varinfo_t, varmap);
2809 fieldoff_s *fo = NULL;
2813 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
2815 if (!DECL_SIZE (fo->field)
2816 || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
2817 || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE
2825 /* We can't sort them if we have a field with a variable sized type,
2826 which will make notokay = true. In that case, we are going to return
2827 without creating varinfos for the fields anyway, so sorting them is a
2830 sort_fieldstack (fieldstack);
2832 if (VEC_length (fieldoff_s, fieldstack) != 0)
2833 fo = VEC_index (fieldoff_s, fieldstack, 0);
2835 if (fo == NULL || notokay)
2837 vi->is_unknown_size_var = 1;
2840 VEC_free (fieldoff_s, heap, fieldstack);
2845 vi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
2846 for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
2849 const char *newname;
2853 newindex = VEC_length (varinfo_t, varmap);
2854 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (field));
2855 newname = ggc_strdup (tempname);
2857 newvi = new_var_info (decl, newindex, newname, newindex);
2858 newvi->offset = fo->offset;
2859 newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
2860 newvi->fullsize = vi->fullsize;
2861 insert_into_field_list (vi, newvi);
2862 VEC_safe_push (varinfo_t, gc, varmap, newvi);
2864 make_constraint_to_anything (newvi);
2868 VEC_free (fieldoff_s, heap, fieldstack);
2873 /* Print out the points-to solution for VAR to FILE. */
2876 dump_solution_for_var (FILE *file, unsigned int var)
2878 varinfo_t vi = get_varinfo (var);
2882 fprintf (file, "%s = { ", vi->name);
2883 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
2885 fprintf (file, "%s ", get_varinfo (i)->name);
2887 fprintf (file, "}\n");
2890 /* Print the points-to solution for VAR to stdout. */
2893 debug_solution_for_var (unsigned int var)
2895 dump_solution_for_var (stdout, var);
2899 /* Create varinfo structures for all of the variables in the
2900 function for intraprocedural mode. */
2903 intra_create_variable_infos (void)
2907 /* For each incoming argument arg, ARG = &ANYTHING */
2908 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
2910 struct constraint_expr lhs;
2911 struct constraint_expr rhs;
2916 lhs.var = create_variable_info_for (t, alias_get_name (t));
2918 get_varinfo (lhs.var)->is_artificial_var = true;
2919 rhs.var = anything_id;
2920 rhs.type = ADDRESSOF;
2923 for (p = get_varinfo (lhs.var); p; p = p->next)
2925 struct constraint_expr temp = lhs;
2927 process_constraint (new_constraint (temp, rhs));
2933 /* Set bits in INTO corresponding to the variable uids in solution set
2937 set_uids_in_ptset (bitmap into, bitmap from)
2942 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
2944 varinfo_t vi = get_varinfo (i);
2946 /* Variables containing unions may need to be converted to their
2947 SFT's, because SFT's can have unions and we cannot. */
2948 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
2950 subvar_t svars = get_subvars_for_var (vi->decl);
2952 for (sv = svars; sv; sv = sv->next)
2953 bitmap_set_bit (into, DECL_UID (sv->var));
2955 /* We may end up with labels in the points-to set because people
2956 take their address, and they are _DECL's. */
2957 else if (TREE_CODE (vi->decl) == VAR_DECL
2958 || TREE_CODE (vi->decl) == PARM_DECL)
2959 bitmap_set_bit (into, DECL_UID (vi->decl));
2964 static int have_alias_info = false;
2966 /* Given a pointer variable P, fill in its points-to set, or return
2967 false if we can't. */
2970 find_what_p_points_to (tree p)
2972 unsigned int id = 0;
2973 if (!have_alias_info)
2975 if (lookup_id_for_tree (p, &id))
2977 varinfo_t vi = get_varinfo (id);
2979 if (vi->is_artificial_var)
2982 /* See if this is a field or a structure */
2983 if (vi->size != vi->fullsize)
2985 if (!var_can_have_subvars (vi->decl)
2986 || get_subvars_for_var (vi->decl) == NULL)
2988 /* Nothing currently asks about structure fields directly, but when
2989 they do, we need code here to hand back the points-to set. */
2993 struct ptr_info_def *pi = get_ptr_info (p);
2997 /* This variable may have been collapsed, let's get the real
2999 vi = get_varinfo (vi->node);
3001 /* Make sure there aren't any artificial vars in the points to set.
3002 XXX: Note that we need to translate our heap variables to
3004 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
3006 if (get_varinfo (i)->is_artificial_var)
3009 pi->pt_anything = false;
3011 pi->pt_vars = BITMAP_GGC_ALLOC ();
3012 set_uids_in_ptset (pi->pt_vars, vi->solution);
3020 /* Initialize things necessary to perform PTA */
3023 init_alias_vars (void)
3025 bitmap_obstack_initialize (&ptabitmap_obstack);
3029 /* Dump points-to information to OUTFILE. */
3032 dump_sa_points_to_info (FILE *outfile)
3036 fprintf (outfile, "\nPoints-to information\n\n");
3038 if (dump_flags & TDF_STATS)
3040 fprintf (outfile, "Stats:\n");
3041 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
3042 fprintf (outfile, "Statically unified vars: %d\n",
3043 stats.unified_vars_static);
3044 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
3045 fprintf (outfile, "Dynamically unified vars: %d\n",
3046 stats.unified_vars_dynamic);
3047 fprintf (outfile, "Iterations: %d\n", stats.iterations);
3050 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
3051 dump_solution_for_var (outfile, i);
3055 /* Debug points-to information to stderr. */
3058 debug_sa_points_to_info (void)
3060 dump_sa_points_to_info (stderr);
3064 /* Initialize the always-existing constraint variables for NULL
3065 ANYTHING, READONLY, and INTEGER */
3068 init_base_vars (void)
3070 struct constraint_expr lhs, rhs;
3072 /* Create the NULL variable, used to represent that a variable points
3074 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
3075 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
3076 insert_id_for_tree (nothing_tree, 0);
3077 var_nothing->is_artificial_var = 1;
3078 var_nothing->offset = 0;
3079 var_nothing->size = ~0;
3080 var_nothing->fullsize = ~0;
3082 VEC_safe_push (varinfo_t, gc, varmap, var_nothing);
3084 /* Create the ANYTHING variable, used to represent that a variable
3085 points to some unknown piece of memory. */
3086 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
3087 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
3088 insert_id_for_tree (anything_tree, 1);
3089 var_anything->is_artificial_var = 1;
3090 var_anything->size = ~0;
3091 var_anything->offset = 0;
3092 var_anything->next = NULL;
3093 var_anything->fullsize = ~0;
3096 /* Anything points to anything. This makes deref constraints just
3097 work in the presence of linked list and other p = *p type loops,
3098 by saying that *ANYTHING = ANYTHING. */
3099 VEC_safe_push (varinfo_t, gc, varmap, var_anything);
3101 lhs.var = anything_id;
3103 rhs.type = ADDRESSOF;
3104 rhs.var = anything_id;
3106 var_anything->address_taken = true;
3107 /* This specifically does not use process_constraint because
3108 process_constraint ignores all anything = anything constraints, since all
3109 but this one are redundant. */
3110 VEC_safe_push (constraint_t, gc, constraints, new_constraint (lhs, rhs));
3112 /* Create the READONLY variable, used to represent that a variable
3113 points to readonly memory. */
3114 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
3115 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
3116 var_readonly->is_artificial_var = 1;
3117 var_readonly->offset = 0;
3118 var_readonly->size = ~0;
3119 var_readonly->fullsize = ~0;
3120 var_readonly->next = NULL;
3121 insert_id_for_tree (readonly_tree, 2);
3123 VEC_safe_push (varinfo_t, gc, varmap, var_readonly);
3125 /* readonly memory points to anything, in order to make deref
3126 easier. In reality, it points to anything the particular
3127 readonly variable can point to, but we don't track this
3130 lhs.var = readonly_id;
3132 rhs.type = ADDRESSOF;
3133 rhs.var = anything_id;
3136 process_constraint (new_constraint (lhs, rhs));
3138 /* Create the INTEGER variable, used to represent that a variable points
3140 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
3141 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
3142 insert_id_for_tree (integer_tree, 3);
3143 var_integer->is_artificial_var = 1;
3144 var_integer->size = ~0;
3145 var_integer->fullsize = ~0;
3146 var_integer->offset = 0;
3147 var_integer->next = NULL;
3149 VEC_safe_push (varinfo_t, gc, varmap, var_integer);
3151 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
3152 integer will point to. */
3154 lhs.var = integer_id;
3156 rhs.type = ADDRESSOF;
3157 rhs.var = anything_id;
3159 process_constraint (new_constraint (lhs, rhs));
3163 /* Create points-to sets for the current function. See the comments
3164 at the start of the file for an algorithmic overview. */
3167 create_alias_vars (void)
3173 constraint_pool = create_alloc_pool ("Constraint pool",
3174 sizeof (struct constraint), 30);
3175 variable_info_pool = create_alloc_pool ("Variable info pool",
3176 sizeof (struct variable_info), 30);
3177 constraint_edge_pool = create_alloc_pool ("Constraint edges",
3178 sizeof (struct constraint_edge), 30);
3180 constraints = VEC_alloc (constraint_t, gc, 8);
3181 varmap = VEC_alloc (varinfo_t, gc, 8);
3182 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
3183 memset (&stats, 0, sizeof (stats));
3187 intra_create_variable_infos ();
3189 /* Now walk all statements and derive aliases. */
3192 block_stmt_iterator bsi;
3195 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3196 if (is_gimple_reg (PHI_RESULT (phi)))
3197 find_func_aliases (phi);
3199 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3200 find_func_aliases (bsi_stmt (bsi));
3203 build_constraint_graph ();
3207 fprintf (dump_file, "Constraints:\n");
3208 dump_constraints (dump_file);
3212 fprintf (dump_file, "Collapsing static cycles and doing variable substitution:\n");
3214 find_and_collapse_graph_cycles (graph, false);
3215 perform_var_substitution (graph);
3218 fprintf (dump_file, "Solving graph:\n");
3220 solve_graph (graph);
3223 dump_sa_points_to_info (dump_file);
3225 have_alias_info = true;
3228 struct tree_opt_pass pass_build_pta =
3232 create_alias_vars, /* execute */
3235 0, /* static_pass_number */
3236 TV_TREE_PTA, /* tv_id */
3237 PROP_cfg, /* properties_required */
3238 PROP_pta, /* properties_provided */
3239 0, /* properties_destroyed */
3240 0, /* todo_flags_start */
3241 0, /* todo_flags_finish */
3246 /* Delete created points-to sets. */
3249 delete_alias_vars (void)
3251 htab_delete (id_for_tree);
3252 free_alloc_pool (variable_info_pool);
3253 free_alloc_pool (constraint_pool);
3254 free_alloc_pool (constraint_edge_pool);
3255 bitmap_obstack_release (&ptabitmap_obstack);
3256 have_alias_info = false;
3259 struct tree_opt_pass pass_del_pta =
3263 delete_alias_vars, /* execute */
3266 0, /* static_pass_number */
3267 TV_TREE_PTA, /* tv_id */
3268 PROP_pta, /* properties_required */
3269 0, /* properties_provided */
3270 PROP_pta, /* properties_destroyed */
3271 0, /* todo_flags_start */
3272 0, /* todo_flags_finish */