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 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
2331 vi->address_taken = true;
2333 VEC_safe_push (constraint_t, heap, constraints, t);
2337 if (lhs.type != DEREF && rhs.type == DEREF)
2338 get_varinfo (lhs.var)->indirect_target = true;
2339 VEC_safe_push (constraint_t, heap, constraints, t);
2343 /* Return true if T is a variable of a type that could contain
2347 could_have_pointers (tree t)
2349 tree type = TREE_TYPE (t);
2351 if (POINTER_TYPE_P (type) || AGGREGATE_TYPE_P (type)
2352 || TREE_CODE (type) == COMPLEX_TYPE)
2357 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2360 static unsigned HOST_WIDE_INT
2361 bitpos_of_field (const tree fdecl)
2364 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
2365 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
2368 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
2369 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
2373 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2374 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2377 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
2378 const unsigned HOST_WIDE_INT fieldsize,
2379 const unsigned HOST_WIDE_INT accesspos,
2380 const unsigned HOST_WIDE_INT accesssize)
2382 if (fieldpos == accesspos && fieldsize == accesssize)
2384 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
2386 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2392 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2395 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results)
2398 HOST_WIDE_INT bitsize = -1;
2399 HOST_WIDE_INT bitmaxsize = -1;
2400 HOST_WIDE_INT bitpos;
2402 struct constraint_expr *result;
2403 unsigned int beforelength = VEC_length (ce_s, *results);
2405 /* Some people like to do cute things like take the address of
2408 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2409 forzero = TREE_OPERAND (forzero, 0);
2411 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2413 struct constraint_expr temp;
2416 temp.var = integer_id;
2418 VEC_safe_push (ce_s, heap, *results, &temp);
2422 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2424 /* String constants are readonly, so there is nothing to really do
2426 if (TREE_CODE (t) == STRING_CST)
2429 get_constraint_for (t, results);
2430 result = VEC_last (ce_s, *results);
2431 result->offset = bitpos;
2433 gcc_assert (beforelength + 1 == VEC_length (ce_s, *results));
2435 /* This can also happen due to weird offsetof type macros. */
2436 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2437 result->type = SCALAR;
2439 if (result->type == SCALAR)
2441 /* In languages like C, you can access one past the end of an
2442 array. You aren't allowed to dereference it, so we can
2443 ignore this constraint. When we handle pointer subtraction,
2444 we may have to do something cute here. */
2446 if (result->offset < get_varinfo (result->var)->fullsize
2449 /* It's also not true that the constraint will actually start at the
2450 right offset, it may start in some padding. We only care about
2451 setting the constraint to the first actual field it touches, so
2454 for (curr = get_varinfo (result->var); curr; curr = curr->next)
2456 if (offset_overlaps_with_access (curr->offset, curr->size,
2457 result->offset, bitmaxsize))
2459 result->var = curr->id;
2463 /* assert that we found *some* field there. The user couldn't be
2464 accessing *only* padding. */
2465 /* Still the user could access one past the end of an array
2466 embedded in a struct resulting in accessing *only* padding. */
2467 gcc_assert (curr || ref_contains_array_ref (orig_t));
2469 else if (bitmaxsize == 0)
2471 if (dump_file && (dump_flags & TDF_DETAILS))
2472 fprintf (dump_file, "Access to zero-sized part of variable,"
2476 if (dump_file && (dump_flags & TDF_DETAILS))
2477 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2484 /* Dereference the constraint expression CONS, and return the result.
2485 DEREF (ADDRESSOF) = SCALAR
2486 DEREF (SCALAR) = DEREF
2487 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2488 This is needed so that we can handle dereferencing DEREF constraints. */
2491 do_deref (VEC (ce_s, heap) **constraints)
2493 struct constraint_expr *c;
2495 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2497 if (c->type == SCALAR)
2499 else if (c->type == ADDRESSOF)
2501 else if (c->type == DEREF)
2503 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
2504 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2505 process_constraint (new_constraint (tmplhs, *c));
2506 c->var = tmplhs.var;
2513 /* Create a nonlocal variable of TYPE to represent nonlocals we can
2517 create_nonlocal_var (tree type)
2519 tree nonlocal = create_tmp_var_raw (type, "NONLOCAL");
2521 if (referenced_vars)
2522 add_referenced_var (nonlocal);
2524 DECL_EXTERNAL (nonlocal) = 1;
2528 /* Given a tree T, return the constraint expression for it. */
2531 get_constraint_for (tree t, VEC (ce_s, heap) **results)
2533 struct constraint_expr temp;
2535 /* x = integer is all glommed to a single variable, which doesn't
2536 point to anything by itself. That is, of course, unless it is an
2537 integer constant being treated as a pointer, in which case, we
2538 will return that this is really the addressof anything. This
2539 happens below, since it will fall into the default case. The only
2540 case we know something about an integer treated like a pointer is
2541 when it is the NULL pointer, and then we just say it points to
2543 if (TREE_CODE (t) == INTEGER_CST
2544 && !POINTER_TYPE_P (TREE_TYPE (t)))
2546 temp.var = integer_id;
2549 VEC_safe_push (ce_s, heap, *results, &temp);
2552 else if (TREE_CODE (t) == INTEGER_CST
2553 && integer_zerop (t))
2555 temp.var = nothing_id;
2556 temp.type = ADDRESSOF;
2558 VEC_safe_push (ce_s, heap, *results, &temp);
2562 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2564 case tcc_expression:
2566 switch (TREE_CODE (t))
2570 struct constraint_expr *c;
2572 tree exp = TREE_OPERAND (t, 0);
2573 tree pttype = TREE_TYPE (TREE_TYPE (t));
2575 get_constraint_for (exp, results);
2576 /* Make sure we capture constraints to all elements
2578 if ((handled_component_p (exp)
2579 && ref_contains_array_ref (exp))
2580 || TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE)
2582 struct constraint_expr *origrhs;
2584 struct constraint_expr tmp;
2586 if (VEC_length (ce_s, *results) == 0)
2589 gcc_assert (VEC_length (ce_s, *results) == 1);
2590 origrhs = VEC_last (ce_s, *results);
2592 VEC_pop (ce_s, *results);
2593 origvar = get_varinfo (origrhs->var);
2594 for (; origvar; origvar = origvar->next)
2596 tmp.var = origvar->id;
2597 VEC_safe_push (ce_s, heap, *results, &tmp);
2600 else if (VEC_length (ce_s, *results) == 1
2601 && (AGGREGATE_TYPE_P (pttype)
2602 || TREE_CODE (pttype) == COMPLEX_TYPE))
2604 struct constraint_expr *origrhs;
2606 struct constraint_expr tmp;
2608 gcc_assert (VEC_length (ce_s, *results) == 1);
2609 origrhs = VEC_last (ce_s, *results);
2611 VEC_pop (ce_s, *results);
2612 origvar = get_varinfo (origrhs->var);
2613 for (; origvar; origvar = origvar->next)
2615 tmp.var = origvar->id;
2616 VEC_safe_push (ce_s, heap, *results, &tmp);
2620 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2622 if (c->type == DEREF)
2625 c->type = ADDRESSOF;
2631 /* XXX: In interprocedural mode, if we didn't have the
2632 body, we would need to do *each pointer argument =
2634 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2637 tree heapvar = heapvar_lookup (t);
2639 if (heapvar == NULL)
2641 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2642 DECL_EXTERNAL (heapvar) = 1;
2643 get_var_ann (heapvar)->is_heapvar = 1;
2644 if (referenced_vars)
2645 add_referenced_var (heapvar);
2646 heapvar_insert (t, heapvar);
2649 temp.var = create_variable_info_for (heapvar,
2650 alias_get_name (heapvar));
2652 vi = get_varinfo (temp.var);
2653 vi->is_artificial_var = 1;
2654 vi->is_heap_var = 1;
2655 temp.type = ADDRESSOF;
2657 VEC_safe_push (ce_s, heap, *results, &temp);
2662 temp.var = escaped_vars_id;
2665 VEC_safe_push (ce_s, heap, *results, &temp);
2671 temp.type = ADDRESSOF;
2672 temp.var = anything_id;
2674 VEC_safe_push (ce_s, heap, *results, &temp);
2681 switch (TREE_CODE (t))
2685 get_constraint_for (TREE_OPERAND (t, 0), results);
2690 case ARRAY_RANGE_REF:
2692 get_constraint_for_component_ref (t, results);
2696 temp.type = ADDRESSOF;
2697 temp.var = anything_id;
2699 VEC_safe_push (ce_s, heap, *results, &temp);
2706 switch (TREE_CODE (t))
2710 case NON_LVALUE_EXPR:
2712 tree op = TREE_OPERAND (t, 0);
2714 /* Cast from non-pointer to pointers are bad news for us.
2715 Anything else, we see through */
2716 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2717 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2719 get_constraint_for (op, results);
2727 temp.type = ADDRESSOF;
2728 temp.var = anything_id;
2730 VEC_safe_push (ce_s, heap, *results, &temp);
2735 case tcc_exceptional:
2737 switch (TREE_CODE (t))
2741 get_constraint_for (PHI_RESULT (t), results);
2747 struct constraint_expr temp;
2748 temp = get_constraint_exp_from_ssa_var (t);
2749 VEC_safe_push (ce_s, heap, *results, &temp);
2755 temp.type = ADDRESSOF;
2756 temp.var = anything_id;
2758 VEC_safe_push (ce_s, heap, *results, &temp);
2763 case tcc_declaration:
2765 struct constraint_expr temp;
2766 temp = get_constraint_exp_from_ssa_var (t);
2767 VEC_safe_push (ce_s, heap, *results, &temp);
2772 temp.type = ADDRESSOF;
2773 temp.var = anything_id;
2775 VEC_safe_push (ce_s, heap, *results, &temp);
2782 /* Handle the structure copy case where we have a simple structure copy
2783 between LHS and RHS that is of SIZE (in bits)
2785 For each field of the lhs variable (lhsfield)
2786 For each field of the rhs variable at lhsfield.offset (rhsfield)
2787 add the constraint lhsfield = rhsfield
2789 If we fail due to some kind of type unsafety or other thing we
2790 can't handle, return false. We expect the caller to collapse the
2791 variable in that case. */
2794 do_simple_structure_copy (const struct constraint_expr lhs,
2795 const struct constraint_expr rhs,
2796 const unsigned HOST_WIDE_INT size)
2798 varinfo_t p = get_varinfo (lhs.var);
2799 unsigned HOST_WIDE_INT pstart, last;
2801 last = p->offset + size;
2802 for (; p && p->offset < last; p = p->next)
2805 struct constraint_expr templhs = lhs;
2806 struct constraint_expr temprhs = rhs;
2807 unsigned HOST_WIDE_INT fieldoffset;
2809 templhs.var = p->id;
2810 q = get_varinfo (temprhs.var);
2811 fieldoffset = p->offset - pstart;
2812 q = first_vi_for_offset (q, q->offset + fieldoffset);
2815 temprhs.var = q->id;
2816 process_constraint (new_constraint (templhs, temprhs));
2822 /* Handle the structure copy case where we have a structure copy between a
2823 aggregate on the LHS and a dereference of a pointer on the RHS
2824 that is of SIZE (in bits)
2826 For each field of the lhs variable (lhsfield)
2827 rhs.offset = lhsfield->offset
2828 add the constraint lhsfield = rhs
2832 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2833 const struct constraint_expr rhs,
2834 const unsigned HOST_WIDE_INT size)
2836 varinfo_t p = get_varinfo (lhs.var);
2837 unsigned HOST_WIDE_INT pstart,last;
2839 last = p->offset + size;
2841 for (; p && p->offset < last; p = p->next)
2844 struct constraint_expr templhs = lhs;
2845 struct constraint_expr temprhs = rhs;
2846 unsigned HOST_WIDE_INT fieldoffset;
2849 if (templhs.type == SCALAR)
2850 templhs.var = p->id;
2852 templhs.offset = p->offset;
2854 q = get_varinfo (temprhs.var);
2855 fieldoffset = p->offset - pstart;
2856 temprhs.offset += fieldoffset;
2857 process_constraint (new_constraint (templhs, temprhs));
2861 /* Handle the structure copy case where we have a structure copy
2862 between a aggregate on the RHS and a dereference of a pointer on
2863 the LHS that is of SIZE (in bits)
2865 For each field of the rhs variable (rhsfield)
2866 lhs.offset = rhsfield->offset
2867 add the constraint lhs = rhsfield
2871 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2872 const struct constraint_expr rhs,
2873 const unsigned HOST_WIDE_INT size)
2875 varinfo_t p = get_varinfo (rhs.var);
2876 unsigned HOST_WIDE_INT pstart,last;
2878 last = p->offset + size;
2880 for (; p && p->offset < last; p = p->next)
2883 struct constraint_expr templhs = lhs;
2884 struct constraint_expr temprhs = rhs;
2885 unsigned HOST_WIDE_INT fieldoffset;
2888 if (temprhs.type == SCALAR)
2889 temprhs.var = p->id;
2891 temprhs.offset = p->offset;
2893 q = get_varinfo (templhs.var);
2894 fieldoffset = p->offset - pstart;
2895 templhs.offset += fieldoffset;
2896 process_constraint (new_constraint (templhs, temprhs));
2900 /* Sometimes, frontends like to give us bad type information. This
2901 function will collapse all the fields from VAR to the end of VAR,
2902 into VAR, so that we treat those fields as a single variable.
2903 We return the variable they were collapsed into. */
2906 collapse_rest_of_var (unsigned int var)
2908 varinfo_t currvar = get_varinfo (var);
2911 for (field = currvar->next; field; field = field->next)
2914 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
2915 field->name, currvar->name);
2917 gcc_assert (!field->collapsed_to);
2918 field->collapsed_to = currvar;
2921 currvar->next = NULL;
2922 currvar->size = currvar->fullsize - currvar->offset;
2927 /* Handle aggregate copies by expanding into copies of the respective
2928 fields of the structures. */
2931 do_structure_copy (tree lhsop, tree rhsop)
2933 struct constraint_expr lhs, rhs, tmp;
2934 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
2936 unsigned HOST_WIDE_INT lhssize;
2937 unsigned HOST_WIDE_INT rhssize;
2939 get_constraint_for (lhsop, &lhsc);
2940 get_constraint_for (rhsop, &rhsc);
2941 gcc_assert (VEC_length (ce_s, lhsc) == 1);
2942 gcc_assert (VEC_length (ce_s, rhsc) == 1);
2943 lhs = *(VEC_last (ce_s, lhsc));
2944 rhs = *(VEC_last (ce_s, rhsc));
2946 VEC_free (ce_s, heap, lhsc);
2947 VEC_free (ce_s, heap, rhsc);
2949 /* If we have special var = x, swap it around. */
2950 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2957 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2958 possible it's something we could handle. However, most cases falling
2959 into this are dealing with transparent unions, which are slightly
2961 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2963 rhs.type = ADDRESSOF;
2964 rhs.var = anything_id;
2967 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2968 that special var. */
2969 if (rhs.var <= integer_id)
2971 for (p = get_varinfo (lhs.var); p; p = p->next)
2973 struct constraint_expr templhs = lhs;
2974 struct constraint_expr temprhs = rhs;
2976 if (templhs.type == SCALAR )
2977 templhs.var = p->id;
2979 templhs.offset += p->offset;
2980 process_constraint (new_constraint (templhs, temprhs));
2985 tree rhstype = TREE_TYPE (rhsop);
2986 tree lhstype = TREE_TYPE (lhsop);
2990 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
2991 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
2993 /* If we have a variably sized types on the rhs or lhs, and a deref
2994 constraint, add the constraint, lhsconstraint = &ANYTHING.
2995 This is conservatively correct because either the lhs is an unknown
2996 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2997 constraint, and every variable it can point to must be unknown sized
2998 anyway, so we don't need to worry about fields at all. */
2999 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
3000 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
3002 rhs.var = anything_id;
3003 rhs.type = ADDRESSOF;
3005 process_constraint (new_constraint (lhs, rhs));
3009 /* The size only really matters insofar as we don't set more or less of
3010 the variable. If we hit an unknown size var, the size should be the
3011 whole darn thing. */
3012 if (get_varinfo (rhs.var)->is_unknown_size_var)
3015 rhssize = TREE_INT_CST_LOW (rhstypesize);
3017 if (get_varinfo (lhs.var)->is_unknown_size_var)
3020 lhssize = TREE_INT_CST_LOW (lhstypesize);
3023 if (rhs.type == SCALAR && lhs.type == SCALAR)
3025 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
3027 lhs.var = collapse_rest_of_var (lhs.var);
3028 rhs.var = collapse_rest_of_var (rhs.var);
3033 process_constraint (new_constraint (lhs, rhs));
3036 else if (lhs.type != DEREF && rhs.type == DEREF)
3037 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3038 else if (lhs.type == DEREF && rhs.type != DEREF)
3039 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3042 tree pointedtotype = lhstype;
3045 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3046 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
3047 do_structure_copy (tmpvar, rhsop);
3048 do_structure_copy (lhsop, tmpvar);
3053 /* Update related alias information kept in AI. This is used when
3054 building name tags, alias sets and deciding grouping heuristics.
3055 STMT is the statement to process. This function also updates
3056 ADDRESSABLE_VARS. */
3059 update_alias_info (tree stmt, struct alias_info *ai)
3062 use_operand_p use_p;
3064 enum escape_type stmt_escape_type = is_escape_site (stmt);
3067 if (stmt_escape_type == ESCAPE_TO_CALL
3068 || stmt_escape_type == ESCAPE_TO_PURE_CONST)
3070 ai->num_calls_found++;
3071 if (stmt_escape_type == ESCAPE_TO_PURE_CONST)
3072 ai->num_pure_const_calls_found++;
3075 /* Mark all the variables whose address are taken by the statement. */
3076 addr_taken = addresses_taken (stmt);
3079 bitmap_ior_into (addressable_vars, addr_taken);
3081 /* If STMT is an escape point, all the addresses taken by it are
3083 if (stmt_escape_type != NO_ESCAPE)
3088 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
3090 tree rvar = referenced_var (i);
3091 if (!unmodifiable_var_p (rvar))
3092 mark_call_clobbered (rvar, stmt_escape_type);
3097 /* Process each operand use. If an operand may be aliased, keep
3098 track of how many times it's being used. For pointers, determine
3099 whether they are dereferenced by the statement, or whether their
3100 value escapes, etc. */
3101 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
3105 struct ptr_info_def *pi;
3106 bool is_store, is_potential_deref;
3107 unsigned num_uses, num_derefs;
3109 op = USE_FROM_PTR (use_p);
3111 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
3112 to the set of addressable variables. */
3113 if (TREE_CODE (op) == ADDR_EXPR)
3115 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
3117 /* PHI nodes don't have annotations for pinning the set
3118 of addresses taken, so we collect them here.
3120 FIXME, should we allow PHI nodes to have annotations
3121 so that they can be treated like regular statements?
3122 Currently, they are treated as second-class
3124 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
3128 /* Ignore constants. */
3129 if (TREE_CODE (op) != SSA_NAME)
3132 var = SSA_NAME_VAR (op);
3133 v_ann = var_ann (var);
3135 /* The base variable of an ssa name must be a GIMPLE register, and thus
3136 it cannot be aliased. */
3137 gcc_assert (!may_be_aliased (var));
3139 /* We are only interested in pointers. */
3140 if (!POINTER_TYPE_P (TREE_TYPE (op)))
3143 pi = get_ptr_info (op);
3145 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3146 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
3148 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
3149 VEC_safe_push (tree, heap, ai->processed_ptrs, op);
3152 /* If STMT is a PHI node, then it will not have pointer
3153 dereferences and it will not be an escape point. */
3154 if (TREE_CODE (stmt) == PHI_NODE)
3157 /* Determine whether OP is a dereferenced pointer, and if STMT
3158 is an escape point, whether OP escapes. */
3159 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
3161 /* Handle a corner case involving address expressions of the
3162 form '&PTR->FLD'. The problem with these expressions is that
3163 they do not represent a dereference of PTR. However, if some
3164 other transformation propagates them into an INDIRECT_REF
3165 expression, we end up with '*(&PTR->FLD)' which is folded
3168 So, if the original code had no other dereferences of PTR,
3169 the aliaser will not create memory tags for it, and when
3170 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3171 memory operations will receive no V_MAY_DEF/VUSE operands.
3173 One solution would be to have count_uses_and_derefs consider
3174 &PTR->FLD a dereference of PTR. But that is wrong, since it
3175 is not really a dereference but an offset calculation.
3177 What we do here is to recognize these special ADDR_EXPR
3178 nodes. Since these expressions are never GIMPLE values (they
3179 are not GIMPLE invariants), they can only appear on the RHS
3180 of an assignment and their base address is always an
3181 INDIRECT_REF expression. */
3182 is_potential_deref = false;
3183 if (TREE_CODE (stmt) == MODIFY_EXPR
3184 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
3185 && !is_gimple_val (TREE_OPERAND (stmt, 1)))
3187 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3188 this represents a potential dereference of PTR. */
3189 tree rhs = TREE_OPERAND (stmt, 1);
3190 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3191 if (TREE_CODE (base) == INDIRECT_REF
3192 && TREE_OPERAND (base, 0) == op)
3193 is_potential_deref = true;
3196 if (num_derefs > 0 || is_potential_deref)
3198 /* Mark OP as dereferenced. In a subsequent pass,
3199 dereferenced pointers that point to a set of
3200 variables will be assigned a name tag to alias
3201 all the variables OP points to. */
3202 pi->is_dereferenced = 1;
3204 /* Keep track of how many time we've dereferenced each
3206 NUM_REFERENCES_INC (v_ann);
3208 /* If this is a store operation, mark OP as being
3209 dereferenced to store, otherwise mark it as being
3210 dereferenced to load. */
3212 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3214 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
3217 if (stmt_escape_type != NO_ESCAPE && num_derefs < num_uses)
3219 /* If STMT is an escape point and STMT contains at
3220 least one direct use of OP, then the value of OP
3221 escapes and so the pointed-to variables need to
3222 be marked call-clobbered. */
3223 pi->value_escapes_p = 1;
3224 pi->escape_mask |= stmt_escape_type;
3226 /* If the statement makes a function call, assume
3227 that pointer OP will be dereferenced in a store
3228 operation inside the called function. */
3229 if (get_call_expr_in (stmt))
3231 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3232 pi->is_dereferenced = 1;
3237 if (TREE_CODE (stmt) == PHI_NODE)
3240 /* Update reference counter for definitions to any
3241 potentially aliased variable. This is used in the alias
3242 grouping heuristics. */
3243 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3245 tree var = SSA_NAME_VAR (op);
3246 var_ann_t ann = var_ann (var);
3247 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3248 if (may_be_aliased (var))
3249 NUM_REFERENCES_INC (ann);
3253 /* Mark variables in V_MAY_DEF operands as being written to. */
3254 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
3256 tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
3257 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3262 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3263 Expressions of the type PTR + CST can be handled in two ways:
3265 1- If the constraint for PTR is ADDRESSOF for a non-structure
3266 variable, then we can use it directly because adding or
3267 subtracting a constant may not alter the original ADDRESSOF
3268 constraint (i.e., pointer arithmetic may not legally go outside
3269 an object's boundaries).
3271 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3272 then if CST is a compile-time constant that can be used as an
3273 offset, we can determine which sub-variable will be pointed-to
3276 Return true if the expression is handled. For any other kind of
3277 expression, return false so that each operand can be added as a
3278 separate constraint by the caller. */
3281 handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr)
3284 struct constraint_expr *c, *c2;
3287 VEC (ce_s, heap) *temp = NULL;
3288 unsigned int rhsoffset = 0;
3290 if (TREE_CODE (expr) != PLUS_EXPR
3291 && TREE_CODE (expr) != MINUS_EXPR)
3294 op0 = TREE_OPERAND (expr, 0);
3295 op1 = TREE_OPERAND (expr, 1);
3297 get_constraint_for (op0, &temp);
3298 if (POINTER_TYPE_P (TREE_TYPE (op0))
3299 && TREE_CODE (op1) == INTEGER_CST
3300 && TREE_CODE (expr) == PLUS_EXPR)
3302 rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
3306 for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
3307 for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
3309 if (c2->type == ADDRESSOF && rhsoffset != 0)
3311 varinfo_t temp = get_varinfo (c2->var);
3313 /* An access one after the end of an array is valid,
3314 so simply punt on accesses we cannot resolve. */
3315 temp = first_vi_for_offset (temp, rhsoffset);
3322 c2->offset = rhsoffset;
3323 process_constraint (new_constraint (*c, *c2));
3326 VEC_free (ce_s, heap, temp);
3332 /* Walk statement T setting up aliasing constraints according to the
3333 references found in T. This function is the main part of the
3334 constraint builder. AI points to auxiliary alias information used
3335 when building alias sets and computing alias grouping heuristics. */
3338 find_func_aliases (tree origt)
3341 VEC(ce_s, heap) *lhsc = NULL;
3342 VEC(ce_s, heap) *rhsc = NULL;
3343 struct constraint_expr *c;
3345 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
3346 t = TREE_OPERAND (t, 0);
3348 /* Now build constraints expressions. */
3349 if (TREE_CODE (t) == PHI_NODE)
3351 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))));
3353 /* Only care about pointers and structures containing
3355 if (could_have_pointers (PHI_RESULT (t)))
3360 /* For a phi node, assign all the arguments to
3362 get_constraint_for (PHI_RESULT (t), &lhsc);
3363 for (i = 0; i < PHI_NUM_ARGS (t); i++)
3366 tree strippedrhs = PHI_ARG_DEF (t, i);
3368 STRIP_NOPS (strippedrhs);
3369 rhstype = TREE_TYPE (strippedrhs);
3370 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
3372 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3374 struct constraint_expr *c2;
3375 while (VEC_length (ce_s, rhsc) > 0)
3377 c2 = VEC_last (ce_s, rhsc);
3378 process_constraint (new_constraint (*c, *c2));
3379 VEC_pop (ce_s, rhsc);
3385 /* In IPA mode, we need to generate constraints to pass call
3386 arguments through their calls. There are two case, either a
3387 modify_expr when we are returning a value, or just a plain
3388 call_expr when we are not. */
3389 else if (in_ipa_mode
3390 && ((TREE_CODE (t) == MODIFY_EXPR
3391 && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR
3392 && !(call_expr_flags (TREE_OPERAND (t, 1))
3393 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
3394 || (TREE_CODE (t) == CALL_EXPR
3395 && !(call_expr_flags (t)
3396 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))))
3405 if (TREE_CODE (t) == MODIFY_EXPR)
3407 lhsop = TREE_OPERAND (t, 0);
3408 rhsop = TREE_OPERAND (t, 1);
3415 decl = get_callee_fndecl (rhsop);
3417 /* If we can directly resolve the function being called, do so.
3418 Otherwise, it must be some sort of indirect expression that
3419 we should still be able to handle. */
3422 varid = get_id_for_tree (decl);
3426 decl = TREE_OPERAND (rhsop, 0);
3427 varid = get_id_for_tree (decl);
3430 /* Assign all the passed arguments to the appropriate incoming
3431 parameters of the function. */
3432 fi = get_varinfo (varid);
3433 arglist = TREE_OPERAND (rhsop, 1);
3435 for (;arglist; arglist = TREE_CHAIN (arglist))
3437 tree arg = TREE_VALUE (arglist);
3438 struct constraint_expr lhs ;
3439 struct constraint_expr *rhsp;
3441 get_constraint_for (arg, &rhsc);
3442 if (TREE_CODE (decl) != FUNCTION_DECL)
3451 lhs.var = first_vi_for_offset (fi, i)->id;
3454 while (VEC_length (ce_s, rhsc) != 0)
3456 rhsp = VEC_last (ce_s, rhsc);
3457 process_constraint (new_constraint (lhs, *rhsp));
3458 VEC_pop (ce_s, rhsc);
3462 /* If we are returning a value, assign it to the result. */
3465 struct constraint_expr rhs;
3466 struct constraint_expr *lhsp;
3469 get_constraint_for (lhsop, &lhsc);
3470 if (TREE_CODE (decl) != FUNCTION_DECL)
3479 rhs.var = first_vi_for_offset (fi, i)->id;
3482 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3483 process_constraint (new_constraint (*lhsp, rhs));
3486 /* Otherwise, just a regular assignment statement. */
3487 else if (TREE_CODE (t) == MODIFY_EXPR)
3489 tree lhsop = TREE_OPERAND (t, 0);
3490 tree rhsop = TREE_OPERAND (t, 1);
3493 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3494 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)
3495 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop))
3496 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE))
3498 do_structure_copy (lhsop, rhsop);
3502 /* Only care about operations with pointers, structures
3503 containing pointers, dereferences, and call expressions. */
3504 if (could_have_pointers (lhsop)
3505 || TREE_CODE (rhsop) == CALL_EXPR)
3507 get_constraint_for (lhsop, &lhsc);
3508 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
3510 /* RHS that consist of unary operations,
3511 exceptional types, or bare decls/constants, get
3512 handled directly by get_constraint_for. */
3514 case tcc_declaration:
3516 case tcc_exceptional:
3517 case tcc_expression:
3522 get_constraint_for (rhsop, &rhsc);
3523 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3525 struct constraint_expr *c2;
3528 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3529 process_constraint (new_constraint (*c, *c2));
3537 /* For pointer arithmetic of the form
3538 PTR + CST, we can simply use PTR's
3539 constraint because pointer arithmetic is
3540 not allowed to go out of bounds. */
3541 if (handle_ptr_arith (lhsc, rhsop))
3546 /* Otherwise, walk each operand. Notice that we
3547 can't use the operand interface because we need
3548 to process expressions other than simple operands
3549 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3551 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
3553 tree op = TREE_OPERAND (rhsop, i);
3556 gcc_assert (VEC_length (ce_s, rhsc) == 0);
3557 get_constraint_for (op, &rhsc);
3558 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3560 struct constraint_expr *c2;
3561 while (VEC_length (ce_s, rhsc) > 0)
3563 c2 = VEC_last (ce_s, rhsc);
3564 process_constraint (new_constraint (*c, *c2));
3565 VEC_pop (ce_s, rhsc);
3574 /* After promoting variables and computing aliasing we will
3575 need to re-scan most statements. FIXME: Try to minimize the
3576 number of statements re-scanned. It's not really necessary to
3577 re-scan *all* statements. */
3578 mark_stmt_modified (origt);
3579 VEC_free (ce_s, heap, rhsc);
3580 VEC_free (ce_s, heap, lhsc);
3584 /* Find the first varinfo in the same variable as START that overlaps with
3586 Effectively, walk the chain of fields for the variable START to find the
3587 first field that overlaps with OFFSET.
3588 Return NULL if we can't find one. */
3591 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3593 varinfo_t curr = start;
3596 /* We may not find a variable in the field list with the actual
3597 offset when when we have glommed a structure to a variable.
3598 In that case, however, offset should still be within the size
3600 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3608 /* Insert the varinfo FIELD into the field list for BASE, at the front
3612 insert_into_field_list (varinfo_t base, varinfo_t field)
3614 varinfo_t prev = base;
3615 varinfo_t curr = base->next;
3621 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3625 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
3627 varinfo_t prev = base;
3628 varinfo_t curr = base->next;
3639 if (field->offset <= curr->offset)
3644 field->next = prev->next;
3649 /* qsort comparison function for two fieldoff's PA and PB */
3652 fieldoff_compare (const void *pa, const void *pb)
3654 const fieldoff_s *foa = (const fieldoff_s *)pa;
3655 const fieldoff_s *fob = (const fieldoff_s *)pb;
3656 HOST_WIDE_INT foasize, fobsize;
3658 if (foa->offset != fob->offset)
3659 return foa->offset - fob->offset;
3661 foasize = TREE_INT_CST_LOW (foa->size);
3662 fobsize = TREE_INT_CST_LOW (fob->size);
3663 return foasize - fobsize;
3666 /* Sort a fieldstack according to the field offset and sizes. */
3668 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3670 qsort (VEC_address (fieldoff_s, fieldstack),
3671 VEC_length (fieldoff_s, fieldstack),
3672 sizeof (fieldoff_s),
3676 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3677 of TYPE onto fieldstack, recording their offsets along the way.
3678 OFFSET is used to keep track of the offset in this entire structure, rather
3679 than just the immediately containing structure. Returns the number
3681 HAS_UNION is set to true if we find a union type as a field of
3685 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
3686 HOST_WIDE_INT offset, bool *has_union)
3691 if (TREE_CODE (type) == COMPLEX_TYPE)
3693 fieldoff_s *real_part, *img_part;
3694 real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3695 real_part->type = TREE_TYPE (type);
3696 real_part->size = TYPE_SIZE (TREE_TYPE (type));
3697 real_part->offset = offset;
3698 real_part->decl = NULL_TREE;
3700 img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3701 img_part->type = TREE_TYPE (type);
3702 img_part->size = TYPE_SIZE (TREE_TYPE (type));
3703 img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
3704 img_part->decl = NULL_TREE;
3709 if (TREE_CODE (type) == ARRAY_TYPE)
3711 tree sz = TYPE_SIZE (type);
3712 tree elsz = TYPE_SIZE (TREE_TYPE (type));
3717 || ! host_integerp (sz, 1)
3718 || TREE_INT_CST_LOW (sz) == 0
3720 || ! host_integerp (elsz, 1)
3721 || TREE_INT_CST_LOW (elsz) == 0)
3724 nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
3725 if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
3728 for (i = 0; i < nr; ++i)
3734 && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
3735 || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
3738 if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
3740 else if (!(pushed = push_fields_onto_fieldstack
3741 (TREE_TYPE (type), fieldstack,
3742 offset + i * TREE_INT_CST_LOW (elsz), has_union)))
3743 /* Empty structures may have actual size, like in C++. So
3744 see if we didn't push any subfields and the size is
3745 nonzero, push the field onto the stack */
3752 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3753 pair->type = TREE_TYPE (type);
3755 pair->decl = NULL_TREE;
3756 pair->offset = offset + i * TREE_INT_CST_LOW (elsz);
3766 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
3767 if (TREE_CODE (field) == FIELD_DECL)
3773 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3774 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3777 if (!var_can_have_subvars (field))
3779 else if (!(pushed = push_fields_onto_fieldstack
3780 (TREE_TYPE (field), fieldstack,
3781 offset + bitpos_of_field (field), has_union))
3782 && DECL_SIZE (field)
3783 && !integer_zerop (DECL_SIZE (field)))
3784 /* Empty structures may have actual size, like in C++. So
3785 see if we didn't push any subfields and the size is
3786 nonzero, push the field onto the stack */
3793 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3794 pair->type = TREE_TYPE (field);
3795 pair->size = DECL_SIZE (field);
3797 pair->offset = offset + bitpos_of_field (field);
3807 /* Create a constraint from ESCAPED_VARS variable to VI. */
3809 make_constraint_from_escaped (varinfo_t vi)
3811 struct constraint_expr lhs, rhs;
3817 rhs.var = escaped_vars_id;
3820 process_constraint (new_constraint (lhs, rhs));
3823 /* Create a constraint to the ESCAPED_VARS variable from constraint
3827 make_constraint_to_escaped (struct constraint_expr rhs)
3829 struct constraint_expr lhs;
3831 lhs.var = escaped_vars_id;
3835 process_constraint (new_constraint (lhs, rhs));
3838 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3839 if it is a varargs function. */
3842 count_num_arguments (tree decl, bool *is_varargs)
3847 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
3851 if (TREE_VALUE (t) == void_type_node)
3861 /* Creation function node for DECL, using NAME, and return the index
3862 of the variable we've created for the function. */
3865 create_function_info_for (tree decl, const char *name)
3867 unsigned int index = VEC_length (varinfo_t, varmap);
3871 bool is_varargs = false;
3873 /* Create the variable info. */
3875 vi = new_var_info (decl, index, name, index);
3880 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3881 insert_id_for_tree (vi->decl, index);
3882 VEC_safe_push (varinfo_t, heap, varmap, vi);
3886 /* If it's varargs, we don't know how many arguments it has, so we
3893 vi->is_unknown_size_var = true;
3898 arg = DECL_ARGUMENTS (decl);
3900 /* Set up variables for each argument. */
3901 for (i = 1; i < vi->fullsize; i++)
3904 const char *newname;
3906 unsigned int newindex;
3907 tree argdecl = decl;
3912 newindex = VEC_length (varinfo_t, varmap);
3913 asprintf (&tempname, "%s.arg%d", name, i-1);
3914 newname = ggc_strdup (tempname);
3917 argvi = new_var_info (argdecl, newindex,newname, newindex);
3918 argvi->decl = argdecl;
3919 VEC_safe_push (varinfo_t, heap, varmap, argvi);
3922 argvi->fullsize = vi->fullsize;
3923 argvi->has_union = false;
3924 insert_into_field_list_sorted (vi, argvi);
3925 stats.total_vars ++;
3928 insert_id_for_tree (arg, newindex);
3929 arg = TREE_CHAIN (arg);
3933 /* Create a variable for the return var. */
3934 if (DECL_RESULT (decl) != NULL
3935 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
3938 const char *newname;
3940 unsigned int newindex;
3941 tree resultdecl = decl;
3945 if (DECL_RESULT (decl))
3946 resultdecl = DECL_RESULT (decl);
3948 newindex = VEC_length (varinfo_t, varmap);
3949 asprintf (&tempname, "%s.result", name);
3950 newname = ggc_strdup (tempname);
3953 resultvi = new_var_info (resultdecl, newindex, newname, newindex);
3954 resultvi->decl = resultdecl;
3955 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
3956 resultvi->offset = i;
3958 resultvi->fullsize = vi->fullsize;
3959 resultvi->has_union = false;
3960 insert_into_field_list_sorted (vi, resultvi);
3961 stats.total_vars ++;
3962 if (DECL_RESULT (decl))
3963 insert_id_for_tree (DECL_RESULT (decl), newindex);
3969 /* Return true if FIELDSTACK contains fields that overlap.
3970 FIELDSTACK is assumed to be sorted by offset. */
3973 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
3975 fieldoff_s *fo = NULL;
3977 HOST_WIDE_INT lastoffset = -1;
3979 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3981 if (fo->offset == lastoffset)
3983 lastoffset = fo->offset;
3988 /* This function is called through walk_tree to walk global
3989 initializers looking for constraints we need to add to the
3993 find_global_initializers (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
3996 varinfo_t vi = (varinfo_t)viv;
3999 switch (TREE_CODE (t))
4001 /* Dereferences and addressofs are the only important things
4002 here, and i don't even remember if dereferences are legal
4003 here in initializers. */
4007 struct constraint_expr *c;
4010 VEC(ce_s, heap) *rhsc = NULL;
4011 get_constraint_for (t, &rhsc);
4012 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4014 struct constraint_expr lhs;
4019 process_constraint (new_constraint (lhs, *c));
4022 VEC_free (ce_s, heap, rhsc);
4026 /* We might not have walked this because we skip
4027 DECL_EXTERNALs during the initial scan. */
4028 if (referenced_vars)
4031 if (referenced_var_check_and_insert (t))
4032 mark_sym_for_renaming (t);
4041 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4042 This will also create any varinfo structures necessary for fields
4046 create_variable_info_for (tree decl, const char *name)
4048 unsigned int index = VEC_length (varinfo_t, varmap);
4050 tree decltype = TREE_TYPE (decl);
4051 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
4052 bool notokay = false;
4054 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
4055 VEC (fieldoff_s,heap) *fieldstack = NULL;
4057 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4058 return create_function_info_for (decl, name);
4060 hasunion = TREE_CODE (decltype) == UNION_TYPE
4061 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
4062 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
4064 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
4067 VEC_free (fieldoff_s, heap, fieldstack);
4073 /* If the variable doesn't have subvars, we may end up needing to
4074 sort the field list and create fake variables for all the
4076 vi = new_var_info (decl, index, name, index);
4079 vi->has_union = hasunion;
4081 || TREE_CODE (declsize) != INTEGER_CST
4082 || TREE_CODE (decltype) == UNION_TYPE
4083 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
4085 vi->is_unknown_size_var = true;
4091 vi->fullsize = TREE_INT_CST_LOW (declsize);
4092 vi->size = vi->fullsize;
4095 insert_id_for_tree (vi->decl, index);
4096 VEC_safe_push (varinfo_t, heap, varmap, vi);
4097 if (is_global && (!flag_whole_program || !in_ipa_mode))
4099 make_constraint_from_escaped (vi);
4101 /* If the variable can't be aliased, there is no point in
4102 putting it in the set of nonlocal vars. */
4103 if (may_be_aliased (vi->decl))
4105 struct constraint_expr rhs;
4107 rhs.type = ADDRESSOF;
4109 make_constraint_to_escaped (rhs);
4112 if (TREE_CODE (decl) != FUNCTION_DECL && DECL_INITIAL (decl))
4114 walk_tree_without_duplicates (&DECL_INITIAL (decl),
4115 find_global_initializers,
4121 if (use_field_sensitive
4123 && !vi->is_unknown_size_var
4124 && var_can_have_subvars (decl)
4125 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4127 unsigned int newindex = VEC_length (varinfo_t, varmap);
4128 fieldoff_s *fo = NULL;
4131 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4134 || TREE_CODE (fo->size) != INTEGER_CST
4142 /* We can't sort them if we have a field with a variable sized type,
4143 which will make notokay = true. In that case, we are going to return
4144 without creating varinfos for the fields anyway, so sorting them is a
4148 sort_fieldstack (fieldstack);
4149 /* Due to some C++ FE issues, like PR 22488, we might end up
4150 what appear to be overlapping fields even though they,
4151 in reality, do not overlap. Until the C++ FE is fixed,
4152 we will simply disable field-sensitivity for these cases. */
4153 notokay = check_for_overlaps (fieldstack);
4157 if (VEC_length (fieldoff_s, fieldstack) != 0)
4158 fo = VEC_index (fieldoff_s, fieldstack, 0);
4160 if (fo == NULL || notokay)
4162 vi->is_unknown_size_var = 1;
4165 VEC_free (fieldoff_s, heap, fieldstack);
4169 vi->size = TREE_INT_CST_LOW (fo->size);
4170 vi->offset = fo->offset;
4171 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4172 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4176 const char *newname = "NULL";
4179 newindex = VEC_length (varinfo_t, varmap);
4183 asprintf (&tempname, "%s.%s",
4184 vi->name, alias_get_name (fo->decl));
4186 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC,
4187 vi->name, fo->offset);
4188 newname = ggc_strdup (tempname);
4191 newvi = new_var_info (decl, newindex, newname, newindex);
4192 newvi->offset = fo->offset;
4193 newvi->size = TREE_INT_CST_LOW (fo->size);
4194 newvi->fullsize = vi->fullsize;
4195 insert_into_field_list (vi, newvi);
4196 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4197 if (is_global && (!flag_whole_program || !in_ipa_mode))
4199 /* If the variable can't be aliased, there is no point in
4200 putting it in the set of nonlocal vars. */
4201 if (may_be_aliased (vi->decl))
4203 struct constraint_expr rhs;
4206 rhs.type = ADDRESSOF;
4208 make_constraint_to_escaped (rhs);
4210 make_constraint_from_escaped (newvi);
4215 VEC_free (fieldoff_s, heap, fieldstack);
4220 /* Print out the points-to solution for VAR to FILE. */
4223 dump_solution_for_var (FILE *file, unsigned int var)
4225 varinfo_t vi = get_varinfo (var);
4229 fprintf (file, "%s = { ", vi->name);
4230 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
4232 fprintf (file, "%s ", get_varinfo (i)->name);
4234 fprintf (file, "}\n");
4237 /* Print the points-to solution for VAR to stdout. */
4240 debug_solution_for_var (unsigned int var)
4242 dump_solution_for_var (stdout, var);
4245 /* Create varinfo structures for all of the variables in the
4246 function for intraprocedural mode. */
4249 intra_create_variable_infos (void)
4252 struct constraint_expr lhs, rhs;
4253 varinfo_t nonlocal_vi;
4255 /* For each incoming pointer argument arg, ARG = ESCAPED_VARS or a
4256 dummy variable if flag_argument_noalias > 2. */
4257 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4260 unsigned int arg_id;
4262 if (!could_have_pointers (t))
4265 arg_id = get_id_for_tree (t);
4267 /* With flag_argument_noalias greater than two means that the incoming
4268 argument cannot alias anything except for itself so create a HEAP
4270 if (POINTER_TYPE_P (TREE_TYPE (t))
4271 && flag_argument_noalias > 2)
4274 tree heapvar = heapvar_lookup (t);
4279 lhs.var = get_id_for_tree (t);
4281 if (heapvar == NULL_TREE)
4283 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4285 get_var_ann (heapvar)->is_heapvar = 1;
4286 DECL_EXTERNAL (heapvar) = 1;
4287 if (referenced_vars)
4288 add_referenced_var (heapvar);
4289 heapvar_insert (t, heapvar);
4291 id = get_id_for_tree (heapvar);
4292 vi = get_varinfo (id);
4293 vi->is_artificial_var = 1;
4294 vi->is_heap_var = 1;
4296 rhs.type = ADDRESSOF;
4298 for (p = get_varinfo (lhs.var); p; p = p->next)
4300 struct constraint_expr temp = lhs;
4302 process_constraint (new_constraint (temp, rhs));
4307 for (p = get_varinfo (arg_id); p; p = p->next)
4308 make_constraint_from_escaped (p);
4312 nonlocal_all = create_nonlocal_var (void_type_node);
4314 /* Create variable info for the nonlocal var if it does not
4316 nonlocal_vars_id = create_variable_info_for (nonlocal_all,
4317 get_name (nonlocal_all));
4318 nonlocal_vi = get_varinfo (nonlocal_vars_id);
4319 nonlocal_vi->is_artificial_var = 1;
4320 nonlocal_vi->is_heap_var = 1;
4321 nonlocal_vi->is_unknown_size_var = 1;
4322 nonlocal_vi->directly_dereferenced = true;
4324 rhs.var = nonlocal_vars_id;
4325 rhs.type = ADDRESSOF;
4328 lhs.var = escaped_vars_id;
4332 process_constraint (new_constraint (lhs, rhs));
4335 /* Set bits in INTO corresponding to the variable uids in solution set
4336 FROM, which came from variable PTR.
4337 For variables that are actually dereferenced, we also use type
4338 based alias analysis to prune the points-to sets. */
4341 set_uids_in_ptset (tree ptr, bitmap into, bitmap from)
4346 unsigned HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr));
4348 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4350 varinfo_t vi = get_varinfo (i);
4351 unsigned HOST_WIDE_INT var_alias_set;
4353 /* The only artificial variables that are allowed in a may-alias
4354 set are heap variables. */
4355 if (vi->is_artificial_var && !vi->is_heap_var)
4358 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
4360 /* Variables containing unions may need to be converted to
4361 their SFT's, because SFT's can have unions and we cannot. */
4362 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
4363 bitmap_set_bit (into, DECL_UID (sv->var));
4365 else if (TREE_CODE (vi->decl) == VAR_DECL
4366 || TREE_CODE (vi->decl) == PARM_DECL)
4368 if (var_can_have_subvars (vi->decl)
4369 && get_subvars_for_var (vi->decl))
4371 /* If VI->DECL is an aggregate for which we created
4372 SFTs, add the SFT corresponding to VI->OFFSET. */
4373 tree sft = get_subvar_at (vi->decl, vi->offset);
4376 var_alias_set = get_alias_set (sft);
4377 if (!vi->directly_dereferenced
4378 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
4379 bitmap_set_bit (into, DECL_UID (sft));
4384 /* Otherwise, just add VI->DECL to the alias set.
4385 Don't type prune artificial vars. */
4386 if (vi->is_artificial_var)
4387 bitmap_set_bit (into, DECL_UID (vi->decl));
4390 var_alias_set = get_alias_set (vi->decl);
4391 if (!vi->directly_dereferenced
4392 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
4393 bitmap_set_bit (into, DECL_UID (vi->decl));
4401 static bool have_alias_info = false;
4403 /* Given a pointer variable P, fill in its points-to set, or return
4404 false if we can't. */
4407 find_what_p_points_to (tree p)
4409 unsigned int id = 0;
4412 if (!have_alias_info)
4415 /* For parameters, get at the points-to set for the actual parm
4417 if (TREE_CODE (p) == SSA_NAME
4418 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4419 && default_def (SSA_NAME_VAR (p)) == p)
4420 lookup_p = SSA_NAME_VAR (p);
4422 if (lookup_id_for_tree (lookup_p, &id))
4424 varinfo_t vi = get_varinfo (id);
4426 if (vi->is_artificial_var)
4429 /* See if this is a field or a structure. */
4430 if (vi->size != vi->fullsize)
4432 /* Nothing currently asks about structure fields directly,
4433 but when they do, we need code here to hand back the
4435 if (!var_can_have_subvars (vi->decl)
4436 || get_subvars_for_var (vi->decl) == NULL)
4441 struct ptr_info_def *pi = get_ptr_info (p);
4445 /* This variable may have been collapsed, let's get the real
4447 vi = get_varinfo (vi->node);
4449 /* Translate artificial variables into SSA_NAME_PTR_INFO
4451 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4453 varinfo_t vi = get_varinfo (i);
4455 if (vi->is_artificial_var)
4457 /* FIXME. READONLY should be handled better so that
4458 flow insensitive aliasing can disregard writable
4460 if (vi->id == nothing_id)
4462 else if (vi->id == anything_id)
4463 pi->pt_anything = 1;
4464 else if (vi->id == readonly_id)
4465 pi->pt_anything = 1;
4466 else if (vi->id == integer_id)
4467 pi->pt_anything = 1;
4468 else if (vi->is_heap_var)
4469 pi->pt_global_mem = 1;
4473 if (pi->pt_anything)
4477 pi->pt_vars = BITMAP_GGC_ALLOC ();
4479 set_uids_in_ptset (vi->decl, pi->pt_vars, vi->solution);
4481 if (bitmap_empty_p (pi->pt_vars))
4493 /* Dump points-to information to OUTFILE. */
4496 dump_sa_points_to_info (FILE *outfile)
4500 fprintf (outfile, "\nPoints-to sets\n\n");
4502 if (dump_flags & TDF_STATS)
4504 fprintf (outfile, "Stats:\n");
4505 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4506 fprintf (outfile, "Statically unified vars: %d\n",
4507 stats.unified_vars_static);
4508 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
4509 fprintf (outfile, "Dynamically unified vars: %d\n",
4510 stats.unified_vars_dynamic);
4511 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4512 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4515 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4516 dump_solution_for_var (outfile, i);
4520 /* Debug points-to information to stderr. */
4523 debug_sa_points_to_info (void)
4525 dump_sa_points_to_info (stderr);
4529 /* Initialize the always-existing constraint variables for NULL
4530 ANYTHING, READONLY, and INTEGER */
4533 init_base_vars (void)
4535 struct constraint_expr lhs, rhs;
4537 /* Create the NULL variable, used to represent that a variable points
4539 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4540 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
4541 insert_id_for_tree (nothing_tree, 0);
4542 var_nothing->is_artificial_var = 1;
4543 var_nothing->offset = 0;
4544 var_nothing->size = ~0;
4545 var_nothing->fullsize = ~0;
4546 var_nothing->is_special_var = 1;
4548 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
4550 /* Create the ANYTHING variable, used to represent that a variable
4551 points to some unknown piece of memory. */
4552 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4553 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
4554 insert_id_for_tree (anything_tree, 1);
4555 var_anything->is_artificial_var = 1;
4556 var_anything->size = ~0;
4557 var_anything->offset = 0;
4558 var_anything->next = NULL;
4559 var_anything->fullsize = ~0;
4560 var_anything->is_special_var = 1;
4563 /* Anything points to anything. This makes deref constraints just
4564 work in the presence of linked list and other p = *p type loops,
4565 by saying that *ANYTHING = ANYTHING. */
4566 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
4568 lhs.var = anything_id;
4570 rhs.type = ADDRESSOF;
4571 rhs.var = anything_id;
4573 var_anything->address_taken = true;
4575 /* This specifically does not use process_constraint because
4576 process_constraint ignores all anything = anything constraints, since all
4577 but this one are redundant. */
4578 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
4580 /* Create the READONLY variable, used to represent that a variable
4581 points to readonly memory. */
4582 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4583 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
4584 var_readonly->is_artificial_var = 1;
4585 var_readonly->offset = 0;
4586 var_readonly->size = ~0;
4587 var_readonly->fullsize = ~0;
4588 var_readonly->next = NULL;
4589 var_readonly->is_special_var = 1;
4590 insert_id_for_tree (readonly_tree, 2);
4592 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4594 /* readonly memory points to anything, in order to make deref
4595 easier. In reality, it points to anything the particular
4596 readonly variable can point to, but we don't track this
4599 lhs.var = readonly_id;
4601 rhs.type = ADDRESSOF;
4602 rhs.var = anything_id;
4605 process_constraint (new_constraint (lhs, rhs));
4607 /* Create the INTEGER variable, used to represent that a variable points
4609 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4610 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
4611 insert_id_for_tree (integer_tree, 3);
4612 var_integer->is_artificial_var = 1;
4613 var_integer->size = ~0;
4614 var_integer->fullsize = ~0;
4615 var_integer->offset = 0;
4616 var_integer->next = NULL;
4617 var_integer->is_special_var = 1;
4619 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
4621 /* INTEGER = ANYTHING, because we don't know where a dereference of
4622 a random integer will point to. */
4624 lhs.var = integer_id;
4626 rhs.type = ADDRESSOF;
4627 rhs.var = anything_id;
4629 process_constraint (new_constraint (lhs, rhs));
4631 /* Create the ESCAPED_VARS variable used to represent variables that
4632 escape this function. */
4633 escaped_vars_tree = create_tmp_var_raw (void_type_node, "ESCAPED_VARS");
4634 var_escaped_vars = new_var_info (escaped_vars_tree, 4, "ESCAPED_VARS", 4);
4635 insert_id_for_tree (escaped_vars_tree, 4);
4636 var_escaped_vars->is_artificial_var = 1;
4637 var_escaped_vars->size = ~0;
4638 var_escaped_vars->fullsize = ~0;
4639 var_escaped_vars->offset = 0;
4640 var_escaped_vars->next = NULL;
4641 escaped_vars_id = 4;
4642 VEC_safe_push (varinfo_t, heap, varmap, var_escaped_vars);
4644 /* ESCAPED_VARS = *ESCAPED_VARS */
4646 lhs.var = escaped_vars_id;
4649 rhs.var = escaped_vars_id;
4651 process_constraint (new_constraint (lhs, rhs));
4655 /* Initialize things necessary to perform PTA */
4658 init_alias_vars (void)
4660 bitmap_obstack_initialize (&ptabitmap_obstack);
4661 bitmap_obstack_initialize (&predbitmap_obstack);
4663 constraint_pool = create_alloc_pool ("Constraint pool",
4664 sizeof (struct constraint), 30);
4665 variable_info_pool = create_alloc_pool ("Variable info pool",
4666 sizeof (struct variable_info), 30);
4667 constraint_edge_pool = create_alloc_pool ("Constraint edges",
4668 sizeof (struct constraint_edge), 30);
4670 constraints = VEC_alloc (constraint_t, heap, 8);
4671 varmap = VEC_alloc (varinfo_t, heap, 8);
4672 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
4673 memset (&stats, 0, sizeof (stats));
4678 /* Given a statement STMT, generate necessary constraints to
4679 escaped_vars for the escaping variables. */
4682 find_escape_constraints (tree stmt)
4684 enum escape_type stmt_escape_type = is_escape_site (stmt);
4686 VEC(ce_s, heap) *rhsc = NULL;
4687 struct constraint_expr *c;
4690 if (stmt_escape_type == NO_ESCAPE)
4693 if (TREE_CODE (stmt) == RETURN_EXPR)
4695 /* Returns are either bare, with an embedded MODIFY_EXPR, or
4696 just a plain old expression. */
4697 if (!TREE_OPERAND (stmt, 0))
4699 if (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
4700 rhs = TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
4702 rhs = TREE_OPERAND (stmt, 0);
4704 get_constraint_for (rhs, &rhsc);
4705 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4706 make_constraint_to_escaped (*c);
4707 VEC_free (ce_s, heap, rhsc);
4710 else if (TREE_CODE (stmt) == ASM_EXPR)
4712 /* Whatever the inputs of the ASM are, escape. */
4715 for (arg = ASM_INPUTS (stmt); arg; arg = TREE_CHAIN (arg))
4718 get_constraint_for (TREE_VALUE (arg), &rhsc);
4719 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4720 make_constraint_to_escaped (*c);
4721 VEC_free (ce_s, heap, rhsc);
4725 else if (TREE_CODE (stmt) == CALL_EXPR
4726 || (TREE_CODE (stmt) == MODIFY_EXPR
4727 && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR))
4729 /* Calls cause all of the arguments passed in to escape. */
4732 if (TREE_CODE (stmt) == MODIFY_EXPR)
4733 stmt = TREE_OPERAND (stmt, 1);
4734 for (arg = TREE_OPERAND (stmt, 1); arg; arg = TREE_CHAIN (arg))
4736 if (POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arg))))
4739 get_constraint_for (TREE_VALUE (arg), &rhsc);
4740 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4741 make_constraint_to_escaped (*c);
4742 VEC_free (ce_s, heap, rhsc);
4749 gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
4752 gcc_assert (stmt_escape_type == ESCAPE_BAD_CAST
4753 || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL
4754 || stmt_escape_type == ESCAPE_UNKNOWN);
4755 rhs = TREE_OPERAND (stmt, 1);
4757 /* Look through casts for the real escaping variable.
4758 Constants don't really escape, so ignore them.
4759 Otherwise, whatever escapes must be on our RHS. */
4760 if (TREE_CODE (rhs) == NOP_EXPR
4761 || TREE_CODE (rhs) == CONVERT_EXPR
4762 || TREE_CODE (rhs) == NON_LVALUE_EXPR)
4764 get_constraint_for (TREE_OPERAND (rhs, 0), &rhsc);
4766 else if (CONSTANT_CLASS_P (rhs))
4770 get_constraint_for (rhs, &rhsc);
4772 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
4773 make_constraint_to_escaped (*c);
4774 VEC_free (ce_s, heap, rhsc);
4777 /* Create points-to sets for the current function. See the comments
4778 at the start of the file for an algorithmic overview. */
4781 compute_points_to_sets (struct alias_info *ai)
4785 timevar_push (TV_TREE_PTA);
4789 intra_create_variable_infos ();
4791 /* Now walk all statements and derive aliases. */
4794 block_stmt_iterator bsi;
4797 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4799 if (is_gimple_reg (PHI_RESULT (phi)))
4801 find_func_aliases (phi);
4802 /* Update various related attributes like escaped
4803 addresses, pointer dereferences for loads and stores.
4804 This is used when creating name tags and alias
4806 update_alias_info (phi, ai);
4810 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4812 tree stmt = bsi_stmt (bsi);
4814 find_func_aliases (stmt);
4815 find_escape_constraints (stmt);
4816 /* Update various related attributes like escaped
4817 addresses, pointer dereferences for loads and stores.
4818 This is used when creating name tags and alias
4820 update_alias_info (stmt, ai);
4824 build_constraint_graph ();
4828 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4829 dump_constraints (dump_file);
4834 "\nCollapsing static cycles and doing variable "
4837 find_and_collapse_graph_cycles (graph, false);
4838 perform_var_substitution (graph);
4841 fprintf (dump_file, "\nSolving graph:\n");
4843 solve_graph (graph);
4846 dump_sa_points_to_info (dump_file);
4848 have_alias_info = true;
4850 timevar_pop (TV_TREE_PTA);
4854 /* Delete created points-to sets. */
4857 delete_points_to_sets (void)
4862 htab_delete (id_for_tree);
4863 bitmap_obstack_release (&ptabitmap_obstack);
4864 bitmap_obstack_release (&predbitmap_obstack);
4865 VEC_free (constraint_t, heap, constraints);
4867 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4869 /* Nonlocal vars may add more varinfos. */
4870 if (i >= graph_size)
4873 VEC_free (constraint_edge_t, heap, graph->succs[i]);
4874 VEC_free (constraint_edge_t, heap, graph->preds[i]);
4875 VEC_free (constraint_t, heap, v->complex);
4877 free (graph->zero_weight_preds);
4878 free (graph->zero_weight_succs);
4879 free (graph->succs);
4880 free (graph->preds);
4883 VEC_free (varinfo_t, heap, varmap);
4884 free_alloc_pool (variable_info_pool);
4885 free_alloc_pool (constraint_pool);
4886 free_alloc_pool (constraint_edge_pool);
4888 have_alias_info = false;
4891 /* Return true if we should execute IPA PTA. */
4895 return (flag_unit_at_a_time != 0
4897 /* Don't bother doing anything if the program has errors. */
4898 && !(errorcount || sorrycount));
4901 /* Execute the driver for IPA PTA. */
4903 ipa_pta_execute (void)
4905 struct cgraph_node *node;
4907 init_alias_heapvars ();
4910 for (node = cgraph_nodes; node; node = node->next)
4912 if (!node->analyzed || cgraph_is_master_clone (node))
4916 varid = create_function_info_for (node->decl,
4917 cgraph_node_name (node));
4918 if (node->local.externally_visible)
4920 varinfo_t fi = get_varinfo (varid);
4921 for (; fi; fi = fi->next)
4922 make_constraint_from_escaped (fi);
4926 for (node = cgraph_nodes; node; node = node->next)
4928 if (node->analyzed && cgraph_is_master_clone (node))
4930 struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
4932 tree old_func_decl = current_function_decl;
4935 "Generating constraints for %s\n",
4936 cgraph_node_name (node));
4938 current_function_decl = node->decl;
4940 FOR_EACH_BB_FN (bb, cfun)
4942 block_stmt_iterator bsi;
4945 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4947 if (is_gimple_reg (PHI_RESULT (phi)))
4949 find_func_aliases (phi);
4953 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4955 tree stmt = bsi_stmt (bsi);
4956 find_func_aliases (stmt);
4959 current_function_decl = old_func_decl;
4964 /* Make point to anything. */
4968 build_constraint_graph ();
4972 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4973 dump_constraints (dump_file);
4978 "\nCollapsing static cycles and doing variable "
4981 find_and_collapse_graph_cycles (graph, false);
4982 perform_var_substitution (graph);
4985 fprintf (dump_file, "\nSolving graph:\n");
4987 solve_graph (graph);
4990 dump_sa_points_to_info (dump_file);
4992 delete_alias_heapvars ();
4993 delete_points_to_sets ();
4997 struct tree_opt_pass pass_ipa_pta =
5000 gate_ipa_pta, /* gate */
5001 ipa_pta_execute, /* execute */
5004 0, /* static_pass_number */
5005 TV_IPA_PTA, /* tv_id */
5006 0, /* properties_required */
5007 0, /* properties_provided */
5008 0, /* properties_destroyed */
5009 0, /* todo_flags_start */
5010 0, /* todo_flags_finish */
5014 /* Initialize the heapvar for statement mapping. */
5016 init_alias_heapvars (void)
5018 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5020 nonlocal_all = NULL_TREE;
5024 delete_alias_heapvars (void)
5026 nonlocal_all = NULL_TREE;
5027 htab_delete (heapvar_for_stmt);
5031 #include "gt-tree-ssa-structalias.h"