1 /* Tree based points-to analysis
2 Copyright (C) 2005 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
43 #include "tree-gimple.h"
47 #include "tree-pass.h"
49 #include "alloc-pool.h"
50 #include "splay-tree.h"
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;
166 static bool use_field_sensitive = true;
167 static int in_ipa_mode = 0;
168 static bitmap_obstack predbitmap_obstack;
169 static bitmap_obstack ptabitmap_obstack;
170 static bitmap_obstack iteration_obstack;
172 static unsigned int create_variable_info_for (tree, const char *);
173 static void build_constraint_graph (void);
175 DEF_VEC_P(constraint_t);
176 DEF_VEC_ALLOC_P(constraint_t,heap);
178 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
180 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
182 static struct constraint_stats
184 unsigned int total_vars;
185 unsigned int collapsed_vars;
186 unsigned int unified_vars_static;
187 unsigned int unified_vars_dynamic;
188 unsigned int iterations;
189 unsigned int num_edges;
194 /* ID of this variable */
197 /* Name of this variable */
200 /* Tree that this variable is associated with. */
203 /* Offset of this variable, in bits, from the base variable */
204 unsigned HOST_WIDE_INT offset;
206 /* Size of the variable, in bits. */
207 unsigned HOST_WIDE_INT size;
209 /* Full size of the base variable, in bits. */
210 unsigned HOST_WIDE_INT fullsize;
212 /* A link to the variable for the next field in this structure. */
213 struct variable_info *next;
215 /* Node in the graph that represents the constraints and points-to
216 solution for the variable. */
219 /* True if the address of this variable is taken. Needed for
220 variable substitution. */
221 unsigned int address_taken:1;
223 /* True if this variable is the target of a dereference. Needed for
224 variable substitution. */
225 unsigned int indirect_target:1;
227 /* True if this is a variable created by the constraint analysis, such as
228 heap variables and constraints we had to break up. */
229 unsigned int is_artificial_var:1;
231 /* True if this is a special variable whose solution set should not be
233 unsigned int is_special_var:1;
235 /* True for variables whose size is not known or variable. */
236 unsigned int is_unknown_size_var:1;
238 /* True for variables that have unions somewhere in them. */
239 unsigned int has_union:1;
241 /* True if this is a heap variable. */
242 unsigned int is_heap_var:1;
244 /* Points-to set for this variable. */
247 /* Variable ids represented by this node. */
250 /* Vector of complex constraints for this node. Complex
251 constraints are those involving dereferences. */
252 VEC(constraint_t,heap) *complex;
254 /* Variable id this was collapsed to due to type unsafety.
255 This should be unused completely after build_constraint_graph, or
256 something is broken. */
257 struct variable_info *collapsed_to;
259 typedef struct variable_info *varinfo_t;
261 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
263 /* Pool of variable info structures. */
264 static alloc_pool variable_info_pool;
266 DEF_VEC_P(varinfo_t);
268 DEF_VEC_ALLOC_P(varinfo_t, heap);
270 /* Table of variable info structures for constraint variables. Indexed directly
271 by variable info id. */
272 static VEC(varinfo_t,heap) *varmap;
274 /* Return the varmap element N */
276 static inline varinfo_t
277 get_varinfo (unsigned int n)
279 return VEC_index(varinfo_t, varmap, n);
282 /* Return the varmap element N, following the collapsed_to link. */
284 static inline varinfo_t
285 get_varinfo_fc (unsigned int n)
287 varinfo_t v = VEC_index(varinfo_t, varmap, n);
290 return v->collapsed_to;
294 /* Variable that represents the unknown pointer. */
295 static varinfo_t var_anything;
296 static tree anything_tree;
297 static unsigned int anything_id;
299 /* Variable that represents the NULL pointer. */
300 static varinfo_t var_nothing;
301 static tree nothing_tree;
302 static unsigned int nothing_id;
304 /* Variable that represents read only memory. */
305 static varinfo_t var_readonly;
306 static tree readonly_tree;
307 static unsigned int readonly_id;
309 /* Variable that represents integers. This is used for when people do things
311 static varinfo_t var_integer;
312 static tree integer_tree;
313 static unsigned int integer_id;
316 /* Lookup a heap var for FROM, and return it if we find one. */
319 heapvar_lookup (tree from)
321 struct tree_map *h, in;
324 h = htab_find_with_hash (heapvar_for_stmt, &in, htab_hash_pointer (from));
330 /* Insert a mapping FROM->TO in the heap var for statement
334 heapvar_insert (tree from, tree to)
339 h = ggc_alloc (sizeof (struct tree_map));
340 h->hash = htab_hash_pointer (from);
343 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
344 *(struct tree_map **) loc = h;
347 /* Return a new variable info structure consisting for a variable
348 named NAME, and using constraint graph node NODE. */
351 new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
353 varinfo_t ret = pool_alloc (variable_info_pool);
359 ret->address_taken = false;
360 ret->indirect_target = false;
361 ret->is_artificial_var = false;
362 ret->is_heap_var = false;
363 ret->is_special_var = false;
364 ret->is_unknown_size_var = false;
365 ret->has_union = false;
366 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
367 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
370 ret->collapsed_to = NULL;
374 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
376 /* An expression that appears in a constraint. */
378 struct constraint_expr
380 /* Constraint type. */
381 constraint_expr_type type;
383 /* Variable we are referring to in the constraint. */
386 /* Offset, in bits, of this constraint from the beginning of
387 variables it ends up referring to.
389 IOW, in a deref constraint, we would deref, get the result set,
390 then add OFFSET to each member. */
391 unsigned HOST_WIDE_INT offset;
394 typedef struct constraint_expr ce_s;
396 DEF_VEC_ALLOC_O(ce_s, heap);
397 static void get_constraint_for (tree, VEC(ce_s, heap) **);
398 static void do_deref (VEC (ce_s, heap) **);
400 /* Our set constraints are made up of two constraint expressions, one
403 As described in the introduction, our set constraints each represent an
404 operation between set valued variables.
408 struct constraint_expr lhs;
409 struct constraint_expr rhs;
412 /* List of constraints that we use to build the constraint graph from. */
414 static VEC(constraint_t,heap) *constraints;
415 static alloc_pool constraint_pool;
417 /* An edge in the weighted constraint graph. The edges are weighted,
418 with a bit set in weights meaning their is an edge with that
420 We don't keep the src in the edge, because we always know what it
423 struct constraint_edge
429 typedef struct constraint_edge *constraint_edge_t;
430 static alloc_pool constraint_edge_pool;
432 /* Return a new constraint edge from SRC to DEST. */
434 static constraint_edge_t
435 new_constraint_edge (unsigned int dest)
437 constraint_edge_t ret = pool_alloc (constraint_edge_pool);
443 DEF_VEC_P(constraint_edge_t);
444 DEF_VEC_ALLOC_P(constraint_edge_t,heap);
447 /* The constraint graph is represented internally in two different
448 ways. The overwhelming majority of edges in the constraint graph
449 are zero weigh edges, and thus, using a vector of contrainst_edge_t
450 is a waste of time and memory, since they have no weights. We
451 simply use a bitmap to store the preds and succs for each node.
452 The weighted edges are stored as a set of adjacency vectors, one
453 per variable. succs[x] is the vector of successors for variable x,
454 and preds[x] is the vector of predecessors for variable x. IOW,
455 all edges are "forward" edges, which is not like our CFG. So
456 remember that preds[x]->src == x, and succs[x]->src == x. */
458 struct constraint_graph
460 bitmap *zero_weight_succs;
461 bitmap *zero_weight_preds;
462 VEC(constraint_edge_t,heap) **succs;
463 VEC(constraint_edge_t,heap) **preds;
466 typedef struct constraint_graph *constraint_graph_t;
468 static constraint_graph_t graph;
470 /* Create a new constraint consisting of LHS and RHS expressions. */
473 new_constraint (const struct constraint_expr lhs,
474 const struct constraint_expr rhs)
476 constraint_t ret = pool_alloc (constraint_pool);
482 /* Print out constraint C to FILE. */
485 dump_constraint (FILE *file, constraint_t c)
487 if (c->lhs.type == ADDRESSOF)
489 else if (c->lhs.type == DEREF)
491 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
492 if (c->lhs.offset != 0)
493 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
494 fprintf (file, " = ");
495 if (c->rhs.type == ADDRESSOF)
497 else if (c->rhs.type == DEREF)
499 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
500 if (c->rhs.offset != 0)
501 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
502 fprintf (file, "\n");
505 /* Print out constraint C to stderr. */
508 debug_constraint (constraint_t c)
510 dump_constraint (stderr, c);
513 /* Print out all constraints to FILE */
516 dump_constraints (FILE *file)
520 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
521 dump_constraint (file, c);
524 /* Print out all constraints to stderr. */
527 debug_constraints (void)
529 dump_constraints (stderr);
534 The solver is a simple worklist solver, that works on the following
537 sbitmap changed_nodes = all ones;
538 changed_count = number of nodes;
539 For each node that was already collapsed:
542 while (changed_count > 0)
544 compute topological ordering for constraint graph
546 find and collapse cycles in the constraint graph (updating
547 changed if necessary)
549 for each node (n) in the graph in topological order:
552 Process each complex constraint associated with the node,
553 updating changed if necessary.
555 For each outgoing edge from n, propagate the solution from n to
556 the destination of the edge, updating changed as necessary.
560 /* Return true if two constraint expressions A and B are equal. */
563 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
565 return a.type == b.type && a.var == b.var && a.offset == b.offset;
568 /* Return true if constraint expression A is less than constraint expression
569 B. This is just arbitrary, but consistent, in order to give them an
573 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
575 if (a.type == b.type)
578 return a.offset < b.offset;
580 return a.var < b.var;
583 return a.type < b.type;
586 /* Return true if constraint A is less than constraint B. This is just
587 arbitrary, but consistent, in order to give them an ordering. */
590 constraint_less (const constraint_t a, const constraint_t b)
592 if (constraint_expr_less (a->lhs, b->lhs))
594 else if (constraint_expr_less (b->lhs, a->lhs))
597 return constraint_expr_less (a->rhs, b->rhs);
600 /* Return true if two constraints A and B are equal. */
603 constraint_equal (struct constraint a, struct constraint b)
605 return constraint_expr_equal (a.lhs, b.lhs)
606 && constraint_expr_equal (a.rhs, b.rhs);
610 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
613 constraint_vec_find (VEC(constraint_t,heap) *vec,
614 struct constraint lookfor)
622 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
623 if (place >= VEC_length (constraint_t, vec))
625 found = VEC_index (constraint_t, vec, place);
626 if (!constraint_equal (*found, lookfor))
631 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
634 constraint_set_union (VEC(constraint_t,heap) **to,
635 VEC(constraint_t,heap) **from)
640 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
642 if (constraint_vec_find (*to, *c) == NULL)
644 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
646 VEC_safe_insert (constraint_t, heap, *to, place, c);
651 /* Take a solution set SET, add OFFSET to each member of the set, and
652 overwrite SET with the result when done. */
655 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
657 bitmap result = BITMAP_ALLOC (&iteration_obstack);
661 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
663 /* If this is a properly sized variable, only add offset if it's
664 less than end. Otherwise, it is globbed to a single
667 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
669 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
670 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
673 bitmap_set_bit (result, v->id);
675 else if (get_varinfo (i)->is_artificial_var
676 || get_varinfo (i)->has_union
677 || get_varinfo (i)->is_unknown_size_var)
679 bitmap_set_bit (result, i);
683 bitmap_copy (set, result);
684 BITMAP_FREE (result);
687 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
691 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
694 return bitmap_ior_into (to, from);
700 tmp = BITMAP_ALLOC (&iteration_obstack);
701 bitmap_copy (tmp, from);
702 solution_set_add (tmp, inc);
703 res = bitmap_ior_into (to, tmp);
709 /* Insert constraint C into the list of complex constraints for VAR. */
712 insert_into_complex (unsigned int var, constraint_t c)
714 varinfo_t vi = get_varinfo (var);
715 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
717 VEC_safe_insert (constraint_t, heap, vi->complex, place, c);
721 /* Compare two constraint edges A and B, return true if they are equal. */
724 constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
726 return a.dest == b.dest;
729 /* Compare two constraint edges, return true if A is less than B */
732 constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
734 if (a->dest < b->dest)
739 /* Find the constraint edge that matches LOOKFOR, in VEC.
740 Return the edge, if found, NULL otherwise. */
742 static constraint_edge_t
743 constraint_edge_vec_find (VEC(constraint_edge_t,heap) *vec,
744 struct constraint_edge lookfor)
747 constraint_edge_t edge = NULL;
749 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
750 constraint_edge_less);
751 if (place >= VEC_length (constraint_edge_t, vec))
753 edge = VEC_index (constraint_edge_t, vec, place);
754 if (!constraint_edge_equal (*edge, lookfor))
759 /* Condense two variable nodes into a single variable node, by moving
760 all associated info from SRC to TO. */
763 condense_varmap_nodes (unsigned int to, unsigned int src)
765 varinfo_t tovi = get_varinfo (to);
766 varinfo_t srcvi = get_varinfo (src);
771 /* the src node, and all its variables, are now the to node. */
773 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
774 get_varinfo (i)->node = to;
776 /* Merge the src node variables and the to node variables. */
777 bitmap_set_bit (tovi->variables, src);
778 bitmap_ior_into (tovi->variables, srcvi->variables);
779 bitmap_clear (srcvi->variables);
781 /* Move all complex constraints from src node into to node */
782 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
784 /* In complex constraints for node src, we may have either
785 a = *src, and *src = a. */
787 if (c->rhs.type == DEREF)
792 constraint_set_union (&tovi->complex, &srcvi->complex);
793 VEC_free (constraint_t, heap, srcvi->complex);
794 srcvi->complex = NULL;
797 /* Erase an edge from SRC to SRC from GRAPH. This routine only
798 handles self-edges (e.g. an edge from a to a). */
801 erase_graph_self_edge (constraint_graph_t graph, unsigned int src)
803 VEC(constraint_edge_t,heap) *predvec = graph->preds[src];
804 VEC(constraint_edge_t,heap) *succvec = graph->succs[src];
805 struct constraint_edge edge;
810 /* Remove from the successors. */
811 place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
812 constraint_edge_less);
814 /* Make sure we found the edge. */
815 #ifdef ENABLE_CHECKING
817 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
818 gcc_assert (constraint_edge_equal (*tmp, edge));
821 VEC_ordered_remove (constraint_edge_t, succvec, place);
823 /* Remove from the predecessors. */
824 place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
825 constraint_edge_less);
827 /* Make sure we found the edge. */
828 #ifdef ENABLE_CHECKING
830 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
831 gcc_assert (constraint_edge_equal (*tmp, edge));
834 VEC_ordered_remove (constraint_edge_t, predvec, place);
837 /* Remove edges involving NODE from GRAPH. */
840 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
842 VEC(constraint_edge_t,heap) *succvec = graph->succs[node];
843 VEC(constraint_edge_t,heap) *predvec = graph->preds[node];
846 constraint_edge_t c = NULL;
849 /* Walk the successors, erase the associated preds. */
851 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[node], 0, j, bi)
853 bitmap_clear_bit (graph->zero_weight_preds[j], node);
855 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
859 struct constraint_edge lookfor;
860 constraint_edge_t result;
863 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
864 &lookfor, constraint_edge_less);
865 result = VEC_ordered_remove (constraint_edge_t,
866 graph->preds[c->dest], place);
867 pool_free (constraint_edge_pool, result);
870 /* Walk the preds, erase the associated succs. */
872 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[node], 0, j, bi)
874 bitmap_clear_bit (graph->zero_weight_succs[j], node);
876 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
880 struct constraint_edge lookfor;
881 constraint_edge_t result;
884 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
885 &lookfor, constraint_edge_less);
886 result = VEC_ordered_remove (constraint_edge_t,
887 graph->succs[c->dest], place);
888 pool_free (constraint_edge_pool, result);
892 if (graph->zero_weight_preds[node])
894 BITMAP_FREE (graph->zero_weight_preds[node]);
895 graph->zero_weight_preds[node] = NULL;
898 if (graph->zero_weight_succs[node])
900 BITMAP_FREE (graph->zero_weight_succs[node]);
901 graph->zero_weight_succs[node] = NULL;
904 VEC_free (constraint_edge_t, heap, graph->preds[node]);
905 VEC_free (constraint_edge_t, heap, graph->succs[node]);
906 graph->preds[node] = NULL;
907 graph->succs[node] = NULL;
910 static bool edge_added = false;
912 /* Add edge (src, dest) to the graph. */
915 add_graph_edge (constraint_graph_t graph, unsigned int src, unsigned int dest)
918 VEC(constraint_edge_t,heap) *vec;
919 struct constraint_edge newe;
922 vec = graph->preds[src];
923 place = VEC_lower_bound (constraint_edge_t, vec, &newe,
924 constraint_edge_less);
925 if (place == VEC_length (constraint_edge_t, vec)
926 || VEC_index (constraint_edge_t, vec, place)->dest != dest)
928 constraint_edge_t edge = new_constraint_edge (dest);
930 VEC_safe_insert (constraint_edge_t, heap, graph->preds[src],
932 edge = new_constraint_edge (src);
934 place = VEC_lower_bound (constraint_edge_t, graph->succs[dest],
935 edge, constraint_edge_less);
936 VEC_safe_insert (constraint_edge_t, heap, graph->succs[dest],
947 /* Return the bitmap representing the weights of edge (SRC, DEST). */
950 get_graph_weights (constraint_graph_t graph, unsigned int src,
953 constraint_edge_t edge;
954 VEC(constraint_edge_t,heap) *vec;
955 struct constraint_edge lookfor;
959 vec = graph->preds[src];
960 edge = constraint_edge_vec_find (vec, lookfor);
961 gcc_assert (edge != NULL);
962 return &edge->weights;
965 /* Allocate graph weight bitmap for the edges associated with SRC and
966 DEST in GRAPH. Both the pred and the succ edges share a single
967 bitmap, so we need to set both edges to that bitmap. */
970 allocate_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;
978 result = BITMAP_ALLOC (&ptabitmap_obstack);
980 /* Set the pred weight. */
982 vec = graph->preds[src];
983 edge = constraint_edge_vec_find (vec, lookfor);
984 gcc_assert (edge != NULL);
985 edge->weights = result;
987 /* Set the succ weight. */
989 vec = graph->succs[dest];
990 edge = constraint_edge_vec_find (vec, lookfor);
991 gcc_assert (edge != NULL);
992 edge->weights = result;
998 /* Merge GRAPH nodes FROM and TO into node TO. */
1001 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1004 VEC(constraint_edge_t,heap) *succvec = graph->succs[from];
1005 VEC(constraint_edge_t,heap) *predvec = graph->preds[from];
1007 constraint_edge_t c;
1011 /* Merge all the zero weighted predecessor edges. */
1012 if (graph->zero_weight_preds[from])
1014 if (!graph->zero_weight_preds[to])
1015 graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1017 EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_preds[from], 0, j, bi)
1021 bitmap_clear_bit (graph->zero_weight_succs[j], from);
1022 bitmap_set_bit (graph->zero_weight_succs[j], to);
1025 bitmap_ior_into (graph->zero_weight_preds[to],
1026 graph->zero_weight_preds[from]);
1029 /* Merge all the zero weighted successor edges. */
1030 if (graph->zero_weight_succs[from])
1032 if (!graph->zero_weight_succs[to])
1033 graph->zero_weight_succs[to] = BITMAP_ALLOC (&ptabitmap_obstack);
1034 EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_succs[from], 0, j, bi)
1036 bitmap_clear_bit (graph->zero_weight_preds[j], from);
1037 bitmap_set_bit (graph->zero_weight_preds[j], to);
1039 bitmap_ior_into (graph->zero_weight_succs[to],
1040 graph->zero_weight_succs[from]);
1043 /* Merge all the non-zero weighted predecessor edges. */
1044 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
1046 unsigned int d = c->dest;
1050 if (c->dest == from)
1053 add_graph_edge (graph, to, d);
1055 temp = *(get_graph_weights (graph, from, c->dest));
1058 weights = get_graph_weights (graph, to, d);
1060 *weights = allocate_graph_weights (graph, to, d);
1062 bitmap_ior_into (*weights, temp);
1067 /* Merge all the non-zero weighted successor edges. */
1068 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
1070 unsigned int d = c->dest;
1074 if (c->dest == from)
1077 add_graph_edge (graph, d, to);
1079 temp = *(get_graph_weights (graph, c->dest, from));
1082 weights = get_graph_weights (graph, d, to);
1084 *weights = allocate_graph_weights (graph, d, to);
1085 bitmap_ior_into (*weights, temp);
1088 clear_edges_for_node (graph, from);
1091 /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if
1092 it doesn't exist in the graph already.
1093 Return false if the edge already existed, true otherwise. */
1096 int_add_graph_edge (constraint_graph_t graph, unsigned int to,
1097 unsigned int from, unsigned HOST_WIDE_INT weight)
1099 if (to == from && weight == 0)
1109 if (!graph->zero_weight_preds[to])
1110 graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1111 if (!graph->zero_weight_succs[from])
1112 graph->zero_weight_succs[from] = BITMAP_ALLOC (&ptabitmap_obstack);
1113 if (!bitmap_bit_p (graph->zero_weight_succs[from], to))
1118 bitmap_set_bit (graph->zero_weight_preds[to], from);
1119 bitmap_set_bit (graph->zero_weight_succs[from], to);
1126 r = add_graph_edge (graph, to, from);
1127 weights = get_graph_weights (graph, to, from);
1132 *weights = allocate_graph_weights (graph, to, from);
1133 bitmap_set_bit (*weights, weight);
1137 r |= !bitmap_bit_p (*weights, weight);
1138 bitmap_set_bit (*weights, weight);
1147 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1150 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1153 struct constraint_edge lookfor;
1156 return (graph->zero_weight_succs[dest]
1157 && bitmap_bit_p (graph->zero_weight_succs[dest], src))
1158 || constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL;
1161 /* Return true if {DEST, SRC} is an existing weighted graph edge (IE has
1162 a weight other than 0) in GRAPH. */
1164 valid_weighted_graph_edge (constraint_graph_t graph, unsigned int src,
1167 struct constraint_edge lookfor;
1170 return graph->preds[src]
1171 && constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL;
1175 /* Build the constraint graph. */
1178 build_constraint_graph (void)
1183 graph = xmalloc (sizeof (struct constraint_graph));
1184 graph->succs = xcalloc (VEC_length (varinfo_t, varmap) + 1,
1185 sizeof (*graph->succs));
1186 graph->preds = xcalloc (VEC_length (varinfo_t, varmap) + 1,
1187 sizeof (*graph->preds));
1188 graph->zero_weight_succs = xcalloc (VEC_length (varinfo_t, varmap) + 1,
1189 sizeof (*graph->zero_weight_succs));
1190 graph->zero_weight_preds = xcalloc (VEC_length (varinfo_t, varmap) + 1,
1191 sizeof (*graph->zero_weight_preds));
1193 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1195 struct constraint_expr lhs = c->lhs;
1196 struct constraint_expr rhs = c->rhs;
1197 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
1198 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
1200 if (lhs.type == DEREF)
1202 /* *x = y or *x = &y (complex) */
1203 if (rhs.type == ADDRESSOF || rhsvar > anything_id)
1204 insert_into_complex (lhsvar, c);
1206 else if (rhs.type == DEREF)
1208 /* !special var= *y */
1209 if (!(get_varinfo (lhsvar)->is_special_var))
1210 insert_into_complex (rhsvar, c);
1212 else if (rhs.type == ADDRESSOF)
1215 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1217 else if (lhsvar > anything_id)
1219 /* Ignore 0 weighted self edges, as they can't possibly contribute
1221 if (lhsvar != rhsvar || rhs.offset != 0 || lhs.offset != 0)
1223 /* x = y (simple) */
1224 int_add_graph_edge (graph, lhs.var, rhs.var, rhs.offset);
1232 /* Changed variables on the last iteration. */
1233 static unsigned int changed_count;
1234 static sbitmap changed;
1236 DEF_VEC_I(unsigned);
1237 DEF_VEC_ALLOC_I(unsigned,heap);
1240 /* Strongly Connected Component visitation info. */
1245 sbitmap in_component;
1247 unsigned int *visited_index;
1248 VEC(unsigned,heap) *scc_stack;
1249 VEC(unsigned,heap) *unification_queue;
1253 /* Recursive routine to find strongly connected components in GRAPH.
1254 SI is the SCC info to store the information in, and N is the id of current
1255 graph node we are processing.
1257 This is Tarjan's strongly connected component finding algorithm, as
1258 modified by Nuutila to keep only non-root nodes on the stack.
1259 The algorithm can be found in "On finding the strongly connected
1260 connected components in a directed graph" by Esko Nuutila and Eljas
1261 Soisalon-Soininen, in Information Processing Letters volume 49,
1262 number 1, pages 9-14. */
1265 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1270 gcc_assert (get_varinfo (n)->node == n);
1271 SET_BIT (si->visited, n);
1272 RESET_BIT (si->in_component, n);
1273 si->visited_index[n] = si->current_index ++;
1275 /* Visit all the successors. */
1276 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[n], 0, i, bi)
1279 if (!TEST_BIT (si->visited, w))
1280 scc_visit (graph, si, w);
1281 if (!TEST_BIT (si->in_component, w))
1283 unsigned int t = get_varinfo (w)->node;
1284 unsigned int nnode = get_varinfo (n)->node;
1285 if (si->visited_index[t] < si->visited_index[nnode])
1286 get_varinfo (n)->node = t;
1290 /* See if any components have been identified. */
1291 if (get_varinfo (n)->node == n)
1293 unsigned int t = si->visited_index[n];
1294 SET_BIT (si->in_component, n);
1295 while (VEC_length (unsigned, si->scc_stack) != 0
1296 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1298 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1299 get_varinfo (w)->node = n;
1300 SET_BIT (si->in_component, w);
1301 /* Mark this node for collapsing. */
1302 VEC_safe_push (unsigned, heap, si->unification_queue, w);
1306 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1310 /* Collapse two variables into one variable. */
1313 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1315 bitmap tosol, fromsol;
1317 condense_varmap_nodes (to, from);
1318 tosol = get_varinfo (to)->solution;
1319 fromsol = get_varinfo (from)->solution;
1320 bitmap_ior_into (tosol, fromsol);
1321 merge_graph_nodes (graph, to, from);
1323 if (valid_graph_edge (graph, to, to))
1325 if (graph->zero_weight_preds[to])
1327 bitmap_clear_bit (graph->zero_weight_preds[to], to);
1328 bitmap_clear_bit (graph->zero_weight_succs[to], to);
1330 if (valid_weighted_graph_edge (graph, to, to))
1332 bitmap weights = *(get_graph_weights (graph, to, to));
1333 if (!weights || bitmap_empty_p (weights))
1334 erase_graph_self_edge (graph, to);
1337 BITMAP_FREE (fromsol);
1338 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1339 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1343 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1344 SI is the Strongly Connected Components information structure that tells us
1345 what components to unify.
1346 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1347 count should be updated to reflect the unification. */
1350 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1351 bool update_changed)
1354 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1357 /* We proceed as follows:
1359 For each component in the queue (components are delineated by
1360 when current_queue_element->node != next_queue_element->node):
1362 rep = representative node for component
1364 For each node (tounify) to be unified in the component,
1365 merge the solution for tounify into tmp bitmap
1367 clear solution for tounify
1369 merge edges from tounify into rep
1371 merge complex constraints from tounify into rep
1373 update changed count to note that tounify will never change
1376 Merge tmp into solution for rep, marking rep changed if this
1377 changed rep's solution.
1379 Delete any 0 weighted self-edges we now have for rep. */
1380 while (i != VEC_length (unsigned, si->unification_queue))
1382 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1383 unsigned int n = get_varinfo (tounify)->node;
1385 if (dump_file && (dump_flags & TDF_DETAILS))
1386 fprintf (dump_file, "Unifying %s to %s\n",
1387 get_varinfo (tounify)->name,
1388 get_varinfo (n)->name);
1390 stats.unified_vars_dynamic++;
1392 stats.unified_vars_static++;
1393 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1394 merge_graph_nodes (graph, n, tounify);
1395 condense_varmap_nodes (n, tounify);
1397 if (update_changed && TEST_BIT (changed, tounify))
1399 RESET_BIT (changed, tounify);
1400 if (!TEST_BIT (changed, n))
1401 SET_BIT (changed, n);
1404 gcc_assert (changed_count > 0);
1409 bitmap_clear (get_varinfo (tounify)->solution);
1412 /* If we've either finished processing the entire queue, or
1413 finished processing all nodes for component n, update the solution for
1415 if (i == VEC_length (unsigned, si->unification_queue)
1416 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1418 /* If the solution changes because of the merging, we need to mark
1419 the variable as changed. */
1420 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1422 if (update_changed && !TEST_BIT (changed, n))
1424 SET_BIT (changed, n);
1430 if (valid_graph_edge (graph, n, n))
1432 if (graph->zero_weight_succs[n])
1434 if (graph->zero_weight_preds[n])
1435 bitmap_clear_bit (graph->zero_weight_preds[n], n);
1436 bitmap_clear_bit (graph->zero_weight_succs[n], n);
1438 if (valid_weighted_graph_edge (graph, n, n))
1440 bitmap weights = *(get_graph_weights (graph, n, n));
1441 if (!weights || bitmap_empty_p (weights))
1442 erase_graph_self_edge (graph, n);
1451 /* Information needed to compute the topological ordering of a graph. */
1455 /* sbitmap of visited nodes. */
1457 /* Array that stores the topological order of the graph, *in
1459 VEC(unsigned,heap) *topo_order;
1463 /* Initialize and return a topological info structure. */
1465 static struct topo_info *
1466 init_topo_info (void)
1468 size_t size = VEC_length (varinfo_t, varmap);
1469 struct topo_info *ti = xmalloc (sizeof (struct topo_info));
1470 ti->visited = sbitmap_alloc (size);
1471 sbitmap_zero (ti->visited);
1472 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1477 /* Free the topological sort info pointed to by TI. */
1480 free_topo_info (struct topo_info *ti)
1482 sbitmap_free (ti->visited);
1483 VEC_free (unsigned, heap, ti->topo_order);
1487 /* Visit the graph in topological order, and store the order in the
1488 topo_info structure. */
1491 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1494 VEC(constraint_edge_t,heap) *succs = graph->succs[n];
1497 constraint_edge_t c;
1501 SET_BIT (ti->visited, n);
1502 if (VEC_length (constraint_edge_t, succs) != 0)
1504 temp = BITMAP_ALLOC (&iteration_obstack);
1505 if (graph->zero_weight_succs[n])
1506 bitmap_ior_into (temp, graph->zero_weight_succs[n]);
1507 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1508 bitmap_set_bit (temp, c->dest);
1511 temp = graph->zero_weight_succs[n];
1514 EXECUTE_IF_SET_IN_BITMAP (temp, 0, j, bi)
1516 if (!TEST_BIT (ti->visited, j))
1517 topo_visit (graph, ti, j);
1519 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1522 /* Return true if variable N + OFFSET is a legal field of N. */
1525 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1527 varinfo_t ninfo = get_varinfo (n);
1529 /* For things we've globbed to single variables, any offset into the
1530 variable acts like the entire variable, so that it becomes offset
1532 if (ninfo->is_special_var
1533 || ninfo->is_artificial_var
1534 || ninfo->is_unknown_size_var)
1539 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1542 #define DONT_PROPAGATE_WITH_ANYTHING 0
1544 /* Process a constraint C that represents *x = &y. */
1547 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1548 constraint_t c, bitmap delta)
1550 unsigned int rhs = c->rhs.var;
1554 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1555 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1557 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1558 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
1560 /* *x != NULL && *x != ANYTHING*/
1564 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1566 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1570 sol = get_varinfo (t)->solution;
1571 if (!bitmap_bit_p (sol, rhs))
1573 bitmap_set_bit (sol, rhs);
1574 if (!TEST_BIT (changed, t))
1576 SET_BIT (changed, t);
1581 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1582 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1587 /* Process a constraint C that represents x = *y, using DELTA as the
1588 starting solution. */
1591 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1594 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1596 bitmap sol = get_varinfo (lhs)->solution;
1600 #if DONT_PROPAGATE_WITH_ANYTHING
1601 if (bitmap_bit_p (delta, anything_id))
1603 flag = !bitmap_bit_p (sol, anything_id);
1605 bitmap_set_bit (sol, anything_id);
1609 /* For each variable j in delta (Sol(y)), add
1610 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1611 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1613 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1614 if (type_safe (j, &roffset))
1617 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1620 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1625 /* Adding edges from the special vars is pointless.
1626 They don't have sets that can change. */
1627 if (get_varinfo (t) ->is_special_var)
1628 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1629 else if (int_add_graph_edge (graph, lhs, t, 0))
1630 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1632 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1633 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1636 #if DONT_PROPAGATE_WITH_ANYTHING
1639 /* If the LHS solution changed, mark the var as changed. */
1642 get_varinfo (lhs)->solution = sol;
1643 if (!TEST_BIT (changed, lhs))
1645 SET_BIT (changed, lhs);
1651 /* Process a constraint C that represents *x = y. */
1654 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1656 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1657 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1658 bitmap sol = get_varinfo (rhs)->solution;
1662 #if DONT_PROPAGATE_WITH_ANYTHING
1663 if (bitmap_bit_p (sol, anything_id))
1665 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1667 varinfo_t jvi = get_varinfo (j);
1669 unsigned int loff = c->lhs.offset;
1670 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
1673 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1678 if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id))
1680 bitmap_set_bit (get_varinfo (t)->solution, anything_id);
1681 if (!TEST_BIT (changed, t))
1683 SET_BIT (changed, t);
1692 /* For each member j of delta (Sol(x)), add an edge from y to j and
1693 union Sol(y) into Sol(j) */
1694 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1696 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1697 if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var))
1701 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1703 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1707 if (int_add_graph_edge (graph, t, rhs, roff))
1709 bitmap tmp = get_varinfo (t)->solution;
1710 if (set_union_with_increment (tmp, sol, roff))
1712 get_varinfo (t)->solution = tmp;
1714 sol = get_varinfo (rhs)->solution;
1715 if (!TEST_BIT (changed, t))
1717 SET_BIT (changed, t);
1723 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1724 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1728 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1729 constraint (IE *x = &y, x = *y, and *x = y). */
1732 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1734 if (c->lhs.type == DEREF)
1736 if (c->rhs.type == ADDRESSOF)
1739 do_da_constraint (graph, c, delta);
1744 do_ds_constraint (graph, c, delta);
1750 if (!(get_varinfo (c->lhs.var)->is_special_var))
1751 do_sd_constraint (graph, c, delta);
1755 /* Initialize and return a new SCC info structure. */
1757 static struct scc_info *
1758 init_scc_info (void)
1760 struct scc_info *si = xmalloc (sizeof (struct scc_info));
1761 size_t size = VEC_length (varinfo_t, varmap);
1763 si->current_index = 0;
1764 si->visited = sbitmap_alloc (size);
1765 sbitmap_zero (si->visited);
1766 si->in_component = sbitmap_alloc (size);
1767 sbitmap_ones (si->in_component);
1768 si->visited_index = xcalloc (sizeof (unsigned int), size + 1);
1769 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1770 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1774 /* Free an SCC info structure pointed to by SI */
1777 free_scc_info (struct scc_info *si)
1779 sbitmap_free (si->visited);
1780 sbitmap_free (si->in_component);
1781 free (si->visited_index);
1782 VEC_free (unsigned, heap, si->scc_stack);
1783 VEC_free (unsigned, heap, si->unification_queue);
1788 /* Find cycles in GRAPH that occur, using strongly connected components, and
1789 collapse the cycles into a single representative node. if UPDATE_CHANGED
1790 is true, then update the changed sbitmap to note those nodes whose
1791 solutions have changed as a result of collapsing. */
1794 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1797 unsigned int size = VEC_length (varinfo_t, varmap);
1798 struct scc_info *si = init_scc_info ();
1800 for (i = 0; i != size; ++i)
1801 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1802 scc_visit (graph, si, i);
1804 process_unification_queue (graph, si, update_changed);
1808 /* Compute a topological ordering for GRAPH, and store the result in the
1809 topo_info structure TI. */
1812 compute_topo_order (constraint_graph_t graph,
1813 struct topo_info *ti)
1816 unsigned int size = VEC_length (varinfo_t, varmap);
1818 for (i = 0; i != size; ++i)
1819 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1820 topo_visit (graph, ti, i);
1823 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1826 bitmap_other_than_zero_bit_set (bitmap b)
1831 if (bitmap_empty_p (b))
1833 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1838 /* Perform offline variable substitution.
1840 This is a linear time way of identifying variables that must have
1841 equivalent points-to sets, including those caused by static cycles,
1842 and single entry subgraphs, in the constraint graph.
1844 The technique is described in "Off-line variable substitution for
1845 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1846 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1849 perform_var_substitution (constraint_graph_t graph)
1851 struct topo_info *ti = init_topo_info ();
1853 bitmap_obstack_initialize (&iteration_obstack);
1854 /* Compute the topological ordering of the graph, then visit each
1855 node in topological order. */
1856 compute_topo_order (graph, ti);
1858 while (VEC_length (unsigned, ti->topo_order) != 0)
1860 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1862 varinfo_t vi = get_varinfo (i);
1863 bool okay_to_elim = false;
1864 unsigned int root = VEC_length (varinfo_t, varmap);
1865 VEC(constraint_edge_t,heap) *predvec = graph->preds[i];
1866 constraint_edge_t ce = NULL;
1871 /* We can't eliminate things whose address is taken, or which is
1872 the target of a dereference. */
1873 if (vi->address_taken || vi->indirect_target)
1876 /* See if all predecessors of I are ripe for elimination */
1877 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[i], 0, k, bi)
1880 w = get_varinfo (k)->node;
1882 /* We can't eliminate the node if one of the predecessors is
1883 part of a different strongly connected component. */
1887 okay_to_elim = true;
1891 okay_to_elim = false;
1895 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1896 then Solution(i) is a subset of Solution (w), where w is a
1897 predecessor in the graph.
1898 Corollary: If all predecessors of i have the same
1899 points-to set, then i has that same points-to set as
1900 those predecessors. */
1901 tmp = BITMAP_ALLOC (NULL);
1902 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1903 get_varinfo (w)->solution);
1904 if (!bitmap_empty_p (tmp))
1906 okay_to_elim = false;
1915 VEC_iterate (constraint_edge_t, predvec, pred, ce);
1920 weight = *(get_graph_weights (graph, i, ce->dest));
1922 /* We can't eliminate variables that have nonzero weighted
1923 edges between them. */
1924 if (weight && bitmap_other_than_zero_bit_set (weight))
1926 okay_to_elim = false;
1929 w = get_varinfo (ce->dest)->node;
1931 /* We can't eliminate the node if one of the predecessors is
1932 part of a different strongly connected component. */
1936 okay_to_elim = true;
1940 okay_to_elim = false;
1944 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1945 then Solution(i) is a subset of Solution (w), where w is a
1946 predecessor in the graph.
1947 Corollary: If all predecessors of i have the same
1948 points-to set, then i has that same points-to set as
1949 those predecessors. */
1950 tmp = BITMAP_ALLOC (NULL);
1951 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1952 get_varinfo (w)->solution);
1953 if (!bitmap_empty_p (tmp))
1955 okay_to_elim = false;
1962 /* See if the root is different than the original node.
1963 If so, we've found an equivalence. */
1964 if (root != get_varinfo (i)->node && okay_to_elim)
1966 /* Found an equivalence */
1967 get_varinfo (i)->node = root;
1968 collapse_nodes (graph, root, i);
1969 if (dump_file && (dump_flags & TDF_DETAILS))
1970 fprintf (dump_file, "Collapsing %s into %s\n",
1971 get_varinfo (i)->name,
1972 get_varinfo (root)->name);
1973 stats.collapsed_vars++;
1977 bitmap_obstack_release (&iteration_obstack);
1978 free_topo_info (ti);
1981 /* Solve the constraint graph GRAPH using our worklist solver.
1982 This is based on the PW* family of solvers from the "Efficient Field
1983 Sensitive Pointer Analysis for C" paper.
1984 It works by iterating over all the graph nodes, processing the complex
1985 constraints and propagating the copy constraints, until everything stops
1986 changed. This corresponds to steps 6-8 in the solving list given above. */
1989 solve_graph (constraint_graph_t graph)
1991 unsigned int size = VEC_length (varinfo_t, varmap);
1994 changed_count = size;
1995 changed = sbitmap_alloc (size);
1996 sbitmap_ones (changed);
1998 /* The already collapsed/unreachable nodes will never change, so we
1999 need to account for them in changed_count. */
2000 for (i = 0; i < size; i++)
2001 if (get_varinfo (i)->node != i)
2004 while (changed_count > 0)
2007 struct topo_info *ti = init_topo_info ();
2010 bitmap_obstack_initialize (&iteration_obstack);
2014 /* We already did cycle elimination once, when we did
2015 variable substitution, so we don't need it again for the
2017 if (stats.iterations > 1)
2018 find_and_collapse_graph_cycles (graph, true);
2023 compute_topo_order (graph, ti);
2025 while (VEC_length (unsigned, ti->topo_order) != 0)
2027 i = VEC_pop (unsigned, ti->topo_order);
2028 gcc_assert (get_varinfo (i)->node == i);
2030 /* If the node has changed, we need to process the
2031 complex constraints and outgoing edges again. */
2032 if (TEST_BIT (changed, i))
2036 constraint_edge_t e = NULL;
2039 VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
2040 VEC(constraint_edge_t,heap) *succs;
2042 RESET_BIT (changed, i);
2045 /* Process the complex constraints */
2046 solution = get_varinfo (i)->solution;
2047 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2048 do_complex_constraint (graph, c, solution);
2050 /* Propagate solution to all successors. */
2051 succs = graph->succs[i];
2053 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[i], 0, j, bi)
2055 bitmap tmp = get_varinfo (j)->solution;
2058 flag = set_union_with_increment (tmp, solution, 0);
2062 get_varinfo (j)->solution = tmp;
2063 if (!TEST_BIT (changed, j))
2065 SET_BIT (changed, j);
2070 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
2072 bitmap tmp = get_varinfo (e->dest)->solution;
2075 bitmap weights = e->weights;
2078 gcc_assert (weights && !bitmap_empty_p (weights));
2079 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
2080 flag |= set_union_with_increment (tmp, solution, k);
2084 get_varinfo (e->dest)->solution = tmp;
2085 if (!TEST_BIT (changed, e->dest))
2087 SET_BIT (changed, e->dest);
2094 free_topo_info (ti);
2095 bitmap_obstack_release (&iteration_obstack);
2098 sbitmap_free (changed);
2102 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
2104 /* Map from trees to variable ids. */
2105 static htab_t id_for_tree;
2107 typedef struct tree_id
2113 /* Hash a tree id structure. */
2116 tree_id_hash (const void *p)
2118 const tree_id_t ta = (tree_id_t) p;
2119 return htab_hash_pointer (ta->t);
2122 /* Return true if the tree in P1 and the tree in P2 are the same. */
2125 tree_id_eq (const void *p1, const void *p2)
2127 const tree_id_t ta1 = (tree_id_t) p1;
2128 const tree_id_t ta2 = (tree_id_t) p2;
2129 return ta1->t == ta2->t;
2132 /* Insert ID as the variable id for tree T in the hashtable. */
2135 insert_id_for_tree (tree t, int id)
2138 struct tree_id finder;
2142 slot = htab_find_slot (id_for_tree, &finder, INSERT);
2143 gcc_assert (*slot == NULL);
2144 new_pair = xmalloc (sizeof (struct tree_id));
2147 *slot = (void *)new_pair;
2150 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
2151 exist in the hash table, return false, otherwise, return true and
2152 set *ID to the id we found. */
2155 lookup_id_for_tree (tree t, unsigned int *id)
2158 struct tree_id finder;
2161 pair = htab_find (id_for_tree, &finder);
2168 /* Return a printable name for DECL */
2171 alias_get_name (tree decl)
2173 const char *res = get_name (decl);
2175 int num_printed = 0;
2181 if (TREE_CODE (decl) == SSA_NAME)
2183 num_printed = asprintf (&temp, "%s_%u",
2184 alias_get_name (SSA_NAME_VAR (decl)),
2185 SSA_NAME_VERSION (decl));
2187 else if (DECL_P (decl))
2189 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2191 if (num_printed > 0)
2193 res = ggc_strdup (temp);
2199 /* Find the variable id for tree T in the hashtable.
2200 If T doesn't exist in the hash table, create an entry for it. */
2203 get_id_for_tree (tree t)
2206 struct tree_id finder;
2209 pair = htab_find (id_for_tree, &finder);
2211 return create_variable_info_for (t, alias_get_name (t));
2216 /* Get a constraint expression from an SSA_VAR_P node. */
2218 static struct constraint_expr
2219 get_constraint_exp_from_ssa_var (tree t)
2221 struct constraint_expr cexpr;
2223 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2225 /* For parameters, get at the points-to set for the actual parm
2227 if (TREE_CODE (t) == SSA_NAME
2228 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2229 && default_def (SSA_NAME_VAR (t)) == t)
2230 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
2232 cexpr.type = SCALAR;
2234 cexpr.var = get_id_for_tree (t);
2235 /* If we determine the result is "anything", and we know this is readonly,
2236 say it points to readonly memory instead. */
2237 if (cexpr.var == anything_id && TREE_READONLY (t))
2239 cexpr.type = ADDRESSOF;
2240 cexpr.var = readonly_id;
2247 /* Process a completed constraint T, and add it to the constraint
2251 process_constraint (constraint_t t)
2253 struct constraint_expr rhs = t->rhs;
2254 struct constraint_expr lhs = t->lhs;
2256 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2257 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2259 /* ANYTHING == ANYTHING is pointless. */
2260 if (lhs.var == anything_id && rhs.var == anything_id)
2263 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2264 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
2269 process_constraint (t);
2271 /* This can happen in our IR with things like n->a = *p */
2272 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2274 /* Split into tmp = *rhs, *lhs = tmp */
2275 tree rhsdecl = get_varinfo (rhs.var)->decl;
2276 tree pointertype = TREE_TYPE (rhsdecl);
2277 tree pointedtotype = TREE_TYPE (pointertype);
2278 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2279 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2281 /* If this is an aggregate of known size, we should have passed
2282 this off to do_structure_copy, and it should have broken it
2284 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
2285 || get_varinfo (rhs.var)->is_unknown_size_var);
2287 process_constraint (new_constraint (tmplhs, rhs));
2288 process_constraint (new_constraint (lhs, tmplhs));
2290 else if (rhs.type == ADDRESSOF)
2293 gcc_assert (rhs.offset == 0);
2295 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
2296 vi->address_taken = true;
2298 VEC_safe_push (constraint_t, heap, constraints, t);
2302 if (lhs.type != DEREF && rhs.type == DEREF)
2303 get_varinfo (lhs.var)->indirect_target = true;
2304 VEC_safe_push (constraint_t, heap, constraints, t);
2309 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2312 static unsigned HOST_WIDE_INT
2313 bitpos_of_field (const tree fdecl)
2316 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
2317 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
2320 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
2321 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
2325 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2326 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2329 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
2330 const unsigned HOST_WIDE_INT fieldsize,
2331 const unsigned HOST_WIDE_INT accesspos,
2332 const unsigned HOST_WIDE_INT accesssize)
2334 if (fieldpos == accesspos && fieldsize == accesssize)
2336 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
2338 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2344 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2347 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results)
2350 HOST_WIDE_INT bitsize = -1;
2351 HOST_WIDE_INT bitmaxsize = -1;
2352 HOST_WIDE_INT bitpos;
2354 struct constraint_expr *result;
2355 unsigned int beforelength = VEC_length (ce_s, *results);
2357 /* Some people like to do cute things like take the address of
2360 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2361 forzero = TREE_OPERAND (forzero, 0);
2363 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2365 struct constraint_expr temp;
2368 temp.var = integer_id;
2370 VEC_safe_push (ce_s, heap, *results, &temp);
2374 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2375 get_constraint_for (t, results);
2376 result = VEC_last (ce_s, *results);
2377 result->offset = bitpos;
2379 gcc_assert (beforelength + 1 == VEC_length (ce_s, *results));
2381 /* This can also happen due to weird offsetof type macros. */
2382 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2383 result->type = SCALAR;
2385 if (result->type == SCALAR)
2387 /* In languages like C, you can access one past the end of an
2388 array. You aren't allowed to dereference it, so we can
2389 ignore this constraint. When we handle pointer subtraction,
2390 we may have to do something cute here. */
2392 if (result->offset < get_varinfo (result->var)->fullsize)
2394 /* It's also not true that the constraint will actually start at the
2395 right offset, it may start in some padding. We only care about
2396 setting the constraint to the first actual field it touches, so
2399 for (curr = get_varinfo (result->var); curr; curr = curr->next)
2401 if (offset_overlaps_with_access (curr->offset, curr->size,
2402 result->offset, bitmaxsize))
2404 result->var = curr->id;
2408 /* assert that we found *some* field there. The user couldn't be
2409 accessing *only* padding. */
2410 /* Still the user could access one past the end of an array
2411 embedded in a struct resulting in accessing *only* padding. */
2412 gcc_assert (curr || ref_contains_array_ref (orig_t));
2415 if (dump_file && (dump_flags & TDF_DETAILS))
2416 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2423 /* Dereference the constraint expression CONS, and return the result.
2424 DEREF (ADDRESSOF) = SCALAR
2425 DEREF (SCALAR) = DEREF
2426 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2427 This is needed so that we can handle dereferencing DEREF constraints. */
2430 do_deref (VEC (ce_s, heap) **constraints)
2432 struct constraint_expr *c;
2434 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2436 if (c->type == SCALAR)
2438 else if (c->type == ADDRESSOF)
2440 else if (c->type == DEREF)
2442 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
2443 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2444 process_constraint (new_constraint (tmplhs, *c));
2445 c->var = tmplhs.var;
2453 /* Given a tree T, return the constraint expression for it. */
2456 get_constraint_for (tree t, VEC (ce_s, heap) **results)
2458 struct constraint_expr temp;
2460 /* x = integer is all glommed to a single variable, which doesn't
2461 point to anything by itself. That is, of course, unless it is an
2462 integer constant being treated as a pointer, in which case, we
2463 will return that this is really the addressof anything. This
2464 happens below, since it will fall into the default case. The only
2465 case we know something about an integer treated like a pointer is
2466 when it is the NULL pointer, and then we just say it points to
2468 if (TREE_CODE (t) == INTEGER_CST
2469 && !POINTER_TYPE_P (TREE_TYPE (t)))
2471 temp.var = integer_id;
2474 VEC_safe_push (ce_s, heap, *results, &temp);
2477 else if (TREE_CODE (t) == INTEGER_CST
2478 && integer_zerop (t))
2480 temp.var = nothing_id;
2481 temp.type = ADDRESSOF;
2483 VEC_safe_push (ce_s, heap, *results, &temp);
2487 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2489 case tcc_expression:
2491 switch (TREE_CODE (t))
2495 struct constraint_expr *c;
2497 tree exp = TREE_OPERAND (t, 0);
2499 get_constraint_for (exp, results);
2500 /* Make sure we capture constraints to all elements
2502 if ((handled_component_p (exp)
2503 && ref_contains_array_ref (exp))
2504 || TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE)
2506 struct constraint_expr *origrhs;
2508 struct constraint_expr tmp;
2510 gcc_assert (VEC_length (ce_s, *results) == 1);
2511 origrhs = VEC_last (ce_s, *results);
2513 VEC_pop (ce_s, *results);
2514 origvar = get_varinfo (origrhs->var);
2515 for (; origvar; origvar = origvar->next)
2517 tmp.var = origvar->id;
2518 VEC_safe_push (ce_s, heap, *results, &tmp);
2521 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2523 if (c->type == DEREF)
2526 c->type = ADDRESSOF;
2533 /* XXX: In interprocedural mode, if we didn't have the
2534 body, we would need to do *each pointer argument =
2536 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2539 tree heapvar = heapvar_lookup (t);
2541 if (heapvar == NULL)
2543 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2544 DECL_EXTERNAL (heapvar) = 1;
2545 add_referenced_tmp_var (heapvar);
2546 heapvar_insert (t, heapvar);
2549 temp.var = create_variable_info_for (heapvar,
2550 alias_get_name (heapvar));
2552 vi = get_varinfo (temp.var);
2553 vi->is_artificial_var = 1;
2554 vi->is_heap_var = 1;
2555 temp.type = ADDRESSOF;
2557 VEC_safe_push (ce_s, heap, *results, &temp);
2563 temp.type = ADDRESSOF;
2564 temp.var = anything_id;
2566 VEC_safe_push (ce_s, heap, *results, &temp);
2573 switch (TREE_CODE (t))
2577 get_constraint_for (TREE_OPERAND (t, 0), results);
2582 case ARRAY_RANGE_REF:
2584 get_constraint_for_component_ref (t, results);
2588 temp.type = ADDRESSOF;
2589 temp.var = anything_id;
2591 VEC_safe_push (ce_s, heap, *results, &temp);
2598 switch (TREE_CODE (t))
2602 case NON_LVALUE_EXPR:
2604 tree op = TREE_OPERAND (t, 0);
2606 /* Cast from non-pointer to pointers are bad news for us.
2607 Anything else, we see through */
2608 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2609 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2611 get_constraint_for (op, results);
2619 temp.type = ADDRESSOF;
2620 temp.var = anything_id;
2622 VEC_safe_push (ce_s, heap, *results, &temp);
2627 case tcc_exceptional:
2629 switch (TREE_CODE (t))
2633 get_constraint_for (PHI_RESULT (t), results);
2639 struct constraint_expr temp;
2640 temp = get_constraint_exp_from_ssa_var (t);
2641 VEC_safe_push (ce_s, heap, *results, &temp);
2647 temp.type = ADDRESSOF;
2648 temp.var = anything_id;
2650 VEC_safe_push (ce_s, heap, *results, &temp);
2655 case tcc_declaration:
2657 struct constraint_expr temp;
2658 temp = get_constraint_exp_from_ssa_var (t);
2659 VEC_safe_push (ce_s, heap, *results, &temp);
2664 temp.type = ADDRESSOF;
2665 temp.var = anything_id;
2667 VEC_safe_push (ce_s, heap, *results, &temp);
2674 /* Handle the structure copy case where we have a simple structure copy
2675 between LHS and RHS that is of SIZE (in bits)
2677 For each field of the lhs variable (lhsfield)
2678 For each field of the rhs variable at lhsfield.offset (rhsfield)
2679 add the constraint lhsfield = rhsfield
2681 If we fail due to some kind of type unsafety or other thing we
2682 can't handle, return false. We expect the caller to collapse the
2683 variable in that case. */
2686 do_simple_structure_copy (const struct constraint_expr lhs,
2687 const struct constraint_expr rhs,
2688 const unsigned HOST_WIDE_INT size)
2690 varinfo_t p = get_varinfo (lhs.var);
2691 unsigned HOST_WIDE_INT pstart, last;
2693 last = p->offset + size;
2694 for (; p && p->offset < last; p = p->next)
2697 struct constraint_expr templhs = lhs;
2698 struct constraint_expr temprhs = rhs;
2699 unsigned HOST_WIDE_INT fieldoffset;
2701 templhs.var = p->id;
2702 q = get_varinfo (temprhs.var);
2703 fieldoffset = p->offset - pstart;
2704 q = first_vi_for_offset (q, q->offset + fieldoffset);
2707 temprhs.var = q->id;
2708 process_constraint (new_constraint (templhs, temprhs));
2714 /* Handle the structure copy case where we have a structure copy between a
2715 aggregate on the LHS and a dereference of a pointer on the RHS
2716 that is of SIZE (in bits)
2718 For each field of the lhs variable (lhsfield)
2719 rhs.offset = lhsfield->offset
2720 add the constraint lhsfield = rhs
2724 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2725 const struct constraint_expr rhs,
2726 const unsigned HOST_WIDE_INT size)
2728 varinfo_t p = get_varinfo (lhs.var);
2729 unsigned HOST_WIDE_INT pstart,last;
2731 last = p->offset + size;
2733 for (; p && p->offset < last; p = p->next)
2736 struct constraint_expr templhs = lhs;
2737 struct constraint_expr temprhs = rhs;
2738 unsigned HOST_WIDE_INT fieldoffset;
2741 if (templhs.type == SCALAR)
2742 templhs.var = p->id;
2744 templhs.offset = p->offset;
2746 q = get_varinfo (temprhs.var);
2747 fieldoffset = p->offset - pstart;
2748 temprhs.offset += fieldoffset;
2749 process_constraint (new_constraint (templhs, temprhs));
2753 /* Handle the structure copy case where we have a structure copy
2754 between a aggregate on the RHS and a dereference of a pointer on
2755 the LHS that is of SIZE (in bits)
2757 For each field of the rhs variable (rhsfield)
2758 lhs.offset = rhsfield->offset
2759 add the constraint lhs = rhsfield
2763 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2764 const struct constraint_expr rhs,
2765 const unsigned HOST_WIDE_INT size)
2767 varinfo_t p = get_varinfo (rhs.var);
2768 unsigned HOST_WIDE_INT pstart,last;
2770 last = p->offset + size;
2772 for (; p && p->offset < last; p = p->next)
2775 struct constraint_expr templhs = lhs;
2776 struct constraint_expr temprhs = rhs;
2777 unsigned HOST_WIDE_INT fieldoffset;
2780 if (temprhs.type == SCALAR)
2781 temprhs.var = p->id;
2783 temprhs.offset = p->offset;
2785 q = get_varinfo (templhs.var);
2786 fieldoffset = p->offset - pstart;
2787 templhs.offset += fieldoffset;
2788 process_constraint (new_constraint (templhs, temprhs));
2792 /* Sometimes, frontends like to give us bad type information. This
2793 function will collapse all the fields from VAR to the end of VAR,
2794 into VAR, so that we treat those fields as a single variable.
2795 We return the variable they were collapsed into. */
2798 collapse_rest_of_var (unsigned int var)
2800 varinfo_t currvar = get_varinfo (var);
2803 for (field = currvar->next; field; field = field->next)
2806 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
2807 field->name, currvar->name);
2809 gcc_assert (!field->collapsed_to);
2810 field->collapsed_to = currvar;
2813 currvar->next = NULL;
2814 currvar->size = currvar->fullsize - currvar->offset;
2819 /* Handle aggregate copies by expanding into copies of the respective
2820 fields of the structures. */
2823 do_structure_copy (tree lhsop, tree rhsop)
2825 struct constraint_expr lhs, rhs, tmp;
2826 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
2828 unsigned HOST_WIDE_INT lhssize;
2829 unsigned HOST_WIDE_INT rhssize;
2831 get_constraint_for (lhsop, &lhsc);
2832 get_constraint_for (rhsop, &rhsc);
2833 gcc_assert (VEC_length (ce_s, lhsc) == 1);
2834 gcc_assert (VEC_length (ce_s, rhsc) == 1);
2835 lhs = *(VEC_last (ce_s, lhsc));
2836 rhs = *(VEC_last (ce_s, rhsc));
2838 VEC_free (ce_s, heap, lhsc);
2839 VEC_free (ce_s, heap, rhsc);
2841 /* If we have special var = x, swap it around. */
2842 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2849 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2850 possible it's something we could handle. However, most cases falling
2851 into this are dealing with transparent unions, which are slightly
2853 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2855 rhs.type = ADDRESSOF;
2856 rhs.var = anything_id;
2859 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2860 that special var. */
2861 if (rhs.var <= integer_id)
2863 for (p = get_varinfo (lhs.var); p; p = p->next)
2865 struct constraint_expr templhs = lhs;
2866 struct constraint_expr temprhs = rhs;
2868 if (templhs.type == SCALAR )
2869 templhs.var = p->id;
2871 templhs.offset += p->offset;
2872 process_constraint (new_constraint (templhs, temprhs));
2877 tree rhstype = TREE_TYPE (rhsop);
2878 tree lhstype = TREE_TYPE (lhsop);
2882 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
2883 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
2885 /* If we have a variably sized types on the rhs or lhs, and a deref
2886 constraint, add the constraint, lhsconstraint = &ANYTHING.
2887 This is conservatively correct because either the lhs is an unknown
2888 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2889 constraint, and every variable it can point to must be unknown sized
2890 anyway, so we don't need to worry about fields at all. */
2891 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2892 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2894 rhs.var = anything_id;
2895 rhs.type = ADDRESSOF;
2897 process_constraint (new_constraint (lhs, rhs));
2901 /* The size only really matters insofar as we don't set more or less of
2902 the variable. If we hit an unknown size var, the size should be the
2903 whole darn thing. */
2904 if (get_varinfo (rhs.var)->is_unknown_size_var)
2907 rhssize = TREE_INT_CST_LOW (rhstypesize);
2909 if (get_varinfo (lhs.var)->is_unknown_size_var)
2912 lhssize = TREE_INT_CST_LOW (lhstypesize);
2915 if (rhs.type == SCALAR && lhs.type == SCALAR)
2917 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
2919 lhs.var = collapse_rest_of_var (lhs.var);
2920 rhs.var = collapse_rest_of_var (rhs.var);
2925 process_constraint (new_constraint (lhs, rhs));
2928 else if (lhs.type != DEREF && rhs.type == DEREF)
2929 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2930 else if (lhs.type == DEREF && rhs.type != DEREF)
2931 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2934 tree pointedtotype = lhstype;
2937 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2938 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2939 do_structure_copy (tmpvar, rhsop);
2940 do_structure_copy (lhsop, tmpvar);
2945 /* Update related alias information kept in AI. This is used when
2946 building name tags, alias sets and deciding grouping heuristics.
2947 STMT is the statement to process. This function also updates
2948 ADDRESSABLE_VARS. */
2951 update_alias_info (tree stmt, struct alias_info *ai)
2954 use_operand_p use_p;
2956 bool stmt_escapes_p = is_escape_site (stmt, ai);
2959 /* Mark all the variables whose address are taken by the statement. */
2960 addr_taken = addresses_taken (stmt);
2963 bitmap_ior_into (addressable_vars, addr_taken);
2965 /* If STMT is an escape point, all the addresses taken by it are
2972 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
2973 mark_call_clobbered (referenced_var (i));
2977 /* Process each operand use. If an operand may be aliased, keep
2978 track of how many times it's being used. For pointers, determine
2979 whether they are dereferenced by the statement, or whether their
2980 value escapes, etc. */
2981 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2985 struct ptr_info_def *pi;
2986 bool is_store, is_potential_deref;
2987 unsigned num_uses, num_derefs;
2989 op = USE_FROM_PTR (use_p);
2991 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2992 to the set of addressable variables. */
2993 if (TREE_CODE (op) == ADDR_EXPR)
2995 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
2997 /* PHI nodes don't have annotations for pinning the set
2998 of addresses taken, so we collect them here.
3000 FIXME, should we allow PHI nodes to have annotations
3001 so that they can be treated like regular statements?
3002 Currently, they are treated as second-class
3004 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
3008 /* Ignore constants. */
3009 if (TREE_CODE (op) != SSA_NAME)
3012 var = SSA_NAME_VAR (op);
3013 v_ann = var_ann (var);
3015 /* The base variable of an ssa name must be a GIMPLE register, and thus
3016 it cannot be aliased. */
3017 gcc_assert (!may_be_aliased (var));
3019 /* We are only interested in pointers. */
3020 if (!POINTER_TYPE_P (TREE_TYPE (op)))
3023 pi = get_ptr_info (op);
3025 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3026 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
3028 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
3029 VARRAY_PUSH_TREE (ai->processed_ptrs, op);
3032 /* If STMT is a PHI node, then it will not have pointer
3033 dereferences and it will not be an escape point. */
3034 if (TREE_CODE (stmt) == PHI_NODE)
3037 /* Determine whether OP is a dereferenced pointer, and if STMT
3038 is an escape point, whether OP escapes. */
3039 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
3041 /* Handle a corner case involving address expressions of the
3042 form '&PTR->FLD'. The problem with these expressions is that
3043 they do not represent a dereference of PTR. However, if some
3044 other transformation propagates them into an INDIRECT_REF
3045 expression, we end up with '*(&PTR->FLD)' which is folded
3048 So, if the original code had no other dereferences of PTR,
3049 the aliaser will not create memory tags for it, and when
3050 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3051 memory operations will receive no V_MAY_DEF/VUSE operands.
3053 One solution would be to have count_uses_and_derefs consider
3054 &PTR->FLD a dereference of PTR. But that is wrong, since it
3055 is not really a dereference but an offset calculation.
3057 What we do here is to recognize these special ADDR_EXPR
3058 nodes. Since these expressions are never GIMPLE values (they
3059 are not GIMPLE invariants), they can only appear on the RHS
3060 of an assignment and their base address is always an
3061 INDIRECT_REF expression. */
3062 is_potential_deref = false;
3063 if (TREE_CODE (stmt) == MODIFY_EXPR
3064 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
3065 && !is_gimple_val (TREE_OPERAND (stmt, 1)))
3067 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3068 this represents a potential dereference of PTR. */
3069 tree rhs = TREE_OPERAND (stmt, 1);
3070 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3071 if (TREE_CODE (base) == INDIRECT_REF
3072 && TREE_OPERAND (base, 0) == op)
3073 is_potential_deref = true;
3076 if (num_derefs > 0 || is_potential_deref)
3078 /* Mark OP as dereferenced. In a subsequent pass,
3079 dereferenced pointers that point to a set of
3080 variables will be assigned a name tag to alias
3081 all the variables OP points to. */
3082 pi->is_dereferenced = 1;
3084 /* Keep track of how many time we've dereferenced each
3086 NUM_REFERENCES_INC (v_ann);
3088 /* If this is a store operation, mark OP as being
3089 dereferenced to store, otherwise mark it as being
3090 dereferenced to load. */
3092 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3094 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
3097 if (stmt_escapes_p && num_derefs < num_uses)
3099 /* If STMT is an escape point and STMT contains at
3100 least one direct use of OP, then the value of OP
3101 escapes and so the pointed-to variables need to
3102 be marked call-clobbered. */
3103 pi->value_escapes_p = 1;
3105 /* If the statement makes a function call, assume
3106 that pointer OP will be dereferenced in a store
3107 operation inside the called function. */
3108 if (get_call_expr_in (stmt))
3110 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3111 pi->is_dereferenced = 1;
3116 if (TREE_CODE (stmt) == PHI_NODE)
3119 /* Update reference counter for definitions to any
3120 potentially aliased variable. This is used in the alias
3121 grouping heuristics. */
3122 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3124 tree var = SSA_NAME_VAR (op);
3125 var_ann_t ann = var_ann (var);
3126 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3127 if (may_be_aliased (var))
3128 NUM_REFERENCES_INC (ann);
3132 /* Mark variables in V_MAY_DEF operands as being written to. */
3133 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
3135 tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
3136 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3141 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3142 Expressions of the type PTR + CST can be handled in two ways:
3144 1- If the constraint for PTR is ADDRESSOF for a non-structure
3145 variable, then we can use it directly because adding or
3146 subtracting a constant may not alter the original ADDRESSOF
3147 constraint (i.e., pointer arithmetic may not legally go outside
3148 an object's boundaries).
3150 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3151 then if CST is a compile-time constant that can be used as an
3152 offset, we can determine which sub-variable will be pointed-to
3155 Return true if the expression is handled. For any other kind of
3156 expression, return false so that each operand can be added as a
3157 separate constraint by the caller. */
3160 handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr)
3163 struct constraint_expr *c, *c2;
3166 VEC (ce_s, heap) *temp = NULL;
3167 unsigned int rhsoffset = 0;
3169 if (TREE_CODE (expr) != PLUS_EXPR)
3172 op0 = TREE_OPERAND (expr, 0);
3173 op1 = TREE_OPERAND (expr, 1);
3175 get_constraint_for (op0, &temp);
3176 if (POINTER_TYPE_P (TREE_TYPE (op0))
3177 && TREE_CODE (op1) == INTEGER_CST)
3179 rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
3183 for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
3184 for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
3186 if (c2->type == ADDRESSOF && rhsoffset != 0)
3188 varinfo_t temp = get_varinfo (c2->var);
3190 /* An access one after the end of an array is valid,
3191 so simply punt on accesses we cannot resolve. */
3192 temp = first_vi_for_offset (temp, rhsoffset);
3199 c2->offset = rhsoffset;
3200 process_constraint (new_constraint (*c, *c2));
3203 VEC_free (ce_s, heap, temp);
3209 /* Walk statement T setting up aliasing constraints according to the
3210 references found in T. This function is the main part of the
3211 constraint builder. AI points to auxiliary alias information used
3212 when building alias sets and computing alias grouping heuristics. */
3215 find_func_aliases (tree origt)
3218 VEC(ce_s, heap) *lhsc = NULL;
3219 VEC(ce_s, heap) *rhsc = NULL;
3220 struct constraint_expr *c;
3222 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
3223 t = TREE_OPERAND (t, 0);
3225 /* Now build constraints expressions. */
3226 if (TREE_CODE (t) == PHI_NODE)
3228 /* Only care about pointers and structures containing
3230 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
3231 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
3236 /* For a phi node, assign all the arguments to
3238 get_constraint_for (PHI_RESULT (t), &lhsc);
3239 for (i = 0; i < PHI_NUM_ARGS (t); i++)
3241 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
3242 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3244 struct constraint_expr *c2;
3245 while (VEC_length (ce_s, rhsc) > 0)
3247 c2 = VEC_last (ce_s, rhsc);
3248 process_constraint (new_constraint (*c, *c2));
3249 VEC_pop (ce_s, rhsc);
3255 /* In IPA mode, we need to generate constraints to pass call
3256 arguments through their calls. There are two case, either a
3257 modify_expr when we are returning a value, or just a plain
3258 call_expr when we are not. */
3259 else if (in_ipa_mode
3260 && ((TREE_CODE (t) == MODIFY_EXPR
3261 && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR
3262 && !(call_expr_flags (TREE_OPERAND (t, 1))
3263 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
3264 || (TREE_CODE (t) == CALL_EXPR
3265 && !(call_expr_flags (t)
3266 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))))
3276 if (TREE_CODE (t) == MODIFY_EXPR)
3278 lhsop = TREE_OPERAND (t, 0);
3279 rhsop = TREE_OPERAND (t, 1);
3286 decl = get_callee_fndecl (rhsop);
3288 /* If we can directly resolve the function being called, do so.
3289 Otherwise, it must be some sort of indirect expression that
3290 we should still be able to handle. */
3293 found = lookup_id_for_tree (decl, &varid);
3298 decl = TREE_OPERAND (rhsop, 0);
3299 found = lookup_id_for_tree (decl, &varid);
3303 /* Assign all the passed arguments to the appropriate incoming
3304 parameters of the function. */
3305 fi = get_varinfo (varid);
3306 arglist = TREE_OPERAND (rhsop, 1);
3308 for (;arglist; arglist = TREE_CHAIN (arglist))
3310 tree arg = TREE_VALUE (arglist);
3311 struct constraint_expr lhs ;
3312 struct constraint_expr *rhsp;
3314 get_constraint_for (arg, &rhsc);
3315 if (TREE_CODE (decl) != FUNCTION_DECL)
3324 lhs.var = first_vi_for_offset (fi, i)->id;
3327 while (VEC_length (ce_s, rhsc) != 0)
3329 rhsp = VEC_last (ce_s, rhsc);
3330 process_constraint (new_constraint (lhs, *rhsp));
3331 VEC_pop (ce_s, rhsc);
3335 /* If we are returning a value, assign it to the result. */
3338 struct constraint_expr rhs;
3339 struct constraint_expr *lhsp;
3342 get_constraint_for (lhsop, &lhsc);
3343 if (TREE_CODE (decl) != FUNCTION_DECL)
3352 rhs.var = first_vi_for_offset (fi, i)->id;
3355 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3356 process_constraint (new_constraint (*lhsp, rhs));
3359 /* Otherwise, just a regular assignment statement. */
3360 else if (TREE_CODE (t) == MODIFY_EXPR)
3362 tree lhsop = TREE_OPERAND (t, 0);
3363 tree rhsop = TREE_OPERAND (t, 1);
3366 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3367 && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
3369 do_structure_copy (lhsop, rhsop);
3373 /* Only care about operations with pointers, structures
3374 containing pointers, dereferences, and call expressions. */
3375 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
3376 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3377 || TREE_CODE (rhsop) == CALL_EXPR)
3379 get_constraint_for (lhsop, &lhsc);
3380 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
3382 /* RHS that consist of unary operations,
3383 exceptional types, or bare decls/constants, get
3384 handled directly by get_constraint_for. */
3386 case tcc_declaration:
3388 case tcc_exceptional:
3389 case tcc_expression:
3393 tree strippedrhs = rhsop;
3396 /* XXX: Push this back into the ADDR_EXPR
3397 case, and remove anyoffset handling. */
3398 STRIP_NOPS (strippedrhs);
3399 rhstype = TREE_TYPE (strippedrhs);
3401 get_constraint_for (rhsop, &rhsc);
3402 if (TREE_CODE (strippedrhs) == ADDR_EXPR
3403 && AGGREGATE_TYPE_P (TREE_TYPE (rhstype))
3404 && VEC_length (ce_s, rhsc) == 1)
3406 struct constraint_expr *origrhs;
3408 struct constraint_expr tmp;
3410 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3411 origrhs = VEC_last (ce_s, rhsc);
3413 VEC_pop (ce_s, rhsc);
3414 origvar = get_varinfo (origrhs->var);
3415 for (; origvar; origvar = origvar->next)
3417 tmp.var = origvar->id;
3418 VEC_safe_push (ce_s, heap, rhsc, &tmp);
3422 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3424 struct constraint_expr *c2;
3427 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3428 process_constraint (new_constraint (*c, *c2));
3436 /* For pointer arithmetic of the form
3437 PTR + CST, we can simply use PTR's
3438 constraint because pointer arithmetic is
3439 not allowed to go out of bounds. */
3440 if (handle_ptr_arith (lhsc, rhsop))
3445 /* Otherwise, walk each operand. Notice that we
3446 can't use the operand interface because we need
3447 to process expressions other than simple operands
3448 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3450 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
3452 tree op = TREE_OPERAND (rhsop, i);
3455 gcc_assert (VEC_length (ce_s, rhsc) == 0);
3456 get_constraint_for (op, &rhsc);
3457 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3459 struct constraint_expr *c2;
3460 while (VEC_length (ce_s, rhsc) > 0)
3462 c2 = VEC_last (ce_s, rhsc);
3463 process_constraint (new_constraint (*c, *c2));
3464 VEC_pop (ce_s, rhsc);
3473 /* After promoting variables and computing aliasing we will
3474 need to re-scan most statements. FIXME: Try to minimize the
3475 number of statements re-scanned. It's not really necessary to
3476 re-scan *all* statements. */
3477 mark_stmt_modified (origt);
3478 VEC_free (ce_s, heap, rhsc);
3479 VEC_free (ce_s, heap, lhsc);
3483 /* Find the first varinfo in the same variable as START that overlaps with
3485 Effectively, walk the chain of fields for the variable START to find the
3486 first field that overlaps with OFFSET.
3487 Return NULL if we can't find one. */
3490 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3492 varinfo_t curr = start;
3495 /* We may not find a variable in the field list with the actual
3496 offset when when we have glommed a structure to a variable.
3497 In that case, however, offset should still be within the size
3499 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3507 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3511 insert_into_field_list (varinfo_t base, varinfo_t field)
3513 varinfo_t prev = base;
3514 varinfo_t curr = base->next;
3525 if (field->offset <= curr->offset)
3530 field->next = prev->next;
3535 /* qsort comparison function for two fieldoff's PA and PB */
3538 fieldoff_compare (const void *pa, const void *pb)
3540 const fieldoff_s *foa = (const fieldoff_s *)pa;
3541 const fieldoff_s *fob = (const fieldoff_s *)pb;
3542 HOST_WIDE_INT foasize, fobsize;
3544 if (foa->offset != fob->offset)
3545 return foa->offset - fob->offset;
3547 foasize = TREE_INT_CST_LOW (foa->size);
3548 fobsize = TREE_INT_CST_LOW (fob->size);
3549 return foasize - fobsize;
3552 /* Sort a fieldstack according to the field offset and sizes. */
3553 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3555 qsort (VEC_address (fieldoff_s, fieldstack),
3556 VEC_length (fieldoff_s, fieldstack),
3557 sizeof (fieldoff_s),
3561 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3562 of TYPE onto fieldstack, recording their offsets along the way.
3563 OFFSET is used to keep track of the offset in this entire structure, rather
3564 than just the immediately containing structure. Returns the number
3566 HAS_UNION is set to true if we find a union type as a field of
3570 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
3571 HOST_WIDE_INT offset, bool *has_union)
3576 if (TREE_CODE (type) == COMPLEX_TYPE)
3578 fieldoff_s *real_part, *img_part;
3579 real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3580 real_part->type = TREE_TYPE (type);
3581 real_part->size = TYPE_SIZE (TREE_TYPE (type));
3582 real_part->offset = offset;
3583 real_part->decl = NULL_TREE;
3585 img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3586 img_part->type = TREE_TYPE (type);
3587 img_part->size = TYPE_SIZE (TREE_TYPE (type));
3588 img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
3589 img_part->decl = NULL_TREE;
3594 if (TREE_CODE (type) == ARRAY_TYPE)
3596 tree sz = TYPE_SIZE (type);
3597 tree elsz = TYPE_SIZE (TREE_TYPE (type));
3602 || ! host_integerp (sz, 1)
3603 || TREE_INT_CST_LOW (sz) == 0
3605 || ! host_integerp (elsz, 1)
3606 || TREE_INT_CST_LOW (elsz) == 0)
3609 nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
3610 if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
3613 for (i = 0; i < nr; ++i)
3619 && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
3620 || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
3623 if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
3625 else if (!(pushed = push_fields_onto_fieldstack
3626 (TREE_TYPE (type), fieldstack,
3627 offset + i * TREE_INT_CST_LOW (elsz), has_union)))
3628 /* Empty structures may have actual size, like in C++. So
3629 see if we didn't push any subfields and the size is
3630 nonzero, push the field onto the stack */
3637 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3638 pair->type = TREE_TYPE (type);
3640 pair->decl = NULL_TREE;
3641 pair->offset = offset + i * TREE_INT_CST_LOW (elsz);
3651 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
3652 if (TREE_CODE (field) == FIELD_DECL)
3658 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3659 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3662 if (!var_can_have_subvars (field))
3664 else if (!(pushed = push_fields_onto_fieldstack
3665 (TREE_TYPE (field), fieldstack,
3666 offset + bitpos_of_field (field), has_union))
3667 && DECL_SIZE (field)
3668 && !integer_zerop (DECL_SIZE (field)))
3669 /* Empty structures may have actual size, like in C++. So
3670 see if we didn't push any subfields and the size is
3671 nonzero, push the field onto the stack */
3678 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3679 pair->type = TREE_TYPE (field);
3680 pair->size = DECL_SIZE (field);
3682 pair->offset = offset + bitpos_of_field (field);
3693 make_constraint_to_anything (varinfo_t vi)
3695 struct constraint_expr lhs, rhs;
3701 rhs.var = anything_id;
3703 rhs.type = ADDRESSOF;
3704 process_constraint (new_constraint (lhs, rhs));
3707 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3708 if it is a varargs function. */
3711 count_num_arguments (tree decl, bool *is_varargs)
3716 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
3720 if (TREE_VALUE (t) == void_type_node)
3730 /* Creation function node for DECL, using NAME, and return the index
3731 of the variable we've created for the function. */
3734 create_function_info_for (tree decl, const char *name)
3736 unsigned int index = VEC_length (varinfo_t, varmap);
3740 bool is_varargs = false;
3742 /* Create the variable info. */
3744 vi = new_var_info (decl, index, name, index);
3749 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3750 insert_id_for_tree (vi->decl, index);
3751 VEC_safe_push (varinfo_t, heap, varmap, vi);
3755 /* If it's varargs, we don't know how many arguments it has, so we
3762 vi->is_unknown_size_var = true;
3767 arg = DECL_ARGUMENTS (decl);
3769 /* Set up variables for each argument. */
3770 for (i = 1; i < vi->fullsize; i++)
3773 const char *newname;
3775 unsigned int newindex;
3776 tree argdecl = decl;
3781 newindex = VEC_length (varinfo_t, varmap);
3782 asprintf (&tempname, "%s.arg%d", name, i-1);
3783 newname = ggc_strdup (tempname);
3786 argvi = new_var_info (argdecl, newindex,newname, newindex);
3787 argvi->decl = argdecl;
3788 VEC_safe_push (varinfo_t, heap, varmap, argvi);
3791 argvi->fullsize = vi->fullsize;
3792 argvi->has_union = false;
3793 insert_into_field_list (vi, argvi);
3794 stats.total_vars ++;
3797 insert_id_for_tree (arg, newindex);
3798 arg = TREE_CHAIN (arg);
3802 /* Create a variable for the return var. */
3803 if (DECL_RESULT (decl) != NULL
3804 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
3807 const char *newname;
3809 unsigned int newindex;
3810 tree resultdecl = decl;
3815 if (DECL_RESULT (decl))
3816 resultdecl = DECL_RESULT (decl);
3818 newindex = VEC_length (varinfo_t, varmap);
3819 asprintf (&tempname, "%s.result", name);
3820 newname = ggc_strdup (tempname);
3823 resultvi = new_var_info (resultdecl, newindex, newname, newindex);
3824 resultvi->decl = resultdecl;
3825 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
3826 resultvi->offset = i;
3828 resultvi->fullsize = vi->fullsize;
3829 resultvi->has_union = false;
3830 insert_into_field_list (vi, resultvi);
3831 stats.total_vars ++;
3832 if (DECL_RESULT (decl))
3833 insert_id_for_tree (DECL_RESULT (decl), newindex);
3839 /* Return true if FIELDSTACK contains fields that overlap.
3840 FIELDSTACK is assumed to be sorted by offset. */
3843 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
3845 fieldoff_s *fo = NULL;
3847 HOST_WIDE_INT lastoffset = -1;
3849 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3851 if (fo->offset == lastoffset)
3853 lastoffset = fo->offset;
3858 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3859 This will also create any varinfo structures necessary for fields
3863 create_variable_info_for (tree decl, const char *name)
3865 unsigned int index = VEC_length (varinfo_t, varmap);
3867 tree decltype = TREE_TYPE (decl);
3868 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
3869 bool notokay = false;
3871 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
3872 VEC (fieldoff_s,heap) *fieldstack = NULL;
3874 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
3875 return create_function_info_for (decl, name);
3877 hasunion = TREE_CODE (decltype) == UNION_TYPE
3878 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
3879 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
3881 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
3884 VEC_free (fieldoff_s, heap, fieldstack);
3890 /* If the variable doesn't have subvars, we may end up needing to
3891 sort the field list and create fake variables for all the
3893 vi = new_var_info (decl, index, name, index);
3896 vi->has_union = hasunion;
3898 || TREE_CODE (declsize) != INTEGER_CST
3899 || TREE_CODE (decltype) == UNION_TYPE
3900 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
3902 vi->is_unknown_size_var = true;
3908 vi->fullsize = TREE_INT_CST_LOW (declsize);
3909 vi->size = vi->fullsize;
3912 insert_id_for_tree (vi->decl, index);
3913 VEC_safe_push (varinfo_t, heap, varmap, vi);
3914 if (is_global && (!flag_whole_program || !in_ipa_mode))
3915 make_constraint_to_anything (vi);
3918 if (use_field_sensitive
3920 && !vi->is_unknown_size_var
3921 && var_can_have_subvars (decl))
3923 unsigned int newindex = VEC_length (varinfo_t, varmap);
3924 fieldoff_s *fo = NULL;
3927 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3930 || TREE_CODE (fo->size) != INTEGER_CST
3938 /* We can't sort them if we have a field with a variable sized type,
3939 which will make notokay = true. In that case, we are going to return
3940 without creating varinfos for the fields anyway, so sorting them is a
3944 sort_fieldstack (fieldstack);
3945 /* Due to some C++ FE issues, like PR 22488, we might end up
3946 what appear to be overlapping fields even though they,
3947 in reality, do not overlap. Until the C++ FE is fixed,
3948 we will simply disable field-sensitivity for these cases. */
3949 notokay = check_for_overlaps (fieldstack);
3953 if (VEC_length (fieldoff_s, fieldstack) != 0)
3954 fo = VEC_index (fieldoff_s, fieldstack, 0);
3956 if (fo == NULL || notokay)
3958 vi->is_unknown_size_var = 1;
3961 VEC_free (fieldoff_s, heap, fieldstack);
3965 vi->size = TREE_INT_CST_LOW (fo->size);
3966 vi->offset = fo->offset;
3967 for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3970 const char *newname;
3973 newindex = VEC_length (varinfo_t, varmap);
3975 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (fo->decl));
3977 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC, vi->name, fo->offset);
3978 newname = ggc_strdup (tempname);
3980 newvi = new_var_info (decl, newindex, newname, newindex);
3981 newvi->offset = fo->offset;
3982 newvi->size = TREE_INT_CST_LOW (fo->size);
3983 newvi->fullsize = vi->fullsize;
3984 insert_into_field_list (vi, newvi);
3985 VEC_safe_push (varinfo_t, heap, varmap, newvi);
3986 if (is_global && (!flag_whole_program || !in_ipa_mode))
3987 make_constraint_to_anything (newvi);
3991 VEC_free (fieldoff_s, heap, fieldstack);
3996 /* Print out the points-to solution for VAR to FILE. */
3999 dump_solution_for_var (FILE *file, unsigned int var)
4001 varinfo_t vi = get_varinfo (var);
4005 fprintf (file, "%s = { ", vi->name);
4006 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
4008 fprintf (file, "%s ", get_varinfo (i)->name);
4010 fprintf (file, "}\n");
4013 /* Print the points-to solution for VAR to stdout. */
4016 debug_solution_for_var (unsigned int var)
4018 dump_solution_for_var (stdout, var);
4022 /* Create varinfo structures for all of the variables in the
4023 function for intraprocedural mode. */
4026 intra_create_variable_infos (void)
4030 /* For each incoming argument arg, ARG = &ANYTHING */
4031 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4033 struct constraint_expr lhs;
4038 lhs.var = create_variable_info_for (t, alias_get_name (t));
4040 for (p = get_varinfo (lhs.var); p; p = p->next)
4041 make_constraint_to_anything (p);
4046 /* Set bits in INTO corresponding to the variable uids in solution set
4050 set_uids_in_ptset (bitmap into, bitmap from)
4056 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4058 varinfo_t vi = get_varinfo (i);
4060 /* The only artificial variables that are allowed in a may-alias
4061 set are heap variables. */
4062 if (vi->is_artificial_var && !vi->is_heap_var)
4065 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
4067 /* Variables containing unions may need to be converted to
4068 their SFT's, because SFT's can have unions and we cannot. */
4069 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
4070 bitmap_set_bit (into, DECL_UID (sv->var));
4072 else if (TREE_CODE (vi->decl) == VAR_DECL
4073 || TREE_CODE (vi->decl) == PARM_DECL)
4075 if (var_can_have_subvars (vi->decl)
4076 && get_subvars_for_var (vi->decl))
4078 /* If VI->DECL is an aggregate for which we created
4079 SFTs, add the SFT corresponding to VI->OFFSET. */
4080 tree sft = get_subvar_at (vi->decl, vi->offset);
4082 bitmap_set_bit (into, DECL_UID (sft));
4086 /* Otherwise, just add VI->DECL to the alias set. */
4087 bitmap_set_bit (into, DECL_UID (vi->decl));
4094 static bool have_alias_info = false;
4096 /* Given a pointer variable P, fill in its points-to set, or return
4097 false if we can't. */
4100 find_what_p_points_to (tree p)
4102 unsigned int id = 0;
4104 if (!have_alias_info)
4107 if (lookup_id_for_tree (p, &id))
4109 varinfo_t vi = get_varinfo (id);
4111 if (vi->is_artificial_var)
4114 /* See if this is a field or a structure. */
4115 if (vi->size != vi->fullsize)
4117 /* Nothing currently asks about structure fields directly,
4118 but when they do, we need code here to hand back the
4120 if (!var_can_have_subvars (vi->decl)
4121 || get_subvars_for_var (vi->decl) == NULL)
4126 struct ptr_info_def *pi = get_ptr_info (p);
4130 /* This variable may have been collapsed, let's get the real
4132 vi = get_varinfo (vi->node);
4134 /* Translate artificial variables into SSA_NAME_PTR_INFO
4136 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4138 varinfo_t vi = get_varinfo (i);
4140 if (vi->is_artificial_var)
4142 /* FIXME. READONLY should be handled better so that
4143 flow insensitive aliasing can disregard writable
4145 if (vi->id == nothing_id)
4147 else if (vi->id == anything_id)
4148 pi->pt_anything = 1;
4149 else if (vi->id == readonly_id)
4150 pi->pt_anything = 1;
4151 else if (vi->id == integer_id)
4152 pi->pt_anything = 1;
4153 else if (vi->is_heap_var)
4154 pi->pt_global_mem = 1;
4158 if (pi->pt_anything)
4162 pi->pt_vars = BITMAP_GGC_ALLOC ();
4164 set_uids_in_ptset (pi->pt_vars, vi->solution);
4166 if (bitmap_empty_p (pi->pt_vars))
4178 /* Dump points-to information to OUTFILE. */
4181 dump_sa_points_to_info (FILE *outfile)
4185 fprintf (outfile, "\nPoints-to sets\n\n");
4187 if (dump_flags & TDF_STATS)
4189 fprintf (outfile, "Stats:\n");
4190 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4191 fprintf (outfile, "Statically unified vars: %d\n",
4192 stats.unified_vars_static);
4193 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
4194 fprintf (outfile, "Dynamically unified vars: %d\n",
4195 stats.unified_vars_dynamic);
4196 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4197 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4200 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4201 dump_solution_for_var (outfile, i);
4205 /* Debug points-to information to stderr. */
4208 debug_sa_points_to_info (void)
4210 dump_sa_points_to_info (stderr);
4214 /* Initialize the always-existing constraint variables for NULL
4215 ANYTHING, READONLY, and INTEGER */
4218 init_base_vars (void)
4220 struct constraint_expr lhs, rhs;
4222 /* Create the NULL variable, used to represent that a variable points
4224 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4225 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
4226 insert_id_for_tree (nothing_tree, 0);
4227 var_nothing->is_artificial_var = 1;
4228 var_nothing->offset = 0;
4229 var_nothing->size = ~0;
4230 var_nothing->fullsize = ~0;
4231 var_nothing->is_special_var = 1;
4233 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
4235 /* Create the ANYTHING variable, used to represent that a variable
4236 points to some unknown piece of memory. */
4237 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4238 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
4239 insert_id_for_tree (anything_tree, 1);
4240 var_anything->is_artificial_var = 1;
4241 var_anything->size = ~0;
4242 var_anything->offset = 0;
4243 var_anything->next = NULL;
4244 var_anything->fullsize = ~0;
4245 var_anything->is_special_var = 1;
4248 /* Anything points to anything. This makes deref constraints just
4249 work in the presence of linked list and other p = *p type loops,
4250 by saying that *ANYTHING = ANYTHING. */
4251 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
4253 lhs.var = anything_id;
4255 rhs.type = ADDRESSOF;
4256 rhs.var = anything_id;
4258 var_anything->address_taken = true;
4260 /* This specifically does not use process_constraint because
4261 process_constraint ignores all anything = anything constraints, since all
4262 but this one are redundant. */
4263 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
4265 /* Create the READONLY variable, used to represent that a variable
4266 points to readonly memory. */
4267 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4268 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
4269 var_readonly->is_artificial_var = 1;
4270 var_readonly->offset = 0;
4271 var_readonly->size = ~0;
4272 var_readonly->fullsize = ~0;
4273 var_readonly->next = NULL;
4274 var_readonly->is_special_var = 1;
4275 insert_id_for_tree (readonly_tree, 2);
4277 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4279 /* readonly memory points to anything, in order to make deref
4280 easier. In reality, it points to anything the particular
4281 readonly variable can point to, but we don't track this
4284 lhs.var = readonly_id;
4286 rhs.type = ADDRESSOF;
4287 rhs.var = anything_id;
4290 process_constraint (new_constraint (lhs, rhs));
4292 /* Create the INTEGER variable, used to represent that a variable points
4294 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4295 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
4296 insert_id_for_tree (integer_tree, 3);
4297 var_integer->is_artificial_var = 1;
4298 var_integer->size = ~0;
4299 var_integer->fullsize = ~0;
4300 var_integer->offset = 0;
4301 var_integer->next = NULL;
4302 var_integer->is_special_var = 1;
4304 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
4306 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
4307 integer will point to. */
4309 lhs.var = integer_id;
4311 rhs.type = ADDRESSOF;
4312 rhs.var = anything_id;
4314 process_constraint (new_constraint (lhs, rhs));
4317 /* Return true if we actually need to solve the constraint graph in order to
4318 get our points-to sets. This is false when, for example, no addresses are
4319 taken other than special vars, or all points-to sets with members already
4320 contain the anything variable and there are no predecessors for other
4324 need_to_solve (void)
4328 bool found_address_taken = false;
4329 bool found_non_anything = false;
4331 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4333 if (v->is_special_var)
4336 if (v->address_taken)
4337 found_address_taken = true;
4340 && !bitmap_empty_p (v->solution)
4341 && !bitmap_bit_p (v->solution, anything_id))
4342 found_non_anything = true;
4343 else if (bitmap_empty_p (v->solution)
4344 && (VEC_length (constraint_edge_t, graph->preds[v->id]) != 0
4345 || (graph->zero_weight_preds[v->id] && !bitmap_empty_p (graph->zero_weight_preds[v->id]))))
4346 found_non_anything = true;
4348 if (found_address_taken && found_non_anything)
4355 /* Initialize things necessary to perform PTA */
4358 init_alias_vars (void)
4360 bitmap_obstack_initialize (&ptabitmap_obstack);
4361 bitmap_obstack_initialize (&predbitmap_obstack);
4363 constraint_pool = create_alloc_pool ("Constraint pool",
4364 sizeof (struct constraint), 30);
4365 variable_info_pool = create_alloc_pool ("Variable info pool",
4366 sizeof (struct variable_info), 30);
4367 constraint_edge_pool = create_alloc_pool ("Constraint edges",
4368 sizeof (struct constraint_edge), 30);
4370 constraints = VEC_alloc (constraint_t, heap, 8);
4371 varmap = VEC_alloc (varinfo_t, heap, 8);
4372 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
4373 memset (&stats, 0, sizeof (stats));
4379 /* Create points-to sets for the current function. See the comments
4380 at the start of the file for an algorithmic overview. */
4383 compute_points_to_sets (struct alias_info *ai)
4387 timevar_push (TV_TREE_PTA);
4391 intra_create_variable_infos ();
4393 /* Now walk all statements and derive aliases. */
4396 block_stmt_iterator bsi;
4399 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4401 if (is_gimple_reg (PHI_RESULT (phi)))
4403 find_func_aliases (phi);
4404 /* Update various related attributes like escaped
4405 addresses, pointer dereferences for loads and stores.
4406 This is used when creating name tags and alias
4408 update_alias_info (phi, ai);
4412 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4414 tree stmt = bsi_stmt (bsi);
4415 find_func_aliases (stmt);
4416 /* Update various related attributes like escaped
4417 addresses, pointer dereferences for loads and stores.
4418 This is used when creating name tags and alias
4420 update_alias_info (stmt, ai);
4424 build_constraint_graph ();
4428 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4429 dump_constraints (dump_file);
4432 if (need_to_solve ())
4436 "\nCollapsing static cycles and doing variable "
4439 find_and_collapse_graph_cycles (graph, false);
4440 perform_var_substitution (graph);
4443 fprintf (dump_file, "\nSolving graph:\n");
4445 solve_graph (graph);
4449 dump_sa_points_to_info (dump_file);
4451 have_alias_info = true;
4453 timevar_pop (TV_TREE_PTA);
4457 /* Delete created points-to sets. */
4460 delete_points_to_sets (void)
4465 htab_delete (id_for_tree);
4466 bitmap_obstack_release (&ptabitmap_obstack);
4467 bitmap_obstack_release (&predbitmap_obstack);
4468 VEC_free (constraint_t, heap, constraints);
4470 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4472 VEC_free (constraint_edge_t, heap, graph->succs[i]);
4473 VEC_free (constraint_edge_t, heap, graph->preds[i]);
4474 VEC_free (constraint_t, heap, v->complex);
4476 free (graph->zero_weight_preds);
4477 free (graph->zero_weight_succs);
4478 free (graph->succs);
4479 free (graph->preds);
4482 VEC_free (varinfo_t, heap, varmap);
4483 free_alloc_pool (variable_info_pool);
4484 free_alloc_pool (constraint_pool);
4485 free_alloc_pool (constraint_edge_pool);
4487 have_alias_info = false;
4490 /* Return true if we should execute IPA PTA. */
4494 return (flag_unit_at_a_time != 0
4495 /* Don't bother doing anything if the program has errors. */
4496 && !(errorcount || sorrycount));
4499 /* Execute the driver for IPA PTA. */
4501 ipa_pta_execute (void)
4503 struct cgraph_node *node;
4508 for (node = cgraph_nodes; node; node = node->next)
4510 if (!node->analyzed || cgraph_is_master_clone (node))
4514 varid = create_function_info_for (node->decl,
4515 cgraph_node_name (node));
4516 if (node->local.externally_visible)
4518 varinfo_t fi = get_varinfo (varid);
4519 for (; fi; fi = fi->next)
4520 make_constraint_to_anything (fi);
4524 for (node = cgraph_nodes; node; node = node->next)
4526 if (node->analyzed && cgraph_is_master_clone (node))
4528 struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
4530 tree old_func_decl = current_function_decl;
4533 "Generating constraints for %s\n",
4534 cgraph_node_name (node));
4536 current_function_decl = node->decl;
4538 FOR_EACH_BB_FN (bb, cfun)
4540 block_stmt_iterator bsi;
4543 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4545 if (is_gimple_reg (PHI_RESULT (phi)))
4547 find_func_aliases (phi);
4551 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4553 tree stmt = bsi_stmt (bsi);
4554 find_func_aliases (stmt);
4557 current_function_decl = old_func_decl;
4562 /* Make point to anything. */
4566 build_constraint_graph ();
4570 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4571 dump_constraints (dump_file);
4574 if (need_to_solve ())
4578 "\nCollapsing static cycles and doing variable "
4581 find_and_collapse_graph_cycles (graph, false);
4582 perform_var_substitution (graph);
4585 fprintf (dump_file, "\nSolving graph:\n");
4587 solve_graph (graph);
4591 dump_sa_points_to_info (dump_file);
4595 struct tree_opt_pass pass_ipa_pta =
4598 gate_ipa_pta, /* gate */
4599 ipa_pta_execute, /* execute */
4602 0, /* static_pass_number */
4603 TV_IPA_PTA, /* tv_id */
4604 0, /* properties_required */
4605 0, /* properties_provided */
4606 0, /* properties_destroyed */
4607 0, /* todo_flags_start */
4608 0, /* todo_flags_finish */
4612 /* Initialize the heapvar for statement mapping. */
4614 init_alias_heapvars (void)
4616 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq, NULL);
4620 delete_alias_heapvars (void)
4622 htab_delete (heapvar_for_stmt);
4626 #include "gt-tree-ssa-structalias.h"