1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006 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"
52 #include "tree-ssa-structalias.h"
55 #include "pointer-set.h"
57 /* The idea behind this analyzer is to generate set constraints from the
58 program, then solve the resulting constraints in order to generate the
61 Set constraints are a way of modeling program analysis problems that
62 involve sets. They consist of an inclusion constraint language,
63 describing the variables (each variable is a set) and operations that
64 are involved on the variables, and a set of rules that derive facts
65 from these operations. To solve a system of set constraints, you derive
66 all possible facts under the rules, which gives you the correct sets
69 See "Efficient Field-sensitive pointer analysis for C" by "David
70 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
71 http://citeseer.ist.psu.edu/pearce04efficient.html
73 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
74 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
75 http://citeseer.ist.psu.edu/heintze01ultrafast.html
77 There are three types of real constraint expressions, DEREF,
78 ADDRESSOF, and SCALAR. There is one type of fake constraint
79 expression, called INCLUDES. Each constraint expression consists
80 of a constraint type, a variable, and an offset.
82 SCALAR is a constraint expression type used to represent x, whether
83 it appears on the LHS or the RHS of a statement.
84 DEREF is a constraint expression type used to represent *x, whether
85 it appears on the LHS or the RHS of a statement.
86 ADDRESSOF is a constraint expression used to represent &x, whether
87 it appears on the LHS or the RHS of a statement.
88 INCLUDES is a constraint expression type used to represent just a
89 setting of a bit in the points-to set without having the address
90 taken. It exists mainly for abstraction sake, and is used for
91 initializing fake variables like the ESCAPED_VARS set.
93 Each pointer variable in the program is assigned an integer id, and
94 each field of a structure variable is assigned an integer id as well.
96 Structure variables are linked to their list of fields through a "next
97 field" in each variable that points to the next field in offset
99 Each variable for a structure field has
101 1. "size", that tells the size in bits of that field.
102 2. "fullsize, that tells the size in bits of the entire structure.
103 3. "offset", that tells the offset in bits from the beginning of the
104 structure to this field.
116 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
117 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
118 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
121 In order to solve the system of set constraints, the following is
124 1. Each constraint variable x has a solution set associated with it,
127 2. Constraints are separated into direct, copy, and complex.
128 Direct constraints are ADDRESSOF constraints that require no extra
129 processing, such as P = &Q
130 Copy constraints are those of the form P = Q.
131 Complex constraints are all the constraints involving dereferences
132 and offsets (including offsetted copies).
134 3. All direct constraints of the form P = &Q are processed, such
135 that Q is added to Sol(P)
137 4. All complex constraints for a given constraint variable are stored in a
138 linked list attached to that variable's node.
140 5. A directed graph is built out of the copy constraints. Each
141 constraint variable is a node in the graph, and an edge from
142 Q to P is added for each copy constraint of the form P = Q
144 6. The graph is then walked, and solution sets are
145 propagated along the copy edges, such that an edge from Q to P
146 causes Sol(P) <- Sol(P) union Sol(Q).
148 7. As we visit each node, all complex constraints associated with
149 that node are processed by adding appropriate copy edges to the graph, or the
150 appropriate variables to the solution set.
152 8. The process of walking the graph is iterated until no solution
155 Prior to walking the graph in steps 6 and 7, We perform static
156 cycle elimination on the constraint graph, as well
157 as off-line variable substitution.
159 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
160 on and turned into anything), but isn't. You can just see what offset
161 inside the pointed-to struct it's going to access.
163 TODO: Constant bounded arrays can be handled as if they were structs of the
164 same number of elements.
166 TODO: Modeling heap and incoming pointers becomes much better if we
167 add fields to them as we discover them, which we could do.
169 TODO: We could handle unions, but to be honest, it's probably not
170 worth the pain or slowdown. */
172 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
173 htab_t heapvar_for_stmt;
175 static bool use_field_sensitive = true;
176 static int in_ipa_mode = 0;
177 static bitmap_obstack predbitmap_obstack;
178 static bitmap_obstack ptabitmap_obstack;
179 static bitmap_obstack iteration_obstack;
181 static unsigned int create_variable_info_for (tree, const char *);
182 static void build_constraint_graph (void);
184 DEF_VEC_P(constraint_t);
185 DEF_VEC_ALLOC_P(constraint_t,heap);
187 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
189 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
191 static struct constraint_stats
193 unsigned int total_vars;
194 unsigned int collapsed_vars;
195 unsigned int unified_vars_static;
196 unsigned int unified_vars_dynamic;
197 unsigned int iterations;
198 unsigned int num_edges;
203 /* ID of this variable */
206 /* Name of this variable */
209 /* Tree that this variable is associated with. */
212 /* Offset of this variable, in bits, from the base variable */
213 unsigned HOST_WIDE_INT offset;
215 /* Size of the variable, in bits. */
216 unsigned HOST_WIDE_INT size;
218 /* Full size of the base variable, in bits. */
219 unsigned HOST_WIDE_INT fullsize;
221 /* A link to the variable for the next field in this structure. */
222 struct variable_info *next;
224 /* Node in the graph that represents the constraints and points-to
225 solution for the variable. */
228 /* True if the address of this variable is taken. Needed for
229 variable substitution. */
230 unsigned int address_taken:1;
232 /* True if this variable is the target of a dereference. Needed for
233 variable substitution. */
234 unsigned int indirect_target:1;
236 /* True if the variable is directly the target of a dereference.
237 This is used to track which variables are *actually* dereferenced
238 so we can prune their points to listed. This is equivalent to the
239 indirect_target flag when no merging of variables happens. */
240 unsigned int directly_dereferenced:1;
242 /* True if this is a variable created by the constraint analysis, such as
243 heap variables and constraints we had to break up. */
244 unsigned int is_artificial_var:1;
246 /* True if this is a special variable whose solution set should not be
248 unsigned int is_special_var:1;
250 /* True for variables whose size is not known or variable. */
251 unsigned int is_unknown_size_var:1;
253 /* True for variables that have unions somewhere in them. */
254 unsigned int has_union:1;
256 /* True if this is a heap variable. */
257 unsigned int is_heap_var:1;
259 /* Points-to set for this variable. */
262 /* Finished points-to set for this variable (IE what is returned
263 from find_what_p_points_to. */
264 bitmap finished_solution;
266 /* Variable ids represented by this node. */
269 /* Vector of complex constraints for this node. Complex
270 constraints are those involving dereferences. */
271 VEC(constraint_t,heap) *complex;
273 /* Variable id this was collapsed to due to type unsafety.
274 This should be unused completely after build_constraint_graph, or
275 something is broken. */
276 struct variable_info *collapsed_to;
278 typedef struct variable_info *varinfo_t;
280 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
282 /* Pool of variable info structures. */
283 static alloc_pool variable_info_pool;
285 DEF_VEC_P(varinfo_t);
287 DEF_VEC_ALLOC_P(varinfo_t, heap);
289 /* Table of variable info structures for constraint variables.
290 Indexed directly by variable info id. */
291 static VEC(varinfo_t,heap) *varmap;
293 /* Return the varmap element N */
295 static inline varinfo_t
296 get_varinfo (unsigned int n)
298 return VEC_index(varinfo_t, varmap, n);
301 /* Return the varmap element N, following the collapsed_to link. */
303 static inline varinfo_t
304 get_varinfo_fc (unsigned int n)
306 varinfo_t v = VEC_index(varinfo_t, varmap, n);
309 return v->collapsed_to;
313 /* Variable that represents the unknown pointer. */
314 static varinfo_t var_anything;
315 static tree anything_tree;
316 static unsigned int anything_id;
318 /* Variable that represents the NULL pointer. */
319 static varinfo_t var_nothing;
320 static tree nothing_tree;
321 static unsigned int nothing_id;
323 /* Variable that represents read only memory. */
324 static varinfo_t var_readonly;
325 static tree readonly_tree;
326 static unsigned int readonly_id;
328 /* Variable that represents integers. This is used for when people do things
330 static varinfo_t var_integer;
331 static tree integer_tree;
332 static unsigned int integer_id;
334 /* Lookup a heap var for FROM, and return it if we find one. */
337 heapvar_lookup (tree from)
339 struct tree_map *h, in;
342 h = htab_find_with_hash (heapvar_for_stmt, &in, htab_hash_pointer (from));
348 /* Insert a mapping FROM->TO in the heap var for statement
352 heapvar_insert (tree from, tree to)
357 h = ggc_alloc (sizeof (struct tree_map));
358 h->hash = htab_hash_pointer (from);
361 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
362 *(struct tree_map **) loc = h;
365 /* Return a new variable info structure consisting for a variable
366 named NAME, and using constraint graph node NODE. */
369 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
371 varinfo_t ret = pool_alloc (variable_info_pool);
377 ret->address_taken = false;
378 ret->indirect_target = false;
379 ret->directly_dereferenced = false;
380 ret->is_artificial_var = false;
381 ret->is_heap_var = false;
382 ret->is_special_var = false;
383 ret->is_unknown_size_var = false;
384 ret->has_union = false;
385 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
386 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
387 ret->finished_solution = NULL;
390 ret->collapsed_to = NULL;
394 typedef enum {SCALAR, DEREF, ADDRESSOF, INCLUDES} constraint_expr_type;
396 /* An expression that appears in a constraint. */
398 struct constraint_expr
400 /* Constraint type. */
401 constraint_expr_type type;
403 /* Variable we are referring to in the constraint. */
406 /* Offset, in bits, of this constraint from the beginning of
407 variables it ends up referring to.
409 IOW, in a deref constraint, we would deref, get the result set,
410 then add OFFSET to each member. */
411 unsigned HOST_WIDE_INT offset;
414 typedef struct constraint_expr ce_s;
416 DEF_VEC_ALLOC_O(ce_s, heap);
417 static void get_constraint_for (tree, VEC(ce_s, heap) **);
418 static void do_deref (VEC (ce_s, heap) **);
420 /* Our set constraints are made up of two constraint expressions, one
423 As described in the introduction, our set constraints each represent an
424 operation between set valued variables.
428 struct constraint_expr lhs;
429 struct constraint_expr rhs;
432 /* List of constraints that we use to build the constraint graph from. */
434 static VEC(constraint_t,heap) *constraints;
435 static alloc_pool constraint_pool;
438 /* The constraint graph is represented as an array of bitmaps
439 containing successor nodes. */
441 struct constraint_graph
447 typedef struct constraint_graph *constraint_graph_t;
449 static constraint_graph_t graph;
451 /* Create a new constraint consisting of LHS and RHS expressions. */
454 new_constraint (const struct constraint_expr lhs,
455 const struct constraint_expr rhs)
457 constraint_t ret = pool_alloc (constraint_pool);
463 /* Print out constraint C to FILE. */
466 dump_constraint (FILE *file, constraint_t c)
468 if (c->lhs.type == ADDRESSOF)
470 else if (c->lhs.type == DEREF)
472 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
473 if (c->lhs.offset != 0)
474 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
475 fprintf (file, " = ");
476 if (c->rhs.type == ADDRESSOF)
478 else if (c->rhs.type == DEREF)
480 else if (c->rhs.type == INCLUDES)
482 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
483 if (c->rhs.offset != 0)
484 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
485 if (c->rhs.type == INCLUDES)
487 fprintf (file, "\n");
490 /* Print out constraint C to stderr. */
493 debug_constraint (constraint_t c)
495 dump_constraint (stderr, c);
498 /* Print out all constraints to FILE */
501 dump_constraints (FILE *file)
505 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
506 dump_constraint (file, c);
509 /* Print out all constraints to stderr. */
512 debug_constraints (void)
514 dump_constraints (stderr);
519 The solver is a simple worklist solver, that works on the following
522 sbitmap changed_nodes = all ones;
523 changed_count = number of nodes;
524 For each node that was already collapsed:
527 while (changed_count > 0)
529 compute topological ordering for constraint graph
531 find and collapse cycles in the constraint graph (updating
532 changed if necessary)
534 for each node (n) in the graph in topological order:
537 Process each complex constraint associated with the node,
538 updating changed if necessary.
540 For each outgoing edge from n, propagate the solution from n to
541 the destination of the edge, updating changed as necessary.
545 /* Return true if two constraint expressions A and B are equal. */
548 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
550 return a.type == b.type && a.var == b.var && a.offset == b.offset;
553 /* Return true if constraint expression A is less than constraint expression
554 B. This is just arbitrary, but consistent, in order to give them an
558 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
560 if (a.type == b.type)
563 return a.offset < b.offset;
565 return a.var < b.var;
568 return a.type < b.type;
571 /* Return true if constraint A is less than constraint B. This is just
572 arbitrary, but consistent, in order to give them an ordering. */
575 constraint_less (const constraint_t a, const constraint_t b)
577 if (constraint_expr_less (a->lhs, b->lhs))
579 else if (constraint_expr_less (b->lhs, a->lhs))
582 return constraint_expr_less (a->rhs, b->rhs);
585 /* Return true if two constraints A and B are equal. */
588 constraint_equal (struct constraint a, struct constraint b)
590 return constraint_expr_equal (a.lhs, b.lhs)
591 && constraint_expr_equal (a.rhs, b.rhs);
595 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
598 constraint_vec_find (VEC(constraint_t,heap) *vec,
599 struct constraint lookfor)
607 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
608 if (place >= VEC_length (constraint_t, vec))
610 found = VEC_index (constraint_t, vec, place);
611 if (!constraint_equal (*found, lookfor))
616 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
619 constraint_set_union (VEC(constraint_t,heap) **to,
620 VEC(constraint_t,heap) **from)
625 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
627 if (constraint_vec_find (*to, *c) == NULL)
629 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
631 VEC_safe_insert (constraint_t, heap, *to, place, c);
636 /* Take a solution set SET, add OFFSET to each member of the set, and
637 overwrite SET with the result when done. */
640 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
642 bitmap result = BITMAP_ALLOC (&iteration_obstack);
646 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
648 /* If this is a properly sized variable, only add offset if it's
649 less than end. Otherwise, it is globbed to a single
652 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
654 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
655 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
658 bitmap_set_bit (result, v->id);
660 else if (get_varinfo (i)->is_artificial_var
661 || get_varinfo (i)->has_union
662 || get_varinfo (i)->is_unknown_size_var)
664 bitmap_set_bit (result, i);
668 bitmap_copy (set, result);
669 BITMAP_FREE (result);
672 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
676 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
679 return bitmap_ior_into (to, from);
685 tmp = BITMAP_ALLOC (&iteration_obstack);
686 bitmap_copy (tmp, from);
687 solution_set_add (tmp, inc);
688 res = bitmap_ior_into (to, tmp);
694 /* Insert constraint C into the list of complex constraints for VAR. */
697 insert_into_complex (unsigned int var, constraint_t c)
699 varinfo_t vi = get_varinfo (var);
700 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
702 VEC_safe_insert (constraint_t, heap, vi->complex, place, c);
706 /* Condense two variable nodes into a single variable node, by moving
707 all associated info from SRC to TO. */
710 condense_varmap_nodes (unsigned int to, unsigned int src)
712 varinfo_t tovi = get_varinfo (to);
713 varinfo_t srcvi = get_varinfo (src);
718 /* the src node, and all its variables, are now the to node. */
720 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
721 get_varinfo (i)->node = to;
723 /* Merge the src node variables and the to node variables. */
724 bitmap_set_bit (tovi->variables, src);
725 bitmap_ior_into (tovi->variables, srcvi->variables);
726 bitmap_clear (srcvi->variables);
728 /* Move all complex constraints from src node into to node */
729 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
731 /* In complex constraints for node src, we may have either
732 a = *src, and *src = a. */
734 if (c->rhs.type == DEREF)
739 constraint_set_union (&tovi->complex, &srcvi->complex);
740 VEC_free (constraint_t, heap, srcvi->complex);
741 srcvi->complex = NULL;
745 /* Remove edges involving NODE from GRAPH. */
748 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
753 /* Walk the successors, erase the associated preds. */
755 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[node], 0, j, bi)
757 bitmap_clear_bit (graph->preds[j], node);
760 /* Walk the preds, erase the associated succs. */
762 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[node], 0, j, bi)
764 bitmap_clear_bit (graph->succs[j], node);
767 if (graph->preds[node])
769 BITMAP_FREE (graph->preds[node]);
770 graph->preds[node] = NULL;
773 if (graph->succs[node])
775 BITMAP_FREE (graph->succs[node]);
776 graph->succs[node] = NULL;
780 static bool edge_added = false;
782 /* Merge GRAPH nodes FROM and TO into node TO. */
785 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
791 /* Merge all the predecessor edges. */
792 if (graph->preds[from])
794 if (!graph->preds[to])
795 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
797 EXECUTE_IF_SET_IN_BITMAP (graph->preds[from], 0, j, bi)
801 bitmap_clear_bit (graph->succs[j], from);
802 bitmap_set_bit (graph->succs[j], to);
805 bitmap_ior_into (graph->preds[to],
809 /* Merge all the successor edges. */
810 if (graph->succs[from])
812 if (!graph->succs[to])
813 graph->succs[to] = BITMAP_ALLOC (&ptabitmap_obstack);
814 EXECUTE_IF_SET_IN_BITMAP (graph->succs[from], 0, j, bi)
816 bitmap_clear_bit (graph->preds[j], from);
817 bitmap_set_bit (graph->preds[j], to);
819 bitmap_ior_into (graph->succs[to],
823 clear_edges_for_node (graph, from);
826 /* Add a graph edge to GRAPH, going from TO to FROM if
827 it doesn't exist in the graph already.
828 Return false if the edge already existed, true otherwise. */
831 add_graph_edge (constraint_graph_t graph, unsigned int to,
842 if (!graph->preds[to])
843 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
844 if (!graph->succs[from])
845 graph->succs[from] = BITMAP_ALLOC (&ptabitmap_obstack);
846 if (!bitmap_bit_p (graph->succs[from], to))
851 bitmap_set_bit (graph->preds[to], from);
852 bitmap_set_bit (graph->succs[from], to);
859 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
862 valid_graph_edge (constraint_graph_t graph, unsigned int src,
865 return (graph->succs[dest]
866 && bitmap_bit_p (graph->succs[dest], src));
869 /* Build the constraint graph. */
872 build_constraint_graph (void)
878 graph = XNEW (struct constraint_graph);
879 graph_size = VEC_length (varinfo_t, varmap) + 1;
880 graph->succs = XCNEWVEC (bitmap, graph_size);
881 graph->preds = XCNEWVEC (bitmap, graph_size);
883 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
885 struct constraint_expr lhs = c->lhs;
886 struct constraint_expr rhs = c->rhs;
887 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
888 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
890 if (lhs.type == DEREF)
892 /* *x = y or *x = &y (complex) */
893 if (rhs.type == ADDRESSOF || rhsvar > anything_id)
894 insert_into_complex (lhsvar, c);
896 else if (rhs.type == DEREF)
898 /* !special var= *y */
899 if (!(get_varinfo (lhsvar)->is_special_var))
900 insert_into_complex (rhsvar, c);
902 else if (rhs.type == ADDRESSOF || rhs.type == INCLUDES)
905 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
907 else if (lhsvar > anything_id)
909 /* Ignore self edges, as they can't possibly contribute
911 if (lhsvar != rhsvar || rhs.offset != 0 || lhs.offset != 0)
913 if (rhs.offset != 0 || lhs.offset != 0)
914 insert_into_complex (rhsvar, c);
916 add_graph_edge (graph, lhs.var, rhs.var);
924 /* Changed variables on the last iteration. */
925 static unsigned int changed_count;
926 static sbitmap changed;
929 DEF_VEC_ALLOC_I(unsigned,heap);
932 /* Strongly Connected Component visitation info. */
937 sbitmap in_component;
939 unsigned int *visited_index;
940 VEC(unsigned,heap) *scc_stack;
941 VEC(unsigned,heap) *unification_queue;
945 /* Recursive routine to find strongly connected components in GRAPH.
946 SI is the SCC info to store the information in, and N is the id of current
947 graph node we are processing.
949 This is Tarjan's strongly connected component finding algorithm, as
950 modified by Nuutila to keep only non-root nodes on the stack.
951 The algorithm can be found in "On finding the strongly connected
952 connected components in a directed graph" by Esko Nuutila and Eljas
953 Soisalon-Soininen, in Information Processing Letters volume 49,
954 number 1, pages 9-14. */
957 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
962 gcc_assert (get_varinfo (n)->node == n);
963 SET_BIT (si->visited, n);
964 RESET_BIT (si->in_component, n);
965 si->visited_index[n] = si->current_index ++;
967 /* Visit all the successors. */
968 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
971 if (!TEST_BIT (si->visited, w))
972 scc_visit (graph, si, w);
973 if (!TEST_BIT (si->in_component, w))
975 unsigned int t = get_varinfo (w)->node;
976 unsigned int nnode = get_varinfo (n)->node;
977 if (si->visited_index[t] < si->visited_index[nnode])
978 get_varinfo (n)->node = t;
982 /* See if any components have been identified. */
983 if (get_varinfo (n)->node == n)
985 unsigned int t = si->visited_index[n];
986 SET_BIT (si->in_component, n);
987 while (VEC_length (unsigned, si->scc_stack) != 0
988 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
990 unsigned int w = VEC_pop (unsigned, si->scc_stack);
991 get_varinfo (w)->node = n;
992 SET_BIT (si->in_component, w);
993 /* Mark this node for collapsing. */
994 VEC_safe_push (unsigned, heap, si->unification_queue, w);
998 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1002 /* Collapse two variables into one variable, merging solutions if
1006 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1007 bool merge_solutions)
1009 bitmap tosol, fromsol;
1011 merge_graph_nodes (graph, to, from);
1012 condense_varmap_nodes (to, from);
1013 if (merge_solutions)
1015 tosol = get_varinfo (to)->solution;
1016 fromsol = get_varinfo (from)->solution;
1017 bitmap_ior_into (tosol, fromsol);
1018 BITMAP_FREE (fromsol);
1021 if (valid_graph_edge (graph, to, to))
1023 if (graph->preds[to])
1025 bitmap_clear_bit (graph->preds[to], to);
1026 bitmap_clear_bit (graph->succs[to], to);
1032 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1033 SI is the Strongly Connected Components information structure that tells us
1034 what components to unify.
1035 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1036 count should be updated to reflect the unification. */
1039 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1040 bool update_changed)
1043 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1046 /* We proceed as follows:
1048 For each component in the queue (components are delineated by
1049 when current_queue_element->node != next_queue_element->node):
1051 rep = representative node for component
1053 For each node (tounify) to be unified in the component,
1054 merge the solution for tounify into tmp bitmap
1056 clear solution for tounify
1058 merge edges from tounify into rep
1060 merge complex constraints from tounify into rep
1062 update changed count to note that tounify will never change
1065 Merge tmp into solution for rep, marking rep changed if this
1066 changed rep's solution.
1068 Delete any self-edges we now have for rep. */
1069 while (i != VEC_length (unsigned, si->unification_queue))
1071 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1072 unsigned int n = get_varinfo (tounify)->node;
1074 if (dump_file && (dump_flags & TDF_DETAILS))
1075 fprintf (dump_file, "Unifying %s to %s\n",
1076 get_varinfo (tounify)->name,
1077 get_varinfo (n)->name);
1079 stats.unified_vars_dynamic++;
1081 stats.unified_vars_static++;
1082 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1083 collapse_nodes (graph, n, tounify, false);
1085 if (update_changed && TEST_BIT (changed, tounify))
1087 RESET_BIT (changed, tounify);
1088 if (!TEST_BIT (changed, n))
1089 SET_BIT (changed, n);
1092 gcc_assert (changed_count > 0);
1097 bitmap_clear (get_varinfo (tounify)->solution);
1100 /* If we've either finished processing the entire queue, or
1101 finished processing all nodes for component n, update the solution for
1103 if (i == VEC_length (unsigned, si->unification_queue)
1104 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1106 /* If the solution changes because of the merging, we need to mark
1107 the variable as changed. */
1108 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1110 if (update_changed && !TEST_BIT (changed, n))
1112 SET_BIT (changed, n);
1118 if (valid_graph_edge (graph, n, n))
1120 if (graph->succs[n])
1122 if (graph->preds[n])
1123 bitmap_clear_bit (graph->preds[n], n);
1124 bitmap_clear_bit (graph->succs[n], n);
1133 /* Information needed to compute the topological ordering of a graph. */
1137 /* sbitmap of visited nodes. */
1139 /* Array that stores the topological order of the graph, *in
1141 VEC(unsigned,heap) *topo_order;
1145 /* Initialize and return a topological info structure. */
1147 static struct topo_info *
1148 init_topo_info (void)
1150 size_t size = VEC_length (varinfo_t, varmap);
1151 struct topo_info *ti = XNEW (struct topo_info);
1152 ti->visited = sbitmap_alloc (size);
1153 sbitmap_zero (ti->visited);
1154 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1159 /* Free the topological sort info pointed to by TI. */
1162 free_topo_info (struct topo_info *ti)
1164 sbitmap_free (ti->visited);
1165 VEC_free (unsigned, heap, ti->topo_order);
1169 /* Visit the graph in topological order, and store the order in the
1170 topo_info structure. */
1173 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1180 SET_BIT (ti->visited, n);
1181 temp = graph->succs[n];
1184 EXECUTE_IF_SET_IN_BITMAP (temp, 0, j, bi)
1186 if (!TEST_BIT (ti->visited, j))
1187 topo_visit (graph, ti, j);
1189 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1192 /* Return true if variable N + OFFSET is a legal field of N. */
1195 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1197 varinfo_t ninfo = get_varinfo (n);
1199 /* For things we've globbed to single variables, any offset into the
1200 variable acts like the entire variable, so that it becomes offset
1202 if (ninfo->is_special_var
1203 || ninfo->is_artificial_var
1204 || ninfo->is_unknown_size_var)
1209 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1212 /* Process a constraint C that represents *x = &y. */
1215 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1216 constraint_t c, bitmap delta)
1218 unsigned int rhs = c->rhs.var;
1222 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1223 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1225 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1226 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
1228 /* *x != NULL && *x != ANYTHING*/
1232 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1234 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1238 sol = get_varinfo (t)->solution;
1239 if (!bitmap_bit_p (sol, rhs))
1241 bitmap_set_bit (sol, rhs);
1242 if (!TEST_BIT (changed, t))
1244 SET_BIT (changed, t);
1249 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1250 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1255 /* Process a constraint C that represents x = *y, using DELTA as the
1256 starting solution. */
1259 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1262 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1264 bitmap sol = get_varinfo (lhs)->solution;
1268 if (bitmap_bit_p (delta, anything_id))
1270 flag = !bitmap_bit_p (sol, anything_id);
1272 bitmap_set_bit (sol, anything_id);
1275 /* For each variable j in delta (Sol(y)), add
1276 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1277 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1279 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1280 if (type_safe (j, &roffset))
1283 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1286 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1291 /* Adding edges from the special vars is pointless.
1292 They don't have sets that can change. */
1293 if (get_varinfo (t) ->is_special_var)
1294 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1295 else if (add_graph_edge (graph, lhs, t))
1296 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1298 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1299 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1304 /* If the LHS solution changed, mark the var as changed. */
1307 get_varinfo (lhs)->solution = sol;
1308 if (!TEST_BIT (changed, lhs))
1310 SET_BIT (changed, lhs);
1316 /* Process a constraint C that represents *x = y. */
1319 do_ds_constraint (constraint_t c, bitmap delta)
1321 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1322 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1323 bitmap sol = get_varinfo (rhs)->solution;
1327 if (bitmap_bit_p (sol, anything_id))
1329 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1331 varinfo_t jvi = get_varinfo (j);
1333 unsigned int loff = c->lhs.offset;
1334 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
1337 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1342 if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id))
1344 bitmap_set_bit (get_varinfo (t)->solution, anything_id);
1345 if (!TEST_BIT (changed, t))
1347 SET_BIT (changed, t);
1355 /* For each member j of delta (Sol(x)), add an edge from y to j and
1356 union Sol(y) into Sol(j) */
1357 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1359 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1360 if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var))
1364 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1367 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1371 tmp = get_varinfo (t)->solution;
1373 if (set_union_with_increment (tmp, sol, roff))
1375 get_varinfo (t)->solution = tmp;
1377 sol = get_varinfo (rhs)->solution;
1378 if (!TEST_BIT (changed, t))
1380 SET_BIT (changed, t);
1385 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1386 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1390 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1391 constraint (IE *x = &y, x = *y, and *x = y). */
1394 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1396 if (c->lhs.type == DEREF)
1398 if (c->rhs.type == ADDRESSOF)
1401 do_da_constraint (graph, c, delta);
1406 do_ds_constraint (c, delta);
1409 else if (c->rhs.type == DEREF)
1412 if (!(get_varinfo (c->lhs.var)->is_special_var))
1413 do_sd_constraint (graph, c, delta);
1422 gcc_assert(c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1423 t = get_varinfo (c->rhs.var)->node;
1424 solution = get_varinfo (t)->solution;
1425 t = get_varinfo (c->lhs.var)->node;
1426 tmp = get_varinfo (t)->solution;
1428 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1432 get_varinfo (t)->solution = tmp;
1433 if (!TEST_BIT (changed, c->lhs.var))
1435 SET_BIT (changed, c->lhs.var);
1442 /* Initialize and return a new SCC info structure. */
1444 static struct scc_info *
1445 init_scc_info (void)
1447 struct scc_info *si = XNEW (struct scc_info);
1448 size_t size = VEC_length (varinfo_t, varmap);
1450 si->current_index = 0;
1451 si->visited = sbitmap_alloc (size);
1452 sbitmap_zero (si->visited);
1453 si->in_component = sbitmap_alloc (size);
1454 sbitmap_ones (si->in_component);
1455 si->visited_index = XCNEWVEC (unsigned int, size + 1);
1456 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1457 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1461 /* Free an SCC info structure pointed to by SI */
1464 free_scc_info (struct scc_info *si)
1466 sbitmap_free (si->visited);
1467 sbitmap_free (si->in_component);
1468 free (si->visited_index);
1469 VEC_free (unsigned, heap, si->scc_stack);
1470 VEC_free (unsigned, heap, si->unification_queue);
1475 /* Find cycles in GRAPH that occur, using strongly connected components, and
1476 collapse the cycles into a single representative node. if UPDATE_CHANGED
1477 is true, then update the changed sbitmap to note those nodes whose
1478 solutions have changed as a result of collapsing. */
1481 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1484 unsigned int size = VEC_length (varinfo_t, varmap);
1485 struct scc_info *si = init_scc_info ();
1487 for (i = 0; i != size; ++i)
1488 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1489 scc_visit (graph, si, i);
1491 process_unification_queue (graph, si, update_changed);
1495 /* Compute a topological ordering for GRAPH, and store the result in the
1496 topo_info structure TI. */
1499 compute_topo_order (constraint_graph_t graph,
1500 struct topo_info *ti)
1503 unsigned int size = VEC_length (varinfo_t, varmap);
1505 for (i = 0; i != size; ++i)
1506 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1507 topo_visit (graph, ti, i);
1510 /* Perform offline variable substitution.
1512 This is a linear time way of identifying variables that must have
1513 equivalent points-to sets, including those caused by static cycles,
1514 and single entry subgraphs, in the constraint graph.
1516 The technique is described in "Off-line variable substitution for
1517 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1518 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1521 perform_var_substitution (constraint_graph_t graph)
1523 struct topo_info *ti = init_topo_info ();
1525 bitmap_obstack_initialize (&iteration_obstack);
1526 /* Compute the topological ordering of the graph, then visit each
1527 node in topological order. */
1528 compute_topo_order (graph, ti);
1530 while (VEC_length (unsigned, ti->topo_order) != 0)
1532 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1533 varinfo_t vi = get_varinfo (i);
1534 bool okay_to_elim = false;
1535 unsigned int root = VEC_length (varinfo_t, varmap);
1540 /* We can't eliminate things whose address is taken, or which is
1541 the target of a dereference. */
1542 if (vi->address_taken || vi->indirect_target)
1545 /* See if all predecessors of I are ripe for elimination */
1546 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, k, bi)
1549 w = get_varinfo (k)->node;
1551 /* We can't eliminate the node if one of the predecessors is
1552 part of a different strongly connected component. */
1556 okay_to_elim = true;
1560 okay_to_elim = false;
1564 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1565 then Solution(i) is a subset of Solution (w), where w is a
1566 predecessor in the graph.
1567 Corollary: If all predecessors of i have the same
1568 points-to set, then i has that same points-to set as
1569 those predecessors. */
1570 tmp = BITMAP_ALLOC (NULL);
1571 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1572 get_varinfo (w)->solution);
1573 if (!bitmap_empty_p (tmp))
1575 okay_to_elim = false;
1582 /* See if the root is different than the original node.
1583 If so, we've found an equivalence. */
1584 if (root != get_varinfo (i)->node && okay_to_elim)
1586 /* Found an equivalence */
1587 get_varinfo (i)->node = root;
1588 collapse_nodes (graph, root, i, true);
1589 if (dump_file && (dump_flags & TDF_DETAILS))
1590 fprintf (dump_file, "Collapsing %s into %s\n",
1591 get_varinfo (i)->name,
1592 get_varinfo (root)->name);
1593 stats.collapsed_vars++;
1597 bitmap_obstack_release (&iteration_obstack);
1598 free_topo_info (ti);
1601 /* Solve the constraint graph GRAPH using our worklist solver.
1602 This is based on the PW* family of solvers from the "Efficient Field
1603 Sensitive Pointer Analysis for C" paper.
1604 It works by iterating over all the graph nodes, processing the complex
1605 constraints and propagating the copy constraints, until everything stops
1606 changed. This corresponds to steps 6-8 in the solving list given above. */
1609 solve_graph (constraint_graph_t graph)
1611 unsigned int size = VEC_length (varinfo_t, varmap);
1614 changed_count = size;
1615 changed = sbitmap_alloc (size);
1616 sbitmap_ones (changed);
1618 /* The already collapsed/unreachable nodes will never change, so we
1619 need to account for them in changed_count. */
1620 for (i = 0; i < size; i++)
1621 if (get_varinfo (i)->node != i)
1624 while (changed_count > 0)
1627 struct topo_info *ti = init_topo_info ();
1630 bitmap_obstack_initialize (&iteration_obstack);
1634 /* We already did cycle elimination once, when we did
1635 variable substitution, so we don't need it again for the
1637 if (stats.iterations > 1)
1638 find_and_collapse_graph_cycles (graph, true);
1643 compute_topo_order (graph, ti);
1645 while (VEC_length (unsigned, ti->topo_order) != 0)
1647 i = VEC_pop (unsigned, ti->topo_order);
1648 gcc_assert (get_varinfo (i)->node == i);
1650 /* If the node has changed, we need to process the
1651 complex constraints and outgoing edges again. */
1652 if (TEST_BIT (changed, i))
1658 VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
1659 bool solution_empty;
1661 RESET_BIT (changed, i);
1664 solution = get_varinfo (i)->solution;
1665 solution_empty = bitmap_empty_p (solution);
1667 /* Process the complex constraints */
1668 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
1670 /* The only complex constraint that can change our
1671 solution to non-empty, given an empty solution,
1672 is a constraint where the lhs side is receiving
1673 some set from elsewhere. */
1674 if (!solution_empty || c->lhs.type != DEREF)
1675 do_complex_constraint (graph, c, solution);
1678 solution_empty = bitmap_empty_p (solution);
1680 if (!solution_empty)
1682 /* Propagate solution to all successors. */
1683 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
1686 bitmap tmp = get_varinfo (j)->solution;
1689 gcc_assert (get_varinfo (j)->node == j);
1691 flag = set_union_with_increment (tmp, solution, 0);
1695 get_varinfo (j)->solution = tmp;
1696 if (!TEST_BIT (changed, j))
1698 SET_BIT (changed, j);
1706 free_topo_info (ti);
1707 bitmap_obstack_release (&iteration_obstack);
1710 sbitmap_free (changed);
1714 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
1716 /* Map from trees to variable ids. */
1717 static htab_t id_for_tree;
1719 typedef struct tree_id
1725 /* Hash a tree id structure. */
1728 tree_id_hash (const void *p)
1730 const tree_id_t ta = (tree_id_t) p;
1731 return htab_hash_pointer (ta->t);
1734 /* Return true if the tree in P1 and the tree in P2 are the same. */
1737 tree_id_eq (const void *p1, const void *p2)
1739 const tree_id_t ta1 = (tree_id_t) p1;
1740 const tree_id_t ta2 = (tree_id_t) p2;
1741 return ta1->t == ta2->t;
1744 /* Insert ID as the variable id for tree T in the hashtable. */
1747 insert_id_for_tree (tree t, int id)
1750 struct tree_id finder;
1754 slot = htab_find_slot (id_for_tree, &finder, INSERT);
1755 gcc_assert (*slot == NULL);
1756 new_pair = XNEW (struct tree_id);
1759 *slot = (void *)new_pair;
1762 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
1763 exist in the hash table, return false, otherwise, return true and
1764 set *ID to the id we found. */
1767 lookup_id_for_tree (tree t, unsigned int *id)
1770 struct tree_id finder;
1773 pair = htab_find (id_for_tree, &finder);
1780 /* Return a printable name for DECL */
1783 alias_get_name (tree decl)
1785 const char *res = get_name (decl);
1787 int num_printed = 0;
1796 if (TREE_CODE (decl) == SSA_NAME)
1798 num_printed = asprintf (&temp, "%s_%u",
1799 alias_get_name (SSA_NAME_VAR (decl)),
1800 SSA_NAME_VERSION (decl));
1802 else if (DECL_P (decl))
1804 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
1806 if (num_printed > 0)
1808 res = ggc_strdup (temp);
1814 /* Find the variable id for tree T in the hashtable.
1815 If T doesn't exist in the hash table, create an entry for it. */
1818 get_id_for_tree (tree t)
1821 struct tree_id finder;
1824 pair = htab_find (id_for_tree, &finder);
1826 return create_variable_info_for (t, alias_get_name (t));
1831 /* Get a constraint expression from an SSA_VAR_P node. */
1833 static struct constraint_expr
1834 get_constraint_exp_from_ssa_var (tree t)
1836 struct constraint_expr cexpr;
1838 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
1840 /* For parameters, get at the points-to set for the actual parm
1842 if (TREE_CODE (t) == SSA_NAME
1843 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
1844 && SSA_NAME_IS_DEFAULT_DEF (t))
1845 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
1847 cexpr.type = SCALAR;
1849 cexpr.var = get_id_for_tree (t);
1850 /* If we determine the result is "anything", and we know this is readonly,
1851 say it points to readonly memory instead. */
1852 if (cexpr.var == anything_id && TREE_READONLY (t))
1854 cexpr.type = INCLUDES;
1855 cexpr.var = readonly_id;
1862 /* Process a completed constraint T, and add it to the constraint
1866 process_constraint (constraint_t t)
1868 struct constraint_expr rhs = t->rhs;
1869 struct constraint_expr lhs = t->lhs;
1871 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
1872 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
1874 gcc_assert (lhs.type != INCLUDES);
1876 if (lhs.type == DEREF)
1877 get_varinfo (lhs.var)->directly_dereferenced = true;
1878 if (rhs.type == DEREF)
1879 get_varinfo (rhs.var)->directly_dereferenced = true;
1881 if (!use_field_sensitive)
1887 /* ANYTHING == ANYTHING is pointless. */
1888 if (lhs.var == anything_id && rhs.var == anything_id)
1891 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
1892 else if (lhs.var == anything_id
1893 && (lhs.type == INCLUDES || lhs.type == ADDRESSOF))
1898 process_constraint (t);
1900 /* This can happen in our IR with things like n->a = *p */
1901 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
1903 /* Split into tmp = *rhs, *lhs = tmp */
1904 tree rhsdecl = get_varinfo (rhs.var)->decl;
1905 tree pointertype = TREE_TYPE (rhsdecl);
1906 tree pointedtotype = TREE_TYPE (pointertype);
1907 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
1908 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
1910 /* If this is an aggregate of known size, we should have passed
1911 this off to do_structure_copy, and it should have broken it
1913 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
1914 || get_varinfo (rhs.var)->is_unknown_size_var);
1916 process_constraint (new_constraint (tmplhs, rhs));
1917 process_constraint (new_constraint (lhs, tmplhs));
1919 else if (rhs.type == ADDRESSOF)
1922 gcc_assert (rhs.offset == 0);
1924 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
1925 vi->address_taken = true;
1927 VEC_safe_push (constraint_t, heap, constraints, t);
1931 if (lhs.type != DEREF && rhs.type == DEREF)
1932 get_varinfo (lhs.var)->indirect_target = true;
1933 VEC_safe_push (constraint_t, heap, constraints, t);
1937 /* Return true if T is a variable of a type that could contain
1941 could_have_pointers (tree t)
1943 tree type = TREE_TYPE (t);
1945 if (POINTER_TYPE_P (type) || AGGREGATE_TYPE_P (type)
1946 || TREE_CODE (type) == COMPLEX_TYPE)
1951 /* Return the position, in bits, of FIELD_DECL from the beginning of its
1954 static unsigned HOST_WIDE_INT
1955 bitpos_of_field (const tree fdecl)
1958 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
1959 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
1962 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
1963 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
1967 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
1968 overlaps with a field at [FIELDPOS, FIELDSIZE] */
1971 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
1972 const unsigned HOST_WIDE_INT fieldsize,
1973 const unsigned HOST_WIDE_INT accesspos,
1974 const unsigned HOST_WIDE_INT accesssize)
1976 if (fieldpos == accesspos && fieldsize == accesssize)
1978 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
1980 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
1986 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
1989 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results)
1992 HOST_WIDE_INT bitsize = -1;
1993 HOST_WIDE_INT bitmaxsize = -1;
1994 HOST_WIDE_INT bitpos;
1996 struct constraint_expr *result;
1997 unsigned int beforelength = VEC_length (ce_s, *results);
1999 /* Some people like to do cute things like take the address of
2002 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2003 forzero = TREE_OPERAND (forzero, 0);
2005 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2007 struct constraint_expr temp;
2010 temp.var = integer_id;
2012 VEC_safe_push (ce_s, heap, *results, &temp);
2016 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2018 /* String constants are readonly, so there is nothing to really do
2020 if (TREE_CODE (t) == STRING_CST)
2023 get_constraint_for (t, results);
2024 result = VEC_last (ce_s, *results);
2025 result->offset = bitpos;
2027 gcc_assert (beforelength + 1 == VEC_length (ce_s, *results));
2029 /* This can also happen due to weird offsetof type macros. */
2030 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2031 result->type = SCALAR;
2033 if (result->type == SCALAR)
2035 /* In languages like C, you can access one past the end of an
2036 array. You aren't allowed to dereference it, so we can
2037 ignore this constraint. When we handle pointer subtraction,
2038 we may have to do something cute here. */
2040 if (result->offset < get_varinfo (result->var)->fullsize
2043 /* It's also not true that the constraint will actually start at the
2044 right offset, it may start in some padding. We only care about
2045 setting the constraint to the first actual field it touches, so
2048 for (curr = get_varinfo (result->var); curr; curr = curr->next)
2050 if (offset_overlaps_with_access (curr->offset, curr->size,
2051 result->offset, bitmaxsize))
2053 result->var = curr->id;
2057 /* assert that we found *some* field there. The user couldn't be
2058 accessing *only* padding. */
2059 /* Still the user could access one past the end of an array
2060 embedded in a struct resulting in accessing *only* padding. */
2061 gcc_assert (curr || ref_contains_array_ref (orig_t));
2063 else if (bitmaxsize == 0)
2065 if (dump_file && (dump_flags & TDF_DETAILS))
2066 fprintf (dump_file, "Access to zero-sized part of variable,"
2070 if (dump_file && (dump_flags & TDF_DETAILS))
2071 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2078 /* Dereference the constraint expression CONS, and return the result.
2079 DEREF (ADDRESSOF) = SCALAR
2080 DEREF (SCALAR) = DEREF
2081 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2082 This is needed so that we can handle dereferencing DEREF constraints. */
2085 do_deref (VEC (ce_s, heap) **constraints)
2087 struct constraint_expr *c;
2090 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2092 if (c->type == SCALAR)
2094 else if (c->type == ADDRESSOF)
2096 else if (c->type == DEREF)
2098 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
2099 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2100 process_constraint (new_constraint (tmplhs, *c));
2101 c->var = tmplhs.var;
2108 /* Given a tree T, return the constraint expression for it. */
2111 get_constraint_for (tree t, VEC (ce_s, heap) **results)
2113 struct constraint_expr temp;
2115 /* x = integer is all glommed to a single variable, which doesn't
2116 point to anything by itself. That is, of course, unless it is an
2117 integer constant being treated as a pointer, in which case, we
2118 will return that this is really the addressof anything. This
2119 happens below, since it will fall into the default case. The only
2120 case we know something about an integer treated like a pointer is
2121 when it is the NULL pointer, and then we just say it points to
2123 if (TREE_CODE (t) == INTEGER_CST
2124 && !POINTER_TYPE_P (TREE_TYPE (t)))
2126 temp.var = integer_id;
2129 VEC_safe_push (ce_s, heap, *results, &temp);
2132 else if (TREE_CODE (t) == INTEGER_CST
2133 && integer_zerop (t))
2135 temp.var = nothing_id;
2136 temp.type = ADDRESSOF;
2138 VEC_safe_push (ce_s, heap, *results, &temp);
2142 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2144 case tcc_expression:
2146 switch (TREE_CODE (t))
2150 struct constraint_expr *c;
2152 tree exp = TREE_OPERAND (t, 0);
2153 tree pttype = TREE_TYPE (TREE_TYPE (t));
2155 get_constraint_for (exp, results);
2156 /* Make sure we capture constraints to all elements
2158 if ((handled_component_p (exp)
2159 && ref_contains_array_ref (exp))
2160 || TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE)
2162 struct constraint_expr *origrhs;
2164 struct constraint_expr tmp;
2166 if (VEC_length (ce_s, *results) == 0)
2169 gcc_assert (VEC_length (ce_s, *results) == 1);
2170 origrhs = VEC_last (ce_s, *results);
2172 VEC_pop (ce_s, *results);
2173 origvar = get_varinfo (origrhs->var);
2174 for (; origvar; origvar = origvar->next)
2176 tmp.var = origvar->id;
2177 VEC_safe_push (ce_s, heap, *results, &tmp);
2180 else if (VEC_length (ce_s, *results) == 1
2181 && (AGGREGATE_TYPE_P (pttype)
2182 || TREE_CODE (pttype) == COMPLEX_TYPE))
2184 struct constraint_expr *origrhs;
2186 struct constraint_expr tmp;
2188 gcc_assert (VEC_length (ce_s, *results) == 1);
2189 origrhs = VEC_last (ce_s, *results);
2191 VEC_pop (ce_s, *results);
2192 origvar = get_varinfo (origrhs->var);
2193 for (; origvar; origvar = origvar->next)
2195 tmp.var = origvar->id;
2196 VEC_safe_push (ce_s, heap, *results, &tmp);
2200 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2202 if (c->type == DEREF)
2205 c->type = ADDRESSOF;
2211 /* XXX: In interprocedural mode, if we didn't have the
2212 body, we would need to do *each pointer argument =
2214 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2217 tree heapvar = heapvar_lookup (t);
2219 if (heapvar == NULL)
2221 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2222 DECL_EXTERNAL (heapvar) = 1;
2223 get_var_ann (heapvar)->is_heapvar = 1;
2224 if (gimple_referenced_vars (cfun))
2225 add_referenced_var (heapvar);
2226 heapvar_insert (t, heapvar);
2229 temp.var = create_variable_info_for (heapvar,
2230 alias_get_name (heapvar));
2232 vi = get_varinfo (temp.var);
2233 vi->is_artificial_var = 1;
2234 vi->is_heap_var = 1;
2235 temp.type = INCLUDES;
2237 VEC_safe_push (ce_s, heap, *results, &temp);
2242 temp.var = anything_id;
2245 VEC_safe_push (ce_s, heap, *results, &temp);
2251 temp.type = ADDRESSOF;
2252 temp.var = anything_id;
2254 VEC_safe_push (ce_s, heap, *results, &temp);
2261 switch (TREE_CODE (t))
2265 get_constraint_for (TREE_OPERAND (t, 0), results);
2270 case ARRAY_RANGE_REF:
2272 get_constraint_for_component_ref (t, results);
2276 temp.type = ADDRESSOF;
2277 temp.var = anything_id;
2279 VEC_safe_push (ce_s, heap, *results, &temp);
2286 switch (TREE_CODE (t))
2290 case NON_LVALUE_EXPR:
2292 tree op = TREE_OPERAND (t, 0);
2294 /* Cast from non-pointer to pointers are bad news for us.
2295 Anything else, we see through */
2296 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2297 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2299 get_constraint_for (op, results);
2307 temp.type = ADDRESSOF;
2308 temp.var = anything_id;
2310 VEC_safe_push (ce_s, heap, *results, &temp);
2315 case tcc_exceptional:
2317 switch (TREE_CODE (t))
2321 get_constraint_for (PHI_RESULT (t), results);
2327 struct constraint_expr temp;
2328 temp = get_constraint_exp_from_ssa_var (t);
2329 VEC_safe_push (ce_s, heap, *results, &temp);
2335 temp.type = ADDRESSOF;
2336 temp.var = anything_id;
2338 VEC_safe_push (ce_s, heap, *results, &temp);
2343 case tcc_declaration:
2345 struct constraint_expr temp;
2346 temp = get_constraint_exp_from_ssa_var (t);
2347 VEC_safe_push (ce_s, heap, *results, &temp);
2352 temp.type = ADDRESSOF;
2353 temp.var = anything_id;
2355 VEC_safe_push (ce_s, heap, *results, &temp);
2362 /* Handle the structure copy case where we have a simple structure copy
2363 between LHS and RHS that is of SIZE (in bits)
2365 For each field of the lhs variable (lhsfield)
2366 For each field of the rhs variable at lhsfield.offset (rhsfield)
2367 add the constraint lhsfield = rhsfield
2369 If we fail due to some kind of type unsafety or other thing we
2370 can't handle, return false. We expect the caller to collapse the
2371 variable in that case. */
2374 do_simple_structure_copy (const struct constraint_expr lhs,
2375 const struct constraint_expr rhs,
2376 const unsigned HOST_WIDE_INT size)
2378 varinfo_t p = get_varinfo (lhs.var);
2379 unsigned HOST_WIDE_INT pstart, last;
2381 last = p->offset + size;
2382 for (; p && p->offset < last; p = p->next)
2385 struct constraint_expr templhs = lhs;
2386 struct constraint_expr temprhs = rhs;
2387 unsigned HOST_WIDE_INT fieldoffset;
2389 templhs.var = p->id;
2390 q = get_varinfo (temprhs.var);
2391 fieldoffset = p->offset - pstart;
2392 q = first_vi_for_offset (q, q->offset + fieldoffset);
2395 temprhs.var = q->id;
2396 process_constraint (new_constraint (templhs, temprhs));
2402 /* Handle the structure copy case where we have a structure copy between a
2403 aggregate on the LHS and a dereference of a pointer on the RHS
2404 that is of SIZE (in bits)
2406 For each field of the lhs variable (lhsfield)
2407 rhs.offset = lhsfield->offset
2408 add the constraint lhsfield = rhs
2412 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2413 const struct constraint_expr rhs,
2414 const unsigned HOST_WIDE_INT size)
2416 varinfo_t p = get_varinfo (lhs.var);
2417 unsigned HOST_WIDE_INT pstart,last;
2419 last = p->offset + size;
2421 for (; p && p->offset < last; p = p->next)
2424 struct constraint_expr templhs = lhs;
2425 struct constraint_expr temprhs = rhs;
2426 unsigned HOST_WIDE_INT fieldoffset;
2429 if (templhs.type == SCALAR)
2430 templhs.var = p->id;
2432 templhs.offset = p->offset;
2434 q = get_varinfo (temprhs.var);
2435 fieldoffset = p->offset - pstart;
2436 temprhs.offset += fieldoffset;
2437 process_constraint (new_constraint (templhs, temprhs));
2441 /* Handle the structure copy case where we have a structure copy
2442 between a aggregate on the RHS and a dereference of a pointer on
2443 the LHS that is of SIZE (in bits)
2445 For each field of the rhs variable (rhsfield)
2446 lhs.offset = rhsfield->offset
2447 add the constraint lhs = rhsfield
2451 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2452 const struct constraint_expr rhs,
2453 const unsigned HOST_WIDE_INT size)
2455 varinfo_t p = get_varinfo (rhs.var);
2456 unsigned HOST_WIDE_INT pstart,last;
2458 last = p->offset + size;
2460 for (; p && p->offset < last; p = p->next)
2463 struct constraint_expr templhs = lhs;
2464 struct constraint_expr temprhs = rhs;
2465 unsigned HOST_WIDE_INT fieldoffset;
2468 if (temprhs.type == SCALAR)
2469 temprhs.var = p->id;
2471 temprhs.offset = p->offset;
2473 q = get_varinfo (templhs.var);
2474 fieldoffset = p->offset - pstart;
2475 templhs.offset += fieldoffset;
2476 process_constraint (new_constraint (templhs, temprhs));
2480 /* Sometimes, frontends like to give us bad type information. This
2481 function will collapse all the fields from VAR to the end of VAR,
2482 into VAR, so that we treat those fields as a single variable.
2483 We return the variable they were collapsed into. */
2486 collapse_rest_of_var (unsigned int var)
2488 varinfo_t currvar = get_varinfo (var);
2491 for (field = currvar->next; field; field = field->next)
2494 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
2495 field->name, currvar->name);
2497 gcc_assert (!field->collapsed_to);
2498 field->collapsed_to = currvar;
2501 currvar->next = NULL;
2502 currvar->size = currvar->fullsize - currvar->offset;
2507 /* Handle aggregate copies by expanding into copies of the respective
2508 fields of the structures. */
2511 do_structure_copy (tree lhsop, tree rhsop)
2513 struct constraint_expr lhs, rhs, tmp;
2514 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
2516 unsigned HOST_WIDE_INT lhssize;
2517 unsigned HOST_WIDE_INT rhssize;
2519 get_constraint_for (lhsop, &lhsc);
2520 get_constraint_for (rhsop, &rhsc);
2521 gcc_assert (VEC_length (ce_s, lhsc) == 1);
2522 gcc_assert (VEC_length (ce_s, rhsc) == 1);
2523 lhs = *(VEC_last (ce_s, lhsc));
2524 rhs = *(VEC_last (ce_s, rhsc));
2526 VEC_free (ce_s, heap, lhsc);
2527 VEC_free (ce_s, heap, rhsc);
2529 /* If we have special var = x, swap it around. */
2530 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2537 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2538 possible it's something we could handle. However, most cases falling
2539 into this are dealing with transparent unions, which are slightly
2541 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2543 rhs.type = ADDRESSOF;
2544 rhs.var = anything_id;
2547 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2548 that special var. */
2549 if (rhs.var <= integer_id)
2551 for (p = get_varinfo (lhs.var); p; p = p->next)
2553 struct constraint_expr templhs = lhs;
2554 struct constraint_expr temprhs = rhs;
2556 if (templhs.type == SCALAR )
2557 templhs.var = p->id;
2559 templhs.offset += p->offset;
2560 process_constraint (new_constraint (templhs, temprhs));
2565 tree rhstype = TREE_TYPE (rhsop);
2566 tree lhstype = TREE_TYPE (lhsop);
2570 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
2571 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
2573 /* If we have a variably sized types on the rhs or lhs, and a deref
2574 constraint, add the constraint, lhsconstraint = &ANYTHING.
2575 This is conservatively correct because either the lhs is an unknown
2576 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2577 constraint, and every variable it can point to must be unknown sized
2578 anyway, so we don't need to worry about fields at all. */
2579 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2580 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2582 rhs.var = anything_id;
2583 rhs.type = ADDRESSOF;
2585 process_constraint (new_constraint (lhs, rhs));
2589 /* The size only really matters insofar as we don't set more or less of
2590 the variable. If we hit an unknown size var, the size should be the
2591 whole darn thing. */
2592 if (get_varinfo (rhs.var)->is_unknown_size_var)
2595 rhssize = TREE_INT_CST_LOW (rhstypesize);
2597 if (get_varinfo (lhs.var)->is_unknown_size_var)
2600 lhssize = TREE_INT_CST_LOW (lhstypesize);
2603 if (rhs.type == SCALAR && lhs.type == SCALAR)
2605 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
2607 lhs.var = collapse_rest_of_var (lhs.var);
2608 rhs.var = collapse_rest_of_var (rhs.var);
2613 process_constraint (new_constraint (lhs, rhs));
2616 else if (lhs.type != DEREF && rhs.type == DEREF)
2617 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2618 else if (lhs.type == DEREF && rhs.type != DEREF)
2619 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2622 tree pointedtotype = lhstype;
2625 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2626 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2627 do_structure_copy (tmpvar, rhsop);
2628 do_structure_copy (lhsop, tmpvar);
2633 /* Update related alias information kept in AI. This is used when
2634 building name tags, alias sets and deciding grouping heuristics.
2635 STMT is the statement to process. This function also updates
2636 ADDRESSABLE_VARS. */
2639 update_alias_info (tree stmt, struct alias_info *ai)
2642 use_operand_p use_p;
2644 enum escape_type stmt_escape_type = is_escape_site (stmt);
2646 if (stmt_escape_type == ESCAPE_TO_CALL
2647 || stmt_escape_type == ESCAPE_TO_PURE_CONST)
2649 ai->num_calls_found++;
2650 if (stmt_escape_type == ESCAPE_TO_PURE_CONST)
2651 ai->num_pure_const_calls_found++;
2654 /* Mark all the variables whose address are taken by the statement. */
2655 addr_taken = addresses_taken (stmt);
2658 bitmap_ior_into (gimple_addressable_vars (cfun), addr_taken);
2660 /* If STMT is an escape point, all the addresses taken by it are
2662 if (stmt_escape_type != NO_ESCAPE)
2667 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
2669 tree rvar = referenced_var (i);
2670 if (!unmodifiable_var_p (rvar))
2671 mark_call_clobbered (rvar, stmt_escape_type);
2676 /* Process each operand use. If an operand may be aliased, keep
2677 track of how many times it's being used. For pointers, determine
2678 whether they are dereferenced by the statement, or whether their
2679 value escapes, etc. */
2680 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2684 struct ptr_info_def *pi;
2685 bool is_store, is_potential_deref;
2686 unsigned num_uses, num_derefs;
2688 op = USE_FROM_PTR (use_p);
2690 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2691 to the set of addressable variables. */
2692 if (TREE_CODE (op) == ADDR_EXPR)
2694 bitmap addressable_vars = gimple_addressable_vars (cfun);
2696 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
2697 gcc_assert (addressable_vars);
2699 /* PHI nodes don't have annotations for pinning the set
2700 of addresses taken, so we collect them here.
2702 FIXME, should we allow PHI nodes to have annotations
2703 so that they can be treated like regular statements?
2704 Currently, they are treated as second-class
2706 add_to_addressable_set (TREE_OPERAND (op, 0),
2711 /* Ignore constants. */
2712 if (TREE_CODE (op) != SSA_NAME)
2715 var = SSA_NAME_VAR (op);
2716 v_ann = var_ann (var);
2718 /* The base variable of an SSA name must be a GIMPLE register, and thus
2719 it cannot be aliased. */
2720 gcc_assert (!may_be_aliased (var));
2722 /* We are only interested in pointers. */
2723 if (!POINTER_TYPE_P (TREE_TYPE (op)))
2726 pi = get_ptr_info (op);
2728 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
2729 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
2731 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
2732 VEC_safe_push (tree, heap, ai->processed_ptrs, op);
2735 /* If STMT is a PHI node, then it will not have pointer
2736 dereferences and it will not be an escape point. */
2737 if (TREE_CODE (stmt) == PHI_NODE)
2740 /* Determine whether OP is a dereferenced pointer, and if STMT
2741 is an escape point, whether OP escapes. */
2742 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
2744 /* Handle a corner case involving address expressions of the
2745 form '&PTR->FLD'. The problem with these expressions is that
2746 they do not represent a dereference of PTR. However, if some
2747 other transformation propagates them into an INDIRECT_REF
2748 expression, we end up with '*(&PTR->FLD)' which is folded
2751 So, if the original code had no other dereferences of PTR,
2752 the aliaser will not create memory tags for it, and when
2753 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
2754 memory operations will receive no VDEF/VUSE operands.
2756 One solution would be to have count_uses_and_derefs consider
2757 &PTR->FLD a dereference of PTR. But that is wrong, since it
2758 is not really a dereference but an offset calculation.
2760 What we do here is to recognize these special ADDR_EXPR
2761 nodes. Since these expressions are never GIMPLE values (they
2762 are not GIMPLE invariants), they can only appear on the RHS
2763 of an assignment and their base address is always an
2764 INDIRECT_REF expression. */
2765 is_potential_deref = false;
2766 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
2767 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ADDR_EXPR
2768 && !is_gimple_val (GIMPLE_STMT_OPERAND (stmt, 1)))
2770 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
2771 this represents a potential dereference of PTR. */
2772 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
2773 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2774 if (TREE_CODE (base) == INDIRECT_REF
2775 && TREE_OPERAND (base, 0) == op)
2776 is_potential_deref = true;
2779 if (num_derefs > 0 || is_potential_deref)
2781 /* Mark OP as dereferenced. In a subsequent pass,
2782 dereferenced pointers that point to a set of
2783 variables will be assigned a name tag to alias
2784 all the variables OP points to. */
2785 pi->is_dereferenced = 1;
2787 /* If this is a store operation, mark OP as being
2788 dereferenced to store, otherwise mark it as being
2789 dereferenced to load. */
2791 pointer_set_insert (ai->dereferenced_ptrs_store, var);
2793 pointer_set_insert (ai->dereferenced_ptrs_load, var);
2796 if (stmt_escape_type != NO_ESCAPE && num_derefs < num_uses)
2798 /* If STMT is an escape point and STMT contains at
2799 least one direct use of OP, then the value of OP
2800 escapes and so the pointed-to variables need to
2801 be marked call-clobbered. */
2802 pi->value_escapes_p = 1;
2803 pi->escape_mask |= stmt_escape_type;
2805 /* If the statement makes a function call, assume
2806 that pointer OP will be dereferenced in a store
2807 operation inside the called function. */
2808 if (get_call_expr_in (stmt)
2809 || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
2811 pointer_set_insert (ai->dereferenced_ptrs_store, var);
2812 pi->is_dereferenced = 1;
2817 if (TREE_CODE (stmt) == PHI_NODE)
2820 /* Mark stored variables in STMT as being written to and update the
2821 reference counter for potentially aliased symbols in STMT. */
2822 if (stmt_references_memory_p (stmt) && STORED_SYMS (stmt))
2826 EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi)
2827 pointer_set_insert (ai->written_vars, referenced_var (i));
2832 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
2833 Expressions of the type PTR + CST can be handled in two ways:
2835 1- If the constraint for PTR is ADDRESSOF for a non-structure
2836 variable, then we can use it directly because adding or
2837 subtracting a constant may not alter the original ADDRESSOF
2838 constraint (i.e., pointer arithmetic may not legally go outside
2839 an object's boundaries).
2841 2- If the constraint for PTR is ADDRESSOF for a structure variable,
2842 then if CST is a compile-time constant that can be used as an
2843 offset, we can determine which sub-variable will be pointed-to
2846 Return true if the expression is handled. For any other kind of
2847 expression, return false so that each operand can be added as a
2848 separate constraint by the caller. */
2851 handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr)
2854 struct constraint_expr *c, *c2;
2857 VEC (ce_s, heap) *temp = NULL;
2858 unsigned int rhsoffset = 0;
2860 if (TREE_CODE (expr) != PLUS_EXPR
2861 && TREE_CODE (expr) != MINUS_EXPR)
2864 op0 = TREE_OPERAND (expr, 0);
2865 op1 = TREE_OPERAND (expr, 1);
2867 get_constraint_for (op0, &temp);
2868 if (POINTER_TYPE_P (TREE_TYPE (op0))
2869 && TREE_CODE (op1) == INTEGER_CST
2870 && TREE_CODE (expr) == PLUS_EXPR)
2872 rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
2878 for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
2879 for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
2881 if (c2->type == ADDRESSOF && rhsoffset != 0)
2883 varinfo_t temp = get_varinfo (c2->var);
2885 /* An access one after the end of an array is valid,
2886 so simply punt on accesses we cannot resolve. */
2887 temp = first_vi_for_offset (temp, rhsoffset);
2894 c2->offset = rhsoffset;
2895 process_constraint (new_constraint (*c, *c2));
2898 VEC_free (ce_s, heap, temp);
2904 /* Walk statement T setting up aliasing constraints according to the
2905 references found in T. This function is the main part of the
2906 constraint builder. AI points to auxiliary alias information used
2907 when building alias sets and computing alias grouping heuristics. */
2910 find_func_aliases (tree origt)
2913 VEC(ce_s, heap) *lhsc = NULL;
2914 VEC(ce_s, heap) *rhsc = NULL;
2915 struct constraint_expr *c;
2917 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
2918 t = TREE_OPERAND (t, 0);
2920 /* Now build constraints expressions. */
2921 if (TREE_CODE (t) == PHI_NODE)
2923 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))));
2925 /* Only care about pointers and structures containing
2927 if (could_have_pointers (PHI_RESULT (t)))
2932 /* For a phi node, assign all the arguments to
2934 get_constraint_for (PHI_RESULT (t), &lhsc);
2935 for (i = 0; i < PHI_NUM_ARGS (t); i++)
2938 tree strippedrhs = PHI_ARG_DEF (t, i);
2940 STRIP_NOPS (strippedrhs);
2941 rhstype = TREE_TYPE (strippedrhs);
2942 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
2944 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
2946 struct constraint_expr *c2;
2947 while (VEC_length (ce_s, rhsc) > 0)
2949 c2 = VEC_last (ce_s, rhsc);
2950 process_constraint (new_constraint (*c, *c2));
2951 VEC_pop (ce_s, rhsc);
2957 /* In IPA mode, we need to generate constraints to pass call
2958 arguments through their calls. There are two case, either a
2959 modify_expr when we are returning a value, or just a plain
2960 call_expr when we are not. */
2961 else if (in_ipa_mode
2962 && ((TREE_CODE (t) == GIMPLE_MODIFY_STMT
2963 && TREE_CODE (GIMPLE_STMT_OPERAND (t, 1)) == CALL_EXPR
2964 && !(call_expr_flags (GIMPLE_STMT_OPERAND (t, 1))
2965 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
2966 || (TREE_CODE (t) == CALL_EXPR
2967 && !(call_expr_flags (t)
2968 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))))
2977 if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
2979 lhsop = GIMPLE_STMT_OPERAND (t, 0);
2980 rhsop = GIMPLE_STMT_OPERAND (t, 1);
2987 decl = get_callee_fndecl (rhsop);
2989 /* If we can directly resolve the function being called, do so.
2990 Otherwise, it must be some sort of indirect expression that
2991 we should still be able to handle. */
2994 varid = get_id_for_tree (decl);
2998 decl = TREE_OPERAND (rhsop, 0);
2999 varid = get_id_for_tree (decl);
3002 /* Assign all the passed arguments to the appropriate incoming
3003 parameters of the function. */
3004 fi = get_varinfo (varid);
3005 arglist = TREE_OPERAND (rhsop, 1);
3007 for (;arglist; arglist = TREE_CHAIN (arglist))
3009 tree arg = TREE_VALUE (arglist);
3010 struct constraint_expr lhs ;
3011 struct constraint_expr *rhsp;
3013 get_constraint_for (arg, &rhsc);
3014 if (TREE_CODE (decl) != FUNCTION_DECL)
3023 lhs.var = first_vi_for_offset (fi, i)->id;
3026 while (VEC_length (ce_s, rhsc) != 0)
3028 rhsp = VEC_last (ce_s, rhsc);
3029 process_constraint (new_constraint (lhs, *rhsp));
3030 VEC_pop (ce_s, rhsc);
3034 /* If we are returning a value, assign it to the result. */
3037 struct constraint_expr rhs;
3038 struct constraint_expr *lhsp;
3041 get_constraint_for (lhsop, &lhsc);
3042 if (TREE_CODE (decl) != FUNCTION_DECL)
3051 rhs.var = first_vi_for_offset (fi, i)->id;
3054 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3055 process_constraint (new_constraint (*lhsp, rhs));
3058 /* Otherwise, just a regular assignment statement. */
3059 else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
3061 tree lhsop = GIMPLE_STMT_OPERAND (t, 0);
3062 tree rhsop = GIMPLE_STMT_OPERAND (t, 1);
3065 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3066 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)
3067 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop))
3068 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE))
3070 do_structure_copy (lhsop, rhsop);
3074 /* Only care about operations with pointers, structures
3075 containing pointers, dereferences, and call expressions. */
3076 if (could_have_pointers (lhsop)
3077 || TREE_CODE (rhsop) == CALL_EXPR)
3079 get_constraint_for (lhsop, &lhsc);
3080 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
3082 /* RHS that consist of unary operations,
3083 exceptional types, or bare decls/constants, get
3084 handled directly by get_constraint_for. */
3086 case tcc_declaration:
3088 case tcc_exceptional:
3089 case tcc_expression:
3094 get_constraint_for (rhsop, &rhsc);
3095 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3097 struct constraint_expr *c2;
3100 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3101 process_constraint (new_constraint (*c, *c2));
3109 /* For pointer arithmetic of the form
3110 PTR + CST, we can simply use PTR's
3111 constraint because pointer arithmetic is
3112 not allowed to go out of bounds. */
3113 if (handle_ptr_arith (lhsc, rhsop))
3118 /* Otherwise, walk each operand. Notice that we
3119 can't use the operand interface because we need
3120 to process expressions other than simple operands
3121 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3123 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
3125 tree op = TREE_OPERAND (rhsop, i);
3128 gcc_assert (VEC_length (ce_s, rhsc) == 0);
3129 get_constraint_for (op, &rhsc);
3130 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3132 struct constraint_expr *c2;
3133 while (VEC_length (ce_s, rhsc) > 0)
3135 c2 = VEC_last (ce_s, rhsc);
3136 process_constraint (new_constraint (*c, *c2));
3137 VEC_pop (ce_s, rhsc);
3146 /* After promoting variables and computing aliasing we will
3147 need to re-scan most statements. FIXME: Try to minimize the
3148 number of statements re-scanned. It's not really necessary to
3149 re-scan *all* statements. */
3150 mark_stmt_modified (origt);
3151 VEC_free (ce_s, heap, rhsc);
3152 VEC_free (ce_s, heap, lhsc);
3156 /* Find the first varinfo in the same variable as START that overlaps with
3158 Effectively, walk the chain of fields for the variable START to find the
3159 first field that overlaps with OFFSET.
3160 Return NULL if we can't find one. */
3163 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3165 varinfo_t curr = start;
3168 /* We may not find a variable in the field list with the actual
3169 offset when when we have glommed a structure to a variable.
3170 In that case, however, offset should still be within the size
3172 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3180 /* Insert the varinfo FIELD into the field list for BASE, at the front
3184 insert_into_field_list (varinfo_t base, varinfo_t field)
3186 varinfo_t prev = base;
3187 varinfo_t curr = base->next;
3193 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3197 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
3199 varinfo_t prev = base;
3200 varinfo_t curr = base->next;
3211 if (field->offset <= curr->offset)
3216 field->next = prev->next;
3221 /* qsort comparison function for two fieldoff's PA and PB */
3224 fieldoff_compare (const void *pa, const void *pb)
3226 const fieldoff_s *foa = (const fieldoff_s *)pa;
3227 const fieldoff_s *fob = (const fieldoff_s *)pb;
3228 HOST_WIDE_INT foasize, fobsize;
3230 if (foa->offset != fob->offset)
3231 return foa->offset - fob->offset;
3233 foasize = TREE_INT_CST_LOW (foa->size);
3234 fobsize = TREE_INT_CST_LOW (fob->size);
3235 return foasize - fobsize;
3238 /* Sort a fieldstack according to the field offset and sizes. */
3240 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3242 qsort (VEC_address (fieldoff_s, fieldstack),
3243 VEC_length (fieldoff_s, fieldstack),
3244 sizeof (fieldoff_s),
3248 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3249 of TYPE onto fieldstack, recording their offsets along the way.
3250 OFFSET is used to keep track of the offset in this entire structure, rather
3251 than just the immediately containing structure. Returns the number
3253 HAS_UNION is set to true if we find a union type as a field of
3257 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
3258 HOST_WIDE_INT offset, bool *has_union)
3263 if (TREE_CODE (type) == COMPLEX_TYPE)
3265 fieldoff_s *real_part, *img_part;
3266 real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3267 real_part->type = TREE_TYPE (type);
3268 real_part->size = TYPE_SIZE (TREE_TYPE (type));
3269 real_part->offset = offset;
3270 real_part->decl = NULL_TREE;
3272 img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3273 img_part->type = TREE_TYPE (type);
3274 img_part->size = TYPE_SIZE (TREE_TYPE (type));
3275 img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
3276 img_part->decl = NULL_TREE;
3281 if (TREE_CODE (type) == ARRAY_TYPE)
3283 tree sz = TYPE_SIZE (type);
3284 tree elsz = TYPE_SIZE (TREE_TYPE (type));
3289 || ! host_integerp (sz, 1)
3290 || TREE_INT_CST_LOW (sz) == 0
3292 || ! host_integerp (elsz, 1)
3293 || TREE_INT_CST_LOW (elsz) == 0)
3296 nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
3297 if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
3300 for (i = 0; i < nr; ++i)
3306 && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
3307 || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
3310 if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
3312 else if (!(pushed = push_fields_onto_fieldstack
3313 (TREE_TYPE (type), fieldstack,
3314 offset + i * TREE_INT_CST_LOW (elsz), has_union)))
3315 /* Empty structures may have actual size, like in C++. So
3316 see if we didn't push any subfields and the size is
3317 nonzero, push the field onto the stack */
3324 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3325 pair->type = TREE_TYPE (type);
3327 pair->decl = NULL_TREE;
3328 pair->offset = offset + i * TREE_INT_CST_LOW (elsz);
3338 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
3339 if (TREE_CODE (field) == FIELD_DECL)
3345 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3346 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3349 if (!var_can_have_subvars (field))
3351 else if (!(pushed = push_fields_onto_fieldstack
3352 (TREE_TYPE (field), fieldstack,
3353 offset + bitpos_of_field (field), has_union))
3354 && DECL_SIZE (field)
3355 && !integer_zerop (DECL_SIZE (field)))
3356 /* Empty structures may have actual size, like in C++. So
3357 see if we didn't push any subfields and the size is
3358 nonzero, push the field onto the stack */
3365 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3366 pair->type = TREE_TYPE (field);
3367 pair->size = DECL_SIZE (field);
3369 pair->offset = offset + bitpos_of_field (field);
3379 /* Create a constraint from ANYTHING variable to VI. */
3381 make_constraint_from_anything (varinfo_t vi)
3383 struct constraint_expr lhs, rhs;
3389 rhs.var = anything_id;
3391 rhs.type = INCLUDES;
3392 process_constraint (new_constraint (lhs, rhs));
3395 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3396 if it is a varargs function. */
3399 count_num_arguments (tree decl, bool *is_varargs)
3404 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
3408 if (TREE_VALUE (t) == void_type_node)
3418 /* Creation function node for DECL, using NAME, and return the index
3419 of the variable we've created for the function. */
3422 create_function_info_for (tree decl, const char *name)
3424 unsigned int index = VEC_length (varinfo_t, varmap);
3428 bool is_varargs = false;
3430 /* Create the variable info. */
3432 vi = new_var_info (decl, index, name, index);
3437 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3438 insert_id_for_tree (vi->decl, index);
3439 VEC_safe_push (varinfo_t, heap, varmap, vi);
3443 /* If it's varargs, we don't know how many arguments it has, so we
3450 vi->is_unknown_size_var = true;
3455 arg = DECL_ARGUMENTS (decl);
3457 /* Set up variables for each argument. */
3458 for (i = 1; i < vi->fullsize; i++)
3461 const char *newname;
3463 unsigned int newindex;
3464 tree argdecl = decl;
3469 newindex = VEC_length (varinfo_t, varmap);
3470 asprintf (&tempname, "%s.arg%d", name, i-1);
3471 newname = ggc_strdup (tempname);
3474 argvi = new_var_info (argdecl, newindex,newname, newindex);
3475 argvi->decl = argdecl;
3476 VEC_safe_push (varinfo_t, heap, varmap, argvi);
3479 argvi->fullsize = vi->fullsize;
3480 argvi->has_union = false;
3481 insert_into_field_list_sorted (vi, argvi);
3482 stats.total_vars ++;
3485 insert_id_for_tree (arg, newindex);
3486 arg = TREE_CHAIN (arg);
3490 /* Create a variable for the return var. */
3491 if (DECL_RESULT (decl) != NULL
3492 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
3495 const char *newname;
3497 unsigned int newindex;
3498 tree resultdecl = decl;
3502 if (DECL_RESULT (decl))
3503 resultdecl = DECL_RESULT (decl);
3505 newindex = VEC_length (varinfo_t, varmap);
3506 asprintf (&tempname, "%s.result", name);
3507 newname = ggc_strdup (tempname);
3510 resultvi = new_var_info (resultdecl, newindex, newname, newindex);
3511 resultvi->decl = resultdecl;
3512 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
3513 resultvi->offset = i;
3515 resultvi->fullsize = vi->fullsize;
3516 resultvi->has_union = false;
3517 insert_into_field_list_sorted (vi, resultvi);
3518 stats.total_vars ++;
3519 if (DECL_RESULT (decl))
3520 insert_id_for_tree (DECL_RESULT (decl), newindex);
3526 /* Return true if FIELDSTACK contains fields that overlap.
3527 FIELDSTACK is assumed to be sorted by offset. */
3530 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
3532 fieldoff_s *fo = NULL;
3534 HOST_WIDE_INT lastoffset = -1;
3536 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3538 if (fo->offset == lastoffset)
3540 lastoffset = fo->offset;
3545 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3546 This will also create any varinfo structures necessary for fields
3550 create_variable_info_for (tree decl, const char *name)
3552 unsigned int index = VEC_length (varinfo_t, varmap);
3554 tree decltype = TREE_TYPE (decl);
3555 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
3556 bool notokay = false;
3558 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
3559 VEC (fieldoff_s,heap) *fieldstack = NULL;
3561 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
3562 return create_function_info_for (decl, name);
3564 hasunion = TREE_CODE (decltype) == UNION_TYPE
3565 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
3566 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
3568 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
3571 VEC_free (fieldoff_s, heap, fieldstack);
3577 /* If the variable doesn't have subvars, we may end up needing to
3578 sort the field list and create fake variables for all the
3580 vi = new_var_info (decl, index, name, index);
3583 vi->has_union = hasunion;
3585 || TREE_CODE (declsize) != INTEGER_CST
3586 || TREE_CODE (decltype) == UNION_TYPE
3587 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
3589 vi->is_unknown_size_var = true;
3595 vi->fullsize = TREE_INT_CST_LOW (declsize);
3596 vi->size = vi->fullsize;
3599 insert_id_for_tree (vi->decl, index);
3600 VEC_safe_push (varinfo_t, heap, varmap, vi);
3601 if (is_global && (!flag_whole_program || !in_ipa_mode))
3602 make_constraint_from_anything (vi);
3605 if (use_field_sensitive
3607 && !vi->is_unknown_size_var
3608 && var_can_have_subvars (decl)
3609 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
3611 unsigned int newindex = VEC_length (varinfo_t, varmap);
3612 fieldoff_s *fo = NULL;
3615 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3618 || TREE_CODE (fo->size) != INTEGER_CST
3626 /* We can't sort them if we have a field with a variable sized type,
3627 which will make notokay = true. In that case, we are going to return
3628 without creating varinfos for the fields anyway, so sorting them is a
3632 sort_fieldstack (fieldstack);
3633 /* Due to some C++ FE issues, like PR 22488, we might end up
3634 what appear to be overlapping fields even though they,
3635 in reality, do not overlap. Until the C++ FE is fixed,
3636 we will simply disable field-sensitivity for these cases. */
3637 notokay = check_for_overlaps (fieldstack);
3641 if (VEC_length (fieldoff_s, fieldstack) != 0)
3642 fo = VEC_index (fieldoff_s, fieldstack, 0);
3644 if (fo == NULL || notokay)
3646 vi->is_unknown_size_var = 1;
3649 VEC_free (fieldoff_s, heap, fieldstack);
3653 vi->size = TREE_INT_CST_LOW (fo->size);
3654 vi->offset = fo->offset;
3655 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
3656 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
3660 const char *newname = "NULL";
3663 newindex = VEC_length (varinfo_t, varmap);
3667 asprintf (&tempname, "%s.%s",
3668 vi->name, alias_get_name (fo->decl));
3670 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC,
3671 vi->name, fo->offset);
3672 newname = ggc_strdup (tempname);
3675 newvi = new_var_info (decl, newindex, newname, newindex);
3676 newvi->offset = fo->offset;
3677 newvi->size = TREE_INT_CST_LOW (fo->size);
3678 newvi->fullsize = vi->fullsize;
3679 insert_into_field_list (vi, newvi);
3680 VEC_safe_push (varinfo_t, heap, varmap, newvi);
3681 if (is_global && (!flag_whole_program || !in_ipa_mode))
3682 make_constraint_from_anything (newvi);
3686 VEC_free (fieldoff_s, heap, fieldstack);
3691 /* Print out the points-to solution for VAR to FILE. */
3694 dump_solution_for_var (FILE *file, unsigned int var)
3696 varinfo_t vi = get_varinfo (var);
3700 if (vi->node != var)
3702 varinfo_t vipt = get_varinfo (vi->node);
3703 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
3707 fprintf (file, "%s = { ", vi->name);
3708 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
3710 fprintf (file, "%s ", get_varinfo (i)->name);
3712 fprintf (file, "}\n");
3716 /* Print the points-to solution for VAR to stdout. */
3719 debug_solution_for_var (unsigned int var)
3721 dump_solution_for_var (stdout, var);
3724 /* Create varinfo structures for all of the variables in the
3725 function for intraprocedural mode. */
3728 intra_create_variable_infos (void)
3731 struct constraint_expr lhs, rhs;
3733 /* For each incoming pointer argument arg, ARG = ANYTHING or a
3734 dummy variable if flag_argument_noalias > 2. */
3735 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
3738 unsigned int arg_id;
3740 if (!could_have_pointers (t))
3743 arg_id = get_id_for_tree (t);
3745 /* With flag_argument_noalias greater than two means that the incoming
3746 argument cannot alias anything except for itself so create a HEAP
3748 if (POINTER_TYPE_P (TREE_TYPE (t))
3749 && flag_argument_noalias > 2)
3752 tree heapvar = heapvar_lookup (t);
3757 lhs.var = get_id_for_tree (t);
3759 if (heapvar == NULL_TREE)
3761 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
3763 get_var_ann (heapvar)->is_heapvar = 1;
3764 DECL_EXTERNAL (heapvar) = 1;
3765 if (gimple_referenced_vars (cfun))
3766 add_referenced_var (heapvar);
3767 heapvar_insert (t, heapvar);
3769 id = get_id_for_tree (heapvar);
3770 vi = get_varinfo (id);
3771 vi->is_artificial_var = 1;
3772 vi->is_heap_var = 1;
3774 rhs.type = INCLUDES;
3776 for (p = get_varinfo (lhs.var); p; p = p->next)
3778 struct constraint_expr temp = lhs;
3780 process_constraint (new_constraint (temp, rhs));
3785 for (p = get_varinfo (arg_id); p; p = p->next)
3786 make_constraint_from_anything (p);
3791 /* Set bits in INTO corresponding to the variable uids in solution set
3792 FROM, which came from variable PTR.
3793 For variables that are actually dereferenced, we also use type
3794 based alias analysis to prune the points-to sets. */
3797 set_uids_in_ptset (tree ptr, bitmap into, bitmap from)
3802 HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr));
3804 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
3806 varinfo_t vi = get_varinfo (i);
3807 unsigned HOST_WIDE_INT var_alias_set;
3809 /* The only artificial variables that are allowed in a may-alias
3810 set are heap variables. */
3811 if (vi->is_artificial_var && !vi->is_heap_var)
3814 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
3816 /* Variables containing unions may need to be converted to
3817 their SFT's, because SFT's can have unions and we cannot. */
3818 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
3819 bitmap_set_bit (into, DECL_UID (sv->var));
3821 else if (TREE_CODE (vi->decl) == VAR_DECL
3822 || TREE_CODE (vi->decl) == PARM_DECL)
3824 if (var_can_have_subvars (vi->decl)
3825 && get_subvars_for_var (vi->decl))
3827 /* If VI->DECL is an aggregate for which we created
3828 SFTs, add the SFT corresponding to VI->OFFSET. */
3829 tree sft = get_subvar_at (vi->decl, vi->offset);
3832 var_alias_set = get_alias_set (sft);
3833 if (!vi->directly_dereferenced
3834 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
3835 bitmap_set_bit (into, DECL_UID (sft));
3840 /* Otherwise, just add VI->DECL to the alias set.
3841 Don't type prune artificial vars. */
3842 if (vi->is_artificial_var)
3843 bitmap_set_bit (into, DECL_UID (vi->decl));
3846 var_alias_set = get_alias_set (vi->decl);
3847 if (!vi->directly_dereferenced
3848 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
3849 bitmap_set_bit (into, DECL_UID (vi->decl));
3857 static bool have_alias_info = false;
3859 /* The list of SMT's that are in use by our pointer variables. This
3860 is the set of SMT's for all pointers that can point to anything. */
3861 static bitmap used_smts;
3863 /* Due to the ordering of points-to set calculation and SMT
3864 calculation being a bit co-dependent, we can't just calculate SMT
3865 used info whenever we want, we have to calculate it around the time
3866 that find_what_p_points_to is called. */
3868 /* Mark which SMT's are in use by points-to anything variables. */
3871 set_used_smts (void)
3875 used_smts = BITMAP_ALLOC (&ptabitmap_obstack);
3877 for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); i++)
3879 tree var = vi->decl;
3882 struct ptr_info_def *pi = NULL;
3884 /* For parm decls, the pointer info may be under the default
3886 if (TREE_CODE (vi->decl) == PARM_DECL
3887 && gimple_default_def (cfun, var))
3888 pi = SSA_NAME_PTR_INFO (gimple_default_def (cfun, var));
3889 else if (TREE_CODE (var) == SSA_NAME)
3890 pi = SSA_NAME_PTR_INFO (var);
3892 /* Skip the special variables and those without their own
3894 if (vi->is_special_var || vi->node != vi->id || !SSA_VAR_P (var)
3895 || (pi && !pi->is_dereferenced)
3896 || (TREE_CODE (var) == VAR_DECL && !may_be_aliased (var))
3897 || !POINTER_TYPE_P (TREE_TYPE (var)))
3900 if (TREE_CODE (var) == SSA_NAME)
3901 var = SSA_NAME_VAR (var);
3907 smt = va->symbol_mem_tag;
3908 if (smt && bitmap_bit_p (vi->solution, anything_id))
3909 bitmap_set_bit (used_smts, DECL_UID (smt));
3913 /* Merge the necessary SMT's into the solution set for VI, which is
3914 P's varinfo. This involves merging all SMT's that are a subset of
3915 the SMT necessary for P. */
3918 merge_smts_into (tree p, varinfo_t vi)
3923 VEC(tree, gc) *aliases;
3926 if (TREE_CODE (p) == SSA_NAME)
3927 var = SSA_NAME_VAR (p);
3929 smt = var_ann (var)->symbol_mem_tag;
3932 HOST_WIDE_INT smtset = get_alias_set (TREE_TYPE (smt));
3934 /* Need to set the SMT subsets first before this
3935 will work properly. */
3936 bitmap_set_bit (vi->finished_solution, DECL_UID (smt));
3937 EXECUTE_IF_SET_IN_BITMAP (used_smts, 0, i, bi)
3939 tree newsmt = referenced_var (i);
3940 tree newsmttype = TREE_TYPE (newsmt);
3942 if (alias_set_subset_of (get_alias_set (newsmttype),
3944 bitmap_set_bit (vi->finished_solution, i);
3947 aliases = var_ann (smt)->may_aliases;
3952 for (k = 0; VEC_iterate (tree, aliases, k, al); k++)
3953 bitmap_set_bit (vi->finished_solution,
3959 /* Given a pointer variable P, fill in its points-to set, or return
3961 Rather than return false for variables that point-to anything, we
3962 instead find the corresponding SMT, and merge in it's aliases. In
3963 addition to these aliases, we also set the bits for the SMT's
3964 themselves and their subsets, as SMT's are still in use by
3965 non-SSA_NAME's, and pruning may eliminate every one of their
3966 aliases. In such a case, if we did not include the right set of
3967 SMT's in the points-to set of the variable, we'd end up with
3968 statements that do not conflict but should. */
3971 find_what_p_points_to (tree p)
3973 unsigned int id = 0;
3976 if (!have_alias_info)
3979 /* For parameters, get at the points-to set for the actual parm
3981 if (TREE_CODE (p) == SSA_NAME
3982 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
3983 && SSA_NAME_IS_DEFAULT_DEF (p))
3984 lookup_p = SSA_NAME_VAR (p);
3986 if (lookup_id_for_tree (lookup_p, &id))
3988 varinfo_t vi = get_varinfo (id);
3990 if (vi->is_artificial_var)
3993 /* See if this is a field or a structure. */
3994 if (vi->size != vi->fullsize)
3996 /* Nothing currently asks about structure fields directly,
3997 but when they do, we need code here to hand back the
3999 if (!var_can_have_subvars (vi->decl)
4000 || get_subvars_for_var (vi->decl) == NULL)
4005 struct ptr_info_def *pi = get_ptr_info (p);
4008 bool was_pt_anything = false;
4010 if (!pi->is_dereferenced)
4013 /* This variable may have been collapsed, let's get the real
4015 vi = get_varinfo (vi->node);
4017 /* Translate artificial variables into SSA_NAME_PTR_INFO
4019 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4021 varinfo_t vi = get_varinfo (i);
4023 if (vi->is_artificial_var)
4025 /* FIXME. READONLY should be handled better so that
4026 flow insensitive aliasing can disregard writable
4028 if (vi->id == nothing_id)
4030 else if (vi->id == anything_id)
4031 was_pt_anything = 1;
4032 else if (vi->id == readonly_id)
4033 was_pt_anything = 1;
4034 else if (vi->id == integer_id)
4035 was_pt_anything = 1;
4036 else if (vi->is_heap_var)
4037 pi->pt_global_mem = 1;
4041 /* Share the final set of variables between the SSA_NAME
4042 pointer infos for collapsed nodes that are collapsed to
4043 non-special variables. This is because special vars have
4044 no real types associated with them, so while we know the
4045 pointers are equivalent to them, we need to generate the
4046 solution separately since it will include SMT's from the
4047 original non-collapsed variable. */
4048 if (!vi->is_special_var && vi->finished_solution)
4050 pi->pt_vars = vi->finished_solution;
4054 vi->finished_solution = BITMAP_GGC_ALLOC ();
4056 /* Instead of using pt_anything, we instead merge in the SMT
4057 aliases for the underlying SMT. */
4058 if (was_pt_anything)
4060 merge_smts_into (p, vi);
4061 pi->pt_global_mem = 1;
4064 set_uids_in_ptset (vi->decl, vi->finished_solution, vi->solution);
4065 pi->pt_vars = vi->finished_solution;
4068 if (bitmap_empty_p (pi->pt_vars))
4080 /* Dump points-to information to OUTFILE. */
4083 dump_sa_points_to_info (FILE *outfile)
4087 fprintf (outfile, "\nPoints-to sets\n\n");
4089 if (dump_flags & TDF_STATS)
4091 fprintf (outfile, "Stats:\n");
4092 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4093 fprintf (outfile, "Statically unified vars: %d\n",
4094 stats.unified_vars_static);
4095 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
4096 fprintf (outfile, "Dynamically unified vars: %d\n",
4097 stats.unified_vars_dynamic);
4098 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4099 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4102 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4103 dump_solution_for_var (outfile, i);
4107 /* Debug points-to information to stderr. */
4110 debug_sa_points_to_info (void)
4112 dump_sa_points_to_info (stderr);
4116 /* Initialize the always-existing constraint variables for NULL
4117 ANYTHING, READONLY, and INTEGER */
4120 init_base_vars (void)
4122 struct constraint_expr lhs, rhs;
4124 /* Create the NULL variable, used to represent that a variable points
4126 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4127 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
4128 insert_id_for_tree (nothing_tree, 0);
4129 var_nothing->is_artificial_var = 1;
4130 var_nothing->offset = 0;
4131 var_nothing->size = ~0;
4132 var_nothing->fullsize = ~0;
4133 var_nothing->is_special_var = 1;
4135 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
4137 /* Create the ANYTHING variable, used to represent that a variable
4138 points to some unknown piece of memory. */
4139 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4140 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
4141 insert_id_for_tree (anything_tree, 1);
4142 var_anything->is_artificial_var = 1;
4143 var_anything->size = ~0;
4144 var_anything->offset = 0;
4145 var_anything->next = NULL;
4146 var_anything->fullsize = ~0;
4147 var_anything->is_special_var = 1;
4150 /* Anything points to anything. This makes deref constraints just
4151 work in the presence of linked list and other p = *p type loops,
4152 by saying that *ANYTHING = ANYTHING. */
4153 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
4155 lhs.var = anything_id;
4157 rhs.type = INCLUDES;
4158 rhs.var = anything_id;
4160 var_anything->address_taken = true;
4162 /* This specifically does not use process_constraint because
4163 process_constraint ignores all anything = anything constraints, since all
4164 but this one are redundant. */
4165 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
4167 /* Create the READONLY variable, used to represent that a variable
4168 points to readonly memory. */
4169 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4170 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
4171 var_readonly->is_artificial_var = 1;
4172 var_readonly->offset = 0;
4173 var_readonly->size = ~0;
4174 var_readonly->fullsize = ~0;
4175 var_readonly->next = NULL;
4176 var_readonly->is_special_var = 1;
4177 insert_id_for_tree (readonly_tree, 2);
4179 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4181 /* readonly memory points to anything, in order to make deref
4182 easier. In reality, it points to anything the particular
4183 readonly variable can point to, but we don't track this
4186 lhs.var = readonly_id;
4188 rhs.type = INCLUDES;
4189 rhs.var = anything_id;
4192 process_constraint (new_constraint (lhs, rhs));
4194 /* Create the INTEGER variable, used to represent that a variable points
4196 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4197 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
4198 insert_id_for_tree (integer_tree, 3);
4199 var_integer->is_artificial_var = 1;
4200 var_integer->size = ~0;
4201 var_integer->fullsize = ~0;
4202 var_integer->offset = 0;
4203 var_integer->next = NULL;
4204 var_integer->is_special_var = 1;
4206 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
4208 /* INTEGER = ANYTHING, because we don't know where a dereference of
4209 a random integer will point to. */
4211 lhs.var = integer_id;
4213 rhs.type = INCLUDES;
4214 rhs.var = anything_id;
4216 process_constraint (new_constraint (lhs, rhs));
4219 /* Initialize things necessary to perform PTA */
4222 init_alias_vars (void)
4224 bitmap_obstack_initialize (&ptabitmap_obstack);
4225 bitmap_obstack_initialize (&predbitmap_obstack);
4227 constraint_pool = create_alloc_pool ("Constraint pool",
4228 sizeof (struct constraint), 30);
4229 variable_info_pool = create_alloc_pool ("Variable info pool",
4230 sizeof (struct variable_info), 30);
4231 constraints = VEC_alloc (constraint_t, heap, 8);
4232 varmap = VEC_alloc (varinfo_t, heap, 8);
4233 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
4234 memset (&stats, 0, sizeof (stats));
4239 /* Create points-to sets for the current function. See the comments
4240 at the start of the file for an algorithmic overview. */
4243 compute_points_to_sets (struct alias_info *ai)
4247 timevar_push (TV_TREE_PTA);
4251 intra_create_variable_infos ();
4253 /* Now walk all statements and derive aliases. */
4256 block_stmt_iterator bsi;
4259 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4261 if (is_gimple_reg (PHI_RESULT (phi)))
4263 find_func_aliases (phi);
4264 /* Update various related attributes like escaped
4265 addresses, pointer dereferences for loads and stores.
4266 This is used when creating name tags and alias
4268 update_alias_info (phi, ai);
4272 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4274 tree stmt = bsi_stmt (bsi);
4276 find_func_aliases (stmt);
4278 /* Update various related attributes like escaped
4279 addresses, pointer dereferences for loads and stores.
4280 This is used when creating name tags and alias
4282 update_alias_info (stmt, ai);
4286 build_constraint_graph ();
4290 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4291 dump_constraints (dump_file);
4296 "\nCollapsing static cycles and doing variable "
4299 find_and_collapse_graph_cycles (graph, false);
4300 perform_var_substitution (graph);
4303 fprintf (dump_file, "\nSolving graph:\n");
4305 solve_graph (graph);
4308 dump_sa_points_to_info (dump_file);
4310 have_alias_info = true;
4312 timevar_pop (TV_TREE_PTA);
4316 /* Delete created points-to sets. */
4319 delete_points_to_sets (void)
4324 htab_delete (id_for_tree);
4325 bitmap_obstack_release (&ptabitmap_obstack);
4326 bitmap_obstack_release (&predbitmap_obstack);
4327 VEC_free (constraint_t, heap, constraints);
4329 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4330 VEC_free (constraint_t, heap, v->complex);
4332 free (graph->preds);
4333 free (graph->succs);
4336 VEC_free (varinfo_t, heap, varmap);
4337 free_alloc_pool (variable_info_pool);
4338 free_alloc_pool (constraint_pool);
4339 have_alias_info = false;
4342 /* Return true if we should execute IPA PTA. */
4346 return (flag_unit_at_a_time != 0
4348 /* Don't bother doing anything if the program has errors. */
4349 && !(errorcount || sorrycount));
4352 /* Execute the driver for IPA PTA. */
4354 ipa_pta_execute (void)
4356 struct cgraph_node *node;
4358 init_alias_heapvars ();
4361 for (node = cgraph_nodes; node; node = node->next)
4363 if (!node->analyzed || cgraph_is_master_clone (node))
4367 varid = create_function_info_for (node->decl,
4368 cgraph_node_name (node));
4369 if (node->local.externally_visible)
4371 varinfo_t fi = get_varinfo (varid);
4372 for (; fi; fi = fi->next)
4373 make_constraint_from_anything (fi);
4377 for (node = cgraph_nodes; node; node = node->next)
4379 if (node->analyzed && cgraph_is_master_clone (node))
4381 struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
4383 tree old_func_decl = current_function_decl;
4386 "Generating constraints for %s\n",
4387 cgraph_node_name (node));
4389 current_function_decl = node->decl;
4391 FOR_EACH_BB_FN (bb, cfun)
4393 block_stmt_iterator bsi;
4396 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4398 if (is_gimple_reg (PHI_RESULT (phi)))
4400 find_func_aliases (phi);
4404 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4406 tree stmt = bsi_stmt (bsi);
4407 find_func_aliases (stmt);
4410 current_function_decl = old_func_decl;
4415 /* Make point to anything. */
4419 build_constraint_graph ();
4423 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4424 dump_constraints (dump_file);
4429 "\nCollapsing static cycles and doing variable "
4432 find_and_collapse_graph_cycles (graph, false);
4433 perform_var_substitution (graph);
4436 fprintf (dump_file, "\nSolving graph:\n");
4438 solve_graph (graph);
4441 dump_sa_points_to_info (dump_file);
4444 delete_alias_heapvars ();
4445 delete_points_to_sets ();
4449 struct tree_opt_pass pass_ipa_pta =
4452 gate_ipa_pta, /* gate */
4453 ipa_pta_execute, /* execute */
4456 0, /* static_pass_number */
4457 TV_IPA_PTA, /* tv_id */
4458 0, /* properties_required */
4459 0, /* properties_provided */
4460 0, /* properties_destroyed */
4461 0, /* todo_flags_start */
4462 0, /* todo_flags_finish */
4466 /* Initialize the heapvar for statement mapping. */
4468 init_alias_heapvars (void)
4470 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
4475 delete_alias_heapvars (void)
4477 htab_delete (heapvar_for_stmt);
4481 #include "gt-tree-ssa-structalias.h"