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"
54 /* The idea behind this analyzer is to generate set constraints from the
55 program, then solve the resulting constraints in order to generate the
58 Set constraints are a way of modeling program analysis problems that
59 involve sets. They consist of an inclusion constraint language,
60 describing the variables (each variable is a set) and operations that
61 are involved on the variables, and a set of rules that derive facts
62 from these operations. To solve a system of set constraints, you derive
63 all possible facts under the rules, which gives you the correct sets
66 See "Efficient Field-sensitive pointer analysis for C" by "David
67 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
68 http://citeseer.ist.psu.edu/pearce04efficient.html
70 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
71 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
72 http://citeseer.ist.psu.edu/heintze01ultrafast.html
74 There are three types of constraint expressions, DEREF, ADDRESSOF, and
75 SCALAR. Each constraint expression consists of a constraint type,
76 a variable, and an offset.
78 SCALAR is a constraint expression type used to represent x, whether
79 it appears on the LHS or the RHS of a statement.
80 DEREF is a constraint expression type used to represent *x, whether
81 it appears on the LHS or the RHS of a statement.
82 ADDRESSOF is a constraint expression used to represent &x, whether
83 it appears on the LHS or the RHS of a statement.
85 Each pointer variable in the program is assigned an integer id, and
86 each field of a structure variable is assigned an integer id as well.
88 Structure variables are linked to their list of fields through a "next
89 field" in each variable that points to the next field in offset
91 Each variable for a structure field has
93 1. "size", that tells the size in bits of that field.
94 2. "fullsize, that tells the size in bits of the entire structure.
95 3. "offset", that tells the offset in bits from the beginning of the
96 structure to this field.
108 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
109 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
110 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
113 In order to solve the system of set constraints, the following is
116 1. Each constraint variable x has a solution set associated with it,
119 2. Constraints are separated into direct, copy, and complex.
120 Direct constraints are ADDRESSOF constraints that require no extra
121 processing, such as P = &Q
122 Copy constraints are those of the form P = Q.
123 Complex constraints are all the constraints involving dereferences.
125 3. All direct constraints of the form P = &Q are processed, such
126 that Q is added to Sol(P)
128 4. All complex constraints for a given constraint variable are stored in a
129 linked list attached to that variable's node.
131 5. A directed graph is built out of the copy constraints. Each
132 constraint variable is a node in the graph, and an edge from
133 Q to P is added for each copy constraint of the form P = Q
135 6. The graph is then walked, and solution sets are
136 propagated along the copy edges, such that an edge from Q to P
137 causes Sol(P) <- Sol(P) union Sol(Q).
139 7. As we visit each node, all complex constraints associated with
140 that node are processed by adding appropriate copy edges to the graph, or the
141 appropriate variables to the solution set.
143 8. The process of walking the graph is iterated until no solution
146 Prior to walking the graph in steps 6 and 7, We perform static
147 cycle elimination on the constraint graph, as well
148 as off-line variable substitution.
150 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
151 on and turned into anything), but isn't. You can just see what offset
152 inside the pointed-to struct it's going to access.
154 TODO: Constant bounded arrays can be handled as if they were structs of the
155 same number of elements.
157 TODO: Modeling heap and incoming pointers becomes much better if we
158 add fields to them as we discover them, which we could do.
160 TODO: We could handle unions, but to be honest, it's probably not
161 worth the pain or slowdown. */
163 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
164 htab_t heapvar_for_stmt;
165 static bool use_field_sensitive = true;
166 static int in_ipa_mode = 0;
167 static bitmap_obstack predbitmap_obstack;
168 static bitmap_obstack ptabitmap_obstack;
169 static bitmap_obstack iteration_obstack;
171 static unsigned int create_variable_info_for (tree, const char *);
172 static void build_constraint_graph (void);
174 DEF_VEC_P(constraint_t);
175 DEF_VEC_ALLOC_P(constraint_t,heap);
177 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
179 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
181 static struct constraint_stats
183 unsigned int total_vars;
184 unsigned int collapsed_vars;
185 unsigned int unified_vars_static;
186 unsigned int unified_vars_dynamic;
187 unsigned int iterations;
188 unsigned int num_edges;
193 /* ID of this variable */
196 /* Name of this variable */
199 /* Tree that this variable is associated with. */
202 /* Offset of this variable, in bits, from the base variable */
203 unsigned HOST_WIDE_INT offset;
205 /* Size of the variable, in bits. */
206 unsigned HOST_WIDE_INT size;
208 /* Full size of the base variable, in bits. */
209 unsigned HOST_WIDE_INT fullsize;
211 /* A link to the variable for the next field in this structure. */
212 struct variable_info *next;
214 /* Node in the graph that represents the constraints and points-to
215 solution for the variable. */
218 /* True if the address of this variable is taken. Needed for
219 variable substitution. */
220 unsigned int address_taken:1;
222 /* True if this variable is the target of a dereference. Needed for
223 variable substitution. */
224 unsigned int indirect_target:1;
226 /* True if this is a variable created by the constraint analysis, such as
227 heap variables and constraints we had to break up. */
228 unsigned int is_artificial_var:1;
230 /* True if this is a special variable whose solution set should not be
232 unsigned int is_special_var:1;
234 /* True for variables whose size is not known or variable. */
235 unsigned int is_unknown_size_var:1;
237 /* True for variables that have unions somewhere in them. */
238 unsigned int has_union:1;
240 /* True if this is a heap variable. */
241 unsigned int is_heap_var:1;
243 /* Points-to set for this variable. */
246 /* Variable ids represented by this node. */
249 /* Vector of complex constraints for this node. Complex
250 constraints are those involving dereferences. */
251 VEC(constraint_t,heap) *complex;
253 /* Variable id this was collapsed to due to type unsafety.
254 This should be unused completely after build_constraint_graph, or
255 something is broken. */
256 struct variable_info *collapsed_to;
258 typedef struct variable_info *varinfo_t;
260 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
262 /* Pool of variable info structures. */
263 static alloc_pool variable_info_pool;
265 DEF_VEC_P(varinfo_t);
267 DEF_VEC_ALLOC_P(varinfo_t, heap);
269 /* Table of variable info structures for constraint variables. Indexed directly
270 by variable info id. */
271 static VEC(varinfo_t,heap) *varmap;
273 /* Return the varmap element N */
275 static inline varinfo_t
276 get_varinfo (unsigned int n)
278 return VEC_index(varinfo_t, varmap, n);
281 /* Return the varmap element N, following the collapsed_to link. */
283 static inline varinfo_t
284 get_varinfo_fc (unsigned int n)
286 varinfo_t v = VEC_index(varinfo_t, varmap, n);
289 return v->collapsed_to;
293 /* Variable that represents the unknown pointer. */
294 static varinfo_t var_anything;
295 static tree anything_tree;
296 static unsigned int anything_id;
298 /* Variable that represents the NULL pointer. */
299 static varinfo_t var_nothing;
300 static tree nothing_tree;
301 static unsigned int nothing_id;
303 /* Variable that represents read only memory. */
304 static varinfo_t var_readonly;
305 static tree readonly_tree;
306 static unsigned int readonly_id;
308 /* Variable that represents integers. This is used for when people do things
310 static varinfo_t var_integer;
311 static tree integer_tree;
312 static unsigned int integer_id;
315 /* Lookup a heap var for FROM, and return it if we find one. */
318 heapvar_lookup (tree from)
320 struct tree_map *h, in;
323 h = htab_find_with_hash (heapvar_for_stmt, &in, htab_hash_pointer (from));
329 /* Insert a mapping FROM->TO in the heap var for statement
333 heapvar_insert (tree from, tree to)
338 h = ggc_alloc (sizeof (struct tree_map));
339 h->hash = htab_hash_pointer (from);
342 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
343 *(struct tree_map **) loc = h;
346 /* Return a new variable info structure consisting for a variable
347 named NAME, and using constraint graph node NODE. */
350 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
352 varinfo_t ret = pool_alloc (variable_info_pool);
358 ret->address_taken = false;
359 ret->indirect_target = false;
360 ret->is_artificial_var = false;
361 ret->is_heap_var = false;
362 ret->is_special_var = false;
363 ret->is_unknown_size_var = false;
364 ret->has_union = false;
365 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
366 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
369 ret->collapsed_to = NULL;
373 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
375 /* An expression that appears in a constraint. */
377 struct constraint_expr
379 /* Constraint type. */
380 constraint_expr_type type;
382 /* Variable we are referring to in the constraint. */
385 /* Offset, in bits, of this constraint from the beginning of
386 variables it ends up referring to.
388 IOW, in a deref constraint, we would deref, get the result set,
389 then add OFFSET to each member. */
390 unsigned HOST_WIDE_INT offset;
393 typedef struct constraint_expr ce_s;
395 DEF_VEC_ALLOC_O(ce_s, heap);
396 static void get_constraint_for (tree, VEC(ce_s, heap) **, bool *);
397 static void do_deref (VEC (ce_s, heap) **);
399 /* Our set constraints are made up of two constraint expressions, one
402 As described in the introduction, our set constraints each represent an
403 operation between set valued variables.
407 struct constraint_expr lhs;
408 struct constraint_expr rhs;
411 /* List of constraints that we use to build the constraint graph from. */
413 static VEC(constraint_t,heap) *constraints;
414 static alloc_pool constraint_pool;
416 /* An edge in the weighted constraint graph. The edges are weighted,
417 with a bit set in weights meaning their is an edge with that
419 We don't keep the src in the edge, because we always know what it
422 struct constraint_edge
428 typedef struct constraint_edge *constraint_edge_t;
429 static alloc_pool constraint_edge_pool;
431 /* Return a new constraint edge from SRC to DEST. */
433 static constraint_edge_t
434 new_constraint_edge (unsigned int dest)
436 constraint_edge_t ret = pool_alloc (constraint_edge_pool);
442 DEF_VEC_P(constraint_edge_t);
443 DEF_VEC_ALLOC_P(constraint_edge_t,heap);
446 /* The constraint graph is represented internally in two different
447 ways. The overwhelming majority of edges in the constraint graph
448 are zero weigh edges, and thus, using a vector of contrainst_edge_t
449 is a waste of time and memory, since they have no weights. We
450 simply use a bitmap to store the preds and succs for each node.
451 The weighted edges are stored as a set of adjacency vectors, one
452 per variable. succs[x] is the vector of successors for variable x,
453 and preds[x] is the vector of predecessors for variable x. IOW,
454 all edges are "forward" edges, which is not like our CFG. So
455 remember that preds[x]->src == x, and succs[x]->src == x. */
457 struct constraint_graph
459 bitmap *zero_weight_succs;
460 bitmap *zero_weight_preds;
461 VEC(constraint_edge_t,heap) **succs;
462 VEC(constraint_edge_t,heap) **preds;
465 typedef struct constraint_graph *constraint_graph_t;
467 static constraint_graph_t graph;
469 /* Create a new constraint consisting of LHS and RHS expressions. */
472 new_constraint (const struct constraint_expr lhs,
473 const struct constraint_expr rhs)
475 constraint_t ret = pool_alloc (constraint_pool);
481 /* Print out constraint C to FILE. */
484 dump_constraint (FILE *file, constraint_t c)
486 if (c->lhs.type == ADDRESSOF)
488 else if (c->lhs.type == DEREF)
490 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
491 if (c->lhs.offset != 0)
492 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
493 fprintf (file, " = ");
494 if (c->rhs.type == ADDRESSOF)
496 else if (c->rhs.type == DEREF)
498 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
499 if (c->rhs.offset != 0)
500 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
501 fprintf (file, "\n");
504 /* Print out constraint C to stderr. */
507 debug_constraint (constraint_t c)
509 dump_constraint (stderr, c);
512 /* Print out all constraints to FILE */
515 dump_constraints (FILE *file)
519 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
520 dump_constraint (file, c);
523 /* Print out all constraints to stderr. */
526 debug_constraints (void)
528 dump_constraints (stderr);
533 The solver is a simple worklist solver, that works on the following
536 sbitmap changed_nodes = all ones;
537 changed_count = number of nodes;
538 For each node that was already collapsed:
541 while (changed_count > 0)
543 compute topological ordering for constraint graph
545 find and collapse cycles in the constraint graph (updating
546 changed if necessary)
548 for each node (n) in the graph in topological order:
551 Process each complex constraint associated with the node,
552 updating changed if necessary.
554 For each outgoing edge from n, propagate the solution from n to
555 the destination of the edge, updating changed as necessary.
559 /* Return true if two constraint expressions A and B are equal. */
562 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
564 return a.type == b.type && a.var == b.var && a.offset == b.offset;
567 /* Return true if constraint expression A is less than constraint expression
568 B. This is just arbitrary, but consistent, in order to give them an
572 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
574 if (a.type == b.type)
577 return a.offset < b.offset;
579 return a.var < b.var;
582 return a.type < b.type;
585 /* Return true if constraint A is less than constraint B. This is just
586 arbitrary, but consistent, in order to give them an ordering. */
589 constraint_less (const constraint_t a, const constraint_t b)
591 if (constraint_expr_less (a->lhs, b->lhs))
593 else if (constraint_expr_less (b->lhs, a->lhs))
596 return constraint_expr_less (a->rhs, b->rhs);
599 /* Return true if two constraints A and B are equal. */
602 constraint_equal (struct constraint a, struct constraint b)
604 return constraint_expr_equal (a.lhs, b.lhs)
605 && constraint_expr_equal (a.rhs, b.rhs);
609 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
612 constraint_vec_find (VEC(constraint_t,heap) *vec,
613 struct constraint lookfor)
621 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
622 if (place >= VEC_length (constraint_t, vec))
624 found = VEC_index (constraint_t, vec, place);
625 if (!constraint_equal (*found, lookfor))
630 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
633 constraint_set_union (VEC(constraint_t,heap) **to,
634 VEC(constraint_t,heap) **from)
639 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
641 if (constraint_vec_find (*to, *c) == NULL)
643 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
645 VEC_safe_insert (constraint_t, heap, *to, place, c);
650 /* Take a solution set SET, add OFFSET to each member of the set, and
651 overwrite SET with the result when done. */
654 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
656 bitmap result = BITMAP_ALLOC (&iteration_obstack);
660 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
662 /* If this is a properly sized variable, only add offset if it's
663 less than end. Otherwise, it is globbed to a single
666 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
668 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
669 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
672 bitmap_set_bit (result, v->id);
674 else if (get_varinfo (i)->is_artificial_var
675 || get_varinfo (i)->has_union
676 || get_varinfo (i)->is_unknown_size_var)
678 bitmap_set_bit (result, i);
682 bitmap_copy (set, result);
683 BITMAP_FREE (result);
686 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
690 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
693 return bitmap_ior_into (to, from);
699 tmp = BITMAP_ALLOC (&iteration_obstack);
700 bitmap_copy (tmp, from);
701 solution_set_add (tmp, inc);
702 res = bitmap_ior_into (to, tmp);
708 /* Insert constraint C into the list of complex constraints for VAR. */
711 insert_into_complex (unsigned int var, constraint_t c)
713 varinfo_t vi = get_varinfo (var);
714 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
716 VEC_safe_insert (constraint_t, heap, vi->complex, place, c);
720 /* Compare two constraint edges A and B, return true if they are equal. */
723 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
725 return a.dest == b.dest;
728 /* Compare two constraint edges, return true if A is less than B */
731 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
733 if (a->dest < b->dest)
738 /* Find the constraint edge that matches LOOKFOR, in VEC.
739 Return the edge, if found, NULL otherwise. */
741 static constraint_edge_t
742 constraint_edge_vec_find (VEC(constraint_edge_t,heap) *vec,
743 struct constraint_edge lookfor)
746 constraint_edge_t edge = NULL;
748 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
749 constraint_edge_less);
750 if (place >= VEC_length (constraint_edge_t, vec))
752 edge = VEC_index (constraint_edge_t, vec, place);
753 if (!constraint_edge_equal (*edge, lookfor))
758 /* Condense two variable nodes into a single variable node, by moving
759 all associated info from SRC to TO. */
762 condense_varmap_nodes (unsigned int to, unsigned int src)
764 varinfo_t tovi = get_varinfo (to);
765 varinfo_t srcvi = get_varinfo (src);
770 /* the src node, and all its variables, are now the to node. */
772 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
773 get_varinfo (i)->node = to;
775 /* Merge the src node variables and the to node variables. */
776 bitmap_set_bit (tovi->variables, src);
777 bitmap_ior_into (tovi->variables, srcvi->variables);
778 bitmap_clear (srcvi->variables);
780 /* Move all complex constraints from src node into to node */
781 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
783 /* In complex constraints for node src, we may have either
784 a = *src, and *src = a. */
786 if (c->rhs.type == DEREF)
791 constraint_set_union (&tovi->complex, &srcvi->complex);
792 VEC_free (constraint_t, heap, srcvi->complex);
793 srcvi->complex = NULL;
796 /* Erase an edge from SRC to SRC from GRAPH. This routine only
797 handles self-edges (e.g. an edge from a to a). */
800 erase_graph_self_edge (constraint_graph_t graph, unsigned int src)
802 VEC(constraint_edge_t,heap) *predvec = graph->preds[src];
803 VEC(constraint_edge_t,heap) *succvec = graph->succs[src];
804 struct constraint_edge edge;
809 /* Remove from the successors. */
810 place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
811 constraint_edge_less);
813 /* Make sure we found the edge. */
814 #ifdef ENABLE_CHECKING
816 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
817 gcc_assert (constraint_edge_equal (*tmp, edge));
820 VEC_ordered_remove (constraint_edge_t, succvec, place);
822 /* Remove from the predecessors. */
823 place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
824 constraint_edge_less);
826 /* Make sure we found the edge. */
827 #ifdef ENABLE_CHECKING
829 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
830 gcc_assert (constraint_edge_equal (*tmp, edge));
833 VEC_ordered_remove (constraint_edge_t, predvec, place);
836 /* Remove edges involving NODE from GRAPH. */
839 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
841 VEC(constraint_edge_t,heap) *succvec = graph->succs[node];
842 VEC(constraint_edge_t,heap) *predvec = graph->preds[node];
845 constraint_edge_t c = NULL;
848 /* Walk the successors, erase the associated preds. */
850 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[node], 0, j, bi)
852 bitmap_clear_bit (graph->zero_weight_preds[j], node);
854 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
858 struct constraint_edge lookfor;
859 constraint_edge_t result;
862 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
863 &lookfor, constraint_edge_less);
864 result = VEC_ordered_remove (constraint_edge_t,
865 graph->preds[c->dest], place);
866 pool_free (constraint_edge_pool, result);
869 /* Walk the preds, erase the associated succs. */
871 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[node], 0, j, bi)
873 bitmap_clear_bit (graph->zero_weight_succs[j], node);
875 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
879 struct constraint_edge lookfor;
880 constraint_edge_t result;
883 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
884 &lookfor, constraint_edge_less);
885 result = VEC_ordered_remove (constraint_edge_t,
886 graph->succs[c->dest], place);
887 pool_free (constraint_edge_pool, result);
891 if (graph->zero_weight_preds[node])
893 BITMAP_FREE (graph->zero_weight_preds[node]);
894 graph->zero_weight_preds[node] = NULL;
897 if (graph->zero_weight_succs[node])
899 BITMAP_FREE (graph->zero_weight_succs[node]);
900 graph->zero_weight_succs[node] = NULL;
903 VEC_free (constraint_edge_t, heap, graph->preds[node]);
904 VEC_free (constraint_edge_t, heap, graph->succs[node]);
905 graph->preds[node] = NULL;
906 graph->succs[node] = NULL;
909 static bool edge_added = false;
911 /* Add edge (src, dest) to the graph. */
914 add_graph_edge (constraint_graph_t graph, unsigned int src, unsigned int dest)
917 VEC(constraint_edge_t,heap) *vec;
918 struct constraint_edge newe;
921 vec = graph->preds[src];
922 place = VEC_lower_bound (constraint_edge_t, vec, &newe,
923 constraint_edge_less);
924 if (place == VEC_length (constraint_edge_t, vec)
925 || VEC_index (constraint_edge_t, vec, place)->dest != dest)
927 constraint_edge_t edge = new_constraint_edge (dest);
929 VEC_safe_insert (constraint_edge_t, heap, graph->preds[src],
931 edge = new_constraint_edge (src);
933 place = VEC_lower_bound (constraint_edge_t, graph->succs[dest],
934 edge, constraint_edge_less);
935 VEC_safe_insert (constraint_edge_t, heap, graph->succs[dest],
946 /* Return the bitmap representing the weights of edge (SRC, DEST). */
949 get_graph_weights (constraint_graph_t graph, unsigned int src,
952 constraint_edge_t edge;
953 VEC(constraint_edge_t,heap) *vec;
954 struct constraint_edge lookfor;
958 vec = graph->preds[src];
959 edge = constraint_edge_vec_find (vec, lookfor);
960 gcc_assert (edge != NULL);
961 return &edge->weights;
964 /* Allocate graph weight bitmap for the edges associated with SRC and
965 DEST in GRAPH. Both the pred and the succ edges share a single
966 bitmap, so we need to set both edges to that bitmap. */
969 allocate_graph_weights (constraint_graph_t graph, unsigned int src,
973 constraint_edge_t edge;
974 VEC(constraint_edge_t,heap) *vec;
975 struct constraint_edge lookfor;
977 result = BITMAP_ALLOC (&ptabitmap_obstack);
979 /* Set the pred weight. */
981 vec = graph->preds[src];
982 edge = constraint_edge_vec_find (vec, lookfor);
983 gcc_assert (edge != NULL);
984 edge->weights = result;
986 /* Set the succ weight. */
988 vec = graph->succs[dest];
989 edge = constraint_edge_vec_find (vec, lookfor);
990 gcc_assert (edge != NULL);
991 edge->weights = result;
997 /* Merge GRAPH nodes FROM and TO into node TO. */
1000 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1003 VEC(constraint_edge_t,heap) *succvec = graph->succs[from];
1004 VEC(constraint_edge_t,heap) *predvec = graph->preds[from];
1006 constraint_edge_t c;
1010 /* Merge all the zero weighted predecessor edges. */
1011 if (graph->zero_weight_preds[from])
1013 if (!graph->zero_weight_preds[to])
1014 graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1016 EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_preds[from], 0, j, bi)
1020 bitmap_clear_bit (graph->zero_weight_succs[j], from);
1021 bitmap_set_bit (graph->zero_weight_succs[j], to);
1024 bitmap_ior_into (graph->zero_weight_preds[to],
1025 graph->zero_weight_preds[from]);
1028 /* Merge all the zero weighted successor edges. */
1029 if (graph->zero_weight_succs[from])
1031 if (!graph->zero_weight_succs[to])
1032 graph->zero_weight_succs[to] = BITMAP_ALLOC (&ptabitmap_obstack);
1033 EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_succs[from], 0, j, bi)
1035 bitmap_clear_bit (graph->zero_weight_preds[j], from);
1036 bitmap_set_bit (graph->zero_weight_preds[j], to);
1038 bitmap_ior_into (graph->zero_weight_succs[to],
1039 graph->zero_weight_succs[from]);
1042 /* Merge all the non-zero weighted predecessor edges. */
1043 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
1045 unsigned int d = c->dest;
1049 if (c->dest == from)
1052 add_graph_edge (graph, to, d);
1054 temp = *(get_graph_weights (graph, from, c->dest));
1057 weights = get_graph_weights (graph, to, d);
1059 *weights = allocate_graph_weights (graph, to, d);
1061 bitmap_ior_into (*weights, temp);
1066 /* Merge all the non-zero weighted successor edges. */
1067 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
1069 unsigned int d = c->dest;
1073 if (c->dest == from)
1076 add_graph_edge (graph, d, to);
1078 temp = *(get_graph_weights (graph, c->dest, from));
1081 weights = get_graph_weights (graph, d, to);
1083 *weights = allocate_graph_weights (graph, d, to);
1084 bitmap_ior_into (*weights, temp);
1087 clear_edges_for_node (graph, from);
1090 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
1091 it doesn't exist in the graph already.
1092 Return false if the edge already existed, true otherwise. */
1095 int_add_graph_edge (constraint_graph_t graph, unsigned int to,
1096 unsigned int from, unsigned HOST_WIDE_INT weight)
1098 if (to == from && weight == 0)
1108 if (!graph->zero_weight_preds[to])
1109 graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1110 if (!graph->zero_weight_succs[from])
1111 graph->zero_weight_succs[from] = BITMAP_ALLOC (&ptabitmap_obstack);
1112 if (!bitmap_bit_p (graph->zero_weight_succs[from], to))
1117 bitmap_set_bit (graph->zero_weight_preds[to], from);
1118 bitmap_set_bit (graph->zero_weight_succs[from], to);
1125 r = add_graph_edge (graph, to, from);
1126 weights = get_graph_weights (graph, to, from);
1131 *weights = allocate_graph_weights (graph, to, from);
1132 bitmap_set_bit (*weights, weight);
1136 r |= !bitmap_bit_p (*weights, weight);
1137 bitmap_set_bit (*weights, weight);
1146 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1149 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1152 struct constraint_edge lookfor;
1155 return (graph->zero_weight_succs[dest]
1156 && bitmap_bit_p (graph->zero_weight_succs[dest], src))
1157 || constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL;
1160 /* Return true if {DEST, SRC} is an existing weighted graph edge (IE has
1161 a weight other than 0) in GRAPH. */
1163 valid_weighted_graph_edge (constraint_graph_t graph, unsigned int src,
1166 struct constraint_edge lookfor;
1169 return graph->preds[src]
1170 && constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL;
1174 /* Build the constraint graph. */
1177 build_constraint_graph (void)
1182 graph = xmalloc (sizeof (struct constraint_graph));
1183 graph->succs = xcalloc (VEC_length (varinfo_t, varmap) + 1,
1184 sizeof (*graph->succs));
1185 graph->preds = xcalloc (VEC_length (varinfo_t, varmap) + 1,
1186 sizeof (*graph->preds));
1187 graph->zero_weight_succs = xcalloc (VEC_length (varinfo_t, varmap) + 1,
1188 sizeof (*graph->zero_weight_succs));
1189 graph->zero_weight_preds = xcalloc (VEC_length (varinfo_t, varmap) + 1,
1190 sizeof (*graph->zero_weight_preds));
1192 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1194 struct constraint_expr lhs = c->lhs;
1195 struct constraint_expr rhs = c->rhs;
1196 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
1197 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
1199 if (lhs.type == DEREF)
1201 /* *x = y or *x = &y (complex) */
1202 if (rhs.type == ADDRESSOF || rhsvar > anything_id)
1203 insert_into_complex (lhsvar, c);
1205 else if (rhs.type == DEREF)
1207 /* !special var= *y */
1208 if (!(get_varinfo (lhsvar)->is_special_var))
1209 insert_into_complex (rhsvar, c);
1211 else if (rhs.type == ADDRESSOF)
1214 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1216 else if (lhsvar > anything_id)
1218 /* Ignore 0 weighted self edges, as they can't possibly contribute
1220 if (lhsvar != rhsvar || rhs.offset != 0 || lhs.offset != 0)
1222 /* x = y (simple) */
1223 int_add_graph_edge (graph, lhs.var, rhs.var, rhs.offset);
1231 /* Changed variables on the last iteration. */
1232 static unsigned int changed_count;
1233 static sbitmap changed;
1235 DEF_VEC_I(unsigned);
1236 DEF_VEC_ALLOC_I(unsigned,heap);
1239 /* Strongly Connected Component visitation info. */
1244 sbitmap in_component;
1246 unsigned int *visited_index;
1247 VEC(unsigned,heap) *scc_stack;
1248 VEC(unsigned,heap) *unification_queue;
1252 /* Recursive routine to find strongly connected components in GRAPH.
1253 SI is the SCC info to store the information in, and N is the id of current
1254 graph node we are processing.
1256 This is Tarjan's strongly connected component finding algorithm, as
1257 modified by Nuutila to keep only non-root nodes on the stack.
1258 The algorithm can be found in "On finding the strongly connected
1259 connected components in a directed graph" by Esko Nuutila and Eljas
1260 Soisalon-Soininen, in Information Processing Letters volume 49,
1261 number 1, pages 9-14. */
1264 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1269 gcc_assert (get_varinfo (n)->node == n);
1270 SET_BIT (si->visited, n);
1271 RESET_BIT (si->in_component, n);
1272 si->visited_index[n] = si->current_index ++;
1274 /* Visit all the successors. */
1275 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[n], 0, i, bi)
1278 if (!TEST_BIT (si->visited, w))
1279 scc_visit (graph, si, w);
1280 if (!TEST_BIT (si->in_component, w))
1282 unsigned int t = get_varinfo (w)->node;
1283 unsigned int nnode = get_varinfo (n)->node;
1284 if (si->visited_index[t] < si->visited_index[nnode])
1285 get_varinfo (n)->node = t;
1289 /* See if any components have been identified. */
1290 if (get_varinfo (n)->node == n)
1292 unsigned int t = si->visited_index[n];
1293 SET_BIT (si->in_component, n);
1294 while (VEC_length (unsigned, si->scc_stack) != 0
1295 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1297 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1298 get_varinfo (w)->node = n;
1299 SET_BIT (si->in_component, w);
1300 /* Mark this node for collapsing. */
1301 VEC_safe_push (unsigned, heap, si->unification_queue, w);
1305 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1309 /* Collapse two variables into one variable. */
1312 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1314 bitmap tosol, fromsol;
1316 condense_varmap_nodes (to, from);
1317 tosol = get_varinfo (to)->solution;
1318 fromsol = get_varinfo (from)->solution;
1319 bitmap_ior_into (tosol, fromsol);
1320 merge_graph_nodes (graph, to, from);
1322 if (valid_graph_edge (graph, to, to))
1324 if (graph->zero_weight_preds[to])
1326 bitmap_clear_bit (graph->zero_weight_preds[to], to);
1327 bitmap_clear_bit (graph->zero_weight_succs[to], to);
1329 if (valid_weighted_graph_edge (graph, to, to))
1331 bitmap weights = *(get_graph_weights (graph, to, to));
1332 if (!weights || bitmap_empty_p (weights))
1333 erase_graph_self_edge (graph, to);
1336 BITMAP_FREE (fromsol);
1337 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1338 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1342 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1343 SI is the Strongly Connected Components information structure that tells us
1344 what components to unify.
1345 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1346 count should be updated to reflect the unification. */
1349 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1350 bool update_changed)
1353 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1356 /* We proceed as follows:
1358 For each component in the queue (components are delineated by
1359 when current_queue_element->node != next_queue_element->node):
1361 rep = representative node for component
1363 For each node (tounify) to be unified in the component,
1364 merge the solution for tounify into tmp bitmap
1366 clear solution for tounify
1368 merge edges from tounify into rep
1370 merge complex constraints from tounify into rep
1372 update changed count to note that tounify will never change
1375 Merge tmp into solution for rep, marking rep changed if this
1376 changed rep's solution.
1378 Delete any 0 weighted self-edges we now have for rep. */
1379 while (i != VEC_length (unsigned, si->unification_queue))
1381 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1382 unsigned int n = get_varinfo (tounify)->node;
1384 if (dump_file && (dump_flags & TDF_DETAILS))
1385 fprintf (dump_file, "Unifying %s to %s\n",
1386 get_varinfo (tounify)->name,
1387 get_varinfo (n)->name);
1389 stats.unified_vars_dynamic++;
1391 stats.unified_vars_static++;
1392 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1393 merge_graph_nodes (graph, n, tounify);
1394 condense_varmap_nodes (n, tounify);
1396 if (update_changed && TEST_BIT (changed, tounify))
1398 RESET_BIT (changed, tounify);
1399 if (!TEST_BIT (changed, n))
1400 SET_BIT (changed, n);
1403 gcc_assert (changed_count > 0);
1408 bitmap_clear (get_varinfo (tounify)->solution);
1411 /* If we've either finished processing the entire queue, or
1412 finished processing all nodes for component n, update the solution for
1414 if (i == VEC_length (unsigned, si->unification_queue)
1415 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1417 /* If the solution changes because of the merging, we need to mark
1418 the variable as changed. */
1419 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1421 if (update_changed && !TEST_BIT (changed, n))
1423 SET_BIT (changed, n);
1429 if (valid_graph_edge (graph, n, n))
1431 if (graph->zero_weight_succs[n])
1433 if (graph->zero_weight_preds[n])
1434 bitmap_clear_bit (graph->zero_weight_preds[n], n);
1435 bitmap_clear_bit (graph->zero_weight_succs[n], n);
1437 if (valid_weighted_graph_edge (graph, n, n))
1439 bitmap weights = *(get_graph_weights (graph, n, n));
1440 if (!weights || bitmap_empty_p (weights))
1441 erase_graph_self_edge (graph, n);
1450 /* Information needed to compute the topological ordering of a graph. */
1454 /* sbitmap of visited nodes. */
1456 /* Array that stores the topological order of the graph, *in
1458 VEC(unsigned,heap) *topo_order;
1462 /* Initialize and return a topological info structure. */
1464 static struct topo_info *
1465 init_topo_info (void)
1467 size_t size = VEC_length (varinfo_t, varmap);
1468 struct topo_info *ti = xmalloc (sizeof (struct topo_info));
1469 ti->visited = sbitmap_alloc (size);
1470 sbitmap_zero (ti->visited);
1471 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1476 /* Free the topological sort info pointed to by TI. */
1479 free_topo_info (struct topo_info *ti)
1481 sbitmap_free (ti->visited);
1482 VEC_free (unsigned, heap, ti->topo_order);
1486 /* Visit the graph in topological order, and store the order in the
1487 topo_info structure. */
1490 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1493 VEC(constraint_edge_t,heap) *succs = graph->succs[n];
1496 constraint_edge_t c;
1500 SET_BIT (ti->visited, n);
1501 if (VEC_length (constraint_edge_t, succs) != 0)
1503 temp = BITMAP_ALLOC (&iteration_obstack);
1504 if (graph->zero_weight_succs[n])
1505 bitmap_ior_into (temp, graph->zero_weight_succs[n]);
1506 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1507 bitmap_set_bit (temp, c->dest);
1510 temp = graph->zero_weight_succs[n];
1513 EXECUTE_IF_SET_IN_BITMAP (temp, 0, j, bi)
1515 if (!TEST_BIT (ti->visited, j))
1516 topo_visit (graph, ti, j);
1518 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1521 /* Return true if variable N + OFFSET is a legal field of N. */
1524 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1526 varinfo_t ninfo = get_varinfo (n);
1528 /* For things we've globbed to single variables, any offset into the
1529 variable acts like the entire variable, so that it becomes offset
1531 if (ninfo->is_special_var
1532 || ninfo->is_artificial_var
1533 || ninfo->is_unknown_size_var)
1538 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1541 #define DONT_PROPAGATE_WITH_ANYTHING 0
1543 /* Process a constraint C that represents *x = &y. */
1546 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1547 constraint_t c, bitmap delta)
1549 unsigned int rhs = c->rhs.var;
1553 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1554 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1556 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1557 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
1559 /* *x != NULL && *x != ANYTHING*/
1563 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1565 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1569 sol = get_varinfo (t)->solution;
1570 if (!bitmap_bit_p (sol, rhs))
1572 bitmap_set_bit (sol, rhs);
1573 if (!TEST_BIT (changed, t))
1575 SET_BIT (changed, t);
1580 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1581 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1586 /* Process a constraint C that represents x = *y, using DELTA as the
1587 starting solution. */
1590 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1593 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1595 bitmap sol = get_varinfo (lhs)->solution;
1599 #if DONT_PROPAGATE_WITH_ANYTHING
1600 if (bitmap_bit_p (delta, anything_id))
1602 flag = !bitmap_bit_p (sol, anything_id);
1604 bitmap_set_bit (sol, anything_id);
1608 /* For each variable j in delta (Sol(y)), add
1609 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1610 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1612 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1613 if (type_safe (j, &roffset))
1616 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1619 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1624 /* Adding edges from the special vars is pointless.
1625 They don't have sets that can change. */
1626 if (get_varinfo (t) ->is_special_var)
1627 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1628 else if (int_add_graph_edge (graph, lhs, t, 0))
1629 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1631 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1632 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1635 #if DONT_PROPAGATE_WITH_ANYTHING
1638 /* If the LHS solution changed, mark the var as changed. */
1641 get_varinfo (lhs)->solution = sol;
1642 if (!TEST_BIT (changed, lhs))
1644 SET_BIT (changed, lhs);
1650 /* Process a constraint C that represents *x = y. */
1653 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1655 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1656 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1657 bitmap sol = get_varinfo (rhs)->solution;
1661 #if DONT_PROPAGATE_WITH_ANYTHING
1662 if (bitmap_bit_p (sol, anything_id))
1664 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1666 varinfo_t jvi = get_varinfo (j);
1668 unsigned int loff = c->lhs.offset;
1669 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
1672 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1677 if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id))
1679 bitmap_set_bit (get_varinfo (t)->solution, anything_id);
1680 if (!TEST_BIT (changed, t))
1682 SET_BIT (changed, t);
1691 /* For each member j of delta (Sol(x)), add an edge from y to j and
1692 union Sol(y) into Sol(j) */
1693 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1695 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1696 if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var))
1700 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1702 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1706 if (int_add_graph_edge (graph, t, rhs, roff))
1708 bitmap tmp = get_varinfo (t)->solution;
1709 if (set_union_with_increment (tmp, sol, roff))
1711 get_varinfo (t)->solution = tmp;
1713 sol = get_varinfo (rhs)->solution;
1714 if (!TEST_BIT (changed, t))
1716 SET_BIT (changed, t);
1722 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1723 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1727 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1728 constraint (IE *x = &y, x = *y, and *x = y). */
1731 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1733 if (c->lhs.type == DEREF)
1735 if (c->rhs.type == ADDRESSOF)
1738 do_da_constraint (graph, c, delta);
1743 do_ds_constraint (graph, c, delta);
1749 if (!(get_varinfo (c->lhs.var)->is_special_var))
1750 do_sd_constraint (graph, c, delta);
1754 /* Initialize and return a new SCC info structure. */
1756 static struct scc_info *
1757 init_scc_info (void)
1759 struct scc_info *si = xmalloc (sizeof (struct scc_info));
1760 size_t size = VEC_length (varinfo_t, varmap);
1762 si->current_index = 0;
1763 si->visited = sbitmap_alloc (size);
1764 sbitmap_zero (si->visited);
1765 si->in_component = sbitmap_alloc (size);
1766 sbitmap_ones (si->in_component);
1767 si->visited_index = xcalloc (sizeof (unsigned int), size + 1);
1768 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1769 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1773 /* Free an SCC info structure pointed to by SI */
1776 free_scc_info (struct scc_info *si)
1778 sbitmap_free (si->visited);
1779 sbitmap_free (si->in_component);
1780 free (si->visited_index);
1781 VEC_free (unsigned, heap, si->scc_stack);
1782 VEC_free (unsigned, heap, si->unification_queue);
1787 /* Find cycles in GRAPH that occur, using strongly connected components, and
1788 collapse the cycles into a single representative node. if UPDATE_CHANGED
1789 is true, then update the changed sbitmap to note those nodes whose
1790 solutions have changed as a result of collapsing. */
1793 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1796 unsigned int size = VEC_length (varinfo_t, varmap);
1797 struct scc_info *si = init_scc_info ();
1799 for (i = 0; i != size; ++i)
1800 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1801 scc_visit (graph, si, i);
1803 process_unification_queue (graph, si, update_changed);
1807 /* Compute a topological ordering for GRAPH, and store the result in the
1808 topo_info structure TI. */
1811 compute_topo_order (constraint_graph_t graph,
1812 struct topo_info *ti)
1815 unsigned int size = VEC_length (varinfo_t, varmap);
1817 for (i = 0; i != size; ++i)
1818 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1819 topo_visit (graph, ti, i);
1822 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1825 bitmap_other_than_zero_bit_set (bitmap b)
1830 if (bitmap_empty_p (b))
1832 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1837 /* Perform offline variable substitution.
1839 This is a linear time way of identifying variables that must have
1840 equivalent points-to sets, including those caused by static cycles,
1841 and single entry subgraphs, in the constraint graph.
1843 The technique is described in "Off-line variable substitution for
1844 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1845 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1848 perform_var_substitution (constraint_graph_t graph)
1850 struct topo_info *ti = init_topo_info ();
1852 bitmap_obstack_initialize (&iteration_obstack);
1853 /* Compute the topological ordering of the graph, then visit each
1854 node in topological order. */
1855 compute_topo_order (graph, ti);
1857 while (VEC_length (unsigned, ti->topo_order) != 0)
1859 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1861 varinfo_t vi = get_varinfo (i);
1862 bool okay_to_elim = false;
1863 unsigned int root = VEC_length (varinfo_t, varmap);
1864 VEC(constraint_edge_t,heap) *predvec = graph->preds[i];
1865 constraint_edge_t ce = NULL;
1870 /* We can't eliminate things whose address is taken, or which is
1871 the target of a dereference. */
1872 if (vi->address_taken || vi->indirect_target)
1875 /* See if all predecessors of I are ripe for elimination */
1876 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[i], 0, k, bi)
1879 w = get_varinfo (k)->node;
1881 /* We can't eliminate the node if one of the predecessors is
1882 part of a different strongly connected component. */
1886 okay_to_elim = true;
1890 okay_to_elim = false;
1894 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1895 then Solution(i) is a subset of Solution (w), where w is a
1896 predecessor in the graph.
1897 Corollary: If all predecessors of i have the same
1898 points-to set, then i has that same points-to set as
1899 those predecessors. */
1900 tmp = BITMAP_ALLOC (NULL);
1901 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1902 get_varinfo (w)->solution);
1903 if (!bitmap_empty_p (tmp))
1905 okay_to_elim = false;
1914 VEC_iterate (constraint_edge_t, predvec, pred, ce);
1919 weight = *(get_graph_weights (graph, i, ce->dest));
1921 /* We can't eliminate variables that have nonzero weighted
1922 edges between them. */
1923 if (weight && bitmap_other_than_zero_bit_set (weight))
1925 okay_to_elim = false;
1928 w = get_varinfo (ce->dest)->node;
1930 /* We can't eliminate the node if one of the predecessors is
1931 part of a different strongly connected component. */
1935 okay_to_elim = true;
1939 okay_to_elim = false;
1943 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1944 then Solution(i) is a subset of Solution (w), where w is a
1945 predecessor in the graph.
1946 Corollary: If all predecessors of i have the same
1947 points-to set, then i has that same points-to set as
1948 those predecessors. */
1949 tmp = BITMAP_ALLOC (NULL);
1950 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1951 get_varinfo (w)->solution);
1952 if (!bitmap_empty_p (tmp))
1954 okay_to_elim = false;
1961 /* See if the root is different than the original node.
1962 If so, we've found an equivalence. */
1963 if (root != get_varinfo (i)->node && okay_to_elim)
1965 /* Found an equivalence */
1966 get_varinfo (i)->node = root;
1967 collapse_nodes (graph, root, i);
1968 if (dump_file && (dump_flags & TDF_DETAILS))
1969 fprintf (dump_file, "Collapsing %s into %s\n",
1970 get_varinfo (i)->name,
1971 get_varinfo (root)->name);
1972 stats.collapsed_vars++;
1976 bitmap_obstack_release (&iteration_obstack);
1977 free_topo_info (ti);
1980 /* Solve the constraint graph GRAPH using our worklist solver.
1981 This is based on the PW* family of solvers from the "Efficient Field
1982 Sensitive Pointer Analysis for C" paper.
1983 It works by iterating over all the graph nodes, processing the complex
1984 constraints and propagating the copy constraints, until everything stops
1985 changed. This corresponds to steps 6-8 in the solving list given above. */
1988 solve_graph (constraint_graph_t graph)
1990 unsigned int size = VEC_length (varinfo_t, varmap);
1993 changed_count = size;
1994 changed = sbitmap_alloc (size);
1995 sbitmap_ones (changed);
1997 /* The already collapsed/unreachable nodes will never change, so we
1998 need to account for them in changed_count. */
1999 for (i = 0; i < size; i++)
2000 if (get_varinfo (i)->node != i)
2003 while (changed_count > 0)
2006 struct topo_info *ti = init_topo_info ();
2009 bitmap_obstack_initialize (&iteration_obstack);
2013 /* We already did cycle elimination once, when we did
2014 variable substitution, so we don't need it again for the
2016 if (stats.iterations > 1)
2017 find_and_collapse_graph_cycles (graph, true);
2022 compute_topo_order (graph, ti);
2024 while (VEC_length (unsigned, ti->topo_order) != 0)
2026 i = VEC_pop (unsigned, ti->topo_order);
2027 gcc_assert (get_varinfo (i)->node == i);
2029 /* If the node has changed, we need to process the
2030 complex constraints and outgoing edges again. */
2031 if (TEST_BIT (changed, i))
2035 constraint_edge_t e = NULL;
2038 VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
2039 VEC(constraint_edge_t,heap) *succs;
2041 RESET_BIT (changed, i);
2044 /* Process the complex constraints */
2045 solution = get_varinfo (i)->solution;
2046 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2047 do_complex_constraint (graph, c, solution);
2049 /* Propagate solution to all successors. */
2050 succs = graph->succs[i];
2052 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[i], 0, j, bi)
2054 bitmap tmp = get_varinfo (j)->solution;
2057 flag = set_union_with_increment (tmp, solution, 0);
2061 get_varinfo (j)->solution = tmp;
2062 if (!TEST_BIT (changed, j))
2064 SET_BIT (changed, j);
2069 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
2071 bitmap tmp = get_varinfo (e->dest)->solution;
2074 bitmap weights = e->weights;
2077 gcc_assert (weights && !bitmap_empty_p (weights));
2078 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
2079 flag |= set_union_with_increment (tmp, solution, k);
2083 get_varinfo (e->dest)->solution = tmp;
2084 if (!TEST_BIT (changed, e->dest))
2086 SET_BIT (changed, e->dest);
2093 free_topo_info (ti);
2094 bitmap_obstack_release (&iteration_obstack);
2097 sbitmap_free (changed);
2101 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
2103 /* Map from trees to variable ids. */
2104 static htab_t id_for_tree;
2106 typedef struct tree_id
2112 /* Hash a tree id structure. */
2115 tree_id_hash (const void *p)
2117 const tree_id_t ta = (tree_id_t) p;
2118 return htab_hash_pointer (ta->t);
2121 /* Return true if the tree in P1 and the tree in P2 are the same. */
2124 tree_id_eq (const void *p1, const void *p2)
2126 const tree_id_t ta1 = (tree_id_t) p1;
2127 const tree_id_t ta2 = (tree_id_t) p2;
2128 return ta1->t == ta2->t;
2131 /* Insert ID as the variable id for tree T in the hashtable. */
2134 insert_id_for_tree (tree t, int id)
2137 struct tree_id finder;
2141 slot = htab_find_slot (id_for_tree, &finder, INSERT);
2142 gcc_assert (*slot == NULL);
2143 new_pair = xmalloc (sizeof (struct tree_id));
2146 *slot = (void *)new_pair;
2149 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
2150 exist in the hash table, return false, otherwise, return true and
2151 set *ID to the id we found. */
2154 lookup_id_for_tree (tree t, unsigned int *id)
2157 struct tree_id finder;
2160 pair = htab_find (id_for_tree, &finder);
2167 /* Return a printable name for DECL */
2170 alias_get_name (tree decl)
2172 const char *res = get_name (decl);
2174 int num_printed = 0;
2180 if (TREE_CODE (decl) == SSA_NAME)
2182 num_printed = asprintf (&temp, "%s_%u",
2183 alias_get_name (SSA_NAME_VAR (decl)),
2184 SSA_NAME_VERSION (decl));
2186 else if (DECL_P (decl))
2188 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2190 if (num_printed > 0)
2192 res = ggc_strdup (temp);
2198 /* Find the variable id for tree T in the hashtable.
2199 If T doesn't exist in the hash table, create an entry for it. */
2202 get_id_for_tree (tree t)
2205 struct tree_id finder;
2208 pair = htab_find (id_for_tree, &finder);
2210 return create_variable_info_for (t, alias_get_name (t));
2215 /* Get a constraint expression from an SSA_VAR_P node. */
2217 static struct constraint_expr
2218 get_constraint_exp_from_ssa_var (tree t)
2220 struct constraint_expr cexpr;
2222 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2224 /* For parameters, get at the points-to set for the actual parm
2226 if (TREE_CODE (t) == SSA_NAME
2227 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2228 && default_def (SSA_NAME_VAR (t)) == t)
2229 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
2231 cexpr.type = SCALAR;
2233 cexpr.var = get_id_for_tree (t);
2234 /* If we determine the result is "anything", and we know this is readonly,
2235 say it points to readonly memory instead. */
2236 if (cexpr.var == anything_id && TREE_READONLY (t))
2238 cexpr.type = ADDRESSOF;
2239 cexpr.var = readonly_id;
2246 /* Process a completed constraint T, and add it to the constraint
2250 process_constraint (constraint_t t)
2252 struct constraint_expr rhs = t->rhs;
2253 struct constraint_expr lhs = t->lhs;
2255 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2256 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2258 /* ANYTHING == ANYTHING is pointless. */
2259 if (lhs.var == anything_id && rhs.var == anything_id)
2262 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2263 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
2268 process_constraint (t);
2270 /* This can happen in our IR with things like n->a = *p */
2271 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2273 /* Split into tmp = *rhs, *lhs = tmp */
2274 tree rhsdecl = get_varinfo (rhs.var)->decl;
2275 tree pointertype = TREE_TYPE (rhsdecl);
2276 tree pointedtotype = TREE_TYPE (pointertype);
2277 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2278 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2280 /* If this is an aggregate of known size, we should have passed
2281 this off to do_structure_copy, and it should have broken it
2283 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
2284 || get_varinfo (rhs.var)->is_unknown_size_var);
2286 process_constraint (new_constraint (tmplhs, rhs));
2287 process_constraint (new_constraint (lhs, tmplhs));
2289 else if (rhs.type == ADDRESSOF)
2292 gcc_assert (rhs.offset == 0);
2294 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
2295 vi->address_taken = true;
2297 VEC_safe_push (constraint_t, heap, constraints, t);
2301 if (lhs.type != DEREF && rhs.type == DEREF)
2302 get_varinfo (lhs.var)->indirect_target = true;
2303 VEC_safe_push (constraint_t, heap, constraints, t);
2308 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2311 static unsigned HOST_WIDE_INT
2312 bitpos_of_field (const tree fdecl)
2315 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
2316 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
2319 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
2320 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
2324 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2325 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2328 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
2329 const unsigned HOST_WIDE_INT fieldsize,
2330 const unsigned HOST_WIDE_INT accesspos,
2331 const unsigned HOST_WIDE_INT accesssize)
2333 if (fieldpos == accesspos && fieldsize == accesssize)
2335 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
2337 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2343 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2346 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
2350 HOST_WIDE_INT bitsize = -1;
2351 HOST_WIDE_INT bitpos;
2352 tree offset = NULL_TREE;
2353 enum machine_mode mode;
2357 struct constraint_expr *result;
2358 unsigned int beforelength = VEC_length (ce_s, *results);
2360 /* Some people like to do cute things like take the address of
2363 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2364 forzero = TREE_OPERAND (forzero, 0);
2366 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2368 struct constraint_expr temp;
2371 temp.var = integer_id;
2373 VEC_safe_push (ce_s, heap, *results, &temp);
2377 t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode,
2378 &unsignedp, &volatilep, false);
2379 get_constraint_for (t, results, anyoffset);
2380 result = VEC_last (ce_s, *results);
2382 gcc_assert (beforelength + 1 == VEC_length (ce_s, *results));
2384 /* This can also happen due to weird offsetof type macros. */
2385 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2386 result->type = SCALAR;
2388 /* If we know where this goes, then yay. Otherwise, booo. */
2390 if (offset == NULL && bitsize != -1)
2392 result->offset = bitpos;
2394 /* FIXME: Handle the DEREF case. */
2395 else if (anyoffset && result->type != DEREF)
2402 result->var = anything_id;
2406 if (result->type == SCALAR)
2408 /* In languages like C, you can access one past the end of an
2409 array. You aren't allowed to dereference it, so we can
2410 ignore this constraint. When we handle pointer subtraction,
2411 we may have to do something cute here. */
2413 if (result->offset < get_varinfo (result->var)->fullsize)
2415 /* It's also not true that the constraint will actually start at the
2416 right offset, it may start in some padding. We only care about
2417 setting the constraint to the first actual field it touches, so
2420 for (curr = get_varinfo (result->var); curr; curr = curr->next)
2422 if (offset_overlaps_with_access (curr->offset, curr->size,
2423 result->offset, bitsize))
2425 result->var = curr->id;
2429 /* assert that we found *some* field there. The user couldn't be
2430 accessing *only* padding. */
2431 /* Still the user could access one past the end of an array
2432 embedded in a struct resulting in accessing *only* padding. */
2433 gcc_assert (curr || ref_contains_array_ref (orig_t));
2436 if (dump_file && (dump_flags & TDF_DETAILS))
2437 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2444 /* Dereference the constraint expression CONS, and return the result.
2445 DEREF (ADDRESSOF) = SCALAR
2446 DEREF (SCALAR) = DEREF
2447 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2448 This is needed so that we can handle dereferencing DEREF constraints. */
2451 do_deref (VEC (ce_s, heap) **constraints)
2453 struct constraint_expr *c;
2455 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2457 if (c->type == SCALAR)
2459 else if (c->type == ADDRESSOF)
2461 else if (c->type == DEREF)
2463 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
2464 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2465 process_constraint (new_constraint (tmplhs, *c));
2466 c->var = tmplhs.var;
2474 /* Given a tree T, return the constraint expression for it. */
2477 get_constraint_for (tree t, VEC (ce_s, heap) **results, bool *anyoffset)
2479 struct constraint_expr temp;
2481 /* x = integer is all glommed to a single variable, which doesn't
2482 point to anything by itself. That is, of course, unless it is an
2483 integer constant being treated as a pointer, in which case, we
2484 will return that this is really the addressof anything. This
2485 happens below, since it will fall into the default case. The only
2486 case we know something about an integer treated like a pointer is
2487 when it is the NULL pointer, and then we just say it points to
2489 if (TREE_CODE (t) == INTEGER_CST
2490 && !POINTER_TYPE_P (TREE_TYPE (t)))
2492 temp.var = integer_id;
2495 VEC_safe_push (ce_s, heap, *results, &temp);
2498 else if (TREE_CODE (t) == INTEGER_CST
2499 && integer_zerop (t))
2501 temp.var = nothing_id;
2502 temp.type = ADDRESSOF;
2504 VEC_safe_push (ce_s, heap, *results, &temp);
2508 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2510 case tcc_expression:
2512 switch (TREE_CODE (t))
2516 struct constraint_expr *c;
2519 get_constraint_for (TREE_OPERAND (t, 0), results, anyoffset);
2520 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2522 if (c->type == DEREF)
2525 c->type = ADDRESSOF;
2532 /* XXX: In interprocedural mode, if we didn't have the
2533 body, we would need to do *each pointer argument =
2535 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2538 tree heapvar = heapvar_lookup (t);
2540 if (heapvar == NULL)
2542 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2543 DECL_EXTERNAL (heapvar) = 1;
2544 add_referenced_tmp_var (heapvar);
2545 heapvar_insert (t, heapvar);
2548 temp.var = create_variable_info_for (heapvar,
2549 alias_get_name (heapvar));
2551 vi = get_varinfo (temp.var);
2552 vi->is_artificial_var = 1;
2553 vi->is_heap_var = 1;
2554 temp.type = ADDRESSOF;
2556 VEC_safe_push (ce_s, heap, *results, &temp);
2562 temp.type = ADDRESSOF;
2563 temp.var = anything_id;
2565 VEC_safe_push (ce_s, heap, *results, &temp);
2572 switch (TREE_CODE (t))
2576 get_constraint_for (TREE_OPERAND (t, 0), results, anyoffset);
2581 case ARRAY_RANGE_REF:
2583 get_constraint_for_component_ref (t, results, anyoffset);
2587 temp.type = ADDRESSOF;
2588 temp.var = anything_id;
2590 VEC_safe_push (ce_s, heap, *results, &temp);
2597 switch (TREE_CODE (t))
2601 case NON_LVALUE_EXPR:
2603 tree op = TREE_OPERAND (t, 0);
2605 /* Cast from non-pointer to pointers are bad news for us.
2606 Anything else, we see through */
2607 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2608 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2610 get_constraint_for (op, results, anyoffset);
2618 temp.type = ADDRESSOF;
2619 temp.var = anything_id;
2621 VEC_safe_push (ce_s, heap, *results, &temp);
2626 case tcc_exceptional:
2628 switch (TREE_CODE (t))
2632 get_constraint_for (PHI_RESULT (t), results, anyoffset);
2638 struct constraint_expr temp;
2639 temp = get_constraint_exp_from_ssa_var (t);
2640 VEC_safe_push (ce_s, heap, *results, &temp);
2646 temp.type = ADDRESSOF;
2647 temp.var = anything_id;
2649 VEC_safe_push (ce_s, heap, *results, &temp);
2654 case tcc_declaration:
2656 struct constraint_expr temp;
2657 temp = get_constraint_exp_from_ssa_var (t);
2658 VEC_safe_push (ce_s, heap, *results, &temp);
2663 temp.type = ADDRESSOF;
2664 temp.var = anything_id;
2666 VEC_safe_push (ce_s, heap, *results, &temp);
2673 /* Handle the structure copy case where we have a simple structure copy
2674 between LHS and RHS that is of SIZE (in bits)
2676 For each field of the lhs variable (lhsfield)
2677 For each field of the rhs variable at lhsfield.offset (rhsfield)
2678 add the constraint lhsfield = rhsfield
2680 If we fail due to some kind of type unsafety or other thing we
2681 can't handle, return false. We expect the caller to collapse the
2682 variable in that case. */
2685 do_simple_structure_copy (const struct constraint_expr lhs,
2686 const struct constraint_expr rhs,
2687 const unsigned HOST_WIDE_INT size)
2689 varinfo_t p = get_varinfo (lhs.var);
2690 unsigned HOST_WIDE_INT pstart, last;
2692 last = p->offset + size;
2693 for (; p && p->offset < last; p = p->next)
2696 struct constraint_expr templhs = lhs;
2697 struct constraint_expr temprhs = rhs;
2698 unsigned HOST_WIDE_INT fieldoffset;
2700 templhs.var = p->id;
2701 q = get_varinfo (temprhs.var);
2702 fieldoffset = p->offset - pstart;
2703 q = first_vi_for_offset (q, q->offset + fieldoffset);
2706 temprhs.var = q->id;
2707 process_constraint (new_constraint (templhs, temprhs));
2713 /* Handle the structure copy case where we have a structure copy between a
2714 aggregate on the LHS and a dereference of a pointer on the RHS
2715 that is of SIZE (in bits)
2717 For each field of the lhs variable (lhsfield)
2718 rhs.offset = lhsfield->offset
2719 add the constraint lhsfield = rhs
2723 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2724 const struct constraint_expr rhs,
2725 const unsigned HOST_WIDE_INT size)
2727 varinfo_t p = get_varinfo (lhs.var);
2728 unsigned HOST_WIDE_INT pstart,last;
2730 last = p->offset + size;
2732 for (; p && p->offset < last; p = p->next)
2735 struct constraint_expr templhs = lhs;
2736 struct constraint_expr temprhs = rhs;
2737 unsigned HOST_WIDE_INT fieldoffset;
2740 if (templhs.type == SCALAR)
2741 templhs.var = p->id;
2743 templhs.offset = p->offset;
2745 q = get_varinfo (temprhs.var);
2746 fieldoffset = p->offset - pstart;
2747 temprhs.offset += fieldoffset;
2748 process_constraint (new_constraint (templhs, temprhs));
2752 /* Handle the structure copy case where we have a structure copy
2753 between a aggregate on the RHS and a dereference of a pointer on
2754 the LHS that is of SIZE (in bits)
2756 For each field of the rhs variable (rhsfield)
2757 lhs.offset = rhsfield->offset
2758 add the constraint lhs = rhsfield
2762 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2763 const struct constraint_expr rhs,
2764 const unsigned HOST_WIDE_INT size)
2766 varinfo_t p = get_varinfo (rhs.var);
2767 unsigned HOST_WIDE_INT pstart,last;
2769 last = p->offset + size;
2771 for (; p && p->offset < last; p = p->next)
2774 struct constraint_expr templhs = lhs;
2775 struct constraint_expr temprhs = rhs;
2776 unsigned HOST_WIDE_INT fieldoffset;
2779 if (temprhs.type == SCALAR)
2780 temprhs.var = p->id;
2782 temprhs.offset = p->offset;
2784 q = get_varinfo (templhs.var);
2785 fieldoffset = p->offset - pstart;
2786 templhs.offset += fieldoffset;
2787 process_constraint (new_constraint (templhs, temprhs));
2791 /* Sometimes, frontends like to give us bad type information. This
2792 function will collapse all the fields from VAR to the end of VAR,
2793 into VAR, so that we treat those fields as a single variable.
2794 We return the variable they were collapsed into. */
2797 collapse_rest_of_var (unsigned int var)
2799 varinfo_t currvar = get_varinfo (var);
2802 for (field = currvar->next; field; field = field->next)
2805 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
2806 field->name, currvar->name);
2808 gcc_assert (!field->collapsed_to);
2809 field->collapsed_to = currvar;
2812 currvar->next = NULL;
2813 currvar->size = currvar->fullsize - currvar->offset;
2818 /* Handle aggregate copies by expanding into copies of the respective
2819 fields of the structures. */
2822 do_structure_copy (tree lhsop, tree rhsop)
2824 struct constraint_expr lhs, rhs, tmp;
2825 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
2827 unsigned HOST_WIDE_INT lhssize;
2828 unsigned HOST_WIDE_INT rhssize;
2830 get_constraint_for (lhsop, &lhsc, NULL);
2831 get_constraint_for (rhsop, &rhsc, NULL);
2832 gcc_assert (VEC_length (ce_s, lhsc) == 1);
2833 gcc_assert (VEC_length (ce_s, rhsc) == 1);
2834 lhs = *(VEC_last (ce_s, lhsc));
2835 rhs = *(VEC_last (ce_s, rhsc));
2837 VEC_free (ce_s, heap, lhsc);
2838 VEC_free (ce_s, heap, rhsc);
2840 /* If we have special var = x, swap it around. */
2841 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2848 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2849 possible it's something we could handle. However, most cases falling
2850 into this are dealing with transparent unions, which are slightly
2852 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2854 rhs.type = ADDRESSOF;
2855 rhs.var = anything_id;
2858 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2859 that special var. */
2860 if (rhs.var <= integer_id)
2862 for (p = get_varinfo (lhs.var); p; p = p->next)
2864 struct constraint_expr templhs = lhs;
2865 struct constraint_expr temprhs = rhs;
2867 if (templhs.type == SCALAR )
2868 templhs.var = p->id;
2870 templhs.offset += p->offset;
2871 process_constraint (new_constraint (templhs, temprhs));
2876 tree rhstype = TREE_TYPE (rhsop);
2877 tree lhstype = TREE_TYPE (lhsop);
2881 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
2882 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
2884 /* If we have a variably sized types on the rhs or lhs, and a deref
2885 constraint, add the constraint, lhsconstraint = &ANYTHING.
2886 This is conservatively correct because either the lhs is an unknown
2887 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2888 constraint, and every variable it can point to must be unknown sized
2889 anyway, so we don't need to worry about fields at all. */
2890 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2891 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2893 rhs.var = anything_id;
2894 rhs.type = ADDRESSOF;
2896 process_constraint (new_constraint (lhs, rhs));
2900 /* The size only really matters insofar as we don't set more or less of
2901 the variable. If we hit an unknown size var, the size should be the
2902 whole darn thing. */
2903 if (get_varinfo (rhs.var)->is_unknown_size_var)
2906 rhssize = TREE_INT_CST_LOW (rhstypesize);
2908 if (get_varinfo (lhs.var)->is_unknown_size_var)
2911 lhssize = TREE_INT_CST_LOW (lhstypesize);
2914 if (rhs.type == SCALAR && lhs.type == SCALAR)
2916 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
2918 lhs.var = collapse_rest_of_var (lhs.var);
2919 rhs.var = collapse_rest_of_var (rhs.var);
2924 process_constraint (new_constraint (lhs, rhs));
2927 else if (lhs.type != DEREF && rhs.type == DEREF)
2928 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2929 else if (lhs.type == DEREF && rhs.type != DEREF)
2930 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2933 tree pointedtotype = lhstype;
2936 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2937 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2938 do_structure_copy (tmpvar, rhsop);
2939 do_structure_copy (lhsop, tmpvar);
2944 /* Update related alias information kept in AI. This is used when
2945 building name tags, alias sets and deciding grouping heuristics.
2946 STMT is the statement to process. This function also updates
2947 ADDRESSABLE_VARS. */
2950 update_alias_info (tree stmt, struct alias_info *ai)
2953 use_operand_p use_p;
2955 bool stmt_escapes_p = is_escape_site (stmt, ai);
2958 /* Mark all the variables whose address are taken by the statement. */
2959 addr_taken = addresses_taken (stmt);
2962 bitmap_ior_into (addressable_vars, addr_taken);
2964 /* If STMT is an escape point, all the addresses taken by it are
2971 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
2972 mark_call_clobbered (referenced_var (i));
2976 /* Process each operand use. If an operand may be aliased, keep
2977 track of how many times it's being used. For pointers, determine
2978 whether they are dereferenced by the statement, or whether their
2979 value escapes, etc. */
2980 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2984 struct ptr_info_def *pi;
2985 bool is_store, is_potential_deref;
2986 unsigned num_uses, num_derefs;
2988 op = USE_FROM_PTR (use_p);
2990 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2991 to the set of addressable variables. */
2992 if (TREE_CODE (op) == ADDR_EXPR)
2994 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
2996 /* PHI nodes don't have annotations for pinning the set
2997 of addresses taken, so we collect them here.
2999 FIXME, should we allow PHI nodes to have annotations
3000 so that they can be treated like regular statements?
3001 Currently, they are treated as second-class
3003 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
3007 /* Ignore constants. */
3008 if (TREE_CODE (op) != SSA_NAME)
3011 var = SSA_NAME_VAR (op);
3012 v_ann = var_ann (var);
3014 /* If the operand's variable may be aliased, keep track of how
3015 many times we've referenced it. This is used for alias
3016 grouping in compute_flow_insensitive_aliasing. */
3017 if (may_be_aliased (var))
3018 NUM_REFERENCES_INC (v_ann);
3020 /* We are only interested in pointers. */
3021 if (!POINTER_TYPE_P (TREE_TYPE (op)))
3024 pi = get_ptr_info (op);
3026 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3027 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
3029 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
3030 VARRAY_PUSH_TREE (ai->processed_ptrs, op);
3033 /* If STMT is a PHI node, then it will not have pointer
3034 dereferences and it will not be an escape point. */
3035 if (TREE_CODE (stmt) == PHI_NODE)
3038 /* Determine whether OP is a dereferenced pointer, and if STMT
3039 is an escape point, whether OP escapes. */
3040 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
3042 /* Handle a corner case involving address expressions of the
3043 form '&PTR->FLD'. The problem with these expressions is that
3044 they do not represent a dereference of PTR. However, if some
3045 other transformation propagates them into an INDIRECT_REF
3046 expression, we end up with '*(&PTR->FLD)' which is folded
3049 So, if the original code had no other dereferences of PTR,
3050 the aliaser will not create memory tags for it, and when
3051 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3052 memory operations will receive no V_MAY_DEF/VUSE operands.
3054 One solution would be to have count_uses_and_derefs consider
3055 &PTR->FLD a dereference of PTR. But that is wrong, since it
3056 is not really a dereference but an offset calculation.
3058 What we do here is to recognize these special ADDR_EXPR
3059 nodes. Since these expressions are never GIMPLE values (they
3060 are not GIMPLE invariants), they can only appear on the RHS
3061 of an assignment and their base address is always an
3062 INDIRECT_REF expression. */
3063 is_potential_deref = false;
3064 if (TREE_CODE (stmt) == MODIFY_EXPR
3065 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
3066 && !is_gimple_val (TREE_OPERAND (stmt, 1)))
3068 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3069 this represents a potential dereference of PTR. */
3070 tree rhs = TREE_OPERAND (stmt, 1);
3071 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3072 if (TREE_CODE (base) == INDIRECT_REF
3073 && TREE_OPERAND (base, 0) == op)
3074 is_potential_deref = true;
3077 if (num_derefs > 0 || is_potential_deref)
3079 /* Mark OP as dereferenced. In a subsequent pass,
3080 dereferenced pointers that point to a set of
3081 variables will be assigned a name tag to alias
3082 all the variables OP points to. */
3083 pi->is_dereferenced = 1;
3085 /* Keep track of how many time we've dereferenced each
3087 NUM_REFERENCES_INC (v_ann);
3089 /* If this is a store operation, mark OP as being
3090 dereferenced to store, otherwise mark it as being
3091 dereferenced to load. */
3093 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3095 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
3098 if (stmt_escapes_p && num_derefs < num_uses)
3100 /* If STMT is an escape point and STMT contains at
3101 least one direct use of OP, then the value of OP
3102 escapes and so the pointed-to variables need to
3103 be marked call-clobbered. */
3104 pi->value_escapes_p = 1;
3106 /* If the statement makes a function call, assume
3107 that pointer OP will be dereferenced in a store
3108 operation inside the called function. */
3109 if (get_call_expr_in (stmt))
3111 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3112 pi->is_dereferenced = 1;
3117 if (TREE_CODE (stmt) == PHI_NODE)
3120 /* Update reference counter for definitions to any
3121 potentially aliased variable. This is used in the alias
3122 grouping heuristics. */
3123 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3125 tree var = SSA_NAME_VAR (op);
3126 var_ann_t ann = var_ann (var);
3127 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3128 if (may_be_aliased (var))
3129 NUM_REFERENCES_INC (ann);
3133 /* Mark variables in V_MAY_DEF operands as being written to. */
3134 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
3136 tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
3137 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3142 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3143 Expressions of the type PTR + CST can be handled in two ways:
3145 1- If the constraint for PTR is ADDRESSOF for a non-structure
3146 variable, then we can use it directly because adding or
3147 subtracting a constant may not alter the original ADDRESSOF
3148 constraint (i.e., pointer arithmetic may not legally go outside
3149 an object's boundaries).
3151 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3152 then if CST is a compile-time constant that can be used as an
3153 offset, we can determine which sub-variable will be pointed-to
3156 Return true if the expression is handled. For any other kind of
3157 expression, return false so that each operand can be added as a
3158 separate constraint by the caller. */
3161 handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr)
3164 struct constraint_expr *c, *c2;
3167 VEC (ce_s, heap) *temp = NULL;
3168 unsigned int rhsoffset = 0;
3170 if (TREE_CODE (expr) != PLUS_EXPR)
3173 op0 = TREE_OPERAND (expr, 0);
3174 op1 = TREE_OPERAND (expr, 1);
3176 get_constraint_for (op0, &temp, NULL);
3177 if (POINTER_TYPE_P (TREE_TYPE (op0))
3178 && TREE_CODE (TREE_TYPE (TREE_TYPE (op0))) == RECORD_TYPE
3179 && TREE_CODE (op1) == INTEGER_CST)
3181 rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
3185 for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
3186 for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
3188 if (c2->type == ADDRESSOF && rhsoffset != 0)
3190 varinfo_t temp = get_varinfo (c2->var);
3192 gcc_assert (first_vi_for_offset (temp, rhsoffset) != NULL);
3193 c2->var = first_vi_for_offset (temp, rhsoffset)->id;
3197 c2->offset = rhsoffset;
3198 process_constraint (new_constraint (*c, *c2));
3201 VEC_free (ce_s, heap, temp);
3207 /* Walk statement T setting up aliasing constraints according to the
3208 references found in T. This function is the main part of the
3209 constraint builder. AI points to auxiliary alias information used
3210 when building alias sets and computing alias grouping heuristics. */
3213 find_func_aliases (tree origt)
3216 VEC(ce_s, heap) *lhsc = NULL;
3217 VEC(ce_s, heap) *rhsc = NULL;
3218 struct constraint_expr *c;
3220 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
3221 t = TREE_OPERAND (t, 0);
3223 /* Now build constraints expressions. */
3224 if (TREE_CODE (t) == PHI_NODE)
3226 /* Only care about pointers and structures containing
3228 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
3229 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
3234 /* For a phi node, assign all the arguments to
3236 get_constraint_for (PHI_RESULT (t), &lhsc, NULL);
3237 for (i = 0; i < PHI_NUM_ARGS (t); i++)
3239 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc, NULL);
3240 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3242 struct constraint_expr *c2;
3243 while (VEC_length (ce_s, rhsc) > 0)
3245 c2 = VEC_last (ce_s, rhsc);
3246 process_constraint (new_constraint (*c, *c2));
3247 VEC_pop (ce_s, rhsc);
3253 /* In IPA mode, we need to generate constraints to pass call
3254 arguments through their calls. There are two case, either a
3255 modify_expr when we are returning a value, or just a plain
3256 call_expr when we are not. */
3257 else if (in_ipa_mode
3258 && ((TREE_CODE (t) == MODIFY_EXPR
3259 && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR
3260 && !(call_expr_flags (TREE_OPERAND (t, 1))
3261 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
3262 || (TREE_CODE (t) == CALL_EXPR
3263 && !(call_expr_flags (t)
3264 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))))
3274 if (TREE_CODE (t) == MODIFY_EXPR)
3276 lhsop = TREE_OPERAND (t, 0);
3277 rhsop = TREE_OPERAND (t, 1);
3284 decl = get_callee_fndecl (rhsop);
3286 /* If we can directly resolve the function being called, do so.
3287 Otherwise, it must be some sort of indirect expression that
3288 we should still be able to handle. */
3291 found = lookup_id_for_tree (decl, &varid);
3296 decl = TREE_OPERAND (rhsop, 0);
3297 found = lookup_id_for_tree (decl, &varid);
3301 /* Assign all the passed arguments to the approriate incoming
3302 parameters of the function. */
3303 fi = get_varinfo (varid);
3304 arglist = TREE_OPERAND (rhsop, 1);
3306 for (;arglist; arglist = TREE_CHAIN (arglist))
3308 tree arg = TREE_VALUE (arglist);
3309 struct constraint_expr lhs ;
3310 struct constraint_expr *rhsp;
3312 get_constraint_for (arg, &rhsc, NULL);
3313 if (TREE_CODE (decl) != FUNCTION_DECL)
3322 lhs.var = first_vi_for_offset (fi, i)->id;
3325 while (VEC_length (ce_s, rhsc) != 0)
3327 rhsp = VEC_last (ce_s, rhsc);
3328 process_constraint (new_constraint (lhs, *rhsp));
3329 VEC_pop (ce_s, rhsc);
3333 /* If we are returning a value, assign it to the result. */
3336 struct constraint_expr rhs;
3337 struct constraint_expr *lhsp;
3340 get_constraint_for (lhsop, &lhsc, NULL);
3341 if (TREE_CODE (decl) != FUNCTION_DECL)
3350 rhs.var = first_vi_for_offset (fi, i)->id;
3353 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3354 process_constraint (new_constraint (*lhsp, rhs));
3357 /* Otherwise, just a regular assignment statement. */
3358 else if (TREE_CODE (t) == MODIFY_EXPR)
3360 tree lhsop = TREE_OPERAND (t, 0);
3361 tree rhsop = TREE_OPERAND (t, 1);
3364 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3365 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
3367 do_structure_copy (lhsop, rhsop);
3371 /* Only care about operations with pointers, structures
3372 containing pointers, dereferences, and call expressions. */
3373 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
3374 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3375 || TREE_CODE (rhsop) == CALL_EXPR)
3377 get_constraint_for (lhsop, &lhsc, NULL);
3378 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
3380 /* RHS that consist of unary operations,
3381 exceptional types, or bare decls/constants, get
3382 handled directly by get_constraint_for. */
3384 case tcc_declaration:
3386 case tcc_exceptional:
3387 case tcc_expression:
3391 bool need_anyoffset = false;
3392 tree strippedrhs = rhsop;
3395 /* XXX: Push this back into the ADDR_EXPR
3396 case, and remove anyoffset handling. */
3397 STRIP_NOPS (strippedrhs);
3398 rhstype = TREE_TYPE (strippedrhs);
3400 get_constraint_for (rhsop, &rhsc, &need_anyoffset);
3401 if (TREE_CODE (strippedrhs) == ADDR_EXPR
3402 && AGGREGATE_TYPE_P (TREE_TYPE (rhstype)))
3404 struct constraint_expr *origrhs;
3406 struct constraint_expr tmp;
3408 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3409 origrhs = VEC_last (ce_s, rhsc);
3411 VEC_pop (ce_s, rhsc);
3412 origvar = get_varinfo (origrhs->var);
3413 for (; origvar; origvar = origvar->next)
3415 tmp.var = origvar->id;
3416 VEC_safe_push (ce_s, heap, rhsc, &tmp);
3420 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3422 struct constraint_expr *c2;
3425 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3426 process_constraint (new_constraint (*c, *c2));
3434 /* For pointer arithmetic of the form
3435 PTR + CST, we can simply use PTR's
3436 constraint because pointer arithmetic is
3437 not allowed to go out of bounds. */
3438 if (handle_ptr_arith (lhsc, rhsop))
3443 /* Otherwise, walk each operand. Notice that we
3444 can't use the operand interface because we need
3445 to process expressions other than simple operands
3446 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3448 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
3450 tree op = TREE_OPERAND (rhsop, i);
3453 gcc_assert (VEC_length (ce_s, rhsc) == 0);
3454 get_constraint_for (op, &rhsc, NULL);
3455 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3457 struct constraint_expr *c2;
3458 while (VEC_length (ce_s, rhsc) > 0)
3460 c2 = VEC_last (ce_s, rhsc);
3461 process_constraint (new_constraint (*c, *c2));
3462 VEC_pop (ce_s, rhsc);
3471 /* After promoting variables and computing aliasing we will
3472 need to re-scan most statements. FIXME: Try to minimize the
3473 number of statements re-scanned. It's not really necessary to
3474 re-scan *all* statements. */
3475 mark_stmt_modified (origt);
3476 VEC_free (ce_s, heap, rhsc);
3477 VEC_free (ce_s, heap, lhsc);
3481 /* Find the first varinfo in the same variable as START that overlaps with
3483 Effectively, walk the chain of fields for the variable START to find the
3484 first field that overlaps with OFFSET.
3485 Return NULL if we can't find one. */
3488 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3490 varinfo_t curr = start;
3493 /* We may not find a variable in the field list with the actual
3494 offset when when we have glommed a structure to a variable.
3495 In that case, however, offset should still be within the size
3497 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3505 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3509 insert_into_field_list (varinfo_t base, varinfo_t field)
3511 varinfo_t prev = base;
3512 varinfo_t curr = base->next;
3523 if (field->offset <= curr->offset)
3528 field->next = prev->next;
3533 /* qsort comparison function for two fieldoff's PA and PB */
3536 fieldoff_compare (const void *pa, const void *pb)
3538 const fieldoff_s *foa = (const fieldoff_s *)pa;
3539 const fieldoff_s *fob = (const fieldoff_s *)pb;
3540 HOST_WIDE_INT foasize, fobsize;
3542 if (foa->offset != fob->offset)
3543 return foa->offset - fob->offset;
3545 foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
3546 fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
3547 return foasize - fobsize;
3550 /* Sort a fieldstack according to the field offset and sizes. */
3551 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3553 qsort (VEC_address (fieldoff_s, fieldstack),
3554 VEC_length (fieldoff_s, fieldstack),
3555 sizeof (fieldoff_s),
3559 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3560 of TYPE onto fieldstack, recording their offsets along the way.
3561 OFFSET is used to keep track of the offset in this entire structure, rather
3562 than just the immediately containing structure. Returns the number
3564 HAS_UNION is set to true if we find a union type as a field of
3568 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
3569 HOST_WIDE_INT offset, bool *has_union)
3574 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
3575 if (TREE_CODE (field) == FIELD_DECL)
3581 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3582 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3585 if (!var_can_have_subvars (field))
3587 else if (!(pushed = push_fields_onto_fieldstack
3588 (TREE_TYPE (field), fieldstack,
3589 offset + bitpos_of_field (field), has_union))
3590 && DECL_SIZE (field)
3591 && !integer_zerop (DECL_SIZE (field)))
3592 /* Empty structures may have actual size, like in C++. So
3593 see if we didn't push any subfields and the size is
3594 nonzero, push the field onto the stack */
3601 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3602 pair->field = field;
3603 pair->offset = offset + bitpos_of_field (field);
3614 make_constraint_to_anything (varinfo_t vi)
3616 struct constraint_expr lhs, rhs;
3622 rhs.var = anything_id;
3624 rhs.type = ADDRESSOF;
3625 process_constraint (new_constraint (lhs, rhs));
3628 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3629 if it is a varargs function. */
3632 count_num_arguments (tree decl, bool *is_varargs)
3637 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
3641 if (TREE_VALUE (t) == void_type_node)
3651 /* Creation function node for DECL, using NAME, and return the index
3652 of the variable we've created for the function. */
3655 create_function_info_for (tree decl, const char *name)
3657 unsigned int index = VEC_length (varinfo_t, varmap);
3661 bool is_varargs = false;
3663 /* Create the variable info. */
3665 vi = new_var_info (decl, index, name, index);
3670 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3671 insert_id_for_tree (vi->decl, index);
3672 VEC_safe_push (varinfo_t, heap, varmap, vi);
3676 /* If it's varargs, we don't know how many arguments it has, so we
3683 vi->is_unknown_size_var = true;
3688 arg = DECL_ARGUMENTS (decl);
3690 /* Set up varirables for each argument. */
3691 for (i = 1; i < vi->fullsize; i++)
3694 const char *newname;
3696 unsigned int newindex;
3697 tree argdecl = decl;
3702 newindex = VEC_length (varinfo_t, varmap);
3703 asprintf (&tempname, "%s.arg%d", name, i-1);
3704 newname = ggc_strdup (tempname);
3707 argvi = new_var_info (argdecl, newindex,newname, newindex);
3708 argvi->decl = argdecl;
3709 VEC_safe_push (varinfo_t, heap, varmap, argvi);
3712 argvi->fullsize = vi->fullsize;
3713 argvi->has_union = false;
3714 insert_into_field_list (vi, argvi);
3715 stats.total_vars ++;
3718 insert_id_for_tree (arg, newindex);
3719 arg = TREE_CHAIN (arg);
3723 /* Create a variable for the return var. */
3724 if (DECL_RESULT (decl) != NULL
3725 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
3728 const char *newname;
3730 unsigned int newindex;
3731 tree resultdecl = decl;
3736 if (DECL_RESULT (decl))
3737 resultdecl = DECL_RESULT (decl);
3739 newindex = VEC_length (varinfo_t, varmap);
3740 asprintf (&tempname, "%s.result", name);
3741 newname = ggc_strdup (tempname);
3744 resultvi = new_var_info (resultdecl, newindex, newname, newindex);
3745 resultvi->decl = resultdecl;
3746 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
3747 resultvi->offset = i;
3749 resultvi->fullsize = vi->fullsize;
3750 resultvi->has_union = false;
3751 insert_into_field_list (vi, resultvi);
3752 stats.total_vars ++;
3753 if (DECL_RESULT (decl))
3754 insert_id_for_tree (DECL_RESULT (decl), newindex);
3760 /* Return true if FIELDSTACK contains fields that overlap.
3761 FIELDSTACK is assumed to be sorted by offset. */
3764 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
3766 fieldoff_s *fo = NULL;
3768 HOST_WIDE_INT lastoffset = -1;
3770 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3772 if (fo->offset == lastoffset)
3774 lastoffset = fo->offset;
3779 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3780 This will also create any varinfo structures necessary for fields
3784 create_variable_info_for (tree decl, const char *name)
3786 unsigned int index = VEC_length (varinfo_t, varmap);
3788 tree decltype = TREE_TYPE (decl);
3789 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
3790 bool notokay = false;
3792 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
3793 VEC (fieldoff_s,heap) *fieldstack = NULL;
3795 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
3796 return create_function_info_for (decl, name);
3798 hasunion = TREE_CODE (decltype) == UNION_TYPE
3799 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
3800 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
3802 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
3805 VEC_free (fieldoff_s, heap, fieldstack);
3811 /* If the variable doesn't have subvars, we may end up needing to
3812 sort the field list and create fake variables for all the
3814 vi = new_var_info (decl, index, name, index);
3817 vi->has_union = hasunion;
3819 || TREE_CODE (declsize) != INTEGER_CST
3820 || TREE_CODE (decltype) == UNION_TYPE
3821 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
3823 vi->is_unknown_size_var = true;
3829 vi->fullsize = TREE_INT_CST_LOW (declsize);
3830 vi->size = vi->fullsize;
3833 insert_id_for_tree (vi->decl, index);
3834 VEC_safe_push (varinfo_t, heap, varmap, vi);
3835 if (is_global && (!flag_whole_program || !in_ipa_mode))
3836 make_constraint_to_anything (vi);
3839 if (use_field_sensitive
3841 && !vi->is_unknown_size_var
3842 && var_can_have_subvars (decl))
3844 unsigned int newindex = VEC_length (varinfo_t, varmap);
3845 fieldoff_s *fo = NULL;
3849 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3851 if (!DECL_SIZE (fo->field)
3852 || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
3860 /* We can't sort them if we have a field with a variable sized type,
3861 which will make notokay = true. In that case, we are going to return
3862 without creating varinfos for the fields anyway, so sorting them is a
3866 sort_fieldstack (fieldstack);
3867 /* Due to some C++ FE issues, like PR 22488, we might end up
3868 what appear to be overlapping fields even though they,
3869 in reality, do not overlap. Until the C++ FE is fixed,
3870 we will simply disable field-sensitivity for these cases. */
3871 notokay = check_for_overlaps (fieldstack);
3875 if (VEC_length (fieldoff_s, fieldstack) != 0)
3876 fo = VEC_index (fieldoff_s, fieldstack, 0);
3878 if (fo == NULL || notokay)
3880 vi->is_unknown_size_var = 1;
3883 VEC_free (fieldoff_s, heap, fieldstack);
3888 vi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
3889 vi->offset = fo->offset;
3890 for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3893 const char *newname;
3897 newindex = VEC_length (varinfo_t, varmap);
3898 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (field));
3899 newname = ggc_strdup (tempname);
3901 newvi = new_var_info (decl, newindex, newname, newindex);
3902 newvi->offset = fo->offset;
3903 newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
3904 newvi->fullsize = vi->fullsize;
3905 insert_into_field_list (vi, newvi);
3906 VEC_safe_push (varinfo_t, heap, varmap, newvi);
3907 if (is_global && (!flag_whole_program || !in_ipa_mode))
3908 make_constraint_to_anything (newvi);
3912 VEC_free (fieldoff_s, heap, fieldstack);
3917 /* Print out the points-to solution for VAR to FILE. */
3920 dump_solution_for_var (FILE *file, unsigned int var)
3922 varinfo_t vi = get_varinfo (var);
3926 fprintf (file, "%s = { ", vi->name);
3927 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
3929 fprintf (file, "%s ", get_varinfo (i)->name);
3931 fprintf (file, "}\n");
3934 /* Print the points-to solution for VAR to stdout. */
3937 debug_solution_for_var (unsigned int var)
3939 dump_solution_for_var (stdout, var);
3943 /* Create varinfo structures for all of the variables in the
3944 function for intraprocedural mode. */
3947 intra_create_variable_infos (void)
3951 /* For each incoming argument arg, ARG = &ANYTHING */
3952 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
3954 struct constraint_expr lhs;
3959 lhs.var = create_variable_info_for (t, alias_get_name (t));
3961 for (p = get_varinfo (lhs.var); p; p = p->next)
3962 make_constraint_to_anything (p);
3967 /* Set bits in INTO corresponding to the variable uids in solution set
3971 set_uids_in_ptset (bitmap into, bitmap from)
3977 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
3979 varinfo_t vi = get_varinfo (i);
3981 /* The only artificial variables that are allowed in a may-alias
3982 set are heap variables. */
3983 if (vi->is_artificial_var && !vi->is_heap_var)
3986 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
3988 /* Variables containing unions may need to be converted to
3989 their SFT's, because SFT's can have unions and we cannot. */
3990 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
3991 bitmap_set_bit (into, DECL_UID (sv->var));
3993 else if (TREE_CODE (vi->decl) == VAR_DECL
3994 || TREE_CODE (vi->decl) == PARM_DECL)
3996 if (var_can_have_subvars (vi->decl)
3997 && get_subvars_for_var (vi->decl))
3999 /* If VI->DECL is an aggregate for which we created
4000 SFTs, add the SFT corresponding to VI->OFFSET. */
4001 tree sft = get_subvar_at (vi->decl, vi->offset);
4003 bitmap_set_bit (into, DECL_UID (sft));
4007 /* Otherwise, just add VI->DECL to the alias set. */
4008 bitmap_set_bit (into, DECL_UID (vi->decl));
4015 static bool have_alias_info = false;
4017 /* Given a pointer variable P, fill in its points-to set, or return
4018 false if we can't. */
4021 find_what_p_points_to (tree p)
4023 unsigned int id = 0;
4025 if (!have_alias_info)
4028 if (lookup_id_for_tree (p, &id))
4030 varinfo_t vi = get_varinfo (id);
4032 if (vi->is_artificial_var)
4035 /* See if this is a field or a structure. */
4036 if (vi->size != vi->fullsize)
4038 /* Nothing currently asks about structure fields directly,
4039 but when they do, we need code here to hand back the
4041 if (!var_can_have_subvars (vi->decl)
4042 || get_subvars_for_var (vi->decl) == NULL)
4047 struct ptr_info_def *pi = get_ptr_info (p);
4051 /* This variable may have been collapsed, let's get the real
4053 vi = get_varinfo (vi->node);
4055 /* Translate artificial variables into SSA_NAME_PTR_INFO
4057 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4059 varinfo_t vi = get_varinfo (i);
4061 if (vi->is_artificial_var)
4063 /* FIXME. READONLY should be handled better so that
4064 flow insensitive aliasing can disregard writable
4066 if (vi->id == nothing_id)
4068 else if (vi->id == anything_id)
4069 pi->pt_anything = 1;
4070 else if (vi->id == readonly_id)
4071 pi->pt_anything = 1;
4072 else if (vi->id == integer_id)
4073 pi->pt_anything = 1;
4074 else if (vi->is_heap_var)
4075 pi->pt_global_mem = 1;
4079 if (pi->pt_anything)
4083 pi->pt_vars = BITMAP_GGC_ALLOC ();
4085 set_uids_in_ptset (pi->pt_vars, vi->solution);
4087 if (bitmap_empty_p (pi->pt_vars))
4099 /* Dump points-to information to OUTFILE. */
4102 dump_sa_points_to_info (FILE *outfile)
4106 fprintf (outfile, "\nPoints-to sets\n\n");
4108 if (dump_flags & TDF_STATS)
4110 fprintf (outfile, "Stats:\n");
4111 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4112 fprintf (outfile, "Statically unified vars: %d\n",
4113 stats.unified_vars_static);
4114 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
4115 fprintf (outfile, "Dynamically unified vars: %d\n",
4116 stats.unified_vars_dynamic);
4117 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4118 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4121 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4122 dump_solution_for_var (outfile, i);
4126 /* Debug points-to information to stderr. */
4129 debug_sa_points_to_info (void)
4131 dump_sa_points_to_info (stderr);
4135 /* Initialize the always-existing constraint variables for NULL
4136 ANYTHING, READONLY, and INTEGER */
4139 init_base_vars (void)
4141 struct constraint_expr lhs, rhs;
4143 /* Create the NULL variable, used to represent that a variable points
4145 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4146 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
4147 insert_id_for_tree (nothing_tree, 0);
4148 var_nothing->is_artificial_var = 1;
4149 var_nothing->offset = 0;
4150 var_nothing->size = ~0;
4151 var_nothing->fullsize = ~0;
4152 var_nothing->is_special_var = 1;
4154 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
4156 /* Create the ANYTHING variable, used to represent that a variable
4157 points to some unknown piece of memory. */
4158 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4159 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
4160 insert_id_for_tree (anything_tree, 1);
4161 var_anything->is_artificial_var = 1;
4162 var_anything->size = ~0;
4163 var_anything->offset = 0;
4164 var_anything->next = NULL;
4165 var_anything->fullsize = ~0;
4166 var_anything->is_special_var = 1;
4169 /* Anything points to anything. This makes deref constraints just
4170 work in the presence of linked list and other p = *p type loops,
4171 by saying that *ANYTHING = ANYTHING. */
4172 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
4174 lhs.var = anything_id;
4176 rhs.type = ADDRESSOF;
4177 rhs.var = anything_id;
4179 var_anything->address_taken = true;
4181 /* This specifically does not use process_constraint because
4182 process_constraint ignores all anything = anything constraints, since all
4183 but this one are redundant. */
4184 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
4186 /* Create the READONLY variable, used to represent that a variable
4187 points to readonly memory. */
4188 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4189 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
4190 var_readonly->is_artificial_var = 1;
4191 var_readonly->offset = 0;
4192 var_readonly->size = ~0;
4193 var_readonly->fullsize = ~0;
4194 var_readonly->next = NULL;
4195 var_readonly->is_special_var = 1;
4196 insert_id_for_tree (readonly_tree, 2);
4198 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4200 /* readonly memory points to anything, in order to make deref
4201 easier. In reality, it points to anything the particular
4202 readonly variable can point to, but we don't track this
4205 lhs.var = readonly_id;
4207 rhs.type = ADDRESSOF;
4208 rhs.var = anything_id;
4211 process_constraint (new_constraint (lhs, rhs));
4213 /* Create the INTEGER variable, used to represent that a variable points
4215 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4216 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
4217 insert_id_for_tree (integer_tree, 3);
4218 var_integer->is_artificial_var = 1;
4219 var_integer->size = ~0;
4220 var_integer->fullsize = ~0;
4221 var_integer->offset = 0;
4222 var_integer->next = NULL;
4223 var_integer->is_special_var = 1;
4225 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
4227 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
4228 integer will point to. */
4230 lhs.var = integer_id;
4232 rhs.type = ADDRESSOF;
4233 rhs.var = anything_id;
4235 process_constraint (new_constraint (lhs, rhs));
4238 /* Return true if we actually need to solve the constraint graph in order to
4239 get our points-to sets. This is false when, for example, no addresses are
4240 taken other than special vars, or all points-to sets with members already
4241 contain the anything variable and there are no predecessors for other
4245 need_to_solve (void)
4249 bool found_address_taken = false;
4250 bool found_non_anything = false;
4252 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4254 if (v->is_special_var)
4257 if (v->address_taken)
4258 found_address_taken = true;
4261 && !bitmap_empty_p (v->solution)
4262 && !bitmap_bit_p (v->solution, anything_id))
4263 found_non_anything = true;
4264 else if (bitmap_empty_p (v->solution)
4265 && (VEC_length (constraint_edge_t, graph->preds[v->id]) != 0
4266 || (graph->zero_weight_preds[v->id] && !bitmap_empty_p (graph->zero_weight_preds[v->id]))))
4267 found_non_anything = true;
4269 if (found_address_taken && found_non_anything)
4276 /* Initialize things necessary to perform PTA */
4279 init_alias_vars (void)
4281 bitmap_obstack_initialize (&ptabitmap_obstack);
4282 bitmap_obstack_initialize (&predbitmap_obstack);
4284 constraint_pool = create_alloc_pool ("Constraint pool",
4285 sizeof (struct constraint), 30);
4286 variable_info_pool = create_alloc_pool ("Variable info pool",
4287 sizeof (struct variable_info), 30);
4288 constraint_edge_pool = create_alloc_pool ("Constraint edges",
4289 sizeof (struct constraint_edge), 30);
4291 constraints = VEC_alloc (constraint_t, heap, 8);
4292 varmap = VEC_alloc (varinfo_t, heap, 8);
4293 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
4294 memset (&stats, 0, sizeof (stats));
4300 /* Create points-to sets for the current function. See the comments
4301 at the start of the file for an algorithmic overview. */
4304 compute_points_to_sets (struct alias_info *ai)
4308 timevar_push (TV_TREE_PTA);
4312 intra_create_variable_infos ();
4314 /* Now walk all statements and derive aliases. */
4317 block_stmt_iterator bsi;
4320 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4322 if (is_gimple_reg (PHI_RESULT (phi)))
4324 find_func_aliases (phi);
4325 /* Update various related attributes like escaped
4326 addresses, pointer dereferences for loads and stores.
4327 This is used when creating name tags and alias
4329 update_alias_info (phi, ai);
4333 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4335 tree stmt = bsi_stmt (bsi);
4336 find_func_aliases (stmt);
4337 /* Update various related attributes like escaped
4338 addresses, pointer dereferences for loads and stores.
4339 This is used when creating name tags and alias
4341 update_alias_info (stmt, ai);
4345 build_constraint_graph ();
4349 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4350 dump_constraints (dump_file);
4353 if (need_to_solve ())
4357 "\nCollapsing static cycles and doing variable "
4360 find_and_collapse_graph_cycles (graph, false);
4361 perform_var_substitution (graph);
4364 fprintf (dump_file, "\nSolving graph:\n");
4366 solve_graph (graph);
4370 dump_sa_points_to_info (dump_file);
4372 have_alias_info = true;
4374 timevar_pop (TV_TREE_PTA);
4378 /* Delete created points-to sets. */
4381 delete_points_to_sets (void)
4386 htab_delete (id_for_tree);
4387 bitmap_obstack_release (&ptabitmap_obstack);
4388 bitmap_obstack_release (&predbitmap_obstack);
4389 VEC_free (constraint_t, heap, constraints);
4391 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4393 VEC_free (constraint_edge_t, heap, graph->succs[i]);
4394 VEC_free (constraint_edge_t, heap, graph->preds[i]);
4395 VEC_free (constraint_t, heap, v->complex);
4397 free (graph->zero_weight_preds);
4398 free (graph->zero_weight_succs);
4399 free (graph->succs);
4400 free (graph->preds);
4403 VEC_free (varinfo_t, heap, varmap);
4404 free_alloc_pool (variable_info_pool);
4405 free_alloc_pool (constraint_pool);
4406 free_alloc_pool (constraint_edge_pool);
4408 have_alias_info = false;
4411 /* Return true if we should execute IPA PTA. */
4415 return (flag_unit_at_a_time != 0
4416 /* Don't bother doing anything if the program has errors. */
4417 && !(errorcount || sorrycount));
4420 /* Execute the driver for IPA PTA. */
4422 ipa_pta_execute (void)
4424 struct cgraph_node *node;
4429 for (node = cgraph_nodes; node; node = node->next)
4431 if (!node->analyzed || cgraph_is_master_clone (node))
4435 varid = create_function_info_for (node->decl,
4436 cgraph_node_name (node));
4437 if (node->local.externally_visible)
4439 varinfo_t fi = get_varinfo (varid);
4440 for (; fi; fi = fi->next)
4441 make_constraint_to_anything (fi);
4445 for (node = cgraph_nodes; node; node = node->next)
4447 if (node->analyzed && cgraph_is_master_clone (node))
4449 struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
4451 tree old_func_decl = current_function_decl;
4454 "Generating constraints for %s\n",
4455 cgraph_node_name (node));
4457 current_function_decl = node->decl;
4459 FOR_EACH_BB_FN (bb, cfun)
4461 block_stmt_iterator bsi;
4464 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4466 if (is_gimple_reg (PHI_RESULT (phi)))
4468 find_func_aliases (phi);
4472 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4474 tree stmt = bsi_stmt (bsi);
4475 find_func_aliases (stmt);
4478 current_function_decl = old_func_decl;
4483 /* Make point to anything. */
4487 build_constraint_graph ();
4491 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4492 dump_constraints (dump_file);
4495 if (need_to_solve ())
4499 "\nCollapsing static cycles and doing variable "
4502 find_and_collapse_graph_cycles (graph, false);
4503 perform_var_substitution (graph);
4506 fprintf (dump_file, "\nSolving graph:\n");
4508 solve_graph (graph);
4512 dump_sa_points_to_info (dump_file);
4516 struct tree_opt_pass pass_ipa_pta =
4519 gate_ipa_pta, /* gate */
4520 ipa_pta_execute, /* execute */
4523 0, /* static_pass_number */
4524 TV_IPA_PTA, /* tv_id */
4525 0, /* properties_required */
4526 0, /* properties_provided */
4527 0, /* properties_destroyed */
4528 0, /* todo_flags_start */
4529 0, /* todo_flags_finish */
4533 /* Initialize the heapvar for statement mapping. */
4535 init_alias_heapvars (void)
4537 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq, NULL);
4541 delete_alias_heapvars (void)
4543 htab_delete (heapvar_for_stmt);
4547 #include "gt-tree-ssa-structalias.h"