1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
36 #include "tree-flow.h"
37 #include "tree-inline.h"
40 #include "diagnostic.h"
46 #include "tree-pass.h"
48 #include "alloc-pool.h"
49 #include "splay-tree.h"
51 #include "tree-ssa-structalias.h"
54 #include "pointer-set.h"
56 /* The idea behind this analyzer is to generate set constraints from the
57 program, then solve the resulting constraints in order to generate the
60 Set constraints are a way of modeling program analysis problems that
61 involve sets. They consist of an inclusion constraint language,
62 describing the variables (each variable is a set) and operations that
63 are involved on the variables, and a set of rules that derive facts
64 from these operations. To solve a system of set constraints, you derive
65 all possible facts under the rules, which gives you the correct sets
68 See "Efficient Field-sensitive pointer analysis for C" by "David
69 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
70 http://citeseer.ist.psu.edu/pearce04efficient.html
72 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
73 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
74 http://citeseer.ist.psu.edu/heintze01ultrafast.html
76 There are three types of real constraint expressions, DEREF,
77 ADDRESSOF, and SCALAR. Each constraint expression consists
78 of a constraint type, a variable, and an offset.
80 SCALAR is a constraint expression type used to represent x, whether
81 it appears on the LHS or the RHS of a statement.
82 DEREF is a constraint expression type used to represent *x, whether
83 it appears on the LHS or the RHS of a statement.
84 ADDRESSOF is a constraint expression used to represent &x, whether
85 it appears on the LHS or the RHS of a statement.
87 Each pointer variable in the program is assigned an integer id, and
88 each field of a structure variable is assigned an integer id as well.
90 Structure variables are linked to their list of fields through a "next
91 field" in each variable that points to the next field in offset
93 Each variable for a structure field has
95 1. "size", that tells the size in bits of that field.
96 2. "fullsize, that tells the size in bits of the entire structure.
97 3. "offset", that tells the offset in bits from the beginning of the
98 structure to this field.
110 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
111 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
112 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
115 In order to solve the system of set constraints, the following is
118 1. Each constraint variable x has a solution set associated with it,
121 2. Constraints are separated into direct, copy, and complex.
122 Direct constraints are ADDRESSOF constraints that require no extra
123 processing, such as P = &Q
124 Copy constraints are those of the form P = Q.
125 Complex constraints are all the constraints involving dereferences
126 and offsets (including offsetted copies).
128 3. All direct constraints of the form P = &Q are processed, such
129 that Q is added to Sol(P)
131 4. All complex constraints for a given constraint variable are stored in a
132 linked list attached to that variable's node.
134 5. A directed graph is built out of the copy constraints. Each
135 constraint variable is a node in the graph, and an edge from
136 Q to P is added for each copy constraint of the form P = Q
138 6. The graph is then walked, and solution sets are
139 propagated along the copy edges, such that an edge from Q to P
140 causes Sol(P) <- Sol(P) union Sol(Q).
142 7. As we visit each node, all complex constraints associated with
143 that node are processed by adding appropriate copy edges to the graph, or the
144 appropriate variables to the solution set.
146 8. The process of walking the graph is iterated until no solution
149 Prior to walking the graph in steps 6 and 7, We perform static
150 cycle elimination on the constraint graph, as well
151 as off-line variable substitution.
153 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
154 on and turned into anything), but isn't. You can just see what offset
155 inside the pointed-to struct it's going to access.
157 TODO: Constant bounded arrays can be handled as if they were structs of the
158 same number of elements.
160 TODO: Modeling heap and incoming pointers becomes much better if we
161 add fields to them as we discover them, which we could do.
163 TODO: We could handle unions, but to be honest, it's probably not
164 worth the pain or slowdown. */
166 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
167 htab_t heapvar_for_stmt;
169 static bool use_field_sensitive = true;
170 static int in_ipa_mode = 0;
172 /* Used for predecessor bitmaps. */
173 static bitmap_obstack predbitmap_obstack;
175 /* Used for points-to sets. */
176 static bitmap_obstack pta_obstack;
178 /* Used for oldsolution members of variables. */
179 static bitmap_obstack oldpta_obstack;
181 /* Used for per-solver-iteration bitmaps. */
182 static bitmap_obstack iteration_obstack;
184 static unsigned int create_variable_info_for (tree, const char *);
185 typedef struct constraint_graph *constraint_graph_t;
186 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
188 DEF_VEC_P(constraint_t);
189 DEF_VEC_ALLOC_P(constraint_t,heap);
191 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
193 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
195 static struct constraint_stats
197 unsigned int total_vars;
198 unsigned int nonpointer_vars;
199 unsigned int unified_vars_static;
200 unsigned int unified_vars_dynamic;
201 unsigned int iterations;
202 unsigned int num_edges;
203 unsigned int num_implicit_edges;
204 unsigned int points_to_sets_created;
209 /* ID of this variable */
212 /* True if this is a variable created by the constraint analysis, such as
213 heap variables and constraints we had to break up. */
214 unsigned int is_artificial_var:1;
216 /* True if this is a special variable whose solution set should not be
218 unsigned int is_special_var:1;
220 /* True for variables whose size is not known or variable. */
221 unsigned int is_unknown_size_var:1;
223 /* True for (sub-)fields that represent a whole variable. */
224 unsigned int is_full_var : 1;
226 /* True if this is a heap variable. */
227 unsigned int is_heap_var:1;
229 /* True if we may not use TBAA to prune references to this
230 variable. This is used for C++ placement new. */
231 unsigned int no_tbaa_pruning : 1;
233 /* 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 /* Vector of complex constraints for each graph node. Complex
510 constraints are those involving dereferences or offsets that are
512 VEC(constraint_t,heap) **complex;
515 static constraint_graph_t graph;
517 /* During variable substitution and the offline version of indirect
518 cycle finding, we create nodes to represent dereferences and
519 address taken constraints. These represent where these start and
521 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
522 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
524 /* Return the representative node for NODE, if NODE has been unioned
526 This function performs path compression along the way to finding
527 the representative. */
530 find (unsigned int node)
532 gcc_assert (node < graph->size);
533 if (graph->rep[node] != node)
534 return graph->rep[node] = find (graph->rep[node]);
538 /* Union the TO and FROM nodes to the TO nodes.
539 Note that at some point in the future, we may want to do
540 union-by-rank, in which case we are going to have to return the
541 node we unified to. */
544 unite (unsigned int to, unsigned int from)
546 gcc_assert (to < graph->size && from < graph->size);
547 if (to != from && graph->rep[from] != to)
549 graph->rep[from] = to;
555 /* Create a new constraint consisting of LHS and RHS expressions. */
558 new_constraint (const struct constraint_expr lhs,
559 const struct constraint_expr rhs)
561 constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
567 /* Print out constraint C to FILE. */
570 dump_constraint (FILE *file, constraint_t c)
572 if (c->lhs.type == ADDRESSOF)
574 else if (c->lhs.type == DEREF)
576 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
577 if (c->lhs.offset != 0)
578 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
579 fprintf (file, " = ");
580 if (c->rhs.type == ADDRESSOF)
582 else if (c->rhs.type == DEREF)
584 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
585 if (c->rhs.offset != 0)
586 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
587 fprintf (file, "\n");
590 /* Print out constraint C to stderr. */
593 debug_constraint (constraint_t c)
595 dump_constraint (stderr, c);
598 /* Print out all constraints to FILE */
601 dump_constraints (FILE *file)
605 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
606 dump_constraint (file, c);
609 /* Print out all constraints to stderr. */
612 debug_constraints (void)
614 dump_constraints (stderr);
617 /* Print out to FILE the edge in the constraint graph that is created by
618 constraint c. The edge may have a label, depending on the type of
619 constraint that it represents. If complex1, e.g: a = *b, then the label
620 is "=*", if complex2, e.g: *a = b, then the label is "*=", if
621 complex with an offset, e.g: a = b + 8, then the label is "+".
622 Otherwise the edge has no label. */
625 dump_constraint_edge (FILE *file, constraint_t c)
627 if (c->rhs.type != ADDRESSOF)
629 const char *src = get_varinfo_fc (c->rhs.var)->name;
630 const char *dst = get_varinfo_fc (c->lhs.var)->name;
631 fprintf (file, " \"%s\" -> \"%s\" ", src, dst);
632 /* Due to preprocessing of constraints, instructions like *a = *b are
633 illegal; thus, we do not have to handle such cases. */
634 if (c->lhs.type == DEREF)
635 fprintf (file, " [ label=\"*=\" ] ;\n");
636 else if (c->rhs.type == DEREF)
637 fprintf (file, " [ label=\"=*\" ] ;\n");
640 /* We must check the case where the constraint is an offset.
641 In this case, it is treated as a complex constraint. */
642 if (c->rhs.offset != c->lhs.offset)
643 fprintf (file, " [ label=\"+\" ] ;\n");
645 fprintf (file, " ;\n");
650 /* Print the constraint graph in dot format. */
653 dump_constraint_graph (FILE *file)
655 unsigned int i=0, size;
658 /* Only print the graph if it has already been initialized: */
662 /* Print the constraints used to produce the constraint graph. The
663 constraints will be printed as comments in the dot file: */
664 fprintf (file, "\n\n/* Constraints used in the constraint graph:\n");
665 dump_constraints (file);
666 fprintf (file, "*/\n");
668 /* Prints the header of the dot file: */
669 fprintf (file, "\n\n// The constraint graph in dot format:\n");
670 fprintf (file, "strict digraph {\n");
671 fprintf (file, " node [\n shape = box\n ]\n");
672 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
673 fprintf (file, "\n // List of nodes in the constraint graph:\n");
675 /* The next lines print the nodes in the graph. In order to get the
676 number of nodes in the graph, we must choose the minimum between the
677 vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
678 yet been initialized, then graph->size == 0, otherwise we must only
679 read nodes that have an entry in VEC (varinfo_t, varmap). */
680 size = VEC_length (varinfo_t, varmap);
681 size = size < graph->size ? size : graph->size;
682 for (i = 0; i < size; i++)
684 const char *name = get_varinfo_fc (graph->rep[i])->name;
685 fprintf (file, " \"%s\" ;\n", name);
688 /* Go over the list of constraints printing the edges in the constraint
690 fprintf (file, "\n // The constraint edges:\n");
691 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
693 dump_constraint_edge (file, c);
695 /* Prints the tail of the dot file. By now, only the closing bracket. */
696 fprintf (file, "}\n\n\n");
699 /* Print out the constraint graph to stderr. */
702 debug_constraint_graph (void)
704 dump_constraint_graph (stderr);
709 The solver is a simple worklist solver, that works on the following
712 sbitmap changed_nodes = all zeroes;
714 For each node that is not already collapsed:
716 set bit in changed nodes
718 while (changed_count > 0)
720 compute topological ordering for constraint graph
722 find and collapse cycles in the constraint graph (updating
723 changed if necessary)
725 for each node (n) in the graph in topological order:
728 Process each complex constraint associated with the node,
729 updating changed if necessary.
731 For each outgoing edge from n, propagate the solution from n to
732 the destination of the edge, updating changed as necessary.
736 /* Return true if two constraint expressions A and B are equal. */
739 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
741 return a.type == b.type && a.var == b.var && a.offset == b.offset;
744 /* Return true if constraint expression A is less than constraint expression
745 B. This is just arbitrary, but consistent, in order to give them an
749 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
751 if (a.type == b.type)
754 return a.offset < b.offset;
756 return a.var < b.var;
759 return a.type < b.type;
762 /* Return true if constraint A is less than constraint B. This is just
763 arbitrary, but consistent, in order to give them an ordering. */
766 constraint_less (const constraint_t a, const constraint_t b)
768 if (constraint_expr_less (a->lhs, b->lhs))
770 else if (constraint_expr_less (b->lhs, a->lhs))
773 return constraint_expr_less (a->rhs, b->rhs);
776 /* Return true if two constraints A and B are equal. */
779 constraint_equal (struct constraint a, struct constraint b)
781 return constraint_expr_equal (a.lhs, b.lhs)
782 && constraint_expr_equal (a.rhs, b.rhs);
786 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
789 constraint_vec_find (VEC(constraint_t,heap) *vec,
790 struct constraint lookfor)
798 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
799 if (place >= VEC_length (constraint_t, vec))
801 found = VEC_index (constraint_t, vec, place);
802 if (!constraint_equal (*found, lookfor))
807 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
810 constraint_set_union (VEC(constraint_t,heap) **to,
811 VEC(constraint_t,heap) **from)
816 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
818 if (constraint_vec_find (*to, *c) == NULL)
820 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
822 VEC_safe_insert (constraint_t, heap, *to, place, c);
827 /* Take a solution set SET, add OFFSET to each member of the set, and
828 overwrite SET with the result when done. */
831 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
833 bitmap result = BITMAP_ALLOC (&iteration_obstack);
837 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
839 varinfo_t vi = get_varinfo (i);
841 /* If this is a variable with just one field just set its bit
843 if (vi->is_artificial_var
844 || vi->is_unknown_size_var
846 bitmap_set_bit (result, i);
849 unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
850 varinfo_t v = first_vi_for_offset (vi, fieldoffset);
851 /* If the result is outside of the variable use the last field. */
855 while (v->next != NULL)
858 bitmap_set_bit (result, v->id);
859 /* If the result is not exactly at fieldoffset include the next
860 field as well. See get_constraint_for_ptr_offset for more
862 if (v->offset != fieldoffset
864 bitmap_set_bit (result, v->next->id);
868 bitmap_copy (set, result);
869 BITMAP_FREE (result);
872 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
876 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
879 return bitmap_ior_into (to, from);
885 tmp = BITMAP_ALLOC (&iteration_obstack);
886 bitmap_copy (tmp, from);
887 solution_set_add (tmp, inc);
888 res = bitmap_ior_into (to, tmp);
894 /* Insert constraint C into the list of complex constraints for graph
898 insert_into_complex (constraint_graph_t graph,
899 unsigned int var, constraint_t c)
901 VEC (constraint_t, heap) *complex = graph->complex[var];
902 unsigned int place = VEC_lower_bound (constraint_t, complex, c,
905 /* Only insert constraints that do not already exist. */
906 if (place >= VEC_length (constraint_t, complex)
907 || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
908 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
912 /* Condense two variable nodes into a single variable node, by moving
913 all associated info from SRC to TO. */
916 merge_node_constraints (constraint_graph_t graph, unsigned int to,
922 gcc_assert (find (from) == to);
924 /* Move all complex constraints from src node into to node */
925 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
927 /* In complex constraints for node src, we may have either
928 a = *src, and *src = a, or an offseted constraint which are
929 always added to the rhs node's constraints. */
931 if (c->rhs.type == DEREF)
933 else if (c->lhs.type == DEREF)
938 constraint_set_union (&graph->complex[to], &graph->complex[from]);
939 VEC_free (constraint_t, heap, graph->complex[from]);
940 graph->complex[from] = NULL;
944 /* Remove edges involving NODE from GRAPH. */
947 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
949 if (graph->succs[node])
950 BITMAP_FREE (graph->succs[node]);
953 /* Merge GRAPH nodes FROM and TO into node TO. */
956 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
959 if (graph->indirect_cycles[from] != -1)
961 /* If we have indirect cycles with the from node, and we have
962 none on the to node, the to node has indirect cycles from the
963 from node now that they are unified.
964 If indirect cycles exist on both, unify the nodes that they
965 are in a cycle with, since we know they are in a cycle with
967 if (graph->indirect_cycles[to] == -1)
968 graph->indirect_cycles[to] = graph->indirect_cycles[from];
971 /* Merge all the successor edges. */
972 if (graph->succs[from])
974 if (!graph->succs[to])
975 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
976 bitmap_ior_into (graph->succs[to],
980 clear_edges_for_node (graph, from);
984 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
985 it doesn't exist in the graph already. */
988 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
994 if (!graph->implicit_preds[to])
995 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
997 if (bitmap_set_bit (graph->implicit_preds[to], from))
998 stats.num_implicit_edges++;
1001 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1002 it doesn't exist in the graph already.
1003 Return false if the edge already existed, true otherwise. */
1006 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1009 if (!graph->preds[to])
1010 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1011 bitmap_set_bit (graph->preds[to], from);
1014 /* Add a graph edge to GRAPH, going from FROM to TO if
1015 it doesn't exist in the graph already.
1016 Return false if the edge already existed, true otherwise. */
1019 add_graph_edge (constraint_graph_t graph, unsigned int to,
1030 if (!graph->succs[from])
1031 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1032 if (bitmap_set_bit (graph->succs[from], to))
1035 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1043 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1046 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1049 return (graph->succs[dest]
1050 && bitmap_bit_p (graph->succs[dest], src));
1053 /* Initialize the constraint graph structure to contain SIZE nodes. */
1056 init_graph (unsigned int size)
1060 graph = XCNEW (struct constraint_graph);
1062 graph->succs = XCNEWVEC (bitmap, graph->size);
1063 graph->indirect_cycles = XNEWVEC (int, graph->size);
1064 graph->rep = XNEWVEC (unsigned int, graph->size);
1065 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
1066 graph->pe = XCNEWVEC (unsigned int, graph->size);
1067 graph->pe_rep = XNEWVEC (int, graph->size);
1069 for (j = 0; j < graph->size; j++)
1072 graph->pe_rep[j] = -1;
1073 graph->indirect_cycles[j] = -1;
1077 /* Build the constraint graph, adding only predecessor edges right now. */
1080 build_pred_graph (void)
1086 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1087 graph->preds = XCNEWVEC (bitmap, graph->size);
1088 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1089 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1090 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1091 graph->points_to = XCNEWVEC (bitmap, graph->size);
1092 graph->eq_rep = XNEWVEC (int, graph->size);
1093 graph->direct_nodes = sbitmap_alloc (graph->size);
1094 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1095 sbitmap_zero (graph->direct_nodes);
1097 for (j = 0; j < FIRST_REF_NODE; j++)
1099 if (!get_varinfo (j)->is_special_var)
1100 SET_BIT (graph->direct_nodes, j);
1103 for (j = 0; j < graph->size; j++)
1104 graph->eq_rep[j] = -1;
1106 for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
1107 graph->indirect_cycles[j] = -1;
1109 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1111 struct constraint_expr lhs = c->lhs;
1112 struct constraint_expr rhs = c->rhs;
1113 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
1114 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
1116 if (lhs.type == DEREF)
1119 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1120 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1122 else if (rhs.type == DEREF)
1125 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1126 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1128 RESET_BIT (graph->direct_nodes, lhsvar);
1130 else if (rhs.type == ADDRESSOF)
1135 if (graph->points_to[lhsvar] == NULL)
1136 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1137 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1139 if (graph->pointed_by[rhsvar] == NULL)
1140 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1141 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1143 /* Implicitly, *x = y */
1144 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1146 /* All related variables are no longer direct nodes. */
1147 RESET_BIT (graph->direct_nodes, rhsvar);
1148 v = get_varinfo (rhsvar);
1149 if (!v->is_full_var)
1151 v = lookup_vi_for_tree (v->decl);
1154 RESET_BIT (graph->direct_nodes, v->id);
1159 bitmap_set_bit (graph->address_taken, rhsvar);
1161 else if (lhsvar > anything_id
1162 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1165 add_pred_graph_edge (graph, lhsvar, rhsvar);
1166 /* Implicitly, *x = *y */
1167 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1168 FIRST_REF_NODE + rhsvar);
1170 else if (lhs.offset != 0 || rhs.offset != 0)
1172 if (rhs.offset != 0)
1173 RESET_BIT (graph->direct_nodes, lhs.var);
1174 else if (lhs.offset != 0)
1175 RESET_BIT (graph->direct_nodes, rhs.var);
1180 /* Build the constraint graph, adding successor edges. */
1183 build_succ_graph (void)
1188 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1190 struct constraint_expr lhs;
1191 struct constraint_expr rhs;
1192 unsigned int lhsvar;
1193 unsigned int rhsvar;
1200 lhsvar = find (get_varinfo_fc (lhs.var)->id);
1201 rhsvar = find (get_varinfo_fc (rhs.var)->id);
1203 if (lhs.type == DEREF)
1205 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1206 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1208 else if (rhs.type == DEREF)
1210 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1211 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1213 else if (rhs.type == ADDRESSOF)
1216 gcc_assert (find (get_varinfo_fc (rhs.var)->id)
1217 == get_varinfo_fc (rhs.var)->id);
1218 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1220 else if (lhsvar > anything_id
1221 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1223 add_graph_edge (graph, lhsvar, rhsvar);
1229 /* Changed variables on the last iteration. */
1230 static unsigned int changed_count;
1231 static sbitmap changed;
1233 DEF_VEC_I(unsigned);
1234 DEF_VEC_ALLOC_I(unsigned,heap);
1237 /* Strongly Connected Component visitation info. */
1244 unsigned int *node_mapping;
1246 VEC(unsigned,heap) *scc_stack;
1250 /* Recursive routine to find strongly connected components in GRAPH.
1251 SI is the SCC info to store the information in, and N is the id of current
1252 graph node we are processing.
1254 This is Tarjan's strongly connected component finding algorithm, as
1255 modified by Nuutila to keep only non-root nodes on the stack.
1256 The algorithm can be found in "On finding the strongly connected
1257 connected components in a directed graph" by Esko Nuutila and Eljas
1258 Soisalon-Soininen, in Information Processing Letters volume 49,
1259 number 1, pages 9-14. */
1262 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1266 unsigned int my_dfs;
1268 SET_BIT (si->visited, n);
1269 si->dfs[n] = si->current_index ++;
1270 my_dfs = si->dfs[n];
1272 /* Visit all the successors. */
1273 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1277 if (i > LAST_REF_NODE)
1281 if (TEST_BIT (si->deleted, w))
1284 if (!TEST_BIT (si->visited, w))
1285 scc_visit (graph, si, w);
1287 unsigned int t = find (w);
1288 unsigned int nnode = find (n);
1289 gcc_assert (nnode == n);
1291 if (si->dfs[t] < si->dfs[nnode])
1292 si->dfs[n] = si->dfs[t];
1296 /* See if any components have been identified. */
1297 if (si->dfs[n] == my_dfs)
1299 if (VEC_length (unsigned, si->scc_stack) > 0
1300 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1302 bitmap scc = BITMAP_ALLOC (NULL);
1303 bool have_ref_node = n >= FIRST_REF_NODE;
1304 unsigned int lowest_node;
1307 bitmap_set_bit (scc, n);
1309 while (VEC_length (unsigned, si->scc_stack) != 0
1310 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1312 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1314 bitmap_set_bit (scc, w);
1315 if (w >= FIRST_REF_NODE)
1316 have_ref_node = true;
1319 lowest_node = bitmap_first_set_bit (scc);
1320 gcc_assert (lowest_node < FIRST_REF_NODE);
1322 /* Collapse the SCC nodes into a single node, and mark the
1324 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1326 if (i < FIRST_REF_NODE)
1328 if (unite (lowest_node, i))
1329 unify_nodes (graph, lowest_node, i, false);
1333 unite (lowest_node, i);
1334 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1338 SET_BIT (si->deleted, n);
1341 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1344 /* Unify node FROM into node TO, updating the changed count if
1345 necessary when UPDATE_CHANGED is true. */
1348 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1349 bool update_changed)
1352 gcc_assert (to != from && find (to) == to);
1353 if (dump_file && (dump_flags & TDF_DETAILS))
1354 fprintf (dump_file, "Unifying %s to %s\n",
1355 get_varinfo (from)->name,
1356 get_varinfo (to)->name);
1359 stats.unified_vars_dynamic++;
1361 stats.unified_vars_static++;
1363 merge_graph_nodes (graph, to, from);
1364 merge_node_constraints (graph, to, from);
1366 if (get_varinfo (from)->no_tbaa_pruning)
1367 get_varinfo (to)->no_tbaa_pruning = true;
1369 /* Mark TO as changed if FROM was changed. If TO was already marked
1370 as changed, decrease the changed count. */
1372 if (update_changed && TEST_BIT (changed, from))
1374 RESET_BIT (changed, from);
1375 if (!TEST_BIT (changed, to))
1376 SET_BIT (changed, to);
1379 gcc_assert (changed_count > 0);
1383 if (get_varinfo (from)->solution)
1385 /* If the solution changes because of the merging, we need to mark
1386 the variable as changed. */
1387 if (bitmap_ior_into (get_varinfo (to)->solution,
1388 get_varinfo (from)->solution))
1390 if (update_changed && !TEST_BIT (changed, to))
1392 SET_BIT (changed, to);
1397 BITMAP_FREE (get_varinfo (from)->solution);
1398 BITMAP_FREE (get_varinfo (from)->oldsolution);
1400 if (stats.iterations > 0)
1402 BITMAP_FREE (get_varinfo (to)->oldsolution);
1403 get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1406 if (valid_graph_edge (graph, to, to))
1408 if (graph->succs[to])
1409 bitmap_clear_bit (graph->succs[to], to);
1413 /* Information needed to compute the topological ordering of a graph. */
1417 /* sbitmap of visited nodes. */
1419 /* Array that stores the topological order of the graph, *in
1421 VEC(unsigned,heap) *topo_order;
1425 /* Initialize and return a topological info structure. */
1427 static struct topo_info *
1428 init_topo_info (void)
1430 size_t size = graph->size;
1431 struct topo_info *ti = XNEW (struct topo_info);
1432 ti->visited = sbitmap_alloc (size);
1433 sbitmap_zero (ti->visited);
1434 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1439 /* Free the topological sort info pointed to by TI. */
1442 free_topo_info (struct topo_info *ti)
1444 sbitmap_free (ti->visited);
1445 VEC_free (unsigned, heap, ti->topo_order);
1449 /* Visit the graph in topological order, and store the order in the
1450 topo_info structure. */
1453 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1459 SET_BIT (ti->visited, n);
1461 if (graph->succs[n])
1462 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1464 if (!TEST_BIT (ti->visited, j))
1465 topo_visit (graph, ti, j);
1468 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1471 /* Return true if variable N + OFFSET is a legal field of N. */
1474 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1476 varinfo_t ninfo = get_varinfo (n);
1478 /* For things we've globbed to single variables, any offset into the
1479 variable acts like the entire variable, so that it becomes offset
1481 if (ninfo->is_special_var
1482 || ninfo->is_artificial_var
1483 || ninfo->is_unknown_size_var
1484 || ninfo->is_full_var)
1489 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1492 /* Process a constraint C that represents x = *y, using DELTA as the
1493 starting solution. */
1496 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1499 unsigned int lhs = c->lhs.var;
1501 bitmap sol = get_varinfo (lhs)->solution;
1505 /* For x = *ESCAPED and x = *CALLUSED we want to compute the
1506 reachability set of the rhs var. As a pointer to a sub-field
1507 of a variable can also reach all other fields of the variable
1508 we simply have to expand the solution to contain all sub-fields
1509 if one sub-field is contained. */
1510 if (c->rhs.var == escaped_id
1511 || c->rhs.var == callused_id)
1514 /* In a first pass record all variables we need to add all
1515 sub-fields off. This avoids quadratic behavior. */
1516 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1518 varinfo_t v = get_varinfo (j);
1522 v = lookup_vi_for_tree (v->decl);
1523 if (v->next != NULL)
1526 vars = BITMAP_ALLOC (NULL);
1527 bitmap_set_bit (vars, v->id);
1530 /* In the second pass now do the addition to the solution and
1531 to speed up solving add it to the delta as well. */
1534 EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
1536 varinfo_t v = get_varinfo (j);
1537 for (; v != NULL; v = v->next)
1539 if (bitmap_set_bit (sol, v->id))
1542 bitmap_set_bit (delta, v->id);
1550 if (bitmap_bit_p (delta, anything_id))
1552 flag |= bitmap_set_bit (sol, anything_id);
1556 /* For each variable j in delta (Sol(y)), add
1557 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1558 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1560 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1561 if (type_safe (j, &roffset))
1564 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1567 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1568 /* If the access is outside of the variable we can ignore it. */
1573 /* Adding edges from the special vars is pointless.
1574 They don't have sets that can change. */
1575 if (get_varinfo (t)->is_special_var)
1576 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1577 /* Merging the solution from ESCAPED needlessly increases
1578 the set. Use ESCAPED as representative instead.
1579 Same for CALLUSED. */
1580 else if (get_varinfo (t)->id == escaped_id
1581 || get_varinfo (t)->id == callused_id)
1582 flag |= bitmap_set_bit (sol, get_varinfo (t)->id);
1583 else if (add_graph_edge (graph, lhs, t))
1584 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1589 /* If the LHS solution changed, mark the var as changed. */
1592 get_varinfo (lhs)->solution = sol;
1593 if (!TEST_BIT (changed, lhs))
1595 SET_BIT (changed, lhs);
1601 /* Process a constraint C that represents *x = y. */
1604 do_ds_constraint (constraint_t c, bitmap delta)
1606 unsigned int rhs = c->rhs.var;
1607 bitmap sol = get_varinfo (rhs)->solution;
1611 if (bitmap_bit_p (sol, anything_id))
1613 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1615 varinfo_t jvi = get_varinfo (j);
1617 unsigned int loff = c->lhs.offset;
1618 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
1621 v = get_varinfo (j);
1622 if (!v->is_full_var)
1624 v = first_vi_for_offset (v, fieldoffset);
1625 /* If the access is outside of the variable we can ignore it. */
1631 if (bitmap_set_bit (get_varinfo (t)->solution, anything_id)
1632 && !TEST_BIT (changed, t))
1634 SET_BIT (changed, t);
1641 /* For each member j of delta (Sol(x)), add an edge from y to j and
1642 union Sol(y) into Sol(j) */
1643 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1645 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1646 if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
1650 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1653 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1654 /* If the access is outside of the variable we can ignore it. */
1658 tmp = get_varinfo (t)->solution;
1660 if (add_graph_edge (graph, t, rhs))
1662 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1665 sol = get_varinfo (rhs)->solution;
1666 if (!TEST_BIT (changed, t))
1668 SET_BIT (changed, t);
1677 /* Handle a non-simple (simple meaning requires no iteration),
1678 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1681 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1683 if (c->lhs.type == DEREF)
1685 if (c->rhs.type == ADDRESSOF)
1692 do_ds_constraint (c, delta);
1695 else if (c->rhs.type == DEREF)
1698 if (!(get_varinfo (c->lhs.var)->is_special_var))
1699 do_sd_constraint (graph, c, delta);
1707 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1708 solution = get_varinfo (c->rhs.var)->solution;
1709 tmp = get_varinfo (c->lhs.var)->solution;
1711 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1715 get_varinfo (c->lhs.var)->solution = tmp;
1716 if (!TEST_BIT (changed, c->lhs.var))
1718 SET_BIT (changed, c->lhs.var);
1725 /* Initialize and return a new SCC info structure. */
1727 static struct scc_info *
1728 init_scc_info (size_t size)
1730 struct scc_info *si = XNEW (struct scc_info);
1733 si->current_index = 0;
1734 si->visited = sbitmap_alloc (size);
1735 sbitmap_zero (si->visited);
1736 si->deleted = sbitmap_alloc (size);
1737 sbitmap_zero (si->deleted);
1738 si->node_mapping = XNEWVEC (unsigned int, size);
1739 si->dfs = XCNEWVEC (unsigned int, size);
1741 for (i = 0; i < size; i++)
1742 si->node_mapping[i] = i;
1744 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1748 /* Free an SCC info structure pointed to by SI */
1751 free_scc_info (struct scc_info *si)
1753 sbitmap_free (si->visited);
1754 sbitmap_free (si->deleted);
1755 free (si->node_mapping);
1757 VEC_free (unsigned, heap, si->scc_stack);
1762 /* Find indirect cycles in GRAPH that occur, using strongly connected
1763 components, and note them in the indirect cycles map.
1765 This technique comes from Ben Hardekopf and Calvin Lin,
1766 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1767 Lines of Code", submitted to PLDI 2007. */
1770 find_indirect_cycles (constraint_graph_t graph)
1773 unsigned int size = graph->size;
1774 struct scc_info *si = init_scc_info (size);
1776 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1777 if (!TEST_BIT (si->visited, i) && find (i) == i)
1778 scc_visit (graph, si, i);
1783 /* Compute a topological ordering for GRAPH, and store the result in the
1784 topo_info structure TI. */
1787 compute_topo_order (constraint_graph_t graph,
1788 struct topo_info *ti)
1791 unsigned int size = graph->size;
1793 for (i = 0; i != size; ++i)
1794 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1795 topo_visit (graph, ti, i);
1798 /* Structure used to for hash value numbering of pointer equivalence
1801 typedef struct equiv_class_label
1803 unsigned int equivalence_class;
1806 } *equiv_class_label_t;
1807 typedef const struct equiv_class_label *const_equiv_class_label_t;
1809 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1811 static htab_t pointer_equiv_class_table;
1813 /* A hashtable for mapping a bitmap of labels->location equivalence
1815 static htab_t location_equiv_class_table;
1817 /* Hash function for a equiv_class_label_t */
1820 equiv_class_label_hash (const void *p)
1822 const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
1823 return ecl->hashcode;
1826 /* Equality function for two equiv_class_label_t's. */
1829 equiv_class_label_eq (const void *p1, const void *p2)
1831 const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
1832 const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
1833 return bitmap_equal_p (eql1->labels, eql2->labels);
1836 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
1840 equiv_class_lookup (htab_t table, bitmap labels)
1843 struct equiv_class_label ecl;
1845 ecl.labels = labels;
1846 ecl.hashcode = bitmap_hash (labels);
1848 slot = htab_find_slot_with_hash (table, &ecl,
1849 ecl.hashcode, NO_INSERT);
1853 return ((equiv_class_label_t) *slot)->equivalence_class;
1857 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
1861 equiv_class_add (htab_t table, unsigned int equivalence_class,
1865 equiv_class_label_t ecl = XNEW (struct equiv_class_label);
1867 ecl->labels = labels;
1868 ecl->equivalence_class = equivalence_class;
1869 ecl->hashcode = bitmap_hash (labels);
1871 slot = htab_find_slot_with_hash (table, ecl,
1872 ecl->hashcode, INSERT);
1873 gcc_assert (!*slot);
1874 *slot = (void *) ecl;
1877 /* Perform offline variable substitution.
1879 This is a worst case quadratic time way of identifying variables
1880 that must have equivalent points-to sets, including those caused by
1881 static cycles, and single entry subgraphs, in the constraint graph.
1883 The technique is described in "Exploiting Pointer and Location
1884 Equivalence to Optimize Pointer Analysis. In the 14th International
1885 Static Analysis Symposium (SAS), August 2007." It is known as the
1886 "HU" algorithm, and is equivalent to value numbering the collapsed
1887 constraint graph including evaluating unions.
1889 The general method of finding equivalence classes is as follows:
1890 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1891 Initialize all non-REF nodes to be direct nodes.
1892 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1894 For each constraint containing the dereference, we also do the same
1897 We then compute SCC's in the graph and unify nodes in the same SCC,
1900 For each non-collapsed node x:
1901 Visit all unvisited explicit incoming edges.
1902 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1904 Lookup the equivalence class for pts(x).
1905 If we found one, equivalence_class(x) = found class.
1906 Otherwise, equivalence_class(x) = new class, and new_class is
1907 added to the lookup table.
1909 All direct nodes with the same equivalence class can be replaced
1910 with a single representative node.
1911 All unlabeled nodes (label == 0) are not pointers and all edges
1912 involving them can be eliminated.
1913 We perform these optimizations during rewrite_constraints
1915 In addition to pointer equivalence class finding, we also perform
1916 location equivalence class finding. This is the set of variables
1917 that always appear together in points-to sets. We use this to
1918 compress the size of the points-to sets. */
1920 /* Current maximum pointer equivalence class id. */
1921 static int pointer_equiv_class;
1923 /* Current maximum location equivalence class id. */
1924 static int location_equiv_class;
1926 /* Recursive routine to find strongly connected components in GRAPH,
1927 and label it's nodes with DFS numbers. */
1930 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1934 unsigned int my_dfs;
1936 gcc_assert (si->node_mapping[n] == n);
1937 SET_BIT (si->visited, n);
1938 si->dfs[n] = si->current_index ++;
1939 my_dfs = si->dfs[n];
1941 /* Visit all the successors. */
1942 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1944 unsigned int w = si->node_mapping[i];
1946 if (TEST_BIT (si->deleted, w))
1949 if (!TEST_BIT (si->visited, w))
1950 condense_visit (graph, si, w);
1952 unsigned int t = si->node_mapping[w];
1953 unsigned int nnode = si->node_mapping[n];
1954 gcc_assert (nnode == n);
1956 if (si->dfs[t] < si->dfs[nnode])
1957 si->dfs[n] = si->dfs[t];
1961 /* Visit all the implicit predecessors. */
1962 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1964 unsigned int w = si->node_mapping[i];
1966 if (TEST_BIT (si->deleted, w))
1969 if (!TEST_BIT (si->visited, w))
1970 condense_visit (graph, si, w);
1972 unsigned int t = si->node_mapping[w];
1973 unsigned int nnode = si->node_mapping[n];
1974 gcc_assert (nnode == n);
1976 if (si->dfs[t] < si->dfs[nnode])
1977 si->dfs[n] = si->dfs[t];
1981 /* See if any components have been identified. */
1982 if (si->dfs[n] == my_dfs)
1984 while (VEC_length (unsigned, si->scc_stack) != 0
1985 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1987 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1988 si->node_mapping[w] = n;
1990 if (!TEST_BIT (graph->direct_nodes, w))
1991 RESET_BIT (graph->direct_nodes, n);
1993 /* Unify our nodes. */
1994 if (graph->preds[w])
1996 if (!graph->preds[n])
1997 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
1998 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2000 if (graph->implicit_preds[w])
2002 if (!graph->implicit_preds[n])
2003 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2004 bitmap_ior_into (graph->implicit_preds[n],
2005 graph->implicit_preds[w]);
2007 if (graph->points_to[w])
2009 if (!graph->points_to[n])
2010 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2011 bitmap_ior_into (graph->points_to[n],
2012 graph->points_to[w]);
2015 SET_BIT (si->deleted, n);
2018 VEC_safe_push (unsigned, heap, si->scc_stack, n);
2021 /* Label pointer equivalences. */
2024 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2028 SET_BIT (si->visited, n);
2030 if (!graph->points_to[n])
2031 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2033 /* Label and union our incoming edges's points to sets. */
2034 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2036 unsigned int w = si->node_mapping[i];
2037 if (!TEST_BIT (si->visited, w))
2038 label_visit (graph, si, w);
2040 /* Skip unused edges */
2041 if (w == n || graph->pointer_label[w] == 0)
2044 if (graph->points_to[w])
2045 bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
2047 /* Indirect nodes get fresh variables. */
2048 if (!TEST_BIT (graph->direct_nodes, n))
2049 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2051 if (!bitmap_empty_p (graph->points_to[n]))
2053 unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
2054 graph->points_to[n]);
2057 label = pointer_equiv_class++;
2058 equiv_class_add (pointer_equiv_class_table,
2059 label, graph->points_to[n]);
2061 graph->pointer_label[n] = label;
2065 /* Perform offline variable substitution, discovering equivalence
2066 classes, and eliminating non-pointer variables. */
2068 static struct scc_info *
2069 perform_var_substitution (constraint_graph_t graph)
2072 unsigned int size = graph->size;
2073 struct scc_info *si = init_scc_info (size);
2075 bitmap_obstack_initialize (&iteration_obstack);
2076 pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
2077 equiv_class_label_eq, free);
2078 location_equiv_class_table = htab_create (511, equiv_class_label_hash,
2079 equiv_class_label_eq, free);
2080 pointer_equiv_class = 1;
2081 location_equiv_class = 1;
2083 /* Condense the nodes, which means to find SCC's, count incoming
2084 predecessors, and unite nodes in SCC's. */
2085 for (i = 0; i < FIRST_REF_NODE; i++)
2086 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2087 condense_visit (graph, si, si->node_mapping[i]);
2089 sbitmap_zero (si->visited);
2090 /* Actually the label the nodes for pointer equivalences */
2091 for (i = 0; i < FIRST_REF_NODE; i++)
2092 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2093 label_visit (graph, si, si->node_mapping[i]);
2095 /* Calculate location equivalence labels. */
2096 for (i = 0; i < FIRST_REF_NODE; i++)
2103 if (!graph->pointed_by[i])
2105 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2107 /* Translate the pointed-by mapping for pointer equivalence
2109 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2111 bitmap_set_bit (pointed_by,
2112 graph->pointer_label[si->node_mapping[j]]);
2114 /* The original pointed_by is now dead. */
2115 BITMAP_FREE (graph->pointed_by[i]);
2117 /* Look up the location equivalence label if one exists, or make
2119 label = equiv_class_lookup (location_equiv_class_table,
2123 label = location_equiv_class++;
2124 equiv_class_add (location_equiv_class_table,
2129 if (dump_file && (dump_flags & TDF_DETAILS))
2130 fprintf (dump_file, "Found location equivalence for node %s\n",
2131 get_varinfo (i)->name);
2132 BITMAP_FREE (pointed_by);
2134 graph->loc_label[i] = label;
2138 if (dump_file && (dump_flags & TDF_DETAILS))
2139 for (i = 0; i < FIRST_REF_NODE; i++)
2141 bool direct_node = TEST_BIT (graph->direct_nodes, i);
2143 "Equivalence classes for %s node id %d:%s are pointer: %d"
2145 direct_node ? "Direct node" : "Indirect node", i,
2146 get_varinfo (i)->name,
2147 graph->pointer_label[si->node_mapping[i]],
2148 graph->loc_label[si->node_mapping[i]]);
2151 /* Quickly eliminate our non-pointer variables. */
2153 for (i = 0; i < FIRST_REF_NODE; i++)
2155 unsigned int node = si->node_mapping[i];
2157 if (graph->pointer_label[node] == 0)
2159 if (dump_file && (dump_flags & TDF_DETAILS))
2161 "%s is a non-pointer variable, eliminating edges.\n",
2162 get_varinfo (node)->name);
2163 stats.nonpointer_vars++;
2164 clear_edges_for_node (graph, node);
2171 /* Free information that was only necessary for variable
2175 free_var_substitution_info (struct scc_info *si)
2178 free (graph->pointer_label);
2179 free (graph->loc_label);
2180 free (graph->pointed_by);
2181 free (graph->points_to);
2182 free (graph->eq_rep);
2183 sbitmap_free (graph->direct_nodes);
2184 htab_delete (pointer_equiv_class_table);
2185 htab_delete (location_equiv_class_table);
2186 bitmap_obstack_release (&iteration_obstack);
2189 /* Return an existing node that is equivalent to NODE, which has
2190 equivalence class LABEL, if one exists. Return NODE otherwise. */
2193 find_equivalent_node (constraint_graph_t graph,
2194 unsigned int node, unsigned int label)
2196 /* If the address version of this variable is unused, we can
2197 substitute it for anything else with the same label.
2198 Otherwise, we know the pointers are equivalent, but not the
2199 locations, and we can unite them later. */
2201 if (!bitmap_bit_p (graph->address_taken, node))
2203 gcc_assert (label < graph->size);
2205 if (graph->eq_rep[label] != -1)
2207 /* Unify the two variables since we know they are equivalent. */
2208 if (unite (graph->eq_rep[label], node))
2209 unify_nodes (graph, graph->eq_rep[label], node, false);
2210 return graph->eq_rep[label];
2214 graph->eq_rep[label] = node;
2215 graph->pe_rep[label] = node;
2220 gcc_assert (label < graph->size);
2221 graph->pe[node] = label;
2222 if (graph->pe_rep[label] == -1)
2223 graph->pe_rep[label] = node;
2229 /* Unite pointer equivalent but not location equivalent nodes in
2230 GRAPH. This may only be performed once variable substitution is
2234 unite_pointer_equivalences (constraint_graph_t graph)
2238 /* Go through the pointer equivalences and unite them to their
2239 representative, if they aren't already. */
2240 for (i = 0; i < FIRST_REF_NODE; i++)
2242 unsigned int label = graph->pe[i];
2245 int label_rep = graph->pe_rep[label];
2247 if (label_rep == -1)
2250 label_rep = find (label_rep);
2251 if (label_rep >= 0 && unite (label_rep, find (i)))
2252 unify_nodes (graph, label_rep, i, false);
2257 /* Move complex constraints to the GRAPH nodes they belong to. */
2260 move_complex_constraints (constraint_graph_t graph)
2265 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2269 struct constraint_expr lhs = c->lhs;
2270 struct constraint_expr rhs = c->rhs;
2272 if (lhs.type == DEREF)
2274 insert_into_complex (graph, lhs.var, c);
2276 else if (rhs.type == DEREF)
2278 if (!(get_varinfo (lhs.var)->is_special_var))
2279 insert_into_complex (graph, rhs.var, c);
2281 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2282 && (lhs.offset != 0 || rhs.offset != 0))
2284 insert_into_complex (graph, rhs.var, c);
2291 /* Optimize and rewrite complex constraints while performing
2292 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2293 result of perform_variable_substitution. */
2296 rewrite_constraints (constraint_graph_t graph,
2297 struct scc_info *si)
2303 for (j = 0; j < graph->size; j++)
2304 gcc_assert (find (j) == j);
2306 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2308 struct constraint_expr lhs = c->lhs;
2309 struct constraint_expr rhs = c->rhs;
2310 unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id);
2311 unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id);
2312 unsigned int lhsnode, rhsnode;
2313 unsigned int lhslabel, rhslabel;
2315 lhsnode = si->node_mapping[lhsvar];
2316 rhsnode = si->node_mapping[rhsvar];
2317 lhslabel = graph->pointer_label[lhsnode];
2318 rhslabel = graph->pointer_label[rhsnode];
2320 /* See if it is really a non-pointer variable, and if so, ignore
2324 if (dump_file && (dump_flags & TDF_DETAILS))
2327 fprintf (dump_file, "%s is a non-pointer variable,"
2328 "ignoring constraint:",
2329 get_varinfo (lhs.var)->name);
2330 dump_constraint (dump_file, c);
2332 VEC_replace (constraint_t, constraints, i, NULL);
2338 if (dump_file && (dump_flags & TDF_DETAILS))
2341 fprintf (dump_file, "%s is a non-pointer variable,"
2342 "ignoring constraint:",
2343 get_varinfo (rhs.var)->name);
2344 dump_constraint (dump_file, c);
2346 VEC_replace (constraint_t, constraints, i, NULL);
2350 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2351 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2352 c->lhs.var = lhsvar;
2353 c->rhs.var = rhsvar;
2358 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2359 part of an SCC, false otherwise. */
2362 eliminate_indirect_cycles (unsigned int node)
2364 if (graph->indirect_cycles[node] != -1
2365 && !bitmap_empty_p (get_varinfo (node)->solution))
2368 VEC(unsigned,heap) *queue = NULL;
2370 unsigned int to = find (graph->indirect_cycles[node]);
2373 /* We can't touch the solution set and call unify_nodes
2374 at the same time, because unify_nodes is going to do
2375 bitmap unions into it. */
2377 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2379 if (find (i) == i && i != to)
2382 VEC_safe_push (unsigned, heap, queue, i);
2387 VEC_iterate (unsigned, queue, queuepos, i);
2390 unify_nodes (graph, to, i, true);
2392 VEC_free (unsigned, heap, queue);
2398 /* Solve the constraint graph GRAPH using our worklist solver.
2399 This is based on the PW* family of solvers from the "Efficient Field
2400 Sensitive Pointer Analysis for C" paper.
2401 It works by iterating over all the graph nodes, processing the complex
2402 constraints and propagating the copy constraints, until everything stops
2403 changed. This corresponds to steps 6-8 in the solving list given above. */
2406 solve_graph (constraint_graph_t graph)
2408 unsigned int size = graph->size;
2413 changed = sbitmap_alloc (size);
2414 sbitmap_zero (changed);
2416 /* Mark all initial non-collapsed nodes as changed. */
2417 for (i = 0; i < size; i++)
2419 varinfo_t ivi = get_varinfo (i);
2420 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2421 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2422 || VEC_length (constraint_t, graph->complex[i]) > 0))
2424 SET_BIT (changed, i);
2429 /* Allocate a bitmap to be used to store the changed bits. */
2430 pts = BITMAP_ALLOC (&pta_obstack);
2432 while (changed_count > 0)
2435 struct topo_info *ti = init_topo_info ();
2438 bitmap_obstack_initialize (&iteration_obstack);
2440 compute_topo_order (graph, ti);
2442 while (VEC_length (unsigned, ti->topo_order) != 0)
2445 i = VEC_pop (unsigned, ti->topo_order);
2447 /* If this variable is not a representative, skip it. */
2451 /* In certain indirect cycle cases, we may merge this
2452 variable to another. */
2453 if (eliminate_indirect_cycles (i) && find (i) != i)
2456 /* If the node has changed, we need to process the
2457 complex constraints and outgoing edges again. */
2458 if (TEST_BIT (changed, i))
2463 VEC(constraint_t,heap) *complex = graph->complex[i];
2464 bool solution_empty;
2466 RESET_BIT (changed, i);
2469 /* Compute the changed set of solution bits. */
2470 bitmap_and_compl (pts, get_varinfo (i)->solution,
2471 get_varinfo (i)->oldsolution);
2473 if (bitmap_empty_p (pts))
2476 bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2478 solution = get_varinfo (i)->solution;
2479 solution_empty = bitmap_empty_p (solution);
2481 /* Process the complex constraints */
2482 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2484 /* XXX: This is going to unsort the constraints in
2485 some cases, which will occasionally add duplicate
2486 constraints during unification. This does not
2487 affect correctness. */
2488 c->lhs.var = find (c->lhs.var);
2489 c->rhs.var = find (c->rhs.var);
2491 /* The only complex constraint that can change our
2492 solution to non-empty, given an empty solution,
2493 is a constraint where the lhs side is receiving
2494 some set from elsewhere. */
2495 if (!solution_empty || c->lhs.type != DEREF)
2496 do_complex_constraint (graph, c, pts);
2499 solution_empty = bitmap_empty_p (solution);
2502 /* Do not propagate the ESCAPED/CALLUSED solutions. */
2504 && i != callused_id)
2508 /* Propagate solution to all successors. */
2509 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2515 unsigned int to = find (j);
2516 tmp = get_varinfo (to)->solution;
2519 /* Don't try to propagate to ourselves. */
2523 flag = set_union_with_increment (tmp, pts, 0);
2527 get_varinfo (to)->solution = tmp;
2528 if (!TEST_BIT (changed, to))
2530 SET_BIT (changed, to);
2538 free_topo_info (ti);
2539 bitmap_obstack_release (&iteration_obstack);
2543 sbitmap_free (changed);
2544 bitmap_obstack_release (&oldpta_obstack);
2547 /* Map from trees to variable infos. */
2548 static struct pointer_map_t *vi_for_tree;
2551 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2554 insert_vi_for_tree (tree t, varinfo_t vi)
2556 void **slot = pointer_map_insert (vi_for_tree, t);
2558 gcc_assert (*slot == NULL);
2562 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2563 exist in the map, return NULL, otherwise, return the varinfo we found. */
2566 lookup_vi_for_tree (tree t)
2568 void **slot = pointer_map_contains (vi_for_tree, t);
2572 return (varinfo_t) *slot;
2575 /* Return a printable name for DECL */
2578 alias_get_name (tree decl)
2580 const char *res = get_name (decl);
2582 int num_printed = 0;
2591 if (TREE_CODE (decl) == SSA_NAME)
2593 num_printed = asprintf (&temp, "%s_%u",
2594 alias_get_name (SSA_NAME_VAR (decl)),
2595 SSA_NAME_VERSION (decl));
2597 else if (DECL_P (decl))
2599 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2601 if (num_printed > 0)
2603 res = ggc_strdup (temp);
2609 /* Find the variable id for tree T in the map.
2610 If T doesn't exist in the map, create an entry for it and return it. */
2613 get_vi_for_tree (tree t)
2615 void **slot = pointer_map_contains (vi_for_tree, t);
2617 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2619 return (varinfo_t) *slot;
2622 /* Get a constraint expression for a new temporary variable. */
2624 static struct constraint_expr
2625 get_constraint_exp_for_temp (tree t)
2627 struct constraint_expr cexpr;
2629 gcc_assert (SSA_VAR_P (t));
2631 cexpr.type = SCALAR;
2632 cexpr.var = get_vi_for_tree (t)->id;
2638 /* Get a constraint expression vector from an SSA_VAR_P node.
2639 If address_p is true, the result will be taken its address of. */
2642 get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
2644 struct constraint_expr cexpr;
2647 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2648 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2650 /* For parameters, get at the points-to set for the actual parm
2652 if (TREE_CODE (t) == SSA_NAME
2653 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2654 && SSA_NAME_IS_DEFAULT_DEF (t))
2656 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2660 vi = get_vi_for_tree (t);
2662 cexpr.type = SCALAR;
2664 /* If we determine the result is "anything", and we know this is readonly,
2665 say it points to readonly memory instead. */
2666 if (cexpr.var == anything_id && TREE_READONLY (t))
2669 cexpr.type = ADDRESSOF;
2670 cexpr.var = readonly_id;
2673 /* If we are not taking the address of the constraint expr, add all
2674 sub-fiels of the variable as well. */
2677 for (; vi; vi = vi->next)
2680 VEC_safe_push (ce_s, heap, *results, &cexpr);
2685 VEC_safe_push (ce_s, heap, *results, &cexpr);
2688 /* Process constraint T, performing various simplifications and then
2689 adding it to our list of overall constraints. */
2692 process_constraint (constraint_t t)
2694 struct constraint_expr rhs = t->rhs;
2695 struct constraint_expr lhs = t->lhs;
2697 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2698 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2700 /* ANYTHING == ANYTHING is pointless. */
2701 if (lhs.var == anything_id && rhs.var == anything_id)
2704 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2705 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
2710 process_constraint (t);
2712 /* This can happen in our IR with things like n->a = *p */
2713 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2715 /* Split into tmp = *rhs, *lhs = tmp */
2716 tree rhsdecl = get_varinfo (rhs.var)->decl;
2717 tree pointertype = TREE_TYPE (rhsdecl);
2718 tree pointedtotype = TREE_TYPE (pointertype);
2719 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2720 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
2722 process_constraint (new_constraint (tmplhs, rhs));
2723 process_constraint (new_constraint (lhs, tmplhs));
2725 else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
2727 /* Split into tmp = &rhs, *lhs = tmp */
2728 tree rhsdecl = get_varinfo (rhs.var)->decl;
2729 tree pointertype = TREE_TYPE (rhsdecl);
2730 tree tmpvar = create_tmp_var_raw (pointertype, "derefaddrtmp");
2731 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
2733 process_constraint (new_constraint (tmplhs, rhs));
2734 process_constraint (new_constraint (lhs, tmplhs));
2738 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2739 VEC_safe_push (constraint_t, heap, constraints, t);
2743 /* Return true if T is a variable of a type that could contain
2747 could_have_pointers (tree t)
2749 tree type = TREE_TYPE (t);
2751 if (POINTER_TYPE_P (type)
2752 || AGGREGATE_TYPE_P (type))
2758 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2761 static HOST_WIDE_INT
2762 bitpos_of_field (const tree fdecl)
2765 if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2766 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2769 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2770 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2774 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2775 resulting constraint expressions in *RESULTS. */
2778 get_constraint_for_ptr_offset (tree ptr, tree offset,
2779 VEC (ce_s, heap) **results)
2781 struct constraint_expr *c;
2783 unsigned HOST_WIDE_INT rhsunitoffset, rhsoffset;
2785 /* If we do not do field-sensitive PTA adding offsets to pointers
2786 does not change the points-to solution. */
2787 if (!use_field_sensitive)
2789 get_constraint_for (ptr, results);
2793 /* If the offset is not a non-negative integer constant that fits
2794 in a HOST_WIDE_INT, we have to fall back to a conservative
2795 solution which includes all sub-fields of all pointed-to
2797 ??? As we do not have the ability to express this, fall back
2799 if (!host_integerp (offset, 1))
2801 struct constraint_expr temp;
2802 temp.var = anything_id;
2805 VEC_safe_push (ce_s, heap, *results, &temp);
2809 /* Make sure the bit-offset also fits. */
2810 rhsunitoffset = TREE_INT_CST_LOW (offset);
2811 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
2812 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
2814 struct constraint_expr temp;
2815 temp.var = anything_id;
2818 VEC_safe_push (ce_s, heap, *results, &temp);
2822 get_constraint_for (ptr, results);
2826 /* As we are eventually appending to the solution do not use
2827 VEC_iterate here. */
2828 n = VEC_length (ce_s, *results);
2829 for (j = 0; j < n; j++)
2832 c = VEC_index (ce_s, *results, j);
2833 curr = get_varinfo (c->var);
2835 if (c->type == ADDRESSOF
2836 && !curr->is_full_var)
2838 varinfo_t temp, curr = get_varinfo (c->var);
2840 /* Search the sub-field which overlaps with the
2841 pointed-to offset. As we deal with positive offsets
2842 only, we can start the search from the current variable. */
2843 temp = first_vi_for_offset (curr, curr->offset + rhsoffset);
2845 /* If the result is outside of the variable we have to provide
2846 a conservative result, as the variable is still reachable
2847 from the resulting pointer (even though it technically
2848 cannot point to anything). The last sub-field is such
2849 a conservative result.
2850 ??? If we always had a sub-field for &object + 1 then
2851 we could represent this in a more precise way. */
2855 while (temp->next != NULL)
2860 /* If the found variable is not exactly at the pointed to
2861 result, we have to include the next variable in the
2862 solution as well. Otherwise two increments by offset / 2
2863 do not result in the same or a conservative superset
2865 if (temp->offset != curr->offset + rhsoffset
2866 && temp->next != NULL)
2868 struct constraint_expr c2;
2869 c2.var = temp->next->id;
2870 c2.type = ADDRESSOF;
2872 VEC_safe_push (ce_s, heap, *results, &c2);
2877 else if (c->type == ADDRESSOF
2878 /* If this varinfo represents a full variable just use it. */
2879 && curr->is_full_var)
2882 c->offset = rhsoffset;
2887 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
2888 If address_p is true the result will be taken its address of. */
2891 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
2895 HOST_WIDE_INT bitsize = -1;
2896 HOST_WIDE_INT bitmaxsize = -1;
2897 HOST_WIDE_INT bitpos;
2899 struct constraint_expr *result;
2901 /* Some people like to do cute things like take the address of
2904 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2905 forzero = TREE_OPERAND (forzero, 0);
2907 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2909 struct constraint_expr temp;
2912 temp.var = integer_id;
2914 VEC_safe_push (ce_s, heap, *results, &temp);
2918 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2920 /* Pretend to take the address of the base, we'll take care of
2921 adding the required subset of sub-fields below. */
2922 get_constraint_for_1 (t, results, true);
2923 gcc_assert (VEC_length (ce_s, *results) == 1);
2924 result = VEC_last (ce_s, *results);
2926 /* This can also happen due to weird offsetof type macros. */
2927 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2928 result->type = SCALAR;
2930 if (result->type == SCALAR
2931 && get_varinfo (result->var)->is_full_var)
2932 /* For single-field vars do not bother about the offset. */
2934 else if (result->type == SCALAR)
2936 /* In languages like C, you can access one past the end of an
2937 array. You aren't allowed to dereference it, so we can
2938 ignore this constraint. When we handle pointer subtraction,
2939 we may have to do something cute here. */
2941 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
2944 /* It's also not true that the constraint will actually start at the
2945 right offset, it may start in some padding. We only care about
2946 setting the constraint to the first actual field it touches, so
2948 struct constraint_expr cexpr = *result;
2950 VEC_pop (ce_s, *results);
2952 for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
2954 if (ranges_overlap_p (curr->offset, curr->size,
2955 bitpos, bitmaxsize))
2957 cexpr.var = curr->id;
2958 VEC_safe_push (ce_s, heap, *results, &cexpr);
2963 /* If we are going to take the address of this field then
2964 to be able to compute reachability correctly add at least
2965 the last field of the variable. */
2967 && VEC_length (ce_s, *results) == 0)
2969 curr = get_varinfo (cexpr.var);
2970 while (curr->next != NULL)
2972 cexpr.var = curr->id;
2973 VEC_safe_push (ce_s, heap, *results, &cexpr);
2976 /* Assert that we found *some* field there. The user couldn't be
2977 accessing *only* padding. */
2978 /* Still the user could access one past the end of an array
2979 embedded in a struct resulting in accessing *only* padding. */
2980 gcc_assert (VEC_length (ce_s, *results) >= 1
2981 || ref_contains_array_ref (orig_t));
2983 else if (bitmaxsize == 0)
2985 if (dump_file && (dump_flags & TDF_DETAILS))
2986 fprintf (dump_file, "Access to zero-sized part of variable,"
2990 if (dump_file && (dump_flags & TDF_DETAILS))
2991 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2993 else if (bitmaxsize == -1)
2995 /* We can't handle DEREF constraints with unknown size, we'll
2996 get the wrong answer. Punt and return anything. */
2997 result->var = anything_id;
3001 result->offset = bitpos;
3005 /* Dereference the constraint expression CONS, and return the result.
3006 DEREF (ADDRESSOF) = SCALAR
3007 DEREF (SCALAR) = DEREF
3008 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3009 This is needed so that we can handle dereferencing DEREF constraints. */
3012 do_deref (VEC (ce_s, heap) **constraints)
3014 struct constraint_expr *c;
3017 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3019 if (c->type == SCALAR)
3021 else if (c->type == ADDRESSOF)
3023 else if (c->type == DEREF)
3025 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
3026 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
3027 process_constraint (new_constraint (tmplhs, *c));
3028 c->var = tmplhs.var;
3035 /* Given a tree T, return the constraint expression for it. */
3038 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3040 struct constraint_expr temp;
3042 /* x = integer is all glommed to a single variable, which doesn't
3043 point to anything by itself. That is, of course, unless it is an
3044 integer constant being treated as a pointer, in which case, we
3045 will return that this is really the addressof anything. This
3046 happens below, since it will fall into the default case. The only
3047 case we know something about an integer treated like a pointer is
3048 when it is the NULL pointer, and then we just say it points to
3051 Do not do that if -fno-delete-null-pointer-checks though, because
3052 in that case *NULL does not fail, so it _should_ alias *anything.
3053 It is not worth adding a new option or renaming the existing one,
3054 since this case is relatively obscure. */
3055 if (flag_delete_null_pointer_checks
3056 && TREE_CODE (t) == INTEGER_CST
3057 && integer_zerop (t))
3059 temp.var = nothing_id;
3060 temp.type = ADDRESSOF;
3062 VEC_safe_push (ce_s, heap, *results, &temp);
3066 /* String constants are read-only. */
3067 if (TREE_CODE (t) == STRING_CST)
3069 temp.var = readonly_id;
3072 VEC_safe_push (ce_s, heap, *results, &temp);
3076 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3078 case tcc_expression:
3080 switch (TREE_CODE (t))
3084 struct constraint_expr *c;
3086 tree exp = TREE_OPERAND (t, 0);
3088 get_constraint_for_1 (exp, results, true);
3090 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3092 if (c->type == DEREF)
3095 c->type = ADDRESSOF;
3106 switch (TREE_CODE (t))
3110 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3115 case ARRAY_RANGE_REF:
3117 get_constraint_for_component_ref (t, results, address_p);
3123 case tcc_exceptional:
3125 switch (TREE_CODE (t))
3129 get_constraint_for_ssa_var (t, results, address_p);
3136 case tcc_declaration:
3138 get_constraint_for_ssa_var (t, results, address_p);
3144 /* The default fallback is a constraint from anything. */
3145 temp.type = ADDRESSOF;
3146 temp.var = anything_id;
3148 VEC_safe_push (ce_s, heap, *results, &temp);
3151 /* Given a gimple tree T, return the constraint expression vector for it. */
3154 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3156 gcc_assert (VEC_length (ce_s, *results) == 0);
3158 get_constraint_for_1 (t, results, false);
3161 /* Handle the structure copy case where we have a simple structure copy
3162 between LHS and RHS that is of SIZE (in bits)
3164 For each field of the lhs variable (lhsfield)
3165 For each field of the rhs variable at lhsfield.offset (rhsfield)
3166 add the constraint lhsfield = rhsfield
3168 If we fail due to some kind of type unsafety or other thing we
3169 can't handle, return false. We expect the caller to collapse the
3170 variable in that case. */
3173 do_simple_structure_copy (const struct constraint_expr lhs,
3174 const struct constraint_expr rhs,
3175 const unsigned HOST_WIDE_INT size)
3177 varinfo_t p = get_varinfo (lhs.var);
3178 unsigned HOST_WIDE_INT pstart, last;
3180 last = p->offset + size;
3181 for (; p && p->offset < last; p = p->next)
3184 struct constraint_expr templhs = lhs;
3185 struct constraint_expr temprhs = rhs;
3186 unsigned HOST_WIDE_INT fieldoffset;
3188 templhs.var = p->id;
3189 q = get_varinfo (temprhs.var);
3190 fieldoffset = p->offset - pstart;
3191 q = first_vi_for_offset (q, q->offset + fieldoffset);
3194 temprhs.var = q->id;
3195 process_constraint (new_constraint (templhs, temprhs));
3201 /* Handle the structure copy case where we have a structure copy between a
3202 aggregate on the LHS and a dereference of a pointer on the RHS
3203 that is of SIZE (in bits)
3205 For each field of the lhs variable (lhsfield)
3206 rhs.offset = lhsfield->offset
3207 add the constraint lhsfield = rhs
3211 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
3212 const struct constraint_expr rhs,
3213 const unsigned HOST_WIDE_INT size)
3215 varinfo_t p = get_varinfo (lhs.var);
3216 unsigned HOST_WIDE_INT pstart,last;
3218 last = p->offset + size;
3220 for (; p && p->offset < last; p = p->next)
3223 struct constraint_expr templhs = lhs;
3224 struct constraint_expr temprhs = rhs;
3225 unsigned HOST_WIDE_INT fieldoffset;
3228 if (templhs.type == SCALAR)
3229 templhs.var = p->id;
3231 templhs.offset = p->offset;
3233 q = get_varinfo (temprhs.var);
3234 fieldoffset = p->offset - pstart;
3235 temprhs.offset += fieldoffset;
3236 process_constraint (new_constraint (templhs, temprhs));
3240 /* Handle the structure copy case where we have a structure copy
3241 between an aggregate on the RHS and a dereference of a pointer on
3242 the LHS that is of SIZE (in bits)
3244 For each field of the rhs variable (rhsfield)
3245 lhs.offset = rhsfield->offset
3246 add the constraint lhs = rhsfield
3250 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
3251 const struct constraint_expr rhs,
3252 const unsigned HOST_WIDE_INT size)
3254 varinfo_t p = get_varinfo (rhs.var);
3255 unsigned HOST_WIDE_INT pstart,last;
3257 last = p->offset + size;
3259 for (; p && p->offset < last; p = p->next)
3262 struct constraint_expr templhs = lhs;
3263 struct constraint_expr temprhs = rhs;
3264 unsigned HOST_WIDE_INT fieldoffset;
3267 if (temprhs.type == SCALAR)
3268 temprhs.var = p->id;
3270 temprhs.offset = p->offset;
3272 q = get_varinfo (templhs.var);
3273 fieldoffset = p->offset - pstart;
3274 templhs.offset += fieldoffset;
3275 process_constraint (new_constraint (templhs, temprhs));
3279 /* Sometimes, frontends like to give us bad type information. This
3280 function will collapse all the fields from VAR to the end of VAR,
3281 into VAR, so that we treat those fields as a single variable.
3282 We return the variable they were collapsed into. */
3285 collapse_rest_of_var (unsigned int var)
3287 varinfo_t currvar = get_varinfo (var);
3290 for (field = currvar->next; field; field = field->next)
3293 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
3294 field->name, currvar->name);
3296 gcc_assert (field->collapsed_to == 0);
3297 field->collapsed_to = currvar->id;
3300 currvar->next = NULL;
3301 currvar->size = currvar->fullsize - currvar->offset;
3306 /* Handle aggregate copies by expanding into copies of the respective
3307 fields of the structures. */
3310 do_structure_copy (tree lhsop, tree rhsop)
3312 struct constraint_expr lhs, rhs, tmp;
3313 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3315 unsigned HOST_WIDE_INT lhssize;
3316 unsigned HOST_WIDE_INT rhssize;
3318 /* Pretend we are taking the address of the constraint exprs.
3319 We deal with walking the sub-fields ourselves. */
3320 get_constraint_for_1 (lhsop, &lhsc, true);
3321 get_constraint_for_1 (rhsop, &rhsc, true);
3322 gcc_assert (VEC_length (ce_s, lhsc) == 1);
3323 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3324 lhs = *(VEC_last (ce_s, lhsc));
3325 rhs = *(VEC_last (ce_s, rhsc));
3327 VEC_free (ce_s, heap, lhsc);
3328 VEC_free (ce_s, heap, rhsc);
3330 /* If we have special var = x, swap it around. */
3331 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
3338 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
3339 possible it's something we could handle. However, most cases falling
3340 into this are dealing with transparent unions, which are slightly
3342 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
3344 rhs.type = ADDRESSOF;
3345 rhs.var = anything_id;
3348 /* If the RHS is a special var, or an addressof, set all the LHS fields to
3349 that special var. */
3350 if (rhs.var <= integer_id)
3352 for (p = get_varinfo (lhs.var); p; p = p->next)
3354 struct constraint_expr templhs = lhs;
3355 struct constraint_expr temprhs = rhs;
3357 if (templhs.type == SCALAR )
3358 templhs.var = p->id;
3360 templhs.offset += p->offset;
3361 process_constraint (new_constraint (templhs, temprhs));
3366 tree rhstype = TREE_TYPE (rhsop);
3367 tree lhstype = TREE_TYPE (lhsop);
3371 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
3372 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
3374 /* If we have a variably sized types on the rhs or lhs, and a deref
3375 constraint, add the constraint, lhsconstraint = &ANYTHING.
3376 This is conservatively correct because either the lhs is an unknown
3377 sized var (if the constraint is SCALAR), or the lhs is a DEREF
3378 constraint, and every variable it can point to must be unknown sized
3379 anyway, so we don't need to worry about fields at all. */
3380 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
3381 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
3383 rhs.var = anything_id;
3384 rhs.type = ADDRESSOF;
3386 process_constraint (new_constraint (lhs, rhs));
3390 /* The size only really matters insofar as we don't set more or less of
3391 the variable. If we hit an unknown size var, the size should be the
3392 whole darn thing. */
3393 if (get_varinfo (rhs.var)->is_unknown_size_var)
3396 rhssize = TREE_INT_CST_LOW (rhstypesize);
3398 if (get_varinfo (lhs.var)->is_unknown_size_var)
3401 lhssize = TREE_INT_CST_LOW (lhstypesize);
3404 if (rhs.type == SCALAR && lhs.type == SCALAR)
3406 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
3408 lhs.var = collapse_rest_of_var (lhs.var);
3409 rhs.var = collapse_rest_of_var (rhs.var);
3414 process_constraint (new_constraint (lhs, rhs));
3417 else if (lhs.type != DEREF && rhs.type == DEREF)
3418 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3419 else if (lhs.type == DEREF && rhs.type != DEREF)
3420 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3423 tree pointedtotype = lhstype;
3426 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3427 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
3428 do_structure_copy (tmpvar, rhsop);
3429 do_structure_copy (lhsop, tmpvar);
3434 /* Create a constraint ID = OP. */
3437 make_constraint_to (unsigned id, tree op)
3439 VEC(ce_s, heap) *rhsc = NULL;
3440 struct constraint_expr *c;
3441 struct constraint_expr includes;
3445 includes.offset = 0;
3446 includes.type = SCALAR;
3448 get_constraint_for (op, &rhsc);
3449 for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3450 process_constraint (new_constraint (includes, *c));
3451 VEC_free (ce_s, heap, rhsc);
3454 /* Make constraints necessary to make OP escape. */
3457 make_escape_constraint (tree op)
3459 make_constraint_to (escaped_id, op);
3462 /* For non-IPA mode, generate constraints necessary for a call on the
3466 handle_rhs_call (gimple stmt)
3470 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3472 tree arg = gimple_call_arg (stmt, i);
3474 /* Find those pointers being passed, and make sure they end up
3475 pointing to anything. */
3476 if (could_have_pointers (arg))
3477 make_escape_constraint (arg);
3480 /* The static chain escapes as well. */
3481 if (gimple_call_chain (stmt))
3482 make_escape_constraint (gimple_call_chain (stmt));
3485 /* For non-IPA mode, generate constraints necessary for a call
3486 that returns a pointer and assigns it to LHS. This simply makes
3487 the LHS point to global and escaped variables. */
3490 handle_lhs_call (tree lhs, int flags)
3492 VEC(ce_s, heap) *lhsc = NULL;
3493 struct constraint_expr rhsc;
3495 struct constraint_expr *lhsp;
3497 get_constraint_for (lhs, &lhsc);
3499 if (flags & ECF_MALLOC)
3501 tree heapvar = heapvar_lookup (lhs);
3504 if (heapvar == NULL)
3506 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
3507 DECL_EXTERNAL (heapvar) = 1;
3508 get_var_ann (heapvar)->is_heapvar = 1;
3509 if (gimple_referenced_vars (cfun))
3510 add_referenced_var (heapvar);
3511 heapvar_insert (lhs, heapvar);
3514 rhsc.var = create_variable_info_for (heapvar,
3515 alias_get_name (heapvar));
3516 vi = get_varinfo (rhsc.var);
3517 vi->is_artificial_var = 1;
3518 vi->is_heap_var = 1;
3519 rhsc.type = ADDRESSOF;
3524 rhsc.var = escaped_id;
3526 rhsc.type = ADDRESSOF;
3528 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3529 process_constraint (new_constraint (*lhsp, rhsc));
3530 VEC_free (ce_s, heap, lhsc);
3533 /* For non-IPA mode, generate constraints necessary for a call of a
3534 const function that returns a pointer in the statement STMT. */
3537 handle_const_call (gimple stmt)
3539 tree lhs = gimple_call_lhs (stmt);
3540 VEC(ce_s, heap) *lhsc = NULL;
3541 struct constraint_expr rhsc;
3543 struct constraint_expr *lhsp;
3545 struct constraint_expr tmpc;
3547 get_constraint_for (lhs, &lhsc);
3549 /* If this is a nested function then it can return anything. */
3550 if (gimple_call_chain (stmt))
3552 rhsc.var = anything_id;
3554 rhsc.type = ADDRESSOF;
3555 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3556 process_constraint (new_constraint (*lhsp, rhsc));
3557 VEC_free (ce_s, heap, lhsc);
3561 /* We always use a temporary here, otherwise we end up with a quadratic
3562 amount of constraints for
3563 large_struct = const_call (large_struct);
3564 in field-sensitive PTA. */
3565 tmpvar = create_tmp_var_raw (ptr_type_node, "consttmp");
3566 tmpc = get_constraint_exp_for_temp (tmpvar);
3568 /* May return addresses of globals. */
3569 rhsc.var = nonlocal_id;
3571 rhsc.type = ADDRESSOF;
3572 process_constraint (new_constraint (tmpc, rhsc));
3574 /* May return arguments. */
3575 for (k = 0; k < gimple_call_num_args (stmt); ++k)
3577 tree arg = gimple_call_arg (stmt, k);
3579 if (could_have_pointers (arg))
3581 VEC(ce_s, heap) *argc = NULL;
3582 struct constraint_expr *argp;
3585 get_constraint_for (arg, &argc);
3586 for (i = 0; VEC_iterate (ce_s, argc, i, argp); i++)
3587 process_constraint (new_constraint (tmpc, *argp));
3588 VEC_free (ce_s, heap, argc);
3592 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3593 process_constraint (new_constraint (*lhsp, tmpc));
3595 VEC_free (ce_s, heap, lhsc);
3598 /* For non-IPA mode, generate constraints necessary for a call to a
3599 pure function in statement STMT. */
3602 handle_pure_call (gimple stmt)
3606 /* Memory reached from pointer arguments is call-used. */
3607 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3609 tree arg = gimple_call_arg (stmt, i);
3611 if (could_have_pointers (arg))
3612 make_constraint_to (callused_id, arg);
3615 /* The static chain is used as well. */
3616 if (gimple_call_chain (stmt))
3617 make_constraint_to (callused_id, gimple_call_chain (stmt));
3619 /* If the call returns a pointer it may point to reachable memory
3620 from the arguments. Not so for malloc functions though. */
3621 if (gimple_call_lhs (stmt)
3622 && could_have_pointers (gimple_call_lhs (stmt))
3623 && !(gimple_call_flags (stmt) & ECF_MALLOC))
3625 tree lhs = gimple_call_lhs (stmt);
3626 VEC(ce_s, heap) *lhsc = NULL;
3627 struct constraint_expr rhsc;
3628 struct constraint_expr *lhsp;
3631 get_constraint_for (lhs, &lhsc);
3633 /* If this is a nested function then it can return anything. */
3634 if (gimple_call_chain (stmt))
3636 rhsc.var = anything_id;
3638 rhsc.type = ADDRESSOF;
3639 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3640 process_constraint (new_constraint (*lhsp, rhsc));
3641 VEC_free (ce_s, heap, lhsc);
3645 /* Else just add the call-used memory here. Escaped variables
3646 and globals will be dealt with in handle_lhs_call. */
3647 rhsc.var = callused_id;
3649 rhsc.type = ADDRESSOF;
3650 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3651 process_constraint (new_constraint (*lhsp, rhsc));
3652 VEC_free (ce_s, heap, lhsc);
3656 /* Walk statement T setting up aliasing constraints according to the
3657 references found in T. This function is the main part of the
3658 constraint builder. AI points to auxiliary alias information used
3659 when building alias sets and computing alias grouping heuristics. */
3662 find_func_aliases (gimple origt)
3665 VEC(ce_s, heap) *lhsc = NULL;
3666 VEC(ce_s, heap) *rhsc = NULL;
3667 struct constraint_expr *c;
3668 enum escape_type stmt_escape_type;
3670 /* Now build constraints expressions. */
3671 if (gimple_code (t) == GIMPLE_PHI)
3673 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (gimple_phi_result (t))));
3675 /* Only care about pointers and structures containing
3677 if (could_have_pointers (gimple_phi_result (t)))
3682 /* For a phi node, assign all the arguments to
3684 get_constraint_for (gimple_phi_result (t), &lhsc);
3685 for (i = 0; i < gimple_phi_num_args (t); i++)
3688 tree strippedrhs = PHI_ARG_DEF (t, i);
3690 STRIP_NOPS (strippedrhs);
3691 rhstype = TREE_TYPE (strippedrhs);
3692 get_constraint_for (gimple_phi_arg_def (t, i), &rhsc);
3694 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3696 struct constraint_expr *c2;
3697 while (VEC_length (ce_s, rhsc) > 0)
3699 c2 = VEC_last (ce_s, rhsc);
3700 process_constraint (new_constraint (*c, *c2));
3701 VEC_pop (ce_s, rhsc);
3707 /* In IPA mode, we need to generate constraints to pass call
3708 arguments through their calls. There are two cases,
3709 either a GIMPLE_CALL returning a value, or just a plain
3710 GIMPLE_CALL when we are not.
3712 In non-ipa mode, we need to generate constraints for each
3713 pointer passed by address. */
3714 else if (is_gimple_call (t))
3718 int flags = gimple_call_flags (t);
3720 /* Const functions can return their arguments and addresses
3721 of global memory but not of escaped memory. */
3722 if (flags & ECF_CONST)
3724 if (gimple_call_lhs (t)
3725 && could_have_pointers (gimple_call_lhs (t)))
3726 handle_const_call (t);
3728 /* Pure functions can return addresses in and of memory
3729 reachable from their arguments, but they are not an escape
3730 point for reachable memory of their arguments. */
3731 else if (flags & ECF_PURE)
3733 handle_pure_call (t);
3734 if (gimple_call_lhs (t)
3735 && could_have_pointers (gimple_call_lhs (t)))
3736 handle_lhs_call (gimple_call_lhs (t), flags);
3740 handle_rhs_call (t);
3741 if (gimple_call_lhs (t)
3742 && could_have_pointers (gimple_call_lhs (t)))
3743 handle_lhs_call (gimple_call_lhs (t), flags);
3754 lhsop = gimple_call_lhs (t);
3755 decl = gimple_call_fndecl (t);
3757 /* If we can directly resolve the function being called, do so.
3758 Otherwise, it must be some sort of indirect expression that
3759 we should still be able to handle. */
3761 fi = get_vi_for_tree (decl);
3764 decl = gimple_call_fn (t);
3765 fi = get_vi_for_tree (decl);
3768 /* Assign all the passed arguments to the appropriate incoming
3769 parameters of the function. */
3770 for (j = 0; j < gimple_call_num_args (t); j++)
3772 struct constraint_expr lhs ;
3773 struct constraint_expr *rhsp;
3774 tree arg = gimple_call_arg (t, j);
3776 get_constraint_for (arg, &rhsc);
3777 if (TREE_CODE (decl) != FUNCTION_DECL)
3786 lhs.var = first_vi_for_offset (fi, i)->id;
3789 while (VEC_length (ce_s, rhsc) != 0)
3791 rhsp = VEC_last (ce_s, rhsc);
3792 process_constraint (new_constraint (lhs, *rhsp));
3793 VEC_pop (ce_s, rhsc);
3798 /* If we are returning a value, assign it to the result. */
3801 struct constraint_expr rhs;
3802 struct constraint_expr *lhsp;
3805 get_constraint_for (lhsop, &lhsc);
3806 if (TREE_CODE (decl) != FUNCTION_DECL)
3815 rhs.var = first_vi_for_offset (fi, i)->id;
3818 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3819 process_constraint (new_constraint (*lhsp, rhs));
3823 /* Otherwise, just a regular assignment statement. Only care about
3824 operations with pointer result, others are dealt with as escape
3825 points if they have pointer operands. */
3826 else if (is_gimple_assign (t)
3827 && could_have_pointers (gimple_assign_lhs (t)))
3829 /* Otherwise, just a regular assignment statement. */
3830 tree lhsop = gimple_assign_lhs (t);
3831 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
3833 if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
3834 do_structure_copy (lhsop, rhsop);
3838 struct constraint_expr temp;
3839 get_constraint_for (lhsop, &lhsc);
3841 if (gimple_assign_rhs_code (t) == POINTER_PLUS_EXPR)
3842 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
3843 gimple_assign_rhs2 (t), &rhsc);
3844 else if ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
3845 && !(POINTER_TYPE_P (gimple_expr_type (t))
3846 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
3847 || gimple_assign_single_p (t))
3848 get_constraint_for (rhsop, &rhsc);
3851 temp.type = ADDRESSOF;
3852 temp.var = anything_id;
3854 VEC_safe_push (ce_s, heap, rhsc, &temp);
3856 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3858 struct constraint_expr *c2;
3861 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3862 process_constraint (new_constraint (*c, *c2));
3866 else if (gimple_code (t) == GIMPLE_CHANGE_DYNAMIC_TYPE)
3870 get_constraint_for (gimple_cdt_location (t), &lhsc);
3871 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); ++j)
3872 get_varinfo (c->var)->no_tbaa_pruning = true;
3875 stmt_escape_type = is_escape_site (t);
3876 if (stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
3878 gcc_assert (is_gimple_assign (t));
3879 if (gimple_assign_rhs_code (t) == ADDR_EXPR)
3881 tree rhs = gimple_assign_rhs1 (t);
3882 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3885 || !is_global_var (base)))
3886 make_escape_constraint (rhs);
3888 else if (get_gimple_rhs_class (gimple_assign_rhs_code (t))
3889 == GIMPLE_SINGLE_RHS)
3891 if (could_have_pointers (gimple_assign_rhs1 (t)))
3892 make_escape_constraint (gimple_assign_rhs1 (t));
3897 else if (stmt_escape_type == ESCAPE_BAD_CAST)
3899 gcc_assert (is_gimple_assign (t));
3900 gcc_assert (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
3901 || gimple_assign_rhs_code (t) == VIEW_CONVERT_EXPR);
3902 make_escape_constraint (gimple_assign_rhs1 (t));
3904 else if (stmt_escape_type == ESCAPE_TO_ASM)
3907 for (i = 0; i < gimple_asm_noutputs (t); ++i)
3909 tree op = TREE_VALUE (gimple_asm_output_op (t, i));
3910 if (op && could_have_pointers (op))
3911 /* Strictly we'd only need the constraints from ESCAPED and
3913 make_escape_constraint (op);
3915 for (i = 0; i < gimple_asm_ninputs (t); ++i)
3917 tree op = TREE_VALUE (gimple_asm_input_op (t, i));
3918 if (op && could_have_pointers (op))
3919 /* Strictly we'd only need the constraint to ESCAPED. */
3920 make_escape_constraint (op);
3924 /* After promoting variables and computing aliasing we will
3925 need to re-scan most statements. FIXME: Try to minimize the
3926 number of statements re-scanned. It's not really necessary to
3927 re-scan *all* statements. */
3929 gimple_set_modified (origt, true);
3930 VEC_free (ce_s, heap, rhsc);
3931 VEC_free (ce_s, heap, lhsc);
3935 /* Find the first varinfo in the same variable as START that overlaps with
3937 Effectively, walk the chain of fields for the variable START to find the
3938 first field that overlaps with OFFSET.
3939 Return NULL if we can't find one. */
3942 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3944 varinfo_t curr = start;
3947 /* We may not find a variable in the field list with the actual
3948 offset when when we have glommed a structure to a variable.
3949 In that case, however, offset should still be within the size
3951 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3959 /* Insert the varinfo FIELD into the field list for BASE, at the front
3963 insert_into_field_list (varinfo_t base, varinfo_t field)
3965 varinfo_t prev = base;
3966 varinfo_t curr = base->next;
3972 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3976 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
3978 varinfo_t prev = base;
3979 varinfo_t curr = base->next;
3990 if (field->offset <= curr->offset)
3995 field->next = prev->next;
4000 /* This structure is used during pushing fields onto the fieldstack
4001 to track the offset of the field, since bitpos_of_field gives it
4002 relative to its immediate containing type, and we want it relative
4003 to the ultimate containing object. */
4007 /* Offset from the base of the base containing object to this field. */
4008 HOST_WIDE_INT offset;
4010 /* Size, in bits, of the field. */
4011 unsigned HOST_WIDE_INT size;
4013 unsigned has_unknown_size : 1;
4015 unsigned may_have_pointers : 1;
4017 typedef struct fieldoff fieldoff_s;
4019 DEF_VEC_O(fieldoff_s);
4020 DEF_VEC_ALLOC_O(fieldoff_s,heap);
4022 /* qsort comparison function for two fieldoff's PA and PB */
4025 fieldoff_compare (const void *pa, const void *pb)
4027 const fieldoff_s *foa = (const fieldoff_s *)pa;
4028 const fieldoff_s *fob = (const fieldoff_s *)pb;
4029 unsigned HOST_WIDE_INT foasize, fobsize;
4031 if (foa->offset < fob->offset)
4033 else if (foa->offset > fob->offset)
4036 foasize = foa->size;
4037 fobsize = fob->size;
4038 if (foasize < fobsize)
4040 else if (foasize > fobsize)
4045 /* Sort a fieldstack according to the field offset and sizes. */
4047 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
4049 qsort (VEC_address (fieldoff_s, fieldstack),
4050 VEC_length (fieldoff_s, fieldstack),
4051 sizeof (fieldoff_s),
4055 /* Return true if V is a tree that we can have subvars for.
4056 Normally, this is any aggregate type. Also complex
4057 types which are not gimple registers can have subvars. */
4060 var_can_have_subvars (const_tree v)
4062 /* Volatile variables should never have subvars. */
4063 if (TREE_THIS_VOLATILE (v))
4066 /* Non decls or memory tags can never have subvars. */
4067 if (!DECL_P (v) || MTAG_P (v))
4070 /* Aggregates without overlapping fields can have subvars. */
4071 if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
4077 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4078 the fields of TYPE onto fieldstack, recording their offsets along
4081 OFFSET is used to keep track of the offset in this entire
4082 structure, rather than just the immediately containing structure.
4083 Returns the number of fields pushed. */
4086 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
4087 HOST_WIDE_INT offset)
4092 if (TREE_CODE (type) != RECORD_TYPE)
4095 /* If the vector of fields is growing too big, bail out early.
4096 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4098 if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
4101 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
4102 if (TREE_CODE (field) == FIELD_DECL)
4106 HOST_WIDE_INT foff = bitpos_of_field (field);
4108 if (!var_can_have_subvars (field)
4109 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
4110 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
4112 else if (!(pushed = push_fields_onto_fieldstack
4113 (TREE_TYPE (field), fieldstack, offset + foff))
4114 && (DECL_SIZE (field)
4115 && !integer_zerop (DECL_SIZE (field))))
4116 /* Empty structures may have actual size, like in C++. So
4117 see if we didn't push any subfields and the size is
4118 nonzero, push the field onto the stack. */
4123 fieldoff_s *pair = NULL;
4124 bool has_unknown_size = false;
4126 if (!VEC_empty (fieldoff_s, *fieldstack))
4127 pair = VEC_last (fieldoff_s, *fieldstack);
4129 if (!DECL_SIZE (field)
4130 || !host_integerp (DECL_SIZE (field), 1))
4131 has_unknown_size = true;
4133 /* If adjacent fields do not contain pointers merge them. */
4135 && !pair->may_have_pointers
4136 && !could_have_pointers (field)
4137 && !pair->has_unknown_size
4138 && !has_unknown_size
4139 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
4141 pair = VEC_last (fieldoff_s, *fieldstack);
4142 pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
4146 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
4147 pair->offset = offset + foff;
4148 pair->has_unknown_size = has_unknown_size;
4149 if (!has_unknown_size)
4150 pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
4153 pair->may_have_pointers = could_have_pointers (field);
4164 /* Create a constraint ID = &FROM. */
4167 make_constraint_from (varinfo_t vi, int from)
4169 struct constraint_expr lhs, rhs;
4177 rhs.type = ADDRESSOF;
4178 process_constraint (new_constraint (lhs, rhs));
4181 /* Count the number of arguments DECL has, and set IS_VARARGS to true
4182 if it is a varargs function. */
4185 count_num_arguments (tree decl, bool *is_varargs)
4190 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
4194 if (TREE_VALUE (t) == void_type_node)
4204 /* Creation function node for DECL, using NAME, and return the index
4205 of the variable we've created for the function. */
4208 create_function_info_for (tree decl, const char *name)
4210 unsigned int index = VEC_length (varinfo_t, varmap);
4214 bool is_varargs = false;
4216 /* Create the variable info. */
4218 vi = new_var_info (decl, index, name);
4222 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
4223 insert_vi_for_tree (vi->decl, vi);
4224 VEC_safe_push (varinfo_t, heap, varmap, vi);
4228 /* If it's varargs, we don't know how many arguments it has, so we
4234 vi->is_unknown_size_var = true;
4239 arg = DECL_ARGUMENTS (decl);
4241 /* Set up variables for each argument. */
4242 for (i = 1; i < vi->fullsize; i++)
4245 const char *newname;
4247 unsigned int newindex;
4248 tree argdecl = decl;
4253 newindex = VEC_length (varinfo_t, varmap);
4254 asprintf (&tempname, "%s.arg%d", name, i-1);
4255 newname = ggc_strdup (tempname);
4258 argvi = new_var_info (argdecl, newindex, newname);
4259 argvi->decl = argdecl;
4260 VEC_safe_push (varinfo_t, heap, varmap, argvi);
4263 argvi->is_full_var = true;
4264 argvi->fullsize = vi->fullsize;
4265 insert_into_field_list_sorted (vi, argvi);
4266 stats.total_vars ++;
4269 insert_vi_for_tree (arg, argvi);
4270 arg = TREE_CHAIN (arg);
4274 /* Create a variable for the return var. */
4275 if (DECL_RESULT (decl) != NULL
4276 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
4279 const char *newname;
4281 unsigned int newindex;
4282 tree resultdecl = decl;
4286 if (DECL_RESULT (decl))
4287 resultdecl = DECL_RESULT (decl);
4289 newindex = VEC_length (varinfo_t, varmap);
4290 asprintf (&tempname, "%s.result", name);
4291 newname = ggc_strdup (tempname);
4294 resultvi = new_var_info (resultdecl, newindex, newname);
4295 resultvi->decl = resultdecl;
4296 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
4297 resultvi->offset = i;
4299 resultvi->fullsize = vi->fullsize;
4300 resultvi->is_full_var = true;
4301 insert_into_field_list_sorted (vi, resultvi);
4302 stats.total_vars ++;
4303 if (DECL_RESULT (decl))
4304 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
4310 /* Return true if FIELDSTACK contains fields that overlap.
4311 FIELDSTACK is assumed to be sorted by offset. */
4314 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
4316 fieldoff_s *fo = NULL;
4318 HOST_WIDE_INT lastoffset = -1;
4320 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4322 if (fo->offset == lastoffset)
4324 lastoffset = fo->offset;
4329 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4330 This will also create any varinfo structures necessary for fields
4334 create_variable_info_for (tree decl, const char *name)
4336 unsigned int index = VEC_length (varinfo_t, varmap);
4338 tree decl_type = TREE_TYPE (decl);
4339 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
4340 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
4341 VEC (fieldoff_s,heap) *fieldstack = NULL;
4343 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4344 return create_function_info_for (decl, name);
4346 if (var_can_have_subvars (decl) && use_field_sensitive
4348 || var_ann (decl)->noalias_state == 0)
4350 || !var_ann (decl)->is_heapvar))
4351 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
4353 /* If the variable doesn't have subvars, we may end up needing to
4354 sort the field list and create fake variables for all the
4356 vi = new_var_info (decl, index, name);
4360 || !host_integerp (declsize, 1))
4362 vi->is_unknown_size_var = true;
4368 vi->fullsize = TREE_INT_CST_LOW (declsize);
4369 vi->size = vi->fullsize;
4372 insert_vi_for_tree (vi->decl, vi);
4373 VEC_safe_push (varinfo_t, heap, varmap, vi);
4374 if (is_global && (!flag_whole_program || !in_ipa_mode)
4375 && could_have_pointers (decl))
4378 && var_ann (decl)->noalias_state == NO_ALIAS_ANYTHING)
4379 make_constraint_from (vi, vi->id);
4381 make_constraint_from (vi, escaped_id);
4385 if (use_field_sensitive
4386 && !vi->is_unknown_size_var
4387 && var_can_have_subvars (decl)
4388 && VEC_length (fieldoff_s, fieldstack) > 1
4389 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4391 unsigned int newindex = VEC_length (varinfo_t, varmap);
4392 fieldoff_s *fo = NULL;
4393 bool notokay = false;
4396 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4398 if (fo->has_unknown_size
4406 /* We can't sort them if we have a field with a variable sized type,
4407 which will make notokay = true. In that case, we are going to return
4408 without creating varinfos for the fields anyway, so sorting them is a
4412 sort_fieldstack (fieldstack);
4413 /* Due to some C++ FE issues, like PR 22488, we might end up
4414 what appear to be overlapping fields even though they,
4415 in reality, do not overlap. Until the C++ FE is fixed,
4416 we will simply disable field-sensitivity for these cases. */
4417 notokay = check_for_overlaps (fieldstack);
4421 if (VEC_length (fieldoff_s, fieldstack) != 0)
4422 fo = VEC_index (fieldoff_s, fieldstack, 0);
4424 if (fo == NULL || notokay)
4426 vi->is_unknown_size_var = 1;
4429 vi->is_full_var = true;
4430 VEC_free (fieldoff_s, heap, fieldstack);
4434 vi->size = fo->size;
4435 vi->offset = fo->offset;
4436 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4437 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4441 const char *newname = "NULL";
4444 newindex = VEC_length (varinfo_t, varmap);
4447 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
4448 "+" HOST_WIDE_INT_PRINT_DEC,
4449 vi->name, fo->offset, fo->size);
4450 newname = ggc_strdup (tempname);
4453 newvi = new_var_info (decl, newindex, newname);
4454 newvi->offset = fo->offset;
4455 newvi->size = fo->size;
4456 newvi->fullsize = vi->fullsize;
4457 insert_into_field_list (vi, newvi);
4458 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4459 if (is_global && (!flag_whole_program || !in_ipa_mode)
4460 && fo->may_have_pointers)
4461 make_constraint_from (newvi, escaped_id);
4467 vi->is_full_var = true;
4469 VEC_free (fieldoff_s, heap, fieldstack);
4474 /* Print out the points-to solution for VAR to FILE. */
4477 dump_solution_for_var (FILE *file, unsigned int var)
4479 varinfo_t vi = get_varinfo (var);
4483 if (find (var) != var)
4485 varinfo_t vipt = get_varinfo (find (var));
4486 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4490 fprintf (file, "%s = { ", vi->name);
4491 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4493 fprintf (file, "%s ", get_varinfo (i)->name);
4495 fprintf (file, "}");
4496 if (vi->no_tbaa_pruning)
4497 fprintf (file, " no-tbaa-pruning");
4498 fprintf (file, "\n");
4502 /* Print the points-to solution for VAR to stdout. */
4505 debug_solution_for_var (unsigned int var)
4507 dump_solution_for_var (stdout, var);
4510 /* Create varinfo structures for all of the variables in the
4511 function for intraprocedural mode. */
4514 intra_create_variable_infos (void)
4517 struct constraint_expr lhs, rhs;
4519 /* For each incoming pointer argument arg, create the constraint ARG
4520 = NONLOCAL or a dummy variable if flag_argument_noalias is set. */
4521 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4525 if (!could_have_pointers (t))
4528 /* If flag_argument_noalias is set, then function pointer
4529 arguments are guaranteed not to point to each other. In that
4530 case, create an artificial variable PARM_NOALIAS and the
4531 constraint ARG = &PARM_NOALIAS. */
4532 if (POINTER_TYPE_P (TREE_TYPE (t)) && flag_argument_noalias > 0)
4535 tree heapvar = heapvar_lookup (t);
4539 lhs.var = get_vi_for_tree (t)->id;
4541 if (heapvar == NULL_TREE)
4544 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4546 DECL_EXTERNAL (heapvar) = 1;
4547 if (gimple_referenced_vars (cfun))
4548 add_referenced_var (heapvar);
4550 heapvar_insert (t, heapvar);
4552 ann = get_var_ann (heapvar);
4553 ann->is_heapvar = 1;
4554 if (flag_argument_noalias == 1)
4555 ann->noalias_state = NO_ALIAS;
4556 else if (flag_argument_noalias == 2)
4557 ann->noalias_state = NO_ALIAS_GLOBAL;
4558 else if (flag_argument_noalias == 3)
4559 ann->noalias_state = NO_ALIAS_ANYTHING;
4564 vi = get_vi_for_tree (heapvar);
4565 vi->is_artificial_var = 1;
4566 vi->is_heap_var = 1;
4568 rhs.type = ADDRESSOF;
4570 for (p = get_varinfo (lhs.var); p; p = p->next)
4572 struct constraint_expr temp = lhs;
4574 process_constraint (new_constraint (temp, rhs));
4579 varinfo_t arg_vi = get_vi_for_tree (t);
4581 for (p = arg_vi; p; p = p->next)
4582 make_constraint_from (p, nonlocal_id);
4586 /* Add a constraint for a result decl that is passed by reference. */
4587 if (DECL_RESULT (cfun->decl)
4588 && DECL_BY_REFERENCE (DECL_RESULT (cfun->decl)))
4590 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
4592 for (p = result_vi; p; p = p->next)
4593 make_constraint_from (p, nonlocal_id);
4596 /* Add a constraint for the incoming static chain parameter. */
4597 if (cfun->static_chain_decl != NULL_TREE)
4599 varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
4601 for (p = chain_vi; p; p = p->next)
4602 make_constraint_from (p, nonlocal_id);
4606 /* Structure used to put solution bitmaps in a hashtable so they can
4607 be shared among variables with the same points-to set. */
4609 typedef struct shared_bitmap_info
4613 } *shared_bitmap_info_t;
4614 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
4616 static htab_t shared_bitmap_table;
4618 /* Hash function for a shared_bitmap_info_t */
4621 shared_bitmap_hash (const void *p)
4623 const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
4624 return bi->hashcode;
4627 /* Equality function for two shared_bitmap_info_t's. */
4630 shared_bitmap_eq (const void *p1, const void *p2)
4632 const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
4633 const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
4634 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
4637 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4638 existing instance if there is one, NULL otherwise. */
4641 shared_bitmap_lookup (bitmap pt_vars)
4644 struct shared_bitmap_info sbi;
4646 sbi.pt_vars = pt_vars;
4647 sbi.hashcode = bitmap_hash (pt_vars);
4649 slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
4650 sbi.hashcode, NO_INSERT);
4654 return ((shared_bitmap_info_t) *slot)->pt_vars;
4658 /* Add a bitmap to the shared bitmap hashtable. */
4661 shared_bitmap_add (bitmap pt_vars)
4664 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
4666 sbi->pt_vars = pt_vars;
4667 sbi->hashcode = bitmap_hash (pt_vars);
4669 slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
4670 sbi->hashcode, INSERT);
4671 gcc_assert (!*slot);
4672 *slot = (void *) sbi;
4676 /* Set bits in INTO corresponding to the variable uids in solution set
4677 FROM, which came from variable PTR.
4678 For variables that are actually dereferenced, we also use type
4679 based alias analysis to prune the points-to sets.
4680 IS_DEREFED is true if PTR was directly dereferenced, which we use to
4681 help determine whether we are we are allowed to prune using TBAA.
4682 If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of
4683 the from set. Returns the number of pruned variables. */
4686 set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed,
4687 bool no_tbaa_pruning)
4691 unsigned pruned = 0;
4693 gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
4695 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4697 varinfo_t vi = get_varinfo (i);
4699 /* The only artificial variables that are allowed in a may-alias
4700 set are heap variables. */
4701 if (vi->is_artificial_var && !vi->is_heap_var)
4704 if (TREE_CODE (vi->decl) == VAR_DECL
4705 || TREE_CODE (vi->decl) == PARM_DECL
4706 || TREE_CODE (vi->decl) == RESULT_DECL)
4708 /* Just add VI->DECL to the alias set.
4709 Don't type prune artificial vars or points-to sets
4710 for pointers that have not been dereferenced or with
4711 type-based pruning disabled. */
4712 if (vi->is_artificial_var
4715 || vi->no_tbaa_pruning)
4716 bitmap_set_bit (into, DECL_UID (vi->decl));
4719 alias_set_type var_alias_set, mem_alias_set;
4720 var_alias_set = get_alias_set (vi->decl);
4721 mem_alias_set = get_alias_set (TREE_TYPE (TREE_TYPE (ptr)));
4722 if (may_alias_p (SSA_NAME_VAR (ptr), mem_alias_set,
4723 vi->decl, var_alias_set, true))
4724 bitmap_set_bit (into, DECL_UID (vi->decl));
4735 static bool have_alias_info = false;
4737 /* Emit a note for the pointer initialization point DEF. */
4740 emit_pointer_definition (tree ptr, bitmap visited)
4742 gimple def = SSA_NAME_DEF_STMT (ptr);
4743 if (gimple_code (def) == GIMPLE_PHI)
4748 FOR_EACH_PHI_ARG (argp, def, oi, SSA_OP_USE)
4750 tree arg = USE_FROM_PTR (argp);
4751 if (TREE_CODE (arg) == SSA_NAME)
4753 if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
4754 emit_pointer_definition (arg, visited);
4757 inform (0, "initialized from %qE", arg);
4760 else if (!gimple_nop_p (def))
4761 inform (gimple_location (def), "initialized from here");
4764 /* Emit a strict aliasing warning for dereferencing the pointer PTR. */
4767 emit_alias_warning (tree ptr)
4770 imm_use_iterator ui;
4771 bool warned = false;
4773 FOR_EACH_IMM_USE_STMT (use, ui, ptr)
4775 tree deref = NULL_TREE;
4777 if (gimple_has_lhs (use))
4779 tree lhs = get_base_address (gimple_get_lhs (use));
4781 && INDIRECT_REF_P (lhs)
4782 && TREE_OPERAND (lhs, 0) == ptr)
4785 if (gimple_assign_single_p (use))
4787 tree rhs = get_base_address (gimple_assign_rhs1 (use));
4789 && INDIRECT_REF_P (rhs)
4790 && TREE_OPERAND (rhs, 0) == ptr)
4793 else if (is_gimple_call (use))
4796 for (i = 0; i < gimple_call_num_args (use); ++i)
4798 tree op = get_base_address (gimple_call_arg (use, i));
4800 && INDIRECT_REF_P (op)
4801 && TREE_OPERAND (op, 0) == ptr)
4806 && !TREE_NO_WARNING (deref))
4808 TREE_NO_WARNING (deref) = 1;
4809 warned |= warning_at (gimple_location (use), OPT_Wstrict_aliasing,
4810 "dereferencing pointer %qD does break "
4811 "strict-aliasing rules", SSA_NAME_VAR (ptr));
4816 bitmap visited = BITMAP_ALLOC (NULL);
4817 emit_pointer_definition (ptr, visited);
4818 BITMAP_FREE (visited);
4822 /* Given a pointer variable P, fill in its points-to set, or return
4824 Rather than return false for variables that point-to anything, we
4825 instead find the corresponding SMT, and merge in its aliases. In
4826 addition to these aliases, we also set the bits for the SMT's
4827 themselves and their subsets, as SMT's are still in use by
4828 non-SSA_NAME's, and pruning may eliminate every one of their
4829 aliases. In such a case, if we did not include the right set of
4830 SMT's in the points-to set of the variable, we'd end up with
4831 statements that do not conflict but should. */
4834 find_what_p_points_to (tree p)
4839 if (!have_alias_info)
4842 /* For parameters, get at the points-to set for the actual parm
4844 if (TREE_CODE (p) == SSA_NAME
4845 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4846 && SSA_NAME_IS_DEFAULT_DEF (p))
4847 lookup_p = SSA_NAME_VAR (p);
4849 vi = lookup_vi_for_tree (lookup_p);
4852 if (vi->is_artificial_var)
4855 /* See if this is a field or a structure. */
4856 if (vi->size != vi->fullsize)
4858 /* Nothing currently asks about structure fields directly,
4859 but when they do, we need code here to hand back the
4865 struct ptr_info_def *pi = get_ptr_info (p);
4866 unsigned int i, pruned;
4868 bool was_pt_anything = false;
4869 bitmap finished_solution;
4872 if (!pi->memory_tag_needed)
4875 /* This variable may have been collapsed, let's get the real
4877 vi = get_varinfo (find (vi->id));
4879 /* Translate artificial variables into SSA_NAME_PTR_INFO
4881 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4883 varinfo_t vi = get_varinfo (i);
4885 if (vi->is_artificial_var)
4887 /* FIXME. READONLY should be handled better so that
4888 flow insensitive aliasing can disregard writable
4890 if (vi->id == nothing_id)
4892 else if (vi->id == anything_id
4893 || vi->id == nonlocal_id
4894 || vi->id == escaped_id
4895 || vi->id == callused_id)
4896 was_pt_anything = 1;
4897 else if (vi->id == readonly_id)
4898 was_pt_anything = 1;
4899 else if (vi->id == integer_id)
4900 was_pt_anything = 1;
4901 else if (vi->is_heap_var)
4902 pi->pt_global_mem = 1;
4906 /* Instead of doing extra work, simply do not create
4907 points-to information for pt_anything pointers. This
4908 will cause the operand scanner to fall back to the
4909 type-based SMT and its aliases. Which is the best
4910 we could do here for the points-to set as well. */
4911 if (was_pt_anything)
4914 /* Share the final set of variables when possible. */
4915 finished_solution = BITMAP_GGC_ALLOC ();
4916 stats.points_to_sets_created++;
4918 pruned = set_uids_in_ptset (p, finished_solution, vi->solution,
4919 pi->is_dereferenced,
4920 vi->no_tbaa_pruning);
4921 result = shared_bitmap_lookup (finished_solution);
4925 shared_bitmap_add (finished_solution);
4926 pi->pt_vars = finished_solution;
4930 pi->pt_vars = result;
4931 bitmap_clear (finished_solution);
4934 if (bitmap_empty_p (pi->pt_vars))
4938 && pi->is_dereferenced
4939 && warn_strict_aliasing > 0
4940 && !SSA_NAME_IS_DEFAULT_DEF (p))
4942 if (dump_file && dump_flags & TDF_DETAILS)
4944 fprintf (dump_file, "alias warning for ");
4945 print_generic_expr (dump_file, p, 0);
4946 fprintf (dump_file, "\n");
4948 emit_alias_warning (p);
4959 /* Mark the ESCAPED solution as call clobbered. Returns false if
4960 pt_anything escaped which needs all locals that have their address
4961 taken marked call clobbered as well. */
4964 clobber_what_escaped (void)
4970 if (!have_alias_info)
4973 /* This variable may have been collapsed, let's get the real
4974 variable for escaped_id. */
4975 vi = get_varinfo (find (escaped_id));
4977 /* If call-used memory escapes we need to include it in the
4978 set of escaped variables. This can happen if a pure
4979 function returns a pointer and this pointer escapes. */
4980 if (bitmap_bit_p (vi->solution, callused_id))
4982 varinfo_t cu_vi = get_varinfo (find (callused_id));
4983 bitmap_ior_into (vi->solution, cu_vi->solution);
4986 /* Mark variables in the solution call-clobbered. */
4987 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4989 varinfo_t vi = get_varinfo (i);
4991 if (vi->is_artificial_var)
4993 /* nothing_id and readonly_id do not cause any
4994 call clobber ops. For anything_id and integer_id
4995 we need to clobber all addressable vars. */
4996 if (vi->id == anything_id
4997 || vi->id == integer_id)
5001 /* Only artificial heap-vars are further interesting. */
5002 if (vi->is_artificial_var && !vi->is_heap_var)
5005 if ((TREE_CODE (vi->decl) == VAR_DECL
5006 || TREE_CODE (vi->decl) == PARM_DECL
5007 || TREE_CODE (vi->decl) == RESULT_DECL)
5008 && !unmodifiable_var_p (vi->decl))
5009 mark_call_clobbered (vi->decl, ESCAPE_TO_CALL);
5015 /* Compute the call-used variables. */
5018 compute_call_used_vars (void)
5023 bool has_anything_id = false;
5025 if (!have_alias_info)
5028 /* This variable may have been collapsed, let's get the real
5029 variable for escaped_id. */
5030 vi = get_varinfo (find (callused_id));
5032 /* Mark variables in the solution call-clobbered. */
5033 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
5035 varinfo_t vi = get_varinfo (i);
5037 if (vi->is_artificial_var)
5039 /* For anything_id and integer_id we need to make
5040 all local addressable vars call-used. */
5041 if (vi->id == anything_id
5042 || vi->id == integer_id)
5043 has_anything_id = true;
5046 /* Only artificial heap-vars are further interesting. */
5047 if (vi->is_artificial_var && !vi->is_heap_var)
5050 if ((TREE_CODE (vi->decl) == VAR_DECL
5051 || TREE_CODE (vi->decl) == PARM_DECL
5052 || TREE_CODE (vi->decl) == RESULT_DECL)
5053 && !unmodifiable_var_p (vi->decl))
5054 bitmap_set_bit (gimple_call_used_vars (cfun), DECL_UID (vi->decl));
5057 /* If anything is call-used, add all addressable locals to the set. */
5058 if (has_anything_id)
5059 bitmap_ior_into (gimple_call_used_vars (cfun),
5060 gimple_addressable_vars (cfun));
5064 /* Dump points-to information to OUTFILE. */
5067 dump_sa_points_to_info (FILE *outfile)
5071 fprintf (outfile, "\nPoints-to sets\n\n");
5073 if (dump_flags & TDF_STATS)
5075 fprintf (outfile, "Stats:\n");
5076 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
5077 fprintf (outfile, "Non-pointer vars: %d\n",
5078 stats.nonpointer_vars);
5079 fprintf (outfile, "Statically unified vars: %d\n",
5080 stats.unified_vars_static);
5081 fprintf (outfile, "Dynamically unified vars: %d\n",
5082 stats.unified_vars_dynamic);
5083 fprintf (outfile, "Iterations: %d\n", stats.iterations);
5084 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
5085 fprintf (outfile, "Number of implicit edges: %d\n",
5086 stats.num_implicit_edges);
5089 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
5090 dump_solution_for_var (outfile, i);
5094 /* Debug points-to information to stderr. */
5097 debug_sa_points_to_info (void)
5099 dump_sa_points_to_info (stderr);
5103 /* Initialize the always-existing constraint variables for NULL
5104 ANYTHING, READONLY, and INTEGER */
5107 init_base_vars (void)
5109 struct constraint_expr lhs, rhs;
5111 /* Create the NULL variable, used to represent that a variable points
5113 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
5114 var_nothing = new_var_info (nothing_tree, nothing_id, "NULL");
5115 insert_vi_for_tree (nothing_tree, var_nothing);
5116 var_nothing->is_artificial_var = 1;
5117 var_nothing->offset = 0;
5118 var_nothing->size = ~0;
5119 var_nothing->fullsize = ~0;
5120 var_nothing->is_special_var = 1;
5121 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
5123 /* Create the ANYTHING variable, used to represent that a variable
5124 points to some unknown piece of memory. */
5125 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
5126 var_anything = new_var_info (anything_tree, anything_id, "ANYTHING");
5127 insert_vi_for_tree (anything_tree, var_anything);
5128 var_anything->is_artificial_var = 1;
5129 var_anything->size = ~0;
5130 var_anything->offset = 0;
5131 var_anything->next = NULL;
5132 var_anything->fullsize = ~0;
5133 var_anything->is_special_var = 1;
5135 /* Anything points to anything. This makes deref constraints just
5136 work in the presence of linked list and other p = *p type loops,
5137 by saying that *ANYTHING = ANYTHING. */
5138 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
5140 lhs.var = anything_id;
5142 rhs.type = ADDRESSOF;
5143 rhs.var = anything_id;
5146 /* This specifically does not use process_constraint because
5147 process_constraint ignores all anything = anything constraints, since all
5148 but this one are redundant. */
5149 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
5151 /* Create the READONLY variable, used to represent that a variable
5152 points to readonly memory. */
5153 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
5154 var_readonly = new_var_info (readonly_tree, readonly_id, "READONLY");
5155 var_readonly->is_artificial_var = 1;
5156 var_readonly->offset = 0;
5157 var_readonly->size = ~0;
5158 var_readonly->fullsize = ~0;
5159 var_readonly->next = NULL;
5160 var_readonly->is_special_var = 1;
5161 insert_vi_for_tree (readonly_tree, var_readonly);
5162 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
5164 /* readonly memory points to anything, in order to make deref
5165 easier. In reality, it points to anything the particular
5166 readonly variable can point to, but we don't track this
5169 lhs.var = readonly_id;
5171 rhs.type = ADDRESSOF;
5172 rhs.var = readonly_id; /* FIXME */
5174 process_constraint (new_constraint (lhs, rhs));
5176 /* Create the ESCAPED variable, used to represent the set of escaped
5178 escaped_tree = create_tmp_var_raw (void_type_node, "ESCAPED");
5179 var_escaped = new_var_info (escaped_tree, escaped_id, "ESCAPED");
5180 insert_vi_for_tree (escaped_tree, var_escaped);
5181 var_escaped->is_artificial_var = 1;
5182 var_escaped->offset = 0;
5183 var_escaped->size = ~0;
5184 var_escaped->fullsize = ~0;
5185 var_escaped->is_special_var = 0;
5186 VEC_safe_push (varinfo_t, heap, varmap, var_escaped);
5187 gcc_assert (VEC_index (varinfo_t, varmap, 3) == var_escaped);
5189 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
5191 lhs.var = escaped_id;
5194 rhs.var = escaped_id;
5196 process_constraint (new_constraint (lhs, rhs));
5198 /* Create the NONLOCAL variable, used to represent the set of nonlocal
5200 nonlocal_tree = create_tmp_var_raw (void_type_node, "NONLOCAL");
5201 var_nonlocal = new_var_info (nonlocal_tree, nonlocal_id, "NONLOCAL");
5202 insert_vi_for_tree (nonlocal_tree, var_nonlocal);
5203 var_nonlocal->is_artificial_var = 1;
5204 var_nonlocal->offset = 0;
5205 var_nonlocal->size = ~0;
5206 var_nonlocal->fullsize = ~0;
5207 var_nonlocal->is_special_var = 1;
5208 VEC_safe_push (varinfo_t, heap, varmap, var_nonlocal);
5210 /* Nonlocal memory points to escaped (which includes nonlocal),
5211 in order to make deref easier. */
5213 lhs.var = nonlocal_id;
5215 rhs.type = ADDRESSOF;
5216 rhs.var = escaped_id;
5218 process_constraint (new_constraint (lhs, rhs));
5220 /* Create the CALLUSED variable, used to represent the set of call-used
5222 callused_tree = create_tmp_var_raw (void_type_node, "CALLUSED");
5223 var_callused = new_var_info (callused_tree, callused_id, "CALLUSED");
5224 insert_vi_for_tree (callused_tree, var_callused);
5225 var_callused->is_artificial_var = 1;
5226 var_callused->offset = 0;
5227 var_callused->size = ~0;
5228 var_callused->fullsize = ~0;
5229 var_callused->is_special_var = 0;
5230 VEC_safe_push (varinfo_t, heap, varmap, var_callused);
5232 /* CALLUSED = *CALLUSED, because call-used is may-deref'd at calls, etc. */
5234 lhs.var = callused_id;
5237 rhs.var = callused_id;
5239 process_constraint (new_constraint (lhs, rhs));
5241 /* Create the INTEGER variable, used to represent that a variable points
5243 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
5244 var_integer = new_var_info (integer_tree, integer_id, "INTEGER");
5245 insert_vi_for_tree (integer_tree, var_integer);
5246 var_integer->is_artificial_var = 1;
5247 var_integer->size = ~0;
5248 var_integer->fullsize = ~0;
5249 var_integer->offset = 0;
5250 var_integer->next = NULL;
5251 var_integer->is_special_var = 1;
5252 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
5254 /* INTEGER = ANYTHING, because we don't know where a dereference of
5255 a random integer will point to. */
5257 lhs.var = integer_id;
5259 rhs.type = ADDRESSOF;
5260 rhs.var = anything_id;
5262 process_constraint (new_constraint (lhs, rhs));
5264 /* *ESCAPED = &ESCAPED. This is true because we have to assume
5265 everything pointed to by escaped can also point to escaped. */
5267 lhs.var = escaped_id;
5269 rhs.type = ADDRESSOF;
5270 rhs.var = escaped_id;
5272 process_constraint (new_constraint (lhs, rhs));
5274 /* *ESCAPED = &NONLOCAL. This is true because we have to assume
5275 everything pointed to by escaped can also point to nonlocal. */
5277 lhs.var = escaped_id;
5279 rhs.type = ADDRESSOF;
5280 rhs.var = nonlocal_id;
5282 process_constraint (new_constraint (lhs, rhs));
5285 /* Initialize things necessary to perform PTA */
5288 init_alias_vars (void)
5290 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
5292 bitmap_obstack_initialize (&pta_obstack);
5293 bitmap_obstack_initialize (&oldpta_obstack);
5294 bitmap_obstack_initialize (&predbitmap_obstack);
5296 constraint_pool = create_alloc_pool ("Constraint pool",
5297 sizeof (struct constraint), 30);
5298 variable_info_pool = create_alloc_pool ("Variable info pool",
5299 sizeof (struct variable_info), 30);
5300 constraints = VEC_alloc (constraint_t, heap, 8);
5301 varmap = VEC_alloc (varinfo_t, heap, 8);
5302 vi_for_tree = pointer_map_create ();
5304 memset (&stats, 0, sizeof (stats));
5305 shared_bitmap_table = htab_create (511, shared_bitmap_hash,
5306 shared_bitmap_eq, free);
5310 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
5311 predecessor edges. */
5314 remove_preds_and_fake_succs (constraint_graph_t graph)
5318 /* Clear the implicit ref and address nodes from the successor
5320 for (i = 0; i < FIRST_REF_NODE; i++)
5322 if (graph->succs[i])
5323 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
5324 FIRST_REF_NODE * 2);
5327 /* Free the successor list for the non-ref nodes. */
5328 for (i = FIRST_REF_NODE; i < graph->size; i++)
5330 if (graph->succs[i])
5331 BITMAP_FREE (graph->succs[i]);
5334 /* Now reallocate the size of the successor list as, and blow away
5335 the predecessor bitmaps. */
5336 graph->size = VEC_length (varinfo_t, varmap);
5337 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
5339 free (graph->implicit_preds);
5340 graph->implicit_preds = NULL;
5341 free (graph->preds);
5342 graph->preds = NULL;
5343 bitmap_obstack_release (&predbitmap_obstack);
5346 /* Compute the set of variables we can't TBAA prune. */
5349 compute_tbaa_pruning (void)
5351 unsigned int size = VEC_length (varinfo_t, varmap);
5356 changed = sbitmap_alloc (size);
5357 sbitmap_zero (changed);
5359 /* Mark all initial no_tbaa_pruning nodes as changed. */
5361 for (i = 0; i < size; ++i)
5363 varinfo_t ivi = get_varinfo (i);
5365 if (find (i) == i && ivi->no_tbaa_pruning)
5368 if ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
5369 || VEC_length (constraint_t, graph->complex[i]) > 0)
5371 SET_BIT (changed, i);
5377 while (changed_count > 0)
5379 struct topo_info *ti = init_topo_info ();
5382 compute_topo_order (graph, ti);
5384 while (VEC_length (unsigned, ti->topo_order) != 0)
5388 i = VEC_pop (unsigned, ti->topo_order);
5390 /* If this variable is not a representative, skip it. */
5394 /* If the node has changed, we need to process the complex
5395 constraints and outgoing edges again. */
5396 if (TEST_BIT (changed, i))
5400 VEC(constraint_t,heap) *complex = graph->complex[i];
5402 RESET_BIT (changed, i);
5405 /* Process the complex copy constraints. */
5406 for (j = 0; VEC_iterate (constraint_t, complex, j, c); ++j)
5408 if (c->lhs.type == SCALAR && c->rhs.type == SCALAR)
5410 varinfo_t lhsvi = get_varinfo (find (c->lhs.var));
5412 if (!lhsvi->no_tbaa_pruning)
5414 lhsvi->no_tbaa_pruning = true;
5415 if (!TEST_BIT (changed, lhsvi->id))
5417 SET_BIT (changed, lhsvi->id);
5424 /* Propagate to all successors. */
5425 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
5427 unsigned int to = find (j);
5428 varinfo_t tovi = get_varinfo (to);
5430 /* Don't propagate to ourselves. */
5434 if (!tovi->no_tbaa_pruning)
5436 tovi->no_tbaa_pruning = true;
5437 if (!TEST_BIT (changed, to))
5439 SET_BIT (changed, to);
5447 free_topo_info (ti);
5450 sbitmap_free (changed);
5454 for (i = 0; i < size; ++i)
5456 varinfo_t ivi = get_varinfo (i);
5457 varinfo_t ivip = get_varinfo (find (i));
5459 if (ivip->no_tbaa_pruning)
5461 tree var = ivi->decl;
5463 if (TREE_CODE (var) == SSA_NAME)
5464 var = SSA_NAME_VAR (var);
5466 if (POINTER_TYPE_P (TREE_TYPE (var)))
5468 DECL_NO_TBAA_P (var) = 1;
5470 /* Tell the RTL layer that this pointer can alias
5472 DECL_POINTER_ALIAS_SET (var) = 0;
5479 /* Create points-to sets for the current function. See the comments
5480 at the start of the file for an algorithmic overview. */
5483 compute_points_to_sets (void)
5485 struct scc_info *si;
5488 timevar_push (TV_TREE_PTA);
5491 init_alias_heapvars ();
5493 intra_create_variable_infos ();
5495 /* Now walk all statements and derive aliases. */
5498 gimple_stmt_iterator gsi;
5500 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5502 gimple phi = gsi_stmt (gsi);
5504 if (is_gimple_reg (gimple_phi_result (phi)))
5505 find_func_aliases (phi);
5508 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5509 find_func_aliases (gsi_stmt (gsi));
5515 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5516 dump_constraints (dump_file);
5521 "\nCollapsing static cycles and doing variable "
5524 init_graph (VEC_length (varinfo_t, varmap) * 2);
5527 fprintf (dump_file, "Building predecessor graph\n");
5528 build_pred_graph ();
5531 fprintf (dump_file, "Detecting pointer and location "
5533 si = perform_var_substitution (graph);
5536 fprintf (dump_file, "Rewriting constraints and unifying "
5538 rewrite_constraints (graph, si);
5539 free_var_substitution_info (si);
5541 build_succ_graph ();
5543 if (dump_file && (dump_flags & TDF_GRAPH))
5544 dump_constraint_graph (dump_file);
5546 move_complex_constraints (graph);
5549 fprintf (dump_file, "Uniting pointer but not location equivalent "
5551 unite_pointer_equivalences (graph);
5554 fprintf (dump_file, "Finding indirect cycles\n");
5555 find_indirect_cycles (graph);
5557 /* Implicit nodes and predecessors are no longer necessary at this
5559 remove_preds_and_fake_succs (graph);
5562 fprintf (dump_file, "Solving graph\n");
5564 solve_graph (graph);
5566 compute_tbaa_pruning ();
5569 dump_sa_points_to_info (dump_file);
5571 have_alias_info = true;
5573 timevar_pop (TV_TREE_PTA);
5577 /* Delete created points-to sets. */
5580 delete_points_to_sets (void)
5584 htab_delete (shared_bitmap_table);
5585 if (dump_file && (dump_flags & TDF_STATS))
5586 fprintf (dump_file, "Points to sets created:%d\n",
5587 stats.points_to_sets_created);
5589 pointer_map_destroy (vi_for_tree);
5590 bitmap_obstack_release (&pta_obstack);
5591 VEC_free (constraint_t, heap, constraints);
5593 for (i = 0; i < graph->size; i++)
5594 VEC_free (constraint_t, heap, graph->complex[i]);
5595 free (graph->complex);
5598 free (graph->succs);
5600 free (graph->pe_rep);
5601 free (graph->indirect_cycles);
5604 VEC_free (varinfo_t, heap, varmap);
5605 free_alloc_pool (variable_info_pool);
5606 free_alloc_pool (constraint_pool);
5607 have_alias_info = false;
5610 /* Return true if we should execute IPA PTA. */
5614 return (flag_ipa_pta
5615 /* Don't bother doing anything if the program has errors. */
5616 && !(errorcount || sorrycount));
5619 /* Execute the driver for IPA PTA. */
5621 ipa_pta_execute (void)
5623 struct cgraph_node *node;
5624 struct scc_info *si;
5627 init_alias_heapvars ();
5630 for (node = cgraph_nodes; node; node = node->next)
5632 if (!node->analyzed || cgraph_is_master_clone (node))
5636 varid = create_function_info_for (node->decl,
5637 cgraph_node_name (node));
5638 if (node->local.externally_visible)
5640 varinfo_t fi = get_varinfo (varid);
5641 for (; fi; fi = fi->next)
5642 make_constraint_from (fi, anything_id);
5646 for (node = cgraph_nodes; node; node = node->next)
5648 if (node->analyzed && cgraph_is_master_clone (node))
5650 struct function *func = DECL_STRUCT_FUNCTION (node->decl);
5652 tree old_func_decl = current_function_decl;
5655 "Generating constraints for %s\n",
5656 cgraph_node_name (node));
5658 current_function_decl = node->decl;
5660 FOR_EACH_BB_FN (bb, func)
5662 gimple_stmt_iterator gsi;
5664 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
5667 gimple phi = gsi_stmt (gsi);
5669 if (is_gimple_reg (gimple_phi_result (phi)))
5670 find_func_aliases (phi);
5673 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5674 find_func_aliases (gsi_stmt (gsi));
5676 current_function_decl = old_func_decl;
5681 /* Make point to anything. */
5687 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5688 dump_constraints (dump_file);
5693 "\nCollapsing static cycles and doing variable "
5696 init_graph (VEC_length (varinfo_t, varmap) * 2);
5697 build_pred_graph ();
5698 si = perform_var_substitution (graph);
5699 rewrite_constraints (graph, si);
5700 free_var_substitution_info (si);
5702 build_succ_graph ();
5703 move_complex_constraints (graph);
5704 unite_pointer_equivalences (graph);
5705 find_indirect_cycles (graph);
5707 /* Implicit nodes and predecessors are no longer necessary at this
5709 remove_preds_and_fake_succs (graph);
5712 fprintf (dump_file, "\nSolving graph\n");
5714 solve_graph (graph);
5717 dump_sa_points_to_info (dump_file);
5720 delete_alias_heapvars ();
5721 delete_points_to_sets ();
5725 struct simple_ipa_opt_pass pass_ipa_pta =
5730 gate_ipa_pta, /* gate */
5731 ipa_pta_execute, /* execute */
5734 0, /* static_pass_number */
5735 TV_IPA_PTA, /* tv_id */
5736 0, /* properties_required */
5737 0, /* properties_provided */
5738 0, /* properties_destroyed */
5739 0, /* todo_flags_start */
5740 TODO_update_ssa /* todo_flags_finish */
5744 /* Initialize the heapvar for statement mapping. */
5746 init_alias_heapvars (void)
5748 if (!heapvar_for_stmt)
5749 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5754 delete_alias_heapvars (void)
5756 htab_delete (heapvar_for_stmt);
5757 heapvar_for_stmt = NULL;
5760 #include "gt-tree-ssa-structalias.h"