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 /* The idea behind this analyzer is to generate set constraints from the
56 program, then solve the resulting constraints in order to generate the
59 Set constraints are a way of modeling program analysis problems that
60 involve sets. They consist of an inclusion constraint language,
61 describing the variables (each variable is a set) and operations that
62 are involved on the variables, and a set of rules that derive facts
63 from these operations. To solve a system of set constraints, you derive
64 all possible facts under the rules, which gives you the correct sets
67 See "Efficient Field-sensitive pointer analysis for C" by "David
68 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
69 http://citeseer.ist.psu.edu/pearce04efficient.html
71 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
72 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
73 http://citeseer.ist.psu.edu/heintze01ultrafast.html
75 There are three types of constraint expressions, DEREF, ADDRESSOF, and
76 SCALAR. Each constraint expression consists of a constraint type,
77 a variable, and an offset.
79 SCALAR is a constraint expression type used to represent x, whether
80 it appears on the LHS or the RHS of a statement.
81 DEREF is a constraint expression type used to represent *x, whether
82 it appears on the LHS or the RHS of a statement.
83 ADDRESSOF is a constraint expression used to represent &x, whether
84 it appears on the LHS or the RHS of a statement.
86 Each pointer variable in the program is assigned an integer id, and
87 each field of a structure variable is assigned an integer id as well.
89 Structure variables are linked to their list of fields through a "next
90 field" in each variable that points to the next field in offset
92 Each variable for a structure field has
94 1. "size", that tells the size in bits of that field.
95 2. "fullsize, that tells the size in bits of the entire structure.
96 3. "offset", that tells the offset in bits from the beginning of the
97 structure to this field.
109 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
110 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
111 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
114 In order to solve the system of set constraints, the following is
117 1. Each constraint variable x has a solution set associated with it,
120 2. Constraints are separated into direct, copy, and complex.
121 Direct constraints are ADDRESSOF constraints that require no extra
122 processing, such as P = &Q
123 Copy constraints are those of the form P = Q.
124 Complex constraints are all the constraints involving dereferences.
126 3. All direct constraints of the form P = &Q are processed, such
127 that Q is added to Sol(P)
129 4. All complex constraints for a given constraint variable are stored in a
130 linked list attached to that variable's node.
132 5. A directed graph is built out of the copy constraints. Each
133 constraint variable is a node in the graph, and an edge from
134 Q to P is added for each copy constraint of the form P = Q
136 6. The graph is then walked, and solution sets are
137 propagated along the copy edges, such that an edge from Q to P
138 causes Sol(P) <- Sol(P) union Sol(Q).
140 7. As we visit each node, all complex constraints associated with
141 that node are processed by adding appropriate copy edges to the graph, or the
142 appropriate variables to the solution set.
144 8. The process of walking the graph is iterated until no solution
147 Prior to walking the graph in steps 6 and 7, We perform static
148 cycle elimination on the constraint graph, as well
149 as off-line variable substitution.
151 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
152 on and turned into anything), but isn't. You can just see what offset
153 inside the pointed-to struct it's going to access.
155 TODO: Constant bounded arrays can be handled as if they were structs of the
156 same number of elements.
158 TODO: Modeling heap and incoming pointers becomes much better if we
159 add fields to them as we discover them, which we could do.
161 TODO: We could handle unions, but to be honest, it's probably not
162 worth the pain or slowdown. */
164 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
165 htab_t heapvar_for_stmt;
168 /* Represents nonlocals. */
169 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
170 htab_t nonlocal_for_type;
172 /* If strict aliasing is off, we only use one variable to represent
173 the nonlocal types. */
174 static GTY (()) tree nonlocal_all;
176 static bool use_field_sensitive = true;
177 static int in_ipa_mode = 0;
178 static bitmap_obstack predbitmap_obstack;
179 static bitmap_obstack ptabitmap_obstack;
180 static bitmap_obstack iteration_obstack;
182 static unsigned int create_variable_info_for (tree, const char *);
183 static void build_constraint_graph (void);
185 DEF_VEC_P(constraint_t);
186 DEF_VEC_ALLOC_P(constraint_t,heap);
188 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
190 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
192 static struct constraint_stats
194 unsigned int total_vars;
195 unsigned int collapsed_vars;
196 unsigned int unified_vars_static;
197 unsigned int unified_vars_dynamic;
198 unsigned int iterations;
199 unsigned int num_edges;
204 /* ID of this variable */
207 /* Name of this variable */
210 /* Tree that this variable is associated with. */
213 /* Offset of this variable, in bits, from the base variable */
214 unsigned HOST_WIDE_INT offset;
216 /* Size of the variable, in bits. */
217 unsigned HOST_WIDE_INT size;
219 /* Full size of the base variable, in bits. */
220 unsigned HOST_WIDE_INT fullsize;
222 /* A link to the variable for the next field in this structure. */
223 struct variable_info *next;
225 /* Node in the graph that represents the constraints and points-to
226 solution for the variable. */
229 /* True if the address of this variable is taken. Needed for
230 variable substitution. */
231 unsigned int address_taken:1;
233 /* True if this variable is the target of a dereference. Needed for
234 variable substitution. */
235 unsigned int indirect_target:1;
237 /* True if the variable is directly the target of a dereference.
238 This is used to track which variables are *actually* dereferenced
239 so we can prune their points to listed. This is equivalent to the
240 indirect_target flag when no merging of variables happens. */
241 unsigned int directly_dereferenced:1;
243 /* True if this is a variable created by the constraint analysis, such as
244 heap variables and constraints we had to break up. */
245 unsigned int is_artificial_var:1;
247 /* True if this is a special variable whose solution set should not be
249 unsigned int is_special_var:1;
251 /* True for variables whose size is not known or variable. */
252 unsigned int is_unknown_size_var:1;
254 /* True for variables that have unions somewhere in them. */
255 unsigned int has_union:1;
257 /* True if this is a heap variable. */
258 unsigned int is_heap_var:1;
260 /* Points-to set for this variable. */
263 /* Variable ids represented by this node. */
266 /* Vector of complex constraints for this node. Complex
267 constraints are those involving dereferences. */
268 VEC(constraint_t,heap) *complex;
270 /* Variable id this was collapsed to due to type unsafety.
271 This should be unused completely after build_constraint_graph, or
272 something is broken. */
273 struct variable_info *collapsed_to;
275 typedef struct variable_info *varinfo_t;
277 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
279 /* Pool of variable info structures. */
280 static alloc_pool variable_info_pool;
282 DEF_VEC_P(varinfo_t);
284 DEF_VEC_ALLOC_P(varinfo_t, heap);
286 /* Table of variable info structures for constraint variables. Indexed directly
287 by variable info id. */
288 static VEC(varinfo_t,heap) *varmap;
290 /* Return the varmap element N */
292 static inline varinfo_t
293 get_varinfo (unsigned int n)
295 return VEC_index(varinfo_t, varmap, n);
298 /* Return the varmap element N, following the collapsed_to link. */
300 static inline varinfo_t
301 get_varinfo_fc (unsigned int n)
303 varinfo_t v = VEC_index(varinfo_t, varmap, n);
306 return v->collapsed_to;
310 /* Variable that represents the unknown pointer. */
311 static varinfo_t var_anything;
312 static tree anything_tree;
313 static unsigned int anything_id;
315 /* Variable that represents the NULL pointer. */
316 static varinfo_t var_nothing;
317 static tree nothing_tree;
318 static unsigned int nothing_id;
320 /* Variable that represents read only memory. */
321 static varinfo_t var_readonly;
322 static tree readonly_tree;
323 static unsigned int readonly_id;
325 /* Variable that represents integers. This is used for when people do things
327 static varinfo_t var_integer;
328 static tree integer_tree;
329 static unsigned int integer_id;
331 /* Variable that represents escaped variables. This is used to give
332 incoming pointer variables a better set than ANYTHING. */
333 static varinfo_t var_escaped_vars;
334 static tree escaped_vars_tree;
335 static unsigned int escaped_vars_id;
337 /* Variable that represents non-local variables before we expand it to
338 one for each type. */
339 static unsigned int nonlocal_vars_id;
341 /* Lookup a heap var for FROM, and return it if we find one. */
344 heapvar_lookup (tree from)
346 struct tree_map *h, in;
349 h = htab_find_with_hash (heapvar_for_stmt, &in, htab_hash_pointer (from));
355 /* Insert a mapping FROM->TO in the heap var for statement
359 heapvar_insert (tree from, tree to)
364 h = ggc_alloc (sizeof (struct tree_map));
365 h->hash = htab_hash_pointer (from);
368 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
369 *(struct tree_map **) loc = h;
372 /* Return a new variable info structure consisting for a variable
373 named NAME, and using constraint graph node NODE. */
376 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
378 varinfo_t ret = pool_alloc (variable_info_pool);
384 ret->address_taken = false;
385 ret->indirect_target = false;
386 ret->directly_dereferenced = false;
387 ret->is_artificial_var = false;
388 ret->is_heap_var = false;
389 ret->is_special_var = false;
390 ret->is_unknown_size_var = false;
391 ret->has_union = false;
392 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
393 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
396 ret->collapsed_to = NULL;
400 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
402 /* An expression that appears in a constraint. */
404 struct constraint_expr
406 /* Constraint type. */
407 constraint_expr_type type;
409 /* Variable we are referring to in the constraint. */
412 /* Offset, in bits, of this constraint from the beginning of
413 variables it ends up referring to.
415 IOW, in a deref constraint, we would deref, get the result set,
416 then add OFFSET to each member. */
417 unsigned HOST_WIDE_INT offset;
420 typedef struct constraint_expr ce_s;
422 DEF_VEC_ALLOC_O(ce_s, heap);
423 static void get_constraint_for (tree, VEC(ce_s, heap) **);
424 static void do_deref (VEC (ce_s, heap) **);
426 /* Our set constraints are made up of two constraint expressions, one
429 As described in the introduction, our set constraints each represent an
430 operation between set valued variables.
434 struct constraint_expr lhs;
435 struct constraint_expr rhs;
438 /* List of constraints that we use to build the constraint graph from. */
440 static VEC(constraint_t,heap) *constraints;
441 static alloc_pool constraint_pool;
443 /* An edge in the weighted constraint graph. The edges are weighted,
444 with a bit set in weights meaning their is an edge with that
446 We don't keep the src in the edge, because we always know what it
449 struct constraint_edge
455 typedef struct constraint_edge *constraint_edge_t;
456 static alloc_pool constraint_edge_pool;
458 /* Return a new constraint edge from SRC to DEST. */
460 static constraint_edge_t
461 new_constraint_edge (unsigned int dest)
463 constraint_edge_t ret = pool_alloc (constraint_edge_pool);
469 DEF_VEC_P(constraint_edge_t);
470 DEF_VEC_ALLOC_P(constraint_edge_t,heap);
473 /* The constraint graph is represented internally in two different
474 ways. The overwhelming majority of edges in the constraint graph
475 are zero weigh edges, and thus, using a vector of contrainst_edge_t
476 is a waste of time and memory, since they have no weights. We
477 simply use a bitmap to store the preds and succs for each node.
478 The weighted edges are stored as a set of adjacency vectors, one
479 per variable. succs[x] is the vector of successors for variable x,
480 and preds[x] is the vector of predecessors for variable x. IOW,
481 all edges are "forward" edges, which is not like our CFG. So
482 remember that preds[x]->src == x, and succs[x]->src == x. */
484 struct constraint_graph
486 bitmap *zero_weight_succs;
487 bitmap *zero_weight_preds;
488 VEC(constraint_edge_t,heap) **succs;
489 VEC(constraint_edge_t,heap) **preds;
492 typedef struct constraint_graph *constraint_graph_t;
494 static constraint_graph_t graph;
495 static int graph_size;
497 /* Create a new constraint consisting of LHS and RHS expressions. */
500 new_constraint (const struct constraint_expr lhs,
501 const struct constraint_expr rhs)
503 constraint_t ret = pool_alloc (constraint_pool);
509 /* Print out constraint C to FILE. */
512 dump_constraint (FILE *file, constraint_t c)
514 if (c->lhs.type == ADDRESSOF)
516 else if (c->lhs.type == DEREF)
518 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
519 if (c->lhs.offset != 0)
520 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
521 fprintf (file, " = ");
522 if (c->rhs.type == ADDRESSOF)
524 else if (c->rhs.type == DEREF)
526 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
527 if (c->rhs.offset != 0)
528 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
529 fprintf (file, "\n");
532 /* Print out constraint C to stderr. */
535 debug_constraint (constraint_t c)
537 dump_constraint (stderr, c);
540 /* Print out all constraints to FILE */
543 dump_constraints (FILE *file)
547 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
548 dump_constraint (file, c);
551 /* Print out all constraints to stderr. */
554 debug_constraints (void)
556 dump_constraints (stderr);
561 The solver is a simple worklist solver, that works on the following
564 sbitmap changed_nodes = all ones;
565 changed_count = number of nodes;
566 For each node that was already collapsed:
569 while (changed_count > 0)
571 compute topological ordering for constraint graph
573 find and collapse cycles in the constraint graph (updating
574 changed if necessary)
576 for each node (n) in the graph in topological order:
579 Process each complex constraint associated with the node,
580 updating changed if necessary.
582 For each outgoing edge from n, propagate the solution from n to
583 the destination of the edge, updating changed as necessary.
587 /* Return true if two constraint expressions A and B are equal. */
590 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
592 return a.type == b.type && a.var == b.var && a.offset == b.offset;
595 /* Return true if constraint expression A is less than constraint expression
596 B. This is just arbitrary, but consistent, in order to give them an
600 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
602 if (a.type == b.type)
605 return a.offset < b.offset;
607 return a.var < b.var;
610 return a.type < b.type;
613 /* Return true if constraint A is less than constraint B. This is just
614 arbitrary, but consistent, in order to give them an ordering. */
617 constraint_less (const constraint_t a, const constraint_t b)
619 if (constraint_expr_less (a->lhs, b->lhs))
621 else if (constraint_expr_less (b->lhs, a->lhs))
624 return constraint_expr_less (a->rhs, b->rhs);
627 /* Return true if two constraints A and B are equal. */
630 constraint_equal (struct constraint a, struct constraint b)
632 return constraint_expr_equal (a.lhs, b.lhs)
633 && constraint_expr_equal (a.rhs, b.rhs);
637 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
640 constraint_vec_find (VEC(constraint_t,heap) *vec,
641 struct constraint lookfor)
649 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
650 if (place >= VEC_length (constraint_t, vec))
652 found = VEC_index (constraint_t, vec, place);
653 if (!constraint_equal (*found, lookfor))
658 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
661 constraint_set_union (VEC(constraint_t,heap) **to,
662 VEC(constraint_t,heap) **from)
667 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
669 if (constraint_vec_find (*to, *c) == NULL)
671 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
673 VEC_safe_insert (constraint_t, heap, *to, place, c);
678 /* Take a solution set SET, add OFFSET to each member of the set, and
679 overwrite SET with the result when done. */
682 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
684 bitmap result = BITMAP_ALLOC (&iteration_obstack);
688 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
690 /* If this is a properly sized variable, only add offset if it's
691 less than end. Otherwise, it is globbed to a single
694 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
696 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
697 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
700 bitmap_set_bit (result, v->id);
702 else if (get_varinfo (i)->is_artificial_var
703 || get_varinfo (i)->has_union
704 || get_varinfo (i)->is_unknown_size_var)
706 bitmap_set_bit (result, i);
710 bitmap_copy (set, result);
711 BITMAP_FREE (result);
714 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
718 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
721 return bitmap_ior_into (to, from);
727 tmp = BITMAP_ALLOC (&iteration_obstack);
728 bitmap_copy (tmp, from);
729 solution_set_add (tmp, inc);
730 res = bitmap_ior_into (to, tmp);
736 /* Insert constraint C into the list of complex constraints for VAR. */
739 insert_into_complex (unsigned int var, constraint_t c)
741 varinfo_t vi = get_varinfo (var);
742 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
744 VEC_safe_insert (constraint_t, heap, vi->complex, place, c);
748 /* Compare two constraint edges A and B, return true if they are equal. */
751 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
753 return a.dest == b.dest;
756 /* Compare two constraint edges, return true if A is less than B */
759 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
761 if (a->dest < b->dest)
766 /* Find the constraint edge that matches LOOKFOR, in VEC.
767 Return the edge, if found, NULL otherwise. */
769 static constraint_edge_t
770 constraint_edge_vec_find (VEC(constraint_edge_t,heap) *vec,
771 struct constraint_edge lookfor)
774 constraint_edge_t edge = NULL;
776 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
777 constraint_edge_less);
778 if (place >= VEC_length (constraint_edge_t, vec))
780 edge = VEC_index (constraint_edge_t, vec, place);
781 if (!constraint_edge_equal (*edge, lookfor))
786 /* Condense two variable nodes into a single variable node, by moving
787 all associated info from SRC to TO. */
790 condense_varmap_nodes (unsigned int to, unsigned int src)
792 varinfo_t tovi = get_varinfo (to);
793 varinfo_t srcvi = get_varinfo (src);
798 /* the src node, and all its variables, are now the to node. */
800 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
801 get_varinfo (i)->node = to;
803 /* Merge the src node variables and the to node variables. */
804 bitmap_set_bit (tovi->variables, src);
805 bitmap_ior_into (tovi->variables, srcvi->variables);
806 bitmap_clear (srcvi->variables);
808 /* Move all complex constraints from src node into to node */
809 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
811 /* In complex constraints for node src, we may have either
812 a = *src, and *src = a. */
814 if (c->rhs.type == DEREF)
819 constraint_set_union (&tovi->complex, &srcvi->complex);
820 VEC_free (constraint_t, heap, srcvi->complex);
821 srcvi->complex = NULL;
824 /* Erase an edge from SRC to SRC from GRAPH. This routine only
825 handles self-edges (e.g. an edge from a to a). */
828 erase_graph_self_edge (constraint_graph_t graph, unsigned int src)
830 VEC(constraint_edge_t,heap) *predvec = graph->preds[src];
831 VEC(constraint_edge_t,heap) *succvec = graph->succs[src];
832 struct constraint_edge edge;
837 /* Remove from the successors. */
838 place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
839 constraint_edge_less);
841 /* Make sure we found the edge. */
842 #ifdef ENABLE_CHECKING
844 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
845 gcc_assert (constraint_edge_equal (*tmp, edge));
848 VEC_ordered_remove (constraint_edge_t, succvec, place);
850 /* Remove from the predecessors. */
851 place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
852 constraint_edge_less);
854 /* Make sure we found the edge. */
855 #ifdef ENABLE_CHECKING
857 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
858 gcc_assert (constraint_edge_equal (*tmp, edge));
861 VEC_ordered_remove (constraint_edge_t, predvec, place);
864 /* Remove edges involving NODE from GRAPH. */
867 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
869 VEC(constraint_edge_t,heap) *succvec = graph->succs[node];
870 VEC(constraint_edge_t,heap) *predvec = graph->preds[node];
873 constraint_edge_t c = NULL;
876 /* Walk the successors, erase the associated preds. */
878 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[node], 0, j, bi)
880 bitmap_clear_bit (graph->zero_weight_preds[j], node);
882 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
886 struct constraint_edge lookfor;
887 constraint_edge_t result;
890 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
891 &lookfor, constraint_edge_less);
892 result = VEC_ordered_remove (constraint_edge_t,
893 graph->preds[c->dest], place);
894 pool_free (constraint_edge_pool, result);
897 /* Walk the preds, erase the associated succs. */
899 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[node], 0, j, bi)
901 bitmap_clear_bit (graph->zero_weight_succs[j], node);
903 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
907 struct constraint_edge lookfor;
908 constraint_edge_t result;
911 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
912 &lookfor, constraint_edge_less);
913 result = VEC_ordered_remove (constraint_edge_t,
914 graph->succs[c->dest], place);
915 pool_free (constraint_edge_pool, result);
919 if (graph->zero_weight_preds[node])
921 BITMAP_FREE (graph->zero_weight_preds[node]);
922 graph->zero_weight_preds[node] = NULL;
925 if (graph->zero_weight_succs[node])
927 BITMAP_FREE (graph->zero_weight_succs[node]);
928 graph->zero_weight_succs[node] = NULL;
931 VEC_free (constraint_edge_t, heap, graph->preds[node]);
932 VEC_free (constraint_edge_t, heap, graph->succs[node]);
933 graph->preds[node] = NULL;
934 graph->succs[node] = NULL;
937 static bool edge_added = false;
939 /* Add edge (src, dest) to the graph. */
942 add_graph_edge (constraint_graph_t graph, unsigned int src, unsigned int dest)
945 VEC(constraint_edge_t,heap) *vec;
946 struct constraint_edge newe;
949 vec = graph->preds[src];
950 place = VEC_lower_bound (constraint_edge_t, vec, &newe,
951 constraint_edge_less);
952 if (place == VEC_length (constraint_edge_t, vec)
953 || VEC_index (constraint_edge_t, vec, place)->dest != dest)
955 constraint_edge_t edge = new_constraint_edge (dest);
957 VEC_safe_insert (constraint_edge_t, heap, graph->preds[src],
959 edge = new_constraint_edge (src);
961 place = VEC_lower_bound (constraint_edge_t, graph->succs[dest],
962 edge, constraint_edge_less);
963 VEC_safe_insert (constraint_edge_t, heap, graph->succs[dest],
974 /* Return the bitmap representing the weights of edge (SRC, DEST). */
977 get_graph_weights (constraint_graph_t graph, unsigned int src,
980 constraint_edge_t edge;
981 VEC(constraint_edge_t,heap) *vec;
982 struct constraint_edge lookfor;
986 vec = graph->preds[src];
987 edge = constraint_edge_vec_find (vec, lookfor);
988 gcc_assert (edge != NULL);
989 return &edge->weights;
992 /* Allocate graph weight bitmap for the edges associated with SRC and
993 DEST in GRAPH. Both the pred and the succ edges share a single
994 bitmap, so we need to set both edges to that bitmap. */
997 allocate_graph_weights (constraint_graph_t graph, unsigned int src,
1001 constraint_edge_t edge;
1002 VEC(constraint_edge_t,heap) *vec;
1003 struct constraint_edge lookfor;
1005 result = BITMAP_ALLOC (&ptabitmap_obstack);
1007 /* Set the pred weight. */
1008 lookfor.dest = dest;
1009 vec = graph->preds[src];
1010 edge = constraint_edge_vec_find (vec, lookfor);
1011 gcc_assert (edge != NULL);
1012 edge->weights = result;
1014 /* Set the succ weight. */
1016 vec = graph->succs[dest];
1017 edge = constraint_edge_vec_find (vec, lookfor);
1018 gcc_assert (edge != NULL);
1019 edge->weights = result;
1025 /* Merge GRAPH nodes FROM and TO into node TO. */
1028 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1031 VEC(constraint_edge_t,heap) *succvec = graph->succs[from];
1032 VEC(constraint_edge_t,heap) *predvec = graph->preds[from];
1034 constraint_edge_t c;
1038 /* Merge all the zero weighted predecessor edges. */
1039 if (graph->zero_weight_preds[from])
1041 if (!graph->zero_weight_preds[to])
1042 graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1044 EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_preds[from], 0, j, bi)
1048 bitmap_clear_bit (graph->zero_weight_succs[j], from);
1049 bitmap_set_bit (graph->zero_weight_succs[j], to);
1052 bitmap_ior_into (graph->zero_weight_preds[to],
1053 graph->zero_weight_preds[from]);
1056 /* Merge all the zero weighted successor edges. */
1057 if (graph->zero_weight_succs[from])
1059 if (!graph->zero_weight_succs[to])
1060 graph->zero_weight_succs[to] = BITMAP_ALLOC (&ptabitmap_obstack);
1061 EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_succs[from], 0, j, bi)
1063 bitmap_clear_bit (graph->zero_weight_preds[j], from);
1064 bitmap_set_bit (graph->zero_weight_preds[j], to);
1066 bitmap_ior_into (graph->zero_weight_succs[to],
1067 graph->zero_weight_succs[from]);
1070 /* Merge all the nonzero weighted predecessor edges. */
1071 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
1073 unsigned int d = c->dest;
1077 if (c->dest == from)
1080 add_graph_edge (graph, to, d);
1082 temp = *(get_graph_weights (graph, from, c->dest));
1085 weights = get_graph_weights (graph, to, d);
1087 *weights = allocate_graph_weights (graph, to, d);
1089 bitmap_ior_into (*weights, temp);
1094 /* Merge all the nonzero weighted successor edges. */
1095 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
1097 unsigned int d = c->dest;
1101 if (c->dest == from)
1104 add_graph_edge (graph, d, to);
1106 temp = *(get_graph_weights (graph, c->dest, from));
1109 weights = get_graph_weights (graph, d, to);
1111 *weights = allocate_graph_weights (graph, d, to);
1112 bitmap_ior_into (*weights, temp);
1115 clear_edges_for_node (graph, from);
1118 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
1119 it doesn't exist in the graph already.
1120 Return false if the edge already existed, true otherwise. */
1123 int_add_graph_edge (constraint_graph_t graph, unsigned int to,
1124 unsigned int from, unsigned HOST_WIDE_INT weight)
1126 if (to == from && weight == 0)
1136 if (!graph->zero_weight_preds[to])
1137 graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1138 if (!graph->zero_weight_succs[from])
1139 graph->zero_weight_succs[from] = BITMAP_ALLOC (&ptabitmap_obstack);
1140 if (!bitmap_bit_p (graph->zero_weight_succs[from], to))
1145 bitmap_set_bit (graph->zero_weight_preds[to], from);
1146 bitmap_set_bit (graph->zero_weight_succs[from], to);
1153 r = add_graph_edge (graph, to, from);
1154 weights = get_graph_weights (graph, to, from);
1159 *weights = allocate_graph_weights (graph, to, from);
1160 bitmap_set_bit (*weights, weight);
1164 r |= !bitmap_bit_p (*weights, weight);
1165 bitmap_set_bit (*weights, weight);
1174 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1177 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1180 struct constraint_edge lookfor;
1183 return (graph->zero_weight_succs[dest]
1184 && bitmap_bit_p (graph->zero_weight_succs[dest], src))
1185 || constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL;
1188 /* Return true if {DEST, SRC} is an existing weighted graph edge (IE has
1189 a weight other than 0) in GRAPH. */
1191 valid_weighted_graph_edge (constraint_graph_t graph, unsigned int src,
1194 struct constraint_edge lookfor;
1197 return graph->preds[src]
1198 && constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL;
1202 /* Build the constraint graph. */
1205 build_constraint_graph (void)
1210 graph = XNEW (struct constraint_graph);
1211 graph_size = VEC_length (varinfo_t, varmap) + 1;
1212 graph->succs = XCNEWVEC (VEC(constraint_edge_t,heap) *, graph_size);
1213 graph->preds = XCNEWVEC (VEC(constraint_edge_t,heap) *, graph_size);
1214 graph->zero_weight_succs = XCNEWVEC (bitmap, graph_size);
1215 graph->zero_weight_preds = XCNEWVEC (bitmap, graph_size);
1217 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1219 struct constraint_expr lhs = c->lhs;
1220 struct constraint_expr rhs = c->rhs;
1221 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
1222 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
1224 if (lhs.type == DEREF)
1226 /* *x = y or *x = &y (complex) */
1227 if (rhs.type == ADDRESSOF || rhsvar > anything_id)
1228 insert_into_complex (lhsvar, c);
1230 else if (rhs.type == DEREF)
1232 /* !special var= *y */
1233 if (!(get_varinfo (lhsvar)->is_special_var))
1234 insert_into_complex (rhsvar, c);
1236 else if (rhs.type == ADDRESSOF)
1239 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1241 else if (lhsvar > anything_id)
1243 /* Ignore 0 weighted self edges, as they can't possibly contribute
1245 if (lhsvar != rhsvar || rhs.offset != 0 || lhs.offset != 0)
1247 /* x = y (simple) */
1248 int_add_graph_edge (graph, lhs.var, rhs.var, rhs.offset);
1256 /* Changed variables on the last iteration. */
1257 static unsigned int changed_count;
1258 static sbitmap changed;
1260 DEF_VEC_I(unsigned);
1261 DEF_VEC_ALLOC_I(unsigned,heap);
1264 /* Strongly Connected Component visitation info. */
1269 sbitmap in_component;
1271 unsigned int *visited_index;
1272 VEC(unsigned,heap) *scc_stack;
1273 VEC(unsigned,heap) *unification_queue;
1277 /* Recursive routine to find strongly connected components in GRAPH.
1278 SI is the SCC info to store the information in, and N is the id of current
1279 graph node we are processing.
1281 This is Tarjan's strongly connected component finding algorithm, as
1282 modified by Nuutila to keep only non-root nodes on the stack.
1283 The algorithm can be found in "On finding the strongly connected
1284 connected components in a directed graph" by Esko Nuutila and Eljas
1285 Soisalon-Soininen, in Information Processing Letters volume 49,
1286 number 1, pages 9-14. */
1289 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1294 gcc_assert (get_varinfo (n)->node == n);
1295 SET_BIT (si->visited, n);
1296 RESET_BIT (si->in_component, n);
1297 si->visited_index[n] = si->current_index ++;
1299 /* Visit all the successors. */
1300 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[n], 0, i, bi)
1303 if (!TEST_BIT (si->visited, w))
1304 scc_visit (graph, si, w);
1305 if (!TEST_BIT (si->in_component, w))
1307 unsigned int t = get_varinfo (w)->node;
1308 unsigned int nnode = get_varinfo (n)->node;
1309 if (si->visited_index[t] < si->visited_index[nnode])
1310 get_varinfo (n)->node = t;
1314 /* See if any components have been identified. */
1315 if (get_varinfo (n)->node == n)
1317 unsigned int t = si->visited_index[n];
1318 SET_BIT (si->in_component, n);
1319 while (VEC_length (unsigned, si->scc_stack) != 0
1320 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1322 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1323 get_varinfo (w)->node = n;
1324 SET_BIT (si->in_component, w);
1325 /* Mark this node for collapsing. */
1326 VEC_safe_push (unsigned, heap, si->unification_queue, w);
1330 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1334 /* Collapse two variables into one variable. */
1337 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1339 bitmap tosol, fromsol;
1341 condense_varmap_nodes (to, from);
1342 tosol = get_varinfo (to)->solution;
1343 fromsol = get_varinfo (from)->solution;
1344 bitmap_ior_into (tosol, fromsol);
1345 merge_graph_nodes (graph, to, from);
1347 if (valid_graph_edge (graph, to, to))
1349 if (graph->zero_weight_preds[to])
1351 bitmap_clear_bit (graph->zero_weight_preds[to], to);
1352 bitmap_clear_bit (graph->zero_weight_succs[to], to);
1354 if (valid_weighted_graph_edge (graph, to, to))
1356 bitmap weights = *(get_graph_weights (graph, to, to));
1357 if (!weights || bitmap_empty_p (weights))
1358 erase_graph_self_edge (graph, to);
1361 BITMAP_FREE (fromsol);
1362 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1363 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1367 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1368 SI is the Strongly Connected Components information structure that tells us
1369 what components to unify.
1370 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1371 count should be updated to reflect the unification. */
1374 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1375 bool update_changed)
1378 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1381 /* We proceed as follows:
1383 For each component in the queue (components are delineated by
1384 when current_queue_element->node != next_queue_element->node):
1386 rep = representative node for component
1388 For each node (tounify) to be unified in the component,
1389 merge the solution for tounify into tmp bitmap
1391 clear solution for tounify
1393 merge edges from tounify into rep
1395 merge complex constraints from tounify into rep
1397 update changed count to note that tounify will never change
1400 Merge tmp into solution for rep, marking rep changed if this
1401 changed rep's solution.
1403 Delete any 0 weighted self-edges we now have for rep. */
1404 while (i != VEC_length (unsigned, si->unification_queue))
1406 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1407 unsigned int n = get_varinfo (tounify)->node;
1409 if (dump_file && (dump_flags & TDF_DETAILS))
1410 fprintf (dump_file, "Unifying %s to %s\n",
1411 get_varinfo (tounify)->name,
1412 get_varinfo (n)->name);
1414 stats.unified_vars_dynamic++;
1416 stats.unified_vars_static++;
1417 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1418 merge_graph_nodes (graph, n, tounify);
1419 condense_varmap_nodes (n, tounify);
1421 if (update_changed && TEST_BIT (changed, tounify))
1423 RESET_BIT (changed, tounify);
1424 if (!TEST_BIT (changed, n))
1425 SET_BIT (changed, n);
1428 gcc_assert (changed_count > 0);
1433 bitmap_clear (get_varinfo (tounify)->solution);
1436 /* If we've either finished processing the entire queue, or
1437 finished processing all nodes for component n, update the solution for
1439 if (i == VEC_length (unsigned, si->unification_queue)
1440 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1442 /* If the solution changes because of the merging, we need to mark
1443 the variable as changed. */
1444 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1446 if (update_changed && !TEST_BIT (changed, n))
1448 SET_BIT (changed, n);
1454 if (valid_graph_edge (graph, n, n))
1456 if (graph->zero_weight_succs[n])
1458 if (graph->zero_weight_preds[n])
1459 bitmap_clear_bit (graph->zero_weight_preds[n], n);
1460 bitmap_clear_bit (graph->zero_weight_succs[n], n);
1462 if (valid_weighted_graph_edge (graph, n, n))
1464 bitmap weights = *(get_graph_weights (graph, n, n));
1465 if (!weights || bitmap_empty_p (weights))
1466 erase_graph_self_edge (graph, n);
1475 /* Information needed to compute the topological ordering of a graph. */
1479 /* sbitmap of visited nodes. */
1481 /* Array that stores the topological order of the graph, *in
1483 VEC(unsigned,heap) *topo_order;
1487 /* Initialize and return a topological info structure. */
1489 static struct topo_info *
1490 init_topo_info (void)
1492 size_t size = VEC_length (varinfo_t, varmap);
1493 struct topo_info *ti = XNEW (struct topo_info);
1494 ti->visited = sbitmap_alloc (size);
1495 sbitmap_zero (ti->visited);
1496 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1501 /* Free the topological sort info pointed to by TI. */
1504 free_topo_info (struct topo_info *ti)
1506 sbitmap_free (ti->visited);
1507 VEC_free (unsigned, heap, ti->topo_order);
1511 /* Visit the graph in topological order, and store the order in the
1512 topo_info structure. */
1515 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1518 VEC(constraint_edge_t,heap) *succs = graph->succs[n];
1521 constraint_edge_t c;
1525 SET_BIT (ti->visited, n);
1526 if (VEC_length (constraint_edge_t, succs) != 0)
1528 temp = BITMAP_ALLOC (&iteration_obstack);
1529 if (graph->zero_weight_succs[n])
1530 bitmap_ior_into (temp, graph->zero_weight_succs[n]);
1531 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1532 bitmap_set_bit (temp, c->dest);
1535 temp = graph->zero_weight_succs[n];
1538 EXECUTE_IF_SET_IN_BITMAP (temp, 0, j, bi)
1540 if (!TEST_BIT (ti->visited, j))
1541 topo_visit (graph, ti, j);
1543 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1546 /* Return true if variable N + OFFSET is a legal field of N. */
1549 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1551 varinfo_t ninfo = get_varinfo (n);
1553 /* For things we've globbed to single variables, any offset into the
1554 variable acts like the entire variable, so that it becomes offset
1556 if (ninfo->is_special_var
1557 || ninfo->is_artificial_var
1558 || ninfo->is_unknown_size_var)
1563 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1566 /* Process a constraint C that represents *x = &y. */
1569 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1570 constraint_t c, bitmap delta)
1572 unsigned int rhs = c->rhs.var;
1576 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1577 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1579 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1580 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
1582 /* *x != NULL && *x != ANYTHING*/
1586 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1588 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1592 sol = get_varinfo (t)->solution;
1593 if (!bitmap_bit_p (sol, rhs))
1595 bitmap_set_bit (sol, rhs);
1596 if (!TEST_BIT (changed, t))
1598 SET_BIT (changed, t);
1603 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1604 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1609 /* Process a constraint C that represents x = *y, using DELTA as the
1610 starting solution. */
1613 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1616 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1618 bitmap sol = get_varinfo (lhs)->solution;
1622 if (bitmap_bit_p (delta, anything_id))
1624 flag = !bitmap_bit_p (sol, anything_id);
1626 bitmap_set_bit (sol, anything_id);
1629 /* For each variable j in delta (Sol(y)), add
1630 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1631 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1633 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1634 if (type_safe (j, &roffset))
1637 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1640 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1645 /* Adding edges from the special vars is pointless.
1646 They don't have sets that can change. */
1647 if (get_varinfo (t) ->is_special_var)
1648 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1649 else if (int_add_graph_edge (graph, lhs, t, 0))
1650 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1652 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1653 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1658 /* If the LHS solution changed, mark the var as changed. */
1661 get_varinfo (lhs)->solution = sol;
1662 if (!TEST_BIT (changed, lhs))
1664 SET_BIT (changed, lhs);
1670 /* Process a constraint C that represents *x = y. */
1673 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1675 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1676 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1677 bitmap sol = get_varinfo (rhs)->solution;
1681 if (bitmap_bit_p (sol, anything_id))
1683 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1685 varinfo_t jvi = get_varinfo (j);
1687 unsigned int loff = c->lhs.offset;
1688 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
1691 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1696 if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id))
1698 bitmap_set_bit (get_varinfo (t)->solution, anything_id);
1699 if (!TEST_BIT (changed, t))
1701 SET_BIT (changed, t);
1709 /* For each member j of delta (Sol(x)), add an edge from y to j and
1710 union Sol(y) into Sol(j) */
1711 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1713 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1714 if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var))
1718 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1720 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1724 if (int_add_graph_edge (graph, t, rhs, roff))
1726 bitmap tmp = get_varinfo (t)->solution;
1727 if (set_union_with_increment (tmp, sol, roff))
1729 get_varinfo (t)->solution = tmp;
1731 sol = get_varinfo (rhs)->solution;
1732 if (!TEST_BIT (changed, t))
1734 SET_BIT (changed, t);
1740 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1741 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1745 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1746 constraint (IE *x = &y, x = *y, and *x = y). */
1749 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1751 if (c->lhs.type == DEREF)
1753 if (c->rhs.type == ADDRESSOF)
1756 do_da_constraint (graph, c, delta);
1761 do_ds_constraint (graph, c, delta);
1767 if (!(get_varinfo (c->lhs.var)->is_special_var))
1768 do_sd_constraint (graph, c, delta);
1772 /* Initialize and return a new SCC info structure. */
1774 static struct scc_info *
1775 init_scc_info (void)
1777 struct scc_info *si = XNEW (struct scc_info);
1778 size_t size = VEC_length (varinfo_t, varmap);
1780 si->current_index = 0;
1781 si->visited = sbitmap_alloc (size);
1782 sbitmap_zero (si->visited);
1783 si->in_component = sbitmap_alloc (size);
1784 sbitmap_ones (si->in_component);
1785 si->visited_index = XCNEWVEC (unsigned int, size + 1);
1786 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1787 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1791 /* Free an SCC info structure pointed to by SI */
1794 free_scc_info (struct scc_info *si)
1796 sbitmap_free (si->visited);
1797 sbitmap_free (si->in_component);
1798 free (si->visited_index);
1799 VEC_free (unsigned, heap, si->scc_stack);
1800 VEC_free (unsigned, heap, si->unification_queue);
1805 /* Find cycles in GRAPH that occur, using strongly connected components, and
1806 collapse the cycles into a single representative node. if UPDATE_CHANGED
1807 is true, then update the changed sbitmap to note those nodes whose
1808 solutions have changed as a result of collapsing. */
1811 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1814 unsigned int size = VEC_length (varinfo_t, varmap);
1815 struct scc_info *si = init_scc_info ();
1817 for (i = 0; i != size; ++i)
1818 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1819 scc_visit (graph, si, i);
1821 process_unification_queue (graph, si, update_changed);
1825 /* Compute a topological ordering for GRAPH, and store the result in the
1826 topo_info structure TI. */
1829 compute_topo_order (constraint_graph_t graph,
1830 struct topo_info *ti)
1833 unsigned int size = VEC_length (varinfo_t, varmap);
1835 for (i = 0; i != size; ++i)
1836 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1837 topo_visit (graph, ti, i);
1840 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1843 bitmap_other_than_zero_bit_set (bitmap b)
1848 if (bitmap_empty_p (b))
1850 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1855 /* Perform offline variable substitution.
1857 This is a linear time way of identifying variables that must have
1858 equivalent points-to sets, including those caused by static cycles,
1859 and single entry subgraphs, in the constraint graph.
1861 The technique is described in "Off-line variable substitution for
1862 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1863 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1866 perform_var_substitution (constraint_graph_t graph)
1868 struct topo_info *ti = init_topo_info ();
1870 bitmap_obstack_initialize (&iteration_obstack);
1871 /* Compute the topological ordering of the graph, then visit each
1872 node in topological order. */
1873 compute_topo_order (graph, ti);
1875 while (VEC_length (unsigned, ti->topo_order) != 0)
1877 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1879 varinfo_t vi = get_varinfo (i);
1880 bool okay_to_elim = false;
1881 unsigned int root = VEC_length (varinfo_t, varmap);
1882 VEC(constraint_edge_t,heap) *predvec = graph->preds[i];
1883 constraint_edge_t ce = NULL;
1888 /* We can't eliminate things whose address is taken, or which is
1889 the target of a dereference. */
1890 if (vi->address_taken || vi->indirect_target)
1893 /* See if all predecessors of I are ripe for elimination */
1894 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[i], 0, k, bi)
1897 w = get_varinfo (k)->node;
1899 /* We can't eliminate the node if one of the predecessors is
1900 part of a different strongly connected component. */
1904 okay_to_elim = true;
1908 okay_to_elim = false;
1912 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1913 then Solution(i) is a subset of Solution (w), where w is a
1914 predecessor in the graph.
1915 Corollary: If all predecessors of i have the same
1916 points-to set, then i has that same points-to set as
1917 those predecessors. */
1918 tmp = BITMAP_ALLOC (NULL);
1919 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1920 get_varinfo (w)->solution);
1921 if (!bitmap_empty_p (tmp))
1923 okay_to_elim = false;
1932 VEC_iterate (constraint_edge_t, predvec, pred, ce);
1937 weight = *(get_graph_weights (graph, i, ce->dest));
1939 /* We can't eliminate variables that have nonzero weighted
1940 edges between them. */
1941 if (weight && bitmap_other_than_zero_bit_set (weight))
1943 okay_to_elim = false;
1946 w = get_varinfo (ce->dest)->node;
1948 /* We can't eliminate the node if one of the predecessors is
1949 part of a different strongly connected component. */
1953 okay_to_elim = true;
1957 okay_to_elim = false;
1961 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1962 then Solution(i) is a subset of Solution (w), where w is a
1963 predecessor in the graph.
1964 Corollary: If all predecessors of i have the same
1965 points-to set, then i has that same points-to set as
1966 those predecessors. */
1967 tmp = BITMAP_ALLOC (NULL);
1968 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1969 get_varinfo (w)->solution);
1970 if (!bitmap_empty_p (tmp))
1972 okay_to_elim = false;
1979 /* See if the root is different than the original node.
1980 If so, we've found an equivalence. */
1981 if (root != get_varinfo (i)->node && okay_to_elim)
1983 /* Found an equivalence */
1984 get_varinfo (i)->node = root;
1985 collapse_nodes (graph, root, i);
1986 if (dump_file && (dump_flags & TDF_DETAILS))
1987 fprintf (dump_file, "Collapsing %s into %s\n",
1988 get_varinfo (i)->name,
1989 get_varinfo (root)->name);
1990 stats.collapsed_vars++;
1994 bitmap_obstack_release (&iteration_obstack);
1995 free_topo_info (ti);
1998 /* Solve the constraint graph GRAPH using our worklist solver.
1999 This is based on the PW* family of solvers from the "Efficient Field
2000 Sensitive Pointer Analysis for C" paper.
2001 It works by iterating over all the graph nodes, processing the complex
2002 constraints and propagating the copy constraints, until everything stops
2003 changed. This corresponds to steps 6-8 in the solving list given above. */
2006 solve_graph (constraint_graph_t graph)
2008 unsigned int size = VEC_length (varinfo_t, varmap);
2011 changed_count = size;
2012 changed = sbitmap_alloc (size);
2013 sbitmap_ones (changed);
2015 /* The already collapsed/unreachable nodes will never change, so we
2016 need to account for them in changed_count. */
2017 for (i = 0; i < size; i++)
2018 if (get_varinfo (i)->node != i)
2021 while (changed_count > 0)
2024 struct topo_info *ti = init_topo_info ();
2027 bitmap_obstack_initialize (&iteration_obstack);
2031 /* We already did cycle elimination once, when we did
2032 variable substitution, so we don't need it again for the
2034 if (stats.iterations > 1)
2035 find_and_collapse_graph_cycles (graph, true);
2040 compute_topo_order (graph, ti);
2042 while (VEC_length (unsigned, ti->topo_order) != 0)
2044 i = VEC_pop (unsigned, ti->topo_order);
2045 gcc_assert (get_varinfo (i)->node == i);
2047 /* If the node has changed, we need to process the
2048 complex constraints and outgoing edges again. */
2049 if (TEST_BIT (changed, i))
2053 constraint_edge_t e = NULL;
2056 VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
2057 VEC(constraint_edge_t,heap) *succs;
2058 bool solution_empty;
2060 RESET_BIT (changed, i);
2063 solution = get_varinfo (i)->solution;
2064 solution_empty = bitmap_empty_p (solution);
2066 /* Process the complex constraints */
2067 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2069 /* The only complex constraint that can change our
2070 solution to non-empty, given an empty solution,
2071 is a constraint where the lhs side is receiving
2072 some set from elsewhere. */
2073 if (!solution_empty || c->lhs.type != DEREF)
2074 do_complex_constraint (graph, c, solution);
2077 solution_empty = bitmap_empty_p (solution);
2079 if (!solution_empty)
2081 /* Propagate solution to all successors. */
2082 succs = graph->succs[i];
2084 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[i],
2087 bitmap tmp = get_varinfo (j)->solution;
2090 flag = set_union_with_increment (tmp, solution, 0);
2094 get_varinfo (j)->solution = tmp;
2095 if (!TEST_BIT (changed, j))
2097 SET_BIT (changed, j);
2102 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
2104 bitmap tmp = get_varinfo (e->dest)->solution;
2107 bitmap weights = e->weights;
2110 gcc_assert (weights && !bitmap_empty_p (weights));
2111 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
2112 flag |= set_union_with_increment (tmp, solution, k);
2116 get_varinfo (e->dest)->solution = tmp;
2117 if (!TEST_BIT (changed, e->dest))
2119 SET_BIT (changed, e->dest);
2127 free_topo_info (ti);
2128 bitmap_obstack_release (&iteration_obstack);
2131 sbitmap_free (changed);
2135 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
2137 /* Map from trees to variable ids. */
2138 static htab_t id_for_tree;
2140 typedef struct tree_id
2146 /* Hash a tree id structure. */
2149 tree_id_hash (const void *p)
2151 const tree_id_t ta = (tree_id_t) p;
2152 return htab_hash_pointer (ta->t);
2155 /* Return true if the tree in P1 and the tree in P2 are the same. */
2158 tree_id_eq (const void *p1, const void *p2)
2160 const tree_id_t ta1 = (tree_id_t) p1;
2161 const tree_id_t ta2 = (tree_id_t) p2;
2162 return ta1->t == ta2->t;
2165 /* Insert ID as the variable id for tree T in the hashtable. */
2168 insert_id_for_tree (tree t, int id)
2171 struct tree_id finder;
2175 slot = htab_find_slot (id_for_tree, &finder, INSERT);
2176 gcc_assert (*slot == NULL);
2177 new_pair = XNEW (struct tree_id);
2180 *slot = (void *)new_pair;
2183 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
2184 exist in the hash table, return false, otherwise, return true and
2185 set *ID to the id we found. */
2188 lookup_id_for_tree (tree t, unsigned int *id)
2191 struct tree_id finder;
2194 pair = htab_find (id_for_tree, &finder);
2201 /* Return a printable name for DECL */
2204 alias_get_name (tree decl)
2206 const char *res = get_name (decl);
2208 int num_printed = 0;
2217 if (TREE_CODE (decl) == SSA_NAME)
2219 num_printed = asprintf (&temp, "%s_%u",
2220 alias_get_name (SSA_NAME_VAR (decl)),
2221 SSA_NAME_VERSION (decl));
2223 else if (DECL_P (decl))
2225 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2227 if (num_printed > 0)
2229 res = ggc_strdup (temp);
2235 /* Find the variable id for tree T in the hashtable.
2236 If T doesn't exist in the hash table, create an entry for it. */
2239 get_id_for_tree (tree t)
2242 struct tree_id finder;
2245 pair = htab_find (id_for_tree, &finder);
2247 return create_variable_info_for (t, alias_get_name (t));
2252 /* Get a constraint expression from an SSA_VAR_P node. */
2254 static struct constraint_expr
2255 get_constraint_exp_from_ssa_var (tree t)
2257 struct constraint_expr cexpr;
2259 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2261 /* For parameters, get at the points-to set for the actual parm
2263 if (TREE_CODE (t) == SSA_NAME
2264 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2265 && default_def (SSA_NAME_VAR (t)) == t)
2266 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
2268 cexpr.type = SCALAR;
2270 cexpr.var = get_id_for_tree (t);
2271 /* If we determine the result is "anything", and we know this is readonly,
2272 say it points to readonly memory instead. */
2273 if (cexpr.var == anything_id && TREE_READONLY (t))
2275 cexpr.type = ADDRESSOF;
2276 cexpr.var = readonly_id;
2283 /* Process a completed constraint T, and add it to the constraint
2287 process_constraint (constraint_t t)
2289 struct constraint_expr rhs = t->rhs;
2290 struct constraint_expr lhs = t->lhs;
2292 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2293 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2295 if (lhs.type == DEREF)
2296 get_varinfo (lhs.var)->directly_dereferenced = true;
2297 if (rhs.type == DEREF)
2298 get_varinfo (rhs.var)->directly_dereferenced = true;
2300 /* ANYTHING == ANYTHING is pointless. */
2301 if (lhs.var == anything_id && rhs.var == anything_id)
2304 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2305 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
2310 process_constraint (t);
2312 /* This can happen in our IR with things like n->a = *p */
2313 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2315 /* Split into tmp = *rhs, *lhs = tmp */
2316 tree rhsdecl = get_varinfo (rhs.var)->decl;
2317 tree pointertype = TREE_TYPE (rhsdecl);
2318 tree pointedtotype = TREE_TYPE (pointertype);
2319 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2320 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2322 /* If this is an aggregate of known size, we should have passed
2323 this off to do_structure_copy, and it should have broken it
2325 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
2326 || get_varinfo (rhs.var)->is_unknown_size_var);
2328 process_constraint (new_constraint (tmplhs, rhs));
2329 process_constraint (new_constraint (lhs, tmplhs));
2331 else if (rhs.type == ADDRESSOF)
2334 gcc_assert (rhs.offset == 0);
2336 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
2337 vi->address_taken = true;
2339 VEC_safe_push (constraint_t, heap, constraints, t);
2343 if (lhs.type != DEREF && rhs.type == DEREF)
2344 get_varinfo (lhs.var)->indirect_target = true;
2345 VEC_safe_push (constraint_t, heap, constraints, t);
2349 /* Return true if T is a variable of a type that could contain
2353 could_have_pointers (tree t)
2355 tree type = TREE_TYPE (t);
2357 if (POINTER_TYPE_P (type) || AGGREGATE_TYPE_P (type)
2358 || TREE_CODE (type) == COMPLEX_TYPE)
2363 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2366 static unsigned HOST_WIDE_INT
2367 bitpos_of_field (const tree fdecl)
2370 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
2371 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
2374 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
2375 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
2379 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2380 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2383 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
2384 const unsigned HOST_WIDE_INT fieldsize,
2385 const unsigned HOST_WIDE_INT accesspos,
2386 const unsigned HOST_WIDE_INT accesssize)
2388 if (fieldpos == accesspos && fieldsize == accesssize)
2390 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
2392 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2398 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2401 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results)
2404 HOST_WIDE_INT bitsize = -1;
2405 HOST_WIDE_INT bitmaxsize = -1;
2406 HOST_WIDE_INT bitpos;
2408 struct constraint_expr *result;
2409 unsigned int beforelength = VEC_length (ce_s, *results);
2411 /* Some people like to do cute things like take the address of
2414 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2415 forzero = TREE_OPERAND (forzero, 0);
2417 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2419 struct constraint_expr temp;
2422 temp.var = integer_id;
2424 VEC_safe_push (ce_s, heap, *results, &temp);
2428 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2430 /* String constants's are readonly, so there is nothing to really do
2432 if (TREE_CODE (t) == STRING_CST)
2435 get_constraint_for (t, results);
2436 result = VEC_last (ce_s, *results);
2437 result->offset = bitpos;
2439 gcc_assert (beforelength + 1 == VEC_length (ce_s, *results));
2441 /* This can also happen due to weird offsetof type macros. */
2442 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2443 result->type = SCALAR;
2445 if (result->type == SCALAR)
2447 /* In languages like C, you can access one past the end of an
2448 array. You aren't allowed to dereference it, so we can
2449 ignore this constraint. When we handle pointer subtraction,
2450 we may have to do something cute here. */
2452 if (result->offset < get_varinfo (result->var)->fullsize
2455 /* It's also not true that the constraint will actually start at the
2456 right offset, it may start in some padding. We only care about
2457 setting the constraint to the first actual field it touches, so
2460 for (curr = get_varinfo (result->var); curr; curr = curr->next)
2462 if (offset_overlaps_with_access (curr->offset, curr->size,
2463 result->offset, bitmaxsize))
2465 result->var = curr->id;
2469 /* assert that we found *some* field there. The user couldn't be
2470 accessing *only* padding. */
2471 /* Still the user could access one past the end of an array
2472 embedded in a struct resulting in accessing *only* padding. */
2473 gcc_assert (curr || ref_contains_array_ref (orig_t));
2475 else if (bitmaxsize == 0)
2477 if (dump_file && (dump_flags & TDF_DETAILS))
2478 fprintf (dump_file, "Access to zero-sized part of variable,"
2482 if (dump_file && (dump_flags & TDF_DETAILS))
2483 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2490 /* Dereference the constraint expression CONS, and return the result.
2491 DEREF (ADDRESSOF) = SCALAR
2492 DEREF (SCALAR) = DEREF
2493 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2494 This is needed so that we can handle dereferencing DEREF constraints. */
2497 do_deref (VEC (ce_s, heap) **constraints)
2499 struct constraint_expr *c;
2501 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2503 if (c->type == SCALAR)
2505 else if (c->type == ADDRESSOF)
2507 else if (c->type == DEREF)
2509 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
2510 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2511 process_constraint (new_constraint (tmplhs, *c));
2512 c->var = tmplhs.var;
2519 /* Lookup a nonlocal variable for type FROM, and return it if we find
2523 nonlocal_lookup (tree from)
2525 struct tree_map *h, in;
2528 h = htab_find_with_hash (nonlocal_for_type, &in,
2529 htab_hash_pointer (from));
2535 /* Insert a mapping FROM->TO in the nonlocal variable for type
2539 nonlocal_insert (tree from, tree to)
2544 h = ggc_alloc (sizeof (struct tree_map));
2545 h->hash = htab_hash_pointer (from);
2548 loc = htab_find_slot_with_hash (nonlocal_for_type, h, h->hash,
2550 *(struct tree_map **) loc = h;
2553 /* Create a nonlocal variable of TYPE to represent nonlocals we can
2557 create_nonlocal_var (tree type)
2559 tree nonlocal = create_tmp_var_raw (type, "NONLOCAL");
2561 if (referenced_vars)
2562 add_referenced_var (nonlocal);
2564 DECL_PTA_ARTIFICIAL (nonlocal) = 1;
2565 DECL_EXTERNAL (nonlocal) = 1;
2566 nonlocal_insert (type, nonlocal);
2570 /* Get or create a nonlocal variable for TYPE, and return its
2571 variable info id. */
2574 get_nonlocal_id_for_type (tree type)
2577 unsigned int nonlocal_id;
2578 varinfo_t nonlocal_vi;
2580 /* For strict aliasing, we have one variable per type. For
2581 non-strict aliasing, we only need one variable. */
2582 if (flag_strict_aliasing != 0)
2584 nonlocal = nonlocal_lookup (type);
2590 nonlocal = create_nonlocal_var (void_type_node);
2591 nonlocal_all = nonlocal;
2594 nonlocal = nonlocal_all;
2597 if (nonlocal && lookup_id_for_tree (nonlocal, &nonlocal_id))
2602 gcc_assert (flag_strict_aliasing != 0);
2603 nonlocal = create_nonlocal_var (type);
2606 /* Create variable info for the nonlocal var if it does not
2608 nonlocal_id = create_variable_info_for (nonlocal,
2609 get_name (nonlocal));
2610 nonlocal_vi = get_varinfo (nonlocal_id);
2611 nonlocal_vi->is_artificial_var = 1;
2612 nonlocal_vi->is_heap_var = 1;
2613 nonlocal_vi->is_unknown_size_var = 1;
2614 nonlocal_vi->directly_dereferenced = true;
2619 /* Given a tree T, return the constraint expression for it. */
2622 get_constraint_for (tree t, VEC (ce_s, heap) **results)
2624 struct constraint_expr temp;
2626 /* x = integer is all glommed to a single variable, which doesn't
2627 point to anything by itself. That is, of course, unless it is an
2628 integer constant being treated as a pointer, in which case, we
2629 will return that this is really the addressof anything. This
2630 happens below, since it will fall into the default case. The only
2631 case we know something about an integer treated like a pointer is
2632 when it is the NULL pointer, and then we just say it points to
2634 if (TREE_CODE (t) == INTEGER_CST
2635 && !POINTER_TYPE_P (TREE_TYPE (t)))
2637 temp.var = integer_id;
2640 VEC_safe_push (ce_s, heap, *results, &temp);
2643 else if (TREE_CODE (t) == INTEGER_CST
2644 && integer_zerop (t))
2646 temp.var = nothing_id;
2647 temp.type = ADDRESSOF;
2649 VEC_safe_push (ce_s, heap, *results, &temp);
2653 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2655 case tcc_expression:
2657 switch (TREE_CODE (t))
2661 struct constraint_expr *c;
2663 tree exp = TREE_OPERAND (t, 0);
2664 tree pttype = TREE_TYPE (TREE_TYPE (t));
2666 get_constraint_for (exp, results);
2667 /* Make sure we capture constraints to all elements
2669 if ((handled_component_p (exp)
2670 && ref_contains_array_ref (exp))
2671 || TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE)
2673 struct constraint_expr *origrhs;
2675 struct constraint_expr tmp;
2677 if (VEC_length (ce_s, *results) == 0)
2680 gcc_assert (VEC_length (ce_s, *results) == 1);
2681 origrhs = VEC_last (ce_s, *results);
2683 VEC_pop (ce_s, *results);
2684 origvar = get_varinfo (origrhs->var);
2685 for (; origvar; origvar = origvar->next)
2687 tmp.var = origvar->id;
2688 VEC_safe_push (ce_s, heap, *results, &tmp);
2691 else if (VEC_length (ce_s, *results) == 1
2692 && (AGGREGATE_TYPE_P (pttype)
2693 || TREE_CODE (pttype) == COMPLEX_TYPE))
2695 struct constraint_expr *origrhs;
2697 struct constraint_expr tmp;
2699 gcc_assert (VEC_length (ce_s, *results) == 1);
2700 origrhs = VEC_last (ce_s, *results);
2702 VEC_pop (ce_s, *results);
2703 origvar = get_varinfo (origrhs->var);
2704 for (; origvar; origvar = origvar->next)
2706 tmp.var = origvar->id;
2707 VEC_safe_push (ce_s, heap, *results, &tmp);
2711 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2713 if (c->type == DEREF)
2716 c->type = ADDRESSOF;
2722 /* XXX: In interprocedural mode, if we didn't have the
2723 body, we would need to do *each pointer argument =
2725 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2728 tree heapvar = heapvar_lookup (t);
2730 if (heapvar == NULL)
2732 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2733 DECL_EXTERNAL (heapvar) = 1;
2734 if (referenced_vars)
2735 add_referenced_var (heapvar);
2736 heapvar_insert (t, heapvar);
2739 temp.var = create_variable_info_for (heapvar,
2740 alias_get_name (heapvar));
2742 vi = get_varinfo (temp.var);
2743 vi->is_artificial_var = 1;
2744 vi->is_heap_var = 1;
2745 temp.type = ADDRESSOF;
2747 VEC_safe_push (ce_s, heap, *results, &temp);
2752 temp.var = escaped_vars_id;
2755 VEC_safe_push (ce_s, heap, *results, &temp);
2762 temp.type = ADDRESSOF;
2763 temp.var = anything_id;
2765 VEC_safe_push (ce_s, heap, *results, &temp);
2772 switch (TREE_CODE (t))
2776 get_constraint_for (TREE_OPERAND (t, 0), results);
2781 case ARRAY_RANGE_REF:
2783 get_constraint_for_component_ref (t, results);
2787 temp.type = ADDRESSOF;
2788 temp.var = anything_id;
2790 VEC_safe_push (ce_s, heap, *results, &temp);
2797 switch (TREE_CODE (t))
2801 case NON_LVALUE_EXPR:
2803 tree op = TREE_OPERAND (t, 0);
2805 /* Cast from non-pointer to pointers are bad news for us.
2806 Anything else, we see through */
2807 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2808 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2810 get_constraint_for (op, results);
2818 temp.type = ADDRESSOF;
2819 temp.var = anything_id;
2821 VEC_safe_push (ce_s, heap, *results, &temp);
2826 case tcc_exceptional:
2828 switch (TREE_CODE (t))
2832 get_constraint_for (PHI_RESULT (t), results);
2838 struct constraint_expr temp;
2839 temp = get_constraint_exp_from_ssa_var (t);
2840 VEC_safe_push (ce_s, heap, *results, &temp);
2846 temp.type = ADDRESSOF;
2847 temp.var = anything_id;
2849 VEC_safe_push (ce_s, heap, *results, &temp);
2854 case tcc_declaration:
2856 struct constraint_expr temp;
2857 temp = get_constraint_exp_from_ssa_var (t);
2858 VEC_safe_push (ce_s, heap, *results, &temp);
2863 temp.type = ADDRESSOF;
2864 temp.var = anything_id;
2866 VEC_safe_push (ce_s, heap, *results, &temp);
2873 /* Handle the structure copy case where we have a simple structure copy
2874 between LHS and RHS that is of SIZE (in bits)
2876 For each field of the lhs variable (lhsfield)
2877 For each field of the rhs variable at lhsfield.offset (rhsfield)
2878 add the constraint lhsfield = rhsfield
2880 If we fail due to some kind of type unsafety or other thing we
2881 can't handle, return false. We expect the caller to collapse the
2882 variable in that case. */
2885 do_simple_structure_copy (const struct constraint_expr lhs,
2886 const struct constraint_expr rhs,
2887 const unsigned HOST_WIDE_INT size)
2889 varinfo_t p = get_varinfo (lhs.var);
2890 unsigned HOST_WIDE_INT pstart, last;
2892 last = p->offset + size;
2893 for (; p && p->offset < last; p = p->next)
2896 struct constraint_expr templhs = lhs;
2897 struct constraint_expr temprhs = rhs;
2898 unsigned HOST_WIDE_INT fieldoffset;
2900 templhs.var = p->id;
2901 q = get_varinfo (temprhs.var);
2902 fieldoffset = p->offset - pstart;
2903 q = first_vi_for_offset (q, q->offset + fieldoffset);
2906 temprhs.var = q->id;
2907 process_constraint (new_constraint (templhs, temprhs));
2913 /* Handle the structure copy case where we have a structure copy between a
2914 aggregate on the LHS and a dereference of a pointer on the RHS
2915 that is of SIZE (in bits)
2917 For each field of the lhs variable (lhsfield)
2918 rhs.offset = lhsfield->offset
2919 add the constraint lhsfield = rhs
2923 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2924 const struct constraint_expr rhs,
2925 const unsigned HOST_WIDE_INT size)
2927 varinfo_t p = get_varinfo (lhs.var);
2928 unsigned HOST_WIDE_INT pstart,last;
2930 last = p->offset + size;
2932 for (; p && p->offset < last; p = p->next)
2935 struct constraint_expr templhs = lhs;
2936 struct constraint_expr temprhs = rhs;
2937 unsigned HOST_WIDE_INT fieldoffset;
2940 if (templhs.type == SCALAR)
2941 templhs.var = p->id;
2943 templhs.offset = p->offset;
2945 q = get_varinfo (temprhs.var);
2946 fieldoffset = p->offset - pstart;
2947 temprhs.offset += fieldoffset;
2948 process_constraint (new_constraint (templhs, temprhs));
2952 /* Handle the structure copy case where we have a structure copy
2953 between a aggregate on the RHS and a dereference of a pointer on
2954 the LHS that is of SIZE (in bits)
2956 For each field of the rhs variable (rhsfield)
2957 lhs.offset = rhsfield->offset
2958 add the constraint lhs = rhsfield
2962 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2963 const struct constraint_expr rhs,
2964 const unsigned HOST_WIDE_INT size)
2966 varinfo_t p = get_varinfo (rhs.var);
2967 unsigned HOST_WIDE_INT pstart,last;
2969 last = p->offset + size;
2971 for (; p && p->offset < last; p = p->next)
2974 struct constraint_expr templhs = lhs;
2975 struct constraint_expr temprhs = rhs;
2976 unsigned HOST_WIDE_INT fieldoffset;
2979 if (temprhs.type == SCALAR)
2980 temprhs.var = p->id;
2982 temprhs.offset = p->offset;
2984 q = get_varinfo (templhs.var);
2985 fieldoffset = p->offset - pstart;
2986 templhs.offset += fieldoffset;
2987 process_constraint (new_constraint (templhs, temprhs));
2991 /* Sometimes, frontends like to give us bad type information. This
2992 function will collapse all the fields from VAR to the end of VAR,
2993 into VAR, so that we treat those fields as a single variable.
2994 We return the variable they were collapsed into. */
2997 collapse_rest_of_var (unsigned int var)
2999 varinfo_t currvar = get_varinfo (var);
3002 for (field = currvar->next; field; field = field->next)
3005 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
3006 field->name, currvar->name);
3008 gcc_assert (!field->collapsed_to);
3009 field->collapsed_to = currvar;
3012 currvar->next = NULL;
3013 currvar->size = currvar->fullsize - currvar->offset;
3018 /* Handle aggregate copies by expanding into copies of the respective
3019 fields of the structures. */
3022 do_structure_copy (tree lhsop, tree rhsop)
3024 struct constraint_expr lhs, rhs, tmp;
3025 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3027 unsigned HOST_WIDE_INT lhssize;
3028 unsigned HOST_WIDE_INT rhssize;
3030 get_constraint_for (lhsop, &lhsc);
3031 get_constraint_for (rhsop, &rhsc);
3032 gcc_assert (VEC_length (ce_s, lhsc) == 1);
3033 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3034 lhs = *(VEC_last (ce_s, lhsc));
3035 rhs = *(VEC_last (ce_s, rhsc));
3037 VEC_free (ce_s, heap, lhsc);
3038 VEC_free (ce_s, heap, rhsc);
3040 /* If we have special var = x, swap it around. */
3041 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
3048 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
3049 possible it's something we could handle. However, most cases falling
3050 into this are dealing with transparent unions, which are slightly
3052 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
3054 rhs.type = ADDRESSOF;
3055 rhs.var = anything_id;
3058 /* If the RHS is a special var, or an addressof, set all the LHS fields to
3059 that special var. */
3060 if (rhs.var <= integer_id)
3062 for (p = get_varinfo (lhs.var); p; p = p->next)
3064 struct constraint_expr templhs = lhs;
3065 struct constraint_expr temprhs = rhs;
3067 if (templhs.type == SCALAR )
3068 templhs.var = p->id;
3070 templhs.offset += p->offset;
3071 process_constraint (new_constraint (templhs, temprhs));
3076 tree rhstype = TREE_TYPE (rhsop);
3077 tree lhstype = TREE_TYPE (lhsop);
3081 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
3082 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
3084 /* If we have a variably sized types on the rhs or lhs, and a deref
3085 constraint, add the constraint, lhsconstraint = &ANYTHING.
3086 This is conservatively correct because either the lhs is an unknown
3087 sized var (if the constraint is SCALAR), or the lhs is a DEREF
3088 constraint, and every variable it can point to must be unknown sized
3089 anyway, so we don't need to worry about fields at all. */
3090 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
3091 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
3093 rhs.var = anything_id;
3094 rhs.type = ADDRESSOF;
3096 process_constraint (new_constraint (lhs, rhs));
3100 /* The size only really matters insofar as we don't set more or less of
3101 the variable. If we hit an unknown size var, the size should be the
3102 whole darn thing. */
3103 if (get_varinfo (rhs.var)->is_unknown_size_var)
3106 rhssize = TREE_INT_CST_LOW (rhstypesize);
3108 if (get_varinfo (lhs.var)->is_unknown_size_var)
3111 lhssize = TREE_INT_CST_LOW (lhstypesize);
3114 if (rhs.type == SCALAR && lhs.type == SCALAR)
3116 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
3118 lhs.var = collapse_rest_of_var (lhs.var);
3119 rhs.var = collapse_rest_of_var (rhs.var);
3124 process_constraint (new_constraint (lhs, rhs));
3127 else if (lhs.type != DEREF && rhs.type == DEREF)
3128 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3129 else if (lhs.type == DEREF && rhs.type != DEREF)
3130 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3133 tree pointedtotype = lhstype;
3136 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3137 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
3138 do_structure_copy (tmpvar, rhsop);
3139 do_structure_copy (lhsop, tmpvar);
3144 /* Update related alias information kept in AI. This is used when
3145 building name tags, alias sets and deciding grouping heuristics.
3146 STMT is the statement to process. This function also updates
3147 ADDRESSABLE_VARS. */
3150 update_alias_info (tree stmt, struct alias_info *ai)
3153 use_operand_p use_p;
3155 enum escape_type stmt_escape_type = is_escape_site (stmt);
3158 if (stmt_escape_type == ESCAPE_TO_CALL
3159 || stmt_escape_type == ESCAPE_TO_PURE_CONST)
3161 ai->num_calls_found++;
3162 if (stmt_escape_type == ESCAPE_TO_PURE_CONST)
3163 ai->num_pure_const_calls_found++;
3166 /* Mark all the variables whose address are taken by the statement. */
3167 addr_taken = addresses_taken (stmt);
3170 bitmap_ior_into (addressable_vars, addr_taken);
3172 /* If STMT is an escape point, all the addresses taken by it are
3174 if (stmt_escape_type != NO_ESCAPE)
3179 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
3181 tree rvar = referenced_var (i);
3182 if (!unmodifiable_var_p (rvar))
3183 mark_call_clobbered (rvar, stmt_escape_type);
3188 /* Process each operand use. If an operand may be aliased, keep
3189 track of how many times it's being used. For pointers, determine
3190 whether they are dereferenced by the statement, or whether their
3191 value escapes, etc. */
3192 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
3196 struct ptr_info_def *pi;
3197 bool is_store, is_potential_deref;
3198 unsigned num_uses, num_derefs;
3200 op = USE_FROM_PTR (use_p);
3202 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
3203 to the set of addressable variables. */
3204 if (TREE_CODE (op) == ADDR_EXPR)
3206 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
3208 /* PHI nodes don't have annotations for pinning the set
3209 of addresses taken, so we collect them here.
3211 FIXME, should we allow PHI nodes to have annotations
3212 so that they can be treated like regular statements?
3213 Currently, they are treated as second-class
3215 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
3219 /* Ignore constants. */
3220 if (TREE_CODE (op) != SSA_NAME)
3223 var = SSA_NAME_VAR (op);
3224 v_ann = var_ann (var);
3226 /* The base variable of an ssa name must be a GIMPLE register, and thus
3227 it cannot be aliased. */
3228 gcc_assert (!may_be_aliased (var));
3230 /* We are only interested in pointers. */
3231 if (!POINTER_TYPE_P (TREE_TYPE (op)))
3234 pi = get_ptr_info (op);
3236 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3237 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
3239 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
3240 VEC_safe_push (tree, heap, ai->processed_ptrs, op);
3243 /* If STMT is a PHI node, then it will not have pointer
3244 dereferences and it will not be an escape point. */
3245 if (TREE_CODE (stmt) == PHI_NODE)
3248 /* Determine whether OP is a dereferenced pointer, and if STMT
3249 is an escape point, whether OP escapes. */
3250 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
3252 /* Handle a corner case involving address expressions of the
3253 form '&PTR->FLD'. The problem with these expressions is that
3254 they do not represent a dereference of PTR. However, if some
3255 other transformation propagates them into an INDIRECT_REF
3256 expression, we end up with '*(&PTR->FLD)' which is folded
3259 So, if the original code had no other dereferences of PTR,
3260 the aliaser will not create memory tags for it, and when
3261 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3262 memory operations will receive no V_MAY_DEF/VUSE operands.
3264 One solution would be to have count_uses_and_derefs consider
3265 &PTR->FLD a dereference of PTR. But that is wrong, since it
3266 is not really a dereference but an offset calculation.
3268 What we do here is to recognize these special ADDR_EXPR
3269 nodes. Since these expressions are never GIMPLE values (they
3270 are not GIMPLE invariants), they can only appear on the RHS
3271 of an assignment and their base address is always an
3272 INDIRECT_REF expression. */
3273 is_potential_deref = false;
3274 if (TREE_CODE (stmt) == MODIFY_EXPR
3275 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
3276 && !is_gimple_val (TREE_OPERAND (stmt, 1)))
3278 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3279 this represents a potential dereference of PTR. */
3280 tree rhs = TREE_OPERAND (stmt, 1);
3281 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3282 if (TREE_CODE (base) == INDIRECT_REF
3283 && TREE_OPERAND (base, 0) == op)
3284 is_potential_deref = true;
3287 if (num_derefs > 0 || is_potential_deref)
3289 /* Mark OP as dereferenced. In a subsequent pass,
3290 dereferenced pointers that point to a set of
3291 variables will be assigned a name tag to alias
3292 all the variables OP points to. */
3293 pi->is_dereferenced = 1;
3295 /* Keep track of how many time we've dereferenced each
3297 NUM_REFERENCES_INC (v_ann);
3299 /* If this is a store operation, mark OP as being
3300 dereferenced to store, otherwise mark it as being
3301 dereferenced to load. */
3303 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3305 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
3308 if (stmt_escape_type != NO_ESCAPE && num_derefs < num_uses)
3310 /* If STMT is an escape point and STMT contains at
3311 least one direct use of OP, then the value of OP
3312 escapes and so the pointed-to variables need to
3313 be marked call-clobbered. */
3314 pi->value_escapes_p = 1;
3315 pi->escape_mask |= stmt_escape_type;
3317 /* If the statement makes a function call, assume
3318 that pointer OP will be dereferenced in a store
3319 operation inside the called function. */
3320 if (get_call_expr_in (stmt))
3322 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3323 pi->is_dereferenced = 1;
3328 if (TREE_CODE (stmt) == PHI_NODE)
3331 /* Update reference counter for definitions to any
3332 potentially aliased variable. This is used in the alias
3333 grouping heuristics. */
3334 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3336 tree var = SSA_NAME_VAR (op);
3337 var_ann_t ann = var_ann (var);
3338 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3339 if (may_be_aliased (var))
3340 NUM_REFERENCES_INC (ann);
3344 /* Mark variables in V_MAY_DEF operands as being written to. */
3345 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
3347 tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
3348 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3353 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3354 Expressions of the type PTR + CST can be handled in two ways:
3356 1- If the constraint for PTR is ADDRESSOF for a non-structure
3357 variable, then we can use it directly because adding or
3358 subtracting a constant may not alter the original ADDRESSOF
3359 constraint (i.e., pointer arithmetic may not legally go outside
3360 an object's boundaries).
3362 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3363 then if CST is a compile-time constant that can be used as an
3364 offset, we can determine which sub-variable will be pointed-to
3367 Return true if the expression is handled. For any other kind of
3368 expression, return false so that each operand can be added as a
3369 separate constraint by the caller. */
3372 handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr)
3375 struct constraint_expr *c, *c2;
3378 VEC (ce_s, heap) *temp = NULL;
3379 unsigned int rhsoffset = 0;
3381 if (TREE_CODE (expr) != PLUS_EXPR
3382 && TREE_CODE (expr) != MINUS_EXPR)
3385 op0 = TREE_OPERAND (expr, 0);
3386 op1 = TREE_OPERAND (expr, 1);
3388 get_constraint_for (op0, &temp);
3389 if (POINTER_TYPE_P (TREE_TYPE (op0))
3390 && TREE_CODE (op1) == INTEGER_CST
3391 && TREE_CODE (expr) == PLUS_EXPR)
3393 rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
3397 for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
3398 for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
3400 if (c2->type == ADDRESSOF && rhsoffset != 0)
3402 varinfo_t temp = get_varinfo (c2->var);
3404 /* An access one after the end of an array is valid,
3405 so simply punt on accesses we cannot resolve. */
3406 temp = first_vi_for_offset (temp, rhsoffset);
3413 c2->offset = rhsoffset;
3414 process_constraint (new_constraint (*c, *c2));
3417 VEC_free (ce_s, heap, temp);
3423 /* Walk statement T setting up aliasing constraints according to the
3424 references found in T. This function is the main part of the
3425 constraint builder. AI points to auxiliary alias information used
3426 when building alias sets and computing alias grouping heuristics. */
3429 find_func_aliases (tree origt)
3432 VEC(ce_s, heap) *lhsc = NULL;
3433 VEC(ce_s, heap) *rhsc = NULL;
3434 struct constraint_expr *c;
3436 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
3437 t = TREE_OPERAND (t, 0);
3439 /* Now build constraints expressions. */
3440 if (TREE_CODE (t) == PHI_NODE)
3442 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))));
3444 /* Only care about pointers and structures containing
3446 if (could_have_pointers (PHI_RESULT (t)))
3451 /* For a phi node, assign all the arguments to
3453 get_constraint_for (PHI_RESULT (t), &lhsc);
3454 for (i = 0; i < PHI_NUM_ARGS (t); i++)
3457 tree strippedrhs = PHI_ARG_DEF (t, i);
3459 STRIP_NOPS (strippedrhs);
3460 rhstype = TREE_TYPE (strippedrhs);
3461 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
3463 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3465 struct constraint_expr *c2;
3466 while (VEC_length (ce_s, rhsc) > 0)
3468 c2 = VEC_last (ce_s, rhsc);
3469 process_constraint (new_constraint (*c, *c2));
3470 VEC_pop (ce_s, rhsc);
3476 /* In IPA mode, we need to generate constraints to pass call
3477 arguments through their calls. There are two case, either a
3478 modify_expr when we are returning a value, or just a plain
3479 call_expr when we are not. */
3480 else if (in_ipa_mode
3481 && ((TREE_CODE (t) == MODIFY_EXPR
3482 && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR
3483 && !(call_expr_flags (TREE_OPERAND (t, 1))
3484 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
3485 || (TREE_CODE (t) == CALL_EXPR
3486 && !(call_expr_flags (t)
3487 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))))
3496 if (TREE_CODE (t) == MODIFY_EXPR)
3498 lhsop = TREE_OPERAND (t, 0);
3499 rhsop = TREE_OPERAND (t, 1);
3506 decl = get_callee_fndecl (rhsop);
3508 /* If we can directly resolve the function being called, do so.
3509 Otherwise, it must be some sort of indirect expression that
3510 we should still be able to handle. */
3513 varid = get_id_for_tree (decl);
3517 decl = TREE_OPERAND (rhsop, 0);
3518 varid = get_id_for_tree (decl);
3521 /* Assign all the passed arguments to the appropriate incoming
3522 parameters of the function. */
3523 fi = get_varinfo (varid);
3524 arglist = TREE_OPERAND (rhsop, 1);
3526 for (;arglist; arglist = TREE_CHAIN (arglist))
3528 tree arg = TREE_VALUE (arglist);
3529 struct constraint_expr lhs ;
3530 struct constraint_expr *rhsp;
3532 get_constraint_for (arg, &rhsc);
3533 if (TREE_CODE (decl) != FUNCTION_DECL)
3542 lhs.var = first_vi_for_offset (fi, i)->id;
3545 while (VEC_length (ce_s, rhsc) != 0)
3547 rhsp = VEC_last (ce_s, rhsc);
3548 process_constraint (new_constraint (lhs, *rhsp));
3549 VEC_pop (ce_s, rhsc);
3553 /* If we are returning a value, assign it to the result. */
3556 struct constraint_expr rhs;
3557 struct constraint_expr *lhsp;
3560 get_constraint_for (lhsop, &lhsc);
3561 if (TREE_CODE (decl) != FUNCTION_DECL)
3570 rhs.var = first_vi_for_offset (fi, i)->id;
3573 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3574 process_constraint (new_constraint (*lhsp, rhs));
3577 /* Otherwise, just a regular assignment statement. */
3578 else if (TREE_CODE (t) == MODIFY_EXPR)
3580 tree lhsop = TREE_OPERAND (t, 0);
3581 tree rhsop = TREE_OPERAND (t, 1);
3584 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3585 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)
3586 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop))
3587 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE))
3589 do_structure_copy (lhsop, rhsop);
3593 /* Only care about operations with pointers, structures
3594 containing pointers, dereferences, and call expressions. */
3595 if (could_have_pointers (lhsop)
3596 || TREE_CODE (rhsop) == CALL_EXPR)
3598 get_constraint_for (lhsop, &lhsc);
3599 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
3601 /* RHS that consist of unary operations,
3602 exceptional types, or bare decls/constants, get
3603 handled directly by get_constraint_for. */
3605 case tcc_declaration:
3607 case tcc_exceptional:
3608 case tcc_expression:
3613 get_constraint_for (rhsop, &rhsc);
3614 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3616 struct constraint_expr *c2;
3619 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3620 process_constraint (new_constraint (*c, *c2));
3628 /* For pointer arithmetic of the form
3629 PTR + CST, we can simply use PTR's
3630 constraint because pointer arithmetic is
3631 not allowed to go out of bounds. */
3632 if (handle_ptr_arith (lhsc, rhsop))
3637 /* Otherwise, walk each operand. Notice that we
3638 can't use the operand interface because we need
3639 to process expressions other than simple operands
3640 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3642 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
3644 tree op = TREE_OPERAND (rhsop, i);
3647 gcc_assert (VEC_length (ce_s, rhsc) == 0);
3648 get_constraint_for (op, &rhsc);
3649 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3651 struct constraint_expr *c2;
3652 while (VEC_length (ce_s, rhsc) > 0)
3654 c2 = VEC_last (ce_s, rhsc);
3655 process_constraint (new_constraint (*c, *c2));
3656 VEC_pop (ce_s, rhsc);
3665 /* After promoting variables and computing aliasing we will
3666 need to re-scan most statements. FIXME: Try to minimize the
3667 number of statements re-scanned. It's not really necessary to
3668 re-scan *all* statements. */
3669 mark_stmt_modified (origt);
3670 VEC_free (ce_s, heap, rhsc);
3671 VEC_free (ce_s, heap, lhsc);
3675 /* Find the first varinfo in the same variable as START that overlaps with
3677 Effectively, walk the chain of fields for the variable START to find the
3678 first field that overlaps with OFFSET.
3679 Return NULL if we can't find one. */
3682 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3684 varinfo_t curr = start;
3687 /* We may not find a variable in the field list with the actual
3688 offset when when we have glommed a structure to a variable.
3689 In that case, however, offset should still be within the size
3691 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3699 /* Insert the varinfo FIELD into the field list for BASE, at the front
3703 insert_into_field_list (varinfo_t base, varinfo_t field)
3705 varinfo_t prev = base;
3706 varinfo_t curr = base->next;
3712 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3716 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
3718 varinfo_t prev = base;
3719 varinfo_t curr = base->next;
3730 if (field->offset <= curr->offset)
3735 field->next = prev->next;
3740 /* qsort comparison function for two fieldoff's PA and PB */
3743 fieldoff_compare (const void *pa, const void *pb)
3745 const fieldoff_s *foa = (const fieldoff_s *)pa;
3746 const fieldoff_s *fob = (const fieldoff_s *)pb;
3747 HOST_WIDE_INT foasize, fobsize;
3749 if (foa->offset != fob->offset)
3750 return foa->offset - fob->offset;
3752 foasize = TREE_INT_CST_LOW (foa->size);
3753 fobsize = TREE_INT_CST_LOW (fob->size);
3754 return foasize - fobsize;
3757 /* Sort a fieldstack according to the field offset and sizes. */
3759 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3761 qsort (VEC_address (fieldoff_s, fieldstack),
3762 VEC_length (fieldoff_s, fieldstack),
3763 sizeof (fieldoff_s),
3767 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3768 of TYPE onto fieldstack, recording their offsets along the way.
3769 OFFSET is used to keep track of the offset in this entire structure, rather
3770 than just the immediately containing structure. Returns the number
3772 HAS_UNION is set to true if we find a union type as a field of
3776 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
3777 HOST_WIDE_INT offset, bool *has_union)
3782 if (TREE_CODE (type) == COMPLEX_TYPE)
3784 fieldoff_s *real_part, *img_part;
3785 real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3786 real_part->type = TREE_TYPE (type);
3787 real_part->size = TYPE_SIZE (TREE_TYPE (type));
3788 real_part->offset = offset;
3789 real_part->decl = NULL_TREE;
3791 img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3792 img_part->type = TREE_TYPE (type);
3793 img_part->size = TYPE_SIZE (TREE_TYPE (type));
3794 img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
3795 img_part->decl = NULL_TREE;
3800 if (TREE_CODE (type) == ARRAY_TYPE)
3802 tree sz = TYPE_SIZE (type);
3803 tree elsz = TYPE_SIZE (TREE_TYPE (type));
3808 || ! host_integerp (sz, 1)
3809 || TREE_INT_CST_LOW (sz) == 0
3811 || ! host_integerp (elsz, 1)
3812 || TREE_INT_CST_LOW (elsz) == 0)
3815 nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
3816 if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
3819 for (i = 0; i < nr; ++i)
3825 && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
3826 || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
3829 if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
3831 else if (!(pushed = push_fields_onto_fieldstack
3832 (TREE_TYPE (type), fieldstack,
3833 offset + i * TREE_INT_CST_LOW (elsz), has_union)))
3834 /* Empty structures may have actual size, like in C++. So
3835 see if we didn't push any subfields and the size is
3836 nonzero, push the field onto the stack */
3843 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3844 pair->type = TREE_TYPE (type);
3846 pair->decl = NULL_TREE;
3847 pair->offset = offset + i * TREE_INT_CST_LOW (elsz);
3857 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
3858 if (TREE_CODE (field) == FIELD_DECL)
3864 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3865 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3868 if (!var_can_have_subvars (field))
3870 else if (!(pushed = push_fields_onto_fieldstack
3871 (TREE_TYPE (field), fieldstack,
3872 offset + bitpos_of_field (field), has_union))
3873 && DECL_SIZE (field)
3874 && !integer_zerop (DECL_SIZE (field)))
3875 /* Empty structures may have actual size, like in C++. So
3876 see if we didn't push any subfields and the size is
3877 nonzero, push the field onto the stack */
3884 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3885 pair->type = TREE_TYPE (field);
3886 pair->size = DECL_SIZE (field);
3888 pair->offset = offset + bitpos_of_field (field);
3898 /* Create a constraint from ESCAPED_VARS variable to VI. */
3900 make_constraint_from_escaped (varinfo_t vi)
3902 struct constraint_expr lhs, rhs;
3908 rhs.var = escaped_vars_id;
3911 process_constraint (new_constraint (lhs, rhs));
3914 /* Create a constraint to the ESCAPED_VARS variable from constraint
3918 make_constraint_to_escaped (struct constraint_expr rhs)
3920 struct constraint_expr lhs;
3922 lhs.var = escaped_vars_id;
3926 process_constraint (new_constraint (lhs, rhs));
3929 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3930 if it is a varargs function. */
3933 count_num_arguments (tree decl, bool *is_varargs)
3938 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
3942 if (TREE_VALUE (t) == void_type_node)
3952 /* Creation function node for DECL, using NAME, and return the index
3953 of the variable we've created for the function. */
3956 create_function_info_for (tree decl, const char *name)
3958 unsigned int index = VEC_length (varinfo_t, varmap);
3962 bool is_varargs = false;
3964 /* Create the variable info. */
3966 vi = new_var_info (decl, index, name, index);
3971 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3972 insert_id_for_tree (vi->decl, index);
3973 VEC_safe_push (varinfo_t, heap, varmap, vi);
3977 /* If it's varargs, we don't know how many arguments it has, so we
3984 vi->is_unknown_size_var = true;
3989 arg = DECL_ARGUMENTS (decl);
3991 /* Set up variables for each argument. */
3992 for (i = 1; i < vi->fullsize; i++)
3995 const char *newname;
3997 unsigned int newindex;
3998 tree argdecl = decl;
4003 newindex = VEC_length (varinfo_t, varmap);
4004 asprintf (&tempname, "%s.arg%d", name, i-1);
4005 newname = ggc_strdup (tempname);
4008 argvi = new_var_info (argdecl, newindex,newname, newindex);
4009 argvi->decl = argdecl;
4010 VEC_safe_push (varinfo_t, heap, varmap, argvi);
4013 argvi->fullsize = vi->fullsize;
4014 argvi->has_union = false;
4015 insert_into_field_list_sorted (vi, argvi);
4016 stats.total_vars ++;
4019 insert_id_for_tree (arg, newindex);
4020 arg = TREE_CHAIN (arg);
4024 /* Create a variable for the return var. */
4025 if (DECL_RESULT (decl) != NULL
4026 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
4029 const char *newname;
4031 unsigned int newindex;
4032 tree resultdecl = decl;
4036 if (DECL_RESULT (decl))
4037 resultdecl = DECL_RESULT (decl);
4039 newindex = VEC_length (varinfo_t, varmap);
4040 asprintf (&tempname, "%s.result", name);
4041 newname = ggc_strdup (tempname);
4044 resultvi = new_var_info (resultdecl, newindex, newname, newindex);
4045 resultvi->decl = resultdecl;
4046 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
4047 resultvi->offset = i;
4049 resultvi->fullsize = vi->fullsize;
4050 resultvi->has_union = false;
4051 insert_into_field_list_sorted (vi, resultvi);
4052 stats.total_vars ++;
4053 if (DECL_RESULT (decl))
4054 insert_id_for_tree (DECL_RESULT (decl), newindex);
4060 /* Return true if FIELDSTACK contains fields that overlap.
4061 FIELDSTACK is assumed to be sorted by offset. */
4064 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
4066 fieldoff_s *fo = NULL;
4068 HOST_WIDE_INT lastoffset = -1;
4070 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4072 if (fo->offset == lastoffset)
4074 lastoffset = fo->offset;
4079 /* This function is called through walk_tree to walk global
4080 initializers looking for constraints we need to add to the
4084 find_global_initializers (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
4087 varinfo_t vi = (varinfo_t)viv;
4090 switch (TREE_CODE (t))
4092 /* Dereferences and addressofs are the only important things
4093 here, and i don't even remember if dereferences are legal
4094 here in initializers. */
4098 struct constraint_expr *c;
4101 VEC(ce_s, heap) *rhsc = NULL;
4102 get_constraint_for (t, &rhsc);
4103 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4105 struct constraint_expr lhs;
4110 process_constraint (new_constraint (lhs, *c));
4113 VEC_free (ce_s, heap, rhsc);
4117 /* We might not have walked this because we skip
4118 DECL_EXTERNALs during the initial scan. */
4119 add_referenced_var (t);
4127 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4128 This will also create any varinfo structures necessary for fields
4132 create_variable_info_for (tree decl, const char *name)
4134 unsigned int index = VEC_length (varinfo_t, varmap);
4136 tree decltype = TREE_TYPE (decl);
4137 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
4138 bool notokay = false;
4140 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
4141 VEC (fieldoff_s,heap) *fieldstack = NULL;
4143 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4144 return create_function_info_for (decl, name);
4146 hasunion = TREE_CODE (decltype) == UNION_TYPE
4147 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
4148 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
4150 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
4153 VEC_free (fieldoff_s, heap, fieldstack);
4159 /* If the variable doesn't have subvars, we may end up needing to
4160 sort the field list and create fake variables for all the
4162 vi = new_var_info (decl, index, name, index);
4165 vi->has_union = hasunion;
4167 || TREE_CODE (declsize) != INTEGER_CST
4168 || TREE_CODE (decltype) == UNION_TYPE
4169 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
4171 vi->is_unknown_size_var = true;
4177 vi->fullsize = TREE_INT_CST_LOW (declsize);
4178 vi->size = vi->fullsize;
4181 insert_id_for_tree (vi->decl, index);
4182 VEC_safe_push (varinfo_t, heap, varmap, vi);
4183 if (is_global && (!flag_whole_program || !in_ipa_mode))
4185 make_constraint_from_escaped (vi);
4187 /* If the variable can't be aliased, there is no point in
4188 putting it in the set of nonlocal vars. */
4189 if (may_be_aliased (vi->decl))
4191 struct constraint_expr rhs;
4193 rhs.type = ADDRESSOF;
4195 make_constraint_to_escaped (rhs);
4198 if (TREE_CODE (decl) != FUNCTION_DECL && DECL_INITIAL (decl))
4200 walk_tree_without_duplicates (&DECL_INITIAL (decl),
4201 find_global_initializers,
4207 if (use_field_sensitive
4209 && !vi->is_unknown_size_var
4210 && var_can_have_subvars (decl)
4211 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4213 unsigned int newindex = VEC_length (varinfo_t, varmap);
4214 fieldoff_s *fo = NULL;
4217 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4220 || TREE_CODE (fo->size) != INTEGER_CST
4228 /* We can't sort them if we have a field with a variable sized type,
4229 which will make notokay = true. In that case, we are going to return
4230 without creating varinfos for the fields anyway, so sorting them is a
4234 sort_fieldstack (fieldstack);
4235 /* Due to some C++ FE issues, like PR 22488, we might end up
4236 what appear to be overlapping fields even though they,
4237 in reality, do not overlap. Until the C++ FE is fixed,
4238 we will simply disable field-sensitivity for these cases. */
4239 notokay = check_for_overlaps (fieldstack);
4243 if (VEC_length (fieldoff_s, fieldstack) != 0)
4244 fo = VEC_index (fieldoff_s, fieldstack, 0);
4246 if (fo == NULL || notokay)
4248 vi->is_unknown_size_var = 1;
4251 VEC_free (fieldoff_s, heap, fieldstack);
4255 vi->size = TREE_INT_CST_LOW (fo->size);
4256 vi->offset = fo->offset;
4257 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4258 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4262 const char *newname = "NULL";
4265 newindex = VEC_length (varinfo_t, varmap);
4269 asprintf (&tempname, "%s.%s",
4270 vi->name, alias_get_name (fo->decl));
4272 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC,
4273 vi->name, fo->offset);
4274 newname = ggc_strdup (tempname);
4277 newvi = new_var_info (decl, newindex, newname, newindex);
4278 newvi->offset = fo->offset;
4279 newvi->size = TREE_INT_CST_LOW (fo->size);
4280 newvi->fullsize = vi->fullsize;
4281 insert_into_field_list (vi, newvi);
4282 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4283 if (is_global && (!flag_whole_program || !in_ipa_mode))
4285 /* If the variable can't be aliased, there is no point in
4286 putting it in the set of nonlocal vars. */
4287 if (may_be_aliased (vi->decl))
4289 struct constraint_expr rhs;
4292 rhs.type = ADDRESSOF;
4294 make_constraint_to_escaped (rhs);
4296 make_constraint_from_escaped (newvi);
4301 VEC_free (fieldoff_s, heap, fieldstack);
4306 /* Print out the points-to solution for VAR to FILE. */
4309 dump_solution_for_var (FILE *file, unsigned int var)
4311 varinfo_t vi = get_varinfo (var);
4315 fprintf (file, "%s = { ", vi->name);
4316 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
4318 fprintf (file, "%s ", get_varinfo (i)->name);
4320 fprintf (file, "}\n");
4323 /* Print the points-to solution for VAR to stdout. */
4326 debug_solution_for_var (unsigned int var)
4328 dump_solution_for_var (stdout, var);
4331 /* Create varinfo structures for all of the variables in the
4332 function for intraprocedural mode. */
4335 intra_create_variable_infos (void)
4338 struct constraint_expr lhs, rhs;
4340 varinfo_t nonlocal_vi;
4341 /* For each incoming pointer argument arg, ARG = ESCAPED_VARS or a
4342 dummy variable if flag_argument_noalias > 2. */
4343 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4346 unsigned int arg_id;
4348 if (!could_have_pointers (t))
4351 arg_id = get_id_for_tree (t);
4353 /* With flag_argument_noalias greater than two means that the incoming
4354 argument cannot alias anything except for itself so create a HEAP
4356 if (POINTER_TYPE_P (TREE_TYPE (t))
4357 && flag_argument_noalias > 2)
4360 tree heapvar = heapvar_lookup (t);
4365 lhs.var = get_id_for_tree (t);
4367 if (heapvar == NULL_TREE)
4369 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4371 DECL_EXTERNAL (heapvar) = 1;
4372 if (referenced_vars)
4373 add_referenced_var (heapvar);
4374 heapvar_insert (t, heapvar);
4376 id = get_id_for_tree (heapvar);
4377 vi = get_varinfo (id);
4378 vi->is_artificial_var = 1;
4379 vi->is_heap_var = 1;
4381 rhs.type = ADDRESSOF;
4383 for (p = get_varinfo (lhs.var); p; p = p->next)
4385 struct constraint_expr temp = lhs;
4387 process_constraint (new_constraint (temp, rhs));
4392 for (p = get_varinfo (arg_id); p; p = p->next)
4393 make_constraint_from_escaped (p);
4396 nonlocal = create_tmp_var_raw (void_type_node, "NONLOCAL_ALL");
4398 DECL_EXTERNAL (nonlocal) = 1;
4400 /* Create variable info for the nonlocal var if it does not
4402 nonlocal_vars_id = create_variable_info_for (nonlocal,
4403 get_name (nonlocal));
4404 nonlocal_vi = get_varinfo (nonlocal_vars_id);
4405 nonlocal_vi->is_artificial_var = 1;
4406 nonlocal_vi->is_heap_var = 1;
4407 nonlocal_vi->is_unknown_size_var = 1;
4408 nonlocal_vi->directly_dereferenced = true;
4410 rhs.var = nonlocal_vars_id;
4411 rhs.type = ADDRESSOF;
4414 lhs.var = escaped_vars_id;
4418 process_constraint (new_constraint (lhs, rhs));
4421 /* Set bits in INTO corresponding to the variable uids in solution set
4422 FROM, which came from variable PTR.
4423 For variables that are actually dereferenced, we also use type
4424 based alias analysis to prune the points-to sets. */
4427 set_uids_in_ptset (tree ptr, bitmap into, bitmap from)
4432 unsigned HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr));
4434 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4436 varinfo_t vi = get_varinfo (i);
4437 unsigned HOST_WIDE_INT var_alias_set;
4439 /* The only artificial variables that are allowed in a may-alias
4440 set are heap variables. */
4441 if (vi->is_artificial_var && !vi->is_heap_var)
4444 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
4446 /* Variables containing unions may need to be converted to
4447 their SFT's, because SFT's can have unions and we cannot. */
4448 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
4449 bitmap_set_bit (into, DECL_UID (sv->var));
4451 else if (TREE_CODE (vi->decl) == VAR_DECL
4452 || TREE_CODE (vi->decl) == PARM_DECL)
4454 if (var_can_have_subvars (vi->decl)
4455 && get_subvars_for_var (vi->decl))
4457 /* If VI->DECL is an aggregate for which we created
4458 SFTs, add the SFT corresponding to VI->OFFSET. */
4459 tree sft = get_subvar_at (vi->decl, vi->offset);
4462 var_alias_set = get_alias_set (sft);
4463 if (!vi->directly_dereferenced
4464 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
4465 bitmap_set_bit (into, DECL_UID (sft));
4470 /* Otherwise, just add VI->DECL to the alias set.
4471 Don't type prune artificial vars. */
4472 if (vi->is_artificial_var)
4473 bitmap_set_bit (into, DECL_UID (vi->decl));
4476 var_alias_set = get_alias_set (vi->decl);
4477 if (!vi->directly_dereferenced
4478 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
4479 bitmap_set_bit (into, DECL_UID (vi->decl));
4487 static bool have_alias_info = false;
4489 /* Given a pointer variable P, fill in its points-to set, or return
4490 false if we can't. */
4493 find_what_p_points_to (tree p)
4495 unsigned int id = 0;
4498 if (!have_alias_info)
4501 /* For parameters, get at the points-to set for the actual parm
4503 if (TREE_CODE (p) == SSA_NAME
4504 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4505 && default_def (SSA_NAME_VAR (p)) == p)
4506 lookup_p = SSA_NAME_VAR (p);
4508 if (lookup_id_for_tree (lookup_p, &id))
4510 varinfo_t vi = get_varinfo (id);
4512 if (vi->is_artificial_var)
4515 /* See if this is a field or a structure. */
4516 if (vi->size != vi->fullsize)
4518 /* Nothing currently asks about structure fields directly,
4519 but when they do, we need code here to hand back the
4521 if (!var_can_have_subvars (vi->decl)
4522 || get_subvars_for_var (vi->decl) == NULL)
4527 struct ptr_info_def *pi = get_ptr_info (p);
4531 /* This variable may have been collapsed, let's get the real
4533 vi = get_varinfo (vi->node);
4535 /* Translate artificial variables into SSA_NAME_PTR_INFO
4537 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4539 varinfo_t vi = get_varinfo (i);
4541 if (vi->is_artificial_var)
4543 /* FIXME. READONLY should be handled better so that
4544 flow insensitive aliasing can disregard writable
4546 if (vi->id == nothing_id)
4548 else if (vi->id == anything_id)
4549 pi->pt_anything = 1;
4550 else if (vi->id == readonly_id)
4551 pi->pt_anything = 1;
4552 else if (vi->id == integer_id)
4553 pi->pt_anything = 1;
4554 else if (vi->is_heap_var)
4555 pi->pt_global_mem = 1;
4559 if (pi->pt_anything)
4563 pi->pt_vars = BITMAP_GGC_ALLOC ();
4565 set_uids_in_ptset (vi->decl, pi->pt_vars, vi->solution);
4567 if (bitmap_empty_p (pi->pt_vars))
4579 /* Dump points-to information to OUTFILE. */
4582 dump_sa_points_to_info (FILE *outfile)
4586 fprintf (outfile, "\nPoints-to sets\n\n");
4588 if (dump_flags & TDF_STATS)
4590 fprintf (outfile, "Stats:\n");
4591 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4592 fprintf (outfile, "Statically unified vars: %d\n",
4593 stats.unified_vars_static);
4594 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
4595 fprintf (outfile, "Dynamically unified vars: %d\n",
4596 stats.unified_vars_dynamic);
4597 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4598 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4601 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4602 dump_solution_for_var (outfile, i);
4606 /* Debug points-to information to stderr. */
4609 debug_sa_points_to_info (void)
4611 dump_sa_points_to_info (stderr);
4615 /* Initialize the always-existing constraint variables for NULL
4616 ANYTHING, READONLY, and INTEGER */
4619 init_base_vars (void)
4621 struct constraint_expr lhs, rhs;
4623 /* Create the NULL variable, used to represent that a variable points
4625 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4626 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
4627 insert_id_for_tree (nothing_tree, 0);
4628 var_nothing->is_artificial_var = 1;
4629 var_nothing->offset = 0;
4630 var_nothing->size = ~0;
4631 var_nothing->fullsize = ~0;
4632 var_nothing->is_special_var = 1;
4634 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
4636 /* Create the ANYTHING variable, used to represent that a variable
4637 points to some unknown piece of memory. */
4638 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4639 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
4640 insert_id_for_tree (anything_tree, 1);
4641 var_anything->is_artificial_var = 1;
4642 var_anything->size = ~0;
4643 var_anything->offset = 0;
4644 var_anything->next = NULL;
4645 var_anything->fullsize = ~0;
4646 var_anything->is_special_var = 1;
4649 /* Anything points to anything. This makes deref constraints just
4650 work in the presence of linked list and other p = *p type loops,
4651 by saying that *ANYTHING = ANYTHING. */
4652 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
4654 lhs.var = anything_id;
4656 rhs.type = ADDRESSOF;
4657 rhs.var = anything_id;
4659 var_anything->address_taken = true;
4661 /* This specifically does not use process_constraint because
4662 process_constraint ignores all anything = anything constraints, since all
4663 but this one are redundant. */
4664 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
4666 /* Create the READONLY variable, used to represent that a variable
4667 points to readonly memory. */
4668 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4669 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
4670 var_readonly->is_artificial_var = 1;
4671 var_readonly->offset = 0;
4672 var_readonly->size = ~0;
4673 var_readonly->fullsize = ~0;
4674 var_readonly->next = NULL;
4675 var_readonly->is_special_var = 1;
4676 insert_id_for_tree (readonly_tree, 2);
4678 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4680 /* readonly memory points to anything, in order to make deref
4681 easier. In reality, it points to anything the particular
4682 readonly variable can point to, but we don't track this
4685 lhs.var = readonly_id;
4687 rhs.type = ADDRESSOF;
4688 rhs.var = anything_id;
4691 process_constraint (new_constraint (lhs, rhs));
4693 /* Create the INTEGER variable, used to represent that a variable points
4695 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4696 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
4697 insert_id_for_tree (integer_tree, 3);
4698 var_integer->is_artificial_var = 1;
4699 var_integer->size = ~0;
4700 var_integer->fullsize = ~0;
4701 var_integer->offset = 0;
4702 var_integer->next = NULL;
4703 var_integer->is_special_var = 1;
4705 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
4707 /* INTEGER = ANYTHING, because we don't know where a dereference of
4708 a random integer will point to. */
4710 lhs.var = integer_id;
4712 rhs.type = ADDRESSOF;
4713 rhs.var = anything_id;
4715 process_constraint (new_constraint (lhs, rhs));
4717 /* Create the ESCAPED_VARS variable used to represent variables that
4718 escape this function. */
4719 escaped_vars_tree = create_tmp_var_raw (void_type_node, "ESCAPED_VARS");
4720 var_escaped_vars = new_var_info (escaped_vars_tree, 4, "ESCAPED_VARS", 4);
4721 insert_id_for_tree (escaped_vars_tree, 4);
4722 var_escaped_vars->is_artificial_var = 1;
4723 var_escaped_vars->size = ~0;
4724 var_escaped_vars->fullsize = ~0;
4725 var_escaped_vars->offset = 0;
4726 var_escaped_vars->next = NULL;
4727 escaped_vars_id = 4;
4728 VEC_safe_push (varinfo_t, heap, varmap, var_escaped_vars);
4730 /* ESCAPED_VARS = *ESCAPED_VARS */
4732 lhs.var = escaped_vars_id;
4735 rhs.var = escaped_vars_id;
4737 process_constraint (new_constraint (lhs, rhs));
4741 /* Initialize things necessary to perform PTA */
4744 init_alias_vars (void)
4746 bitmap_obstack_initialize (&ptabitmap_obstack);
4747 bitmap_obstack_initialize (&predbitmap_obstack);
4749 constraint_pool = create_alloc_pool ("Constraint pool",
4750 sizeof (struct constraint), 30);
4751 variable_info_pool = create_alloc_pool ("Variable info pool",
4752 sizeof (struct variable_info), 30);
4753 constraint_edge_pool = create_alloc_pool ("Constraint edges",
4754 sizeof (struct constraint_edge), 30);
4756 constraints = VEC_alloc (constraint_t, heap, 8);
4757 varmap = VEC_alloc (varinfo_t, heap, 8);
4758 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
4759 memset (&stats, 0, sizeof (stats));
4764 /* Given a statement STMT, generate necessary constraints to
4765 escaped_vars for the escaping variables. */
4768 find_escape_constraints (tree stmt)
4770 enum escape_type stmt_escape_type = is_escape_site (stmt);
4772 VEC(ce_s, heap) *rhsc = NULL;
4773 struct constraint_expr *c;
4776 if (stmt_escape_type == NO_ESCAPE)
4779 if (TREE_CODE (stmt) == RETURN_EXPR)
4781 /* Returns are either bare, with an embedded MODIFY_EXPR, or
4782 just a plain old expression. */
4783 if (!TREE_OPERAND (stmt, 0))
4785 if (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
4786 rhs = TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
4788 rhs = TREE_OPERAND (stmt, 0);
4790 get_constraint_for (rhs, &rhsc);
4791 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4792 make_constraint_to_escaped (*c);
4793 VEC_free (ce_s, heap, rhsc);
4796 else if (TREE_CODE (stmt) == ASM_EXPR)
4798 /* Whatever the inputs of the ASM are, escape. */
4801 for (arg = ASM_INPUTS (stmt); arg; arg = TREE_CHAIN (arg))
4804 get_constraint_for (TREE_VALUE (arg), &rhsc);
4805 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4806 make_constraint_to_escaped (*c);
4807 VEC_free (ce_s, heap, rhsc);
4811 else if (TREE_CODE (stmt) == CALL_EXPR
4812 || (TREE_CODE (stmt) == MODIFY_EXPR
4813 && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR))
4815 /* Calls cause all of the arguments passed in to escape. */
4818 if (TREE_CODE (stmt) == MODIFY_EXPR)
4819 stmt = TREE_OPERAND (stmt, 1);
4820 for (arg = TREE_OPERAND (stmt, 1); arg; arg = TREE_CHAIN (arg))
4822 if (POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arg))))
4825 get_constraint_for (TREE_VALUE (arg), &rhsc);
4826 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4827 make_constraint_to_escaped (*c);
4828 VEC_free (ce_s, heap, rhsc);
4835 gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
4838 gcc_assert (stmt_escape_type == ESCAPE_BAD_CAST
4839 || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL
4840 || stmt_escape_type == ESCAPE_UNKNOWN);
4841 rhs = TREE_OPERAND (stmt, 1);
4843 /* Look through casts for the real escaping variable.
4844 Constants don't really escape, so ignore them.
4845 Otherwise, whatever escapes must be on our RHS. */
4846 if (TREE_CODE (rhs) == NOP_EXPR
4847 || TREE_CODE (rhs) == CONVERT_EXPR
4848 || TREE_CODE (rhs) == NON_LVALUE_EXPR)
4850 get_constraint_for (TREE_OPERAND (rhs, 0), &rhsc);
4852 else if (CONSTANT_CLASS_P (rhs))
4856 get_constraint_for (rhs, &rhsc);
4858 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4859 make_constraint_to_escaped (*c);
4860 VEC_free (ce_s, heap, rhsc);
4863 /* Expand the solutions that have nonlocal_id in them to include one
4864 variable for each type that is pointed to by nonlocal and
4868 expand_nonlocal_solutions (void)
4872 bitmap new_nonlocal_solution = BITMAP_ALLOC (&ptabitmap_obstack);
4874 /* We could do this faster by only checking non-collapsed nodes,
4875 unless the node was collapsed to one we would normally ignore in the
4876 rest of the loop. Logic already seems complicated enough, and
4877 it wasn't a measurable speedup on any testcases i had. */
4878 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4880 /* Where the solution for our variable is, since it may have
4881 been collapsed to another varinfo. */
4884 if (v->is_special_var
4885 || v->id == nonlocal_vars_id
4886 || v->id == escaped_vars_id
4887 || !POINTER_TYPE_P (TREE_TYPE (v->decl)))
4890 if (v->node != v->id)
4891 solv = get_varinfo (v->node);
4892 if (bitmap_bit_p (solv->solution, nonlocal_vars_id))
4894 unsigned int new_nonlocal_id;
4895 tree pttype = TREE_TYPE (TREE_TYPE (v->decl));
4897 new_nonlocal_id = get_nonlocal_id_for_type (pttype);
4898 bitmap_set_bit (new_nonlocal_solution, new_nonlocal_id);
4902 if (!bitmap_empty_p (new_nonlocal_solution))
4905 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4907 if (v->node != v->id)
4909 if (bitmap_bit_p (v->solution, nonlocal_vars_id))
4911 bitmap_clear_bit (v->solution, nonlocal_vars_id);
4912 bitmap_ior_into (v->solution, new_nonlocal_solution);
4918 /* Create points-to sets for the current function. See the comments
4919 at the start of the file for an algorithmic overview. */
4922 compute_points_to_sets (struct alias_info *ai)
4926 timevar_push (TV_TREE_PTA);
4930 intra_create_variable_infos ();
4932 /* Now walk all statements and derive aliases. */
4935 block_stmt_iterator bsi;
4938 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4940 if (is_gimple_reg (PHI_RESULT (phi)))
4942 find_func_aliases (phi);
4943 /* Update various related attributes like escaped
4944 addresses, pointer dereferences for loads and stores.
4945 This is used when creating name tags and alias
4947 update_alias_info (phi, ai);
4951 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4953 tree stmt = bsi_stmt (bsi);
4955 find_func_aliases (stmt);
4956 find_escape_constraints (stmt);
4957 /* Update various related attributes like escaped
4958 addresses, pointer dereferences for loads and stores.
4959 This is used when creating name tags and alias
4961 update_alias_info (stmt, ai);
4965 build_constraint_graph ();
4969 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4970 dump_constraints (dump_file);
4975 "\nCollapsing static cycles and doing variable "
4978 find_and_collapse_graph_cycles (graph, false);
4979 perform_var_substitution (graph);
4982 fprintf (dump_file, "\nSolving graph:\n");
4984 solve_graph (graph);
4986 expand_nonlocal_solutions ();
4989 dump_sa_points_to_info (dump_file);
4991 have_alias_info = true;
4993 timevar_pop (TV_TREE_PTA);
4997 /* Delete created points-to sets. */
5000 delete_points_to_sets (void)
5005 htab_delete (id_for_tree);
5006 bitmap_obstack_release (&ptabitmap_obstack);
5007 bitmap_obstack_release (&predbitmap_obstack);
5008 VEC_free (constraint_t, heap, constraints);
5010 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
5012 /* Nonlocal vars may add more varinfos. */
5013 if (i >= graph_size)
5016 VEC_free (constraint_edge_t, heap, graph->succs[i]);
5017 VEC_free (constraint_edge_t, heap, graph->preds[i]);
5018 VEC_free (constraint_t, heap, v->complex);
5020 free (graph->zero_weight_preds);
5021 free (graph->zero_weight_succs);
5022 free (graph->succs);
5023 free (graph->preds);
5026 VEC_free (varinfo_t, heap, varmap);
5027 free_alloc_pool (variable_info_pool);
5028 free_alloc_pool (constraint_pool);
5029 free_alloc_pool (constraint_edge_pool);
5031 have_alias_info = false;
5034 /* Return true if we should execute IPA PTA. */
5038 return (flag_unit_at_a_time != 0
5040 /* Don't bother doing anything if the program has errors. */
5041 && !(errorcount || sorrycount));
5044 /* Execute the driver for IPA PTA. */
5046 ipa_pta_execute (void)
5048 struct cgraph_node *node;
5050 init_alias_heapvars ();
5053 for (node = cgraph_nodes; node; node = node->next)
5055 if (!node->analyzed || cgraph_is_master_clone (node))
5059 varid = create_function_info_for (node->decl,
5060 cgraph_node_name (node));
5061 if (node->local.externally_visible)
5063 varinfo_t fi = get_varinfo (varid);
5064 for (; fi; fi = fi->next)
5065 make_constraint_from_escaped (fi);
5069 for (node = cgraph_nodes; node; node = node->next)
5071 if (node->analyzed && cgraph_is_master_clone (node))
5073 struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
5075 tree old_func_decl = current_function_decl;
5078 "Generating constraints for %s\n",
5079 cgraph_node_name (node));
5081 current_function_decl = node->decl;
5083 FOR_EACH_BB_FN (bb, cfun)
5085 block_stmt_iterator bsi;
5088 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
5090 if (is_gimple_reg (PHI_RESULT (phi)))
5092 find_func_aliases (phi);
5096 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
5098 tree stmt = bsi_stmt (bsi);
5099 find_func_aliases (stmt);
5102 current_function_decl = old_func_decl;
5107 /* Make point to anything. */
5111 build_constraint_graph ();
5115 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5116 dump_constraints (dump_file);
5121 "\nCollapsing static cycles and doing variable "
5124 find_and_collapse_graph_cycles (graph, false);
5125 perform_var_substitution (graph);
5128 fprintf (dump_file, "\nSolving graph:\n");
5130 solve_graph (graph);
5132 expand_nonlocal_solutions ();
5135 dump_sa_points_to_info (dump_file);
5137 delete_alias_heapvars ();
5138 delete_points_to_sets ();
5142 struct tree_opt_pass pass_ipa_pta =
5145 gate_ipa_pta, /* gate */
5146 ipa_pta_execute, /* execute */
5149 0, /* static_pass_number */
5150 TV_IPA_PTA, /* tv_id */
5151 0, /* properties_required */
5152 0, /* properties_provided */
5153 0, /* properties_destroyed */
5154 0, /* todo_flags_start */
5155 0, /* todo_flags_finish */
5159 /* Initialize the heapvar for statement mapping. */
5161 init_alias_heapvars (void)
5163 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5165 nonlocal_for_type = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5167 nonlocal_all = NULL_TREE;
5171 delete_alias_heapvars (void)
5173 nonlocal_all = NULL_TREE;
5174 htab_delete (heapvar_for_stmt);
5175 htab_delete (nonlocal_for_type);
5179 #include "gt-tree-ssa-structalias.h"