1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
35 #include "diagnostic.h"
38 #include "tree-flow.h"
39 #include "tree-inline.h"
42 #include "tree-gimple.h"
46 #include "tree-pass.h"
48 #include "alloc-pool.h"
49 #include "splay-tree.h"
51 #include "tree-ssa-structalias.h"
54 #include "pointer-set.h"
56 /* The idea behind this analyzer is to generate set constraints from the
57 program, then solve the resulting constraints in order to generate the
60 Set constraints are a way of modeling program analysis problems that
61 involve sets. They consist of an inclusion constraint language,
62 describing the variables (each variable is a set) and operations that
63 are involved on the variables, and a set of rules that derive facts
64 from these operations. To solve a system of set constraints, you derive
65 all possible facts under the rules, which gives you the correct sets
68 See "Efficient Field-sensitive pointer analysis for C" by "David
69 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
70 http://citeseer.ist.psu.edu/pearce04efficient.html
72 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
73 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
74 http://citeseer.ist.psu.edu/heintze01ultrafast.html
76 There are three types of real constraint expressions, DEREF,
77 ADDRESSOF, and SCALAR. Each constraint expression consists
78 of a constraint type, a variable, and an offset.
80 SCALAR is a constraint expression type used to represent x, whether
81 it appears on the LHS or the RHS of a statement.
82 DEREF is a constraint expression type used to represent *x, whether
83 it appears on the LHS or the RHS of a statement.
84 ADDRESSOF is a constraint expression used to represent &x, whether
85 it appears on the LHS or the RHS of a statement.
87 Each pointer variable in the program is assigned an integer id, and
88 each field of a structure variable is assigned an integer id as well.
90 Structure variables are linked to their list of fields through a "next
91 field" in each variable that points to the next field in offset
93 Each variable for a structure field has
95 1. "size", that tells the size in bits of that field.
96 2. "fullsize, that tells the size in bits of the entire structure.
97 3. "offset", that tells the offset in bits from the beginning of the
98 structure to this field.
110 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
111 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
112 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
115 In order to solve the system of set constraints, the following is
118 1. Each constraint variable x has a solution set associated with it,
121 2. Constraints are separated into direct, copy, and complex.
122 Direct constraints are ADDRESSOF constraints that require no extra
123 processing, such as P = &Q
124 Copy constraints are those of the form P = Q.
125 Complex constraints are all the constraints involving dereferences
126 and offsets (including offsetted copies).
128 3. All direct constraints of the form P = &Q are processed, such
129 that Q is added to Sol(P)
131 4. All complex constraints for a given constraint variable are stored in a
132 linked list attached to that variable's node.
134 5. A directed graph is built out of the copy constraints. Each
135 constraint variable is a node in the graph, and an edge from
136 Q to P is added for each copy constraint of the form P = Q
138 6. The graph is then walked, and solution sets are
139 propagated along the copy edges, such that an edge from Q to P
140 causes Sol(P) <- Sol(P) union Sol(Q).
142 7. As we visit each node, all complex constraints associated with
143 that node are processed by adding appropriate copy edges to the graph, or the
144 appropriate variables to the solution set.
146 8. The process of walking the graph is iterated until no solution
149 Prior to walking the graph in steps 6 and 7, We perform static
150 cycle elimination on the constraint graph, as well
151 as off-line variable substitution.
153 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
154 on and turned into anything), but isn't. You can just see what offset
155 inside the pointed-to struct it's going to access.
157 TODO: Constant bounded arrays can be handled as if they were structs of the
158 same number of elements.
160 TODO: Modeling heap and incoming pointers becomes much better if we
161 add fields to them as we discover them, which we could do.
163 TODO: We could handle unions, but to be honest, it's probably not
164 worth the pain or slowdown. */
166 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
167 htab_t heapvar_for_stmt;
169 static bool use_field_sensitive = true;
170 static int in_ipa_mode = 0;
172 /* Used for predecessor bitmaps. */
173 static bitmap_obstack predbitmap_obstack;
175 /* Used for points-to sets. */
176 static bitmap_obstack pta_obstack;
178 /* Used for oldsolution members of variables. */
179 static bitmap_obstack oldpta_obstack;
181 /* Used for per-solver-iteration bitmaps. */
182 static bitmap_obstack iteration_obstack;
184 static unsigned int create_variable_info_for (tree, const char *);
185 typedef struct constraint_graph *constraint_graph_t;
186 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
188 DEF_VEC_P(constraint_t);
189 DEF_VEC_ALLOC_P(constraint_t,heap);
191 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
193 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
195 static struct constraint_stats
197 unsigned int total_vars;
198 unsigned int nonpointer_vars;
199 unsigned int unified_vars_static;
200 unsigned int unified_vars_dynamic;
201 unsigned int iterations;
202 unsigned int num_edges;
203 unsigned int num_implicit_edges;
204 unsigned int points_to_sets_created;
209 /* ID of this variable */
212 /* 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 /* Variable id this was collapsed to due to type unsafety. Zero if
234 this variable was not collapsed. This should be unused completely
235 after build_succ_graph, or something is broken. */
236 unsigned int collapsed_to;
238 /* A link to the variable for the next field in this structure. */
239 struct variable_info *next;
241 /* Offset of this variable, in bits, from the base variable */
242 unsigned HOST_WIDE_INT offset;
244 /* Size of the variable, in bits. */
245 unsigned HOST_WIDE_INT size;
247 /* Full size of the base variable, in bits. */
248 unsigned HOST_WIDE_INT fullsize;
250 /* Name of this variable */
253 /* Tree that this variable is associated with. */
256 /* Points-to set for this variable. */
259 /* Old points-to set for this variable. */
262 typedef struct variable_info *varinfo_t;
264 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
265 static varinfo_t lookup_vi_for_tree (tree);
267 /* Pool of variable info structures. */
268 static alloc_pool variable_info_pool;
270 DEF_VEC_P(varinfo_t);
272 DEF_VEC_ALLOC_P(varinfo_t, heap);
274 /* Table of variable info structures for constraint variables.
275 Indexed directly by variable info id. */
276 static VEC(varinfo_t,heap) *varmap;
278 /* Return the varmap element N */
280 static inline varinfo_t
281 get_varinfo (unsigned int n)
283 return VEC_index (varinfo_t, varmap, n);
286 /* Return the varmap element N, following the collapsed_to link. */
288 static inline varinfo_t
289 get_varinfo_fc (unsigned int n)
291 varinfo_t v = VEC_index (varinfo_t, varmap, n);
293 if (v->collapsed_to != 0)
294 return get_varinfo (v->collapsed_to);
298 /* Static IDs for the special variables. */
299 enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
300 escaped_id = 3, nonlocal_id = 4, callused_id = 5, integer_id = 6 };
302 /* Variable that represents the unknown pointer. */
303 static varinfo_t var_anything;
304 static tree anything_tree;
306 /* Variable that represents the NULL pointer. */
307 static varinfo_t var_nothing;
308 static tree nothing_tree;
310 /* Variable that represents read only memory. */
311 static varinfo_t var_readonly;
312 static tree readonly_tree;
314 /* Variable that represents escaped memory. */
315 static varinfo_t var_escaped;
316 static tree escaped_tree;
318 /* Variable that represents nonlocal memory. */
319 static varinfo_t var_nonlocal;
320 static tree nonlocal_tree;
322 /* Variable that represents call-used memory. */
323 static varinfo_t var_callused;
324 static tree callused_tree;
326 /* Variable that represents integers. This is used for when people do things
328 static varinfo_t var_integer;
329 static tree integer_tree;
331 /* Lookup a heap var for FROM, and return it if we find one. */
334 heapvar_lookup (tree from)
336 struct tree_map *h, in;
339 h = (struct tree_map *) htab_find_with_hash (heapvar_for_stmt, &in,
340 htab_hash_pointer (from));
346 /* Insert a mapping FROM->TO in the heap var for statement
350 heapvar_insert (tree from, tree to)
355 h = GGC_NEW (struct tree_map);
356 h->hash = htab_hash_pointer (from);
359 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
360 *(struct tree_map **) loc = h;
363 /* Return a new variable info structure consisting for a variable
364 named NAME, and using constraint graph node NODE. */
367 new_var_info (tree t, unsigned int id, const char *name)
369 varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
375 ret->is_artificial_var = false;
376 ret->is_heap_var = false;
377 ret->is_special_var = false;
378 ret->is_unknown_size_var = false;
379 ret->is_full_var = false;
381 if (TREE_CODE (var) == SSA_NAME)
382 var = SSA_NAME_VAR (var);
383 ret->no_tbaa_pruning = (DECL_P (var)
384 && POINTER_TYPE_P (TREE_TYPE (var))
385 && DECL_NO_TBAA_P (var));
386 ret->solution = BITMAP_ALLOC (&pta_obstack);
387 ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
389 ret->collapsed_to = 0;
393 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
395 /* An expression that appears in a constraint. */
397 struct constraint_expr
399 /* Constraint type. */
400 constraint_expr_type type;
402 /* Variable we are referring to in the constraint. */
405 /* Offset, in bits, of this constraint from the beginning of
406 variables it ends up referring to.
408 IOW, in a deref constraint, we would deref, get the result set,
409 then add OFFSET to each member. */
410 unsigned HOST_WIDE_INT offset;
413 typedef struct constraint_expr ce_s;
415 DEF_VEC_ALLOC_O(ce_s, heap);
416 static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);
417 static void get_constraint_for (tree, VEC(ce_s, heap) **);
418 static void do_deref (VEC (ce_s, heap) **);
420 /* Our set constraints are made up of two constraint expressions, one
423 As described in the introduction, our set constraints each represent an
424 operation between set valued variables.
428 struct constraint_expr lhs;
429 struct constraint_expr rhs;
432 /* List of constraints that we use to build the constraint graph from. */
434 static VEC(constraint_t,heap) *constraints;
435 static alloc_pool constraint_pool;
439 DEF_VEC_ALLOC_I(int, heap);
441 /* The constraint graph is represented as an array of bitmaps
442 containing successor nodes. */
444 struct constraint_graph
446 /* Size of this graph, which may be different than the number of
447 nodes in the variable map. */
450 /* Explicit successors of each node. */
453 /* Implicit predecessors of each node (Used for variable
455 bitmap *implicit_preds;
457 /* Explicit predecessors of each node (Used for variable substitution). */
460 /* Indirect cycle representatives, or -1 if the node has no indirect
462 int *indirect_cycles;
464 /* Representative node for a node. rep[a] == a unless the node has
468 /* Equivalence class representative for a label. This is used for
469 variable substitution. */
472 /* Pointer equivalence label for a node. All nodes with the same
473 pointer equivalence label can be unified together at some point
474 (either during constraint optimization or after the constraint
478 /* Pointer equivalence representative for a label. This is used to
479 handle nodes that are pointer equivalent but not location
480 equivalent. We can unite these once the addressof constraints
481 are transformed into initial points-to sets. */
484 /* Pointer equivalence label for each node, used during variable
486 unsigned int *pointer_label;
488 /* Location equivalence label for each node, used during location
489 equivalence finding. */
490 unsigned int *loc_label;
492 /* Pointed-by set for each node, used during location equivalence
493 finding. This is pointed-by rather than pointed-to, because it
494 is constructed using the predecessor graph. */
497 /* Points to sets for pointer equivalence. This is *not* the actual
498 points-to sets for nodes. */
501 /* Bitmap of nodes where the bit is set if the node is a direct
502 node. Used for variable substitution. */
503 sbitmap direct_nodes;
505 /* Bitmap of nodes where the bit is set if the node is address
506 taken. Used for variable substitution. */
507 bitmap address_taken;
509 /* True if points_to bitmap for this node is stored in the hash
513 /* Number of incoming edges remaining to be processed by pointer
515 Used for variable substitution. */
516 unsigned int *number_incoming;
519 /* Vector of complex constraints for each graph node. Complex
520 constraints are those involving dereferences or offsets that are
522 VEC(constraint_t,heap) **complex;
525 static constraint_graph_t graph;
527 /* During variable substitution and the offline version of indirect
528 cycle finding, we create nodes to represent dereferences and
529 address taken constraints. These represent where these start and
531 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
532 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
534 /* Return the representative node for NODE, if NODE has been unioned
536 This function performs path compression along the way to finding
537 the representative. */
540 find (unsigned int node)
542 gcc_assert (node < graph->size);
543 if (graph->rep[node] != node)
544 return graph->rep[node] = find (graph->rep[node]);
548 /* Union the TO and FROM nodes to the TO nodes.
549 Note that at some point in the future, we may want to do
550 union-by-rank, in which case we are going to have to return the
551 node we unified to. */
554 unite (unsigned int to, unsigned int from)
556 gcc_assert (to < graph->size && from < graph->size);
557 if (to != from && graph->rep[from] != to)
559 graph->rep[from] = to;
565 /* Create a new constraint consisting of LHS and RHS expressions. */
568 new_constraint (const struct constraint_expr lhs,
569 const struct constraint_expr rhs)
571 constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
577 /* Print out constraint C to FILE. */
580 dump_constraint (FILE *file, constraint_t c)
582 if (c->lhs.type == ADDRESSOF)
584 else if (c->lhs.type == DEREF)
586 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
587 if (c->lhs.offset != 0)
588 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
589 fprintf (file, " = ");
590 if (c->rhs.type == ADDRESSOF)
592 else if (c->rhs.type == DEREF)
594 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
595 if (c->rhs.offset != 0)
596 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
597 fprintf (file, "\n");
600 /* Print out constraint C to stderr. */
603 debug_constraint (constraint_t c)
605 dump_constraint (stderr, c);
608 /* Print out all constraints to FILE */
611 dump_constraints (FILE *file)
615 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
616 dump_constraint (file, c);
619 /* Print out all constraints to stderr. */
622 debug_constraints (void)
624 dump_constraints (stderr);
627 /* Print out to FILE the edge in the constraint graph that is created by
628 constraint c. The edge may have a label, depending on the type of
629 constraint that it represents. If complex1, e.g: a = *b, then the label
630 is "=*", if complex2, e.g: *a = b, then the label is "*=", if
631 complex with an offset, e.g: a = b + 8, then the label is "+".
632 Otherwise the edge has no label. */
635 dump_constraint_edge (FILE *file, constraint_t c)
637 if (c->rhs.type != ADDRESSOF)
639 const char *src = get_varinfo_fc (c->rhs.var)->name;
640 const char *dst = get_varinfo_fc (c->lhs.var)->name;
641 fprintf (file, " \"%s\" -> \"%s\" ", src, dst);
642 /* Due to preprocessing of constraints, instructions like *a = *b are
643 illegal; thus, we do not have to handle such cases. */
644 if (c->lhs.type == DEREF)
645 fprintf (file, " [ label=\"*=\" ] ;\n");
646 else if (c->rhs.type == DEREF)
647 fprintf (file, " [ label=\"=*\" ] ;\n");
650 /* We must check the case where the constraint is an offset.
651 In this case, it is treated as a complex constraint. */
652 if (c->rhs.offset != c->lhs.offset)
653 fprintf (file, " [ label=\"+\" ] ;\n");
655 fprintf (file, " ;\n");
660 /* Print the constraint graph in dot format. */
663 dump_constraint_graph (FILE *file)
665 unsigned int i=0, size;
668 /* Only print the graph if it has already been initialized: */
672 /* Print the constraints used to produce the constraint graph. The
673 constraints will be printed as comments in the dot file: */
674 fprintf (file, "\n\n/* Constraints used in the constraint graph:\n");
675 dump_constraints (file);
676 fprintf (file, "*/\n");
678 /* Prints the header of the dot file: */
679 fprintf (file, "\n\n// The constraint graph in dot format:\n");
680 fprintf (file, "strict digraph {\n");
681 fprintf (file, " node [\n shape = box\n ]\n");
682 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
683 fprintf (file, "\n // List of nodes in the constraint graph:\n");
685 /* The next lines print the nodes in the graph. In order to get the
686 number of nodes in the graph, we must choose the minimum between the
687 vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
688 yet been initialized, then graph->size == 0, otherwise we must only
689 read nodes that have an entry in VEC (varinfo_t, varmap). */
690 size = VEC_length (varinfo_t, varmap);
691 size = size < graph->size ? size : graph->size;
692 for (i = 0; i < size; i++)
694 const char *name = get_varinfo_fc (graph->rep[i])->name;
695 fprintf (file, " \"%s\" ;\n", name);
698 /* Go over the list of constraints printing the edges in the constraint
700 fprintf (file, "\n // The constraint edges:\n");
701 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
703 dump_constraint_edge (file, c);
705 /* Prints the tail of the dot file. By now, only the closing bracket. */
706 fprintf (file, "}\n\n\n");
709 /* Print out the constraint graph to stderr. */
712 debug_constraint_graph (void)
714 dump_constraint_graph (stderr);
719 The solver is a simple worklist solver, that works on the following
722 sbitmap changed_nodes = all zeroes;
724 For each node that is not already collapsed:
726 set bit in changed nodes
728 while (changed_count > 0)
730 compute topological ordering for constraint graph
732 find and collapse cycles in the constraint graph (updating
733 changed if necessary)
735 for each node (n) in the graph in topological order:
738 Process each complex constraint associated with the node,
739 updating changed if necessary.
741 For each outgoing edge from n, propagate the solution from n to
742 the destination of the edge, updating changed as necessary.
746 /* Return true if two constraint expressions A and B are equal. */
749 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
751 return a.type == b.type && a.var == b.var && a.offset == b.offset;
754 /* Return true if constraint expression A is less than constraint expression
755 B. This is just arbitrary, but consistent, in order to give them an
759 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
761 if (a.type == b.type)
764 return a.offset < b.offset;
766 return a.var < b.var;
769 return a.type < b.type;
772 /* Return true if constraint A is less than constraint B. This is just
773 arbitrary, but consistent, in order to give them an ordering. */
776 constraint_less (const constraint_t a, const constraint_t b)
778 if (constraint_expr_less (a->lhs, b->lhs))
780 else if (constraint_expr_less (b->lhs, a->lhs))
783 return constraint_expr_less (a->rhs, b->rhs);
786 /* Return true if two constraints A and B are equal. */
789 constraint_equal (struct constraint a, struct constraint b)
791 return constraint_expr_equal (a.lhs, b.lhs)
792 && constraint_expr_equal (a.rhs, b.rhs);
796 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
799 constraint_vec_find (VEC(constraint_t,heap) *vec,
800 struct constraint lookfor)
808 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
809 if (place >= VEC_length (constraint_t, vec))
811 found = VEC_index (constraint_t, vec, place);
812 if (!constraint_equal (*found, lookfor))
817 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
820 constraint_set_union (VEC(constraint_t,heap) **to,
821 VEC(constraint_t,heap) **from)
826 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
828 if (constraint_vec_find (*to, *c) == NULL)
830 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
832 VEC_safe_insert (constraint_t, heap, *to, place, c);
837 /* Take a solution set SET, add OFFSET to each member of the set, and
838 overwrite SET with the result when done. */
841 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
843 bitmap result = BITMAP_ALLOC (&iteration_obstack);
847 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
849 varinfo_t vi = get_varinfo (i);
851 /* If this is a variable with just one field just set its bit
853 if (vi->is_artificial_var
854 || vi->is_unknown_size_var
856 bitmap_set_bit (result, i);
859 unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
860 varinfo_t v = first_vi_for_offset (vi, fieldoffset);
861 /* If the result is outside of the variable use the last field. */
865 while (v->next != NULL)
868 bitmap_set_bit (result, v->id);
869 /* If the result is not exactly at fieldoffset include the next
870 field as well. See get_constraint_for_ptr_offset for more
872 if (v->offset != fieldoffset
874 bitmap_set_bit (result, v->next->id);
878 bitmap_copy (set, result);
879 BITMAP_FREE (result);
882 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
886 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
889 return bitmap_ior_into (to, from);
895 tmp = BITMAP_ALLOC (&iteration_obstack);
896 bitmap_copy (tmp, from);
897 solution_set_add (tmp, inc);
898 res = bitmap_ior_into (to, tmp);
904 /* Insert constraint C into the list of complex constraints for graph
908 insert_into_complex (constraint_graph_t graph,
909 unsigned int var, constraint_t c)
911 VEC (constraint_t, heap) *complex = graph->complex[var];
912 unsigned int place = VEC_lower_bound (constraint_t, complex, c,
915 /* Only insert constraints that do not already exist. */
916 if (place >= VEC_length (constraint_t, complex)
917 || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
918 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
922 /* Condense two variable nodes into a single variable node, by moving
923 all associated info from SRC to TO. */
926 merge_node_constraints (constraint_graph_t graph, unsigned int to,
932 gcc_assert (find (from) == to);
934 /* Move all complex constraints from src node into to node */
935 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
937 /* In complex constraints for node src, we may have either
938 a = *src, and *src = a, or an offseted constraint which are
939 always added to the rhs node's constraints. */
941 if (c->rhs.type == DEREF)
943 else if (c->lhs.type == DEREF)
948 constraint_set_union (&graph->complex[to], &graph->complex[from]);
949 VEC_free (constraint_t, heap, graph->complex[from]);
950 graph->complex[from] = NULL;
954 /* Remove edges involving NODE from GRAPH. */
957 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
959 if (graph->succs[node])
960 BITMAP_FREE (graph->succs[node]);
963 /* Merge GRAPH nodes FROM and TO into node TO. */
966 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
969 if (graph->indirect_cycles[from] != -1)
971 /* If we have indirect cycles with the from node, and we have
972 none on the to node, the to node has indirect cycles from the
973 from node now that they are unified.
974 If indirect cycles exist on both, unify the nodes that they
975 are in a cycle with, since we know they are in a cycle with
977 if (graph->indirect_cycles[to] == -1)
978 graph->indirect_cycles[to] = graph->indirect_cycles[from];
981 /* Merge all the successor edges. */
982 if (graph->succs[from])
984 if (!graph->succs[to])
985 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
986 bitmap_ior_into (graph->succs[to],
990 clear_edges_for_node (graph, from);
994 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
995 it doesn't exist in the graph already. */
998 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1004 if (!graph->implicit_preds[to])
1005 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1007 if (bitmap_set_bit (graph->implicit_preds[to], from))
1008 stats.num_implicit_edges++;
1011 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1012 it doesn't exist in the graph already.
1013 Return false if the edge already existed, true otherwise. */
1016 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1019 if (!graph->preds[to])
1020 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1021 bitmap_set_bit (graph->preds[to], from);
1024 /* Add a graph edge to GRAPH, going from FROM to TO if
1025 it doesn't exist in the graph already.
1026 Return false if the edge already existed, true otherwise. */
1029 add_graph_edge (constraint_graph_t graph, unsigned int to,
1040 if (!graph->succs[from])
1041 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1042 if (bitmap_set_bit (graph->succs[from], to))
1045 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1053 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1056 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1059 return (graph->succs[dest]
1060 && bitmap_bit_p (graph->succs[dest], src));
1063 /* Initialize the constraint graph structure to contain SIZE nodes. */
1066 init_graph (unsigned int size)
1070 graph = XCNEW (struct constraint_graph);
1072 graph->succs = XCNEWVEC (bitmap, graph->size);
1073 graph->indirect_cycles = XNEWVEC (int, graph->size);
1074 graph->rep = XNEWVEC (unsigned int, graph->size);
1075 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
1076 graph->pe = XCNEWVEC (unsigned int, graph->size);
1077 graph->pe_rep = XNEWVEC (int, graph->size);
1079 for (j = 0; j < graph->size; j++)
1082 graph->pe_rep[j] = -1;
1083 graph->indirect_cycles[j] = -1;
1087 /* Build the constraint graph, adding only predecessor edges right now. */
1090 build_pred_graph (void)
1096 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1097 graph->preds = XCNEWVEC (bitmap, graph->size);
1098 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1099 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1100 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1101 graph->points_to = XCNEWVEC (bitmap, graph->size);
1102 graph->eq_rep = XNEWVEC (int, graph->size);
1103 graph->direct_nodes = sbitmap_alloc (graph->size);
1104 graph->pt_used = sbitmap_alloc (graph->size);
1105 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1106 graph->number_incoming = XCNEWVEC (unsigned int, graph->size);
1107 sbitmap_zero (graph->direct_nodes);
1108 sbitmap_zero (graph->pt_used);
1110 for (j = 0; j < FIRST_REF_NODE; j++)
1112 if (!get_varinfo (j)->is_special_var)
1113 SET_BIT (graph->direct_nodes, j);
1116 for (j = 0; j < graph->size; j++)
1117 graph->eq_rep[j] = -1;
1119 for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
1120 graph->indirect_cycles[j] = -1;
1122 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1124 struct constraint_expr lhs = c->lhs;
1125 struct constraint_expr rhs = c->rhs;
1126 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
1127 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
1129 if (lhs.type == DEREF)
1132 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1133 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1135 else if (rhs.type == DEREF)
1138 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1139 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1141 RESET_BIT (graph->direct_nodes, lhsvar);
1143 else if (rhs.type == ADDRESSOF)
1146 if (graph->points_to[lhsvar] == NULL)
1147 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1148 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1150 if (graph->pointed_by[rhsvar] == NULL)
1151 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1152 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1154 /* Implicitly, *x = y */
1155 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1157 RESET_BIT (graph->direct_nodes, rhsvar);
1158 bitmap_set_bit (graph->address_taken, rhsvar);
1160 else if (lhsvar > anything_id
1161 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1164 add_pred_graph_edge (graph, lhsvar, rhsvar);
1165 /* Implicitly, *x = *y */
1166 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1167 FIRST_REF_NODE + rhsvar);
1169 else if (lhs.offset != 0 || rhs.offset != 0)
1171 if (rhs.offset != 0)
1172 RESET_BIT (graph->direct_nodes, lhs.var);
1173 else if (lhs.offset != 0)
1174 RESET_BIT (graph->direct_nodes, rhs.var);
1179 /* Build the constraint graph, adding successor edges. */
1182 build_succ_graph (void)
1187 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1189 struct constraint_expr lhs;
1190 struct constraint_expr rhs;
1191 unsigned int lhsvar;
1192 unsigned int rhsvar;
1199 lhsvar = find (get_varinfo_fc (lhs.var)->id);
1200 rhsvar = find (get_varinfo_fc (rhs.var)->id);
1202 if (lhs.type == DEREF)
1204 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1205 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1207 else if (rhs.type == DEREF)
1209 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1210 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1212 else if (rhs.type == ADDRESSOF)
1215 gcc_assert (find (get_varinfo_fc (rhs.var)->id)
1216 == get_varinfo_fc (rhs.var)->id);
1217 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1219 else if (lhsvar > anything_id
1220 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1222 add_graph_edge (graph, lhsvar, rhsvar);
1228 /* Changed variables on the last iteration. */
1229 static unsigned int changed_count;
1230 static sbitmap changed;
1232 DEF_VEC_I(unsigned);
1233 DEF_VEC_ALLOC_I(unsigned,heap);
1236 /* Strongly Connected Component visitation info. */
1243 unsigned int *node_mapping;
1245 VEC(unsigned,heap) *scc_stack;
1249 /* Recursive routine to find strongly connected components in GRAPH.
1250 SI is the SCC info to store the information in, and N is the id of current
1251 graph node we are processing.
1253 This is Tarjan's strongly connected component finding algorithm, as
1254 modified by Nuutila to keep only non-root nodes on the stack.
1255 The algorithm can be found in "On finding the strongly connected
1256 connected components in a directed graph" by Esko Nuutila and Eljas
1257 Soisalon-Soininen, in Information Processing Letters volume 49,
1258 number 1, pages 9-14. */
1261 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1265 unsigned int my_dfs;
1267 SET_BIT (si->visited, n);
1268 si->dfs[n] = si->current_index ++;
1269 my_dfs = si->dfs[n];
1271 /* Visit all the successors. */
1272 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1276 if (i > LAST_REF_NODE)
1280 if (TEST_BIT (si->deleted, w))
1283 if (!TEST_BIT (si->visited, w))
1284 scc_visit (graph, si, w);
1286 unsigned int t = find (w);
1287 unsigned int nnode = find (n);
1288 gcc_assert (nnode == n);
1290 if (si->dfs[t] < si->dfs[nnode])
1291 si->dfs[n] = si->dfs[t];
1295 /* See if any components have been identified. */
1296 if (si->dfs[n] == my_dfs)
1298 if (VEC_length (unsigned, si->scc_stack) > 0
1299 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1301 bitmap scc = BITMAP_ALLOC (NULL);
1302 bool have_ref_node = n >= FIRST_REF_NODE;
1303 unsigned int lowest_node;
1306 bitmap_set_bit (scc, n);
1308 while (VEC_length (unsigned, si->scc_stack) != 0
1309 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1311 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1313 bitmap_set_bit (scc, w);
1314 if (w >= FIRST_REF_NODE)
1315 have_ref_node = true;
1318 lowest_node = bitmap_first_set_bit (scc);
1319 gcc_assert (lowest_node < FIRST_REF_NODE);
1321 /* Collapse the SCC nodes into a single node, and mark the
1323 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1325 if (i < FIRST_REF_NODE)
1327 if (unite (lowest_node, i))
1328 unify_nodes (graph, lowest_node, i, false);
1332 unite (lowest_node, i);
1333 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1337 SET_BIT (si->deleted, n);
1340 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1343 /* Unify node FROM into node TO, updating the changed count if
1344 necessary when UPDATE_CHANGED is true. */
1347 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1348 bool update_changed)
1351 gcc_assert (to != from && find (to) == to);
1352 if (dump_file && (dump_flags & TDF_DETAILS))
1353 fprintf (dump_file, "Unifying %s to %s\n",
1354 get_varinfo (from)->name,
1355 get_varinfo (to)->name);
1358 stats.unified_vars_dynamic++;
1360 stats.unified_vars_static++;
1362 merge_graph_nodes (graph, to, from);
1363 merge_node_constraints (graph, to, from);
1365 if (get_varinfo (from)->no_tbaa_pruning)
1366 get_varinfo (to)->no_tbaa_pruning = true;
1368 /* Mark TO as changed if FROM was changed. If TO was already marked
1369 as changed, decrease the changed count. */
1371 if (update_changed && TEST_BIT (changed, from))
1373 RESET_BIT (changed, from);
1374 if (!TEST_BIT (changed, to))
1375 SET_BIT (changed, to);
1378 gcc_assert (changed_count > 0);
1382 if (get_varinfo (from)->solution)
1384 /* If the solution changes because of the merging, we need to mark
1385 the variable as changed. */
1386 if (bitmap_ior_into (get_varinfo (to)->solution,
1387 get_varinfo (from)->solution))
1389 if (update_changed && !TEST_BIT (changed, to))
1391 SET_BIT (changed, to);
1396 BITMAP_FREE (get_varinfo (from)->solution);
1397 BITMAP_FREE (get_varinfo (from)->oldsolution);
1399 if (stats.iterations > 0)
1401 BITMAP_FREE (get_varinfo (to)->oldsolution);
1402 get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1405 if (valid_graph_edge (graph, to, to))
1407 if (graph->succs[to])
1408 bitmap_clear_bit (graph->succs[to], to);
1412 /* Information needed to compute the topological ordering of a graph. */
1416 /* sbitmap of visited nodes. */
1418 /* Array that stores the topological order of the graph, *in
1420 VEC(unsigned,heap) *topo_order;
1424 /* Initialize and return a topological info structure. */
1426 static struct topo_info *
1427 init_topo_info (void)
1429 size_t size = graph->size;
1430 struct topo_info *ti = XNEW (struct topo_info);
1431 ti->visited = sbitmap_alloc (size);
1432 sbitmap_zero (ti->visited);
1433 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1438 /* Free the topological sort info pointed to by TI. */
1441 free_topo_info (struct topo_info *ti)
1443 sbitmap_free (ti->visited);
1444 VEC_free (unsigned, heap, ti->topo_order);
1448 /* Visit the graph in topological order, and store the order in the
1449 topo_info structure. */
1452 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1458 SET_BIT (ti->visited, n);
1460 if (graph->succs[n])
1461 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1463 if (!TEST_BIT (ti->visited, j))
1464 topo_visit (graph, ti, j);
1467 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1470 /* Return true if variable N + OFFSET is a legal field of N. */
1473 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1475 varinfo_t ninfo = get_varinfo (n);
1477 /* For things we've globbed to single variables, any offset into the
1478 variable acts like the entire variable, so that it becomes offset
1480 if (ninfo->is_special_var
1481 || ninfo->is_artificial_var
1482 || ninfo->is_unknown_size_var
1483 || ninfo->is_full_var)
1488 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1491 /* Process a constraint C that represents x = *y, using DELTA as the
1492 starting solution. */
1495 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1498 unsigned int lhs = c->lhs.var;
1500 bitmap sol = get_varinfo (lhs)->solution;
1504 if (bitmap_bit_p (delta, anything_id))
1506 flag |= bitmap_set_bit (sol, anything_id);
1510 /* For x = *ESCAPED and x = *CALLUSED we want to compute the
1511 reachability set of the rhs var. As a pointer to a sub-field
1512 of a variable can also reach all other fields of the variable
1513 we simply have to expand the solution to contain all sub-fields
1514 if one sub-field is contained. */
1515 if (c->rhs.var == escaped_id
1516 || c->rhs.var == callused_id)
1519 /* In a first pass record all variables we need to add all
1520 sub-fields off. This avoids quadratic behavior. */
1521 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1523 varinfo_t v = get_varinfo (j);
1527 v = lookup_vi_for_tree (v->decl);
1528 if (v->next != NULL)
1531 vars = BITMAP_ALLOC (NULL);
1532 bitmap_set_bit (vars, v->id);
1535 /* In the second pass now do the addition to the solution and
1536 to speed up solving add it to the delta as well. */
1539 EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
1541 varinfo_t v = get_varinfo (j);
1542 for (; v != NULL; v = v->next)
1544 if (bitmap_set_bit (sol, v->id))
1547 bitmap_set_bit (delta, v->id);
1555 /* For each variable j in delta (Sol(y)), add
1556 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1557 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1559 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1560 if (type_safe (j, &roffset))
1563 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1566 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1567 /* If the access is outside of the variable we can ignore it. */
1572 /* Adding edges from the special vars is pointless.
1573 They don't have sets that can change. */
1574 if (get_varinfo (t)->is_special_var)
1575 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1576 /* Merging the solution from ESCAPED needlessly increases
1577 the set. Use ESCAPED as representative instead.
1578 Same for CALLUSED. */
1579 else if (get_varinfo (t)->id == escaped_id
1580 || get_varinfo (t)->id == callused_id)
1581 flag |= bitmap_set_bit (sol, get_varinfo (t)->id);
1582 else if (add_graph_edge (graph, lhs, t))
1583 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1588 /* If the LHS solution changed, mark the var as changed. */
1591 get_varinfo (lhs)->solution = sol;
1592 if (!TEST_BIT (changed, lhs))
1594 SET_BIT (changed, lhs);
1600 /* Process a constraint C that represents *x = y. */
1603 do_ds_constraint (constraint_t c, bitmap delta)
1605 unsigned int rhs = c->rhs.var;
1606 bitmap sol = get_varinfo (rhs)->solution;
1610 if (bitmap_bit_p (sol, anything_id))
1612 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1614 varinfo_t jvi = get_varinfo (j);
1616 unsigned int loff = c->lhs.offset;
1617 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
1620 v = get_varinfo (j);
1621 if (!v->is_full_var)
1623 v = first_vi_for_offset (v, fieldoffset);
1624 /* If the access is outside of the variable we can ignore it. */
1630 if (bitmap_set_bit (get_varinfo (t)->solution, anything_id)
1631 && !TEST_BIT (changed, t))
1633 SET_BIT (changed, t);
1640 /* For each member j of delta (Sol(x)), add an edge from y to j and
1641 union Sol(y) into Sol(j) */
1642 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1644 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1645 if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
1649 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1652 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1653 /* If the access is outside of the variable we can ignore it. */
1657 tmp = get_varinfo (t)->solution;
1659 if (set_union_with_increment (tmp, sol, 0))
1661 get_varinfo (t)->solution = tmp;
1663 sol = get_varinfo (rhs)->solution;
1664 if (!TEST_BIT (changed, t))
1666 SET_BIT (changed, t);
1674 /* Handle a non-simple (simple meaning requires no iteration),
1675 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1678 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1680 if (c->lhs.type == DEREF)
1682 if (c->rhs.type == ADDRESSOF)
1689 do_ds_constraint (c, delta);
1692 else if (c->rhs.type == DEREF)
1695 if (!(get_varinfo (c->lhs.var)->is_special_var))
1696 do_sd_constraint (graph, c, delta);
1704 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1705 solution = get_varinfo (c->rhs.var)->solution;
1706 tmp = get_varinfo (c->lhs.var)->solution;
1708 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1712 get_varinfo (c->lhs.var)->solution = tmp;
1713 if (!TEST_BIT (changed, c->lhs.var))
1715 SET_BIT (changed, c->lhs.var);
1722 /* Initialize and return a new SCC info structure. */
1724 static struct scc_info *
1725 init_scc_info (size_t size)
1727 struct scc_info *si = XNEW (struct scc_info);
1730 si->current_index = 0;
1731 si->visited = sbitmap_alloc (size);
1732 sbitmap_zero (si->visited);
1733 si->deleted = sbitmap_alloc (size);
1734 sbitmap_zero (si->deleted);
1735 si->node_mapping = XNEWVEC (unsigned int, size);
1736 si->dfs = XCNEWVEC (unsigned int, size);
1738 for (i = 0; i < size; i++)
1739 si->node_mapping[i] = i;
1741 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1745 /* Free an SCC info structure pointed to by SI */
1748 free_scc_info (struct scc_info *si)
1750 sbitmap_free (si->visited);
1751 sbitmap_free (si->deleted);
1752 free (si->node_mapping);
1754 VEC_free (unsigned, heap, si->scc_stack);
1759 /* Find indirect cycles in GRAPH that occur, using strongly connected
1760 components, and note them in the indirect cycles map.
1762 This technique comes from Ben Hardekopf and Calvin Lin,
1763 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1764 Lines of Code", submitted to PLDI 2007. */
1767 find_indirect_cycles (constraint_graph_t graph)
1770 unsigned int size = graph->size;
1771 struct scc_info *si = init_scc_info (size);
1773 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1774 if (!TEST_BIT (si->visited, i) && find (i) == i)
1775 scc_visit (graph, si, i);
1780 /* Compute a topological ordering for GRAPH, and store the result in the
1781 topo_info structure TI. */
1784 compute_topo_order (constraint_graph_t graph,
1785 struct topo_info *ti)
1788 unsigned int size = graph->size;
1790 for (i = 0; i != size; ++i)
1791 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1792 topo_visit (graph, ti, i);
1795 /* Structure used to for hash value numbering of pointer equivalence
1798 typedef struct equiv_class_label
1800 unsigned int equivalence_class;
1803 } *equiv_class_label_t;
1804 typedef const struct equiv_class_label *const_equiv_class_label_t;
1806 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1808 static htab_t pointer_equiv_class_table;
1810 /* A hashtable for mapping a bitmap of labels->location equivalence
1812 static htab_t location_equiv_class_table;
1814 /* Hash function for a equiv_class_label_t */
1817 equiv_class_label_hash (const void *p)
1819 const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
1820 return ecl->hashcode;
1823 /* Equality function for two equiv_class_label_t's. */
1826 equiv_class_label_eq (const void *p1, const void *p2)
1828 const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
1829 const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
1830 return bitmap_equal_p (eql1->labels, eql2->labels);
1833 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
1837 equiv_class_lookup (htab_t table, bitmap labels)
1840 struct equiv_class_label ecl;
1842 ecl.labels = labels;
1843 ecl.hashcode = bitmap_hash (labels);
1845 slot = htab_find_slot_with_hash (table, &ecl,
1846 ecl.hashcode, NO_INSERT);
1850 return ((equiv_class_label_t) *slot)->equivalence_class;
1854 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
1858 equiv_class_add (htab_t table, unsigned int equivalence_class,
1862 equiv_class_label_t ecl = XNEW (struct equiv_class_label);
1864 ecl->labels = labels;
1865 ecl->equivalence_class = equivalence_class;
1866 ecl->hashcode = bitmap_hash (labels);
1868 slot = htab_find_slot_with_hash (table, ecl,
1869 ecl->hashcode, INSERT);
1870 gcc_assert (!*slot);
1871 *slot = (void *) ecl;
1874 /* Perform offline variable substitution.
1876 This is a worst case quadratic time way of identifying variables
1877 that must have equivalent points-to sets, including those caused by
1878 static cycles, and single entry subgraphs, in the constraint graph.
1880 The technique is described in "Exploiting Pointer and Location
1881 Equivalence to Optimize Pointer Analysis. In the 14th International
1882 Static Analysis Symposium (SAS), August 2007." It is known as the
1883 "HU" algorithm, and is equivalent to value numbering the collapsed
1884 constraint graph including evaluating unions.
1886 The general method of finding equivalence classes is as follows:
1887 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1888 Initialize all non-REF nodes to be direct nodes.
1889 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1891 For each constraint containing the dereference, we also do the same
1894 We then compute SCC's in the graph and unify nodes in the same SCC,
1897 For each non-collapsed node x:
1898 Visit all unvisited explicit incoming edges.
1899 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1901 Lookup the equivalence class for pts(x).
1902 If we found one, equivalence_class(x) = found class.
1903 Otherwise, equivalence_class(x) = new class, and new_class is
1904 added to the lookup table.
1906 All direct nodes with the same equivalence class can be replaced
1907 with a single representative node.
1908 All unlabeled nodes (label == 0) are not pointers and all edges
1909 involving them can be eliminated.
1910 We perform these optimizations during rewrite_constraints
1912 In addition to pointer equivalence class finding, we also perform
1913 location equivalence class finding. This is the set of variables
1914 that always appear together in points-to sets. We use this to
1915 compress the size of the points-to sets. */
1917 /* Current maximum pointer equivalence class id. */
1918 static int pointer_equiv_class;
1920 /* Current maximum location equivalence class id. */
1921 static int location_equiv_class;
1923 /* Recursive routine to find strongly connected components in GRAPH,
1924 and label it's nodes with DFS numbers. */
1927 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1931 unsigned int my_dfs;
1933 gcc_assert (si->node_mapping[n] == n);
1934 SET_BIT (si->visited, n);
1935 si->dfs[n] = si->current_index ++;
1936 my_dfs = si->dfs[n];
1938 /* Visit all the successors. */
1939 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1941 unsigned int w = si->node_mapping[i];
1943 if (TEST_BIT (si->deleted, w))
1946 if (!TEST_BIT (si->visited, w))
1947 condense_visit (graph, si, w);
1949 unsigned int t = si->node_mapping[w];
1950 unsigned int nnode = si->node_mapping[n];
1951 gcc_assert (nnode == n);
1953 if (si->dfs[t] < si->dfs[nnode])
1954 si->dfs[n] = si->dfs[t];
1958 /* Visit all the implicit predecessors. */
1959 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1961 unsigned int w = si->node_mapping[i];
1963 if (TEST_BIT (si->deleted, w))
1966 if (!TEST_BIT (si->visited, w))
1967 condense_visit (graph, si, w);
1969 unsigned int t = si->node_mapping[w];
1970 unsigned int nnode = si->node_mapping[n];
1971 gcc_assert (nnode == n);
1973 if (si->dfs[t] < si->dfs[nnode])
1974 si->dfs[n] = si->dfs[t];
1978 /* See if any components have been identified. */
1979 if (si->dfs[n] == my_dfs)
1981 while (VEC_length (unsigned, si->scc_stack) != 0
1982 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1984 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1985 si->node_mapping[w] = n;
1987 if (!TEST_BIT (graph->direct_nodes, w))
1988 RESET_BIT (graph->direct_nodes, n);
1990 /* Unify our nodes. */
1991 if (graph->preds[w])
1993 if (!graph->preds[n])
1994 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
1995 bitmap_ior_into (graph->preds[n], graph->preds[w]);
1997 if (graph->implicit_preds[w])
1999 if (!graph->implicit_preds[n])
2000 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2001 bitmap_ior_into (graph->implicit_preds[n],
2002 graph->implicit_preds[w]);
2004 if (graph->points_to[w])
2006 if (!graph->points_to[n])
2007 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2008 bitmap_ior_into (graph->points_to[n],
2009 graph->points_to[w]);
2011 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2013 unsigned int rep = si->node_mapping[i];
2014 graph->number_incoming[rep]++;
2017 SET_BIT (si->deleted, n);
2020 VEC_safe_push (unsigned, heap, si->scc_stack, n);
2023 /* Label pointer equivalences. */
2026 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2030 SET_BIT (si->visited, n);
2032 if (!graph->points_to[n])
2033 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2035 /* Label and union our incoming edges's points to sets. */
2036 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2038 unsigned int w = si->node_mapping[i];
2039 if (!TEST_BIT (si->visited, w))
2040 label_visit (graph, si, w);
2042 /* Skip unused edges */
2043 if (w == n || graph->pointer_label[w] == 0)
2045 graph->number_incoming[w]--;
2048 if (graph->points_to[w])
2049 bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
2051 /* If all incoming edges to w have been processed and
2052 graph->points_to[w] was not stored in the hash table, we can
2054 graph->number_incoming[w]--;
2055 if (!graph->number_incoming[w] && !TEST_BIT (graph->pt_used, w))
2057 BITMAP_FREE (graph->points_to[w]);
2060 /* Indirect nodes get fresh variables. */
2061 if (!TEST_BIT (graph->direct_nodes, n))
2062 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2064 if (!bitmap_empty_p (graph->points_to[n]))
2066 unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
2067 graph->points_to[n]);
2070 SET_BIT (graph->pt_used, n);
2071 label = pointer_equiv_class++;
2072 equiv_class_add (pointer_equiv_class_table,
2073 label, graph->points_to[n]);
2075 graph->pointer_label[n] = label;
2079 /* Perform offline variable substitution, discovering equivalence
2080 classes, and eliminating non-pointer variables. */
2082 static struct scc_info *
2083 perform_var_substitution (constraint_graph_t graph)
2086 unsigned int size = graph->size;
2087 struct scc_info *si = init_scc_info (size);
2089 bitmap_obstack_initialize (&iteration_obstack);
2090 pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
2091 equiv_class_label_eq, free);
2092 location_equiv_class_table = htab_create (511, equiv_class_label_hash,
2093 equiv_class_label_eq, free);
2094 pointer_equiv_class = 1;
2095 location_equiv_class = 1;
2097 /* Condense the nodes, which means to find SCC's, count incoming
2098 predecessors, and unite nodes in SCC's. */
2099 for (i = 0; i < FIRST_REF_NODE; i++)
2100 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2101 condense_visit (graph, si, si->node_mapping[i]);
2103 sbitmap_zero (si->visited);
2104 /* Actually the label the nodes for pointer equivalences */
2105 for (i = 0; i < FIRST_REF_NODE; i++)
2106 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2107 label_visit (graph, si, si->node_mapping[i]);
2109 /* Calculate location equivalence labels. */
2110 for (i = 0; i < FIRST_REF_NODE; i++)
2117 if (!graph->pointed_by[i])
2119 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2121 /* Translate the pointed-by mapping for pointer equivalence
2123 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2125 bitmap_set_bit (pointed_by,
2126 graph->pointer_label[si->node_mapping[j]]);
2128 /* The original pointed_by is now dead. */
2129 BITMAP_FREE (graph->pointed_by[i]);
2131 /* Look up the location equivalence label if one exists, or make
2133 label = equiv_class_lookup (location_equiv_class_table,
2137 label = location_equiv_class++;
2138 equiv_class_add (location_equiv_class_table,
2143 if (dump_file && (dump_flags & TDF_DETAILS))
2144 fprintf (dump_file, "Found location equivalence for node %s\n",
2145 get_varinfo (i)->name);
2146 BITMAP_FREE (pointed_by);
2148 graph->loc_label[i] = label;
2152 if (dump_file && (dump_flags & TDF_DETAILS))
2153 for (i = 0; i < FIRST_REF_NODE; i++)
2155 bool direct_node = TEST_BIT (graph->direct_nodes, i);
2157 "Equivalence classes for %s node id %d:%s are pointer: %d"
2159 direct_node ? "Direct node" : "Indirect node", i,
2160 get_varinfo (i)->name,
2161 graph->pointer_label[si->node_mapping[i]],
2162 graph->loc_label[si->node_mapping[i]]);
2165 /* Quickly eliminate our non-pointer variables. */
2167 for (i = 0; i < FIRST_REF_NODE; i++)
2169 unsigned int node = si->node_mapping[i];
2171 if (graph->pointer_label[node] == 0)
2173 if (dump_file && (dump_flags & TDF_DETAILS))
2175 "%s is a non-pointer variable, eliminating edges.\n",
2176 get_varinfo (node)->name);
2177 stats.nonpointer_vars++;
2178 clear_edges_for_node (graph, node);
2185 /* Free information that was only necessary for variable
2189 free_var_substitution_info (struct scc_info *si)
2192 free (graph->pointer_label);
2193 free (graph->loc_label);
2194 free (graph->pointed_by);
2195 free (graph->points_to);
2196 free (graph->number_incoming);
2197 free (graph->eq_rep);
2198 sbitmap_free (graph->direct_nodes);
2199 sbitmap_free (graph->pt_used);
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 variable of a type that could contain
2763 could_have_pointers (tree t)
2765 tree type = TREE_TYPE (t);
2767 if (POINTER_TYPE_P (type)
2768 || AGGREGATE_TYPE_P (type)
2769 || TREE_CODE (type) == COMPLEX_TYPE)
2775 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2778 static HOST_WIDE_INT
2779 bitpos_of_field (const tree fdecl)
2782 if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2783 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2786 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2787 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2791 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2792 resulting constraint expressions in *RESULTS. */
2795 get_constraint_for_ptr_offset (tree ptr, tree offset,
2796 VEC (ce_s, heap) **results)
2798 struct constraint_expr *c;
2800 unsigned HOST_WIDE_INT rhsunitoffset, rhsoffset;
2802 /* If we do not do field-sensitive PTA adding offsets to pointers
2803 does not change the points-to solution. */
2804 if (!use_field_sensitive)
2806 get_constraint_for (ptr, results);
2810 /* If the offset is not a non-negative integer constant that fits
2811 in a HOST_WIDE_INT, we have to fall back to a conservative
2812 solution which includes all sub-fields of all pointed-to
2814 ??? As we do not have the ability to express this, fall back
2816 if (!host_integerp (offset, 1))
2818 struct constraint_expr temp;
2819 temp.var = anything_id;
2822 VEC_safe_push (ce_s, heap, *results, &temp);
2826 /* Make sure the bit-offset also fits. */
2827 rhsunitoffset = TREE_INT_CST_LOW (offset);
2828 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
2829 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
2831 struct constraint_expr temp;
2832 temp.var = anything_id;
2835 VEC_safe_push (ce_s, heap, *results, &temp);
2839 get_constraint_for (ptr, results);
2843 /* As we are eventually appending to the solution do not use
2844 VEC_iterate here. */
2845 n = VEC_length (ce_s, *results);
2846 for (j = 0; j < n; j++)
2849 c = VEC_index (ce_s, *results, j);
2850 curr = get_varinfo (c->var);
2852 if (c->type == ADDRESSOF
2853 && !curr->is_full_var)
2855 varinfo_t temp, curr = get_varinfo (c->var);
2857 /* Search the sub-field which overlaps with the
2858 pointed-to offset. As we deal with positive offsets
2859 only, we can start the search from the current variable. */
2860 temp = first_vi_for_offset (curr, curr->offset + rhsoffset);
2862 /* If the result is outside of the variable we have to provide
2863 a conservative result, as the variable is still reachable
2864 from the resulting pointer (even though it technically
2865 cannot point to anything). The last sub-field is such
2866 a conservative result.
2867 ??? If we always had a sub-field for &object + 1 then
2868 we could represent this in a more precise way. */
2872 while (temp->next != NULL)
2877 /* If the found variable is not exactly at the pointed to
2878 result, we have to include the next variable in the
2879 solution as well. Otherwise two increments by offset / 2
2880 do not result in the same or a conservative superset
2882 if (temp->offset != curr->offset + rhsoffset
2883 && temp->next != NULL)
2885 struct constraint_expr c2;
2886 c2.var = temp->next->id;
2887 c2.type = ADDRESSOF;
2889 VEC_safe_push (ce_s, heap, *results, &c2);
2894 else if (c->type == ADDRESSOF
2895 /* If this varinfo represents a full variable just use it. */
2896 && curr->is_full_var)
2899 c->offset = rhsoffset;
2904 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
2905 If address_p is true the result will be taken its address of. */
2908 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
2912 HOST_WIDE_INT bitsize = -1;
2913 HOST_WIDE_INT bitmaxsize = -1;
2914 HOST_WIDE_INT bitpos;
2916 struct constraint_expr *result;
2918 /* Some people like to do cute things like take the address of
2921 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2922 forzero = TREE_OPERAND (forzero, 0);
2924 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2926 struct constraint_expr temp;
2929 temp.var = integer_id;
2931 VEC_safe_push (ce_s, heap, *results, &temp);
2935 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2937 /* Pretend to take the address of the base, we'll take care of
2938 adding the required subset of sub-fields below. */
2939 get_constraint_for_1 (t, results, true);
2940 gcc_assert (VEC_length (ce_s, *results) == 1);
2941 result = VEC_last (ce_s, *results);
2943 /* This can also happen due to weird offsetof type macros. */
2944 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2945 result->type = SCALAR;
2947 if (result->type == SCALAR
2948 && get_varinfo (result->var)->is_full_var)
2949 /* For single-field vars do not bother about the offset. */
2951 else if (result->type == SCALAR)
2953 /* In languages like C, you can access one past the end of an
2954 array. You aren't allowed to dereference it, so we can
2955 ignore this constraint. When we handle pointer subtraction,
2956 we may have to do something cute here. */
2958 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
2961 /* It's also not true that the constraint will actually start at the
2962 right offset, it may start in some padding. We only care about
2963 setting the constraint to the first actual field it touches, so
2965 struct constraint_expr cexpr = *result;
2967 VEC_pop (ce_s, *results);
2969 for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
2971 if (ranges_overlap_p (curr->offset, curr->size,
2972 bitpos, bitmaxsize))
2974 cexpr.var = curr->id;
2975 VEC_safe_push (ce_s, heap, *results, &cexpr);
2980 /* If we are going to take the address of this field then
2981 to be able to compute reachability correctly add at least
2982 the last field of the variable. */
2984 && VEC_length (ce_s, *results) == 0)
2986 curr = get_varinfo (cexpr.var);
2987 while (curr->next != NULL)
2989 cexpr.var = curr->id;
2990 VEC_safe_push (ce_s, heap, *results, &cexpr);
2993 /* Assert that we found *some* field there. The user couldn't be
2994 accessing *only* padding. */
2995 /* Still the user could access one past the end of an array
2996 embedded in a struct resulting in accessing *only* padding. */
2997 gcc_assert (VEC_length (ce_s, *results) >= 1
2998 || ref_contains_array_ref (orig_t));
3000 else if (bitmaxsize == 0)
3002 if (dump_file && (dump_flags & TDF_DETAILS))
3003 fprintf (dump_file, "Access to zero-sized part of variable,"
3007 if (dump_file && (dump_flags & TDF_DETAILS))
3008 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3010 else if (bitmaxsize == -1)
3012 /* We can't handle DEREF constraints with unknown size, we'll
3013 get the wrong answer. Punt and return anything. */
3014 result->var = anything_id;
3018 result->offset = bitpos;
3022 /* Dereference the constraint expression CONS, and return the result.
3023 DEREF (ADDRESSOF) = SCALAR
3024 DEREF (SCALAR) = DEREF
3025 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3026 This is needed so that we can handle dereferencing DEREF constraints. */
3029 do_deref (VEC (ce_s, heap) **constraints)
3031 struct constraint_expr *c;
3034 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3036 if (c->type == SCALAR)
3038 else if (c->type == ADDRESSOF)
3040 else if (c->type == DEREF)
3042 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
3043 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
3044 process_constraint (new_constraint (tmplhs, *c));
3045 c->var = tmplhs.var;
3052 /* Given a tree T, return the constraint expression for it. */
3055 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3057 struct constraint_expr temp;
3059 /* x = integer is all glommed to a single variable, which doesn't
3060 point to anything by itself. That is, of course, unless it is an
3061 integer constant being treated as a pointer, in which case, we
3062 will return that this is really the addressof anything. This
3063 happens below, since it will fall into the default case. The only
3064 case we know something about an integer treated like a pointer is
3065 when it is the NULL pointer, and then we just say it points to
3067 if (TREE_CODE (t) == INTEGER_CST
3068 && integer_zerop (t))
3070 temp.var = nothing_id;
3071 temp.type = ADDRESSOF;
3073 VEC_safe_push (ce_s, heap, *results, &temp);
3077 /* String constants are read-only. */
3078 if (TREE_CODE (t) == STRING_CST)
3080 temp.var = readonly_id;
3083 VEC_safe_push (ce_s, heap, *results, &temp);
3087 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3089 case tcc_expression:
3092 switch (TREE_CODE (t))
3096 struct constraint_expr *c;
3098 tree exp = TREE_OPERAND (t, 0);
3100 get_constraint_for_1 (exp, results, true);
3102 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3104 if (c->type == DEREF)
3107 c->type = ADDRESSOF;
3113 /* XXX: In interprocedural mode, if we didn't have the
3114 body, we would need to do *each pointer argument =
3116 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
3119 tree heapvar = heapvar_lookup (t);
3121 if (heapvar == NULL)
3123 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
3124 DECL_EXTERNAL (heapvar) = 1;
3125 get_var_ann (heapvar)->is_heapvar = 1;
3126 if (gimple_referenced_vars (cfun))
3127 add_referenced_var (heapvar);
3128 heapvar_insert (t, heapvar);
3131 temp.var = create_variable_info_for (heapvar,
3132 alias_get_name (heapvar));
3134 vi = get_varinfo (temp.var);
3135 vi->is_artificial_var = 1;
3136 vi->is_heap_var = 1;
3137 temp.type = ADDRESSOF;
3139 VEC_safe_push (ce_s, heap, *results, &temp);
3149 switch (TREE_CODE (t))
3153 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3158 case ARRAY_RANGE_REF:
3160 get_constraint_for_component_ref (t, results, address_p);
3168 switch (TREE_CODE (t))
3172 tree op = TREE_OPERAND (t, 0);
3174 /* Cast from non-pointer to pointers are bad news for us.
3175 Anything else, we see through */
3176 if (!(POINTER_TYPE_P (TREE_TYPE (t))
3177 && ! POINTER_TYPE_P (TREE_TYPE (op))))
3179 get_constraint_for_1 (op, results, address_p);
3191 if (TREE_CODE (t) == POINTER_PLUS_EXPR)
3193 get_constraint_for_ptr_offset (TREE_OPERAND (t, 0),
3194 TREE_OPERAND (t, 1), results);
3199 case tcc_exceptional:
3201 switch (TREE_CODE (t))
3205 get_constraint_for_1 (PHI_RESULT (t), results, address_p);
3210 get_constraint_for_ssa_var (t, results, address_p);
3217 case tcc_declaration:
3219 get_constraint_for_ssa_var (t, results, address_p);
3225 /* The default fallback is a constraint from anything. */
3226 temp.type = ADDRESSOF;
3227 temp.var = anything_id;
3229 VEC_safe_push (ce_s, heap, *results, &temp);
3232 /* Given a gimple tree T, return the constraint expression vector for it. */
3235 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3237 gcc_assert (VEC_length (ce_s, *results) == 0);
3239 get_constraint_for_1 (t, results, false);
3242 /* Handle the structure copy case where we have a simple structure copy
3243 between LHS and RHS that is of SIZE (in bits)
3245 For each field of the lhs variable (lhsfield)
3246 For each field of the rhs variable at lhsfield.offset (rhsfield)
3247 add the constraint lhsfield = rhsfield
3249 If we fail due to some kind of type unsafety or other thing we
3250 can't handle, return false. We expect the caller to collapse the
3251 variable in that case. */
3254 do_simple_structure_copy (const struct constraint_expr lhs,
3255 const struct constraint_expr rhs,
3256 const unsigned HOST_WIDE_INT size)
3258 varinfo_t p = get_varinfo (lhs.var);
3259 unsigned HOST_WIDE_INT pstart, last;
3261 last = p->offset + size;
3262 for (; p && p->offset < last; p = p->next)
3265 struct constraint_expr templhs = lhs;
3266 struct constraint_expr temprhs = rhs;
3267 unsigned HOST_WIDE_INT fieldoffset;
3269 templhs.var = p->id;
3270 q = get_varinfo (temprhs.var);
3271 fieldoffset = p->offset - pstart;
3272 q = first_vi_for_offset (q, q->offset + fieldoffset);
3275 temprhs.var = q->id;
3276 process_constraint (new_constraint (templhs, temprhs));
3282 /* Handle the structure copy case where we have a structure copy between a
3283 aggregate on the LHS and a dereference of a pointer on the RHS
3284 that is of SIZE (in bits)
3286 For each field of the lhs variable (lhsfield)
3287 rhs.offset = lhsfield->offset
3288 add the constraint lhsfield = rhs
3292 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
3293 const struct constraint_expr rhs,
3294 const unsigned HOST_WIDE_INT size)
3296 varinfo_t p = get_varinfo (lhs.var);
3297 unsigned HOST_WIDE_INT pstart,last;
3299 last = p->offset + size;
3301 for (; p && p->offset < last; p = p->next)
3304 struct constraint_expr templhs = lhs;
3305 struct constraint_expr temprhs = rhs;
3306 unsigned HOST_WIDE_INT fieldoffset;
3309 if (templhs.type == SCALAR)
3310 templhs.var = p->id;
3312 templhs.offset = p->offset;
3314 q = get_varinfo (temprhs.var);
3315 fieldoffset = p->offset - pstart;
3316 temprhs.offset += fieldoffset;
3317 process_constraint (new_constraint (templhs, temprhs));
3321 /* Handle the structure copy case where we have a structure copy
3322 between an aggregate on the RHS and a dereference of a pointer on
3323 the LHS that is of SIZE (in bits)
3325 For each field of the rhs variable (rhsfield)
3326 lhs.offset = rhsfield->offset
3327 add the constraint lhs = rhsfield
3331 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
3332 const struct constraint_expr rhs,
3333 const unsigned HOST_WIDE_INT size)
3335 varinfo_t p = get_varinfo (rhs.var);
3336 unsigned HOST_WIDE_INT pstart,last;
3338 last = p->offset + size;
3340 for (; p && p->offset < last; p = p->next)
3343 struct constraint_expr templhs = lhs;
3344 struct constraint_expr temprhs = rhs;
3345 unsigned HOST_WIDE_INT fieldoffset;
3348 if (temprhs.type == SCALAR)
3349 temprhs.var = p->id;
3351 temprhs.offset = p->offset;
3353 q = get_varinfo (templhs.var);
3354 fieldoffset = p->offset - pstart;
3355 templhs.offset += fieldoffset;
3356 process_constraint (new_constraint (templhs, temprhs));
3360 /* Sometimes, frontends like to give us bad type information. This
3361 function will collapse all the fields from VAR to the end of VAR,
3362 into VAR, so that we treat those fields as a single variable.
3363 We return the variable they were collapsed into. */
3366 collapse_rest_of_var (unsigned int var)
3368 varinfo_t currvar = get_varinfo (var);
3371 for (field = currvar->next; field; field = field->next)
3374 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
3375 field->name, currvar->name);
3377 gcc_assert (field->collapsed_to == 0);
3378 field->collapsed_to = currvar->id;
3381 currvar->next = NULL;
3382 currvar->size = currvar->fullsize - currvar->offset;
3387 /* Handle aggregate copies by expanding into copies of the respective
3388 fields of the structures. */
3391 do_structure_copy (tree lhsop, tree rhsop)
3393 struct constraint_expr lhs, rhs, tmp;
3394 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3396 unsigned HOST_WIDE_INT lhssize;
3397 unsigned HOST_WIDE_INT rhssize;
3399 /* Pretend we are taking the address of the constraint exprs.
3400 We deal with walking the sub-fields ourselves. */
3401 get_constraint_for_1 (lhsop, &lhsc, true);
3402 get_constraint_for_1 (rhsop, &rhsc, true);
3403 gcc_assert (VEC_length (ce_s, lhsc) == 1);
3404 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3405 lhs = *(VEC_last (ce_s, lhsc));
3406 rhs = *(VEC_last (ce_s, rhsc));
3408 VEC_free (ce_s, heap, lhsc);
3409 VEC_free (ce_s, heap, rhsc);
3411 /* If we have special var = x, swap it around. */
3412 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
3419 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
3420 possible it's something we could handle. However, most cases falling
3421 into this are dealing with transparent unions, which are slightly
3423 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
3425 rhs.type = ADDRESSOF;
3426 rhs.var = anything_id;
3429 /* If the RHS is a special var, or an addressof, set all the LHS fields to
3430 that special var. */
3431 if (rhs.var <= integer_id)
3433 for (p = get_varinfo (lhs.var); p; p = p->next)
3435 struct constraint_expr templhs = lhs;
3436 struct constraint_expr temprhs = rhs;
3438 if (templhs.type == SCALAR )
3439 templhs.var = p->id;
3441 templhs.offset += p->offset;
3442 process_constraint (new_constraint (templhs, temprhs));
3447 tree rhstype = TREE_TYPE (rhsop);
3448 tree lhstype = TREE_TYPE (lhsop);
3452 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
3453 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
3455 /* If we have a variably sized types on the rhs or lhs, and a deref
3456 constraint, add the constraint, lhsconstraint = &ANYTHING.
3457 This is conservatively correct because either the lhs is an unknown
3458 sized var (if the constraint is SCALAR), or the lhs is a DEREF
3459 constraint, and every variable it can point to must be unknown sized
3460 anyway, so we don't need to worry about fields at all. */
3461 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
3462 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
3464 rhs.var = anything_id;
3465 rhs.type = ADDRESSOF;
3467 process_constraint (new_constraint (lhs, rhs));
3471 /* The size only really matters insofar as we don't set more or less of
3472 the variable. If we hit an unknown size var, the size should be the
3473 whole darn thing. */
3474 if (get_varinfo (rhs.var)->is_unknown_size_var)
3477 rhssize = TREE_INT_CST_LOW (rhstypesize);
3479 if (get_varinfo (lhs.var)->is_unknown_size_var)
3482 lhssize = TREE_INT_CST_LOW (lhstypesize);
3485 if (rhs.type == SCALAR && lhs.type == SCALAR)
3487 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
3489 lhs.var = collapse_rest_of_var (lhs.var);
3490 rhs.var = collapse_rest_of_var (rhs.var);
3495 process_constraint (new_constraint (lhs, rhs));
3498 else if (lhs.type != DEREF && rhs.type == DEREF)
3499 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3500 else if (lhs.type == DEREF && rhs.type != DEREF)
3501 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3504 tree pointedtotype = lhstype;
3507 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3508 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
3509 do_structure_copy (tmpvar, rhsop);
3510 do_structure_copy (lhsop, tmpvar);
3515 /* Create a constraint ID = OP. */
3518 make_constraint_to (unsigned id, tree op)
3520 VEC(ce_s, heap) *rhsc = NULL;
3521 struct constraint_expr *c;
3522 struct constraint_expr includes;
3526 includes.offset = 0;
3527 includes.type = SCALAR;
3529 get_constraint_for (op, &rhsc);
3530 for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3531 process_constraint (new_constraint (includes, *c));
3532 VEC_free (ce_s, heap, rhsc);
3535 /* Make constraints necessary to make OP escape. */
3538 make_escape_constraint (tree op)
3540 make_constraint_to (escaped_id, op);
3543 /* For non-IPA mode, generate constraints necessary for a call on the
3547 handle_rhs_call (tree rhs)
3550 call_expr_arg_iterator iter;
3552 FOR_EACH_CALL_EXPR_ARG (arg, iter, rhs)
3553 /* Find those pointers being passed, and make sure they end up
3554 pointing to anything. */
3555 if (could_have_pointers (arg))
3556 make_escape_constraint (arg);
3558 /* The static chain escapes as well. */
3559 if (CALL_EXPR_STATIC_CHAIN (rhs))
3560 make_escape_constraint (CALL_EXPR_STATIC_CHAIN (rhs));
3563 /* For non-IPA mode, generate constraints necessary for a call
3564 that returns a pointer and assigns it to LHS. This simply makes
3565 the LHS point to global and escaped variables. */
3568 handle_lhs_call (tree lhs, int flags)
3570 VEC(ce_s, heap) *lhsc = NULL;
3571 struct constraint_expr rhsc;
3573 struct constraint_expr *lhsp;
3575 get_constraint_for (lhs, &lhsc);
3577 if (flags & ECF_MALLOC)
3579 tree heapvar = heapvar_lookup (lhs);
3582 if (heapvar == NULL)
3584 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
3585 DECL_EXTERNAL (heapvar) = 1;
3586 get_var_ann (heapvar)->is_heapvar = 1;
3587 if (gimple_referenced_vars (cfun))
3588 add_referenced_var (heapvar);
3589 heapvar_insert (lhs, heapvar);
3592 rhsc.var = create_variable_info_for (heapvar,
3593 alias_get_name (heapvar));
3594 vi = get_varinfo (rhsc.var);
3595 vi->is_artificial_var = 1;
3596 vi->is_heap_var = 1;
3597 rhsc.type = ADDRESSOF;
3602 rhsc.var = escaped_id;
3604 rhsc.type = ADDRESSOF;
3606 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3607 process_constraint (new_constraint (*lhsp, rhsc));
3608 VEC_free (ce_s, heap, lhsc);
3611 /* For non-IPA mode, generate constraints necessary for a call of a
3612 const function that returns a pointer in the statement STMT. */
3615 handle_const_call (tree stmt)
3617 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3618 tree call = get_call_expr_in (stmt);
3619 VEC(ce_s, heap) *lhsc = NULL;
3620 struct constraint_expr rhsc;
3622 struct constraint_expr *lhsp;
3624 call_expr_arg_iterator iter;
3625 struct constraint_expr tmpc;
3627 get_constraint_for (lhs, &lhsc);
3629 /* If this is a nested function then it can return anything. */
3630 if (CALL_EXPR_STATIC_CHAIN (call))
3632 rhsc.var = anything_id;
3634 rhsc.type = ADDRESSOF;
3635 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3636 process_constraint (new_constraint (*lhsp, rhsc));
3637 VEC_free (ce_s, heap, lhsc);
3641 /* We always use a temporary here, otherwise we end up with a quadratic
3642 amount of constraints for
3643 large_struct = const_call (large_struct);
3644 in field-sensitive PTA. */
3645 tmpvar = create_tmp_var_raw (ptr_type_node, "consttmp");
3646 tmpc = get_constraint_exp_for_temp (tmpvar);
3648 /* May return addresses of globals. */
3649 rhsc.var = nonlocal_id;
3651 rhsc.type = ADDRESSOF;
3652 process_constraint (new_constraint (tmpc, rhsc));
3654 /* May return arguments. */
3655 FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
3656 if (could_have_pointers (arg))
3658 VEC(ce_s, heap) *argc = NULL;
3659 struct constraint_expr *argp;
3662 get_constraint_for (arg, &argc);
3663 for (i = 0; VEC_iterate (ce_s, argc, i, argp); i++)
3664 process_constraint (new_constraint (tmpc, *argp));
3665 VEC_free (ce_s, heap, argc);
3668 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3669 process_constraint (new_constraint (*lhsp, tmpc));
3671 VEC_free (ce_s, heap, lhsc);
3674 /* For non-IPA mode, generate constraints necessary for a call to a
3675 pure function in statement STMT. */
3678 handle_pure_call (tree stmt)
3680 tree call = get_call_expr_in (stmt);
3682 call_expr_arg_iterator iter;
3684 /* Memory reached from pointer arguments is call-used. */
3685 FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
3686 if (could_have_pointers (arg))
3687 make_constraint_to (callused_id, arg);
3689 /* The static chain is used as well. */
3690 if (CALL_EXPR_STATIC_CHAIN (call))
3691 make_constraint_to (callused_id, CALL_EXPR_STATIC_CHAIN (call));
3693 /* If the call returns a pointer it may point to reachable memory
3694 from the arguments. Not so for malloc functions though. */
3695 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3696 && could_have_pointers (GIMPLE_STMT_OPERAND (stmt, 0))
3697 && !(call_expr_flags (call) & ECF_MALLOC))
3699 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3700 VEC(ce_s, heap) *lhsc = NULL;
3701 struct constraint_expr rhsc;
3702 struct constraint_expr *lhsp;
3705 get_constraint_for (lhs, &lhsc);
3707 /* If this is a nested function then it can return anything. */
3708 if (CALL_EXPR_STATIC_CHAIN (call))
3710 rhsc.var = anything_id;
3712 rhsc.type = ADDRESSOF;
3713 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3714 process_constraint (new_constraint (*lhsp, rhsc));
3715 VEC_free (ce_s, heap, lhsc);
3719 /* Else just add the call-used memory here. Escaped variables
3720 and globals will be dealt with in handle_lhs_call. */
3721 rhsc.var = callused_id;
3723 rhsc.type = ADDRESSOF;
3724 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3725 process_constraint (new_constraint (*lhsp, rhsc));
3726 VEC_free (ce_s, heap, lhsc);
3730 /* Walk statement T setting up aliasing constraints according to the
3731 references found in T. This function is the main part of the
3732 constraint builder. AI points to auxiliary alias information used
3733 when building alias sets and computing alias grouping heuristics. */
3736 find_func_aliases (tree origt)
3738 tree call, t = origt;
3739 VEC(ce_s, heap) *lhsc = NULL;
3740 VEC(ce_s, heap) *rhsc = NULL;
3741 struct constraint_expr *c;
3742 enum escape_type stmt_escape_type;
3744 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
3745 t = TREE_OPERAND (t, 0);
3747 /* Now build constraints expressions. */
3748 if (TREE_CODE (t) == PHI_NODE)
3750 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))));
3752 /* Only care about pointers and structures containing
3754 if (could_have_pointers (PHI_RESULT (t)))
3759 /* For a phi node, assign all the arguments to
3761 get_constraint_for (PHI_RESULT (t), &lhsc);
3762 for (i = 0; i < PHI_NUM_ARGS (t); i++)
3765 tree strippedrhs = PHI_ARG_DEF (t, i);
3767 STRIP_NOPS (strippedrhs);
3768 rhstype = TREE_TYPE (strippedrhs);
3769 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
3771 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3773 struct constraint_expr *c2;
3774 while (VEC_length (ce_s, rhsc) > 0)
3776 c2 = VEC_last (ce_s, rhsc);
3777 process_constraint (new_constraint (*c, *c2));
3778 VEC_pop (ce_s, rhsc);
3784 /* In IPA mode, we need to generate constraints to pass call
3785 arguments through their calls. There are two cases, either a
3786 GIMPLE_MODIFY_STMT when we are returning a value, or just a plain
3787 CALL_EXPR when we are not.
3789 In non-ipa mode, we need to generate constraints for each
3790 pointer passed by address. */
3791 else if ((call = get_call_expr_in (t)) != NULL_TREE)
3793 int flags = call_expr_flags (call);
3796 /* Const functions can return their arguments and addresses
3797 of global memory but not of escaped memory. */
3798 if (flags & ECF_CONST)
3800 if (TREE_CODE (t) == GIMPLE_MODIFY_STMT
3801 && could_have_pointers (GIMPLE_STMT_OPERAND (t, 1)))
3802 handle_const_call (t);
3804 else if (flags & ECF_PURE)
3806 handle_pure_call (t);
3807 if (TREE_CODE (t) == GIMPLE_MODIFY_STMT
3808 && could_have_pointers (GIMPLE_STMT_OPERAND (t, 1)))
3809 handle_lhs_call (GIMPLE_STMT_OPERAND (t, 0), flags);
3811 /* Pure functions can return addresses in and of memory
3812 reachable from their arguments, but they are not an escape
3813 point for reachable memory of their arguments. But as we
3814 do not compute call-used memory separately we cannot do
3815 something special here. */
3816 else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
3818 handle_rhs_call (GIMPLE_STMT_OPERAND (t, 1));
3819 if (could_have_pointers (GIMPLE_STMT_OPERAND (t, 1)))
3820 handle_lhs_call (GIMPLE_STMT_OPERAND (t, 0), flags);
3823 handle_rhs_call (t);
3830 call_expr_arg_iterator iter;
3834 if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
3836 lhsop = GIMPLE_STMT_OPERAND (t, 0);
3837 rhsop = GIMPLE_STMT_OPERAND (t, 1);
3844 decl = get_callee_fndecl (rhsop);
3846 /* If we can directly resolve the function being called, do so.
3847 Otherwise, it must be some sort of indirect expression that
3848 we should still be able to handle. */
3851 fi = get_vi_for_tree (decl);
3855 decl = CALL_EXPR_FN (rhsop);
3856 fi = get_vi_for_tree (decl);
3859 /* Assign all the passed arguments to the appropriate incoming
3860 parameters of the function. */
3862 FOR_EACH_CALL_EXPR_ARG (arg, iter, rhsop)
3864 struct constraint_expr lhs ;
3865 struct constraint_expr *rhsp;
3867 get_constraint_for (arg, &rhsc);
3868 if (TREE_CODE (decl) != FUNCTION_DECL)
3877 lhs.var = first_vi_for_offset (fi, i)->id;
3880 while (VEC_length (ce_s, rhsc) != 0)
3882 rhsp = VEC_last (ce_s, rhsc);
3883 process_constraint (new_constraint (lhs, *rhsp));
3884 VEC_pop (ce_s, rhsc);
3889 /* If we are returning a value, assign it to the result. */
3892 struct constraint_expr rhs;
3893 struct constraint_expr *lhsp;
3896 get_constraint_for (lhsop, &lhsc);
3897 if (TREE_CODE (decl) != FUNCTION_DECL)
3906 rhs.var = first_vi_for_offset (fi, i)->id;
3909 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3910 process_constraint (new_constraint (*lhsp, rhs));
3914 /* Otherwise, just a regular assignment statement. Only care about
3915 operations with pointer result, others are dealt with as escape
3916 points if they have pointer operands. */
3917 else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT
3918 && could_have_pointers (GIMPLE_STMT_OPERAND (t, 0)))
3920 tree lhsop = GIMPLE_STMT_OPERAND (t, 0);
3921 tree rhsop = GIMPLE_STMT_OPERAND (t, 1);
3923 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
3924 do_structure_copy (lhsop, rhsop);
3928 get_constraint_for (lhsop, &lhsc);
3929 get_constraint_for (rhsop, &rhsc);
3930 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3932 struct constraint_expr *c2;
3935 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3936 process_constraint (new_constraint (*c, *c2));
3940 else if (TREE_CODE (t) == CHANGE_DYNAMIC_TYPE_EXPR)
3944 get_constraint_for (CHANGE_DYNAMIC_TYPE_LOCATION (t), &lhsc);
3945 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); ++j)
3946 get_varinfo (c->var)->no_tbaa_pruning = true;
3949 stmt_escape_type = is_escape_site (t);
3950 if (stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
3953 gcc_assert (TREE_CODE (t) == GIMPLE_MODIFY_STMT);
3954 rhs = GIMPLE_STMT_OPERAND (t, 1);
3955 if (TREE_CODE (rhs) == ADDR_EXPR)
3957 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3960 || !is_global_var (base)))
3961 make_escape_constraint (rhs);
3963 else if (TREE_CODE (rhs) == SSA_NAME
3964 && POINTER_TYPE_P (TREE_TYPE (rhs)))
3965 make_escape_constraint (rhs);
3966 else if (could_have_pointers (rhs))
3967 make_escape_constraint (rhs);
3969 else if (stmt_escape_type == ESCAPE_BAD_CAST)
3972 gcc_assert (TREE_CODE (t) == GIMPLE_MODIFY_STMT);
3973 rhs = GIMPLE_STMT_OPERAND (t, 1);
3974 gcc_assert (CONVERT_EXPR_P (rhs)
3975 || TREE_CODE (rhs) == VIEW_CONVERT_EXPR);
3976 rhs = TREE_OPERAND (rhs, 0);
3977 make_escape_constraint (rhs);
3979 else if (stmt_escape_type == ESCAPE_TO_ASM)
3983 for (i = 0, link = ASM_OUTPUTS (t); link; i++, link = TREE_CHAIN (link))
3985 tree op = TREE_VALUE (link);
3986 if (op && could_have_pointers (op))
3987 /* Strictly we'd only need the constraints from ESCAPED and
3989 make_escape_constraint (op);
3991 for (i = 0, link = ASM_INPUTS (t); link; i++, link = TREE_CHAIN (link))
3993 tree op = TREE_VALUE (link);
3994 if (op && could_have_pointers (op))
3995 /* Strictly we'd only need the constraint to ESCAPED. */
3996 make_escape_constraint (op);
4000 /* After promoting variables and computing aliasing we will
4001 need to re-scan most statements. FIXME: Try to minimize the
4002 number of statements re-scanned. It's not really necessary to
4003 re-scan *all* statements. */
4005 mark_stmt_modified (origt);
4006 VEC_free (ce_s, heap, rhsc);
4007 VEC_free (ce_s, heap, lhsc);
4011 /* Find the first varinfo in the same variable as START that overlaps with
4013 Effectively, walk the chain of fields for the variable START to find the
4014 first field that overlaps with OFFSET.
4015 Return NULL if we can't find one. */
4018 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
4020 varinfo_t curr = start;
4023 /* We may not find a variable in the field list with the actual
4024 offset when when we have glommed a structure to a variable.
4025 In that case, however, offset should still be within the size
4027 if (offset >= curr->offset && offset < (curr->offset + curr->size))
4035 /* Insert the varinfo FIELD into the field list for BASE, at the front
4039 insert_into_field_list (varinfo_t base, varinfo_t field)
4041 varinfo_t prev = base;
4042 varinfo_t curr = base->next;
4048 /* Insert the varinfo FIELD into the field list for BASE, ordered by
4052 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
4054 varinfo_t prev = base;
4055 varinfo_t curr = base->next;
4066 if (field->offset <= curr->offset)
4071 field->next = prev->next;
4076 /* This structure is used during pushing fields onto the fieldstack
4077 to track the offset of the field, since bitpos_of_field gives it
4078 relative to its immediate containing type, and we want it relative
4079 to the ultimate containing object. */
4083 /* Offset from the base of the base containing object to this field. */
4084 HOST_WIDE_INT offset;
4086 /* Size, in bits, of the field. */
4087 unsigned HOST_WIDE_INT size;
4089 unsigned has_unknown_size : 1;
4091 unsigned may_have_pointers : 1;
4093 typedef struct fieldoff fieldoff_s;
4095 DEF_VEC_O(fieldoff_s);
4096 DEF_VEC_ALLOC_O(fieldoff_s,heap);
4098 /* qsort comparison function for two fieldoff's PA and PB */
4101 fieldoff_compare (const void *pa, const void *pb)
4103 const fieldoff_s *foa = (const fieldoff_s *)pa;
4104 const fieldoff_s *fob = (const fieldoff_s *)pb;
4105 unsigned HOST_WIDE_INT foasize, fobsize;
4107 if (foa->offset < fob->offset)
4109 else if (foa->offset > fob->offset)
4112 foasize = foa->size;
4113 fobsize = fob->size;
4114 if (foasize < fobsize)
4116 else if (foasize > fobsize)
4121 /* Sort a fieldstack according to the field offset and sizes. */
4123 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
4125 qsort (VEC_address (fieldoff_s, fieldstack),
4126 VEC_length (fieldoff_s, fieldstack),
4127 sizeof (fieldoff_s),
4131 /* Return true if V is a tree that we can have subvars for.
4132 Normally, this is any aggregate type. Also complex
4133 types which are not gimple registers can have subvars. */
4136 var_can_have_subvars (const_tree v)
4138 /* Volatile variables should never have subvars. */
4139 if (TREE_THIS_VOLATILE (v))
4142 /* Non decls or memory tags can never have subvars. */
4143 if (!DECL_P (v) || MTAG_P (v))
4146 /* Aggregates without overlapping fields can have subvars. */
4147 if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
4153 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4154 the fields of TYPE onto fieldstack, recording their offsets along
4157 OFFSET is used to keep track of the offset in this entire
4158 structure, rather than just the immediately containing structure.
4159 Returns the number of fields pushed. */
4162 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
4163 HOST_WIDE_INT offset)
4168 if (TREE_CODE (type) != RECORD_TYPE)
4171 /* If the vector of fields is growing too big, bail out early.
4172 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4174 if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
4177 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
4178 if (TREE_CODE (field) == FIELD_DECL)
4182 HOST_WIDE_INT foff = bitpos_of_field (field);
4184 if (!var_can_have_subvars (field)
4185 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
4186 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
4188 else if (!(pushed = push_fields_onto_fieldstack
4189 (TREE_TYPE (field), fieldstack, offset + foff))
4190 && (DECL_SIZE (field)
4191 && !integer_zerop (DECL_SIZE (field))))
4192 /* Empty structures may have actual size, like in C++. So
4193 see if we didn't push any subfields and the size is
4194 nonzero, push the field onto the stack. */
4199 fieldoff_s *pair = NULL;
4200 bool has_unknown_size = false;
4202 if (!VEC_empty (fieldoff_s, *fieldstack))
4203 pair = VEC_last (fieldoff_s, *fieldstack);
4205 if (!DECL_SIZE (field)
4206 || !host_integerp (DECL_SIZE (field), 1))
4207 has_unknown_size = true;
4209 /* If adjacent fields do not contain pointers merge them. */
4211 && !pair->may_have_pointers
4212 && !could_have_pointers (field)
4213 && !pair->has_unknown_size
4214 && !has_unknown_size
4215 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
4217 pair = VEC_last (fieldoff_s, *fieldstack);
4218 pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
4222 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
4223 pair->offset = offset + foff;
4224 pair->has_unknown_size = has_unknown_size;
4225 if (!has_unknown_size)
4226 pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
4229 pair->may_have_pointers = could_have_pointers (field);
4240 /* Create a constraint ID = &FROM. */
4243 make_constraint_from (varinfo_t vi, int from)
4245 struct constraint_expr lhs, rhs;
4253 rhs.type = ADDRESSOF;
4254 process_constraint (new_constraint (lhs, rhs));
4257 /* Count the number of arguments DECL has, and set IS_VARARGS to true
4258 if it is a varargs function. */
4261 count_num_arguments (tree decl, bool *is_varargs)
4266 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
4270 if (TREE_VALUE (t) == void_type_node)
4280 /* Creation function node for DECL, using NAME, and return the index
4281 of the variable we've created for the function. */
4284 create_function_info_for (tree decl, const char *name)
4286 unsigned int index = VEC_length (varinfo_t, varmap);
4290 bool is_varargs = false;
4292 /* Create the variable info. */
4294 vi = new_var_info (decl, index, name);
4298 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
4299 insert_vi_for_tree (vi->decl, vi);
4300 VEC_safe_push (varinfo_t, heap, varmap, vi);
4304 /* If it's varargs, we don't know how many arguments it has, so we
4310 vi->is_unknown_size_var = true;
4315 arg = DECL_ARGUMENTS (decl);
4317 /* Set up variables for each argument. */
4318 for (i = 1; i < vi->fullsize; i++)
4321 const char *newname;
4323 unsigned int newindex;
4324 tree argdecl = decl;
4329 newindex = VEC_length (varinfo_t, varmap);
4330 asprintf (&tempname, "%s.arg%d", name, i-1);
4331 newname = ggc_strdup (tempname);
4334 argvi = new_var_info (argdecl, newindex, newname);
4335 argvi->decl = argdecl;
4336 VEC_safe_push (varinfo_t, heap, varmap, argvi);
4339 argvi->is_full_var = true;
4340 argvi->fullsize = vi->fullsize;
4341 insert_into_field_list_sorted (vi, argvi);
4342 stats.total_vars ++;
4345 insert_vi_for_tree (arg, argvi);
4346 arg = TREE_CHAIN (arg);
4350 /* Create a variable for the return var. */
4351 if (DECL_RESULT (decl) != NULL
4352 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
4355 const char *newname;
4357 unsigned int newindex;
4358 tree resultdecl = decl;
4362 if (DECL_RESULT (decl))
4363 resultdecl = DECL_RESULT (decl);
4365 newindex = VEC_length (varinfo_t, varmap);
4366 asprintf (&tempname, "%s.result", name);
4367 newname = ggc_strdup (tempname);
4370 resultvi = new_var_info (resultdecl, newindex, newname);
4371 resultvi->decl = resultdecl;
4372 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
4373 resultvi->offset = i;
4375 resultvi->fullsize = vi->fullsize;
4376 resultvi->is_full_var = true;
4377 insert_into_field_list_sorted (vi, resultvi);
4378 stats.total_vars ++;
4379 if (DECL_RESULT (decl))
4380 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
4386 /* Return true if FIELDSTACK contains fields that overlap.
4387 FIELDSTACK is assumed to be sorted by offset. */
4390 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
4392 fieldoff_s *fo = NULL;
4394 HOST_WIDE_INT lastoffset = -1;
4396 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4398 if (fo->offset == lastoffset)
4400 lastoffset = fo->offset;
4405 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4406 This will also create any varinfo structures necessary for fields
4410 create_variable_info_for (tree decl, const char *name)
4412 unsigned int index = VEC_length (varinfo_t, varmap);
4414 tree decltype = TREE_TYPE (decl);
4415 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
4416 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
4417 VEC (fieldoff_s,heap) *fieldstack = NULL;
4419 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4420 return create_function_info_for (decl, name);
4422 if (var_can_have_subvars (decl) && use_field_sensitive)
4423 push_fields_onto_fieldstack (decltype, &fieldstack, 0);
4425 /* If the variable doesn't have subvars, we may end up needing to
4426 sort the field list and create fake variables for all the
4428 vi = new_var_info (decl, index, name);
4432 || !host_integerp (declsize, 1))
4434 vi->is_unknown_size_var = true;
4440 vi->fullsize = TREE_INT_CST_LOW (declsize);
4441 vi->size = vi->fullsize;
4444 insert_vi_for_tree (vi->decl, vi);
4445 VEC_safe_push (varinfo_t, heap, varmap, vi);
4446 if (is_global && (!flag_whole_program || !in_ipa_mode)
4447 && could_have_pointers (decl))
4448 make_constraint_from (vi, escaped_id);
4451 if (use_field_sensitive
4452 && !vi->is_unknown_size_var
4453 && var_can_have_subvars (decl)
4454 && VEC_length (fieldoff_s, fieldstack) > 1
4455 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4457 unsigned int newindex = VEC_length (varinfo_t, varmap);
4458 fieldoff_s *fo = NULL;
4459 bool notokay = false;
4462 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4464 if (fo->has_unknown_size
4472 /* We can't sort them if we have a field with a variable sized type,
4473 which will make notokay = true. In that case, we are going to return
4474 without creating varinfos for the fields anyway, so sorting them is a
4478 sort_fieldstack (fieldstack);
4479 /* Due to some C++ FE issues, like PR 22488, we might end up
4480 what appear to be overlapping fields even though they,
4481 in reality, do not overlap. Until the C++ FE is fixed,
4482 we will simply disable field-sensitivity for these cases. */
4483 notokay = check_for_overlaps (fieldstack);
4487 if (VEC_length (fieldoff_s, fieldstack) != 0)
4488 fo = VEC_index (fieldoff_s, fieldstack, 0);
4490 if (fo == NULL || notokay)
4492 vi->is_unknown_size_var = 1;
4495 vi->is_full_var = true;
4496 VEC_free (fieldoff_s, heap, fieldstack);
4500 vi->size = fo->size;
4501 vi->offset = fo->offset;
4502 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4503 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4507 const char *newname = "NULL";
4510 newindex = VEC_length (varinfo_t, varmap);
4513 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
4514 "+" HOST_WIDE_INT_PRINT_DEC,
4515 vi->name, fo->offset, fo->size);
4516 newname = ggc_strdup (tempname);
4519 newvi = new_var_info (decl, newindex, newname);
4520 newvi->offset = fo->offset;
4521 newvi->size = fo->size;
4522 newvi->fullsize = vi->fullsize;
4523 insert_into_field_list (vi, newvi);
4524 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4525 if (is_global && (!flag_whole_program || !in_ipa_mode)
4526 && fo->may_have_pointers)
4527 make_constraint_from (newvi, escaped_id);
4533 vi->is_full_var = true;
4535 VEC_free (fieldoff_s, heap, fieldstack);
4540 /* Print out the points-to solution for VAR to FILE. */
4543 dump_solution_for_var (FILE *file, unsigned int var)
4545 varinfo_t vi = get_varinfo (var);
4549 if (find (var) != var)
4551 varinfo_t vipt = get_varinfo (find (var));
4552 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4556 fprintf (file, "%s = { ", vi->name);
4557 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4559 fprintf (file, "%s ", get_varinfo (i)->name);
4561 fprintf (file, "}");
4562 if (vi->no_tbaa_pruning)
4563 fprintf (file, " no-tbaa-pruning");
4564 fprintf (file, "\n");
4568 /* Print the points-to solution for VAR to stdout. */
4571 debug_solution_for_var (unsigned int var)
4573 dump_solution_for_var (stdout, var);
4576 /* Create varinfo structures for all of the variables in the
4577 function for intraprocedural mode. */
4580 intra_create_variable_infos (void)
4583 struct constraint_expr lhs, rhs;
4585 /* For each incoming pointer argument arg, create the constraint ARG
4586 = NONLOCAL or a dummy variable if flag_argument_noalias is set. */
4587 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4591 if (!could_have_pointers (t))
4594 /* If flag_argument_noalias is set, then function pointer
4595 arguments are guaranteed not to point to each other. In that
4596 case, create an artificial variable PARM_NOALIAS and the
4597 constraint ARG = &PARM_NOALIAS. */
4598 if (POINTER_TYPE_P (TREE_TYPE (t)) && flag_argument_noalias > 0)
4601 tree heapvar = heapvar_lookup (t);
4605 lhs.var = get_vi_for_tree (t)->id;
4607 if (heapvar == NULL_TREE)
4610 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4612 DECL_EXTERNAL (heapvar) = 1;
4613 if (gimple_referenced_vars (cfun))
4614 add_referenced_var (heapvar);
4616 heapvar_insert (t, heapvar);
4618 ann = get_var_ann (heapvar);
4619 if (flag_argument_noalias == 1)
4620 ann->noalias_state = NO_ALIAS;
4621 else if (flag_argument_noalias == 2)
4622 ann->noalias_state = NO_ALIAS_GLOBAL;
4623 else if (flag_argument_noalias == 3)
4624 ann->noalias_state = NO_ALIAS_ANYTHING;
4629 vi = get_vi_for_tree (heapvar);
4630 vi->is_artificial_var = 1;
4631 vi->is_heap_var = 1;
4633 rhs.type = ADDRESSOF;
4635 for (p = get_varinfo (lhs.var); p; p = p->next)
4637 struct constraint_expr temp = lhs;
4639 process_constraint (new_constraint (temp, rhs));
4644 varinfo_t arg_vi = get_vi_for_tree (t);
4646 for (p = arg_vi; p; p = p->next)
4647 make_constraint_from (p, nonlocal_id);
4652 /* Structure used to put solution bitmaps in a hashtable so they can
4653 be shared among variables with the same points-to set. */
4655 typedef struct shared_bitmap_info
4659 } *shared_bitmap_info_t;
4660 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
4662 static htab_t shared_bitmap_table;
4664 /* Hash function for a shared_bitmap_info_t */
4667 shared_bitmap_hash (const void *p)
4669 const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
4670 return bi->hashcode;
4673 /* Equality function for two shared_bitmap_info_t's. */
4676 shared_bitmap_eq (const void *p1, const void *p2)
4678 const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
4679 const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
4680 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
4683 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4684 existing instance if there is one, NULL otherwise. */
4687 shared_bitmap_lookup (bitmap pt_vars)
4690 struct shared_bitmap_info sbi;
4692 sbi.pt_vars = pt_vars;
4693 sbi.hashcode = bitmap_hash (pt_vars);
4695 slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
4696 sbi.hashcode, NO_INSERT);
4700 return ((shared_bitmap_info_t) *slot)->pt_vars;
4704 /* Add a bitmap to the shared bitmap hashtable. */
4707 shared_bitmap_add (bitmap pt_vars)
4710 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
4712 sbi->pt_vars = pt_vars;
4713 sbi->hashcode = bitmap_hash (pt_vars);
4715 slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
4716 sbi->hashcode, INSERT);
4717 gcc_assert (!*slot);
4718 *slot = (void *) sbi;
4722 /* Set bits in INTO corresponding to the variable uids in solution set
4723 FROM, which came from variable PTR.
4724 For variables that are actually dereferenced, we also use type
4725 based alias analysis to prune the points-to sets.
4726 IS_DEREFED is true if PTR was directly dereferenced, which we use to
4727 help determine whether we are we are allowed to prune using TBAA.
4728 If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of
4732 set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed,
4733 bool no_tbaa_pruning)
4738 gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
4740 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4742 varinfo_t vi = get_varinfo (i);
4744 /* The only artificial variables that are allowed in a may-alias
4745 set are heap variables. */
4746 if (vi->is_artificial_var && !vi->is_heap_var)
4749 if (TREE_CODE (vi->decl) == VAR_DECL
4750 || TREE_CODE (vi->decl) == PARM_DECL
4751 || TREE_CODE (vi->decl) == RESULT_DECL)
4753 /* Just add VI->DECL to the alias set.
4754 Don't type prune artificial vars or points-to sets
4755 for pointers that have not been dereferenced or with
4756 type-based pruning disabled. */
4757 if (vi->is_artificial_var
4760 bitmap_set_bit (into, DECL_UID (vi->decl));
4763 alias_set_type var_alias_set, mem_alias_set;
4764 var_alias_set = get_alias_set (vi->decl);
4765 mem_alias_set = get_alias_set (TREE_TYPE (TREE_TYPE (ptr)));
4766 if (may_alias_p (SSA_NAME_VAR (ptr), mem_alias_set,
4767 vi->decl, var_alias_set, true))
4768 bitmap_set_bit (into, DECL_UID (vi->decl));
4775 static bool have_alias_info = false;
4777 /* Given a pointer variable P, fill in its points-to set, or return
4779 Rather than return false for variables that point-to anything, we
4780 instead find the corresponding SMT, and merge in its aliases. In
4781 addition to these aliases, we also set the bits for the SMT's
4782 themselves and their subsets, as SMT's are still in use by
4783 non-SSA_NAME's, and pruning may eliminate every one of their
4784 aliases. In such a case, if we did not include the right set of
4785 SMT's in the points-to set of the variable, we'd end up with
4786 statements that do not conflict but should. */
4789 find_what_p_points_to (tree p)
4794 if (!have_alias_info)
4797 /* For parameters, get at the points-to set for the actual parm
4799 if (TREE_CODE (p) == SSA_NAME
4800 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4801 && SSA_NAME_IS_DEFAULT_DEF (p))
4802 lookup_p = SSA_NAME_VAR (p);
4804 vi = lookup_vi_for_tree (lookup_p);
4807 if (vi->is_artificial_var)
4810 /* See if this is a field or a structure. */
4811 if (vi->size != vi->fullsize)
4813 /* Nothing currently asks about structure fields directly,
4814 but when they do, we need code here to hand back the
4820 struct ptr_info_def *pi = get_ptr_info (p);
4823 bool was_pt_anything = false;
4824 bitmap finished_solution;
4827 if (!pi->memory_tag_needed)
4830 /* This variable may have been collapsed, let's get the real
4832 vi = get_varinfo (find (vi->id));
4834 /* Translate artificial variables into SSA_NAME_PTR_INFO
4836 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4838 varinfo_t vi = get_varinfo (i);
4840 if (vi->is_artificial_var)
4842 /* FIXME. READONLY should be handled better so that
4843 flow insensitive aliasing can disregard writable
4845 if (vi->id == nothing_id)
4847 else if (vi->id == anything_id
4848 || vi->id == nonlocal_id
4849 || vi->id == escaped_id
4850 || vi->id == callused_id)
4851 was_pt_anything = 1;
4852 else if (vi->id == readonly_id)
4853 was_pt_anything = 1;
4854 else if (vi->id == integer_id)
4855 was_pt_anything = 1;
4856 else if (vi->is_heap_var)
4857 pi->pt_global_mem = 1;
4861 /* Instead of doing extra work, simply do not create
4862 points-to information for pt_anything pointers. This
4863 will cause the operand scanner to fall back to the
4864 type-based SMT and its aliases. Which is the best
4865 we could do here for the points-to set as well. */
4866 if (was_pt_anything)
4869 /* Share the final set of variables when possible. */
4870 finished_solution = BITMAP_GGC_ALLOC ();
4871 stats.points_to_sets_created++;
4873 set_uids_in_ptset (p, finished_solution, vi->solution,
4874 pi->is_dereferenced,
4875 vi->no_tbaa_pruning);
4876 result = shared_bitmap_lookup (finished_solution);
4880 shared_bitmap_add (finished_solution);
4881 pi->pt_vars = finished_solution;
4885 pi->pt_vars = result;
4886 bitmap_clear (finished_solution);
4889 if (bitmap_empty_p (pi->pt_vars))
4899 /* Mark the ESCAPED solution as call clobbered. Returns false if
4900 pt_anything escaped which needs all locals that have their address
4901 taken marked call clobbered as well. */
4904 clobber_what_escaped (void)
4910 if (!have_alias_info)
4913 /* This variable may have been collapsed, let's get the real
4914 variable for escaped_id. */
4915 vi = get_varinfo (find (escaped_id));
4917 /* If call-used memory escapes we need to include it in the
4918 set of escaped variables. This can happen if a pure
4919 function returns a pointer and this pointer escapes. */
4920 if (bitmap_bit_p (vi->solution, callused_id))
4922 varinfo_t cu_vi = get_varinfo (find (callused_id));
4923 bitmap_ior_into (vi->solution, cu_vi->solution);
4926 /* Mark variables in the solution call-clobbered. */
4927 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4929 varinfo_t vi = get_varinfo (i);
4931 if (vi->is_artificial_var)
4933 /* nothing_id and readonly_id do not cause any
4934 call clobber ops. For anything_id and integer_id
4935 we need to clobber all addressable vars. */
4936 if (vi->id == anything_id
4937 || vi->id == integer_id)
4941 /* Only artificial heap-vars are further interesting. */
4942 if (vi->is_artificial_var && !vi->is_heap_var)
4945 if ((TREE_CODE (vi->decl) == VAR_DECL
4946 || TREE_CODE (vi->decl) == PARM_DECL
4947 || TREE_CODE (vi->decl) == RESULT_DECL)
4948 && !unmodifiable_var_p (vi->decl))
4949 mark_call_clobbered (vi->decl, ESCAPE_TO_CALL);
4955 /* Compute the call-used variables. */
4958 compute_call_used_vars (void)
4963 bool has_anything_id = false;
4965 if (!have_alias_info)
4968 /* This variable may have been collapsed, let's get the real
4969 variable for escaped_id. */
4970 vi = get_varinfo (find (callused_id));
4972 /* Mark variables in the solution call-clobbered. */
4973 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4975 varinfo_t vi = get_varinfo (i);
4977 if (vi->is_artificial_var)
4979 /* For anything_id and integer_id we need to make
4980 all local addressable vars call-used. */
4981 if (vi->id == anything_id
4982 || vi->id == integer_id)
4983 has_anything_id = true;
4986 /* Only artificial heap-vars are further interesting. */
4987 if (vi->is_artificial_var && !vi->is_heap_var)
4990 if ((TREE_CODE (vi->decl) == VAR_DECL
4991 || TREE_CODE (vi->decl) == PARM_DECL
4992 || TREE_CODE (vi->decl) == RESULT_DECL)
4993 && !unmodifiable_var_p (vi->decl))
4994 bitmap_set_bit (gimple_call_used_vars (cfun), DECL_UID (vi->decl));
4997 /* If anything is call-used, add all addressable locals to the set. */
4998 if (has_anything_id)
4999 bitmap_ior_into (gimple_call_used_vars (cfun),
5000 gimple_addressable_vars (cfun));
5004 /* Dump points-to information to OUTFILE. */
5007 dump_sa_points_to_info (FILE *outfile)
5011 fprintf (outfile, "\nPoints-to sets\n\n");
5013 if (dump_flags & TDF_STATS)
5015 fprintf (outfile, "Stats:\n");
5016 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
5017 fprintf (outfile, "Non-pointer vars: %d\n",
5018 stats.nonpointer_vars);
5019 fprintf (outfile, "Statically unified vars: %d\n",
5020 stats.unified_vars_static);
5021 fprintf (outfile, "Dynamically unified vars: %d\n",
5022 stats.unified_vars_dynamic);
5023 fprintf (outfile, "Iterations: %d\n", stats.iterations);
5024 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
5025 fprintf (outfile, "Number of implicit edges: %d\n",
5026 stats.num_implicit_edges);
5029 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
5030 dump_solution_for_var (outfile, i);
5034 /* Debug points-to information to stderr. */
5037 debug_sa_points_to_info (void)
5039 dump_sa_points_to_info (stderr);
5043 /* Initialize the always-existing constraint variables for NULL
5044 ANYTHING, READONLY, and INTEGER */
5047 init_base_vars (void)
5049 struct constraint_expr lhs, rhs;
5051 /* Create the NULL variable, used to represent that a variable points
5053 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
5054 var_nothing = new_var_info (nothing_tree, nothing_id, "NULL");
5055 insert_vi_for_tree (nothing_tree, var_nothing);
5056 var_nothing->is_artificial_var = 1;
5057 var_nothing->offset = 0;
5058 var_nothing->size = ~0;
5059 var_nothing->fullsize = ~0;
5060 var_nothing->is_special_var = 1;
5061 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
5063 /* Create the ANYTHING variable, used to represent that a variable
5064 points to some unknown piece of memory. */
5065 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
5066 var_anything = new_var_info (anything_tree, anything_id, "ANYTHING");
5067 insert_vi_for_tree (anything_tree, var_anything);
5068 var_anything->is_artificial_var = 1;
5069 var_anything->size = ~0;
5070 var_anything->offset = 0;
5071 var_anything->next = NULL;
5072 var_anything->fullsize = ~0;
5073 var_anything->is_special_var = 1;
5075 /* Anything points to anything. This makes deref constraints just
5076 work in the presence of linked list and other p = *p type loops,
5077 by saying that *ANYTHING = ANYTHING. */
5078 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
5080 lhs.var = anything_id;
5082 rhs.type = ADDRESSOF;
5083 rhs.var = anything_id;
5086 /* This specifically does not use process_constraint because
5087 process_constraint ignores all anything = anything constraints, since all
5088 but this one are redundant. */
5089 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
5091 /* Create the READONLY variable, used to represent that a variable
5092 points to readonly memory. */
5093 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
5094 var_readonly = new_var_info (readonly_tree, readonly_id, "READONLY");
5095 var_readonly->is_artificial_var = 1;
5096 var_readonly->offset = 0;
5097 var_readonly->size = ~0;
5098 var_readonly->fullsize = ~0;
5099 var_readonly->next = NULL;
5100 var_readonly->is_special_var = 1;
5101 insert_vi_for_tree (readonly_tree, var_readonly);
5102 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
5104 /* readonly memory points to anything, in order to make deref
5105 easier. In reality, it points to anything the particular
5106 readonly variable can point to, but we don't track this
5109 lhs.var = readonly_id;
5111 rhs.type = ADDRESSOF;
5112 rhs.var = readonly_id; /* FIXME */
5114 process_constraint (new_constraint (lhs, rhs));
5116 /* Create the ESCAPED variable, used to represent the set of escaped
5118 escaped_tree = create_tmp_var_raw (void_type_node, "ESCAPED");
5119 var_escaped = new_var_info (escaped_tree, escaped_id, "ESCAPED");
5120 insert_vi_for_tree (escaped_tree, var_escaped);
5121 var_escaped->is_artificial_var = 1;
5122 var_escaped->offset = 0;
5123 var_escaped->size = ~0;
5124 var_escaped->fullsize = ~0;
5125 var_escaped->is_special_var = 0;
5126 VEC_safe_push (varinfo_t, heap, varmap, var_escaped);
5127 gcc_assert (VEC_index (varinfo_t, varmap, 3) == var_escaped);
5129 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
5131 lhs.var = escaped_id;
5134 rhs.var = escaped_id;
5136 process_constraint (new_constraint (lhs, rhs));
5138 /* Create the NONLOCAL variable, used to represent the set of nonlocal
5140 nonlocal_tree = create_tmp_var_raw (void_type_node, "NONLOCAL");
5141 var_nonlocal = new_var_info (nonlocal_tree, nonlocal_id, "NONLOCAL");
5142 insert_vi_for_tree (nonlocal_tree, var_nonlocal);
5143 var_nonlocal->is_artificial_var = 1;
5144 var_nonlocal->offset = 0;
5145 var_nonlocal->size = ~0;
5146 var_nonlocal->fullsize = ~0;
5147 var_nonlocal->is_special_var = 1;
5148 VEC_safe_push (varinfo_t, heap, varmap, var_nonlocal);
5150 /* Nonlocal memory points to escaped (which includes nonlocal),
5151 in order to make deref easier. */
5153 lhs.var = nonlocal_id;
5155 rhs.type = ADDRESSOF;
5156 rhs.var = escaped_id;
5158 process_constraint (new_constraint (lhs, rhs));
5160 /* Create the CALLUSED variable, used to represent the set of call-used
5162 callused_tree = create_tmp_var_raw (void_type_node, "CALLUSED");
5163 var_callused = new_var_info (callused_tree, callused_id, "CALLUSED");
5164 insert_vi_for_tree (callused_tree, var_callused);
5165 var_callused->is_artificial_var = 1;
5166 var_callused->offset = 0;
5167 var_callused->size = ~0;
5168 var_callused->fullsize = ~0;
5169 var_callused->is_special_var = 0;
5170 VEC_safe_push (varinfo_t, heap, varmap, var_callused);
5172 /* CALLUSED = *CALLUSED, because call-used is may-deref'd at calls, etc. */
5174 lhs.var = callused_id;
5177 rhs.var = callused_id;
5179 process_constraint (new_constraint (lhs, rhs));
5181 /* Create the INTEGER variable, used to represent that a variable points
5183 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
5184 var_integer = new_var_info (integer_tree, integer_id, "INTEGER");
5185 insert_vi_for_tree (integer_tree, var_integer);
5186 var_integer->is_artificial_var = 1;
5187 var_integer->size = ~0;
5188 var_integer->fullsize = ~0;
5189 var_integer->offset = 0;
5190 var_integer->next = NULL;
5191 var_integer->is_special_var = 1;
5192 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
5194 /* INTEGER = ANYTHING, because we don't know where a dereference of
5195 a random integer will point to. */
5197 lhs.var = integer_id;
5199 rhs.type = ADDRESSOF;
5200 rhs.var = anything_id;
5202 process_constraint (new_constraint (lhs, rhs));
5204 /* *ESCAPED = &ESCAPED. This is true because we have to assume
5205 everything pointed to by escaped can also point to escaped. */
5207 lhs.var = escaped_id;
5209 rhs.type = ADDRESSOF;
5210 rhs.var = escaped_id;
5212 process_constraint (new_constraint (lhs, rhs));
5214 /* *ESCAPED = &NONLOCAL. This is true because we have to assume
5215 everything pointed to by escaped can also point to nonlocal. */
5217 lhs.var = escaped_id;
5219 rhs.type = ADDRESSOF;
5220 rhs.var = nonlocal_id;
5222 process_constraint (new_constraint (lhs, rhs));
5225 /* Initialize things necessary to perform PTA */
5228 init_alias_vars (void)
5230 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
5232 bitmap_obstack_initialize (&pta_obstack);
5233 bitmap_obstack_initialize (&oldpta_obstack);
5234 bitmap_obstack_initialize (&predbitmap_obstack);
5236 constraint_pool = create_alloc_pool ("Constraint pool",
5237 sizeof (struct constraint), 30);
5238 variable_info_pool = create_alloc_pool ("Variable info pool",
5239 sizeof (struct variable_info), 30);
5240 constraints = VEC_alloc (constraint_t, heap, 8);
5241 varmap = VEC_alloc (varinfo_t, heap, 8);
5242 vi_for_tree = pointer_map_create ();
5244 memset (&stats, 0, sizeof (stats));
5245 shared_bitmap_table = htab_create (511, shared_bitmap_hash,
5246 shared_bitmap_eq, free);
5250 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
5251 predecessor edges. */
5254 remove_preds_and_fake_succs (constraint_graph_t graph)
5258 /* Clear the implicit ref and address nodes from the successor
5260 for (i = 0; i < FIRST_REF_NODE; i++)
5262 if (graph->succs[i])
5263 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
5264 FIRST_REF_NODE * 2);
5267 /* Free the successor list for the non-ref nodes. */
5268 for (i = FIRST_REF_NODE; i < graph->size; i++)
5270 if (graph->succs[i])
5271 BITMAP_FREE (graph->succs[i]);
5274 /* Now reallocate the size of the successor list as, and blow away
5275 the predecessor bitmaps. */
5276 graph->size = VEC_length (varinfo_t, varmap);
5277 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
5279 free (graph->implicit_preds);
5280 graph->implicit_preds = NULL;
5281 free (graph->preds);
5282 graph->preds = NULL;
5283 bitmap_obstack_release (&predbitmap_obstack);
5286 /* Compute the set of variables we can't TBAA prune. */
5289 compute_tbaa_pruning (void)
5291 unsigned int size = VEC_length (varinfo_t, varmap);
5296 changed = sbitmap_alloc (size);
5297 sbitmap_zero (changed);
5299 /* Mark all initial no_tbaa_pruning nodes as changed. */
5301 for (i = 0; i < size; ++i)
5303 varinfo_t ivi = get_varinfo (i);
5305 if (find (i) == i && ivi->no_tbaa_pruning)
5308 if ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
5309 || VEC_length (constraint_t, graph->complex[i]) > 0)
5311 SET_BIT (changed, i);
5317 while (changed_count > 0)
5319 struct topo_info *ti = init_topo_info ();
5322 compute_topo_order (graph, ti);
5324 while (VEC_length (unsigned, ti->topo_order) != 0)
5328 i = VEC_pop (unsigned, ti->topo_order);
5330 /* If this variable is not a representative, skip it. */
5334 /* If the node has changed, we need to process the complex
5335 constraints and outgoing edges again. */
5336 if (TEST_BIT (changed, i))
5340 VEC(constraint_t,heap) *complex = graph->complex[i];
5342 RESET_BIT (changed, i);
5345 /* Process the complex copy constraints. */
5346 for (j = 0; VEC_iterate (constraint_t, complex, j, c); ++j)
5348 if (c->lhs.type == SCALAR && c->rhs.type == SCALAR)
5350 varinfo_t lhsvi = get_varinfo (find (c->lhs.var));
5352 if (!lhsvi->no_tbaa_pruning)
5354 lhsvi->no_tbaa_pruning = true;
5355 if (!TEST_BIT (changed, lhsvi->id))
5357 SET_BIT (changed, lhsvi->id);
5364 /* Propagate to all successors. */
5365 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
5367 unsigned int to = find (j);
5368 varinfo_t tovi = get_varinfo (to);
5370 /* Don't propagate to ourselves. */
5374 if (!tovi->no_tbaa_pruning)
5376 tovi->no_tbaa_pruning = true;
5377 if (!TEST_BIT (changed, to))
5379 SET_BIT (changed, to);
5387 free_topo_info (ti);
5390 sbitmap_free (changed);
5394 for (i = 0; i < size; ++i)
5396 varinfo_t ivi = get_varinfo (i);
5397 varinfo_t ivip = get_varinfo (find (i));
5399 if (ivip->no_tbaa_pruning)
5401 tree var = ivi->decl;
5403 if (TREE_CODE (var) == SSA_NAME)
5404 var = SSA_NAME_VAR (var);
5406 if (POINTER_TYPE_P (TREE_TYPE (var)))
5408 DECL_NO_TBAA_P (var) = 1;
5410 /* Tell the RTL layer that this pointer can alias
5412 DECL_POINTER_ALIAS_SET (var) = 0;
5419 /* Create points-to sets for the current function. See the comments
5420 at the start of the file for an algorithmic overview. */
5423 compute_points_to_sets (void)
5425 struct scc_info *si;
5428 timevar_push (TV_TREE_PTA);
5431 init_alias_heapvars ();
5433 intra_create_variable_infos ();
5435 /* Now walk all statements and derive aliases. */
5438 block_stmt_iterator bsi;
5441 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5442 if (is_gimple_reg (PHI_RESULT (phi)))
5443 find_func_aliases (phi);
5445 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
5447 tree stmt = bsi_stmt (bsi);
5449 find_func_aliases (stmt);
5451 /* The information in CHANGE_DYNAMIC_TYPE_EXPR nodes has now
5452 been captured, and we can remove them. */
5453 if (TREE_CODE (stmt) == CHANGE_DYNAMIC_TYPE_EXPR)
5454 bsi_remove (&bsi, true);
5463 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5464 dump_constraints (dump_file);
5469 "\nCollapsing static cycles and doing variable "
5472 init_graph (VEC_length (varinfo_t, varmap) * 2);
5475 fprintf (dump_file, "Building predecessor graph\n");
5476 build_pred_graph ();
5479 fprintf (dump_file, "Detecting pointer and location "
5481 si = perform_var_substitution (graph);
5484 fprintf (dump_file, "Rewriting constraints and unifying "
5486 rewrite_constraints (graph, si);
5487 free_var_substitution_info (si);
5489 build_succ_graph ();
5491 if (dump_file && (dump_flags & TDF_GRAPH))
5492 dump_constraint_graph (dump_file);
5494 move_complex_constraints (graph);
5497 fprintf (dump_file, "Uniting pointer but not location equivalent "
5499 unite_pointer_equivalences (graph);
5502 fprintf (dump_file, "Finding indirect cycles\n");
5503 find_indirect_cycles (graph);
5505 /* Implicit nodes and predecessors are no longer necessary at this
5507 remove_preds_and_fake_succs (graph);
5510 fprintf (dump_file, "Solving graph\n");
5512 solve_graph (graph);
5514 compute_tbaa_pruning ();
5517 dump_sa_points_to_info (dump_file);
5519 have_alias_info = true;
5521 timevar_pop (TV_TREE_PTA);
5525 /* Delete created points-to sets. */
5528 delete_points_to_sets (void)
5532 htab_delete (shared_bitmap_table);
5533 if (dump_file && (dump_flags & TDF_STATS))
5534 fprintf (dump_file, "Points to sets created:%d\n",
5535 stats.points_to_sets_created);
5537 pointer_map_destroy (vi_for_tree);
5538 bitmap_obstack_release (&pta_obstack);
5539 VEC_free (constraint_t, heap, constraints);
5541 for (i = 0; i < graph->size; i++)
5542 VEC_free (constraint_t, heap, graph->complex[i]);
5543 free (graph->complex);
5546 free (graph->succs);
5548 free (graph->pe_rep);
5549 free (graph->indirect_cycles);
5552 VEC_free (varinfo_t, heap, varmap);
5553 free_alloc_pool (variable_info_pool);
5554 free_alloc_pool (constraint_pool);
5555 have_alias_info = false;
5558 /* Return true if we should execute IPA PTA. */
5562 return (flag_unit_at_a_time != 0
5564 /* Don't bother doing anything if the program has errors. */
5565 && !(errorcount || sorrycount));
5568 /* Execute the driver for IPA PTA. */
5570 ipa_pta_execute (void)
5572 struct cgraph_node *node;
5573 struct scc_info *si;
5576 init_alias_heapvars ();
5579 for (node = cgraph_nodes; node; node = node->next)
5581 if (!node->analyzed || cgraph_is_master_clone (node))
5585 varid = create_function_info_for (node->decl,
5586 cgraph_node_name (node));
5587 if (node->local.externally_visible)
5589 varinfo_t fi = get_varinfo (varid);
5590 for (; fi; fi = fi->next)
5591 make_constraint_from (fi, anything_id);
5595 for (node = cgraph_nodes; node; node = node->next)
5597 if (node->analyzed && cgraph_is_master_clone (node))
5599 struct function *func = DECL_STRUCT_FUNCTION (node->decl);
5601 tree old_func_decl = current_function_decl;
5604 "Generating constraints for %s\n",
5605 cgraph_node_name (node));
5607 current_function_decl = node->decl;
5609 FOR_EACH_BB_FN (bb, func)
5611 block_stmt_iterator bsi;
5614 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5616 if (is_gimple_reg (PHI_RESULT (phi)))
5618 find_func_aliases (phi);
5622 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
5624 tree stmt = bsi_stmt (bsi);
5625 find_func_aliases (stmt);
5628 current_function_decl = old_func_decl;
5633 /* Make point to anything. */
5639 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5640 dump_constraints (dump_file);
5645 "\nCollapsing static cycles and doing variable "
5648 init_graph (VEC_length (varinfo_t, varmap) * 2);
5649 build_pred_graph ();
5650 si = perform_var_substitution (graph);
5651 rewrite_constraints (graph, si);
5652 free_var_substitution_info (si);
5654 build_succ_graph ();
5655 move_complex_constraints (graph);
5656 unite_pointer_equivalences (graph);
5657 find_indirect_cycles (graph);
5659 /* Implicit nodes and predecessors are no longer necessary at this
5661 remove_preds_and_fake_succs (graph);
5664 fprintf (dump_file, "\nSolving graph\n");
5666 solve_graph (graph);
5669 dump_sa_points_to_info (dump_file);
5672 delete_alias_heapvars ();
5673 delete_points_to_sets ();
5677 struct simple_ipa_opt_pass pass_ipa_pta =
5682 gate_ipa_pta, /* gate */
5683 ipa_pta_execute, /* execute */
5686 0, /* static_pass_number */
5687 TV_IPA_PTA, /* tv_id */
5688 0, /* properties_required */
5689 0, /* properties_provided */
5690 0, /* properties_destroyed */
5691 0, /* todo_flags_start */
5692 TODO_update_ssa /* todo_flags_finish */
5696 /* Initialize the heapvar for statement mapping. */
5698 init_alias_heapvars (void)
5700 if (!heapvar_for_stmt)
5701 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5706 delete_alias_heapvars (void)
5708 htab_delete (heapvar_for_stmt);
5709 heapvar_for_stmt = NULL;
5713 #include "gt-tree-ssa-structalias.h"