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_full_var = (t == NULL_TREE);
341 ret->is_heap_var = false;
342 ret->is_special_var = false;
343 ret->is_unknown_size_var = false;
344 ret->may_have_pointers = true;
345 ret->is_global_var = (t == NULL_TREE);
347 ret->is_global_var = is_global_var (t);
348 ret->solution = BITMAP_ALLOC (&pta_obstack);
349 ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
352 VEC_safe_push (varinfo_t, heap, varmap, ret);
357 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
359 /* An expression that appears in a constraint. */
361 struct constraint_expr
363 /* Constraint type. */
364 constraint_expr_type type;
366 /* Variable we are referring to in the constraint. */
369 /* Offset, in bits, of this constraint from the beginning of
370 variables it ends up referring to.
372 IOW, in a deref constraint, we would deref, get the result set,
373 then add OFFSET to each member. */
374 HOST_WIDE_INT offset;
377 /* Use 0x8000... as special unknown offset. */
378 #define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))
380 typedef struct constraint_expr ce_s;
382 DEF_VEC_ALLOC_O(ce_s, heap);
383 static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);
384 static void get_constraint_for (tree, VEC(ce_s, heap) **);
385 static void do_deref (VEC (ce_s, heap) **);
387 /* Our set constraints are made up of two constraint expressions, one
390 As described in the introduction, our set constraints each represent an
391 operation between set valued variables.
395 struct constraint_expr lhs;
396 struct constraint_expr rhs;
399 /* List of constraints that we use to build the constraint graph from. */
401 static VEC(constraint_t,heap) *constraints;
402 static alloc_pool constraint_pool;
406 DEF_VEC_ALLOC_I(int, heap);
408 /* The constraint graph is represented as an array of bitmaps
409 containing successor nodes. */
411 struct constraint_graph
413 /* Size of this graph, which may be different than the number of
414 nodes in the variable map. */
417 /* Explicit successors of each node. */
420 /* Implicit predecessors of each node (Used for variable
422 bitmap *implicit_preds;
424 /* Explicit predecessors of each node (Used for variable substitution). */
427 /* Indirect cycle representatives, or -1 if the node has no indirect
429 int *indirect_cycles;
431 /* Representative node for a node. rep[a] == a unless the node has
435 /* Equivalence class representative for a label. This is used for
436 variable substitution. */
439 /* Pointer equivalence label for a node. All nodes with the same
440 pointer equivalence label can be unified together at some point
441 (either during constraint optimization or after the constraint
445 /* Pointer equivalence representative for a label. This is used to
446 handle nodes that are pointer equivalent but not location
447 equivalent. We can unite these once the addressof constraints
448 are transformed into initial points-to sets. */
451 /* Pointer equivalence label for each node, used during variable
453 unsigned int *pointer_label;
455 /* Location equivalence label for each node, used during location
456 equivalence finding. */
457 unsigned int *loc_label;
459 /* Pointed-by set for each node, used during location equivalence
460 finding. This is pointed-by rather than pointed-to, because it
461 is constructed using the predecessor graph. */
464 /* Points to sets for pointer equivalence. This is *not* the actual
465 points-to sets for nodes. */
468 /* Bitmap of nodes where the bit is set if the node is a direct
469 node. Used for variable substitution. */
470 sbitmap direct_nodes;
472 /* Bitmap of nodes where the bit is set if the node is address
473 taken. Used for variable substitution. */
474 bitmap address_taken;
476 /* Vector of complex constraints for each graph node. Complex
477 constraints are those involving dereferences or offsets that are
479 VEC(constraint_t,heap) **complex;
482 static constraint_graph_t graph;
484 /* During variable substitution and the offline version of indirect
485 cycle finding, we create nodes to represent dereferences and
486 address taken constraints. These represent where these start and
488 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
489 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
491 /* Return the representative node for NODE, if NODE has been unioned
493 This function performs path compression along the way to finding
494 the representative. */
497 find (unsigned int node)
499 gcc_assert (node < graph->size);
500 if (graph->rep[node] != node)
501 return graph->rep[node] = find (graph->rep[node]);
505 /* Union the TO and FROM nodes to the TO nodes.
506 Note that at some point in the future, we may want to do
507 union-by-rank, in which case we are going to have to return the
508 node we unified to. */
511 unite (unsigned int to, unsigned int from)
513 gcc_assert (to < graph->size && from < graph->size);
514 if (to != from && graph->rep[from] != to)
516 graph->rep[from] = to;
522 /* Create a new constraint consisting of LHS and RHS expressions. */
525 new_constraint (const struct constraint_expr lhs,
526 const struct constraint_expr rhs)
528 constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
534 /* Print out constraint C to FILE. */
537 dump_constraint (FILE *file, constraint_t c)
539 if (c->lhs.type == ADDRESSOF)
541 else if (c->lhs.type == DEREF)
543 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
544 if (c->lhs.offset == UNKNOWN_OFFSET)
545 fprintf (file, " + UNKNOWN");
546 else if (c->lhs.offset != 0)
547 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
548 fprintf (file, " = ");
549 if (c->rhs.type == ADDRESSOF)
551 else if (c->rhs.type == DEREF)
553 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
554 if (c->rhs.offset == UNKNOWN_OFFSET)
555 fprintf (file, " + UNKNOWN");
556 else if (c->rhs.offset != 0)
557 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
558 fprintf (file, "\n");
562 void debug_constraint (constraint_t);
563 void debug_constraints (void);
564 void debug_constraint_graph (void);
565 void debug_solution_for_var (unsigned int);
566 void debug_sa_points_to_info (void);
568 /* Print out constraint C to stderr. */
571 debug_constraint (constraint_t c)
573 dump_constraint (stderr, c);
576 /* Print out all constraints to FILE */
579 dump_constraints (FILE *file)
583 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
584 dump_constraint (file, c);
587 /* Print out all constraints to stderr. */
590 debug_constraints (void)
592 dump_constraints (stderr);
595 /* Print out to FILE the edge in the constraint graph that is created by
596 constraint c. The edge may have a label, depending on the type of
597 constraint that it represents. If complex1, e.g: a = *b, then the label
598 is "=*", if complex2, e.g: *a = b, then the label is "*=", if
599 complex with an offset, e.g: a = b + 8, then the label is "+".
600 Otherwise the edge has no label. */
603 dump_constraint_edge (FILE *file, constraint_t c)
605 if (c->rhs.type != ADDRESSOF)
607 const char *src = get_varinfo (c->rhs.var)->name;
608 const char *dst = get_varinfo (c->lhs.var)->name;
609 fprintf (file, " \"%s\" -> \"%s\" ", src, dst);
610 /* Due to preprocessing of constraints, instructions like *a = *b are
611 illegal; thus, we do not have to handle such cases. */
612 if (c->lhs.type == DEREF)
613 fprintf (file, " [ label=\"*=\" ] ;\n");
614 else if (c->rhs.type == DEREF)
615 fprintf (file, " [ label=\"=*\" ] ;\n");
618 /* We must check the case where the constraint is an offset.
619 In this case, it is treated as a complex constraint. */
620 if (c->rhs.offset != c->lhs.offset)
621 fprintf (file, " [ label=\"+\" ] ;\n");
623 fprintf (file, " ;\n");
628 /* Print the constraint graph in dot format. */
631 dump_constraint_graph (FILE *file)
633 unsigned int i=0, size;
636 /* Only print the graph if it has already been initialized: */
640 /* Print the constraints used to produce the constraint graph. The
641 constraints will be printed as comments in the dot file: */
642 fprintf (file, "\n\n/* Constraints used in the constraint graph:\n");
643 dump_constraints (file);
644 fprintf (file, "*/\n");
646 /* Prints the header of the dot file: */
647 fprintf (file, "\n\n// The constraint graph in dot format:\n");
648 fprintf (file, "strict digraph {\n");
649 fprintf (file, " node [\n shape = box\n ]\n");
650 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
651 fprintf (file, "\n // List of nodes in the constraint graph:\n");
653 /* The next lines print the nodes in the graph. In order to get the
654 number of nodes in the graph, we must choose the minimum between the
655 vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
656 yet been initialized, then graph->size == 0, otherwise we must only
657 read nodes that have an entry in VEC (varinfo_t, varmap). */
658 size = VEC_length (varinfo_t, varmap);
659 size = size < graph->size ? size : graph->size;
660 for (i = 0; i < size; i++)
662 const char *name = get_varinfo (graph->rep[i])->name;
663 fprintf (file, " \"%s\" ;\n", name);
666 /* Go over the list of constraints printing the edges in the constraint
668 fprintf (file, "\n // The constraint edges:\n");
669 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
671 dump_constraint_edge (file, c);
673 /* Prints the tail of the dot file. By now, only the closing bracket. */
674 fprintf (file, "}\n\n\n");
677 /* Print out the constraint graph to stderr. */
680 debug_constraint_graph (void)
682 dump_constraint_graph (stderr);
687 The solver is a simple worklist solver, that works on the following
690 sbitmap changed_nodes = all zeroes;
692 For each node that is not already collapsed:
694 set bit in changed nodes
696 while (changed_count > 0)
698 compute topological ordering for constraint graph
700 find and collapse cycles in the constraint graph (updating
701 changed if necessary)
703 for each node (n) in the graph in topological order:
706 Process each complex constraint associated with the node,
707 updating changed if necessary.
709 For each outgoing edge from n, propagate the solution from n to
710 the destination of the edge, updating changed as necessary.
714 /* Return true if two constraint expressions A and B are equal. */
717 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
719 return a.type == b.type && a.var == b.var && a.offset == b.offset;
722 /* Return true if constraint expression A is less than constraint expression
723 B. This is just arbitrary, but consistent, in order to give them an
727 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
729 if (a.type == b.type)
732 return a.offset < b.offset;
734 return a.var < b.var;
737 return a.type < b.type;
740 /* Return true if constraint A is less than constraint B. This is just
741 arbitrary, but consistent, in order to give them an ordering. */
744 constraint_less (const constraint_t a, const constraint_t b)
746 if (constraint_expr_less (a->lhs, b->lhs))
748 else if (constraint_expr_less (b->lhs, a->lhs))
751 return constraint_expr_less (a->rhs, b->rhs);
754 /* Return true if two constraints A and B are equal. */
757 constraint_equal (struct constraint a, struct constraint b)
759 return constraint_expr_equal (a.lhs, b.lhs)
760 && constraint_expr_equal (a.rhs, b.rhs);
764 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
767 constraint_vec_find (VEC(constraint_t,heap) *vec,
768 struct constraint lookfor)
776 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
777 if (place >= VEC_length (constraint_t, vec))
779 found = VEC_index (constraint_t, vec, place);
780 if (!constraint_equal (*found, lookfor))
785 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
788 constraint_set_union (VEC(constraint_t,heap) **to,
789 VEC(constraint_t,heap) **from)
794 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
796 if (constraint_vec_find (*to, *c) == NULL)
798 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
800 VEC_safe_insert (constraint_t, heap, *to, place, c);
805 /* Expands the solution in SET to all sub-fields of variables included.
806 Union the expanded result into RESULT. */
809 solution_set_expand (bitmap result, bitmap set)
815 /* In a first pass record all variables we need to add all
816 sub-fields off. This avoids quadratic behavior. */
817 EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
819 varinfo_t v = get_varinfo (j);
820 if (v->is_artificial_var
823 v = lookup_vi_for_tree (v->decl);
825 vars = BITMAP_ALLOC (NULL);
826 bitmap_set_bit (vars, v->id);
829 /* In the second pass now do the addition to the solution and
830 to speed up solving add it to the delta as well. */
833 EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
835 varinfo_t v = get_varinfo (j);
836 for (; v != NULL; v = v->next)
837 bitmap_set_bit (result, v->id);
843 /* Take a solution set SET, add OFFSET to each member of the set, and
844 overwrite SET with the result when done. */
847 solution_set_add (bitmap set, HOST_WIDE_INT offset)
849 bitmap result = BITMAP_ALLOC (&iteration_obstack);
853 /* If the offset is unknown we have to expand the solution to
855 if (offset == UNKNOWN_OFFSET)
857 solution_set_expand (set, set);
861 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
863 varinfo_t vi = get_varinfo (i);
865 /* If this is a variable with just one field just set its bit
867 if (vi->is_artificial_var
868 || vi->is_unknown_size_var
870 bitmap_set_bit (result, i);
873 unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
875 /* If the offset makes the pointer point to before the
876 variable use offset zero for the field lookup. */
878 && fieldoffset > vi->offset)
882 vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
884 bitmap_set_bit (result, vi->id);
885 /* If the result is not exactly at fieldoffset include the next
886 field as well. See get_constraint_for_ptr_offset for more
888 if (vi->offset != fieldoffset
890 bitmap_set_bit (result, vi->next->id);
894 bitmap_copy (set, result);
895 BITMAP_FREE (result);
898 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
902 set_union_with_increment (bitmap to, bitmap from, HOST_WIDE_INT inc)
905 return bitmap_ior_into (to, from);
911 tmp = BITMAP_ALLOC (&iteration_obstack);
912 bitmap_copy (tmp, from);
913 solution_set_add (tmp, inc);
914 res = bitmap_ior_into (to, tmp);
920 /* Insert constraint C into the list of complex constraints for graph
924 insert_into_complex (constraint_graph_t graph,
925 unsigned int var, constraint_t c)
927 VEC (constraint_t, heap) *complex = graph->complex[var];
928 unsigned int place = VEC_lower_bound (constraint_t, complex, c,
931 /* Only insert constraints that do not already exist. */
932 if (place >= VEC_length (constraint_t, complex)
933 || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
934 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
938 /* Condense two variable nodes into a single variable node, by moving
939 all associated info from SRC to TO. */
942 merge_node_constraints (constraint_graph_t graph, unsigned int to,
948 gcc_assert (find (from) == to);
950 /* Move all complex constraints from src node into to node */
951 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
953 /* In complex constraints for node src, we may have either
954 a = *src, and *src = a, or an offseted constraint which are
955 always added to the rhs node's constraints. */
957 if (c->rhs.type == DEREF)
959 else if (c->lhs.type == DEREF)
964 constraint_set_union (&graph->complex[to], &graph->complex[from]);
965 VEC_free (constraint_t, heap, graph->complex[from]);
966 graph->complex[from] = NULL;
970 /* Remove edges involving NODE from GRAPH. */
973 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
975 if (graph->succs[node])
976 BITMAP_FREE (graph->succs[node]);
979 /* Merge GRAPH nodes FROM and TO into node TO. */
982 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
985 if (graph->indirect_cycles[from] != -1)
987 /* If we have indirect cycles with the from node, and we have
988 none on the to node, the to node has indirect cycles from the
989 from node now that they are unified.
990 If indirect cycles exist on both, unify the nodes that they
991 are in a cycle with, since we know they are in a cycle with
993 if (graph->indirect_cycles[to] == -1)
994 graph->indirect_cycles[to] = graph->indirect_cycles[from];
997 /* Merge all the successor edges. */
998 if (graph->succs[from])
1000 if (!graph->succs[to])
1001 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1002 bitmap_ior_into (graph->succs[to],
1003 graph->succs[from]);
1006 clear_edges_for_node (graph, from);
1010 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
1011 it doesn't exist in the graph already. */
1014 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1020 if (!graph->implicit_preds[to])
1021 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1023 if (bitmap_set_bit (graph->implicit_preds[to], from))
1024 stats.num_implicit_edges++;
1027 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1028 it doesn't exist in the graph already.
1029 Return false if the edge already existed, true otherwise. */
1032 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1035 if (!graph->preds[to])
1036 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1037 bitmap_set_bit (graph->preds[to], from);
1040 /* Add a graph edge to GRAPH, going from FROM to TO if
1041 it doesn't exist in the graph already.
1042 Return false if the edge already existed, true otherwise. */
1045 add_graph_edge (constraint_graph_t graph, unsigned int to,
1056 if (!graph->succs[from])
1057 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1058 if (bitmap_set_bit (graph->succs[from], to))
1061 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1069 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
1072 valid_graph_edge (constraint_graph_t graph, unsigned int src,
1075 return (graph->succs[dest]
1076 && bitmap_bit_p (graph->succs[dest], src));
1079 /* Initialize the constraint graph structure to contain SIZE nodes. */
1082 init_graph (unsigned int size)
1086 graph = XCNEW (struct constraint_graph);
1088 graph->succs = XCNEWVEC (bitmap, graph->size);
1089 graph->indirect_cycles = XNEWVEC (int, graph->size);
1090 graph->rep = XNEWVEC (unsigned int, graph->size);
1091 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
1092 graph->pe = XCNEWVEC (unsigned int, graph->size);
1093 graph->pe_rep = XNEWVEC (int, graph->size);
1095 for (j = 0; j < graph->size; j++)
1098 graph->pe_rep[j] = -1;
1099 graph->indirect_cycles[j] = -1;
1103 /* Build the constraint graph, adding only predecessor edges right now. */
1106 build_pred_graph (void)
1112 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1113 graph->preds = XCNEWVEC (bitmap, graph->size);
1114 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1115 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1116 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1117 graph->points_to = XCNEWVEC (bitmap, graph->size);
1118 graph->eq_rep = XNEWVEC (int, graph->size);
1119 graph->direct_nodes = sbitmap_alloc (graph->size);
1120 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1121 sbitmap_zero (graph->direct_nodes);
1123 for (j = 0; j < FIRST_REF_NODE; j++)
1125 if (!get_varinfo (j)->is_special_var)
1126 SET_BIT (graph->direct_nodes, j);
1129 for (j = 0; j < graph->size; j++)
1130 graph->eq_rep[j] = -1;
1132 for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
1133 graph->indirect_cycles[j] = -1;
1135 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1137 struct constraint_expr lhs = c->lhs;
1138 struct constraint_expr rhs = c->rhs;
1139 unsigned int lhsvar = lhs.var;
1140 unsigned int rhsvar = rhs.var;
1142 if (lhs.type == DEREF)
1145 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1146 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1148 else if (rhs.type == DEREF)
1151 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1152 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1154 RESET_BIT (graph->direct_nodes, lhsvar);
1156 else if (rhs.type == ADDRESSOF)
1161 if (graph->points_to[lhsvar] == NULL)
1162 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1163 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1165 if (graph->pointed_by[rhsvar] == NULL)
1166 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1167 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1169 /* Implicitly, *x = y */
1170 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1172 /* All related variables are no longer direct nodes. */
1173 RESET_BIT (graph->direct_nodes, rhsvar);
1174 v = get_varinfo (rhsvar);
1175 if (!v->is_full_var)
1177 v = lookup_vi_for_tree (v->decl);
1180 RESET_BIT (graph->direct_nodes, v->id);
1185 bitmap_set_bit (graph->address_taken, rhsvar);
1187 else if (lhsvar > anything_id
1188 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1191 add_pred_graph_edge (graph, lhsvar, rhsvar);
1192 /* Implicitly, *x = *y */
1193 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1194 FIRST_REF_NODE + rhsvar);
1196 else if (lhs.offset != 0 || rhs.offset != 0)
1198 if (rhs.offset != 0)
1199 RESET_BIT (graph->direct_nodes, lhs.var);
1200 else if (lhs.offset != 0)
1201 RESET_BIT (graph->direct_nodes, rhs.var);
1206 /* Build the constraint graph, adding successor edges. */
1209 build_succ_graph (void)
1214 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1216 struct constraint_expr lhs;
1217 struct constraint_expr rhs;
1218 unsigned int lhsvar;
1219 unsigned int rhsvar;
1226 lhsvar = find (lhs.var);
1227 rhsvar = find (rhs.var);
1229 if (lhs.type == DEREF)
1231 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1232 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1234 else if (rhs.type == DEREF)
1236 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1237 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1239 else if (rhs.type == ADDRESSOF)
1242 gcc_assert (find (rhs.var) == rhs.var);
1243 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1245 else if (lhsvar > anything_id
1246 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1248 add_graph_edge (graph, lhsvar, rhsvar);
1252 /* Add edges from STOREDANYTHING to all non-direct nodes. */
1253 t = find (storedanything_id);
1254 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1256 if (!TEST_BIT (graph->direct_nodes, i))
1257 add_graph_edge (graph, find (i), t);
1262 /* Changed variables on the last iteration. */
1263 static unsigned int changed_count;
1264 static sbitmap changed;
1266 DEF_VEC_I(unsigned);
1267 DEF_VEC_ALLOC_I(unsigned,heap);
1270 /* Strongly Connected Component visitation info. */
1277 unsigned int *node_mapping;
1279 VEC(unsigned,heap) *scc_stack;
1283 /* Recursive routine to find strongly connected components in GRAPH.
1284 SI is the SCC info to store the information in, and N is the id of current
1285 graph node we are processing.
1287 This is Tarjan's strongly connected component finding algorithm, as
1288 modified by Nuutila to keep only non-root nodes on the stack.
1289 The algorithm can be found in "On finding the strongly connected
1290 connected components in a directed graph" by Esko Nuutila and Eljas
1291 Soisalon-Soininen, in Information Processing Letters volume 49,
1292 number 1, pages 9-14. */
1295 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1299 unsigned int my_dfs;
1301 SET_BIT (si->visited, n);
1302 si->dfs[n] = si->current_index ++;
1303 my_dfs = si->dfs[n];
1305 /* Visit all the successors. */
1306 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1310 if (i > LAST_REF_NODE)
1314 if (TEST_BIT (si->deleted, w))
1317 if (!TEST_BIT (si->visited, w))
1318 scc_visit (graph, si, w);
1320 unsigned int t = find (w);
1321 unsigned int nnode = find (n);
1322 gcc_assert (nnode == n);
1324 if (si->dfs[t] < si->dfs[nnode])
1325 si->dfs[n] = si->dfs[t];
1329 /* See if any components have been identified. */
1330 if (si->dfs[n] == my_dfs)
1332 if (VEC_length (unsigned, si->scc_stack) > 0
1333 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1335 bitmap scc = BITMAP_ALLOC (NULL);
1336 bool have_ref_node = n >= FIRST_REF_NODE;
1337 unsigned int lowest_node;
1340 bitmap_set_bit (scc, n);
1342 while (VEC_length (unsigned, si->scc_stack) != 0
1343 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1345 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1347 bitmap_set_bit (scc, w);
1348 if (w >= FIRST_REF_NODE)
1349 have_ref_node = true;
1352 lowest_node = bitmap_first_set_bit (scc);
1353 gcc_assert (lowest_node < FIRST_REF_NODE);
1355 /* Collapse the SCC nodes into a single node, and mark the
1357 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1359 if (i < FIRST_REF_NODE)
1361 if (unite (lowest_node, i))
1362 unify_nodes (graph, lowest_node, i, false);
1366 unite (lowest_node, i);
1367 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1371 SET_BIT (si->deleted, n);
1374 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1377 /* Unify node FROM into node TO, updating the changed count if
1378 necessary when UPDATE_CHANGED is true. */
1381 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1382 bool update_changed)
1385 gcc_assert (to != from && find (to) == to);
1386 if (dump_file && (dump_flags & TDF_DETAILS))
1387 fprintf (dump_file, "Unifying %s to %s\n",
1388 get_varinfo (from)->name,
1389 get_varinfo (to)->name);
1392 stats.unified_vars_dynamic++;
1394 stats.unified_vars_static++;
1396 merge_graph_nodes (graph, to, from);
1397 merge_node_constraints (graph, to, from);
1399 /* Mark TO as changed if FROM was changed. If TO was already marked
1400 as changed, decrease the changed count. */
1402 if (update_changed && TEST_BIT (changed, from))
1404 RESET_BIT (changed, from);
1405 if (!TEST_BIT (changed, to))
1406 SET_BIT (changed, to);
1409 gcc_assert (changed_count > 0);
1413 if (get_varinfo (from)->solution)
1415 /* If the solution changes because of the merging, we need to mark
1416 the variable as changed. */
1417 if (bitmap_ior_into (get_varinfo (to)->solution,
1418 get_varinfo (from)->solution))
1420 if (update_changed && !TEST_BIT (changed, to))
1422 SET_BIT (changed, to);
1427 BITMAP_FREE (get_varinfo (from)->solution);
1428 BITMAP_FREE (get_varinfo (from)->oldsolution);
1430 if (stats.iterations > 0)
1432 BITMAP_FREE (get_varinfo (to)->oldsolution);
1433 get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1436 if (valid_graph_edge (graph, to, to))
1438 if (graph->succs[to])
1439 bitmap_clear_bit (graph->succs[to], to);
1443 /* Information needed to compute the topological ordering of a graph. */
1447 /* sbitmap of visited nodes. */
1449 /* Array that stores the topological order of the graph, *in
1451 VEC(unsigned,heap) *topo_order;
1455 /* Initialize and return a topological info structure. */
1457 static struct topo_info *
1458 init_topo_info (void)
1460 size_t size = graph->size;
1461 struct topo_info *ti = XNEW (struct topo_info);
1462 ti->visited = sbitmap_alloc (size);
1463 sbitmap_zero (ti->visited);
1464 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1469 /* Free the topological sort info pointed to by TI. */
1472 free_topo_info (struct topo_info *ti)
1474 sbitmap_free (ti->visited);
1475 VEC_free (unsigned, heap, ti->topo_order);
1479 /* Visit the graph in topological order, and store the order in the
1480 topo_info structure. */
1483 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1489 SET_BIT (ti->visited, n);
1491 if (graph->succs[n])
1492 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1494 if (!TEST_BIT (ti->visited, j))
1495 topo_visit (graph, ti, j);
1498 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1501 /* Process a constraint C that represents x = *(y + off), using DELTA as the
1502 starting solution for y. */
1505 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1508 unsigned int lhs = c->lhs.var;
1510 bitmap sol = get_varinfo (lhs)->solution;
1513 HOST_WIDE_INT roffset = c->rhs.offset;
1515 /* Our IL does not allow this. */
1516 gcc_assert (c->lhs.offset == 0);
1518 /* If the solution of Y contains anything it is good enough to transfer
1520 if (bitmap_bit_p (delta, anything_id))
1522 flag |= bitmap_set_bit (sol, anything_id);
1526 /* If we do not know at with offset the rhs is dereferenced compute
1527 the reachability set of DELTA, conservatively assuming it is
1528 dereferenced at all valid offsets. */
1529 if (roffset == UNKNOWN_OFFSET)
1531 solution_set_expand (delta, delta);
1532 /* No further offset processing is necessary. */
1536 /* For each variable j in delta (Sol(y)), add
1537 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1538 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1540 varinfo_t v = get_varinfo (j);
1541 HOST_WIDE_INT fieldoffset = v->offset + roffset;
1545 fieldoffset = v->offset;
1546 else if (roffset != 0)
1547 v = first_vi_for_offset (v, fieldoffset);
1548 /* If the access is outside of the variable we can ignore it. */
1556 /* Adding edges from the special vars is pointless.
1557 They don't have sets that can change. */
1558 if (get_varinfo (t)->is_special_var)
1559 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1560 /* Merging the solution from ESCAPED needlessly increases
1561 the set. Use ESCAPED as representative instead. */
1562 else if (v->id == escaped_id)
1563 flag |= bitmap_set_bit (sol, escaped_id);
1564 else if (add_graph_edge (graph, lhs, t))
1565 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1567 /* If the variable is not exactly at the requested offset
1568 we have to include the next one. */
1569 if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1574 fieldoffset = v->offset;
1580 /* If the LHS solution changed, mark the var as changed. */
1583 get_varinfo (lhs)->solution = sol;
1584 if (!TEST_BIT (changed, lhs))
1586 SET_BIT (changed, lhs);
1592 /* Process a constraint C that represents *(x + off) = y using DELTA
1593 as the starting solution for x. */
1596 do_ds_constraint (constraint_t c, bitmap delta)
1598 unsigned int rhs = c->rhs.var;
1599 bitmap sol = get_varinfo (rhs)->solution;
1602 HOST_WIDE_INT loff = c->lhs.offset;
1604 /* Our IL does not allow this. */
1605 gcc_assert (c->rhs.offset == 0);
1607 /* If the solution of y contains ANYTHING simply use the ANYTHING
1608 solution. This avoids needlessly increasing the points-to sets. */
1609 if (bitmap_bit_p (sol, anything_id))
1610 sol = get_varinfo (find (anything_id))->solution;
1612 /* If the solution for x contains ANYTHING we have to merge the
1613 solution of y into all pointer variables which we do via
1615 if (bitmap_bit_p (delta, anything_id))
1617 unsigned t = find (storedanything_id);
1618 if (add_graph_edge (graph, t, rhs))
1620 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1622 if (!TEST_BIT (changed, t))
1624 SET_BIT (changed, t);
1632 /* If we do not know at with offset the rhs is dereferenced compute
1633 the reachability set of DELTA, conservatively assuming it is
1634 dereferenced at all valid offsets. */
1635 if (loff == UNKNOWN_OFFSET)
1637 solution_set_expand (delta, delta);
1641 /* For each member j of delta (Sol(x)), add an edge from y to j and
1642 union Sol(y) into Sol(j) */
1643 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1645 varinfo_t v = get_varinfo (j);
1647 HOST_WIDE_INT fieldoffset = v->offset + loff;
1649 /* If v is a global variable then this is an escape point. */
1650 if (v->is_global_var)
1652 t = find (escaped_id);
1653 if (add_graph_edge (graph, t, rhs)
1654 && bitmap_ior_into (get_varinfo (t)->solution, sol)
1655 && !TEST_BIT (changed, t))
1657 SET_BIT (changed, t);
1662 if (v->is_special_var)
1666 fieldoffset = v->offset;
1668 v = first_vi_for_offset (v, fieldoffset);
1669 /* If the access is outside of the variable we can ignore it. */
1675 if (v->may_have_pointers)
1678 if (add_graph_edge (graph, t, rhs)
1679 && bitmap_ior_into (get_varinfo (t)->solution, sol)
1680 && !TEST_BIT (changed, t))
1682 SET_BIT (changed, t);
1687 /* If the variable is not exactly at the requested offset
1688 we have to include the next one. */
1689 if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
1694 fieldoffset = v->offset;
1700 /* Handle a non-simple (simple meaning requires no iteration),
1701 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1704 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1706 if (c->lhs.type == DEREF)
1708 if (c->rhs.type == ADDRESSOF)
1715 do_ds_constraint (c, delta);
1718 else if (c->rhs.type == DEREF)
1721 if (!(get_varinfo (c->lhs.var)->is_special_var))
1722 do_sd_constraint (graph, c, delta);
1730 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1731 solution = get_varinfo (c->rhs.var)->solution;
1732 tmp = get_varinfo (c->lhs.var)->solution;
1734 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1738 get_varinfo (c->lhs.var)->solution = tmp;
1739 if (!TEST_BIT (changed, c->lhs.var))
1741 SET_BIT (changed, c->lhs.var);
1748 /* Initialize and return a new SCC info structure. */
1750 static struct scc_info *
1751 init_scc_info (size_t size)
1753 struct scc_info *si = XNEW (struct scc_info);
1756 si->current_index = 0;
1757 si->visited = sbitmap_alloc (size);
1758 sbitmap_zero (si->visited);
1759 si->deleted = sbitmap_alloc (size);
1760 sbitmap_zero (si->deleted);
1761 si->node_mapping = XNEWVEC (unsigned int, size);
1762 si->dfs = XCNEWVEC (unsigned int, size);
1764 for (i = 0; i < size; i++)
1765 si->node_mapping[i] = i;
1767 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1771 /* Free an SCC info structure pointed to by SI */
1774 free_scc_info (struct scc_info *si)
1776 sbitmap_free (si->visited);
1777 sbitmap_free (si->deleted);
1778 free (si->node_mapping);
1780 VEC_free (unsigned, heap, si->scc_stack);
1785 /* Find indirect cycles in GRAPH that occur, using strongly connected
1786 components, and note them in the indirect cycles map.
1788 This technique comes from Ben Hardekopf and Calvin Lin,
1789 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1790 Lines of Code", submitted to PLDI 2007. */
1793 find_indirect_cycles (constraint_graph_t graph)
1796 unsigned int size = graph->size;
1797 struct scc_info *si = init_scc_info (size);
1799 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1800 if (!TEST_BIT (si->visited, i) && find (i) == i)
1801 scc_visit (graph, si, i);
1806 /* Compute a topological ordering for GRAPH, and store the result in the
1807 topo_info structure TI. */
1810 compute_topo_order (constraint_graph_t graph,
1811 struct topo_info *ti)
1814 unsigned int size = graph->size;
1816 for (i = 0; i != size; ++i)
1817 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1818 topo_visit (graph, ti, i);
1821 /* Structure used to for hash value numbering of pointer equivalence
1824 typedef struct equiv_class_label
1827 unsigned int equivalence_class;
1829 } *equiv_class_label_t;
1830 typedef const struct equiv_class_label *const_equiv_class_label_t;
1832 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1834 static htab_t pointer_equiv_class_table;
1836 /* A hashtable for mapping a bitmap of labels->location equivalence
1838 static htab_t location_equiv_class_table;
1840 /* Hash function for a equiv_class_label_t */
1843 equiv_class_label_hash (const void *p)
1845 const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
1846 return ecl->hashcode;
1849 /* Equality function for two equiv_class_label_t's. */
1852 equiv_class_label_eq (const void *p1, const void *p2)
1854 const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
1855 const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
1856 return (eql1->hashcode == eql2->hashcode
1857 && bitmap_equal_p (eql1->labels, eql2->labels));
1860 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
1864 equiv_class_lookup (htab_t table, bitmap labels)
1867 struct equiv_class_label ecl;
1869 ecl.labels = labels;
1870 ecl.hashcode = bitmap_hash (labels);
1872 slot = htab_find_slot_with_hash (table, &ecl,
1873 ecl.hashcode, NO_INSERT);
1877 return ((equiv_class_label_t) *slot)->equivalence_class;
1881 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
1885 equiv_class_add (htab_t table, unsigned int equivalence_class,
1889 equiv_class_label_t ecl = XNEW (struct equiv_class_label);
1891 ecl->labels = labels;
1892 ecl->equivalence_class = equivalence_class;
1893 ecl->hashcode = bitmap_hash (labels);
1895 slot = htab_find_slot_with_hash (table, ecl,
1896 ecl->hashcode, INSERT);
1897 gcc_assert (!*slot);
1898 *slot = (void *) ecl;
1901 /* Perform offline variable substitution.
1903 This is a worst case quadratic time way of identifying variables
1904 that must have equivalent points-to sets, including those caused by
1905 static cycles, and single entry subgraphs, in the constraint graph.
1907 The technique is described in "Exploiting Pointer and Location
1908 Equivalence to Optimize Pointer Analysis. In the 14th International
1909 Static Analysis Symposium (SAS), August 2007." It is known as the
1910 "HU" algorithm, and is equivalent to value numbering the collapsed
1911 constraint graph including evaluating unions.
1913 The general method of finding equivalence classes is as follows:
1914 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1915 Initialize all non-REF nodes to be direct nodes.
1916 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1918 For each constraint containing the dereference, we also do the same
1921 We then compute SCC's in the graph and unify nodes in the same SCC,
1924 For each non-collapsed node x:
1925 Visit all unvisited explicit incoming edges.
1926 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1928 Lookup the equivalence class for pts(x).
1929 If we found one, equivalence_class(x) = found class.
1930 Otherwise, equivalence_class(x) = new class, and new_class is
1931 added to the lookup table.
1933 All direct nodes with the same equivalence class can be replaced
1934 with a single representative node.
1935 All unlabeled nodes (label == 0) are not pointers and all edges
1936 involving them can be eliminated.
1937 We perform these optimizations during rewrite_constraints
1939 In addition to pointer equivalence class finding, we also perform
1940 location equivalence class finding. This is the set of variables
1941 that always appear together in points-to sets. We use this to
1942 compress the size of the points-to sets. */
1944 /* Current maximum pointer equivalence class id. */
1945 static int pointer_equiv_class;
1947 /* Current maximum location equivalence class id. */
1948 static int location_equiv_class;
1950 /* Recursive routine to find strongly connected components in GRAPH,
1951 and label it's nodes with DFS numbers. */
1954 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1958 unsigned int my_dfs;
1960 gcc_assert (si->node_mapping[n] == n);
1961 SET_BIT (si->visited, n);
1962 si->dfs[n] = si->current_index ++;
1963 my_dfs = si->dfs[n];
1965 /* Visit all the successors. */
1966 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1968 unsigned int w = si->node_mapping[i];
1970 if (TEST_BIT (si->deleted, w))
1973 if (!TEST_BIT (si->visited, w))
1974 condense_visit (graph, si, w);
1976 unsigned int t = si->node_mapping[w];
1977 unsigned int nnode = si->node_mapping[n];
1978 gcc_assert (nnode == n);
1980 if (si->dfs[t] < si->dfs[nnode])
1981 si->dfs[n] = si->dfs[t];
1985 /* Visit all the implicit predecessors. */
1986 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1988 unsigned int w = si->node_mapping[i];
1990 if (TEST_BIT (si->deleted, w))
1993 if (!TEST_BIT (si->visited, w))
1994 condense_visit (graph, si, w);
1996 unsigned int t = si->node_mapping[w];
1997 unsigned int nnode = si->node_mapping[n];
1998 gcc_assert (nnode == n);
2000 if (si->dfs[t] < si->dfs[nnode])
2001 si->dfs[n] = si->dfs[t];
2005 /* See if any components have been identified. */
2006 if (si->dfs[n] == my_dfs)
2008 while (VEC_length (unsigned, si->scc_stack) != 0
2009 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
2011 unsigned int w = VEC_pop (unsigned, si->scc_stack);
2012 si->node_mapping[w] = n;
2014 if (!TEST_BIT (graph->direct_nodes, w))
2015 RESET_BIT (graph->direct_nodes, n);
2017 /* Unify our nodes. */
2018 if (graph->preds[w])
2020 if (!graph->preds[n])
2021 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2022 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2024 if (graph->implicit_preds[w])
2026 if (!graph->implicit_preds[n])
2027 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2028 bitmap_ior_into (graph->implicit_preds[n],
2029 graph->implicit_preds[w]);
2031 if (graph->points_to[w])
2033 if (!graph->points_to[n])
2034 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2035 bitmap_ior_into (graph->points_to[n],
2036 graph->points_to[w]);
2039 SET_BIT (si->deleted, n);
2042 VEC_safe_push (unsigned, heap, si->scc_stack, n);
2045 /* Label pointer equivalences. */
2048 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2052 SET_BIT (si->visited, n);
2054 if (!graph->points_to[n])
2055 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2057 /* Label and union our incoming edges's points to sets. */
2058 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2060 unsigned int w = si->node_mapping[i];
2061 if (!TEST_BIT (si->visited, w))
2062 label_visit (graph, si, w);
2064 /* Skip unused edges */
2065 if (w == n || graph->pointer_label[w] == 0)
2068 if (graph->points_to[w])
2069 bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
2071 /* Indirect nodes get fresh variables. */
2072 if (!TEST_BIT (graph->direct_nodes, n))
2073 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2075 if (!bitmap_empty_p (graph->points_to[n]))
2077 unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
2078 graph->points_to[n]);
2081 label = pointer_equiv_class++;
2082 equiv_class_add (pointer_equiv_class_table,
2083 label, graph->points_to[n]);
2085 graph->pointer_label[n] = label;
2089 /* Perform offline variable substitution, discovering equivalence
2090 classes, and eliminating non-pointer variables. */
2092 static struct scc_info *
2093 perform_var_substitution (constraint_graph_t graph)
2096 unsigned int size = graph->size;
2097 struct scc_info *si = init_scc_info (size);
2099 bitmap_obstack_initialize (&iteration_obstack);
2100 pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
2101 equiv_class_label_eq, free);
2102 location_equiv_class_table = htab_create (511, equiv_class_label_hash,
2103 equiv_class_label_eq, free);
2104 pointer_equiv_class = 1;
2105 location_equiv_class = 1;
2107 /* Condense the nodes, which means to find SCC's, count incoming
2108 predecessors, and unite nodes in SCC's. */
2109 for (i = 0; i < FIRST_REF_NODE; i++)
2110 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2111 condense_visit (graph, si, si->node_mapping[i]);
2113 sbitmap_zero (si->visited);
2114 /* Actually the label the nodes for pointer equivalences */
2115 for (i = 0; i < FIRST_REF_NODE; i++)
2116 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2117 label_visit (graph, si, si->node_mapping[i]);
2119 /* Calculate location equivalence labels. */
2120 for (i = 0; i < FIRST_REF_NODE; i++)
2127 if (!graph->pointed_by[i])
2129 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2131 /* Translate the pointed-by mapping for pointer equivalence
2133 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2135 bitmap_set_bit (pointed_by,
2136 graph->pointer_label[si->node_mapping[j]]);
2138 /* The original pointed_by is now dead. */
2139 BITMAP_FREE (graph->pointed_by[i]);
2141 /* Look up the location equivalence label if one exists, or make
2143 label = equiv_class_lookup (location_equiv_class_table,
2147 label = location_equiv_class++;
2148 equiv_class_add (location_equiv_class_table,
2153 if (dump_file && (dump_flags & TDF_DETAILS))
2154 fprintf (dump_file, "Found location equivalence for node %s\n",
2155 get_varinfo (i)->name);
2156 BITMAP_FREE (pointed_by);
2158 graph->loc_label[i] = label;
2162 if (dump_file && (dump_flags & TDF_DETAILS))
2163 for (i = 0; i < FIRST_REF_NODE; i++)
2165 bool direct_node = TEST_BIT (graph->direct_nodes, i);
2167 "Equivalence classes for %s node id %d:%s are pointer: %d"
2169 direct_node ? "Direct node" : "Indirect node", i,
2170 get_varinfo (i)->name,
2171 graph->pointer_label[si->node_mapping[i]],
2172 graph->loc_label[si->node_mapping[i]]);
2175 /* Quickly eliminate our non-pointer variables. */
2177 for (i = 0; i < FIRST_REF_NODE; i++)
2179 unsigned int node = si->node_mapping[i];
2181 if (graph->pointer_label[node] == 0)
2183 if (dump_file && (dump_flags & TDF_DETAILS))
2185 "%s is a non-pointer variable, eliminating edges.\n",
2186 get_varinfo (node)->name);
2187 stats.nonpointer_vars++;
2188 clear_edges_for_node (graph, node);
2195 /* Free information that was only necessary for variable
2199 free_var_substitution_info (struct scc_info *si)
2202 free (graph->pointer_label);
2203 free (graph->loc_label);
2204 free (graph->pointed_by);
2205 free (graph->points_to);
2206 free (graph->eq_rep);
2207 sbitmap_free (graph->direct_nodes);
2208 htab_delete (pointer_equiv_class_table);
2209 htab_delete (location_equiv_class_table);
2210 bitmap_obstack_release (&iteration_obstack);
2213 /* Return an existing node that is equivalent to NODE, which has
2214 equivalence class LABEL, if one exists. Return NODE otherwise. */
2217 find_equivalent_node (constraint_graph_t graph,
2218 unsigned int node, unsigned int label)
2220 /* If the address version of this variable is unused, we can
2221 substitute it for anything else with the same label.
2222 Otherwise, we know the pointers are equivalent, but not the
2223 locations, and we can unite them later. */
2225 if (!bitmap_bit_p (graph->address_taken, node))
2227 gcc_assert (label < graph->size);
2229 if (graph->eq_rep[label] != -1)
2231 /* Unify the two variables since we know they are equivalent. */
2232 if (unite (graph->eq_rep[label], node))
2233 unify_nodes (graph, graph->eq_rep[label], node, false);
2234 return graph->eq_rep[label];
2238 graph->eq_rep[label] = node;
2239 graph->pe_rep[label] = node;
2244 gcc_assert (label < graph->size);
2245 graph->pe[node] = label;
2246 if (graph->pe_rep[label] == -1)
2247 graph->pe_rep[label] = node;
2253 /* Unite pointer equivalent but not location equivalent nodes in
2254 GRAPH. This may only be performed once variable substitution is
2258 unite_pointer_equivalences (constraint_graph_t graph)
2262 /* Go through the pointer equivalences and unite them to their
2263 representative, if they aren't already. */
2264 for (i = 0; i < FIRST_REF_NODE; i++)
2266 unsigned int label = graph->pe[i];
2269 int label_rep = graph->pe_rep[label];
2271 if (label_rep == -1)
2274 label_rep = find (label_rep);
2275 if (label_rep >= 0 && unite (label_rep, find (i)))
2276 unify_nodes (graph, label_rep, i, false);
2281 /* Move complex constraints to the GRAPH nodes they belong to. */
2284 move_complex_constraints (constraint_graph_t graph)
2289 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2293 struct constraint_expr lhs = c->lhs;
2294 struct constraint_expr rhs = c->rhs;
2296 if (lhs.type == DEREF)
2298 insert_into_complex (graph, lhs.var, c);
2300 else if (rhs.type == DEREF)
2302 if (!(get_varinfo (lhs.var)->is_special_var))
2303 insert_into_complex (graph, rhs.var, c);
2305 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2306 && (lhs.offset != 0 || rhs.offset != 0))
2308 insert_into_complex (graph, rhs.var, c);
2315 /* Optimize and rewrite complex constraints while performing
2316 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2317 result of perform_variable_substitution. */
2320 rewrite_constraints (constraint_graph_t graph,
2321 struct scc_info *si)
2327 for (j = 0; j < graph->size; j++)
2328 gcc_assert (find (j) == j);
2330 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2332 struct constraint_expr lhs = c->lhs;
2333 struct constraint_expr rhs = c->rhs;
2334 unsigned int lhsvar = find (lhs.var);
2335 unsigned int rhsvar = find (rhs.var);
2336 unsigned int lhsnode, rhsnode;
2337 unsigned int lhslabel, rhslabel;
2339 lhsnode = si->node_mapping[lhsvar];
2340 rhsnode = si->node_mapping[rhsvar];
2341 lhslabel = graph->pointer_label[lhsnode];
2342 rhslabel = graph->pointer_label[rhsnode];
2344 /* See if it is really a non-pointer variable, and if so, ignore
2348 if (dump_file && (dump_flags & TDF_DETAILS))
2351 fprintf (dump_file, "%s is a non-pointer variable,"
2352 "ignoring constraint:",
2353 get_varinfo (lhs.var)->name);
2354 dump_constraint (dump_file, c);
2356 VEC_replace (constraint_t, constraints, i, NULL);
2362 if (dump_file && (dump_flags & TDF_DETAILS))
2365 fprintf (dump_file, "%s is a non-pointer variable,"
2366 "ignoring constraint:",
2367 get_varinfo (rhs.var)->name);
2368 dump_constraint (dump_file, c);
2370 VEC_replace (constraint_t, constraints, i, NULL);
2374 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2375 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2376 c->lhs.var = lhsvar;
2377 c->rhs.var = rhsvar;
2382 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2383 part of an SCC, false otherwise. */
2386 eliminate_indirect_cycles (unsigned int node)
2388 if (graph->indirect_cycles[node] != -1
2389 && !bitmap_empty_p (get_varinfo (node)->solution))
2392 VEC(unsigned,heap) *queue = NULL;
2394 unsigned int to = find (graph->indirect_cycles[node]);
2397 /* We can't touch the solution set and call unify_nodes
2398 at the same time, because unify_nodes is going to do
2399 bitmap unions into it. */
2401 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2403 if (find (i) == i && i != to)
2406 VEC_safe_push (unsigned, heap, queue, i);
2411 VEC_iterate (unsigned, queue, queuepos, i);
2414 unify_nodes (graph, to, i, true);
2416 VEC_free (unsigned, heap, queue);
2422 /* Solve the constraint graph GRAPH using our worklist solver.
2423 This is based on the PW* family of solvers from the "Efficient Field
2424 Sensitive Pointer Analysis for C" paper.
2425 It works by iterating over all the graph nodes, processing the complex
2426 constraints and propagating the copy constraints, until everything stops
2427 changed. This corresponds to steps 6-8 in the solving list given above. */
2430 solve_graph (constraint_graph_t graph)
2432 unsigned int size = graph->size;
2437 changed = sbitmap_alloc (size);
2438 sbitmap_zero (changed);
2440 /* Mark all initial non-collapsed nodes as changed. */
2441 for (i = 0; i < size; i++)
2443 varinfo_t ivi = get_varinfo (i);
2444 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2445 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2446 || VEC_length (constraint_t, graph->complex[i]) > 0))
2448 SET_BIT (changed, i);
2453 /* Allocate a bitmap to be used to store the changed bits. */
2454 pts = BITMAP_ALLOC (&pta_obstack);
2456 while (changed_count > 0)
2459 struct topo_info *ti = init_topo_info ();
2462 bitmap_obstack_initialize (&iteration_obstack);
2464 compute_topo_order (graph, ti);
2466 while (VEC_length (unsigned, ti->topo_order) != 0)
2469 i = VEC_pop (unsigned, ti->topo_order);
2471 /* If this variable is not a representative, skip it. */
2475 /* In certain indirect cycle cases, we may merge this
2476 variable to another. */
2477 if (eliminate_indirect_cycles (i) && find (i) != i)
2480 /* If the node has changed, we need to process the
2481 complex constraints and outgoing edges again. */
2482 if (TEST_BIT (changed, i))
2487 VEC(constraint_t,heap) *complex = graph->complex[i];
2488 bool solution_empty;
2490 RESET_BIT (changed, i);
2493 /* Compute the changed set of solution bits. */
2494 bitmap_and_compl (pts, get_varinfo (i)->solution,
2495 get_varinfo (i)->oldsolution);
2497 if (bitmap_empty_p (pts))
2500 bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2502 solution = get_varinfo (i)->solution;
2503 solution_empty = bitmap_empty_p (solution);
2505 /* Process the complex constraints */
2506 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2508 /* XXX: This is going to unsort the constraints in
2509 some cases, which will occasionally add duplicate
2510 constraints during unification. This does not
2511 affect correctness. */
2512 c->lhs.var = find (c->lhs.var);
2513 c->rhs.var = find (c->rhs.var);
2515 /* The only complex constraint that can change our
2516 solution to non-empty, given an empty solution,
2517 is a constraint where the lhs side is receiving
2518 some set from elsewhere. */
2519 if (!solution_empty || c->lhs.type != DEREF)
2520 do_complex_constraint (graph, c, pts);
2523 solution_empty = bitmap_empty_p (solution);
2525 if (!solution_empty)
2528 unsigned eff_escaped_id = find (escaped_id);
2530 /* Propagate solution to all successors. */
2531 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2537 unsigned int to = find (j);
2538 tmp = get_varinfo (to)->solution;
2541 /* Don't try to propagate to ourselves. */
2545 /* If we propagate from ESCAPED use ESCAPED as
2547 if (i == eff_escaped_id)
2548 flag = bitmap_set_bit (tmp, escaped_id);
2550 flag = set_union_with_increment (tmp, pts, 0);
2554 get_varinfo (to)->solution = tmp;
2555 if (!TEST_BIT (changed, to))
2557 SET_BIT (changed, to);
2565 free_topo_info (ti);
2566 bitmap_obstack_release (&iteration_obstack);
2570 sbitmap_free (changed);
2571 bitmap_obstack_release (&oldpta_obstack);
2574 /* Map from trees to variable infos. */
2575 static struct pointer_map_t *vi_for_tree;
2578 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2581 insert_vi_for_tree (tree t, varinfo_t vi)
2583 void **slot = pointer_map_insert (vi_for_tree, t);
2585 gcc_assert (*slot == NULL);
2589 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2590 exist in the map, return NULL, otherwise, return the varinfo we found. */
2593 lookup_vi_for_tree (tree t)
2595 void **slot = pointer_map_contains (vi_for_tree, t);
2599 return (varinfo_t) *slot;
2602 /* Return a printable name for DECL */
2605 alias_get_name (tree decl)
2607 const char *res = get_name (decl);
2609 int num_printed = 0;
2618 if (TREE_CODE (decl) == SSA_NAME)
2620 num_printed = asprintf (&temp, "%s_%u",
2621 alias_get_name (SSA_NAME_VAR (decl)),
2622 SSA_NAME_VERSION (decl));
2624 else if (DECL_P (decl))
2626 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2628 if (num_printed > 0)
2630 res = ggc_strdup (temp);
2636 /* Find the variable id for tree T in the map.
2637 If T doesn't exist in the map, create an entry for it and return it. */
2640 get_vi_for_tree (tree t)
2642 void **slot = pointer_map_contains (vi_for_tree, t);
2644 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2646 return (varinfo_t) *slot;
2649 /* Get a scalar constraint expression for a new temporary variable. */
2651 static struct constraint_expr
2652 new_scalar_tmp_constraint_exp (const char *name)
2654 struct constraint_expr tmp;
2657 vi = new_var_info (NULL_TREE, name);
2661 vi->is_full_var = 1;
2670 /* Get a constraint expression vector from an SSA_VAR_P node.
2671 If address_p is true, the result will be taken its address of. */
2674 get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
2676 struct constraint_expr cexpr;
2679 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2680 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2682 /* For parameters, get at the points-to set for the actual parm
2684 if (TREE_CODE (t) == SSA_NAME
2685 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2686 && SSA_NAME_IS_DEFAULT_DEF (t))
2688 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2692 vi = get_vi_for_tree (t);
2694 cexpr.type = SCALAR;
2696 /* If we determine the result is "anything", and we know this is readonly,
2697 say it points to readonly memory instead. */
2698 if (cexpr.var == anything_id && TREE_READONLY (t))
2701 cexpr.type = ADDRESSOF;
2702 cexpr.var = readonly_id;
2705 /* If we are not taking the address of the constraint expr, add all
2706 sub-fiels of the variable as well. */
2709 for (; vi; vi = vi->next)
2712 VEC_safe_push (ce_s, heap, *results, &cexpr);
2717 VEC_safe_push (ce_s, heap, *results, &cexpr);
2720 /* Process constraint T, performing various simplifications and then
2721 adding it to our list of overall constraints. */
2724 process_constraint (constraint_t t)
2726 struct constraint_expr rhs = t->rhs;
2727 struct constraint_expr lhs = t->lhs;
2729 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2730 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2732 /* If we didn't get any useful constraint from the lhs we get
2733 &ANYTHING as fallback from get_constraint_for. Deal with
2734 it here by turning it into *ANYTHING. */
2735 if (lhs.type == ADDRESSOF
2736 && lhs.var == anything_id)
2739 /* ADDRESSOF on the lhs is invalid. */
2740 gcc_assert (lhs.type != ADDRESSOF);
2742 /* This can happen in our IR with things like n->a = *p */
2743 if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2745 /* Split into tmp = *rhs, *lhs = tmp */
2746 struct constraint_expr tmplhs;
2747 tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp");
2748 process_constraint (new_constraint (tmplhs, rhs));
2749 process_constraint (new_constraint (lhs, tmplhs));
2751 else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
2753 /* Split into tmp = &rhs, *lhs = tmp */
2754 struct constraint_expr tmplhs;
2755 tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp");
2756 process_constraint (new_constraint (tmplhs, rhs));
2757 process_constraint (new_constraint (lhs, tmplhs));
2761 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2762 VEC_safe_push (constraint_t, heap, constraints, t);
2766 /* Return true if T is a type that could contain pointers. */
2769 type_could_have_pointers (tree type)
2771 if (POINTER_TYPE_P (type))
2774 if (TREE_CODE (type) == ARRAY_TYPE)
2775 return type_could_have_pointers (TREE_TYPE (type));
2777 return AGGREGATE_TYPE_P (type);
2780 /* Return true if T is a variable of a type that could contain
2784 could_have_pointers (tree t)
2786 return type_could_have_pointers (TREE_TYPE (t));
2789 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2792 static HOST_WIDE_INT
2793 bitpos_of_field (const tree fdecl)
2796 if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2797 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2800 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2801 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2805 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2806 resulting constraint expressions in *RESULTS. */
2809 get_constraint_for_ptr_offset (tree ptr, tree offset,
2810 VEC (ce_s, heap) **results)
2812 struct constraint_expr *c;
2814 HOST_WIDE_INT rhsunitoffset, rhsoffset;
2816 /* If we do not do field-sensitive PTA adding offsets to pointers
2817 does not change the points-to solution. */
2818 if (!use_field_sensitive)
2820 get_constraint_for (ptr, results);
2824 /* If the offset is not a non-negative integer constant that fits
2825 in a HOST_WIDE_INT, we have to fall back to a conservative
2826 solution which includes all sub-fields of all pointed-to
2827 variables of ptr. */
2828 if (offset == NULL_TREE
2829 || !host_integerp (offset, 0))
2830 rhsoffset = UNKNOWN_OFFSET;
2833 /* Make sure the bit-offset also fits. */
2834 rhsunitoffset = TREE_INT_CST_LOW (offset);
2835 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
2836 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
2837 rhsoffset = UNKNOWN_OFFSET;
2840 get_constraint_for (ptr, results);
2844 /* As we are eventually appending to the solution do not use
2845 VEC_iterate here. */
2846 n = VEC_length (ce_s, *results);
2847 for (j = 0; j < n; j++)
2850 c = VEC_index (ce_s, *results, j);
2851 curr = get_varinfo (c->var);
2853 if (c->type == ADDRESSOF
2854 /* If this varinfo represents a full variable just use it. */
2855 && curr->is_full_var)
2857 else if (c->type == ADDRESSOF
2858 /* If we do not know the offset add all subfields. */
2859 && rhsoffset == UNKNOWN_OFFSET)
2861 varinfo_t temp = lookup_vi_for_tree (curr->decl);
2864 struct constraint_expr c2;
2866 c2.type = ADDRESSOF;
2868 if (c2.var != c->var)
2869 VEC_safe_push (ce_s, heap, *results, &c2);
2874 else if (c->type == ADDRESSOF)
2877 unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
2879 /* Search the sub-field which overlaps with the
2880 pointed-to offset. If the result is outside of the variable
2881 we have to provide a conservative result, as the variable is
2882 still reachable from the resulting pointer (even though it
2883 technically cannot point to anything). The last and first
2884 sub-fields are such conservative results.
2885 ??? If we always had a sub-field for &object + 1 then
2886 we could represent this in a more precise way. */
2888 && curr->offset < offset)
2890 temp = first_or_preceding_vi_for_offset (curr, offset);
2892 /* If the found variable is not exactly at the pointed to
2893 result, we have to include the next variable in the
2894 solution as well. Otherwise two increments by offset / 2
2895 do not result in the same or a conservative superset
2897 if (temp->offset != offset
2898 && temp->next != NULL)
2900 struct constraint_expr c2;
2901 c2.var = temp->next->id;
2902 c2.type = ADDRESSOF;
2904 VEC_safe_push (ce_s, heap, *results, &c2);
2910 c->offset = rhsoffset;
2915 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
2916 If address_p is true the result will be taken its address of. */
2919 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
2923 HOST_WIDE_INT bitsize = -1;
2924 HOST_WIDE_INT bitmaxsize = -1;
2925 HOST_WIDE_INT bitpos;
2927 struct constraint_expr *result;
2929 /* Some people like to do cute things like take the address of
2932 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2933 forzero = TREE_OPERAND (forzero, 0);
2935 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2937 struct constraint_expr temp;
2940 temp.var = integer_id;
2942 VEC_safe_push (ce_s, heap, *results, &temp);
2946 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2948 /* Pretend to take the address of the base, we'll take care of
2949 adding the required subset of sub-fields below. */
2950 get_constraint_for_1 (t, results, true);
2951 gcc_assert (VEC_length (ce_s, *results) == 1);
2952 result = VEC_last (ce_s, *results);
2954 if (result->type == SCALAR
2955 && get_varinfo (result->var)->is_full_var)
2956 /* For single-field vars do not bother about the offset. */
2958 else if (result->type == SCALAR)
2960 /* In languages like C, you can access one past the end of an
2961 array. You aren't allowed to dereference it, so we can
2962 ignore this constraint. When we handle pointer subtraction,
2963 we may have to do something cute here. */
2965 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
2968 /* It's also not true that the constraint will actually start at the
2969 right offset, it may start in some padding. We only care about
2970 setting the constraint to the first actual field it touches, so
2972 struct constraint_expr cexpr = *result;
2974 VEC_pop (ce_s, *results);
2976 for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
2978 if (ranges_overlap_p (curr->offset, curr->size,
2979 bitpos, bitmaxsize))
2981 cexpr.var = curr->id;
2982 VEC_safe_push (ce_s, heap, *results, &cexpr);
2987 /* If we are going to take the address of this field then
2988 to be able to compute reachability correctly add at least
2989 the last field of the variable. */
2991 && VEC_length (ce_s, *results) == 0)
2993 curr = get_varinfo (cexpr.var);
2994 while (curr->next != NULL)
2996 cexpr.var = curr->id;
2997 VEC_safe_push (ce_s, heap, *results, &cexpr);
3000 /* Assert that we found *some* field there. The user couldn't be
3001 accessing *only* padding. */
3002 /* Still the user could access one past the end of an array
3003 embedded in a struct resulting in accessing *only* padding. */
3004 gcc_assert (VEC_length (ce_s, *results) >= 1
3005 || ref_contains_array_ref (orig_t));
3007 else if (bitmaxsize == 0)
3009 if (dump_file && (dump_flags & TDF_DETAILS))
3010 fprintf (dump_file, "Access to zero-sized part of variable,"
3014 if (dump_file && (dump_flags & TDF_DETAILS))
3015 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3017 else if (result->type == DEREF)
3019 /* If we do not know exactly where the access goes say so. Note
3020 that only for non-structure accesses we know that we access
3021 at most one subfiled of any variable. */
3023 || bitsize != bitmaxsize
3024 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t)))
3025 result->offset = UNKNOWN_OFFSET;
3027 result->offset = bitpos;
3029 else if (result->type == ADDRESSOF)
3031 /* We can end up here for component references on a
3032 VIEW_CONVERT_EXPR <>(&foobar). */
3033 result->type = SCALAR;
3034 result->var = anything_id;
3042 /* Dereference the constraint expression CONS, and return the result.
3043 DEREF (ADDRESSOF) = SCALAR
3044 DEREF (SCALAR) = DEREF
3045 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3046 This is needed so that we can handle dereferencing DEREF constraints. */
3049 do_deref (VEC (ce_s, heap) **constraints)
3051 struct constraint_expr *c;
3054 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
3056 if (c->type == SCALAR)
3058 else if (c->type == ADDRESSOF)
3060 else if (c->type == DEREF)
3062 struct constraint_expr tmplhs;
3063 tmplhs = new_scalar_tmp_constraint_exp ("dereftmp");
3064 process_constraint (new_constraint (tmplhs, *c));
3065 c->var = tmplhs.var;
3072 static void get_constraint_for_1 (tree, VEC (ce_s, heap) **, bool);
3074 /* Given a tree T, return the constraint expression for taking the
3078 get_constraint_for_address_of (tree t, VEC (ce_s, heap) **results)
3080 struct constraint_expr *c;
3083 get_constraint_for_1 (t, results, true);
3085 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3087 if (c->type == DEREF)
3090 c->type = ADDRESSOF;
3094 /* Given a tree T, return the constraint expression for it. */
3097 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
3099 struct constraint_expr temp;
3101 /* x = integer is all glommed to a single variable, which doesn't
3102 point to anything by itself. That is, of course, unless it is an
3103 integer constant being treated as a pointer, in which case, we
3104 will return that this is really the addressof anything. This
3105 happens below, since it will fall into the default case. The only
3106 case we know something about an integer treated like a pointer is
3107 when it is the NULL pointer, and then we just say it points to
3110 Do not do that if -fno-delete-null-pointer-checks though, because
3111 in that case *NULL does not fail, so it _should_ alias *anything.
3112 It is not worth adding a new option or renaming the existing one,
3113 since this case is relatively obscure. */
3114 if (flag_delete_null_pointer_checks
3115 && ((TREE_CODE (t) == INTEGER_CST
3116 && integer_zerop (t))
3117 /* The only valid CONSTRUCTORs in gimple with pointer typed
3118 elements are zero-initializer. */
3119 || TREE_CODE (t) == CONSTRUCTOR))
3121 temp.var = nothing_id;
3122 temp.type = ADDRESSOF;
3124 VEC_safe_push (ce_s, heap, *results, &temp);
3128 /* String constants are read-only. */
3129 if (TREE_CODE (t) == STRING_CST)
3131 temp.var = readonly_id;
3134 VEC_safe_push (ce_s, heap, *results, &temp);
3138 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3140 case tcc_expression:
3142 switch (TREE_CODE (t))
3145 get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3153 switch (TREE_CODE (t))
3157 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3162 case ARRAY_RANGE_REF:
3164 get_constraint_for_component_ref (t, results, address_p);
3166 case VIEW_CONVERT_EXPR:
3167 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3169 /* We are missing handling for TARGET_MEM_REF here. */
3174 case tcc_exceptional:
3176 switch (TREE_CODE (t))
3180 get_constraint_for_ssa_var (t, results, address_p);
3187 case tcc_declaration:
3189 get_constraint_for_ssa_var (t, results, address_p);
3195 /* The default fallback is a constraint from anything. */
3196 temp.type = ADDRESSOF;
3197 temp.var = anything_id;
3199 VEC_safe_push (ce_s, heap, *results, &temp);
3202 /* Given a gimple tree T, return the constraint expression vector for it. */
3205 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3207 gcc_assert (VEC_length (ce_s, *results) == 0);
3209 get_constraint_for_1 (t, results, false);
3213 /* Efficiently generates constraints from all entries in *RHSC to all
3214 entries in *LHSC. */
3217 process_all_all_constraints (VEC (ce_s, heap) *lhsc, VEC (ce_s, heap) *rhsc)
3219 struct constraint_expr *lhsp, *rhsp;
3222 if (VEC_length (ce_s, lhsc) <= 1
3223 || VEC_length (ce_s, rhsc) <= 1)
3225 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3226 for (j = 0; VEC_iterate (ce_s, rhsc, j, rhsp); ++j)
3227 process_constraint (new_constraint (*lhsp, *rhsp));
3231 struct constraint_expr tmp;
3232 tmp = new_scalar_tmp_constraint_exp ("allalltmp");
3233 for (i = 0; VEC_iterate (ce_s, rhsc, i, rhsp); ++i)
3234 process_constraint (new_constraint (tmp, *rhsp));
3235 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3236 process_constraint (new_constraint (*lhsp, tmp));
3240 /* Handle aggregate copies by expanding into copies of the respective
3241 fields of the structures. */
3244 do_structure_copy (tree lhsop, tree rhsop)
3246 struct constraint_expr *lhsp, *rhsp;
3247 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3250 get_constraint_for (lhsop, &lhsc);
3251 get_constraint_for (rhsop, &rhsc);
3252 lhsp = VEC_index (ce_s, lhsc, 0);
3253 rhsp = VEC_index (ce_s, rhsc, 0);
3254 if (lhsp->type == DEREF
3255 || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3256 || rhsp->type == DEREF)
3257 process_all_all_constraints (lhsc, rhsc);
3258 else if (lhsp->type == SCALAR
3259 && (rhsp->type == SCALAR
3260 || rhsp->type == ADDRESSOF))
3262 tree lhsbase, rhsbase;
3263 HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
3264 HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
3266 lhsbase = get_ref_base_and_extent (lhsop, &lhsoffset,
3267 &lhssize, &lhsmaxsize);
3268 rhsbase = get_ref_base_and_extent (rhsop, &rhsoffset,
3269 &rhssize, &rhsmaxsize);
3270 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp);)
3272 varinfo_t lhsv, rhsv;
3273 rhsp = VEC_index (ce_s, rhsc, k);
3274 lhsv = get_varinfo (lhsp->var);
3275 rhsv = get_varinfo (rhsp->var);
3276 if (lhsv->may_have_pointers
3277 && ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3278 rhsv->offset + lhsoffset, rhsv->size))
3279 process_constraint (new_constraint (*lhsp, *rhsp));
3280 if (lhsv->offset + rhsoffset + lhsv->size
3281 > rhsv->offset + lhsoffset + rhsv->size)
3284 if (k >= VEC_length (ce_s, rhsc))
3294 VEC_free (ce_s, heap, lhsc);
3295 VEC_free (ce_s, heap, rhsc);
3298 /* Create a constraint ID = OP. */
3301 make_constraint_to (unsigned id, tree op)
3303 VEC(ce_s, heap) *rhsc = NULL;
3304 struct constraint_expr *c;
3305 struct constraint_expr includes;
3309 includes.offset = 0;
3310 includes.type = SCALAR;
3312 get_constraint_for (op, &rhsc);
3313 for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3314 process_constraint (new_constraint (includes, *c));
3315 VEC_free (ce_s, heap, rhsc);
3318 /* Create a constraint ID = &FROM. */
3321 make_constraint_from (varinfo_t vi, int from)
3323 struct constraint_expr lhs, rhs;
3331 rhs.type = ADDRESSOF;
3332 process_constraint (new_constraint (lhs, rhs));
3335 /* Create a constraint ID = FROM. */
3338 make_copy_constraint (varinfo_t vi, int from)
3340 struct constraint_expr lhs, rhs;
3349 process_constraint (new_constraint (lhs, rhs));
3352 /* Make constraints necessary to make OP escape. */
3355 make_escape_constraint (tree op)
3357 make_constraint_to (escaped_id, op);
3360 /* Create a new artificial heap variable with NAME and make a
3361 constraint from it to LHS. Return the created variable. */
3364 make_constraint_from_heapvar (varinfo_t lhs, const char *name)
3367 tree heapvar = heapvar_lookup (lhs->decl);
3369 if (heapvar == NULL_TREE)
3372 heapvar = create_tmp_var_raw (ptr_type_node, name);
3373 DECL_EXTERNAL (heapvar) = 1;
3375 heapvar_insert (lhs->decl, heapvar);
3377 ann = get_var_ann (heapvar);
3378 ann->is_heapvar = 1;
3381 /* For global vars we need to add a heapvar to the list of referenced
3382 vars of a different function than it was created for originally. */
3383 if (gimple_referenced_vars (cfun))
3384 add_referenced_var (heapvar);
3386 vi = new_var_info (heapvar, name);
3387 vi->is_artificial_var = true;
3388 vi->is_heap_var = true;
3389 vi->is_unknown_size_var = true;
3392 vi->is_full_var = true;
3393 insert_vi_for_tree (heapvar, vi);
3395 make_constraint_from (lhs, vi->id);
3400 /* Create a new artificial heap variable with NAME and make a
3401 constraint from it to LHS. Set flags according to a tag used
3402 for tracking restrict pointers. */
3405 make_constraint_from_restrict (varinfo_t lhs, const char *name)
3408 vi = make_constraint_from_heapvar (lhs, name);
3409 vi->is_restrict_var = 1;
3410 vi->is_global_var = 0;
3411 vi->is_special_var = 1;
3412 vi->may_have_pointers = 0;
3415 /* For non-IPA mode, generate constraints necessary for a call on the
3419 handle_rhs_call (gimple stmt, VEC(ce_s, heap) **results)
3421 struct constraint_expr rhsc;
3424 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3426 tree arg = gimple_call_arg (stmt, i);
3428 /* Find those pointers being passed, and make sure they end up
3429 pointing to anything. */
3430 if (could_have_pointers (arg))
3431 make_escape_constraint (arg);
3434 /* The static chain escapes as well. */
3435 if (gimple_call_chain (stmt))
3436 make_escape_constraint (gimple_call_chain (stmt));
3438 /* And if we applied NRV the address of the return slot escapes as well. */
3439 if (gimple_call_return_slot_opt_p (stmt)
3440 && gimple_call_lhs (stmt) != NULL_TREE
3441 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
3443 VEC(ce_s, heap) *tmpc = NULL;
3444 struct constraint_expr lhsc, *c;
3445 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
3446 lhsc.var = escaped_id;
3449 for (i = 0; VEC_iterate (ce_s, tmpc, i, c); ++i)
3450 process_constraint (new_constraint (lhsc, *c));
3451 VEC_free(ce_s, heap, tmpc);
3454 /* Regular functions return nonlocal memory. */
3455 rhsc.var = nonlocal_id;
3458 VEC_safe_push (ce_s, heap, *results, &rhsc);
3461 /* For non-IPA mode, generate constraints necessary for a call
3462 that returns a pointer and assigns it to LHS. This simply makes
3463 the LHS point to global and escaped variables. */
3466 handle_lhs_call (tree lhs, int flags, VEC(ce_s, heap) *rhsc)
3468 VEC(ce_s, heap) *lhsc = NULL;
3470 get_constraint_for (lhs, &lhsc);
3472 if (flags & ECF_MALLOC)
3475 vi = make_constraint_from_heapvar (get_vi_for_tree (lhs), "HEAP");
3476 /* We delay marking allocated storage global until we know if
3478 DECL_EXTERNAL (vi->decl) = 0;
3479 vi->is_global_var = 0;
3481 else if (VEC_length (ce_s, rhsc) > 0)
3483 /* If the store is to a global decl make sure to
3484 add proper escape constraints. */
3485 lhs = get_base_address (lhs);
3488 && is_global_var (lhs))
3490 struct constraint_expr tmpc;
3491 tmpc.var = escaped_id;
3494 VEC_safe_push (ce_s, heap, lhsc, &tmpc);
3496 process_all_all_constraints (lhsc, rhsc);
3498 VEC_free (ce_s, heap, lhsc);
3501 /* For non-IPA mode, generate constraints necessary for a call of a
3502 const function that returns a pointer in the statement STMT. */
3505 handle_const_call (gimple stmt, VEC(ce_s, heap) **results)
3507 struct constraint_expr rhsc;
3510 /* Treat nested const functions the same as pure functions as far
3511 as the static chain is concerned. */
3512 if (gimple_call_chain (stmt))
3514 make_constraint_to (callused_id, gimple_call_chain (stmt));
3515 rhsc.var = callused_id;
3518 VEC_safe_push (ce_s, heap, *results, &rhsc);
3521 /* May return arguments. */
3522 for (k = 0; k < gimple_call_num_args (stmt); ++k)
3524 tree arg = gimple_call_arg (stmt, k);
3526 if (could_have_pointers (arg))
3528 VEC(ce_s, heap) *argc = NULL;
3530 struct constraint_expr *argp;
3531 get_constraint_for (arg, &argc);
3532 for (i = 0; VEC_iterate (ce_s, argc, i, argp); ++i)
3533 VEC_safe_push (ce_s, heap, *results, argp);
3534 VEC_free(ce_s, heap, argc);
3538 /* May return addresses of globals. */
3539 rhsc.var = nonlocal_id;
3541 rhsc.type = ADDRESSOF;
3542 VEC_safe_push (ce_s, heap, *results, &rhsc);
3545 /* For non-IPA mode, generate constraints necessary for a call to a
3546 pure function in statement STMT. */
3549 handle_pure_call (gimple stmt, VEC(ce_s, heap) **results)
3551 struct constraint_expr rhsc;
3553 bool need_callused = false;
3555 /* Memory reached from pointer arguments is call-used. */
3556 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3558 tree arg = gimple_call_arg (stmt, i);
3560 if (could_have_pointers (arg))
3562 make_constraint_to (callused_id, arg);
3563 need_callused = true;
3567 /* The static chain is used as well. */
3568 if (gimple_call_chain (stmt))
3570 make_constraint_to (callused_id, gimple_call_chain (stmt));
3571 need_callused = true;
3574 /* Pure functions may return callused and nonlocal memory. */
3577 rhsc.var = callused_id;
3580 VEC_safe_push (ce_s, heap, *results, &rhsc);
3582 rhsc.var = nonlocal_id;
3585 VEC_safe_push (ce_s, heap, *results, &rhsc);
3588 /* Walk statement T setting up aliasing constraints according to the
3589 references found in T. This function is the main part of the
3590 constraint builder. AI points to auxiliary alias information used
3591 when building alias sets and computing alias grouping heuristics. */
3594 find_func_aliases (gimple origt)
3597 VEC(ce_s, heap) *lhsc = NULL;
3598 VEC(ce_s, heap) *rhsc = NULL;
3599 struct constraint_expr *c;
3601 /* Now build constraints expressions. */
3602 if (gimple_code (t) == GIMPLE_PHI)
3604 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (gimple_phi_result (t))));
3606 /* Only care about pointers and structures containing
3608 if (could_have_pointers (gimple_phi_result (t)))
3613 /* For a phi node, assign all the arguments to
3615 get_constraint_for (gimple_phi_result (t), &lhsc);
3616 for (i = 0; i < gimple_phi_num_args (t); i++)
3619 tree strippedrhs = PHI_ARG_DEF (t, i);
3621 STRIP_NOPS (strippedrhs);
3622 rhstype = TREE_TYPE (strippedrhs);
3623 get_constraint_for (gimple_phi_arg_def (t, i), &rhsc);
3625 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3627 struct constraint_expr *c2;
3628 while (VEC_length (ce_s, rhsc) > 0)
3630 c2 = VEC_last (ce_s, rhsc);
3631 process_constraint (new_constraint (*c, *c2));
3632 VEC_pop (ce_s, rhsc);
3638 /* In IPA mode, we need to generate constraints to pass call
3639 arguments through their calls. There are two cases,
3640 either a GIMPLE_CALL returning a value, or just a plain
3641 GIMPLE_CALL when we are not.
3643 In non-ipa mode, we need to generate constraints for each
3644 pointer passed by address. */
3645 else if (is_gimple_call (t))
3648 if ((fndecl = gimple_call_fndecl (t)) != NULL_TREE
3649 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
3650 /* ??? All builtins that are handled here need to be handled
3651 in the alias-oracle query functions explicitly! */
3652 switch (DECL_FUNCTION_CODE (fndecl))
3654 /* All the following functions return a pointer to the same object
3655 as their first argument points to. The functions do not add
3656 to the ESCAPED solution. The functions make the first argument
3657 pointed to memory point to what the second argument pointed to
3658 memory points to. */
3659 case BUILT_IN_STRCPY:
3660 case BUILT_IN_STRNCPY:
3661 case BUILT_IN_BCOPY:
3662 case BUILT_IN_MEMCPY:
3663 case BUILT_IN_MEMMOVE:
3664 case BUILT_IN_MEMPCPY:
3665 case BUILT_IN_STPCPY:
3666 case BUILT_IN_STPNCPY:
3667 case BUILT_IN_STRCAT:
3668 case BUILT_IN_STRNCAT:
3670 tree res = gimple_call_lhs (t);
3671 tree dest = gimple_call_arg (t, 0);
3672 tree src = gimple_call_arg (t, 1);
3673 if (res != NULL_TREE)
3675 get_constraint_for (res, &lhsc);
3676 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
3677 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
3678 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY)
3679 get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
3681 get_constraint_for (dest, &rhsc);
3682 process_all_all_constraints (lhsc, rhsc);
3683 VEC_free (ce_s, heap, lhsc);
3684 VEC_free (ce_s, heap, rhsc);
3686 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
3687 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
3690 process_all_all_constraints (lhsc, rhsc);
3691 VEC_free (ce_s, heap, lhsc);
3692 VEC_free (ce_s, heap, rhsc);
3695 case BUILT_IN_MEMSET:
3697 tree res = gimple_call_lhs (t);
3698 tree dest = gimple_call_arg (t, 0);
3701 struct constraint_expr ac;
3702 if (res != NULL_TREE)
3704 get_constraint_for (res, &lhsc);
3705 get_constraint_for (dest, &rhsc);
3706 process_all_all_constraints (lhsc, rhsc);
3707 VEC_free (ce_s, heap, lhsc);
3708 VEC_free (ce_s, heap, rhsc);
3710 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
3712 if (flag_delete_null_pointer_checks
3713 && integer_zerop (gimple_call_arg (t, 1)))
3715 ac.type = ADDRESSOF;
3716 ac.var = nothing_id;
3721 ac.var = integer_id;
3724 for (i = 0; VEC_iterate (ce_s, lhsc, i, lhsp); ++i)
3725 process_constraint (new_constraint (*lhsp, ac));
3726 VEC_free (ce_s, heap, lhsc);
3729 /* All the following functions do not return pointers, do not
3730 modify the points-to sets of memory reachable from their
3731 arguments and do not add to the ESCAPED solution. */
3732 case BUILT_IN_SINCOS:
3733 case BUILT_IN_SINCOSF:
3734 case BUILT_IN_SINCOSL:
3735 case BUILT_IN_FREXP:
3736 case BUILT_IN_FREXPF:
3737 case BUILT_IN_FREXPL:
3738 case BUILT_IN_GAMMA_R:
3739 case BUILT_IN_GAMMAF_R:
3740 case BUILT_IN_GAMMAL_R:
3741 case BUILT_IN_LGAMMA_R:
3742 case BUILT_IN_LGAMMAF_R:
3743 case BUILT_IN_LGAMMAL_R:
3745 case BUILT_IN_MODFF:
3746 case BUILT_IN_MODFL:
3747 case BUILT_IN_REMQUO:
3748 case BUILT_IN_REMQUOF:
3749 case BUILT_IN_REMQUOL:
3752 /* printf-style functions may have hooks to set pointers to
3753 point to somewhere into the generated string. Leave them
3754 for a later excercise... */
3756 /* Fallthru to general call handling. */;
3760 VEC(ce_s, heap) *rhsc = NULL;
3761 int flags = gimple_call_flags (t);
3763 /* Const functions can return their arguments and addresses
3764 of global memory but not of escaped memory. */
3765 if (flags & (ECF_CONST|ECF_NOVOPS))
3767 if (gimple_call_lhs (t)
3768 && could_have_pointers (gimple_call_lhs (t)))
3769 handle_const_call (t, &rhsc);
3771 /* Pure functions can return addresses in and of memory
3772 reachable from their arguments, but they are not an escape
3773 point for reachable memory of their arguments. */
3774 else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE))
3775 handle_pure_call (t, &rhsc);
3777 handle_rhs_call (t, &rhsc);
3778 if (gimple_call_lhs (t)
3779 && could_have_pointers (gimple_call_lhs (t)))
3780 handle_lhs_call (gimple_call_lhs (t), flags, rhsc);
3781 VEC_free (ce_s, heap, rhsc);
3791 lhsop = gimple_call_lhs (t);
3792 decl = gimple_call_fndecl (t);
3794 /* If we can directly resolve the function being called, do so.
3795 Otherwise, it must be some sort of indirect expression that
3796 we should still be able to handle. */
3798 fi = get_vi_for_tree (decl);
3801 decl = gimple_call_fn (t);
3802 fi = get_vi_for_tree (decl);
3805 /* Assign all the passed arguments to the appropriate incoming
3806 parameters of the function. */
3807 for (j = 0; j < gimple_call_num_args (t); j++)
3809 struct constraint_expr lhs ;
3810 struct constraint_expr *rhsp;
3811 tree arg = gimple_call_arg (t, j);
3813 get_constraint_for (arg, &rhsc);
3814 if (TREE_CODE (decl) != FUNCTION_DECL)
3823 lhs.var = first_vi_for_offset (fi, i)->id;
3826 while (VEC_length (ce_s, rhsc) != 0)
3828 rhsp = VEC_last (ce_s, rhsc);
3829 process_constraint (new_constraint (lhs, *rhsp));
3830 VEC_pop (ce_s, rhsc);
3835 /* If we are returning a value, assign it to the result. */
3838 struct constraint_expr rhs;
3839 struct constraint_expr *lhsp;
3842 get_constraint_for (lhsop, &lhsc);
3843 if (TREE_CODE (decl) != FUNCTION_DECL)
3852 rhs.var = first_vi_for_offset (fi, i)->id;
3855 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3856 process_constraint (new_constraint (*lhsp, rhs));
3860 /* Otherwise, just a regular assignment statement. Only care about
3861 operations with pointer result, others are dealt with as escape
3862 points if they have pointer operands. */
3863 else if (is_gimple_assign (t)
3864 && could_have_pointers (gimple_assign_lhs (t)))
3866 /* Otherwise, just a regular assignment statement. */
3867 tree lhsop = gimple_assign_lhs (t);
3868 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
3870 if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
3871 do_structure_copy (lhsop, rhsop);
3874 struct constraint_expr temp;
3875 get_constraint_for (lhsop, &lhsc);
3877 if (gimple_assign_rhs_code (t) == POINTER_PLUS_EXPR)
3878 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
3879 gimple_assign_rhs2 (t), &rhsc);
3880 else if ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
3881 && !(POINTER_TYPE_P (gimple_expr_type (t))
3882 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
3883 || gimple_assign_single_p (t))
3884 get_constraint_for (rhsop, &rhsc);
3887 temp.type = ADDRESSOF;
3888 temp.var = anything_id;
3890 VEC_safe_push (ce_s, heap, rhsc, &temp);
3892 process_all_all_constraints (lhsc, rhsc);
3894 /* If there is a store to a global variable the rhs escapes. */
3895 if ((lhsop = get_base_address (lhsop)) != NULL_TREE
3897 && is_global_var (lhsop))
3898 make_escape_constraint (rhsop);
3899 /* If this is a conversion of a non-restrict pointer to a
3900 restrict pointer track it with a new heapvar. */
3901 else if (gimple_assign_cast_p (t)
3902 && POINTER_TYPE_P (TREE_TYPE (rhsop))
3903 && POINTER_TYPE_P (TREE_TYPE (lhsop))
3904 && !TYPE_RESTRICT (TREE_TYPE (rhsop))
3905 && TYPE_RESTRICT (TREE_TYPE (lhsop)))
3906 make_constraint_from_restrict (get_vi_for_tree (lhsop),
3909 /* For conversions of pointers to non-pointers the pointer escapes. */
3910 else if (gimple_assign_cast_p (t)
3911 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (t)))
3912 && !POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (t))))
3914 make_escape_constraint (gimple_assign_rhs1 (t));
3916 /* Handle escapes through return. */
3917 else if (gimple_code (t) == GIMPLE_RETURN
3918 && gimple_return_retval (t) != NULL_TREE
3919 && could_have_pointers (gimple_return_retval (t)))
3921 make_escape_constraint (gimple_return_retval (t));
3923 /* Handle asms conservatively by adding escape constraints to everything. */
3924 else if (gimple_code (t) == GIMPLE_ASM)
3926 unsigned i, noutputs;
3927 const char **oconstraints;
3928 const char *constraint;
3929 bool allows_mem, allows_reg, is_inout;
3931 noutputs = gimple_asm_noutputs (t);
3932 oconstraints = XALLOCAVEC (const char *, noutputs);
3934 for (i = 0; i < noutputs; ++i)
3936 tree link = gimple_asm_output_op (t, i);
3937 tree op = TREE_VALUE (link);
3939 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
3940 oconstraints[i] = constraint;
3941 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
3942 &allows_reg, &is_inout);
3944 /* A memory constraint makes the address of the operand escape. */
3945 if (!allows_reg && allows_mem)
3946 make_escape_constraint (build_fold_addr_expr (op));
3948 /* The asm may read global memory, so outputs may point to
3949 any global memory. */
3950 if (op && could_have_pointers (op))
3952 VEC(ce_s, heap) *lhsc = NULL;
3953 struct constraint_expr rhsc, *lhsp;
3955 get_constraint_for (op, &lhsc);
3956 rhsc.var = nonlocal_id;
3959 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3960 process_constraint (new_constraint (*lhsp, rhsc));
3961 VEC_free (ce_s, heap, lhsc);
3964 for (i = 0; i < gimple_asm_ninputs (t); ++i)
3966 tree link = gimple_asm_input_op (t, i);
3967 tree op = TREE_VALUE (link);
3969 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
3971 parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
3972 &allows_mem, &allows_reg);
3974 /* A memory constraint makes the address of the operand escape. */
3975 if (!allows_reg && allows_mem)
3976 make_escape_constraint (build_fold_addr_expr (op));
3977 /* Strictly we'd only need the constraint to ESCAPED if
3978 the asm clobbers memory, otherwise using CALLUSED
3980 else if (op && could_have_pointers (op))
3981 make_escape_constraint (op);
3985 VEC_free (ce_s, heap, rhsc);
3986 VEC_free (ce_s, heap, lhsc);
3990 /* Find the first varinfo in the same variable as START that overlaps with
3991 OFFSET. Return NULL if we can't find one. */
3994 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3996 /* If the offset is outside of the variable, bail out. */
3997 if (offset >= start->fullsize)
4000 /* If we cannot reach offset from start, lookup the first field
4001 and start from there. */
4002 if (start->offset > offset)
4003 start = lookup_vi_for_tree (start->decl);
4007 /* We may not find a variable in the field list with the actual
4008 offset when when we have glommed a structure to a variable.
4009 In that case, however, offset should still be within the size
4011 if (offset >= start->offset
4012 && offset < (start->offset + start->size))
4021 /* Find the first varinfo in the same variable as START that overlaps with
4022 OFFSET. If there is no such varinfo the varinfo directly preceding
4023 OFFSET is returned. */
4026 first_or_preceding_vi_for_offset (varinfo_t start,
4027 unsigned HOST_WIDE_INT offset)
4029 /* If we cannot reach offset from start, lookup the first field
4030 and start from there. */
4031 if (start->offset > offset)
4032 start = lookup_vi_for_tree (start->decl);
4034 /* We may not find a variable in the field list with the actual
4035 offset when when we have glommed a structure to a variable.
4036 In that case, however, offset should still be within the size
4038 If we got beyond the offset we look for return the field
4039 directly preceding offset which may be the last field. */
4041 && offset >= start->offset
4042 && !(offset < (start->offset + start->size)))
4043 start = start->next;
4049 /* Insert the varinfo FIELD into the field list for BASE, at the front
4053 insert_into_field_list (varinfo_t base, varinfo_t field)
4055 varinfo_t prev = base;
4056 varinfo_t curr = base->next;
4062 /* Insert the varinfo FIELD into the field list for BASE, ordered by
4066 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
4068 varinfo_t prev = base;
4069 varinfo_t curr = base->next;
4080 if (field->offset <= curr->offset)
4085 field->next = prev->next;
4090 /* This structure is used during pushing fields onto the fieldstack
4091 to track the offset of the field, since bitpos_of_field gives it
4092 relative to its immediate containing type, and we want it relative
4093 to the ultimate containing object. */
4097 /* Offset from the base of the base containing object to this field. */
4098 HOST_WIDE_INT offset;
4100 /* Size, in bits, of the field. */
4101 unsigned HOST_WIDE_INT size;
4103 unsigned has_unknown_size : 1;
4105 unsigned may_have_pointers : 1;
4107 unsigned only_restrict_pointers : 1;
4109 typedef struct fieldoff fieldoff_s;
4111 DEF_VEC_O(fieldoff_s);
4112 DEF_VEC_ALLOC_O(fieldoff_s,heap);
4114 /* qsort comparison function for two fieldoff's PA and PB */
4117 fieldoff_compare (const void *pa, const void *pb)
4119 const fieldoff_s *foa = (const fieldoff_s *)pa;
4120 const fieldoff_s *fob = (const fieldoff_s *)pb;
4121 unsigned HOST_WIDE_INT foasize, fobsize;
4123 if (foa->offset < fob->offset)
4125 else if (foa->offset > fob->offset)
4128 foasize = foa->size;
4129 fobsize = fob->size;
4130 if (foasize < fobsize)
4132 else if (foasize > fobsize)
4137 /* Sort a fieldstack according to the field offset and sizes. */
4139 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
4141 qsort (VEC_address (fieldoff_s, fieldstack),
4142 VEC_length (fieldoff_s, fieldstack),
4143 sizeof (fieldoff_s),
4147 /* Return true if V is a tree that we can have subvars for.
4148 Normally, this is any aggregate type. Also complex
4149 types which are not gimple registers can have subvars. */
4152 var_can_have_subvars (const_tree v)
4154 /* Volatile variables should never have subvars. */
4155 if (TREE_THIS_VOLATILE (v))
4158 /* Non decls or memory tags can never have subvars. */
4162 /* Aggregates without overlapping fields can have subvars. */
4163 if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
4169 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4170 the fields of TYPE onto fieldstack, recording their offsets along
4173 OFFSET is used to keep track of the offset in this entire
4174 structure, rather than just the immediately containing structure.
4175 Returns the number of fields pushed. */
4178 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
4179 HOST_WIDE_INT offset)
4184 if (TREE_CODE (type) != RECORD_TYPE)
4187 /* If the vector of fields is growing too big, bail out early.
4188 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4190 if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
4193 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
4194 if (TREE_CODE (field) == FIELD_DECL)
4198 HOST_WIDE_INT foff = bitpos_of_field (field);
4200 if (!var_can_have_subvars (field)
4201 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
4202 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
4204 else if (!(pushed = push_fields_onto_fieldstack
4205 (TREE_TYPE (field), fieldstack, offset + foff))
4206 && (DECL_SIZE (field)
4207 && !integer_zerop (DECL_SIZE (field))))
4208 /* Empty structures may have actual size, like in C++. So
4209 see if we didn't push any subfields and the size is
4210 nonzero, push the field onto the stack. */
4215 fieldoff_s *pair = NULL;
4216 bool has_unknown_size = false;
4218 if (!VEC_empty (fieldoff_s, *fieldstack))
4219 pair = VEC_last (fieldoff_s, *fieldstack);
4221 if (!DECL_SIZE (field)
4222 || !host_integerp (DECL_SIZE (field), 1))
4223 has_unknown_size = true;
4225 /* If adjacent fields do not contain pointers merge them. */
4227 && !pair->may_have_pointers
4228 && !could_have_pointers (field)
4229 && !pair->has_unknown_size
4230 && !has_unknown_size
4231 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
4233 pair = VEC_last (fieldoff_s, *fieldstack);
4234 pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
4238 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
4239 pair->offset = offset + foff;
4240 pair->has_unknown_size = has_unknown_size;
4241 if (!has_unknown_size)
4242 pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
4245 pair->may_have_pointers = could_have_pointers (field);
4246 pair->only_restrict_pointers
4247 = (!has_unknown_size
4248 && POINTER_TYPE_P (TREE_TYPE (field))
4249 && TYPE_RESTRICT (TREE_TYPE (field)));
4260 /* Count the number of arguments DECL has, and set IS_VARARGS to true
4261 if it is a varargs function. */
4264 count_num_arguments (tree decl, bool *is_varargs)
4269 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
4273 if (TREE_VALUE (t) == void_type_node)
4283 /* Creation function node for DECL, using NAME, and return the index
4284 of the variable we've created for the function. */
4287 create_function_info_for (tree decl, const char *name)
4292 bool is_varargs = false;
4294 /* Create the variable info. */
4296 vi = new_var_info (decl, name);
4299 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
4300 insert_vi_for_tree (vi->decl, vi);
4304 /* If it's varargs, we don't know how many arguments it has, so we
4310 vi->is_unknown_size_var = true;
4314 arg = DECL_ARGUMENTS (decl);
4316 /* Set up variables for each argument. */
4317 for (i = 1; i < vi->fullsize; i++)
4320 const char *newname;
4322 tree argdecl = decl;
4327 asprintf (&tempname, "%s.arg%d", name, i-1);
4328 newname = ggc_strdup (tempname);
4331 argvi = new_var_info (argdecl, newname);
4334 argvi->is_full_var = true;
4335 argvi->fullsize = vi->fullsize;
4336 insert_into_field_list_sorted (vi, argvi);
4337 stats.total_vars ++;
4340 insert_vi_for_tree (arg, argvi);
4341 arg = TREE_CHAIN (arg);
4345 /* Create a variable for the return var. */
4346 if (DECL_RESULT (decl) != NULL
4347 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
4350 const char *newname;
4352 tree resultdecl = decl;
4356 if (DECL_RESULT (decl))
4357 resultdecl = DECL_RESULT (decl);
4359 asprintf (&tempname, "%s.result", name);
4360 newname = ggc_strdup (tempname);
4363 resultvi = new_var_info (resultdecl, newname);
4364 resultvi->offset = i;
4366 resultvi->fullsize = vi->fullsize;
4367 resultvi->is_full_var = true;
4368 insert_into_field_list_sorted (vi, resultvi);
4369 stats.total_vars ++;
4370 if (DECL_RESULT (decl))
4371 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
4378 /* Return true if FIELDSTACK contains fields that overlap.
4379 FIELDSTACK is assumed to be sorted by offset. */
4382 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
4384 fieldoff_s *fo = NULL;
4386 HOST_WIDE_INT lastoffset = -1;
4388 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4390 if (fo->offset == lastoffset)
4392 lastoffset = fo->offset;
4397 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4398 This will also create any varinfo structures necessary for fields
4402 create_variable_info_for (tree decl, const char *name)
4405 tree decl_type = TREE_TYPE (decl);
4406 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
4407 VEC (fieldoff_s,heap) *fieldstack = NULL;
4409 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4410 return create_function_info_for (decl, name);
4412 if (var_can_have_subvars (decl) && use_field_sensitive)
4413 push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
4415 /* If the variable doesn't have subvars, we may end up needing to
4416 sort the field list and create fake variables for all the
4418 vi = new_var_info (decl, name);
4420 vi->may_have_pointers = could_have_pointers (decl);
4422 || !host_integerp (declsize, 1))
4424 vi->is_unknown_size_var = true;
4430 vi->fullsize = TREE_INT_CST_LOW (declsize);
4431 vi->size = vi->fullsize;
4434 insert_vi_for_tree (vi->decl, vi);
4435 if (vi->is_global_var
4436 && (!flag_whole_program || !in_ipa_mode)
4437 && vi->may_have_pointers)
4439 if (POINTER_TYPE_P (TREE_TYPE (decl))
4440 && TYPE_RESTRICT (TREE_TYPE (decl)))
4441 make_constraint_from_restrict (vi, "GLOBAL_RESTRICT");
4442 make_copy_constraint (vi, nonlocal_id);
4446 if (use_field_sensitive
4447 && !vi->is_unknown_size_var
4448 && var_can_have_subvars (decl)
4449 && VEC_length (fieldoff_s, fieldstack) > 1
4450 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4452 fieldoff_s *fo = NULL;
4453 bool notokay = false;
4456 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4458 if (fo->has_unknown_size
4466 /* We can't sort them if we have a field with a variable sized type,
4467 which will make notokay = true. In that case, we are going to return
4468 without creating varinfos for the fields anyway, so sorting them is a
4472 sort_fieldstack (fieldstack);
4473 /* Due to some C++ FE issues, like PR 22488, we might end up
4474 what appear to be overlapping fields even though they,
4475 in reality, do not overlap. Until the C++ FE is fixed,
4476 we will simply disable field-sensitivity for these cases. */
4477 notokay = check_for_overlaps (fieldstack);
4481 if (VEC_length (fieldoff_s, fieldstack) != 0)
4482 fo = VEC_index (fieldoff_s, fieldstack, 0);
4484 if (fo == NULL || notokay)
4486 vi->is_unknown_size_var = 1;
4489 vi->is_full_var = true;
4490 VEC_free (fieldoff_s, heap, fieldstack);
4494 vi->size = fo->size;
4495 vi->offset = fo->offset;
4496 vi->may_have_pointers = fo->may_have_pointers;
4497 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4498 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4502 const char *newname = "NULL";
4507 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
4508 "+" HOST_WIDE_INT_PRINT_DEC,
4509 vi->name, fo->offset, fo->size);
4510 newname = ggc_strdup (tempname);
4513 newvi = new_var_info (decl, newname);
4514 newvi->offset = fo->offset;
4515 newvi->size = fo->size;
4516 newvi->fullsize = vi->fullsize;
4517 newvi->may_have_pointers = fo->may_have_pointers;
4518 insert_into_field_list (vi, newvi);
4519 if (newvi->is_global_var
4520 && (!flag_whole_program || !in_ipa_mode)
4521 && newvi->may_have_pointers)
4523 if (fo->only_restrict_pointers)
4524 make_constraint_from_restrict (newvi, "GLOBAL_RESTRICT");
4525 make_copy_constraint (newvi, nonlocal_id);
4532 vi->is_full_var = true;
4534 VEC_free (fieldoff_s, heap, fieldstack);
4539 /* Print out the points-to solution for VAR to FILE. */
4542 dump_solution_for_var (FILE *file, unsigned int var)
4544 varinfo_t vi = get_varinfo (var);
4548 if (find (var) != var)
4550 varinfo_t vipt = get_varinfo (find (var));
4551 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4555 fprintf (file, "%s = { ", vi->name);
4556 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4558 fprintf (file, "%s ", get_varinfo (i)->name);
4560 fprintf (file, "}\n");
4564 /* Print the points-to solution for VAR to stdout. */
4567 debug_solution_for_var (unsigned int var)
4569 dump_solution_for_var (stdout, var);
4572 /* Create varinfo structures for all of the variables in the
4573 function for intraprocedural mode. */
4576 intra_create_variable_infos (void)
4580 /* For each incoming pointer argument arg, create the constraint ARG
4581 = NONLOCAL or a dummy variable if flag_argument_noalias is set. */
4582 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4586 if (!could_have_pointers (t))
4589 /* If flag_argument_noalias is set, then function pointer
4590 arguments are guaranteed not to point to each other. In that
4591 case, create an artificial variable PARM_NOALIAS and the
4592 constraint ARG = &PARM_NOALIAS. */
4593 if (POINTER_TYPE_P (TREE_TYPE (t)) && flag_argument_noalias > 0)
4598 vi = make_constraint_from_heapvar (get_vi_for_tree (t),
4600 ann = get_var_ann (vi->decl);
4601 if (flag_argument_noalias == 1)
4603 ann->noalias_state = NO_ALIAS;
4604 make_copy_constraint (vi, nonlocal_id);
4606 else if (flag_argument_noalias == 2)
4608 ann->noalias_state = NO_ALIAS_GLOBAL;
4609 make_constraint_from (vi, vi->id);
4611 else if (flag_argument_noalias == 3)
4613 ann->noalias_state = NO_ALIAS_ANYTHING;
4614 make_constraint_from (vi, vi->id);
4621 varinfo_t arg_vi = get_vi_for_tree (t);
4623 for (p = arg_vi; p; p = p->next)
4624 make_constraint_from (p, nonlocal_id);
4626 if (POINTER_TYPE_P (TREE_TYPE (t))
4627 && TYPE_RESTRICT (TREE_TYPE (t)))
4628 make_constraint_from_restrict (get_vi_for_tree (t), "PARM_RESTRICT");
4631 /* Add a constraint for a result decl that is passed by reference. */
4632 if (DECL_RESULT (cfun->decl)
4633 && DECL_BY_REFERENCE (DECL_RESULT (cfun->decl)))
4635 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
4637 for (p = result_vi; p; p = p->next)
4638 make_constraint_from (p, nonlocal_id);
4641 /* Add a constraint for the incoming static chain parameter. */
4642 if (cfun->static_chain_decl != NULL_TREE)
4644 varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
4646 for (p = chain_vi; p; p = p->next)
4647 make_constraint_from (p, nonlocal_id);
4651 /* Structure used to put solution bitmaps in a hashtable so they can
4652 be shared among variables with the same points-to set. */
4654 typedef struct shared_bitmap_info
4658 } *shared_bitmap_info_t;
4659 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
4661 static htab_t shared_bitmap_table;
4663 /* Hash function for a shared_bitmap_info_t */
4666 shared_bitmap_hash (const void *p)
4668 const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
4669 return bi->hashcode;
4672 /* Equality function for two shared_bitmap_info_t's. */
4675 shared_bitmap_eq (const void *p1, const void *p2)
4677 const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
4678 const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
4679 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
4682 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4683 existing instance if there is one, NULL otherwise. */
4686 shared_bitmap_lookup (bitmap pt_vars)
4689 struct shared_bitmap_info sbi;
4691 sbi.pt_vars = pt_vars;
4692 sbi.hashcode = bitmap_hash (pt_vars);
4694 slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
4695 sbi.hashcode, NO_INSERT);
4699 return ((shared_bitmap_info_t) *slot)->pt_vars;
4703 /* Add a bitmap to the shared bitmap hashtable. */
4706 shared_bitmap_add (bitmap pt_vars)
4709 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
4711 sbi->pt_vars = pt_vars;
4712 sbi->hashcode = bitmap_hash (pt_vars);
4714 slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
4715 sbi->hashcode, INSERT);
4716 gcc_assert (!*slot);
4717 *slot = (void *) sbi;
4721 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */
4724 set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt)
4729 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4731 varinfo_t vi = get_varinfo (i);
4733 /* The only artificial variables that are allowed in a may-alias
4734 set are heap variables. */
4735 if (vi->is_artificial_var && !vi->is_heap_var)
4738 if (TREE_CODE (vi->decl) == VAR_DECL
4739 || TREE_CODE (vi->decl) == PARM_DECL
4740 || TREE_CODE (vi->decl) == RESULT_DECL)
4742 /* Add the decl to the points-to set. Note that the points-to
4743 set contains global variables. */
4744 bitmap_set_bit (into, DECL_UID (vi->decl));
4745 if (vi->is_global_var)
4746 pt->vars_contains_global = true;
4752 static bool have_alias_info = false;
4754 /* Compute the points-to solution *PT for the variable VI. */
4757 find_what_var_points_to (varinfo_t vi, struct pt_solution *pt)
4761 bitmap finished_solution;
4764 memset (pt, 0, sizeof (struct pt_solution));
4766 /* This variable may have been collapsed, let's get the real
4768 vi = get_varinfo (find (vi->id));
4770 /* Translate artificial variables into SSA_NAME_PTR_INFO
4772 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4774 varinfo_t vi = get_varinfo (i);
4776 if (vi->is_artificial_var)
4778 if (vi->id == nothing_id)
4780 else if (vi->id == escaped_id)
4782 else if (vi->id == callused_id)
4784 else if (vi->id == nonlocal_id)
4786 else if (vi->is_heap_var)
4787 /* We represent heapvars in the points-to set properly. */
4789 else if (vi->id == readonly_id)
4792 else if (vi->id == anything_id
4793 || vi->id == integer_id)
4796 if (vi->is_restrict_var)
4797 pt->vars_contains_restrict = true;
4800 /* Instead of doing extra work, simply do not create
4801 elaborate points-to information for pt_anything pointers. */
4803 && (vi->is_artificial_var
4804 || !pt->vars_contains_restrict))
4807 /* Share the final set of variables when possible. */
4808 finished_solution = BITMAP_GGC_ALLOC ();
4809 stats.points_to_sets_created++;
4811 set_uids_in_ptset (finished_solution, vi->solution, pt);
4812 result = shared_bitmap_lookup (finished_solution);
4815 shared_bitmap_add (finished_solution);
4816 pt->vars = finished_solution;
4821 bitmap_clear (finished_solution);
4825 /* Given a pointer variable P, fill in its points-to set. */
4828 find_what_p_points_to (tree p)
4830 struct ptr_info_def *pi;
4834 /* For parameters, get at the points-to set for the actual parm
4836 if (TREE_CODE (p) == SSA_NAME
4837 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4838 && SSA_NAME_IS_DEFAULT_DEF (p))
4839 lookup_p = SSA_NAME_VAR (p);
4841 vi = lookup_vi_for_tree (lookup_p);
4845 pi = get_ptr_info (p);
4846 find_what_var_points_to (vi, &pi->pt);
4850 /* Query statistics for points-to solutions. */
4853 unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
4854 unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
4855 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
4856 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
4860 dump_pta_stats (FILE *s)
4862 fprintf (s, "\nPTA query stats:\n");
4863 fprintf (s, " pt_solution_includes: "
4864 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
4865 HOST_WIDE_INT_PRINT_DEC" queries\n",
4866 pta_stats.pt_solution_includes_no_alias,
4867 pta_stats.pt_solution_includes_no_alias
4868 + pta_stats.pt_solution_includes_may_alias);
4869 fprintf (s, " pt_solutions_intersect: "
4870 HOST_WIDE_INT_PRINT_DEC" disambiguations, "
4871 HOST_WIDE_INT_PRINT_DEC" queries\n",
4872 pta_stats.pt_solutions_intersect_no_alias,
4873 pta_stats.pt_solutions_intersect_no_alias
4874 + pta_stats.pt_solutions_intersect_may_alias);
4878 /* Reset the points-to solution *PT to a conservative default
4879 (point to anything). */
4882 pt_solution_reset (struct pt_solution *pt)
4884 memset (pt, 0, sizeof (struct pt_solution));
4885 pt->anything = true;
4888 /* Return true if the points-to solution *PT is empty. */
4891 pt_solution_empty_p (struct pt_solution *pt)
4898 && !bitmap_empty_p (pt->vars))
4901 /* If the solution includes ESCAPED, check if that is empty. */
4903 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
4909 /* Return true if the points-to solution *PT includes global memory. */
4912 pt_solution_includes_global (struct pt_solution *pt)
4916 || pt->vars_contains_global)
4920 return pt_solution_includes_global (&cfun->gimple_df->escaped);
4925 /* Return true if the points-to solution *PT includes the variable
4926 declaration DECL. */
4929 pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
4935 && is_global_var (decl))
4939 && bitmap_bit_p (pt->vars, DECL_UID (decl)))
4942 /* If the solution includes ESCAPED, check it. */
4944 && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
4951 pt_solution_includes (struct pt_solution *pt, const_tree decl)
4953 bool res = pt_solution_includes_1 (pt, decl);
4955 ++pta_stats.pt_solution_includes_may_alias;
4957 ++pta_stats.pt_solution_includes_no_alias;
4961 /* Return true if both points-to solutions PT1 and PT2 have a non-empty
4965 pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
4967 if (pt1->anything || pt2->anything)
4970 /* If either points to unknown global memory and the other points to
4971 any global memory they alias. */
4974 || pt2->vars_contains_global))
4976 && pt1->vars_contains_global))
4979 /* Check the escaped solution if required. */
4980 if ((pt1->escaped || pt2->escaped)
4981 && !pt_solution_empty_p (&cfun->gimple_df->escaped))
4983 /* If both point to escaped memory and that solution
4984 is not empty they alias. */
4985 if (pt1->escaped && pt2->escaped)
4988 /* If either points to escaped memory see if the escaped solution
4989 intersects with the other. */
4991 && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt2))
4993 && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt1)))
4997 /* Now both pointers alias if their points-to solution intersects. */
5000 && bitmap_intersect_p (pt1->vars, pt2->vars));
5004 pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
5006 bool res = pt_solutions_intersect_1 (pt1, pt2);
5008 ++pta_stats.pt_solutions_intersect_may_alias;
5010 ++pta_stats.pt_solutions_intersect_no_alias;
5014 /* Return true if both points-to solutions PT1 and PT2 for two restrict
5015 qualified pointers are possibly based on the same pointer. */
5018 pt_solutions_same_restrict_base (struct pt_solution *pt1,
5019 struct pt_solution *pt2)
5021 /* If we deal with points-to solutions of two restrict qualified
5022 pointers solely rely on the pointed-to variable bitmap intersection.
5023 For two pointers that are based on each other the bitmaps will
5025 if (pt1->vars_contains_restrict
5026 && pt2->vars_contains_restrict)
5028 gcc_assert (pt1->vars && pt2->vars);
5029 return bitmap_intersect_p (pt1->vars, pt2->vars);
5036 /* Dump points-to information to OUTFILE. */
5039 dump_sa_points_to_info (FILE *outfile)
5043 fprintf (outfile, "\nPoints-to sets\n\n");
5045 if (dump_flags & TDF_STATS)
5047 fprintf (outfile, "Stats:\n");
5048 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
5049 fprintf (outfile, "Non-pointer vars: %d\n",
5050 stats.nonpointer_vars);
5051 fprintf (outfile, "Statically unified vars: %d\n",
5052 stats.unified_vars_static);
5053 fprintf (outfile, "Dynamically unified vars: %d\n",
5054 stats.unified_vars_dynamic);
5055 fprintf (outfile, "Iterations: %d\n", stats.iterations);
5056 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
5057 fprintf (outfile, "Number of implicit edges: %d\n",
5058 stats.num_implicit_edges);
5061 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
5062 dump_solution_for_var (outfile, i);
5066 /* Debug points-to information to stderr. */
5069 debug_sa_points_to_info (void)
5071 dump_sa_points_to_info (stderr);
5075 /* Initialize the always-existing constraint variables for NULL
5076 ANYTHING, READONLY, and INTEGER */
5079 init_base_vars (void)
5081 struct constraint_expr lhs, rhs;
5082 varinfo_t var_anything;
5083 varinfo_t var_nothing;
5084 varinfo_t var_readonly;
5085 varinfo_t var_escaped;
5086 varinfo_t var_nonlocal;
5087 varinfo_t var_callused;
5088 varinfo_t var_storedanything;
5089 varinfo_t var_integer;
5091 /* Create the NULL variable, used to represent that a variable points
5093 var_nothing = new_var_info (NULL_TREE, "NULL");
5094 gcc_assert (var_nothing->id == nothing_id);
5095 var_nothing->is_artificial_var = 1;
5096 var_nothing->offset = 0;
5097 var_nothing->size = ~0;
5098 var_nothing->fullsize = ~0;
5099 var_nothing->is_special_var = 1;
5101 /* Create the ANYTHING variable, used to represent that a variable
5102 points to some unknown piece of memory. */
5103 var_anything = new_var_info (NULL_TREE, "ANYTHING");
5104 gcc_assert (var_anything->id == anything_id);
5105 var_anything->is_artificial_var = 1;
5106 var_anything->size = ~0;
5107 var_anything->offset = 0;
5108 var_anything->next = NULL;
5109 var_anything->fullsize = ~0;
5110 var_anything->is_special_var = 1;
5112 /* Anything points to anything. This makes deref constraints just
5113 work in the presence of linked list and other p = *p type loops,
5114 by saying that *ANYTHING = ANYTHING. */
5116 lhs.var = anything_id;
5118 rhs.type = ADDRESSOF;
5119 rhs.var = anything_id;
5122 /* This specifically does not use process_constraint because
5123 process_constraint ignores all anything = anything constraints, since all
5124 but this one are redundant. */
5125 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
5127 /* Create the READONLY variable, used to represent that a variable
5128 points to readonly memory. */
5129 var_readonly = new_var_info (NULL_TREE, "READONLY");
5130 gcc_assert (var_readonly->id == readonly_id);
5131 var_readonly->is_artificial_var = 1;
5132 var_readonly->offset = 0;
5133 var_readonly->size = ~0;
5134 var_readonly->fullsize = ~0;
5135 var_readonly->next = NULL;
5136 var_readonly->is_special_var = 1;
5138 /* readonly memory points to anything, in order to make deref
5139 easier. In reality, it points to anything the particular
5140 readonly variable can point to, but we don't track this
5143 lhs.var = readonly_id;
5145 rhs.type = ADDRESSOF;
5146 rhs.var = readonly_id; /* FIXME */
5148 process_constraint (new_constraint (lhs, rhs));
5150 /* Create the ESCAPED variable, used to represent the set of escaped
5152 var_escaped = new_var_info (NULL_TREE, "ESCAPED");
5153 gcc_assert (var_escaped->id == escaped_id);
5154 var_escaped->is_artificial_var = 1;
5155 var_escaped->offset = 0;
5156 var_escaped->size = ~0;
5157 var_escaped->fullsize = ~0;
5158 var_escaped->is_special_var = 0;
5160 /* Create the NONLOCAL variable, used to represent the set of nonlocal
5162 var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL");
5163 gcc_assert (var_nonlocal->id == nonlocal_id);
5164 var_nonlocal->is_artificial_var = 1;
5165 var_nonlocal->offset = 0;
5166 var_nonlocal->size = ~0;
5167 var_nonlocal->fullsize = ~0;
5168 var_nonlocal->is_special_var = 1;
5170 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
5172 lhs.var = escaped_id;
5175 rhs.var = escaped_id;
5177 process_constraint (new_constraint (lhs, rhs));
5179 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
5180 whole variable escapes. */
5182 lhs.var = escaped_id;
5185 rhs.var = escaped_id;
5186 rhs.offset = UNKNOWN_OFFSET;
5187 process_constraint (new_constraint (lhs, rhs));
5189 /* *ESCAPED = NONLOCAL. This is true because we have to assume
5190 everything pointed to by escaped points to what global memory can
5193 lhs.var = escaped_id;
5196 rhs.var = nonlocal_id;
5198 process_constraint (new_constraint (lhs, rhs));
5200 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
5201 global memory may point to global memory and escaped memory. */
5203 lhs.var = nonlocal_id;
5205 rhs.type = ADDRESSOF;
5206 rhs.var = nonlocal_id;
5208 process_constraint (new_constraint (lhs, rhs));
5209 rhs.type = ADDRESSOF;
5210 rhs.var = escaped_id;
5212 process_constraint (new_constraint (lhs, rhs));
5214 /* Create the CALLUSED variable, used to represent the set of call-used
5216 var_callused = new_var_info (NULL_TREE, "CALLUSED");
5217 gcc_assert (var_callused->id == callused_id);
5218 var_callused->is_artificial_var = 1;
5219 var_callused->offset = 0;
5220 var_callused->size = ~0;
5221 var_callused->fullsize = ~0;
5222 var_callused->is_special_var = 0;
5224 /* CALLUSED = *CALLUSED, because call-used is may-deref'd at calls, etc. */
5226 lhs.var = callused_id;
5229 rhs.var = callused_id;
5231 process_constraint (new_constraint (lhs, rhs));
5233 /* CALLUSED = CALLUSED + UNKNOWN, because if a sub-field is call-used the
5234 whole variable is call-used. */
5236 lhs.var = callused_id;
5239 rhs.var = callused_id;
5240 rhs.offset = UNKNOWN_OFFSET;
5241 process_constraint (new_constraint (lhs, rhs));
5243 /* Create the STOREDANYTHING variable, used to represent the set of
5244 variables stored to *ANYTHING. */
5245 var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING");
5246 gcc_assert (var_storedanything->id == storedanything_id);
5247 var_storedanything->is_artificial_var = 1;
5248 var_storedanything->offset = 0;
5249 var_storedanything->size = ~0;
5250 var_storedanything->fullsize = ~0;
5251 var_storedanything->is_special_var = 0;
5253 /* Create the INTEGER variable, used to represent that a variable points
5254 to what an INTEGER "points to". */
5255 var_integer = new_var_info (NULL_TREE, "INTEGER");
5256 gcc_assert (var_integer->id == integer_id);
5257 var_integer->is_artificial_var = 1;
5258 var_integer->size = ~0;
5259 var_integer->fullsize = ~0;
5260 var_integer->offset = 0;
5261 var_integer->next = NULL;
5262 var_integer->is_special_var = 1;
5264 /* INTEGER = ANYTHING, because we don't know where a dereference of
5265 a random integer will point to. */
5267 lhs.var = integer_id;
5269 rhs.type = ADDRESSOF;
5270 rhs.var = anything_id;
5272 process_constraint (new_constraint (lhs, rhs));
5275 /* Initialize things necessary to perform PTA */
5278 init_alias_vars (void)
5280 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
5282 bitmap_obstack_initialize (&pta_obstack);
5283 bitmap_obstack_initialize (&oldpta_obstack);
5284 bitmap_obstack_initialize (&predbitmap_obstack);
5286 constraint_pool = create_alloc_pool ("Constraint pool",
5287 sizeof (struct constraint), 30);
5288 variable_info_pool = create_alloc_pool ("Variable info pool",
5289 sizeof (struct variable_info), 30);
5290 constraints = VEC_alloc (constraint_t, heap, 8);
5291 varmap = VEC_alloc (varinfo_t, heap, 8);
5292 vi_for_tree = pointer_map_create ();
5294 memset (&stats, 0, sizeof (stats));
5295 shared_bitmap_table = htab_create (511, shared_bitmap_hash,
5296 shared_bitmap_eq, free);
5300 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
5301 predecessor edges. */
5304 remove_preds_and_fake_succs (constraint_graph_t graph)
5308 /* Clear the implicit ref and address nodes from the successor
5310 for (i = 0; i < FIRST_REF_NODE; i++)
5312 if (graph->succs[i])
5313 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
5314 FIRST_REF_NODE * 2);
5317 /* Free the successor list for the non-ref nodes. */
5318 for (i = FIRST_REF_NODE; i < graph->size; i++)
5320 if (graph->succs[i])
5321 BITMAP_FREE (graph->succs[i]);
5324 /* Now reallocate the size of the successor list as, and blow away
5325 the predecessor bitmaps. */
5326 graph->size = VEC_length (varinfo_t, varmap);
5327 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
5329 free (graph->implicit_preds);
5330 graph->implicit_preds = NULL;
5331 free (graph->preds);
5332 graph->preds = NULL;
5333 bitmap_obstack_release (&predbitmap_obstack);
5336 /* Initialize the heapvar for statement mapping. */
5339 init_alias_heapvars (void)
5341 if (!heapvar_for_stmt)
5342 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5346 /* Delete the heapvar for statement mapping. */
5349 delete_alias_heapvars (void)
5351 if (heapvar_for_stmt)
5352 htab_delete (heapvar_for_stmt);
5353 heapvar_for_stmt = NULL;
5356 /* Create points-to sets for the current function. See the comments
5357 at the start of the file for an algorithmic overview. */
5360 compute_points_to_sets (void)
5362 struct scc_info *si;
5367 timevar_push (TV_TREE_PTA);
5370 init_alias_heapvars ();
5372 intra_create_variable_infos ();
5374 /* Now walk all statements and derive aliases. */
5377 gimple_stmt_iterator gsi;
5379 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5381 gimple phi = gsi_stmt (gsi);
5383 if (is_gimple_reg (gimple_phi_result (phi)))
5384 find_func_aliases (phi);
5387 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5389 gimple stmt = gsi_stmt (gsi);
5391 find_func_aliases (stmt);
5397 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5398 dump_constraints (dump_file);
5403 "\nCollapsing static cycles and doing variable "
5406 init_graph (VEC_length (varinfo_t, varmap) * 2);
5409 fprintf (dump_file, "Building predecessor graph\n");
5410 build_pred_graph ();
5413 fprintf (dump_file, "Detecting pointer and location "
5415 si = perform_var_substitution (graph);
5418 fprintf (dump_file, "Rewriting constraints and unifying "
5420 rewrite_constraints (graph, si);
5422 build_succ_graph ();
5423 free_var_substitution_info (si);
5425 if (dump_file && (dump_flags & TDF_GRAPH))
5426 dump_constraint_graph (dump_file);
5428 move_complex_constraints (graph);
5431 fprintf (dump_file, "Uniting pointer but not location equivalent "
5433 unite_pointer_equivalences (graph);
5436 fprintf (dump_file, "Finding indirect cycles\n");
5437 find_indirect_cycles (graph);
5439 /* Implicit nodes and predecessors are no longer necessary at this
5441 remove_preds_and_fake_succs (graph);
5444 fprintf (dump_file, "Solving graph\n");
5446 solve_graph (graph);
5449 dump_sa_points_to_info (dump_file);
5451 /* Compute the points-to sets for ESCAPED and CALLUSED used for
5452 call-clobber analysis. */
5453 find_what_var_points_to (get_varinfo (escaped_id),
5454 &cfun->gimple_df->escaped);
5455 find_what_var_points_to (get_varinfo (callused_id),
5456 &cfun->gimple_df->callused);
5458 /* Make sure the ESCAPED solution (which is used as placeholder in
5459 other solutions) does not reference itself. This simplifies
5460 points-to solution queries. */
5461 cfun->gimple_df->escaped.escaped = 0;
5463 /* Mark escaped HEAP variables as global. */
5464 for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); ++i)
5466 && !vi->is_restrict_var
5467 && !vi->is_global_var)
5468 DECL_EXTERNAL (vi->decl) = vi->is_global_var
5469 = pt_solution_includes (&cfun->gimple_df->escaped, vi->decl);
5471 /* Compute the points-to sets for pointer SSA_NAMEs. */
5472 for (i = 0; i < num_ssa_names; ++i)
5474 tree ptr = ssa_name (i);
5476 && POINTER_TYPE_P (TREE_TYPE (ptr)))
5477 find_what_p_points_to (ptr);
5480 timevar_pop (TV_TREE_PTA);
5482 have_alias_info = true;
5486 /* Delete created points-to sets. */
5489 delete_points_to_sets (void)
5493 htab_delete (shared_bitmap_table);
5494 if (dump_file && (dump_flags & TDF_STATS))
5495 fprintf (dump_file, "Points to sets created:%d\n",
5496 stats.points_to_sets_created);
5498 pointer_map_destroy (vi_for_tree);
5499 bitmap_obstack_release (&pta_obstack);
5500 VEC_free (constraint_t, heap, constraints);
5502 for (i = 0; i < graph->size; i++)
5503 VEC_free (constraint_t, heap, graph->complex[i]);
5504 free (graph->complex);
5507 free (graph->succs);
5509 free (graph->pe_rep);
5510 free (graph->indirect_cycles);
5513 VEC_free (varinfo_t, heap, varmap);
5514 free_alloc_pool (variable_info_pool);
5515 free_alloc_pool (constraint_pool);
5516 have_alias_info = false;
5520 /* Compute points-to information for every SSA_NAME pointer in the
5521 current function and compute the transitive closure of escaped
5522 variables to re-initialize the call-clobber states of local variables. */
5525 compute_may_aliases (void)
5527 /* For each pointer P_i, determine the sets of variables that P_i may
5528 point-to. Compute the reachability set of escaped and call-used
5530 compute_points_to_sets ();
5532 /* Debugging dumps. */
5535 dump_alias_info (dump_file);
5537 if (dump_flags & TDF_DETAILS)
5538 dump_referenced_vars (dump_file);
5541 /* Deallocate memory used by aliasing data structures and the internal
5542 points-to solution. */
5543 delete_points_to_sets ();
5545 gcc_assert (!need_ssa_update_p (cfun));
5551 gate_tree_pta (void)
5553 return flag_tree_pta;
5556 /* A dummy pass to cause points-to information to be computed via
5557 TODO_rebuild_alias. */
5559 struct gimple_opt_pass pass_build_alias =
5564 gate_tree_pta, /* gate */
5568 0, /* static_pass_number */
5569 TV_NONE, /* tv_id */
5570 PROP_cfg | PROP_ssa, /* properties_required */
5571 0, /* properties_provided */
5572 0, /* properties_destroyed */
5573 0, /* todo_flags_start */
5574 TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */
5578 /* A dummy pass to cause points-to information to be computed via
5579 TODO_rebuild_alias. */
5581 struct gimple_opt_pass pass_build_ealias =
5585 "ealias", /* name */
5586 gate_tree_pta, /* gate */
5590 0, /* static_pass_number */
5591 TV_NONE, /* tv_id */
5592 PROP_cfg | PROP_ssa, /* properties_required */
5593 0, /* properties_provided */
5594 0, /* properties_destroyed */
5595 0, /* todo_flags_start */
5596 TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */
5601 /* Return true if we should execute IPA PTA. */
5605 return (flag_ipa_pta
5606 /* Don't bother doing anything if the program has errors. */
5607 && !(errorcount || sorrycount));
5610 /* Execute the driver for IPA PTA. */
5612 ipa_pta_execute (void)
5614 struct cgraph_node *node;
5615 struct scc_info *si;
5618 init_alias_heapvars ();
5621 for (node = cgraph_nodes; node; node = node->next)
5625 varid = create_function_info_for (node->decl,
5626 cgraph_node_name (node));
5627 if (node->local.externally_visible)
5629 varinfo_t fi = get_varinfo (varid);
5630 for (; fi; fi = fi->next)
5631 make_constraint_from (fi, anything_id);
5634 for (node = cgraph_nodes; node; node = node->next)
5638 struct function *func = DECL_STRUCT_FUNCTION (node->decl);
5640 tree old_func_decl = current_function_decl;
5643 "Generating constraints for %s\n",
5644 cgraph_node_name (node));
5646 current_function_decl = node->decl;
5648 FOR_EACH_BB_FN (bb, func)
5650 gimple_stmt_iterator gsi;
5652 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
5655 gimple phi = gsi_stmt (gsi);
5657 if (is_gimple_reg (gimple_phi_result (phi)))
5658 find_func_aliases (phi);
5661 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5662 find_func_aliases (gsi_stmt (gsi));
5664 current_function_decl = old_func_decl;
5669 /* Make point to anything. */
5675 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5676 dump_constraints (dump_file);
5681 "\nCollapsing static cycles and doing variable "
5684 init_graph (VEC_length (varinfo_t, varmap) * 2);
5685 build_pred_graph ();
5686 si = perform_var_substitution (graph);
5687 rewrite_constraints (graph, si);
5689 build_succ_graph ();
5690 free_var_substitution_info (si);
5691 move_complex_constraints (graph);
5692 unite_pointer_equivalences (graph);
5693 find_indirect_cycles (graph);
5695 /* Implicit nodes and predecessors are no longer necessary at this
5697 remove_preds_and_fake_succs (graph);
5700 fprintf (dump_file, "\nSolving graph\n");
5702 solve_graph (graph);
5705 dump_sa_points_to_info (dump_file);
5708 delete_alias_heapvars ();
5709 delete_points_to_sets ();
5713 struct simple_ipa_opt_pass pass_ipa_pta =
5718 gate_ipa_pta, /* gate */
5719 ipa_pta_execute, /* execute */
5722 0, /* static_pass_number */
5723 TV_IPA_PTA, /* tv_id */
5724 0, /* properties_required */
5725 0, /* properties_provided */
5726 0, /* properties_destroyed */
5727 0, /* todo_flags_start */
5728 TODO_update_ssa /* todo_flags_finish */
5733 #include "gt-tree-ssa-structalias.h"