1 /* Tree based points-to analysis
2 Copyright (C) 2005 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
43 #include "tree-gimple.h"
47 #include "tree-pass.h"
49 #include "alloc-pool.h"
50 #include "splay-tree.h"
51 #include "tree-ssa-structalias.h"
53 /* The idea behind this analyzer is to generate set constraints from the
54 program, then solve the resulting constraints in order to generate the
57 Set constraints are a way of modeling program analysis problems that
58 involve sets. They consist of an inclusion constraint language,
59 describing the variables (each variable is a set) and operations that
60 are involved on the variables, and a set of rules that derive facts
61 from these operations. To solve a system of set constraints, you derive
62 all possible facts under the rules, which gives you the correct sets
65 See "Efficient Field-sensitive pointer analysis for C" by "David
66 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
67 http://citeseer.ist.psu.edu/pearce04efficient.html
69 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
70 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
71 http://citeseer.ist.psu.edu/heintze01ultrafast.html
73 There are three types of constraint expressions, DEREF, ADDRESSOF, and
74 SCALAR. Each constraint expression consists of a constraint type,
75 a variable, and an offset.
77 SCALAR is a constraint expression type used to represent x, whether
78 it appears on the LHS or the RHS of a statement.
79 DEREF is a constraint expression type used to represent *x, whether
80 it appears on the LHS or the RHS of a statement.
81 ADDRESSOF is a constraint expression used to represent &x, whether
82 it appears on the LHS or the RHS of a statement.
84 Each pointer variable in the program is assigned an integer id, and
85 each field of a structure variable is assigned an integer id as well.
87 Structure variables are linked to their list of fields through a "next
88 field" in each variable that points to the next field in offset
90 Each variable for a structure field has
92 1. "size", that tells the size in bits of that field.
93 2. "fullsize, that tells the size in bits of the entire structure.
94 3. "offset", that tells the offset in bits from the beginning of the
95 structure to this field.
107 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
108 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
109 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
112 In order to solve the system of set constraints, the following is
115 1. Each constraint variable x has a solution set associated with it,
118 2. Constraints are separated into direct, copy, and complex.
119 Direct constraints are ADDRESSOF constraints that require no extra
120 processing, such as P = &Q
121 Copy constraints are those of the form P = Q.
122 Complex constraints are all the constraints involving dereferences.
124 3. All direct constraints of the form P = &Q are processed, such
125 that Q is added to Sol(P)
127 4. All complex constraints for a given constraint variable are stored in a
128 linked list attached to that variable's node.
130 5. A directed graph is built out of the copy constraints. Each
131 constraint variable is a node in the graph, and an edge from
132 Q to P is added for each copy constraint of the form P = Q
134 6. The graph is then walked, and solution sets are
135 propagated along the copy edges, such that an edge from Q to P
136 causes Sol(P) <- Sol(P) union Sol(Q).
138 7. As we visit each node, all complex constraints associated with
139 that node are processed by adding appropriate copy edges to the graph, or the
140 appropriate variables to the solution set.
142 8. The process of walking the graph is iterated until no solution
145 Prior to walking the graph in steps 6 and 7, We perform static
146 cycle elimination on the constraint graph, as well
147 as off-line variable substitution.
149 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
150 on and turned into anything), but isn't. You can just see what offset
151 inside the pointed-to struct it's going to access.
153 TODO: Constant bounded arrays can be handled as if they were structs of the
154 same number of elements.
156 TODO: Modeling heap and incoming pointers becomes much better if we
157 add fields to them as we discover them, which we could do.
159 TODO: We could handle unions, but to be honest, it's probably not
160 worth the pain or slowdown. */
162 static bool use_field_sensitive = true;
163 static unsigned int create_variable_info_for (tree, const char *);
164 static struct constraint_expr get_constraint_for (tree);
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 /* True if this is a heap variable. */
227 unsigned int is_heap_var:1;
229 /* Points-to set for this variable. */
232 /* Variable ids represented by this node. */
235 /* Vector of complex constraints for this node. Complex
236 constraints are those involving dereferences. */
237 VEC(constraint_t,gc) *complex;
239 typedef struct variable_info *varinfo_t;
241 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
243 /* Pool of variable info structures. */
244 static alloc_pool variable_info_pool;
246 DEF_VEC_P(varinfo_t);
248 DEF_VEC_ALLOC_P(varinfo_t, gc);
250 /* Table of variable info structures for constraint variables. Indexed directly
251 by variable info id. */
252 static VEC(varinfo_t,gc) *varmap;
253 #define get_varinfo(n) VEC_index(varinfo_t, varmap, n)
255 /* Variable that represents the unknown pointer. */
256 static varinfo_t var_anything;
257 static tree anything_tree;
258 static unsigned int anything_id;
260 /* Variable that represents the NULL pointer. */
261 static varinfo_t var_nothing;
262 static tree nothing_tree;
263 static unsigned int nothing_id;
265 /* Variable that represents read only memory. */
266 static varinfo_t var_readonly;
267 static tree readonly_tree;
268 static unsigned int readonly_id;
270 /* Variable that represents integers. This is used for when people do things
272 static varinfo_t var_integer;
273 static tree integer_tree;
274 static unsigned int integer_id;
276 /* Variable that represents arbitrary offsets into an object. Used to
277 represent pointer arithmetic, which may not legally escape the
278 bounds of an object. */
279 static varinfo_t var_anyoffset;
280 static tree anyoffset_tree;
281 static unsigned int anyoffset_id;
283 /* Return a new variable info structure consisting for a variable
284 named NAME, and using constraint graph node NODE. */
287 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
289 varinfo_t ret = pool_alloc (variable_info_pool);
295 ret->address_taken = false;
296 ret->indirect_target = false;
297 ret->is_artificial_var = false;
298 ret->is_heap_var = false;
299 ret->is_unknown_size_var = false;
300 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
301 bitmap_clear (ret->solution);
302 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
303 bitmap_clear (ret->variables);
309 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
311 /* An expression that appears in a constraint. */
313 struct constraint_expr
315 /* Constraint type. */
316 constraint_expr_type type;
318 /* Variable we are referring to in the constraint. */
321 /* Offset, in bits, of this constraint from the beginning of
322 variables it ends up referring to.
324 IOW, in a deref constraint, we would deref, get the result set,
325 then add OFFSET to each member. */
326 unsigned HOST_WIDE_INT offset;
329 static struct constraint_expr do_deref (struct constraint_expr);
331 /* Our set constraints are made up of two constraint expressions, one
334 As described in the introduction, our set constraints each represent an
335 operation between set valued variables.
339 struct constraint_expr lhs;
340 struct constraint_expr rhs;
343 /* List of constraints that we use to build the constraint graph from. */
345 static VEC(constraint_t,gc) *constraints;
346 static alloc_pool constraint_pool;
348 /* An edge in the constraint graph. We technically have no use for
349 the src, since it will always be the same node that we are indexing
350 into the pred/succ arrays with, but it's nice for checking
351 purposes. The edges are weighted, with a bit set in weights for
352 each edge from src to dest with that weight. */
354 struct constraint_edge
361 typedef struct constraint_edge *constraint_edge_t;
362 static alloc_pool constraint_edge_pool;
364 /* Return a new constraint edge from SRC to DEST. */
366 static constraint_edge_t
367 new_constraint_edge (unsigned int src, unsigned int dest)
369 constraint_edge_t ret = pool_alloc (constraint_edge_pool);
376 DEF_VEC_P(constraint_edge_t);
377 DEF_VEC_ALLOC_P(constraint_edge_t,gc);
380 /* The constraint graph is simply a set of adjacency vectors, one per
381 variable. succs[x] is the vector of successors for variable x, and preds[x]
382 is the vector of predecessors for variable x.
383 IOW, all edges are "forward" edges, which is not like our CFG.
385 preds[x]->src == x, and
388 struct constraint_graph
390 VEC(constraint_edge_t,gc) **succs;
391 VEC(constraint_edge_t,gc) **preds;
394 typedef struct constraint_graph *constraint_graph_t;
396 static constraint_graph_t graph;
398 /* Create a new constraint consisting of LHS and RHS expressions. */
401 new_constraint (const struct constraint_expr lhs,
402 const struct constraint_expr rhs)
404 constraint_t ret = pool_alloc (constraint_pool);
410 /* Print out constraint C to FILE. */
413 dump_constraint (FILE *file, constraint_t c)
415 if (c->lhs.type == ADDRESSOF)
417 else if (c->lhs.type == DEREF)
419 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
420 if (c->lhs.offset != 0)
421 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
422 fprintf (file, " = ");
423 if (c->rhs.type == ADDRESSOF)
425 else if (c->rhs.type == DEREF)
427 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
428 if (c->rhs.offset != 0)
429 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
430 fprintf (file, "\n");
433 /* Print out constraint C to stderr. */
436 debug_constraint (constraint_t c)
438 dump_constraint (stderr, c);
441 /* Print out all constraints to FILE */
444 dump_constraints (FILE *file)
448 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
449 dump_constraint (file, c);
452 /* Print out all constraints to stderr. */
455 debug_constraints (void)
457 dump_constraints (stderr);
462 The solver is a simple worklist solver, that works on the following
465 sbitmap changed_nodes = all ones;
466 changed_count = number of nodes;
467 For each node that was already collapsed:
471 while (changed_count > 0)
473 compute topological ordering for constraint graph
475 find and collapse cycles in the constraint graph (updating
476 changed if necessary)
478 for each node (n) in the graph in topological order:
481 Process each complex constraint associated with the node,
482 updating changed if necessary.
484 For each outgoing edge from n, propagate the solution from n to
485 the destination of the edge, updating changed as necessary.
489 /* Return true if two constraint expressions A and B are equal. */
492 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
494 return a.type == b.type
496 && a.offset == b.offset;
499 /* Return true if constraint expression A is less than constraint expression
500 B. This is just arbitrary, but consistent, in order to give them an
504 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
506 if (a.type == b.type)
509 return a.offset < b.offset;
511 return a.var < b.var;
514 return a.type < b.type;
517 /* Return true if constraint A is less than constraint B. This is just
518 arbitrary, but consistent, in order to give them an ordering. */
521 constraint_less (const constraint_t a, const constraint_t b)
523 if (constraint_expr_less (a->lhs, b->lhs))
525 else if (constraint_expr_less (b->lhs, a->lhs))
528 return constraint_expr_less (a->rhs, b->rhs);
531 /* Return true if two constraints A and B are equal. */
534 constraint_equal (struct constraint a, struct constraint b)
536 return constraint_expr_equal (a.lhs, b.lhs)
537 && constraint_expr_equal (a.rhs, b.rhs);
541 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
544 constraint_vec_find (VEC(constraint_t,gc) *vec,
545 struct constraint lookfor)
553 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
554 if (place >= VEC_length (constraint_t, vec))
556 found = VEC_index (constraint_t, vec, place);
557 if (!constraint_equal (*found, lookfor))
562 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
565 constraint_set_union (VEC(constraint_t,gc) **to,
566 VEC(constraint_t,gc) **from)
571 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
573 if (constraint_vec_find (*to, *c) == NULL)
575 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
577 VEC_safe_insert (constraint_t, gc, *to, place, c);
582 /* Take a solution set SET, add OFFSET to each member of the set, and
583 overwrite SET with the result when done. */
586 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
588 bitmap result = BITMAP_ALLOC (&iteration_obstack);
592 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
594 /* If this is a properly sized variable, only add offset if it's
595 less than end. Otherwise, it is globbed to a single
598 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
600 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
601 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
602 bitmap_set_bit (result, v->id);
604 else if (get_varinfo (i)->is_artificial_var
605 || get_varinfo (i)->is_unknown_size_var)
607 bitmap_set_bit (result, i);
611 bitmap_copy (set, result);
612 BITMAP_FREE (result);
615 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
619 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
622 return bitmap_ior_into (to, from);
628 tmp = BITMAP_ALLOC (&iteration_obstack);
629 bitmap_copy (tmp, from);
630 solution_set_add (tmp, inc);
631 res = bitmap_ior_into (to, tmp);
637 /* Insert constraint C into the list of complex constraints for VAR. */
640 insert_into_complex (unsigned int var, constraint_t c)
642 varinfo_t vi = get_varinfo (var);
643 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
645 VEC_safe_insert (constraint_t, gc, vi->complex, place, c);
649 /* Compare two constraint edges A and B, return true if they are equal. */
652 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
654 return a.src == b.src && a.dest == b.dest;
657 /* Compare two constraint edges, return true if A is less than B */
660 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
662 if (a->dest < b->dest)
664 else if (a->dest == b->dest)
665 return a->src < b->src;
670 /* Find the constraint edge that matches LOOKFOR, in VEC.
671 Return the edge, if found, NULL otherwise. */
673 static constraint_edge_t
674 constraint_edge_vec_find (VEC(constraint_edge_t,gc) *vec,
675 struct constraint_edge lookfor)
678 constraint_edge_t edge;
680 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
681 constraint_edge_less);
682 edge = VEC_index (constraint_edge_t, vec, place);
683 if (!constraint_edge_equal (*edge, lookfor))
688 /* Condense two variable nodes into a single variable node, by moving
689 all associated info from SRC to TO. */
692 condense_varmap_nodes (unsigned int to, unsigned int src)
694 varinfo_t tovi = get_varinfo (to);
695 varinfo_t srcvi = get_varinfo (src);
700 /* the src node, and all its variables, are now the to node. */
702 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
703 get_varinfo (i)->node = to;
705 /* Merge the src node variables and the to node variables. */
706 bitmap_set_bit (tovi->variables, src);
707 bitmap_ior_into (tovi->variables, srcvi->variables);
708 bitmap_clear (srcvi->variables);
710 /* Move all complex constraints from src node into to node */
711 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
713 /* In complex constraints for node src, we may have either
714 a = *src, and *src = a. */
716 if (c->rhs.type == DEREF)
721 constraint_set_union (&tovi->complex, &srcvi->complex);
722 srcvi->complex = NULL;
725 /* Erase EDGE from GRAPH. This routine only handles self-edges
726 (e.g. an edge from a to a). */
729 erase_graph_self_edge (constraint_graph_t graph, struct constraint_edge edge)
731 VEC(constraint_edge_t,gc) *predvec = graph->preds[edge.src];
732 VEC(constraint_edge_t,gc) *succvec = graph->succs[edge.dest];
734 gcc_assert (edge.src == edge.dest);
736 /* Remove from the successors. */
737 place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
738 constraint_edge_less);
740 /* Make sure we found the edge. */
741 #ifdef ENABLE_CHECKING
743 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
744 gcc_assert (constraint_edge_equal (*tmp, edge));
747 VEC_ordered_remove (constraint_edge_t, succvec, place);
749 /* Remove from the predecessors. */
750 place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
751 constraint_edge_less);
753 /* Make sure we found the edge. */
754 #ifdef ENABLE_CHECKING
756 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
757 gcc_assert (constraint_edge_equal (*tmp, edge));
760 VEC_ordered_remove (constraint_edge_t, predvec, place);
763 /* Remove edges involving NODE from GRAPH. */
766 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
768 VEC(constraint_edge_t,gc) *succvec = graph->succs[node];
769 VEC(constraint_edge_t,gc) *predvec = graph->preds[node];
773 /* Walk the successors, erase the associated preds. */
774 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
778 struct constraint_edge lookfor;
779 lookfor.src = c->dest;
781 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
782 &lookfor, constraint_edge_less);
783 VEC_ordered_remove (constraint_edge_t, graph->preds[c->dest], place);
785 /* Walk the preds, erase the associated succs. */
786 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
790 struct constraint_edge lookfor;
791 lookfor.src = c->dest;
793 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
794 &lookfor, constraint_edge_less);
795 VEC_ordered_remove (constraint_edge_t, graph->succs[c->dest], place);
798 graph->preds[node] = NULL;
799 graph->succs[node] = NULL;
802 static bool edge_added = false;
804 /* Add edge NEWE to the graph. */
807 add_graph_edge (constraint_graph_t graph, struct constraint_edge newe)
810 unsigned int src = newe.src;
811 unsigned int dest = newe.dest;
812 VEC(constraint_edge_t,gc) *vec;
814 vec = graph->preds[src];
815 place = VEC_lower_bound (constraint_edge_t, vec, &newe,
816 constraint_edge_less);
817 if (place == VEC_length (constraint_edge_t, vec)
818 || VEC_index (constraint_edge_t, vec, place)->dest != dest)
820 constraint_edge_t edge = new_constraint_edge (src, dest);
823 weightbitmap = BITMAP_ALLOC (&ptabitmap_obstack);
824 edge->weights = weightbitmap;
825 VEC_safe_insert (constraint_edge_t, gc, graph->preds[edge->src],
827 edge = new_constraint_edge (dest, src);
828 edge->weights = weightbitmap;
829 place = VEC_lower_bound (constraint_edge_t, graph->succs[edge->src],
830 edge, constraint_edge_less);
831 VEC_safe_insert (constraint_edge_t, gc, graph->succs[edge->src],
841 /* Return the bitmap representing the weights of edge LOOKFOR */
844 get_graph_weights (constraint_graph_t graph, struct constraint_edge lookfor)
846 constraint_edge_t edge;
847 unsigned int src = lookfor.src;
848 VEC(constraint_edge_t,gc) *vec;
849 vec = graph->preds[src];
850 edge = constraint_edge_vec_find (vec, lookfor);
851 gcc_assert (edge != NULL);
852 return edge->weights;
856 /* Merge GRAPH nodes FROM and TO into node TO. */
859 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
862 VEC(constraint_edge_t,gc) *succvec = graph->succs[from];
863 VEC(constraint_edge_t,gc) *predvec = graph->preds[from];
867 /* Merge all the predecessor edges. */
869 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
871 unsigned int d = c->dest;
872 struct constraint_edge olde;
873 struct constraint_edge newe;
880 add_graph_edge (graph, newe);
883 temp = get_graph_weights (graph, olde);
884 weights = get_graph_weights (graph, newe);
885 bitmap_ior_into (weights, temp);
888 /* Merge all the successor edges. */
889 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
891 unsigned int d = c->dest;
892 struct constraint_edge olde;
893 struct constraint_edge newe;
900 add_graph_edge (graph, newe);
903 temp = get_graph_weights (graph, olde);
904 weights = get_graph_weights (graph, newe);
905 bitmap_ior_into (weights, temp);
907 clear_edges_for_node (graph, from);
910 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
911 it doesn't exist in the graph already.
912 Return false if the edge already existed, true otherwise. */
915 int_add_graph_edge (constraint_graph_t graph, unsigned int to,
916 unsigned int from, unsigned HOST_WIDE_INT weight)
918 if (to == from && weight == 0)
925 struct constraint_edge edge;
928 r = add_graph_edge (graph, edge);
929 r |= !bitmap_bit_p (get_graph_weights (graph, edge), weight);
930 bitmap_set_bit (get_graph_weights (graph, edge), weight);
936 /* Return true if LOOKFOR is an existing graph edge. */
939 valid_graph_edge (constraint_graph_t graph, struct constraint_edge lookfor)
941 return constraint_edge_vec_find (graph->preds[lookfor.src], lookfor) != NULL;
945 /* Build the constraint graph. */
948 build_constraint_graph (void)
953 graph = ggc_alloc (sizeof (struct constraint_graph));
954 graph->succs = ggc_alloc_cleared (VEC_length (varinfo_t, varmap)
955 * sizeof (*graph->succs));
956 graph->preds = ggc_alloc_cleared (VEC_length (varinfo_t, varmap)
957 * sizeof (*graph->preds));
959 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
961 struct constraint_expr lhs = c->lhs;
962 struct constraint_expr rhs = c->rhs;
963 if (lhs.type == DEREF)
965 /* *x = y or *x = &y (complex) */
966 if (rhs.type == ADDRESSOF || rhs.var > anything_id)
967 insert_into_complex (lhs.var, c);
969 else if (rhs.type == DEREF)
972 if (lhs.var > anything_id)
973 insert_into_complex (rhs.var, c);
975 else if (rhs.type == ADDRESSOF)
978 bitmap_set_bit (get_varinfo (lhs.var)->solution, rhs.var);
980 else if (rhs.var > anything_id && lhs.var > anything_id)
982 /* Ignore 0 weighted self edges, as they can't possibly contribute
984 if (lhs.var != rhs.var || rhs.offset != 0 || lhs.offset != 0)
987 struct constraint_edge edge;
991 add_graph_edge (graph, edge);
992 bitmap_set_bit (get_graph_weights (graph, edge),
1001 /* Changed variables on the last iteration. */
1002 static unsigned int changed_count;
1003 static sbitmap changed;
1005 DEF_VEC_I(unsigned);
1006 DEF_VEC_ALLOC_I(unsigned,heap);
1009 /* Strongly Connected Component visitation info. */
1014 sbitmap in_component;
1016 unsigned int *visited_index;
1017 VEC(unsigned,heap) *scc_stack;
1018 VEC(unsigned,heap) *unification_queue;
1022 /* Recursive routine to find strongly connected components in GRAPH.
1023 SI is the SCC info to store the information in, and N is the id of current
1024 graph node we are processing.
1026 This is Tarjan's strongly connected component finding algorithm, as
1027 modified by Nuutila to keep only non-root nodes on the stack.
1028 The algorithm can be found in "On finding the strongly connected
1029 connected components in a directed graph" by Esko Nuutila and Eljas
1030 Soisalon-Soininen, in Information Processing Letters volume 49,
1031 number 1, pages 9-14. */
1034 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1036 constraint_edge_t c;
1039 gcc_assert (get_varinfo (n)->node == n);
1040 SET_BIT (si->visited, n);
1041 RESET_BIT (si->in_component, n);
1042 si->visited_index[n] = si->current_index ++;
1044 /* Visit all the successors. */
1045 for (i = 0; VEC_iterate (constraint_edge_t, graph->succs[n], i, c); i++)
1047 /* We only want to find and collapse the zero weight edges. */
1048 if (bitmap_bit_p (c->weights, 0))
1050 unsigned int w = c->dest;
1051 if (!TEST_BIT (si->visited, w))
1052 scc_visit (graph, si, w);
1053 if (!TEST_BIT (si->in_component, w))
1055 unsigned int t = get_varinfo (w)->node;
1056 unsigned int nnode = get_varinfo (n)->node;
1057 if (si->visited_index[t] < si->visited_index[nnode])
1058 get_varinfo (n)->node = t;
1063 /* See if any components have been identified. */
1064 if (get_varinfo (n)->node == n)
1066 unsigned int t = si->visited_index[n];
1067 SET_BIT (si->in_component, n);
1068 while (VEC_length (unsigned, si->scc_stack) != 0
1069 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1071 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1072 get_varinfo (w)->node = n;
1073 SET_BIT (si->in_component, w);
1074 /* Mark this node for collapsing. */
1075 VEC_safe_push (unsigned, heap, si->unification_queue, w);
1079 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1083 /* Collapse two variables into one variable. */
1086 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1088 bitmap tosol, fromsol;
1089 struct constraint_edge edge;
1092 condense_varmap_nodes (to, from);
1093 tosol = get_varinfo (to)->solution;
1094 fromsol = get_varinfo (from)->solution;
1095 bitmap_ior_into (tosol, fromsol);
1096 merge_graph_nodes (graph, to, from);
1099 if (valid_graph_edge (graph, edge))
1101 bitmap weights = get_graph_weights (graph, edge);
1102 bitmap_clear_bit (weights, 0);
1103 if (bitmap_empty_p (weights))
1104 erase_graph_self_edge (graph, edge);
1106 bitmap_clear (fromsol);
1107 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1108 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1112 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1113 SI is the Strongly Connected Components information structure that tells us
1114 what components to unify.
1115 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1116 count should be updated to reflect the unification. */
1119 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1120 bool update_changed)
1123 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1126 /* We proceed as follows:
1128 For each component in the queue (components are delineated by
1129 when current_queue_element->node != next_queue_element->node):
1131 rep = representative node for component
1133 For each node (tounify) to be unified in the component,
1134 merge the solution for tounify into tmp bitmap
1136 clear solution for tounify
1138 merge edges from tounify into rep
1140 merge complex constraints from tounify into rep
1142 update changed count to note that tounify will never change
1145 Merge tmp into solution for rep, marking rep changed if this
1146 changed rep's solution.
1148 Delete any 0 weighted self-edges we now have for rep. */
1149 while (i != VEC_length (unsigned, si->unification_queue))
1151 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1152 unsigned int n = get_varinfo (tounify)->node;
1154 if (dump_file && (dump_flags & TDF_DETAILS))
1155 fprintf (dump_file, "Unifying %s to %s\n",
1156 get_varinfo (tounify)->name,
1157 get_varinfo (n)->name);
1159 stats.unified_vars_dynamic++;
1161 stats.unified_vars_static++;
1162 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1163 merge_graph_nodes (graph, n, tounify);
1164 condense_varmap_nodes (n, tounify);
1166 if (update_changed && TEST_BIT (changed, tounify))
1168 RESET_BIT (changed, tounify);
1169 if (!TEST_BIT (changed, n))
1170 SET_BIT (changed, n);
1173 gcc_assert (changed_count > 0);
1178 bitmap_clear (get_varinfo (tounify)->solution);
1181 /* If we've either finished processing the entire queue, or
1182 finished processing all nodes for component n, update the solution for
1184 if (i == VEC_length (unsigned, si->unification_queue)
1185 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1187 struct constraint_edge edge;
1189 /* If the solution changes because of the merging, we need to mark
1190 the variable as changed. */
1191 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1193 if (update_changed && !TEST_BIT (changed, n))
1195 SET_BIT (changed, n);
1202 if (valid_graph_edge (graph, edge))
1204 bitmap weights = get_graph_weights (graph, edge);
1205 bitmap_clear_bit (weights, 0);
1206 if (bitmap_empty_p (weights))
1207 erase_graph_self_edge (graph, edge);
1215 /* Information needed to compute the topological ordering of a graph. */
1219 /* sbitmap of visited nodes. */
1221 /* Array that stores the topological order of the graph, *in
1223 VEC(unsigned,heap) *topo_order;
1227 /* Initialize and return a topological info structure. */
1229 static struct topo_info *
1230 init_topo_info (void)
1232 size_t size = VEC_length (varinfo_t, varmap);
1233 struct topo_info *ti = xmalloc (sizeof (struct topo_info));
1234 ti->visited = sbitmap_alloc (size);
1235 sbitmap_zero (ti->visited);
1236 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1241 /* Free the topological sort info pointed to by TI. */
1244 free_topo_info (struct topo_info *ti)
1246 sbitmap_free (ti->visited);
1247 VEC_free (unsigned, heap, ti->topo_order);
1251 /* Visit the graph in topological order, and store the order in the
1252 topo_info structure. */
1255 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1258 VEC(constraint_edge_t,gc) *succs = graph->succs[n];
1259 constraint_edge_t c;
1261 SET_BIT (ti->visited, n);
1262 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1264 if (!TEST_BIT (ti->visited, c->dest))
1265 topo_visit (graph, ti, c->dest);
1267 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1270 /* Return true if variable N + OFFSET is a legal field of N. */
1273 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1275 varinfo_t ninfo = get_varinfo (n);
1277 /* For things we've globbed to single variables, any offset into the
1278 variable acts like the entire variable, so that it becomes offset
1280 if (n == anything_id
1281 || ninfo->is_artificial_var
1282 || ninfo->is_unknown_size_var)
1287 return n > anything_id
1288 && (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1291 /* Process a constraint C that represents *x = &y. */
1294 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1295 constraint_t c, bitmap delta)
1297 unsigned int rhs = c->rhs.var;
1298 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1302 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1303 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1305 if (type_safe (j, &offset))
1307 /* *x != NULL && *x != ANYTHING*/
1311 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1312 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1314 sol = get_varinfo (t)->solution;
1315 if (!bitmap_bit_p (sol, rhs))
1317 bitmap_set_bit (sol, rhs);
1318 if (!TEST_BIT (changed, t))
1320 SET_BIT (changed, t);
1326 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1331 /* Process a constraint C that represents x = *y, using DELTA as the
1332 starting solution. */
1335 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1338 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1339 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1341 bitmap sol = get_varinfo (lhs)->solution;
1345 /* For each variable j in delta (Sol(y)), add
1346 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1347 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1349 if (type_safe (j, &roffset))
1352 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1355 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1357 if (int_add_graph_edge (graph, lhs, t, 0))
1358 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1361 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1365 /* If the LHS solution changed, mark the var as changed. */
1368 get_varinfo (lhs)->solution = sol;
1369 if (!TEST_BIT (changed, lhs))
1371 SET_BIT (changed, lhs);
1377 /* Process a constraint C that represents *x = y. */
1380 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1382 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1383 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1384 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1385 bitmap sol = get_varinfo (rhs)->solution;
1389 /* For each member j of delta (Sol(x)), add an edge from y to j and
1390 union Sol(y) into Sol(j) */
1391 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1393 if (type_safe (j, &loff))
1397 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1399 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1401 if (int_add_graph_edge (graph, t, rhs, roff))
1403 bitmap tmp = get_varinfo (t)->solution;
1404 if (set_union_with_increment (tmp, sol, roff))
1406 get_varinfo (t)->solution = tmp;
1409 sol = get_varinfo (rhs)->solution;
1411 if (!TEST_BIT (changed, t))
1413 SET_BIT (changed, t);
1420 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1424 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1425 constraint (IE *x = &y, x = *y, and *x = y). */
1428 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1430 if (c->lhs.type == DEREF)
1432 if (c->rhs.type == ADDRESSOF)
1435 do_da_constraint (graph, c, delta);
1440 do_ds_constraint (graph, c, delta);
1446 do_sd_constraint (graph, c, delta);
1450 /* Initialize and return a new SCC info structure. */
1452 static struct scc_info *
1453 init_scc_info (void)
1455 struct scc_info *si = xmalloc (sizeof (struct scc_info));
1456 size_t size = VEC_length (varinfo_t, varmap);
1458 si->current_index = 0;
1459 si->visited = sbitmap_alloc (size);
1460 sbitmap_zero (si->visited);
1461 si->in_component = sbitmap_alloc (size);
1462 sbitmap_ones (si->in_component);
1463 si->visited_index = xcalloc (sizeof (unsigned int), size + 1);
1464 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1465 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1469 /* Free an SCC info structure pointed to by SI */
1472 free_scc_info (struct scc_info *si)
1474 sbitmap_free (si->visited);
1475 sbitmap_free (si->in_component);
1476 free (si->visited_index);
1477 VEC_free (unsigned, heap, si->scc_stack);
1478 VEC_free (unsigned, heap, si->unification_queue);
1483 /* Find cycles in GRAPH that occur, using strongly connected components, and
1484 collapse the cycles into a single representative node. if UPDATE_CHANGED
1485 is true, then update the changed sbitmap to note those nodes whose
1486 solutions have changed as a result of collapsing. */
1489 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1492 unsigned int size = VEC_length (varinfo_t, varmap);
1493 struct scc_info *si = init_scc_info ();
1495 for (i = 0; i != size; ++i)
1496 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1497 scc_visit (graph, si, i);
1498 process_unification_queue (graph, si, update_changed);
1502 /* Compute a topological ordering for GRAPH, and store the result in the
1503 topo_info structure TI. */
1506 compute_topo_order (constraint_graph_t graph,
1507 struct topo_info *ti)
1510 unsigned int size = VEC_length (varinfo_t, varmap);
1512 for (i = 0; i != size; ++i)
1513 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1514 topo_visit (graph, ti, i);
1517 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1520 bitmap_other_than_zero_bit_set (bitmap b)
1525 if (bitmap_empty_p (b))
1527 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1532 /* Perform offline variable substitution.
1534 This is a linear time way of identifying variables that must have
1535 equivalent points-to sets, including those caused by static cycles,
1536 and single entry subgraphs, in the constraint graph.
1538 The technique is described in "Off-line variable substitution for
1539 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1540 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1543 perform_var_substitution (constraint_graph_t graph)
1545 struct topo_info *ti = init_topo_info ();
1547 /* Compute the topological ordering of the graph, then visit each
1548 node in topological order. */
1549 compute_topo_order (graph, ti);
1551 while (VEC_length (unsigned, ti->topo_order) != 0)
1553 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1555 varinfo_t vi = get_varinfo (i);
1556 bool okay_to_elim = false;
1557 unsigned int root = VEC_length (varinfo_t, varmap);
1558 VEC(constraint_edge_t,gc) *predvec = graph->preds[i];
1559 constraint_edge_t ce;
1562 /* We can't eliminate things whose address is taken, or which is
1563 the target of a dereference. */
1564 if (vi->address_taken || vi->indirect_target)
1567 /* See if all predecessors of I are ripe for elimination */
1568 for (pred = 0; VEC_iterate (constraint_edge_t, predvec, pred, ce); pred++)
1572 weight = get_graph_weights (graph, *ce);
1574 /* We can't eliminate variables that have non-zero weighted
1575 edges between them. */
1576 if (bitmap_other_than_zero_bit_set (weight))
1578 okay_to_elim = false;
1581 w = get_varinfo (ce->dest)->node;
1583 /* We can't eliminate the node if one of the predecessors is
1584 part of a different strongly connected component. */
1588 okay_to_elim = true;
1592 okay_to_elim = false;
1596 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1597 then Solution(i) is a subset of Solution (w), where w is a
1598 predecessor in the graph.
1599 Corollary: If all predecessors of i have the same
1600 points-to set, then i has that same points-to set as
1601 those predecessors. */
1602 tmp = BITMAP_ALLOC (NULL);
1603 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1604 get_varinfo (w)->solution);
1605 if (!bitmap_empty_p (tmp))
1607 okay_to_elim = false;
1614 /* See if the root is different than the original node.
1615 If so, we've found an equivalence. */
1616 if (root != get_varinfo (i)->node && okay_to_elim)
1618 /* Found an equivalence */
1619 get_varinfo (i)->node = root;
1620 collapse_nodes (graph, root, i);
1621 if (dump_file && (dump_flags & TDF_DETAILS))
1622 fprintf (dump_file, "Collapsing %s into %s\n",
1623 get_varinfo (i)->name,
1624 get_varinfo (root)->name);
1625 stats.collapsed_vars++;
1629 free_topo_info (ti);
1633 /* Solve the constraint graph GRAPH using our worklist solver.
1634 This is based on the PW* family of solvers from the "Efficient Field
1635 Sensitive Pointer Analysis for C" paper.
1636 It works by iterating over all the graph nodes, processing the complex
1637 constraints and propagating the copy constraints, until everything stops
1638 changed. This corresponds to steps 6-8 in the solving list given above. */
1641 solve_graph (constraint_graph_t graph)
1643 unsigned int size = VEC_length (varinfo_t, varmap);
1646 changed_count = size;
1647 changed = sbitmap_alloc (size);
1648 sbitmap_ones (changed);
1650 /* The already collapsed/unreachable nodes will never change, so we
1651 need to account for them in changed_count. */
1652 for (i = 0; i < size; i++)
1653 if (get_varinfo (i)->node != i)
1656 while (changed_count > 0)
1659 struct topo_info *ti = init_topo_info ();
1662 bitmap_obstack_initialize (&iteration_obstack);
1666 /* We already did cycle elimination once, when we did
1667 variable substitution, so we don't need it again for the
1669 if (stats.iterations > 1)
1670 find_and_collapse_graph_cycles (graph, true);
1675 compute_topo_order (graph, ti);
1677 while (VEC_length (unsigned, ti->topo_order) != 0)
1679 i = VEC_pop (unsigned, ti->topo_order);
1680 gcc_assert (get_varinfo (i)->node == i);
1682 /* If the node has changed, we need to process the
1683 complex constraints and outgoing edges again. */
1684 if (TEST_BIT (changed, i))
1688 constraint_edge_t e;
1690 VEC(constraint_t,gc) *complex = get_varinfo (i)->complex;
1691 VEC(constraint_edge_t,gc) *succs;
1693 RESET_BIT (changed, i);
1696 /* Process the complex constraints */
1697 solution = get_varinfo (i)->solution;
1698 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
1699 do_complex_constraint (graph, c, solution);
1701 /* Propagate solution to all successors. */
1702 succs = graph->succs[i];
1703 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
1705 bitmap tmp = get_varinfo (e->dest)->solution;
1708 bitmap weights = e->weights;
1711 gcc_assert (!bitmap_empty_p (weights));
1712 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
1713 flag |= set_union_with_increment (tmp, solution, k);
1717 get_varinfo (e->dest)->solution = tmp;
1718 if (!TEST_BIT (changed, e->dest))
1720 SET_BIT (changed, e->dest);
1727 free_topo_info (ti);
1728 bitmap_obstack_release (&iteration_obstack);
1731 sbitmap_free (changed);
1735 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1737 /* Map from trees to variable ids. */
1738 static htab_t id_for_tree;
1740 typedef struct tree_id
1746 /* Hash a tree id structure. */
1749 tree_id_hash (const void *p)
1751 const tree_id_t ta = (tree_id_t) p;
1752 return htab_hash_pointer (ta->t);
1755 /* Return true if the tree in P1 and the tree in P2 are the same. */
1758 tree_id_eq (const void *p1, const void *p2)
1760 const tree_id_t ta1 = (tree_id_t) p1;
1761 const tree_id_t ta2 = (tree_id_t) p2;
1762 return ta1->t == ta2->t;
1765 /* Insert ID as the variable id for tree T in the hashtable. */
1768 insert_id_for_tree (tree t, int id)
1771 struct tree_id finder;
1775 slot = htab_find_slot (id_for_tree, &finder, INSERT);
1776 gcc_assert (*slot == NULL);
1777 new_pair = xmalloc (sizeof (struct tree_id));
1780 *slot = (void *)new_pair;
1783 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1784 exist in the hash table, return false, otherwise, return true and
1785 set *ID to the id we found. */
1788 lookup_id_for_tree (tree t, unsigned int *id)
1791 struct tree_id finder;
1794 pair = htab_find (id_for_tree, &finder);
1801 /* Return a printable name for DECL */
1804 alias_get_name (tree decl)
1806 const char *res = get_name (decl);
1808 int num_printed = 0;
1814 if (TREE_CODE (decl) == SSA_NAME)
1816 num_printed = asprintf (&temp, "%s_%u",
1817 alias_get_name (SSA_NAME_VAR (decl)),
1818 SSA_NAME_VERSION (decl));
1820 else if (DECL_P (decl))
1822 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
1824 if (num_printed > 0)
1826 res = ggc_strdup (temp);
1832 /* Find the variable id for tree T in the hashtable.
1833 If T doesn't exist in the hash table, create an entry for it. */
1836 get_id_for_tree (tree t)
1839 struct tree_id finder;
1842 pair = htab_find (id_for_tree, &finder);
1844 return create_variable_info_for (t, alias_get_name (t));
1849 /* Get a constraint expression from an SSA_VAR_P node. */
1851 static struct constraint_expr
1852 get_constraint_exp_from_ssa_var (tree t)
1854 struct constraint_expr cexpr;
1856 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
1858 /* For parameters, get at the points-to set for the actual parm
1860 if (TREE_CODE (t) == SSA_NAME
1861 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
1862 && default_def (SSA_NAME_VAR (t)) == t)
1863 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
1865 cexpr.type = SCALAR;
1867 cexpr.var = get_id_for_tree (t);
1868 /* If we determine the result is "anything", and we know this is readonly,
1869 say it points to readonly memory instead. */
1870 if (cexpr.var == anything_id && TREE_READONLY (t))
1872 cexpr.type = ADDRESSOF;
1873 cexpr.var = readonly_id;
1880 /* Process a completed constraint T, and add it to the constraint
1884 process_constraint (constraint_t t)
1886 struct constraint_expr rhs = t->rhs;
1887 struct constraint_expr lhs = t->lhs;
1889 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
1890 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
1892 /* ANYTHING == ANYTHING is pointless. */
1893 if (lhs.var == anything_id && rhs.var == anything_id)
1896 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1897 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
1902 process_constraint (t);
1904 /* This can happen in our IR with things like n->a = *p */
1905 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
1907 /* Split into tmp = *rhs, *lhs = tmp */
1908 tree rhsdecl = get_varinfo (rhs.var)->decl;
1909 tree pointertype = TREE_TYPE (rhsdecl);
1910 tree pointedtotype = TREE_TYPE (pointertype);
1911 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
1912 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
1914 /* If this is an aggregate of known size, we should have passed
1915 this off to do_structure_copy, and it should have broken it
1917 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
1918 || get_varinfo (rhs.var)->is_unknown_size_var);
1920 process_constraint (new_constraint (tmplhs, rhs));
1921 process_constraint (new_constraint (lhs, tmplhs));
1923 else if (rhs.type == ADDRESSOF)
1926 gcc_assert (rhs.offset == 0);
1928 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
1929 vi->address_taken = true;
1931 VEC_safe_push (constraint_t, gc, constraints, t);
1935 if (lhs.type != DEREF && rhs.type == DEREF)
1936 get_varinfo (lhs.var)->indirect_target = true;
1937 VEC_safe_push (constraint_t, gc, constraints, t);
1942 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1945 static unsigned HOST_WIDE_INT
1946 bitpos_of_field (const tree fdecl)
1949 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
1950 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
1953 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
1954 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
1958 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1959 overlaps with a field at [FIELDPOS, FIELDSIZE] */
1962 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
1963 const unsigned HOST_WIDE_INT fieldsize,
1964 const unsigned HOST_WIDE_INT accesspos,
1965 const unsigned HOST_WIDE_INT accesssize)
1967 if (fieldpos == accesspos && fieldsize == accesssize)
1969 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
1971 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
1977 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1979 static struct constraint_expr
1980 get_constraint_for_component_ref (tree t)
1982 struct constraint_expr result;
1983 HOST_WIDE_INT bitsize;
1984 HOST_WIDE_INT bitpos;
1986 enum machine_mode mode;
1992 result.type = SCALAR;
1995 /* Some people like to do cute things like take the address of
1998 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
1999 forzero = TREE_OPERAND (forzero, 0);
2001 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2004 result.var = integer_id;
2005 result.type = SCALAR;
2009 t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode,
2010 &unsignedp, &volatilep, false);
2011 result = get_constraint_for (t);
2013 /* This can also happen due to weird offsetof type macros. */
2014 if (TREE_CODE (t) != ADDR_EXPR && result.type == ADDRESSOF)
2015 result.type = SCALAR;
2017 /* If we know where this goes, then yay. Otherwise, booo. */
2019 if (offset == NULL && bitsize != -1)
2021 result.offset = bitpos;
2025 result.var = anything_id;
2029 if (result.type == SCALAR)
2031 /* In languages like C, you can access one past the end of an
2032 array. You aren't allowed to dereference it, so we can
2033 ignore this constraint. When we handle pointer subtraction,
2034 we may have to do something cute here. */
2036 if (result.offset < get_varinfo (result.var)->fullsize)
2038 /* It's also not true that the constraint will actually start at the
2039 right offset, it may start in some padding. We only care about
2040 setting the constraint to the first actual field it touches, so
2043 for (curr = get_varinfo (result.var); curr; curr = curr->next)
2045 if (offset_overlaps_with_access (curr->offset, curr->size,
2046 result.offset, bitsize))
2048 result.var = curr->id;
2053 /* assert that we found *some* field there. The user couldn't be
2054 accessing *only* padding. */
2059 if (dump_file && (dump_flags & TDF_DETAILS))
2060 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2069 /* Dereference the constraint expression CONS, and return the result.
2070 DEREF (ADDRESSOF) = SCALAR
2071 DEREF (SCALAR) = DEREF
2072 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2073 This is needed so that we can handle dereferencing DEREF constraints. */
2075 static struct constraint_expr
2076 do_deref (struct constraint_expr cons)
2078 if (cons.type == SCALAR)
2083 else if (cons.type == ADDRESSOF)
2088 else if (cons.type == DEREF)
2090 tree tmpvar = create_tmp_var_raw (ptr_type_node, "derefmp");
2091 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2092 process_constraint (new_constraint (tmplhs, cons));
2093 cons.var = tmplhs.var;
2100 /* Given a tree T, return the constraint expression for it. */
2102 static struct constraint_expr
2103 get_constraint_for (tree t)
2105 struct constraint_expr temp;
2107 /* x = integer is all glommed to a single variable, which doesn't
2108 point to anything by itself. That is, of course, unless it is an
2109 integer constant being treated as a pointer, in which case, we
2110 will return that this is really the addressof anything. This
2111 happens below, since it will fall into the default case. The only
2112 case we know something about an integer treated like a pointer is
2113 when it is the NULL pointer, and then we just say it points to
2115 if (TREE_CODE (t) == INTEGER_CST
2116 && !POINTER_TYPE_P (TREE_TYPE (t)))
2118 temp.var = integer_id;
2123 else if (TREE_CODE (t) == INTEGER_CST
2124 && integer_zerop (t))
2126 temp.var = nothing_id;
2127 temp.type = ADDRESSOF;
2132 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2134 case tcc_expression:
2136 switch (TREE_CODE (t))
2140 temp = get_constraint_for (TREE_OPERAND (t, 0));
2141 if (temp.type == DEREF)
2144 temp.type = ADDRESSOF;
2150 /* XXX: In interprocedural mode, if we didn't have the
2151 body, we would need to do *each pointer argument =
2153 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2158 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2159 DECL_EXTERNAL (heapvar) = 1;
2160 add_referenced_tmp_var (heapvar);
2161 temp.var = create_variable_info_for (heapvar,
2162 alias_get_name (heapvar));
2164 vi = get_varinfo (temp.var);
2165 vi->is_artificial_var = 1;
2166 vi->is_heap_var = 1;
2167 temp.type = ADDRESSOF;
2174 temp.type = ADDRESSOF;
2175 temp.var = anything_id;
2183 switch (TREE_CODE (t))
2187 temp = get_constraint_for (TREE_OPERAND (t, 0));
2188 temp = do_deref (temp);
2193 temp = get_constraint_for_component_ref (t);
2197 temp.type = ADDRESSOF;
2198 temp.var = anything_id;
2206 switch (TREE_CODE (t))
2210 case NON_LVALUE_EXPR:
2212 tree op = TREE_OPERAND (t, 0);
2214 /* Cast from non-pointer to pointers are bad news for us.
2215 Anything else, we see through */
2216 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2217 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2218 return get_constraint_for (op);
2224 temp.type = ADDRESSOF;
2225 temp.var = anything_id;
2231 case tcc_exceptional:
2233 switch (TREE_CODE (t))
2236 return get_constraint_for (PHI_RESULT (t));
2238 return get_constraint_exp_from_ssa_var (t);
2241 temp.type = ADDRESSOF;
2242 temp.var = anything_id;
2248 case tcc_declaration:
2249 return get_constraint_exp_from_ssa_var (t);
2252 temp.type = ADDRESSOF;
2253 temp.var = anything_id;
2261 /* Handle the structure copy case where we have a simple structure copy
2262 between LHS and RHS that is of SIZE (in bits)
2264 For each field of the lhs variable (lhsfield)
2265 For each field of the rhs variable at lhsfield.offset (rhsfield)
2266 add the constraint lhsfield = rhsfield
2270 do_simple_structure_copy (const struct constraint_expr lhs,
2271 const struct constraint_expr rhs,
2272 const unsigned HOST_WIDE_INT size)
2274 varinfo_t p = get_varinfo (lhs.var);
2275 unsigned HOST_WIDE_INT pstart, last;
2277 last = p->offset + size;
2278 for (; p && p->offset < last; p = p->next)
2281 struct constraint_expr templhs = lhs;
2282 struct constraint_expr temprhs = rhs;
2283 unsigned HOST_WIDE_INT fieldoffset;
2285 templhs.var = p->id;
2286 q = get_varinfo (temprhs.var);
2287 fieldoffset = p->offset - pstart;
2288 q = first_vi_for_offset (q, q->offset + fieldoffset);
2289 temprhs.var = q->id;
2290 process_constraint (new_constraint (templhs, temprhs));
2295 /* Handle the structure copy case where we have a structure copy between a
2296 aggregate on the LHS and a dereference of a pointer on the RHS
2297 that is of SIZE (in bits)
2299 For each field of the lhs variable (lhsfield)
2300 rhs.offset = lhsfield->offset
2301 add the constraint lhsfield = rhs
2305 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2306 const struct constraint_expr rhs,
2307 const unsigned HOST_WIDE_INT size)
2309 varinfo_t p = get_varinfo (lhs.var);
2310 unsigned HOST_WIDE_INT pstart,last;
2312 last = p->offset + size;
2314 for (; p && p->offset < last; p = p->next)
2317 struct constraint_expr templhs = lhs;
2318 struct constraint_expr temprhs = rhs;
2319 unsigned HOST_WIDE_INT fieldoffset;
2322 if (templhs.type == SCALAR)
2323 templhs.var = p->id;
2325 templhs.offset = p->offset;
2327 q = get_varinfo (temprhs.var);
2328 fieldoffset = p->offset - pstart;
2329 temprhs.offset += fieldoffset;
2330 process_constraint (new_constraint (templhs, temprhs));
2334 /* Handle the structure copy case where we have a structure copy
2335 between a aggregate on the RHS and a dereference of a pointer on
2336 the LHS that is of SIZE (in bits)
2338 For each field of the rhs variable (rhsfield)
2339 lhs.offset = rhsfield->offset
2340 add the constraint lhs = rhsfield
2344 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2345 const struct constraint_expr rhs,
2346 const unsigned HOST_WIDE_INT size)
2348 varinfo_t p = get_varinfo (rhs.var);
2349 unsigned HOST_WIDE_INT pstart,last;
2351 last = p->offset + size;
2353 for (; p && p->offset < last; p = p->next)
2356 struct constraint_expr templhs = lhs;
2357 struct constraint_expr temprhs = rhs;
2358 unsigned HOST_WIDE_INT fieldoffset;
2361 if (temprhs.type == SCALAR)
2362 temprhs.var = p->id;
2364 temprhs.offset = p->offset;
2366 q = get_varinfo (templhs.var);
2367 fieldoffset = p->offset - pstart;
2368 templhs.offset += fieldoffset;
2369 process_constraint (new_constraint (templhs, temprhs));
2374 /* Handle aggregate copies by expanding into copies of the respective
2375 fields of the structures. */
2378 do_structure_copy (tree lhsop, tree rhsop)
2380 struct constraint_expr lhs, rhs, tmp;
2382 unsigned HOST_WIDE_INT lhssize;
2383 unsigned HOST_WIDE_INT rhssize;
2385 lhs = get_constraint_for (lhsop);
2386 rhs = get_constraint_for (rhsop);
2388 /* If we have special var = x, swap it around. */
2389 if (lhs.var <= integer_id && rhs.var > integer_id)
2396 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2397 possible it's something we could handle. However, most cases falling
2398 into this are dealing with transparent unions, which are slightly
2400 if (rhs.type == ADDRESSOF && rhs.var > integer_id)
2402 rhs.type = ADDRESSOF;
2403 rhs.var = anything_id;
2406 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2407 that special var. */
2408 if (rhs.var <= integer_id)
2410 for (p = get_varinfo (lhs.var); p; p = p->next)
2412 struct constraint_expr templhs = lhs;
2413 struct constraint_expr temprhs = rhs;
2414 if (templhs.type == SCALAR )
2415 templhs.var = p->id;
2417 templhs.offset += p->offset;
2418 process_constraint (new_constraint (templhs, temprhs));
2423 tree rhstype = TREE_TYPE (rhsop);
2424 tree lhstype = TREE_TYPE (lhsop);
2425 tree rhstypesize = TYPE_SIZE (rhstype);
2426 tree lhstypesize = TYPE_SIZE (lhstype);
2428 /* If we have a variably sized types on the rhs or lhs, and a deref
2429 constraint, add the constraint, lhsconstraint = &ANYTHING.
2430 This is conservatively correct because either the lhs is an unknown
2431 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2432 constraint, and every variable it can point to must be unknown sized
2433 anyway, so we don't need to worry about fields at all. */
2434 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2435 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2437 rhs.var = anything_id;
2438 rhs.type = ADDRESSOF;
2440 process_constraint (new_constraint (lhs, rhs));
2444 /* The size only really matters insofar as we don't set more or less of
2445 the variable. If we hit an unknown size var, the size should be the
2446 whole darn thing. */
2447 if (get_varinfo (rhs.var)->is_unknown_size_var)
2450 rhssize = TREE_INT_CST_LOW (rhstypesize);
2452 if (get_varinfo (lhs.var)->is_unknown_size_var)
2455 lhssize = TREE_INT_CST_LOW (lhstypesize);
2458 if (rhs.type == SCALAR && lhs.type == SCALAR)
2459 do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2460 else if (lhs.type != DEREF && rhs.type == DEREF)
2461 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2462 else if (lhs.type == DEREF && rhs.type != DEREF)
2463 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2466 tree pointedtotype = lhstype;
2469 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2470 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2471 do_structure_copy (tmpvar, rhsop);
2472 do_structure_copy (lhsop, tmpvar);
2478 /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere
2482 ref_contains_indirect_ref (tree ref)
2484 while (handled_component_p (ref))
2486 if (TREE_CODE (ref) == INDIRECT_REF)
2488 ref = TREE_OPERAND (ref, 0);
2494 /* Update related alias information kept in AI. This is used when
2495 building name tags, alias sets and deciding grouping heuristics.
2496 STMT is the statement to process. This function also updates
2497 ADDRESSABLE_VARS. */
2500 update_alias_info (tree stmt, struct alias_info *ai)
2503 use_operand_p use_p;
2504 def_operand_p def_p;
2506 bool stmt_escapes_p = is_escape_site (stmt, ai);
2508 /* Mark all the variables whose address are taken by the statement. */
2509 addr_taken = addresses_taken (stmt);
2512 bitmap_ior_into (addressable_vars, addr_taken);
2514 /* If STMT is an escape point, all the addresses taken by it are
2521 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
2522 mark_call_clobbered (referenced_var (i));
2526 /* Process each operand use. If an operand may be aliased, keep
2527 track of how many times it's being used. For pointers, determine
2528 whether they are dereferenced by the statement, or whether their
2529 value escapes, etc. */
2530 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2534 struct ptr_info_def *pi;
2536 unsigned num_uses, num_derefs;
2538 op = USE_FROM_PTR (use_p);
2540 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2541 to the set of addressable variables. */
2542 if (TREE_CODE (op) == ADDR_EXPR)
2544 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
2546 /* PHI nodes don't have annotations for pinning the set
2547 of addresses taken, so we collect them here.
2549 FIXME, should we allow PHI nodes to have annotations
2550 so that they can be treated like regular statements?
2551 Currently, they are treated as second-class
2553 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
2557 /* Ignore constants. */
2558 if (TREE_CODE (op) != SSA_NAME)
2561 var = SSA_NAME_VAR (op);
2562 v_ann = var_ann (var);
2564 /* If the operand's variable may be aliased, keep track of how
2565 many times we've referenced it. This is used for alias
2566 grouping in compute_flow_insensitive_aliasing. */
2567 if (may_be_aliased (var))
2568 NUM_REFERENCES_INC (v_ann);
2570 /* We are only interested in pointers. */
2571 if (!POINTER_TYPE_P (TREE_TYPE (op)))
2574 pi = get_ptr_info (op);
2576 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
2577 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
2579 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
2580 VARRAY_PUSH_TREE (ai->processed_ptrs, op);
2583 /* If STMT is a PHI node, then it will not have pointer
2584 dereferences and it will not be an escape point. */
2585 if (TREE_CODE (stmt) == PHI_NODE)
2588 /* Determine whether OP is a dereferenced pointer, and if STMT
2589 is an escape point, whether OP escapes. */
2590 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
2594 /* Mark OP as dereferenced. In a subsequent pass,
2595 dereferenced pointers that point to a set of
2596 variables will be assigned a name tag to alias
2597 all the variables OP points to. */
2598 pi->is_dereferenced = 1;
2600 /* Keep track of how many time we've dereferenced each
2602 NUM_REFERENCES_INC (v_ann);
2604 /* If this is a store operation, mark OP as being
2605 dereferenced to store, otherwise mark it as being
2606 dereferenced to load. */
2608 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
2610 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
2613 if (stmt_escapes_p && num_derefs < num_uses)
2615 /* If STMT is an escape point and STMT contains at
2616 least one direct use of OP, then the value of OP
2617 escapes and so the pointed-to variables need to
2618 be marked call-clobbered. */
2619 pi->value_escapes_p = 1;
2621 /* If the statement makes a function call, assume
2622 that pointer OP will be dereferenced in a store
2623 operation inside the called function. */
2624 if (get_call_expr_in (stmt))
2626 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
2627 pi->is_dereferenced = 1;
2632 /* Update reference counter for definitions to any potentially
2633 aliased variable. This is used in the alias grouping heuristics. */
2634 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, iter, SSA_OP_ALL_DEFS)
2636 tree op = DEF_FROM_PTR (def_p);
2637 tree var = SSA_NAME_VAR (op);
2638 var_ann_t ann = var_ann (var);
2639 bitmap_set_bit (ai->written_vars, DECL_UID (var));
2640 if (may_be_aliased (var))
2641 NUM_REFERENCES_INC (ann);
2646 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
2647 Expressions of the type PTR + CST can be handled in two ways:
2649 1- If the constraint for PTR is ADDRESSOF for a non-structure
2650 variable, then we can use it directly because adding or
2651 subtracting a constant may not alter the original ADDRESSOF
2652 constraing (i.e., pointer arithmetic may not legally go outside
2653 an object's boundaries).
2655 2- If the constraint for PTR is ADDRESSOF for a structure variable,
2656 then if CST is a compile-time constant that can be used as an
2657 offset, we can determine which sub-variable will be pointed-to
2660 Return true if the expression is handled. For any other kind of
2661 expression, return false so that each operand can be added as a
2662 separate constraint by the caller. */
2665 handle_ptr_arith (struct constraint_expr lhs, tree expr)
2668 struct constraint_expr base, offset;
2670 if (TREE_CODE (expr) != PLUS_EXPR)
2673 op0 = TREE_OPERAND (expr, 0);
2674 op1 = TREE_OPERAND (expr, 1);
2676 base = get_constraint_for (op0);
2678 offset.var = anyoffset_id;
2679 offset.type = ADDRESSOF;
2682 process_constraint (new_constraint (lhs, base));
2683 process_constraint (new_constraint (lhs, offset));
2689 /* Walk statement T setting up aliasing constraints according to the
2690 references found in T. This function is the main part of the
2691 constraint builder. AI points to auxiliary alias information used
2692 when building alias sets and computing alias grouping heuristics. */
2695 find_func_aliases (tree t, struct alias_info *ai)
2697 struct constraint_expr lhs, rhs;
2699 /* Update various related attributes like escaped addresses, pointer
2700 dereferences for loads and stores. This is used when creating
2701 name tags and alias sets. */
2702 update_alias_info (t, ai);
2704 /* Now build constraints expressions. */
2705 if (TREE_CODE (t) == PHI_NODE)
2707 /* Only care about pointers and structures containing
2709 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
2710 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
2714 lhs = get_constraint_for (PHI_RESULT (t));
2715 for (i = 0; i < PHI_NUM_ARGS (t); i++)
2717 rhs = get_constraint_for (PHI_ARG_DEF (t, i));
2718 process_constraint (new_constraint (lhs, rhs));
2722 else if (TREE_CODE (t) == MODIFY_EXPR)
2724 tree lhsop = TREE_OPERAND (t, 0);
2725 tree rhsop = TREE_OPERAND (t, 1);
2728 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2729 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
2731 do_structure_copy (lhsop, rhsop);
2735 /* Only care about operations with pointers, structures
2736 containing pointers, dereferences, and call expressions. */
2737 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
2738 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
2739 || ref_contains_indirect_ref (lhsop)
2740 || TREE_CODE (rhsop) == CALL_EXPR)
2742 lhs = get_constraint_for (lhsop);
2743 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
2745 /* RHS that consist of unary operations,
2746 exceptional types, or bare decls/constants, get
2747 handled directly by get_constraint_for. */
2749 case tcc_declaration:
2751 case tcc_exceptional:
2752 case tcc_expression:
2755 rhs = get_constraint_for (rhsop);
2756 process_constraint (new_constraint (lhs, rhs));
2758 /* When taking the address of an aggregate
2759 type, from the LHS we can access any field
2761 if (rhs.type == ADDRESSOF
2762 && rhs.var > anything_id
2763 && AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (rhsop))))
2765 rhs.var = anyoffset_id;
2766 rhs.type = ADDRESSOF;
2768 process_constraint (new_constraint (lhs, rhs));
2775 /* For pointer arithmetic of the form
2776 PTR + CST, we can simply use PTR's
2777 constraint because pointer arithmetic is
2778 not allowed to go out of bounds. */
2779 if (handle_ptr_arith (lhs, rhsop))
2784 /* Otherwise, walk each operand. Notice that we
2785 can't use the operand interface because we need
2786 to process expressions other than simple operands
2787 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
2789 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
2791 tree op = TREE_OPERAND (rhsop, i);
2792 rhs = get_constraint_for (op);
2793 process_constraint (new_constraint (lhs, rhs));
2800 /* After promoting variables and computing aliasing we will
2801 need to re-scan most statements. FIXME: Try to minimize the
2802 number of statements re-scanned. It's not really necessary to
2803 re-scan *all* statements. */
2804 mark_stmt_modified (t);
2808 /* Find the first varinfo in the same variable as START that overlaps with
2810 Effectively, walk the chain of fields for the variable START to find the
2811 first field that overlaps with OFFSET.
2812 Abort if we can't find one. */
2815 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
2817 varinfo_t curr = start;
2820 /* We may not find a variable in the field list with the actual
2821 offset when when we have glommed a structure to a variable.
2822 In that case, however, offset should still be within the size
2824 if (offset >= curr->offset && offset < (curr->offset + curr->size))
2833 /* Insert the varinfo FIELD into the field list for BASE, ordered by
2837 insert_into_field_list (varinfo_t base, varinfo_t field)
2839 varinfo_t prev = base;
2840 varinfo_t curr = base->next;
2851 if (field->offset <= curr->offset)
2856 field->next = prev->next;
2861 /* qsort comparison function for two fieldoff's PA and PB */
2864 fieldoff_compare (const void *pa, const void *pb)
2866 const fieldoff_s *foa = (const fieldoff_s *)pa;
2867 const fieldoff_s *fob = (const fieldoff_s *)pb;
2868 HOST_WIDE_INT foasize, fobsize;
2870 if (foa->offset != fob->offset)
2871 return foa->offset - fob->offset;
2873 foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
2874 fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
2875 return foasize - fobsize;
2878 /* Sort a fieldstack according to the field offset and sizes. */
2879 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
2881 qsort (VEC_address (fieldoff_s, fieldstack),
2882 VEC_length (fieldoff_s, fieldstack),
2883 sizeof (fieldoff_s),
2887 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
2888 of TYPE onto fieldstack, recording their offsets along the way.
2889 OFFSET is used to keep track of the offset in this entire structure, rather
2890 than just the immediately containing structure. Returns the number
2892 HAS_UNION is set to true if we find a union type as a field of
2896 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
2897 HOST_WIDE_INT offset, bool *has_union)
2902 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2903 if (TREE_CODE (field) == FIELD_DECL)
2908 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
2909 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
2912 if (!var_can_have_subvars (field))
2914 else if (!(push_fields_onto_fieldstack
2915 (TREE_TYPE (field), fieldstack,
2916 offset + bitpos_of_field (field), has_union))
2917 && DECL_SIZE (field)
2918 && !integer_zerop (DECL_SIZE (field)))
2919 /* Empty structures may have actual size, like in C++. So
2920 see if we didn't push any subfields and the size is
2921 nonzero, push the field onto the stack */
2928 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
2929 pair->field = field;
2930 pair->offset = offset + bitpos_of_field (field);
2939 make_constraint_to_anything (varinfo_t vi)
2941 struct constraint_expr lhs, rhs;
2947 rhs.var = anything_id;
2949 rhs.type = ADDRESSOF;
2950 process_constraint (new_constraint (lhs, rhs));
2953 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
2954 This will also create any varinfo structures necessary for fields
2958 create_variable_info_for (tree decl, const char *name)
2960 unsigned int index = VEC_length (varinfo_t, varmap);
2962 tree decltype = TREE_TYPE (decl);
2963 bool notokay = false;
2965 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
2966 VEC (fieldoff_s,heap) *fieldstack = NULL;
2969 hasunion = TREE_CODE (decltype) == UNION_TYPE
2970 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
2971 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
2973 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
2976 VEC_free (fieldoff_s, heap, fieldstack);
2982 /* If the variable doesn't have subvars, we may end up needing to
2983 sort the field list and create fake variables for all the
2985 vi = new_var_info (decl, index, name, index);
2988 vi->has_union = hasunion;
2989 if (!TYPE_SIZE (decltype)
2990 || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
2991 || TREE_CODE (decltype) == ARRAY_TYPE
2992 || TREE_CODE (decltype) == UNION_TYPE
2993 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
2995 vi->is_unknown_size_var = true;
3001 vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
3002 vi->size = vi->fullsize;
3005 insert_id_for_tree (vi->decl, index);
3006 VEC_safe_push (varinfo_t, gc, varmap, vi);
3008 make_constraint_to_anything (vi);
3011 if (use_field_sensitive
3013 && !vi->is_unknown_size_var
3014 && var_can_have_subvars (decl))
3016 unsigned int newindex = VEC_length (varinfo_t, varmap);
3017 fieldoff_s *fo = NULL;
3021 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3023 if (!DECL_SIZE (fo->field)
3024 || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
3025 || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE
3033 /* We can't sort them if we have a field with a variable sized type,
3034 which will make notokay = true. In that case, we are going to return
3035 without creating varinfos for the fields anyway, so sorting them is a
3038 sort_fieldstack (fieldstack);
3040 if (VEC_length (fieldoff_s, fieldstack) != 0)
3041 fo = VEC_index (fieldoff_s, fieldstack, 0);
3043 if (fo == NULL || notokay)
3045 vi->is_unknown_size_var = 1;
3048 VEC_free (fieldoff_s, heap, fieldstack);
3053 vi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
3054 for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3057 const char *newname;
3061 newindex = VEC_length (varinfo_t, varmap);
3062 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (field));
3063 newname = ggc_strdup (tempname);
3065 newvi = new_var_info (decl, newindex, newname, newindex);
3066 newvi->offset = fo->offset;
3067 newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
3068 newvi->fullsize = vi->fullsize;
3069 insert_into_field_list (vi, newvi);
3070 VEC_safe_push (varinfo_t, gc, varmap, newvi);
3072 make_constraint_to_anything (newvi);
3076 VEC_free (fieldoff_s, heap, fieldstack);
3081 /* Print out the points-to solution for VAR to FILE. */
3084 dump_solution_for_var (FILE *file, unsigned int var)
3086 varinfo_t vi = get_varinfo (var);
3090 fprintf (file, "%s = { ", vi->name);
3091 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
3093 fprintf (file, "%s ", get_varinfo (i)->name);
3095 fprintf (file, "}\n");
3098 /* Print the points-to solution for VAR to stdout. */
3101 debug_solution_for_var (unsigned int var)
3103 dump_solution_for_var (stdout, var);
3107 /* Create varinfo structures for all of the variables in the
3108 function for intraprocedural mode. */
3111 intra_create_variable_infos (void)
3115 /* For each incoming argument arg, ARG = &ANYTHING */
3116 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
3118 struct constraint_expr lhs;
3119 struct constraint_expr rhs;
3124 lhs.var = create_variable_info_for (t, alias_get_name (t));
3126 rhs.var = anything_id;
3127 rhs.type = ADDRESSOF;
3130 for (p = get_varinfo (lhs.var); p; p = p->next)
3132 struct constraint_expr temp = lhs;
3134 process_constraint (new_constraint (temp, rhs));
3140 /* Set bits in INTO corresponding to the variable uids in solution set
3144 set_uids_in_ptset (bitmap into, bitmap from)
3148 bool found_anyoffset = false;
3151 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
3153 varinfo_t vi = get_varinfo (i);
3155 /* If we find ANYOFFSET in the solution and the solution
3156 includes SFTs for some structure, then all the SFTs in that
3157 structure will need to be added to the alias set. */
3158 if (vi->id == anyoffset_id)
3160 found_anyoffset = true;
3164 /* The only artificial variables that are allowed in a may-alias
3165 set are heap variables. */
3166 if (vi->is_artificial_var && !vi->is_heap_var)
3169 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
3171 /* Variables containing unions may need to be converted to
3172 their SFT's, because SFT's can have unions and we cannot. */
3173 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
3174 bitmap_set_bit (into, DECL_UID (sv->var));
3176 else if (TREE_CODE (vi->decl) == VAR_DECL
3177 || TREE_CODE (vi->decl) == PARM_DECL)
3180 && var_can_have_subvars (vi->decl)
3181 && get_subvars_for_var (vi->decl))
3183 /* If ANYOFFSET is in the solution set and VI->DECL is
3184 an aggregate variable with sub-variables, then any of
3185 the SFTs inside VI->DECL may have been accessed. Add
3186 all the sub-vars for VI->DECL. */
3187 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
3188 bitmap_set_bit (into, DECL_UID (sv->var));
3190 else if (var_can_have_subvars (vi->decl)
3191 && get_subvars_for_var (vi->decl))
3193 /* If VI->DECL is an aggregate for which we created
3194 SFTs, add the SFT corresponding to VI->OFFSET. */
3195 tree sft = get_subvar_at (vi->decl, vi->offset);
3196 bitmap_set_bit (into, DECL_UID (sft));
3200 /* Otherwise, just add VI->DECL to the alias set. */
3201 bitmap_set_bit (into, DECL_UID (vi->decl));
3208 static bool have_alias_info = false;
3210 /* Given a pointer variable P, fill in its points-to set, or return
3211 false if we can't. */
3214 find_what_p_points_to (tree p)
3216 unsigned int id = 0;
3218 if (!have_alias_info)
3221 if (lookup_id_for_tree (p, &id))
3223 varinfo_t vi = get_varinfo (id);
3225 if (vi->is_artificial_var)
3228 /* See if this is a field or a structure. */
3229 if (vi->size != vi->fullsize)
3231 /* Nothing currently asks about structure fields directly,
3232 but when they do, we need code here to hand back the
3234 if (!var_can_have_subvars (vi->decl)
3235 || get_subvars_for_var (vi->decl) == NULL)
3240 struct ptr_info_def *pi = get_ptr_info (p);
3244 /* This variable may have been collapsed, let's get the real
3246 vi = get_varinfo (vi->node);
3248 /* Translate artificial variables into SSA_NAME_PTR_INFO
3250 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
3252 varinfo_t vi = get_varinfo (i);
3254 if (vi->is_artificial_var)
3256 /* FIXME. READONLY should be handled better so that
3257 flow insensitive aliasing can disregard writeable
3259 if (vi->id == nothing_id)
3261 else if (vi->id == anything_id)
3262 pi->pt_anything = 1;
3263 else if (vi->id == readonly_id)
3264 pi->pt_anything = 1;
3265 else if (vi->id == integer_id)
3266 pi->pt_anything = 1;
3267 else if (vi->is_heap_var)
3268 pi->pt_global_mem = 1;
3272 if (pi->pt_anything)
3276 pi->pt_vars = BITMAP_GGC_ALLOC ();
3278 set_uids_in_ptset (pi->pt_vars, vi->solution);
3280 if (bitmap_empty_p (pi->pt_vars))
3291 /* Initialize things necessary to perform PTA */
3294 init_alias_vars (void)
3296 bitmap_obstack_initialize (&ptabitmap_obstack);
3300 /* Dump points-to information to OUTFILE. */
3303 dump_sa_points_to_info (FILE *outfile)
3307 fprintf (outfile, "\nPoints-to sets\n\n");
3309 if (dump_flags & TDF_STATS)
3311 fprintf (outfile, "Stats:\n");
3312 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
3313 fprintf (outfile, "Statically unified vars: %d\n",
3314 stats.unified_vars_static);
3315 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
3316 fprintf (outfile, "Dynamically unified vars: %d\n",
3317 stats.unified_vars_dynamic);
3318 fprintf (outfile, "Iterations: %d\n", stats.iterations);
3321 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
3322 dump_solution_for_var (outfile, i);
3326 /* Debug points-to information to stderr. */
3329 debug_sa_points_to_info (void)
3331 dump_sa_points_to_info (stderr);
3335 /* Initialize the always-existing constraint variables for NULL
3336 ANYTHING, READONLY, and INTEGER */
3339 init_base_vars (void)
3341 struct constraint_expr lhs, rhs;
3343 /* Create the NULL variable, used to represent that a variable points
3345 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
3346 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
3347 insert_id_for_tree (nothing_tree, 0);
3348 var_nothing->is_artificial_var = 1;
3349 var_nothing->offset = 0;
3350 var_nothing->size = ~0;
3351 var_nothing->fullsize = ~0;
3353 VEC_safe_push (varinfo_t, gc, varmap, var_nothing);
3355 /* Create the ANYTHING variable, used to represent that a variable
3356 points to some unknown piece of memory. */
3357 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
3358 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
3359 insert_id_for_tree (anything_tree, 1);
3360 var_anything->is_artificial_var = 1;
3361 var_anything->size = ~0;
3362 var_anything->offset = 0;
3363 var_anything->next = NULL;
3364 var_anything->fullsize = ~0;
3367 /* Anything points to anything. This makes deref constraints just
3368 work in the presence of linked list and other p = *p type loops,
3369 by saying that *ANYTHING = ANYTHING. */
3370 VEC_safe_push (varinfo_t, gc, varmap, var_anything);
3372 lhs.var = anything_id;
3374 rhs.type = ADDRESSOF;
3375 rhs.var = anything_id;
3377 var_anything->address_taken = true;
3379 /* This specifically does not use process_constraint because
3380 process_constraint ignores all anything = anything constraints, since all
3381 but this one are redundant. */
3382 VEC_safe_push (constraint_t, gc, constraints, new_constraint (lhs, rhs));
3384 /* Create the READONLY variable, used to represent that a variable
3385 points to readonly memory. */
3386 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
3387 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
3388 var_readonly->is_artificial_var = 1;
3389 var_readonly->offset = 0;
3390 var_readonly->size = ~0;
3391 var_readonly->fullsize = ~0;
3392 var_readonly->next = NULL;
3393 insert_id_for_tree (readonly_tree, 2);
3395 VEC_safe_push (varinfo_t, gc, varmap, var_readonly);
3397 /* readonly memory points to anything, in order to make deref
3398 easier. In reality, it points to anything the particular
3399 readonly variable can point to, but we don't track this
3402 lhs.var = readonly_id;
3404 rhs.type = ADDRESSOF;
3405 rhs.var = anything_id;
3408 process_constraint (new_constraint (lhs, rhs));
3410 /* Create the INTEGER variable, used to represent that a variable points
3412 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
3413 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
3414 insert_id_for_tree (integer_tree, 3);
3415 var_integer->is_artificial_var = 1;
3416 var_integer->size = ~0;
3417 var_integer->fullsize = ~0;
3418 var_integer->offset = 0;
3419 var_integer->next = NULL;
3421 VEC_safe_push (varinfo_t, gc, varmap, var_integer);
3423 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
3424 integer will point to. */
3426 lhs.var = integer_id;
3428 rhs.type = ADDRESSOF;
3429 rhs.var = anything_id;
3431 process_constraint (new_constraint (lhs, rhs));
3433 /* Create the ANYOFFSET variable, used to represent an arbitrary offset
3434 inside an object. This is similar to ANYTHING, but less drastic.
3435 It means that the pointer can point anywhere inside an object,
3436 but not outside of it. */
3437 anyoffset_tree = create_tmp_var_raw (void_type_node, "ANYOFFSET");
3439 var_anyoffset = new_var_info (anyoffset_tree, anyoffset_id, "ANYOFFSET",
3441 insert_id_for_tree (anyoffset_tree, anyoffset_id);
3442 var_anyoffset->is_artificial_var = 1;
3443 var_anyoffset->size = ~0;
3444 var_anyoffset->offset = 0;
3445 var_anyoffset->next = NULL;
3446 var_anyoffset->fullsize = ~0;
3447 VEC_safe_push (varinfo_t, gc, varmap, var_anyoffset);
3449 /* ANYOFFSET points to ANYOFFSET. */
3451 lhs.var = anyoffset_id;
3453 rhs.type = ADDRESSOF;
3454 rhs.var = anyoffset_id;
3456 process_constraint (new_constraint (lhs, rhs));
3460 /* Create points-to sets for the current function. See the comments
3461 at the start of the file for an algorithmic overview. */
3464 compute_points_to_sets (struct alias_info *ai)
3468 timevar_push (TV_TREE_PTA);
3472 constraint_pool = create_alloc_pool ("Constraint pool",
3473 sizeof (struct constraint), 30);
3474 variable_info_pool = create_alloc_pool ("Variable info pool",
3475 sizeof (struct variable_info), 30);
3476 constraint_edge_pool = create_alloc_pool ("Constraint edges",
3477 sizeof (struct constraint_edge), 30);
3479 constraints = VEC_alloc (constraint_t, gc, 8);
3480 varmap = VEC_alloc (varinfo_t, gc, 8);
3481 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
3482 memset (&stats, 0, sizeof (stats));
3486 intra_create_variable_infos ();
3488 /* Now walk all statements and derive aliases. */
3491 block_stmt_iterator bsi;
3494 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3495 if (is_gimple_reg (PHI_RESULT (phi)))
3496 find_func_aliases (phi, ai);
3498 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3499 find_func_aliases (bsi_stmt (bsi), ai);
3502 build_constraint_graph ();
3506 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
3507 dump_constraints (dump_file);
3511 fprintf (dump_file, "\nCollapsing static cycles and doing variable "
3514 find_and_collapse_graph_cycles (graph, false);
3515 perform_var_substitution (graph);
3518 fprintf (dump_file, "\nSolving graph:\n");
3520 solve_graph (graph);
3523 dump_sa_points_to_info (dump_file);
3525 have_alias_info = true;
3527 timevar_pop (TV_TREE_PTA);
3531 /* Delete created points-to sets. */
3534 delete_points_to_sets (void)
3536 htab_delete (id_for_tree);
3537 free_alloc_pool (variable_info_pool);
3538 free_alloc_pool (constraint_pool);
3539 free_alloc_pool (constraint_edge_pool);
3540 bitmap_obstack_release (&ptabitmap_obstack);
3541 have_alias_info = false;