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"
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))
2774 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2777 static HOST_WIDE_INT
2778 bitpos_of_field (const tree fdecl)
2781 if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2782 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2785 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2786 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2790 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2791 resulting constraint expressions in *RESULTS. */
2794 get_constraint_for_ptr_offset (tree ptr, tree offset,
2795 VEC (ce_s, heap) **results)
2797 struct constraint_expr *c;
2799 unsigned HOST_WIDE_INT rhsunitoffset, rhsoffset;
2801 /* If we do not do field-sensitive PTA adding offsets to pointers
2802 does not change the points-to solution. */
2803 if (!use_field_sensitive)
2805 get_constraint_for (ptr, results);
2809 /* If the offset is not a non-negative integer constant that fits
2810 in a HOST_WIDE_INT, we have to fall back to a conservative
2811 solution which includes all sub-fields of all pointed-to
2813 ??? As we do not have the ability to express this, fall back
2815 if (!host_integerp (offset, 1))
2817 struct constraint_expr temp;
2818 temp.var = anything_id;
2821 VEC_safe_push (ce_s, heap, *results, &temp);
2825 /* Make sure the bit-offset also fits. */
2826 rhsunitoffset = TREE_INT_CST_LOW (offset);
2827 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
2828 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
2830 struct constraint_expr temp;
2831 temp.var = anything_id;
2834 VEC_safe_push (ce_s, heap, *results, &temp);
2838 get_constraint_for (ptr, results);
2842 /* As we are eventually appending to the solution do not use
2843 VEC_iterate here. */
2844 n = VEC_length (ce_s, *results);
2845 for (j = 0; j < n; j++)
2848 c = VEC_index (ce_s, *results, j);
2849 curr = get_varinfo (c->var);
2851 if (c->type == ADDRESSOF
2852 && !curr->is_full_var)
2854 varinfo_t temp, curr = get_varinfo (c->var);
2856 /* Search the sub-field which overlaps with the
2857 pointed-to offset. As we deal with positive offsets
2858 only, we can start the search from the current variable. */
2859 temp = first_vi_for_offset (curr, curr->offset + rhsoffset);
2861 /* If the result is outside of the variable we have to provide
2862 a conservative result, as the variable is still reachable
2863 from the resulting pointer (even though it technically
2864 cannot point to anything). The last sub-field is such
2865 a conservative result.
2866 ??? If we always had a sub-field for &object + 1 then
2867 we could represent this in a more precise way. */
2871 while (temp->next != NULL)
2876 /* If the found variable is not exactly at the pointed to
2877 result, we have to include the next variable in the
2878 solution as well. Otherwise two increments by offset / 2
2879 do not result in the same or a conservative superset
2881 if (temp->offset != curr->offset + rhsoffset
2882 && temp->next != NULL)
2884 struct constraint_expr c2;
2885 c2.var = temp->next->id;
2886 c2.type = ADDRESSOF;
2888 VEC_safe_push (ce_s, heap, *results, &c2);
2893 else if (c->type == ADDRESSOF
2894 /* If this varinfo represents a full variable just use it. */
2895 && curr->is_full_var)
2898 c->offset = rhsoffset;
2903 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
2904 If address_p is true the result will be taken its address of. */
2907 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
2911 HOST_WIDE_INT bitsize = -1;
2912 HOST_WIDE_INT bitmaxsize = -1;
2913 HOST_WIDE_INT bitpos;
2915 struct constraint_expr *result;
2917 /* Some people like to do cute things like take the address of
2920 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2921 forzero = TREE_OPERAND (forzero, 0);
2923 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2925 struct constraint_expr temp;
2928 temp.var = integer_id;
2930 VEC_safe_push (ce_s, heap, *results, &temp);
2934 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2936 /* Pretend to take the address of the base, we'll take care of
2937 adding the required subset of sub-fields below. */
2938 get_constraint_for_1 (t, results, true);
2939 gcc_assert (VEC_length (ce_s, *results) == 1);
2940 result = VEC_last (ce_s, *results);
2942 /* This can also happen due to weird offsetof type macros. */
2943 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2944 result->type = SCALAR;
2946 if (result->type == SCALAR
2947 && get_varinfo (result->var)->is_full_var)
2948 /* For single-field vars do not bother about the offset. */
2950 else if (result->type == SCALAR)
2952 /* In languages like C, you can access one past the end of an
2953 array. You aren't allowed to dereference it, so we can
2954 ignore this constraint. When we handle pointer subtraction,
2955 we may have to do something cute here. */
2957 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
2960 /* It's also not true that the constraint will actually start at the
2961 right offset, it may start in some padding. We only care about
2962 setting the constraint to the first actual field it touches, so
2964 struct constraint_expr cexpr = *result;
2966 VEC_pop (ce_s, *results);
2968 for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
2970 if (ranges_overlap_p (curr->offset, curr->size,
2971 bitpos, bitmaxsize))
2973 cexpr.var = curr->id;
2974 VEC_safe_push (ce_s, heap, *results, &cexpr);
2979 /* If we are going to take the address of this field then
2980 to be able to compute reachability correctly add at least
2981 the last field of the variable. */
2983 && VEC_length (ce_s, *results) == 0)
2985 curr = get_varinfo (cexpr.var);
2986 while (curr->next != NULL)
2988 cexpr.var = curr->id;
2989 VEC_safe_push (ce_s, heap, *results, &cexpr);
2992 /* Assert that we found *some* field there. The user couldn't be
2993 accessing *only* padding. */
2994 /* Still the user could access one past the end of an array
2995 embedded in a struct resulting in accessing *only* padding. */
2996 gcc_assert (VEC_length (ce_s, *results) >= 1
2997 || ref_contains_array_ref (orig_t));
2999 else if (bitmaxsize == 0)
3001 if (dump_file && (dump_flags & TDF_DETAILS))
3002 fprintf (dump_file, "Access to zero-sized part of variable,"
3006 if (dump_file && (dump_flags & TDF_DETAILS))
3007 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3009 else if (bitmaxsize == -1)
3011 /* We can't handle DEREF constraints with unknown size, we'll
3012 get the wrong answer. Punt and return anything. */
3013 result->var = anything_id;
3017 result->offset = bitpos;
3021 /* Dereference the constraint expression CONS, and return the result.
3022 DEREF (ADDRESSOF) = SCALAR
3023 DEREF (SCALAR) = DEREF
3024 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3025 This is needed so that we can handle dereferencing DEREF constraints. */
3028 do_deref (VEC (ce_s, heap) **constraints)
3030 struct constraint_expr *c;
3033 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3035 if (c->type == SCALAR)
3037 else if (c->type == ADDRESSOF)
3039 else if (c->type == DEREF)
3041 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
3042 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
3043 process_constraint (new_constraint (tmplhs, *c));
3044 c->var = tmplhs.var;
3051 /* Given a tree T, return the constraint expression for it. */
3054 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3056 struct constraint_expr temp;
3058 /* x = integer is all glommed to a single variable, which doesn't
3059 point to anything by itself. That is, of course, unless it is an
3060 integer constant being treated as a pointer, in which case, we
3061 will return that this is really the addressof anything. This
3062 happens below, since it will fall into the default case. The only
3063 case we know something about an integer treated like a pointer is
3064 when it is the NULL pointer, and then we just say it points to
3066 if (TREE_CODE (t) == INTEGER_CST
3067 && integer_zerop (t))
3069 temp.var = nothing_id;
3070 temp.type = ADDRESSOF;
3072 VEC_safe_push (ce_s, heap, *results, &temp);
3076 /* String constants are read-only. */
3077 if (TREE_CODE (t) == STRING_CST)
3079 temp.var = readonly_id;
3082 VEC_safe_push (ce_s, heap, *results, &temp);
3086 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3088 case tcc_expression:
3090 switch (TREE_CODE (t))
3094 struct constraint_expr *c;
3096 tree exp = TREE_OPERAND (t, 0);
3098 get_constraint_for_1 (exp, results, true);
3100 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3102 if (c->type == DEREF)
3105 c->type = ADDRESSOF;
3116 switch (TREE_CODE (t))
3120 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3125 case ARRAY_RANGE_REF:
3127 get_constraint_for_component_ref (t, results, address_p);
3133 case tcc_exceptional:
3135 switch (TREE_CODE (t))
3139 get_constraint_for_ssa_var (t, results, address_p);
3146 case tcc_declaration:
3148 get_constraint_for_ssa_var (t, results, address_p);
3154 /* The default fallback is a constraint from anything. */
3155 temp.type = ADDRESSOF;
3156 temp.var = anything_id;
3158 VEC_safe_push (ce_s, heap, *results, &temp);
3161 /* Given a gimple tree T, return the constraint expression vector for it. */
3164 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3166 gcc_assert (VEC_length (ce_s, *results) == 0);
3168 get_constraint_for_1 (t, results, false);
3171 /* Handle the structure copy case where we have a simple structure copy
3172 between LHS and RHS that is of SIZE (in bits)
3174 For each field of the lhs variable (lhsfield)
3175 For each field of the rhs variable at lhsfield.offset (rhsfield)
3176 add the constraint lhsfield = rhsfield
3178 If we fail due to some kind of type unsafety or other thing we
3179 can't handle, return false. We expect the caller to collapse the
3180 variable in that case. */
3183 do_simple_structure_copy (const struct constraint_expr lhs,
3184 const struct constraint_expr rhs,
3185 const unsigned HOST_WIDE_INT size)
3187 varinfo_t p = get_varinfo (lhs.var);
3188 unsigned HOST_WIDE_INT pstart, last;
3190 last = p->offset + size;
3191 for (; p && p->offset < last; p = p->next)
3194 struct constraint_expr templhs = lhs;
3195 struct constraint_expr temprhs = rhs;
3196 unsigned HOST_WIDE_INT fieldoffset;
3198 templhs.var = p->id;
3199 q = get_varinfo (temprhs.var);
3200 fieldoffset = p->offset - pstart;
3201 q = first_vi_for_offset (q, q->offset + fieldoffset);
3204 temprhs.var = q->id;
3205 process_constraint (new_constraint (templhs, temprhs));
3211 /* Handle the structure copy case where we have a structure copy between a
3212 aggregate on the LHS and a dereference of a pointer on the RHS
3213 that is of SIZE (in bits)
3215 For each field of the lhs variable (lhsfield)
3216 rhs.offset = lhsfield->offset
3217 add the constraint lhsfield = rhs
3221 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
3222 const struct constraint_expr rhs,
3223 const unsigned HOST_WIDE_INT size)
3225 varinfo_t p = get_varinfo (lhs.var);
3226 unsigned HOST_WIDE_INT pstart,last;
3228 last = p->offset + size;
3230 for (; p && p->offset < last; p = p->next)
3233 struct constraint_expr templhs = lhs;
3234 struct constraint_expr temprhs = rhs;
3235 unsigned HOST_WIDE_INT fieldoffset;
3238 if (templhs.type == SCALAR)
3239 templhs.var = p->id;
3241 templhs.offset = p->offset;
3243 q = get_varinfo (temprhs.var);
3244 fieldoffset = p->offset - pstart;
3245 temprhs.offset += fieldoffset;
3246 process_constraint (new_constraint (templhs, temprhs));
3250 /* Handle the structure copy case where we have a structure copy
3251 between an aggregate on the RHS and a dereference of a pointer on
3252 the LHS that is of SIZE (in bits)
3254 For each field of the rhs variable (rhsfield)
3255 lhs.offset = rhsfield->offset
3256 add the constraint lhs = rhsfield
3260 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
3261 const struct constraint_expr rhs,
3262 const unsigned HOST_WIDE_INT size)
3264 varinfo_t p = get_varinfo (rhs.var);
3265 unsigned HOST_WIDE_INT pstart,last;
3267 last = p->offset + size;
3269 for (; p && p->offset < last; p = p->next)
3272 struct constraint_expr templhs = lhs;
3273 struct constraint_expr temprhs = rhs;
3274 unsigned HOST_WIDE_INT fieldoffset;
3277 if (temprhs.type == SCALAR)
3278 temprhs.var = p->id;
3280 temprhs.offset = p->offset;
3282 q = get_varinfo (templhs.var);
3283 fieldoffset = p->offset - pstart;
3284 templhs.offset += fieldoffset;
3285 process_constraint (new_constraint (templhs, temprhs));
3289 /* Sometimes, frontends like to give us bad type information. This
3290 function will collapse all the fields from VAR to the end of VAR,
3291 into VAR, so that we treat those fields as a single variable.
3292 We return the variable they were collapsed into. */
3295 collapse_rest_of_var (unsigned int var)
3297 varinfo_t currvar = get_varinfo (var);
3300 for (field = currvar->next; field; field = field->next)
3303 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
3304 field->name, currvar->name);
3306 gcc_assert (field->collapsed_to == 0);
3307 field->collapsed_to = currvar->id;
3310 currvar->next = NULL;
3311 currvar->size = currvar->fullsize - currvar->offset;
3316 /* Handle aggregate copies by expanding into copies of the respective
3317 fields of the structures. */
3320 do_structure_copy (tree lhsop, tree rhsop)
3322 struct constraint_expr lhs, rhs, tmp;
3323 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3325 unsigned HOST_WIDE_INT lhssize;
3326 unsigned HOST_WIDE_INT rhssize;
3328 /* Pretend we are taking the address of the constraint exprs.
3329 We deal with walking the sub-fields ourselves. */
3330 get_constraint_for_1 (lhsop, &lhsc, true);
3331 get_constraint_for_1 (rhsop, &rhsc, true);
3332 gcc_assert (VEC_length (ce_s, lhsc) == 1);
3333 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3334 lhs = *(VEC_last (ce_s, lhsc));
3335 rhs = *(VEC_last (ce_s, rhsc));
3337 VEC_free (ce_s, heap, lhsc);
3338 VEC_free (ce_s, heap, rhsc);
3340 /* If we have special var = x, swap it around. */
3341 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
3348 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
3349 possible it's something we could handle. However, most cases falling
3350 into this are dealing with transparent unions, which are slightly
3352 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
3354 rhs.type = ADDRESSOF;
3355 rhs.var = anything_id;
3358 /* If the RHS is a special var, or an addressof, set all the LHS fields to
3359 that special var. */
3360 if (rhs.var <= integer_id)
3362 for (p = get_varinfo (lhs.var); p; p = p->next)
3364 struct constraint_expr templhs = lhs;
3365 struct constraint_expr temprhs = rhs;
3367 if (templhs.type == SCALAR )
3368 templhs.var = p->id;
3370 templhs.offset += p->offset;
3371 process_constraint (new_constraint (templhs, temprhs));
3376 tree rhstype = TREE_TYPE (rhsop);
3377 tree lhstype = TREE_TYPE (lhsop);
3381 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
3382 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
3384 /* If we have a variably sized types on the rhs or lhs, and a deref
3385 constraint, add the constraint, lhsconstraint = &ANYTHING.
3386 This is conservatively correct because either the lhs is an unknown
3387 sized var (if the constraint is SCALAR), or the lhs is a DEREF
3388 constraint, and every variable it can point to must be unknown sized
3389 anyway, so we don't need to worry about fields at all. */
3390 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
3391 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
3393 rhs.var = anything_id;
3394 rhs.type = ADDRESSOF;
3396 process_constraint (new_constraint (lhs, rhs));
3400 /* The size only really matters insofar as we don't set more or less of
3401 the variable. If we hit an unknown size var, the size should be the
3402 whole darn thing. */
3403 if (get_varinfo (rhs.var)->is_unknown_size_var)
3406 rhssize = TREE_INT_CST_LOW (rhstypesize);
3408 if (get_varinfo (lhs.var)->is_unknown_size_var)
3411 lhssize = TREE_INT_CST_LOW (lhstypesize);
3414 if (rhs.type == SCALAR && lhs.type == SCALAR)
3416 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
3418 lhs.var = collapse_rest_of_var (lhs.var);
3419 rhs.var = collapse_rest_of_var (rhs.var);
3424 process_constraint (new_constraint (lhs, rhs));
3427 else if (lhs.type != DEREF && rhs.type == DEREF)
3428 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3429 else if (lhs.type == DEREF && rhs.type != DEREF)
3430 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3433 tree pointedtotype = lhstype;
3436 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3437 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
3438 do_structure_copy (tmpvar, rhsop);
3439 do_structure_copy (lhsop, tmpvar);
3444 /* Create a constraint ID = OP. */
3447 make_constraint_to (unsigned id, tree op)
3449 VEC(ce_s, heap) *rhsc = NULL;
3450 struct constraint_expr *c;
3451 struct constraint_expr includes;
3455 includes.offset = 0;
3456 includes.type = SCALAR;
3458 get_constraint_for (op, &rhsc);
3459 for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3460 process_constraint (new_constraint (includes, *c));
3461 VEC_free (ce_s, heap, rhsc);
3464 /* Make constraints necessary to make OP escape. */
3467 make_escape_constraint (tree op)
3469 make_constraint_to (escaped_id, op);
3472 /* For non-IPA mode, generate constraints necessary for a call on the
3476 handle_rhs_call (gimple stmt)
3480 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3482 tree arg = gimple_call_arg (stmt, i);
3484 /* Find those pointers being passed, and make sure they end up
3485 pointing to anything. */
3486 if (could_have_pointers (arg))
3487 make_escape_constraint (arg);
3490 /* The static chain escapes as well. */
3491 if (gimple_call_chain (stmt))
3492 make_escape_constraint (gimple_call_chain (stmt));
3495 /* For non-IPA mode, generate constraints necessary for a call
3496 that returns a pointer and assigns it to LHS. This simply makes
3497 the LHS point to global and escaped variables. */
3500 handle_lhs_call (tree lhs, int flags)
3502 VEC(ce_s, heap) *lhsc = NULL;
3503 struct constraint_expr rhsc;
3505 struct constraint_expr *lhsp;
3507 get_constraint_for (lhs, &lhsc);
3509 if (flags & ECF_MALLOC)
3511 tree heapvar = heapvar_lookup (lhs);
3514 if (heapvar == NULL)
3516 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
3517 DECL_EXTERNAL (heapvar) = 1;
3518 get_var_ann (heapvar)->is_heapvar = 1;
3519 if (gimple_referenced_vars (cfun))
3520 add_referenced_var (heapvar);
3521 heapvar_insert (lhs, heapvar);
3524 rhsc.var = create_variable_info_for (heapvar,
3525 alias_get_name (heapvar));
3526 vi = get_varinfo (rhsc.var);
3527 vi->is_artificial_var = 1;
3528 vi->is_heap_var = 1;
3529 rhsc.type = ADDRESSOF;
3534 rhsc.var = escaped_id;
3536 rhsc.type = ADDRESSOF;
3538 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3539 process_constraint (new_constraint (*lhsp, rhsc));
3540 VEC_free (ce_s, heap, lhsc);
3543 /* For non-IPA mode, generate constraints necessary for a call of a
3544 const function that returns a pointer in the statement STMT. */
3547 handle_const_call (gimple stmt)
3549 tree lhs = gimple_call_lhs (stmt);
3550 VEC(ce_s, heap) *lhsc = NULL;
3551 struct constraint_expr rhsc;
3553 struct constraint_expr *lhsp;
3555 struct constraint_expr tmpc;
3557 get_constraint_for (lhs, &lhsc);
3559 /* If this is a nested function then it can return anything. */
3560 if (gimple_call_chain (stmt))
3562 rhsc.var = anything_id;
3564 rhsc.type = ADDRESSOF;
3565 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3566 process_constraint (new_constraint (*lhsp, rhsc));
3567 VEC_free (ce_s, heap, lhsc);
3571 /* We always use a temporary here, otherwise we end up with a quadratic
3572 amount of constraints for
3573 large_struct = const_call (large_struct);
3574 in field-sensitive PTA. */
3575 tmpvar = create_tmp_var_raw (ptr_type_node, "consttmp");
3576 tmpc = get_constraint_exp_for_temp (tmpvar);
3578 /* May return addresses of globals. */
3579 rhsc.var = nonlocal_id;
3581 rhsc.type = ADDRESSOF;
3582 process_constraint (new_constraint (tmpc, rhsc));
3584 /* May return arguments. */
3585 for (k = 0; k < gimple_call_num_args (stmt); ++k)
3587 tree arg = gimple_call_arg (stmt, k);
3589 if (could_have_pointers (arg))
3591 VEC(ce_s, heap) *argc = NULL;
3592 struct constraint_expr *argp;
3595 get_constraint_for (arg, &argc);
3596 for (i = 0; VEC_iterate (ce_s, argc, i, argp); i++)
3597 process_constraint (new_constraint (tmpc, *argp));
3598 VEC_free (ce_s, heap, argc);
3602 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3603 process_constraint (new_constraint (*lhsp, tmpc));
3605 VEC_free (ce_s, heap, lhsc);
3608 /* For non-IPA mode, generate constraints necessary for a call to a
3609 pure function in statement STMT. */
3612 handle_pure_call (gimple stmt)
3616 /* Memory reached from pointer arguments is call-used. */
3617 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3619 tree arg = gimple_call_arg (stmt, i);
3621 if (could_have_pointers (arg))
3622 make_constraint_to (callused_id, arg);
3625 /* The static chain is used as well. */
3626 if (gimple_call_chain (stmt))
3627 make_constraint_to (callused_id, gimple_call_chain (stmt));
3629 /* If the call returns a pointer it may point to reachable memory
3630 from the arguments. Not so for malloc functions though. */
3631 if (gimple_call_lhs (stmt)
3632 && could_have_pointers (gimple_call_lhs (stmt))
3633 && !(gimple_call_flags (stmt) & ECF_MALLOC))
3635 tree lhs = gimple_call_lhs (stmt);
3636 VEC(ce_s, heap) *lhsc = NULL;
3637 struct constraint_expr rhsc;
3638 struct constraint_expr *lhsp;
3641 get_constraint_for (lhs, &lhsc);
3643 /* If this is a nested function then it can return anything. */
3644 if (gimple_call_chain (stmt))
3646 rhsc.var = anything_id;
3648 rhsc.type = ADDRESSOF;
3649 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3650 process_constraint (new_constraint (*lhsp, rhsc));
3651 VEC_free (ce_s, heap, lhsc);
3655 /* Else just add the call-used memory here. Escaped variables
3656 and globals will be dealt with in handle_lhs_call. */
3657 rhsc.var = callused_id;
3659 rhsc.type = ADDRESSOF;
3660 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3661 process_constraint (new_constraint (*lhsp, rhsc));
3662 VEC_free (ce_s, heap, lhsc);
3666 /* Walk statement T setting up aliasing constraints according to the
3667 references found in T. This function is the main part of the
3668 constraint builder. AI points to auxiliary alias information used
3669 when building alias sets and computing alias grouping heuristics. */
3672 find_func_aliases (gimple origt)
3675 VEC(ce_s, heap) *lhsc = NULL;
3676 VEC(ce_s, heap) *rhsc = NULL;
3677 struct constraint_expr *c;
3678 enum escape_type stmt_escape_type;
3680 /* Now build constraints expressions. */
3681 if (gimple_code (t) == GIMPLE_PHI)
3683 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (gimple_phi_result (t))));
3685 /* Only care about pointers and structures containing
3687 if (could_have_pointers (gimple_phi_result (t)))
3692 /* For a phi node, assign all the arguments to
3694 get_constraint_for (gimple_phi_result (t), &lhsc);
3695 for (i = 0; i < gimple_phi_num_args (t); i++)
3698 tree strippedrhs = PHI_ARG_DEF (t, i);
3700 STRIP_NOPS (strippedrhs);
3701 rhstype = TREE_TYPE (strippedrhs);
3702 get_constraint_for (gimple_phi_arg_def (t, i), &rhsc);
3704 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3706 struct constraint_expr *c2;
3707 while (VEC_length (ce_s, rhsc) > 0)
3709 c2 = VEC_last (ce_s, rhsc);
3710 process_constraint (new_constraint (*c, *c2));
3711 VEC_pop (ce_s, rhsc);
3717 /* In IPA mode, we need to generate constraints to pass call
3718 arguments through their calls. There are two cases,
3719 either a GIMPLE_CALL returning a value, or just a plain
3720 GIMPLE_CALL when we are not.
3722 In non-ipa mode, we need to generate constraints for each
3723 pointer passed by address. */
3724 else if (is_gimple_call (t))
3728 int flags = gimple_call_flags (t);
3730 /* Const functions can return their arguments and addresses
3731 of global memory but not of escaped memory. */
3732 if (flags & ECF_CONST)
3734 if (gimple_call_lhs (t)
3735 && could_have_pointers (gimple_call_lhs (t)))
3736 handle_const_call (t);
3738 /* Pure functions can return addresses in and of memory
3739 reachable from their arguments, but they are not an escape
3740 point for reachable memory of their arguments. */
3741 else if (flags & ECF_PURE)
3743 handle_pure_call (t);
3744 if (gimple_call_lhs (t)
3745 && could_have_pointers (gimple_call_lhs (t)))
3746 handle_lhs_call (gimple_call_lhs (t), flags);
3750 handle_rhs_call (t);
3751 if (gimple_call_lhs (t)
3752 && could_have_pointers (gimple_call_lhs (t)))
3753 handle_lhs_call (gimple_call_lhs (t), flags);
3764 lhsop = gimple_call_lhs (t);
3765 decl = gimple_call_fndecl (t);
3767 /* If we can directly resolve the function being called, do so.
3768 Otherwise, it must be some sort of indirect expression that
3769 we should still be able to handle. */
3771 fi = get_vi_for_tree (decl);
3774 decl = gimple_call_fn (t);
3775 fi = get_vi_for_tree (decl);
3778 /* Assign all the passed arguments to the appropriate incoming
3779 parameters of the function. */
3780 for (j = 0; j < gimple_call_num_args (t); j++)
3782 struct constraint_expr lhs ;
3783 struct constraint_expr *rhsp;
3784 tree arg = gimple_call_arg (t, j);
3786 get_constraint_for (arg, &rhsc);
3787 if (TREE_CODE (decl) != FUNCTION_DECL)
3796 lhs.var = first_vi_for_offset (fi, i)->id;
3799 while (VEC_length (ce_s, rhsc) != 0)
3801 rhsp = VEC_last (ce_s, rhsc);
3802 process_constraint (new_constraint (lhs, *rhsp));
3803 VEC_pop (ce_s, rhsc);
3808 /* If we are returning a value, assign it to the result. */
3811 struct constraint_expr rhs;
3812 struct constraint_expr *lhsp;
3815 get_constraint_for (lhsop, &lhsc);
3816 if (TREE_CODE (decl) != FUNCTION_DECL)
3825 rhs.var = first_vi_for_offset (fi, i)->id;
3828 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3829 process_constraint (new_constraint (*lhsp, rhs));
3833 /* Otherwise, just a regular assignment statement. Only care about
3834 operations with pointer result, others are dealt with as escape
3835 points if they have pointer operands. */
3836 else if (is_gimple_assign (t)
3837 && could_have_pointers (gimple_assign_lhs (t)))
3839 /* Otherwise, just a regular assignment statement. */
3840 tree lhsop = gimple_assign_lhs (t);
3841 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
3843 if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
3844 do_structure_copy (lhsop, rhsop);
3848 struct constraint_expr temp;
3849 get_constraint_for (lhsop, &lhsc);
3851 if (gimple_assign_rhs_code (t) == POINTER_PLUS_EXPR)
3852 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
3853 gimple_assign_rhs2 (t), &rhsc);
3854 else if ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
3855 && !(POINTER_TYPE_P (gimple_expr_type (t))
3856 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
3857 || gimple_assign_single_p (t))
3858 get_constraint_for (rhsop, &rhsc);
3861 temp.type = ADDRESSOF;
3862 temp.var = anything_id;
3864 VEC_safe_push (ce_s, heap, rhsc, &temp);
3866 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3868 struct constraint_expr *c2;
3871 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3872 process_constraint (new_constraint (*c, *c2));
3876 else if (gimple_code (t) == GIMPLE_CHANGE_DYNAMIC_TYPE)
3880 get_constraint_for (gimple_cdt_location (t), &lhsc);
3881 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); ++j)
3882 get_varinfo (c->var)->no_tbaa_pruning = true;
3885 stmt_escape_type = is_escape_site (t);
3886 if (stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
3888 gcc_assert (is_gimple_assign (t));
3889 if (gimple_assign_rhs_code (t) == ADDR_EXPR)
3891 tree rhs = gimple_assign_rhs1 (t);
3892 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3895 || !is_global_var (base)))
3896 make_escape_constraint (rhs);
3898 else if (get_gimple_rhs_class (gimple_assign_rhs_code (t))
3899 == GIMPLE_SINGLE_RHS)
3901 if (could_have_pointers (gimple_assign_rhs1 (t)))
3902 make_escape_constraint (gimple_assign_rhs1 (t));
3907 else if (stmt_escape_type == ESCAPE_BAD_CAST)
3909 gcc_assert (is_gimple_assign (t));
3910 gcc_assert (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
3911 || gimple_assign_rhs_code (t) == VIEW_CONVERT_EXPR);
3912 make_escape_constraint (gimple_assign_rhs1 (t));
3914 else if (stmt_escape_type == ESCAPE_TO_ASM)
3917 for (i = 0; i < gimple_asm_noutputs (t); ++i)
3919 tree op = TREE_VALUE (gimple_asm_output_op (t, i));
3920 if (op && could_have_pointers (op))
3921 /* Strictly we'd only need the constraints from ESCAPED and
3923 make_escape_constraint (op);
3925 for (i = 0; i < gimple_asm_ninputs (t); ++i)
3927 tree op = TREE_VALUE (gimple_asm_input_op (t, i));
3928 if (op && could_have_pointers (op))
3929 /* Strictly we'd only need the constraint to ESCAPED. */
3930 make_escape_constraint (op);
3934 /* After promoting variables and computing aliasing we will
3935 need to re-scan most statements. FIXME: Try to minimize the
3936 number of statements re-scanned. It's not really necessary to
3937 re-scan *all* statements. */
3939 gimple_set_modified (origt, true);
3940 VEC_free (ce_s, heap, rhsc);
3941 VEC_free (ce_s, heap, lhsc);
3945 /* Find the first varinfo in the same variable as START that overlaps with
3947 Effectively, walk the chain of fields for the variable START to find the
3948 first field that overlaps with OFFSET.
3949 Return NULL if we can't find one. */
3952 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3954 varinfo_t curr = start;
3957 /* We may not find a variable in the field list with the actual
3958 offset when when we have glommed a structure to a variable.
3959 In that case, however, offset should still be within the size
3961 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3969 /* Insert the varinfo FIELD into the field list for BASE, at the front
3973 insert_into_field_list (varinfo_t base, varinfo_t field)
3975 varinfo_t prev = base;
3976 varinfo_t curr = base->next;
3982 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3986 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
3988 varinfo_t prev = base;
3989 varinfo_t curr = base->next;
4000 if (field->offset <= curr->offset)
4005 field->next = prev->next;
4010 /* This structure is used during pushing fields onto the fieldstack
4011 to track the offset of the field, since bitpos_of_field gives it
4012 relative to its immediate containing type, and we want it relative
4013 to the ultimate containing object. */
4017 /* Offset from the base of the base containing object to this field. */
4018 HOST_WIDE_INT offset;
4020 /* Size, in bits, of the field. */
4021 unsigned HOST_WIDE_INT size;
4023 unsigned has_unknown_size : 1;
4025 unsigned may_have_pointers : 1;
4027 typedef struct fieldoff fieldoff_s;
4029 DEF_VEC_O(fieldoff_s);
4030 DEF_VEC_ALLOC_O(fieldoff_s,heap);
4032 /* qsort comparison function for two fieldoff's PA and PB */
4035 fieldoff_compare (const void *pa, const void *pb)
4037 const fieldoff_s *foa = (const fieldoff_s *)pa;
4038 const fieldoff_s *fob = (const fieldoff_s *)pb;
4039 unsigned HOST_WIDE_INT foasize, fobsize;
4041 if (foa->offset < fob->offset)
4043 else if (foa->offset > fob->offset)
4046 foasize = foa->size;
4047 fobsize = fob->size;
4048 if (foasize < fobsize)
4050 else if (foasize > fobsize)
4055 /* Sort a fieldstack according to the field offset and sizes. */
4057 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
4059 qsort (VEC_address (fieldoff_s, fieldstack),
4060 VEC_length (fieldoff_s, fieldstack),
4061 sizeof (fieldoff_s),
4065 /* Return true if V is a tree that we can have subvars for.
4066 Normally, this is any aggregate type. Also complex
4067 types which are not gimple registers can have subvars. */
4070 var_can_have_subvars (const_tree v)
4072 /* Volatile variables should never have subvars. */
4073 if (TREE_THIS_VOLATILE (v))
4076 /* Non decls or memory tags can never have subvars. */
4077 if (!DECL_P (v) || MTAG_P (v))
4080 /* Aggregates without overlapping fields can have subvars. */
4081 if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
4087 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4088 the fields of TYPE onto fieldstack, recording their offsets along
4091 OFFSET is used to keep track of the offset in this entire
4092 structure, rather than just the immediately containing structure.
4093 Returns the number of fields pushed. */
4096 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
4097 HOST_WIDE_INT offset)
4102 if (TREE_CODE (type) != RECORD_TYPE)
4105 /* If the vector of fields is growing too big, bail out early.
4106 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4108 if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
4111 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
4112 if (TREE_CODE (field) == FIELD_DECL)
4116 HOST_WIDE_INT foff = bitpos_of_field (field);
4118 if (!var_can_have_subvars (field)
4119 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
4120 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
4122 else if (!(pushed = push_fields_onto_fieldstack
4123 (TREE_TYPE (field), fieldstack, offset + foff))
4124 && (DECL_SIZE (field)
4125 && !integer_zerop (DECL_SIZE (field))))
4126 /* Empty structures may have actual size, like in C++. So
4127 see if we didn't push any subfields and the size is
4128 nonzero, push the field onto the stack. */
4133 fieldoff_s *pair = NULL;
4134 bool has_unknown_size = false;
4136 if (!VEC_empty (fieldoff_s, *fieldstack))
4137 pair = VEC_last (fieldoff_s, *fieldstack);
4139 if (!DECL_SIZE (field)
4140 || !host_integerp (DECL_SIZE (field), 1))
4141 has_unknown_size = true;
4143 /* If adjacent fields do not contain pointers merge them. */
4145 && !pair->may_have_pointers
4146 && !could_have_pointers (field)
4147 && !pair->has_unknown_size
4148 && !has_unknown_size
4149 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
4151 pair = VEC_last (fieldoff_s, *fieldstack);
4152 pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
4156 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
4157 pair->offset = offset + foff;
4158 pair->has_unknown_size = has_unknown_size;
4159 if (!has_unknown_size)
4160 pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
4163 pair->may_have_pointers = could_have_pointers (field);
4174 /* Create a constraint ID = &FROM. */
4177 make_constraint_from (varinfo_t vi, int from)
4179 struct constraint_expr lhs, rhs;
4187 rhs.type = ADDRESSOF;
4188 process_constraint (new_constraint (lhs, rhs));
4191 /* Count the number of arguments DECL has, and set IS_VARARGS to true
4192 if it is a varargs function. */
4195 count_num_arguments (tree decl, bool *is_varargs)
4200 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
4204 if (TREE_VALUE (t) == void_type_node)
4214 /* Creation function node for DECL, using NAME, and return the index
4215 of the variable we've created for the function. */
4218 create_function_info_for (tree decl, const char *name)
4220 unsigned int index = VEC_length (varinfo_t, varmap);
4224 bool is_varargs = false;
4226 /* Create the variable info. */
4228 vi = new_var_info (decl, index, name);
4232 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
4233 insert_vi_for_tree (vi->decl, vi);
4234 VEC_safe_push (varinfo_t, heap, varmap, vi);
4238 /* If it's varargs, we don't know how many arguments it has, so we
4244 vi->is_unknown_size_var = true;
4249 arg = DECL_ARGUMENTS (decl);
4251 /* Set up variables for each argument. */
4252 for (i = 1; i < vi->fullsize; i++)
4255 const char *newname;
4257 unsigned int newindex;
4258 tree argdecl = decl;
4263 newindex = VEC_length (varinfo_t, varmap);
4264 asprintf (&tempname, "%s.arg%d", name, i-1);
4265 newname = ggc_strdup (tempname);
4268 argvi = new_var_info (argdecl, newindex, newname);
4269 argvi->decl = argdecl;
4270 VEC_safe_push (varinfo_t, heap, varmap, argvi);
4273 argvi->is_full_var = true;
4274 argvi->fullsize = vi->fullsize;
4275 insert_into_field_list_sorted (vi, argvi);
4276 stats.total_vars ++;
4279 insert_vi_for_tree (arg, argvi);
4280 arg = TREE_CHAIN (arg);
4284 /* Create a variable for the return var. */
4285 if (DECL_RESULT (decl) != NULL
4286 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
4289 const char *newname;
4291 unsigned int newindex;
4292 tree resultdecl = decl;
4296 if (DECL_RESULT (decl))
4297 resultdecl = DECL_RESULT (decl);
4299 newindex = VEC_length (varinfo_t, varmap);
4300 asprintf (&tempname, "%s.result", name);
4301 newname = ggc_strdup (tempname);
4304 resultvi = new_var_info (resultdecl, newindex, newname);
4305 resultvi->decl = resultdecl;
4306 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
4307 resultvi->offset = i;
4309 resultvi->fullsize = vi->fullsize;
4310 resultvi->is_full_var = true;
4311 insert_into_field_list_sorted (vi, resultvi);
4312 stats.total_vars ++;
4313 if (DECL_RESULT (decl))
4314 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
4320 /* Return true if FIELDSTACK contains fields that overlap.
4321 FIELDSTACK is assumed to be sorted by offset. */
4324 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
4326 fieldoff_s *fo = NULL;
4328 HOST_WIDE_INT lastoffset = -1;
4330 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4332 if (fo->offset == lastoffset)
4334 lastoffset = fo->offset;
4339 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4340 This will also create any varinfo structures necessary for fields
4344 create_variable_info_for (tree decl, const char *name)
4346 unsigned int index = VEC_length (varinfo_t, varmap);
4348 tree decl_type = TREE_TYPE (decl);
4349 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
4350 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
4351 VEC (fieldoff_s,heap) *fieldstack = NULL;
4353 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4354 return create_function_info_for (decl, name);
4356 if (var_can_have_subvars (decl) && use_field_sensitive
4358 || var_ann (decl)->noalias_state == 0)
4360 || !var_ann (decl)->is_heapvar))
4361 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
4363 /* If the variable doesn't have subvars, we may end up needing to
4364 sort the field list and create fake variables for all the
4366 vi = new_var_info (decl, index, name);
4370 || !host_integerp (declsize, 1))
4372 vi->is_unknown_size_var = true;
4378 vi->fullsize = TREE_INT_CST_LOW (declsize);
4379 vi->size = vi->fullsize;
4382 insert_vi_for_tree (vi->decl, vi);
4383 VEC_safe_push (varinfo_t, heap, varmap, vi);
4384 if (is_global && (!flag_whole_program || !in_ipa_mode)
4385 && could_have_pointers (decl))
4388 && var_ann (decl)->noalias_state == NO_ALIAS_ANYTHING)
4389 make_constraint_from (vi, vi->id);
4391 make_constraint_from (vi, escaped_id);
4395 if (use_field_sensitive
4396 && !vi->is_unknown_size_var
4397 && var_can_have_subvars (decl)
4398 && VEC_length (fieldoff_s, fieldstack) > 1
4399 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4401 unsigned int newindex = VEC_length (varinfo_t, varmap);
4402 fieldoff_s *fo = NULL;
4403 bool notokay = false;
4406 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4408 if (fo->has_unknown_size
4416 /* We can't sort them if we have a field with a variable sized type,
4417 which will make notokay = true. In that case, we are going to return
4418 without creating varinfos for the fields anyway, so sorting them is a
4422 sort_fieldstack (fieldstack);
4423 /* Due to some C++ FE issues, like PR 22488, we might end up
4424 what appear to be overlapping fields even though they,
4425 in reality, do not overlap. Until the C++ FE is fixed,
4426 we will simply disable field-sensitivity for these cases. */
4427 notokay = check_for_overlaps (fieldstack);
4431 if (VEC_length (fieldoff_s, fieldstack) != 0)
4432 fo = VEC_index (fieldoff_s, fieldstack, 0);
4434 if (fo == NULL || notokay)
4436 vi->is_unknown_size_var = 1;
4439 vi->is_full_var = true;
4440 VEC_free (fieldoff_s, heap, fieldstack);
4444 vi->size = fo->size;
4445 vi->offset = fo->offset;
4446 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4447 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4451 const char *newname = "NULL";
4454 newindex = VEC_length (varinfo_t, varmap);
4457 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
4458 "+" HOST_WIDE_INT_PRINT_DEC,
4459 vi->name, fo->offset, fo->size);
4460 newname = ggc_strdup (tempname);
4463 newvi = new_var_info (decl, newindex, newname);
4464 newvi->offset = fo->offset;
4465 newvi->size = fo->size;
4466 newvi->fullsize = vi->fullsize;
4467 insert_into_field_list (vi, newvi);
4468 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4469 if (is_global && (!flag_whole_program || !in_ipa_mode)
4470 && fo->may_have_pointers)
4471 make_constraint_from (newvi, escaped_id);
4477 vi->is_full_var = true;
4479 VEC_free (fieldoff_s, heap, fieldstack);
4484 /* Print out the points-to solution for VAR to FILE. */
4487 dump_solution_for_var (FILE *file, unsigned int var)
4489 varinfo_t vi = get_varinfo (var);
4493 if (find (var) != var)
4495 varinfo_t vipt = get_varinfo (find (var));
4496 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4500 fprintf (file, "%s = { ", vi->name);
4501 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4503 fprintf (file, "%s ", get_varinfo (i)->name);
4505 fprintf (file, "}");
4506 if (vi->no_tbaa_pruning)
4507 fprintf (file, " no-tbaa-pruning");
4508 fprintf (file, "\n");
4512 /* Print the points-to solution for VAR to stdout. */
4515 debug_solution_for_var (unsigned int var)
4517 dump_solution_for_var (stdout, var);
4520 /* Create varinfo structures for all of the variables in the
4521 function for intraprocedural mode. */
4524 intra_create_variable_infos (void)
4527 struct constraint_expr lhs, rhs;
4529 /* For each incoming pointer argument arg, create the constraint ARG
4530 = NONLOCAL or a dummy variable if flag_argument_noalias is set. */
4531 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4535 if (!could_have_pointers (t))
4538 /* If flag_argument_noalias is set, then function pointer
4539 arguments are guaranteed not to point to each other. In that
4540 case, create an artificial variable PARM_NOALIAS and the
4541 constraint ARG = &PARM_NOALIAS. */
4542 if (POINTER_TYPE_P (TREE_TYPE (t)) && flag_argument_noalias > 0)
4545 tree heapvar = heapvar_lookup (t);
4549 lhs.var = get_vi_for_tree (t)->id;
4551 if (heapvar == NULL_TREE)
4554 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4556 DECL_EXTERNAL (heapvar) = 1;
4557 if (gimple_referenced_vars (cfun))
4558 add_referenced_var (heapvar);
4560 heapvar_insert (t, heapvar);
4562 ann = get_var_ann (heapvar);
4563 ann->is_heapvar = 1;
4564 if (flag_argument_noalias == 1)
4565 ann->noalias_state = NO_ALIAS;
4566 else if (flag_argument_noalias == 2)
4567 ann->noalias_state = NO_ALIAS_GLOBAL;
4568 else if (flag_argument_noalias == 3)
4569 ann->noalias_state = NO_ALIAS_ANYTHING;
4574 vi = get_vi_for_tree (heapvar);
4575 vi->is_artificial_var = 1;
4576 vi->is_heap_var = 1;
4578 rhs.type = ADDRESSOF;
4580 for (p = get_varinfo (lhs.var); p; p = p->next)
4582 struct constraint_expr temp = lhs;
4584 process_constraint (new_constraint (temp, rhs));
4589 varinfo_t arg_vi = get_vi_for_tree (t);
4591 for (p = arg_vi; p; p = p->next)
4592 make_constraint_from (p, nonlocal_id);
4597 /* Structure used to put solution bitmaps in a hashtable so they can
4598 be shared among variables with the same points-to set. */
4600 typedef struct shared_bitmap_info
4604 } *shared_bitmap_info_t;
4605 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
4607 static htab_t shared_bitmap_table;
4609 /* Hash function for a shared_bitmap_info_t */
4612 shared_bitmap_hash (const void *p)
4614 const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
4615 return bi->hashcode;
4618 /* Equality function for two shared_bitmap_info_t's. */
4621 shared_bitmap_eq (const void *p1, const void *p2)
4623 const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
4624 const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
4625 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
4628 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4629 existing instance if there is one, NULL otherwise. */
4632 shared_bitmap_lookup (bitmap pt_vars)
4635 struct shared_bitmap_info sbi;
4637 sbi.pt_vars = pt_vars;
4638 sbi.hashcode = bitmap_hash (pt_vars);
4640 slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
4641 sbi.hashcode, NO_INSERT);
4645 return ((shared_bitmap_info_t) *slot)->pt_vars;
4649 /* Add a bitmap to the shared bitmap hashtable. */
4652 shared_bitmap_add (bitmap pt_vars)
4655 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
4657 sbi->pt_vars = pt_vars;
4658 sbi->hashcode = bitmap_hash (pt_vars);
4660 slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
4661 sbi->hashcode, INSERT);
4662 gcc_assert (!*slot);
4663 *slot = (void *) sbi;
4667 /* Set bits in INTO corresponding to the variable uids in solution set
4668 FROM, which came from variable PTR.
4669 For variables that are actually dereferenced, we also use type
4670 based alias analysis to prune the points-to sets.
4671 IS_DEREFED is true if PTR was directly dereferenced, which we use to
4672 help determine whether we are we are allowed to prune using TBAA.
4673 If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of
4677 set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed,
4678 bool no_tbaa_pruning)
4683 gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
4685 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4687 varinfo_t vi = get_varinfo (i);
4689 /* The only artificial variables that are allowed in a may-alias
4690 set are heap variables. */
4691 if (vi->is_artificial_var && !vi->is_heap_var)
4694 if (TREE_CODE (vi->decl) == VAR_DECL
4695 || TREE_CODE (vi->decl) == PARM_DECL
4696 || TREE_CODE (vi->decl) == RESULT_DECL)
4698 /* Just add VI->DECL to the alias set.
4699 Don't type prune artificial vars or points-to sets
4700 for pointers that have not been dereferenced or with
4701 type-based pruning disabled. */
4702 if (vi->is_artificial_var
4705 bitmap_set_bit (into, DECL_UID (vi->decl));
4708 alias_set_type var_alias_set, mem_alias_set;
4709 var_alias_set = get_alias_set (vi->decl);
4710 mem_alias_set = get_alias_set (TREE_TYPE (TREE_TYPE (ptr)));
4711 if (may_alias_p (SSA_NAME_VAR (ptr), mem_alias_set,
4712 vi->decl, var_alias_set, true))
4713 bitmap_set_bit (into, DECL_UID (vi->decl));
4720 static bool have_alias_info = false;
4722 /* Given a pointer variable P, fill in its points-to set, or return
4724 Rather than return false for variables that point-to anything, we
4725 instead find the corresponding SMT, and merge in its aliases. In
4726 addition to these aliases, we also set the bits for the SMT's
4727 themselves and their subsets, as SMT's are still in use by
4728 non-SSA_NAME's, and pruning may eliminate every one of their
4729 aliases. In such a case, if we did not include the right set of
4730 SMT's in the points-to set of the variable, we'd end up with
4731 statements that do not conflict but should. */
4734 find_what_p_points_to (tree p)
4739 if (!have_alias_info)
4742 /* For parameters, get at the points-to set for the actual parm
4744 if (TREE_CODE (p) == SSA_NAME
4745 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4746 && SSA_NAME_IS_DEFAULT_DEF (p))
4747 lookup_p = SSA_NAME_VAR (p);
4749 vi = lookup_vi_for_tree (lookup_p);
4752 if (vi->is_artificial_var)
4755 /* See if this is a field or a structure. */
4756 if (vi->size != vi->fullsize)
4758 /* Nothing currently asks about structure fields directly,
4759 but when they do, we need code here to hand back the
4765 struct ptr_info_def *pi = get_ptr_info (p);
4768 bool was_pt_anything = false;
4769 bitmap finished_solution;
4772 if (!pi->memory_tag_needed)
4775 /* This variable may have been collapsed, let's get the real
4777 vi = get_varinfo (find (vi->id));
4779 /* Translate artificial variables into SSA_NAME_PTR_INFO
4781 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4783 varinfo_t vi = get_varinfo (i);
4785 if (vi->is_artificial_var)
4787 /* FIXME. READONLY should be handled better so that
4788 flow insensitive aliasing can disregard writable
4790 if (vi->id == nothing_id)
4792 else if (vi->id == anything_id
4793 || vi->id == nonlocal_id
4794 || vi->id == escaped_id
4795 || vi->id == callused_id)
4796 was_pt_anything = 1;
4797 else if (vi->id == readonly_id)
4798 was_pt_anything = 1;
4799 else if (vi->id == integer_id)
4800 was_pt_anything = 1;
4801 else if (vi->is_heap_var)
4802 pi->pt_global_mem = 1;
4806 /* Instead of doing extra work, simply do not create
4807 points-to information for pt_anything pointers. This
4808 will cause the operand scanner to fall back to the
4809 type-based SMT and its aliases. Which is the best
4810 we could do here for the points-to set as well. */
4811 if (was_pt_anything)
4814 /* Share the final set of variables when possible. */
4815 finished_solution = BITMAP_GGC_ALLOC ();
4816 stats.points_to_sets_created++;
4818 set_uids_in_ptset (p, finished_solution, vi->solution,
4819 pi->is_dereferenced,
4820 vi->no_tbaa_pruning);
4821 result = shared_bitmap_lookup (finished_solution);
4825 shared_bitmap_add (finished_solution);
4826 pi->pt_vars = finished_solution;
4830 pi->pt_vars = result;
4831 bitmap_clear (finished_solution);
4834 if (bitmap_empty_p (pi->pt_vars))
4844 /* Mark the ESCAPED solution as call clobbered. Returns false if
4845 pt_anything escaped which needs all locals that have their address
4846 taken marked call clobbered as well. */
4849 clobber_what_escaped (void)
4855 if (!have_alias_info)
4858 /* This variable may have been collapsed, let's get the real
4859 variable for escaped_id. */
4860 vi = get_varinfo (find (escaped_id));
4862 /* If call-used memory escapes we need to include it in the
4863 set of escaped variables. This can happen if a pure
4864 function returns a pointer and this pointer escapes. */
4865 if (bitmap_bit_p (vi->solution, callused_id))
4867 varinfo_t cu_vi = get_varinfo (find (callused_id));
4868 bitmap_ior_into (vi->solution, cu_vi->solution);
4871 /* Mark variables in the solution call-clobbered. */
4872 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4874 varinfo_t vi = get_varinfo (i);
4876 if (vi->is_artificial_var)
4878 /* nothing_id and readonly_id do not cause any
4879 call clobber ops. For anything_id and integer_id
4880 we need to clobber all addressable vars. */
4881 if (vi->id == anything_id
4882 || vi->id == integer_id)
4886 /* Only artificial heap-vars are further interesting. */
4887 if (vi->is_artificial_var && !vi->is_heap_var)
4890 if ((TREE_CODE (vi->decl) == VAR_DECL
4891 || TREE_CODE (vi->decl) == PARM_DECL
4892 || TREE_CODE (vi->decl) == RESULT_DECL)
4893 && !unmodifiable_var_p (vi->decl))
4894 mark_call_clobbered (vi->decl, ESCAPE_TO_CALL);
4900 /* Compute the call-used variables. */
4903 compute_call_used_vars (void)
4908 bool has_anything_id = false;
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 (callused_id));
4917 /* Mark variables in the solution call-clobbered. */
4918 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4920 varinfo_t vi = get_varinfo (i);
4922 if (vi->is_artificial_var)
4924 /* For anything_id and integer_id we need to make
4925 all local addressable vars call-used. */
4926 if (vi->id == anything_id
4927 || vi->id == integer_id)
4928 has_anything_id = true;
4931 /* Only artificial heap-vars are further interesting. */
4932 if (vi->is_artificial_var && !vi->is_heap_var)
4935 if ((TREE_CODE (vi->decl) == VAR_DECL
4936 || TREE_CODE (vi->decl) == PARM_DECL
4937 || TREE_CODE (vi->decl) == RESULT_DECL)
4938 && !unmodifiable_var_p (vi->decl))
4939 bitmap_set_bit (gimple_call_used_vars (cfun), DECL_UID (vi->decl));
4942 /* If anything is call-used, add all addressable locals to the set. */
4943 if (has_anything_id)
4944 bitmap_ior_into (gimple_call_used_vars (cfun),
4945 gimple_addressable_vars (cfun));
4949 /* Dump points-to information to OUTFILE. */
4952 dump_sa_points_to_info (FILE *outfile)
4956 fprintf (outfile, "\nPoints-to sets\n\n");
4958 if (dump_flags & TDF_STATS)
4960 fprintf (outfile, "Stats:\n");
4961 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4962 fprintf (outfile, "Non-pointer vars: %d\n",
4963 stats.nonpointer_vars);
4964 fprintf (outfile, "Statically unified vars: %d\n",
4965 stats.unified_vars_static);
4966 fprintf (outfile, "Dynamically unified vars: %d\n",
4967 stats.unified_vars_dynamic);
4968 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4969 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4970 fprintf (outfile, "Number of implicit edges: %d\n",
4971 stats.num_implicit_edges);
4974 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4975 dump_solution_for_var (outfile, i);
4979 /* Debug points-to information to stderr. */
4982 debug_sa_points_to_info (void)
4984 dump_sa_points_to_info (stderr);
4988 /* Initialize the always-existing constraint variables for NULL
4989 ANYTHING, READONLY, and INTEGER */
4992 init_base_vars (void)
4994 struct constraint_expr lhs, rhs;
4996 /* Create the NULL variable, used to represent that a variable points
4998 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4999 var_nothing = new_var_info (nothing_tree, nothing_id, "NULL");
5000 insert_vi_for_tree (nothing_tree, var_nothing);
5001 var_nothing->is_artificial_var = 1;
5002 var_nothing->offset = 0;
5003 var_nothing->size = ~0;
5004 var_nothing->fullsize = ~0;
5005 var_nothing->is_special_var = 1;
5006 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
5008 /* Create the ANYTHING variable, used to represent that a variable
5009 points to some unknown piece of memory. */
5010 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
5011 var_anything = new_var_info (anything_tree, anything_id, "ANYTHING");
5012 insert_vi_for_tree (anything_tree, var_anything);
5013 var_anything->is_artificial_var = 1;
5014 var_anything->size = ~0;
5015 var_anything->offset = 0;
5016 var_anything->next = NULL;
5017 var_anything->fullsize = ~0;
5018 var_anything->is_special_var = 1;
5020 /* Anything points to anything. This makes deref constraints just
5021 work in the presence of linked list and other p = *p type loops,
5022 by saying that *ANYTHING = ANYTHING. */
5023 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
5025 lhs.var = anything_id;
5027 rhs.type = ADDRESSOF;
5028 rhs.var = anything_id;
5031 /* This specifically does not use process_constraint because
5032 process_constraint ignores all anything = anything constraints, since all
5033 but this one are redundant. */
5034 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
5036 /* Create the READONLY variable, used to represent that a variable
5037 points to readonly memory. */
5038 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
5039 var_readonly = new_var_info (readonly_tree, readonly_id, "READONLY");
5040 var_readonly->is_artificial_var = 1;
5041 var_readonly->offset = 0;
5042 var_readonly->size = ~0;
5043 var_readonly->fullsize = ~0;
5044 var_readonly->next = NULL;
5045 var_readonly->is_special_var = 1;
5046 insert_vi_for_tree (readonly_tree, var_readonly);
5047 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
5049 /* readonly memory points to anything, in order to make deref
5050 easier. In reality, it points to anything the particular
5051 readonly variable can point to, but we don't track this
5054 lhs.var = readonly_id;
5056 rhs.type = ADDRESSOF;
5057 rhs.var = readonly_id; /* FIXME */
5059 process_constraint (new_constraint (lhs, rhs));
5061 /* Create the ESCAPED variable, used to represent the set of escaped
5063 escaped_tree = create_tmp_var_raw (void_type_node, "ESCAPED");
5064 var_escaped = new_var_info (escaped_tree, escaped_id, "ESCAPED");
5065 insert_vi_for_tree (escaped_tree, var_escaped);
5066 var_escaped->is_artificial_var = 1;
5067 var_escaped->offset = 0;
5068 var_escaped->size = ~0;
5069 var_escaped->fullsize = ~0;
5070 var_escaped->is_special_var = 0;
5071 VEC_safe_push (varinfo_t, heap, varmap, var_escaped);
5072 gcc_assert (VEC_index (varinfo_t, varmap, 3) == var_escaped);
5074 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
5076 lhs.var = escaped_id;
5079 rhs.var = escaped_id;
5081 process_constraint (new_constraint (lhs, rhs));
5083 /* Create the NONLOCAL variable, used to represent the set of nonlocal
5085 nonlocal_tree = create_tmp_var_raw (void_type_node, "NONLOCAL");
5086 var_nonlocal = new_var_info (nonlocal_tree, nonlocal_id, "NONLOCAL");
5087 insert_vi_for_tree (nonlocal_tree, var_nonlocal);
5088 var_nonlocal->is_artificial_var = 1;
5089 var_nonlocal->offset = 0;
5090 var_nonlocal->size = ~0;
5091 var_nonlocal->fullsize = ~0;
5092 var_nonlocal->is_special_var = 1;
5093 VEC_safe_push (varinfo_t, heap, varmap, var_nonlocal);
5095 /* Nonlocal memory points to escaped (which includes nonlocal),
5096 in order to make deref easier. */
5098 lhs.var = nonlocal_id;
5100 rhs.type = ADDRESSOF;
5101 rhs.var = escaped_id;
5103 process_constraint (new_constraint (lhs, rhs));
5105 /* Create the CALLUSED variable, used to represent the set of call-used
5107 callused_tree = create_tmp_var_raw (void_type_node, "CALLUSED");
5108 var_callused = new_var_info (callused_tree, callused_id, "CALLUSED");
5109 insert_vi_for_tree (callused_tree, var_callused);
5110 var_callused->is_artificial_var = 1;
5111 var_callused->offset = 0;
5112 var_callused->size = ~0;
5113 var_callused->fullsize = ~0;
5114 var_callused->is_special_var = 0;
5115 VEC_safe_push (varinfo_t, heap, varmap, var_callused);
5117 /* CALLUSED = *CALLUSED, because call-used is may-deref'd at calls, etc. */
5119 lhs.var = callused_id;
5122 rhs.var = callused_id;
5124 process_constraint (new_constraint (lhs, rhs));
5126 /* Create the INTEGER variable, used to represent that a variable points
5128 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
5129 var_integer = new_var_info (integer_tree, integer_id, "INTEGER");
5130 insert_vi_for_tree (integer_tree, var_integer);
5131 var_integer->is_artificial_var = 1;
5132 var_integer->size = ~0;
5133 var_integer->fullsize = ~0;
5134 var_integer->offset = 0;
5135 var_integer->next = NULL;
5136 var_integer->is_special_var = 1;
5137 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
5139 /* INTEGER = ANYTHING, because we don't know where a dereference of
5140 a random integer will point to. */
5142 lhs.var = integer_id;
5144 rhs.type = ADDRESSOF;
5145 rhs.var = anything_id;
5147 process_constraint (new_constraint (lhs, rhs));
5149 /* *ESCAPED = &ESCAPED. This is true because we have to assume
5150 everything pointed to by escaped can also point to escaped. */
5152 lhs.var = escaped_id;
5154 rhs.type = ADDRESSOF;
5155 rhs.var = escaped_id;
5157 process_constraint (new_constraint (lhs, rhs));
5159 /* *ESCAPED = &NONLOCAL. This is true because we have to assume
5160 everything pointed to by escaped can also point to nonlocal. */
5162 lhs.var = escaped_id;
5164 rhs.type = ADDRESSOF;
5165 rhs.var = nonlocal_id;
5167 process_constraint (new_constraint (lhs, rhs));
5170 /* Initialize things necessary to perform PTA */
5173 init_alias_vars (void)
5175 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
5177 bitmap_obstack_initialize (&pta_obstack);
5178 bitmap_obstack_initialize (&oldpta_obstack);
5179 bitmap_obstack_initialize (&predbitmap_obstack);
5181 constraint_pool = create_alloc_pool ("Constraint pool",
5182 sizeof (struct constraint), 30);
5183 variable_info_pool = create_alloc_pool ("Variable info pool",
5184 sizeof (struct variable_info), 30);
5185 constraints = VEC_alloc (constraint_t, heap, 8);
5186 varmap = VEC_alloc (varinfo_t, heap, 8);
5187 vi_for_tree = pointer_map_create ();
5189 memset (&stats, 0, sizeof (stats));
5190 shared_bitmap_table = htab_create (511, shared_bitmap_hash,
5191 shared_bitmap_eq, free);
5195 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
5196 predecessor edges. */
5199 remove_preds_and_fake_succs (constraint_graph_t graph)
5203 /* Clear the implicit ref and address nodes from the successor
5205 for (i = 0; i < FIRST_REF_NODE; i++)
5207 if (graph->succs[i])
5208 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
5209 FIRST_REF_NODE * 2);
5212 /* Free the successor list for the non-ref nodes. */
5213 for (i = FIRST_REF_NODE; i < graph->size; i++)
5215 if (graph->succs[i])
5216 BITMAP_FREE (graph->succs[i]);
5219 /* Now reallocate the size of the successor list as, and blow away
5220 the predecessor bitmaps. */
5221 graph->size = VEC_length (varinfo_t, varmap);
5222 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
5224 free (graph->implicit_preds);
5225 graph->implicit_preds = NULL;
5226 free (graph->preds);
5227 graph->preds = NULL;
5228 bitmap_obstack_release (&predbitmap_obstack);
5231 /* Compute the set of variables we can't TBAA prune. */
5234 compute_tbaa_pruning (void)
5236 unsigned int size = VEC_length (varinfo_t, varmap);
5241 changed = sbitmap_alloc (size);
5242 sbitmap_zero (changed);
5244 /* Mark all initial no_tbaa_pruning nodes as changed. */
5246 for (i = 0; i < size; ++i)
5248 varinfo_t ivi = get_varinfo (i);
5250 if (find (i) == i && ivi->no_tbaa_pruning)
5253 if ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
5254 || VEC_length (constraint_t, graph->complex[i]) > 0)
5256 SET_BIT (changed, i);
5262 while (changed_count > 0)
5264 struct topo_info *ti = init_topo_info ();
5267 compute_topo_order (graph, ti);
5269 while (VEC_length (unsigned, ti->topo_order) != 0)
5273 i = VEC_pop (unsigned, ti->topo_order);
5275 /* If this variable is not a representative, skip it. */
5279 /* If the node has changed, we need to process the complex
5280 constraints and outgoing edges again. */
5281 if (TEST_BIT (changed, i))
5285 VEC(constraint_t,heap) *complex = graph->complex[i];
5287 RESET_BIT (changed, i);
5290 /* Process the complex copy constraints. */
5291 for (j = 0; VEC_iterate (constraint_t, complex, j, c); ++j)
5293 if (c->lhs.type == SCALAR && c->rhs.type == SCALAR)
5295 varinfo_t lhsvi = get_varinfo (find (c->lhs.var));
5297 if (!lhsvi->no_tbaa_pruning)
5299 lhsvi->no_tbaa_pruning = true;
5300 if (!TEST_BIT (changed, lhsvi->id))
5302 SET_BIT (changed, lhsvi->id);
5309 /* Propagate to all successors. */
5310 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
5312 unsigned int to = find (j);
5313 varinfo_t tovi = get_varinfo (to);
5315 /* Don't propagate to ourselves. */
5319 if (!tovi->no_tbaa_pruning)
5321 tovi->no_tbaa_pruning = true;
5322 if (!TEST_BIT (changed, to))
5324 SET_BIT (changed, to);
5332 free_topo_info (ti);
5335 sbitmap_free (changed);
5339 for (i = 0; i < size; ++i)
5341 varinfo_t ivi = get_varinfo (i);
5342 varinfo_t ivip = get_varinfo (find (i));
5344 if (ivip->no_tbaa_pruning)
5346 tree var = ivi->decl;
5348 if (TREE_CODE (var) == SSA_NAME)
5349 var = SSA_NAME_VAR (var);
5351 if (POINTER_TYPE_P (TREE_TYPE (var)))
5353 DECL_NO_TBAA_P (var) = 1;
5355 /* Tell the RTL layer that this pointer can alias
5357 DECL_POINTER_ALIAS_SET (var) = 0;
5364 /* Create points-to sets for the current function. See the comments
5365 at the start of the file for an algorithmic overview. */
5368 compute_points_to_sets (void)
5370 struct scc_info *si;
5373 timevar_push (TV_TREE_PTA);
5376 init_alias_heapvars ();
5378 intra_create_variable_infos ();
5380 /* Now walk all statements and derive aliases. */
5383 gimple_stmt_iterator gsi;
5385 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5387 gimple phi = gsi_stmt (gsi);
5389 if (is_gimple_reg (gimple_phi_result (phi)))
5390 find_func_aliases (phi);
5393 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
5395 gimple stmt = gsi_stmt (gsi);
5397 find_func_aliases (stmt);
5399 /* The information in GIMPLE_CHANGE_DYNAMIC_TYPE statements
5400 has now been captured, and we can remove them. */
5401 if (gimple_code (stmt) == GIMPLE_CHANGE_DYNAMIC_TYPE)
5402 gsi_remove (&gsi, true);
5411 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5412 dump_constraints (dump_file);
5417 "\nCollapsing static cycles and doing variable "
5420 init_graph (VEC_length (varinfo_t, varmap) * 2);
5423 fprintf (dump_file, "Building predecessor graph\n");
5424 build_pred_graph ();
5427 fprintf (dump_file, "Detecting pointer and location "
5429 si = perform_var_substitution (graph);
5432 fprintf (dump_file, "Rewriting constraints and unifying "
5434 rewrite_constraints (graph, si);
5435 free_var_substitution_info (si);
5437 build_succ_graph ();
5439 if (dump_file && (dump_flags & TDF_GRAPH))
5440 dump_constraint_graph (dump_file);
5442 move_complex_constraints (graph);
5445 fprintf (dump_file, "Uniting pointer but not location equivalent "
5447 unite_pointer_equivalences (graph);
5450 fprintf (dump_file, "Finding indirect cycles\n");
5451 find_indirect_cycles (graph);
5453 /* Implicit nodes and predecessors are no longer necessary at this
5455 remove_preds_and_fake_succs (graph);
5458 fprintf (dump_file, "Solving graph\n");
5460 solve_graph (graph);
5462 compute_tbaa_pruning ();
5465 dump_sa_points_to_info (dump_file);
5467 have_alias_info = true;
5469 timevar_pop (TV_TREE_PTA);
5473 /* Delete created points-to sets. */
5476 delete_points_to_sets (void)
5480 htab_delete (shared_bitmap_table);
5481 if (dump_file && (dump_flags & TDF_STATS))
5482 fprintf (dump_file, "Points to sets created:%d\n",
5483 stats.points_to_sets_created);
5485 pointer_map_destroy (vi_for_tree);
5486 bitmap_obstack_release (&pta_obstack);
5487 VEC_free (constraint_t, heap, constraints);
5489 for (i = 0; i < graph->size; i++)
5490 VEC_free (constraint_t, heap, graph->complex[i]);
5491 free (graph->complex);
5494 free (graph->succs);
5496 free (graph->pe_rep);
5497 free (graph->indirect_cycles);
5500 VEC_free (varinfo_t, heap, varmap);
5501 free_alloc_pool (variable_info_pool);
5502 free_alloc_pool (constraint_pool);
5503 have_alias_info = false;
5506 /* Return true if we should execute IPA PTA. */
5510 return (flag_ipa_pta
5511 /* Don't bother doing anything if the program has errors. */
5512 && !(errorcount || sorrycount));
5515 /* Execute the driver for IPA PTA. */
5517 ipa_pta_execute (void)
5519 struct cgraph_node *node;
5520 struct scc_info *si;
5523 init_alias_heapvars ();
5526 for (node = cgraph_nodes; node; node = node->next)
5528 if (!node->analyzed || cgraph_is_master_clone (node))
5532 varid = create_function_info_for (node->decl,
5533 cgraph_node_name (node));
5534 if (node->local.externally_visible)
5536 varinfo_t fi = get_varinfo (varid);
5537 for (; fi; fi = fi->next)
5538 make_constraint_from (fi, anything_id);
5542 for (node = cgraph_nodes; node; node = node->next)
5544 if (node->analyzed && cgraph_is_master_clone (node))
5546 struct function *func = DECL_STRUCT_FUNCTION (node->decl);
5548 tree old_func_decl = current_function_decl;
5551 "Generating constraints for %s\n",
5552 cgraph_node_name (node));
5554 current_function_decl = node->decl;
5556 FOR_EACH_BB_FN (bb, func)
5558 gimple_stmt_iterator gsi;
5560 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
5563 gimple phi = gsi_stmt (gsi);
5565 if (is_gimple_reg (gimple_phi_result (phi)))
5566 find_func_aliases (phi);
5569 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5570 find_func_aliases (gsi_stmt (gsi));
5572 current_function_decl = old_func_decl;
5577 /* Make point to anything. */
5583 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5584 dump_constraints (dump_file);
5589 "\nCollapsing static cycles and doing variable "
5592 init_graph (VEC_length (varinfo_t, varmap) * 2);
5593 build_pred_graph ();
5594 si = perform_var_substitution (graph);
5595 rewrite_constraints (graph, si);
5596 free_var_substitution_info (si);
5598 build_succ_graph ();
5599 move_complex_constraints (graph);
5600 unite_pointer_equivalences (graph);
5601 find_indirect_cycles (graph);
5603 /* Implicit nodes and predecessors are no longer necessary at this
5605 remove_preds_and_fake_succs (graph);
5608 fprintf (dump_file, "\nSolving graph\n");
5610 solve_graph (graph);
5613 dump_sa_points_to_info (dump_file);
5616 delete_alias_heapvars ();
5617 delete_points_to_sets ();
5621 struct simple_ipa_opt_pass pass_ipa_pta =
5626 gate_ipa_pta, /* gate */
5627 ipa_pta_execute, /* execute */
5630 0, /* static_pass_number */
5631 TV_IPA_PTA, /* tv_id */
5632 0, /* properties_required */
5633 0, /* properties_provided */
5634 0, /* properties_destroyed */
5635 0, /* todo_flags_start */
5636 TODO_update_ssa /* todo_flags_finish */
5640 /* Initialize the heapvar for statement mapping. */
5642 init_alias_heapvars (void)
5644 if (!heapvar_for_stmt)
5645 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5650 delete_alias_heapvars (void)
5652 htab_delete (heapvar_for_stmt);
5653 heapvar_for_stmt = NULL;
5656 #include "gt-tree-ssa-structalias.h"