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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 apepars 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 approriate copy edges to the graph, or the
141 approriate 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 /* Points-to set for this variable. */
227 /* Variable ids represented by this node. */
230 /* Vector of complex constraints for this node. Complex
231 constraints are those involving dereferences. */
232 VEC(constraint_t,gc) *complex;
234 typedef struct variable_info *varinfo_t;
236 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
238 /* Pool of variable info structures. */
239 static alloc_pool variable_info_pool;
241 DEF_VEC_P(varinfo_t);
243 DEF_VEC_ALLOC_P(varinfo_t, gc);
245 /* Table of variable info structures for constraint variables. Indexed direcly
246 by variable info id. */
247 static VEC(varinfo_t,gc) *varmap;
248 #define get_varinfo(n) VEC_index(varinfo_t, varmap, n)
250 /* Variable that represents the unknown pointer. */
251 static varinfo_t var_anything;
252 static tree anything_tree;
253 static unsigned int anything_id;
255 /* Variable that represents the NULL pointer. */
256 static varinfo_t var_nothing;
257 static tree nothing_tree;
258 static unsigned int nothing_id;
260 /* Variable that represents read only memory. */
261 static varinfo_t var_readonly;
262 static tree readonly_tree;
263 static unsigned int readonly_id;
265 /* Variable that represents integers. This is used for when people do things
267 static varinfo_t var_integer;
268 static tree integer_tree;
269 static unsigned int integer_id;
272 /* Return a new variable info structure consisting for a variable
273 named NAME, and using constraint graph node NODE. */
276 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
278 varinfo_t ret = pool_alloc (variable_info_pool);
284 ret->address_taken = false;
285 ret->indirect_target = false;
286 ret->is_artificial_var = false;
287 ret->is_unknown_size_var = false;
288 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
289 bitmap_clear (ret->solution);
290 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
291 bitmap_clear (ret->variables);
297 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
299 /* An expression that appears in a constraint. */
301 struct constraint_expr
303 /* Constraint type. */
304 constraint_expr_type type;
306 /* Variable we are referring to in the constraint. */
309 /* Offset, in bits, of this constraint from the beginning of
310 variables it ends up referring to.
312 IOW, in a deref constraint, we would deref, get the result set,
313 then add OFFSET to each member. */
314 unsigned HOST_WIDE_INT offset;
317 static struct constraint_expr do_deref (struct constraint_expr);
319 /* Our set constraints are made up of two constraint expressions, one
322 As described in the introduction, our set constraints each represent an
323 operation between set valued variables.
327 struct constraint_expr lhs;
328 struct constraint_expr rhs;
331 /* List of constraints that we use to build the constraint graph from. */
333 static VEC(constraint_t,gc) *constraints;
334 static alloc_pool constraint_pool;
336 /* An edge in the constraint graph. We technically have no use for
337 the src, since it will always be the same node that we are indexing
338 into the pred/succ arrays with, but it's nice for checking
339 purposes. The edges are weighted, with a bit set in weights for
340 each edge from src to dest with that weight. */
342 struct constraint_edge
349 typedef struct constraint_edge *constraint_edge_t;
350 static alloc_pool constraint_edge_pool;
352 /* Return a new constraint edge from SRC to DEST. */
354 static constraint_edge_t
355 new_constraint_edge (unsigned int src, unsigned int dest)
357 constraint_edge_t ret = pool_alloc (constraint_edge_pool);
364 DEF_VEC_P(constraint_edge_t);
365 DEF_VEC_ALLOC_P(constraint_edge_t,gc);
368 /* The constraint graph is simply a set of adjacency vectors, one per
369 variable. succs[x] is the vector of successors for variable x, and preds[x]
370 is the vector of predecessors for variable x.
371 IOW, all edges are "forward" edges, which is not like our CFG.
373 preds[x]->src == x, and
376 struct constraint_graph
378 VEC(constraint_edge_t,gc) **succs;
379 VEC(constraint_edge_t,gc) **preds;
382 typedef struct constraint_graph *constraint_graph_t;
384 static constraint_graph_t graph;
386 /* Create a new constraint consisting of LHS and RHS expressions. */
389 new_constraint (const struct constraint_expr lhs,
390 const struct constraint_expr rhs)
392 constraint_t ret = pool_alloc (constraint_pool);
398 /* Print out constraint C to FILE. */
401 dump_constraint (FILE *file, constraint_t c)
403 if (c->lhs.type == ADDRESSOF)
405 else if (c->lhs.type == DEREF)
407 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
408 if (c->lhs.offset != 0)
409 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
410 fprintf (file, " = ");
411 if (c->rhs.type == ADDRESSOF)
413 else if (c->rhs.type == DEREF)
415 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
416 if (c->rhs.offset != 0)
417 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
418 fprintf (file, "\n");
421 /* Print out constraint C to stderr. */
424 debug_constraint (constraint_t c)
426 dump_constraint (stderr, c);
429 /* Print out all constraints to FILE */
432 dump_constraints (FILE *file)
436 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
437 dump_constraint (file, c);
440 /* Print out all constraints to stderr. */
443 debug_constraints (void)
445 dump_constraints (stderr);
450 The solver is a simple worklist solver, that works on the following
453 sbitmap changed_nodes = all ones;
454 changed_count = number of nodes;
455 For each node that was already collapsed:
459 while (changed_count > 0)
461 compute topological ordering for constraint graph
463 find and collapse cycles in the constraint graph (updating
464 changed if necessary)
466 for each node (n) in the graph in topological order:
469 Process each complex constraint associated with the node,
470 updating changed if necessary.
472 For each outgoing edge from n, propagate the solution from n to
473 the destination of the edge, updating changed as necessary.
477 /* Return true if two constraint expressions A and B are equal. */
480 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
482 return a.type == b.type
484 && a.offset == b.offset;
487 /* Return true if constraint expression A is less than constraint expression
488 B. This is just arbitrary, but consistent, in order to give them an
492 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
494 if (a.type == b.type)
497 return a.offset < b.offset;
499 return a.var < b.var;
502 return a.type < b.type;
505 /* Return true if constraint A is less than constraint B. This is just
506 arbitrary, but consistent, in order to give them an ordering. */
509 constraint_less (const constraint_t a, const constraint_t b)
511 if (constraint_expr_less (a->lhs, b->lhs))
513 else if (constraint_expr_less (b->lhs, a->lhs))
516 return constraint_expr_less (a->rhs, b->rhs);
519 /* Return true if two constraints A and B are equal. */
522 constraint_equal (struct constraint a, struct constraint b)
524 return constraint_expr_equal (a.lhs, b.lhs)
525 && constraint_expr_equal (a.rhs, b.rhs);
529 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
532 constraint_vec_find (VEC(constraint_t,gc) *vec,
533 struct constraint lookfor)
541 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
542 if (place >= VEC_length (constraint_t, vec))
544 found = VEC_index (constraint_t, vec, place);
545 if (!constraint_equal (*found, lookfor))
550 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
553 constraint_set_union (VEC(constraint_t,gc) **to,
554 VEC(constraint_t,gc) **from)
559 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
561 if (constraint_vec_find (*to, *c) == NULL)
563 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
565 VEC_safe_insert (constraint_t, gc, *to, place, c);
570 /* Take a solution set SET, add OFFSET to each member of the set, and
571 overwrite SET with the result when done. */
574 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
576 bitmap result = BITMAP_ALLOC (&iteration_obstack);
580 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
582 /* If this is a properly sized variable, only add offset if it's
583 less than end. Otherwise, it is globbed to a single
586 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
588 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
589 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
590 bitmap_set_bit (result, v->id);
592 else if (get_varinfo (i)->is_artificial_var
593 || get_varinfo (i)->is_unknown_size_var)
595 bitmap_set_bit (result, i);
599 bitmap_copy (set, result);
600 BITMAP_FREE (result);
603 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
607 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
610 return bitmap_ior_into (to, from);
616 tmp = BITMAP_ALLOC (&iteration_obstack);
617 bitmap_copy (tmp, from);
618 solution_set_add (tmp, inc);
619 res = bitmap_ior_into (to, tmp);
625 /* Insert constraint C into the list of complex constraints for VAR. */
628 insert_into_complex (unsigned int var, constraint_t c)
630 varinfo_t vi = get_varinfo (var);
631 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
633 VEC_safe_insert (constraint_t, gc, vi->complex, place, c);
637 /* Compare two constraint edges A and B, return true if they are equal. */
640 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
642 return a.src == b.src && a.dest == b.dest;
645 /* Compare two constraint edges, return true if A is less than B */
648 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
650 if (a->dest < b->dest)
652 else if (a->dest == b->dest)
653 return a->src < b->src;
658 /* Find the constraint edge that matches LOOKFOR, in VEC.
659 Return the edge, if found, NULL otherwise. */
661 static constraint_edge_t
662 constraint_edge_vec_find (VEC(constraint_edge_t,gc) *vec,
663 struct constraint_edge lookfor)
666 constraint_edge_t edge;
668 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
669 constraint_edge_less);
670 edge = VEC_index (constraint_edge_t, vec, place);
671 if (!constraint_edge_equal (*edge, lookfor))
676 /* Condense two variable nodes into a single variable node, by moving
677 all associated info from SRC to TO. */
680 condense_varmap_nodes (unsigned int to, unsigned int src)
682 varinfo_t tovi = get_varinfo (to);
683 varinfo_t srcvi = get_varinfo (src);
688 /* the src node, and all its variables, are now the to node. */
690 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
691 get_varinfo (i)->node = to;
693 /* Merge the src node variables and the to node variables. */
694 bitmap_set_bit (tovi->variables, src);
695 bitmap_ior_into (tovi->variables, srcvi->variables);
696 bitmap_clear (srcvi->variables);
698 /* Move all complex constraints from src node into to node */
699 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
701 /* In complex constraints for node src, we may have either
702 a = *src, and *src = a. */
704 if (c->rhs.type == DEREF)
709 constraint_set_union (&tovi->complex, &srcvi->complex);
710 srcvi->complex = NULL;
713 /* Erase EDGE from GRAPH. This routine only handles self-edges
714 (e.g. an edge from a to a). */
717 erase_graph_self_edge (constraint_graph_t graph, struct constraint_edge edge)
719 VEC(constraint_edge_t,gc) *predvec = graph->preds[edge.src];
720 VEC(constraint_edge_t,gc) *succvec = graph->succs[edge.dest];
722 gcc_assert (edge.src == edge.dest);
724 /* Remove from the successors. */
725 place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
726 constraint_edge_less);
728 /* Make sure we found the edge. */
729 #ifdef ENABLE_CHECKING
731 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
732 gcc_assert (constraint_edge_equal (*tmp, edge));
735 VEC_ordered_remove (constraint_edge_t, succvec, place);
737 /* Remove from the predecessors. */
738 place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
739 constraint_edge_less);
741 /* Make sure we found the edge. */
742 #ifdef ENABLE_CHECKING
744 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
745 gcc_assert (constraint_edge_equal (*tmp, edge));
748 VEC_ordered_remove (constraint_edge_t, predvec, place);
751 /* Remove edges involving NODE from GRAPH. */
754 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
756 VEC(constraint_edge_t,gc) *succvec = graph->succs[node];
757 VEC(constraint_edge_t,gc) *predvec = graph->preds[node];
761 /* Walk the successors, erase the associated preds. */
762 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
766 struct constraint_edge lookfor;
767 lookfor.src = c->dest;
769 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
770 &lookfor, constraint_edge_less);
771 VEC_ordered_remove (constraint_edge_t, graph->preds[c->dest], place);
773 /* Walk the preds, erase the associated succs. */
774 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
778 struct constraint_edge lookfor;
779 lookfor.src = c->dest;
781 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
782 &lookfor, constraint_edge_less);
783 VEC_ordered_remove (constraint_edge_t, graph->succs[c->dest], place);
786 graph->preds[node] = NULL;
787 graph->succs[node] = NULL;
790 static bool edge_added = false;
792 /* Add edge NEWE to the graph. */
795 add_graph_edge (constraint_graph_t graph, struct constraint_edge newe)
798 unsigned int src = newe.src;
799 unsigned int dest = newe.dest;
800 VEC(constraint_edge_t,gc) *vec;
802 vec = graph->preds[src];
803 place = VEC_lower_bound (constraint_edge_t, vec, &newe,
804 constraint_edge_less);
805 if (place == VEC_length (constraint_edge_t, vec)
806 || VEC_index (constraint_edge_t, vec, place)->dest != dest)
808 constraint_edge_t edge = new_constraint_edge (src, dest);
811 weightbitmap = BITMAP_ALLOC (&ptabitmap_obstack);
812 edge->weights = weightbitmap;
813 VEC_safe_insert (constraint_edge_t, gc, graph->preds[edge->src],
815 edge = new_constraint_edge (dest, src);
816 edge->weights = weightbitmap;
817 place = VEC_lower_bound (constraint_edge_t, graph->succs[edge->src],
818 edge, constraint_edge_less);
819 VEC_safe_insert (constraint_edge_t, gc, graph->succs[edge->src],
829 /* Return the bitmap representing the weights of edge LOOKFOR */
832 get_graph_weights (constraint_graph_t graph, struct constraint_edge lookfor)
834 constraint_edge_t edge;
835 unsigned int src = lookfor.src;
836 VEC(constraint_edge_t,gc) *vec;
837 vec = graph->preds[src];
838 edge = constraint_edge_vec_find (vec, lookfor);
839 gcc_assert (edge != NULL);
840 return edge->weights;
844 /* Merge GRAPH nodes FROM and TO into node TO. */
847 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
850 VEC(constraint_edge_t,gc) *succvec = graph->succs[from];
851 VEC(constraint_edge_t,gc) *predvec = graph->preds[from];
855 /* Merge all the predecessor edges. */
857 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
859 unsigned int d = c->dest;
860 struct constraint_edge olde;
861 struct constraint_edge newe;
868 add_graph_edge (graph, newe);
871 temp = get_graph_weights (graph, olde);
872 weights = get_graph_weights (graph, newe);
873 bitmap_ior_into (weights, temp);
876 /* Merge all the successor edges. */
877 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
879 unsigned int d = c->dest;
880 struct constraint_edge olde;
881 struct constraint_edge newe;
888 add_graph_edge (graph, newe);
891 temp = get_graph_weights (graph, olde);
892 weights = get_graph_weights (graph, newe);
893 bitmap_ior_into (weights, temp);
895 clear_edges_for_node (graph, from);
898 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
899 it doesn't exist in the graph already.
900 Return false if the edge already existed, true otherwise. */
903 int_add_graph_edge (constraint_graph_t graph, unsigned int to,
904 unsigned int from, unsigned HOST_WIDE_INT weight)
906 if (to == from && weight == 0)
913 struct constraint_edge edge;
916 r = add_graph_edge (graph, edge);
917 r |= !bitmap_bit_p (get_graph_weights (graph, edge), weight);
918 bitmap_set_bit (get_graph_weights (graph, edge), weight);
924 /* Return true if LOOKFOR is an existing graph edge. */
927 valid_graph_edge (constraint_graph_t graph, struct constraint_edge lookfor)
929 return constraint_edge_vec_find (graph->preds[lookfor.src], lookfor) != NULL;
933 /* Build the constraint graph. */
936 build_constraint_graph (void)
941 graph = ggc_alloc (sizeof (struct constraint_graph));
942 graph->succs = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->succs));
943 graph->preds = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->preds));
944 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
946 struct constraint_expr lhs = c->lhs;
947 struct constraint_expr rhs = c->rhs;
948 if (lhs.type == DEREF)
950 /* *x = y or *x = &y (complex) */
951 if (rhs.type == ADDRESSOF || rhs.var > anything_id)
952 insert_into_complex (lhs.var, c);
954 else if (rhs.type == DEREF)
957 if (lhs.var > anything_id)
958 insert_into_complex (rhs.var, c);
960 else if (rhs.type == ADDRESSOF)
963 bitmap_set_bit (get_varinfo (lhs.var)->solution, rhs.var);
965 else if (rhs.var > anything_id && lhs.var > anything_id)
967 /* Ignore 0 weighted self edges, as they can't possibly contribute
969 if (lhs.var != rhs.var || rhs.offset != 0 || lhs.offset != 0)
972 struct constraint_edge edge;
976 add_graph_edge (graph, edge);
977 bitmap_set_bit (get_graph_weights (graph, edge),
984 /* Changed variables on the last iteration. */
985 static unsigned int changed_count;
986 static sbitmap changed;
989 DEF_VEC_ALLOC_I(uint,heap);
992 /* Strongly Connected Component visitation info. */
997 sbitmap in_component;
999 unsigned int *visited_index;
1000 VEC(uint,heap) *scc_stack;
1001 VEC(uint,heap) *unification_queue;
1005 /* Recursive routine to find strongly connected components in GRAPH.
1006 SI is the SCC info to store the information in, and N is the id of current
1007 graph node we are processing.
1009 This is Tarjan's strongly connected component finding algorithm, as
1010 modified by Nuutila to keep only non-root nodes on the stack.
1011 The algorithm can be found in "On finding the strongly connected
1012 connected components in a directed graph" by Esko Nuutila and Eljas
1013 Soisalon-Soininen, in Information Processing Letters volume 49,
1014 number 1, pages 9-14. */
1017 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1019 constraint_edge_t c;
1022 gcc_assert (get_varinfo (n)->node == n);
1023 SET_BIT (si->visited, n);
1024 RESET_BIT (si->in_component, n);
1025 si->visited_index[n] = si->current_index ++;
1027 /* Visit all the successors. */
1028 for (i = 0; VEC_iterate (constraint_edge_t, graph->succs[n], i, c); i++)
1030 /* We only want to find and collapse the zero weight edges. */
1031 if (bitmap_bit_p (c->weights, 0))
1033 unsigned int w = c->dest;
1034 if (!TEST_BIT (si->visited, w))
1035 scc_visit (graph, si, w);
1036 if (!TEST_BIT (si->in_component, w))
1038 unsigned int t = get_varinfo (w)->node;
1039 unsigned int nnode = get_varinfo (n)->node;
1040 if (si->visited_index[t] < si->visited_index[nnode])
1041 get_varinfo (n)->node = t;
1046 /* See if any components have been identified. */
1047 if (get_varinfo (n)->node == n)
1049 unsigned int t = si->visited_index[n];
1050 SET_BIT (si->in_component, n);
1051 while (VEC_length (uint, si->scc_stack) != 0
1052 && t < si->visited_index[VEC_last (uint, si->scc_stack)])
1054 unsigned int w = VEC_pop (uint, si->scc_stack);
1055 get_varinfo (w)->node = n;
1056 SET_BIT (si->in_component, w);
1057 /* Mark this node for collapsing. */
1058 VEC_safe_push (uint, heap, si->unification_queue, w);
1062 VEC_safe_push (uint, heap, si->scc_stack, n);
1066 /* Collapse two variables into one variable. */
1069 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1071 bitmap tosol, fromsol;
1072 struct constraint_edge edge;
1075 condense_varmap_nodes (to, from);
1076 tosol = get_varinfo (to)->solution;
1077 fromsol = get_varinfo (from)->solution;
1078 bitmap_ior_into (tosol, fromsol);
1079 merge_graph_nodes (graph, to, from);
1082 if (valid_graph_edge (graph, edge))
1084 bitmap weights = get_graph_weights (graph, edge);
1085 bitmap_clear_bit (weights, 0);
1086 if (bitmap_empty_p (weights))
1087 erase_graph_self_edge (graph, edge);
1089 bitmap_clear (fromsol);
1090 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1091 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1095 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1096 SI is the Strongly Connected Components information structure that tells us
1097 what components to unify.
1098 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1099 count should be updated to reflect the unification. */
1102 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1103 bool update_changed)
1106 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1109 /* We proceed as follows:
1111 For each component in the queue (components are delineated by
1112 when current_queue_element->node != next_queue_element->node):
1114 rep = representative node for component
1116 For each node (tounify) to be unified in the component,
1117 merge the solution for tounify into tmp bitmap
1119 clear solution for tounify
1121 merge edges from tounify into rep
1123 merge complex constraints from tounify into rep
1125 update changed count to note that tounify will never change
1128 Merge tmp into solution for rep, marking rep changed if this
1129 changed rep's solution.
1131 Delete any 0 weighted self-edges we now have for rep. */
1132 while (i != VEC_length (uint, si->unification_queue))
1134 unsigned int tounify = VEC_index (uint, si->unification_queue, i);
1135 unsigned int n = get_varinfo (tounify)->node;
1137 if (dump_file && (dump_flags & TDF_DETAILS))
1138 fprintf (dump_file, "Unifying %s to %s\n",
1139 get_varinfo (tounify)->name,
1140 get_varinfo (n)->name);
1142 stats.unified_vars_dynamic++;
1144 stats.unified_vars_static++;
1145 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1146 merge_graph_nodes (graph, n, tounify);
1147 condense_varmap_nodes (n, tounify);
1149 if (update_changed && TEST_BIT (changed, tounify))
1151 RESET_BIT (changed, tounify);
1152 if (!TEST_BIT (changed, n))
1153 SET_BIT (changed, n);
1156 gcc_assert (changed_count > 0);
1161 bitmap_clear (get_varinfo (tounify)->solution);
1164 /* If we've either finished processing the entire queue, or
1165 finished processing all nodes for component n, update the solution for
1167 if (i == VEC_length (uint, si->unification_queue)
1168 || get_varinfo (VEC_index (uint, si->unification_queue, i))->node != n)
1170 struct constraint_edge edge;
1172 /* If the solution changes because of the merging, we need to mark
1173 the variable as changed. */
1174 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1176 if (update_changed && !TEST_BIT (changed, n))
1178 SET_BIT (changed, n);
1185 if (valid_graph_edge (graph, edge))
1187 bitmap weights = get_graph_weights (graph, edge);
1188 bitmap_clear_bit (weights, 0);
1189 if (bitmap_empty_p (weights))
1190 erase_graph_self_edge (graph, edge);
1198 /* Information needed to compute the topological ordering of a graph. */
1202 /* sbitmap of visited nodes. */
1204 /* Array that stores the topological order of the graph, *in
1206 VEC(uint,heap) *topo_order;
1210 /* Initialize and return a topological info structure. */
1212 static struct topo_info *
1213 init_topo_info (void)
1215 size_t size = VEC_length (varinfo_t, varmap);
1216 struct topo_info *ti = xmalloc (sizeof (struct topo_info));
1217 ti->visited = sbitmap_alloc (size);
1218 sbitmap_zero (ti->visited);
1219 ti->topo_order = VEC_alloc (uint, heap, 1);
1224 /* Free the topological sort info pointed to by TI. */
1227 free_topo_info (struct topo_info *ti)
1229 sbitmap_free (ti->visited);
1230 VEC_free (uint, heap, ti->topo_order);
1234 /* Visit the graph in topological order, and store the order in the
1235 topo_info structure. */
1238 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1241 VEC(constraint_edge_t,gc) *succs = graph->succs[n];
1242 constraint_edge_t c;
1244 SET_BIT (ti->visited, n);
1245 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1247 if (!TEST_BIT (ti->visited, c->dest))
1248 topo_visit (graph, ti, c->dest);
1250 VEC_safe_push (uint, heap, ti->topo_order, n);
1253 /* Return true if variable N + OFFSET is a legal field of N. */
1256 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1258 varinfo_t ninfo = get_varinfo (n);
1260 /* For things we've globbed to single variables, any offset into the
1261 variable acts like the entire variable, so that it becomes offset
1263 if (n == anything_id
1264 || ninfo->is_artificial_var
1265 || ninfo->is_unknown_size_var)
1270 return n > anything_id
1271 && (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1274 /* Process a constraint C that represents *x = &y. */
1277 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1278 constraint_t c, bitmap delta)
1280 unsigned int rhs = c->rhs.var;
1281 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1285 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1286 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1288 if (type_safe (j, &offset))
1290 /* *x != NULL && *x != ANYTHING*/
1294 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1295 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1297 sol = get_varinfo (t)->solution;
1298 if (!bitmap_bit_p (sol, rhs))
1300 bitmap_set_bit (sol, rhs);
1301 if (!TEST_BIT (changed, t))
1303 SET_BIT (changed, t);
1309 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1314 /* Process a constraint C that represents x = *y, using DELTA as the
1315 starting solution. */
1318 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1321 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1322 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1324 bitmap sol = get_varinfo (lhs)->solution;
1328 /* For each variable j in delta (Sol(y)), add
1329 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1330 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1332 if (type_safe (j, &roffset))
1335 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1338 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1340 if (int_add_graph_edge (graph, lhs, t, 0))
1341 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1344 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1348 /* If the LHS solution changed, mark the var as changed. */
1351 get_varinfo (lhs)->solution = sol;
1352 if (!TEST_BIT (changed, lhs))
1354 SET_BIT (changed, lhs);
1360 /* Process a constraint C that represents *x = y. */
1363 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1365 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1366 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1367 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1368 bitmap sol = get_varinfo (rhs)->solution;
1372 /* For each member j of delta (Sol(x)), add an edge from y to j and
1373 union Sol(y) into Sol(j) */
1374 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1376 if (type_safe (j, &loff))
1380 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1382 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1384 if (int_add_graph_edge (graph, t, rhs, roff))
1386 bitmap tmp = get_varinfo (t)->solution;
1387 if (set_union_with_increment (tmp, sol, roff))
1389 get_varinfo (t)->solution = tmp;
1392 sol = get_varinfo (rhs)->solution;
1394 if (!TEST_BIT (changed, t))
1396 SET_BIT (changed, t);
1403 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1407 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1408 constraint (IE *x = &y, x = *y, and *x = y). */
1411 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1413 if (c->lhs.type == DEREF)
1415 if (c->rhs.type == ADDRESSOF)
1418 do_da_constraint (graph, c, delta);
1423 do_ds_constraint (graph, c, delta);
1429 do_sd_constraint (graph, c, delta);
1433 /* Initialize and return a new SCC info structure. */
1435 static struct scc_info *
1436 init_scc_info (void)
1438 struct scc_info *si = xmalloc (sizeof (struct scc_info));
1439 size_t size = VEC_length (varinfo_t, varmap);
1441 si->current_index = 0;
1442 si->visited = sbitmap_alloc (size);
1443 sbitmap_zero (si->visited);
1444 si->in_component = sbitmap_alloc (size);
1445 sbitmap_ones (si->in_component);
1446 si->visited_index = xcalloc (sizeof (unsigned int), size + 1);
1447 si->scc_stack = VEC_alloc (uint, heap, 1);
1448 si->unification_queue = VEC_alloc (uint, heap, 1);
1452 /* Free an SCC info structure pointed to by SI */
1455 free_scc_info (struct scc_info *si)
1457 sbitmap_free (si->visited);
1458 sbitmap_free (si->in_component);
1459 free (si->visited_index);
1460 VEC_free (uint, heap, si->scc_stack);
1461 VEC_free (uint, heap, si->unification_queue);
1466 /* Find cycles in GRAPH that occur, using strongly connected components, and
1467 collapse the cycles into a single representative node. if UPDATE_CHANGED
1468 is true, then update the changed sbitmap to note those nodes whose
1469 solutions have changed as a result of collapsing. */
1472 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1475 unsigned int size = VEC_length (varinfo_t, varmap);
1476 struct scc_info *si = init_scc_info ();
1478 for (i = 0; i != size; ++i)
1479 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1480 scc_visit (graph, si, i);
1481 process_unification_queue (graph, si, update_changed);
1485 /* Compute a topological ordering for GRAPH, and store the result in the
1486 topo_info structure TI. */
1489 compute_topo_order (constraint_graph_t graph,
1490 struct topo_info *ti)
1493 unsigned int size = VEC_length (varinfo_t, varmap);
1495 for (i = 0; i != size; ++i)
1496 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1497 topo_visit (graph, ti, i);
1500 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1503 bitmap_other_than_zero_bit_set (bitmap b)
1508 if (bitmap_empty_p (b))
1510 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1515 /* Perform offline variable substitution.
1517 This is a linear time way of identifying variables that must have
1518 equivalent points-to sets, including those caused by static cycles,
1519 and single entry subgraphs, in the constraint graph.
1521 The technique is described in "Off-line variable substitution for
1522 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1523 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1526 perform_var_substitution (constraint_graph_t graph)
1528 struct topo_info *ti = init_topo_info ();
1530 /* Compute the topological ordering of the graph, then visit each
1531 node in topological order. */
1532 compute_topo_order (graph, ti);
1534 while (VEC_length (uint, ti->topo_order) != 0)
1536 unsigned int i = VEC_pop (uint, ti->topo_order);
1538 varinfo_t vi = get_varinfo (i);
1539 bool okay_to_elim = false;
1540 unsigned int root = VEC_length (varinfo_t, varmap);
1541 VEC(constraint_edge_t,gc) *predvec = graph->preds[i];
1542 constraint_edge_t ce;
1545 /* We can't eliminate things whose address is taken, or which is
1546 the target of a dereference. */
1547 if (vi->address_taken || vi->indirect_target)
1550 /* See if all predecessors of I are ripe for elimination */
1551 for (pred = 0; VEC_iterate (constraint_edge_t, predvec, pred, ce); pred++)
1555 weight = get_graph_weights (graph, *ce);
1557 /* We can't eliminate variables that have non-zero weighted
1558 edges between them. */
1559 if (bitmap_other_than_zero_bit_set (weight))
1561 okay_to_elim = false;
1564 w = get_varinfo (ce->dest)->node;
1566 /* We can't eliminate the node if one of the predecessors is
1567 part of a different strongly connected component. */
1571 okay_to_elim = true;
1575 okay_to_elim = false;
1579 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1580 then Solution(i) is a subset of Solution (w), where w is a
1581 predecessor in the graph.
1582 Corrolary: If all predecessors of i have the same
1583 points-to set, then i has that same points-to set as
1584 those predecessors. */
1585 tmp = BITMAP_ALLOC (NULL);
1586 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1587 get_varinfo (w)->solution);
1588 if (!bitmap_empty_p (tmp))
1590 okay_to_elim = false;
1597 /* See if the root is different than the original node.
1598 If so, we've found an equivalence. */
1599 if (root != get_varinfo (i)->node && okay_to_elim)
1601 /* Found an equivalence */
1602 get_varinfo (i)->node = root;
1603 collapse_nodes (graph, root, i);
1604 if (dump_file && (dump_flags & TDF_DETAILS))
1605 fprintf (dump_file, "Collapsing %s into %s\n",
1606 get_varinfo (i)->name,
1607 get_varinfo (root)->name);
1608 stats.collapsed_vars++;
1612 free_topo_info (ti);
1616 /* Solve the constraint graph GRAPH using our worklist solver.
1617 This is based on the PW* family of solvers from the "Efficient Field
1618 Sensitive Pointer Analysis for C" paper.
1619 It works by iterating over all the graph nodes, processing the complex
1620 constraints and propagating the copy constraints, until everything stops
1621 changed. This corresponds to steps 6-8 in the solving list given above. */
1624 solve_graph (constraint_graph_t graph)
1626 unsigned int size = VEC_length (varinfo_t, varmap);
1629 changed_count = size;
1630 changed = sbitmap_alloc (size);
1631 sbitmap_ones (changed);
1633 /* The already collapsed/unreachable nodes will never change, so we
1634 need to account for them in changed_count. */
1635 for (i = 0; i < size; i++)
1636 if (get_varinfo (i)->node != i)
1639 while (changed_count > 0)
1642 struct topo_info *ti = init_topo_info ();
1645 bitmap_obstack_initialize (&iteration_obstack);
1649 /* We already did cycle elimination once, when we did
1650 variable substitution, so we don't need it again for the
1652 if (stats.iterations > 1)
1653 find_and_collapse_graph_cycles (graph, true);
1658 compute_topo_order (graph, ti);
1660 while (VEC_length (uint, ti->topo_order) != 0)
1662 i = VEC_pop (uint, ti->topo_order);
1663 gcc_assert (get_varinfo (i)->node == i);
1665 /* If the node has changed, we need to process the
1666 complex constraints and outgoing edges again. */
1667 if (TEST_BIT (changed, i))
1671 constraint_edge_t e;
1673 VEC(constraint_t,gc) *complex = get_varinfo (i)->complex;
1674 VEC(constraint_edge_t,gc) *succs;
1676 RESET_BIT (changed, i);
1679 /* Process the complex constraints */
1680 solution = get_varinfo (i)->solution;
1681 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
1682 do_complex_constraint (graph, c, solution);
1684 /* Propagate solution to all successors. */
1685 succs = graph->succs[i];
1686 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
1688 bitmap tmp = get_varinfo (e->dest)->solution;
1691 bitmap weights = e->weights;
1694 gcc_assert (!bitmap_empty_p (weights));
1695 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
1696 flag |= set_union_with_increment (tmp, solution, k);
1700 get_varinfo (e->dest)->solution = tmp;
1701 if (!TEST_BIT (changed, e->dest))
1703 SET_BIT (changed, e->dest);
1710 free_topo_info (ti);
1711 bitmap_obstack_release (&iteration_obstack);
1714 sbitmap_free (changed);
1718 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1720 /* Map from trees to variable ids. */
1721 static htab_t id_for_tree;
1723 typedef struct tree_id
1729 /* Hash a tree id structure. */
1732 tree_id_hash (const void *p)
1734 const tree_id_t ta = (tree_id_t) p;
1735 return htab_hash_pointer (ta->t);
1738 /* Return true if the tree in P1 and the tree in P2 are the same. */
1741 tree_id_eq (const void *p1, const void *p2)
1743 const tree_id_t ta1 = (tree_id_t) p1;
1744 const tree_id_t ta2 = (tree_id_t) p2;
1745 return ta1->t == ta2->t;
1748 /* Insert ID as the variable id for tree T in the hashtable. */
1751 insert_id_for_tree (tree t, int id)
1754 struct tree_id finder;
1758 slot = htab_find_slot (id_for_tree, &finder, INSERT);
1759 gcc_assert (*slot == NULL);
1760 new_pair = xmalloc (sizeof (struct tree_id));
1763 *slot = (void *)new_pair;
1766 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1767 exist in the hash table, return false, otherwise, return true and
1768 set *ID to the id we found. */
1771 lookup_id_for_tree (tree t, unsigned int *id)
1774 struct tree_id finder;
1777 pair = htab_find (id_for_tree, &finder);
1784 /* Return a printable name for DECL */
1787 alias_get_name (tree decl)
1789 const char *res = get_name (decl);
1791 int num_printed = 0;
1797 if (TREE_CODE (decl) == SSA_NAME)
1799 num_printed = asprintf (&temp, "%s_%u",
1800 alias_get_name (SSA_NAME_VAR (decl)),
1801 SSA_NAME_VERSION (decl));
1803 else if (DECL_P (decl))
1805 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
1807 if (num_printed > 0)
1809 res = ggc_strdup (temp);
1815 /* Find the variable id for tree T in the hashtable.
1816 If T doesn't exist in the hash table, create an entry for it. */
1819 get_id_for_tree (tree t)
1822 struct tree_id finder;
1825 pair = htab_find (id_for_tree, &finder);
1827 return create_variable_info_for (t, alias_get_name (t));
1832 /* Get a constraint expression from an SSA_VAR_P node. */
1834 static struct constraint_expr
1835 get_constraint_exp_from_ssa_var (tree t)
1837 struct constraint_expr cexpr;
1839 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
1841 /* For parameters, get at the points-to set for the actual parm
1843 if (TREE_CODE (t) == SSA_NAME
1844 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
1845 && default_def (SSA_NAME_VAR (t)) == t)
1846 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
1848 cexpr.type = SCALAR;
1850 if (TREE_READONLY (t))
1852 cexpr.type = ADDRESSOF;
1853 cexpr.var = readonly_id;
1856 cexpr.var = get_id_for_tree (t);
1862 /* Process a completed constraint T, and add it to the constraint
1866 process_constraint (constraint_t t)
1868 struct constraint_expr rhs = t->rhs;
1869 struct constraint_expr lhs = t->lhs;
1871 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
1872 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
1874 /* ANYTHING == ANYTHING is pointless. */
1875 if (lhs.var == anything_id && rhs.var == anything_id)
1878 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1879 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
1884 process_constraint (t);
1886 /* This can happen in our IR with things like n->a = *p */
1887 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
1889 /* Split into tmp = *rhs, *lhs = tmp */
1890 tree rhsdecl = get_varinfo (rhs.var)->decl;
1891 tree pointertype = TREE_TYPE (rhsdecl);
1892 tree pointedtotype = TREE_TYPE (pointertype);
1893 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
1894 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
1896 /* If this is an aggregate of known size, we should have passed
1897 this off to do_structure_copy, and it should have broken it
1899 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
1900 || get_varinfo (rhs.var)->is_unknown_size_var);
1902 process_constraint (new_constraint (tmplhs, rhs));
1903 process_constraint (new_constraint (lhs, tmplhs));
1905 else if (rhs.type == ADDRESSOF)
1908 gcc_assert (rhs.offset == 0);
1910 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
1911 vi->address_taken = true;
1913 VEC_safe_push (constraint_t, gc, constraints, t);
1917 if (lhs.type != DEREF && rhs.type == DEREF)
1918 get_varinfo (lhs.var)->indirect_target = true;
1919 VEC_safe_push (constraint_t, gc, constraints, t);
1924 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1927 static unsigned HOST_WIDE_INT
1928 bitpos_of_field (const tree fdecl)
1931 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
1932 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
1935 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
1936 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
1940 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1942 static struct constraint_expr
1943 get_constraint_for_component_ref (tree t)
1945 struct constraint_expr result;
1946 HOST_WIDE_INT bitsize;
1947 HOST_WIDE_INT bitpos;
1949 enum machine_mode mode;
1955 result.type = SCALAR;
1958 /* Some people like to do cute things like take the address of
1961 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
1962 forzero = TREE_OPERAND (forzero, 0);
1964 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
1967 result.var = integer_id;
1968 result.type = SCALAR;
1972 t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode,
1973 &unsignedp, &volatilep, false);
1974 result = get_constraint_for (t);
1976 /* This can also happen due to weird offsetof type macros. */
1977 if (TREE_CODE (t) != ADDR_EXPR && result.type == ADDRESSOF)
1978 result.type = SCALAR;
1980 /* If we know where this goes, then yay. Otherwise, booo. */
1982 if (offset == NULL && bitsize != -1)
1984 result.offset = bitpos;
1988 result.var = anything_id;
1992 if (result.type == SCALAR)
1994 /* In languages like C, you can access one past the end of an
1995 array. You aren't allowed to dereference it, so we can
1996 ignore this constraint. When we handle pointer subtraction,
1997 we may have to do something cute here. */
1999 if (result.offset < get_varinfo (result.var)->fullsize)
2000 result.var = first_vi_for_offset (get_varinfo (result.var),
2003 if (dump_file && (dump_flags & TDF_DETAILS))
2004 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2013 /* Dereference the constraint expression CONS, and return the result.
2014 DEREF (ADDRESSOF) = SCALAR
2015 DEREF (SCALAR) = DEREF
2016 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2017 This is needed so that we can handle dereferencing DEREF constraints. */
2019 static struct constraint_expr
2020 do_deref (struct constraint_expr cons)
2022 if (cons.type == SCALAR)
2027 else if (cons.type == ADDRESSOF)
2032 else if (cons.type == DEREF)
2034 tree tmpvar = create_tmp_var_raw (ptr_type_node, "derefmp");
2035 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2036 process_constraint (new_constraint (tmplhs, cons));
2037 cons.var = tmplhs.var;
2044 /* Given a tree T, return the constraint expression for it. */
2046 static struct constraint_expr
2047 get_constraint_for (tree t)
2049 struct constraint_expr temp;
2051 /* x = integer is all glommed to a single variable, which doesn't
2052 point to anything by itself. That is, of course, unless it is an
2053 integer constant being treated as a pointer, in which case, we
2054 will return that this is really the addressof anything. This
2055 happens below, since it will fall into the default case. The only
2056 case we know something about an integer treated like a pointer is
2057 when it is the NULL pointer, and then we just say it points to
2059 if (TREE_CODE (t) == INTEGER_CST
2060 && !POINTER_TYPE_P (TREE_TYPE (t)))
2062 temp.var = integer_id;
2067 else if (TREE_CODE (t) == INTEGER_CST
2068 && integer_zerop (t))
2070 temp.var = nothing_id;
2071 temp.type = ADDRESSOF;
2076 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2078 case tcc_expression:
2080 switch (TREE_CODE (t))
2084 temp = get_constraint_for (TREE_OPERAND (t, 0));
2085 if (temp.type == DEREF)
2088 temp.type = ADDRESSOF;
2094 /* XXX: In interprocedural mode, if we didn't have the
2095 body, we would need to do *each pointer argument =
2097 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2099 tree heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2100 temp.var = create_variable_info_for (heapvar,
2101 alias_get_name (heapvar));
2103 get_varinfo (temp.var)->is_artificial_var = 1;
2104 temp.type = ADDRESSOF;
2111 temp.type = ADDRESSOF;
2112 temp.var = anything_id;
2120 switch (TREE_CODE (t))
2124 temp = get_constraint_for (TREE_OPERAND (t, 0));
2125 temp = do_deref (temp);
2130 temp = get_constraint_for_component_ref (t);
2134 temp.type = ADDRESSOF;
2135 temp.var = anything_id;
2143 switch (TREE_CODE (t))
2147 case NON_LVALUE_EXPR:
2149 tree op = TREE_OPERAND (t, 0);
2151 /* Cast from non-pointer to pointers are bad news for us.
2152 Anything else, we see through */
2153 if (!(POINTER_TYPE_P (TREE_TYPE (t)) &&
2154 ! POINTER_TYPE_P (TREE_TYPE (op))))
2155 return get_constraint_for (op);
2159 temp.type = ADDRESSOF;
2160 temp.var = anything_id;
2166 case tcc_exceptional:
2168 switch (TREE_CODE (t))
2171 return get_constraint_for (PHI_RESULT (t));
2173 return get_constraint_exp_from_ssa_var (t);
2176 temp.type = ADDRESSOF;
2177 temp.var = anything_id;
2183 case tcc_declaration:
2184 return get_constraint_exp_from_ssa_var (t);
2187 temp.type = ADDRESSOF;
2188 temp.var = anything_id;
2196 /* Handle the structure copy case where we have a simple structure copy
2197 between LHS and RHS that is of SIZE (in bits)
2199 For each field of the lhs variable (lhsfield)
2200 For each field of the rhs variable at lhsfield.offset (rhsfield)
2201 add the constraint lhsfield = rhsfield
2205 do_simple_structure_copy (const struct constraint_expr lhs,
2206 const struct constraint_expr rhs,
2207 const unsigned HOST_WIDE_INT size)
2209 varinfo_t p = get_varinfo (lhs.var);
2210 unsigned HOST_WIDE_INT pstart,last;
2213 last = p->offset + size;
2214 for (; p && p->offset < last; p = p->next)
2217 struct constraint_expr templhs = lhs;
2218 struct constraint_expr temprhs = rhs;
2219 unsigned HOST_WIDE_INT fieldoffset;
2221 templhs.var = p->id;
2222 q = get_varinfo (temprhs.var);
2223 fieldoffset = p->offset - pstart;
2224 q = first_vi_for_offset (q, q->offset + fieldoffset);
2225 temprhs.var = q->id;
2226 process_constraint (new_constraint (templhs, temprhs));
2231 /* Handle the structure copy case where we have a structure copy between a
2232 aggregate on the LHS and a dereference of a pointer on the RHS
2233 that is of SIZE (in bits)
2235 For each field of the lhs variable (lhsfield)
2236 rhs.offset = lhsfield->offset
2237 add the constraint lhsfield = rhs
2241 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2242 const struct constraint_expr rhs,
2243 const unsigned HOST_WIDE_INT size)
2245 varinfo_t p = get_varinfo (lhs.var);
2246 unsigned HOST_WIDE_INT pstart,last;
2248 last = p->offset + size;
2250 for (; p && p->offset < last; p = p->next)
2253 struct constraint_expr templhs = lhs;
2254 struct constraint_expr temprhs = rhs;
2255 unsigned HOST_WIDE_INT fieldoffset;
2258 if (templhs.type == SCALAR)
2259 templhs.var = p->id;
2261 templhs.offset = p->offset;
2263 q = get_varinfo (temprhs.var);
2264 fieldoffset = p->offset - pstart;
2265 temprhs.offset += fieldoffset;
2266 process_constraint (new_constraint (templhs, temprhs));
2270 /* Handle the structure copy case where we have a structure copy
2271 between a aggregate on the RHS and a dereference of a pointer on
2272 the LHS that is of SIZE (in bits)
2274 For each field of the rhs variable (rhsfield)
2275 lhs.offset = rhsfield->offset
2276 add the constraint lhs = rhsfield
2280 do_lhs_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 (rhs.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 (temprhs.type == SCALAR)
2298 temprhs.var = p->id;
2300 temprhs.offset = p->offset;
2302 q = get_varinfo (templhs.var);
2303 fieldoffset = p->offset - pstart;
2304 templhs.offset += fieldoffset;
2305 process_constraint (new_constraint (templhs, temprhs));
2310 /* Handle aggregate copies by expanding into copies of the respective
2311 fields of the structures. */
2314 do_structure_copy (tree lhsop, tree rhsop)
2316 struct constraint_expr lhs, rhs, tmp;
2318 unsigned HOST_WIDE_INT lhssize;
2319 unsigned HOST_WIDE_INT rhssize;
2321 lhssize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (lhsop)));
2322 rhssize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (rhsop)));
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 /* If the RHS is a special var, set all the LHS fields to that
2336 if (rhs.var <= integer_id)
2338 for (p = get_varinfo (lhs.var); p; p = p->next)
2340 struct constraint_expr templhs = lhs;
2341 struct constraint_expr temprhs = rhs;
2342 if (templhs.type == SCALAR )
2343 templhs.var = p->id;
2345 templhs.offset += p->offset;
2346 process_constraint (new_constraint (templhs, temprhs));
2351 if (rhs.type == SCALAR && lhs.type == SCALAR)
2352 do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2353 else if (lhs.type != DEREF && rhs.type == DEREF)
2354 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2355 else if (lhs.type == DEREF && rhs.type != DEREF)
2356 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2359 tree rhsdecl = get_varinfo (rhs.var)->decl;
2360 tree pointertype = TREE_TYPE (rhsdecl);
2361 tree pointedtotype = TREE_TYPE (pointertype);
2363 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2364 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2365 lhs = get_constraint_for (tmpvar);
2366 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2368 lhs = get_constraint_for (lhsop);
2369 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2375 /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere
2379 ref_contains_indirect_ref (tree ref)
2381 while (handled_component_p (ref))
2383 if (TREE_CODE (ref) == INDIRECT_REF)
2385 ref = TREE_OPERAND (ref, 0);
2391 /* Tree walker that is the heart of the aliasing infrastructure.
2392 TP is a pointer to the current tree.
2393 WALK_SUBTREES specifies whether to continue traversing subtrees or
2395 Returns NULL_TREE when we should stop.
2397 This function is the main part of the constraint builder. It
2398 walks the trees, calling the appropriate building functions
2399 to process various statements. */
2402 find_func_aliases (tree t)
2404 struct constraint_expr lhs, rhs;
2405 switch (TREE_CODE (t))
2411 /* Only care about pointers and structures containing
2413 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
2414 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
2416 lhs = get_constraint_for (PHI_RESULT (t));
2417 for (i = 0; i < PHI_NUM_ARGS (t); i++)
2419 rhs = get_constraint_for (PHI_ARG_DEF (t, i));
2420 process_constraint (new_constraint (lhs, rhs));
2428 tree lhsop = TREE_OPERAND (t, 0);
2429 tree rhsop = TREE_OPERAND (t, 1);
2432 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2433 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
2435 do_structure_copy (lhsop, rhsop);
2439 /* Only care about operations with pointers, structures
2440 containing pointers, dereferences, and call
2442 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
2443 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2444 || ref_contains_indirect_ref (lhsop)
2445 || TREE_CODE (rhsop) == CALL_EXPR)
2447 lhs = get_constraint_for (lhsop);
2448 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
2450 /* RHS that consist of unary operations,
2451 exceptional types, or bare decls/constants, get
2452 handled directly by get_constraint_for. */
2454 case tcc_declaration:
2456 case tcc_exceptional:
2457 case tcc_expression:
2460 rhs = get_constraint_for (rhsop);
2461 process_constraint (new_constraint (lhs, rhs));
2465 /* Otherwise, walk each operand. */
2467 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
2469 tree op = TREE_OPERAND (rhsop, i);
2470 rhs = get_constraint_for (op);
2471 process_constraint (new_constraint (lhs, rhs));
2485 /* Find the first varinfo in the same variable as START that overlaps with
2487 Effectively, walk the chain of fields for the variable START to find the
2488 first field that overlaps with OFFSET.
2489 Abort if we can't find one. */
2492 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
2494 varinfo_t curr = start;
2497 /* We may not find a variable in the field list with the actual
2498 offset when when we have glommed a structure to a variable.
2499 In that case, however, offset should still be within the size
2501 if (offset >= curr->offset && offset < (curr->offset + curr->size))
2510 /* Insert the varinfo FIELD into the field list for BASE, ordered by
2514 insert_into_field_list (varinfo_t base, varinfo_t field)
2516 varinfo_t prev = base;
2517 varinfo_t curr = base->next;
2528 if (field->offset <= curr->offset)
2533 field->next = prev->next;
2538 /* qsort comparison function for two fieldoff's PA and PB */
2541 fieldoff_compare (const void *pa, const void *pb)
2543 const fieldoff_s *foa = (const fieldoff_s *)pa;
2544 const fieldoff_s *fob = (const fieldoff_s *)pb;
2545 HOST_WIDE_INT foasize, fobsize;
2547 if (foa->offset != fob->offset)
2548 return foa->offset - fob->offset;
2550 foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
2551 fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
2552 return foasize - fobsize;
2555 /* Sort a fieldstack according to the field offset and sizes. */
2556 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
2558 qsort (VEC_address (fieldoff_s, fieldstack),
2559 VEC_length (fieldoff_s, fieldstack),
2560 sizeof (fieldoff_s),
2564 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
2565 of TYPE onto fieldstack, recording their offsets along the way.
2566 OFFSET is used to keep track of the offset in this entire structure, rather
2567 than just the immediately containing structure. Returns the number
2569 HAS_UNION is set to true if we find a union type as a field of
2573 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
2574 HOST_WIDE_INT offset, bool *has_union)
2579 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2580 if (TREE_CODE (field) == FIELD_DECL)
2585 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
2586 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
2589 if (!var_can_have_subvars (field))
2591 else if (!(push_fields_onto_fieldstack
2592 (TREE_TYPE (field), fieldstack,
2593 offset + bitpos_of_field (field), has_union))
2594 && DECL_SIZE (field)
2595 && !integer_zerop (DECL_SIZE (field)))
2596 /* Empty structures may have actual size, like in C++. So
2597 see if we didn't push any subfields and the size is
2598 nonzero, push the field onto the stack */
2605 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
2606 pair->field = field;
2607 pair->offset = offset + bitpos_of_field (field);
2616 make_constraint_to_anything (varinfo_t vi)
2618 struct constraint_expr lhs, rhs;
2624 rhs.var = anything_id;
2626 rhs.type = ADDRESSOF;
2627 process_constraint (new_constraint (lhs, rhs));
2630 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
2631 This will also create any varinfo structures necessary for fields
2635 create_variable_info_for (tree decl, const char *name)
2637 unsigned int index = VEC_length (varinfo_t, varmap);
2639 tree decltype = TREE_TYPE (decl);
2640 bool notokay = false;
2642 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
2644 VEC (fieldoff_s,heap) *fieldstack = NULL;
2646 if (var_can_have_subvars (decl) && use_field_sensitive)
2648 push_fields_onto_fieldstack (decltype, &fieldstack, 0, ¬okay);
2650 VEC_free (fieldoff_s, heap, fieldstack);
2653 /* If this variable already has subvars, just create the variables for the
2654 subvars and we are done.
2655 NOTE: This assumes things haven't generated uses of previously
2656 unused structure fields. */
2657 if (use_field_sensitive
2659 && var_can_have_subvars (decl)
2661 && (svars = get_subvars_for_var (decl)))
2664 varinfo_t base = NULL;
2665 unsigned int firstindex = index;
2667 for (sv = svars; sv; sv = sv->next)
2669 /* For debugging purposes, this will print the names of the
2670 fields as "<var>.<offset>.<size>"
2671 This is only for debugging purposes. */
2672 #define PRINT_LONG_NAMES
2673 #ifdef PRINT_LONG_NAMES
2675 const char *newname;
2677 asprintf (&tempname,
2678 "%s." HOST_WIDE_INT_PRINT_DEC "." HOST_WIDE_INT_PRINT_DEC,
2679 alias_get_name (decl), sv->offset, sv->size);
2680 newname = ggc_strdup (tempname);
2682 vi = new_var_info (sv->var, index, newname, index);
2684 vi = new_var_info (sv->var, index, alias_get_name (sv->var), index);
2687 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2688 vi->size = sv->size;
2689 vi->offset = sv->offset;
2693 insert_id_for_tree (decl, index);
2697 insert_into_field_list (base, vi);
2699 insert_id_for_tree (sv->var, index);
2700 VEC_safe_push (varinfo_t, gc, varmap, vi);
2702 make_constraint_to_anything (vi);
2710 /* If the variable doesn't have subvars, we may end up needing to
2711 sort the field list and create fake variables for all the
2713 vi = new_var_info (decl, index, name, index);
2716 if (!TYPE_SIZE (decltype)
2717 || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
2718 || TREE_CODE (decltype) == ARRAY_TYPE
2719 || TREE_CODE (decltype) == UNION_TYPE
2720 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
2722 vi->is_unknown_size_var = true;
2728 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
2729 vi->size = vi->fullsize;
2732 insert_id_for_tree (vi->decl, index);
2733 VEC_safe_push (varinfo_t, gc, varmap, vi);
2735 make_constraint_to_anything (vi);
2738 if (use_field_sensitive
2740 && !vi->is_unknown_size_var
2741 && var_can_have_subvars (decl))
2743 unsigned int newindex = VEC_length (varinfo_t, varmap);
2744 fieldoff_s *fo = NULL;
2748 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
2750 if (!DECL_SIZE (fo->field)
2751 || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
2752 || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE
2759 sort_fieldstack (fieldstack);
2761 if (VEC_length (fieldoff_s, fieldstack) != 0)
2762 fo = VEC_index (fieldoff_s, fieldstack, 0);
2764 if (fo == NULL || notokay)
2766 vi->is_unknown_size_var = 1;
2769 VEC_free (fieldoff_s, heap, fieldstack);
2774 gcc_assert (bitpos_of_field (field) == 0);
2775 vi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
2776 for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
2779 const char *newname;
2783 newindex = VEC_length (varinfo_t, varmap);
2784 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (field));
2785 newname = ggc_strdup (tempname);
2787 newvi = new_var_info (decl, newindex, newname, newindex);
2788 newvi->offset = fo->offset;
2789 newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
2790 newvi->fullsize = vi->fullsize;
2791 insert_into_field_list (vi, newvi);
2792 VEC_safe_push (varinfo_t, gc, varmap, newvi);
2794 make_constraint_to_anything (newvi);
2798 VEC_free (fieldoff_s, heap, fieldstack);
2803 /* Print out the points-to solution for VAR to FILE. */
2806 dump_solution_for_var (FILE *file, unsigned int var)
2808 varinfo_t vi = get_varinfo (var);
2812 fprintf (file, "%s = {", vi->name);
2813 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
2815 fprintf (file, "%s,", get_varinfo (i)->name);
2817 fprintf (file, "}\n");
2820 /* Print the points-to solution for VAR to stdout. */
2823 debug_solution_for_var (unsigned int var)
2825 dump_solution_for_var (stdout, var);
2829 /* Create varinfo structures for all of the variables in the
2830 function for intraprocedural mode. */
2833 intra_create_variable_infos (void)
2837 /* For each incoming argument arg, ARG = &ANYTHING */
2838 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
2840 struct constraint_expr lhs;
2841 struct constraint_expr rhs;
2846 lhs.var = create_variable_info_for (t, alias_get_name (t));
2848 get_varinfo (lhs.var)->is_artificial_var = true;
2849 rhs.var = anything_id;
2850 rhs.type = ADDRESSOF;
2853 for (p = get_varinfo (lhs.var); p; p = p->next)
2855 struct constraint_expr temp = lhs;
2857 process_constraint (new_constraint (temp, rhs));
2863 /* Set bits in INTO corresponding to the variable uids in solution set
2867 set_uids_in_ptset (bitmap into, bitmap from)
2872 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
2874 varinfo_t vi = get_varinfo (i);
2876 /* We may end up with labels in the points-to set because people
2877 take their address, and they are _DECL's. */
2878 if (TREE_CODE (vi->decl) == VAR_DECL
2879 || TREE_CODE (vi->decl) == PARM_DECL)
2880 bitmap_set_bit (into, var_ann (vi->decl)->uid);
2883 static int have_alias_info = false;
2885 /* Given a pointer variable P, fill in its points-to set, or return
2886 false if we can't. */
2889 find_what_p_points_to (tree p)
2891 unsigned int id = 0;
2892 if (!have_alias_info)
2894 if (lookup_id_for_tree (p, &id))
2896 varinfo_t vi = get_varinfo (id);
2898 if (vi->is_artificial_var)
2901 /* See if this is a field or a structure */
2902 if (vi->size != vi->fullsize)
2904 if (!var_can_have_subvars (vi->decl)
2905 || get_subvars_for_var (vi->decl) == NULL)
2910 struct ptr_info_def *pi = get_ptr_info (p);
2914 /* This variable may have been collapsed, let's get the real
2916 vi = get_varinfo (vi->node);
2918 /* Make sure there aren't any artificial vars in the points
2919 to set. XXX: Note that we need to translate our heap
2920 variables to something. */
2921 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
2923 if (get_varinfo (i)->is_artificial_var)
2926 pi->pt_anything = false;
2928 pi->pt_vars = BITMAP_GGC_ALLOC ();
2929 set_uids_in_ptset (pi->pt_vars, vi->solution);
2936 /* Initialize things necessary to perform PTA */
2939 init_alias_vars (void)
2941 bitmap_obstack_initialize (&ptabitmap_obstack);
2944 /* Dump the points-to information to OUTFILE. */
2947 dump_sa_points_to_info (FILE *outfile)
2951 if (dump_flags & TDF_STATS)
2953 fprintf (outfile, "Stats:\n");
2954 fprintf (outfile, "Total vars:%d\n", stats.total_vars);
2955 fprintf (outfile, "Statically unified vars:%d\n", stats.unified_vars_static);
2956 fprintf (outfile, "Collapsed vars:%d\n", stats.collapsed_vars);
2957 fprintf (outfile, "Dynamically unified vars:%d\n", stats.unified_vars_dynamic);
2958 fprintf (outfile, "Iterations:%d\n", stats.iterations);
2960 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
2961 dump_solution_for_var (outfile, i);
2965 /* Initialize the always-existing constraint variables for NULL
2966 ANYTHING, READONLY, and INTEGER */
2969 init_base_vars (void)
2971 struct constraint_expr lhs, rhs;
2973 /* Create the NULL variable, used to represent that a variable points
2975 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
2976 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
2977 insert_id_for_tree (nothing_tree, 0);
2978 var_nothing->is_artificial_var = 1;
2979 var_nothing->offset = 0;
2980 var_nothing->size = ~0;
2981 var_nothing->fullsize = ~0;
2983 VEC_safe_push (varinfo_t, gc, varmap, var_nothing);
2985 /* Create the ANYTHING variable, used to represent that a variable
2986 points to some unknown piece of memory. */
2987 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
2988 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
2989 insert_id_for_tree (anything_tree, 1);
2990 var_anything->is_artificial_var = 1;
2991 var_anything->size = ~0;
2992 var_anything->offset = 0;
2993 var_anything->next = NULL;
2994 var_anything->fullsize = ~0;
2997 /* Anything points to anything. This makes deref constraints just
2998 work in the presence of linked list and other p = *p type loops,
2999 by saying that *ANYTHING = ANYTHING. */
3000 VEC_safe_push (varinfo_t, gc, varmap, var_anything);
3002 lhs.var = anything_id;
3004 rhs.type = ADDRESSOF;
3005 rhs.var = anything_id;
3007 var_anything->address_taken = true;
3008 process_constraint (new_constraint (lhs, rhs));
3011 /* Create the READONLY variable, used to represent that a variable
3012 points to readonly memory. */
3013 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
3014 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
3015 var_readonly->is_artificial_var = 1;
3016 var_readonly->offset = 0;
3017 var_readonly->size = ~0;
3018 var_readonly->fullsize = ~0;
3019 var_readonly->next = NULL;
3020 insert_id_for_tree (readonly_tree, 2);
3022 VEC_safe_push (varinfo_t, gc, varmap, var_readonly);
3024 /* readonly memory points to anything, in order to make deref
3025 easier. In reality, it points to anything the particular
3026 readonly variable can point to, but we don't track this
3029 lhs.var = readonly_id;
3031 rhs.type = ADDRESSOF;
3032 rhs.var = anything_id;
3034 var_readonly->address_taken = true;
3036 process_constraint (new_constraint (lhs, rhs));
3038 /* Create the INTEGER variable, used to represent that a variable points
3040 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
3041 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
3042 insert_id_for_tree (integer_tree, 3);
3043 var_integer->is_artificial_var = 1;
3044 var_integer->size = ~0;
3045 var_integer->fullsize = ~0;
3046 var_integer->offset = 0;
3047 var_integer->next = NULL;
3049 VEC_safe_push (varinfo_t, gc, varmap, var_integer);
3053 /* Create points-to sets for the current function. See the comments
3054 at the start of the file for an algorithmic overview. */
3057 create_alias_vars (void)
3064 constraint_pool = create_alloc_pool ("Constraint pool",
3065 sizeof (struct constraint), 30);
3066 variable_info_pool = create_alloc_pool ("Variable info pool",
3067 sizeof (struct variable_info), 30);
3068 constraint_edge_pool = create_alloc_pool ("Constraint edges",
3069 sizeof (struct constraint_edge), 30);
3071 constraints = VEC_alloc (constraint_t, gc, 8);
3072 varmap = VEC_alloc (varinfo_t, gc, 8);
3073 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
3074 memset (&stats, 0, sizeof (stats));
3078 intra_create_variable_infos ();
3080 /* Now walk all statements and derive aliases. */
3083 block_stmt_iterator bsi;
3086 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3087 if (is_gimple_reg (PHI_RESULT (phi)))
3088 find_func_aliases (phi);
3090 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3091 find_func_aliases (bsi_stmt (bsi));
3094 build_constraint_graph ();
3098 fprintf (dump_file, "Constraints:\n");
3099 dump_constraints (dump_file);
3103 fprintf (dump_file, "Collapsing static cycles and doing variable substitution:\n");
3105 find_and_collapse_graph_cycles (graph, false);
3106 perform_var_substitution (graph);
3109 fprintf (dump_file, "Solving graph:\n");
3111 solve_graph (graph);
3114 dump_sa_points_to_info (dump_file);
3116 have_alias_info = true;
3119 struct tree_opt_pass pass_build_pta =
3123 create_alias_vars, /* execute */
3126 0, /* static_pass_number */
3127 TV_TREE_PTA, /* tv_id */
3128 PROP_cfg, /* properties_required */
3129 PROP_pta, /* properties_provided */
3130 0, /* properties_destroyed */
3131 0, /* todo_flags_start */
3132 0, /* todo_flags_finish */
3137 /* Delete created points-to sets. */
3140 delete_alias_vars (void)
3142 htab_delete (id_for_tree);
3143 free_alloc_pool (variable_info_pool);
3144 free_alloc_pool (constraint_pool);
3145 free_alloc_pool (constraint_edge_pool);
3146 bitmap_obstack_release (&ptabitmap_obstack);
3147 have_alias_info = false;
3150 struct tree_opt_pass pass_del_pta =
3154 delete_alias_vars, /* execute */
3157 0, /* static_pass_number */
3158 TV_TREE_PTA, /* tv_id */
3159 PROP_pta, /* properties_required */
3160 0, /* properties_provided */
3161 PROP_pta, /* properties_destroyed */
3162 0, /* todo_flags_start */
3163 0, /* todo_flags_finish */