1 /* Tree based points-to analysis
2 Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or
10 (at your option) any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
35 #include "diagnostic.h"
38 #include "tree-flow.h"
39 #include "tree-inline.h"
42 #include "tree-gimple.h"
46 #include "tree-pass.h"
48 #include "alloc-pool.h"
49 #include "splay-tree.h"
51 #include "tree-ssa-structalias.h"
54 #include "pointer-set.h"
56 /* The idea behind this analyzer is to generate set constraints from the
57 program, then solve the resulting constraints in order to generate the
60 Set constraints are a way of modeling program analysis problems that
61 involve sets. They consist of an inclusion constraint language,
62 describing the variables (each variable is a set) and operations that
63 are involved on the variables, and a set of rules that derive facts
64 from these operations. To solve a system of set constraints, you derive
65 all possible facts under the rules, which gives you the correct sets
68 See "Efficient Field-sensitive pointer analysis for C" by "David
69 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
70 http://citeseer.ist.psu.edu/pearce04efficient.html
72 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
73 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
74 http://citeseer.ist.psu.edu/heintze01ultrafast.html
76 There are three types of real constraint expressions, DEREF,
77 ADDRESSOF, and SCALAR. Each constraint expression consists
78 of a constraint type, a variable, and an offset.
80 SCALAR is a constraint expression type used to represent x, whether
81 it appears on the LHS or the RHS of a statement.
82 DEREF is a constraint expression type used to represent *x, whether
83 it appears on the LHS or the RHS of a statement.
84 ADDRESSOF is a constraint expression used to represent &x, whether
85 it appears on the LHS or the RHS of a statement.
87 Each pointer variable in the program is assigned an integer id, and
88 each field of a structure variable is assigned an integer id as well.
90 Structure variables are linked to their list of fields through a "next
91 field" in each variable that points to the next field in offset
93 Each variable for a structure field has
95 1. "size", that tells the size in bits of that field.
96 2. "fullsize, that tells the size in bits of the entire structure.
97 3. "offset", that tells the offset in bits from the beginning of the
98 structure to this field.
110 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
111 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
112 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
115 In order to solve the system of set constraints, the following is
118 1. Each constraint variable x has a solution set associated with it,
121 2. Constraints are separated into direct, copy, and complex.
122 Direct constraints are ADDRESSOF constraints that require no extra
123 processing, such as P = &Q
124 Copy constraints are those of the form P = Q.
125 Complex constraints are all the constraints involving dereferences
126 and offsets (including offsetted copies).
128 3. All direct constraints of the form P = &Q are processed, such
129 that Q is added to Sol(P)
131 4. All complex constraints for a given constraint variable are stored in a
132 linked list attached to that variable's node.
134 5. A directed graph is built out of the copy constraints. Each
135 constraint variable is a node in the graph, and an edge from
136 Q to P is added for each copy constraint of the form P = Q
138 6. The graph is then walked, and solution sets are
139 propagated along the copy edges, such that an edge from Q to P
140 causes Sol(P) <- Sol(P) union Sol(Q).
142 7. As we visit each node, all complex constraints associated with
143 that node are processed by adding appropriate copy edges to the graph, or the
144 appropriate variables to the solution set.
146 8. The process of walking the graph is iterated until no solution
149 Prior to walking the graph in steps 6 and 7, We perform static
150 cycle elimination on the constraint graph, as well
151 as off-line variable substitution.
153 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
154 on and turned into anything), but isn't. You can just see what offset
155 inside the pointed-to struct it's going to access.
157 TODO: Constant bounded arrays can be handled as if they were structs of the
158 same number of elements.
160 TODO: Modeling heap and incoming pointers becomes much better if we
161 add fields to them as we discover them, which we could do.
163 TODO: We could handle unions, but to be honest, it's probably not
164 worth the pain or slowdown. */
166 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
167 htab_t heapvar_for_stmt;
169 static bool use_field_sensitive = true;
170 static int in_ipa_mode = 0;
172 /* Used for predecessor bitmaps. */
173 static bitmap_obstack predbitmap_obstack;
175 /* Used for points-to sets. */
176 static bitmap_obstack pta_obstack;
178 /* Used for oldsolution members of variables. */
179 static bitmap_obstack oldpta_obstack;
181 /* Used for per-solver-iteration bitmaps. */
182 static bitmap_obstack iteration_obstack;
184 static unsigned int create_variable_info_for (tree, const char *);
185 typedef struct constraint_graph *constraint_graph_t;
186 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
188 DEF_VEC_P(constraint_t);
189 DEF_VEC_ALLOC_P(constraint_t,heap);
191 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
193 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
195 static struct constraint_stats
197 unsigned int total_vars;
198 unsigned int nonpointer_vars;
199 unsigned int unified_vars_static;
200 unsigned int unified_vars_dynamic;
201 unsigned int iterations;
202 unsigned int num_edges;
203 unsigned int num_implicit_edges;
204 unsigned int points_to_sets_created;
209 /* ID of this variable */
212 /* True if this is a variable created by the constraint analysis, such as
213 heap variables and constraints we had to break up. */
214 unsigned int is_artificial_var:1;
216 /* True if this is a special variable whose solution set should not be
218 unsigned int is_special_var:1;
220 /* True for variables whose size is not known or variable. */
221 unsigned int is_unknown_size_var:1;
223 /* True for (sub-)fields that represent a whole variable. */
224 unsigned int is_full_var : 1;
226 /* True if this is a heap variable. */
227 unsigned int is_heap_var:1;
229 /* True if we may not use TBAA to prune references to this
230 variable. This is used for C++ placement new. */
231 unsigned int no_tbaa_pruning : 1;
233 /* Variable id this was collapsed to due to type unsafety. Zero if
234 this variable was not collapsed. This should be unused completely
235 after build_succ_graph, or something is broken. */
236 unsigned int collapsed_to;
238 /* A link to the variable for the next field in this structure. */
239 struct variable_info *next;
241 /* Offset of this variable, in bits, from the base variable */
242 unsigned HOST_WIDE_INT offset;
244 /* Size of the variable, in bits. */
245 unsigned HOST_WIDE_INT size;
247 /* Full size of the base variable, in bits. */
248 unsigned HOST_WIDE_INT fullsize;
250 /* Name of this variable */
253 /* Tree that this variable is associated with. */
256 /* Points-to set for this variable. */
259 /* Old points-to set for this variable. */
262 typedef struct variable_info *varinfo_t;
264 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
265 static varinfo_t lookup_vi_for_tree (tree);
267 /* Pool of variable info structures. */
268 static alloc_pool variable_info_pool;
270 DEF_VEC_P(varinfo_t);
272 DEF_VEC_ALLOC_P(varinfo_t, heap);
274 /* Table of variable info structures for constraint variables.
275 Indexed directly by variable info id. */
276 static VEC(varinfo_t,heap) *varmap;
278 /* Return the varmap element N */
280 static inline varinfo_t
281 get_varinfo (unsigned int n)
283 return VEC_index (varinfo_t, varmap, n);
286 /* Return the varmap element N, following the collapsed_to link. */
288 static inline varinfo_t
289 get_varinfo_fc (unsigned int n)
291 varinfo_t v = VEC_index (varinfo_t, varmap, n);
293 if (v->collapsed_to != 0)
294 return get_varinfo (v->collapsed_to);
298 /* Static IDs for the special variables. */
299 enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
300 escaped_id = 3, nonlocal_id = 4, callused_id = 5, integer_id = 6 };
302 /* Variable that represents the unknown pointer. */
303 static varinfo_t var_anything;
304 static tree anything_tree;
306 /* Variable that represents the NULL pointer. */
307 static varinfo_t var_nothing;
308 static tree nothing_tree;
310 /* Variable that represents read only memory. */
311 static varinfo_t var_readonly;
312 static tree readonly_tree;
314 /* Variable that represents escaped memory. */
315 static varinfo_t var_escaped;
316 static tree escaped_tree;
318 /* Variable that represents nonlocal memory. */
319 static varinfo_t var_nonlocal;
320 static tree nonlocal_tree;
322 /* Variable that represents call-used memory. */
323 static varinfo_t var_callused;
324 static tree callused_tree;
326 /* Variable that represents integers. This is used for when people do things
328 static varinfo_t var_integer;
329 static tree integer_tree;
331 /* Lookup a heap var for FROM, and return it if we find one. */
334 heapvar_lookup (tree from)
336 struct tree_map *h, in;
339 h = (struct tree_map *) htab_find_with_hash (heapvar_for_stmt, &in,
340 htab_hash_pointer (from));
346 /* Insert a mapping FROM->TO in the heap var for statement
350 heapvar_insert (tree from, tree to)
355 h = GGC_NEW (struct tree_map);
356 h->hash = htab_hash_pointer (from);
359 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
360 *(struct tree_map **) loc = h;
363 /* Return a new variable info structure consisting for a variable
364 named NAME, and using constraint graph node NODE. */
367 new_var_info (tree t, unsigned int id, const char *name)
369 varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
375 ret->is_artificial_var = false;
376 ret->is_heap_var = false;
377 ret->is_special_var = false;
378 ret->is_unknown_size_var = false;
379 ret->is_full_var = false;
381 if (TREE_CODE (var) == SSA_NAME)
382 var = SSA_NAME_VAR (var);
383 ret->no_tbaa_pruning = (DECL_P (var)
384 && POINTER_TYPE_P (TREE_TYPE (var))
385 && DECL_NO_TBAA_P (var));
386 ret->solution = BITMAP_ALLOC (&pta_obstack);
387 ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
389 ret->collapsed_to = 0;
393 typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
395 /* An expression that appears in a constraint. */
397 struct constraint_expr
399 /* Constraint type. */
400 constraint_expr_type type;
402 /* Variable we are referring to in the constraint. */
405 /* Offset, in bits, of this constraint from the beginning of
406 variables it ends up referring to.
408 IOW, in a deref constraint, we would deref, get the result set,
409 then add OFFSET to each member. */
410 unsigned HOST_WIDE_INT offset;
413 typedef struct constraint_expr ce_s;
415 DEF_VEC_ALLOC_O(ce_s, heap);
416 static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);
417 static void get_constraint_for (tree, VEC(ce_s, heap) **);
418 static void do_deref (VEC (ce_s, heap) **);
420 /* Our set constraints are made up of two constraint expressions, one
423 As described in the introduction, our set constraints each represent an
424 operation between set valued variables.
428 struct constraint_expr lhs;
429 struct constraint_expr rhs;
432 /* List of constraints that we use to build the constraint graph from. */
434 static VEC(constraint_t,heap) *constraints;
435 static alloc_pool constraint_pool;
439 DEF_VEC_ALLOC_I(int, heap);
441 /* The constraint graph is represented as an array of bitmaps
442 containing successor nodes. */
444 struct constraint_graph
446 /* Size of this graph, which may be different than the number of
447 nodes in the variable map. */
450 /* Explicit successors of each node. */
453 /* Implicit predecessors of each node (Used for variable
455 bitmap *implicit_preds;
457 /* Explicit predecessors of each node (Used for variable substitution). */
460 /* Indirect cycle representatives, or -1 if the node has no indirect
462 int *indirect_cycles;
464 /* Representative node for a node. rep[a] == a unless the node has
468 /* Equivalence class representative for a label. This is used for
469 variable substitution. */
472 /* Pointer equivalence label for a node. All nodes with the same
473 pointer equivalence label can be unified together at some point
474 (either during constraint optimization or after the constraint
478 /* Pointer equivalence representative for a label. This is used to
479 handle nodes that are pointer equivalent but not location
480 equivalent. We can unite these once the addressof constraints
481 are transformed into initial points-to sets. */
484 /* Pointer equivalence label for each node, used during variable
486 unsigned int *pointer_label;
488 /* Location equivalence label for each node, used during location
489 equivalence finding. */
490 unsigned int *loc_label;
492 /* Pointed-by set for each node, used during location equivalence
493 finding. This is pointed-by rather than pointed-to, because it
494 is constructed using the predecessor graph. */
497 /* Points to sets for pointer equivalence. This is *not* the actual
498 points-to sets for nodes. */
501 /* Bitmap of nodes where the bit is set if the node is a direct
502 node. Used for variable substitution. */
503 sbitmap direct_nodes;
505 /* Bitmap of nodes where the bit is set if the node is address
506 taken. Used for variable substitution. */
507 bitmap address_taken;
509 /* True if points_to bitmap for this node is stored in the hash
513 /* Number of incoming edges remaining to be processed by pointer
515 Used for variable substitution. */
516 unsigned int *number_incoming;
519 /* Vector of complex constraints for each graph node. Complex
520 constraints are those involving dereferences or offsets that are
522 VEC(constraint_t,heap) **complex;
525 static constraint_graph_t graph;
527 /* During variable substitution and the offline version of indirect
528 cycle finding, we create nodes to represent dereferences and
529 address taken constraints. These represent where these start and
531 #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
532 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
534 /* Return the representative node for NODE, if NODE has been unioned
536 This function performs path compression along the way to finding
537 the representative. */
540 find (unsigned int node)
542 gcc_assert (node < graph->size);
543 if (graph->rep[node] != node)
544 return graph->rep[node] = find (graph->rep[node]);
548 /* Union the TO and FROM nodes to the TO nodes.
549 Note that at some point in the future, we may want to do
550 union-by-rank, in which case we are going to have to return the
551 node we unified to. */
554 unite (unsigned int to, unsigned int from)
556 gcc_assert (to < graph->size && from < graph->size);
557 if (to != from && graph->rep[from] != to)
559 graph->rep[from] = to;
565 /* Create a new constraint consisting of LHS and RHS expressions. */
568 new_constraint (const struct constraint_expr lhs,
569 const struct constraint_expr rhs)
571 constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
577 /* Print out constraint C to FILE. */
580 dump_constraint (FILE *file, constraint_t c)
582 if (c->lhs.type == ADDRESSOF)
584 else if (c->lhs.type == DEREF)
586 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
587 if (c->lhs.offset != 0)
588 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
589 fprintf (file, " = ");
590 if (c->rhs.type == ADDRESSOF)
592 else if (c->rhs.type == DEREF)
594 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
595 if (c->rhs.offset != 0)
596 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
597 fprintf (file, "\n");
600 /* Print out constraint C to stderr. */
603 debug_constraint (constraint_t c)
605 dump_constraint (stderr, c);
608 /* Print out all constraints to FILE */
611 dump_constraints (FILE *file)
615 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
616 dump_constraint (file, c);
619 /* Print out all constraints to stderr. */
622 debug_constraints (void)
624 dump_constraints (stderr);
629 The solver is a simple worklist solver, that works on the following
632 sbitmap changed_nodes = all zeroes;
634 For each node that is not already collapsed:
636 set bit in changed nodes
638 while (changed_count > 0)
640 compute topological ordering for constraint graph
642 find and collapse cycles in the constraint graph (updating
643 changed if necessary)
645 for each node (n) in the graph in topological order:
648 Process each complex constraint associated with the node,
649 updating changed if necessary.
651 For each outgoing edge from n, propagate the solution from n to
652 the destination of the edge, updating changed as necessary.
656 /* Return true if two constraint expressions A and B are equal. */
659 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
661 return a.type == b.type && a.var == b.var && a.offset == b.offset;
664 /* Return true if constraint expression A is less than constraint expression
665 B. This is just arbitrary, but consistent, in order to give them an
669 constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
671 if (a.type == b.type)
674 return a.offset < b.offset;
676 return a.var < b.var;
679 return a.type < b.type;
682 /* Return true if constraint A is less than constraint B. This is just
683 arbitrary, but consistent, in order to give them an ordering. */
686 constraint_less (const constraint_t a, const constraint_t b)
688 if (constraint_expr_less (a->lhs, b->lhs))
690 else if (constraint_expr_less (b->lhs, a->lhs))
693 return constraint_expr_less (a->rhs, b->rhs);
696 /* Return true if two constraints A and B are equal. */
699 constraint_equal (struct constraint a, struct constraint b)
701 return constraint_expr_equal (a.lhs, b.lhs)
702 && constraint_expr_equal (a.rhs, b.rhs);
706 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */
709 constraint_vec_find (VEC(constraint_t,heap) *vec,
710 struct constraint lookfor)
718 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
719 if (place >= VEC_length (constraint_t, vec))
721 found = VEC_index (constraint_t, vec, place);
722 if (!constraint_equal (*found, lookfor))
727 /* Union two constraint vectors, TO and FROM. Put the result in TO. */
730 constraint_set_union (VEC(constraint_t,heap) **to,
731 VEC(constraint_t,heap) **from)
736 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
738 if (constraint_vec_find (*to, *c) == NULL)
740 unsigned int place = VEC_lower_bound (constraint_t, *to, c,
742 VEC_safe_insert (constraint_t, heap, *to, place, c);
747 /* Take a solution set SET, add OFFSET to each member of the set, and
748 overwrite SET with the result when done. */
751 solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
753 bitmap result = BITMAP_ALLOC (&iteration_obstack);
757 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
759 varinfo_t vi = get_varinfo (i);
761 /* If this is a variable with just one field just set its bit
763 if (vi->is_artificial_var
764 || vi->is_unknown_size_var
766 bitmap_set_bit (result, i);
769 unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
770 varinfo_t v = first_vi_for_offset (vi, fieldoffset);
771 /* If the result is outside of the variable use the last field. */
775 while (v->next != NULL)
778 bitmap_set_bit (result, v->id);
779 /* If the result is not exactly at fieldoffset include the next
780 field as well. See get_constraint_for_ptr_offset for more
782 if (v->offset != fieldoffset
784 bitmap_set_bit (result, v->next->id);
788 bitmap_copy (set, result);
789 BITMAP_FREE (result);
792 /* Union solution sets TO and FROM, and add INC to each member of FROM in the
796 set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
799 return bitmap_ior_into (to, from);
805 tmp = BITMAP_ALLOC (&iteration_obstack);
806 bitmap_copy (tmp, from);
807 solution_set_add (tmp, inc);
808 res = bitmap_ior_into (to, tmp);
814 /* Insert constraint C into the list of complex constraints for graph
818 insert_into_complex (constraint_graph_t graph,
819 unsigned int var, constraint_t c)
821 VEC (constraint_t, heap) *complex = graph->complex[var];
822 unsigned int place = VEC_lower_bound (constraint_t, complex, c,
825 /* Only insert constraints that do not already exist. */
826 if (place >= VEC_length (constraint_t, complex)
827 || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
828 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
832 /* Condense two variable nodes into a single variable node, by moving
833 all associated info from SRC to TO. */
836 merge_node_constraints (constraint_graph_t graph, unsigned int to,
842 gcc_assert (find (from) == to);
844 /* Move all complex constraints from src node into to node */
845 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
847 /* In complex constraints for node src, we may have either
848 a = *src, and *src = a, or an offseted constraint which are
849 always added to the rhs node's constraints. */
851 if (c->rhs.type == DEREF)
853 else if (c->lhs.type == DEREF)
858 constraint_set_union (&graph->complex[to], &graph->complex[from]);
859 VEC_free (constraint_t, heap, graph->complex[from]);
860 graph->complex[from] = NULL;
864 /* Remove edges involving NODE from GRAPH. */
867 clear_edges_for_node (constraint_graph_t graph, unsigned int node)
869 if (graph->succs[node])
870 BITMAP_FREE (graph->succs[node]);
873 /* Merge GRAPH nodes FROM and TO into node TO. */
876 merge_graph_nodes (constraint_graph_t graph, unsigned int to,
879 if (graph->indirect_cycles[from] != -1)
881 /* If we have indirect cycles with the from node, and we have
882 none on the to node, the to node has indirect cycles from the
883 from node now that they are unified.
884 If indirect cycles exist on both, unify the nodes that they
885 are in a cycle with, since we know they are in a cycle with
887 if (graph->indirect_cycles[to] == -1)
888 graph->indirect_cycles[to] = graph->indirect_cycles[from];
891 /* Merge all the successor edges. */
892 if (graph->succs[from])
894 if (!graph->succs[to])
895 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
896 bitmap_ior_into (graph->succs[to],
900 clear_edges_for_node (graph, from);
904 /* Add an indirect graph edge to GRAPH, going from TO to FROM if
905 it doesn't exist in the graph already. */
908 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
914 if (!graph->implicit_preds[to])
915 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
917 if (bitmap_set_bit (graph->implicit_preds[to], from))
918 stats.num_implicit_edges++;
921 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
922 it doesn't exist in the graph already.
923 Return false if the edge already existed, true otherwise. */
926 add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
929 if (!graph->preds[to])
930 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
931 bitmap_set_bit (graph->preds[to], from);
934 /* Add a graph edge to GRAPH, going from FROM to TO if
935 it doesn't exist in the graph already.
936 Return false if the edge already existed, true otherwise. */
939 add_graph_edge (constraint_graph_t graph, unsigned int to,
950 if (!graph->succs[from])
951 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
952 if (bitmap_set_bit (graph->succs[from], to))
955 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
963 /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
966 valid_graph_edge (constraint_graph_t graph, unsigned int src,
969 return (graph->succs[dest]
970 && bitmap_bit_p (graph->succs[dest], src));
973 /* Initialize the constraint graph structure to contain SIZE nodes. */
976 init_graph (unsigned int size)
980 graph = XCNEW (struct constraint_graph);
982 graph->succs = XCNEWVEC (bitmap, graph->size);
983 graph->indirect_cycles = XNEWVEC (int, graph->size);
984 graph->rep = XNEWVEC (unsigned int, graph->size);
985 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
986 graph->pe = XCNEWVEC (unsigned int, graph->size);
987 graph->pe_rep = XNEWVEC (int, graph->size);
989 for (j = 0; j < graph->size; j++)
992 graph->pe_rep[j] = -1;
993 graph->indirect_cycles[j] = -1;
997 /* Build the constraint graph, adding only predecessor edges right now. */
1000 build_pred_graph (void)
1006 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1007 graph->preds = XCNEWVEC (bitmap, graph->size);
1008 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1009 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1010 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1011 graph->points_to = XCNEWVEC (bitmap, graph->size);
1012 graph->eq_rep = XNEWVEC (int, graph->size);
1013 graph->direct_nodes = sbitmap_alloc (graph->size);
1014 graph->pt_used = sbitmap_alloc (graph->size);
1015 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1016 graph->number_incoming = XCNEWVEC (unsigned int, graph->size);
1017 sbitmap_zero (graph->direct_nodes);
1018 sbitmap_zero (graph->pt_used);
1020 for (j = 0; j < FIRST_REF_NODE; j++)
1022 if (!get_varinfo (j)->is_special_var)
1023 SET_BIT (graph->direct_nodes, j);
1026 for (j = 0; j < graph->size; j++)
1027 graph->eq_rep[j] = -1;
1029 for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
1030 graph->indirect_cycles[j] = -1;
1032 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1034 struct constraint_expr lhs = c->lhs;
1035 struct constraint_expr rhs = c->rhs;
1036 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
1037 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
1039 if (lhs.type == DEREF)
1042 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1043 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1045 else if (rhs.type == DEREF)
1048 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1049 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1051 RESET_BIT (graph->direct_nodes, lhsvar);
1053 else if (rhs.type == ADDRESSOF)
1056 if (graph->points_to[lhsvar] == NULL)
1057 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1058 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1060 if (graph->pointed_by[rhsvar] == NULL)
1061 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1062 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1064 /* Implicitly, *x = y */
1065 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1067 RESET_BIT (graph->direct_nodes, rhsvar);
1068 bitmap_set_bit (graph->address_taken, rhsvar);
1070 else if (lhsvar > anything_id
1071 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1074 add_pred_graph_edge (graph, lhsvar, rhsvar);
1075 /* Implicitly, *x = *y */
1076 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1077 FIRST_REF_NODE + rhsvar);
1079 else if (lhs.offset != 0 || rhs.offset != 0)
1081 if (rhs.offset != 0)
1082 RESET_BIT (graph->direct_nodes, lhs.var);
1083 else if (lhs.offset != 0)
1084 RESET_BIT (graph->direct_nodes, rhs.var);
1089 /* Build the constraint graph, adding successor edges. */
1092 build_succ_graph (void)
1097 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
1099 struct constraint_expr lhs;
1100 struct constraint_expr rhs;
1101 unsigned int lhsvar;
1102 unsigned int rhsvar;
1109 lhsvar = find (get_varinfo_fc (lhs.var)->id);
1110 rhsvar = find (get_varinfo_fc (rhs.var)->id);
1112 if (lhs.type == DEREF)
1114 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1115 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1117 else if (rhs.type == DEREF)
1119 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1120 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1122 else if (rhs.type == ADDRESSOF)
1125 gcc_assert (find (get_varinfo_fc (rhs.var)->id)
1126 == get_varinfo_fc (rhs.var)->id);
1127 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1129 else if (lhsvar > anything_id
1130 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1132 add_graph_edge (graph, lhsvar, rhsvar);
1138 /* Changed variables on the last iteration. */
1139 static unsigned int changed_count;
1140 static sbitmap changed;
1142 DEF_VEC_I(unsigned);
1143 DEF_VEC_ALLOC_I(unsigned,heap);
1146 /* Strongly Connected Component visitation info. */
1153 unsigned int *node_mapping;
1155 VEC(unsigned,heap) *scc_stack;
1159 /* Recursive routine to find strongly connected components in GRAPH.
1160 SI is the SCC info to store the information in, and N is the id of current
1161 graph node we are processing.
1163 This is Tarjan's strongly connected component finding algorithm, as
1164 modified by Nuutila to keep only non-root nodes on the stack.
1165 The algorithm can be found in "On finding the strongly connected
1166 connected components in a directed graph" by Esko Nuutila and Eljas
1167 Soisalon-Soininen, in Information Processing Letters volume 49,
1168 number 1, pages 9-14. */
1171 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1175 unsigned int my_dfs;
1177 SET_BIT (si->visited, n);
1178 si->dfs[n] = si->current_index ++;
1179 my_dfs = si->dfs[n];
1181 /* Visit all the successors. */
1182 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1186 if (i > LAST_REF_NODE)
1190 if (TEST_BIT (si->deleted, w))
1193 if (!TEST_BIT (si->visited, w))
1194 scc_visit (graph, si, w);
1196 unsigned int t = find (w);
1197 unsigned int nnode = find (n);
1198 gcc_assert (nnode == n);
1200 if (si->dfs[t] < si->dfs[nnode])
1201 si->dfs[n] = si->dfs[t];
1205 /* See if any components have been identified. */
1206 if (si->dfs[n] == my_dfs)
1208 if (VEC_length (unsigned, si->scc_stack) > 0
1209 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1211 bitmap scc = BITMAP_ALLOC (NULL);
1212 bool have_ref_node = n >= FIRST_REF_NODE;
1213 unsigned int lowest_node;
1216 bitmap_set_bit (scc, n);
1218 while (VEC_length (unsigned, si->scc_stack) != 0
1219 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1221 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1223 bitmap_set_bit (scc, w);
1224 if (w >= FIRST_REF_NODE)
1225 have_ref_node = true;
1228 lowest_node = bitmap_first_set_bit (scc);
1229 gcc_assert (lowest_node < FIRST_REF_NODE);
1231 /* Collapse the SCC nodes into a single node, and mark the
1233 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1235 if (i < FIRST_REF_NODE)
1237 if (unite (lowest_node, i))
1238 unify_nodes (graph, lowest_node, i, false);
1242 unite (lowest_node, i);
1243 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1247 SET_BIT (si->deleted, n);
1250 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1253 /* Unify node FROM into node TO, updating the changed count if
1254 necessary when UPDATE_CHANGED is true. */
1257 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1258 bool update_changed)
1261 gcc_assert (to != from && find (to) == to);
1262 if (dump_file && (dump_flags & TDF_DETAILS))
1263 fprintf (dump_file, "Unifying %s to %s\n",
1264 get_varinfo (from)->name,
1265 get_varinfo (to)->name);
1268 stats.unified_vars_dynamic++;
1270 stats.unified_vars_static++;
1272 merge_graph_nodes (graph, to, from);
1273 merge_node_constraints (graph, to, from);
1275 if (get_varinfo (from)->no_tbaa_pruning)
1276 get_varinfo (to)->no_tbaa_pruning = true;
1278 /* Mark TO as changed if FROM was changed. If TO was already marked
1279 as changed, decrease the changed count. */
1281 if (update_changed && TEST_BIT (changed, from))
1283 RESET_BIT (changed, from);
1284 if (!TEST_BIT (changed, to))
1285 SET_BIT (changed, to);
1288 gcc_assert (changed_count > 0);
1292 if (get_varinfo (from)->solution)
1294 /* If the solution changes because of the merging, we need to mark
1295 the variable as changed. */
1296 if (bitmap_ior_into (get_varinfo (to)->solution,
1297 get_varinfo (from)->solution))
1299 if (update_changed && !TEST_BIT (changed, to))
1301 SET_BIT (changed, to);
1306 BITMAP_FREE (get_varinfo (from)->solution);
1307 BITMAP_FREE (get_varinfo (from)->oldsolution);
1309 if (stats.iterations > 0)
1311 BITMAP_FREE (get_varinfo (to)->oldsolution);
1312 get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
1315 if (valid_graph_edge (graph, to, to))
1317 if (graph->succs[to])
1318 bitmap_clear_bit (graph->succs[to], to);
1322 /* Information needed to compute the topological ordering of a graph. */
1326 /* sbitmap of visited nodes. */
1328 /* Array that stores the topological order of the graph, *in
1330 VEC(unsigned,heap) *topo_order;
1334 /* Initialize and return a topological info structure. */
1336 static struct topo_info *
1337 init_topo_info (void)
1339 size_t size = graph->size;
1340 struct topo_info *ti = XNEW (struct topo_info);
1341 ti->visited = sbitmap_alloc (size);
1342 sbitmap_zero (ti->visited);
1343 ti->topo_order = VEC_alloc (unsigned, heap, 1);
1348 /* Free the topological sort info pointed to by TI. */
1351 free_topo_info (struct topo_info *ti)
1353 sbitmap_free (ti->visited);
1354 VEC_free (unsigned, heap, ti->topo_order);
1358 /* Visit the graph in topological order, and store the order in the
1359 topo_info structure. */
1362 topo_visit (constraint_graph_t graph, struct topo_info *ti,
1368 SET_BIT (ti->visited, n);
1370 if (graph->succs[n])
1371 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1373 if (!TEST_BIT (ti->visited, j))
1374 topo_visit (graph, ti, j);
1377 VEC_safe_push (unsigned, heap, ti->topo_order, n);
1380 /* Return true if variable N + OFFSET is a legal field of N. */
1383 type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
1385 varinfo_t ninfo = get_varinfo (n);
1387 /* For things we've globbed to single variables, any offset into the
1388 variable acts like the entire variable, so that it becomes offset
1390 if (ninfo->is_special_var
1391 || ninfo->is_artificial_var
1392 || ninfo->is_unknown_size_var
1393 || ninfo->is_full_var)
1398 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
1401 /* Process a constraint C that represents x = *y, using DELTA as the
1402 starting solution. */
1405 do_sd_constraint (constraint_graph_t graph, constraint_t c,
1408 unsigned int lhs = c->lhs.var;
1410 bitmap sol = get_varinfo (lhs)->solution;
1414 if (bitmap_bit_p (delta, anything_id))
1416 flag |= bitmap_set_bit (sol, anything_id);
1420 /* For x = *ESCAPED and x = *CALLUSED we want to compute the
1421 reachability set of the rhs var. As a pointer to a sub-field
1422 of a variable can also reach all other fields of the variable
1423 we simply have to expand the solution to contain all sub-fields
1424 if one sub-field is contained. */
1425 if (c->rhs.var == escaped_id
1426 || c->rhs.var == callused_id)
1429 /* In a first pass record all variables we need to add all
1430 sub-fields off. This avoids quadratic behavior. */
1431 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1433 varinfo_t v = get_varinfo (j);
1437 v = lookup_vi_for_tree (v->decl);
1438 if (v->next != NULL)
1441 vars = BITMAP_ALLOC (NULL);
1442 bitmap_set_bit (vars, v->id);
1445 /* In the second pass now do the addition to the solution and
1446 to speed up solving add it to the delta as well. */
1449 EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
1451 varinfo_t v = get_varinfo (j);
1452 for (; v != NULL; v = v->next)
1454 if (bitmap_set_bit (sol, v->id))
1457 bitmap_set_bit (delta, v->id);
1465 /* For each variable j in delta (Sol(y)), add
1466 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1467 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1469 unsigned HOST_WIDE_INT roffset = c->rhs.offset;
1470 if (type_safe (j, &roffset))
1473 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
1476 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1477 /* If the access is outside of the variable we can ignore it. */
1482 /* Adding edges from the special vars is pointless.
1483 They don't have sets that can change. */
1484 if (get_varinfo (t)->is_special_var)
1485 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1486 /* Merging the solution from ESCAPED needlessly increases
1487 the set. Use ESCAPED as representative instead.
1488 Same for CALLUSED. */
1489 else if (get_varinfo (t)->id == escaped_id
1490 || get_varinfo (t)->id == callused_id)
1491 flag |= bitmap_set_bit (sol, get_varinfo (t)->id);
1492 else if (add_graph_edge (graph, lhs, t))
1493 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1498 /* If the LHS solution changed, mark the var as changed. */
1501 get_varinfo (lhs)->solution = sol;
1502 if (!TEST_BIT (changed, lhs))
1504 SET_BIT (changed, lhs);
1510 /* Process a constraint C that represents *x = y. */
1513 do_ds_constraint (constraint_t c, bitmap delta)
1515 unsigned int rhs = c->rhs.var;
1516 bitmap sol = get_varinfo (rhs)->solution;
1520 if (bitmap_bit_p (sol, anything_id))
1522 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1524 varinfo_t jvi = get_varinfo (j);
1526 unsigned int loff = c->lhs.offset;
1527 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
1530 v = get_varinfo (j);
1531 if (!v->is_full_var)
1533 v = first_vi_for_offset (v, fieldoffset);
1534 /* If the access is outside of the variable we can ignore it. */
1540 if (bitmap_set_bit (get_varinfo (t)->solution, anything_id)
1541 && !TEST_BIT (changed, t))
1543 SET_BIT (changed, t);
1550 /* For each member j of delta (Sol(x)), add an edge from y to j and
1551 union Sol(y) into Sol(j) */
1552 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1554 unsigned HOST_WIDE_INT loff = c->lhs.offset;
1555 if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
1559 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
1562 v = first_vi_for_offset (get_varinfo (j), fieldoffset);
1563 /* If the access is outside of the variable we can ignore it. */
1567 tmp = get_varinfo (t)->solution;
1569 if (set_union_with_increment (tmp, sol, 0))
1571 get_varinfo (t)->solution = tmp;
1573 sol = get_varinfo (rhs)->solution;
1574 if (!TEST_BIT (changed, t))
1576 SET_BIT (changed, t);
1584 /* Handle a non-simple (simple meaning requires no iteration),
1585 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1588 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
1590 if (c->lhs.type == DEREF)
1592 if (c->rhs.type == ADDRESSOF)
1599 do_ds_constraint (c, delta);
1602 else if (c->rhs.type == DEREF)
1605 if (!(get_varinfo (c->lhs.var)->is_special_var))
1606 do_sd_constraint (graph, c, delta);
1614 gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
1615 solution = get_varinfo (c->rhs.var)->solution;
1616 tmp = get_varinfo (c->lhs.var)->solution;
1618 flag = set_union_with_increment (tmp, solution, c->rhs.offset);
1622 get_varinfo (c->lhs.var)->solution = tmp;
1623 if (!TEST_BIT (changed, c->lhs.var))
1625 SET_BIT (changed, c->lhs.var);
1632 /* Initialize and return a new SCC info structure. */
1634 static struct scc_info *
1635 init_scc_info (size_t size)
1637 struct scc_info *si = XNEW (struct scc_info);
1640 si->current_index = 0;
1641 si->visited = sbitmap_alloc (size);
1642 sbitmap_zero (si->visited);
1643 si->deleted = sbitmap_alloc (size);
1644 sbitmap_zero (si->deleted);
1645 si->node_mapping = XNEWVEC (unsigned int, size);
1646 si->dfs = XCNEWVEC (unsigned int, size);
1648 for (i = 0; i < size; i++)
1649 si->node_mapping[i] = i;
1651 si->scc_stack = VEC_alloc (unsigned, heap, 1);
1655 /* Free an SCC info structure pointed to by SI */
1658 free_scc_info (struct scc_info *si)
1660 sbitmap_free (si->visited);
1661 sbitmap_free (si->deleted);
1662 free (si->node_mapping);
1664 VEC_free (unsigned, heap, si->scc_stack);
1669 /* Find indirect cycles in GRAPH that occur, using strongly connected
1670 components, and note them in the indirect cycles map.
1672 This technique comes from Ben Hardekopf and Calvin Lin,
1673 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1674 Lines of Code", submitted to PLDI 2007. */
1677 find_indirect_cycles (constraint_graph_t graph)
1680 unsigned int size = graph->size;
1681 struct scc_info *si = init_scc_info (size);
1683 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1684 if (!TEST_BIT (si->visited, i) && find (i) == i)
1685 scc_visit (graph, si, i);
1690 /* Compute a topological ordering for GRAPH, and store the result in the
1691 topo_info structure TI. */
1694 compute_topo_order (constraint_graph_t graph,
1695 struct topo_info *ti)
1698 unsigned int size = graph->size;
1700 for (i = 0; i != size; ++i)
1701 if (!TEST_BIT (ti->visited, i) && find (i) == i)
1702 topo_visit (graph, ti, i);
1705 /* Structure used to for hash value numbering of pointer equivalence
1708 typedef struct equiv_class_label
1710 unsigned int equivalence_class;
1713 } *equiv_class_label_t;
1714 typedef const struct equiv_class_label *const_equiv_class_label_t;
1716 /* A hashtable for mapping a bitmap of labels->pointer equivalence
1718 static htab_t pointer_equiv_class_table;
1720 /* A hashtable for mapping a bitmap of labels->location equivalence
1722 static htab_t location_equiv_class_table;
1724 /* Hash function for a equiv_class_label_t */
1727 equiv_class_label_hash (const void *p)
1729 const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
1730 return ecl->hashcode;
1733 /* Equality function for two equiv_class_label_t's. */
1736 equiv_class_label_eq (const void *p1, const void *p2)
1738 const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
1739 const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
1740 return bitmap_equal_p (eql1->labels, eql2->labels);
1743 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
1747 equiv_class_lookup (htab_t table, bitmap labels)
1750 struct equiv_class_label ecl;
1752 ecl.labels = labels;
1753 ecl.hashcode = bitmap_hash (labels);
1755 slot = htab_find_slot_with_hash (table, &ecl,
1756 ecl.hashcode, NO_INSERT);
1760 return ((equiv_class_label_t) *slot)->equivalence_class;
1764 /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
1768 equiv_class_add (htab_t table, unsigned int equivalence_class,
1772 equiv_class_label_t ecl = XNEW (struct equiv_class_label);
1774 ecl->labels = labels;
1775 ecl->equivalence_class = equivalence_class;
1776 ecl->hashcode = bitmap_hash (labels);
1778 slot = htab_find_slot_with_hash (table, ecl,
1779 ecl->hashcode, INSERT);
1780 gcc_assert (!*slot);
1781 *slot = (void *) ecl;
1784 /* Perform offline variable substitution.
1786 This is a worst case quadratic time way of identifying variables
1787 that must have equivalent points-to sets, including those caused by
1788 static cycles, and single entry subgraphs, in the constraint graph.
1790 The technique is described in "Exploiting Pointer and Location
1791 Equivalence to Optimize Pointer Analysis. In the 14th International
1792 Static Analysis Symposium (SAS), August 2007." It is known as the
1793 "HU" algorithm, and is equivalent to value numbering the collapsed
1794 constraint graph including evaluating unions.
1796 The general method of finding equivalence classes is as follows:
1797 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1798 Initialize all non-REF nodes to be direct nodes.
1799 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1801 For each constraint containing the dereference, we also do the same
1804 We then compute SCC's in the graph and unify nodes in the same SCC,
1807 For each non-collapsed node x:
1808 Visit all unvisited explicit incoming edges.
1809 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1811 Lookup the equivalence class for pts(x).
1812 If we found one, equivalence_class(x) = found class.
1813 Otherwise, equivalence_class(x) = new class, and new_class is
1814 added to the lookup table.
1816 All direct nodes with the same equivalence class can be replaced
1817 with a single representative node.
1818 All unlabeled nodes (label == 0) are not pointers and all edges
1819 involving them can be eliminated.
1820 We perform these optimizations during rewrite_constraints
1822 In addition to pointer equivalence class finding, we also perform
1823 location equivalence class finding. This is the set of variables
1824 that always appear together in points-to sets. We use this to
1825 compress the size of the points-to sets. */
1827 /* Current maximum pointer equivalence class id. */
1828 static int pointer_equiv_class;
1830 /* Current maximum location equivalence class id. */
1831 static int location_equiv_class;
1833 /* Recursive routine to find strongly connected components in GRAPH,
1834 and label it's nodes with DFS numbers. */
1837 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1841 unsigned int my_dfs;
1843 gcc_assert (si->node_mapping[n] == n);
1844 SET_BIT (si->visited, n);
1845 si->dfs[n] = si->current_index ++;
1846 my_dfs = si->dfs[n];
1848 /* Visit all the successors. */
1849 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1851 unsigned int w = si->node_mapping[i];
1853 if (TEST_BIT (si->deleted, w))
1856 if (!TEST_BIT (si->visited, w))
1857 condense_visit (graph, si, w);
1859 unsigned int t = si->node_mapping[w];
1860 unsigned int nnode = si->node_mapping[n];
1861 gcc_assert (nnode == n);
1863 if (si->dfs[t] < si->dfs[nnode])
1864 si->dfs[n] = si->dfs[t];
1868 /* Visit all the implicit predecessors. */
1869 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1871 unsigned int w = si->node_mapping[i];
1873 if (TEST_BIT (si->deleted, w))
1876 if (!TEST_BIT (si->visited, w))
1877 condense_visit (graph, si, w);
1879 unsigned int t = si->node_mapping[w];
1880 unsigned int nnode = si->node_mapping[n];
1881 gcc_assert (nnode == n);
1883 if (si->dfs[t] < si->dfs[nnode])
1884 si->dfs[n] = si->dfs[t];
1888 /* See if any components have been identified. */
1889 if (si->dfs[n] == my_dfs)
1891 while (VEC_length (unsigned, si->scc_stack) != 0
1892 && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
1894 unsigned int w = VEC_pop (unsigned, si->scc_stack);
1895 si->node_mapping[w] = n;
1897 if (!TEST_BIT (graph->direct_nodes, w))
1898 RESET_BIT (graph->direct_nodes, n);
1900 /* Unify our nodes. */
1901 if (graph->preds[w])
1903 if (!graph->preds[n])
1904 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
1905 bitmap_ior_into (graph->preds[n], graph->preds[w]);
1907 if (graph->implicit_preds[w])
1909 if (!graph->implicit_preds[n])
1910 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
1911 bitmap_ior_into (graph->implicit_preds[n],
1912 graph->implicit_preds[w]);
1914 if (graph->points_to[w])
1916 if (!graph->points_to[n])
1917 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1918 bitmap_ior_into (graph->points_to[n],
1919 graph->points_to[w]);
1921 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1923 unsigned int rep = si->node_mapping[i];
1924 graph->number_incoming[rep]++;
1927 SET_BIT (si->deleted, n);
1930 VEC_safe_push (unsigned, heap, si->scc_stack, n);
1933 /* Label pointer equivalences. */
1936 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1940 SET_BIT (si->visited, n);
1942 if (!graph->points_to[n])
1943 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1945 /* Label and union our incoming edges's points to sets. */
1946 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1948 unsigned int w = si->node_mapping[i];
1949 if (!TEST_BIT (si->visited, w))
1950 label_visit (graph, si, w);
1952 /* Skip unused edges */
1953 if (w == n || graph->pointer_label[w] == 0)
1955 graph->number_incoming[w]--;
1958 if (graph->points_to[w])
1959 bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
1961 /* If all incoming edges to w have been processed and
1962 graph->points_to[w] was not stored in the hash table, we can
1964 graph->number_incoming[w]--;
1965 if (!graph->number_incoming[w] && !TEST_BIT (graph->pt_used, w))
1967 BITMAP_FREE (graph->points_to[w]);
1970 /* Indirect nodes get fresh variables. */
1971 if (!TEST_BIT (graph->direct_nodes, n))
1972 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
1974 if (!bitmap_empty_p (graph->points_to[n]))
1976 unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
1977 graph->points_to[n]);
1980 SET_BIT (graph->pt_used, n);
1981 label = pointer_equiv_class++;
1982 equiv_class_add (pointer_equiv_class_table,
1983 label, graph->points_to[n]);
1985 graph->pointer_label[n] = label;
1989 /* Perform offline variable substitution, discovering equivalence
1990 classes, and eliminating non-pointer variables. */
1992 static struct scc_info *
1993 perform_var_substitution (constraint_graph_t graph)
1996 unsigned int size = graph->size;
1997 struct scc_info *si = init_scc_info (size);
1999 bitmap_obstack_initialize (&iteration_obstack);
2000 pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
2001 equiv_class_label_eq, free);
2002 location_equiv_class_table = htab_create (511, equiv_class_label_hash,
2003 equiv_class_label_eq, free);
2004 pointer_equiv_class = 1;
2005 location_equiv_class = 1;
2007 /* Condense the nodes, which means to find SCC's, count incoming
2008 predecessors, and unite nodes in SCC's. */
2009 for (i = 0; i < FIRST_REF_NODE; i++)
2010 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2011 condense_visit (graph, si, si->node_mapping[i]);
2013 sbitmap_zero (si->visited);
2014 /* Actually the label the nodes for pointer equivalences */
2015 for (i = 0; i < FIRST_REF_NODE; i++)
2016 if (!TEST_BIT (si->visited, si->node_mapping[i]))
2017 label_visit (graph, si, si->node_mapping[i]);
2019 /* Calculate location equivalence labels. */
2020 for (i = 0; i < FIRST_REF_NODE; i++)
2027 if (!graph->pointed_by[i])
2029 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2031 /* Translate the pointed-by mapping for pointer equivalence
2033 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2035 bitmap_set_bit (pointed_by,
2036 graph->pointer_label[si->node_mapping[j]]);
2038 /* The original pointed_by is now dead. */
2039 BITMAP_FREE (graph->pointed_by[i]);
2041 /* Look up the location equivalence label if one exists, or make
2043 label = equiv_class_lookup (location_equiv_class_table,
2047 label = location_equiv_class++;
2048 equiv_class_add (location_equiv_class_table,
2053 if (dump_file && (dump_flags & TDF_DETAILS))
2054 fprintf (dump_file, "Found location equivalence for node %s\n",
2055 get_varinfo (i)->name);
2056 BITMAP_FREE (pointed_by);
2058 graph->loc_label[i] = label;
2062 if (dump_file && (dump_flags & TDF_DETAILS))
2063 for (i = 0; i < FIRST_REF_NODE; i++)
2065 bool direct_node = TEST_BIT (graph->direct_nodes, i);
2067 "Equivalence classes for %s node id %d:%s are pointer: %d"
2069 direct_node ? "Direct node" : "Indirect node", i,
2070 get_varinfo (i)->name,
2071 graph->pointer_label[si->node_mapping[i]],
2072 graph->loc_label[si->node_mapping[i]]);
2075 /* Quickly eliminate our non-pointer variables. */
2077 for (i = 0; i < FIRST_REF_NODE; i++)
2079 unsigned int node = si->node_mapping[i];
2081 if (graph->pointer_label[node] == 0)
2083 if (dump_file && (dump_flags & TDF_DETAILS))
2085 "%s is a non-pointer variable, eliminating edges.\n",
2086 get_varinfo (node)->name);
2087 stats.nonpointer_vars++;
2088 clear_edges_for_node (graph, node);
2095 /* Free information that was only necessary for variable
2099 free_var_substitution_info (struct scc_info *si)
2102 free (graph->pointer_label);
2103 free (graph->loc_label);
2104 free (graph->pointed_by);
2105 free (graph->points_to);
2106 free (graph->number_incoming);
2107 free (graph->eq_rep);
2108 sbitmap_free (graph->direct_nodes);
2109 sbitmap_free (graph->pt_used);
2110 htab_delete (pointer_equiv_class_table);
2111 htab_delete (location_equiv_class_table);
2112 bitmap_obstack_release (&iteration_obstack);
2115 /* Return an existing node that is equivalent to NODE, which has
2116 equivalence class LABEL, if one exists. Return NODE otherwise. */
2119 find_equivalent_node (constraint_graph_t graph,
2120 unsigned int node, unsigned int label)
2122 /* If the address version of this variable is unused, we can
2123 substitute it for anything else with the same label.
2124 Otherwise, we know the pointers are equivalent, but not the
2125 locations, and we can unite them later. */
2127 if (!bitmap_bit_p (graph->address_taken, node))
2129 gcc_assert (label < graph->size);
2131 if (graph->eq_rep[label] != -1)
2133 /* Unify the two variables since we know they are equivalent. */
2134 if (unite (graph->eq_rep[label], node))
2135 unify_nodes (graph, graph->eq_rep[label], node, false);
2136 return graph->eq_rep[label];
2140 graph->eq_rep[label] = node;
2141 graph->pe_rep[label] = node;
2146 gcc_assert (label < graph->size);
2147 graph->pe[node] = label;
2148 if (graph->pe_rep[label] == -1)
2149 graph->pe_rep[label] = node;
2155 /* Unite pointer equivalent but not location equivalent nodes in
2156 GRAPH. This may only be performed once variable substitution is
2160 unite_pointer_equivalences (constraint_graph_t graph)
2164 /* Go through the pointer equivalences and unite them to their
2165 representative, if they aren't already. */
2166 for (i = 0; i < FIRST_REF_NODE; i++)
2168 unsigned int label = graph->pe[i];
2171 int label_rep = graph->pe_rep[label];
2173 if (label_rep == -1)
2176 label_rep = find (label_rep);
2177 if (label_rep >= 0 && unite (label_rep, find (i)))
2178 unify_nodes (graph, label_rep, i, false);
2183 /* Move complex constraints to the GRAPH nodes they belong to. */
2186 move_complex_constraints (constraint_graph_t graph)
2191 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2195 struct constraint_expr lhs = c->lhs;
2196 struct constraint_expr rhs = c->rhs;
2198 if (lhs.type == DEREF)
2200 insert_into_complex (graph, lhs.var, c);
2202 else if (rhs.type == DEREF)
2204 if (!(get_varinfo (lhs.var)->is_special_var))
2205 insert_into_complex (graph, rhs.var, c);
2207 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2208 && (lhs.offset != 0 || rhs.offset != 0))
2210 insert_into_complex (graph, rhs.var, c);
2217 /* Optimize and rewrite complex constraints while performing
2218 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2219 result of perform_variable_substitution. */
2222 rewrite_constraints (constraint_graph_t graph,
2223 struct scc_info *si)
2229 for (j = 0; j < graph->size; j++)
2230 gcc_assert (find (j) == j);
2232 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
2234 struct constraint_expr lhs = c->lhs;
2235 struct constraint_expr rhs = c->rhs;
2236 unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id);
2237 unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id);
2238 unsigned int lhsnode, rhsnode;
2239 unsigned int lhslabel, rhslabel;
2241 lhsnode = si->node_mapping[lhsvar];
2242 rhsnode = si->node_mapping[rhsvar];
2243 lhslabel = graph->pointer_label[lhsnode];
2244 rhslabel = graph->pointer_label[rhsnode];
2246 /* See if it is really a non-pointer variable, and if so, ignore
2250 if (dump_file && (dump_flags & TDF_DETAILS))
2253 fprintf (dump_file, "%s is a non-pointer variable,"
2254 "ignoring constraint:",
2255 get_varinfo (lhs.var)->name);
2256 dump_constraint (dump_file, c);
2258 VEC_replace (constraint_t, constraints, i, NULL);
2264 if (dump_file && (dump_flags & TDF_DETAILS))
2267 fprintf (dump_file, "%s is a non-pointer variable,"
2268 "ignoring constraint:",
2269 get_varinfo (rhs.var)->name);
2270 dump_constraint (dump_file, c);
2272 VEC_replace (constraint_t, constraints, i, NULL);
2276 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2277 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2278 c->lhs.var = lhsvar;
2279 c->rhs.var = rhsvar;
2284 /* Eliminate indirect cycles involving NODE. Return true if NODE was
2285 part of an SCC, false otherwise. */
2288 eliminate_indirect_cycles (unsigned int node)
2290 if (graph->indirect_cycles[node] != -1
2291 && !bitmap_empty_p (get_varinfo (node)->solution))
2294 VEC(unsigned,heap) *queue = NULL;
2296 unsigned int to = find (graph->indirect_cycles[node]);
2299 /* We can't touch the solution set and call unify_nodes
2300 at the same time, because unify_nodes is going to do
2301 bitmap unions into it. */
2303 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2305 if (find (i) == i && i != to)
2308 VEC_safe_push (unsigned, heap, queue, i);
2313 VEC_iterate (unsigned, queue, queuepos, i);
2316 unify_nodes (graph, to, i, true);
2318 VEC_free (unsigned, heap, queue);
2324 /* Solve the constraint graph GRAPH using our worklist solver.
2325 This is based on the PW* family of solvers from the "Efficient Field
2326 Sensitive Pointer Analysis for C" paper.
2327 It works by iterating over all the graph nodes, processing the complex
2328 constraints and propagating the copy constraints, until everything stops
2329 changed. This corresponds to steps 6-8 in the solving list given above. */
2332 solve_graph (constraint_graph_t graph)
2334 unsigned int size = graph->size;
2339 changed = sbitmap_alloc (size);
2340 sbitmap_zero (changed);
2342 /* Mark all initial non-collapsed nodes as changed. */
2343 for (i = 0; i < size; i++)
2345 varinfo_t ivi = get_varinfo (i);
2346 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2347 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2348 || VEC_length (constraint_t, graph->complex[i]) > 0))
2350 SET_BIT (changed, i);
2355 /* Allocate a bitmap to be used to store the changed bits. */
2356 pts = BITMAP_ALLOC (&pta_obstack);
2358 while (changed_count > 0)
2361 struct topo_info *ti = init_topo_info ();
2364 bitmap_obstack_initialize (&iteration_obstack);
2366 compute_topo_order (graph, ti);
2368 while (VEC_length (unsigned, ti->topo_order) != 0)
2371 i = VEC_pop (unsigned, ti->topo_order);
2373 /* If this variable is not a representative, skip it. */
2377 /* In certain indirect cycle cases, we may merge this
2378 variable to another. */
2379 if (eliminate_indirect_cycles (i) && find (i) != i)
2382 /* If the node has changed, we need to process the
2383 complex constraints and outgoing edges again. */
2384 if (TEST_BIT (changed, i))
2389 VEC(constraint_t,heap) *complex = graph->complex[i];
2390 bool solution_empty;
2392 RESET_BIT (changed, i);
2395 /* Compute the changed set of solution bits. */
2396 bitmap_and_compl (pts, get_varinfo (i)->solution,
2397 get_varinfo (i)->oldsolution);
2399 if (bitmap_empty_p (pts))
2402 bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
2404 solution = get_varinfo (i)->solution;
2405 solution_empty = bitmap_empty_p (solution);
2407 /* Process the complex constraints */
2408 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
2410 /* XXX: This is going to unsort the constraints in
2411 some cases, which will occasionally add duplicate
2412 constraints during unification. This does not
2413 affect correctness. */
2414 c->lhs.var = find (c->lhs.var);
2415 c->rhs.var = find (c->rhs.var);
2417 /* The only complex constraint that can change our
2418 solution to non-empty, given an empty solution,
2419 is a constraint where the lhs side is receiving
2420 some set from elsewhere. */
2421 if (!solution_empty || c->lhs.type != DEREF)
2422 do_complex_constraint (graph, c, pts);
2425 solution_empty = bitmap_empty_p (solution);
2428 /* Do not propagate the ESCAPED/CALLUSED solutions. */
2430 && i != callused_id)
2434 /* Propagate solution to all successors. */
2435 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2441 unsigned int to = find (j);
2442 tmp = get_varinfo (to)->solution;
2445 /* Don't try to propagate to ourselves. */
2449 flag = set_union_with_increment (tmp, pts, 0);
2453 get_varinfo (to)->solution = tmp;
2454 if (!TEST_BIT (changed, to))
2456 SET_BIT (changed, to);
2464 free_topo_info (ti);
2465 bitmap_obstack_release (&iteration_obstack);
2469 sbitmap_free (changed);
2470 bitmap_obstack_release (&oldpta_obstack);
2473 /* Map from trees to variable infos. */
2474 static struct pointer_map_t *vi_for_tree;
2477 /* Insert ID as the variable id for tree T in the vi_for_tree map. */
2480 insert_vi_for_tree (tree t, varinfo_t vi)
2482 void **slot = pointer_map_insert (vi_for_tree, t);
2484 gcc_assert (*slot == NULL);
2488 /* Find the variable info for tree T in VI_FOR_TREE. If T does not
2489 exist in the map, return NULL, otherwise, return the varinfo we found. */
2492 lookup_vi_for_tree (tree t)
2494 void **slot = pointer_map_contains (vi_for_tree, t);
2498 return (varinfo_t) *slot;
2501 /* Return a printable name for DECL */
2504 alias_get_name (tree decl)
2506 const char *res = get_name (decl);
2508 int num_printed = 0;
2517 if (TREE_CODE (decl) == SSA_NAME)
2519 num_printed = asprintf (&temp, "%s_%u",
2520 alias_get_name (SSA_NAME_VAR (decl)),
2521 SSA_NAME_VERSION (decl));
2523 else if (DECL_P (decl))
2525 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
2527 if (num_printed > 0)
2529 res = ggc_strdup (temp);
2535 /* Find the variable id for tree T in the map.
2536 If T doesn't exist in the map, create an entry for it and return it. */
2539 get_vi_for_tree (tree t)
2541 void **slot = pointer_map_contains (vi_for_tree, t);
2543 return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
2545 return (varinfo_t) *slot;
2548 /* Get a constraint expression for a new temporary variable. */
2550 static struct constraint_expr
2551 get_constraint_exp_for_temp (tree t)
2553 struct constraint_expr cexpr;
2555 gcc_assert (SSA_VAR_P (t));
2557 cexpr.type = SCALAR;
2558 cexpr.var = get_vi_for_tree (t)->id;
2564 /* Get a constraint expression vector from an SSA_VAR_P node.
2565 If address_p is true, the result will be taken its address of. */
2568 get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
2570 struct constraint_expr cexpr;
2573 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2574 gcc_assert (SSA_VAR_P (t) || DECL_P (t));
2576 /* For parameters, get at the points-to set for the actual parm
2578 if (TREE_CODE (t) == SSA_NAME
2579 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2580 && SSA_NAME_IS_DEFAULT_DEF (t))
2582 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2586 vi = get_vi_for_tree (t);
2588 cexpr.type = SCALAR;
2590 /* If we determine the result is "anything", and we know this is readonly,
2591 say it points to readonly memory instead. */
2592 if (cexpr.var == anything_id && TREE_READONLY (t))
2595 cexpr.type = ADDRESSOF;
2596 cexpr.var = readonly_id;
2599 /* If we are not taking the address of the constraint expr, add all
2600 sub-fiels of the variable as well. */
2603 for (; vi; vi = vi->next)
2606 VEC_safe_push (ce_s, heap, *results, &cexpr);
2611 VEC_safe_push (ce_s, heap, *results, &cexpr);
2614 /* Process constraint T, performing various simplifications and then
2615 adding it to our list of overall constraints. */
2618 process_constraint (constraint_t t)
2620 struct constraint_expr rhs = t->rhs;
2621 struct constraint_expr lhs = t->lhs;
2623 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
2624 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
2626 /* ANYTHING == ANYTHING is pointless. */
2627 if (lhs.var == anything_id && rhs.var == anything_id)
2630 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
2631 else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
2636 process_constraint (t);
2638 /* This can happen in our IR with things like n->a = *p */
2639 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
2641 /* Split into tmp = *rhs, *lhs = tmp */
2642 tree rhsdecl = get_varinfo (rhs.var)->decl;
2643 tree pointertype = TREE_TYPE (rhsdecl);
2644 tree pointedtotype = TREE_TYPE (pointertype);
2645 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
2646 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
2648 process_constraint (new_constraint (tmplhs, rhs));
2649 process_constraint (new_constraint (lhs, tmplhs));
2651 else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
2653 /* Split into tmp = &rhs, *lhs = tmp */
2654 tree rhsdecl = get_varinfo (rhs.var)->decl;
2655 tree pointertype = TREE_TYPE (rhsdecl);
2656 tree tmpvar = create_tmp_var_raw (pointertype, "derefaddrtmp");
2657 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
2659 process_constraint (new_constraint (tmplhs, rhs));
2660 process_constraint (new_constraint (lhs, tmplhs));
2664 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
2665 VEC_safe_push (constraint_t, heap, constraints, t);
2669 /* Return true if T is a variable of a type that could contain
2673 could_have_pointers (tree t)
2675 tree type = TREE_TYPE (t);
2677 if (POINTER_TYPE_P (type)
2678 || AGGREGATE_TYPE_P (type)
2679 || TREE_CODE (type) == COMPLEX_TYPE)
2685 /* Return the position, in bits, of FIELD_DECL from the beginning of its
2688 static HOST_WIDE_INT
2689 bitpos_of_field (const tree fdecl)
2692 if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
2693 || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
2696 return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
2697 + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
2701 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the
2702 resulting constraint expressions in *RESULTS. */
2705 get_constraint_for_ptr_offset (tree ptr, tree offset,
2706 VEC (ce_s, heap) **results)
2708 struct constraint_expr *c;
2710 unsigned HOST_WIDE_INT rhsunitoffset, rhsoffset;
2712 /* If we do not do field-sensitive PTA adding offsets to pointers
2713 does not change the points-to solution. */
2714 if (!use_field_sensitive)
2716 get_constraint_for (ptr, results);
2720 /* If the offset is not a non-negative integer constant that fits
2721 in a HOST_WIDE_INT, we have to fall back to a conservative
2722 solution which includes all sub-fields of all pointed-to
2724 ??? As we do not have the ability to express this, fall back
2726 if (!host_integerp (offset, 1))
2728 struct constraint_expr temp;
2729 temp.var = anything_id;
2732 VEC_safe_push (ce_s, heap, *results, &temp);
2736 /* Make sure the bit-offset also fits. */
2737 rhsunitoffset = TREE_INT_CST_LOW (offset);
2738 rhsoffset = rhsunitoffset * BITS_PER_UNIT;
2739 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
2741 struct constraint_expr temp;
2742 temp.var = anything_id;
2745 VEC_safe_push (ce_s, heap, *results, &temp);
2749 get_constraint_for (ptr, results);
2753 /* As we are eventually appending to the solution do not use
2754 VEC_iterate here. */
2755 n = VEC_length (ce_s, *results);
2756 for (j = 0; j < n; j++)
2759 c = VEC_index (ce_s, *results, j);
2760 curr = get_varinfo (c->var);
2762 if (c->type == ADDRESSOF
2763 && !curr->is_full_var)
2765 varinfo_t temp, curr = get_varinfo (c->var);
2767 /* Search the sub-field which overlaps with the
2768 pointed-to offset. As we deal with positive offsets
2769 only, we can start the search from the current variable. */
2770 temp = first_vi_for_offset (curr, curr->offset + rhsoffset);
2772 /* If the result is outside of the variable we have to provide
2773 a conservative result, as the variable is still reachable
2774 from the resulting pointer (even though it technically
2775 cannot point to anything). The last sub-field is such
2776 a conservative result.
2777 ??? If we always had a sub-field for &object + 1 then
2778 we could represent this in a more precise way. */
2782 while (temp->next != NULL)
2787 /* If the found variable is not exactly at the pointed to
2788 result, we have to include the next variable in the
2789 solution as well. Otherwise two increments by offset / 2
2790 do not result in the same or a conservative superset
2792 if (temp->offset != curr->offset + rhsoffset
2793 && temp->next != NULL)
2795 struct constraint_expr c2;
2796 c2.var = temp->next->id;
2797 c2.type = ADDRESSOF;
2799 VEC_safe_push (ce_s, heap, *results, &c2);
2804 else if (c->type == ADDRESSOF
2805 /* If this varinfo represents a full variable just use it. */
2806 && curr->is_full_var)
2809 c->offset = rhsoffset;
2814 /* Given a COMPONENT_REF T, return the constraint_expr vector for it.
2815 If address_p is true the result will be taken its address of. */
2818 get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
2822 HOST_WIDE_INT bitsize = -1;
2823 HOST_WIDE_INT bitmaxsize = -1;
2824 HOST_WIDE_INT bitpos;
2826 struct constraint_expr *result;
2828 /* Some people like to do cute things like take the address of
2831 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
2832 forzero = TREE_OPERAND (forzero, 0);
2834 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
2836 struct constraint_expr temp;
2839 temp.var = integer_id;
2841 VEC_safe_push (ce_s, heap, *results, &temp);
2845 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
2847 /* Pretend to take the address of the base, we'll take care of
2848 adding the required subset of sub-fields below. */
2849 get_constraint_for_1 (t, results, true);
2850 gcc_assert (VEC_length (ce_s, *results) == 1);
2851 result = VEC_last (ce_s, *results);
2853 /* This can also happen due to weird offsetof type macros. */
2854 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
2855 result->type = SCALAR;
2857 if (result->type == SCALAR
2858 && get_varinfo (result->var)->is_full_var)
2859 /* For single-field vars do not bother about the offset. */
2861 else if (result->type == SCALAR)
2863 /* In languages like C, you can access one past the end of an
2864 array. You aren't allowed to dereference it, so we can
2865 ignore this constraint. When we handle pointer subtraction,
2866 we may have to do something cute here. */
2868 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
2871 /* It's also not true that the constraint will actually start at the
2872 right offset, it may start in some padding. We only care about
2873 setting the constraint to the first actual field it touches, so
2875 struct constraint_expr cexpr = *result;
2877 VEC_pop (ce_s, *results);
2879 for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
2881 if (ranges_overlap_p (curr->offset, curr->size,
2882 bitpos, bitmaxsize))
2884 cexpr.var = curr->id;
2885 VEC_safe_push (ce_s, heap, *results, &cexpr);
2890 /* If we are going to take the address of this field then
2891 to be able to compute reachability correctly add at least
2892 the last field of the variable. */
2894 && VEC_length (ce_s, *results) == 0)
2896 curr = get_varinfo (cexpr.var);
2897 while (curr->next != NULL)
2899 cexpr.var = curr->id;
2900 VEC_safe_push (ce_s, heap, *results, &cexpr);
2903 /* Assert that we found *some* field there. The user couldn't be
2904 accessing *only* padding. */
2905 /* Still the user could access one past the end of an array
2906 embedded in a struct resulting in accessing *only* padding. */
2907 gcc_assert (VEC_length (ce_s, *results) >= 1
2908 || ref_contains_array_ref (orig_t));
2910 else if (bitmaxsize == 0)
2912 if (dump_file && (dump_flags & TDF_DETAILS))
2913 fprintf (dump_file, "Access to zero-sized part of variable,"
2917 if (dump_file && (dump_flags & TDF_DETAILS))
2918 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
2920 else if (bitmaxsize == -1)
2922 /* We can't handle DEREF constraints with unknown size, we'll
2923 get the wrong answer. Punt and return anything. */
2924 result->var = anything_id;
2928 result->offset = bitpos;
2932 /* Dereference the constraint expression CONS, and return the result.
2933 DEREF (ADDRESSOF) = SCALAR
2934 DEREF (SCALAR) = DEREF
2935 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
2936 This is needed so that we can handle dereferencing DEREF constraints. */
2939 do_deref (VEC (ce_s, heap) **constraints)
2941 struct constraint_expr *c;
2944 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
2946 if (c->type == SCALAR)
2948 else if (c->type == ADDRESSOF)
2950 else if (c->type == DEREF)
2952 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
2953 struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
2954 process_constraint (new_constraint (tmplhs, *c));
2955 c->var = tmplhs.var;
2962 /* Given a tree T, return the constraint expression for it. */
2965 get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
2967 struct constraint_expr temp;
2969 /* x = integer is all glommed to a single variable, which doesn't
2970 point to anything by itself. That is, of course, unless it is an
2971 integer constant being treated as a pointer, in which case, we
2972 will return that this is really the addressof anything. This
2973 happens below, since it will fall into the default case. The only
2974 case we know something about an integer treated like a pointer is
2975 when it is the NULL pointer, and then we just say it points to
2977 if (TREE_CODE (t) == INTEGER_CST
2978 && integer_zerop (t))
2980 temp.var = nothing_id;
2981 temp.type = ADDRESSOF;
2983 VEC_safe_push (ce_s, heap, *results, &temp);
2987 /* String constants are read-only. */
2988 if (TREE_CODE (t) == STRING_CST)
2990 temp.var = readonly_id;
2993 VEC_safe_push (ce_s, heap, *results, &temp);
2997 switch (TREE_CODE_CLASS (TREE_CODE (t)))
2999 case tcc_expression:
3002 switch (TREE_CODE (t))
3006 struct constraint_expr *c;
3008 tree exp = TREE_OPERAND (t, 0);
3010 get_constraint_for_1 (exp, results, true);
3012 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
3014 if (c->type == DEREF)
3017 c->type = ADDRESSOF;
3023 /* XXX: In interprocedural mode, if we didn't have the
3024 body, we would need to do *each pointer argument =
3026 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
3029 tree heapvar = heapvar_lookup (t);
3031 if (heapvar == NULL)
3033 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
3034 DECL_EXTERNAL (heapvar) = 1;
3035 get_var_ann (heapvar)->is_heapvar = 1;
3036 if (gimple_referenced_vars (cfun))
3037 add_referenced_var (heapvar);
3038 heapvar_insert (t, heapvar);
3041 temp.var = create_variable_info_for (heapvar,
3042 alias_get_name (heapvar));
3044 vi = get_varinfo (temp.var);
3045 vi->is_artificial_var = 1;
3046 vi->is_heap_var = 1;
3047 temp.type = ADDRESSOF;
3049 VEC_safe_push (ce_s, heap, *results, &temp);
3059 switch (TREE_CODE (t))
3063 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
3068 case ARRAY_RANGE_REF:
3070 get_constraint_for_component_ref (t, results, address_p);
3078 switch (TREE_CODE (t))
3082 tree op = TREE_OPERAND (t, 0);
3084 /* Cast from non-pointer to pointers are bad news for us.
3085 Anything else, we see through */
3086 if (!(POINTER_TYPE_P (TREE_TYPE (t))
3087 && ! POINTER_TYPE_P (TREE_TYPE (op))))
3089 get_constraint_for_1 (op, results, address_p);
3101 if (TREE_CODE (t) == POINTER_PLUS_EXPR)
3103 get_constraint_for_ptr_offset (TREE_OPERAND (t, 0),
3104 TREE_OPERAND (t, 1), results);
3109 case tcc_exceptional:
3111 switch (TREE_CODE (t))
3115 get_constraint_for_1 (PHI_RESULT (t), results, address_p);
3120 get_constraint_for_ssa_var (t, results, address_p);
3127 case tcc_declaration:
3129 get_constraint_for_ssa_var (t, results, address_p);
3135 /* The default fallback is a constraint from anything. */
3136 temp.type = ADDRESSOF;
3137 temp.var = anything_id;
3139 VEC_safe_push (ce_s, heap, *results, &temp);
3142 /* Given a gimple tree T, return the constraint expression vector for it. */
3145 get_constraint_for (tree t, VEC (ce_s, heap) **results)
3147 gcc_assert (VEC_length (ce_s, *results) == 0);
3149 get_constraint_for_1 (t, results, false);
3152 /* Handle the structure copy case where we have a simple structure copy
3153 between LHS and RHS that is of SIZE (in bits)
3155 For each field of the lhs variable (lhsfield)
3156 For each field of the rhs variable at lhsfield.offset (rhsfield)
3157 add the constraint lhsfield = rhsfield
3159 If we fail due to some kind of type unsafety or other thing we
3160 can't handle, return false. We expect the caller to collapse the
3161 variable in that case. */
3164 do_simple_structure_copy (const struct constraint_expr lhs,
3165 const struct constraint_expr rhs,
3166 const unsigned HOST_WIDE_INT size)
3168 varinfo_t p = get_varinfo (lhs.var);
3169 unsigned HOST_WIDE_INT pstart, last;
3171 last = p->offset + size;
3172 for (; p && p->offset < last; p = p->next)
3175 struct constraint_expr templhs = lhs;
3176 struct constraint_expr temprhs = rhs;
3177 unsigned HOST_WIDE_INT fieldoffset;
3179 templhs.var = p->id;
3180 q = get_varinfo (temprhs.var);
3181 fieldoffset = p->offset - pstart;
3182 q = first_vi_for_offset (q, q->offset + fieldoffset);
3185 temprhs.var = q->id;
3186 process_constraint (new_constraint (templhs, temprhs));
3192 /* Handle the structure copy case where we have a structure copy between a
3193 aggregate on the LHS and a dereference of a pointer on the RHS
3194 that is of SIZE (in bits)
3196 For each field of the lhs variable (lhsfield)
3197 rhs.offset = lhsfield->offset
3198 add the constraint lhsfield = rhs
3202 do_rhs_deref_structure_copy (const struct constraint_expr lhs,
3203 const struct constraint_expr rhs,
3204 const unsigned HOST_WIDE_INT size)
3206 varinfo_t p = get_varinfo (lhs.var);
3207 unsigned HOST_WIDE_INT pstart,last;
3209 last = p->offset + size;
3211 for (; p && p->offset < last; p = p->next)
3214 struct constraint_expr templhs = lhs;
3215 struct constraint_expr temprhs = rhs;
3216 unsigned HOST_WIDE_INT fieldoffset;
3219 if (templhs.type == SCALAR)
3220 templhs.var = p->id;
3222 templhs.offset = p->offset;
3224 q = get_varinfo (temprhs.var);
3225 fieldoffset = p->offset - pstart;
3226 temprhs.offset += fieldoffset;
3227 process_constraint (new_constraint (templhs, temprhs));
3231 /* Handle the structure copy case where we have a structure copy
3232 between an aggregate on the RHS and a dereference of a pointer on
3233 the LHS that is of SIZE (in bits)
3235 For each field of the rhs variable (rhsfield)
3236 lhs.offset = rhsfield->offset
3237 add the constraint lhs = rhsfield
3241 do_lhs_deref_structure_copy (const struct constraint_expr lhs,
3242 const struct constraint_expr rhs,
3243 const unsigned HOST_WIDE_INT size)
3245 varinfo_t p = get_varinfo (rhs.var);
3246 unsigned HOST_WIDE_INT pstart,last;
3248 last = p->offset + size;
3250 for (; p && p->offset < last; p = p->next)
3253 struct constraint_expr templhs = lhs;
3254 struct constraint_expr temprhs = rhs;
3255 unsigned HOST_WIDE_INT fieldoffset;
3258 if (temprhs.type == SCALAR)
3259 temprhs.var = p->id;
3261 temprhs.offset = p->offset;
3263 q = get_varinfo (templhs.var);
3264 fieldoffset = p->offset - pstart;
3265 templhs.offset += fieldoffset;
3266 process_constraint (new_constraint (templhs, temprhs));
3270 /* Sometimes, frontends like to give us bad type information. This
3271 function will collapse all the fields from VAR to the end of VAR,
3272 into VAR, so that we treat those fields as a single variable.
3273 We return the variable they were collapsed into. */
3276 collapse_rest_of_var (unsigned int var)
3278 varinfo_t currvar = get_varinfo (var);
3281 for (field = currvar->next; field; field = field->next)
3284 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
3285 field->name, currvar->name);
3287 gcc_assert (field->collapsed_to == 0);
3288 field->collapsed_to = currvar->id;
3291 currvar->next = NULL;
3292 currvar->size = currvar->fullsize - currvar->offset;
3297 /* Handle aggregate copies by expanding into copies of the respective
3298 fields of the structures. */
3301 do_structure_copy (tree lhsop, tree rhsop)
3303 struct constraint_expr lhs, rhs, tmp;
3304 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
3306 unsigned HOST_WIDE_INT lhssize;
3307 unsigned HOST_WIDE_INT rhssize;
3309 /* Pretend we are taking the address of the constraint exprs.
3310 We deal with walking the sub-fields ourselves. */
3311 get_constraint_for_1 (lhsop, &lhsc, true);
3312 get_constraint_for_1 (rhsop, &rhsc, true);
3313 gcc_assert (VEC_length (ce_s, lhsc) == 1);
3314 gcc_assert (VEC_length (ce_s, rhsc) == 1);
3315 lhs = *(VEC_last (ce_s, lhsc));
3316 rhs = *(VEC_last (ce_s, rhsc));
3318 VEC_free (ce_s, heap, lhsc);
3319 VEC_free (ce_s, heap, rhsc);
3321 /* If we have special var = x, swap it around. */
3322 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
3329 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
3330 possible it's something we could handle. However, most cases falling
3331 into this are dealing with transparent unions, which are slightly
3333 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
3335 rhs.type = ADDRESSOF;
3336 rhs.var = anything_id;
3339 /* If the RHS is a special var, or an addressof, set all the LHS fields to
3340 that special var. */
3341 if (rhs.var <= integer_id)
3343 for (p = get_varinfo (lhs.var); p; p = p->next)
3345 struct constraint_expr templhs = lhs;
3346 struct constraint_expr temprhs = rhs;
3348 if (templhs.type == SCALAR )
3349 templhs.var = p->id;
3351 templhs.offset += p->offset;
3352 process_constraint (new_constraint (templhs, temprhs));
3357 tree rhstype = TREE_TYPE (rhsop);
3358 tree lhstype = TREE_TYPE (lhsop);
3362 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
3363 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
3365 /* If we have a variably sized types on the rhs or lhs, and a deref
3366 constraint, add the constraint, lhsconstraint = &ANYTHING.
3367 This is conservatively correct because either the lhs is an unknown
3368 sized var (if the constraint is SCALAR), or the lhs is a DEREF
3369 constraint, and every variable it can point to must be unknown sized
3370 anyway, so we don't need to worry about fields at all. */
3371 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
3372 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
3374 rhs.var = anything_id;
3375 rhs.type = ADDRESSOF;
3377 process_constraint (new_constraint (lhs, rhs));
3381 /* The size only really matters insofar as we don't set more or less of
3382 the variable. If we hit an unknown size var, the size should be the
3383 whole darn thing. */
3384 if (get_varinfo (rhs.var)->is_unknown_size_var)
3387 rhssize = TREE_INT_CST_LOW (rhstypesize);
3389 if (get_varinfo (lhs.var)->is_unknown_size_var)
3392 lhssize = TREE_INT_CST_LOW (lhstypesize);
3395 if (rhs.type == SCALAR && lhs.type == SCALAR)
3397 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
3399 lhs.var = collapse_rest_of_var (lhs.var);
3400 rhs.var = collapse_rest_of_var (rhs.var);
3405 process_constraint (new_constraint (lhs, rhs));
3408 else if (lhs.type != DEREF && rhs.type == DEREF)
3409 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3410 else if (lhs.type == DEREF && rhs.type != DEREF)
3411 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
3414 tree pointedtotype = lhstype;
3417 gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
3418 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
3419 do_structure_copy (tmpvar, rhsop);
3420 do_structure_copy (lhsop, tmpvar);
3425 /* Create a constraint ID = OP. */
3428 make_constraint_to (unsigned id, tree op)
3430 VEC(ce_s, heap) *rhsc = NULL;
3431 struct constraint_expr *c;
3432 struct constraint_expr includes;
3436 includes.offset = 0;
3437 includes.type = SCALAR;
3439 get_constraint_for (op, &rhsc);
3440 for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
3441 process_constraint (new_constraint (includes, *c));
3442 VEC_free (ce_s, heap, rhsc);
3445 /* Make constraints necessary to make OP escape. */
3448 make_escape_constraint (tree op)
3450 make_constraint_to (escaped_id, op);
3453 /* For non-IPA mode, generate constraints necessary for a call on the
3457 handle_rhs_call (tree rhs)
3460 call_expr_arg_iterator iter;
3462 FOR_EACH_CALL_EXPR_ARG (arg, iter, rhs)
3463 /* Find those pointers being passed, and make sure they end up
3464 pointing to anything. */
3465 if (could_have_pointers (arg))
3466 make_escape_constraint (arg);
3468 /* The static chain escapes as well. */
3469 if (CALL_EXPR_STATIC_CHAIN (rhs))
3470 make_escape_constraint (CALL_EXPR_STATIC_CHAIN (rhs));
3473 /* For non-IPA mode, generate constraints necessary for a call
3474 that returns a pointer and assigns it to LHS. This simply makes
3475 the LHS point to global and escaped variables. */
3478 handle_lhs_call (tree lhs, int flags)
3480 VEC(ce_s, heap) *lhsc = NULL;
3481 struct constraint_expr rhsc;
3483 struct constraint_expr *lhsp;
3485 get_constraint_for (lhs, &lhsc);
3487 if (flags & ECF_MALLOC)
3489 tree heapvar = heapvar_lookup (lhs);
3492 if (heapvar == NULL)
3494 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
3495 DECL_EXTERNAL (heapvar) = 1;
3496 get_var_ann (heapvar)->is_heapvar = 1;
3497 if (gimple_referenced_vars (cfun))
3498 add_referenced_var (heapvar);
3499 heapvar_insert (lhs, heapvar);
3502 rhsc.var = create_variable_info_for (heapvar,
3503 alias_get_name (heapvar));
3504 vi = get_varinfo (rhsc.var);
3505 vi->is_artificial_var = 1;
3506 vi->is_heap_var = 1;
3507 rhsc.type = ADDRESSOF;
3512 rhsc.var = escaped_id;
3514 rhsc.type = ADDRESSOF;
3516 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3517 process_constraint (new_constraint (*lhsp, rhsc));
3518 VEC_free (ce_s, heap, lhsc);
3521 /* For non-IPA mode, generate constraints necessary for a call of a
3522 const function that returns a pointer in the statement STMT. */
3525 handle_const_call (tree stmt)
3527 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3528 tree call = get_call_expr_in (stmt);
3529 VEC(ce_s, heap) *lhsc = NULL;
3530 struct constraint_expr rhsc;
3532 struct constraint_expr *lhsp;
3534 call_expr_arg_iterator iter;
3535 struct constraint_expr tmpc;
3537 get_constraint_for (lhs, &lhsc);
3539 /* If this is a nested function then it can return anything. */
3540 if (CALL_EXPR_STATIC_CHAIN (call))
3542 rhsc.var = anything_id;
3544 rhsc.type = ADDRESSOF;
3545 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3546 process_constraint (new_constraint (*lhsp, rhsc));
3547 VEC_free (ce_s, heap, lhsc);
3551 /* We always use a temporary here, otherwise we end up with a quadratic
3552 amount of constraints for
3553 large_struct = const_call (large_struct);
3554 in field-sensitive PTA. */
3555 tmpvar = create_tmp_var_raw (ptr_type_node, "consttmp");
3556 tmpc = get_constraint_exp_for_temp (tmpvar);
3558 /* May return addresses of globals. */
3559 rhsc.var = nonlocal_id;
3561 rhsc.type = ADDRESSOF;
3562 process_constraint (new_constraint (tmpc, rhsc));
3564 /* May return arguments. */
3565 FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
3566 if (could_have_pointers (arg))
3568 VEC(ce_s, heap) *argc = NULL;
3569 struct constraint_expr *argp;
3572 get_constraint_for (arg, &argc);
3573 for (i = 0; VEC_iterate (ce_s, argc, i, argp); i++)
3574 process_constraint (new_constraint (tmpc, *argp));
3575 VEC_free (ce_s, heap, argc);
3578 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3579 process_constraint (new_constraint (*lhsp, tmpc));
3581 VEC_free (ce_s, heap, lhsc);
3584 /* For non-IPA mode, generate constraints necessary for a call to a
3585 pure function in statement STMT. */
3588 handle_pure_call (tree stmt)
3590 tree call = get_call_expr_in (stmt);
3592 call_expr_arg_iterator iter;
3594 /* Memory reached from pointer arguments is call-used. */
3595 FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
3596 if (could_have_pointers (arg))
3597 make_constraint_to (callused_id, arg);
3599 /* The static chain is used as well. */
3600 if (CALL_EXPR_STATIC_CHAIN (call))
3601 make_constraint_to (callused_id, CALL_EXPR_STATIC_CHAIN (call));
3603 /* If the call returns a pointer it may point to reachable memory
3604 from the arguments. Not so for malloc functions though. */
3605 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3606 && could_have_pointers (GIMPLE_STMT_OPERAND (stmt, 0))
3607 && !(call_expr_flags (call) & ECF_MALLOC))
3609 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3610 VEC(ce_s, heap) *lhsc = NULL;
3611 struct constraint_expr rhsc;
3612 struct constraint_expr *lhsp;
3615 get_constraint_for (lhs, &lhsc);
3617 /* If this is a nested function then it can return anything. */
3618 if (CALL_EXPR_STATIC_CHAIN (call))
3620 rhsc.var = anything_id;
3622 rhsc.type = ADDRESSOF;
3623 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3624 process_constraint (new_constraint (*lhsp, rhsc));
3625 VEC_free (ce_s, heap, lhsc);
3629 /* Else just add the call-used memory here. Escaped variables
3630 and globals will be dealt with in handle_lhs_call. */
3631 rhsc.var = callused_id;
3633 rhsc.type = ADDRESSOF;
3634 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3635 process_constraint (new_constraint (*lhsp, rhsc));
3636 VEC_free (ce_s, heap, lhsc);
3640 /* Walk statement T setting up aliasing constraints according to the
3641 references found in T. This function is the main part of the
3642 constraint builder. AI points to auxiliary alias information used
3643 when building alias sets and computing alias grouping heuristics. */
3646 find_func_aliases (tree origt)
3648 tree call, t = origt;
3649 VEC(ce_s, heap) *lhsc = NULL;
3650 VEC(ce_s, heap) *rhsc = NULL;
3651 struct constraint_expr *c;
3652 enum escape_type stmt_escape_type;
3654 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
3655 t = TREE_OPERAND (t, 0);
3657 /* Now build constraints expressions. */
3658 if (TREE_CODE (t) == PHI_NODE)
3660 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))));
3662 /* Only care about pointers and structures containing
3664 if (could_have_pointers (PHI_RESULT (t)))
3669 /* For a phi node, assign all the arguments to
3671 get_constraint_for (PHI_RESULT (t), &lhsc);
3672 for (i = 0; i < PHI_NUM_ARGS (t); i++)
3675 tree strippedrhs = PHI_ARG_DEF (t, i);
3677 STRIP_NOPS (strippedrhs);
3678 rhstype = TREE_TYPE (strippedrhs);
3679 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
3681 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3683 struct constraint_expr *c2;
3684 while (VEC_length (ce_s, rhsc) > 0)
3686 c2 = VEC_last (ce_s, rhsc);
3687 process_constraint (new_constraint (*c, *c2));
3688 VEC_pop (ce_s, rhsc);
3694 /* In IPA mode, we need to generate constraints to pass call
3695 arguments through their calls. There are two cases, either a
3696 GIMPLE_MODIFY_STMT when we are returning a value, or just a plain
3697 CALL_EXPR when we are not.
3699 In non-ipa mode, we need to generate constraints for each
3700 pointer passed by address. */
3701 else if ((call = get_call_expr_in (t)) != NULL_TREE)
3703 int flags = call_expr_flags (call);
3706 /* Const functions can return their arguments and addresses
3707 of global memory but not of escaped memory. */
3708 if (flags & ECF_CONST)
3710 if (TREE_CODE (t) == GIMPLE_MODIFY_STMT
3711 && could_have_pointers (GIMPLE_STMT_OPERAND (t, 1)))
3712 handle_const_call (t);
3714 else if (flags & ECF_PURE)
3716 handle_pure_call (t);
3717 if (TREE_CODE (t) == GIMPLE_MODIFY_STMT
3718 && could_have_pointers (GIMPLE_STMT_OPERAND (t, 1)))
3719 handle_lhs_call (GIMPLE_STMT_OPERAND (t, 0), flags);
3721 /* Pure functions can return addresses in and of memory
3722 reachable from their arguments, but they are not an escape
3723 point for reachable memory of their arguments. But as we
3724 do not compute call-used memory separately we cannot do
3725 something special here. */
3726 else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
3728 handle_rhs_call (GIMPLE_STMT_OPERAND (t, 1));
3729 if (could_have_pointers (GIMPLE_STMT_OPERAND (t, 1)))
3730 handle_lhs_call (GIMPLE_STMT_OPERAND (t, 0), flags);
3733 handle_rhs_call (t);
3740 call_expr_arg_iterator iter;
3744 if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
3746 lhsop = GIMPLE_STMT_OPERAND (t, 0);
3747 rhsop = GIMPLE_STMT_OPERAND (t, 1);
3754 decl = get_callee_fndecl (rhsop);
3756 /* If we can directly resolve the function being called, do so.
3757 Otherwise, it must be some sort of indirect expression that
3758 we should still be able to handle. */
3761 fi = get_vi_for_tree (decl);
3765 decl = CALL_EXPR_FN (rhsop);
3766 fi = get_vi_for_tree (decl);
3769 /* Assign all the passed arguments to the appropriate incoming
3770 parameters of the function. */
3772 FOR_EACH_CALL_EXPR_ARG (arg, iter, rhsop)
3774 struct constraint_expr lhs ;
3775 struct constraint_expr *rhsp;
3777 get_constraint_for (arg, &rhsc);
3778 if (TREE_CODE (decl) != FUNCTION_DECL)
3787 lhs.var = first_vi_for_offset (fi, i)->id;
3790 while (VEC_length (ce_s, rhsc) != 0)
3792 rhsp = VEC_last (ce_s, rhsc);
3793 process_constraint (new_constraint (lhs, *rhsp));
3794 VEC_pop (ce_s, rhsc);
3799 /* If we are returning a value, assign it to the result. */
3802 struct constraint_expr rhs;
3803 struct constraint_expr *lhsp;
3806 get_constraint_for (lhsop, &lhsc);
3807 if (TREE_CODE (decl) != FUNCTION_DECL)
3816 rhs.var = first_vi_for_offset (fi, i)->id;
3819 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
3820 process_constraint (new_constraint (*lhsp, rhs));
3824 /* Otherwise, just a regular assignment statement. Only care about
3825 operations with pointer result, others are dealt with as escape
3826 points if they have pointer operands. */
3827 else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT
3828 && could_have_pointers (GIMPLE_STMT_OPERAND (t, 0)))
3830 tree lhsop = GIMPLE_STMT_OPERAND (t, 0);
3831 tree rhsop = GIMPLE_STMT_OPERAND (t, 1);
3833 if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
3834 do_structure_copy (lhsop, rhsop);
3838 get_constraint_for (lhsop, &lhsc);
3839 get_constraint_for (rhsop, &rhsc);
3840 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
3842 struct constraint_expr *c2;
3845 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
3846 process_constraint (new_constraint (*c, *c2));
3850 else if (TREE_CODE (t) == CHANGE_DYNAMIC_TYPE_EXPR)
3854 get_constraint_for (CHANGE_DYNAMIC_TYPE_LOCATION (t), &lhsc);
3855 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); ++j)
3856 get_varinfo (c->var)->no_tbaa_pruning = true;
3859 stmt_escape_type = is_escape_site (t);
3860 if (stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
3863 gcc_assert (TREE_CODE (t) == GIMPLE_MODIFY_STMT);
3864 rhs = GIMPLE_STMT_OPERAND (t, 1);
3865 if (TREE_CODE (rhs) == ADDR_EXPR)
3867 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3870 || !is_global_var (base)))
3871 make_escape_constraint (rhs);
3873 else if (TREE_CODE (rhs) == SSA_NAME
3874 && POINTER_TYPE_P (TREE_TYPE (rhs)))
3875 make_escape_constraint (rhs);
3876 else if (could_have_pointers (rhs))
3877 make_escape_constraint (rhs);
3879 else if (stmt_escape_type == ESCAPE_BAD_CAST)
3882 gcc_assert (TREE_CODE (t) == GIMPLE_MODIFY_STMT);
3883 rhs = GIMPLE_STMT_OPERAND (t, 1);
3884 gcc_assert (CONVERT_EXPR_P (rhs)
3885 || TREE_CODE (rhs) == VIEW_CONVERT_EXPR);
3886 rhs = TREE_OPERAND (rhs, 0);
3887 make_escape_constraint (rhs);
3889 else if (stmt_escape_type == ESCAPE_TO_ASM)
3893 for (i = 0, link = ASM_OUTPUTS (t); link; i++, link = TREE_CHAIN (link))
3895 tree op = TREE_VALUE (link);
3896 if (op && could_have_pointers (op))
3897 /* Strictly we'd only need the constraints from ESCAPED and
3899 make_escape_constraint (op);
3901 for (i = 0, link = ASM_INPUTS (t); link; i++, link = TREE_CHAIN (link))
3903 tree op = TREE_VALUE (link);
3904 if (op && could_have_pointers (op))
3905 /* Strictly we'd only need the constraint to ESCAPED. */
3906 make_escape_constraint (op);
3910 /* After promoting variables and computing aliasing we will
3911 need to re-scan most statements. FIXME: Try to minimize the
3912 number of statements re-scanned. It's not really necessary to
3913 re-scan *all* statements. */
3915 mark_stmt_modified (origt);
3916 VEC_free (ce_s, heap, rhsc);
3917 VEC_free (ce_s, heap, lhsc);
3921 /* Find the first varinfo in the same variable as START that overlaps with
3923 Effectively, walk the chain of fields for the variable START to find the
3924 first field that overlaps with OFFSET.
3925 Return NULL if we can't find one. */
3928 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
3930 varinfo_t curr = start;
3933 /* We may not find a variable in the field list with the actual
3934 offset when when we have glommed a structure to a variable.
3935 In that case, however, offset should still be within the size
3937 if (offset >= curr->offset && offset < (curr->offset + curr->size))
3945 /* Insert the varinfo FIELD into the field list for BASE, at the front
3949 insert_into_field_list (varinfo_t base, varinfo_t field)
3951 varinfo_t prev = base;
3952 varinfo_t curr = base->next;
3958 /* Insert the varinfo FIELD into the field list for BASE, ordered by
3962 insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
3964 varinfo_t prev = base;
3965 varinfo_t curr = base->next;
3976 if (field->offset <= curr->offset)
3981 field->next = prev->next;
3986 /* This structure is used during pushing fields onto the fieldstack
3987 to track the offset of the field, since bitpos_of_field gives it
3988 relative to its immediate containing type, and we want it relative
3989 to the ultimate containing object. */
3993 /* Offset from the base of the base containing object to this field. */
3994 HOST_WIDE_INT offset;
3996 /* Size, in bits, of the field. */
3997 unsigned HOST_WIDE_INT size;
3999 unsigned has_unknown_size : 1;
4001 unsigned may_have_pointers : 1;
4003 typedef struct fieldoff fieldoff_s;
4005 DEF_VEC_O(fieldoff_s);
4006 DEF_VEC_ALLOC_O(fieldoff_s,heap);
4008 /* qsort comparison function for two fieldoff's PA and PB */
4011 fieldoff_compare (const void *pa, const void *pb)
4013 const fieldoff_s *foa = (const fieldoff_s *)pa;
4014 const fieldoff_s *fob = (const fieldoff_s *)pb;
4015 unsigned HOST_WIDE_INT foasize, fobsize;
4017 if (foa->offset < fob->offset)
4019 else if (foa->offset > fob->offset)
4022 foasize = foa->size;
4023 fobsize = fob->size;
4024 if (foasize < fobsize)
4026 else if (foasize > fobsize)
4031 /* Sort a fieldstack according to the field offset and sizes. */
4033 sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
4035 qsort (VEC_address (fieldoff_s, fieldstack),
4036 VEC_length (fieldoff_s, fieldstack),
4037 sizeof (fieldoff_s),
4041 /* Return true if V is a tree that we can have subvars for.
4042 Normally, this is any aggregate type. Also complex
4043 types which are not gimple registers can have subvars. */
4046 var_can_have_subvars (const_tree v)
4048 /* Volatile variables should never have subvars. */
4049 if (TREE_THIS_VOLATILE (v))
4052 /* Non decls or memory tags can never have subvars. */
4053 if (!DECL_P (v) || MTAG_P (v))
4056 /* Aggregates without overlapping fields can have subvars. */
4057 if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
4063 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
4064 the fields of TYPE onto fieldstack, recording their offsets along
4067 OFFSET is used to keep track of the offset in this entire
4068 structure, rather than just the immediately containing structure.
4069 Returns the number of fields pushed. */
4072 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
4073 HOST_WIDE_INT offset)
4078 if (TREE_CODE (type) != RECORD_TYPE)
4081 /* If the vector of fields is growing too big, bail out early.
4082 Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
4084 if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
4087 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
4088 if (TREE_CODE (field) == FIELD_DECL)
4092 HOST_WIDE_INT foff = bitpos_of_field (field);
4094 if (!var_can_have_subvars (field)
4095 || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
4096 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
4098 else if (!(pushed = push_fields_onto_fieldstack
4099 (TREE_TYPE (field), fieldstack, offset + foff))
4100 && (DECL_SIZE (field)
4101 && !integer_zerop (DECL_SIZE (field))))
4102 /* Empty structures may have actual size, like in C++. So
4103 see if we didn't push any subfields and the size is
4104 nonzero, push the field onto the stack. */
4109 fieldoff_s *pair = NULL;
4110 bool has_unknown_size = false;
4112 if (!VEC_empty (fieldoff_s, *fieldstack))
4113 pair = VEC_last (fieldoff_s, *fieldstack);
4115 if (!DECL_SIZE (field)
4116 || !host_integerp (DECL_SIZE (field), 1))
4117 has_unknown_size = true;
4119 /* If adjacent fields do not contain pointers merge them. */
4121 && !pair->may_have_pointers
4122 && !could_have_pointers (field)
4123 && !pair->has_unknown_size
4124 && !has_unknown_size
4125 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
4127 pair = VEC_last (fieldoff_s, *fieldstack);
4128 pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
4132 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
4133 pair->offset = offset + foff;
4134 pair->has_unknown_size = has_unknown_size;
4135 if (!has_unknown_size)
4136 pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
4139 pair->may_have_pointers = could_have_pointers (field);
4150 /* Create a constraint ID = &FROM. */
4153 make_constraint_from (varinfo_t vi, int from)
4155 struct constraint_expr lhs, rhs;
4163 rhs.type = ADDRESSOF;
4164 process_constraint (new_constraint (lhs, rhs));
4167 /* Count the number of arguments DECL has, and set IS_VARARGS to true
4168 if it is a varargs function. */
4171 count_num_arguments (tree decl, bool *is_varargs)
4176 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
4180 if (TREE_VALUE (t) == void_type_node)
4190 /* Creation function node for DECL, using NAME, and return the index
4191 of the variable we've created for the function. */
4194 create_function_info_for (tree decl, const char *name)
4196 unsigned int index = VEC_length (varinfo_t, varmap);
4200 bool is_varargs = false;
4202 /* Create the variable info. */
4204 vi = new_var_info (decl, index, name);
4208 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
4209 insert_vi_for_tree (vi->decl, vi);
4210 VEC_safe_push (varinfo_t, heap, varmap, vi);
4214 /* If it's varargs, we don't know how many arguments it has, so we
4220 vi->is_unknown_size_var = true;
4225 arg = DECL_ARGUMENTS (decl);
4227 /* Set up variables for each argument. */
4228 for (i = 1; i < vi->fullsize; i++)
4231 const char *newname;
4233 unsigned int newindex;
4234 tree argdecl = decl;
4239 newindex = VEC_length (varinfo_t, varmap);
4240 asprintf (&tempname, "%s.arg%d", name, i-1);
4241 newname = ggc_strdup (tempname);
4244 argvi = new_var_info (argdecl, newindex, newname);
4245 argvi->decl = argdecl;
4246 VEC_safe_push (varinfo_t, heap, varmap, argvi);
4249 argvi->is_full_var = true;
4250 argvi->fullsize = vi->fullsize;
4251 insert_into_field_list_sorted (vi, argvi);
4252 stats.total_vars ++;
4255 insert_vi_for_tree (arg, argvi);
4256 arg = TREE_CHAIN (arg);
4260 /* Create a variable for the return var. */
4261 if (DECL_RESULT (decl) != NULL
4262 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
4265 const char *newname;
4267 unsigned int newindex;
4268 tree resultdecl = decl;
4272 if (DECL_RESULT (decl))
4273 resultdecl = DECL_RESULT (decl);
4275 newindex = VEC_length (varinfo_t, varmap);
4276 asprintf (&tempname, "%s.result", name);
4277 newname = ggc_strdup (tempname);
4280 resultvi = new_var_info (resultdecl, newindex, newname);
4281 resultvi->decl = resultdecl;
4282 VEC_safe_push (varinfo_t, heap, varmap, resultvi);
4283 resultvi->offset = i;
4285 resultvi->fullsize = vi->fullsize;
4286 resultvi->is_full_var = true;
4287 insert_into_field_list_sorted (vi, resultvi);
4288 stats.total_vars ++;
4289 if (DECL_RESULT (decl))
4290 insert_vi_for_tree (DECL_RESULT (decl), resultvi);
4296 /* Return true if FIELDSTACK contains fields that overlap.
4297 FIELDSTACK is assumed to be sorted by offset. */
4300 check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
4302 fieldoff_s *fo = NULL;
4304 HOST_WIDE_INT lastoffset = -1;
4306 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4308 if (fo->offset == lastoffset)
4310 lastoffset = fo->offset;
4315 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
4316 This will also create any varinfo structures necessary for fields
4320 create_variable_info_for (tree decl, const char *name)
4322 unsigned int index = VEC_length (varinfo_t, varmap);
4324 tree decltype = TREE_TYPE (decl);
4325 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
4326 bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
4327 VEC (fieldoff_s,heap) *fieldstack = NULL;
4329 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
4330 return create_function_info_for (decl, name);
4332 if (var_can_have_subvars (decl) && use_field_sensitive)
4333 push_fields_onto_fieldstack (decltype, &fieldstack, 0);
4335 /* If the variable doesn't have subvars, we may end up needing to
4336 sort the field list and create fake variables for all the
4338 vi = new_var_info (decl, index, name);
4342 || !host_integerp (declsize, 1))
4344 vi->is_unknown_size_var = true;
4350 vi->fullsize = TREE_INT_CST_LOW (declsize);
4351 vi->size = vi->fullsize;
4354 insert_vi_for_tree (vi->decl, vi);
4355 VEC_safe_push (varinfo_t, heap, varmap, vi);
4356 if (is_global && (!flag_whole_program || !in_ipa_mode)
4357 && could_have_pointers (decl))
4358 make_constraint_from (vi, escaped_id);
4361 if (use_field_sensitive
4362 && !vi->is_unknown_size_var
4363 && var_can_have_subvars (decl)
4364 && VEC_length (fieldoff_s, fieldstack) > 1
4365 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
4367 unsigned int newindex = VEC_length (varinfo_t, varmap);
4368 fieldoff_s *fo = NULL;
4369 bool notokay = false;
4372 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
4374 if (fo->has_unknown_size
4382 /* We can't sort them if we have a field with a variable sized type,
4383 which will make notokay = true. In that case, we are going to return
4384 without creating varinfos for the fields anyway, so sorting them is a
4388 sort_fieldstack (fieldstack);
4389 /* Due to some C++ FE issues, like PR 22488, we might end up
4390 what appear to be overlapping fields even though they,
4391 in reality, do not overlap. Until the C++ FE is fixed,
4392 we will simply disable field-sensitivity for these cases. */
4393 notokay = check_for_overlaps (fieldstack);
4397 if (VEC_length (fieldoff_s, fieldstack) != 0)
4398 fo = VEC_index (fieldoff_s, fieldstack, 0);
4400 if (fo == NULL || notokay)
4402 vi->is_unknown_size_var = 1;
4405 vi->is_full_var = true;
4406 VEC_free (fieldoff_s, heap, fieldstack);
4410 vi->size = fo->size;
4411 vi->offset = fo->offset;
4412 for (i = VEC_length (fieldoff_s, fieldstack) - 1;
4413 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
4417 const char *newname = "NULL";
4420 newindex = VEC_length (varinfo_t, varmap);
4423 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
4424 "+" HOST_WIDE_INT_PRINT_DEC,
4425 vi->name, fo->offset, fo->size);
4426 newname = ggc_strdup (tempname);
4429 newvi = new_var_info (decl, newindex, newname);
4430 newvi->offset = fo->offset;
4431 newvi->size = fo->size;
4432 newvi->fullsize = vi->fullsize;
4433 insert_into_field_list (vi, newvi);
4434 VEC_safe_push (varinfo_t, heap, varmap, newvi);
4435 if (is_global && (!flag_whole_program || !in_ipa_mode)
4436 && fo->may_have_pointers)
4437 make_constraint_from (newvi, escaped_id);
4443 vi->is_full_var = true;
4445 VEC_free (fieldoff_s, heap, fieldstack);
4450 /* Print out the points-to solution for VAR to FILE. */
4453 dump_solution_for_var (FILE *file, unsigned int var)
4455 varinfo_t vi = get_varinfo (var);
4459 if (find (var) != var)
4461 varinfo_t vipt = get_varinfo (find (var));
4462 fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
4466 fprintf (file, "%s = { ", vi->name);
4467 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4469 fprintf (file, "%s ", get_varinfo (i)->name);
4471 fprintf (file, "}");
4472 if (vi->no_tbaa_pruning)
4473 fprintf (file, " no-tbaa-pruning");
4474 fprintf (file, "\n");
4478 /* Print the points-to solution for VAR to stdout. */
4481 debug_solution_for_var (unsigned int var)
4483 dump_solution_for_var (stdout, var);
4486 /* Create varinfo structures for all of the variables in the
4487 function for intraprocedural mode. */
4490 intra_create_variable_infos (void)
4493 struct constraint_expr lhs, rhs;
4495 /* For each incoming pointer argument arg, create the constraint ARG
4496 = NONLOCAL or a dummy variable if flag_argument_noalias is set. */
4497 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
4501 if (!could_have_pointers (t))
4504 /* If flag_argument_noalias is set, then function pointer
4505 arguments are guaranteed not to point to each other. In that
4506 case, create an artificial variable PARM_NOALIAS and the
4507 constraint ARG = &PARM_NOALIAS. */
4508 if (POINTER_TYPE_P (TREE_TYPE (t)) && flag_argument_noalias > 0)
4511 tree heapvar = heapvar_lookup (t);
4515 lhs.var = get_vi_for_tree (t)->id;
4517 if (heapvar == NULL_TREE)
4520 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
4522 DECL_EXTERNAL (heapvar) = 1;
4523 if (gimple_referenced_vars (cfun))
4524 add_referenced_var (heapvar);
4526 heapvar_insert (t, heapvar);
4528 ann = get_var_ann (heapvar);
4529 if (flag_argument_noalias == 1)
4530 ann->noalias_state = NO_ALIAS;
4531 else if (flag_argument_noalias == 2)
4532 ann->noalias_state = NO_ALIAS_GLOBAL;
4533 else if (flag_argument_noalias == 3)
4534 ann->noalias_state = NO_ALIAS_ANYTHING;
4539 vi = get_vi_for_tree (heapvar);
4540 vi->is_artificial_var = 1;
4541 vi->is_heap_var = 1;
4543 rhs.type = ADDRESSOF;
4545 for (p = get_varinfo (lhs.var); p; p = p->next)
4547 struct constraint_expr temp = lhs;
4549 process_constraint (new_constraint (temp, rhs));
4554 varinfo_t arg_vi = get_vi_for_tree (t);
4556 for (p = arg_vi; p; p = p->next)
4557 make_constraint_from (p, nonlocal_id);
4562 /* Structure used to put solution bitmaps in a hashtable so they can
4563 be shared among variables with the same points-to set. */
4565 typedef struct shared_bitmap_info
4569 } *shared_bitmap_info_t;
4570 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
4572 static htab_t shared_bitmap_table;
4574 /* Hash function for a shared_bitmap_info_t */
4577 shared_bitmap_hash (const void *p)
4579 const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
4580 return bi->hashcode;
4583 /* Equality function for two shared_bitmap_info_t's. */
4586 shared_bitmap_eq (const void *p1, const void *p2)
4588 const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
4589 const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
4590 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
4593 /* Lookup a bitmap in the shared bitmap hashtable, and return an already
4594 existing instance if there is one, NULL otherwise. */
4597 shared_bitmap_lookup (bitmap pt_vars)
4600 struct shared_bitmap_info sbi;
4602 sbi.pt_vars = pt_vars;
4603 sbi.hashcode = bitmap_hash (pt_vars);
4605 slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
4606 sbi.hashcode, NO_INSERT);
4610 return ((shared_bitmap_info_t) *slot)->pt_vars;
4614 /* Add a bitmap to the shared bitmap hashtable. */
4617 shared_bitmap_add (bitmap pt_vars)
4620 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
4622 sbi->pt_vars = pt_vars;
4623 sbi->hashcode = bitmap_hash (pt_vars);
4625 slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
4626 sbi->hashcode, INSERT);
4627 gcc_assert (!*slot);
4628 *slot = (void *) sbi;
4632 /* Set bits in INTO corresponding to the variable uids in solution set
4633 FROM, which came from variable PTR.
4634 For variables that are actually dereferenced, we also use type
4635 based alias analysis to prune the points-to sets.
4636 IS_DEREFED is true if PTR was directly dereferenced, which we use to
4637 help determine whether we are we are allowed to prune using TBAA.
4638 If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of
4642 set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed,
4643 bool no_tbaa_pruning)
4648 gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
4650 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4652 varinfo_t vi = get_varinfo (i);
4654 /* The only artificial variables that are allowed in a may-alias
4655 set are heap variables. */
4656 if (vi->is_artificial_var && !vi->is_heap_var)
4659 if (TREE_CODE (vi->decl) == VAR_DECL
4660 || TREE_CODE (vi->decl) == PARM_DECL
4661 || TREE_CODE (vi->decl) == RESULT_DECL)
4663 /* Just add VI->DECL to the alias set.
4664 Don't type prune artificial vars or points-to sets
4665 for pointers that have not been dereferenced or with
4666 type-based pruning disabled. */
4667 if (vi->is_artificial_var
4670 bitmap_set_bit (into, DECL_UID (vi->decl));
4673 alias_set_type var_alias_set, mem_alias_set;
4674 var_alias_set = get_alias_set (vi->decl);
4675 mem_alias_set = get_alias_set (TREE_TYPE (TREE_TYPE (ptr)));
4676 if (may_alias_p (SSA_NAME_VAR (ptr), mem_alias_set,
4677 vi->decl, var_alias_set, true))
4678 bitmap_set_bit (into, DECL_UID (vi->decl));
4685 static bool have_alias_info = false;
4687 /* Given a pointer variable P, fill in its points-to set, or return
4689 Rather than return false for variables that point-to anything, we
4690 instead find the corresponding SMT, and merge in its aliases. In
4691 addition to these aliases, we also set the bits for the SMT's
4692 themselves and their subsets, as SMT's are still in use by
4693 non-SSA_NAME's, and pruning may eliminate every one of their
4694 aliases. In such a case, if we did not include the right set of
4695 SMT's in the points-to set of the variable, we'd end up with
4696 statements that do not conflict but should. */
4699 find_what_p_points_to (tree p)
4704 if (!have_alias_info)
4707 /* For parameters, get at the points-to set for the actual parm
4709 if (TREE_CODE (p) == SSA_NAME
4710 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
4711 && SSA_NAME_IS_DEFAULT_DEF (p))
4712 lookup_p = SSA_NAME_VAR (p);
4714 vi = lookup_vi_for_tree (lookup_p);
4717 if (vi->is_artificial_var)
4720 /* See if this is a field or a structure. */
4721 if (vi->size != vi->fullsize)
4723 /* Nothing currently asks about structure fields directly,
4724 but when they do, we need code here to hand back the
4730 struct ptr_info_def *pi = get_ptr_info (p);
4733 bool was_pt_anything = false;
4734 bitmap finished_solution;
4737 if (!pi->memory_tag_needed)
4740 /* This variable may have been collapsed, let's get the real
4742 vi = get_varinfo (find (vi->id));
4744 /* Translate artificial variables into SSA_NAME_PTR_INFO
4746 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4748 varinfo_t vi = get_varinfo (i);
4750 if (vi->is_artificial_var)
4752 /* FIXME. READONLY should be handled better so that
4753 flow insensitive aliasing can disregard writable
4755 if (vi->id == nothing_id)
4757 else if (vi->id == anything_id
4758 || vi->id == nonlocal_id
4759 || vi->id == escaped_id
4760 || vi->id == callused_id)
4761 was_pt_anything = 1;
4762 else if (vi->id == readonly_id)
4763 was_pt_anything = 1;
4764 else if (vi->id == integer_id)
4765 was_pt_anything = 1;
4766 else if (vi->is_heap_var)
4767 pi->pt_global_mem = 1;
4771 /* Instead of doing extra work, simply do not create
4772 points-to information for pt_anything pointers. This
4773 will cause the operand scanner to fall back to the
4774 type-based SMT and its aliases. Which is the best
4775 we could do here for the points-to set as well. */
4776 if (was_pt_anything)
4779 /* Share the final set of variables when possible. */
4780 finished_solution = BITMAP_GGC_ALLOC ();
4781 stats.points_to_sets_created++;
4783 set_uids_in_ptset (p, finished_solution, vi->solution,
4784 pi->is_dereferenced,
4785 vi->no_tbaa_pruning);
4786 result = shared_bitmap_lookup (finished_solution);
4790 shared_bitmap_add (finished_solution);
4791 pi->pt_vars = finished_solution;
4795 pi->pt_vars = result;
4796 bitmap_clear (finished_solution);
4799 if (bitmap_empty_p (pi->pt_vars))
4809 /* Mark the ESCAPED solution as call clobbered. Returns false if
4810 pt_anything escaped which needs all locals that have their address
4811 taken marked call clobbered as well. */
4814 clobber_what_escaped (void)
4820 if (!have_alias_info)
4823 /* This variable may have been collapsed, let's get the real
4824 variable for escaped_id. */
4825 vi = get_varinfo (find (escaped_id));
4827 /* If call-used memory escapes we need to include it in the
4828 set of escaped variables. This can happen if a pure
4829 function returns a pointer and this pointer escapes. */
4830 if (bitmap_bit_p (vi->solution, callused_id))
4832 varinfo_t cu_vi = get_varinfo (find (callused_id));
4833 bitmap_ior_into (vi->solution, cu_vi->solution);
4836 /* Mark variables in the solution call-clobbered. */
4837 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4839 varinfo_t vi = get_varinfo (i);
4841 if (vi->is_artificial_var)
4843 /* nothing_id and readonly_id do not cause any
4844 call clobber ops. For anything_id and integer_id
4845 we need to clobber all addressable vars. */
4846 if (vi->id == anything_id
4847 || vi->id == integer_id)
4851 /* Only artificial heap-vars are further interesting. */
4852 if (vi->is_artificial_var && !vi->is_heap_var)
4855 if ((TREE_CODE (vi->decl) == VAR_DECL
4856 || TREE_CODE (vi->decl) == PARM_DECL
4857 || TREE_CODE (vi->decl) == RESULT_DECL)
4858 && !unmodifiable_var_p (vi->decl))
4859 mark_call_clobbered (vi->decl, ESCAPE_TO_CALL);
4865 /* Compute the call-used variables. */
4868 compute_call_used_vars (void)
4873 bool has_anything_id = false;
4875 if (!have_alias_info)
4878 /* This variable may have been collapsed, let's get the real
4879 variable for escaped_id. */
4880 vi = get_varinfo (find (callused_id));
4882 /* Mark variables in the solution call-clobbered. */
4883 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
4885 varinfo_t vi = get_varinfo (i);
4887 if (vi->is_artificial_var)
4889 /* For anything_id and integer_id we need to make
4890 all local addressable vars call-used. */
4891 if (vi->id == anything_id
4892 || vi->id == integer_id)
4893 has_anything_id = true;
4896 /* Only artificial heap-vars are further interesting. */
4897 if (vi->is_artificial_var && !vi->is_heap_var)
4900 if ((TREE_CODE (vi->decl) == VAR_DECL
4901 || TREE_CODE (vi->decl) == PARM_DECL
4902 || TREE_CODE (vi->decl) == RESULT_DECL)
4903 && !unmodifiable_var_p (vi->decl))
4904 bitmap_set_bit (gimple_call_used_vars (cfun), DECL_UID (vi->decl));
4907 /* If anything is call-used, add all addressable locals to the set. */
4908 if (has_anything_id)
4909 bitmap_ior_into (gimple_call_used_vars (cfun),
4910 gimple_addressable_vars (cfun));
4914 /* Dump points-to information to OUTFILE. */
4917 dump_sa_points_to_info (FILE *outfile)
4921 fprintf (outfile, "\nPoints-to sets\n\n");
4923 if (dump_flags & TDF_STATS)
4925 fprintf (outfile, "Stats:\n");
4926 fprintf (outfile, "Total vars: %d\n", stats.total_vars);
4927 fprintf (outfile, "Non-pointer vars: %d\n",
4928 stats.nonpointer_vars);
4929 fprintf (outfile, "Statically unified vars: %d\n",
4930 stats.unified_vars_static);
4931 fprintf (outfile, "Dynamically unified vars: %d\n",
4932 stats.unified_vars_dynamic);
4933 fprintf (outfile, "Iterations: %d\n", stats.iterations);
4934 fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
4935 fprintf (outfile, "Number of implicit edges: %d\n",
4936 stats.num_implicit_edges);
4939 for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
4940 dump_solution_for_var (outfile, i);
4944 /* Debug points-to information to stderr. */
4947 debug_sa_points_to_info (void)
4949 dump_sa_points_to_info (stderr);
4953 /* Initialize the always-existing constraint variables for NULL
4954 ANYTHING, READONLY, and INTEGER */
4957 init_base_vars (void)
4959 struct constraint_expr lhs, rhs;
4961 /* Create the NULL variable, used to represent that a variable points
4963 nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
4964 var_nothing = new_var_info (nothing_tree, nothing_id, "NULL");
4965 insert_vi_for_tree (nothing_tree, var_nothing);
4966 var_nothing->is_artificial_var = 1;
4967 var_nothing->offset = 0;
4968 var_nothing->size = ~0;
4969 var_nothing->fullsize = ~0;
4970 var_nothing->is_special_var = 1;
4971 VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
4973 /* Create the ANYTHING variable, used to represent that a variable
4974 points to some unknown piece of memory. */
4975 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
4976 var_anything = new_var_info (anything_tree, anything_id, "ANYTHING");
4977 insert_vi_for_tree (anything_tree, var_anything);
4978 var_anything->is_artificial_var = 1;
4979 var_anything->size = ~0;
4980 var_anything->offset = 0;
4981 var_anything->next = NULL;
4982 var_anything->fullsize = ~0;
4983 var_anything->is_special_var = 1;
4985 /* Anything points to anything. This makes deref constraints just
4986 work in the presence of linked list and other p = *p type loops,
4987 by saying that *ANYTHING = ANYTHING. */
4988 VEC_safe_push (varinfo_t, heap, varmap, var_anything);
4990 lhs.var = anything_id;
4992 rhs.type = ADDRESSOF;
4993 rhs.var = anything_id;
4996 /* This specifically does not use process_constraint because
4997 process_constraint ignores all anything = anything constraints, since all
4998 but this one are redundant. */
4999 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
5001 /* Create the READONLY variable, used to represent that a variable
5002 points to readonly memory. */
5003 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
5004 var_readonly = new_var_info (readonly_tree, readonly_id, "READONLY");
5005 var_readonly->is_artificial_var = 1;
5006 var_readonly->offset = 0;
5007 var_readonly->size = ~0;
5008 var_readonly->fullsize = ~0;
5009 var_readonly->next = NULL;
5010 var_readonly->is_special_var = 1;
5011 insert_vi_for_tree (readonly_tree, var_readonly);
5012 VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
5014 /* readonly memory points to anything, in order to make deref
5015 easier. In reality, it points to anything the particular
5016 readonly variable can point to, but we don't track this
5019 lhs.var = readonly_id;
5021 rhs.type = ADDRESSOF;
5022 rhs.var = readonly_id; /* FIXME */
5024 process_constraint (new_constraint (lhs, rhs));
5026 /* Create the ESCAPED variable, used to represent the set of escaped
5028 escaped_tree = create_tmp_var_raw (void_type_node, "ESCAPED");
5029 var_escaped = new_var_info (escaped_tree, escaped_id, "ESCAPED");
5030 insert_vi_for_tree (escaped_tree, var_escaped);
5031 var_escaped->is_artificial_var = 1;
5032 var_escaped->offset = 0;
5033 var_escaped->size = ~0;
5034 var_escaped->fullsize = ~0;
5035 var_escaped->is_special_var = 0;
5036 VEC_safe_push (varinfo_t, heap, varmap, var_escaped);
5037 gcc_assert (VEC_index (varinfo_t, varmap, 3) == var_escaped);
5039 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
5041 lhs.var = escaped_id;
5044 rhs.var = escaped_id;
5046 process_constraint (new_constraint (lhs, rhs));
5048 /* Create the NONLOCAL variable, used to represent the set of nonlocal
5050 nonlocal_tree = create_tmp_var_raw (void_type_node, "NONLOCAL");
5051 var_nonlocal = new_var_info (nonlocal_tree, nonlocal_id, "NONLOCAL");
5052 insert_vi_for_tree (nonlocal_tree, var_nonlocal);
5053 var_nonlocal->is_artificial_var = 1;
5054 var_nonlocal->offset = 0;
5055 var_nonlocal->size = ~0;
5056 var_nonlocal->fullsize = ~0;
5057 var_nonlocal->is_special_var = 1;
5058 VEC_safe_push (varinfo_t, heap, varmap, var_nonlocal);
5060 /* Nonlocal memory points to escaped (which includes nonlocal),
5061 in order to make deref easier. */
5063 lhs.var = nonlocal_id;
5065 rhs.type = ADDRESSOF;
5066 rhs.var = escaped_id;
5068 process_constraint (new_constraint (lhs, rhs));
5070 /* Create the CALLUSED variable, used to represent the set of call-used
5072 callused_tree = create_tmp_var_raw (void_type_node, "CALLUSED");
5073 var_callused = new_var_info (callused_tree, callused_id, "CALLUSED");
5074 insert_vi_for_tree (callused_tree, var_callused);
5075 var_callused->is_artificial_var = 1;
5076 var_callused->offset = 0;
5077 var_callused->size = ~0;
5078 var_callused->fullsize = ~0;
5079 var_callused->is_special_var = 0;
5080 VEC_safe_push (varinfo_t, heap, varmap, var_callused);
5082 /* CALLUSED = *CALLUSED, because call-used is may-deref'd at calls, etc. */
5084 lhs.var = callused_id;
5087 rhs.var = callused_id;
5089 process_constraint (new_constraint (lhs, rhs));
5091 /* Create the INTEGER variable, used to represent that a variable points
5093 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
5094 var_integer = new_var_info (integer_tree, integer_id, "INTEGER");
5095 insert_vi_for_tree (integer_tree, var_integer);
5096 var_integer->is_artificial_var = 1;
5097 var_integer->size = ~0;
5098 var_integer->fullsize = ~0;
5099 var_integer->offset = 0;
5100 var_integer->next = NULL;
5101 var_integer->is_special_var = 1;
5102 VEC_safe_push (varinfo_t, heap, varmap, var_integer);
5104 /* INTEGER = ANYTHING, because we don't know where a dereference of
5105 a random integer will point to. */
5107 lhs.var = integer_id;
5109 rhs.type = ADDRESSOF;
5110 rhs.var = anything_id;
5112 process_constraint (new_constraint (lhs, rhs));
5114 /* *ESCAPED = &ESCAPED. This is true because we have to assume
5115 everything pointed to by escaped can also point to escaped. */
5117 lhs.var = escaped_id;
5119 rhs.type = ADDRESSOF;
5120 rhs.var = escaped_id;
5122 process_constraint (new_constraint (lhs, rhs));
5124 /* *ESCAPED = &NONLOCAL. This is true because we have to assume
5125 everything pointed to by escaped can also point to nonlocal. */
5127 lhs.var = escaped_id;
5129 rhs.type = ADDRESSOF;
5130 rhs.var = nonlocal_id;
5132 process_constraint (new_constraint (lhs, rhs));
5135 /* Initialize things necessary to perform PTA */
5138 init_alias_vars (void)
5140 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
5142 bitmap_obstack_initialize (&pta_obstack);
5143 bitmap_obstack_initialize (&oldpta_obstack);
5144 bitmap_obstack_initialize (&predbitmap_obstack);
5146 constraint_pool = create_alloc_pool ("Constraint pool",
5147 sizeof (struct constraint), 30);
5148 variable_info_pool = create_alloc_pool ("Variable info pool",
5149 sizeof (struct variable_info), 30);
5150 constraints = VEC_alloc (constraint_t, heap, 8);
5151 varmap = VEC_alloc (varinfo_t, heap, 8);
5152 vi_for_tree = pointer_map_create ();
5154 memset (&stats, 0, sizeof (stats));
5155 shared_bitmap_table = htab_create (511, shared_bitmap_hash,
5156 shared_bitmap_eq, free);
5160 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
5161 predecessor edges. */
5164 remove_preds_and_fake_succs (constraint_graph_t graph)
5168 /* Clear the implicit ref and address nodes from the successor
5170 for (i = 0; i < FIRST_REF_NODE; i++)
5172 if (graph->succs[i])
5173 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
5174 FIRST_REF_NODE * 2);
5177 /* Free the successor list for the non-ref nodes. */
5178 for (i = FIRST_REF_NODE; i < graph->size; i++)
5180 if (graph->succs[i])
5181 BITMAP_FREE (graph->succs[i]);
5184 /* Now reallocate the size of the successor list as, and blow away
5185 the predecessor bitmaps. */
5186 graph->size = VEC_length (varinfo_t, varmap);
5187 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
5189 free (graph->implicit_preds);
5190 graph->implicit_preds = NULL;
5191 free (graph->preds);
5192 graph->preds = NULL;
5193 bitmap_obstack_release (&predbitmap_obstack);
5196 /* Compute the set of variables we can't TBAA prune. */
5199 compute_tbaa_pruning (void)
5201 unsigned int size = VEC_length (varinfo_t, varmap);
5206 changed = sbitmap_alloc (size);
5207 sbitmap_zero (changed);
5209 /* Mark all initial no_tbaa_pruning nodes as changed. */
5211 for (i = 0; i < size; ++i)
5213 varinfo_t ivi = get_varinfo (i);
5215 if (find (i) == i && ivi->no_tbaa_pruning)
5218 if ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
5219 || VEC_length (constraint_t, graph->complex[i]) > 0)
5221 SET_BIT (changed, i);
5227 while (changed_count > 0)
5229 struct topo_info *ti = init_topo_info ();
5232 compute_topo_order (graph, ti);
5234 while (VEC_length (unsigned, ti->topo_order) != 0)
5238 i = VEC_pop (unsigned, ti->topo_order);
5240 /* If this variable is not a representative, skip it. */
5244 /* If the node has changed, we need to process the complex
5245 constraints and outgoing edges again. */
5246 if (TEST_BIT (changed, i))
5250 VEC(constraint_t,heap) *complex = graph->complex[i];
5252 RESET_BIT (changed, i);
5255 /* Process the complex copy constraints. */
5256 for (j = 0; VEC_iterate (constraint_t, complex, j, c); ++j)
5258 if (c->lhs.type == SCALAR && c->rhs.type == SCALAR)
5260 varinfo_t lhsvi = get_varinfo (find (c->lhs.var));
5262 if (!lhsvi->no_tbaa_pruning)
5264 lhsvi->no_tbaa_pruning = true;
5265 if (!TEST_BIT (changed, lhsvi->id))
5267 SET_BIT (changed, lhsvi->id);
5274 /* Propagate to all successors. */
5275 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
5277 unsigned int to = find (j);
5278 varinfo_t tovi = get_varinfo (to);
5280 /* Don't propagate to ourselves. */
5284 if (!tovi->no_tbaa_pruning)
5286 tovi->no_tbaa_pruning = true;
5287 if (!TEST_BIT (changed, to))
5289 SET_BIT (changed, to);
5297 free_topo_info (ti);
5300 sbitmap_free (changed);
5304 for (i = 0; i < size; ++i)
5306 varinfo_t ivi = get_varinfo (i);
5307 varinfo_t ivip = get_varinfo (find (i));
5309 if (ivip->no_tbaa_pruning)
5311 tree var = ivi->decl;
5313 if (TREE_CODE (var) == SSA_NAME)
5314 var = SSA_NAME_VAR (var);
5316 if (POINTER_TYPE_P (TREE_TYPE (var)))
5318 DECL_NO_TBAA_P (var) = 1;
5320 /* Tell the RTL layer that this pointer can alias
5322 DECL_POINTER_ALIAS_SET (var) = 0;
5329 /* Create points-to sets for the current function. See the comments
5330 at the start of the file for an algorithmic overview. */
5333 compute_points_to_sets (void)
5335 struct scc_info *si;
5338 timevar_push (TV_TREE_PTA);
5341 init_alias_heapvars ();
5343 intra_create_variable_infos ();
5345 /* Now walk all statements and derive aliases. */
5348 block_stmt_iterator bsi;
5351 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5352 if (is_gimple_reg (PHI_RESULT (phi)))
5353 find_func_aliases (phi);
5355 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
5357 tree stmt = bsi_stmt (bsi);
5359 find_func_aliases (stmt);
5361 /* The information in CHANGE_DYNAMIC_TYPE_EXPR nodes has now
5362 been captured, and we can remove them. */
5363 if (TREE_CODE (stmt) == CHANGE_DYNAMIC_TYPE_EXPR)
5364 bsi_remove (&bsi, true);
5373 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5374 dump_constraints (dump_file);
5379 "\nCollapsing static cycles and doing variable "
5382 init_graph (VEC_length (varinfo_t, varmap) * 2);
5385 fprintf (dump_file, "Building predecessor graph\n");
5386 build_pred_graph ();
5389 fprintf (dump_file, "Detecting pointer and location "
5391 si = perform_var_substitution (graph);
5394 fprintf (dump_file, "Rewriting constraints and unifying "
5396 rewrite_constraints (graph, si);
5397 free_var_substitution_info (si);
5399 build_succ_graph ();
5400 move_complex_constraints (graph);
5403 fprintf (dump_file, "Uniting pointer but not location equivalent "
5405 unite_pointer_equivalences (graph);
5408 fprintf (dump_file, "Finding indirect cycles\n");
5409 find_indirect_cycles (graph);
5411 /* Implicit nodes and predecessors are no longer necessary at this
5413 remove_preds_and_fake_succs (graph);
5416 fprintf (dump_file, "Solving graph\n");
5418 solve_graph (graph);
5420 compute_tbaa_pruning ();
5423 dump_sa_points_to_info (dump_file);
5425 have_alias_info = true;
5427 timevar_pop (TV_TREE_PTA);
5431 /* Delete created points-to sets. */
5434 delete_points_to_sets (void)
5438 htab_delete (shared_bitmap_table);
5439 if (dump_file && (dump_flags & TDF_STATS))
5440 fprintf (dump_file, "Points to sets created:%d\n",
5441 stats.points_to_sets_created);
5443 pointer_map_destroy (vi_for_tree);
5444 bitmap_obstack_release (&pta_obstack);
5445 VEC_free (constraint_t, heap, constraints);
5447 for (i = 0; i < graph->size; i++)
5448 VEC_free (constraint_t, heap, graph->complex[i]);
5449 free (graph->complex);
5452 free (graph->succs);
5454 free (graph->pe_rep);
5455 free (graph->indirect_cycles);
5458 VEC_free (varinfo_t, heap, varmap);
5459 free_alloc_pool (variable_info_pool);
5460 free_alloc_pool (constraint_pool);
5461 have_alias_info = false;
5464 /* Return true if we should execute IPA PTA. */
5468 return (flag_unit_at_a_time != 0
5470 /* Don't bother doing anything if the program has errors. */
5471 && !(errorcount || sorrycount));
5474 /* Execute the driver for IPA PTA. */
5476 ipa_pta_execute (void)
5478 struct cgraph_node *node;
5479 struct scc_info *si;
5482 init_alias_heapvars ();
5485 for (node = cgraph_nodes; node; node = node->next)
5487 if (!node->analyzed || cgraph_is_master_clone (node))
5491 varid = create_function_info_for (node->decl,
5492 cgraph_node_name (node));
5493 if (node->local.externally_visible)
5495 varinfo_t fi = get_varinfo (varid);
5496 for (; fi; fi = fi->next)
5497 make_constraint_from (fi, anything_id);
5501 for (node = cgraph_nodes; node; node = node->next)
5503 if (node->analyzed && cgraph_is_master_clone (node))
5505 struct function *func = DECL_STRUCT_FUNCTION (node->decl);
5507 tree old_func_decl = current_function_decl;
5510 "Generating constraints for %s\n",
5511 cgraph_node_name (node));
5513 current_function_decl = node->decl;
5515 FOR_EACH_BB_FN (bb, func)
5517 block_stmt_iterator bsi;
5520 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5522 if (is_gimple_reg (PHI_RESULT (phi)))
5524 find_func_aliases (phi);
5528 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
5530 tree stmt = bsi_stmt (bsi);
5531 find_func_aliases (stmt);
5534 current_function_decl = old_func_decl;
5539 /* Make point to anything. */
5545 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
5546 dump_constraints (dump_file);
5551 "\nCollapsing static cycles and doing variable "
5554 init_graph (VEC_length (varinfo_t, varmap) * 2);
5555 build_pred_graph ();
5556 si = perform_var_substitution (graph);
5557 rewrite_constraints (graph, si);
5558 free_var_substitution_info (si);
5560 build_succ_graph ();
5561 move_complex_constraints (graph);
5562 unite_pointer_equivalences (graph);
5563 find_indirect_cycles (graph);
5565 /* Implicit nodes and predecessors are no longer necessary at this
5567 remove_preds_and_fake_succs (graph);
5570 fprintf (dump_file, "\nSolving graph\n");
5572 solve_graph (graph);
5575 dump_sa_points_to_info (dump_file);
5578 delete_alias_heapvars ();
5579 delete_points_to_sets ();
5583 struct simple_ipa_opt_pass pass_ipa_pta =
5588 gate_ipa_pta, /* gate */
5589 ipa_pta_execute, /* execute */
5592 0, /* static_pass_number */
5593 TV_IPA_PTA, /* tv_id */
5594 0, /* properties_required */
5595 0, /* properties_provided */
5596 0, /* properties_destroyed */
5597 0, /* todo_flags_start */
5598 TODO_update_ssa /* todo_flags_finish */
5602 /* Initialize the heapvar for statement mapping. */
5604 init_alias_heapvars (void)
5606 if (!heapvar_for_stmt)
5607 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
5612 delete_alias_heapvars (void)
5614 htab_delete (heapvar_for_stmt);
5615 heapvar_for_stmt = NULL;
5619 #include "gt-tree-ssa-structalias.h"