1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
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 == escaped_id
1528 || c->rhs.var == 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 == escaped_id
1598 || get_varinfo (t)->id == callused_id)
1599 flag |= bitmap_set_bit (sol, get_varinfo (t)->id);
1600 else if (add_graph_edge (graph, lhs, t))
1601 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1606 /* If the LHS solution changed, mark the var as changed. */
1609 get_varinfo (lhs)->solution = sol;
1610 if (!TEST_BIT (changed, lhs))
1612 SET_BIT (changed, lhs);
1618 /* Process a constraint C that represents *x = y. */
1621 do_ds_constraint (constraint_t c, bitmap delta)
1623 unsigned int rhs = c->rhs.var;
1624 bitmap sol = get_varinfo (rhs)->solution;
1628 /* Our IL does not allow this. */
1629 gcc_assert (c->rhs.offset == 0);
1631 /* If the solution of y contains ANYTHING simply use the ANYTHING
1632 solution. This avoids needlessly increasing the points-to sets. */
1633 if (bitmap_bit_p (sol, anything_id))
1634 sol = get_varinfo (find (anything_id))->solution;
1636 /* If the solution for x contains ANYTHING we have to merge the
1637 solution of y into all pointer variables which we do via
1639 if (bitmap_bit_p (delta, anything_id))
1641 unsigned t = find (storedanything_id);
1642 if (add_graph_edge (graph, t, rhs))
1644 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1646 if (!TEST_BIT (changed, t))
1648 SET_BIT (changed, t);
1656 /* For each member j of delta (Sol(x)), add an edge from y to j and
1657 union Sol(y) into Sol(j) */
1658 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1660 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1661 if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
1665 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1667 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1668 /* If the access is outside of the variable we can ignore it. */
1672 if (v->may_have_pointers)
1675 if (add_graph_edge (graph, t, rhs))
1677 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1680 sol = get_varinfo (rhs)->solution;
1681 if (!TEST_BIT (changed, t))
1683 SET_BIT (changed, t);
1693 /* Handle a non-simple (simple meaning requires no iteration),
1694 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1697 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1699 if (c->lhs.type == DEREF)
1701 if (c->rhs.type == ADDRESSOF)
1708 do_ds_constraint (c, delta);
1711 else if (c->rhs.type == DEREF)
1714 if (!(get_varinfo (c->lhs.var)->is_special_var))
1715 do_sd_constraint (graph, c, delta);
1723 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1724 solution = get_varinfo (c->rhs.var)->solution;
1725 tmp = get_varinfo (c->lhs.var)->solution;
1727 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1731 get_varinfo (c->lhs.var)->solution = tmp;
1732 if (!TEST_BIT (changed, c->lhs.var))
1734 SET_BIT (changed, c->lhs.var);
1741 /* Initialize and return a new SCC info structure. */
1743 static struct scc_info *
1744 init_scc_info (size_t size)
1746 struct scc_info *si = XNEW (struct scc_info);
1749 si->current_index = 0;
1750 si->visited = sbitmap_alloc (size);
1751 sbitmap_zero (si->visited);
1752 si->deleted = sbitmap_alloc (size);
1753 sbitmap_zero (si->deleted);
1754 si->node_mapping = XNEWVEC (unsigned int, size);
1755 si->dfs = XCNEWVEC (unsigned int, size);
1757 for (i = 0; i < size; i++)
1758 si->node_mapping[i] = i;
1760 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1764 /* Free an SCC info structure pointed to by SI */
1767 free_scc_info (struct scc_info *si)
1769 sbitmap_free (si->visited);
1770 sbitmap_free (si->deleted);
1771 free (si->node_mapping);
1773 VEC_free (unsigned, heap, si->scc_stack);
1778 /* Find indirect cycles in GRAPH that occur, using strongly connected
1779 components, and note them in the indirect cycles map.
1781 This technique comes from Ben Hardekopf and Calvin Lin,
1782 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1783 Lines of Code", submitted to PLDI 2007. */
1786 find_indirect_cycles (constraint_graph_t graph)
1789 unsigned int size = graph->size;
1790 struct scc_info *si = init_scc_info (size);
1792 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1793 if (!TEST_BIT (si->visited, i) && find (i) == i)
1794 scc_visit (graph, si, i);
1799 /* Compute a topological ordering for GRAPH, and store the result in the
1800 topo_info structure TI. */
1803 compute_topo_order (constraint_graph_t graph,
1804 struct topo_info *ti)
1807 unsigned int size = graph->size;
1809 for (i = 0; i != size; ++i)
1810 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1811 topo_visit (graph, ti, i);
1814 /* Structure used to for hash value numbering of pointer equivalence
1817 typedef struct equiv_class_label
1819 unsigned int equivalence_class;
1822 } *equiv_class_label_t;
1823 typedef const struct equiv_class_label *const_equiv_class_label_t;
1825 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1827 static htab_t pointer_equiv_class_table;
1829 /* A hashtable for mapping a bitmap of labels->location equivalence
1831 static htab_t location_equiv_class_table;
1833 /* Hash function for a equiv_class_label_t */
1836 equiv_class_label_hash (const void *p)
1838 const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
1839 return ecl->hashcode;
1842 /* Equality function for two equiv_class_label_t's. */
1845 equiv_class_label_eq (const void *p1, const void *p2)
1847 const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
1848 const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
1849 return bitmap_equal_p (eql1->labels, eql2->labels);
1852 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
1856 equiv_class_lookup (htab_t table, bitmap labels)
1859 struct equiv_class_label ecl;
1861 ecl.labels = labels;
1862 ecl.hashcode = bitmap_hash (labels);
1864 slot = htab_find_slot_with_hash (table, &ecl,
1865 ecl.hashcode, NO_INSERT);
1869 return ((equiv_class_label_t) *slot)->equivalence_class;
1873 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
1877 equiv_class_add (htab_t table, unsigned int equivalence_class,
1881 equiv_class_label_t ecl = XNEW (struct equiv_class_label);
1883 ecl->labels = labels;
1884 ecl->equivalence_class = equivalence_class;
1885 ecl->hashcode = bitmap_hash (labels);
1887 slot = htab_find_slot_with_hash (table, ecl,
1888 ecl->hashcode, INSERT);
1889 gcc_assert (!*slot);
1890 *slot = (void *) ecl;
1893 /* Perform offline variable substitution.
1895 This is a worst case quadratic time way of identifying variables
1896 that must have equivalent points-to sets, including those caused by
1897 static cycles, and single entry subgraphs, in the constraint graph.
1899 The technique is described in "Exploiting Pointer and Location
1900 Equivalence to Optimize Pointer Analysis. In the 14th International
1901 Static Analysis Symposium (SAS), August 2007." It is known as the
1902 "HU" algorithm, and is equivalent to value numbering the collapsed
1903 constraint graph including evaluating unions.
1905 The general method of finding equivalence classes is as follows:
1906 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1907 Initialize all non-REF nodes to be direct nodes.
1908 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1910 For each constraint containing the dereference, we also do the same
1913 We then compute SCC's in the graph and unify nodes in the same SCC,
1916 For each non-collapsed node x:
1917 Visit all unvisited explicit incoming edges.
1918 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1920 Lookup the equivalence class for pts(x).
1921 If we found one, equivalence_class(x) = found class.
1922 Otherwise, equivalence_class(x) = new class, and new_class is
1923 added to the lookup table.
1925 All direct nodes with the same equivalence class can be replaced
1926 with a single representative node.
1927 All unlabeled nodes (label == 0) are not pointers and all edges
1928 involving them can be eliminated.
1929 We perform these optimizations during rewrite_constraints
1931 In addition to pointer equivalence class finding, we also perform
1932 location equivalence class finding. This is the set of variables
1933 that always appear together in points-to sets. We use this to
1934 compress the size of the points-to sets. */
1936 /* Current maximum pointer equivalence class id. */
1937 static int pointer_equiv_class;
1939 /* Current maximum location equivalence class id. */
1940 static int location_equiv_class;
1942 /* Recursive routine to find strongly connected components in GRAPH,
1943 and label it's nodes with DFS numbers. */
1946 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1950 unsigned int my_dfs;
1952 gcc_assert (si->node_mapping[n] == n);
1953 SET_BIT (si->visited, n);
1954 si->dfs[n] = si->current_index ++;
1955 my_dfs = si->dfs[n];
1957 /* Visit all the successors. */
1958 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1960 unsigned int w = si->node_mapping[i];
1962 if (TEST_BIT (si->deleted, w))
1965 if (!TEST_BIT (si->visited, w))
1966 condense_visit (graph, si, w);
1968 unsigned int t = si->node_mapping[w];
1969 unsigned int nnode = si->node_mapping[n];
1970 gcc_assert (nnode == n);
1972 if (si->dfs[t] < si->dfs[nnode])
1973 si->dfs[n] = si->dfs[t];
1977 /* Visit all the implicit predecessors. */
1978 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1980 unsigned int w = si->node_mapping[i];
1982 if (TEST_BIT (si->deleted, w))
1985 if (!TEST_BIT (si->visited, w))
1986 condense_visit (graph, si, w);
1988 unsigned int t = si->node_mapping[w];
1989 unsigned int nnode = si->node_mapping[n];
1990 gcc_assert (nnode == n);
1992 if (si->dfs[t] < si->dfs[nnode])
1993 si->dfs[n] = si->dfs[t];
1997 /* See if any components have been identified. */
1998 if (si->dfs[n] == my_dfs)
2000 while (VEC_length (unsigned, si->scc_stack) != 0
2001 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
2003 unsigned int w = VEC_pop (unsigned, si->scc_stack);
2004 si->node_mapping[w] = n;
2006 if (!TEST_BIT (graph->direct_nodes, w))
2007 RESET_BIT (graph->direct_nodes, n);
2009 /* Unify our nodes. */
2010 if (graph->preds[w])
2012 if (!graph->preds[n])
2013 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2014 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2016 if (graph->implicit_preds[w])
2018 if (!graph->implicit_preds[n])
2019 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2020 bitmap_ior_into (graph->implicit_preds[n],
2021 graph->implicit_preds[w]);
2023 if (graph->points_to[w])
2025 if (!graph->points_to[n])
2026 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2027 bitmap_ior_into (graph->points_to[n],
2028 graph->points_to[w]);
2031 SET_BIT (si->deleted, n);
2034 VEC_safe_push (unsigned, heap, si->scc_stack, n);
2037 /* Label pointer equivalences. */
2040 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2044 SET_BIT (si->visited, n);
2046 if (!graph->points_to[n])
2047 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2049 /* Label and union our incoming edges's points to sets. */
2050 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2052 unsigned int w = si->node_mapping[i];
2053 if (!TEST_BIT (si->visited, w))
2054 label_visit (graph, si, w);
2056 /* Skip unused edges */
2057 if (w == n || graph->pointer_label[w] == 0)
2060 if (graph->points_to[w])
2061 bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
2063 /* Indirect nodes get fresh variables. */
2064 if (!TEST_BIT (graph->direct_nodes, n))
2065 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2067 if (!bitmap_empty_p (graph->points_to[n]))
2069 unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
2070 graph->points_to[n]);
2073 label = pointer_equiv_class++;
2074 equiv_class_add (pointer_equiv_class_table,
2075 label, graph->points_to[n]);
2077 graph->pointer_label[n] = label;
2081 /* Perform offline variable substitution, discovering equivalence
2082 classes, and eliminating non-pointer variables. */
2084 static struct scc_info *
2085 perform_var_substitution (constraint_graph_t graph)
2088 unsigned int size = graph->size;
2089 struct scc_info *si = init_scc_info (size);
2091 bitmap_obstack_initialize (&iteration_obstack);
2092 pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
2093 equiv_class_label_eq, free);
2094 location_equiv_class_table = htab_create (511, equiv_class_label_hash,
2095 equiv_class_label_eq, free);
2096 pointer_equiv_class = 1;
2097 location_equiv_class = 1;
2099 /* Condense the nodes, which means to find SCC's, count incoming
2100 predecessors, and unite nodes in SCC's. */
2101 for (i = 0; i < FIRST_REF_NODE; i++)
2102 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2103 condense_visit (graph, si, si->node_mapping[i]);
2105 sbitmap_zero (si->visited);
2106 /* Actually the label the nodes for pointer equivalences */
2107 for (i = 0; i < FIRST_REF_NODE; i++)
2108 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2109 label_visit (graph, si, si->node_mapping[i]);
2111 /* Calculate location equivalence labels. */
2112 for (i = 0; i < FIRST_REF_NODE; i++)
2119 if (!graph->pointed_by[i])
2121 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2123 /* Translate the pointed-by mapping for pointer equivalence
2125 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2127 bitmap_set_bit (pointed_by,
2128 graph->pointer_label[si->node_mapping[j]]);
2130 /* The original pointed_by is now dead. */
2131 BITMAP_FREE (graph->pointed_by[i]);
2133 /* Look up the location equivalence label if one exists, or make
2135 label = equiv_class_lookup (location_equiv_class_table,
2139 label = location_equiv_class++;
2140 equiv_class_add (location_equiv_class_table,
2145 if (dump_file && (dump_flags & TDF_DETAILS))
2146 fprintf (dump_file, "Found location equivalence for node %s\n",
2147 get_varinfo (i)->name);
2148 BITMAP_FREE (pointed_by);
2150 graph->loc_label[i] = label;
2154 if (dump_file && (dump_flags & TDF_DETAILS))
2155 for (i = 0; i < FIRST_REF_NODE; i++)
2157 bool direct_node = TEST_BIT (graph->direct_nodes, i);
2159 "Equivalence classes for %s node id %d:%s are pointer: %d"
2161 direct_node ? "Direct node" : "Indirect node", i,
2162 get_varinfo (i)->name,
2163 graph->pointer_label[si->node_mapping[i]],
2164 graph->loc_label[si->node_mapping[i]]);
2167 /* Quickly eliminate our non-pointer variables. */
2169 for (i = 0; i < FIRST_REF_NODE; i++)
2171 unsigned int node = si->node_mapping[i];
2173 if (graph->pointer_label[node] == 0)
2175 if (dump_file && (dump_flags & TDF_DETAILS))
2177 "%s is a non-pointer variable, eliminating edges.\n",
2178 get_varinfo (node)->name);
2179 stats.nonpointer_vars++;
2180 clear_edges_for_node (graph, node);
2187 /* Free information that was only necessary for variable
2191 free_var_substitution_info (struct scc_info *si)
2194 free (graph->pointer_label);
2195 free (graph->loc_label);
2196 free (graph->pointed_by);
2197 free (graph->points_to);
2198 free (graph->eq_rep);
2199 sbitmap_free (graph->direct_nodes);
2200 htab_delete (pointer_equiv_class_table);
2201 htab_delete (location_equiv_class_table);
2202 bitmap_obstack_release (&iteration_obstack);
2205 /* Return an existing node that is equivalent to NODE, which has
2206 equivalence class LABEL, if one exists. Return NODE otherwise. */
2209 find_equivalent_node (constraint_graph_t graph,
2210 unsigned int node, unsigned int label)
2212 /* If the address version of this variable is unused, we can
2213 substitute it for anything else with the same label.
2214 Otherwise, we know the pointers are equivalent, but not the
2215 locations, and we can unite them later. */
2217 if (!bitmap_bit_p (graph->address_taken, node))
2219 gcc_assert (label < graph->size);
2221 if (graph->eq_rep[label] != -1)
2223 /* Unify the two variables since we know they are equivalent. */
2224 if (unite (graph->eq_rep[label], node))
2225 unify_nodes (graph, graph->eq_rep[label], node, false);
2226 return graph->eq_rep[label];
2230 graph->eq_rep[label] = node;
2231 graph->pe_rep[label] = node;
2236 gcc_assert (label < graph->size);
2237 graph->pe[node] = label;
2238 if (graph->pe_rep[label] == -1)
2239 graph->pe_rep[label] = node;
2245 /* Unite pointer equivalent but not location equivalent nodes in
2246 GRAPH. This may only be performed once variable substitution is
2250 unite_pointer_equivalences (constraint_graph_t graph)
2254 /* Go through the pointer equivalences and unite them to their
2255 representative, if they aren't already. */
2256 for (i = 0; i < FIRST_REF_NODE; i++)
2258 unsigned int label = graph->pe[i];
2261 int label_rep = graph->pe_rep[label];
2263 if (label_rep == -1)
2266 label_rep = find (label_rep);
2267 if (label_rep >= 0 && unite (label_rep, find (i)))
2268 unify_nodes (graph, label_rep, i, false);
2273 /* Move complex constraints to the GRAPH nodes they belong to. */
2276 move_complex_constraints (constraint_graph_t graph)
2281 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2285 struct constraint_expr lhs = c->lhs;
2286 struct constraint_expr rhs = c->rhs;
2288 if (lhs.type == DEREF)
2290 insert_into_complex (graph, lhs.var, c);
2292 else if (rhs.type == DEREF)
2294 if (!(get_varinfo (lhs.var)->is_special_var))
2295 insert_into_complex (graph, rhs.var, c);
2297 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2298 && (lhs.offset != 0 || rhs.offset != 0))
2300 insert_into_complex (graph, rhs.var, c);
2307 /* Optimize and rewrite complex constraints while performing
2308 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2309 result of perform_variable_substitution. */
2312 rewrite_constraints (constraint_graph_t graph,
2313 struct scc_info *si)
2319 for (j = 0; j < graph->size; j++)
2320 gcc_assert (find (j) == j);
2322 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2324 struct constraint_expr lhs = c->lhs;
2325 struct constraint_expr rhs = c->rhs;
2326 unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id);
2327 unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id);
2328 unsigned int lhsnode, rhsnode;
2329 unsigned int lhslabel, rhslabel;
2331 lhsnode = si->node_mapping[lhsvar];
2332 rhsnode = si->node_mapping[rhsvar];
2333 lhslabel = graph->pointer_label[lhsnode];
2334 rhslabel = graph->pointer_label[rhsnode];
2336 /* See if it is really a non-pointer variable, and if so, ignore
2340 if (dump_file && (dump_flags & TDF_DETAILS))
2343 fprintf (dump_file, "%s is a non-pointer variable,"
2344 "ignoring constraint:",
2345 get_varinfo (lhs.var)->name);
2346 dump_constraint (dump_file, c);
2348 VEC_replace (constraint_t, constraints, i, NULL);
2354 if (dump_file && (dump_flags & TDF_DETAILS))
2357 fprintf (dump_file, "%s is a non-pointer variable,"
2358 "ignoring constraint:",
2359 get_varinfo (rhs.var)->name);
2360 dump_constraint (dump_file, c);
2362 VEC_replace (constraint_t, constraints, i, NULL);
2366 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2367 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2368 c->lhs.var = lhsvar;
2369 c->rhs.var = rhsvar;
2374 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2375 part of an SCC, false otherwise. */
2378 eliminate_indirect_cycles (unsigned int node)
2380 if (graph->indirect_cycles[node] != -1
2381 && !bitmap_empty_p (get_varinfo (node)->solution))
2384 VEC(unsigned,heap) *queue = NULL;
2386 unsigned int to = find (graph->indirect_cycles[node]);
2389 /* We can't touch the solution set and call unify_nodes
2390 at the same time, because unify_nodes is going to do
2391 bitmap unions into it. */
2393 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2395 if (find (i) == i && i != to)
2398 VEC_safe_push (unsigned, heap, queue, i);
2403 VEC_iterate (unsigned, queue, queuepos, i);
2406 unify_nodes (graph, to, i, true);
2408 VEC_free (unsigned, heap, queue);
2414 /* Solve the constraint graph GRAPH using our worklist solver.
2415 This is based on the PW* family of solvers from the "Efficient Field
2416 Sensitive Pointer Analysis for C" paper.
2417 It works by iterating over all the graph nodes, processing the complex
2418 constraints and propagating the copy constraints, until everything stops
2419 changed. This corresponds to steps 6-8 in the solving list given above. */
2422 solve_graph (constraint_graph_t graph)
2424 unsigned int size = graph->size;
2429 changed = sbitmap_alloc (size);
2430 sbitmap_zero (changed);
2432 /* Mark all initial non-collapsed nodes as changed. */
2433 for (i = 0; i < size; i++)
2435 varinfo_t ivi = get_varinfo (i);
2436 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2437 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2438 || VEC_length (constraint_t, graph->complex[i]) > 0))
2440 SET_BIT (changed, i);
2445 /* Allocate a bitmap to be used to store the changed bits. */
2446 pts = BITMAP_ALLOC (&pta_obstack);
2448 while (changed_count > 0)
2451 struct topo_info *ti = init_topo_info ();
2454 bitmap_obstack_initialize (&iteration_obstack);
2456 compute_topo_order (graph, ti);
2458 while (VEC_length (unsigned, ti->topo_order) != 0)
2461 i = VEC_pop (unsigned, ti->topo_order);
2463 /* If this variable is not a representative, skip it. */
2467 /* In certain indirect cycle cases, we may merge this
2468 variable to another. */
2469 if (eliminate_indirect_cycles (i) && find (i) != i)
2472 /* If the node has changed, we need to process the
2473 complex constraints and outgoing edges again. */
2474 if (TEST_BIT (changed, i))
2479 VEC(constraint_t,heap) *complex = graph->complex[i];
2480 bool solution_empty;
2482 RESET_BIT (changed, i);
2485 /* Compute the changed set of solution bits. */
2486 bitmap_and_compl (pts, get_varinfo (i)->solution,
2487 get_varinfo (i)->oldsolution);
2489 if (bitmap_empty_p (pts))
2492 bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2494 solution = get_varinfo (i)->solution;
2495 solution_empty = bitmap_empty_p (solution);
2497 /* Process the complex constraints */
2498 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2500 /* XXX: This is going to unsort the constraints in
2501 some cases, which will occasionally add duplicate
2502 constraints during unification. This does not
2503 affect correctness. */
2504 c->lhs.var = find (c->lhs.var);
2505 c->rhs.var = find (c->rhs.var);
2507 /* The only complex constraint that can change our
2508 solution to non-empty, given an empty solution,
2509 is a constraint where the lhs side is receiving
2510 some set from elsewhere. */
2511 if (!solution_empty || c->lhs.type != DEREF)
2512 do_complex_constraint (graph, c, pts);
2515 solution_empty = bitmap_empty_p (solution);
2518 /* Do not propagate the ESCAPED/CALLUSED solutions. */
2520 && i != callused_id)
2524 /* Propagate solution to all successors. */
2525 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2531 unsigned int to = find (j);
2532 tmp = get_varinfo (to)->solution;
2535 /* Don't try to propagate to ourselves. */
2539 flag = set_union_with_increment (tmp, pts, 0);
2543 get_varinfo (to)->solution = tmp;
2544 if (!TEST_BIT (changed, to))
2546 SET_BIT (changed, to);
2554 free_topo_info (ti);
2555 bitmap_obstack_release (&iteration_obstack);
2559 sbitmap_free (changed);
2560 bitmap_obstack_release (&oldpta_obstack);
2563 /* Map from trees to variable infos. */
2564 static struct pointer_map_t *vi_for_tree;
2567 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2570 insert_vi_for_tree (tree t, varinfo_t vi)
2572 void **slot = pointer_map_insert (vi_for_tree, t);
2574 gcc_assert (*slot == NULL);
2578 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2579 exist in the map, return NULL, otherwise, return the varinfo we found. */
2582 lookup_vi_for_tree (tree t)
2584 void **slot = pointer_map_contains (vi_for_tree, t);
2588 return (varinfo_t) *slot;
2591 /* Return a printable name for DECL */
2594 alias_get_name (tree decl)
2596 const char *res = get_name (decl);
2598 int num_printed = 0;
2607 if (TREE_CODE (decl) == SSA_NAME)
2609 num_printed = asprintf (&temp, "%s_%u",
2610 alias_get_name (SSA_NAME_VAR (decl)),
2611 SSA_NAME_VERSION (decl));
2613 else if (DECL_P (decl))
2615 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2617 if (num_printed > 0)
2619 res = ggc_strdup (temp);
2625 /* Find the variable id for tree T in the map.
2626 If T doesn't exist in the map, create an entry for it and return it. */
2629 get_vi_for_tree (tree t)
2631 void **slot = pointer_map_contains (vi_for_tree, t);
2633 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2635 return (varinfo_t) *slot;
2638 /* Get a constraint expression for a new temporary variable. */
2640 static struct constraint_expr
2641 get_constraint_exp_for_temp (tree t)
2643 struct constraint_expr cexpr;
2645 gcc_assert (SSA_VAR_P (t));
2647 cexpr.type = SCALAR;
2648 cexpr.var = get_vi_for_tree (t)->id;
2654 /* Get a constraint expression vector from an SSA_VAR_P node.
2655 If address_p is true, the result will be taken its address of. */
2658 get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
2660 struct constraint_expr cexpr;
2663 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2664 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2666 /* For parameters, get at the points-to set for the actual parm
2668 if (TREE_CODE (t) == SSA_NAME
2669 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2670 && SSA_NAME_IS_DEFAULT_DEF (t))
2672 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2676 vi = get_vi_for_tree (t);
2678 cexpr.type = SCALAR;
2680 /* If we determine the result is "anything", and we know this is readonly,
2681 say it points to readonly memory instead. */
2682 if (cexpr.var == anything_id && TREE_READONLY (t))
2685 cexpr.type = ADDRESSOF;
2686 cexpr.var = readonly_id;
2689 /* If we are not taking the address of the constraint expr, add all
2690 sub-fiels of the variable as well. */
2693 for (; vi; vi = vi->next)
2696 VEC_safe_push (ce_s, heap, *results, &cexpr);
2701 VEC_safe_push (ce_s, heap, *results, &cexpr);
2704 /* Process constraint T, performing various simplifications and then
2705 adding it to our list of overall constraints. */
2708 process_constraint (constraint_t t)
2710 struct constraint_expr rhs = t->rhs;
2711 struct constraint_expr lhs = t->lhs;
2713 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2714 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2716 /* ANYTHING == ANYTHING is pointless. */
2717 if (lhs.var == anything_id && rhs.var == anything_id)
2720 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2721 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
2726 process_constraint (t);
2728 /* This can happen in our IR with things like n->a = *p */
2729 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2731 /* Split into tmp = *rhs, *lhs = tmp */
2732 tree rhsdecl = get_varinfo (rhs.var)->decl;
2733 tree pointertype = TREE_TYPE (rhsdecl);
2734 tree pointedtotype = TREE_TYPE (pointertype);
2735 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2736 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
2738 process_constraint (new_constraint (tmplhs, rhs));
2739 process_constraint (new_constraint (lhs, tmplhs));
2741 else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
2743 /* Split into tmp = &rhs, *lhs = tmp */
2744 tree rhsdecl = get_varinfo (rhs.var)->decl;
2745 tree pointertype = TREE_TYPE (rhsdecl);
2746 tree tmpvar = create_tmp_var_raw (pointertype, "derefaddrtmp");
2747 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
2749 process_constraint (new_constraint (tmplhs, rhs));
2750 process_constraint (new_constraint (lhs, tmplhs));
2754 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2755 VEC_safe_push (constraint_t, heap, constraints, t);
2759 /* Return true if T is a type that could contain pointers. */
2762 type_could_have_pointers (tree type)
2764 if (POINTER_TYPE_P (type))
2767 if (TREE_CODE (type) == ARRAY_TYPE)
2768 return type_could_have_pointers (TREE_TYPE (type));
2770 return AGGREGATE_TYPE_P (type);
2773 /* Return true if T is a variable of a type that could contain
2777 could_have_pointers (tree t)
2779 return type_could_have_pointers (TREE_TYPE (t));
2782 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2785 static HOST_WIDE_INT
2786 bitpos_of_field (const tree fdecl)
2789 if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2790 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2793 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2794 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2798 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2799 resulting constraint expressions in *RESULTS. */
2802 get_constraint_for_ptr_offset (tree ptr, tree offset,
2803 VEC (ce_s, heap) **results)
2805 struct constraint_expr *c;
2807 unsigned HOST_WIDE_INT rhsunitoffset, rhsoffset;
2809 /* If we do not do field-sensitive PTA adding offsets to pointers
2810 does not change the points-to solution. */
2811 if (!use_field_sensitive)
2813 get_constraint_for (ptr, results);
2817 /* If the offset is not a non-negative integer constant that fits
2818 in a HOST_WIDE_INT, we have to fall back to a conservative
2819 solution which includes all sub-fields of all pointed-to
2821 ??? As we do not have the ability to express this, fall back
2823 if (!host_integerp (offset, 1))
2825 struct constraint_expr temp;
2826 temp.var = anything_id;
2829 VEC_safe_push (ce_s, heap, *results, &temp);
2833 /* Make sure the bit-offset also fits. */
2834 rhsunitoffset = TREE_INT_CST_LOW (offset);
2835 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
2836 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
2838 struct constraint_expr temp;
2839 temp.var = anything_id;
2842 VEC_safe_push (ce_s, heap, *results, &temp);
2846 get_constraint_for (ptr, results);
2850 /* As we are eventually appending to the solution do not use
2851 VEC_iterate here. */
2852 n = VEC_length (ce_s, *results);
2853 for (j = 0; j < n; j++)
2856 c = VEC_index (ce_s, *results, j);
2857 curr = get_varinfo (c->var);
2859 if (c->type == ADDRESSOF
2860 && !curr->is_full_var)
2862 varinfo_t temp, curr = get_varinfo (c->var);
2864 /* Search the sub-field which overlaps with the
2865 pointed-to offset. As we deal with positive offsets
2866 only, we can start the search from the current variable. */
2867 temp = first_vi_for_offset (curr, curr->offset + rhsoffset);
2869 /* If the result is outside of the variable we have to provide
2870 a conservative result, as the variable is still reachable
2871 from the resulting pointer (even though it technically
2872 cannot point to anything). The last sub-field is such
2873 a conservative result.
2874 ??? If we always had a sub-field for &object + 1 then
2875 we could represent this in a more precise way. */
2879 while (temp->next != NULL)
2884 /* If the found variable is not exactly at the pointed to
2885 result, we have to include the next variable in the
2886 solution as well. Otherwise two increments by offset / 2
2887 do not result in the same or a conservative superset
2889 if (temp->offset != curr->offset + rhsoffset
2890 && temp->next != NULL)
2892 struct constraint_expr c2;
2893 c2.var = temp->next->id;
2894 c2.type = ADDRESSOF;
2896 VEC_safe_push (ce_s, heap, *results, &c2);
2901 else if (c->type == ADDRESSOF
2902 /* If this varinfo represents a full variable just use it. */
2903 && curr->is_full_var)
2906 c->offset = rhsoffset;
2911 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
2912 If address_p is true the result will be taken its address of. */
2915 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
2919 HOST_WIDE_INT bitsize = -1;
2920 HOST_WIDE_INT bitmaxsize = -1;
2921 HOST_WIDE_INT bitpos;
2923 struct constraint_expr *result;
2925 /* Some people like to do cute things like take the address of
2928 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2929 forzero = TREE_OPERAND (forzero, 0);
2931 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2933 struct constraint_expr temp;
2936 temp.var = integer_id;
2938 VEC_safe_push (ce_s, heap, *results, &temp);
2942 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2944 /* Pretend to take the address of the base, we'll take care of
2945 adding the required subset of sub-fields below. */
2946 get_constraint_for_1 (t, results, true);
2947 gcc_assert (VEC_length (ce_s, *results) == 1);
2948 result = VEC_last (ce_s, *results);
2950 /* This can also happen due to weird offsetof type macros. */
2951 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2952 result->type = SCALAR;
2954 if (result->type == SCALAR
2955 && get_varinfo (result->var)->is_full_var)
2956 /* For single-field vars do not bother about the offset. */
2958 else if (result->type == SCALAR)
2960 /* In languages like C, you can access one past the end of an
2961 array. You aren't allowed to dereference it, so we can
2962 ignore this constraint. When we handle pointer subtraction,
2963 we may have to do something cute here. */
2965 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
2968 /* It's also not true that the constraint will actually start at the
2969 right offset, it may start in some padding. We only care about
2970 setting the constraint to the first actual field it touches, so
2972 struct constraint_expr cexpr = *result;
2974 VEC_pop (ce_s, *results);
2976 for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
2978 if (ranges_overlap_p (curr->offset, curr->size,
2979 bitpos, bitmaxsize))
2981 cexpr.var = curr->id;
2982 VEC_safe_push (ce_s, heap, *results, &cexpr);
2987 /* If we are going to take the address of this field then
2988 to be able to compute reachability correctly add at least
2989 the last field of the variable. */
2991 && VEC_length (ce_s, *results) == 0)
2993 curr = get_varinfo (cexpr.var);
2994 while (curr->next != NULL)
2996 cexpr.var = curr->id;
2997 VEC_safe_push (ce_s, heap, *results, &cexpr);
3000 /* Assert that we found *some* field there. The user couldn't be
3001 accessing *only* padding. */
3002 /* Still the user could access one past the end of an array
3003 embedded in a struct resulting in accessing *only* padding. */
3004 gcc_assert (VEC_length (ce_s, *results) >= 1
3005 || ref_contains_array_ref (orig_t));
3007 else if (bitmaxsize == 0)
3009 if (dump_file && (dump_flags & TDF_DETAILS))
3010 fprintf (dump_file, "Access to zero-sized part of variable,"
3014 if (dump_file && (dump_flags & TDF_DETAILS))
3015 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3017 else if (bitmaxsize == -1)
3019 /* We can't handle DEREF constraints with unknown size, we'll
3020 get the wrong answer. Punt and return anything. */
3021 result->var = anything_id;
3025 result->offset = bitpos;
3029 /* Dereference the constraint expression CONS, and return the result.
3030 DEREF (ADDRESSOF) = SCALAR
3031 DEREF (SCALAR) = DEREF
3032 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3033 This is needed so that we can handle dereferencing DEREF constraints. */
3036 do_deref (VEC (ce_s, heap) **constraints)
3038 struct constraint_expr *c;
3041 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3043 if (c->type == SCALAR)
3045 else if (c->type == ADDRESSOF)
3047 else if (c->type == DEREF)
3049 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
3050 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
3051 process_constraint (new_constraint (tmplhs, *c));
3052 c->var = tmplhs.var;
3059 /* Given a tree T, return the constraint expression for it. */
3062 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3064 struct constraint_expr temp;
3066 /* x = integer is all glommed to a single variable, which doesn't
3067 point to anything by itself. That is, of course, unless it is an
3068 integer constant being treated as a pointer, in which case, we
3069 will return that this is really the addressof anything. This
3070 happens below, since it will fall into the default case. The only
3071 case we know something about an integer treated like a pointer is
3072 when it is the NULL pointer, and then we just say it points to
3075 Do not do that if -fno-delete-null-pointer-checks though, because
3076 in that case *NULL does not fail, so it _should_ alias *anything.
3077 It is not worth adding a new option or renaming the existing one,
3078 since this case is relatively obscure. */
3079 if (flag_delete_null_pointer_checks
3080 && TREE_CODE (t) == INTEGER_CST
3081 && integer_zerop (t))
3083 temp.var = nothing_id;
3084 temp.type = ADDRESSOF;
3086 VEC_safe_push (ce_s, heap, *results, &temp);
3090 /* String constants are read-only. */
3091 if (TREE_CODE (t) == STRING_CST)
3093 temp.var = readonly_id;
3096 VEC_safe_push (ce_s, heap, *results, &temp);
3100 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3102 case tcc_expression:
3104 switch (TREE_CODE (t))
3108 struct constraint_expr *c;
3110 tree exp = TREE_OPERAND (t, 0);
3112 get_constraint_for_1 (exp, results, true);
3114 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3116 if (c->type == DEREF)
3119 c->type = ADDRESSOF;
3130 switch (TREE_CODE (t))
3134 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3139 case ARRAY_RANGE_REF:
3141 get_constraint_for_component_ref (t, results, address_p);
3147 case tcc_exceptional:
3149 switch (TREE_CODE (t))
3153 get_constraint_for_ssa_var (t, results, address_p);
3160 case tcc_declaration:
3162 get_constraint_for_ssa_var (t, results, address_p);
3168 /* The default fallback is a constraint from anything. */
3169 temp.type = ADDRESSOF;
3170 temp.var = anything_id;
3172 VEC_safe_push (ce_s, heap, *results, &temp);
3175 /* Given a gimple tree T, return the constraint expression vector for it. */
3178 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3180 gcc_assert (VEC_length (ce_s, *results) == 0);
3182 get_constraint_for_1 (t, results, false);
3185 /* Handle the structure copy case where we have a simple structure copy
3186 between LHS and RHS that is of SIZE (in bits)
3188 For each field of the lhs variable (lhsfield)
3189 For each field of the rhs variable at lhsfield.offset (rhsfield)
3190 add the constraint lhsfield = rhsfield
3192 If we fail due to some kind of type unsafety or other thing we
3193 can't handle, return false. We expect the caller to collapse the
3194 variable in that case. */
3197 do_simple_structure_copy (const struct constraint_expr lhs,
3198 const struct constraint_expr rhs,
3199 const unsigned HOST_WIDE_INT size)
3201 varinfo_t p = get_varinfo (lhs.var);
3202 unsigned HOST_WIDE_INT pstart, last;
3204 last = p->offset + size;
3205 for (; p && p->offset < last; p = p->next)
3208 struct constraint_expr templhs = lhs;
3209 struct constraint_expr temprhs = rhs;
3210 unsigned HOST_WIDE_INT fieldoffset;
3212 templhs.var = p->id;
3213 q = get_varinfo (temprhs.var);
3214 fieldoffset = p->offset - pstart;
3215 q = first_vi_for_offset (q, q->offset + fieldoffset);
3218 temprhs.var = q->id;
3219 process_constraint (new_constraint (templhs, temprhs));
3225 /* Handle the structure copy case where we have a structure copy between a
3226 aggregate on the LHS and a dereference of a pointer on the RHS
3227 that is of SIZE (in bits)
3229 For each field of the lhs variable (lhsfield)
3230 rhs.offset = lhsfield->offset
3231 add the constraint lhsfield = rhs
3235 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
3236 const struct constraint_expr rhs,
3237 const unsigned HOST_WIDE_INT size)
3239 varinfo_t p = get_varinfo (lhs.var);
3240 unsigned HOST_WIDE_INT pstart,last;
3242 last = p->offset + size;
3244 for (; p && p->offset < last; p = p->next)
3247 struct constraint_expr templhs = lhs;
3248 struct constraint_expr temprhs = rhs;
3249 unsigned HOST_WIDE_INT fieldoffset;
3252 if (templhs.type == SCALAR)
3253 templhs.var = p->id;
3255 templhs.offset = p->offset;
3257 q = get_varinfo (temprhs.var);
3258 fieldoffset = p->offset - pstart;
3259 temprhs.offset += fieldoffset;
3260 process_constraint (new_constraint (templhs, temprhs));
3264 /* Handle the structure copy case where we have a structure copy
3265 between an aggregate on the RHS and a dereference of a pointer on
3266 the LHS that is of SIZE (in bits)
3268 For each field of the rhs variable (rhsfield)
3269 lhs.offset = rhsfield->offset
3270 add the constraint lhs = rhsfield
3274 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
3275 const struct constraint_expr rhs,
3276 const unsigned HOST_WIDE_INT size)
3278 varinfo_t p = get_varinfo (rhs.var);
3279 unsigned HOST_WIDE_INT pstart,last;
3281 last = p->offset + size;
3283 for (; p && p->offset < last; p = p->next)
3286 struct constraint_expr templhs = lhs;
3287 struct constraint_expr temprhs = rhs;
3288 unsigned HOST_WIDE_INT fieldoffset;
3291 if (temprhs.type == SCALAR)
3292 temprhs.var = p->id;
3294 temprhs.offset = p->offset;
3296 q = get_varinfo (templhs.var);
3297 fieldoffset = p->offset - pstart;
3298 templhs.offset += fieldoffset;
3299 process_constraint (new_constraint (templhs, temprhs));
3303 /* Sometimes, frontends like to give us bad type information. This
3304 function will collapse all the fields from VAR to the end of VAR,
3305 into VAR, so that we treat those fields as a single variable.
3306 We return the variable they were collapsed into. */
3309 collapse_rest_of_var (unsigned int var)
3311 varinfo_t currvar = get_varinfo (var);
3314 for (field = currvar->next; field; field = field->next)
3317 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
3318 field->name, currvar->name);
3320 gcc_assert (field->collapsed_to == 0);
3321 field->collapsed_to = currvar->id;
3324 currvar->next = NULL;
3325 currvar->size = currvar->fullsize - currvar->offset;
3330 /* Handle aggregate copies by expanding into copies of the respective
3331 fields of the structures. */
3334 do_structure_copy (tree lhsop, tree rhsop)
3336 struct constraint_expr lhs, rhs, tmp;
3337 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3339 unsigned HOST_WIDE_INT lhssize;
3340 unsigned HOST_WIDE_INT rhssize;
3342 /* Pretend we are taking the address of the constraint exprs.
3343 We deal with walking the sub-fields ourselves. */
3344 get_constraint_for_1 (lhsop, &lhsc, true);
3345 get_constraint_for_1 (rhsop, &rhsc, true);
3346 gcc_assert (VEC_length (ce_s, lhsc) == 1);
3347 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3348 lhs = *(VEC_last (ce_s, lhsc));
3349 rhs = *(VEC_last (ce_s, rhsc));
3351 VEC_free (ce_s, heap, lhsc);
3352 VEC_free (ce_s, heap, rhsc);
3354 /* If we have special var = x, swap it around. */
3355 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
3362 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
3363 possible it's something we could handle. However, most cases falling
3364 into this are dealing with transparent unions, which are slightly
3366 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
3368 rhs.type = ADDRESSOF;
3369 rhs.var = anything_id;
3372 /* If the RHS is a special var, or an addressof, set all the LHS fields to
3373 that special var. */
3374 if (rhs.var <= integer_id)
3376 for (p = get_varinfo (lhs.var); p; p = p->next)
3378 struct constraint_expr templhs = lhs;
3379 struct constraint_expr temprhs = rhs;
3381 if (templhs.type == SCALAR )
3382 templhs.var = p->id;
3384 templhs.offset += p->offset;
3385 process_constraint (new_constraint (templhs, temprhs));
3390 tree rhstype = TREE_TYPE (rhsop);
3391 tree lhstype = TREE_TYPE (lhsop);
3395 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
3396 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
3398 /* If we have a variably sized types on the rhs or lhs, and a deref
3399 constraint, add the constraint, lhsconstraint = &ANYTHING.
3400 This is conservatively correct because either the lhs is an unknown
3401 sized var (if the constraint is SCALAR), or the lhs is a DEREF
3402 constraint, and every variable it can point to must be unknown sized
3403 anyway, so we don't need to worry about fields at all. */
3404 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
3405 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
3407 rhs.var = anything_id;
3408 rhs.type = ADDRESSOF;
3410 process_constraint (new_constraint (lhs, rhs));
3414 /* The size only really matters insofar as we don't set more or less of
3415 the variable. If we hit an unknown size var, the size should be the
3416 whole darn thing. */
3417 if (get_varinfo (rhs.var)->is_unknown_size_var)
3420 rhssize = TREE_INT_CST_LOW (rhstypesize);
3422 if (get_varinfo (lhs.var)->is_unknown_size_var)
3425 lhssize = TREE_INT_CST_LOW (lhstypesize);
3428 if (rhs.type == SCALAR && lhs.type == SCALAR)
3430 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
3432 lhs.var = collapse_rest_of_var (get_varinfo_fc (lhs.var)->id);
3433 rhs.var = collapse_rest_of_var (get_varinfo_fc (rhs.var)->id);
3438 process_constraint (new_constraint (lhs, rhs));
3441 else if (lhs.type != DEREF && rhs.type == DEREF)
3442 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3443 else if (lhs.type == DEREF && rhs.type != DEREF)
3444 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3447 tree pointedtotype = lhstype;
3450 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3451 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
3452 do_structure_copy (tmpvar, rhsop);
3453 do_structure_copy (lhsop, tmpvar);
3458 /* Create a constraint ID = OP. */
3461 make_constraint_to (unsigned id, tree op)
3463 VEC(ce_s, heap) *rhsc = NULL;
3464 struct constraint_expr *c;
3465 struct constraint_expr includes;
3469 includes.offset = 0;
3470 includes.type = SCALAR;
3472 get_constraint_for (op, &rhsc);
3473 for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3474 process_constraint (new_constraint (includes, *c));
3475 VEC_free (ce_s, heap, rhsc);
3478 /* Make constraints necessary to make OP escape. */
3481 make_escape_constraint (tree op)
3483 make_constraint_to (escaped_id, op);
3486 /* For non-IPA mode, generate constraints necessary for a call on the
3490 handle_rhs_call (gimple stmt)
3494 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3496 tree arg = gimple_call_arg (stmt, i);
3498 /* Find those pointers being passed, and make sure they end up
3499 pointing to anything. */
3500 if (could_have_pointers (arg))
3501 make_escape_constraint (arg);
3504 /* The static chain escapes as well. */
3505 if (gimple_call_chain (stmt))
3506 make_escape_constraint (gimple_call_chain (stmt));
3509 /* For non-IPA mode, generate constraints necessary for a call
3510 that returns a pointer and assigns it to LHS. This simply makes
3511 the LHS point to global and escaped variables. */
3514 handle_lhs_call (tree lhs, int flags)
3516 VEC(ce_s, heap) *lhsc = NULL;
3517 struct constraint_expr rhsc;
3519 struct constraint_expr *lhsp;
3521 get_constraint_for (lhs, &lhsc);
3523 if (flags & ECF_MALLOC)
3525 tree heapvar = heapvar_lookup (lhs);
3528 if (heapvar == NULL)
3530 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
3531 DECL_EXTERNAL (heapvar) = 1;
3532 get_var_ann (heapvar)->is_heapvar = 1;
3533 if (gimple_referenced_vars (cfun))
3534 add_referenced_var (heapvar);
3535 heapvar_insert (lhs, heapvar);
3538 rhsc.var = create_variable_info_for (heapvar,
3539 alias_get_name (heapvar));
3540 vi = get_varinfo (rhsc.var);
3541 vi->is_artificial_var = 1;
3542 vi->is_heap_var = 1;
3543 vi->is_unknown_size_var = true;
3546 rhsc.type = ADDRESSOF;
3551 rhsc.var = escaped_id;
3553 rhsc.type = ADDRESSOF;
3555 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3556 process_constraint (new_constraint (*lhsp, rhsc));
3557 VEC_free (ce_s, heap, lhsc);
3560 /* For non-IPA mode, generate constraints necessary for a call of a
3561 const function that returns a pointer in the statement STMT. */
3564 handle_const_call (gimple stmt)
3566 tree lhs = gimple_call_lhs (stmt);
3567 VEC(ce_s, heap) *lhsc = NULL;
3568 struct constraint_expr rhsc;
3570 struct constraint_expr *lhsp;
3572 struct constraint_expr tmpc;
3574 get_constraint_for (lhs, &lhsc);
3576 /* If this is a nested function then it can return anything. */
3577 if (gimple_call_chain (stmt))
3579 rhsc.var = anything_id;
3581 rhsc.type = ADDRESSOF;
3582 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3583 process_constraint (new_constraint (*lhsp, rhsc));
3584 VEC_free (ce_s, heap, lhsc);
3588 /* We always use a temporary here, otherwise we end up with a quadratic
3589 amount of constraints for
3590 large_struct = const_call (large_struct);
3591 in field-sensitive PTA. */
3592 tmpvar = create_tmp_var_raw (ptr_type_node, "consttmp");
3593 tmpc = get_constraint_exp_for_temp (tmpvar);
3595 /* May return addresses of globals. */
3596 rhsc.var = nonlocal_id;
3598 rhsc.type = ADDRESSOF;
3599 process_constraint (new_constraint (tmpc, rhsc));
3601 /* May return arguments. */
3602 for (k = 0; k < gimple_call_num_args (stmt); ++k)
3604 tree arg = gimple_call_arg (stmt, k);
3606 if (could_have_pointers (arg))
3608 VEC(ce_s, heap) *argc = NULL;
3609 struct constraint_expr *argp;
3612 get_constraint_for (arg, &argc);
3613 for (i = 0; VEC_iterate (ce_s, argc, i, argp); i++)
3614 process_constraint (new_constraint (tmpc, *argp));
3615 VEC_free (ce_s, heap, argc);
3619 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3620 process_constraint (new_constraint (*lhsp, tmpc));
3622 VEC_free (ce_s, heap, lhsc);
3625 /* For non-IPA mode, generate constraints necessary for a call to a
3626 pure function in statement STMT. */
3629 handle_pure_call (gimple stmt)
3633 /* Memory reached from pointer arguments is call-used. */
3634 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3636 tree arg = gimple_call_arg (stmt, i);
3638 if (could_have_pointers (arg))
3639 make_constraint_to (callused_id, arg);
3642 /* The static chain is used as well. */
3643 if (gimple_call_chain (stmt))
3644 make_constraint_to (callused_id, gimple_call_chain (stmt));
3646 /* If the call returns a pointer it may point to reachable memory
3647 from the arguments. Not so for malloc functions though. */
3648 if (gimple_call_lhs (stmt)
3649 && could_have_pointers (gimple_call_lhs (stmt))
3650 && !(gimple_call_flags (stmt) & ECF_MALLOC))
3652 tree lhs = gimple_call_lhs (stmt);
3653 VEC(ce_s, heap) *lhsc = NULL;
3654 struct constraint_expr rhsc;
3655 struct constraint_expr *lhsp;
3658 get_constraint_for (lhs, &lhsc);
3660 /* If this is a nested function then it can return anything. */
3661 if (gimple_call_chain (stmt))
3663 rhsc.var = anything_id;
3665 rhsc.type = ADDRESSOF;
3666 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3667 process_constraint (new_constraint (*lhsp, rhsc));
3668 VEC_free (ce_s, heap, lhsc);
3672 /* Else just add the call-used memory here. Escaped variables
3673 and globals will be dealt with in handle_lhs_call. */
3674 rhsc.var = callused_id;
3676 rhsc.type = ADDRESSOF;
3677 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3678 process_constraint (new_constraint (*lhsp, rhsc));
3679 VEC_free (ce_s, heap, lhsc);
3683 /* Walk statement T setting up aliasing constraints according to the
3684 references found in T. This function is the main part of the
3685 constraint builder. AI points to auxiliary alias information used
3686 when building alias sets and computing alias grouping heuristics. */
3689 find_func_aliases (gimple origt)
3692 VEC(ce_s, heap) *lhsc = NULL;
3693 VEC(ce_s, heap) *rhsc = NULL;
3694 struct constraint_expr *c;
3695 enum escape_type stmt_escape_type;
3697 /* Now build constraints expressions. */
3698 if (gimple_code (t) == GIMPLE_PHI)
3700 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (gimple_phi_result (t))));
3702 /* Only care about pointers and structures containing
3704 if (could_have_pointers (gimple_phi_result (t)))
3709 /* For a phi node, assign all the arguments to
3711 get_constraint_for (gimple_phi_result (t), &lhsc);
3712 for (i = 0; i < gimple_phi_num_args (t); i++)
3715 tree strippedrhs = PHI_ARG_DEF (t, i);
3717 STRIP_NOPS (strippedrhs);
3718 rhstype = TREE_TYPE (strippedrhs);
3719 get_constraint_for (gimple_phi_arg_def (t, i), &rhsc);
3721 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3723 struct constraint_expr *c2;
3724 while (VEC_length (ce_s, rhsc) > 0)
3726 c2 = VEC_last (ce_s, rhsc);
3727 process_constraint (new_constraint (*c, *c2));
3728 VEC_pop (ce_s, rhsc);
3734 /* In IPA mode, we need to generate constraints to pass call
3735 arguments through their calls. There are two cases,
3736 either a GIMPLE_CALL returning a value, or just a plain
3737 GIMPLE_CALL when we are not.
3739 In non-ipa mode, we need to generate constraints for each
3740 pointer passed by address. */
3741 else if (is_gimple_call (t))
3745 int flags = gimple_call_flags (t);
3747 /* Const functions can return their arguments and addresses
3748 of global memory but not of escaped memory. */
3749 if (flags & ECF_CONST)
3751 if (gimple_call_lhs (t)
3752 && could_have_pointers (gimple_call_lhs (t)))
3753 handle_const_call (t);
3755 /* Pure functions can return addresses in and of memory
3756 reachable from their arguments, but they are not an escape
3757 point for reachable memory of their arguments. */
3758 else if (flags & ECF_PURE)
3760 handle_pure_call (t);
3761 if (gimple_call_lhs (t)
3762 && could_have_pointers (gimple_call_lhs (t)))
3763 handle_lhs_call (gimple_call_lhs (t), flags);
3767 handle_rhs_call (t);
3768 if (gimple_call_lhs (t)
3769 && could_have_pointers (gimple_call_lhs (t)))
3770 handle_lhs_call (gimple_call_lhs (t), flags);
3781 lhsop = gimple_call_lhs (t);
3782 decl = gimple_call_fndecl (t);
3784 /* If we can directly resolve the function being called, do so.
3785 Otherwise, it must be some sort of indirect expression that
3786 we should still be able to handle. */
3788 fi = get_vi_for_tree (decl);
3791 decl = gimple_call_fn (t);
3792 fi = get_vi_for_tree (decl);
3795 /* Assign all the passed arguments to the appropriate incoming
3796 parameters of the function. */
3797 for (j = 0; j < gimple_call_num_args (t); j++)
3799 struct constraint_expr lhs ;
3800 struct constraint_expr *rhsp;
3801 tree arg = gimple_call_arg (t, j);
3803 get_constraint_for (arg, &rhsc);
3804 if (TREE_CODE (decl) != FUNCTION_DECL)
3813 lhs.var = first_vi_for_offset (fi, i)->id;
3816 while (VEC_length (ce_s, rhsc) != 0)
3818 rhsp = VEC_last (ce_s, rhsc);
3819 process_constraint (new_constraint (lhs, *rhsp));
3820 VEC_pop (ce_s, rhsc);
3825 /* If we are returning a value, assign it to the result. */
3828 struct constraint_expr rhs;
3829 struct constraint_expr *lhsp;
3832 get_constraint_for (lhsop, &lhsc);
3833 if (TREE_CODE (decl) != FUNCTION_DECL)
3842 rhs.var = first_vi_for_offset (fi, i)->id;
3845 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3846 process_constraint (new_constraint (*lhsp, rhs));
3850 /* Otherwise, just a regular assignment statement. Only care about
3851 operations with pointer result, others are dealt with as escape
3852 points if they have pointer operands. */
3853 else if (is_gimple_assign (t)
3854 && could_have_pointers (gimple_assign_lhs (t)))
3856 /* Otherwise, just a regular assignment statement. */
3857 tree lhsop = gimple_assign_lhs (t);
3858 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
3860 if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
3861 do_structure_copy (lhsop, rhsop);
3865 struct constraint_expr temp;
3866 get_constraint_for (lhsop, &lhsc);
3868 if (gimple_assign_rhs_code (t) == POINTER_PLUS_EXPR)
3869 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
3870 gimple_assign_rhs2 (t), &rhsc);
3871 else if ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
3872 && !(POINTER_TYPE_P (gimple_expr_type (t))
3873 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
3874 || gimple_assign_single_p (t))
3875 get_constraint_for (rhsop, &rhsc);
3878 temp.type = ADDRESSOF;
3879 temp.var = anything_id;
3881 VEC_safe_push (ce_s, heap, rhsc, &temp);
3883 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3885 struct constraint_expr *c2;
3888 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3889 process_constraint (new_constraint (*c, *c2));
3893 else if (gimple_code (t) == GIMPLE_CHANGE_DYNAMIC_TYPE)
3897 get_constraint_for (gimple_cdt_location (t), &lhsc);
3898 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); ++j)
3899 get_varinfo (c->var)->no_tbaa_pruning = true;
3902 stmt_escape_type = is_escape_site (t);
3903 if (stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
3905 gcc_assert (is_gimple_assign (t));
3906 if (gimple_assign_rhs_code (t) == ADDR_EXPR)
3908 tree rhs = gimple_assign_rhs1 (t);
3909 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3912 || !is_global_var (base)))
3913 make_escape_constraint (rhs);
3915 else if (get_gimple_rhs_class (gimple_assign_rhs_code (t))
3916 == GIMPLE_SINGLE_RHS)
3918 if (could_have_pointers (gimple_assign_rhs1 (t)))
3919 make_escape_constraint (gimple_assign_rhs1 (t));
3924 else if (stmt_escape_type == ESCAPE_BAD_CAST)
3926 gcc_assert (is_gimple_assign (t));
3927 gcc_assert (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
3928 || gimple_assign_rhs_code (t) == VIEW_CONVERT_EXPR);
3929 make_escape_constraint (gimple_assign_rhs1 (t));
3931 else if (stmt_escape_type == ESCAPE_TO_ASM)
3934 for (i = 0; i < gimple_asm_noutputs (t); ++i)
3936 tree op = TREE_VALUE (gimple_asm_output_op (t, i));
3937 if (op && could_have_pointers (op))
3938 /* Strictly we'd only need the constraints from ESCAPED and
3940 make_escape_constraint (op);
3942 for (i = 0; i < gimple_asm_ninputs (t); ++i)
3944 tree op = TREE_VALUE (gimple_asm_input_op (t, i));
3945 if (op && could_have_pointers (op))
3946 /* Strictly we'd only need the constraint to ESCAPED. */
3947 make_escape_constraint (op);
3951 /* After promoting variables and computing aliasing we will
3952 need to re-scan most statements. FIXME: Try to minimize the
3953 number of statements re-scanned. It's not really necessary to
3954 re-scan *all* statements. */
3956 gimple_set_modified (origt, true);
3957 VEC_free (ce_s, heap, rhsc);
3958 VEC_free (ce_s, heap, lhsc);
3962 /* Find the first varinfo in the same variable as START that overlaps with
3964 Effectively, walk the chain of fields for the variable START to find the
3965 first field that overlaps with OFFSET.
3966 Return NULL if we can't find one. */
3969 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3971 varinfo_t curr = start;
3974 /* We may not find a variable in the field list with the actual
3975 offset when when we have glommed a structure to a variable.
3976 In that case, however, offset should still be within the size
3978 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3986 /* Insert the varinfo FIELD into the field list for BASE, at the front
3990 insert_into_field_list (varinfo_t base, varinfo_t field)
3992 varinfo_t prev = base;
3993 varinfo_t curr = base->next;
3999 /* Insert the varinfo FIELD into the field list for BASE, ordered by
4003 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
4005 varinfo_t prev = base;
4006 varinfo_t curr = base->next;
4017 if (field->offset <= curr->offset)
4022 field->next = prev->next;
4027 /* This structure is used during pushing fields onto the fieldstack
4028 to track the offset of the field, since bitpos_of_field gives it
4029 relative to its immediate containing type, and we want it relative
4030 to the ultimate containing object. */
4034 /* Offset from the base of the base containing object to this field. */
4035 HOST_WIDE_INT offset;
4037 /* Size, in bits, of the field. */
4038 unsigned HOST_WIDE_INT size;
4040 unsigned has_unknown_size : 1;
4042 unsigned may_have_pointers : 1;
4044 typedef struct fieldoff fieldoff_s;
4046 DEF_VEC_O(fieldoff_s);
4047 DEF_VEC_ALLOC_O(fieldoff_s,heap);
4049 /* qsort comparison function for two fieldoff's PA and PB */
4052 fieldoff_compare (const void *pa, const void *pb)
4054 const fieldoff_s *foa = (const fieldoff_s *)pa;
4055 const fieldoff_s *fob = (const fieldoff_s *)pb;
4056 unsigned HOST_WIDE_INT foasize, fobsize;
4058 if (foa->offset < fob->offset)
4060 else if (foa->offset > fob->offset)
4063 foasize = foa->size;
4064 fobsize = fob->size;
4065 if (foasize < fobsize)
4067 else if (foasize > fobsize)
4072 /* Sort a fieldstack according to the field offset and sizes. */
4074 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
4076 qsort (VEC_address (fieldoff_s, fieldstack),
4077 VEC_length (fieldoff_s, fieldstack),
4078 sizeof (fieldoff_s),
4082 /* Return true if V is a tree that we can have subvars for.
4083 Normally, this is any aggregate type. Also complex
4084 types which are not gimple registers can have subvars. */
4087 var_can_have_subvars (const_tree v)
4089 /* Volatile variables should never have subvars. */
4090 if (TREE_THIS_VOLATILE (v))
4093 /* Non decls or memory tags can never have subvars. */
4094 if (!DECL_P (v) || MTAG_P (v))
4097 /* Aggregates without overlapping fields can have subvars. */
4098 if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
4104 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4105 the fields of TYPE onto fieldstack, recording their offsets along
4108 OFFSET is used to keep track of the offset in this entire
4109 structure, rather than just the immediately containing structure.
4110 Returns the number of fields pushed. */
4113 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
4114 HOST_WIDE_INT offset)
4119 if (TREE_CODE (type) != RECORD_TYPE)
4122 /* If the vector of fields is growing too big, bail out early.
4123 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4125 if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
4128 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
4129 if (TREE_CODE (field) == FIELD_DECL)
4133 HOST_WIDE_INT foff = bitpos_of_field (field);
4135 if (!var_can_have_subvars (field)
4136 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
4137 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
4139 else if (!(pushed = push_fields_onto_fieldstack
4140 (TREE_TYPE (field), fieldstack, offset + foff))
4141 && (DECL_SIZE (field)
4142 && !integer_zerop (DECL_SIZE (field))))
4143 /* Empty structures may have actual size, like in C++. So
4144 see if we didn't push any subfields and the size is
4145 nonzero, push the field onto the stack. */
4150 fieldoff_s *pair = NULL;
4151 bool has_unknown_size = false;
4153 if (!VEC_empty (fieldoff_s, *fieldstack))
4154 pair = VEC_last (fieldoff_s, *fieldstack);
4156 if (!DECL_SIZE (field)
4157 || !host_integerp (DECL_SIZE (field), 1))
4158 has_unknown_size = true;
4160 /* If adjacent fields do not contain pointers merge them. */
4162 && !pair->may_have_pointers
4163 && !could_have_pointers (field)
4164 && !pair->has_unknown_size
4165 && !has_unknown_size
4166 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
4168 pair = VEC_last (fieldoff_s, *fieldstack);
4169 pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
4173 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
4174 pair->offset = offset + foff;
4175 pair->has_unknown_size = has_unknown_size;
4176 if (!has_unknown_size)
4177 pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
4180 pair->may_have_pointers = could_have_pointers (field);
4191 /* Create a constraint ID = &FROM. */
4194 make_constraint_from (varinfo_t vi, int from)
4196 struct constraint_expr lhs, rhs;
4204 rhs.type = ADDRESSOF;
4205 process_constraint (new_constraint (lhs, rhs));
4208 /* Count the number of arguments DECL has, and set IS_VARARGS to true
4209 if it is a varargs function. */
4212 count_num_arguments (tree decl, bool *is_varargs)
4217 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
4221 if (TREE_VALUE (t) == void_type_node)
4231 /* Creation function node for DECL, using NAME, and return the index
4232 of the variable we've created for the function. */
4235 create_function_info_for (tree decl, const char *name)
4237 unsigned int index = VEC_length (varinfo_t, varmap);
4241 bool is_varargs = false;
4243 /* Create the variable info. */
4245 vi = new_var_info (decl, index, name);
4249 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
4250 insert_vi_for_tree (vi->decl, vi);
4251 VEC_safe_push (varinfo_t, heap, varmap, vi);
4255 /* If it's varargs, we don't know how many arguments it has, so we
4261 vi->is_unknown_size_var = true;
4266 arg = DECL_ARGUMENTS (decl);
4268 /* Set up variables for each argument. */
4269 for (i = 1; i < vi->fullsize; i++)
4272 const char *newname;
4274 unsigned int newindex;
4275 tree argdecl = decl;
4280 newindex = VEC_length (varinfo_t, varmap);
4281 asprintf (&tempname, "%s.arg%d", name, i-1);
4282 newname = ggc_strdup (tempname);
4285 argvi = new_var_info (argdecl, newindex, newname);
4286 argvi->decl = argdecl;
4287 VEC_safe_push (varinfo_t, heap, varmap, argvi);
4290 argvi->is_full_var = true;
4291 argvi->fullsize = vi->fullsize;
4292 insert_into_field_list_sorted (vi, argvi);
4293 stats.total_vars ++;
4296 insert_vi_for_tree (arg, argvi);
4297 arg = TREE_CHAIN (arg);
4301 /* Create a variable for the return var. */
4302 if (DECL_RESULT (decl) != NULL
4303 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
4306 const char *newname;
4308 unsigned int newindex;
4309 tree resultdecl = decl;
4313 if (DECL_RESULT (decl))
4314 resultdecl = DECL_RESULT (decl);
4316 newindex = VEC_length (varinfo_t, varmap);
4317 asprintf (&tempname, "%s.result", name);
4318 newname = ggc_strdup (tempname);
4321 resultvi = new_var_info (resultdecl, newindex, newname);
4322 resultvi->decl = resultdecl;
4323 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
4324 resultvi->offset = i;
4326 resultvi->fullsize = vi->fullsize;
4327 resultvi->is_full_var = true;
4328 insert_into_field_list_sorted (vi, resultvi);
4329 stats.total_vars ++;
4330 if (DECL_RESULT (decl))
4331 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
4337 /* Return true if FIELDSTACK contains fields that overlap.
4338 FIELDSTACK is assumed to be sorted by offset. */
4341 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
4343 fieldoff_s *fo = NULL;
4345 HOST_WIDE_INT lastoffset = -1;
4347 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4349 if (fo->offset == lastoffset)
4351 lastoffset = fo->offset;
4356 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4357 This will also create any varinfo structures necessary for fields
4361 create_variable_info_for (tree decl, const char *name)
4363 unsigned int index = VEC_length (varinfo_t, varmap);
4365 tree decl_type = TREE_TYPE (decl);
4366 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
4367 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
4368 VEC (fieldoff_s,heap) *fieldstack = NULL;
4370 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4371 return create_function_info_for (decl, name);
4373 if (var_can_have_subvars (decl) && use_field_sensitive
4375 || var_ann (decl)->noalias_state == 0)
4377 || !var_ann (decl)->is_heapvar))
4378 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
4380 /* If the variable doesn't have subvars, we may end up needing to
4381 sort the field list and create fake variables for all the
4383 vi = new_var_info (decl, index, name);
4386 vi->may_have_pointers = could_have_pointers (decl);
4388 || !host_integerp (declsize, 1))
4390 vi->is_unknown_size_var = true;
4396 vi->fullsize = TREE_INT_CST_LOW (declsize);
4397 vi->size = vi->fullsize;
4400 insert_vi_for_tree (vi->decl, vi);
4401 VEC_safe_push (varinfo_t, heap, varmap, vi);
4402 if (is_global && (!flag_whole_program || !in_ipa_mode)
4403 && vi->may_have_pointers)
4406 && var_ann (decl)->noalias_state == NO_ALIAS_ANYTHING)
4407 make_constraint_from (vi, vi->id);
4409 make_constraint_from (vi, escaped_id);
4413 if (use_field_sensitive
4414 && !vi->is_unknown_size_var
4415 && var_can_have_subvars (decl)
4416 && VEC_length (fieldoff_s, fieldstack) > 1
4417 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4419 unsigned int newindex = VEC_length (varinfo_t, varmap);
4420 fieldoff_s *fo = NULL;
4421 bool notokay = false;
4424 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4426 if (fo->has_unknown_size
4434 /* We can't sort them if we have a field with a variable sized type,
4435 which will make notokay = true. In that case, we are going to return
4436 without creating varinfos for the fields anyway, so sorting them is a
4440 sort_fieldstack (fieldstack);
4441 /* Due to some C++ FE issues, like PR 22488, we might end up
4442 what appear to be overlapping fields even though they,
4443 in reality, do not overlap. Until the C++ FE is fixed,
4444 we will simply disable field-sensitivity for these cases. */
4445 notokay = check_for_overlaps (fieldstack);
4449 if (VEC_length (fieldoff_s, fieldstack) != 0)
4450 fo = VEC_index (fieldoff_s, fieldstack, 0);
4452 if (fo == NULL || notokay)
4454 vi->is_unknown_size_var = 1;
4457 vi->is_full_var = true;
4458 VEC_free (fieldoff_s, heap, fieldstack);
4462 vi->size = fo->size;
4463 vi->offset = fo->offset;
4464 vi->may_have_pointers = fo->may_have_pointers;
4465 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4466 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4470 const char *newname = "NULL";
4473 newindex = VEC_length (varinfo_t, varmap);
4476 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
4477 "+" HOST_WIDE_INT_PRINT_DEC,
4478 vi->name, fo->offset, fo->size);
4479 newname = ggc_strdup (tempname);
4482 newvi = new_var_info (decl, newindex, newname);
4483 newvi->offset = fo->offset;
4484 newvi->size = fo->size;
4485 newvi->fullsize = vi->fullsize;
4486 newvi->may_have_pointers = fo->may_have_pointers;
4487 insert_into_field_list (vi, newvi);
4488 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4489 if (is_global && (!flag_whole_program || !in_ipa_mode)
4490 && newvi->may_have_pointers)
4491 make_constraint_from (newvi, escaped_id);
4497 vi->is_full_var = true;
4499 VEC_free (fieldoff_s, heap, fieldstack);
4504 /* Print out the points-to solution for VAR to FILE. */
4507 dump_solution_for_var (FILE *file, unsigned int var)
4509 varinfo_t vi = get_varinfo (var);
4513 if (find (var) != var)
4515 varinfo_t vipt = get_varinfo (find (var));
4516 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4520 fprintf (file, "%s = { ", vi->name);
4521 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4523 fprintf (file, "%s ", get_varinfo (i)->name);
4525 fprintf (file, "}");
4526 if (vi->no_tbaa_pruning)
4527 fprintf (file, " no-tbaa-pruning");
4528 fprintf (file, "\n");
4532 /* Print the points-to solution for VAR to stdout. */
4535 debug_solution_for_var (unsigned int var)
4537 dump_solution_for_var (stdout, var);
4540 /* Create varinfo structures for all of the variables in the
4541 function for intraprocedural mode. */
4544 intra_create_variable_infos (void)
4547 struct constraint_expr lhs, rhs;
4549 /* For each incoming pointer argument arg, create the constraint ARG
4550 = NONLOCAL or a dummy variable if flag_argument_noalias is set. */
4551 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4555 if (!could_have_pointers (t))
4558 /* If flag_argument_noalias is set, then function pointer
4559 arguments are guaranteed not to point to each other. In that
4560 case, create an artificial variable PARM_NOALIAS and the
4561 constraint ARG = &PARM_NOALIAS. */
4562 if (POINTER_TYPE_P (TREE_TYPE (t)) && flag_argument_noalias > 0)
4565 tree heapvar = heapvar_lookup (t);
4569 lhs.var = get_vi_for_tree (t)->id;
4571 if (heapvar == NULL_TREE)
4574 heapvar = create_tmp_var_raw (ptr_type_node,
4576 DECL_EXTERNAL (heapvar) = 1;
4577 if (gimple_referenced_vars (cfun))
4578 add_referenced_var (heapvar);
4580 heapvar_insert (t, heapvar);
4582 ann = get_var_ann (heapvar);
4583 ann->is_heapvar = 1;
4584 if (flag_argument_noalias == 1)
4585 ann->noalias_state = NO_ALIAS;
4586 else if (flag_argument_noalias == 2)
4587 ann->noalias_state = NO_ALIAS_GLOBAL;
4588 else if (flag_argument_noalias == 3)
4589 ann->noalias_state = NO_ALIAS_ANYTHING;
4594 vi = get_vi_for_tree (heapvar);
4595 vi->is_artificial_var = 1;
4596 vi->is_heap_var = 1;
4597 vi->is_unknown_size_var = true;
4601 rhs.type = ADDRESSOF;
4603 for (p = get_varinfo (lhs.var); p; p = p->next)
4605 struct constraint_expr temp = lhs;
4607 process_constraint (new_constraint (temp, rhs));
4612 varinfo_t arg_vi = get_vi_for_tree (t);
4614 for (p = arg_vi; p; p = p->next)
4615 make_constraint_from (p, nonlocal_id);
4619 /* Add a constraint for a result decl that is passed by reference. */
4620 if (DECL_RESULT (cfun->decl)
4621 && DECL_BY_REFERENCE (DECL_RESULT (cfun->decl)))
4623 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
4625 for (p = result_vi; p; p = p->next)
4626 make_constraint_from (p, nonlocal_id);
4629 /* Add a constraint for the incoming static chain parameter. */
4630 if (cfun->static_chain_decl != NULL_TREE)
4632 varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
4634 for (p = chain_vi; p; p = p->next)
4635 make_constraint_from (p, nonlocal_id);
4639 /* Structure used to put solution bitmaps in a hashtable so they can
4640 be shared among variables with the same points-to set. */
4642 typedef struct shared_bitmap_info
4646 } *shared_bitmap_info_t;
4647 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
4649 static htab_t shared_bitmap_table;
4651 /* Hash function for a shared_bitmap_info_t */
4654 shared_bitmap_hash (const void *p)
4656 const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
4657 return bi->hashcode;
4660 /* Equality function for two shared_bitmap_info_t's. */
4663 shared_bitmap_eq (const void *p1, const void *p2)
4665 const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
4666 const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
4667 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
4670 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4671 existing instance if there is one, NULL otherwise. */
4674 shared_bitmap_lookup (bitmap pt_vars)
4677 struct shared_bitmap_info sbi;
4679 sbi.pt_vars = pt_vars;
4680 sbi.hashcode = bitmap_hash (pt_vars);
4682 slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
4683 sbi.hashcode, NO_INSERT);
4687 return ((shared_bitmap_info_t) *slot)->pt_vars;
4691 /* Add a bitmap to the shared bitmap hashtable. */
4694 shared_bitmap_add (bitmap pt_vars)
4697 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
4699 sbi->pt_vars = pt_vars;
4700 sbi->hashcode = bitmap_hash (pt_vars);
4702 slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
4703 sbi->hashcode, INSERT);
4704 gcc_assert (!*slot);
4705 *slot = (void *) sbi;
4709 /* Set bits in INTO corresponding to the variable uids in solution set
4710 FROM, which came from variable PTR.
4711 For variables that are actually dereferenced, we also use type
4712 based alias analysis to prune the points-to sets.
4713 IS_DEREFED is true if PTR was directly dereferenced, which we use to
4714 help determine whether we are we are allowed to prune using TBAA.
4715 If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of
4716 the from set. Returns the number of pruned variables. */
4719 set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed,
4720 bool no_tbaa_pruning)
4724 unsigned pruned = 0;
4726 gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
4728 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4730 varinfo_t vi = get_varinfo (i);
4732 /* The only artificial variables that are allowed in a may-alias
4733 set are heap variables. */
4734 if (vi->is_artificial_var && !vi->is_heap_var)
4737 if (TREE_CODE (vi->decl) == VAR_DECL
4738 || TREE_CODE (vi->decl) == PARM_DECL
4739 || TREE_CODE (vi->decl) == RESULT_DECL)
4741 /* Just add VI->DECL to the alias set.
4742 Don't type prune artificial vars or points-to sets
4743 for pointers that have not been dereferenced or with
4744 type-based pruning disabled. */
4745 if (vi->is_artificial_var
4748 || vi->no_tbaa_pruning)
4749 bitmap_set_bit (into, DECL_UID (vi->decl));
4752 alias_set_type var_alias_set, mem_alias_set;
4753 var_alias_set = get_alias_set (vi->decl);
4754 mem_alias_set = get_alias_set (TREE_TYPE (TREE_TYPE (ptr)));
4755 if (may_alias_p (SSA_NAME_VAR (ptr), mem_alias_set,
4756 vi->decl, var_alias_set, true))
4757 bitmap_set_bit (into, DECL_UID (vi->decl));
4768 static bool have_alias_info = false;
4770 /* Emit a note for the pointer initialization point DEF. */
4773 emit_pointer_definition (tree ptr, bitmap visited)
4775 gimple def = SSA_NAME_DEF_STMT (ptr);
4776 if (gimple_code (def) == GIMPLE_PHI)
4781 FOR_EACH_PHI_ARG (argp, def, oi, SSA_OP_USE)
4783 tree arg = USE_FROM_PTR (argp);
4784 if (TREE_CODE (arg) == SSA_NAME)
4786 if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
4787 emit_pointer_definition (arg, visited);
4790 inform (0, "initialized from %qE", arg);
4793 else if (!gimple_nop_p (def))
4794 inform (gimple_location (def), "initialized from here");
4797 /* Emit a strict aliasing warning for dereferencing the pointer PTR. */
4800 emit_alias_warning (tree ptr)
4803 imm_use_iterator ui;
4804 bool warned = false;
4806 FOR_EACH_IMM_USE_STMT (use, ui, ptr)
4808 tree deref = NULL_TREE;
4810 if (gimple_has_lhs (use))
4812 tree lhs = get_base_address (gimple_get_lhs (use));
4814 && INDIRECT_REF_P (lhs)
4815 && TREE_OPERAND (lhs, 0) == ptr)
4818 if (gimple_assign_single_p (use))
4820 tree rhs = get_base_address (gimple_assign_rhs1 (use));
4822 && INDIRECT_REF_P (rhs)
4823 && TREE_OPERAND (rhs, 0) == ptr)
4826 else if (is_gimple_call (use))
4829 for (i = 0; i < gimple_call_num_args (use); ++i)
4831 tree op = get_base_address (gimple_call_arg (use, i));
4833 && INDIRECT_REF_P (op)
4834 && TREE_OPERAND (op, 0) == ptr)
4839 && !TREE_NO_WARNING (deref))
4841 TREE_NO_WARNING (deref) = 1;
4842 warned |= warning_at (gimple_location (use), OPT_Wstrict_aliasing,
4843 "dereferencing pointer %qD does break "
4844 "strict-aliasing rules", SSA_NAME_VAR (ptr));
4849 bitmap visited = BITMAP_ALLOC (NULL);
4850 emit_pointer_definition (ptr, visited);
4851 BITMAP_FREE (visited);
4855 /* Given a pointer variable P, fill in its points-to set, or return
4857 Rather than return false for variables that point-to anything, we
4858 instead find the corresponding SMT, and merge in its aliases. In
4859 addition to these aliases, we also set the bits for the SMT's
4860 themselves and their subsets, as SMT's are still in use by
4861 non-SSA_NAME's, and pruning may eliminate every one of their
4862 aliases. In such a case, if we did not include the right set of
4863 SMT's in the points-to set of the variable, we'd end up with
4864 statements that do not conflict but should. */
4867 find_what_p_points_to (tree p)
4872 if (!have_alias_info)
4875 /* For parameters, get at the points-to set for the actual parm
4877 if (TREE_CODE (p) == SSA_NAME
4878 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4879 && SSA_NAME_IS_DEFAULT_DEF (p))
4880 lookup_p = SSA_NAME_VAR (p);
4882 vi = lookup_vi_for_tree (lookup_p);
4885 if (vi->is_artificial_var)
4888 /* See if this is a field or a structure. */
4889 if (vi->size != vi->fullsize)
4891 /* Nothing currently asks about structure fields directly,
4892 but when they do, we need code here to hand back the
4898 struct ptr_info_def *pi = get_ptr_info (p);
4899 unsigned int i, pruned;
4901 bool was_pt_anything = false;
4902 bitmap finished_solution;
4905 if (!pi->memory_tag_needed)
4908 /* This variable may have been collapsed, let's get the real
4910 vi = get_varinfo (find (vi->id));
4912 /* Translate artificial variables into SSA_NAME_PTR_INFO
4914 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4916 varinfo_t vi = get_varinfo (i);
4918 if (vi->is_artificial_var)
4920 /* FIXME. READONLY should be handled better so that
4921 flow insensitive aliasing can disregard writable
4923 if (vi->id == nothing_id)
4925 else if (vi->id == anything_id
4926 || vi->id == nonlocal_id
4927 || vi->id == escaped_id
4928 || vi->id == callused_id)
4929 was_pt_anything = 1;
4930 else if (vi->id == readonly_id)
4931 was_pt_anything = 1;
4932 else if (vi->id == integer_id)
4933 was_pt_anything = 1;
4934 else if (vi->is_heap_var)
4935 pi->pt_global_mem = 1;
4939 /* Instead of doing extra work, simply do not create
4940 points-to information for pt_anything pointers. This
4941 will cause the operand scanner to fall back to the
4942 type-based SMT and its aliases. Which is the best
4943 we could do here for the points-to set as well. */
4944 if (was_pt_anything)
4947 /* Share the final set of variables when possible. */
4948 finished_solution = BITMAP_GGC_ALLOC ();
4949 stats.points_to_sets_created++;
4951 pruned = set_uids_in_ptset (p, finished_solution, vi->solution,
4952 pi->is_dereferenced,
4953 vi->no_tbaa_pruning);
4954 result = shared_bitmap_lookup (finished_solution);
4958 shared_bitmap_add (finished_solution);
4959 pi->pt_vars = finished_solution;
4963 pi->pt_vars = result;
4964 bitmap_clear (finished_solution);
4967 if (bitmap_empty_p (pi->pt_vars))
4972 && pi->is_dereferenced
4973 && warn_strict_aliasing > 0
4974 && !SSA_NAME_IS_DEFAULT_DEF (p))
4976 if (dump_file && dump_flags & TDF_DETAILS)
4978 fprintf (dump_file, "alias warning for ");
4979 print_generic_expr (dump_file, p, 0);
4980 fprintf (dump_file, "\n");
4982 emit_alias_warning (p);
4993 /* Mark the ESCAPED solution as call clobbered. Returns false if
4994 pt_anything escaped which needs all locals that have their address
4995 taken marked call clobbered as well. */
4998 clobber_what_escaped (void)
5004 if (!have_alias_info)
5007 /* This variable may have been collapsed, let's get the real
5008 variable for escaped_id. */
5009 vi = get_varinfo (find (escaped_id));
5011 /* If call-used memory escapes we need to include it in the
5012 set of escaped variables. This can happen if a pure
5013 function returns a pointer and this pointer escapes. */
5014 if (bitmap_bit_p (vi->solution, callused_id))
5016 varinfo_t cu_vi = get_varinfo (find (callused_id));
5017 bitmap_ior_into (vi->solution, cu_vi->solution);
5020 /* Mark variables in the solution call-clobbered. */
5021 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
5023 varinfo_t vi = get_varinfo (i);
5025 if (vi->is_artificial_var)
5027 /* nothing_id and readonly_id do not cause any
5028 call clobber ops. For anything_id and integer_id
5029 we need to clobber all addressable vars. */
5030 if (vi->id == anything_id
5031 || vi->id == integer_id)
5035 /* Only artificial heap-vars are further interesting. */
5036 if (vi->is_artificial_var && !vi->is_heap_var)
5039 if ((TREE_CODE (vi->decl) == VAR_DECL
5040 || TREE_CODE (vi->decl) == PARM_DECL
5041 || TREE_CODE (vi->decl) == RESULT_DECL)
5042 && !unmodifiable_var_p (vi->decl))
5043 mark_call_clobbered (vi->decl, ESCAPE_TO_CALL);
5049 /* Compute the call-used variables. */
5052 compute_call_used_vars (void)
5057 bool has_anything_id = false;
5059 if (!have_alias_info)
5062 /* This variable may have been collapsed, let's get the real
5063 variable for escaped_id. */
5064 vi = get_varinfo (find (callused_id));
5066 /* Mark variables in the solution call-clobbered. */
5067 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
5069 varinfo_t vi = get_varinfo (i);
5071 if (vi->is_artificial_var)
5073 /* For anything_id and integer_id we need to make
5074 all local addressable vars call-used. */
5075 if (vi->id == anything_id
5076 || vi->id == integer_id)
5077 has_anything_id = true;
5080 /* Only artificial heap-vars are further interesting. */
5081 if (vi->is_artificial_var && !vi->is_heap_var)
5084 if ((TREE_CODE (vi->decl) == VAR_DECL
5085 || TREE_CODE (vi->decl) == PARM_DECL
5086 || TREE_CODE (vi->decl) == RESULT_DECL)
5087 && !unmodifiable_var_p (vi->decl))
5088 bitmap_set_bit (gimple_call_used_vars (cfun), DECL_UID (vi->decl));
5091 /* If anything is call-used, add all addressable locals to the set. */
5092 if (has_anything_id)
5093 bitmap_ior_into (gimple_call_used_vars (cfun),
5094 gimple_addressable_vars (cfun));
5098 /* Dump points-to information to OUTFILE. */
5101 dump_sa_points_to_info (FILE *outfile)
5105 fprintf (outfile, "\nPoints-to sets\n\n");
5107 if (dump_flags & TDF_STATS)
5109 fprintf (outfile, "Stats:\n");
5110 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
5111 fprintf (outfile, "Non-pointer vars: %d\n",
5112 stats.nonpointer_vars);
5113 fprintf (outfile, "Statically unified vars: %d\n",
5114 stats.unified_vars_static);
5115 fprintf (outfile, "Dynamically unified vars: %d\n",
5116 stats.unified_vars_dynamic);
5117 fprintf (outfile, "Iterations: %d\n", stats.iterations);
5118 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
5119 fprintf (outfile, "Number of implicit edges: %d\n",
5120 stats.num_implicit_edges);
5123 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
5124 dump_solution_for_var (outfile, i);
5128 /* Debug points-to information to stderr. */
5131 debug_sa_points_to_info (void)
5133 dump_sa_points_to_info (stderr);
5137 /* Initialize the always-existing constraint variables for NULL
5138 ANYTHING, READONLY, and INTEGER */
5141 init_base_vars (void)
5143 struct constraint_expr lhs, rhs;
5145 /* Create the NULL variable, used to represent that a variable points
5147 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
5148 var_nothing = new_var_info (nothing_tree, nothing_id, "NULL");
5149 insert_vi_for_tree (nothing_tree, var_nothing);
5150 var_nothing->is_artificial_var = 1;
5151 var_nothing->offset = 0;
5152 var_nothing->size = ~0;
5153 var_nothing->fullsize = ~0;
5154 var_nothing->is_special_var = 1;
5155 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
5157 /* Create the ANYTHING variable, used to represent that a variable
5158 points to some unknown piece of memory. */
5159 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
5160 var_anything = new_var_info (anything_tree, anything_id, "ANYTHING");
5161 insert_vi_for_tree (anything_tree, var_anything);
5162 var_anything->is_artificial_var = 1;
5163 var_anything->size = ~0;
5164 var_anything->offset = 0;
5165 var_anything->next = NULL;
5166 var_anything->fullsize = ~0;
5167 var_anything->is_special_var = 1;
5169 /* Anything points to anything. This makes deref constraints just
5170 work in the presence of linked list and other p = *p type loops,
5171 by saying that *ANYTHING = ANYTHING. */
5172 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
5174 lhs.var = anything_id;
5176 rhs.type = ADDRESSOF;
5177 rhs.var = anything_id;
5180 /* This specifically does not use process_constraint because
5181 process_constraint ignores all anything = anything constraints, since all
5182 but this one are redundant. */
5183 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
5185 /* Create the READONLY variable, used to represent that a variable
5186 points to readonly memory. */
5187 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
5188 var_readonly = new_var_info (readonly_tree, readonly_id, "READONLY");
5189 var_readonly->is_artificial_var = 1;
5190 var_readonly->offset = 0;
5191 var_readonly->size = ~0;
5192 var_readonly->fullsize = ~0;
5193 var_readonly->next = NULL;
5194 var_readonly->is_special_var = 1;
5195 insert_vi_for_tree (readonly_tree, var_readonly);
5196 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
5198 /* readonly memory points to anything, in order to make deref
5199 easier. In reality, it points to anything the particular
5200 readonly variable can point to, but we don't track this
5203 lhs.var = readonly_id;
5205 rhs.type = ADDRESSOF;
5206 rhs.var = readonly_id; /* FIXME */
5208 process_constraint (new_constraint (lhs, rhs));
5210 /* Create the ESCAPED variable, used to represent the set of escaped
5212 escaped_tree = create_tmp_var_raw (void_type_node, "ESCAPED");
5213 var_escaped = new_var_info (escaped_tree, escaped_id, "ESCAPED");
5214 insert_vi_for_tree (escaped_tree, var_escaped);
5215 var_escaped->is_artificial_var = 1;
5216 var_escaped->offset = 0;
5217 var_escaped->size = ~0;
5218 var_escaped->fullsize = ~0;
5219 var_escaped->is_special_var = 0;
5220 VEC_safe_push (varinfo_t, heap, varmap, var_escaped);
5221 gcc_assert (VEC_index (varinfo_t, varmap, 3) == var_escaped);
5223 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
5225 lhs.var = escaped_id;
5228 rhs.var = escaped_id;
5230 process_constraint (new_constraint (lhs, rhs));
5232 /* Create the NONLOCAL variable, used to represent the set of nonlocal
5234 nonlocal_tree = create_tmp_var_raw (void_type_node, "NONLOCAL");
5235 var_nonlocal = new_var_info (nonlocal_tree, nonlocal_id, "NONLOCAL");
5236 insert_vi_for_tree (nonlocal_tree, var_nonlocal);
5237 var_nonlocal->is_artificial_var = 1;
5238 var_nonlocal->offset = 0;
5239 var_nonlocal->size = ~0;
5240 var_nonlocal->fullsize = ~0;
5241 var_nonlocal->is_special_var = 1;
5242 VEC_safe_push (varinfo_t, heap, varmap, var_nonlocal);
5244 /* Nonlocal memory points to escaped (which includes nonlocal),
5245 in order to make deref easier. */
5247 lhs.var = nonlocal_id;
5249 rhs.type = ADDRESSOF;
5250 rhs.var = escaped_id;
5252 process_constraint (new_constraint (lhs, rhs));
5254 /* Create the CALLUSED variable, used to represent the set of call-used
5256 callused_tree = create_tmp_var_raw (void_type_node, "CALLUSED");
5257 var_callused = new_var_info (callused_tree, callused_id, "CALLUSED");
5258 insert_vi_for_tree (callused_tree, var_callused);
5259 var_callused->is_artificial_var = 1;
5260 var_callused->offset = 0;
5261 var_callused->size = ~0;
5262 var_callused->fullsize = ~0;
5263 var_callused->is_special_var = 0;
5264 VEC_safe_push (varinfo_t, heap, varmap, var_callused);
5266 /* CALLUSED = *CALLUSED, because call-used is may-deref'd at calls, etc. */
5268 lhs.var = callused_id;
5271 rhs.var = callused_id;
5273 process_constraint (new_constraint (lhs, rhs));
5275 /* Create the STOREDANYTHING variable, used to represent the set of
5276 variables stored to *ANYTHING. */
5277 storedanything_tree = create_tmp_var_raw (ptr_type_node, "STOREDANYTHING");
5278 var_storedanything = new_var_info (storedanything_tree, storedanything_id,
5280 insert_vi_for_tree (storedanything_tree, var_storedanything);
5281 var_storedanything->is_artificial_var = 1;
5282 var_storedanything->offset = 0;
5283 var_storedanything->size = ~0;
5284 var_storedanything->fullsize = ~0;
5285 var_storedanything->is_special_var = 0;
5286 VEC_safe_push (varinfo_t, heap, varmap, var_storedanything);
5288 /* Create the INTEGER variable, used to represent that a variable points
5290 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
5291 var_integer = new_var_info (integer_tree, integer_id, "INTEGER");
5292 insert_vi_for_tree (integer_tree, var_integer);
5293 var_integer->is_artificial_var = 1;
5294 var_integer->size = ~0;
5295 var_integer->fullsize = ~0;
5296 var_integer->offset = 0;
5297 var_integer->next = NULL;
5298 var_integer->is_special_var = 1;
5299 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
5301 /* INTEGER = ANYTHING, because we don't know where a dereference of
5302 a random integer will point to. */
5304 lhs.var = integer_id;
5306 rhs.type = ADDRESSOF;
5307 rhs.var = anything_id;
5309 process_constraint (new_constraint (lhs, rhs));
5311 /* *ESCAPED = &ESCAPED. This is true because we have to assume
5312 everything pointed to by escaped can also point to escaped. */
5314 lhs.var = escaped_id;
5316 rhs.type = ADDRESSOF;
5317 rhs.var = escaped_id;
5319 process_constraint (new_constraint (lhs, rhs));
5321 /* *ESCAPED = &NONLOCAL. This is true because we have to assume
5322 everything pointed to by escaped can also point to nonlocal. */
5324 lhs.var = escaped_id;
5326 rhs.type = ADDRESSOF;
5327 rhs.var = nonlocal_id;
5329 process_constraint (new_constraint (lhs, rhs));
5332 /* Initialize things necessary to perform PTA */
5335 init_alias_vars (void)
5337 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
5339 bitmap_obstack_initialize (&pta_obstack);
5340 bitmap_obstack_initialize (&oldpta_obstack);
5341 bitmap_obstack_initialize (&predbitmap_obstack);
5343 constraint_pool = create_alloc_pool ("Constraint pool",
5344 sizeof (struct constraint), 30);
5345 variable_info_pool = create_alloc_pool ("Variable info pool",
5346 sizeof (struct variable_info), 30);
5347 constraints = VEC_alloc (constraint_t, heap, 8);
5348 varmap = VEC_alloc (varinfo_t, heap, 8);
5349 vi_for_tree = pointer_map_create ();
5351 memset (&stats, 0, sizeof (stats));
5352 shared_bitmap_table = htab_create (511, shared_bitmap_hash,
5353 shared_bitmap_eq, free);
5357 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
5358 predecessor edges. */
5361 remove_preds_and_fake_succs (constraint_graph_t graph)
5365 /* Clear the implicit ref and address nodes from the successor
5367 for (i = 0; i < FIRST_REF_NODE; i++)
5369 if (graph->succs[i])
5370 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
5371 FIRST_REF_NODE * 2);
5374 /* Free the successor list for the non-ref nodes. */
5375 for (i = FIRST_REF_NODE; i < graph->size; i++)
5377 if (graph->succs[i])
5378 BITMAP_FREE (graph->succs[i]);
5381 /* Now reallocate the size of the successor list as, and blow away
5382 the predecessor bitmaps. */
5383 graph->size = VEC_length (varinfo_t, varmap);
5384 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
5386 free (graph->implicit_preds);
5387 graph->implicit_preds = NULL;
5388 free (graph->preds);
5389 graph->preds = NULL;
5390 bitmap_obstack_release (&predbitmap_obstack);
5393 /* Compute the set of variables we can't TBAA prune. */
5396 compute_tbaa_pruning (void)
5398 unsigned int size = VEC_length (varinfo_t, varmap);
5403 changed = sbitmap_alloc (size);
5404 sbitmap_zero (changed);
5406 /* Mark all initial no_tbaa_pruning nodes as changed. */
5408 for (i = 0; i < size; ++i)
5410 varinfo_t ivi = get_varinfo (i);
5412 if (find (i) == i && ivi->no_tbaa_pruning)
5415 if ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
5416 || VEC_length (constraint_t, graph->complex[i]) > 0)
5418 SET_BIT (changed, i);
5424 while (changed_count > 0)
5426 struct topo_info *ti = init_topo_info ();
5429 compute_topo_order (graph, ti);
5431 while (VEC_length (unsigned, ti->topo_order) != 0)
5435 i = VEC_pop (unsigned, ti->topo_order);
5437 /* If this variable is not a representative, skip it. */
5441 /* If the node has changed, we need to process the complex
5442 constraints and outgoing edges again. */
5443 if (TEST_BIT (changed, i))
5447 VEC(constraint_t,heap) *complex = graph->complex[i];
5449 RESET_BIT (changed, i);
5452 /* Process the complex copy constraints. */
5453 for (j = 0; VEC_iterate (constraint_t, complex, j, c); ++j)
5455 if (c->lhs.type == SCALAR && c->rhs.type == SCALAR)
5457 varinfo_t lhsvi = get_varinfo (find (c->lhs.var));
5459 if (!lhsvi->no_tbaa_pruning)
5461 lhsvi->no_tbaa_pruning = true;
5462 if (!TEST_BIT (changed, lhsvi->id))
5464 SET_BIT (changed, lhsvi->id);
5471 /* Propagate to all successors. */
5472 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
5474 unsigned int to = find (j);
5475 varinfo_t tovi = get_varinfo (to);
5477 /* Don't propagate to ourselves. */
5481 if (!tovi->no_tbaa_pruning)
5483 tovi->no_tbaa_pruning = true;
5484 if (!TEST_BIT (changed, to))
5486 SET_BIT (changed, to);
5494 free_topo_info (ti);
5497 sbitmap_free (changed);
5501 for (i = 0; i < size; ++i)
5503 varinfo_t ivi = get_varinfo (i);
5504 varinfo_t ivip = get_varinfo (find (i));
5506 if (ivip->no_tbaa_pruning)
5508 tree var = ivi->decl;
5510 if (TREE_CODE (var) == SSA_NAME)
5511 var = SSA_NAME_VAR (var);
5513 if (POINTER_TYPE_P (TREE_TYPE (var)))
5515 DECL_NO_TBAA_P (var) = 1;
5517 /* Tell the RTL layer that this pointer can alias
5519 DECL_POINTER_ALIAS_SET (var) = 0;
5526 /* Create points-to sets for the current function. See the comments
5527 at the start of the file for an algorithmic overview. */
5530 compute_points_to_sets (void)
5532 struct scc_info *si;
5535 timevar_push (TV_TREE_PTA);
5538 init_alias_heapvars ();
5540 intra_create_variable_infos ();
5542 /* Now walk all statements and derive aliases. */
5545 gimple_stmt_iterator gsi;
5547 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5549 gimple phi = gsi_stmt (gsi);
5551 if (is_gimple_reg (gimple_phi_result (phi)))
5552 find_func_aliases (phi);
5555 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5556 find_func_aliases (gsi_stmt (gsi));
5562 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5563 dump_constraints (dump_file);
5568 "\nCollapsing static cycles and doing variable "
5571 init_graph (VEC_length (varinfo_t, varmap) * 2);
5574 fprintf (dump_file, "Building predecessor graph\n");
5575 build_pred_graph ();
5578 fprintf (dump_file, "Detecting pointer and location "
5580 si = perform_var_substitution (graph);
5583 fprintf (dump_file, "Rewriting constraints and unifying "
5585 rewrite_constraints (graph, si);
5587 build_succ_graph ();
5588 free_var_substitution_info (si);
5590 if (dump_file && (dump_flags & TDF_GRAPH))
5591 dump_constraint_graph (dump_file);
5593 move_complex_constraints (graph);
5596 fprintf (dump_file, "Uniting pointer but not location equivalent "
5598 unite_pointer_equivalences (graph);
5601 fprintf (dump_file, "Finding indirect cycles\n");
5602 find_indirect_cycles (graph);
5604 /* Implicit nodes and predecessors are no longer necessary at this
5606 remove_preds_and_fake_succs (graph);
5609 fprintf (dump_file, "Solving graph\n");
5611 solve_graph (graph);
5613 compute_tbaa_pruning ();
5616 dump_sa_points_to_info (dump_file);
5618 have_alias_info = true;
5620 timevar_pop (TV_TREE_PTA);
5624 /* Delete created points-to sets. */
5627 delete_points_to_sets (void)
5631 htab_delete (shared_bitmap_table);
5632 if (dump_file && (dump_flags & TDF_STATS))
5633 fprintf (dump_file, "Points to sets created:%d\n",
5634 stats.points_to_sets_created);
5636 pointer_map_destroy (vi_for_tree);
5637 bitmap_obstack_release (&pta_obstack);
5638 VEC_free (constraint_t, heap, constraints);
5640 for (i = 0; i < graph->size; i++)
5641 VEC_free (constraint_t, heap, graph->complex[i]);
5642 free (graph->complex);
5645 free (graph->succs);
5647 free (graph->pe_rep);
5648 free (graph->indirect_cycles);
5651 VEC_free (varinfo_t, heap, varmap);
5652 free_alloc_pool (variable_info_pool);
5653 free_alloc_pool (constraint_pool);
5654 have_alias_info = false;
5657 /* Return true if we should execute IPA PTA. */
5661 return (flag_ipa_pta
5662 /* Don't bother doing anything if the program has errors. */
5663 && !(errorcount || sorrycount));
5666 /* Execute the driver for IPA PTA. */
5668 ipa_pta_execute (void)
5670 struct cgraph_node *node;
5671 struct scc_info *si;
5674 init_alias_heapvars ();
5677 for (node = cgraph_nodes; node; node = node->next)
5679 if (!node->analyzed || cgraph_is_master_clone (node))
5683 varid = create_function_info_for (node->decl,
5684 cgraph_node_name (node));
5685 if (node->local.externally_visible)
5687 varinfo_t fi = get_varinfo (varid);
5688 for (; fi; fi = fi->next)
5689 make_constraint_from (fi, anything_id);
5693 for (node = cgraph_nodes; node; node = node->next)
5695 if (node->analyzed && cgraph_is_master_clone (node))
5697 struct function *func = DECL_STRUCT_FUNCTION (node->decl);
5699 tree old_func_decl = current_function_decl;
5702 "Generating constraints for %s\n",
5703 cgraph_node_name (node));
5705 current_function_decl = node->decl;
5707 FOR_EACH_BB_FN (bb, func)
5709 gimple_stmt_iterator gsi;
5711 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
5714 gimple phi = gsi_stmt (gsi);
5716 if (is_gimple_reg (gimple_phi_result (phi)))
5717 find_func_aliases (phi);
5720 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5721 find_func_aliases (gsi_stmt (gsi));
5723 current_function_decl = old_func_decl;
5728 /* Make point to anything. */
5734 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5735 dump_constraints (dump_file);
5740 "\nCollapsing static cycles and doing variable "
5743 init_graph (VEC_length (varinfo_t, varmap) * 2);
5744 build_pred_graph ();
5745 si = perform_var_substitution (graph);
5746 rewrite_constraints (graph, si);
5748 build_succ_graph ();
5749 free_var_substitution_info (si);
5750 move_complex_constraints (graph);
5751 unite_pointer_equivalences (graph);
5752 find_indirect_cycles (graph);
5754 /* Implicit nodes and predecessors are no longer necessary at this
5756 remove_preds_and_fake_succs (graph);
5759 fprintf (dump_file, "\nSolving graph\n");
5761 solve_graph (graph);
5764 dump_sa_points_to_info (dump_file);
5767 delete_alias_heapvars ();
5768 delete_points_to_sets ();
5772 struct simple_ipa_opt_pass pass_ipa_pta =
5777 gate_ipa_pta, /* gate */
5778 ipa_pta_execute, /* execute */
5781 0, /* static_pass_number */
5782 TV_IPA_PTA, /* tv_id */
5783 0, /* properties_required */
5784 0, /* properties_provided */
5785 0, /* properties_destroyed */
5786 0, /* todo_flags_start */
5787 TODO_update_ssa /* todo_flags_finish */
5791 /* Initialize the heapvar for statement mapping. */
5793 init_alias_heapvars (void)
5795 if (!heapvar_for_stmt)
5796 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5801 delete_alias_heapvars (void)
5803 htab_delete (heapvar_for_stmt);
5804 heapvar_for_stmt = NULL;
5807 #include "gt-tree-ssa-structalias.h"