1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006, 2007 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 #include "pointer-set.h"
57 /* The idea behind this analyzer is to generate set constraints from the
58 program, then solve the resulting constraints in order to generate the
61 Set constraints are a way of modeling program analysis problems that
62 involve sets. They consist of an inclusion constraint language,
63 describing the variables (each variable is a set) and operations that
64 are involved on the variables, and a set of rules that derive facts
65 from these operations. To solve a system of set constraints, you derive
66 all possible facts under the rules, which gives you the correct sets
69 See "Efficient Field-sensitive pointer analysis for C" by "David
70 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
71 http://citeseer.ist.psu.edu/pearce04efficient.html
73 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
74 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
75 http://citeseer.ist.psu.edu/heintze01ultrafast.html
77 There are three types of real constraint expressions, DEREF,
78 ADDRESSOF, and SCALAR. Each constraint expression consists
79 of a constraint type, a variable, and an offset.
81 SCALAR is a constraint expression type used to represent x, whether
82 it appears on the LHS or the RHS of a statement.
83 DEREF is a constraint expression type used to represent *x, whether
84 it appears on the LHS or the RHS of a statement.
85 ADDRESSOF is a constraint expression used to represent &x, whether
86 it appears on the LHS or the RHS of a statement.
88 Each pointer variable in the program is assigned an integer id, and
89 each field of a structure variable is assigned an integer id as well.
91 Structure variables are linked to their list of fields through a "next
92 field" in each variable that points to the next field in offset
94 Each variable for a structure field has
96 1. "size", that tells the size in bits of that field.
97 2. "fullsize, that tells the size in bits of the entire structure.
98 3. "offset", that tells the offset in bits from the beginning of the
99 structure to this field.
111 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
112 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
113 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
116 In order to solve the system of set constraints, the following is
119 1. Each constraint variable x has a solution set associated with it,
122 2. Constraints are separated into direct, copy, and complex.
123 Direct constraints are ADDRESSOF constraints that require no extra
124 processing, such as P = &Q
125 Copy constraints are those of the form P = Q.
126 Complex constraints are all the constraints involving dereferences
127 and offsets (including offsetted copies).
129 3. All direct constraints of the form P = &Q are processed, such
130 that Q is added to Sol(P)
132 4. All complex constraints for a given constraint variable are stored in a
133 linked list attached to that variable's node.
135 5. A directed graph is built out of the copy constraints. Each
136 constraint variable is a node in the graph, and an edge from
137 Q to P is added for each copy constraint of the form P = Q
139 6. The graph is then walked, and solution sets are
140 propagated along the copy edges, such that an edge from Q to P
141 causes Sol(P) <- Sol(P) union Sol(Q).
143 7. As we visit each node, all complex constraints associated with
144 that node are processed by adding appropriate copy edges to the graph, or the
145 appropriate variables to the solution set.
147 8. The process of walking the graph is iterated until no solution
150 Prior to walking the graph in steps 6 and 7, We perform static
151 cycle elimination on the constraint graph, as well
152 as off-line variable substitution.
154 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
155 on and turned into anything), but isn't. You can just see what offset
156 inside the pointed-to struct it's going to access.
158 TODO: Constant bounded arrays can be handled as if they were structs of the
159 same number of elements.
161 TODO: Modeling heap and incoming pointers becomes much better if we
162 add fields to them as we discover them, which we could do.
164 TODO: We could handle unions, but to be honest, it's probably not
165 worth the pain or slowdown. */
167 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
168 htab_t heapvar_for_stmt;
170 static bool use_field_sensitive = true;
171 static int in_ipa_mode = 0;
173 /* Used for predecessor bitmaps. */
174 static bitmap_obstack predbitmap_obstack;
176 /* Used for points-to sets. */
177 static bitmap_obstack pta_obstack;
179 /* Used for oldsolution members of variables. */
180 static bitmap_obstack oldpta_obstack;
182 /* Used for per-solver-iteration bitmaps. */
183 static bitmap_obstack iteration_obstack;
185 static unsigned int create_variable_info_for (tree, const char *);
186 typedef struct constraint_graph *constraint_graph_t;
187 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
189 DEF_VEC_P(constraint_t);
190 DEF_VEC_ALLOC_P(constraint_t,heap);
192 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
194 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
196 static struct constraint_stats
198 unsigned int total_vars;
199 unsigned int nonpointer_vars;
200 unsigned int unified_vars_static;
201 unsigned int unified_vars_dynamic;
202 unsigned int iterations;
203 unsigned int num_edges;
204 unsigned int num_implicit_edges;
205 unsigned int points_to_sets_created;
210 /* ID of this variable */
213 /* Name of this variable */
216 /* Tree that this variable is associated with. */
219 /* Offset of this variable, in bits, from the base variable */
220 unsigned HOST_WIDE_INT offset;
222 /* Size of the variable, in bits. */
223 unsigned HOST_WIDE_INT size;
225 /* Full size of the base variable, in bits. */
226 unsigned HOST_WIDE_INT fullsize;
228 /* A link to the variable for the next field in this structure. */
229 struct variable_info *next;
231 /* True if the variable is directly the target of a dereference.
232 This is used to track which variables are *actually* dereferenced
233 so we can prune their points to listed. */
234 unsigned int directly_dereferenced:1;
236 /* True if this is a variable created by the constraint analysis, such as
237 heap variables and constraints we had to break up. */
238 unsigned int is_artificial_var:1;
240 /* True if this is a special variable whose solution set should not be
242 unsigned int is_special_var:1;
244 /* True for variables whose size is not known or variable. */
245 unsigned int is_unknown_size_var:1;
247 /* True for variables that have unions somewhere in them. */
248 unsigned int has_union:1;
250 /* True if this is a heap variable. */
251 unsigned int is_heap_var:1;
253 /* Points-to set for this variable. */
256 /* Old points-to set for this variable. */
259 /* Finished points-to set for this variable (IE what is returned
260 from find_what_p_points_to. */
261 bitmap finished_solution;
263 /* Variable ids represented by this node. */
266 /* Variable id this was collapsed to due to type unsafety. This
267 should be unused completely after build_succ_graph, or something
269 struct variable_info *collapsed_to;
271 typedef struct variable_info *varinfo_t;
273 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
275 /* Pool of variable info structures. */
276 static alloc_pool variable_info_pool;
278 DEF_VEC_P(varinfo_t);
280 DEF_VEC_ALLOC_P(varinfo_t, heap);
282 /* Table of variable info structures for constraint variables.
283 Indexed directly by variable info id. */
284 static VEC(varinfo_t,heap) *varmap;
286 /* Return the varmap element N */
288 static inline varinfo_t
289 get_varinfo (unsigned int n)
291 return VEC_index (varinfo_t, varmap, n);
294 /* Return the varmap element N, following the collapsed_to link. */
296 static inline varinfo_t
297 get_varinfo_fc (unsigned int n)
299 varinfo_t v = VEC_index (varinfo_t, varmap, n);
302 return v->collapsed_to;
306 /* Variable that represents the unknown pointer. */
307 static varinfo_t var_anything;
308 static tree anything_tree;
309 static unsigned int anything_id;
311 /* Variable that represents the NULL pointer. */
312 static varinfo_t var_nothing;
313 static tree nothing_tree;
314 static unsigned int nothing_id;
316 /* Variable that represents read only memory. */
317 static varinfo_t var_readonly;
318 static tree readonly_tree;
319 static unsigned int readonly_id;
321 /* Variable that represents integers. This is used for when people do things
323 static varinfo_t var_integer;
324 static tree integer_tree;
325 static unsigned int integer_id;
327 /* Lookup a heap var for FROM, and return it if we find one. */
330 heapvar_lookup (tree from)
332 struct tree_map *h, in;
335 h = htab_find_with_hash (heapvar_for_stmt, &in, htab_hash_pointer (from));
341 /* Insert a mapping FROM->TO in the heap var for statement
345 heapvar_insert (tree from, tree to)
350 h = ggc_alloc (sizeof (struct tree_map));
351 h->hash = htab_hash_pointer (from);
354 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
355 *(struct tree_map **) loc = h;
358 /* Return a new variable info structure consisting for a variable
359 named NAME, and using constraint graph node NODE. */
362 new_var_info (tree t, unsigned int id, const char *name)
364 varinfo_t ret = pool_alloc (variable_info_pool);
369 ret->directly_dereferenced = false;
370 ret->is_artificial_var = false;
371 ret->is_heap_var = false;
372 ret->is_special_var = false;
373 ret->is_unknown_size_var = false;
374 ret->has_union = false;
375 ret->solution = BITMAP_ALLOC (&pta_obstack);
376 ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
377 ret->finished_solution = NULL;
379 ret->collapsed_to = NULL;
383 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
385 /* An expression that appears in a constraint. */
387 struct constraint_expr
389 /* Constraint type. */
390 constraint_expr_type type;
392 /* Variable we are referring to in the constraint. */
395 /* Offset, in bits, of this constraint from the beginning of
396 variables it ends up referring to.
398 IOW, in a deref constraint, we would deref, get the result set,
399 then add OFFSET to each member. */
400 unsigned HOST_WIDE_INT offset;
403 typedef struct constraint_expr ce_s;
405 DEF_VEC_ALLOC_O(ce_s, heap);
406 static void get_constraint_for (tree, VEC(ce_s, heap) **);
407 static void do_deref (VEC (ce_s, heap) **);
409 /* Our set constraints are made up of two constraint expressions, one
412 As described in the introduction, our set constraints each represent an
413 operation between set valued variables.
417 struct constraint_expr lhs;
418 struct constraint_expr rhs;
421 /* List of constraints that we use to build the constraint graph from. */
423 static VEC(constraint_t,heap) *constraints;
424 static alloc_pool constraint_pool;
428 DEF_VEC_ALLOC_I(int, heap);
430 /* The constraint graph is represented as an array of bitmaps
431 containing successor nodes. */
433 struct constraint_graph
435 /* Size of this graph, which may be different than the number of
436 nodes in the variable map. */
439 /* Explicit successors of each node. */
442 /* Implicit predecessors of each node (Used for variable
444 bitmap *implicit_preds;
446 /* Explicit predecessors of each node (Used for variable substitution). */
449 /* Indirect cycle representatives, or -1 if the node has no indirect
451 int *indirect_cycles;
453 /* Representative node for a node. rep[a] == a unless the node has
457 /* Equivalence class representative for a node. This is used for
458 variable substitution. */
461 /* Label for each node, used during variable substitution. */
464 /* Bitmap of nodes where the bit is set if the node is a direct
465 node. Used for variable substitution. */
466 sbitmap direct_nodes;
468 /* Vector of complex constraints for each graph node. Complex
469 constraints are those involving dereferences or offsets that are
471 VEC(constraint_t,heap) **complex;
474 static constraint_graph_t graph;
476 /* During variable substitution and the offline version of indirect
477 cycle finding, we create nodes to represent dereferences and
478 address taken constraints. These represent where these start and
480 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
481 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
482 #define FIRST_ADDR_NODE (LAST_REF_NODE + 1)
484 /* Return the representative node for NODE, if NODE has been unioned
486 This function performs path compression along the way to finding
487 the representative. */
490 find (unsigned int node)
492 gcc_assert (node < graph->size);
493 if (graph->rep[node] != node)
494 return graph->rep[node] = find (graph->rep[node]);
498 /* Union the TO and FROM nodes to the TO nodes.
499 Note that at some point in the future, we may want to do
500 union-by-rank, in which case we are going to have to return the
501 node we unified to. */
504 unite (unsigned int to, unsigned int from)
506 gcc_assert (to < graph->size && from < graph->size);
507 if (to != from && graph->rep[from] != to)
509 graph->rep[from] = to;
515 /* Create a new constraint consisting of LHS and RHS expressions. */
518 new_constraint (const struct constraint_expr lhs,
519 const struct constraint_expr rhs)
521 constraint_t ret = pool_alloc (constraint_pool);
527 /* Print out constraint C to FILE. */
530 dump_constraint (FILE *file, constraint_t c)
532 if (c->lhs.type == ADDRESSOF)
534 else if (c->lhs.type == DEREF)
536 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
537 if (c->lhs.offset != 0)
538 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
539 fprintf (file, " = ");
540 if (c->rhs.type == ADDRESSOF)
542 else if (c->rhs.type == DEREF)
544 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
545 if (c->rhs.offset != 0)
546 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
547 fprintf (file, "\n");
550 /* Print out constraint C to stderr. */
553 debug_constraint (constraint_t c)
555 dump_constraint (stderr, c);
558 /* Print out all constraints to FILE */
561 dump_constraints (FILE *file)
565 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
566 dump_constraint (file, c);
569 /* Print out all constraints to stderr. */
572 debug_constraints (void)
574 dump_constraints (stderr);
579 The solver is a simple worklist solver, that works on the following
582 sbitmap changed_nodes = all zeroes;
584 For each node that is not already collapsed:
586 set bit in changed nodes
588 while (changed_count > 0)
590 compute topological ordering for constraint graph
592 find and collapse cycles in the constraint graph (updating
593 changed if necessary)
595 for each node (n) in the graph in topological order:
598 Process each complex constraint associated with the node,
599 updating changed if necessary.
601 For each outgoing edge from n, propagate the solution from n to
602 the destination of the edge, updating changed as necessary.
606 /* Return true if two constraint expressions A and B are equal. */
609 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
611 return a.type == b.type && a.var == b.var && a.offset == b.offset;
614 /* Return true if constraint expression A is less than constraint expression
615 B. This is just arbitrary, but consistent, in order to give them an
619 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
621 if (a.type == b.type)
624 return a.offset < b.offset;
626 return a.var < b.var;
629 return a.type < b.type;
632 /* Return true if constraint A is less than constraint B. This is just
633 arbitrary, but consistent, in order to give them an ordering. */
636 constraint_less (const constraint_t a, const constraint_t b)
638 if (constraint_expr_less (a->lhs, b->lhs))
640 else if (constraint_expr_less (b->lhs, a->lhs))
643 return constraint_expr_less (a->rhs, b->rhs);
646 /* Return true if two constraints A and B are equal. */
649 constraint_equal (struct constraint a, struct constraint b)
651 return constraint_expr_equal (a.lhs, b.lhs)
652 && constraint_expr_equal (a.rhs, b.rhs);
656 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
659 constraint_vec_find (VEC(constraint_t,heap) *vec,
660 struct constraint lookfor)
668 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
669 if (place >= VEC_length (constraint_t, vec))
671 found = VEC_index (constraint_t, vec, place);
672 if (!constraint_equal (*found, lookfor))
677 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
680 constraint_set_union (VEC(constraint_t,heap) **to,
681 VEC(constraint_t,heap) **from)
686 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
688 if (constraint_vec_find (*to, *c) == NULL)
690 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
692 VEC_safe_insert (constraint_t, heap, *to, place, c);
697 /* Take a solution set SET, add OFFSET to each member of the set, and
698 overwrite SET with the result when done. */
701 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
703 bitmap result = BITMAP_ALLOC (&iteration_obstack);
707 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
709 /* If this is a properly sized variable, only add offset if it's
710 less than end. Otherwise, it is globbed to a single
713 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
715 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
716 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
719 bitmap_set_bit (result, v->id);
721 else if (get_varinfo (i)->is_artificial_var
722 || get_varinfo (i)->has_union
723 || get_varinfo (i)->is_unknown_size_var)
725 bitmap_set_bit (result, i);
729 bitmap_copy (set, result);
730 BITMAP_FREE (result);
733 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
737 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
740 return bitmap_ior_into (to, from);
746 tmp = BITMAP_ALLOC (&iteration_obstack);
747 bitmap_copy (tmp, from);
748 solution_set_add (tmp, inc);
749 res = bitmap_ior_into (to, tmp);
755 /* Insert constraint C into the list of complex constraints for graph
759 insert_into_complex (constraint_graph_t graph,
760 unsigned int var, constraint_t c)
762 VEC (constraint_t, heap) *complex = graph->complex[var];
763 unsigned int place = VEC_lower_bound (constraint_t, complex, c,
766 /* Only insert constraints that do not already exist. */
767 if (place >= VEC_length (constraint_t, complex)
768 || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
769 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
773 /* Condense two variable nodes into a single variable node, by moving
774 all associated info from SRC to TO. */
777 merge_node_constraints (constraint_graph_t graph, unsigned int to,
783 gcc_assert (find (from) == to);
785 /* Move all complex constraints from src node into to node */
786 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
788 /* In complex constraints for node src, we may have either
789 a = *src, and *src = a, or an offseted constraint which are
790 always added to the rhs node's constraints. */
792 if (c->rhs.type == DEREF)
794 else if (c->lhs.type == DEREF)
799 constraint_set_union (&graph->complex[to], &graph->complex[from]);
800 VEC_free (constraint_t, heap, graph->complex[from]);
801 graph->complex[from] = NULL;
805 /* Remove edges involving NODE from GRAPH. */
808 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
810 if (graph->succs[node])
811 BITMAP_FREE (graph->succs[node]);
814 /* Merge GRAPH nodes FROM and TO into node TO. */
817 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
820 if (graph->indirect_cycles[from] != -1)
822 /* If we have indirect cycles with the from node, and we have
823 none on the to node, the to node has indirect cycles from the
824 from node now that they are unified.
825 If indirect cycles exist on both, unify the nodes that they
826 are in a cycle with, since we know they are in a cycle with
828 if (graph->indirect_cycles[to] == -1)
830 graph->indirect_cycles[to] = graph->indirect_cycles[from];
834 unsigned int tonode = find (graph->indirect_cycles[to]);
835 unsigned int fromnode = find (graph->indirect_cycles[from]);
837 if (unite (tonode, fromnode))
838 unify_nodes (graph, tonode, fromnode, true);
842 /* Merge all the successor edges. */
843 if (graph->succs[from])
845 if (!graph->succs[to])
846 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
847 bitmap_ior_into (graph->succs[to],
851 clear_edges_for_node (graph, from);
855 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
856 it doesn't exist in the graph already. */
859 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
865 if (!graph->implicit_preds[to])
866 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
868 if (!bitmap_bit_p (graph->implicit_preds[to], from))
870 stats.num_implicit_edges++;
871 bitmap_set_bit (graph->implicit_preds[to], from);
875 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
876 it doesn't exist in the graph already.
877 Return false if the edge already existed, true otherwise. */
880 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
883 if (!graph->preds[to])
884 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
885 if (!bitmap_bit_p (graph->preds[to], from))
886 bitmap_set_bit (graph->preds[to], from);
889 /* Add a graph edge to GRAPH, going from FROM to TO if
890 it doesn't exist in the graph already.
891 Return false if the edge already existed, true otherwise. */
894 add_graph_edge (constraint_graph_t graph, unsigned int to,
905 if (!graph->succs[from])
906 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
907 if (!bitmap_bit_p (graph->succs[from], to))
910 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
912 bitmap_set_bit (graph->succs[from], to);
919 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
922 valid_graph_edge (constraint_graph_t graph, unsigned int src,
925 return (graph->succs[dest]
926 && bitmap_bit_p (graph->succs[dest], src));
929 /* Build the constraint graph, adding only predecessor edges right now. */
932 build_pred_graph (void)
938 graph = XNEW (struct constraint_graph);
939 graph->size = (VEC_length (varinfo_t, varmap)) * 3;
940 graph->succs = XCNEWVEC (bitmap, graph->size);
941 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
942 graph->preds = XCNEWVEC (bitmap, graph->size);
943 graph->indirect_cycles = XNEWVEC (int, VEC_length (varinfo_t, varmap));
944 graph->label = XCNEWVEC (unsigned int, graph->size);
945 graph->rep = XNEWVEC (unsigned int, graph->size);
946 graph->eq_rep = XNEWVEC (int, graph->size);
947 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *,
948 VEC_length (varinfo_t, varmap));
949 graph->direct_nodes = sbitmap_alloc (graph->size);
950 sbitmap_zero (graph->direct_nodes);
952 for (j = 0; j < FIRST_REF_NODE; j++)
954 if (!get_varinfo (j)->is_special_var)
955 SET_BIT (graph->direct_nodes, j);
958 for (j = 0; j < graph->size; j++)
961 graph->eq_rep[j] = -1;
964 for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
965 graph->indirect_cycles[j] = -1;
967 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
969 struct constraint_expr lhs = c->lhs;
970 struct constraint_expr rhs = c->rhs;
971 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
972 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
974 if (lhs.type == DEREF)
977 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
978 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
979 if (rhs.type == ADDRESSOF)
980 RESET_BIT (graph->direct_nodes, rhsvar);
982 else if (rhs.type == DEREF)
985 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
986 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
988 RESET_BIT (graph->direct_nodes, lhsvar);
990 else if (rhs.type == ADDRESSOF)
993 add_pred_graph_edge (graph, lhsvar, FIRST_ADDR_NODE + rhsvar);
994 /* Implicitly, *x = y */
995 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
997 RESET_BIT (graph->direct_nodes, rhsvar);
999 else if (lhsvar > anything_id
1000 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1003 add_pred_graph_edge (graph, lhsvar, rhsvar);
1004 /* Implicitly, *x = *y */
1005 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1006 FIRST_REF_NODE + rhsvar);
1008 else if (lhs.offset != 0 || rhs.offset != 0)
1010 if (rhs.offset != 0)
1011 RESET_BIT (graph->direct_nodes, lhs.var);
1012 if (lhs.offset != 0)
1013 RESET_BIT (graph->direct_nodes, rhs.var);
1018 /* Build the constraint graph, adding successor edges. */
1021 build_succ_graph (void)
1026 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1028 struct constraint_expr lhs;
1029 struct constraint_expr rhs;
1030 unsigned int lhsvar;
1031 unsigned int rhsvar;
1038 lhsvar = find (get_varinfo_fc (lhs.var)->id);
1039 rhsvar = find (get_varinfo_fc (rhs.var)->id);
1041 if (lhs.type == DEREF)
1043 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1044 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1046 else if (rhs.type == DEREF)
1048 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1049 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1051 else if (rhs.type == ADDRESSOF)
1054 gcc_assert (find (get_varinfo_fc (rhs.var)->id)
1055 == get_varinfo_fc (rhs.var)->id);
1056 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1058 else if (lhsvar > anything_id
1059 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1061 add_graph_edge (graph, lhsvar, rhsvar);
1067 /* Changed variables on the last iteration. */
1068 static unsigned int changed_count;
1069 static sbitmap changed;
1071 DEF_VEC_I(unsigned);
1072 DEF_VEC_ALLOC_I(unsigned,heap);
1075 /* Strongly Connected Component visitation info. */
1082 unsigned int *node_mapping;
1084 VEC(unsigned,heap) *scc_stack;
1088 /* Recursive routine to find strongly connected components in GRAPH.
1089 SI is the SCC info to store the information in, and N is the id of current
1090 graph node we are processing.
1092 This is Tarjan's strongly connected component finding algorithm, as
1093 modified by Nuutila to keep only non-root nodes on the stack.
1094 The algorithm can be found in "On finding the strongly connected
1095 connected components in a directed graph" by Esko Nuutila and Eljas
1096 Soisalon-Soininen, in Information Processing Letters volume 49,
1097 number 1, pages 9-14. */
1100 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1104 unsigned int my_dfs;
1106 SET_BIT (si->visited, n);
1107 si->dfs[n] = si->current_index ++;
1108 my_dfs = si->dfs[n];
1110 /* Visit all the successors. */
1111 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1115 if (i > LAST_REF_NODE)
1119 if (TEST_BIT (si->roots, w))
1122 if (!TEST_BIT (si->visited, w))
1123 scc_visit (graph, si, w);
1125 unsigned int t = find (w);
1126 unsigned int nnode = find (n);
1127 gcc_assert (nnode == n);
1129 if (si->dfs[t] < si->dfs[nnode])
1130 si->dfs[n] = si->dfs[t];
1134 /* See if any components have been identified. */
1135 if (si->dfs[n] == my_dfs)
1137 if (VEC_length (unsigned, si->scc_stack) > 0
1138 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1140 bitmap scc = BITMAP_ALLOC (NULL);
1141 bool have_ref_node = n >= FIRST_REF_NODE;
1142 unsigned int lowest_node;
1145 bitmap_set_bit (scc, n);
1147 while (VEC_length (unsigned, si->scc_stack) != 0
1148 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1150 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1152 bitmap_set_bit (scc, w);
1153 if (w >= FIRST_REF_NODE)
1154 have_ref_node = true;
1157 lowest_node = bitmap_first_set_bit (scc);
1158 gcc_assert (lowest_node < FIRST_REF_NODE);
1159 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1161 if (i < FIRST_REF_NODE)
1163 /* Mark this node for collapsing. */
1164 if (unite (lowest_node, i))
1165 unify_nodes (graph, lowest_node, i, false);
1169 unite (lowest_node, i);
1170 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1174 SET_BIT (si->roots, n);
1177 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1180 /* Unify node FROM into node TO, updating the changed count if
1181 necessary when UPDATE_CHANGED is true. */
1184 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1185 bool update_changed)
1188 gcc_assert (to != from && find (to) == to);
1189 if (dump_file && (dump_flags & TDF_DETAILS))
1190 fprintf (dump_file, "Unifying %s to %s\n",
1191 get_varinfo (from)->name,
1192 get_varinfo (to)->name);
1195 stats.unified_vars_dynamic++;
1197 stats.unified_vars_static++;
1199 merge_graph_nodes (graph, to, from);
1200 merge_node_constraints (graph, to, from);
1202 if (update_changed && TEST_BIT (changed, from))
1204 RESET_BIT (changed, from);
1205 if (!TEST_BIT (changed, to))
1206 SET_BIT (changed, to);
1209 gcc_assert (changed_count > 0);
1214 /* If the solution changes because of the merging, we need to mark
1215 the variable as changed. */
1216 if (bitmap_ior_into (get_varinfo (to)->solution,
1217 get_varinfo (from)->solution))
1219 if (update_changed && !TEST_BIT (changed, to))
1221 SET_BIT (changed, to);
1226 BITMAP_FREE (get_varinfo (from)->solution);
1227 BITMAP_FREE (get_varinfo (from)->oldsolution);
1229 if (stats.iterations > 0)
1231 BITMAP_FREE (get_varinfo (to)->oldsolution);
1232 get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1235 if (valid_graph_edge (graph, to, to))
1237 if (graph->succs[to])
1238 bitmap_clear_bit (graph->succs[to], to);
1242 /* Information needed to compute the topological ordering of a graph. */
1246 /* sbitmap of visited nodes. */
1248 /* Array that stores the topological order of the graph, *in
1250 VEC(unsigned,heap) *topo_order;
1254 /* Initialize and return a topological info structure. */
1256 static struct topo_info *
1257 init_topo_info (void)
1259 size_t size = VEC_length (varinfo_t, varmap);
1260 struct topo_info *ti = XNEW (struct topo_info);
1261 ti->visited = sbitmap_alloc (size);
1262 sbitmap_zero (ti->visited);
1263 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1268 /* Free the topological sort info pointed to by TI. */
1271 free_topo_info (struct topo_info *ti)
1273 sbitmap_free (ti->visited);
1274 VEC_free (unsigned, heap, ti->topo_order);
1278 /* Visit the graph in topological order, and store the order in the
1279 topo_info structure. */
1282 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1288 SET_BIT (ti->visited, n);
1290 if (graph->succs[n])
1291 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1293 if (!TEST_BIT (ti->visited, j))
1294 topo_visit (graph, ti, j);
1297 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1300 /* Return true if variable N + OFFSET is a legal field of N. */
1303 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1305 varinfo_t ninfo = get_varinfo (n);
1307 /* For things we've globbed to single variables, any offset into the
1308 variable acts like the entire variable, so that it becomes offset
1310 if (ninfo->is_special_var
1311 || ninfo->is_artificial_var
1312 || ninfo->is_unknown_size_var)
1317 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1320 /* Process a constraint C that represents *x = &y. */
1323 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1324 constraint_t c, bitmap delta)
1326 unsigned int rhs = c->rhs.var;
1330 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1331 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1333 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1334 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
1336 /* *x != NULL && *x != ANYTHING*/
1340 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1342 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1346 sol = get_varinfo (t)->solution;
1347 if (!bitmap_bit_p (sol, rhs))
1349 bitmap_set_bit (sol, rhs);
1350 if (!TEST_BIT (changed, t))
1352 SET_BIT (changed, t);
1357 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1358 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1363 /* Process a constraint C that represents x = *y, using DELTA as the
1364 starting solution. */
1367 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1370 unsigned int lhs = find (c->lhs.var);
1372 bitmap sol = get_varinfo (lhs)->solution;
1376 if (bitmap_bit_p (delta, anything_id))
1378 flag = !bitmap_bit_p (sol, anything_id);
1380 bitmap_set_bit (sol, anything_id);
1383 /* For each variable j in delta (Sol(y)), add
1384 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1385 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1387 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1388 if (type_safe (j, &roffset))
1391 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1394 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1399 /* Adding edges from the special vars is pointless.
1400 They don't have sets that can change. */
1401 if (get_varinfo (t) ->is_special_var)
1402 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1403 else if (add_graph_edge (graph, lhs, t))
1404 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1406 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1407 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1412 /* If the LHS solution changed, mark the var as changed. */
1415 get_varinfo (lhs)->solution = sol;
1416 if (!TEST_BIT (changed, lhs))
1418 SET_BIT (changed, lhs);
1424 /* Process a constraint C that represents *x = y. */
1427 do_ds_constraint (constraint_t c, bitmap delta)
1429 unsigned int rhs = find (c->rhs.var);
1430 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1431 bitmap sol = get_varinfo (rhs)->solution;
1435 if (bitmap_bit_p (sol, anything_id))
1437 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1439 varinfo_t jvi = get_varinfo (j);
1441 unsigned int loff = c->lhs.offset;
1442 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
1445 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1450 if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id))
1452 bitmap_set_bit (get_varinfo (t)->solution, anything_id);
1453 if (!TEST_BIT (changed, t))
1455 SET_BIT (changed, t);
1463 /* For each member j of delta (Sol(x)), add an edge from y to j and
1464 union Sol(y) into Sol(j) */
1465 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1467 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1468 if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
1472 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1475 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1479 tmp = get_varinfo (t)->solution;
1481 if (set_union_with_increment (tmp, sol, roff))
1483 get_varinfo (t)->solution = tmp;
1485 sol = get_varinfo (rhs)->solution;
1486 if (!TEST_BIT (changed, t))
1488 SET_BIT (changed, t);
1493 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1494 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1498 /* Handle a non-simple (simple meaning requires no iteration),
1499 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1502 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1504 if (c->lhs.type == DEREF)
1506 if (c->rhs.type == ADDRESSOF)
1509 do_da_constraint (graph, c, delta);
1514 do_ds_constraint (c, delta);
1517 else if (c->rhs.type == DEREF)
1520 if (!(get_varinfo (c->lhs.var)->is_special_var))
1521 do_sd_constraint (graph, c, delta);
1530 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1531 t = find (c->rhs.var);
1532 solution = get_varinfo (t)->solution;
1533 t = find (c->lhs.var);
1534 tmp = get_varinfo (t)->solution;
1536 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1540 get_varinfo (t)->solution = tmp;
1541 if (!TEST_BIT (changed, t))
1543 SET_BIT (changed, t);
1550 /* Initialize and return a new SCC info structure. */
1552 static struct scc_info *
1553 init_scc_info (size_t size)
1555 struct scc_info *si = XNEW (struct scc_info);
1558 si->current_index = 0;
1559 si->visited = sbitmap_alloc (size);
1560 sbitmap_zero (si->visited);
1561 si->roots = sbitmap_alloc (size);
1562 sbitmap_zero (si->roots);
1563 si->node_mapping = XNEWVEC (unsigned int, size);
1564 si->dfs = XCNEWVEC (unsigned int, size);
1566 for (i = 0; i < size; i++)
1567 si->node_mapping[i] = i;
1569 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1573 /* Free an SCC info structure pointed to by SI */
1576 free_scc_info (struct scc_info *si)
1578 sbitmap_free (si->visited);
1579 sbitmap_free (si->roots);
1580 free (si->node_mapping);
1582 VEC_free (unsigned, heap, si->scc_stack);
1587 /* Find indirect cycles in GRAPH that occur, using strongly connected
1588 components, and note them in the indirect cycles map.
1590 This technique comes from Ben Hardekopf and Calvin Lin,
1591 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1592 Lines of Code", submitted to PLDI 2007. */
1595 find_indirect_cycles (constraint_graph_t graph)
1598 unsigned int size = graph->size;
1599 struct scc_info *si = init_scc_info (size);
1601 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1602 if (!TEST_BIT (si->visited, i) && find (i) == i)
1603 scc_visit (graph, si, i);
1608 /* Compute a topological ordering for GRAPH, and store the result in the
1609 topo_info structure TI. */
1612 compute_topo_order (constraint_graph_t graph,
1613 struct topo_info *ti)
1616 unsigned int size = VEC_length (varinfo_t, varmap);
1618 for (i = 0; i != size; ++i)
1619 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1620 topo_visit (graph, ti, i);
1623 /* Perform offline variable substitution.
1625 This is a linear time way of identifying variables that must have
1626 equivalent points-to sets, including those caused by static cycles,
1627 and single entry subgraphs, in the constraint graph.
1629 The technique is described in "Off-line variable substitution for
1630 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1631 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56.
1633 There is an optimal way to do this involving hash based value
1634 numbering, once the technique is published i will implement it
1637 The general method of finding equivalence classes is as follows:
1638 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1639 Add fake nodes (ADDRESS nodes) and edges for a = &b constraints.
1640 Initialize all non-REF/ADDRESS nodes to be direct nodes
1641 For each SCC in the predecessor graph:
1642 for each member (x) of the SCC
1643 if x is not a direct node:
1644 set rootnode(SCC) to be not a direct node
1645 collapse node x into rootnode(SCC).
1646 if rootnode(SCC) is not a direct node:
1647 label rootnode(SCC) with a new equivalence class
1649 if all labeled predecessors of rootnode(SCC) have the same
1651 label rootnode(SCC) with this label
1653 label rootnode(SCC) with a new equivalence class
1655 All direct nodes with the same equivalence class can be replaced
1656 with a single representative node.
1657 All unlabeled nodes (label == 0) are not pointers and all edges
1658 involving them can be eliminated.
1659 We perform these optimizations during move_complex_constraints.
1662 static int equivalence_class;
1664 /* Recursive routine to find strongly connected components in GRAPH,
1665 and label it's nodes with equivalence classes.
1666 This is used during variable substitution to find cycles involving
1667 the regular or implicit predecessors, and label them as equivalent.
1668 The SCC finding algorithm used is the same as that for scc_visit. */
1671 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1675 unsigned int my_dfs;
1677 gcc_assert (si->node_mapping[n] == n);
1678 SET_BIT (si->visited, n);
1679 si->dfs[n] = si->current_index ++;
1680 my_dfs = si->dfs[n];
1682 /* Visit all the successors. */
1683 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1685 unsigned int w = si->node_mapping[i];
1687 if (TEST_BIT (si->roots, w))
1690 if (!TEST_BIT (si->visited, w))
1691 label_visit (graph, si, w);
1693 unsigned int t = si->node_mapping[w];
1694 unsigned int nnode = si->node_mapping[n];
1695 gcc_assert (nnode == n);
1697 if (si->dfs[t] < si->dfs[nnode])
1698 si->dfs[n] = si->dfs[t];
1702 /* Visit all the implicit predecessors. */
1703 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1705 unsigned int w = si->node_mapping[i];
1707 if (TEST_BIT (si->roots, w))
1710 if (!TEST_BIT (si->visited, w))
1711 label_visit (graph, si, w);
1713 unsigned int t = si->node_mapping[w];
1714 unsigned int nnode = si->node_mapping[n];
1715 gcc_assert (nnode == n);
1717 if (si->dfs[t] < si->dfs[nnode])
1718 si->dfs[n] = si->dfs[t];
1722 /* See if any components have been identified. */
1723 if (si->dfs[n] == my_dfs)
1725 while (VEC_length (unsigned, si->scc_stack) != 0
1726 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1728 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1729 si->node_mapping[w] = n;
1731 if (!TEST_BIT (graph->direct_nodes, w))
1732 RESET_BIT (graph->direct_nodes, n);
1734 SET_BIT (si->roots, n);
1736 if (!TEST_BIT (graph->direct_nodes, n))
1738 graph->label[n] = equivalence_class++;
1742 unsigned int size = 0;
1743 unsigned int firstlabel = ~0;
1745 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1747 unsigned int j = si->node_mapping[i];
1749 if (j == n || graph->label[j] == 0)
1752 if (firstlabel == (unsigned int)~0)
1754 firstlabel = graph->label[j];
1757 else if (graph->label[j] != firstlabel)
1762 graph->label[n] = 0;
1764 graph->label[n] = firstlabel;
1766 graph->label[n] = equivalence_class++;
1770 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1773 /* Perform offline variable substitution, discovering equivalence
1774 classes, and eliminating non-pointer variables. */
1776 static struct scc_info *
1777 perform_var_substitution (constraint_graph_t graph)
1780 unsigned int size = graph->size;
1781 struct scc_info *si = init_scc_info (size);
1783 bitmap_obstack_initialize (&iteration_obstack);
1784 equivalence_class = 0;
1786 /* We only need to visit the non-address nodes for labeling
1787 purposes, as the address nodes will never have any predecessors,
1788 because &x never appears on the LHS of a constraint. */
1789 for (i = 0; i < LAST_REF_NODE; i++)
1790 if (!TEST_BIT (si->visited, si->node_mapping[i]))
1791 label_visit (graph, si, si->node_mapping[i]);
1793 if (dump_file && (dump_flags & TDF_DETAILS))
1794 for (i = 0; i < FIRST_REF_NODE; i++)
1796 bool direct_node = TEST_BIT (graph->direct_nodes, i);
1798 "Equivalence class for %s node id %d:%s is %d\n",
1799 direct_node ? "Direct node" : "Indirect node", i,
1800 get_varinfo (i)->name,
1801 graph->label[si->node_mapping[i]]);
1804 /* Quickly eliminate our non-pointer variables. */
1806 for (i = 0; i < FIRST_REF_NODE; i++)
1808 unsigned int node = si->node_mapping[i];
1810 if (graph->label[node] == 0 && TEST_BIT (graph->direct_nodes, node))
1812 if (dump_file && (dump_flags & TDF_DETAILS))
1814 "%s is a non-pointer variable, eliminating edges.\n",
1815 get_varinfo (node)->name);
1816 stats.nonpointer_vars++;
1817 clear_edges_for_node (graph, node);
1823 /* Free information that was only necessary for variable
1827 free_var_substitution_info (struct scc_info *si)
1830 free (graph->label);
1831 free (graph->eq_rep);
1832 sbitmap_free (graph->direct_nodes);
1833 bitmap_obstack_release (&iteration_obstack);
1836 /* Return an existing node that is equivalent to NODE, which has
1837 equivalence class LABEL, if one exists. Return NODE otherwise. */
1840 find_equivalent_node (constraint_graph_t graph,
1841 unsigned int node, unsigned int label)
1843 /* If the address version of this variable is unused, we can
1844 substitute it for anything else with the same label.
1845 Otherwise, we know the pointers are equivalent, but not the
1848 if (graph->label[FIRST_ADDR_NODE + node] == 0)
1850 gcc_assert (label < graph->size);
1852 if (graph->eq_rep[label] != -1)
1854 /* Unify the two variables since we know they are equivalent. */
1855 if (unite (graph->eq_rep[label], node))
1856 unify_nodes (graph, graph->eq_rep[label], node, false);
1857 return graph->eq_rep[label];
1861 graph->eq_rep[label] = node;
1867 /* Move complex constraints to the appropriate nodes, and collapse
1868 variables we've discovered are equivalent during variable
1869 substitution. SI is the SCC_INFO that is the result of
1870 perform_variable_substitution. */
1873 move_complex_constraints (constraint_graph_t graph,
1874 struct scc_info *si)
1880 for (j = 0; j < graph->size; j++)
1881 gcc_assert (find (j) == j);
1883 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1885 struct constraint_expr lhs = c->lhs;
1886 struct constraint_expr rhs = c->rhs;
1887 unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id);
1888 unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id);
1889 unsigned int lhsnode, rhsnode;
1890 unsigned int lhslabel, rhslabel;
1892 lhsnode = si->node_mapping[lhsvar];
1893 rhsnode = si->node_mapping[rhsvar];
1894 lhslabel = graph->label[lhsnode];
1895 rhslabel = graph->label[rhsnode];
1897 /* See if it is really a non-pointer variable, and if so, ignore
1901 if (!TEST_BIT (graph->direct_nodes, lhsnode))
1902 lhslabel = graph->label[lhsnode] = equivalence_class++;
1905 if (dump_file && (dump_flags & TDF_DETAILS))
1908 fprintf (dump_file, "%s is a non-pointer variable,"
1909 "ignoring constraint:",
1910 get_varinfo (lhs.var)->name);
1911 dump_constraint (dump_file, c);
1913 VEC_replace (constraint_t, constraints, i, NULL);
1920 if (!TEST_BIT (graph->direct_nodes, rhsnode))
1921 rhslabel = graph->label[rhsnode] = equivalence_class++;
1924 if (dump_file && (dump_flags & TDF_DETAILS))
1927 fprintf (dump_file, "%s is a non-pointer variable,"
1928 "ignoring constraint:",
1929 get_varinfo (rhs.var)->name);
1930 dump_constraint (dump_file, c);
1932 VEC_replace (constraint_t, constraints, i, NULL);
1937 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
1938 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
1939 c->lhs.var = lhsvar;
1940 c->rhs.var = rhsvar;
1942 if (lhs.type == DEREF)
1944 if (rhs.type == ADDRESSOF || rhsvar > anything_id)
1945 insert_into_complex (graph, lhsvar, c);
1947 else if (rhs.type == DEREF)
1949 if (!(get_varinfo (lhsvar)->is_special_var))
1950 insert_into_complex (graph, rhsvar, c);
1952 else if (rhs.type != ADDRESSOF && lhsvar > anything_id
1953 && (lhs.offset != 0 || rhs.offset != 0))
1955 insert_into_complex (graph, rhsvar, c);
1961 /* Eliminate indirect cycles involving NODE. Return true if NODE was
1962 part of an SCC, false otherwise. */
1965 eliminate_indirect_cycles (unsigned int node)
1967 if (graph->indirect_cycles[node] != -1
1968 && !bitmap_empty_p (get_varinfo (node)->solution))
1971 VEC(unsigned,heap) *queue = NULL;
1973 unsigned int to = find (graph->indirect_cycles[node]);
1976 /* We can't touch the solution set and call unify_nodes
1977 at the same time, because unify_nodes is going to do
1978 bitmap unions into it. */
1980 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
1982 if (find (i) == i && i != to)
1985 VEC_safe_push (unsigned, heap, queue, i);
1990 VEC_iterate (unsigned, queue, queuepos, i);
1993 unify_nodes (graph, to, i, true);
1995 VEC_free (unsigned, heap, queue);
2001 /* Solve the constraint graph GRAPH using our worklist solver.
2002 This is based on the PW* family of solvers from the "Efficient Field
2003 Sensitive Pointer Analysis for C" paper.
2004 It works by iterating over all the graph nodes, processing the complex
2005 constraints and propagating the copy constraints, until everything stops
2006 changed. This corresponds to steps 6-8 in the solving list given above. */
2009 solve_graph (constraint_graph_t graph)
2011 unsigned int size = VEC_length (varinfo_t, varmap);
2016 changed = sbitmap_alloc (size);
2017 sbitmap_zero (changed);
2019 /* Mark all initial non-collapsed nodes as changed. */
2020 for (i = 0; i < size; i++)
2022 varinfo_t ivi = get_varinfo (i);
2023 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2024 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2025 || VEC_length (constraint_t, graph->complex[i]) > 0))
2027 SET_BIT (changed, i);
2032 /* Allocate a bitmap to be used to store the changed bits. */
2033 pts = BITMAP_ALLOC (&pta_obstack);
2035 while (changed_count > 0)
2038 struct topo_info *ti = init_topo_info ();
2041 bitmap_obstack_initialize (&iteration_obstack);
2043 compute_topo_order (graph, ti);
2045 while (VEC_length (unsigned, ti->topo_order) != 0)
2048 i = VEC_pop (unsigned, ti->topo_order);
2050 /* If this variable is not a representative, skip it. */
2054 /* In certain indirect cycle cases, we may merge this
2055 variable to another. */
2056 if (eliminate_indirect_cycles (i) && find (i) != i)
2059 /* If the node has changed, we need to process the
2060 complex constraints and outgoing edges again. */
2061 if (TEST_BIT (changed, i))
2066 VEC(constraint_t,heap) *complex = graph->complex[i];
2067 bool solution_empty;
2069 RESET_BIT (changed, i);
2072 /* Compute the changed set of solution bits. */
2073 bitmap_and_compl (pts, get_varinfo (i)->solution,
2074 get_varinfo (i)->oldsolution);
2076 if (bitmap_empty_p (pts))
2079 bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2081 solution = get_varinfo (i)->solution;
2082 solution_empty = bitmap_empty_p (solution);
2084 /* Process the complex constraints */
2085 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2087 /* The only complex constraint that can change our
2088 solution to non-empty, given an empty solution,
2089 is a constraint where the lhs side is receiving
2090 some set from elsewhere. */
2091 if (!solution_empty || c->lhs.type != DEREF)
2092 do_complex_constraint (graph, c, pts);
2095 solution_empty = bitmap_empty_p (solution);
2097 if (!solution_empty)
2101 /* Propagate solution to all successors. */
2102 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2108 unsigned int to = find (j);
2109 tmp = get_varinfo (to)->solution;
2112 /* Don't try to propagate to ourselves. */
2116 flag = set_union_with_increment (tmp, pts, 0);
2120 get_varinfo (to)->solution = tmp;
2121 if (!TEST_BIT (changed, to))
2123 SET_BIT (changed, to);
2131 free_topo_info (ti);
2132 bitmap_obstack_release (&iteration_obstack);
2136 sbitmap_free (changed);
2137 bitmap_obstack_release (&oldpta_obstack);
2140 /* Map from trees to variable infos. */
2141 static struct pointer_map_t *vi_for_tree;
2144 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2147 insert_vi_for_tree (tree t, varinfo_t vi)
2149 void **slot = pointer_map_insert (vi_for_tree, t);
2151 gcc_assert (*slot == NULL);
2155 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2156 exist in the map, return NULL, otherwise, return the varinfo we found. */
2159 lookup_vi_for_tree (tree t)
2161 void **slot = pointer_map_contains (vi_for_tree, t);
2165 return (varinfo_t) *slot;
2168 /* Return a printable name for DECL */
2171 alias_get_name (tree decl)
2173 const char *res = get_name (decl);
2175 int num_printed = 0;
2184 if (TREE_CODE (decl) == SSA_NAME)
2186 num_printed = asprintf (&temp, "%s_%u",
2187 alias_get_name (SSA_NAME_VAR (decl)),
2188 SSA_NAME_VERSION (decl));
2190 else if (DECL_P (decl))
2192 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2194 if (num_printed > 0)
2196 res = ggc_strdup (temp);
2202 /* Find the variable id for tree T in the map.
2203 If T doesn't exist in the map, create an entry for it and return it. */
2206 get_vi_for_tree (tree t)
2208 void **slot = pointer_map_contains (vi_for_tree, t);
2210 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2212 return (varinfo_t) *slot;
2215 /* Get a constraint expression from an SSA_VAR_P node. */
2217 static struct constraint_expr
2218 get_constraint_exp_from_ssa_var (tree t)
2220 struct constraint_expr cexpr;
2222 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2224 /* For parameters, get at the points-to set for the actual parm
2226 if (TREE_CODE (t) == SSA_NAME
2227 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2228 && SSA_NAME_IS_DEFAULT_DEF (t))
2229 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
2231 cexpr.type = SCALAR;
2233 cexpr.var = get_vi_for_tree (t)->id;
2234 /* If we determine the result is "anything", and we know this is readonly,
2235 say it points to readonly memory instead. */
2236 if (cexpr.var == anything_id && TREE_READONLY (t))
2238 cexpr.type = ADDRESSOF;
2239 cexpr.var = readonly_id;
2246 /* Process a completed constraint T, and add it to the constraint
2250 process_constraint (constraint_t t)
2252 struct constraint_expr rhs = t->rhs;
2253 struct constraint_expr lhs = t->lhs;
2255 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2256 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2258 if (lhs.type == DEREF)
2259 get_varinfo (lhs.var)->directly_dereferenced = true;
2260 if (rhs.type == DEREF)
2261 get_varinfo (rhs.var)->directly_dereferenced = true;
2263 if (!use_field_sensitive)
2269 /* ANYTHING == ANYTHING is pointless. */
2270 if (lhs.var == anything_id && rhs.var == anything_id)
2273 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2274 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
2279 process_constraint (t);
2281 /* This can happen in our IR with things like n->a = *p */
2282 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2284 /* Split into tmp = *rhs, *lhs = tmp */
2285 tree rhsdecl = get_varinfo (rhs.var)->decl;
2286 tree pointertype = TREE_TYPE (rhsdecl);
2287 tree pointedtotype = TREE_TYPE (pointertype);
2288 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2289 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2291 /* If this is an aggregate of known size, we should have passed
2292 this off to do_structure_copy, and it should have broken it
2294 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
2295 || get_varinfo (rhs.var)->is_unknown_size_var);
2297 process_constraint (new_constraint (tmplhs, rhs));
2298 process_constraint (new_constraint (lhs, tmplhs));
2302 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2303 VEC_safe_push (constraint_t, heap, constraints, t);
2307 /* Return true if T is a variable of a type that could contain
2311 could_have_pointers (tree t)
2313 tree type = TREE_TYPE (t);
2315 if (POINTER_TYPE_P (type)
2316 || AGGREGATE_TYPE_P (type)
2317 || TREE_CODE (type) == COMPLEX_TYPE)
2323 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2326 static unsigned HOST_WIDE_INT
2327 bitpos_of_field (const tree fdecl)
2330 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
2331 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
2334 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
2335 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
2339 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2340 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2343 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
2344 const unsigned HOST_WIDE_INT fieldsize,
2345 const unsigned HOST_WIDE_INT accesspos,
2346 const unsigned HOST_WIDE_INT accesssize)
2348 if (fieldpos == accesspos && fieldsize == accesssize)
2350 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
2352 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2358 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2361 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results)
2364 HOST_WIDE_INT bitsize = -1;
2365 HOST_WIDE_INT bitmaxsize = -1;
2366 HOST_WIDE_INT bitpos;
2368 struct constraint_expr *result;
2369 unsigned int beforelength = VEC_length (ce_s, *results);
2371 /* Some people like to do cute things like take the address of
2374 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2375 forzero = TREE_OPERAND (forzero, 0);
2377 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2379 struct constraint_expr temp;
2382 temp.var = integer_id;
2384 VEC_safe_push (ce_s, heap, *results, &temp);
2388 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2390 /* String constants are readonly, so there is nothing to really do
2392 if (TREE_CODE (t) == STRING_CST)
2395 get_constraint_for (t, results);
2396 result = VEC_last (ce_s, *results);
2397 result->offset = bitpos;
2399 gcc_assert (beforelength + 1 == VEC_length (ce_s, *results));
2401 /* This can also happen due to weird offsetof type macros. */
2402 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2403 result->type = SCALAR;
2405 if (result->type == SCALAR)
2407 /* In languages like C, you can access one past the end of an
2408 array. You aren't allowed to dereference it, so we can
2409 ignore this constraint. When we handle pointer subtraction,
2410 we may have to do something cute here. */
2412 if (result->offset < get_varinfo (result->var)->fullsize
2415 /* It's also not true that the constraint will actually start at the
2416 right offset, it may start in some padding. We only care about
2417 setting the constraint to the first actual field it touches, so
2420 for (curr = get_varinfo (result->var); curr; curr = curr->next)
2422 if (offset_overlaps_with_access (curr->offset, curr->size,
2423 result->offset, bitmaxsize))
2425 result->var = curr->id;
2429 /* assert that we found *some* field there. The user couldn't be
2430 accessing *only* padding. */
2431 /* Still the user could access one past the end of an array
2432 embedded in a struct resulting in accessing *only* padding. */
2433 gcc_assert (curr || ref_contains_array_ref (orig_t));
2435 else if (bitmaxsize == 0)
2437 if (dump_file && (dump_flags & TDF_DETAILS))
2438 fprintf (dump_file, "Access to zero-sized part of variable,"
2442 if (dump_file && (dump_flags & TDF_DETAILS))
2443 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2450 /* Dereference the constraint expression CONS, and return the result.
2451 DEREF (ADDRESSOF) = SCALAR
2452 DEREF (SCALAR) = DEREF
2453 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2454 This is needed so that we can handle dereferencing DEREF constraints. */
2457 do_deref (VEC (ce_s, heap) **constraints)
2459 struct constraint_expr *c;
2462 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2464 if (c->type == SCALAR)
2466 else if (c->type == ADDRESSOF)
2468 else if (c->type == DEREF)
2470 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
2471 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2472 process_constraint (new_constraint (tmplhs, *c));
2473 c->var = tmplhs.var;
2480 /* Given a tree T, return the constraint expression for it. */
2483 get_constraint_for (tree t, VEC (ce_s, heap) **results)
2485 struct constraint_expr temp;
2487 /* x = integer is all glommed to a single variable, which doesn't
2488 point to anything by itself. That is, of course, unless it is an
2489 integer constant being treated as a pointer, in which case, we
2490 will return that this is really the addressof anything. This
2491 happens below, since it will fall into the default case. The only
2492 case we know something about an integer treated like a pointer is
2493 when it is the NULL pointer, and then we just say it points to
2495 if (TREE_CODE (t) == INTEGER_CST
2496 && !POINTER_TYPE_P (TREE_TYPE (t)))
2498 temp.var = integer_id;
2501 VEC_safe_push (ce_s, heap, *results, &temp);
2504 else if (TREE_CODE (t) == INTEGER_CST
2505 && integer_zerop (t))
2507 temp.var = nothing_id;
2508 temp.type = ADDRESSOF;
2510 VEC_safe_push (ce_s, heap, *results, &temp);
2514 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2516 case tcc_expression:
2519 switch (TREE_CODE (t))
2523 struct constraint_expr *c;
2525 tree exp = TREE_OPERAND (t, 0);
2526 tree pttype = TREE_TYPE (TREE_TYPE (t));
2528 get_constraint_for (exp, results);
2530 /* Make sure we capture constraints to all elements
2532 if ((handled_component_p (exp)
2533 && ref_contains_array_ref (exp))
2534 || TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE)
2536 struct constraint_expr *origrhs;
2538 struct constraint_expr tmp;
2540 if (VEC_length (ce_s, *results) == 0)
2543 gcc_assert (VEC_length (ce_s, *results) == 1);
2544 origrhs = VEC_last (ce_s, *results);
2546 VEC_pop (ce_s, *results);
2547 origvar = get_varinfo (origrhs->var);
2548 for (; origvar; origvar = origvar->next)
2550 tmp.var = origvar->id;
2551 VEC_safe_push (ce_s, heap, *results, &tmp);
2554 else if (VEC_length (ce_s, *results) == 1
2555 && (AGGREGATE_TYPE_P (pttype)
2556 || TREE_CODE (pttype) == COMPLEX_TYPE))
2558 struct constraint_expr *origrhs;
2560 struct constraint_expr tmp;
2562 gcc_assert (VEC_length (ce_s, *results) == 1);
2563 origrhs = VEC_last (ce_s, *results);
2565 VEC_pop (ce_s, *results);
2566 origvar = get_varinfo (origrhs->var);
2567 for (; origvar; origvar = origvar->next)
2569 tmp.var = origvar->id;
2570 VEC_safe_push (ce_s, heap, *results, &tmp);
2574 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2576 if (c->type == DEREF)
2579 c->type = ADDRESSOF;
2585 /* XXX: In interprocedural mode, if we didn't have the
2586 body, we would need to do *each pointer argument =
2588 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2591 tree heapvar = heapvar_lookup (t);
2593 if (heapvar == NULL)
2595 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2596 DECL_EXTERNAL (heapvar) = 1;
2597 get_var_ann (heapvar)->is_heapvar = 1;
2598 if (gimple_referenced_vars (cfun))
2599 add_referenced_var (heapvar);
2600 heapvar_insert (t, heapvar);
2603 temp.var = create_variable_info_for (heapvar,
2604 alias_get_name (heapvar));
2606 vi = get_varinfo (temp.var);
2607 vi->is_artificial_var = 1;
2608 vi->is_heap_var = 1;
2609 temp.type = ADDRESSOF;
2611 VEC_safe_push (ce_s, heap, *results, &temp);
2616 temp.var = anything_id;
2619 VEC_safe_push (ce_s, heap, *results, &temp);
2625 temp.type = ADDRESSOF;
2626 temp.var = anything_id;
2628 VEC_safe_push (ce_s, heap, *results, &temp);
2635 switch (TREE_CODE (t))
2639 get_constraint_for (TREE_OPERAND (t, 0), results);
2644 case ARRAY_RANGE_REF:
2646 get_constraint_for_component_ref (t, results);
2650 temp.type = ADDRESSOF;
2651 temp.var = anything_id;
2653 VEC_safe_push (ce_s, heap, *results, &temp);
2660 switch (TREE_CODE (t))
2664 case NON_LVALUE_EXPR:
2666 tree op = TREE_OPERAND (t, 0);
2668 /* Cast from non-pointer to pointers are bad news for us.
2669 Anything else, we see through */
2670 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2671 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2673 get_constraint_for (op, results);
2681 temp.type = ADDRESSOF;
2682 temp.var = anything_id;
2684 VEC_safe_push (ce_s, heap, *results, &temp);
2689 case tcc_exceptional:
2691 switch (TREE_CODE (t))
2695 get_constraint_for (PHI_RESULT (t), results);
2701 struct constraint_expr temp;
2702 temp = get_constraint_exp_from_ssa_var (t);
2703 VEC_safe_push (ce_s, heap, *results, &temp);
2709 temp.type = ADDRESSOF;
2710 temp.var = anything_id;
2712 VEC_safe_push (ce_s, heap, *results, &temp);
2717 case tcc_declaration:
2719 struct constraint_expr temp;
2720 temp = get_constraint_exp_from_ssa_var (t);
2721 VEC_safe_push (ce_s, heap, *results, &temp);
2726 temp.type = ADDRESSOF;
2727 temp.var = anything_id;
2729 VEC_safe_push (ce_s, heap, *results, &temp);
2736 /* Handle the structure copy case where we have a simple structure copy
2737 between LHS and RHS that is of SIZE (in bits)
2739 For each field of the lhs variable (lhsfield)
2740 For each field of the rhs variable at lhsfield.offset (rhsfield)
2741 add the constraint lhsfield = rhsfield
2743 If we fail due to some kind of type unsafety or other thing we
2744 can't handle, return false. We expect the caller to collapse the
2745 variable in that case. */
2748 do_simple_structure_copy (const struct constraint_expr lhs,
2749 const struct constraint_expr rhs,
2750 const unsigned HOST_WIDE_INT size)
2752 varinfo_t p = get_varinfo (lhs.var);
2753 unsigned HOST_WIDE_INT pstart, last;
2755 last = p->offset + size;
2756 for (; p && p->offset < last; p = p->next)
2759 struct constraint_expr templhs = lhs;
2760 struct constraint_expr temprhs = rhs;
2761 unsigned HOST_WIDE_INT fieldoffset;
2763 templhs.var = p->id;
2764 q = get_varinfo (temprhs.var);
2765 fieldoffset = p->offset - pstart;
2766 q = first_vi_for_offset (q, q->offset + fieldoffset);
2769 temprhs.var = q->id;
2770 process_constraint (new_constraint (templhs, temprhs));
2776 /* Handle the structure copy case where we have a structure copy between a
2777 aggregate on the LHS and a dereference of a pointer on the RHS
2778 that is of SIZE (in bits)
2780 For each field of the lhs variable (lhsfield)
2781 rhs.offset = lhsfield->offset
2782 add the constraint lhsfield = rhs
2786 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2787 const struct constraint_expr rhs,
2788 const unsigned HOST_WIDE_INT size)
2790 varinfo_t p = get_varinfo (lhs.var);
2791 unsigned HOST_WIDE_INT pstart,last;
2793 last = p->offset + size;
2795 for (; p && p->offset < last; p = p->next)
2798 struct constraint_expr templhs = lhs;
2799 struct constraint_expr temprhs = rhs;
2800 unsigned HOST_WIDE_INT fieldoffset;
2803 if (templhs.type == SCALAR)
2804 templhs.var = p->id;
2806 templhs.offset = p->offset;
2808 q = get_varinfo (temprhs.var);
2809 fieldoffset = p->offset - pstart;
2810 temprhs.offset += fieldoffset;
2811 process_constraint (new_constraint (templhs, temprhs));
2815 /* Handle the structure copy case where we have a structure copy
2816 between a aggregate on the RHS and a dereference of a pointer on
2817 the LHS that is of SIZE (in bits)
2819 For each field of the rhs variable (rhsfield)
2820 lhs.offset = rhsfield->offset
2821 add the constraint lhs = rhsfield
2825 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2826 const struct constraint_expr rhs,
2827 const unsigned HOST_WIDE_INT size)
2829 varinfo_t p = get_varinfo (rhs.var);
2830 unsigned HOST_WIDE_INT pstart,last;
2832 last = p->offset + size;
2834 for (; p && p->offset < last; p = p->next)
2837 struct constraint_expr templhs = lhs;
2838 struct constraint_expr temprhs = rhs;
2839 unsigned HOST_WIDE_INT fieldoffset;
2842 if (temprhs.type == SCALAR)
2843 temprhs.var = p->id;
2845 temprhs.offset = p->offset;
2847 q = get_varinfo (templhs.var);
2848 fieldoffset = p->offset - pstart;
2849 templhs.offset += fieldoffset;
2850 process_constraint (new_constraint (templhs, temprhs));
2854 /* Sometimes, frontends like to give us bad type information. This
2855 function will collapse all the fields from VAR to the end of VAR,
2856 into VAR, so that we treat those fields as a single variable.
2857 We return the variable they were collapsed into. */
2860 collapse_rest_of_var (unsigned int var)
2862 varinfo_t currvar = get_varinfo (var);
2865 for (field = currvar->next; field; field = field->next)
2868 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
2869 field->name, currvar->name);
2871 gcc_assert (!field->collapsed_to);
2872 field->collapsed_to = currvar;
2875 currvar->next = NULL;
2876 currvar->size = currvar->fullsize - currvar->offset;
2881 /* Handle aggregate copies by expanding into copies of the respective
2882 fields of the structures. */
2885 do_structure_copy (tree lhsop, tree rhsop)
2887 struct constraint_expr lhs, rhs, tmp;
2888 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
2890 unsigned HOST_WIDE_INT lhssize;
2891 unsigned HOST_WIDE_INT rhssize;
2893 get_constraint_for (lhsop, &lhsc);
2894 get_constraint_for (rhsop, &rhsc);
2895 gcc_assert (VEC_length (ce_s, lhsc) == 1);
2896 gcc_assert (VEC_length (ce_s, rhsc) == 1);
2897 lhs = *(VEC_last (ce_s, lhsc));
2898 rhs = *(VEC_last (ce_s, rhsc));
2900 VEC_free (ce_s, heap, lhsc);
2901 VEC_free (ce_s, heap, rhsc);
2903 /* If we have special var = x, swap it around. */
2904 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2911 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2912 possible it's something we could handle. However, most cases falling
2913 into this are dealing with transparent unions, which are slightly
2915 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2917 rhs.type = ADDRESSOF;
2918 rhs.var = anything_id;
2921 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2922 that special var. */
2923 if (rhs.var <= integer_id)
2925 for (p = get_varinfo (lhs.var); p; p = p->next)
2927 struct constraint_expr templhs = lhs;
2928 struct constraint_expr temprhs = rhs;
2930 if (templhs.type == SCALAR )
2931 templhs.var = p->id;
2933 templhs.offset += p->offset;
2934 process_constraint (new_constraint (templhs, temprhs));
2939 tree rhstype = TREE_TYPE (rhsop);
2940 tree lhstype = TREE_TYPE (lhsop);
2944 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
2945 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
2947 /* If we have a variably sized types on the rhs or lhs, and a deref
2948 constraint, add the constraint, lhsconstraint = &ANYTHING.
2949 This is conservatively correct because either the lhs is an unknown
2950 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2951 constraint, and every variable it can point to must be unknown sized
2952 anyway, so we don't need to worry about fields at all. */
2953 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2954 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2956 rhs.var = anything_id;
2957 rhs.type = ADDRESSOF;
2959 process_constraint (new_constraint (lhs, rhs));
2963 /* The size only really matters insofar as we don't set more or less of
2964 the variable. If we hit an unknown size var, the size should be the
2965 whole darn thing. */
2966 if (get_varinfo (rhs.var)->is_unknown_size_var)
2969 rhssize = TREE_INT_CST_LOW (rhstypesize);
2971 if (get_varinfo (lhs.var)->is_unknown_size_var)
2974 lhssize = TREE_INT_CST_LOW (lhstypesize);
2977 if (rhs.type == SCALAR && lhs.type == SCALAR)
2979 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
2981 lhs.var = collapse_rest_of_var (lhs.var);
2982 rhs.var = collapse_rest_of_var (rhs.var);
2987 process_constraint (new_constraint (lhs, rhs));
2990 else if (lhs.type != DEREF && rhs.type == DEREF)
2991 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2992 else if (lhs.type == DEREF && rhs.type != DEREF)
2993 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
2996 tree pointedtotype = lhstype;
2999 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3000 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
3001 do_structure_copy (tmpvar, rhsop);
3002 do_structure_copy (lhsop, tmpvar);
3008 /* Update related alias information kept in AI. This is used when
3009 building name tags, alias sets and deciding grouping heuristics.
3010 STMT is the statement to process. This function also updates
3011 ADDRESSABLE_VARS. */
3014 update_alias_info (tree stmt, struct alias_info *ai)
3017 use_operand_p use_p;
3019 enum escape_type stmt_escape_type = is_escape_site (stmt);
3021 if (stmt_escape_type == ESCAPE_TO_CALL
3022 || stmt_escape_type == ESCAPE_TO_PURE_CONST)
3024 ai->num_calls_found++;
3025 if (stmt_escape_type == ESCAPE_TO_PURE_CONST)
3026 ai->num_pure_const_calls_found++;
3029 /* Mark all the variables whose address are taken by the statement. */
3030 addr_taken = addresses_taken (stmt);
3033 bitmap_ior_into (gimple_addressable_vars (cfun), addr_taken);
3035 /* If STMT is an escape point, all the addresses taken by it are
3037 if (stmt_escape_type != NO_ESCAPE)
3042 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
3044 tree rvar = referenced_var (i);
3045 if (!unmodifiable_var_p (rvar))
3046 mark_call_clobbered (rvar, stmt_escape_type);
3051 /* Process each operand use. If an operand may be aliased, keep
3052 track of how many times it's being used. For pointers, determine
3053 whether they are dereferenced by the statement, or whether their
3054 value escapes, etc. */
3055 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
3059 struct ptr_info_def *pi;
3060 bool is_store, is_potential_deref;
3061 unsigned num_uses, num_derefs;
3063 op = USE_FROM_PTR (use_p);
3065 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
3066 to the set of addressable variables. */
3067 if (TREE_CODE (op) == ADDR_EXPR)
3069 bitmap addressable_vars = gimple_addressable_vars (cfun);
3071 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
3072 gcc_assert (addressable_vars);
3074 /* PHI nodes don't have annotations for pinning the set
3075 of addresses taken, so we collect them here.
3077 FIXME, should we allow PHI nodes to have annotations
3078 so that they can be treated like regular statements?
3079 Currently, they are treated as second-class
3081 add_to_addressable_set (TREE_OPERAND (op, 0),
3086 /* Ignore constants. */
3087 if (TREE_CODE (op) != SSA_NAME)
3090 var = SSA_NAME_VAR (op);
3091 v_ann = var_ann (var);
3093 /* The base variable of an SSA name must be a GIMPLE register, and thus
3094 it cannot be aliased. */
3095 gcc_assert (!may_be_aliased (var));
3097 /* We are only interested in pointers. */
3098 if (!POINTER_TYPE_P (TREE_TYPE (op)))
3101 pi = get_ptr_info (op);
3103 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3104 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
3106 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
3107 VEC_safe_push (tree, heap, ai->processed_ptrs, op);
3110 /* If STMT is a PHI node, then it will not have pointer
3111 dereferences and it will not be an escape point. */
3112 if (TREE_CODE (stmt) == PHI_NODE)
3115 /* Determine whether OP is a dereferenced pointer, and if STMT
3116 is an escape point, whether OP escapes. */
3117 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
3119 /* Handle a corner case involving address expressions of the
3120 form '&PTR->FLD'. The problem with these expressions is that
3121 they do not represent a dereference of PTR. However, if some
3122 other transformation propagates them into an INDIRECT_REF
3123 expression, we end up with '*(&PTR->FLD)' which is folded
3126 So, if the original code had no other dereferences of PTR,
3127 the aliaser will not create memory tags for it, and when
3128 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3129 memory operations will receive no VDEF/VUSE operands.
3131 One solution would be to have count_uses_and_derefs consider
3132 &PTR->FLD a dereference of PTR. But that is wrong, since it
3133 is not really a dereference but an offset calculation.
3135 What we do here is to recognize these special ADDR_EXPR
3136 nodes. Since these expressions are never GIMPLE values (they
3137 are not GIMPLE invariants), they can only appear on the RHS
3138 of an assignment and their base address is always an
3139 INDIRECT_REF expression. */
3140 is_potential_deref = false;
3141 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3142 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ADDR_EXPR
3143 && !is_gimple_val (GIMPLE_STMT_OPERAND (stmt, 1)))
3145 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3146 this represents a potential dereference of PTR. */
3147 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3148 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3149 if (TREE_CODE (base) == INDIRECT_REF
3150 && TREE_OPERAND (base, 0) == op)
3151 is_potential_deref = true;
3154 if (num_derefs > 0 || is_potential_deref)
3156 /* Mark OP as dereferenced. In a subsequent pass,
3157 dereferenced pointers that point to a set of
3158 variables will be assigned a name tag to alias
3159 all the variables OP points to. */
3160 pi->is_dereferenced = 1;
3162 /* If this is a store operation, mark OP as being
3163 dereferenced to store, otherwise mark it as being
3164 dereferenced to load. */
3166 pointer_set_insert (ai->dereferenced_ptrs_store, var);
3168 pointer_set_insert (ai->dereferenced_ptrs_load, var);
3171 if (stmt_escape_type != NO_ESCAPE && num_derefs < num_uses)
3173 /* If STMT is an escape point and STMT contains at
3174 least one direct use of OP, then the value of OP
3175 escapes and so the pointed-to variables need to
3176 be marked call-clobbered. */
3177 pi->value_escapes_p = 1;
3178 pi->escape_mask |= stmt_escape_type;
3180 /* If the statement makes a function call, assume
3181 that pointer OP will be dereferenced in a store
3182 operation inside the called function. */
3183 if (get_call_expr_in (stmt)
3184 || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
3186 pointer_set_insert (ai->dereferenced_ptrs_store, var);
3187 pi->is_dereferenced = 1;
3192 if (TREE_CODE (stmt) == PHI_NODE)
3195 /* Mark stored variables in STMT as being written to and update the
3196 reference counter for potentially aliased symbols in STMT. */
3197 if (stmt_references_memory_p (stmt) && STORED_SYMS (stmt))
3201 EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi)
3202 pointer_set_insert (ai->written_vars, referenced_var (i));
3207 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3208 Expressions of the type PTR + CST can be handled in two ways:
3210 1- If the constraint for PTR is ADDRESSOF for a non-structure
3211 variable, then we can use it directly because adding or
3212 subtracting a constant may not alter the original ADDRESSOF
3213 constraint (i.e., pointer arithmetic may not legally go outside
3214 an object's boundaries).
3216 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3217 then if CST is a compile-time constant that can be used as an
3218 offset, we can determine which sub-variable will be pointed-to
3221 Return true if the expression is handled. For any other kind of
3222 expression, return false so that each operand can be added as a
3223 separate constraint by the caller. */
3226 handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr)
3229 struct constraint_expr *c, *c2;
3232 VEC (ce_s, heap) *temp = NULL;
3233 unsigned int rhsoffset = 0;
3235 if (TREE_CODE (expr) != PLUS_EXPR
3236 && TREE_CODE (expr) != MINUS_EXPR)
3239 op0 = TREE_OPERAND (expr, 0);
3240 op1 = TREE_OPERAND (expr, 1);
3242 get_constraint_for (op0, &temp);
3243 if (POINTER_TYPE_P (TREE_TYPE (op0))
3244 && TREE_CODE (op1) == INTEGER_CST
3245 && TREE_CODE (expr) == PLUS_EXPR)
3247 rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
3253 for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
3254 for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
3256 if (c2->type == ADDRESSOF && rhsoffset != 0)
3258 varinfo_t temp = get_varinfo (c2->var);
3260 /* An access one after the end of an array is valid,
3261 so simply punt on accesses we cannot resolve. */
3262 temp = first_vi_for_offset (temp, rhsoffset);
3269 c2->offset = rhsoffset;
3270 process_constraint (new_constraint (*c, *c2));
3273 VEC_free (ce_s, heap, temp);
3279 /* Walk statement T setting up aliasing constraints according to the
3280 references found in T. This function is the main part of the
3281 constraint builder. AI points to auxiliary alias information used
3282 when building alias sets and computing alias grouping heuristics. */
3285 find_func_aliases (tree origt)
3288 VEC(ce_s, heap) *lhsc = NULL;
3289 VEC(ce_s, heap) *rhsc = NULL;
3290 struct constraint_expr *c;
3292 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
3293 t = TREE_OPERAND (t, 0);
3295 /* Now build constraints expressions. */
3296 if (TREE_CODE (t) == PHI_NODE)
3298 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))));
3300 /* Only care about pointers and structures containing
3302 if (could_have_pointers (PHI_RESULT (t)))
3307 /* For a phi node, assign all the arguments to
3309 get_constraint_for (PHI_RESULT (t), &lhsc);
3310 for (i = 0; i < PHI_NUM_ARGS (t); i++)
3313 tree strippedrhs = PHI_ARG_DEF (t, i);
3315 STRIP_NOPS (strippedrhs);
3316 rhstype = TREE_TYPE (strippedrhs);
3317 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
3319 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3321 struct constraint_expr *c2;
3322 while (VEC_length (ce_s, rhsc) > 0)
3324 c2 = VEC_last (ce_s, rhsc);
3325 process_constraint (new_constraint (*c, *c2));
3326 VEC_pop (ce_s, rhsc);
3332 /* In IPA mode, we need to generate constraints to pass call
3333 arguments through their calls. There are two cases, either a
3334 GIMPLE_MODIFY_STMT when we are returning a value, or just a plain
3335 CALL_EXPR when we are not. */
3336 else if (in_ipa_mode
3337 && ((TREE_CODE (t) == GIMPLE_MODIFY_STMT
3338 && TREE_CODE (GIMPLE_STMT_OPERAND (t, 1)) == CALL_EXPR
3339 && !(call_expr_flags (GIMPLE_STMT_OPERAND (t, 1))
3340 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
3341 || (TREE_CODE (t) == CALL_EXPR
3342 && !(call_expr_flags (t)
3343 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))))
3348 call_expr_arg_iterator iter;
3352 if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
3354 lhsop = GIMPLE_STMT_OPERAND (t, 0);
3355 rhsop = GIMPLE_STMT_OPERAND (t, 1);
3362 decl = get_callee_fndecl (rhsop);
3364 /* If we can directly resolve the function being called, do so.
3365 Otherwise, it must be some sort of indirect expression that
3366 we should still be able to handle. */
3369 fi = get_vi_for_tree (decl);
3373 decl = CALL_EXPR_FN (rhsop);
3374 fi = get_vi_for_tree (decl);
3377 /* Assign all the passed arguments to the appropriate incoming
3378 parameters of the function. */
3380 FOR_EACH_CALL_EXPR_ARG (arg, iter, rhsop)
3382 struct constraint_expr lhs ;
3383 struct constraint_expr *rhsp;
3385 get_constraint_for (arg, &rhsc);
3386 if (TREE_CODE (decl) != FUNCTION_DECL)
3395 lhs.var = first_vi_for_offset (fi, i)->id;
3398 while (VEC_length (ce_s, rhsc) != 0)
3400 rhsp = VEC_last (ce_s, rhsc);
3401 process_constraint (new_constraint (lhs, *rhsp));
3402 VEC_pop (ce_s, rhsc);
3407 /* If we are returning a value, assign it to the result. */
3410 struct constraint_expr rhs;
3411 struct constraint_expr *lhsp;
3414 get_constraint_for (lhsop, &lhsc);
3415 if (TREE_CODE (decl) != FUNCTION_DECL)
3424 rhs.var = first_vi_for_offset (fi, i)->id;
3427 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3428 process_constraint (new_constraint (*lhsp, rhs));
3431 /* Otherwise, just a regular assignment statement. */
3432 else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
3434 tree lhsop = GIMPLE_STMT_OPERAND (t, 0);
3435 tree rhsop = GIMPLE_STMT_OPERAND (t, 1);
3438 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3439 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)
3440 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop))
3441 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE))
3443 do_structure_copy (lhsop, rhsop);
3447 /* Only care about operations with pointers, structures
3448 containing pointers, dereferences, and call expressions. */
3449 if (could_have_pointers (lhsop)
3450 || TREE_CODE (rhsop) == CALL_EXPR)
3452 get_constraint_for (lhsop, &lhsc);
3453 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
3455 /* RHS that consist of unary operations,
3456 exceptional types, or bare decls/constants, get
3457 handled directly by get_constraint_for. */
3459 case tcc_declaration:
3461 case tcc_exceptional:
3462 case tcc_expression:
3468 get_constraint_for (rhsop, &rhsc);
3469 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3471 struct constraint_expr *c2;
3474 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3475 process_constraint (new_constraint (*c, *c2));
3483 /* For pointer arithmetic of the form
3484 PTR + CST, we can simply use PTR's
3485 constraint because pointer arithmetic is
3486 not allowed to go out of bounds. */
3487 if (handle_ptr_arith (lhsc, rhsop))
3492 /* Otherwise, walk each operand. Notice that we
3493 can't use the operand interface because we need
3494 to process expressions other than simple operands
3495 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3497 for (i = 0; i < TREE_OPERAND_LENGTH (rhsop); i++)
3499 tree op = TREE_OPERAND (rhsop, i);
3502 gcc_assert (VEC_length (ce_s, rhsc) == 0);
3503 get_constraint_for (op, &rhsc);
3504 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3506 struct constraint_expr *c2;
3507 while (VEC_length (ce_s, rhsc) > 0)
3509 c2 = VEC_last (ce_s, rhsc);
3510 process_constraint (new_constraint (*c, *c2));
3511 VEC_pop (ce_s, rhsc);
3520 /* After promoting variables and computing aliasing we will
3521 need to re-scan most statements. FIXME: Try to minimize the
3522 number of statements re-scanned. It's not really necessary to
3523 re-scan *all* statements. */
3524 mark_stmt_modified (origt);
3525 VEC_free (ce_s, heap, rhsc);
3526 VEC_free (ce_s, heap, lhsc);
3530 /* Find the first varinfo in the same variable as START that overlaps with
3532 Effectively, walk the chain of fields for the variable START to find the
3533 first field that overlaps with OFFSET.
3534 Return NULL if we can't find one. */
3537 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3539 varinfo_t curr = start;
3542 /* We may not find a variable in the field list with the actual
3543 offset when when we have glommed a structure to a variable.
3544 In that case, however, offset should still be within the size
3546 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3554 /* Insert the varinfo FIELD into the field list for BASE, at the front
3558 insert_into_field_list (varinfo_t base, varinfo_t field)
3560 varinfo_t prev = base;
3561 varinfo_t curr = base->next;
3567 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3571 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
3573 varinfo_t prev = base;
3574 varinfo_t curr = base->next;
3585 if (field->offset <= curr->offset)
3590 field->next = prev->next;
3595 /* qsort comparison function for two fieldoff's PA and PB */
3598 fieldoff_compare (const void *pa, const void *pb)
3600 const fieldoff_s *foa = (const fieldoff_s *)pa;
3601 const fieldoff_s *fob = (const fieldoff_s *)pb;
3602 HOST_WIDE_INT foasize, fobsize;
3604 if (foa->offset != fob->offset)
3605 return foa->offset - fob->offset;
3607 foasize = TREE_INT_CST_LOW (foa->size);
3608 fobsize = TREE_INT_CST_LOW (fob->size);
3609 return foasize - fobsize;
3612 /* Sort a fieldstack according to the field offset and sizes. */
3614 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3616 qsort (VEC_address (fieldoff_s, fieldstack),
3617 VEC_length (fieldoff_s, fieldstack),
3618 sizeof (fieldoff_s),
3622 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3623 of TYPE onto fieldstack, recording their offsets along the way.
3624 OFFSET is used to keep track of the offset in this entire structure, rather
3625 than just the immediately containing structure. Returns the number
3627 HAS_UNION is set to true if we find a union type as a field of
3631 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
3632 HOST_WIDE_INT offset, bool *has_union)
3637 if (TREE_CODE (type) == COMPLEX_TYPE)
3639 fieldoff_s *real_part, *img_part;
3640 real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3641 real_part->type = TREE_TYPE (type);
3642 real_part->size = TYPE_SIZE (TREE_TYPE (type));
3643 real_part->offset = offset;
3644 real_part->decl = NULL_TREE;
3646 img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3647 img_part->type = TREE_TYPE (type);
3648 img_part->size = TYPE_SIZE (TREE_TYPE (type));
3649 img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
3650 img_part->decl = NULL_TREE;
3655 if (TREE_CODE (type) == ARRAY_TYPE)
3657 tree sz = TYPE_SIZE (type);
3658 tree elsz = TYPE_SIZE (TREE_TYPE (type));
3663 || ! host_integerp (sz, 1)
3664 || TREE_INT_CST_LOW (sz) == 0
3666 || ! host_integerp (elsz, 1)
3667 || TREE_INT_CST_LOW (elsz) == 0)
3670 nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
3671 if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
3674 for (i = 0; i < nr; ++i)
3680 && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
3681 || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
3684 if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
3686 else if (!(pushed = push_fields_onto_fieldstack
3687 (TREE_TYPE (type), fieldstack,
3688 offset + i * TREE_INT_CST_LOW (elsz), has_union)))
3689 /* Empty structures may have actual size, like in C++. So
3690 see if we didn't push any subfields and the size is
3691 nonzero, push the field onto the stack */
3698 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3699 pair->type = TREE_TYPE (type);
3701 pair->decl = NULL_TREE;
3702 pair->offset = offset + i * TREE_INT_CST_LOW (elsz);
3712 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
3713 if (TREE_CODE (field) == FIELD_DECL)
3719 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3720 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3723 if (!var_can_have_subvars (field))
3725 else if (!(pushed = push_fields_onto_fieldstack
3726 (TREE_TYPE (field), fieldstack,
3727 offset + bitpos_of_field (field), has_union))
3728 && DECL_SIZE (field)
3729 && !integer_zerop (DECL_SIZE (field)))
3730 /* Empty structures may have actual size, like in C++. So
3731 see if we didn't push any subfields and the size is
3732 nonzero, push the field onto the stack */
3739 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3740 pair->type = TREE_TYPE (field);
3741 pair->size = DECL_SIZE (field);
3743 pair->offset = offset + bitpos_of_field (field);
3753 /* Create a constraint from ANYTHING variable to VI. */
3755 make_constraint_from_anything (varinfo_t vi)
3757 struct constraint_expr lhs, rhs;
3763 rhs.var = anything_id;
3765 rhs.type = ADDRESSOF;
3766 process_constraint (new_constraint (lhs, rhs));
3769 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3770 if it is a varargs function. */
3773 count_num_arguments (tree decl, bool *is_varargs)
3778 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
3782 if (TREE_VALUE (t) == void_type_node)
3792 /* Creation function node for DECL, using NAME, and return the index
3793 of the variable we've created for the function. */
3796 create_function_info_for (tree decl, const char *name)
3798 unsigned int index = VEC_length (varinfo_t, varmap);
3802 bool is_varargs = false;
3804 /* Create the variable info. */
3806 vi = new_var_info (decl, index, name);
3811 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3812 insert_vi_for_tree (vi->decl, vi);
3813 VEC_safe_push (varinfo_t, heap, varmap, vi);
3817 /* If it's varargs, we don't know how many arguments it has, so we
3824 vi->is_unknown_size_var = true;
3829 arg = DECL_ARGUMENTS (decl);
3831 /* Set up variables for each argument. */
3832 for (i = 1; i < vi->fullsize; i++)
3835 const char *newname;
3837 unsigned int newindex;
3838 tree argdecl = decl;
3843 newindex = VEC_length (varinfo_t, varmap);
3844 asprintf (&tempname, "%s.arg%d", name, i-1);
3845 newname = ggc_strdup (tempname);
3848 argvi = new_var_info (argdecl, newindex, newname);
3849 argvi->decl = argdecl;
3850 VEC_safe_push (varinfo_t, heap, varmap, argvi);
3853 argvi->fullsize = vi->fullsize;
3854 argvi->has_union = false;
3855 insert_into_field_list_sorted (vi, argvi);
3856 stats.total_vars ++;
3859 insert_vi_for_tree (arg, argvi);
3860 arg = TREE_CHAIN (arg);
3864 /* Create a variable for the return var. */
3865 if (DECL_RESULT (decl) != NULL
3866 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
3869 const char *newname;
3871 unsigned int newindex;
3872 tree resultdecl = decl;
3876 if (DECL_RESULT (decl))
3877 resultdecl = DECL_RESULT (decl);
3879 newindex = VEC_length (varinfo_t, varmap);
3880 asprintf (&tempname, "%s.result", name);
3881 newname = ggc_strdup (tempname);
3884 resultvi = new_var_info (resultdecl, newindex, newname);
3885 resultvi->decl = resultdecl;
3886 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
3887 resultvi->offset = i;
3889 resultvi->fullsize = vi->fullsize;
3890 resultvi->has_union = false;
3891 insert_into_field_list_sorted (vi, resultvi);
3892 stats.total_vars ++;
3893 if (DECL_RESULT (decl))
3894 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
3900 /* Return true if FIELDSTACK contains fields that overlap.
3901 FIELDSTACK is assumed to be sorted by offset. */
3904 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
3906 fieldoff_s *fo = NULL;
3908 HOST_WIDE_INT lastoffset = -1;
3910 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3912 if (fo->offset == lastoffset)
3914 lastoffset = fo->offset;
3919 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
3920 This will also create any varinfo structures necessary for fields
3924 create_variable_info_for (tree decl, const char *name)
3926 unsigned int index = VEC_length (varinfo_t, varmap);
3928 tree decltype = TREE_TYPE (decl);
3929 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
3930 bool notokay = false;
3932 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
3933 VEC (fieldoff_s,heap) *fieldstack = NULL;
3935 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
3936 return create_function_info_for (decl, name);
3938 hasunion = TREE_CODE (decltype) == UNION_TYPE
3939 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
3940 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
3942 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
3945 VEC_free (fieldoff_s, heap, fieldstack);
3951 /* If the variable doesn't have subvars, we may end up needing to
3952 sort the field list and create fake variables for all the
3954 vi = new_var_info (decl, index, name);
3957 vi->has_union = hasunion;
3959 || TREE_CODE (declsize) != INTEGER_CST
3960 || TREE_CODE (decltype) == UNION_TYPE
3961 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
3963 vi->is_unknown_size_var = true;
3969 vi->fullsize = TREE_INT_CST_LOW (declsize);
3970 vi->size = vi->fullsize;
3973 insert_vi_for_tree (vi->decl, vi);
3974 VEC_safe_push (varinfo_t, heap, varmap, vi);
3975 if (is_global && (!flag_whole_program || !in_ipa_mode))
3976 make_constraint_from_anything (vi);
3979 if (use_field_sensitive
3981 && !vi->is_unknown_size_var
3982 && var_can_have_subvars (decl)
3983 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
3985 unsigned int newindex = VEC_length (varinfo_t, varmap);
3986 fieldoff_s *fo = NULL;
3989 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3992 || TREE_CODE (fo->size) != INTEGER_CST
4000 /* We can't sort them if we have a field with a variable sized type,
4001 which will make notokay = true. In that case, we are going to return
4002 without creating varinfos for the fields anyway, so sorting them is a
4006 sort_fieldstack (fieldstack);
4007 /* Due to some C++ FE issues, like PR 22488, we might end up
4008 what appear to be overlapping fields even though they,
4009 in reality, do not overlap. Until the C++ FE is fixed,
4010 we will simply disable field-sensitivity for these cases. */
4011 notokay = check_for_overlaps (fieldstack);
4015 if (VEC_length (fieldoff_s, fieldstack) != 0)
4016 fo = VEC_index (fieldoff_s, fieldstack, 0);
4018 if (fo == NULL || notokay)
4020 vi->is_unknown_size_var = 1;
4023 VEC_free (fieldoff_s, heap, fieldstack);
4027 vi->size = TREE_INT_CST_LOW (fo->size);
4028 vi->offset = fo->offset;
4029 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4030 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4034 const char *newname = "NULL";
4037 newindex = VEC_length (varinfo_t, varmap);
4041 asprintf (&tempname, "%s.%s",
4042 vi->name, alias_get_name (fo->decl));
4044 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC,
4045 vi->name, fo->offset);
4046 newname = ggc_strdup (tempname);
4049 newvi = new_var_info (decl, newindex, newname);
4050 newvi->offset = fo->offset;
4051 newvi->size = TREE_INT_CST_LOW (fo->size);
4052 newvi->fullsize = vi->fullsize;
4053 insert_into_field_list (vi, newvi);
4054 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4055 if (is_global && (!flag_whole_program || !in_ipa_mode))
4056 make_constraint_from_anything (newvi);
4060 VEC_free (fieldoff_s, heap, fieldstack);
4065 /* Print out the points-to solution for VAR to FILE. */
4068 dump_solution_for_var (FILE *file, unsigned int var)
4070 varinfo_t vi = get_varinfo (var);
4074 if (find (var) != var)
4076 varinfo_t vipt = get_varinfo (find (var));
4077 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4081 fprintf (file, "%s = { ", vi->name);
4082 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4084 fprintf (file, "%s ", get_varinfo (i)->name);
4086 fprintf (file, "}\n");
4090 /* Print the points-to solution for VAR to stdout. */
4093 debug_solution_for_var (unsigned int var)
4095 dump_solution_for_var (stdout, var);
4098 /* Create varinfo structures for all of the variables in the
4099 function for intraprocedural mode. */
4102 intra_create_variable_infos (void)
4105 struct constraint_expr lhs, rhs;
4107 /* For each incoming pointer argument arg, create the constraint ARG
4108 = ANYTHING or a dummy variable if flag_argument_noalias is set. */
4109 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4113 if (!could_have_pointers (t))
4116 /* With flag_argument_noalias greater than two means that the incoming
4117 argument cannot alias anything except for itself so create a HEAP
4119 if (POINTER_TYPE_P (TREE_TYPE (t))
4120 && flag_argument_noalias > 2)
4123 tree heapvar = heapvar_lookup (t);
4127 lhs.var = get_vi_for_tree (t)->id;
4129 if (heapvar == NULL_TREE)
4131 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4133 get_var_ann (heapvar)->is_heapvar = 1;
4134 DECL_EXTERNAL (heapvar) = 1;
4135 if (gimple_referenced_vars (cfun))
4136 add_referenced_var (heapvar);
4137 heapvar_insert (t, heapvar);
4139 vi = get_vi_for_tree (heapvar);
4140 vi->is_artificial_var = 1;
4141 vi->is_heap_var = 1;
4143 rhs.type = ADDRESSOF;
4145 for (p = get_varinfo (lhs.var); p; p = p->next)
4147 struct constraint_expr temp = lhs;
4149 process_constraint (new_constraint (temp, rhs));
4154 varinfo_t arg_vi = get_vi_for_tree (t);
4156 for (p = arg_vi; p; p = p->next)
4157 make_constraint_from_anything (p);
4162 /* Set bits in INTO corresponding to the variable uids in solution set
4163 FROM, which came from variable PTR.
4164 For variables that are actually dereferenced, we also use type
4165 based alias analysis to prune the points-to sets. */
4168 set_uids_in_ptset (tree ptr, bitmap into, bitmap from)
4173 HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr));
4175 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4177 varinfo_t vi = get_varinfo (i);
4178 unsigned HOST_WIDE_INT var_alias_set;
4180 /* The only artificial variables that are allowed in a may-alias
4181 set are heap variables. */
4182 if (vi->is_artificial_var && !vi->is_heap_var)
4185 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
4187 /* Variables containing unions may need to be converted to
4188 their SFT's, because SFT's can have unions and we cannot. */
4189 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
4190 bitmap_set_bit (into, DECL_UID (sv->var));
4192 else if (TREE_CODE (vi->decl) == VAR_DECL
4193 || TREE_CODE (vi->decl) == PARM_DECL)
4195 if (var_can_have_subvars (vi->decl)
4196 && get_subvars_for_var (vi->decl))
4198 /* If VI->DECL is an aggregate for which we created
4199 SFTs, add the SFT corresponding to VI->OFFSET. */
4200 tree sft = get_subvar_at (vi->decl, vi->offset);
4203 var_alias_set = get_alias_set (sft);
4204 if (!vi->directly_dereferenced
4205 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
4206 bitmap_set_bit (into, DECL_UID (sft));
4211 /* Otherwise, just add VI->DECL to the alias set.
4212 Don't type prune artificial vars. */
4213 if (vi->is_artificial_var)
4214 bitmap_set_bit (into, DECL_UID (vi->decl));
4217 var_alias_set = get_alias_set (vi->decl);
4218 if (!vi->directly_dereferenced
4219 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
4220 bitmap_set_bit (into, DECL_UID (vi->decl));
4228 static bool have_alias_info = false;
4230 /* The list of SMT's that are in use by our pointer variables. This
4231 is the set of SMT's for all pointers that can point to anything. */
4232 static bitmap used_smts;
4234 /* Due to the ordering of points-to set calculation and SMT
4235 calculation being a bit co-dependent, we can't just calculate SMT
4236 used info whenever we want, we have to calculate it around the time
4237 that find_what_p_points_to is called. */
4239 /* Mark which SMT's are in use by points-to anything variables. */
4242 set_used_smts (void)
4246 used_smts = BITMAP_ALLOC (&pta_obstack);
4248 for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); i++)
4250 tree var = vi->decl;
4253 struct ptr_info_def *pi = NULL;
4255 /* For parm decls, the pointer info may be under the default
4257 if (TREE_CODE (vi->decl) == PARM_DECL
4258 && gimple_default_def (cfun, var))
4259 pi = SSA_NAME_PTR_INFO (gimple_default_def (cfun, var));
4260 else if (TREE_CODE (var) == SSA_NAME)
4261 pi = SSA_NAME_PTR_INFO (var);
4263 /* Skip the special variables and those without their own
4265 if (vi->is_special_var || find (vi->id) != vi->id
4267 || (pi && !pi->is_dereferenced)
4268 || (TREE_CODE (var) == VAR_DECL && !may_be_aliased (var))
4269 || !POINTER_TYPE_P (TREE_TYPE (var)))
4272 if (TREE_CODE (var) == SSA_NAME)
4273 var = SSA_NAME_VAR (var);
4279 smt = va->symbol_mem_tag;
4280 if (smt && bitmap_bit_p (vi->solution, anything_id))
4281 bitmap_set_bit (used_smts, DECL_UID (smt));
4285 /* Merge the necessary SMT's into the solution set for VI, which is
4286 P's varinfo. This involves merging all SMT's that are a subset of
4287 the SMT necessary for P. */
4290 merge_smts_into (tree p, varinfo_t vi)
4298 if (TREE_CODE (p) == SSA_NAME)
4299 var = SSA_NAME_VAR (p);
4301 smt = var_ann (var)->symbol_mem_tag;
4304 HOST_WIDE_INT smtset = get_alias_set (TREE_TYPE (smt));
4306 /* Need to set the SMT subsets first before this
4307 will work properly. */
4308 bitmap_set_bit (vi->finished_solution, DECL_UID (smt));
4309 EXECUTE_IF_SET_IN_BITMAP (used_smts, 0, i, bi)
4311 tree newsmt = referenced_var (i);
4312 tree newsmttype = TREE_TYPE (newsmt);
4314 if (alias_set_subset_of (get_alias_set (newsmttype),
4316 bitmap_set_bit (vi->finished_solution, i);
4319 aliases = MTAG_ALIASES (smt);
4321 bitmap_ior_into (vi->finished_solution, aliases);
4325 /* Given a pointer variable P, fill in its points-to set, or return
4327 Rather than return false for variables that point-to anything, we
4328 instead find the corresponding SMT, and merge in it's aliases. In
4329 addition to these aliases, we also set the bits for the SMT's
4330 themselves and their subsets, as SMT's are still in use by
4331 non-SSA_NAME's, and pruning may eliminate every one of their
4332 aliases. In such a case, if we did not include the right set of
4333 SMT's in the points-to set of the variable, we'd end up with
4334 statements that do not conflict but should. */
4337 find_what_p_points_to (tree p)
4342 if (!have_alias_info)
4345 /* For parameters, get at the points-to set for the actual parm
4347 if (TREE_CODE (p) == SSA_NAME
4348 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4349 && SSA_NAME_IS_DEFAULT_DEF (p))
4350 lookup_p = SSA_NAME_VAR (p);
4352 vi = lookup_vi_for_tree (lookup_p);
4355 if (vi->is_artificial_var)
4358 /* See if this is a field or a structure. */
4359 if (vi->size != vi->fullsize)
4361 /* Nothing currently asks about structure fields directly,
4362 but when they do, we need code here to hand back the
4364 if (!var_can_have_subvars (vi->decl)
4365 || get_subvars_for_var (vi->decl) == NULL)
4370 struct ptr_info_def *pi = get_ptr_info (p);
4373 bool was_pt_anything = false;
4375 if (!pi->is_dereferenced)
4378 /* This variable may have been collapsed, let's get the real
4380 vi = get_varinfo (find (vi->id));
4382 /* Translate artificial variables into SSA_NAME_PTR_INFO
4384 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4386 varinfo_t vi = get_varinfo (i);
4388 if (vi->is_artificial_var)
4390 /* FIXME. READONLY should be handled better so that
4391 flow insensitive aliasing can disregard writable
4393 if (vi->id == nothing_id)
4395 else if (vi->id == anything_id)
4396 was_pt_anything = 1;
4397 else if (vi->id == readonly_id)
4398 was_pt_anything = 1;
4399 else if (vi->id == integer_id)
4400 was_pt_anything = 1;
4401 else if (vi->is_heap_var)
4402 pi->pt_global_mem = 1;
4406 /* Share the final set of variables between the SSA_NAME
4407 pointer infos for collapsed nodes that are collapsed to
4408 non-special variables. This is because special vars have
4409 no real types associated with them, so while we know the
4410 pointers are equivalent to them, we need to generate the
4411 solution separately since it will include SMT's from the
4412 original non-collapsed variable. */
4413 if (!vi->is_special_var && vi->finished_solution)
4415 pi->pt_vars = vi->finished_solution;
4419 vi->finished_solution = BITMAP_GGC_ALLOC ();
4420 stats.points_to_sets_created++;
4422 /* Instead of using pt_anything, we instead merge in the SMT
4423 aliases for the underlying SMT. */
4424 if (was_pt_anything)
4426 merge_smts_into (p, vi);
4427 pi->pt_global_mem = 1;
4430 set_uids_in_ptset (vi->decl, vi->finished_solution, vi->solution);
4431 pi->pt_vars = vi->finished_solution;
4434 if (bitmap_empty_p (pi->pt_vars))
4446 /* Dump points-to information to OUTFILE. */
4449 dump_sa_points_to_info (FILE *outfile)
4453 fprintf (outfile, "\nPoints-to sets\n\n");
4455 if (dump_flags & TDF_STATS)
4457 fprintf (outfile, "Stats:\n");
4458 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4459 fprintf (outfile, "Non-pointer vars: %d\n",
4460 stats.nonpointer_vars);
4461 fprintf (outfile, "Statically unified vars: %d\n",
4462 stats.unified_vars_static);
4463 fprintf (outfile, "Dynamically unified vars: %d\n",
4464 stats.unified_vars_dynamic);
4465 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4466 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4467 fprintf (outfile, "Number of implicit edges: %d\n",
4468 stats.num_implicit_edges);
4471 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4472 dump_solution_for_var (outfile, i);
4476 /* Debug points-to information to stderr. */
4479 debug_sa_points_to_info (void)
4481 dump_sa_points_to_info (stderr);
4485 /* Initialize the always-existing constraint variables for NULL
4486 ANYTHING, READONLY, and INTEGER */
4489 init_base_vars (void)
4491 struct constraint_expr lhs, rhs;
4493 /* Create the NULL variable, used to represent that a variable points
4495 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4496 var_nothing = new_var_info (nothing_tree, 0, "NULL");
4497 insert_vi_for_tree (nothing_tree, var_nothing);
4498 var_nothing->is_artificial_var = 1;
4499 var_nothing->offset = 0;
4500 var_nothing->size = ~0;
4501 var_nothing->fullsize = ~0;
4502 var_nothing->is_special_var = 1;
4504 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
4506 /* Create the ANYTHING variable, used to represent that a variable
4507 points to some unknown piece of memory. */
4508 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4509 var_anything = new_var_info (anything_tree, 1, "ANYTHING");
4510 insert_vi_for_tree (anything_tree, var_anything);
4511 var_anything->is_artificial_var = 1;
4512 var_anything->size = ~0;
4513 var_anything->offset = 0;
4514 var_anything->next = NULL;
4515 var_anything->fullsize = ~0;
4516 var_anything->is_special_var = 1;
4519 /* Anything points to anything. This makes deref constraints just
4520 work in the presence of linked list and other p = *p type loops,
4521 by saying that *ANYTHING = ANYTHING. */
4522 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
4524 lhs.var = anything_id;
4526 rhs.type = ADDRESSOF;
4527 rhs.var = anything_id;
4530 /* This specifically does not use process_constraint because
4531 process_constraint ignores all anything = anything constraints, since all
4532 but this one are redundant. */
4533 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
4535 /* Create the READONLY variable, used to represent that a variable
4536 points to readonly memory. */
4537 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4538 var_readonly = new_var_info (readonly_tree, 2, "READONLY");
4539 var_readonly->is_artificial_var = 1;
4540 var_readonly->offset = 0;
4541 var_readonly->size = ~0;
4542 var_readonly->fullsize = ~0;
4543 var_readonly->next = NULL;
4544 var_readonly->is_special_var = 1;
4545 insert_vi_for_tree (readonly_tree, var_readonly);
4547 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4549 /* readonly memory points to anything, in order to make deref
4550 easier. In reality, it points to anything the particular
4551 readonly variable can point to, but we don't track this
4554 lhs.var = readonly_id;
4556 rhs.type = ADDRESSOF;
4557 rhs.var = anything_id;
4560 process_constraint (new_constraint (lhs, rhs));
4562 /* Create the INTEGER variable, used to represent that a variable points
4564 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4565 var_integer = new_var_info (integer_tree, 3, "INTEGER");
4566 insert_vi_for_tree (integer_tree, var_integer);
4567 var_integer->is_artificial_var = 1;
4568 var_integer->size = ~0;
4569 var_integer->fullsize = ~0;
4570 var_integer->offset = 0;
4571 var_integer->next = NULL;
4572 var_integer->is_special_var = 1;
4574 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
4576 /* INTEGER = ANYTHING, because we don't know where a dereference of
4577 a random integer will point to. */
4579 lhs.var = integer_id;
4581 rhs.type = ADDRESSOF;
4582 rhs.var = anything_id;
4584 process_constraint (new_constraint (lhs, rhs));
4587 /* Initialize things necessary to perform PTA */
4590 init_alias_vars (void)
4592 bitmap_obstack_initialize (&pta_obstack);
4593 bitmap_obstack_initialize (&oldpta_obstack);
4594 bitmap_obstack_initialize (&predbitmap_obstack);
4596 constraint_pool = create_alloc_pool ("Constraint pool",
4597 sizeof (struct constraint), 30);
4598 variable_info_pool = create_alloc_pool ("Variable info pool",
4599 sizeof (struct variable_info), 30);
4600 constraints = VEC_alloc (constraint_t, heap, 8);
4601 varmap = VEC_alloc (varinfo_t, heap, 8);
4602 vi_for_tree = pointer_map_create ();
4604 memset (&stats, 0, sizeof (stats));
4609 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
4610 predecessor edges. */
4613 remove_preds_and_fake_succs (constraint_graph_t graph)
4617 /* Clear the implicit ref and address nodes from the successor
4619 for (i = 0; i < FIRST_REF_NODE; i++)
4621 if (graph->succs[i])
4622 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
4623 FIRST_REF_NODE * 2);
4626 /* Free the successor list for the non-ref nodes. */
4627 for (i = FIRST_REF_NODE; i < graph->size; i++)
4629 if (graph->succs[i])
4630 BITMAP_FREE (graph->succs[i]);
4633 /* Now reallocate the size of the successor list as, and blow away
4634 the predecessor bitmaps. */
4635 graph->size = VEC_length (varinfo_t, varmap);
4636 graph->succs = xrealloc (graph->succs, graph->size * sizeof (bitmap));
4638 free (graph->implicit_preds);
4639 graph->implicit_preds = NULL;
4640 free (graph->preds);
4641 graph->preds = NULL;
4642 bitmap_obstack_release (&predbitmap_obstack);
4645 /* Create points-to sets for the current function. See the comments
4646 at the start of the file for an algorithmic overview. */
4649 compute_points_to_sets (struct alias_info *ai)
4651 struct scc_info *si;
4654 timevar_push (TV_TREE_PTA);
4657 init_alias_heapvars ();
4659 intra_create_variable_infos ();
4661 /* Now walk all statements and derive aliases. */
4664 block_stmt_iterator bsi;
4667 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4669 if (is_gimple_reg (PHI_RESULT (phi)))
4671 find_func_aliases (phi);
4673 /* Update various related attributes like escaped
4674 addresses, pointer dereferences for loads and stores.
4675 This is used when creating name tags and alias
4677 update_alias_info (phi, ai);
4681 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4683 tree stmt = bsi_stmt (bsi);
4685 find_func_aliases (stmt);
4687 /* Update various related attributes like escaped
4688 addresses, pointer dereferences for loads and stores.
4689 This is used when creating name tags and alias
4691 update_alias_info (stmt, ai);
4698 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4699 dump_constraints (dump_file);
4704 "\nCollapsing static cycles and doing variable "
4706 build_pred_graph ();
4707 si = perform_var_substitution (graph);
4708 move_complex_constraints (graph, si);
4709 free_var_substitution_info (si);
4711 build_succ_graph ();
4712 find_indirect_cycles (graph);
4714 /* Implicit nodes and predecessors are no longer necessary at this
4716 remove_preds_and_fake_succs (graph);
4719 fprintf (dump_file, "\nSolving graph:\n");
4721 solve_graph (graph);
4724 dump_sa_points_to_info (dump_file);
4726 have_alias_info = true;
4728 timevar_pop (TV_TREE_PTA);
4732 /* Delete created points-to sets. */
4735 delete_points_to_sets (void)
4740 if (dump_file && (dump_flags & TDF_STATS))
4741 fprintf (dump_file, "Points to sets created:%d\n",
4742 stats.points_to_sets_created);
4744 pointer_map_destroy (vi_for_tree);
4745 bitmap_obstack_release (&pta_obstack);
4746 VEC_free (constraint_t, heap, constraints);
4748 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
4749 VEC_free (constraint_t, heap, graph->complex[i]);
4752 free (graph->succs);
4753 free (graph->indirect_cycles);
4756 VEC_free (varinfo_t, heap, varmap);
4757 free_alloc_pool (variable_info_pool);
4758 free_alloc_pool (constraint_pool);
4759 have_alias_info = false;
4762 /* Return true if we should execute IPA PTA. */
4766 return (flag_unit_at_a_time != 0
4768 /* Don't bother doing anything if the program has errors. */
4769 && !(errorcount || sorrycount));
4772 /* Execute the driver for IPA PTA. */
4774 ipa_pta_execute (void)
4776 struct cgraph_node *node;
4777 struct scc_info *si;
4780 init_alias_heapvars ();
4783 for (node = cgraph_nodes; node; node = node->next)
4785 if (!node->analyzed || cgraph_is_master_clone (node))
4789 varid = create_function_info_for (node->decl,
4790 cgraph_node_name (node));
4791 if (node->local.externally_visible)
4793 varinfo_t fi = get_varinfo (varid);
4794 for (; fi; fi = fi->next)
4795 make_constraint_from_anything (fi);
4799 for (node = cgraph_nodes; node; node = node->next)
4801 if (node->analyzed && cgraph_is_master_clone (node))
4803 struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
4805 tree old_func_decl = current_function_decl;
4808 "Generating constraints for %s\n",
4809 cgraph_node_name (node));
4811 current_function_decl = node->decl;
4813 FOR_EACH_BB_FN (bb, cfun)
4815 block_stmt_iterator bsi;
4818 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4820 if (is_gimple_reg (PHI_RESULT (phi)))
4822 find_func_aliases (phi);
4826 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4828 tree stmt = bsi_stmt (bsi);
4829 find_func_aliases (stmt);
4832 current_function_decl = old_func_decl;
4837 /* Make point to anything. */
4845 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
4846 dump_constraints (dump_file);
4851 "\nCollapsing static cycles and doing variable "
4854 build_pred_graph ();
4855 si = perform_var_substitution (graph);
4856 move_complex_constraints (graph, si);
4857 free_var_substitution_info (si);
4859 build_succ_graph ();
4860 find_indirect_cycles (graph);
4862 /* Implicit nodes and predecessors are no longer necessary at this
4864 remove_preds_and_fake_succs (graph);
4867 fprintf (dump_file, "\nSolving graph:\n");
4869 solve_graph (graph);
4872 dump_sa_points_to_info (dump_file);
4875 delete_alias_heapvars ();
4876 delete_points_to_sets ();
4880 struct tree_opt_pass pass_ipa_pta =
4883 gate_ipa_pta, /* gate */
4884 ipa_pta_execute, /* execute */
4887 0, /* static_pass_number */
4888 TV_IPA_PTA, /* tv_id */
4889 0, /* properties_required */
4890 0, /* properties_provided */
4891 0, /* properties_destroyed */
4892 0, /* todo_flags_start */
4893 0, /* todo_flags_finish */
4897 /* Initialize the heapvar for statement mapping. */
4899 init_alias_heapvars (void)
4901 if (!heapvar_for_stmt)
4902 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
4907 delete_alias_heapvars (void)
4909 htab_delete (heapvar_for_stmt);
4910 heapvar_for_stmt = NULL;
4914 #include "gt-tree-ssa-structalias.h"