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 3 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; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
35 #include "diagnostic.h"
38 #include "tree-flow.h"
39 #include "tree-inline.h"
42 #include "tree-gimple.h"
46 #include "tree-pass.h"
48 #include "alloc-pool.h"
49 #include "splay-tree.h"
51 #include "tree-ssa-structalias.h"
54 #include "pointer-set.h"
56 /* The idea behind this analyzer is to generate set constraints from the
57 program, then solve the resulting constraints in order to generate the
60 Set constraints are a way of modeling program analysis problems that
61 involve sets. They consist of an inclusion constraint language,
62 describing the variables (each variable is a set) and operations that
63 are involved on the variables, and a set of rules that derive facts
64 from these operations. To solve a system of set constraints, you derive
65 all possible facts under the rules, which gives you the correct sets
68 See "Efficient Field-sensitive pointer analysis for C" by "David
69 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
70 http://citeseer.ist.psu.edu/pearce04efficient.html
72 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
73 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
74 http://citeseer.ist.psu.edu/heintze01ultrafast.html
76 There are three types of real constraint expressions, DEREF,
77 ADDRESSOF, and SCALAR. Each constraint expression consists
78 of a constraint type, a variable, and an offset.
80 SCALAR is a constraint expression type used to represent x, whether
81 it appears on the LHS or the RHS of a statement.
82 DEREF is a constraint expression type used to represent *x, whether
83 it appears on the LHS or the RHS of a statement.
84 ADDRESSOF is a constraint expression used to represent &x, whether
85 it appears on the LHS or the RHS of a statement.
87 Each pointer variable in the program is assigned an integer id, and
88 each field of a structure variable is assigned an integer id as well.
90 Structure variables are linked to their list of fields through a "next
91 field" in each variable that points to the next field in offset
93 Each variable for a structure field has
95 1. "size", that tells the size in bits of that field.
96 2. "fullsize, that tells the size in bits of the entire structure.
97 3. "offset", that tells the offset in bits from the beginning of the
98 structure to this field.
110 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
111 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
112 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
115 In order to solve the system of set constraints, the following is
118 1. Each constraint variable x has a solution set associated with it,
121 2. Constraints are separated into direct, copy, and complex.
122 Direct constraints are ADDRESSOF constraints that require no extra
123 processing, such as P = &Q
124 Copy constraints are those of the form P = Q.
125 Complex constraints are all the constraints involving dereferences
126 and offsets (including offsetted copies).
128 3. All direct constraints of the form P = &Q are processed, such
129 that Q is added to Sol(P)
131 4. All complex constraints for a given constraint variable are stored in a
132 linked list attached to that variable's node.
134 5. A directed graph is built out of the copy constraints. Each
135 constraint variable is a node in the graph, and an edge from
136 Q to P is added for each copy constraint of the form P = Q
138 6. The graph is then walked, and solution sets are
139 propagated along the copy edges, such that an edge from Q to P
140 causes Sol(P) <- Sol(P) union Sol(Q).
142 7. As we visit each node, all complex constraints associated with
143 that node are processed by adding appropriate copy edges to the graph, or the
144 appropriate variables to the solution set.
146 8. The process of walking the graph is iterated until no solution
149 Prior to walking the graph in steps 6 and 7, We perform static
150 cycle elimination on the constraint graph, as well
151 as off-line variable substitution.
153 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
154 on and turned into anything), but isn't. You can just see what offset
155 inside the pointed-to struct it's going to access.
157 TODO: Constant bounded arrays can be handled as if they were structs of the
158 same number of elements.
160 TODO: Modeling heap and incoming pointers becomes much better if we
161 add fields to them as we discover them, which we could do.
163 TODO: We could handle unions, but to be honest, it's probably not
164 worth the pain or slowdown. */
166 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
167 htab_t heapvar_for_stmt;
169 static bool use_field_sensitive = true;
170 static int in_ipa_mode = 0;
172 /* Used for predecessor bitmaps. */
173 static bitmap_obstack predbitmap_obstack;
175 /* Used for points-to sets. */
176 static bitmap_obstack pta_obstack;
178 /* Used for oldsolution members of variables. */
179 static bitmap_obstack oldpta_obstack;
181 /* Used for per-solver-iteration bitmaps. */
182 static bitmap_obstack iteration_obstack;
184 static unsigned int create_variable_info_for (tree, const char *);
185 typedef struct constraint_graph *constraint_graph_t;
186 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
188 DEF_VEC_P(constraint_t);
189 DEF_VEC_ALLOC_P(constraint_t,heap);
191 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
193 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
195 static struct constraint_stats
197 unsigned int total_vars;
198 unsigned int nonpointer_vars;
199 unsigned int unified_vars_static;
200 unsigned int unified_vars_dynamic;
201 unsigned int iterations;
202 unsigned int num_edges;
203 unsigned int num_implicit_edges;
204 unsigned int points_to_sets_created;
209 /* ID of this variable */
212 /* Name of this variable */
215 /* Tree that this variable is associated with. */
218 /* Offset of this variable, in bits, from the base variable */
219 unsigned HOST_WIDE_INT offset;
221 /* Size of the variable, in bits. */
222 unsigned HOST_WIDE_INT size;
224 /* Full size of the base variable, in bits. */
225 unsigned HOST_WIDE_INT fullsize;
227 /* A link to the variable for the next field in this structure. */
228 struct variable_info *next;
230 /* True if the variable is directly the target of a dereference.
231 This is used to track which variables are *actually* dereferenced
232 so we can prune their points to listed. */
233 unsigned int directly_dereferenced:1;
235 /* True if this is a variable created by the constraint analysis, such as
236 heap variables and constraints we had to break up. */
237 unsigned int is_artificial_var:1;
239 /* True if this is a special variable whose solution set should not be
241 unsigned int is_special_var:1;
243 /* True for variables whose size is not known or variable. */
244 unsigned int is_unknown_size_var:1;
246 /* True for variables that have unions somewhere in them. */
247 unsigned int has_union:1;
249 /* True if this is a heap variable. */
250 unsigned int is_heap_var:1;
252 /* True if we may not use TBAA to prune references to this
253 variable. This is used for C++ placement new. */
254 unsigned int no_tbaa_pruning : 1;
256 /* Points-to set for this variable. */
259 /* Old points-to set for this variable. */
262 /* Variable ids represented by this node. */
265 /* Variable id this was collapsed to due to type unsafety. This
266 should be unused completely after build_succ_graph, or something
268 struct variable_info *collapsed_to;
270 typedef struct variable_info *varinfo_t;
272 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
274 /* Pool of variable info structures. */
275 static alloc_pool variable_info_pool;
277 DEF_VEC_P(varinfo_t);
279 DEF_VEC_ALLOC_P(varinfo_t, heap);
281 /* Table of variable info structures for constraint variables.
282 Indexed directly by variable info id. */
283 static VEC(varinfo_t,heap) *varmap;
285 /* Return the varmap element N */
287 static inline varinfo_t
288 get_varinfo (unsigned int n)
290 return VEC_index (varinfo_t, varmap, n);
293 /* Return the varmap element N, following the collapsed_to link. */
295 static inline varinfo_t
296 get_varinfo_fc (unsigned int n)
298 varinfo_t v = VEC_index (varinfo_t, varmap, n);
301 return v->collapsed_to;
305 /* Variable that represents the unknown pointer. */
306 static varinfo_t var_anything;
307 static tree anything_tree;
308 static unsigned int anything_id;
310 /* Variable that represents the NULL pointer. */
311 static varinfo_t var_nothing;
312 static tree nothing_tree;
313 static unsigned int nothing_id;
315 /* Variable that represents read only memory. */
316 static varinfo_t var_readonly;
317 static tree readonly_tree;
318 static unsigned int readonly_id;
320 /* Variable that represents integers. This is used for when people do things
322 static varinfo_t var_integer;
323 static tree integer_tree;
324 static unsigned int integer_id;
326 /* Lookup a heap var for FROM, and return it if we find one. */
329 heapvar_lookup (tree from)
331 struct tree_map *h, in;
334 h = (struct tree_map *) htab_find_with_hash (heapvar_for_stmt, &in,
335 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_NEW (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 = (varinfo_t) pool_alloc (variable_info_pool);
370 ret->directly_dereferenced = false;
371 ret->is_artificial_var = false;
372 ret->is_heap_var = false;
373 ret->is_special_var = false;
374 ret->is_unknown_size_var = false;
375 ret->has_union = false;
377 if (TREE_CODE (var) == SSA_NAME)
378 var = SSA_NAME_VAR (var);
379 ret->no_tbaa_pruning = (DECL_P (var)
380 && POINTER_TYPE_P (TREE_TYPE (var))
381 && DECL_NO_TBAA_P (var));
382 ret->solution = BITMAP_ALLOC (&pta_obstack);
383 ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
385 ret->collapsed_to = NULL;
389 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
391 /* An expression that appears in a constraint. */
393 struct constraint_expr
395 /* Constraint type. */
396 constraint_expr_type type;
398 /* Variable we are referring to in the constraint. */
401 /* Offset, in bits, of this constraint from the beginning of
402 variables it ends up referring to.
404 IOW, in a deref constraint, we would deref, get the result set,
405 then add OFFSET to each member. */
406 unsigned HOST_WIDE_INT offset;
409 typedef struct constraint_expr ce_s;
411 DEF_VEC_ALLOC_O(ce_s, heap);
412 static void get_constraint_for (tree, VEC(ce_s, heap) **);
413 static void do_deref (VEC (ce_s, heap) **);
415 /* Our set constraints are made up of two constraint expressions, one
418 As described in the introduction, our set constraints each represent an
419 operation between set valued variables.
423 struct constraint_expr lhs;
424 struct constraint_expr rhs;
427 /* List of constraints that we use to build the constraint graph from. */
429 static VEC(constraint_t,heap) *constraints;
430 static alloc_pool constraint_pool;
434 DEF_VEC_ALLOC_I(int, heap);
436 /* The constraint graph is represented as an array of bitmaps
437 containing successor nodes. */
439 struct constraint_graph
441 /* Size of this graph, which may be different than the number of
442 nodes in the variable map. */
445 /* Explicit successors of each node. */
448 /* Implicit predecessors of each node (Used for variable
450 bitmap *implicit_preds;
452 /* Explicit predecessors of each node (Used for variable substitution). */
455 /* Indirect cycle representatives, or -1 if the node has no indirect
457 int *indirect_cycles;
459 /* Representative node for a node. rep[a] == a unless the node has
463 /* Equivalence class representative for a node. This is used for
464 variable substitution. */
467 /* Label for each node, used during variable substitution. */
470 /* Bitmap of nodes where the bit is set if the node is a direct
471 node. Used for variable substitution. */
472 sbitmap direct_nodes;
474 /* Vector of complex constraints for each graph node. Complex
475 constraints are those involving dereferences or offsets that are
477 VEC(constraint_t,heap) **complex;
480 static constraint_graph_t graph;
482 /* During variable substitution and the offline version of indirect
483 cycle finding, we create nodes to represent dereferences and
484 address taken constraints. These represent where these start and
486 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
487 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
488 #define FIRST_ADDR_NODE (LAST_REF_NODE + 1)
490 /* Return the representative node for NODE, if NODE has been unioned
492 This function performs path compression along the way to finding
493 the representative. */
496 find (unsigned int node)
498 gcc_assert (node < graph->size);
499 if (graph->rep[node] != node)
500 return graph->rep[node] = find (graph->rep[node]);
504 /* Union the TO and FROM nodes to the TO nodes.
505 Note that at some point in the future, we may want to do
506 union-by-rank, in which case we are going to have to return the
507 node we unified to. */
510 unite (unsigned int to, unsigned int from)
512 gcc_assert (to < graph->size && from < graph->size);
513 if (to != from && graph->rep[from] != to)
515 graph->rep[from] = to;
521 /* Create a new constraint consisting of LHS and RHS expressions. */
524 new_constraint (const struct constraint_expr lhs,
525 const struct constraint_expr rhs)
527 constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
533 /* Print out constraint C to FILE. */
536 dump_constraint (FILE *file, constraint_t c)
538 if (c->lhs.type == ADDRESSOF)
540 else if (c->lhs.type == DEREF)
542 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
543 if (c->lhs.offset != 0)
544 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
545 fprintf (file, " = ");
546 if (c->rhs.type == ADDRESSOF)
548 else if (c->rhs.type == DEREF)
550 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
551 if (c->rhs.offset != 0)
552 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
553 fprintf (file, "\n");
556 /* Print out constraint C to stderr. */
559 debug_constraint (constraint_t c)
561 dump_constraint (stderr, c);
564 /* Print out all constraints to FILE */
567 dump_constraints (FILE *file)
571 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
572 dump_constraint (file, c);
575 /* Print out all constraints to stderr. */
578 debug_constraints (void)
580 dump_constraints (stderr);
585 The solver is a simple worklist solver, that works on the following
588 sbitmap changed_nodes = all zeroes;
590 For each node that is not already collapsed:
592 set bit in changed nodes
594 while (changed_count > 0)
596 compute topological ordering for constraint graph
598 find and collapse cycles in the constraint graph (updating
599 changed if necessary)
601 for each node (n) in the graph in topological order:
604 Process each complex constraint associated with the node,
605 updating changed if necessary.
607 For each outgoing edge from n, propagate the solution from n to
608 the destination of the edge, updating changed as necessary.
612 /* Return true if two constraint expressions A and B are equal. */
615 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
617 return a.type == b.type && a.var == b.var && a.offset == b.offset;
620 /* Return true if constraint expression A is less than constraint expression
621 B. This is just arbitrary, but consistent, in order to give them an
625 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
627 if (a.type == b.type)
630 return a.offset < b.offset;
632 return a.var < b.var;
635 return a.type < b.type;
638 /* Return true if constraint A is less than constraint B. This is just
639 arbitrary, but consistent, in order to give them an ordering. */
642 constraint_less (const constraint_t a, const constraint_t b)
644 if (constraint_expr_less (a->lhs, b->lhs))
646 else if (constraint_expr_less (b->lhs, a->lhs))
649 return constraint_expr_less (a->rhs, b->rhs);
652 /* Return true if two constraints A and B are equal. */
655 constraint_equal (struct constraint a, struct constraint b)
657 return constraint_expr_equal (a.lhs, b.lhs)
658 && constraint_expr_equal (a.rhs, b.rhs);
662 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
665 constraint_vec_find (VEC(constraint_t,heap) *vec,
666 struct constraint lookfor)
674 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
675 if (place >= VEC_length (constraint_t, vec))
677 found = VEC_index (constraint_t, vec, place);
678 if (!constraint_equal (*found, lookfor))
683 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
686 constraint_set_union (VEC(constraint_t,heap) **to,
687 VEC(constraint_t,heap) **from)
692 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
694 if (constraint_vec_find (*to, *c) == NULL)
696 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
698 VEC_safe_insert (constraint_t, heap, *to, place, c);
703 /* Take a solution set SET, add OFFSET to each member of the set, and
704 overwrite SET with the result when done. */
707 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
709 bitmap result = BITMAP_ALLOC (&iteration_obstack);
713 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
715 /* If this is a properly sized variable, only add offset if it's
716 less than end. Otherwise, it is globbed to a single
719 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
721 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
722 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
725 bitmap_set_bit (result, v->id);
727 else if (get_varinfo (i)->is_artificial_var
728 || get_varinfo (i)->has_union
729 || get_varinfo (i)->is_unknown_size_var)
731 bitmap_set_bit (result, i);
735 bitmap_copy (set, result);
736 BITMAP_FREE (result);
739 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
743 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
746 return bitmap_ior_into (to, from);
752 tmp = BITMAP_ALLOC (&iteration_obstack);
753 bitmap_copy (tmp, from);
754 solution_set_add (tmp, inc);
755 res = bitmap_ior_into (to, tmp);
761 /* Insert constraint C into the list of complex constraints for graph
765 insert_into_complex (constraint_graph_t graph,
766 unsigned int var, constraint_t c)
768 VEC (constraint_t, heap) *complex = graph->complex[var];
769 unsigned int place = VEC_lower_bound (constraint_t, complex, c,
772 /* Only insert constraints that do not already exist. */
773 if (place >= VEC_length (constraint_t, complex)
774 || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
775 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
779 /* Condense two variable nodes into a single variable node, by moving
780 all associated info from SRC to TO. */
783 merge_node_constraints (constraint_graph_t graph, unsigned int to,
789 gcc_assert (find (from) == to);
791 /* Move all complex constraints from src node into to node */
792 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
794 /* In complex constraints for node src, we may have either
795 a = *src, and *src = a, or an offseted constraint which are
796 always added to the rhs node's constraints. */
798 if (c->rhs.type == DEREF)
800 else if (c->lhs.type == DEREF)
805 constraint_set_union (&graph->complex[to], &graph->complex[from]);
806 VEC_free (constraint_t, heap, graph->complex[from]);
807 graph->complex[from] = NULL;
811 /* Remove edges involving NODE from GRAPH. */
814 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
816 if (graph->succs[node])
817 BITMAP_FREE (graph->succs[node]);
820 /* Merge GRAPH nodes FROM and TO into node TO. */
823 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
826 if (graph->indirect_cycles[from] != -1)
828 /* If we have indirect cycles with the from node, and we have
829 none on the to node, the to node has indirect cycles from the
830 from node now that they are unified.
831 If indirect cycles exist on both, unify the nodes that they
832 are in a cycle with, since we know they are in a cycle with
834 if (graph->indirect_cycles[to] == -1)
836 graph->indirect_cycles[to] = graph->indirect_cycles[from];
840 unsigned int tonode = find (graph->indirect_cycles[to]);
841 unsigned int fromnode = find (graph->indirect_cycles[from]);
843 if (unite (tonode, fromnode))
844 unify_nodes (graph, tonode, fromnode, true);
848 /* Merge all the successor edges. */
849 if (graph->succs[from])
851 if (!graph->succs[to])
852 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
853 bitmap_ior_into (graph->succs[to],
857 clear_edges_for_node (graph, from);
861 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
862 it doesn't exist in the graph already. */
865 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
871 if (!graph->implicit_preds[to])
872 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
874 if (!bitmap_bit_p (graph->implicit_preds[to], from))
876 stats.num_implicit_edges++;
877 bitmap_set_bit (graph->implicit_preds[to], from);
881 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
882 it doesn't exist in the graph already.
883 Return false if the edge already existed, true otherwise. */
886 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
889 if (!graph->preds[to])
890 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
891 if (!bitmap_bit_p (graph->preds[to], from))
892 bitmap_set_bit (graph->preds[to], from);
895 /* Add a graph edge to GRAPH, going from FROM to TO if
896 it doesn't exist in the graph already.
897 Return false if the edge already existed, true otherwise. */
900 add_graph_edge (constraint_graph_t graph, unsigned int to,
911 if (!graph->succs[from])
912 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
913 if (!bitmap_bit_p (graph->succs[from], to))
916 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
918 bitmap_set_bit (graph->succs[from], to);
925 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
928 valid_graph_edge (constraint_graph_t graph, unsigned int src,
931 return (graph->succs[dest]
932 && bitmap_bit_p (graph->succs[dest], src));
935 /* Build the constraint graph, adding only predecessor edges right now. */
938 build_pred_graph (void)
944 graph = XNEW (struct constraint_graph);
945 graph->size = (VEC_length (varinfo_t, varmap)) * 3;
946 graph->succs = XCNEWVEC (bitmap, graph->size);
947 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
948 graph->preds = XCNEWVEC (bitmap, graph->size);
949 graph->indirect_cycles = XNEWVEC (int, VEC_length (varinfo_t, varmap));
950 graph->label = XCNEWVEC (unsigned int, graph->size);
951 graph->rep = XNEWVEC (unsigned int, graph->size);
952 graph->eq_rep = XNEWVEC (int, graph->size);
953 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *,
954 VEC_length (varinfo_t, varmap));
955 graph->direct_nodes = sbitmap_alloc (graph->size);
956 sbitmap_zero (graph->direct_nodes);
958 for (j = 0; j < FIRST_REF_NODE; j++)
960 if (!get_varinfo (j)->is_special_var)
961 SET_BIT (graph->direct_nodes, j);
964 for (j = 0; j < graph->size; j++)
967 graph->eq_rep[j] = -1;
970 for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
971 graph->indirect_cycles[j] = -1;
973 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
975 struct constraint_expr lhs = c->lhs;
976 struct constraint_expr rhs = c->rhs;
977 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
978 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
980 if (lhs.type == DEREF)
983 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
984 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
985 if (rhs.type == ADDRESSOF)
986 RESET_BIT (graph->direct_nodes, rhsvar);
988 else if (rhs.type == DEREF)
991 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
992 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
994 RESET_BIT (graph->direct_nodes, lhsvar);
996 else if (rhs.type == ADDRESSOF)
999 add_pred_graph_edge (graph, lhsvar, FIRST_ADDR_NODE + rhsvar);
1000 /* Implicitly, *x = y */
1001 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1003 RESET_BIT (graph->direct_nodes, rhsvar);
1005 else if (lhsvar > anything_id
1006 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1009 add_pred_graph_edge (graph, lhsvar, rhsvar);
1010 /* Implicitly, *x = *y */
1011 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1012 FIRST_REF_NODE + rhsvar);
1014 else if (lhs.offset != 0 || rhs.offset != 0)
1016 if (rhs.offset != 0)
1017 RESET_BIT (graph->direct_nodes, lhs.var);
1018 if (lhs.offset != 0)
1019 RESET_BIT (graph->direct_nodes, rhs.var);
1024 /* Build the constraint graph, adding successor edges. */
1027 build_succ_graph (void)
1032 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1034 struct constraint_expr lhs;
1035 struct constraint_expr rhs;
1036 unsigned int lhsvar;
1037 unsigned int rhsvar;
1044 lhsvar = find (get_varinfo_fc (lhs.var)->id);
1045 rhsvar = find (get_varinfo_fc (rhs.var)->id);
1047 if (lhs.type == DEREF)
1049 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1050 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1052 else if (rhs.type == DEREF)
1054 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1055 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1057 else if (rhs.type == ADDRESSOF)
1060 gcc_assert (find (get_varinfo_fc (rhs.var)->id)
1061 == get_varinfo_fc (rhs.var)->id);
1062 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1064 else if (lhsvar > anything_id
1065 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1067 add_graph_edge (graph, lhsvar, rhsvar);
1073 /* Changed variables on the last iteration. */
1074 static unsigned int changed_count;
1075 static sbitmap changed;
1077 DEF_VEC_I(unsigned);
1078 DEF_VEC_ALLOC_I(unsigned,heap);
1081 /* Strongly Connected Component visitation info. */
1088 unsigned int *node_mapping;
1090 VEC(unsigned,heap) *scc_stack;
1094 /* Recursive routine to find strongly connected components in GRAPH.
1095 SI is the SCC info to store the information in, and N is the id of current
1096 graph node we are processing.
1098 This is Tarjan's strongly connected component finding algorithm, as
1099 modified by Nuutila to keep only non-root nodes on the stack.
1100 The algorithm can be found in "On finding the strongly connected
1101 connected components in a directed graph" by Esko Nuutila and Eljas
1102 Soisalon-Soininen, in Information Processing Letters volume 49,
1103 number 1, pages 9-14. */
1106 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1110 unsigned int my_dfs;
1112 SET_BIT (si->visited, n);
1113 si->dfs[n] = si->current_index ++;
1114 my_dfs = si->dfs[n];
1116 /* Visit all the successors. */
1117 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1121 if (i > LAST_REF_NODE)
1125 if (TEST_BIT (si->roots, w))
1128 if (!TEST_BIT (si->visited, w))
1129 scc_visit (graph, si, w);
1131 unsigned int t = find (w);
1132 unsigned int nnode = find (n);
1133 gcc_assert (nnode == n);
1135 if (si->dfs[t] < si->dfs[nnode])
1136 si->dfs[n] = si->dfs[t];
1140 /* See if any components have been identified. */
1141 if (si->dfs[n] == my_dfs)
1143 if (VEC_length (unsigned, si->scc_stack) > 0
1144 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1146 bitmap scc = BITMAP_ALLOC (NULL);
1147 bool have_ref_node = n >= FIRST_REF_NODE;
1148 unsigned int lowest_node;
1151 bitmap_set_bit (scc, n);
1153 while (VEC_length (unsigned, si->scc_stack) != 0
1154 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1156 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1158 bitmap_set_bit (scc, w);
1159 if (w >= FIRST_REF_NODE)
1160 have_ref_node = true;
1163 lowest_node = bitmap_first_set_bit (scc);
1164 gcc_assert (lowest_node < FIRST_REF_NODE);
1165 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1167 if (i < FIRST_REF_NODE)
1169 /* Mark this node for collapsing. */
1170 if (unite (lowest_node, i))
1171 unify_nodes (graph, lowest_node, i, false);
1175 unite (lowest_node, i);
1176 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1180 SET_BIT (si->roots, n);
1183 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1186 /* Unify node FROM into node TO, updating the changed count if
1187 necessary when UPDATE_CHANGED is true. */
1190 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1191 bool update_changed)
1194 gcc_assert (to != from && find (to) == to);
1195 if (dump_file && (dump_flags & TDF_DETAILS))
1196 fprintf (dump_file, "Unifying %s to %s\n",
1197 get_varinfo (from)->name,
1198 get_varinfo (to)->name);
1201 stats.unified_vars_dynamic++;
1203 stats.unified_vars_static++;
1205 merge_graph_nodes (graph, to, from);
1206 merge_node_constraints (graph, to, from);
1208 if (get_varinfo (from)->no_tbaa_pruning)
1209 get_varinfo (to)->no_tbaa_pruning = true;
1211 if (update_changed && TEST_BIT (changed, from))
1213 RESET_BIT (changed, from);
1214 if (!TEST_BIT (changed, to))
1215 SET_BIT (changed, to);
1218 gcc_assert (changed_count > 0);
1223 /* If the solution changes because of the merging, we need to mark
1224 the variable as changed. */
1225 if (bitmap_ior_into (get_varinfo (to)->solution,
1226 get_varinfo (from)->solution))
1228 if (update_changed && !TEST_BIT (changed, to))
1230 SET_BIT (changed, to);
1235 BITMAP_FREE (get_varinfo (from)->solution);
1236 BITMAP_FREE (get_varinfo (from)->oldsolution);
1238 if (stats.iterations > 0)
1240 BITMAP_FREE (get_varinfo (to)->oldsolution);
1241 get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1244 if (valid_graph_edge (graph, to, to))
1246 if (graph->succs[to])
1247 bitmap_clear_bit (graph->succs[to], to);
1251 /* Information needed to compute the topological ordering of a graph. */
1255 /* sbitmap of visited nodes. */
1257 /* Array that stores the topological order of the graph, *in
1259 VEC(unsigned,heap) *topo_order;
1263 /* Initialize and return a topological info structure. */
1265 static struct topo_info *
1266 init_topo_info (void)
1268 size_t size = VEC_length (varinfo_t, varmap);
1269 struct topo_info *ti = XNEW (struct topo_info);
1270 ti->visited = sbitmap_alloc (size);
1271 sbitmap_zero (ti->visited);
1272 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1277 /* Free the topological sort info pointed to by TI. */
1280 free_topo_info (struct topo_info *ti)
1282 sbitmap_free (ti->visited);
1283 VEC_free (unsigned, heap, ti->topo_order);
1287 /* Visit the graph in topological order, and store the order in the
1288 topo_info structure. */
1291 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1297 SET_BIT (ti->visited, n);
1299 if (graph->succs[n])
1300 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1302 if (!TEST_BIT (ti->visited, j))
1303 topo_visit (graph, ti, j);
1306 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1309 /* Return true if variable N + OFFSET is a legal field of N. */
1312 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1314 varinfo_t ninfo = get_varinfo (n);
1316 /* For things we've globbed to single variables, any offset into the
1317 variable acts like the entire variable, so that it becomes offset
1319 if (ninfo->is_special_var
1320 || ninfo->is_artificial_var
1321 || ninfo->is_unknown_size_var)
1326 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1329 /* Process a constraint C that represents *x = &y. */
1332 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
1333 constraint_t c, bitmap delta)
1335 unsigned int rhs = c->rhs.var;
1339 /* For each member j of Delta (Sol(x)), add x to Sol(j) */
1340 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1342 unsigned HOST_WIDE_INT offset = c->lhs.offset;
1343 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
1345 /* *x != NULL && *x != ANYTHING*/
1349 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
1351 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1355 sol = get_varinfo (t)->solution;
1356 if (!bitmap_bit_p (sol, rhs))
1358 bitmap_set_bit (sol, rhs);
1359 if (!TEST_BIT (changed, t))
1361 SET_BIT (changed, t);
1366 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1367 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
1372 /* Process a constraint C that represents x = *y, using DELTA as the
1373 starting solution. */
1376 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1379 unsigned int lhs = find (c->lhs.var);
1381 bitmap sol = get_varinfo (lhs)->solution;
1385 if (bitmap_bit_p (delta, anything_id))
1387 flag = !bitmap_bit_p (sol, anything_id);
1389 bitmap_set_bit (sol, anything_id);
1392 /* For each variable j in delta (Sol(y)), add
1393 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1394 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1396 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1397 if (type_safe (j, &roffset))
1400 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1403 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1408 /* Adding edges from the special vars is pointless.
1409 They don't have sets that can change. */
1410 if (get_varinfo (t) ->is_special_var)
1411 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1412 else if (add_graph_edge (graph, lhs, t))
1413 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1415 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1416 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
1421 /* If the LHS solution changed, mark the var as changed. */
1424 get_varinfo (lhs)->solution = sol;
1425 if (!TEST_BIT (changed, lhs))
1427 SET_BIT (changed, lhs);
1433 /* Process a constraint C that represents *x = y. */
1436 do_ds_constraint (constraint_t c, bitmap delta)
1438 unsigned int rhs = find (c->rhs.var);
1439 unsigned HOST_WIDE_INT roff = c->rhs.offset;
1440 bitmap sol = get_varinfo (rhs)->solution;
1444 if (bitmap_bit_p (sol, anything_id))
1446 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1448 varinfo_t jvi = get_varinfo (j);
1450 unsigned int loff = c->lhs.offset;
1451 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
1454 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1459 if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id))
1461 bitmap_set_bit (get_varinfo (t)->solution, anything_id);
1462 if (!TEST_BIT (changed, t))
1464 SET_BIT (changed, t);
1472 /* For each member j of delta (Sol(x)), add an edge from y to j and
1473 union Sol(y) into Sol(j) */
1474 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1476 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1477 if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
1481 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1484 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1488 tmp = get_varinfo (t)->solution;
1490 if (set_union_with_increment (tmp, sol, roff))
1492 get_varinfo (t)->solution = tmp;
1494 sol = get_varinfo (rhs)->solution;
1495 if (!TEST_BIT (changed, t))
1497 SET_BIT (changed, t);
1502 else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
1503 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
1507 /* Handle a non-simple (simple meaning requires no iteration),
1508 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1511 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1513 if (c->lhs.type == DEREF)
1515 if (c->rhs.type == ADDRESSOF)
1518 do_da_constraint (graph, c, delta);
1523 do_ds_constraint (c, delta);
1526 else if (c->rhs.type == DEREF)
1529 if (!(get_varinfo (c->lhs.var)->is_special_var))
1530 do_sd_constraint (graph, c, delta);
1539 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1540 t = find (c->rhs.var);
1541 solution = get_varinfo (t)->solution;
1542 t = find (c->lhs.var);
1543 tmp = get_varinfo (t)->solution;
1545 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1549 get_varinfo (t)->solution = tmp;
1550 if (!TEST_BIT (changed, t))
1552 SET_BIT (changed, t);
1559 /* Initialize and return a new SCC info structure. */
1561 static struct scc_info *
1562 init_scc_info (size_t size)
1564 struct scc_info *si = XNEW (struct scc_info);
1567 si->current_index = 0;
1568 si->visited = sbitmap_alloc (size);
1569 sbitmap_zero (si->visited);
1570 si->roots = sbitmap_alloc (size);
1571 sbitmap_zero (si->roots);
1572 si->node_mapping = XNEWVEC (unsigned int, size);
1573 si->dfs = XCNEWVEC (unsigned int, size);
1575 for (i = 0; i < size; i++)
1576 si->node_mapping[i] = i;
1578 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1582 /* Free an SCC info structure pointed to by SI */
1585 free_scc_info (struct scc_info *si)
1587 sbitmap_free (si->visited);
1588 sbitmap_free (si->roots);
1589 free (si->node_mapping);
1591 VEC_free (unsigned, heap, si->scc_stack);
1596 /* Find indirect cycles in GRAPH that occur, using strongly connected
1597 components, and note them in the indirect cycles map.
1599 This technique comes from Ben Hardekopf and Calvin Lin,
1600 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1601 Lines of Code", submitted to PLDI 2007. */
1604 find_indirect_cycles (constraint_graph_t graph)
1607 unsigned int size = graph->size;
1608 struct scc_info *si = init_scc_info (size);
1610 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1611 if (!TEST_BIT (si->visited, i) && find (i) == i)
1612 scc_visit (graph, si, i);
1617 /* Compute a topological ordering for GRAPH, and store the result in the
1618 topo_info structure TI. */
1621 compute_topo_order (constraint_graph_t graph,
1622 struct topo_info *ti)
1625 unsigned int size = VEC_length (varinfo_t, varmap);
1627 for (i = 0; i != size; ++i)
1628 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1629 topo_visit (graph, ti, i);
1632 /* Perform offline variable substitution.
1634 This is a linear time way of identifying variables that must have
1635 equivalent points-to sets, including those caused by static cycles,
1636 and single entry subgraphs, in the constraint graph.
1638 The technique is described in "Off-line variable substitution for
1639 scaling points-to analysis" by Atanas Rountev and Satish Chandra,
1640 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56.
1642 There is an optimal way to do this involving hash based value
1643 numbering, once the technique is published i will implement it
1646 The general method of finding equivalence classes is as follows:
1647 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1648 Add fake nodes (ADDRESS nodes) and edges for a = &b constraints.
1649 Initialize all non-REF/ADDRESS nodes to be direct nodes
1650 For each SCC in the predecessor graph:
1651 for each member (x) of the SCC
1652 if x is not a direct node:
1653 set rootnode(SCC) to be not a direct node
1654 collapse node x into rootnode(SCC).
1655 if rootnode(SCC) is not a direct node:
1656 label rootnode(SCC) with a new equivalence class
1658 if all labeled predecessors of rootnode(SCC) have the same
1660 label rootnode(SCC) with this label
1662 label rootnode(SCC) with a new equivalence class
1664 All direct nodes with the same equivalence class can be replaced
1665 with a single representative node.
1666 All unlabeled nodes (label == 0) are not pointers and all edges
1667 involving them can be eliminated.
1668 We perform these optimizations during move_complex_constraints.
1671 static int equivalence_class;
1673 /* Recursive routine to find strongly connected components in GRAPH,
1674 and label it's nodes with equivalence classes.
1675 This is used during variable substitution to find cycles involving
1676 the regular or implicit predecessors, and label them as equivalent.
1677 The SCC finding algorithm used is the same as that for scc_visit. */
1680 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1684 unsigned int my_dfs;
1686 gcc_assert (si->node_mapping[n] == n);
1687 SET_BIT (si->visited, n);
1688 si->dfs[n] = si->current_index ++;
1689 my_dfs = si->dfs[n];
1691 /* Visit all the successors. */
1692 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1694 unsigned int w = si->node_mapping[i];
1696 if (TEST_BIT (si->roots, w))
1699 if (!TEST_BIT (si->visited, w))
1700 label_visit (graph, si, w);
1702 unsigned int t = si->node_mapping[w];
1703 unsigned int nnode = si->node_mapping[n];
1704 gcc_assert (nnode == n);
1706 if (si->dfs[t] < si->dfs[nnode])
1707 si->dfs[n] = si->dfs[t];
1711 /* Visit all the implicit predecessors. */
1712 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1714 unsigned int w = si->node_mapping[i];
1716 if (TEST_BIT (si->roots, w))
1719 if (!TEST_BIT (si->visited, w))
1720 label_visit (graph, si, w);
1722 unsigned int t = si->node_mapping[w];
1723 unsigned int nnode = si->node_mapping[n];
1724 gcc_assert (nnode == n);
1726 if (si->dfs[t] < si->dfs[nnode])
1727 si->dfs[n] = si->dfs[t];
1731 /* See if any components have been identified. */
1732 if (si->dfs[n] == my_dfs)
1734 while (VEC_length (unsigned, si->scc_stack) != 0
1735 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1737 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1738 si->node_mapping[w] = n;
1740 if (!TEST_BIT (graph->direct_nodes, w))
1741 RESET_BIT (graph->direct_nodes, n);
1743 SET_BIT (si->roots, n);
1745 if (!TEST_BIT (graph->direct_nodes, n))
1747 graph->label[n] = equivalence_class++;
1751 unsigned int size = 0;
1752 unsigned int firstlabel = ~0;
1754 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1756 unsigned int j = si->node_mapping[i];
1758 if (j == n || graph->label[j] == 0)
1761 if (firstlabel == (unsigned int)~0)
1763 firstlabel = graph->label[j];
1766 else if (graph->label[j] != firstlabel)
1771 graph->label[n] = 0;
1773 graph->label[n] = firstlabel;
1775 graph->label[n] = equivalence_class++;
1779 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1782 /* Perform offline variable substitution, discovering equivalence
1783 classes, and eliminating non-pointer variables. */
1785 static struct scc_info *
1786 perform_var_substitution (constraint_graph_t graph)
1789 unsigned int size = graph->size;
1790 struct scc_info *si = init_scc_info (size);
1792 bitmap_obstack_initialize (&iteration_obstack);
1793 equivalence_class = 0;
1795 /* We only need to visit the non-address nodes for labeling
1796 purposes, as the address nodes will never have any predecessors,
1797 because &x never appears on the LHS of a constraint. */
1798 for (i = 0; i < LAST_REF_NODE; i++)
1799 if (!TEST_BIT (si->visited, si->node_mapping[i]))
1800 label_visit (graph, si, si->node_mapping[i]);
1802 if (dump_file && (dump_flags & TDF_DETAILS))
1803 for (i = 0; i < FIRST_REF_NODE; i++)
1805 bool direct_node = TEST_BIT (graph->direct_nodes, i);
1807 "Equivalence class for %s node id %d:%s is %d\n",
1808 direct_node ? "Direct node" : "Indirect node", i,
1809 get_varinfo (i)->name,
1810 graph->label[si->node_mapping[i]]);
1813 /* Quickly eliminate our non-pointer variables. */
1815 for (i = 0; i < FIRST_REF_NODE; i++)
1817 unsigned int node = si->node_mapping[i];
1819 if (graph->label[node] == 0 && TEST_BIT (graph->direct_nodes, node))
1821 if (dump_file && (dump_flags & TDF_DETAILS))
1823 "%s is a non-pointer variable, eliminating edges.\n",
1824 get_varinfo (node)->name);
1825 stats.nonpointer_vars++;
1826 clear_edges_for_node (graph, node);
1832 /* Free information that was only necessary for variable
1836 free_var_substitution_info (struct scc_info *si)
1839 free (graph->label);
1840 free (graph->eq_rep);
1841 sbitmap_free (graph->direct_nodes);
1842 bitmap_obstack_release (&iteration_obstack);
1845 /* Return an existing node that is equivalent to NODE, which has
1846 equivalence class LABEL, if one exists. Return NODE otherwise. */
1849 find_equivalent_node (constraint_graph_t graph,
1850 unsigned int node, unsigned int label)
1852 /* If the address version of this variable is unused, we can
1853 substitute it for anything else with the same label.
1854 Otherwise, we know the pointers are equivalent, but not the
1857 if (graph->label[FIRST_ADDR_NODE + node] == 0)
1859 gcc_assert (label < graph->size);
1861 if (graph->eq_rep[label] != -1)
1863 /* Unify the two variables since we know they are equivalent. */
1864 if (unite (graph->eq_rep[label], node))
1865 unify_nodes (graph, graph->eq_rep[label], node, false);
1866 return graph->eq_rep[label];
1870 graph->eq_rep[label] = node;
1876 /* Move complex constraints to the appropriate nodes, and collapse
1877 variables we've discovered are equivalent during variable
1878 substitution. SI is the SCC_INFO that is the result of
1879 perform_variable_substitution. */
1882 move_complex_constraints (constraint_graph_t graph,
1883 struct scc_info *si)
1889 for (j = 0; j < graph->size; j++)
1890 gcc_assert (find (j) == j);
1892 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1894 struct constraint_expr lhs = c->lhs;
1895 struct constraint_expr rhs = c->rhs;
1896 unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id);
1897 unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id);
1898 unsigned int lhsnode, rhsnode;
1899 unsigned int lhslabel, rhslabel;
1901 lhsnode = si->node_mapping[lhsvar];
1902 rhsnode = si->node_mapping[rhsvar];
1903 lhslabel = graph->label[lhsnode];
1904 rhslabel = graph->label[rhsnode];
1906 /* See if it is really a non-pointer variable, and if so, ignore
1910 if (!TEST_BIT (graph->direct_nodes, lhsnode))
1911 lhslabel = graph->label[lhsnode] = equivalence_class++;
1914 if (dump_file && (dump_flags & TDF_DETAILS))
1917 fprintf (dump_file, "%s is a non-pointer variable,"
1918 "ignoring constraint:",
1919 get_varinfo (lhs.var)->name);
1920 dump_constraint (dump_file, c);
1922 VEC_replace (constraint_t, constraints, i, NULL);
1929 if (!TEST_BIT (graph->direct_nodes, rhsnode))
1930 rhslabel = graph->label[rhsnode] = equivalence_class++;
1933 if (dump_file && (dump_flags & TDF_DETAILS))
1936 fprintf (dump_file, "%s is a non-pointer variable,"
1937 "ignoring constraint:",
1938 get_varinfo (rhs.var)->name);
1939 dump_constraint (dump_file, c);
1941 VEC_replace (constraint_t, constraints, i, NULL);
1946 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
1947 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
1948 c->lhs.var = lhsvar;
1949 c->rhs.var = rhsvar;
1951 if (lhs.type == DEREF)
1953 if (rhs.type == ADDRESSOF || rhsvar > anything_id)
1954 insert_into_complex (graph, lhsvar, c);
1956 else if (rhs.type == DEREF)
1958 if (!(get_varinfo (lhsvar)->is_special_var))
1959 insert_into_complex (graph, rhsvar, c);
1961 else if (rhs.type != ADDRESSOF && lhsvar > anything_id
1962 && (lhs.offset != 0 || rhs.offset != 0))
1964 insert_into_complex (graph, rhsvar, c);
1970 /* Eliminate indirect cycles involving NODE. Return true if NODE was
1971 part of an SCC, false otherwise. */
1974 eliminate_indirect_cycles (unsigned int node)
1976 if (graph->indirect_cycles[node] != -1
1977 && !bitmap_empty_p (get_varinfo (node)->solution))
1980 VEC(unsigned,heap) *queue = NULL;
1982 unsigned int to = find (graph->indirect_cycles[node]);
1985 /* We can't touch the solution set and call unify_nodes
1986 at the same time, because unify_nodes is going to do
1987 bitmap unions into it. */
1989 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
1991 if (find (i) == i && i != to)
1994 VEC_safe_push (unsigned, heap, queue, i);
1999 VEC_iterate (unsigned, queue, queuepos, i);
2002 unify_nodes (graph, to, i, true);
2004 VEC_free (unsigned, heap, queue);
2010 /* Solve the constraint graph GRAPH using our worklist solver.
2011 This is based on the PW* family of solvers from the "Efficient Field
2012 Sensitive Pointer Analysis for C" paper.
2013 It works by iterating over all the graph nodes, processing the complex
2014 constraints and propagating the copy constraints, until everything stops
2015 changed. This corresponds to steps 6-8 in the solving list given above. */
2018 solve_graph (constraint_graph_t graph)
2020 unsigned int size = VEC_length (varinfo_t, varmap);
2025 changed = sbitmap_alloc (size);
2026 sbitmap_zero (changed);
2028 /* Mark all initial non-collapsed nodes as changed. */
2029 for (i = 0; i < size; i++)
2031 varinfo_t ivi = get_varinfo (i);
2032 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2033 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2034 || VEC_length (constraint_t, graph->complex[i]) > 0))
2036 SET_BIT (changed, i);
2041 /* Allocate a bitmap to be used to store the changed bits. */
2042 pts = BITMAP_ALLOC (&pta_obstack);
2044 while (changed_count > 0)
2047 struct topo_info *ti = init_topo_info ();
2050 bitmap_obstack_initialize (&iteration_obstack);
2052 compute_topo_order (graph, ti);
2054 while (VEC_length (unsigned, ti->topo_order) != 0)
2057 i = VEC_pop (unsigned, ti->topo_order);
2059 /* If this variable is not a representative, skip it. */
2063 /* In certain indirect cycle cases, we may merge this
2064 variable to another. */
2065 if (eliminate_indirect_cycles (i) && find (i) != i)
2068 /* If the node has changed, we need to process the
2069 complex constraints and outgoing edges again. */
2070 if (TEST_BIT (changed, i))
2075 VEC(constraint_t,heap) *complex = graph->complex[i];
2076 bool solution_empty;
2078 RESET_BIT (changed, i);
2081 /* Compute the changed set of solution bits. */
2082 bitmap_and_compl (pts, get_varinfo (i)->solution,
2083 get_varinfo (i)->oldsolution);
2085 if (bitmap_empty_p (pts))
2088 bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2090 solution = get_varinfo (i)->solution;
2091 solution_empty = bitmap_empty_p (solution);
2093 /* Process the complex constraints */
2094 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2096 /* The only complex constraint that can change our
2097 solution to non-empty, given an empty solution,
2098 is a constraint where the lhs side is receiving
2099 some set from elsewhere. */
2100 if (!solution_empty || c->lhs.type != DEREF)
2101 do_complex_constraint (graph, c, pts);
2104 solution_empty = bitmap_empty_p (solution);
2106 if (!solution_empty)
2110 /* Propagate solution to all successors. */
2111 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2117 unsigned int to = find (j);
2118 tmp = get_varinfo (to)->solution;
2121 /* Don't try to propagate to ourselves. */
2125 flag = set_union_with_increment (tmp, pts, 0);
2129 get_varinfo (to)->solution = tmp;
2130 if (!TEST_BIT (changed, to))
2132 SET_BIT (changed, to);
2140 free_topo_info (ti);
2141 bitmap_obstack_release (&iteration_obstack);
2145 sbitmap_free (changed);
2146 bitmap_obstack_release (&oldpta_obstack);
2149 /* Map from trees to variable infos. */
2150 static struct pointer_map_t *vi_for_tree;
2153 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2156 insert_vi_for_tree (tree t, varinfo_t vi)
2158 void **slot = pointer_map_insert (vi_for_tree, t);
2160 gcc_assert (*slot == NULL);
2164 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2165 exist in the map, return NULL, otherwise, return the varinfo we found. */
2168 lookup_vi_for_tree (tree t)
2170 void **slot = pointer_map_contains (vi_for_tree, t);
2174 return (varinfo_t) *slot;
2177 /* Return a printable name for DECL */
2180 alias_get_name (tree decl)
2182 const char *res = get_name (decl);
2184 int num_printed = 0;
2193 if (TREE_CODE (decl) == SSA_NAME)
2195 num_printed = asprintf (&temp, "%s_%u",
2196 alias_get_name (SSA_NAME_VAR (decl)),
2197 SSA_NAME_VERSION (decl));
2199 else if (DECL_P (decl))
2201 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2203 if (num_printed > 0)
2205 res = ggc_strdup (temp);
2211 /* Find the variable id for tree T in the map.
2212 If T doesn't exist in the map, create an entry for it and return it. */
2215 get_vi_for_tree (tree t)
2217 void **slot = pointer_map_contains (vi_for_tree, t);
2219 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2221 return (varinfo_t) *slot;
2224 /* Get a constraint expression from an SSA_VAR_P node. */
2226 static struct constraint_expr
2227 get_constraint_exp_from_ssa_var (tree t)
2229 struct constraint_expr cexpr;
2231 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2233 /* For parameters, get at the points-to set for the actual parm
2235 if (TREE_CODE (t) == SSA_NAME
2236 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2237 && SSA_NAME_IS_DEFAULT_DEF (t))
2238 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
2240 cexpr.type = SCALAR;
2242 cexpr.var = get_vi_for_tree (t)->id;
2243 /* If we determine the result is "anything", and we know this is readonly,
2244 say it points to readonly memory instead. */
2245 if (cexpr.var == anything_id && TREE_READONLY (t))
2247 cexpr.type = ADDRESSOF;
2248 cexpr.var = readonly_id;
2255 /* Process a completed constraint T, and add it to the constraint
2259 process_constraint (constraint_t t)
2261 struct constraint_expr rhs = t->rhs;
2262 struct constraint_expr lhs = t->lhs;
2264 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2265 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2267 if (lhs.type == DEREF)
2268 get_varinfo (lhs.var)->directly_dereferenced = true;
2269 if (rhs.type == DEREF)
2270 get_varinfo (rhs.var)->directly_dereferenced = true;
2272 if (!use_field_sensitive)
2278 /* ANYTHING == ANYTHING is pointless. */
2279 if (lhs.var == anything_id && rhs.var == anything_id)
2282 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2283 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
2288 process_constraint (t);
2290 /* This can happen in our IR with things like n->a = *p */
2291 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2293 /* Split into tmp = *rhs, *lhs = tmp */
2294 tree rhsdecl = get_varinfo (rhs.var)->decl;
2295 tree pointertype = TREE_TYPE (rhsdecl);
2296 tree pointedtotype = TREE_TYPE (pointertype);
2297 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2298 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2300 /* If this is an aggregate of known size, we should have passed
2301 this off to do_structure_copy, and it should have broken it
2303 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
2304 || get_varinfo (rhs.var)->is_unknown_size_var);
2306 process_constraint (new_constraint (tmplhs, rhs));
2307 process_constraint (new_constraint (lhs, tmplhs));
2311 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2312 VEC_safe_push (constraint_t, heap, constraints, t);
2316 /* Return true if T is a variable of a type that could contain
2320 could_have_pointers (tree t)
2322 tree type = TREE_TYPE (t);
2324 if (POINTER_TYPE_P (type)
2325 || AGGREGATE_TYPE_P (type)
2326 || TREE_CODE (type) == COMPLEX_TYPE)
2332 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2335 static unsigned HOST_WIDE_INT
2336 bitpos_of_field (const tree fdecl)
2339 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
2340 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
2343 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
2344 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
2348 /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
2349 overlaps with a field at [FIELDPOS, FIELDSIZE] */
2352 offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
2353 const unsigned HOST_WIDE_INT fieldsize,
2354 const unsigned HOST_WIDE_INT accesspos,
2355 const unsigned HOST_WIDE_INT accesssize)
2357 if (fieldpos == accesspos && fieldsize == accesssize)
2359 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
2361 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
2367 /* Given a COMPONENT_REF T, return the constraint_expr for it. */
2370 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results)
2373 HOST_WIDE_INT bitsize = -1;
2374 HOST_WIDE_INT bitmaxsize = -1;
2375 HOST_WIDE_INT bitpos;
2377 struct constraint_expr *result;
2378 unsigned int beforelength = VEC_length (ce_s, *results);
2380 /* Some people like to do cute things like take the address of
2383 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2384 forzero = TREE_OPERAND (forzero, 0);
2386 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2388 struct constraint_expr temp;
2391 temp.var = integer_id;
2393 VEC_safe_push (ce_s, heap, *results, &temp);
2397 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2399 /* String constants are readonly, so there is nothing to really do
2401 if (TREE_CODE (t) == STRING_CST)
2404 get_constraint_for (t, results);
2405 result = VEC_last (ce_s, *results);
2406 result->offset = bitpos;
2408 gcc_assert (beforelength + 1 == VEC_length (ce_s, *results));
2410 /* This can also happen due to weird offsetof type macros. */
2411 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2412 result->type = SCALAR;
2414 if (result->type == SCALAR)
2416 /* In languages like C, you can access one past the end of an
2417 array. You aren't allowed to dereference it, so we can
2418 ignore this constraint. When we handle pointer subtraction,
2419 we may have to do something cute here. */
2421 if (result->offset < get_varinfo (result->var)->fullsize
2424 /* It's also not true that the constraint will actually start at the
2425 right offset, it may start in some padding. We only care about
2426 setting the constraint to the first actual field it touches, so
2429 for (curr = get_varinfo (result->var); curr; curr = curr->next)
2431 if (offset_overlaps_with_access (curr->offset, curr->size,
2432 result->offset, bitmaxsize))
2434 result->var = curr->id;
2438 /* assert that we found *some* field there. The user couldn't be
2439 accessing *only* padding. */
2440 /* Still the user could access one past the end of an array
2441 embedded in a struct resulting in accessing *only* padding. */
2442 gcc_assert (curr || ref_contains_array_ref (orig_t));
2444 else if (bitmaxsize == 0)
2446 if (dump_file && (dump_flags & TDF_DETAILS))
2447 fprintf (dump_file, "Access to zero-sized part of variable,"
2451 if (dump_file && (dump_flags & TDF_DETAILS))
2452 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2459 /* Dereference the constraint expression CONS, and return the result.
2460 DEREF (ADDRESSOF) = SCALAR
2461 DEREF (SCALAR) = DEREF
2462 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2463 This is needed so that we can handle dereferencing DEREF constraints. */
2466 do_deref (VEC (ce_s, heap) **constraints)
2468 struct constraint_expr *c;
2471 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2473 if (c->type == SCALAR)
2475 else if (c->type == ADDRESSOF)
2477 else if (c->type == DEREF)
2479 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
2480 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
2481 process_constraint (new_constraint (tmplhs, *c));
2482 c->var = tmplhs.var;
2489 /* Given a tree T, return the constraint expression for it. */
2492 get_constraint_for (tree t, VEC (ce_s, heap) **results)
2494 struct constraint_expr temp;
2496 /* x = integer is all glommed to a single variable, which doesn't
2497 point to anything by itself. That is, of course, unless it is an
2498 integer constant being treated as a pointer, in which case, we
2499 will return that this is really the addressof anything. This
2500 happens below, since it will fall into the default case. The only
2501 case we know something about an integer treated like a pointer is
2502 when it is the NULL pointer, and then we just say it points to
2504 if (TREE_CODE (t) == INTEGER_CST
2505 && !POINTER_TYPE_P (TREE_TYPE (t)))
2507 temp.var = integer_id;
2510 VEC_safe_push (ce_s, heap, *results, &temp);
2513 else if (TREE_CODE (t) == INTEGER_CST
2514 && integer_zerop (t))
2516 temp.var = nothing_id;
2517 temp.type = ADDRESSOF;
2519 VEC_safe_push (ce_s, heap, *results, &temp);
2523 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2525 case tcc_expression:
2528 switch (TREE_CODE (t))
2532 struct constraint_expr *c;
2534 tree exp = TREE_OPERAND (t, 0);
2535 tree pttype = TREE_TYPE (TREE_TYPE (t));
2537 get_constraint_for (exp, results);
2539 /* Make sure we capture constraints to all elements
2541 if ((handled_component_p (exp)
2542 && ref_contains_array_ref (exp))
2543 || TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE)
2545 struct constraint_expr *origrhs;
2547 struct constraint_expr tmp;
2549 if (VEC_length (ce_s, *results) == 0)
2552 gcc_assert (VEC_length (ce_s, *results) == 1);
2553 origrhs = VEC_last (ce_s, *results);
2555 VEC_pop (ce_s, *results);
2556 origvar = get_varinfo (origrhs->var);
2557 for (; origvar; origvar = origvar->next)
2559 tmp.var = origvar->id;
2560 VEC_safe_push (ce_s, heap, *results, &tmp);
2563 else if (VEC_length (ce_s, *results) == 1
2564 && (AGGREGATE_TYPE_P (pttype)
2565 || TREE_CODE (pttype) == COMPLEX_TYPE))
2567 struct constraint_expr *origrhs;
2569 struct constraint_expr tmp;
2571 gcc_assert (VEC_length (ce_s, *results) == 1);
2572 origrhs = VEC_last (ce_s, *results);
2574 VEC_pop (ce_s, *results);
2575 origvar = get_varinfo (origrhs->var);
2576 for (; origvar; origvar = origvar->next)
2578 tmp.var = origvar->id;
2579 VEC_safe_push (ce_s, heap, *results, &tmp);
2583 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
2585 if (c->type == DEREF)
2588 c->type = ADDRESSOF;
2594 /* XXX: In interprocedural mode, if we didn't have the
2595 body, we would need to do *each pointer argument =
2597 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
2600 tree heapvar = heapvar_lookup (t);
2602 if (heapvar == NULL)
2604 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
2605 DECL_EXTERNAL (heapvar) = 1;
2606 get_var_ann (heapvar)->is_heapvar = 1;
2607 if (gimple_referenced_vars (cfun))
2608 add_referenced_var (heapvar);
2609 heapvar_insert (t, heapvar);
2612 temp.var = create_variable_info_for (heapvar,
2613 alias_get_name (heapvar));
2615 vi = get_varinfo (temp.var);
2616 vi->is_artificial_var = 1;
2617 vi->is_heap_var = 1;
2618 temp.type = ADDRESSOF;
2620 VEC_safe_push (ce_s, heap, *results, &temp);
2625 temp.var = anything_id;
2628 VEC_safe_push (ce_s, heap, *results, &temp);
2634 temp.type = ADDRESSOF;
2635 temp.var = anything_id;
2637 VEC_safe_push (ce_s, heap, *results, &temp);
2644 switch (TREE_CODE (t))
2648 get_constraint_for (TREE_OPERAND (t, 0), results);
2653 case ARRAY_RANGE_REF:
2655 get_constraint_for_component_ref (t, results);
2659 temp.type = ADDRESSOF;
2660 temp.var = anything_id;
2662 VEC_safe_push (ce_s, heap, *results, &temp);
2669 switch (TREE_CODE (t))
2673 case NON_LVALUE_EXPR:
2675 tree op = TREE_OPERAND (t, 0);
2677 /* Cast from non-pointer to pointers are bad news for us.
2678 Anything else, we see through */
2679 if (!(POINTER_TYPE_P (TREE_TYPE (t))
2680 && ! POINTER_TYPE_P (TREE_TYPE (op))))
2682 get_constraint_for (op, results);
2690 temp.type = ADDRESSOF;
2691 temp.var = anything_id;
2693 VEC_safe_push (ce_s, heap, *results, &temp);
2698 case tcc_exceptional:
2700 switch (TREE_CODE (t))
2704 get_constraint_for (PHI_RESULT (t), results);
2710 struct constraint_expr temp;
2711 temp = get_constraint_exp_from_ssa_var (t);
2712 VEC_safe_push (ce_s, heap, *results, &temp);
2718 temp.type = ADDRESSOF;
2719 temp.var = anything_id;
2721 VEC_safe_push (ce_s, heap, *results, &temp);
2726 case tcc_declaration:
2728 struct constraint_expr temp;
2729 temp = get_constraint_exp_from_ssa_var (t);
2730 VEC_safe_push (ce_s, heap, *results, &temp);
2735 temp.type = ADDRESSOF;
2736 temp.var = anything_id;
2738 VEC_safe_push (ce_s, heap, *results, &temp);
2745 /* Handle the structure copy case where we have a simple structure copy
2746 between LHS and RHS that is of SIZE (in bits)
2748 For each field of the lhs variable (lhsfield)
2749 For each field of the rhs variable at lhsfield.offset (rhsfield)
2750 add the constraint lhsfield = rhsfield
2752 If we fail due to some kind of type unsafety or other thing we
2753 can't handle, return false. We expect the caller to collapse the
2754 variable in that case. */
2757 do_simple_structure_copy (const struct constraint_expr lhs,
2758 const struct constraint_expr rhs,
2759 const unsigned HOST_WIDE_INT size)
2761 varinfo_t p = get_varinfo (lhs.var);
2762 unsigned HOST_WIDE_INT pstart, last;
2764 last = p->offset + size;
2765 for (; p && p->offset < last; p = p->next)
2768 struct constraint_expr templhs = lhs;
2769 struct constraint_expr temprhs = rhs;
2770 unsigned HOST_WIDE_INT fieldoffset;
2772 templhs.var = p->id;
2773 q = get_varinfo (temprhs.var);
2774 fieldoffset = p->offset - pstart;
2775 q = first_vi_for_offset (q, q->offset + fieldoffset);
2778 temprhs.var = q->id;
2779 process_constraint (new_constraint (templhs, temprhs));
2785 /* Handle the structure copy case where we have a structure copy between a
2786 aggregate on the LHS and a dereference of a pointer on the RHS
2787 that is of SIZE (in bits)
2789 For each field of the lhs variable (lhsfield)
2790 rhs.offset = lhsfield->offset
2791 add the constraint lhsfield = rhs
2795 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
2796 const struct constraint_expr rhs,
2797 const unsigned HOST_WIDE_INT size)
2799 varinfo_t p = get_varinfo (lhs.var);
2800 unsigned HOST_WIDE_INT pstart,last;
2802 last = p->offset + size;
2804 for (; p && p->offset < last; p = p->next)
2807 struct constraint_expr templhs = lhs;
2808 struct constraint_expr temprhs = rhs;
2809 unsigned HOST_WIDE_INT fieldoffset;
2812 if (templhs.type == SCALAR)
2813 templhs.var = p->id;
2815 templhs.offset = p->offset;
2817 q = get_varinfo (temprhs.var);
2818 fieldoffset = p->offset - pstart;
2819 temprhs.offset += fieldoffset;
2820 process_constraint (new_constraint (templhs, temprhs));
2824 /* Handle the structure copy case where we have a structure copy
2825 between an aggregate on the RHS and a dereference of a pointer on
2826 the LHS that is of SIZE (in bits)
2828 For each field of the rhs variable (rhsfield)
2829 lhs.offset = rhsfield->offset
2830 add the constraint lhs = rhsfield
2834 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
2835 const struct constraint_expr rhs,
2836 const unsigned HOST_WIDE_INT size)
2838 varinfo_t p = get_varinfo (rhs.var);
2839 unsigned HOST_WIDE_INT pstart,last;
2841 last = p->offset + size;
2843 for (; p && p->offset < last; p = p->next)
2846 struct constraint_expr templhs = lhs;
2847 struct constraint_expr temprhs = rhs;
2848 unsigned HOST_WIDE_INT fieldoffset;
2851 if (temprhs.type == SCALAR)
2852 temprhs.var = p->id;
2854 temprhs.offset = p->offset;
2856 q = get_varinfo (templhs.var);
2857 fieldoffset = p->offset - pstart;
2858 templhs.offset += fieldoffset;
2859 process_constraint (new_constraint (templhs, temprhs));
2863 /* Sometimes, frontends like to give us bad type information. This
2864 function will collapse all the fields from VAR to the end of VAR,
2865 into VAR, so that we treat those fields as a single variable.
2866 We return the variable they were collapsed into. */
2869 collapse_rest_of_var (unsigned int var)
2871 varinfo_t currvar = get_varinfo (var);
2874 for (field = currvar->next; field; field = field->next)
2877 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
2878 field->name, currvar->name);
2880 gcc_assert (!field->collapsed_to);
2881 field->collapsed_to = currvar;
2884 currvar->next = NULL;
2885 currvar->size = currvar->fullsize - currvar->offset;
2890 /* Handle aggregate copies by expanding into copies of the respective
2891 fields of the structures. */
2894 do_structure_copy (tree lhsop, tree rhsop)
2896 struct constraint_expr lhs, rhs, tmp;
2897 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
2899 unsigned HOST_WIDE_INT lhssize;
2900 unsigned HOST_WIDE_INT rhssize;
2902 get_constraint_for (lhsop, &lhsc);
2903 get_constraint_for (rhsop, &rhsc);
2904 gcc_assert (VEC_length (ce_s, lhsc) == 1);
2905 gcc_assert (VEC_length (ce_s, rhsc) == 1);
2906 lhs = *(VEC_last (ce_s, lhsc));
2907 rhs = *(VEC_last (ce_s, rhsc));
2909 VEC_free (ce_s, heap, lhsc);
2910 VEC_free (ce_s, heap, rhsc);
2912 /* If we have special var = x, swap it around. */
2913 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
2920 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
2921 possible it's something we could handle. However, most cases falling
2922 into this are dealing with transparent unions, which are slightly
2924 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
2926 rhs.type = ADDRESSOF;
2927 rhs.var = anything_id;
2930 /* If the RHS is a special var, or an addressof, set all the LHS fields to
2931 that special var. */
2932 if (rhs.var <= integer_id)
2934 for (p = get_varinfo (lhs.var); p; p = p->next)
2936 struct constraint_expr templhs = lhs;
2937 struct constraint_expr temprhs = rhs;
2939 if (templhs.type == SCALAR )
2940 templhs.var = p->id;
2942 templhs.offset += p->offset;
2943 process_constraint (new_constraint (templhs, temprhs));
2948 tree rhstype = TREE_TYPE (rhsop);
2949 tree lhstype = TREE_TYPE (lhsop);
2953 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
2954 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
2956 /* If we have a variably sized types on the rhs or lhs, and a deref
2957 constraint, add the constraint, lhsconstraint = &ANYTHING.
2958 This is conservatively correct because either the lhs is an unknown
2959 sized var (if the constraint is SCALAR), or the lhs is a DEREF
2960 constraint, and every variable it can point to must be unknown sized
2961 anyway, so we don't need to worry about fields at all. */
2962 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
2963 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
2965 rhs.var = anything_id;
2966 rhs.type = ADDRESSOF;
2968 process_constraint (new_constraint (lhs, rhs));
2972 /* The size only really matters insofar as we don't set more or less of
2973 the variable. If we hit an unknown size var, the size should be the
2974 whole darn thing. */
2975 if (get_varinfo (rhs.var)->is_unknown_size_var)
2978 rhssize = TREE_INT_CST_LOW (rhstypesize);
2980 if (get_varinfo (lhs.var)->is_unknown_size_var)
2983 lhssize = TREE_INT_CST_LOW (lhstypesize);
2986 if (rhs.type == SCALAR && lhs.type == SCALAR)
2988 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
2990 lhs.var = collapse_rest_of_var (lhs.var);
2991 rhs.var = collapse_rest_of_var (rhs.var);
2996 process_constraint (new_constraint (lhs, rhs));
2999 else if (lhs.type != DEREF && rhs.type == DEREF)
3000 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3001 else if (lhs.type == DEREF && rhs.type != DEREF)
3002 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3005 tree pointedtotype = lhstype;
3008 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3009 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
3010 do_structure_copy (tmpvar, rhsop);
3011 do_structure_copy (lhsop, tmpvar);
3017 /* Update related alias information kept in AI. This is used when
3018 building name tags, alias sets and deciding grouping heuristics.
3019 STMT is the statement to process. This function also updates
3020 ADDRESSABLE_VARS. */
3023 update_alias_info (tree stmt, struct alias_info *ai)
3026 use_operand_p use_p;
3028 bool stmt_dereferences_ptr_p;
3029 enum escape_type stmt_escape_type = is_escape_site (stmt);
3030 struct mem_ref_stats_d *mem_ref_stats = gimple_mem_ref_stats (cfun);
3032 stmt_dereferences_ptr_p = false;
3034 if (stmt_escape_type == ESCAPE_TO_CALL
3035 || stmt_escape_type == ESCAPE_TO_PURE_CONST)
3037 mem_ref_stats->num_call_sites++;
3038 if (stmt_escape_type == ESCAPE_TO_PURE_CONST)
3039 mem_ref_stats->num_pure_const_call_sites++;
3041 else if (stmt_escape_type == ESCAPE_TO_ASM)
3042 mem_ref_stats->num_asm_sites++;
3044 /* Mark all the variables whose address are taken by the statement. */
3045 addr_taken = addresses_taken (stmt);
3048 bitmap_ior_into (gimple_addressable_vars (cfun), addr_taken);
3050 /* If STMT is an escape point, all the addresses taken by it are
3052 if (stmt_escape_type != NO_ESCAPE)
3057 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
3059 tree rvar = referenced_var (i);
3060 if (!unmodifiable_var_p (rvar))
3061 mark_call_clobbered (rvar, stmt_escape_type);
3066 /* Process each operand use. For pointers, determine whether they
3067 are dereferenced by the statement, or whether their value
3069 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
3073 struct ptr_info_def *pi;
3074 unsigned num_uses, num_loads, num_stores;
3076 op = USE_FROM_PTR (use_p);
3078 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
3079 to the set of addressable variables. */
3080 if (TREE_CODE (op) == ADDR_EXPR)
3082 bitmap addressable_vars = gimple_addressable_vars (cfun);
3084 gcc_assert (TREE_CODE (stmt) == PHI_NODE);
3085 gcc_assert (addressable_vars);
3087 /* PHI nodes don't have annotations for pinning the set
3088 of addresses taken, so we collect them here.
3090 FIXME, should we allow PHI nodes to have annotations
3091 so that they can be treated like regular statements?
3092 Currently, they are treated as second-class
3094 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
3098 /* Ignore constants (they may occur in PHI node arguments). */
3099 if (TREE_CODE (op) != SSA_NAME)
3102 var = SSA_NAME_VAR (op);
3103 v_ann = var_ann (var);
3105 /* The base variable of an SSA name must be a GIMPLE register, and thus
3106 it cannot be aliased. */
3107 gcc_assert (!may_be_aliased (var));
3109 /* We are only interested in pointers. */
3110 if (!POINTER_TYPE_P (TREE_TYPE (op)))
3113 pi = get_ptr_info (op);
3115 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
3116 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
3118 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
3119 VEC_safe_push (tree, heap, ai->processed_ptrs, op);
3122 /* If STMT is a PHI node, then it will not have pointer
3123 dereferences and it will not be an escape point. */
3124 if (TREE_CODE (stmt) == PHI_NODE)
3127 /* Determine whether OP is a dereferenced pointer, and if STMT
3128 is an escape point, whether OP escapes. */
3129 count_uses_and_derefs (op, stmt, &num_uses, &num_loads, &num_stores);
3131 /* Handle a corner case involving address expressions of the
3132 form '&PTR->FLD'. The problem with these expressions is that
3133 they do not represent a dereference of PTR. However, if some
3134 other transformation propagates them into an INDIRECT_REF
3135 expression, we end up with '*(&PTR->FLD)' which is folded
3138 So, if the original code had no other dereferences of PTR,
3139 the aliaser will not create memory tags for it, and when
3140 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
3141 memory operations will receive no VDEF/VUSE operands.
3143 One solution would be to have count_uses_and_derefs consider
3144 &PTR->FLD a dereference of PTR. But that is wrong, since it
3145 is not really a dereference but an offset calculation.
3147 What we do here is to recognize these special ADDR_EXPR
3148 nodes. Since these expressions are never GIMPLE values (they
3149 are not GIMPLE invariants), they can only appear on the RHS
3150 of an assignment and their base address is always an
3151 INDIRECT_REF expression. */
3152 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3153 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ADDR_EXPR
3154 && !is_gimple_val (GIMPLE_STMT_OPERAND (stmt, 1)))
3156 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
3157 this represents a potential dereference of PTR. */
3158 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3159 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3160 if (TREE_CODE (base) == INDIRECT_REF
3161 && TREE_OPERAND (base, 0) == op)
3165 if (num_loads + num_stores > 0)
3167 /* Mark OP as dereferenced. In a subsequent pass,
3168 dereferenced pointers that point to a set of
3169 variables will be assigned a name tag to alias
3170 all the variables OP points to. */
3171 pi->is_dereferenced = 1;
3173 /* If this is a store operation, mark OP as being
3174 dereferenced to store, otherwise mark it as being
3175 dereferenced to load. */
3177 pointer_set_insert (ai->dereferenced_ptrs_store, var);
3179 pointer_set_insert (ai->dereferenced_ptrs_load, var);
3181 /* Update the frequency estimate for all the dereferences of
3183 update_mem_sym_stats_from_stmt (op, stmt, num_loads, num_stores);
3185 /* Indicate that STMT contains pointer dereferences. */
3186 stmt_dereferences_ptr_p = true;
3189 if (stmt_escape_type != NO_ESCAPE && num_loads + num_stores < num_uses)
3191 /* If STMT is an escape point and STMT contains at
3192 least one direct use of OP, then the value of OP
3193 escapes and so the pointed-to variables need to
3194 be marked call-clobbered. */
3195 pi->value_escapes_p = 1;
3196 pi->escape_mask |= stmt_escape_type;
3198 /* If the statement makes a function call, assume
3199 that pointer OP will be dereferenced in a store
3200 operation inside the called function. */
3201 if (get_call_expr_in (stmt)
3202 || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
3204 pointer_set_insert (ai->dereferenced_ptrs_store, var);
3205 pi->is_dereferenced = 1;
3210 if (TREE_CODE (stmt) == PHI_NODE)
3213 /* Mark stored variables in STMT as being written to and update the
3214 memory reference stats for all memory symbols referenced by STMT. */
3215 if (stmt_references_memory_p (stmt))
3220 mem_ref_stats->num_mem_stmts++;
3222 /* Notice that we only update memory reference stats for symbols
3223 loaded and stored by the statement if the statement does not
3224 contain pointer dereferences and it is not a call/asm site.
3225 This is to avoid double accounting problems when creating
3226 memory partitions. After computing points-to information,
3227 pointer dereference statistics are used to update the
3228 reference stats of the pointed-to variables, so here we
3229 should only update direct references to symbols.
3231 Indirect references are not updated here for two reasons: (1)
3232 The first time we compute alias information, the sets
3233 LOADED/STORED are empty for pointer dereferences, (2) After
3234 partitioning, LOADED/STORED may have references to
3235 partitions, not the original pointed-to variables. So, if we
3236 always counted LOADED/STORED here and during partitioning, we
3237 would count many symbols more than once.
3239 This does cause some imprecision when a statement has a
3240 combination of direct symbol references and pointer
3241 dereferences (e.g., MEMORY_VAR = *PTR) or if a call site has
3242 memory symbols in its argument list, but these cases do not
3243 occur so frequently as to constitute a serious problem. */
3244 if (STORED_SYMS (stmt))
3245 EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi)
3247 tree sym = referenced_var (i);
3248 pointer_set_insert (ai->written_vars, sym);
3249 if (!stmt_dereferences_ptr_p
3250 && stmt_escape_type != ESCAPE_TO_CALL
3251 && stmt_escape_type != ESCAPE_TO_PURE_CONST
3252 && stmt_escape_type != ESCAPE_TO_ASM)
3253 update_mem_sym_stats_from_stmt (sym, stmt, 0, 1);
3256 if (!stmt_dereferences_ptr_p
3257 && LOADED_SYMS (stmt)
3258 && stmt_escape_type != ESCAPE_TO_CALL
3259 && stmt_escape_type != ESCAPE_TO_PURE_CONST
3260 && stmt_escape_type != ESCAPE_TO_ASM)
3261 EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt), 0, i, bi)
3262 update_mem_sym_stats_from_stmt (referenced_var (i), stmt, 1, 0);
3267 /* Handle pointer arithmetic EXPR when creating aliasing constraints.
3268 Expressions of the type PTR + CST can be handled in two ways:
3270 1- If the constraint for PTR is ADDRESSOF for a non-structure
3271 variable, then we can use it directly because adding or
3272 subtracting a constant may not alter the original ADDRESSOF
3273 constraint (i.e., pointer arithmetic may not legally go outside
3274 an object's boundaries).
3276 2- If the constraint for PTR is ADDRESSOF for a structure variable,
3277 then if CST is a compile-time constant that can be used as an
3278 offset, we can determine which sub-variable will be pointed-to
3281 Return true if the expression is handled. For any other kind of
3282 expression, return false so that each operand can be added as a
3283 separate constraint by the caller. */
3286 handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr)
3289 struct constraint_expr *c, *c2;
3292 VEC (ce_s, heap) *temp = NULL;
3293 unsigned HOST_WIDE_INT rhsoffset = 0;
3295 if (TREE_CODE (expr) != POINTER_PLUS_EXPR)
3298 op0 = TREE_OPERAND (expr, 0);
3299 op1 = TREE_OPERAND (expr, 1);
3300 gcc_assert (POINTER_TYPE_P (TREE_TYPE (op0)));
3302 get_constraint_for (op0, &temp);
3304 /* We can only handle positive offsets that do not overflow
3305 if we multiply it by BITS_PER_UNIT. */
3306 if (host_integerp (op1, 1))
3308 rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
3310 if (rhsoffset / BITS_PER_UNIT != TREE_INT_CST_LOW (op1))
3314 for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
3315 for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
3317 if (c2->type == ADDRESSOF && rhsoffset != 0)
3319 varinfo_t temp = get_varinfo (c2->var);
3321 /* An access one after the end of an array is valid,
3322 so simply punt on accesses we cannot resolve. */
3323 temp = first_vi_for_offset (temp, rhsoffset);
3330 c2->offset = rhsoffset;
3331 process_constraint (new_constraint (*c, *c2));
3334 VEC_free (ce_s, heap, temp);
3340 /* Walk statement T setting up aliasing constraints according to the
3341 references found in T. This function is the main part of the
3342 constraint builder. AI points to auxiliary alias information used
3343 when building alias sets and computing alias grouping heuristics. */
3346 find_func_aliases (tree origt)
3349 VEC(ce_s, heap) *lhsc = NULL;
3350 VEC(ce_s, heap) *rhsc = NULL;
3351 struct constraint_expr *c;
3353 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
3354 t = TREE_OPERAND (t, 0);
3356 /* Now build constraints expressions. */
3357 if (TREE_CODE (t) == PHI_NODE)
3359 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))));
3361 /* Only care about pointers and structures containing
3363 if (could_have_pointers (PHI_RESULT (t)))
3368 /* For a phi node, assign all the arguments to
3370 get_constraint_for (PHI_RESULT (t), &lhsc);
3371 for (i = 0; i < PHI_NUM_ARGS (t); i++)
3374 tree strippedrhs = PHI_ARG_DEF (t, i);
3376 STRIP_NOPS (strippedrhs);
3377 rhstype = TREE_TYPE (strippedrhs);
3378 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
3380 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3382 struct constraint_expr *c2;
3383 while (VEC_length (ce_s, rhsc) > 0)
3385 c2 = VEC_last (ce_s, rhsc);
3386 process_constraint (new_constraint (*c, *c2));
3387 VEC_pop (ce_s, rhsc);
3393 /* In IPA mode, we need to generate constraints to pass call
3394 arguments through their calls. There are two cases, either a
3395 GIMPLE_MODIFY_STMT when we are returning a value, or just a plain
3396 CALL_EXPR when we are not. */
3397 else if (in_ipa_mode
3398 && ((TREE_CODE (t) == GIMPLE_MODIFY_STMT
3399 && TREE_CODE (GIMPLE_STMT_OPERAND (t, 1)) == CALL_EXPR
3400 && !(call_expr_flags (GIMPLE_STMT_OPERAND (t, 1))
3401 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
3402 || (TREE_CODE (t) == CALL_EXPR
3403 && !(call_expr_flags (t)
3404 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))))
3409 call_expr_arg_iterator iter;
3413 if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
3415 lhsop = GIMPLE_STMT_OPERAND (t, 0);
3416 rhsop = GIMPLE_STMT_OPERAND (t, 1);
3423 decl = get_callee_fndecl (rhsop);
3425 /* If we can directly resolve the function being called, do so.
3426 Otherwise, it must be some sort of indirect expression that
3427 we should still be able to handle. */
3430 fi = get_vi_for_tree (decl);
3434 decl = CALL_EXPR_FN (rhsop);
3435 fi = get_vi_for_tree (decl);
3438 /* Assign all the passed arguments to the appropriate incoming
3439 parameters of the function. */
3441 FOR_EACH_CALL_EXPR_ARG (arg, iter, rhsop)
3443 struct constraint_expr lhs ;
3444 struct constraint_expr *rhsp;
3446 get_constraint_for (arg, &rhsc);
3447 if (TREE_CODE (decl) != FUNCTION_DECL)
3456 lhs.var = first_vi_for_offset (fi, i)->id;
3459 while (VEC_length (ce_s, rhsc) != 0)
3461 rhsp = VEC_last (ce_s, rhsc);
3462 process_constraint (new_constraint (lhs, *rhsp));
3463 VEC_pop (ce_s, rhsc);
3468 /* If we are returning a value, assign it to the result. */
3471 struct constraint_expr rhs;
3472 struct constraint_expr *lhsp;
3475 get_constraint_for (lhsop, &lhsc);
3476 if (TREE_CODE (decl) != FUNCTION_DECL)
3485 rhs.var = first_vi_for_offset (fi, i)->id;
3488 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3489 process_constraint (new_constraint (*lhsp, rhs));
3492 /* Otherwise, just a regular assignment statement. */
3493 else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
3495 tree lhsop = GIMPLE_STMT_OPERAND (t, 0);
3496 tree rhsop = GIMPLE_STMT_OPERAND (t, 1);
3499 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
3500 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)
3501 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop))
3502 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE))
3504 do_structure_copy (lhsop, rhsop);
3508 /* Only care about operations with pointers, structures
3509 containing pointers, dereferences, and call expressions. */
3510 if (could_have_pointers (lhsop)
3511 || TREE_CODE (rhsop) == CALL_EXPR)
3513 get_constraint_for (lhsop, &lhsc);
3514 switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
3516 /* RHS that consist of unary operations,
3517 exceptional types, or bare decls/constants, get
3518 handled directly by get_constraint_for. */
3520 case tcc_declaration:
3522 case tcc_exceptional:
3523 case tcc_expression:
3529 get_constraint_for (rhsop, &rhsc);
3530 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3532 struct constraint_expr *c2;
3535 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3536 process_constraint (new_constraint (*c, *c2));
3544 /* For pointer arithmetic of the form
3545 PTR + CST, we can simply use PTR's
3546 constraint because pointer arithmetic is
3547 not allowed to go out of bounds. */
3548 if (handle_ptr_arith (lhsc, rhsop))
3553 /* Otherwise, walk each operand. Notice that we
3554 can't use the operand interface because we need
3555 to process expressions other than simple operands
3556 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
3558 for (i = 0; i < TREE_OPERAND_LENGTH (rhsop); i++)
3560 tree op = TREE_OPERAND (rhsop, i);
3563 gcc_assert (VEC_length (ce_s, rhsc) == 0);
3564 get_constraint_for (op, &rhsc);
3565 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3567 struct constraint_expr *c2;
3568 while (VEC_length (ce_s, rhsc) > 0)
3570 c2 = VEC_last (ce_s, rhsc);
3571 process_constraint (new_constraint (*c, *c2));
3572 VEC_pop (ce_s, rhsc);
3580 else if (TREE_CODE (t) == CHANGE_DYNAMIC_TYPE_EXPR)
3584 get_constraint_for (CHANGE_DYNAMIC_TYPE_LOCATION (t), &lhsc);
3585 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); ++j)
3586 get_varinfo (c->var)->no_tbaa_pruning = true;
3589 /* After promoting variables and computing aliasing we will
3590 need to re-scan most statements. FIXME: Try to minimize the
3591 number of statements re-scanned. It's not really necessary to
3592 re-scan *all* statements. */
3593 mark_stmt_modified (origt);
3594 VEC_free (ce_s, heap, rhsc);
3595 VEC_free (ce_s, heap, lhsc);
3599 /* Find the first varinfo in the same variable as START that overlaps with
3601 Effectively, walk the chain of fields for the variable START to find the
3602 first field that overlaps with OFFSET.
3603 Return NULL if we can't find one. */
3606 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3608 varinfo_t curr = start;
3611 /* We may not find a variable in the field list with the actual
3612 offset when when we have glommed a structure to a variable.
3613 In that case, however, offset should still be within the size
3615 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3623 /* Insert the varinfo FIELD into the field list for BASE, at the front
3627 insert_into_field_list (varinfo_t base, varinfo_t field)
3629 varinfo_t prev = base;
3630 varinfo_t curr = base->next;
3636 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3640 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
3642 varinfo_t prev = base;
3643 varinfo_t curr = base->next;
3654 if (field->offset <= curr->offset)
3659 field->next = prev->next;
3664 /* qsort comparison function for two fieldoff's PA and PB */
3667 fieldoff_compare (const void *pa, const void *pb)
3669 const fieldoff_s *foa = (const fieldoff_s *)pa;
3670 const fieldoff_s *fob = (const fieldoff_s *)pb;
3671 HOST_WIDE_INT foasize, fobsize;
3673 if (foa->offset != fob->offset)
3674 return foa->offset - fob->offset;
3676 foasize = TREE_INT_CST_LOW (foa->size);
3677 fobsize = TREE_INT_CST_LOW (fob->size);
3678 return foasize - fobsize;
3681 /* Sort a fieldstack according to the field offset and sizes. */
3683 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
3685 qsort (VEC_address (fieldoff_s, fieldstack),
3686 VEC_length (fieldoff_s, fieldstack),
3687 sizeof (fieldoff_s),
3691 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
3692 of TYPE onto fieldstack, recording their offsets along the way.
3693 OFFSET is used to keep track of the offset in this entire structure, rather
3694 than just the immediately containing structure. Returns the number
3696 HAS_UNION is set to true if we find a union type as a field of
3697 TYPE. ADDRESSABLE_TYPE is the type of the outermost object that could have
3698 its address taken. */
3701 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
3702 HOST_WIDE_INT offset, bool *has_union,
3703 tree addressable_type)
3708 if (TREE_CODE (type) == COMPLEX_TYPE)
3710 fieldoff_s *real_part, *img_part;
3711 real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3712 real_part->type = TREE_TYPE (type);
3713 real_part->size = TYPE_SIZE (TREE_TYPE (type));
3714 real_part->offset = offset;
3715 real_part->decl = NULL_TREE;
3716 real_part->alias_set = -1;
3718 img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3719 img_part->type = TREE_TYPE (type);
3720 img_part->size = TYPE_SIZE (TREE_TYPE (type));
3721 img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
3722 img_part->decl = NULL_TREE;
3723 img_part->alias_set = -1;
3728 if (TREE_CODE (type) == ARRAY_TYPE)
3730 tree sz = TYPE_SIZE (type);
3731 tree elsz = TYPE_SIZE (TREE_TYPE (type));
3736 || ! host_integerp (sz, 1)
3737 || TREE_INT_CST_LOW (sz) == 0
3739 || ! host_integerp (elsz, 1)
3740 || TREE_INT_CST_LOW (elsz) == 0)
3743 nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
3744 if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
3747 for (i = 0; i < nr; ++i)
3753 && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
3754 || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
3757 if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
3759 else if (!(pushed = push_fields_onto_fieldstack
3760 (TREE_TYPE (type), fieldstack,
3761 offset + i * TREE_INT_CST_LOW (elsz), has_union,
3763 /* Empty structures may have actual size, like in C++. So
3764 see if we didn't push any subfields and the size is
3765 nonzero, push the field onto the stack */
3772 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3773 pair->type = TREE_TYPE (type);
3775 pair->decl = NULL_TREE;
3776 pair->offset = offset + i * TREE_INT_CST_LOW (elsz);
3777 pair->alias_set = -1;
3787 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
3788 if (TREE_CODE (field) == FIELD_DECL)
3794 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
3795 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
3798 if (!var_can_have_subvars (field))
3800 else if (!(pushed = push_fields_onto_fieldstack
3801 (TREE_TYPE (field), fieldstack,
3802 offset + bitpos_of_field (field), has_union,
3803 (DECL_NONADDRESSABLE_P (field)
3805 : TREE_TYPE (field))))
3806 && DECL_SIZE (field)
3807 && !integer_zerop (DECL_SIZE (field)))
3808 /* Empty structures may have actual size, like in C++. So
3809 see if we didn't push any subfields and the size is
3810 nonzero, push the field onto the stack */
3817 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
3818 pair->type = TREE_TYPE (field);
3819 pair->size = DECL_SIZE (field);
3821 pair->offset = offset + bitpos_of_field (field);
3822 if (DECL_NONADDRESSABLE_P (field))
3823 pair->alias_set = get_alias_set (addressable_type);
3825 pair->alias_set = -1;
3835 /* Create a constraint from ANYTHING variable to VI. */
3837 make_constraint_from_anything (varinfo_t vi)
3839 struct constraint_expr lhs, rhs;
3845 rhs.var = anything_id;
3847 rhs.type = ADDRESSOF;
3848 process_constraint (new_constraint (lhs, rhs));
3851 /* Count the number of arguments DECL has, and set IS_VARARGS to true
3852 if it is a varargs function. */
3855 count_num_arguments (tree decl, bool *is_varargs)
3860 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
3864 if (TREE_VALUE (t) == void_type_node)
3874 /* Creation function node for DECL, using NAME, and return the index
3875 of the variable we've created for the function. */
3878 create_function_info_for (tree decl, const char *name)
3880 unsigned int index = VEC_length (varinfo_t, varmap);
3884 bool is_varargs = false;
3886 /* Create the variable info. */
3888 vi = new_var_info (decl, index, name);
3893 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
3894 insert_vi_for_tree (vi->decl, vi);
3895 VEC_safe_push (varinfo_t, heap, varmap, vi);
3899 /* If it's varargs, we don't know how many arguments it has, so we
3906 vi->is_unknown_size_var = true;
3911 arg = DECL_ARGUMENTS (decl);
3913 /* Set up variables for each argument. */
3914 for (i = 1; i < vi->fullsize; i++)
3917 const char *newname;
3919 unsigned int newindex;
3920 tree argdecl = decl;
3925 newindex = VEC_length (varinfo_t, varmap);
3926 asprintf (&tempname, "%s.arg%d", name, i-1);
3927 newname = ggc_strdup (tempname);
3930 argvi = new_var_info (argdecl, newindex, newname);
3931 argvi->decl = argdecl;
3932 VEC_safe_push (varinfo_t, heap, varmap, argvi);
3935 argvi->fullsize = vi->fullsize;
3936 argvi->has_union = false;
3937 insert_into_field_list_sorted (vi, argvi);
3938 stats.total_vars ++;
3941 insert_vi_for_tree (arg, argvi);
3942 arg = TREE_CHAIN (arg);
3946 /* Create a variable for the return var. */
3947 if (DECL_RESULT (decl) != NULL
3948 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
3951 const char *newname;
3953 unsigned int newindex;
3954 tree resultdecl = decl;
3958 if (DECL_RESULT (decl))
3959 resultdecl = DECL_RESULT (decl);
3961 newindex = VEC_length (varinfo_t, varmap);
3962 asprintf (&tempname, "%s.result", name);
3963 newname = ggc_strdup (tempname);
3966 resultvi = new_var_info (resultdecl, newindex, newname);
3967 resultvi->decl = resultdecl;
3968 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
3969 resultvi->offset = i;
3971 resultvi->fullsize = vi->fullsize;
3972 resultvi->has_union = false;
3973 insert_into_field_list_sorted (vi, resultvi);
3974 stats.total_vars ++;
3975 if (DECL_RESULT (decl))
3976 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
3982 /* Return true if FIELDSTACK contains fields that overlap.
3983 FIELDSTACK is assumed to be sorted by offset. */
3986 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
3988 fieldoff_s *fo = NULL;
3990 HOST_WIDE_INT lastoffset = -1;
3992 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3994 if (fo->offset == lastoffset)
3996 lastoffset = fo->offset;
4001 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4002 This will also create any varinfo structures necessary for fields
4006 create_variable_info_for (tree decl, const char *name)
4008 unsigned int index = VEC_length (varinfo_t, varmap);
4010 tree decltype = TREE_TYPE (decl);
4011 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
4012 bool notokay = false;
4014 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
4015 VEC (fieldoff_s,heap) *fieldstack = NULL;
4017 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4018 return create_function_info_for (decl, name);
4020 hasunion = TREE_CODE (decltype) == UNION_TYPE
4021 || TREE_CODE (decltype) == QUAL_UNION_TYPE;
4022 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
4024 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion,
4028 VEC_free (fieldoff_s, heap, fieldstack);
4034 /* If the variable doesn't have subvars, we may end up needing to
4035 sort the field list and create fake variables for all the
4037 vi = new_var_info (decl, index, name);
4040 vi->has_union = hasunion;
4042 || TREE_CODE (declsize) != INTEGER_CST
4043 || TREE_CODE (decltype) == UNION_TYPE
4044 || TREE_CODE (decltype) == QUAL_UNION_TYPE)
4046 vi->is_unknown_size_var = true;
4052 vi->fullsize = TREE_INT_CST_LOW (declsize);
4053 vi->size = vi->fullsize;
4056 insert_vi_for_tree (vi->decl, vi);
4057 VEC_safe_push (varinfo_t, heap, varmap, vi);
4058 if (is_global && (!flag_whole_program || !in_ipa_mode))
4059 make_constraint_from_anything (vi);
4062 if (use_field_sensitive
4064 && !vi->is_unknown_size_var
4065 && var_can_have_subvars (decl)
4066 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4068 unsigned int newindex = VEC_length (varinfo_t, varmap);
4069 fieldoff_s *fo = NULL;
4072 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4075 || TREE_CODE (fo->size) != INTEGER_CST
4083 /* We can't sort them if we have a field with a variable sized type,
4084 which will make notokay = true. In that case, we are going to return
4085 without creating varinfos for the fields anyway, so sorting them is a
4089 sort_fieldstack (fieldstack);
4090 /* Due to some C++ FE issues, like PR 22488, we might end up
4091 what appear to be overlapping fields even though they,
4092 in reality, do not overlap. Until the C++ FE is fixed,
4093 we will simply disable field-sensitivity for these cases. */
4094 notokay = check_for_overlaps (fieldstack);
4098 if (VEC_length (fieldoff_s, fieldstack) != 0)
4099 fo = VEC_index (fieldoff_s, fieldstack, 0);
4101 if (fo == NULL || notokay)
4103 vi->is_unknown_size_var = 1;
4106 VEC_free (fieldoff_s, heap, fieldstack);
4110 vi->size = TREE_INT_CST_LOW (fo->size);
4111 vi->offset = fo->offset;
4112 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4113 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4117 const char *newname = "NULL";
4120 newindex = VEC_length (varinfo_t, varmap);
4124 asprintf (&tempname, "%s.%s",
4125 vi->name, alias_get_name (fo->decl));
4127 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC,
4128 vi->name, fo->offset);
4129 newname = ggc_strdup (tempname);
4132 newvi = new_var_info (decl, newindex, newname);
4133 newvi->offset = fo->offset;
4134 newvi->size = TREE_INT_CST_LOW (fo->size);
4135 newvi->fullsize = vi->fullsize;
4136 insert_into_field_list (vi, newvi);
4137 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4138 if (is_global && (!flag_whole_program || !in_ipa_mode))
4139 make_constraint_from_anything (newvi);
4143 VEC_free (fieldoff_s, heap, fieldstack);
4148 /* Print out the points-to solution for VAR to FILE. */
4151 dump_solution_for_var (FILE *file, unsigned int var)
4153 varinfo_t vi = get_varinfo (var);
4157 if (find (var) != var)
4159 varinfo_t vipt = get_varinfo (find (var));
4160 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4164 fprintf (file, "%s = { ", vi->name);
4165 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4167 fprintf (file, "%s ", get_varinfo (i)->name);
4169 fprintf (file, "}");
4170 if (vi->no_tbaa_pruning)
4171 fprintf (file, " no-tbaa-pruning");
4172 fprintf (file, "\n");
4176 /* Print the points-to solution for VAR to stdout. */
4179 debug_solution_for_var (unsigned int var)
4181 dump_solution_for_var (stdout, var);
4184 /* Create varinfo structures for all of the variables in the
4185 function for intraprocedural mode. */
4188 intra_create_variable_infos (void)
4191 struct constraint_expr lhs, rhs;
4193 /* For each incoming pointer argument arg, create the constraint ARG
4194 = ANYTHING or a dummy variable if flag_argument_noalias is set. */
4195 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4199 if (!could_have_pointers (t))
4202 /* If flag_argument_noalias is set, then function pointer
4203 arguments are guaranteed not to point to each other. In that
4204 case, create an artificial variable PARM_NOALIAS and the
4205 constraint ARG = &PARM_NOALIAS. */
4206 if (POINTER_TYPE_P (TREE_TYPE (t)) && flag_argument_noalias > 0)
4209 tree heapvar = heapvar_lookup (t);
4213 lhs.var = get_vi_for_tree (t)->id;
4215 if (heapvar == NULL_TREE)
4218 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4220 DECL_EXTERNAL (heapvar) = 1;
4221 if (gimple_referenced_vars (cfun))
4222 add_referenced_var (heapvar);
4224 heapvar_insert (t, heapvar);
4226 ann = get_var_ann (heapvar);
4227 if (flag_argument_noalias == 1)
4228 ann->noalias_state = NO_ALIAS;
4229 else if (flag_argument_noalias == 2)
4230 ann->noalias_state = NO_ALIAS_GLOBAL;
4231 else if (flag_argument_noalias == 3)
4232 ann->noalias_state = NO_ALIAS_ANYTHING;
4237 vi = get_vi_for_tree (heapvar);
4238 vi->is_artificial_var = 1;
4239 vi->is_heap_var = 1;
4241 rhs.type = ADDRESSOF;
4243 for (p = get_varinfo (lhs.var); p; p = p->next)
4245 struct constraint_expr temp = lhs;
4247 process_constraint (new_constraint (temp, rhs));
4252 varinfo_t arg_vi = get_vi_for_tree (t);
4254 for (p = arg_vi; p; p = p->next)
4255 make_constraint_from_anything (p);
4260 /* Structure used to put solution bitmaps in a hashtable so they can
4261 be shared among variables with the same points-to set. */
4263 typedef struct shared_bitmap_info
4267 } *shared_bitmap_info_t;
4268 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
4270 static htab_t shared_bitmap_table;
4272 /* Hash function for a shared_bitmap_info_t */
4275 shared_bitmap_hash (const void *p)
4277 const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
4278 return bi->hashcode;
4281 /* Equality function for two shared_bitmap_info_t's. */
4284 shared_bitmap_eq (const void *p1, const void *p2)
4286 const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
4287 const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
4288 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
4291 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4292 existing instance if there is one, NULL otherwise. */
4295 shared_bitmap_lookup (bitmap pt_vars)
4298 struct shared_bitmap_info sbi;
4300 sbi.pt_vars = pt_vars;
4301 sbi.hashcode = bitmap_hash (pt_vars);
4303 slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
4304 sbi.hashcode, NO_INSERT);
4308 return ((shared_bitmap_info_t) *slot)->pt_vars;
4312 /* Add a bitmap to the shared bitmap hashtable. */
4315 shared_bitmap_add (bitmap pt_vars)
4318 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
4320 sbi->pt_vars = pt_vars;
4321 sbi->hashcode = bitmap_hash (pt_vars);
4323 slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
4324 sbi->hashcode, INSERT);
4325 gcc_assert (!*slot);
4326 *slot = (void *) sbi;
4330 /* Set bits in INTO corresponding to the variable uids in solution set
4331 FROM, which came from variable PTR.
4332 For variables that are actually dereferenced, we also use type
4333 based alias analysis to prune the points-to sets.
4334 IS_DEREFED is true if PTR was directly dereferenced, which we use to
4335 help determine whether we are we are allowed to prune using TBAA.
4336 If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of
4340 set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed,
4341 bool no_tbaa_pruning)
4346 HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr));
4348 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4350 varinfo_t vi = get_varinfo (i);
4351 unsigned HOST_WIDE_INT var_alias_set;
4353 /* The only artificial variables that are allowed in a may-alias
4354 set are heap variables. */
4355 if (vi->is_artificial_var && !vi->is_heap_var)
4358 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
4360 /* Variables containing unions may need to be converted to
4361 their SFT's, because SFT's can have unions and we cannot. */
4362 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
4363 bitmap_set_bit (into, DECL_UID (sv->var));
4365 else if (TREE_CODE (vi->decl) == VAR_DECL
4366 || TREE_CODE (vi->decl) == PARM_DECL
4367 || TREE_CODE (vi->decl) == RESULT_DECL)
4369 if (var_can_have_subvars (vi->decl)
4370 && get_subvars_for_var (vi->decl))
4372 /* If VI->DECL is an aggregate for which we created
4373 SFTs, add the SFT corresponding to VI->OFFSET. */
4374 tree sft = get_subvar_at (vi->decl, vi->offset);
4377 var_alias_set = get_alias_set (sft);
4379 || (!is_derefed && !vi->directly_dereferenced)
4380 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
4381 bitmap_set_bit (into, DECL_UID (sft));
4386 /* Otherwise, just add VI->DECL to the alias set.
4387 Don't type prune artificial vars. */
4388 if (vi->is_artificial_var)
4389 bitmap_set_bit (into, DECL_UID (vi->decl));
4392 var_alias_set = get_alias_set (vi->decl);
4394 || (!is_derefed && !vi->directly_dereferenced)
4395 || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
4396 bitmap_set_bit (into, DECL_UID (vi->decl));
4404 static bool have_alias_info = false;
4406 /* The list of SMT's that are in use by our pointer variables. This
4407 is the set of SMT's for all pointers that can point to anything. */
4408 static bitmap used_smts;
4410 /* Due to the ordering of points-to set calculation and SMT
4411 calculation being a bit co-dependent, we can't just calculate SMT
4412 used info whenever we want, we have to calculate it around the time
4413 that find_what_p_points_to is called. */
4415 /* Mark which SMT's are in use by points-to anything variables. */
4418 set_used_smts (void)
4422 used_smts = BITMAP_ALLOC (&pta_obstack);
4424 for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); i++)
4426 tree var = vi->decl;
4429 struct ptr_info_def *pi = NULL;
4431 /* For parm decls, the pointer info may be under the default
4433 if (TREE_CODE (vi->decl) == PARM_DECL
4434 && gimple_default_def (cfun, var))
4435 pi = SSA_NAME_PTR_INFO (gimple_default_def (cfun, var));
4436 else if (TREE_CODE (var) == SSA_NAME)
4437 pi = SSA_NAME_PTR_INFO (var);
4439 /* Skip the special variables and those without their own
4441 if (vi->is_special_var || find (vi->id) != vi->id
4443 || (pi && !pi->is_dereferenced)
4444 || (TREE_CODE (var) == VAR_DECL && !may_be_aliased (var))
4445 || !POINTER_TYPE_P (TREE_TYPE (var)))
4448 if (TREE_CODE (var) == SSA_NAME)
4449 var = SSA_NAME_VAR (var);
4455 smt = va->symbol_mem_tag;
4456 if (smt && bitmap_bit_p (vi->solution, anything_id))
4457 bitmap_set_bit (used_smts, DECL_UID (smt));
4461 /* Merge the necessary SMT's into the bitmap INTO, which is
4462 P's varinfo. This involves merging all SMT's that are a subset of
4463 the SMT necessary for P. */
4466 merge_smts_into (tree p, bitmap solution)
4474 if (TREE_CODE (p) == SSA_NAME)
4475 var = SSA_NAME_VAR (p);
4477 smt = var_ann (var)->symbol_mem_tag;
4480 HOST_WIDE_INT smtset = get_alias_set (TREE_TYPE (smt));
4482 /* Need to set the SMT subsets first before this
4483 will work properly. */
4484 bitmap_set_bit (solution, DECL_UID (smt));
4485 EXECUTE_IF_SET_IN_BITMAP (used_smts, 0, i, bi)
4487 tree newsmt = referenced_var (i);
4488 tree newsmttype = TREE_TYPE (newsmt);
4490 if (alias_set_subset_of (get_alias_set (newsmttype),
4492 bitmap_set_bit (solution, i);
4495 aliases = MTAG_ALIASES (smt);
4497 bitmap_ior_into (solution, aliases);
4501 /* Given a pointer variable P, fill in its points-to set, or return
4503 Rather than return false for variables that point-to anything, we
4504 instead find the corresponding SMT, and merge in it's aliases. In
4505 addition to these aliases, we also set the bits for the SMT's
4506 themselves and their subsets, as SMT's are still in use by
4507 non-SSA_NAME's, and pruning may eliminate every one of their
4508 aliases. In such a case, if we did not include the right set of
4509 SMT's in the points-to set of the variable, we'd end up with
4510 statements that do not conflict but should. */
4513 find_what_p_points_to (tree p)
4518 if (!have_alias_info)
4521 /* For parameters, get at the points-to set for the actual parm
4523 if (TREE_CODE (p) == SSA_NAME
4524 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4525 && SSA_NAME_IS_DEFAULT_DEF (p))
4526 lookup_p = SSA_NAME_VAR (p);
4528 vi = lookup_vi_for_tree (lookup_p);
4531 if (vi->is_artificial_var)
4534 /* See if this is a field or a structure. */
4535 if (vi->size != vi->fullsize)
4537 /* Nothing currently asks about structure fields directly,
4538 but when they do, we need code here to hand back the
4540 if (!var_can_have_subvars (vi->decl)
4541 || get_subvars_for_var (vi->decl) == NULL)
4546 struct ptr_info_def *pi = get_ptr_info (p);
4549 bool was_pt_anything = false;
4550 bitmap finished_solution;
4553 if (!pi->is_dereferenced)
4556 /* This variable may have been collapsed, let's get the real
4558 vi = get_varinfo (find (vi->id));
4560 /* Translate artificial variables into SSA_NAME_PTR_INFO
4562 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4564 varinfo_t vi = get_varinfo (i);
4566 if (vi->is_artificial_var)
4568 /* FIXME. READONLY should be handled better so that
4569 flow insensitive aliasing can disregard writable
4571 if (vi->id == nothing_id)
4573 else if (vi->id == anything_id)
4574 was_pt_anything = 1;
4575 else if (vi->id == readonly_id)
4576 was_pt_anything = 1;
4577 else if (vi->id == integer_id)
4578 was_pt_anything = 1;
4579 else if (vi->is_heap_var)
4580 pi->pt_global_mem = 1;
4584 /* Share the final set of variables when possible. */
4586 finished_solution = BITMAP_GGC_ALLOC ();
4587 stats.points_to_sets_created++;
4589 /* Instead of using pt_anything, we merge in the SMT aliases
4590 for the underlying SMT. In addition, if they could have
4591 pointed to anything, they could point to global memory.
4592 But we cannot do that for ref-all pointers because these
4593 aliases have not been computed yet. */
4594 if (was_pt_anything)
4596 if (PTR_IS_REF_ALL (p))
4598 pi->pt_anything = 1;
4602 merge_smts_into (p, finished_solution);
4603 pi->pt_global_mem = 1;
4606 set_uids_in_ptset (vi->decl, finished_solution, vi->solution,
4607 vi->directly_dereferenced,
4608 vi->no_tbaa_pruning);
4609 result = shared_bitmap_lookup (finished_solution);
4613 shared_bitmap_add (finished_solution);
4614 pi->pt_vars = finished_solution;
4618 pi->pt_vars = result;
4619 bitmap_clear (finished_solution);
4622 if (bitmap_empty_p (pi->pt_vars))
4634 /* Dump points-to information to OUTFILE. */
4637 dump_sa_points_to_info (FILE *outfile)
4641 fprintf (outfile, "\nPoints-to sets\n\n");
4643 if (dump_flags & TDF_STATS)
4645 fprintf (outfile, "Stats:\n");
4646 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4647 fprintf (outfile, "Non-pointer vars: %d\n",
4648 stats.nonpointer_vars);
4649 fprintf (outfile, "Statically unified vars: %d\n",
4650 stats.unified_vars_static);
4651 fprintf (outfile, "Dynamically unified vars: %d\n",
4652 stats.unified_vars_dynamic);
4653 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4654 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4655 fprintf (outfile, "Number of implicit edges: %d\n",
4656 stats.num_implicit_edges);
4659 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4660 dump_solution_for_var (outfile, i);
4664 /* Debug points-to information to stderr. */
4667 debug_sa_points_to_info (void)
4669 dump_sa_points_to_info (stderr);
4673 /* Initialize the always-existing constraint variables for NULL
4674 ANYTHING, READONLY, and INTEGER */
4677 init_base_vars (void)
4679 struct constraint_expr lhs, rhs;
4681 /* Create the NULL variable, used to represent that a variable points
4683 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4684 var_nothing = new_var_info (nothing_tree, 0, "NULL");
4685 insert_vi_for_tree (nothing_tree, var_nothing);
4686 var_nothing->is_artificial_var = 1;
4687 var_nothing->offset = 0;
4688 var_nothing->size = ~0;
4689 var_nothing->fullsize = ~0;
4690 var_nothing->is_special_var = 1;
4692 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
4694 /* Create the ANYTHING variable, used to represent that a variable
4695 points to some unknown piece of memory. */
4696 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4697 var_anything = new_var_info (anything_tree, 1, "ANYTHING");
4698 insert_vi_for_tree (anything_tree, var_anything);
4699 var_anything->is_artificial_var = 1;
4700 var_anything->size = ~0;
4701 var_anything->offset = 0;
4702 var_anything->next = NULL;
4703 var_anything->fullsize = ~0;
4704 var_anything->is_special_var = 1;
4707 /* Anything points to anything. This makes deref constraints just
4708 work in the presence of linked list and other p = *p type loops,
4709 by saying that *ANYTHING = ANYTHING. */
4710 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
4712 lhs.var = anything_id;
4714 rhs.type = ADDRESSOF;
4715 rhs.var = anything_id;
4718 /* This specifically does not use process_constraint because
4719 process_constraint ignores all anything = anything constraints, since all
4720 but this one are redundant. */
4721 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
4723 /* Create the READONLY variable, used to represent that a variable
4724 points to readonly memory. */
4725 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
4726 var_readonly = new_var_info (readonly_tree, 2, "READONLY");
4727 var_readonly->is_artificial_var = 1;
4728 var_readonly->offset = 0;
4729 var_readonly->size = ~0;
4730 var_readonly->fullsize = ~0;
4731 var_readonly->next = NULL;
4732 var_readonly->is_special_var = 1;
4733 insert_vi_for_tree (readonly_tree, var_readonly);
4735 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
4737 /* readonly memory points to anything, in order to make deref
4738 easier. In reality, it points to anything the particular
4739 readonly variable can point to, but we don't track this
4742 lhs.var = readonly_id;
4744 rhs.type = ADDRESSOF;
4745 rhs.var = anything_id;
4748 process_constraint (new_constraint (lhs, rhs));
4750 /* Create the INTEGER variable, used to represent that a variable points
4752 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
4753 var_integer = new_var_info (integer_tree, 3, "INTEGER");
4754 insert_vi_for_tree (integer_tree, var_integer);
4755 var_integer->is_artificial_var = 1;
4756 var_integer->size = ~0;
4757 var_integer->fullsize = ~0;
4758 var_integer->offset = 0;
4759 var_integer->next = NULL;
4760 var_integer->is_special_var = 1;
4762 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
4764 /* INTEGER = ANYTHING, because we don't know where a dereference of
4765 a random integer will point to. */
4767 lhs.var = integer_id;
4769 rhs.type = ADDRESSOF;
4770 rhs.var = anything_id;
4772 process_constraint (new_constraint (lhs, rhs));
4775 /* Initialize things necessary to perform PTA */
4778 init_alias_vars (void)
4780 bitmap_obstack_initialize (&pta_obstack);
4781 bitmap_obstack_initialize (&oldpta_obstack);
4782 bitmap_obstack_initialize (&predbitmap_obstack);
4784 constraint_pool = create_alloc_pool ("Constraint pool",
4785 sizeof (struct constraint), 30);
4786 variable_info_pool = create_alloc_pool ("Variable info pool",
4787 sizeof (struct variable_info), 30);
4788 constraints = VEC_alloc (constraint_t, heap, 8);
4789 varmap = VEC_alloc (varinfo_t, heap, 8);
4790 vi_for_tree = pointer_map_create ();
4792 memset (&stats, 0, sizeof (stats));
4793 shared_bitmap_table = htab_create (511, shared_bitmap_hash,
4794 shared_bitmap_eq, free);
4798 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
4799 predecessor edges. */
4802 remove_preds_and_fake_succs (constraint_graph_t graph)
4806 /* Clear the implicit ref and address nodes from the successor
4808 for (i = 0; i < FIRST_REF_NODE; i++)
4810 if (graph->succs[i])
4811 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
4812 FIRST_REF_NODE * 2);
4815 /* Free the successor list for the non-ref nodes. */
4816 for (i = FIRST_REF_NODE; i < graph->size; i++)
4818 if (graph->succs[i])
4819 BITMAP_FREE (graph->succs[i]);
4822 /* Now reallocate the size of the successor list as, and blow away
4823 the predecessor bitmaps. */
4824 graph->size = VEC_length (varinfo_t, varmap);
4825 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
4827 free (graph->implicit_preds);
4828 graph->implicit_preds = NULL;
4829 free (graph->preds);
4830 graph->preds = NULL;
4831 bitmap_obstack_release (&predbitmap_obstack);
4834 /* Compute the set of variables we can't TBAA prune. */
4837 compute_tbaa_pruning (void)
4839 unsigned int size = VEC_length (varinfo_t, varmap);
4844 changed = sbitmap_alloc (size);
4845 sbitmap_zero (changed);
4847 /* Mark all initial no_tbaa_pruning nodes as changed. */
4849 for (i = 0; i < size; ++i)
4851 varinfo_t ivi = get_varinfo (i);
4853 if (find (i) == i && ivi->no_tbaa_pruning)
4856 if ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
4857 || VEC_length (constraint_t, graph->complex[i]) > 0)
4859 SET_BIT (changed, i);
4865 while (changed_count > 0)
4867 struct topo_info *ti = init_topo_info ();
4870 bitmap_obstack_initialize (&iteration_obstack);
4872 compute_topo_order (graph, ti);
4874 while (VEC_length (unsigned, ti->topo_order) != 0)
4878 i = VEC_pop (unsigned, ti->topo_order);
4880 /* If this variable is not a representative, skip it. */
4884 /* If the node has changed, we need to process the complex
4885 constraints and outgoing edges again. */
4886 if (TEST_BIT (changed, i))
4890 VEC(constraint_t,heap) *complex = graph->complex[i];
4892 RESET_BIT (changed, i);
4895 /* Process the complex copy constraints. */
4896 for (j = 0; VEC_iterate (constraint_t, complex, j, c); ++j)
4898 if (c->lhs.type == SCALAR && c->rhs.type == SCALAR)
4900 varinfo_t lhsvi = get_varinfo (find (c->lhs.var));
4902 if (!lhsvi->no_tbaa_pruning)
4904 lhsvi->no_tbaa_pruning = true;
4905 if (!TEST_BIT (changed, lhsvi->id))
4907 SET_BIT (changed, lhsvi->id);
4914 /* Propagate to all successors. */
4915 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
4917 unsigned int to = find (j);
4918 varinfo_t tovi = get_varinfo (to);
4920 /* Don't propagate to ourselves. */
4924 if (!tovi->no_tbaa_pruning)
4926 tovi->no_tbaa_pruning = true;
4927 if (!TEST_BIT (changed, to))
4929 SET_BIT (changed, to);
4937 free_topo_info (ti);
4938 bitmap_obstack_release (&iteration_obstack);
4941 sbitmap_free (changed);
4945 for (i = 0; i < size; ++i)
4947 varinfo_t ivi = get_varinfo (i);
4948 varinfo_t ivip = get_varinfo (find (i));
4950 if (ivip->no_tbaa_pruning)
4952 tree var = ivi->decl;
4954 if (TREE_CODE (var) == SSA_NAME)
4955 var = SSA_NAME_VAR (var);
4957 if (POINTER_TYPE_P (TREE_TYPE (var)))
4959 DECL_NO_TBAA_P (var) = 1;
4961 /* Tell the RTL layer that this pointer can alias
4963 DECL_POINTER_ALIAS_SET (var) = 0;
4970 /* Create points-to sets for the current function. See the comments
4971 at the start of the file for an algorithmic overview. */
4974 compute_points_to_sets (struct alias_info *ai)
4976 struct scc_info *si;
4979 timevar_push (TV_TREE_PTA);
4982 init_alias_heapvars ();
4984 intra_create_variable_infos ();
4986 /* Now walk all statements and derive aliases. */
4989 block_stmt_iterator bsi;
4992 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4994 if (is_gimple_reg (PHI_RESULT (phi)))
4996 find_func_aliases (phi);
4998 /* Update various related attributes like escaped
4999 addresses, pointer dereferences for loads and stores.
5000 This is used when creating name tags and alias
5002 update_alias_info (phi, ai);
5006 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
5008 tree stmt = bsi_stmt (bsi);
5010 find_func_aliases (stmt);
5012 /* Update various related attributes like escaped
5013 addresses, pointer dereferences for loads and stores.
5014 This is used when creating name tags and alias
5016 update_alias_info (stmt, ai);
5018 /* The information in CHANGE_DYNAMIC_TYPE_EXPR nodes has now
5019 been captured, and we can remove them. */
5020 if (TREE_CODE (stmt) == CHANGE_DYNAMIC_TYPE_EXPR)
5021 bsi_remove (&bsi, true);
5030 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5031 dump_constraints (dump_file);
5036 "\nCollapsing static cycles and doing variable "
5038 build_pred_graph ();
5039 si = perform_var_substitution (graph);
5040 move_complex_constraints (graph, si);
5041 free_var_substitution_info (si);
5043 build_succ_graph ();
5044 find_indirect_cycles (graph);
5046 /* Implicit nodes and predecessors are no longer necessary at this
5048 remove_preds_and_fake_succs (graph);
5051 fprintf (dump_file, "\nSolving graph:\n");
5053 solve_graph (graph);
5055 compute_tbaa_pruning ();
5058 dump_sa_points_to_info (dump_file);
5060 have_alias_info = true;
5062 timevar_pop (TV_TREE_PTA);
5066 /* Delete created points-to sets. */
5069 delete_points_to_sets (void)
5074 htab_delete (shared_bitmap_table);
5075 if (dump_file && (dump_flags & TDF_STATS))
5076 fprintf (dump_file, "Points to sets created:%d\n",
5077 stats.points_to_sets_created);
5079 pointer_map_destroy (vi_for_tree);
5080 bitmap_obstack_release (&pta_obstack);
5081 VEC_free (constraint_t, heap, constraints);
5083 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
5084 VEC_free (constraint_t, heap, graph->complex[i]);
5085 free (graph->complex);
5088 free (graph->succs);
5089 free (graph->indirect_cycles);
5092 VEC_free (varinfo_t, heap, varmap);
5093 free_alloc_pool (variable_info_pool);
5094 free_alloc_pool (constraint_pool);
5095 have_alias_info = false;
5098 /* Return true if we should execute IPA PTA. */
5102 return (flag_unit_at_a_time != 0
5104 /* Don't bother doing anything if the program has errors. */
5105 && !(errorcount || sorrycount));
5108 /* Execute the driver for IPA PTA. */
5110 ipa_pta_execute (void)
5112 struct cgraph_node *node;
5113 struct scc_info *si;
5116 init_alias_heapvars ();
5119 for (node = cgraph_nodes; node; node = node->next)
5121 if (!node->analyzed || cgraph_is_master_clone (node))
5125 varid = create_function_info_for (node->decl,
5126 cgraph_node_name (node));
5127 if (node->local.externally_visible)
5129 varinfo_t fi = get_varinfo (varid);
5130 for (; fi; fi = fi->next)
5131 make_constraint_from_anything (fi);
5135 for (node = cgraph_nodes; node; node = node->next)
5137 if (node->analyzed && cgraph_is_master_clone (node))
5139 struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
5141 tree old_func_decl = current_function_decl;
5144 "Generating constraints for %s\n",
5145 cgraph_node_name (node));
5147 current_function_decl = node->decl;
5149 FOR_EACH_BB_FN (bb, cfun)
5151 block_stmt_iterator bsi;
5154 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5156 if (is_gimple_reg (PHI_RESULT (phi)))
5158 find_func_aliases (phi);
5162 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
5164 tree stmt = bsi_stmt (bsi);
5165 find_func_aliases (stmt);
5168 current_function_decl = old_func_decl;
5173 /* Make point to anything. */
5181 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5182 dump_constraints (dump_file);
5187 "\nCollapsing static cycles and doing variable "
5190 build_pred_graph ();
5191 si = perform_var_substitution (graph);
5192 move_complex_constraints (graph, si);
5193 free_var_substitution_info (si);
5195 build_succ_graph ();
5196 find_indirect_cycles (graph);
5198 /* Implicit nodes and predecessors are no longer necessary at this
5200 remove_preds_and_fake_succs (graph);
5203 fprintf (dump_file, "\nSolving graph:\n");
5205 solve_graph (graph);
5208 dump_sa_points_to_info (dump_file);
5211 delete_alias_heapvars ();
5212 delete_points_to_sets ();
5216 struct tree_opt_pass pass_ipa_pta =
5219 gate_ipa_pta, /* gate */
5220 ipa_pta_execute, /* execute */
5223 0, /* static_pass_number */
5224 TV_IPA_PTA, /* tv_id */
5225 0, /* properties_required */
5226 0, /* properties_provided */
5227 0, /* properties_destroyed */
5228 0, /* todo_flags_start */
5229 0, /* todo_flags_finish */
5233 /* Initialize the heapvar for statement mapping. */
5235 init_alias_heapvars (void)
5237 if (!heapvar_for_stmt)
5238 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5243 delete_alias_heapvars (void)
5245 htab_delete (heapvar_for_stmt);
5246 heapvar_for_stmt = NULL;
5250 #include "gt-tree-ssa-structalias.h"