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;
167 /* One variable to represent all non-local accesses. */
170 static bool use_field_sensitive = true;
171 static int in_ipa_mode = 0;
172 static bitmap_obstack predbitmap_obstack;
173 static bitmap_obstack ptabitmap_obstack;
174 static bitmap_obstack iteration_obstack;
176 static unsigned int create_variable_info_for (tree, const char *);
177 static void build_constraint_graph (void);
179 DEF_VEC_P(constraint_t);
180 DEF_VEC_ALLOC_P(constraint_t,heap);
182 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
184 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
186 static struct constraint_stats
188 unsigned int total_vars;
189 unsigned int collapsed_vars;
190 unsigned int unified_vars_static;
191 unsigned int unified_vars_dynamic;
192 unsigned int iterations;
193 unsigned int num_edges;
198 /* ID of this variable */
201 /* Name of this variable */
204 /* Tree that this variable is associated with. */
207 /* Offset of this variable, in bits, from the base variable */
208 unsigned HOST_WIDE_INT offset;
210 /* Size of the variable, in bits. */
211 unsigned HOST_WIDE_INT size;
213 /* Full size of the base variable, in bits. */
214 unsigned HOST_WIDE_INT fullsize;
216 /* A link to the variable for the next field in this structure. */
217 struct variable_info *next;
219 /* Node in the graph that represents the constraints and points-to
220 solution for the variable. */
223 /* True if the address of this variable is taken. Needed for
224 variable substitution. */
225 unsigned int address_taken:1;
227 /* True if this variable is the target of a dereference. Needed for
228 variable substitution. */
229 unsigned int indirect_target:1;
231 /* True if the variable is directly the target of a dereference.
232 This is used to track which variables are *actually* dereferenced
233 so we can prune their points to listed. This is equivalent to the
234 indirect_target flag when no merging of variables happens. */
235 unsigned int directly_dereferenced:1;
237 /* True if this is a variable created by the constraint analysis, such as
238 heap variables and constraints we had to break up. */
239 unsigned int is_artificial_var:1;
241 /* True if this is a special variable whose solution set should not be
243 unsigned int is_special_var:1;
245 /* True for variables whose size is not known or variable. */
246 unsigned int is_unknown_size_var:1;
248 /* True for variables that have unions somewhere in them. */
249 unsigned int has_union:1;
251 /* True if this is a heap variable. */
252 unsigned int is_heap_var:1;
254 /* Points-to set for this variable. */
257 /* Variable ids represented by this node. */
260 /* Vector of complex constraints for this node. Complex
261 constraints are those involving dereferences. */
262 VEC(constraint_t,heap) *complex;
264 /* Variable id this was collapsed to due to type unsafety.
265 This should be unused completely after build_constraint_graph, or
266 something is broken. */
267 struct variable_info *collapsed_to;
269 typedef struct variable_info *varinfo_t;
271 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
273 /* Pool of variable info structures. */
274 static alloc_pool variable_info_pool;
276 DEF_VEC_P(varinfo_t);
278 DEF_VEC_ALLOC_P(varinfo_t, heap);
280 /* Table of variable info structures for constraint variables. Indexed directly
281 by variable info id. */
282 static VEC(varinfo_t,heap) *varmap;
284 /* Return the varmap element N */
286 static inline varinfo_t
287 get_varinfo (unsigned int n)
289 return VEC_index(varinfo_t, varmap, n);
292 /* Return the varmap element N, following the collapsed_to link. */
294 static inline varinfo_t
295 get_varinfo_fc (unsigned int n)
297 varinfo_t v = VEC_index(varinfo_t, varmap, n);
300 return v->collapsed_to;
304 /* Variable that represents the unknown pointer. */
305 static varinfo_t var_anything;
306 static tree anything_tree;
307 static unsigned int anything_id;
309 /* Variable that represents the NULL pointer. */
310 static varinfo_t var_nothing;
311 static tree nothing_tree;
312 static unsigned int nothing_id;
314 /* Variable that represents read only memory. */
315 static varinfo_t var_readonly;
316 static tree readonly_tree;
317 static unsigned int readonly_id;
319 /* Variable that represents integers. This is used for when people do things
321 static varinfo_t var_integer;
322 static tree integer_tree;
323 static unsigned int integer_id;
325 /* Variable that represents escaped variables. This is used to give
326 incoming pointer variables a better set than ANYTHING. */
327 static varinfo_t var_escaped_vars;
328 static tree escaped_vars_tree;
329 static unsigned int escaped_vars_id;
331 /* Variable that represents non-local variables before we expand it to
332 one for each type. */
333 static unsigned int nonlocal_vars_id;
335 /* Lookup a heap var for FROM, and return it if we find one. */
338 heapvar_lookup (tree from)
340 struct tree_map *h, in;
343 h = htab_find_with_hash (heapvar_for_stmt, &in, htab_hash_pointer (from));
349 /* Insert a mapping FROM->TO in the heap var for statement
353 heapvar_insert (tree from, tree to)
358 h = ggc_alloc (sizeof (struct tree_map));
359 h->hash = htab_hash_pointer (from);
362 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
363 *(struct tree_map **) loc = h;
366 /* Return a new variable info structure consisting for a variable
367 named NAME, and using constraint graph node NODE. */
370 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
372 varinfo_t ret = pool_alloc (variable_info_pool);
378 ret->address_taken = false;
379 ret->indirect_target = false;
380 ret->directly_dereferenced = false;
381 ret->is_artificial_var = false;
382 ret->is_heap_var = false;
383 ret->is_special_var = false;
384 ret->is_unknown_size_var = false;
385 ret->has_union = false;
386 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
387 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
390 ret->collapsed_to = NULL;
394 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
396 /* An expression that appears in a constraint. */
398 struct constraint_expr
400 /* Constraint type. */
401 constraint_expr_type type;
403 /* Variable we are referring to in the constraint. */
406 /* Offset, in bits, of this constraint from the beginning of
407 variables it ends up referring to.
409 IOW, in a deref constraint, we would deref, get the result set,
410 then add OFFSET to each member. */
411 unsigned HOST_WIDE_INT offset;
414 typedef struct constraint_expr ce_s;
416 DEF_VEC_ALLOC_O(ce_s, heap);
417 static void get_constraint_for (tree, VEC(ce_s, heap) **);
418 static void do_deref (VEC (ce_s, heap) **);
420 /* Our set constraints are made up of two constraint expressions, one
423 As described in the introduction, our set constraints each represent an
424 operation between set valued variables.
428 struct constraint_expr lhs;
429 struct constraint_expr rhs;
432 /* List of constraints that we use to build the constraint graph from. */
434 static VEC(constraint_t,heap) *constraints;
435 static alloc_pool constraint_pool;
437 /* An edge in the weighted constraint graph. The edges are weighted,
438 with a bit set in weights meaning their is an edge with that
440 We don't keep the src in the edge, because we always know what it
443 struct constraint_edge
449 typedef struct constraint_edge *constraint_edge_t;
450 static alloc_pool constraint_edge_pool;
452 /* Return a new constraint edge from SRC to DEST. */
454 static constraint_edge_t
455 new_constraint_edge (unsigned int dest)
457 constraint_edge_t ret = pool_alloc (constraint_edge_pool);
463 DEF_VEC_P(constraint_edge_t);
464 DEF_VEC_ALLOC_P(constraint_edge_t,heap);
467 /* The constraint graph is represented internally in two different
468 ways. The overwhelming majority of edges in the constraint graph
469 are zero weigh edges, and thus, using a vector of contrainst_edge_t
470 is a waste of time and memory, since they have no weights. We
471 simply use a bitmap to store the preds and succs for each node.
472 The weighted edges are stored as a set of adjacency vectors, one
473 per variable. succs[x] is the vector of successors for variable x,
474 and preds[x] is the vector of predecessors for variable x. IOW,
475 all edges are "forward" edges, which is not like our CFG. So
476 remember that preds[x]->src == x, and succs[x]->src == x. */
478 struct constraint_graph
480 bitmap *zero_weight_succs;
481 bitmap *zero_weight_preds;
482 VEC(constraint_edge_t,heap) **succs;
483 VEC(constraint_edge_t,heap) **preds;
486 typedef struct constraint_graph *constraint_graph_t;
488 static constraint_graph_t graph;
489 static int graph_size;
491 /* Create a new constraint consisting of LHS and RHS expressions. */
494 new_constraint (const struct constraint_expr lhs,
495 const struct constraint_expr rhs)
497 constraint_t ret = pool_alloc (constraint_pool);
503 /* Print out constraint C to FILE. */
506 dump_constraint (FILE *file, constraint_t c)
508 if (c->lhs.type == ADDRESSOF)
510 else if (c->lhs.type == DEREF)
512 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
513 if (c->lhs.offset != 0)
514 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
515 fprintf (file, " = ");
516 if (c->rhs.type == ADDRESSOF)
518 else if (c->rhs.type == DEREF)
520 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
521 if (c->rhs.offset != 0)
522 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
523 fprintf (file, "\n");
526 /* Print out constraint C to stderr. */
529 debug_constraint (constraint_t c)
531 dump_constraint (stderr, c);
534 /* Print out all constraints to FILE */
537 dump_constraints (FILE *file)
541 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
542 dump_constraint (file, c);
545 /* Print out all constraints to stderr. */
548 debug_constraints (void)
550 dump_constraints (stderr);
555 The solver is a simple worklist solver, that works on the following
558 sbitmap changed_nodes = all ones;
559 changed_count = number of nodes;
560 For each node that was already collapsed:
563 while (changed_count > 0)
565 compute topological ordering for constraint graph
567 find and collapse cycles in the constraint graph (updating
568 changed if necessary)
570 for each node (n) in the graph in topological order:
573 Process each complex constraint associated with the node,
574 updating changed if necessary.
576 For each outgoing edge from n, propagate the solution from n to
577 the destination of the edge, updating changed as necessary.
581 /* Return true if two constraint expressions A and B are equal. */
584 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
586 return a.type == b.type && a.var == b.var && a.offset == b.offset;
589 /* Return true if constraint expression A is less than constraint expression
590 B. This is just arbitrary, but consistent, in order to give them an
594 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
596 if (a.type == b.type)
599 return a.offset < b.offset;
601 return a.var < b.var;
604 return a.type < b.type;
607 /* Return true if constraint A is less than constraint B. This is just
608 arbitrary, but consistent, in order to give them an ordering. */
611 constraint_less (const constraint_t a, const constraint_t b)
613 if (constraint_expr_less (a->lhs, b->lhs))
615 else if (constraint_expr_less (b->lhs, a->lhs))
618 return constraint_expr_less (a->rhs, b->rhs);
621 /* Return true if two constraints A and B are equal. */
624 constraint_equal (struct constraint a, struct constraint b)
626 return constraint_expr_equal (a.lhs, b.lhs)
627 && constraint_expr_equal (a.rhs, b.rhs);
631 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
634 constraint_vec_find (VEC(constraint_t,heap) *vec,
635 struct constraint lookfor)
643 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
644 if (place >= VEC_length (constraint_t, vec))
646 found = VEC_index (constraint_t, vec, place);
647 if (!constraint_equal (*found, lookfor))
652 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
655 constraint_set_union (VEC(constraint_t,heap) **to,
656 VEC(constraint_t,heap) **from)
661 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
663 if (constraint_vec_find (*to, *c) == NULL)
665 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
667 VEC_safe_insert (constraint_t, heap, *to, place, c);
672 /* Take a solution set SET, add OFFSET to each member of the set, and
673 overwrite SET with the result when done. */
676 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
678 bitmap result = BITMAP_ALLOC (&iteration_obstack);
682 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
684 /* If this is a properly sized variable, only add offset if it's
685 less than end. Otherwise, it is globbed to a single
688 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
690 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
691 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
694 bitmap_set_bit (result, v->id);
696 else if (get_varinfo (i)->is_artificial_var
697 || get_varinfo (i)->has_union
698 || get_varinfo (i)->is_unknown_size_var)
700 bitmap_set_bit (result, i);
704 bitmap_copy (set, result);
705 BITMAP_FREE (result);
708 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
712 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
715 return bitmap_ior_into (to, from);
721 tmp = BITMAP_ALLOC (&iteration_obstack);
722 bitmap_copy (tmp, from);
723 solution_set_add (tmp, inc);
724 res = bitmap_ior_into (to, tmp);
730 /* Insert constraint C into the list of complex constraints for VAR. */
733 insert_into_complex (unsigned int var, constraint_t c)
735 varinfo_t vi = get_varinfo (var);
736 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
738 VEC_safe_insert (constraint_t, heap, vi->complex, place, c);
742 /* Compare two constraint edges A and B, return true if they are equal. */
745 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
747 return a.dest == b.dest;
750 /* Compare two constraint edges, return true if A is less than B */
753 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
755 if (a->dest < b->dest)
760 /* Find the constraint edge that matches LOOKFOR, in VEC.
761 Return the edge, if found, NULL otherwise. */
763 static constraint_edge_t
764 constraint_edge_vec_find (VEC(constraint_edge_t,heap) *vec,
765 struct constraint_edge lookfor)
768 constraint_edge_t edge = NULL;
770 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
771 constraint_edge_less);
772 if (place >= VEC_length (constraint_edge_t, vec))
774 edge = VEC_index (constraint_edge_t, vec, place);
775 if (!constraint_edge_equal (*edge, lookfor))
780 /* Condense two variable nodes into a single variable node, by moving
781 all associated info from SRC to TO. */
784 condense_varmap_nodes (unsigned int to, unsigned int src)
786 varinfo_t tovi = get_varinfo (to);
787 varinfo_t srcvi = get_varinfo (src);
792 /* the src node, and all its variables, are now the to node. */
794 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
795 get_varinfo (i)->node = to;
797 /* Merge the src node variables and the to node variables. */
798 bitmap_set_bit (tovi->variables, src);
799 bitmap_ior_into (tovi->variables, srcvi->variables);
800 bitmap_clear (srcvi->variables);
802 /* Move all complex constraints from src node into to node */
803 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
805 /* In complex constraints for node src, we may have either
806 a = *src, and *src = a. */
808 if (c->rhs.type == DEREF)
813 constraint_set_union (&tovi->complex, &srcvi->complex);
814 VEC_free (constraint_t, heap, srcvi->complex);
815 srcvi->complex = NULL;
818 /* Erase an edge from SRC to SRC from GRAPH. This routine only
819 handles self-edges (e.g. an edge from a to a). */
822 erase_graph_self_edge (constraint_graph_t graph, unsigned int src)
824 VEC(constraint_edge_t,heap) *predvec = graph->preds[src];
825 VEC(constraint_edge_t,heap) *succvec = graph->succs[src];
826 struct constraint_edge edge;
831 /* Remove from the successors. */
832 place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
833 constraint_edge_less);
835 /* Make sure we found the edge. */
836 #ifdef ENABLE_CHECKING
838 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
839 gcc_assert (constraint_edge_equal (*tmp, edge));
842 VEC_ordered_remove (constraint_edge_t, succvec, place);
844 /* Remove from the predecessors. */
845 place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
846 constraint_edge_less);
848 /* Make sure we found the edge. */
849 #ifdef ENABLE_CHECKING
851 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
852 gcc_assert (constraint_edge_equal (*tmp, edge));
855 VEC_ordered_remove (constraint_edge_t, predvec, place);
858 /* Remove edges involving NODE from GRAPH. */
861 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
863 VEC(constraint_edge_t,heap) *succvec = graph->succs[node];
864 VEC(constraint_edge_t,heap) *predvec = graph->preds[node];
867 constraint_edge_t c = NULL;
870 /* Walk the successors, erase the associated preds. */
872 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[node], 0, j, bi)
874 bitmap_clear_bit (graph->zero_weight_preds[j], node);
876 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
880 struct constraint_edge lookfor;
881 constraint_edge_t result;
884 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
885 &lookfor, constraint_edge_less);
886 result = VEC_ordered_remove (constraint_edge_t,
887 graph->preds[c->dest], place);
888 pool_free (constraint_edge_pool, result);
891 /* Walk the preds, erase the associated succs. */
893 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[node], 0, j, bi)
895 bitmap_clear_bit (graph->zero_weight_succs[j], node);
897 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
901 struct constraint_edge lookfor;
902 constraint_edge_t result;
905 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
906 &lookfor, constraint_edge_less);
907 result = VEC_ordered_remove (constraint_edge_t,
908 graph->succs[c->dest], place);
909 pool_free (constraint_edge_pool, result);
913 if (graph->zero_weight_preds[node])
915 BITMAP_FREE (graph->zero_weight_preds[node]);
916 graph->zero_weight_preds[node] = NULL;
919 if (graph->zero_weight_succs[node])
921 BITMAP_FREE (graph->zero_weight_succs[node]);
922 graph->zero_weight_succs[node] = NULL;
925 VEC_free (constraint_edge_t, heap, graph->preds[node]);
926 VEC_free (constraint_edge_t, heap, graph->succs[node]);
927 graph->preds[node] = NULL;
928 graph->succs[node] = NULL;
931 static bool edge_added = false;
933 /* Add edge (src, dest) to the graph. */
936 add_graph_edge (constraint_graph_t graph, unsigned int src, unsigned int dest)
939 VEC(constraint_edge_t,heap) *vec;
940 struct constraint_edge newe;
943 vec = graph->preds[src];
944 place = VEC_lower_bound (constraint_edge_t, vec, &newe,
945 constraint_edge_less);
946 if (place == VEC_length (constraint_edge_t, vec)
947 || VEC_index (constraint_edge_t, vec, place)->dest != dest)
949 constraint_edge_t edge = new_constraint_edge (dest);
951 VEC_safe_insert (constraint_edge_t, heap, graph->preds[src],
953 edge = new_constraint_edge (src);
955 place = VEC_lower_bound (constraint_edge_t, graph->succs[dest],
956 edge, constraint_edge_less);
957 VEC_safe_insert (constraint_edge_t, heap, graph->succs[dest],
968 /* Return the bitmap representing the weights of edge (SRC, DEST). */
971 get_graph_weights (constraint_graph_t graph, unsigned int src,
974 constraint_edge_t edge;
975 VEC(constraint_edge_t,heap) *vec;
976 struct constraint_edge lookfor;
980 vec = graph->preds[src];
981 edge = constraint_edge_vec_find (vec, lookfor);
982 gcc_assert (edge != NULL);
983 return &edge->weights;
986 /* Allocate graph weight bitmap for the edges associated with SRC and
987 DEST in GRAPH. Both the pred and the succ edges share a single
988 bitmap, so we need to set both edges to that bitmap. */
991 allocate_graph_weights (constraint_graph_t graph, unsigned int src,
995 constraint_edge_t edge;
996 VEC(constraint_edge_t,heap) *vec;
997 struct constraint_edge lookfor;
999 result = BITMAP_ALLOC (&ptabitmap_obstack);
1001 /* Set the pred weight. */
1002 lookfor.dest = dest;
1003 vec = graph->preds[src];
1004 edge = constraint_edge_vec_find (vec, lookfor);
1005 gcc_assert (edge != NULL);
1006 edge->weights = result;
1008 /* Set the succ weight. */
1010 vec = graph->succs[dest];
1011 edge = constraint_edge_vec_find (vec, lookfor);
1012 gcc_assert (edge != NULL);
1013 edge->weights = result;
1019 /* Merge GRAPH nodes FROM and TO into node TO. */
1022 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1025 VEC(constraint_edge_t,heap) *succvec = graph->succs[from];
1026 VEC(constraint_edge_t,heap) *predvec = graph->preds[from];
1028 constraint_edge_t c;
1032 /* Merge all the zero weighted predecessor edges. */
1033 if (graph->zero_weight_preds[from])
1035 if (!graph->zero_weight_preds[to])
1036 graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1038 EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_preds[from], 0, j, bi)
1042 bitmap_clear_bit (graph->zero_weight_succs[j], from);
1043 bitmap_set_bit (graph->zero_weight_succs[j], to);
1046 bitmap_ior_into (graph->zero_weight_preds[to],
1047 graph->zero_weight_preds[from]);
1050 /* Merge all the zero weighted successor edges. */
1051 if (graph->zero_weight_succs[from])
1053 if (!graph->zero_weight_succs[to])
1054 graph->zero_weight_succs[to] = BITMAP_ALLOC (&ptabitmap_obstack);
1055 EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_succs[from], 0, j, bi)
1057 bitmap_clear_bit (graph->zero_weight_preds[j], from);
1058 bitmap_set_bit (graph->zero_weight_preds[j], to);
1060 bitmap_ior_into (graph->zero_weight_succs[to],
1061 graph->zero_weight_succs[from]);
1064 /* Merge all the nonzero weighted predecessor edges. */
1065 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
1067 unsigned int d = c->dest;
1071 if (c->dest == from)
1074 add_graph_edge (graph, to, d);
1076 temp = *(get_graph_weights (graph, from, c->dest));
1079 weights = get_graph_weights (graph, to, d);
1081 *weights = allocate_graph_weights (graph, to, d);
1083 bitmap_ior_into (*weights, temp);
1088 /* Merge all the nonzero weighted successor edges. */
1089 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
1091 unsigned int d = c->dest;
1095 if (c->dest == from)
1098 add_graph_edge (graph, d, to);
1100 temp = *(get_graph_weights (graph, c->dest, from));
1103 weights = get_graph_weights (graph, d, to);
1105 *weights = allocate_graph_weights (graph, d, to);
1106 bitmap_ior_into (*weights, temp);
1109 clear_edges_for_node (graph, from);
1112 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
1113 it doesn't exist in the graph already.
1114 Return false if the edge already existed, true otherwise. */
1117 int_add_graph_edge (constraint_graph_t graph, unsigned int to,
1118 unsigned int from, unsigned HOST_WIDE_INT weight)
1120 if (to == from && weight == 0)
1130 if (!graph->zero_weight_preds[to])
1131 graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1132 if (!graph->zero_weight_succs[from])
1133 graph->zero_weight_succs[from] = BITMAP_ALLOC (&ptabitmap_obstack);
1134 if (!bitmap_bit_p (graph->zero_weight_succs[from], to))
1139 bitmap_set_bit (graph->zero_weight_preds[to], from);
1140 bitmap_set_bit (graph->zero_weight_succs[from], to);
1147 r = add_graph_edge (graph, to, from);
1148 weights = get_graph_weights (graph, to, from);
1153 *weights = allocate_graph_weights (graph, to, from);
1154 bitmap_set_bit (*weights, weight);
1158 r |= !bitmap_bit_p (*weights, weight);
1159 bitmap_set_bit (*weights, weight);
1168 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1171 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1174 struct constraint_edge lookfor;
1177 return (graph->zero_weight_succs[dest]
1178 && bitmap_bit_p (graph->zero_weight_succs[dest], src))
1179 || constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL;
1182 /* Return true if {DEST, SRC} is an existing weighted graph edge (IE has
1183 a weight other than 0) in GRAPH. */
1185 valid_weighted_graph_edge (constraint_graph_t graph, unsigned int src,
1188 struct constraint_edge lookfor;
1191 return graph->preds[src]
1192 && constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL;
1196 /* Build the constraint graph. */
1199 build_constraint_graph (void)
1204 graph = XNEW (struct constraint_graph);
1205 graph_size = VEC_length (varinfo_t, varmap) + 1;
1206 graph->succs = XCNEWVEC (VEC(constraint_edge_t,heap) *, graph_size);
1207 graph->preds = XCNEWVEC (VEC(constraint_edge_t,heap) *, graph_size);
1208 graph->zero_weight_succs = XCNEWVEC (bitmap, graph_size);
1209 graph->zero_weight_preds = XCNEWVEC (bitmap, graph_size);
1211 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1213 struct constraint_expr lhs = c->lhs;
1214 struct constraint_expr rhs = c->rhs;
1215 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
1216 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
1218 if (lhs.type == DEREF)
1220 /* *x = y or *x = &y (complex) */
1221 if (rhs.type == ADDRESSOF || rhsvar > anything_id)
1222 insert_into_complex (lhsvar, c);
1224 else if (rhs.type == DEREF)
1226 /* !special var= *y */
1227 if (!(get_varinfo (lhsvar)->is_special_var))
1228 insert_into_complex (rhsvar, c);
1230 else if (rhs.type == ADDRESSOF)
1233 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1235 else if (lhsvar > anything_id)
1237 /* Ignore 0 weighted self edges, as they can't possibly contribute
1239 if (lhsvar != rhsvar || rhs.offset != 0 || lhs.offset != 0)
1241 /* x = y (simple) */
1242 int_add_graph_edge (graph, lhs.var, rhs.var, rhs.offset);
1250 /* Changed variables on the last iteration. */
1251 static unsigned int changed_count;
1252 static sbitmap changed;
1254 DEF_VEC_I(unsigned);
1255 DEF_VEC_ALLOC_I(unsigned,heap);
1258 /* Strongly Connected Component visitation info. */
1263 sbitmap in_component;
1265 unsigned int *visited_index;
1266 VEC(unsigned,heap) *scc_stack;
1267 VEC(unsigned,heap) *unification_queue;
1271 /* Recursive routine to find strongly connected components in GRAPH.
1272 SI is the SCC info to store the information in, and N is the id of current
1273 graph node we are processing.
1275 This is Tarjan's strongly connected component finding algorithm, as
1276 modified by Nuutila to keep only non-root nodes on the stack.
1277 The algorithm can be found in "On finding the strongly connected
1278 connected components in a directed graph" by Esko Nuutila and Eljas
1279 Soisalon-Soininen, in Information Processing Letters volume 49,
1280 number 1, pages 9-14. */
1283 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1288 gcc_assert (get_varinfo (n)->node == n);
1289 SET_BIT (si->visited, n);
1290 RESET_BIT (si->in_component, n);
1291 si->visited_index[n] = si->current_index ++;
1293 /* Visit all the successors. */
1294 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[n], 0, i, bi)
1297 if (!TEST_BIT (si->visited, w))
1298 scc_visit (graph, si, w);
1299 if (!TEST_BIT (si->in_component, w))
1301 unsigned int t = get_varinfo (w)->node;
1302 unsigned int nnode = get_varinfo (n)->node;
1303 if (si->visited_index[t] < si->visited_index[nnode])
1304 get_varinfo (n)->node = t;
1308 /* See if any components have been identified. */
1309 if (get_varinfo (n)->node == n)
1311 unsigned int t = si->visited_index[n];
1312 SET_BIT (si->in_component, n);
1313 while (VEC_length (unsigned, si->scc_stack) != 0
1314 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1316 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1317 get_varinfo (w)->node = n;
1318 SET_BIT (si->in_component, w);
1319 /* Mark this node for collapsing. */
1320 VEC_safe_push (unsigned, heap, si->unification_queue, w);
1324 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1328 /* Collapse two variables into one variable. */
1331 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1333 bitmap tosol, fromsol;
1335 condense_varmap_nodes (to, from);
1336 tosol = get_varinfo (to)->solution;
1337 fromsol = get_varinfo (from)->solution;
1338 bitmap_ior_into (tosol, fromsol);
1339 merge_graph_nodes (graph, to, from);
1341 if (valid_graph_edge (graph, to, to))
1343 if (graph->zero_weight_preds[to])
1345 bitmap_clear_bit (graph->zero_weight_preds[to], to);
1346 bitmap_clear_bit (graph->zero_weight_succs[to], to);
1348 if (valid_weighted_graph_edge (graph, to, to))
1350 bitmap weights = *(get_graph_weights (graph, to, to));
1351 if (!weights || bitmap_empty_p (weights))
1352 erase_graph_self_edge (graph, to);
1355 BITMAP_FREE (fromsol);
1356 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1357 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1361 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1362 SI is the Strongly Connected Components information structure that tells us
1363 what components to unify.
1364 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1365 count should be updated to reflect the unification. */
1368 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1369 bool update_changed)
1372 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1375 /* We proceed as follows:
1377 For each component in the queue (components are delineated by
1378 when current_queue_element->node != next_queue_element->node):
1380 rep = representative node for component
1382 For each node (tounify) to be unified in the component,
1383 merge the solution for tounify into tmp bitmap
1385 clear solution for tounify
1387 merge edges from tounify into rep
1389 merge complex constraints from tounify into rep
1391 update changed count to note that tounify will never change
1394 Merge tmp into solution for rep, marking rep changed if this
1395 changed rep's solution.
1397 Delete any 0 weighted self-edges we now have for rep. */
1398 while (i != VEC_length (unsigned, si->unification_queue))
1400 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1401 unsigned int n = get_varinfo (tounify)->node;
1403 if (dump_file && (dump_flags & TDF_DETAILS))
1404 fprintf (dump_file, "Unifying %s to %s\n",
1405 get_varinfo (tounify)->name,
1406 get_varinfo (n)->name);
1408 stats.unified_vars_dynamic++;
1410 stats.unified_vars_static++;
1411 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1412 merge_graph_nodes (graph, n, tounify);
1413 condense_varmap_nodes (n, tounify);
1415 if (update_changed && TEST_BIT (changed, tounify))
1417 RESET_BIT (changed, tounify);
1418 if (!TEST_BIT (changed, n))
1419 SET_BIT (changed, n);
1422 gcc_assert (changed_count > 0);
1427 bitmap_clear (get_varinfo (tounify)->solution);
1430 /* If we've either finished processing the entire queue, or
1431 finished processing all nodes for component n, update the solution for
1433 if (i == VEC_length (unsigned, si->unification_queue)
1434 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1436 /* If the solution changes because of the merging, we need to mark
1437 the variable as changed. */
1438 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1440 if (update_changed && !TEST_BIT (changed, n))
1442 SET_BIT (changed, n);
1448 if (valid_graph_edge (graph, n, n))
1450 if (graph->zero_weight_succs[n])
1452 if (graph->zero_weight_preds[n])
1453 bitmap_clear_bit (graph->zero_weight_preds[n], n);
1454 bitmap_clear_bit (graph->zero_weight_succs[n], n);
1456 if (valid_weighted_graph_edge (graph, n, n))
1458 bitmap weights = *(get_graph_weights (graph, n, n));
1459 if (!weights || bitmap_empty_p (weights))
1460 erase_graph_self_edge (graph, n);
1469 /* Information needed to compute the topological ordering of a graph. */
1473 /* sbitmap of visited nodes. */
1475 /* Array that stores the topological order of the graph, *in
1477 VEC(unsigned,heap) *topo_order;
1481 /* Initialize and return a topological info structure. */
1483 static struct topo_info *
1484 init_topo_info (void)
1486 size_t size = VEC_length (varinfo_t, varmap);
1487 struct topo_info *ti = XNEW (struct topo_info);
1488 ti->visited = sbitmap_alloc (size);
1489 sbitmap_zero (ti->visited);
1490 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1495 /* Free the topological sort info pointed to by TI. */
1498 free_topo_info (struct topo_info *ti)
1500 sbitmap_free (ti->visited);
1501 VEC_free (unsigned, heap, ti->topo_order);
1505 /* Visit the graph in topological order, and store the order in the
1506 topo_info structure. */
1509 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1512 VEC(constraint_edge_t,heap) *succs = graph->succs[n];
1515 constraint_edge_t c;
1519 SET_BIT (ti->visited, n);
1520 if (VEC_length (constraint_edge_t, succs) != 0)
1522 temp = BITMAP_ALLOC (&iteration_obstack);
1523 if (graph->zero_weight_succs[n])
1524 bitmap_ior_into (temp, graph->zero_weight_succs[n]);
1525 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1526 bitmap_set_bit (temp, c->dest);
1529 temp = graph->zero_weight_succs[n];
1532 EXECUTE_IF_SET_IN_BITMAP (temp, 0, j, bi)
1534 if (!TEST_BIT (ti->visited, j))
1535 topo_visit (graph, ti, j);
1537 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1540 /* Return true if variable N + OFFSET is a legal field of N. */
1543 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1545 varinfo_t ninfo = get_varinfo (n);
1547 /* For things we've globbed to single variables, any offset into the
1548 variable acts like the entire variable, so that it becomes offset
1550 if (ninfo->is_special_var
1551 || ninfo->is_artificial_var
1552 || ninfo->is_unknown_size_var)
1557 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1560 /* Process a constraint C that represents *x = &y. */
1563 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1564 constraint_t c, bitmap delta)
1566 unsigned int rhs = c->rhs.var;
1570 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1571 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1573 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1574 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
1576 /* *x != NULL && *x != ANYTHING*/
1580 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1582 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1586 sol = get_varinfo (t)->solution;
1587 if (!bitmap_bit_p (sol, rhs))
1589 bitmap_set_bit (sol, rhs);
1590 if (!TEST_BIT (changed, t))
1592 SET_BIT (changed, t);
1597 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1598 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1603 /* Process a constraint C that represents x = *y, using DELTA as the
1604 starting solution. */
1607 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1610 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1612 bitmap sol = get_varinfo (lhs)->solution;
1616 if (bitmap_bit_p (delta, anything_id))
1618 flag = !bitmap_bit_p (sol, anything_id);
1620 bitmap_set_bit (sol, anything_id);
1623 /* For each variable j in delta (Sol(y)), add
1624 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1625 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1627 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1628 if (type_safe (j, &roffset))
1631 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1634 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1639 /* Adding edges from the special vars is pointless.
1640 They don't have sets that can change. */
1641 if (get_varinfo (t) ->is_special_var)
1642 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1643 else if (int_add_graph_edge (graph, lhs, t, 0))
1644 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1646 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1647 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1652 /* If the LHS solution changed, mark the var as changed. */
1655 get_varinfo (lhs)->solution = sol;
1656 if (!TEST_BIT (changed, lhs))
1658 SET_BIT (changed, lhs);
1664 /* Process a constraint C that represents *x = y. */
1667 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1669 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1670 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1671 bitmap sol = get_varinfo (rhs)->solution;
1675 if (bitmap_bit_p (sol, anything_id))
1677 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1679 varinfo_t jvi = get_varinfo (j);
1681 unsigned int loff = c->lhs.offset;
1682 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
1685 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1690 if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id))
1692 bitmap_set_bit (get_varinfo (t)->solution, anything_id);
1693 if (!TEST_BIT (changed, t))
1695 SET_BIT (changed, t);
1703 /* For each member j of delta (Sol(x)), add an edge from y to j and
1704 union Sol(y) into Sol(j) */
1705 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1707 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1708 if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var))
1712 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1714 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1718 if (int_add_graph_edge (graph, t, rhs, roff))
1720 bitmap tmp = get_varinfo (t)->solution;
1721 if (set_union_with_increment (tmp, sol, roff))
1723 get_varinfo (t)->solution = tmp;
1725 sol = get_varinfo (rhs)->solution;
1726 if (!TEST_BIT (changed, t))
1728 SET_BIT (changed, t);
1734 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1735 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1739 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1740 constraint (IE *x = &y, x = *y, and *x = y). */
1743 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1745 if (c->lhs.type == DEREF)
1747 if (c->rhs.type == ADDRESSOF)
1750 do_da_constraint (graph, c, delta);
1755 do_ds_constraint (graph, c, delta);
1761 if (!(get_varinfo (c->lhs.var)->is_special_var))
1762 do_sd_constraint (graph, c, delta);
1766 /* Initialize and return a new SCC info structure. */
1768 static struct scc_info *
1769 init_scc_info (void)
1771 struct scc_info *si = XNEW (struct scc_info);
1772 size_t size = VEC_length (varinfo_t, varmap);
1774 si->current_index = 0;
1775 si->visited = sbitmap_alloc (size);
1776 sbitmap_zero (si->visited);
1777 si->in_component = sbitmap_alloc (size);
1778 sbitmap_ones (si->in_component);
1779 si->visited_index = XCNEWVEC (unsigned int, size + 1);
1780 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1781 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1785 /* Free an SCC info structure pointed to by SI */
1788 free_scc_info (struct scc_info *si)
1790 sbitmap_free (si->visited);
1791 sbitmap_free (si->in_component);
1792 free (si->visited_index);
1793 VEC_free (unsigned, heap, si->scc_stack);
1794 VEC_free (unsigned, heap, si->unification_queue);
1799 /* Find cycles in GRAPH that occur, using strongly connected components, and
1800 collapse the cycles into a single representative node. if UPDATE_CHANGED
1801 is true, then update the changed sbitmap to note those nodes whose
1802 solutions have changed as a result of collapsing. */
1805 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1808 unsigned int size = VEC_length (varinfo_t, varmap);
1809 struct scc_info *si = init_scc_info ();
1811 for (i = 0; i != size; ++i)
1812 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1813 scc_visit (graph, si, i);
1815 process_unification_queue (graph, si, update_changed);
1819 /* Compute a topological ordering for GRAPH, and store the result in the
1820 topo_info structure TI. */
1823 compute_topo_order (constraint_graph_t graph,
1824 struct topo_info *ti)
1827 unsigned int size = VEC_length (varinfo_t, varmap);
1829 for (i = 0; i != size; ++i)
1830 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1831 topo_visit (graph, ti, i);
1834 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1837 bitmap_other_than_zero_bit_set (bitmap b)
1842 if (bitmap_empty_p (b))
1844 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1849 /* Perform offline variable substitution.
1851 This is a linear time way of identifying variables that must have
1852 equivalent points-to sets, including those caused by static cycles,
1853 and single entry subgraphs, in the constraint graph.
1855 The technique is described in "Off-line variable substitution for
1856 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1857 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1860 perform_var_substitution (constraint_graph_t graph)
1862 struct topo_info *ti = init_topo_info ();
1864 bitmap_obstack_initialize (&iteration_obstack);
1865 /* Compute the topological ordering of the graph, then visit each
1866 node in topological order. */
1867 compute_topo_order (graph, ti);
1869 while (VEC_length (unsigned, ti->topo_order) != 0)
1871 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1873 varinfo_t vi = get_varinfo (i);
1874 bool okay_to_elim = false;
1875 unsigned int root = VEC_length (varinfo_t, varmap);
1876 VEC(constraint_edge_t,heap) *predvec = graph->preds[i];
1877 constraint_edge_t ce = NULL;
1882 /* We can't eliminate things whose address is taken, or which is
1883 the target of a dereference. */
1884 if (vi->address_taken || vi->indirect_target)
1887 /* See if all predecessors of I are ripe for elimination */
1888 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[i], 0, k, bi)
1891 w = get_varinfo (k)->node;
1893 /* We can't eliminate the node if one of the predecessors is
1894 part of a different strongly connected component. */
1898 okay_to_elim = true;
1902 okay_to_elim = false;
1906 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1907 then Solution(i) is a subset of Solution (w), where w is a
1908 predecessor in the graph.
1909 Corollary: If all predecessors of i have the same
1910 points-to set, then i has that same points-to set as
1911 those predecessors. */
1912 tmp = BITMAP_ALLOC (NULL);
1913 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1914 get_varinfo (w)->solution);
1915 if (!bitmap_empty_p (tmp))
1917 okay_to_elim = false;
1926 VEC_iterate (constraint_edge_t, predvec, pred, ce);
1931 weight = *(get_graph_weights (graph, i, ce->dest));
1933 /* We can't eliminate variables that have nonzero weighted
1934 edges between them. */
1935 if (weight && bitmap_other_than_zero_bit_set (weight))
1937 okay_to_elim = false;
1940 w = get_varinfo (ce->dest)->node;
1942 /* We can't eliminate the node if one of the predecessors is
1943 part of a different strongly connected component. */
1947 okay_to_elim = true;
1951 okay_to_elim = false;
1955 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1956 then Solution(i) is a subset of Solution (w), where w is a
1957 predecessor in the graph.
1958 Corollary: If all predecessors of i have the same
1959 points-to set, then i has that same points-to set as
1960 those predecessors. */
1961 tmp = BITMAP_ALLOC (NULL);
1962 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1963 get_varinfo (w)->solution);
1964 if (!bitmap_empty_p (tmp))
1966 okay_to_elim = false;
1973 /* See if the root is different than the original node.
1974 If so, we've found an equivalence. */
1975 if (root != get_varinfo (i)->node && okay_to_elim)
1977 /* Found an equivalence */
1978 get_varinfo (i)->node = root;
1979 collapse_nodes (graph, root, i);
1980 if (dump_file && (dump_flags & TDF_DETAILS))
1981 fprintf (dump_file, "Collapsing %s into %s\n",
1982 get_varinfo (i)->name,
1983 get_varinfo (root)->name);
1984 stats.collapsed_vars++;
1988 bitmap_obstack_release (&iteration_obstack);
1989 free_topo_info (ti);
1992 /* Solve the constraint graph GRAPH using our worklist solver.
1993 This is based on the PW* family of solvers from the "Efficient Field
1994 Sensitive Pointer Analysis for C" paper.
1995 It works by iterating over all the graph nodes, processing the complex
1996 constraints and propagating the copy constraints, until everything stops
1997 changed. This corresponds to steps 6-8 in the solving list given above. */
2000 solve_graph (constraint_graph_t graph)
2002 unsigned int size = VEC_length (varinfo_t, varmap);
2005 changed_count = size;
2006 changed = sbitmap_alloc (size);
2007 sbitmap_ones (changed);
2009 /* The already collapsed/unreachable nodes will never change, so we
2010 need to account for them in changed_count. */
2011 for (i = 0; i < size; i++)
2012 if (get_varinfo (i)->node != i)
2015 while (changed_count > 0)
2018 struct topo_info *ti = init_topo_info ();
2021 bitmap_obstack_initialize (&iteration_obstack);
2025 /* We already did cycle elimination once, when we did
2026 variable substitution, so we don't need it again for the
2028 if (stats.iterations > 1)
2029 find_and_collapse_graph_cycles (graph, true);
2034 compute_topo_order (graph, ti);
2036 while (VEC_length (unsigned, ti->topo_order) != 0)
2038 i = VEC_pop (unsigned, ti->topo_order);
2039 gcc_assert (get_varinfo (i)->node == i);
2041 /* If the node has changed, we need to process the
2042 complex constraints and outgoing edges again. */
2043 if (TEST_BIT (changed, i))
2047 constraint_edge_t e = NULL;
2050 VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
2051 VEC(constraint_edge_t,heap) *succs;
2052 bool solution_empty;
2054 RESET_BIT (changed, i);
2057 solution = get_varinfo (i)->solution;
2058 solution_empty = bitmap_empty_p (solution);
2060 /* Process the complex constraints */
2061 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2063 /* The only complex constraint that can change our
2064 solution to non-empty, given an empty solution,
2065 is a constraint where the lhs side is receiving
2066 some set from elsewhere. */
2067 if (!solution_empty || c->lhs.type != DEREF)
2068 do_complex_constraint (graph, c, solution);
2071 solution_empty = bitmap_empty_p (solution);
2073 if (!solution_empty)
2075 /* Propagate solution to all successors. */
2076 succs = graph->succs[i];
2078 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[i],
2081 bitmap tmp = get_varinfo (j)->solution;
2084 flag = set_union_with_increment (tmp, solution, 0);
2088 get_varinfo (j)->solution = tmp;
2089 if (!TEST_BIT (changed, j))
2091 SET_BIT (changed, j);
2096 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
2098 bitmap tmp = get_varinfo (e->dest)->solution;
2101 bitmap weights = e->weights;
2104 gcc_assert (weights && !bitmap_empty_p (weights));
2105 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
2106 flag |= set_union_with_increment (tmp, solution, k);
2110 get_varinfo (e->dest)->solution = tmp;
2111 if (!TEST_BIT (changed, e->dest))
2113 SET_BIT (changed, e->dest);
2121 free_topo_info (ti);
2122 bitmap_obstack_release (&iteration_obstack);
2125 sbitmap_free (changed);
2129 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
2131 /* Map from trees to variable ids. */
2132 static htab_t id_for_tree;
2134 typedef struct tree_id
2140 /* Hash a tree id structure. */
2143 tree_id_hash (const void *p)
2145 const tree_id_t ta = (tree_id_t) p;
2146 return htab_hash_pointer (ta->t);
2149 /* Return true if the tree in P1 and the tree in P2 are the same. */
2152 tree_id_eq (const void *p1, const void *p2)
2154 const tree_id_t ta1 = (tree_id_t) p1;
2155 const tree_id_t ta2 = (tree_id_t) p2;
2156 return ta1->t == ta2->t;
2159 /* Insert ID as the variable id for tree T in the hashtable. */
2162 insert_id_for_tree (tree t, int id)
2165 struct tree_id finder;
2169 slot = htab_find_slot (id_for_tree, &finder, INSERT);
2170 gcc_assert (*slot == NULL);
2171 new_pair = XNEW (struct tree_id);
2174 *slot = (void *)new_pair;
2177 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
2178 exist in the hash table, return false, otherwise, return true and
2179 set *ID to the id we found. */
2182 lookup_id_for_tree (tree t, unsigned int *id)
2185 struct tree_id finder;
2188 pair = htab_find (id_for_tree, &finder);
2195 /* Return a printable name for DECL */
2198 alias_get_name (tree decl)
2200 const char *res = get_name (decl);
2202 int num_printed = 0;
2211 if (TREE_CODE (decl) == SSA_NAME)
2213 num_printed = asprintf (&temp, "%s_%u",
2214 alias_get_name (SSA_NAME_VAR (decl)),
2215 SSA_NAME_VERSION (decl));
2217 else if (DECL_P (decl))
2219 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2221 if (num_printed > 0)
2223 res = ggc_strdup (temp);
2229 /* Find the variable id for tree T in the hashtable.
2230 If T doesn't exist in the hash table, create an entry for it. */
2233 get_id_for_tree (tree t)
2236 struct tree_id finder;
2239 pair = htab_find (id_for_tree, &finder);
2241 return create_variable_info_for (t, alias_get_name (t));
2246 /* Get a constraint expression from an SSA_VAR_P node. */
2248 static struct constraint_expr
2249 get_constraint_exp_from_ssa_var (tree t)
2251 struct constraint_expr cexpr;
2253 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2255 /* For parameters, get at the points-to set for the actual parm
2257 if (TREE_CODE (t) == SSA_NAME
2258 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2259 && default_def (SSA_NAME_VAR (t)) == t)
2260 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
2262 cexpr.type = SCALAR;
2264 cexpr.var = get_id_for_tree (t);
2265 /* If we determine the result is "anything", and we know this is readonly,
2266 say it points to readonly memory instead. */
2267 if (cexpr.var == anything_id && TREE_READONLY (t))
2269 cexpr.type = ADDRESSOF;
2270 cexpr.var = readonly_id;
2277 /* Process a completed constraint T, and add it to the constraint
2281 process_constraint (constraint_t t)
2283 struct constraint_expr rhs = t->rhs;
2284 struct constraint_expr lhs = t->lhs;
2286 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2287 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2289 if (lhs.type == DEREF)
2290 get_varinfo (lhs.var)->directly_dereferenced = true;
2291 if (rhs.type == DEREF)
2292 get_varinfo (rhs.var)->directly_dereferenced = true;
2294 /* ANYTHING == ANYTHING is pointless. */
2295 if (lhs.var == anything_id && rhs.var == anything_id)
2298 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2299 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
2304 process_constraint (t);
2306 /* This can happen in our IR with things like n->a = *p */
2307 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2309 /* Split into tmp = *rhs, *lhs = tmp */
2310 tree rhsdecl = get_varinfo (rhs.var)->decl;
2311 tree pointertype = TREE_TYPE (rhsdecl);
2312 tree pointedtotype = TREE_TYPE (pointertype);
2313 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2314 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2316 /* If this is an aggregate of known size, we should have passed
2317 this off to do_structure_copy, and it should have broken it
2319 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
2320 || get_varinfo (rhs.var)->is_unknown_size_var);
2322 process_constraint (new_constraint (tmplhs, rhs));
2323 process_constraint (new_constraint (lhs, tmplhs));
2325 else if (rhs.type == ADDRESSOF)
2328 gcc_assert (rhs.offset == 0);
2330 /* No need to mark address taken simply because of escaped vars
2332 if (lhs.var != escaped_vars_id)
2333 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
2334 vi->address_taken = true;
2336 VEC_safe_push (constraint_t, heap, constraints, t);
2340 if (lhs.type != DEREF && rhs.type == DEREF)
2341 get_varinfo (lhs.var)->indirect_target = true;
2342 VEC_safe_push (constraint_t, heap, constraints, t);
2346 /* Return true if T is a variable of a type that could contain
2350 could_have_pointers (tree t)
2352 tree type = TREE_TYPE (t);
2354 if (POINTER_TYPE_P (type) || AGGREGATE_TYPE_P (type)
2355 || TREE_CODE (type) == COMPLEX_TYPE)
2360 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2363 static unsigned HOST_WIDE_INT
2364 bitpos_of_field (const tree fdecl)
2367 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
2368 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
2371 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
2372 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
2376 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2377 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2380 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
2381 const unsigned HOST_WIDE_INT fieldsize,
2382 const unsigned HOST_WIDE_INT accesspos,
2383 const unsigned HOST_WIDE_INT accesssize)
2385 if (fieldpos == accesspos && fieldsize == accesssize)
2387 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
2389 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2395 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2398 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results)
2401 HOST_WIDE_INT bitsize = -1;
2402 HOST_WIDE_INT bitmaxsize = -1;
2403 HOST_WIDE_INT bitpos;
2405 struct constraint_expr *result;
2406 unsigned int beforelength = VEC_length (ce_s, *results);
2408 /* Some people like to do cute things like take the address of
2411 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2412 forzero = TREE_OPERAND (forzero, 0);
2414 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2416 struct constraint_expr temp;
2419 temp.var = integer_id;
2421 VEC_safe_push (ce_s, heap, *results, &temp);
2425 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2427 /* String constants are readonly, so there is nothing to really do
2429 if (TREE_CODE (t) == STRING_CST)
2432 get_constraint_for (t, results);
2433 result = VEC_last (ce_s, *results);
2434 result->offset = bitpos;
2436 gcc_assert (beforelength + 1 == VEC_length (ce_s, *results));
2438 /* This can also happen due to weird offsetof type macros. */
2439 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2440 result->type = SCALAR;
2442 if (result->type == SCALAR)
2444 /* In languages like C, you can access one past the end of an
2445 array. You aren't allowed to dereference it, so we can
2446 ignore this constraint. When we handle pointer subtraction,
2447 we may have to do something cute here. */
2449 if (result->offset < get_varinfo (result->var)->fullsize
2452 /* It's also not true that the constraint will actually start at the
2453 right offset, it may start in some padding. We only care about
2454 setting the constraint to the first actual field it touches, so
2457 for (curr = get_varinfo (result->var); curr; curr = curr->next)
2459 if (offset_overlaps_with_access (curr->offset, curr->size,
2460 result->offset, bitmaxsize))
2462 result->var = curr->id;
2466 /* assert that we found *some* field there. The user couldn't be
2467 accessing *only* padding. */
2468 /* Still the user could access one past the end of an array
2469 embedded in a struct resulting in accessing *only* padding. */
2470 gcc_assert (curr || ref_contains_array_ref (orig_t));
2472 else if (bitmaxsize == 0)
2474 if (dump_file && (dump_flags & TDF_DETAILS))
2475 fprintf (dump_file, "Access to zero-sized part of variable,"
2479 if (dump_file && (dump_flags & TDF_DETAILS))
2480 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2487 /* Dereference the constraint expression CONS, and return the result.
2488 DEREF (ADDRESSOF) = SCALAR
2489 DEREF (SCALAR) = DEREF
2490 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2491 This is needed so that we can handle dereferencing DEREF constraints. */
2494 do_deref (VEC (ce_s, heap) **constraints)
2496 struct constraint_expr *c;
2498 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2500 if (c->type == SCALAR)
2502 else if (c->type == ADDRESSOF)
2504 else if (c->type == DEREF)
2506 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
2507 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2508 process_constraint (new_constraint (tmplhs, *c));
2509 c->var = tmplhs.var;
2516 /* Create a nonlocal variable of TYPE to represent nonlocals we can
2520 create_nonlocal_var (tree type)
2522 tree nonlocal = create_tmp_var_raw (type, "NONLOCAL");
2524 if (referenced_vars)
2525 add_referenced_var (nonlocal);
2527 DECL_EXTERNAL (nonlocal) = 1;
2531 /* Given a tree T, return the constraint expression for it. */
2534 get_constraint_for (tree t, VEC (ce_s, heap) **results)
2536 struct constraint_expr temp;
2538 /* x = integer is all glommed to a single variable, which doesn't
2539 point to anything by itself. That is, of course, unless it is an
2540 integer constant being treated as a pointer, in which case, we
2541 will return that this is really the addressof anything. This
2542 happens below, since it will fall into the default case. The only
2543 case we know something about an integer treated like a pointer is
2544 when it is the NULL pointer, and then we just say it points to
2546 if (TREE_CODE (t) == INTEGER_CST
2547 && !POINTER_TYPE_P (TREE_TYPE (t)))
2549 temp.var = integer_id;
2552 VEC_safe_push (ce_s, heap, *results, &temp);
2555 else if (TREE_CODE (t) == INTEGER_CST
2556 && integer_zerop (t))
2558 temp.var = nothing_id;
2559 temp.type = ADDRESSOF;
2561 VEC_safe_push (ce_s, heap, *results, &temp);
2565 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2567 case tcc_expression:
2569 switch (TREE_CODE (t))
2573 struct constraint_expr *c;
2575 tree exp = TREE_OPERAND (t, 0);
2576 tree pttype = TREE_TYPE (TREE_TYPE (t));
2578 get_constraint_for (exp, results);
2579 /* Make sure we capture constraints to all elements
2581 if ((handled_component_p (exp)
2582 && ref_contains_array_ref (exp))
2583 || TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE)
2585 struct constraint_expr *origrhs;
2587 struct constraint_expr tmp;
2589 if (VEC_length (ce_s, *results) == 0)
2592 gcc_assert (VEC_length (ce_s, *results) == 1);
2593 origrhs = VEC_last (ce_s, *results);
2595 VEC_pop (ce_s, *results);
2596 origvar = get_varinfo (origrhs->var);
2597 for (; origvar; origvar = origvar->next)
2599 tmp.var = origvar->id;
2600 VEC_safe_push (ce_s, heap, *results, &tmp);
2603 else if (VEC_length (ce_s, *results) == 1
2604 && (AGGREGATE_TYPE_P (pttype)
2605 || TREE_CODE (pttype) == COMPLEX_TYPE))
2607 struct constraint_expr *origrhs;
2609 struct constraint_expr tmp;
2611 gcc_assert (VEC_length (ce_s, *results) == 1);
2612 origrhs = VEC_last (ce_s, *results);
2614 VEC_pop (ce_s, *results);
2615 origvar = get_varinfo (origrhs->var);
2616 for (; origvar; origvar = origvar->next)
2618 tmp.var = origvar->id;
2619 VEC_safe_push (ce_s, heap, *results, &tmp);
2623 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2625 if (c->type == DEREF)
2628 c->type = ADDRESSOF;
2634 /* XXX: In interprocedural mode, if we didn't have the
2635 body, we would need to do *each pointer argument =
2637 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2640 tree heapvar = heapvar_lookup (t);
2642 if (heapvar == NULL)
2644 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2645 DECL_EXTERNAL (heapvar) = 1;
2646 get_var_ann (heapvar)->is_heapvar = 1;
2647 if (referenced_vars)
2648 add_referenced_var (heapvar);
2649 heapvar_insert (t, heapvar);
2652 temp.var = create_variable_info_for (heapvar,
2653 alias_get_name (heapvar));
2655 vi = get_varinfo (temp.var);
2656 vi->is_artificial_var = 1;
2657 vi->is_heap_var = 1;
2658 temp.type = ADDRESSOF;
2660 VEC_safe_push (ce_s, heap, *results, &temp);
2665 temp.var = escaped_vars_id;
2668 VEC_safe_push (ce_s, heap, *results, &temp);
2674 temp.type = ADDRESSOF;
2675 temp.var = anything_id;
2677 VEC_safe_push (ce_s, heap, *results, &temp);
2684 switch (TREE_CODE (t))
2688 get_constraint_for (TREE_OPERAND (t, 0), results);
2693 case ARRAY_RANGE_REF:
2695 get_constraint_for_component_ref (t, results);
2699 temp.type = ADDRESSOF;
2700 temp.var = anything_id;
2702 VEC_safe_push (ce_s, heap, *results, &temp);
2709 switch (TREE_CODE (t))
2713 case NON_LVALUE_EXPR:
2715 tree op = TREE_OPERAND (t, 0);
2717 /* Cast from non-pointer to pointers are bad news for us.
2718 Anything else, we see through */
2719 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2720 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2722 get_constraint_for (op, results);
2730 temp.type = ADDRESSOF;
2731 temp.var = anything_id;
2733 VEC_safe_push (ce_s, heap, *results, &temp);
2738 case tcc_exceptional:
2740 switch (TREE_CODE (t))
2744 get_constraint_for (PHI_RESULT (t), results);
2750 struct constraint_expr temp;
2751 temp = get_constraint_exp_from_ssa_var (t);
2752 VEC_safe_push (ce_s, heap, *results, &temp);
2758 temp.type = ADDRESSOF;
2759 temp.var = anything_id;
2761 VEC_safe_push (ce_s, heap, *results, &temp);
2766 case tcc_declaration:
2768 struct constraint_expr temp;
2769 temp = get_constraint_exp_from_ssa_var (t);
2770 VEC_safe_push (ce_s, heap, *results, &temp);
2775 temp.type = ADDRESSOF;
2776 temp.var = anything_id;
2778 VEC_safe_push (ce_s, heap, *results, &temp);
2785 /* Handle the structure copy case where we have a simple structure copy
2786 between LHS and RHS that is of SIZE (in bits)
2788 For each field of the lhs variable (lhsfield)
2789 For each field of the rhs variable at lhsfield.offset (rhsfield)
2790 add the constraint lhsfield = rhsfield
2792 If we fail due to some kind of type unsafety or other thing we
2793 can't handle, return false. We expect the caller to collapse the
2794 variable in that case. */
2797 do_simple_structure_copy (const struct constraint_expr lhs,
2798 const struct constraint_expr rhs,
2799 const unsigned HOST_WIDE_INT size)
2801 varinfo_t p = get_varinfo (lhs.var);
2802 unsigned HOST_WIDE_INT pstart, last;
2804 last = p->offset + size;
2805 for (; p && p->offset < last; p = p->next)
2808 struct constraint_expr templhs = lhs;
2809 struct constraint_expr temprhs = rhs;
2810 unsigned HOST_WIDE_INT fieldoffset;
2812 templhs.var = p->id;
2813 q = get_varinfo (temprhs.var);
2814 fieldoffset = p->offset - pstart;
2815 q = first_vi_for_offset (q, q->offset + fieldoffset);
2818 temprhs.var = q->id;
2819 process_constraint (new_constraint (templhs, temprhs));
2825 /* Handle the structure copy case where we have a structure copy between a
2826 aggregate on the LHS and a dereference of a pointer on the RHS
2827 that is of SIZE (in bits)
2829 For each field of the lhs variable (lhsfield)
2830 rhs.offset = lhsfield->offset
2831 add the constraint lhsfield = rhs
2835 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2836 const struct constraint_expr rhs,
2837 const unsigned HOST_WIDE_INT size)
2839 varinfo_t p = get_varinfo (lhs.var);
2840 unsigned HOST_WIDE_INT pstart,last;
2842 last = p->offset + size;
2844 for (; p && p->offset < last; p = p->next)
2847 struct constraint_expr templhs = lhs;
2848 struct constraint_expr temprhs = rhs;
2849 unsigned HOST_WIDE_INT fieldoffset;
2852 if (templhs.type == SCALAR)
2853 templhs.var = p->id;
2855 templhs.offset = p->offset;
2857 q = get_varinfo (temprhs.var);
2858 fieldoffset = p->offset - pstart;
2859 temprhs.offset += fieldoffset;
2860 process_constraint (new_constraint (templhs, temprhs));
2864 /* Handle the structure copy case where we have a structure copy
2865 between a aggregate on the RHS and a dereference of a pointer on
2866 the LHS that is of SIZE (in bits)
2868 For each field of the rhs variable (rhsfield)
2869 lhs.offset = rhsfield->offset
2870 add the constraint lhs = rhsfield
2874 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2875 const struct constraint_expr rhs,
2876 const unsigned HOST_WIDE_INT size)
2878 varinfo_t p = get_varinfo (rhs.var);
2879 unsigned HOST_WIDE_INT pstart,last;
2881 last = p->offset + size;
2883 for (; p && p->offset < last; p = p->next)
2886 struct constraint_expr templhs = lhs;
2887 struct constraint_expr temprhs = rhs;
2888 unsigned HOST_WIDE_INT fieldoffset;
2891 if (temprhs.type == SCALAR)
2892 temprhs.var = p->id;
2894 temprhs.offset = p->offset;
2896 q = get_varinfo (templhs.var);
2897 fieldoffset = p->offset - pstart;
2898 templhs.offset += fieldoffset;
2899 process_constraint (new_constraint (templhs, temprhs));
2903 /* Sometimes, frontends like to give us bad type information. This
2904 function will collapse all the fields from VAR to the end of VAR,
2905 into VAR, so that we treat those fields as a single variable.
2906 We return the variable they were collapsed into. */
2909 collapse_rest_of_var (unsigned int var)
2911 varinfo_t currvar = get_varinfo (var);
2914 for (field = currvar->next; field; field = field->next)
2917 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
2918 field->name, currvar->name);
2920 gcc_assert (!field->collapsed_to);
2921 field->collapsed_to = currvar;
2924 currvar->next = NULL;
2925 currvar->size = currvar->fullsize - currvar->offset;
2930 /* Handle aggregate copies by expanding into copies of the respective
2931 fields of the structures. */
2934 do_structure_copy (tree lhsop, tree rhsop)
2936 struct constraint_expr lhs, rhs, tmp;
2937 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
2939 unsigned HOST_WIDE_INT lhssize;
2940 unsigned HOST_WIDE_INT rhssize;
2942 get_constraint_for (lhsop, &lhsc);
2943 get_constraint_for (rhsop, &rhsc);
2944 gcc_assert (VEC_length (ce_s, lhsc) == 1);
2945 gcc_assert (VEC_length (ce_s, rhsc) == 1);
2946 lhs = *(VEC_last (ce_s, lhsc));
2947 rhs = *(VEC_last (ce_s, rhsc));
2949 VEC_free (ce_s, heap, lhsc);
2950 VEC_free (ce_s, heap, rhsc);
2952 /* If we have special var = x, swap it around. */
2953 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2960 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2961 possible it's something we could handle. However, most cases falling
2962 into this are dealing with transparent unions, which are slightly
2964 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2966 rhs.type = ADDRESSOF;
2967 rhs.var = anything_id;
2970 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2971 that special var. */
2972 if (rhs.var <= integer_id)
2974 for (p = get_varinfo (lhs.var); p; p = p->next)
2976 struct constraint_expr templhs = lhs;
2977 struct constraint_expr temprhs = rhs;
2979 if (templhs.type == SCALAR )
2980 templhs.var = p->id;
2982 templhs.offset += p->offset;
2983 process_constraint (new_constraint (templhs, temprhs));
2988 tree rhstype = TREE_TYPE (rhsop);
2989 tree lhstype = TREE_TYPE (lhsop);
2993 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
2994 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
2996 /* If we have a variably sized types on the rhs or lhs, and a deref
2997 constraint, add the constraint, lhsconstraint = &ANYTHING.
2998 This is conservatively correct because either the lhs is an unknown
2999 sized var (if the constraint is SCALAR), or the lhs is a DEREF
3000 constraint, and every variable it can point to must be unknown sized
3001 anyway, so we don't need to worry about fields at all. */
3002 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
3003 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
3005 rhs.var = anything_id;
3006 rhs.type = ADDRESSOF;
3008 process_constraint (new_constraint (lhs, rhs));
3012 /* The size only really matters insofar as we don't set more or less of
3013 the variable. If we hit an unknown size var, the size should be the
3014 whole darn thing. */
3015 if (get_varinfo (rhs.var)->is_unknown_size_var)
3018 rhssize = TREE_INT_CST_LOW (rhstypesize);
3020 if (get_varinfo (lhs.var)->is_unknown_size_var)
3023 lhssize = TREE_INT_CST_LOW (lhstypesize);
3026 if (rhs.type == SCALAR && lhs.type == SCALAR)
3028 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
3030 lhs.var = collapse_rest_of_var (lhs.var);
3031 rhs.var = collapse_rest_of_var (rhs.var);
3036 process_constraint (new_constraint (lhs, rhs));
3039 else if (lhs.type != DEREF && rhs.type == DEREF)
3040 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3041 else if (lhs.type == DEREF && rhs.type != DEREF)
3042 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3045 tree pointedtotype = lhstype;
3048 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3049 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
3050 do_structure_copy (tmpvar, rhsop);
3051 do_structure_copy (lhsop, tmpvar);
3056 /* Update related alias information kept in AI. This is used when
3057 building name tags, alias sets and deciding grouping heuristics.
3058 STMT is the statement to process. This function also updates
3059 ADDRESSABLE_VARS. */
3062 update_alias_info (tree stmt, struct alias_info *ai)
3065 use_operand_p use_p;
3067 enum escape_type stmt_escape_type = is_escape_site (stmt);
3070 if (stmt_escape_type == ESCAPE_TO_CALL
3071 || stmt_escape_type == ESCAPE_TO_PURE_CONST)
3073 ai->num_calls_found++;
3074 if (stmt_escape_type == ESCAPE_TO_PURE_CONST)
3075 ai->num_pure_const_calls_found++;
3078 /* Mark all the variables whose address are taken by the statement. */
3079 addr_taken = addresses_taken (stmt);
3082 bitmap_ior_into (addressable_vars, addr_taken);
3084 /* If STMT is an escape point, all the addresses taken by it are
3086 if (stmt_escape_type != NO_ESCAPE)
3091 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
3093 tree rvar = referenced_var (i);
3094 if (!unmodifiable_var_p (rvar))
3095 mark_call_clobbered (rvar, stmt_escape_type);
3100 /* Process each operand use. If an operand may be aliased, keep
3101 track of how many times it's being used. For pointers, determine
3102 whether they are dereferenced by the statement, or whether their
3103 value escapes, etc. */
3104 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
3108 struct ptr_info_def *pi;
3109 bool is_store, is_potential_deref;
3110 unsigned num_uses, num_derefs;
3112 op = USE_FROM_PTR (use_p);
3114 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
3115 to the set of addressable variables. */
3116 if (TREE_CODE (op) == ADDR_EXPR)
3118 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
3120 /* PHI nodes don't have annotations for pinning the set
3121 of addresses taken, so we collect them here.
3123 FIXME, should we allow PHI nodes to have annotations
3124 so that they can be treated like regular statements?
3125 Currently, they are treated as second-class
3127 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
3131 /* Ignore constants. */
3132 if (TREE_CODE (op) != SSA_NAME)
3135 var = SSA_NAME_VAR (op);
3136 v_ann = var_ann (var);
3138 /* The base variable of an ssa name must be a GIMPLE register, and thus
3139 it cannot be aliased. */
3140 gcc_assert (!may_be_aliased (var));
3142 /* We are only interested in pointers. */
3143 if (!POINTER_TYPE_P (TREE_TYPE (op)))
3146 pi = get_ptr_info (op);
3148 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3149 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
3151 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
3152 VEC_safe_push (tree, heap, ai->processed_ptrs, op);
3155 /* If STMT is a PHI node, then it will not have pointer
3156 dereferences and it will not be an escape point. */
3157 if (TREE_CODE (stmt) == PHI_NODE)
3160 /* Determine whether OP is a dereferenced pointer, and if STMT
3161 is an escape point, whether OP escapes. */
3162 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
3164 /* Handle a corner case involving address expressions of the
3165 form '&PTR->FLD'. The problem with these expressions is that
3166 they do not represent a dereference of PTR. However, if some
3167 other transformation propagates them into an INDIRECT_REF
3168 expression, we end up with '*(&PTR->FLD)' which is folded
3171 So, if the original code had no other dereferences of PTR,
3172 the aliaser will not create memory tags for it, and when
3173 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3174 memory operations will receive no V_MAY_DEF/VUSE operands.
3176 One solution would be to have count_uses_and_derefs consider
3177 &PTR->FLD a dereference of PTR. But that is wrong, since it
3178 is not really a dereference but an offset calculation.
3180 What we do here is to recognize these special ADDR_EXPR
3181 nodes. Since these expressions are never GIMPLE values (they
3182 are not GIMPLE invariants), they can only appear on the RHS
3183 of an assignment and their base address is always an
3184 INDIRECT_REF expression. */
3185 is_potential_deref = false;
3186 if (TREE_CODE (stmt) == MODIFY_EXPR
3187 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
3188 && !is_gimple_val (TREE_OPERAND (stmt, 1)))
3190 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3191 this represents a potential dereference of PTR. */
3192 tree rhs = TREE_OPERAND (stmt, 1);
3193 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3194 if (TREE_CODE (base) == INDIRECT_REF
3195 && TREE_OPERAND (base, 0) == op)
3196 is_potential_deref = true;
3199 if (num_derefs > 0 || is_potential_deref)
3201 /* Mark OP as dereferenced. In a subsequent pass,
3202 dereferenced pointers that point to a set of
3203 variables will be assigned a name tag to alias
3204 all the variables OP points to. */
3205 pi->is_dereferenced = 1;
3207 /* Keep track of how many time we've dereferenced each
3209 NUM_REFERENCES_INC (v_ann);
3211 /* If this is a store operation, mark OP as being
3212 dereferenced to store, otherwise mark it as being
3213 dereferenced to load. */
3215 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3217 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
3220 if (stmt_escape_type != NO_ESCAPE && num_derefs < num_uses)
3222 /* If STMT is an escape point and STMT contains at
3223 least one direct use of OP, then the value of OP
3224 escapes and so the pointed-to variables need to
3225 be marked call-clobbered. */
3226 pi->value_escapes_p = 1;
3227 pi->escape_mask |= stmt_escape_type;
3229 /* If the statement makes a function call, assume
3230 that pointer OP will be dereferenced in a store
3231 operation inside the called function. */
3232 if (get_call_expr_in (stmt))
3234 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3235 pi->is_dereferenced = 1;
3240 if (TREE_CODE (stmt) == PHI_NODE)
3243 /* Update reference counter for definitions to any
3244 potentially aliased variable. This is used in the alias
3245 grouping heuristics. */
3246 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3248 tree var = SSA_NAME_VAR (op);
3249 var_ann_t ann = var_ann (var);
3250 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3251 if (may_be_aliased (var))
3252 NUM_REFERENCES_INC (ann);
3256 /* Mark variables in V_MAY_DEF operands as being written to. */
3257 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
3259 tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
3260 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3265 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3266 Expressions of the type PTR + CST can be handled in two ways:
3268 1- If the constraint for PTR is ADDRESSOF for a non-structure
3269 variable, then we can use it directly because adding or
3270 subtracting a constant may not alter the original ADDRESSOF
3271 constraint (i.e., pointer arithmetic may not legally go outside
3272 an object's boundaries).
3274 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3275 then if CST is a compile-time constant that can be used as an
3276 offset, we can determine which sub-variable will be pointed-to
3279 Return true if the expression is handled. For any other kind of
3280 expression, return false so that each operand can be added as a
3281 separate constraint by the caller. */
3284 handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr)
3287 struct constraint_expr *c, *c2;
3290 VEC (ce_s, heap) *temp = NULL;
3291 unsigned int rhsoffset = 0;
3293 if (TREE_CODE (expr) != PLUS_EXPR
3294 && TREE_CODE (expr) != MINUS_EXPR)
3297 op0 = TREE_OPERAND (expr, 0);
3298 op1 = TREE_OPERAND (expr, 1);
3300 get_constraint_for (op0, &temp);
3301 if (POINTER_TYPE_P (TREE_TYPE (op0))
3302 && TREE_CODE (op1) == INTEGER_CST
3303 && TREE_CODE (expr) == PLUS_EXPR)
3305 rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
3309 for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
3310 for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
3312 if (c2->type == ADDRESSOF && rhsoffset != 0)
3314 varinfo_t temp = get_varinfo (c2->var);
3316 /* An access one after the end of an array is valid,
3317 so simply punt on accesses we cannot resolve. */
3318 temp = first_vi_for_offset (temp, rhsoffset);
3325 c2->offset = rhsoffset;
3326 process_constraint (new_constraint (*c, *c2));
3329 VEC_free (ce_s, heap, temp);
3335 /* Walk statement T setting up aliasing constraints according to the
3336 references found in T. This function is the main part of the
3337 constraint builder. AI points to auxiliary alias information used
3338 when building alias sets and computing alias grouping heuristics. */
3341 find_func_aliases (tree origt)
3344 VEC(ce_s, heap) *lhsc = NULL;
3345 VEC(ce_s, heap) *rhsc = NULL;
3346 struct constraint_expr *c;
3348 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
3349 t = TREE_OPERAND (t, 0);
3351 /* Now build constraints expressions. */
3352 if (TREE_CODE (t) == PHI_NODE)
3354 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))));
3356 /* Only care about pointers and structures containing
3358 if (could_have_pointers (PHI_RESULT (t)))
3363 /* For a phi node, assign all the arguments to
3365 get_constraint_for (PHI_RESULT (t), &lhsc);
3366 for (i = 0; i < PHI_NUM_ARGS (t); i++)
3369 tree strippedrhs = PHI_ARG_DEF (t, i);
3371 STRIP_NOPS (strippedrhs);
3372 rhstype = TREE_TYPE (strippedrhs);
3373 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
3375 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3377 struct constraint_expr *c2;
3378 while (VEC_length (ce_s, rhsc) > 0)
3380 c2 = VEC_last (ce_s, rhsc);
3381 process_constraint (new_constraint (*c, *c2));
3382 VEC_pop (ce_s, rhsc);
3388 /* In IPA mode, we need to generate constraints to pass call
3389 arguments through their calls. There are two case, either a
3390 modify_expr when we are returning a value, or just a plain
3391 call_expr when we are not. */
3392 else if (in_ipa_mode
3393 && ((TREE_CODE (t) == MODIFY_EXPR
3394 && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR
3395 && !(call_expr_flags (TREE_OPERAND (t, 1))
3396 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
3397 || (TREE_CODE (t) == CALL_EXPR
3398 && !(call_expr_flags (t)
3399 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))))
3408 if (TREE_CODE (t) == MODIFY_EXPR)
3410 lhsop = TREE_OPERAND (t, 0);
3411 rhsop = TREE_OPERAND (t, 1);
3418 decl = get_callee_fndecl (rhsop);
3420 /* If we can directly resolve the function being called, do so.
3421 Otherwise, it must be some sort of indirect expression that
3422 we should still be able to handle. */
3425 varid = get_id_for_tree (decl);
3429 decl = TREE_OPERAND (rhsop, 0);
3430 varid = get_id_for_tree (decl);
3433 /* Assign all the passed arguments to the appropriate incoming
3434 parameters of the function. */
3435 fi = get_varinfo (varid);
3436 arglist = TREE_OPERAND (rhsop, 1);
3438 for (;arglist; arglist = TREE_CHAIN (arglist))
3440 tree arg = TREE_VALUE (arglist);
3441 struct constraint_expr lhs ;
3442 struct constraint_expr *rhsp;
3444 get_constraint_for (arg, &rhsc);
3445 if (TREE_CODE (decl) != FUNCTION_DECL)
3454 lhs.var = first_vi_for_offset (fi, i)->id;
3457 while (VEC_length (ce_s, rhsc) != 0)
3459 rhsp = VEC_last (ce_s, rhsc);
3460 process_constraint (new_constraint (lhs, *rhsp));
3461 VEC_pop (ce_s, rhsc);
3465 /* If we are returning a value, assign it to the result. */
3468 struct constraint_expr rhs;
3469 struct constraint_expr *lhsp;
3472 get_constraint_for (lhsop, &lhsc);
3473 if (TREE_CODE (decl) != FUNCTION_DECL)
3482 rhs.var = first_vi_for_offset (fi, i)->id;
3485 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3486 process_constraint (new_constraint (*lhsp, rhs));
3489 /* Otherwise, just a regular assignment statement. */
3490 else if (TREE_CODE (t) == MODIFY_EXPR)
3492 tree lhsop = TREE_OPERAND (t, 0);
3493 tree rhsop = TREE_OPERAND (t, 1);
3496 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3497 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)
3498 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop))
3499 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE))
3501 do_structure_copy (lhsop, rhsop);
3505 /* Only care about operations with pointers, structures
3506 containing pointers, dereferences, and call expressions. */
3507 if (could_have_pointers (lhsop)
3508 || TREE_CODE (rhsop) == CALL_EXPR)
3510 get_constraint_for (lhsop, &lhsc);
3511 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
3513 /* RHS that consist of unary operations,
3514 exceptional types, or bare decls/constants, get
3515 handled directly by get_constraint_for. */
3517 case tcc_declaration:
3519 case tcc_exceptional:
3520 case tcc_expression:
3525 get_constraint_for (rhsop, &rhsc);
3526 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3528 struct constraint_expr *c2;
3531 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3532 process_constraint (new_constraint (*c, *c2));
3540 /* For pointer arithmetic of the form
3541 PTR + CST, we can simply use PTR's
3542 constraint because pointer arithmetic is
3543 not allowed to go out of bounds. */
3544 if (handle_ptr_arith (lhsc, rhsop))
3549 /* Otherwise, walk each operand. Notice that we
3550 can't use the operand interface because we need
3551 to process expressions other than simple operands
3552 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3554 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
3556 tree op = TREE_OPERAND (rhsop, i);
3559 gcc_assert (VEC_length (ce_s, rhsc) == 0);
3560 get_constraint_for (op, &rhsc);
3561 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3563 struct constraint_expr *c2;
3564 while (VEC_length (ce_s, rhsc) > 0)
3566 c2 = VEC_last (ce_s, rhsc);
3567 process_constraint (new_constraint (*c, *c2));
3568 VEC_pop (ce_s, rhsc);
3577 /* After promoting variables and computing aliasing we will
3578 need to re-scan most statements. FIXME: Try to minimize the
3579 number of statements re-scanned. It's not really necessary to
3580 re-scan *all* statements. */
3581 mark_stmt_modified (origt);
3582 VEC_free (ce_s, heap, rhsc);
3583 VEC_free (ce_s, heap, lhsc);
3587 /* Find the first varinfo in the same variable as START that overlaps with
3589 Effectively, walk the chain of fields for the variable START to find the
3590 first field that overlaps with OFFSET.
3591 Return NULL if we can't find one. */
3594 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3596 varinfo_t curr = start;
3599 /* We may not find a variable in the field list with the actual
3600 offset when when we have glommed a structure to a variable.
3601 In that case, however, offset should still be within the size
3603 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3611 /* Insert the varinfo FIELD into the field list for BASE, at the front
3615 insert_into_field_list (varinfo_t base, varinfo_t field)
3617 varinfo_t prev = base;
3618 varinfo_t curr = base->next;
3624 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3628 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
3630 varinfo_t prev = base;
3631 varinfo_t curr = base->next;
3642 if (field->offset <= curr->offset)
3647 field->next = prev->next;
3652 /* qsort comparison function for two fieldoff's PA and PB */
3655 fieldoff_compare (const void *pa, const void *pb)
3657 const fieldoff_s *foa = (const fieldoff_s *)pa;
3658 const fieldoff_s *fob = (const fieldoff_s *)pb;
3659 HOST_WIDE_INT foasize, fobsize;
3661 if (foa->offset != fob->offset)
3662 return foa->offset - fob->offset;
3664 foasize = TREE_INT_CST_LOW (foa->size);
3665 fobsize = TREE_INT_CST_LOW (fob->size);
3666 return foasize - fobsize;
3669 /* Sort a fieldstack according to the field offset and sizes. */
3671 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3673 qsort (VEC_address (fieldoff_s, fieldstack),
3674 VEC_length (fieldoff_s, fieldstack),
3675 sizeof (fieldoff_s),
3679 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3680 of TYPE onto fieldstack, recording their offsets along the way.
3681 OFFSET is used to keep track of the offset in this entire structure, rather
3682 than just the immediately containing structure. Returns the number
3684 HAS_UNION is set to true if we find a union type as a field of
3688 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
3689 HOST_WIDE_INT offset, bool *has_union)
3694 if (TREE_CODE (type) == COMPLEX_TYPE)
3696 fieldoff_s *real_part, *img_part;
3697 real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3698 real_part->type = TREE_TYPE (type);
3699 real_part->size = TYPE_SIZE (TREE_TYPE (type));
3700 real_part->offset = offset;
3701 real_part->decl = NULL_TREE;
3703 img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3704 img_part->type = TREE_TYPE (type);
3705 img_part->size = TYPE_SIZE (TREE_TYPE (type));
3706 img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
3707 img_part->decl = NULL_TREE;
3712 if (TREE_CODE (type) == ARRAY_TYPE)
3714 tree sz = TYPE_SIZE (type);
3715 tree elsz = TYPE_SIZE (TREE_TYPE (type));
3720 || ! host_integerp (sz, 1)
3721 || TREE_INT_CST_LOW (sz) == 0
3723 || ! host_integerp (elsz, 1)
3724 || TREE_INT_CST_LOW (elsz) == 0)
3727 nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
3728 if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
3731 for (i = 0; i < nr; ++i)
3737 && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
3738 || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
3741 if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
3743 else if (!(pushed = push_fields_onto_fieldstack
3744 (TREE_TYPE (type), fieldstack,
3745 offset + i * TREE_INT_CST_LOW (elsz), has_union)))
3746 /* Empty structures may have actual size, like in C++. So
3747 see if we didn't push any subfields and the size is
3748 nonzero, push the field onto the stack */
3755 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3756 pair->type = TREE_TYPE (type);
3758 pair->decl = NULL_TREE;
3759 pair->offset = offset + i * TREE_INT_CST_LOW (elsz);
3769 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
3770 if (TREE_CODE (field) == FIELD_DECL)
3776 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3777 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3780 if (!var_can_have_subvars (field))
3782 else if (!(pushed = push_fields_onto_fieldstack
3783 (TREE_TYPE (field), fieldstack,
3784 offset + bitpos_of_field (field), has_union))
3785 && DECL_SIZE (field)
3786 && !integer_zerop (DECL_SIZE (field)))
3787 /* Empty structures may have actual size, like in C++. So
3788 see if we didn't push any subfields and the size is
3789 nonzero, push the field onto the stack */
3796 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3797 pair->type = TREE_TYPE (field);
3798 pair->size = DECL_SIZE (field);
3800 pair->offset = offset + bitpos_of_field (field);
3810 /* Create a constraint from ESCAPED_VARS variable to VI. */
3812 make_constraint_from_escaped (varinfo_t vi)
3814 struct constraint_expr lhs, rhs;
3820 rhs.var = escaped_vars_id;
3823 process_constraint (new_constraint (lhs, rhs));
3826 /* Create a constraint to the ESCAPED_VARS variable from constraint
3830 make_constraint_to_escaped (struct constraint_expr rhs)
3832 struct constraint_expr lhs;
3834 lhs.var = escaped_vars_id;
3838 process_constraint (new_constraint (lhs, rhs));
3841 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3842 if it is a varargs function. */
3845 count_num_arguments (tree decl, bool *is_varargs)
3850 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
3854 if (TREE_VALUE (t) == void_type_node)
3864 /* Creation function node for DECL, using NAME, and return the index
3865 of the variable we've created for the function. */
3868 create_function_info_for (tree decl, const char *name)
3870 unsigned int index = VEC_length (varinfo_t, varmap);
3874 bool is_varargs = false;
3876 /* Create the variable info. */
3878 vi = new_var_info (decl, index, name, index);
3883 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3884 insert_id_for_tree (vi->decl, index);
3885 VEC_safe_push (varinfo_t, heap, varmap, vi);
3889 /* If it's varargs, we don't know how many arguments it has, so we
3896 vi->is_unknown_size_var = true;
3901 arg = DECL_ARGUMENTS (decl);
3903 /* Set up variables for each argument. */
3904 for (i = 1; i < vi->fullsize; i++)
3907 const char *newname;
3909 unsigned int newindex;
3910 tree argdecl = decl;
3915 newindex = VEC_length (varinfo_t, varmap);
3916 asprintf (&tempname, "%s.arg%d", name, i-1);
3917 newname = ggc_strdup (tempname);
3920 argvi = new_var_info (argdecl, newindex,newname, newindex);
3921 argvi->decl = argdecl;
3922 VEC_safe_push (varinfo_t, heap, varmap, argvi);
3925 argvi->fullsize = vi->fullsize;
3926 argvi->has_union = false;
3927 insert_into_field_list_sorted (vi, argvi);
3928 stats.total_vars ++;
3931 insert_id_for_tree (arg, newindex);
3932 arg = TREE_CHAIN (arg);
3936 /* Create a variable for the return var. */
3937 if (DECL_RESULT (decl) != NULL
3938 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
3941 const char *newname;
3943 unsigned int newindex;
3944 tree resultdecl = decl;
3948 if (DECL_RESULT (decl))
3949 resultdecl = DECL_RESULT (decl);
3951 newindex = VEC_length (varinfo_t, varmap);
3952 asprintf (&tempname, "%s.result", name);
3953 newname = ggc_strdup (tempname);
3956 resultvi = new_var_info (resultdecl, newindex, newname, newindex);
3957 resultvi->decl = resultdecl;
3958 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
3959 resultvi->offset = i;
3961 resultvi->fullsize = vi->fullsize;
3962 resultvi->has_union = false;
3963 insert_into_field_list_sorted (vi, resultvi);
3964 stats.total_vars ++;
3965 if (DECL_RESULT (decl))
3966 insert_id_for_tree (DECL_RESULT (decl), newindex);
3972 /* Return true if FIELDSTACK contains fields that overlap.
3973 FIELDSTACK is assumed to be sorted by offset. */
3976 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
3978 fieldoff_s *fo = NULL;
3980 HOST_WIDE_INT lastoffset = -1;
3982 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3984 if (fo->offset == lastoffset)
3986 lastoffset = fo->offset;
3991 /* This function is called through walk_tree to walk global
3992 initializers looking for constraints we need to add to the
3996 find_global_initializers (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
3999 varinfo_t vi = (varinfo_t)viv;
4002 switch (TREE_CODE (t))
4004 /* Dereferences and addressofs are the only important things
4005 here, and i don't even remember if dereferences are legal
4006 here in initializers. */
4010 struct constraint_expr *c;
4013 VEC(ce_s, heap) *rhsc = NULL;
4014 get_constraint_for (t, &rhsc);
4015 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4017 struct constraint_expr lhs;
4022 process_constraint (new_constraint (lhs, *c));
4025 VEC_free (ce_s, heap, rhsc);
4029 /* We might not have walked this because we skip
4030 DECL_EXTERNALs during the initial scan. */
4031 if (referenced_vars)
4034 if (referenced_var_check_and_insert (t))
4035 mark_sym_for_renaming (t);
4044 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4045 This will also create any varinfo structures necessary for fields
4049 create_variable_info_for (tree decl, const char *name)
4051 unsigned int index = VEC_length (varinfo_t, varmap);
4053 tree decltype = TREE_TYPE (decl);
4054 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
4055 bool notokay = false;
4057 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
4058 VEC (fieldoff_s,heap) *fieldstack = NULL;
4060 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4061 return create_function_info_for (decl, name);
4063 hasunion = TREE_CODE (decltype) == UNION_TYPE
4064 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
4065 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
4067 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
4070 VEC_free (fieldoff_s, heap, fieldstack);
4076 /* If the variable doesn't have subvars, we may end up needing to
4077 sort the field list and create fake variables for all the
4079 vi = new_var_info (decl, index, name, index);
4082 vi->has_union = hasunion;
4084 || TREE_CODE (declsize) != INTEGER_CST
4085 || TREE_CODE (decltype) == UNION_TYPE
4086 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
4088 vi->is_unknown_size_var = true;
4094 vi->fullsize = TREE_INT_CST_LOW (declsize);
4095 vi->size = vi->fullsize;
4098 insert_id_for_tree (vi->decl, index);
4099 VEC_safe_push (varinfo_t, heap, varmap, vi);
4100 if (is_global && (!flag_whole_program || !in_ipa_mode))
4102 make_constraint_from_escaped (vi);
4104 /* If the variable can't be aliased, there is no point in
4105 putting it in the set of nonlocal vars. */
4106 if (may_be_aliased (vi->decl))
4108 struct constraint_expr rhs;
4110 rhs.type = ADDRESSOF;
4112 make_constraint_to_escaped (rhs);
4115 if (TREE_CODE (decl) != FUNCTION_DECL && DECL_INITIAL (decl))
4117 walk_tree_without_duplicates (&DECL_INITIAL (decl),
4118 find_global_initializers,
4124 if (use_field_sensitive
4126 && !vi->is_unknown_size_var
4127 && var_can_have_subvars (decl)
4128 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4130 unsigned int newindex = VEC_length (varinfo_t, varmap);
4131 fieldoff_s *fo = NULL;
4134 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4137 || TREE_CODE (fo->size) != INTEGER_CST
4145 /* We can't sort them if we have a field with a variable sized type,
4146 which will make notokay = true. In that case, we are going to return
4147 without creating varinfos for the fields anyway, so sorting them is a
4151 sort_fieldstack (fieldstack);
4152 /* Due to some C++ FE issues, like PR 22488, we might end up
4153 what appear to be overlapping fields even though they,
4154 in reality, do not overlap. Until the C++ FE is fixed,
4155 we will simply disable field-sensitivity for these cases. */
4156 notokay = check_for_overlaps (fieldstack);
4160 if (VEC_length (fieldoff_s, fieldstack) != 0)
4161 fo = VEC_index (fieldoff_s, fieldstack, 0);
4163 if (fo == NULL || notokay)
4165 vi->is_unknown_size_var = 1;
4168 VEC_free (fieldoff_s, heap, fieldstack);
4172 vi->size = TREE_INT_CST_LOW (fo->size);
4173 vi->offset = fo->offset;
4174 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4175 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4179 const char *newname = "NULL";
4182 newindex = VEC_length (varinfo_t, varmap);
4186 asprintf (&tempname, "%s.%s",
4187 vi->name, alias_get_name (fo->decl));
4189 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC,
4190 vi->name, fo->offset);
4191 newname = ggc_strdup (tempname);
4194 newvi = new_var_info (decl, newindex, newname, newindex);
4195 newvi->offset = fo->offset;
4196 newvi->size = TREE_INT_CST_LOW (fo->size);
4197 newvi->fullsize = vi->fullsize;
4198 insert_into_field_list (vi, newvi);
4199 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4200 if (is_global && (!flag_whole_program || !in_ipa_mode))
4202 /* If the variable can't be aliased, there is no point in
4203 putting it in the set of nonlocal vars. */
4204 if (may_be_aliased (vi->decl))
4206 struct constraint_expr rhs;
4209 rhs.type = ADDRESSOF;
4211 make_constraint_to_escaped (rhs);
4213 make_constraint_from_escaped (newvi);
4218 VEC_free (fieldoff_s, heap, fieldstack);
4223 /* Print out the points-to solution for VAR to FILE. */
4226 dump_solution_for_var (FILE *file, unsigned int var)
4228 varinfo_t vi = get_varinfo (var);
4232 fprintf (file, "%s = { ", vi->name);
4233 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
4235 fprintf (file, "%s ", get_varinfo (i)->name);
4237 fprintf (file, "}\n");
4240 /* Print the points-to solution for VAR to stdout. */
4243 debug_solution_for_var (unsigned int var)
4245 dump_solution_for_var (stdout, var);
4248 /* Create varinfo structures for all of the variables in the
4249 function for intraprocedural mode. */
4252 intra_create_variable_infos (void)
4255 struct constraint_expr lhs, rhs;
4256 varinfo_t nonlocal_vi;
4258 /* For each incoming pointer argument arg, ARG = ESCAPED_VARS or a
4259 dummy variable if flag_argument_noalias > 2. */
4260 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4263 unsigned int arg_id;
4265 if (!could_have_pointers (t))
4268 arg_id = get_id_for_tree (t);
4270 /* With flag_argument_noalias greater than two means that the incoming
4271 argument cannot alias anything except for itself so create a HEAP
4273 if (POINTER_TYPE_P (TREE_TYPE (t))
4274 && flag_argument_noalias > 2)
4277 tree heapvar = heapvar_lookup (t);
4282 lhs.var = get_id_for_tree (t);
4284 if (heapvar == NULL_TREE)
4286 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4288 get_var_ann (heapvar)->is_heapvar = 1;
4289 DECL_EXTERNAL (heapvar) = 1;
4290 if (referenced_vars)
4291 add_referenced_var (heapvar);
4292 heapvar_insert (t, heapvar);
4294 id = get_id_for_tree (heapvar);
4295 vi = get_varinfo (id);
4296 vi->is_artificial_var = 1;
4297 vi->is_heap_var = 1;
4299 rhs.type = ADDRESSOF;
4301 for (p = get_varinfo (lhs.var); p; p = p->next)
4303 struct constraint_expr temp = lhs;
4305 process_constraint (new_constraint (temp, rhs));
4310 for (p = get_varinfo (arg_id); p; p = p->next)
4311 make_constraint_from_escaped (p);
4315 nonlocal_all = create_nonlocal_var (void_type_node);
4317 /* Create variable info for the nonlocal var if it does not
4319 nonlocal_vars_id = create_variable_info_for (nonlocal_all,
4320 get_name (nonlocal_all));
4321 nonlocal_vi = get_varinfo (nonlocal_vars_id);
4322 nonlocal_vi->is_artificial_var = 1;
4323 nonlocal_vi->is_heap_var = 1;
4324 nonlocal_vi->is_unknown_size_var = 1;
4325 nonlocal_vi->directly_dereferenced = true;
4327 rhs.var = nonlocal_vars_id;
4328 rhs.type = ADDRESSOF;
4331 lhs.var = escaped_vars_id;
4335 process_constraint (new_constraint (lhs, rhs));
4338 /* Set bits in INTO corresponding to the variable uids in solution set
4339 FROM, which came from variable PTR.
4340 For variables that are actually dereferenced, we also use type
4341 based alias analysis to prune the points-to sets. */
4344 set_uids_in_ptset (tree ptr, bitmap into, bitmap from)
4349 unsigned HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr));
4351 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4353 varinfo_t vi = get_varinfo (i);
4354 unsigned HOST_WIDE_INT var_alias_set;
4356 /* The only artificial variables that are allowed in a may-alias
4357 set are heap variables. */
4358 if (vi->is_artificial_var && !vi->is_heap_var)
4361 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
4363 /* Variables containing unions may need to be converted to
4364 their SFT's, because SFT's can have unions and we cannot. */
4365 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
4366 bitmap_set_bit (into, DECL_UID (sv->var));
4368 else if (TREE_CODE (vi->decl) == VAR_DECL
4369 || TREE_CODE (vi->decl) == PARM_DECL)
4371 if (var_can_have_subvars (vi->decl)
4372 && get_subvars_for_var (vi->decl))
4374 /* If VI->DECL is an aggregate for which we created
4375 SFTs, add the SFT corresponding to VI->OFFSET. */
4376 tree sft = get_subvar_at (vi->decl, vi->offset);
4379 var_alias_set = get_alias_set (sft);
4380 if (!vi->directly_dereferenced
4381 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
4382 bitmap_set_bit (into, DECL_UID (sft));
4387 /* Otherwise, just add VI->DECL to the alias set.
4388 Don't type prune artificial vars. */
4389 if (vi->is_artificial_var)
4390 bitmap_set_bit (into, DECL_UID (vi->decl));
4393 var_alias_set = get_alias_set (vi->decl);
4394 if (!vi->directly_dereferenced
4395 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
4396 bitmap_set_bit (into, DECL_UID (vi->decl));
4404 static bool have_alias_info = false;
4406 /* Given a pointer variable P, fill in its points-to set, or return
4407 false if we can't. */
4410 find_what_p_points_to (tree p)
4412 unsigned int id = 0;
4415 if (!have_alias_info)
4418 /* For parameters, get at the points-to set for the actual parm
4420 if (TREE_CODE (p) == SSA_NAME
4421 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4422 && default_def (SSA_NAME_VAR (p)) == p)
4423 lookup_p = SSA_NAME_VAR (p);
4425 if (lookup_id_for_tree (lookup_p, &id))
4427 varinfo_t vi = get_varinfo (id);
4429 if (vi->is_artificial_var)
4432 /* See if this is a field or a structure. */
4433 if (vi->size != vi->fullsize)
4435 /* Nothing currently asks about structure fields directly,
4436 but when they do, we need code here to hand back the
4438 if (!var_can_have_subvars (vi->decl)
4439 || get_subvars_for_var (vi->decl) == NULL)
4444 struct ptr_info_def *pi = get_ptr_info (p);
4448 /* This variable may have been collapsed, let's get the real
4450 vi = get_varinfo (vi->node);
4452 /* Translate artificial variables into SSA_NAME_PTR_INFO
4454 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4456 varinfo_t vi = get_varinfo (i);
4458 if (vi->is_artificial_var)
4460 /* FIXME. READONLY should be handled better so that
4461 flow insensitive aliasing can disregard writable
4463 if (vi->id == nothing_id)
4465 else if (vi->id == anything_id)
4466 pi->pt_anything = 1;
4467 else if (vi->id == readonly_id)
4468 pi->pt_anything = 1;
4469 else if (vi->id == integer_id)
4470 pi->pt_anything = 1;
4471 else if (vi->is_heap_var)
4472 pi->pt_global_mem = 1;
4476 if (pi->pt_anything)
4480 pi->pt_vars = BITMAP_GGC_ALLOC ();
4482 set_uids_in_ptset (vi->decl, pi->pt_vars, vi->solution);
4484 if (bitmap_empty_p (pi->pt_vars))
4496 /* Dump points-to information to OUTFILE. */
4499 dump_sa_points_to_info (FILE *outfile)
4503 fprintf (outfile, "\nPoints-to sets\n\n");
4505 if (dump_flags & TDF_STATS)
4507 fprintf (outfile, "Stats:\n");
4508 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4509 fprintf (outfile, "Statically unified vars: %d\n",
4510 stats.unified_vars_static);
4511 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
4512 fprintf (outfile, "Dynamically unified vars: %d\n",
4513 stats.unified_vars_dynamic);
4514 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4515 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4518 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4519 dump_solution_for_var (outfile, i);
4523 /* Debug points-to information to stderr. */
4526 debug_sa_points_to_info (void)
4528 dump_sa_points_to_info (stderr);
4532 /* Initialize the always-existing constraint variables for NULL
4533 ANYTHING, READONLY, and INTEGER */
4536 init_base_vars (void)
4538 struct constraint_expr lhs, rhs;
4540 /* Create the NULL variable, used to represent that a variable points
4542 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4543 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
4544 insert_id_for_tree (nothing_tree, 0);
4545 var_nothing->is_artificial_var = 1;
4546 var_nothing->offset = 0;
4547 var_nothing->size = ~0;
4548 var_nothing->fullsize = ~0;
4549 var_nothing->is_special_var = 1;
4551 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
4553 /* Create the ANYTHING variable, used to represent that a variable
4554 points to some unknown piece of memory. */
4555 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4556 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
4557 insert_id_for_tree (anything_tree, 1);
4558 var_anything->is_artificial_var = 1;
4559 var_anything->size = ~0;
4560 var_anything->offset = 0;
4561 var_anything->next = NULL;
4562 var_anything->fullsize = ~0;
4563 var_anything->is_special_var = 1;
4566 /* Anything points to anything. This makes deref constraints just
4567 work in the presence of linked list and other p = *p type loops,
4568 by saying that *ANYTHING = ANYTHING. */
4569 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
4571 lhs.var = anything_id;
4573 rhs.type = ADDRESSOF;
4574 rhs.var = anything_id;
4576 var_anything->address_taken = true;
4578 /* This specifically does not use process_constraint because
4579 process_constraint ignores all anything = anything constraints, since all
4580 but this one are redundant. */
4581 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
4583 /* Create the READONLY variable, used to represent that a variable
4584 points to readonly memory. */
4585 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4586 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
4587 var_readonly->is_artificial_var = 1;
4588 var_readonly->offset = 0;
4589 var_readonly->size = ~0;
4590 var_readonly->fullsize = ~0;
4591 var_readonly->next = NULL;
4592 var_readonly->is_special_var = 1;
4593 insert_id_for_tree (readonly_tree, 2);
4595 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4597 /* readonly memory points to anything, in order to make deref
4598 easier. In reality, it points to anything the particular
4599 readonly variable can point to, but we don't track this
4602 lhs.var = readonly_id;
4604 rhs.type = ADDRESSOF;
4605 rhs.var = anything_id;
4608 process_constraint (new_constraint (lhs, rhs));
4610 /* Create the INTEGER variable, used to represent that a variable points
4612 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4613 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
4614 insert_id_for_tree (integer_tree, 3);
4615 var_integer->is_artificial_var = 1;
4616 var_integer->size = ~0;
4617 var_integer->fullsize = ~0;
4618 var_integer->offset = 0;
4619 var_integer->next = NULL;
4620 var_integer->is_special_var = 1;
4622 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
4624 /* INTEGER = ANYTHING, because we don't know where a dereference of
4625 a random integer will point to. */
4627 lhs.var = integer_id;
4629 rhs.type = ADDRESSOF;
4630 rhs.var = anything_id;
4632 process_constraint (new_constraint (lhs, rhs));
4634 /* Create the ESCAPED_VARS variable used to represent variables that
4635 escape this function. */
4636 escaped_vars_tree = create_tmp_var_raw (void_type_node, "ESCAPED_VARS");
4637 var_escaped_vars = new_var_info (escaped_vars_tree, 4, "ESCAPED_VARS", 4);
4638 insert_id_for_tree (escaped_vars_tree, 4);
4639 var_escaped_vars->is_artificial_var = 1;
4640 var_escaped_vars->size = ~0;
4641 var_escaped_vars->fullsize = ~0;
4642 var_escaped_vars->offset = 0;
4643 var_escaped_vars->next = NULL;
4644 escaped_vars_id = 4;
4645 VEC_safe_push (varinfo_t, heap, varmap, var_escaped_vars);
4647 /* ESCAPED_VARS = *ESCAPED_VARS */
4649 lhs.var = escaped_vars_id;
4652 rhs.var = escaped_vars_id;
4654 process_constraint (new_constraint (lhs, rhs));
4658 /* Initialize things necessary to perform PTA */
4661 init_alias_vars (void)
4663 bitmap_obstack_initialize (&ptabitmap_obstack);
4664 bitmap_obstack_initialize (&predbitmap_obstack);
4666 constraint_pool = create_alloc_pool ("Constraint pool",
4667 sizeof (struct constraint), 30);
4668 variable_info_pool = create_alloc_pool ("Variable info pool",
4669 sizeof (struct variable_info), 30);
4670 constraint_edge_pool = create_alloc_pool ("Constraint edges",
4671 sizeof (struct constraint_edge), 30);
4673 constraints = VEC_alloc (constraint_t, heap, 8);
4674 varmap = VEC_alloc (varinfo_t, heap, 8);
4675 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
4676 memset (&stats, 0, sizeof (stats));
4681 /* Given a statement STMT, generate necessary constraints to
4682 escaped_vars for the escaping variables. */
4685 find_escape_constraints (tree stmt)
4687 enum escape_type stmt_escape_type = is_escape_site (stmt);
4689 VEC(ce_s, heap) *rhsc = NULL;
4690 struct constraint_expr *c;
4693 if (stmt_escape_type == NO_ESCAPE)
4696 if (TREE_CODE (stmt) == RETURN_EXPR)
4698 /* Returns are either bare, with an embedded MODIFY_EXPR, or
4699 just a plain old expression. */
4700 if (!TREE_OPERAND (stmt, 0))
4702 if (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
4703 rhs = TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
4705 rhs = TREE_OPERAND (stmt, 0);
4707 get_constraint_for (rhs, &rhsc);
4708 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4709 make_constraint_to_escaped (*c);
4710 VEC_free (ce_s, heap, rhsc);
4713 else if (TREE_CODE (stmt) == ASM_EXPR)
4715 /* Whatever the inputs of the ASM are, escape. */
4718 for (arg = ASM_INPUTS (stmt); arg; arg = TREE_CHAIN (arg))
4721 get_constraint_for (TREE_VALUE (arg), &rhsc);
4722 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4723 make_constraint_to_escaped (*c);
4724 VEC_free (ce_s, heap, rhsc);
4728 else if (TREE_CODE (stmt) == CALL_EXPR
4729 || (TREE_CODE (stmt) == MODIFY_EXPR
4730 && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR))
4732 /* Calls cause all of the arguments passed in to escape. */
4735 if (TREE_CODE (stmt) == MODIFY_EXPR)
4736 stmt = TREE_OPERAND (stmt, 1);
4737 for (arg = TREE_OPERAND (stmt, 1); arg; arg = TREE_CHAIN (arg))
4739 if (POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arg))))
4742 get_constraint_for (TREE_VALUE (arg), &rhsc);
4743 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4744 make_constraint_to_escaped (*c);
4745 VEC_free (ce_s, heap, rhsc);
4752 gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
4755 gcc_assert (stmt_escape_type == ESCAPE_BAD_CAST
4756 || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL
4757 || stmt_escape_type == ESCAPE_UNKNOWN);
4758 rhs = TREE_OPERAND (stmt, 1);
4760 /* Look through casts for the real escaping variable.
4761 Constants don't really escape, so ignore them.
4762 Otherwise, whatever escapes must be on our RHS. */
4763 if (TREE_CODE (rhs) == NOP_EXPR
4764 || TREE_CODE (rhs) == CONVERT_EXPR
4765 || TREE_CODE (rhs) == NON_LVALUE_EXPR)
4767 get_constraint_for (TREE_OPERAND (rhs, 0), &rhsc);
4769 else if (CONSTANT_CLASS_P (rhs))
4773 get_constraint_for (rhs, &rhsc);
4775 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4776 make_constraint_to_escaped (*c);
4777 VEC_free (ce_s, heap, rhsc);
4780 /* Create points-to sets for the current function. See the comments
4781 at the start of the file for an algorithmic overview. */
4784 compute_points_to_sets (struct alias_info *ai)
4788 timevar_push (TV_TREE_PTA);
4792 intra_create_variable_infos ();
4794 /* Now walk all statements and derive aliases. */
4797 block_stmt_iterator bsi;
4800 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4802 if (is_gimple_reg (PHI_RESULT (phi)))
4804 find_func_aliases (phi);
4805 /* Update various related attributes like escaped
4806 addresses, pointer dereferences for loads and stores.
4807 This is used when creating name tags and alias
4809 update_alias_info (phi, ai);
4813 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4815 tree stmt = bsi_stmt (bsi);
4817 find_func_aliases (stmt);
4818 find_escape_constraints (stmt);
4819 /* Update various related attributes like escaped
4820 addresses, pointer dereferences for loads and stores.
4821 This is used when creating name tags and alias
4823 update_alias_info (stmt, ai);
4827 build_constraint_graph ();
4831 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4832 dump_constraints (dump_file);
4837 "\nCollapsing static cycles and doing variable "
4840 find_and_collapse_graph_cycles (graph, false);
4841 perform_var_substitution (graph);
4844 fprintf (dump_file, "\nSolving graph:\n");
4846 solve_graph (graph);
4849 dump_sa_points_to_info (dump_file);
4851 have_alias_info = true;
4853 timevar_pop (TV_TREE_PTA);
4857 /* Delete created points-to sets. */
4860 delete_points_to_sets (void)
4865 htab_delete (id_for_tree);
4866 bitmap_obstack_release (&ptabitmap_obstack);
4867 bitmap_obstack_release (&predbitmap_obstack);
4868 VEC_free (constraint_t, heap, constraints);
4870 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4872 /* Nonlocal vars may add more varinfos. */
4873 if (i >= graph_size)
4876 VEC_free (constraint_edge_t, heap, graph->succs[i]);
4877 VEC_free (constraint_edge_t, heap, graph->preds[i]);
4878 VEC_free (constraint_t, heap, v->complex);
4880 free (graph->zero_weight_preds);
4881 free (graph->zero_weight_succs);
4882 free (graph->succs);
4883 free (graph->preds);
4886 VEC_free (varinfo_t, heap, varmap);
4887 free_alloc_pool (variable_info_pool);
4888 free_alloc_pool (constraint_pool);
4889 free_alloc_pool (constraint_edge_pool);
4891 have_alias_info = false;
4894 /* Return true if we should execute IPA PTA. */
4898 return (flag_unit_at_a_time != 0
4900 /* Don't bother doing anything if the program has errors. */
4901 && !(errorcount || sorrycount));
4904 /* Execute the driver for IPA PTA. */
4906 ipa_pta_execute (void)
4908 struct cgraph_node *node;
4910 init_alias_heapvars ();
4913 for (node = cgraph_nodes; node; node = node->next)
4915 if (!node->analyzed || cgraph_is_master_clone (node))
4919 varid = create_function_info_for (node->decl,
4920 cgraph_node_name (node));
4921 if (node->local.externally_visible)
4923 varinfo_t fi = get_varinfo (varid);
4924 for (; fi; fi = fi->next)
4925 make_constraint_from_escaped (fi);
4929 for (node = cgraph_nodes; node; node = node->next)
4931 if (node->analyzed && cgraph_is_master_clone (node))
4933 struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
4935 tree old_func_decl = current_function_decl;
4938 "Generating constraints for %s\n",
4939 cgraph_node_name (node));
4941 current_function_decl = node->decl;
4943 FOR_EACH_BB_FN (bb, cfun)
4945 block_stmt_iterator bsi;
4948 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4950 if (is_gimple_reg (PHI_RESULT (phi)))
4952 find_func_aliases (phi);
4956 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4958 tree stmt = bsi_stmt (bsi);
4959 find_func_aliases (stmt);
4962 current_function_decl = old_func_decl;
4967 /* Make point to anything. */
4971 build_constraint_graph ();
4975 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4976 dump_constraints (dump_file);
4981 "\nCollapsing static cycles and doing variable "
4984 find_and_collapse_graph_cycles (graph, false);
4985 perform_var_substitution (graph);
4988 fprintf (dump_file, "\nSolving graph:\n");
4990 solve_graph (graph);
4993 dump_sa_points_to_info (dump_file);
4995 delete_alias_heapvars ();
4996 delete_points_to_sets ();
5000 struct tree_opt_pass pass_ipa_pta =
5003 gate_ipa_pta, /* gate */
5004 ipa_pta_execute, /* execute */
5007 0, /* static_pass_number */
5008 TV_IPA_PTA, /* tv_id */
5009 0, /* properties_required */
5010 0, /* properties_provided */
5011 0, /* properties_destroyed */
5012 0, /* todo_flags_start */
5013 0, /* todo_flags_finish */
5017 /* Initialize the heapvar for statement mapping. */
5019 init_alias_heapvars (void)
5021 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5023 nonlocal_all = NULL_TREE;
5027 delete_alias_heapvars (void)
5029 nonlocal_all = NULL_TREE;
5030 htab_delete (heapvar_for_stmt);
5034 #include "gt-tree-ssa-structalias.h"