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 = XNEW (struct constraint_graph);
1184 graph->succs = XCNEWVEC (VEC(constraint_edge_t,heap) *, VEC_length (varinfo_t, varmap) + 1);
1185 graph->preds = XCNEWVEC (VEC(constraint_edge_t,heap) *, VEC_length (varinfo_t, varmap) + 1);
1186 graph->zero_weight_succs = XCNEWVEC (bitmap, VEC_length (varinfo_t, varmap) + 1);
1187 graph->zero_weight_preds = XCNEWVEC (bitmap, VEC_length (varinfo_t, varmap) + 1);
1189 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1191 struct constraint_expr lhs = c->lhs;
1192 struct constraint_expr rhs = c->rhs;
1193 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
1194 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
1196 if (lhs.type == DEREF)
1198 /* *x = y or *x = &y (complex) */
1199 if (rhs.type == ADDRESSOF || rhsvar > anything_id)
1200 insert_into_complex (lhsvar, c);
1202 else if (rhs.type == DEREF)
1204 /* !special var= *y */
1205 if (!(get_varinfo (lhsvar)->is_special_var))
1206 insert_into_complex (rhsvar, c);
1208 else if (rhs.type == ADDRESSOF)
1211 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1213 else if (lhsvar > anything_id)
1215 /* Ignore 0 weighted self edges, as they can't possibly contribute
1217 if (lhsvar != rhsvar || rhs.offset != 0 || lhs.offset != 0)
1219 /* x = y (simple) */
1220 int_add_graph_edge (graph, lhs.var, rhs.var, rhs.offset);
1228 /* Changed variables on the last iteration. */
1229 static unsigned int changed_count;
1230 static sbitmap changed;
1232 DEF_VEC_I(unsigned);
1233 DEF_VEC_ALLOC_I(unsigned,heap);
1236 /* Strongly Connected Component visitation info. */
1241 sbitmap in_component;
1243 unsigned int *visited_index;
1244 VEC(unsigned,heap) *scc_stack;
1245 VEC(unsigned,heap) *unification_queue;
1249 /* Recursive routine to find strongly connected components in GRAPH.
1250 SI is the SCC info to store the information in, and N is the id of current
1251 graph node we are processing.
1253 This is Tarjan's strongly connected component finding algorithm, as
1254 modified by Nuutila to keep only non-root nodes on the stack.
1255 The algorithm can be found in "On finding the strongly connected
1256 connected components in a directed graph" by Esko Nuutila and Eljas
1257 Soisalon-Soininen, in Information Processing Letters volume 49,
1258 number 1, pages 9-14. */
1261 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1266 gcc_assert (get_varinfo (n)->node == n);
1267 SET_BIT (si->visited, n);
1268 RESET_BIT (si->in_component, n);
1269 si->visited_index[n] = si->current_index ++;
1271 /* Visit all the successors. */
1272 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[n], 0, i, bi)
1275 if (!TEST_BIT (si->visited, w))
1276 scc_visit (graph, si, w);
1277 if (!TEST_BIT (si->in_component, w))
1279 unsigned int t = get_varinfo (w)->node;
1280 unsigned int nnode = get_varinfo (n)->node;
1281 if (si->visited_index[t] < si->visited_index[nnode])
1282 get_varinfo (n)->node = t;
1286 /* See if any components have been identified. */
1287 if (get_varinfo (n)->node == n)
1289 unsigned int t = si->visited_index[n];
1290 SET_BIT (si->in_component, n);
1291 while (VEC_length (unsigned, si->scc_stack) != 0
1292 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
1294 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1295 get_varinfo (w)->node = n;
1296 SET_BIT (si->in_component, w);
1297 /* Mark this node for collapsing. */
1298 VEC_safe_push (unsigned, heap, si->unification_queue, w);
1302 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1306 /* Collapse two variables into one variable. */
1309 collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
1311 bitmap tosol, fromsol;
1313 condense_varmap_nodes (to, from);
1314 tosol = get_varinfo (to)->solution;
1315 fromsol = get_varinfo (from)->solution;
1316 bitmap_ior_into (tosol, fromsol);
1317 merge_graph_nodes (graph, to, from);
1319 if (valid_graph_edge (graph, to, to))
1321 if (graph->zero_weight_preds[to])
1323 bitmap_clear_bit (graph->zero_weight_preds[to], to);
1324 bitmap_clear_bit (graph->zero_weight_succs[to], to);
1326 if (valid_weighted_graph_edge (graph, to, to))
1328 bitmap weights = *(get_graph_weights (graph, to, to));
1329 if (!weights || bitmap_empty_p (weights))
1330 erase_graph_self_edge (graph, to);
1333 BITMAP_FREE (fromsol);
1334 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
1335 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
1339 /* Unify nodes in GRAPH that we have found to be part of a cycle.
1340 SI is the Strongly Connected Components information structure that tells us
1341 what components to unify.
1342 UPDATE_CHANGED should be set to true if the changed sbitmap and changed
1343 count should be updated to reflect the unification. */
1346 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
1347 bool update_changed)
1350 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
1353 /* We proceed as follows:
1355 For each component in the queue (components are delineated by
1356 when current_queue_element->node != next_queue_element->node):
1358 rep = representative node for component
1360 For each node (tounify) to be unified in the component,
1361 merge the solution for tounify into tmp bitmap
1363 clear solution for tounify
1365 merge edges from tounify into rep
1367 merge complex constraints from tounify into rep
1369 update changed count to note that tounify will never change
1372 Merge tmp into solution for rep, marking rep changed if this
1373 changed rep's solution.
1375 Delete any 0 weighted self-edges we now have for rep. */
1376 while (i != VEC_length (unsigned, si->unification_queue))
1378 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
1379 unsigned int n = get_varinfo (tounify)->node;
1381 if (dump_file && (dump_flags & TDF_DETAILS))
1382 fprintf (dump_file, "Unifying %s to %s\n",
1383 get_varinfo (tounify)->name,
1384 get_varinfo (n)->name);
1386 stats.unified_vars_dynamic++;
1388 stats.unified_vars_static++;
1389 bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
1390 merge_graph_nodes (graph, n, tounify);
1391 condense_varmap_nodes (n, tounify);
1393 if (update_changed && TEST_BIT (changed, tounify))
1395 RESET_BIT (changed, tounify);
1396 if (!TEST_BIT (changed, n))
1397 SET_BIT (changed, n);
1400 gcc_assert (changed_count > 0);
1405 bitmap_clear (get_varinfo (tounify)->solution);
1408 /* If we've either finished processing the entire queue, or
1409 finished processing all nodes for component n, update the solution for
1411 if (i == VEC_length (unsigned, si->unification_queue)
1412 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
1414 /* If the solution changes because of the merging, we need to mark
1415 the variable as changed. */
1416 if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
1418 if (update_changed && !TEST_BIT (changed, n))
1420 SET_BIT (changed, n);
1426 if (valid_graph_edge (graph, n, n))
1428 if (graph->zero_weight_succs[n])
1430 if (graph->zero_weight_preds[n])
1431 bitmap_clear_bit (graph->zero_weight_preds[n], n);
1432 bitmap_clear_bit (graph->zero_weight_succs[n], n);
1434 if (valid_weighted_graph_edge (graph, n, n))
1436 bitmap weights = *(get_graph_weights (graph, n, n));
1437 if (!weights || bitmap_empty_p (weights))
1438 erase_graph_self_edge (graph, n);
1447 /* Information needed to compute the topological ordering of a graph. */
1451 /* sbitmap of visited nodes. */
1453 /* Array that stores the topological order of the graph, *in
1455 VEC(unsigned,heap) *topo_order;
1459 /* Initialize and return a topological info structure. */
1461 static struct topo_info *
1462 init_topo_info (void)
1464 size_t size = VEC_length (varinfo_t, varmap);
1465 struct topo_info *ti = XNEW (struct topo_info);
1466 ti->visited = sbitmap_alloc (size);
1467 sbitmap_zero (ti->visited);
1468 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1473 /* Free the topological sort info pointed to by TI. */
1476 free_topo_info (struct topo_info *ti)
1478 sbitmap_free (ti->visited);
1479 VEC_free (unsigned, heap, ti->topo_order);
1483 /* Visit the graph in topological order, and store the order in the
1484 topo_info structure. */
1487 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1490 VEC(constraint_edge_t,heap) *succs = graph->succs[n];
1493 constraint_edge_t c;
1497 SET_BIT (ti->visited, n);
1498 if (VEC_length (constraint_edge_t, succs) != 0)
1500 temp = BITMAP_ALLOC (&iteration_obstack);
1501 if (graph->zero_weight_succs[n])
1502 bitmap_ior_into (temp, graph->zero_weight_succs[n]);
1503 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
1504 bitmap_set_bit (temp, c->dest);
1507 temp = graph->zero_weight_succs[n];
1510 EXECUTE_IF_SET_IN_BITMAP (temp, 0, j, bi)
1512 if (!TEST_BIT (ti->visited, j))
1513 topo_visit (graph, ti, j);
1515 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1518 /* Return true if variable N + OFFSET is a legal field of N. */
1521 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1523 varinfo_t ninfo = get_varinfo (n);
1525 /* For things we've globbed to single variables, any offset into the
1526 variable acts like the entire variable, so that it becomes offset
1528 if (ninfo->is_special_var
1529 || ninfo->is_artificial_var
1530 || ninfo->is_unknown_size_var)
1535 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1538 /* Process a constraint C that represents *x = &y. */
1541 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1542 constraint_t c, bitmap delta)
1544 unsigned int rhs = c->rhs.var;
1548 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1549 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1551 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1552 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
1554 /* *x != NULL && *x != ANYTHING*/
1558 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1560 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1564 sol = get_varinfo (t)->solution;
1565 if (!bitmap_bit_p (sol, rhs))
1567 bitmap_set_bit (sol, rhs);
1568 if (!TEST_BIT (changed, t))
1570 SET_BIT (changed, t);
1575 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1576 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1581 /* Process a constraint C that represents x = *y, using DELTA as the
1582 starting solution. */
1585 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1588 unsigned int lhs = get_varinfo (c->lhs.var)->node;
1590 bitmap sol = get_varinfo (lhs)->solution;
1594 if (bitmap_bit_p (delta, anything_id))
1596 flag = !bitmap_bit_p (sol, anything_id);
1598 bitmap_set_bit (sol, anything_id);
1601 /* For each variable j in delta (Sol(y)), add
1602 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1603 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1605 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1606 if (type_safe (j, &roffset))
1609 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1612 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1617 /* Adding edges from the special vars is pointless.
1618 They don't have sets that can change. */
1619 if (get_varinfo (t) ->is_special_var)
1620 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1621 else if (int_add_graph_edge (graph, lhs, t, 0))
1622 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1624 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1625 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1630 /* If the LHS solution changed, mark the var as changed. */
1633 get_varinfo (lhs)->solution = sol;
1634 if (!TEST_BIT (changed, lhs))
1636 SET_BIT (changed, lhs);
1642 /* Process a constraint C that represents *x = y. */
1645 do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1647 unsigned int rhs = get_varinfo (c->rhs.var)->node;
1648 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1649 bitmap sol = get_varinfo (rhs)->solution;
1653 if (bitmap_bit_p (sol, anything_id))
1655 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1657 varinfo_t jvi = get_varinfo (j);
1659 unsigned int loff = c->lhs.offset;
1660 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
1663 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1668 if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id))
1670 bitmap_set_bit (get_varinfo (t)->solution, anything_id);
1671 if (!TEST_BIT (changed, t))
1673 SET_BIT (changed, t);
1681 /* For each member j of delta (Sol(x)), add an edge from y to j and
1682 union Sol(y) into Sol(j) */
1683 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1685 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1686 if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var))
1690 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1692 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1696 if (int_add_graph_edge (graph, t, rhs, roff))
1698 bitmap tmp = get_varinfo (t)->solution;
1699 if (set_union_with_increment (tmp, sol, roff))
1701 get_varinfo (t)->solution = tmp;
1703 sol = get_varinfo (rhs)->solution;
1704 if (!TEST_BIT (changed, t))
1706 SET_BIT (changed, t);
1712 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1713 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1717 /* Handle a non-simple (simple meaning requires no iteration), non-copy
1718 constraint (IE *x = &y, x = *y, and *x = y). */
1721 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1723 if (c->lhs.type == DEREF)
1725 if (c->rhs.type == ADDRESSOF)
1728 do_da_constraint (graph, c, delta);
1733 do_ds_constraint (graph, c, delta);
1739 if (!(get_varinfo (c->lhs.var)->is_special_var))
1740 do_sd_constraint (graph, c, delta);
1744 /* Initialize and return a new SCC info structure. */
1746 static struct scc_info *
1747 init_scc_info (void)
1749 struct scc_info *si = XNEW (struct scc_info);
1750 size_t size = VEC_length (varinfo_t, varmap);
1752 si->current_index = 0;
1753 si->visited = sbitmap_alloc (size);
1754 sbitmap_zero (si->visited);
1755 si->in_component = sbitmap_alloc (size);
1756 sbitmap_ones (si->in_component);
1757 si->visited_index = XCNEWVEC (unsigned int, size + 1);
1758 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1759 si->unification_queue = VEC_alloc (unsigned, heap, 1);
1763 /* Free an SCC info structure pointed to by SI */
1766 free_scc_info (struct scc_info *si)
1768 sbitmap_free (si->visited);
1769 sbitmap_free (si->in_component);
1770 free (si->visited_index);
1771 VEC_free (unsigned, heap, si->scc_stack);
1772 VEC_free (unsigned, heap, si->unification_queue);
1777 /* Find cycles in GRAPH that occur, using strongly connected components, and
1778 collapse the cycles into a single representative node. if UPDATE_CHANGED
1779 is true, then update the changed sbitmap to note those nodes whose
1780 solutions have changed as a result of collapsing. */
1783 find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
1786 unsigned int size = VEC_length (varinfo_t, varmap);
1787 struct scc_info *si = init_scc_info ();
1789 for (i = 0; i != size; ++i)
1790 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
1791 scc_visit (graph, si, i);
1793 process_unification_queue (graph, si, update_changed);
1797 /* Compute a topological ordering for GRAPH, and store the result in the
1798 topo_info structure TI. */
1801 compute_topo_order (constraint_graph_t graph,
1802 struct topo_info *ti)
1805 unsigned int size = VEC_length (varinfo_t, varmap);
1807 for (i = 0; i != size; ++i)
1808 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
1809 topo_visit (graph, ti, i);
1812 /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */
1815 bitmap_other_than_zero_bit_set (bitmap b)
1820 if (bitmap_empty_p (b))
1822 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
1827 /* Perform offline variable substitution.
1829 This is a linear time way of identifying variables that must have
1830 equivalent points-to sets, including those caused by static cycles,
1831 and single entry subgraphs, in the constraint graph.
1833 The technique is described in "Off-line variable substitution for
1834 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1835 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */
1838 perform_var_substitution (constraint_graph_t graph)
1840 struct topo_info *ti = init_topo_info ();
1842 bitmap_obstack_initialize (&iteration_obstack);
1843 /* Compute the topological ordering of the graph, then visit each
1844 node in topological order. */
1845 compute_topo_order (graph, ti);
1847 while (VEC_length (unsigned, ti->topo_order) != 0)
1849 unsigned int i = VEC_pop (unsigned, ti->topo_order);
1851 varinfo_t vi = get_varinfo (i);
1852 bool okay_to_elim = false;
1853 unsigned int root = VEC_length (varinfo_t, varmap);
1854 VEC(constraint_edge_t,heap) *predvec = graph->preds[i];
1855 constraint_edge_t ce = NULL;
1860 /* We can't eliminate things whose address is taken, or which is
1861 the target of a dereference. */
1862 if (vi->address_taken || vi->indirect_target)
1865 /* See if all predecessors of I are ripe for elimination */
1866 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[i], 0, k, bi)
1869 w = get_varinfo (k)->node;
1871 /* We can't eliminate the node if one of the predecessors is
1872 part of a different strongly connected component. */
1876 okay_to_elim = true;
1880 okay_to_elim = false;
1884 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1885 then Solution(i) is a subset of Solution (w), where w is a
1886 predecessor in the graph.
1887 Corollary: If all predecessors of i have the same
1888 points-to set, then i has that same points-to set as
1889 those predecessors. */
1890 tmp = BITMAP_ALLOC (NULL);
1891 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1892 get_varinfo (w)->solution);
1893 if (!bitmap_empty_p (tmp))
1895 okay_to_elim = false;
1904 VEC_iterate (constraint_edge_t, predvec, pred, ce);
1909 weight = *(get_graph_weights (graph, i, ce->dest));
1911 /* We can't eliminate variables that have nonzero weighted
1912 edges between them. */
1913 if (weight && bitmap_other_than_zero_bit_set (weight))
1915 okay_to_elim = false;
1918 w = get_varinfo (ce->dest)->node;
1920 /* We can't eliminate the node if one of the predecessors is
1921 part of a different strongly connected component. */
1925 okay_to_elim = true;
1929 okay_to_elim = false;
1933 /* Theorem 4 in Rountev and Chandra: If i is a direct node,
1934 then Solution(i) is a subset of Solution (w), where w is a
1935 predecessor in the graph.
1936 Corollary: If all predecessors of i have the same
1937 points-to set, then i has that same points-to set as
1938 those predecessors. */
1939 tmp = BITMAP_ALLOC (NULL);
1940 bitmap_and_compl (tmp, get_varinfo (i)->solution,
1941 get_varinfo (w)->solution);
1942 if (!bitmap_empty_p (tmp))
1944 okay_to_elim = false;
1951 /* See if the root is different than the original node.
1952 If so, we've found an equivalence. */
1953 if (root != get_varinfo (i)->node && okay_to_elim)
1955 /* Found an equivalence */
1956 get_varinfo (i)->node = root;
1957 collapse_nodes (graph, root, i);
1958 if (dump_file && (dump_flags & TDF_DETAILS))
1959 fprintf (dump_file, "Collapsing %s into %s\n",
1960 get_varinfo (i)->name,
1961 get_varinfo (root)->name);
1962 stats.collapsed_vars++;
1966 bitmap_obstack_release (&iteration_obstack);
1967 free_topo_info (ti);
1970 /* Solve the constraint graph GRAPH using our worklist solver.
1971 This is based on the PW* family of solvers from the "Efficient Field
1972 Sensitive Pointer Analysis for C" paper.
1973 It works by iterating over all the graph nodes, processing the complex
1974 constraints and propagating the copy constraints, until everything stops
1975 changed. This corresponds to steps 6-8 in the solving list given above. */
1978 solve_graph (constraint_graph_t graph)
1980 unsigned int size = VEC_length (varinfo_t, varmap);
1983 changed_count = size;
1984 changed = sbitmap_alloc (size);
1985 sbitmap_ones (changed);
1987 /* The already collapsed/unreachable nodes will never change, so we
1988 need to account for them in changed_count. */
1989 for (i = 0; i < size; i++)
1990 if (get_varinfo (i)->node != i)
1993 while (changed_count > 0)
1996 struct topo_info *ti = init_topo_info ();
1999 bitmap_obstack_initialize (&iteration_obstack);
2003 /* We already did cycle elimination once, when we did
2004 variable substitution, so we don't need it again for the
2006 if (stats.iterations > 1)
2007 find_and_collapse_graph_cycles (graph, true);
2012 compute_topo_order (graph, ti);
2014 while (VEC_length (unsigned, ti->topo_order) != 0)
2016 i = VEC_pop (unsigned, ti->topo_order);
2017 gcc_assert (get_varinfo (i)->node == i);
2019 /* If the node has changed, we need to process the
2020 complex constraints and outgoing edges again. */
2021 if (TEST_BIT (changed, i))
2025 constraint_edge_t e = NULL;
2028 VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
2029 VEC(constraint_edge_t,heap) *succs;
2031 RESET_BIT (changed, i);
2034 /* Process the complex constraints */
2035 solution = get_varinfo (i)->solution;
2036 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2037 do_complex_constraint (graph, c, solution);
2039 /* Propagate solution to all successors. */
2040 succs = graph->succs[i];
2042 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[i], 0, j, bi)
2044 bitmap tmp = get_varinfo (j)->solution;
2047 flag = set_union_with_increment (tmp, solution, 0);
2051 get_varinfo (j)->solution = tmp;
2052 if (!TEST_BIT (changed, j))
2054 SET_BIT (changed, j);
2059 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
2061 bitmap tmp = get_varinfo (e->dest)->solution;
2064 bitmap weights = e->weights;
2067 gcc_assert (weights && !bitmap_empty_p (weights));
2068 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
2069 flag |= set_union_with_increment (tmp, solution, k);
2073 get_varinfo (e->dest)->solution = tmp;
2074 if (!TEST_BIT (changed, e->dest))
2076 SET_BIT (changed, e->dest);
2083 free_topo_info (ti);
2084 bitmap_obstack_release (&iteration_obstack);
2087 sbitmap_free (changed);
2091 /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */
2093 /* Map from trees to variable ids. */
2094 static htab_t id_for_tree;
2096 typedef struct tree_id
2102 /* Hash a tree id structure. */
2105 tree_id_hash (const void *p)
2107 const tree_id_t ta = (tree_id_t) p;
2108 return htab_hash_pointer (ta->t);
2111 /* Return true if the tree in P1 and the tree in P2 are the same. */
2114 tree_id_eq (const void *p1, const void *p2)
2116 const tree_id_t ta1 = (tree_id_t) p1;
2117 const tree_id_t ta2 = (tree_id_t) p2;
2118 return ta1->t == ta2->t;
2121 /* Insert ID as the variable id for tree T in the hashtable. */
2124 insert_id_for_tree (tree t, int id)
2127 struct tree_id finder;
2131 slot = htab_find_slot (id_for_tree, &finder, INSERT);
2132 gcc_assert (*slot == NULL);
2133 new_pair = XNEW (struct tree_id);
2136 *slot = (void *)new_pair;
2139 /* Find the variable id for tree T in ID_FOR_TREE. If T does not
2140 exist in the hash table, return false, otherwise, return true and
2141 set *ID to the id we found. */
2144 lookup_id_for_tree (tree t, unsigned int *id)
2147 struct tree_id finder;
2150 pair = htab_find (id_for_tree, &finder);
2157 /* Return a printable name for DECL */
2160 alias_get_name (tree decl)
2162 const char *res = get_name (decl);
2164 int num_printed = 0;
2170 if (TREE_CODE (decl) == SSA_NAME)
2172 num_printed = asprintf (&temp, "%s_%u",
2173 alias_get_name (SSA_NAME_VAR (decl)),
2174 SSA_NAME_VERSION (decl));
2176 else if (DECL_P (decl))
2178 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2180 if (num_printed > 0)
2182 res = ggc_strdup (temp);
2188 /* Find the variable id for tree T in the hashtable.
2189 If T doesn't exist in the hash table, create an entry for it. */
2192 get_id_for_tree (tree t)
2195 struct tree_id finder;
2198 pair = htab_find (id_for_tree, &finder);
2200 return create_variable_info_for (t, alias_get_name (t));
2205 /* Get a constraint expression from an SSA_VAR_P node. */
2207 static struct constraint_expr
2208 get_constraint_exp_from_ssa_var (tree t)
2210 struct constraint_expr cexpr;
2212 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2214 /* For parameters, get at the points-to set for the actual parm
2216 if (TREE_CODE (t) == SSA_NAME
2217 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2218 && default_def (SSA_NAME_VAR (t)) == t)
2219 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
2221 cexpr.type = SCALAR;
2223 cexpr.var = get_id_for_tree (t);
2224 /* If we determine the result is "anything", and we know this is readonly,
2225 say it points to readonly memory instead. */
2226 if (cexpr.var == anything_id && TREE_READONLY (t))
2228 cexpr.type = ADDRESSOF;
2229 cexpr.var = readonly_id;
2236 /* Process a completed constraint T, and add it to the constraint
2240 process_constraint (constraint_t t)
2242 struct constraint_expr rhs = t->rhs;
2243 struct constraint_expr lhs = t->lhs;
2245 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2246 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2248 /* ANYTHING == ANYTHING is pointless. */
2249 if (lhs.var == anything_id && rhs.var == anything_id)
2252 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2253 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
2258 process_constraint (t);
2260 /* This can happen in our IR with things like n->a = *p */
2261 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2263 /* Split into tmp = *rhs, *lhs = tmp */
2264 tree rhsdecl = get_varinfo (rhs.var)->decl;
2265 tree pointertype = TREE_TYPE (rhsdecl);
2266 tree pointedtotype = TREE_TYPE (pointertype);
2267 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2268 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2270 /* If this is an aggregate of known size, we should have passed
2271 this off to do_structure_copy, and it should have broken it
2273 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
2274 || get_varinfo (rhs.var)->is_unknown_size_var);
2276 process_constraint (new_constraint (tmplhs, rhs));
2277 process_constraint (new_constraint (lhs, tmplhs));
2279 else if (rhs.type == ADDRESSOF)
2282 gcc_assert (rhs.offset == 0);
2284 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
2285 vi->address_taken = true;
2287 VEC_safe_push (constraint_t, heap, constraints, t);
2291 if (lhs.type != DEREF && rhs.type == DEREF)
2292 get_varinfo (lhs.var)->indirect_target = true;
2293 VEC_safe_push (constraint_t, heap, constraints, t);
2298 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2301 static unsigned HOST_WIDE_INT
2302 bitpos_of_field (const tree fdecl)
2305 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
2306 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
2309 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
2310 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
2314 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2315 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2318 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
2319 const unsigned HOST_WIDE_INT fieldsize,
2320 const unsigned HOST_WIDE_INT accesspos,
2321 const unsigned HOST_WIDE_INT accesssize)
2323 if (fieldpos == accesspos && fieldsize == accesssize)
2325 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
2327 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2333 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2336 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results)
2339 HOST_WIDE_INT bitsize = -1;
2340 HOST_WIDE_INT bitmaxsize = -1;
2341 HOST_WIDE_INT bitpos;
2343 struct constraint_expr *result;
2344 unsigned int beforelength = VEC_length (ce_s, *results);
2346 /* Some people like to do cute things like take the address of
2349 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2350 forzero = TREE_OPERAND (forzero, 0);
2352 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2354 struct constraint_expr temp;
2357 temp.var = integer_id;
2359 VEC_safe_push (ce_s, heap, *results, &temp);
2363 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2364 get_constraint_for (t, results);
2365 result = VEC_last (ce_s, *results);
2366 result->offset = bitpos;
2368 gcc_assert (beforelength + 1 == VEC_length (ce_s, *results));
2370 /* This can also happen due to weird offsetof type macros. */
2371 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2372 result->type = SCALAR;
2374 if (result->type == SCALAR)
2376 /* In languages like C, you can access one past the end of an
2377 array. You aren't allowed to dereference it, so we can
2378 ignore this constraint. When we handle pointer subtraction,
2379 we may have to do something cute here. */
2381 if (result->offset < get_varinfo (result->var)->fullsize)
2383 /* It's also not true that the constraint will actually start at the
2384 right offset, it may start in some padding. We only care about
2385 setting the constraint to the first actual field it touches, so
2388 for (curr = get_varinfo (result->var); curr; curr = curr->next)
2390 if (offset_overlaps_with_access (curr->offset, curr->size,
2391 result->offset, bitmaxsize))
2393 result->var = curr->id;
2397 /* assert that we found *some* field there. The user couldn't be
2398 accessing *only* padding. */
2399 /* Still the user could access one past the end of an array
2400 embedded in a struct resulting in accessing *only* padding. */
2401 gcc_assert (curr || ref_contains_array_ref (orig_t));
2404 if (dump_file && (dump_flags & TDF_DETAILS))
2405 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2412 /* Dereference the constraint expression CONS, and return the result.
2413 DEREF (ADDRESSOF) = SCALAR
2414 DEREF (SCALAR) = DEREF
2415 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2416 This is needed so that we can handle dereferencing DEREF constraints. */
2419 do_deref (VEC (ce_s, heap) **constraints)
2421 struct constraint_expr *c;
2423 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2425 if (c->type == SCALAR)
2427 else if (c->type == ADDRESSOF)
2429 else if (c->type == DEREF)
2431 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
2432 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2433 process_constraint (new_constraint (tmplhs, *c));
2434 c->var = tmplhs.var;
2442 /* Given a tree T, return the constraint expression for it. */
2445 get_constraint_for (tree t, VEC (ce_s, heap) **results)
2447 struct constraint_expr temp;
2449 /* x = integer is all glommed to a single variable, which doesn't
2450 point to anything by itself. That is, of course, unless it is an
2451 integer constant being treated as a pointer, in which case, we
2452 will return that this is really the addressof anything. This
2453 happens below, since it will fall into the default case. The only
2454 case we know something about an integer treated like a pointer is
2455 when it is the NULL pointer, and then we just say it points to
2457 if (TREE_CODE (t) == INTEGER_CST
2458 && !POINTER_TYPE_P (TREE_TYPE (t)))
2460 temp.var = integer_id;
2463 VEC_safe_push (ce_s, heap, *results, &temp);
2466 else if (TREE_CODE (t) == INTEGER_CST
2467 && integer_zerop (t))
2469 temp.var = nothing_id;
2470 temp.type = ADDRESSOF;
2472 VEC_safe_push (ce_s, heap, *results, &temp);
2476 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2478 case tcc_expression:
2480 switch (TREE_CODE (t))
2484 struct constraint_expr *c;
2486 tree exp = TREE_OPERAND (t, 0);
2487 tree pttype = TREE_TYPE (TREE_TYPE (t));
2489 get_constraint_for (exp, results);
2490 /* Make sure we capture constraints to all elements
2492 if ((handled_component_p (exp)
2493 && ref_contains_array_ref (exp))
2494 || TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE)
2496 struct constraint_expr *origrhs;
2498 struct constraint_expr tmp;
2500 gcc_assert (VEC_length (ce_s, *results) == 1);
2501 origrhs = VEC_last (ce_s, *results);
2503 VEC_pop (ce_s, *results);
2504 origvar = get_varinfo (origrhs->var);
2505 for (; origvar; origvar = origvar->next)
2507 tmp.var = origvar->id;
2508 VEC_safe_push (ce_s, heap, *results, &tmp);
2511 else if (VEC_length (ce_s, *results) == 1
2512 && (AGGREGATE_TYPE_P (pttype)
2513 || TREE_CODE (pttype) == COMPLEX_TYPE))
2515 struct constraint_expr *origrhs;
2517 struct constraint_expr tmp;
2519 gcc_assert (VEC_length (ce_s, *results) == 1);
2520 origrhs = VEC_last (ce_s, *results);
2522 VEC_pop (ce_s, *results);
2523 origvar = get_varinfo (origrhs->var);
2524 for (; origvar; origvar = origvar->next)
2526 tmp.var = origvar->id;
2527 VEC_safe_push (ce_s, heap, *results, &tmp);
2531 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2533 if (c->type == DEREF)
2536 c->type = ADDRESSOF;
2543 /* XXX: In interprocedural mode, if we didn't have the
2544 body, we would need to do *each pointer argument =
2546 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2549 tree heapvar = heapvar_lookup (t);
2551 if (heapvar == NULL)
2553 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2554 DECL_EXTERNAL (heapvar) = 1;
2555 if (referenced_vars)
2556 add_referenced_tmp_var (heapvar);
2557 heapvar_insert (t, heapvar);
2560 temp.var = create_variable_info_for (heapvar,
2561 alias_get_name (heapvar));
2563 vi = get_varinfo (temp.var);
2564 vi->is_artificial_var = 1;
2565 vi->is_heap_var = 1;
2566 temp.type = ADDRESSOF;
2568 VEC_safe_push (ce_s, heap, *results, &temp);
2574 temp.type = ADDRESSOF;
2575 temp.var = anything_id;
2577 VEC_safe_push (ce_s, heap, *results, &temp);
2584 switch (TREE_CODE (t))
2588 get_constraint_for (TREE_OPERAND (t, 0), results);
2593 case ARRAY_RANGE_REF:
2595 get_constraint_for_component_ref (t, results);
2599 temp.type = ADDRESSOF;
2600 temp.var = anything_id;
2602 VEC_safe_push (ce_s, heap, *results, &temp);
2609 switch (TREE_CODE (t))
2613 case NON_LVALUE_EXPR:
2615 tree op = TREE_OPERAND (t, 0);
2617 /* Cast from non-pointer to pointers are bad news for us.
2618 Anything else, we see through */
2619 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2620 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2622 get_constraint_for (op, results);
2630 temp.type = ADDRESSOF;
2631 temp.var = anything_id;
2633 VEC_safe_push (ce_s, heap, *results, &temp);
2638 case tcc_exceptional:
2640 switch (TREE_CODE (t))
2644 get_constraint_for (PHI_RESULT (t), results);
2650 struct constraint_expr temp;
2651 temp = get_constraint_exp_from_ssa_var (t);
2652 VEC_safe_push (ce_s, heap, *results, &temp);
2658 temp.type = ADDRESSOF;
2659 temp.var = anything_id;
2661 VEC_safe_push (ce_s, heap, *results, &temp);
2666 case tcc_declaration:
2668 struct constraint_expr temp;
2669 temp = get_constraint_exp_from_ssa_var (t);
2670 VEC_safe_push (ce_s, heap, *results, &temp);
2675 temp.type = ADDRESSOF;
2676 temp.var = anything_id;
2678 VEC_safe_push (ce_s, heap, *results, &temp);
2685 /* Handle the structure copy case where we have a simple structure copy
2686 between LHS and RHS that is of SIZE (in bits)
2688 For each field of the lhs variable (lhsfield)
2689 For each field of the rhs variable at lhsfield.offset (rhsfield)
2690 add the constraint lhsfield = rhsfield
2692 If we fail due to some kind of type unsafety or other thing we
2693 can't handle, return false. We expect the caller to collapse the
2694 variable in that case. */
2697 do_simple_structure_copy (const struct constraint_expr lhs,
2698 const struct constraint_expr rhs,
2699 const unsigned HOST_WIDE_INT size)
2701 varinfo_t p = get_varinfo (lhs.var);
2702 unsigned HOST_WIDE_INT pstart, last;
2704 last = p->offset + size;
2705 for (; p && p->offset < last; p = p->next)
2708 struct constraint_expr templhs = lhs;
2709 struct constraint_expr temprhs = rhs;
2710 unsigned HOST_WIDE_INT fieldoffset;
2712 templhs.var = p->id;
2713 q = get_varinfo (temprhs.var);
2714 fieldoffset = p->offset - pstart;
2715 q = first_vi_for_offset (q, q->offset + fieldoffset);
2718 temprhs.var = q->id;
2719 process_constraint (new_constraint (templhs, temprhs));
2725 /* Handle the structure copy case where we have a structure copy between a
2726 aggregate on the LHS and a dereference of a pointer on the RHS
2727 that is of SIZE (in bits)
2729 For each field of the lhs variable (lhsfield)
2730 rhs.offset = lhsfield->offset
2731 add the constraint lhsfield = rhs
2735 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2736 const struct constraint_expr rhs,
2737 const unsigned HOST_WIDE_INT size)
2739 varinfo_t p = get_varinfo (lhs.var);
2740 unsigned HOST_WIDE_INT pstart,last;
2742 last = p->offset + size;
2744 for (; p && p->offset < last; p = p->next)
2747 struct constraint_expr templhs = lhs;
2748 struct constraint_expr temprhs = rhs;
2749 unsigned HOST_WIDE_INT fieldoffset;
2752 if (templhs.type == SCALAR)
2753 templhs.var = p->id;
2755 templhs.offset = p->offset;
2757 q = get_varinfo (temprhs.var);
2758 fieldoffset = p->offset - pstart;
2759 temprhs.offset += fieldoffset;
2760 process_constraint (new_constraint (templhs, temprhs));
2764 /* Handle the structure copy case where we have a structure copy
2765 between a aggregate on the RHS and a dereference of a pointer on
2766 the LHS that is of SIZE (in bits)
2768 For each field of the rhs variable (rhsfield)
2769 lhs.offset = rhsfield->offset
2770 add the constraint lhs = rhsfield
2774 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2775 const struct constraint_expr rhs,
2776 const unsigned HOST_WIDE_INT size)
2778 varinfo_t p = get_varinfo (rhs.var);
2779 unsigned HOST_WIDE_INT pstart,last;
2781 last = p->offset + size;
2783 for (; p && p->offset < last; p = p->next)
2786 struct constraint_expr templhs = lhs;
2787 struct constraint_expr temprhs = rhs;
2788 unsigned HOST_WIDE_INT fieldoffset;
2791 if (temprhs.type == SCALAR)
2792 temprhs.var = p->id;
2794 temprhs.offset = p->offset;
2796 q = get_varinfo (templhs.var);
2797 fieldoffset = p->offset - pstart;
2798 templhs.offset += fieldoffset;
2799 process_constraint (new_constraint (templhs, temprhs));
2803 /* Sometimes, frontends like to give us bad type information. This
2804 function will collapse all the fields from VAR to the end of VAR,
2805 into VAR, so that we treat those fields as a single variable.
2806 We return the variable they were collapsed into. */
2809 collapse_rest_of_var (unsigned int var)
2811 varinfo_t currvar = get_varinfo (var);
2814 for (field = currvar->next; field; field = field->next)
2817 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
2818 field->name, currvar->name);
2820 gcc_assert (!field->collapsed_to);
2821 field->collapsed_to = currvar;
2824 currvar->next = NULL;
2825 currvar->size = currvar->fullsize - currvar->offset;
2830 /* Handle aggregate copies by expanding into copies of the respective
2831 fields of the structures. */
2834 do_structure_copy (tree lhsop, tree rhsop)
2836 struct constraint_expr lhs, rhs, tmp;
2837 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
2839 unsigned HOST_WIDE_INT lhssize;
2840 unsigned HOST_WIDE_INT rhssize;
2842 get_constraint_for (lhsop, &lhsc);
2843 get_constraint_for (rhsop, &rhsc);
2844 gcc_assert (VEC_length (ce_s, lhsc) == 1);
2845 gcc_assert (VEC_length (ce_s, rhsc) == 1);
2846 lhs = *(VEC_last (ce_s, lhsc));
2847 rhs = *(VEC_last (ce_s, rhsc));
2849 VEC_free (ce_s, heap, lhsc);
2850 VEC_free (ce_s, heap, rhsc);
2852 /* If we have special var = x, swap it around. */
2853 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2860 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2861 possible it's something we could handle. However, most cases falling
2862 into this are dealing with transparent unions, which are slightly
2864 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2866 rhs.type = ADDRESSOF;
2867 rhs.var = anything_id;
2870 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2871 that special var. */
2872 if (rhs.var <= integer_id)
2874 for (p = get_varinfo (lhs.var); p; p = p->next)
2876 struct constraint_expr templhs = lhs;
2877 struct constraint_expr temprhs = rhs;
2879 if (templhs.type == SCALAR )
2880 templhs.var = p->id;
2882 templhs.offset += p->offset;
2883 process_constraint (new_constraint (templhs, temprhs));
2888 tree rhstype = TREE_TYPE (rhsop);
2889 tree lhstype = TREE_TYPE (lhsop);
2893 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
2894 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
2896 /* If we have a variably sized types on the rhs or lhs, and a deref
2897 constraint, add the constraint, lhsconstraint = &ANYTHING.
2898 This is conservatively correct because either the lhs is an unknown
2899 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2900 constraint, and every variable it can point to must be unknown sized
2901 anyway, so we don't need to worry about fields at all. */
2902 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2903 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2905 rhs.var = anything_id;
2906 rhs.type = ADDRESSOF;
2908 process_constraint (new_constraint (lhs, rhs));
2912 /* The size only really matters insofar as we don't set more or less of
2913 the variable. If we hit an unknown size var, the size should be the
2914 whole darn thing. */
2915 if (get_varinfo (rhs.var)->is_unknown_size_var)
2918 rhssize = TREE_INT_CST_LOW (rhstypesize);
2920 if (get_varinfo (lhs.var)->is_unknown_size_var)
2923 lhssize = TREE_INT_CST_LOW (lhstypesize);
2926 if (rhs.type == SCALAR && lhs.type == SCALAR)
2928 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
2930 lhs.var = collapse_rest_of_var (lhs.var);
2931 rhs.var = collapse_rest_of_var (rhs.var);
2936 process_constraint (new_constraint (lhs, rhs));
2939 else if (lhs.type != DEREF && rhs.type == DEREF)
2940 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2941 else if (lhs.type == DEREF && rhs.type != DEREF)
2942 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2945 tree pointedtotype = lhstype;
2948 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2949 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2950 do_structure_copy (tmpvar, rhsop);
2951 do_structure_copy (lhsop, tmpvar);
2956 /* Update related alias information kept in AI. This is used when
2957 building name tags, alias sets and deciding grouping heuristics.
2958 STMT is the statement to process. This function also updates
2959 ADDRESSABLE_VARS. */
2962 update_alias_info (tree stmt, struct alias_info *ai)
2965 use_operand_p use_p;
2967 enum escape_type stmt_escape_type = is_escape_site (stmt, ai);
2970 /* Mark all the variables whose address are taken by the statement. */
2971 addr_taken = addresses_taken (stmt);
2974 bitmap_ior_into (addressable_vars, addr_taken);
2976 /* If STMT is an escape point, all the addresses taken by it are
2978 if (stmt_escape_type != NO_ESCAPE)
2983 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
2985 tree rvar = referenced_var (i);
2986 if (!unmodifiable_var_p (rvar))
2987 mark_call_clobbered (rvar, stmt_escape_type);
2992 /* Process each operand use. If an operand may be aliased, keep
2993 track of how many times it's being used. For pointers, determine
2994 whether they are dereferenced by the statement, or whether their
2995 value escapes, etc. */
2996 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
3000 struct ptr_info_def *pi;
3001 bool is_store, is_potential_deref;
3002 unsigned num_uses, num_derefs;
3004 op = USE_FROM_PTR (use_p);
3006 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
3007 to the set of addressable variables. */
3008 if (TREE_CODE (op) == ADDR_EXPR)
3010 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
3012 /* PHI nodes don't have annotations for pinning the set
3013 of addresses taken, so we collect them here.
3015 FIXME, should we allow PHI nodes to have annotations
3016 so that they can be treated like regular statements?
3017 Currently, they are treated as second-class
3019 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
3023 /* Ignore constants. */
3024 if (TREE_CODE (op) != SSA_NAME)
3027 var = SSA_NAME_VAR (op);
3028 v_ann = var_ann (var);
3030 /* The base variable of an ssa name must be a GIMPLE register, and thus
3031 it cannot be aliased. */
3032 gcc_assert (!may_be_aliased (var));
3034 /* We are only interested in pointers. */
3035 if (!POINTER_TYPE_P (TREE_TYPE (op)))
3038 pi = get_ptr_info (op);
3040 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3041 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
3043 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
3044 VARRAY_PUSH_TREE (ai->processed_ptrs, op);
3047 /* If STMT is a PHI node, then it will not have pointer
3048 dereferences and it will not be an escape point. */
3049 if (TREE_CODE (stmt) == PHI_NODE)
3052 /* Determine whether OP is a dereferenced pointer, and if STMT
3053 is an escape point, whether OP escapes. */
3054 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
3056 /* Handle a corner case involving address expressions of the
3057 form '&PTR->FLD'. The problem with these expressions is that
3058 they do not represent a dereference of PTR. However, if some
3059 other transformation propagates them into an INDIRECT_REF
3060 expression, we end up with '*(&PTR->FLD)' which is folded
3063 So, if the original code had no other dereferences of PTR,
3064 the aliaser will not create memory tags for it, and when
3065 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3066 memory operations will receive no V_MAY_DEF/VUSE operands.
3068 One solution would be to have count_uses_and_derefs consider
3069 &PTR->FLD a dereference of PTR. But that is wrong, since it
3070 is not really a dereference but an offset calculation.
3072 What we do here is to recognize these special ADDR_EXPR
3073 nodes. Since these expressions are never GIMPLE values (they
3074 are not GIMPLE invariants), they can only appear on the RHS
3075 of an assignment and their base address is always an
3076 INDIRECT_REF expression. */
3077 is_potential_deref = false;
3078 if (TREE_CODE (stmt) == MODIFY_EXPR
3079 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
3080 && !is_gimple_val (TREE_OPERAND (stmt, 1)))
3082 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3083 this represents a potential dereference of PTR. */
3084 tree rhs = TREE_OPERAND (stmt, 1);
3085 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3086 if (TREE_CODE (base) == INDIRECT_REF
3087 && TREE_OPERAND (base, 0) == op)
3088 is_potential_deref = true;
3091 if (num_derefs > 0 || is_potential_deref)
3093 /* Mark OP as dereferenced. In a subsequent pass,
3094 dereferenced pointers that point to a set of
3095 variables will be assigned a name tag to alias
3096 all the variables OP points to. */
3097 pi->is_dereferenced = 1;
3099 /* Keep track of how many time we've dereferenced each
3101 NUM_REFERENCES_INC (v_ann);
3103 /* If this is a store operation, mark OP as being
3104 dereferenced to store, otherwise mark it as being
3105 dereferenced to load. */
3107 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3109 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
3112 if (stmt_escape_type != NO_ESCAPE && num_derefs < num_uses)
3114 /* If STMT is an escape point and STMT contains at
3115 least one direct use of OP, then the value of OP
3116 escapes and so the pointed-to variables need to
3117 be marked call-clobbered. */
3118 pi->value_escapes_p = 1;
3119 pi->escape_mask |= stmt_escape_type;
3121 /* If the statement makes a function call, assume
3122 that pointer OP will be dereferenced in a store
3123 operation inside the called function. */
3124 if (get_call_expr_in (stmt))
3126 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3127 pi->is_dereferenced = 1;
3132 if (TREE_CODE (stmt) == PHI_NODE)
3135 /* Update reference counter for definitions to any
3136 potentially aliased variable. This is used in the alias
3137 grouping heuristics. */
3138 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3140 tree var = SSA_NAME_VAR (op);
3141 var_ann_t ann = var_ann (var);
3142 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3143 if (may_be_aliased (var))
3144 NUM_REFERENCES_INC (ann);
3148 /* Mark variables in V_MAY_DEF operands as being written to. */
3149 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
3151 tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
3152 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3157 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3158 Expressions of the type PTR + CST can be handled in two ways:
3160 1- If the constraint for PTR is ADDRESSOF for a non-structure
3161 variable, then we can use it directly because adding or
3162 subtracting a constant may not alter the original ADDRESSOF
3163 constraint (i.e., pointer arithmetic may not legally go outside
3164 an object's boundaries).
3166 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3167 then if CST is a compile-time constant that can be used as an
3168 offset, we can determine which sub-variable will be pointed-to
3171 Return true if the expression is handled. For any other kind of
3172 expression, return false so that each operand can be added as a
3173 separate constraint by the caller. */
3176 handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr)
3179 struct constraint_expr *c, *c2;
3182 VEC (ce_s, heap) *temp = NULL;
3183 unsigned int rhsoffset = 0;
3185 if (TREE_CODE (expr) != PLUS_EXPR)
3188 op0 = TREE_OPERAND (expr, 0);
3189 op1 = TREE_OPERAND (expr, 1);
3191 get_constraint_for (op0, &temp);
3192 if (POINTER_TYPE_P (TREE_TYPE (op0))
3193 && TREE_CODE (op1) == INTEGER_CST)
3195 rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
3199 for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
3200 for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
3202 if (c2->type == ADDRESSOF && rhsoffset != 0)
3204 varinfo_t temp = get_varinfo (c2->var);
3206 /* An access one after the end of an array is valid,
3207 so simply punt on accesses we cannot resolve. */
3208 temp = first_vi_for_offset (temp, rhsoffset);
3215 c2->offset = rhsoffset;
3216 process_constraint (new_constraint (*c, *c2));
3219 VEC_free (ce_s, heap, temp);
3225 /* Walk statement T setting up aliasing constraints according to the
3226 references found in T. This function is the main part of the
3227 constraint builder. AI points to auxiliary alias information used
3228 when building alias sets and computing alias grouping heuristics. */
3231 find_func_aliases (tree origt)
3234 VEC(ce_s, heap) *lhsc = NULL;
3235 VEC(ce_s, heap) *rhsc = NULL;
3236 struct constraint_expr *c;
3238 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
3239 t = TREE_OPERAND (t, 0);
3241 /* Now build constraints expressions. */
3242 if (TREE_CODE (t) == PHI_NODE)
3244 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))));
3246 /* Only care about pointers and structures containing
3248 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
3249 || TREE_CODE (TREE_TYPE (PHI_RESULT (t))) == COMPLEX_TYPE)
3254 /* For a phi node, assign all the arguments to
3256 get_constraint_for (PHI_RESULT (t), &lhsc);
3257 for (i = 0; i < PHI_NUM_ARGS (t); i++)
3260 tree strippedrhs = PHI_ARG_DEF (t, i);
3262 STRIP_NOPS (strippedrhs);
3263 rhstype = TREE_TYPE (strippedrhs);
3264 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
3266 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3268 struct constraint_expr *c2;
3269 while (VEC_length (ce_s, rhsc) > 0)
3271 c2 = VEC_last (ce_s, rhsc);
3272 process_constraint (new_constraint (*c, *c2));
3273 VEC_pop (ce_s, rhsc);
3279 /* In IPA mode, we need to generate constraints to pass call
3280 arguments through their calls. There are two case, either a
3281 modify_expr when we are returning a value, or just a plain
3282 call_expr when we are not. */
3283 else if (in_ipa_mode
3284 && ((TREE_CODE (t) == MODIFY_EXPR
3285 && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR
3286 && !(call_expr_flags (TREE_OPERAND (t, 1))
3287 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
3288 || (TREE_CODE (t) == CALL_EXPR
3289 && !(call_expr_flags (t)
3290 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))))
3299 if (TREE_CODE (t) == MODIFY_EXPR)
3301 lhsop = TREE_OPERAND (t, 0);
3302 rhsop = TREE_OPERAND (t, 1);
3309 decl = get_callee_fndecl (rhsop);
3311 /* If we can directly resolve the function being called, do so.
3312 Otherwise, it must be some sort of indirect expression that
3313 we should still be able to handle. */
3316 varid = get_id_for_tree (decl);
3320 decl = TREE_OPERAND (rhsop, 0);
3321 varid = get_id_for_tree (decl);
3324 /* Assign all the passed arguments to the appropriate incoming
3325 parameters of the function. */
3326 fi = get_varinfo (varid);
3327 arglist = TREE_OPERAND (rhsop, 1);
3329 for (;arglist; arglist = TREE_CHAIN (arglist))
3331 tree arg = TREE_VALUE (arglist);
3332 struct constraint_expr lhs ;
3333 struct constraint_expr *rhsp;
3335 get_constraint_for (arg, &rhsc);
3336 if (TREE_CODE (decl) != FUNCTION_DECL)
3345 lhs.var = first_vi_for_offset (fi, i)->id;
3348 while (VEC_length (ce_s, rhsc) != 0)
3350 rhsp = VEC_last (ce_s, rhsc);
3351 process_constraint (new_constraint (lhs, *rhsp));
3352 VEC_pop (ce_s, rhsc);
3356 /* If we are returning a value, assign it to the result. */
3359 struct constraint_expr rhs;
3360 struct constraint_expr *lhsp;
3363 get_constraint_for (lhsop, &lhsc);
3364 if (TREE_CODE (decl) != FUNCTION_DECL)
3373 rhs.var = first_vi_for_offset (fi, i)->id;
3376 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3377 process_constraint (new_constraint (*lhsp, rhs));
3380 /* Otherwise, just a regular assignment statement. */
3381 else if (TREE_CODE (t) == MODIFY_EXPR)
3383 tree lhsop = TREE_OPERAND (t, 0);
3384 tree rhsop = TREE_OPERAND (t, 1);
3387 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3388 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)
3389 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop))
3390 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE))
3392 do_structure_copy (lhsop, rhsop);
3396 /* Only care about operations with pointers, structures
3397 containing pointers, dereferences, and call expressions. */
3398 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
3399 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3400 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE
3401 || TREE_CODE (rhsop) == CALL_EXPR)
3403 get_constraint_for (lhsop, &lhsc);
3404 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
3406 /* RHS that consist of unary operations,
3407 exceptional types, or bare decls/constants, get
3408 handled directly by get_constraint_for. */
3410 case tcc_declaration:
3412 case tcc_exceptional:
3413 case tcc_expression:
3418 get_constraint_for (rhsop, &rhsc);
3419 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3421 struct constraint_expr *c2;
3424 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3425 process_constraint (new_constraint (*c, *c2));
3433 /* For pointer arithmetic of the form
3434 PTR + CST, we can simply use PTR's
3435 constraint because pointer arithmetic is
3436 not allowed to go out of bounds. */
3437 if (handle_ptr_arith (lhsc, rhsop))
3442 /* Otherwise, walk each operand. Notice that we
3443 can't use the operand interface because we need
3444 to process expressions other than simple operands
3445 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3447 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
3449 tree op = TREE_OPERAND (rhsop, i);
3452 gcc_assert (VEC_length (ce_s, rhsc) == 0);
3453 get_constraint_for (op, &rhsc);
3454 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3456 struct constraint_expr *c2;
3457 while (VEC_length (ce_s, rhsc) > 0)
3459 c2 = VEC_last (ce_s, rhsc);
3460 process_constraint (new_constraint (*c, *c2));
3461 VEC_pop (ce_s, rhsc);
3470 /* After promoting variables and computing aliasing we will
3471 need to re-scan most statements. FIXME: Try to minimize the
3472 number of statements re-scanned. It's not really necessary to
3473 re-scan *all* statements. */
3474 mark_stmt_modified (origt);
3475 VEC_free (ce_s, heap, rhsc);
3476 VEC_free (ce_s, heap, lhsc);
3480 /* Find the first varinfo in the same variable as START that overlaps with
3482 Effectively, walk the chain of fields for the variable START to find the
3483 first field that overlaps with OFFSET.
3484 Return NULL if we can't find one. */
3487 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3489 varinfo_t curr = start;
3492 /* We may not find a variable in the field list with the actual
3493 offset when when we have glommed a structure to a variable.
3494 In that case, however, offset should still be within the size
3496 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3504 /* Insert the varinfo FIELD into the field list for BASE, at the front
3508 insert_into_field_list (varinfo_t base, varinfo_t field)
3510 varinfo_t prev = base;
3511 varinfo_t curr = base->next;
3517 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3521 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
3523 varinfo_t prev = base;
3524 varinfo_t curr = base->next;
3535 if (field->offset <= curr->offset)
3540 field->next = prev->next;
3545 /* qsort comparison function for two fieldoff's PA and PB */
3548 fieldoff_compare (const void *pa, const void *pb)
3550 const fieldoff_s *foa = (const fieldoff_s *)pa;
3551 const fieldoff_s *fob = (const fieldoff_s *)pb;
3552 HOST_WIDE_INT foasize, fobsize;
3554 if (foa->offset != fob->offset)
3555 return foa->offset - fob->offset;
3557 foasize = TREE_INT_CST_LOW (foa->size);
3558 fobsize = TREE_INT_CST_LOW (fob->size);
3559 return foasize - fobsize;
3562 /* Sort a fieldstack according to the field offset and sizes. */
3563 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3565 qsort (VEC_address (fieldoff_s, fieldstack),
3566 VEC_length (fieldoff_s, fieldstack),
3567 sizeof (fieldoff_s),
3571 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3572 of TYPE onto fieldstack, recording their offsets along the way.
3573 OFFSET is used to keep track of the offset in this entire structure, rather
3574 than just the immediately containing structure. Returns the number
3576 HAS_UNION is set to true if we find a union type as a field of
3580 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
3581 HOST_WIDE_INT offset, bool *has_union)
3586 if (TREE_CODE (type) == COMPLEX_TYPE)
3588 fieldoff_s *real_part, *img_part;
3589 real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3590 real_part->type = TREE_TYPE (type);
3591 real_part->size = TYPE_SIZE (TREE_TYPE (type));
3592 real_part->offset = offset;
3593 real_part->decl = NULL_TREE;
3595 img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3596 img_part->type = TREE_TYPE (type);
3597 img_part->size = TYPE_SIZE (TREE_TYPE (type));
3598 img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
3599 img_part->decl = NULL_TREE;
3604 if (TREE_CODE (type) == ARRAY_TYPE)
3606 tree sz = TYPE_SIZE (type);
3607 tree elsz = TYPE_SIZE (TREE_TYPE (type));
3612 || ! host_integerp (sz, 1)
3613 || TREE_INT_CST_LOW (sz) == 0
3615 || ! host_integerp (elsz, 1)
3616 || TREE_INT_CST_LOW (elsz) == 0)
3619 nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
3620 if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
3623 for (i = 0; i < nr; ++i)
3629 && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
3630 || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
3633 if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
3635 else if (!(pushed = push_fields_onto_fieldstack
3636 (TREE_TYPE (type), fieldstack,
3637 offset + i * TREE_INT_CST_LOW (elsz), has_union)))
3638 /* Empty structures may have actual size, like in C++. So
3639 see if we didn't push any subfields and the size is
3640 nonzero, push the field onto the stack */
3647 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3648 pair->type = TREE_TYPE (type);
3650 pair->decl = NULL_TREE;
3651 pair->offset = offset + i * TREE_INT_CST_LOW (elsz);
3661 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
3662 if (TREE_CODE (field) == FIELD_DECL)
3668 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3669 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3672 if (!var_can_have_subvars (field))
3674 else if (!(pushed = push_fields_onto_fieldstack
3675 (TREE_TYPE (field), fieldstack,
3676 offset + bitpos_of_field (field), has_union))
3677 && DECL_SIZE (field)
3678 && !integer_zerop (DECL_SIZE (field)))
3679 /* Empty structures may have actual size, like in C++. So
3680 see if we didn't push any subfields and the size is
3681 nonzero, push the field onto the stack */
3688 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3689 pair->type = TREE_TYPE (field);
3690 pair->size = DECL_SIZE (field);
3692 pair->offset = offset + bitpos_of_field (field);
3703 make_constraint_to_anything (varinfo_t vi)
3705 struct constraint_expr lhs, rhs;
3711 rhs.var = anything_id;
3713 rhs.type = ADDRESSOF;
3714 process_constraint (new_constraint (lhs, rhs));
3717 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3718 if it is a varargs function. */
3721 count_num_arguments (tree decl, bool *is_varargs)
3726 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
3730 if (TREE_VALUE (t) == void_type_node)
3740 /* Creation function node for DECL, using NAME, and return the index
3741 of the variable we've created for the function. */
3744 create_function_info_for (tree decl, const char *name)
3746 unsigned int index = VEC_length (varinfo_t, varmap);
3750 bool is_varargs = false;
3752 /* Create the variable info. */
3754 vi = new_var_info (decl, index, name, index);
3759 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3760 insert_id_for_tree (vi->decl, index);
3761 VEC_safe_push (varinfo_t, heap, varmap, vi);
3765 /* If it's varargs, we don't know how many arguments it has, so we
3772 vi->is_unknown_size_var = true;
3777 arg = DECL_ARGUMENTS (decl);
3779 /* Set up variables for each argument. */
3780 for (i = 1; i < vi->fullsize; i++)
3783 const char *newname;
3785 unsigned int newindex;
3786 tree argdecl = decl;
3791 newindex = VEC_length (varinfo_t, varmap);
3792 asprintf (&tempname, "%s.arg%d", name, i-1);
3793 newname = ggc_strdup (tempname);
3796 argvi = new_var_info (argdecl, newindex,newname, newindex);
3797 argvi->decl = argdecl;
3798 VEC_safe_push (varinfo_t, heap, varmap, argvi);
3801 argvi->fullsize = vi->fullsize;
3802 argvi->has_union = false;
3803 insert_into_field_list_sorted (vi, argvi);
3804 stats.total_vars ++;
3807 insert_id_for_tree (arg, newindex);
3808 arg = TREE_CHAIN (arg);
3812 /* Create a variable for the return var. */
3813 if (DECL_RESULT (decl) != NULL
3814 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
3817 const char *newname;
3819 unsigned int newindex;
3820 tree resultdecl = decl;
3824 if (DECL_RESULT (decl))
3825 resultdecl = DECL_RESULT (decl);
3827 newindex = VEC_length (varinfo_t, varmap);
3828 asprintf (&tempname, "%s.result", name);
3829 newname = ggc_strdup (tempname);
3832 resultvi = new_var_info (resultdecl, newindex, newname, newindex);
3833 resultvi->decl = resultdecl;
3834 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
3835 resultvi->offset = i;
3837 resultvi->fullsize = vi->fullsize;
3838 resultvi->has_union = false;
3839 insert_into_field_list_sorted (vi, resultvi);
3840 stats.total_vars ++;
3841 if (DECL_RESULT (decl))
3842 insert_id_for_tree (DECL_RESULT (decl), newindex);
3848 /* Return true if FIELDSTACK contains fields that overlap.
3849 FIELDSTACK is assumed to be sorted by offset. */
3852 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
3854 fieldoff_s *fo = NULL;
3856 HOST_WIDE_INT lastoffset = -1;
3858 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3860 if (fo->offset == lastoffset)
3862 lastoffset = fo->offset;
3866 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3867 This will also create any varinfo structures necessary for fields
3871 create_variable_info_for (tree decl, const char *name)
3873 unsigned int index = VEC_length (varinfo_t, varmap);
3875 tree decltype = TREE_TYPE (decl);
3876 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
3877 bool notokay = false;
3879 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
3880 VEC (fieldoff_s,heap) *fieldstack = NULL;
3882 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
3883 return create_function_info_for (decl, name);
3885 hasunion = TREE_CODE (decltype) == UNION_TYPE
3886 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
3887 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
3889 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
3892 VEC_free (fieldoff_s, heap, fieldstack);
3898 /* If the variable doesn't have subvars, we may end up needing to
3899 sort the field list and create fake variables for all the
3901 vi = new_var_info (decl, index, name, index);
3904 vi->has_union = hasunion;
3906 || TREE_CODE (declsize) != INTEGER_CST
3907 || TREE_CODE (decltype) == UNION_TYPE
3908 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
3910 vi->is_unknown_size_var = true;
3916 vi->fullsize = TREE_INT_CST_LOW (declsize);
3917 vi->size = vi->fullsize;
3920 insert_id_for_tree (vi->decl, index);
3921 VEC_safe_push (varinfo_t, heap, varmap, vi);
3922 if (is_global && (!flag_whole_program || !in_ipa_mode))
3923 make_constraint_to_anything (vi);
3926 if (use_field_sensitive
3928 && !vi->is_unknown_size_var
3929 && var_can_have_subvars (decl)
3930 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
3932 unsigned int newindex = VEC_length (varinfo_t, varmap);
3933 fieldoff_s *fo = NULL;
3936 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3939 || TREE_CODE (fo->size) != INTEGER_CST
3947 /* We can't sort them if we have a field with a variable sized type,
3948 which will make notokay = true. In that case, we are going to return
3949 without creating varinfos for the fields anyway, so sorting them is a
3953 sort_fieldstack (fieldstack);
3954 /* Due to some C++ FE issues, like PR 22488, we might end up
3955 what appear to be overlapping fields even though they,
3956 in reality, do not overlap. Until the C++ FE is fixed,
3957 we will simply disable field-sensitivity for these cases. */
3958 notokay = check_for_overlaps (fieldstack);
3962 if (VEC_length (fieldoff_s, fieldstack) != 0)
3963 fo = VEC_index (fieldoff_s, fieldstack, 0);
3965 if (fo == NULL || notokay)
3967 vi->is_unknown_size_var = 1;
3970 VEC_free (fieldoff_s, heap, fieldstack);
3974 vi->size = TREE_INT_CST_LOW (fo->size);
3975 vi->offset = fo->offset;
3976 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
3977 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
3981 const char *newname;
3984 newindex = VEC_length (varinfo_t, varmap);
3986 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (fo->decl));
3988 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC, vi->name, fo->offset);
3989 newname = ggc_strdup (tempname);
3991 newvi = new_var_info (decl, newindex, newname, newindex);
3992 newvi->offset = fo->offset;
3993 newvi->size = TREE_INT_CST_LOW (fo->size);
3994 newvi->fullsize = vi->fullsize;
3995 insert_into_field_list (vi, newvi);
3996 VEC_safe_push (varinfo_t, heap, varmap, newvi);
3997 if (is_global && (!flag_whole_program || !in_ipa_mode))
3998 make_constraint_to_anything (newvi);
4002 VEC_free (fieldoff_s, heap, fieldstack);
4007 /* Print out the points-to solution for VAR to FILE. */
4010 dump_solution_for_var (FILE *file, unsigned int var)
4012 varinfo_t vi = get_varinfo (var);
4016 fprintf (file, "%s = { ", vi->name);
4017 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
4019 fprintf (file, "%s ", get_varinfo (i)->name);
4021 fprintf (file, "}\n");
4024 /* Print the points-to solution for VAR to stdout. */
4027 debug_solution_for_var (unsigned int var)
4029 dump_solution_for_var (stdout, var);
4033 /* Create varinfo structures for all of the variables in the
4034 function for intraprocedural mode. */
4037 intra_create_variable_infos (void)
4041 /* For each incoming argument arg, ARG = &ANYTHING or a dummy variable if
4042 flag_argument_noalias > 1. */
4043 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4045 struct constraint_expr lhs;
4050 lhs.var = create_variable_info_for (t, alias_get_name (t));
4052 /* With flag_argument_noalias greater than one means that the incomming
4053 argument cannot alias anything except for itself so create a HEAP
4055 if (POINTER_TYPE_P (TREE_TYPE (t))
4056 && flag_argument_noalias > 1)
4059 struct constraint_expr rhs;
4060 tree heapvar = heapvar_lookup (t);
4062 if (heapvar == NULL_TREE)
4064 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4066 DECL_EXTERNAL (heapvar) = 1;
4067 if (referenced_vars)
4068 add_referenced_tmp_var (heapvar);
4069 heapvar_insert (t, heapvar);
4071 id = create_variable_info_for (heapvar,
4072 alias_get_name (heapvar));
4073 vi = get_varinfo (id);
4074 vi->is_artificial_var = 1;
4075 vi->is_heap_var = 1;
4077 rhs.type = ADDRESSOF;
4079 for (p = get_varinfo (lhs.var); p; p = p->next)
4081 struct constraint_expr temp = lhs;
4083 process_constraint (new_constraint (temp, rhs));
4087 for (p = get_varinfo (lhs.var); p; p = p->next)
4088 make_constraint_to_anything (p);
4092 /* Set bits in INTO corresponding to the variable uids in solution set
4096 set_uids_in_ptset (bitmap into, bitmap from)
4102 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4104 varinfo_t vi = get_varinfo (i);
4106 /* The only artificial variables that are allowed in a may-alias
4107 set are heap variables. */
4108 if (vi->is_artificial_var && !vi->is_heap_var)
4111 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
4113 /* Variables containing unions may need to be converted to
4114 their SFT's, because SFT's can have unions and we cannot. */
4115 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
4116 bitmap_set_bit (into, DECL_UID (sv->var));
4118 else if (TREE_CODE (vi->decl) == VAR_DECL
4119 || TREE_CODE (vi->decl) == PARM_DECL)
4121 if (var_can_have_subvars (vi->decl)
4122 && get_subvars_for_var (vi->decl))
4124 /* If VI->DECL is an aggregate for which we created
4125 SFTs, add the SFT corresponding to VI->OFFSET. */
4126 tree sft = get_subvar_at (vi->decl, vi->offset);
4128 bitmap_set_bit (into, DECL_UID (sft));
4132 /* Otherwise, just add VI->DECL to the alias set. */
4133 bitmap_set_bit (into, DECL_UID (vi->decl));
4140 static bool have_alias_info = false;
4142 /* Given a pointer variable P, fill in its points-to set, or return
4143 false if we can't. */
4146 find_what_p_points_to (tree p)
4148 unsigned int id = 0;
4151 if (!have_alias_info)
4154 /* For parameters, get at the points-to set for the actual parm
4156 if (TREE_CODE (p) == SSA_NAME
4157 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4158 && default_def (SSA_NAME_VAR (p)) == p)
4159 lookup_p = SSA_NAME_VAR (p);
4161 if (lookup_id_for_tree (lookup_p, &id))
4163 varinfo_t vi = get_varinfo (id);
4165 if (vi->is_artificial_var)
4168 /* See if this is a field or a structure. */
4169 if (vi->size != vi->fullsize)
4171 /* Nothing currently asks about structure fields directly,
4172 but when they do, we need code here to hand back the
4174 if (!var_can_have_subvars (vi->decl)
4175 || get_subvars_for_var (vi->decl) == NULL)
4180 struct ptr_info_def *pi = get_ptr_info (p);
4184 /* This variable may have been collapsed, let's get the real
4186 vi = get_varinfo (vi->node);
4188 /* Translate artificial variables into SSA_NAME_PTR_INFO
4190 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4192 varinfo_t vi = get_varinfo (i);
4194 if (vi->is_artificial_var)
4196 /* FIXME. READONLY should be handled better so that
4197 flow insensitive aliasing can disregard writable
4199 if (vi->id == nothing_id)
4201 else if (vi->id == anything_id)
4202 pi->pt_anything = 1;
4203 else if (vi->id == readonly_id)
4204 pi->pt_anything = 1;
4205 else if (vi->id == integer_id)
4206 pi->pt_anything = 1;
4207 else if (vi->is_heap_var)
4208 pi->pt_global_mem = 1;
4212 if (pi->pt_anything)
4216 pi->pt_vars = BITMAP_GGC_ALLOC ();
4218 set_uids_in_ptset (pi->pt_vars, vi->solution);
4220 if (bitmap_empty_p (pi->pt_vars))
4232 /* Dump points-to information to OUTFILE. */
4235 dump_sa_points_to_info (FILE *outfile)
4239 fprintf (outfile, "\nPoints-to sets\n\n");
4241 if (dump_flags & TDF_STATS)
4243 fprintf (outfile, "Stats:\n");
4244 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4245 fprintf (outfile, "Statically unified vars: %d\n",
4246 stats.unified_vars_static);
4247 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
4248 fprintf (outfile, "Dynamically unified vars: %d\n",
4249 stats.unified_vars_dynamic);
4250 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4251 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4254 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4255 dump_solution_for_var (outfile, i);
4259 /* Debug points-to information to stderr. */
4262 debug_sa_points_to_info (void)
4264 dump_sa_points_to_info (stderr);
4268 /* Initialize the always-existing constraint variables for NULL
4269 ANYTHING, READONLY, and INTEGER */
4272 init_base_vars (void)
4274 struct constraint_expr lhs, rhs;
4276 /* Create the NULL variable, used to represent that a variable points
4278 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4279 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
4280 insert_id_for_tree (nothing_tree, 0);
4281 var_nothing->is_artificial_var = 1;
4282 var_nothing->offset = 0;
4283 var_nothing->size = ~0;
4284 var_nothing->fullsize = ~0;
4285 var_nothing->is_special_var = 1;
4287 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
4289 /* Create the ANYTHING variable, used to represent that a variable
4290 points to some unknown piece of memory. */
4291 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4292 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
4293 insert_id_for_tree (anything_tree, 1);
4294 var_anything->is_artificial_var = 1;
4295 var_anything->size = ~0;
4296 var_anything->offset = 0;
4297 var_anything->next = NULL;
4298 var_anything->fullsize = ~0;
4299 var_anything->is_special_var = 1;
4302 /* Anything points to anything. This makes deref constraints just
4303 work in the presence of linked list and other p = *p type loops,
4304 by saying that *ANYTHING = ANYTHING. */
4305 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
4307 lhs.var = anything_id;
4309 rhs.type = ADDRESSOF;
4310 rhs.var = anything_id;
4312 var_anything->address_taken = true;
4314 /* This specifically does not use process_constraint because
4315 process_constraint ignores all anything = anything constraints, since all
4316 but this one are redundant. */
4317 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
4319 /* Create the READONLY variable, used to represent that a variable
4320 points to readonly memory. */
4321 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4322 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
4323 var_readonly->is_artificial_var = 1;
4324 var_readonly->offset = 0;
4325 var_readonly->size = ~0;
4326 var_readonly->fullsize = ~0;
4327 var_readonly->next = NULL;
4328 var_readonly->is_special_var = 1;
4329 insert_id_for_tree (readonly_tree, 2);
4331 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4333 /* readonly memory points to anything, in order to make deref
4334 easier. In reality, it points to anything the particular
4335 readonly variable can point to, but we don't track this
4338 lhs.var = readonly_id;
4340 rhs.type = ADDRESSOF;
4341 rhs.var = anything_id;
4344 process_constraint (new_constraint (lhs, rhs));
4346 /* Create the INTEGER variable, used to represent that a variable points
4348 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4349 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
4350 insert_id_for_tree (integer_tree, 3);
4351 var_integer->is_artificial_var = 1;
4352 var_integer->size = ~0;
4353 var_integer->fullsize = ~0;
4354 var_integer->offset = 0;
4355 var_integer->next = NULL;
4356 var_integer->is_special_var = 1;
4358 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
4360 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
4361 integer will point to. */
4363 lhs.var = integer_id;
4365 rhs.type = ADDRESSOF;
4366 rhs.var = anything_id;
4368 process_constraint (new_constraint (lhs, rhs));
4371 /* Return true if we actually need to solve the constraint graph in order to
4372 get our points-to sets. This is false when, for example, no addresses are
4373 taken other than special vars, or all points-to sets with members already
4374 contain the anything variable and there are no predecessors for other
4378 need_to_solve (void)
4382 bool found_address_taken = false;
4383 bool found_non_anything = false;
4385 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4387 if (v->is_special_var)
4390 if (v->address_taken)
4391 found_address_taken = true;
4394 && !bitmap_empty_p (v->solution)
4395 && !bitmap_bit_p (v->solution, anything_id))
4396 found_non_anything = true;
4397 else if (bitmap_empty_p (v->solution)
4398 && (VEC_length (constraint_edge_t, graph->preds[v->id]) != 0
4399 || (graph->zero_weight_preds[v->id] && !bitmap_empty_p (graph->zero_weight_preds[v->id]))))
4400 found_non_anything = true;
4402 if (found_address_taken && found_non_anything)
4409 /* Initialize things necessary to perform PTA */
4412 init_alias_vars (void)
4414 bitmap_obstack_initialize (&ptabitmap_obstack);
4415 bitmap_obstack_initialize (&predbitmap_obstack);
4417 constraint_pool = create_alloc_pool ("Constraint pool",
4418 sizeof (struct constraint), 30);
4419 variable_info_pool = create_alloc_pool ("Variable info pool",
4420 sizeof (struct variable_info), 30);
4421 constraint_edge_pool = create_alloc_pool ("Constraint edges",
4422 sizeof (struct constraint_edge), 30);
4424 constraints = VEC_alloc (constraint_t, heap, 8);
4425 varmap = VEC_alloc (varinfo_t, heap, 8);
4426 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
4427 memset (&stats, 0, sizeof (stats));
4433 /* Create points-to sets for the current function. See the comments
4434 at the start of the file for an algorithmic overview. */
4437 compute_points_to_sets (struct alias_info *ai)
4441 timevar_push (TV_TREE_PTA);
4445 intra_create_variable_infos ();
4447 /* Now walk all statements and derive aliases. */
4450 block_stmt_iterator bsi;
4453 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4455 if (is_gimple_reg (PHI_RESULT (phi)))
4457 find_func_aliases (phi);
4458 /* Update various related attributes like escaped
4459 addresses, pointer dereferences for loads and stores.
4460 This is used when creating name tags and alias
4462 update_alias_info (phi, ai);
4466 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4468 tree stmt = bsi_stmt (bsi);
4469 find_func_aliases (stmt);
4470 /* Update various related attributes like escaped
4471 addresses, pointer dereferences for loads and stores.
4472 This is used when creating name tags and alias
4474 update_alias_info (stmt, ai);
4478 build_constraint_graph ();
4482 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4483 dump_constraints (dump_file);
4486 if (need_to_solve ())
4490 "\nCollapsing static cycles and doing variable "
4493 find_and_collapse_graph_cycles (graph, false);
4494 perform_var_substitution (graph);
4497 fprintf (dump_file, "\nSolving graph:\n");
4499 solve_graph (graph);
4503 dump_sa_points_to_info (dump_file);
4505 have_alias_info = true;
4507 timevar_pop (TV_TREE_PTA);
4511 /* Delete created points-to sets. */
4514 delete_points_to_sets (void)
4519 htab_delete (id_for_tree);
4520 bitmap_obstack_release (&ptabitmap_obstack);
4521 bitmap_obstack_release (&predbitmap_obstack);
4522 VEC_free (constraint_t, heap, constraints);
4524 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4526 VEC_free (constraint_edge_t, heap, graph->succs[i]);
4527 VEC_free (constraint_edge_t, heap, graph->preds[i]);
4528 VEC_free (constraint_t, heap, v->complex);
4530 free (graph->zero_weight_preds);
4531 free (graph->zero_weight_succs);
4532 free (graph->succs);
4533 free (graph->preds);
4536 VEC_free (varinfo_t, heap, varmap);
4537 free_alloc_pool (variable_info_pool);
4538 free_alloc_pool (constraint_pool);
4539 free_alloc_pool (constraint_edge_pool);
4541 have_alias_info = false;
4544 /* Return true if we should execute IPA PTA. */
4548 return (flag_unit_at_a_time != 0
4550 /* Don't bother doing anything if the program has errors. */
4551 && !(errorcount || sorrycount));
4554 /* Execute the driver for IPA PTA. */
4556 ipa_pta_execute (void)
4558 struct cgraph_node *node;
4560 init_alias_heapvars ();
4563 for (node = cgraph_nodes; node; node = node->next)
4565 if (!node->analyzed || cgraph_is_master_clone (node))
4569 varid = create_function_info_for (node->decl,
4570 cgraph_node_name (node));
4571 if (node->local.externally_visible)
4573 varinfo_t fi = get_varinfo (varid);
4574 for (; fi; fi = fi->next)
4575 make_constraint_to_anything (fi);
4579 for (node = cgraph_nodes; node; node = node->next)
4581 if (node->analyzed && cgraph_is_master_clone (node))
4583 struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
4585 tree old_func_decl = current_function_decl;
4588 "Generating constraints for %s\n",
4589 cgraph_node_name (node));
4591 current_function_decl = node->decl;
4593 FOR_EACH_BB_FN (bb, cfun)
4595 block_stmt_iterator bsi;
4598 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4600 if (is_gimple_reg (PHI_RESULT (phi)))
4602 find_func_aliases (phi);
4606 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4608 tree stmt = bsi_stmt (bsi);
4609 find_func_aliases (stmt);
4612 current_function_decl = old_func_decl;
4617 /* Make point to anything. */
4621 build_constraint_graph ();
4625 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4626 dump_constraints (dump_file);
4629 if (need_to_solve ())
4633 "\nCollapsing static cycles and doing variable "
4636 find_and_collapse_graph_cycles (graph, false);
4637 perform_var_substitution (graph);
4640 fprintf (dump_file, "\nSolving graph:\n");
4642 solve_graph (graph);
4646 dump_sa_points_to_info (dump_file);
4648 delete_alias_heapvars ();
4649 delete_points_to_sets ();
4652 struct tree_opt_pass pass_ipa_pta =
4655 gate_ipa_pta, /* gate */
4656 ipa_pta_execute, /* execute */
4659 0, /* static_pass_number */
4660 TV_IPA_PTA, /* tv_id */
4661 0, /* properties_required */
4662 0, /* properties_provided */
4663 0, /* properties_destroyed */
4664 0, /* todo_flags_start */
4665 0, /* todo_flags_finish */
4669 /* Initialize the heapvar for statement mapping. */
4671 init_alias_heapvars (void)
4673 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq, NULL);
4677 delete_alias_heapvars (void)
4679 htab_delete (heapvar_for_stmt);
4683 #include "gt-tree-ssa-structalias.h"