1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006, 2007, 2008, 2009 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"
36 #include "tree-flow.h"
37 #include "tree-inline.h"
40 #include "diagnostic.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 /* True if this is a variable created by the constraint analysis, such as
213 heap variables and constraints we had to break up. */
214 unsigned int is_artificial_var:1;
216 /* True if this is a special variable whose solution set should not be
218 unsigned int is_special_var:1;
220 /* True for variables whose size is not known or variable. */
221 unsigned int is_unknown_size_var:1;
223 /* True for (sub-)fields that represent a whole variable. */
224 unsigned int is_full_var : 1;
226 /* True if this is a heap variable. */
227 unsigned int is_heap_var:1;
229 /* True if we may not use TBAA to prune references to this
230 variable. This is used for C++ placement new. */
231 unsigned int no_tbaa_pruning : 1;
233 /* True if this field may contain pointers. */
234 unsigned int may_have_pointers : 1;
236 /* Variable id this was collapsed to due to type unsafety. Zero if
237 this variable was not collapsed. This should be unused completely
238 after build_succ_graph, or something is broken. */
239 unsigned int collapsed_to;
241 /* A link to the variable for the next field in this structure. */
242 struct variable_info *next;
244 /* Offset of this variable, in bits, from the base variable */
245 unsigned HOST_WIDE_INT offset;
247 /* Size of the variable, in bits. */
248 unsigned HOST_WIDE_INT size;
250 /* Full size of the base variable, in bits. */
251 unsigned HOST_WIDE_INT fullsize;
253 /* Name of this variable */
256 /* Tree that this variable is associated with. */
259 /* Points-to set for this variable. */
262 /* Old points-to set for this variable. */
265 typedef struct variable_info *varinfo_t;
267 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
268 static varinfo_t lookup_vi_for_tree (tree);
270 /* Pool of variable info structures. */
271 static alloc_pool variable_info_pool;
273 DEF_VEC_P(varinfo_t);
275 DEF_VEC_ALLOC_P(varinfo_t, heap);
277 /* Table of variable info structures for constraint variables.
278 Indexed directly by variable info id. */
279 static VEC(varinfo_t,heap) *varmap;
281 /* Return the varmap element N */
283 static inline varinfo_t
284 get_varinfo (unsigned int n)
286 return VEC_index (varinfo_t, varmap, n);
289 /* Return the varmap element N, following the collapsed_to link. */
291 static inline varinfo_t
292 get_varinfo_fc (unsigned int n)
294 varinfo_t v = VEC_index (varinfo_t, varmap, n);
296 if (v->collapsed_to != 0)
297 return get_varinfo (v->collapsed_to);
301 /* Static IDs for the special variables. */
302 enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
303 escaped_id = 3, nonlocal_id = 4, callused_id = 5,
304 storedanything_id = 6, integer_id = 7 };
306 /* Variable that represents the unknown pointer. */
307 static varinfo_t var_anything;
308 static tree anything_tree;
310 /* Variable that represents the NULL pointer. */
311 static varinfo_t var_nothing;
312 static tree nothing_tree;
314 /* Variable that represents read only memory. */
315 static varinfo_t var_readonly;
316 static tree readonly_tree;
318 /* Variable that represents escaped memory. */
319 static varinfo_t var_escaped;
320 static tree escaped_tree;
322 /* Variable that represents nonlocal memory. */
323 static varinfo_t var_nonlocal;
324 static tree nonlocal_tree;
326 /* Variable that represents call-used memory. */
327 static varinfo_t var_callused;
328 static tree callused_tree;
330 /* Variable that represents variables that are stored to anything. */
331 static varinfo_t var_storedanything;
332 static tree storedanything_tree;
334 /* Variable that represents integers. This is used for when people do things
336 static varinfo_t var_integer;
337 static tree integer_tree;
339 /* Lookup a heap var for FROM, and return it if we find one. */
342 heapvar_lookup (tree from)
344 struct tree_map *h, in;
347 h = (struct tree_map *) htab_find_with_hash (heapvar_for_stmt, &in,
348 htab_hash_pointer (from));
354 /* Insert a mapping FROM->TO in the heap var for statement
358 heapvar_insert (tree from, tree to)
363 h = GGC_NEW (struct tree_map);
364 h->hash = htab_hash_pointer (from);
367 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
368 *(struct tree_map **) loc = h;
371 /* Return a new variable info structure consisting for a variable
372 named NAME, and using constraint graph node NODE. */
375 new_var_info (tree t, unsigned int id, const char *name)
377 varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
383 ret->is_artificial_var = false;
384 ret->is_heap_var = false;
385 ret->is_special_var = false;
386 ret->is_unknown_size_var = false;
387 ret->is_full_var = false;
388 ret->may_have_pointers = true;
390 if (TREE_CODE (var) == SSA_NAME)
391 var = SSA_NAME_VAR (var);
392 ret->no_tbaa_pruning = (DECL_P (var)
393 && POINTER_TYPE_P (TREE_TYPE (var))
394 && DECL_NO_TBAA_P (var));
395 ret->solution = BITMAP_ALLOC (&pta_obstack);
396 ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
398 ret->collapsed_to = 0;
402 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
404 /* An expression that appears in a constraint. */
406 struct constraint_expr
408 /* Constraint type. */
409 constraint_expr_type type;
411 /* Variable we are referring to in the constraint. */
414 /* Offset, in bits, of this constraint from the beginning of
415 variables it ends up referring to.
417 IOW, in a deref constraint, we would deref, get the result set,
418 then add OFFSET to each member. */
419 unsigned HOST_WIDE_INT offset;
422 typedef struct constraint_expr ce_s;
424 DEF_VEC_ALLOC_O(ce_s, heap);
425 static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);
426 static void get_constraint_for (tree, VEC(ce_s, heap) **);
427 static void do_deref (VEC (ce_s, heap) **);
429 /* Our set constraints are made up of two constraint expressions, one
432 As described in the introduction, our set constraints each represent an
433 operation between set valued variables.
437 struct constraint_expr lhs;
438 struct constraint_expr rhs;
441 /* List of constraints that we use to build the constraint graph from. */
443 static VEC(constraint_t,heap) *constraints;
444 static alloc_pool constraint_pool;
448 DEF_VEC_ALLOC_I(int, heap);
450 /* The constraint graph is represented as an array of bitmaps
451 containing successor nodes. */
453 struct constraint_graph
455 /* Size of this graph, which may be different than the number of
456 nodes in the variable map. */
459 /* Explicit successors of each node. */
462 /* Implicit predecessors of each node (Used for variable
464 bitmap *implicit_preds;
466 /* Explicit predecessors of each node (Used for variable substitution). */
469 /* Indirect cycle representatives, or -1 if the node has no indirect
471 int *indirect_cycles;
473 /* Representative node for a node. rep[a] == a unless the node has
477 /* Equivalence class representative for a label. This is used for
478 variable substitution. */
481 /* Pointer equivalence label for a node. All nodes with the same
482 pointer equivalence label can be unified together at some point
483 (either during constraint optimization or after the constraint
487 /* Pointer equivalence representative for a label. This is used to
488 handle nodes that are pointer equivalent but not location
489 equivalent. We can unite these once the addressof constraints
490 are transformed into initial points-to sets. */
493 /* Pointer equivalence label for each node, used during variable
495 unsigned int *pointer_label;
497 /* Location equivalence label for each node, used during location
498 equivalence finding. */
499 unsigned int *loc_label;
501 /* Pointed-by set for each node, used during location equivalence
502 finding. This is pointed-by rather than pointed-to, because it
503 is constructed using the predecessor graph. */
506 /* Points to sets for pointer equivalence. This is *not* the actual
507 points-to sets for nodes. */
510 /* Bitmap of nodes where the bit is set if the node is a direct
511 node. Used for variable substitution. */
512 sbitmap direct_nodes;
514 /* Bitmap of nodes where the bit is set if the node is address
515 taken. Used for variable substitution. */
516 bitmap address_taken;
518 /* Vector of complex constraints for each graph node. Complex
519 constraints are those involving dereferences or offsets that are
521 VEC(constraint_t,heap) **complex;
524 static constraint_graph_t graph;
526 /* During variable substitution and the offline version of indirect
527 cycle finding, we create nodes to represent dereferences and
528 address taken constraints. These represent where these start and
530 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
531 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
533 /* Return the representative node for NODE, if NODE has been unioned
535 This function performs path compression along the way to finding
536 the representative. */
539 find (unsigned int node)
541 gcc_assert (node < graph->size);
542 if (graph->rep[node] != node)
543 return graph->rep[node] = find (graph->rep[node]);
547 /* Union the TO and FROM nodes to the TO nodes.
548 Note that at some point in the future, we may want to do
549 union-by-rank, in which case we are going to have to return the
550 node we unified to. */
553 unite (unsigned int to, unsigned int from)
555 gcc_assert (to < graph->size && from < graph->size);
556 if (to != from && graph->rep[from] != to)
558 graph->rep[from] = to;
564 /* Create a new constraint consisting of LHS and RHS expressions. */
567 new_constraint (const struct constraint_expr lhs,
568 const struct constraint_expr rhs)
570 constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
576 /* Print out constraint C to FILE. */
579 dump_constraint (FILE *file, constraint_t c)
581 if (c->lhs.type == ADDRESSOF)
583 else if (c->lhs.type == DEREF)
585 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
586 if (c->lhs.offset != 0)
587 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
588 fprintf (file, " = ");
589 if (c->rhs.type == ADDRESSOF)
591 else if (c->rhs.type == DEREF)
593 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
594 if (c->rhs.offset != 0)
595 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
596 fprintf (file, "\n");
599 /* Print out constraint C to stderr. */
602 debug_constraint (constraint_t c)
604 dump_constraint (stderr, c);
607 /* Print out all constraints to FILE */
610 dump_constraints (FILE *file)
614 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
615 dump_constraint (file, c);
618 /* Print out all constraints to stderr. */
621 debug_constraints (void)
623 dump_constraints (stderr);
626 /* Print out to FILE the edge in the constraint graph that is created by
627 constraint c. The edge may have a label, depending on the type of
628 constraint that it represents. If complex1, e.g: a = *b, then the label
629 is "=*", if complex2, e.g: *a = b, then the label is "*=", if
630 complex with an offset, e.g: a = b + 8, then the label is "+".
631 Otherwise the edge has no label. */
634 dump_constraint_edge (FILE *file, constraint_t c)
636 if (c->rhs.type != ADDRESSOF)
638 const char *src = get_varinfo_fc (c->rhs.var)->name;
639 const char *dst = get_varinfo_fc (c->lhs.var)->name;
640 fprintf (file, " \"%s\" -> \"%s\" ", src, dst);
641 /* Due to preprocessing of constraints, instructions like *a = *b are
642 illegal; thus, we do not have to handle such cases. */
643 if (c->lhs.type == DEREF)
644 fprintf (file, " [ label=\"*=\" ] ;\n");
645 else if (c->rhs.type == DEREF)
646 fprintf (file, " [ label=\"=*\" ] ;\n");
649 /* We must check the case where the constraint is an offset.
650 In this case, it is treated as a complex constraint. */
651 if (c->rhs.offset != c->lhs.offset)
652 fprintf (file, " [ label=\"+\" ] ;\n");
654 fprintf (file, " ;\n");
659 /* Print the constraint graph in dot format. */
662 dump_constraint_graph (FILE *file)
664 unsigned int i=0, size;
667 /* Only print the graph if it has already been initialized: */
671 /* Print the constraints used to produce the constraint graph. The
672 constraints will be printed as comments in the dot file: */
673 fprintf (file, "\n\n/* Constraints used in the constraint graph:\n");
674 dump_constraints (file);
675 fprintf (file, "*/\n");
677 /* Prints the header of the dot file: */
678 fprintf (file, "\n\n// The constraint graph in dot format:\n");
679 fprintf (file, "strict digraph {\n");
680 fprintf (file, " node [\n shape = box\n ]\n");
681 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
682 fprintf (file, "\n // List of nodes in the constraint graph:\n");
684 /* The next lines print the nodes in the graph. In order to get the
685 number of nodes in the graph, we must choose the minimum between the
686 vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
687 yet been initialized, then graph->size == 0, otherwise we must only
688 read nodes that have an entry in VEC (varinfo_t, varmap). */
689 size = VEC_length (varinfo_t, varmap);
690 size = size < graph->size ? size : graph->size;
691 for (i = 0; i < size; i++)
693 const char *name = get_varinfo_fc (graph->rep[i])->name;
694 fprintf (file, " \"%s\" ;\n", name);
697 /* Go over the list of constraints printing the edges in the constraint
699 fprintf (file, "\n // The constraint edges:\n");
700 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
702 dump_constraint_edge (file, c);
704 /* Prints the tail of the dot file. By now, only the closing bracket. */
705 fprintf (file, "}\n\n\n");
708 /* Print out the constraint graph to stderr. */
711 debug_constraint_graph (void)
713 dump_constraint_graph (stderr);
718 The solver is a simple worklist solver, that works on the following
721 sbitmap changed_nodes = all zeroes;
723 For each node that is not already collapsed:
725 set bit in changed nodes
727 while (changed_count > 0)
729 compute topological ordering for constraint graph
731 find and collapse cycles in the constraint graph (updating
732 changed if necessary)
734 for each node (n) in the graph in topological order:
737 Process each complex constraint associated with the node,
738 updating changed if necessary.
740 For each outgoing edge from n, propagate the solution from n to
741 the destination of the edge, updating changed as necessary.
745 /* Return true if two constraint expressions A and B are equal. */
748 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
750 return a.type == b.type && a.var == b.var && a.offset == b.offset;
753 /* Return true if constraint expression A is less than constraint expression
754 B. This is just arbitrary, but consistent, in order to give them an
758 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
760 if (a.type == b.type)
763 return a.offset < b.offset;
765 return a.var < b.var;
768 return a.type < b.type;
771 /* Return true if constraint A is less than constraint B. This is just
772 arbitrary, but consistent, in order to give them an ordering. */
775 constraint_less (const constraint_t a, const constraint_t b)
777 if (constraint_expr_less (a->lhs, b->lhs))
779 else if (constraint_expr_less (b->lhs, a->lhs))
782 return constraint_expr_less (a->rhs, b->rhs);
785 /* Return true if two constraints A and B are equal. */
788 constraint_equal (struct constraint a, struct constraint b)
790 return constraint_expr_equal (a.lhs, b.lhs)
791 && constraint_expr_equal (a.rhs, b.rhs);
795 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
798 constraint_vec_find (VEC(constraint_t,heap) *vec,
799 struct constraint lookfor)
807 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
808 if (place >= VEC_length (constraint_t, vec))
810 found = VEC_index (constraint_t, vec, place);
811 if (!constraint_equal (*found, lookfor))
816 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
819 constraint_set_union (VEC(constraint_t,heap) **to,
820 VEC(constraint_t,heap) **from)
825 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
827 if (constraint_vec_find (*to, *c) == NULL)
829 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
831 VEC_safe_insert (constraint_t, heap, *to, place, c);
836 /* Take a solution set SET, add OFFSET to each member of the set, and
837 overwrite SET with the result when done. */
840 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
842 bitmap result = BITMAP_ALLOC (&iteration_obstack);
846 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
848 varinfo_t vi = get_varinfo (i);
850 /* If this is a variable with just one field just set its bit
852 if (vi->is_artificial_var
853 || vi->is_unknown_size_var
855 bitmap_set_bit (result, i);
858 unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
859 varinfo_t v = first_vi_for_offset (vi, fieldoffset);
860 /* If the result is outside of the variable use the last field. */
864 while (v->next != NULL)
867 bitmap_set_bit (result, v->id);
868 /* If the result is not exactly at fieldoffset include the next
869 field as well. See get_constraint_for_ptr_offset for more
871 if (v->offset != fieldoffset
873 bitmap_set_bit (result, v->next->id);
877 bitmap_copy (set, result);
878 BITMAP_FREE (result);
881 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
885 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
888 return bitmap_ior_into (to, from);
894 tmp = BITMAP_ALLOC (&iteration_obstack);
895 bitmap_copy (tmp, from);
896 solution_set_add (tmp, inc);
897 res = bitmap_ior_into (to, tmp);
903 /* Insert constraint C into the list of complex constraints for graph
907 insert_into_complex (constraint_graph_t graph,
908 unsigned int var, constraint_t c)
910 VEC (constraint_t, heap) *complex = graph->complex[var];
911 unsigned int place = VEC_lower_bound (constraint_t, complex, c,
914 /* Only insert constraints that do not already exist. */
915 if (place >= VEC_length (constraint_t, complex)
916 || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
917 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
921 /* Condense two variable nodes into a single variable node, by moving
922 all associated info from SRC to TO. */
925 merge_node_constraints (constraint_graph_t graph, unsigned int to,
931 gcc_assert (find (from) == to);
933 /* Move all complex constraints from src node into to node */
934 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
936 /* In complex constraints for node src, we may have either
937 a = *src, and *src = a, or an offseted constraint which are
938 always added to the rhs node's constraints. */
940 if (c->rhs.type == DEREF)
942 else if (c->lhs.type == DEREF)
947 constraint_set_union (&graph->complex[to], &graph->complex[from]);
948 VEC_free (constraint_t, heap, graph->complex[from]);
949 graph->complex[from] = NULL;
953 /* Remove edges involving NODE from GRAPH. */
956 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
958 if (graph->succs[node])
959 BITMAP_FREE (graph->succs[node]);
962 /* Merge GRAPH nodes FROM and TO into node TO. */
965 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
968 if (graph->indirect_cycles[from] != -1)
970 /* If we have indirect cycles with the from node, and we have
971 none on the to node, the to node has indirect cycles from the
972 from node now that they are unified.
973 If indirect cycles exist on both, unify the nodes that they
974 are in a cycle with, since we know they are in a cycle with
976 if (graph->indirect_cycles[to] == -1)
977 graph->indirect_cycles[to] = graph->indirect_cycles[from];
980 /* Merge all the successor edges. */
981 if (graph->succs[from])
983 if (!graph->succs[to])
984 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
985 bitmap_ior_into (graph->succs[to],
989 clear_edges_for_node (graph, from);
993 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
994 it doesn't exist in the graph already. */
997 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1003 if (!graph->implicit_preds[to])
1004 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1006 if (bitmap_set_bit (graph->implicit_preds[to], from))
1007 stats.num_implicit_edges++;
1010 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1011 it doesn't exist in the graph already.
1012 Return false if the edge already existed, true otherwise. */
1015 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1018 if (!graph->preds[to])
1019 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1020 bitmap_set_bit (graph->preds[to], from);
1023 /* Add a graph edge to GRAPH, going from FROM to TO if
1024 it doesn't exist in the graph already.
1025 Return false if the edge already existed, true otherwise. */
1028 add_graph_edge (constraint_graph_t graph, unsigned int to,
1039 if (!graph->succs[from])
1040 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1041 if (bitmap_set_bit (graph->succs[from], to))
1044 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1052 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1055 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1058 return (graph->succs[dest]
1059 && bitmap_bit_p (graph->succs[dest], src));
1062 /* Initialize the constraint graph structure to contain SIZE nodes. */
1065 init_graph (unsigned int size)
1069 graph = XCNEW (struct constraint_graph);
1071 graph->succs = XCNEWVEC (bitmap, graph->size);
1072 graph->indirect_cycles = XNEWVEC (int, graph->size);
1073 graph->rep = XNEWVEC (unsigned int, graph->size);
1074 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
1075 graph->pe = XCNEWVEC (unsigned int, graph->size);
1076 graph->pe_rep = XNEWVEC (int, graph->size);
1078 for (j = 0; j < graph->size; j++)
1081 graph->pe_rep[j] = -1;
1082 graph->indirect_cycles[j] = -1;
1086 /* Build the constraint graph, adding only predecessor edges right now. */
1089 build_pred_graph (void)
1095 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1096 graph->preds = XCNEWVEC (bitmap, graph->size);
1097 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1098 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1099 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1100 graph->points_to = XCNEWVEC (bitmap, graph->size);
1101 graph->eq_rep = XNEWVEC (int, graph->size);
1102 graph->direct_nodes = sbitmap_alloc (graph->size);
1103 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1104 sbitmap_zero (graph->direct_nodes);
1106 for (j = 0; j < FIRST_REF_NODE; j++)
1108 if (!get_varinfo (j)->is_special_var)
1109 SET_BIT (graph->direct_nodes, j);
1112 for (j = 0; j < graph->size; j++)
1113 graph->eq_rep[j] = -1;
1115 for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
1116 graph->indirect_cycles[j] = -1;
1118 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1120 struct constraint_expr lhs = c->lhs;
1121 struct constraint_expr rhs = c->rhs;
1122 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
1123 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
1125 if (lhs.type == DEREF)
1128 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1129 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1131 else if (rhs.type == DEREF)
1134 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1135 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1137 RESET_BIT (graph->direct_nodes, lhsvar);
1139 else if (rhs.type == ADDRESSOF)
1144 if (graph->points_to[lhsvar] == NULL)
1145 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1146 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1148 if (graph->pointed_by[rhsvar] == NULL)
1149 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1150 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1152 /* Implicitly, *x = y */
1153 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1155 /* All related variables are no longer direct nodes. */
1156 RESET_BIT (graph->direct_nodes, rhsvar);
1157 v = get_varinfo (rhsvar);
1158 if (!v->is_full_var)
1160 v = lookup_vi_for_tree (v->decl);
1163 RESET_BIT (graph->direct_nodes, v->id);
1168 bitmap_set_bit (graph->address_taken, rhsvar);
1170 else if (lhsvar > anything_id
1171 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1174 add_pred_graph_edge (graph, lhsvar, rhsvar);
1175 /* Implicitly, *x = *y */
1176 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1177 FIRST_REF_NODE + rhsvar);
1179 else if (lhs.offset != 0 || rhs.offset != 0)
1181 if (rhs.offset != 0)
1182 RESET_BIT (graph->direct_nodes, lhs.var);
1183 else if (lhs.offset != 0)
1184 RESET_BIT (graph->direct_nodes, rhs.var);
1189 /* Build the constraint graph, adding successor edges. */
1192 build_succ_graph (void)
1197 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1199 struct constraint_expr lhs;
1200 struct constraint_expr rhs;
1201 unsigned int lhsvar;
1202 unsigned int rhsvar;
1209 lhsvar = find (get_varinfo_fc (lhs.var)->id);
1210 rhsvar = find (get_varinfo_fc (rhs.var)->id);
1212 if (lhs.type == DEREF)
1214 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1215 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1217 else if (rhs.type == DEREF)
1219 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1220 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1222 else if (rhs.type == ADDRESSOF)
1225 gcc_assert (find (get_varinfo_fc (rhs.var)->id)
1226 == get_varinfo_fc (rhs.var)->id);
1227 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1229 else if (lhsvar > anything_id
1230 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1232 add_graph_edge (graph, lhsvar, rhsvar);
1236 /* Add edges from STOREDANYTHING to all non-direct nodes. */
1237 t = find (storedanything_id);
1238 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1240 if (!TEST_BIT (graph->direct_nodes, i))
1241 add_graph_edge (graph, find (i), t);
1246 /* Changed variables on the last iteration. */
1247 static unsigned int changed_count;
1248 static sbitmap changed;
1250 DEF_VEC_I(unsigned);
1251 DEF_VEC_ALLOC_I(unsigned,heap);
1254 /* Strongly Connected Component visitation info. */
1261 unsigned int *node_mapping;
1263 VEC(unsigned,heap) *scc_stack;
1267 /* Recursive routine to find strongly connected components in GRAPH.
1268 SI is the SCC info to store the information in, and N is the id of current
1269 graph node we are processing.
1271 This is Tarjan's strongly connected component finding algorithm, as
1272 modified by Nuutila to keep only non-root nodes on the stack.
1273 The algorithm can be found in "On finding the strongly connected
1274 connected components in a directed graph" by Esko Nuutila and Eljas
1275 Soisalon-Soininen, in Information Processing Letters volume 49,
1276 number 1, pages 9-14. */
1279 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1283 unsigned int my_dfs;
1285 SET_BIT (si->visited, n);
1286 si->dfs[n] = si->current_index ++;
1287 my_dfs = si->dfs[n];
1289 /* Visit all the successors. */
1290 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1294 if (i > LAST_REF_NODE)
1298 if (TEST_BIT (si->deleted, w))
1301 if (!TEST_BIT (si->visited, w))
1302 scc_visit (graph, si, w);
1304 unsigned int t = find (w);
1305 unsigned int nnode = find (n);
1306 gcc_assert (nnode == n);
1308 if (si->dfs[t] < si->dfs[nnode])
1309 si->dfs[n] = si->dfs[t];
1313 /* See if any components have been identified. */
1314 if (si->dfs[n] == my_dfs)
1316 if (VEC_length (unsigned, si->scc_stack) > 0
1317 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1319 bitmap scc = BITMAP_ALLOC (NULL);
1320 bool have_ref_node = n >= FIRST_REF_NODE;
1321 unsigned int lowest_node;
1324 bitmap_set_bit (scc, n);
1326 while (VEC_length (unsigned, si->scc_stack) != 0
1327 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1329 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1331 bitmap_set_bit (scc, w);
1332 if (w >= FIRST_REF_NODE)
1333 have_ref_node = true;
1336 lowest_node = bitmap_first_set_bit (scc);
1337 gcc_assert (lowest_node < FIRST_REF_NODE);
1339 /* Collapse the SCC nodes into a single node, and mark the
1341 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1343 if (i < FIRST_REF_NODE)
1345 if (unite (lowest_node, i))
1346 unify_nodes (graph, lowest_node, i, false);
1350 unite (lowest_node, i);
1351 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1355 SET_BIT (si->deleted, n);
1358 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1361 /* Unify node FROM into node TO, updating the changed count if
1362 necessary when UPDATE_CHANGED is true. */
1365 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1366 bool update_changed)
1369 gcc_assert (to != from && find (to) == to);
1370 if (dump_file && (dump_flags & TDF_DETAILS))
1371 fprintf (dump_file, "Unifying %s to %s\n",
1372 get_varinfo (from)->name,
1373 get_varinfo (to)->name);
1376 stats.unified_vars_dynamic++;
1378 stats.unified_vars_static++;
1380 merge_graph_nodes (graph, to, from);
1381 merge_node_constraints (graph, to, from);
1383 if (get_varinfo (from)->no_tbaa_pruning)
1384 get_varinfo (to)->no_tbaa_pruning = true;
1386 /* Mark TO as changed if FROM was changed. If TO was already marked
1387 as changed, decrease the changed count. */
1389 if (update_changed && TEST_BIT (changed, from))
1391 RESET_BIT (changed, from);
1392 if (!TEST_BIT (changed, to))
1393 SET_BIT (changed, to);
1396 gcc_assert (changed_count > 0);
1400 if (get_varinfo (from)->solution)
1402 /* If the solution changes because of the merging, we need to mark
1403 the variable as changed. */
1404 if (bitmap_ior_into (get_varinfo (to)->solution,
1405 get_varinfo (from)->solution))
1407 if (update_changed && !TEST_BIT (changed, to))
1409 SET_BIT (changed, to);
1414 BITMAP_FREE (get_varinfo (from)->solution);
1415 BITMAP_FREE (get_varinfo (from)->oldsolution);
1417 if (stats.iterations > 0)
1419 BITMAP_FREE (get_varinfo (to)->oldsolution);
1420 get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1423 if (valid_graph_edge (graph, to, to))
1425 if (graph->succs[to])
1426 bitmap_clear_bit (graph->succs[to], to);
1430 /* Information needed to compute the topological ordering of a graph. */
1434 /* sbitmap of visited nodes. */
1436 /* Array that stores the topological order of the graph, *in
1438 VEC(unsigned,heap) *topo_order;
1442 /* Initialize and return a topological info structure. */
1444 static struct topo_info *
1445 init_topo_info (void)
1447 size_t size = graph->size;
1448 struct topo_info *ti = XNEW (struct topo_info);
1449 ti->visited = sbitmap_alloc (size);
1450 sbitmap_zero (ti->visited);
1451 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1456 /* Free the topological sort info pointed to by TI. */
1459 free_topo_info (struct topo_info *ti)
1461 sbitmap_free (ti->visited);
1462 VEC_free (unsigned, heap, ti->topo_order);
1466 /* Visit the graph in topological order, and store the order in the
1467 topo_info structure. */
1470 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1476 SET_BIT (ti->visited, n);
1478 if (graph->succs[n])
1479 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1481 if (!TEST_BIT (ti->visited, j))
1482 topo_visit (graph, ti, j);
1485 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1488 /* Return true if variable N + OFFSET is a legal field of N. */
1491 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1493 varinfo_t ninfo = get_varinfo (n);
1495 /* For things we've globbed to single variables, any offset into the
1496 variable acts like the entire variable, so that it becomes offset
1498 if (ninfo->is_special_var
1499 || ninfo->is_artificial_var
1500 || ninfo->is_unknown_size_var
1501 || ninfo->is_full_var)
1506 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1509 /* Process a constraint C that represents x = *y, using DELTA as the
1510 starting solution. */
1513 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1516 unsigned int lhs = c->lhs.var;
1518 bitmap sol = get_varinfo (lhs)->solution;
1522 /* For x = *ESCAPED and x = *CALLUSED we want to compute the
1523 reachability set of the rhs var. As a pointer to a sub-field
1524 of a variable can also reach all other fields of the variable
1525 we simply have to expand the solution to contain all sub-fields
1526 if one sub-field is contained. */
1527 if (c->rhs.var == find (escaped_id)
1528 || c->rhs.var == find (callused_id))
1531 /* In a first pass record all variables we need to add all
1532 sub-fields off. This avoids quadratic behavior. */
1533 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1535 varinfo_t v = get_varinfo (j);
1539 v = lookup_vi_for_tree (v->decl);
1540 if (v->next != NULL)
1543 vars = BITMAP_ALLOC (NULL);
1544 bitmap_set_bit (vars, v->id);
1547 /* In the second pass now do the addition to the solution and
1548 to speed up solving add it to the delta as well. */
1551 EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
1553 varinfo_t v = get_varinfo (j);
1554 for (; v != NULL; v = v->next)
1556 if (bitmap_set_bit (sol, v->id))
1559 bitmap_set_bit (delta, v->id);
1567 if (bitmap_bit_p (delta, anything_id))
1569 flag |= bitmap_set_bit (sol, anything_id);
1573 /* For each variable j in delta (Sol(y)), add
1574 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1575 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1577 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1578 if (type_safe (j, &roffset))
1581 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1584 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1585 /* If the access is outside of the variable we can ignore it. */
1590 /* Adding edges from the special vars is pointless.
1591 They don't have sets that can change. */
1592 if (get_varinfo (t)->is_special_var)
1593 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1594 /* Merging the solution from ESCAPED needlessly increases
1595 the set. Use ESCAPED as representative instead.
1596 Same for CALLUSED. */
1597 else if (get_varinfo (t)->id == find (escaped_id))
1598 flag |= bitmap_set_bit (sol, escaped_id);
1599 else if (get_varinfo (t)->id == find (callused_id))
1600 flag |= bitmap_set_bit (sol, callused_id);
1601 else if (add_graph_edge (graph, lhs, t))
1602 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1607 /* If the LHS solution changed, mark the var as changed. */
1610 get_varinfo (lhs)->solution = sol;
1611 if (!TEST_BIT (changed, lhs))
1613 SET_BIT (changed, lhs);
1619 /* Process a constraint C that represents *x = y. */
1622 do_ds_constraint (constraint_t c, bitmap delta)
1624 unsigned int rhs = c->rhs.var;
1625 bitmap sol = get_varinfo (rhs)->solution;
1629 /* Our IL does not allow this. */
1630 gcc_assert (c->rhs.offset == 0);
1632 /* If the solution of y contains ANYTHING simply use the ANYTHING
1633 solution. This avoids needlessly increasing the points-to sets. */
1634 if (bitmap_bit_p (sol, anything_id))
1635 sol = get_varinfo (find (anything_id))->solution;
1637 /* If the solution for x contains ANYTHING we have to merge the
1638 solution of y into all pointer variables which we do via
1640 if (bitmap_bit_p (delta, anything_id))
1642 unsigned t = find (storedanything_id);
1643 if (add_graph_edge (graph, t, rhs))
1645 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1647 if (!TEST_BIT (changed, t))
1649 SET_BIT (changed, t);
1657 /* For each member j of delta (Sol(x)), add an edge from y to j and
1658 union Sol(y) into Sol(j) */
1659 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1661 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1662 if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
1666 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1668 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1669 /* If the access is outside of the variable we can ignore it. */
1673 if (v->may_have_pointers)
1676 if (add_graph_edge (graph, t, rhs))
1678 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1681 sol = get_varinfo (rhs)->solution;
1682 if (!TEST_BIT (changed, t))
1684 SET_BIT (changed, t);
1694 /* Handle a non-simple (simple meaning requires no iteration),
1695 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1698 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1700 if (c->lhs.type == DEREF)
1702 if (c->rhs.type == ADDRESSOF)
1709 do_ds_constraint (c, delta);
1712 else if (c->rhs.type == DEREF)
1715 if (!(get_varinfo (c->lhs.var)->is_special_var))
1716 do_sd_constraint (graph, c, delta);
1724 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1725 solution = get_varinfo (c->rhs.var)->solution;
1726 tmp = get_varinfo (c->lhs.var)->solution;
1728 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1732 get_varinfo (c->lhs.var)->solution = tmp;
1733 if (!TEST_BIT (changed, c->lhs.var))
1735 SET_BIT (changed, c->lhs.var);
1742 /* Initialize and return a new SCC info structure. */
1744 static struct scc_info *
1745 init_scc_info (size_t size)
1747 struct scc_info *si = XNEW (struct scc_info);
1750 si->current_index = 0;
1751 si->visited = sbitmap_alloc (size);
1752 sbitmap_zero (si->visited);
1753 si->deleted = sbitmap_alloc (size);
1754 sbitmap_zero (si->deleted);
1755 si->node_mapping = XNEWVEC (unsigned int, size);
1756 si->dfs = XCNEWVEC (unsigned int, size);
1758 for (i = 0; i < size; i++)
1759 si->node_mapping[i] = i;
1761 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1765 /* Free an SCC info structure pointed to by SI */
1768 free_scc_info (struct scc_info *si)
1770 sbitmap_free (si->visited);
1771 sbitmap_free (si->deleted);
1772 free (si->node_mapping);
1774 VEC_free (unsigned, heap, si->scc_stack);
1779 /* Find indirect cycles in GRAPH that occur, using strongly connected
1780 components, and note them in the indirect cycles map.
1782 This technique comes from Ben Hardekopf and Calvin Lin,
1783 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1784 Lines of Code", submitted to PLDI 2007. */
1787 find_indirect_cycles (constraint_graph_t graph)
1790 unsigned int size = graph->size;
1791 struct scc_info *si = init_scc_info (size);
1793 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1794 if (!TEST_BIT (si->visited, i) && find (i) == i)
1795 scc_visit (graph, si, i);
1800 /* Compute a topological ordering for GRAPH, and store the result in the
1801 topo_info structure TI. */
1804 compute_topo_order (constraint_graph_t graph,
1805 struct topo_info *ti)
1808 unsigned int size = graph->size;
1810 for (i = 0; i != size; ++i)
1811 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1812 topo_visit (graph, ti, i);
1815 /* Structure used to for hash value numbering of pointer equivalence
1818 typedef struct equiv_class_label
1821 unsigned int equivalence_class;
1823 } *equiv_class_label_t;
1824 typedef const struct equiv_class_label *const_equiv_class_label_t;
1826 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1828 static htab_t pointer_equiv_class_table;
1830 /* A hashtable for mapping a bitmap of labels->location equivalence
1832 static htab_t location_equiv_class_table;
1834 /* Hash function for a equiv_class_label_t */
1837 equiv_class_label_hash (const void *p)
1839 const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
1840 return ecl->hashcode;
1843 /* Equality function for two equiv_class_label_t's. */
1846 equiv_class_label_eq (const void *p1, const void *p2)
1848 const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
1849 const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
1850 return bitmap_equal_p (eql1->labels, eql2->labels);
1853 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
1857 equiv_class_lookup (htab_t table, bitmap labels)
1860 struct equiv_class_label ecl;
1862 ecl.labels = labels;
1863 ecl.hashcode = bitmap_hash (labels);
1865 slot = htab_find_slot_with_hash (table, &ecl,
1866 ecl.hashcode, NO_INSERT);
1870 return ((equiv_class_label_t) *slot)->equivalence_class;
1874 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
1878 equiv_class_add (htab_t table, unsigned int equivalence_class,
1882 equiv_class_label_t ecl = XNEW (struct equiv_class_label);
1884 ecl->labels = labels;
1885 ecl->equivalence_class = equivalence_class;
1886 ecl->hashcode = bitmap_hash (labels);
1888 slot = htab_find_slot_with_hash (table, ecl,
1889 ecl->hashcode, INSERT);
1890 gcc_assert (!*slot);
1891 *slot = (void *) ecl;
1894 /* Perform offline variable substitution.
1896 This is a worst case quadratic time way of identifying variables
1897 that must have equivalent points-to sets, including those caused by
1898 static cycles, and single entry subgraphs, in the constraint graph.
1900 The technique is described in "Exploiting Pointer and Location
1901 Equivalence to Optimize Pointer Analysis. In the 14th International
1902 Static Analysis Symposium (SAS), August 2007." It is known as the
1903 "HU" algorithm, and is equivalent to value numbering the collapsed
1904 constraint graph including evaluating unions.
1906 The general method of finding equivalence classes is as follows:
1907 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1908 Initialize all non-REF nodes to be direct nodes.
1909 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1911 For each constraint containing the dereference, we also do the same
1914 We then compute SCC's in the graph and unify nodes in the same SCC,
1917 For each non-collapsed node x:
1918 Visit all unvisited explicit incoming edges.
1919 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1921 Lookup the equivalence class for pts(x).
1922 If we found one, equivalence_class(x) = found class.
1923 Otherwise, equivalence_class(x) = new class, and new_class is
1924 added to the lookup table.
1926 All direct nodes with the same equivalence class can be replaced
1927 with a single representative node.
1928 All unlabeled nodes (label == 0) are not pointers and all edges
1929 involving them can be eliminated.
1930 We perform these optimizations during rewrite_constraints
1932 In addition to pointer equivalence class finding, we also perform
1933 location equivalence class finding. This is the set of variables
1934 that always appear together in points-to sets. We use this to
1935 compress the size of the points-to sets. */
1937 /* Current maximum pointer equivalence class id. */
1938 static int pointer_equiv_class;
1940 /* Current maximum location equivalence class id. */
1941 static int location_equiv_class;
1943 /* Recursive routine to find strongly connected components in GRAPH,
1944 and label it's nodes with DFS numbers. */
1947 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1951 unsigned int my_dfs;
1953 gcc_assert (si->node_mapping[n] == n);
1954 SET_BIT (si->visited, n);
1955 si->dfs[n] = si->current_index ++;
1956 my_dfs = si->dfs[n];
1958 /* Visit all the successors. */
1959 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1961 unsigned int w = si->node_mapping[i];
1963 if (TEST_BIT (si->deleted, w))
1966 if (!TEST_BIT (si->visited, w))
1967 condense_visit (graph, si, w);
1969 unsigned int t = si->node_mapping[w];
1970 unsigned int nnode = si->node_mapping[n];
1971 gcc_assert (nnode == n);
1973 if (si->dfs[t] < si->dfs[nnode])
1974 si->dfs[n] = si->dfs[t];
1978 /* Visit all the implicit predecessors. */
1979 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1981 unsigned int w = si->node_mapping[i];
1983 if (TEST_BIT (si->deleted, w))
1986 if (!TEST_BIT (si->visited, w))
1987 condense_visit (graph, si, w);
1989 unsigned int t = si->node_mapping[w];
1990 unsigned int nnode = si->node_mapping[n];
1991 gcc_assert (nnode == n);
1993 if (si->dfs[t] < si->dfs[nnode])
1994 si->dfs[n] = si->dfs[t];
1998 /* See if any components have been identified. */
1999 if (si->dfs[n] == my_dfs)
2001 while (VEC_length (unsigned, si->scc_stack) != 0
2002 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
2004 unsigned int w = VEC_pop (unsigned, si->scc_stack);
2005 si->node_mapping[w] = n;
2007 if (!TEST_BIT (graph->direct_nodes, w))
2008 RESET_BIT (graph->direct_nodes, n);
2010 /* Unify our nodes. */
2011 if (graph->preds[w])
2013 if (!graph->preds[n])
2014 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2015 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2017 if (graph->implicit_preds[w])
2019 if (!graph->implicit_preds[n])
2020 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2021 bitmap_ior_into (graph->implicit_preds[n],
2022 graph->implicit_preds[w]);
2024 if (graph->points_to[w])
2026 if (!graph->points_to[n])
2027 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2028 bitmap_ior_into (graph->points_to[n],
2029 graph->points_to[w]);
2032 SET_BIT (si->deleted, n);
2035 VEC_safe_push (unsigned, heap, si->scc_stack, n);
2038 /* Label pointer equivalences. */
2041 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2045 SET_BIT (si->visited, n);
2047 if (!graph->points_to[n])
2048 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2050 /* Label and union our incoming edges's points to sets. */
2051 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2053 unsigned int w = si->node_mapping[i];
2054 if (!TEST_BIT (si->visited, w))
2055 label_visit (graph, si, w);
2057 /* Skip unused edges */
2058 if (w == n || graph->pointer_label[w] == 0)
2061 if (graph->points_to[w])
2062 bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
2064 /* Indirect nodes get fresh variables. */
2065 if (!TEST_BIT (graph->direct_nodes, n))
2066 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2068 if (!bitmap_empty_p (graph->points_to[n]))
2070 unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
2071 graph->points_to[n]);
2074 label = pointer_equiv_class++;
2075 equiv_class_add (pointer_equiv_class_table,
2076 label, graph->points_to[n]);
2078 graph->pointer_label[n] = label;
2082 /* Perform offline variable substitution, discovering equivalence
2083 classes, and eliminating non-pointer variables. */
2085 static struct scc_info *
2086 perform_var_substitution (constraint_graph_t graph)
2089 unsigned int size = graph->size;
2090 struct scc_info *si = init_scc_info (size);
2092 bitmap_obstack_initialize (&iteration_obstack);
2093 pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
2094 equiv_class_label_eq, free);
2095 location_equiv_class_table = htab_create (511, equiv_class_label_hash,
2096 equiv_class_label_eq, free);
2097 pointer_equiv_class = 1;
2098 location_equiv_class = 1;
2100 /* Condense the nodes, which means to find SCC's, count incoming
2101 predecessors, and unite nodes in SCC's. */
2102 for (i = 0; i < FIRST_REF_NODE; i++)
2103 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2104 condense_visit (graph, si, si->node_mapping[i]);
2106 sbitmap_zero (si->visited);
2107 /* Actually the label the nodes for pointer equivalences */
2108 for (i = 0; i < FIRST_REF_NODE; i++)
2109 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2110 label_visit (graph, si, si->node_mapping[i]);
2112 /* Calculate location equivalence labels. */
2113 for (i = 0; i < FIRST_REF_NODE; i++)
2120 if (!graph->pointed_by[i])
2122 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2124 /* Translate the pointed-by mapping for pointer equivalence
2126 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2128 bitmap_set_bit (pointed_by,
2129 graph->pointer_label[si->node_mapping[j]]);
2131 /* The original pointed_by is now dead. */
2132 BITMAP_FREE (graph->pointed_by[i]);
2134 /* Look up the location equivalence label if one exists, or make
2136 label = equiv_class_lookup (location_equiv_class_table,
2140 label = location_equiv_class++;
2141 equiv_class_add (location_equiv_class_table,
2146 if (dump_file && (dump_flags & TDF_DETAILS))
2147 fprintf (dump_file, "Found location equivalence for node %s\n",
2148 get_varinfo (i)->name);
2149 BITMAP_FREE (pointed_by);
2151 graph->loc_label[i] = label;
2155 if (dump_file && (dump_flags & TDF_DETAILS))
2156 for (i = 0; i < FIRST_REF_NODE; i++)
2158 bool direct_node = TEST_BIT (graph->direct_nodes, i);
2160 "Equivalence classes for %s node id %d:%s are pointer: %d"
2162 direct_node ? "Direct node" : "Indirect node", i,
2163 get_varinfo (i)->name,
2164 graph->pointer_label[si->node_mapping[i]],
2165 graph->loc_label[si->node_mapping[i]]);
2168 /* Quickly eliminate our non-pointer variables. */
2170 for (i = 0; i < FIRST_REF_NODE; i++)
2172 unsigned int node = si->node_mapping[i];
2174 if (graph->pointer_label[node] == 0)
2176 if (dump_file && (dump_flags & TDF_DETAILS))
2178 "%s is a non-pointer variable, eliminating edges.\n",
2179 get_varinfo (node)->name);
2180 stats.nonpointer_vars++;
2181 clear_edges_for_node (graph, node);
2188 /* Free information that was only necessary for variable
2192 free_var_substitution_info (struct scc_info *si)
2195 free (graph->pointer_label);
2196 free (graph->loc_label);
2197 free (graph->pointed_by);
2198 free (graph->points_to);
2199 free (graph->eq_rep);
2200 sbitmap_free (graph->direct_nodes);
2201 htab_delete (pointer_equiv_class_table);
2202 htab_delete (location_equiv_class_table);
2203 bitmap_obstack_release (&iteration_obstack);
2206 /* Return an existing node that is equivalent to NODE, which has
2207 equivalence class LABEL, if one exists. Return NODE otherwise. */
2210 find_equivalent_node (constraint_graph_t graph,
2211 unsigned int node, unsigned int label)
2213 /* If the address version of this variable is unused, we can
2214 substitute it for anything else with the same label.
2215 Otherwise, we know the pointers are equivalent, but not the
2216 locations, and we can unite them later. */
2218 if (!bitmap_bit_p (graph->address_taken, node))
2220 gcc_assert (label < graph->size);
2222 if (graph->eq_rep[label] != -1)
2224 /* Unify the two variables since we know they are equivalent. */
2225 if (unite (graph->eq_rep[label], node))
2226 unify_nodes (graph, graph->eq_rep[label], node, false);
2227 return graph->eq_rep[label];
2231 graph->eq_rep[label] = node;
2232 graph->pe_rep[label] = node;
2237 gcc_assert (label < graph->size);
2238 graph->pe[node] = label;
2239 if (graph->pe_rep[label] == -1)
2240 graph->pe_rep[label] = node;
2246 /* Unite pointer equivalent but not location equivalent nodes in
2247 GRAPH. This may only be performed once variable substitution is
2251 unite_pointer_equivalences (constraint_graph_t graph)
2255 /* Go through the pointer equivalences and unite them to their
2256 representative, if they aren't already. */
2257 for (i = 0; i < FIRST_REF_NODE; i++)
2259 unsigned int label = graph->pe[i];
2262 int label_rep = graph->pe_rep[label];
2264 if (label_rep == -1)
2267 label_rep = find (label_rep);
2268 if (label_rep >= 0 && unite (label_rep, find (i)))
2269 unify_nodes (graph, label_rep, i, false);
2274 /* Move complex constraints to the GRAPH nodes they belong to. */
2277 move_complex_constraints (constraint_graph_t graph)
2282 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2286 struct constraint_expr lhs = c->lhs;
2287 struct constraint_expr rhs = c->rhs;
2289 if (lhs.type == DEREF)
2291 insert_into_complex (graph, lhs.var, c);
2293 else if (rhs.type == DEREF)
2295 if (!(get_varinfo (lhs.var)->is_special_var))
2296 insert_into_complex (graph, rhs.var, c);
2298 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2299 && (lhs.offset != 0 || rhs.offset != 0))
2301 insert_into_complex (graph, rhs.var, c);
2308 /* Optimize and rewrite complex constraints while performing
2309 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2310 result of perform_variable_substitution. */
2313 rewrite_constraints (constraint_graph_t graph,
2314 struct scc_info *si)
2320 for (j = 0; j < graph->size; j++)
2321 gcc_assert (find (j) == j);
2323 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2325 struct constraint_expr lhs = c->lhs;
2326 struct constraint_expr rhs = c->rhs;
2327 unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id);
2328 unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id);
2329 unsigned int lhsnode, rhsnode;
2330 unsigned int lhslabel, rhslabel;
2332 lhsnode = si->node_mapping[lhsvar];
2333 rhsnode = si->node_mapping[rhsvar];
2334 lhslabel = graph->pointer_label[lhsnode];
2335 rhslabel = graph->pointer_label[rhsnode];
2337 /* See if it is really a non-pointer variable, and if so, ignore
2341 if (dump_file && (dump_flags & TDF_DETAILS))
2344 fprintf (dump_file, "%s is a non-pointer variable,"
2345 "ignoring constraint:",
2346 get_varinfo (lhs.var)->name);
2347 dump_constraint (dump_file, c);
2349 VEC_replace (constraint_t, constraints, i, NULL);
2355 if (dump_file && (dump_flags & TDF_DETAILS))
2358 fprintf (dump_file, "%s is a non-pointer variable,"
2359 "ignoring constraint:",
2360 get_varinfo (rhs.var)->name);
2361 dump_constraint (dump_file, c);
2363 VEC_replace (constraint_t, constraints, i, NULL);
2367 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2368 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2369 c->lhs.var = lhsvar;
2370 c->rhs.var = rhsvar;
2375 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2376 part of an SCC, false otherwise. */
2379 eliminate_indirect_cycles (unsigned int node)
2381 if (graph->indirect_cycles[node] != -1
2382 && !bitmap_empty_p (get_varinfo (node)->solution))
2385 VEC(unsigned,heap) *queue = NULL;
2387 unsigned int to = find (graph->indirect_cycles[node]);
2390 /* We can't touch the solution set and call unify_nodes
2391 at the same time, because unify_nodes is going to do
2392 bitmap unions into it. */
2394 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2396 if (find (i) == i && i != to)
2399 VEC_safe_push (unsigned, heap, queue, i);
2404 VEC_iterate (unsigned, queue, queuepos, i);
2407 unify_nodes (graph, to, i, true);
2409 VEC_free (unsigned, heap, queue);
2415 /* Solve the constraint graph GRAPH using our worklist solver.
2416 This is based on the PW* family of solvers from the "Efficient Field
2417 Sensitive Pointer Analysis for C" paper.
2418 It works by iterating over all the graph nodes, processing the complex
2419 constraints and propagating the copy constraints, until everything stops
2420 changed. This corresponds to steps 6-8 in the solving list given above. */
2423 solve_graph (constraint_graph_t graph)
2425 unsigned int size = graph->size;
2430 changed = sbitmap_alloc (size);
2431 sbitmap_zero (changed);
2433 /* Mark all initial non-collapsed nodes as changed. */
2434 for (i = 0; i < size; i++)
2436 varinfo_t ivi = get_varinfo (i);
2437 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2438 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2439 || VEC_length (constraint_t, graph->complex[i]) > 0))
2441 SET_BIT (changed, i);
2446 /* Allocate a bitmap to be used to store the changed bits. */
2447 pts = BITMAP_ALLOC (&pta_obstack);
2449 while (changed_count > 0)
2452 struct topo_info *ti = init_topo_info ();
2455 bitmap_obstack_initialize (&iteration_obstack);
2457 compute_topo_order (graph, ti);
2459 while (VEC_length (unsigned, ti->topo_order) != 0)
2462 i = VEC_pop (unsigned, ti->topo_order);
2464 /* If this variable is not a representative, skip it. */
2468 /* In certain indirect cycle cases, we may merge this
2469 variable to another. */
2470 if (eliminate_indirect_cycles (i) && find (i) != i)
2473 /* If the node has changed, we need to process the
2474 complex constraints and outgoing edges again. */
2475 if (TEST_BIT (changed, i))
2480 VEC(constraint_t,heap) *complex = graph->complex[i];
2481 bool solution_empty;
2483 RESET_BIT (changed, i);
2486 /* Compute the changed set of solution bits. */
2487 bitmap_and_compl (pts, get_varinfo (i)->solution,
2488 get_varinfo (i)->oldsolution);
2490 if (bitmap_empty_p (pts))
2493 bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2495 solution = get_varinfo (i)->solution;
2496 solution_empty = bitmap_empty_p (solution);
2498 /* Process the complex constraints */
2499 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2501 /* XXX: This is going to unsort the constraints in
2502 some cases, which will occasionally add duplicate
2503 constraints during unification. This does not
2504 affect correctness. */
2505 c->lhs.var = find (c->lhs.var);
2506 c->rhs.var = find (c->rhs.var);
2508 /* The only complex constraint that can change our
2509 solution to non-empty, given an empty solution,
2510 is a constraint where the lhs side is receiving
2511 some set from elsewhere. */
2512 if (!solution_empty || c->lhs.type != DEREF)
2513 do_complex_constraint (graph, c, pts);
2516 solution_empty = bitmap_empty_p (solution);
2519 /* Do not propagate the ESCAPED/CALLUSED solutions. */
2520 && i != find (escaped_id)
2521 && i != find (callused_id))
2525 /* Propagate solution to all successors. */
2526 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2532 unsigned int to = find (j);
2533 tmp = get_varinfo (to)->solution;
2536 /* Don't try to propagate to ourselves. */
2540 flag = set_union_with_increment (tmp, pts, 0);
2544 get_varinfo (to)->solution = tmp;
2545 if (!TEST_BIT (changed, to))
2547 SET_BIT (changed, to);
2555 free_topo_info (ti);
2556 bitmap_obstack_release (&iteration_obstack);
2560 sbitmap_free (changed);
2561 bitmap_obstack_release (&oldpta_obstack);
2564 /* Map from trees to variable infos. */
2565 static struct pointer_map_t *vi_for_tree;
2568 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2571 insert_vi_for_tree (tree t, varinfo_t vi)
2573 void **slot = pointer_map_insert (vi_for_tree, t);
2575 gcc_assert (*slot == NULL);
2579 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2580 exist in the map, return NULL, otherwise, return the varinfo we found. */
2583 lookup_vi_for_tree (tree t)
2585 void **slot = pointer_map_contains (vi_for_tree, t);
2589 return (varinfo_t) *slot;
2592 /* Return a printable name for DECL */
2595 alias_get_name (tree decl)
2597 const char *res = get_name (decl);
2599 int num_printed = 0;
2608 if (TREE_CODE (decl) == SSA_NAME)
2610 num_printed = asprintf (&temp, "%s_%u",
2611 alias_get_name (SSA_NAME_VAR (decl)),
2612 SSA_NAME_VERSION (decl));
2614 else if (DECL_P (decl))
2616 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2618 if (num_printed > 0)
2620 res = ggc_strdup (temp);
2626 /* Find the variable id for tree T in the map.
2627 If T doesn't exist in the map, create an entry for it and return it. */
2630 get_vi_for_tree (tree t)
2632 void **slot = pointer_map_contains (vi_for_tree, t);
2634 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2636 return (varinfo_t) *slot;
2639 /* Get a constraint expression for a new temporary variable. */
2641 static struct constraint_expr
2642 get_constraint_exp_for_temp (tree t)
2644 struct constraint_expr cexpr;
2646 gcc_assert (SSA_VAR_P (t));
2648 cexpr.type = SCALAR;
2649 cexpr.var = get_vi_for_tree (t)->id;
2655 /* Get a constraint expression vector from an SSA_VAR_P node.
2656 If address_p is true, the result will be taken its address of. */
2659 get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
2661 struct constraint_expr cexpr;
2664 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2665 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2667 /* For parameters, get at the points-to set for the actual parm
2669 if (TREE_CODE (t) == SSA_NAME
2670 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2671 && SSA_NAME_IS_DEFAULT_DEF (t))
2673 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2677 vi = get_vi_for_tree (t);
2679 cexpr.type = SCALAR;
2681 /* If we determine the result is "anything", and we know this is readonly,
2682 say it points to readonly memory instead. */
2683 if (cexpr.var == anything_id && TREE_READONLY (t))
2686 cexpr.type = ADDRESSOF;
2687 cexpr.var = readonly_id;
2690 /* If we are not taking the address of the constraint expr, add all
2691 sub-fiels of the variable as well. */
2694 for (; vi; vi = vi->next)
2697 VEC_safe_push (ce_s, heap, *results, &cexpr);
2702 VEC_safe_push (ce_s, heap, *results, &cexpr);
2705 /* Process constraint T, performing various simplifications and then
2706 adding it to our list of overall constraints. */
2709 process_constraint (constraint_t t)
2711 struct constraint_expr rhs = t->rhs;
2712 struct constraint_expr lhs = t->lhs;
2714 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2715 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2717 /* ANYTHING == ANYTHING is pointless. */
2718 if (lhs.var == anything_id && rhs.var == anything_id)
2721 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2722 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
2727 process_constraint (t);
2729 /* This can happen in our IR with things like n->a = *p */
2730 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2732 /* Split into tmp = *rhs, *lhs = tmp */
2733 tree rhsdecl = get_varinfo (rhs.var)->decl;
2734 tree pointertype = TREE_TYPE (rhsdecl);
2735 tree pointedtotype = TREE_TYPE (pointertype);
2736 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2737 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
2739 process_constraint (new_constraint (tmplhs, rhs));
2740 process_constraint (new_constraint (lhs, tmplhs));
2742 else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
2744 /* Split into tmp = &rhs, *lhs = tmp */
2745 tree rhsdecl = get_varinfo (rhs.var)->decl;
2746 tree pointertype = TREE_TYPE (rhsdecl);
2747 tree tmpvar = create_tmp_var_raw (pointertype, "derefaddrtmp");
2748 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
2750 process_constraint (new_constraint (tmplhs, rhs));
2751 process_constraint (new_constraint (lhs, tmplhs));
2755 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2756 VEC_safe_push (constraint_t, heap, constraints, t);
2760 /* Return true if T is a type that could contain pointers. */
2763 type_could_have_pointers (tree type)
2765 if (POINTER_TYPE_P (type))
2768 if (TREE_CODE (type) == ARRAY_TYPE)
2769 return type_could_have_pointers (TREE_TYPE (type));
2771 return AGGREGATE_TYPE_P (type);
2774 /* Return true if T is a variable of a type that could contain
2778 could_have_pointers (tree t)
2780 return type_could_have_pointers (TREE_TYPE (t));
2783 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2786 static HOST_WIDE_INT
2787 bitpos_of_field (const tree fdecl)
2790 if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2791 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2794 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2795 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2799 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2800 resulting constraint expressions in *RESULTS. */
2803 get_constraint_for_ptr_offset (tree ptr, tree offset,
2804 VEC (ce_s, heap) **results)
2806 struct constraint_expr c;
2808 unsigned HOST_WIDE_INT rhsunitoffset, rhsoffset;
2810 /* If we do not do field-sensitive PTA adding offsets to pointers
2811 does not change the points-to solution. */
2812 if (!use_field_sensitive)
2814 get_constraint_for (ptr, results);
2818 /* If the offset is not a non-negative integer constant that fits
2819 in a HOST_WIDE_INT, we have to fall back to a conservative
2820 solution which includes all sub-fields of all pointed-to
2822 ??? As we do not have the ability to express this, fall back
2824 if (!host_integerp (offset, 1))
2826 struct constraint_expr temp;
2827 temp.var = anything_id;
2830 VEC_safe_push (ce_s, heap, *results, &temp);
2834 /* Make sure the bit-offset also fits. */
2835 rhsunitoffset = TREE_INT_CST_LOW (offset);
2836 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
2837 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
2839 struct constraint_expr temp;
2840 temp.var = anything_id;
2843 VEC_safe_push (ce_s, heap, *results, &temp);
2847 get_constraint_for (ptr, results);
2851 /* As we are eventually appending to the solution do not use
2852 VEC_iterate here. */
2853 n = VEC_length (ce_s, *results);
2854 for (j = 0; j < n; j++)
2857 c = *VEC_index (ce_s, *results, j);
2858 curr = get_varinfo (c.var);
2860 if (c.type == ADDRESSOF
2861 && !curr->is_full_var)
2863 varinfo_t temp, curr = get_varinfo (c.var);
2865 /* Search the sub-field which overlaps with the
2866 pointed-to offset. As we deal with positive offsets
2867 only, we can start the search from the current variable. */
2868 temp = first_vi_for_offset (curr, curr->offset + rhsoffset);
2870 /* If the result is outside of the variable we have to provide
2871 a conservative result, as the variable is still reachable
2872 from the resulting pointer (even though it technically
2873 cannot point to anything). The last sub-field is such
2874 a conservative result.
2875 ??? If we always had a sub-field for &object + 1 then
2876 we could represent this in a more precise way. */
2880 while (temp->next != NULL)
2885 /* If the found variable is not exactly at the pointed to
2886 result, we have to include the next variable in the
2887 solution as well. Otherwise two increments by offset / 2
2888 do not result in the same or a conservative superset
2890 if (temp->offset != curr->offset + rhsoffset
2891 && temp->next != NULL)
2893 struct constraint_expr c2;
2894 c2.var = temp->next->id;
2895 c2.type = ADDRESSOF;
2897 VEC_safe_push (ce_s, heap, *results, &c2);
2902 else if (c.type == ADDRESSOF
2903 /* If this varinfo represents a full variable just use it. */
2904 && curr->is_full_var)
2907 c.offset = rhsoffset;
2909 VEC_replace (ce_s, *results, j, &c);
2914 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
2915 If address_p is true the result will be taken its address of. */
2918 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
2922 HOST_WIDE_INT bitsize = -1;
2923 HOST_WIDE_INT bitmaxsize = -1;
2924 HOST_WIDE_INT bitpos;
2926 struct constraint_expr *result;
2928 /* Some people like to do cute things like take the address of
2931 while (handled_component_p (forzero)
2932 || INDIRECT_REF_P (forzero))
2933 forzero = TREE_OPERAND (forzero, 0);
2935 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2937 struct constraint_expr temp;
2940 temp.var = integer_id;
2942 VEC_safe_push (ce_s, heap, *results, &temp);
2946 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2948 /* Pretend to take the address of the base, we'll take care of
2949 adding the required subset of sub-fields below. */
2950 get_constraint_for_1 (t, results, true);
2951 gcc_assert (VEC_length (ce_s, *results) == 1);
2952 result = VEC_last (ce_s, *results);
2954 /* This can also happen due to weird offsetof type macros. */
2955 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2956 result->type = SCALAR;
2958 if (result->type == SCALAR
2959 && get_varinfo (result->var)->is_full_var)
2960 /* For single-field vars do not bother about the offset. */
2962 else if (result->type == SCALAR)
2964 /* In languages like C, you can access one past the end of an
2965 array. You aren't allowed to dereference it, so we can
2966 ignore this constraint. When we handle pointer subtraction,
2967 we may have to do something cute here. */
2969 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
2972 /* It's also not true that the constraint will actually start at the
2973 right offset, it may start in some padding. We only care about
2974 setting the constraint to the first actual field it touches, so
2976 struct constraint_expr cexpr = *result;
2978 VEC_pop (ce_s, *results);
2980 for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
2982 if (ranges_overlap_p (curr->offset, curr->size,
2983 bitpos, bitmaxsize))
2985 cexpr.var = curr->id;
2986 VEC_safe_push (ce_s, heap, *results, &cexpr);
2991 /* If we are going to take the address of this field then
2992 to be able to compute reachability correctly add at least
2993 the last field of the variable. */
2995 && VEC_length (ce_s, *results) == 0)
2997 curr = get_varinfo (cexpr.var);
2998 while (curr->next != NULL)
3000 cexpr.var = curr->id;
3001 VEC_safe_push (ce_s, heap, *results, &cexpr);
3004 /* Assert that we found *some* field there. The user couldn't be
3005 accessing *only* padding. */
3006 /* Still the user could access one past the end of an array
3007 embedded in a struct resulting in accessing *only* padding. */
3008 gcc_assert (VEC_length (ce_s, *results) >= 1
3009 || ref_contains_array_ref (orig_t));
3011 else if (bitmaxsize == 0)
3013 if (dump_file && (dump_flags & TDF_DETAILS))
3014 fprintf (dump_file, "Access to zero-sized part of variable,"
3018 if (dump_file && (dump_flags & TDF_DETAILS))
3019 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3021 else if (bitmaxsize == -1)
3023 /* We can't handle DEREF constraints with unknown size, we'll
3024 get the wrong answer. Punt and return anything. */
3025 result->var = anything_id;
3029 result->offset = bitpos;
3033 /* Dereference the constraint expression CONS, and return the result.
3034 DEREF (ADDRESSOF) = SCALAR
3035 DEREF (SCALAR) = DEREF
3036 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3037 This is needed so that we can handle dereferencing DEREF constraints. */
3040 do_deref (VEC (ce_s, heap) **constraints)
3042 struct constraint_expr *c;
3045 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3047 if (c->type == SCALAR)
3049 else if (c->type == ADDRESSOF)
3051 else if (c->type == DEREF)
3053 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
3054 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
3055 process_constraint (new_constraint (tmplhs, *c));
3056 c->var = tmplhs.var;
3063 /* Given a tree T, return the constraint expression for it. */
3066 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3068 struct constraint_expr temp;
3070 /* x = integer is all glommed to a single variable, which doesn't
3071 point to anything by itself. That is, of course, unless it is an
3072 integer constant being treated as a pointer, in which case, we
3073 will return that this is really the addressof anything. This
3074 happens below, since it will fall into the default case. The only
3075 case we know something about an integer treated like a pointer is
3076 when it is the NULL pointer, and then we just say it points to
3079 Do not do that if -fno-delete-null-pointer-checks though, because
3080 in that case *NULL does not fail, so it _should_ alias *anything.
3081 It is not worth adding a new option or renaming the existing one,
3082 since this case is relatively obscure. */
3083 if (flag_delete_null_pointer_checks
3084 && TREE_CODE (t) == INTEGER_CST
3085 && integer_zerop (t))
3087 temp.var = nothing_id;
3088 temp.type = ADDRESSOF;
3090 VEC_safe_push (ce_s, heap, *results, &temp);
3094 /* String constants are read-only. */
3095 if (TREE_CODE (t) == STRING_CST)
3097 temp.var = readonly_id;
3100 VEC_safe_push (ce_s, heap, *results, &temp);
3104 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3106 case tcc_expression:
3108 switch (TREE_CODE (t))
3112 struct constraint_expr *c;
3114 tree exp = TREE_OPERAND (t, 0);
3116 get_constraint_for_1 (exp, results, true);
3118 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3120 if (c->type == DEREF)
3123 c->type = ADDRESSOF;
3134 switch (TREE_CODE (t))
3138 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3143 case ARRAY_RANGE_REF:
3145 get_constraint_for_component_ref (t, results, address_p);
3151 case tcc_exceptional:
3153 switch (TREE_CODE (t))
3157 get_constraint_for_ssa_var (t, results, address_p);
3164 case tcc_declaration:
3166 get_constraint_for_ssa_var (t, results, address_p);
3172 /* The default fallback is a constraint from anything. */
3173 temp.type = ADDRESSOF;
3174 temp.var = anything_id;
3176 VEC_safe_push (ce_s, heap, *results, &temp);
3179 /* Given a gimple tree T, return the constraint expression vector for it. */
3182 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3184 gcc_assert (VEC_length (ce_s, *results) == 0);
3186 get_constraint_for_1 (t, results, false);
3189 /* Handle the structure copy case where we have a simple structure copy
3190 between LHS and RHS that is of SIZE (in bits)
3192 For each field of the lhs variable (lhsfield)
3193 For each field of the rhs variable at lhsfield.offset (rhsfield)
3194 add the constraint lhsfield = rhsfield
3196 If we fail due to some kind of type unsafety or other thing we
3197 can't handle, return false. We expect the caller to collapse the
3198 variable in that case. */
3201 do_simple_structure_copy (const struct constraint_expr lhs,
3202 const struct constraint_expr rhs,
3203 const unsigned HOST_WIDE_INT size)
3205 varinfo_t p = get_varinfo (lhs.var);
3206 unsigned HOST_WIDE_INT pstart, last;
3208 last = p->offset + size;
3209 for (; p && p->offset < last; p = p->next)
3212 struct constraint_expr templhs = lhs;
3213 struct constraint_expr temprhs = rhs;
3214 unsigned HOST_WIDE_INT fieldoffset;
3216 templhs.var = p->id;
3217 q = get_varinfo (temprhs.var);
3218 fieldoffset = p->offset - pstart;
3219 q = first_vi_for_offset (q, q->offset + fieldoffset);
3222 temprhs.var = q->id;
3223 process_constraint (new_constraint (templhs, temprhs));
3229 /* Handle the structure copy case where we have a structure copy between a
3230 aggregate on the LHS and a dereference of a pointer on the RHS
3231 that is of SIZE (in bits)
3233 For each field of the lhs variable (lhsfield)
3234 rhs.offset = lhsfield->offset
3235 add the constraint lhsfield = rhs
3239 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
3240 const struct constraint_expr rhs,
3241 const unsigned HOST_WIDE_INT size)
3243 varinfo_t p = get_varinfo (lhs.var);
3244 unsigned HOST_WIDE_INT pstart,last;
3246 last = p->offset + size;
3248 for (; p && p->offset < last; p = p->next)
3251 struct constraint_expr templhs = lhs;
3252 struct constraint_expr temprhs = rhs;
3253 unsigned HOST_WIDE_INT fieldoffset;
3256 if (templhs.type == SCALAR)
3257 templhs.var = p->id;
3259 templhs.offset = p->offset;
3261 q = get_varinfo (temprhs.var);
3262 fieldoffset = p->offset - pstart;
3263 temprhs.offset += fieldoffset;
3264 process_constraint (new_constraint (templhs, temprhs));
3268 /* Handle the structure copy case where we have a structure copy
3269 between an aggregate on the RHS and a dereference of a pointer on
3270 the LHS that is of SIZE (in bits)
3272 For each field of the rhs variable (rhsfield)
3273 lhs.offset = rhsfield->offset
3274 add the constraint lhs = rhsfield
3278 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
3279 const struct constraint_expr rhs,
3280 const unsigned HOST_WIDE_INT size)
3282 varinfo_t p = get_varinfo (rhs.var);
3283 unsigned HOST_WIDE_INT pstart,last;
3285 last = p->offset + size;
3287 for (; p && p->offset < last; p = p->next)
3290 struct constraint_expr templhs = lhs;
3291 struct constraint_expr temprhs = rhs;
3292 unsigned HOST_WIDE_INT fieldoffset;
3295 if (temprhs.type == SCALAR)
3296 temprhs.var = p->id;
3298 temprhs.offset = p->offset;
3300 q = get_varinfo (templhs.var);
3301 fieldoffset = p->offset - pstart;
3302 templhs.offset += fieldoffset;
3303 process_constraint (new_constraint (templhs, temprhs));
3307 /* Sometimes, frontends like to give us bad type information. This
3308 function will collapse all the fields from VAR to the end of VAR,
3309 into VAR, so that we treat those fields as a single variable.
3310 We return the variable they were collapsed into. */
3313 collapse_rest_of_var (unsigned int var)
3315 varinfo_t currvar = get_varinfo (var);
3318 for (field = currvar->next; field; field = field->next)
3321 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
3322 field->name, currvar->name);
3324 gcc_assert (field->collapsed_to == 0);
3325 field->collapsed_to = currvar->id;
3328 currvar->next = NULL;
3329 currvar->size = currvar->fullsize - currvar->offset;
3334 /* Handle aggregate copies by expanding into copies of the respective
3335 fields of the structures. */
3338 do_structure_copy (tree lhsop, tree rhsop)
3340 struct constraint_expr lhs, rhs, tmp;
3341 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3343 unsigned HOST_WIDE_INT lhssize;
3344 unsigned HOST_WIDE_INT rhssize;
3346 /* Pretend we are taking the address of the constraint exprs.
3347 We deal with walking the sub-fields ourselves. */
3348 get_constraint_for_1 (lhsop, &lhsc, true);
3349 get_constraint_for_1 (rhsop, &rhsc, true);
3350 gcc_assert (VEC_length (ce_s, lhsc) == 1);
3351 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3352 lhs = *(VEC_last (ce_s, lhsc));
3353 rhs = *(VEC_last (ce_s, rhsc));
3355 VEC_free (ce_s, heap, lhsc);
3356 VEC_free (ce_s, heap, rhsc);
3358 /* If we have special var = x, swap it around. */
3359 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
3366 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
3367 possible it's something we could handle. However, most cases falling
3368 into this are dealing with transparent unions, which are slightly
3370 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
3372 rhs.type = ADDRESSOF;
3373 rhs.var = anything_id;
3376 /* If the RHS is a special var, or an addressof, set all the LHS fields to
3377 that special var. */
3378 if (rhs.var <= integer_id)
3380 for (p = get_varinfo (lhs.var); p; p = p->next)
3382 struct constraint_expr templhs = lhs;
3383 struct constraint_expr temprhs = rhs;
3385 if (templhs.type == SCALAR )
3386 templhs.var = p->id;
3388 templhs.offset += p->offset;
3389 process_constraint (new_constraint (templhs, temprhs));
3394 tree rhstype = TREE_TYPE (rhsop);
3395 tree lhstype = TREE_TYPE (lhsop);
3399 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
3400 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
3402 /* If we have a variably sized types on the rhs or lhs, and a deref
3403 constraint, add the constraint, lhsconstraint = &ANYTHING.
3404 This is conservatively correct because either the lhs is an unknown
3405 sized var (if the constraint is SCALAR), or the lhs is a DEREF
3406 constraint, and every variable it can point to must be unknown sized
3407 anyway, so we don't need to worry about fields at all. */
3408 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
3409 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
3411 rhs.var = anything_id;
3412 rhs.type = ADDRESSOF;
3414 process_constraint (new_constraint (lhs, rhs));
3418 /* The size only really matters insofar as we don't set more or less of
3419 the variable. If we hit an unknown size var, the size should be the
3420 whole darn thing. */
3421 if (get_varinfo (rhs.var)->is_unknown_size_var)
3424 rhssize = TREE_INT_CST_LOW (rhstypesize);
3426 if (get_varinfo (lhs.var)->is_unknown_size_var)
3429 lhssize = TREE_INT_CST_LOW (lhstypesize);
3432 if (rhs.type == SCALAR && lhs.type == SCALAR)
3434 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
3436 lhs.var = collapse_rest_of_var (get_varinfo_fc (lhs.var)->id);
3437 rhs.var = collapse_rest_of_var (get_varinfo_fc (rhs.var)->id);
3442 process_constraint (new_constraint (lhs, rhs));
3445 else if (lhs.type != DEREF && rhs.type == DEREF)
3446 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3447 else if (lhs.type == DEREF && rhs.type != DEREF)
3448 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3451 tree pointedtotype = lhstype;
3454 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3455 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
3456 do_structure_copy (tmpvar, rhsop);
3457 do_structure_copy (lhsop, tmpvar);
3462 /* Create a constraint ID = OP. */
3465 make_constraint_to (unsigned id, tree op)
3467 VEC(ce_s, heap) *rhsc = NULL;
3468 struct constraint_expr *c;
3469 struct constraint_expr includes;
3473 includes.offset = 0;
3474 includes.type = SCALAR;
3476 get_constraint_for (op, &rhsc);
3477 for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3478 process_constraint (new_constraint (includes, *c));
3479 VEC_free (ce_s, heap, rhsc);
3482 /* Make constraints necessary to make OP escape. */
3485 make_escape_constraint (tree op)
3487 make_constraint_to (escaped_id, op);
3490 /* For non-IPA mode, generate constraints necessary for a call on the
3494 handle_rhs_call (gimple stmt)
3498 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3500 tree arg = gimple_call_arg (stmt, i);
3502 /* Find those pointers being passed, and make sure they end up
3503 pointing to anything. */
3504 if (could_have_pointers (arg))
3505 make_escape_constraint (arg);
3508 /* The static chain escapes as well. */
3509 if (gimple_call_chain (stmt))
3510 make_escape_constraint (gimple_call_chain (stmt));
3513 /* For non-IPA mode, generate constraints necessary for a call
3514 that returns a pointer and assigns it to LHS. This simply makes
3515 the LHS point to global and escaped variables. */
3518 handle_lhs_call (tree lhs, int flags)
3520 VEC(ce_s, heap) *lhsc = NULL;
3521 struct constraint_expr rhsc;
3523 struct constraint_expr *lhsp;
3525 get_constraint_for (lhs, &lhsc);
3527 if (flags & ECF_MALLOC)
3529 tree heapvar = heapvar_lookup (lhs);
3532 if (heapvar == NULL)
3534 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
3535 DECL_EXTERNAL (heapvar) = 1;
3536 get_var_ann (heapvar)->is_heapvar = 1;
3537 if (gimple_referenced_vars (cfun))
3538 add_referenced_var (heapvar);
3539 heapvar_insert (lhs, heapvar);
3542 rhsc.var = create_variable_info_for (heapvar,
3543 alias_get_name (heapvar));
3544 vi = get_varinfo (rhsc.var);
3545 vi->is_artificial_var = 1;
3546 vi->is_heap_var = 1;
3547 vi->is_unknown_size_var = true;
3550 rhsc.type = ADDRESSOF;
3555 rhsc.var = escaped_id;
3557 rhsc.type = ADDRESSOF;
3559 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3560 process_constraint (new_constraint (*lhsp, rhsc));
3561 VEC_free (ce_s, heap, lhsc);
3564 /* For non-IPA mode, generate constraints necessary for a call of a
3565 const function that returns a pointer in the statement STMT. */
3568 handle_const_call (gimple stmt)
3570 tree lhs = gimple_call_lhs (stmt);
3571 VEC(ce_s, heap) *lhsc = NULL;
3572 struct constraint_expr rhsc;
3574 struct constraint_expr *lhsp;
3576 struct constraint_expr tmpc;
3578 get_constraint_for (lhs, &lhsc);
3580 /* If this is a nested function then it can return anything. */
3581 if (gimple_call_chain (stmt))
3583 rhsc.var = anything_id;
3585 rhsc.type = ADDRESSOF;
3586 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3587 process_constraint (new_constraint (*lhsp, rhsc));
3588 VEC_free (ce_s, heap, lhsc);
3592 /* We always use a temporary here, otherwise we end up with a quadratic
3593 amount of constraints for
3594 large_struct = const_call (large_struct);
3595 in field-sensitive PTA. */
3596 tmpvar = create_tmp_var_raw (ptr_type_node, "consttmp");
3597 tmpc = get_constraint_exp_for_temp (tmpvar);
3599 /* May return addresses of globals. */
3600 rhsc.var = nonlocal_id;
3602 rhsc.type = ADDRESSOF;
3603 process_constraint (new_constraint (tmpc, rhsc));
3605 /* May return arguments. */
3606 for (k = 0; k < gimple_call_num_args (stmt); ++k)
3608 tree arg = gimple_call_arg (stmt, k);
3610 if (could_have_pointers (arg))
3612 VEC(ce_s, heap) *argc = NULL;
3613 struct constraint_expr *argp;
3616 get_constraint_for (arg, &argc);
3617 for (i = 0; VEC_iterate (ce_s, argc, i, argp); i++)
3618 process_constraint (new_constraint (tmpc, *argp));
3619 VEC_free (ce_s, heap, argc);
3623 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3624 process_constraint (new_constraint (*lhsp, tmpc));
3626 VEC_free (ce_s, heap, lhsc);
3629 /* For non-IPA mode, generate constraints necessary for a call to a
3630 pure function in statement STMT. */
3633 handle_pure_call (gimple stmt)
3637 /* Memory reached from pointer arguments is call-used. */
3638 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3640 tree arg = gimple_call_arg (stmt, i);
3642 if (could_have_pointers (arg))
3643 make_constraint_to (callused_id, arg);
3646 /* The static chain is used as well. */
3647 if (gimple_call_chain (stmt))
3648 make_constraint_to (callused_id, gimple_call_chain (stmt));
3650 /* If the call returns a pointer it may point to reachable memory
3651 from the arguments. Not so for malloc functions though. */
3652 if (gimple_call_lhs (stmt)
3653 && could_have_pointers (gimple_call_lhs (stmt))
3654 && !(gimple_call_flags (stmt) & ECF_MALLOC))
3656 tree lhs = gimple_call_lhs (stmt);
3657 VEC(ce_s, heap) *lhsc = NULL;
3658 struct constraint_expr rhsc;
3659 struct constraint_expr *lhsp;
3662 get_constraint_for (lhs, &lhsc);
3664 /* If this is a nested function then it can return anything. */
3665 if (gimple_call_chain (stmt))
3667 rhsc.var = anything_id;
3669 rhsc.type = ADDRESSOF;
3670 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3671 process_constraint (new_constraint (*lhsp, rhsc));
3672 VEC_free (ce_s, heap, lhsc);
3676 /* Else just add the call-used memory here. Escaped variables
3677 and globals will be dealt with in handle_lhs_call. */
3678 rhsc.var = callused_id;
3680 rhsc.type = ADDRESSOF;
3681 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3682 process_constraint (new_constraint (*lhsp, rhsc));
3683 VEC_free (ce_s, heap, lhsc);
3687 /* Walk statement T setting up aliasing constraints according to the
3688 references found in T. This function is the main part of the
3689 constraint builder. AI points to auxiliary alias information used
3690 when building alias sets and computing alias grouping heuristics. */
3693 find_func_aliases (gimple origt)
3696 VEC(ce_s, heap) *lhsc = NULL;
3697 VEC(ce_s, heap) *rhsc = NULL;
3698 struct constraint_expr *c;
3699 enum escape_type stmt_escape_type;
3701 /* Now build constraints expressions. */
3702 if (gimple_code (t) == GIMPLE_PHI)
3704 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (gimple_phi_result (t))));
3706 /* Only care about pointers and structures containing
3708 if (could_have_pointers (gimple_phi_result (t)))
3713 /* For a phi node, assign all the arguments to
3715 get_constraint_for (gimple_phi_result (t), &lhsc);
3716 for (i = 0; i < gimple_phi_num_args (t); i++)
3719 tree strippedrhs = PHI_ARG_DEF (t, i);
3721 STRIP_NOPS (strippedrhs);
3722 rhstype = TREE_TYPE (strippedrhs);
3723 get_constraint_for (gimple_phi_arg_def (t, i), &rhsc);
3725 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3727 struct constraint_expr *c2;
3728 while (VEC_length (ce_s, rhsc) > 0)
3730 c2 = VEC_last (ce_s, rhsc);
3731 process_constraint (new_constraint (*c, *c2));
3732 VEC_pop (ce_s, rhsc);
3738 /* In IPA mode, we need to generate constraints to pass call
3739 arguments through their calls. There are two cases,
3740 either a GIMPLE_CALL returning a value, or just a plain
3741 GIMPLE_CALL when we are not.
3743 In non-ipa mode, we need to generate constraints for each
3744 pointer passed by address. */
3745 else if (is_gimple_call (t))
3749 int flags = gimple_call_flags (t);
3751 /* Const functions can return their arguments and addresses
3752 of global memory but not of escaped memory. */
3753 if (flags & ECF_CONST)
3755 if (gimple_call_lhs (t)
3756 && could_have_pointers (gimple_call_lhs (t)))
3757 handle_const_call (t);
3759 /* Pure functions can return addresses in and of memory
3760 reachable from their arguments, but they are not an escape
3761 point for reachable memory of their arguments. */
3762 else if (flags & ECF_PURE)
3764 handle_pure_call (t);
3765 if (gimple_call_lhs (t)
3766 && could_have_pointers (gimple_call_lhs (t)))
3767 handle_lhs_call (gimple_call_lhs (t), flags);
3771 handle_rhs_call (t);
3772 if (gimple_call_lhs (t)
3773 && could_have_pointers (gimple_call_lhs (t)))
3774 handle_lhs_call (gimple_call_lhs (t), flags);
3785 lhsop = gimple_call_lhs (t);
3786 decl = gimple_call_fndecl (t);
3788 /* If we can directly resolve the function being called, do so.
3789 Otherwise, it must be some sort of indirect expression that
3790 we should still be able to handle. */
3792 fi = get_vi_for_tree (decl);
3795 decl = gimple_call_fn (t);
3796 fi = get_vi_for_tree (decl);
3799 /* Assign all the passed arguments to the appropriate incoming
3800 parameters of the function. */
3801 for (j = 0; j < gimple_call_num_args (t); j++)
3803 struct constraint_expr lhs ;
3804 struct constraint_expr *rhsp;
3805 tree arg = gimple_call_arg (t, j);
3807 get_constraint_for (arg, &rhsc);
3808 if (TREE_CODE (decl) != FUNCTION_DECL)
3817 lhs.var = first_vi_for_offset (fi, i)->id;
3820 while (VEC_length (ce_s, rhsc) != 0)
3822 rhsp = VEC_last (ce_s, rhsc);
3823 process_constraint (new_constraint (lhs, *rhsp));
3824 VEC_pop (ce_s, rhsc);
3829 /* If we are returning a value, assign it to the result. */
3832 struct constraint_expr rhs;
3833 struct constraint_expr *lhsp;
3836 get_constraint_for (lhsop, &lhsc);
3837 if (TREE_CODE (decl) != FUNCTION_DECL)
3846 rhs.var = first_vi_for_offset (fi, i)->id;
3849 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3850 process_constraint (new_constraint (*lhsp, rhs));
3854 /* Otherwise, just a regular assignment statement. Only care about
3855 operations with pointer result, others are dealt with as escape
3856 points if they have pointer operands. */
3857 else if (is_gimple_assign (t)
3858 && could_have_pointers (gimple_assign_lhs (t)))
3860 /* Otherwise, just a regular assignment statement. */
3861 tree lhsop = gimple_assign_lhs (t);
3862 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
3864 if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
3865 do_structure_copy (lhsop, rhsop);
3869 struct constraint_expr temp;
3870 get_constraint_for (lhsop, &lhsc);
3872 if (gimple_assign_rhs_code (t) == POINTER_PLUS_EXPR)
3873 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
3874 gimple_assign_rhs2 (t), &rhsc);
3875 else if ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
3876 && !(POINTER_TYPE_P (gimple_expr_type (t))
3877 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
3878 || gimple_assign_single_p (t))
3879 get_constraint_for (rhsop, &rhsc);
3882 temp.type = ADDRESSOF;
3883 temp.var = anything_id;
3885 VEC_safe_push (ce_s, heap, rhsc, &temp);
3887 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3889 struct constraint_expr *c2;
3892 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3893 process_constraint (new_constraint (*c, *c2));
3897 else if (gimple_code (t) == GIMPLE_CHANGE_DYNAMIC_TYPE)
3901 get_constraint_for (gimple_cdt_location (t), &lhsc);
3902 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); ++j)
3903 get_varinfo (c->var)->no_tbaa_pruning = true;
3906 stmt_escape_type = is_escape_site (t);
3907 if (stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
3909 gcc_assert (is_gimple_assign (t));
3910 if (gimple_assign_rhs_code (t) == ADDR_EXPR)
3912 tree rhs = gimple_assign_rhs1 (t);
3913 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3916 || !is_global_var (base)))
3917 make_escape_constraint (rhs);
3919 else if (get_gimple_rhs_class (gimple_assign_rhs_code (t))
3920 == GIMPLE_SINGLE_RHS)
3922 if (could_have_pointers (gimple_assign_rhs1 (t)))
3923 make_escape_constraint (gimple_assign_rhs1 (t));
3928 else if (stmt_escape_type == ESCAPE_BAD_CAST)
3930 gcc_assert (is_gimple_assign (t));
3931 gcc_assert (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
3932 || gimple_assign_rhs_code (t) == VIEW_CONVERT_EXPR);
3933 make_escape_constraint (gimple_assign_rhs1 (t));
3935 else if (stmt_escape_type == ESCAPE_TO_ASM)
3938 for (i = 0; i < gimple_asm_noutputs (t); ++i)
3940 tree op = TREE_VALUE (gimple_asm_output_op (t, i));
3941 if (op && could_have_pointers (op))
3942 /* Strictly we'd only need the constraints from ESCAPED and
3944 make_escape_constraint (op);
3946 for (i = 0; i < gimple_asm_ninputs (t); ++i)
3948 tree op = TREE_VALUE (gimple_asm_input_op (t, i));
3949 if (op && could_have_pointers (op))
3950 /* Strictly we'd only need the constraint to ESCAPED. */
3951 make_escape_constraint (op);
3955 /* After promoting variables and computing aliasing we will
3956 need to re-scan most statements. FIXME: Try to minimize the
3957 number of statements re-scanned. It's not really necessary to
3958 re-scan *all* statements. */
3960 gimple_set_modified (origt, true);
3961 VEC_free (ce_s, heap, rhsc);
3962 VEC_free (ce_s, heap, lhsc);
3966 /* Find the first varinfo in the same variable as START that overlaps with
3968 Effectively, walk the chain of fields for the variable START to find the
3969 first field that overlaps with OFFSET.
3970 Return NULL if we can't find one. */
3973 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3975 varinfo_t curr = start;
3978 /* We may not find a variable in the field list with the actual
3979 offset when when we have glommed a structure to a variable.
3980 In that case, however, offset should still be within the size
3982 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3990 /* Insert the varinfo FIELD into the field list for BASE, at the front
3994 insert_into_field_list (varinfo_t base, varinfo_t field)
3996 varinfo_t prev = base;
3997 varinfo_t curr = base->next;
4003 /* Insert the varinfo FIELD into the field list for BASE, ordered by
4007 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
4009 varinfo_t prev = base;
4010 varinfo_t curr = base->next;
4021 if (field->offset <= curr->offset)
4026 field->next = prev->next;
4031 /* This structure is used during pushing fields onto the fieldstack
4032 to track the offset of the field, since bitpos_of_field gives it
4033 relative to its immediate containing type, and we want it relative
4034 to the ultimate containing object. */
4038 /* Offset from the base of the base containing object to this field. */
4039 HOST_WIDE_INT offset;
4041 /* Size, in bits, of the field. */
4042 unsigned HOST_WIDE_INT size;
4044 unsigned has_unknown_size : 1;
4046 unsigned may_have_pointers : 1;
4048 typedef struct fieldoff fieldoff_s;
4050 DEF_VEC_O(fieldoff_s);
4051 DEF_VEC_ALLOC_O(fieldoff_s,heap);
4053 /* qsort comparison function for two fieldoff's PA and PB */
4056 fieldoff_compare (const void *pa, const void *pb)
4058 const fieldoff_s *foa = (const fieldoff_s *)pa;
4059 const fieldoff_s *fob = (const fieldoff_s *)pb;
4060 unsigned HOST_WIDE_INT foasize, fobsize;
4062 if (foa->offset < fob->offset)
4064 else if (foa->offset > fob->offset)
4067 foasize = foa->size;
4068 fobsize = fob->size;
4069 if (foasize < fobsize)
4071 else if (foasize > fobsize)
4076 /* Sort a fieldstack according to the field offset and sizes. */
4078 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
4080 qsort (VEC_address (fieldoff_s, fieldstack),
4081 VEC_length (fieldoff_s, fieldstack),
4082 sizeof (fieldoff_s),
4086 /* Return true if V is a tree that we can have subvars for.
4087 Normally, this is any aggregate type. Also complex
4088 types which are not gimple registers can have subvars. */
4091 var_can_have_subvars (const_tree v)
4093 /* Volatile variables should never have subvars. */
4094 if (TREE_THIS_VOLATILE (v))
4097 /* Non decls or memory tags can never have subvars. */
4098 if (!DECL_P (v) || MTAG_P (v))
4101 /* Aggregates without overlapping fields can have subvars. */
4102 if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
4108 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4109 the fields of TYPE onto fieldstack, recording their offsets along
4112 OFFSET is used to keep track of the offset in this entire
4113 structure, rather than just the immediately containing structure.
4114 Returns the number of fields pushed. */
4117 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
4118 HOST_WIDE_INT offset)
4123 if (TREE_CODE (type) != RECORD_TYPE)
4126 /* If the vector of fields is growing too big, bail out early.
4127 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4129 if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
4132 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
4133 if (TREE_CODE (field) == FIELD_DECL)
4137 HOST_WIDE_INT foff = bitpos_of_field (field);
4139 if (!var_can_have_subvars (field)
4140 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
4141 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
4143 else if (!(pushed = push_fields_onto_fieldstack
4144 (TREE_TYPE (field), fieldstack, offset + foff))
4145 && (DECL_SIZE (field)
4146 && !integer_zerop (DECL_SIZE (field))))
4147 /* Empty structures may have actual size, like in C++. So
4148 see if we didn't push any subfields and the size is
4149 nonzero, push the field onto the stack. */
4154 fieldoff_s *pair = NULL;
4155 bool has_unknown_size = false;
4157 if (!VEC_empty (fieldoff_s, *fieldstack))
4158 pair = VEC_last (fieldoff_s, *fieldstack);
4160 if (!DECL_SIZE (field)
4161 || !host_integerp (DECL_SIZE (field), 1))
4162 has_unknown_size = true;
4164 /* If adjacent fields do not contain pointers merge them. */
4166 && !pair->may_have_pointers
4167 && !could_have_pointers (field)
4168 && !pair->has_unknown_size
4169 && !has_unknown_size
4170 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
4172 pair = VEC_last (fieldoff_s, *fieldstack);
4173 pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
4177 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
4178 pair->offset = offset + foff;
4179 pair->has_unknown_size = has_unknown_size;
4180 if (!has_unknown_size)
4181 pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
4184 pair->may_have_pointers = could_have_pointers (field);
4195 /* Create a constraint ID = &FROM. */
4198 make_constraint_from (varinfo_t vi, int from)
4200 struct constraint_expr lhs, rhs;
4208 rhs.type = ADDRESSOF;
4209 process_constraint (new_constraint (lhs, rhs));
4212 /* Count the number of arguments DECL has, and set IS_VARARGS to true
4213 if it is a varargs function. */
4216 count_num_arguments (tree decl, bool *is_varargs)
4221 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
4225 if (TREE_VALUE (t) == void_type_node)
4235 /* Creation function node for DECL, using NAME, and return the index
4236 of the variable we've created for the function. */
4239 create_function_info_for (tree decl, const char *name)
4241 unsigned int index = VEC_length (varinfo_t, varmap);
4245 bool is_varargs = false;
4247 /* Create the variable info. */
4249 vi = new_var_info (decl, index, name);
4253 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
4254 insert_vi_for_tree (vi->decl, vi);
4255 VEC_safe_push (varinfo_t, heap, varmap, vi);
4259 /* If it's varargs, we don't know how many arguments it has, so we
4265 vi->is_unknown_size_var = true;
4270 arg = DECL_ARGUMENTS (decl);
4272 /* Set up variables for each argument. */
4273 for (i = 1; i < vi->fullsize; i++)
4276 const char *newname;
4278 unsigned int newindex;
4279 tree argdecl = decl;
4284 newindex = VEC_length (varinfo_t, varmap);
4285 asprintf (&tempname, "%s.arg%d", name, i-1);
4286 newname = ggc_strdup (tempname);
4289 argvi = new_var_info (argdecl, newindex, newname);
4290 argvi->decl = argdecl;
4291 VEC_safe_push (varinfo_t, heap, varmap, argvi);
4294 argvi->is_full_var = true;
4295 argvi->fullsize = vi->fullsize;
4296 insert_into_field_list_sorted (vi, argvi);
4297 stats.total_vars ++;
4300 insert_vi_for_tree (arg, argvi);
4301 arg = TREE_CHAIN (arg);
4305 /* Create a variable for the return var. */
4306 if (DECL_RESULT (decl) != NULL
4307 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
4310 const char *newname;
4312 unsigned int newindex;
4313 tree resultdecl = decl;
4317 if (DECL_RESULT (decl))
4318 resultdecl = DECL_RESULT (decl);
4320 newindex = VEC_length (varinfo_t, varmap);
4321 asprintf (&tempname, "%s.result", name);
4322 newname = ggc_strdup (tempname);
4325 resultvi = new_var_info (resultdecl, newindex, newname);
4326 resultvi->decl = resultdecl;
4327 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
4328 resultvi->offset = i;
4330 resultvi->fullsize = vi->fullsize;
4331 resultvi->is_full_var = true;
4332 insert_into_field_list_sorted (vi, resultvi);
4333 stats.total_vars ++;
4334 if (DECL_RESULT (decl))
4335 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
4341 /* Return true if FIELDSTACK contains fields that overlap.
4342 FIELDSTACK is assumed to be sorted by offset. */
4345 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
4347 fieldoff_s *fo = NULL;
4349 HOST_WIDE_INT lastoffset = -1;
4351 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4353 if (fo->offset == lastoffset)
4355 lastoffset = fo->offset;
4360 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4361 This will also create any varinfo structures necessary for fields
4365 create_variable_info_for (tree decl, const char *name)
4367 unsigned int index = VEC_length (varinfo_t, varmap);
4369 tree decl_type = TREE_TYPE (decl);
4370 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
4371 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
4372 VEC (fieldoff_s,heap) *fieldstack = NULL;
4374 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4375 return create_function_info_for (decl, name);
4377 if (var_can_have_subvars (decl) && use_field_sensitive
4379 || var_ann (decl)->noalias_state == 0)
4381 || !var_ann (decl)->is_heapvar))
4382 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
4384 /* If the variable doesn't have subvars, we may end up needing to
4385 sort the field list and create fake variables for all the
4387 vi = new_var_info (decl, index, name);
4390 vi->may_have_pointers = could_have_pointers (decl);
4392 || !host_integerp (declsize, 1))
4394 vi->is_unknown_size_var = true;
4400 vi->fullsize = TREE_INT_CST_LOW (declsize);
4401 vi->size = vi->fullsize;
4404 insert_vi_for_tree (vi->decl, vi);
4405 VEC_safe_push (varinfo_t, heap, varmap, vi);
4406 if (is_global && (!flag_whole_program || !in_ipa_mode)
4407 && vi->may_have_pointers)
4410 && var_ann (decl)->noalias_state == NO_ALIAS_ANYTHING)
4411 make_constraint_from (vi, vi->id);
4413 make_constraint_from (vi, escaped_id);
4417 if (use_field_sensitive
4418 && !vi->is_unknown_size_var
4419 && var_can_have_subvars (decl)
4420 && VEC_length (fieldoff_s, fieldstack) > 1
4421 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4423 unsigned int newindex = VEC_length (varinfo_t, varmap);
4424 fieldoff_s *fo = NULL;
4425 bool notokay = false;
4428 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4430 if (fo->has_unknown_size
4438 /* We can't sort them if we have a field with a variable sized type,
4439 which will make notokay = true. In that case, we are going to return
4440 without creating varinfos for the fields anyway, so sorting them is a
4444 sort_fieldstack (fieldstack);
4445 /* Due to some C++ FE issues, like PR 22488, we might end up
4446 what appear to be overlapping fields even though they,
4447 in reality, do not overlap. Until the C++ FE is fixed,
4448 we will simply disable field-sensitivity for these cases. */
4449 notokay = check_for_overlaps (fieldstack);
4453 if (VEC_length (fieldoff_s, fieldstack) != 0)
4454 fo = VEC_index (fieldoff_s, fieldstack, 0);
4456 if (fo == NULL || notokay)
4458 vi->is_unknown_size_var = 1;
4461 vi->is_full_var = true;
4462 VEC_free (fieldoff_s, heap, fieldstack);
4466 vi->size = fo->size;
4467 vi->offset = fo->offset;
4468 vi->may_have_pointers = fo->may_have_pointers;
4469 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4470 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4474 const char *newname = "NULL";
4477 newindex = VEC_length (varinfo_t, varmap);
4480 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
4481 "+" HOST_WIDE_INT_PRINT_DEC,
4482 vi->name, fo->offset, fo->size);
4483 newname = ggc_strdup (tempname);
4486 newvi = new_var_info (decl, newindex, newname);
4487 newvi->offset = fo->offset;
4488 newvi->size = fo->size;
4489 newvi->fullsize = vi->fullsize;
4490 newvi->may_have_pointers = fo->may_have_pointers;
4491 insert_into_field_list (vi, newvi);
4492 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4493 if (is_global && (!flag_whole_program || !in_ipa_mode)
4494 && newvi->may_have_pointers)
4495 make_constraint_from (newvi, escaped_id);
4501 vi->is_full_var = true;
4503 VEC_free (fieldoff_s, heap, fieldstack);
4508 /* Print out the points-to solution for VAR to FILE. */
4511 dump_solution_for_var (FILE *file, unsigned int var)
4513 varinfo_t vi = get_varinfo (var);
4517 if (find (var) != var)
4519 varinfo_t vipt = get_varinfo (find (var));
4520 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4524 fprintf (file, "%s = { ", vi->name);
4525 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4527 fprintf (file, "%s ", get_varinfo (i)->name);
4529 fprintf (file, "}");
4530 if (vi->no_tbaa_pruning)
4531 fprintf (file, " no-tbaa-pruning");
4532 fprintf (file, "\n");
4536 /* Print the points-to solution for VAR to stdout. */
4539 debug_solution_for_var (unsigned int var)
4541 dump_solution_for_var (stdout, var);
4544 /* Create varinfo structures for all of the variables in the
4545 function for intraprocedural mode. */
4548 intra_create_variable_infos (void)
4551 struct constraint_expr lhs, rhs;
4553 /* For each incoming pointer argument arg, create the constraint ARG
4554 = NONLOCAL or a dummy variable if flag_argument_noalias is set. */
4555 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4559 if (!could_have_pointers (t))
4562 /* If flag_argument_noalias is set, then function pointer
4563 arguments are guaranteed not to point to each other. In that
4564 case, create an artificial variable PARM_NOALIAS and the
4565 constraint ARG = &PARM_NOALIAS. */
4566 if (POINTER_TYPE_P (TREE_TYPE (t)) && flag_argument_noalias > 0)
4569 tree heapvar = heapvar_lookup (t);
4573 lhs.var = get_vi_for_tree (t)->id;
4575 if (heapvar == NULL_TREE)
4578 heapvar = create_tmp_var_raw (ptr_type_node,
4580 DECL_EXTERNAL (heapvar) = 1;
4581 if (gimple_referenced_vars (cfun))
4582 add_referenced_var (heapvar);
4584 heapvar_insert (t, heapvar);
4586 ann = get_var_ann (heapvar);
4587 ann->is_heapvar = 1;
4588 if (flag_argument_noalias == 1)
4589 ann->noalias_state = NO_ALIAS;
4590 else if (flag_argument_noalias == 2)
4591 ann->noalias_state = NO_ALIAS_GLOBAL;
4592 else if (flag_argument_noalias == 3)
4593 ann->noalias_state = NO_ALIAS_ANYTHING;
4598 vi = get_vi_for_tree (heapvar);
4599 vi->is_artificial_var = 1;
4600 vi->is_heap_var = 1;
4601 vi->is_unknown_size_var = true;
4605 rhs.type = ADDRESSOF;
4607 for (p = get_varinfo (lhs.var); p; p = p->next)
4609 struct constraint_expr temp = lhs;
4611 process_constraint (new_constraint (temp, rhs));
4616 varinfo_t arg_vi = get_vi_for_tree (t);
4618 for (p = arg_vi; p; p = p->next)
4619 make_constraint_from (p, nonlocal_id);
4623 /* Add a constraint for a result decl that is passed by reference. */
4624 if (DECL_RESULT (cfun->decl)
4625 && DECL_BY_REFERENCE (DECL_RESULT (cfun->decl)))
4627 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
4629 for (p = result_vi; p; p = p->next)
4630 make_constraint_from (p, nonlocal_id);
4633 /* Add a constraint for the incoming static chain parameter. */
4634 if (cfun->static_chain_decl != NULL_TREE)
4636 varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
4638 for (p = chain_vi; p; p = p->next)
4639 make_constraint_from (p, nonlocal_id);
4643 /* Structure used to put solution bitmaps in a hashtable so they can
4644 be shared among variables with the same points-to set. */
4646 typedef struct shared_bitmap_info
4650 } *shared_bitmap_info_t;
4651 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
4653 static htab_t shared_bitmap_table;
4655 /* Hash function for a shared_bitmap_info_t */
4658 shared_bitmap_hash (const void *p)
4660 const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
4661 return bi->hashcode;
4664 /* Equality function for two shared_bitmap_info_t's. */
4667 shared_bitmap_eq (const void *p1, const void *p2)
4669 const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
4670 const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
4671 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
4674 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4675 existing instance if there is one, NULL otherwise. */
4678 shared_bitmap_lookup (bitmap pt_vars)
4681 struct shared_bitmap_info sbi;
4683 sbi.pt_vars = pt_vars;
4684 sbi.hashcode = bitmap_hash (pt_vars);
4686 slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
4687 sbi.hashcode, NO_INSERT);
4691 return ((shared_bitmap_info_t) *slot)->pt_vars;
4695 /* Add a bitmap to the shared bitmap hashtable. */
4698 shared_bitmap_add (bitmap pt_vars)
4701 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
4703 sbi->pt_vars = pt_vars;
4704 sbi->hashcode = bitmap_hash (pt_vars);
4706 slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
4707 sbi->hashcode, INSERT);
4708 gcc_assert (!*slot);
4709 *slot = (void *) sbi;
4713 /* Set bits in INTO corresponding to the variable uids in solution set
4714 FROM, which came from variable PTR.
4715 For variables that are actually dereferenced, we also use type
4716 based alias analysis to prune the points-to sets.
4717 IS_DEREFED is true if PTR was directly dereferenced, which we use to
4718 help determine whether we are we are allowed to prune using TBAA.
4719 If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of
4720 the from set. Returns the number of pruned variables. */
4723 set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed,
4724 bool no_tbaa_pruning)
4728 unsigned pruned = 0;
4730 gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
4732 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4734 varinfo_t vi = get_varinfo (i);
4736 /* The only artificial variables that are allowed in a may-alias
4737 set are heap variables. */
4738 if (vi->is_artificial_var && !vi->is_heap_var)
4741 if (TREE_CODE (vi->decl) == VAR_DECL
4742 || TREE_CODE (vi->decl) == PARM_DECL
4743 || TREE_CODE (vi->decl) == RESULT_DECL)
4745 /* Just add VI->DECL to the alias set.
4746 Don't type prune artificial vars or points-to sets
4747 for pointers that have not been dereferenced or with
4748 type-based pruning disabled. */
4749 if (vi->is_artificial_var
4752 || vi->no_tbaa_pruning)
4753 bitmap_set_bit (into, DECL_UID (vi->decl));
4756 alias_set_type var_alias_set, mem_alias_set;
4757 var_alias_set = get_alias_set (vi->decl);
4758 mem_alias_set = get_alias_set (TREE_TYPE (TREE_TYPE (ptr)));
4759 if (may_alias_p (SSA_NAME_VAR (ptr), mem_alias_set,
4760 vi->decl, var_alias_set, true))
4761 bitmap_set_bit (into, DECL_UID (vi->decl));
4772 static bool have_alias_info = false;
4774 /* Emit a note for the pointer initialization point DEF. */
4777 emit_pointer_definition (tree ptr, bitmap visited)
4779 gimple def = SSA_NAME_DEF_STMT (ptr);
4780 if (gimple_code (def) == GIMPLE_PHI)
4785 FOR_EACH_PHI_ARG (argp, def, oi, SSA_OP_USE)
4787 tree arg = USE_FROM_PTR (argp);
4788 if (TREE_CODE (arg) == SSA_NAME)
4790 if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
4791 emit_pointer_definition (arg, visited);
4794 inform (0, "initialized from %qE", arg);
4797 else if (!gimple_nop_p (def))
4798 inform (gimple_location (def), "initialized from here");
4801 /* Emit a strict aliasing warning for dereferencing the pointer PTR. */
4804 emit_alias_warning (tree ptr)
4807 imm_use_iterator ui;
4808 bool warned = false;
4810 FOR_EACH_IMM_USE_STMT (use, ui, ptr)
4812 tree deref = NULL_TREE;
4814 if (gimple_has_lhs (use))
4816 tree lhs = get_base_address (gimple_get_lhs (use));
4818 && INDIRECT_REF_P (lhs)
4819 && TREE_OPERAND (lhs, 0) == ptr)
4822 if (gimple_assign_single_p (use))
4824 tree rhs = get_base_address (gimple_assign_rhs1 (use));
4826 && INDIRECT_REF_P (rhs)
4827 && TREE_OPERAND (rhs, 0) == ptr)
4830 else if (is_gimple_call (use))
4833 for (i = 0; i < gimple_call_num_args (use); ++i)
4835 tree op = get_base_address (gimple_call_arg (use, i));
4837 && INDIRECT_REF_P (op)
4838 && TREE_OPERAND (op, 0) == ptr)
4843 && !TREE_NO_WARNING (deref))
4845 TREE_NO_WARNING (deref) = 1;
4846 warned |= warning_at (gimple_location (use), OPT_Wstrict_aliasing,
4847 "dereferencing pointer %qD does break "
4848 "strict-aliasing rules", SSA_NAME_VAR (ptr));
4853 bitmap visited = BITMAP_ALLOC (NULL);
4854 emit_pointer_definition (ptr, visited);
4855 BITMAP_FREE (visited);
4859 /* Given a pointer variable P, fill in its points-to set, or return
4861 Rather than return false for variables that point-to anything, we
4862 instead find the corresponding SMT, and merge in its aliases. In
4863 addition to these aliases, we also set the bits for the SMT's
4864 themselves and their subsets, as SMT's are still in use by
4865 non-SSA_NAME's, and pruning may eliminate every one of their
4866 aliases. In such a case, if we did not include the right set of
4867 SMT's in the points-to set of the variable, we'd end up with
4868 statements that do not conflict but should. */
4871 find_what_p_points_to (tree p)
4876 if (!have_alias_info)
4879 /* For parameters, get at the points-to set for the actual parm
4881 if (TREE_CODE (p) == SSA_NAME
4882 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4883 && SSA_NAME_IS_DEFAULT_DEF (p))
4884 lookup_p = SSA_NAME_VAR (p);
4886 vi = lookup_vi_for_tree (lookup_p);
4889 if (vi->is_artificial_var)
4892 /* See if this is a field or a structure. */
4893 if (vi->size != vi->fullsize)
4895 /* Nothing currently asks about structure fields directly,
4896 but when they do, we need code here to hand back the
4902 struct ptr_info_def *pi = get_ptr_info (p);
4903 unsigned int i, pruned;
4905 bool was_pt_anything = false;
4906 bitmap finished_solution;
4909 if (!pi->memory_tag_needed)
4912 /* This variable may have been collapsed, let's get the real
4914 vi = get_varinfo (find (vi->id));
4916 /* Translate artificial variables into SSA_NAME_PTR_INFO
4918 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4920 varinfo_t vi = get_varinfo (i);
4922 if (vi->is_artificial_var)
4924 /* FIXME. READONLY should be handled better so that
4925 flow insensitive aliasing can disregard writable
4927 if (vi->id == nothing_id)
4929 else if (vi->id == anything_id
4930 || vi->id == nonlocal_id
4931 || vi->id == escaped_id
4932 || vi->id == callused_id)
4933 was_pt_anything = 1;
4934 else if (vi->id == readonly_id)
4935 was_pt_anything = 1;
4936 else if (vi->id == integer_id)
4937 was_pt_anything = 1;
4938 else if (vi->is_heap_var)
4939 pi->pt_global_mem = 1;
4943 /* Instead of doing extra work, simply do not create
4944 points-to information for pt_anything pointers. This
4945 will cause the operand scanner to fall back to the
4946 type-based SMT and its aliases. Which is the best
4947 we could do here for the points-to set as well. */
4948 if (was_pt_anything)
4951 /* Share the final set of variables when possible. */
4952 finished_solution = BITMAP_GGC_ALLOC ();
4953 stats.points_to_sets_created++;
4955 pruned = set_uids_in_ptset (p, finished_solution, vi->solution,
4956 pi->is_dereferenced,
4957 vi->no_tbaa_pruning);
4958 result = shared_bitmap_lookup (finished_solution);
4962 shared_bitmap_add (finished_solution);
4963 pi->pt_vars = finished_solution;
4967 pi->pt_vars = result;
4968 bitmap_clear (finished_solution);
4971 if (bitmap_empty_p (pi->pt_vars))
4976 && pi->is_dereferenced
4977 && warn_strict_aliasing > 0
4978 && !SSA_NAME_IS_DEFAULT_DEF (p))
4980 if (dump_file && dump_flags & TDF_DETAILS)
4982 fprintf (dump_file, "alias warning for ");
4983 print_generic_expr (dump_file, p, 0);
4984 fprintf (dump_file, "\n");
4986 emit_alias_warning (p);
4997 /* Mark the ESCAPED solution as call clobbered. Returns false if
4998 pt_anything escaped which needs all locals that have their address
4999 taken marked call clobbered as well. */
5002 clobber_what_escaped (void)
5008 if (!have_alias_info)
5011 /* This variable may have been collapsed, let's get the real
5012 variable for escaped_id. */
5013 vi = get_varinfo (find (escaped_id));
5015 /* If call-used memory escapes we need to include it in the
5016 set of escaped variables. This can happen if a pure
5017 function returns a pointer and this pointer escapes. */
5018 if (bitmap_bit_p (vi->solution, callused_id))
5020 varinfo_t cu_vi = get_varinfo (find (callused_id));
5021 bitmap_ior_into (vi->solution, cu_vi->solution);
5024 /* Mark variables in the solution call-clobbered. */
5025 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
5027 varinfo_t vi = get_varinfo (i);
5029 if (vi->is_artificial_var)
5031 /* nothing_id and readonly_id do not cause any
5032 call clobber ops. For anything_id and integer_id
5033 we need to clobber all addressable vars. */
5034 if (vi->id == anything_id
5035 || vi->id == integer_id)
5039 /* Only artificial heap-vars are further interesting. */
5040 if (vi->is_artificial_var && !vi->is_heap_var)
5043 if ((TREE_CODE (vi->decl) == VAR_DECL
5044 || TREE_CODE (vi->decl) == PARM_DECL
5045 || TREE_CODE (vi->decl) == RESULT_DECL)
5046 && !unmodifiable_var_p (vi->decl))
5047 mark_call_clobbered (vi->decl, ESCAPE_TO_CALL);
5053 /* Compute the call-used variables. */
5056 compute_call_used_vars (void)
5061 bool has_anything_id = false;
5063 if (!have_alias_info)
5066 /* This variable may have been collapsed, let's get the real
5067 variable for escaped_id. */
5068 vi = get_varinfo (find (callused_id));
5070 /* Mark variables in the solution call-clobbered. */
5071 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
5073 varinfo_t vi = get_varinfo (i);
5075 if (vi->is_artificial_var)
5077 /* For anything_id and integer_id we need to make
5078 all local addressable vars call-used. */
5079 if (vi->id == anything_id
5080 || vi->id == integer_id)
5081 has_anything_id = true;
5084 /* Only artificial heap-vars are further interesting. */
5085 if (vi->is_artificial_var && !vi->is_heap_var)
5088 if ((TREE_CODE (vi->decl) == VAR_DECL
5089 || TREE_CODE (vi->decl) == PARM_DECL
5090 || TREE_CODE (vi->decl) == RESULT_DECL)
5091 && !unmodifiable_var_p (vi->decl))
5092 bitmap_set_bit (gimple_call_used_vars (cfun), DECL_UID (vi->decl));
5095 /* If anything is call-used, add all addressable locals to the set. */
5096 if (has_anything_id)
5097 bitmap_ior_into (gimple_call_used_vars (cfun),
5098 gimple_addressable_vars (cfun));
5102 /* Dump points-to information to OUTFILE. */
5105 dump_sa_points_to_info (FILE *outfile)
5109 fprintf (outfile, "\nPoints-to sets\n\n");
5111 if (dump_flags & TDF_STATS)
5113 fprintf (outfile, "Stats:\n");
5114 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
5115 fprintf (outfile, "Non-pointer vars: %d\n",
5116 stats.nonpointer_vars);
5117 fprintf (outfile, "Statically unified vars: %d\n",
5118 stats.unified_vars_static);
5119 fprintf (outfile, "Dynamically unified vars: %d\n",
5120 stats.unified_vars_dynamic);
5121 fprintf (outfile, "Iterations: %d\n", stats.iterations);
5122 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
5123 fprintf (outfile, "Number of implicit edges: %d\n",
5124 stats.num_implicit_edges);
5127 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
5128 dump_solution_for_var (outfile, i);
5132 /* Debug points-to information to stderr. */
5135 debug_sa_points_to_info (void)
5137 dump_sa_points_to_info (stderr);
5141 /* Initialize the always-existing constraint variables for NULL
5142 ANYTHING, READONLY, and INTEGER */
5145 init_base_vars (void)
5147 struct constraint_expr lhs, rhs;
5149 /* Create the NULL variable, used to represent that a variable points
5151 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
5152 var_nothing = new_var_info (nothing_tree, nothing_id, "NULL");
5153 insert_vi_for_tree (nothing_tree, var_nothing);
5154 var_nothing->is_artificial_var = 1;
5155 var_nothing->offset = 0;
5156 var_nothing->size = ~0;
5157 var_nothing->fullsize = ~0;
5158 var_nothing->is_special_var = 1;
5159 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
5161 /* Create the ANYTHING variable, used to represent that a variable
5162 points to some unknown piece of memory. */
5163 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
5164 var_anything = new_var_info (anything_tree, anything_id, "ANYTHING");
5165 insert_vi_for_tree (anything_tree, var_anything);
5166 var_anything->is_artificial_var = 1;
5167 var_anything->size = ~0;
5168 var_anything->offset = 0;
5169 var_anything->next = NULL;
5170 var_anything->fullsize = ~0;
5171 var_anything->is_special_var = 1;
5173 /* Anything points to anything. This makes deref constraints just
5174 work in the presence of linked list and other p = *p type loops,
5175 by saying that *ANYTHING = ANYTHING. */
5176 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
5178 lhs.var = anything_id;
5180 rhs.type = ADDRESSOF;
5181 rhs.var = anything_id;
5184 /* This specifically does not use process_constraint because
5185 process_constraint ignores all anything = anything constraints, since all
5186 but this one are redundant. */
5187 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
5189 /* Create the READONLY variable, used to represent that a variable
5190 points to readonly memory. */
5191 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
5192 var_readonly = new_var_info (readonly_tree, readonly_id, "READONLY");
5193 var_readonly->is_artificial_var = 1;
5194 var_readonly->offset = 0;
5195 var_readonly->size = ~0;
5196 var_readonly->fullsize = ~0;
5197 var_readonly->next = NULL;
5198 var_readonly->is_special_var = 1;
5199 insert_vi_for_tree (readonly_tree, var_readonly);
5200 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
5202 /* readonly memory points to anything, in order to make deref
5203 easier. In reality, it points to anything the particular
5204 readonly variable can point to, but we don't track this
5207 lhs.var = readonly_id;
5209 rhs.type = ADDRESSOF;
5210 rhs.var = readonly_id; /* FIXME */
5212 process_constraint (new_constraint (lhs, rhs));
5214 /* Create the ESCAPED variable, used to represent the set of escaped
5216 escaped_tree = create_tmp_var_raw (void_type_node, "ESCAPED");
5217 var_escaped = new_var_info (escaped_tree, escaped_id, "ESCAPED");
5218 insert_vi_for_tree (escaped_tree, var_escaped);
5219 var_escaped->is_artificial_var = 1;
5220 var_escaped->offset = 0;
5221 var_escaped->size = ~0;
5222 var_escaped->fullsize = ~0;
5223 var_escaped->is_special_var = 0;
5224 VEC_safe_push (varinfo_t, heap, varmap, var_escaped);
5225 gcc_assert (VEC_index (varinfo_t, varmap, 3) == var_escaped);
5227 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
5229 lhs.var = escaped_id;
5232 rhs.var = escaped_id;
5234 process_constraint (new_constraint (lhs, rhs));
5236 /* Create the NONLOCAL variable, used to represent the set of nonlocal
5238 nonlocal_tree = create_tmp_var_raw (void_type_node, "NONLOCAL");
5239 var_nonlocal = new_var_info (nonlocal_tree, nonlocal_id, "NONLOCAL");
5240 insert_vi_for_tree (nonlocal_tree, var_nonlocal);
5241 var_nonlocal->is_artificial_var = 1;
5242 var_nonlocal->offset = 0;
5243 var_nonlocal->size = ~0;
5244 var_nonlocal->fullsize = ~0;
5245 var_nonlocal->is_special_var = 1;
5246 VEC_safe_push (varinfo_t, heap, varmap, var_nonlocal);
5248 /* Nonlocal memory points to escaped (which includes nonlocal),
5249 in order to make deref easier. */
5251 lhs.var = nonlocal_id;
5253 rhs.type = ADDRESSOF;
5254 rhs.var = escaped_id;
5256 process_constraint (new_constraint (lhs, rhs));
5258 /* Create the CALLUSED variable, used to represent the set of call-used
5260 callused_tree = create_tmp_var_raw (void_type_node, "CALLUSED");
5261 var_callused = new_var_info (callused_tree, callused_id, "CALLUSED");
5262 insert_vi_for_tree (callused_tree, var_callused);
5263 var_callused->is_artificial_var = 1;
5264 var_callused->offset = 0;
5265 var_callused->size = ~0;
5266 var_callused->fullsize = ~0;
5267 var_callused->is_special_var = 0;
5268 VEC_safe_push (varinfo_t, heap, varmap, var_callused);
5270 /* CALLUSED = *CALLUSED, because call-used is may-deref'd at calls, etc. */
5272 lhs.var = callused_id;
5275 rhs.var = callused_id;
5277 process_constraint (new_constraint (lhs, rhs));
5279 /* Create the STOREDANYTHING variable, used to represent the set of
5280 variables stored to *ANYTHING. */
5281 storedanything_tree = create_tmp_var_raw (ptr_type_node, "STOREDANYTHING");
5282 var_storedanything = new_var_info (storedanything_tree, storedanything_id,
5284 insert_vi_for_tree (storedanything_tree, var_storedanything);
5285 var_storedanything->is_artificial_var = 1;
5286 var_storedanything->offset = 0;
5287 var_storedanything->size = ~0;
5288 var_storedanything->fullsize = ~0;
5289 var_storedanything->is_special_var = 0;
5290 VEC_safe_push (varinfo_t, heap, varmap, var_storedanything);
5292 /* Create the INTEGER variable, used to represent that a variable points
5294 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
5295 var_integer = new_var_info (integer_tree, integer_id, "INTEGER");
5296 insert_vi_for_tree (integer_tree, var_integer);
5297 var_integer->is_artificial_var = 1;
5298 var_integer->size = ~0;
5299 var_integer->fullsize = ~0;
5300 var_integer->offset = 0;
5301 var_integer->next = NULL;
5302 var_integer->is_special_var = 1;
5303 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
5305 /* INTEGER = ANYTHING, because we don't know where a dereference of
5306 a random integer will point to. */
5308 lhs.var = integer_id;
5310 rhs.type = ADDRESSOF;
5311 rhs.var = anything_id;
5313 process_constraint (new_constraint (lhs, rhs));
5315 /* *ESCAPED = &ESCAPED. This is true because we have to assume
5316 everything pointed to by escaped can also point to escaped. */
5318 lhs.var = escaped_id;
5320 rhs.type = ADDRESSOF;
5321 rhs.var = escaped_id;
5323 process_constraint (new_constraint (lhs, rhs));
5325 /* *ESCAPED = &NONLOCAL. This is true because we have to assume
5326 everything pointed to by escaped can also point to nonlocal. */
5328 lhs.var = escaped_id;
5330 rhs.type = ADDRESSOF;
5331 rhs.var = nonlocal_id;
5333 process_constraint (new_constraint (lhs, rhs));
5336 /* Initialize things necessary to perform PTA */
5339 init_alias_vars (void)
5341 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
5343 bitmap_obstack_initialize (&pta_obstack);
5344 bitmap_obstack_initialize (&oldpta_obstack);
5345 bitmap_obstack_initialize (&predbitmap_obstack);
5347 constraint_pool = create_alloc_pool ("Constraint pool",
5348 sizeof (struct constraint), 30);
5349 variable_info_pool = create_alloc_pool ("Variable info pool",
5350 sizeof (struct variable_info), 30);
5351 constraints = VEC_alloc (constraint_t, heap, 8);
5352 varmap = VEC_alloc (varinfo_t, heap, 8);
5353 vi_for_tree = pointer_map_create ();
5355 memset (&stats, 0, sizeof (stats));
5356 shared_bitmap_table = htab_create (511, shared_bitmap_hash,
5357 shared_bitmap_eq, free);
5361 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
5362 predecessor edges. */
5365 remove_preds_and_fake_succs (constraint_graph_t graph)
5369 /* Clear the implicit ref and address nodes from the successor
5371 for (i = 0; i < FIRST_REF_NODE; i++)
5373 if (graph->succs[i])
5374 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
5375 FIRST_REF_NODE * 2);
5378 /* Free the successor list for the non-ref nodes. */
5379 for (i = FIRST_REF_NODE; i < graph->size; i++)
5381 if (graph->succs[i])
5382 BITMAP_FREE (graph->succs[i]);
5385 /* Now reallocate the size of the successor list as, and blow away
5386 the predecessor bitmaps. */
5387 graph->size = VEC_length (varinfo_t, varmap);
5388 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
5390 free (graph->implicit_preds);
5391 graph->implicit_preds = NULL;
5392 free (graph->preds);
5393 graph->preds = NULL;
5394 bitmap_obstack_release (&predbitmap_obstack);
5397 /* Compute the set of variables we can't TBAA prune. */
5400 compute_tbaa_pruning (void)
5402 unsigned int size = VEC_length (varinfo_t, varmap);
5407 changed = sbitmap_alloc (size);
5408 sbitmap_zero (changed);
5410 /* Mark all initial no_tbaa_pruning nodes as changed. */
5412 for (i = 0; i < size; ++i)
5414 varinfo_t ivi = get_varinfo (i);
5416 if (find (i) == i && ivi->no_tbaa_pruning)
5419 if ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
5420 || VEC_length (constraint_t, graph->complex[i]) > 0)
5422 SET_BIT (changed, i);
5428 while (changed_count > 0)
5430 struct topo_info *ti = init_topo_info ();
5433 compute_topo_order (graph, ti);
5435 while (VEC_length (unsigned, ti->topo_order) != 0)
5439 i = VEC_pop (unsigned, ti->topo_order);
5441 /* If this variable is not a representative, skip it. */
5445 /* If the node has changed, we need to process the complex
5446 constraints and outgoing edges again. */
5447 if (TEST_BIT (changed, i))
5451 VEC(constraint_t,heap) *complex = graph->complex[i];
5453 RESET_BIT (changed, i);
5456 /* Process the complex copy constraints. */
5457 for (j = 0; VEC_iterate (constraint_t, complex, j, c); ++j)
5459 if (c->lhs.type == SCALAR && c->rhs.type == SCALAR)
5461 varinfo_t lhsvi = get_varinfo (find (c->lhs.var));
5463 if (!lhsvi->no_tbaa_pruning)
5465 lhsvi->no_tbaa_pruning = true;
5466 if (!TEST_BIT (changed, lhsvi->id))
5468 SET_BIT (changed, lhsvi->id);
5475 /* Propagate to all successors. */
5476 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
5478 unsigned int to = find (j);
5479 varinfo_t tovi = get_varinfo (to);
5481 /* Don't propagate to ourselves. */
5485 if (!tovi->no_tbaa_pruning)
5487 tovi->no_tbaa_pruning = true;
5488 if (!TEST_BIT (changed, to))
5490 SET_BIT (changed, to);
5498 free_topo_info (ti);
5501 sbitmap_free (changed);
5505 for (i = 0; i < size; ++i)
5507 varinfo_t ivi = get_varinfo (i);
5508 varinfo_t ivip = get_varinfo (find (i));
5510 if (ivip->no_tbaa_pruning)
5512 tree var = ivi->decl;
5514 if (TREE_CODE (var) == SSA_NAME)
5515 var = SSA_NAME_VAR (var);
5517 if (POINTER_TYPE_P (TREE_TYPE (var)))
5519 DECL_NO_TBAA_P (var) = 1;
5521 /* Tell the RTL layer that this pointer can alias
5523 DECL_POINTER_ALIAS_SET (var) = 0;
5530 /* Create points-to sets for the current function. See the comments
5531 at the start of the file for an algorithmic overview. */
5534 compute_points_to_sets (void)
5536 struct scc_info *si;
5539 timevar_push (TV_TREE_PTA);
5542 init_alias_heapvars ();
5544 intra_create_variable_infos ();
5546 /* Now walk all statements and derive aliases. */
5549 gimple_stmt_iterator gsi;
5551 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5553 gimple phi = gsi_stmt (gsi);
5555 if (is_gimple_reg (gimple_phi_result (phi)))
5556 find_func_aliases (phi);
5559 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5560 find_func_aliases (gsi_stmt (gsi));
5566 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5567 dump_constraints (dump_file);
5572 "\nCollapsing static cycles and doing variable "
5575 init_graph (VEC_length (varinfo_t, varmap) * 2);
5578 fprintf (dump_file, "Building predecessor graph\n");
5579 build_pred_graph ();
5582 fprintf (dump_file, "Detecting pointer and location "
5584 si = perform_var_substitution (graph);
5587 fprintf (dump_file, "Rewriting constraints and unifying "
5589 rewrite_constraints (graph, si);
5591 build_succ_graph ();
5592 free_var_substitution_info (si);
5594 if (dump_file && (dump_flags & TDF_GRAPH))
5595 dump_constraint_graph (dump_file);
5597 move_complex_constraints (graph);
5600 fprintf (dump_file, "Uniting pointer but not location equivalent "
5602 unite_pointer_equivalences (graph);
5605 fprintf (dump_file, "Finding indirect cycles\n");
5606 find_indirect_cycles (graph);
5608 /* Implicit nodes and predecessors are no longer necessary at this
5610 remove_preds_and_fake_succs (graph);
5613 fprintf (dump_file, "Solving graph\n");
5615 solve_graph (graph);
5617 compute_tbaa_pruning ();
5620 dump_sa_points_to_info (dump_file);
5622 have_alias_info = true;
5624 timevar_pop (TV_TREE_PTA);
5628 /* Delete created points-to sets. */
5631 delete_points_to_sets (void)
5635 htab_delete (shared_bitmap_table);
5636 if (dump_file && (dump_flags & TDF_STATS))
5637 fprintf (dump_file, "Points to sets created:%d\n",
5638 stats.points_to_sets_created);
5640 pointer_map_destroy (vi_for_tree);
5641 bitmap_obstack_release (&pta_obstack);
5642 VEC_free (constraint_t, heap, constraints);
5644 for (i = 0; i < graph->size; i++)
5645 VEC_free (constraint_t, heap, graph->complex[i]);
5646 free (graph->complex);
5649 free (graph->succs);
5651 free (graph->pe_rep);
5652 free (graph->indirect_cycles);
5655 VEC_free (varinfo_t, heap, varmap);
5656 free_alloc_pool (variable_info_pool);
5657 free_alloc_pool (constraint_pool);
5658 have_alias_info = false;
5661 /* Return true if we should execute IPA PTA. */
5665 return (flag_ipa_pta
5666 /* Don't bother doing anything if the program has errors. */
5667 && !(errorcount || sorrycount));
5670 /* Execute the driver for IPA PTA. */
5672 ipa_pta_execute (void)
5674 struct cgraph_node *node;
5675 struct scc_info *si;
5678 init_alias_heapvars ();
5681 for (node = cgraph_nodes; node; node = node->next)
5683 if (!node->analyzed || cgraph_is_master_clone (node))
5687 varid = create_function_info_for (node->decl,
5688 cgraph_node_name (node));
5689 if (node->local.externally_visible)
5691 varinfo_t fi = get_varinfo (varid);
5692 for (; fi; fi = fi->next)
5693 make_constraint_from (fi, anything_id);
5697 for (node = cgraph_nodes; node; node = node->next)
5699 if (node->analyzed && cgraph_is_master_clone (node))
5701 struct function *func = DECL_STRUCT_FUNCTION (node->decl);
5703 tree old_func_decl = current_function_decl;
5706 "Generating constraints for %s\n",
5707 cgraph_node_name (node));
5709 current_function_decl = node->decl;
5711 FOR_EACH_BB_FN (bb, func)
5713 gimple_stmt_iterator gsi;
5715 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
5718 gimple phi = gsi_stmt (gsi);
5720 if (is_gimple_reg (gimple_phi_result (phi)))
5721 find_func_aliases (phi);
5724 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5725 find_func_aliases (gsi_stmt (gsi));
5727 current_function_decl = old_func_decl;
5732 /* Make point to anything. */
5738 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5739 dump_constraints (dump_file);
5744 "\nCollapsing static cycles and doing variable "
5747 init_graph (VEC_length (varinfo_t, varmap) * 2);
5748 build_pred_graph ();
5749 si = perform_var_substitution (graph);
5750 rewrite_constraints (graph, si);
5752 build_succ_graph ();
5753 free_var_substitution_info (si);
5754 move_complex_constraints (graph);
5755 unite_pointer_equivalences (graph);
5756 find_indirect_cycles (graph);
5758 /* Implicit nodes and predecessors are no longer necessary at this
5760 remove_preds_and_fake_succs (graph);
5763 fprintf (dump_file, "\nSolving graph\n");
5765 solve_graph (graph);
5768 dump_sa_points_to_info (dump_file);
5771 delete_alias_heapvars ();
5772 delete_points_to_sets ();
5776 struct simple_ipa_opt_pass pass_ipa_pta =
5781 gate_ipa_pta, /* gate */
5782 ipa_pta_execute, /* execute */
5785 0, /* static_pass_number */
5786 TV_IPA_PTA, /* tv_id */
5787 0, /* properties_required */
5788 0, /* properties_provided */
5789 0, /* properties_destroyed */
5790 0, /* todo_flags_start */
5791 TODO_update_ssa /* todo_flags_finish */
5795 /* Initialize the heapvar for statement mapping. */
5797 init_alias_heapvars (void)
5799 if (!heapvar_for_stmt)
5800 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5805 delete_alias_heapvars (void)
5807 htab_delete (heapvar_for_stmt);
5808 heapvar_for_stmt = NULL;
5811 #include "gt-tree-ssa-structalias.h"