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);
2488 get_constraint_for (exp, results);
2489 /* Make sure we capture constraints to all elements
2491 if ((handled_component_p (exp)
2492 && ref_contains_array_ref (exp))
2493 || TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE)
2495 struct constraint_expr *origrhs;
2497 struct constraint_expr tmp;
2499 gcc_assert (VEC_length (ce_s, *results) == 1);
2500 origrhs = VEC_last (ce_s, *results);
2502 VEC_pop (ce_s, *results);
2503 origvar = get_varinfo (origrhs->var);
2504 for (; origvar; origvar = origvar->next)
2506 tmp.var = origvar->id;
2507 VEC_safe_push (ce_s, heap, *results, &tmp);
2510 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2512 if (c->type == DEREF)
2515 c->type = ADDRESSOF;
2522 /* XXX: In interprocedural mode, if we didn't have the
2523 body, we would need to do *each pointer argument =
2525 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2528 tree heapvar = heapvar_lookup (t);
2530 if (heapvar == NULL)
2532 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2533 DECL_EXTERNAL (heapvar) = 1;
2534 if (referenced_vars)
2535 add_referenced_tmp_var (heapvar);
2536 heapvar_insert (t, heapvar);
2539 temp.var = create_variable_info_for (heapvar,
2540 alias_get_name (heapvar));
2542 vi = get_varinfo (temp.var);
2543 vi->is_artificial_var = 1;
2544 vi->is_heap_var = 1;
2545 temp.type = ADDRESSOF;
2547 VEC_safe_push (ce_s, heap, *results, &temp);
2553 temp.type = ADDRESSOF;
2554 temp.var = anything_id;
2556 VEC_safe_push (ce_s, heap, *results, &temp);
2563 switch (TREE_CODE (t))
2567 get_constraint_for (TREE_OPERAND (t, 0), results);
2572 case ARRAY_RANGE_REF:
2574 get_constraint_for_component_ref (t, results);
2578 temp.type = ADDRESSOF;
2579 temp.var = anything_id;
2581 VEC_safe_push (ce_s, heap, *results, &temp);
2588 switch (TREE_CODE (t))
2592 case NON_LVALUE_EXPR:
2594 tree op = TREE_OPERAND (t, 0);
2596 /* Cast from non-pointer to pointers are bad news for us.
2597 Anything else, we see through */
2598 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2599 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2601 get_constraint_for (op, results);
2609 temp.type = ADDRESSOF;
2610 temp.var = anything_id;
2612 VEC_safe_push (ce_s, heap, *results, &temp);
2617 case tcc_exceptional:
2619 switch (TREE_CODE (t))
2623 get_constraint_for (PHI_RESULT (t), results);
2629 struct constraint_expr temp;
2630 temp = get_constraint_exp_from_ssa_var (t);
2631 VEC_safe_push (ce_s, heap, *results, &temp);
2637 temp.type = ADDRESSOF;
2638 temp.var = anything_id;
2640 VEC_safe_push (ce_s, heap, *results, &temp);
2645 case tcc_declaration:
2647 struct constraint_expr temp;
2648 temp = get_constraint_exp_from_ssa_var (t);
2649 VEC_safe_push (ce_s, heap, *results, &temp);
2654 temp.type = ADDRESSOF;
2655 temp.var = anything_id;
2657 VEC_safe_push (ce_s, heap, *results, &temp);
2664 /* Handle the structure copy case where we have a simple structure copy
2665 between LHS and RHS that is of SIZE (in bits)
2667 For each field of the lhs variable (lhsfield)
2668 For each field of the rhs variable at lhsfield.offset (rhsfield)
2669 add the constraint lhsfield = rhsfield
2671 If we fail due to some kind of type unsafety or other thing we
2672 can't handle, return false. We expect the caller to collapse the
2673 variable in that case. */
2676 do_simple_structure_copy (const struct constraint_expr lhs,
2677 const struct constraint_expr rhs,
2678 const unsigned HOST_WIDE_INT size)
2680 varinfo_t p = get_varinfo (lhs.var);
2681 unsigned HOST_WIDE_INT pstart, last;
2683 last = p->offset + size;
2684 for (; p && p->offset < last; p = p->next)
2687 struct constraint_expr templhs = lhs;
2688 struct constraint_expr temprhs = rhs;
2689 unsigned HOST_WIDE_INT fieldoffset;
2691 templhs.var = p->id;
2692 q = get_varinfo (temprhs.var);
2693 fieldoffset = p->offset - pstart;
2694 q = first_vi_for_offset (q, q->offset + fieldoffset);
2697 temprhs.var = q->id;
2698 process_constraint (new_constraint (templhs, temprhs));
2704 /* Handle the structure copy case where we have a structure copy between a
2705 aggregate on the LHS and a dereference of a pointer on the RHS
2706 that is of SIZE (in bits)
2708 For each field of the lhs variable (lhsfield)
2709 rhs.offset = lhsfield->offset
2710 add the constraint lhsfield = rhs
2714 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2715 const struct constraint_expr rhs,
2716 const unsigned HOST_WIDE_INT size)
2718 varinfo_t p = get_varinfo (lhs.var);
2719 unsigned HOST_WIDE_INT pstart,last;
2721 last = p->offset + size;
2723 for (; p && p->offset < last; p = p->next)
2726 struct constraint_expr templhs = lhs;
2727 struct constraint_expr temprhs = rhs;
2728 unsigned HOST_WIDE_INT fieldoffset;
2731 if (templhs.type == SCALAR)
2732 templhs.var = p->id;
2734 templhs.offset = p->offset;
2736 q = get_varinfo (temprhs.var);
2737 fieldoffset = p->offset - pstart;
2738 temprhs.offset += fieldoffset;
2739 process_constraint (new_constraint (templhs, temprhs));
2743 /* Handle the structure copy case where we have a structure copy
2744 between a aggregate on the RHS and a dereference of a pointer on
2745 the LHS that is of SIZE (in bits)
2747 For each field of the rhs variable (rhsfield)
2748 lhs.offset = rhsfield->offset
2749 add the constraint lhs = rhsfield
2753 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2754 const struct constraint_expr rhs,
2755 const unsigned HOST_WIDE_INT size)
2757 varinfo_t p = get_varinfo (rhs.var);
2758 unsigned HOST_WIDE_INT pstart,last;
2760 last = p->offset + size;
2762 for (; p && p->offset < last; p = p->next)
2765 struct constraint_expr templhs = lhs;
2766 struct constraint_expr temprhs = rhs;
2767 unsigned HOST_WIDE_INT fieldoffset;
2770 if (temprhs.type == SCALAR)
2771 temprhs.var = p->id;
2773 temprhs.offset = p->offset;
2775 q = get_varinfo (templhs.var);
2776 fieldoffset = p->offset - pstart;
2777 templhs.offset += fieldoffset;
2778 process_constraint (new_constraint (templhs, temprhs));
2782 /* Sometimes, frontends like to give us bad type information. This
2783 function will collapse all the fields from VAR to the end of VAR,
2784 into VAR, so that we treat those fields as a single variable.
2785 We return the variable they were collapsed into. */
2788 collapse_rest_of_var (unsigned int var)
2790 varinfo_t currvar = get_varinfo (var);
2793 for (field = currvar->next; field; field = field->next)
2796 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
2797 field->name, currvar->name);
2799 gcc_assert (!field->collapsed_to);
2800 field->collapsed_to = currvar;
2803 currvar->next = NULL;
2804 currvar->size = currvar->fullsize - currvar->offset;
2809 /* Handle aggregate copies by expanding into copies of the respective
2810 fields of the structures. */
2813 do_structure_copy (tree lhsop, tree rhsop)
2815 struct constraint_expr lhs, rhs, tmp;
2816 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
2818 unsigned HOST_WIDE_INT lhssize;
2819 unsigned HOST_WIDE_INT rhssize;
2821 get_constraint_for (lhsop, &lhsc);
2822 get_constraint_for (rhsop, &rhsc);
2823 gcc_assert (VEC_length (ce_s, lhsc) == 1);
2824 gcc_assert (VEC_length (ce_s, rhsc) == 1);
2825 lhs = *(VEC_last (ce_s, lhsc));
2826 rhs = *(VEC_last (ce_s, rhsc));
2828 VEC_free (ce_s, heap, lhsc);
2829 VEC_free (ce_s, heap, rhsc);
2831 /* If we have special var = x, swap it around. */
2832 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2839 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2840 possible it's something we could handle. However, most cases falling
2841 into this are dealing with transparent unions, which are slightly
2843 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2845 rhs.type = ADDRESSOF;
2846 rhs.var = anything_id;
2849 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2850 that special var. */
2851 if (rhs.var <= integer_id)
2853 for (p = get_varinfo (lhs.var); p; p = p->next)
2855 struct constraint_expr templhs = lhs;
2856 struct constraint_expr temprhs = rhs;
2858 if (templhs.type == SCALAR )
2859 templhs.var = p->id;
2861 templhs.offset += p->offset;
2862 process_constraint (new_constraint (templhs, temprhs));
2867 tree rhstype = TREE_TYPE (rhsop);
2868 tree lhstype = TREE_TYPE (lhsop);
2872 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
2873 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
2875 /* If we have a variably sized types on the rhs or lhs, and a deref
2876 constraint, add the constraint, lhsconstraint = &ANYTHING.
2877 This is conservatively correct because either the lhs is an unknown
2878 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2879 constraint, and every variable it can point to must be unknown sized
2880 anyway, so we don't need to worry about fields at all. */
2881 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2882 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2884 rhs.var = anything_id;
2885 rhs.type = ADDRESSOF;
2887 process_constraint (new_constraint (lhs, rhs));
2891 /* The size only really matters insofar as we don't set more or less of
2892 the variable. If we hit an unknown size var, the size should be the
2893 whole darn thing. */
2894 if (get_varinfo (rhs.var)->is_unknown_size_var)
2897 rhssize = TREE_INT_CST_LOW (rhstypesize);
2899 if (get_varinfo (lhs.var)->is_unknown_size_var)
2902 lhssize = TREE_INT_CST_LOW (lhstypesize);
2905 if (rhs.type == SCALAR && lhs.type == SCALAR)
2907 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
2909 lhs.var = collapse_rest_of_var (lhs.var);
2910 rhs.var = collapse_rest_of_var (rhs.var);
2915 process_constraint (new_constraint (lhs, rhs));
2918 else if (lhs.type != DEREF && rhs.type == DEREF)
2919 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2920 else if (lhs.type == DEREF && rhs.type != DEREF)
2921 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2924 tree pointedtotype = lhstype;
2927 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
2928 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
2929 do_structure_copy (tmpvar, rhsop);
2930 do_structure_copy (lhsop, tmpvar);
2935 /* Update related alias information kept in AI. This is used when
2936 building name tags, alias sets and deciding grouping heuristics.
2937 STMT is the statement to process. This function also updates
2938 ADDRESSABLE_VARS. */
2941 update_alias_info (tree stmt, struct alias_info *ai)
2944 use_operand_p use_p;
2946 enum escape_type stmt_escape_type = is_escape_site (stmt, ai);
2949 /* Mark all the variables whose address are taken by the statement. */
2950 addr_taken = addresses_taken (stmt);
2953 bitmap_ior_into (addressable_vars, addr_taken);
2955 /* If STMT is an escape point, all the addresses taken by it are
2957 if (stmt_escape_type != NO_ESCAPE)
2962 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
2964 tree rvar = referenced_var (i);
2965 if (!unmodifiable_var_p (rvar))
2966 mark_call_clobbered (rvar, stmt_escape_type);
2971 /* Process each operand use. If an operand may be aliased, keep
2972 track of how many times it's being used. For pointers, determine
2973 whether they are dereferenced by the statement, or whether their
2974 value escapes, etc. */
2975 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2979 struct ptr_info_def *pi;
2980 bool is_store, is_potential_deref;
2981 unsigned num_uses, num_derefs;
2983 op = USE_FROM_PTR (use_p);
2985 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2986 to the set of addressable variables. */
2987 if (TREE_CODE (op) == ADDR_EXPR)
2989 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
2991 /* PHI nodes don't have annotations for pinning the set
2992 of addresses taken, so we collect them here.
2994 FIXME, should we allow PHI nodes to have annotations
2995 so that they can be treated like regular statements?
2996 Currently, they are treated as second-class
2998 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
3002 /* Ignore constants. */
3003 if (TREE_CODE (op) != SSA_NAME)
3006 var = SSA_NAME_VAR (op);
3007 v_ann = var_ann (var);
3009 /* The base variable of an ssa name must be a GIMPLE register, and thus
3010 it cannot be aliased. */
3011 gcc_assert (!may_be_aliased (var));
3013 /* We are only interested in pointers. */
3014 if (!POINTER_TYPE_P (TREE_TYPE (op)))
3017 pi = get_ptr_info (op);
3019 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3020 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
3022 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
3023 VARRAY_PUSH_TREE (ai->processed_ptrs, op);
3026 /* If STMT is a PHI node, then it will not have pointer
3027 dereferences and it will not be an escape point. */
3028 if (TREE_CODE (stmt) == PHI_NODE)
3031 /* Determine whether OP is a dereferenced pointer, and if STMT
3032 is an escape point, whether OP escapes. */
3033 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
3035 /* Handle a corner case involving address expressions of the
3036 form '&PTR->FLD'. The problem with these expressions is that
3037 they do not represent a dereference of PTR. However, if some
3038 other transformation propagates them into an INDIRECT_REF
3039 expression, we end up with '*(&PTR->FLD)' which is folded
3042 So, if the original code had no other dereferences of PTR,
3043 the aliaser will not create memory tags for it, and when
3044 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3045 memory operations will receive no V_MAY_DEF/VUSE operands.
3047 One solution would be to have count_uses_and_derefs consider
3048 &PTR->FLD a dereference of PTR. But that is wrong, since it
3049 is not really a dereference but an offset calculation.
3051 What we do here is to recognize these special ADDR_EXPR
3052 nodes. Since these expressions are never GIMPLE values (they
3053 are not GIMPLE invariants), they can only appear on the RHS
3054 of an assignment and their base address is always an
3055 INDIRECT_REF expression. */
3056 is_potential_deref = false;
3057 if (TREE_CODE (stmt) == MODIFY_EXPR
3058 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
3059 && !is_gimple_val (TREE_OPERAND (stmt, 1)))
3061 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3062 this represents a potential dereference of PTR. */
3063 tree rhs = TREE_OPERAND (stmt, 1);
3064 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3065 if (TREE_CODE (base) == INDIRECT_REF
3066 && TREE_OPERAND (base, 0) == op)
3067 is_potential_deref = true;
3070 if (num_derefs > 0 || is_potential_deref)
3072 /* Mark OP as dereferenced. In a subsequent pass,
3073 dereferenced pointers that point to a set of
3074 variables will be assigned a name tag to alias
3075 all the variables OP points to. */
3076 pi->is_dereferenced = 1;
3078 /* Keep track of how many time we've dereferenced each
3080 NUM_REFERENCES_INC (v_ann);
3082 /* If this is a store operation, mark OP as being
3083 dereferenced to store, otherwise mark it as being
3084 dereferenced to load. */
3086 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3088 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
3091 if (stmt_escape_type != NO_ESCAPE && num_derefs < num_uses)
3093 /* If STMT is an escape point and STMT contains at
3094 least one direct use of OP, then the value of OP
3095 escapes and so the pointed-to variables need to
3096 be marked call-clobbered. */
3097 pi->value_escapes_p = 1;
3098 pi->escape_mask |= stmt_escape_type;
3100 /* If the statement makes a function call, assume
3101 that pointer OP will be dereferenced in a store
3102 operation inside the called function. */
3103 if (get_call_expr_in (stmt))
3105 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
3106 pi->is_dereferenced = 1;
3111 if (TREE_CODE (stmt) == PHI_NODE)
3114 /* Update reference counter for definitions to any
3115 potentially aliased variable. This is used in the alias
3116 grouping heuristics. */
3117 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3119 tree var = SSA_NAME_VAR (op);
3120 var_ann_t ann = var_ann (var);
3121 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3122 if (may_be_aliased (var))
3123 NUM_REFERENCES_INC (ann);
3127 /* Mark variables in V_MAY_DEF operands as being written to. */
3128 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
3130 tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
3131 bitmap_set_bit (ai->written_vars, DECL_UID (var));
3136 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3137 Expressions of the type PTR + CST can be handled in two ways:
3139 1- If the constraint for PTR is ADDRESSOF for a non-structure
3140 variable, then we can use it directly because adding or
3141 subtracting a constant may not alter the original ADDRESSOF
3142 constraint (i.e., pointer arithmetic may not legally go outside
3143 an object's boundaries).
3145 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3146 then if CST is a compile-time constant that can be used as an
3147 offset, we can determine which sub-variable will be pointed-to
3150 Return true if the expression is handled. For any other kind of
3151 expression, return false so that each operand can be added as a
3152 separate constraint by the caller. */
3155 handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr)
3158 struct constraint_expr *c, *c2;
3161 VEC (ce_s, heap) *temp = NULL;
3162 unsigned int rhsoffset = 0;
3164 if (TREE_CODE (expr) != PLUS_EXPR)
3167 op0 = TREE_OPERAND (expr, 0);
3168 op1 = TREE_OPERAND (expr, 1);
3170 get_constraint_for (op0, &temp);
3171 if (POINTER_TYPE_P (TREE_TYPE (op0))
3172 && TREE_CODE (op1) == INTEGER_CST)
3174 rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
3178 for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
3179 for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
3181 if (c2->type == ADDRESSOF && rhsoffset != 0)
3183 varinfo_t temp = get_varinfo (c2->var);
3185 /* An access one after the end of an array is valid,
3186 so simply punt on accesses we cannot resolve. */
3187 temp = first_vi_for_offset (temp, rhsoffset);
3194 c2->offset = rhsoffset;
3195 process_constraint (new_constraint (*c, *c2));
3198 VEC_free (ce_s, heap, temp);
3204 /* Walk statement T setting up aliasing constraints according to the
3205 references found in T. This function is the main part of the
3206 constraint builder. AI points to auxiliary alias information used
3207 when building alias sets and computing alias grouping heuristics. */
3210 find_func_aliases (tree origt)
3213 VEC(ce_s, heap) *lhsc = NULL;
3214 VEC(ce_s, heap) *rhsc = NULL;
3215 struct constraint_expr *c;
3217 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
3218 t = TREE_OPERAND (t, 0);
3220 /* Now build constraints expressions. */
3221 if (TREE_CODE (t) == PHI_NODE)
3223 /* Only care about pointers and structures containing
3225 if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
3226 || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
3227 || TREE_CODE (TREE_TYPE (PHI_RESULT (t))) == COMPLEX_TYPE)
3232 /* For a phi node, assign all the arguments to
3234 get_constraint_for (PHI_RESULT (t), &lhsc);
3235 for (i = 0; i < PHI_NUM_ARGS (t); i++)
3238 tree strippedrhs = PHI_ARG_DEF (t, i);
3240 STRIP_NOPS (strippedrhs);
3241 rhstype = TREE_TYPE (strippedrhs);
3242 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
3244 if (TREE_CODE (strippedrhs) == ADDR_EXPR
3245 && (AGGREGATE_TYPE_P (TREE_TYPE (rhstype))
3246 || TREE_CODE (TREE_TYPE (rhstype)) == COMPLEX_TYPE)
3247 && VEC_length (ce_s, rhsc) == 1)
3249 struct constraint_expr *origrhs;
3251 struct constraint_expr tmp;
3253 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3254 origrhs = VEC_last (ce_s, rhsc);
3256 VEC_pop (ce_s, rhsc);
3257 origvar = get_varinfo (origrhs->var);
3258 for (; origvar; origvar = origvar->next)
3260 tmp.var = origvar->id;
3261 VEC_safe_push (ce_s, heap, rhsc, &tmp);
3265 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3267 struct constraint_expr *c2;
3268 while (VEC_length (ce_s, rhsc) > 0)
3270 c2 = VEC_last (ce_s, rhsc);
3271 process_constraint (new_constraint (*c, *c2));
3272 VEC_pop (ce_s, rhsc);
3278 /* In IPA mode, we need to generate constraints to pass call
3279 arguments through their calls. There are two case, either a
3280 modify_expr when we are returning a value, or just a plain
3281 call_expr when we are not. */
3282 else if (in_ipa_mode
3283 && ((TREE_CODE (t) == MODIFY_EXPR
3284 && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR
3285 && !(call_expr_flags (TREE_OPERAND (t, 1))
3286 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
3287 || (TREE_CODE (t) == CALL_EXPR
3288 && !(call_expr_flags (t)
3289 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))))
3298 if (TREE_CODE (t) == MODIFY_EXPR)
3300 lhsop = TREE_OPERAND (t, 0);
3301 rhsop = TREE_OPERAND (t, 1);
3308 decl = get_callee_fndecl (rhsop);
3310 /* If we can directly resolve the function being called, do so.
3311 Otherwise, it must be some sort of indirect expression that
3312 we should still be able to handle. */
3315 varid = get_id_for_tree (decl);
3319 decl = TREE_OPERAND (rhsop, 0);
3320 varid = get_id_for_tree (decl);
3323 /* Assign all the passed arguments to the appropriate incoming
3324 parameters of the function. */
3325 fi = get_varinfo (varid);
3326 arglist = TREE_OPERAND (rhsop, 1);
3328 for (;arglist; arglist = TREE_CHAIN (arglist))
3330 tree arg = TREE_VALUE (arglist);
3331 struct constraint_expr lhs ;
3332 struct constraint_expr *rhsp;
3334 get_constraint_for (arg, &rhsc);
3335 if (TREE_CODE (decl) != FUNCTION_DECL)
3344 lhs.var = first_vi_for_offset (fi, i)->id;
3347 while (VEC_length (ce_s, rhsc) != 0)
3349 rhsp = VEC_last (ce_s, rhsc);
3350 process_constraint (new_constraint (lhs, *rhsp));
3351 VEC_pop (ce_s, rhsc);
3355 /* If we are returning a value, assign it to the result. */
3358 struct constraint_expr rhs;
3359 struct constraint_expr *lhsp;
3362 get_constraint_for (lhsop, &lhsc);
3363 if (TREE_CODE (decl) != FUNCTION_DECL)
3372 rhs.var = first_vi_for_offset (fi, i)->id;
3375 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3376 process_constraint (new_constraint (*lhsp, rhs));
3379 /* Otherwise, just a regular assignment statement. */
3380 else if (TREE_CODE (t) == MODIFY_EXPR)
3382 tree lhsop = TREE_OPERAND (t, 0);
3383 tree rhsop = TREE_OPERAND (t, 1);
3386 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3387 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)
3388 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop))
3389 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE))
3391 do_structure_copy (lhsop, rhsop);
3395 /* Only care about operations with pointers, structures
3396 containing pointers, dereferences, and call expressions. */
3397 if (POINTER_TYPE_P (TREE_TYPE (lhsop))
3398 || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3399 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE
3400 || TREE_CODE (rhsop) == CALL_EXPR)
3402 get_constraint_for (lhsop, &lhsc);
3403 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
3405 /* RHS that consist of unary operations,
3406 exceptional types, or bare decls/constants, get
3407 handled directly by get_constraint_for. */
3409 case tcc_declaration:
3411 case tcc_exceptional:
3412 case tcc_expression:
3416 tree strippedrhs = rhsop;
3419 /* XXX: Push this back into the ADDR_EXPR
3420 case, and remove anyoffset handling. */
3421 STRIP_NOPS (strippedrhs);
3422 rhstype = TREE_TYPE (strippedrhs);
3424 get_constraint_for (rhsop, &rhsc);
3425 if (TREE_CODE (strippedrhs) == ADDR_EXPR
3426 && (AGGREGATE_TYPE_P (TREE_TYPE (rhstype))
3427 || TREE_CODE (TREE_TYPE (rhstype)) == COMPLEX_TYPE)
3428 && VEC_length (ce_s, rhsc) == 1)
3430 struct constraint_expr *origrhs;
3432 struct constraint_expr tmp;
3434 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3435 origrhs = VEC_last (ce_s, rhsc);
3437 VEC_pop (ce_s, rhsc);
3438 origvar = get_varinfo (origrhs->var);
3439 for (; origvar; origvar = origvar->next)
3441 tmp.var = origvar->id;
3442 VEC_safe_push (ce_s, heap, rhsc, &tmp);
3446 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3448 struct constraint_expr *c2;
3451 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3452 process_constraint (new_constraint (*c, *c2));
3460 /* For pointer arithmetic of the form
3461 PTR + CST, we can simply use PTR's
3462 constraint because pointer arithmetic is
3463 not allowed to go out of bounds. */
3464 if (handle_ptr_arith (lhsc, rhsop))
3469 /* Otherwise, walk each operand. Notice that we
3470 can't use the operand interface because we need
3471 to process expressions other than simple operands
3472 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3474 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
3476 tree op = TREE_OPERAND (rhsop, i);
3479 gcc_assert (VEC_length (ce_s, rhsc) == 0);
3480 get_constraint_for (op, &rhsc);
3481 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3483 struct constraint_expr *c2;
3484 while (VEC_length (ce_s, rhsc) > 0)
3486 c2 = VEC_last (ce_s, rhsc);
3487 process_constraint (new_constraint (*c, *c2));
3488 VEC_pop (ce_s, rhsc);
3497 /* After promoting variables and computing aliasing we will
3498 need to re-scan most statements. FIXME: Try to minimize the
3499 number of statements re-scanned. It's not really necessary to
3500 re-scan *all* statements. */
3501 mark_stmt_modified (origt);
3502 VEC_free (ce_s, heap, rhsc);
3503 VEC_free (ce_s, heap, lhsc);
3507 /* Find the first varinfo in the same variable as START that overlaps with
3509 Effectively, walk the chain of fields for the variable START to find the
3510 first field that overlaps with OFFSET.
3511 Return NULL if we can't find one. */
3514 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3516 varinfo_t curr = start;
3519 /* We may not find a variable in the field list with the actual
3520 offset when when we have glommed a structure to a variable.
3521 In that case, however, offset should still be within the size
3523 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3531 /* Insert the varinfo FIELD into the field list for BASE, at the front
3535 insert_into_field_list (varinfo_t base, varinfo_t field)
3537 varinfo_t prev = base;
3538 varinfo_t curr = base->next;
3544 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3548 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
3550 varinfo_t prev = base;
3551 varinfo_t curr = base->next;
3562 if (field->offset <= curr->offset)
3567 field->next = prev->next;
3572 /* qsort comparison function for two fieldoff's PA and PB */
3575 fieldoff_compare (const void *pa, const void *pb)
3577 const fieldoff_s *foa = (const fieldoff_s *)pa;
3578 const fieldoff_s *fob = (const fieldoff_s *)pb;
3579 HOST_WIDE_INT foasize, fobsize;
3581 if (foa->offset != fob->offset)
3582 return foa->offset - fob->offset;
3584 foasize = TREE_INT_CST_LOW (foa->size);
3585 fobsize = TREE_INT_CST_LOW (fob->size);
3586 return foasize - fobsize;
3589 /* Sort a fieldstack according to the field offset and sizes. */
3590 void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3592 qsort (VEC_address (fieldoff_s, fieldstack),
3593 VEC_length (fieldoff_s, fieldstack),
3594 sizeof (fieldoff_s),
3598 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3599 of TYPE onto fieldstack, recording their offsets along the way.
3600 OFFSET is used to keep track of the offset in this entire structure, rather
3601 than just the immediately containing structure. Returns the number
3603 HAS_UNION is set to true if we find a union type as a field of
3607 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
3608 HOST_WIDE_INT offset, bool *has_union)
3613 if (TREE_CODE (type) == COMPLEX_TYPE)
3615 fieldoff_s *real_part, *img_part;
3616 real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3617 real_part->type = TREE_TYPE (type);
3618 real_part->size = TYPE_SIZE (TREE_TYPE (type));
3619 real_part->offset = offset;
3620 real_part->decl = NULL_TREE;
3622 img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3623 img_part->type = TREE_TYPE (type);
3624 img_part->size = TYPE_SIZE (TREE_TYPE (type));
3625 img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
3626 img_part->decl = NULL_TREE;
3631 if (TREE_CODE (type) == ARRAY_TYPE)
3633 tree sz = TYPE_SIZE (type);
3634 tree elsz = TYPE_SIZE (TREE_TYPE (type));
3639 || ! host_integerp (sz, 1)
3640 || TREE_INT_CST_LOW (sz) == 0
3642 || ! host_integerp (elsz, 1)
3643 || TREE_INT_CST_LOW (elsz) == 0)
3646 nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
3647 if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
3650 for (i = 0; i < nr; ++i)
3656 && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
3657 || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
3660 if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
3662 else if (!(pushed = push_fields_onto_fieldstack
3663 (TREE_TYPE (type), fieldstack,
3664 offset + i * TREE_INT_CST_LOW (elsz), has_union)))
3665 /* Empty structures may have actual size, like in C++. So
3666 see if we didn't push any subfields and the size is
3667 nonzero, push the field onto the stack */
3674 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3675 pair->type = TREE_TYPE (type);
3677 pair->decl = NULL_TREE;
3678 pair->offset = offset + i * TREE_INT_CST_LOW (elsz);
3688 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
3689 if (TREE_CODE (field) == FIELD_DECL)
3695 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3696 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3699 if (!var_can_have_subvars (field))
3701 else if (!(pushed = push_fields_onto_fieldstack
3702 (TREE_TYPE (field), fieldstack,
3703 offset + bitpos_of_field (field), has_union))
3704 && DECL_SIZE (field)
3705 && !integer_zerop (DECL_SIZE (field)))
3706 /* Empty structures may have actual size, like in C++. So
3707 see if we didn't push any subfields and the size is
3708 nonzero, push the field onto the stack */
3715 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3716 pair->type = TREE_TYPE (field);
3717 pair->size = DECL_SIZE (field);
3719 pair->offset = offset + bitpos_of_field (field);
3730 make_constraint_to_anything (varinfo_t vi)
3732 struct constraint_expr lhs, rhs;
3738 rhs.var = anything_id;
3740 rhs.type = ADDRESSOF;
3741 process_constraint (new_constraint (lhs, rhs));
3744 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3745 if it is a varargs function. */
3748 count_num_arguments (tree decl, bool *is_varargs)
3753 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
3757 if (TREE_VALUE (t) == void_type_node)
3767 /* Creation function node for DECL, using NAME, and return the index
3768 of the variable we've created for the function. */
3771 create_function_info_for (tree decl, const char *name)
3773 unsigned int index = VEC_length (varinfo_t, varmap);
3777 bool is_varargs = false;
3779 /* Create the variable info. */
3781 vi = new_var_info (decl, index, name, index);
3786 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3787 insert_id_for_tree (vi->decl, index);
3788 VEC_safe_push (varinfo_t, heap, varmap, vi);
3792 /* If it's varargs, we don't know how many arguments it has, so we
3799 vi->is_unknown_size_var = true;
3804 arg = DECL_ARGUMENTS (decl);
3806 /* Set up variables for each argument. */
3807 for (i = 1; i < vi->fullsize; i++)
3810 const char *newname;
3812 unsigned int newindex;
3813 tree argdecl = decl;
3818 newindex = VEC_length (varinfo_t, varmap);
3819 asprintf (&tempname, "%s.arg%d", name, i-1);
3820 newname = ggc_strdup (tempname);
3823 argvi = new_var_info (argdecl, newindex,newname, newindex);
3824 argvi->decl = argdecl;
3825 VEC_safe_push (varinfo_t, heap, varmap, argvi);
3828 argvi->fullsize = vi->fullsize;
3829 argvi->has_union = false;
3830 insert_into_field_list_sorted (vi, argvi);
3831 stats.total_vars ++;
3834 insert_id_for_tree (arg, newindex);
3835 arg = TREE_CHAIN (arg);
3839 /* Create a variable for the return var. */
3840 if (DECL_RESULT (decl) != NULL
3841 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
3844 const char *newname;
3846 unsigned int newindex;
3847 tree resultdecl = decl;
3851 if (DECL_RESULT (decl))
3852 resultdecl = DECL_RESULT (decl);
3854 newindex = VEC_length (varinfo_t, varmap);
3855 asprintf (&tempname, "%s.result", name);
3856 newname = ggc_strdup (tempname);
3859 resultvi = new_var_info (resultdecl, newindex, newname, newindex);
3860 resultvi->decl = resultdecl;
3861 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
3862 resultvi->offset = i;
3864 resultvi->fullsize = vi->fullsize;
3865 resultvi->has_union = false;
3866 insert_into_field_list_sorted (vi, resultvi);
3867 stats.total_vars ++;
3868 if (DECL_RESULT (decl))
3869 insert_id_for_tree (DECL_RESULT (decl), newindex);
3875 /* Return true if FIELDSTACK contains fields that overlap.
3876 FIELDSTACK is assumed to be sorted by offset. */
3879 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
3881 fieldoff_s *fo = NULL;
3883 HOST_WIDE_INT lastoffset = -1;
3885 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3887 if (fo->offset == lastoffset)
3889 lastoffset = fo->offset;
3893 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3894 This will also create any varinfo structures necessary for fields
3898 create_variable_info_for (tree decl, const char *name)
3900 unsigned int index = VEC_length (varinfo_t, varmap);
3902 tree decltype = TREE_TYPE (decl);
3903 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
3904 bool notokay = false;
3906 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
3907 VEC (fieldoff_s,heap) *fieldstack = NULL;
3909 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
3910 return create_function_info_for (decl, name);
3912 hasunion = TREE_CODE (decltype) == UNION_TYPE
3913 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
3914 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
3916 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
3919 VEC_free (fieldoff_s, heap, fieldstack);
3925 /* If the variable doesn't have subvars, we may end up needing to
3926 sort the field list and create fake variables for all the
3928 vi = new_var_info (decl, index, name, index);
3931 vi->has_union = hasunion;
3933 || TREE_CODE (declsize) != INTEGER_CST
3934 || TREE_CODE (decltype) == UNION_TYPE
3935 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
3937 vi->is_unknown_size_var = true;
3943 vi->fullsize = TREE_INT_CST_LOW (declsize);
3944 vi->size = vi->fullsize;
3947 insert_id_for_tree (vi->decl, index);
3948 VEC_safe_push (varinfo_t, heap, varmap, vi);
3949 if (is_global && (!flag_whole_program || !in_ipa_mode))
3950 make_constraint_to_anything (vi);
3953 if (use_field_sensitive
3955 && !vi->is_unknown_size_var
3956 && var_can_have_subvars (decl)
3957 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
3959 unsigned int newindex = VEC_length (varinfo_t, varmap);
3960 fieldoff_s *fo = NULL;
3963 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3966 || TREE_CODE (fo->size) != INTEGER_CST
3974 /* We can't sort them if we have a field with a variable sized type,
3975 which will make notokay = true. In that case, we are going to return
3976 without creating varinfos for the fields anyway, so sorting them is a
3980 sort_fieldstack (fieldstack);
3981 /* Due to some C++ FE issues, like PR 22488, we might end up
3982 what appear to be overlapping fields even though they,
3983 in reality, do not overlap. Until the C++ FE is fixed,
3984 we will simply disable field-sensitivity for these cases. */
3985 notokay = check_for_overlaps (fieldstack);
3989 if (VEC_length (fieldoff_s, fieldstack) != 0)
3990 fo = VEC_index (fieldoff_s, fieldstack, 0);
3992 if (fo == NULL || notokay)
3994 vi->is_unknown_size_var = 1;
3997 VEC_free (fieldoff_s, heap, fieldstack);
4001 vi->size = TREE_INT_CST_LOW (fo->size);
4002 vi->offset = fo->offset;
4003 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4004 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4008 const char *newname;
4011 newindex = VEC_length (varinfo_t, varmap);
4013 asprintf (&tempname, "%s.%s", vi->name, alias_get_name (fo->decl));
4015 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC, vi->name, fo->offset);
4016 newname = ggc_strdup (tempname);
4018 newvi = new_var_info (decl, newindex, newname, newindex);
4019 newvi->offset = fo->offset;
4020 newvi->size = TREE_INT_CST_LOW (fo->size);
4021 newvi->fullsize = vi->fullsize;
4022 insert_into_field_list (vi, newvi);
4023 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4024 if (is_global && (!flag_whole_program || !in_ipa_mode))
4025 make_constraint_to_anything (newvi);
4029 VEC_free (fieldoff_s, heap, fieldstack);
4034 /* Print out the points-to solution for VAR to FILE. */
4037 dump_solution_for_var (FILE *file, unsigned int var)
4039 varinfo_t vi = get_varinfo (var);
4043 fprintf (file, "%s = { ", vi->name);
4044 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
4046 fprintf (file, "%s ", get_varinfo (i)->name);
4048 fprintf (file, "}\n");
4051 /* Print the points-to solution for VAR to stdout. */
4054 debug_solution_for_var (unsigned int var)
4056 dump_solution_for_var (stdout, var);
4060 /* Create varinfo structures for all of the variables in the
4061 function for intraprocedural mode. */
4064 intra_create_variable_infos (void)
4068 /* For each incoming argument arg, ARG = &ANYTHING or a dummy variable if
4069 flag_argument_noalias > 1. */
4070 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4072 struct constraint_expr lhs;
4077 lhs.var = create_variable_info_for (t, alias_get_name (t));
4079 /* With flag_argument_noalias greater than one means that the incomming
4080 argument cannot alias anything except for itself so create a HEAP
4082 if (POINTER_TYPE_P (TREE_TYPE (t))
4083 && flag_argument_noalias > 1)
4086 struct constraint_expr rhs;
4087 tree heapvar = heapvar_lookup (t);
4089 if (heapvar == NULL_TREE)
4091 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4093 DECL_EXTERNAL (heapvar) = 1;
4094 if (referenced_vars)
4095 add_referenced_tmp_var (heapvar);
4096 heapvar_insert (t, heapvar);
4098 id = create_variable_info_for (heapvar,
4099 alias_get_name (heapvar));
4100 vi = get_varinfo (id);
4101 vi->is_artificial_var = 1;
4102 vi->is_heap_var = 1;
4104 rhs.type = ADDRESSOF;
4106 for (p = get_varinfo (lhs.var); p; p = p->next)
4108 struct constraint_expr temp = lhs;
4110 process_constraint (new_constraint (temp, rhs));
4114 for (p = get_varinfo (lhs.var); p; p = p->next)
4115 make_constraint_to_anything (p);
4119 /* Set bits in INTO corresponding to the variable uids in solution set
4123 set_uids_in_ptset (bitmap into, bitmap from)
4129 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4131 varinfo_t vi = get_varinfo (i);
4133 /* The only artificial variables that are allowed in a may-alias
4134 set are heap variables. */
4135 if (vi->is_artificial_var && !vi->is_heap_var)
4138 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
4140 /* Variables containing unions may need to be converted to
4141 their SFT's, because SFT's can have unions and we cannot. */
4142 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
4143 bitmap_set_bit (into, DECL_UID (sv->var));
4145 else if (TREE_CODE (vi->decl) == VAR_DECL
4146 || TREE_CODE (vi->decl) == PARM_DECL)
4148 if (var_can_have_subvars (vi->decl)
4149 && get_subvars_for_var (vi->decl))
4151 /* If VI->DECL is an aggregate for which we created
4152 SFTs, add the SFT corresponding to VI->OFFSET. */
4153 tree sft = get_subvar_at (vi->decl, vi->offset);
4155 bitmap_set_bit (into, DECL_UID (sft));
4159 /* Otherwise, just add VI->DECL to the alias set. */
4160 bitmap_set_bit (into, DECL_UID (vi->decl));
4167 static bool have_alias_info = false;
4169 /* Given a pointer variable P, fill in its points-to set, or return
4170 false if we can't. */
4173 find_what_p_points_to (tree p)
4175 unsigned int id = 0;
4178 if (!have_alias_info)
4181 /* For parameters, get at the points-to set for the actual parm
4183 if (TREE_CODE (p) == SSA_NAME
4184 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4185 && default_def (SSA_NAME_VAR (p)) == p)
4186 lookup_p = SSA_NAME_VAR (p);
4188 if (lookup_id_for_tree (lookup_p, &id))
4190 varinfo_t vi = get_varinfo (id);
4192 if (vi->is_artificial_var)
4195 /* See if this is a field or a structure. */
4196 if (vi->size != vi->fullsize)
4198 /* Nothing currently asks about structure fields directly,
4199 but when they do, we need code here to hand back the
4201 if (!var_can_have_subvars (vi->decl)
4202 || get_subvars_for_var (vi->decl) == NULL)
4207 struct ptr_info_def *pi = get_ptr_info (p);
4211 /* This variable may have been collapsed, let's get the real
4213 vi = get_varinfo (vi->node);
4215 /* Translate artificial variables into SSA_NAME_PTR_INFO
4217 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4219 varinfo_t vi = get_varinfo (i);
4221 if (vi->is_artificial_var)
4223 /* FIXME. READONLY should be handled better so that
4224 flow insensitive aliasing can disregard writable
4226 if (vi->id == nothing_id)
4228 else if (vi->id == anything_id)
4229 pi->pt_anything = 1;
4230 else if (vi->id == readonly_id)
4231 pi->pt_anything = 1;
4232 else if (vi->id == integer_id)
4233 pi->pt_anything = 1;
4234 else if (vi->is_heap_var)
4235 pi->pt_global_mem = 1;
4239 if (pi->pt_anything)
4243 pi->pt_vars = BITMAP_GGC_ALLOC ();
4245 set_uids_in_ptset (pi->pt_vars, vi->solution);
4247 if (bitmap_empty_p (pi->pt_vars))
4259 /* Dump points-to information to OUTFILE. */
4262 dump_sa_points_to_info (FILE *outfile)
4266 fprintf (outfile, "\nPoints-to sets\n\n");
4268 if (dump_flags & TDF_STATS)
4270 fprintf (outfile, "Stats:\n");
4271 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4272 fprintf (outfile, "Statically unified vars: %d\n",
4273 stats.unified_vars_static);
4274 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
4275 fprintf (outfile, "Dynamically unified vars: %d\n",
4276 stats.unified_vars_dynamic);
4277 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4278 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4281 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4282 dump_solution_for_var (outfile, i);
4286 /* Debug points-to information to stderr. */
4289 debug_sa_points_to_info (void)
4291 dump_sa_points_to_info (stderr);
4295 /* Initialize the always-existing constraint variables for NULL
4296 ANYTHING, READONLY, and INTEGER */
4299 init_base_vars (void)
4301 struct constraint_expr lhs, rhs;
4303 /* Create the NULL variable, used to represent that a variable points
4305 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4306 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
4307 insert_id_for_tree (nothing_tree, 0);
4308 var_nothing->is_artificial_var = 1;
4309 var_nothing->offset = 0;
4310 var_nothing->size = ~0;
4311 var_nothing->fullsize = ~0;
4312 var_nothing->is_special_var = 1;
4314 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
4316 /* Create the ANYTHING variable, used to represent that a variable
4317 points to some unknown piece of memory. */
4318 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4319 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
4320 insert_id_for_tree (anything_tree, 1);
4321 var_anything->is_artificial_var = 1;
4322 var_anything->size = ~0;
4323 var_anything->offset = 0;
4324 var_anything->next = NULL;
4325 var_anything->fullsize = ~0;
4326 var_anything->is_special_var = 1;
4329 /* Anything points to anything. This makes deref constraints just
4330 work in the presence of linked list and other p = *p type loops,
4331 by saying that *ANYTHING = ANYTHING. */
4332 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
4334 lhs.var = anything_id;
4336 rhs.type = ADDRESSOF;
4337 rhs.var = anything_id;
4339 var_anything->address_taken = true;
4341 /* This specifically does not use process_constraint because
4342 process_constraint ignores all anything = anything constraints, since all
4343 but this one are redundant. */
4344 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
4346 /* Create the READONLY variable, used to represent that a variable
4347 points to readonly memory. */
4348 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4349 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
4350 var_readonly->is_artificial_var = 1;
4351 var_readonly->offset = 0;
4352 var_readonly->size = ~0;
4353 var_readonly->fullsize = ~0;
4354 var_readonly->next = NULL;
4355 var_readonly->is_special_var = 1;
4356 insert_id_for_tree (readonly_tree, 2);
4358 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4360 /* readonly memory points to anything, in order to make deref
4361 easier. In reality, it points to anything the particular
4362 readonly variable can point to, but we don't track this
4365 lhs.var = readonly_id;
4367 rhs.type = ADDRESSOF;
4368 rhs.var = anything_id;
4371 process_constraint (new_constraint (lhs, rhs));
4373 /* Create the INTEGER variable, used to represent that a variable points
4375 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4376 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
4377 insert_id_for_tree (integer_tree, 3);
4378 var_integer->is_artificial_var = 1;
4379 var_integer->size = ~0;
4380 var_integer->fullsize = ~0;
4381 var_integer->offset = 0;
4382 var_integer->next = NULL;
4383 var_integer->is_special_var = 1;
4385 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
4387 /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
4388 integer will point to. */
4390 lhs.var = integer_id;
4392 rhs.type = ADDRESSOF;
4393 rhs.var = anything_id;
4395 process_constraint (new_constraint (lhs, rhs));
4398 /* Return true if we actually need to solve the constraint graph in order to
4399 get our points-to sets. This is false when, for example, no addresses are
4400 taken other than special vars, or all points-to sets with members already
4401 contain the anything variable and there are no predecessors for other
4405 need_to_solve (void)
4409 bool found_address_taken = false;
4410 bool found_non_anything = false;
4412 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4414 if (v->is_special_var)
4417 if (v->address_taken)
4418 found_address_taken = true;
4421 && !bitmap_empty_p (v->solution)
4422 && !bitmap_bit_p (v->solution, anything_id))
4423 found_non_anything = true;
4424 else if (bitmap_empty_p (v->solution)
4425 && (VEC_length (constraint_edge_t, graph->preds[v->id]) != 0
4426 || (graph->zero_weight_preds[v->id] && !bitmap_empty_p (graph->zero_weight_preds[v->id]))))
4427 found_non_anything = true;
4429 if (found_address_taken && found_non_anything)
4436 /* Initialize things necessary to perform PTA */
4439 init_alias_vars (void)
4441 bitmap_obstack_initialize (&ptabitmap_obstack);
4442 bitmap_obstack_initialize (&predbitmap_obstack);
4444 constraint_pool = create_alloc_pool ("Constraint pool",
4445 sizeof (struct constraint), 30);
4446 variable_info_pool = create_alloc_pool ("Variable info pool",
4447 sizeof (struct variable_info), 30);
4448 constraint_edge_pool = create_alloc_pool ("Constraint edges",
4449 sizeof (struct constraint_edge), 30);
4451 constraints = VEC_alloc (constraint_t, heap, 8);
4452 varmap = VEC_alloc (varinfo_t, heap, 8);
4453 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
4454 memset (&stats, 0, sizeof (stats));
4460 /* Create points-to sets for the current function. See the comments
4461 at the start of the file for an algorithmic overview. */
4464 compute_points_to_sets (struct alias_info *ai)
4468 timevar_push (TV_TREE_PTA);
4472 intra_create_variable_infos ();
4474 /* Now walk all statements and derive aliases. */
4477 block_stmt_iterator bsi;
4480 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4482 if (is_gimple_reg (PHI_RESULT (phi)))
4484 find_func_aliases (phi);
4485 /* Update various related attributes like escaped
4486 addresses, pointer dereferences for loads and stores.
4487 This is used when creating name tags and alias
4489 update_alias_info (phi, ai);
4493 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4495 tree stmt = bsi_stmt (bsi);
4496 find_func_aliases (stmt);
4497 /* Update various related attributes like escaped
4498 addresses, pointer dereferences for loads and stores.
4499 This is used when creating name tags and alias
4501 update_alias_info (stmt, ai);
4505 build_constraint_graph ();
4509 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4510 dump_constraints (dump_file);
4513 if (need_to_solve ())
4517 "\nCollapsing static cycles and doing variable "
4520 find_and_collapse_graph_cycles (graph, false);
4521 perform_var_substitution (graph);
4524 fprintf (dump_file, "\nSolving graph:\n");
4526 solve_graph (graph);
4530 dump_sa_points_to_info (dump_file);
4532 have_alias_info = true;
4534 timevar_pop (TV_TREE_PTA);
4538 /* Delete created points-to sets. */
4541 delete_points_to_sets (void)
4546 htab_delete (id_for_tree);
4547 bitmap_obstack_release (&ptabitmap_obstack);
4548 bitmap_obstack_release (&predbitmap_obstack);
4549 VEC_free (constraint_t, heap, constraints);
4551 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4553 VEC_free (constraint_edge_t, heap, graph->succs[i]);
4554 VEC_free (constraint_edge_t, heap, graph->preds[i]);
4555 VEC_free (constraint_t, heap, v->complex);
4557 free (graph->zero_weight_preds);
4558 free (graph->zero_weight_succs);
4559 free (graph->succs);
4560 free (graph->preds);
4563 VEC_free (varinfo_t, heap, varmap);
4564 free_alloc_pool (variable_info_pool);
4565 free_alloc_pool (constraint_pool);
4566 free_alloc_pool (constraint_edge_pool);
4568 have_alias_info = false;
4571 /* Return true if we should execute IPA PTA. */
4575 return (flag_unit_at_a_time != 0
4577 /* Don't bother doing anything if the program has errors. */
4578 && !(errorcount || sorrycount));
4581 /* Execute the driver for IPA PTA. */
4583 ipa_pta_execute (void)
4585 struct cgraph_node *node;
4587 init_alias_heapvars ();
4590 for (node = cgraph_nodes; node; node = node->next)
4592 if (!node->analyzed || cgraph_is_master_clone (node))
4596 varid = create_function_info_for (node->decl,
4597 cgraph_node_name (node));
4598 if (node->local.externally_visible)
4600 varinfo_t fi = get_varinfo (varid);
4601 for (; fi; fi = fi->next)
4602 make_constraint_to_anything (fi);
4606 for (node = cgraph_nodes; node; node = node->next)
4608 if (node->analyzed && cgraph_is_master_clone (node))
4610 struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
4612 tree old_func_decl = current_function_decl;
4615 "Generating constraints for %s\n",
4616 cgraph_node_name (node));
4618 current_function_decl = node->decl;
4620 FOR_EACH_BB_FN (bb, cfun)
4622 block_stmt_iterator bsi;
4625 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4627 if (is_gimple_reg (PHI_RESULT (phi)))
4629 find_func_aliases (phi);
4633 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4635 tree stmt = bsi_stmt (bsi);
4636 find_func_aliases (stmt);
4639 current_function_decl = old_func_decl;
4644 /* Make point to anything. */
4648 build_constraint_graph ();
4652 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4653 dump_constraints (dump_file);
4656 if (need_to_solve ())
4660 "\nCollapsing static cycles and doing variable "
4663 find_and_collapse_graph_cycles (graph, false);
4664 perform_var_substitution (graph);
4667 fprintf (dump_file, "\nSolving graph:\n");
4669 solve_graph (graph);
4673 dump_sa_points_to_info (dump_file);
4675 delete_alias_heapvars ();
4676 delete_points_to_sets ();
4679 struct tree_opt_pass pass_ipa_pta =
4682 gate_ipa_pta, /* gate */
4683 ipa_pta_execute, /* execute */
4686 0, /* static_pass_number */
4687 TV_IPA_PTA, /* tv_id */
4688 0, /* properties_required */
4689 0, /* properties_provided */
4690 0, /* properties_destroyed */
4691 0, /* todo_flags_start */
4692 0, /* todo_flags_finish */
4696 /* Initialize the heapvar for statement mapping. */
4698 init_alias_heapvars (void)
4700 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq, NULL);
4704 delete_alias_heapvars (void)
4706 htab_delete (heapvar_for_stmt);
4710 #include "gt-tree-ssa-structalias.h"