1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
35 #include "tree-flow.h"
36 #include "tree-inline.h"
38 #include "diagnostic.h"
44 #include "tree-pass.h"
46 #include "alloc-pool.h"
47 #include "splay-tree.h"
51 #include "pointer-set.h"
53 /* The idea behind this analyzer is to generate set constraints from the
54 program, then solve the resulting constraints in order to generate the
57 Set constraints are a way of modeling program analysis problems that
58 involve sets. They consist of an inclusion constraint language,
59 describing the variables (each variable is a set) and operations that
60 are involved on the variables, and a set of rules that derive facts
61 from these operations. To solve a system of set constraints, you derive
62 all possible facts under the rules, which gives you the correct sets
65 See "Efficient Field-sensitive pointer analysis for C" by "David
66 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
67 http://citeseer.ist.psu.edu/pearce04efficient.html
69 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
70 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
71 http://citeseer.ist.psu.edu/heintze01ultrafast.html
73 There are three types of real constraint expressions, DEREF,
74 ADDRESSOF, and SCALAR. Each constraint expression consists
75 of a constraint type, a variable, and an offset.
77 SCALAR is a constraint expression type used to represent x, whether
78 it appears on the LHS or the RHS of a statement.
79 DEREF is a constraint expression type used to represent *x, whether
80 it appears on the LHS or the RHS of a statement.
81 ADDRESSOF is a constraint expression used to represent &x, whether
82 it appears on the LHS or the RHS of a statement.
84 Each pointer variable in the program is assigned an integer id, and
85 each field of a structure variable is assigned an integer id as well.
87 Structure variables are linked to their list of fields through a "next
88 field" in each variable that points to the next field in offset
90 Each variable for a structure field has
92 1. "size", that tells the size in bits of that field.
93 2. "fullsize, that tells the size in bits of the entire structure.
94 3. "offset", that tells the offset in bits from the beginning of the
95 structure to this field.
107 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
108 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
109 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
112 In order to solve the system of set constraints, the following is
115 1. Each constraint variable x has a solution set associated with it,
118 2. Constraints are separated into direct, copy, and complex.
119 Direct constraints are ADDRESSOF constraints that require no extra
120 processing, such as P = &Q
121 Copy constraints are those of the form P = Q.
122 Complex constraints are all the constraints involving dereferences
123 and offsets (including offsetted copies).
125 3. All direct constraints of the form P = &Q are processed, such
126 that Q is added to Sol(P)
128 4. All complex constraints for a given constraint variable are stored in a
129 linked list attached to that variable's node.
131 5. A directed graph is built out of the copy constraints. Each
132 constraint variable is a node in the graph, and an edge from
133 Q to P is added for each copy constraint of the form P = Q
135 6. The graph is then walked, and solution sets are
136 propagated along the copy edges, such that an edge from Q to P
137 causes Sol(P) <- Sol(P) union Sol(Q).
139 7. As we visit each node, all complex constraints associated with
140 that node are processed by adding appropriate copy edges to the graph, or the
141 appropriate variables to the solution set.
143 8. The process of walking the graph is iterated until no solution
146 Prior to walking the graph in steps 6 and 7, We perform static
147 cycle elimination on the constraint graph, as well
148 as off-line variable substitution.
150 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
151 on and turned into anything), but isn't. You can just see what offset
152 inside the pointed-to struct it's going to access.
154 TODO: Constant bounded arrays can be handled as if they were structs of the
155 same number of elements.
157 TODO: Modeling heap and incoming pointers becomes much better if we
158 add fields to them as we discover them, which we could do.
160 TODO: We could handle unions, but to be honest, it's probably not
161 worth the pain or slowdown. */
163 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
164 htab_t heapvar_for_stmt;
166 static bool use_field_sensitive = true;
167 static int in_ipa_mode = 0;
169 /* Used for predecessor bitmaps. */
170 static bitmap_obstack predbitmap_obstack;
172 /* Used for points-to sets. */
173 static bitmap_obstack pta_obstack;
175 /* Used for oldsolution members of variables. */
176 static bitmap_obstack oldpta_obstack;
178 /* Used for per-solver-iteration bitmaps. */
179 static bitmap_obstack iteration_obstack;
181 static unsigned int create_variable_info_for (tree, const char *);
182 typedef struct constraint_graph *constraint_graph_t;
183 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
186 typedef struct constraint *constraint_t;
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 this is a variable tracking a restrict pointer source. */
230 unsigned int is_restrict_var : 1;
232 /* True if this field may contain pointers. */
233 unsigned int may_have_pointers : 1;
235 /* True if this represents a global variable. */
236 unsigned int is_global_var : 1;
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 first_or_preceding_vi_for_offset (varinfo_t,
266 unsigned HOST_WIDE_INT);
267 static varinfo_t lookup_vi_for_tree (tree);
269 /* Pool of variable info structures. */
270 static alloc_pool variable_info_pool;
272 DEF_VEC_P(varinfo_t);
274 DEF_VEC_ALLOC_P(varinfo_t, heap);
276 /* Table of variable info structures for constraint variables.
277 Indexed directly by variable info id. */
278 static VEC(varinfo_t,heap) *varmap;
280 /* Return the varmap element N */
282 static inline varinfo_t
283 get_varinfo (unsigned int n)
285 return VEC_index (varinfo_t, varmap, n);
288 /* Static IDs for the special variables. */
289 enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
290 escaped_id = 3, nonlocal_id = 4, callused_id = 5,
291 storedanything_id = 6, integer_id = 7 };
293 /* Lookup a heap var for FROM, and return it if we find one. */
296 heapvar_lookup (tree from)
298 struct tree_map *h, in;
301 h = (struct tree_map *) htab_find_with_hash (heapvar_for_stmt, &in,
302 htab_hash_pointer (from));
308 /* Insert a mapping FROM->TO in the heap var for statement
312 heapvar_insert (tree from, tree to)
317 h = GGC_NEW (struct tree_map);
318 h->hash = htab_hash_pointer (from);
321 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
322 *(struct tree_map **) loc = h;
325 /* Return a new variable info structure consisting for a variable
326 named NAME, and using constraint graph node NODE. Append it
327 to the vector of variable info structures. */
330 new_var_info (tree t, const char *name)
332 unsigned index = VEC_length (varinfo_t, varmap);
333 varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
338 /* Vars without decl are artificial and do not have sub-variables. */
339 ret->is_artificial_var = (t == NULL_TREE);
340 ret->is_special_var = false;
341 ret->is_unknown_size_var = false;
342 ret->is_full_var = (t == NULL_TREE);
343 ret->is_heap_var = false;
344 ret->is_restrict_var = false;
345 ret->may_have_pointers = true;
346 ret->is_global_var = (t == NULL_TREE);
348 ret->is_global_var = is_global_var (t);
349 ret->solution = BITMAP_ALLOC (&pta_obstack);
350 ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
353 VEC_safe_push (varinfo_t, heap, varmap, ret);
358 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
360 /* An expression that appears in a constraint. */
362 struct constraint_expr
364 /* Constraint type. */
365 constraint_expr_type type;
367 /* Variable we are referring to in the constraint. */
370 /* Offset, in bits, of this constraint from the beginning of
371 variables it ends up referring to.
373 IOW, in a deref constraint, we would deref, get the result set,
374 then add OFFSET to each member. */
375 HOST_WIDE_INT offset;
378 /* Use 0x8000... as special unknown offset. */
379 #define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))
381 typedef struct constraint_expr ce_s;
383 DEF_VEC_ALLOC_O(ce_s, heap);
384 static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);
385 static void get_constraint_for (tree, VEC(ce_s, heap) **);
386 static void do_deref (VEC (ce_s, heap) **);
388 /* Our set constraints are made up of two constraint expressions, one
391 As described in the introduction, our set constraints each represent an
392 operation between set valued variables.
396 struct constraint_expr lhs;
397 struct constraint_expr rhs;
400 /* List of constraints that we use to build the constraint graph from. */
402 static VEC(constraint_t,heap) *constraints;
403 static alloc_pool constraint_pool;
407 DEF_VEC_ALLOC_I(int, heap);
409 /* The constraint graph is represented as an array of bitmaps
410 containing successor nodes. */
412 struct constraint_graph
414 /* Size of this graph, which may be different than the number of
415 nodes in the variable map. */
418 /* Explicit successors of each node. */
421 /* Implicit predecessors of each node (Used for variable
423 bitmap *implicit_preds;
425 /* Explicit predecessors of each node (Used for variable substitution). */
428 /* Indirect cycle representatives, or -1 if the node has no indirect
430 int *indirect_cycles;
432 /* Representative node for a node. rep[a] == a unless the node has
436 /* Equivalence class representative for a label. This is used for
437 variable substitution. */
440 /* Pointer equivalence label for a node. All nodes with the same
441 pointer equivalence label can be unified together at some point
442 (either during constraint optimization or after the constraint
446 /* Pointer equivalence representative for a label. This is used to
447 handle nodes that are pointer equivalent but not location
448 equivalent. We can unite these once the addressof constraints
449 are transformed into initial points-to sets. */
452 /* Pointer equivalence label for each node, used during variable
454 unsigned int *pointer_label;
456 /* Location equivalence label for each node, used during location
457 equivalence finding. */
458 unsigned int *loc_label;
460 /* Pointed-by set for each node, used during location equivalence
461 finding. This is pointed-by rather than pointed-to, because it
462 is constructed using the predecessor graph. */
465 /* Points to sets for pointer equivalence. This is *not* the actual
466 points-to sets for nodes. */
469 /* Bitmap of nodes where the bit is set if the node is a direct
470 node. Used for variable substitution. */
471 sbitmap direct_nodes;
473 /* Bitmap of nodes where the bit is set if the node is address
474 taken. Used for variable substitution. */
475 bitmap address_taken;
477 /* Vector of complex constraints for each graph node. Complex
478 constraints are those involving dereferences or offsets that are
480 VEC(constraint_t,heap) **complex;
483 static constraint_graph_t graph;
485 /* During variable substitution and the offline version of indirect
486 cycle finding, we create nodes to represent dereferences and
487 address taken constraints. These represent where these start and
489 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
490 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
492 /* Return the representative node for NODE, if NODE has been unioned
494 This function performs path compression along the way to finding
495 the representative. */
498 find (unsigned int node)
500 gcc_assert (node < graph->size);
501 if (graph->rep[node] != node)
502 return graph->rep[node] = find (graph->rep[node]);
506 /* Union the TO and FROM nodes to the TO nodes.
507 Note that at some point in the future, we may want to do
508 union-by-rank, in which case we are going to have to return the
509 node we unified to. */
512 unite (unsigned int to, unsigned int from)
514 gcc_assert (to < graph->size && from < graph->size);
515 if (to != from && graph->rep[from] != to)
517 graph->rep[from] = to;
523 /* Create a new constraint consisting of LHS and RHS expressions. */
526 new_constraint (const struct constraint_expr lhs,
527 const struct constraint_expr rhs)
529 constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
535 /* Print out constraint C to FILE. */
538 dump_constraint (FILE *file, constraint_t c)
540 if (c->lhs.type == ADDRESSOF)
542 else if (c->lhs.type == DEREF)
544 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
545 if (c->lhs.offset == UNKNOWN_OFFSET)
546 fprintf (file, " + UNKNOWN");
547 else if (c->lhs.offset != 0)
548 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
549 fprintf (file, " = ");
550 if (c->rhs.type == ADDRESSOF)
552 else if (c->rhs.type == DEREF)
554 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
555 if (c->rhs.offset == UNKNOWN_OFFSET)
556 fprintf (file, " + UNKNOWN");
557 else if (c->rhs.offset != 0)
558 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
559 fprintf (file, "\n");
563 void debug_constraint (constraint_t);
564 void debug_constraints (void);
565 void debug_constraint_graph (void);
566 void debug_solution_for_var (unsigned int);
567 void debug_sa_points_to_info (void);
569 /* Print out constraint C to stderr. */
572 debug_constraint (constraint_t c)
574 dump_constraint (stderr, c);
577 /* Print out all constraints to FILE */
580 dump_constraints (FILE *file)
584 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
585 dump_constraint (file, c);
588 /* Print out all constraints to stderr. */
591 debug_constraints (void)
593 dump_constraints (stderr);
596 /* Print out to FILE the edge in the constraint graph that is created by
597 constraint c. The edge may have a label, depending on the type of
598 constraint that it represents. If complex1, e.g: a = *b, then the label
599 is "=*", if complex2, e.g: *a = b, then the label is "*=", if
600 complex with an offset, e.g: a = b + 8, then the label is "+".
601 Otherwise the edge has no label. */
604 dump_constraint_edge (FILE *file, constraint_t c)
606 if (c->rhs.type != ADDRESSOF)
608 const char *src = get_varinfo (c->rhs.var)->name;
609 const char *dst = get_varinfo (c->lhs.var)->name;
610 fprintf (file, " \"%s\" -> \"%s\" ", src, dst);
611 /* Due to preprocessing of constraints, instructions like *a = *b are
612 illegal; thus, we do not have to handle such cases. */
613 if (c->lhs.type == DEREF)
614 fprintf (file, " [ label=\"*=\" ] ;\n");
615 else if (c->rhs.type == DEREF)
616 fprintf (file, " [ label=\"=*\" ] ;\n");
619 /* We must check the case where the constraint is an offset.
620 In this case, it is treated as a complex constraint. */
621 if (c->rhs.offset != c->lhs.offset)
622 fprintf (file, " [ label=\"+\" ] ;\n");
624 fprintf (file, " ;\n");
629 /* Print the constraint graph in dot format. */
632 dump_constraint_graph (FILE *file)
634 unsigned int i=0, size;
637 /* Only print the graph if it has already been initialized: */
641 /* Print the constraints used to produce the constraint graph. The
642 constraints will be printed as comments in the dot file: */
643 fprintf (file, "\n\n/* Constraints used in the constraint graph:\n");
644 dump_constraints (file);
645 fprintf (file, "*/\n");
647 /* Prints the header of the dot file: */
648 fprintf (file, "\n\n// The constraint graph in dot format:\n");
649 fprintf (file, "strict digraph {\n");
650 fprintf (file, " node [\n shape = box\n ]\n");
651 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
652 fprintf (file, "\n // List of nodes in the constraint graph:\n");
654 /* The next lines print the nodes in the graph. In order to get the
655 number of nodes in the graph, we must choose the minimum between the
656 vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
657 yet been initialized, then graph->size == 0, otherwise we must only
658 read nodes that have an entry in VEC (varinfo_t, varmap). */
659 size = VEC_length (varinfo_t, varmap);
660 size = size < graph->size ? size : graph->size;
661 for (i = 0; i < size; i++)
663 const char *name = get_varinfo (graph->rep[i])->name;
664 fprintf (file, " \"%s\" ;\n", name);
667 /* Go over the list of constraints printing the edges in the constraint
669 fprintf (file, "\n // The constraint edges:\n");
670 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
672 dump_constraint_edge (file, c);
674 /* Prints the tail of the dot file. By now, only the closing bracket. */
675 fprintf (file, "}\n\n\n");
678 /* Print out the constraint graph to stderr. */
681 debug_constraint_graph (void)
683 dump_constraint_graph (stderr);
688 The solver is a simple worklist solver, that works on the following
691 sbitmap changed_nodes = all zeroes;
693 For each node that is not already collapsed:
695 set bit in changed nodes
697 while (changed_count > 0)
699 compute topological ordering for constraint graph
701 find and collapse cycles in the constraint graph (updating
702 changed if necessary)
704 for each node (n) in the graph in topological order:
707 Process each complex constraint associated with the node,
708 updating changed if necessary.
710 For each outgoing edge from n, propagate the solution from n to
711 the destination of the edge, updating changed as necessary.
715 /* Return true if two constraint expressions A and B are equal. */
718 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
720 return a.type == b.type && a.var == b.var && a.offset == b.offset;
723 /* Return true if constraint expression A is less than constraint expression
724 B. This is just arbitrary, but consistent, in order to give them an
728 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
730 if (a.type == b.type)
733 return a.offset < b.offset;
735 return a.var < b.var;
738 return a.type < b.type;
741 /* Return true if constraint A is less than constraint B. This is just
742 arbitrary, but consistent, in order to give them an ordering. */
745 constraint_less (const constraint_t a, const constraint_t b)
747 if (constraint_expr_less (a->lhs, b->lhs))
749 else if (constraint_expr_less (b->lhs, a->lhs))
752 return constraint_expr_less (a->rhs, b->rhs);
755 /* Return true if two constraints A and B are equal. */
758 constraint_equal (struct constraint a, struct constraint b)
760 return constraint_expr_equal (a.lhs, b.lhs)
761 && constraint_expr_equal (a.rhs, b.rhs);
765 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
768 constraint_vec_find (VEC(constraint_t,heap) *vec,
769 struct constraint lookfor)
777 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
778 if (place >= VEC_length (constraint_t, vec))
780 found = VEC_index (constraint_t, vec, place);
781 if (!constraint_equal (*found, lookfor))
786 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
789 constraint_set_union (VEC(constraint_t,heap) **to,
790 VEC(constraint_t,heap) **from)
795 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
797 if (constraint_vec_find (*to, *c) == NULL)
799 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
801 VEC_safe_insert (constraint_t, heap, *to, place, c);
806 /* Expands the solution in SET to all sub-fields of variables included.
807 Union the expanded result into RESULT. */
810 solution_set_expand (bitmap result, bitmap set)
816 /* In a first pass record all variables we need to add all
817 sub-fields off. This avoids quadratic behavior. */
818 EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
820 varinfo_t v = get_varinfo (j);
821 if (v->is_artificial_var
824 v = lookup_vi_for_tree (v->decl);
826 vars = BITMAP_ALLOC (NULL);
827 bitmap_set_bit (vars, v->id);
830 /* In the second pass now do the addition to the solution and
831 to speed up solving add it to the delta as well. */
834 EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
836 varinfo_t v = get_varinfo (j);
837 for (; v != NULL; v = v->next)
838 bitmap_set_bit (result, v->id);
844 /* Take a solution set SET, add OFFSET to each member of the set, and
845 overwrite SET with the result when done. */
848 solution_set_add (bitmap set, HOST_WIDE_INT offset)
850 bitmap result = BITMAP_ALLOC (&iteration_obstack);
854 /* If the offset is unknown we have to expand the solution to
856 if (offset == UNKNOWN_OFFSET)
858 solution_set_expand (set, set);
862 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
864 varinfo_t vi = get_varinfo (i);
866 /* If this is a variable with just one field just set its bit
868 if (vi->is_artificial_var
869 || vi->is_unknown_size_var
871 bitmap_set_bit (result, i);
874 unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
876 /* If the offset makes the pointer point to before the
877 variable use offset zero for the field lookup. */
879 && fieldoffset > vi->offset)
883 vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
885 bitmap_set_bit (result, vi->id);
886 /* If the result is not exactly at fieldoffset include the next
887 field as well. See get_constraint_for_ptr_offset for more
889 if (vi->offset != fieldoffset
891 bitmap_set_bit (result, vi->next->id);
895 bitmap_copy (set, result);
896 BITMAP_FREE (result);
899 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
903 set_union_with_increment (bitmap to, bitmap from, HOST_WIDE_INT inc)
906 return bitmap_ior_into (to, from);
912 tmp = BITMAP_ALLOC (&iteration_obstack);
913 bitmap_copy (tmp, from);
914 solution_set_add (tmp, inc);
915 res = bitmap_ior_into (to, tmp);
921 /* Insert constraint C into the list of complex constraints for graph
925 insert_into_complex (constraint_graph_t graph,
926 unsigned int var, constraint_t c)
928 VEC (constraint_t, heap) *complex = graph->complex[var];
929 unsigned int place = VEC_lower_bound (constraint_t, complex, c,
932 /* Only insert constraints that do not already exist. */
933 if (place >= VEC_length (constraint_t, complex)
934 || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
935 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
939 /* Condense two variable nodes into a single variable node, by moving
940 all associated info from SRC to TO. */
943 merge_node_constraints (constraint_graph_t graph, unsigned int to,
949 gcc_assert (find (from) == to);
951 /* Move all complex constraints from src node into to node */
952 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
954 /* In complex constraints for node src, we may have either
955 a = *src, and *src = a, or an offseted constraint which are
956 always added to the rhs node's constraints. */
958 if (c->rhs.type == DEREF)
960 else if (c->lhs.type == DEREF)
965 constraint_set_union (&graph->complex[to], &graph->complex[from]);
966 VEC_free (constraint_t, heap, graph->complex[from]);
967 graph->complex[from] = NULL;
971 /* Remove edges involving NODE from GRAPH. */
974 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
976 if (graph->succs[node])
977 BITMAP_FREE (graph->succs[node]);
980 /* Merge GRAPH nodes FROM and TO into node TO. */
983 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
986 if (graph->indirect_cycles[from] != -1)
988 /* If we have indirect cycles with the from node, and we have
989 none on the to node, the to node has indirect cycles from the
990 from node now that they are unified.
991 If indirect cycles exist on both, unify the nodes that they
992 are in a cycle with, since we know they are in a cycle with
994 if (graph->indirect_cycles[to] == -1)
995 graph->indirect_cycles[to] = graph->indirect_cycles[from];
998 /* Merge all the successor edges. */
999 if (graph->succs[from])
1001 if (!graph->succs[to])
1002 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1003 bitmap_ior_into (graph->succs[to],
1004 graph->succs[from]);
1007 clear_edges_for_node (graph, from);
1011 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1012 it doesn't exist in the graph already. */
1015 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1021 if (!graph->implicit_preds[to])
1022 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1024 if (bitmap_set_bit (graph->implicit_preds[to], from))
1025 stats.num_implicit_edges++;
1028 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1029 it doesn't exist in the graph already.
1030 Return false if the edge already existed, true otherwise. */
1033 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1036 if (!graph->preds[to])
1037 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1038 bitmap_set_bit (graph->preds[to], from);
1041 /* Add a graph edge to GRAPH, going from FROM to TO if
1042 it doesn't exist in the graph already.
1043 Return false if the edge already existed, true otherwise. */
1046 add_graph_edge (constraint_graph_t graph, unsigned int to,
1057 if (!graph->succs[from])
1058 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1059 if (bitmap_set_bit (graph->succs[from], to))
1062 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1070 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1073 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1076 return (graph->succs[dest]
1077 && bitmap_bit_p (graph->succs[dest], src));
1080 /* Initialize the constraint graph structure to contain SIZE nodes. */
1083 init_graph (unsigned int size)
1087 graph = XCNEW (struct constraint_graph);
1089 graph->succs = XCNEWVEC (bitmap, graph->size);
1090 graph->indirect_cycles = XNEWVEC (int, graph->size);
1091 graph->rep = XNEWVEC (unsigned int, graph->size);
1092 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
1093 graph->pe = XCNEWVEC (unsigned int, graph->size);
1094 graph->pe_rep = XNEWVEC (int, graph->size);
1096 for (j = 0; j < graph->size; j++)
1099 graph->pe_rep[j] = -1;
1100 graph->indirect_cycles[j] = -1;
1104 /* Build the constraint graph, adding only predecessor edges right now. */
1107 build_pred_graph (void)
1113 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1114 graph->preds = XCNEWVEC (bitmap, graph->size);
1115 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1116 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1117 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1118 graph->points_to = XCNEWVEC (bitmap, graph->size);
1119 graph->eq_rep = XNEWVEC (int, graph->size);
1120 graph->direct_nodes = sbitmap_alloc (graph->size);
1121 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1122 sbitmap_zero (graph->direct_nodes);
1124 for (j = 0; j < FIRST_REF_NODE; j++)
1126 if (!get_varinfo (j)->is_special_var)
1127 SET_BIT (graph->direct_nodes, j);
1130 for (j = 0; j < graph->size; j++)
1131 graph->eq_rep[j] = -1;
1133 for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
1134 graph->indirect_cycles[j] = -1;
1136 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1138 struct constraint_expr lhs = c->lhs;
1139 struct constraint_expr rhs = c->rhs;
1140 unsigned int lhsvar = lhs.var;
1141 unsigned int rhsvar = rhs.var;
1143 if (lhs.type == DEREF)
1146 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1147 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1149 else if (rhs.type == DEREF)
1152 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1153 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1155 RESET_BIT (graph->direct_nodes, lhsvar);
1157 else if (rhs.type == ADDRESSOF)
1162 if (graph->points_to[lhsvar] == NULL)
1163 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1164 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1166 if (graph->pointed_by[rhsvar] == NULL)
1167 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1168 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1170 /* Implicitly, *x = y */
1171 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1173 /* All related variables are no longer direct nodes. */
1174 RESET_BIT (graph->direct_nodes, rhsvar);
1175 v = get_varinfo (rhsvar);
1176 if (!v->is_full_var)
1178 v = lookup_vi_for_tree (v->decl);
1181 RESET_BIT (graph->direct_nodes, v->id);
1186 bitmap_set_bit (graph->address_taken, rhsvar);
1188 else if (lhsvar > anything_id
1189 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1192 add_pred_graph_edge (graph, lhsvar, rhsvar);
1193 /* Implicitly, *x = *y */
1194 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1195 FIRST_REF_NODE + rhsvar);
1197 else if (lhs.offset != 0 || rhs.offset != 0)
1199 if (rhs.offset != 0)
1200 RESET_BIT (graph->direct_nodes, lhs.var);
1201 else if (lhs.offset != 0)
1202 RESET_BIT (graph->direct_nodes, rhs.var);
1207 /* Build the constraint graph, adding successor edges. */
1210 build_succ_graph (void)
1215 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1217 struct constraint_expr lhs;
1218 struct constraint_expr rhs;
1219 unsigned int lhsvar;
1220 unsigned int rhsvar;
1227 lhsvar = find (lhs.var);
1228 rhsvar = find (rhs.var);
1230 if (lhs.type == DEREF)
1232 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1233 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1235 else if (rhs.type == DEREF)
1237 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1238 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1240 else if (rhs.type == ADDRESSOF)
1243 gcc_assert (find (rhs.var) == rhs.var);
1244 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1246 else if (lhsvar > anything_id
1247 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1249 add_graph_edge (graph, lhsvar, rhsvar);
1253 /* Add edges from STOREDANYTHING to all non-direct nodes. */
1254 t = find (storedanything_id);
1255 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1257 if (!TEST_BIT (graph->direct_nodes, i))
1258 add_graph_edge (graph, find (i), t);
1263 /* Changed variables on the last iteration. */
1264 static unsigned int changed_count;
1265 static sbitmap changed;
1267 DEF_VEC_I(unsigned);
1268 DEF_VEC_ALLOC_I(unsigned,heap);
1271 /* Strongly Connected Component visitation info. */
1278 unsigned int *node_mapping;
1280 VEC(unsigned,heap) *scc_stack;
1284 /* Recursive routine to find strongly connected components in GRAPH.
1285 SI is the SCC info to store the information in, and N is the id of current
1286 graph node we are processing.
1288 This is Tarjan's strongly connected component finding algorithm, as
1289 modified by Nuutila to keep only non-root nodes on the stack.
1290 The algorithm can be found in "On finding the strongly connected
1291 connected components in a directed graph" by Esko Nuutila and Eljas
1292 Soisalon-Soininen, in Information Processing Letters volume 49,
1293 number 1, pages 9-14. */
1296 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1300 unsigned int my_dfs;
1302 SET_BIT (si->visited, n);
1303 si->dfs[n] = si->current_index ++;
1304 my_dfs = si->dfs[n];
1306 /* Visit all the successors. */
1307 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1311 if (i > LAST_REF_NODE)
1315 if (TEST_BIT (si->deleted, w))
1318 if (!TEST_BIT (si->visited, w))
1319 scc_visit (graph, si, w);
1321 unsigned int t = find (w);
1322 unsigned int nnode = find (n);
1323 gcc_assert (nnode == n);
1325 if (si->dfs[t] < si->dfs[nnode])
1326 si->dfs[n] = si->dfs[t];
1330 /* See if any components have been identified. */
1331 if (si->dfs[n] == my_dfs)
1333 if (VEC_length (unsigned, si->scc_stack) > 0
1334 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1336 bitmap scc = BITMAP_ALLOC (NULL);
1337 bool have_ref_node = n >= FIRST_REF_NODE;
1338 unsigned int lowest_node;
1341 bitmap_set_bit (scc, n);
1343 while (VEC_length (unsigned, si->scc_stack) != 0
1344 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1346 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1348 bitmap_set_bit (scc, w);
1349 if (w >= FIRST_REF_NODE)
1350 have_ref_node = true;
1353 lowest_node = bitmap_first_set_bit (scc);
1354 gcc_assert (lowest_node < FIRST_REF_NODE);
1356 /* Collapse the SCC nodes into a single node, and mark the
1358 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1360 if (i < FIRST_REF_NODE)
1362 if (unite (lowest_node, i))
1363 unify_nodes (graph, lowest_node, i, false);
1367 unite (lowest_node, i);
1368 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1372 SET_BIT (si->deleted, n);
1375 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1378 /* Unify node FROM into node TO, updating the changed count if
1379 necessary when UPDATE_CHANGED is true. */
1382 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1383 bool update_changed)
1386 gcc_assert (to != from && find (to) == to);
1387 if (dump_file && (dump_flags & TDF_DETAILS))
1388 fprintf (dump_file, "Unifying %s to %s\n",
1389 get_varinfo (from)->name,
1390 get_varinfo (to)->name);
1393 stats.unified_vars_dynamic++;
1395 stats.unified_vars_static++;
1397 merge_graph_nodes (graph, to, from);
1398 merge_node_constraints (graph, to, from);
1400 /* Mark TO as changed if FROM was changed. If TO was already marked
1401 as changed, decrease the changed count. */
1403 if (update_changed && TEST_BIT (changed, from))
1405 RESET_BIT (changed, from);
1406 if (!TEST_BIT (changed, to))
1407 SET_BIT (changed, to);
1410 gcc_assert (changed_count > 0);
1414 if (get_varinfo (from)->solution)
1416 /* If the solution changes because of the merging, we need to mark
1417 the variable as changed. */
1418 if (bitmap_ior_into (get_varinfo (to)->solution,
1419 get_varinfo (from)->solution))
1421 if (update_changed && !TEST_BIT (changed, to))
1423 SET_BIT (changed, to);
1428 BITMAP_FREE (get_varinfo (from)->solution);
1429 BITMAP_FREE (get_varinfo (from)->oldsolution);
1431 if (stats.iterations > 0)
1433 BITMAP_FREE (get_varinfo (to)->oldsolution);
1434 get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1437 if (valid_graph_edge (graph, to, to))
1439 if (graph->succs[to])
1440 bitmap_clear_bit (graph->succs[to], to);
1444 /* Information needed to compute the topological ordering of a graph. */
1448 /* sbitmap of visited nodes. */
1450 /* Array that stores the topological order of the graph, *in
1452 VEC(unsigned,heap) *topo_order;
1456 /* Initialize and return a topological info structure. */
1458 static struct topo_info *
1459 init_topo_info (void)
1461 size_t size = graph->size;
1462 struct topo_info *ti = XNEW (struct topo_info);
1463 ti->visited = sbitmap_alloc (size);
1464 sbitmap_zero (ti->visited);
1465 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1470 /* Free the topological sort info pointed to by TI. */
1473 free_topo_info (struct topo_info *ti)
1475 sbitmap_free (ti->visited);
1476 VEC_free (unsigned, heap, ti->topo_order);
1480 /* Visit the graph in topological order, and store the order in the
1481 topo_info structure. */
1484 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1490 SET_BIT (ti->visited, n);
1492 if (graph->succs[n])
1493 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1495 if (!TEST_BIT (ti->visited, j))
1496 topo_visit (graph, ti, j);
1499 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1502 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1503 starting solution for y. */
1506 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1509 unsigned int lhs = c->lhs.var;
1511 bitmap sol = get_varinfo (lhs)->solution;
1514 HOST_WIDE_INT roffset = c->rhs.offset;
1516 /* Our IL does not allow this. */
1517 gcc_assert (c->lhs.offset == 0);
1519 /* If the solution of Y contains anything it is good enough to transfer
1521 if (bitmap_bit_p (delta, anything_id))
1523 flag |= bitmap_set_bit (sol, anything_id);
1527 /* If we do not know at with offset the rhs is dereferenced compute
1528 the reachability set of DELTA, conservatively assuming it is
1529 dereferenced at all valid offsets. */
1530 if (roffset == UNKNOWN_OFFSET)
1532 solution_set_expand (delta, delta);
1533 /* No further offset processing is necessary. */
1537 /* For each variable j in delta (Sol(y)), add
1538 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1539 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1541 varinfo_t v = get_varinfo (j);
1542 HOST_WIDE_INT fieldoffset = v->offset + roffset;
1546 fieldoffset = v->offset;
1547 else if (roffset != 0)
1548 v = first_vi_for_offset (v, fieldoffset);
1549 /* If the access is outside of the variable we can ignore it. */
1557 /* Adding edges from the special vars is pointless.
1558 They don't have sets that can change. */
1559 if (get_varinfo (t)->is_special_var)
1560 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1561 /* Merging the solution from ESCAPED needlessly increases
1562 the set. Use ESCAPED as representative instead. */
1563 else if (v->id == escaped_id)
1564 flag |= bitmap_set_bit (sol, escaped_id);
1565 else if (add_graph_edge (graph, lhs, t))
1566 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1568 /* If the variable is not exactly at the requested offset
1569 we have to include the next one. */
1570 if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1575 fieldoffset = v->offset;
1581 /* If the LHS solution changed, mark the var as changed. */
1584 get_varinfo (lhs)->solution = sol;
1585 if (!TEST_BIT (changed, lhs))
1587 SET_BIT (changed, lhs);
1593 /* Process a constraint C that represents *(x + off) = y using DELTA
1594 as the starting solution for x. */
1597 do_ds_constraint (constraint_t c, bitmap delta)
1599 unsigned int rhs = c->rhs.var;
1600 bitmap sol = get_varinfo (rhs)->solution;
1603 HOST_WIDE_INT loff = c->lhs.offset;
1605 /* Our IL does not allow this. */
1606 gcc_assert (c->rhs.offset == 0);
1608 /* If the solution of y contains ANYTHING simply use the ANYTHING
1609 solution. This avoids needlessly increasing the points-to sets. */
1610 if (bitmap_bit_p (sol, anything_id))
1611 sol = get_varinfo (find (anything_id))->solution;
1613 /* If the solution for x contains ANYTHING we have to merge the
1614 solution of y into all pointer variables which we do via
1616 if (bitmap_bit_p (delta, anything_id))
1618 unsigned t = find (storedanything_id);
1619 if (add_graph_edge (graph, t, rhs))
1621 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1623 if (!TEST_BIT (changed, t))
1625 SET_BIT (changed, t);
1633 /* If we do not know at with offset the rhs is dereferenced compute
1634 the reachability set of DELTA, conservatively assuming it is
1635 dereferenced at all valid offsets. */
1636 if (loff == UNKNOWN_OFFSET)
1638 solution_set_expand (delta, delta);
1642 /* For each member j of delta (Sol(x)), add an edge from y to j and
1643 union Sol(y) into Sol(j) */
1644 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1646 varinfo_t v = get_varinfo (j);
1648 HOST_WIDE_INT fieldoffset = v->offset + loff;
1650 /* If v is a global variable then this is an escape point. */
1651 if (v->is_global_var)
1653 t = find (escaped_id);
1654 if (add_graph_edge (graph, t, rhs)
1655 && bitmap_ior_into (get_varinfo (t)->solution, sol)
1656 && !TEST_BIT (changed, t))
1658 SET_BIT (changed, t);
1663 if (v->is_special_var)
1667 fieldoffset = v->offset;
1669 v = first_vi_for_offset (v, fieldoffset);
1670 /* If the access is outside of the variable we can ignore it. */
1676 if (v->may_have_pointers)
1679 if (add_graph_edge (graph, t, rhs)
1680 && bitmap_ior_into (get_varinfo (t)->solution, sol)
1681 && !TEST_BIT (changed, t))
1683 SET_BIT (changed, t);
1688 /* If the variable is not exactly at the requested offset
1689 we have to include the next one. */
1690 if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1695 fieldoffset = v->offset;
1701 /* Handle a non-simple (simple meaning requires no iteration),
1702 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1705 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1707 if (c->lhs.type == DEREF)
1709 if (c->rhs.type == ADDRESSOF)
1716 do_ds_constraint (c, delta);
1719 else if (c->rhs.type == DEREF)
1722 if (!(get_varinfo (c->lhs.var)->is_special_var))
1723 do_sd_constraint (graph, c, delta);
1731 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1732 solution = get_varinfo (c->rhs.var)->solution;
1733 tmp = get_varinfo (c->lhs.var)->solution;
1735 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1739 get_varinfo (c->lhs.var)->solution = tmp;
1740 if (!TEST_BIT (changed, c->lhs.var))
1742 SET_BIT (changed, c->lhs.var);
1749 /* Initialize and return a new SCC info structure. */
1751 static struct scc_info *
1752 init_scc_info (size_t size)
1754 struct scc_info *si = XNEW (struct scc_info);
1757 si->current_index = 0;
1758 si->visited = sbitmap_alloc (size);
1759 sbitmap_zero (si->visited);
1760 si->deleted = sbitmap_alloc (size);
1761 sbitmap_zero (si->deleted);
1762 si->node_mapping = XNEWVEC (unsigned int, size);
1763 si->dfs = XCNEWVEC (unsigned int, size);
1765 for (i = 0; i < size; i++)
1766 si->node_mapping[i] = i;
1768 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1772 /* Free an SCC info structure pointed to by SI */
1775 free_scc_info (struct scc_info *si)
1777 sbitmap_free (si->visited);
1778 sbitmap_free (si->deleted);
1779 free (si->node_mapping);
1781 VEC_free (unsigned, heap, si->scc_stack);
1786 /* Find indirect cycles in GRAPH that occur, using strongly connected
1787 components, and note them in the indirect cycles map.
1789 This technique comes from Ben Hardekopf and Calvin Lin,
1790 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1791 Lines of Code", submitted to PLDI 2007. */
1794 find_indirect_cycles (constraint_graph_t graph)
1797 unsigned int size = graph->size;
1798 struct scc_info *si = init_scc_info (size);
1800 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1801 if (!TEST_BIT (si->visited, i) && find (i) == i)
1802 scc_visit (graph, si, i);
1807 /* Compute a topological ordering for GRAPH, and store the result in the
1808 topo_info structure TI. */
1811 compute_topo_order (constraint_graph_t graph,
1812 struct topo_info *ti)
1815 unsigned int size = graph->size;
1817 for (i = 0; i != size; ++i)
1818 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1819 topo_visit (graph, ti, i);
1822 /* Structure used to for hash value numbering of pointer equivalence
1825 typedef struct equiv_class_label
1828 unsigned int equivalence_class;
1830 } *equiv_class_label_t;
1831 typedef const struct equiv_class_label *const_equiv_class_label_t;
1833 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1835 static htab_t pointer_equiv_class_table;
1837 /* A hashtable for mapping a bitmap of labels->location equivalence
1839 static htab_t location_equiv_class_table;
1841 /* Hash function for a equiv_class_label_t */
1844 equiv_class_label_hash (const void *p)
1846 const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
1847 return ecl->hashcode;
1850 /* Equality function for two equiv_class_label_t's. */
1853 equiv_class_label_eq (const void *p1, const void *p2)
1855 const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
1856 const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
1857 return (eql1->hashcode == eql2->hashcode
1858 && bitmap_equal_p (eql1->labels, eql2->labels));
1861 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
1865 equiv_class_lookup (htab_t table, bitmap labels)
1868 struct equiv_class_label ecl;
1870 ecl.labels = labels;
1871 ecl.hashcode = bitmap_hash (labels);
1873 slot = htab_find_slot_with_hash (table, &ecl,
1874 ecl.hashcode, NO_INSERT);
1878 return ((equiv_class_label_t) *slot)->equivalence_class;
1882 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
1886 equiv_class_add (htab_t table, unsigned int equivalence_class,
1890 equiv_class_label_t ecl = XNEW (struct equiv_class_label);
1892 ecl->labels = labels;
1893 ecl->equivalence_class = equivalence_class;
1894 ecl->hashcode = bitmap_hash (labels);
1896 slot = htab_find_slot_with_hash (table, ecl,
1897 ecl->hashcode, INSERT);
1898 gcc_assert (!*slot);
1899 *slot = (void *) ecl;
1902 /* Perform offline variable substitution.
1904 This is a worst case quadratic time way of identifying variables
1905 that must have equivalent points-to sets, including those caused by
1906 static cycles, and single entry subgraphs, in the constraint graph.
1908 The technique is described in "Exploiting Pointer and Location
1909 Equivalence to Optimize Pointer Analysis. In the 14th International
1910 Static Analysis Symposium (SAS), August 2007." It is known as the
1911 "HU" algorithm, and is equivalent to value numbering the collapsed
1912 constraint graph including evaluating unions.
1914 The general method of finding equivalence classes is as follows:
1915 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1916 Initialize all non-REF nodes to be direct nodes.
1917 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1919 For each constraint containing the dereference, we also do the same
1922 We then compute SCC's in the graph and unify nodes in the same SCC,
1925 For each non-collapsed node x:
1926 Visit all unvisited explicit incoming edges.
1927 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1929 Lookup the equivalence class for pts(x).
1930 If we found one, equivalence_class(x) = found class.
1931 Otherwise, equivalence_class(x) = new class, and new_class is
1932 added to the lookup table.
1934 All direct nodes with the same equivalence class can be replaced
1935 with a single representative node.
1936 All unlabeled nodes (label == 0) are not pointers and all edges
1937 involving them can be eliminated.
1938 We perform these optimizations during rewrite_constraints
1940 In addition to pointer equivalence class finding, we also perform
1941 location equivalence class finding. This is the set of variables
1942 that always appear together in points-to sets. We use this to
1943 compress the size of the points-to sets. */
1945 /* Current maximum pointer equivalence class id. */
1946 static int pointer_equiv_class;
1948 /* Current maximum location equivalence class id. */
1949 static int location_equiv_class;
1951 /* Recursive routine to find strongly connected components in GRAPH,
1952 and label it's nodes with DFS numbers. */
1955 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1959 unsigned int my_dfs;
1961 gcc_assert (si->node_mapping[n] == n);
1962 SET_BIT (si->visited, n);
1963 si->dfs[n] = si->current_index ++;
1964 my_dfs = si->dfs[n];
1966 /* Visit all the successors. */
1967 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1969 unsigned int w = si->node_mapping[i];
1971 if (TEST_BIT (si->deleted, w))
1974 if (!TEST_BIT (si->visited, w))
1975 condense_visit (graph, si, w);
1977 unsigned int t = si->node_mapping[w];
1978 unsigned int nnode = si->node_mapping[n];
1979 gcc_assert (nnode == n);
1981 if (si->dfs[t] < si->dfs[nnode])
1982 si->dfs[n] = si->dfs[t];
1986 /* Visit all the implicit predecessors. */
1987 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1989 unsigned int w = si->node_mapping[i];
1991 if (TEST_BIT (si->deleted, w))
1994 if (!TEST_BIT (si->visited, w))
1995 condense_visit (graph, si, w);
1997 unsigned int t = si->node_mapping[w];
1998 unsigned int nnode = si->node_mapping[n];
1999 gcc_assert (nnode == n);
2001 if (si->dfs[t] < si->dfs[nnode])
2002 si->dfs[n] = si->dfs[t];
2006 /* See if any components have been identified. */
2007 if (si->dfs[n] == my_dfs)
2009 while (VEC_length (unsigned, si->scc_stack) != 0
2010 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
2012 unsigned int w = VEC_pop (unsigned, si->scc_stack);
2013 si->node_mapping[w] = n;
2015 if (!TEST_BIT (graph->direct_nodes, w))
2016 RESET_BIT (graph->direct_nodes, n);
2018 /* Unify our nodes. */
2019 if (graph->preds[w])
2021 if (!graph->preds[n])
2022 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2023 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2025 if (graph->implicit_preds[w])
2027 if (!graph->implicit_preds[n])
2028 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2029 bitmap_ior_into (graph->implicit_preds[n],
2030 graph->implicit_preds[w]);
2032 if (graph->points_to[w])
2034 if (!graph->points_to[n])
2035 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2036 bitmap_ior_into (graph->points_to[n],
2037 graph->points_to[w]);
2040 SET_BIT (si->deleted, n);
2043 VEC_safe_push (unsigned, heap, si->scc_stack, n);
2046 /* Label pointer equivalences. */
2049 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2053 SET_BIT (si->visited, n);
2055 if (!graph->points_to[n])
2056 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2058 /* Label and union our incoming edges's points to sets. */
2059 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2061 unsigned int w = si->node_mapping[i];
2062 if (!TEST_BIT (si->visited, w))
2063 label_visit (graph, si, w);
2065 /* Skip unused edges */
2066 if (w == n || graph->pointer_label[w] == 0)
2069 if (graph->points_to[w])
2070 bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
2072 /* Indirect nodes get fresh variables. */
2073 if (!TEST_BIT (graph->direct_nodes, n))
2074 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2076 if (!bitmap_empty_p (graph->points_to[n]))
2078 unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
2079 graph->points_to[n]);
2082 label = pointer_equiv_class++;
2083 equiv_class_add (pointer_equiv_class_table,
2084 label, graph->points_to[n]);
2086 graph->pointer_label[n] = label;
2090 /* Perform offline variable substitution, discovering equivalence
2091 classes, and eliminating non-pointer variables. */
2093 static struct scc_info *
2094 perform_var_substitution (constraint_graph_t graph)
2097 unsigned int size = graph->size;
2098 struct scc_info *si = init_scc_info (size);
2100 bitmap_obstack_initialize (&iteration_obstack);
2101 pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
2102 equiv_class_label_eq, free);
2103 location_equiv_class_table = htab_create (511, equiv_class_label_hash,
2104 equiv_class_label_eq, free);
2105 pointer_equiv_class = 1;
2106 location_equiv_class = 1;
2108 /* Condense the nodes, which means to find SCC's, count incoming
2109 predecessors, and unite nodes in SCC's. */
2110 for (i = 0; i < FIRST_REF_NODE; i++)
2111 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2112 condense_visit (graph, si, si->node_mapping[i]);
2114 sbitmap_zero (si->visited);
2115 /* Actually the label the nodes for pointer equivalences */
2116 for (i = 0; i < FIRST_REF_NODE; i++)
2117 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2118 label_visit (graph, si, si->node_mapping[i]);
2120 /* Calculate location equivalence labels. */
2121 for (i = 0; i < FIRST_REF_NODE; i++)
2128 if (!graph->pointed_by[i])
2130 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2132 /* Translate the pointed-by mapping for pointer equivalence
2134 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2136 bitmap_set_bit (pointed_by,
2137 graph->pointer_label[si->node_mapping[j]]);
2139 /* The original pointed_by is now dead. */
2140 BITMAP_FREE (graph->pointed_by[i]);
2142 /* Look up the location equivalence label if one exists, or make
2144 label = equiv_class_lookup (location_equiv_class_table,
2148 label = location_equiv_class++;
2149 equiv_class_add (location_equiv_class_table,
2154 if (dump_file && (dump_flags & TDF_DETAILS))
2155 fprintf (dump_file, "Found location equivalence for node %s\n",
2156 get_varinfo (i)->name);
2157 BITMAP_FREE (pointed_by);
2159 graph->loc_label[i] = label;
2163 if (dump_file && (dump_flags & TDF_DETAILS))
2164 for (i = 0; i < FIRST_REF_NODE; i++)
2166 bool direct_node = TEST_BIT (graph->direct_nodes, i);
2168 "Equivalence classes for %s node id %d:%s are pointer: %d"
2170 direct_node ? "Direct node" : "Indirect node", i,
2171 get_varinfo (i)->name,
2172 graph->pointer_label[si->node_mapping[i]],
2173 graph->loc_label[si->node_mapping[i]]);
2176 /* Quickly eliminate our non-pointer variables. */
2178 for (i = 0; i < FIRST_REF_NODE; i++)
2180 unsigned int node = si->node_mapping[i];
2182 if (graph->pointer_label[node] == 0)
2184 if (dump_file && (dump_flags & TDF_DETAILS))
2186 "%s is a non-pointer variable, eliminating edges.\n",
2187 get_varinfo (node)->name);
2188 stats.nonpointer_vars++;
2189 clear_edges_for_node (graph, node);
2196 /* Free information that was only necessary for variable
2200 free_var_substitution_info (struct scc_info *si)
2203 free (graph->pointer_label);
2204 free (graph->loc_label);
2205 free (graph->pointed_by);
2206 free (graph->points_to);
2207 free (graph->eq_rep);
2208 sbitmap_free (graph->direct_nodes);
2209 htab_delete (pointer_equiv_class_table);
2210 htab_delete (location_equiv_class_table);
2211 bitmap_obstack_release (&iteration_obstack);
2214 /* Return an existing node that is equivalent to NODE, which has
2215 equivalence class LABEL, if one exists. Return NODE otherwise. */
2218 find_equivalent_node (constraint_graph_t graph,
2219 unsigned int node, unsigned int label)
2221 /* If the address version of this variable is unused, we can
2222 substitute it for anything else with the same label.
2223 Otherwise, we know the pointers are equivalent, but not the
2224 locations, and we can unite them later. */
2226 if (!bitmap_bit_p (graph->address_taken, node))
2228 gcc_assert (label < graph->size);
2230 if (graph->eq_rep[label] != -1)
2232 /* Unify the two variables since we know they are equivalent. */
2233 if (unite (graph->eq_rep[label], node))
2234 unify_nodes (graph, graph->eq_rep[label], node, false);
2235 return graph->eq_rep[label];
2239 graph->eq_rep[label] = node;
2240 graph->pe_rep[label] = node;
2245 gcc_assert (label < graph->size);
2246 graph->pe[node] = label;
2247 if (graph->pe_rep[label] == -1)
2248 graph->pe_rep[label] = node;
2254 /* Unite pointer equivalent but not location equivalent nodes in
2255 GRAPH. This may only be performed once variable substitution is
2259 unite_pointer_equivalences (constraint_graph_t graph)
2263 /* Go through the pointer equivalences and unite them to their
2264 representative, if they aren't already. */
2265 for (i = 0; i < FIRST_REF_NODE; i++)
2267 unsigned int label = graph->pe[i];
2270 int label_rep = graph->pe_rep[label];
2272 if (label_rep == -1)
2275 label_rep = find (label_rep);
2276 if (label_rep >= 0 && unite (label_rep, find (i)))
2277 unify_nodes (graph, label_rep, i, false);
2282 /* Move complex constraints to the GRAPH nodes they belong to. */
2285 move_complex_constraints (constraint_graph_t graph)
2290 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2294 struct constraint_expr lhs = c->lhs;
2295 struct constraint_expr rhs = c->rhs;
2297 if (lhs.type == DEREF)
2299 insert_into_complex (graph, lhs.var, c);
2301 else if (rhs.type == DEREF)
2303 if (!(get_varinfo (lhs.var)->is_special_var))
2304 insert_into_complex (graph, rhs.var, c);
2306 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2307 && (lhs.offset != 0 || rhs.offset != 0))
2309 insert_into_complex (graph, rhs.var, c);
2316 /* Optimize and rewrite complex constraints while performing
2317 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2318 result of perform_variable_substitution. */
2321 rewrite_constraints (constraint_graph_t graph,
2322 struct scc_info *si)
2328 for (j = 0; j < graph->size; j++)
2329 gcc_assert (find (j) == j);
2331 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2333 struct constraint_expr lhs = c->lhs;
2334 struct constraint_expr rhs = c->rhs;
2335 unsigned int lhsvar = find (lhs.var);
2336 unsigned int rhsvar = find (rhs.var);
2337 unsigned int lhsnode, rhsnode;
2338 unsigned int lhslabel, rhslabel;
2340 lhsnode = si->node_mapping[lhsvar];
2341 rhsnode = si->node_mapping[rhsvar];
2342 lhslabel = graph->pointer_label[lhsnode];
2343 rhslabel = graph->pointer_label[rhsnode];
2345 /* See if it is really a non-pointer variable, and if so, ignore
2349 if (dump_file && (dump_flags & TDF_DETAILS))
2352 fprintf (dump_file, "%s is a non-pointer variable,"
2353 "ignoring constraint:",
2354 get_varinfo (lhs.var)->name);
2355 dump_constraint (dump_file, c);
2357 VEC_replace (constraint_t, constraints, i, NULL);
2363 if (dump_file && (dump_flags & TDF_DETAILS))
2366 fprintf (dump_file, "%s is a non-pointer variable,"
2367 "ignoring constraint:",
2368 get_varinfo (rhs.var)->name);
2369 dump_constraint (dump_file, c);
2371 VEC_replace (constraint_t, constraints, i, NULL);
2375 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2376 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2377 c->lhs.var = lhsvar;
2378 c->rhs.var = rhsvar;
2383 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2384 part of an SCC, false otherwise. */
2387 eliminate_indirect_cycles (unsigned int node)
2389 if (graph->indirect_cycles[node] != -1
2390 && !bitmap_empty_p (get_varinfo (node)->solution))
2393 VEC(unsigned,heap) *queue = NULL;
2395 unsigned int to = find (graph->indirect_cycles[node]);
2398 /* We can't touch the solution set and call unify_nodes
2399 at the same time, because unify_nodes is going to do
2400 bitmap unions into it. */
2402 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2404 if (find (i) == i && i != to)
2407 VEC_safe_push (unsigned, heap, queue, i);
2412 VEC_iterate (unsigned, queue, queuepos, i);
2415 unify_nodes (graph, to, i, true);
2417 VEC_free (unsigned, heap, queue);
2423 /* Solve the constraint graph GRAPH using our worklist solver.
2424 This is based on the PW* family of solvers from the "Efficient Field
2425 Sensitive Pointer Analysis for C" paper.
2426 It works by iterating over all the graph nodes, processing the complex
2427 constraints and propagating the copy constraints, until everything stops
2428 changed. This corresponds to steps 6-8 in the solving list given above. */
2431 solve_graph (constraint_graph_t graph)
2433 unsigned int size = graph->size;
2438 changed = sbitmap_alloc (size);
2439 sbitmap_zero (changed);
2441 /* Mark all initial non-collapsed nodes as changed. */
2442 for (i = 0; i < size; i++)
2444 varinfo_t ivi = get_varinfo (i);
2445 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2446 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2447 || VEC_length (constraint_t, graph->complex[i]) > 0))
2449 SET_BIT (changed, i);
2454 /* Allocate a bitmap to be used to store the changed bits. */
2455 pts = BITMAP_ALLOC (&pta_obstack);
2457 while (changed_count > 0)
2460 struct topo_info *ti = init_topo_info ();
2463 bitmap_obstack_initialize (&iteration_obstack);
2465 compute_topo_order (graph, ti);
2467 while (VEC_length (unsigned, ti->topo_order) != 0)
2470 i = VEC_pop (unsigned, ti->topo_order);
2472 /* If this variable is not a representative, skip it. */
2476 /* In certain indirect cycle cases, we may merge this
2477 variable to another. */
2478 if (eliminate_indirect_cycles (i) && find (i) != i)
2481 /* If the node has changed, we need to process the
2482 complex constraints and outgoing edges again. */
2483 if (TEST_BIT (changed, i))
2488 VEC(constraint_t,heap) *complex = graph->complex[i];
2489 bool solution_empty;
2491 RESET_BIT (changed, i);
2494 /* Compute the changed set of solution bits. */
2495 bitmap_and_compl (pts, get_varinfo (i)->solution,
2496 get_varinfo (i)->oldsolution);
2498 if (bitmap_empty_p (pts))
2501 bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2503 solution = get_varinfo (i)->solution;
2504 solution_empty = bitmap_empty_p (solution);
2506 /* Process the complex constraints */
2507 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2509 /* XXX: This is going to unsort the constraints in
2510 some cases, which will occasionally add duplicate
2511 constraints during unification. This does not
2512 affect correctness. */
2513 c->lhs.var = find (c->lhs.var);
2514 c->rhs.var = find (c->rhs.var);
2516 /* The only complex constraint that can change our
2517 solution to non-empty, given an empty solution,
2518 is a constraint where the lhs side is receiving
2519 some set from elsewhere. */
2520 if (!solution_empty || c->lhs.type != DEREF)
2521 do_complex_constraint (graph, c, pts);
2524 solution_empty = bitmap_empty_p (solution);
2526 if (!solution_empty)
2529 unsigned eff_escaped_id = find (escaped_id);
2531 /* Propagate solution to all successors. */
2532 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2538 unsigned int to = find (j);
2539 tmp = get_varinfo (to)->solution;
2542 /* Don't try to propagate to ourselves. */
2546 /* If we propagate from ESCAPED use ESCAPED as
2548 if (i == eff_escaped_id)
2549 flag = bitmap_set_bit (tmp, escaped_id);
2551 flag = set_union_with_increment (tmp, pts, 0);
2555 get_varinfo (to)->solution = tmp;
2556 if (!TEST_BIT (changed, to))
2558 SET_BIT (changed, to);
2566 free_topo_info (ti);
2567 bitmap_obstack_release (&iteration_obstack);
2571 sbitmap_free (changed);
2572 bitmap_obstack_release (&oldpta_obstack);
2575 /* Map from trees to variable infos. */
2576 static struct pointer_map_t *vi_for_tree;
2579 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2582 insert_vi_for_tree (tree t, varinfo_t vi)
2584 void **slot = pointer_map_insert (vi_for_tree, t);
2586 gcc_assert (*slot == NULL);
2590 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2591 exist in the map, return NULL, otherwise, return the varinfo we found. */
2594 lookup_vi_for_tree (tree t)
2596 void **slot = pointer_map_contains (vi_for_tree, t);
2600 return (varinfo_t) *slot;
2603 /* Return a printable name for DECL */
2606 alias_get_name (tree decl)
2608 const char *res = get_name (decl);
2610 int num_printed = 0;
2619 if (TREE_CODE (decl) == SSA_NAME)
2621 num_printed = asprintf (&temp, "%s_%u",
2622 alias_get_name (SSA_NAME_VAR (decl)),
2623 SSA_NAME_VERSION (decl));
2625 else if (DECL_P (decl))
2627 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2629 if (num_printed > 0)
2631 res = ggc_strdup (temp);
2637 /* Find the variable id for tree T in the map.
2638 If T doesn't exist in the map, create an entry for it and return it. */
2641 get_vi_for_tree (tree t)
2643 void **slot = pointer_map_contains (vi_for_tree, t);
2645 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2647 return (varinfo_t) *slot;
2650 /* Get a scalar constraint expression for a new temporary variable. */
2652 static struct constraint_expr
2653 new_scalar_tmp_constraint_exp (const char *name)
2655 struct constraint_expr tmp;
2658 vi = new_var_info (NULL_TREE, name);
2662 vi->is_full_var = 1;
2671 /* Get a constraint expression vector from an SSA_VAR_P node.
2672 If address_p is true, the result will be taken its address of. */
2675 get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
2677 struct constraint_expr cexpr;
2680 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2681 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2683 /* For parameters, get at the points-to set for the actual parm
2685 if (TREE_CODE (t) == SSA_NAME
2686 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2687 && SSA_NAME_IS_DEFAULT_DEF (t))
2689 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2693 vi = get_vi_for_tree (t);
2695 cexpr.type = SCALAR;
2697 /* If we determine the result is "anything", and we know this is readonly,
2698 say it points to readonly memory instead. */
2699 if (cexpr.var == anything_id && TREE_READONLY (t))
2702 cexpr.type = ADDRESSOF;
2703 cexpr.var = readonly_id;
2706 /* If we are not taking the address of the constraint expr, add all
2707 sub-fiels of the variable as well. */
2710 for (; vi; vi = vi->next)
2713 VEC_safe_push (ce_s, heap, *results, &cexpr);
2718 VEC_safe_push (ce_s, heap, *results, &cexpr);
2721 /* Process constraint T, performing various simplifications and then
2722 adding it to our list of overall constraints. */
2725 process_constraint (constraint_t t)
2727 struct constraint_expr rhs = t->rhs;
2728 struct constraint_expr lhs = t->lhs;
2730 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2731 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2733 /* If we didn't get any useful constraint from the lhs we get
2734 &ANYTHING as fallback from get_constraint_for. Deal with
2735 it here by turning it into *ANYTHING. */
2736 if (lhs.type == ADDRESSOF
2737 && lhs.var == anything_id)
2740 /* ADDRESSOF on the lhs is invalid. */
2741 gcc_assert (lhs.type != ADDRESSOF);
2743 /* This can happen in our IR with things like n->a = *p */
2744 if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2746 /* Split into tmp = *rhs, *lhs = tmp */
2747 struct constraint_expr tmplhs;
2748 tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp");
2749 process_constraint (new_constraint (tmplhs, rhs));
2750 process_constraint (new_constraint (lhs, tmplhs));
2752 else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
2754 /* Split into tmp = &rhs, *lhs = tmp */
2755 struct constraint_expr tmplhs;
2756 tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp");
2757 process_constraint (new_constraint (tmplhs, rhs));
2758 process_constraint (new_constraint (lhs, tmplhs));
2762 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2763 VEC_safe_push (constraint_t, heap, constraints, t);
2767 /* Return true if T is a type that could contain pointers. */
2770 type_could_have_pointers (tree type)
2772 if (POINTER_TYPE_P (type))
2775 if (TREE_CODE (type) == ARRAY_TYPE)
2776 return type_could_have_pointers (TREE_TYPE (type));
2778 return AGGREGATE_TYPE_P (type);
2781 /* Return true if T is a variable of a type that could contain
2785 could_have_pointers (tree t)
2787 return type_could_have_pointers (TREE_TYPE (t));
2790 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2793 static HOST_WIDE_INT
2794 bitpos_of_field (const tree fdecl)
2797 if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2798 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2801 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2802 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2806 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2807 resulting constraint expressions in *RESULTS. */
2810 get_constraint_for_ptr_offset (tree ptr, tree offset,
2811 VEC (ce_s, heap) **results)
2813 struct constraint_expr *c;
2815 HOST_WIDE_INT rhsunitoffset, rhsoffset;
2817 /* If we do not do field-sensitive PTA adding offsets to pointers
2818 does not change the points-to solution. */
2819 if (!use_field_sensitive)
2821 get_constraint_for (ptr, results);
2825 /* If the offset is not a non-negative integer constant that fits
2826 in a HOST_WIDE_INT, we have to fall back to a conservative
2827 solution which includes all sub-fields of all pointed-to
2828 variables of ptr. */
2829 if (offset == NULL_TREE
2830 || !host_integerp (offset, 0))
2831 rhsoffset = UNKNOWN_OFFSET;
2834 /* Make sure the bit-offset also fits. */
2835 rhsunitoffset = TREE_INT_CST_LOW (offset);
2836 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
2837 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
2838 rhsoffset = UNKNOWN_OFFSET;
2841 get_constraint_for (ptr, results);
2845 /* As we are eventually appending to the solution do not use
2846 VEC_iterate here. */
2847 n = VEC_length (ce_s, *results);
2848 for (j = 0; j < n; j++)
2851 c = VEC_index (ce_s, *results, j);
2852 curr = get_varinfo (c->var);
2854 if (c->type == ADDRESSOF
2855 /* If this varinfo represents a full variable just use it. */
2856 && curr->is_full_var)
2858 else if (c->type == ADDRESSOF
2859 /* If we do not know the offset add all subfields. */
2860 && rhsoffset == UNKNOWN_OFFSET)
2862 varinfo_t temp = lookup_vi_for_tree (curr->decl);
2865 struct constraint_expr c2;
2867 c2.type = ADDRESSOF;
2869 if (c2.var != c->var)
2870 VEC_safe_push (ce_s, heap, *results, &c2);
2875 else if (c->type == ADDRESSOF)
2878 unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
2880 /* Search the sub-field which overlaps with the
2881 pointed-to offset. If the result is outside of the variable
2882 we have to provide a conservative result, as the variable is
2883 still reachable from the resulting pointer (even though it
2884 technically cannot point to anything). The last and first
2885 sub-fields are such conservative results.
2886 ??? If we always had a sub-field for &object + 1 then
2887 we could represent this in a more precise way. */
2889 && curr->offset < offset)
2891 temp = first_or_preceding_vi_for_offset (curr, offset);
2893 /* If the found variable is not exactly at the pointed to
2894 result, we have to include the next variable in the
2895 solution as well. Otherwise two increments by offset / 2
2896 do not result in the same or a conservative superset
2898 if (temp->offset != offset
2899 && temp->next != NULL)
2901 struct constraint_expr c2;
2902 c2.var = temp->next->id;
2903 c2.type = ADDRESSOF;
2905 VEC_safe_push (ce_s, heap, *results, &c2);
2911 c->offset = rhsoffset;
2916 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
2917 If address_p is true the result will be taken its address of. */
2920 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
2924 HOST_WIDE_INT bitsize = -1;
2925 HOST_WIDE_INT bitmaxsize = -1;
2926 HOST_WIDE_INT bitpos;
2928 struct constraint_expr *result;
2930 /* Some people like to do cute things like take the address of
2933 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2934 forzero = TREE_OPERAND (forzero, 0);
2936 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2938 struct constraint_expr temp;
2941 temp.var = integer_id;
2943 VEC_safe_push (ce_s, heap, *results, &temp);
2947 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2949 /* Pretend to take the address of the base, we'll take care of
2950 adding the required subset of sub-fields below. */
2951 get_constraint_for_1 (t, results, true);
2952 gcc_assert (VEC_length (ce_s, *results) == 1);
2953 result = VEC_last (ce_s, *results);
2955 if (result->type == SCALAR
2956 && get_varinfo (result->var)->is_full_var)
2957 /* For single-field vars do not bother about the offset. */
2959 else if (result->type == SCALAR)
2961 /* In languages like C, you can access one past the end of an
2962 array. You aren't allowed to dereference it, so we can
2963 ignore this constraint. When we handle pointer subtraction,
2964 we may have to do something cute here. */
2966 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
2969 /* It's also not true that the constraint will actually start at the
2970 right offset, it may start in some padding. We only care about
2971 setting the constraint to the first actual field it touches, so
2973 struct constraint_expr cexpr = *result;
2975 VEC_pop (ce_s, *results);
2977 for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
2979 if (ranges_overlap_p (curr->offset, curr->size,
2980 bitpos, bitmaxsize))
2982 cexpr.var = curr->id;
2983 VEC_safe_push (ce_s, heap, *results, &cexpr);
2988 /* If we are going to take the address of this field then
2989 to be able to compute reachability correctly add at least
2990 the last field of the variable. */
2992 && VEC_length (ce_s, *results) == 0)
2994 curr = get_varinfo (cexpr.var);
2995 while (curr->next != NULL)
2997 cexpr.var = curr->id;
2998 VEC_safe_push (ce_s, heap, *results, &cexpr);
3001 /* Assert that we found *some* field there. The user couldn't be
3002 accessing *only* padding. */
3003 /* Still the user could access one past the end of an array
3004 embedded in a struct resulting in accessing *only* padding. */
3005 gcc_assert (VEC_length (ce_s, *results) >= 1
3006 || ref_contains_array_ref (orig_t));
3008 else if (bitmaxsize == 0)
3010 if (dump_file && (dump_flags & TDF_DETAILS))
3011 fprintf (dump_file, "Access to zero-sized part of variable,"
3015 if (dump_file && (dump_flags & TDF_DETAILS))
3016 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3018 else if (result->type == DEREF)
3020 /* If we do not know exactly where the access goes say so. Note
3021 that only for non-structure accesses we know that we access
3022 at most one subfiled of any variable. */
3024 || bitsize != bitmaxsize
3025 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t)))
3026 result->offset = UNKNOWN_OFFSET;
3028 result->offset = bitpos;
3030 else if (result->type == ADDRESSOF)
3032 /* We can end up here for component references on a
3033 VIEW_CONVERT_EXPR <>(&foobar). */
3034 result->type = SCALAR;
3035 result->var = anything_id;
3043 /* Dereference the constraint expression CONS, and return the result.
3044 DEREF (ADDRESSOF) = SCALAR
3045 DEREF (SCALAR) = DEREF
3046 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3047 This is needed so that we can handle dereferencing DEREF constraints. */
3050 do_deref (VEC (ce_s, heap) **constraints)
3052 struct constraint_expr *c;
3055 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3057 if (c->type == SCALAR)
3059 else if (c->type == ADDRESSOF)
3061 else if (c->type == DEREF)
3063 struct constraint_expr tmplhs;
3064 tmplhs = new_scalar_tmp_constraint_exp ("dereftmp");
3065 process_constraint (new_constraint (tmplhs, *c));
3066 c->var = tmplhs.var;
3073 static void get_constraint_for_1 (tree, VEC (ce_s, heap) **, bool);
3075 /* Given a tree T, return the constraint expression for taking the
3079 get_constraint_for_address_of (tree t, VEC (ce_s, heap) **results)
3081 struct constraint_expr *c;
3084 get_constraint_for_1 (t, results, true);
3086 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3088 if (c->type == DEREF)
3091 c->type = ADDRESSOF;
3095 /* Given a tree T, return the constraint expression for it. */
3098 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3100 struct constraint_expr temp;
3102 /* x = integer is all glommed to a single variable, which doesn't
3103 point to anything by itself. That is, of course, unless it is an
3104 integer constant being treated as a pointer, in which case, we
3105 will return that this is really the addressof anything. This
3106 happens below, since it will fall into the default case. The only
3107 case we know something about an integer treated like a pointer is
3108 when it is the NULL pointer, and then we just say it points to
3111 Do not do that if -fno-delete-null-pointer-checks though, because
3112 in that case *NULL does not fail, so it _should_ alias *anything.
3113 It is not worth adding a new option or renaming the existing one,
3114 since this case is relatively obscure. */
3115 if (flag_delete_null_pointer_checks
3116 && ((TREE_CODE (t) == INTEGER_CST
3117 && integer_zerop (t))
3118 /* The only valid CONSTRUCTORs in gimple with pointer typed
3119 elements are zero-initializer. */
3120 || TREE_CODE (t) == CONSTRUCTOR))
3122 temp.var = nothing_id;
3123 temp.type = ADDRESSOF;
3125 VEC_safe_push (ce_s, heap, *results, &temp);
3129 /* String constants are read-only. */
3130 if (TREE_CODE (t) == STRING_CST)
3132 temp.var = readonly_id;
3135 VEC_safe_push (ce_s, heap, *results, &temp);
3139 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3141 case tcc_expression:
3143 switch (TREE_CODE (t))
3146 get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3154 switch (TREE_CODE (t))
3158 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3163 case ARRAY_RANGE_REF:
3165 get_constraint_for_component_ref (t, results, address_p);
3167 case VIEW_CONVERT_EXPR:
3168 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3170 /* We are missing handling for TARGET_MEM_REF here. */
3175 case tcc_exceptional:
3177 switch (TREE_CODE (t))
3181 get_constraint_for_ssa_var (t, results, address_p);
3188 case tcc_declaration:
3190 get_constraint_for_ssa_var (t, results, address_p);
3196 /* The default fallback is a constraint from anything. */
3197 temp.type = ADDRESSOF;
3198 temp.var = anything_id;
3200 VEC_safe_push (ce_s, heap, *results, &temp);
3203 /* Given a gimple tree T, return the constraint expression vector for it. */
3206 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3208 gcc_assert (VEC_length (ce_s, *results) == 0);
3210 get_constraint_for_1 (t, results, false);
3214 /* Efficiently generates constraints from all entries in *RHSC to all
3215 entries in *LHSC. */
3218 process_all_all_constraints (VEC (ce_s, heap) *lhsc, VEC (ce_s, heap) *rhsc)
3220 struct constraint_expr *lhsp, *rhsp;
3223 if (VEC_length (ce_s, lhsc) <= 1
3224 || VEC_length (ce_s, rhsc) <= 1)
3226 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3227 for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); ++j)
3228 process_constraint (new_constraint (*lhsp, *rhsp));
3232 struct constraint_expr tmp;
3233 tmp = new_scalar_tmp_constraint_exp ("allalltmp");
3234 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
3235 process_constraint (new_constraint (tmp, *rhsp));
3236 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3237 process_constraint (new_constraint (*lhsp, tmp));
3241 /* Handle aggregate copies by expanding into copies of the respective
3242 fields of the structures. */
3245 do_structure_copy (tree lhsop, tree rhsop)
3247 struct constraint_expr *lhsp, *rhsp;
3248 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3251 get_constraint_for (lhsop, &lhsc);
3252 get_constraint_for (rhsop, &rhsc);
3253 lhsp = VEC_index (ce_s, lhsc, 0);
3254 rhsp = VEC_index (ce_s, rhsc, 0);
3255 if (lhsp->type == DEREF
3256 || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3257 || rhsp->type == DEREF)
3258 process_all_all_constraints (lhsc, rhsc);
3259 else if (lhsp->type == SCALAR
3260 && (rhsp->type == SCALAR
3261 || rhsp->type == ADDRESSOF))
3263 tree lhsbase, rhsbase;
3264 HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
3265 HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
3267 lhsbase = get_ref_base_and_extent (lhsop, &lhsoffset,
3268 &lhssize, &lhsmaxsize);
3269 rhsbase = get_ref_base_and_extent (rhsop, &rhsoffset,
3270 &rhssize, &rhsmaxsize);
3271 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp);)
3273 varinfo_t lhsv, rhsv;
3274 rhsp = VEC_index (ce_s, rhsc, k);
3275 lhsv = get_varinfo (lhsp->var);
3276 rhsv = get_varinfo (rhsp->var);
3277 if (lhsv->may_have_pointers
3278 && ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3279 rhsv->offset + lhsoffset, rhsv->size))
3280 process_constraint (new_constraint (*lhsp, *rhsp));
3281 if (lhsv->offset + rhsoffset + lhsv->size
3282 > rhsv->offset + lhsoffset + rhsv->size)
3285 if (k >= VEC_length (ce_s, rhsc))
3295 VEC_free (ce_s, heap, lhsc);
3296 VEC_free (ce_s, heap, rhsc);
3299 /* Create a constraint ID = OP. */
3302 make_constraint_to (unsigned id, tree op)
3304 VEC(ce_s, heap) *rhsc = NULL;
3305 struct constraint_expr *c;
3306 struct constraint_expr includes;
3310 includes.offset = 0;
3311 includes.type = SCALAR;
3313 get_constraint_for (op, &rhsc);
3314 for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3315 process_constraint (new_constraint (includes, *c));
3316 VEC_free (ce_s, heap, rhsc);
3319 /* Create a constraint ID = &FROM. */
3322 make_constraint_from (varinfo_t vi, int from)
3324 struct constraint_expr lhs, rhs;
3332 rhs.type = ADDRESSOF;
3333 process_constraint (new_constraint (lhs, rhs));
3336 /* Create a constraint ID = FROM. */
3339 make_copy_constraint (varinfo_t vi, int from)
3341 struct constraint_expr lhs, rhs;
3350 process_constraint (new_constraint (lhs, rhs));
3353 /* Make constraints necessary to make OP escape. */
3356 make_escape_constraint (tree op)
3358 make_constraint_to (escaped_id, op);
3361 /* Create a new artificial heap variable with NAME and make a
3362 constraint from it to LHS. Return the created variable. */
3365 make_constraint_from_heapvar (varinfo_t lhs, const char *name)
3368 tree heapvar = heapvar_lookup (lhs->decl);
3370 if (heapvar == NULL_TREE)
3373 heapvar = create_tmp_var_raw (ptr_type_node, name);
3374 DECL_EXTERNAL (heapvar) = 1;
3376 heapvar_insert (lhs->decl, heapvar);
3378 ann = get_var_ann (heapvar);
3379 ann->is_heapvar = 1;
3382 /* For global vars we need to add a heapvar to the list of referenced
3383 vars of a different function than it was created for originally. */
3384 if (gimple_referenced_vars (cfun))
3385 add_referenced_var (heapvar);
3387 vi = new_var_info (heapvar, name);
3388 vi->is_artificial_var = true;
3389 vi->is_heap_var = true;
3390 vi->is_unknown_size_var = true;
3394 vi->is_full_var = true;
3395 insert_vi_for_tree (heapvar, vi);
3397 make_constraint_from (lhs, vi->id);
3402 /* Create a new artificial heap variable with NAME and make a
3403 constraint from it to LHS. Set flags according to a tag used
3404 for tracking restrict pointers. */
3407 make_constraint_from_restrict (varinfo_t lhs, const char *name)
3410 vi = make_constraint_from_heapvar (lhs, name);
3411 vi->is_restrict_var = 1;
3412 vi->is_global_var = 0;
3413 vi->is_special_var = 1;
3414 vi->may_have_pointers = 0;
3417 /* For non-IPA mode, generate constraints necessary for a call on the
3421 handle_rhs_call (gimple stmt, VEC(ce_s, heap) **results)
3423 struct constraint_expr rhsc;
3426 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3428 tree arg = gimple_call_arg (stmt, i);
3430 /* Find those pointers being passed, and make sure they end up
3431 pointing to anything. */
3432 if (could_have_pointers (arg))
3433 make_escape_constraint (arg);
3436 /* The static chain escapes as well. */
3437 if (gimple_call_chain (stmt))
3438 make_escape_constraint (gimple_call_chain (stmt));
3440 /* And if we applied NRV the address of the return slot escapes as well. */
3441 if (gimple_call_return_slot_opt_p (stmt)
3442 && gimple_call_lhs (stmt) != NULL_TREE
3443 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
3445 VEC(ce_s, heap) *tmpc = NULL;
3446 struct constraint_expr lhsc, *c;
3447 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
3448 lhsc.var = escaped_id;
3451 for (i = 0; VEC_iterate (ce_s, tmpc, i, c); ++i)
3452 process_constraint (new_constraint (lhsc, *c));
3453 VEC_free(ce_s, heap, tmpc);
3456 /* Regular functions return nonlocal memory. */
3457 rhsc.var = nonlocal_id;
3460 VEC_safe_push (ce_s, heap, *results, &rhsc);
3463 /* For non-IPA mode, generate constraints necessary for a call
3464 that returns a pointer and assigns it to LHS. This simply makes
3465 the LHS point to global and escaped variables. */
3468 handle_lhs_call (tree lhs, int flags, VEC(ce_s, heap) *rhsc)
3470 VEC(ce_s, heap) *lhsc = NULL;
3472 get_constraint_for (lhs, &lhsc);
3474 if (flags & ECF_MALLOC)
3477 vi = make_constraint_from_heapvar (get_vi_for_tree (lhs), "HEAP");
3478 /* We delay marking allocated storage global until we know if
3480 DECL_EXTERNAL (vi->decl) = 0;
3481 vi->is_global_var = 0;
3483 else if (VEC_length (ce_s, rhsc) > 0)
3485 /* If the store is to a global decl make sure to
3486 add proper escape constraints. */
3487 lhs = get_base_address (lhs);
3490 && is_global_var (lhs))
3492 struct constraint_expr tmpc;
3493 tmpc.var = escaped_id;
3496 VEC_safe_push (ce_s, heap, lhsc, &tmpc);
3498 process_all_all_constraints (lhsc, rhsc);
3500 VEC_free (ce_s, heap, lhsc);
3503 /* For non-IPA mode, generate constraints necessary for a call of a
3504 const function that returns a pointer in the statement STMT. */
3507 handle_const_call (gimple stmt, VEC(ce_s, heap) **results)
3509 struct constraint_expr rhsc;
3512 /* Treat nested const functions the same as pure functions as far
3513 as the static chain is concerned. */
3514 if (gimple_call_chain (stmt))
3516 make_constraint_to (callused_id, gimple_call_chain (stmt));
3517 rhsc.var = callused_id;
3520 VEC_safe_push (ce_s, heap, *results, &rhsc);
3523 /* May return arguments. */
3524 for (k = 0; k < gimple_call_num_args (stmt); ++k)
3526 tree arg = gimple_call_arg (stmt, k);
3528 if (could_have_pointers (arg))
3530 VEC(ce_s, heap) *argc = NULL;
3532 struct constraint_expr *argp;
3533 get_constraint_for (arg, &argc);
3534 for (i = 0; VEC_iterate (ce_s, argc, i, argp); ++i)
3535 VEC_safe_push (ce_s, heap, *results, argp);
3536 VEC_free(ce_s, heap, argc);
3540 /* May return addresses of globals. */
3541 rhsc.var = nonlocal_id;
3543 rhsc.type = ADDRESSOF;
3544 VEC_safe_push (ce_s, heap, *results, &rhsc);
3547 /* For non-IPA mode, generate constraints necessary for a call to a
3548 pure function in statement STMT. */
3551 handle_pure_call (gimple stmt, VEC(ce_s, heap) **results)
3553 struct constraint_expr rhsc;
3555 bool need_callused = false;
3557 /* Memory reached from pointer arguments is call-used. */
3558 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3560 tree arg = gimple_call_arg (stmt, i);
3562 if (could_have_pointers (arg))
3564 make_constraint_to (callused_id, arg);
3565 need_callused = true;
3569 /* The static chain is used as well. */
3570 if (gimple_call_chain (stmt))
3572 make_constraint_to (callused_id, gimple_call_chain (stmt));
3573 need_callused = true;
3576 /* Pure functions may return callused and nonlocal memory. */
3579 rhsc.var = callused_id;
3582 VEC_safe_push (ce_s, heap, *results, &rhsc);
3584 rhsc.var = nonlocal_id;
3587 VEC_safe_push (ce_s, heap, *results, &rhsc);
3590 /* Walk statement T setting up aliasing constraints according to the
3591 references found in T. This function is the main part of the
3592 constraint builder. AI points to auxiliary alias information used
3593 when building alias sets and computing alias grouping heuristics. */
3596 find_func_aliases (gimple origt)
3599 VEC(ce_s, heap) *lhsc = NULL;
3600 VEC(ce_s, heap) *rhsc = NULL;
3601 struct constraint_expr *c;
3603 /* Now build constraints expressions. */
3604 if (gimple_code (t) == GIMPLE_PHI)
3606 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (gimple_phi_result (t))));
3608 /* Only care about pointers and structures containing
3610 if (could_have_pointers (gimple_phi_result (t)))
3615 /* For a phi node, assign all the arguments to
3617 get_constraint_for (gimple_phi_result (t), &lhsc);
3618 for (i = 0; i < gimple_phi_num_args (t); i++)
3621 tree strippedrhs = PHI_ARG_DEF (t, i);
3623 STRIP_NOPS (strippedrhs);
3624 rhstype = TREE_TYPE (strippedrhs);
3625 get_constraint_for (gimple_phi_arg_def (t, i), &rhsc);
3627 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3629 struct constraint_expr *c2;
3630 while (VEC_length (ce_s, rhsc) > 0)
3632 c2 = VEC_last (ce_s, rhsc);
3633 process_constraint (new_constraint (*c, *c2));
3634 VEC_pop (ce_s, rhsc);
3640 /* In IPA mode, we need to generate constraints to pass call
3641 arguments through their calls. There are two cases,
3642 either a GIMPLE_CALL returning a value, or just a plain
3643 GIMPLE_CALL when we are not.
3645 In non-ipa mode, we need to generate constraints for each
3646 pointer passed by address. */
3647 else if (is_gimple_call (t))
3650 if ((fndecl = gimple_call_fndecl (t)) != NULL_TREE
3651 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
3652 /* ??? All builtins that are handled here need to be handled
3653 in the alias-oracle query functions explicitly! */
3654 switch (DECL_FUNCTION_CODE (fndecl))
3656 /* All the following functions return a pointer to the same object
3657 as their first argument points to. The functions do not add
3658 to the ESCAPED solution. The functions make the first argument
3659 pointed to memory point to what the second argument pointed to
3660 memory points to. */
3661 case BUILT_IN_STRCPY:
3662 case BUILT_IN_STRNCPY:
3663 case BUILT_IN_BCOPY:
3664 case BUILT_IN_MEMCPY:
3665 case BUILT_IN_MEMMOVE:
3666 case BUILT_IN_MEMPCPY:
3667 case BUILT_IN_STPCPY:
3668 case BUILT_IN_STPNCPY:
3669 case BUILT_IN_STRCAT:
3670 case BUILT_IN_STRNCAT:
3672 tree res = gimple_call_lhs (t);
3673 tree dest = gimple_call_arg (t, 0);
3674 tree src = gimple_call_arg (t, 1);
3675 if (res != NULL_TREE)
3677 get_constraint_for (res, &lhsc);
3678 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
3679 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
3680 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY)
3681 get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
3683 get_constraint_for (dest, &rhsc);
3684 process_all_all_constraints (lhsc, rhsc);
3685 VEC_free (ce_s, heap, lhsc);
3686 VEC_free (ce_s, heap, rhsc);
3688 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
3689 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
3692 process_all_all_constraints (lhsc, rhsc);
3693 VEC_free (ce_s, heap, lhsc);
3694 VEC_free (ce_s, heap, rhsc);
3697 case BUILT_IN_MEMSET:
3699 tree res = gimple_call_lhs (t);
3700 tree dest = gimple_call_arg (t, 0);
3703 struct constraint_expr ac;
3704 if (res != NULL_TREE)
3706 get_constraint_for (res, &lhsc);
3707 get_constraint_for (dest, &rhsc);
3708 process_all_all_constraints (lhsc, rhsc);
3709 VEC_free (ce_s, heap, lhsc);
3710 VEC_free (ce_s, heap, rhsc);
3712 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
3714 if (flag_delete_null_pointer_checks
3715 && integer_zerop (gimple_call_arg (t, 1)))
3717 ac.type = ADDRESSOF;
3718 ac.var = nothing_id;
3723 ac.var = integer_id;
3726 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3727 process_constraint (new_constraint (*lhsp, ac));
3728 VEC_free (ce_s, heap, lhsc);
3731 /* All the following functions do not return pointers, do not
3732 modify the points-to sets of memory reachable from their
3733 arguments and do not add to the ESCAPED solution. */
3734 case BUILT_IN_SINCOS:
3735 case BUILT_IN_SINCOSF:
3736 case BUILT_IN_SINCOSL:
3737 case BUILT_IN_FREXP:
3738 case BUILT_IN_FREXPF:
3739 case BUILT_IN_FREXPL:
3740 case BUILT_IN_GAMMA_R:
3741 case BUILT_IN_GAMMAF_R:
3742 case BUILT_IN_GAMMAL_R:
3743 case BUILT_IN_LGAMMA_R:
3744 case BUILT_IN_LGAMMAF_R:
3745 case BUILT_IN_LGAMMAL_R:
3747 case BUILT_IN_MODFF:
3748 case BUILT_IN_MODFL:
3749 case BUILT_IN_REMQUO:
3750 case BUILT_IN_REMQUOF:
3751 case BUILT_IN_REMQUOL:
3754 /* printf-style functions may have hooks to set pointers to
3755 point to somewhere into the generated string. Leave them
3756 for a later excercise... */
3758 /* Fallthru to general call handling. */;
3762 VEC(ce_s, heap) *rhsc = NULL;
3763 int flags = gimple_call_flags (t);
3765 /* Const functions can return their arguments and addresses
3766 of global memory but not of escaped memory. */
3767 if (flags & (ECF_CONST|ECF_NOVOPS))
3769 if (gimple_call_lhs (t)
3770 && could_have_pointers (gimple_call_lhs (t)))
3771 handle_const_call (t, &rhsc);
3773 /* Pure functions can return addresses in and of memory
3774 reachable from their arguments, but they are not an escape
3775 point for reachable memory of their arguments. */
3776 else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE))
3777 handle_pure_call (t, &rhsc);
3779 handle_rhs_call (t, &rhsc);
3780 if (gimple_call_lhs (t)
3781 && could_have_pointers (gimple_call_lhs (t)))
3782 handle_lhs_call (gimple_call_lhs (t), flags, rhsc);
3783 VEC_free (ce_s, heap, rhsc);
3793 lhsop = gimple_call_lhs (t);
3794 decl = gimple_call_fndecl (t);
3796 /* If we can directly resolve the function being called, do so.
3797 Otherwise, it must be some sort of indirect expression that
3798 we should still be able to handle. */
3800 fi = get_vi_for_tree (decl);
3803 decl = gimple_call_fn (t);
3804 fi = get_vi_for_tree (decl);
3807 /* Assign all the passed arguments to the appropriate incoming
3808 parameters of the function. */
3809 for (j = 0; j < gimple_call_num_args (t); j++)
3811 struct constraint_expr lhs ;
3812 struct constraint_expr *rhsp;
3813 tree arg = gimple_call_arg (t, j);
3815 get_constraint_for (arg, &rhsc);
3816 if (TREE_CODE (decl) != FUNCTION_DECL)
3825 lhs.var = first_vi_for_offset (fi, i)->id;
3828 while (VEC_length (ce_s, rhsc) != 0)
3830 rhsp = VEC_last (ce_s, rhsc);
3831 process_constraint (new_constraint (lhs, *rhsp));
3832 VEC_pop (ce_s, rhsc);
3837 /* If we are returning a value, assign it to the result. */
3840 struct constraint_expr rhs;
3841 struct constraint_expr *lhsp;
3844 get_constraint_for (lhsop, &lhsc);
3845 if (TREE_CODE (decl) != FUNCTION_DECL)
3854 rhs.var = first_vi_for_offset (fi, i)->id;
3857 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3858 process_constraint (new_constraint (*lhsp, rhs));
3862 /* Otherwise, just a regular assignment statement. Only care about
3863 operations with pointer result, others are dealt with as escape
3864 points if they have pointer operands. */
3865 else if (is_gimple_assign (t)
3866 && could_have_pointers (gimple_assign_lhs (t)))
3868 /* Otherwise, just a regular assignment statement. */
3869 tree lhsop = gimple_assign_lhs (t);
3870 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
3872 if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
3873 do_structure_copy (lhsop, rhsop);
3876 struct constraint_expr temp;
3877 get_constraint_for (lhsop, &lhsc);
3879 if (gimple_assign_rhs_code (t) == POINTER_PLUS_EXPR)
3880 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
3881 gimple_assign_rhs2 (t), &rhsc);
3882 else if ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
3883 && !(POINTER_TYPE_P (gimple_expr_type (t))
3884 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
3885 || gimple_assign_single_p (t))
3886 get_constraint_for (rhsop, &rhsc);
3889 temp.type = ADDRESSOF;
3890 temp.var = anything_id;
3892 VEC_safe_push (ce_s, heap, rhsc, &temp);
3894 process_all_all_constraints (lhsc, rhsc);
3896 /* If there is a store to a global variable the rhs escapes. */
3897 if ((lhsop = get_base_address (lhsop)) != NULL_TREE
3899 && is_global_var (lhsop))
3900 make_escape_constraint (rhsop);
3901 /* If this is a conversion of a non-restrict pointer to a
3902 restrict pointer track it with a new heapvar. */
3903 else if (gimple_assign_cast_p (t)
3904 && POINTER_TYPE_P (TREE_TYPE (rhsop))
3905 && POINTER_TYPE_P (TREE_TYPE (lhsop))
3906 && !TYPE_RESTRICT (TREE_TYPE (rhsop))
3907 && TYPE_RESTRICT (TREE_TYPE (lhsop)))
3908 make_constraint_from_restrict (get_vi_for_tree (lhsop),
3911 /* For conversions of pointers to non-pointers the pointer escapes. */
3912 else if (gimple_assign_cast_p (t)
3913 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (t)))
3914 && !POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (t))))
3916 make_escape_constraint (gimple_assign_rhs1 (t));
3918 /* Handle escapes through return. */
3919 else if (gimple_code (t) == GIMPLE_RETURN
3920 && gimple_return_retval (t) != NULL_TREE
3921 && could_have_pointers (gimple_return_retval (t)))
3923 make_escape_constraint (gimple_return_retval (t));
3925 /* Handle asms conservatively by adding escape constraints to everything. */
3926 else if (gimple_code (t) == GIMPLE_ASM)
3928 unsigned i, noutputs;
3929 const char **oconstraints;
3930 const char *constraint;
3931 bool allows_mem, allows_reg, is_inout;
3933 noutputs = gimple_asm_noutputs (t);
3934 oconstraints = XALLOCAVEC (const char *, noutputs);
3936 for (i = 0; i < noutputs; ++i)
3938 tree link = gimple_asm_output_op (t, i);
3939 tree op = TREE_VALUE (link);
3941 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
3942 oconstraints[i] = constraint;
3943 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
3944 &allows_reg, &is_inout);
3946 /* A memory constraint makes the address of the operand escape. */
3947 if (!allows_reg && allows_mem)
3948 make_escape_constraint (build_fold_addr_expr (op));
3950 /* The asm may read global memory, so outputs may point to
3951 any global memory. */
3952 if (op && could_have_pointers (op))
3954 VEC(ce_s, heap) *lhsc = NULL;
3955 struct constraint_expr rhsc, *lhsp;
3957 get_constraint_for (op, &lhsc);
3958 rhsc.var = nonlocal_id;
3961 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3962 process_constraint (new_constraint (*lhsp, rhsc));
3963 VEC_free (ce_s, heap, lhsc);
3966 for (i = 0; i < gimple_asm_ninputs (t); ++i)
3968 tree link = gimple_asm_input_op (t, i);
3969 tree op = TREE_VALUE (link);
3971 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
3973 parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
3974 &allows_mem, &allows_reg);
3976 /* A memory constraint makes the address of the operand escape. */
3977 if (!allows_reg && allows_mem)
3978 make_escape_constraint (build_fold_addr_expr (op));
3979 /* Strictly we'd only need the constraint to ESCAPED if
3980 the asm clobbers memory, otherwise using CALLUSED
3982 else if (op && could_have_pointers (op))
3983 make_escape_constraint (op);
3987 VEC_free (ce_s, heap, rhsc);
3988 VEC_free (ce_s, heap, lhsc);
3992 /* Find the first varinfo in the same variable as START that overlaps with
3993 OFFSET. Return NULL if we can't find one. */
3996 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3998 /* If the offset is outside of the variable, bail out. */
3999 if (offset >= start->fullsize)
4002 /* If we cannot reach offset from start, lookup the first field
4003 and start from there. */
4004 if (start->offset > offset)
4005 start = lookup_vi_for_tree (start->decl);
4009 /* We may not find a variable in the field list with the actual
4010 offset when when we have glommed a structure to a variable.
4011 In that case, however, offset should still be within the size
4013 if (offset >= start->offset
4014 && offset < (start->offset + start->size))
4023 /* Find the first varinfo in the same variable as START that overlaps with
4024 OFFSET. If there is no such varinfo the varinfo directly preceding
4025 OFFSET is returned. */
4028 first_or_preceding_vi_for_offset (varinfo_t start,
4029 unsigned HOST_WIDE_INT offset)
4031 /* If we cannot reach offset from start, lookup the first field
4032 and start from there. */
4033 if (start->offset > offset)
4034 start = lookup_vi_for_tree (start->decl);
4036 /* We may not find a variable in the field list with the actual
4037 offset when when we have glommed a structure to a variable.
4038 In that case, however, offset should still be within the size
4040 If we got beyond the offset we look for return the field
4041 directly preceding offset which may be the last field. */
4043 && offset >= start->offset
4044 && !(offset < (start->offset + start->size)))
4045 start = start->next;
4051 /* Insert the varinfo FIELD into the field list for BASE, at the front
4055 insert_into_field_list (varinfo_t base, varinfo_t field)
4057 varinfo_t prev = base;
4058 varinfo_t curr = base->next;
4064 /* Insert the varinfo FIELD into the field list for BASE, ordered by
4068 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
4070 varinfo_t prev = base;
4071 varinfo_t curr = base->next;
4082 if (field->offset <= curr->offset)
4087 field->next = prev->next;
4092 /* This structure is used during pushing fields onto the fieldstack
4093 to track the offset of the field, since bitpos_of_field gives it
4094 relative to its immediate containing type, and we want it relative
4095 to the ultimate containing object. */
4099 /* Offset from the base of the base containing object to this field. */
4100 HOST_WIDE_INT offset;
4102 /* Size, in bits, of the field. */
4103 unsigned HOST_WIDE_INT size;
4105 unsigned has_unknown_size : 1;
4107 unsigned may_have_pointers : 1;
4109 unsigned only_restrict_pointers : 1;
4111 typedef struct fieldoff fieldoff_s;
4113 DEF_VEC_O(fieldoff_s);
4114 DEF_VEC_ALLOC_O(fieldoff_s,heap);
4116 /* qsort comparison function for two fieldoff's PA and PB */
4119 fieldoff_compare (const void *pa, const void *pb)
4121 const fieldoff_s *foa = (const fieldoff_s *)pa;
4122 const fieldoff_s *fob = (const fieldoff_s *)pb;
4123 unsigned HOST_WIDE_INT foasize, fobsize;
4125 if (foa->offset < fob->offset)
4127 else if (foa->offset > fob->offset)
4130 foasize = foa->size;
4131 fobsize = fob->size;
4132 if (foasize < fobsize)
4134 else if (foasize > fobsize)
4139 /* Sort a fieldstack according to the field offset and sizes. */
4141 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
4143 qsort (VEC_address (fieldoff_s, fieldstack),
4144 VEC_length (fieldoff_s, fieldstack),
4145 sizeof (fieldoff_s),
4149 /* Return true if V is a tree that we can have subvars for.
4150 Normally, this is any aggregate type. Also complex
4151 types which are not gimple registers can have subvars. */
4154 var_can_have_subvars (const_tree v)
4156 /* Volatile variables should never have subvars. */
4157 if (TREE_THIS_VOLATILE (v))
4160 /* Non decls or memory tags can never have subvars. */
4164 /* Aggregates without overlapping fields can have subvars. */
4165 if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
4171 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4172 the fields of TYPE onto fieldstack, recording their offsets along
4175 OFFSET is used to keep track of the offset in this entire
4176 structure, rather than just the immediately containing structure.
4177 Returns the number of fields pushed. */
4180 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
4181 HOST_WIDE_INT offset)
4186 if (TREE_CODE (type) != RECORD_TYPE)
4189 /* If the vector of fields is growing too big, bail out early.
4190 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4192 if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
4195 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
4196 if (TREE_CODE (field) == FIELD_DECL)
4200 HOST_WIDE_INT foff = bitpos_of_field (field);
4202 if (!var_can_have_subvars (field)
4203 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
4204 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
4206 else if (!(pushed = push_fields_onto_fieldstack
4207 (TREE_TYPE (field), fieldstack, offset + foff))
4208 && (DECL_SIZE (field)
4209 && !integer_zerop (DECL_SIZE (field))))
4210 /* Empty structures may have actual size, like in C++. So
4211 see if we didn't push any subfields and the size is
4212 nonzero, push the field onto the stack. */
4217 fieldoff_s *pair = NULL;
4218 bool has_unknown_size = false;
4220 if (!VEC_empty (fieldoff_s, *fieldstack))
4221 pair = VEC_last (fieldoff_s, *fieldstack);
4223 if (!DECL_SIZE (field)
4224 || !host_integerp (DECL_SIZE (field), 1))
4225 has_unknown_size = true;
4227 /* If adjacent fields do not contain pointers merge them. */
4229 && !pair->may_have_pointers
4230 && !could_have_pointers (field)
4231 && !pair->has_unknown_size
4232 && !has_unknown_size
4233 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
4235 pair = VEC_last (fieldoff_s, *fieldstack);
4236 pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
4240 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
4241 pair->offset = offset + foff;
4242 pair->has_unknown_size = has_unknown_size;
4243 if (!has_unknown_size)
4244 pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
4247 pair->may_have_pointers = could_have_pointers (field);
4248 pair->only_restrict_pointers
4249 = (!has_unknown_size
4250 && POINTER_TYPE_P (TREE_TYPE (field))
4251 && TYPE_RESTRICT (TREE_TYPE (field)));
4262 /* Count the number of arguments DECL has, and set IS_VARARGS to true
4263 if it is a varargs function. */
4266 count_num_arguments (tree decl, bool *is_varargs)
4271 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
4275 if (TREE_VALUE (t) == void_type_node)
4285 /* Creation function node for DECL, using NAME, and return the index
4286 of the variable we've created for the function. */
4289 create_function_info_for (tree decl, const char *name)
4294 bool is_varargs = false;
4296 /* Create the variable info. */
4298 vi = new_var_info (decl, name);
4301 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
4302 insert_vi_for_tree (vi->decl, vi);
4306 /* If it's varargs, we don't know how many arguments it has, so we
4312 vi->is_unknown_size_var = true;
4316 arg = DECL_ARGUMENTS (decl);
4318 /* Set up variables for each argument. */
4319 for (i = 1; i < vi->fullsize; i++)
4322 const char *newname;
4324 tree argdecl = decl;
4329 asprintf (&tempname, "%s.arg%d", name, i-1);
4330 newname = ggc_strdup (tempname);
4333 argvi = new_var_info (argdecl, newname);
4336 argvi->is_full_var = true;
4337 argvi->fullsize = vi->fullsize;
4338 insert_into_field_list_sorted (vi, argvi);
4339 stats.total_vars ++;
4342 insert_vi_for_tree (arg, argvi);
4343 arg = TREE_CHAIN (arg);
4347 /* Create a variable for the return var. */
4348 if (DECL_RESULT (decl) != NULL
4349 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
4352 const char *newname;
4354 tree resultdecl = decl;
4358 if (DECL_RESULT (decl))
4359 resultdecl = DECL_RESULT (decl);
4361 asprintf (&tempname, "%s.result", name);
4362 newname = ggc_strdup (tempname);
4365 resultvi = new_var_info (resultdecl, newname);
4366 resultvi->offset = i;
4368 resultvi->fullsize = vi->fullsize;
4369 resultvi->is_full_var = true;
4370 insert_into_field_list_sorted (vi, resultvi);
4371 stats.total_vars ++;
4372 if (DECL_RESULT (decl))
4373 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
4380 /* Return true if FIELDSTACK contains fields that overlap.
4381 FIELDSTACK is assumed to be sorted by offset. */
4384 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
4386 fieldoff_s *fo = NULL;
4388 HOST_WIDE_INT lastoffset = -1;
4390 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4392 if (fo->offset == lastoffset)
4394 lastoffset = fo->offset;
4399 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4400 This will also create any varinfo structures necessary for fields
4404 create_variable_info_for (tree decl, const char *name)
4407 tree decl_type = TREE_TYPE (decl);
4408 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
4409 VEC (fieldoff_s,heap) *fieldstack = NULL;
4411 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4412 return create_function_info_for (decl, name);
4414 if (var_can_have_subvars (decl) && use_field_sensitive)
4415 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
4417 /* If the variable doesn't have subvars, we may end up needing to
4418 sort the field list and create fake variables for all the
4420 vi = new_var_info (decl, name);
4422 vi->may_have_pointers = could_have_pointers (decl);
4424 || !host_integerp (declsize, 1))
4426 vi->is_unknown_size_var = true;
4432 vi->fullsize = TREE_INT_CST_LOW (declsize);
4433 vi->size = vi->fullsize;
4436 insert_vi_for_tree (vi->decl, vi);
4437 if (vi->is_global_var
4438 && (!flag_whole_program || !in_ipa_mode)
4439 && vi->may_have_pointers)
4441 if (POINTER_TYPE_P (TREE_TYPE (decl))
4442 && TYPE_RESTRICT (TREE_TYPE (decl)))
4443 make_constraint_from_restrict (vi, "GLOBAL_RESTRICT");
4444 make_copy_constraint (vi, nonlocal_id);
4448 if (use_field_sensitive
4449 && !vi->is_unknown_size_var
4450 && var_can_have_subvars (decl)
4451 && VEC_length (fieldoff_s, fieldstack) > 1
4452 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4454 fieldoff_s *fo = NULL;
4455 bool notokay = false;
4458 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4460 if (fo->has_unknown_size
4468 /* We can't sort them if we have a field with a variable sized type,
4469 which will make notokay = true. In that case, we are going to return
4470 without creating varinfos for the fields anyway, so sorting them is a
4474 sort_fieldstack (fieldstack);
4475 /* Due to some C++ FE issues, like PR 22488, we might end up
4476 what appear to be overlapping fields even though they,
4477 in reality, do not overlap. Until the C++ FE is fixed,
4478 we will simply disable field-sensitivity for these cases. */
4479 notokay = check_for_overlaps (fieldstack);
4483 if (VEC_length (fieldoff_s, fieldstack) != 0)
4484 fo = VEC_index (fieldoff_s, fieldstack, 0);
4486 if (fo == NULL || notokay)
4488 vi->is_unknown_size_var = 1;
4491 vi->is_full_var = true;
4492 VEC_free (fieldoff_s, heap, fieldstack);
4496 vi->size = fo->size;
4497 vi->offset = fo->offset;
4498 vi->may_have_pointers = fo->may_have_pointers;
4499 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4500 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4504 const char *newname = "NULL";
4509 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
4510 "+" HOST_WIDE_INT_PRINT_DEC,
4511 vi->name, fo->offset, fo->size);
4512 newname = ggc_strdup (tempname);
4515 newvi = new_var_info (decl, newname);
4516 newvi->offset = fo->offset;
4517 newvi->size = fo->size;
4518 newvi->fullsize = vi->fullsize;
4519 newvi->may_have_pointers = fo->may_have_pointers;
4520 insert_into_field_list (vi, newvi);
4521 if (newvi->is_global_var
4522 && (!flag_whole_program || !in_ipa_mode)
4523 && newvi->may_have_pointers)
4525 if (fo->only_restrict_pointers)
4526 make_constraint_from_restrict (newvi, "GLOBAL_RESTRICT");
4527 make_copy_constraint (newvi, nonlocal_id);
4534 vi->is_full_var = true;
4536 VEC_free (fieldoff_s, heap, fieldstack);
4541 /* Print out the points-to solution for VAR to FILE. */
4544 dump_solution_for_var (FILE *file, unsigned int var)
4546 varinfo_t vi = get_varinfo (var);
4550 if (find (var) != var)
4552 varinfo_t vipt = get_varinfo (find (var));
4553 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4557 fprintf (file, "%s = { ", vi->name);
4558 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4560 fprintf (file, "%s ", get_varinfo (i)->name);
4562 fprintf (file, "}\n");
4566 /* Print the points-to solution for VAR to stdout. */
4569 debug_solution_for_var (unsigned int var)
4571 dump_solution_for_var (stdout, var);
4574 /* Create varinfo structures for all of the variables in the
4575 function for intraprocedural mode. */
4578 intra_create_variable_infos (void)
4582 /* For each incoming pointer argument arg, create the constraint ARG
4583 = NONLOCAL or a dummy variable if flag_argument_noalias is set. */
4584 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4588 if (!could_have_pointers (t))
4591 /* If flag_argument_noalias is set, then function pointer
4592 arguments are guaranteed not to point to each other. In that
4593 case, create an artificial variable PARM_NOALIAS and the
4594 constraint ARG = &PARM_NOALIAS. */
4595 if (POINTER_TYPE_P (TREE_TYPE (t)) && flag_argument_noalias > 0)
4600 vi = make_constraint_from_heapvar (get_vi_for_tree (t),
4602 ann = get_var_ann (vi->decl);
4603 if (flag_argument_noalias == 1)
4605 ann->noalias_state = NO_ALIAS;
4606 make_copy_constraint (vi, nonlocal_id);
4608 else if (flag_argument_noalias == 2)
4610 ann->noalias_state = NO_ALIAS_GLOBAL;
4611 make_constraint_from (vi, vi->id);
4613 else if (flag_argument_noalias == 3)
4615 ann->noalias_state = NO_ALIAS_ANYTHING;
4616 make_constraint_from (vi, vi->id);
4623 varinfo_t arg_vi = get_vi_for_tree (t);
4625 for (p = arg_vi; p; p = p->next)
4626 make_constraint_from (p, nonlocal_id);
4628 if (POINTER_TYPE_P (TREE_TYPE (t))
4629 && TYPE_RESTRICT (TREE_TYPE (t)))
4630 make_constraint_from_restrict (get_vi_for_tree (t), "PARM_RESTRICT");
4633 /* Add a constraint for a result decl that is passed by reference. */
4634 if (DECL_RESULT (cfun->decl)
4635 && DECL_BY_REFERENCE (DECL_RESULT (cfun->decl)))
4637 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
4639 for (p = result_vi; p; p = p->next)
4640 make_constraint_from (p, nonlocal_id);
4643 /* Add a constraint for the incoming static chain parameter. */
4644 if (cfun->static_chain_decl != NULL_TREE)
4646 varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
4648 for (p = chain_vi; p; p = p->next)
4649 make_constraint_from (p, nonlocal_id);
4653 /* Structure used to put solution bitmaps in a hashtable so they can
4654 be shared among variables with the same points-to set. */
4656 typedef struct shared_bitmap_info
4660 } *shared_bitmap_info_t;
4661 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
4663 static htab_t shared_bitmap_table;
4665 /* Hash function for a shared_bitmap_info_t */
4668 shared_bitmap_hash (const void *p)
4670 const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
4671 return bi->hashcode;
4674 /* Equality function for two shared_bitmap_info_t's. */
4677 shared_bitmap_eq (const void *p1, const void *p2)
4679 const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
4680 const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
4681 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
4684 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4685 existing instance if there is one, NULL otherwise. */
4688 shared_bitmap_lookup (bitmap pt_vars)
4691 struct shared_bitmap_info sbi;
4693 sbi.pt_vars = pt_vars;
4694 sbi.hashcode = bitmap_hash (pt_vars);
4696 slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
4697 sbi.hashcode, NO_INSERT);
4701 return ((shared_bitmap_info_t) *slot)->pt_vars;
4705 /* Add a bitmap to the shared bitmap hashtable. */
4708 shared_bitmap_add (bitmap pt_vars)
4711 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
4713 sbi->pt_vars = pt_vars;
4714 sbi->hashcode = bitmap_hash (pt_vars);
4716 slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
4717 sbi->hashcode, INSERT);
4718 gcc_assert (!*slot);
4719 *slot = (void *) sbi;
4723 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
4726 set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt)
4731 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4733 varinfo_t vi = get_varinfo (i);
4735 /* The only artificial variables that are allowed in a may-alias
4736 set are heap variables. */
4737 if (vi->is_artificial_var && !vi->is_heap_var)
4740 if (TREE_CODE (vi->decl) == VAR_DECL
4741 || TREE_CODE (vi->decl) == PARM_DECL
4742 || TREE_CODE (vi->decl) == RESULT_DECL)
4744 /* Add the decl to the points-to set. Note that the points-to
4745 set contains global variables. */
4746 bitmap_set_bit (into, DECL_UID (vi->decl));
4747 if (vi->is_global_var)
4748 pt->vars_contains_global = true;
4754 static bool have_alias_info = false;
4756 /* Compute the points-to solution *PT for the variable VI. */
4759 find_what_var_points_to (varinfo_t vi, struct pt_solution *pt)
4763 bitmap finished_solution;
4766 memset (pt, 0, sizeof (struct pt_solution));
4768 /* This variable may have been collapsed, let's get the real
4770 vi = get_varinfo (find (vi->id));
4772 /* Translate artificial variables into SSA_NAME_PTR_INFO
4774 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4776 varinfo_t vi = get_varinfo (i);
4778 if (vi->is_artificial_var)
4780 if (vi->id == nothing_id)
4782 else if (vi->id == escaped_id)
4784 else if (vi->id == callused_id)
4786 else if (vi->id == nonlocal_id)
4788 else if (vi->is_heap_var)
4789 /* We represent heapvars in the points-to set properly. */
4791 else if (vi->id == readonly_id)
4794 else if (vi->id == anything_id
4795 || vi->id == integer_id)
4798 if (vi->is_restrict_var)
4799 pt->vars_contains_restrict = true;
4802 /* Instead of doing extra work, simply do not create
4803 elaborate points-to information for pt_anything pointers. */
4805 && (vi->is_artificial_var
4806 || !pt->vars_contains_restrict))
4809 /* Share the final set of variables when possible. */
4810 finished_solution = BITMAP_GGC_ALLOC ();
4811 stats.points_to_sets_created++;
4813 set_uids_in_ptset (finished_solution, vi->solution, pt);
4814 result = shared_bitmap_lookup (finished_solution);
4817 shared_bitmap_add (finished_solution);
4818 pt->vars = finished_solution;
4823 bitmap_clear (finished_solution);
4827 /* Given a pointer variable P, fill in its points-to set. */
4830 find_what_p_points_to (tree p)
4832 struct ptr_info_def *pi;
4836 /* For parameters, get at the points-to set for the actual parm
4838 if (TREE_CODE (p) == SSA_NAME
4839 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4840 && SSA_NAME_IS_DEFAULT_DEF (p))
4841 lookup_p = SSA_NAME_VAR (p);
4843 vi = lookup_vi_for_tree (lookup_p);
4847 pi = get_ptr_info (p);
4848 find_what_var_points_to (vi, &pi->pt);
4852 /* Query statistics for points-to solutions. */
4855 unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
4856 unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
4857 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
4858 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
4862 dump_pta_stats (FILE *s)
4864 fprintf (s, "\nPTA query stats:\n");
4865 fprintf (s, " pt_solution_includes: "
4866 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
4867 HOST_WIDE_INT_PRINT_DEC" queries\n",
4868 pta_stats.pt_solution_includes_no_alias,
4869 pta_stats.pt_solution_includes_no_alias
4870 + pta_stats.pt_solution_includes_may_alias);
4871 fprintf (s, " pt_solutions_intersect: "
4872 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
4873 HOST_WIDE_INT_PRINT_DEC" queries\n",
4874 pta_stats.pt_solutions_intersect_no_alias,
4875 pta_stats.pt_solutions_intersect_no_alias
4876 + pta_stats.pt_solutions_intersect_may_alias);
4880 /* Reset the points-to solution *PT to a conservative default
4881 (point to anything). */
4884 pt_solution_reset (struct pt_solution *pt)
4886 memset (pt, 0, sizeof (struct pt_solution));
4887 pt->anything = true;
4890 /* Set the points-to solution *PT to point only to the variables
4894 pt_solution_set (struct pt_solution *pt, bitmap vars)
4899 memset (pt, 0, sizeof (struct pt_solution));
4901 EXECUTE_IF_SET_IN_BITMAP (vars, 0, i, bi)
4903 tree var = referenced_var_lookup (i);
4904 if (is_global_var (var))
4906 pt->vars_contains_global = true;
4912 /* Return true if the points-to solution *PT is empty. */
4915 pt_solution_empty_p (struct pt_solution *pt)
4922 && !bitmap_empty_p (pt->vars))
4925 /* If the solution includes ESCAPED, check if that is empty. */
4927 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
4933 /* Return true if the points-to solution *PT includes global memory. */
4936 pt_solution_includes_global (struct pt_solution *pt)
4940 || pt->vars_contains_global)
4944 return pt_solution_includes_global (&cfun->gimple_df->escaped);
4949 /* Return true if the points-to solution *PT includes the variable
4950 declaration DECL. */
4953 pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
4959 && is_global_var (decl))
4963 && bitmap_bit_p (pt->vars, DECL_UID (decl)))
4966 /* If the solution includes ESCAPED, check it. */
4968 && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
4975 pt_solution_includes (struct pt_solution *pt, const_tree decl)
4977 bool res = pt_solution_includes_1 (pt, decl);
4979 ++pta_stats.pt_solution_includes_may_alias;
4981 ++pta_stats.pt_solution_includes_no_alias;
4985 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
4989 pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
4991 if (pt1->anything || pt2->anything)
4994 /* If either points to unknown global memory and the other points to
4995 any global memory they alias. */
4998 || pt2->vars_contains_global))
5000 && pt1->vars_contains_global))
5003 /* Check the escaped solution if required. */
5004 if ((pt1->escaped || pt2->escaped)
5005 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
5007 /* If both point to escaped memory and that solution
5008 is not empty they alias. */
5009 if (pt1->escaped && pt2->escaped)
5012 /* If either points to escaped memory see if the escaped solution
5013 intersects with the other. */
5015 && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt2))
5017 && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt1)))
5021 /* Now both pointers alias if their points-to solution intersects. */
5024 && bitmap_intersect_p (pt1->vars, pt2->vars));
5028 pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
5030 bool res = pt_solutions_intersect_1 (pt1, pt2);
5032 ++pta_stats.pt_solutions_intersect_may_alias;
5034 ++pta_stats.pt_solutions_intersect_no_alias;
5038 /* Return true if both points-to solutions PT1 and PT2 for two restrict
5039 qualified pointers are possibly based on the same pointer. */
5042 pt_solutions_same_restrict_base (struct pt_solution *pt1,
5043 struct pt_solution *pt2)
5045 /* If we deal with points-to solutions of two restrict qualified
5046 pointers solely rely on the pointed-to variable bitmap intersection.
5047 For two pointers that are based on each other the bitmaps will
5049 if (pt1->vars_contains_restrict
5050 && pt2->vars_contains_restrict)
5052 gcc_assert (pt1->vars && pt2->vars);
5053 return bitmap_intersect_p (pt1->vars, pt2->vars);
5060 /* Dump points-to information to OUTFILE. */
5063 dump_sa_points_to_info (FILE *outfile)
5067 fprintf (outfile, "\nPoints-to sets\n\n");
5069 if (dump_flags & TDF_STATS)
5071 fprintf (outfile, "Stats:\n");
5072 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
5073 fprintf (outfile, "Non-pointer vars: %d\n",
5074 stats.nonpointer_vars);
5075 fprintf (outfile, "Statically unified vars: %d\n",
5076 stats.unified_vars_static);
5077 fprintf (outfile, "Dynamically unified vars: %d\n",
5078 stats.unified_vars_dynamic);
5079 fprintf (outfile, "Iterations: %d\n", stats.iterations);
5080 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
5081 fprintf (outfile, "Number of implicit edges: %d\n",
5082 stats.num_implicit_edges);
5085 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
5086 dump_solution_for_var (outfile, i);
5090 /* Debug points-to information to stderr. */
5093 debug_sa_points_to_info (void)
5095 dump_sa_points_to_info (stderr);
5099 /* Initialize the always-existing constraint variables for NULL
5100 ANYTHING, READONLY, and INTEGER */
5103 init_base_vars (void)
5105 struct constraint_expr lhs, rhs;
5106 varinfo_t var_anything;
5107 varinfo_t var_nothing;
5108 varinfo_t var_readonly;
5109 varinfo_t var_escaped;
5110 varinfo_t var_nonlocal;
5111 varinfo_t var_callused;
5112 varinfo_t var_storedanything;
5113 varinfo_t var_integer;
5115 /* Create the NULL variable, used to represent that a variable points
5117 var_nothing = new_var_info (NULL_TREE, "NULL");
5118 gcc_assert (var_nothing->id == nothing_id);
5119 var_nothing->is_artificial_var = 1;
5120 var_nothing->offset = 0;
5121 var_nothing->size = ~0;
5122 var_nothing->fullsize = ~0;
5123 var_nothing->is_special_var = 1;
5125 /* Create the ANYTHING variable, used to represent that a variable
5126 points to some unknown piece of memory. */
5127 var_anything = new_var_info (NULL_TREE, "ANYTHING");
5128 gcc_assert (var_anything->id == anything_id);
5129 var_anything->is_artificial_var = 1;
5130 var_anything->size = ~0;
5131 var_anything->offset = 0;
5132 var_anything->next = NULL;
5133 var_anything->fullsize = ~0;
5134 var_anything->is_special_var = 1;
5136 /* Anything points to anything. This makes deref constraints just
5137 work in the presence of linked list and other p = *p type loops,
5138 by saying that *ANYTHING = 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 var_readonly = new_var_info (NULL_TREE, "READONLY");
5154 gcc_assert (var_readonly->id == readonly_id);
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;
5162 /* readonly memory points to anything, in order to make deref
5163 easier. In reality, it points to anything the particular
5164 readonly variable can point to, but we don't track this
5167 lhs.var = readonly_id;
5169 rhs.type = ADDRESSOF;
5170 rhs.var = readonly_id; /* FIXME */
5172 process_constraint (new_constraint (lhs, rhs));
5174 /* Create the ESCAPED variable, used to represent the set of escaped
5176 var_escaped = new_var_info (NULL_TREE, "ESCAPED");
5177 gcc_assert (var_escaped->id == escaped_id);
5178 var_escaped->is_artificial_var = 1;
5179 var_escaped->offset = 0;
5180 var_escaped->size = ~0;
5181 var_escaped->fullsize = ~0;
5182 var_escaped->is_special_var = 0;
5184 /* Create the NONLOCAL variable, used to represent the set of nonlocal
5186 var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL");
5187 gcc_assert (var_nonlocal->id == nonlocal_id);
5188 var_nonlocal->is_artificial_var = 1;
5189 var_nonlocal->offset = 0;
5190 var_nonlocal->size = ~0;
5191 var_nonlocal->fullsize = ~0;
5192 var_nonlocal->is_special_var = 1;
5194 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
5196 lhs.var = escaped_id;
5199 rhs.var = escaped_id;
5201 process_constraint (new_constraint (lhs, rhs));
5203 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
5204 whole variable escapes. */
5206 lhs.var = escaped_id;
5209 rhs.var = escaped_id;
5210 rhs.offset = UNKNOWN_OFFSET;
5211 process_constraint (new_constraint (lhs, rhs));
5213 /* *ESCAPED = NONLOCAL. This is true because we have to assume
5214 everything pointed to by escaped points to what global memory can
5217 lhs.var = escaped_id;
5220 rhs.var = nonlocal_id;
5222 process_constraint (new_constraint (lhs, rhs));
5224 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
5225 global memory may point to global memory and escaped memory. */
5227 lhs.var = nonlocal_id;
5229 rhs.type = ADDRESSOF;
5230 rhs.var = nonlocal_id;
5232 process_constraint (new_constraint (lhs, rhs));
5233 rhs.type = ADDRESSOF;
5234 rhs.var = escaped_id;
5236 process_constraint (new_constraint (lhs, rhs));
5238 /* Create the CALLUSED variable, used to represent the set of call-used
5240 var_callused = new_var_info (NULL_TREE, "CALLUSED");
5241 gcc_assert (var_callused->id == callused_id);
5242 var_callused->is_artificial_var = 1;
5243 var_callused->offset = 0;
5244 var_callused->size = ~0;
5245 var_callused->fullsize = ~0;
5246 var_callused->is_special_var = 0;
5248 /* CALLUSED = *CALLUSED, because call-used is may-deref'd at calls, etc. */
5250 lhs.var = callused_id;
5253 rhs.var = callused_id;
5255 process_constraint (new_constraint (lhs, rhs));
5257 /* CALLUSED = CALLUSED + UNKNOWN, because if a sub-field is call-used the
5258 whole variable is call-used. */
5260 lhs.var = callused_id;
5263 rhs.var = callused_id;
5264 rhs.offset = UNKNOWN_OFFSET;
5265 process_constraint (new_constraint (lhs, rhs));
5267 /* Create the STOREDANYTHING variable, used to represent the set of
5268 variables stored to *ANYTHING. */
5269 var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING");
5270 gcc_assert (var_storedanything->id == storedanything_id);
5271 var_storedanything->is_artificial_var = 1;
5272 var_storedanything->offset = 0;
5273 var_storedanything->size = ~0;
5274 var_storedanything->fullsize = ~0;
5275 var_storedanything->is_special_var = 0;
5277 /* Create the INTEGER variable, used to represent that a variable points
5278 to what an INTEGER "points to". */
5279 var_integer = new_var_info (NULL_TREE, "INTEGER");
5280 gcc_assert (var_integer->id == integer_id);
5281 var_integer->is_artificial_var = 1;
5282 var_integer->size = ~0;
5283 var_integer->fullsize = ~0;
5284 var_integer->offset = 0;
5285 var_integer->next = NULL;
5286 var_integer->is_special_var = 1;
5288 /* INTEGER = ANYTHING, because we don't know where a dereference of
5289 a random integer will point to. */
5291 lhs.var = integer_id;
5293 rhs.type = ADDRESSOF;
5294 rhs.var = anything_id;
5296 process_constraint (new_constraint (lhs, rhs));
5299 /* Initialize things necessary to perform PTA */
5302 init_alias_vars (void)
5304 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
5306 bitmap_obstack_initialize (&pta_obstack);
5307 bitmap_obstack_initialize (&oldpta_obstack);
5308 bitmap_obstack_initialize (&predbitmap_obstack);
5310 constraint_pool = create_alloc_pool ("Constraint pool",
5311 sizeof (struct constraint), 30);
5312 variable_info_pool = create_alloc_pool ("Variable info pool",
5313 sizeof (struct variable_info), 30);
5314 constraints = VEC_alloc (constraint_t, heap, 8);
5315 varmap = VEC_alloc (varinfo_t, heap, 8);
5316 vi_for_tree = pointer_map_create ();
5318 memset (&stats, 0, sizeof (stats));
5319 shared_bitmap_table = htab_create (511, shared_bitmap_hash,
5320 shared_bitmap_eq, free);
5324 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
5325 predecessor edges. */
5328 remove_preds_and_fake_succs (constraint_graph_t graph)
5332 /* Clear the implicit ref and address nodes from the successor
5334 for (i = 0; i < FIRST_REF_NODE; i++)
5336 if (graph->succs[i])
5337 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
5338 FIRST_REF_NODE * 2);
5341 /* Free the successor list for the non-ref nodes. */
5342 for (i = FIRST_REF_NODE; i < graph->size; i++)
5344 if (graph->succs[i])
5345 BITMAP_FREE (graph->succs[i]);
5348 /* Now reallocate the size of the successor list as, and blow away
5349 the predecessor bitmaps. */
5350 graph->size = VEC_length (varinfo_t, varmap);
5351 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
5353 free (graph->implicit_preds);
5354 graph->implicit_preds = NULL;
5355 free (graph->preds);
5356 graph->preds = NULL;
5357 bitmap_obstack_release (&predbitmap_obstack);
5360 /* Initialize the heapvar for statement mapping. */
5363 init_alias_heapvars (void)
5365 if (!heapvar_for_stmt)
5366 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5370 /* Delete the heapvar for statement mapping. */
5373 delete_alias_heapvars (void)
5375 if (heapvar_for_stmt)
5376 htab_delete (heapvar_for_stmt);
5377 heapvar_for_stmt = NULL;
5380 /* Create points-to sets for the current function. See the comments
5381 at the start of the file for an algorithmic overview. */
5384 compute_points_to_sets (void)
5386 struct scc_info *si;
5391 timevar_push (TV_TREE_PTA);
5394 init_alias_heapvars ();
5396 intra_create_variable_infos ();
5398 /* Now walk all statements and derive aliases. */
5401 gimple_stmt_iterator gsi;
5403 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5405 gimple phi = gsi_stmt (gsi);
5407 if (is_gimple_reg (gimple_phi_result (phi)))
5408 find_func_aliases (phi);
5411 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5413 gimple stmt = gsi_stmt (gsi);
5415 find_func_aliases (stmt);
5421 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5422 dump_constraints (dump_file);
5427 "\nCollapsing static cycles and doing variable "
5430 init_graph (VEC_length (varinfo_t, varmap) * 2);
5433 fprintf (dump_file, "Building predecessor graph\n");
5434 build_pred_graph ();
5437 fprintf (dump_file, "Detecting pointer and location "
5439 si = perform_var_substitution (graph);
5442 fprintf (dump_file, "Rewriting constraints and unifying "
5444 rewrite_constraints (graph, si);
5446 build_succ_graph ();
5447 free_var_substitution_info (si);
5449 if (dump_file && (dump_flags & TDF_GRAPH))
5450 dump_constraint_graph (dump_file);
5452 move_complex_constraints (graph);
5455 fprintf (dump_file, "Uniting pointer but not location equivalent "
5457 unite_pointer_equivalences (graph);
5460 fprintf (dump_file, "Finding indirect cycles\n");
5461 find_indirect_cycles (graph);
5463 /* Implicit nodes and predecessors are no longer necessary at this
5465 remove_preds_and_fake_succs (graph);
5468 fprintf (dump_file, "Solving graph\n");
5470 solve_graph (graph);
5473 dump_sa_points_to_info (dump_file);
5475 /* Compute the points-to sets for ESCAPED and CALLUSED used for
5476 call-clobber analysis. */
5477 find_what_var_points_to (get_varinfo (escaped_id),
5478 &cfun->gimple_df->escaped);
5479 find_what_var_points_to (get_varinfo (callused_id),
5480 &cfun->gimple_df->callused);
5482 /* Make sure the ESCAPED solution (which is used as placeholder in
5483 other solutions) does not reference itself. This simplifies
5484 points-to solution queries. */
5485 cfun->gimple_df->escaped.escaped = 0;
5487 /* Mark escaped HEAP variables as global. */
5488 for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); ++i)
5490 && !vi->is_restrict_var
5491 && !vi->is_global_var)
5492 DECL_EXTERNAL (vi->decl) = vi->is_global_var
5493 = pt_solution_includes (&cfun->gimple_df->escaped, vi->decl);
5495 /* Compute the points-to sets for pointer SSA_NAMEs. */
5496 for (i = 0; i < num_ssa_names; ++i)
5498 tree ptr = ssa_name (i);
5500 && POINTER_TYPE_P (TREE_TYPE (ptr)))
5501 find_what_p_points_to (ptr);
5504 timevar_pop (TV_TREE_PTA);
5506 have_alias_info = true;
5510 /* Delete created points-to sets. */
5513 delete_points_to_sets (void)
5517 htab_delete (shared_bitmap_table);
5518 if (dump_file && (dump_flags & TDF_STATS))
5519 fprintf (dump_file, "Points to sets created:%d\n",
5520 stats.points_to_sets_created);
5522 pointer_map_destroy (vi_for_tree);
5523 bitmap_obstack_release (&pta_obstack);
5524 VEC_free (constraint_t, heap, constraints);
5526 for (i = 0; i < graph->size; i++)
5527 VEC_free (constraint_t, heap, graph->complex[i]);
5528 free (graph->complex);
5531 free (graph->succs);
5533 free (graph->pe_rep);
5534 free (graph->indirect_cycles);
5537 VEC_free (varinfo_t, heap, varmap);
5538 free_alloc_pool (variable_info_pool);
5539 free_alloc_pool (constraint_pool);
5540 have_alias_info = false;
5544 /* Compute points-to information for every SSA_NAME pointer in the
5545 current function and compute the transitive closure of escaped
5546 variables to re-initialize the call-clobber states of local variables. */
5549 compute_may_aliases (void)
5551 /* For each pointer P_i, determine the sets of variables that P_i may
5552 point-to. Compute the reachability set of escaped and call-used
5554 compute_points_to_sets ();
5556 /* Debugging dumps. */
5559 dump_alias_info (dump_file);
5561 if (dump_flags & TDF_DETAILS)
5562 dump_referenced_vars (dump_file);
5565 /* Deallocate memory used by aliasing data structures and the internal
5566 points-to solution. */
5567 delete_points_to_sets ();
5569 gcc_assert (!need_ssa_update_p (cfun));
5575 gate_tree_pta (void)
5577 return flag_tree_pta;
5580 /* A dummy pass to cause points-to information to be computed via
5581 TODO_rebuild_alias. */
5583 struct gimple_opt_pass pass_build_alias =
5588 gate_tree_pta, /* gate */
5592 0, /* static_pass_number */
5593 TV_NONE, /* tv_id */
5594 PROP_cfg | PROP_ssa, /* properties_required */
5595 0, /* properties_provided */
5596 0, /* properties_destroyed */
5597 0, /* todo_flags_start */
5598 TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */
5602 /* A dummy pass to cause points-to information to be computed via
5603 TODO_rebuild_alias. */
5605 struct gimple_opt_pass pass_build_ealias =
5609 "ealias", /* name */
5610 gate_tree_pta, /* gate */
5614 0, /* static_pass_number */
5615 TV_NONE, /* tv_id */
5616 PROP_cfg | PROP_ssa, /* properties_required */
5617 0, /* properties_provided */
5618 0, /* properties_destroyed */
5619 0, /* todo_flags_start */
5620 TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */
5625 /* Return true if we should execute IPA PTA. */
5629 return (flag_ipa_pta
5630 /* Don't bother doing anything if the program has errors. */
5631 && !(errorcount || sorrycount));
5634 /* Execute the driver for IPA PTA. */
5636 ipa_pta_execute (void)
5638 struct cgraph_node *node;
5639 struct scc_info *si;
5642 init_alias_heapvars ();
5645 for (node = cgraph_nodes; node; node = node->next)
5649 varid = create_function_info_for (node->decl,
5650 cgraph_node_name (node));
5651 if (node->local.externally_visible)
5653 varinfo_t fi = get_varinfo (varid);
5654 for (; fi; fi = fi->next)
5655 make_constraint_from (fi, anything_id);
5658 for (node = cgraph_nodes; node; node = node->next)
5662 struct function *func = DECL_STRUCT_FUNCTION (node->decl);
5664 tree old_func_decl = current_function_decl;
5667 "Generating constraints for %s\n",
5668 cgraph_node_name (node));
5670 current_function_decl = node->decl;
5672 FOR_EACH_BB_FN (bb, func)
5674 gimple_stmt_iterator gsi;
5676 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
5679 gimple phi = gsi_stmt (gsi);
5681 if (is_gimple_reg (gimple_phi_result (phi)))
5682 find_func_aliases (phi);
5685 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5686 find_func_aliases (gsi_stmt (gsi));
5688 current_function_decl = old_func_decl;
5693 /* Make point to anything. */
5699 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5700 dump_constraints (dump_file);
5705 "\nCollapsing static cycles and doing variable "
5708 init_graph (VEC_length (varinfo_t, varmap) * 2);
5709 build_pred_graph ();
5710 si = perform_var_substitution (graph);
5711 rewrite_constraints (graph, si);
5713 build_succ_graph ();
5714 free_var_substitution_info (si);
5715 move_complex_constraints (graph);
5716 unite_pointer_equivalences (graph);
5717 find_indirect_cycles (graph);
5719 /* Implicit nodes and predecessors are no longer necessary at this
5721 remove_preds_and_fake_succs (graph);
5724 fprintf (dump_file, "\nSolving graph\n");
5726 solve_graph (graph);
5729 dump_sa_points_to_info (dump_file);
5732 delete_alias_heapvars ();
5733 delete_points_to_sets ();
5737 struct simple_ipa_opt_pass pass_ipa_pta =
5742 gate_ipa_pta, /* gate */
5743 ipa_pta_execute, /* execute */
5746 0, /* static_pass_number */
5747 TV_IPA_PTA, /* tv_id */
5748 0, /* properties_required */
5749 0, /* properties_provided */
5750 0, /* properties_destroyed */
5751 0, /* todo_flags_start */
5752 TODO_update_ssa /* todo_flags_finish */
5757 #include "gt-tree-ssa-structalias.h"